Lines Matching refs:si
374 # define xfarray_sort_bump_loads(si) do { (si)->loads++; } while (0)
375 # define xfarray_sort_bump_stores(si) do { (si)->stores++; } while (0)
376 # define xfarray_sort_bump_compares(si) do { (si)->compares++; } while (0)
377 # define xfarray_sort_bump_heapsorts(si) do { (si)->heapsorts++; } while (0)
379 # define xfarray_sort_bump_loads(si)
380 # define xfarray_sort_bump_stores(si)
381 # define xfarray_sort_bump_compares(si)
382 # define xfarray_sort_bump_heapsorts(si)
388 struct xfarray_sortinfo *si,
392 xfarray_sort_bump_loads(si);
393 return xfarray_load(si->array, idx, ptr);
399 struct xfarray_sortinfo *si,
403 xfarray_sort_bump_stores(si);
404 return xfarray_store(si->array, idx, ptr);
410 struct xfarray_sortinfo *si,
414 xfarray_sort_bump_compares(si);
415 return si->cmp_fn(a, b);
419 static inline xfarray_idx_t *xfarray_sortinfo_lo(struct xfarray_sortinfo *si)
421 return (xfarray_idx_t *)(si + 1);
425 static inline xfarray_idx_t *xfarray_sortinfo_hi(struct xfarray_sortinfo *si)
427 return xfarray_sortinfo_lo(si) + si->max_stack_depth;
446 struct xfarray_sortinfo *si;
477 si = kvzalloc(nr_bytes, XCHK_GFP_FLAGS);
478 if (!si)
481 si->array = array;
482 si->cmp_fn = cmp_fn;
483 si->flags = flags;
484 si->max_stack_depth = max_stack_depth;
485 si->max_stack_used = 1;
487 xfarray_sortinfo_lo(si)[0] = 0;
488 xfarray_sortinfo_hi(si)[0] = array->nr - 1;
490 trace_xfarray_sort(si, nr_bytes);
491 *infop = si;
498 struct xfarray_sortinfo *si,
508 if ((si->flags & XFARRAY_SORT_KILLABLE) &&
520 struct xfarray_sortinfo *si,
532 static inline void *xfarray_sortinfo_isort_scratch(struct xfarray_sortinfo *si)
534 return xfarray_sortinfo_hi(si) + si->max_stack_depth;
543 struct xfarray_sortinfo *si,
547 void *scratch = xfarray_sortinfo_isort_scratch(si);
548 loff_t lo_pos = xfarray_pos(si->array, lo);
549 loff_t len = xfarray_pos(si->array, hi - lo + 1);
552 trace_xfarray_isort(si, lo, hi);
554 xfarray_sort_bump_loads(si);
555 error = xfile_obj_load(si->array->xfile, scratch, len, lo_pos);
559 xfarray_sort_bump_heapsorts(si);
560 sort(scratch, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
562 xfarray_sort_bump_stores(si);
563 return xfile_obj_store(si->array->xfile, scratch, len, lo_pos);
569 struct xfarray_sortinfo *si,
575 error = xfile_get_page(si->array->xfile, pos, len, &si->xfpage);
583 si->page_kaddr = kmap_local_page(si->xfpage.page);
590 struct xfarray_sortinfo *si)
592 if (!si->page_kaddr)
595 kunmap_local(si->page_kaddr);
596 si->page_kaddr = NULL;
598 return xfile_put_page(si->array->xfile, &si->xfpage);
604 struct xfarray_sortinfo *si,
613 lo_page = xfarray_pos(si->array, lo) >> PAGE_SHIFT;
614 end_pos = xfarray_pos(si->array, hi) + si->array->obj_size - 1;
623 struct xfarray_sortinfo *si,
628 loff_t lo_pos = xfarray_pos(si->array, lo);
629 uint64_t len = xfarray_pos(si->array, hi - lo);
632 trace_xfarray_pagesort(si, lo, hi);
634 xfarray_sort_bump_loads(si);
635 error = xfarray_sort_get_page(si, lo_pos, len);
639 xfarray_sort_bump_heapsorts(si);
640 startp = si->page_kaddr + offset_in_page(lo_pos);
641 sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
643 xfarray_sort_bump_stores(si);
644 return xfarray_sort_put_page(si);
648 static inline void *xfarray_sortinfo_pivot(struct xfarray_sortinfo *si)
650 return xfarray_sortinfo_hi(si) + si->max_stack_depth;
656 struct xfarray_sortinfo *si)
658 return xfarray_sortinfo_pivot(si) + si->array->obj_size;
693 struct xfarray_sortinfo *si,
697 void *pivot = xfarray_sortinfo_pivot(si);
698 void *parray = xfarray_sortinfo_pivot_array(si);
702 size_t pivot_rec_sz = xfarray_pivot_rec_sz(si->array);
730 if (likely(si->array->unset_slots == 0)) {
731 error = xfarray_sort_load(si, *idxp, recp);
742 xfarray_sort_bump_loads(si);
743 error = xfarray_load_next(si->array, &idx, recp);
748 xfarray_sort_bump_heapsorts(si);
749 sort(parray, XFARRAY_QSORT_PIVOT_NR, pivot_rec_sz, si->cmp_fn, NULL);
759 memcpy(pivot, recp, si->array->obj_size);
782 error = xfarray_sort_store(si, lo, pivot);
789 return xfarray_sort_store(si, *idxp, recp);
800 struct xfarray_sortinfo *si,
807 if (si->stack_depth >= si->max_stack_depth - 1) {
808 ASSERT(si->stack_depth < si->max_stack_depth - 1);
812 si->max_stack_used = max_t(uint8_t, si->max_stack_used,
813 si->stack_depth + 2);
815 si_lo[si->stack_depth + 1] = lo + 1;
816 si_hi[si->stack_depth + 1] = si_hi[si->stack_depth];
817 si_hi[si->stack_depth++] = lo - 1;
823 if (si_hi[si->stack_depth] - si_lo[si->stack_depth] >
824 si_hi[si->stack_depth - 1] - si_lo[si->stack_depth - 1]) {
825 swap(si_lo[si->stack_depth], si_lo[si->stack_depth - 1]);
826 swap(si_hi[si->stack_depth], si_hi[si->stack_depth - 1]);
838 struct xfarray_sortinfo *si,
842 loff_t idx_pos = xfarray_pos(si->array, idx);
852 endpage = (idx_pos + si->array->obj_size - 1) >> PAGE_SHIFT;
854 error = xfarray_sort_put_page(si);
858 if (xfarray_sort_terminated(si, &error))
861 return xfile_obj_load(si->array->xfile, ptr,
862 si->array->obj_size, idx_pos);
866 if (xfile_page_cached(&si->xfpage) &&
867 xfile_page_index(&si->xfpage) != startpage) {
868 error = xfarray_sort_put_page(si);
877 if (!xfile_page_cached(&si->xfpage)) {
878 if (xfarray_sort_terminated(si, &error))
881 error = xfarray_sort_get_page(si, startpage << PAGE_SHIFT,
887 memcpy(ptr, si->page_kaddr + offset_in_page(idx_pos),
888 si->array->obj_size);
935 struct xfarray_sortinfo *si;
947 error = xfarray_sortinfo_alloc(array, cmp_fn, flags, &si);
950 si_lo = xfarray_sortinfo_lo(si);
951 si_hi = xfarray_sortinfo_hi(si);
952 pivot = xfarray_sortinfo_pivot(si);
954 while (si->stack_depth >= 0) {
955 lo = si_lo[si->stack_depth];
956 hi = si_hi[si->stack_depth];
958 trace_xfarray_qsort(si, lo, hi);
962 si->stack_depth--;
970 if (xfarray_want_pagesort(si, lo, hi)) {
971 error = xfarray_pagesort(si, lo, hi);
974 si->stack_depth--;
979 if (xfarray_want_isort(si, lo, hi)) {
980 error = xfarray_isort(si, lo, hi);
983 si->stack_depth--;
988 error = xfarray_qsort_pivot(si, lo, hi);
1002 error = xfarray_sort_load_cached(si, hi, scratch);
1005 while (xfarray_sort_cmp(si, scratch, pivot) >= 0 &&
1008 error = xfarray_sort_load_cached(si, hi,
1013 error = xfarray_sort_put_page(si);
1017 if (xfarray_sort_terminated(si, &error))
1022 error = xfarray_sort_store(si, lo++, scratch);
1031 error = xfarray_sort_load_cached(si, lo, scratch);
1034 while (xfarray_sort_cmp(si, scratch, pivot) <= 0 &&
1037 error = xfarray_sort_load_cached(si, lo,
1042 error = xfarray_sort_put_page(si);
1046 if (xfarray_sort_terminated(si, &error))
1051 error = xfarray_sort_store(si, hi--, scratch);
1056 if (xfarray_sort_terminated(si, &error))
1066 error = xfarray_sort_store(si, lo, pivot);
1071 error = xfarray_qsort_push(si, si_lo, si_hi, lo, hi);
1075 if (xfarray_sort_terminated(si, &error))
1080 trace_xfarray_sort_stats(si, error);
1081 kvfree(si);