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
489 	si->relax = INIT_XCHK_RELAX;  in xfarray_sortinfo_alloc()
491 		si->relax.interruptible = false;  in xfarray_sortinfo_alloc()
493 	trace_xfarray_sort(si, nr_bytes);  in xfarray_sortinfo_alloc()
494 	*infop = si;  in xfarray_sortinfo_alloc()
501 	struct xfarray_sortinfo	*si,  in xfarray_sort_terminated()  argument
509 	if (xchk_maybe_relax(&si->relax)) {  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_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_store(si->array->xfile, scratch, len, lo_pos);  in xfarray_isort()
573 	struct xfarray_sortinfo	*si,  in xfarray_foliosort()  argument
579 	loff_t			lo_pos = xfarray_pos(si->array, lo);  in xfarray_foliosort()
580 	uint64_t		len = xfarray_pos(si->array, hi - lo + 1);  in xfarray_foliosort()
586 	xfarray_sort_bump_loads(si);  in xfarray_foliosort()
587 	folio = xfile_get_folio(si->array->xfile, lo_pos, len, XFILE_ALLOC);  in xfarray_foliosort()
593 	trace_xfarray_foliosort(si, lo, hi);  in xfarray_foliosort()
595 	xfarray_sort_bump_heapsorts(si);  in xfarray_foliosort()
597 	sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);  in xfarray_foliosort()
599 	xfarray_sort_bump_stores(si);  in xfarray_foliosort()
600 	xfile_put_folio(si->array->xfile, folio);  in xfarray_foliosort()
605 static inline void *xfarray_sortinfo_pivot(struct xfarray_sortinfo *si)  in xfarray_sortinfo_pivot()  argument
607 	return xfarray_sortinfo_hi(si) + si->max_stack_depth;  in xfarray_sortinfo_pivot()
613 	struct xfarray_sortinfo	*si)  in xfarray_sortinfo_pivot_array()  argument
615 	return xfarray_sortinfo_pivot(si) + si->array->obj_size;  in xfarray_sortinfo_pivot_array()
650 	struct xfarray_sortinfo	*si,  in xfarray_qsort_pivot()  argument
654 	void			*pivot = xfarray_sortinfo_pivot(si);  in xfarray_qsort_pivot()
655 	void			*parray = xfarray_sortinfo_pivot_array(si);  in xfarray_qsort_pivot()
659 	size_t			pivot_rec_sz = xfarray_pivot_rec_sz(si->array);  in xfarray_qsort_pivot()
687 		if (likely(si->array->unset_slots == 0)) {  in xfarray_qsort_pivot()
688 			error = xfarray_sort_load(si, *idxp, recp);  in xfarray_qsort_pivot()
699 		xfarray_sort_bump_loads(si);  in xfarray_qsort_pivot()
700 		error = xfarray_load_next(si->array, &idx, recp);  in xfarray_qsort_pivot()
705 	xfarray_sort_bump_heapsorts(si);  in xfarray_qsort_pivot()
706 	sort(parray, XFARRAY_QSORT_PIVOT_NR, pivot_rec_sz, si->cmp_fn, NULL);  in xfarray_qsort_pivot()
716 	memcpy(pivot, recp, si->array->obj_size);  in xfarray_qsort_pivot()
739 	error = xfarray_sort_store(si, lo, pivot);  in xfarray_qsort_pivot()
746 	return xfarray_sort_store(si, *idxp, recp);  in xfarray_qsort_pivot()
757 	struct xfarray_sortinfo	*si,  in xfarray_qsort_push()  argument
764 	if (si->stack_depth >= si->max_stack_depth - 1) {  in xfarray_qsort_push()
765 		ASSERT(si->stack_depth < si->max_stack_depth - 1);  in xfarray_qsort_push()
769 	si->max_stack_used = max_t(uint8_t, si->max_stack_used,  in xfarray_qsort_push()
770 					    si->stack_depth + 2);  in xfarray_qsort_push()
772 	si_lo[si->stack_depth + 1] = lo + 1;  in xfarray_qsort_push()
773 	si_hi[si->stack_depth + 1] = si_hi[si->stack_depth];  in xfarray_qsort_push()
774 	si_hi[si->stack_depth++] = lo - 1;  in xfarray_qsort_push()
780 	if (si_hi[si->stack_depth]     - si_lo[si->stack_depth] >  in xfarray_qsort_push()
781 	    si_hi[si->stack_depth - 1] - si_lo[si->stack_depth - 1]) {  in xfarray_qsort_push()
782 		swap(si_lo[si->stack_depth], si_lo[si->stack_depth - 1]);  in xfarray_qsort_push()
783 		swap(si_hi[si->stack_depth], si_hi[si->stack_depth - 1]);  in xfarray_qsort_push()
791 	struct xfarray_sortinfo	*si)  in xfarray_sort_scan_done()  argument
793 	if (si->folio)  in xfarray_sort_scan_done()
794 		xfile_put_folio(si->array->xfile, si->folio);  in xfarray_sort_scan_done()
795 	si->folio = NULL;  in xfarray_sort_scan_done()
806 	struct xfarray_sortinfo	*si,  in xfarray_sort_scan()  argument
810 	loff_t			idx_pos = xfarray_pos(si->array, idx);  in xfarray_sort_scan()
813 	if (xfarray_sort_terminated(si, &error))  in xfarray_sort_scan()
816 	trace_xfarray_sort_scan(si, idx);  in xfarray_sort_scan()
819 	if (si->folio &&  in xfarray_sort_scan()
820 	    (idx < si->first_folio_idx || idx > si->last_folio_idx))  in xfarray_sort_scan()
821 		xfarray_sort_scan_done(si);  in xfarray_sort_scan()
824 	if (!si->folio) {  in xfarray_sort_scan()
828 		folio = xfile_get_folio(si->array->xfile, idx_pos,  in xfarray_sort_scan()
829 				si->array->obj_size, XFILE_ALLOC);  in xfarray_sort_scan()
832 		si->folio = folio;  in xfarray_sort_scan()
834 		si->first_folio_idx = xfarray_idx(si->array,  in xfarray_sort_scan()
835 				folio_pos(si->folio) + si->array->obj_size - 1);  in xfarray_sort_scan()
837 		next_pos = folio_pos(si->folio) + folio_size(si->folio);  in xfarray_sort_scan()
838 		si->last_folio_idx = xfarray_idx(si->array, next_pos - 1);  in xfarray_sort_scan()
839 		if (xfarray_pos(si->array, si->last_folio_idx + 1) > next_pos)  in xfarray_sort_scan()
840 			si->last_folio_idx--;  in xfarray_sort_scan()
842 		trace_xfarray_sort_scan(si, idx);  in xfarray_sort_scan()
849 	if (idx < si->first_folio_idx || idx > si->last_folio_idx) {  in xfarray_sort_scan()
850 		void		*temp = xfarray_scratch(si->array);  in xfarray_sort_scan()
852 		error = xfile_load(si->array->xfile, temp, si->array->obj_size,  in xfarray_sort_scan()
862 	*ptrp = folio_address(si->folio) + offset_in_folio(si->folio, idx_pos);  in xfarray_sort_scan()
909 	struct xfarray_sortinfo	*si;  in xfarray_sort()  local
921 	error = xfarray_sortinfo_alloc(array, cmp_fn, flags, &si);  in xfarray_sort()
924 	si_lo = xfarray_sortinfo_lo(si);  in xfarray_sort()
925 	si_hi = xfarray_sortinfo_hi(si);  in xfarray_sort()
926 	pivot = xfarray_sortinfo_pivot(si);  in xfarray_sort()
928 	while (si->stack_depth >= 0) {  in xfarray_sort()
931 		lo = si_lo[si->stack_depth];  in xfarray_sort()
932 		hi = si_hi[si->stack_depth];  in xfarray_sort()
934 		trace_xfarray_qsort(si, lo, hi);  in xfarray_sort()
938 			si->stack_depth--;  in xfarray_sort()
946 		ret = xfarray_foliosort(si, lo, hi);  in xfarray_sort()
950 			si->stack_depth--;  in xfarray_sort()
955 		if (xfarray_want_isort(si, lo, hi)) {  in xfarray_sort()
956 			error = xfarray_isort(si, lo, hi);  in xfarray_sort()
959 			si->stack_depth--;  in xfarray_sort()
964 		error = xfarray_qsort_pivot(si, lo, hi);  in xfarray_sort()
980 			error = xfarray_sort_scan(si, hi, &p);  in xfarray_sort()
983 			while (xfarray_sort_cmp(si, p, pivot) >= 0 && lo < hi) {  in xfarray_sort()
985 				error = xfarray_sort_scan(si, hi, &p);  in xfarray_sort()
990 				memcpy(scratch, p, si->array->obj_size);  in xfarray_sort()
991 			xfarray_sort_scan_done(si);  in xfarray_sort()
992 			if (xfarray_sort_terminated(si, &error))  in xfarray_sort()
997 				error = xfarray_sort_store(si, lo++, scratch);  in xfarray_sort()
1006 			error = xfarray_sort_scan(si, lo, &p);  in xfarray_sort()
1009 			while (xfarray_sort_cmp(si, p, pivot) <= 0 && lo < hi) {  in xfarray_sort()
1011 				error = xfarray_sort_scan(si, lo, &p);  in xfarray_sort()
1016 				memcpy(scratch, p, si->array->obj_size);  in xfarray_sort()
1017 			xfarray_sort_scan_done(si);  in xfarray_sort()
1018 			if (xfarray_sort_terminated(si, &error))  in xfarray_sort()
1023 				error = xfarray_sort_store(si, hi--, scratch);  in xfarray_sort()
1028 			if (xfarray_sort_terminated(si, &error))  in xfarray_sort()
1038 		error = xfarray_sort_store(si, lo, pivot);  in xfarray_sort()
1043 		error = xfarray_qsort_push(si, si_lo, si_hi, lo, hi);  in xfarray_sort()
1047 		if (xfarray_sort_terminated(si, &error))  in xfarray_sort()
1052 	trace_xfarray_sort_stats(si, error);  in xfarray_sort()
1053 	xfarray_sort_scan_done(si);  in xfarray_sort()
1054 	kvfree(si);  in xfarray_sort()