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