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 2014 Joyent, Inc. All rights reserved.
14 * Copyright (c) 2014, Tegile Systems Inc. All rights reserved.
15 */
16
17 #include <sys/scsi/adapters/mpt_sas3/mptsas3_hash.h>
18 #include <sys/sysmacros.h>
19 #include <sys/types.h>
20 #include <sys/kmem.h>
21 #include <sys/list.h>
22 #include <sys/ddi.h>
23
24 #ifdef lint
25 extern refhash_link_t *obj_to_link(refhash_t *, void *);
26 extern void *link_to_obj(refhash_t *, refhash_link_t *);
27 extern void *obj_to_tag(refhash_t *, void *);
28 #else
29 #define obj_to_link(_h, _o) \
30 ((refhash_link_t *)(((char *)(_o)) + (_h)->rh_link_off))
31 #define link_to_obj(_h, _l) \
32 ((void *)(((char *)(_l)) - (_h)->rh_link_off))
33 #define obj_to_tag(_h, _o) \
34 ((void *)(((char *)(_o)) + (_h)->rh_tag_off))
35 #endif
36
37 refhash_t *
38 refhash_create(uint_t bucket_count, refhash_hash_f hash,
39 refhash_cmp_f cmp, refhash_dtor_f dtor, size_t obj_size, size_t link_off,
40 size_t tag_off, int km_flags)
41 {
42 refhash_t *hp;
43 uint_t i;
44
45 hp = kmem_alloc(sizeof (refhash_t), km_flags);
46 if (hp == NULL)
47 return (NULL);
48 hp->rh_buckets = kmem_zalloc(bucket_count * sizeof (list_t), km_flags);
49 if (hp->rh_buckets == NULL) {
50 kmem_free(hp, sizeof (refhash_t));
51 return (NULL);
52 }
53 hp->rh_bucket_count = bucket_count;
54
55 for (i = 0; i < bucket_count; i++) {
56 list_create(&hp->rh_buckets[i], sizeof (refhash_link_t),
57 offsetof(refhash_link_t, rhl_chain_link));
58 }
59 list_create(&hp->rh_objs, sizeof (refhash_link_t),
60 offsetof(refhash_link_t, rhl_global_link));
61
62 hp->rh_obj_size = obj_size;
63 hp->rh_link_off = link_off;
64 hp->rh_tag_off = tag_off;
65 hp->rh_hash = hash;
66 hp->rh_cmp = cmp;
67 hp->rh_dtor = dtor;
68
69 return (hp);
70 }
71
72 void
73 refhash_destroy(refhash_t *hp)
74 {
75 ASSERT(list_is_empty(&hp->rh_objs));
76
77 kmem_free(hp->rh_buckets, hp->rh_bucket_count * sizeof (list_t));
78 kmem_free(hp, sizeof (refhash_t));
79 }
80
81 void
82 refhash_insert(refhash_t *hp, void *op)
83 {
84 uint_t bucket;
85 refhash_link_t *lp = obj_to_link(hp, op);
86
87 bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count;
88 list_link_init(&lp->rhl_chain_link);
89 list_link_init(&lp->rhl_global_link);
90 lp->rhl_flags = 0;
91 lp->rhl_refcnt = 0;
92 list_insert_tail(&hp->rh_buckets[bucket], lp);
93 list_insert_tail(&hp->rh_objs, lp);
94 }
95
96 static void
97 refhash_delete(refhash_t *hp, void *op)
98 {
99 refhash_link_t *lp = obj_to_link(hp, op);
100 uint_t bucket;
101
102 bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count;
103 list_remove(&hp->rh_buckets[bucket], lp);
104 list_remove(&hp->rh_objs, lp);
105 hp->rh_dtor(op);
106 }
107
108 void
109 refhash_remove(refhash_t *hp, void *op)
110 {
111 refhash_link_t *lp = obj_to_link(hp, op);
112
113 if (lp->rhl_refcnt > 0) {
114 lp->rhl_flags |= RHL_F_DEAD;
115 } else {
116 refhash_delete(hp, op);
117 }
118 }
119
120 void *
121 refhash_lookup(refhash_t *hp, const void *tp)
122 {
123 uint_t bucket;
124 refhash_link_t *lp;
125 void *op;
126
127 bucket = hp->rh_hash(tp) % hp->rh_bucket_count;
128 for (lp = list_head(&hp->rh_buckets[bucket]); lp != NULL;
129 lp = list_next(&hp->rh_buckets[bucket], lp)) {
130 op = link_to_obj(hp, lp);
131 if (hp->rh_cmp(obj_to_tag(hp, op), tp) == 0 &&
132 !(lp->rhl_flags & RHL_F_DEAD)) {
133 return (op);
134 }
135 }
136
137 return (NULL);
138 }
139
140 void *
141 refhash_linear_search(refhash_t *hp, refhash_eval_f eval, void *arg)
142 {
143 void *op;
144 refhash_link_t *lp;
145
146 for (lp = list_head(&hp->rh_objs); lp != NULL;
147 lp = list_next(&hp->rh_objs, lp)) {
148 op = link_to_obj(hp, lp);
149 if (eval(op, arg) == 0)
150 return (op);
151 }
152
153 return (NULL);
154 }
155
156 void
157 refhash_hold(refhash_t *hp, void *op)
158 {
159 refhash_link_t *lp = obj_to_link(hp, op);
160
161 ++lp->rhl_refcnt;
162 }
163
164 void
165 refhash_rele(refhash_t *hp, void *op)
166 {
167 refhash_link_t *lp = obj_to_link(hp, op);
168
169 ASSERT(lp->rhl_refcnt > 0);
170
171 if (--lp->rhl_refcnt == 0 && (lp->rhl_flags & RHL_F_DEAD))
172 refhash_remove(hp, op);
173 }
174
175 void *
176 refhash_first(refhash_t *hp)
177 {
178 refhash_link_t *lp;
179
180 lp = list_head(&hp->rh_objs);
181 if (lp == NULL)
182 return (NULL);
183
184 ++lp->rhl_refcnt;
185
186 return (link_to_obj(hp, lp));
187 }
188
189 void *
190 refhash_next(refhash_t *hp, void *op)
191 {
192 refhash_link_t *lp;
193
194 lp = obj_to_link(hp, op);
195 while ((lp = list_next(&hp->rh_objs, lp)) != NULL) {
196 if (!(lp->rhl_flags & RHL_F_DEAD))
197 break;
198 }
199
200 refhash_rele(hp, op);
201 if (lp == NULL)
202 return (NULL);
203
204 ++lp->rhl_refcnt;
205
206 return (link_to_obj(hp, lp));
207 }
208
209 boolean_t
210 refhash_obj_valid(refhash_t *hp, const void *op)
211 {
212 /* LINTED - E_ARG_INCOMPATIBLE_WITH_ARG_L */
213 const refhash_link_t *lp = obj_to_link(hp, op);
214
215 return ((lp->rhl_flags & RHL_F_DEAD) != 0);
216 }