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 * 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 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 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 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 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 * 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 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 277 uu_avl_numnodes(uu_avl_t *ap) 278 { 279 return (avl_numnodes(&ap->ua_tree)); 280 } 281 282 void * 283 uu_avl_first(uu_avl_t *ap) 284 { 285 return (avl_first(&ap->ua_tree)); 286 } 287 288 void * 289 uu_avl_last(uu_avl_t *ap) 290 { 291 return (avl_last(&ap->ua_tree)); 292 } 293 294 void * 295 uu_avl_next(uu_avl_t *ap, void *node) 296 { 297 return (AVL_NEXT(&ap->ua_tree, node)); 298 } 299 300 void * 301 uu_avl_prev(uu_avl_t *ap, void *node) 302 { 303 return (AVL_PREV(&ap->ua_tree, node)); 304 } 305 306 static void 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 * 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 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 * 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 * 382 uu_avl_walk_next(uu_avl_walk_t *wp) 383 { 384 return (_avl_walk_advance(wp, wp->uaw_avl)); 385 } 386 387 void 388 uu_avl_walk_end(uu_avl_walk_t *wp) 389 { 390 _avl_walk_fini(wp); 391 uu_free(wp); 392 } 393 394 int 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 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 * 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 * 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 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 * 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 * 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 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 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