1 // SPDX-License-Identifier: CDDL-1.0 2 /* 3 * CDDL HEADER START 4 * 5 * This file and its contents are supplied under the terms of the 6 * Common Development and Distribution License ("CDDL"), version 1.0. 7 * You may only use this file in accordance with the terms of version 8 * 1.0 of the CDDL. 9 * 10 * A full copy of the text of the CDDL should have accompanied this 11 * source. A copy of the CDDL is also available via the Internet at 12 * http://www.illumos.org/license/CDDL. 13 * 14 * CDDL HEADER END 15 */ 16 /* 17 * Copyright (c) 2013, 2017 by Delphix. All rights reserved. 18 */ 19 20 #ifndef _SYS_MULTILIST_H 21 #define _SYS_MULTILIST_H 22 23 #include <sys/zfs_context.h> 24 25 #ifdef __cplusplus 26 extern "C" { 27 #endif 28 29 typedef list_node_t multilist_node_t; 30 typedef struct multilist multilist_t; 31 typedef struct multilist_sublist multilist_sublist_t; 32 typedef unsigned int multilist_sublist_index_func_t(multilist_t *, void *); 33 34 struct multilist_sublist { 35 /* 36 * The mutex used internally to implement thread safe insertions 37 * and removals to this individual sublist. It can also be locked 38 * by a consumer using multilist_sublist_{lock,unlock}, which is 39 * useful if a consumer needs to traverse the list in a thread 40 * safe manner. 41 */ 42 kmutex_t mls_lock; 43 /* 44 * The actual list object containing all objects in this sublist. 45 */ 46 list_t mls_list; 47 /* 48 * Pad to cache line, in an effort to try and prevent cache line 49 * contention. 50 */ 51 } ____cacheline_aligned; 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_create(multilist_t *, size_t, size_t, 76 multilist_sublist_index_func_t *); 77 void multilist_destroy(multilist_t *); 78 79 void multilist_insert(multilist_t *, void *); 80 void multilist_remove(multilist_t *, void *); 81 int multilist_is_empty(multilist_t *); 82 83 unsigned int multilist_get_num_sublists(multilist_t *); 84 unsigned int multilist_get_random_index(multilist_t *); 85 86 void multilist_sublist_lock(multilist_sublist_t *); 87 multilist_sublist_t *multilist_sublist_lock_idx(multilist_t *, unsigned int); 88 multilist_sublist_t *multilist_sublist_lock_obj(multilist_t *, void *); 89 void multilist_sublist_unlock(multilist_sublist_t *); 90 91 void multilist_sublist_insert_head(multilist_sublist_t *, void *); 92 void multilist_sublist_insert_tail(multilist_sublist_t *, void *); 93 void multilist_sublist_insert_after(multilist_sublist_t *, void *, void *); 94 void multilist_sublist_insert_before(multilist_sublist_t *, void *, void *); 95 void multilist_sublist_move_forward(multilist_sublist_t *mls, void *obj); 96 void multilist_sublist_remove(multilist_sublist_t *, void *); 97 int multilist_sublist_is_empty(multilist_sublist_t *); 98 int multilist_sublist_is_empty_idx(multilist_t *, unsigned int); 99 100 void *multilist_sublist_head(multilist_sublist_t *); 101 void *multilist_sublist_tail(multilist_sublist_t *); 102 void *multilist_sublist_next(multilist_sublist_t *, void *); 103 void *multilist_sublist_prev(multilist_sublist_t *, void *); 104 105 void multilist_link_init(multilist_node_t *); 106 int multilist_link_active(multilist_node_t *); 107 108 #ifdef __cplusplus 109 } 110 #endif 111 112 #endif /* _SYS_MULTILIST_H */ 113