]>
Commit | Line | Data |
---|---|---|
ca0bf58d PS |
1 | /* |
2 | * CDDL HEADER START | |
3 | * | |
4 | * This file and its contents are supplied under the terms of the | |
5 | * Common Development and Distribution License ("CDDL"), version 1.0. | |
6 | * You may only use this file in accordance with the terms of version | |
7 | * 1.0 of the CDDL. | |
8 | * | |
9 | * A full copy of the text of the CDDL should have accompanied this | |
10 | * source. A copy of the CDDL is also available via the Internet at | |
11 | * http://www.illumos.org/license/CDDL. | |
12 | * | |
13 | * CDDL HEADER END | |
14 | */ | |
15 | /* | |
16 | * Copyright (c) 2013, 2014 by Delphix. All rights reserved. | |
17 | */ | |
18 | ||
19 | #include <sys/zfs_context.h> | |
20 | #include <sys/multilist.h> | |
21 | #include <sys/trace_multilist.h> | |
22 | ||
23 | /* needed for spa_get_random() */ | |
24 | #include <sys/spa.h> | |
25 | ||
26 | /* | |
27 | * Given the object contained on the list, return a pointer to the | |
28 | * object's multilist_node_t structure it contains. | |
29 | */ | |
30 | #ifdef DEBUG | |
31 | static multilist_node_t * | |
32 | multilist_d2l(multilist_t *ml, void *obj) | |
33 | { | |
34 | return ((multilist_node_t *)((char *)obj + ml->ml_offset)); | |
35 | } | |
36 | #endif | |
37 | ||
38 | /* | |
39 | * Initialize a new mutlilist using the parameters specified. | |
40 | * | |
41 | * - 'size' denotes the size of the structure containing the | |
42 | * multilist_node_t. | |
43 | * - 'offset' denotes the byte offset of the mutlilist_node_t within | |
44 | * the structure that contains it. | |
45 | * - 'num' specifies the number of internal sublists to create. | |
46 | * - 'index_func' is used to determine which sublist to insert into | |
47 | * when the multilist_insert() function is called; as well as which | |
48 | * sublist to remove from when multilist_remove() is called. The | |
49 | * requirements this function must meet, are the following: | |
50 | * | |
51 | * - It must always return the same value when called on the same | |
52 | * object (to ensure the object is removed from the list it was | |
53 | * inserted into). | |
54 | * | |
55 | * - It must return a value in the range [0, number of sublists). | |
56 | * The multilist_get_num_sublists() function may be used to | |
57 | * determine the number of sublists in the multilist. | |
58 | * | |
59 | * Also, in order to reduce internal contention between the sublists | |
60 | * during insertion and removal, this function should choose evenly | |
61 | * between all available sublists when inserting. This isn't a hard | |
62 | * requirement, but a general rule of thumb in order to garner the | |
63 | * best multi-threaded performance out of the data structure. | |
64 | */ | |
65 | void | |
66 | multilist_create(multilist_t *ml, size_t size, size_t offset, unsigned int num, | |
67 | multilist_sublist_index_func_t *index_func) | |
68 | { | |
69 | int i; | |
70 | ||
71 | ASSERT3P(ml, !=, NULL); | |
72 | ASSERT3U(size, >, 0); | |
73 | ASSERT3U(size, >=, offset + sizeof (multilist_node_t)); | |
74 | ASSERT3U(num, >, 0); | |
75 | ASSERT3P(index_func, !=, NULL); | |
76 | ||
77 | ml->ml_offset = offset; | |
78 | ml->ml_num_sublists = num; | |
79 | ml->ml_index_func = index_func; | |
80 | ||
81 | ml->ml_sublists = kmem_zalloc(sizeof (multilist_sublist_t) * | |
82 | ml->ml_num_sublists, KM_SLEEP); | |
83 | ||
84 | ASSERT3P(ml->ml_sublists, !=, NULL); | |
85 | ||
86 | for (i = 0; i < ml->ml_num_sublists; i++) { | |
87 | multilist_sublist_t *mls = &ml->ml_sublists[i]; | |
88 | mutex_init(&mls->mls_lock, NULL, MUTEX_DEFAULT, NULL); | |
89 | list_create(&mls->mls_list, size, offset); | |
90 | } | |
91 | } | |
92 | ||
93 | /* | |
94 | * Destroy the given multilist object, and free up any memory it holds. | |
95 | */ | |
96 | void | |
97 | multilist_destroy(multilist_t *ml) | |
98 | { | |
99 | int i; | |
100 | ||
101 | ASSERT(multilist_is_empty(ml)); | |
102 | ||
103 | for (i = 0; i < ml->ml_num_sublists; i++) { | |
104 | multilist_sublist_t *mls = &ml->ml_sublists[i]; | |
105 | ||
106 | ASSERT(list_is_empty(&mls->mls_list)); | |
107 | ||
108 | list_destroy(&mls->mls_list); | |
109 | mutex_destroy(&mls->mls_lock); | |
110 | } | |
111 | ||
112 | ASSERT3P(ml->ml_sublists, !=, NULL); | |
113 | kmem_free(ml->ml_sublists, | |
114 | sizeof (multilist_sublist_t) * ml->ml_num_sublists); | |
115 | ||
116 | ml->ml_num_sublists = 0; | |
117 | ml->ml_offset = 0; | |
118 | } | |
119 | ||
120 | /* | |
121 | * Insert the given object into the multilist. | |
122 | * | |
123 | * This function will insert the object specified into the sublist | |
124 | * determined using the function given at multilist creation time. | |
125 | * | |
126 | * The sublist locks are automatically acquired if not already held, to | |
127 | * ensure consistency when inserting and removing from multiple threads. | |
128 | */ | |
129 | void | |
130 | multilist_insert(multilist_t *ml, void *obj) | |
131 | { | |
132 | unsigned int sublist_idx = ml->ml_index_func(ml, obj); | |
133 | multilist_sublist_t *mls; | |
134 | boolean_t need_lock; | |
135 | ||
136 | DTRACE_PROBE3(multilist__insert, multilist_t *, ml, | |
137 | unsigned int, sublist_idx, void *, obj); | |
138 | ||
139 | ASSERT3U(sublist_idx, <, ml->ml_num_sublists); | |
140 | ||
141 | mls = &ml->ml_sublists[sublist_idx]; | |
142 | ||
143 | /* | |
144 | * Note: Callers may already hold the sublist lock by calling | |
145 | * multilist_sublist_lock(). Here we rely on MUTEX_HELD() | |
146 | * returning TRUE if and only if the current thread holds the | |
147 | * lock. While it's a little ugly to make the lock recursive in | |
148 | * this way, it works and allows the calling code to be much | |
149 | * simpler -- otherwise it would have to pass around a flag | |
150 | * indicating that it already has the lock. | |
151 | */ | |
152 | need_lock = !MUTEX_HELD(&mls->mls_lock); | |
153 | ||
154 | if (need_lock) | |
155 | mutex_enter(&mls->mls_lock); | |
156 | ||
157 | ASSERT(!multilist_link_active(multilist_d2l(ml, obj))); | |
158 | ||
159 | multilist_sublist_insert_head(mls, obj); | |
160 | ||
161 | if (need_lock) | |
162 | mutex_exit(&mls->mls_lock); | |
163 | } | |
164 | ||
165 | /* | |
166 | * Remove the given object from the multilist. | |
167 | * | |
168 | * This function will remove the object specified from the sublist | |
169 | * determined using the function given at multilist creation time. | |
170 | * | |
171 | * The necessary sublist locks are automatically acquired, to ensure | |
172 | * consistency when inserting and removing from multiple threads. | |
173 | */ | |
174 | void | |
175 | multilist_remove(multilist_t *ml, void *obj) | |
176 | { | |
177 | unsigned int sublist_idx = ml->ml_index_func(ml, obj); | |
178 | multilist_sublist_t *mls; | |
179 | boolean_t need_lock; | |
180 | ||
181 | DTRACE_PROBE3(multilist__remove, multilist_t *, ml, | |
182 | unsigned int, sublist_idx, void *, obj); | |
183 | ||
184 | ASSERT3U(sublist_idx, <, ml->ml_num_sublists); | |
185 | ||
186 | mls = &ml->ml_sublists[sublist_idx]; | |
187 | /* See comment in multilist_insert(). */ | |
188 | need_lock = !MUTEX_HELD(&mls->mls_lock); | |
189 | ||
190 | if (need_lock) | |
191 | mutex_enter(&mls->mls_lock); | |
192 | ||
193 | ASSERT(multilist_link_active(multilist_d2l(ml, obj))); | |
194 | ||
195 | multilist_sublist_remove(mls, obj); | |
196 | ||
197 | if (need_lock) | |
198 | mutex_exit(&mls->mls_lock); | |
199 | } | |
200 | ||
201 | /* | |
202 | * Check to see if this multilist object is empty. | |
203 | * | |
204 | * This will return TRUE if it finds all of the sublists of this | |
205 | * multilist to be empty, and FALSE otherwise. Each sublist lock will be | |
206 | * automatically acquired as necessary. | |
207 | * | |
208 | * If concurrent insertions and removals are occurring, the semantics | |
209 | * of this function become a little fuzzy. Instead of locking all | |
210 | * sublists for the entire call time of the function, each sublist is | |
211 | * only locked as it is individually checked for emptiness. Thus, it's | |
212 | * possible for this function to return TRUE with non-empty sublists at | |
213 | * the time the function returns. This would be due to another thread | |
214 | * inserting into a given sublist, after that specific sublist was check | |
215 | * and deemed empty, but before all sublists have been checked. | |
216 | */ | |
217 | int | |
218 | multilist_is_empty(multilist_t *ml) | |
219 | { | |
220 | int i; | |
221 | ||
222 | for (i = 0; i < ml->ml_num_sublists; i++) { | |
223 | multilist_sublist_t *mls = &ml->ml_sublists[i]; | |
224 | /* See comment in multilist_insert(). */ | |
225 | boolean_t need_lock = !MUTEX_HELD(&mls->mls_lock); | |
226 | ||
227 | if (need_lock) | |
228 | mutex_enter(&mls->mls_lock); | |
229 | ||
230 | if (!list_is_empty(&mls->mls_list)) { | |
231 | if (need_lock) | |
232 | mutex_exit(&mls->mls_lock); | |
233 | ||
234 | return (FALSE); | |
235 | } | |
236 | ||
237 | if (need_lock) | |
238 | mutex_exit(&mls->mls_lock); | |
239 | } | |
240 | ||
241 | return (TRUE); | |
242 | } | |
243 | ||
244 | /* Return the number of sublists composing this multilist */ | |
245 | unsigned int | |
246 | multilist_get_num_sublists(multilist_t *ml) | |
247 | { | |
248 | return (ml->ml_num_sublists); | |
249 | } | |
250 | ||
251 | /* Return a randomly selected, valid sublist index for this multilist */ | |
252 | unsigned int | |
253 | multilist_get_random_index(multilist_t *ml) | |
254 | { | |
255 | return (spa_get_random(ml->ml_num_sublists)); | |
256 | } | |
257 | ||
258 | /* Lock and return the sublist specified at the given index */ | |
259 | multilist_sublist_t * | |
260 | multilist_sublist_lock(multilist_t *ml, unsigned int sublist_idx) | |
261 | { | |
262 | multilist_sublist_t *mls; | |
263 | ||
264 | ASSERT3U(sublist_idx, <, ml->ml_num_sublists); | |
265 | mls = &ml->ml_sublists[sublist_idx]; | |
266 | mutex_enter(&mls->mls_lock); | |
267 | ||
268 | return (mls); | |
269 | } | |
270 | ||
271 | void | |
272 | multilist_sublist_unlock(multilist_sublist_t *mls) | |
273 | { | |
274 | mutex_exit(&mls->mls_lock); | |
275 | } | |
276 | ||
277 | /* | |
278 | * We're allowing any object to be inserted into this specific sublist, | |
279 | * but this can lead to trouble if multilist_remove() is called to | |
280 | * remove this object. Specifically, if calling ml_index_func on this | |
281 | * object returns an index for sublist different than what is passed as | |
282 | * a parameter here, any call to multilist_remove() with this newly | |
283 | * inserted object is undefined! (the call to multilist_remove() will | |
284 | * remove the object from a list that it isn't contained in) | |
285 | */ | |
286 | void | |
287 | multilist_sublist_insert_head(multilist_sublist_t *mls, void *obj) | |
288 | { | |
289 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
290 | list_insert_head(&mls->mls_list, obj); | |
291 | } | |
292 | ||
293 | /* please see comment above multilist_sublist_insert_head */ | |
294 | void | |
295 | multilist_sublist_insert_tail(multilist_sublist_t *mls, void *obj) | |
296 | { | |
297 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
298 | list_insert_tail(&mls->mls_list, obj); | |
299 | } | |
300 | ||
301 | /* | |
302 | * Move the object one element forward in the list. | |
303 | * | |
304 | * This function will move the given object forward in the list (towards | |
305 | * the head) by one object. So, in essence, it will swap its position in | |
306 | * the list with its "prev" pointer. If the given object is already at the | |
307 | * head of the list, it cannot be moved forward any more than it already | |
308 | * is, so no action is taken. | |
309 | * | |
310 | * NOTE: This function **must not** remove any object from the list other | |
311 | * than the object given as the parameter. This is relied upon in | |
312 | * arc_evict_state_impl(). | |
313 | */ | |
314 | void | |
315 | multilist_sublist_move_forward(multilist_sublist_t *mls, void *obj) | |
316 | { | |
317 | void *prev = list_prev(&mls->mls_list, obj); | |
318 | ||
319 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
320 | ASSERT(!list_is_empty(&mls->mls_list)); | |
321 | ||
322 | /* 'obj' must be at the head of the list, nothing to do */ | |
323 | if (prev == NULL) | |
324 | return; | |
325 | ||
326 | list_remove(&mls->mls_list, obj); | |
327 | list_insert_before(&mls->mls_list, prev, obj); | |
328 | } | |
329 | ||
330 | void | |
331 | multilist_sublist_remove(multilist_sublist_t *mls, void *obj) | |
332 | { | |
333 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
334 | list_remove(&mls->mls_list, obj); | |
335 | } | |
336 | ||
337 | void * | |
338 | multilist_sublist_head(multilist_sublist_t *mls) | |
339 | { | |
340 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
341 | return (list_head(&mls->mls_list)); | |
342 | } | |
343 | ||
344 | void * | |
345 | multilist_sublist_tail(multilist_sublist_t *mls) | |
346 | { | |
347 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
348 | return (list_tail(&mls->mls_list)); | |
349 | } | |
350 | ||
351 | void * | |
352 | multilist_sublist_next(multilist_sublist_t *mls, void *obj) | |
353 | { | |
354 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
355 | return (list_next(&mls->mls_list, obj)); | |
356 | } | |
357 | ||
358 | void * | |
359 | multilist_sublist_prev(multilist_sublist_t *mls, void *obj) | |
360 | { | |
361 | ASSERT(MUTEX_HELD(&mls->mls_lock)); | |
362 | return (list_prev(&mls->mls_list, obj)); | |
363 | } | |
364 | ||
365 | void | |
366 | multilist_link_init(multilist_node_t *link) | |
367 | { | |
368 | list_link_init(link); | |
369 | } | |
370 | ||
371 | int | |
372 | multilist_link_active(multilist_node_t *link) | |
373 | { | |
374 | return (list_link_active(link)); | |
375 | } |