231 lines · c
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 not10 * allocated11 */12void *__genradix_ptr(struct __genradix *radix, size_t offset)13{14 return __genradix_ptr_inlined(radix, offset);15}16EXPORT_SYMBOL(__genradix_ptr);17 18/*19 * Returns pointer to the specified byte @offset within @radix, allocating it if20 * necessary - newly allocated slots are always zeroed out:21 */22void *__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}84EXPORT_SYMBOL(__genradix_ptr_alloc);85 86void *__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 97restart: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}137EXPORT_SYMBOL(__genradix_iter_peek);138 139void *__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 151restart: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}195EXPORT_SYMBOL(__genradix_iter_peek_prev);196 197static 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 210int __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}221EXPORT_SYMBOL(__genradix_prealloc);222 223void __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}230EXPORT_SYMBOL(__genradix_free);231