]>
Commit | Line | Data |
---|---|---|
f8d5d0cc MW |
1 | // SPDX-License-Identifier: GPL-2.0+ |
2 | /* | |
3 | * XArray implementation | |
4 | * Copyright (c) 2017 Microsoft Corporation | |
5 | * Author: Matthew Wilcox <willy@infradead.org> | |
6 | */ | |
7 | ||
9b89a035 | 8 | #include <linux/bitmap.h> |
f8d5d0cc MW |
9 | #include <linux/export.h> |
10 | #include <linux/xarray.h> | |
11 | ||
12 | /* | |
13 | * Coding conventions in this file: | |
14 | * | |
15 | * @xa is used to refer to the entire xarray. | |
16 | * @xas is the 'xarray operation state'. It may be either a pointer to | |
17 | * an xa_state, or an xa_state stored on the stack. This is an unfortunate | |
18 | * ambiguity. | |
19 | * @index is the index of the entry being operated on | |
20 | * @mark is an xa_mark_t; a small number indicating one of the mark bits. | |
21 | * @node refers to an xa_node; usually the primary one being operated on by | |
22 | * this function. | |
23 | * @offset is the index into the slots array inside an xa_node. | |
24 | * @parent refers to the @xa_node closer to the head than @node. | |
25 | * @entry refers to something stored in a slot in the xarray | |
26 | */ | |
27 | ||
9b89a035 MW |
28 | static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark) |
29 | { | |
30 | if (!(xa->xa_flags & XA_FLAGS_MARK(mark))) | |
31 | xa->xa_flags |= XA_FLAGS_MARK(mark); | |
32 | } | |
33 | ||
34 | static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark) | |
35 | { | |
36 | if (xa->xa_flags & XA_FLAGS_MARK(mark)) | |
37 | xa->xa_flags &= ~(XA_FLAGS_MARK(mark)); | |
38 | } | |
39 | ||
40 | static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark) | |
41 | { | |
42 | return node->marks[(__force unsigned)mark]; | |
43 | } | |
44 | ||
45 | static inline bool node_get_mark(struct xa_node *node, | |
46 | unsigned int offset, xa_mark_t mark) | |
47 | { | |
48 | return test_bit(offset, node_marks(node, mark)); | |
49 | } | |
50 | ||
51 | /* returns true if the bit was set */ | |
52 | static inline bool node_set_mark(struct xa_node *node, unsigned int offset, | |
53 | xa_mark_t mark) | |
54 | { | |
55 | return __test_and_set_bit(offset, node_marks(node, mark)); | |
56 | } | |
57 | ||
58 | /* returns true if the bit was set */ | |
59 | static inline bool node_clear_mark(struct xa_node *node, unsigned int offset, | |
60 | xa_mark_t mark) | |
61 | { | |
62 | return __test_and_clear_bit(offset, node_marks(node, mark)); | |
63 | } | |
64 | ||
65 | static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark) | |
66 | { | |
67 | return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE); | |
68 | } | |
69 | ||
ad3d6c72 MW |
70 | /* extracts the offset within this node from the index */ |
71 | static unsigned int get_offset(unsigned long index, struct xa_node *node) | |
72 | { | |
73 | return (index >> node->shift) & XA_CHUNK_MASK; | |
74 | } | |
75 | ||
76 | /* move the index either forwards (find) or backwards (sibling slot) */ | |
77 | static void xas_move_index(struct xa_state *xas, unsigned long offset) | |
78 | { | |
79 | unsigned int shift = xas->xa_node->shift; | |
80 | xas->xa_index &= ~XA_CHUNK_MASK << shift; | |
81 | xas->xa_index += offset << shift; | |
82 | } | |
83 | ||
84 | static void *set_bounds(struct xa_state *xas) | |
85 | { | |
86 | xas->xa_node = XAS_BOUNDS; | |
87 | return NULL; | |
88 | } | |
89 | ||
90 | /* | |
91 | * Starts a walk. If the @xas is already valid, we assume that it's on | |
92 | * the right path and just return where we've got to. If we're in an | |
93 | * error state, return NULL. If the index is outside the current scope | |
94 | * of the xarray, return NULL without changing @xas->xa_node. Otherwise | |
95 | * set @xas->xa_node to NULL and return the current head of the array. | |
96 | */ | |
97 | static void *xas_start(struct xa_state *xas) | |
98 | { | |
99 | void *entry; | |
100 | ||
101 | if (xas_valid(xas)) | |
102 | return xas_reload(xas); | |
103 | if (xas_error(xas)) | |
104 | return NULL; | |
105 | ||
106 | entry = xa_head(xas->xa); | |
107 | if (!xa_is_node(entry)) { | |
108 | if (xas->xa_index) | |
109 | return set_bounds(xas); | |
110 | } else { | |
111 | if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK) | |
112 | return set_bounds(xas); | |
113 | } | |
114 | ||
115 | xas->xa_node = NULL; | |
116 | return entry; | |
117 | } | |
118 | ||
119 | static void *xas_descend(struct xa_state *xas, struct xa_node *node) | |
120 | { | |
121 | unsigned int offset = get_offset(xas->xa_index, node); | |
122 | void *entry = xa_entry(xas->xa, node, offset); | |
123 | ||
124 | xas->xa_node = node; | |
125 | if (xa_is_sibling(entry)) { | |
126 | offset = xa_to_sibling(entry); | |
127 | entry = xa_entry(xas->xa, node, offset); | |
128 | } | |
129 | ||
130 | xas->xa_offset = offset; | |
131 | return entry; | |
132 | } | |
133 | ||
134 | /** | |
135 | * xas_load() - Load an entry from the XArray (advanced). | |
136 | * @xas: XArray operation state. | |
137 | * | |
138 | * Usually walks the @xas to the appropriate state to load the entry | |
139 | * stored at xa_index. However, it will do nothing and return %NULL if | |
140 | * @xas is in an error state. xas_load() will never expand the tree. | |
141 | * | |
142 | * If the xa_state is set up to operate on a multi-index entry, xas_load() | |
143 | * may return %NULL or an internal entry, even if there are entries | |
144 | * present within the range specified by @xas. | |
145 | * | |
146 | * Context: Any context. The caller should hold the xa_lock or the RCU lock. | |
147 | * Return: Usually an entry in the XArray, but see description for exceptions. | |
148 | */ | |
149 | void *xas_load(struct xa_state *xas) | |
150 | { | |
151 | void *entry = xas_start(xas); | |
152 | ||
153 | while (xa_is_node(entry)) { | |
154 | struct xa_node *node = xa_to_node(entry); | |
155 | ||
156 | if (xas->xa_shift > node->shift) | |
157 | break; | |
158 | entry = xas_descend(xas, node); | |
159 | } | |
160 | return entry; | |
161 | } | |
162 | EXPORT_SYMBOL_GPL(xas_load); | |
163 | ||
9b89a035 MW |
164 | /** |
165 | * xas_get_mark() - Returns the state of this mark. | |
166 | * @xas: XArray operation state. | |
167 | * @mark: Mark number. | |
168 | * | |
169 | * Return: true if the mark is set, false if the mark is clear or @xas | |
170 | * is in an error state. | |
171 | */ | |
172 | bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark) | |
173 | { | |
174 | if (xas_invalid(xas)) | |
175 | return false; | |
176 | if (!xas->xa_node) | |
177 | return xa_marked(xas->xa, mark); | |
178 | return node_get_mark(xas->xa_node, xas->xa_offset, mark); | |
179 | } | |
180 | EXPORT_SYMBOL_GPL(xas_get_mark); | |
181 | ||
182 | /** | |
183 | * xas_set_mark() - Sets the mark on this entry and its parents. | |
184 | * @xas: XArray operation state. | |
185 | * @mark: Mark number. | |
186 | * | |
187 | * Sets the specified mark on this entry, and walks up the tree setting it | |
188 | * on all the ancestor entries. Does nothing if @xas has not been walked to | |
189 | * an entry, or is in an error state. | |
190 | */ | |
191 | void xas_set_mark(const struct xa_state *xas, xa_mark_t mark) | |
192 | { | |
193 | struct xa_node *node = xas->xa_node; | |
194 | unsigned int offset = xas->xa_offset; | |
195 | ||
196 | if (xas_invalid(xas)) | |
197 | return; | |
198 | ||
199 | while (node) { | |
200 | if (node_set_mark(node, offset, mark)) | |
201 | return; | |
202 | offset = node->offset; | |
203 | node = xa_parent_locked(xas->xa, node); | |
204 | } | |
205 | ||
206 | if (!xa_marked(xas->xa, mark)) | |
207 | xa_mark_set(xas->xa, mark); | |
208 | } | |
209 | EXPORT_SYMBOL_GPL(xas_set_mark); | |
210 | ||
211 | /** | |
212 | * xas_clear_mark() - Clears the mark on this entry and its parents. | |
213 | * @xas: XArray operation state. | |
214 | * @mark: Mark number. | |
215 | * | |
216 | * Clears the specified mark on this entry, and walks back to the head | |
217 | * attempting to clear it on all the ancestor entries. Does nothing if | |
218 | * @xas has not been walked to an entry, or is in an error state. | |
219 | */ | |
220 | void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark) | |
221 | { | |
222 | struct xa_node *node = xas->xa_node; | |
223 | unsigned int offset = xas->xa_offset; | |
224 | ||
225 | if (xas_invalid(xas)) | |
226 | return; | |
227 | ||
228 | while (node) { | |
229 | if (!node_clear_mark(node, offset, mark)) | |
230 | return; | |
231 | if (node_any_mark(node, mark)) | |
232 | return; | |
233 | ||
234 | offset = node->offset; | |
235 | node = xa_parent_locked(xas->xa, node); | |
236 | } | |
237 | ||
238 | if (xa_marked(xas->xa, mark)) | |
239 | xa_mark_clear(xas->xa, mark); | |
240 | } | |
241 | EXPORT_SYMBOL_GPL(xas_clear_mark); | |
242 | ||
f8d5d0cc MW |
243 | /** |
244 | * xa_init_flags() - Initialise an empty XArray with flags. | |
245 | * @xa: XArray. | |
246 | * @flags: XA_FLAG values. | |
247 | * | |
248 | * If you need to initialise an XArray with special flags (eg you need | |
249 | * to take the lock from interrupt context), use this function instead | |
250 | * of xa_init(). | |
251 | * | |
252 | * Context: Any context. | |
253 | */ | |
254 | void xa_init_flags(struct xarray *xa, gfp_t flags) | |
255 | { | |
256 | spin_lock_init(&xa->xa_lock); | |
257 | xa->xa_flags = flags; | |
258 | xa->xa_head = NULL; | |
259 | } | |
260 | EXPORT_SYMBOL(xa_init_flags); | |
ad3d6c72 MW |
261 | |
262 | /** | |
263 | * xa_load() - Load an entry from an XArray. | |
264 | * @xa: XArray. | |
265 | * @index: index into array. | |
266 | * | |
267 | * Context: Any context. Takes and releases the RCU lock. | |
268 | * Return: The entry at @index in @xa. | |
269 | */ | |
270 | void *xa_load(struct xarray *xa, unsigned long index) | |
271 | { | |
272 | XA_STATE(xas, xa, index); | |
273 | void *entry; | |
274 | ||
275 | rcu_read_lock(); | |
276 | do { | |
277 | entry = xas_load(&xas); | |
278 | } while (xas_retry(&xas, entry)); | |
279 | rcu_read_unlock(); | |
280 | ||
281 | return entry; | |
282 | } | |
283 | EXPORT_SYMBOL(xa_load); | |
284 | ||
9b89a035 MW |
285 | /** |
286 | * __xa_set_mark() - Set this mark on this entry while locked. | |
287 | * @xa: XArray. | |
288 | * @index: Index of entry. | |
289 | * @mark: Mark number. | |
290 | * | |
291 | * Attempting to set a mark on a NULL entry does not succeed. | |
292 | * | |
293 | * Context: Any context. Expects xa_lock to be held on entry. | |
294 | */ | |
295 | void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) | |
296 | { | |
297 | XA_STATE(xas, xa, index); | |
298 | void *entry = xas_load(&xas); | |
299 | ||
300 | if (entry) | |
301 | xas_set_mark(&xas, mark); | |
302 | } | |
303 | EXPORT_SYMBOL_GPL(__xa_set_mark); | |
304 | ||
305 | /** | |
306 | * __xa_clear_mark() - Clear this mark on this entry while locked. | |
307 | * @xa: XArray. | |
308 | * @index: Index of entry. | |
309 | * @mark: Mark number. | |
310 | * | |
311 | * Context: Any context. Expects xa_lock to be held on entry. | |
312 | */ | |
313 | void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) | |
314 | { | |
315 | XA_STATE(xas, xa, index); | |
316 | void *entry = xas_load(&xas); | |
317 | ||
318 | if (entry) | |
319 | xas_clear_mark(&xas, mark); | |
320 | } | |
321 | EXPORT_SYMBOL_GPL(__xa_clear_mark); | |
322 | ||
323 | /** | |
324 | * xa_get_mark() - Inquire whether this mark is set on this entry. | |
325 | * @xa: XArray. | |
326 | * @index: Index of entry. | |
327 | * @mark: Mark number. | |
328 | * | |
329 | * This function uses the RCU read lock, so the result may be out of date | |
330 | * by the time it returns. If you need the result to be stable, use a lock. | |
331 | * | |
332 | * Context: Any context. Takes and releases the RCU lock. | |
333 | * Return: True if the entry at @index has this mark set, false if it doesn't. | |
334 | */ | |
335 | bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) | |
336 | { | |
337 | XA_STATE(xas, xa, index); | |
338 | void *entry; | |
339 | ||
340 | rcu_read_lock(); | |
341 | entry = xas_start(&xas); | |
342 | while (xas_get_mark(&xas, mark)) { | |
343 | if (!xa_is_node(entry)) | |
344 | goto found; | |
345 | entry = xas_descend(&xas, xa_to_node(entry)); | |
346 | } | |
347 | rcu_read_unlock(); | |
348 | return false; | |
349 | found: | |
350 | rcu_read_unlock(); | |
351 | return true; | |
352 | } | |
353 | EXPORT_SYMBOL(xa_get_mark); | |
354 | ||
355 | /** | |
356 | * xa_set_mark() - Set this mark on this entry. | |
357 | * @xa: XArray. | |
358 | * @index: Index of entry. | |
359 | * @mark: Mark number. | |
360 | * | |
361 | * Attempting to set a mark on a NULL entry does not succeed. | |
362 | * | |
363 | * Context: Process context. Takes and releases the xa_lock. | |
364 | */ | |
365 | void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) | |
366 | { | |
367 | xa_lock(xa); | |
368 | __xa_set_mark(xa, index, mark); | |
369 | xa_unlock(xa); | |
370 | } | |
371 | EXPORT_SYMBOL(xa_set_mark); | |
372 | ||
373 | /** | |
374 | * xa_clear_mark() - Clear this mark on this entry. | |
375 | * @xa: XArray. | |
376 | * @index: Index of entry. | |
377 | * @mark: Mark number. | |
378 | * | |
379 | * Clearing a mark always succeeds. | |
380 | * | |
381 | * Context: Process context. Takes and releases the xa_lock. | |
382 | */ | |
383 | void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) | |
384 | { | |
385 | xa_lock(xa); | |
386 | __xa_clear_mark(xa, index, mark); | |
387 | xa_unlock(xa); | |
388 | } | |
389 | EXPORT_SYMBOL(xa_clear_mark); | |
390 | ||
ad3d6c72 MW |
391 | #ifdef XA_DEBUG |
392 | void xa_dump_node(const struct xa_node *node) | |
393 | { | |
394 | unsigned i, j; | |
395 | ||
396 | if (!node) | |
397 | return; | |
398 | if ((unsigned long)node & 3) { | |
399 | pr_cont("node %px\n", node); | |
400 | return; | |
401 | } | |
402 | ||
403 | pr_cont("node %px %s %d parent %px shift %d count %d values %d " | |
404 | "array %px list %px %px marks", | |
405 | node, node->parent ? "offset" : "max", node->offset, | |
406 | node->parent, node->shift, node->count, node->nr_values, | |
407 | node->array, node->private_list.prev, node->private_list.next); | |
408 | for (i = 0; i < XA_MAX_MARKS; i++) | |
409 | for (j = 0; j < XA_MARK_LONGS; j++) | |
410 | pr_cont(" %lx", node->marks[i][j]); | |
411 | pr_cont("\n"); | |
412 | } | |
413 | ||
414 | void xa_dump_index(unsigned long index, unsigned int shift) | |
415 | { | |
416 | if (!shift) | |
417 | pr_info("%lu: ", index); | |
418 | else if (shift >= BITS_PER_LONG) | |
419 | pr_info("0-%lu: ", ~0UL); | |
420 | else | |
421 | pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1)); | |
422 | } | |
423 | ||
424 | void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift) | |
425 | { | |
426 | if (!entry) | |
427 | return; | |
428 | ||
429 | xa_dump_index(index, shift); | |
430 | ||
431 | if (xa_is_node(entry)) { | |
432 | if (shift == 0) { | |
433 | pr_cont("%px\n", entry); | |
434 | } else { | |
435 | unsigned long i; | |
436 | struct xa_node *node = xa_to_node(entry); | |
437 | xa_dump_node(node); | |
438 | for (i = 0; i < XA_CHUNK_SIZE; i++) | |
439 | xa_dump_entry(node->slots[i], | |
440 | index + (i << node->shift), node->shift); | |
441 | } | |
442 | } else if (xa_is_value(entry)) | |
443 | pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry), | |
444 | xa_to_value(entry), entry); | |
445 | else if (!xa_is_internal(entry)) | |
446 | pr_cont("%px\n", entry); | |
447 | else if (xa_is_retry(entry)) | |
448 | pr_cont("retry (%ld)\n", xa_to_internal(entry)); | |
449 | else if (xa_is_sibling(entry)) | |
450 | pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry)); | |
451 | else | |
452 | pr_cont("UNKNOWN ENTRY (%px)\n", entry); | |
453 | } | |
454 | ||
455 | void xa_dump(const struct xarray *xa) | |
456 | { | |
457 | void *entry = xa->xa_head; | |
458 | unsigned int shift = 0; | |
459 | ||
460 | pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry, | |
9b89a035 MW |
461 | xa->xa_flags, xa_marked(xa, XA_MARK_0), |
462 | xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2)); | |
ad3d6c72 MW |
463 | if (xa_is_node(entry)) |
464 | shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT; | |
465 | xa_dump_entry(entry, 0, shift); | |
466 | } | |
467 | #endif |