1/*-
2 * Copyright (c) 2014 Yandex LLC
3 * Copyright (c) 2014 Alexander V. Chernikov
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27#include <sys/cdefs.h>
28__FBSDID("$FreeBSD$");
29
30/*
31 * Lookup table algorithms.
32 *
33 */
34
35#include "opt_ipfw.h"
36#include "opt_inet.h"
37#ifndef INET
38#error IPFIREWALL requires INET.
39#endif /* INET */
40#include "opt_inet6.h"
41
42#include <sys/param.h>
43#include <sys/systm.h>
44#include <sys/malloc.h>
45#include <sys/kernel.h>
46#include <sys/lock.h>
47#include <sys/rwlock.h>
48#include <sys/rmlock.h>
49#include <sys/socket.h>
50#include <sys/queue.h>
51#include <net/if.h>	/* ip_fw.h requires IFNAMSIZ */
52#include <net/radix.h>
53#include <net/route.h>
54#include <net/route/nhop.h>
55#include <net/route/route_var.h>
56
57#include <netinet/in.h>
58#include <netinet/in_fib.h>
59#include <netinet/ip_var.h>	/* struct ipfw_rule_ref */
60#include <netinet/ip_fw.h>
61#include <netinet6/in6_fib.h>
62
63#include <netpfil/ipfw/ip_fw_private.h>
64#include <netpfil/ipfw/ip_fw_table.h>
65
66
67/*
68 * IPFW table lookup algorithms.
69 *
70 * What is needed to add another table algo?
71 *
72 * Algo init:
73 * * struct table_algo has to be filled with:
74 *   name: "type:algoname" format, e.g. "addr:radix". Currently
75 *     there are the following types: "addr", "iface", "number" and "flow".
76 *   type: one of IPFW_TABLE_* types
77 *   flags: one or more TA_FLAGS_*
78 *   ta_buf_size: size of structure used to store add/del item state.
79 *     Needs to be less than TA_BUF_SZ.
80 *   callbacks: see below for description.
81 * * ipfw_add_table_algo / ipfw_del_table_algo has to be called
82 *
83 * Callbacks description:
84 *
85 * -init: request to initialize new table instance.
86 * typedef int (ta_init)(struct ip_fw_chain *ch, void **ta_state,
87 *     struct table_info *ti, char *data, uint8_t tflags);
88 * MANDATORY, unlocked. (M_WAITOK). Returns 0 on success.
89 *
90 *  Allocate all structures needed for normal operations.
91 *  * Caller may want to parse @data for some algo-specific
92 *    options provided by userland.
93 *  * Caller may want to save configuration state pointer to @ta_state
94 *  * Caller needs to save desired runtime structure pointer(s)
95 *    inside @ti fields. Note that it is not correct to save
96 *    @ti pointer at this moment. Use -change_ti hook for that.
97 *  * Caller has to fill in ti->lookup to appropriate function
98 *    pointer.
99 *
100 *
101 *
102 * -destroy: request to destroy table instance.
103 * typedef void (ta_destroy)(void *ta_state, struct table_info *ti);
104 * MANDATORY, unlocked. (M_WAITOK).
105 *
106 * Frees all table entries and all tables structures allocated by -init.
107 *
108 *
109 *
110 * -prepare_add: request to allocate state for adding new entry.
111 * typedef int (ta_prepare_add)(struct ip_fw_chain *ch, struct tentry_info *tei,
112 *     void *ta_buf);
113 * MANDATORY, unlocked. (M_WAITOK). Returns 0 on success.
114 *
115 * Allocates state and fills it in with all necessary data (EXCEPT value)
116 * from @tei to minimize operations needed to be done under WLOCK.
117 * "value" field has to be copied to new entry in @add callback.
118 * Buffer ta_buf of size ta->ta_buf_sz may be used to store
119 * allocated state.
120 *
121 *
122 *
123 * -prepare_del: request to set state for deleting existing entry.
124 * typedef int (ta_prepare_del)(struct ip_fw_chain *ch, struct tentry_info *tei,
125 *     void *ta_buf);
126 * MANDATORY, locked, UH. (M_NOWAIT). Returns 0 on success.
127 *
128 * Buffer ta_buf of size ta->ta_buf_sz may be used to store
129 * allocated state. Caller should use on-stack ta_buf allocation
130 * instead of doing malloc().
131 *
132 *
133 *
134 * -add: request to insert new entry into runtime/config structures.
135 *  typedef int (ta_add)(void *ta_state, struct table_info *ti,
136 *     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
137 * MANDATORY, UH+WLOCK. (M_NOWAIT). Returns 0 on success.
138 *
139 * Insert new entry using previously-allocated state in @ta_buf.
140 * * @tei may have the following flags:
141 *   TEI_FLAGS_UPDATE: request to add or update entry.
142 *   TEI_FLAGS_DONTADD: request to update (but not add) entry.
143 * * Caller is required to do the following:
144 *   copy real entry value from @tei
145 *   entry added: return 0, set 1 to @pnum
146 *   entry updated: return 0, store 0 to @pnum, store old value in @tei,
147 *     add TEI_FLAGS_UPDATED flag to @tei.
148 *   entry exists: return EEXIST
149 *   entry not found: return ENOENT
150 *   other error: return non-zero error code.
151 *
152 *
153 *
154 * -del: request to delete existing entry from runtime/config structures.
155 *  typedef int (ta_del)(void *ta_state, struct table_info *ti,
156 *     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
157 *  MANDATORY, UH+WLOCK. (M_NOWAIT). Returns 0 on success.
158 *
159 *  Delete entry using previously set up in @ta_buf.
160 * * Caller is required to do the following:
161 *   entry deleted: return 0, set 1 to @pnum, store old value in @tei.
162 *   entry not found: return ENOENT
163 *   other error: return non-zero error code.
164 *
165 *
166 *
167 * -flush_entry: flush entry state created by -prepare_add / -del / others
168 *  typedef void (ta_flush_entry)(struct ip_fw_chain *ch,
169 *      struct tentry_info *tei, void *ta_buf);
170 *  MANDATORY, may be locked. (M_NOWAIT).
171 *
172 *  Delete state allocated by:
173 *  -prepare_add (-add returned EEXIST|UPDATED)
174 *  -prepare_del (if any)
175 *  -del
176 *  * Caller is required to handle empty @ta_buf correctly.
177 *
178 *
179 * -find_tentry: finds entry specified by key @tei
180 *  typedef int ta_find_tentry(void *ta_state, struct table_info *ti,
181 *      ipfw_obj_tentry *tent);
182 *  OPTIONAL, locked (UH). (M_NOWAIT). Returns 0 on success.
183 *
184 *  Finds entry specified by given key.
185 *  * Caller is required to do the following:
186 *    entry found: returns 0, export entry to @tent
187 *    entry not found: returns ENOENT
188 *
189 *
190 * -need_modify: checks if @ti has enough space to hold another @count items.
191 *  typedef int (ta_need_modify)(void *ta_state, struct table_info *ti,
192 *      uint32_t count, uint64_t *pflags);
193 *  OPTIONAL, locked (UH). (M_NOWAIT). Returns 0 if has.
194 *
195 *  Checks if given table has enough space to add @count items without
196 *  resize. Caller may use @pflags to store desired modification data.
197 *
198 *
199 *
200 * -prepare_mod: allocate structures for table modification.
201 *  typedef int (ta_prepare_mod)(void *ta_buf, uint64_t *pflags);
202 * OPTIONAL(need_modify), unlocked. (M_WAITOK). Returns 0 on success.
203 *
204 * Allocate all needed state for table modification. Caller
205 * should use `struct mod_item` to store new state in @ta_buf.
206 * Up to TA_BUF_SZ (128 bytes) can be stored in @ta_buf.
207 *
208 *
209 *
210 * -fill_mod: copy some data to new state/
211 *  typedef int (ta_fill_mod)(void *ta_state, struct table_info *ti,
212 *      void *ta_buf, uint64_t *pflags);
213 * OPTIONAL(need_modify), locked (UH). (M_NOWAIT). Returns 0 on success.
214 *
215 * Copy as much data as we can to minimize changes under WLOCK.
216 * For example, array can be merged inside this callback.
217 *
218 *
219 *
220 * -modify: perform final modification.
221 *  typedef void (ta_modify)(void *ta_state, struct table_info *ti,
222 *      void *ta_buf, uint64_t pflags);
223 * OPTIONAL(need_modify), locked (UH+WLOCK). (M_NOWAIT).
224 *
225 * Performs all changes necessary to switch to new structures.
226 * * Caller should save old pointers to @ta_buf storage.
227 *
228 *
229 *
230 * -flush_mod: flush table modification state.
231 *  typedef void (ta_flush_mod)(void *ta_buf);
232 * OPTIONAL(need_modify), unlocked. (M_WAITOK).
233 *
234 * Performs flush for the following:
235 *   - prepare_mod (modification was not necessary)
236 *   - modify (for the old state)
237 *
238 *
239 *
240 * -change_gi: monitor table info pointer changes
241 * typedef void (ta_change_ti)(void *ta_state, struct table_info *ti);
242 * OPTIONAL, locked (UH). (M_NOWAIT).
243 *
244 * Called on @ti pointer changed. Called immediately after -init
245 * to set initial state.
246 *
247 *
248 *
249 * -foreach: calls @f for each table entry
250 *  typedef void ta_foreach(void *ta_state, struct table_info *ti,
251 *      ta_foreach_f *f, void *arg);
252 * MANDATORY, locked(UH). (M_NOWAIT).
253 *
254 * Runs callback with specified argument for each table entry,
255 * Typically used for dumping table entries.
256 *
257 *
258 *
259 * -dump_tentry: dump table entry in current @tentry format.
260 *  typedef int ta_dump_tentry(void *ta_state, struct table_info *ti, void *e,
261 *      ipfw_obj_tentry *tent);
262 * MANDATORY, locked(UH). (M_NOWAIT). Returns 0 on success.
263 *
264 * Dumps entry @e to @tent.
265 *
266 *
267 * -print_config: prints custom algorithm options into buffer.
268 *  typedef void (ta_print_config)(void *ta_state, struct table_info *ti,
269 *      char *buf, size_t bufsize);
270 * OPTIONAL. locked(UH). (M_NOWAIT).
271 *
272 * Prints custom algorithm options in the format suitable to pass
273 * back to -init callback.
274 *
275 *
276 *
277 * -dump_tinfo: dumps algo-specific info.
278 *  typedef void ta_dump_tinfo(void *ta_state, struct table_info *ti,
279 *      ipfw_ta_tinfo *tinfo);
280 * OPTIONAL. locked(UH). (M_NOWAIT).
281 *
282 * Dumps options like items size/hash size, etc.
283 */
284
285MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
286
287/*
288 * Utility structures/functions common to more than one algo
289 */
290
291struct mod_item {
292	void	*main_ptr;
293	size_t	size;
294	void	*main_ptr6;
295	size_t	size6;
296};
297
298static int badd(const void *key, void *item, void *base, size_t nmemb,
299    size_t size, int (*compar) (const void *, const void *));
300static int bdel(const void *key, void *base, size_t nmemb, size_t size,
301    int (*compar) (const void *, const void *));
302
303
304/*
305 * ADDR implementation using radix
306 *
307 */
308
309/*
310 * The radix code expects addr and mask to be array of bytes,
311 * with the first byte being the length of the array. rn_inithead
312 * is called with the offset in bits of the lookup key within the
313 * array. If we use a sockaddr_in as the underlying type,
314 * sin_len is conveniently located at offset 0, sin_addr is at
315 * offset 4 and normally aligned.
316 * But for portability, let's avoid assumption and make the code explicit
317 */
318#define KEY_LEN(v)	*((uint8_t *)&(v))
319/*
320 * Do not require radix to compare more than actual IPv4/IPv6 address
321 */
322#define KEY_LEN_INET	(offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))
323#define KEY_LEN_INET6	(offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr))
324
325#define OFF_LEN_INET	(8 * offsetof(struct sockaddr_in, sin_addr))
326#define OFF_LEN_INET6	(8 * offsetof(struct sa_in6, sin6_addr))
327
328struct radix_addr_entry {
329	struct radix_node	rn[2];
330	struct sockaddr_in	addr;
331	uint32_t		value;
332	uint8_t			masklen;
333};
334
335struct sa_in6 {
336	uint8_t			sin6_len;
337	uint8_t			sin6_family;
338	uint8_t			pad[2];
339	struct in6_addr		sin6_addr;
340};
341
342struct radix_addr_xentry {
343	struct radix_node	rn[2];
344	struct sa_in6		addr6;
345	uint32_t		value;
346	uint8_t			masklen;
347};
348
349struct radix_cfg {
350	struct radix_node_head	*head4;
351	struct radix_node_head	*head6;
352	size_t			count4;
353	size_t			count6;
354};
355
356struct ta_buf_radix
357{
358	void *ent_ptr;
359	struct sockaddr	*addr_ptr;
360	struct sockaddr	*mask_ptr;
361	union {
362		struct {
363			struct sockaddr_in sa;
364			struct sockaddr_in ma;
365		} a4;
366		struct {
367			struct sa_in6 sa;
368			struct sa_in6 ma;
369		} a6;
370	} addr;
371};
372
373static int ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
374    uint32_t *val);
375static int ta_init_radix(struct ip_fw_chain *ch, void **ta_state,
376    struct table_info *ti, char *data, uint8_t tflags);
377static int flush_radix_entry(struct radix_node *rn, void *arg);
378static void ta_destroy_radix(void *ta_state, struct table_info *ti);
379static void ta_dump_radix_tinfo(void *ta_state, struct table_info *ti,
380    ipfw_ta_tinfo *tinfo);
381static int ta_dump_radix_tentry(void *ta_state, struct table_info *ti,
382    void *e, ipfw_obj_tentry *tent);
383static int ta_find_radix_tentry(void *ta_state, struct table_info *ti,
384    ipfw_obj_tentry *tent);
385static void ta_foreach_radix(void *ta_state, struct table_info *ti,
386    ta_foreach_f *f, void *arg);
387static void tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
388    struct sockaddr *ma, int *set_mask);
389static int ta_prepare_add_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
390    void *ta_buf);
391static int ta_add_radix(void *ta_state, struct table_info *ti,
392    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
393static int ta_prepare_del_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
394    void *ta_buf);
395static int ta_del_radix(void *ta_state, struct table_info *ti,
396    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
397static void ta_flush_radix_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
398    void *ta_buf);
399static int ta_need_modify_radix(void *ta_state, struct table_info *ti,
400    uint32_t count, uint64_t *pflags);
401
402static int
403ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
404    uint32_t *val)
405{
406	struct radix_node_head *rnh;
407
408	if (keylen == sizeof(in_addr_t)) {
409		struct radix_addr_entry *ent;
410		struct sockaddr_in sa;
411		KEY_LEN(sa) = KEY_LEN_INET;
412		sa.sin_addr.s_addr = *((in_addr_t *)key);
413		rnh = (struct radix_node_head *)ti->state;
414		ent = (struct radix_addr_entry *)(rnh->rnh_matchaddr(&sa, &rnh->rh));
415		if (ent != NULL) {
416			*val = ent->value;
417			return (1);
418		}
419	} else {
420		struct radix_addr_xentry *xent;
421		struct sa_in6 sa6;
422		KEY_LEN(sa6) = KEY_LEN_INET6;
423		memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
424		rnh = (struct radix_node_head *)ti->xstate;
425		xent = (struct radix_addr_xentry *)(rnh->rnh_matchaddr(&sa6, &rnh->rh));
426		if (xent != NULL) {
427			*val = xent->value;
428			return (1);
429		}
430	}
431
432	return (0);
433}
434
435/*
436 * New table
437 */
438static int
439ta_init_radix(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
440    char *data, uint8_t tflags)
441{
442	struct radix_cfg *cfg;
443
444	if (!rn_inithead(&ti->state, OFF_LEN_INET))
445		return (ENOMEM);
446	if (!rn_inithead(&ti->xstate, OFF_LEN_INET6)) {
447		rn_detachhead(&ti->state);
448		return (ENOMEM);
449	}
450
451	cfg = malloc(sizeof(struct radix_cfg), M_IPFW, M_WAITOK | M_ZERO);
452
453	*ta_state = cfg;
454	ti->lookup = ta_lookup_radix;
455
456	return (0);
457}
458
459static int
460flush_radix_entry(struct radix_node *rn, void *arg)
461{
462	struct radix_node_head * const rnh = arg;
463	struct radix_addr_entry *ent;
464
465	ent = (struct radix_addr_entry *)
466	    rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, &rnh->rh);
467	if (ent != NULL)
468		free(ent, M_IPFW_TBL);
469	return (0);
470}
471
472static void
473ta_destroy_radix(void *ta_state, struct table_info *ti)
474{
475	struct radix_cfg *cfg;
476	struct radix_node_head *rnh;
477
478	cfg = (struct radix_cfg *)ta_state;
479
480	rnh = (struct radix_node_head *)(ti->state);
481	rnh->rnh_walktree(&rnh->rh, flush_radix_entry, rnh);
482	rn_detachhead(&ti->state);
483
484	rnh = (struct radix_node_head *)(ti->xstate);
485	rnh->rnh_walktree(&rnh->rh, flush_radix_entry, rnh);
486	rn_detachhead(&ti->xstate);
487
488	free(cfg, M_IPFW);
489}
490
491/*
492 * Provide algo-specific table info
493 */
494static void
495ta_dump_radix_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
496{
497	struct radix_cfg *cfg;
498
499	cfg = (struct radix_cfg *)ta_state;
500
501	tinfo->flags = IPFW_TATFLAGS_AFDATA | IPFW_TATFLAGS_AFITEM;
502	tinfo->taclass4 = IPFW_TACLASS_RADIX;
503	tinfo->count4 = cfg->count4;
504	tinfo->itemsize4 = sizeof(struct radix_addr_entry);
505	tinfo->taclass6 = IPFW_TACLASS_RADIX;
506	tinfo->count6 = cfg->count6;
507	tinfo->itemsize6 = sizeof(struct radix_addr_xentry);
508}
509
510static int
511ta_dump_radix_tentry(void *ta_state, struct table_info *ti, void *e,
512    ipfw_obj_tentry *tent)
513{
514	struct radix_addr_entry *n;
515#ifdef INET6
516	struct radix_addr_xentry *xn;
517#endif
518
519	n = (struct radix_addr_entry *)e;
520
521	/* Guess IPv4/IPv6 radix by sockaddr family */
522	if (n->addr.sin_family == AF_INET) {
523		tent->k.addr.s_addr = n->addr.sin_addr.s_addr;
524		tent->masklen = n->masklen;
525		tent->subtype = AF_INET;
526		tent->v.kidx = n->value;
527#ifdef INET6
528	} else {
529		xn = (struct radix_addr_xentry *)e;
530		memcpy(&tent->k.addr6, &xn->addr6.sin6_addr,
531		    sizeof(struct in6_addr));
532		tent->masklen = xn->masklen;
533		tent->subtype = AF_INET6;
534		tent->v.kidx = xn->value;
535#endif
536	}
537
538	return (0);
539}
540
541static int
542ta_find_radix_tentry(void *ta_state, struct table_info *ti,
543    ipfw_obj_tentry *tent)
544{
545	struct radix_node_head *rnh;
546	void *e;
547
548	e = NULL;
549	if (tent->subtype == AF_INET) {
550		struct sockaddr_in sa;
551		KEY_LEN(sa) = KEY_LEN_INET;
552		sa.sin_addr.s_addr = tent->k.addr.s_addr;
553		rnh = (struct radix_node_head *)ti->state;
554		e = rnh->rnh_matchaddr(&sa, &rnh->rh);
555	} else {
556		struct sa_in6 sa6;
557		KEY_LEN(sa6) = KEY_LEN_INET6;
558		memcpy(&sa6.sin6_addr, &tent->k.addr6, sizeof(struct in6_addr));
559		rnh = (struct radix_node_head *)ti->xstate;
560		e = rnh->rnh_matchaddr(&sa6, &rnh->rh);
561	}
562
563	if (e != NULL) {
564		ta_dump_radix_tentry(ta_state, ti, e, tent);
565		return (0);
566	}
567
568	return (ENOENT);
569}
570
571static void
572ta_foreach_radix(void *ta_state, struct table_info *ti, ta_foreach_f *f,
573    void *arg)
574{
575	struct radix_node_head *rnh;
576
577	rnh = (struct radix_node_head *)(ti->state);
578	rnh->rnh_walktree(&rnh->rh, (walktree_f_t *)f, arg);
579
580	rnh = (struct radix_node_head *)(ti->xstate);
581	rnh->rnh_walktree(&rnh->rh, (walktree_f_t *)f, arg);
582}
583
584
585#ifdef INET6
586static inline void ipv6_writemask(struct in6_addr *addr6, uint8_t mask);
587
588static inline void
589ipv6_writemask(struct in6_addr *addr6, uint8_t mask)
590{
591	uint32_t *cp;
592
593	for (cp = (uint32_t *)addr6; mask >= 32; mask -= 32)
594		*cp++ = 0xFFFFFFFF;
595	if (mask > 0)
596		*cp = htonl(mask ? ~((1 << (32 - mask)) - 1) : 0);
597}
598#endif
599
600static void
601tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
602    struct sockaddr *ma, int *set_mask)
603{
604	int mlen;
605#ifdef INET
606	struct sockaddr_in *addr, *mask;
607#endif
608#ifdef INET6
609	struct sa_in6 *addr6, *mask6;
610#endif
611	in_addr_t a4;
612
613	mlen = tei->masklen;
614
615	if (tei->subtype == AF_INET) {
616#ifdef INET
617		addr = (struct sockaddr_in *)sa;
618		mask = (struct sockaddr_in *)ma;
619		/* Set 'total' structure length */
620		KEY_LEN(*addr) = KEY_LEN_INET;
621		KEY_LEN(*mask) = KEY_LEN_INET;
622		addr->sin_family = AF_INET;
623		mask->sin_addr.s_addr =
624		    htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
625		a4 = *((in_addr_t *)tei->paddr);
626		addr->sin_addr.s_addr = a4 & mask->sin_addr.s_addr;
627		if (mlen != 32)
628			*set_mask = 1;
629		else
630			*set_mask = 0;
631#endif
632#ifdef INET6
633	} else if (tei->subtype == AF_INET6) {
634		/* IPv6 case */
635		addr6 = (struct sa_in6 *)sa;
636		mask6 = (struct sa_in6 *)ma;
637		/* Set 'total' structure length */
638		KEY_LEN(*addr6) = KEY_LEN_INET6;
639		KEY_LEN(*mask6) = KEY_LEN_INET6;
640		addr6->sin6_family = AF_INET6;
641		ipv6_writemask(&mask6->sin6_addr, mlen);
642		memcpy(&addr6->sin6_addr, tei->paddr, sizeof(struct in6_addr));
643		APPLY_MASK(&addr6->sin6_addr, &mask6->sin6_addr);
644		if (mlen != 128)
645			*set_mask = 1;
646		else
647			*set_mask = 0;
648#endif
649	}
650}
651
652static int
653ta_prepare_add_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
654    void *ta_buf)
655{
656	struct ta_buf_radix *tb;
657	struct radix_addr_entry *ent;
658#ifdef INET6
659	struct radix_addr_xentry *xent;
660#endif
661	struct sockaddr *addr, *mask;
662	int mlen, set_mask;
663
664	tb = (struct ta_buf_radix *)ta_buf;
665
666	mlen = tei->masklen;
667	set_mask = 0;
668
669	if (tei->subtype == AF_INET) {
670#ifdef INET
671		if (mlen > 32)
672			return (EINVAL);
673		ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
674		ent->masklen = mlen;
675
676		addr = (struct sockaddr *)&ent->addr;
677		mask = (struct sockaddr *)&tb->addr.a4.ma;
678		tb->ent_ptr = ent;
679#endif
680#ifdef INET6
681	} else if (tei->subtype == AF_INET6) {
682		/* IPv6 case */
683		if (mlen > 128)
684			return (EINVAL);
685		xent = malloc(sizeof(*xent), M_IPFW_TBL, M_WAITOK | M_ZERO);
686		xent->masklen = mlen;
687
688		addr = (struct sockaddr *)&xent->addr6;
689		mask = (struct sockaddr *)&tb->addr.a6.ma;
690		tb->ent_ptr = xent;
691#endif
692	} else {
693		/* Unknown CIDR type */
694		return (EINVAL);
695	}
696
697	tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
698	/* Set pointers */
699	tb->addr_ptr = addr;
700	if (set_mask != 0)
701		tb->mask_ptr = mask;
702
703	return (0);
704}
705
706static int
707ta_add_radix(void *ta_state, struct table_info *ti, struct tentry_info *tei,
708    void *ta_buf, uint32_t *pnum)
709{
710	struct radix_cfg *cfg;
711	struct radix_node_head *rnh;
712	struct radix_node *rn;
713	struct ta_buf_radix *tb;
714	uint32_t *old_value, value;
715
716	cfg = (struct radix_cfg *)ta_state;
717	tb = (struct ta_buf_radix *)ta_buf;
718
719	/* Save current entry value from @tei */
720	if (tei->subtype == AF_INET) {
721		rnh = ti->state;
722		((struct radix_addr_entry *)tb->ent_ptr)->value = tei->value;
723	} else {
724		rnh = ti->xstate;
725		((struct radix_addr_xentry *)tb->ent_ptr)->value = tei->value;
726	}
727
728	/* Search for an entry first */
729	rn = rnh->rnh_lookup(tb->addr_ptr, tb->mask_ptr, &rnh->rh);
730	if (rn != NULL) {
731		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
732			return (EEXIST);
733		/* Record already exists. Update value if we're asked to */
734		if (tei->subtype == AF_INET)
735			old_value = &((struct radix_addr_entry *)rn)->value;
736		else
737			old_value = &((struct radix_addr_xentry *)rn)->value;
738
739		value = *old_value;
740		*old_value = tei->value;
741		tei->value = value;
742
743		/* Indicate that update has happened instead of addition */
744		tei->flags |= TEI_FLAGS_UPDATED;
745		*pnum = 0;
746
747		return (0);
748	}
749
750	if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
751		return (EFBIG);
752
753	rn = rnh->rnh_addaddr(tb->addr_ptr, tb->mask_ptr, &rnh->rh,tb->ent_ptr);
754	if (rn == NULL) {
755		/* Unknown error */
756		return (EINVAL);
757	}
758
759	if (tei->subtype == AF_INET)
760		cfg->count4++;
761	else
762		cfg->count6++;
763	tb->ent_ptr = NULL;
764	*pnum = 1;
765
766	return (0);
767}
768
769static int
770ta_prepare_del_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
771    void *ta_buf)
772{
773	struct ta_buf_radix *tb;
774	struct sockaddr *addr, *mask;
775	int mlen, set_mask;
776
777	tb = (struct ta_buf_radix *)ta_buf;
778
779	mlen = tei->masklen;
780	set_mask = 0;
781
782	if (tei->subtype == AF_INET) {
783		if (mlen > 32)
784			return (EINVAL);
785
786		addr = (struct sockaddr *)&tb->addr.a4.sa;
787		mask = (struct sockaddr *)&tb->addr.a4.ma;
788#ifdef INET6
789	} else if (tei->subtype == AF_INET6) {
790		if (mlen > 128)
791			return (EINVAL);
792
793		addr = (struct sockaddr *)&tb->addr.a6.sa;
794		mask = (struct sockaddr *)&tb->addr.a6.ma;
795#endif
796	} else
797		return (EINVAL);
798
799	tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
800	tb->addr_ptr = addr;
801	if (set_mask != 0)
802		tb->mask_ptr = mask;
803
804	return (0);
805}
806
807static int
808ta_del_radix(void *ta_state, struct table_info *ti, struct tentry_info *tei,
809    void *ta_buf, uint32_t *pnum)
810{
811	struct radix_cfg *cfg;
812	struct radix_node_head *rnh;
813	struct radix_node *rn;
814	struct ta_buf_radix *tb;
815
816	cfg = (struct radix_cfg *)ta_state;
817	tb = (struct ta_buf_radix *)ta_buf;
818
819	if (tei->subtype == AF_INET)
820		rnh = ti->state;
821	else
822		rnh = ti->xstate;
823
824	rn = rnh->rnh_deladdr(tb->addr_ptr, tb->mask_ptr, &rnh->rh);
825
826	if (rn == NULL)
827		return (ENOENT);
828
829	/* Save entry value to @tei */
830	if (tei->subtype == AF_INET)
831		tei->value = ((struct radix_addr_entry *)rn)->value;
832	else
833		tei->value = ((struct radix_addr_xentry *)rn)->value;
834
835	tb->ent_ptr = rn;
836
837	if (tei->subtype == AF_INET)
838		cfg->count4--;
839	else
840		cfg->count6--;
841	*pnum = 1;
842
843	return (0);
844}
845
846static void
847ta_flush_radix_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
848    void *ta_buf)
849{
850	struct ta_buf_radix *tb;
851
852	tb = (struct ta_buf_radix *)ta_buf;
853
854	if (tb->ent_ptr != NULL)
855		free(tb->ent_ptr, M_IPFW_TBL);
856}
857
858static int
859ta_need_modify_radix(void *ta_state, struct table_info *ti, uint32_t count,
860    uint64_t *pflags)
861{
862
863	/*
864	 * radix does not require additional memory allocations
865	 * other than nodes itself. Adding new masks to the tree do
866	 * but we don't have any API to call (and we don't known which
867	 * sizes do we need).
868	 */
869	return (0);
870}
871
872struct table_algo addr_radix = {
873	.name		= "addr:radix",
874	.type		= IPFW_TABLE_ADDR,
875	.flags		= TA_FLAG_DEFAULT,
876	.ta_buf_size	= sizeof(struct ta_buf_radix),
877	.init		= ta_init_radix,
878	.destroy	= ta_destroy_radix,
879	.prepare_add	= ta_prepare_add_radix,
880	.prepare_del	= ta_prepare_del_radix,
881	.add		= ta_add_radix,
882	.del		= ta_del_radix,
883	.flush_entry	= ta_flush_radix_entry,
884	.foreach	= ta_foreach_radix,
885	.dump_tentry	= ta_dump_radix_tentry,
886	.find_tentry	= ta_find_radix_tentry,
887	.dump_tinfo	= ta_dump_radix_tinfo,
888	.need_modify	= ta_need_modify_radix,
889};
890
891
892/*
893 * addr:hash cmds
894 *
895 *
896 * ti->data:
897 * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
898 * [        8][        8[          8][         8]
899 *
900 * inv.mask4: 32 - mask
901 * inv.mask6:
902 * 1) _slow lookup: mask
903 * 2) _aligned: (128 - mask) / 8
904 * 3) _64: 8
905 *
906 *
907 * pflags:
908 * [v4=1/v6=0][hsize]
909 * [       32][   32]
910 */
911
912struct chashentry;
913
914SLIST_HEAD(chashbhead, chashentry);
915
916struct chash_cfg {
917	struct chashbhead *head4;
918	struct chashbhead *head6;
919	size_t	size4;
920	size_t	size6;
921	size_t	items4;
922	size_t	items6;
923	uint8_t	mask4;
924	uint8_t	mask6;
925};
926
927struct chashentry {
928	SLIST_ENTRY(chashentry)	next;
929	uint32_t	value;
930	uint32_t	type;
931	union {
932		uint32_t	a4;	/* Host format */
933		struct in6_addr	a6;	/* Network format */
934	} a;
935};
936
937struct ta_buf_chash
938{
939	void *ent_ptr;
940	struct chashentry ent;
941};
942
943#ifdef INET
944static __inline uint32_t hash_ip(uint32_t addr, int hsize);
945#endif
946#ifdef INET6
947static __inline uint32_t hash_ip6(struct in6_addr *addr6, int hsize);
948static __inline uint16_t hash_ip64(struct in6_addr *addr6, int hsize);
949static __inline uint32_t hash_ip6_slow(struct in6_addr *addr6, void *key,
950    int mask, int hsize);
951static __inline uint32_t hash_ip6_al(struct in6_addr *addr6, void *key, int mask,
952    int hsize);
953#endif
954static int ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
955    uint32_t *val);
956static int ta_lookup_chash_aligned(struct table_info *ti, void *key,
957    uint32_t keylen, uint32_t *val);
958static int ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
959    uint32_t *val);
960static int chash_parse_opts(struct chash_cfg *cfg, char *data);
961static void ta_print_chash_config(void *ta_state, struct table_info *ti,
962    char *buf, size_t bufsize);
963static int ta_log2(uint32_t v);
964static int ta_init_chash(struct ip_fw_chain *ch, void **ta_state,
965    struct table_info *ti, char *data, uint8_t tflags);
966static void ta_destroy_chash(void *ta_state, struct table_info *ti);
967static void ta_dump_chash_tinfo(void *ta_state, struct table_info *ti,
968    ipfw_ta_tinfo *tinfo);
969static int ta_dump_chash_tentry(void *ta_state, struct table_info *ti,
970    void *e, ipfw_obj_tentry *tent);
971static uint32_t hash_ent(struct chashentry *ent, int af, int mlen,
972    uint32_t size);
973static int tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent);
974static int ta_find_chash_tentry(void *ta_state, struct table_info *ti,
975    ipfw_obj_tentry *tent);
976static void ta_foreach_chash(void *ta_state, struct table_info *ti,
977    ta_foreach_f *f, void *arg);
978static int ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
979    void *ta_buf);
980static int ta_add_chash(void *ta_state, struct table_info *ti,
981    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
982static int ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
983    void *ta_buf);
984static int ta_del_chash(void *ta_state, struct table_info *ti,
985    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
986static void ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
987    void *ta_buf);
988static int ta_need_modify_chash(void *ta_state, struct table_info *ti,
989    uint32_t count, uint64_t *pflags);
990static int ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags);
991static int ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
992    uint64_t *pflags);
993static void ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
994    uint64_t pflags);
995static void ta_flush_mod_chash(void *ta_buf);
996
997
998#ifdef INET
999static __inline uint32_t
1000hash_ip(uint32_t addr, int hsize)
1001{
1002
1003	return (addr % (hsize - 1));
1004}
1005#endif
1006
1007#ifdef INET6
1008static __inline uint32_t
1009hash_ip6(struct in6_addr *addr6, int hsize)
1010{
1011	uint32_t i;
1012
1013	i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1] ^
1014	    addr6->s6_addr32[2] ^ addr6->s6_addr32[3];
1015
1016	return (i % (hsize - 1));
1017}
1018
1019
1020static __inline uint16_t
1021hash_ip64(struct in6_addr *addr6, int hsize)
1022{
1023	uint32_t i;
1024
1025	i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1];
1026
1027	return (i % (hsize - 1));
1028}
1029
1030
1031static __inline uint32_t
1032hash_ip6_slow(struct in6_addr *addr6, void *key, int mask, int hsize)
1033{
1034	struct in6_addr mask6;
1035
1036	ipv6_writemask(&mask6, mask);
1037	memcpy(addr6, key, sizeof(struct in6_addr));
1038	APPLY_MASK(addr6, &mask6);
1039	return (hash_ip6(addr6, hsize));
1040}
1041
1042static __inline uint32_t
1043hash_ip6_al(struct in6_addr *addr6, void *key, int mask, int hsize)
1044{
1045	uint64_t *paddr;
1046
1047	paddr = (uint64_t *)addr6;
1048	*paddr = 0;
1049	*(paddr + 1) = 0;
1050	memcpy(addr6, key, mask);
1051	return (hash_ip6(addr6, hsize));
1052}
1053#endif
1054
1055static int
1056ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
1057    uint32_t *val)
1058{
1059	struct chashbhead *head;
1060	struct chashentry *ent;
1061	uint16_t hash, hsize;
1062	uint8_t imask;
1063
1064	if (keylen == sizeof(in_addr_t)) {
1065#ifdef INET
1066		head = (struct chashbhead *)ti->state;
1067		imask = ti->data >> 24;
1068		hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1069		uint32_t a;
1070		a = ntohl(*((in_addr_t *)key));
1071		a = a >> imask;
1072		hash = hash_ip(a, hsize);
1073		SLIST_FOREACH(ent, &head[hash], next) {
1074			if (ent->a.a4 == a) {
1075				*val = ent->value;
1076				return (1);
1077			}
1078		}
1079#endif
1080	} else {
1081#ifdef INET6
1082		/* IPv6: worst scenario: non-round mask */
1083		struct in6_addr addr6;
1084		head = (struct chashbhead *)ti->xstate;
1085		imask = (ti->data & 0xFF0000) >> 16;
1086		hsize = 1 << (ti->data & 0xFF);
1087		hash = hash_ip6_slow(&addr6, key, imask, hsize);
1088		SLIST_FOREACH(ent, &head[hash], next) {
1089			if (memcmp(&ent->a.a6, &addr6, 16) == 0) {
1090				*val = ent->value;
1091				return (1);
1092			}
1093		}
1094#endif
1095	}
1096
1097	return (0);
1098}
1099
1100static int
1101ta_lookup_chash_aligned(struct table_info *ti, void *key, uint32_t keylen,
1102    uint32_t *val)
1103{
1104	struct chashbhead *head;
1105	struct chashentry *ent;
1106	uint16_t hash, hsize;
1107	uint8_t imask;
1108
1109	if (keylen == sizeof(in_addr_t)) {
1110#ifdef INET
1111		head = (struct chashbhead *)ti->state;
1112		imask = ti->data >> 24;
1113		hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1114		uint32_t a;
1115		a = ntohl(*((in_addr_t *)key));
1116		a = a >> imask;
1117		hash = hash_ip(a, hsize);
1118		SLIST_FOREACH(ent, &head[hash], next) {
1119			if (ent->a.a4 == a) {
1120				*val = ent->value;
1121				return (1);
1122			}
1123		}
1124#endif
1125	} else {
1126#ifdef INET6
1127		/* IPv6: aligned to 8bit mask */
1128		struct in6_addr addr6;
1129		uint64_t *paddr, *ptmp;
1130		head = (struct chashbhead *)ti->xstate;
1131		imask = (ti->data & 0xFF0000) >> 16;
1132		hsize = 1 << (ti->data & 0xFF);
1133
1134		hash = hash_ip6_al(&addr6, key, imask, hsize);
1135		paddr = (uint64_t *)&addr6;
1136		SLIST_FOREACH(ent, &head[hash], next) {
1137			ptmp = (uint64_t *)&ent->a.a6;
1138			if (paddr[0] == ptmp[0] && paddr[1] == ptmp[1]) {
1139				*val = ent->value;
1140				return (1);
1141			}
1142		}
1143#endif
1144	}
1145
1146	return (0);
1147}
1148
1149static int
1150ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
1151    uint32_t *val)
1152{
1153	struct chashbhead *head;
1154	struct chashentry *ent;
1155	uint16_t hash, hsize;
1156	uint8_t imask;
1157
1158	if (keylen == sizeof(in_addr_t)) {
1159#ifdef INET
1160		head = (struct chashbhead *)ti->state;
1161		imask = ti->data >> 24;
1162		hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1163		uint32_t a;
1164		a = ntohl(*((in_addr_t *)key));
1165		a = a >> imask;
1166		hash = hash_ip(a, hsize);
1167		SLIST_FOREACH(ent, &head[hash], next) {
1168			if (ent->a.a4 == a) {
1169				*val = ent->value;
1170				return (1);
1171			}
1172		}
1173#endif
1174	} else {
1175#ifdef INET6
1176		/* IPv6: /64 */
1177		uint64_t a6, *paddr;
1178		head = (struct chashbhead *)ti->xstate;
1179		paddr = (uint64_t *)key;
1180		hsize = 1 << (ti->data & 0xFF);
1181		a6 = *paddr;
1182		hash = hash_ip64((struct in6_addr *)key, hsize);
1183		SLIST_FOREACH(ent, &head[hash], next) {
1184			paddr = (uint64_t *)&ent->a.a6;
1185			if (a6 == *paddr) {
1186				*val = ent->value;
1187				return (1);
1188			}
1189		}
1190#endif
1191	}
1192
1193	return (0);
1194}
1195
1196static int
1197chash_parse_opts(struct chash_cfg *cfg, char *data)
1198{
1199	char *pdel, *pend, *s;
1200	int mask4, mask6;
1201
1202	mask4 = cfg->mask4;
1203	mask6 = cfg->mask6;
1204
1205	if (data == NULL)
1206		return (0);
1207	if ((pdel = strchr(data, ' ')) == NULL)
1208		return (0);
1209	while (*pdel == ' ')
1210		pdel++;
1211	if (strncmp(pdel, "masks=", 6) != 0)
1212		return (EINVAL);
1213	if ((s = strchr(pdel, ' ')) != NULL)
1214		*s++ = '\0';
1215
1216	pdel += 6;
1217	/* Need /XX[,/YY] */
1218	if (*pdel++ != '/')
1219		return (EINVAL);
1220	mask4 = strtol(pdel, &pend, 10);
1221	if (*pend == ',') {
1222		/* ,/YY */
1223		pdel = pend + 1;
1224		if (*pdel++ != '/')
1225			return (EINVAL);
1226		mask6 = strtol(pdel, &pend, 10);
1227		if (*pend != '\0')
1228			return (EINVAL);
1229	} else if (*pend != '\0')
1230		return (EINVAL);
1231
1232	if (mask4 < 0 || mask4 > 32 || mask6 < 0 || mask6 > 128)
1233		return (EINVAL);
1234
1235	cfg->mask4 = mask4;
1236	cfg->mask6 = mask6;
1237
1238	return (0);
1239}
1240
1241static void
1242ta_print_chash_config(void *ta_state, struct table_info *ti, char *buf,
1243    size_t bufsize)
1244{
1245	struct chash_cfg *cfg;
1246
1247	cfg = (struct chash_cfg *)ta_state;
1248
1249	if (cfg->mask4 != 32 || cfg->mask6 != 128)
1250		snprintf(buf, bufsize, "%s masks=/%d,/%d", "addr:hash",
1251		    cfg->mask4, cfg->mask6);
1252	else
1253		snprintf(buf, bufsize, "%s", "addr:hash");
1254}
1255
1256static int
1257ta_log2(uint32_t v)
1258{
1259	uint32_t r;
1260
1261	r = 0;
1262	while (v >>= 1)
1263		r++;
1264
1265	return (r);
1266}
1267
1268/*
1269 * New table.
1270 * We assume 'data' to be either NULL or the following format:
1271 * 'addr:hash [masks=/32[,/128]]'
1272 */
1273static int
1274ta_init_chash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
1275    char *data, uint8_t tflags)
1276{
1277	int error, i;
1278	uint32_t hsize;
1279	struct chash_cfg *cfg;
1280
1281	cfg = malloc(sizeof(struct chash_cfg), M_IPFW, M_WAITOK | M_ZERO);
1282
1283	cfg->mask4 = 32;
1284	cfg->mask6 = 128;
1285
1286	if ((error = chash_parse_opts(cfg, data)) != 0) {
1287		free(cfg, M_IPFW);
1288		return (error);
1289	}
1290
1291	cfg->size4 = 128;
1292	cfg->size6 = 128;
1293
1294	cfg->head4 = malloc(sizeof(struct chashbhead) * cfg->size4, M_IPFW,
1295	    M_WAITOK | M_ZERO);
1296	cfg->head6 = malloc(sizeof(struct chashbhead) * cfg->size6, M_IPFW,
1297	    M_WAITOK | M_ZERO);
1298	for (i = 0; i < cfg->size4; i++)
1299		SLIST_INIT(&cfg->head4[i]);
1300	for (i = 0; i < cfg->size6; i++)
1301		SLIST_INIT(&cfg->head6[i]);
1302
1303
1304	*ta_state = cfg;
1305	ti->state = cfg->head4;
1306	ti->xstate = cfg->head6;
1307
1308	/* Store data depending on v6 mask length */
1309	hsize = ta_log2(cfg->size4) << 8 | ta_log2(cfg->size6);
1310	if (cfg->mask6 == 64) {
1311		ti->data = (32 - cfg->mask4) << 24 | (128 - cfg->mask6) << 16|
1312		    hsize;
1313		ti->lookup = ta_lookup_chash_64;
1314	} else if ((cfg->mask6  % 8) == 0) {
1315		ti->data = (32 - cfg->mask4) << 24 |
1316		    cfg->mask6 << 13 | hsize;
1317		ti->lookup = ta_lookup_chash_aligned;
1318	} else {
1319		/* don't do that! */
1320		ti->data = (32 - cfg->mask4) << 24 |
1321		    cfg->mask6 << 16 | hsize;
1322		ti->lookup = ta_lookup_chash_slow;
1323	}
1324
1325	return (0);
1326}
1327
1328static void
1329ta_destroy_chash(void *ta_state, struct table_info *ti)
1330{
1331	struct chash_cfg *cfg;
1332	struct chashentry *ent, *ent_next;
1333	int i;
1334
1335	cfg = (struct chash_cfg *)ta_state;
1336
1337	for (i = 0; i < cfg->size4; i++)
1338		SLIST_FOREACH_SAFE(ent, &cfg->head4[i], next, ent_next)
1339			free(ent, M_IPFW_TBL);
1340
1341	for (i = 0; i < cfg->size6; i++)
1342		SLIST_FOREACH_SAFE(ent, &cfg->head6[i], next, ent_next)
1343			free(ent, M_IPFW_TBL);
1344
1345	free(cfg->head4, M_IPFW);
1346	free(cfg->head6, M_IPFW);
1347
1348	free(cfg, M_IPFW);
1349}
1350
1351static void
1352ta_dump_chash_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
1353{
1354	struct chash_cfg *cfg;
1355
1356	cfg = (struct chash_cfg *)ta_state;
1357
1358	tinfo->flags = IPFW_TATFLAGS_AFDATA | IPFW_TATFLAGS_AFITEM;
1359	tinfo->taclass4 = IPFW_TACLASS_HASH;
1360	tinfo->size4 = cfg->size4;
1361	tinfo->count4 = cfg->items4;
1362	tinfo->itemsize4 = sizeof(struct chashentry);
1363	tinfo->taclass6 = IPFW_TACLASS_HASH;
1364	tinfo->size6 = cfg->size6;
1365	tinfo->count6 = cfg->items6;
1366	tinfo->itemsize6 = sizeof(struct chashentry);
1367}
1368
1369static int
1370ta_dump_chash_tentry(void *ta_state, struct table_info *ti, void *e,
1371    ipfw_obj_tentry *tent)
1372{
1373	struct chash_cfg *cfg;
1374	struct chashentry *ent;
1375
1376	cfg = (struct chash_cfg *)ta_state;
1377	ent = (struct chashentry *)e;
1378
1379	if (ent->type == AF_INET) {
1380		tent->k.addr.s_addr = htonl(ent->a.a4 << (32 - cfg->mask4));
1381		tent->masklen = cfg->mask4;
1382		tent->subtype = AF_INET;
1383		tent->v.kidx = ent->value;
1384#ifdef INET6
1385	} else {
1386		memcpy(&tent->k.addr6, &ent->a.a6, sizeof(struct in6_addr));
1387		tent->masklen = cfg->mask6;
1388		tent->subtype = AF_INET6;
1389		tent->v.kidx = ent->value;
1390#endif
1391	}
1392
1393	return (0);
1394}
1395
1396static uint32_t
1397hash_ent(struct chashentry *ent, int af, int mlen, uint32_t size)
1398{
1399	uint32_t hash;
1400
1401	hash = 0;
1402
1403	if (af == AF_INET) {
1404#ifdef INET
1405		hash = hash_ip(ent->a.a4, size);
1406#endif
1407	} else {
1408#ifdef INET6
1409		if (mlen == 64)
1410			hash = hash_ip64(&ent->a.a6, size);
1411		else
1412			hash = hash_ip6(&ent->a.a6, size);
1413#endif
1414	}
1415
1416	return (hash);
1417}
1418
1419static int
1420tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent)
1421{
1422	int mlen;
1423#ifdef INET6
1424	struct in6_addr mask6;
1425#endif
1426
1427
1428	mlen = tei->masklen;
1429
1430	if (tei->subtype == AF_INET) {
1431#ifdef INET
1432		if (mlen > 32)
1433			return (EINVAL);
1434		ent->type = AF_INET;
1435
1436		/* Calculate masked address */
1437		ent->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1438#endif
1439#ifdef INET6
1440	} else if (tei->subtype == AF_INET6) {
1441		/* IPv6 case */
1442		if (mlen > 128)
1443			return (EINVAL);
1444		ent->type = AF_INET6;
1445
1446		ipv6_writemask(&mask6, mlen);
1447		memcpy(&ent->a.a6, tei->paddr, sizeof(struct in6_addr));
1448		APPLY_MASK(&ent->a.a6, &mask6);
1449#endif
1450	} else {
1451		/* Unknown CIDR type */
1452		return (EINVAL);
1453	}
1454
1455	return (0);
1456}
1457
1458static int
1459ta_find_chash_tentry(void *ta_state, struct table_info *ti,
1460    ipfw_obj_tentry *tent)
1461{
1462	struct chash_cfg *cfg;
1463	struct chashbhead *head;
1464	struct chashentry ent, *tmp;
1465	struct tentry_info tei;
1466	int error;
1467	uint32_t hash;
1468
1469	cfg = (struct chash_cfg *)ta_state;
1470
1471	memset(&ent, 0, sizeof(ent));
1472	memset(&tei, 0, sizeof(tei));
1473
1474	if (tent->subtype == AF_INET) {
1475		tei.paddr = &tent->k.addr;
1476		tei.masklen = cfg->mask4;
1477		tei.subtype = AF_INET;
1478
1479		if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
1480			return (error);
1481
1482		head = cfg->head4;
1483		hash = hash_ent(&ent, AF_INET, cfg->mask4, cfg->size4);
1484		/* Check for existence */
1485		SLIST_FOREACH(tmp, &head[hash], next) {
1486			if (tmp->a.a4 != ent.a.a4)
1487				continue;
1488
1489			ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1490			return (0);
1491		}
1492	} else {
1493		tei.paddr = &tent->k.addr6;
1494		tei.masklen = cfg->mask6;
1495		tei.subtype = AF_INET6;
1496
1497		if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
1498			return (error);
1499
1500		head = cfg->head6;
1501		hash = hash_ent(&ent, AF_INET6, cfg->mask6, cfg->size6);
1502		/* Check for existence */
1503		SLIST_FOREACH(tmp, &head[hash], next) {
1504			if (memcmp(&tmp->a.a6, &ent.a.a6, 16) != 0)
1505				continue;
1506			ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1507			return (0);
1508		}
1509	}
1510
1511	return (ENOENT);
1512}
1513
1514static void
1515ta_foreach_chash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
1516    void *arg)
1517{
1518	struct chash_cfg *cfg;
1519	struct chashentry *ent, *ent_next;
1520	int i;
1521
1522	cfg = (struct chash_cfg *)ta_state;
1523
1524	for (i = 0; i < cfg->size4; i++)
1525		SLIST_FOREACH_SAFE(ent, &cfg->head4[i], next, ent_next)
1526			f(ent, arg);
1527
1528	for (i = 0; i < cfg->size6; i++)
1529		SLIST_FOREACH_SAFE(ent, &cfg->head6[i], next, ent_next)
1530			f(ent, arg);
1531}
1532
1533static int
1534ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1535    void *ta_buf)
1536{
1537	struct ta_buf_chash *tb;
1538	struct chashentry *ent;
1539	int error;
1540
1541	tb = (struct ta_buf_chash *)ta_buf;
1542
1543	ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1544
1545	error = tei_to_chash_ent(tei, ent);
1546	if (error != 0) {
1547		free(ent, M_IPFW_TBL);
1548		return (error);
1549	}
1550	tb->ent_ptr = ent;
1551
1552	return (0);
1553}
1554
1555static int
1556ta_add_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1557    void *ta_buf, uint32_t *pnum)
1558{
1559	struct chash_cfg *cfg;
1560	struct chashbhead *head;
1561	struct chashentry *ent, *tmp;
1562	struct ta_buf_chash *tb;
1563	int exists;
1564	uint32_t hash, value;
1565
1566	cfg = (struct chash_cfg *)ta_state;
1567	tb = (struct ta_buf_chash *)ta_buf;
1568	ent = (struct chashentry *)tb->ent_ptr;
1569	hash = 0;
1570	exists = 0;
1571
1572	/* Read current value from @tei */
1573	ent->value = tei->value;
1574
1575	/* Read cuurrent value */
1576	if (tei->subtype == AF_INET) {
1577		if (tei->masklen != cfg->mask4)
1578			return (EINVAL);
1579		head = cfg->head4;
1580		hash = hash_ent(ent, AF_INET, cfg->mask4, cfg->size4);
1581
1582		/* Check for existence */
1583		SLIST_FOREACH(tmp, &head[hash], next) {
1584			if (tmp->a.a4 == ent->a.a4) {
1585				exists = 1;
1586				break;
1587			}
1588		}
1589	} else {
1590		if (tei->masklen != cfg->mask6)
1591			return (EINVAL);
1592		head = cfg->head6;
1593		hash = hash_ent(ent, AF_INET6, cfg->mask6, cfg->size6);
1594		/* Check for existence */
1595		SLIST_FOREACH(tmp, &head[hash], next) {
1596			if (memcmp(&tmp->a.a6, &ent->a.a6, 16) == 0) {
1597				exists = 1;
1598				break;
1599			}
1600		}
1601	}
1602
1603	if (exists == 1) {
1604		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1605			return (EEXIST);
1606		/* Record already exists. Update value if we're asked to */
1607		value = tmp->value;
1608		tmp->value = tei->value;
1609		tei->value = value;
1610		/* Indicate that update has happened instead of addition */
1611		tei->flags |= TEI_FLAGS_UPDATED;
1612		*pnum = 0;
1613	} else {
1614		if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
1615			return (EFBIG);
1616		SLIST_INSERT_HEAD(&head[hash], ent, next);
1617		tb->ent_ptr = NULL;
1618		*pnum = 1;
1619
1620		/* Update counters */
1621		if (tei->subtype == AF_INET)
1622			cfg->items4++;
1623		else
1624			cfg->items6++;
1625	}
1626
1627	return (0);
1628}
1629
1630static int
1631ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1632    void *ta_buf)
1633{
1634	struct ta_buf_chash *tb;
1635
1636	tb = (struct ta_buf_chash *)ta_buf;
1637
1638	return (tei_to_chash_ent(tei, &tb->ent));
1639}
1640
1641static int
1642ta_del_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1643    void *ta_buf, uint32_t *pnum)
1644{
1645	struct chash_cfg *cfg;
1646	struct chashbhead *head;
1647	struct chashentry *tmp, *tmp_next, *ent;
1648	struct ta_buf_chash *tb;
1649	uint32_t hash;
1650
1651	cfg = (struct chash_cfg *)ta_state;
1652	tb = (struct ta_buf_chash *)ta_buf;
1653	ent = &tb->ent;
1654
1655	if (tei->subtype == AF_INET) {
1656		if (tei->masklen != cfg->mask4)
1657			return (EINVAL);
1658		head = cfg->head4;
1659		hash = hash_ent(ent, AF_INET, cfg->mask4, cfg->size4);
1660
1661		SLIST_FOREACH_SAFE(tmp, &head[hash], next, tmp_next) {
1662			if (tmp->a.a4 != ent->a.a4)
1663				continue;
1664
1665			SLIST_REMOVE(&head[hash], tmp, chashentry, next);
1666			cfg->items4--;
1667			tb->ent_ptr = tmp;
1668			tei->value = tmp->value;
1669			*pnum = 1;
1670			return (0);
1671		}
1672	} else {
1673		if (tei->masklen != cfg->mask6)
1674			return (EINVAL);
1675		head = cfg->head6;
1676		hash = hash_ent(ent, AF_INET6, cfg->mask6, cfg->size6);
1677		SLIST_FOREACH_SAFE(tmp, &head[hash], next, tmp_next) {
1678			if (memcmp(&tmp->a.a6, &ent->a.a6, 16) != 0)
1679				continue;
1680
1681			SLIST_REMOVE(&head[hash], tmp, chashentry, next);
1682			cfg->items6--;
1683			tb->ent_ptr = tmp;
1684			tei->value = tmp->value;
1685			*pnum = 1;
1686			return (0);
1687		}
1688	}
1689
1690	return (ENOENT);
1691}
1692
1693static void
1694ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1695    void *ta_buf)
1696{
1697	struct ta_buf_chash *tb;
1698
1699	tb = (struct ta_buf_chash *)ta_buf;
1700
1701	if (tb->ent_ptr != NULL)
1702		free(tb->ent_ptr, M_IPFW_TBL);
1703}
1704
1705/*
1706 * Hash growing callbacks.
1707 */
1708
1709static int
1710ta_need_modify_chash(void *ta_state, struct table_info *ti, uint32_t count,
1711    uint64_t *pflags)
1712{
1713	struct chash_cfg *cfg;
1714	uint64_t data;
1715
1716	/*
1717	 * Since we don't know exact number of IPv4/IPv6 records in @count,
1718	 * ignore non-zero @count value at all. Check current hash sizes
1719	 * and return appropriate data.
1720	 */
1721
1722	cfg = (struct chash_cfg *)ta_state;
1723
1724	data = 0;
1725	if (cfg->items4 > cfg->size4 && cfg->size4 < 65536)
1726		data |= (cfg->size4 * 2) << 16;
1727	if (cfg->items6 > cfg->size6 && cfg->size6 < 65536)
1728		data |= cfg->size6 * 2;
1729
1730	if (data != 0) {
1731		*pflags = data;
1732		return (1);
1733	}
1734
1735	return (0);
1736}
1737
1738/*
1739 * Allocate new, larger chash.
1740 */
1741static int
1742ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags)
1743{
1744	struct mod_item *mi;
1745	struct chashbhead *head;
1746	int i;
1747
1748	mi = (struct mod_item *)ta_buf;
1749
1750	memset(mi, 0, sizeof(struct mod_item));
1751	mi->size = (*pflags >> 16) & 0xFFFF;
1752	mi->size6 = *pflags & 0xFFFF;
1753	if (mi->size > 0) {
1754		head = malloc(sizeof(struct chashbhead) * mi->size,
1755		    M_IPFW, M_WAITOK | M_ZERO);
1756		for (i = 0; i < mi->size; i++)
1757			SLIST_INIT(&head[i]);
1758		mi->main_ptr = head;
1759	}
1760
1761	if (mi->size6 > 0) {
1762		head = malloc(sizeof(struct chashbhead) * mi->size6,
1763		    M_IPFW, M_WAITOK | M_ZERO);
1764		for (i = 0; i < mi->size6; i++)
1765			SLIST_INIT(&head[i]);
1766		mi->main_ptr6 = head;
1767	}
1768
1769	return (0);
1770}
1771
1772/*
1773 * Copy data from old runtime array to new one.
1774 */
1775static int
1776ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1777    uint64_t *pflags)
1778{
1779
1780	/* In is not possible to do rehash if we're not holidng WLOCK. */
1781	return (0);
1782}
1783
1784/*
1785 * Switch old & new arrays.
1786 */
1787static void
1788ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1789    uint64_t pflags)
1790{
1791	struct mod_item *mi;
1792	struct chash_cfg *cfg;
1793	struct chashbhead *old_head, *new_head;
1794	struct chashentry *ent, *ent_next;
1795	int af, i, mlen;
1796	uint32_t nhash;
1797	size_t old_size, new_size;
1798
1799	mi = (struct mod_item *)ta_buf;
1800	cfg = (struct chash_cfg *)ta_state;
1801
1802	/* Check which hash we need to grow and do we still need that */
1803	if (mi->size > 0 && cfg->size4 < mi->size) {
1804		new_head = (struct chashbhead *)mi->main_ptr;
1805		new_size = mi->size;
1806		old_size = cfg->size4;
1807		old_head = ti->state;
1808		mlen = cfg->mask4;
1809		af = AF_INET;
1810
1811		for (i = 0; i < old_size; i++) {
1812			SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
1813				nhash = hash_ent(ent, af, mlen, new_size);
1814				SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
1815			}
1816		}
1817
1818		ti->state = new_head;
1819		cfg->head4 = new_head;
1820		cfg->size4 = mi->size;
1821		mi->main_ptr = old_head;
1822	}
1823
1824	if (mi->size6 > 0 && cfg->size6 < mi->size6) {
1825		new_head = (struct chashbhead *)mi->main_ptr6;
1826		new_size = mi->size6;
1827		old_size = cfg->size6;
1828		old_head = ti->xstate;
1829		mlen = cfg->mask6;
1830		af = AF_INET6;
1831
1832		for (i = 0; i < old_size; i++) {
1833			SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
1834				nhash = hash_ent(ent, af, mlen, new_size);
1835				SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
1836			}
1837		}
1838
1839		ti->xstate = new_head;
1840		cfg->head6 = new_head;
1841		cfg->size6 = mi->size6;
1842		mi->main_ptr6 = old_head;
1843	}
1844
1845	/* Update lower 32 bits with new values */
1846	ti->data &= 0xFFFFFFFF00000000;
1847	ti->data |= ta_log2(cfg->size4) << 8 | ta_log2(cfg->size6);
1848}
1849
1850/*
1851 * Free unneded array.
1852 */
1853static void
1854ta_flush_mod_chash(void *ta_buf)
1855{
1856	struct mod_item *mi;
1857
1858	mi = (struct mod_item *)ta_buf;
1859	if (mi->main_ptr != NULL)
1860		free(mi->main_ptr, M_IPFW);
1861	if (mi->main_ptr6 != NULL)
1862		free(mi->main_ptr6, M_IPFW);
1863}
1864
1865struct table_algo addr_hash = {
1866	.name		= "addr:hash",
1867	.type		= IPFW_TABLE_ADDR,
1868	.ta_buf_size	= sizeof(struct ta_buf_chash),
1869	.init		= ta_init_chash,
1870	.destroy	= ta_destroy_chash,
1871	.prepare_add	= ta_prepare_add_chash,
1872	.prepare_del	= ta_prepare_del_chash,
1873	.add		= ta_add_chash,
1874	.del		= ta_del_chash,
1875	.flush_entry	= ta_flush_chash_entry,
1876	.foreach	= ta_foreach_chash,
1877	.dump_tentry	= ta_dump_chash_tentry,
1878	.find_tentry	= ta_find_chash_tentry,
1879	.print_config	= ta_print_chash_config,
1880	.dump_tinfo	= ta_dump_chash_tinfo,
1881	.need_modify	= ta_need_modify_chash,
1882	.prepare_mod	= ta_prepare_mod_chash,
1883	.fill_mod	= ta_fill_mod_chash,
1884	.modify		= ta_modify_chash,
1885	.flush_mod	= ta_flush_mod_chash,
1886};
1887
1888
1889/*
1890 * Iface table cmds.
1891 *
1892 * Implementation:
1893 *
1894 * Runtime part:
1895 * - sorted array of "struct ifidx" pointed by ti->state.
1896 *   Array is allocated with rounding up to IFIDX_CHUNK. Only existing
1897 *   interfaces are stored in array, however its allocated size is
1898 *   sufficient to hold all table records if needed.
1899 * - current array size is stored in ti->data
1900 *
1901 * Table data:
1902 * - "struct iftable_cfg" is allocated to store table state (ta_state).
1903 * - All table records are stored inside namedobj instance.
1904 *
1905 */
1906
1907struct ifidx {
1908	uint16_t	kidx;
1909	uint16_t	spare;
1910	uint32_t	value;
1911};
1912#define	DEFAULT_IFIDX_SIZE	64
1913
1914struct iftable_cfg;
1915
1916struct ifentry {
1917	struct named_object	no;
1918	struct ipfw_ifc		ic;
1919	struct iftable_cfg	*icfg;
1920	uint32_t		value;
1921	int			linked;
1922};
1923
1924struct iftable_cfg {
1925	struct namedobj_instance	*ii;
1926	struct ip_fw_chain	*ch;
1927	struct table_info	*ti;
1928	void	*main_ptr;
1929	size_t	size;	/* Number of items allocated in array */
1930	size_t	count;	/* Number of all items */
1931	size_t	used;	/* Number of items _active_ now */
1932};
1933
1934struct ta_buf_ifidx
1935{
1936	struct ifentry *ife;
1937	uint32_t value;
1938};
1939
1940int compare_ifidx(const void *k, const void *v);
1941static struct ifidx * ifidx_find(struct table_info *ti, void *key);
1942static int ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
1943    uint32_t *val);
1944static int ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state,
1945    struct table_info *ti, char *data, uint8_t tflags);
1946static void ta_change_ti_ifidx(void *ta_state, struct table_info *ti);
1947static int destroy_ifidx_locked(struct namedobj_instance *ii,
1948    struct named_object *no, void *arg);
1949static void ta_destroy_ifidx(void *ta_state, struct table_info *ti);
1950static void ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti,
1951    ipfw_ta_tinfo *tinfo);
1952static int ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1953    void *ta_buf);
1954static int ta_add_ifidx(void *ta_state, struct table_info *ti,
1955    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1956static int ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1957    void *ta_buf);
1958static int ta_del_ifidx(void *ta_state, struct table_info *ti,
1959    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1960static void ta_flush_ifidx_entry(struct ip_fw_chain *ch,
1961    struct tentry_info *tei, void *ta_buf);
1962static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
1963static int ta_need_modify_ifidx(void *ta_state, struct table_info *ti,
1964    uint32_t count, uint64_t *pflags);
1965static int ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags);
1966static int ta_fill_mod_ifidx(void *ta_state, struct table_info *ti,
1967    void *ta_buf, uint64_t *pflags);
1968static void ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1969    uint64_t pflags);
1970static void ta_flush_mod_ifidx(void *ta_buf);
1971static int ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
1972    ipfw_obj_tentry *tent);
1973static int ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
1974    ipfw_obj_tentry *tent);
1975static int foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
1976    void *arg);
1977static void ta_foreach_ifidx(void *ta_state, struct table_info *ti,
1978    ta_foreach_f *f, void *arg);
1979
1980int
1981compare_ifidx(const void *k, const void *v)
1982{
1983	const struct ifidx *ifidx;
1984	uint16_t key;
1985
1986	key = *((const uint16_t *)k);
1987	ifidx = (const struct ifidx *)v;
1988
1989	if (key < ifidx->kidx)
1990		return (-1);
1991	else if (key > ifidx->kidx)
1992		return (1);
1993
1994	return (0);
1995}
1996
1997/*
1998 * Adds item @item with key @key into ascending-sorted array @base.
1999 * Assumes @base has enough additional storage.
2000 *
2001 * Returns 1 on success, 0 on duplicate key.
2002 */
2003static int
2004badd(const void *key, void *item, void *base, size_t nmemb,
2005    size_t size, int (*compar) (const void *, const void *))
2006{
2007	int min, max, mid, shift, res;
2008	caddr_t paddr;
2009
2010	if (nmemb == 0) {
2011		memcpy(base, item, size);
2012		return (1);
2013	}
2014
2015	/* Binary search */
2016	min = 0;
2017	max = nmemb - 1;
2018	mid = 0;
2019	while (min <= max) {
2020		mid = (min + max) / 2;
2021		res = compar(key, (const void *)((caddr_t)base + mid * size));
2022		if (res == 0)
2023			return (0);
2024
2025		if (res > 0)
2026			min = mid + 1;
2027		else
2028			max = mid - 1;
2029	}
2030
2031	/* Item not found. */
2032	res = compar(key, (const void *)((caddr_t)base + mid * size));
2033	if (res > 0)
2034		shift = mid + 1;
2035	else
2036		shift = mid;
2037
2038	paddr = (caddr_t)base + shift * size;
2039	if (nmemb > shift)
2040		memmove(paddr + size, paddr, (nmemb - shift) * size);
2041
2042	memcpy(paddr, item, size);
2043
2044	return (1);
2045}
2046
2047/*
2048 * Deletes item with key @key from ascending-sorted array @base.
2049 *
2050 * Returns 1 on success, 0 for non-existent key.
2051 */
2052static int
2053bdel(const void *key, void *base, size_t nmemb, size_t size,
2054    int (*compar) (const void *, const void *))
2055{
2056	caddr_t item;
2057	size_t sz;
2058
2059	item = (caddr_t)bsearch(key, base, nmemb, size, compar);
2060
2061	if (item == NULL)
2062		return (0);
2063
2064	sz = (caddr_t)base + nmemb * size - item;
2065
2066	if (sz > 0)
2067		memmove(item, item + size, sz);
2068
2069	return (1);
2070}
2071
2072static struct ifidx *
2073ifidx_find(struct table_info *ti, void *key)
2074{
2075	struct ifidx *ifi;
2076
2077	ifi = bsearch(key, ti->state, ti->data, sizeof(struct ifidx),
2078	    compare_ifidx);
2079
2080	return (ifi);
2081}
2082
2083static int
2084ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
2085    uint32_t *val)
2086{
2087	struct ifidx *ifi;
2088
2089	ifi = ifidx_find(ti, key);
2090
2091	if (ifi != NULL) {
2092		*val = ifi->value;
2093		return (1);
2094	}
2095
2096	return (0);
2097}
2098
2099static int
2100ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2101    char *data, uint8_t tflags)
2102{
2103	struct iftable_cfg *icfg;
2104
2105	icfg = malloc(sizeof(struct iftable_cfg), M_IPFW, M_WAITOK | M_ZERO);
2106
2107	icfg->ii = ipfw_objhash_create(DEFAULT_IFIDX_SIZE);
2108	icfg->size = DEFAULT_IFIDX_SIZE;
2109	icfg->main_ptr = malloc(sizeof(struct ifidx) * icfg->size, M_IPFW,
2110	    M_WAITOK | M_ZERO);
2111	icfg->ch = ch;
2112
2113	*ta_state = icfg;
2114	ti->state = icfg->main_ptr;
2115	ti->lookup = ta_lookup_ifidx;
2116
2117	return (0);
2118}
2119
2120/*
2121 * Handle tableinfo @ti pointer change (on table array resize).
2122 */
2123static void
2124ta_change_ti_ifidx(void *ta_state, struct table_info *ti)
2125{
2126	struct iftable_cfg *icfg;
2127
2128	icfg = (struct iftable_cfg *)ta_state;
2129	icfg->ti = ti;
2130}
2131
2132static int
2133destroy_ifidx_locked(struct namedobj_instance *ii, struct named_object *no,
2134    void *arg)
2135{
2136	struct ifentry *ife;
2137	struct ip_fw_chain *ch;
2138
2139	ch = (struct ip_fw_chain *)arg;
2140	ife = (struct ifentry *)no;
2141
2142	ipfw_iface_del_notify(ch, &ife->ic);
2143	ipfw_iface_unref(ch, &ife->ic);
2144	free(ife, M_IPFW_TBL);
2145	return (0);
2146}
2147
2148
2149/*
2150 * Destroys table @ti
2151 */
2152static void
2153ta_destroy_ifidx(void *ta_state, struct table_info *ti)
2154{
2155	struct iftable_cfg *icfg;
2156	struct ip_fw_chain *ch;
2157
2158	icfg = (struct iftable_cfg *)ta_state;
2159	ch = icfg->ch;
2160
2161	if (icfg->main_ptr != NULL)
2162		free(icfg->main_ptr, M_IPFW);
2163
2164	IPFW_UH_WLOCK(ch);
2165	ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
2166	IPFW_UH_WUNLOCK(ch);
2167
2168	ipfw_objhash_destroy(icfg->ii);
2169
2170	free(icfg, M_IPFW);
2171}
2172
2173/*
2174 * Provide algo-specific table info
2175 */
2176static void
2177ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2178{
2179	struct iftable_cfg *cfg;
2180
2181	cfg = (struct iftable_cfg *)ta_state;
2182
2183	tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2184	tinfo->size4 = cfg->size;
2185	tinfo->count4 = cfg->used;
2186	tinfo->itemsize4 = sizeof(struct ifidx);
2187}
2188
2189/*
2190 * Prepare state to add to the table:
2191 * allocate ifentry and reference needed interface.
2192 */
2193static int
2194ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2195    void *ta_buf)
2196{
2197	struct ta_buf_ifidx *tb;
2198	char *ifname;
2199	struct ifentry *ife;
2200
2201	tb = (struct ta_buf_ifidx *)ta_buf;
2202
2203	/* Check if string is terminated */
2204	ifname = (char *)tei->paddr;
2205	if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2206		return (EINVAL);
2207
2208	ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
2209	ife->ic.cb = if_notifier;
2210	ife->ic.cbdata = ife;
2211
2212	if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0) {
2213		free(ife, M_IPFW_TBL);
2214		return (EINVAL);
2215	}
2216
2217	/* Use ipfw_iface 'ifname' field as stable storage */
2218	ife->no.name = ife->ic.iface->ifname;
2219
2220	tb->ife = ife;
2221
2222	return (0);
2223}
2224
2225static int
2226ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2227    void *ta_buf, uint32_t *pnum)
2228{
2229	struct iftable_cfg *icfg;
2230	struct ifentry *ife, *tmp;
2231	struct ta_buf_ifidx *tb;
2232	struct ipfw_iface *iif;
2233	struct ifidx *ifi;
2234	char *ifname;
2235	uint32_t value;
2236
2237	tb = (struct ta_buf_ifidx *)ta_buf;
2238	ifname = (char *)tei->paddr;
2239	icfg = (struct iftable_cfg *)ta_state;
2240	ife = tb->ife;
2241
2242	ife->icfg = icfg;
2243	ife->value = tei->value;
2244
2245	tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2246
2247	if (tmp != NULL) {
2248		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2249			return (EEXIST);
2250
2251		/* Exchange values in @tmp and @tei */
2252		value = tmp->value;
2253		tmp->value = tei->value;
2254		tei->value = value;
2255
2256		iif = tmp->ic.iface;
2257		if (iif->resolved != 0) {
2258			/* We have to update runtime value, too */
2259			ifi = ifidx_find(ti, &iif->ifindex);
2260			ifi->value = ife->value;
2261		}
2262
2263		/* Indicate that update has happened instead of addition */
2264		tei->flags |= TEI_FLAGS_UPDATED;
2265		*pnum = 0;
2266		return (0);
2267	}
2268
2269	if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2270		return (EFBIG);
2271
2272	/* Link to internal list */
2273	ipfw_objhash_add(icfg->ii, &ife->no);
2274
2275	/* Link notifier (possible running its callback) */
2276	ipfw_iface_add_notify(icfg->ch, &ife->ic);
2277	icfg->count++;
2278
2279	tb->ife = NULL;
2280	*pnum = 1;
2281
2282	return (0);
2283}
2284
2285/*
2286 * Prepare to delete key from table.
2287 * Do basic interface name checks.
2288 */
2289static int
2290ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2291    void *ta_buf)
2292{
2293	struct ta_buf_ifidx *tb;
2294	char *ifname;
2295
2296	tb = (struct ta_buf_ifidx *)ta_buf;
2297
2298	/* Check if string is terminated */
2299	ifname = (char *)tei->paddr;
2300	if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2301		return (EINVAL);
2302
2303	return (0);
2304}
2305
2306/*
2307 * Remove key from both configuration list and
2308 * runtime array. Removed interface notification.
2309 */
2310static int
2311ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2312    void *ta_buf, uint32_t *pnum)
2313{
2314	struct iftable_cfg *icfg;
2315	struct ifentry *ife;
2316	struct ta_buf_ifidx *tb;
2317	char *ifname;
2318	uint16_t ifindex;
2319	int res;
2320
2321	tb = (struct ta_buf_ifidx *)ta_buf;
2322	ifname = (char *)tei->paddr;
2323	icfg = (struct iftable_cfg *)ta_state;
2324
2325	ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2326
2327	if (ife == NULL)
2328		return (ENOENT);
2329
2330	if (ife->linked != 0) {
2331		/* We have to remove item from runtime */
2332		ifindex = ife->ic.iface->ifindex;
2333
2334		res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2335		    sizeof(struct ifidx), compare_ifidx);
2336
2337		KASSERT(res == 1, ("index %d does not exist", ifindex));
2338		icfg->used--;
2339		ti->data = icfg->used;
2340		ife->linked = 0;
2341	}
2342
2343	/* Unlink from local list */
2344	ipfw_objhash_del(icfg->ii, &ife->no);
2345	/* Unlink notifier and deref */
2346	ipfw_iface_del_notify(icfg->ch, &ife->ic);
2347	ipfw_iface_unref(icfg->ch, &ife->ic);
2348
2349	icfg->count--;
2350	tei->value = ife->value;
2351
2352	tb->ife = ife;
2353	*pnum = 1;
2354
2355	return (0);
2356}
2357
2358/*
2359 * Flush deleted entry.
2360 * Drops interface reference and frees entry.
2361 */
2362static void
2363ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2364    void *ta_buf)
2365{
2366	struct ta_buf_ifidx *tb;
2367
2368	tb = (struct ta_buf_ifidx *)ta_buf;
2369
2370	if (tb->ife != NULL)
2371		free(tb->ife, M_IPFW_TBL);
2372}
2373
2374
2375/*
2376 * Handle interface announce/withdrawal for particular table.
2377 * Every real runtime array modification happens here.
2378 */
2379static void
2380if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
2381{
2382	struct ifentry *ife;
2383	struct ifidx ifi;
2384	struct iftable_cfg *icfg;
2385	struct table_info *ti;
2386	int res;
2387
2388	ife = (struct ifentry *)cbdata;
2389	icfg = ife->icfg;
2390	ti = icfg->ti;
2391
2392	KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
2393
2394	if (ife->linked == 0 && ifindex != 0) {
2395		/* Interface announce */
2396		ifi.kidx = ifindex;
2397		ifi.spare = 0;
2398		ifi.value = ife->value;
2399		res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used,
2400		    sizeof(struct ifidx), compare_ifidx);
2401		KASSERT(res == 1, ("index %d already exists", ifindex));
2402		icfg->used++;
2403		ti->data = icfg->used;
2404		ife->linked = 1;
2405	} else if (ife->linked != 0 && ifindex == 0) {
2406		/* Interface withdrawal */
2407		ifindex = ife->ic.iface->ifindex;
2408
2409		res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2410		    sizeof(struct ifidx), compare_ifidx);
2411
2412		KASSERT(res == 1, ("index %d does not exist", ifindex));
2413		icfg->used--;
2414		ti->data = icfg->used;
2415		ife->linked = 0;
2416	}
2417}
2418
2419
2420/*
2421 * Table growing callbacks.
2422 */
2423
2424static int
2425ta_need_modify_ifidx(void *ta_state, struct table_info *ti, uint32_t count,
2426    uint64_t *pflags)
2427{
2428	struct iftable_cfg *cfg;
2429	uint32_t size;
2430
2431	cfg = (struct iftable_cfg *)ta_state;
2432
2433	size = cfg->size;
2434	while (size < cfg->count + count)
2435		size *= 2;
2436
2437	if (size != cfg->size) {
2438		*pflags = size;
2439		return (1);
2440	}
2441
2442	return (0);
2443}
2444
2445/*
2446 * Allocate ned, larger runtime ifidx array.
2447 */
2448static int
2449ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
2450{
2451	struct mod_item *mi;
2452
2453	mi = (struct mod_item *)ta_buf;
2454
2455	memset(mi, 0, sizeof(struct mod_item));
2456	mi->size = *pflags;
2457	mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
2458	    M_WAITOK | M_ZERO);
2459
2460	return (0);
2461}
2462
2463/*
2464 * Copy data from old runtime array to new one.
2465 */
2466static int
2467ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2468    uint64_t *pflags)
2469{
2470	struct mod_item *mi;
2471	struct iftable_cfg *icfg;
2472
2473	mi = (struct mod_item *)ta_buf;
2474	icfg = (struct iftable_cfg *)ta_state;
2475
2476	/* Check if we still need to grow array */
2477	if (icfg->size >= mi->size) {
2478		*pflags = 0;
2479		return (0);
2480	}
2481
2482	memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
2483
2484	return (0);
2485}
2486
2487/*
2488 * Switch old & new arrays.
2489 */
2490static void
2491ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2492    uint64_t pflags)
2493{
2494	struct mod_item *mi;
2495	struct iftable_cfg *icfg;
2496	void *old_ptr;
2497
2498	mi = (struct mod_item *)ta_buf;
2499	icfg = (struct iftable_cfg *)ta_state;
2500
2501	old_ptr = icfg->main_ptr;
2502	icfg->main_ptr = mi->main_ptr;
2503	icfg->size = mi->size;
2504	ti->state = icfg->main_ptr;
2505
2506	mi->main_ptr = old_ptr;
2507}
2508
2509/*
2510 * Free unneded array.
2511 */
2512static void
2513ta_flush_mod_ifidx(void *ta_buf)
2514{
2515	struct mod_item *mi;
2516
2517	mi = (struct mod_item *)ta_buf;
2518	if (mi->main_ptr != NULL)
2519		free(mi->main_ptr, M_IPFW);
2520}
2521
2522static int
2523ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
2524    ipfw_obj_tentry *tent)
2525{
2526	struct ifentry *ife;
2527
2528	ife = (struct ifentry *)e;
2529
2530	tent->masklen = 8 * IF_NAMESIZE;
2531	memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
2532	tent->v.kidx = ife->value;
2533
2534	return (0);
2535}
2536
2537static int
2538ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
2539    ipfw_obj_tentry *tent)
2540{
2541	struct iftable_cfg *icfg;
2542	struct ifentry *ife;
2543	char *ifname;
2544
2545	icfg = (struct iftable_cfg *)ta_state;
2546	ifname = tent->k.iface;
2547
2548	if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2549		return (EINVAL);
2550
2551	ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2552
2553	if (ife != NULL) {
2554		ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
2555		return (0);
2556	}
2557
2558	return (ENOENT);
2559}
2560
2561struct wa_ifidx {
2562	ta_foreach_f	*f;
2563	void		*arg;
2564};
2565
2566static int
2567foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
2568    void *arg)
2569{
2570	struct ifentry *ife;
2571	struct wa_ifidx *wa;
2572
2573	ife = (struct ifentry *)no;
2574	wa = (struct wa_ifidx *)arg;
2575
2576	wa->f(ife, wa->arg);
2577	return (0);
2578}
2579
2580static void
2581ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2582    void *arg)
2583{
2584	struct iftable_cfg *icfg;
2585	struct wa_ifidx wa;
2586
2587	icfg = (struct iftable_cfg *)ta_state;
2588
2589	wa.f = f;
2590	wa.arg = arg;
2591
2592	ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
2593}
2594
2595struct table_algo iface_idx = {
2596	.name		= "iface:array",
2597	.type		= IPFW_TABLE_INTERFACE,
2598	.flags		= TA_FLAG_DEFAULT,
2599	.ta_buf_size	= sizeof(struct ta_buf_ifidx),
2600	.init		= ta_init_ifidx,
2601	.destroy	= ta_destroy_ifidx,
2602	.prepare_add	= ta_prepare_add_ifidx,
2603	.prepare_del	= ta_prepare_del_ifidx,
2604	.add		= ta_add_ifidx,
2605	.del		= ta_del_ifidx,
2606	.flush_entry	= ta_flush_ifidx_entry,
2607	.foreach	= ta_foreach_ifidx,
2608	.dump_tentry	= ta_dump_ifidx_tentry,
2609	.find_tentry	= ta_find_ifidx_tentry,
2610	.dump_tinfo	= ta_dump_ifidx_tinfo,
2611	.need_modify	= ta_need_modify_ifidx,
2612	.prepare_mod	= ta_prepare_mod_ifidx,
2613	.fill_mod	= ta_fill_mod_ifidx,
2614	.modify		= ta_modify_ifidx,
2615	.flush_mod	= ta_flush_mod_ifidx,
2616	.change_ti	= ta_change_ti_ifidx,
2617};
2618
2619/*
2620 * Number array cmds.
2621 *
2622 * Implementation:
2623 *
2624 * Runtime part:
2625 * - sorted array of "struct numarray" pointed by ti->state.
2626 *   Array is allocated with rounding up to NUMARRAY_CHUNK.
2627 * - current array size is stored in ti->data
2628 *
2629 */
2630
2631struct numarray {
2632	uint32_t	number;
2633	uint32_t	value;
2634};
2635
2636struct numarray_cfg {
2637	void	*main_ptr;
2638	size_t	size;	/* Number of items allocated in array */
2639	size_t	used;	/* Number of items _active_ now */
2640};
2641
2642struct ta_buf_numarray
2643{
2644	struct numarray na;
2645};
2646
2647int compare_numarray(const void *k, const void *v);
2648static struct numarray *numarray_find(struct table_info *ti, void *key);
2649static int ta_lookup_numarray(struct table_info *ti, void *key,
2650    uint32_t keylen, uint32_t *val);
2651static int ta_init_numarray(struct ip_fw_chain *ch, void **ta_state,
2652    struct table_info *ti, char *data, uint8_t tflags);
2653static void ta_destroy_numarray(void *ta_state, struct table_info *ti);
2654static void ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti,
2655    ipfw_ta_tinfo *tinfo);
2656static int ta_prepare_add_numarray(struct ip_fw_chain *ch,
2657    struct tentry_info *tei, void *ta_buf);
2658static int ta_add_numarray(void *ta_state, struct table_info *ti,
2659    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2660static int ta_del_numarray(void *ta_state, struct table_info *ti,
2661    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2662static void ta_flush_numarray_entry(struct ip_fw_chain *ch,
2663    struct tentry_info *tei, void *ta_buf);
2664static int ta_need_modify_numarray(void *ta_state, struct table_info *ti,
2665    uint32_t count, uint64_t *pflags);
2666static int ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags);
2667static int ta_fill_mod_numarray(void *ta_state, struct table_info *ti,
2668    void *ta_buf, uint64_t *pflags);
2669static void ta_modify_numarray(void *ta_state, struct table_info *ti,
2670    void *ta_buf, uint64_t pflags);
2671static void ta_flush_mod_numarray(void *ta_buf);
2672static int ta_dump_numarray_tentry(void *ta_state, struct table_info *ti,
2673    void *e, ipfw_obj_tentry *tent);
2674static int ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2675    ipfw_obj_tentry *tent);
2676static void ta_foreach_numarray(void *ta_state, struct table_info *ti,
2677    ta_foreach_f *f, void *arg);
2678
2679int
2680compare_numarray(const void *k, const void *v)
2681{
2682	const struct numarray *na;
2683	uint32_t key;
2684
2685	key = *((const uint32_t *)k);
2686	na = (const struct numarray *)v;
2687
2688	if (key < na->number)
2689		return (-1);
2690	else if (key > na->number)
2691		return (1);
2692
2693	return (0);
2694}
2695
2696static struct numarray *
2697numarray_find(struct table_info *ti, void *key)
2698{
2699	struct numarray *ri;
2700
2701	ri = bsearch(key, ti->state, ti->data, sizeof(struct numarray),
2702	    compare_ifidx);
2703
2704	return (ri);
2705}
2706
2707static int
2708ta_lookup_numarray(struct table_info *ti, void *key, uint32_t keylen,
2709    uint32_t *val)
2710{
2711	struct numarray *ri;
2712
2713	ri = numarray_find(ti, key);
2714
2715	if (ri != NULL) {
2716		*val = ri->value;
2717		return (1);
2718	}
2719
2720	return (0);
2721}
2722
2723static int
2724ta_init_numarray(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2725    char *data, uint8_t tflags)
2726{
2727	struct numarray_cfg *cfg;
2728
2729	cfg = malloc(sizeof(*cfg), M_IPFW, M_WAITOK | M_ZERO);
2730
2731	cfg->size = 16;
2732	cfg->main_ptr = malloc(sizeof(struct numarray) * cfg->size, M_IPFW,
2733	    M_WAITOK | M_ZERO);
2734
2735	*ta_state = cfg;
2736	ti->state = cfg->main_ptr;
2737	ti->lookup = ta_lookup_numarray;
2738
2739	return (0);
2740}
2741
2742/*
2743 * Destroys table @ti
2744 */
2745static void
2746ta_destroy_numarray(void *ta_state, struct table_info *ti)
2747{
2748	struct numarray_cfg *cfg;
2749
2750	cfg = (struct numarray_cfg *)ta_state;
2751
2752	if (cfg->main_ptr != NULL)
2753		free(cfg->main_ptr, M_IPFW);
2754
2755	free(cfg, M_IPFW);
2756}
2757
2758/*
2759 * Provide algo-specific table info
2760 */
2761static void
2762ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2763{
2764	struct numarray_cfg *cfg;
2765
2766	cfg = (struct numarray_cfg *)ta_state;
2767
2768	tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2769	tinfo->size4 = cfg->size;
2770	tinfo->count4 = cfg->used;
2771	tinfo->itemsize4 = sizeof(struct numarray);
2772}
2773
2774/*
2775 * Prepare for addition/deletion to an array.
2776 */
2777static int
2778ta_prepare_add_numarray(struct ip_fw_chain *ch, struct tentry_info *tei,
2779    void *ta_buf)
2780{
2781	struct ta_buf_numarray *tb;
2782
2783	tb = (struct ta_buf_numarray *)ta_buf;
2784
2785	tb->na.number = *((uint32_t *)tei->paddr);
2786
2787	return (0);
2788}
2789
2790static int
2791ta_add_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2792    void *ta_buf, uint32_t *pnum)
2793{
2794	struct numarray_cfg *cfg;
2795	struct ta_buf_numarray *tb;
2796	struct numarray *ri;
2797	int res;
2798	uint32_t value;
2799
2800	tb = (struct ta_buf_numarray *)ta_buf;
2801	cfg = (struct numarray_cfg *)ta_state;
2802
2803	/* Read current value from @tei */
2804	tb->na.value = tei->value;
2805
2806	ri = numarray_find(ti, &tb->na.number);
2807
2808	if (ri != NULL) {
2809		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2810			return (EEXIST);
2811
2812		/* Exchange values between ri and @tei */
2813		value = ri->value;
2814		ri->value = tei->value;
2815		tei->value = value;
2816		/* Indicate that update has happened instead of addition */
2817		tei->flags |= TEI_FLAGS_UPDATED;
2818		*pnum = 0;
2819		return (0);
2820	}
2821
2822	if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2823		return (EFBIG);
2824
2825	res = badd(&tb->na.number, &tb->na, cfg->main_ptr, cfg->used,
2826	    sizeof(struct numarray), compare_numarray);
2827
2828	KASSERT(res == 1, ("number %d already exists", tb->na.number));
2829	cfg->used++;
2830	ti->data = cfg->used;
2831	*pnum = 1;
2832
2833	return (0);
2834}
2835
2836/*
2837 * Remove key from both configuration list and
2838 * runtime array. Removed interface notification.
2839 */
2840static int
2841ta_del_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2842    void *ta_buf, uint32_t *pnum)
2843{
2844	struct numarray_cfg *cfg;
2845	struct ta_buf_numarray *tb;
2846	struct numarray *ri;
2847	int res;
2848
2849	tb = (struct ta_buf_numarray *)ta_buf;
2850	cfg = (struct numarray_cfg *)ta_state;
2851
2852	ri = numarray_find(ti, &tb->na.number);
2853	if (ri == NULL)
2854		return (ENOENT);
2855
2856	tei->value = ri->value;
2857
2858	res = bdel(&tb->na.number, cfg->main_ptr, cfg->used,
2859	    sizeof(struct numarray), compare_numarray);
2860
2861	KASSERT(res == 1, ("number %u does not exist", tb->na.number));
2862	cfg->used--;
2863	ti->data = cfg->used;
2864	*pnum = 1;
2865
2866	return (0);
2867}
2868
2869static void
2870ta_flush_numarray_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2871    void *ta_buf)
2872{
2873
2874	/* We don't have any state, do nothing */
2875}
2876
2877
2878/*
2879 * Table growing callbacks.
2880 */
2881
2882static int
2883ta_need_modify_numarray(void *ta_state, struct table_info *ti, uint32_t count,
2884    uint64_t *pflags)
2885{
2886	struct numarray_cfg *cfg;
2887	size_t size;
2888
2889	cfg = (struct numarray_cfg *)ta_state;
2890
2891	size = cfg->size;
2892	while (size < cfg->used + count)
2893		size *= 2;
2894
2895	if (size != cfg->size) {
2896		*pflags = size;
2897		return (1);
2898	}
2899
2900	return (0);
2901}
2902
2903/*
2904 * Allocate new, larger runtime array.
2905 */
2906static int
2907ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags)
2908{
2909	struct mod_item *mi;
2910
2911	mi = (struct mod_item *)ta_buf;
2912
2913	memset(mi, 0, sizeof(struct mod_item));
2914	mi->size = *pflags;
2915	mi->main_ptr = malloc(sizeof(struct numarray) * mi->size, M_IPFW,
2916	    M_WAITOK | M_ZERO);
2917
2918	return (0);
2919}
2920
2921/*
2922 * Copy data from old runtime array to new one.
2923 */
2924static int
2925ta_fill_mod_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2926    uint64_t *pflags)
2927{
2928	struct mod_item *mi;
2929	struct numarray_cfg *cfg;
2930
2931	mi = (struct mod_item *)ta_buf;
2932	cfg = (struct numarray_cfg *)ta_state;
2933
2934	/* Check if we still need to grow array */
2935	if (cfg->size >= mi->size) {
2936		*pflags = 0;
2937		return (0);
2938	}
2939
2940	memcpy(mi->main_ptr, cfg->main_ptr, cfg->used * sizeof(struct numarray));
2941
2942	return (0);
2943}
2944
2945/*
2946 * Switch old & new arrays.
2947 */
2948static void
2949ta_modify_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2950    uint64_t pflags)
2951{
2952	struct mod_item *mi;
2953	struct numarray_cfg *cfg;
2954	void *old_ptr;
2955
2956	mi = (struct mod_item *)ta_buf;
2957	cfg = (struct numarray_cfg *)ta_state;
2958
2959	old_ptr = cfg->main_ptr;
2960	cfg->main_ptr = mi->main_ptr;
2961	cfg->size = mi->size;
2962	ti->state = cfg->main_ptr;
2963
2964	mi->main_ptr = old_ptr;
2965}
2966
2967/*
2968 * Free unneded array.
2969 */
2970static void
2971ta_flush_mod_numarray(void *ta_buf)
2972{
2973	struct mod_item *mi;
2974
2975	mi = (struct mod_item *)ta_buf;
2976	if (mi->main_ptr != NULL)
2977		free(mi->main_ptr, M_IPFW);
2978}
2979
2980static int
2981ta_dump_numarray_tentry(void *ta_state, struct table_info *ti, void *e,
2982    ipfw_obj_tentry *tent)
2983{
2984	struct numarray *na;
2985
2986	na = (struct numarray *)e;
2987
2988	tent->k.key = na->number;
2989	tent->v.kidx = na->value;
2990
2991	return (0);
2992}
2993
2994static int
2995ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2996    ipfw_obj_tentry *tent)
2997{
2998	struct numarray_cfg *cfg;
2999	struct numarray *ri;
3000
3001	cfg = (struct numarray_cfg *)ta_state;
3002
3003	ri = numarray_find(ti, &tent->k.key);
3004
3005	if (ri != NULL) {
3006		ta_dump_numarray_tentry(ta_state, ti, ri, tent);
3007		return (0);
3008	}
3009
3010	return (ENOENT);
3011}
3012
3013static void
3014ta_foreach_numarray(void *ta_state, struct table_info *ti, ta_foreach_f *f,
3015    void *arg)
3016{
3017	struct numarray_cfg *cfg;
3018	struct numarray *array;
3019	int i;
3020
3021	cfg = (struct numarray_cfg *)ta_state;
3022	array = cfg->main_ptr;
3023
3024	for (i = 0; i < cfg->used; i++)
3025		f(&array[i], arg);
3026}
3027
3028struct table_algo number_array = {
3029	.name		= "number:array",
3030	.type		= IPFW_TABLE_NUMBER,
3031	.ta_buf_size	= sizeof(struct ta_buf_numarray),
3032	.init		= ta_init_numarray,
3033	.destroy	= ta_destroy_numarray,
3034	.prepare_add	= ta_prepare_add_numarray,
3035	.prepare_del	= ta_prepare_add_numarray,
3036	.add		= ta_add_numarray,
3037	.del		= ta_del_numarray,
3038	.flush_entry	= ta_flush_numarray_entry,
3039	.foreach	= ta_foreach_numarray,
3040	.dump_tentry	= ta_dump_numarray_tentry,
3041	.find_tentry	= ta_find_numarray_tentry,
3042	.dump_tinfo	= ta_dump_numarray_tinfo,
3043	.need_modify	= ta_need_modify_numarray,
3044	.prepare_mod	= ta_prepare_mod_numarray,
3045	.fill_mod	= ta_fill_mod_numarray,
3046	.modify		= ta_modify_numarray,
3047	.flush_mod	= ta_flush_mod_numarray,
3048};
3049
3050/*
3051 * flow:hash cmds
3052 *
3053 *
3054 * ti->data:
3055 * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
3056 * [        8][        8[          8][         8]
3057 *
3058 * inv.mask4: 32 - mask
3059 * inv.mask6:
3060 * 1) _slow lookup: mask
3061 * 2) _aligned: (128 - mask) / 8
3062 * 3) _64: 8
3063 *
3064 *
3065 * pflags:
3066 * [hsize4][hsize6]
3067 * [    16][    16]
3068 */
3069
3070struct fhashentry;
3071
3072SLIST_HEAD(fhashbhead, fhashentry);
3073
3074struct fhashentry {
3075	SLIST_ENTRY(fhashentry)	next;
3076	uint8_t		af;
3077	uint8_t		proto;
3078	uint16_t	spare0;
3079	uint16_t	dport;
3080	uint16_t	sport;
3081	uint32_t	value;
3082	uint32_t	spare1;
3083};
3084
3085struct fhashentry4 {
3086	struct fhashentry	e;
3087	struct in_addr		dip;
3088	struct in_addr		sip;
3089};
3090
3091struct fhashentry6 {
3092	struct fhashentry	e;
3093	struct in6_addr		dip6;
3094	struct in6_addr		sip6;
3095};
3096
3097struct fhash_cfg {
3098	struct fhashbhead	*head;
3099	size_t			size;
3100	size_t			items;
3101	struct fhashentry4	fe4;
3102	struct fhashentry6	fe6;
3103};
3104
3105struct ta_buf_fhash {
3106	void	*ent_ptr;
3107	struct fhashentry6 fe6;
3108};
3109
3110static __inline int cmp_flow_ent(struct fhashentry *a,
3111    struct fhashentry *b, size_t sz);
3112static __inline uint32_t hash_flow4(struct fhashentry4 *f, int hsize);
3113static __inline uint32_t hash_flow6(struct fhashentry6 *f, int hsize);
3114static uint32_t hash_flow_ent(struct fhashentry *ent, uint32_t size);
3115static int ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3116    uint32_t *val);
3117static int ta_init_fhash(struct ip_fw_chain *ch, void **ta_state,
3118struct table_info *ti, char *data, uint8_t tflags);
3119static void ta_destroy_fhash(void *ta_state, struct table_info *ti);
3120static void ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti,
3121    ipfw_ta_tinfo *tinfo);
3122static int ta_dump_fhash_tentry(void *ta_state, struct table_info *ti,
3123    void *e, ipfw_obj_tentry *tent);
3124static int tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent);
3125static int ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
3126    ipfw_obj_tentry *tent);
3127static void ta_foreach_fhash(void *ta_state, struct table_info *ti,
3128    ta_foreach_f *f, void *arg);
3129static int ta_prepare_add_fhash(struct ip_fw_chain *ch,
3130    struct tentry_info *tei, void *ta_buf);
3131static int ta_add_fhash(void *ta_state, struct table_info *ti,
3132    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3133static int ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3134    void *ta_buf);
3135static int ta_del_fhash(void *ta_state, struct table_info *ti,
3136    struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3137static void ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3138    void *ta_buf);
3139static int ta_need_modify_fhash(void *ta_state, struct table_info *ti,
3140    uint32_t count, uint64_t *pflags);
3141static int ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags);
3142static int ta_fill_mod_fhash(void *ta_state, struct table_info *ti,
3143    void *ta_buf, uint64_t *pflags);
3144static void ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3145    uint64_t pflags);
3146static void ta_flush_mod_fhash(void *ta_buf);
3147
3148static __inline int
3149cmp_flow_ent(struct fhashentry *a, struct fhashentry *b, size_t sz)
3150{
3151	uint64_t *ka, *kb;
3152
3153	ka = (uint64_t *)(&a->next + 1);
3154	kb = (uint64_t *)(&b->next + 1);
3155
3156	if (*ka == *kb && (memcmp(a + 1, b + 1, sz) == 0))
3157		return (1);
3158
3159	return (0);
3160}
3161
3162static __inline uint32_t
3163hash_flow4(struct fhashentry4 *f, int hsize)
3164{
3165	uint32_t i;
3166
3167	i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport);
3168
3169	return (i % (hsize - 1));
3170}
3171
3172static __inline uint32_t
3173hash_flow6(struct fhashentry6 *f, int hsize)
3174{
3175	uint32_t i;
3176
3177	i = (f->dip6.__u6_addr.__u6_addr32[2]) ^
3178	    (f->dip6.__u6_addr.__u6_addr32[3]) ^
3179	    (f->sip6.__u6_addr.__u6_addr32[2]) ^
3180	    (f->sip6.__u6_addr.__u6_addr32[3]) ^
3181	    (f->e.dport) ^ (f->e.sport);
3182
3183	return (i % (hsize - 1));
3184}
3185
3186static uint32_t
3187hash_flow_ent(struct fhashentry *ent, uint32_t size)
3188{
3189	uint32_t hash;
3190
3191	if (ent->af == AF_INET) {
3192		hash = hash_flow4((struct fhashentry4 *)ent, size);
3193	} else {
3194		hash = hash_flow6((struct fhashentry6 *)ent, size);
3195	}
3196
3197	return (hash);
3198}
3199
3200static int
3201ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3202    uint32_t *val)
3203{
3204	struct fhashbhead *head;
3205	struct fhashentry *ent;
3206	struct fhashentry4 *m4;
3207	struct ipfw_flow_id *id;
3208	uint32_t hsize;
3209	uint16_t hash;
3210
3211	id = (struct ipfw_flow_id *)key;
3212	head = (struct fhashbhead *)ti->state;
3213	hsize = ti->data;
3214	m4 = (struct fhashentry4 *)ti->xstate;
3215
3216	if (id->addr_type == 4) {
3217		struct fhashentry4 f;
3218
3219		/* Copy hash mask */
3220		f = *m4;
3221
3222		f.dip.s_addr &= id->dst_ip;
3223		f.sip.s_addr &= id->src_ip;
3224		f.e.dport &= id->dst_port;
3225		f.e.sport &= id->src_port;
3226		f.e.proto &= id->proto;
3227		hash = hash_flow4(&f, hsize);
3228		SLIST_FOREACH(ent, &head[hash], next) {
3229			if (cmp_flow_ent(ent, &f.e, 2 * 4) != 0) {
3230				*val = ent->value;
3231				return (1);
3232			}
3233		}
3234	} else if (id->addr_type == 6) {
3235		struct fhashentry6 f;
3236		uint64_t *fp, *idp;
3237
3238		/* Copy hash mask */
3239		f = *((struct fhashentry6 *)(m4 + 1));
3240
3241		/* Handle lack of __u6_addr.__u6_addr64 */
3242		fp = (uint64_t *)&f.dip6;
3243		idp = (uint64_t *)&id->dst_ip6;
3244		/* src IPv6 is stored after dst IPv6 */
3245		*fp++ &= *idp++;
3246		*fp++ &= *idp++;
3247		*fp++ &= *idp++;
3248		*fp &= *idp;
3249		f.e.dport &= id->dst_port;
3250		f.e.sport &= id->src_port;
3251		f.e.proto &= id->proto;
3252		hash = hash_flow6(&f, hsize);
3253		SLIST_FOREACH(ent, &head[hash], next) {
3254			if (cmp_flow_ent(ent, &f.e, 2 * 16) != 0) {
3255				*val = ent->value;
3256				return (1);
3257			}
3258		}
3259	}
3260
3261	return (0);
3262}
3263
3264/*
3265 * New table.
3266 */
3267static int
3268ta_init_fhash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
3269    char *data, uint8_t tflags)
3270{
3271	struct fhash_cfg *cfg;
3272	struct fhashentry4 *fe4;
3273	struct fhashentry6 *fe6;
3274	u_int i;
3275
3276	cfg = malloc(sizeof(struct fhash_cfg), M_IPFW, M_WAITOK | M_ZERO);
3277
3278	cfg->size = 512;
3279
3280	cfg->head = malloc(sizeof(struct fhashbhead) * cfg->size, M_IPFW,
3281	    M_WAITOK | M_ZERO);
3282	for (i = 0; i < cfg->size; i++)
3283		SLIST_INIT(&cfg->head[i]);
3284
3285	/* Fill in fe masks based on @tflags */
3286	fe4 = &cfg->fe4;
3287	fe6 = &cfg->fe6;
3288	if (tflags & IPFW_TFFLAG_SRCIP) {
3289		memset(&fe4->sip, 0xFF, sizeof(fe4->sip));
3290		memset(&fe6->sip6, 0xFF, sizeof(fe6->sip6));
3291	}
3292	if (tflags & IPFW_TFFLAG_DSTIP) {
3293		memset(&fe4->dip, 0xFF, sizeof(fe4->dip));
3294		memset(&fe6->dip6, 0xFF, sizeof(fe6->dip6));
3295	}
3296	if (tflags & IPFW_TFFLAG_SRCPORT) {
3297		memset(&fe4->e.sport, 0xFF, sizeof(fe4->e.sport));
3298		memset(&fe6->e.sport, 0xFF, sizeof(fe6->e.sport));
3299	}
3300	if (tflags & IPFW_TFFLAG_DSTPORT) {
3301		memset(&fe4->e.dport, 0xFF, sizeof(fe4->e.dport));
3302		memset(&fe6->e.dport, 0xFF, sizeof(fe6->e.dport));
3303	}
3304	if (tflags & IPFW_TFFLAG_PROTO) {
3305		memset(&fe4->e.proto, 0xFF, sizeof(fe4->e.proto));
3306		memset(&fe6->e.proto, 0xFF, sizeof(fe6->e.proto));
3307	}
3308
3309	fe4->e.af = AF_INET;
3310	fe6->e.af = AF_INET6;
3311
3312	*ta_state = cfg;
3313	ti->state = cfg->head;
3314	ti->xstate = &cfg->fe4;
3315	ti->data = cfg->size;
3316	ti->lookup = ta_lookup_fhash;
3317
3318	return (0);
3319}
3320
3321static void
3322ta_destroy_fhash(void *ta_state, struct table_info *ti)
3323{
3324	struct fhash_cfg *cfg;
3325	struct fhashentry *ent, *ent_next;
3326	int i;
3327
3328	cfg = (struct fhash_cfg *)ta_state;
3329
3330	for (i = 0; i < cfg->size; i++)
3331		SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next)
3332			free(ent, M_IPFW_TBL);
3333
3334	free(cfg->head, M_IPFW);
3335	free(cfg, M_IPFW);
3336}
3337
3338/*
3339 * Provide algo-specific table info
3340 */
3341static void
3342ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
3343{
3344	struct fhash_cfg *cfg;
3345
3346	cfg = (struct fhash_cfg *)ta_state;
3347
3348	tinfo->flags = IPFW_TATFLAGS_AFITEM;
3349	tinfo->taclass4 = IPFW_TACLASS_HASH;
3350	tinfo->size4 = cfg->size;
3351	tinfo->count4 = cfg->items;
3352	tinfo->itemsize4 = sizeof(struct fhashentry4);
3353	tinfo->itemsize6 = sizeof(struct fhashentry6);
3354}
3355
3356static int
3357ta_dump_fhash_tentry(void *ta_state, struct table_info *ti, void *e,
3358    ipfw_obj_tentry *tent)
3359{
3360	struct fhash_cfg *cfg;
3361	struct fhashentry *ent;
3362	struct fhashentry4 *fe4;
3363#ifdef INET6
3364	struct fhashentry6 *fe6;
3365#endif
3366	struct tflow_entry *tfe;
3367
3368	cfg = (struct fhash_cfg *)ta_state;
3369	ent = (struct fhashentry *)e;
3370	tfe = &tent->k.flow;
3371
3372	tfe->af = ent->af;
3373	tfe->proto = ent->proto;
3374	tfe->dport = htons(ent->dport);
3375	tfe->sport = htons(ent->sport);
3376	tent->v.kidx = ent->value;
3377	tent->subtype = ent->af;
3378
3379	if (ent->af == AF_INET) {
3380		fe4 = (struct fhashentry4 *)ent;
3381		tfe->a.a4.sip.s_addr = htonl(fe4->sip.s_addr);
3382		tfe->a.a4.dip.s_addr = htonl(fe4->dip.s_addr);
3383		tent->masklen = 32;
3384#ifdef INET6
3385	} else {
3386		fe6 = (struct fhashentry6 *)ent;
3387		tfe->a.a6.sip6 = fe6->sip6;
3388		tfe->a.a6.dip6 = fe6->dip6;
3389		tent->masklen = 128;
3390#endif
3391	}
3392
3393	return (0);
3394}
3395
3396static int
3397tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent)
3398{
3399#ifdef INET
3400	struct fhashentry4 *fe4;
3401#endif
3402#ifdef INET6
3403	struct fhashentry6 *fe6;
3404#endif
3405	struct tflow_entry *tfe;
3406
3407	tfe = (struct tflow_entry *)tei->paddr;
3408
3409	ent->af = tei->subtype;
3410	ent->proto = tfe->proto;
3411	ent->dport = ntohs(tfe->dport);
3412	ent->sport = ntohs(tfe->sport);
3413
3414	if (tei->subtype == AF_INET) {
3415#ifdef INET
3416		fe4 = (struct fhashentry4 *)ent;
3417		fe4->sip.s_addr = ntohl(tfe->a.a4.sip.s_addr);
3418		fe4->dip.s_addr = ntohl(tfe->a.a4.dip.s_addr);
3419#endif
3420#ifdef INET6
3421	} else if (tei->subtype == AF_INET6) {
3422		fe6 = (struct fhashentry6 *)ent;
3423		fe6->sip6 = tfe->a.a6.sip6;
3424		fe6->dip6 = tfe->a.a6.dip6;
3425#endif
3426	} else {
3427		/* Unknown CIDR type */
3428		return (EINVAL);
3429	}
3430
3431	return (0);
3432}
3433
3434
3435static int
3436ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
3437    ipfw_obj_tentry *tent)
3438{
3439	struct fhash_cfg *cfg;
3440	struct fhashbhead *head;
3441	struct fhashentry *ent, *tmp;
3442	struct fhashentry6 fe6;
3443	struct tentry_info tei;
3444	int error;
3445	uint32_t hash;
3446	size_t sz;
3447
3448	cfg = (struct fhash_cfg *)ta_state;
3449
3450	ent = &fe6.e;
3451
3452	memset(&fe6, 0, sizeof(fe6));
3453	memset(&tei, 0, sizeof(tei));
3454
3455	tei.paddr = &tent->k.flow;
3456	tei.subtype = tent->subtype;
3457
3458	if ((error = tei_to_fhash_ent(&tei, ent)) != 0)
3459		return (error);
3460
3461	head = cfg->head;
3462	hash = hash_flow_ent(ent, cfg->size);
3463
3464	if (tei.subtype == AF_INET)
3465		sz = 2 * sizeof(struct in_addr);
3466	else
3467		sz = 2 * sizeof(struct in6_addr);
3468
3469	/* Check for existence */
3470	SLIST_FOREACH(tmp, &head[hash], next) {
3471		if (cmp_flow_ent(tmp, ent, sz) != 0) {
3472			ta_dump_fhash_tentry(ta_state, ti, tmp, tent);
3473			return (0);
3474		}
3475	}
3476
3477	return (ENOENT);
3478}
3479
3480static void
3481ta_foreach_fhash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
3482    void *arg)
3483{
3484	struct fhash_cfg *cfg;
3485	struct fhashentry *ent, *ent_next;
3486	int i;
3487
3488	cfg = (struct fhash_cfg *)ta_state;
3489
3490	for (i = 0; i < cfg->size; i++)
3491		SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next)
3492			f(ent, arg);
3493}
3494
3495static int
3496ta_prepare_add_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3497    void *ta_buf)
3498{
3499	struct ta_buf_fhash *tb;
3500	struct fhashentry *ent;
3501	size_t sz;
3502	int error;
3503
3504	tb = (struct ta_buf_fhash *)ta_buf;
3505
3506	if (tei->subtype == AF_INET)
3507		sz = sizeof(struct fhashentry4);
3508	else if (tei->subtype == AF_INET6)
3509		sz = sizeof(struct fhashentry6);
3510	else
3511		return (EINVAL);
3512
3513	ent = malloc(sz, M_IPFW_TBL, M_WAITOK | M_ZERO);
3514
3515	error = tei_to_fhash_ent(tei, ent);
3516	if (error != 0) {
3517		free(ent, M_IPFW_TBL);
3518		return (error);
3519	}
3520	tb->ent_ptr = ent;
3521
3522	return (0);
3523}
3524
3525static int
3526ta_add_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
3527    void *ta_buf, uint32_t *pnum)
3528{
3529	struct fhash_cfg *cfg;
3530	struct fhashbhead *head;
3531	struct fhashentry *ent, *tmp;
3532	struct ta_buf_fhash *tb;
3533	int exists;
3534	uint32_t hash, value;
3535	size_t sz;
3536
3537	cfg = (struct fhash_cfg *)ta_state;
3538	tb = (struct ta_buf_fhash *)ta_buf;
3539	ent = (struct fhashentry *)tb->ent_ptr;
3540	exists = 0;
3541
3542	/* Read current value from @tei */
3543	ent->value = tei->value;
3544
3545	head = cfg->head;
3546	hash = hash_flow_ent(ent, cfg->size);
3547
3548	if (tei->subtype == AF_INET)
3549		sz = 2 * sizeof(struct in_addr);
3550	else
3551		sz = 2 * sizeof(struct in6_addr);
3552
3553	/* Check for existence */
3554	SLIST_FOREACH(tmp, &head[hash], next) {
3555		if (cmp_flow_ent(tmp, ent, sz) != 0) {
3556			exists = 1;
3557			break;
3558		}
3559	}
3560
3561	if (exists == 1) {
3562		if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
3563			return (EEXIST);
3564		/* Record already exists. Update value if we're asked to */
3565		/* Exchange values between tmp and @tei */
3566		value = tmp->value;
3567		tmp->value = tei->value;
3568		tei->value = value;
3569		/* Indicate that update has happened instead of addition */
3570		tei->flags |= TEI_FLAGS_UPDATED;
3571		*pnum = 0;
3572	} else {
3573		if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
3574			return (EFBIG);
3575
3576		SLIST_INSERT_HEAD(&head[hash], ent, next);
3577		tb->ent_ptr = NULL;
3578		*pnum = 1;
3579
3580		/* Update counters and check if we need to grow hash */
3581		cfg->items++;
3582	}
3583
3584	return (0);
3585}
3586
3587static int
3588ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3589    void *ta_buf)
3590{
3591	struct ta_buf_fhash *tb;
3592
3593	tb = (struct ta_buf_fhash *)ta_buf;
3594
3595	return (tei_to_fhash_ent(tei, &tb->fe6.e));
3596}
3597
3598static int
3599ta_del_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
3600    void *ta_buf, uint32_t *pnum)
3601{
3602	struct fhash_cfg *cfg;
3603	struct fhashbhead *head;
3604	struct fhashentry *ent, *tmp;
3605	struct ta_buf_fhash *tb;
3606	uint32_t hash;
3607	size_t sz;
3608
3609	cfg = (struct fhash_cfg *)ta_state;
3610	tb = (struct ta_buf_fhash *)ta_buf;
3611	ent = &tb->fe6.e;
3612
3613	head = cfg->head;
3614	hash = hash_flow_ent(ent, cfg->size);
3615
3616	if (tei->subtype == AF_INET)
3617		sz = 2 * sizeof(struct in_addr);
3618	else
3619		sz = 2 * sizeof(struct in6_addr);
3620
3621	/* Check for existence */
3622	SLIST_FOREACH(tmp, &head[hash], next) {
3623		if (cmp_flow_ent(tmp, ent, sz) == 0)
3624			continue;
3625
3626		SLIST_REMOVE(&head[hash], tmp, fhashentry, next);
3627		tei->value = tmp->value;
3628		*pnum = 1;
3629		cfg->items--;
3630		tb->ent_ptr = tmp;
3631		return (0);
3632	}
3633
3634	return (ENOENT);
3635}
3636
3637static void
3638ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3639    void *ta_buf)
3640{
3641	struct ta_buf_fhash *tb;
3642
3643	tb = (struct ta_buf_fhash *)ta_buf;
3644
3645	if (tb->ent_ptr != NULL)
3646		free(tb->ent_ptr, M_IPFW_TBL);
3647}
3648
3649/*
3650 * Hash growing callbacks.
3651 */
3652
3653static int
3654ta_need_modify_fhash(void *ta_state, struct table_info *ti, uint32_t count,
3655    uint64_t *pflags)
3656{
3657	struct fhash_cfg *cfg;
3658
3659	cfg = (struct fhash_cfg *)ta_state;
3660
3661	if (cfg->items > cfg->size && cfg->size < 65536) {
3662		*pflags = cfg->size * 2;
3663		return (1);
3664	}
3665
3666	return (0);
3667}
3668
3669/*
3670 * Allocate new, larger fhash.
3671 */
3672static int
3673ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags)
3674{
3675	struct mod_item *mi;
3676	struct fhashbhead *head;
3677	u_int i;
3678
3679	mi = (struct mod_item *)ta_buf;
3680
3681	memset(mi, 0, sizeof(struct mod_item));
3682	mi->size = *pflags;
3683	head = malloc(sizeof(struct fhashbhead) * mi->size, M_IPFW,
3684	    M_WAITOK | M_ZERO);
3685	for (i = 0; i < mi->size; i++)
3686		SLIST_INIT(&head[i]);
3687
3688	mi->main_ptr = head;
3689
3690	return (0);
3691}
3692
3693/*
3694 * Copy data from old runtime array to new one.
3695 */
3696static int
3697ta_fill_mod_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3698    uint64_t *pflags)
3699{
3700
3701	/* In is not possible to do rehash if we're not holidng WLOCK. */
3702	return (0);
3703}
3704
3705/*
3706 * Switch old & new arrays.
3707 */
3708static void
3709ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3710    uint64_t pflags)
3711{
3712	struct mod_item *mi;
3713	struct fhash_cfg *cfg;
3714	struct fhashbhead *old_head, *new_head;
3715	struct fhashentry *ent, *ent_next;
3716	int i;
3717	uint32_t nhash;
3718	size_t old_size;
3719
3720	mi = (struct mod_item *)ta_buf;
3721	cfg = (struct fhash_cfg *)ta_state;
3722
3723	old_size = cfg->size;
3724	old_head = ti->state;
3725
3726	new_head = (struct fhashbhead *)mi->main_ptr;
3727	for (i = 0; i < old_size; i++) {
3728		SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
3729			nhash = hash_flow_ent(ent, mi->size);
3730			SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
3731		}
3732	}
3733
3734	ti->state = new_head;
3735	ti->data = mi->size;
3736	cfg->head = new_head;
3737	cfg->size = mi->size;
3738
3739	mi->main_ptr = old_head;
3740}
3741
3742/*
3743 * Free unneded array.
3744 */
3745static void
3746ta_flush_mod_fhash(void *ta_buf)
3747{
3748	struct mod_item *mi;
3749
3750	mi = (struct mod_item *)ta_buf;
3751	if (mi->main_ptr != NULL)
3752		free(mi->main_ptr, M_IPFW);
3753}
3754
3755struct table_algo flow_hash = {
3756	.name		= "flow:hash",
3757	.type		= IPFW_TABLE_FLOW,
3758	.flags		= TA_FLAG_DEFAULT,
3759	.ta_buf_size	= sizeof(struct ta_buf_fhash),
3760	.init		= ta_init_fhash,
3761	.destroy	= ta_destroy_fhash,
3762	.prepare_add	= ta_prepare_add_fhash,
3763	.prepare_del	= ta_prepare_del_fhash,
3764	.add		= ta_add_fhash,
3765	.del		= ta_del_fhash,
3766	.flush_entry	= ta_flush_fhash_entry,
3767	.foreach	= ta_foreach_fhash,
3768	.dump_tentry	= ta_dump_fhash_tentry,
3769	.find_tentry	= ta_find_fhash_tentry,
3770	.dump_tinfo	= ta_dump_fhash_tinfo,
3771	.need_modify	= ta_need_modify_fhash,
3772	.prepare_mod	= ta_prepare_mod_fhash,
3773	.fill_mod	= ta_fill_mod_fhash,
3774	.modify		= ta_modify_fhash,
3775	.flush_mod	= ta_flush_mod_fhash,
3776};
3777
3778/*
3779 * Kernel fibs bindings.
3780 *
3781 * Implementation:
3782 *
3783 * Runtime part:
3784 * - fully relies on route API
3785 * - fib number is stored in ti->data
3786 *
3787 */
3788
3789static int ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen,
3790    uint32_t *val);
3791static int kfib_parse_opts(int *pfib, char *data);
3792static void ta_print_kfib_config(void *ta_state, struct table_info *ti,
3793    char *buf, size_t bufsize);
3794static int ta_init_kfib(struct ip_fw_chain *ch, void **ta_state,
3795    struct table_info *ti, char *data, uint8_t tflags);
3796static void ta_destroy_kfib(void *ta_state, struct table_info *ti);
3797static void ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti,
3798    ipfw_ta_tinfo *tinfo);
3799static int contigmask(uint8_t *p, int len);
3800static int ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e,
3801    ipfw_obj_tentry *tent);
3802static int ta_dump_kfib_tentry_int(struct sockaddr *paddr,
3803    struct sockaddr *pmask, ipfw_obj_tentry *tent);
3804static int ta_find_kfib_tentry(void *ta_state, struct table_info *ti,
3805    ipfw_obj_tentry *tent);
3806static void ta_foreach_kfib(void *ta_state, struct table_info *ti,
3807    ta_foreach_f *f, void *arg);
3808
3809
3810static int
3811ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen,
3812    uint32_t *val)
3813{
3814#ifdef INET
3815	struct in_addr in;
3816#endif
3817	int error;
3818
3819	error = ENOENT;
3820#ifdef INET
3821	if (keylen == 4) {
3822		in.s_addr = *(in_addr_t *)key;
3823		NET_EPOCH_ASSERT();
3824		error = fib4_lookup(ti->data, in, 0, NHR_NONE, 0) != NULL;
3825	}
3826#endif
3827#ifdef INET6
3828	if (keylen == 6)
3829		error = fib6_lookup(ti->data, (struct in6_addr *)key,
3830		    0, NHR_NONE, 0) != NULL;
3831#endif
3832
3833	if (error != 0)
3834		return (0);
3835
3836	*val = 0;
3837
3838	return (1);
3839}
3840
3841/* Parse 'fib=%d' */
3842static int
3843kfib_parse_opts(int *pfib, char *data)
3844{
3845	char *pdel, *pend, *s;
3846	int fibnum;
3847
3848	if (data == NULL)
3849		return (0);
3850	if ((pdel = strchr(data, ' ')) == NULL)
3851		return (0);
3852	while (*pdel == ' ')
3853		pdel++;
3854	if (strncmp(pdel, "fib=", 4) != 0)
3855		return (EINVAL);
3856	if ((s = strchr(pdel, ' ')) != NULL)
3857		*s++ = '\0';
3858
3859	pdel += 4;
3860	/* Need \d+ */
3861	fibnum = strtol(pdel, &pend, 10);
3862	if (*pend != '\0')
3863		return (EINVAL);
3864
3865	*pfib = fibnum;
3866
3867	return (0);
3868}
3869
3870static void
3871ta_print_kfib_config(void *ta_state, struct table_info *ti, char *buf,
3872    size_t bufsize)
3873{
3874
3875	if (ti->data != 0)
3876		snprintf(buf, bufsize, "%s fib=%lu", "addr:kfib", ti->data);
3877	else
3878		snprintf(buf, bufsize, "%s", "addr:kfib");
3879}
3880
3881static int
3882ta_init_kfib(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
3883    char *data, uint8_t tflags)
3884{
3885	int error, fibnum;
3886
3887	fibnum = 0;
3888	if ((error = kfib_parse_opts(&fibnum, data)) != 0)
3889		return (error);
3890
3891	if (fibnum >= rt_numfibs)
3892		return (E2BIG);
3893
3894	ti->data = fibnum;
3895	ti->lookup = ta_lookup_kfib;
3896
3897	return (0);
3898}
3899
3900/*
3901 * Destroys table @ti
3902 */
3903static void
3904ta_destroy_kfib(void *ta_state, struct table_info *ti)
3905{
3906
3907}
3908
3909/*
3910 * Provide algo-specific table info
3911 */
3912static void
3913ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
3914{
3915
3916	tinfo->flags = IPFW_TATFLAGS_AFDATA;
3917	tinfo->taclass4 = IPFW_TACLASS_RADIX;
3918	tinfo->count4 = 0;
3919	tinfo->itemsize4 = sizeof(struct rtentry);
3920	tinfo->taclass6 = IPFW_TACLASS_RADIX;
3921	tinfo->count6 = 0;
3922	tinfo->itemsize6 = sizeof(struct rtentry);
3923}
3924
3925static int
3926contigmask(uint8_t *p, int len)
3927{
3928	int i, n;
3929
3930	for (i = 0; i < len ; i++)
3931		if ( (p[i/8] & (1 << (7 - (i%8)))) == 0) /* first bit unset */
3932			break;
3933	for (n= i + 1; n < len; n++)
3934		if ( (p[n/8] & (1 << (7 - (n % 8)))) != 0)
3935			return (-1); /* mask not contiguous */
3936	return (i);
3937}
3938
3939
3940static int
3941ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e,
3942    ipfw_obj_tentry *tent)
3943{
3944	struct rtentry *rte;
3945
3946	rte = (struct rtentry *)e;
3947
3948	return ta_dump_kfib_tentry_int(rt_key(rte), rt_mask(rte), tent);
3949}
3950
3951static int
3952ta_dump_kfib_tentry_int(struct sockaddr *paddr, struct sockaddr *pmask,
3953    ipfw_obj_tentry *tent)
3954{
3955#ifdef INET
3956	struct sockaddr_in *addr, *mask;
3957#endif
3958#ifdef INET6
3959	struct sockaddr_in6 *addr6, *mask6;
3960#endif
3961	int len;
3962
3963	len = 0;
3964
3965	/* Guess IPv4/IPv6 radix by sockaddr family */
3966#ifdef INET
3967	if (paddr->sa_family == AF_INET) {
3968		addr = (struct sockaddr_in *)paddr;
3969		mask = (struct sockaddr_in *)pmask;
3970		tent->k.addr.s_addr = addr->sin_addr.s_addr;
3971		len = 32;
3972		if (mask != NULL)
3973			len = contigmask((uint8_t *)&mask->sin_addr, 32);
3974		if (len == -1)
3975			len = 0;
3976		tent->masklen = len;
3977		tent->subtype = AF_INET;
3978		tent->v.kidx = 0; /* Do we need to put GW here? */
3979	}
3980#endif
3981#ifdef INET6
3982	if (paddr->sa_family == AF_INET6) {
3983		addr6 = (struct sockaddr_in6 *)paddr;
3984		mask6 = (struct sockaddr_in6 *)pmask;
3985		memcpy(&tent->k.addr6, &addr6->sin6_addr,
3986		    sizeof(struct in6_addr));
3987		len = 128;
3988		if (mask6 != NULL)
3989			len = contigmask((uint8_t *)&mask6->sin6_addr, 128);
3990		if (len == -1)
3991			len = 0;
3992		tent->masklen = len;
3993		tent->subtype = AF_INET6;
3994		tent->v.kidx = 0;
3995	}
3996#endif
3997
3998	return (0);
3999}
4000
4001static int
4002ta_find_kfib_tentry(void *ta_state, struct table_info *ti,
4003    ipfw_obj_tentry *tent)
4004{
4005	struct rt_addrinfo info;
4006	struct sockaddr_in6 key6, dst6, mask6;
4007	struct sockaddr *dst, *key, *mask;
4008
4009	/* Prepare sockaddr for prefix/mask and info */
4010	bzero(&dst6, sizeof(dst6));
4011	dst6.sin6_len = sizeof(dst6);
4012	dst = (struct sockaddr *)&dst6;
4013	bzero(&mask6, sizeof(mask6));
4014	mask6.sin6_len = sizeof(mask6);
4015	mask = (struct sockaddr *)&mask6;
4016
4017	bzero(&info, sizeof(info));
4018	info.rti_info[RTAX_DST] = dst;
4019	info.rti_info[RTAX_NETMASK] = mask;
4020
4021	/* Prepare the lookup key */
4022	bzero(&key6, sizeof(key6));
4023	key6.sin6_family = tent->subtype;
4024	key = (struct sockaddr *)&key6;
4025
4026	if (tent->subtype == AF_INET) {
4027		((struct sockaddr_in *)&key6)->sin_addr = tent->k.addr;
4028		key6.sin6_len = sizeof(struct sockaddr_in);
4029	} else {
4030		key6.sin6_addr = tent->k.addr6;
4031		key6.sin6_len = sizeof(struct sockaddr_in6);
4032	}
4033
4034	if (rib_lookup_info(ti->data, key, 0, 0, &info) != 0)
4035		return (ENOENT);
4036	if ((info.rti_addrs & RTA_NETMASK) == 0)
4037		mask = NULL;
4038
4039	ta_dump_kfib_tentry_int(dst, mask, tent);
4040
4041	return (0);
4042}
4043
4044static void
4045ta_foreach_kfib(void *ta_state, struct table_info *ti, ta_foreach_f *f,
4046    void *arg)
4047{
4048	RIB_RLOCK_TRACKER;
4049	struct rib_head *rh;
4050	int error;
4051
4052	rh = rt_tables_get_rnh(ti->data, AF_INET);
4053	if (rh != NULL) {
4054		RIB_RLOCK(rh);
4055		error = rh->rnh_walktree(&rh->head, (walktree_f_t *)f, arg);
4056		RIB_RUNLOCK(rh);
4057	}
4058
4059	rh = rt_tables_get_rnh(ti->data, AF_INET6);
4060	if (rh != NULL) {
4061		RIB_RLOCK(rh);
4062		error = rh->rnh_walktree(&rh->head, (walktree_f_t *)f, arg);
4063		RIB_RUNLOCK(rh);
4064	}
4065}
4066
4067struct table_algo addr_kfib = {
4068	.name		= "addr:kfib",
4069	.type		= IPFW_TABLE_ADDR,
4070	.flags		= TA_FLAG_READONLY,
4071	.ta_buf_size	= 0,
4072	.init		= ta_init_kfib,
4073	.destroy	= ta_destroy_kfib,
4074	.foreach	= ta_foreach_kfib,
4075	.dump_tentry	= ta_dump_kfib_tentry,
4076	.find_tentry	= ta_find_kfib_tentry,
4077	.dump_tinfo	= ta_dump_kfib_tinfo,
4078	.print_config	= ta_print_kfib_config,
4079};
4080
4081void
4082ipfw_table_algo_init(struct ip_fw_chain *ch)
4083{
4084	size_t sz;
4085
4086	/*
4087	 * Register all algorithms presented here.
4088	 */
4089	sz = sizeof(struct table_algo);
4090	ipfw_add_table_algo(ch, &addr_radix, sz, &addr_radix.idx);
4091	ipfw_add_table_algo(ch, &addr_hash, sz, &addr_hash.idx);
4092	ipfw_add_table_algo(ch, &iface_idx, sz, &iface_idx.idx);
4093	ipfw_add_table_algo(ch, &number_array, sz, &number_array.idx);
4094	ipfw_add_table_algo(ch, &flow_hash, sz, &flow_hash.idx);
4095	ipfw_add_table_algo(ch, &addr_kfib, sz, &addr_kfib.idx);
4096}
4097
4098void
4099ipfw_table_algo_destroy(struct ip_fw_chain *ch)
4100{
4101
4102	ipfw_del_table_algo(ch, addr_radix.idx);
4103	ipfw_del_table_algo(ch, addr_hash.idx);
4104	ipfw_del_table_algo(ch, iface_idx.idx);
4105	ipfw_del_table_algo(ch, number_array.idx);
4106	ipfw_del_table_algo(ch, flow_hash.idx);
4107	ipfw_del_table_algo(ch, addr_kfib.idx);
4108}
4109
4110
4111