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 #define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *)) 9 #define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY) 10 11 struct genradix_node { 12 union { 13 /* Interior node: */ 14 struct genradix_node *children[GENRADIX_ARY]; 15 16 /* Leaf: */ 17 u8 data[PAGE_SIZE]; 18 }; 19 }; 20 21 static inline int genradix_depth_shift(unsigned depth) 22 { 23 return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth; 24 } 25 26 /* 27 * Returns size (of data, in bytes) that a tree of a given depth holds: 28 */ 29 static inline size_t genradix_depth_size(unsigned depth) 30 { 31 return 1UL << genradix_depth_shift(depth); 32 } 33 34 /* depth that's needed for a genradix that can address up to ULONG_MAX: */ 35 #define GENRADIX_MAX_DEPTH \ 36 DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT) 37 38 #define GENRADIX_DEPTH_MASK \ 39 ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1)) 40 41 static inline unsigned genradix_root_to_depth(struct genradix_root *r) 42 { 43 return (unsigned long) r & GENRADIX_DEPTH_MASK; 44 } 45 46 static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r) 47 { 48 return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK); 49 } 50 51 /* 52 * Returns pointer to the specified byte @offset within @radix, or NULL if not 53 * allocated 54 */ 55 void *__genradix_ptr(struct __genradix *radix, size_t offset) 56 { 57 struct genradix_root *r = READ_ONCE(radix->root); 58 struct genradix_node *n = genradix_root_to_node(r); 59 unsigned level = genradix_root_to_depth(r); 60 61 if (ilog2(offset) >= genradix_depth_shift(level)) 62 return NULL; 63 64 while (1) { 65 if (!n) 66 return NULL; 67 if (!level) 68 break; 69 70 level--; 71 72 n = n->children[offset >> genradix_depth_shift(level)]; 73 offset &= genradix_depth_size(level) - 1; 74 } 75 76 return &n->data[offset]; 77 } 78 EXPORT_SYMBOL(__genradix_ptr); 79 80 static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask) 81 { 82 struct genradix_node *node; 83 84 node = (struct genradix_node *)__get_free_page(gfp_mask|__GFP_ZERO); 85 86 /* 87 * We're using pages (not slab allocations) directly for kernel data 88 * structures, so we need to explicitly inform kmemleak of them in order 89 * to avoid false positive memory leak reports. 90 */ 91 kmemleak_alloc(node, PAGE_SIZE, 1, gfp_mask); 92 return node; 93 } 94 95 static inline void genradix_free_node(struct genradix_node *node) 96 { 97 kmemleak_free(node); 98 free_page((unsigned long)node); 99 } 100 101 /* 102 * Returns pointer to the specified byte @offset within @radix, allocating it if 103 * necessary - newly allocated slots are always zeroed out: 104 */ 105 void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, 106 gfp_t gfp_mask) 107 { 108 struct genradix_root *v = READ_ONCE(radix->root); 109 struct genradix_node *n, *new_node = NULL; 110 unsigned level; 111 112 /* Increase tree depth if necessary: */ 113 while (1) { 114 struct genradix_root *r = v, *new_root; 115 116 n = genradix_root_to_node(r); 117 level = genradix_root_to_depth(r); 118 119 if (n && ilog2(offset) < genradix_depth_shift(level)) 120 break; 121 122 if (!new_node) { 123 new_node = genradix_alloc_node(gfp_mask); 124 if (!new_node) 125 return NULL; 126 } 127 128 new_node->children[0] = n; 129 new_root = ((struct genradix_root *) 130 ((unsigned long) new_node | (n ? level + 1 : 0))); 131 132 if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) { 133 v = new_root; 134 new_node = NULL; 135 } 136 } 137 138 while (level--) { 139 struct genradix_node **p = 140 &n->children[offset >> genradix_depth_shift(level)]; 141 offset &= genradix_depth_size(level) - 1; 142 143 n = READ_ONCE(*p); 144 if (!n) { 145 if (!new_node) { 146 new_node = genradix_alloc_node(gfp_mask); 147 if (!new_node) 148 return NULL; 149 } 150 151 if (!(n = cmpxchg_release(p, NULL, new_node))) 152 swap(n, new_node); 153 } 154 } 155 156 if (new_node) 157 genradix_free_node(new_node); 158 159 return &n->data[offset]; 160 } 161 EXPORT_SYMBOL(__genradix_ptr_alloc); 162 163 void *__genradix_iter_peek(struct genradix_iter *iter, 164 struct __genradix *radix, 165 size_t objs_per_page) 166 { 167 struct genradix_root *r; 168 struct genradix_node *n; 169 unsigned level, i; 170 171 if (iter->offset == SIZE_MAX) 172 return NULL; 173 174 restart: 175 r = READ_ONCE(radix->root); 176 if (!r) 177 return NULL; 178 179 n = genradix_root_to_node(r); 180 level = genradix_root_to_depth(r); 181 182 if (ilog2(iter->offset) >= genradix_depth_shift(level)) 183 return NULL; 184 185 while (level) { 186 level--; 187 188 i = (iter->offset >> genradix_depth_shift(level)) & 189 (GENRADIX_ARY - 1); 190 191 while (!n->children[i]) { 192 size_t objs_per_ptr = genradix_depth_size(level); 193 194 if (iter->offset + objs_per_ptr < iter->offset) { 195 iter->offset = SIZE_MAX; 196 iter->pos = SIZE_MAX; 197 return NULL; 198 } 199 200 i++; 201 iter->offset = round_down(iter->offset + objs_per_ptr, 202 objs_per_ptr); 203 iter->pos = (iter->offset >> PAGE_SHIFT) * 204 objs_per_page; 205 if (i == GENRADIX_ARY) 206 goto restart; 207 } 208 209 n = n->children[i]; 210 } 211 212 return &n->data[iter->offset & (PAGE_SIZE - 1)]; 213 } 214 EXPORT_SYMBOL(__genradix_iter_peek); 215 216 void *__genradix_iter_peek_prev(struct genradix_iter *iter, 217 struct __genradix *radix, 218 size_t objs_per_page, 219 size_t obj_size_plus_page_remainder) 220 { 221 struct genradix_root *r; 222 struct genradix_node *n; 223 unsigned level, i; 224 225 if (iter->offset == SIZE_MAX) 226 return NULL; 227 228 restart: 229 r = READ_ONCE(radix->root); 230 if (!r) 231 return NULL; 232 233 n = genradix_root_to_node(r); 234 level = genradix_root_to_depth(r); 235 236 if (ilog2(iter->offset) >= genradix_depth_shift(level)) { 237 iter->offset = genradix_depth_size(level); 238 iter->pos = (iter->offset >> PAGE_SHIFT) * objs_per_page; 239 240 iter->offset -= obj_size_plus_page_remainder; 241 iter->pos--; 242 } 243 244 while (level) { 245 level--; 246 247 i = (iter->offset >> genradix_depth_shift(level)) & 248 (GENRADIX_ARY - 1); 249 250 while (!n->children[i]) { 251 size_t objs_per_ptr = genradix_depth_size(level); 252 253 iter->offset = round_down(iter->offset, objs_per_ptr); 254 iter->pos = (iter->offset >> PAGE_SHIFT) * objs_per_page; 255 256 if (!iter->offset) 257 return NULL; 258 259 iter->offset -= obj_size_plus_page_remainder; 260 iter->pos--; 261 262 if (!i) 263 goto restart; 264 --i; 265 } 266 267 n = n->children[i]; 268 } 269 270 return &n->data[iter->offset & (PAGE_SIZE - 1)]; 271 } 272 EXPORT_SYMBOL(__genradix_iter_peek_prev); 273 274 static void genradix_free_recurse(struct genradix_node *n, unsigned level) 275 { 276 if (level) { 277 unsigned i; 278 279 for (i = 0; i < GENRADIX_ARY; i++) 280 if (n->children[i]) 281 genradix_free_recurse(n->children[i], level - 1); 282 } 283 284 genradix_free_node(n); 285 } 286 287 int __genradix_prealloc(struct __genradix *radix, size_t size, 288 gfp_t gfp_mask) 289 { 290 size_t offset; 291 292 for (offset = 0; offset < size; offset += PAGE_SIZE) 293 if (!__genradix_ptr_alloc(radix, offset, gfp_mask)) 294 return -ENOMEM; 295 296 return 0; 297 } 298 EXPORT_SYMBOL(__genradix_prealloc); 299 300 void __genradix_free(struct __genradix *radix) 301 { 302 struct genradix_root *r = xchg(&radix->root, NULL); 303 304 genradix_free_recurse(genradix_root_to_node(r), 305 genradix_root_to_depth(r)); 306 } 307 EXPORT_SYMBOL(__genradix_free); 308