lib/generic-radix-tree.c

   1
   2 #include <linux/export.h>
   3 #include <linux/generic-radix-tree.h>
   4 #include <linux/gfp.h>
   5 #include <linux/kmemleak.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 static inline unsigned genradix_root_to_depth(struct genradix_root *r)
  41 {
  42         return (unsigned long) r & GENRADIX_DEPTH_MASK;
  43 }
  44
  45 static inline 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 static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask)
  80 {
  81         struct genradix_node *node;
  82
  83         node = (struct genradix_node *)__get_free_page(gfp_mask|__GFP_ZERO);
  84
  85         /*
  86          * We're using pages (not slab allocations) directly for kernel data
  87          * structures, so we need to explicitly inform kmemleak of them in order
  88          * to avoid false positive memory leak reports.
  89          */
  90         kmemleak_alloc(node, PAGE_SIZE, 1, gfp_mask);
  91         return node;
  92 }
  93
  94 static inline void genradix_free_node(struct genradix_node *node)
  95 {
  96         kmemleak_free(node);
  97         free_page((unsigned long)node);
  98 }
  99
 100 /*
 101  * Returns pointer to the specified byte @offset within @radix, allocating it if
 102  * necessary - newly allocated slots are always zeroed out:
 103  */
 104 void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
 105                            gfp_t gfp_mask)
 106 {
 107         struct genradix_root *v = READ_ONCE(radix->root);
 108         struct genradix_node *n, *new_node = NULL;
 109         unsigned level;
 110
 111         /* Increase tree depth if necessary: */
 112         while (1) {
 113                 struct genradix_root *r = v, *new_root;
 114
 115                 n       = genradix_root_to_node(r);
 116                 level   = genradix_root_to_depth(r);
 117
 118                 if (n && ilog2(offset) < genradix_depth_shift(level))
 119                         break;
 120
 121                 if (!new_node) {
 122                         new_node = genradix_alloc_node(gfp_mask);
 123                         if (!new_node)
 124                                 return NULL;
 125                 }
 126
 127                 new_node->children[0] = n;
 128                 new_root = ((struct genradix_root *)
 129                             ((unsigned long) new_node | (n ? level + 1 : 0)));
 130
 131                 if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
 132                         v = new_root;
 133                         new_node = NULL;
 134                 }
 135         }
 136
 137         while (level--) {
 138                 struct genradix_node **p =
 139                         &n->children[offset >> genradix_depth_shift(level)];
 140                 offset &= genradix_depth_size(level) - 1;
 141
 142                 n = READ_ONCE(*p);
 143                 if (!n) {
 144                         if (!new_node) {
 145                                 new_node = genradix_alloc_node(gfp_mask);
 146                                 if (!new_node)
 147                                         return NULL;
 148                         }
 149
 150                         if (!(n = cmpxchg_release(p, NULL, new_node)))
 151                                 swap(n, new_node);
 152                 }
 153         }
 154
 155         if (new_node)
 156                 genradix_free_node(new_node);
 157
 158         return &n->data[offset];
 159 }
 160 EXPORT_SYMBOL(__genradix_ptr_alloc);
 161
 162 void *__genradix_iter_peek(struct genradix_iter *iter,
 163                            struct __genradix *radix,
 164                            size_t objs_per_page)
 165 {
 166         struct genradix_root *r;
 167         struct genradix_node *n;
 168         unsigned level, i;
 169
 170         if (iter->offset == SIZE_MAX)
 171                 return NULL;
 172
 173 restart:
 174         r = READ_ONCE(radix->root);
 175         if (!r)
 176                 return NULL;
 177
 178         n       = genradix_root_to_node(r);
 179         level   = genradix_root_to_depth(r);
 180
 181         if (ilog2(iter->offset) >= genradix_depth_shift(level))
 182                 return NULL;
 183
 184         while (level) {
 185                 level--;
 186
 187                 i = (iter->offset >> genradix_depth_shift(level)) &
 188                         (GENRADIX_ARY - 1);
 189
 190                 while (!n->children[i]) {
 191                         size_t objs_per_ptr = genradix_depth_size(level);
 192
 193                         if (iter->offset + objs_per_ptr < iter->offset) {
 194                                 iter->offset    = SIZE_MAX;
 195                                 iter->pos       = SIZE_MAX;
 196                                 return NULL;
 197                         }
 198
 199                         i++;
 200                         iter->offset = round_down(iter->offset + objs_per_ptr,
 201                                                   objs_per_ptr);
 202                         iter->pos = (iter->offset >> PAGE_SHIFT) *
 203                                 objs_per_page;
 204                         if (i == GENRADIX_ARY)
 205                                 goto restart;
 206                 }
 207
 208                 n = n->children[i];
 209         }
 210
 211         return &n->data[iter->offset & (PAGE_SIZE - 1)];
 212 }
 213 EXPORT_SYMBOL(__genradix_iter_peek);
 214
 215 static void genradix_free_recurse(struct genradix_node *n, unsigned level)
 216 {
 217         if (level) {
 218                 unsigned i;
 219
 220                 for (i = 0; i < GENRADIX_ARY; i++)
 221                         if (n->children[i])
 222                                 genradix_free_recurse(n->children[i], level - 1);
 223         }
 224
 225         genradix_free_node(n);
 226 }
 227
 228 int __genradix_prealloc(struct __genradix *radix, size_t size,
 229                         gfp_t gfp_mask)
 230 {
 231         size_t offset;
 232
 233         for (offset = 0; offset < size; offset += PAGE_SIZE)
 234                 if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
 235                         return -ENOMEM;
 236
 237         return 0;
 238 }
 239 EXPORT_SYMBOL(__genradix_prealloc);
 240
 241 void __genradix_free(struct __genradix *radix)
 242 {
 243         struct genradix_root *r = xchg(&radix->root, NULL);
 244
 245         genradix_free_recurse(genradix_root_to_node(r),
 246                               genradix_root_to_depth(r));
 247 }
 248 EXPORT_SYMBOL(__genradix_free);