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/nhop.h>
55 #include <net/route/route_var.h>
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>
63 #include <netpfil/ipfw/ip_fw_private.h>
64 #include <netpfil/ipfw/ip_fw_table.h>
68 * IPFW table lookup algorithms.
70 * What is needed to add another table algo?
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
83 * Callbacks description:
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.
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
102 * -destroy: request to destroy table instance.
103 * typedef void (ta_destroy)(void *ta_state, struct table_info *ti);
104 * MANDATORY, unlocked. (M_WAITOK).
106 * Frees all table entries and all tables structures allocated by -init.
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,
113 * MANDATORY, unlocked. (M_WAITOK). Returns 0 on success.
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
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,
126 * MANDATORY, locked, UH. (M_NOWAIT). Returns 0 on success.
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().
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.
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.
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.
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.
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).
172 * Delete state allocated by:
173 * -prepare_add (-add returned EEXIST|UPDATED)
174 * -prepare_del (if any)
176 * * Caller is required to handle empty @ta_buf correctly.
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.
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
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.
195 * Checks if given table has enough space to add @count items without
196 * resize. Caller may use @pflags to store desired modification data.
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.
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.
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.
215 * Copy as much data as we can to minimize changes under WLOCK.
216 * For example, array can be merged inside this callback.
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).
225 * Performs all changes necessary to switch to new structures.
226 * * Caller should save old pointers to @ta_buf storage.
230 * -flush_mod: flush table modification state.
231 * typedef void (ta_flush_mod)(void *ta_buf);
232 * OPTIONAL(need_modify), unlocked. (M_WAITOK).
234 * Performs flush for the following:
235 * - prepare_mod (modification was not necessary)
236 * - modify (for the old state)
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).
244 * Called on @ti pointer changed. Called immediately after -init
245 * to set initial state.
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).
254 * Runs callback with specified argument for each table entry,
255 * Typically used for dumping table entries.
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.
264 * Dumps entry @e to @tent.
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).
272 * Prints custom algorithm options in the format suitable to pass
273 * back to -init callback.
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).
282 * Dumps options like items size/hash size, etc.
285 MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
288 * Utility structures/functions common to more than one algo
298 static int badd(const void *key, void *item, void *base, size_t nmemb,
299 size_t size, int (*compar) (const void *, const void *));
300 static int bdel(const void *key, void *base, size_t nmemb, size_t size,
301 int (*compar) (const void *, const void *));
305 * ADDR implementation using radix
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
318 #define KEY_LEN(v) *((uint8_t *)&(v))
320 * Do not require radix to compare more than actual IPv4/IPv6 address
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))
325 #define OFF_LEN_INET (8 * offsetof(struct sockaddr_in, sin_addr))
326 #define OFF_LEN_INET6 (8 * offsetof(struct sa_in6, sin6_addr))
328 struct radix_addr_entry {
329 struct radix_node rn[2];
330 struct sockaddr_in addr;
339 struct in6_addr sin6_addr;
342 struct radix_addr_xentry {
343 struct radix_node rn[2];
350 struct radix_node_head *head4;
351 struct radix_node_head *head6;
359 struct sockaddr *addr_ptr;
360 struct sockaddr *mask_ptr;
363 struct sockaddr_in sa;
364 struct sockaddr_in ma;
373 static int ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
375 static int ta_init_radix(struct ip_fw_chain *ch, void **ta_state,
376 struct table_info *ti, char *data, uint8_t tflags);
377 static int flush_radix_entry(struct radix_node *rn, void *arg);
378 static void ta_destroy_radix(void *ta_state, struct table_info *ti);
379 static void ta_dump_radix_tinfo(void *ta_state, struct table_info *ti,
380 ipfw_ta_tinfo *tinfo);
381 static int ta_dump_radix_tentry(void *ta_state, struct table_info *ti,
382 void *e, ipfw_obj_tentry *tent);
383 static int ta_find_radix_tentry(void *ta_state, struct table_info *ti,
384 ipfw_obj_tentry *tent);
385 static void ta_foreach_radix(void *ta_state, struct table_info *ti,
386 ta_foreach_f *f, void *arg);
387 static void tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
388 struct sockaddr *ma, int *set_mask);
389 static int ta_prepare_add_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
391 static int ta_add_radix(void *ta_state, struct table_info *ti,
392 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
393 static int ta_prepare_del_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
395 static int ta_del_radix(void *ta_state, struct table_info *ti,
396 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
397 static void ta_flush_radix_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
399 static int ta_need_modify_radix(void *ta_state, struct table_info *ti,
400 uint32_t count, uint64_t *pflags);
403 ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
406 struct radix_node_head *rnh;
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));
420 struct radix_addr_xentry *xent;
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));
439 ta_init_radix(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
440 char *data, uint8_t tflags)
442 struct radix_cfg *cfg;
444 if (!rn_inithead(&ti->state, OFF_LEN_INET))
446 if (!rn_inithead(&ti->xstate, OFF_LEN_INET6)) {
447 rn_detachhead(&ti->state);
451 cfg = malloc(sizeof(struct radix_cfg), M_IPFW, M_WAITOK | M_ZERO);
454 ti->lookup = ta_lookup_radix;
460 flush_radix_entry(struct radix_node *rn, void *arg)
462 struct radix_node_head * const rnh = arg;
463 struct radix_addr_entry *ent;
465 ent = (struct radix_addr_entry *)
466 rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, &rnh->rh);
468 free(ent, M_IPFW_TBL);
473 ta_destroy_radix(void *ta_state, struct table_info *ti)
475 struct radix_cfg *cfg;
476 struct radix_node_head *rnh;
478 cfg = (struct radix_cfg *)ta_state;
480 rnh = (struct radix_node_head *)(ti->state);
481 rnh->rnh_walktree(&rnh->rh, flush_radix_entry, rnh);
482 rn_detachhead(&ti->state);
484 rnh = (struct radix_node_head *)(ti->xstate);
485 rnh->rnh_walktree(&rnh->rh, flush_radix_entry, rnh);
486 rn_detachhead(&ti->xstate);
492 * Provide algo-specific table info
495 ta_dump_radix_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
497 struct radix_cfg *cfg;
499 cfg = (struct radix_cfg *)ta_state;
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);
511 ta_dump_radix_tentry(void *ta_state, struct table_info *ti, void *e,
512 ipfw_obj_tentry *tent)
514 struct radix_addr_entry *n;
516 struct radix_addr_xentry *xn;
519 n = (struct radix_addr_entry *)e;
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;
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;
542 ta_find_radix_tentry(void *ta_state, struct table_info *ti,
543 ipfw_obj_tentry *tent)
545 struct radix_node_head *rnh;
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);
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);
564 ta_dump_radix_tentry(ta_state, ti, e, tent);
572 ta_foreach_radix(void *ta_state, struct table_info *ti, ta_foreach_f *f,
575 struct radix_node_head *rnh;
577 rnh = (struct radix_node_head *)(ti->state);
578 rnh->rnh_walktree(&rnh->rh, (walktree_f_t *)f, arg);
580 rnh = (struct radix_node_head *)(ti->xstate);
581 rnh->rnh_walktree(&rnh->rh, (walktree_f_t *)f, arg);
586 static inline void ipv6_writemask(struct in6_addr *addr6, uint8_t mask);
589 ipv6_writemask(struct in6_addr *addr6, uint8_t mask)
593 for (cp = (uint32_t *)addr6; mask >= 32; mask -= 32)
596 *cp = htonl(mask ? ~((1 << (32 - mask)) - 1) : 0);
601 tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
602 struct sockaddr *ma, int *set_mask)
606 struct sockaddr_in *addr, *mask;
609 struct sa_in6 *addr6, *mask6;
615 if (tei->subtype == AF_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;
633 } else if (tei->subtype == AF_INET6) {
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);
653 ta_prepare_add_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
656 struct ta_buf_radix *tb;
657 struct radix_addr_entry *ent;
659 struct radix_addr_xentry *xent;
661 struct sockaddr *addr, *mask;
664 tb = (struct ta_buf_radix *)ta_buf;
669 if (tei->subtype == AF_INET) {
673 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
676 addr = (struct sockaddr *)&ent->addr;
677 mask = (struct sockaddr *)&tb->addr.a4.ma;
681 } else if (tei->subtype == AF_INET6) {
685 xent = malloc(sizeof(*xent), M_IPFW_TBL, M_WAITOK | M_ZERO);
686 xent->masklen = mlen;
688 addr = (struct sockaddr *)&xent->addr6;
689 mask = (struct sockaddr *)&tb->addr.a6.ma;
693 /* Unknown CIDR type */
697 tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
707 ta_add_radix(void *ta_state, struct table_info *ti, struct tentry_info *tei,
708 void *ta_buf, uint32_t *pnum)
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;
716 cfg = (struct radix_cfg *)ta_state;
717 tb = (struct ta_buf_radix *)ta_buf;
719 /* Save current entry value from @tei */
720 if (tei->subtype == AF_INET) {
722 ((struct radix_addr_entry *)tb->ent_ptr)->value = tei->value;
725 ((struct radix_addr_xentry *)tb->ent_ptr)->value = tei->value;
728 /* Search for an entry first */
729 rn = rnh->rnh_lookup(tb->addr_ptr, tb->mask_ptr, &rnh->rh);
731 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
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;
737 old_value = &((struct radix_addr_xentry *)rn)->value;
740 *old_value = tei->value;
743 /* Indicate that update has happened instead of addition */
744 tei->flags |= TEI_FLAGS_UPDATED;
750 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
753 rn = rnh->rnh_addaddr(tb->addr_ptr, tb->mask_ptr, &rnh->rh,tb->ent_ptr);
759 if (tei->subtype == AF_INET)
770 ta_prepare_del_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
773 struct ta_buf_radix *tb;
774 struct sockaddr *addr, *mask;
777 tb = (struct ta_buf_radix *)ta_buf;
782 if (tei->subtype == AF_INET) {
786 addr = (struct sockaddr *)&tb->addr.a4.sa;
787 mask = (struct sockaddr *)&tb->addr.a4.ma;
789 } else if (tei->subtype == AF_INET6) {
793 addr = (struct sockaddr *)&tb->addr.a6.sa;
794 mask = (struct sockaddr *)&tb->addr.a6.ma;
799 tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
808 ta_del_radix(void *ta_state, struct table_info *ti, struct tentry_info *tei,
809 void *ta_buf, uint32_t *pnum)
811 struct radix_cfg *cfg;
812 struct radix_node_head *rnh;
813 struct radix_node *rn;
814 struct ta_buf_radix *tb;
816 cfg = (struct radix_cfg *)ta_state;
817 tb = (struct ta_buf_radix *)ta_buf;
819 if (tei->subtype == AF_INET)
824 rn = rnh->rnh_deladdr(tb->addr_ptr, tb->mask_ptr, &rnh->rh);
829 /* Save entry value to @tei */
830 if (tei->subtype == AF_INET)
831 tei->value = ((struct radix_addr_entry *)rn)->value;
833 tei->value = ((struct radix_addr_xentry *)rn)->value;
837 if (tei->subtype == AF_INET)
847 ta_flush_radix_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
850 struct ta_buf_radix *tb;
852 tb = (struct ta_buf_radix *)ta_buf;
854 if (tb->ent_ptr != NULL)
855 free(tb->ent_ptr, M_IPFW_TBL);
859 ta_need_modify_radix(void *ta_state, struct table_info *ti, uint32_t count,
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
872 struct 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,
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,
897 * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
900 * inv.mask4: 32 - mask
902 * 1) _slow lookup: mask
903 * 2) _aligned: (128 - mask) / 8
914 SLIST_HEAD(chashbhead, chashentry);
917 struct chashbhead *head4;
918 struct chashbhead *head6;
928 SLIST_ENTRY(chashentry) next;
932 uint32_t a4; /* Host format */
933 struct in6_addr a6; /* Network format */
940 struct chashentry ent;
944 static __inline uint32_t hash_ip(uint32_t addr, int hsize);
947 static __inline uint32_t hash_ip6(struct in6_addr *addr6, int hsize);
948 static __inline uint16_t hash_ip64(struct in6_addr *addr6, int hsize);
949 static __inline uint32_t hash_ip6_slow(struct in6_addr *addr6, void *key,
950 int mask, int hsize);
951 static __inline uint32_t hash_ip6_al(struct in6_addr *addr6, void *key, int mask,
954 static int ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
956 static int ta_lookup_chash_aligned(struct table_info *ti, void *key,
957 uint32_t keylen, uint32_t *val);
958 static int ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
960 static int chash_parse_opts(struct chash_cfg *cfg, char *data);
961 static void ta_print_chash_config(void *ta_state, struct table_info *ti,
962 char *buf, size_t bufsize);
963 static int ta_log2(uint32_t v);
964 static int ta_init_chash(struct ip_fw_chain *ch, void **ta_state,
965 struct table_info *ti, char *data, uint8_t tflags);
966 static void ta_destroy_chash(void *ta_state, struct table_info *ti);
967 static void ta_dump_chash_tinfo(void *ta_state, struct table_info *ti,
968 ipfw_ta_tinfo *tinfo);
969 static int ta_dump_chash_tentry(void *ta_state, struct table_info *ti,
970 void *e, ipfw_obj_tentry *tent);
971 static uint32_t hash_ent(struct chashentry *ent, int af, int mlen,
973 static int tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent);
974 static int ta_find_chash_tentry(void *ta_state, struct table_info *ti,
975 ipfw_obj_tentry *tent);
976 static void ta_foreach_chash(void *ta_state, struct table_info *ti,
977 ta_foreach_f *f, void *arg);
978 static int ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
980 static int ta_add_chash(void *ta_state, struct table_info *ti,
981 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
982 static int ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
984 static int ta_del_chash(void *ta_state, struct table_info *ti,
985 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
986 static void ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
988 static int ta_need_modify_chash(void *ta_state, struct table_info *ti,
989 uint32_t count, uint64_t *pflags);
990 static int ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags);
991 static int ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
993 static void ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
995 static void ta_flush_mod_chash(void *ta_buf);
999 static __inline uint32_t
1000 hash_ip(uint32_t addr, int hsize)
1003 return (addr % (hsize - 1));
1008 static __inline uint32_t
1009 hash_ip6(struct in6_addr *addr6, int hsize)
1013 i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1] ^
1014 addr6->s6_addr32[2] ^ addr6->s6_addr32[3];
1016 return (i % (hsize - 1));
1020 static __inline uint16_t
1021 hash_ip64(struct in6_addr *addr6, int hsize)
1025 i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1];
1027 return (i % (hsize - 1));
1031 static __inline uint32_t
1032 hash_ip6_slow(struct in6_addr *addr6, void *key, int mask, int hsize)
1034 struct in6_addr mask6;
1036 ipv6_writemask(&mask6, mask);
1037 memcpy(addr6, key, sizeof(struct in6_addr));
1038 APPLY_MASK(addr6, &mask6);
1039 return (hash_ip6(addr6, hsize));
1042 static __inline uint32_t
1043 hash_ip6_al(struct in6_addr *addr6, void *key, int mask, int hsize)
1047 paddr = (uint64_t *)addr6;
1050 memcpy(addr6, key, mask);
1051 return (hash_ip6(addr6, hsize));
1056 ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
1059 struct chashbhead *head;
1060 struct chashentry *ent;
1061 uint16_t hash, hsize;
1064 if (keylen == sizeof(in_addr_t)) {
1066 head = (struct chashbhead *)ti->state;
1067 imask = ti->data >> 24;
1068 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1070 a = ntohl(*((in_addr_t *)key));
1072 hash = hash_ip(a, hsize);
1073 SLIST_FOREACH(ent, &head[hash], next) {
1074 if (ent->a.a4 == a) {
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) {
1101 ta_lookup_chash_aligned(struct table_info *ti, void *key, uint32_t keylen,
1104 struct chashbhead *head;
1105 struct chashentry *ent;
1106 uint16_t hash, hsize;
1109 if (keylen == sizeof(in_addr_t)) {
1111 head = (struct chashbhead *)ti->state;
1112 imask = ti->data >> 24;
1113 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1115 a = ntohl(*((in_addr_t *)key));
1117 hash = hash_ip(a, hsize);
1118 SLIST_FOREACH(ent, &head[hash], next) {
1119 if (ent->a.a4 == a) {
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);
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]) {
1150 ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
1153 struct chashbhead *head;
1154 struct chashentry *ent;
1155 uint16_t hash, hsize;
1158 if (keylen == sizeof(in_addr_t)) {
1160 head = (struct chashbhead *)ti->state;
1161 imask = ti->data >> 24;
1162 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
1164 a = ntohl(*((in_addr_t *)key));
1166 hash = hash_ip(a, hsize);
1167 SLIST_FOREACH(ent, &head[hash], next) {
1168 if (ent->a.a4 == a) {
1177 uint64_t a6, *paddr;
1178 head = (struct chashbhead *)ti->xstate;
1179 paddr = (uint64_t *)key;
1180 hsize = 1 << (ti->data & 0xFF);
1182 hash = hash_ip64((struct in6_addr *)key, hsize);
1183 SLIST_FOREACH(ent, &head[hash], next) {
1184 paddr = (uint64_t *)&ent->a.a6;
1197 chash_parse_opts(struct chash_cfg *cfg, char *data)
1199 char *pdel, *pend, *s;
1207 if ((pdel = strchr(data, ' ')) == NULL)
1209 while (*pdel == ' ')
1211 if (strncmp(pdel, "masks=", 6) != 0)
1213 if ((s = strchr(pdel, ' ')) != NULL)
1217 /* Need /XX[,/YY] */
1220 mask4 = strtol(pdel, &pend, 10);
1226 mask6 = strtol(pdel, &pend, 10);
1229 } else if (*pend != '\0')
1232 if (mask4 < 0 || mask4 > 32 || mask6 < 0 || mask6 > 128)
1242 ta_print_chash_config(void *ta_state, struct table_info *ti, char *buf,
1245 struct chash_cfg *cfg;
1247 cfg = (struct chash_cfg *)ta_state;
1249 if (cfg->mask4 != 32 || cfg->mask6 != 128)
1250 snprintf(buf, bufsize, "%s masks=/%d,/%d", "addr:hash",
1251 cfg->mask4, cfg->mask6);
1253 snprintf(buf, bufsize, "%s", "addr:hash");
1270 * We assume 'data' to be either NULL or the following format:
1271 * 'addr:hash [masks=/32[,/128]]'
1274 ta_init_chash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
1275 char *data, uint8_t tflags)
1279 struct chash_cfg *cfg;
1281 cfg = malloc(sizeof(struct chash_cfg), M_IPFW, M_WAITOK | M_ZERO);
1286 if ((error = chash_parse_opts(cfg, data)) != 0) {
1294 cfg->head4 = malloc(sizeof(struct chashbhead) * cfg->size4, M_IPFW,
1296 cfg->head6 = malloc(sizeof(struct chashbhead) * cfg->size6, M_IPFW,
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]);
1305 ti->state = cfg->head4;
1306 ti->xstate = cfg->head6;
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|
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;
1319 /* don't do that! */
1320 ti->data = (32 - cfg->mask4) << 24 |
1321 cfg->mask6 << 16 | hsize;
1322 ti->lookup = ta_lookup_chash_slow;
1329 ta_destroy_chash(void *ta_state, struct table_info *ti)
1331 struct chash_cfg *cfg;
1332 struct chashentry *ent, *ent_next;
1335 cfg = (struct chash_cfg *)ta_state;
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);
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);
1345 free(cfg->head4, M_IPFW);
1346 free(cfg->head6, M_IPFW);
1352 ta_dump_chash_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
1354 struct chash_cfg *cfg;
1356 cfg = (struct chash_cfg *)ta_state;
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);
1370 ta_dump_chash_tentry(void *ta_state, struct table_info *ti, void *e,
1371 ipfw_obj_tentry *tent)
1373 struct chash_cfg *cfg;
1374 struct chashentry *ent;
1376 cfg = (struct chash_cfg *)ta_state;
1377 ent = (struct chashentry *)e;
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;
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;
1397 hash_ent(struct chashentry *ent, int af, int mlen, uint32_t size)
1403 if (af == AF_INET) {
1405 hash = hash_ip(ent->a.a4, size);
1410 hash = hash_ip64(&ent->a.a6, size);
1412 hash = hash_ip6(&ent->a.a6, size);
1420 tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent)
1424 struct in6_addr mask6;
1428 mlen = tei->masklen;
1430 if (tei->subtype == AF_INET) {
1434 ent->type = AF_INET;
1436 /* Calculate masked address */
1437 ent->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1440 } else if (tei->subtype == AF_INET6) {
1444 ent->type = AF_INET6;
1446 ipv6_writemask(&mask6, mlen);
1447 memcpy(&ent->a.a6, tei->paddr, sizeof(struct in6_addr));
1448 APPLY_MASK(&ent->a.a6, &mask6);
1451 /* Unknown CIDR type */
1459 ta_find_chash_tentry(void *ta_state, struct table_info *ti,
1460 ipfw_obj_tentry *tent)
1462 struct chash_cfg *cfg;
1463 struct chashbhead *head;
1464 struct chashentry ent, *tmp;
1465 struct tentry_info tei;
1469 cfg = (struct chash_cfg *)ta_state;
1471 memset(&ent, 0, sizeof(ent));
1472 memset(&tei, 0, sizeof(tei));
1474 if (tent->subtype == AF_INET) {
1475 tei.paddr = &tent->k.addr;
1476 tei.masklen = cfg->mask4;
1477 tei.subtype = AF_INET;
1479 if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
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)
1489 ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1493 tei.paddr = &tent->k.addr6;
1494 tei.masklen = cfg->mask6;
1495 tei.subtype = AF_INET6;
1497 if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
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)
1506 ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1515 ta_foreach_chash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
1518 struct chash_cfg *cfg;
1519 struct chashentry *ent, *ent_next;
1522 cfg = (struct chash_cfg *)ta_state;
1524 for (i = 0; i < cfg->size4; i++)
1525 SLIST_FOREACH_SAFE(ent, &cfg->head4[i], next, ent_next)
1528 for (i = 0; i < cfg->size6; i++)
1529 SLIST_FOREACH_SAFE(ent, &cfg->head6[i], next, ent_next)
1534 ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1537 struct ta_buf_chash *tb;
1538 struct chashentry *ent;
1541 tb = (struct ta_buf_chash *)ta_buf;
1543 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1545 error = tei_to_chash_ent(tei, ent);
1547 free(ent, M_IPFW_TBL);
1556 ta_add_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1557 void *ta_buf, uint32_t *pnum)
1559 struct chash_cfg *cfg;
1560 struct chashbhead *head;
1561 struct chashentry *ent, *tmp;
1562 struct ta_buf_chash *tb;
1564 uint32_t hash, value;
1566 cfg = (struct chash_cfg *)ta_state;
1567 tb = (struct ta_buf_chash *)ta_buf;
1568 ent = (struct chashentry *)tb->ent_ptr;
1572 /* Read current value from @tei */
1573 ent->value = tei->value;
1575 /* Read cuurrent value */
1576 if (tei->subtype == AF_INET) {
1577 if (tei->masklen != cfg->mask4)
1580 hash = hash_ent(ent, AF_INET, cfg->mask4, cfg->size4);
1582 /* Check for existence */
1583 SLIST_FOREACH(tmp, &head[hash], next) {
1584 if (tmp->a.a4 == ent->a.a4) {
1590 if (tei->masklen != cfg->mask6)
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) {
1604 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1606 /* Record already exists. Update value if we're asked to */
1608 tmp->value = tei->value;
1610 /* Indicate that update has happened instead of addition */
1611 tei->flags |= TEI_FLAGS_UPDATED;
1614 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
1616 SLIST_INSERT_HEAD(&head[hash], ent, next);
1620 /* Update counters */
1621 if (tei->subtype == AF_INET)
1631 ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1634 struct ta_buf_chash *tb;
1636 tb = (struct ta_buf_chash *)ta_buf;
1638 return (tei_to_chash_ent(tei, &tb->ent));
1642 ta_del_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1643 void *ta_buf, uint32_t *pnum)
1645 struct chash_cfg *cfg;
1646 struct chashbhead *head;
1647 struct chashentry *tmp, *tmp_next, *ent;
1648 struct ta_buf_chash *tb;
1651 cfg = (struct chash_cfg *)ta_state;
1652 tb = (struct ta_buf_chash *)ta_buf;
1655 if (tei->subtype == AF_INET) {
1656 if (tei->masklen != cfg->mask4)
1659 hash = hash_ent(ent, AF_INET, cfg->mask4, cfg->size4);
1661 SLIST_FOREACH_SAFE(tmp, &head[hash], next, tmp_next) {
1662 if (tmp->a.a4 != ent->a.a4)
1665 SLIST_REMOVE(&head[hash], tmp, chashentry, next);
1668 tei->value = tmp->value;
1673 if (tei->masklen != cfg->mask6)
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)
1681 SLIST_REMOVE(&head[hash], tmp, chashentry, next);
1684 tei->value = tmp->value;
1694 ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1697 struct ta_buf_chash *tb;
1699 tb = (struct ta_buf_chash *)ta_buf;
1701 if (tb->ent_ptr != NULL)
1702 free(tb->ent_ptr, M_IPFW_TBL);
1706 * Hash growing callbacks.
1710 ta_need_modify_chash(void *ta_state, struct table_info *ti, uint32_t count,
1713 struct chash_cfg *cfg;
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.
1722 cfg = (struct chash_cfg *)ta_state;
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;
1739 * Allocate new, larger chash.
1742 ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags)
1744 struct mod_item *mi;
1745 struct chashbhead *head;
1748 mi = (struct mod_item *)ta_buf;
1750 memset(mi, 0, sizeof(struct mod_item));
1751 mi->size = (*pflags >> 16) & 0xFFFF;
1752 mi->size6 = *pflags & 0xFFFF;
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;
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;
1773 * Copy data from old runtime array to new one.
1776 ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1780 /* In is not possible to do rehash if we're not holidng WLOCK. */
1785 * Switch old & new arrays.
1788 ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1791 struct mod_item *mi;
1792 struct chash_cfg *cfg;
1793 struct chashbhead *old_head, *new_head;
1794 struct chashentry *ent, *ent_next;
1797 size_t old_size, new_size;
1799 mi = (struct mod_item *)ta_buf;
1800 cfg = (struct chash_cfg *)ta_state;
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;
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);
1818 ti->state = new_head;
1819 cfg->head4 = new_head;
1820 cfg->size4 = mi->size;
1821 mi->main_ptr = old_head;
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;
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);
1839 ti->xstate = new_head;
1840 cfg->head6 = new_head;
1841 cfg->size6 = mi->size6;
1842 mi->main_ptr6 = old_head;
1845 /* Update lower 32 bits with new values */
1846 ti->data &= 0xFFFFFFFF00000000;
1847 ti->data |= ta_log2(cfg->size4) << 8 | ta_log2(cfg->size6);
1851 * Free unneded array.
1854 ta_flush_mod_chash(void *ta_buf)
1856 struct mod_item *mi;
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);
1865 struct 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,
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
1902 * - "struct iftable_cfg" is allocated to store table state (ta_state).
1903 * - All table records are stored inside namedobj instance.
1912 #define DEFAULT_IFIDX_SIZE 64
1917 struct named_object no;
1919 struct iftable_cfg *icfg;
1924 struct iftable_cfg {
1925 struct namedobj_instance *ii;
1926 struct ip_fw_chain *ch;
1927 struct table_info *ti;
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 */
1936 struct ifentry *ife;
1940 int compare_ifidx(const void *k, const void *v);
1941 static struct ifidx * ifidx_find(struct table_info *ti, void *key);
1942 static int ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
1944 static int ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state,
1945 struct table_info *ti, char *data, uint8_t tflags);
1946 static void ta_change_ti_ifidx(void *ta_state, struct table_info *ti);
1947 static int destroy_ifidx_locked(struct namedobj_instance *ii,
1948 struct named_object *no, void *arg);
1949 static void ta_destroy_ifidx(void *ta_state, struct table_info *ti);
1950 static void ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti,
1951 ipfw_ta_tinfo *tinfo);
1952 static int ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1954 static int ta_add_ifidx(void *ta_state, struct table_info *ti,
1955 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1956 static int ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1958 static int ta_del_ifidx(void *ta_state, struct table_info *ti,
1959 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1960 static void ta_flush_ifidx_entry(struct ip_fw_chain *ch,
1961 struct tentry_info *tei, void *ta_buf);
1962 static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
1963 static int ta_need_modify_ifidx(void *ta_state, struct table_info *ti,
1964 uint32_t count, uint64_t *pflags);
1965 static int ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags);
1966 static int ta_fill_mod_ifidx(void *ta_state, struct table_info *ti,
1967 void *ta_buf, uint64_t *pflags);
1968 static void ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1970 static void ta_flush_mod_ifidx(void *ta_buf);
1971 static int ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
1972 ipfw_obj_tentry *tent);
1973 static int ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
1974 ipfw_obj_tentry *tent);
1975 static int foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
1977 static void ta_foreach_ifidx(void *ta_state, struct table_info *ti,
1978 ta_foreach_f *f, void *arg);
1981 compare_ifidx(const void *k, const void *v)
1983 const struct ifidx *ifidx;
1986 key = *((const uint16_t *)k);
1987 ifidx = (const struct ifidx *)v;
1989 if (key < ifidx->kidx)
1991 else if (key > ifidx->kidx)
1998 * Adds item @item with key @key into ascending-sorted array @base.
1999 * Assumes @base has enough additional storage.
2001 * Returns 1 on success, 0 on duplicate key.
2004 badd(const void *key, void *item, void *base, size_t nmemb,
2005 size_t size, int (*compar) (const void *, const void *))
2007 int min, max, mid, shift, res;
2011 memcpy(base, item, size);
2019 while (min <= max) {
2020 mid = (min + max) / 2;
2021 res = compar(key, (const void *)((caddr_t)base + mid * size));
2031 /* Item not found. */
2032 res = compar(key, (const void *)((caddr_t)base + mid * size));
2038 paddr = (caddr_t)base + shift * size;
2040 memmove(paddr + size, paddr, (nmemb - shift) * size);
2042 memcpy(paddr, item, size);
2048 * Deletes item with key @key from ascending-sorted array @base.
2050 * Returns 1 on success, 0 for non-existent key.
2053 bdel(const void *key, void *base, size_t nmemb, size_t size,
2054 int (*compar) (const void *, const void *))
2059 item = (caddr_t)bsearch(key, base, nmemb, size, compar);
2064 sz = (caddr_t)base + nmemb * size - item;
2067 memmove(item, item + size, sz);
2072 static struct ifidx *
2073 ifidx_find(struct table_info *ti, void *key)
2077 ifi = bsearch(key, ti->state, ti->data, sizeof(struct ifidx),
2084 ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
2089 ifi = ifidx_find(ti, key);
2100 ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2101 char *data, uint8_t tflags)
2103 struct iftable_cfg *icfg;
2105 icfg = malloc(sizeof(struct iftable_cfg), M_IPFW, M_WAITOK | M_ZERO);
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,
2114 ti->state = icfg->main_ptr;
2115 ti->lookup = ta_lookup_ifidx;
2121 * Handle tableinfo @ti pointer change (on table array resize).
2124 ta_change_ti_ifidx(void *ta_state, struct table_info *ti)
2126 struct iftable_cfg *icfg;
2128 icfg = (struct iftable_cfg *)ta_state;
2133 destroy_ifidx_locked(struct namedobj_instance *ii, struct named_object *no,
2136 struct ifentry *ife;
2137 struct ip_fw_chain *ch;
2139 ch = (struct ip_fw_chain *)arg;
2140 ife = (struct ifentry *)no;
2142 ipfw_iface_del_notify(ch, &ife->ic);
2143 ipfw_iface_unref(ch, &ife->ic);
2144 free(ife, M_IPFW_TBL);
2150 * Destroys table @ti
2153 ta_destroy_ifidx(void *ta_state, struct table_info *ti)
2155 struct iftable_cfg *icfg;
2156 struct ip_fw_chain *ch;
2158 icfg = (struct iftable_cfg *)ta_state;
2161 if (icfg->main_ptr != NULL)
2162 free(icfg->main_ptr, M_IPFW);
2165 ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
2166 IPFW_UH_WUNLOCK(ch);
2168 ipfw_objhash_destroy(icfg->ii);
2174 * Provide algo-specific table info
2177 ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2179 struct iftable_cfg *cfg;
2181 cfg = (struct iftable_cfg *)ta_state;
2183 tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2184 tinfo->size4 = cfg->size;
2185 tinfo->count4 = cfg->used;
2186 tinfo->itemsize4 = sizeof(struct ifidx);
2190 * Prepare state to add to the table:
2191 * allocate ifentry and reference needed interface.
2194 ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2197 struct ta_buf_ifidx *tb;
2199 struct ifentry *ife;
2201 tb = (struct ta_buf_ifidx *)ta_buf;
2203 /* Check if string is terminated */
2204 ifname = (char *)tei->paddr;
2205 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2208 ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
2209 ife->ic.cb = if_notifier;
2210 ife->ic.cbdata = ife;
2212 if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0) {
2213 free(ife, M_IPFW_TBL);
2217 /* Use ipfw_iface 'ifname' field as stable storage */
2218 ife->no.name = ife->ic.iface->ifname;
2226 ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2227 void *ta_buf, uint32_t *pnum)
2229 struct iftable_cfg *icfg;
2230 struct ifentry *ife, *tmp;
2231 struct ta_buf_ifidx *tb;
2232 struct ipfw_iface *iif;
2237 tb = (struct ta_buf_ifidx *)ta_buf;
2238 ifname = (char *)tei->paddr;
2239 icfg = (struct iftable_cfg *)ta_state;
2243 ife->value = tei->value;
2245 tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2248 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2251 /* Exchange values in @tmp and @tei */
2253 tmp->value = tei->value;
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;
2263 /* Indicate that update has happened instead of addition */
2264 tei->flags |= TEI_FLAGS_UPDATED;
2269 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2272 /* Link to internal list */
2273 ipfw_objhash_add(icfg->ii, &ife->no);
2275 /* Link notifier (possible running its callback) */
2276 ipfw_iface_add_notify(icfg->ch, &ife->ic);
2286 * Prepare to delete key from table.
2287 * Do basic interface name checks.
2290 ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2293 struct ta_buf_ifidx *tb;
2296 tb = (struct ta_buf_ifidx *)ta_buf;
2298 /* Check if string is terminated */
2299 ifname = (char *)tei->paddr;
2300 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2307 * Remove key from both configuration list and
2308 * runtime array. Removed interface notification.
2311 ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2312 void *ta_buf, uint32_t *pnum)
2314 struct iftable_cfg *icfg;
2315 struct ifentry *ife;
2316 struct ta_buf_ifidx *tb;
2321 tb = (struct ta_buf_ifidx *)ta_buf;
2322 ifname = (char *)tei->paddr;
2323 icfg = (struct iftable_cfg *)ta_state;
2325 ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2330 if (ife->linked != 0) {
2331 /* We have to remove item from runtime */
2332 ifindex = ife->ic.iface->ifindex;
2334 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2335 sizeof(struct ifidx), compare_ifidx);
2337 KASSERT(res == 1, ("index %d does not exist", ifindex));
2339 ti->data = icfg->used;
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);
2350 tei->value = ife->value;
2359 * Flush deleted entry.
2360 * Drops interface reference and frees entry.
2363 ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2366 struct ta_buf_ifidx *tb;
2368 tb = (struct ta_buf_ifidx *)ta_buf;
2370 if (tb->ife != NULL)
2371 free(tb->ife, M_IPFW_TBL);
2376 * Handle interface announce/withdrawal for particular table.
2377 * Every real runtime array modification happens here.
2380 if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
2382 struct ifentry *ife;
2384 struct iftable_cfg *icfg;
2385 struct table_info *ti;
2388 ife = (struct ifentry *)cbdata;
2392 KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
2394 if (ife->linked == 0 && ifindex != 0) {
2395 /* Interface announce */
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));
2403 ti->data = icfg->used;
2405 } else if (ife->linked != 0 && ifindex == 0) {
2406 /* Interface withdrawal */
2407 ifindex = ife->ic.iface->ifindex;
2409 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2410 sizeof(struct ifidx), compare_ifidx);
2412 KASSERT(res == 1, ("index %d does not exist", ifindex));
2414 ti->data = icfg->used;
2421 * Table growing callbacks.
2425 ta_need_modify_ifidx(void *ta_state, struct table_info *ti, uint32_t count,
2428 struct iftable_cfg *cfg;
2431 cfg = (struct iftable_cfg *)ta_state;
2434 while (size < cfg->count + count)
2437 if (size != cfg->size) {
2446 * Allocate ned, larger runtime ifidx array.
2449 ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
2451 struct mod_item *mi;
2453 mi = (struct mod_item *)ta_buf;
2455 memset(mi, 0, sizeof(struct mod_item));
2457 mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
2464 * Copy data from old runtime array to new one.
2467 ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2470 struct mod_item *mi;
2471 struct iftable_cfg *icfg;
2473 mi = (struct mod_item *)ta_buf;
2474 icfg = (struct iftable_cfg *)ta_state;
2476 /* Check if we still need to grow array */
2477 if (icfg->size >= mi->size) {
2482 memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
2488 * Switch old & new arrays.
2491 ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2494 struct mod_item *mi;
2495 struct iftable_cfg *icfg;
2498 mi = (struct mod_item *)ta_buf;
2499 icfg = (struct iftable_cfg *)ta_state;
2501 old_ptr = icfg->main_ptr;
2502 icfg->main_ptr = mi->main_ptr;
2503 icfg->size = mi->size;
2504 ti->state = icfg->main_ptr;
2506 mi->main_ptr = old_ptr;
2510 * Free unneded array.
2513 ta_flush_mod_ifidx(void *ta_buf)
2515 struct mod_item *mi;
2517 mi = (struct mod_item *)ta_buf;
2518 if (mi->main_ptr != NULL)
2519 free(mi->main_ptr, M_IPFW);
2523 ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
2524 ipfw_obj_tentry *tent)
2526 struct ifentry *ife;
2528 ife = (struct ifentry *)e;
2530 tent->masklen = 8 * IF_NAMESIZE;
2531 memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
2532 tent->v.kidx = ife->value;
2538 ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
2539 ipfw_obj_tentry *tent)
2541 struct iftable_cfg *icfg;
2542 struct ifentry *ife;
2545 icfg = (struct iftable_cfg *)ta_state;
2546 ifname = tent->k.iface;
2548 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2551 ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2554 ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
2567 foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
2570 struct ifentry *ife;
2571 struct wa_ifidx *wa;
2573 ife = (struct ifentry *)no;
2574 wa = (struct wa_ifidx *)arg;
2576 wa->f(ife, wa->arg);
2581 ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2584 struct iftable_cfg *icfg;
2587 icfg = (struct iftable_cfg *)ta_state;
2592 ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
2595 struct 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,
2620 * Number array cmds.
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
2636 struct numarray_cfg {
2638 size_t size; /* Number of items allocated in array */
2639 size_t used; /* Number of items _active_ now */
2642 struct ta_buf_numarray
2647 int compare_numarray(const void *k, const void *v);
2648 static struct numarray *numarray_find(struct table_info *ti, void *key);
2649 static int ta_lookup_numarray(struct table_info *ti, void *key,
2650 uint32_t keylen, uint32_t *val);
2651 static int ta_init_numarray(struct ip_fw_chain *ch, void **ta_state,
2652 struct table_info *ti, char *data, uint8_t tflags);
2653 static void ta_destroy_numarray(void *ta_state, struct table_info *ti);
2654 static void ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti,
2655 ipfw_ta_tinfo *tinfo);
2656 static int ta_prepare_add_numarray(struct ip_fw_chain *ch,
2657 struct tentry_info *tei, void *ta_buf);
2658 static int ta_add_numarray(void *ta_state, struct table_info *ti,
2659 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2660 static int ta_del_numarray(void *ta_state, struct table_info *ti,
2661 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2662 static void ta_flush_numarray_entry(struct ip_fw_chain *ch,
2663 struct tentry_info *tei, void *ta_buf);
2664 static int ta_need_modify_numarray(void *ta_state, struct table_info *ti,
2665 uint32_t count, uint64_t *pflags);
2666 static int ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags);
2667 static int ta_fill_mod_numarray(void *ta_state, struct table_info *ti,
2668 void *ta_buf, uint64_t *pflags);
2669 static void ta_modify_numarray(void *ta_state, struct table_info *ti,
2670 void *ta_buf, uint64_t pflags);
2671 static void ta_flush_mod_numarray(void *ta_buf);
2672 static int ta_dump_numarray_tentry(void *ta_state, struct table_info *ti,
2673 void *e, ipfw_obj_tentry *tent);
2674 static int ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2675 ipfw_obj_tentry *tent);
2676 static void ta_foreach_numarray(void *ta_state, struct table_info *ti,
2677 ta_foreach_f *f, void *arg);
2680 compare_numarray(const void *k, const void *v)
2682 const struct numarray *na;
2685 key = *((const uint32_t *)k);
2686 na = (const struct numarray *)v;
2688 if (key < na->number)
2690 else if (key > na->number)
2696 static struct numarray *
2697 numarray_find(struct table_info *ti, void *key)
2699 struct numarray *ri;
2701 ri = bsearch(key, ti->state, ti->data, sizeof(struct numarray),
2708 ta_lookup_numarray(struct table_info *ti, void *key, uint32_t keylen,
2711 struct numarray *ri;
2713 ri = numarray_find(ti, key);
2724 ta_init_numarray(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2725 char *data, uint8_t tflags)
2727 struct numarray_cfg *cfg;
2729 cfg = malloc(sizeof(*cfg), M_IPFW, M_WAITOK | M_ZERO);
2732 cfg->main_ptr = malloc(sizeof(struct numarray) * cfg->size, M_IPFW,
2736 ti->state = cfg->main_ptr;
2737 ti->lookup = ta_lookup_numarray;
2743 * Destroys table @ti
2746 ta_destroy_numarray(void *ta_state, struct table_info *ti)
2748 struct numarray_cfg *cfg;
2750 cfg = (struct numarray_cfg *)ta_state;
2752 if (cfg->main_ptr != NULL)
2753 free(cfg->main_ptr, M_IPFW);
2759 * Provide algo-specific table info
2762 ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2764 struct numarray_cfg *cfg;
2766 cfg = (struct numarray_cfg *)ta_state;
2768 tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2769 tinfo->size4 = cfg->size;
2770 tinfo->count4 = cfg->used;
2771 tinfo->itemsize4 = sizeof(struct numarray);
2775 * Prepare for addition/deletion to an array.
2778 ta_prepare_add_numarray(struct ip_fw_chain *ch, struct tentry_info *tei,
2781 struct ta_buf_numarray *tb;
2783 tb = (struct ta_buf_numarray *)ta_buf;
2785 tb->na.number = *((uint32_t *)tei->paddr);
2791 ta_add_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2792 void *ta_buf, uint32_t *pnum)
2794 struct numarray_cfg *cfg;
2795 struct ta_buf_numarray *tb;
2796 struct numarray *ri;
2800 tb = (struct ta_buf_numarray *)ta_buf;
2801 cfg = (struct numarray_cfg *)ta_state;
2803 /* Read current value from @tei */
2804 tb->na.value = tei->value;
2806 ri = numarray_find(ti, &tb->na.number);
2809 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2812 /* Exchange values between ri and @tei */
2814 ri->value = tei->value;
2816 /* Indicate that update has happened instead of addition */
2817 tei->flags |= TEI_FLAGS_UPDATED;
2822 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2825 res = badd(&tb->na.number, &tb->na, cfg->main_ptr, cfg->used,
2826 sizeof(struct numarray), compare_numarray);
2828 KASSERT(res == 1, ("number %d already exists", tb->na.number));
2830 ti->data = cfg->used;
2837 * Remove key from both configuration list and
2838 * runtime array. Removed interface notification.
2841 ta_del_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2842 void *ta_buf, uint32_t *pnum)
2844 struct numarray_cfg *cfg;
2845 struct ta_buf_numarray *tb;
2846 struct numarray *ri;
2849 tb = (struct ta_buf_numarray *)ta_buf;
2850 cfg = (struct numarray_cfg *)ta_state;
2852 ri = numarray_find(ti, &tb->na.number);
2856 tei->value = ri->value;
2858 res = bdel(&tb->na.number, cfg->main_ptr, cfg->used,
2859 sizeof(struct numarray), compare_numarray);
2861 KASSERT(res == 1, ("number %u does not exist", tb->na.number));
2863 ti->data = cfg->used;
2870 ta_flush_numarray_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2874 /* We don't have any state, do nothing */
2879 * Table growing callbacks.
2883 ta_need_modify_numarray(void *ta_state, struct table_info *ti, uint32_t count,
2886 struct numarray_cfg *cfg;
2889 cfg = (struct numarray_cfg *)ta_state;
2892 while (size < cfg->used + count)
2895 if (size != cfg->size) {
2904 * Allocate new, larger runtime array.
2907 ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags)
2909 struct mod_item *mi;
2911 mi = (struct mod_item *)ta_buf;
2913 memset(mi, 0, sizeof(struct mod_item));
2915 mi->main_ptr = malloc(sizeof(struct numarray) * mi->size, M_IPFW,
2922 * Copy data from old runtime array to new one.
2925 ta_fill_mod_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2928 struct mod_item *mi;
2929 struct numarray_cfg *cfg;
2931 mi = (struct mod_item *)ta_buf;
2932 cfg = (struct numarray_cfg *)ta_state;
2934 /* Check if we still need to grow array */
2935 if (cfg->size >= mi->size) {
2940 memcpy(mi->main_ptr, cfg->main_ptr, cfg->used * sizeof(struct numarray));
2946 * Switch old & new arrays.
2949 ta_modify_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2952 struct mod_item *mi;
2953 struct numarray_cfg *cfg;
2956 mi = (struct mod_item *)ta_buf;
2957 cfg = (struct numarray_cfg *)ta_state;
2959 old_ptr = cfg->main_ptr;
2960 cfg->main_ptr = mi->main_ptr;
2961 cfg->size = mi->size;
2962 ti->state = cfg->main_ptr;
2964 mi->main_ptr = old_ptr;
2968 * Free unneded array.
2971 ta_flush_mod_numarray(void *ta_buf)
2973 struct mod_item *mi;
2975 mi = (struct mod_item *)ta_buf;
2976 if (mi->main_ptr != NULL)
2977 free(mi->main_ptr, M_IPFW);
2981 ta_dump_numarray_tentry(void *ta_state, struct table_info *ti, void *e,
2982 ipfw_obj_tentry *tent)
2984 struct numarray *na;
2986 na = (struct numarray *)e;
2988 tent->k.key = na->number;
2989 tent->v.kidx = na->value;
2995 ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2996 ipfw_obj_tentry *tent)
2998 struct numarray_cfg *cfg;
2999 struct numarray *ri;
3001 cfg = (struct numarray_cfg *)ta_state;
3003 ri = numarray_find(ti, &tent->k.key);
3006 ta_dump_numarray_tentry(ta_state, ti, ri, tent);
3014 ta_foreach_numarray(void *ta_state, struct table_info *ti, ta_foreach_f *f,
3017 struct numarray_cfg *cfg;
3018 struct numarray *array;
3021 cfg = (struct numarray_cfg *)ta_state;
3022 array = cfg->main_ptr;
3024 for (i = 0; i < cfg->used; i++)
3028 struct 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,
3055 * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
3058 * inv.mask4: 32 - mask
3060 * 1) _slow lookup: mask
3061 * 2) _aligned: (128 - mask) / 8
3072 SLIST_HEAD(fhashbhead, fhashentry);
3075 SLIST_ENTRY(fhashentry) next;
3085 struct fhashentry4 {
3086 struct fhashentry e;
3091 struct fhashentry6 {
3092 struct fhashentry e;
3093 struct in6_addr dip6;
3094 struct in6_addr sip6;
3098 struct fhashbhead *head;
3101 struct fhashentry4 fe4;
3102 struct fhashentry6 fe6;
3105 struct ta_buf_fhash {
3107 struct fhashentry6 fe6;
3110 static __inline int cmp_flow_ent(struct fhashentry *a,
3111 struct fhashentry *b, size_t sz);
3112 static __inline uint32_t hash_flow4(struct fhashentry4 *f, int hsize);
3113 static __inline uint32_t hash_flow6(struct fhashentry6 *f, int hsize);
3114 static uint32_t hash_flow_ent(struct fhashentry *ent, uint32_t size);
3115 static int ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3117 static int ta_init_fhash(struct ip_fw_chain *ch, void **ta_state,
3118 struct table_info *ti, char *data, uint8_t tflags);
3119 static void ta_destroy_fhash(void *ta_state, struct table_info *ti);
3120 static void ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti,
3121 ipfw_ta_tinfo *tinfo);
3122 static int ta_dump_fhash_tentry(void *ta_state, struct table_info *ti,
3123 void *e, ipfw_obj_tentry *tent);
3124 static int tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent);
3125 static int ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
3126 ipfw_obj_tentry *tent);
3127 static void ta_foreach_fhash(void *ta_state, struct table_info *ti,
3128 ta_foreach_f *f, void *arg);
3129 static int ta_prepare_add_fhash(struct ip_fw_chain *ch,
3130 struct tentry_info *tei, void *ta_buf);
3131 static int ta_add_fhash(void *ta_state, struct table_info *ti,
3132 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3133 static int ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3135 static int ta_del_fhash(void *ta_state, struct table_info *ti,
3136 struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3137 static void ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3139 static int ta_need_modify_fhash(void *ta_state, struct table_info *ti,
3140 uint32_t count, uint64_t *pflags);
3141 static int ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags);
3142 static int ta_fill_mod_fhash(void *ta_state, struct table_info *ti,
3143 void *ta_buf, uint64_t *pflags);
3144 static void ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3146 static void ta_flush_mod_fhash(void *ta_buf);
3149 cmp_flow_ent(struct fhashentry *a, struct fhashentry *b, size_t sz)
3153 ka = (uint64_t *)(&a->next + 1);
3154 kb = (uint64_t *)(&b->next + 1);
3156 if (*ka == *kb && (memcmp(a + 1, b + 1, sz) == 0))
3162 static __inline uint32_t
3163 hash_flow4(struct fhashentry4 *f, int hsize)
3167 i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport);
3169 return (i % (hsize - 1));
3172 static __inline uint32_t
3173 hash_flow6(struct fhashentry6 *f, int hsize)
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);
3183 return (i % (hsize - 1));
3187 hash_flow_ent(struct fhashentry *ent, uint32_t size)
3191 if (ent->af == AF_INET) {
3192 hash = hash_flow4((struct fhashentry4 *)ent, size);
3194 hash = hash_flow6((struct fhashentry6 *)ent, size);
3201 ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3204 struct fhashbhead *head;
3205 struct fhashentry *ent;
3206 struct fhashentry4 *m4;
3207 struct ipfw_flow_id *id;
3211 id = (struct ipfw_flow_id *)key;
3212 head = (struct fhashbhead *)ti->state;
3214 m4 = (struct fhashentry4 *)ti->xstate;
3216 if (id->addr_type == 4) {
3217 struct fhashentry4 f;
3219 /* Copy hash mask */
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) {
3234 } else if (id->addr_type == 6) {
3235 struct fhashentry6 f;
3238 /* Copy hash mask */
3239 f = *((struct fhashentry6 *)(m4 + 1));
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 */
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) {
3268 ta_init_fhash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
3269 char *data, uint8_t tflags)
3271 struct fhash_cfg *cfg;
3272 struct fhashentry4 *fe4;
3273 struct fhashentry6 *fe6;
3276 cfg = malloc(sizeof(struct fhash_cfg), M_IPFW, M_WAITOK | M_ZERO);
3280 cfg->head = malloc(sizeof(struct fhashbhead) * cfg->size, M_IPFW,
3282 for (i = 0; i < cfg->size; i++)
3283 SLIST_INIT(&cfg->head[i]);
3285 /* Fill in fe masks based on @tflags */
3288 if (tflags & IPFW_TFFLAG_SRCIP) {
3289 memset(&fe4->sip, 0xFF, sizeof(fe4->sip));
3290 memset(&fe6->sip6, 0xFF, sizeof(fe6->sip6));
3292 if (tflags & IPFW_TFFLAG_DSTIP) {
3293 memset(&fe4->dip, 0xFF, sizeof(fe4->dip));
3294 memset(&fe6->dip6, 0xFF, sizeof(fe6->dip6));
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));
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));
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));
3309 fe4->e.af = AF_INET;
3310 fe6->e.af = AF_INET6;
3313 ti->state = cfg->head;
3314 ti->xstate = &cfg->fe4;
3315 ti->data = cfg->size;
3316 ti->lookup = ta_lookup_fhash;
3322 ta_destroy_fhash(void *ta_state, struct table_info *ti)
3324 struct fhash_cfg *cfg;
3325 struct fhashentry *ent, *ent_next;
3328 cfg = (struct fhash_cfg *)ta_state;
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);
3334 free(cfg->head, M_IPFW);
3339 * Provide algo-specific table info
3342 ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
3344 struct fhash_cfg *cfg;
3346 cfg = (struct fhash_cfg *)ta_state;
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);
3357 ta_dump_fhash_tentry(void *ta_state, struct table_info *ti, void *e,
3358 ipfw_obj_tentry *tent)
3360 struct fhash_cfg *cfg;
3361 struct fhashentry *ent;
3362 struct fhashentry4 *fe4;
3364 struct fhashentry6 *fe6;
3366 struct tflow_entry *tfe;
3368 cfg = (struct fhash_cfg *)ta_state;
3369 ent = (struct fhashentry *)e;
3370 tfe = &tent->k.flow;
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;
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);
3386 fe6 = (struct fhashentry6 *)ent;
3387 tfe->a.a6.sip6 = fe6->sip6;
3388 tfe->a.a6.dip6 = fe6->dip6;
3389 tent->masklen = 128;
3397 tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent)
3400 struct fhashentry4 *fe4;
3403 struct fhashentry6 *fe6;
3405 struct tflow_entry *tfe;
3407 tfe = (struct tflow_entry *)tei->paddr;
3409 ent->af = tei->subtype;
3410 ent->proto = tfe->proto;
3411 ent->dport = ntohs(tfe->dport);
3412 ent->sport = ntohs(tfe->sport);
3414 if (tei->subtype == AF_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);
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;
3427 /* Unknown CIDR type */
3436 ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
3437 ipfw_obj_tentry *tent)
3439 struct fhash_cfg *cfg;
3440 struct fhashbhead *head;
3441 struct fhashentry *ent, *tmp;
3442 struct fhashentry6 fe6;
3443 struct tentry_info tei;
3448 cfg = (struct fhash_cfg *)ta_state;
3452 memset(&fe6, 0, sizeof(fe6));
3453 memset(&tei, 0, sizeof(tei));
3455 tei.paddr = &tent->k.flow;
3456 tei.subtype = tent->subtype;
3458 if ((error = tei_to_fhash_ent(&tei, ent)) != 0)
3462 hash = hash_flow_ent(ent, cfg->size);
3464 if (tei.subtype == AF_INET)
3465 sz = 2 * sizeof(struct in_addr);
3467 sz = 2 * sizeof(struct in6_addr);
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);
3481 ta_foreach_fhash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
3484 struct fhash_cfg *cfg;
3485 struct fhashentry *ent, *ent_next;
3488 cfg = (struct fhash_cfg *)ta_state;
3490 for (i = 0; i < cfg->size; i++)
3491 SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next)
3496 ta_prepare_add_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3499 struct ta_buf_fhash *tb;
3500 struct fhashentry *ent;
3504 tb = (struct ta_buf_fhash *)ta_buf;
3506 if (tei->subtype == AF_INET)
3507 sz = sizeof(struct fhashentry4);
3508 else if (tei->subtype == AF_INET6)
3509 sz = sizeof(struct fhashentry6);
3513 ent = malloc(sz, M_IPFW_TBL, M_WAITOK | M_ZERO);
3515 error = tei_to_fhash_ent(tei, ent);
3517 free(ent, M_IPFW_TBL);
3526 ta_add_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
3527 void *ta_buf, uint32_t *pnum)
3529 struct fhash_cfg *cfg;
3530 struct fhashbhead *head;
3531 struct fhashentry *ent, *tmp;
3532 struct ta_buf_fhash *tb;
3534 uint32_t hash, value;
3537 cfg = (struct fhash_cfg *)ta_state;
3538 tb = (struct ta_buf_fhash *)ta_buf;
3539 ent = (struct fhashentry *)tb->ent_ptr;
3542 /* Read current value from @tei */
3543 ent->value = tei->value;
3546 hash = hash_flow_ent(ent, cfg->size);
3548 if (tei->subtype == AF_INET)
3549 sz = 2 * sizeof(struct in_addr);
3551 sz = 2 * sizeof(struct in6_addr);
3553 /* Check for existence */
3554 SLIST_FOREACH(tmp, &head[hash], next) {
3555 if (cmp_flow_ent(tmp, ent, sz) != 0) {
3562 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
3564 /* Record already exists. Update value if we're asked to */
3565 /* Exchange values between tmp and @tei */
3567 tmp->value = tei->value;
3569 /* Indicate that update has happened instead of addition */
3570 tei->flags |= TEI_FLAGS_UPDATED;
3573 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
3576 SLIST_INSERT_HEAD(&head[hash], ent, next);
3580 /* Update counters and check if we need to grow hash */
3588 ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3591 struct ta_buf_fhash *tb;
3593 tb = (struct ta_buf_fhash *)ta_buf;
3595 return (tei_to_fhash_ent(tei, &tb->fe6.e));
3599 ta_del_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
3600 void *ta_buf, uint32_t *pnum)
3602 struct fhash_cfg *cfg;
3603 struct fhashbhead *head;
3604 struct fhashentry *ent, *tmp;
3605 struct ta_buf_fhash *tb;
3609 cfg = (struct fhash_cfg *)ta_state;
3610 tb = (struct ta_buf_fhash *)ta_buf;
3614 hash = hash_flow_ent(ent, cfg->size);
3616 if (tei->subtype == AF_INET)
3617 sz = 2 * sizeof(struct in_addr);
3619 sz = 2 * sizeof(struct in6_addr);
3621 /* Check for existence */
3622 SLIST_FOREACH(tmp, &head[hash], next) {
3623 if (cmp_flow_ent(tmp, ent, sz) == 0)
3626 SLIST_REMOVE(&head[hash], tmp, fhashentry, next);
3627 tei->value = tmp->value;
3638 ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3641 struct ta_buf_fhash *tb;
3643 tb = (struct ta_buf_fhash *)ta_buf;
3645 if (tb->ent_ptr != NULL)
3646 free(tb->ent_ptr, M_IPFW_TBL);
3650 * Hash growing callbacks.
3654 ta_need_modify_fhash(void *ta_state, struct table_info *ti, uint32_t count,
3657 struct fhash_cfg *cfg;
3659 cfg = (struct fhash_cfg *)ta_state;
3661 if (cfg->items > cfg->size && cfg->size < 65536) {
3662 *pflags = cfg->size * 2;
3670 * Allocate new, larger fhash.
3673 ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags)
3675 struct mod_item *mi;
3676 struct fhashbhead *head;
3679 mi = (struct mod_item *)ta_buf;
3681 memset(mi, 0, sizeof(struct mod_item));
3683 head = malloc(sizeof(struct fhashbhead) * mi->size, M_IPFW,
3685 for (i = 0; i < mi->size; i++)
3686 SLIST_INIT(&head[i]);
3688 mi->main_ptr = head;
3694 * Copy data from old runtime array to new one.
3697 ta_fill_mod_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3701 /* In is not possible to do rehash if we're not holidng WLOCK. */
3706 * Switch old & new arrays.
3709 ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3712 struct mod_item *mi;
3713 struct fhash_cfg *cfg;
3714 struct fhashbhead *old_head, *new_head;
3715 struct fhashentry *ent, *ent_next;
3720 mi = (struct mod_item *)ta_buf;
3721 cfg = (struct fhash_cfg *)ta_state;
3723 old_size = cfg->size;
3724 old_head = ti->state;
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);
3734 ti->state = new_head;
3735 ti->data = mi->size;
3736 cfg->head = new_head;
3737 cfg->size = mi->size;
3739 mi->main_ptr = old_head;
3743 * Free unneded array.
3746 ta_flush_mod_fhash(void *ta_buf)
3748 struct mod_item *mi;
3750 mi = (struct mod_item *)ta_buf;
3751 if (mi->main_ptr != NULL)
3752 free(mi->main_ptr, M_IPFW);
3755 struct 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,
3779 * Kernel fibs bindings.
3784 * - fully relies on route API
3785 * - fib number is stored in ti->data
3789 static int ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen,
3791 static int kfib_parse_opts(int *pfib, char *data);
3792 static void ta_print_kfib_config(void *ta_state, struct table_info *ti,
3793 char *buf, size_t bufsize);
3794 static int ta_init_kfib(struct ip_fw_chain *ch, void **ta_state,
3795 struct table_info *ti, char *data, uint8_t tflags);
3796 static void ta_destroy_kfib(void *ta_state, struct table_info *ti);
3797 static void ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti,
3798 ipfw_ta_tinfo *tinfo);
3799 static int contigmask(uint8_t *p, int len);
3800 static int ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e,
3801 ipfw_obj_tentry *tent);
3802 static int ta_dump_kfib_tentry_int(struct sockaddr *paddr,
3803 struct sockaddr *pmask, ipfw_obj_tentry *tent);
3804 static int ta_find_kfib_tentry(void *ta_state, struct table_info *ti,
3805 ipfw_obj_tentry *tent);
3806 static void ta_foreach_kfib(void *ta_state, struct table_info *ti,
3807 ta_foreach_f *f, void *arg);
3811 ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen,
3822 in.s_addr = *(in_addr_t *)key;
3824 error = fib4_lookup(ti->data, in, 0, NHR_NONE, 0) != NULL;
3829 error = fib6_lookup(ti->data, (struct in6_addr *)key,
3830 0, NHR_NONE, 0) != NULL;
3841 /* Parse 'fib=%d' */
3843 kfib_parse_opts(int *pfib, char *data)
3845 char *pdel, *pend, *s;
3850 if ((pdel = strchr(data, ' ')) == NULL)
3852 while (*pdel == ' ')
3854 if (strncmp(pdel, "fib=", 4) != 0)
3856 if ((s = strchr(pdel, ' ')) != NULL)
3861 fibnum = strtol(pdel, &pend, 10);
3871 ta_print_kfib_config(void *ta_state, struct table_info *ti, char *buf,
3876 snprintf(buf, bufsize, "%s fib=%lu", "addr:kfib", ti->data);
3878 snprintf(buf, bufsize, "%s", "addr:kfib");
3882 ta_init_kfib(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
3883 char *data, uint8_t tflags)
3888 if ((error = kfib_parse_opts(&fibnum, data)) != 0)
3891 if (fibnum >= rt_numfibs)
3895 ti->lookup = ta_lookup_kfib;
3901 * Destroys table @ti
3904 ta_destroy_kfib(void *ta_state, struct table_info *ti)
3910 * Provide algo-specific table info
3913 ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
3916 tinfo->flags = IPFW_TATFLAGS_AFDATA;
3917 tinfo->taclass4 = IPFW_TACLASS_RADIX;
3919 tinfo->itemsize4 = sizeof(struct rtentry);
3920 tinfo->taclass6 = IPFW_TACLASS_RADIX;
3922 tinfo->itemsize6 = sizeof(struct rtentry);
3926 contigmask(uint8_t *p, int len)
3930 for (i = 0; i < len ; i++)
3931 if ( (p[i/8] & (1 << (7 - (i%8)))) == 0) /* first bit unset */
3933 for (n= i + 1; n < len; n++)
3934 if ( (p[n/8] & (1 << (7 - (n % 8)))) != 0)
3935 return (-1); /* mask not contiguous */
3941 ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e,
3942 ipfw_obj_tentry *tent)
3944 struct rtentry *rte;
3946 rte = (struct rtentry *)e;
3948 return ta_dump_kfib_tentry_int(rt_key(rte), rt_mask(rte), tent);
3952 ta_dump_kfib_tentry_int(struct sockaddr *paddr, struct sockaddr *pmask,
3953 ipfw_obj_tentry *tent)
3956 struct sockaddr_in *addr, *mask;
3959 struct sockaddr_in6 *addr6, *mask6;
3965 /* Guess IPv4/IPv6 radix by sockaddr family */
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;
3973 len = contigmask((uint8_t *)&mask->sin_addr, 32);
3976 tent->masklen = len;
3977 tent->subtype = AF_INET;
3978 tent->v.kidx = 0; /* Do we need to put GW here? */
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));
3989 len = contigmask((uint8_t *)&mask6->sin6_addr, 128);
3992 tent->masklen = len;
3993 tent->subtype = AF_INET6;
4002 ta_find_kfib_tentry(void *ta_state, struct table_info *ti,
4003 ipfw_obj_tentry *tent)
4005 struct rt_addrinfo info;
4006 struct sockaddr_in6 key6, dst6, mask6;
4007 struct sockaddr *dst, *key, *mask;
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;
4017 bzero(&info, sizeof(info));
4018 info.rti_info[RTAX_DST] = dst;
4019 info.rti_info[RTAX_NETMASK] = mask;
4021 /* Prepare the lookup key */
4022 bzero(&key6, sizeof(key6));
4023 key6.sin6_family = tent->subtype;
4024 key = (struct sockaddr *)&key6;
4026 if (tent->subtype == AF_INET) {
4027 ((struct sockaddr_in *)&key6)->sin_addr = tent->k.addr;
4028 key6.sin6_len = sizeof(struct sockaddr_in);
4030 key6.sin6_addr = tent->k.addr6;
4031 key6.sin6_len = sizeof(struct sockaddr_in6);
4034 if (rib_lookup_info(ti->data, key, 0, 0, &info) != 0)
4036 if ((info.rti_addrs & RTA_NETMASK) == 0)
4039 ta_dump_kfib_tentry_int(dst, mask, tent);
4045 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);