xref: /illumos-gate/usr/src/uts/common/refhash/refhash.c (revision db2effc6fa1e364418090bfc0ca0cfd267792bea)
1 /*
2  * This file and its contents are supplied under the terms of the
3  * Common Development and Distribution License ("CDDL"), version 1.0.
4  * You may only use this file in accordance with the terms of version
5  * 1.0 of the CDDL.
6  *
7  * A full copy of the text of the CDDL should have accompanied this
8  * source.  A copy of the CDDL is also available via the Internet at
9  * http://www.illumos.org/license/CDDL.
10  */
11 
12 /*
13  * Copyright 2015 Joyent, Inc.
14  */
15 
16 #include <sys/refhash.h>
17 #include <sys/sysmacros.h>
18 #include <sys/types.h>
19 #include <sys/kmem.h>
20 #include <sys/list.h>
21 #include <sys/ddi.h>
22 
23 #define	obj_to_link(_h, _o)	\
24 	((refhash_link_t *)(((char *)(_o)) + (_h)->rh_link_off))
25 #define	link_to_obj(_h, _l)	\
26 	((void *)(((char *)(_l)) - (_h)->rh_link_off))
27 #define	obj_to_tag(_h, _o)	\
28 	((void *)(((char *)(_o)) + (_h)->rh_tag_off))
29 
30 refhash_t *
refhash_create(uint_t bucket_count,refhash_hash_f hash,refhash_cmp_f cmp,refhash_dtor_f dtor,size_t obj_size,size_t link_off,size_t tag_off,int km_flags)31 refhash_create(uint_t bucket_count, refhash_hash_f hash,
32     refhash_cmp_f cmp, refhash_dtor_f dtor, size_t obj_size, size_t link_off,
33     size_t tag_off, int km_flags)
34 {
35 	refhash_t *hp;
36 	uint_t i;
37 
38 	hp = kmem_alloc(sizeof (refhash_t), km_flags);
39 	if (hp == NULL)
40 		return (NULL);
41 	hp->rh_buckets = kmem_zalloc(bucket_count * sizeof (list_t), km_flags);
42 	if (hp->rh_buckets == NULL) {
43 		kmem_free(hp, sizeof (refhash_t));
44 		return (NULL);
45 	}
46 	hp->rh_bucket_count = bucket_count;
47 
48 	for (i = 0; i < bucket_count; i++) {
49 		list_create(&hp->rh_buckets[i], sizeof (refhash_link_t),
50 		    offsetof(refhash_link_t, rhl_chain_link));
51 	}
52 	list_create(&hp->rh_objs, sizeof (refhash_link_t),
53 	    offsetof(refhash_link_t, rhl_global_link));
54 
55 	hp->rh_obj_size = obj_size;
56 	hp->rh_link_off = link_off;
57 	hp->rh_tag_off = tag_off;
58 	hp->rh_hash = hash;
59 	hp->rh_cmp = cmp;
60 	hp->rh_dtor = dtor;
61 
62 	return (hp);
63 }
64 
65 void
refhash_destroy(refhash_t * hp)66 refhash_destroy(refhash_t *hp)
67 {
68 	ASSERT(list_is_empty(&hp->rh_objs));
69 
70 	kmem_free(hp->rh_buckets, hp->rh_bucket_count * sizeof (list_t));
71 	kmem_free(hp, sizeof (refhash_t));
72 }
73 
74 void
refhash_insert(refhash_t * hp,void * op)75 refhash_insert(refhash_t *hp, void *op)
76 {
77 	uint_t bucket;
78 	refhash_link_t *lp = obj_to_link(hp, op);
79 
80 	bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count;
81 	list_link_init(&lp->rhl_chain_link);
82 	list_link_init(&lp->rhl_global_link);
83 	lp->rhl_flags = 0;
84 	lp->rhl_refcnt = 0;
85 	list_insert_tail(&hp->rh_buckets[bucket], lp);
86 	list_insert_tail(&hp->rh_objs, lp);
87 }
88 
89 static void
refhash_delete(refhash_t * hp,void * op)90 refhash_delete(refhash_t *hp, void *op)
91 {
92 	refhash_link_t *lp = obj_to_link(hp, op);
93 	uint_t bucket;
94 
95 	bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count;
96 	list_remove(&hp->rh_buckets[bucket], lp);
97 	list_remove(&hp->rh_objs, lp);
98 	hp->rh_dtor(op);
99 }
100 
101 void
refhash_remove(refhash_t * hp,void * op)102 refhash_remove(refhash_t *hp, void *op)
103 {
104 	refhash_link_t *lp = obj_to_link(hp, op);
105 
106 	if (lp->rhl_refcnt > 0) {
107 		lp->rhl_flags |= RHL_F_DEAD;
108 	} else {
109 		refhash_delete(hp, op);
110 	}
111 }
112 
113 void *
refhash_lookup(refhash_t * hp,const void * tp)114 refhash_lookup(refhash_t *hp, const void *tp)
115 {
116 	uint_t bucket;
117 	refhash_link_t *lp;
118 	void *op;
119 
120 	bucket = hp->rh_hash(tp) % hp->rh_bucket_count;
121 	for (lp = list_head(&hp->rh_buckets[bucket]); lp != NULL;
122 	    lp = list_next(&hp->rh_buckets[bucket], lp)) {
123 		op = link_to_obj(hp, lp);
124 		if (hp->rh_cmp(obj_to_tag(hp, op), tp) == 0 &&
125 		    !(lp->rhl_flags & RHL_F_DEAD)) {
126 			return (op);
127 		}
128 	}
129 
130 	return (NULL);
131 }
132 
133 void *
refhash_linear_search(refhash_t * hp,refhash_eval_f eval,void * arg)134 refhash_linear_search(refhash_t *hp, refhash_eval_f eval, void *arg)
135 {
136 	void *op;
137 	refhash_link_t *lp;
138 
139 	for (lp = list_head(&hp->rh_objs); lp != NULL;
140 	    lp = list_next(&hp->rh_objs, lp)) {
141 		op = link_to_obj(hp, lp);
142 		if (eval(op, arg) == 0)
143 			return (op);
144 	}
145 
146 	return (NULL);
147 }
148 
149 void
refhash_hold(refhash_t * hp,void * op)150 refhash_hold(refhash_t *hp, void *op)
151 {
152 	refhash_link_t *lp = obj_to_link(hp, op);
153 
154 	++lp->rhl_refcnt;
155 }
156 
157 void
refhash_rele(refhash_t * hp,void * op)158 refhash_rele(refhash_t *hp, void *op)
159 {
160 	refhash_link_t *lp = obj_to_link(hp, op);
161 
162 	ASSERT(lp->rhl_refcnt > 0);
163 
164 	if (--lp->rhl_refcnt == 0 && (lp->rhl_flags & RHL_F_DEAD))
165 		refhash_remove(hp, op);
166 }
167 
168 void *
refhash_first(refhash_t * hp)169 refhash_first(refhash_t *hp)
170 {
171 	refhash_link_t *lp;
172 
173 	lp = list_head(&hp->rh_objs);
174 	if (lp == NULL)
175 		return (NULL);
176 
177 	++lp->rhl_refcnt;
178 
179 	return (link_to_obj(hp, lp));
180 }
181 
182 void *
refhash_next(refhash_t * hp,void * op)183 refhash_next(refhash_t *hp, void *op)
184 {
185 	refhash_link_t *lp;
186 
187 	lp = obj_to_link(hp, op);
188 	while ((lp = list_next(&hp->rh_objs, lp)) != NULL) {
189 		if (!(lp->rhl_flags & RHL_F_DEAD))
190 			break;
191 	}
192 
193 	refhash_rele(hp, op);
194 	if (lp == NULL)
195 		return (NULL);
196 
197 	++lp->rhl_refcnt;
198 
199 	return (link_to_obj(hp, lp));
200 }
201 
202 boolean_t
refhash_obj_valid(refhash_t * hp,const void * op)203 refhash_obj_valid(refhash_t *hp, const void *op)
204 {
205 	const refhash_link_t *lp = obj_to_link(hp, op);
206 
207 	return ((lp->rhl_flags & RHL_F_DEAD) != 0);
208 }
209