lib/libuutil/uu_avl.c

   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 }