36 static inline void *xfarray_scratch(struct xfarray *array)  in xfarray_scratch()  argument
38 	return (array + 1);  in xfarray_scratch()
44 	struct xfarray	*array,  in xfarray_idx()  argument
47 	if (array->obj_size_log >= 0)  in xfarray_idx()
48 		return (xfarray_idx_t)pos >> array->obj_size_log;  in xfarray_idx()
50 	return div_u64((xfarray_idx_t)pos, array->obj_size);  in xfarray_idx()
54 static inline loff_t xfarray_pos(struct xfarray *array, xfarray_idx_t idx)  in xfarray_pos()  argument
56 	if (array->obj_size_log >= 0)  in xfarray_pos()
57 		return idx << array->obj_size_log;  in xfarray_pos()
59 	return idx * array->obj_size;  in xfarray_pos()
76 	struct xfarray		*array;  in xfarray_create()  local
87 	array = kzalloc(sizeof(struct xfarray) + obj_size, XCHK_GFP_FLAGS);  in xfarray_create()
88 	if (!array)  in xfarray_create()
91 	array->xfile = xfile;  in xfarray_create()
92 	array->obj_size = obj_size;  in xfarray_create()
95 		array->obj_size_log = ilog2(obj_size);  in xfarray_create()
97 		array->obj_size_log = -1;  in xfarray_create()
99 	array->max_nr = xfarray_idx(array, MAX_LFS_FILESIZE);  in xfarray_create()
100 	trace_xfarray_create(array, required_capacity);  in xfarray_create()
103 		if (array->max_nr < required_capacity) {  in xfarray_create()
107 		array->max_nr = required_capacity;  in xfarray_create()
110 	*arrayp = array;  in xfarray_create()
114 	kfree(array);  in xfarray_create()
123 	struct xfarray	*array)  in xfarray_destroy()  argument
125 	xfile_destroy(array->xfile);  in xfarray_destroy()
126 	kfree(array);  in xfarray_destroy()
132 	struct xfarray	*array,  in xfarray_load()  argument
136 	if (idx >= array->nr)  in xfarray_load()
139 	return xfile_obj_load(array->xfile, ptr, array->obj_size,  in xfarray_load()
140 			xfarray_pos(array, idx));  in xfarray_load()
146 	struct xfarray	*array,  in xfarray_is_unset()  argument
149 	void		*temp = xfarray_scratch(array);  in xfarray_is_unset()
152 	if (array->unset_slots == 0)  in xfarray_is_unset()
155 	error = xfile_obj_load(array->xfile, temp, array->obj_size, pos);  in xfarray_is_unset()
156 	if (!error && xfarray_element_is_null(array, temp))  in xfarray_is_unset()
168 	struct xfarray	*array,  in xfarray_unset()  argument
171 	void		*temp = xfarray_scratch(array);  in xfarray_unset()
172 	loff_t		pos = xfarray_pos(array, idx);  in xfarray_unset()
175 	if (idx >= array->nr)  in xfarray_unset()
178 	if (idx == array->nr - 1) {  in xfarray_unset()
179 		array->nr--;  in xfarray_unset()
183 	if (xfarray_is_unset(array, pos))  in xfarray_unset()
186 	memset(temp, 0, array->obj_size);  in xfarray_unset()
187 	error = xfile_obj_store(array->xfile, temp, array->obj_size, pos);  in xfarray_unset()
191 	array->unset_slots++;  in xfarray_unset()
201 	struct xfarray	*array,  in xfarray_store()  argument
207 	if (idx >= array->max_nr)  in xfarray_store()
210 	ASSERT(!xfarray_element_is_null(array, ptr));  in xfarray_store()
212 	ret = xfile_obj_store(array->xfile, ptr, array->obj_size,  in xfarray_store()
213 			xfarray_pos(array, idx));  in xfarray_store()
217 	array->nr = max(array->nr, idx + 1);  in xfarray_store()
224 	struct xfarray	*array,  in xfarray_element_is_null()  argument
227 	return !memchr_inv(ptr, 0, array->obj_size);  in xfarray_element_is_null()
236 	struct xfarray	*array,  in xfarray_store_anywhere()  argument
239 	void		*temp = xfarray_scratch(array);  in xfarray_store_anywhere()
240 	loff_t		endpos = xfarray_pos(array, array->nr);  in xfarray_store_anywhere()
246 	     pos < endpos && array->unset_slots > 0;  in xfarray_store_anywhere()
247 	     pos += array->obj_size) {  in xfarray_store_anywhere()
248 		error = xfile_obj_load(array->xfile, temp, array->obj_size,  in xfarray_store_anywhere()
250 		if (error || !xfarray_element_is_null(array, temp))  in xfarray_store_anywhere()
253 		error = xfile_obj_store(array->xfile, ptr, array->obj_size,  in xfarray_store_anywhere()
258 		array->unset_slots--;  in xfarray_store_anywhere()
263 	array->unset_slots = 0;  in xfarray_store_anywhere()
264 	return xfarray_append(array, ptr);  in xfarray_store_anywhere()
270 	struct xfarray	*array)  in xfarray_length()  argument
272 	return array->nr;  in xfarray_length()
287 	struct xfarray	*array,  in xfarray_find_data()  argument
292 	loff_t		end_pos = *pos + array->obj_size - 1;  in xfarray_find_data()
299 	if (pgoff != 0 && pgoff + array->obj_size - 1 < PAGE_SIZE)  in xfarray_find_data()
313 	new_pos = xfile_seek_data(array->xfile, end_pos);  in xfarray_find_data()
326 	new_pos = roundup_64(new_pos, array->obj_size);  in xfarray_find_data()
327 	*cur = xfarray_idx(array, new_pos);  in xfarray_find_data()
328 	*pos = xfarray_pos(array, *cur);  in xfarray_find_data()
340 	struct xfarray	*array,  in xfarray_load_next()  argument
345 	loff_t		pos = xfarray_pos(array, cur);  in xfarray_load_next()
349 		if (cur >= array->nr)  in xfarray_load_next()
356 		error = xfarray_find_data(array, &cur, &pos);  in xfarray_load_next()
359 		error = xfarray_load(array, cur, rec);  in xfarray_load_next()
364 		pos += array->obj_size;  in xfarray_load_next()
365 	} while (xfarray_element_is_null(array, rec));  in xfarray_load_next()
393 	return xfarray_load(si->array, idx, ptr);  in xfarray_sort_load()
404 	return xfarray_store(si->array, idx, ptr);  in xfarray_sort_store()
433 	struct xfarray		*array)  in xfarray_pivot_rec_sz()  argument
435 	return round_up(array->obj_size, 8) + sizeof(xfarray_idx_t);  in xfarray_pivot_rec_sz()
441 	struct xfarray		*array,  in xfarray_sortinfo_alloc()  argument
448 	size_t			pivot_rec_sz = xfarray_pivot_rec_sz(array);  in xfarray_sortinfo_alloc()
465 	max_stack_depth = ilog2(array->nr) + 1 - (XFARRAY_ISORT_SHIFT - 1);  in xfarray_sortinfo_alloc()
475 			XFARRAY_ISORT_NR * array->obj_size);  in xfarray_sortinfo_alloc()
481 	si->array = array;  in xfarray_sortinfo_alloc()
488 	xfarray_sortinfo_hi(si)[0] = array->nr - 1;  in xfarray_sortinfo_alloc()
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()
555 	error = xfile_obj_load(si->array->xfile, scratch, len, lo_pos);  in xfarray_isort()
560 	sort(scratch, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);  in xfarray_isort()
563 	return xfile_obj_store(si->array->xfile, scratch, len, lo_pos);  in xfarray_isort()
575 	error = xfile_get_page(si->array->xfile, pos, len, &si->xfpage);  in xfarray_sort_get_page()
598 	return xfile_put_page(si->array->xfile, &si->xfpage);  in xfarray_sort_put_page()
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()
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()
641 	sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);  in xfarray_pagesort()
658 	return xfarray_sortinfo_pivot(si) + si->array->obj_size;  in xfarray_sortinfo_pivot_array()
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()
743 		error = xfarray_load_next(si->array, &idx, recp);  in xfarray_qsort_pivot()
759 	memcpy(pivot, recp, si->array->obj_size);  in xfarray_qsort_pivot()
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()
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()
888 			si->array->obj_size);  in xfarray_sort_load_cached()
931 	struct xfarray		*array,  in xfarray_sort()  argument
938 	void			*scratch = xfarray_scratch(array);  in xfarray_sort()
942 	if (array->nr < 2)  in xfarray_sort()
944 	if (array->nr >= QSORT_MAX_RECS)  in xfarray_sort()
947 	error = xfarray_sortinfo_alloc(array, cmp_fn, flags, &si);  in xfarray_sort()