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