Index: conf/files =================================================================== RCS file: /cvs/src/sys/conf/files,v retrieving revision 1.620 diff -u -p -r1.620 files --- conf/files 17 Jun 2016 19:20:19 -0000 1.620 +++ conf/files 28 Jul 2016 04:10:40 -0000 @@ -688,6 +688,7 @@ file kern/subr_hibernate.c hibernate file kern/subr_log.c file kern/subr_poison.c diagnostic file kern/subr_pool.c +file kern/subr_rbtree.c file kern/dma_alloc.c file kern/subr_prf.c file kern/subr_prof.c Index: kern/subr_pool.c =================================================================== RCS file: /cvs/src/sys/kern/subr_pool.c,v retrieving revision 1.194 diff -u -p -r1.194 subr_pool.c --- kern/subr_pool.c 15 Jan 2016 11:21:58 -0000 1.194 +++ kern/subr_pool.c 28 Jul 2016 04:10:41 -0000 @@ -79,8 +79,7 @@ struct pool_item_header { TAILQ_ENTRY(pool_item_header) ph_pagelist; /* pool page list */ XSIMPLEQ_HEAD(,pool_item) ph_itemlist; /* chunk list for this page */ - RB_ENTRY(pool_item_header) - ph_node; /* Off-page page headers */ + struct rb_entry ph_node; /* Off-page page headers */ int ph_nmissing; /* # of chunks in use */ caddr_t ph_page; /* this page's address */ caddr_t ph_colored; /* page's colored address */ @@ -165,11 +164,13 @@ struct task pool_gc_task = TASK_INITIALI int pool_wait_free = 1; int pool_wait_gc = 8; -static inline int -phtree_compare(struct pool_item_header *a, struct pool_item_header *b) +int phtree_compare(const void *, const void *); + +int +phtree_compare(const void *a, const void *b) { - vaddr_t va = (vaddr_t)a->ph_page; - vaddr_t vb = (vaddr_t)b->ph_page; + vaddr_t va = (vaddr_t)((struct pool_item_header *)a)->ph_page; + vaddr_t vb = (vaddr_t)((struct pool_item_header *)b)->ph_page; /* the compares in this order are important for the NFIND to work */ if (vb < va) @@ -180,9 +181,6 @@ phtree_compare(struct pool_item_header * return (0); } -RB_PROTOTYPE(phtree, pool_item_header, ph_node, phtree_compare); -RB_GENERATE(phtree, pool_item_header, ph_node, phtree_compare); - /* * Return the pool page header based on page address. */ @@ -200,7 +198,7 @@ pr_find_pagehead(struct pool *pp, void * } key.ph_page = v; - ph = RB_NFIND(phtree, &pp->pr_phtree, &key); + ph = rb_nfind(&pp->pr_phtree, &key); if (ph == NULL) panic("%s: %s: page header missing", __func__, pp->pr_wchan); @@ -292,7 +290,8 @@ pool_init(struct pool *pp, size_t size, pp->pr_hardlimit_ratecap.tv_usec = 0; pp->pr_hardlimit_warning_last.tv_sec = 0; pp->pr_hardlimit_warning_last.tv_usec = 0; - RB_INIT(&pp->pr_phtree); + rb_init(&pp->pr_phtree, phtree_compare, + offsetof(struct pool_item_header, ph_node)); /* * Use the space between the chunks and the page header @@ -847,7 +846,7 @@ pool_p_insert(struct pool *pp, struct po TAILQ_INSERT_TAIL(&pp->pr_emptypages, ph, ph_pagelist); if (!POOL_INPGHDR(pp)) - RB_INSERT(phtree, &pp->pr_phtree, ph); + rb_insert(&pp->pr_phtree, ph); pp->pr_nitems += pp->pr_itemsperpage; pp->pr_nidle++; @@ -868,7 +867,7 @@ pool_p_remove(struct pool *pp, struct po pp->pr_nitems -= pp->pr_itemsperpage; if (!POOL_INPGHDR(pp)) - RB_REMOVE(phtree, &pp->pr_phtree, ph); + rb_remove(&pp->pr_phtree, ph); TAILQ_REMOVE(&pp->pr_emptypages, ph, ph_pagelist); pool_update_curpage(pp); Index: kern/subr_rbtree.c =================================================================== RCS file: kern/subr_rbtree.c diff -N kern/subr_rbtree.c --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ kern/subr_rbtree.c 28 Jul 2016 04:10:41 -0000 @@ -0,0 +1,565 @@ +/* $OpenBSD */ + +/* + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright (c) 2016 David Gwynne + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include + +#define RB_BLACK 0x0 +#define RB_RED 0x1 + +static inline void * +rb_n2e(struct rb_tree *rbt, void *node) +{ + caddr_t addr = (caddr_t)node; + + return ((void *)(addr + rbt->rbt_entry)); +} + +static inline void * +rb_e2n(struct rb_tree *rbt, struct rb_entry *rbe) +{ + caddr_t addr = (caddr_t)rbe; + + return ((void *)(addr - rbt->rbt_entry)); +} + +#define RBE_LEFT(_rbe) (_rbe)->rbe_left +#define RBE_RIGHT(_rbe) (_rbe)->rbe_right +#define RBE_PARENT(_rbe) (_rbe)->rbe_parent +#define RBE_COLOR(_rbe) (_rbe)->rbe_color + +#define RBT_ROOT(_rbt) (_rbt)->rbt_root + +static inline void +rbe_set(struct rb_entry *rbe, struct rb_entry *parent) +{ + RBE_PARENT(rbe) = parent; + RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; + RBE_COLOR(rbe) = RB_RED; +} + +static inline void +rbe_set_blackred(struct rb_entry *black, struct rb_entry *red) +{ + RBE_COLOR(black) = RB_BLACK; + RBE_COLOR(red) = RB_RED; +} + +static inline void +rbe_rotate_left(struct rb_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_RIGHT(rbe); + RBE_RIGHT(rbe) = RBE_LEFT(tmp); + if (RBE_RIGHT(rbe) != NULL) + RBE_PARENT(RBE_LEFT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBT_ROOT(rbt) = tmp; + + RBE_LEFT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; +} + +static inline void +rbe_rotate_right(struct rb_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_LEFT(rbe); + RBE_LEFT(rbe) = RBE_RIGHT(tmp); + if (RBE_LEFT(rbe) != NULL) + RBE_PARENT(RBE_RIGHT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBT_ROOT(rbt) = tmp; + + RBE_RIGHT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; +} + +static inline void +rbe_insert_color(struct rb_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *parent, *gparent, *tmp; + + while ((parent = RBE_PARENT(rbe)) != NULL && + RBE_COLOR(parent) == RB_RED) { + gparent = RBE_PARENT(parent); + + if (parent == RBE_LEFT(gparent)) { + tmp = RBE_RIGHT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_RIGHT(parent) == rbe) { + rbe_rotate_left(rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_right(rbt, gparent); + } else { + tmp = RBE_LEFT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_LEFT(parent) == rbe) { + rbe_rotate_right(rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_left(rbt, gparent); + } + } + + RBE_COLOR(RBT_ROOT(rbt)) = RB_BLACK; +} + +static inline void +rbe_remove_color(struct rb_tree *rbt, struct rb_entry *parent, + struct rb_entry *rbe) +{ + struct rb_entry *tmp; + + while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) && + rbe != RBT_ROOT(rbt)) { + if (RBE_LEFT(parent) == rbe) { + tmp = RBE_RIGHT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_left(rbt, parent); + tmp = RBE_RIGHT(parent); + } + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) { + struct rb_entry *oleft; + + oleft = RBE_LEFT(tmp); + if (oleft != NULL) + RBE_COLOR(oleft) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_right(rbt, tmp); + tmp = RBE_RIGHT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_RIGHT(tmp)) + RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK; + + rbe_rotate_left(rbt, parent); + rbe = RBT_ROOT(rbt); + break; + } + } else { + tmp = RBE_LEFT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_right(rbt, parent); + tmp = RBE_LEFT(parent); + } + + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) { + struct rb_entry *oright; + + oright = RBE_RIGHT(tmp); + if (oright != NULL) + RBE_COLOR(oright) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_left(rbt, tmp); + tmp = RBE_LEFT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_LEFT(tmp) != NULL) + RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK; + + rbe_rotate_right(rbt, parent); + rbe = RBT_ROOT(rbt); + break; + } + } + } + + if (rbe != NULL) + RBE_COLOR(rbe) = RB_BLACK; +} + +void +rb_init(struct rb_tree *rbt, int (*cmp)(const void *, const void *), + size_t offset) +{ + rbt->rbt_root = NULL; + rbt->rbt_cmp = cmp; + rbt->rbt_entry = offset; +} + +static inline struct rb_entry * +rbe_remove(struct rb_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *child, *parent, *old = rbe; + unsigned int color; + + if (RBE_LEFT(rbe) == NULL) + child = RBE_RIGHT(rbe); + else if (RBE_RIGHT(rbe) == NULL) + child = RBE_LEFT(rbe); + else { + struct rb_entry *tmp; + + rbe = RBE_RIGHT(rbe); + while ((tmp = RBE_LEFT(rbe)) != NULL) + rbe = tmp; + + child = RBE_RIGHT(rbe); + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + } else + RBT_ROOT(rbt) = child; + if (RBE_PARENT(rbe) == old) + parent = rbe; + *rbe = *old; + + tmp = RBE_PARENT(old); + if (tmp != NULL) { + if (RBE_LEFT(tmp) == old) + RBE_LEFT(tmp) = rbe; + else + RBE_RIGHT(tmp) = rbe; + } else + RBT_ROOT(rbt) = rbe; + + RBE_PARENT(RBE_LEFT(old)) = rbe; + if (RBE_RIGHT(old)) + RBE_PARENT(RBE_RIGHT(old)) = rbe; + + goto color; + } + + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + } else + RBT_ROOT(rbt) = child; +color: + if (color == RB_BLACK) + rbe_remove_color(rbt, parent, child); + + return (old); +} + +void * +rb_remove(struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(rbt, elm); + struct rb_entry *old; + + old = rbe_remove(rbt, rbe); + + return (old == NULL ? NULL : rb_e2n(rbt, old)); +} + +void * +rb_insert(struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(rbt, elm); + struct rb_entry *tmp; + struct rb_entry *parent = NULL; + void *node; + int comp = 0; + + tmp = RBT_ROOT(rbt); + while (tmp != NULL) { + parent = tmp; + + node = rb_e2n(rbt, tmp); + comp = (*rbt->rbt_cmp)(elm, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + rbe_set(rbe, parent); + + if (parent != NULL) { + if (comp < 0) + RBE_LEFT(parent) = rbe; + else + RBE_RIGHT(parent) = rbe; + } else + RBT_ROOT(rbt) = rbe; + + rbe_insert_color(rbt, rbe); + + return (NULL); +} + +/* Finds the node with the same key as elm */ +void * +rb_find(struct rb_tree *rbt, void *elm) +{ + struct rb_entry *tmp = RBT_ROOT(rbt); + void *node; + int comp; + + while (tmp != NULL) { + node = rb_e2n(rbt, tmp); + comp = (*rbt->rbt_cmp)(elm, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (NULL); +} + +/* Finds the first node greater than or equal to the search key */ \ +void * +rb_nfind(struct rb_tree *rbt, void *elm) +{ + struct rb_entry *tmp = RBT_ROOT(rbt); + void *node; + void *res = NULL; + int comp; + + while (tmp != NULL) { + node = rb_e2n(rbt, tmp); + comp = (*rbt->rbt_cmp)(elm, node); + if (comp < 0) { + res = node; + tmp = RBE_LEFT(tmp); + } else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (res); +} + +void * +rb_next(struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(rbt, elm); + + if (RBE_RIGHT(rbe) != NULL) { + rbe = RBE_RIGHT(rbe); + while (RBE_LEFT(rbe) != NULL) + rbe = RBE_LEFT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(rbt, rbe)); +} + + +void * +rb_pref(struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(rbt, elm); + + if (RBE_LEFT(rbe)) { + rbe = RBE_LEFT(rbe); + while (RBE_RIGHT(rbe)) + rbe = RBE_RIGHT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(rbt, rbe)); +} + +void * +rb_root(struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBT_ROOT(rbt); + + return (rbe == NULL ? rbe : rb_e2n(rbt, rbe)); +} + +int +rb_empty(struct rb_tree *rbt) +{ + return (RBT_ROOT(rbt) == NULL); +} + +void * +rb_min(struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBT_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_LEFT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(rbt, parent)); +} + +void * +rb_max(struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBT_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_RIGHT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(rbt, parent)); +} + +void * +rb_left(struct rb_tree *rbt, void *node) +{ + struct rb_entry *rbe = rb_n2e(rbt, node); + rbe = RBE_LEFT(rbe); + return (rbe == NULL ? NULL : rb_e2n(rbt, rbe)); +} + +void * +rb_right(struct rb_tree *rbt, void *node) +{ + struct rb_entry *rbe = rb_n2e(rbt, node); + rbe = RBE_RIGHT(rbe); + return (rbe == NULL ? NULL : rb_e2n(rbt, rbe)); +} + +void * +rb_parent(struct rb_tree *rbt, void *node) +{ + struct rb_entry *rbe = rb_n2e(rbt, node); + rbe = RBE_PARENT(rbe); + return (rbe == NULL ? NULL : rb_e2n(rbt, rbe)); +} + Index: kern/vfs_bio.c =================================================================== RCS file: /cvs/src/sys/kern/vfs_bio.c,v retrieving revision 1.175 diff -u -p -r1.175 vfs_bio.c --- kern/vfs_bio.c 7 Jun 2016 01:31:54 -0000 1.175 +++ kern/vfs_bio.c 28 Jul 2016 04:10:41 -0000 @@ -248,8 +248,7 @@ bufadjust(int newbufpages) (bcstats.numbufpages > targetpages)) { bufcache_take(bp); if (bp->b_vp) { - RB_REMOVE(buf_rb_bufs, - &bp->b_vp->v_bufs_tree, bp); + rb_remove(&bp->b_vp->v_bufs_tree, bp); brelvp(bp); } buf_put(bp); @@ -766,8 +765,7 @@ brelse(struct buf *bp) } if (bp->b_vp) { - RB_REMOVE(buf_rb_bufs, &bp->b_vp->v_bufs_tree, - bp); + rb_remove(&bp->b_vp->v_bufs_tree, bp); brelvp(bp); } bp->b_vp = NULL; @@ -834,7 +832,7 @@ incore(struct vnode *vp, daddr_t blkno) /* Search buf lookup tree */ b.b_lblkno = blkno; - bp = RB_FIND(buf_rb_bufs, &vp->v_bufs_tree, &b); + bp = rb_find(&vp->v_bufs_tree, &b); if (bp != NULL && ISSET(bp->b_flags, B_INVAL)) bp = NULL; @@ -870,7 +868,7 @@ getblk(struct vnode *vp, daddr_t blkno, start: s = splbio(); b.b_lblkno = blkno; - bp = RB_FIND(buf_rb_bufs, &vp->v_bufs_tree, &b); + bp = rb_find(&vp->v_bufs_tree, &b); if (bp != NULL) { if (ISSET(bp->b_flags, B_BUSY)) { SET(bp->b_flags, B_WANTED); @@ -953,8 +951,7 @@ buf_get(struct vnode *vp, daddr_t blkno, (bp = bufcache_getanycleanbuf())) { bufcache_take(bp); if (bp->b_vp) { - RB_REMOVE(buf_rb_bufs, - &bp->b_vp->v_bufs_tree, bp); + rb_remove(&bp->b_vp->v_bufs_tree, bp); brelvp(bp); } buf_put(bp); @@ -1014,7 +1011,7 @@ buf_get(struct vnode *vp, daddr_t blkno, bp->b_blkno = bp->b_lblkno = blkno; bgetvp(vp, bp); - if (RB_INSERT(buf_rb_bufs, &vp->v_bufs_tree, bp)) + if (rb_insert(&vp->v_bufs_tree, bp) != NULL) panic("buf_get: dup lblk vp %p bp %p", vp, bp); } else { bp->b_vnbufs.le_next = NOLIST; @@ -1513,8 +1510,7 @@ hibernate_suspend_bufcache(void) while ((bp = bufcache_getcleanbuf_range(DMA_CACHE, NUM_CACHES - 1, 1))) { bufcache_take(bp); if (bp->b_vp) { - RB_REMOVE(buf_rb_bufs, - &bp->b_vp->v_bufs_tree, bp); + rb_remove(&bp->b_vp->v_bufs_tree, bp); brelvp(bp); } buf_put(bp); Index: kern/vfs_cache.c =================================================================== RCS file: /cvs/src/sys/kern/vfs_cache.c,v retrieving revision 1.49 diff -u -p -r1.49 vfs_cache.c --- kern/vfs_cache.c 19 Mar 2016 12:04:15 -0000 1.49 +++ kern/vfs_cache.c 28 Jul 2016 04:10:41 -0000 @@ -73,17 +73,6 @@ struct pool nch_pool; void cache_zap(struct namecache *); u_long nextvnodeid; -static int -namecache_compare(struct namecache *n1, struct namecache *n2) -{ - if (n1->nc_nlen == n2->nc_nlen) - return (memcmp(n1->nc_name, n2->nc_name, n1->nc_nlen)); - else - return (n1->nc_nlen - n2->nc_nlen); -} - -RB_GENERATE(namecache_rb_cache, namecache, n_rbcache, namecache_compare); - /* * blow away a namecache entry */ @@ -100,8 +89,8 @@ cache_zap(struct namecache *ncp) numneg--; } if (ncp->nc_dvp) { - RB_REMOVE(namecache_rb_cache, &ncp->nc_dvp->v_nc_tree, ncp); - if (RB_EMPTY(&ncp->nc_dvp->v_nc_tree)) + rb_remove(&ncp->nc_dvp->v_nc_tree, ncp); + if (rb_empty(&ncp->nc_dvp->v_nc_tree)) dvp = ncp->nc_dvp; } if (ncp->nc_vp && (ncp->nc_vpid == ncp->nc_vp->v_id)) { @@ -157,7 +146,7 @@ cache_lookup(struct vnode *dvp, struct v /* lookup in directory vnode's redblack tree */ n.nc_nlen = cnp->cn_namelen; memcpy(n.nc_name, cnp->cn_nameptr, n.nc_nlen); - ncp = RB_FIND(namecache_rb_cache, &dvp->v_nc_tree, &n); + ncp = rb_find(&dvp->v_nc_tree, &n); if (ncp == NULL) { nchstats.ncs_miss++; @@ -368,10 +357,10 @@ cache_enter(struct vnode *dvp, struct vn ncp->nc_dvpid = dvp->v_id; ncp->nc_nlen = cnp->cn_namelen; memcpy(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen); - if (RB_EMPTY(&dvp->v_nc_tree)) { + if (rb_empty(&dvp->v_nc_tree)) { vhold(dvp); } - if ((lncp = RB_INSERT(namecache_rb_cache, &dvp->v_nc_tree, ncp)) + if ((lncp = rb_insert(&dvp->v_nc_tree, ncp)) != NULL) { /* someone has raced us and added a different entry * for the same vnode (different ncp) - we don't need @@ -435,7 +424,7 @@ cache_purge(struct vnode *vp) while ((ncp = TAILQ_FIRST(&vp->v_cache_dst))) cache_zap(ncp); - while ((ncp = RB_ROOT(&vp->v_nc_tree))) + while ((ncp = rb_root(&vp->v_nc_tree))) cache_zap(ncp); /* XXX this blows goats */ Index: kern/vfs_subr.c =================================================================== RCS file: /cvs/src/sys/kern/vfs_subr.c,v retrieving revision 1.249 diff -u -p -r1.249 vfs_subr.c --- kern/vfs_subr.c 22 Jul 2016 09:54:09 -0000 1.249 +++ kern/vfs_subr.c 28 Jul 2016 04:10:41 -0000 @@ -122,17 +122,33 @@ void printlockedvnodes(void); struct pool vnode_pool; struct pool uvm_vnode_pool; -static int rb_buf_compare(struct buf *b1, struct buf *b2); -RB_GENERATE(buf_rb_bufs, buf, b_rbbufs, rb_buf_compare); +static int rb_buf_compare(const void *, const void *); +static int namecache_compare(const void *, const void *); static int -rb_buf_compare(struct buf *b1, struct buf *b2) +rb_buf_compare(const void *a, const void *b) { - if (b1->b_lblkno < b2->b_lblkno) - return(-1); + const struct buf *b1 = a, *b2 = b; + if (b1->b_lblkno > b2->b_lblkno) - return(1); - return(0); + return (1); + if (b1->b_lblkno < b2->b_lblkno) + return (-1); + + return (0); +} + +static int +namecache_compare(const void *a, const void *b) +{ + const struct namecache *n1 = a, *n2 = b; + + if (n1->nc_nlen > n2->nc_nlen) + return (1); + if (n1->nc_nlen < n2->nc_nlen) + return (-1); + + return (memcmp(n1->nc_name, n2->nc_name, n1->nc_nlen)); } /* @@ -375,8 +391,10 @@ getnewvnode(enum vtagtype tag, struct mo vp = pool_get(&vnode_pool, PR_WAITOK | PR_ZERO); vp->v_uvm = pool_get(&uvm_vnode_pool, PR_WAITOK | PR_ZERO); vp->v_uvm->u_vnode = vp; - RB_INIT(&vp->v_bufs_tree); - RB_INIT(&vp->v_nc_tree); + rb_init(&vp->v_bufs_tree, rb_buf_compare, + offsetof(struct buf, b_rbbufs)); + rb_init(&vp->v_nc_tree, namecache_compare, + offsetof(struct namecache, n_rbcache)); TAILQ_INIT(&vp->v_cache_dst); numvnodes++; } else { Index: net/if_pfsync.c =================================================================== RCS file: /cvs/src/sys/net/if_pfsync.c,v retrieving revision 1.229 diff -u -p -r1.229 if_pfsync.c --- net/if_pfsync.c 29 Apr 2016 08:55:03 -0000 1.229 +++ net/if_pfsync.c 28 Jul 2016 04:10:41 -0000 @@ -749,8 +749,8 @@ pfsync_in_clr(caddr_t buf, int len, int (kif = pfi_kif_find(clr->ifname)) == NULL) continue; - for (st = RB_MIN(pf_state_tree_id, &tree_id); st; st = nexts) { - nexts = RB_NEXT(pf_state_tree_id, &tree_id, st); + for (st = rb_min(&tree_id); st; st = nexts) { + nexts = rb_next(&tree_id, st); if (st->creatorid == creatorid && ((kif && st->kif == kif) || !kif)) { SET(st->state_flags, PFSTATE_NOSYNC); Index: net/if_pppx.c =================================================================== RCS file: /cvs/src/sys/net/if_pppx.c,v retrieving revision 1.51 diff -u -p -r1.51 if_pppx.c --- net/if_pppx.c 13 Apr 2016 11:41:15 -0000 1.51 +++ net/if_pppx.c 28 Jul 2016 04:10:41 -0000 @@ -50,6 +50,7 @@ #include #include #include +#include #include #include #include @@ -139,12 +140,12 @@ struct pppx_if_key { int pxik_protocol; }; -int pppx_if_cmp(struct pppx_if *, struct pppx_if *); +int pppx_if_cmp(const void *, const void *); struct pppx_if { struct pppx_if_key pxi_key; /* must be first in the struct */ - RB_ENTRY(pppx_if) pxi_entry; + struct rb_entry pxi_entry; LIST_ENTRY(pppx_if) pxi_list; int pxi_unit; @@ -155,8 +156,8 @@ struct pppx_if { }; struct rwlock pppx_ifs_lk = RWLOCK_INITIALIZER("pppxifs"); -RB_HEAD(pppx_ifs, pppx_if) pppx_ifs = RB_INITIALIZER(&pppx_ifs); -RB_PROTOTYPE(pppx_ifs, pppx_if, pxi_entry, pppx_if_cmp); +struct rb_tree pppx_ifs = RB_TREE_INITIALIZER(pppx_if_cmp, + offsetof(struct pppx_if, pxi_entry)); int pppx_if_next_unit(void); struct pppx_if *pppx_if_find(struct pppx_dev *, int, int); @@ -607,9 +608,11 @@ pppxclose(dev_t dev, int flags, int mode } int -pppx_if_cmp(struct pppx_if *a, struct pppx_if *b) +pppx_if_cmp(const void *a, const void *b) { - return memcmp(&a->pxi_key, &b->pxi_key, sizeof(a->pxi_key)); + const struct pppx_if *pa = a, *pb = b; + + return memcmp(&pa->pxi_key, &pb->pxi_key, sizeof(pa->pxi_key)); } int @@ -623,7 +626,7 @@ pppx_if_next_unit(void) /* this is safe without splnet since we're not modifying it */ do { int found = 0; - RB_FOREACH(pxi, pppx_ifs, &pppx_ifs) { + rb_foreach(pxi, &pppx_ifs) { if (pxi->pxi_unit == unit) { found = 1; break; @@ -648,7 +651,7 @@ pppx_if_find(struct pppx_dev *pxd, int s s->pxi_key.pxik_protocol = protocol; rw_enter_read(&pppx_ifs_lk); - p = RB_FIND(pppx_ifs, &pppx_ifs, s); + p = rb_find(&pppx_ifs, s); rw_exit_read(&pppx_ifs_lk); free(s, M_DEVBUF, 0); @@ -829,7 +832,7 @@ pppx_add_session(struct pppx_dev *pxd, s pxi->pxi_dev = pxd; /* this is safe without splnet since we're not modifying it */ - if (RB_FIND(pppx_ifs, &pppx_ifs, pxi) != NULL) { + if (rb_find(&pppx_ifs, pxi) != NULL) { pool_put(pppx_if_pl, pxi); error = EADDRINUSE; goto out; @@ -875,7 +878,7 @@ pppx_add_session(struct pppx_dev *pxd, s #endif SET(ifp->if_flags, IFF_RUNNING); - if (RB_INSERT(pppx_ifs, &pppx_ifs, pxi) != NULL) + if (rb_insert(&pppx_ifs, pxi) != NULL) panic("pppx_ifs modified while lock was held"); LIST_INSERT_HEAD(&pxd->pxd_pxis, pxi, pxi_list); @@ -983,7 +986,7 @@ pppx_if_destroy(struct pppx_dev *pxd, st if_detach(ifp); rw_enter_write(&pppx_ifs_lk); - if (RB_REMOVE(pppx_ifs, &pppx_ifs, pxi) == NULL) + if (rb_remove(&pppx_ifs, pxi) == NULL) panic("pppx_ifs modified while lock was held"); LIST_REMOVE(pxi, pxi_list); rw_exit_write(&pppx_ifs_lk); @@ -1126,5 +1129,3 @@ pppx_if_ioctl(struct ifnet *ifp, u_long return (error); } - -RB_GENERATE(pppx_ifs, pppx_if, pxi_entry, pppx_if_cmp); Index: net/pf.c =================================================================== RCS file: /cvs/src/sys/net/pf.c,v retrieving revision 1.979 diff -u -p -r1.979 pf.c --- net/pf.c 18 Jul 2016 13:17:44 -0000 1.979 +++ net/pf.c 28 Jul 2016 04:10:41 -0000 @@ -107,7 +107,7 @@ /* * Global variables */ -struct pf_state_tree pf_statetbl; +struct rb_tree pf_statetbl; struct pf_queuehead pf_queues[2]; struct pf_queuehead *pf_queues_active; struct pf_queuehead *pf_queues_inactive; @@ -122,7 +122,7 @@ int pf_tcp_iss_off; struct pf_anchor_stackframe { struct pf_ruleset *rs; struct pf_rule *r; - struct pf_anchor_node *parent; + struct rb_tree *parent; struct pf_anchor *child; } pf_anchor_stack[64]; @@ -288,24 +288,14 @@ struct pf_pool_limit pf_pool_limits[PF_L mrm->r->states_cur++; \ } while (0) -static __inline int pf_src_compare(struct pf_src_node *, struct pf_src_node *); -static __inline int pf_state_compare_key(struct pf_state_key *, - struct pf_state_key *); -static __inline int pf_state_compare_id(struct pf_state *, - struct pf_state *); +struct rb_tree tree_src_tracking; -struct pf_src_tree tree_src_tracking; - -struct pf_state_tree_id tree_id; +struct rb_tree tree_id; struct pf_state_queue state_list; -RB_GENERATE(pf_src_tree, pf_src_node, entry, pf_src_compare); -RB_GENERATE(pf_state_tree, pf_state_key, entry, pf_state_compare_key); -RB_GENERATE(pf_state_tree_id, pf_state, - entry_id, pf_state_compare_id); - -__inline int -pf_addr_compare(struct pf_addr *a, struct pf_addr *b, sa_family_t af) +int +pf_addr_compare(const struct pf_addr *a, const struct pf_addr *b, + sa_family_t af) { switch (af) { case AF_INET: @@ -338,10 +328,11 @@ pf_addr_compare(struct pf_addr *a, struc return (0); } -static __inline int -pf_src_compare(struct pf_src_node *a, struct pf_src_node *b) +int +pf_src_compare(const void *aptr, const void *bptr) { - int diff; + const struct pf_src_node *a = aptr, *b = bptr; + int diff; if (a->rule.ptr > b->rule.ptr) return (1); @@ -470,7 +461,7 @@ pf_src_connlimit(struct pf_state **state struct pf_state *st; pf_status.lcounters[LCNT_OVERLOAD_FLUSH]++; - RB_FOREACH(st, pf_state_tree_id, &tree_id) { + rb_foreach(st, &tree_id) { sk = st->key[PF_SK_WIRE]; /* * Kill states from this source. (Only those @@ -518,7 +509,7 @@ pf_insert_src_node(struct pf_src_node ** PF_ACPY(&k.addr, src, af); k.rule.ptr = rule; pf_status.scounters[SCNT_SRC_NODE_SEARCH]++; - *sn = RB_FIND(pf_src_tree, &tree_src_tracking, &k); + *sn = rb_find(&tree_src_tracking, &k); } if (*sn == NULL) { if (!rule->max_src_nodes || @@ -539,8 +530,7 @@ pf_insert_src_node(struct pf_src_node ** PF_ACPY(&(*sn)->addr, src, af); if (raddr) PF_ACPY(&(*sn)->raddr, raddr, af); - if (RB_INSERT(pf_src_tree, - &tree_src_tracking, *sn) != NULL) { + if (rb_insert(&tree_src_tracking, *sn) != NULL) { if (pf_status.debug >= LOG_NOTICE) { log(LOG_NOTICE, "pf: src_tree insert failed: "); @@ -574,7 +564,7 @@ pf_remove_src_node(struct pf_src_node *s if (sn->rule.ptr->states_cur == 0 && sn->rule.ptr->src_nodes == 0) pf_rm_rule(NULL, sn->rule.ptr); - RB_REMOVE(pf_src_tree, &tree_src_tracking, sn); + rb_remove(&tree_src_tracking, sn); pf_status.scounters[SCNT_SRC_NODE_REMOVALS]++; pf_status.src_nodes--; pool_put(&pf_src_tree_pl, sn); @@ -614,10 +604,11 @@ pf_state_rm_src_node(struct pf_state *s, /* state table stuff */ -static __inline int -pf_state_compare_key(struct pf_state_key *a, struct pf_state_key *b) +int +pf_state_compare_key(const void *aptr, const void *bptr) { - int diff; + const struct pf_state_key *a = aptr, *b = bptr; + int diff; if ((diff = a->proto - b->proto) != 0) return (diff); @@ -636,9 +627,11 @@ pf_state_compare_key(struct pf_state_key return (0); } -static __inline int -pf_state_compare_id(struct pf_state *a, struct pf_state *b) +int +pf_state_compare_id(const void *aptr, const void *bptr) { + const struct pf_state *a = aptr, *b = bptr; + if (a->id > b->id) return (1); if (a->id < b->id) @@ -659,7 +652,7 @@ pf_state_key_attach(struct pf_state_key struct pf_state *olds = NULL; KASSERT(s->key[idx] == NULL); - if ((cur = RB_INSERT(pf_state_tree, &pf_statetbl, sk)) != NULL) { + if ((cur = rb_insert(&pf_statetbl, sk)) != NULL) { /* key exists. check for same kif, if none, add to key */ TAILQ_FOREACH(si, &cur->states, entry) if (si->s->kif == s->kif && @@ -758,7 +751,7 @@ pf_state_key_detach(struct pf_state *s, sk = s->key[idx]; s->key[idx] = NULL; if (TAILQ_EMPTY(&sk->states)) { - RB_REMOVE(pf_state_tree, &pf_statetbl, sk); + rb_remove(&pf_statetbl, sk); sk->removed = 1; pf_state_key_unlink_reverse(sk); pf_inpcb_unlink_state_key(sk->inp); @@ -934,7 +927,7 @@ pf_state_insert(struct pfi_kif *kif, str s->id = htobe64(pf_status.stateid++); s->creatorid = pf_status.hostid; } - if (RB_INSERT(pf_state_tree_id, &tree_id, s) != NULL) { + if (rb_insert(&tree_id, s) != NULL) { if (pf_status.debug >= LOG_NOTICE) { log(LOG_NOTICE, "pf: state insert failed: " "id: %016llx creatorid: %08x", @@ -959,7 +952,7 @@ pf_find_state_byid(struct pf_state_cmp * { pf_status.fcounters[FCNT_STATE_SEARCH]++; - return (RB_FIND(pf_state_tree_id, &tree_id, (struct pf_state *)key)); + return (rb_find(&tree_id, (struct pf_state *)key)); } int @@ -1038,8 +1031,7 @@ pf_find_state(struct pfi_kif *kif, struc } if (sk == NULL) { - if ((sk = RB_FIND(pf_state_tree, &pf_statetbl, - (struct pf_state_key *)key)) == NULL) + if ((sk = rb_find(&pf_statetbl, key)) == NULL) return (NULL); if (dir == PF_OUT && pkt_sk && pf_compare_state_keys(pkt_sk, sk, kif, dir) == 0) @@ -1074,7 +1066,7 @@ pf_find_state_all(struct pf_state_key_cm pf_status.fcounters[FCNT_STATE_SEARCH]++; - sk = RB_FIND(pf_state_tree, &pf_statetbl, (struct pf_state_key *)key); + sk = rb_find(&pf_statetbl, key); if (sk != NULL) { TAILQ_FOREACH(si, &sk->states, entry) @@ -1235,14 +1227,13 @@ pf_purge_expired_src_nodes(int waslocked struct pf_src_node *cur, *next; int locked = waslocked; - for (cur = RB_MIN(pf_src_tree, &tree_src_tracking); cur; cur = next) { - next = RB_NEXT(pf_src_tree, &tree_src_tracking, cur); + for (cur = rb_min(&tree_src_tracking); cur != NULL; cur = next) { + next = rb_next(&tree_src_tracking, cur); if (cur->states == 0 && cur->expire <= time_uptime) { if (! locked) { rw_enter_write(&pf_consistency_lock); - next = RB_NEXT(pf_src_tree, - &tree_src_tracking, cur); + next = rb_next(&tree_src_tracking, cur); locked = 1; } pf_remove_src_node(cur); @@ -1293,7 +1284,7 @@ pf_remove_state(struct pf_state *cur) TH_RST|TH_ACK, 0, 0, 0, 1, cur->tag, cur->key[PF_SK_WIRE]->rdomain); } - RB_REMOVE(pf_state_tree_id, &tree_id, cur); + rb_remove(&tree_id, cur); #if NPFLOW > 0 if (cur->state_flags & PFSTATE_PFLOW) export_pflow(cur); @@ -2672,7 +2663,7 @@ pf_step_into_anchor(int *depth, struct p f->r = *r; if ((*r)->anchor_wildcard) { f->parent = &(*r)->anchor->children; - if ((f->child = RB_MIN(pf_anchor_node, f->parent)) == NULL) { + if ((f->child = rb_min(f->parent)) == NULL) { *r = NULL; return; } @@ -2697,7 +2688,7 @@ pf_step_out_of_anchor(int *depth, struct break; f = pf_anchor_stack + *depth - 1; if (f->parent != NULL && f->child != NULL) { - f->child = RB_NEXT(pf_anchor_node, f->parent, f->child); + f->child = rb_next(f->parent, f->child); if (f->child != NULL) { *rs = &f->child->ruleset; *r = TAILQ_FIRST((*rs)->rules.active.ptr); Index: net/pf_if.c =================================================================== RCS file: /cvs/src/sys/net/pf_if.c,v retrieving revision 1.82 diff -u -p -r1.82 pf_if.c --- net/pf_if.c 20 Nov 2015 03:35:23 -0000 1.82 +++ net/pf_if.c 28 Jul 2016 04:10:41 -0000 @@ -59,7 +59,7 @@ struct pfi_kif *pfi_all = NULL; struct pool pfi_addr_pl; -struct pfi_ifhead pfi_ifs; +struct rb_tree pfi_ifs; long pfi_update = 1; struct pfr_addr *pfi_buffer; int pfi_buffer_cnt; @@ -72,13 +72,10 @@ void pfi_table_update(struct pfr_ktabl void pfi_kifaddr_update(void *); void pfi_instance_add(struct ifnet *, u_int8_t, int); void pfi_address_add(struct sockaddr *, sa_family_t, u_int8_t); -int pfi_if_compare(struct pfi_kif *, struct pfi_kif *); +int pfi_if_compare(const void *, const void *); int pfi_skip_if(const char *, struct pfi_kif *); int pfi_unmask(void *); -RB_PROTOTYPE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare); -RB_GENERATE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare); - #define PFI_BUFFER_MAX 0x10000 #define PFI_MTYPE M_IFADDR @@ -94,6 +91,8 @@ pfi_initialize(void) pfi_buffer = mallocarray(pfi_buffer_max, sizeof(*pfi_buffer), PFI_MTYPE, M_WAITOK); + rb_init(&pfi_ifs, pfi_if_compare, offsetof(struct pfi_kif, pfik_tree)); + if ((pfi_all = pfi_kif_get(IFG_ALL)) == NULL) panic("pfi_kif_get for pfi_all failed"); } @@ -105,7 +104,7 @@ pfi_kif_find(const char *kif_name) bzero(&s, sizeof(s)); strlcpy(s.pfik_name, kif_name, sizeof(s.pfik_name)); - return (RB_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&s)); + return (rb_find(&pfi_ifs, (struct pfi_kif *)&s)); } struct pfi_kif * @@ -130,7 +129,7 @@ pfi_kif_get(const char *kif_name) kif->pfik_flags_new |= PFI_IFLAG_ANY; } - RB_INSERT(pfi_ifhead, &pfi_ifs, kif); + rb_insert(&pfi_ifs, kif); return (kif); } @@ -195,7 +194,7 @@ pfi_kif_unref(struct pfi_kif *kif, enum if (kif->pfik_rules || kif->pfik_states || kif->pfik_routes) return; - RB_REMOVE(pfi_ifhead, &pfi_ifs, kif); + rb_remove(&pfi_ifs, kif); free(kif, PFI_MTYPE, 0); } @@ -628,8 +627,10 @@ pfi_kifaddr_update(void *v) } int -pfi_if_compare(struct pfi_kif *p, struct pfi_kif *q) +pfi_if_compare(const void *aptr, const void *bptr) { + const struct pfi_kif *p = aptr, *q = bptr; + return (strncmp(p->pfik_name, q->pfik_name, IFNAMSIZ)); } @@ -644,7 +645,7 @@ pfi_update_status(const char *name, stru s = splsoftnet(); if (*name == '\0' && pfs == NULL) { - RB_FOREACH(p, pfi_ifhead, &pfi_ifs) { + rb_foreach (p, &pfi_ifs) { bzero(p->pfik_packets, sizeof(p->pfik_packets)); bzero(p->pfik_bytes, sizeof(p->pfik_bytes)); p->pfik_tzero = time_second; @@ -654,7 +655,7 @@ pfi_update_status(const char *name, stru } strlcpy(key.pfik_name, name, sizeof(key.pfik_name)); - p = RB_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&key); + p = rb_find(&pfi_ifs, (struct pfi_kif *)&key); if (p == NULL) { splx(s); return; @@ -704,8 +705,8 @@ pfi_get_ifaces(const char *name, struct int s, n = 0; s = splsoftnet(); - for (p = RB_MIN(pfi_ifhead, &pfi_ifs); p; p = nextp) { - nextp = RB_NEXT(pfi_ifhead, &pfi_ifs, p); + for (p = rb_min(&pfi_ifs); p; p = nextp) { + nextp = rb_next(&pfi_ifs, p); if (pfi_skip_if(name, p)) continue; if (*size > n++) { @@ -717,7 +718,7 @@ pfi_get_ifaces(const char *name, struct splx(s); return (EFAULT); } - nextp = RB_NEXT(pfi_ifhead, &pfi_ifs, p); + nextp = rb_next(&pfi_ifs, p); pfi_kif_unref(p, PFI_KIF_REF_RULE); } } @@ -755,7 +756,7 @@ pfi_set_flags(const char *name, int flag int s; s = splsoftnet(); - RB_FOREACH(p, pfi_ifhead, &pfi_ifs) { + rb_foreach (p, &pfi_ifs) { if (pfi_skip_if(name, p)) continue; p->pfik_flags_new = p->pfik_flags | flags; @@ -771,7 +772,7 @@ pfi_clear_flags(const char *name, int fl int s; s = splsoftnet(); - RB_FOREACH(p, pfi_ifhead, &pfi_ifs) { + rb_foreach (p, &pfi_ifs) { if (pfi_skip_if(name, p)) continue; p->pfik_flags_new = p->pfik_flags & ~flags; @@ -787,7 +788,7 @@ pfi_xcommit(void) int s; s = splsoftnet(); - RB_FOREACH(p, pfi_ifhead, &pfi_ifs) + rb_foreach (p, &pfi_ifs) p->pfik_flags = p->pfik_flags_new; splx(s); } Index: net/pf_ioctl.c =================================================================== RCS file: /cvs/src/sys/net/pf_ioctl.c,v retrieving revision 1.297 diff -u -p -r1.297 pf_ioctl.c --- net/pf_ioctl.c 3 Dec 2015 13:30:18 -0000 1.297 +++ net/pf_ioctl.c 28 Jul 2016 04:10:41 -0000 @@ -169,8 +169,12 @@ pfattach(int num) pf_pool_limits[PF_LIMIT_TABLE_ENTRIES].limit = PFR_KENTRY_HIWAT_SMALL; - RB_INIT(&tree_src_tracking); - RB_INIT(&pf_anchors); + rb_init(&pf_statetbl, pf_state_compare_key, + offsetof(struct pf_state_key, entry)); + rb_init(&tree_id, pf_state_compare_id, + offsetof(struct pf_state, entry_id)); + rb_init(&tree_src_tracking, pf_src_compare, + offsetof(struct pf_src_node, entry)); pf_init_ruleset(&pf_main_ruleset); TAILQ_INIT(&pf_queues[0]); TAILQ_INIT(&pf_queues[1]); @@ -1421,8 +1425,8 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a struct pfioc_state_kill *psk = (struct pfioc_state_kill *)addr; u_int killed = 0; - for (s = RB_MIN(pf_state_tree_id, &tree_id); s; s = nexts) { - nexts = RB_NEXT(pf_state_tree_id, &tree_id, s); + for (s = rb_min(&tree_id); s; s = nexts) { + nexts = rb_next(&tree_id, s); if (!psk->psk_ifname[0] || !strcmp(psk->psk_ifname, s->kif->pfik_name)) { @@ -1459,9 +1463,8 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a break; } - for (s = RB_MIN(pf_state_tree_id, &tree_id); s; - s = nexts) { - nexts = RB_NEXT(pf_state_tree_id, &tree_id, s); + for (s = rb_min(&tree_id); s; s = nexts) { + nexts = rb_next(&tree_id, s); if (s->direction == PF_OUT) { sk = s->key[PF_SK_STACK]; @@ -1757,12 +1760,11 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a pr->nr = 0; if (ruleset->anchor == NULL) { /* XXX kludge for pf_main_ruleset */ - RB_FOREACH(anchor, pf_anchor_global, &pf_anchors) + rb_foreach (anchor, &pf_anchors) if (anchor->parent == NULL) pr->nr++; } else { - RB_FOREACH(anchor, pf_anchor_node, - &ruleset->anchor->children) + rb_foreach (anchor, &ruleset->anchor->children) pr->nr++; } break; @@ -1782,15 +1784,14 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a pr->name[0] = 0; if (ruleset->anchor == NULL) { /* XXX kludge for pf_main_ruleset */ - RB_FOREACH(anchor, pf_anchor_global, &pf_anchors) + rb_foreach (anchor, &pf_anchors) if (anchor->parent == NULL && nr++ == pr->nr) { strlcpy(pr->name, anchor->name, sizeof(pr->name)); break; } } else { - RB_FOREACH(anchor, pf_anchor_node, - &ruleset->anchor->children) + rb_foreach (anchor, &ruleset->anchor->children) if (nr++ == pr->nr) { strlcpy(pr->name, anchor->name, sizeof(pr->name)); @@ -2239,7 +2240,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a int space = psn->psn_len; if (space == 0) { - RB_FOREACH(n, pf_src_tree, &tree_src_tracking) + rb_foreach (n, &tree_src_tracking) nr++; psn->psn_len = sizeof(struct pf_src_node) * nr; break; @@ -2248,7 +2249,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a pstore = malloc(sizeof(*pstore), M_TEMP, M_WAITOK); p = psn->psn_src_nodes; - RB_FOREACH(n, pf_src_tree, &tree_src_tracking) { + rb_foreach (n, &tree_src_tracking) { int secs = time_uptime, diff; if ((nr + 1) * sizeof(*p) > (unsigned)psn->psn_len) @@ -2292,9 +2293,9 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a struct pf_src_node *n; struct pf_state *state; - RB_FOREACH(state, pf_state_tree_id, &tree_id) + rb_foreach (state, &tree_id) pf_src_tree_remove_state(state); - RB_FOREACH(n, pf_src_tree, &tree_src_tracking) + rb_foreach (n, &tree_src_tracking) n->expire = 1; pf_purge_expired_src_nodes(1); break; @@ -2307,7 +2308,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a (struct pfioc_src_node_kill *)addr; u_int killed = 0; - RB_FOREACH(sn, pf_src_tree, &tree_src_tracking) { + rb_foreach (sn, &tree_src_tracking) { if (PF_MATCHA(psnk->psnk_src.neg, &psnk->psnk_src.addr.v.a.addr, &psnk->psnk_src.addr.v.a.mask, @@ -2318,8 +2319,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a &sn->raddr, sn->af)) { /* Handle state to src_node linkage */ if (sn->states != 0) - RB_FOREACH(s, pf_state_tree_id, - &tree_id) + rb_foreach (s, &tree_id) pf_state_rm_src_node(s, sn); sn->expire = 1; killed++; Index: net/pf_lb.c =================================================================== RCS file: /cvs/src/sys/net/pf_lb.c,v retrieving revision 1.55 diff -u -p -r1.55 pf_lb.c --- net/pf_lb.c 19 Jul 2016 12:51:19 -0000 1.55 +++ net/pf_lb.c 28 Jul 2016 04:10:41 -0000 @@ -275,7 +275,7 @@ pf_map_addr_sticky(sa_family_t af, struc PF_ACPY(&k.addr, saddr, af); k.rule.ptr = r; pf_status.scounters[SCNT_SRC_NODE_SEARCH]++; - sns[type] = RB_FIND(pf_src_tree, &tree_src_tracking, &k); + sns[type] = rb_find(&tree_src_tracking, &k); if (sns[type] == NULL) return (-1); @@ -307,10 +307,8 @@ pf_map_addr_sticky(sa_family_t af, struc } if (sns[type]->states != 0) { /* XXX expensive */ - RB_FOREACH(s, pf_state_tree_id, - &tree_id) - pf_state_rm_src_node(s, - sns[type]); + rb_foreach(s, &tree_id) + pf_state_rm_src_node(s, sns[type]); } sns[type]->expire = 1; pf_remove_src_node(sns[type]); Index: net/pf_norm.c =================================================================== RCS file: /cvs/src/sys/net/pf_norm.c,v retrieving revision 1.188 diff -u -p -r1.188 pf_norm.c --- net/pf_norm.c 15 Jun 2016 11:49:34 -0000 1.188 +++ net/pf_norm.c 28 Jul 2016 04:10:41 -0000 @@ -74,7 +74,7 @@ struct pf_frent { u_int16_t fe_mff; /* more fragment flag */ }; -/* keep synced with struct pf_fragment, used in RB_FIND */ +/* keep synced with struct pf_fragment, used in rb_find */ struct pf_fragment_cmp { struct pf_addr fr_src; struct pf_addr fr_dst; @@ -92,7 +92,7 @@ struct pf_fragment { u_int8_t fr_proto; /* protocol of this fragment */ u_int8_t fr_direction; /* pf packet direction */ - RB_ENTRY(pf_fragment) fr_entry; + struct rb_entry fr_entry; TAILQ_ENTRY(pf_fragment) frag_next; TAILQ_HEAD(pf_fragq, pf_frent) fr_queue; int32_t fr_timeout; @@ -107,17 +107,13 @@ struct pf_fragment_tag { TAILQ_HEAD(pf_fragqueue, pf_fragment) pf_fragqueue; -static __inline int pf_frag_compare(struct pf_fragment *, - struct pf_fragment *); -RB_HEAD(pf_frag_tree, pf_fragment) pf_frag_tree, pf_cache_tree; -RB_PROTOTYPE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare); -RB_GENERATE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare); +int pf_frag_compare(const void *, const void *); /* Private prototypes */ void pf_flush_fragments(void); void pf_free_fragment(struct pf_fragment *); struct pf_fragment *pf_find_fragment(struct pf_fragment_cmp *, - struct pf_frag_tree *); + struct rb_tree *); struct pf_frent *pf_create_fragment(u_short *); struct pf_fragment *pf_fillup_fragment(struct pf_fragment_cmp *, struct pf_frent *, u_short *); @@ -133,6 +129,7 @@ int pf_reassemble6(struct mbuf **, st struct pool pf_frent_pl, pf_frag_pl; struct pool pf_state_scrub_pl; int pf_nfrents; +struct rb_tree pf_frag_tree, pf_cache_tree; void pf_normalize_init(void) @@ -147,12 +144,18 @@ pf_normalize_init(void) pool_sethiwat(&pf_frag_pl, PFFRAG_FRAG_HIWAT); pool_sethardlimit(&pf_frent_pl, PFFRAG_FRENT_HIWAT, NULL, 0); + rb_init(&pf_frag_tree, pf_frag_compare, + offsetof(struct pf_fragment, fr_entry)); + rb_init(&pf_cache_tree, pf_frag_compare, + offsetof(struct pf_fragment, fr_entry)); + TAILQ_INIT(&pf_fragqueue); } -static __inline int -pf_frag_compare(struct pf_fragment *a, struct pf_fragment *b) +int +pf_frag_compare(const void *aptr, const void *bptr) { + const struct pf_fragment *a = aptr, *b = bptr; int diff; if ((diff = a->fr_id - b->fr_id) != 0) @@ -211,7 +214,7 @@ pf_free_fragment(struct pf_fragment *fra { struct pf_frent *frent; - RB_REMOVE(pf_frag_tree, &pf_frag_tree, frag); + rb_remove(&pf_frag_tree, frag); TAILQ_REMOVE(&pf_fragqueue, frag, frag_next); /* Free all fragment entries */ @@ -225,11 +228,11 @@ pf_free_fragment(struct pf_fragment *fra } struct pf_fragment * -pf_find_fragment(struct pf_fragment_cmp *key, struct pf_frag_tree *tree) +pf_find_fragment(struct pf_fragment_cmp *key, struct rb_tree *tree) { struct pf_fragment *frag; - frag = RB_FIND(pf_frag_tree, tree, (struct pf_fragment *)key); + frag = rb_find(tree, key); if (frag != NULL) { TAILQ_REMOVE(&pf_fragqueue, frag, frag_next); TAILQ_INSERT_HEAD(&pf_fragqueue, frag, frag_next); @@ -309,7 +312,7 @@ pf_fillup_fragment(struct pf_fragment_cm frag->fr_timeout = time_uptime; frag->fr_maxlen = frent->fe_len; - RB_INSERT(pf_frag_tree, &pf_frag_tree, frag); + rb_insert(&pf_frag_tree, frag); TAILQ_INSERT_HEAD(&pf_fragqueue, frag, frag_next); /* We do not have a previous fragment */ Index: net/pf_ruleset.c =================================================================== RCS file: /cvs/src/sys/net/pf_ruleset.c,v retrieving revision 1.12 diff -u -p -r1.12 pf_ruleset.c --- net/pf_ruleset.c 19 Jul 2016 13:34:12 -0000 1.12 +++ net/pf_ruleset.c 28 Jul 2016 04:10:41 -0000 @@ -75,18 +75,16 @@ #endif /* PFDEBUG */ #endif /* _KERNEL */ +int pf_anchor_compare(const void *, const void *); -struct pf_anchor_global pf_anchors; +struct rb_tree pf_anchors = RB_TREE_INITIALIZER(pf_anchor_compare, + offsetof(struct pf_anchor, entry_global)); struct pf_anchor pf_main_anchor; -static __inline int pf_anchor_compare(struct pf_anchor *, struct pf_anchor *); - -RB_GENERATE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare); -RB_GENERATE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare); - -static __inline int -pf_anchor_compare(struct pf_anchor *a, struct pf_anchor *b) +int +pf_anchor_compare(const void *aptr, const void *bptr) { + const struct pf_anchor *a = aptr, *b = bptr; int c = strcmp(a->path, b->path); return (c ? (c < 0 ? -1 : 1) : 0); @@ -111,7 +109,7 @@ pf_find_anchor(const char *path) if (key == NULL) return (NULL); strlcpy(key->path, path, sizeof(key->path)); - found = RB_FIND(pf_anchor_global, &pf_anchors, key); + found = rb_find(&pf_anchors, key); rs_free(key); return (found); } @@ -180,7 +178,8 @@ pf_find_or_create_ruleset(const char *pa rs_free(p); return (NULL); } - RB_INIT(&anchor->children); + rb_init(&anchor->children, pf_anchor_compare, + offsetof(struct pf_anchor, entry_node)); strlcpy(anchor->name, q, sizeof(anchor->name)); if (parent != NULL) { strlcpy(anchor->path, parent->path, @@ -188,10 +187,10 @@ pf_find_or_create_ruleset(const char *pa strlcat(anchor->path, "/", sizeof(anchor->path)); } strlcat(anchor->path, anchor->name, sizeof(anchor->path)); - if ((dup = RB_INSERT(pf_anchor_global, &pf_anchors, anchor)) != - NULL) { + dup = rb_insert(&pf_anchors, anchor); + if (dup != NULL) { DPFPRINTF(LOG_NOTICE, - "pf_find_or_create_ruleset: RB_INSERT1 " + "pf_find_or_create_ruleset: rb_insert1 " "'%s' '%s' collides with '%s' '%s'", anchor->path, anchor->name, dup->path, dup->name); rs_free(anchor); @@ -200,15 +199,14 @@ pf_find_or_create_ruleset(const char *pa } if (parent != NULL) { anchor->parent = parent; - if ((dup = RB_INSERT(pf_anchor_node, &parent->children, - anchor)) != NULL) { + dup = rb_insert(&parent->children, anchor); + if (dup != NULL) { DPFPRINTF(LOG_NOTICE, "pf_find_or_create_ruleset: " - "RB_INSERT2 '%s' '%s' collides with " + "rb_insert2 '%s' '%s' collides with " "'%s' '%s'", anchor->path, anchor->name, dup->path, dup->name); - RB_REMOVE(pf_anchor_global, &pf_anchors, - anchor); + rb_remove(&pf_anchors, anchor); rs_free(anchor); rs_free(p); return (NULL); @@ -233,7 +231,7 @@ pf_remove_if_empty_ruleset(struct pf_rul while (ruleset != NULL) { if (ruleset == &pf_main_ruleset || ruleset->anchor == NULL || - !RB_EMPTY(&ruleset->anchor->children) || + !rb_empty(&ruleset->anchor->children) || ruleset->anchor->refcnt > 0 || ruleset->tables > 0 || ruleset->topen) return; @@ -241,10 +239,9 @@ pf_remove_if_empty_ruleset(struct pf_rul !TAILQ_EMPTY(ruleset->rules.inactive.ptr) || ruleset->rules.inactive.open) return; - RB_REMOVE(pf_anchor_global, &pf_anchors, ruleset->anchor); + rb_remove(&pf_anchors, ruleset->anchor); if ((parent = ruleset->anchor->parent) != NULL) - RB_REMOVE(pf_anchor_node, &parent->children, - ruleset->anchor); + rb_remove(&parent->children, ruleset->anchor); rs_free(ruleset->anchor); if (parent == NULL) return; Index: net/pf_table.c =================================================================== RCS file: /cvs/src/sys/net/pf_table.c,v retrieving revision 1.116 diff -u -p -r1.116 pf_table.c --- net/pf_table.c 3 Nov 2015 22:10:33 -0000 1.116 +++ net/pf_table.c 28 Jul 2016 04:10:41 -0000 @@ -177,8 +177,7 @@ struct pfr_ktable *pfr_create_ktable(str int); void pfr_destroy_ktables(struct pfr_ktableworkq *, int); void pfr_destroy_ktable(struct pfr_ktable *, int); -int pfr_ktable_compare(struct pfr_ktable *, - struct pfr_ktable *); +int pfr_ktable_compare(const void *, const void *); void pfr_ktable_winfo_update(struct pfr_ktable *, struct pfr_kentry *); struct pfr_ktable *pfr_lookup_table(struct pfr_table *); @@ -190,10 +189,8 @@ int pfr_skip_table(struct pfr_table * struct pfr_kentry *pfr_kentry_byidx(struct pfr_ktable *, int, int); int pfr_islinklocal(sa_family_t, struct pf_addr *); -RB_PROTOTYPE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare); -RB_GENERATE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare); - -struct pfr_ktablehead pfr_ktables; +struct rb_tree pfr_ktables = RB_TREE_INITIALIZER(pfr_ktable_compare, + offsetof(struct pfr_ktable, pfrkt_tree)); struct pfr_table pfr_nulltable; int pfr_ktable_cnt; @@ -1274,7 +1271,7 @@ pfr_clr_tables(struct pfr_table *filter, return (ENOENT); SLIST_INIT(&workq); - RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) { + rb_foreach (p, &pfr_ktables) { if (pfr_skip_table(filter, p, flags)) continue; if (!strcmp(p->pfrkt_anchor, PF_RESERVED_ANCHOR)) @@ -1312,7 +1309,7 @@ pfr_add_tables(struct pfr_table *tbl, in flags & PFR_FLAG_USERIOCTL)) senderr(EINVAL); key.pfrkt_flags |= PFR_TFLAG_ACTIVE; - p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key); + p = rb_find(&pfr_ktables, &key); if (p == NULL) { p = pfr_create_ktable(&key.pfrkt_t, tzero, 1, !(flags & PFR_FLAG_USERIOCTL)); @@ -1329,7 +1326,7 @@ pfr_add_tables(struct pfr_table *tbl, in /* find or create root table */ bzero(key.pfrkt_anchor, sizeof(key.pfrkt_anchor)); - r = RB_FIND(pfr_ktablehead, &pfr_ktables, &key); + r = rb_find(&pfr_ktables, &key); if (r != NULL) { p->pfrkt_root = r; goto _skip; @@ -1388,7 +1385,7 @@ pfr_del_tables(struct pfr_table *tbl, in if (pfr_validate_table(&key.pfrkt_t, 0, flags & PFR_FLAG_USERIOCTL)) return (EINVAL); - p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key); + p = rb_find(&pfr_ktables, &key); if (p != NULL && (p->pfrkt_flags & PFR_TFLAG_ACTIVE)) { SLIST_FOREACH(q, &workq, pfrkt_workq) if (!pfr_ktable_compare(p, q)) @@ -1426,7 +1423,7 @@ pfr_get_tables(struct pfr_table *filter, *size = n; return (0); } - RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) { + rb_foreach (p, &pfr_ktables) { if (pfr_skip_table(filter, p, flags)) continue; if (n-- <= 0) @@ -1464,7 +1461,7 @@ pfr_get_tstats(struct pfr_table *filter, return (0); } SLIST_INIT(&workq); - RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) { + rb_foreach (p, &pfr_ktables) { if (pfr_skip_table(filter, p, flags)) continue; if (n-- <= 0) @@ -1505,7 +1502,7 @@ pfr_clr_tstats(struct pfr_table *tbl, in return (EFAULT); if (pfr_validate_table(&key.pfrkt_t, 0, 0)) return (EINVAL); - p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key); + p = rb_find(&pfr_ktables, &key); if (p != NULL) { SLIST_INSERT_HEAD(&workq, p, pfrkt_workq); xzero++; @@ -1540,7 +1537,7 @@ pfr_set_tflags(struct pfr_table *tbl, in if (pfr_validate_table(&key.pfrkt_t, 0, flags & PFR_FLAG_USERIOCTL)) return (EINVAL); - p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key); + p = rb_find(&pfr_ktables, &key); if (p != NULL && (p->pfrkt_flags & PFR_TFLAG_ACTIVE)) { p->pfrkt_nflags = (p->pfrkt_flags | setflag) & ~clrflag; @@ -1583,7 +1580,7 @@ pfr_ina_begin(struct pfr_table *trs, u_i if (rs == NULL) return (ENOMEM); SLIST_INIT(&workq); - RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) { + rb_foreach (p, &pfr_ktables) { if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) || pfr_skip_table(trs, p, 0)) continue; @@ -1626,7 +1623,7 @@ pfr_ina_define(struct pfr_table *tbl, st return (EBUSY); tbl->pfrt_flags |= PFR_TFLAG_INACTIVE; SLIST_INIT(&tableq); - kt = RB_FIND(pfr_ktablehead, &pfr_ktables, (struct pfr_ktable *)tbl); + kt = rb_find(&pfr_ktables, (struct pfr_ktable *)tbl); if (kt == NULL) { kt = pfr_create_ktable(tbl, 0, 1, !(flags & PFR_FLAG_USERIOCTL)); @@ -1640,7 +1637,7 @@ pfr_ina_define(struct pfr_table *tbl, st /* find or create root table */ bzero(&key, sizeof(key)); strlcpy(key.pfrkt_name, tbl->pfrt_name, sizeof(key.pfrkt_name)); - rt = RB_FIND(pfr_ktablehead, &pfr_ktables, &key); + rt = rb_find(&pfr_ktables, &key); if (rt != NULL) { kt->pfrkt_root = rt; goto _skip; @@ -1722,7 +1719,7 @@ pfr_ina_rollback(struct pfr_table *trs, if (rs == NULL || !rs->topen || ticket != rs->tticket) return (0); SLIST_INIT(&workq); - RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) { + rb_foreach (p, &pfr_ktables) { if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) || pfr_skip_table(trs, p, 0)) continue; @@ -1756,7 +1753,7 @@ pfr_ina_commit(struct pfr_table *trs, u_ return (EBUSY); SLIST_INIT(&workq); - RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) { + rb_foreach (p, &pfr_ktables) { if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) || pfr_skip_table(trs, p, 0)) continue; @@ -1929,7 +1926,7 @@ pfr_insert_ktables(struct pfr_ktablework void pfr_insert_ktable(struct pfr_ktable *kt) { - RB_INSERT(pfr_ktablehead, &pfr_ktables, kt); + rb_insert(&pfr_ktables, kt); pfr_ktable_cnt++; if (kt->pfrkt_root != NULL) if (!kt->pfrkt_root->pfrkt_refcnt[PFR_REFCNT_ANCHOR]++) @@ -1960,7 +1957,7 @@ pfr_setflags_ktable(struct pfr_ktable *k if (!(newf & PFR_TFLAG_ACTIVE)) newf &= ~PFR_TFLAG_USRMASK; if (!(newf & PFR_TFLAG_SETMASK)) { - RB_REMOVE(pfr_ktablehead, &pfr_ktables, kt); + rb_remove(&pfr_ktables, kt); if (kt->pfrkt_root != NULL) if (!--kt->pfrkt_root->pfrkt_refcnt[PFR_REFCNT_ANCHOR]) pfr_setflags_ktable(kt->pfrkt_root, @@ -2083,12 +2080,14 @@ pfr_destroy_ktable(struct pfr_ktable *kt } int -pfr_ktable_compare(struct pfr_ktable *p, struct pfr_ktable *q) +pfr_ktable_compare(const void *aptr, const void *bptr) { + const struct pfr_ktable *p = aptr, *q = bptr; int d; if ((d = strncmp(p->pfrkt_name, q->pfrkt_name, PF_TABLE_NAME_SIZE))) return (d); + return (strcmp(p->pfrkt_anchor, q->pfrkt_anchor)); } @@ -2096,8 +2095,7 @@ struct pfr_ktable * pfr_lookup_table(struct pfr_table *tbl) { /* struct pfr_ktable start like a struct pfr_table */ - return (RB_FIND(pfr_ktablehead, &pfr_ktables, - (struct pfr_ktable *)tbl)); + return (rb_find(&pfr_ktables, tbl)); } int Index: net/pfvar.h =================================================================== RCS file: /cvs/src/sys/net/pfvar.h,v retrieving revision 1.434 diff -u -p -r1.434 pfvar.h --- net/pfvar.h 19 Jul 2016 13:30:51 -0000 1.434 +++ net/pfvar.h 28 Jul 2016 04:10:41 -0000 @@ -35,7 +35,7 @@ #define _NET_PFVAR_H_ #include -#include +#include #include #include #include @@ -614,7 +614,7 @@ SLIST_HEAD(pf_rule_slist, pf_rule_item); enum pf_sn_types { PF_SN_NONE, PF_SN_NAT, PF_SN_RDR, PF_SN_ROUTE, PF_SN_MAX }; struct pf_src_node { - RB_ENTRY(pf_src_node) entry; + struct rb_entry entry; struct pf_addr addr; struct pf_addr raddr; union pf_rule_ptr rule; @@ -677,7 +677,7 @@ struct pf_state_peer { TAILQ_HEAD(pf_state_queue, pf_state); -/* keep synced with struct pf_state_key, used in RB_FIND */ +/* keep synced with struct pf_state_key, used in rb_find */ struct pf_state_key_cmp { struct pf_addr addr[2]; u_int16_t port[2]; @@ -700,7 +700,7 @@ struct pf_state_key { sa_family_t af; u_int8_t proto; - RB_ENTRY(pf_state_key) entry; + struct rb_entry entry; struct pf_statelisthead states; struct pf_state_key *reverse; struct inpcb *inp; @@ -711,7 +711,7 @@ struct pf_state_key { ((key[PF_SK_WIRE]->af != key[PF_SK_STACK]->af) && \ (key[PF_SK_WIRE]->af != (family))) -/* keep synced with struct pf_state, used in RB_FIND */ +/* keep synced with struct pf_state, used in rb_find */ struct pf_state_cmp { u_int64_t id; u_int32_t creatorid; @@ -727,7 +727,7 @@ struct pf_state { TAILQ_ENTRY(pf_state) sync_list; TAILQ_ENTRY(pf_state) entry_list; - RB_ENTRY(pf_state) entry_id; + struct rb_entry entry_id; struct pf_state_peer src; struct pf_state_peer dst; struct pf_rule_slist match_rules; @@ -911,21 +911,17 @@ struct pf_ruleset { int topen; }; -RB_HEAD(pf_anchor_global, pf_anchor); -RB_HEAD(pf_anchor_node, pf_anchor); struct pf_anchor { - RB_ENTRY(pf_anchor) entry_global; - RB_ENTRY(pf_anchor) entry_node; + struct rb_entry entry_global; + struct rb_entry entry_node; struct pf_anchor *parent; - struct pf_anchor_node children; + struct rb_tree children; char name[PF_ANCHOR_NAME_SIZE]; char path[PATH_MAX]; struct pf_ruleset ruleset; int refcnt; /* anchor rules */ int match; }; -RB_PROTOTYPE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare) -RB_PROTOTYPE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare) #define PF_RESERVED_ANCHOR "_pf" @@ -1075,10 +1071,9 @@ struct pfr_kentry_all { #define pfrke_rkif u.kr.kif SLIST_HEAD(pfr_ktableworkq, pfr_ktable); -RB_HEAD(pfr_ktablehead, pfr_ktable); struct pfr_ktable { struct pfr_tstats pfrkt_ts; - RB_ENTRY(pfr_ktable) pfrkt_tree; + struct rb_entry pfrkt_tree; SLIST_ENTRY(pfr_ktable) pfrkt_workq; struct radix_node_head *pfrkt_ip4; struct radix_node_head *pfrkt_ip6; @@ -1104,19 +1099,10 @@ struct pfr_ktable { #define pfrkt_nomatch pfrkt_ts.pfrts_nomatch #define pfrkt_tzero pfrkt_ts.pfrts_tzero -RB_HEAD(pf_state_tree, pf_state_key); -RB_PROTOTYPE(pf_state_tree, pf_state_key, entry, pf_state_compare_key) - -RB_HEAD(pf_state_tree_ext_gwy, pf_state_key); -RB_PROTOTYPE(pf_state_tree_ext_gwy, pf_state_key, - entry_ext_gwy, pf_state_compare_ext_gwy) - -RB_HEAD(pfi_ifhead, pfi_kif); - /* state tables */ -extern struct pf_state_tree pf_statetbl; +extern struct rb_tree pf_statetbl; -/* keep synced with pfi_kif, used in RB_FIND */ +/* keep synced with pfi_kif, used in rb_find */ struct pfi_kif_cmp { char pfik_name[IFNAMSIZ]; }; @@ -1126,7 +1112,7 @@ struct ifg_group; struct pfi_kif { char pfik_name[IFNAMSIZ]; - RB_ENTRY(pfi_kif) pfik_tree; + struct rb_entry pfik_tree; u_int64_t pfik_packets[2][2][2]; u_int64_t pfik_bytes[2][2][2]; time_t pfik_tzero; @@ -1640,14 +1626,9 @@ struct pfioc_iface { #define DIOCGETQSTATS _IOWR('D', 96, struct pfioc_qstats) #ifdef _KERNEL -RB_HEAD(pf_src_tree, pf_src_node); -RB_PROTOTYPE(pf_src_tree, pf_src_node, entry, pf_src_compare); -extern struct pf_src_tree tree_src_tracking; - -RB_HEAD(pf_state_tree_id, pf_state); -RB_PROTOTYPE(pf_state_tree_id, pf_state, - entry_id, pf_state_compare_id); -extern struct pf_state_tree_id tree_id; +extern struct rb_tree tree_src_tracking; + +extern struct rb_tree tree_id; extern struct pf_state_queue state_list; TAILQ_HEAD(pf_queuehead, pf_queuespec); @@ -1837,7 +1818,10 @@ void pf_tag2tagname(u_int16_t, char *) void pf_tag_ref(u_int16_t); void pf_tag_unref(u_int16_t); void pf_tag_packet(struct mbuf *, int, int); -int pf_addr_compare(struct pf_addr *, struct pf_addr *, +int pf_src_compare(const void *, const void *); +int pf_state_compare_key(const void *, const void *); +int pf_state_compare_id(const void *, const void *); +int pf_addr_compare(const struct pf_addr *, const struct pf_addr *, sa_family_t); extern struct pf_status pf_status; @@ -1853,7 +1837,7 @@ extern struct pf_pool_limit pf_pool_limi #endif /* _KERNEL */ -extern struct pf_anchor_global pf_anchors; +extern struct rb_tree pf_anchors; extern struct pf_anchor pf_main_anchor; #define pf_main_ruleset pf_main_anchor.ruleset Index: nfs/nfs_node.c =================================================================== RCS file: /cvs/src/sys/nfs/nfs_node.c,v retrieving revision 1.64 diff -u -p -r1.64 nfs_node.c --- nfs/nfs_node.c 19 Mar 2016 12:04:16 -0000 1.64 +++ nfs/nfs_node.c 28 Jul 2016 04:10:41 -0000 @@ -64,16 +64,24 @@ struct rwlock nfs_hashlock = RWLOCK_INIT extern struct vops nfs_vops; /* filehandle to node lookup. */ -static __inline int -nfsnode_cmp(const struct nfsnode *a, const struct nfsnode *b) +static int +nfsnode_cmp(const void *a, const void *b) { - if (a->n_fhsize != b->n_fhsize) - return (a->n_fhsize - b->n_fhsize); - return (memcmp(a->n_fhp, b->n_fhp, a->n_fhsize)); + const struct nfsnode *na = a, *nb = b; + + if (na->n_fhsize > nb->n_fhsize) + return (1); + if (na->n_fhsize < nb->n_fhsize) + return (-1); + + return (memcmp(na->n_fhp, nb->n_fhp, na->n_fhsize)); } -RB_PROTOTYPE(nfs_nodetree, nfsnode, n_entry, nfsnode_cmp); -RB_GENERATE(nfs_nodetree, nfsnode, n_entry, nfsnode_cmp); +void +nfs_rb_init(struct rb_tree *rbt) +{ + rb_init(rbt, nfsnode_cmp, offsetof(struct nfsnode, n_entry)); +} /* * Look up a vnode/nfsnode by file handle and store the pointer in *npp. @@ -95,7 +103,7 @@ loop: rw_enter_write(&nfs_hashlock); find.n_fhp = fh; find.n_fhsize = fhsize; - np = RB_FIND(nfs_nodetree, &nmp->nm_ntree, &find); + np = rb_find(&nmp->nm_ntree, &find); if (np != NULL) { rw_exit_write(&nfs_hashlock); vp = NFSTOV(np); @@ -124,7 +132,7 @@ loop: return (error); } nvp->v_flag |= VLARVAL; - np = RB_FIND(nfs_nodetree, &nmp->nm_ntree, &find); + np = rb_find(&nmp->nm_ntree, &find); if (np != NULL) { vgone(nvp); rw_exit_write(&nfs_hashlock); @@ -153,7 +161,7 @@ loop: np->n_fhp = &np->n_fh; bcopy(fh, np->n_fhp, fhsize); np->n_fhsize = fhsize; - np2 = RB_INSERT(nfs_nodetree, &nmp->nm_ntree, np); + np2 = rb_insert(&nmp->nm_ntree, np); KASSERT(np2 == NULL); np->n_accstamp = -1; rw_exit(&nfs_hashlock); @@ -234,7 +242,7 @@ nfs_reclaim(void *v) #endif nmp = VFSTONFS(vp->v_mount); rw_enter_write(&nfs_hashlock); - RB_REMOVE(nfs_nodetree, &nmp->nm_ntree, np); + rb_remove(&nmp->nm_ntree, np); rw_exit_write(&nfs_hashlock); if (np->n_rcred) Index: nfs/nfs_var.h =================================================================== RCS file: /cvs/src/sys/nfs/nfs_var.h,v retrieving revision 1.61 diff -u -p -r1.61 nfs_var.h --- nfs/nfs_var.h 29 Apr 2016 14:40:36 -0000 1.61 +++ nfs/nfs_var.h 28 Jul 2016 04:10:41 -0000 @@ -43,6 +43,7 @@ struct sillyrename; struct componentname; struct nfs_diskless; struct nfsm_info; +struct rb_tree; /* nfs_bio.c */ int nfs_bioread(struct vnode *, struct uio *, int, struct ucred *); @@ -56,6 +57,7 @@ int nfs_doio(struct buf *, struct proc * int nfs_boot_init(struct nfs_diskless *, struct proc *); /* nfs_node.c */ +void nfs_rb_init(struct rb_tree *); int nfs_nget(struct mount *, nfsfh_t *, int, struct nfsnode **); int nfs_inactive(void *); int nfs_reclaim(void *); Index: nfs/nfs_vfsops.c =================================================================== RCS file: /cvs/src/sys/nfs/nfs_vfsops.c,v retrieving revision 1.109 diff -u -p -r1.109 nfs_vfsops.c --- nfs/nfs_vfsops.c 26 Apr 2016 18:37:03 -0000 1.109 +++ nfs/nfs_vfsops.c 28 Jul 2016 04:10:41 -0000 @@ -652,7 +652,7 @@ mountnfs(struct nfs_args *argp, struct m nmp->nm_nam = nam; nfs_decode_args(nmp, argp, &mp->mnt_stat.mount_info.nfs_args); - RB_INIT(&nmp->nm_ntree); + nfs_rb_init(&nmp->nm_ntree); TAILQ_INIT(&nmp->nm_reqsq); timeout_set(&nmp->nm_rtimeout, nfs_timer, nmp); Index: nfs/nfsmount.h =================================================================== RCS file: /cvs/src/sys/nfs/nfsmount.h,v retrieving revision 1.25 diff -u -p -r1.25 nfsmount.h --- nfs/nfsmount.h 10 Sep 2012 11:10:59 -0000 1.25 +++ nfs/nfsmount.h 28 Jul 2016 04:10:41 -0000 @@ -45,7 +45,7 @@ * Holds NFS specific information for mount. */ struct nfsmount { - RB_HEAD(nfs_nodetree, nfsnode) + struct rb_tree nm_ntree; /* filehandle/node tree */ TAILQ_HEAD(reqs, nfsreq) nm_reqsq; /* request queue for this mount. */ Index: nfs/nfsnode.h =================================================================== RCS file: /cvs/src/sys/nfs/nfsnode.h,v retrieving revision 1.39 diff -u -p -r1.39 nfsnode.h --- nfs/nfsnode.h 15 Dec 2009 15:53:48 -0000 1.39 +++ nfs/nfsnode.h 28 Jul 2016 04:10:41 -0000 @@ -70,7 +70,7 @@ struct sillyrename { * be well aligned and, therefore, tightly packed. */ struct nfsnode { - RB_ENTRY(nfsnode) n_entry; /* filehandle/node tree. */ + struct rb_entry n_entry; /* filehandle/node tree. */ u_quad_t n_size; /* Current size of file */ struct vattr n_vattr; /* Vnode attribute cache */ time_t n_attrstamp; /* Attr. cache timestamp */ Index: sys/buf.h =================================================================== RCS file: /cvs/src/sys/sys/buf.h,v retrieving revision 1.103 diff -u -p -r1.103 buf.h --- sys/buf.h 23 May 2016 09:31:28 -0000 1.103 +++ sys/buf.h 28 Jul 2016 04:10:41 -0000 @@ -40,7 +40,7 @@ #ifndef _SYS_BUF_H_ #define _SYS_BUF_H_ #include -#include +#include #include #define NOLIST ((struct buf *)0x87654321) @@ -49,7 +49,6 @@ struct buf; struct vnode; struct buf_rb_bufs; -RB_PROTOTYPE(buf_rb_bufs, buf, b_rbbufs, rb_buf_compare); LIST_HEAD(bufhead, buf); @@ -140,7 +139,7 @@ extern struct bio_ops { /* The buffer header describes an I/O operation in the kernel. */ struct buf { - RB_ENTRY(buf) b_rbbufs; /* vnode "hash" tree */ + struct rb_entry b_rbbufs; /* vnode "hash" tree */ LIST_ENTRY(buf) b_list; /* All allocated buffers. */ LIST_ENTRY(buf) b_vnbufs; /* Buffer's associated vnode. */ TAILQ_ENTRY(buf) b_freelist; /* Free list position if not active. */ Index: sys/namei.h =================================================================== RCS file: /cvs/src/sys/sys/namei.h,v retrieving revision 1.32 diff -u -p -r1.32 namei.h --- sys/namei.h 29 Apr 2016 14:40:36 -0000 1.32 +++ sys/namei.h 28 Jul 2016 04:10:41 -0000 @@ -36,12 +36,11 @@ #define _SYS_NAMEI_H_ #include -#include +#include #include struct namecache; struct namecache_rb_cache; -RB_PROTOTYPE(namecache_rb_cache, namecache, n_rbcache, namecache_compare); /* * Encapsulation of namei parameters. @@ -176,7 +175,7 @@ void ndinitat(struct nameidata *ndp, u_l struct namecache { TAILQ_ENTRY(namecache) nc_lru; /* Regular Entry LRU chain */ TAILQ_ENTRY(namecache) nc_neg; /* Negative Entry LRU chain */ - RB_ENTRY(namecache) n_rbcache; /* Namecache rb tree from vnode */ + struct rb_entry n_rbcache; /* Namecache rb tree from vnode */ TAILQ_ENTRY(namecache) nc_me; /* ncp's referring to me */ struct vnode *nc_dvp; /* vnode of parent of name */ u_long nc_dvpid; /* capability number of nc_dvp */ Index: sys/pool.h =================================================================== RCS file: /cvs/src/sys/sys/pool.h,v retrieving revision 1.59 diff -u -p -r1.59 pool.h --- sys/pool.h 21 Apr 2016 04:09:28 -0000 1.59 +++ sys/pool.h 28 Jul 2016 04:10:41 -0000 @@ -69,7 +69,7 @@ struct kinfo_pool { #if defined(_KERNEL) || defined(_LIBKVM) #include -#include +#include #include struct pool; @@ -121,8 +121,7 @@ struct pool { int pr_ipl; - RB_HEAD(phtree, pool_item_header) - pr_phtree; + struct rb_tree pr_phtree; u_int pr_align; u_int pr_maxcolors; /* Cache coloring */ Index: sys/rbtree.h =================================================================== RCS file: sys/rbtree.h diff -N sys/rbtree.h --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ sys/rbtree.h 28 Jul 2016 04:10:41 -0000 @@ -0,0 +1,78 @@ +/* $OpenBSD */ + +/* + * Copyright (c) 2016 David Gwynne + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _SYS_RBTREE_H_ +#define _SYS_RBTREE_H_ + +#include + +struct rb_entry { + struct rb_entry *rbe_parent; + struct rb_entry *rbe_left; + struct rb_entry *rbe_right; + unsigned int rbe_color; +}; + +struct rb_tree { + struct rb_entry *rbt_root; + int (*rbt_cmp)(const void *, const void *); + size_t rbt_entry; /* offset of rb_entry in node */ +}; + +#ifdef _KERNEL + +#define RB_TREE_INITIALIZER(_cmp, _off) { NULL, (_cmp), (_off) } + +void rb_init(struct rb_tree *, int (*)(const void *, const void *), size_t); +void *rb_insert(struct rb_tree *, void *); +void *rb_remove(struct rb_tree *, void *); +void *rb_find(struct rb_tree *, void *); +void *rb_nfind(struct rb_tree *, void *); +void *rb_root(struct rb_tree *); +int rb_empty(struct rb_tree *); +void *rb_next(struct rb_tree *, void *); +void *rb_prev(struct rb_tree *, void *); +void *rb_min(struct rb_tree *); +void *rb_max(struct rb_tree *); +void *rb_left(struct rb_tree *, void *); +void *rb_right(struct rb_tree *, void *); +void *rb_parent(struct rb_tree *, void *); + +#define rb_foreach(_e, _t) \ + for ((_e) = rb_min((_t)); \ + (_e) != NULL; \ + (_e) = rb_next((_t), (_e))) + +#define rb_foreach_safe(_e, _t, _n) \ + for ((_e) = rb_min((_t)); \ + (_e) != NULL && (_n) = rb_next((_t), (_e)); \ + (_e) = (_n)) + +#define rb_foreach_reverse(_e, _t) \ + for ((_e) = rb_max((_t)); \ + (_e) != NULL; \ + (_e) = rb_prev((_t), (_e))) + +#define rb_foreach_reverse_safe(_e, _t, _n) \ + for ((_e) = rb_max((_t)); \ + (_e) != NULL && (_n) = rb_prev((_t), (_v); \ + (_e) = (_n)) + +#endif /* _KERNEL */ + +#endif /* _SYS_RBTREE_H_ */ Index: sys/vnode.h =================================================================== RCS file: /cvs/src/sys/sys/vnode.h,v retrieving revision 1.135 diff -u -p -r1.135 vnode.h --- sys/vnode.h 23 May 2016 09:31:28 -0000 1.135 +++ sys/vnode.h 28 Jul 2016 04:10:41 -0000 @@ -39,7 +39,7 @@ #include #include #include -#include +#include /* * The vnode is the focus of all file activity in UNIX. There is a @@ -80,9 +80,6 @@ enum vtagtype { */ LIST_HEAD(buflists, buf); -RB_HEAD(buf_rb_bufs, buf); -RB_HEAD(namecache_rb_cache, namecache); - struct uvm_vnode; struct vnode { struct uvm_vnode *v_uvm; /* uvm data */ @@ -100,7 +97,7 @@ struct vnode { struct mount *v_mount; /* ptr to vfs we are in */ TAILQ_ENTRY(vnode) v_freelist; /* vnode freelist */ LIST_ENTRY(vnode) v_mntvnodes; /* vnodes for mount point */ - struct buf_rb_bufs v_bufs_tree; /* lookup of all bufs */ + struct rb_tree v_bufs_tree; /* lookup of all bufs */ struct buflists v_cleanblkhd; /* clean blocklist head */ struct buflists v_dirtyblkhd; /* dirty blocklist head */ u_int v_numoutput; /* num of writes in progress */ @@ -113,7 +110,7 @@ struct vnode { } v_un; /* VFS namecache */ - struct namecache_rb_cache v_nc_tree; + struct rb_tree v_nc_tree; TAILQ_HEAD(, namecache) v_cache_dst; /* cache entries to us */ void *v_data; /* private data for fs */