kernel/fs/zfs/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 (64 bytes), in an effort to try and prevent
  48          * cache line contention.
  49          */
  50         uint8_t         mls_pad[24];
  51 };
  52
  53 struct multilist {
  54         /*
  55          * This is used to get to the multilist_node_t structure given
  56          * the void *object contained on the list.
  57          */
  58         size_t                          ml_offset;
  59         /*
  60          * The number of sublists used internally by this multilist.
  61          */
  62         uint64_t                        ml_num_sublists;
  63         /*
  64          * The array of pointers to the actual sublists.
  65          */
  66         multilist_sublist_t             *ml_sublists;
  67         /*
  68          * Pointer to function which determines the sublist to use
  69          * when inserting and removing objects from this multilist.
  70          * Please see the comment above multilist_create for details.
  71          */
  72         multilist_sublist_index_func_t  *ml_index_func;
  73 };
  74
  75 void multilist_destroy(multilist_t *);
  76 multilist_t *multilist_create(size_t, size_t, multilist_sublist_index_func_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
  94 void *multilist_sublist_head(multilist_sublist_t *);
  95 void *multilist_sublist_tail(multilist_sublist_t *);
  96 void *multilist_sublist_next(multilist_sublist_t *, void *);
  97 void *multilist_sublist_prev(multilist_sublist_t *, void *);
  98
  99 void multilist_link_init(multilist_node_t *);
 100 int  multilist_link_active(multilist_node_t *);
 101
 102 #ifdef  __cplusplus
 103 }
 104 #endif
 105
 106 #endif /* _SYS_MULTILIST_H */