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 /* 9 * Returns pointer to the specified byte @offset within @radix, or NULL if not 10 * allocated 11 */ 12 void *__genradix_ptr(struct __genradix *radix, size_t offset) 13 { 14 return __genradix_ptr_inlined(radix, offset); 15 } 16 EXPORT_SYMBOL(__genradix_ptr); 17 18 static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask) 19 { 20 return kzalloc(GENRADIX_NODE_SIZE, gfp_mask); 21 } 22 23 static inline void genradix_free_node(struct genradix_node *node) 24 { 25 kfree(node); 26 } 27 28 /* 29 * Returns pointer to the specified byte @offset within @radix, allocating it if 30 * necessary - newly allocated slots are always zeroed out: 31 */ 32 void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, 33 gfp_t gfp_mask) 34 { 35 struct genradix_root *v = READ_ONCE(radix->root); 36 struct genradix_node *n, *new_node = NULL; 37 unsigned level; 38 39 /* Increase tree depth if necessary: */ 40 while (1) { 41 struct genradix_root *r = v, *new_root; 42 43 n = genradix_root_to_node(r); 44 level = genradix_root_to_depth(r); 45 46 if (n && ilog2(offset) < genradix_depth_shift(level)) 47 break; 48 49 if (!new_node) { 50 new_node = genradix_alloc_node(gfp_mask); 51 if (!new_node) 52 return NULL; 53 } 54 55 new_node->children[0] = n; 56 new_root = ((struct genradix_root *) 57 ((unsigned long) new_node | (n ? level + 1 : 0))); 58 59 if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) { 60 v = new_root; 61 new_node = NULL; 62 } else { 63 new_node->children[0] = NULL; 64 } 65 } 66 67 while (level--) { 68 struct genradix_node **p = 69 &n->children[offset >> genradix_depth_shift(level)]; 70 offset &= genradix_depth_size(level) - 1; 71 72 n = READ_ONCE(*p); 73 if (!n) { 74 if (!new_node) { 75 new_node = genradix_alloc_node(gfp_mask); 76 if (!new_node) 77 return NULL; 78 } 79 80 if (!(n = cmpxchg_release(p, NULL, new_node))) 81 swap(n, new_node); 82 } 83 } 84 85 if (new_node) 86 genradix_free_node(new_node); 87 88 return &n->data[offset]; 89 } 90 EXPORT_SYMBOL(__genradix_ptr_alloc); 91 92 void *__genradix_iter_peek(struct genradix_iter *iter, 93 struct __genradix *radix, 94 size_t objs_per_page) 95 { 96 struct genradix_root *r; 97 struct genradix_node *n; 98 unsigned level, i; 99 100 if (iter->offset == SIZE_MAX) 101 return NULL; 102 103 restart: 104 r = READ_ONCE(radix->root); 105 if (!r) 106 return NULL; 107 108 n = genradix_root_to_node(r); 109 level = genradix_root_to_depth(r); 110 111 if (ilog2(iter->offset) >= genradix_depth_shift(level)) 112 return NULL; 113 114 while (level) { 115 level--; 116 117 i = (iter->offset >> genradix_depth_shift(level)) & 118 (GENRADIX_ARY - 1); 119 120 while (!n->children[i]) { 121 size_t objs_per_ptr = genradix_depth_size(level); 122 123 if (iter->offset + objs_per_ptr < iter->offset) { 124 iter->offset = SIZE_MAX; 125 iter->pos = SIZE_MAX; 126 return NULL; 127 } 128 129 i++; 130 iter->offset = round_down(iter->offset + objs_per_ptr, 131 objs_per_ptr); 132 iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * 133 objs_per_page; 134 if (i == GENRADIX_ARY) 135 goto restart; 136 } 137 138 n = n->children[i]; 139 } 140 141 return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)]; 142 } 143 EXPORT_SYMBOL(__genradix_iter_peek); 144 145 void *__genradix_iter_peek_prev(struct genradix_iter *iter, 146 struct __genradix *radix, 147 size_t objs_per_page, 148 size_t obj_size_plus_page_remainder) 149 { 150 struct genradix_root *r; 151 struct genradix_node *n; 152 unsigned level, i; 153 154 if (iter->offset == SIZE_MAX) 155 return NULL; 156 157 restart: 158 r = READ_ONCE(radix->root); 159 if (!r) 160 return NULL; 161 162 n = genradix_root_to_node(r); 163 level = genradix_root_to_depth(r); 164 165 if (ilog2(iter->offset) >= genradix_depth_shift(level)) { 166 iter->offset = genradix_depth_size(level); 167 iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page; 168 169 iter->offset -= obj_size_plus_page_remainder; 170 iter->pos--; 171 } 172 173 while (level) { 174 level--; 175 176 i = (iter->offset >> genradix_depth_shift(level)) & 177 (GENRADIX_ARY - 1); 178 179 while (!n->children[i]) { 180 size_t objs_per_ptr = genradix_depth_size(level); 181 182 iter->offset = round_down(iter->offset, objs_per_ptr); 183 iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page; 184 185 if (!iter->offset) 186 return NULL; 187 188 iter->offset -= obj_size_plus_page_remainder; 189 iter->pos--; 190 191 if (!i) 192 goto restart; 193 --i; 194 } 195 196 n = n->children[i]; 197 } 198 199 return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)]; 200 } 201 EXPORT_SYMBOL(__genradix_iter_peek_prev); 202 203 static void genradix_free_recurse(struct genradix_node *n, unsigned level) 204 { 205 if (level) { 206 unsigned i; 207 208 for (i = 0; i < GENRADIX_ARY; i++) 209 if (n->children[i]) 210 genradix_free_recurse(n->children[i], level - 1); 211 } 212 213 genradix_free_node(n); 214 } 215 216 int __genradix_prealloc(struct __genradix *radix, size_t size, 217 gfp_t gfp_mask) 218 { 219 size_t offset; 220 221 for (offset = 0; offset < size; offset += GENRADIX_NODE_SIZE) 222 if (!__genradix_ptr_alloc(radix, offset, gfp_mask)) 223 return -ENOMEM; 224 225 return 0; 226 } 227 EXPORT_SYMBOL(__genradix_prealloc); 228 229 void __genradix_free(struct __genradix *radix) 230 { 231 struct genradix_root *r = xchg(&radix->root, NULL); 232 233 genradix_free_recurse(genradix_root_to_node(r), 234 genradix_root_to_depth(r)); 235 } 236 EXPORT_SYMBOL(__genradix_free); 237