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 (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #include "libuutil_common.h"
27 
28 #include <stdlib.h>
29 #include <string.h>
30 #include <unistd.h>
31 #include <sys/avl.h>
32 
33 static uu_avl_pool_t	uu_null_apool = { &uu_null_apool, &uu_null_apool };
34 static pthread_mutex_t	uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER;
35 
36 /*
37  * The index mark change on every insert and delete, to catch stale
38  * references.
39  *
40  * We leave the low bit alone, since the avl code uses it.
41  */
42 #define	INDEX_MAX		(sizeof (uintptr_t) - 2)
43 #define	INDEX_NEXT(m)		(((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX)
44 
45 #define	INDEX_DECODE(i)		((i) & ~INDEX_MAX)
46 #define	INDEX_ENCODE(p, n)	(((n) & ~INDEX_MAX) | (p)->ua_index)
47 #define	INDEX_VALID(p, i)	(((i) & INDEX_MAX) == (p)->ua_index)
48 #define	INDEX_CHECK(i)		(((i) & INDEX_MAX) != 0)
49 
50 /*
51  * When an element is inactive (not in a tree), we keep a marked pointer to
52  * its containing pool in its first word, and a NULL pointer in its second.
53  *
54  * On insert, we use these to verify that it comes from the correct pool.
55  */
56 #define	NODE_ARRAY(p, n)	((uintptr_t *)((uintptr_t)(n) + \
57 				    (pp)->uap_nodeoffset))
58 
59 #define	POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1))
60 
61 #define	DEAD_MARKER		0xc4
62 
63 uu_avl_pool_t *
uu_avl_pool_create(const char * name,size_t objsize,size_t nodeoffset,uu_compare_fn_t * compare_func,uint32_t flags)64 uu_avl_pool_create(const char *name, size_t objsize, size_t nodeoffset,
65     uu_compare_fn_t *compare_func, uint32_t flags)
66 {
67 	uu_avl_pool_t *pp, *next, *prev;
68 
69 	if (name == NULL ||
70 	    uu_check_name(name, UU_NAME_DOMAIN) == -1 ||
71 	    nodeoffset + sizeof (uu_avl_node_t) > objsize ||
72 	    compare_func == NULL) {
73 		uu_set_error(UU_ERROR_INVALID_ARGUMENT);
74 		return (NULL);
75 	}
76 
77 	if (flags & ~UU_AVL_POOL_DEBUG) {
78 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
79 		return (NULL);
80 	}
81 
82 	pp = uu_zalloc(sizeof (uu_avl_pool_t));
83 	if (pp == NULL) {
84 		uu_set_error(UU_ERROR_NO_MEMORY);
85 		return (NULL);
86 	}
87 
88 	(void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name));
89 	pp->uap_nodeoffset = nodeoffset;
90 	pp->uap_objsize = objsize;
91 	pp->uap_cmp = compare_func;
92 	if (flags & UU_AVL_POOL_DEBUG)
93 		pp->uap_debug = 1;
94 	pp->uap_last_index = 0;
95 
96 	(void) pthread_mutex_init(&pp->uap_lock, NULL);
97 
98 	pp->uap_null_avl.ua_next_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
99 	pp->uap_null_avl.ua_prev_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
100 
101 	(void) pthread_mutex_lock(&uu_apool_list_lock);
102 	pp->uap_next = next = &uu_null_apool;
103 	pp->uap_prev = prev = next->uap_prev;
104 	next->uap_prev = pp;
105 	prev->uap_next = pp;
106 	(void) pthread_mutex_unlock(&uu_apool_list_lock);
107 
108 	return (pp);
109 }
110 
111 void
uu_avl_pool_destroy(uu_avl_pool_t * pp)112 uu_avl_pool_destroy(uu_avl_pool_t *pp)
113 {
114 	if (pp->uap_debug) {
115 		if (pp->uap_null_avl.ua_next_enc !=
116 		    UU_PTR_ENCODE(&pp->uap_null_avl) ||
117 		    pp->uap_null_avl.ua_prev_enc !=
118 		    UU_PTR_ENCODE(&pp->uap_null_avl)) {
119 			uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has "
120 			    "outstanding avls, or is corrupt.\n",
121 			    (int)sizeof (pp->uap_name), pp->uap_name,
122 			    (void *)pp);
123 		}
124 	}
125 	(void) pthread_mutex_lock(&uu_apool_list_lock);
126 	pp->uap_next->uap_prev = pp->uap_prev;
127 	pp->uap_prev->uap_next = pp->uap_next;
128 	(void) pthread_mutex_unlock(&uu_apool_list_lock);
129 	(void) pthread_mutex_destroy(&pp->uap_lock);
130 	pp->uap_prev = NULL;
131 	pp->uap_next = NULL;
132 	uu_free(pp);
133 }
134 
135 void
uu_avl_node_init(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)136 uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
137 {
138 	uintptr_t *na = (uintptr_t *)np;
139 
140 	if (pp->uap_debug) {
141 		uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
142 		if (offset + sizeof (*np) > pp->uap_objsize) {
143 			uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
144 			    "offset %ld doesn't fit in object (size %ld)\n",
145 			    base, (void *)np, (void *)pp, pp->uap_name,
146 			    (long)offset, (long)pp->uap_objsize);
147 		}
148 		if (offset != pp->uap_nodeoffset) {
149 			uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
150 			    "offset %ld doesn't match pool's offset (%ld)\n",
151 			    base, (void *)np, (void *)pp, pp->uap_name,
152 			    (long)offset, (long)pp->uap_objsize);
153 		}
154 	}
155 
156 	na[0] = POOL_TO_MARKER(pp);
157 	na[1] = 0;
158 }
159 
160 void
uu_avl_node_fini(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)161 uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
162 {
163 	uintptr_t *na = (uintptr_t *)np;
164 
165 	if (pp->uap_debug) {
166 		if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) {
167 			uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
168 			    "node already finied\n",
169 			    base, (void *)np, (void *)pp, pp->uap_name);
170 		}
171 		if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) {
172 			uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
173 			    "node corrupt, in tree, or in different pool\n",
174 			    base, (void *)np, (void *)pp, pp->uap_name);
175 		}
176 	}
177 
178 	na[0] = DEAD_MARKER;
179 	na[1] = DEAD_MARKER;
180 	na[2] = DEAD_MARKER;
181 }
182 
183 struct uu_avl_node_compare_info {
184 	uu_compare_fn_t	*ac_compare;
185 	void		*ac_private;
186 	void		*ac_right;
187 	void		*ac_found;
188 };
189 
190 static int
uu_avl_node_compare(const void * l,const void * r)191 uu_avl_node_compare(const void *l, const void *r)
192 {
193 	struct uu_avl_node_compare_info *info =
194 	    (struct uu_avl_node_compare_info *)l;
195 
196 	int res = info->ac_compare(r, info->ac_right, info->ac_private);
197 
198 	if (res == 0) {
199 		if (info->ac_found == NULL)
200 			info->ac_found = (void *)r;
201 		return (-1);
202 	}
203 	if (res < 0)
204 		return (1);
205 	return (-1);
206 }
207 
208 uu_avl_t *
uu_avl_create(uu_avl_pool_t * pp,void * parent,uint32_t flags)209 uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags)
210 {
211 	uu_avl_t *ap, *next, *prev;
212 
213 	if (flags & ~UU_AVL_DEBUG) {
214 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
215 		return (NULL);
216 	}
217 
218 	ap = uu_zalloc(sizeof (*ap));
219 	if (ap == NULL) {
220 		uu_set_error(UU_ERROR_NO_MEMORY);
221 		return (NULL);
222 	}
223 
224 	ap->ua_pool = pp;
225 	ap->ua_parent_enc = UU_PTR_ENCODE(parent);
226 	ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG);
227 	ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index));
228 
229 	avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize,
230 	    pp->uap_nodeoffset);
231 
232 	ap->ua_null_walk.uaw_next = &ap->ua_null_walk;
233 	ap->ua_null_walk.uaw_prev = &ap->ua_null_walk;
234 
235 	(void) pthread_mutex_lock(&pp->uap_lock);
236 	next = &pp->uap_null_avl;
237 	prev = UU_PTR_DECODE(next->ua_prev_enc);
238 	ap->ua_next_enc = UU_PTR_ENCODE(next);
239 	ap->ua_prev_enc = UU_PTR_ENCODE(prev);
240 	next->ua_prev_enc = UU_PTR_ENCODE(ap);
241 	prev->ua_next_enc = UU_PTR_ENCODE(ap);
242 	(void) pthread_mutex_unlock(&pp->uap_lock);
243 
244 	return (ap);
245 }
246 
247 void
uu_avl_destroy(uu_avl_t * ap)248 uu_avl_destroy(uu_avl_t *ap)
249 {
250 	uu_avl_pool_t *pp = ap->ua_pool;
251 
252 	if (ap->ua_debug) {
253 		if (avl_numnodes(&ap->ua_tree) != 0) {
254 			uu_panic("uu_avl_destroy(%p): tree not empty\n",
255 			    (void *)ap);
256 		}
257 		if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
258 		    ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
259 			uu_panic("uu_avl_destroy(%p):  outstanding walkers\n",
260 			    (void *)ap);
261 		}
262 	}
263 	(void) pthread_mutex_lock(&pp->uap_lock);
264 	UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc;
265 	UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc;
266 	(void) pthread_mutex_unlock(&pp->uap_lock);
267 	ap->ua_prev_enc = UU_PTR_ENCODE(NULL);
268 	ap->ua_next_enc = UU_PTR_ENCODE(NULL);
269 
270 	ap->ua_pool = NULL;
271 	avl_destroy(&ap->ua_tree);
272 
273 	uu_free(ap);
274 }
275 
276 size_t
uu_avl_numnodes(uu_avl_t * ap)277 uu_avl_numnodes(uu_avl_t *ap)
278 {
279 	return (avl_numnodes(&ap->ua_tree));
280 }
281 
282 void *
uu_avl_first(uu_avl_t * ap)283 uu_avl_first(uu_avl_t *ap)
284 {
285 	return (avl_first(&ap->ua_tree));
286 }
287 
288 void *
uu_avl_last(uu_avl_t * ap)289 uu_avl_last(uu_avl_t *ap)
290 {
291 	return (avl_last(&ap->ua_tree));
292 }
293 
294 void *
uu_avl_next(uu_avl_t * ap,void * node)295 uu_avl_next(uu_avl_t *ap, void *node)
296 {
297 	return (AVL_NEXT(&ap->ua_tree, node));
298 }
299 
300 void *
uu_avl_prev(uu_avl_t * ap,void * node)301 uu_avl_prev(uu_avl_t *ap, void *node)
302 {
303 	return (AVL_PREV(&ap->ua_tree, node));
304 }
305 
306 static void
_avl_walk_init(uu_avl_walk_t * wp,uu_avl_t * ap,uint32_t flags)307 _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags)
308 {
309 	uu_avl_walk_t *next, *prev;
310 
311 	int robust = (flags & UU_WALK_ROBUST);
312 	int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
313 
314 	(void) memset(wp, 0, sizeof (*wp));
315 	wp->uaw_avl = ap;
316 	wp->uaw_robust = robust;
317 	wp->uaw_dir = direction;
318 
319 	if (direction > 0)
320 		wp->uaw_next_result = avl_first(&ap->ua_tree);
321 	else
322 		wp->uaw_next_result = avl_last(&ap->ua_tree);
323 
324 	if (ap->ua_debug || robust) {
325 		wp->uaw_next = next = &ap->ua_null_walk;
326 		wp->uaw_prev = prev = next->uaw_prev;
327 		next->uaw_prev = wp;
328 		prev->uaw_next = wp;
329 	}
330 }
331 
332 static void *
_avl_walk_advance(uu_avl_walk_t * wp,uu_avl_t * ap)333 _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap)
334 {
335 	void *np = wp->uaw_next_result;
336 
337 	avl_tree_t *t = &ap->ua_tree;
338 
339 	if (np == NULL)
340 		return (NULL);
341 
342 	wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) :
343 	    AVL_PREV(t, np);
344 
345 	return (np);
346 }
347 
348 static void
_avl_walk_fini(uu_avl_walk_t * wp)349 _avl_walk_fini(uu_avl_walk_t *wp)
350 {
351 	if (wp->uaw_next != NULL) {
352 		wp->uaw_next->uaw_prev = wp->uaw_prev;
353 		wp->uaw_prev->uaw_next = wp->uaw_next;
354 		wp->uaw_next = NULL;
355 		wp->uaw_prev = NULL;
356 	}
357 	wp->uaw_avl = NULL;
358 	wp->uaw_next_result = NULL;
359 }
360 
361 uu_avl_walk_t *
uu_avl_walk_start(uu_avl_t * ap,uint32_t flags)362 uu_avl_walk_start(uu_avl_t *ap, uint32_t flags)
363 {
364 	uu_avl_walk_t *wp;
365 
366 	if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
367 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
368 		return (NULL);
369 	}
370 
371 	wp = uu_zalloc(sizeof (*wp));
372 	if (wp == NULL) {
373 		uu_set_error(UU_ERROR_NO_MEMORY);
374 		return (NULL);
375 	}
376 
377 	_avl_walk_init(wp, ap, flags);
378 	return (wp);
379 }
380 
381 void *
uu_avl_walk_next(uu_avl_walk_t * wp)382 uu_avl_walk_next(uu_avl_walk_t *wp)
383 {
384 	return (_avl_walk_advance(wp, wp->uaw_avl));
385 }
386 
387 void
uu_avl_walk_end(uu_avl_walk_t * wp)388 uu_avl_walk_end(uu_avl_walk_t *wp)
389 {
390 	_avl_walk_fini(wp);
391 	uu_free(wp);
392 }
393 
394 int
uu_avl_walk(uu_avl_t * ap,uu_walk_fn_t * func,void * private,uint32_t flags)395 uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags)
396 {
397 	void *e;
398 	uu_avl_walk_t my_walk;
399 
400 	int status = UU_WALK_NEXT;
401 
402 	if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
403 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
404 		return (-1);
405 	}
406 
407 	_avl_walk_init(&my_walk, ap, flags);
408 	while (status == UU_WALK_NEXT &&
409 	    (e = _avl_walk_advance(&my_walk, ap)) != NULL)
410 		status = (*func)(e, private);
411 	_avl_walk_fini(&my_walk);
412 
413 	if (status >= 0)
414 		return (0);
415 	uu_set_error(UU_ERROR_CALLBACK_FAILED);
416 	return (-1);
417 }
418 
419 void
uu_avl_remove(uu_avl_t * ap,void * elem)420 uu_avl_remove(uu_avl_t *ap, void *elem)
421 {
422 	uu_avl_walk_t *wp;
423 	uu_avl_pool_t *pp = ap->ua_pool;
424 	uintptr_t *na = NODE_ARRAY(pp, elem);
425 
426 	if (ap->ua_debug) {
427 		/*
428 		 * invalidate outstanding uu_avl_index_ts.
429 		 */
430 		ap->ua_index = INDEX_NEXT(ap->ua_index);
431 	}
432 
433 	/*
434 	 * Robust walkers most be advanced, if we are removing the node
435 	 * they are currently using.  In debug mode, non-robust walkers
436 	 * are also on the walker list.
437 	 */
438 	for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk;
439 	    wp = wp->uaw_next) {
440 		if (wp->uaw_robust) {
441 			if (elem == wp->uaw_next_result)
442 				(void) _avl_walk_advance(wp, ap);
443 		} else if (wp->uaw_next_result != NULL) {
444 			uu_panic("uu_avl_remove(%p, %p): active non-robust "
445 			    "walker\n", (void *)ap, elem);
446 		}
447 	}
448 
449 	avl_remove(&ap->ua_tree, elem);
450 
451 	na[0] = POOL_TO_MARKER(pp);
452 	na[1] = 0;
453 }
454 
455 void *
uu_avl_teardown(uu_avl_t * ap,void ** cookie)456 uu_avl_teardown(uu_avl_t *ap, void **cookie)
457 {
458 	void *elem = avl_destroy_nodes(&ap->ua_tree, cookie);
459 
460 	if (elem != NULL) {
461 		uu_avl_pool_t *pp = ap->ua_pool;
462 		uintptr_t *na = NODE_ARRAY(pp, elem);
463 
464 		na[0] = POOL_TO_MARKER(pp);
465 		na[1] = 0;
466 	}
467 	return (elem);
468 }
469 
470 void *
uu_avl_find(uu_avl_t * ap,void * elem,void * private,uu_avl_index_t * out)471 uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out)
472 {
473 	struct uu_avl_node_compare_info info;
474 	void *result;
475 
476 	info.ac_compare = ap->ua_pool->uap_cmp;
477 	info.ac_private = private;
478 	info.ac_right = elem;
479 	info.ac_found = NULL;
480 
481 	result = avl_find(&ap->ua_tree, &info, out);
482 	if (out != NULL)
483 		*out = INDEX_ENCODE(ap, *out);
484 
485 	if (ap->ua_debug && result != NULL)
486 		uu_panic("uu_avl_find: internal error: avl_find succeeded\n");
487 
488 	return (info.ac_found);
489 }
490 
491 void
uu_avl_insert(uu_avl_t * ap,void * elem,uu_avl_index_t idx)492 uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx)
493 {
494 	if (ap->ua_debug) {
495 		uu_avl_pool_t *pp = ap->ua_pool;
496 		uintptr_t *na = NODE_ARRAY(pp, elem);
497 
498 		if (na[1] != 0)
499 			uu_panic("uu_avl_insert(%p, %p, %p): node already "
500 			    "in tree, or corrupt\n",
501 			    (void *)ap, elem, (void *)idx);
502 		if (na[0] == 0)
503 			uu_panic("uu_avl_insert(%p, %p, %p): node not "
504 			    "initialized\n",
505 			    (void *)ap, elem, (void *)idx);
506 		if (na[0] != POOL_TO_MARKER(pp))
507 			uu_panic("uu_avl_insert(%p, %p, %p): node from "
508 			    "other pool, or corrupt\n",
509 			    (void *)ap, elem, (void *)idx);
510 
511 		if (!INDEX_VALID(ap, idx))
512 			uu_panic("uu_avl_insert(%p, %p, %p): %s\n",
513 			    (void *)ap, elem, (void *)idx,
514 			    INDEX_CHECK(idx)? "outdated index" :
515 			    "invalid index");
516 
517 		/*
518 		 * invalidate outstanding uu_avl_index_ts.
519 		 */
520 		ap->ua_index = INDEX_NEXT(ap->ua_index);
521 	}
522 	avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx));
523 }
524 
525 void *
uu_avl_nearest_next(uu_avl_t * ap,uu_avl_index_t idx)526 uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx)
527 {
528 	if (ap->ua_debug && !INDEX_VALID(ap, idx))
529 		uu_panic("uu_avl_nearest_next(%p, %p): %s\n",
530 		    (void *)ap, (void *)idx, INDEX_CHECK(idx)?
531 		    "outdated index" : "invalid index");
532 	return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER));
533 }
534 
535 void *
uu_avl_nearest_prev(uu_avl_t * ap,uu_avl_index_t idx)536 uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx)
537 {
538 	if (ap->ua_debug && !INDEX_VALID(ap, idx))
539 		uu_panic("uu_avl_nearest_prev(%p, %p): %s\n",
540 		    (void *)ap, (void *)idx, INDEX_CHECK(idx)?
541 		    "outdated index" : "invalid index");
542 	return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE));
543 }
544 
545 /*
546  * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
547  */
548 void
uu_avl_lockup(void)549 uu_avl_lockup(void)
550 {
551 	uu_avl_pool_t *pp;
552 
553 	(void) pthread_mutex_lock(&uu_apool_list_lock);
554 	for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
555 	    pp = pp->uap_next)
556 		(void) pthread_mutex_lock(&pp->uap_lock);
557 }
558 
559 void
uu_avl_release(void)560 uu_avl_release(void)
561 {
562 	uu_avl_pool_t *pp;
563 
564 	for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
565 	    pp = pp->uap_next)
566 		(void) pthread_mutex_unlock(&pp->uap_lock);
567 	(void) pthread_mutex_unlock(&uu_apool_list_lock);
568 }
569