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