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
 151         if (iter->offset == SIZE_MAX)
 152                 return NULL;
 153
 154 restart:
 155         r = READ_ONCE(radix->root);
 156         if (!r)
 157                 return NULL;
 158
 159         n       = genradix_root_to_node(r);
 160         level   = genradix_root_to_depth(r);
 161
 162         if (ilog2(iter->offset) >= genradix_depth_shift(level))
 163                 return NULL;
 164
 165         while (level) {
 166                 level--;
 167
 168                 i = (iter->offset >> genradix_depth_shift(level)) &
 169                         (GENRADIX_ARY - 1);
 170
 171                 while (!n->children[i]) {
 172                         size_t objs_per_ptr = genradix_depth_size(level);
 173
 174                         if (iter->offset + objs_per_ptr < iter->offset) {
 175                                 iter->offset    = SIZE_MAX;
 176                                 iter->pos       = SIZE_MAX;
 177                                 return NULL;
 178                         }
 179
 180                         i++;
 181                         iter->offset = round_down(iter->offset + objs_per_ptr,
 182                                                   objs_per_ptr);
 183                         iter->pos = (iter->offset >> PAGE_SHIFT) *
 184                                 objs_per_page;
 185                         if (i == GENRADIX_ARY)
 186                                 goto restart;
 187                 }
 188
 189                 n = n->children[i];
 190         }
 191
 192         return &n->data[iter->offset & (PAGE_SIZE - 1)];
 193 }
 194 EXPORT_SYMBOL(__genradix_iter_peek);
 195
 196 static void genradix_free_recurse(struct genradix_node *n, unsigned level)
 197 {
 198         if (level) {
 199                 unsigned i;
 200
 201                 for (i = 0; i < GENRADIX_ARY; i++)
 202                         if (n->children[i])
 203                                 genradix_free_recurse(n->children[i], level - 1);
 204         }
 205
 206         free_page((unsigned long) n);
 207 }
 208
 209 int __genradix_prealloc(struct __genradix *radix, size_t size,
 210                         gfp_t gfp_mask)
 211 {
 212         size_t offset;
 213
 214         for (offset = 0; offset < size; offset += PAGE_SIZE)
 215                 if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
 216                         return -ENOMEM;
 217
 218         return 0;
 219 }
 220 EXPORT_SYMBOL(__genradix_prealloc);
 221
 222 void __genradix_free(struct __genradix *radix)
 223 {
 224         struct genradix_root *r = xchg(&radix->root, NULL);
 225
 226         genradix_free_recurse(genradix_root_to_node(r),
 227                               genradix_root_to_depth(r));
 228 }
 229 EXPORT_SYMBOL(__genradix_free);