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