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