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 | ||
8 | #include <linux/export.h> | |
9 | #include <linux/xarray.h> | |
10 | ||
11 | /* | |
12 | * Coding conventions in this file: | |
13 | * | |
14 | * @xa is used to refer to the entire xarray. | |
15 | * @xas is the 'xarray operation state'. It may be either a pointer to | |
16 | * an xa_state, or an xa_state stored on the stack. This is an unfortunate | |
17 | * ambiguity. | |
18 | * @index is the index of the entry being operated on | |
19 | * @mark is an xa_mark_t; a small number indicating one of the mark bits. | |
20 | * @node refers to an xa_node; usually the primary one being operated on by | |
21 | * this function. | |
22 | * @offset is the index into the slots array inside an xa_node. | |
23 | * @parent refers to the @xa_node closer to the head than @node. | |
24 | * @entry refers to something stored in a slot in the xarray | |
25 | */ | |
26 | ||
ad3d6c72 MW |
27 | /* extracts the offset within this node from the index */ |
28 | static unsigned int get_offset(unsigned long index, struct xa_node *node) | |
29 | { | |
30 | return (index >> node->shift) & XA_CHUNK_MASK; | |
31 | } | |
32 | ||
33 | /* move the index either forwards (find) or backwards (sibling slot) */ | |
34 | static void xas_move_index(struct xa_state *xas, unsigned long offset) | |
35 | { | |
36 | unsigned int shift = xas->xa_node->shift; | |
37 | xas->xa_index &= ~XA_CHUNK_MASK << shift; | |
38 | xas->xa_index += offset << shift; | |
39 | } | |
40 | ||
41 | static void *set_bounds(struct xa_state *xas) | |
42 | { | |
43 | xas->xa_node = XAS_BOUNDS; | |
44 | return NULL; | |
45 | } | |
46 | ||
47 | /* | |
48 | * Starts a walk. If the @xas is already valid, we assume that it's on | |
49 | * the right path and just return where we've got to. If we're in an | |
50 | * error state, return NULL. If the index is outside the current scope | |
51 | * of the xarray, return NULL without changing @xas->xa_node. Otherwise | |
52 | * set @xas->xa_node to NULL and return the current head of the array. | |
53 | */ | |
54 | static void *xas_start(struct xa_state *xas) | |
55 | { | |
56 | void *entry; | |
57 | ||
58 | if (xas_valid(xas)) | |
59 | return xas_reload(xas); | |
60 | if (xas_error(xas)) | |
61 | return NULL; | |
62 | ||
63 | entry = xa_head(xas->xa); | |
64 | if (!xa_is_node(entry)) { | |
65 | if (xas->xa_index) | |
66 | return set_bounds(xas); | |
67 | } else { | |
68 | if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK) | |
69 | return set_bounds(xas); | |
70 | } | |
71 | ||
72 | xas->xa_node = NULL; | |
73 | return entry; | |
74 | } | |
75 | ||
76 | static void *xas_descend(struct xa_state *xas, struct xa_node *node) | |
77 | { | |
78 | unsigned int offset = get_offset(xas->xa_index, node); | |
79 | void *entry = xa_entry(xas->xa, node, offset); | |
80 | ||
81 | xas->xa_node = node; | |
82 | if (xa_is_sibling(entry)) { | |
83 | offset = xa_to_sibling(entry); | |
84 | entry = xa_entry(xas->xa, node, offset); | |
85 | } | |
86 | ||
87 | xas->xa_offset = offset; | |
88 | return entry; | |
89 | } | |
90 | ||
91 | /** | |
92 | * xas_load() - Load an entry from the XArray (advanced). | |
93 | * @xas: XArray operation state. | |
94 | * | |
95 | * Usually walks the @xas to the appropriate state to load the entry | |
96 | * stored at xa_index. However, it will do nothing and return %NULL if | |
97 | * @xas is in an error state. xas_load() will never expand the tree. | |
98 | * | |
99 | * If the xa_state is set up to operate on a multi-index entry, xas_load() | |
100 | * may return %NULL or an internal entry, even if there are entries | |
101 | * present within the range specified by @xas. | |
102 | * | |
103 | * Context: Any context. The caller should hold the xa_lock or the RCU lock. | |
104 | * Return: Usually an entry in the XArray, but see description for exceptions. | |
105 | */ | |
106 | void *xas_load(struct xa_state *xas) | |
107 | { | |
108 | void *entry = xas_start(xas); | |
109 | ||
110 | while (xa_is_node(entry)) { | |
111 | struct xa_node *node = xa_to_node(entry); | |
112 | ||
113 | if (xas->xa_shift > node->shift) | |
114 | break; | |
115 | entry = xas_descend(xas, node); | |
116 | } | |
117 | return entry; | |
118 | } | |
119 | EXPORT_SYMBOL_GPL(xas_load); | |
120 | ||
f8d5d0cc MW |
121 | /** |
122 | * xa_init_flags() - Initialise an empty XArray with flags. | |
123 | * @xa: XArray. | |
124 | * @flags: XA_FLAG values. | |
125 | * | |
126 | * If you need to initialise an XArray with special flags (eg you need | |
127 | * to take the lock from interrupt context), use this function instead | |
128 | * of xa_init(). | |
129 | * | |
130 | * Context: Any context. | |
131 | */ | |
132 | void xa_init_flags(struct xarray *xa, gfp_t flags) | |
133 | { | |
134 | spin_lock_init(&xa->xa_lock); | |
135 | xa->xa_flags = flags; | |
136 | xa->xa_head = NULL; | |
137 | } | |
138 | EXPORT_SYMBOL(xa_init_flags); | |
ad3d6c72 MW |
139 | |
140 | /** | |
141 | * xa_load() - Load an entry from an XArray. | |
142 | * @xa: XArray. | |
143 | * @index: index into array. | |
144 | * | |
145 | * Context: Any context. Takes and releases the RCU lock. | |
146 | * Return: The entry at @index in @xa. | |
147 | */ | |
148 | void *xa_load(struct xarray *xa, unsigned long index) | |
149 | { | |
150 | XA_STATE(xas, xa, index); | |
151 | void *entry; | |
152 | ||
153 | rcu_read_lock(); | |
154 | do { | |
155 | entry = xas_load(&xas); | |
156 | } while (xas_retry(&xas, entry)); | |
157 | rcu_read_unlock(); | |
158 | ||
159 | return entry; | |
160 | } | |
161 | EXPORT_SYMBOL(xa_load); | |
162 | ||
163 | #ifdef XA_DEBUG | |
164 | void xa_dump_node(const struct xa_node *node) | |
165 | { | |
166 | unsigned i, j; | |
167 | ||
168 | if (!node) | |
169 | return; | |
170 | if ((unsigned long)node & 3) { | |
171 | pr_cont("node %px\n", node); | |
172 | return; | |
173 | } | |
174 | ||
175 | pr_cont("node %px %s %d parent %px shift %d count %d values %d " | |
176 | "array %px list %px %px marks", | |
177 | node, node->parent ? "offset" : "max", node->offset, | |
178 | node->parent, node->shift, node->count, node->nr_values, | |
179 | node->array, node->private_list.prev, node->private_list.next); | |
180 | for (i = 0; i < XA_MAX_MARKS; i++) | |
181 | for (j = 0; j < XA_MARK_LONGS; j++) | |
182 | pr_cont(" %lx", node->marks[i][j]); | |
183 | pr_cont("\n"); | |
184 | } | |
185 | ||
186 | void xa_dump_index(unsigned long index, unsigned int shift) | |
187 | { | |
188 | if (!shift) | |
189 | pr_info("%lu: ", index); | |
190 | else if (shift >= BITS_PER_LONG) | |
191 | pr_info("0-%lu: ", ~0UL); | |
192 | else | |
193 | pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1)); | |
194 | } | |
195 | ||
196 | void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift) | |
197 | { | |
198 | if (!entry) | |
199 | return; | |
200 | ||
201 | xa_dump_index(index, shift); | |
202 | ||
203 | if (xa_is_node(entry)) { | |
204 | if (shift == 0) { | |
205 | pr_cont("%px\n", entry); | |
206 | } else { | |
207 | unsigned long i; | |
208 | struct xa_node *node = xa_to_node(entry); | |
209 | xa_dump_node(node); | |
210 | for (i = 0; i < XA_CHUNK_SIZE; i++) | |
211 | xa_dump_entry(node->slots[i], | |
212 | index + (i << node->shift), node->shift); | |
213 | } | |
214 | } else if (xa_is_value(entry)) | |
215 | pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry), | |
216 | xa_to_value(entry), entry); | |
217 | else if (!xa_is_internal(entry)) | |
218 | pr_cont("%px\n", entry); | |
219 | else if (xa_is_retry(entry)) | |
220 | pr_cont("retry (%ld)\n", xa_to_internal(entry)); | |
221 | else if (xa_is_sibling(entry)) | |
222 | pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry)); | |
223 | else | |
224 | pr_cont("UNKNOWN ENTRY (%px)\n", entry); | |
225 | } | |
226 | ||
227 | void xa_dump(const struct xarray *xa) | |
228 | { | |
229 | void *entry = xa->xa_head; | |
230 | unsigned int shift = 0; | |
231 | ||
232 | pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry, | |
233 | xa->xa_flags, radix_tree_tagged(xa, 0), | |
234 | radix_tree_tagged(xa, 1), radix_tree_tagged(xa, 2)); | |
235 | if (xa_is_node(entry)) | |
236 | shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT; | |
237 | xa_dump_entry(entry, 0, shift); | |
238 | } | |
239 | #endif |