Branch data Line data Source code
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 : 0 : static inline int genradix_depth_shift(unsigned depth)
21 : : {
22 : 0 : 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 : 0 : static inline size_t genradix_depth_size(unsigned depth)
29 : : {
30 : 0 : 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 : 0 : static inline unsigned genradix_root_to_depth(struct genradix_root *r)
41 : : {
42 : 0 : return (unsigned long) r & GENRADIX_DEPTH_MASK;
43 : : }
44 : :
45 : 0 : static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r)
46 : : {
47 : 0 : 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 : 0 : void *__genradix_ptr(struct __genradix *radix, size_t offset)
55 : : {
56 [ # # ]: 0 : struct genradix_root *r = READ_ONCE(radix->root);
57 : 0 : struct genradix_node *n = genradix_root_to_node(r);
58 : 0 : unsigned level = genradix_root_to_depth(r);
59 : :
60 [ # # # # : 0 : if (ilog2(offset) >= genradix_depth_shift(level))
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
61 : : return NULL;
62 : :
63 : 0 : while (1) {
64 [ # # ]: 0 : if (!n)
65 : : return NULL;
66 [ # # ]: 0 : if (!level)
67 : : break;
68 : :
69 : 0 : level--;
70 : :
71 : 0 : n = n->children[offset >> genradix_depth_shift(level)];
72 : 0 : offset &= genradix_depth_size(level) - 1;
73 : : }
74 : :
75 : 0 : return &n->data[offset];
76 : : }
77 : : EXPORT_SYMBOL(__genradix_ptr);
78 : :
79 : 0 : static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask)
80 : : {
81 : 0 : struct genradix_node *node;
82 : :
83 : 0 : 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 [ # # # # ]: 0 : kmemleak_alloc(node, PAGE_SIZE, 1, gfp_mask);
91 : 0 : return node;
92 : : }
93 : :
94 : 0 : static inline void genradix_free_node(struct genradix_node *node)
95 : : {
96 : 0 : kmemleak_free(node);
97 : 0 : free_page((unsigned long)node);
98 : 0 : }
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 : 0 : void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
105 : : gfp_t gfp_mask)
106 : : {
107 : 0 : struct genradix_root *v = READ_ONCE(radix->root);
108 : 0 : struct genradix_node *n, *new_node = NULL;
109 : 0 : unsigned level;
110 : :
111 : : /* Increase tree depth if necessary: */
112 : 0 : while (1) {
113 : 0 : struct genradix_root *r = v, *new_root;
114 : :
115 : 0 : n = genradix_root_to_node(r);
116 : 0 : level = genradix_root_to_depth(r);
117 : :
118 [ # # # # : 0 : if (n && ilog2(offset) < genradix_depth_shift(level))
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
119 : : break;
120 : :
121 [ # # ]: 0 : if (!new_node) {
122 : 0 : new_node = genradix_alloc_node(gfp_mask);
123 [ # # ]: 0 : if (!new_node)
124 : : return NULL;
125 : : }
126 : :
127 : 0 : new_node->children[0] = n;
128 : 0 : new_root = ((struct genradix_root *)
129 [ # # ]: 0 : ((unsigned long) new_node | (n ? level + 1 : 0)));
130 : :
131 [ # # ]: 0 : if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
132 : 0 : v = new_root;
133 : 0 : new_node = NULL;
134 : : }
135 : : }
136 : :
137 : 0 : while (level--) {
138 : 0 : struct genradix_node **p =
139 : 0 : &n->children[offset >> genradix_depth_shift(level)];
140 : 0 : offset &= genradix_depth_size(level) - 1;
141 : :
142 [ # # ]: 0 : n = READ_ONCE(*p);
143 [ # # ]: 0 : if (!n) {
144 [ # # ]: 0 : if (!new_node) {
145 : 0 : new_node = genradix_alloc_node(gfp_mask);
146 [ # # ]: 0 : if (!new_node)
147 : : return NULL;
148 : : }
149 : :
150 [ # # ]: 0 : if (!(n = cmpxchg_release(p, NULL, new_node)))
151 [ # # ]: 0 : swap(n, new_node);
152 : : }
153 : : }
154 : :
155 [ # # ]: 0 : if (new_node)
156 : 0 : genradix_free_node(new_node);
157 : :
158 : 0 : return &n->data[offset];
159 : : }
160 : : EXPORT_SYMBOL(__genradix_ptr_alloc);
161 : :
162 : 0 : void *__genradix_iter_peek(struct genradix_iter *iter,
163 : : struct __genradix *radix,
164 : : size_t objs_per_page)
165 : : {
166 : 0 : struct genradix_root *r;
167 : 0 : struct genradix_node *n;
168 : 0 : unsigned level, i;
169 : 0 : restart:
170 [ # # ]: 0 : r = READ_ONCE(radix->root);
171 [ # # ]: 0 : if (!r)
172 : : return NULL;
173 : :
174 : 0 : n = genradix_root_to_node(r);
175 : 0 : level = genradix_root_to_depth(r);
176 : :
177 [ # # # # : 0 : if (ilog2(iter->offset) >= genradix_depth_shift(level))
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
178 : : return NULL;
179 : :
180 [ # # ]: 0 : while (level) {
181 : 0 : level--;
182 : :
183 : 0 : i = (iter->offset >> genradix_depth_shift(level)) &
184 : : (GENRADIX_ARY - 1);
185 : :
186 [ # # ]: 0 : while (!n->children[i]) {
187 : 0 : i++;
188 : 0 : iter->offset = round_down(iter->offset +
189 : : genradix_depth_size(level),
190 : : genradix_depth_size(level));
191 : 0 : iter->pos = (iter->offset >> PAGE_SHIFT) *
192 : : objs_per_page;
193 [ # # ]: 0 : if (i == GENRADIX_ARY)
194 : 0 : goto restart;
195 : : }
196 : :
197 : : n = n->children[i];
198 : : }
199 : :
200 : 0 : return &n->data[iter->offset & (PAGE_SIZE - 1)];
201 : : }
202 : : EXPORT_SYMBOL(__genradix_iter_peek);
203 : :
204 : 0 : static void genradix_free_recurse(struct genradix_node *n, unsigned level)
205 : : {
206 [ # # ]: 0 : if (level) {
207 : : unsigned i;
208 : :
209 [ # # ]: 0 : for (i = 0; i < GENRADIX_ARY; i++)
210 [ # # ]: 0 : if (n->children[i])
211 : 0 : genradix_free_recurse(n->children[i], level - 1);
212 : : }
213 : :
214 : 0 : genradix_free_node(n);
215 : 0 : }
216 : :
217 : 0 : int __genradix_prealloc(struct __genradix *radix, size_t size,
218 : : gfp_t gfp_mask)
219 : : {
220 : 0 : size_t offset;
221 : :
222 [ # # ]: 0 : for (offset = 0; offset < size; offset += PAGE_SIZE)
223 [ # # ]: 0 : if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
224 : : return -ENOMEM;
225 : :
226 : : return 0;
227 : : }
228 : : EXPORT_SYMBOL(__genradix_prealloc);
229 : :
230 : 0 : void __genradix_free(struct __genradix *radix)
231 : : {
232 : 0 : struct genradix_root *r = xchg(&radix->root, NULL);
233 : :
234 : 0 : genradix_free_recurse(genradix_root_to_node(r),
235 : : genradix_root_to_depth(r));
236 : 0 : }
237 : : EXPORT_SYMBOL(__genradix_free);
|
