lib/generic-radix-tree.c

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