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