xref: /freebsd/sys/netpfil/ipfw/ip_fw_table_algo.c (revision 74b941f042e6ed533f2795ccde897b447ae35ca3)
19f7d47b0SAlexander V. Chernikov /*-
29f7d47b0SAlexander V. Chernikov  * Copyright (c) 2004 Ruslan Ermilov and Vsevolod Lobko.
39f7d47b0SAlexander V. Chernikov  *
49f7d47b0SAlexander V. Chernikov  * Redistribution and use in source and binary forms, with or without
59f7d47b0SAlexander V. Chernikov  * modification, are permitted provided that the following conditions
69f7d47b0SAlexander V. Chernikov  * are met:
79f7d47b0SAlexander V. Chernikov  * 1. Redistributions of source code must retain the above copyright
89f7d47b0SAlexander V. Chernikov  *    notice, this list of conditions and the following disclaimer.
99f7d47b0SAlexander V. Chernikov  * 2. Redistributions in binary form must reproduce the above copyright
109f7d47b0SAlexander V. Chernikov  *    notice, this list of conditions and the following disclaimer in the
119f7d47b0SAlexander V. Chernikov  *    documentation and/or other materials provided with the distribution.
129f7d47b0SAlexander V. Chernikov  *
139f7d47b0SAlexander V. Chernikov  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
149f7d47b0SAlexander V. Chernikov  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
159f7d47b0SAlexander V. Chernikov  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
169f7d47b0SAlexander V. Chernikov  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
179f7d47b0SAlexander V. Chernikov  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
189f7d47b0SAlexander V. Chernikov  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
199f7d47b0SAlexander V. Chernikov  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
209f7d47b0SAlexander V. Chernikov  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
219f7d47b0SAlexander V. Chernikov  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
229f7d47b0SAlexander V. Chernikov  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
239f7d47b0SAlexander V. Chernikov  * SUCH DAMAGE.
249f7d47b0SAlexander V. Chernikov  */
259f7d47b0SAlexander V. Chernikov 
269f7d47b0SAlexander V. Chernikov #include <sys/cdefs.h>
279f7d47b0SAlexander V. Chernikov __FBSDID("$FreeBSD: projects/ipfw/sys/netpfil/ipfw/ip_fw_table.c 267384 2014-06-12 09:59:11Z melifaro $");
289f7d47b0SAlexander V. Chernikov 
299f7d47b0SAlexander V. Chernikov /*
309f7d47b0SAlexander V. Chernikov  * Lookup table algorithms.
319f7d47b0SAlexander V. Chernikov  *
329f7d47b0SAlexander V. Chernikov  */
339f7d47b0SAlexander V. Chernikov 
349f7d47b0SAlexander V. Chernikov #include "opt_ipfw.h"
359f7d47b0SAlexander V. Chernikov #include "opt_inet.h"
369f7d47b0SAlexander V. Chernikov #ifndef INET
379f7d47b0SAlexander V. Chernikov #error IPFIREWALL requires INET.
389f7d47b0SAlexander V. Chernikov #endif /* INET */
399f7d47b0SAlexander V. Chernikov #include "opt_inet6.h"
409f7d47b0SAlexander V. Chernikov 
419f7d47b0SAlexander V. Chernikov #include <sys/param.h>
429f7d47b0SAlexander V. Chernikov #include <sys/systm.h>
439f7d47b0SAlexander V. Chernikov #include <sys/malloc.h>
449f7d47b0SAlexander V. Chernikov #include <sys/kernel.h>
459f7d47b0SAlexander V. Chernikov #include <sys/lock.h>
469f7d47b0SAlexander V. Chernikov #include <sys/rwlock.h>
479f7d47b0SAlexander V. Chernikov #include <sys/socket.h>
489f7d47b0SAlexander V. Chernikov #include <sys/queue.h>
499f7d47b0SAlexander V. Chernikov #include <net/if.h>	/* ip_fw.h requires IFNAMSIZ */
509f7d47b0SAlexander V. Chernikov #include <net/radix.h>
519f7d47b0SAlexander V. Chernikov #include <net/route.h>
529f7d47b0SAlexander V. Chernikov #include <net/vnet.h>
539f7d47b0SAlexander V. Chernikov 
549f7d47b0SAlexander V. Chernikov #include <netinet/in.h>
559f7d47b0SAlexander V. Chernikov #include <netinet/ip_var.h>	/* struct ipfw_rule_ref */
569f7d47b0SAlexander V. Chernikov #include <netinet/ip_fw.h>
579f7d47b0SAlexander V. Chernikov 
589f7d47b0SAlexander V. Chernikov #include <netpfil/ipfw/ip_fw_private.h>
59ea761a5dSAlexander V. Chernikov #include <netpfil/ipfw/ip_fw_table.h>
609f7d47b0SAlexander V. Chernikov 
619f7d47b0SAlexander V. Chernikov static MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
629f7d47b0SAlexander V. Chernikov 
6368394ec8SAlexander V. Chernikov static int badd(const void *key, void *item, void *base, size_t nmemb,
6468394ec8SAlexander V. Chernikov     size_t size, int (*compar) (const void *, const void *));
6568394ec8SAlexander V. Chernikov static int bdel(const void *key, void *base, size_t nmemb, size_t size,
6668394ec8SAlexander V. Chernikov     int (*compar) (const void *, const void *));
6768394ec8SAlexander V. Chernikov 
6868394ec8SAlexander V. Chernikov 
6968394ec8SAlexander V. Chernikov /*
7068394ec8SAlexander V. Chernikov  * CIDR implementation using radix
7168394ec8SAlexander V. Chernikov  *
7268394ec8SAlexander V. Chernikov  */
7368394ec8SAlexander V. Chernikov 
749f7d47b0SAlexander V. Chernikov /*
759f7d47b0SAlexander V. Chernikov  * The radix code expects addr and mask to be array of bytes,
769f7d47b0SAlexander V. Chernikov  * with the first byte being the length of the array. rn_inithead
779f7d47b0SAlexander V. Chernikov  * is called with the offset in bits of the lookup key within the
789f7d47b0SAlexander V. Chernikov  * array. If we use a sockaddr_in as the underlying type,
799f7d47b0SAlexander V. Chernikov  * sin_len is conveniently located at offset 0, sin_addr is at
809f7d47b0SAlexander V. Chernikov  * offset 4 and normally aligned.
819f7d47b0SAlexander V. Chernikov  * But for portability, let's avoid assumption and make the code explicit
829f7d47b0SAlexander V. Chernikov  */
839f7d47b0SAlexander V. Chernikov #define KEY_LEN(v)	*((uint8_t *)&(v))
849f7d47b0SAlexander V. Chernikov /*
859f7d47b0SAlexander V. Chernikov  * Do not require radix to compare more than actual IPv4/IPv6 address
869f7d47b0SAlexander V. Chernikov  */
879f7d47b0SAlexander V. Chernikov #define KEY_LEN_INET	(offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))
88e0a8b9eeSAlexander V. Chernikov #define KEY_LEN_INET6	(offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr))
899f7d47b0SAlexander V. Chernikov 
909f7d47b0SAlexander V. Chernikov #define OFF_LEN_INET	(8 * offsetof(struct sockaddr_in, sin_addr))
91e0a8b9eeSAlexander V. Chernikov #define OFF_LEN_INET6	(8 * offsetof(struct sa_in6, sin6_addr))
929f7d47b0SAlexander V. Chernikov 
93e0a8b9eeSAlexander V. Chernikov struct radix_cidr_entry {
949f7d47b0SAlexander V. Chernikov 	struct radix_node	rn[2];
95e0a8b9eeSAlexander V. Chernikov 	struct sockaddr_in	addr;
96e0a8b9eeSAlexander V. Chernikov 	uint32_t		value;
97e0a8b9eeSAlexander V. Chernikov 	uint8_t			masklen;
98e0a8b9eeSAlexander V. Chernikov };
99e0a8b9eeSAlexander V. Chernikov 
100e0a8b9eeSAlexander V. Chernikov struct sa_in6 {
101e0a8b9eeSAlexander V. Chernikov 	uint8_t			sin6_len;
102e0a8b9eeSAlexander V. Chernikov 	uint8_t			sin6_family;
103e0a8b9eeSAlexander V. Chernikov 	uint8_t			pad[2];
104e0a8b9eeSAlexander V. Chernikov 	struct in6_addr		sin6_addr;
105e0a8b9eeSAlexander V. Chernikov };
106e0a8b9eeSAlexander V. Chernikov 
107e0a8b9eeSAlexander V. Chernikov struct radix_cidr_xentry {
108e0a8b9eeSAlexander V. Chernikov 	struct radix_node	rn[2];
109e0a8b9eeSAlexander V. Chernikov 	struct sa_in6		addr6;
110e0a8b9eeSAlexander V. Chernikov 	uint32_t		value;
111e0a8b9eeSAlexander V. Chernikov 	uint8_t			masklen;
1129f7d47b0SAlexander V. Chernikov };
1139f7d47b0SAlexander V. Chernikov 
1149f7d47b0SAlexander V. Chernikov static int
1159f7d47b0SAlexander V. Chernikov ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
1169f7d47b0SAlexander V. Chernikov     uint32_t *val)
1179f7d47b0SAlexander V. Chernikov {
1189f7d47b0SAlexander V. Chernikov 	struct radix_node_head *rnh;
1199f7d47b0SAlexander V. Chernikov 
1209f7d47b0SAlexander V. Chernikov 	if (keylen == sizeof(in_addr_t)) {
121e0a8b9eeSAlexander V. Chernikov 		struct radix_cidr_entry *ent;
1229f7d47b0SAlexander V. Chernikov 		struct sockaddr_in sa;
1239f7d47b0SAlexander V. Chernikov 		KEY_LEN(sa) = KEY_LEN_INET;
1249f7d47b0SAlexander V. Chernikov 		sa.sin_addr.s_addr = *((in_addr_t *)key);
1259f7d47b0SAlexander V. Chernikov 		rnh = (struct radix_node_head *)ti->state;
126e0a8b9eeSAlexander V. Chernikov 		ent = (struct radix_cidr_entry *)(rnh->rnh_matchaddr(&sa, rnh));
1279f7d47b0SAlexander V. Chernikov 		if (ent != NULL) {
1289f7d47b0SAlexander V. Chernikov 			*val = ent->value;
1299f7d47b0SAlexander V. Chernikov 			return (1);
1309f7d47b0SAlexander V. Chernikov 		}
1319f7d47b0SAlexander V. Chernikov 	} else {
132e0a8b9eeSAlexander V. Chernikov 		struct radix_cidr_xentry *xent;
133e0a8b9eeSAlexander V. Chernikov 		struct sa_in6 sa6;
1349f7d47b0SAlexander V. Chernikov 		KEY_LEN(sa6) = KEY_LEN_INET6;
1359f7d47b0SAlexander V. Chernikov 		memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
1369f7d47b0SAlexander V. Chernikov 		rnh = (struct radix_node_head *)ti->xstate;
137e0a8b9eeSAlexander V. Chernikov 		xent = (struct radix_cidr_xentry *)(rnh->rnh_matchaddr(&sa6, rnh));
1389f7d47b0SAlexander V. Chernikov 		if (xent != NULL) {
1399f7d47b0SAlexander V. Chernikov 			*val = xent->value;
1409f7d47b0SAlexander V. Chernikov 			return (1);
1419f7d47b0SAlexander V. Chernikov 		}
1429f7d47b0SAlexander V. Chernikov 	}
1439f7d47b0SAlexander V. Chernikov 
1449f7d47b0SAlexander V. Chernikov 	return (0);
1459f7d47b0SAlexander V. Chernikov }
1469f7d47b0SAlexander V. Chernikov 
1479f7d47b0SAlexander V. Chernikov /*
1489f7d47b0SAlexander V. Chernikov  * New table
1499f7d47b0SAlexander V. Chernikov  */
1509f7d47b0SAlexander V. Chernikov static int
15168394ec8SAlexander V. Chernikov ta_init_radix(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
15268394ec8SAlexander V. Chernikov     char *data)
1539f7d47b0SAlexander V. Chernikov {
1549f7d47b0SAlexander V. Chernikov 
1559f7d47b0SAlexander V. Chernikov 	if (!rn_inithead(&ti->state, OFF_LEN_INET))
1569f7d47b0SAlexander V. Chernikov 		return (ENOMEM);
1579f7d47b0SAlexander V. Chernikov 	if (!rn_inithead(&ti->xstate, OFF_LEN_INET6)) {
1589f7d47b0SAlexander V. Chernikov 		rn_detachhead(&ti->state);
1599f7d47b0SAlexander V. Chernikov 		return (ENOMEM);
1609f7d47b0SAlexander V. Chernikov 	}
1619f7d47b0SAlexander V. Chernikov 
1629f7d47b0SAlexander V. Chernikov 	*ta_state = NULL;
1639f7d47b0SAlexander V. Chernikov 	ti->lookup = ta_lookup_radix;
1649f7d47b0SAlexander V. Chernikov 
1659f7d47b0SAlexander V. Chernikov 	return (0);
1669f7d47b0SAlexander V. Chernikov }
1679f7d47b0SAlexander V. Chernikov 
1689f7d47b0SAlexander V. Chernikov static int
1699f7d47b0SAlexander V. Chernikov flush_table_entry(struct radix_node *rn, void *arg)
1709f7d47b0SAlexander V. Chernikov {
1719f7d47b0SAlexander V. Chernikov 	struct radix_node_head * const rnh = arg;
172e0a8b9eeSAlexander V. Chernikov 	struct radix_cidr_entry *ent;
1739f7d47b0SAlexander V. Chernikov 
174e0a8b9eeSAlexander V. Chernikov 	ent = (struct radix_cidr_entry *)
1759f7d47b0SAlexander V. Chernikov 	    rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);
1769f7d47b0SAlexander V. Chernikov 	if (ent != NULL)
1779f7d47b0SAlexander V. Chernikov 		free(ent, M_IPFW_TBL);
1789f7d47b0SAlexander V. Chernikov 	return (0);
1799f7d47b0SAlexander V. Chernikov }
1809f7d47b0SAlexander V. Chernikov 
1819f7d47b0SAlexander V. Chernikov static void
1829f7d47b0SAlexander V. Chernikov ta_destroy_radix(void *ta_state, struct table_info *ti)
1839f7d47b0SAlexander V. Chernikov {
1849f7d47b0SAlexander V. Chernikov 	struct radix_node_head *rnh;
1859f7d47b0SAlexander V. Chernikov 
1869f7d47b0SAlexander V. Chernikov 	rnh = (struct radix_node_head *)(ti->state);
1879f7d47b0SAlexander V. Chernikov 	rnh->rnh_walktree(rnh, flush_table_entry, rnh);
1889f7d47b0SAlexander V. Chernikov 	rn_detachhead(&ti->state);
1899f7d47b0SAlexander V. Chernikov 
1909f7d47b0SAlexander V. Chernikov 	rnh = (struct radix_node_head *)(ti->xstate);
1919f7d47b0SAlexander V. Chernikov 	rnh->rnh_walktree(rnh, flush_table_entry, rnh);
1929f7d47b0SAlexander V. Chernikov 	rn_detachhead(&ti->xstate);
1939f7d47b0SAlexander V. Chernikov }
1949f7d47b0SAlexander V. Chernikov 
1959f7d47b0SAlexander V. Chernikov static int
19681d3153dSAlexander V. Chernikov ta_dump_radix_tentry(void *ta_state, struct table_info *ti, void *e,
19781d3153dSAlexander V. Chernikov     ipfw_obj_tentry *tent)
1989f7d47b0SAlexander V. Chernikov {
199e0a8b9eeSAlexander V. Chernikov 	struct radix_cidr_entry *n;
200e0a8b9eeSAlexander V. Chernikov 	struct radix_cidr_xentry *xn;
2019f7d47b0SAlexander V. Chernikov 
202e0a8b9eeSAlexander V. Chernikov 	n = (struct radix_cidr_entry *)e;
2039f7d47b0SAlexander V. Chernikov 
2049f7d47b0SAlexander V. Chernikov 	/* Guess IPv4/IPv6 radix by sockaddr family */
2059f7d47b0SAlexander V. Chernikov 	if (n->addr.sin_family == AF_INET) {
20681d3153dSAlexander V. Chernikov 		tent->k.addr.s_addr = n->addr.sin_addr.s_addr;
207e0a8b9eeSAlexander V. Chernikov 		tent->masklen = n->masklen;
20881d3153dSAlexander V. Chernikov 		tent->subtype = AF_INET;
20981d3153dSAlexander V. Chernikov 		tent->value = n->value;
2109f7d47b0SAlexander V. Chernikov #ifdef INET6
2119f7d47b0SAlexander V. Chernikov 	} else {
212e0a8b9eeSAlexander V. Chernikov 		xn = (struct radix_cidr_xentry *)e;
213e0a8b9eeSAlexander V. Chernikov 		memcpy(&tent->k, &xn->addr6.sin6_addr, sizeof(struct in6_addr));
214e0a8b9eeSAlexander V. Chernikov 		tent->masklen = xn->masklen;
21581d3153dSAlexander V. Chernikov 		tent->subtype = AF_INET6;
21681d3153dSAlexander V. Chernikov 		tent->value = xn->value;
2179f7d47b0SAlexander V. Chernikov #endif
2189f7d47b0SAlexander V. Chernikov 	}
2199f7d47b0SAlexander V. Chernikov 
2209f7d47b0SAlexander V. Chernikov 	return (0);
2219f7d47b0SAlexander V. Chernikov }
2229f7d47b0SAlexander V. Chernikov 
22381d3153dSAlexander V. Chernikov static int
22481d3153dSAlexander V. Chernikov ta_find_radix_tentry(void *ta_state, struct table_info *ti, void *key,
22581d3153dSAlexander V. Chernikov     uint32_t keylen, ipfw_obj_tentry *tent)
22681d3153dSAlexander V. Chernikov {
22781d3153dSAlexander V. Chernikov 	struct radix_node_head *rnh;
22881d3153dSAlexander V. Chernikov 	void *e;
22981d3153dSAlexander V. Chernikov 
23081d3153dSAlexander V. Chernikov 	e = NULL;
23181d3153dSAlexander V. Chernikov 	if (keylen == sizeof(in_addr_t)) {
23281d3153dSAlexander V. Chernikov 		struct sockaddr_in sa;
23381d3153dSAlexander V. Chernikov 		KEY_LEN(sa) = KEY_LEN_INET;
23481d3153dSAlexander V. Chernikov 		sa.sin_addr.s_addr = *((in_addr_t *)key);
23581d3153dSAlexander V. Chernikov 		rnh = (struct radix_node_head *)ti->state;
23681d3153dSAlexander V. Chernikov 		e = rnh->rnh_matchaddr(&sa, rnh);
23781d3153dSAlexander V. Chernikov 	} else {
238e0a8b9eeSAlexander V. Chernikov 		struct sa_in6 sa6;
23981d3153dSAlexander V. Chernikov 		KEY_LEN(sa6) = KEY_LEN_INET6;
24081d3153dSAlexander V. Chernikov 		memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
24181d3153dSAlexander V. Chernikov 		rnh = (struct radix_node_head *)ti->xstate;
24281d3153dSAlexander V. Chernikov 		e = rnh->rnh_matchaddr(&sa6, rnh);
24381d3153dSAlexander V. Chernikov 	}
24481d3153dSAlexander V. Chernikov 
24581d3153dSAlexander V. Chernikov 	if (e != NULL) {
24681d3153dSAlexander V. Chernikov 		ta_dump_radix_tentry(ta_state, ti, e, tent);
24781d3153dSAlexander V. Chernikov 		return (0);
24881d3153dSAlexander V. Chernikov 	}
24981d3153dSAlexander V. Chernikov 
25081d3153dSAlexander V. Chernikov 	return (ENOENT);
25181d3153dSAlexander V. Chernikov }
25281d3153dSAlexander V. Chernikov 
2539f7d47b0SAlexander V. Chernikov static void
2549f7d47b0SAlexander V. Chernikov ta_foreach_radix(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2559f7d47b0SAlexander V. Chernikov     void *arg)
2569f7d47b0SAlexander V. Chernikov {
2579f7d47b0SAlexander V. Chernikov 	struct radix_node_head *rnh;
2589f7d47b0SAlexander V. Chernikov 
2599f7d47b0SAlexander V. Chernikov 	rnh = (struct radix_node_head *)(ti->state);
2609f7d47b0SAlexander V. Chernikov 	rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg);
2619f7d47b0SAlexander V. Chernikov 
2629f7d47b0SAlexander V. Chernikov 	rnh = (struct radix_node_head *)(ti->xstate);
2639f7d47b0SAlexander V. Chernikov 	rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg);
2649f7d47b0SAlexander V. Chernikov }
2659f7d47b0SAlexander V. Chernikov 
2669f7d47b0SAlexander V. Chernikov 
2679f7d47b0SAlexander V. Chernikov struct ta_buf_cidr
2689f7d47b0SAlexander V. Chernikov {
2699f7d47b0SAlexander V. Chernikov 	struct sockaddr	*addr_ptr;
2709f7d47b0SAlexander V. Chernikov 	struct sockaddr	*mask_ptr;
2719f7d47b0SAlexander V. Chernikov 	void *ent_ptr;
2729f7d47b0SAlexander V. Chernikov 	union {
2739f7d47b0SAlexander V. Chernikov 		struct {
2749f7d47b0SAlexander V. Chernikov 			struct sockaddr_in sa;
2759f7d47b0SAlexander V. Chernikov 			struct sockaddr_in ma;
2769f7d47b0SAlexander V. Chernikov 		} a4;
2779f7d47b0SAlexander V. Chernikov 		struct {
278e0a8b9eeSAlexander V. Chernikov 			struct sa_in6 sa;
279e0a8b9eeSAlexander V. Chernikov 			struct sa_in6 ma;
2809f7d47b0SAlexander V. Chernikov 		} a6;
2819f7d47b0SAlexander V. Chernikov 	} addr;
2829f7d47b0SAlexander V. Chernikov };
2839f7d47b0SAlexander V. Chernikov 
2849f7d47b0SAlexander V. Chernikov #ifdef INET6
2859f7d47b0SAlexander V. Chernikov static inline void
2869f7d47b0SAlexander V. Chernikov ipv6_writemask(struct in6_addr *addr6, uint8_t mask)
2879f7d47b0SAlexander V. Chernikov {
2889f7d47b0SAlexander V. Chernikov 	uint32_t *cp;
2899f7d47b0SAlexander V. Chernikov 
2909f7d47b0SAlexander V. Chernikov 	for (cp = (uint32_t *)addr6; mask >= 32; mask -= 32)
2919f7d47b0SAlexander V. Chernikov 		*cp++ = 0xFFFFFFFF;
2929f7d47b0SAlexander V. Chernikov 	*cp = htonl(mask ? ~((1 << (32 - mask)) - 1) : 0);
2939f7d47b0SAlexander V. Chernikov }
2949f7d47b0SAlexander V. Chernikov #endif
2959f7d47b0SAlexander V. Chernikov 
2969f7d47b0SAlexander V. Chernikov 
2979f7d47b0SAlexander V. Chernikov static int
29868394ec8SAlexander V. Chernikov ta_prepare_add_cidr(struct ip_fw_chain *ch, struct tentry_info *tei,
29968394ec8SAlexander V. Chernikov     void *ta_buf)
3009f7d47b0SAlexander V. Chernikov {
3019f7d47b0SAlexander V. Chernikov 	struct ta_buf_cidr *tb;
302e0a8b9eeSAlexander V. Chernikov 	struct radix_cidr_entry *ent;
303e0a8b9eeSAlexander V. Chernikov 	struct radix_cidr_xentry *xent;
3049f7d47b0SAlexander V. Chernikov 	in_addr_t addr;
305e0a8b9eeSAlexander V. Chernikov 	struct sockaddr_in *mask;
306e0a8b9eeSAlexander V. Chernikov 	struct sa_in6 *mask6;
3079f7d47b0SAlexander V. Chernikov 	int mlen;
3089f7d47b0SAlexander V. Chernikov 
3099f7d47b0SAlexander V. Chernikov 	tb = (struct ta_buf_cidr *)ta_buf;
3109f7d47b0SAlexander V. Chernikov 	memset(tb, 0, sizeof(struct ta_buf_cidr));
3119f7d47b0SAlexander V. Chernikov 
3129f7d47b0SAlexander V. Chernikov 	mlen = tei->masklen;
3139f7d47b0SAlexander V. Chernikov 
314ac35ff17SAlexander V. Chernikov 	if (tei->subtype == AF_INET) {
3159f7d47b0SAlexander V. Chernikov #ifdef INET
3169f7d47b0SAlexander V. Chernikov 		if (mlen > 32)
3179f7d47b0SAlexander V. Chernikov 			return (EINVAL);
3189f7d47b0SAlexander V. Chernikov 		ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
3199f7d47b0SAlexander V. Chernikov 		ent->value = tei->value;
320e0a8b9eeSAlexander V. Chernikov 		mask = &tb->addr.a4.ma;
3219f7d47b0SAlexander V. Chernikov 		/* Set 'total' structure length */
3229f7d47b0SAlexander V. Chernikov 		KEY_LEN(ent->addr) = KEY_LEN_INET;
323e0a8b9eeSAlexander V. Chernikov 		KEY_LEN(*mask) = KEY_LEN_INET;
3249f7d47b0SAlexander V. Chernikov 		ent->addr.sin_family = AF_INET;
325e0a8b9eeSAlexander V. Chernikov 		mask->sin_addr.s_addr =
3269f7d47b0SAlexander V. Chernikov 		    htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
3279f7d47b0SAlexander V. Chernikov 		addr = *((in_addr_t *)tei->paddr);
328e0a8b9eeSAlexander V. Chernikov 		ent->addr.sin_addr.s_addr = addr & mask->sin_addr.s_addr;
329e0a8b9eeSAlexander V. Chernikov 		ent->masklen = mlen;
3309f7d47b0SAlexander V. Chernikov 		/* Set pointers */
3319f7d47b0SAlexander V. Chernikov 		tb->ent_ptr = ent;
3329f7d47b0SAlexander V. Chernikov 		tb->addr_ptr = (struct sockaddr *)&ent->addr;
333e0a8b9eeSAlexander V. Chernikov 		if (mlen != 32)
334e0a8b9eeSAlexander V. Chernikov 			tb->mask_ptr = (struct sockaddr *)mask;
3359f7d47b0SAlexander V. Chernikov #endif
3369f7d47b0SAlexander V. Chernikov #ifdef INET6
337ac35ff17SAlexander V. Chernikov 	} else if (tei->subtype == AF_INET6) {
3389f7d47b0SAlexander V. Chernikov 		/* IPv6 case */
3399f7d47b0SAlexander V. Chernikov 		if (mlen > 128)
3409f7d47b0SAlexander V. Chernikov 			return (EINVAL);
3419f7d47b0SAlexander V. Chernikov 		xent = malloc(sizeof(*xent), M_IPFW_TBL, M_WAITOK | M_ZERO);
3429f7d47b0SAlexander V. Chernikov 		xent->value = tei->value;
343e0a8b9eeSAlexander V. Chernikov 		mask6 = &tb->addr.a6.ma;
3449f7d47b0SAlexander V. Chernikov 		/* Set 'total' structure length */
345e0a8b9eeSAlexander V. Chernikov 		KEY_LEN(xent->addr6) = KEY_LEN_INET6;
346e0a8b9eeSAlexander V. Chernikov 		KEY_LEN(*mask6) = KEY_LEN_INET6;
347e0a8b9eeSAlexander V. Chernikov 		xent->addr6.sin6_family = AF_INET6;
348e0a8b9eeSAlexander V. Chernikov 		ipv6_writemask(&mask6->sin6_addr, mlen);
349e0a8b9eeSAlexander V. Chernikov 		memcpy(&xent->addr6.sin6_addr, tei->paddr,
3509f7d47b0SAlexander V. Chernikov 		    sizeof(struct in6_addr));
351e0a8b9eeSAlexander V. Chernikov 		APPLY_MASK(&xent->addr6.sin6_addr, &mask6->sin6_addr);
352e0a8b9eeSAlexander V. Chernikov 		xent->masklen = mlen;
3539f7d47b0SAlexander V. Chernikov 		/* Set pointers */
3549f7d47b0SAlexander V. Chernikov 		tb->ent_ptr = xent;
355e0a8b9eeSAlexander V. Chernikov 		tb->addr_ptr = (struct sockaddr *)&xent->addr6;
356e0a8b9eeSAlexander V. Chernikov 		if (mlen != 128)
357e0a8b9eeSAlexander V. Chernikov 			tb->mask_ptr = (struct sockaddr *)mask6;
3589f7d47b0SAlexander V. Chernikov #endif
3599f7d47b0SAlexander V. Chernikov 	} else {
3609f7d47b0SAlexander V. Chernikov 		/* Unknown CIDR type */
3619f7d47b0SAlexander V. Chernikov 		return (EINVAL);
3629f7d47b0SAlexander V. Chernikov 	}
3639f7d47b0SAlexander V. Chernikov 
3649f7d47b0SAlexander V. Chernikov 	return (0);
3659f7d47b0SAlexander V. Chernikov }
3669f7d47b0SAlexander V. Chernikov 
3679f7d47b0SAlexander V. Chernikov static int
368adea6201SAlexander V. Chernikov ta_add_cidr(void *ta_state, struct table_info *ti, struct tentry_info *tei,
369adea6201SAlexander V. Chernikov     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
3709f7d47b0SAlexander V. Chernikov {
3719f7d47b0SAlexander V. Chernikov 	struct radix_node_head *rnh;
3729f7d47b0SAlexander V. Chernikov 	struct radix_node *rn;
3739f7d47b0SAlexander V. Chernikov 	struct ta_buf_cidr *tb;
374ac35ff17SAlexander V. Chernikov 	uint32_t value;
3759f7d47b0SAlexander V. Chernikov 
3769f7d47b0SAlexander V. Chernikov 	tb = (struct ta_buf_cidr *)ta_buf;
3779f7d47b0SAlexander V. Chernikov 
378ac35ff17SAlexander V. Chernikov 	if (tei->subtype == AF_INET)
3799f7d47b0SAlexander V. Chernikov 		rnh = ti->state;
3809f7d47b0SAlexander V. Chernikov 	else
3819f7d47b0SAlexander V. Chernikov 		rnh = ti->xstate;
3829f7d47b0SAlexander V. Chernikov 
3839f7d47b0SAlexander V. Chernikov 	rn = rnh->rnh_addaddr(tb->addr_ptr, tb->mask_ptr, rnh, tb->ent_ptr);
3849f7d47b0SAlexander V. Chernikov 
385ac35ff17SAlexander V. Chernikov 	if (rn == NULL) {
386ac35ff17SAlexander V. Chernikov 		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
3879f7d47b0SAlexander V. Chernikov 			return (EEXIST);
388ac35ff17SAlexander V. Chernikov 		/* Record already exists. Update value if we're asked to */
389ac35ff17SAlexander V. Chernikov 		rn = rnh->rnh_lookup(tb->addr_ptr, tb->mask_ptr, rnh);
390ac35ff17SAlexander V. Chernikov 		if (rn == NULL) {
391ac35ff17SAlexander V. Chernikov 
392ac35ff17SAlexander V. Chernikov 			/*
393ac35ff17SAlexander V. Chernikov 			 * Radix may have failed addition for other reasons
394ac35ff17SAlexander V. Chernikov 			 * like failure in mask allocation code.
395ac35ff17SAlexander V. Chernikov 			 */
396ac35ff17SAlexander V. Chernikov 			return (EINVAL);
397ac35ff17SAlexander V. Chernikov 		}
398ac35ff17SAlexander V. Chernikov 
399ac35ff17SAlexander V. Chernikov 		if (tei->subtype == AF_INET) {
400ac35ff17SAlexander V. Chernikov 			/* IPv4. */
401e0a8b9eeSAlexander V. Chernikov 			value = ((struct radix_cidr_entry *)tb->ent_ptr)->value;
402e0a8b9eeSAlexander V. Chernikov 			((struct radix_cidr_entry *)rn)->value = value;
403ac35ff17SAlexander V. Chernikov 		} else {
404ac35ff17SAlexander V. Chernikov 			/* IPv6 */
405e0a8b9eeSAlexander V. Chernikov 			value = ((struct radix_cidr_xentry *)tb->ent_ptr)->value;
406e0a8b9eeSAlexander V. Chernikov 			((struct radix_cidr_xentry *)rn)->value = value;
407ac35ff17SAlexander V. Chernikov 		}
408ac35ff17SAlexander V. Chernikov 
409ac35ff17SAlexander V. Chernikov 		/* Indicate that update has happened instead of addition */
410ac35ff17SAlexander V. Chernikov 		tei->flags |= TEI_FLAGS_UPDATED;
411adea6201SAlexander V. Chernikov 		*pnum = 0;
412e0a8b9eeSAlexander V. Chernikov 
413e0a8b9eeSAlexander V. Chernikov 		return (0);
414ac35ff17SAlexander V. Chernikov 	}
415ac35ff17SAlexander V. Chernikov 
416ac35ff17SAlexander V. Chernikov 	tb->ent_ptr = NULL;
417adea6201SAlexander V. Chernikov 	*pnum = 1;
4189f7d47b0SAlexander V. Chernikov 
4199f7d47b0SAlexander V. Chernikov 	return (0);
4209f7d47b0SAlexander V. Chernikov }
4219f7d47b0SAlexander V. Chernikov 
4229f7d47b0SAlexander V. Chernikov static int
42368394ec8SAlexander V. Chernikov ta_prepare_del_cidr(struct ip_fw_chain *ch, struct tentry_info *tei,
42468394ec8SAlexander V. Chernikov     void *ta_buf)
4259f7d47b0SAlexander V. Chernikov {
4269f7d47b0SAlexander V. Chernikov 	struct ta_buf_cidr *tb;
427e0a8b9eeSAlexander V. Chernikov 	struct sockaddr_in sa, mask;
428e0a8b9eeSAlexander V. Chernikov 	struct sa_in6 sa6, mask6;
4299f7d47b0SAlexander V. Chernikov 	in_addr_t addr;
4309f7d47b0SAlexander V. Chernikov 	int mlen;
4319f7d47b0SAlexander V. Chernikov 
4329f7d47b0SAlexander V. Chernikov 	tb = (struct ta_buf_cidr *)ta_buf;
4339f7d47b0SAlexander V. Chernikov 	memset(tb, 0, sizeof(struct ta_buf_cidr));
4349f7d47b0SAlexander V. Chernikov 
4359f7d47b0SAlexander V. Chernikov 	mlen = tei->masklen;
4369f7d47b0SAlexander V. Chernikov 
437ac35ff17SAlexander V. Chernikov 	if (tei->subtype == AF_INET) {
438e0a8b9eeSAlexander V. Chernikov 		if (mlen > 32)
439e0a8b9eeSAlexander V. Chernikov 			return (EINVAL);
440e0a8b9eeSAlexander V. Chernikov 		memset(&sa, 0, sizeof(struct sockaddr_in));
441e0a8b9eeSAlexander V. Chernikov 		memset(&mask, 0, sizeof(struct sockaddr_in));
4429f7d47b0SAlexander V. Chernikov 		/* Set 'total' structure length */
4439f7d47b0SAlexander V. Chernikov 		KEY_LEN(sa) = KEY_LEN_INET;
4449f7d47b0SAlexander V. Chernikov 		KEY_LEN(mask) = KEY_LEN_INET;
4459f7d47b0SAlexander V. Chernikov 		mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
4469f7d47b0SAlexander V. Chernikov 		addr = *((in_addr_t *)tei->paddr);
4479f7d47b0SAlexander V. Chernikov 		sa.sin_addr.s_addr = addr & mask.sin_addr.s_addr;
4489f7d47b0SAlexander V. Chernikov 		tb->addr.a4.sa = sa;
4499f7d47b0SAlexander V. Chernikov 		tb->addr.a4.ma = mask;
4509f7d47b0SAlexander V. Chernikov 		tb->addr_ptr = (struct sockaddr *)&tb->addr.a4.sa;
451e0a8b9eeSAlexander V. Chernikov 		if (mlen != 32)
4529f7d47b0SAlexander V. Chernikov 			tb->mask_ptr = (struct sockaddr *)&tb->addr.a4.ma;
4539f7d47b0SAlexander V. Chernikov #ifdef INET6
454ac35ff17SAlexander V. Chernikov 	} else if (tei->subtype == AF_INET6) {
4559f7d47b0SAlexander V. Chernikov 		if (mlen > 128)
4569f7d47b0SAlexander V. Chernikov 			return (EINVAL);
457e0a8b9eeSAlexander V. Chernikov 		memset(&sa6, 0, sizeof(struct sa_in6));
458e0a8b9eeSAlexander V. Chernikov 		memset(&mask6, 0, sizeof(struct sa_in6));
4599f7d47b0SAlexander V. Chernikov 		/* Set 'total' structure length */
4609f7d47b0SAlexander V. Chernikov 		KEY_LEN(sa6) = KEY_LEN_INET6;
4619f7d47b0SAlexander V. Chernikov 		KEY_LEN(mask6) = KEY_LEN_INET6;
4629f7d47b0SAlexander V. Chernikov 		ipv6_writemask(&mask6.sin6_addr, mlen);
4639f7d47b0SAlexander V. Chernikov 		memcpy(&sa6.sin6_addr, tei->paddr,
4649f7d47b0SAlexander V. Chernikov 		    sizeof(struct in6_addr));
4659f7d47b0SAlexander V. Chernikov 		APPLY_MASK(&sa6.sin6_addr, &mask6.sin6_addr);
4669f7d47b0SAlexander V. Chernikov 		tb->addr.a6.sa = sa6;
4679f7d47b0SAlexander V. Chernikov 		tb->addr.a6.ma = mask6;
4689f7d47b0SAlexander V. Chernikov 		tb->addr_ptr = (struct sockaddr *)&tb->addr.a6.sa;
469e0a8b9eeSAlexander V. Chernikov 		if (mlen != 128)
4709f7d47b0SAlexander V. Chernikov 			tb->mask_ptr = (struct sockaddr *)&tb->addr.a6.ma;
4719f7d47b0SAlexander V. Chernikov #endif
4729f7d47b0SAlexander V. Chernikov 	} else
4739f7d47b0SAlexander V. Chernikov 		return (EINVAL);
4749f7d47b0SAlexander V. Chernikov 
4759f7d47b0SAlexander V. Chernikov 	return (0);
4769f7d47b0SAlexander V. Chernikov }
4779f7d47b0SAlexander V. Chernikov 
4789f7d47b0SAlexander V. Chernikov static int
479adea6201SAlexander V. Chernikov ta_del_cidr(void *ta_state, struct table_info *ti, struct tentry_info *tei,
480adea6201SAlexander V. Chernikov     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
4819f7d47b0SAlexander V. Chernikov {
4829f7d47b0SAlexander V. Chernikov 	struct radix_node_head *rnh;
4839f7d47b0SAlexander V. Chernikov 	struct radix_node *rn;
4849f7d47b0SAlexander V. Chernikov 	struct ta_buf_cidr *tb;
4859f7d47b0SAlexander V. Chernikov 
4869f7d47b0SAlexander V. Chernikov 	tb = (struct ta_buf_cidr *)ta_buf;
4879f7d47b0SAlexander V. Chernikov 
488ac35ff17SAlexander V. Chernikov 	if (tei->subtype == AF_INET)
4899f7d47b0SAlexander V. Chernikov 		rnh = ti->state;
4909f7d47b0SAlexander V. Chernikov 	else
4919f7d47b0SAlexander V. Chernikov 		rnh = ti->xstate;
4929f7d47b0SAlexander V. Chernikov 
4939f7d47b0SAlexander V. Chernikov 	rn = rnh->rnh_deladdr(tb->addr_ptr, tb->mask_ptr, rnh);
4949f7d47b0SAlexander V. Chernikov 
4959f7d47b0SAlexander V. Chernikov 	tb->ent_ptr = rn;
4969f7d47b0SAlexander V. Chernikov 
4979f7d47b0SAlexander V. Chernikov 	if (rn == NULL)
49881d3153dSAlexander V. Chernikov 		return (ENOENT);
4999f7d47b0SAlexander V. Chernikov 
500adea6201SAlexander V. Chernikov 	*pnum = 1;
501adea6201SAlexander V. Chernikov 
5029f7d47b0SAlexander V. Chernikov 	return (0);
5039f7d47b0SAlexander V. Chernikov }
5049f7d47b0SAlexander V. Chernikov 
5059f7d47b0SAlexander V. Chernikov static void
50668394ec8SAlexander V. Chernikov ta_flush_cidr_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
50768394ec8SAlexander V. Chernikov     void *ta_buf)
5089f7d47b0SAlexander V. Chernikov {
5099f7d47b0SAlexander V. Chernikov 	struct ta_buf_cidr *tb;
5109f7d47b0SAlexander V. Chernikov 
5119f7d47b0SAlexander V. Chernikov 	tb = (struct ta_buf_cidr *)ta_buf;
5129f7d47b0SAlexander V. Chernikov 
513ac35ff17SAlexander V. Chernikov 	if (tb->ent_ptr != NULL)
5149f7d47b0SAlexander V. Chernikov 		free(tb->ent_ptr, M_IPFW_TBL);
5159f7d47b0SAlexander V. Chernikov }
5169f7d47b0SAlexander V. Chernikov 
517*74b941f0SAlexander V. Chernikov struct table_algo cidr_radix = {
518adea6201SAlexander V. Chernikov 	.name		= "cidr:radix",
5199f7d47b0SAlexander V. Chernikov 	.lookup		= ta_lookup_radix,
5209f7d47b0SAlexander V. Chernikov 	.init		= ta_init_radix,
5219f7d47b0SAlexander V. Chernikov 	.destroy	= ta_destroy_radix,
5229f7d47b0SAlexander V. Chernikov 	.prepare_add	= ta_prepare_add_cidr,
5239f7d47b0SAlexander V. Chernikov 	.prepare_del	= ta_prepare_del_cidr,
5249f7d47b0SAlexander V. Chernikov 	.add		= ta_add_cidr,
5259f7d47b0SAlexander V. Chernikov 	.del		= ta_del_cidr,
5269f7d47b0SAlexander V. Chernikov 	.flush_entry	= ta_flush_cidr_entry,
5279f7d47b0SAlexander V. Chernikov 	.foreach	= ta_foreach_radix,
52881d3153dSAlexander V. Chernikov 	.dump_tentry	= ta_dump_radix_tentry,
52981d3153dSAlexander V. Chernikov 	.find_tentry	= ta_find_radix_tentry,
5309f7d47b0SAlexander V. Chernikov };
5319f7d47b0SAlexander V. Chernikov 
5329f7d47b0SAlexander V. Chernikov 
5339f7d47b0SAlexander V. Chernikov /*
534*74b941f0SAlexander V. Chernikov  * cidr:hash cmds
535*74b941f0SAlexander V. Chernikov  *
536*74b941f0SAlexander V. Chernikov  *
537*74b941f0SAlexander V. Chernikov  * ti->data:
538*74b941f0SAlexander V. Chernikov  * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
539*74b941f0SAlexander V. Chernikov  * [        8][        8[          8][         8]
540*74b941f0SAlexander V. Chernikov  *
541*74b941f0SAlexander V. Chernikov  * inv.mask4: 32 - mask
542*74b941f0SAlexander V. Chernikov  * inv.mask6:
543*74b941f0SAlexander V. Chernikov  * 1) _slow lookup: mask
544*74b941f0SAlexander V. Chernikov  * 2) _aligned: (128 - mask) / 8
545*74b941f0SAlexander V. Chernikov  * 3) _64: 8
546*74b941f0SAlexander V. Chernikov  */
547*74b941f0SAlexander V. Chernikov 
548*74b941f0SAlexander V. Chernikov struct chashentry;
549*74b941f0SAlexander V. Chernikov 
550*74b941f0SAlexander V. Chernikov SLIST_HEAD(chashbhead, chashentry);
551*74b941f0SAlexander V. Chernikov 
552*74b941f0SAlexander V. Chernikov struct chash_cfg {
553*74b941f0SAlexander V. Chernikov 	struct chashbhead *head4;
554*74b941f0SAlexander V. Chernikov 	struct chashbhead *head6;
555*74b941f0SAlexander V. Chernikov 	size_t	size4;
556*74b941f0SAlexander V. Chernikov 	size_t	size6;
557*74b941f0SAlexander V. Chernikov 	size_t	items;
558*74b941f0SAlexander V. Chernikov 	uint8_t	mask4;
559*74b941f0SAlexander V. Chernikov 	uint8_t	mask6;
560*74b941f0SAlexander V. Chernikov };
561*74b941f0SAlexander V. Chernikov 
562*74b941f0SAlexander V. Chernikov struct chashentry {
563*74b941f0SAlexander V. Chernikov 	SLIST_ENTRY(chashentry)	next;
564*74b941f0SAlexander V. Chernikov 	uint32_t	value;
565*74b941f0SAlexander V. Chernikov 	uint32_t	type;
566*74b941f0SAlexander V. Chernikov 	union {
567*74b941f0SAlexander V. Chernikov 		uint32_t	a4;	/* Host format */
568*74b941f0SAlexander V. Chernikov 		struct in6_addr	a6;	/* Network format */
569*74b941f0SAlexander V. Chernikov 	} a;
570*74b941f0SAlexander V. Chernikov };
571*74b941f0SAlexander V. Chernikov 
572*74b941f0SAlexander V. Chernikov static __inline uint32_t
573*74b941f0SAlexander V. Chernikov hash_ip(uint32_t addr, int hsize)
574*74b941f0SAlexander V. Chernikov {
575*74b941f0SAlexander V. Chernikov 
576*74b941f0SAlexander V. Chernikov 	return (addr % (hsize - 1));
577*74b941f0SAlexander V. Chernikov }
578*74b941f0SAlexander V. Chernikov 
579*74b941f0SAlexander V. Chernikov static __inline uint32_t
580*74b941f0SAlexander V. Chernikov hash_ip6(struct in6_addr *addr6, int hsize)
581*74b941f0SAlexander V. Chernikov {
582*74b941f0SAlexander V. Chernikov 	uint32_t i;
583*74b941f0SAlexander V. Chernikov 
584*74b941f0SAlexander V. Chernikov 	i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1] ^
585*74b941f0SAlexander V. Chernikov 	    addr6->s6_addr32[2] ^ addr6->s6_addr32[3];
586*74b941f0SAlexander V. Chernikov 
587*74b941f0SAlexander V. Chernikov 	return (i % (hsize - 1));
588*74b941f0SAlexander V. Chernikov }
589*74b941f0SAlexander V. Chernikov 
590*74b941f0SAlexander V. Chernikov 
591*74b941f0SAlexander V. Chernikov static __inline uint16_t
592*74b941f0SAlexander V. Chernikov hash_ip64(struct in6_addr *addr6, int hsize)
593*74b941f0SAlexander V. Chernikov {
594*74b941f0SAlexander V. Chernikov 	uint32_t i;
595*74b941f0SAlexander V. Chernikov 
596*74b941f0SAlexander V. Chernikov 	i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1];
597*74b941f0SAlexander V. Chernikov 
598*74b941f0SAlexander V. Chernikov 	return (i % (hsize - 1));
599*74b941f0SAlexander V. Chernikov }
600*74b941f0SAlexander V. Chernikov 
601*74b941f0SAlexander V. Chernikov 
602*74b941f0SAlexander V. Chernikov static __inline uint32_t
603*74b941f0SAlexander V. Chernikov hash_ip6_slow(struct in6_addr *addr6, void *key, int mask, int hsize)
604*74b941f0SAlexander V. Chernikov {
605*74b941f0SAlexander V. Chernikov 	struct in6_addr mask6;
606*74b941f0SAlexander V. Chernikov 
607*74b941f0SAlexander V. Chernikov 	ipv6_writemask(&mask6, mask);
608*74b941f0SAlexander V. Chernikov 	memcpy(addr6, key, sizeof(struct in6_addr));
609*74b941f0SAlexander V. Chernikov 	APPLY_MASK(addr6, &mask6);
610*74b941f0SAlexander V. Chernikov 	return (hash_ip6(addr6, hsize));
611*74b941f0SAlexander V. Chernikov }
612*74b941f0SAlexander V. Chernikov 
613*74b941f0SAlexander V. Chernikov static __inline uint32_t
614*74b941f0SAlexander V. Chernikov hash_ip6_al(struct in6_addr *addr6, void *key, int mask, int hsize)
615*74b941f0SAlexander V. Chernikov {
616*74b941f0SAlexander V. Chernikov 	uint64_t *paddr;
617*74b941f0SAlexander V. Chernikov 
618*74b941f0SAlexander V. Chernikov 	paddr = (uint64_t *)addr6;
619*74b941f0SAlexander V. Chernikov 	*paddr = 0;
620*74b941f0SAlexander V. Chernikov 	*(paddr + 1) = 0;
621*74b941f0SAlexander V. Chernikov 	memcpy(addr6, key, mask);
622*74b941f0SAlexander V. Chernikov 	return (hash_ip6(addr6, hsize));
623*74b941f0SAlexander V. Chernikov }
624*74b941f0SAlexander V. Chernikov 
625*74b941f0SAlexander V. Chernikov static int
626*74b941f0SAlexander V. Chernikov ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
627*74b941f0SAlexander V. Chernikov     uint32_t *val)
628*74b941f0SAlexander V. Chernikov {
629*74b941f0SAlexander V. Chernikov 	struct chashbhead *head;
630*74b941f0SAlexander V. Chernikov 	struct chashentry *ent;
631*74b941f0SAlexander V. Chernikov 	uint16_t hash, hsize;
632*74b941f0SAlexander V. Chernikov 	uint8_t imask;
633*74b941f0SAlexander V. Chernikov 
634*74b941f0SAlexander V. Chernikov 	if (keylen == sizeof(in_addr_t)) {
635*74b941f0SAlexander V. Chernikov 		head = (struct chashbhead *)ti->state;
636*74b941f0SAlexander V. Chernikov 		imask = ti->data >> 24;
637*74b941f0SAlexander V. Chernikov 		hsize = 1 << ((ti->data & 0xFFFF) >> 8);
638*74b941f0SAlexander V. Chernikov 		uint32_t a;
639*74b941f0SAlexander V. Chernikov 		a = ntohl(*((in_addr_t *)key));
640*74b941f0SAlexander V. Chernikov 		a = a >> imask;
641*74b941f0SAlexander V. Chernikov 		hash = hash_ip(a, hsize);
642*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(ent, &head[hash], next) {
643*74b941f0SAlexander V. Chernikov 			if (ent->a.a4 == a) {
644*74b941f0SAlexander V. Chernikov 				*val = ent->value;
645*74b941f0SAlexander V. Chernikov 				return (1);
646*74b941f0SAlexander V. Chernikov 			}
647*74b941f0SAlexander V. Chernikov 		}
648*74b941f0SAlexander V. Chernikov 	} else {
649*74b941f0SAlexander V. Chernikov 		/* IPv6: worst scenario: non-round mask */
650*74b941f0SAlexander V. Chernikov 		struct in6_addr addr6;
651*74b941f0SAlexander V. Chernikov 		head = (struct chashbhead *)ti->xstate;
652*74b941f0SAlexander V. Chernikov 		imask = (ti->data & 0xFF0000) >> 16;
653*74b941f0SAlexander V. Chernikov 		hsize = 1 << (ti->data & 0xFF);
654*74b941f0SAlexander V. Chernikov 		hash = hash_ip6_slow(&addr6, key, imask, hsize);
655*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(ent, &head[hash], next) {
656*74b941f0SAlexander V. Chernikov 			if (memcmp(&ent->a.a6, &addr6, 16) == 0) {
657*74b941f0SAlexander V. Chernikov 				*val = ent->value;
658*74b941f0SAlexander V. Chernikov 				return (1);
659*74b941f0SAlexander V. Chernikov 			}
660*74b941f0SAlexander V. Chernikov 		}
661*74b941f0SAlexander V. Chernikov 	}
662*74b941f0SAlexander V. Chernikov 
663*74b941f0SAlexander V. Chernikov 	return (0);
664*74b941f0SAlexander V. Chernikov }
665*74b941f0SAlexander V. Chernikov 
666*74b941f0SAlexander V. Chernikov static int
667*74b941f0SAlexander V. Chernikov ta_lookup_chash_aligned(struct table_info *ti, void *key, uint32_t keylen,
668*74b941f0SAlexander V. Chernikov     uint32_t *val)
669*74b941f0SAlexander V. Chernikov {
670*74b941f0SAlexander V. Chernikov 	struct chashbhead *head;
671*74b941f0SAlexander V. Chernikov 	struct chashentry *ent;
672*74b941f0SAlexander V. Chernikov 	uint16_t hash, hsize;
673*74b941f0SAlexander V. Chernikov 	uint8_t imask;
674*74b941f0SAlexander V. Chernikov 
675*74b941f0SAlexander V. Chernikov 	if (keylen == sizeof(in_addr_t)) {
676*74b941f0SAlexander V. Chernikov 		head = (struct chashbhead *)ti->state;
677*74b941f0SAlexander V. Chernikov 		imask = ti->data >> 24;
678*74b941f0SAlexander V. Chernikov 		hsize = 1 << ((ti->data & 0xFFFF) >> 8);
679*74b941f0SAlexander V. Chernikov 		uint32_t a;
680*74b941f0SAlexander V. Chernikov 		a = ntohl(*((in_addr_t *)key));
681*74b941f0SAlexander V. Chernikov 		a = a >> imask;
682*74b941f0SAlexander V. Chernikov 		hash = hash_ip(a, hsize);
683*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(ent, &head[hash], next) {
684*74b941f0SAlexander V. Chernikov 			if (ent->a.a4 == a) {
685*74b941f0SAlexander V. Chernikov 				*val = ent->value;
686*74b941f0SAlexander V. Chernikov 				return (1);
687*74b941f0SAlexander V. Chernikov 			}
688*74b941f0SAlexander V. Chernikov 		}
689*74b941f0SAlexander V. Chernikov 	} else {
690*74b941f0SAlexander V. Chernikov 		/* IPv6: aligned to 8bit mask */
691*74b941f0SAlexander V. Chernikov 		struct in6_addr addr6;
692*74b941f0SAlexander V. Chernikov 		uint64_t *paddr, *ptmp;
693*74b941f0SAlexander V. Chernikov 		head = (struct chashbhead *)ti->xstate;
694*74b941f0SAlexander V. Chernikov 		imask = (ti->data & 0xFF0000) >> 16;
695*74b941f0SAlexander V. Chernikov 		hsize = 1 << (ti->data & 0xFF);
696*74b941f0SAlexander V. Chernikov 
697*74b941f0SAlexander V. Chernikov 		hash = hash_ip6_al(&addr6, key, imask, hsize);
698*74b941f0SAlexander V. Chernikov 		paddr = (uint64_t *)&addr6;
699*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(ent, &head[hash], next) {
700*74b941f0SAlexander V. Chernikov 			ptmp = (uint64_t *)&ent->a.a6;
701*74b941f0SAlexander V. Chernikov 			if (paddr[0] == ptmp[0] && paddr[1] == ptmp[1]) {
702*74b941f0SAlexander V. Chernikov 				*val = ent->value;
703*74b941f0SAlexander V. Chernikov 				return (1);
704*74b941f0SAlexander V. Chernikov 			}
705*74b941f0SAlexander V. Chernikov 		}
706*74b941f0SAlexander V. Chernikov 	}
707*74b941f0SAlexander V. Chernikov 
708*74b941f0SAlexander V. Chernikov 	return (0);
709*74b941f0SAlexander V. Chernikov }
710*74b941f0SAlexander V. Chernikov 
711*74b941f0SAlexander V. Chernikov static int
712*74b941f0SAlexander V. Chernikov ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
713*74b941f0SAlexander V. Chernikov     uint32_t *val)
714*74b941f0SAlexander V. Chernikov {
715*74b941f0SAlexander V. Chernikov 	struct chashbhead *head;
716*74b941f0SAlexander V. Chernikov 	struct chashentry *ent;
717*74b941f0SAlexander V. Chernikov 	uint16_t hash, hsize;
718*74b941f0SAlexander V. Chernikov 	uint8_t imask;
719*74b941f0SAlexander V. Chernikov 
720*74b941f0SAlexander V. Chernikov 	if (keylen == sizeof(in_addr_t)) {
721*74b941f0SAlexander V. Chernikov 		head = (struct chashbhead *)ti->state;
722*74b941f0SAlexander V. Chernikov 		imask = ti->data >> 24;
723*74b941f0SAlexander V. Chernikov 		hsize = 1 << ((ti->data & 0xFFFF) >> 8);
724*74b941f0SAlexander V. Chernikov 		uint32_t a;
725*74b941f0SAlexander V. Chernikov 		a = ntohl(*((in_addr_t *)key));
726*74b941f0SAlexander V. Chernikov 		a = a >> imask;
727*74b941f0SAlexander V. Chernikov 		hash = hash_ip(a, hsize);
728*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(ent, &head[hash], next) {
729*74b941f0SAlexander V. Chernikov 			if (ent->a.a4 == a) {
730*74b941f0SAlexander V. Chernikov 				*val = ent->value;
731*74b941f0SAlexander V. Chernikov 				return (1);
732*74b941f0SAlexander V. Chernikov 			}
733*74b941f0SAlexander V. Chernikov 		}
734*74b941f0SAlexander V. Chernikov 	} else {
735*74b941f0SAlexander V. Chernikov 		/* IPv6: /64 */
736*74b941f0SAlexander V. Chernikov 		uint64_t a6, *paddr;
737*74b941f0SAlexander V. Chernikov 		head = (struct chashbhead *)ti->xstate;
738*74b941f0SAlexander V. Chernikov 		paddr = (uint64_t *)key;
739*74b941f0SAlexander V. Chernikov 		hsize = 1 << (ti->data & 0xFF);
740*74b941f0SAlexander V. Chernikov 		a6 = *paddr;
741*74b941f0SAlexander V. Chernikov 		hash = hash_ip64((struct in6_addr *)key, hsize);
742*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(ent, &head[hash], next) {
743*74b941f0SAlexander V. Chernikov 			paddr = (uint64_t *)&ent->a.a6;
744*74b941f0SAlexander V. Chernikov 			if (a6 == *paddr) {
745*74b941f0SAlexander V. Chernikov 				*val = ent->value;
746*74b941f0SAlexander V. Chernikov 				return (1);
747*74b941f0SAlexander V. Chernikov 			}
748*74b941f0SAlexander V. Chernikov 		}
749*74b941f0SAlexander V. Chernikov 	}
750*74b941f0SAlexander V. Chernikov 
751*74b941f0SAlexander V. Chernikov 	return (0);
752*74b941f0SAlexander V. Chernikov }
753*74b941f0SAlexander V. Chernikov 
754*74b941f0SAlexander V. Chernikov static int
755*74b941f0SAlexander V. Chernikov chash_parse_opts(struct chash_cfg *ccfg, char *data)
756*74b941f0SAlexander V. Chernikov {
757*74b941f0SAlexander V. Chernikov 	char *pdel, *pend, *s;
758*74b941f0SAlexander V. Chernikov 	int mask4, mask6;
759*74b941f0SAlexander V. Chernikov 
760*74b941f0SAlexander V. Chernikov 	mask4 = ccfg->mask4;
761*74b941f0SAlexander V. Chernikov 	mask6 = ccfg->mask6;
762*74b941f0SAlexander V. Chernikov 
763*74b941f0SAlexander V. Chernikov 	if (data == NULL)
764*74b941f0SAlexander V. Chernikov 		return (0);
765*74b941f0SAlexander V. Chernikov 	if ((pdel = strchr(data, ' ')) == NULL)
766*74b941f0SAlexander V. Chernikov 		return (0);
767*74b941f0SAlexander V. Chernikov 	while (*pdel == ' ')
768*74b941f0SAlexander V. Chernikov 		pdel++;
769*74b941f0SAlexander V. Chernikov 	if (strncmp(pdel, "masks=", 6) != 0)
770*74b941f0SAlexander V. Chernikov 		return (EINVAL);
771*74b941f0SAlexander V. Chernikov 	if ((s = strchr(pdel, ' ')) != NULL)
772*74b941f0SAlexander V. Chernikov 		*s++ = '\0';
773*74b941f0SAlexander V. Chernikov 
774*74b941f0SAlexander V. Chernikov 	pdel += 6;
775*74b941f0SAlexander V. Chernikov 	/* Need /XX[,/YY] */
776*74b941f0SAlexander V. Chernikov 	if (*pdel++ != '/')
777*74b941f0SAlexander V. Chernikov 		return (EINVAL);
778*74b941f0SAlexander V. Chernikov 	mask4 = strtol(pdel, &pend, 10);
779*74b941f0SAlexander V. Chernikov 	if (*pend == ',') {
780*74b941f0SAlexander V. Chernikov 		/* ,/YY */
781*74b941f0SAlexander V. Chernikov 		pdel = pend + 1;
782*74b941f0SAlexander V. Chernikov 		if (*pdel++ != '/')
783*74b941f0SAlexander V. Chernikov 			return (EINVAL);
784*74b941f0SAlexander V. Chernikov 		mask6 = strtol(pdel, &pend, 10);
785*74b941f0SAlexander V. Chernikov 		if (*pend != '\0')
786*74b941f0SAlexander V. Chernikov 			return (EINVAL);
787*74b941f0SAlexander V. Chernikov 	} else if (*pend != '\0')
788*74b941f0SAlexander V. Chernikov 		return (EINVAL);
789*74b941f0SAlexander V. Chernikov 
790*74b941f0SAlexander V. Chernikov 	if (mask4 < 0 || mask4 > 32 || mask6 < 0 || mask6 > 128)
791*74b941f0SAlexander V. Chernikov 		return (EINVAL);
792*74b941f0SAlexander V. Chernikov 
793*74b941f0SAlexander V. Chernikov 	ccfg->mask4 = mask4;
794*74b941f0SAlexander V. Chernikov 	ccfg->mask6 = mask6;
795*74b941f0SAlexander V. Chernikov 
796*74b941f0SAlexander V. Chernikov 	return (0);
797*74b941f0SAlexander V. Chernikov }
798*74b941f0SAlexander V. Chernikov 
799*74b941f0SAlexander V. Chernikov static void
800*74b941f0SAlexander V. Chernikov ta_print_chash_config(void *ta_state, struct table_info *ti, char *buf,
801*74b941f0SAlexander V. Chernikov     size_t bufsize)
802*74b941f0SAlexander V. Chernikov {
803*74b941f0SAlexander V. Chernikov 	struct chash_cfg *ccfg;
804*74b941f0SAlexander V. Chernikov 
805*74b941f0SAlexander V. Chernikov 	ccfg = (struct chash_cfg *)ta_state;
806*74b941f0SAlexander V. Chernikov 
807*74b941f0SAlexander V. Chernikov 	if (ccfg->mask4 != 32 || ccfg->mask6 != 128)
808*74b941f0SAlexander V. Chernikov 		snprintf(buf, bufsize, "%s masks=/%d,/%d", "cidr:hash",
809*74b941f0SAlexander V. Chernikov 		    ccfg->mask4, ccfg->mask6);
810*74b941f0SAlexander V. Chernikov 	else
811*74b941f0SAlexander V. Chernikov 		snprintf(buf, bufsize, "%s", "cidr:hash");
812*74b941f0SAlexander V. Chernikov }
813*74b941f0SAlexander V. Chernikov 
814*74b941f0SAlexander V. Chernikov 
815*74b941f0SAlexander V. Chernikov /*
816*74b941f0SAlexander V. Chernikov  * New table.
817*74b941f0SAlexander V. Chernikov  * We assume 'data' to be either NULL or the following format:
818*74b941f0SAlexander V. Chernikov  * 'cidr:hash [masks=/32[,/128]]'
819*74b941f0SAlexander V. Chernikov  */
820*74b941f0SAlexander V. Chernikov static int
821*74b941f0SAlexander V. Chernikov ta_init_chash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
822*74b941f0SAlexander V. Chernikov     char *data)
823*74b941f0SAlexander V. Chernikov {
824*74b941f0SAlexander V. Chernikov 	int error, i;
825*74b941f0SAlexander V. Chernikov 	int v4, v6;
826*74b941f0SAlexander V. Chernikov 	struct chash_cfg *ccfg;
827*74b941f0SAlexander V. Chernikov 
828*74b941f0SAlexander V. Chernikov 	ccfg = malloc(sizeof(struct chash_cfg), M_IPFW, M_WAITOK | M_ZERO);
829*74b941f0SAlexander V. Chernikov 
830*74b941f0SAlexander V. Chernikov 	ccfg->mask4 = 32;
831*74b941f0SAlexander V. Chernikov 	ccfg->mask6 = 128;
832*74b941f0SAlexander V. Chernikov 
833*74b941f0SAlexander V. Chernikov 	if ((error = chash_parse_opts(ccfg, data)) != 0) {
834*74b941f0SAlexander V. Chernikov 		free(ccfg, M_IPFW);
835*74b941f0SAlexander V. Chernikov 		return (error);
836*74b941f0SAlexander V. Chernikov 	}
837*74b941f0SAlexander V. Chernikov 
838*74b941f0SAlexander V. Chernikov 	v4 = 7;
839*74b941f0SAlexander V. Chernikov 	v6 = 7;
840*74b941f0SAlexander V. Chernikov 	ccfg->size4 = 1 << v4;
841*74b941f0SAlexander V. Chernikov 	ccfg->size6 = 1 << v6;
842*74b941f0SAlexander V. Chernikov 
843*74b941f0SAlexander V. Chernikov 	ccfg->head4 = malloc(sizeof(struct chashbhead) * ccfg->size4, M_IPFW,
844*74b941f0SAlexander V. Chernikov 	    M_WAITOK | M_ZERO);
845*74b941f0SAlexander V. Chernikov 	ccfg->head6 = malloc(sizeof(struct chashbhead) * ccfg->size6, M_IPFW,
846*74b941f0SAlexander V. Chernikov 	    M_WAITOK | M_ZERO);
847*74b941f0SAlexander V. Chernikov 	for (i = 0; i < ccfg->size4; i++)
848*74b941f0SAlexander V. Chernikov 		SLIST_INIT(&ccfg->head4[i]);
849*74b941f0SAlexander V. Chernikov 	for (i = 0; i < ccfg->size6; i++)
850*74b941f0SAlexander V. Chernikov 		SLIST_INIT(&ccfg->head6[i]);
851*74b941f0SAlexander V. Chernikov 
852*74b941f0SAlexander V. Chernikov 
853*74b941f0SAlexander V. Chernikov 	*ta_state = ccfg;
854*74b941f0SAlexander V. Chernikov 	ti->state = ccfg->head4;
855*74b941f0SAlexander V. Chernikov 	ti->xstate = ccfg->head6;
856*74b941f0SAlexander V. Chernikov 
857*74b941f0SAlexander V. Chernikov 	/* Store data depending on v6 mask length */
858*74b941f0SAlexander V. Chernikov 	if (ccfg->mask6 == 64) {
859*74b941f0SAlexander V. Chernikov 		ti->data = (32 - ccfg->mask4) << 24 | (128 - ccfg->mask6) << 16 |
860*74b941f0SAlexander V. Chernikov 		    v4 << 8 | v6;
861*74b941f0SAlexander V. Chernikov 		ti->lookup = ta_lookup_chash_64;
862*74b941f0SAlexander V. Chernikov 	} else if ((ccfg->mask6  % 8) == 0) {
863*74b941f0SAlexander V. Chernikov 		ti->data = (32 - ccfg->mask4) << 24 |
864*74b941f0SAlexander V. Chernikov 		    ccfg->mask6 << 13 | v4 << 8 | v6;
865*74b941f0SAlexander V. Chernikov 		ti->lookup = ta_lookup_chash_aligned;
866*74b941f0SAlexander V. Chernikov 	} else {
867*74b941f0SAlexander V. Chernikov 		/* don't do that! */
868*74b941f0SAlexander V. Chernikov 		ti->data = (32 - ccfg->mask4) << 24 |
869*74b941f0SAlexander V. Chernikov 		    ccfg->mask6 << 16 | v4 << 8 | v6;
870*74b941f0SAlexander V. Chernikov 		ti->lookup = ta_lookup_chash_slow;
871*74b941f0SAlexander V. Chernikov 	}
872*74b941f0SAlexander V. Chernikov 
873*74b941f0SAlexander V. Chernikov 	return (0);
874*74b941f0SAlexander V. Chernikov }
875*74b941f0SAlexander V. Chernikov 
876*74b941f0SAlexander V. Chernikov static void
877*74b941f0SAlexander V. Chernikov ta_destroy_chash(void *ta_state, struct table_info *ti)
878*74b941f0SAlexander V. Chernikov {
879*74b941f0SAlexander V. Chernikov 	struct chash_cfg *ccfg;
880*74b941f0SAlexander V. Chernikov 	struct chashentry *ent, *ent_next;
881*74b941f0SAlexander V. Chernikov 	int i;
882*74b941f0SAlexander V. Chernikov 
883*74b941f0SAlexander V. Chernikov 	ccfg = (struct chash_cfg *)ta_state;
884*74b941f0SAlexander V. Chernikov 
885*74b941f0SAlexander V. Chernikov 	for (i = 0; i < ccfg->size4; i++)
886*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
887*74b941f0SAlexander V. Chernikov 			free(ent, M_IPFW_TBL);
888*74b941f0SAlexander V. Chernikov 
889*74b941f0SAlexander V. Chernikov 	for (i = 0; i < ccfg->size6; i++)
890*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
891*74b941f0SAlexander V. Chernikov 			free(ent, M_IPFW_TBL);
892*74b941f0SAlexander V. Chernikov 
893*74b941f0SAlexander V. Chernikov 	free(ccfg->head4, M_IPFW);
894*74b941f0SAlexander V. Chernikov 	free(ccfg->head6, M_IPFW);
895*74b941f0SAlexander V. Chernikov }
896*74b941f0SAlexander V. Chernikov 
897*74b941f0SAlexander V. Chernikov static int
898*74b941f0SAlexander V. Chernikov ta_dump_chash_tentry(void *ta_state, struct table_info *ti, void *e,
899*74b941f0SAlexander V. Chernikov     ipfw_obj_tentry *tent)
900*74b941f0SAlexander V. Chernikov {
901*74b941f0SAlexander V. Chernikov 	struct chash_cfg *ccfg;
902*74b941f0SAlexander V. Chernikov 	struct chashentry *ent;
903*74b941f0SAlexander V. Chernikov 
904*74b941f0SAlexander V. Chernikov 	ccfg = (struct chash_cfg *)ta_state;
905*74b941f0SAlexander V. Chernikov 	ent = (struct chashentry *)e;
906*74b941f0SAlexander V. Chernikov 
907*74b941f0SAlexander V. Chernikov 	if (ent->type == AF_INET) {
908*74b941f0SAlexander V. Chernikov 		tent->k.addr.s_addr = htonl(ent->a.a4 << (32 - ccfg->mask4));
909*74b941f0SAlexander V. Chernikov 		tent->masklen = ccfg->mask4;
910*74b941f0SAlexander V. Chernikov 		tent->subtype = AF_INET;
911*74b941f0SAlexander V. Chernikov 		tent->value = ent->value;
912*74b941f0SAlexander V. Chernikov #ifdef INET6
913*74b941f0SAlexander V. Chernikov 	} else {
914*74b941f0SAlexander V. Chernikov 		memcpy(&tent->k, &ent->a.a6, sizeof(struct in6_addr));
915*74b941f0SAlexander V. Chernikov 		tent->masklen = ccfg->mask6;
916*74b941f0SAlexander V. Chernikov 		tent->subtype = AF_INET6;
917*74b941f0SAlexander V. Chernikov 		tent->value = ent->value;
918*74b941f0SAlexander V. Chernikov #endif
919*74b941f0SAlexander V. Chernikov 	}
920*74b941f0SAlexander V. Chernikov 
921*74b941f0SAlexander V. Chernikov 	return (0);
922*74b941f0SAlexander V. Chernikov }
923*74b941f0SAlexander V. Chernikov 
924*74b941f0SAlexander V. Chernikov static int
925*74b941f0SAlexander V. Chernikov ta_find_chash_tentry(void *ta_state, struct table_info *ti, void *key,
926*74b941f0SAlexander V. Chernikov     uint32_t keylen, ipfw_obj_tentry *tent)
927*74b941f0SAlexander V. Chernikov {
928*74b941f0SAlexander V. Chernikov #if 0
929*74b941f0SAlexander V. Chernikov 	struct radix_node_head *rnh;
930*74b941f0SAlexander V. Chernikov 	void *e;
931*74b941f0SAlexander V. Chernikov 
932*74b941f0SAlexander V. Chernikov 	e = NULL;
933*74b941f0SAlexander V. Chernikov 	if (keylen == sizeof(in_addr_t)) {
934*74b941f0SAlexander V. Chernikov 		struct sockaddr_in sa;
935*74b941f0SAlexander V. Chernikov 		KEY_LEN(sa) = KEY_LEN_INET;
936*74b941f0SAlexander V. Chernikov 		sa.sin_addr.s_addr = *((in_addr_t *)key);
937*74b941f0SAlexander V. Chernikov 		rnh = (struct radix_node_head *)ti->state;
938*74b941f0SAlexander V. Chernikov 		e = rnh->rnh_matchaddr(&sa, rnh);
939*74b941f0SAlexander V. Chernikov 	} else {
940*74b941f0SAlexander V. Chernikov 		struct sa_in6 sa6;
941*74b941f0SAlexander V. Chernikov 		KEY_LEN(sa6) = KEY_LEN_INET6;
942*74b941f0SAlexander V. Chernikov 		memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
943*74b941f0SAlexander V. Chernikov 		rnh = (struct radix_node_head *)ti->xstate;
944*74b941f0SAlexander V. Chernikov 		e = rnh->rnh_matchaddr(&sa6, rnh);
945*74b941f0SAlexander V. Chernikov 	}
946*74b941f0SAlexander V. Chernikov 
947*74b941f0SAlexander V. Chernikov 	if (e != NULL) {
948*74b941f0SAlexander V. Chernikov 		ta_dump_radix_tentry(ta_state, ti, e, tent);
949*74b941f0SAlexander V. Chernikov 		return (0);
950*74b941f0SAlexander V. Chernikov 	}
951*74b941f0SAlexander V. Chernikov #endif
952*74b941f0SAlexander V. Chernikov 	return (ENOENT);
953*74b941f0SAlexander V. Chernikov }
954*74b941f0SAlexander V. Chernikov 
955*74b941f0SAlexander V. Chernikov static void
956*74b941f0SAlexander V. Chernikov ta_foreach_chash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
957*74b941f0SAlexander V. Chernikov     void *arg)
958*74b941f0SAlexander V. Chernikov {
959*74b941f0SAlexander V. Chernikov 	struct chash_cfg *ccfg;
960*74b941f0SAlexander V. Chernikov 	struct chashentry *ent, *ent_next;
961*74b941f0SAlexander V. Chernikov 	int i;
962*74b941f0SAlexander V. Chernikov 
963*74b941f0SAlexander V. Chernikov 	ccfg = (struct chash_cfg *)ta_state;
964*74b941f0SAlexander V. Chernikov 
965*74b941f0SAlexander V. Chernikov 	for (i = 0; i < ccfg->size4; i++)
966*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
967*74b941f0SAlexander V. Chernikov 			f(ent, arg);
968*74b941f0SAlexander V. Chernikov 
969*74b941f0SAlexander V. Chernikov 	for (i = 0; i < ccfg->size6; i++)
970*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
971*74b941f0SAlexander V. Chernikov 			f(ent, arg);
972*74b941f0SAlexander V. Chernikov }
973*74b941f0SAlexander V. Chernikov 
974*74b941f0SAlexander V. Chernikov 
975*74b941f0SAlexander V. Chernikov struct ta_buf_chash
976*74b941f0SAlexander V. Chernikov {
977*74b941f0SAlexander V. Chernikov 	void *ent_ptr;
978*74b941f0SAlexander V. Chernikov 	int type;
979*74b941f0SAlexander V. Chernikov 	union {
980*74b941f0SAlexander V. Chernikov 		uint32_t	a4;
981*74b941f0SAlexander V. Chernikov 		struct in6_addr	a6;
982*74b941f0SAlexander V. Chernikov 	} a;
983*74b941f0SAlexander V. Chernikov };
984*74b941f0SAlexander V. Chernikov 
985*74b941f0SAlexander V. Chernikov static int
986*74b941f0SAlexander V. Chernikov ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
987*74b941f0SAlexander V. Chernikov     void *ta_buf)
988*74b941f0SAlexander V. Chernikov {
989*74b941f0SAlexander V. Chernikov 	struct ta_buf_chash *tb;
990*74b941f0SAlexander V. Chernikov 	struct chashentry *ent;
991*74b941f0SAlexander V. Chernikov 	int mlen;
992*74b941f0SAlexander V. Chernikov 	struct in6_addr mask6;
993*74b941f0SAlexander V. Chernikov 
994*74b941f0SAlexander V. Chernikov 	tb = (struct ta_buf_chash *)ta_buf;
995*74b941f0SAlexander V. Chernikov 	memset(tb, 0, sizeof(struct ta_buf_chash));
996*74b941f0SAlexander V. Chernikov 
997*74b941f0SAlexander V. Chernikov 	mlen = tei->masklen;
998*74b941f0SAlexander V. Chernikov 
999*74b941f0SAlexander V. Chernikov 	if (tei->subtype == AF_INET) {
1000*74b941f0SAlexander V. Chernikov #ifdef INET
1001*74b941f0SAlexander V. Chernikov 		if (mlen > 32)
1002*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1003*74b941f0SAlexander V. Chernikov 		ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1004*74b941f0SAlexander V. Chernikov 		ent->value = tei->value;
1005*74b941f0SAlexander V. Chernikov 		ent->type = AF_INET;
1006*74b941f0SAlexander V. Chernikov 
1007*74b941f0SAlexander V. Chernikov 		/* Calculate mask */
1008*74b941f0SAlexander V. Chernikov 		ent->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1009*74b941f0SAlexander V. Chernikov 		tb->ent_ptr = ent;
1010*74b941f0SAlexander V. Chernikov #endif
1011*74b941f0SAlexander V. Chernikov #ifdef INET6
1012*74b941f0SAlexander V. Chernikov 	} else if (tei->subtype == AF_INET6) {
1013*74b941f0SAlexander V. Chernikov 		/* IPv6 case */
1014*74b941f0SAlexander V. Chernikov 		if (mlen > 128)
1015*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1016*74b941f0SAlexander V. Chernikov 		ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1017*74b941f0SAlexander V. Chernikov 		ent->value = tei->value;
1018*74b941f0SAlexander V. Chernikov 		ent->type = AF_INET6;
1019*74b941f0SAlexander V. Chernikov 
1020*74b941f0SAlexander V. Chernikov 		ipv6_writemask(&mask6, mlen);
1021*74b941f0SAlexander V. Chernikov 		memcpy(&ent->a.a6, tei->paddr, sizeof(struct in6_addr));
1022*74b941f0SAlexander V. Chernikov 		APPLY_MASK(&ent->a.a6, &mask6);
1023*74b941f0SAlexander V. Chernikov 		tb->ent_ptr = ent;
1024*74b941f0SAlexander V. Chernikov #endif
1025*74b941f0SAlexander V. Chernikov 	} else {
1026*74b941f0SAlexander V. Chernikov 		/* Unknown CIDR type */
1027*74b941f0SAlexander V. Chernikov 		return (EINVAL);
1028*74b941f0SAlexander V. Chernikov 	}
1029*74b941f0SAlexander V. Chernikov 
1030*74b941f0SAlexander V. Chernikov 	return (0);
1031*74b941f0SAlexander V. Chernikov }
1032*74b941f0SAlexander V. Chernikov 
1033*74b941f0SAlexander V. Chernikov static int
1034*74b941f0SAlexander V. Chernikov ta_add_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1035*74b941f0SAlexander V. Chernikov     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1036*74b941f0SAlexander V. Chernikov {
1037*74b941f0SAlexander V. Chernikov 	struct chash_cfg *ccfg;
1038*74b941f0SAlexander V. Chernikov 	struct chashbhead *head;
1039*74b941f0SAlexander V. Chernikov 	struct chashentry *ent, *tmp;
1040*74b941f0SAlexander V. Chernikov 	struct ta_buf_chash *tb;
1041*74b941f0SAlexander V. Chernikov 	int exists;
1042*74b941f0SAlexander V. Chernikov 	uint32_t hash;
1043*74b941f0SAlexander V. Chernikov 
1044*74b941f0SAlexander V. Chernikov 	ccfg = (struct chash_cfg *)ta_state;
1045*74b941f0SAlexander V. Chernikov 	tb = (struct ta_buf_chash *)ta_buf;
1046*74b941f0SAlexander V. Chernikov 	ent = (struct chashentry *)tb->ent_ptr;
1047*74b941f0SAlexander V. Chernikov 	hash = 0;
1048*74b941f0SAlexander V. Chernikov 	exists = 0;
1049*74b941f0SAlexander V. Chernikov 
1050*74b941f0SAlexander V. Chernikov 	if (tei->subtype == AF_INET) {
1051*74b941f0SAlexander V. Chernikov 		if (tei->masklen != ccfg->mask4)
1052*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1053*74b941f0SAlexander V. Chernikov 		head = ccfg->head4;
1054*74b941f0SAlexander V. Chernikov 		hash = hash_ip(ent->a.a4, ccfg->size4);
1055*74b941f0SAlexander V. Chernikov 		/* Check for existence */
1056*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(tmp, &head[hash], next) {
1057*74b941f0SAlexander V. Chernikov 			if (tmp->a.a4 == ent->a.a4) {
1058*74b941f0SAlexander V. Chernikov 				exists = 1;
1059*74b941f0SAlexander V. Chernikov 				break;
1060*74b941f0SAlexander V. Chernikov 			}
1061*74b941f0SAlexander V. Chernikov 		}
1062*74b941f0SAlexander V. Chernikov 	} else {
1063*74b941f0SAlexander V. Chernikov 		if (tei->masklen != ccfg->mask6)
1064*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1065*74b941f0SAlexander V. Chernikov 		head = ccfg->head6;
1066*74b941f0SAlexander V. Chernikov 		if (tei->masklen == 64)
1067*74b941f0SAlexander V. Chernikov 			hash = hash_ip64(&ent->a.a6, ccfg->size6);
1068*74b941f0SAlexander V. Chernikov 		else
1069*74b941f0SAlexander V. Chernikov 			hash = hash_ip6(&ent->a.a6, ccfg->size6);
1070*74b941f0SAlexander V. Chernikov 		/* Check for existence */
1071*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH(tmp, &head[hash], next) {
1072*74b941f0SAlexander V. Chernikov 			if (memcmp(&tmp->a.a6, &ent->a.a6, 16)) {
1073*74b941f0SAlexander V. Chernikov 				exists = 1;
1074*74b941f0SAlexander V. Chernikov 				break;
1075*74b941f0SAlexander V. Chernikov 			}
1076*74b941f0SAlexander V. Chernikov 		}
1077*74b941f0SAlexander V. Chernikov 	}
1078*74b941f0SAlexander V. Chernikov 
1079*74b941f0SAlexander V. Chernikov 	if (exists == 1) {
1080*74b941f0SAlexander V. Chernikov 		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1081*74b941f0SAlexander V. Chernikov 			return (EEXIST);
1082*74b941f0SAlexander V. Chernikov 		/* Record already exists. Update value if we're asked to */
1083*74b941f0SAlexander V. Chernikov 		tmp->value = tei->value;
1084*74b941f0SAlexander V. Chernikov 		/* Indicate that update has happened instead of addition */
1085*74b941f0SAlexander V. Chernikov 		tei->flags |= TEI_FLAGS_UPDATED;
1086*74b941f0SAlexander V. Chernikov 		*pnum = 0;
1087*74b941f0SAlexander V. Chernikov 	} else {
1088*74b941f0SAlexander V. Chernikov 		SLIST_INSERT_HEAD(&head[hash], ent, next);
1089*74b941f0SAlexander V. Chernikov 		tb->ent_ptr = NULL;
1090*74b941f0SAlexander V. Chernikov 		*pnum = 1;
1091*74b941f0SAlexander V. Chernikov 	}
1092*74b941f0SAlexander V. Chernikov 
1093*74b941f0SAlexander V. Chernikov 	return (0);
1094*74b941f0SAlexander V. Chernikov }
1095*74b941f0SAlexander V. Chernikov 
1096*74b941f0SAlexander V. Chernikov static int
1097*74b941f0SAlexander V. Chernikov ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1098*74b941f0SAlexander V. Chernikov     void *ta_buf)
1099*74b941f0SAlexander V. Chernikov {
1100*74b941f0SAlexander V. Chernikov 	struct ta_buf_chash *tb;
1101*74b941f0SAlexander V. Chernikov 	int mlen;
1102*74b941f0SAlexander V. Chernikov 	struct in6_addr mask6;
1103*74b941f0SAlexander V. Chernikov 
1104*74b941f0SAlexander V. Chernikov 	tb = (struct ta_buf_chash *)ta_buf;
1105*74b941f0SAlexander V. Chernikov 	memset(tb, 0, sizeof(struct ta_buf_chash));
1106*74b941f0SAlexander V. Chernikov 
1107*74b941f0SAlexander V. Chernikov 	mlen = tei->masklen;
1108*74b941f0SAlexander V. Chernikov 
1109*74b941f0SAlexander V. Chernikov 	if (tei->subtype == AF_INET) {
1110*74b941f0SAlexander V. Chernikov #ifdef INET
1111*74b941f0SAlexander V. Chernikov 		if (mlen > 32)
1112*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1113*74b941f0SAlexander V. Chernikov 		tb->type = AF_INET;
1114*74b941f0SAlexander V. Chernikov 
1115*74b941f0SAlexander V. Chernikov 		/* Calculate masked address */
1116*74b941f0SAlexander V. Chernikov 		tb->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1117*74b941f0SAlexander V. Chernikov #endif
1118*74b941f0SAlexander V. Chernikov #ifdef INET6
1119*74b941f0SAlexander V. Chernikov 	} else if (tei->subtype == AF_INET6) {
1120*74b941f0SAlexander V. Chernikov 		/* IPv6 case */
1121*74b941f0SAlexander V. Chernikov 		if (mlen > 128)
1122*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1123*74b941f0SAlexander V. Chernikov 		tb->type = AF_INET6;
1124*74b941f0SAlexander V. Chernikov 
1125*74b941f0SAlexander V. Chernikov 		ipv6_writemask(&mask6, mlen);
1126*74b941f0SAlexander V. Chernikov 		memcpy(&tb->a.a6, tei->paddr, sizeof(struct in6_addr));
1127*74b941f0SAlexander V. Chernikov 		APPLY_MASK(&tb->a.a6, &mask6);
1128*74b941f0SAlexander V. Chernikov #endif
1129*74b941f0SAlexander V. Chernikov 	} else {
1130*74b941f0SAlexander V. Chernikov 		/* Unknown CIDR type */
1131*74b941f0SAlexander V. Chernikov 		return (EINVAL);
1132*74b941f0SAlexander V. Chernikov 	}
1133*74b941f0SAlexander V. Chernikov 
1134*74b941f0SAlexander V. Chernikov 	return (0);
1135*74b941f0SAlexander V. Chernikov }
1136*74b941f0SAlexander V. Chernikov 
1137*74b941f0SAlexander V. Chernikov static int
1138*74b941f0SAlexander V. Chernikov ta_del_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1139*74b941f0SAlexander V. Chernikov     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1140*74b941f0SAlexander V. Chernikov {
1141*74b941f0SAlexander V. Chernikov 	struct chash_cfg *ccfg;
1142*74b941f0SAlexander V. Chernikov 	struct chashbhead *head;
1143*74b941f0SAlexander V. Chernikov 	struct chashentry *ent, *tmp_next;
1144*74b941f0SAlexander V. Chernikov 	struct ta_buf_chash *tb;
1145*74b941f0SAlexander V. Chernikov 	uint32_t hash;
1146*74b941f0SAlexander V. Chernikov 
1147*74b941f0SAlexander V. Chernikov 	ccfg = (struct chash_cfg *)ta_state;
1148*74b941f0SAlexander V. Chernikov 	tb = (struct ta_buf_chash *)ta_buf;
1149*74b941f0SAlexander V. Chernikov 
1150*74b941f0SAlexander V. Chernikov 	if (tei->subtype == AF_INET) {
1151*74b941f0SAlexander V. Chernikov 		if (tei->masklen != ccfg->mask4)
1152*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1153*74b941f0SAlexander V. Chernikov 		head = ccfg->head4;
1154*74b941f0SAlexander V. Chernikov 		hash = hash_ip(tb->a.a4, ccfg->size4);
1155*74b941f0SAlexander V. Chernikov 
1156*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1157*74b941f0SAlexander V. Chernikov 			if (ent->a.a4 == tb->a.a4) {
1158*74b941f0SAlexander V. Chernikov 				SLIST_REMOVE(&head[hash], ent, chashentry,next);
1159*74b941f0SAlexander V. Chernikov 				*pnum = 1;
1160*74b941f0SAlexander V. Chernikov 				return (0);
1161*74b941f0SAlexander V. Chernikov 			}
1162*74b941f0SAlexander V. Chernikov 		}
1163*74b941f0SAlexander V. Chernikov 	} else {
1164*74b941f0SAlexander V. Chernikov 		if (tei->masklen != ccfg->mask6)
1165*74b941f0SAlexander V. Chernikov 			return (EINVAL);
1166*74b941f0SAlexander V. Chernikov 		head = ccfg->head6;
1167*74b941f0SAlexander V. Chernikov 		if (tei->masklen == 64)
1168*74b941f0SAlexander V. Chernikov 			hash = hash_ip64(&tb->a.a6, ccfg->size6);
1169*74b941f0SAlexander V. Chernikov 		else
1170*74b941f0SAlexander V. Chernikov 			hash = hash_ip6(&tb->a.a6, ccfg->size6);
1171*74b941f0SAlexander V. Chernikov 
1172*74b941f0SAlexander V. Chernikov 		SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1173*74b941f0SAlexander V. Chernikov 			if (memcmp(&ent->a.a6, &tb->a.a6, 16)) {
1174*74b941f0SAlexander V. Chernikov 				SLIST_REMOVE(&head[hash], ent, chashentry,next);
1175*74b941f0SAlexander V. Chernikov 				*pnum = 1;
1176*74b941f0SAlexander V. Chernikov 				return (0);
1177*74b941f0SAlexander V. Chernikov 			}
1178*74b941f0SAlexander V. Chernikov 		}
1179*74b941f0SAlexander V. Chernikov 	}
1180*74b941f0SAlexander V. Chernikov 
1181*74b941f0SAlexander V. Chernikov 	return (ENOENT);
1182*74b941f0SAlexander V. Chernikov }
1183*74b941f0SAlexander V. Chernikov 
1184*74b941f0SAlexander V. Chernikov static void
1185*74b941f0SAlexander V. Chernikov ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1186*74b941f0SAlexander V. Chernikov     void *ta_buf)
1187*74b941f0SAlexander V. Chernikov {
1188*74b941f0SAlexander V. Chernikov 	struct ta_buf_chash *tb;
1189*74b941f0SAlexander V. Chernikov 
1190*74b941f0SAlexander V. Chernikov 	tb = (struct ta_buf_chash *)ta_buf;
1191*74b941f0SAlexander V. Chernikov 
1192*74b941f0SAlexander V. Chernikov 	if (tb->ent_ptr != NULL)
1193*74b941f0SAlexander V. Chernikov 		free(tb->ent_ptr, M_IPFW_TBL);
1194*74b941f0SAlexander V. Chernikov }
1195*74b941f0SAlexander V. Chernikov 
1196*74b941f0SAlexander V. Chernikov struct table_algo cidr_hash = {
1197*74b941f0SAlexander V. Chernikov 	.name		= "cidr:hash",
1198*74b941f0SAlexander V. Chernikov 	.lookup		= ta_lookup_chash_slow,
1199*74b941f0SAlexander V. Chernikov 	.init		= ta_init_chash,
1200*74b941f0SAlexander V. Chernikov 	.destroy	= ta_destroy_chash,
1201*74b941f0SAlexander V. Chernikov 	.prepare_add	= ta_prepare_add_chash,
1202*74b941f0SAlexander V. Chernikov 	.prepare_del	= ta_prepare_del_chash,
1203*74b941f0SAlexander V. Chernikov 	.add		= ta_add_chash,
1204*74b941f0SAlexander V. Chernikov 	.del		= ta_del_chash,
1205*74b941f0SAlexander V. Chernikov 	.flush_entry	= ta_flush_chash_entry,
1206*74b941f0SAlexander V. Chernikov 	.foreach	= ta_foreach_chash,
1207*74b941f0SAlexander V. Chernikov 	.dump_tentry	= ta_dump_chash_tentry,
1208*74b941f0SAlexander V. Chernikov 	.find_tentry	= ta_find_chash_tentry,
1209*74b941f0SAlexander V. Chernikov 	.print_config	= ta_print_chash_config,
1210*74b941f0SAlexander V. Chernikov };
1211*74b941f0SAlexander V. Chernikov 
1212*74b941f0SAlexander V. Chernikov 
1213*74b941f0SAlexander V. Chernikov /*
121468394ec8SAlexander V. Chernikov  * Iface table cmds.
121568394ec8SAlexander V. Chernikov  *
121668394ec8SAlexander V. Chernikov  * Implementation:
121768394ec8SAlexander V. Chernikov  *
121868394ec8SAlexander V. Chernikov  * Runtime part:
121968394ec8SAlexander V. Chernikov  * - sorted array of "struct ifidx" pointed by ti->state.
122068394ec8SAlexander V. Chernikov  *   Array is allocated with routing up to IFIDX_CHUNK. Only existing
122168394ec8SAlexander V. Chernikov  *   interfaces are stored in array, however its allocated size is
122268394ec8SAlexander V. Chernikov  *   sufficient to hold all table records if needed.
122368394ec8SAlexander V. Chernikov  * - current array size is stored in ti->data
122468394ec8SAlexander V. Chernikov  *
122568394ec8SAlexander V. Chernikov  * Table data:
122668394ec8SAlexander V. Chernikov  * - "struct iftable_cfg" is allocated to store table state (ta_state).
122768394ec8SAlexander V. Chernikov  * - All table records are stored inside namedobj instance.
12289f7d47b0SAlexander V. Chernikov  *
12299f7d47b0SAlexander V. Chernikov  */
12309f7d47b0SAlexander V. Chernikov 
123168394ec8SAlexander V. Chernikov struct ifidx {
123268394ec8SAlexander V. Chernikov 	uint16_t	kidx;
123368394ec8SAlexander V. Chernikov 	uint16_t	spare;
123468394ec8SAlexander V. Chernikov 	uint32_t	value;
123568394ec8SAlexander V. Chernikov };
123668394ec8SAlexander V. Chernikov 
123768394ec8SAlexander V. Chernikov struct iftable_cfg;
123868394ec8SAlexander V. Chernikov 
123968394ec8SAlexander V. Chernikov struct ifentry {
124068394ec8SAlexander V. Chernikov 	struct named_object	no;
124168394ec8SAlexander V. Chernikov 	struct ipfw_ifc		ic;
124268394ec8SAlexander V. Chernikov 	struct iftable_cfg	*icfg;
124368394ec8SAlexander V. Chernikov 	uint32_t		value;
124468394ec8SAlexander V. Chernikov 	int			linked;
124568394ec8SAlexander V. Chernikov };
124668394ec8SAlexander V. Chernikov 
124768394ec8SAlexander V. Chernikov struct iftable_cfg {
124868394ec8SAlexander V. Chernikov 	struct namedobj_instance	*ii;
124968394ec8SAlexander V. Chernikov 	struct ip_fw_chain	*ch;
125068394ec8SAlexander V. Chernikov 	struct table_info	*ti;
125168394ec8SAlexander V. Chernikov 	void	*main_ptr;
125268394ec8SAlexander V. Chernikov 	size_t	size;	/* Number of items allocated in array */
125368394ec8SAlexander V. Chernikov 	size_t	count;	/* Number of all items */
125468394ec8SAlexander V. Chernikov 	size_t	used;	/* Number of items _active_ now */
125568394ec8SAlexander V. Chernikov };
125668394ec8SAlexander V. Chernikov 
125768394ec8SAlexander V. Chernikov #define	IFIDX_CHUNK	16
125868394ec8SAlexander V. Chernikov 
125968394ec8SAlexander V. Chernikov int compare_ifidx(const void *k, const void *v);
126068394ec8SAlexander V. Chernikov static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
126168394ec8SAlexander V. Chernikov 
126268394ec8SAlexander V. Chernikov int
126368394ec8SAlexander V. Chernikov compare_ifidx(const void *k, const void *v)
126468394ec8SAlexander V. Chernikov {
126568394ec8SAlexander V. Chernikov 	struct ifidx *ifidx;
126668394ec8SAlexander V. Chernikov 	uint16_t key;
126768394ec8SAlexander V. Chernikov 
126868394ec8SAlexander V. Chernikov 	key = *((uint16_t *)k);
126968394ec8SAlexander V. Chernikov 	ifidx = (struct ifidx *)v;
127068394ec8SAlexander V. Chernikov 
127168394ec8SAlexander V. Chernikov 	if (key < ifidx->kidx)
127268394ec8SAlexander V. Chernikov 		return (-1);
127368394ec8SAlexander V. Chernikov 	else if (key > ifidx->kidx)
127468394ec8SAlexander V. Chernikov 		return (1);
127568394ec8SAlexander V. Chernikov 
127668394ec8SAlexander V. Chernikov 	return (0);
127768394ec8SAlexander V. Chernikov }
127868394ec8SAlexander V. Chernikov 
127968394ec8SAlexander V. Chernikov /*
128068394ec8SAlexander V. Chernikov  * Adds item @item with key @key into ascending-sorted array @base.
128168394ec8SAlexander V. Chernikov  * Assumes @base has enough additional storage.
128268394ec8SAlexander V. Chernikov  *
128368394ec8SAlexander V. Chernikov  * Returns 1 on success, 0 on duplicate key.
128468394ec8SAlexander V. Chernikov  */
12859f7d47b0SAlexander V. Chernikov static int
128668394ec8SAlexander V. Chernikov badd(const void *key, void *item, void *base, size_t nmemb,
128768394ec8SAlexander V. Chernikov     size_t size, int (*compar) (const void *, const void *))
128868394ec8SAlexander V. Chernikov {
128968394ec8SAlexander V. Chernikov 	int min, max, mid, shift, res;
129068394ec8SAlexander V. Chernikov 	caddr_t paddr;
129168394ec8SAlexander V. Chernikov 
129268394ec8SAlexander V. Chernikov 	if (nmemb == 0) {
129368394ec8SAlexander V. Chernikov 		memcpy(base, item, size);
129468394ec8SAlexander V. Chernikov 		return (1);
129568394ec8SAlexander V. Chernikov 	}
129668394ec8SAlexander V. Chernikov 
129768394ec8SAlexander V. Chernikov 	/* Binary search */
129868394ec8SAlexander V. Chernikov 	min = 0;
129968394ec8SAlexander V. Chernikov 	max = nmemb - 1;
130068394ec8SAlexander V. Chernikov 	mid = 0;
130168394ec8SAlexander V. Chernikov 	while (min <= max) {
130268394ec8SAlexander V. Chernikov 		mid = (min + max) / 2;
130368394ec8SAlexander V. Chernikov 		res = compar(key, (const void *)((caddr_t)base + mid * size));
130468394ec8SAlexander V. Chernikov 		if (res == 0)
130568394ec8SAlexander V. Chernikov 			return (0);
130668394ec8SAlexander V. Chernikov 
130768394ec8SAlexander V. Chernikov 		if (res > 0)
130868394ec8SAlexander V. Chernikov 			 min = mid + 1;
130968394ec8SAlexander V. Chernikov 		else
131068394ec8SAlexander V. Chernikov 			 max = mid - 1;
131168394ec8SAlexander V. Chernikov 	}
131268394ec8SAlexander V. Chernikov 
131368394ec8SAlexander V. Chernikov 	/* Item not found. */
131468394ec8SAlexander V. Chernikov 	res = compar(key, (const void *)((caddr_t)base + mid * size));
131568394ec8SAlexander V. Chernikov 	if (res > 0)
131668394ec8SAlexander V. Chernikov 		shift = mid + 1;
131768394ec8SAlexander V. Chernikov 	else
131868394ec8SAlexander V. Chernikov 		shift = mid;
131968394ec8SAlexander V. Chernikov 
132068394ec8SAlexander V. Chernikov 	paddr = (caddr_t)base + shift * size;
132168394ec8SAlexander V. Chernikov 	if (nmemb > shift)
132268394ec8SAlexander V. Chernikov 		memmove(paddr + size, paddr, (nmemb - shift) * size);
132368394ec8SAlexander V. Chernikov 
132468394ec8SAlexander V. Chernikov 	memcpy(paddr, item, size);
132568394ec8SAlexander V. Chernikov 
132668394ec8SAlexander V. Chernikov 	return (1);
132768394ec8SAlexander V. Chernikov }
132868394ec8SAlexander V. Chernikov 
132968394ec8SAlexander V. Chernikov /*
133068394ec8SAlexander V. Chernikov  * Deletes item with key @key from ascending-sorted array @base.
133168394ec8SAlexander V. Chernikov  *
133268394ec8SAlexander V. Chernikov  * Returns 1 on success, 0 for non-existent key.
133368394ec8SAlexander V. Chernikov  */
133468394ec8SAlexander V. Chernikov static int
133568394ec8SAlexander V. Chernikov bdel(const void *key, void *base, size_t nmemb, size_t size,
133668394ec8SAlexander V. Chernikov     int (*compar) (const void *, const void *))
133768394ec8SAlexander V. Chernikov {
133868394ec8SAlexander V. Chernikov 	caddr_t item;
133968394ec8SAlexander V. Chernikov 	size_t sz;
134068394ec8SAlexander V. Chernikov 
134168394ec8SAlexander V. Chernikov 	item = (caddr_t)bsearch(key, base, nmemb, size, compar);
134268394ec8SAlexander V. Chernikov 
134368394ec8SAlexander V. Chernikov 	if (item == NULL)
134468394ec8SAlexander V. Chernikov 		return (0);
134568394ec8SAlexander V. Chernikov 
134668394ec8SAlexander V. Chernikov 	sz = (caddr_t)base + nmemb * size - item;
134768394ec8SAlexander V. Chernikov 
134868394ec8SAlexander V. Chernikov 	if (sz > 0)
134968394ec8SAlexander V. Chernikov 		memmove(item, item + size, sz);
135068394ec8SAlexander V. Chernikov 
135168394ec8SAlexander V. Chernikov 	return (1);
135268394ec8SAlexander V. Chernikov }
135368394ec8SAlexander V. Chernikov 
135468394ec8SAlexander V. Chernikov static struct ifidx *
135568394ec8SAlexander V. Chernikov ifidx_find(struct table_info *ti, void *key)
135668394ec8SAlexander V. Chernikov {
135768394ec8SAlexander V. Chernikov 	struct ifidx *ifi;
135868394ec8SAlexander V. Chernikov 
135968394ec8SAlexander V. Chernikov 	ifi = bsearch(key, ti->state, ti->data, sizeof(struct ifidx),
136068394ec8SAlexander V. Chernikov 	    compare_ifidx);
136168394ec8SAlexander V. Chernikov 
136268394ec8SAlexander V. Chernikov 	return (ifi);
136368394ec8SAlexander V. Chernikov }
136468394ec8SAlexander V. Chernikov 
136568394ec8SAlexander V. Chernikov static int
136668394ec8SAlexander V. Chernikov ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
13679f7d47b0SAlexander V. Chernikov     uint32_t *val)
13689f7d47b0SAlexander V. Chernikov {
136968394ec8SAlexander V. Chernikov 	struct ifidx *ifi;
13709f7d47b0SAlexander V. Chernikov 
137168394ec8SAlexander V. Chernikov 	ifi = ifidx_find(ti, key);
13729f7d47b0SAlexander V. Chernikov 
137368394ec8SAlexander V. Chernikov 	if (ifi != NULL) {
137468394ec8SAlexander V. Chernikov 		*val = ifi->value;
13759f7d47b0SAlexander V. Chernikov 		return (1);
13769f7d47b0SAlexander V. Chernikov 	}
13779f7d47b0SAlexander V. Chernikov 
13789f7d47b0SAlexander V. Chernikov 	return (0);
13799f7d47b0SAlexander V. Chernikov }
13809f7d47b0SAlexander V. Chernikov 
13819f7d47b0SAlexander V. Chernikov static int
138268394ec8SAlexander V. Chernikov ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
138368394ec8SAlexander V. Chernikov     char *data)
13849f7d47b0SAlexander V. Chernikov {
138568394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
13869f7d47b0SAlexander V. Chernikov 
138768394ec8SAlexander V. Chernikov 	icfg = malloc(sizeof(struct iftable_cfg), M_IPFW, M_WAITOK | M_ZERO);
13889f7d47b0SAlexander V. Chernikov 
138968394ec8SAlexander V. Chernikov 	icfg->ii = ipfw_objhash_create(16);
139068394ec8SAlexander V. Chernikov 	icfg->main_ptr = malloc(sizeof(struct ifidx) * IFIDX_CHUNK,  M_IPFW,
139168394ec8SAlexander V. Chernikov 	    M_WAITOK | M_ZERO);
139268394ec8SAlexander V. Chernikov 	icfg->size = IFIDX_CHUNK;
139368394ec8SAlexander V. Chernikov 	icfg->ch = ch;
13949f7d47b0SAlexander V. Chernikov 
139568394ec8SAlexander V. Chernikov 	*ta_state = icfg;
139668394ec8SAlexander V. Chernikov 	ti->state = icfg->main_ptr;
139768394ec8SAlexander V. Chernikov 	ti->lookup = ta_lookup_ifidx;
13989f7d47b0SAlexander V. Chernikov 
13999f7d47b0SAlexander V. Chernikov 	return (0);
14009f7d47b0SAlexander V. Chernikov }
14019f7d47b0SAlexander V. Chernikov 
140268394ec8SAlexander V. Chernikov /*
140368394ec8SAlexander V. Chernikov  * Handle tableinfo @ti pointer change (on table array resize).
140468394ec8SAlexander V. Chernikov  */
140568394ec8SAlexander V. Chernikov static void
140668394ec8SAlexander V. Chernikov ta_change_ti_ifidx(void *ta_state, struct table_info *ti)
140768394ec8SAlexander V. Chernikov {
140868394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
140968394ec8SAlexander V. Chernikov 
141068394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
141168394ec8SAlexander V. Chernikov 	icfg->ti = ti;
141268394ec8SAlexander V. Chernikov }
14139f7d47b0SAlexander V. Chernikov 
14149f7d47b0SAlexander V. Chernikov static void
141568394ec8SAlexander V. Chernikov destroy_ifidx_locked(struct namedobj_instance *ii, struct named_object *no,
141668394ec8SAlexander V. Chernikov     void *arg)
14179f7d47b0SAlexander V. Chernikov {
141868394ec8SAlexander V. Chernikov 	struct ifentry *ife;
141968394ec8SAlexander V. Chernikov 	struct ip_fw_chain *ch;
14209f7d47b0SAlexander V. Chernikov 
142168394ec8SAlexander V. Chernikov 	ch = (struct ip_fw_chain *)arg;
142268394ec8SAlexander V. Chernikov 	ife = (struct ifentry *)no;
142368394ec8SAlexander V. Chernikov 
142468394ec8SAlexander V. Chernikov 	ipfw_iface_del_notify(ch, &ife->ic);
142568394ec8SAlexander V. Chernikov 	free(ife, M_IPFW_TBL);
14269f7d47b0SAlexander V. Chernikov }
14279f7d47b0SAlexander V. Chernikov 
142868394ec8SAlexander V. Chernikov 
142968394ec8SAlexander V. Chernikov /*
143068394ec8SAlexander V. Chernikov  * Destroys table @ti
143168394ec8SAlexander V. Chernikov  */
143268394ec8SAlexander V. Chernikov static void
143368394ec8SAlexander V. Chernikov ta_destroy_ifidx(void *ta_state, struct table_info *ti)
14349f7d47b0SAlexander V. Chernikov {
143568394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
143668394ec8SAlexander V. Chernikov 	struct ip_fw_chain *ch;
143768394ec8SAlexander V. Chernikov 
143868394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
143968394ec8SAlexander V. Chernikov 	ch = icfg->ch;
144068394ec8SAlexander V. Chernikov 
144168394ec8SAlexander V. Chernikov 	if (icfg->main_ptr != NULL)
144268394ec8SAlexander V. Chernikov 		free(icfg->main_ptr, M_IPFW);
144368394ec8SAlexander V. Chernikov 
144468394ec8SAlexander V. Chernikov 	ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
144568394ec8SAlexander V. Chernikov 
144668394ec8SAlexander V. Chernikov 	ipfw_objhash_destroy(icfg->ii);
144768394ec8SAlexander V. Chernikov 
144868394ec8SAlexander V. Chernikov 	free(icfg, M_IPFW);
144968394ec8SAlexander V. Chernikov }
145068394ec8SAlexander V. Chernikov 
145168394ec8SAlexander V. Chernikov struct ta_buf_ifidx
145268394ec8SAlexander V. Chernikov {
145368394ec8SAlexander V. Chernikov 	struct ifentry *ife;
145468394ec8SAlexander V. Chernikov 	uint32_t value;
14559f7d47b0SAlexander V. Chernikov };
14569f7d47b0SAlexander V. Chernikov 
145768394ec8SAlexander V. Chernikov /*
145868394ec8SAlexander V. Chernikov  * Prepare state to add to the table:
145968394ec8SAlexander V. Chernikov  * allocate ifentry and reference needed interface.
146068394ec8SAlexander V. Chernikov  */
14619f7d47b0SAlexander V. Chernikov static int
146268394ec8SAlexander V. Chernikov ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
146368394ec8SAlexander V. Chernikov     void *ta_buf)
146468394ec8SAlexander V. Chernikov {
146568394ec8SAlexander V. Chernikov 	struct ta_buf_ifidx *tb;
146668394ec8SAlexander V. Chernikov 	char *ifname;
146768394ec8SAlexander V. Chernikov 	struct ifentry *ife;
146868394ec8SAlexander V. Chernikov 
146968394ec8SAlexander V. Chernikov 	tb = (struct ta_buf_ifidx *)ta_buf;
1470*74b941f0SAlexander V. Chernikov 	memset(tb, 0, sizeof(struct ta_buf_ifidx));
147168394ec8SAlexander V. Chernikov 
147268394ec8SAlexander V. Chernikov 	/* Check if string is terminated */
147368394ec8SAlexander V. Chernikov 	ifname = (char *)tei->paddr;
147468394ec8SAlexander V. Chernikov 	if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
147568394ec8SAlexander V. Chernikov 		return (EINVAL);
147668394ec8SAlexander V. Chernikov 
147768394ec8SAlexander V. Chernikov 	ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
147868394ec8SAlexander V. Chernikov 	ife->value = tei->value;
147968394ec8SAlexander V. Chernikov 	ife->ic.cb = if_notifier;
148068394ec8SAlexander V. Chernikov 	ife->ic.cbdata = ife;
148168394ec8SAlexander V. Chernikov 
148268394ec8SAlexander V. Chernikov 	if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0)
148368394ec8SAlexander V. Chernikov 		return (EINVAL);
148468394ec8SAlexander V. Chernikov 
148568394ec8SAlexander V. Chernikov 	/* Use ipfw_iface 'ifname' field as stable storage */
148668394ec8SAlexander V. Chernikov 	ife->no.name = ife->ic.iface->ifname;
148768394ec8SAlexander V. Chernikov 
148868394ec8SAlexander V. Chernikov 	tb->ife = ife;
148968394ec8SAlexander V. Chernikov 
149068394ec8SAlexander V. Chernikov 	return (0);
149168394ec8SAlexander V. Chernikov }
149268394ec8SAlexander V. Chernikov 
149368394ec8SAlexander V. Chernikov static int
1494adea6201SAlexander V. Chernikov ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1495adea6201SAlexander V. Chernikov     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
149668394ec8SAlexander V. Chernikov {
149768394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
149868394ec8SAlexander V. Chernikov 	struct ifentry *ife, *tmp;
149968394ec8SAlexander V. Chernikov 	struct ta_buf_ifidx *tb;
150068394ec8SAlexander V. Chernikov 	struct ipfw_iface *iif;
150168394ec8SAlexander V. Chernikov 	struct ifidx *ifi;
150268394ec8SAlexander V. Chernikov 	char *ifname;
150368394ec8SAlexander V. Chernikov 
150468394ec8SAlexander V. Chernikov 	tb = (struct ta_buf_ifidx *)ta_buf;
150568394ec8SAlexander V. Chernikov 	ifname = (char *)tei->paddr;
150668394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
150768394ec8SAlexander V. Chernikov 	ife = tb->ife;
150868394ec8SAlexander V. Chernikov 
150968394ec8SAlexander V. Chernikov 	ife->icfg = icfg;
151068394ec8SAlexander V. Chernikov 
151168394ec8SAlexander V. Chernikov 	tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
151268394ec8SAlexander V. Chernikov 
151368394ec8SAlexander V. Chernikov 	if (tmp != NULL) {
151468394ec8SAlexander V. Chernikov 		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
151568394ec8SAlexander V. Chernikov 			return (EEXIST);
151668394ec8SAlexander V. Chernikov 
151768394ec8SAlexander V. Chernikov 		/* We need to update value */
151868394ec8SAlexander V. Chernikov 		iif = tmp->ic.iface;
151968394ec8SAlexander V. Chernikov 		tmp->value = ife->value;
152068394ec8SAlexander V. Chernikov 
152168394ec8SAlexander V. Chernikov 		if (iif->resolved != 0) {
152268394ec8SAlexander V. Chernikov 			/* We need to update runtime value, too */
152368394ec8SAlexander V. Chernikov 			ifi = ifidx_find(ti, &iif->ifindex);
152468394ec8SAlexander V. Chernikov 			ifi->value = ife->value;
152568394ec8SAlexander V. Chernikov 		}
152668394ec8SAlexander V. Chernikov 
152768394ec8SAlexander V. Chernikov 		/* Indicate that update has happened instead of addition */
152868394ec8SAlexander V. Chernikov 		tei->flags |= TEI_FLAGS_UPDATED;
1529adea6201SAlexander V. Chernikov 		*pnum = 0;
153068394ec8SAlexander V. Chernikov 		return (0);
153168394ec8SAlexander V. Chernikov 	}
153268394ec8SAlexander V. Chernikov 
153368394ec8SAlexander V. Chernikov 	/* Link to internal list */
153468394ec8SAlexander V. Chernikov 	ipfw_objhash_add(icfg->ii, &ife->no);
153568394ec8SAlexander V. Chernikov 
153668394ec8SAlexander V. Chernikov 	/* Link notifier (possible running its callback) */
153768394ec8SAlexander V. Chernikov 	ipfw_iface_add_notify(icfg->ch, &ife->ic);
153868394ec8SAlexander V. Chernikov 	icfg->count++;
153968394ec8SAlexander V. Chernikov 
154068394ec8SAlexander V. Chernikov 	if (icfg->count + 1 == icfg->size) {
154168394ec8SAlexander V. Chernikov 		/* Notify core we need to grow */
154268394ec8SAlexander V. Chernikov 		*pflags = icfg->size + IFIDX_CHUNK;
154368394ec8SAlexander V. Chernikov 	}
154468394ec8SAlexander V. Chernikov 
154568394ec8SAlexander V. Chernikov 	tb->ife = NULL;
1546adea6201SAlexander V. Chernikov 	*pnum = 1;
154768394ec8SAlexander V. Chernikov 
154868394ec8SAlexander V. Chernikov 	return (0);
154968394ec8SAlexander V. Chernikov }
155068394ec8SAlexander V. Chernikov 
155168394ec8SAlexander V. Chernikov /*
155268394ec8SAlexander V. Chernikov  * Prepare to delete key from table.
155368394ec8SAlexander V. Chernikov  * Do basic interface name checks.
155468394ec8SAlexander V. Chernikov  */
155568394ec8SAlexander V. Chernikov static int
155668394ec8SAlexander V. Chernikov ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
155768394ec8SAlexander V. Chernikov     void *ta_buf)
15589f7d47b0SAlexander V. Chernikov {
1559*74b941f0SAlexander V. Chernikov 	struct ta_buf_ifidx *tb;
1560e0a8b9eeSAlexander V. Chernikov 	char *ifname;
15619f7d47b0SAlexander V. Chernikov 
1562*74b941f0SAlexander V. Chernikov 	tb = (struct ta_buf_ifidx *)ta_buf;
1563*74b941f0SAlexander V. Chernikov 	memset(tb, 0, sizeof(struct ta_buf_ifidx));
15649f7d47b0SAlexander V. Chernikov 
15659f7d47b0SAlexander V. Chernikov 	/* Check if string is terminated */
1566e0a8b9eeSAlexander V. Chernikov 	ifname = (char *)tei->paddr;
1567e0a8b9eeSAlexander V. Chernikov 	if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
15689f7d47b0SAlexander V. Chernikov 		return (EINVAL);
15699f7d47b0SAlexander V. Chernikov 
15709f7d47b0SAlexander V. Chernikov 	return (0);
15719f7d47b0SAlexander V. Chernikov }
15729f7d47b0SAlexander V. Chernikov 
157368394ec8SAlexander V. Chernikov /*
157468394ec8SAlexander V. Chernikov  * Remove key from both configuration list and
157568394ec8SAlexander V. Chernikov  * runtime array. Removed interface notification.
157668394ec8SAlexander V. Chernikov  */
15779f7d47b0SAlexander V. Chernikov static int
1578adea6201SAlexander V. Chernikov ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1579adea6201SAlexander V. Chernikov     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
15809f7d47b0SAlexander V. Chernikov {
158168394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
158268394ec8SAlexander V. Chernikov 	struct ifentry *ife;
158368394ec8SAlexander V. Chernikov 	struct ta_buf_ifidx *tb;
158468394ec8SAlexander V. Chernikov 	char *ifname;
158568394ec8SAlexander V. Chernikov 	uint16_t ifindex;
158668394ec8SAlexander V. Chernikov 	int res;
15879f7d47b0SAlexander V. Chernikov 
158868394ec8SAlexander V. Chernikov 	tb = (struct ta_buf_ifidx *)ta_buf;
158968394ec8SAlexander V. Chernikov 	ifname = (char *)tei->paddr;
159068394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
159168394ec8SAlexander V. Chernikov 	ife = tb->ife;
15929f7d47b0SAlexander V. Chernikov 
159368394ec8SAlexander V. Chernikov 	ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
15949f7d47b0SAlexander V. Chernikov 
159568394ec8SAlexander V. Chernikov 	if (ife == NULL)
159681d3153dSAlexander V. Chernikov 		return (ENOENT);
15979f7d47b0SAlexander V. Chernikov 
159868394ec8SAlexander V. Chernikov 	if (ife->linked != 0) {
159968394ec8SAlexander V. Chernikov 		/* We have to remove item from runtime */
160068394ec8SAlexander V. Chernikov 		ifindex = ife->ic.iface->ifindex;
160168394ec8SAlexander V. Chernikov 
160268394ec8SAlexander V. Chernikov 		res = bdel(&ifindex, icfg->main_ptr, icfg->used,
160368394ec8SAlexander V. Chernikov 		    sizeof(struct ifidx), compare_ifidx);
160468394ec8SAlexander V. Chernikov 
160568394ec8SAlexander V. Chernikov 		KASSERT(res == 1, ("index %d does not exist", ifindex));
160668394ec8SAlexander V. Chernikov 		icfg->used--;
160768394ec8SAlexander V. Chernikov 		ti->data = icfg->used;
160868394ec8SAlexander V. Chernikov 		ife->linked = 0;
160968394ec8SAlexander V. Chernikov 	}
161068394ec8SAlexander V. Chernikov 
161168394ec8SAlexander V. Chernikov 	/* Unlink from local list */
161268394ec8SAlexander V. Chernikov 	ipfw_objhash_del(icfg->ii, &ife->no);
161368394ec8SAlexander V. Chernikov 	/* Unlink notifier */
161468394ec8SAlexander V. Chernikov 	ipfw_iface_del_notify(icfg->ch, &ife->ic);
161568394ec8SAlexander V. Chernikov 
161668394ec8SAlexander V. Chernikov 	icfg->count--;
161768394ec8SAlexander V. Chernikov 
161868394ec8SAlexander V. Chernikov 	tb->ife = ife;
1619adea6201SAlexander V. Chernikov 	*pnum = 1;
162068394ec8SAlexander V. Chernikov 
16219f7d47b0SAlexander V. Chernikov 	return (0);
16229f7d47b0SAlexander V. Chernikov }
16239f7d47b0SAlexander V. Chernikov 
162468394ec8SAlexander V. Chernikov /*
162568394ec8SAlexander V. Chernikov  * Flush deleted entry.
162668394ec8SAlexander V. Chernikov  * Drops interface reference and frees entry.
162768394ec8SAlexander V. Chernikov  */
16289f7d47b0SAlexander V. Chernikov static void
162968394ec8SAlexander V. Chernikov ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
163068394ec8SAlexander V. Chernikov     void *ta_buf)
16319f7d47b0SAlexander V. Chernikov {
163268394ec8SAlexander V. Chernikov 	struct ta_buf_ifidx *tb;
16339f7d47b0SAlexander V. Chernikov 
163468394ec8SAlexander V. Chernikov 	tb = (struct ta_buf_ifidx *)ta_buf;
16359f7d47b0SAlexander V. Chernikov 
163668394ec8SAlexander V. Chernikov 	if (tb->ife != NULL) {
163768394ec8SAlexander V. Chernikov 		/* Unlink first */
163868394ec8SAlexander V. Chernikov 		ipfw_iface_unref(ch, &tb->ife->ic);
163968394ec8SAlexander V. Chernikov 		free(tb->ife, M_IPFW_TBL);
164068394ec8SAlexander V. Chernikov 	}
164168394ec8SAlexander V. Chernikov }
164268394ec8SAlexander V. Chernikov 
164368394ec8SAlexander V. Chernikov 
164468394ec8SAlexander V. Chernikov /*
164568394ec8SAlexander V. Chernikov  * Handle interface announce/withdrawal for particular table.
164668394ec8SAlexander V. Chernikov  * Every real runtime array modification happens here.
164768394ec8SAlexander V. Chernikov  */
164868394ec8SAlexander V. Chernikov static void
164968394ec8SAlexander V. Chernikov if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
165068394ec8SAlexander V. Chernikov {
165168394ec8SAlexander V. Chernikov 	struct ifentry *ife;
165268394ec8SAlexander V. Chernikov 	struct ifidx ifi;
165368394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
165468394ec8SAlexander V. Chernikov 	struct table_info *ti;
165568394ec8SAlexander V. Chernikov 	int res;
165668394ec8SAlexander V. Chernikov 
165768394ec8SAlexander V. Chernikov 	ife = (struct ifentry *)cbdata;
165868394ec8SAlexander V. Chernikov 	icfg = ife->icfg;
165968394ec8SAlexander V. Chernikov 	ti = icfg->ti;
166068394ec8SAlexander V. Chernikov 
166168394ec8SAlexander V. Chernikov 	KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
166268394ec8SAlexander V. Chernikov 
166368394ec8SAlexander V. Chernikov 	if (ife->linked == 0 && ifindex != 0) {
166468394ec8SAlexander V. Chernikov 		/* Interface announce */
166568394ec8SAlexander V. Chernikov 		ifi.kidx = ifindex;
166668394ec8SAlexander V. Chernikov 		ifi.spare = 0;
166768394ec8SAlexander V. Chernikov 		ifi.value = ife->value;
166868394ec8SAlexander V. Chernikov 		res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used,
166968394ec8SAlexander V. Chernikov 		    sizeof(struct ifidx), compare_ifidx);
167068394ec8SAlexander V. Chernikov 		KASSERT(res == 1, ("index %d already exists", ifindex));
167168394ec8SAlexander V. Chernikov 		icfg->used++;
167268394ec8SAlexander V. Chernikov 		ti->data = icfg->used;
167368394ec8SAlexander V. Chernikov 		ife->linked = 1;
167468394ec8SAlexander V. Chernikov 	} else if (ife->linked != 0 && ifindex == 0) {
167568394ec8SAlexander V. Chernikov 		/* Interface withdrawal */
167668394ec8SAlexander V. Chernikov 		ifindex = ife->ic.iface->ifindex;
167768394ec8SAlexander V. Chernikov 
167868394ec8SAlexander V. Chernikov 		res = bdel(&ifindex, icfg->main_ptr, icfg->used,
167968394ec8SAlexander V. Chernikov 		    sizeof(struct ifidx), compare_ifidx);
168068394ec8SAlexander V. Chernikov 
168168394ec8SAlexander V. Chernikov 		KASSERT(res == 1, ("index %d does not exist", ifindex));
168268394ec8SAlexander V. Chernikov 		icfg->used--;
168368394ec8SAlexander V. Chernikov 		ti->data = icfg->used;
168468394ec8SAlexander V. Chernikov 		ife->linked = 0;
168568394ec8SAlexander V. Chernikov 	}
168668394ec8SAlexander V. Chernikov }
168768394ec8SAlexander V. Chernikov 
168868394ec8SAlexander V. Chernikov 
168968394ec8SAlexander V. Chernikov /*
169068394ec8SAlexander V. Chernikov  * Table growing callbacks.
169168394ec8SAlexander V. Chernikov  */
169268394ec8SAlexander V. Chernikov 
169368394ec8SAlexander V. Chernikov struct mod_ifidx {
169468394ec8SAlexander V. Chernikov 	void	*main_ptr;
169568394ec8SAlexander V. Chernikov 	size_t	size;
169668394ec8SAlexander V. Chernikov };
169768394ec8SAlexander V. Chernikov 
169868394ec8SAlexander V. Chernikov /*
169968394ec8SAlexander V. Chernikov  * Allocate ned, larger runtime ifidx array.
170068394ec8SAlexander V. Chernikov  */
170168394ec8SAlexander V. Chernikov static int
170268394ec8SAlexander V. Chernikov ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
170368394ec8SAlexander V. Chernikov {
170468394ec8SAlexander V. Chernikov 	struct mod_ifidx *mi;
170568394ec8SAlexander V. Chernikov 
170668394ec8SAlexander V. Chernikov 	mi = (struct mod_ifidx *)ta_buf;
170768394ec8SAlexander V. Chernikov 
170868394ec8SAlexander V. Chernikov 	memset(mi, 0, sizeof(struct mod_ifidx));
170968394ec8SAlexander V. Chernikov 	mi->size = *pflags;
171068394ec8SAlexander V. Chernikov 	mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
171168394ec8SAlexander V. Chernikov 	    M_WAITOK | M_ZERO);
171268394ec8SAlexander V. Chernikov 
171368394ec8SAlexander V. Chernikov 	return (0);
171468394ec8SAlexander V. Chernikov }
171568394ec8SAlexander V. Chernikov 
171668394ec8SAlexander V. Chernikov /*
171768394ec8SAlexander V. Chernikov  * Copy data from old runtime array to new one.
171868394ec8SAlexander V. Chernikov  */
171968394ec8SAlexander V. Chernikov static int
172068394ec8SAlexander V. Chernikov ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
172168394ec8SAlexander V. Chernikov     uint64_t *pflags)
172268394ec8SAlexander V. Chernikov {
172368394ec8SAlexander V. Chernikov 	struct mod_ifidx *mi;
172468394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
172568394ec8SAlexander V. Chernikov 
172668394ec8SAlexander V. Chernikov 	mi = (struct mod_ifidx *)ta_buf;
172768394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
172868394ec8SAlexander V. Chernikov 
172968394ec8SAlexander V. Chernikov 	/* Check if we still need to grow array */
173068394ec8SAlexander V. Chernikov 	if (icfg->size >= mi->size) {
173168394ec8SAlexander V. Chernikov 		*pflags = 0;
173268394ec8SAlexander V. Chernikov 		return (0);
173368394ec8SAlexander V. Chernikov 	}
173468394ec8SAlexander V. Chernikov 
173568394ec8SAlexander V. Chernikov 	memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
173668394ec8SAlexander V. Chernikov 
173768394ec8SAlexander V. Chernikov 	return (0);
173868394ec8SAlexander V. Chernikov }
173968394ec8SAlexander V. Chernikov 
174068394ec8SAlexander V. Chernikov /*
174168394ec8SAlexander V. Chernikov  * Switch old & new arrays.
174268394ec8SAlexander V. Chernikov  */
174368394ec8SAlexander V. Chernikov static int
174468394ec8SAlexander V. Chernikov ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
174568394ec8SAlexander V. Chernikov     uint64_t pflags)
174668394ec8SAlexander V. Chernikov {
174768394ec8SAlexander V. Chernikov 	struct mod_ifidx *mi;
174868394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
174968394ec8SAlexander V. Chernikov 	void *old_ptr;
175068394ec8SAlexander V. Chernikov 
175168394ec8SAlexander V. Chernikov 	mi = (struct mod_ifidx *)ta_buf;
175268394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
175368394ec8SAlexander V. Chernikov 
175468394ec8SAlexander V. Chernikov 	old_ptr = icfg->main_ptr;
175568394ec8SAlexander V. Chernikov 	icfg->main_ptr = mi->main_ptr;
175668394ec8SAlexander V. Chernikov 	icfg->size = mi->size;
175768394ec8SAlexander V. Chernikov 	ti->state = icfg->main_ptr;
175868394ec8SAlexander V. Chernikov 
175968394ec8SAlexander V. Chernikov 	mi->main_ptr = old_ptr;
176068394ec8SAlexander V. Chernikov 
176168394ec8SAlexander V. Chernikov 	return (0);
176268394ec8SAlexander V. Chernikov }
176368394ec8SAlexander V. Chernikov 
176468394ec8SAlexander V. Chernikov /*
176568394ec8SAlexander V. Chernikov  * Free unneded array.
176668394ec8SAlexander V. Chernikov  */
176768394ec8SAlexander V. Chernikov static void
176868394ec8SAlexander V. Chernikov ta_flush_mod_ifidx(void *ta_buf)
176968394ec8SAlexander V. Chernikov {
177068394ec8SAlexander V. Chernikov 	struct mod_ifidx *mi;
177168394ec8SAlexander V. Chernikov 
177268394ec8SAlexander V. Chernikov 	mi = (struct mod_ifidx *)ta_buf;
177368394ec8SAlexander V. Chernikov 	if (mi->main_ptr != NULL)
177468394ec8SAlexander V. Chernikov 		free(mi->main_ptr, M_IPFW);
17759f7d47b0SAlexander V. Chernikov }
17769f7d47b0SAlexander V. Chernikov 
17779f7d47b0SAlexander V. Chernikov static int
177868394ec8SAlexander V. Chernikov ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
177981d3153dSAlexander V. Chernikov     ipfw_obj_tentry *tent)
17809f7d47b0SAlexander V. Chernikov {
178168394ec8SAlexander V. Chernikov 	struct ifentry *ife;
17829f7d47b0SAlexander V. Chernikov 
178368394ec8SAlexander V. Chernikov 	ife = (struct ifentry *)e;
178468394ec8SAlexander V. Chernikov 
178581d3153dSAlexander V. Chernikov 	tent->masklen = 8 * IF_NAMESIZE;
178668394ec8SAlexander V. Chernikov 	memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
178768394ec8SAlexander V. Chernikov 	tent->value = ife->value;
17889f7d47b0SAlexander V. Chernikov 
17899f7d47b0SAlexander V. Chernikov 	return (0);
17909f7d47b0SAlexander V. Chernikov }
17919f7d47b0SAlexander V. Chernikov 
179281d3153dSAlexander V. Chernikov static int
179368394ec8SAlexander V. Chernikov ta_find_ifidx_tentry(void *ta_state, struct table_info *ti, void *key,
179481d3153dSAlexander V. Chernikov     uint32_t keylen, ipfw_obj_tentry *tent)
179581d3153dSAlexander V. Chernikov {
179668394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
179768394ec8SAlexander V. Chernikov 	struct ifentry *ife;
179868394ec8SAlexander V. Chernikov 	char *ifname;
179981d3153dSAlexander V. Chernikov 
180068394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
180168394ec8SAlexander V. Chernikov 	ifname = (char *)key;
180281d3153dSAlexander V. Chernikov 
180368394ec8SAlexander V. Chernikov 	if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
180468394ec8SAlexander V. Chernikov 		return (EINVAL);
180581d3153dSAlexander V. Chernikov 
180668394ec8SAlexander V. Chernikov 	ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
180768394ec8SAlexander V. Chernikov 
180868394ec8SAlexander V. Chernikov 	if (ife != NULL) {
180968394ec8SAlexander V. Chernikov 		ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
181081d3153dSAlexander V. Chernikov 		return (0);
181181d3153dSAlexander V. Chernikov 	}
181281d3153dSAlexander V. Chernikov 
181381d3153dSAlexander V. Chernikov 	return (ENOENT);
181481d3153dSAlexander V. Chernikov }
181581d3153dSAlexander V. Chernikov 
181668394ec8SAlexander V. Chernikov struct wa_ifidx {
181768394ec8SAlexander V. Chernikov 	ta_foreach_f	*f;
181868394ec8SAlexander V. Chernikov 	void		*arg;
181968394ec8SAlexander V. Chernikov };
182068394ec8SAlexander V. Chernikov 
18219f7d47b0SAlexander V. Chernikov static void
182268394ec8SAlexander V. Chernikov foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
18239f7d47b0SAlexander V. Chernikov     void *arg)
18249f7d47b0SAlexander V. Chernikov {
182568394ec8SAlexander V. Chernikov 	struct ifentry *ife;
182668394ec8SAlexander V. Chernikov 	struct wa_ifidx *wa;
18279f7d47b0SAlexander V. Chernikov 
182868394ec8SAlexander V. Chernikov 	ife = (struct ifentry *)no;
182968394ec8SAlexander V. Chernikov 	wa = (struct wa_ifidx *)arg;
183068394ec8SAlexander V. Chernikov 
183168394ec8SAlexander V. Chernikov 	wa->f(ife, wa->arg);
18329f7d47b0SAlexander V. Chernikov }
18339f7d47b0SAlexander V. Chernikov 
183468394ec8SAlexander V. Chernikov static void
183568394ec8SAlexander V. Chernikov ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
183668394ec8SAlexander V. Chernikov     void *arg)
183768394ec8SAlexander V. Chernikov {
183868394ec8SAlexander V. Chernikov 	struct iftable_cfg *icfg;
183968394ec8SAlexander V. Chernikov 	struct wa_ifidx wa;
184068394ec8SAlexander V. Chernikov 
184168394ec8SAlexander V. Chernikov 	icfg = (struct iftable_cfg *)ta_state;
184268394ec8SAlexander V. Chernikov 
184368394ec8SAlexander V. Chernikov 	wa.f = f;
184468394ec8SAlexander V. Chernikov 	wa.arg = arg;
184568394ec8SAlexander V. Chernikov 
184668394ec8SAlexander V. Chernikov 	ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
184768394ec8SAlexander V. Chernikov }
184868394ec8SAlexander V. Chernikov 
1849*74b941f0SAlexander V. Chernikov struct table_algo iface_idx = {
1850adea6201SAlexander V. Chernikov 	.name		= "iface:array",
185168394ec8SAlexander V. Chernikov 	.lookup		= ta_lookup_ifidx,
185268394ec8SAlexander V. Chernikov 	.init		= ta_init_ifidx,
185368394ec8SAlexander V. Chernikov 	.destroy	= ta_destroy_ifidx,
185468394ec8SAlexander V. Chernikov 	.prepare_add	= ta_prepare_add_ifidx,
185568394ec8SAlexander V. Chernikov 	.prepare_del	= ta_prepare_del_ifidx,
185668394ec8SAlexander V. Chernikov 	.add		= ta_add_ifidx,
185768394ec8SAlexander V. Chernikov 	.del		= ta_del_ifidx,
185868394ec8SAlexander V. Chernikov 	.flush_entry	= ta_flush_ifidx_entry,
185968394ec8SAlexander V. Chernikov 	.foreach	= ta_foreach_ifidx,
186068394ec8SAlexander V. Chernikov 	.dump_tentry	= ta_dump_ifidx_tentry,
186168394ec8SAlexander V. Chernikov 	.find_tentry	= ta_find_ifidx_tentry,
186268394ec8SAlexander V. Chernikov 	.prepare_mod	= ta_prepare_mod_ifidx,
186368394ec8SAlexander V. Chernikov 	.fill_mod	= ta_fill_mod_ifidx,
186468394ec8SAlexander V. Chernikov 	.modify		= ta_modify_ifidx,
186568394ec8SAlexander V. Chernikov 	.flush_mod	= ta_flush_mod_ifidx,
186668394ec8SAlexander V. Chernikov 	.change_ti	= ta_change_ti_ifidx,
18679f7d47b0SAlexander V. Chernikov };
18689f7d47b0SAlexander V. Chernikov 
18699f7d47b0SAlexander V. Chernikov void
18709f7d47b0SAlexander V. Chernikov ipfw_table_algo_init(struct ip_fw_chain *chain)
18719f7d47b0SAlexander V. Chernikov {
18729f7d47b0SAlexander V. Chernikov 	/*
18739f7d47b0SAlexander V. Chernikov 	 * Register all algorithms presented here.
18749f7d47b0SAlexander V. Chernikov 	 */
1875*74b941f0SAlexander V. Chernikov 	ipfw_add_table_algo(chain, &cidr_radix);
1876*74b941f0SAlexander V. Chernikov 	ipfw_add_table_algo(chain, &cidr_hash);
1877*74b941f0SAlexander V. Chernikov 	ipfw_add_table_algo(chain, &iface_idx);
18789f7d47b0SAlexander V. Chernikov }
18799f7d47b0SAlexander V. Chernikov 
18809f7d47b0SAlexander V. Chernikov void
18819f7d47b0SAlexander V. Chernikov ipfw_table_algo_destroy(struct ip_fw_chain *chain)
18829f7d47b0SAlexander V. Chernikov {
18839f7d47b0SAlexander V. Chernikov 	/* Do nothing */
18849f7d47b0SAlexander V. Chernikov }
18859f7d47b0SAlexander V. Chernikov 
18869f7d47b0SAlexander V. Chernikov 
1887