git.sesse.net Git - bcachefs-tools-debian/blob - linux/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 unsigned 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 /*
  33  * Returns pointer to the specified byte @offset within @radix, or NULL if not
  34  * allocated
  35  */
  36 void *__genradix_ptr(struct __genradix *radix, size_t offset)
  37 {
  38         size_t level = radix->depth;
  39         struct genradix_node *n = radix->root;
  40
  41         if (offset >= genradix_depth_size(radix->depth))
  42                 return NULL;
  43
  44         while (1) {
  45                 if (!n)
  46                         return NULL;
  47                 if (!level)
  48                         break;
  49
  50                 level--;
  51
  52                 n = n->children[offset >> genradix_depth_shift(level)];
  53                 offset &= genradix_depth_size(level) - 1;
  54         }
  55
  56         return &n->data[offset];
  57 }
  58 EXPORT_SYMBOL(__genradix_ptr);
  59
  60 /*
  61  * Returns pointer to the specified byte @offset within @radix, allocating it if
  62  * necessary - newly allocated slots are always zeroed out:
  63  */
  64 void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
  65                            gfp_t gfp_mask)
  66 {
  67         struct genradix_node **n;
  68         size_t level;
  69
  70         /* Increase tree depth if necessary: */
  71
  72         while (offset >= genradix_depth_size(radix->depth)) {
  73                 struct genradix_node *new_root =
  74                         (void *) __get_free_page(gfp_mask|__GFP_ZERO);
  75
  76                 if (!new_root)
  77                         return NULL;
  78
  79                 new_root->children[0] = radix->root;
  80                 radix->root = new_root;
  81                 radix->depth++;
  82         }
  83
  84         n = &radix->root;
  85         level = radix->depth;
  86
  87         while (1) {
  88                 if (!*n) {
  89                         *n = (void *) __get_free_page(gfp_mask|__GFP_ZERO);
  90                         if (!*n)
  91                                 return NULL;
  92                 }
  93
  94                 if (!level)
  95                         break;
  96
  97                 level--;
  98
  99                 n = &(*n)->children[offset >> genradix_depth_shift(level)];
 100                 offset &= genradix_depth_size(level) - 1;
 101         }
 102
 103         return &(*n)->data[offset];
 104 }
 105 EXPORT_SYMBOL(__genradix_ptr_alloc);
 106
 107 void *__genradix_iter_peek(struct genradix_iter *iter,
 108                            struct __genradix *radix,
 109                            size_t objs_per_page)
 110 {
 111         struct genradix_node *n;
 112         size_t level, i;
 113
 114         if (!radix->root)
 115                 return NULL;
 116 restart:
 117         if (iter->offset >= genradix_depth_size(radix->depth))
 118                 return NULL;
 119
 120         n       = radix->root;
 121         level   = radix->depth;
 122
 123         while (level) {
 124                 level--;
 125
 126                 i = (iter->offset >> genradix_depth_shift(level)) &
 127                         (GENRADIX_ARY - 1);
 128
 129                 while (!n->children[i]) {
 130                         i++;
 131                         iter->offset = round_down(iter->offset +
 132                                            genradix_depth_size(level),
 133                                            genradix_depth_size(level));
 134                         iter->pos = (iter->offset >> PAGE_SHIFT) *
 135                                 objs_per_page;
 136                         if (i == GENRADIX_ARY)
 137                                 goto restart;
 138                 }
 139
 140                 n = n->children[i];
 141         }
 142
 143         return &n->data[iter->offset & (PAGE_SIZE - 1)];
 144 }
 145 EXPORT_SYMBOL(__genradix_iter_peek);
 146
 147 static void genradix_free_recurse(struct genradix_node *n, unsigned level)
 148 {
 149         if (level) {
 150                 unsigned i;
 151
 152                 for (i = 0; i < GENRADIX_ARY; i++)
 153                         if (n->children[i])
 154                                 genradix_free_recurse(n->children[i], level - 1);
 155         }
 156
 157         free_page((unsigned long) n);
 158 }
 159
 160 void __genradix_free(struct __genradix *radix)
 161 {
 162         genradix_free_recurse(radix->root, radix->depth);
 163
 164         radix->root = NULL;
 165         radix->depth = 0;
 166 }
 167 EXPORT_SYMBOL(__genradix_free);