1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 #pragma ident	"%Z%%M%	%I%	%E% SMI"
28 
29 #include <fmd_alloc.h>
30 #include <fmd_subr.h>
31 #include <fmd_conf.h>
32 #include <fmd_error.h>
33 #include <fmd_string.h>
34 #include <fmd_idspace.h>
35 #include <fmd.h>
36 
37 static int
38 highbit(ulong_t i)
39 {
40 	int h = 1;
41 
42 	if (i == 0)
43 		return (0);
44 
45 #ifdef _LP64
46 	if (i & 0xffffffff00000000ul) {
47 		h += 32;
48 		i >>= 32;
49 	}
50 #endif
51 
52 	if (i & 0xffff0000) {
53 		h += 16;
54 		i >>= 16;
55 	}
56 
57 	if (i & 0xff00) {
58 		h += 8;
59 		i >>= 8;
60 	}
61 
62 	if (i & 0xf0) {
63 		h += 4;
64 		i >>= 4;
65 	}
66 
67 	if (i & 0xc) {
68 		h += 2;
69 		i >>= 2;
70 	}
71 
72 	if (i & 0x2)
73 		h += 1;
74 
75 	return (h);
76 }
77 
78 fmd_idspace_t *
79 fmd_idspace_create(const char *name, id_t min, id_t max)
80 {
81 	fmd_idspace_t *ids = fmd_alloc(sizeof (fmd_idspace_t), FMD_SLEEP);
82 	uint_t ids_avg, ids_max, hashlen, hashmax;
83 
84 	/*
85 	 * Dynamically size the hash table bucket array based on the desired
86 	 * chain length.  We hash by indexing on the low-order bits.
87 	 * Do not permit the hash bucket array to exceed a reasonable size.
88 	 */
89 	ASSERT(min >= 0 && max >= 0);
90 	ASSERT(max >= min);
91 
92 	(void) fmd_conf_getprop(fmd.d_conf, "ids.avg", &ids_avg);
93 	(void) fmd_conf_getprop(fmd.d_conf, "ids.max", &ids_max);
94 
95 	hashmax = max - min + 1;
96 	hashlen = 1 << highbit(hashmax / ids_avg);
97 	if (hashlen > ids_max)
98 		hashlen = ids_max;
99 
100 	(void) strlcpy(ids->ids_name, name, sizeof (ids->ids_name));
101 	(void) pthread_mutex_init(&ids->ids_lock, NULL);
102 
103 	ids->ids_hash = fmd_zalloc(sizeof (void *) * hashlen, FMD_SLEEP);
104 	ids->ids_hashlen = hashlen;
105 	ids->ids_nextid = min - 1;
106 	ids->ids_minid = min;
107 	ids->ids_maxid = max;
108 	ids->ids_count = 0;
109 
110 	return (ids);
111 }
112 
113 void
114 fmd_idspace_destroy(fmd_idspace_t *ids)
115 {
116 	fmd_idelem_t *ide, *nde;
117 	uint_t i;
118 
119 	(void) pthread_mutex_lock(&ids->ids_lock);
120 
121 	for (i = 0; i < ids->ids_hashlen; i++) {
122 		for (ide = ids->ids_hash[i]; ide != NULL; ide = nde) {
123 			nde = ide->ide_next;
124 			fmd_free(ide, sizeof (fmd_idelem_t));
125 		}
126 	}
127 
128 	fmd_free(ids->ids_hash, sizeof (void *) * ids->ids_hashlen);
129 	fmd_free(ids, sizeof (fmd_idspace_t));
130 }
131 
132 void
133 fmd_idspace_apply(fmd_idspace_t *ids, void (*func)(void *, id_t), void *arg)
134 {
135 	fmd_idelem_t *ide;
136 	id_t *ida, *idp;
137 	uint_t i, count;
138 
139 	(void) pthread_mutex_lock(&ids->ids_lock);
140 	count = ids->ids_count;
141 	ida = idp = fmd_alloc(sizeof (id_t) * count, FMD_SLEEP);
142 
143 	for (i = 0; i < ids->ids_hashlen; i++) {
144 		for (ide = ids->ids_hash[i]; ide != NULL; ide = ide->ide_next)
145 			*idp++ = ide->ide_id;
146 	}
147 
148 	ASSERT(idp == ida + count);
149 	(void) pthread_mutex_unlock(&ids->ids_lock);
150 
151 	for (i = 0; i < count; i++)
152 		func(arg, ida[i]);
153 
154 	fmd_free(ida, sizeof (id_t) * count);
155 }
156 
157 static fmd_idelem_t *
158 fmd_idspace_lookup(fmd_idspace_t *ids, id_t id)
159 {
160 	fmd_idelem_t *ide;
161 
162 	ASSERT(MUTEX_HELD(&ids->ids_lock));
163 	ide = ids->ids_hash[id & (ids->ids_hashlen - 1)];
164 
165 	for (; ide != NULL; ide = ide->ide_next) {
166 		if (ide->ide_id == id)
167 			break;
168 	}
169 
170 	return (ide);
171 }
172 
173 void *
174 fmd_idspace_getspecific(fmd_idspace_t *ids, id_t id)
175 {
176 	fmd_idelem_t *ide;
177 	void *data;
178 
179 	(void) pthread_mutex_lock(&ids->ids_lock);
180 	ide = fmd_idspace_lookup(ids, id);
181 	data = ide ? ide->ide_data : NULL;
182 	(void) pthread_mutex_unlock(&ids->ids_lock);
183 
184 	return (data);
185 }
186 
187 void
188 fmd_idspace_setspecific(fmd_idspace_t *ids, id_t id, void *data)
189 {
190 	fmd_idelem_t *ide;
191 
192 	(void) pthread_mutex_lock(&ids->ids_lock);
193 
194 	if ((ide = fmd_idspace_lookup(ids, id)) == NULL) {
195 		fmd_panic("idspace %p (%s) does not contain id %ld",
196 		    (void *)ids, ids->ids_name, id);
197 	}
198 
199 	ide->ide_data = data;
200 	(void) pthread_mutex_unlock(&ids->ids_lock);
201 }
202 
203 int
204 fmd_idspace_contains(fmd_idspace_t *ids, id_t id)
205 {
206 	fmd_idelem_t *ide;
207 
208 	(void) pthread_mutex_lock(&ids->ids_lock);
209 	ide = fmd_idspace_lookup(ids, id);
210 	(void) pthread_mutex_unlock(&ids->ids_lock);
211 
212 	return (ide != NULL);
213 }
214 
215 int
216 fmd_idspace_valid(fmd_idspace_t *ids, id_t id)
217 {
218 	return (id >= ids->ids_minid && id <= ids->ids_maxid);
219 }
220 
221 static id_t
222 fmd_idspace_xalloc_locked(fmd_idspace_t *ids, id_t id, void *data)
223 {
224 	fmd_idelem_t *ide;
225 	uint_t h;
226 
227 	if (id < ids->ids_minid || id > ids->ids_maxid) {
228 		fmd_panic("%ld out of range [%ld .. %ld] for idspace %p (%s)\n",
229 		    id, ids->ids_minid, ids->ids_maxid,
230 		    (void *)ids, ids->ids_name);
231 	}
232 
233 	if (fmd_idspace_lookup(ids, id) != NULL)
234 		return (fmd_set_errno(EALREADY));
235 
236 	ide = fmd_alloc(sizeof (fmd_idelem_t), FMD_SLEEP);
237 	h = id & (ids->ids_hashlen - 1);
238 
239 	ide->ide_next = ids->ids_hash[h];
240 	ide->ide_data = data;
241 	ide->ide_id = id;
242 
243 	ids->ids_hash[h] = ide;
244 	ids->ids_count++;
245 
246 	return (id);
247 }
248 
249 id_t
250 fmd_idspace_xalloc(fmd_idspace_t *ids, id_t id, void *data)
251 {
252 	(void) pthread_mutex_lock(&ids->ids_lock);
253 	id = fmd_idspace_xalloc_locked(ids, id, data);
254 	(void) pthread_mutex_unlock(&ids->ids_lock);
255 	return (id);
256 }
257 
258 id_t
259 fmd_idspace_alloc(fmd_idspace_t *ids, void *data)
260 {
261 	id_t id;
262 
263 	(void) pthread_mutex_lock(&ids->ids_lock);
264 
265 	if (ids->ids_count == ids->ids_maxid - ids->ids_minid + 1) {
266 		(void) pthread_mutex_unlock(&ids->ids_lock);
267 		return (fmd_set_errno(ENOSPC));
268 	}
269 
270 	do {
271 		if (++ids->ids_nextid > ids->ids_maxid)
272 			ids->ids_nextid = ids->ids_minid;
273 		id = ids->ids_nextid;
274 	} while (fmd_idspace_xalloc_locked(ids, id, data) != id);
275 
276 	(void) pthread_mutex_unlock(&ids->ids_lock);
277 	return (id);
278 }
279 
280 void *
281 fmd_idspace_free(fmd_idspace_t *ids, id_t id)
282 {
283 	fmd_idelem_t *ide, **pp;
284 	void *data;
285 
286 	(void) pthread_mutex_lock(&ids->ids_lock);
287 	pp = &ids->ids_hash[id & (ids->ids_hashlen - 1)];
288 
289 	for (ide = *pp; ide != NULL; ide = ide->ide_next) {
290 		if (ide->ide_id != id)
291 			pp = &ide->ide_next;
292 		else
293 			break;
294 	}
295 
296 	if (ide == NULL) {
297 		(void) pthread_mutex_unlock(&ids->ids_lock);
298 		return (NULL);
299 	}
300 
301 	data = ide->ide_data;
302 	*pp = ide->ide_next;
303 	fmd_free(ide, sizeof (fmd_idelem_t));
304 
305 	ASSERT(ids->ids_count != 0);
306 	ids->ids_count--;
307 
308 	(void) pthread_mutex_unlock(&ids->ids_lock);
309 	return (data);
310 }
311