1 // SPDX-License-Identifier: CDDL-1.0 2 /* 3 * This file and its contents are supplied under the terms of the 4 * Common Development and Distribution License ("CDDL"), version 1.0. 5 * You may only use this file in accordance with the terms of version 6 * 1.0 of the CDDL. 7 * 8 * A full copy of the text of the CDDL should have accompanied this 9 * source. A copy of the CDDL is also available via the Internet at 10 * https://opensource.org/license/CDDL-1.0. 11 */ 12 /* 13 * Copyright (c) 2013, 2017 by Delphix. All rights reserved. 14 */ 15 16 #ifndef _SYS_MULTILIST_H 17 #define _SYS_MULTILIST_H 18 19 #include <sys/zfs_context.h> 20 21 #ifdef __cplusplus 22 extern "C" { 23 #endif 24 25 typedef list_node_t multilist_node_t; 26 typedef struct multilist multilist_t; 27 typedef struct multilist_sublist multilist_sublist_t; 28 typedef unsigned int multilist_sublist_index_func_t(multilist_t *, void *); 29 30 struct multilist_sublist { 31 /* 32 * The mutex used internally to implement thread safe insertions 33 * and removals to this individual sublist. It can also be locked 34 * by a consumer using multilist_sublist_{lock,unlock}, which is 35 * useful if a consumer needs to traverse the list in a thread 36 * safe manner. 37 */ 38 kmutex_t mls_lock; 39 /* 40 * The actual list object containing all objects in this sublist. 41 */ 42 list_t mls_list; 43 /* 44 * Pad to cache line, in an effort to try and prevent cache line 45 * contention. 46 */ 47 } ____cacheline_aligned; 48 49 struct multilist { 50 /* 51 * This is used to get to the multilist_node_t structure given 52 * the void *object contained on the list. 53 */ 54 size_t ml_offset; 55 /* 56 * The number of sublists used internally by this multilist. 57 */ 58 uint64_t ml_num_sublists; 59 /* 60 * The array of pointers to the actual sublists. 61 */ 62 multilist_sublist_t *ml_sublists; 63 /* 64 * Pointer to function which determines the sublist to use 65 * when inserting and removing objects from this multilist. 66 * Please see the comment above multilist_create for details. 67 */ 68 multilist_sublist_index_func_t *ml_index_func; 69 }; 70 71 void multilist_create(multilist_t *, size_t, size_t, 72 multilist_sublist_index_func_t *); 73 void multilist_destroy(multilist_t *); 74 75 void multilist_insert(multilist_t *, void *); 76 void multilist_remove(multilist_t *, void *); 77 int multilist_is_empty(multilist_t *); 78 79 unsigned int multilist_get_num_sublists(multilist_t *); 80 unsigned int multilist_get_random_index(multilist_t *); 81 82 void multilist_sublist_lock(multilist_sublist_t *); 83 multilist_sublist_t *multilist_sublist_lock_idx(multilist_t *, unsigned int); 84 multilist_sublist_t *multilist_sublist_lock_obj(multilist_t *, void *); 85 void multilist_sublist_unlock(multilist_sublist_t *); 86 87 void multilist_sublist_insert_head(multilist_sublist_t *, void *); 88 void multilist_sublist_insert_tail(multilist_sublist_t *, void *); 89 void multilist_sublist_insert_after(multilist_sublist_t *, void *, void *); 90 void multilist_sublist_insert_before(multilist_sublist_t *, void *, 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 */ 109