diff --git a/include/libuutil_impl.h b/include/libuutil_impl.h index 7aa8f0cedf15..58b6df579d72 100644 --- a/include/libuutil_impl.h +++ b/include/libuutil_impl.h @@ -1,175 +1,156 @@ /* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License, Version 1.0 only * (the "License"). You may not use this file except in compliance * with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or https://opensource.org/licenses/CDDL-1.0. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright 2005 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. */ #ifndef _LIBUUTIL_IMPL_H #define _LIBUUTIL_IMPL_H #include #include #include #include #ifdef __cplusplus extern "C" { #endif void uu_set_error(uint_t); __attribute__((format(printf, 1, 2), __noreturn__)) void uu_panic(const char *format, ...); -/* - * For debugging purposes, libuutil keeps around linked lists of all uu_lists - * and uu_avls, along with pointers to their parents. These can cause false - * negatives when looking for memory leaks, so we encode the pointers by - * storing them with swapped endianness; this is not perfect, but it's about - * the best we can do without wasting a lot of space. - */ -#ifdef _LP64 -#define UU_PTR_ENCODE(ptr) BSWAP_64((uintptr_t)(void *)(ptr)) -#else -#define UU_PTR_ENCODE(ptr) BSWAP_32((uintptr_t)(void *)(ptr)) -#endif - -#define UU_PTR_DECODE(ptr) ((void *)UU_PTR_ENCODE(ptr)) - /* * uu_list structures */ typedef struct uu_list_node_impl { struct uu_list_node_impl *uln_next; struct uu_list_node_impl *uln_prev; } uu_list_node_impl_t; struct uu_list_walk { uu_list_walk_t *ulw_next; uu_list_walk_t *ulw_prev; uu_list_t *ulw_list; int8_t ulw_dir; uint8_t ulw_robust; uu_list_node_impl_t *ulw_next_result; }; struct uu_list { - uintptr_t ul_next_enc; - uintptr_t ul_prev_enc; + uu_list_t *ul_next; + uu_list_t *ul_prev; uu_list_pool_t *ul_pool; - uintptr_t ul_parent_enc; /* encoded parent pointer */ + void *ul_parent; size_t ul_offset; size_t ul_numnodes; uint8_t ul_debug; uint8_t ul_sorted; uint8_t ul_index; /* mark for uu_list_index_ts */ uu_list_node_impl_t ul_null_node; uu_list_walk_t ul_null_walk; /* for robust walkers */ }; -#define UU_LIST_PTR(ptr) ((uu_list_t *)UU_PTR_DECODE(ptr)) - #define UU_LIST_POOL_MAXNAME 64 struct uu_list_pool { uu_list_pool_t *ulp_next; uu_list_pool_t *ulp_prev; char ulp_name[UU_LIST_POOL_MAXNAME]; size_t ulp_nodeoffset; size_t ulp_objsize; uu_compare_fn_t *ulp_cmp; uint8_t ulp_debug; uint8_t ulp_last_index; pthread_mutex_t ulp_lock; /* protects null_list */ uu_list_t ulp_null_list; }; /* * uu_avl structures */ typedef struct avl_node uu_avl_node_impl_t; struct uu_avl_walk { uu_avl_walk_t *uaw_next; uu_avl_walk_t *uaw_prev; uu_avl_t *uaw_avl; void *uaw_next_result; int8_t uaw_dir; uint8_t uaw_robust; }; struct uu_avl { - uintptr_t ua_next_enc; - uintptr_t ua_prev_enc; + uu_avl_t *ua_next; + uu_avl_t *ua_prev; uu_avl_pool_t *ua_pool; - uintptr_t ua_parent_enc; + void *ua_parent; uint8_t ua_debug; uint8_t ua_index; /* mark for uu_avl_index_ts */ struct avl_tree ua_tree; uu_avl_walk_t ua_null_walk; }; -#define UU_AVL_PTR(x) ((uu_avl_t *)UU_PTR_DECODE(x)) - #define UU_AVL_POOL_MAXNAME 64 struct uu_avl_pool { uu_avl_pool_t *uap_next; uu_avl_pool_t *uap_prev; char uap_name[UU_AVL_POOL_MAXNAME]; size_t uap_nodeoffset; size_t uap_objsize; uu_compare_fn_t *uap_cmp; uint8_t uap_debug; uint8_t uap_last_index; pthread_mutex_t uap_lock; /* protects null_avl */ uu_avl_t uap_null_avl; }; /* * atfork() handlers */ void uu_avl_lockup(void); void uu_avl_release(void); void uu_list_lockup(void); void uu_list_release(void); #ifdef __cplusplus } #endif #endif /* _LIBUUTIL_IMPL_H */ diff --git a/lib/libuutil/uu_avl.c b/lib/libuutil/uu_avl.c index 12f7bd4bcc72..ef1497b31439 100644 --- a/lib/libuutil/uu_avl.c +++ b/lib/libuutil/uu_avl.c @@ -1,570 +1,568 @@ /* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License (the "License"). * You may not use this file except in compliance with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or https://opensource.org/licenses/CDDL-1.0. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright 2008 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. */ #include "libuutil_common.h" #include #include #include #include static uu_avl_pool_t uu_null_apool = { &uu_null_apool, &uu_null_apool }; static pthread_mutex_t uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER; /* * The index mark change on every insert and delete, to catch stale * references. * * We leave the low bit alone, since the avl code uses it. */ #define INDEX_MAX (sizeof (uintptr_t) - 2) #define INDEX_NEXT(m) (((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX) #define INDEX_DECODE(i) ((i) & ~INDEX_MAX) #define INDEX_ENCODE(p, n) (((n) & ~INDEX_MAX) | (p)->ua_index) #define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ua_index) #define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0) /* * When an element is inactive (not in a tree), we keep a marked pointer to * its containing pool in its first word, and a NULL pointer in its second. * * On insert, we use these to verify that it comes from the correct pool. */ #define NODE_ARRAY(p, n) ((uintptr_t *)((uintptr_t)(n) + \ (pp)->uap_nodeoffset)) #define POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1)) #define DEAD_MARKER 0xc4 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) { uu_avl_pool_t *pp, *next, *prev; if (name == NULL || uu_check_name(name, UU_NAME_DOMAIN) == -1 || nodeoffset + sizeof (uu_avl_node_t) > objsize || compare_func == NULL) { uu_set_error(UU_ERROR_INVALID_ARGUMENT); return (NULL); } if (flags & ~UU_AVL_POOL_DEBUG) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (NULL); } pp = uu_zalloc(sizeof (uu_avl_pool_t)); if (pp == NULL) { uu_set_error(UU_ERROR_NO_MEMORY); return (NULL); } (void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name)); pp->uap_nodeoffset = nodeoffset; pp->uap_objsize = objsize; pp->uap_cmp = compare_func; if (flags & UU_AVL_POOL_DEBUG) pp->uap_debug = 1; pp->uap_last_index = 0; (void) pthread_mutex_init(&pp->uap_lock, NULL); - pp->uap_null_avl.ua_next_enc = UU_PTR_ENCODE(&pp->uap_null_avl); - pp->uap_null_avl.ua_prev_enc = UU_PTR_ENCODE(&pp->uap_null_avl); + pp->uap_null_avl.ua_next = &pp->uap_null_avl; + pp->uap_null_avl.ua_prev = &pp->uap_null_avl; (void) pthread_mutex_lock(&uu_apool_list_lock); pp->uap_next = next = &uu_null_apool; pp->uap_prev = prev = next->uap_prev; next->uap_prev = pp; prev->uap_next = pp; (void) pthread_mutex_unlock(&uu_apool_list_lock); return (pp); } void uu_avl_pool_destroy(uu_avl_pool_t *pp) { if (pp->uap_debug) { - if (pp->uap_null_avl.ua_next_enc != - UU_PTR_ENCODE(&pp->uap_null_avl) || - pp->uap_null_avl.ua_prev_enc != - UU_PTR_ENCODE(&pp->uap_null_avl)) { + if (pp->uap_null_avl.ua_next != &pp->uap_null_avl || + pp->uap_null_avl.ua_prev != &pp->uap_null_avl) { uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has " "outstanding avls, or is corrupt.\n", (int)sizeof (pp->uap_name), pp->uap_name, (void *)pp); } } (void) pthread_mutex_lock(&uu_apool_list_lock); pp->uap_next->uap_prev = pp->uap_prev; pp->uap_prev->uap_next = pp->uap_next; (void) pthread_mutex_unlock(&uu_apool_list_lock); (void) pthread_mutex_destroy(&pp->uap_lock); pp->uap_prev = NULL; pp->uap_next = NULL; uu_free(pp); } void uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp) { uintptr_t *na = (uintptr_t *)np; if (pp->uap_debug) { uintptr_t offset = (uintptr_t)np - (uintptr_t)base; if (offset + sizeof (*np) > pp->uap_objsize) { uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): " "offset %ld doesn't fit in object (size %ld)\n", base, (void *)np, (void *)pp, pp->uap_name, (long)offset, (long)pp->uap_objsize); } if (offset != pp->uap_nodeoffset) { uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): " "offset %ld doesn't match pool's offset (%ld)\n", base, (void *)np, (void *)pp, pp->uap_name, (long)offset, (long)pp->uap_objsize); } } na[0] = POOL_TO_MARKER(pp); na[1] = 0; } void uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp) { uintptr_t *na = (uintptr_t *)np; if (pp->uap_debug) { if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) { uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): " "node already finied\n", base, (void *)np, (void *)pp, pp->uap_name); } if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) { uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): " "node corrupt, in tree, or in different pool\n", base, (void *)np, (void *)pp, pp->uap_name); } } na[0] = DEAD_MARKER; na[1] = DEAD_MARKER; na[2] = DEAD_MARKER; } struct uu_avl_node_compare_info { uu_compare_fn_t *ac_compare; void *ac_private; void *ac_right; void *ac_found; }; static int uu_avl_node_compare(const void *l, const void *r) { struct uu_avl_node_compare_info *info = (struct uu_avl_node_compare_info *)l; int res = info->ac_compare(r, info->ac_right, info->ac_private); if (res == 0) { if (info->ac_found == NULL) info->ac_found = (void *)r; return (-1); } if (res < 0) return (1); return (-1); } uu_avl_t * uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags) { uu_avl_t *ap, *next, *prev; if (flags & ~UU_AVL_DEBUG) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (NULL); } ap = uu_zalloc(sizeof (*ap)); if (ap == NULL) { uu_set_error(UU_ERROR_NO_MEMORY); return (NULL); } ap->ua_pool = pp; - ap->ua_parent_enc = UU_PTR_ENCODE(parent); + ap->ua_parent = parent; ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG); ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index)); avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize, pp->uap_nodeoffset); ap->ua_null_walk.uaw_next = &ap->ua_null_walk; ap->ua_null_walk.uaw_prev = &ap->ua_null_walk; (void) pthread_mutex_lock(&pp->uap_lock); next = &pp->uap_null_avl; - prev = UU_PTR_DECODE(next->ua_prev_enc); - ap->ua_next_enc = UU_PTR_ENCODE(next); - ap->ua_prev_enc = UU_PTR_ENCODE(prev); - next->ua_prev_enc = UU_PTR_ENCODE(ap); - prev->ua_next_enc = UU_PTR_ENCODE(ap); + prev = next->ua_prev; + ap->ua_next = next; + ap->ua_prev = prev; + next->ua_prev = ap; + prev->ua_next = ap; (void) pthread_mutex_unlock(&pp->uap_lock); return (ap); } void uu_avl_destroy(uu_avl_t *ap) { uu_avl_pool_t *pp = ap->ua_pool; if (ap->ua_debug) { if (avl_numnodes(&ap->ua_tree) != 0) { uu_panic("uu_avl_destroy(%p): tree not empty\n", (void *)ap); } if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk || ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) { uu_panic("uu_avl_destroy(%p): outstanding walkers\n", (void *)ap); } } (void) pthread_mutex_lock(&pp->uap_lock); - UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc; - UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc; + ap->ua_next->ua_prev = ap->ua_prev; + ap->ua_prev->ua_next = ap->ua_next; (void) pthread_mutex_unlock(&pp->uap_lock); - ap->ua_prev_enc = UU_PTR_ENCODE(NULL); - ap->ua_next_enc = UU_PTR_ENCODE(NULL); + ap->ua_prev = NULL; + ap->ua_next = NULL; ap->ua_pool = NULL; avl_destroy(&ap->ua_tree); uu_free(ap); } size_t uu_avl_numnodes(uu_avl_t *ap) { return (avl_numnodes(&ap->ua_tree)); } void * uu_avl_first(uu_avl_t *ap) { return (avl_first(&ap->ua_tree)); } void * uu_avl_last(uu_avl_t *ap) { return (avl_last(&ap->ua_tree)); } void * uu_avl_next(uu_avl_t *ap, void *node) { return (AVL_NEXT(&ap->ua_tree, node)); } void * uu_avl_prev(uu_avl_t *ap, void *node) { return (AVL_PREV(&ap->ua_tree, node)); } static void _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags) { uu_avl_walk_t *next, *prev; int robust = (flags & UU_WALK_ROBUST); int direction = (flags & UU_WALK_REVERSE)? -1 : 1; (void) memset(wp, 0, sizeof (*wp)); wp->uaw_avl = ap; wp->uaw_robust = robust; wp->uaw_dir = direction; if (direction > 0) wp->uaw_next_result = avl_first(&ap->ua_tree); else wp->uaw_next_result = avl_last(&ap->ua_tree); if (ap->ua_debug || robust) { wp->uaw_next = next = &ap->ua_null_walk; wp->uaw_prev = prev = next->uaw_prev; next->uaw_prev = wp; prev->uaw_next = wp; } } static void * _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap) { void *np = wp->uaw_next_result; avl_tree_t *t = &ap->ua_tree; if (np == NULL) return (NULL); wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) : AVL_PREV(t, np); return (np); } static void _avl_walk_fini(uu_avl_walk_t *wp) { if (wp->uaw_next != NULL) { wp->uaw_next->uaw_prev = wp->uaw_prev; wp->uaw_prev->uaw_next = wp->uaw_next; wp->uaw_next = NULL; wp->uaw_prev = NULL; } wp->uaw_avl = NULL; wp->uaw_next_result = NULL; } uu_avl_walk_t * uu_avl_walk_start(uu_avl_t *ap, uint32_t flags) { uu_avl_walk_t *wp; if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (NULL); } wp = uu_zalloc(sizeof (*wp)); if (wp == NULL) { uu_set_error(UU_ERROR_NO_MEMORY); return (NULL); } _avl_walk_init(wp, ap, flags); return (wp); } void * uu_avl_walk_next(uu_avl_walk_t *wp) { return (_avl_walk_advance(wp, wp->uaw_avl)); } void uu_avl_walk_end(uu_avl_walk_t *wp) { _avl_walk_fini(wp); uu_free(wp); } int uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags) { void *e; uu_avl_walk_t my_walk; int status = UU_WALK_NEXT; if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (-1); } _avl_walk_init(&my_walk, ap, flags); while (status == UU_WALK_NEXT && (e = _avl_walk_advance(&my_walk, ap)) != NULL) status = (*func)(e, private); _avl_walk_fini(&my_walk); if (status >= 0) return (0); uu_set_error(UU_ERROR_CALLBACK_FAILED); return (-1); } void uu_avl_remove(uu_avl_t *ap, void *elem) { uu_avl_walk_t *wp; uu_avl_pool_t *pp = ap->ua_pool; uintptr_t *na = NODE_ARRAY(pp, elem); if (ap->ua_debug) { /* * invalidate outstanding uu_avl_index_ts. */ ap->ua_index = INDEX_NEXT(ap->ua_index); } /* * Robust walkers most be advanced, if we are removing the node * they are currently using. In debug mode, non-robust walkers * are also on the walker list. */ for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk; wp = wp->uaw_next) { if (wp->uaw_robust) { if (elem == wp->uaw_next_result) (void) _avl_walk_advance(wp, ap); } else if (wp->uaw_next_result != NULL) { uu_panic("uu_avl_remove(%p, %p): active non-robust " "walker\n", (void *)ap, elem); } } avl_remove(&ap->ua_tree, elem); na[0] = POOL_TO_MARKER(pp); na[1] = 0; } void * uu_avl_teardown(uu_avl_t *ap, void **cookie) { void *elem = avl_destroy_nodes(&ap->ua_tree, cookie); if (elem != NULL) { uu_avl_pool_t *pp = ap->ua_pool; uintptr_t *na = NODE_ARRAY(pp, elem); na[0] = POOL_TO_MARKER(pp); na[1] = 0; } return (elem); } void * uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out) { struct uu_avl_node_compare_info info; void *result; info.ac_compare = ap->ua_pool->uap_cmp; info.ac_private = private; info.ac_right = elem; info.ac_found = NULL; result = avl_find(&ap->ua_tree, &info, out); if (out != NULL) *out = INDEX_ENCODE(ap, *out); if (ap->ua_debug && result != NULL) uu_panic("uu_avl_find: internal error: avl_find succeeded\n"); return (info.ac_found); } void uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx) { if (ap->ua_debug) { uu_avl_pool_t *pp = ap->ua_pool; uintptr_t *na = NODE_ARRAY(pp, elem); if (na[1] != 0) uu_panic("uu_avl_insert(%p, %p, %p): node already " "in tree, or corrupt\n", (void *)ap, elem, (void *)idx); if (na[0] == 0) uu_panic("uu_avl_insert(%p, %p, %p): node not " "initialized\n", (void *)ap, elem, (void *)idx); if (na[0] != POOL_TO_MARKER(pp)) uu_panic("uu_avl_insert(%p, %p, %p): node from " "other pool, or corrupt\n", (void *)ap, elem, (void *)idx); if (!INDEX_VALID(ap, idx)) uu_panic("uu_avl_insert(%p, %p, %p): %s\n", (void *)ap, elem, (void *)idx, INDEX_CHECK(idx)? "outdated index" : "invalid index"); /* * invalidate outstanding uu_avl_index_ts. */ ap->ua_index = INDEX_NEXT(ap->ua_index); } avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx)); } void * uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx) { if (ap->ua_debug && !INDEX_VALID(ap, idx)) uu_panic("uu_avl_nearest_next(%p, %p): %s\n", (void *)ap, (void *)idx, INDEX_CHECK(idx)? "outdated index" : "invalid index"); return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER)); } void * uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx) { if (ap->ua_debug && !INDEX_VALID(ap, idx)) uu_panic("uu_avl_nearest_prev(%p, %p): %s\n", (void *)ap, (void *)idx, INDEX_CHECK(idx)? "outdated index" : "invalid index"); return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE)); } /* * called from uu_lockup() and uu_release(), as part of our fork1()-safety. */ void uu_avl_lockup(void) { uu_avl_pool_t *pp; (void) pthread_mutex_lock(&uu_apool_list_lock); for (pp = uu_null_apool.uap_next; pp != &uu_null_apool; pp = pp->uap_next) (void) pthread_mutex_lock(&pp->uap_lock); } void uu_avl_release(void) { uu_avl_pool_t *pp; for (pp = uu_null_apool.uap_next; pp != &uu_null_apool; pp = pp->uap_next) (void) pthread_mutex_unlock(&pp->uap_lock); (void) pthread_mutex_unlock(&uu_apool_list_lock); } diff --git a/lib/libuutil/uu_list.c b/lib/libuutil/uu_list.c index 5ece4b14701e..0ca6f05205e9 100644 --- a/lib/libuutil/uu_list.c +++ b/lib/libuutil/uu_list.c @@ -1,718 +1,716 @@ /* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License (the "License"). * You may not use this file except in compliance with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or https://opensource.org/licenses/CDDL-1.0. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright 2008 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. */ #include "libuutil_common.h" #include #include #include #include #define ELEM_TO_NODE(lp, e) \ ((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset)) #define NODE_TO_ELEM(lp, n) \ ((void *)((uintptr_t)(n) - (lp)->ul_offset)) /* * uu_list_index_ts define a location for insertion. They are simply a * pointer to the object after the insertion point. We store a mark * in the low-bits of the index, to help prevent mistakes. * * When debugging, the index mark changes on every insert and delete, to * catch stale references. */ #define INDEX_MAX (sizeof (uintptr_t) - 1) #define INDEX_NEXT(m) (((m) == INDEX_MAX)? 1 : ((m) + 1) & INDEX_MAX) #define INDEX_TO_NODE(i) ((uu_list_node_impl_t *)((i) & ~INDEX_MAX)) #define NODE_TO_INDEX(p, n) (((uintptr_t)(n) & ~INDEX_MAX) | (p)->ul_index) #define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ul_index) #define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0) #define POOL_TO_MARKER(pp) ((void *)((uintptr_t)(pp) | 1)) static uu_list_pool_t uu_null_lpool = { &uu_null_lpool, &uu_null_lpool }; static pthread_mutex_t uu_lpool_list_lock = PTHREAD_MUTEX_INITIALIZER; uu_list_pool_t * uu_list_pool_create(const char *name, size_t objsize, size_t nodeoffset, uu_compare_fn_t *compare_func, uint32_t flags) { uu_list_pool_t *pp, *next, *prev; if (name == NULL || uu_check_name(name, UU_NAME_DOMAIN) == -1 || nodeoffset + sizeof (uu_list_node_t) > objsize) { uu_set_error(UU_ERROR_INVALID_ARGUMENT); return (NULL); } if (flags & ~UU_LIST_POOL_DEBUG) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (NULL); } pp = uu_zalloc(sizeof (uu_list_pool_t)); if (pp == NULL) { uu_set_error(UU_ERROR_NO_MEMORY); return (NULL); } (void) strlcpy(pp->ulp_name, name, sizeof (pp->ulp_name)); pp->ulp_nodeoffset = nodeoffset; pp->ulp_objsize = objsize; pp->ulp_cmp = compare_func; if (flags & UU_LIST_POOL_DEBUG) pp->ulp_debug = 1; pp->ulp_last_index = 0; (void) pthread_mutex_init(&pp->ulp_lock, NULL); - pp->ulp_null_list.ul_next_enc = UU_PTR_ENCODE(&pp->ulp_null_list); - pp->ulp_null_list.ul_prev_enc = UU_PTR_ENCODE(&pp->ulp_null_list); + pp->ulp_null_list.ul_next = &pp->ulp_null_list; + pp->ulp_null_list.ul_prev = &pp->ulp_null_list; (void) pthread_mutex_lock(&uu_lpool_list_lock); pp->ulp_next = next = &uu_null_lpool; pp->ulp_prev = prev = next->ulp_prev; next->ulp_prev = pp; prev->ulp_next = pp; (void) pthread_mutex_unlock(&uu_lpool_list_lock); return (pp); } void uu_list_pool_destroy(uu_list_pool_t *pp) { if (pp->ulp_debug) { - if (pp->ulp_null_list.ul_next_enc != - UU_PTR_ENCODE(&pp->ulp_null_list) || - pp->ulp_null_list.ul_prev_enc != - UU_PTR_ENCODE(&pp->ulp_null_list)) { + if (pp->ulp_null_list.ul_next != &pp->ulp_null_list || + pp->ulp_null_list.ul_prev != &pp->ulp_null_list) { uu_panic("uu_list_pool_destroy: Pool \"%.*s\" (%p) has " "outstanding lists, or is corrupt.\n", (int)sizeof (pp->ulp_name), pp->ulp_name, (void *)pp); } } (void) pthread_mutex_lock(&uu_lpool_list_lock); pp->ulp_next->ulp_prev = pp->ulp_prev; pp->ulp_prev->ulp_next = pp->ulp_next; (void) pthread_mutex_unlock(&uu_lpool_list_lock); pp->ulp_prev = NULL; pp->ulp_next = NULL; uu_free(pp); } void uu_list_node_init(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp) { uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg; if (pp->ulp_debug) { uintptr_t offset = (uintptr_t)np - (uintptr_t)base; if (offset + sizeof (*np) > pp->ulp_objsize) { uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): " "offset %ld doesn't fit in object (size %ld)\n", base, (void *)np, (void *)pp, pp->ulp_name, (long)offset, (long)pp->ulp_objsize); } if (offset != pp->ulp_nodeoffset) { uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): " "offset %ld doesn't match pool's offset (%ld)\n", base, (void *)np, (void *)pp, pp->ulp_name, (long)offset, (long)pp->ulp_objsize); } } np->uln_next = POOL_TO_MARKER(pp); np->uln_prev = NULL; } void uu_list_node_fini(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp) { uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg; if (pp->ulp_debug) { if (np->uln_next == NULL && np->uln_prev == NULL) { uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): " "node already finied\n", base, (void *)np_arg, (void *)pp, pp->ulp_name); } if (np->uln_next != POOL_TO_MARKER(pp) || np->uln_prev != NULL) { uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): " "node corrupt or on list\n", base, (void *)np_arg, (void *)pp, pp->ulp_name); } } np->uln_next = NULL; np->uln_prev = NULL; } uu_list_t * uu_list_create(uu_list_pool_t *pp, void *parent, uint32_t flags) { uu_list_t *lp, *next, *prev; if (flags & ~(UU_LIST_DEBUG | UU_LIST_SORTED)) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (NULL); } if ((flags & UU_LIST_SORTED) && pp->ulp_cmp == NULL) { if (pp->ulp_debug) uu_panic("uu_list_create(%p, ...): requested " "UU_LIST_SORTED, but pool has no comparison func\n", (void *)pp); uu_set_error(UU_ERROR_NOT_SUPPORTED); return (NULL); } lp = uu_zalloc(sizeof (*lp)); if (lp == NULL) { uu_set_error(UU_ERROR_NO_MEMORY); return (NULL); } lp->ul_pool = pp; - lp->ul_parent_enc = UU_PTR_ENCODE(parent); + lp->ul_parent = parent; lp->ul_offset = pp->ulp_nodeoffset; lp->ul_debug = pp->ulp_debug || (flags & UU_LIST_DEBUG); lp->ul_sorted = (flags & UU_LIST_SORTED); lp->ul_numnodes = 0; lp->ul_index = (pp->ulp_last_index = INDEX_NEXT(pp->ulp_last_index)); lp->ul_null_node.uln_next = &lp->ul_null_node; lp->ul_null_node.uln_prev = &lp->ul_null_node; lp->ul_null_walk.ulw_next = &lp->ul_null_walk; lp->ul_null_walk.ulw_prev = &lp->ul_null_walk; (void) pthread_mutex_lock(&pp->ulp_lock); next = &pp->ulp_null_list; - prev = UU_PTR_DECODE(next->ul_prev_enc); - lp->ul_next_enc = UU_PTR_ENCODE(next); - lp->ul_prev_enc = UU_PTR_ENCODE(prev); - next->ul_prev_enc = UU_PTR_ENCODE(lp); - prev->ul_next_enc = UU_PTR_ENCODE(lp); + prev = next->ul_prev; + lp->ul_next = next; + lp->ul_prev = prev; + next->ul_prev = lp; + prev->ul_next = lp; (void) pthread_mutex_unlock(&pp->ulp_lock); return (lp); } void uu_list_destroy(uu_list_t *lp) { uu_list_pool_t *pp = lp->ul_pool; if (lp->ul_debug) { if (lp->ul_null_node.uln_next != &lp->ul_null_node || lp->ul_null_node.uln_prev != &lp->ul_null_node) { uu_panic("uu_list_destroy(%p): list not empty\n", (void *)lp); } if (lp->ul_numnodes != 0) { uu_panic("uu_list_destroy(%p): numnodes is nonzero, " "but list is empty\n", (void *)lp); } if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk || lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) { uu_panic("uu_list_destroy(%p): outstanding walkers\n", (void *)lp); } } (void) pthread_mutex_lock(&pp->ulp_lock); - UU_LIST_PTR(lp->ul_next_enc)->ul_prev_enc = lp->ul_prev_enc; - UU_LIST_PTR(lp->ul_prev_enc)->ul_next_enc = lp->ul_next_enc; + lp->ul_next->ul_prev = lp->ul_prev; + lp->ul_prev->ul_next = lp->ul_next; (void) pthread_mutex_unlock(&pp->ulp_lock); - lp->ul_prev_enc = UU_PTR_ENCODE(NULL); - lp->ul_next_enc = UU_PTR_ENCODE(NULL); + lp->ul_prev = NULL; + lp->ul_next = NULL; lp->ul_pool = NULL; uu_free(lp); } static void list_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev, uu_list_node_impl_t *next) { if (lp->ul_debug) { if (next->uln_prev != prev || prev->uln_next != next) uu_panic("insert(%p): internal error: %p and %p not " "neighbors\n", (void *)lp, (void *)next, (void *)prev); if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) || np->uln_prev != NULL) { uu_panic("insert(%p): elem %p node %p corrupt, " "not initialized, or already in a list.\n", (void *)lp, NODE_TO_ELEM(lp, np), (void *)np); } /* * invalidate outstanding uu_list_index_ts. */ lp->ul_index = INDEX_NEXT(lp->ul_index); } np->uln_next = next; np->uln_prev = prev; next->uln_prev = np; prev->uln_next = np; lp->ul_numnodes++; } void uu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx) { uu_list_node_impl_t *np; np = INDEX_TO_NODE(idx); if (np == NULL) np = &lp->ul_null_node; if (lp->ul_debug) { if (!INDEX_VALID(lp, idx)) uu_panic("uu_list_insert(%p, %p, %p): %s\n", (void *)lp, elem, (void *)idx, INDEX_CHECK(idx)? "outdated index" : "invalid index"); if (np->uln_prev == NULL) uu_panic("uu_list_insert(%p, %p, %p): out-of-date " "index\n", (void *)lp, elem, (void *)idx); } list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); } void * uu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out) { int sorted = lp->ul_sorted; uu_compare_fn_t *func = lp->ul_pool->ulp_cmp; uu_list_node_impl_t *np; if (func == NULL) { if (out != NULL) *out = 0; uu_set_error(UU_ERROR_NOT_SUPPORTED); return (NULL); } for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node; np = np->uln_next) { void *ep = NODE_TO_ELEM(lp, np); int cmp = func(ep, elem, private); if (cmp == 0) { if (out != NULL) *out = NODE_TO_INDEX(lp, np); return (ep); } if (sorted && cmp > 0) { if (out != NULL) *out = NODE_TO_INDEX(lp, np); return (NULL); } } if (out != NULL) *out = NODE_TO_INDEX(lp, 0); return (NULL); } void * uu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx) { uu_list_node_impl_t *np = INDEX_TO_NODE(idx); if (np == NULL) np = &lp->ul_null_node; if (lp->ul_debug) { if (!INDEX_VALID(lp, idx)) uu_panic("uu_list_nearest_next(%p, %p): %s\n", (void *)lp, (void *)idx, INDEX_CHECK(idx)? "outdated index" : "invalid index"); if (np->uln_prev == NULL) uu_panic("uu_list_nearest_next(%p, %p): out-of-date " "index\n", (void *)lp, (void *)idx); } if (np == &lp->ul_null_node) return (NULL); else return (NODE_TO_ELEM(lp, np)); } void * uu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx) { uu_list_node_impl_t *np = INDEX_TO_NODE(idx); if (np == NULL) np = &lp->ul_null_node; if (lp->ul_debug) { if (!INDEX_VALID(lp, idx)) uu_panic("uu_list_nearest_prev(%p, %p): %s\n", (void *)lp, (void *)idx, INDEX_CHECK(idx)? "outdated index" : "invalid index"); if (np->uln_prev == NULL) uu_panic("uu_list_nearest_prev(%p, %p): out-of-date " "index\n", (void *)lp, (void *)idx); } if ((np = np->uln_prev) == &lp->ul_null_node) return (NULL); else return (NODE_TO_ELEM(lp, np)); } static void list_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags) { uu_list_walk_t *next, *prev; int robust = (flags & UU_WALK_ROBUST); int direction = (flags & UU_WALK_REVERSE)? -1 : 1; (void) memset(wp, 0, sizeof (*wp)); wp->ulw_list = lp; wp->ulw_robust = robust; wp->ulw_dir = direction; if (direction > 0) wp->ulw_next_result = lp->ul_null_node.uln_next; else wp->ulw_next_result = lp->ul_null_node.uln_prev; if (lp->ul_debug || robust) { /* * Add this walker to the list's list of walkers so * uu_list_remove() can advance us if somebody tries to * remove ulw_next_result. */ wp->ulw_next = next = &lp->ul_null_walk; wp->ulw_prev = prev = next->ulw_prev; next->ulw_prev = wp; prev->ulw_next = wp; } } static uu_list_node_impl_t * list_walk_advance(uu_list_walk_t *wp, uu_list_t *lp) { uu_list_node_impl_t *np = wp->ulw_next_result; uu_list_node_impl_t *next; if (np == &lp->ul_null_node) return (NULL); next = (wp->ulw_dir > 0)? np->uln_next : np->uln_prev; wp->ulw_next_result = next; return (np); } static void list_walk_fini(uu_list_walk_t *wp) { /* GLXXX debugging? */ if (wp->ulw_next != NULL) { wp->ulw_next->ulw_prev = wp->ulw_prev; wp->ulw_prev->ulw_next = wp->ulw_next; wp->ulw_next = NULL; wp->ulw_prev = NULL; } wp->ulw_list = NULL; wp->ulw_next_result = NULL; } uu_list_walk_t * uu_list_walk_start(uu_list_t *lp, uint32_t flags) { uu_list_walk_t *wp; if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (NULL); } wp = uu_zalloc(sizeof (*wp)); if (wp == NULL) { uu_set_error(UU_ERROR_NO_MEMORY); return (NULL); } list_walk_init(wp, lp, flags); return (wp); } void * uu_list_walk_next(uu_list_walk_t *wp) { uu_list_t *lp = wp->ulw_list; uu_list_node_impl_t *np = list_walk_advance(wp, lp); if (np == NULL) return (NULL); return (NODE_TO_ELEM(lp, np)); } void uu_list_walk_end(uu_list_walk_t *wp) { list_walk_fini(wp); uu_free(wp); } int uu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags) { uu_list_node_impl_t *np; int status = UU_WALK_NEXT; int robust = (flags & UU_WALK_ROBUST); int reverse = (flags & UU_WALK_REVERSE); if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { uu_set_error(UU_ERROR_UNKNOWN_FLAG); return (-1); } if (lp->ul_debug || robust) { uu_list_walk_t my_walk; void *e; list_walk_init(&my_walk, lp, flags); while (status == UU_WALK_NEXT && (e = uu_list_walk_next(&my_walk)) != NULL) status = (*func)(e, private); list_walk_fini(&my_walk); } else { if (!reverse) { for (np = lp->ul_null_node.uln_next; status == UU_WALK_NEXT && np != &lp->ul_null_node; np = np->uln_next) { status = (*func)(NODE_TO_ELEM(lp, np), private); } } else { for (np = lp->ul_null_node.uln_prev; status == UU_WALK_NEXT && np != &lp->ul_null_node; np = np->uln_prev) { status = (*func)(NODE_TO_ELEM(lp, np), private); } } } if (status >= 0) return (0); uu_set_error(UU_ERROR_CALLBACK_FAILED); return (-1); } void uu_list_remove(uu_list_t *lp, void *elem) { uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem); uu_list_walk_t *wp; if (lp->ul_debug) { if (np->uln_prev == NULL) uu_panic("uu_list_remove(%p, %p): elem not on list\n", (void *)lp, elem); /* * invalidate outstanding uu_list_index_ts. */ lp->ul_index = INDEX_NEXT(lp->ul_index); } /* * robust walkers must be advanced. In debug mode, non-robust * walkers are also on the list. If there are any, it's an error. */ for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk; wp = wp->ulw_next) { if (wp->ulw_robust) { if (np == wp->ulw_next_result) (void) list_walk_advance(wp, lp); } else if (wp->ulw_next_result != NULL) { uu_panic("uu_list_remove(%p, %p): active non-robust " "walker\n", (void *)lp, elem); } } np->uln_next->uln_prev = np->uln_prev; np->uln_prev->uln_next = np->uln_next; lp->ul_numnodes--; np->uln_next = POOL_TO_MARKER(lp->ul_pool); np->uln_prev = NULL; } void * uu_list_teardown(uu_list_t *lp, void **cookie) { void *ep; /* * XXX: disable list modification until list is empty */ if (lp->ul_debug && *cookie != NULL) uu_panic("uu_list_teardown(%p, %p): unexpected cookie\n", (void *)lp, (void *)cookie); ep = uu_list_first(lp); if (ep) uu_list_remove(lp, ep); return (ep); } int uu_list_insert_before(uu_list_t *lp, void *target, void *elem) { uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); if (target == NULL) np = &lp->ul_null_node; if (lp->ul_debug) { if (np->uln_prev == NULL) uu_panic("uu_list_insert_before(%p, %p, %p): %p is " "not currently on a list\n", (void *)lp, target, elem, target); } if (lp->ul_sorted) { if (lp->ul_debug) uu_panic("uu_list_insert_before(%p, ...): list is " "UU_LIST_SORTED\n", (void *)lp); uu_set_error(UU_ERROR_NOT_SUPPORTED); return (-1); } list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); return (0); } int uu_list_insert_after(uu_list_t *lp, void *target, void *elem) { uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); if (target == NULL) np = &lp->ul_null_node; if (lp->ul_debug) { if (np->uln_prev == NULL) uu_panic("uu_list_insert_after(%p, %p, %p): %p is " "not currently on a list\n", (void *)lp, target, elem, target); } if (lp->ul_sorted) { if (lp->ul_debug) uu_panic("uu_list_insert_after(%p, ...): list is " "UU_LIST_SORTED\n", (void *)lp); uu_set_error(UU_ERROR_NOT_SUPPORTED); return (-1); } list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next); return (0); } size_t uu_list_numnodes(uu_list_t *lp) { return (lp->ul_numnodes); } void * uu_list_first(uu_list_t *lp) { uu_list_node_impl_t *n = lp->ul_null_node.uln_next; if (n == &lp->ul_null_node) return (NULL); return (NODE_TO_ELEM(lp, n)); } void * uu_list_last(uu_list_t *lp) { uu_list_node_impl_t *n = lp->ul_null_node.uln_prev; if (n == &lp->ul_null_node) return (NULL); return (NODE_TO_ELEM(lp, n)); } void * uu_list_next(uu_list_t *lp, void *elem) { uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); n = n->uln_next; if (n == &lp->ul_null_node) return (NULL); return (NODE_TO_ELEM(lp, n)); } void * uu_list_prev(uu_list_t *lp, void *elem) { uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); n = n->uln_prev; if (n == &lp->ul_null_node) return (NULL); return (NODE_TO_ELEM(lp, n)); } /* * called from uu_lockup() and uu_release(), as part of our fork1()-safety. */ void uu_list_lockup(void) { uu_list_pool_t *pp; (void) pthread_mutex_lock(&uu_lpool_list_lock); for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; pp = pp->ulp_next) (void) pthread_mutex_lock(&pp->ulp_lock); } void uu_list_release(void) { uu_list_pool_t *pp; for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; pp = pp->ulp_next) (void) pthread_mutex_unlock(&pp->ulp_lock); (void) pthread_mutex_unlock(&uu_lpool_list_lock); }