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