// SPDX-License-Identifier: GPL-2.0-or-later /* * Copyright ( C ) 2021 - 2023 Oracle . All Rights Reserved . * Author : Darrick J . Wong < djwong @ kernel . org > #include "xfs.h" #include "xfs_fs.h" #include "xfs_shared.h" #include "xfs_format.h" #include "scrub/scrub.h" #include "scrub/xfile.h" #include "scrub/xfarray.h" #include "scrub/trace.h" /* * Large Arrays of Fixed - Size Records * = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = * * This memory array uses an xfile ( which itself is a shmem file ) to store * large numbers of fixed - size records in memory that can be paged out . This * puts less stress on the memory reclaim algorithms during an online repair * because we don ' t have to pin so much memory . However , array access is less * direct than would be in a regular memory array . Access to the array is * performed via indexed load and store methods , and an append method is * provided for convenience . Array elements can be unset , which sets them to * all zeroes . Unset entries are skipped during iteration , though direct loads * will return a zeroed buffer . Callers are responsible for concurrency * control . /* * Pointer to scratch space . Because we can ' t access the xfile data directly , * we allocate a small amount of memory on the end of the xfarray structure to * buffer array items when we need space to store values temporarily . static inline void *xfarray_scratch(struct xfarray *array)return (array + 1 );/* Compute array index given an xfile offset. */ static xfarray_idx_tstruct xfarray *array,if (array->obj_size_log >= 0 )return (xfarray_idx_t)pos >> array->obj_size_log;return div_u64((xfarray_idx_t)pos, array->obj_size);/* Compute xfile offset of array element. */ static inline loff_t xfarray_pos(struct xfarray *array, xfarray_idx_t idx)if (array->obj_size_log >= 0 )return idx << array->obj_size_log;return idx * array->obj_size;/* * Initialize a big memory array . Array records cannot be larger than a * page , and the array cannot span more bytes than the page cache supports . * If @ required_capacity is nonzero , the maximum array size will be set to this * quantity and the array creation will fail if the underlying storage cannot * support that many records . int const char *description,unsigned long long required_capacity,struct xfarray **arrayp)struct xfarray *array;struct xfile *xfile;int error;0 , &xfile);if (error)return error;sizeof (struct xfarray) + obj_size, XCHK_GFP_FLAGS);if (!array)goto out_xfile;if (is_power_of_2(obj_size))else 1 ;if (required_capacity > 0 ) {if (array->max_nr < required_capacity) {goto out_xfarray;return 0 ;return error;/* Destroy the array. */ void struct xfarray *array)/* Load an element from the array. */ int struct xfarray *array,void *ptr)if (idx >= array->nr)return -ENODATA;return xfile_load(array->xfile, ptr, array->obj_size,/* Is this array element potentially unset? */ static inline bool struct xfarray *array,void *temp = xfarray_scratch(array);int error;if (array->unset_slots == 0 )return false ;if (!error && xfarray_element_is_null(array, temp))return true ;return false ;/* * Unset an array element . If @ idx is the last element in the array , the * array will be truncated . Otherwise , the entry will be zeroed . int struct xfarray *array,void *temp = xfarray_scratch(array);int error;if (idx >= array->nr)return -ENODATA;if (idx == array->nr - 1 ) {return 0 ;if (xfarray_is_unset(array, pos))return 0 ;0 , array->obj_size);if (error)return error;return 0 ;/* * Store an element in the array . The element must not be completely zeroed , * because those are considered unset sparse elements . int struct xfarray *array,const void *ptr)int ret;if (idx >= array->max_nr)return -EFBIG;if (ret)return ret;1 );return 0 ;/* Is this array element NULL? */ bool struct xfarray *array,const void *ptr)return !memchr_inv(ptr, 0 , array->obj_size);/* * Store an element anywhere in the array that is unset . If there are no * unset slots , append the element to the array . int struct xfarray *array,const void *ptr)void *temp = xfarray_scratch(array);int error;/* Find an unset slot to put it in. */ for (pos = 0 ;0 ;if (error || !xfarray_element_is_null(array, temp))continue ;if (error)return error;return 0 ;/* No unset slots found; attach it on the end. */ 0 ;return xfarray_append(array, ptr);/* Return length of array. */ struct xfarray *array)return array->nr;/* * Decide which array item we ' re going to read as part of an _ iter_get . * @ cur is the array index , and @ pos is the file offset of that array index in * the backing xfile . Returns ENODATA if we reach the end of the records . * * Reading from a hole in a sparse xfile causes page instantiation , so for * iterating a ( possibly sparse ) array we need to figure out if the cursor is * pointing at a totally uninitialized hole and move the cursor up if * necessary . static inline int struct xfarray *array,unsigned int pgoff = offset_in_page(*pos);1 ;/* * If the current array record is not adjacent to a page boundary , we * are in the middle of the page . We do not need to move the cursor . if (pgoff != 0 && pgoff + array->obj_size - 1 < PAGE_SIZE)return 0 ;/* * Call SEEK_DATA on the last byte in the record we ' re about to read . * If the record ends at ( or crosses ) the end of a page then we know * that the first byte of the record is backed by pages and don ' t need * to query it . If instead the record begins at the start of the page * then we know that querying the last byte is just as good as querying * the first byte , since records cannot be larger than a page . * * If the call returns the same file offset , we know this record is * backed by real pages . We do not need to move the cursor . if (new_pos == -ENXIO)return -ENODATA;if (new_pos < 0 )return new_pos;if (new_pos == end_pos)return 0 ;/* * Otherwise , SEEK_DATA told us how far up to move the file pointer to * find more data . Move the array index to the first record past the * byte offset we were given . return 0 ;/* * Starting at * idx , fetch the next non - null array entry and advance the index * to set up the next _ load_next call . Returns ENODATA if we reach the end of * the array . Callers must set @ * idx to XFARRAY_CURSOR_INIT before the first * call to this function . int struct xfarray *array,void *rec)int error;do {if (cur >= array->nr)return -ENODATA;/* * Ask the backing store for the location of next possible * written record , then retrieve that record . if (error)return error;if (error)return error;while (xfarray_element_is_null(array, rec));return 0 ;/* Sorting functions */ #ifdef DEBUG# define xfarray_sort_bump_loads(si) do { (si)->loads++; } while (0 )# define xfarray_sort_bump_stores(si) do { (si)->stores++; } while (0 )# define xfarray_sort_bump_compares(si) do { (si)->compares++; } while (0 )# define xfarray_sort_bump_heapsorts(si) do { (si)->heapsorts++; } while (0 )#else # define xfarray_sort_bump_loads(si)# define xfarray_sort_bump_stores(si)# define xfarray_sort_bump_compares(si)# define xfarray_sort_bump_heapsorts(si)#endif /* DEBUG */ /* Load an array element for sorting. */ static inline int struct xfarray_sortinfo *si,void *ptr)return xfarray_load(si->array, idx, ptr);/* Store an array element for sorting. */ static inline int struct xfarray_sortinfo *si,void *ptr)return xfarray_store(si->array, idx, ptr);/* Compare an array element for sorting. */ static inline int struct xfarray_sortinfo *si,const void *a,const void *b)return si->cmp_fn(a, b);/* Return a pointer to the low index stack for quicksort partitioning. */ static inline xfarray_idx_t *xfarray_sortinfo_lo(struct xfarray_sortinfo *si)return (xfarray_idx_t *)(si + 1 );/* Return a pointer to the high index stack for quicksort partitioning. */ static inline xfarray_idx_t *xfarray_sortinfo_hi(struct xfarray_sortinfo *si)return xfarray_sortinfo_lo(si) + si->max_stack_depth;/* Size of each element in the quicksort pivot array. */ static inline size_tstruct xfarray *array)return round_up(array->obj_size, 8 ) + sizeof (xfarray_idx_t);/* Allocate memory to handle the sort. */ static inline int struct xfarray *array,unsigned int flags,struct xfarray_sortinfo **infop)struct xfarray_sortinfo *si;sizeof (struct xfarray_sortinfo);int max_stack_depth;/* * The median - of - nine pivot algorithm doesn ' t work if a subset has * fewer than 9 items . Make sure the in - memory sort will always take * over for subsets where this wouldn ' t be the case . /* * Tail - call recursion during the partitioning phase means that * quicksort will never recurse more than log2 ( nr ) times . We need one * extra level of stack to hold the initial parameters . In - memory * sort will always take care of the last few levels of recursion for * us , so we can reduce the stack depth by that much . 1 - (XFARRAY_ISORT_SHIFT - 1 );if (max_stack_depth < 1 )1 ;/* Each level of quicksort uses a lo and a hi index */ sizeof (xfarray_idx_t) * 2 ;/* Scratchpad for in-memory sort, or finding the pivot */ 1 ) * pivot_rec_sz,if (!si)return -ENOMEM;1 ;0 ] = 0 ;0 ] = array->nr - 1 ;if (flags & XFARRAY_SORT_KILLABLE)false ;return 0 ;/* Should this sort be terminated by a fatal signal? */ static inline bool struct xfarray_sortinfo *si,int *error)/* * If preemption is disabled , we need to yield to the scheduler every * few seconds so that we don ' t run afoul of the soft lockup watchdog * or RCU stall detector . if (xchk_maybe_relax(&si->relax)) {if (*error == 0 )return true ;return false ;/* Do we want an in-memory sort? */ static inline bool struct xfarray_sortinfo *si,/* * For array subsets that fit in the scratchpad , it ' s much faster to * use the kernel ' s heapsort than quicksort ' s stack machine . return (end - start) < XFARRAY_ISORT_NR;/* Return the scratch space within the sortinfo structure. */ static inline void *xfarray_sortinfo_isort_scratch(struct xfarray_sortinfo *si)return xfarray_sortinfo_hi(si) + si->max_stack_depth;/* * Sort a small number of array records using scratchpad memory . The records * need not be contiguous in the xfile ' s memory pages . STATIC int struct xfarray_sortinfo *si,void *scratch = xfarray_sortinfo_isort_scratch(si);1 );int error;if (error)return error;1 , si->array->obj_size, si->cmp_fn, NULL);return xfile_store(si->array->xfile, scratch, len, lo_pos);/* * Sort the records from lo to hi ( inclusive ) if they are all backed by the * same memory folio . Returns 1 if it sorted , 0 if it did not , or a negative * errno . STATIC int struct xfarray_sortinfo *si,struct folio *folio;void *startp;1 );/* No single folio could back this many records. */ if (len > XFILE_MAX_FOLIO_SIZE)return 0 ;if (IS_ERR(folio))return PTR_ERR(folio);if (!folio)return 0 ;1 , si->array->obj_size, si->cmp_fn, NULL);return 1 ;/* Return a pointer to the xfarray pivot record within the sortinfo struct. */ static inline void *xfarray_sortinfo_pivot(struct xfarray_sortinfo *si)return xfarray_sortinfo_hi(si) + si->max_stack_depth;/* Return a pointer to the start of the pivot array. */ static inline void *struct xfarray_sortinfo *si)return xfarray_sortinfo_pivot(si) + si->array->obj_size;/* The xfarray record is stored at the start of each pivot array element. */ static inline void *void *pa,unsigned int pa_idx)return pa + (pa_recsz * pa_idx);/* The xfarray index is stored at the end of each pivot array element. */ static inline xfarray_idx_t *void *pa,unsigned int pa_idx)return xfarray_pivot_array_rec(pa, pa_recsz, pa_idx + 1 ) -sizeof (xfarray_idx_t);/* * Find a pivot value for quicksort partitioning , swap it with a [ lo ] , and save * the cached pivot record for the next step . * * Load evenly - spaced records within the given range into memory , sort them , * and choose the pivot from the median record . Using multiple points will * improve the quality of the pivot selection , and hopefully avoid the worst * quicksort behavior , since our array values are nearly always evenly sorted . STATIC int struct xfarray_sortinfo *si,void *pivot = xfarray_sortinfo_pivot(si);void *parray = xfarray_sortinfo_pivot_array(si);void *recp;1 );int i, j;int error;0 );/* * Load the xfarray indexes of the records we intend to sample into the * pivot array . 0 );for (i = 1 ; i < XFARRAY_QSORT_PIVOT_NR - 1 ; i++) {1 );/* Load the selected xfarray records into the pivot array. */ for (i = 0 ; i < XFARRAY_QSORT_PIVOT_NR; i++) {/* No unset records; load directly into the array. */ if (likely(si->array->unset_slots == 0 )) {if (error)return error;continue ;/* * Load non - null records into the scratchpad without changing * the xfarray_idx_t in the pivot array . if (error)return error;/* * We sorted the pivot array records ( which includes the xfarray * indices ) in xfarray record order . The median element of the pivot * array contains the xfarray record that we will use as the pivot . * Copy that xfarray record to the designated space . 2 );/* If the pivot record we chose was already in a[lo] then we're done. */ 2 );if (*idxp == lo)return 0 ;/* * Find the cached copy of a [ lo ] in the pivot array so that we can swap * a [ lo ] and a [ pivot ] . for (i = 0 , j = -1 ; i < XFARRAY_QSORT_PIVOT_NR; i++) {if (*idxp == lo)if (j < 0 ) {0 );return -EFSCORRUPTED;/* Swap a[lo] and a[pivot]. */ if (error)return error;2 );return xfarray_sort_store(si, *idxp, recp);/* * Set up the pointers for the next iteration . We push onto the stack all of * the unsorted values between a [ lo + 1 ] and a [ end [ i ] ] , and we tweak the * current stack frame to point to the unsorted values between a [ beg [ i ] ] and * a [ lo ] so that those values will be sorted when we pop the stack . static inline int struct xfarray_sortinfo *si,/* Check for stack overflows */ if (si->stack_depth >= si->max_stack_depth - 1 ) {1 );return -EFSCORRUPTED;2 );1 ] = lo + 1 ;1 ] = si_hi[si->stack_depth];1 ;/* * Always start with the smaller of the two partitions to keep the * amount of recursion in check . if (si_hi[si->stack_depth] - si_lo[si->stack_depth] >1 ] - si_lo[si->stack_depth - 1 ]) {1 ]);1 ]);return 0 ;static inline void struct xfarray_sortinfo *si)if (si->folio)/* * Cache the folio backing the start of the given array element . If the array * element is contained entirely within the folio , return a pointer to the * cached folio . Otherwise , load the element into the scratchpad and return a * pointer to the scratchpad . static inline int struct xfarray_sortinfo *si,void **ptrp)int error = 0 ;if (xfarray_sort_terminated(si, &error))return error;/* If the cached folio doesn't cover this index, release it. */ if (si->folio &&/* Grab the first folio that backs this array element. */ if (!si->folio) {struct folio *folio;if (IS_ERR(folio))return PTR_ERR(folio);1 );1 );if (xfarray_pos(si->array, si->last_folio_idx + 1 ) > next_pos)/* * If this folio still doesn ' t cover the desired element , it must cross * a folio boundary . Read into the scratchpad and we ' re done . if (idx < si->first_folio_idx || idx > si->last_folio_idx) {void *temp = xfarray_scratch(si->array);if (error)return error;return 0 ;/* Otherwise return a pointer to the array element in the folio. */ return 0 ;/* * Sort the array elements via quicksort . This implementation incorporates * four optimizations discussed in Sedgewick : * * 1 . Use an explicit stack of array indices to store the next array partition * to sort . This helps us to avoid recursion in the call stack , which is * particularly expensive in the kernel . * * 2 . For arrays with records in arbitrary or user - controlled order , choose the * pivot element using a median - of - nine decision tree . This reduces the * probability of selecting a bad pivot value which causes worst case * behavior ( i . e . partition sizes of 1 ) . * * 3 . The smaller of the two sub - partitions is pushed onto the stack to start * the next level of recursion , and the larger sub - partition replaces the * current stack frame . This guarantees that we won ' t need more than * log2 ( nr ) stack space . * * 4 . For small sets , load the records into the scratchpad and run heapsort on * them because that is very fast . In the author ' s experience , this yields * a ~ 10 % reduction in runtime . * * If a small set is contained entirely within a single xfile memory page , * map the page directly and run heap sort directly on the xfile page * instead of using the load / store interface . This halves the runtime . * * 5 . This optimization is specific to the implementation . When converging lo * and hi after selecting a pivot , we will try to retain the xfile memory * page between load calls , which reduces run time by 50 % . /* * Due to the use of signed indices , we can only support up to 2 ^ 63 records . * Files can only grow to 2 ^ 63 bytes , so this is not much of a limitation . #define QSORT_MAX_RECS (1 ULL << 63 )int struct xfarray *array,unsigned int flags)struct xfarray_sortinfo *si;void *pivot;void *scratch = xfarray_scratch(array);int error = 0 ;if (array->nr < 2 )return 0 ;if (array->nr >= QSORT_MAX_RECS)return -E2BIG;if (error)return error;while (si->stack_depth >= 0 ) {int ret;/* Nothing left in this partition to sort; pop stack. */ if (lo >= hi) {continue ;/* * If directly mapping the folio and sorting can solve our * problems , we ' re done . if (ret < 0 )goto out_free;if (ret == 1 ) {continue ;/* If insertion sort can solve our problems, we're done. */ if (xfarray_want_isort(si, lo, hi)) {if (error)goto out_free;continue ;/* Pick a pivot, move it to a[lo] and stash it. */ if (error)goto out_free;/* * Rearrange a [ lo . . hi ] such that everything smaller than the * pivot is on the left side of the range and everything larger * than the pivot is on the right side of the range . while (lo < hi) {void *p;/* * Decrement hi until it finds an a [ hi ] less than the * pivot value . if (error)goto out_free;while (xfarray_sort_cmp(si, p, pivot) >= 0 && lo < hi) {if (error)goto out_free;if (p != scratch)if (xfarray_sort_terminated(si, &error))goto out_free;/* Copy that item (a[hi]) to a[lo]. */ if (lo < hi) {if (error)goto out_free;/* * Increment lo until it finds an a [ lo ] greater than * the pivot value . if (error)goto out_free;while (xfarray_sort_cmp(si, p, pivot) <= 0 && lo < hi) {if (error)goto out_free;if (p != scratch)if (xfarray_sort_terminated(si, &error))goto out_free;/* Copy that item (a[lo]) to a[hi]. */ if (lo < hi) {if (error)goto out_free;if (xfarray_sort_terminated(si, &error))goto out_free;/* * Put our pivot value in the correct place at a [ lo ] . All * values between a [ beg [ i ] ] and a [ lo - 1 ] should be less than * the pivot ; and all values between a [ lo + 1 ] and a [ end [ i ] - 1 ] * should be greater than the pivot . if (error)goto out_free;/* Set up the stack frame to process the two partitions. */ if (error)goto out_free;if (xfarray_sort_terminated(si, &error))goto out_free;return error;/* How many bytes is this array consuming? */ unsigned long long struct xfarray *array)return xfile_bytes(array->xfile);/* Empty the entire array. */ void struct xfarray *array)0 , MAX_LFS_FILESIZE);0 ;
Messung V0.5 in Prozent C=93 H=82 G=87
¤ Dauer der Verarbeitung: 0.22 Sekunden
(vorverarbeitet am 2026-09-27)
¤ *© Formatika GbR, Deutschland
