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