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 unsigned genradix_root_to_depth(struct genradix_root *r) 40 { 41 return (unsigned long) r & GENRADIX_DEPTH_MASK; 42 } 43 44 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); 218