git.sesse.net Git - bcachefs-tools-debian/blob - linux/generic-radix-tree.c

   1
   2 #include <linux/atomic.h>
   3 #include <linux/export.h>
   4 #include <linux/generic-radix-tree.h>
   5 #include <linux/gfp.h>
   6
   7 #define GENRADIX_ARY            (PAGE_SIZE / sizeof(struct genradix_node *))
   8 #define GENRADIX_ARY_SHIFT      ilog2(GENRADIX_ARY)
   9
  10 struct genradix_node {
  11         union {
  12                 /* Interior node: */
  13                 struct genradix_node    *children[GENRADIX_ARY];
  14
  15                 /* Leaf: */
  16                 u8                      data[PAGE_SIZE];
  17         };
  18 };
  19
  20 static inline int genradix_depth_shift(unsigned depth)
  21 {
  22         return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
  23 }
  24
  25 /*
  26  * Returns size (of data, in bytes) that a tree of a given depth holds:
  27  */
  28 static inline size_t genradix_depth_size(unsigned depth)
  29 {
  30         return 1UL << genradix_depth_shift(depth);
  31 }
  32
  33 /* depth that's needed for a genradix that can address up to ULONG_MAX: */
  34 #define GENRADIX_MAX_DEPTH      \
  35         DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
  36
  37 #define GENRADIX_DEPTH_MASK                             \
  38         ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
  39
  40 unsigned genradix_root_to_depth(struct genradix_root *r)
  41 {
  42         return (unsigned long) r & GENRADIX_DEPTH_MASK;
  43 }
  44
  45 struct genradix_node *genradix_root_to_node(struct genradix_root *r)
  46 {
  47         return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
  48 }
  49
  50 /*
  51  * Returns pointer to the specified byte @offset within @radix, or NULL if not
  52  * allocated
  53  */
  54 void *__genradix_ptr(struct __genradix *radix, size_t offset)
  55 {
  56         struct genradix_root *r = READ_ONCE(radix->root);
  57         struct genradix_node *n = genradix_root_to_node(r);
  58         unsigned level          = genradix_root_to_depth(r);
  59
  60         if (ilog2(offset) >= genradix_depth_shift(level))
  61                 return NULL;
  62
  63         while (1) {
  64                 if (!n)
  65                         return NULL;
  66                 if (!level)
  67                         break;
  68
  69                 level--;
  70
  71                 n = n->children[offset >> genradix_depth_shift(level)];
  72                 offset &= genradix_depth_size(level) - 1;
  73         }
  74
  75         return &n->data[offset];
  76 }
  77 EXPORT_SYMBOL(__genradix_ptr);
  78
  79 /*
  80  * Returns pointer to the specified byte @offset within @radix, allocating it if
  81  * necessary - newly allocated slots are always zeroed out:
  82  */
  83 void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
  84                            gfp_t gfp_mask)
  85 {
  86         struct genradix_root *v = READ_ONCE(radix->root);
  87         struct genradix_node *n, *new_node = NULL;
  88         unsigned level;
  89
  90         /* Increase tree depth if necessary: */
  91         while (1) {
  92                 struct genradix_root *r = v, *new_root;
  93
  94                 n       = genradix_root_to_node(r);
  95                 level   = genradix_root_to_depth(r);
  96
  97                 if (n && ilog2(offset) < genradix_depth_shift(level))
  98                         break;
  99
 100                 if (!new_node) {
 101                         new_node = (void *)
 102                                 __get_free_page(gfp_mask|__GFP_ZERO);
 103                         if (!new_node)
 104                                 return NULL;
 105                 }
 106
 107                 new_node->children[0] = n;
 108                 new_root = ((struct genradix_root *)
 109                             ((unsigned long) new_node | (n ? level + 1 : 0)));
 110
 111                 if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
 112                         v = new_root;
 113                         new_node = NULL;
 114                 }
 115         }
 116
 117         while (level--) {
 118                 struct genradix_node **p =
 119                         &n->children[offset >> genradix_depth_shift(level)];
 120                 offset &= genradix_depth_size(level) - 1;
 121
 122                 n = READ_ONCE(*p);
 123                 if (!n) {
 124                         if (!new_node) {
 125                                 new_node = (void *)
 126                                         __get_free_page(gfp_mask|__GFP_ZERO);
 127                                 if (!new_node)
 128                                         return NULL;
 129                         }
 130
 131                         if (!(n = cmpxchg_release(p, NULL, new_node)))
 132                                 swap(n, new_node);
 133                 }
 134         }
 135
 136         if (new_node)
 137                 free_page((unsigned long) new_node);
 138
 139         return &n->data[offset];
 140 }
 141 EXPORT_SYMBOL(__genradix_ptr_alloc);
 142
 143 void *__genradix_iter_peek(struct genradix_iter *iter,
 144                            struct __genradix *radix,
 145                            size_t objs_per_page)
 146 {
 147         struct genradix_root *r;
 148         struct genradix_node *n;
 149         unsigned level, i;
 150 restart:
 151         r = READ_ONCE(radix->root);
 152         if (!r)
 153                 return NULL;
 154
 155         n       = genradix_root_to_node(r);
 156         level   = genradix_root_to_depth(r);
 157
 158         if (ilog2(iter->offset) >= genradix_depth_shift(level))
 159                 return NULL;
 160
 161         while (level) {
 162                 level--;
 163
 164                 i = (iter->offset >> genradix_depth_shift(level)) &
 165                         (GENRADIX_ARY - 1);
 166
 167                 while (!n->children[i]) {
 168                         i++;
 169                         iter->offset = round_down(iter->offset +
 170                                            genradix_depth_size(level),
 171                                            genradix_depth_size(level));
 172                         iter->pos = (iter->offset >> PAGE_SHIFT) *
 173                                 objs_per_page;
 174                         if (i == GENRADIX_ARY)
 175                                 goto restart;
 176                 }
 177
 178                 n = n->children[i];
 179         }
 180
 181         return &n->data[iter->offset & (PAGE_SIZE - 1)];
 182 }
 183 EXPORT_SYMBOL(__genradix_iter_peek);
 184
 185 static void genradix_free_recurse(struct genradix_node *n, unsigned level)
 186 {
 187         if (level) {
 188                 unsigned i;
 189
 190                 for (i = 0; i < GENRADIX_ARY; i++)
 191                         if (n->children[i])
 192                                 genradix_free_recurse(n->children[i], level - 1);
 193         }
 194
 195         free_page((unsigned long) n);
 196 }
 197
 198 int __genradix_prealloc(struct __genradix *radix, size_t size,
 199                         gfp_t gfp_mask)
 200 {
 201         size_t offset;
 202
 203         for (offset = 0; offset < size; offset += PAGE_SIZE)
 204                 if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
 205                         return -ENOMEM;
 206
 207         return 0;
 208 }
 209 EXPORT_SYMBOL(__genradix_prealloc);
 210
 211 void __genradix_free(struct __genradix *radix)
 212 {
 213         struct genradix_root *r = xchg(&radix->root, NULL);
 214
 215         genradix_free_recurse(genradix_root_to_node(r),
 216                               genradix_root_to_depth(r));
 217 }
 218 EXPORT_SYMBOL(__genradix_free);