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