Home | History | Annotate | Line # | Download | only in sys 
      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, 2014 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 void multilist_create(multilist_t *, size_t, size_t, unsigned int,
     77     multilist_sublist_index_func_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 multilist_sublist_t *multilist_sublist_lock(multilist_t *, unsigned int);
     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 */
    107