include/sys/multilist.h

   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, 2017 by Delphix. All rights reserved.
  17  */
  18
  19 #ifndef _SYS_MULTILIST_H
  20 #define _SYS_MULTILIST_H
  21
  22 #include <sys/zfs_context.h>
  23
  24 #ifdef  __cplusplus
  25 extern "C" {
  26 #endif
  27
  28 typedef list_node_t multilist_node_t;
  29 typedef struct multilist multilist_t;
  30 typedef struct multilist_sublist multilist_sublist_t;
  31 typedef unsigned int multilist_sublist_index_func_t(multilist_t *, void *);
  32
  33 struct multilist_sublist {
  34         /*
  35          * The mutex used internally to implement thread safe insertions
  36          * and removals to this individual sublist. It can also be locked
  37          * by a consumer using multilist_sublist_{lock,unlock}, which is
  38          * useful if a consumer needs to traverse the list in a thread
  39          * safe manner.
  40          */
  41         kmutex_t        mls_lock;
  42         /*
  43          * The actual list object containing all objects in this sublist.
  44          */
  45         list_t          mls_list;
  46         /*
  47          * Pad to cache line, in an effort to try and prevent cache line
  48          * contention.
  49          */
  50 } ____cacheline_aligned;
  51
  52 struct multilist {
  53         /*
  54          * This is used to get to the multilist_node_t structure given
  55          * the void *object contained on the list.
  56          */
  57         size_t                          ml_offset;
  58         /*
  59          * The number of sublists used internally by this multilist.
  60          */
  61         uint64_t                        ml_num_sublists;
  62         /*
  63          * The array of pointers to the actual sublists.
  64          */
  65         multilist_sublist_t             *ml_sublists;
  66         /*
  67          * Pointer to function which determines the sublist to use
  68          * when inserting and removing objects from this multilist.
  69          * Please see the comment above multilist_create for details.
  70          */
  71         multilist_sublist_index_func_t  *ml_index_func;
  72 };
  73
  74 void multilist_create(multilist_t *, size_t, size_t,
  75     multilist_sublist_index_func_t *);
  76 void multilist_destroy(multilist_t *);
  77
  78 void multilist_insert(multilist_t *, void *);
  79 void multilist_remove(multilist_t *, void *);
  80 int  multilist_is_empty(multilist_t *);
  81
  82 unsigned int multilist_get_num_sublists(multilist_t *);
  83 unsigned int multilist_get_random_index(multilist_t *);
  84
  85 multilist_sublist_t *multilist_sublist_lock(multilist_t *, unsigned int);
  86 multilist_sublist_t *multilist_sublist_lock_obj(multilist_t *, void *);
  87 void multilist_sublist_unlock(multilist_sublist_t *);
  88
  89 void multilist_sublist_insert_head(multilist_sublist_t *, void *);
  90 void multilist_sublist_insert_tail(multilist_sublist_t *, void *);
  91 void multilist_sublist_move_forward(multilist_sublist_t *mls, void *obj);
  92 void multilist_sublist_remove(multilist_sublist_t *, void *);
  93 int  multilist_sublist_is_empty(multilist_sublist_t *);
  94 int  multilist_sublist_is_empty_idx(multilist_t *, unsigned int);
  95
  96 void *multilist_sublist_head(multilist_sublist_t *);
  97 void *multilist_sublist_tail(multilist_sublist_t *);
  98 void *multilist_sublist_next(multilist_sublist_t *, void *);
  99 void *multilist_sublist_prev(multilist_sublist_t *, void *);
 100
 101 void multilist_link_init(multilist_node_t *);
 102 int  multilist_link_active(multilist_node_t *);
 103
 104 #ifdef  __cplusplus
 105 }
 106 #endif
 107
 108 #endif /* _SYS_MULTILIST_H */