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
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.
16 * Copyright (c) 2013, 2017 by Delphix. All rights reserved.
19 #include <sys/zfs_context.h>
20 #include <sys/multilist.h>
21 #include <sys/trace_multilist.h>
23 /* needed for spa_get_random() */
27 * This overrides the number of sublists in each multilist_t, which defaults
28 * to the number of CPUs in the system (see multilist_create()).
30 int zfs_multilist_num_sublists
= 0;
33 * Given the object contained on the list, return a pointer to the
34 * object's multilist_node_t structure it contains.
37 static multilist_node_t
*
38 multilist_d2l(multilist_t
*ml
, void *obj
)
40 return ((multilist_node_t
*)((char *)obj
+ ml
->ml_offset
));
45 * Initialize a new mutlilist using the parameters specified.
47 * - 'size' denotes the size of the structure containing the
49 * - 'offset' denotes the byte offset of the mutlilist_node_t within
50 * the structure that contains it.
51 * - 'num' specifies the number of internal sublists to create.
52 * - 'index_func' is used to determine which sublist to insert into
53 * when the multilist_insert() function is called; as well as which
54 * sublist to remove from when multilist_remove() is called. The
55 * requirements this function must meet, are the following:
57 * - It must always return the same value when called on the same
58 * object (to ensure the object is removed from the list it was
61 * - It must return a value in the range [0, number of sublists).
62 * The multilist_get_num_sublists() function may be used to
63 * determine the number of sublists in the multilist.
65 * Also, in order to reduce internal contention between the sublists
66 * during insertion and removal, this function should choose evenly
67 * between all available sublists when inserting. This isn't a hard
68 * requirement, but a general rule of thumb in order to garner the
69 * best multi-threaded performance out of the data structure.
72 multilist_create_impl(size_t size
, size_t offset
,
73 unsigned int num
, multilist_sublist_index_func_t
*index_func
)
76 ASSERT3U(size
, >=, offset
+ sizeof (multilist_node_t
));
78 ASSERT3P(index_func
, !=, NULL
);
80 multilist_t
*ml
= kmem_alloc(sizeof (*ml
), KM_SLEEP
);
81 ml
->ml_offset
= offset
;
82 ml
->ml_num_sublists
= num
;
83 ml
->ml_index_func
= index_func
;
85 ml
->ml_sublists
= kmem_zalloc(sizeof (multilist_sublist_t
) *
86 ml
->ml_num_sublists
, KM_SLEEP
);
88 ASSERT3P(ml
->ml_sublists
, !=, NULL
);
90 for (int i
= 0; i
< ml
->ml_num_sublists
; i
++) {
91 multilist_sublist_t
*mls
= &ml
->ml_sublists
[i
];
92 mutex_init(&mls
->mls_lock
, NULL
, MUTEX_NOLOCKDEP
, NULL
);
93 list_create(&mls
->mls_list
, size
, offset
);
99 * Allocate a new multilist, using the default number of sublists
100 * (the number of CPUs, or at least 4, or the tunable
101 * zfs_multilist_num_sublists).
104 multilist_create(size_t size
, size_t offset
,
105 multilist_sublist_index_func_t
*index_func
)
109 if (zfs_multilist_num_sublists
> 0) {
110 num_sublists
= zfs_multilist_num_sublists
;
112 num_sublists
= MAX(boot_ncpus
, 4);
115 return (multilist_create_impl(size
, offset
, num_sublists
, index_func
));
119 * Destroy the given multilist object, and free up any memory it holds.
122 multilist_destroy(multilist_t
*ml
)
126 ASSERT(multilist_is_empty(ml
));
128 for (i
= 0; i
< ml
->ml_num_sublists
; i
++) {
129 multilist_sublist_t
*mls
= &ml
->ml_sublists
[i
];
131 ASSERT(list_is_empty(&mls
->mls_list
));
133 list_destroy(&mls
->mls_list
);
134 mutex_destroy(&mls
->mls_lock
);
137 ASSERT3P(ml
->ml_sublists
, !=, NULL
);
138 kmem_free(ml
->ml_sublists
,
139 sizeof (multilist_sublist_t
) * ml
->ml_num_sublists
);
141 ml
->ml_num_sublists
= 0;
143 kmem_free(ml
, sizeof (multilist_t
));
147 * Insert the given object into the multilist.
149 * This function will insert the object specified into the sublist
150 * determined using the function given at multilist creation time.
152 * The sublist locks are automatically acquired if not already held, to
153 * ensure consistency when inserting and removing from multiple threads.
156 multilist_insert(multilist_t
*ml
, void *obj
)
158 unsigned int sublist_idx
= ml
->ml_index_func(ml
, obj
);
159 multilist_sublist_t
*mls
;
162 DTRACE_PROBE3(multilist__insert
, multilist_t
*, ml
,
163 unsigned int, sublist_idx
, void *, obj
);
165 ASSERT3U(sublist_idx
, <, ml
->ml_num_sublists
);
167 mls
= &ml
->ml_sublists
[sublist_idx
];
170 * Note: Callers may already hold the sublist lock by calling
171 * multilist_sublist_lock(). Here we rely on MUTEX_HELD()
172 * returning TRUE if and only if the current thread holds the
173 * lock. While it's a little ugly to make the lock recursive in
174 * this way, it works and allows the calling code to be much
175 * simpler -- otherwise it would have to pass around a flag
176 * indicating that it already has the lock.
178 need_lock
= !MUTEX_HELD(&mls
->mls_lock
);
181 mutex_enter(&mls
->mls_lock
);
183 ASSERT(!multilist_link_active(multilist_d2l(ml
, obj
)));
185 multilist_sublist_insert_head(mls
, obj
);
188 mutex_exit(&mls
->mls_lock
);
192 * Remove the given object from the multilist.
194 * This function will remove the object specified from the sublist
195 * determined using the function given at multilist creation time.
197 * The necessary sublist locks are automatically acquired, to ensure
198 * consistency when inserting and removing from multiple threads.
201 multilist_remove(multilist_t
*ml
, void *obj
)
203 unsigned int sublist_idx
= ml
->ml_index_func(ml
, obj
);
204 multilist_sublist_t
*mls
;
207 DTRACE_PROBE3(multilist__remove
, multilist_t
*, ml
,
208 unsigned int, sublist_idx
, void *, obj
);
210 ASSERT3U(sublist_idx
, <, ml
->ml_num_sublists
);
212 mls
= &ml
->ml_sublists
[sublist_idx
];
213 /* See comment in multilist_insert(). */
214 need_lock
= !MUTEX_HELD(&mls
->mls_lock
);
217 mutex_enter(&mls
->mls_lock
);
219 ASSERT(multilist_link_active(multilist_d2l(ml
, obj
)));
221 multilist_sublist_remove(mls
, obj
);
224 mutex_exit(&mls
->mls_lock
);
228 * Check to see if this multilist object is empty.
230 * This will return TRUE if it finds all of the sublists of this
231 * multilist to be empty, and FALSE otherwise. Each sublist lock will be
232 * automatically acquired as necessary.
234 * If concurrent insertions and removals are occurring, the semantics
235 * of this function become a little fuzzy. Instead of locking all
236 * sublists for the entire call time of the function, each sublist is
237 * only locked as it is individually checked for emptiness. Thus, it's
238 * possible for this function to return TRUE with non-empty sublists at
239 * the time the function returns. This would be due to another thread
240 * inserting into a given sublist, after that specific sublist was check
241 * and deemed empty, but before all sublists have been checked.
244 multilist_is_empty(multilist_t
*ml
)
248 for (i
= 0; i
< ml
->ml_num_sublists
; i
++) {
249 multilist_sublist_t
*mls
= &ml
->ml_sublists
[i
];
250 /* See comment in multilist_insert(). */
251 boolean_t need_lock
= !MUTEX_HELD(&mls
->mls_lock
);
254 mutex_enter(&mls
->mls_lock
);
256 if (!list_is_empty(&mls
->mls_list
)) {
258 mutex_exit(&mls
->mls_lock
);
264 mutex_exit(&mls
->mls_lock
);
270 /* Return the number of sublists composing this multilist */
272 multilist_get_num_sublists(multilist_t
*ml
)
274 return (ml
->ml_num_sublists
);
277 /* Return a randomly selected, valid sublist index for this multilist */
279 multilist_get_random_index(multilist_t
*ml
)
281 return (spa_get_random(ml
->ml_num_sublists
));
284 /* Lock and return the sublist specified at the given index */
285 multilist_sublist_t
*
286 multilist_sublist_lock(multilist_t
*ml
, unsigned int sublist_idx
)
288 multilist_sublist_t
*mls
;
290 ASSERT3U(sublist_idx
, <, ml
->ml_num_sublists
);
291 mls
= &ml
->ml_sublists
[sublist_idx
];
292 mutex_enter(&mls
->mls_lock
);
297 /* Lock and return the sublist that would be used to store the specified obj */
298 multilist_sublist_t
*
299 multilist_sublist_lock_obj(multilist_t
*ml
, void *obj
)
301 return (multilist_sublist_lock(ml
, ml
->ml_index_func(ml
, obj
)));
305 multilist_sublist_unlock(multilist_sublist_t
*mls
)
307 mutex_exit(&mls
->mls_lock
);
311 * We're allowing any object to be inserted into this specific sublist,
312 * but this can lead to trouble if multilist_remove() is called to
313 * remove this object. Specifically, if calling ml_index_func on this
314 * object returns an index for sublist different than what is passed as
315 * a parameter here, any call to multilist_remove() with this newly
316 * inserted object is undefined! (the call to multilist_remove() will
317 * remove the object from a list that it isn't contained in)
320 multilist_sublist_insert_head(multilist_sublist_t
*mls
, void *obj
)
322 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
323 list_insert_head(&mls
->mls_list
, obj
);
326 /* please see comment above multilist_sublist_insert_head */
328 multilist_sublist_insert_tail(multilist_sublist_t
*mls
, void *obj
)
330 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
331 list_insert_tail(&mls
->mls_list
, obj
);
335 * Move the object one element forward in the list.
337 * This function will move the given object forward in the list (towards
338 * the head) by one object. So, in essence, it will swap its position in
339 * the list with its "prev" pointer. If the given object is already at the
340 * head of the list, it cannot be moved forward any more than it already
341 * is, so no action is taken.
343 * NOTE: This function **must not** remove any object from the list other
344 * than the object given as the parameter. This is relied upon in
345 * arc_evict_state_impl().
348 multilist_sublist_move_forward(multilist_sublist_t
*mls
, void *obj
)
350 void *prev
= list_prev(&mls
->mls_list
, obj
);
352 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
353 ASSERT(!list_is_empty(&mls
->mls_list
));
355 /* 'obj' must be at the head of the list, nothing to do */
359 list_remove(&mls
->mls_list
, obj
);
360 list_insert_before(&mls
->mls_list
, prev
, obj
);
364 multilist_sublist_remove(multilist_sublist_t
*mls
, void *obj
)
366 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
367 list_remove(&mls
->mls_list
, obj
);
371 multilist_sublist_head(multilist_sublist_t
*mls
)
373 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
374 return (list_head(&mls
->mls_list
));
378 multilist_sublist_tail(multilist_sublist_t
*mls
)
380 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
381 return (list_tail(&mls
->mls_list
));
385 multilist_sublist_next(multilist_sublist_t
*mls
, void *obj
)
387 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
388 return (list_next(&mls
->mls_list
, obj
));
392 multilist_sublist_prev(multilist_sublist_t
*mls
, void *obj
)
394 ASSERT(MUTEX_HELD(&mls
->mls_lock
));
395 return (list_prev(&mls
->mls_list
, obj
));
399 multilist_link_init(multilist_node_t
*link
)
401 list_link_init(link
);
405 multilist_link_active(multilist_node_t
*link
)
407 return (list_link_active(link
));
410 #if defined(_KERNEL) && defined(HAVE_SPL)
414 module_param(zfs_multilist_num_sublists
, int, 0644);
415 MODULE_PARM_DESC(zfs_multilist_num_sublists
,
416 "Number of sublists used in each multilist");