diff --git a/sys/net/route/nhgrp.c b/sys/net/route/nhgrp.c index f6638b12ebea..f40ee3c2981c 100644 --- a/sys/net/route/nhgrp.c +++ b/sys/net/route/nhgrp.c @@ -1,344 +1,344 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2020 Alexander V. Chernikov * * 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 AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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. * * $FreeBSD$ */ #include "opt_inet.h" #include "opt_route.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* * This file contains data structures management logic for the nexthop * groups ("nhgrp") route subsystem. * * Nexthop groups are used to store multiple routes available for the specific * prefix. Nexthop groups are immutable and can be shared across multiple * prefixes. * * Each group consists of a control plane part and a dataplane part. * Control plane is basically a collection of nexthop objects with * weights and refcount. * * Datapath consists of a array of nexthop pointers, compiled from control * plane data to support O(1) nexthop selection. * * For example, consider the following group: * [(nh1, weight=100), (nh2, weight=200)] * It will compile to the following array: * [nh1, nh2, nh2] * */ static void consider_resize(struct nh_control *ctl, uint32_t new_nh_buckets, uint32_t new_idx_items); static int cmp_nhgrp(const struct nhgrp_priv *a, const struct nhgrp_priv *b); static unsigned int hash_nhgrp(const struct nhgrp_priv *obj); static unsigned djb_hash(const unsigned char *h, const int len) { unsigned int result = 0; int i; for (i = 0; i < len; i++) result = 33 * result ^ h[i]; return (result); } static int cmp_nhgrp(const struct nhgrp_priv *a, const struct nhgrp_priv *b) { /* * In case of consistent hashing, there can be multiple nexthop groups * with the same "control plane" list of nexthops with weights and a * different set of "data plane" nexthops. * For now, ignore the data plane and focus on the control plane list. */ if (a->nhg_nh_count != b->nhg_nh_count) return (0); return !memcmp(a->nhg_nh_weights, b->nhg_nh_weights, sizeof(struct weightened_nhop) * a->nhg_nh_count); } /* * Hash callback: calculate hash of an object */ static unsigned int hash_nhgrp(const struct nhgrp_priv *obj) { const unsigned char *key; key = (const unsigned char *)obj->nhg_nh_weights; return (djb_hash(key, sizeof(struct weightened_nhop) * obj->nhg_nh_count)); } /* * Returns object referenced and unlocked */ struct nhgrp_priv * find_nhgrp(struct nh_control *ctl, const struct nhgrp_priv *key) { struct nhgrp_priv *priv_ret; NHOPS_RLOCK(ctl); CHT_SLIST_FIND_BYOBJ(&ctl->gr_head, mpath, key, priv_ret); if (priv_ret != NULL) { if (refcount_acquire_if_not_zero(&priv_ret->nhg_refcount) == 0) { /* refcount is 0 -> group is being deleted */ priv_ret = NULL; } } NHOPS_RUNLOCK(ctl); return (priv_ret); } int link_nhgrp(struct nh_control *ctl, struct nhgrp_priv *grp_priv) { uint16_t idx; uint32_t new_num_buckets, new_num_items; NHOPS_WLOCK(ctl); /* Check if we need to resize hash and index */ new_num_buckets = CHT_SLIST_GET_RESIZE_BUCKETS(&ctl->gr_head); new_num_items = bitmask_get_resize_items(&ctl->gr_idx_head); if (bitmask_alloc_idx(&ctl->gr_idx_head, &idx) != 0) { NHOPS_WUNLOCK(ctl); DPRINTF("Unable to allocate mpath index"); consider_resize(ctl, new_num_buckets, new_num_items); return (0); } grp_priv->nhg_idx = idx; grp_priv->nh_control = ctl; CHT_SLIST_INSERT_HEAD(&ctl->gr_head, mpath, grp_priv); NHOPS_WUNLOCK(ctl); consider_resize(ctl, new_num_buckets, new_num_items); return (1); } struct nhgrp_priv * unlink_nhgrp(struct nh_control *ctl, struct nhgrp_priv *key) { struct nhgrp_priv *nhg_priv_ret; int ret, idx; NHOPS_WLOCK(ctl); - CHT_SLIST_REMOVE_BYOBJ(&ctl->gr_head, mpath, key, nhg_priv_ret); + CHT_SLIST_REMOVE(&ctl->gr_head, mpath, key, nhg_priv_ret); if (nhg_priv_ret == NULL) { DPRINTF("Unable to find nhop group!"); NHOPS_WUNLOCK(ctl); return (NULL); } idx = nhg_priv_ret->nhg_idx; ret = bitmask_free_idx(&ctl->gr_idx_head, idx); nhg_priv_ret->nhg_idx = 0; nhg_priv_ret->nh_control = NULL; NHOPS_WUNLOCK(ctl); return (nhg_priv_ret); } /* * Checks if hash needs resizing and performs this resize if necessary * */ __noinline static void consider_resize(struct nh_control *ctl, uint32_t new_nh_buckets, uint32_t new_idx_items) { void *nh_ptr, *nh_idx_ptr; void *old_idx_ptr; size_t alloc_size; nh_ptr = NULL ; if (new_nh_buckets != 0) { alloc_size = CHT_SLIST_GET_RESIZE_SIZE(new_nh_buckets); nh_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO); } nh_idx_ptr = NULL; if (new_idx_items != 0) { alloc_size = bitmask_get_size(new_idx_items); nh_idx_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO); } if (nh_ptr == NULL && nh_idx_ptr == NULL) { /* Either resize is not required or allocations have failed. */ return; } DPRINTF("mp: going to resize: nh:[ptr:%p sz:%u] idx:[ptr:%p sz:%u]", nh_ptr, new_nh_buckets, nh_idx_ptr, new_idx_items); old_idx_ptr = NULL; NHOPS_WLOCK(ctl); if (nh_ptr != NULL) { CHT_SLIST_RESIZE(&ctl->gr_head, mpath, nh_ptr, new_nh_buckets); } if (nh_idx_ptr != NULL) { if (bitmask_copy(&ctl->gr_idx_head, nh_idx_ptr, new_idx_items) == 0) bitmask_swap(&ctl->gr_idx_head, nh_idx_ptr, new_idx_items, &old_idx_ptr); } NHOPS_WUNLOCK(ctl); if (nh_ptr != NULL) free(nh_ptr, M_NHOP); if (old_idx_ptr != NULL) free(old_idx_ptr, M_NHOP); } /* * Function allocating the necessary group data structures. */ bool nhgrp_ctl_alloc_default(struct nh_control *ctl, int malloc_flags) { size_t alloc_size; uint32_t num_buckets, num_items; void *cht_ptr, *mask_ptr; malloc_flags = (malloc_flags & (M_NOWAIT | M_WAITOK)) | M_ZERO; num_buckets = 8; alloc_size = CHT_SLIST_GET_RESIZE_SIZE(num_buckets); cht_ptr = malloc(alloc_size, M_NHOP, malloc_flags); if (cht_ptr == NULL) { DPRINTF("mpath init failed"); return (false); } /* * Allocate nexthop index bitmask. */ num_items = 128; mask_ptr = malloc(bitmask_get_size(num_items), M_NHOP, malloc_flags); if (mask_ptr == NULL) { DPRINTF("mpath bitmask init failed"); free(cht_ptr, M_NHOP); return (false); } NHOPS_WLOCK(ctl); if (ctl->gr_head.hash_size == 0) { /* Init hash and bitmask */ CHT_SLIST_INIT(&ctl->gr_head, cht_ptr, num_buckets); bitmask_init(&ctl->gr_idx_head, mask_ptr, num_items); NHOPS_WUNLOCK(ctl); } else { /* Other thread has already initiliazed hash/bitmask */ NHOPS_WUNLOCK(ctl); free(cht_ptr, M_NHOP); free(mask_ptr, M_NHOP); } DPRINTF("mpath init done for fib/af %d/%d", ctl->rh->rib_fibnum, ctl->rh->rib_family); return (true); } int nhgrp_ctl_init(struct nh_control *ctl) { /* * By default, do not allocate datastructures as multipath * routes will not be necessarily used. */ CHT_SLIST_INIT(&ctl->gr_head, NULL, 0); bitmask_init(&ctl->gr_idx_head, NULL, 0); return (0); } void nhgrp_ctl_free(struct nh_control *ctl) { if (ctl->gr_head.ptr != NULL) free(ctl->gr_head.ptr, M_NHOP); if (ctl->gr_idx_head.idx != NULL) free(ctl->gr_idx_head.idx, M_NHOP); } void nhgrp_ctl_unlink_all(struct nh_control *ctl) { struct nhgrp_priv *nhg_priv; NHOPS_WLOCK_ASSERT(ctl); CHT_SLIST_FOREACH(&ctl->gr_head, mpath, nhg_priv) { DPRINTF("Marking nhgrp %u unlinked", nhg_priv->nhg_idx); refcount_release(&nhg_priv->nhg_linked); } CHT_SLIST_FOREACH_END; } diff --git a/sys/net/route/nhop.c b/sys/net/route/nhop.c index 0db47db9916e..ab5e393ae56a 100644 --- a/sys/net/route/nhop.c +++ b/sys/net/route/nhop.c @@ -1,391 +1,391 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2020 Alexander V. Chernikov * * 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 AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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. */ #include __FBSDID("$FreeBSD$"); #include "opt_inet.h" #include "opt_route.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* * This file contains data structures management logic for the nexthop ("nhop") * route subsystem. * * Nexthops in the original sense are the objects containing all the necessary * information to forward the packet to the selected destination. * In particular, nexthop is defined by a combination of * ifp, ifa, aifp, mtu, gw addr(if set), nh_type, nh_family, mask of rt_flags and * NHF_DEFAULT * * All nexthops are stored in the resizable hash table. * Additionally, each nexthop gets assigned its unique index (nexthop index) * so userland programs can interact with the nexthops easier. Index allocation * is backed by the bitmask array. */ MALLOC_DEFINE(M_NHOP, "nhops", "nexthops data"); /* Hash management functions */ int nhops_init_rib(struct rib_head *rh) { struct nh_control *ctl; size_t alloc_size; uint32_t num_buckets, num_items; void *ptr; ctl = malloc(sizeof(struct nh_control), M_NHOP, M_WAITOK | M_ZERO); /* * Allocate nexthop hash. Start with 16 items by default (128 bytes). * This will be enough for most of the cases. */ num_buckets = 16; alloc_size = CHT_SLIST_GET_RESIZE_SIZE(num_buckets); ptr = malloc(alloc_size, M_NHOP, M_WAITOK | M_ZERO); CHT_SLIST_INIT(&ctl->nh_head, ptr, num_buckets); /* * Allocate nexthop index bitmask. */ num_items = 128 * 8; /* 128 bytes */ ptr = malloc(bitmask_get_size(num_items), M_NHOP, M_WAITOK | M_ZERO); bitmask_init(&ctl->nh_idx_head, ptr, num_items); NHOPS_LOCK_INIT(ctl); rh->nh_control = ctl; ctl->ctl_rh = rh; DPRINTF("NHOPS init for fib %u af %u: ctl %p rh %p", rh->rib_fibnum, rh->rib_family, ctl, rh); return (0); } static void destroy_ctl(struct nh_control *ctl) { NHOPS_LOCK_DESTROY(ctl); free(ctl->nh_head.ptr, M_NHOP); free(ctl->nh_idx_head.idx, M_NHOP); #ifdef ROUTE_MPATH nhgrp_ctl_free(ctl); #endif free(ctl, M_NHOP); } /* * Epoch callback indicating ctl is safe to destroy */ static void destroy_ctl_epoch(epoch_context_t ctx) { struct nh_control *ctl; ctl = __containerof(ctx, struct nh_control, ctl_epoch_ctx); destroy_ctl(ctl); } void nhops_destroy_rib(struct rib_head *rh) { struct nh_control *ctl; struct nhop_priv *nh_priv; ctl = rh->nh_control; /* * All routes should have been deleted in rt_table_destroy(). * However, TCP stack or other consumers may store referenced * nexthop pointers. When these references go to zero, * nhop_free() will try to unlink these records from the * datastructures, most likely leading to panic. * * Avoid that by explicitly marking all of the remaining * nexthops as unlinked by removing a reference from a special * counter. Please see nhop_free() comments for more * details. */ NHOPS_WLOCK(ctl); CHT_SLIST_FOREACH(&ctl->nh_head, nhops, nh_priv) { DPRINTF("Marking nhop %u unlinked", nh_priv->nh_idx); refcount_release(&nh_priv->nh_linked); } CHT_SLIST_FOREACH_END; #ifdef ROUTE_MPATH nhgrp_ctl_unlink_all(ctl); #endif NHOPS_WUNLOCK(ctl); /* * Postpone destruction till the end of current epoch * so nhop_free() can safely use nh_control pointer. */ epoch_call(net_epoch_preempt, destroy_ctl_epoch, &ctl->ctl_epoch_ctx); } /* * Nexhop hash calculation: * * Nexthops distribution: * 2 "mandatory" nexthops per interface ("interface route", "loopback"). * For direct peering: 1 nexthop for the peering router per ifp/af. * For Ix-like peering: tens to hundreds nexthops of neghbors per ifp/af. * IGP control plane & broadcast segment: tens of nexthops per ifp/af. * * Each fib/af combination has its own hash table. * With that in mind, hash nexthops by the combination of the interface * and GW IP address. * * To optimize hash calculation, ignore higher bytes of ifindex, as they * give very little entropy. * Similarly, use lower 4 bytes of IPv6 address to distinguish between the * neighbors. */ struct _hash_data { uint16_t ifindex; uint8_t family; uint8_t nh_type; uint32_t gw_addr; }; static unsigned djb_hash(const unsigned char *h, const int len) { unsigned int result = 0; int i; for (i = 0; i < len; i++) result = 33 * result ^ h[i]; return (result); } static uint32_t hash_priv(const struct nhop_priv *priv) { struct nhop_object *nh; uint16_t ifindex; struct _hash_data key; nh = priv->nh; ifindex = nh->nh_ifp->if_index & 0xFFFF; memset(&key, 0, sizeof(key)); key.ifindex = ifindex; key.family = nh->gw_sa.sa_family; key.nh_type = priv->nh_type & 0xFF; if (nh->gw_sa.sa_family == AF_INET6) memcpy(&key.gw_addr, &nh->gw6_sa.sin6_addr.s6_addr32[3], 4); else if (nh->gw_sa.sa_family == AF_INET) memcpy(&key.gw_addr, &nh->gw4_sa.sin_addr, 4); return (uint32_t)(djb_hash((const unsigned char *)&key, sizeof(key))); } /* * Checks if hash needs resizing and performs this resize if necessary * */ static void consider_resize(struct nh_control *ctl, uint32_t new_nh_buckets, uint32_t new_idx_items) { void *nh_ptr, *nh_idx_ptr; void *old_idx_ptr; size_t alloc_size; nh_ptr = NULL; if (new_nh_buckets != 0) { alloc_size = CHT_SLIST_GET_RESIZE_SIZE(new_nh_buckets); nh_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO); } nh_idx_ptr = NULL; if (new_idx_items != 0) { alloc_size = bitmask_get_size(new_idx_items); nh_idx_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO); } if (nh_ptr == NULL && nh_idx_ptr == NULL) { /* Either resize is not required or allocations have failed. */ return; } DPRINTF("going to resize: nh:[ptr:%p sz:%u] idx:[ptr:%p sz:%u]", nh_ptr, new_nh_buckets, nh_idx_ptr, new_idx_items); old_idx_ptr = NULL; NHOPS_WLOCK(ctl); if (nh_ptr != NULL) { CHT_SLIST_RESIZE(&ctl->nh_head, nhops, nh_ptr, new_nh_buckets); } if (nh_idx_ptr != NULL) { if (bitmask_copy(&ctl->nh_idx_head, nh_idx_ptr, new_idx_items) == 0) bitmask_swap(&ctl->nh_idx_head, nh_idx_ptr, new_idx_items, &old_idx_ptr); } NHOPS_WUNLOCK(ctl); if (nh_ptr != NULL) free(nh_ptr, M_NHOP); if (old_idx_ptr != NULL) free(old_idx_ptr, M_NHOP); } /* * Links nextop @nh_priv to the nexhop hash table and allocates * nexhop index. * Returns allocated index or 0 on failure. */ int link_nhop(struct nh_control *ctl, struct nhop_priv *nh_priv) { uint16_t idx; uint32_t num_buckets_new, num_items_new; KASSERT((nh_priv->nh_idx == 0), ("nhop index is already allocated")); NHOPS_WLOCK(ctl); /* * Check if we need to resize hash and index. * The following 2 functions returns either new size or 0 * if resize is not required. */ num_buckets_new = CHT_SLIST_GET_RESIZE_BUCKETS(&ctl->nh_head); num_items_new = bitmask_get_resize_items(&ctl->nh_idx_head); if (bitmask_alloc_idx(&ctl->nh_idx_head, &idx) != 0) { NHOPS_WUNLOCK(ctl); DPRINTF("Unable to allocate nhop index"); RTSTAT_INC(rts_nh_idx_alloc_failure); consider_resize(ctl, num_buckets_new, num_items_new); return (0); } nh_priv->nh_idx = idx; nh_priv->nh_control = ctl; CHT_SLIST_INSERT_HEAD(&ctl->nh_head, nhops, nh_priv); NHOPS_WUNLOCK(ctl); DPRINTF("Linked nhop priv %p to %d, hash %u, ctl %p", nh_priv, idx, hash_priv(nh_priv), ctl); consider_resize(ctl, num_buckets_new, num_items_new); return (idx); } /* * Unlinks nexthop specified by @nh_priv data from the hash. * * Returns found nexthop or NULL. */ struct nhop_priv * unlink_nhop(struct nh_control *ctl, struct nhop_priv *nh_priv_del) { struct nhop_priv *priv_ret; int idx; uint32_t num_buckets_new, num_items_new; idx = 0; NHOPS_WLOCK(ctl); - CHT_SLIST_REMOVE_BYOBJ(&ctl->nh_head, nhops, nh_priv_del, priv_ret); + CHT_SLIST_REMOVE(&ctl->nh_head, nhops, nh_priv_del, priv_ret); if (priv_ret != NULL) { idx = priv_ret->nh_idx; priv_ret->nh_idx = 0; KASSERT((idx != 0), ("bogus nhop index 0")); if ((bitmask_free_idx(&ctl->nh_idx_head, idx)) != 0) { DPRINTF("Unable to remove index %d from fib %u af %d", idx, ctl->ctl_rh->rib_fibnum, ctl->ctl_rh->rib_family); } } /* Check if hash or index needs to be resized */ num_buckets_new = CHT_SLIST_GET_RESIZE_BUCKETS(&ctl->nh_head); num_items_new = bitmask_get_resize_items(&ctl->nh_idx_head); NHOPS_WUNLOCK(ctl); if (priv_ret == NULL) DPRINTF("Unable to unlink nhop priv %p from hash, hash %u ctl %p", nh_priv_del, hash_priv(nh_priv_del), ctl); else DPRINTF("Unlinked nhop %p priv idx %d", priv_ret, idx); consider_resize(ctl, num_buckets_new, num_items_new); return (priv_ret); } /* * Searches for the nexthop by data specifcied in @nh_priv. * Returns referenced nexthop or NULL. */ struct nhop_priv * find_nhop(struct nh_control *ctl, const struct nhop_priv *nh_priv) { struct nhop_priv *nh_priv_ret; NHOPS_RLOCK(ctl); CHT_SLIST_FIND_BYOBJ(&ctl->nh_head, nhops, nh_priv, nh_priv_ret); if (nh_priv_ret != NULL) { if (refcount_acquire_if_not_zero(&nh_priv_ret->nh_refcnt) == 0){ /* refcount was 0 -> nhop is being deleted */ nh_priv_ret = NULL; } } NHOPS_RUNLOCK(ctl); return (nh_priv_ret); } diff --git a/sys/net/route/nhop_utils.h b/sys/net/route/nhop_utils.h index a0d7cd564e72..1f56f4cb8b0b 100644 --- a/sys/net/route/nhop_utils.h +++ b/sys/net/route/nhop_utils.h @@ -1,196 +1,179 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2020 Alexander V. Chernikov * * 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 AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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. * * $FreeBSD$ */ #ifndef _NET_ROUTE_NHOP_UTILS_H_ #define _NET_ROUTE_NHOP_UTILS_H_ /* Chained hash table */ struct _cht_head { uint32_t hash_size; uint32_t items_count; void **ptr; }; static inline uint32_t _cht_get_resize_size(const struct _cht_head *head) { uint32_t new_size = 0; if ((head->items_count * 2 > head->hash_size) && (head->hash_size < 65536)) new_size = head->hash_size * 2; else if ((head->items_count * 4 < head->hash_size) && head->hash_size > 16) new_size = head->hash_size / 2; return (new_size); } static inline int _cht_need_resize(const struct _cht_head *head) { return (_cht_get_resize_size(head) > 0); } #ifndef typeof #define typeof __typeof #endif #define CHT_SLIST_NEED_RESIZE(_head) \ _cht_need_resize((const struct _cht_head *)(_head)) #define CHT_SLIST_GET_RESIZE_BUCKETS(_head) \ _cht_get_resize_size((const struct _cht_head *)(_head)) #define CHT_SLIST_GET_RESIZE_SIZE(_buckets) ((_buckets) * sizeof(void *)) #define CHT_SLIST_DEFINE(_HNAME, _ITEM_TYPE) \ struct _HNAME##_head { \ uint32_t hash_size; \ uint32_t items_count; \ _ITEM_TYPE **ptr; \ } #define CHT_SLIST_INIT(_head, _ptr, _num_buckets) \ (_head)->hash_size = _num_buckets; \ (_head)->items_count = 0; \ (_head)->ptr = _ptr; /* Default hash method for constant-size keys */ #define CHT_GET_BUCK(_head, _PX, _key) _PX##_hash_key(_key) & ((_head)->hash_size - 1) #define CHT_GET_BUCK_OBJ(_head, _PX, _obj) _PX##_hash_obj(_obj) & ((_head)->hash_size - 1) #define CHT_FIRST(_head, idx) _CHT_FIRST((_head)->ptr, idx) #define _CHT_FIRST(_ptr, idx) (_ptr)[idx] #define CHT_SLIST_FIND(_head, _PX, _key, _ret) do { \ uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key); \ _ret = CHT_FIRST(_head, _buck); \ for ( ; _ret != NULL; _ret = _PX##_next(_ret)) { \ if (_PX##_cmp(_key, (_ret))) \ break; \ } \ } while(0) /* * hash_obj, nhop_cmp */ #define CHT_SLIST_FIND_BYOBJ(_head, _PX, _obj, _ret) do { \ uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \ _ret = CHT_FIRST(_head, _buck); \ for ( ; _ret != NULL; _ret = _PX##_next(_ret)) { \ if (_PX##_cmp(_obj, _ret)) \ break; \ } \ } while(0) #define CHT_SLIST_INSERT_HEAD(_head, _PX, _obj) do { \ uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \ _PX##_next(_obj) = CHT_FIRST(_head, _buck); \ CHT_FIRST(_head, _buck) = _obj; \ (_head)->items_count++; \ } while(0) -#define CHT_SLIST_REMOVE(_head, _PX, _key, _ret) do { \ - typeof(*(_head)->ptr) _tmp; \ - uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key); \ - _ret = CHT_FIRST(_head, _buck); \ - _tmp = NULL; \ - for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) { \ - if (_PX##_cmp(_key, _ret)) \ - break; \ - } \ - if (_ret != NULL) { \ - if (_tmp == NULL) \ - CHT_FIRST(_head, _buck) = _PX##_next(_ret); \ - else \ - _PX##_next(_tmp) = _PX##_next(_ret); \ - (_head)->items_count--; \ - } \ -} while(0) - -#define CHT_SLIST_REMOVE_BYOBJ(_head, _PX, _obj, _ret) do { \ +#define CHT_SLIST_REMOVE(_head, _PX, _obj, _ret) do { \ typeof(*(_head)->ptr) _tmp; \ uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj); \ _ret = CHT_FIRST(_head, _buck); \ _tmp = NULL; \ for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) { \ - if (_PX##_cmp(_obj, _ret)) \ + if (_obj == _ret) \ break; \ } \ if (_ret != NULL) { \ if (_tmp == NULL) \ CHT_FIRST(_head, _buck) = _PX##_next(_ret); \ else \ _PX##_next(_tmp) = _PX##_next(_ret); \ (_head)->items_count--; \ } \ } while(0) +#define CHT_SLIST_REMOVE_BYOBJ CHT_SLIST_REMOVE #define CHT_SLIST_FOREACH(_head, _PX, _x) \ for (uint32_t _i = 0; _i < (_head)->hash_size; _i++) { \ for (_x = CHT_FIRST(_head, _i); _x; _x = _PX##_next(_x)) #define CHT_SLIST_FOREACH_END } #define CHT_SLIST_RESIZE(_head, _PX, _new_void_ptr, _new_hsize) \ uint32_t _new_idx; \ typeof((_head)->ptr) _new_ptr = (void *)_new_void_ptr; \ typeof(*(_head)->ptr) _x, _y; \ for (uint32_t _old_idx = 0; _old_idx < (_head)->hash_size; _old_idx++) {\ _x = CHT_FIRST(_head, _old_idx); \ _y = _x; \ while (_y != NULL) { \ _y = _PX##_next(_x); \ _new_idx = _PX##_hash_obj(_x) & (_new_hsize - 1);\ _PX##_next(_x) = _CHT_FIRST(_new_ptr, _new_idx);\ _CHT_FIRST(_new_ptr, _new_idx) = _x; \ _x = _y; \ } \ } \ (_head)->hash_size = _new_hsize; \ _new_void_ptr = (void *)(_head)->ptr; \ (_head)->ptr = _new_ptr; /* bitmasks */ struct bitmask_head { uint16_t free_off; /* index of the first potentially free block */ uint16_t blocks; /* number of 4/8-byte blocks in the index */ uint32_t items_count; /* total number of items */ u_long *idx; }; size_t bitmask_get_size(uint32_t items); uint32_t bitmask_get_resize_items(const struct bitmask_head *nh); int bitmask_should_resize(const struct bitmask_head *bh); void bitmask_swap(struct bitmask_head *bh, void *new_idx, uint32_t new_items, void **pidx); void bitmask_init(struct bitmask_head *bh, void *idx, uint32_t num_items); int bitmask_copy(const struct bitmask_head *bi, void *new_idx, uint32_t new_items); int bitmask_alloc_idx(struct bitmask_head *bi, uint16_t *pidx); int bitmask_free_idx(struct bitmask_head *bi, uint16_t idx); #endif