/*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2019 Yandex LLC * Copyright (c) 2019 Andrey V. Elsukov * * 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 #include #include #include #include #include #include #include #include /* * Hash tables implementation for DUMMYNET using ConcurrencyKit. */ static MALLOC_DEFINE(M_DN_HT, "dummynet_ht", "dummynet hash tables"); static void* dn_alloc(size_t); static void dn_free(void *, size_t, bool); struct dn_ht { ck_hs_t hs; dn_ht_add_cb_t *add; dn_ht_del_cb_t *del; struct mtx lock; }; static struct ck_malloc dn_allocator = { .malloc = dn_alloc, .free = dn_free }; static void* dn_alloc(size_t s) { struct epoch_context *ctx; ctx = malloc(sizeof(*ctx) + s, M_DN_HT, M_NOWAIT); return (ctx ? ctx + 1: ctx); } static void dn_deferred_free(epoch_context_t ctx) { free(ctx, M_DN_HT); } static void dn_free(void *p, size_t s __unused, bool defer) { struct epoch_context *ctx = p; if (p == NULL) return; ctx--; if (defer) epoch_call(net_epoch_preempt, ctx, dn_deferred_free); else free(ctx, M_DN_HT); } struct dn_ht * dn_ht_init(struct dn_ht *ht, unsigned long capacity, unsigned long seed, dn_ht_hash_cb_t *hash, dn_ht_match_cb_t *match, dn_ht_add_cb_t *add, dn_ht_del_cb_t *del) { if (ht == NULL) ht = dn_alloc(sizeof(*ht)); if (ht == NULL) return (NULL); if (!ck_hs_init(&ht->hs, CK_HS_MODE_OBJECT | CK_HS_MODE_SPMC, hash, match, &dn_allocator, capacity, seed)) { dn_free(ht, 0, false); return (NULL); } mtx_init(&ht->lock, "dn_ht", NULL, MTX_DEF | MTX_NEW); ht->add = add; ht->del = del; return (ht); } void dn_ht_destroy(struct dn_ht *ht) { ck_hs_reset_drain(&ht->hs, ht->del); ck_hs_destroy(&ht->hs); mtx_destroy(&ht->lock); dn_free(ht, 0, false); } void dn_ht_reset(struct dn_ht *ht) { ck_hs_reset_drain(&ht->hs, ht->del); } static inline void * dn_ht_remove(struct dn_ht *ht, unsigned long hash, const void *key) { void *ret; mtx_lock(&ht->lock); ret = ck_hs_remove(&ht->hs, hash, key); mtx_unlock(&ht->lock); return (ret); } void dn_ht_scan(struct dn_ht *ht, dn_ht_scan_cb_t *fn, int flags, void *arg) { ck_hs_iterator_t i; void *key; if (ht == NULL || fn == NULL) return; MPASS(in_epoch(net_epoch_preempt)); ck_hs_iterator_init(&i); while (ck_hs_next(&ht->hs, &i, &key)) { switch (fn(key, flags, arg)) { case DNHT_SCAN_DEL: dn_ht_remove(ht, CK_HS_HASH(&ht->hs, ht->hs.hf, key), key); ht->del(key); break; case DNHT_SCAN_END: /* Callback requested stop iterating */ return; } } } void * dn_ht_find(struct dn_ht *ht, const void *key, int flags, void *arg) { unsigned long hash; void *ret; MPASS(in_epoch(net_epoch_preempt)); hash = CK_HS_HASH(&ht->hs, ht->hs.hf, key); if (flags & DNHT_REMOVE) ret = dn_ht_remove(ht, hash, key); else { ret = ck_hs_get(&ht->hs, hash, key); if (ret == NULL && (flags & DNHT_INSERT)) { bool result; ret = ht->add(key, flags, arg); if (ret == NULL) return (NULL); mtx_lock(&ht->lock); if (flags & DNHT_UNIQUE) result = ck_hs_put_unique(&ht->hs, hash, ret); else result = ck_hs_put(&ht->hs, hash, ret); mtx_unlock(&ht->lock); if (result == false) { ht->del(ret); ret = NULL; } } } return (ret); } unsigned long dn_ht_entries(struct dn_ht *ht) { return (ht ? ck_hs_count(&ht->hs): 0); } /* * flow_id mask, hash and compare functions. * * The flow_id includes the 5-tuple, the queue/pipe number * which we store in the extra area in host order, * and for ipv6 also the flow_id6. * XXX see if we want the tos byte (can store in 'flags') */ struct ipfw_flow_id* dn_flow_id_mask(const struct ipfw_flow_id *mask, struct ipfw_flow_id *id) { id->dst_port &= mask->dst_port; id->src_port &= mask->src_port; id->proto &= mask->proto; id->extra &= mask->extra; if (IS_IP6_FLOW_ID(id)) { APPLY_MASK(&id->dst_ip6, &mask->dst_ip6); APPLY_MASK(&id->src_ip6, &mask->src_ip6); id->flow_id6 &= mask->flow_id6; } else { id->dst_ip &= mask->dst_ip; id->src_ip &= mask->src_ip; } return (id); } /* * Computes an OR of two masks, result in dst and also returned */ struct ipfw_flow_id* dn_flow_id_or(const struct ipfw_flow_id *src, struct ipfw_flow_id *dst) { dst->dst_port |= src->dst_port; dst->src_port |= src->src_port; dst->proto |= src->proto; dst->extra |= src->extra; if (IS_IP6_FLOW_ID(dst)) { #define OR_MASK(_d, _s) \ (_d)->__u6_addr.__u6_addr32[0] |= (_s)->__u6_addr.__u6_addr32[0]; \ (_d)->__u6_addr.__u6_addr32[1] |= (_s)->__u6_addr.__u6_addr32[1]; \ (_d)->__u6_addr.__u6_addr32[2] |= (_s)->__u6_addr.__u6_addr32[2]; \ (_d)->__u6_addr.__u6_addr32[3] |= (_s)->__u6_addr.__u6_addr32[3]; OR_MASK(&dst->dst_ip6, &src->dst_ip6); OR_MASK(&dst->src_ip6, &src->src_ip6); #undef OR_MASK dst->flow_id6 |= src->flow_id6; } else { dst->dst_ip |= src->dst_ip; dst->src_ip |= src->src_ip; } return (dst); } /* * Returns true if mask is not empty. */ bool dn_mask_is_nonzero(const struct ipfw_flow_id *m) { if (m->dst_port || m->src_port || m->proto || m->extra) return (true); if (IS_IP6_FLOW_ID(m)) return (m->dst_ip6.__u6_addr.__u6_addr32[0] || m->dst_ip6.__u6_addr.__u6_addr32[1] || m->dst_ip6.__u6_addr.__u6_addr32[2] || m->dst_ip6.__u6_addr.__u6_addr32[3] || m->src_ip6.__u6_addr.__u6_addr32[0] || m->src_ip6.__u6_addr.__u6_addr32[1] || m->src_ip6.__u6_addr.__u6_addr32[2] || m->src_ip6.__u6_addr.__u6_addr32[3] || m->flow_id6); return (m->dst_ip || m->src_ip); } /* XXX we may want a better hash function */ uint32_t dn_flow_id_hash(const struct ipfw_flow_id *id) { uint32_t i; if (IS_IP6_FLOW_ID(id)) { const uint32_t *d = (const uint32_t *)&id->dst_ip6; const uint32_t *s = (const uint32_t *)&id->src_ip6; i = (d[0] ) ^ (d[1]) ^ (d[2] ) ^ (d[3]) ^ (d[0] >> 15) ^ (d[1] >> 15) ^ (d[2] >> 15) ^ (d[3] >> 15) ^ (s[0] << 1) ^ (s[1] << 1) ^ (s[2] << 1) ^ (s[3] << 1) ^ (s[0] << 16) ^ (s[1] << 16) ^ (s[2] << 16) ^ (s[3] << 16) ^ (id->dst_port << 1) ^ (id->src_port) ^ (id->extra) ^ (id->proto ) ^ (id->flow_id6); } else { i = (id->dst_ip) ^ (id->dst_ip >> 15) ^ (id->src_ip << 1) ^ (id->src_ip >> 16) ^ (id->extra) ^ (id->dst_port << 1) ^ (id->src_port) ^ (id->proto); } return (i); } /* * Like bcmp, returns 0 if ids match, 1 otherwise. */ int dn_flow_id_cmp(const struct ipfw_flow_id *id1, const struct ipfw_flow_id *id2) { if (!IS_IP6_FLOW_ID(id1)) { if (IS_IP6_FLOW_ID(id2)) return (1); /* different address families */ return ((id1->dst_ip == id2->dst_ip && id1->src_ip == id2->src_ip && id1->dst_port == id2->dst_port && id1->src_port == id2->src_port && id1->proto == id2->proto && id1->extra == id2->extra) ? 0 : 1); } /* the ipv6 case */ return (( !bcmp(&id1->dst_ip6, &id2->dst_ip6, sizeof(id1->dst_ip6)) && !bcmp(&id1->src_ip6, &id2->src_ip6, sizeof(id1->src_ip6)) && id1->dst_port == id2->dst_port && id1->src_port == id2->src_port && id1->proto == id2->proto && id1->extra == id2->extra && id1->flow_id6 == id2->flow_id6) ? 0 : 1); } inline uint32_t dn_id_hash(uint32_t id) { return ((id >> 8) ^ (id >> 4) ^ id); }