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 void multilist_sublist_lock(multilist_sublist_t *); 86 multilist_sublist_t *multilist_sublist_lock_idx(multilist_t *, unsigned int); 87 multilist_sublist_t *multilist_sublist_lock_obj(multilist_t *, void *); 88 void multilist_sublist_unlock(multilist_sublist_t *); 89 90 void multilist_sublist_insert_head(multilist_sublist_t *, void *); 91 void multilist_sublist_insert_tail(multilist_sublist_t *, void *); 92 void multilist_sublist_insert_after(multilist_sublist_t *, void *, void *); 93 void multilist_sublist_insert_before(multilist_sublist_t *, void *, void *); 94 void multilist_sublist_move_forward(multilist_sublist_t *mls, void *obj); 95 void multilist_sublist_remove(multilist_sublist_t *, void *); 96 int multilist_sublist_is_empty(multilist_sublist_t *); 97 int multilist_sublist_is_empty_idx(multilist_t *, unsigned int); 98 99 void *multilist_sublist_head(multilist_sublist_t *); 100 void *multilist_sublist_tail(multilist_sublist_t *); 101 void *multilist_sublist_next(multilist_sublist_t *, void *); 102 void *multilist_sublist_prev(multilist_sublist_t *, void *); 103 104 void multilist_link_init(multilist_node_t *); 105 int multilist_link_active(multilist_node_t *); 106 107 #ifdef __cplusplus 108 } 109 #endif 110 111 #endif /* _SYS_MULTILIST_H */ 112