Line data    Source code

       1             : /* SPDX-License-Identifier: GPL-2.0-or-later */
       2             : /*
       3             :  * Copyright (C) 2021-2023 Oracle.  All Rights Reserved.
       4             :  * Author: Darrick J. Wong <djwong@kernel.org>
       5             :  */
       6             : #ifndef __XFS_SCRUB_XFARRAY_H__
       7             : #define __XFS_SCRUB_XFARRAY_H__
       8             : 
       9             : /* xfile array index type, along with cursor initialization */
      10             : typedef uint64_t                xfarray_idx_t;
      11             : #define XFARRAY_NULLIDX         ((__force xfarray_idx_t)-1ULL)
      12             : #define XFARRAY_CURSOR_INIT     ((__force xfarray_idx_t)0)
      13             : 
      14             : /* Iterate each index of an xfile array. */
      15             : #define foreach_xfarray_idx(array, idx) \
      16             :         for ((idx) = XFARRAY_CURSOR_INIT; \
      17             :              (idx) < xfarray_length(array); \
      18             :              (idx)++)
      19             : 
      20             : struct xfarray {
      21             :         /* Underlying file that backs the array. */
      22             :         struct xfile    *xfile;
      23             : 
      24             :         /* Number of array elements. */
      25             :         xfarray_idx_t   nr;
      26             : 
      27             :         /* Maximum possible array size. */
      28             :         xfarray_idx_t   max_nr;
      29             : 
      30             :         /* Number of unset slots in the array below @nr. */
      31             :         uint64_t        unset_slots;
      32             : 
      33             :         /* Size of an array element. */
      34             :         size_t          obj_size;
      35             : 
      36             :         /* log2 of array element size, if possible. */
      37             :         int             obj_size_log;
      38             : };
      39             : 
      40             : int xfarray_create(const char *descr, unsigned long long required_capacity,
      41             :                 size_t obj_size, struct xfarray **arrayp);
      42             : void xfarray_destroy(struct xfarray *array);
      43             : int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr);
      44             : int xfarray_unset(struct xfarray *array, xfarray_idx_t idx);
      45             : int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr);
      46             : int xfarray_store_anywhere(struct xfarray *array, const void *ptr);
      47             : bool xfarray_element_is_null(struct xfarray *array, const void *ptr);
      48             : void xfarray_truncate(struct xfarray *array);
      49             : unsigned long long xfarray_bytes(struct xfarray *array);
      50             : 
      51             : /*
      52             :  * Load an array element, but zero the buffer if there's no data because we
      53             :  * haven't stored to that array element yet.
      54             :  */
      55             : static inline int
      56  1650950958 : xfarray_load_sparse(
      57             :         struct xfarray  *array,
      58             :         uint64_t        idx,
      59             :         void            *rec)
      60             : {
      61  1650950958 :         int             error = xfarray_load(array, idx, rec);
      62             : 
      63  1650950958 :         if (error == -ENODATA) {
      64     1034721 :                 memset(rec, 0, array->obj_size);
      65     1034721 :                 return 0;
      66             :         }
      67             :         return error;
      68             : }
      69             : 
      70             : /* Append an element to the array. */
      71             : static inline int xfarray_append(struct xfarray *array, const void *ptr)
      72             : {
      73  1195089743 :         return xfarray_store(array, array->nr, ptr);
      74             : }
      75             : 
      76             : uint64_t xfarray_length(struct xfarray *array);
      77             : int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec);
      78             : 
      79             : /*
      80             :  * Iterate the non-null elements in a sparse xfarray.  Callers should
      81             :  * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it
      82             :  * will be set to one more than the index of the record that was retrieved.
      83             :  * Returns 1 if a record was retrieved, 0 if there weren't any more records, or
      84             :  * a negative errno.
      85             :  */
      86             : static inline int
      87   507290759 : xfarray_iter(
      88             :         struct xfarray  *array,
      89             :         xfarray_idx_t   *idx,
      90             :         void            *rec)
      91             : {
      92   507290759 :         int ret = xfarray_load_next(array, idx, rec);
      93             : 
      94   507290760 :         if (ret == -ENODATA)
      95             :                 return 0;
      96   506908015 :         if (ret == 0)
      97   506908015 :                 return 1;
      98             :         return ret;
      99             : }
     100             : 
     101             : /* Declarations for xfile array sort functionality. */
     102             : 
     103             : typedef cmp_func_t xfarray_cmp_fn;
     104             : 
     105             : /* Perform an in-memory heapsort for small subsets. */
     106             : #define XFARRAY_ISORT_SHIFT             (4)
     107             : #define XFARRAY_ISORT_NR                (1U << XFARRAY_ISORT_SHIFT)
     108             : 
     109             : /* Evalulate this many points to find the qsort pivot. */
     110             : #define XFARRAY_QSORT_PIVOT_NR          (9)
     111             : 
     112             : struct xfarray_sortinfo {
     113             :         struct xfarray          *array;
     114             : 
     115             :         /* Comparison function for the sort. */
     116             :         xfarray_cmp_fn          cmp_fn;
     117             : 
     118             :         /* Maximum height of the partition stack. */
     119             :         uint8_t                 max_stack_depth;
     120             : 
     121             :         /* Current height of the partition stack. */
     122             :         int8_t                  stack_depth;
     123             : 
     124             :         /* Maximum stack depth ever used. */
     125             :         uint8_t                 max_stack_used;
     126             : 
     127             :         /* XFARRAY_SORT_* flags; see below. */
     128             :         unsigned int            flags;
     129             : 
     130             :         /* Cache a page here for faster access. */
     131             :         struct xfile_page       xfpage;
     132             :         void                    *page_kaddr;
     133             : 
     134             : #ifdef DEBUG
     135             :         /* Performance statistics. */
     136             :         uint64_t                loads;
     137             :         uint64_t                stores;
     138             :         uint64_t                compares;
     139             :         uint64_t                heapsorts;
     140             : #endif
     141             :         /*
     142             :          * Extra bytes are allocated beyond the end of the structure to store
     143             :          * quicksort information.  C does not permit multiple VLAs per struct,
     144             :          * so we document all of this in a comment.
     145             :          *
     146             :          * Pretend that we have a typedef for array records:
     147             :          *
     148             :          * typedef char[array->obj_size]     xfarray_rec_t;
     149             :          *
     150             :          * First comes the quicksort partition stack:
     151             :          *
     152             :          * xfarray_idx_t        lo[max_stack_depth];
     153             :          * xfarray_idx_t        hi[max_stack_depth];
     154             :          *
     155             :          * union {
     156             :          *
     157             :          * If for a given subset we decide to use an in-memory sort, we use a
     158             :          * block of scratchpad records here to compare items:
     159             :          *
     160             :          *      xfarray_rec_t   scratch[ISORT_NR];
     161             :          *
     162             :          * Otherwise, we want to partition the records to partition the array.
     163             :          * We store the chosen pivot record at the start of the scratchpad area
     164             :          * and use the rest to sample some records to estimate the median.
     165             :          * The format of the qsort_pivot array enables us to use the kernel
     166             :          * heapsort function to place the median value in the middle.
     167             :          *
     168             :          *      struct {
     169             :          *              xfarray_rec_t   pivot;
     170             :          *              struct {
     171             :          *                      xfarray_rec_t   rec;  (rounded up to 8 bytes)
     172             :          *                      xfarray_idx_t   idx;
     173             :          *              } qsort_pivot[QSORT_PIVOT_NR];
     174             :          *      };
     175             :          * }
     176             :          */
     177             : };
     178             : 
     179             : /* Sort can be interrupted by a fatal signal. */
     180             : #define XFARRAY_SORT_KILLABLE   (1U << 0)
     181             : 
     182             : int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
     183             :                 unsigned int flags);
     184             : 
     185             : #endif /* __XFS_SCRUB_XFARRAY_H__ */