sys/cddl/contrib/opensolaris/uts/common/fs/zfs/multilist.c

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