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