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