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