Lines Matching full:array
19 * This memory array uses an xfile (which itself is a shmem file) to store
22 * because we don't have to pin so much memory. However, array access is less
23 * direct than would be in a regular memory array. Access to the array is
25 * provided for convenience. Array elements can be unset, which sets them to
34 * buffer array items when we need space to store values temporarily.
36 static inline void *xfarray_scratch(struct xfarray *array) in xfarray_scratch() argument
38 return (array + 1); in xfarray_scratch()
41 /* Compute array index given an xfile offset. */
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()
53 /* Compute xfile offset of array element. */
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()
63 * Initialize a big memory array. Array records cannot be larger than a
64 * page, and the array cannot span more bytes than the page cache supports.
65 * If @required_capacity is nonzero, the maximum array size will be set to this
66 * quantity and the array creation will fail if the underlying storage cannot
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()
120 /* Destroy the array. */
123 struct xfarray *array) in xfarray_destroy() argument
125 xfile_destroy(array->xfile); in xfarray_destroy()
126 kfree(array); in xfarray_destroy()
129 /* Load an element from the array. */
132 struct xfarray *array, in xfarray_load() argument
136 if (idx >= array->nr) in xfarray_load()
139 return xfile_load(array->xfile, ptr, array->obj_size, in xfarray_load()
140 xfarray_pos(array, idx)); in xfarray_load()
143 /* Is this array element potentially unset? */
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_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()
163 * Unset an array element. If @idx is the last element in the array, the
164 * array will be truncated. Otherwise, the entry will be zeroed.
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_store(array->xfile, temp, array->obj_size, pos); in xfarray_unset()
191 array->unset_slots++; in xfarray_unset()
196 * Store an element in the array. The element must not be completely zeroed,
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_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()
221 /* Is this array element NULL? */
224 struct xfarray *array, in xfarray_element_is_null() argument
227 return !memchr_inv(ptr, 0, array->obj_size); in xfarray_element_is_null()
231 * Store an element anywhere in the array that is unset. If there are no
232 * unset slots, append the element to the array.
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_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_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()
267 /* Return length of array. */
270 struct xfarray *array) in xfarray_length() argument
272 return array->nr; in xfarray_length()
276 * Decide which array item we're going to read as part of an _iter_get.
277 * @cur is the array index, and @pos is the file offset of that array index in
281 * iterating a (possibly sparse) array we need to figure out if the cursor is
287 struct xfarray *array, in xfarray_find_data() argument
292 loff_t end_pos = *pos + array->obj_size - 1; in xfarray_find_data()
296 * If the current array record is not adjacent to a page boundary, we 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()
323 * find more data. Move the array index to the first record past the 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()
333 * Starting at *idx, fetch the next non-null array entry and advance the index
335 * the array. Callers must set @*idx to XFARRAY_CURSOR_INIT before the first
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()
385 /* Load an array element for sorting. */
393 return xfarray_load(si->array, idx, ptr); in xfarray_sort_load()
396 /* Store an array element for sorting. */
404 return xfarray_store(si->array, idx, ptr); in xfarray_sort_store()
407 /* Compare an array element for sorting. */
430 /* Size of each element in the quicksort pivot array. */
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()
525 * For array subsets that fit in the scratchpad, it's much faster to in xfarray_want_isort()
538 * Sort a small number of array records using scratchpad memory. The records
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_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_store(si->array->xfile, scratch, len, lo_pos); in xfarray_isort()
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()
587 folio = xfile_get_folio(si->array->xfile, lo_pos, len, XFILE_ALLOC); in xfarray_foliosort()
597 sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL); in xfarray_foliosort()
600 xfile_put_folio(si->array->xfile, folio); in xfarray_foliosort()
610 /* Return a pointer to the start of the pivot array. */
615 return xfarray_sortinfo_pivot(si) + si->array->obj_size; in xfarray_sortinfo_pivot_array()
618 /* The xfarray record is stored at the start of each pivot array element. */
628 /* The xfarray index is stored at the end of each pivot array element. */
646 * quicksort behavior, since our array values are nearly always evenly sorted.
659 size_t pivot_rec_sz = xfarray_pivot_rec_sz(si->array); in xfarray_qsort_pivot()
667 * pivot array. in xfarray_qsort_pivot()
679 /* Load the selected xfarray records into the pivot array. */ in xfarray_qsort_pivot()
686 /* No unset records; load directly into the array. */ in xfarray_qsort_pivot()
687 if (likely(si->array->unset_slots == 0)) { in xfarray_qsort_pivot()
696 * the xfarray_idx_t in the pivot array. in xfarray_qsort_pivot()
700 error = xfarray_load_next(si->array, &idx, recp); in xfarray_qsort_pivot()
709 * We sorted the pivot array records (which includes the xfarray in xfarray_qsort_pivot()
711 * array contains the xfarray record that we will use as the pivot. in xfarray_qsort_pivot()
716 memcpy(pivot, recp, si->array->obj_size); in xfarray_qsort_pivot()
725 * Find the cached copy of a[lo] in the pivot array so that we can swap in xfarray_qsort_pivot()
794 xfile_put_folio(si->array->xfile, si->folio); in xfarray_sort_scan_done()
799 * Cache the folio backing the start of the given array element. If the array
810 loff_t idx_pos = xfarray_pos(si->array, idx); in xfarray_sort_scan()
823 /* Grab the first folio that backs this array element. */ 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()
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()
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()
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()
861 /* Otherwise return a pointer to the array element in the folio. */ in xfarray_sort_scan()
867 * Sort the array elements via quicksort. This implementation incorporates
870 * 1. Use an explicit stack of array indices to store the next array partition
905 struct xfarray *array, in xfarray_sort() argument
912 void *scratch = xfarray_scratch(array); in xfarray_sort()
916 if (array->nr < 2) in xfarray_sort()
918 if (array->nr >= QSORT_MAX_RECS) in xfarray_sort()
921 error = xfarray_sortinfo_alloc(array, cmp_fn, flags, &si); in xfarray_sort()
990 memcpy(scratch, p, si->array->obj_size); in xfarray_sort()
1016 memcpy(scratch, p, si->array->obj_size); in xfarray_sort()
1058 /* How many bytes is this array consuming? */
1061 struct xfarray *array) in xfarray_bytes() argument
1063 return xfile_bytes(array->xfile); in xfarray_bytes()
1066 /* Empty the entire array. */
1069 struct xfarray *array) in xfarray_truncate() argument
1071 xfile_discard(array->xfile, 0, MAX_LFS_FILESIZE); in xfarray_truncate()
1072 array->nr = 0; in xfarray_truncate()