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