2 * Copyright (c) 2014 Yandex LLC
3 * Copyright (c) 2014 Alexander V. Chernikov
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
27 #include <sys/cdefs.h>
28 __FBSDID("$FreeBSD$");
31 * Lookup table algorithms.
38 #error IPFIREWALL requires INET.
40 #include "opt_inet6.h"
42 #include <sys/param.h>
43 #include <sys/systm.h>
44 #include <sys/malloc.h>
45 #include <sys/kernel.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_var.h>
56 #include <netinet/in.h>
57 #include <netinet/in_fib.h>
58 #include <netinet/ip_var.h> /* struct ipfw_rule_ref */
59 #include <netinet/ip_fw.h>
60 #include <netinet6/in6_fib.h>
62 #include <netpfil/ipfw/ip_fw_private.h>
63 #include <netpfil/ipfw/ip_fw_table.h>
67 * IPFW table lookup algorithms.
69 * What is needed to add another table algo?
72 * * struct table_algo has to be filled with:
73 * name: "type:algoname" format, e.g. "addr:radix". Currently
74 * there are the following types: "addr", "iface", "number" and "flow".
75 * type: one of IPFW_TABLE_* types
76 * flags: one or more TA_FLAGS_*
77 * ta_buf_size: size of structure used to store add/del item state.
78 * Needs to be less than TA_BUF_SZ.
79 * callbacks: see below for description.
80 * * ipfw_add_table_algo / ipfw_del_table_algo has to be called
82 * Callbacks description:
84 * -init: request to initialize new table instance.
85 * typedef int (ta_init)(struct ip_fw_chain *ch, void **ta_state,
86 * struct table_info *ti, char *data, uint8_t tflags);
87 * MANDATORY, unlocked. (M_WAITOK). Returns 0 on success.
89 * Allocate all structures needed for normal operations.
90 * * Caller may want to parse @data for some algo-specific
91 * options provided by userland.
92 * * Caller may want to save configuration state pointer to @ta_state
93 * * Caller needs to save desired runtime structure pointer(s)
94 * inside @ti fields. Note that it is not correct to save
95 * @ti pointer at this moment. Use -change_ti hook for that.
96 * * Caller has to fill in ti->lookup to appropriate function
101 * -destroy: request to destroy table instance.
102 * typedef void (ta_destroy)(void *ta_state, struct table_info *ti);
103 * MANDATORY, unlocked. (M_WAITOK).
105 * Frees all table entries and all tables structures allocated by -init.
109 * -prepare_add: request to allocate state for adding new entry.
110 * typedef int (ta_prepare_add)(struct ip_fw_chain *ch, struct tentry_info *tei,
112 * MANDATORY, unlocked. (M_WAITOK). Returns 0 on success.
114 * Allocates state and fills it in with all necessary data (EXCEPT value)
115 * from @tei to minimize operations needed to be done under WLOCK.
116 * "value" field has to be copied to new entry in @add callback.
117 * Buffer ta_buf of size ta->ta_buf_sz may be used to store
122 * -prepare_del: request to set state for deleting existing entry.
123 * typedef int (ta_prepare_del)(struct ip_fw_chain *ch, struct tentry_info *tei,
125 * MANDATORY, locked, UH. (M_NOWAIT). Returns 0 on success.
127 * Buffer ta_buf of size ta->ta_buf_sz may be used to store
128 * allocated state. Caller should use on-stack ta_buf allocation
129 * instead of doing malloc().
133 * -add: request to insert new entry into runtime/config structures.
134 * typedef int (ta_add)(void *ta_state, struct table_info *ti,
135 * struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
136 * MANDATORY, UH+WLOCK. (M_NOWAIT). Returns 0 on success.
138 * Insert new entry using previously-allocated state in @ta_buf.
139 * * @tei may have the following flags:
140 * TEI_FLAGS_UPDATE: request to add or update entry.
141 * TEI_FLAGS_DONTADD: request to update (but not add) entry.
142 * * Caller is required to do the following:
143 * copy real entry value from @tei
144 * entry added: return 0, set 1 to @pnum
145 * entry updated: return 0, store 0 to @pnum, store old value in @tei,
146 * add TEI_FLAGS_UPDATED flag to @tei.
147 * entry exists: return EEXIST
148 * entry not found: return ENOENT
149 * other error: return non-zero error code.
153 * -del: request to delete existing entry from runtime/config structures.
154 * typedef int (ta_del)(void *ta_state, struct table_info *ti,
155 * struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
156 * MANDATORY, UH+WLOCK. (M_NOWAIT). Returns 0 on success.
158 * Delete entry using previously set up in @ta_buf.
159 * * Caller is required to do the following:
160 * entry deleted: return 0, set 1 to @pnum, store old value in @tei.
161 * entry not found: return ENOENT
162 * other error: return non-zero error code.
166 * -flush_entry: flush entry state created by -prepare_add / -del / others
167 * typedef void (ta_flush_entry)(struct ip_fw_chain *ch,
168 * struct tentry_info *tei, void *ta_buf);
169 * MANDATORY, may be locked. (M_NOWAIT).
171 * Delete state allocated by:
172 * -prepare_add (-add returned EEXIST|UPDATED)
173 * -prepare_del (if any)
175 * * Caller is required to handle empty @ta_buf correctly.
178 * -find_tentry: finds entry specified by key @tei
179 * typedef int ta_find_tentry(void *ta_state, struct table_info *ti,
180 * ipfw_obj_tentry *tent);
181 * OPTIONAL, locked (UH). (M_NOWAIT). Returns 0 on success.
183 * Finds entry specified by given key.
184 * * Caller is required to do the following:
185 * entry found: returns 0, export entry to @tent
186 * entry not found: returns ENOENT
189 * -need_modify: checks if @ti has enough space to hold another @count items.
190 * typedef int (ta_need_modify)(void *ta_state, struct table_info *ti,
191 * uint32_t count, uint64_t *pflags);
192 * OPTIONAL, locked (UH). (M_NOWAIT). Returns 0 if has.
194 * Checks if given table has enough space to add @count items without
195 * resize. Caller may use @pflags to store desired modification data.
199 * -prepare_mod: allocate structures for table modification.
200 * typedef int (ta_prepare_mod)(void *ta_buf, uint64_t *pflags);
201 * OPTIONAL(need_modify), unlocked. (M_WAITOK). Returns 0 on success.
203 * Allocate all needed state for table modification. Caller
204 * should use `struct mod_item` to store new state in @ta_buf.
205 * Up to TA_BUF_SZ (128 bytes) can be stored in @ta_buf.
209 * -fill_mod: copy some data to new state/
210 * typedef int (ta_fill_mod)(void *ta_state, struct table_info *ti,
211 * void *ta_buf, uint64_t *pflags);
212 * OPTIONAL(need_modify), locked (UH). (M_NOWAIT). Returns 0 on success.
214 * Copy as much data as we can to minimize changes under WLOCK.
215 * For example, array can be merged inside this callback.
219 * -modify: perform final modification.
220 * typedef void (ta_modify)(void *ta_state, struct table_info *ti,
221 * void *ta_buf, uint64_t pflags);
222 * OPTIONAL(need_modify), locked (UH+WLOCK). (M_NOWAIT).
224 * Performs all changes necessary to switch to new structures.
225 * * Caller should save old pointers to @ta_buf storage.
229 * -flush_mod: flush table modification state.
230 * typedef void (ta_flush_mod)(void *ta_buf);
231 * OPTIONAL(need_modify), unlocked. (M_WAITOK).
233 * Performs flush for the following:
234 * - prepare_mod (modification was not necessary)
235 * - modify (for the old state)
239 * -change_gi: monitor table info pointer changes
240 * typedef void (ta_change_ti)(void *ta_state, struct table_info *ti);
241 * OPTIONAL, locked (UH). (M_NOWAIT).
243 * Called on @ti pointer changed. Called immediately after -init
244 * to set initial state.
248 * -foreach: calls @f for each table entry
249 * typedef void ta_foreach(void *ta_state, struct table_info *ti,
250 * ta_foreach_f *f, void *arg);
251 * MANDATORY, locked(UH). (M_NOWAIT).
253 * Runs callback with specified argument for each table entry,
254 * Typically used for dumping table entries.
258 * -dump_tentry: dump table entry in current @tentry format.
259 * typedef int ta_dump_tentry(void *ta_state, struct table_info *ti, void *e,
260 * ipfw_obj_tentry *tent);
261 * MANDATORY, locked(UH). (M_NOWAIT). Returns 0 on success.
263 * Dumps entry @e to @tent.
266 * -print_config: prints custom algorithm options into buffer.
267 * typedef void (ta_print_config)(void *ta_state, struct table_info *ti,
268 * char *buf, size_t bufsize);
269 * OPTIONAL. locked(UH). (M_NOWAIT).
271 * Prints custom algorithm options in the format suitable to pass
272 * back to -init callback.
276 * -dump_tinfo: dumps algo-specific info.
277 * typedef void ta_dump_tinfo(void *ta_state, struct table_info *ti,
278 * ipfw_ta_tinfo *tinfo);
279 * OPTIONAL. locked(UH). (M_NOWAIT).
281 * Dumps options like items size/hash size, etc.
284 MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
287 * Utility structures/functions common to more than one algo
297 static int badd(const void *key, void *item, void *base, size_t nmemb,
298 size_t size, int (*compar) (const void *, const void *));
299 static int bdel(const void *key, void *base, size_t nmemb, size_t size,
300 int (*compar) (const void *, const void *));
304 * ADDR implementation using radix
309 * The radix code expects addr and mask to be array of bytes,
310 * with the first byte being the length of the array. rn_inithead
311 * is called with the offset in bits of the lookup key within the
312 * array. If we use a sockaddr_in as the underlying type,
313 * sin_len is conveniently located at offset 0, sin_addr is at
314 * offset 4 and normally aligned.
315 * But for portability, let's avoid assumption and make the code explicit
317 #define KEY_LEN(v) *((uint8_t *)&(v))
319 * Do not require radix to compare more than actual IPv4/IPv6 address
321 #define KEY_LEN_INET (offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))
322 #define KEY_LEN_INET6 (offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr))
324 #define OFF_LEN_INET (8 * offsetof(struct sockaddr_in, sin_addr))
325 #define OFF_LEN_INET6 (8 * offsetof(struct sa_in6, sin6_addr))
327 struct radix_addr_entry {
328 struct radix_node rn[2];
329 struct sockaddr_in addr;
338 struct in6_addr sin6_addr;
341 struct radix_addr_xentry {
342 struct radix_node rn[2];
349 struct radix_node_head *head4;
350 struct radix_node_head *head6;
358 struct sockaddr *addr_ptr;
359 struct sockaddr *mask_ptr;
362 struct sockaddr_in sa;
363 struct sockaddr_in ma;
372 static int ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
374 static int ta_init_radix(struct ip_fw_chain *ch, void **ta_state,
375 struct table_info *ti, char *data, uint8_t tflags);
376 static int flush_radix_entry(struct radix_node *rn, void *arg);
377 static void ta_destroy_radix(void *ta_state, struct table_info *ti);
378 static void ta_dump_radix_tinfo(void *ta_state, struct table_info *ti,
379 ipfw_ta_tinfo *tinfo);
380 static int ta_dump_radix_tentry(void *ta_state, struct table_info *ti,
381 void *e, ipfw_obj_tentry *tent);
382 static int ta_find_radix_tentry(void *ta_state, struct table_info *ti,
383 ipfw_obj_tentry *tent);
384 static void ta_foreach_radix(void *ta_state, struct table_info *ti,
385 ta_foreach_f *f, void *arg);
386 static void tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
387 struct sockaddr *ma, int *set_mask);
388 static int ta_prepare_add_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
390 static int ta_add_radix(void *ta_state, struct table_info *ti,
391 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
392 static int ta_prepare_del_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
394 static int ta_del_radix(void *ta_state, struct table_info *ti,
395 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
396 static void ta_flush_radix_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
398 static int ta_need_modify_radix(void *ta_state, struct table_info *ti,
399 uint32_t count, uint64_t *pflags);
402 ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
405 struct radix_node_head *rnh;
407 if (keylen == sizeof(in_addr_t)) {
408 struct radix_addr_entry *ent;
409 struct sockaddr_in sa;
410 KEY_LEN(sa) = KEY_LEN_INET;
411 sa.sin_addr.s_addr = *((in_addr_t *)key);
412 rnh = (struct radix_node_head *)ti->state;
413 ent = (struct radix_addr_entry *)(rnh->rnh_matchaddr(&sa, &rnh->rh));
419 struct radix_addr_xentry *xent;
421 KEY_LEN(sa6) = KEY_LEN_INET6;
422 memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
423 rnh = (struct radix_node_head *)ti->xstate;
424 xent = (struct radix_addr_xentry *)(rnh->rnh_matchaddr(&sa6, &rnh->rh));
438 ta_init_radix(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
439 char *data, uint8_t tflags)
441 struct radix_cfg *cfg;
443 if (!rn_inithead(&ti->state, OFF_LEN_INET))
445 if (!rn_inithead(&ti->xstate, OFF_LEN_INET6)) {
446 rn_detachhead(&ti->state);
450 cfg = malloc(sizeof(struct radix_cfg), M_IPFW, M_WAITOK | M_ZERO);
453 ti->lookup = ta_lookup_radix;
459 flush_radix_entry(struct radix_node *rn, void *arg)
461 struct radix_node_head * const rnh = arg;
462 struct radix_addr_entry *ent;
464 ent = (struct radix_addr_entry *)
465 rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, &rnh->rh);
467 free(ent, M_IPFW_TBL);
472 ta_destroy_radix(void *ta_state, struct table_info *ti)
474 struct radix_cfg *cfg;
475 struct radix_node_head *rnh;
477 cfg = (struct radix_cfg *)ta_state;
479 rnh = (struct radix_node_head *)(ti->state);
480 rnh->rnh_walktree(&rnh->rh, flush_radix_entry, rnh);
481 rn_detachhead(&ti->state);
483 rnh = (struct radix_node_head *)(ti->xstate);
484 rnh->rnh_walktree(&rnh->rh, flush_radix_entry, rnh);
485 rn_detachhead(&ti->xstate);
491 * Provide algo-specific table info
494 ta_dump_radix_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
496 struct radix_cfg *cfg;
498 cfg = (struct radix_cfg *)ta_state;
500 tinfo->flags = IPFW_TATFLAGS_AFDATA | IPFW_TATFLAGS_AFITEM;
501 tinfo->taclass4 = IPFW_TACLASS_RADIX;
502 tinfo->count4 = cfg->count4;
503 tinfo->itemsize4 = sizeof(struct radix_addr_entry);
504 tinfo->taclass6 = IPFW_TACLASS_RADIX;
505 tinfo->count6 = cfg->count6;
506 tinfo->itemsize6 = sizeof(struct radix_addr_xentry);
510 ta_dump_radix_tentry(void *ta_state, struct table_info *ti, void *e,
511 ipfw_obj_tentry *tent)
513 struct radix_addr_entry *n;
515 struct radix_addr_xentry *xn;
518 n = (struct radix_addr_entry *)e;
520 /* Guess IPv4/IPv6 radix by sockaddr family */
521 if (n->addr.sin_family == AF_INET) {
522 tent->k.addr.s_addr = n->addr.sin_addr.s_addr;
523 tent->masklen = n->masklen;
524 tent->subtype = AF_INET;
525 tent->v.kidx = n->value;
528 xn = (struct radix_addr_xentry *)e;
529 memcpy(&tent->k, &xn->addr6.sin6_addr, sizeof(struct in6_addr));
530 tent->masklen = xn->masklen;
531 tent->subtype = AF_INET6;
532 tent->v.kidx = xn->value;
540 ta_find_radix_tentry(void *ta_state, struct table_info *ti,
541 ipfw_obj_tentry *tent)
543 struct radix_node_head *rnh;
547 if (tent->subtype == AF_INET) {
548 struct sockaddr_in sa;
549 KEY_LEN(sa) = KEY_LEN_INET;
550 sa.sin_addr.s_addr = tent->k.addr.s_addr;
551 rnh = (struct radix_node_head *)ti->state;
552 e = rnh->rnh_matchaddr(&sa, &rnh->rh);
555 KEY_LEN(sa6) = KEY_LEN_INET6;
556 memcpy(&sa6.sin6_addr, &tent->k.addr6, sizeof(struct in6_addr));
557 rnh = (struct radix_node_head *)ti->xstate;
558 e = rnh->rnh_matchaddr(&sa6, &rnh->rh);
562 ta_dump_radix_tentry(ta_state, ti, e, tent);
570 ta_foreach_radix(void *ta_state, struct table_info *ti, ta_foreach_f *f,
573 struct radix_node_head *rnh;
575 rnh = (struct radix_node_head *)(ti->state);
576 rnh->rnh_walktree(&rnh->rh, (walktree_f_t *)f, arg);
578 rnh = (struct radix_node_head *)(ti->xstate);
579 rnh->rnh_walktree(&rnh->rh, (walktree_f_t *)f, arg);
584 static inline void ipv6_writemask(struct in6_addr *addr6, uint8_t mask);
587 ipv6_writemask(struct in6_addr *addr6, uint8_t mask)
591 for (cp = (uint32_t *)addr6; mask >= 32; mask -= 32)
594 *cp = htonl(mask ? ~((1 << (32 - mask)) - 1) : 0);
599 tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
600 struct sockaddr *ma, int *set_mask)
604 struct sockaddr_in *addr, *mask;
607 struct sa_in6 *addr6, *mask6;
613 if (tei->subtype == AF_INET) {
615 addr = (struct sockaddr_in *)sa;
616 mask = (struct sockaddr_in *)ma;
617 /* Set 'total' structure length */
618 KEY_LEN(*addr) = KEY_LEN_INET;
619 KEY_LEN(*mask) = KEY_LEN_INET;
620 addr->sin_family = AF_INET;
621 mask->sin_addr.s_addr =
622 htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
623 a4 = *((in_addr_t *)tei->paddr);
624 addr->sin_addr.s_addr = a4 & mask->sin_addr.s_addr;
631 } else if (tei->subtype == AF_INET6) {
633 addr6 = (struct sa_in6 *)sa;
634 mask6 = (struct sa_in6 *)ma;
635 /* Set 'total' structure length */
636 KEY_LEN(*addr6) = KEY_LEN_INET6;
637 KEY_LEN(*mask6) = KEY_LEN_INET6;
638 addr6->sin6_family = AF_INET6;
639 ipv6_writemask(&mask6->sin6_addr, mlen);
640 memcpy(&addr6->sin6_addr, tei->paddr, sizeof(struct in6_addr));
641 APPLY_MASK(&addr6->sin6_addr, &mask6->sin6_addr);
651 ta_prepare_add_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
654 struct ta_buf_radix *tb;
655 struct radix_addr_entry *ent;
657 struct radix_addr_xentry *xent;
659 struct sockaddr *addr, *mask;
662 tb = (struct ta_buf_radix *)ta_buf;
667 if (tei->subtype == AF_INET) {
671 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
674 addr = (struct sockaddr *)&ent->addr;
675 mask = (struct sockaddr *)&tb->addr.a4.ma;
679 } else if (tei->subtype == AF_INET6) {
683 xent = malloc(sizeof(*xent), M_IPFW_TBL, M_WAITOK | M_ZERO);
684 xent->masklen = mlen;
686 addr = (struct sockaddr *)&xent->addr6;
687 mask = (struct sockaddr *)&tb->addr.a6.ma;
691 /* Unknown CIDR type */
695 tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
705 ta_add_radix(void *ta_state, struct table_info *ti, struct tentry_info *tei,
706 void *ta_buf, uint32_t *pnum)
708 struct radix_cfg *cfg;
709 struct radix_node_head *rnh;
710 struct radix_node *rn;
711 struct ta_buf_radix *tb;
712 uint32_t *old_value, value;
714 cfg = (struct radix_cfg *)ta_state;
715 tb = (struct ta_buf_radix *)ta_buf;
717 /* Save current entry value from @tei */
718 if (tei->subtype == AF_INET) {
720 ((struct radix_addr_entry *)tb->ent_ptr)->value = tei->value;
723 ((struct radix_addr_xentry *)tb->ent_ptr)->value = tei->value;
726 /* Search for an entry first */
727 rn = rnh->rnh_lookup(tb->addr_ptr, tb->mask_ptr, &rnh->rh);
729 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
731 /* Record already exists. Update value if we're asked to */
732 if (tei->subtype == AF_INET)
733 old_value = &((struct radix_addr_entry *)rn)->value;
735 old_value = &((struct radix_addr_xentry *)rn)->value;
738 *old_value = tei->value;
741 /* Indicate that update has happened instead of addition */
742 tei->flags |= TEI_FLAGS_UPDATED;
748 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
751 rn = rnh->rnh_addaddr(tb->addr_ptr, tb->mask_ptr, &rnh->rh,tb->ent_ptr);
757 if (tei->subtype == AF_INET)
768 ta_prepare_del_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
771 struct ta_buf_radix *tb;
772 struct sockaddr *addr, *mask;
775 tb = (struct ta_buf_radix *)ta_buf;
780 if (tei->subtype == AF_INET) {
784 addr = (struct sockaddr *)&tb->addr.a4.sa;
785 mask = (struct sockaddr *)&tb->addr.a4.ma;
787 } else if (tei->subtype == AF_INET6) {
791 addr = (struct sockaddr *)&tb->addr.a6.sa;
792 mask = (struct sockaddr *)&tb->addr.a6.ma;
797 tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
806 ta_del_radix(void *ta_state, struct table_info *ti, struct tentry_info *tei,
807 void *ta_buf, uint32_t *pnum)
809 struct radix_cfg *cfg;
810 struct radix_node_head *rnh;
811 struct radix_node *rn;
812 struct ta_buf_radix *tb;
814 cfg = (struct radix_cfg *)ta_state;
815 tb = (struct ta_buf_radix *)ta_buf;
817 if (tei->subtype == AF_INET)
822 rn = rnh->rnh_deladdr(tb->addr_ptr, tb->mask_ptr, &rnh->rh);
827 /* Save entry value to @tei */
828 if (tei->subtype == AF_INET)
829 tei->value = ((struct radix_addr_entry *)rn)->value;
831 tei->value = ((struct radix_addr_xentry *)rn)->value;
835 if (tei->subtype == AF_INET)
845 ta_flush_radix_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
848 struct ta_buf_radix *tb;
850 tb = (struct ta_buf_radix *)ta_buf;
852 if (tb->ent_ptr != NULL)
853 free(tb->ent_ptr, M_IPFW_TBL);
857 ta_need_modify_radix(void *ta_state, struct table_info *ti, uint32_t count,
862 * radix does not require additional memory allocations
863 * other than nodes itself. Adding new masks to the tree do
864 * but we don't have any API to call (and we don't known which
870 struct table_algo addr_radix = {
871 .name = "addr:radix",
872 .type = IPFW_TABLE_ADDR,
873 .flags = TA_FLAG_DEFAULT,
874 .ta_buf_size = sizeof(struct ta_buf_radix),
875 .init = ta_init_radix,
876 .destroy = ta_destroy_radix,
877 .prepare_add = ta_prepare_add_radix,
878 .prepare_del = ta_prepare_del_radix,
881 .flush_entry = ta_flush_radix_entry,
882 .foreach = ta_foreach_radix,
883 .dump_tentry = ta_dump_radix_tentry,
884 .find_tentry = ta_find_radix_tentry,
885 .dump_tinfo = ta_dump_radix_tinfo,
886 .need_modify = ta_need_modify_radix,
895 * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
898 * inv.mask4: 32 - mask
900 * 1) _slow lookup: mask
901 * 2) _aligned: (128 - mask) / 8
912 SLIST_HEAD(chashbhead, chashentry);
915 struct chashbhead *head4;
916 struct chashbhead *head6;
926 SLIST_ENTRY(chashentry) next;
930 uint32_t a4; /* Host format */
931 struct in6_addr a6; /* Network format */
938 struct chashentry ent;
942 static __inline uint32_t hash_ip(uint32_t addr, int hsize);
945 static __inline uint32_t hash_ip6(struct in6_addr *addr6, int hsize);
946 static __inline uint16_t hash_ip64(struct in6_addr *addr6, int hsize);
947 static __inline uint32_t hash_ip6_slow(struct in6_addr *addr6, void *key,
948 int mask, int hsize);
949 static __inline uint32_t hash_ip6_al(struct in6_addr *addr6, void *key, int mask,
952 static int ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
954 static int ta_lookup_chash_aligned(struct table_info *ti, void *key,
955 uint32_t keylen, uint32_t *val);
956 static int ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
958 static int chash_parse_opts(struct chash_cfg *cfg, char *data);
959 static void ta_print_chash_config(void *ta_state, struct table_info *ti,
960 char *buf, size_t bufsize);
961 static int ta_log2(uint32_t v);
962 static int ta_init_chash(struct ip_fw_chain *ch, void **ta_state,
963 struct table_info *ti, char *data, uint8_t tflags);
964 static void ta_destroy_chash(void *ta_state, struct table_info *ti);
965 static void ta_dump_chash_tinfo(void *ta_state, struct table_info *ti,
966 ipfw_ta_tinfo *tinfo);
967 static int ta_dump_chash_tentry(void *ta_state, struct table_info *ti,
968 void *e, ipfw_obj_tentry *tent);
969 static uint32_t hash_ent(struct chashentry *ent, int af, int mlen,
971 static int tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent);
972 static int ta_find_chash_tentry(void *ta_state, struct table_info *ti,
973 ipfw_obj_tentry *tent);
974 static void ta_foreach_chash(void *ta_state, struct table_info *ti,
975 ta_foreach_f *f, void *arg);
976 static int ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
978 static int ta_add_chash(void *ta_state, struct table_info *ti,
979 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
980 static int ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
982 static int ta_del_chash(void *ta_state, struct table_info *ti,
983 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
984 static void ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
986 static int ta_need_modify_chash(void *ta_state, struct table_info *ti,
987 uint32_t count, uint64_t *pflags);
988 static int ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags);
989 static int ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
991 static void ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
993 static void ta_flush_mod_chash(void *ta_buf);
997 static __inline uint32_t
998 hash_ip(uint32_t addr, int hsize)
1001 return (addr % (hsize - 1));
1006 static __inline uint32_t
1007 hash_ip6(struct in6_addr *addr6, int hsize)
1011 i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1] ^
1012 addr6->s6_addr32[2] ^ addr6->s6_addr32[3];
1014 return (i % (hsize - 1));
1018 static __inline uint16_t
1019 hash_ip64(struct in6_addr *addr6, int hsize)
1023 i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1];
1025 return (i % (hsize - 1));
1029 static __inline uint32_t
1030 hash_ip6_slow(struct in6_addr *addr6, void *key, int mask, int hsize)
1032 struct in6_addr mask6;
1034 ipv6_writemask(&mask6, mask);
1035 memcpy(addr6, key, sizeof(struct in6_addr));
1036 APPLY_MASK(addr6, &mask6);
1037 return (hash_ip6(addr6, hsize));
1040 static __inline uint32_t
1041 hash_ip6_al(struct in6_addr *addr6, void *key, int mask, int hsize)
1045 paddr = (uint64_t *)addr6;
1048 memcpy(addr6, key, mask);
1049 return (hash_ip6(addr6, hsize));
1054 ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
1057 struct chashbhead *head;
1058 struct chashentry *ent;
1059 uint16_t hash, hsize;
1062 if (keylen == sizeof(in_addr_t)) {
1064 head = (struct chashbhead *)ti->state;
1065 imask = ti->data >> 24;
1066 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1068 a = ntohl(*((in_addr_t *)key));
1070 hash = hash_ip(a, hsize);
1071 SLIST_FOREACH(ent, &head[hash], next) {
1072 if (ent->a.a4 == a) {
1080 /* IPv6: worst scenario: non-round mask */
1081 struct in6_addr addr6;
1082 head = (struct chashbhead *)ti->xstate;
1083 imask = (ti->data & 0xFF0000) >> 16;
1084 hsize = 1 << (ti->data & 0xFF);
1085 hash = hash_ip6_slow(&addr6, key, imask, hsize);
1086 SLIST_FOREACH(ent, &head[hash], next) {
1087 if (memcmp(&ent->a.a6, &addr6, 16) == 0) {
1099 ta_lookup_chash_aligned(struct table_info *ti, void *key, uint32_t keylen,
1102 struct chashbhead *head;
1103 struct chashentry *ent;
1104 uint16_t hash, hsize;
1107 if (keylen == sizeof(in_addr_t)) {
1109 head = (struct chashbhead *)ti->state;
1110 imask = ti->data >> 24;
1111 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1113 a = ntohl(*((in_addr_t *)key));
1115 hash = hash_ip(a, hsize);
1116 SLIST_FOREACH(ent, &head[hash], next) {
1117 if (ent->a.a4 == a) {
1125 /* IPv6: aligned to 8bit mask */
1126 struct in6_addr addr6;
1127 uint64_t *paddr, *ptmp;
1128 head = (struct chashbhead *)ti->xstate;
1129 imask = (ti->data & 0xFF0000) >> 16;
1130 hsize = 1 << (ti->data & 0xFF);
1132 hash = hash_ip6_al(&addr6, key, imask, hsize);
1133 paddr = (uint64_t *)&addr6;
1134 SLIST_FOREACH(ent, &head[hash], next) {
1135 ptmp = (uint64_t *)&ent->a.a6;
1136 if (paddr[0] == ptmp[0] && paddr[1] == ptmp[1]) {
1148 ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
1151 struct chashbhead *head;
1152 struct chashentry *ent;
1153 uint16_t hash, hsize;
1156 if (keylen == sizeof(in_addr_t)) {
1158 head = (struct chashbhead *)ti->state;
1159 imask = ti->data >> 24;
1160 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1162 a = ntohl(*((in_addr_t *)key));
1164 hash = hash_ip(a, hsize);
1165 SLIST_FOREACH(ent, &head[hash], next) {
1166 if (ent->a.a4 == a) {
1175 uint64_t a6, *paddr;
1176 head = (struct chashbhead *)ti->xstate;
1177 paddr = (uint64_t *)key;
1178 hsize = 1 << (ti->data & 0xFF);
1180 hash = hash_ip64((struct in6_addr *)key, hsize);
1181 SLIST_FOREACH(ent, &head[hash], next) {
1182 paddr = (uint64_t *)&ent->a.a6;
1195 chash_parse_opts(struct chash_cfg *cfg, char *data)
1197 char *pdel, *pend, *s;
1205 if ((pdel = strchr(data, ' ')) == NULL)
1207 while (*pdel == ' ')
1209 if (strncmp(pdel, "masks=", 6) != 0)
1211 if ((s = strchr(pdel, ' ')) != NULL)
1215 /* Need /XX[,/YY] */
1218 mask4 = strtol(pdel, &pend, 10);
1224 mask6 = strtol(pdel, &pend, 10);
1227 } else if (*pend != '\0')
1230 if (mask4 < 0 || mask4 > 32 || mask6 < 0 || mask6 > 128)
1240 ta_print_chash_config(void *ta_state, struct table_info *ti, char *buf,
1243 struct chash_cfg *cfg;
1245 cfg = (struct chash_cfg *)ta_state;
1247 if (cfg->mask4 != 32 || cfg->mask6 != 128)
1248 snprintf(buf, bufsize, "%s masks=/%d,/%d", "addr:hash",
1249 cfg->mask4, cfg->mask6);
1251 snprintf(buf, bufsize, "%s", "addr:hash");
1268 * We assume 'data' to be either NULL or the following format:
1269 * 'addr:hash [masks=/32[,/128]]'
1272 ta_init_chash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
1273 char *data, uint8_t tflags)
1277 struct chash_cfg *cfg;
1279 cfg = malloc(sizeof(struct chash_cfg), M_IPFW, M_WAITOK | M_ZERO);
1284 if ((error = chash_parse_opts(cfg, data)) != 0) {
1292 cfg->head4 = malloc(sizeof(struct chashbhead) * cfg->size4, M_IPFW,
1294 cfg->head6 = malloc(sizeof(struct chashbhead) * cfg->size6, M_IPFW,
1296 for (i = 0; i < cfg->size4; i++)
1297 SLIST_INIT(&cfg->head4[i]);
1298 for (i = 0; i < cfg->size6; i++)
1299 SLIST_INIT(&cfg->head6[i]);
1303 ti->state = cfg->head4;
1304 ti->xstate = cfg->head6;
1306 /* Store data depending on v6 mask length */
1307 hsize = ta_log2(cfg->size4) << 8 | ta_log2(cfg->size6);
1308 if (cfg->mask6 == 64) {
1309 ti->data = (32 - cfg->mask4) << 24 | (128 - cfg->mask6) << 16|
1311 ti->lookup = ta_lookup_chash_64;
1312 } else if ((cfg->mask6 % 8) == 0) {
1313 ti->data = (32 - cfg->mask4) << 24 |
1314 cfg->mask6 << 13 | hsize;
1315 ti->lookup = ta_lookup_chash_aligned;
1317 /* don't do that! */
1318 ti->data = (32 - cfg->mask4) << 24 |
1319 cfg->mask6 << 16 | hsize;
1320 ti->lookup = ta_lookup_chash_slow;
1327 ta_destroy_chash(void *ta_state, struct table_info *ti)
1329 struct chash_cfg *cfg;
1330 struct chashentry *ent, *ent_next;
1333 cfg = (struct chash_cfg *)ta_state;
1335 for (i = 0; i < cfg->size4; i++)
1336 SLIST_FOREACH_SAFE(ent, &cfg->head4[i], next, ent_next)
1337 free(ent, M_IPFW_TBL);
1339 for (i = 0; i < cfg->size6; i++)
1340 SLIST_FOREACH_SAFE(ent, &cfg->head6[i], next, ent_next)
1341 free(ent, M_IPFW_TBL);
1343 free(cfg->head4, M_IPFW);
1344 free(cfg->head6, M_IPFW);
1350 ta_dump_chash_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
1352 struct chash_cfg *cfg;
1354 cfg = (struct chash_cfg *)ta_state;
1356 tinfo->flags = IPFW_TATFLAGS_AFDATA | IPFW_TATFLAGS_AFITEM;
1357 tinfo->taclass4 = IPFW_TACLASS_HASH;
1358 tinfo->size4 = cfg->size4;
1359 tinfo->count4 = cfg->items4;
1360 tinfo->itemsize4 = sizeof(struct chashentry);
1361 tinfo->taclass6 = IPFW_TACLASS_HASH;
1362 tinfo->size6 = cfg->size6;
1363 tinfo->count6 = cfg->items6;
1364 tinfo->itemsize6 = sizeof(struct chashentry);
1368 ta_dump_chash_tentry(void *ta_state, struct table_info *ti, void *e,
1369 ipfw_obj_tentry *tent)
1371 struct chash_cfg *cfg;
1372 struct chashentry *ent;
1374 cfg = (struct chash_cfg *)ta_state;
1375 ent = (struct chashentry *)e;
1377 if (ent->type == AF_INET) {
1378 tent->k.addr.s_addr = htonl(ent->a.a4 << (32 - cfg->mask4));
1379 tent->masklen = cfg->mask4;
1380 tent->subtype = AF_INET;
1381 tent->v.kidx = ent->value;
1384 memcpy(&tent->k, &ent->a.a6, sizeof(struct in6_addr));
1385 tent->masklen = cfg->mask6;
1386 tent->subtype = AF_INET6;
1387 tent->v.kidx = ent->value;
1395 hash_ent(struct chashentry *ent, int af, int mlen, uint32_t size)
1401 if (af == AF_INET) {
1403 hash = hash_ip(ent->a.a4, size);
1408 hash = hash_ip64(&ent->a.a6, size);
1410 hash = hash_ip6(&ent->a.a6, size);
1418 tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent)
1422 struct in6_addr mask6;
1426 mlen = tei->masklen;
1428 if (tei->subtype == AF_INET) {
1432 ent->type = AF_INET;
1434 /* Calculate masked address */
1435 ent->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1438 } else if (tei->subtype == AF_INET6) {
1442 ent->type = AF_INET6;
1444 ipv6_writemask(&mask6, mlen);
1445 memcpy(&ent->a.a6, tei->paddr, sizeof(struct in6_addr));
1446 APPLY_MASK(&ent->a.a6, &mask6);
1449 /* Unknown CIDR type */
1457 ta_find_chash_tentry(void *ta_state, struct table_info *ti,
1458 ipfw_obj_tentry *tent)
1460 struct chash_cfg *cfg;
1461 struct chashbhead *head;
1462 struct chashentry ent, *tmp;
1463 struct tentry_info tei;
1467 cfg = (struct chash_cfg *)ta_state;
1469 memset(&ent, 0, sizeof(ent));
1470 memset(&tei, 0, sizeof(tei));
1472 if (tent->subtype == AF_INET) {
1473 tei.paddr = &tent->k.addr;
1474 tei.masklen = cfg->mask4;
1475 tei.subtype = AF_INET;
1477 if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
1481 hash = hash_ent(&ent, AF_INET, cfg->mask4, cfg->size4);
1482 /* Check for existence */
1483 SLIST_FOREACH(tmp, &head[hash], next) {
1484 if (tmp->a.a4 != ent.a.a4)
1487 ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1491 tei.paddr = &tent->k.addr6;
1492 tei.masklen = cfg->mask6;
1493 tei.subtype = AF_INET6;
1495 if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
1499 hash = hash_ent(&ent, AF_INET6, cfg->mask6, cfg->size6);
1500 /* Check for existence */
1501 SLIST_FOREACH(tmp, &head[hash], next) {
1502 if (memcmp(&tmp->a.a6, &ent.a.a6, 16) != 0)
1504 ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1513 ta_foreach_chash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
1516 struct chash_cfg *cfg;
1517 struct chashentry *ent, *ent_next;
1520 cfg = (struct chash_cfg *)ta_state;
1522 for (i = 0; i < cfg->size4; i++)
1523 SLIST_FOREACH_SAFE(ent, &cfg->head4[i], next, ent_next)
1526 for (i = 0; i < cfg->size6; i++)
1527 SLIST_FOREACH_SAFE(ent, &cfg->head6[i], next, ent_next)
1532 ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1535 struct ta_buf_chash *tb;
1536 struct chashentry *ent;
1539 tb = (struct ta_buf_chash *)ta_buf;
1541 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1543 error = tei_to_chash_ent(tei, ent);
1545 free(ent, M_IPFW_TBL);
1554 ta_add_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1555 void *ta_buf, uint32_t *pnum)
1557 struct chash_cfg *cfg;
1558 struct chashbhead *head;
1559 struct chashentry *ent, *tmp;
1560 struct ta_buf_chash *tb;
1562 uint32_t hash, value;
1564 cfg = (struct chash_cfg *)ta_state;
1565 tb = (struct ta_buf_chash *)ta_buf;
1566 ent = (struct chashentry *)tb->ent_ptr;
1570 /* Read current value from @tei */
1571 ent->value = tei->value;
1573 /* Read cuurrent value */
1574 if (tei->subtype == AF_INET) {
1575 if (tei->masklen != cfg->mask4)
1578 hash = hash_ent(ent, AF_INET, cfg->mask4, cfg->size4);
1580 /* Check for existence */
1581 SLIST_FOREACH(tmp, &head[hash], next) {
1582 if (tmp->a.a4 == ent->a.a4) {
1588 if (tei->masklen != cfg->mask6)
1591 hash = hash_ent(ent, AF_INET6, cfg->mask6, cfg->size6);
1592 /* Check for existence */
1593 SLIST_FOREACH(tmp, &head[hash], next) {
1594 if (memcmp(&tmp->a.a6, &ent->a.a6, 16) == 0) {
1602 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1604 /* Record already exists. Update value if we're asked to */
1606 tmp->value = tei->value;
1608 /* Indicate that update has happened instead of addition */
1609 tei->flags |= TEI_FLAGS_UPDATED;
1612 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
1614 SLIST_INSERT_HEAD(&head[hash], ent, next);
1618 /* Update counters */
1619 if (tei->subtype == AF_INET)
1629 ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1632 struct ta_buf_chash *tb;
1634 tb = (struct ta_buf_chash *)ta_buf;
1636 return (tei_to_chash_ent(tei, &tb->ent));
1640 ta_del_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1641 void *ta_buf, uint32_t *pnum)
1643 struct chash_cfg *cfg;
1644 struct chashbhead *head;
1645 struct chashentry *tmp, *tmp_next, *ent;
1646 struct ta_buf_chash *tb;
1649 cfg = (struct chash_cfg *)ta_state;
1650 tb = (struct ta_buf_chash *)ta_buf;
1653 if (tei->subtype == AF_INET) {
1654 if (tei->masklen != cfg->mask4)
1657 hash = hash_ent(ent, AF_INET, cfg->mask4, cfg->size4);
1659 SLIST_FOREACH_SAFE(tmp, &head[hash], next, tmp_next) {
1660 if (tmp->a.a4 != ent->a.a4)
1663 SLIST_REMOVE(&head[hash], tmp, chashentry, next);
1666 tei->value = tmp->value;
1671 if (tei->masklen != cfg->mask6)
1674 hash = hash_ent(ent, AF_INET6, cfg->mask6, cfg->size6);
1675 SLIST_FOREACH_SAFE(tmp, &head[hash], next, tmp_next) {
1676 if (memcmp(&tmp->a.a6, &ent->a.a6, 16) != 0)
1679 SLIST_REMOVE(&head[hash], tmp, chashentry, next);
1682 tei->value = tmp->value;
1692 ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1695 struct ta_buf_chash *tb;
1697 tb = (struct ta_buf_chash *)ta_buf;
1699 if (tb->ent_ptr != NULL)
1700 free(tb->ent_ptr, M_IPFW_TBL);
1704 * Hash growing callbacks.
1708 ta_need_modify_chash(void *ta_state, struct table_info *ti, uint32_t count,
1711 struct chash_cfg *cfg;
1715 * Since we don't know exact number of IPv4/IPv6 records in @count,
1716 * ignore non-zero @count value at all. Check current hash sizes
1717 * and return appropriate data.
1720 cfg = (struct chash_cfg *)ta_state;
1723 if (cfg->items4 > cfg->size4 && cfg->size4 < 65536)
1724 data |= (cfg->size4 * 2) << 16;
1725 if (cfg->items6 > cfg->size6 && cfg->size6 < 65536)
1726 data |= cfg->size6 * 2;
1737 * Allocate new, larger chash.
1740 ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags)
1742 struct mod_item *mi;
1743 struct chashbhead *head;
1746 mi = (struct mod_item *)ta_buf;
1748 memset(mi, 0, sizeof(struct mod_item));
1749 mi->size = (*pflags >> 16) & 0xFFFF;
1750 mi->size6 = *pflags & 0xFFFF;
1752 head = malloc(sizeof(struct chashbhead) * mi->size,
1753 M_IPFW, M_WAITOK | M_ZERO);
1754 for (i = 0; i < mi->size; i++)
1755 SLIST_INIT(&head[i]);
1756 mi->main_ptr = head;
1759 if (mi->size6 > 0) {
1760 head = malloc(sizeof(struct chashbhead) * mi->size6,
1761 M_IPFW, M_WAITOK | M_ZERO);
1762 for (i = 0; i < mi->size6; i++)
1763 SLIST_INIT(&head[i]);
1764 mi->main_ptr6 = head;
1771 * Copy data from old runtime array to new one.
1774 ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1778 /* In is not possible to do rehash if we're not holidng WLOCK. */
1783 * Switch old & new arrays.
1786 ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1789 struct mod_item *mi;
1790 struct chash_cfg *cfg;
1791 struct chashbhead *old_head, *new_head;
1792 struct chashentry *ent, *ent_next;
1795 size_t old_size, new_size;
1797 mi = (struct mod_item *)ta_buf;
1798 cfg = (struct chash_cfg *)ta_state;
1800 /* Check which hash we need to grow and do we still need that */
1801 if (mi->size > 0 && cfg->size4 < mi->size) {
1802 new_head = (struct chashbhead *)mi->main_ptr;
1803 new_size = mi->size;
1804 old_size = cfg->size4;
1805 old_head = ti->state;
1809 for (i = 0; i < old_size; i++) {
1810 SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
1811 nhash = hash_ent(ent, af, mlen, new_size);
1812 SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
1816 ti->state = new_head;
1817 cfg->head4 = new_head;
1818 cfg->size4 = mi->size;
1819 mi->main_ptr = old_head;
1822 if (mi->size6 > 0 && cfg->size6 < mi->size6) {
1823 new_head = (struct chashbhead *)mi->main_ptr6;
1824 new_size = mi->size6;
1825 old_size = cfg->size6;
1826 old_head = ti->xstate;
1830 for (i = 0; i < old_size; i++) {
1831 SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
1832 nhash = hash_ent(ent, af, mlen, new_size);
1833 SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
1837 ti->xstate = new_head;
1838 cfg->head6 = new_head;
1839 cfg->size6 = mi->size6;
1840 mi->main_ptr6 = old_head;
1843 /* Update lower 32 bits with new values */
1844 ti->data &= 0xFFFFFFFF00000000;
1845 ti->data |= ta_log2(cfg->size4) << 8 | ta_log2(cfg->size6);
1849 * Free unneded array.
1852 ta_flush_mod_chash(void *ta_buf)
1854 struct mod_item *mi;
1856 mi = (struct mod_item *)ta_buf;
1857 if (mi->main_ptr != NULL)
1858 free(mi->main_ptr, M_IPFW);
1859 if (mi->main_ptr6 != NULL)
1860 free(mi->main_ptr6, M_IPFW);
1863 struct table_algo addr_hash = {
1864 .name = "addr:hash",
1865 .type = IPFW_TABLE_ADDR,
1866 .ta_buf_size = sizeof(struct ta_buf_chash),
1867 .init = ta_init_chash,
1868 .destroy = ta_destroy_chash,
1869 .prepare_add = ta_prepare_add_chash,
1870 .prepare_del = ta_prepare_del_chash,
1871 .add = ta_add_chash,
1872 .del = ta_del_chash,
1873 .flush_entry = ta_flush_chash_entry,
1874 .foreach = ta_foreach_chash,
1875 .dump_tentry = ta_dump_chash_tentry,
1876 .find_tentry = ta_find_chash_tentry,
1877 .print_config = ta_print_chash_config,
1878 .dump_tinfo = ta_dump_chash_tinfo,
1879 .need_modify = ta_need_modify_chash,
1880 .prepare_mod = ta_prepare_mod_chash,
1881 .fill_mod = ta_fill_mod_chash,
1882 .modify = ta_modify_chash,
1883 .flush_mod = ta_flush_mod_chash,
1893 * - sorted array of "struct ifidx" pointed by ti->state.
1894 * Array is allocated with rounding up to IFIDX_CHUNK. Only existing
1895 * interfaces are stored in array, however its allocated size is
1896 * sufficient to hold all table records if needed.
1897 * - current array size is stored in ti->data
1900 * - "struct iftable_cfg" is allocated to store table state (ta_state).
1901 * - All table records are stored inside namedobj instance.
1910 #define DEFAULT_IFIDX_SIZE 64
1915 struct named_object no;
1917 struct iftable_cfg *icfg;
1922 struct iftable_cfg {
1923 struct namedobj_instance *ii;
1924 struct ip_fw_chain *ch;
1925 struct table_info *ti;
1927 size_t size; /* Number of items allocated in array */
1928 size_t count; /* Number of all items */
1929 size_t used; /* Number of items _active_ now */
1934 struct ifentry *ife;
1938 int compare_ifidx(const void *k, const void *v);
1939 static struct ifidx * ifidx_find(struct table_info *ti, void *key);
1940 static int ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
1942 static int ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state,
1943 struct table_info *ti, char *data, uint8_t tflags);
1944 static void ta_change_ti_ifidx(void *ta_state, struct table_info *ti);
1945 static int destroy_ifidx_locked(struct namedobj_instance *ii,
1946 struct named_object *no, void *arg);
1947 static void ta_destroy_ifidx(void *ta_state, struct table_info *ti);
1948 static void ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti,
1949 ipfw_ta_tinfo *tinfo);
1950 static int ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1952 static int ta_add_ifidx(void *ta_state, struct table_info *ti,
1953 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1954 static int ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1956 static int ta_del_ifidx(void *ta_state, struct table_info *ti,
1957 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1958 static void ta_flush_ifidx_entry(struct ip_fw_chain *ch,
1959 struct tentry_info *tei, void *ta_buf);
1960 static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
1961 static int ta_need_modify_ifidx(void *ta_state, struct table_info *ti,
1962 uint32_t count, uint64_t *pflags);
1963 static int ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags);
1964 static int ta_fill_mod_ifidx(void *ta_state, struct table_info *ti,
1965 void *ta_buf, uint64_t *pflags);
1966 static void ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1968 static void ta_flush_mod_ifidx(void *ta_buf);
1969 static int ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
1970 ipfw_obj_tentry *tent);
1971 static int ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
1972 ipfw_obj_tentry *tent);
1973 static int foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
1975 static void ta_foreach_ifidx(void *ta_state, struct table_info *ti,
1976 ta_foreach_f *f, void *arg);
1979 compare_ifidx(const void *k, const void *v)
1981 const struct ifidx *ifidx;
1984 key = *((const uint16_t *)k);
1985 ifidx = (const struct ifidx *)v;
1987 if (key < ifidx->kidx)
1989 else if (key > ifidx->kidx)
1996 * Adds item @item with key @key into ascending-sorted array @base.
1997 * Assumes @base has enough additional storage.
1999 * Returns 1 on success, 0 on duplicate key.
2002 badd(const void *key, void *item, void *base, size_t nmemb,
2003 size_t size, int (*compar) (const void *, const void *))
2005 int min, max, mid, shift, res;
2009 memcpy(base, item, size);
2017 while (min <= max) {
2018 mid = (min + max) / 2;
2019 res = compar(key, (const void *)((caddr_t)base + mid * size));
2029 /* Item not found. */
2030 res = compar(key, (const void *)((caddr_t)base + mid * size));
2036 paddr = (caddr_t)base + shift * size;
2038 memmove(paddr + size, paddr, (nmemb - shift) * size);
2040 memcpy(paddr, item, size);
2046 * Deletes item with key @key from ascending-sorted array @base.
2048 * Returns 1 on success, 0 for non-existent key.
2051 bdel(const void *key, void *base, size_t nmemb, size_t size,
2052 int (*compar) (const void *, const void *))
2057 item = (caddr_t)bsearch(key, base, nmemb, size, compar);
2062 sz = (caddr_t)base + nmemb * size - item;
2065 memmove(item, item + size, sz);
2070 static struct ifidx *
2071 ifidx_find(struct table_info *ti, void *key)
2075 ifi = bsearch(key, ti->state, ti->data, sizeof(struct ifidx),
2082 ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
2087 ifi = ifidx_find(ti, key);
2098 ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2099 char *data, uint8_t tflags)
2101 struct iftable_cfg *icfg;
2103 icfg = malloc(sizeof(struct iftable_cfg), M_IPFW, M_WAITOK | M_ZERO);
2105 icfg->ii = ipfw_objhash_create(DEFAULT_IFIDX_SIZE);
2106 icfg->size = DEFAULT_IFIDX_SIZE;
2107 icfg->main_ptr = malloc(sizeof(struct ifidx) * icfg->size, M_IPFW,
2112 ti->state = icfg->main_ptr;
2113 ti->lookup = ta_lookup_ifidx;
2119 * Handle tableinfo @ti pointer change (on table array resize).
2122 ta_change_ti_ifidx(void *ta_state, struct table_info *ti)
2124 struct iftable_cfg *icfg;
2126 icfg = (struct iftable_cfg *)ta_state;
2131 destroy_ifidx_locked(struct namedobj_instance *ii, struct named_object *no,
2134 struct ifentry *ife;
2135 struct ip_fw_chain *ch;
2137 ch = (struct ip_fw_chain *)arg;
2138 ife = (struct ifentry *)no;
2140 ipfw_iface_del_notify(ch, &ife->ic);
2141 ipfw_iface_unref(ch, &ife->ic);
2142 free(ife, M_IPFW_TBL);
2148 * Destroys table @ti
2151 ta_destroy_ifidx(void *ta_state, struct table_info *ti)
2153 struct iftable_cfg *icfg;
2154 struct ip_fw_chain *ch;
2156 icfg = (struct iftable_cfg *)ta_state;
2159 if (icfg->main_ptr != NULL)
2160 free(icfg->main_ptr, M_IPFW);
2163 ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
2164 IPFW_UH_WUNLOCK(ch);
2166 ipfw_objhash_destroy(icfg->ii);
2172 * Provide algo-specific table info
2175 ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2177 struct iftable_cfg *cfg;
2179 cfg = (struct iftable_cfg *)ta_state;
2181 tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2182 tinfo->size4 = cfg->size;
2183 tinfo->count4 = cfg->used;
2184 tinfo->itemsize4 = sizeof(struct ifidx);
2188 * Prepare state to add to the table:
2189 * allocate ifentry and reference needed interface.
2192 ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2195 struct ta_buf_ifidx *tb;
2197 struct ifentry *ife;
2199 tb = (struct ta_buf_ifidx *)ta_buf;
2201 /* Check if string is terminated */
2202 ifname = (char *)tei->paddr;
2203 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2206 ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
2207 ife->ic.cb = if_notifier;
2208 ife->ic.cbdata = ife;
2210 if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0) {
2211 free(ife, M_IPFW_TBL);
2215 /* Use ipfw_iface 'ifname' field as stable storage */
2216 ife->no.name = ife->ic.iface->ifname;
2224 ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2225 void *ta_buf, uint32_t *pnum)
2227 struct iftable_cfg *icfg;
2228 struct ifentry *ife, *tmp;
2229 struct ta_buf_ifidx *tb;
2230 struct ipfw_iface *iif;
2235 tb = (struct ta_buf_ifidx *)ta_buf;
2236 ifname = (char *)tei->paddr;
2237 icfg = (struct iftable_cfg *)ta_state;
2241 ife->value = tei->value;
2243 tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2246 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2249 /* Exchange values in @tmp and @tei */
2251 tmp->value = tei->value;
2254 iif = tmp->ic.iface;
2255 if (iif->resolved != 0) {
2256 /* We have to update runtime value, too */
2257 ifi = ifidx_find(ti, &iif->ifindex);
2258 ifi->value = ife->value;
2261 /* Indicate that update has happened instead of addition */
2262 tei->flags |= TEI_FLAGS_UPDATED;
2267 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2270 /* Link to internal list */
2271 ipfw_objhash_add(icfg->ii, &ife->no);
2273 /* Link notifier (possible running its callback) */
2274 ipfw_iface_add_notify(icfg->ch, &ife->ic);
2284 * Prepare to delete key from table.
2285 * Do basic interface name checks.
2288 ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2291 struct ta_buf_ifidx *tb;
2294 tb = (struct ta_buf_ifidx *)ta_buf;
2296 /* Check if string is terminated */
2297 ifname = (char *)tei->paddr;
2298 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2305 * Remove key from both configuration list and
2306 * runtime array. Removed interface notification.
2309 ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2310 void *ta_buf, uint32_t *pnum)
2312 struct iftable_cfg *icfg;
2313 struct ifentry *ife;
2314 struct ta_buf_ifidx *tb;
2319 tb = (struct ta_buf_ifidx *)ta_buf;
2320 ifname = (char *)tei->paddr;
2321 icfg = (struct iftable_cfg *)ta_state;
2324 ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2329 if (ife->linked != 0) {
2330 /* We have to remove item from runtime */
2331 ifindex = ife->ic.iface->ifindex;
2333 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2334 sizeof(struct ifidx), compare_ifidx);
2336 KASSERT(res == 1, ("index %d does not exist", ifindex));
2338 ti->data = icfg->used;
2342 /* Unlink from local list */
2343 ipfw_objhash_del(icfg->ii, &ife->no);
2344 /* Unlink notifier and deref */
2345 ipfw_iface_del_notify(icfg->ch, &ife->ic);
2346 ipfw_iface_unref(icfg->ch, &ife->ic);
2349 tei->value = ife->value;
2358 * Flush deleted entry.
2359 * Drops interface reference and frees entry.
2362 ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2365 struct ta_buf_ifidx *tb;
2367 tb = (struct ta_buf_ifidx *)ta_buf;
2369 if (tb->ife != NULL)
2370 free(tb->ife, M_IPFW_TBL);
2375 * Handle interface announce/withdrawal for particular table.
2376 * Every real runtime array modification happens here.
2379 if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
2381 struct ifentry *ife;
2383 struct iftable_cfg *icfg;
2384 struct table_info *ti;
2387 ife = (struct ifentry *)cbdata;
2391 KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
2393 if (ife->linked == 0 && ifindex != 0) {
2394 /* Interface announce */
2397 ifi.value = ife->value;
2398 res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used,
2399 sizeof(struct ifidx), compare_ifidx);
2400 KASSERT(res == 1, ("index %d already exists", ifindex));
2402 ti->data = icfg->used;
2404 } else if (ife->linked != 0 && ifindex == 0) {
2405 /* Interface withdrawal */
2406 ifindex = ife->ic.iface->ifindex;
2408 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2409 sizeof(struct ifidx), compare_ifidx);
2411 KASSERT(res == 1, ("index %d does not exist", ifindex));
2413 ti->data = icfg->used;
2420 * Table growing callbacks.
2424 ta_need_modify_ifidx(void *ta_state, struct table_info *ti, uint32_t count,
2427 struct iftable_cfg *cfg;
2430 cfg = (struct iftable_cfg *)ta_state;
2433 while (size < cfg->count + count)
2436 if (size != cfg->size) {
2445 * Allocate ned, larger runtime ifidx array.
2448 ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
2450 struct mod_item *mi;
2452 mi = (struct mod_item *)ta_buf;
2454 memset(mi, 0, sizeof(struct mod_item));
2456 mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
2463 * Copy data from old runtime array to new one.
2466 ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2469 struct mod_item *mi;
2470 struct iftable_cfg *icfg;
2472 mi = (struct mod_item *)ta_buf;
2473 icfg = (struct iftable_cfg *)ta_state;
2475 /* Check if we still need to grow array */
2476 if (icfg->size >= mi->size) {
2481 memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
2487 * Switch old & new arrays.
2490 ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2493 struct mod_item *mi;
2494 struct iftable_cfg *icfg;
2497 mi = (struct mod_item *)ta_buf;
2498 icfg = (struct iftable_cfg *)ta_state;
2500 old_ptr = icfg->main_ptr;
2501 icfg->main_ptr = mi->main_ptr;
2502 icfg->size = mi->size;
2503 ti->state = icfg->main_ptr;
2505 mi->main_ptr = old_ptr;
2509 * Free unneded array.
2512 ta_flush_mod_ifidx(void *ta_buf)
2514 struct mod_item *mi;
2516 mi = (struct mod_item *)ta_buf;
2517 if (mi->main_ptr != NULL)
2518 free(mi->main_ptr, M_IPFW);
2522 ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
2523 ipfw_obj_tentry *tent)
2525 struct ifentry *ife;
2527 ife = (struct ifentry *)e;
2529 tent->masklen = 8 * IF_NAMESIZE;
2530 memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
2531 tent->v.kidx = ife->value;
2537 ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
2538 ipfw_obj_tentry *tent)
2540 struct iftable_cfg *icfg;
2541 struct ifentry *ife;
2544 icfg = (struct iftable_cfg *)ta_state;
2545 ifname = tent->k.iface;
2547 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2550 ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2553 ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
2566 foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
2569 struct ifentry *ife;
2570 struct wa_ifidx *wa;
2572 ife = (struct ifentry *)no;
2573 wa = (struct wa_ifidx *)arg;
2575 wa->f(ife, wa->arg);
2580 ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2583 struct iftable_cfg *icfg;
2586 icfg = (struct iftable_cfg *)ta_state;
2591 ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
2594 struct table_algo iface_idx = {
2595 .name = "iface:array",
2596 .type = IPFW_TABLE_INTERFACE,
2597 .flags = TA_FLAG_DEFAULT,
2598 .ta_buf_size = sizeof(struct ta_buf_ifidx),
2599 .init = ta_init_ifidx,
2600 .destroy = ta_destroy_ifidx,
2601 .prepare_add = ta_prepare_add_ifidx,
2602 .prepare_del = ta_prepare_del_ifidx,
2603 .add = ta_add_ifidx,
2604 .del = ta_del_ifidx,
2605 .flush_entry = ta_flush_ifidx_entry,
2606 .foreach = ta_foreach_ifidx,
2607 .dump_tentry = ta_dump_ifidx_tentry,
2608 .find_tentry = ta_find_ifidx_tentry,
2609 .dump_tinfo = ta_dump_ifidx_tinfo,
2610 .need_modify = ta_need_modify_ifidx,
2611 .prepare_mod = ta_prepare_mod_ifidx,
2612 .fill_mod = ta_fill_mod_ifidx,
2613 .modify = ta_modify_ifidx,
2614 .flush_mod = ta_flush_mod_ifidx,
2615 .change_ti = ta_change_ti_ifidx,
2619 * Number array cmds.
2624 * - sorted array of "struct numarray" pointed by ti->state.
2625 * Array is allocated with rounding up to NUMARRAY_CHUNK.
2626 * - current array size is stored in ti->data
2635 struct numarray_cfg {
2637 size_t size; /* Number of items allocated in array */
2638 size_t used; /* Number of items _active_ now */
2641 struct ta_buf_numarray
2646 int compare_numarray(const void *k, const void *v);
2647 static struct numarray *numarray_find(struct table_info *ti, void *key);
2648 static int ta_lookup_numarray(struct table_info *ti, void *key,
2649 uint32_t keylen, uint32_t *val);
2650 static int ta_init_numarray(struct ip_fw_chain *ch, void **ta_state,
2651 struct table_info *ti, char *data, uint8_t tflags);
2652 static void ta_destroy_numarray(void *ta_state, struct table_info *ti);
2653 static void ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti,
2654 ipfw_ta_tinfo *tinfo);
2655 static int ta_prepare_add_numarray(struct ip_fw_chain *ch,
2656 struct tentry_info *tei, void *ta_buf);
2657 static int ta_add_numarray(void *ta_state, struct table_info *ti,
2658 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2659 static int ta_del_numarray(void *ta_state, struct table_info *ti,
2660 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2661 static void ta_flush_numarray_entry(struct ip_fw_chain *ch,
2662 struct tentry_info *tei, void *ta_buf);
2663 static int ta_need_modify_numarray(void *ta_state, struct table_info *ti,
2664 uint32_t count, uint64_t *pflags);
2665 static int ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags);
2666 static int ta_fill_mod_numarray(void *ta_state, struct table_info *ti,
2667 void *ta_buf, uint64_t *pflags);
2668 static void ta_modify_numarray(void *ta_state, struct table_info *ti,
2669 void *ta_buf, uint64_t pflags);
2670 static void ta_flush_mod_numarray(void *ta_buf);
2671 static int ta_dump_numarray_tentry(void *ta_state, struct table_info *ti,
2672 void *e, ipfw_obj_tentry *tent);
2673 static int ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2674 ipfw_obj_tentry *tent);
2675 static void ta_foreach_numarray(void *ta_state, struct table_info *ti,
2676 ta_foreach_f *f, void *arg);
2679 compare_numarray(const void *k, const void *v)
2681 const struct numarray *na;
2684 key = *((const uint32_t *)k);
2685 na = (const struct numarray *)v;
2687 if (key < na->number)
2689 else if (key > na->number)
2695 static struct numarray *
2696 numarray_find(struct table_info *ti, void *key)
2698 struct numarray *ri;
2700 ri = bsearch(key, ti->state, ti->data, sizeof(struct numarray),
2707 ta_lookup_numarray(struct table_info *ti, void *key, uint32_t keylen,
2710 struct numarray *ri;
2712 ri = numarray_find(ti, key);
2723 ta_init_numarray(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2724 char *data, uint8_t tflags)
2726 struct numarray_cfg *cfg;
2728 cfg = malloc(sizeof(*cfg), M_IPFW, M_WAITOK | M_ZERO);
2731 cfg->main_ptr = malloc(sizeof(struct numarray) * cfg->size, M_IPFW,
2735 ti->state = cfg->main_ptr;
2736 ti->lookup = ta_lookup_numarray;
2742 * Destroys table @ti
2745 ta_destroy_numarray(void *ta_state, struct table_info *ti)
2747 struct numarray_cfg *cfg;
2749 cfg = (struct numarray_cfg *)ta_state;
2751 if (cfg->main_ptr != NULL)
2752 free(cfg->main_ptr, M_IPFW);
2758 * Provide algo-specific table info
2761 ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2763 struct numarray_cfg *cfg;
2765 cfg = (struct numarray_cfg *)ta_state;
2767 tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2768 tinfo->size4 = cfg->size;
2769 tinfo->count4 = cfg->used;
2770 tinfo->itemsize4 = sizeof(struct numarray);
2774 * Prepare for addition/deletion to an array.
2777 ta_prepare_add_numarray(struct ip_fw_chain *ch, struct tentry_info *tei,
2780 struct ta_buf_numarray *tb;
2782 tb = (struct ta_buf_numarray *)ta_buf;
2784 tb->na.number = *((uint32_t *)tei->paddr);
2790 ta_add_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2791 void *ta_buf, uint32_t *pnum)
2793 struct numarray_cfg *cfg;
2794 struct ta_buf_numarray *tb;
2795 struct numarray *ri;
2799 tb = (struct ta_buf_numarray *)ta_buf;
2800 cfg = (struct numarray_cfg *)ta_state;
2802 /* Read current value from @tei */
2803 tb->na.value = tei->value;
2805 ri = numarray_find(ti, &tb->na.number);
2808 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2811 /* Exchange values between ri and @tei */
2813 ri->value = tei->value;
2815 /* Indicate that update has happened instead of addition */
2816 tei->flags |= TEI_FLAGS_UPDATED;
2821 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2824 res = badd(&tb->na.number, &tb->na, cfg->main_ptr, cfg->used,
2825 sizeof(struct numarray), compare_numarray);
2827 KASSERT(res == 1, ("number %d already exists", tb->na.number));
2829 ti->data = cfg->used;
2836 * Remove key from both configuration list and
2837 * runtime array. Removed interface notification.
2840 ta_del_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2841 void *ta_buf, uint32_t *pnum)
2843 struct numarray_cfg *cfg;
2844 struct ta_buf_numarray *tb;
2845 struct numarray *ri;
2848 tb = (struct ta_buf_numarray *)ta_buf;
2849 cfg = (struct numarray_cfg *)ta_state;
2851 ri = numarray_find(ti, &tb->na.number);
2855 tei->value = ri->value;
2857 res = bdel(&tb->na.number, cfg->main_ptr, cfg->used,
2858 sizeof(struct numarray), compare_numarray);
2860 KASSERT(res == 1, ("number %u does not exist", tb->na.number));
2862 ti->data = cfg->used;
2869 ta_flush_numarray_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2873 /* We don't have any state, do nothing */
2878 * Table growing callbacks.
2882 ta_need_modify_numarray(void *ta_state, struct table_info *ti, uint32_t count,
2885 struct numarray_cfg *cfg;
2888 cfg = (struct numarray_cfg *)ta_state;
2891 while (size < cfg->used + count)
2894 if (size != cfg->size) {
2903 * Allocate new, larger runtime array.
2906 ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags)
2908 struct mod_item *mi;
2910 mi = (struct mod_item *)ta_buf;
2912 memset(mi, 0, sizeof(struct mod_item));
2914 mi->main_ptr = malloc(sizeof(struct numarray) * mi->size, M_IPFW,
2921 * Copy data from old runtime array to new one.
2924 ta_fill_mod_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2927 struct mod_item *mi;
2928 struct numarray_cfg *cfg;
2930 mi = (struct mod_item *)ta_buf;
2931 cfg = (struct numarray_cfg *)ta_state;
2933 /* Check if we still need to grow array */
2934 if (cfg->size >= mi->size) {
2939 memcpy(mi->main_ptr, cfg->main_ptr, cfg->used * sizeof(struct numarray));
2945 * Switch old & new arrays.
2948 ta_modify_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2951 struct mod_item *mi;
2952 struct numarray_cfg *cfg;
2955 mi = (struct mod_item *)ta_buf;
2956 cfg = (struct numarray_cfg *)ta_state;
2958 old_ptr = cfg->main_ptr;
2959 cfg->main_ptr = mi->main_ptr;
2960 cfg->size = mi->size;
2961 ti->state = cfg->main_ptr;
2963 mi->main_ptr = old_ptr;
2967 * Free unneded array.
2970 ta_flush_mod_numarray(void *ta_buf)
2972 struct mod_item *mi;
2974 mi = (struct mod_item *)ta_buf;
2975 if (mi->main_ptr != NULL)
2976 free(mi->main_ptr, M_IPFW);
2980 ta_dump_numarray_tentry(void *ta_state, struct table_info *ti, void *e,
2981 ipfw_obj_tentry *tent)
2983 struct numarray *na;
2985 na = (struct numarray *)e;
2987 tent->k.key = na->number;
2988 tent->v.kidx = na->value;
2994 ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2995 ipfw_obj_tentry *tent)
2997 struct numarray_cfg *cfg;
2998 struct numarray *ri;
3000 cfg = (struct numarray_cfg *)ta_state;
3002 ri = numarray_find(ti, &tent->k.key);
3005 ta_dump_numarray_tentry(ta_state, ti, ri, tent);
3013 ta_foreach_numarray(void *ta_state, struct table_info *ti, ta_foreach_f *f,
3016 struct numarray_cfg *cfg;
3017 struct numarray *array;
3020 cfg = (struct numarray_cfg *)ta_state;
3021 array = cfg->main_ptr;
3023 for (i = 0; i < cfg->used; i++)
3027 struct table_algo number_array = {
3028 .name = "number:array",
3029 .type = IPFW_TABLE_NUMBER,
3030 .ta_buf_size = sizeof(struct ta_buf_numarray),
3031 .init = ta_init_numarray,
3032 .destroy = ta_destroy_numarray,
3033 .prepare_add = ta_prepare_add_numarray,
3034 .prepare_del = ta_prepare_add_numarray,
3035 .add = ta_add_numarray,
3036 .del = ta_del_numarray,
3037 .flush_entry = ta_flush_numarray_entry,
3038 .foreach = ta_foreach_numarray,
3039 .dump_tentry = ta_dump_numarray_tentry,
3040 .find_tentry = ta_find_numarray_tentry,
3041 .dump_tinfo = ta_dump_numarray_tinfo,
3042 .need_modify = ta_need_modify_numarray,
3043 .prepare_mod = ta_prepare_mod_numarray,
3044 .fill_mod = ta_fill_mod_numarray,
3045 .modify = ta_modify_numarray,
3046 .flush_mod = ta_flush_mod_numarray,
3054 * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
3057 * inv.mask4: 32 - mask
3059 * 1) _slow lookup: mask
3060 * 2) _aligned: (128 - mask) / 8
3071 SLIST_HEAD(fhashbhead, fhashentry);
3074 SLIST_ENTRY(fhashentry) next;
3084 struct fhashentry4 {
3085 struct fhashentry e;
3090 struct fhashentry6 {
3091 struct fhashentry e;
3092 struct in6_addr dip6;
3093 struct in6_addr sip6;
3097 struct fhashbhead *head;
3100 struct fhashentry4 fe4;
3101 struct fhashentry6 fe6;
3104 struct ta_buf_fhash {
3106 struct fhashentry6 fe6;
3109 static __inline int cmp_flow_ent(struct fhashentry *a,
3110 struct fhashentry *b, size_t sz);
3111 static __inline uint32_t hash_flow4(struct fhashentry4 *f, int hsize);
3112 static __inline uint32_t hash_flow6(struct fhashentry6 *f, int hsize);
3113 static uint32_t hash_flow_ent(struct fhashentry *ent, uint32_t size);
3114 static int ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3116 static int ta_init_fhash(struct ip_fw_chain *ch, void **ta_state,
3117 struct table_info *ti, char *data, uint8_t tflags);
3118 static void ta_destroy_fhash(void *ta_state, struct table_info *ti);
3119 static void ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti,
3120 ipfw_ta_tinfo *tinfo);
3121 static int ta_dump_fhash_tentry(void *ta_state, struct table_info *ti,
3122 void *e, ipfw_obj_tentry *tent);
3123 static int tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent);
3124 static int ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
3125 ipfw_obj_tentry *tent);
3126 static void ta_foreach_fhash(void *ta_state, struct table_info *ti,
3127 ta_foreach_f *f, void *arg);
3128 static int ta_prepare_add_fhash(struct ip_fw_chain *ch,
3129 struct tentry_info *tei, void *ta_buf);
3130 static int ta_add_fhash(void *ta_state, struct table_info *ti,
3131 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3132 static int ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3134 static int ta_del_fhash(void *ta_state, struct table_info *ti,
3135 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3136 static void ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3138 static int ta_need_modify_fhash(void *ta_state, struct table_info *ti,
3139 uint32_t count, uint64_t *pflags);
3140 static int ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags);
3141 static int ta_fill_mod_fhash(void *ta_state, struct table_info *ti,
3142 void *ta_buf, uint64_t *pflags);
3143 static void ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3145 static void ta_flush_mod_fhash(void *ta_buf);
3148 cmp_flow_ent(struct fhashentry *a, struct fhashentry *b, size_t sz)
3152 ka = (uint64_t *)(&a->next + 1);
3153 kb = (uint64_t *)(&b->next + 1);
3155 if (*ka == *kb && (memcmp(a + 1, b + 1, sz) == 0))
3161 static __inline uint32_t
3162 hash_flow4(struct fhashentry4 *f, int hsize)
3166 i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport);
3168 return (i % (hsize - 1));
3171 static __inline uint32_t
3172 hash_flow6(struct fhashentry6 *f, int hsize)
3176 i = (f->dip6.__u6_addr.__u6_addr32[2]) ^
3177 (f->dip6.__u6_addr.__u6_addr32[3]) ^
3178 (f->sip6.__u6_addr.__u6_addr32[2]) ^
3179 (f->sip6.__u6_addr.__u6_addr32[3]) ^
3180 (f->e.dport) ^ (f->e.sport);
3182 return (i % (hsize - 1));
3186 hash_flow_ent(struct fhashentry *ent, uint32_t size)
3190 if (ent->af == AF_INET) {
3191 hash = hash_flow4((struct fhashentry4 *)ent, size);
3193 hash = hash_flow6((struct fhashentry6 *)ent, size);
3200 ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3203 struct fhashbhead *head;
3204 struct fhashentry *ent;
3205 struct fhashentry4 *m4;
3206 struct ipfw_flow_id *id;
3207 uint16_t hash, hsize;
3209 id = (struct ipfw_flow_id *)key;
3210 head = (struct fhashbhead *)ti->state;
3212 m4 = (struct fhashentry4 *)ti->xstate;
3214 if (id->addr_type == 4) {
3215 struct fhashentry4 f;
3217 /* Copy hash mask */
3220 f.dip.s_addr &= id->dst_ip;
3221 f.sip.s_addr &= id->src_ip;
3222 f.e.dport &= id->dst_port;
3223 f.e.sport &= id->src_port;
3224 f.e.proto &= id->proto;
3225 hash = hash_flow4(&f, hsize);
3226 SLIST_FOREACH(ent, &head[hash], next) {
3227 if (cmp_flow_ent(ent, &f.e, 2 * 4) != 0) {
3232 } else if (id->addr_type == 6) {
3233 struct fhashentry6 f;
3236 /* Copy hash mask */
3237 f = *((struct fhashentry6 *)(m4 + 1));
3239 /* Handle lack of __u6_addr.__u6_addr64 */
3240 fp = (uint64_t *)&f.dip6;
3241 idp = (uint64_t *)&id->dst_ip6;
3242 /* src IPv6 is stored after dst IPv6 */
3247 f.e.dport &= id->dst_port;
3248 f.e.sport &= id->src_port;
3249 f.e.proto &= id->proto;
3250 hash = hash_flow6(&f, hsize);
3251 SLIST_FOREACH(ent, &head[hash], next) {
3252 if (cmp_flow_ent(ent, &f.e, 2 * 16) != 0) {
3266 ta_init_fhash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
3267 char *data, uint8_t tflags)
3270 struct fhash_cfg *cfg;
3271 struct fhashentry4 *fe4;
3272 struct fhashentry6 *fe6;
3274 cfg = malloc(sizeof(struct fhash_cfg), M_IPFW, M_WAITOK | M_ZERO);
3278 cfg->head = malloc(sizeof(struct fhashbhead) * cfg->size, M_IPFW,
3280 for (i = 0; i < cfg->size; i++)
3281 SLIST_INIT(&cfg->head[i]);
3283 /* Fill in fe masks based on @tflags */
3286 if (tflags & IPFW_TFFLAG_SRCIP) {
3287 memset(&fe4->sip, 0xFF, sizeof(fe4->sip));
3288 memset(&fe6->sip6, 0xFF, sizeof(fe6->sip6));
3290 if (tflags & IPFW_TFFLAG_DSTIP) {
3291 memset(&fe4->dip, 0xFF, sizeof(fe4->dip));
3292 memset(&fe6->dip6, 0xFF, sizeof(fe6->dip6));
3294 if (tflags & IPFW_TFFLAG_SRCPORT) {
3295 memset(&fe4->e.sport, 0xFF, sizeof(fe4->e.sport));
3296 memset(&fe6->e.sport, 0xFF, sizeof(fe6->e.sport));
3298 if (tflags & IPFW_TFFLAG_DSTPORT) {
3299 memset(&fe4->e.dport, 0xFF, sizeof(fe4->e.dport));
3300 memset(&fe6->e.dport, 0xFF, sizeof(fe6->e.dport));
3302 if (tflags & IPFW_TFFLAG_PROTO) {
3303 memset(&fe4->e.proto, 0xFF, sizeof(fe4->e.proto));
3304 memset(&fe6->e.proto, 0xFF, sizeof(fe6->e.proto));
3307 fe4->e.af = AF_INET;
3308 fe6->e.af = AF_INET6;
3311 ti->state = cfg->head;
3312 ti->xstate = &cfg->fe4;
3313 ti->data = cfg->size;
3314 ti->lookup = ta_lookup_fhash;
3320 ta_destroy_fhash(void *ta_state, struct table_info *ti)
3322 struct fhash_cfg *cfg;
3323 struct fhashentry *ent, *ent_next;
3326 cfg = (struct fhash_cfg *)ta_state;
3328 for (i = 0; i < cfg->size; i++)
3329 SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next)
3330 free(ent, M_IPFW_TBL);
3332 free(cfg->head, M_IPFW);
3337 * Provide algo-specific table info
3340 ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
3342 struct fhash_cfg *cfg;
3344 cfg = (struct fhash_cfg *)ta_state;
3346 tinfo->flags = IPFW_TATFLAGS_AFITEM;
3347 tinfo->taclass4 = IPFW_TACLASS_HASH;
3348 tinfo->size4 = cfg->size;
3349 tinfo->count4 = cfg->items;
3350 tinfo->itemsize4 = sizeof(struct fhashentry4);
3351 tinfo->itemsize6 = sizeof(struct fhashentry6);
3355 ta_dump_fhash_tentry(void *ta_state, struct table_info *ti, void *e,
3356 ipfw_obj_tentry *tent)
3358 struct fhash_cfg *cfg;
3359 struct fhashentry *ent;
3360 struct fhashentry4 *fe4;
3362 struct fhashentry6 *fe6;
3364 struct tflow_entry *tfe;
3366 cfg = (struct fhash_cfg *)ta_state;
3367 ent = (struct fhashentry *)e;
3368 tfe = &tent->k.flow;
3371 tfe->proto = ent->proto;
3372 tfe->dport = htons(ent->dport);
3373 tfe->sport = htons(ent->sport);
3374 tent->v.kidx = ent->value;
3375 tent->subtype = ent->af;
3377 if (ent->af == AF_INET) {
3378 fe4 = (struct fhashentry4 *)ent;
3379 tfe->a.a4.sip.s_addr = htonl(fe4->sip.s_addr);
3380 tfe->a.a4.dip.s_addr = htonl(fe4->dip.s_addr);
3384 fe6 = (struct fhashentry6 *)ent;
3385 tfe->a.a6.sip6 = fe6->sip6;
3386 tfe->a.a6.dip6 = fe6->dip6;
3387 tent->masklen = 128;
3395 tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent)
3398 struct fhashentry4 *fe4;
3401 struct fhashentry6 *fe6;
3403 struct tflow_entry *tfe;
3405 tfe = (struct tflow_entry *)tei->paddr;
3407 ent->af = tei->subtype;
3408 ent->proto = tfe->proto;
3409 ent->dport = ntohs(tfe->dport);
3410 ent->sport = ntohs(tfe->sport);
3412 if (tei->subtype == AF_INET) {
3414 fe4 = (struct fhashentry4 *)ent;
3415 fe4->sip.s_addr = ntohl(tfe->a.a4.sip.s_addr);
3416 fe4->dip.s_addr = ntohl(tfe->a.a4.dip.s_addr);
3419 } else if (tei->subtype == AF_INET6) {
3420 fe6 = (struct fhashentry6 *)ent;
3421 fe6->sip6 = tfe->a.a6.sip6;
3422 fe6->dip6 = tfe->a.a6.dip6;
3425 /* Unknown CIDR type */
3434 ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
3435 ipfw_obj_tentry *tent)
3437 struct fhash_cfg *cfg;
3438 struct fhashbhead *head;
3439 struct fhashentry *ent, *tmp;
3440 struct fhashentry6 fe6;
3441 struct tentry_info tei;
3446 cfg = (struct fhash_cfg *)ta_state;
3450 memset(&fe6, 0, sizeof(fe6));
3451 memset(&tei, 0, sizeof(tei));
3453 tei.paddr = &tent->k.flow;
3454 tei.subtype = tent->subtype;
3456 if ((error = tei_to_fhash_ent(&tei, ent)) != 0)
3460 hash = hash_flow_ent(ent, cfg->size);
3462 if (tei.subtype == AF_INET)
3463 sz = 2 * sizeof(struct in_addr);
3465 sz = 2 * sizeof(struct in6_addr);
3467 /* Check for existence */
3468 SLIST_FOREACH(tmp, &head[hash], next) {
3469 if (cmp_flow_ent(tmp, ent, sz) != 0) {
3470 ta_dump_fhash_tentry(ta_state, ti, tmp, tent);
3479 ta_foreach_fhash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
3482 struct fhash_cfg *cfg;
3483 struct fhashentry *ent, *ent_next;
3486 cfg = (struct fhash_cfg *)ta_state;
3488 for (i = 0; i < cfg->size; i++)
3489 SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next)
3494 ta_prepare_add_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3497 struct ta_buf_fhash *tb;
3498 struct fhashentry *ent;
3502 tb = (struct ta_buf_fhash *)ta_buf;
3504 if (tei->subtype == AF_INET)
3505 sz = sizeof(struct fhashentry4);
3506 else if (tei->subtype == AF_INET6)
3507 sz = sizeof(struct fhashentry6);
3511 ent = malloc(sz, M_IPFW_TBL, M_WAITOK | M_ZERO);
3513 error = tei_to_fhash_ent(tei, ent);
3515 free(ent, M_IPFW_TBL);
3524 ta_add_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
3525 void *ta_buf, uint32_t *pnum)
3527 struct fhash_cfg *cfg;
3528 struct fhashbhead *head;
3529 struct fhashentry *ent, *tmp;
3530 struct ta_buf_fhash *tb;
3532 uint32_t hash, value;
3535 cfg = (struct fhash_cfg *)ta_state;
3536 tb = (struct ta_buf_fhash *)ta_buf;
3537 ent = (struct fhashentry *)tb->ent_ptr;
3540 /* Read current value from @tei */
3541 ent->value = tei->value;
3544 hash = hash_flow_ent(ent, cfg->size);
3546 if (tei->subtype == AF_INET)
3547 sz = 2 * sizeof(struct in_addr);
3549 sz = 2 * sizeof(struct in6_addr);
3551 /* Check for existence */
3552 SLIST_FOREACH(tmp, &head[hash], next) {
3553 if (cmp_flow_ent(tmp, ent, sz) != 0) {
3560 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
3562 /* Record already exists. Update value if we're asked to */
3563 /* Exchange values between tmp and @tei */
3565 tmp->value = tei->value;
3567 /* Indicate that update has happened instead of addition */
3568 tei->flags |= TEI_FLAGS_UPDATED;
3571 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
3574 SLIST_INSERT_HEAD(&head[hash], ent, next);
3578 /* Update counters and check if we need to grow hash */
3586 ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3589 struct ta_buf_fhash *tb;
3591 tb = (struct ta_buf_fhash *)ta_buf;
3593 return (tei_to_fhash_ent(tei, &tb->fe6.e));
3597 ta_del_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
3598 void *ta_buf, uint32_t *pnum)
3600 struct fhash_cfg *cfg;
3601 struct fhashbhead *head;
3602 struct fhashentry *ent, *tmp;
3603 struct ta_buf_fhash *tb;
3607 cfg = (struct fhash_cfg *)ta_state;
3608 tb = (struct ta_buf_fhash *)ta_buf;
3612 hash = hash_flow_ent(ent, cfg->size);
3614 if (tei->subtype == AF_INET)
3615 sz = 2 * sizeof(struct in_addr);
3617 sz = 2 * sizeof(struct in6_addr);
3619 /* Check for existence */
3620 SLIST_FOREACH(tmp, &head[hash], next) {
3621 if (cmp_flow_ent(tmp, ent, sz) == 0)
3624 SLIST_REMOVE(&head[hash], tmp, fhashentry, next);
3625 tei->value = tmp->value;
3636 ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3639 struct ta_buf_fhash *tb;
3641 tb = (struct ta_buf_fhash *)ta_buf;
3643 if (tb->ent_ptr != NULL)
3644 free(tb->ent_ptr, M_IPFW_TBL);
3648 * Hash growing callbacks.
3652 ta_need_modify_fhash(void *ta_state, struct table_info *ti, uint32_t count,
3655 struct fhash_cfg *cfg;
3657 cfg = (struct fhash_cfg *)ta_state;
3659 if (cfg->items > cfg->size && cfg->size < 65536) {
3660 *pflags = cfg->size * 2;
3668 * Allocate new, larger fhash.
3671 ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags)
3673 struct mod_item *mi;
3674 struct fhashbhead *head;
3677 mi = (struct mod_item *)ta_buf;
3679 memset(mi, 0, sizeof(struct mod_item));
3681 head = malloc(sizeof(struct fhashbhead) * mi->size, M_IPFW,
3683 for (i = 0; i < mi->size; i++)
3684 SLIST_INIT(&head[i]);
3686 mi->main_ptr = head;
3692 * Copy data from old runtime array to new one.
3695 ta_fill_mod_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3699 /* In is not possible to do rehash if we're not holidng WLOCK. */
3704 * Switch old & new arrays.
3707 ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3710 struct mod_item *mi;
3711 struct fhash_cfg *cfg;
3712 struct fhashbhead *old_head, *new_head;
3713 struct fhashentry *ent, *ent_next;
3718 mi = (struct mod_item *)ta_buf;
3719 cfg = (struct fhash_cfg *)ta_state;
3721 old_size = cfg->size;
3722 old_head = ti->state;
3724 new_head = (struct fhashbhead *)mi->main_ptr;
3725 for (i = 0; i < old_size; i++) {
3726 SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
3727 nhash = hash_flow_ent(ent, mi->size);
3728 SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
3732 ti->state = new_head;
3733 ti->data = mi->size;
3734 cfg->head = new_head;
3735 cfg->size = mi->size;
3737 mi->main_ptr = old_head;
3741 * Free unneded array.
3744 ta_flush_mod_fhash(void *ta_buf)
3746 struct mod_item *mi;
3748 mi = (struct mod_item *)ta_buf;
3749 if (mi->main_ptr != NULL)
3750 free(mi->main_ptr, M_IPFW);
3753 struct table_algo flow_hash = {
3754 .name = "flow:hash",
3755 .type = IPFW_TABLE_FLOW,
3756 .flags = TA_FLAG_DEFAULT,
3757 .ta_buf_size = sizeof(struct ta_buf_fhash),
3758 .init = ta_init_fhash,
3759 .destroy = ta_destroy_fhash,
3760 .prepare_add = ta_prepare_add_fhash,
3761 .prepare_del = ta_prepare_del_fhash,
3762 .add = ta_add_fhash,
3763 .del = ta_del_fhash,
3764 .flush_entry = ta_flush_fhash_entry,
3765 .foreach = ta_foreach_fhash,
3766 .dump_tentry = ta_dump_fhash_tentry,
3767 .find_tentry = ta_find_fhash_tentry,
3768 .dump_tinfo = ta_dump_fhash_tinfo,
3769 .need_modify = ta_need_modify_fhash,
3770 .prepare_mod = ta_prepare_mod_fhash,
3771 .fill_mod = ta_fill_mod_fhash,
3772 .modify = ta_modify_fhash,
3773 .flush_mod = ta_flush_mod_fhash,
3777 * Kernel fibs bindings.
3782 * - fully relies on route API
3783 * - fib number is stored in ti->data
3787 static int ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen,
3789 static int kfib_parse_opts(int *pfib, char *data);
3790 static void ta_print_kfib_config(void *ta_state, struct table_info *ti,
3791 char *buf, size_t bufsize);
3792 static int ta_init_kfib(struct ip_fw_chain *ch, void **ta_state,
3793 struct table_info *ti, char *data, uint8_t tflags);
3794 static void ta_destroy_kfib(void *ta_state, struct table_info *ti);
3795 static void ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti,
3796 ipfw_ta_tinfo *tinfo);
3797 static int contigmask(uint8_t *p, int len);
3798 static int ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e,
3799 ipfw_obj_tentry *tent);
3800 static int ta_dump_kfib_tentry_int(struct sockaddr *paddr,
3801 struct sockaddr *pmask, ipfw_obj_tentry *tent);
3802 static int ta_find_kfib_tentry(void *ta_state, struct table_info *ti,
3803 ipfw_obj_tentry *tent);
3804 static void ta_foreach_kfib(void *ta_state, struct table_info *ti,
3805 ta_foreach_f *f, void *arg);
3809 ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen,
3813 struct nhop4_basic nh4;
3817 struct nhop6_basic nh6;
3824 in.s_addr = *(in_addr_t *)key;
3825 error = fib4_lookup_nh_basic(ti->data,
3831 error = fib6_lookup_nh_basic(ti->data,
3832 (struct in6_addr *)key, 0, 0, 0, &nh6);
3843 /* Parse 'fib=%d' */
3845 kfib_parse_opts(int *pfib, char *data)
3847 char *pdel, *pend, *s;
3852 if ((pdel = strchr(data, ' ')) == NULL)
3854 while (*pdel == ' ')
3856 if (strncmp(pdel, "fib=", 4) != 0)
3858 if ((s = strchr(pdel, ' ')) != NULL)
3863 fibnum = strtol(pdel, &pend, 10);
3873 ta_print_kfib_config(void *ta_state, struct table_info *ti, char *buf,
3878 snprintf(buf, bufsize, "%s fib=%lu", "addr:kfib", ti->data);
3880 snprintf(buf, bufsize, "%s", "addr:kfib");
3884 ta_init_kfib(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
3885 char *data, uint8_t tflags)
3890 if ((error = kfib_parse_opts(&fibnum, data)) != 0)
3893 if (fibnum >= rt_numfibs)
3897 ti->lookup = ta_lookup_kfib;
3903 * Destroys table @ti
3906 ta_destroy_kfib(void *ta_state, struct table_info *ti)
3912 * Provide algo-specific table info
3915 ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
3918 tinfo->flags = IPFW_TATFLAGS_AFDATA;
3919 tinfo->taclass4 = IPFW_TACLASS_RADIX;
3921 tinfo->itemsize4 = sizeof(struct rtentry);
3922 tinfo->taclass6 = IPFW_TACLASS_RADIX;
3924 tinfo->itemsize6 = sizeof(struct rtentry);
3928 contigmask(uint8_t *p, int len)
3932 for (i = 0; i < len ; i++)
3933 if ( (p[i/8] & (1 << (7 - (i%8)))) == 0) /* first bit unset */
3935 for (n= i + 1; n < len; n++)
3936 if ( (p[n/8] & (1 << (7 - (n % 8)))) != 0)
3937 return (-1); /* mask not contiguous */
3943 ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e,
3944 ipfw_obj_tentry *tent)
3946 struct rtentry *rte;
3948 rte = (struct rtentry *)e;
3950 return ta_dump_kfib_tentry_int(rt_key(rte), rt_mask(rte), tent);
3954 ta_dump_kfib_tentry_int(struct sockaddr *paddr, struct sockaddr *pmask,
3955 ipfw_obj_tentry *tent)
3958 struct sockaddr_in *addr, *mask;
3961 struct sockaddr_in6 *addr6, *mask6;
3967 /* Guess IPv4/IPv6 radix by sockaddr family */
3969 if (paddr->sa_family == AF_INET) {
3970 addr = (struct sockaddr_in *)paddr;
3971 mask = (struct sockaddr_in *)pmask;
3972 tent->k.addr.s_addr = addr->sin_addr.s_addr;
3975 len = contigmask((uint8_t *)&mask->sin_addr, 32);
3978 tent->masklen = len;
3979 tent->subtype = AF_INET;
3980 tent->v.kidx = 0; /* Do we need to put GW here? */
3984 if (paddr->sa_family == AF_INET6) {
3985 addr6 = (struct sockaddr_in6 *)paddr;
3986 mask6 = (struct sockaddr_in6 *)pmask;
3987 memcpy(&tent->k, &addr6->sin6_addr, sizeof(struct in6_addr));
3990 len = contigmask((uint8_t *)&mask6->sin6_addr, 128);
3993 tent->masklen = len;
3994 tent->subtype = AF_INET6;
4003 ta_find_kfib_tentry(void *ta_state, struct table_info *ti,
4004 ipfw_obj_tentry *tent)
4006 struct rt_addrinfo info;
4007 struct sockaddr_in6 key6, dst6, mask6;
4008 struct sockaddr *dst, *key, *mask;
4010 /* Prepare sockaddr for prefix/mask and info */
4011 bzero(&dst6, sizeof(dst6));
4012 dst6.sin6_len = sizeof(dst6);
4013 dst = (struct sockaddr *)&dst6;
4014 bzero(&mask6, sizeof(mask6));
4015 mask6.sin6_len = sizeof(mask6);
4016 mask = (struct sockaddr *)&mask6;
4018 bzero(&info, sizeof(info));
4019 info.rti_info[RTAX_DST] = dst;
4020 info.rti_info[RTAX_NETMASK] = mask;
4022 /* Prepare the lookup key */
4023 bzero(&key6, sizeof(key6));
4024 key6.sin6_family = tent->subtype;
4025 key = (struct sockaddr *)&key6;
4027 if (tent->subtype == AF_INET) {
4028 ((struct sockaddr_in *)&key6)->sin_addr = tent->k.addr;
4029 key6.sin6_len = sizeof(struct sockaddr_in);
4031 key6.sin6_addr = tent->k.addr6;
4032 key6.sin6_len = sizeof(struct sockaddr_in6);
4035 if (rib_lookup_info(ti->data, key, 0, 0, &info) != 0)
4037 if ((info.rti_addrs & RTA_NETMASK) == 0)
4040 ta_dump_kfib_tentry_int(dst, mask, tent);
4046 ta_foreach_kfib(void *ta_state, struct table_info *ti, ta_foreach_f *f,
4049 struct rib_head *rh;
4052 rh = rt_tables_get_rnh(ti->data, AF_INET);
4055 error = rh->rnh_walktree(&rh->head, (walktree_f_t *)f, arg);
4059 rh = rt_tables_get_rnh(ti->data, AF_INET6);
4062 error = rh->rnh_walktree(&rh->head, (walktree_f_t *)f, arg);
4067 struct table_algo addr_kfib = {
4068 .name = "addr:kfib",
4069 .type = IPFW_TABLE_ADDR,
4070 .flags = TA_FLAG_READONLY,
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,
4082 ipfw_table_algo_init(struct ip_fw_chain *ch)
4087 * Register all algorithms presented here.
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);
4099 ipfw_table_algo_destroy(struct ip_fw_chain *ch)
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);