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, may be locked (UH+WLOCK). (M_NOWAIT). 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 free(ife, M_IPFW_TBL); 2138 } 2139 2140 2141 /* 2142 * Destroys table @ti 2143 */ 2144 static void 2145 ta_destroy_ifidx(void *ta_state, struct table_info *ti) 2146 { 2147 struct iftable_cfg *icfg; 2148 struct ip_fw_chain *ch; 2149 2150 icfg = (struct iftable_cfg *)ta_state; 2151 ch = icfg->ch; 2152 2153 if (icfg->main_ptr != NULL) 2154 free(icfg->main_ptr, M_IPFW); 2155 2156 ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch); 2157 2158 ipfw_objhash_destroy(icfg->ii); 2159 2160 free(icfg, M_IPFW); 2161 } 2162 2163 /* 2164 * Provide algo-specific table info 2165 */ 2166 static void 2167 ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo) 2168 { 2169 struct iftable_cfg *cfg; 2170 2171 cfg = (struct iftable_cfg *)ta_state; 2172 2173 tinfo->taclass4 = IPFW_TACLASS_ARRAY; 2174 tinfo->size4 = cfg->size; 2175 tinfo->count4 = cfg->used; 2176 tinfo->itemsize4 = sizeof(struct ifidx); 2177 } 2178 2179 /* 2180 * Prepare state to add to the table: 2181 * allocate ifentry and reference needed interface. 2182 */ 2183 static int 2184 ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei, 2185 void *ta_buf) 2186 { 2187 struct ta_buf_ifidx *tb; 2188 char *ifname; 2189 struct ifentry *ife; 2190 2191 tb = (struct ta_buf_ifidx *)ta_buf; 2192 2193 /* Check if string is terminated */ 2194 ifname = (char *)tei->paddr; 2195 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE) 2196 return (EINVAL); 2197 2198 ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO); 2199 ife->ic.cb = if_notifier; 2200 ife->ic.cbdata = ife; 2201 2202 if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0) { 2203 free(ife, M_IPFW_TBL); 2204 return (EINVAL); 2205 } 2206 2207 /* Use ipfw_iface 'ifname' field as stable storage */ 2208 ife->no.name = ife->ic.iface->ifname; 2209 2210 tb->ife = ife; 2211 2212 return (0); 2213 } 2214 2215 static int 2216 ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei, 2217 void *ta_buf, uint32_t *pnum) 2218 { 2219 struct iftable_cfg *icfg; 2220 struct ifentry *ife, *tmp; 2221 struct ta_buf_ifidx *tb; 2222 struct ipfw_iface *iif; 2223 struct ifidx *ifi; 2224 char *ifname; 2225 uint32_t value; 2226 2227 tb = (struct ta_buf_ifidx *)ta_buf; 2228 ifname = (char *)tei->paddr; 2229 icfg = (struct iftable_cfg *)ta_state; 2230 ife = tb->ife; 2231 2232 ife->icfg = icfg; 2233 ife->value = tei->value; 2234 2235 tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname); 2236 2237 if (tmp != NULL) { 2238 if ((tei->flags & TEI_FLAGS_UPDATE) == 0) 2239 return (EEXIST); 2240 2241 /* Exchange values in @tmp and @tei */ 2242 value = tmp->value; 2243 tmp->value = tei->value; 2244 tei->value = value; 2245 2246 iif = tmp->ic.iface; 2247 if (iif->resolved != 0) { 2248 /* We have to update runtime value, too */ 2249 ifi = ifidx_find(ti, &iif->ifindex); 2250 ifi->value = ife->value; 2251 } 2252 2253 /* Indicate that update has happened instead of addition */ 2254 tei->flags |= TEI_FLAGS_UPDATED; 2255 *pnum = 0; 2256 return (0); 2257 } 2258 2259 if ((tei->flags & TEI_FLAGS_DONTADD) != 0) 2260 return (EFBIG); 2261 2262 /* Link to internal list */ 2263 ipfw_objhash_add(icfg->ii, &ife->no); 2264 2265 /* Link notifier (possible running its callback) */ 2266 ipfw_iface_add_notify(icfg->ch, &ife->ic); 2267 icfg->count++; 2268 2269 tb->ife = NULL; 2270 *pnum = 1; 2271 2272 return (0); 2273 } 2274 2275 /* 2276 * Prepare to delete key from table. 2277 * Do basic interface name checks. 2278 */ 2279 static int 2280 ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei, 2281 void *ta_buf) 2282 { 2283 struct ta_buf_ifidx *tb; 2284 char *ifname; 2285 2286 tb = (struct ta_buf_ifidx *)ta_buf; 2287 2288 /* Check if string is terminated */ 2289 ifname = (char *)tei->paddr; 2290 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE) 2291 return (EINVAL); 2292 2293 return (0); 2294 } 2295 2296 /* 2297 * Remove key from both configuration list and 2298 * runtime array. Removed interface notification. 2299 */ 2300 static int 2301 ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei, 2302 void *ta_buf, uint32_t *pnum) 2303 { 2304 struct iftable_cfg *icfg; 2305 struct ifentry *ife; 2306 struct ta_buf_ifidx *tb; 2307 char *ifname; 2308 uint16_t ifindex; 2309 int res; 2310 2311 tb = (struct ta_buf_ifidx *)ta_buf; 2312 ifname = (char *)tei->paddr; 2313 icfg = (struct iftable_cfg *)ta_state; 2314 ife = tb->ife; 2315 2316 ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname); 2317 2318 if (ife == NULL) 2319 return (ENOENT); 2320 2321 if (ife->linked != 0) { 2322 /* We have to remove item from runtime */ 2323 ifindex = ife->ic.iface->ifindex; 2324 2325 res = bdel(&ifindex, icfg->main_ptr, icfg->used, 2326 sizeof(struct ifidx), compare_ifidx); 2327 2328 KASSERT(res == 1, ("index %d does not exist", ifindex)); 2329 icfg->used--; 2330 ti->data = icfg->used; 2331 ife->linked = 0; 2332 } 2333 2334 /* Unlink from local list */ 2335 ipfw_objhash_del(icfg->ii, &ife->no); 2336 /* Unlink notifier */ 2337 ipfw_iface_del_notify(icfg->ch, &ife->ic); 2338 2339 icfg->count--; 2340 tei->value = ife->value; 2341 2342 tb->ife = ife; 2343 *pnum = 1; 2344 2345 return (0); 2346 } 2347 2348 /* 2349 * Flush deleted entry. 2350 * Drops interface reference and frees entry. 2351 */ 2352 static void 2353 ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei, 2354 void *ta_buf) 2355 { 2356 struct ta_buf_ifidx *tb; 2357 2358 tb = (struct ta_buf_ifidx *)ta_buf; 2359 2360 if (tb->ife != NULL) { 2361 /* Unlink first */ 2362 ipfw_iface_unref(ch, &tb->ife->ic); 2363 free(tb->ife, M_IPFW_TBL); 2364 } 2365 } 2366 2367 2368 /* 2369 * Handle interface announce/withdrawal for particular table. 2370 * Every real runtime array modification happens here. 2371 */ 2372 static void 2373 if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex) 2374 { 2375 struct ifentry *ife; 2376 struct ifidx ifi; 2377 struct iftable_cfg *icfg; 2378 struct table_info *ti; 2379 int res; 2380 2381 ife = (struct ifentry *)cbdata; 2382 icfg = ife->icfg; 2383 ti = icfg->ti; 2384 2385 KASSERT(ti != NULL, ("ti=NULL, check change_ti handler")); 2386 2387 if (ife->linked == 0 && ifindex != 0) { 2388 /* Interface announce */ 2389 ifi.kidx = ifindex; 2390 ifi.spare = 0; 2391 ifi.value = ife->value; 2392 res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used, 2393 sizeof(struct ifidx), compare_ifidx); 2394 KASSERT(res == 1, ("index %d already exists", ifindex)); 2395 icfg->used++; 2396 ti->data = icfg->used; 2397 ife->linked = 1; 2398 } else if (ife->linked != 0 && ifindex == 0) { 2399 /* Interface withdrawal */ 2400 ifindex = ife->ic.iface->ifindex; 2401 2402 res = bdel(&ifindex, icfg->main_ptr, icfg->used, 2403 sizeof(struct ifidx), compare_ifidx); 2404 2405 KASSERT(res == 1, ("index %d does not exist", ifindex)); 2406 icfg->used--; 2407 ti->data = icfg->used; 2408 ife->linked = 0; 2409 } 2410 } 2411 2412 2413 /* 2414 * Table growing callbacks. 2415 */ 2416 2417 static int 2418 ta_need_modify_ifidx(void *ta_state, struct table_info *ti, uint32_t count, 2419 uint64_t *pflags) 2420 { 2421 struct iftable_cfg *cfg; 2422 uint32_t size; 2423 2424 cfg = (struct iftable_cfg *)ta_state; 2425 2426 size = cfg->size; 2427 while (size < cfg->count + count) 2428 size *= 2; 2429 2430 if (size != cfg->size) { 2431 *pflags = size; 2432 return (1); 2433 } 2434 2435 return (0); 2436 } 2437 2438 /* 2439 * Allocate ned, larger runtime ifidx array. 2440 */ 2441 static int 2442 ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags) 2443 { 2444 struct mod_item *mi; 2445 2446 mi = (struct mod_item *)ta_buf; 2447 2448 memset(mi, 0, sizeof(struct mod_item)); 2449 mi->size = *pflags; 2450 mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW, 2451 M_WAITOK | M_ZERO); 2452 2453 return (0); 2454 } 2455 2456 /* 2457 * Copy data from old runtime array to new one. 2458 */ 2459 static int 2460 ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf, 2461 uint64_t *pflags) 2462 { 2463 struct mod_item *mi; 2464 struct iftable_cfg *icfg; 2465 2466 mi = (struct mod_item *)ta_buf; 2467 icfg = (struct iftable_cfg *)ta_state; 2468 2469 /* Check if we still need to grow array */ 2470 if (icfg->size >= mi->size) { 2471 *pflags = 0; 2472 return (0); 2473 } 2474 2475 memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx)); 2476 2477 return (0); 2478 } 2479 2480 /* 2481 * Switch old & new arrays. 2482 */ 2483 static void 2484 ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf, 2485 uint64_t pflags) 2486 { 2487 struct mod_item *mi; 2488 struct iftable_cfg *icfg; 2489 void *old_ptr; 2490 2491 mi = (struct mod_item *)ta_buf; 2492 icfg = (struct iftable_cfg *)ta_state; 2493 2494 old_ptr = icfg->main_ptr; 2495 icfg->main_ptr = mi->main_ptr; 2496 icfg->size = mi->size; 2497 ti->state = icfg->main_ptr; 2498 2499 mi->main_ptr = old_ptr; 2500 } 2501 2502 /* 2503 * Free unneded array. 2504 */ 2505 static void 2506 ta_flush_mod_ifidx(void *ta_buf) 2507 { 2508 struct mod_item *mi; 2509 2510 mi = (struct mod_item *)ta_buf; 2511 if (mi->main_ptr != NULL) 2512 free(mi->main_ptr, M_IPFW); 2513 } 2514 2515 static int 2516 ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e, 2517 ipfw_obj_tentry *tent) 2518 { 2519 struct ifentry *ife; 2520 2521 ife = (struct ifentry *)e; 2522 2523 tent->masklen = 8 * IF_NAMESIZE; 2524 memcpy(&tent->k, ife->no.name, IF_NAMESIZE); 2525 tent->v.kidx = ife->value; 2526 2527 return (0); 2528 } 2529 2530 static int 2531 ta_find_ifidx_tentry(void *ta_state, struct table_info *ti, 2532 ipfw_obj_tentry *tent) 2533 { 2534 struct iftable_cfg *icfg; 2535 struct ifentry *ife; 2536 char *ifname; 2537 2538 icfg = (struct iftable_cfg *)ta_state; 2539 ifname = tent->k.iface; 2540 2541 if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE) 2542 return (EINVAL); 2543 2544 ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname); 2545 2546 if (ife != NULL) { 2547 ta_dump_ifidx_tentry(ta_state, ti, ife, tent); 2548 return (0); 2549 } 2550 2551 return (ENOENT); 2552 } 2553 2554 struct wa_ifidx { 2555 ta_foreach_f *f; 2556 void *arg; 2557 }; 2558 2559 static void 2560 foreach_ifidx(struct namedobj_instance *ii, struct named_object *no, 2561 void *arg) 2562 { 2563 struct ifentry *ife; 2564 struct wa_ifidx *wa; 2565 2566 ife = (struct ifentry *)no; 2567 wa = (struct wa_ifidx *)arg; 2568 2569 wa->f(ife, wa->arg); 2570 } 2571 2572 static void 2573 ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f, 2574 void *arg) 2575 { 2576 struct iftable_cfg *icfg; 2577 struct wa_ifidx wa; 2578 2579 icfg = (struct iftable_cfg *)ta_state; 2580 2581 wa.f = f; 2582 wa.arg = arg; 2583 2584 ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa); 2585 } 2586 2587 struct table_algo iface_idx = { 2588 .name = "iface:array", 2589 .type = IPFW_TABLE_INTERFACE, 2590 .flags = TA_FLAG_DEFAULT, 2591 .ta_buf_size = sizeof(struct ta_buf_ifidx), 2592 .init = ta_init_ifidx, 2593 .destroy = ta_destroy_ifidx, 2594 .prepare_add = ta_prepare_add_ifidx, 2595 .prepare_del = ta_prepare_del_ifidx, 2596 .add = ta_add_ifidx, 2597 .del = ta_del_ifidx, 2598 .flush_entry = ta_flush_ifidx_entry, 2599 .foreach = ta_foreach_ifidx, 2600 .dump_tentry = ta_dump_ifidx_tentry, 2601 .find_tentry = ta_find_ifidx_tentry, 2602 .dump_tinfo = ta_dump_ifidx_tinfo, 2603 .need_modify = ta_need_modify_ifidx, 2604 .prepare_mod = ta_prepare_mod_ifidx, 2605 .fill_mod = ta_fill_mod_ifidx, 2606 .modify = ta_modify_ifidx, 2607 .flush_mod = ta_flush_mod_ifidx, 2608 .change_ti = ta_change_ti_ifidx, 2609 }; 2610 2611 /* 2612 * Number array cmds. 2613 * 2614 * Implementation: 2615 * 2616 * Runtime part: 2617 * - sorted array of "struct numarray" pointed by ti->state. 2618 * Array is allocated with rounding up to NUMARRAY_CHUNK. 2619 * - current array size is stored in ti->data 2620 * 2621 */ 2622 2623 struct numarray { 2624 uint32_t number; 2625 uint32_t value; 2626 }; 2627 2628 struct numarray_cfg { 2629 void *main_ptr; 2630 size_t size; /* Number of items allocated in array */ 2631 size_t used; /* Number of items _active_ now */ 2632 }; 2633 2634 struct ta_buf_numarray 2635 { 2636 struct numarray na; 2637 }; 2638 2639 int compare_numarray(const void *k, const void *v); 2640 static struct numarray *numarray_find(struct table_info *ti, void *key); 2641 static int ta_lookup_numarray(struct table_info *ti, void *key, 2642 uint32_t keylen, uint32_t *val); 2643 static int ta_init_numarray(struct ip_fw_chain *ch, void **ta_state, 2644 struct table_info *ti, char *data, uint8_t tflags); 2645 static void ta_destroy_numarray(void *ta_state, struct table_info *ti); 2646 static void ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti, 2647 ipfw_ta_tinfo *tinfo); 2648 static int ta_prepare_add_numarray(struct ip_fw_chain *ch, 2649 struct tentry_info *tei, void *ta_buf); 2650 static int ta_add_numarray(void *ta_state, struct table_info *ti, 2651 struct tentry_info *tei, void *ta_buf, uint32_t *pnum); 2652 static int ta_del_numarray(void *ta_state, struct table_info *ti, 2653 struct tentry_info *tei, void *ta_buf, uint32_t *pnum); 2654 static void ta_flush_numarray_entry(struct ip_fw_chain *ch, 2655 struct tentry_info *tei, void *ta_buf); 2656 static int ta_need_modify_numarray(void *ta_state, struct table_info *ti, 2657 uint32_t count, uint64_t *pflags); 2658 static int ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags); 2659 static int ta_fill_mod_numarray(void *ta_state, struct table_info *ti, 2660 void *ta_buf, uint64_t *pflags); 2661 static void ta_modify_numarray(void *ta_state, struct table_info *ti, 2662 void *ta_buf, uint64_t pflags); 2663 static void ta_flush_mod_numarray(void *ta_buf); 2664 static int ta_dump_numarray_tentry(void *ta_state, struct table_info *ti, 2665 void *e, ipfw_obj_tentry *tent); 2666 static int ta_find_numarray_tentry(void *ta_state, struct table_info *ti, 2667 ipfw_obj_tentry *tent); 2668 static void ta_foreach_numarray(void *ta_state, struct table_info *ti, 2669 ta_foreach_f *f, void *arg); 2670 2671 int 2672 compare_numarray(const void *k, const void *v) 2673 { 2674 const struct numarray *na; 2675 uint32_t key; 2676 2677 key = *((const uint32_t *)k); 2678 na = (const struct numarray *)v; 2679 2680 if (key < na->number) 2681 return (-1); 2682 else if (key > na->number) 2683 return (1); 2684 2685 return (0); 2686 } 2687 2688 static struct numarray * 2689 numarray_find(struct table_info *ti, void *key) 2690 { 2691 struct numarray *ri; 2692 2693 ri = bsearch(key, ti->state, ti->data, sizeof(struct numarray), 2694 compare_ifidx); 2695 2696 return (ri); 2697 } 2698 2699 static int 2700 ta_lookup_numarray(struct table_info *ti, void *key, uint32_t keylen, 2701 uint32_t *val) 2702 { 2703 struct numarray *ri; 2704 2705 ri = numarray_find(ti, key); 2706 2707 if (ri != NULL) { 2708 *val = ri->value; 2709 return (1); 2710 } 2711 2712 return (0); 2713 } 2714 2715 static int 2716 ta_init_numarray(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti, 2717 char *data, uint8_t tflags) 2718 { 2719 struct numarray_cfg *cfg; 2720 2721 cfg = malloc(sizeof(*cfg), M_IPFW, M_WAITOK | M_ZERO); 2722 2723 cfg->size = 16; 2724 cfg->main_ptr = malloc(sizeof(struct numarray) * cfg->size, M_IPFW, 2725 M_WAITOK | M_ZERO); 2726 2727 *ta_state = cfg; 2728 ti->state = cfg->main_ptr; 2729 ti->lookup = ta_lookup_numarray; 2730 2731 return (0); 2732 } 2733 2734 /* 2735 * Destroys table @ti 2736 */ 2737 static void 2738 ta_destroy_numarray(void *ta_state, struct table_info *ti) 2739 { 2740 struct numarray_cfg *cfg; 2741 2742 cfg = (struct numarray_cfg *)ta_state; 2743 2744 if (cfg->main_ptr != NULL) 2745 free(cfg->main_ptr, M_IPFW); 2746 2747 free(cfg, M_IPFW); 2748 } 2749 2750 /* 2751 * Provide algo-specific table info 2752 */ 2753 static void 2754 ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo) 2755 { 2756 struct numarray_cfg *cfg; 2757 2758 cfg = (struct numarray_cfg *)ta_state; 2759 2760 tinfo->taclass4 = IPFW_TACLASS_ARRAY; 2761 tinfo->size4 = cfg->size; 2762 tinfo->count4 = cfg->used; 2763 tinfo->itemsize4 = sizeof(struct numarray); 2764 } 2765 2766 /* 2767 * Prepare for addition/deletion to an array. 2768 */ 2769 static int 2770 ta_prepare_add_numarray(struct ip_fw_chain *ch, struct tentry_info *tei, 2771 void *ta_buf) 2772 { 2773 struct ta_buf_numarray *tb; 2774 2775 tb = (struct ta_buf_numarray *)ta_buf; 2776 2777 tb->na.number = *((uint32_t *)tei->paddr); 2778 2779 return (0); 2780 } 2781 2782 static int 2783 ta_add_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei, 2784 void *ta_buf, uint32_t *pnum) 2785 { 2786 struct numarray_cfg *cfg; 2787 struct ta_buf_numarray *tb; 2788 struct numarray *ri; 2789 int res; 2790 uint32_t value; 2791 2792 tb = (struct ta_buf_numarray *)ta_buf; 2793 cfg = (struct numarray_cfg *)ta_state; 2794 2795 /* Read current value from @tei */ 2796 tb->na.value = tei->value; 2797 2798 ri = numarray_find(ti, &tb->na.number); 2799 2800 if (ri != NULL) { 2801 if ((tei->flags & TEI_FLAGS_UPDATE) == 0) 2802 return (EEXIST); 2803 2804 /* Exchange values between ri and @tei */ 2805 value = ri->value; 2806 ri->value = tei->value; 2807 tei->value = value; 2808 /* Indicate that update has happened instead of addition */ 2809 tei->flags |= TEI_FLAGS_UPDATED; 2810 *pnum = 0; 2811 return (0); 2812 } 2813 2814 if ((tei->flags & TEI_FLAGS_DONTADD) != 0) 2815 return (EFBIG); 2816 2817 res = badd(&tb->na.number, &tb->na, cfg->main_ptr, cfg->used, 2818 sizeof(struct numarray), compare_numarray); 2819 2820 KASSERT(res == 1, ("number %d already exists", tb->na.number)); 2821 cfg->used++; 2822 ti->data = cfg->used; 2823 *pnum = 1; 2824 2825 return (0); 2826 } 2827 2828 /* 2829 * Remove key from both configuration list and 2830 * runtime array. Removed interface notification. 2831 */ 2832 static int 2833 ta_del_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei, 2834 void *ta_buf, uint32_t *pnum) 2835 { 2836 struct numarray_cfg *cfg; 2837 struct ta_buf_numarray *tb; 2838 struct numarray *ri; 2839 int res; 2840 2841 tb = (struct ta_buf_numarray *)ta_buf; 2842 cfg = (struct numarray_cfg *)ta_state; 2843 2844 ri = numarray_find(ti, &tb->na.number); 2845 if (ri == NULL) 2846 return (ENOENT); 2847 2848 tei->value = ri->value; 2849 2850 res = bdel(&tb->na.number, cfg->main_ptr, cfg->used, 2851 sizeof(struct numarray), compare_numarray); 2852 2853 KASSERT(res == 1, ("number %u does not exist", tb->na.number)); 2854 cfg->used--; 2855 ti->data = cfg->used; 2856 *pnum = 1; 2857 2858 return (0); 2859 } 2860 2861 static void 2862 ta_flush_numarray_entry(struct ip_fw_chain *ch, struct tentry_info *tei, 2863 void *ta_buf) 2864 { 2865 2866 /* We don't have any state, do nothing */ 2867 } 2868 2869 2870 /* 2871 * Table growing callbacks. 2872 */ 2873 2874 static int 2875 ta_need_modify_numarray(void *ta_state, struct table_info *ti, uint32_t count, 2876 uint64_t *pflags) 2877 { 2878 struct numarray_cfg *cfg; 2879 size_t size; 2880 2881 cfg = (struct numarray_cfg *)ta_state; 2882 2883 size = cfg->size; 2884 while (size < cfg->used + count) 2885 size *= 2; 2886 2887 if (size != cfg->size) { 2888 *pflags = size; 2889 return (1); 2890 } 2891 2892 return (0); 2893 } 2894 2895 /* 2896 * Allocate new, larger runtime array. 2897 */ 2898 static int 2899 ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags) 2900 { 2901 struct mod_item *mi; 2902 2903 mi = (struct mod_item *)ta_buf; 2904 2905 memset(mi, 0, sizeof(struct mod_item)); 2906 mi->size = *pflags; 2907 mi->main_ptr = malloc(sizeof(struct numarray) * mi->size, M_IPFW, 2908 M_WAITOK | M_ZERO); 2909 2910 return (0); 2911 } 2912 2913 /* 2914 * Copy data from old runtime array to new one. 2915 */ 2916 static int 2917 ta_fill_mod_numarray(void *ta_state, struct table_info *ti, void *ta_buf, 2918 uint64_t *pflags) 2919 { 2920 struct mod_item *mi; 2921 struct numarray_cfg *cfg; 2922 2923 mi = (struct mod_item *)ta_buf; 2924 cfg = (struct numarray_cfg *)ta_state; 2925 2926 /* Check if we still need to grow array */ 2927 if (cfg->size >= mi->size) { 2928 *pflags = 0; 2929 return (0); 2930 } 2931 2932 memcpy(mi->main_ptr, cfg->main_ptr, cfg->used * sizeof(struct numarray)); 2933 2934 return (0); 2935 } 2936 2937 /* 2938 * Switch old & new arrays. 2939 */ 2940 static void 2941 ta_modify_numarray(void *ta_state, struct table_info *ti, void *ta_buf, 2942 uint64_t pflags) 2943 { 2944 struct mod_item *mi; 2945 struct numarray_cfg *cfg; 2946 void *old_ptr; 2947 2948 mi = (struct mod_item *)ta_buf; 2949 cfg = (struct numarray_cfg *)ta_state; 2950 2951 old_ptr = cfg->main_ptr; 2952 cfg->main_ptr = mi->main_ptr; 2953 cfg->size = mi->size; 2954 ti->state = cfg->main_ptr; 2955 2956 mi->main_ptr = old_ptr; 2957 } 2958 2959 /* 2960 * Free unneded array. 2961 */ 2962 static void 2963 ta_flush_mod_numarray(void *ta_buf) 2964 { 2965 struct mod_item *mi; 2966 2967 mi = (struct mod_item *)ta_buf; 2968 if (mi->main_ptr != NULL) 2969 free(mi->main_ptr, M_IPFW); 2970 } 2971 2972 static int 2973 ta_dump_numarray_tentry(void *ta_state, struct table_info *ti, void *e, 2974 ipfw_obj_tentry *tent) 2975 { 2976 struct numarray *na; 2977 2978 na = (struct numarray *)e; 2979 2980 tent->k.key = na->number; 2981 tent->v.kidx = na->value; 2982 2983 return (0); 2984 } 2985 2986 static int 2987 ta_find_numarray_tentry(void *ta_state, struct table_info *ti, 2988 ipfw_obj_tentry *tent) 2989 { 2990 struct numarray_cfg *cfg; 2991 struct numarray *ri; 2992 2993 cfg = (struct numarray_cfg *)ta_state; 2994 2995 ri = numarray_find(ti, &tent->k.key); 2996 2997 if (ri != NULL) { 2998 ta_dump_numarray_tentry(ta_state, ti, ri, tent); 2999 return (0); 3000 } 3001 3002 return (ENOENT); 3003 } 3004 3005 static void 3006 ta_foreach_numarray(void *ta_state, struct table_info *ti, ta_foreach_f *f, 3007 void *arg) 3008 { 3009 struct numarray_cfg *cfg; 3010 struct numarray *array; 3011 int i; 3012 3013 cfg = (struct numarray_cfg *)ta_state; 3014 array = cfg->main_ptr; 3015 3016 for (i = 0; i < cfg->used; i++) 3017 f(&array[i], arg); 3018 } 3019 3020 struct table_algo number_array = { 3021 .name = "number:array", 3022 .type = IPFW_TABLE_NUMBER, 3023 .ta_buf_size = sizeof(struct ta_buf_numarray), 3024 .init = ta_init_numarray, 3025 .destroy = ta_destroy_numarray, 3026 .prepare_add = ta_prepare_add_numarray, 3027 .prepare_del = ta_prepare_add_numarray, 3028 .add = ta_add_numarray, 3029 .del = ta_del_numarray, 3030 .flush_entry = ta_flush_numarray_entry, 3031 .foreach = ta_foreach_numarray, 3032 .dump_tentry = ta_dump_numarray_tentry, 3033 .find_tentry = ta_find_numarray_tentry, 3034 .dump_tinfo = ta_dump_numarray_tinfo, 3035 .need_modify = ta_need_modify_numarray, 3036 .prepare_mod = ta_prepare_mod_numarray, 3037 .fill_mod = ta_fill_mod_numarray, 3038 .modify = ta_modify_numarray, 3039 .flush_mod = ta_flush_mod_numarray, 3040 }; 3041 3042 /* 3043 * flow:hash cmds 3044 * 3045 * 3046 * ti->data: 3047 * [inv.mask4][inv.mask6][log2hsize4][log2hsize6] 3048 * [ 8][ 8[ 8][ 8] 3049 * 3050 * inv.mask4: 32 - mask 3051 * inv.mask6: 3052 * 1) _slow lookup: mask 3053 * 2) _aligned: (128 - mask) / 8 3054 * 3) _64: 8 3055 * 3056 * 3057 * pflags: 3058 * [hsize4][hsize6] 3059 * [ 16][ 16] 3060 */ 3061 3062 struct fhashentry; 3063 3064 SLIST_HEAD(fhashbhead, fhashentry); 3065 3066 struct fhashentry { 3067 SLIST_ENTRY(fhashentry) next; 3068 uint8_t af; 3069 uint8_t proto; 3070 uint16_t spare0; 3071 uint16_t dport; 3072 uint16_t sport; 3073 uint32_t value; 3074 uint32_t spare1; 3075 }; 3076 3077 struct fhashentry4 { 3078 struct fhashentry e; 3079 struct in_addr dip; 3080 struct in_addr sip; 3081 }; 3082 3083 struct fhashentry6 { 3084 struct fhashentry e; 3085 struct in6_addr dip6; 3086 struct in6_addr sip6; 3087 }; 3088 3089 struct fhash_cfg { 3090 struct fhashbhead *head; 3091 size_t size; 3092 size_t items; 3093 struct fhashentry4 fe4; 3094 struct fhashentry6 fe6; 3095 }; 3096 3097 struct ta_buf_fhash { 3098 void *ent_ptr; 3099 struct fhashentry6 fe6; 3100 }; 3101 3102 static __inline int cmp_flow_ent(struct fhashentry *a, 3103 struct fhashentry *b, size_t sz); 3104 static __inline uint32_t hash_flow4(struct fhashentry4 *f, int hsize); 3105 static __inline uint32_t hash_flow6(struct fhashentry6 *f, int hsize); 3106 static uint32_t hash_flow_ent(struct fhashentry *ent, uint32_t size); 3107 static int ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen, 3108 uint32_t *val); 3109 static int ta_init_fhash(struct ip_fw_chain *ch, void **ta_state, 3110 struct table_info *ti, char *data, uint8_t tflags); 3111 static void ta_destroy_fhash(void *ta_state, struct table_info *ti); 3112 static void ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti, 3113 ipfw_ta_tinfo *tinfo); 3114 static int ta_dump_fhash_tentry(void *ta_state, struct table_info *ti, 3115 void *e, ipfw_obj_tentry *tent); 3116 static int tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent); 3117 static int ta_find_fhash_tentry(void *ta_state, struct table_info *ti, 3118 ipfw_obj_tentry *tent); 3119 static void ta_foreach_fhash(void *ta_state, struct table_info *ti, 3120 ta_foreach_f *f, void *arg); 3121 static int ta_prepare_add_fhash(struct ip_fw_chain *ch, 3122 struct tentry_info *tei, void *ta_buf); 3123 static int ta_add_fhash(void *ta_state, struct table_info *ti, 3124 struct tentry_info *tei, void *ta_buf, uint32_t *pnum); 3125 static int ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei, 3126 void *ta_buf); 3127 static int ta_del_fhash(void *ta_state, struct table_info *ti, 3128 struct tentry_info *tei, void *ta_buf, uint32_t *pnum); 3129 static void ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei, 3130 void *ta_buf); 3131 static int ta_need_modify_fhash(void *ta_state, struct table_info *ti, 3132 uint32_t count, uint64_t *pflags); 3133 static int ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags); 3134 static int ta_fill_mod_fhash(void *ta_state, struct table_info *ti, 3135 void *ta_buf, uint64_t *pflags); 3136 static void ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf, 3137 uint64_t pflags); 3138 static void ta_flush_mod_fhash(void *ta_buf); 3139 3140 static __inline int 3141 cmp_flow_ent(struct fhashentry *a, struct fhashentry *b, size_t sz) 3142 { 3143 uint64_t *ka, *kb; 3144 3145 ka = (uint64_t *)(&a->next + 1); 3146 kb = (uint64_t *)(&b->next + 1); 3147 3148 if (*ka == *kb && (memcmp(a + 1, b + 1, sz) == 0)) 3149 return (1); 3150 3151 return (0); 3152 } 3153 3154 static __inline uint32_t 3155 hash_flow4(struct fhashentry4 *f, int hsize) 3156 { 3157 uint32_t i; 3158 3159 i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport); 3160 3161 return (i % (hsize - 1)); 3162 } 3163 3164 static __inline uint32_t 3165 hash_flow6(struct fhashentry6 *f, int hsize) 3166 { 3167 uint32_t i; 3168 3169 i = (f->dip6.__u6_addr.__u6_addr32[2]) ^ 3170 (f->dip6.__u6_addr.__u6_addr32[3]) ^ 3171 (f->sip6.__u6_addr.__u6_addr32[2]) ^ 3172 (f->sip6.__u6_addr.__u6_addr32[3]) ^ 3173 (f->e.dport) ^ (f->e.sport); 3174 3175 return (i % (hsize - 1)); 3176 } 3177 3178 static uint32_t 3179 hash_flow_ent(struct fhashentry *ent, uint32_t size) 3180 { 3181 uint32_t hash; 3182 3183 if (ent->af == AF_INET) { 3184 hash = hash_flow4((struct fhashentry4 *)ent, size); 3185 } else { 3186 hash = hash_flow6((struct fhashentry6 *)ent, size); 3187 } 3188 3189 return (hash); 3190 } 3191 3192 static int 3193 ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen, 3194 uint32_t *val) 3195 { 3196 struct fhashbhead *head; 3197 struct fhashentry *ent; 3198 struct fhashentry4 *m4; 3199 struct ipfw_flow_id *id; 3200 uint16_t hash, hsize; 3201 3202 id = (struct ipfw_flow_id *)key; 3203 head = (struct fhashbhead *)ti->state; 3204 hsize = ti->data; 3205 m4 = (struct fhashentry4 *)ti->xstate; 3206 3207 if (id->addr_type == 4) { 3208 struct fhashentry4 f; 3209 3210 /* Copy hash mask */ 3211 f = *m4; 3212 3213 f.dip.s_addr &= id->dst_ip; 3214 f.sip.s_addr &= id->src_ip; 3215 f.e.dport &= id->dst_port; 3216 f.e.sport &= id->src_port; 3217 f.e.proto &= id->proto; 3218 hash = hash_flow4(&f, hsize); 3219 SLIST_FOREACH(ent, &head[hash], next) { 3220 if (cmp_flow_ent(ent, &f.e, 2 * 4) != 0) { 3221 *val = ent->value; 3222 return (1); 3223 } 3224 } 3225 } else if (id->addr_type == 6) { 3226 struct fhashentry6 f; 3227 uint64_t *fp, *idp; 3228 3229 /* Copy hash mask */ 3230 f = *((struct fhashentry6 *)(m4 + 1)); 3231 3232 /* Handle lack of __u6_addr.__u6_addr64 */ 3233 fp = (uint64_t *)&f.dip6; 3234 idp = (uint64_t *)&id->dst_ip6; 3235 /* src IPv6 is stored after dst IPv6 */ 3236 *fp++ &= *idp++; 3237 *fp++ &= *idp++; 3238 *fp++ &= *idp++; 3239 *fp &= *idp; 3240 f.e.dport &= id->dst_port; 3241 f.e.sport &= id->src_port; 3242 f.e.proto &= id->proto; 3243 hash = hash_flow6(&f, hsize); 3244 SLIST_FOREACH(ent, &head[hash], next) { 3245 if (cmp_flow_ent(ent, &f.e, 2 * 16) != 0) { 3246 *val = ent->value; 3247 return (1); 3248 } 3249 } 3250 } 3251 3252 return (0); 3253 } 3254 3255 /* 3256 * New table. 3257 */ 3258 static int 3259 ta_init_fhash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti, 3260 char *data, uint8_t tflags) 3261 { 3262 int i; 3263 struct fhash_cfg *cfg; 3264 struct fhashentry4 *fe4; 3265 struct fhashentry6 *fe6; 3266 3267 cfg = malloc(sizeof(struct fhash_cfg), M_IPFW, M_WAITOK | M_ZERO); 3268 3269 cfg->size = 512; 3270 3271 cfg->head = malloc(sizeof(struct fhashbhead) * cfg->size, M_IPFW, 3272 M_WAITOK | M_ZERO); 3273 for (i = 0; i < cfg->size; i++) 3274 SLIST_INIT(&cfg->head[i]); 3275 3276 /* Fill in fe masks based on @tflags */ 3277 fe4 = &cfg->fe4; 3278 fe6 = &cfg->fe6; 3279 if (tflags & IPFW_TFFLAG_SRCIP) { 3280 memset(&fe4->sip, 0xFF, sizeof(fe4->sip)); 3281 memset(&fe6->sip6, 0xFF, sizeof(fe6->sip6)); 3282 } 3283 if (tflags & IPFW_TFFLAG_DSTIP) { 3284 memset(&fe4->dip, 0xFF, sizeof(fe4->dip)); 3285 memset(&fe6->dip6, 0xFF, sizeof(fe6->dip6)); 3286 } 3287 if (tflags & IPFW_TFFLAG_SRCPORT) { 3288 memset(&fe4->e.sport, 0xFF, sizeof(fe4->e.sport)); 3289 memset(&fe6->e.sport, 0xFF, sizeof(fe6->e.sport)); 3290 } 3291 if (tflags & IPFW_TFFLAG_DSTPORT) { 3292 memset(&fe4->e.dport, 0xFF, sizeof(fe4->e.dport)); 3293 memset(&fe6->e.dport, 0xFF, sizeof(fe6->e.dport)); 3294 } 3295 if (tflags & IPFW_TFFLAG_PROTO) { 3296 memset(&fe4->e.proto, 0xFF, sizeof(fe4->e.proto)); 3297 memset(&fe6->e.proto, 0xFF, sizeof(fe6->e.proto)); 3298 } 3299 3300 fe4->e.af = AF_INET; 3301 fe6->e.af = AF_INET6; 3302 3303 *ta_state = cfg; 3304 ti->state = cfg->head; 3305 ti->xstate = &cfg->fe4; 3306 ti->data = cfg->size; 3307 ti->lookup = ta_lookup_fhash; 3308 3309 return (0); 3310 } 3311 3312 static void 3313 ta_destroy_fhash(void *ta_state, struct table_info *ti) 3314 { 3315 struct fhash_cfg *cfg; 3316 struct fhashentry *ent, *ent_next; 3317 int i; 3318 3319 cfg = (struct fhash_cfg *)ta_state; 3320 3321 for (i = 0; i < cfg->size; i++) 3322 SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next) 3323 free(ent, M_IPFW_TBL); 3324 3325 free(cfg->head, M_IPFW); 3326 free(cfg, M_IPFW); 3327 } 3328 3329 /* 3330 * Provide algo-specific table info 3331 */ 3332 static void 3333 ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo) 3334 { 3335 struct fhash_cfg *cfg; 3336 3337 cfg = (struct fhash_cfg *)ta_state; 3338 3339 tinfo->flags = IPFW_TATFLAGS_AFITEM; 3340 tinfo->taclass4 = IPFW_TACLASS_HASH; 3341 tinfo->size4 = cfg->size; 3342 tinfo->count4 = cfg->items; 3343 tinfo->itemsize4 = sizeof(struct fhashentry4); 3344 tinfo->itemsize6 = sizeof(struct fhashentry6); 3345 } 3346 3347 static int 3348 ta_dump_fhash_tentry(void *ta_state, struct table_info *ti, void *e, 3349 ipfw_obj_tentry *tent) 3350 { 3351 struct fhash_cfg *cfg; 3352 struct fhashentry *ent; 3353 struct fhashentry4 *fe4; 3354 #ifdef INET6 3355 struct fhashentry6 *fe6; 3356 #endif 3357 struct tflow_entry *tfe; 3358 3359 cfg = (struct fhash_cfg *)ta_state; 3360 ent = (struct fhashentry *)e; 3361 tfe = &tent->k.flow; 3362 3363 tfe->af = ent->af; 3364 tfe->proto = ent->proto; 3365 tfe->dport = htons(ent->dport); 3366 tfe->sport = htons(ent->sport); 3367 tent->v.kidx = ent->value; 3368 tent->subtype = ent->af; 3369 3370 if (ent->af == AF_INET) { 3371 fe4 = (struct fhashentry4 *)ent; 3372 tfe->a.a4.sip.s_addr = htonl(fe4->sip.s_addr); 3373 tfe->a.a4.dip.s_addr = htonl(fe4->dip.s_addr); 3374 tent->masklen = 32; 3375 #ifdef INET6 3376 } else { 3377 fe6 = (struct fhashentry6 *)ent; 3378 tfe->a.a6.sip6 = fe6->sip6; 3379 tfe->a.a6.dip6 = fe6->dip6; 3380 tent->masklen = 128; 3381 #endif 3382 } 3383 3384 return (0); 3385 } 3386 3387 static int 3388 tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent) 3389 { 3390 #ifdef INET 3391 struct fhashentry4 *fe4; 3392 #endif 3393 #ifdef INET6 3394 struct fhashentry6 *fe6; 3395 #endif 3396 struct tflow_entry *tfe; 3397 3398 tfe = (struct tflow_entry *)tei->paddr; 3399 3400 ent->af = tei->subtype; 3401 ent->proto = tfe->proto; 3402 ent->dport = ntohs(tfe->dport); 3403 ent->sport = ntohs(tfe->sport); 3404 3405 if (tei->subtype == AF_INET) { 3406 #ifdef INET 3407 fe4 = (struct fhashentry4 *)ent; 3408 fe4->sip.s_addr = ntohl(tfe->a.a4.sip.s_addr); 3409 fe4->dip.s_addr = ntohl(tfe->a.a4.dip.s_addr); 3410 #endif 3411 #ifdef INET6 3412 } else if (tei->subtype == AF_INET6) { 3413 fe6 = (struct fhashentry6 *)ent; 3414 fe6->sip6 = tfe->a.a6.sip6; 3415 fe6->dip6 = tfe->a.a6.dip6; 3416 #endif 3417 } else { 3418 /* Unknown CIDR type */ 3419 return (EINVAL); 3420 } 3421 3422 return (0); 3423 } 3424 3425 3426 static int 3427 ta_find_fhash_tentry(void *ta_state, struct table_info *ti, 3428 ipfw_obj_tentry *tent) 3429 { 3430 struct fhash_cfg *cfg; 3431 struct fhashbhead *head; 3432 struct fhashentry *ent, *tmp; 3433 struct fhashentry6 fe6; 3434 struct tentry_info tei; 3435 int error; 3436 uint32_t hash; 3437 size_t sz; 3438 3439 cfg = (struct fhash_cfg *)ta_state; 3440 3441 ent = &fe6.e; 3442 3443 memset(&fe6, 0, sizeof(fe6)); 3444 memset(&tei, 0, sizeof(tei)); 3445 3446 tei.paddr = &tent->k.flow; 3447 tei.subtype = tent->subtype; 3448 3449 if ((error = tei_to_fhash_ent(&tei, ent)) != 0) 3450 return (error); 3451 3452 head = cfg->head; 3453 hash = hash_flow_ent(ent, cfg->size); 3454 3455 if (tei.subtype == AF_INET) 3456 sz = 2 * sizeof(struct in_addr); 3457 else 3458 sz = 2 * sizeof(struct in6_addr); 3459 3460 /* Check for existence */ 3461 SLIST_FOREACH(tmp, &head[hash], next) { 3462 if (cmp_flow_ent(tmp, ent, sz) != 0) { 3463 ta_dump_fhash_tentry(ta_state, ti, tmp, tent); 3464 return (0); 3465 } 3466 } 3467 3468 return (ENOENT); 3469 } 3470 3471 static void 3472 ta_foreach_fhash(void *ta_state, struct table_info *ti, ta_foreach_f *f, 3473 void *arg) 3474 { 3475 struct fhash_cfg *cfg; 3476 struct fhashentry *ent, *ent_next; 3477 int i; 3478 3479 cfg = (struct fhash_cfg *)ta_state; 3480 3481 for (i = 0; i < cfg->size; i++) 3482 SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next) 3483 f(ent, arg); 3484 } 3485 3486 static int 3487 ta_prepare_add_fhash(struct ip_fw_chain *ch, struct tentry_info *tei, 3488 void *ta_buf) 3489 { 3490 struct ta_buf_fhash *tb; 3491 struct fhashentry *ent; 3492 size_t sz; 3493 int error; 3494 3495 tb = (struct ta_buf_fhash *)ta_buf; 3496 3497 if (tei->subtype == AF_INET) 3498 sz = sizeof(struct fhashentry4); 3499 else if (tei->subtype == AF_INET6) 3500 sz = sizeof(struct fhashentry6); 3501 else 3502 return (EINVAL); 3503 3504 ent = malloc(sz, M_IPFW_TBL, M_WAITOK | M_ZERO); 3505 3506 error = tei_to_fhash_ent(tei, ent); 3507 if (error != 0) { 3508 free(ent, M_IPFW_TBL); 3509 return (error); 3510 } 3511 tb->ent_ptr = ent; 3512 3513 return (0); 3514 } 3515 3516 static int 3517 ta_add_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei, 3518 void *ta_buf, uint32_t *pnum) 3519 { 3520 struct fhash_cfg *cfg; 3521 struct fhashbhead *head; 3522 struct fhashentry *ent, *tmp; 3523 struct ta_buf_fhash *tb; 3524 int exists; 3525 uint32_t hash, value; 3526 size_t sz; 3527 3528 cfg = (struct fhash_cfg *)ta_state; 3529 tb = (struct ta_buf_fhash *)ta_buf; 3530 ent = (struct fhashentry *)tb->ent_ptr; 3531 exists = 0; 3532 3533 /* Read current value from @tei */ 3534 ent->value = tei->value; 3535 3536 head = cfg->head; 3537 hash = hash_flow_ent(ent, cfg->size); 3538 3539 if (tei->subtype == AF_INET) 3540 sz = 2 * sizeof(struct in_addr); 3541 else 3542 sz = 2 * sizeof(struct in6_addr); 3543 3544 /* Check for existence */ 3545 SLIST_FOREACH(tmp, &head[hash], next) { 3546 if (cmp_flow_ent(tmp, ent, sz) != 0) { 3547 exists = 1; 3548 break; 3549 } 3550 } 3551 3552 if (exists == 1) { 3553 if ((tei->flags & TEI_FLAGS_UPDATE) == 0) 3554 return (EEXIST); 3555 /* Record already exists. Update value if we're asked to */ 3556 /* Exchange values between tmp and @tei */ 3557 value = tmp->value; 3558 tmp->value = tei->value; 3559 tei->value = value; 3560 /* Indicate that update has happened instead of addition */ 3561 tei->flags |= TEI_FLAGS_UPDATED; 3562 *pnum = 0; 3563 } else { 3564 if ((tei->flags & TEI_FLAGS_DONTADD) != 0) 3565 return (EFBIG); 3566 3567 SLIST_INSERT_HEAD(&head[hash], ent, next); 3568 tb->ent_ptr = NULL; 3569 *pnum = 1; 3570 3571 /* Update counters and check if we need to grow hash */ 3572 cfg->items++; 3573 } 3574 3575 return (0); 3576 } 3577 3578 static int 3579 ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei, 3580 void *ta_buf) 3581 { 3582 struct ta_buf_fhash *tb; 3583 3584 tb = (struct ta_buf_fhash *)ta_buf; 3585 3586 return (tei_to_fhash_ent(tei, &tb->fe6.e)); 3587 } 3588 3589 static int 3590 ta_del_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei, 3591 void *ta_buf, uint32_t *pnum) 3592 { 3593 struct fhash_cfg *cfg; 3594 struct fhashbhead *head; 3595 struct fhashentry *ent, *tmp; 3596 struct ta_buf_fhash *tb; 3597 uint32_t hash; 3598 size_t sz; 3599 3600 cfg = (struct fhash_cfg *)ta_state; 3601 tb = (struct ta_buf_fhash *)ta_buf; 3602 ent = &tb->fe6.e; 3603 3604 head = cfg->head; 3605 hash = hash_flow_ent(ent, cfg->size); 3606 3607 if (tei->subtype == AF_INET) 3608 sz = 2 * sizeof(struct in_addr); 3609 else 3610 sz = 2 * sizeof(struct in6_addr); 3611 3612 /* Check for existence */ 3613 SLIST_FOREACH(tmp, &head[hash], next) { 3614 if (cmp_flow_ent(tmp, ent, sz) == 0) 3615 continue; 3616 3617 SLIST_REMOVE(&head[hash], tmp, fhashentry, next); 3618 tei->value = tmp->value; 3619 *pnum = 1; 3620 cfg->items--; 3621 tb->ent_ptr = tmp; 3622 return (0); 3623 } 3624 3625 return (ENOENT); 3626 } 3627 3628 static void 3629 ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei, 3630 void *ta_buf) 3631 { 3632 struct ta_buf_fhash *tb; 3633 3634 tb = (struct ta_buf_fhash *)ta_buf; 3635 3636 if (tb->ent_ptr != NULL) 3637 free(tb->ent_ptr, M_IPFW_TBL); 3638 } 3639 3640 /* 3641 * Hash growing callbacks. 3642 */ 3643 3644 static int 3645 ta_need_modify_fhash(void *ta_state, struct table_info *ti, uint32_t count, 3646 uint64_t *pflags) 3647 { 3648 struct fhash_cfg *cfg; 3649 3650 cfg = (struct fhash_cfg *)ta_state; 3651 3652 if (cfg->items > cfg->size && cfg->size < 65536) { 3653 *pflags = cfg->size * 2; 3654 return (1); 3655 } 3656 3657 return (0); 3658 } 3659 3660 /* 3661 * Allocate new, larger fhash. 3662 */ 3663 static int 3664 ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags) 3665 { 3666 struct mod_item *mi; 3667 struct fhashbhead *head; 3668 int i; 3669 3670 mi = (struct mod_item *)ta_buf; 3671 3672 memset(mi, 0, sizeof(struct mod_item)); 3673 mi->size = *pflags; 3674 head = malloc(sizeof(struct fhashbhead) * mi->size, M_IPFW, 3675 M_WAITOK | M_ZERO); 3676 for (i = 0; i < mi->size; i++) 3677 SLIST_INIT(&head[i]); 3678 3679 mi->main_ptr = head; 3680 3681 return (0); 3682 } 3683 3684 /* 3685 * Copy data from old runtime array to new one. 3686 */ 3687 static int 3688 ta_fill_mod_fhash(void *ta_state, struct table_info *ti, void *ta_buf, 3689 uint64_t *pflags) 3690 { 3691 3692 /* In is not possible to do rehash if we're not holidng WLOCK. */ 3693 return (0); 3694 } 3695 3696 /* 3697 * Switch old & new arrays. 3698 */ 3699 static void 3700 ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf, 3701 uint64_t pflags) 3702 { 3703 struct mod_item *mi; 3704 struct fhash_cfg *cfg; 3705 struct fhashbhead *old_head, *new_head; 3706 struct fhashentry *ent, *ent_next; 3707 int i; 3708 uint32_t nhash; 3709 size_t old_size; 3710 3711 mi = (struct mod_item *)ta_buf; 3712 cfg = (struct fhash_cfg *)ta_state; 3713 3714 old_size = cfg->size; 3715 old_head = ti->state; 3716 3717 new_head = (struct fhashbhead *)mi->main_ptr; 3718 for (i = 0; i < old_size; i++) { 3719 SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) { 3720 nhash = hash_flow_ent(ent, mi->size); 3721 SLIST_INSERT_HEAD(&new_head[nhash], ent, next); 3722 } 3723 } 3724 3725 ti->state = new_head; 3726 ti->data = mi->size; 3727 cfg->head = new_head; 3728 cfg->size = mi->size; 3729 3730 mi->main_ptr = old_head; 3731 } 3732 3733 /* 3734 * Free unneded array. 3735 */ 3736 static void 3737 ta_flush_mod_fhash(void *ta_buf) 3738 { 3739 struct mod_item *mi; 3740 3741 mi = (struct mod_item *)ta_buf; 3742 if (mi->main_ptr != NULL) 3743 free(mi->main_ptr, M_IPFW); 3744 } 3745 3746 struct table_algo flow_hash = { 3747 .name = "flow:hash", 3748 .type = IPFW_TABLE_FLOW, 3749 .flags = TA_FLAG_DEFAULT, 3750 .ta_buf_size = sizeof(struct ta_buf_fhash), 3751 .init = ta_init_fhash, 3752 .destroy = ta_destroy_fhash, 3753 .prepare_add = ta_prepare_add_fhash, 3754 .prepare_del = ta_prepare_del_fhash, 3755 .add = ta_add_fhash, 3756 .del = ta_del_fhash, 3757 .flush_entry = ta_flush_fhash_entry, 3758 .foreach = ta_foreach_fhash, 3759 .dump_tentry = ta_dump_fhash_tentry, 3760 .find_tentry = ta_find_fhash_tentry, 3761 .dump_tinfo = ta_dump_fhash_tinfo, 3762 .need_modify = ta_need_modify_fhash, 3763 .prepare_mod = ta_prepare_mod_fhash, 3764 .fill_mod = ta_fill_mod_fhash, 3765 .modify = ta_modify_fhash, 3766 .flush_mod = ta_flush_mod_fhash, 3767 }; 3768 3769 /* 3770 * Kernel fibs bindings. 3771 * 3772 * Implementation: 3773 * 3774 * Runtime part: 3775 * - fully relies on route API 3776 * - fib number is stored in ti->data 3777 * 3778 */ 3779 3780 static struct rtentry *lookup_kfib(void *key, int keylen, int fib); 3781 static int ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen, 3782 uint32_t *val); 3783 static int kfib_parse_opts(int *pfib, char *data); 3784 static void ta_print_kfib_config(void *ta_state, struct table_info *ti, 3785 char *buf, size_t bufsize); 3786 static int ta_init_kfib(struct ip_fw_chain *ch, void **ta_state, 3787 struct table_info *ti, char *data, uint8_t tflags); 3788 static void ta_destroy_kfib(void *ta_state, struct table_info *ti); 3789 static void ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti, 3790 ipfw_ta_tinfo *tinfo); 3791 static int contigmask(uint8_t *p, int len); 3792 static int ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e, 3793 ipfw_obj_tentry *tent); 3794 static int ta_find_kfib_tentry(void *ta_state, struct table_info *ti, 3795 ipfw_obj_tentry *tent); 3796 static void ta_foreach_kfib(void *ta_state, struct table_info *ti, 3797 ta_foreach_f *f, void *arg); 3798 3799 static struct rtentry * 3800 lookup_kfib(void *key, int keylen, int fib) 3801 { 3802 struct sockaddr *s; 3803 3804 if (keylen == 4) { 3805 struct sockaddr_in sin; 3806 bzero(&sin, sizeof(sin)); 3807 sin.sin_len = sizeof(struct sockaddr_in); 3808 sin.sin_family = AF_INET; 3809 sin.sin_addr.s_addr = *(in_addr_t *)key; 3810 s = (struct sockaddr *)&sin; 3811 } else { 3812 struct sockaddr_in6 sin6; 3813 bzero(&sin6, sizeof(sin6)); 3814 sin6.sin6_len = sizeof(struct sockaddr_in6); 3815 sin6.sin6_family = AF_INET6; 3816 sin6.sin6_addr = *(struct in6_addr *)key; 3817 s = (struct sockaddr *)&sin6; 3818 } 3819 3820 return (rtalloc1_fib(s, 0, 0, fib)); 3821 } 3822 3823 static int 3824 ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen, 3825 uint32_t *val) 3826 { 3827 struct rtentry *rte; 3828 3829 if ((rte = lookup_kfib(key, keylen, ti->data)) == NULL) 3830 return (0); 3831 3832 *val = 0; 3833 RTFREE_LOCKED(rte); 3834 3835 return (1); 3836 } 3837 3838 /* Parse 'fib=%d' */ 3839 static int 3840 kfib_parse_opts(int *pfib, char *data) 3841 { 3842 char *pdel, *pend, *s; 3843 int fibnum; 3844 3845 if (data == NULL) 3846 return (0); 3847 if ((pdel = strchr(data, ' ')) == NULL) 3848 return (0); 3849 while (*pdel == ' ') 3850 pdel++; 3851 if (strncmp(pdel, "fib=", 4) != 0) 3852 return (EINVAL); 3853 if ((s = strchr(pdel, ' ')) != NULL) 3854 *s++ = '\0'; 3855 3856 pdel += 4; 3857 /* Need \d+ */ 3858 fibnum = strtol(pdel, &pend, 10); 3859 if (*pend != '\0') 3860 return (EINVAL); 3861 3862 *pfib = fibnum; 3863 3864 return (0); 3865 } 3866 3867 static void 3868 ta_print_kfib_config(void *ta_state, struct table_info *ti, char *buf, 3869 size_t bufsize) 3870 { 3871 3872 if (ti->data != 0) 3873 snprintf(buf, bufsize, "%s fib=%lu", "addr:kfib", ti->data); 3874 else 3875 snprintf(buf, bufsize, "%s", "addr:kfib"); 3876 } 3877 3878 static int 3879 ta_init_kfib(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti, 3880 char *data, uint8_t tflags) 3881 { 3882 int error, fibnum; 3883 3884 fibnum = 0; 3885 if ((error = kfib_parse_opts(&fibnum, data)) != 0) 3886 return (error); 3887 3888 if (fibnum >= rt_numfibs) 3889 return (E2BIG); 3890 3891 ti->data = fibnum; 3892 ti->lookup = ta_lookup_kfib; 3893 3894 return (0); 3895 } 3896 3897 /* 3898 * Destroys table @ti 3899 */ 3900 static void 3901 ta_destroy_kfib(void *ta_state, struct table_info *ti) 3902 { 3903 3904 } 3905 3906 /* 3907 * Provide algo-specific table info 3908 */ 3909 static void 3910 ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo) 3911 { 3912 3913 tinfo->flags = IPFW_TATFLAGS_AFDATA; 3914 tinfo->taclass4 = IPFW_TACLASS_RADIX; 3915 tinfo->count4 = 0; 3916 tinfo->itemsize4 = sizeof(struct rtentry); 3917 tinfo->taclass6 = IPFW_TACLASS_RADIX; 3918 tinfo->count6 = 0; 3919 tinfo->itemsize6 = sizeof(struct rtentry); 3920 } 3921 3922 static int 3923 contigmask(uint8_t *p, int len) 3924 { 3925 int i, n; 3926 3927 for (i = 0; i < len ; i++) 3928 if ( (p[i/8] & (1 << (7 - (i%8)))) == 0) /* first bit unset */ 3929 break; 3930 for (n= i + 1; n < len; n++) 3931 if ( (p[n/8] & (1 << (7 - (n % 8)))) != 0) 3932 return (-1); /* mask not contiguous */ 3933 return (i); 3934 } 3935 3936 3937 static int 3938 ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e, 3939 ipfw_obj_tentry *tent) 3940 { 3941 struct rtentry *rte; 3942 #ifdef INET 3943 struct sockaddr_in *addr, *mask; 3944 #endif 3945 #ifdef INET6 3946 struct sockaddr_in6 *addr6, *mask6; 3947 #endif 3948 int len; 3949 3950 rte = (struct rtentry *)e; 3951 addr = (struct sockaddr_in *)rt_key(rte); 3952 mask = (struct sockaddr_in *)rt_mask(rte); 3953 len = 0; 3954 3955 /* Guess IPv4/IPv6 radix by sockaddr family */ 3956 #ifdef INET 3957 if (addr->sin_family == AF_INET) { 3958 tent->k.addr.s_addr = addr->sin_addr.s_addr; 3959 len = 32; 3960 if (mask != NULL) 3961 len = contigmask((uint8_t *)&mask->sin_addr, 32); 3962 if (len == -1) 3963 len = 0; 3964 tent->masklen = len; 3965 tent->subtype = AF_INET; 3966 tent->v.kidx = 0; /* Do we need to put GW here? */ 3967 } 3968 #endif 3969 #ifdef INET6 3970 if (addr->sin_family == AF_INET6) { 3971 addr6 = (struct sockaddr_in6 *)addr; 3972 mask6 = (struct sockaddr_in6 *)mask; 3973 memcpy(&tent->k, &addr6->sin6_addr, sizeof(struct in6_addr)); 3974 len = 128; 3975 if (mask6 != NULL) 3976 len = contigmask((uint8_t *)&mask6->sin6_addr, 128); 3977 if (len == -1) 3978 len = 0; 3979 tent->masklen = len; 3980 tent->subtype = AF_INET6; 3981 tent->v.kidx = 0; 3982 } 3983 #endif 3984 3985 return (0); 3986 } 3987 3988 static int 3989 ta_find_kfib_tentry(void *ta_state, struct table_info *ti, 3990 ipfw_obj_tentry *tent) 3991 { 3992 struct rtentry *rte; 3993 void *key; 3994 int keylen; 3995 3996 if (tent->subtype == AF_INET) { 3997 key = &tent->k.addr; 3998 keylen = sizeof(struct in_addr); 3999 } else { 4000 key = &tent->k.addr6; 4001 keylen = sizeof(struct in6_addr); 4002 } 4003 4004 if ((rte = lookup_kfib(key, keylen, ti->data)) == NULL) 4005 return (0); 4006 4007 if (rte != NULL) { 4008 ta_dump_kfib_tentry(ta_state, ti, rte, tent); 4009 RTFREE_LOCKED(rte); 4010 return (0); 4011 } 4012 4013 return (ENOENT); 4014 } 4015 4016 static void 4017 ta_foreach_kfib(void *ta_state, struct table_info *ti, ta_foreach_f *f, 4018 void *arg) 4019 { 4020 struct radix_node_head *rnh; 4021 int error; 4022 4023 rnh = rt_tables_get_rnh(ti->data, AF_INET); 4024 if (rnh != NULL) { 4025 RADIX_NODE_HEAD_RLOCK(rnh); 4026 error = rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg); 4027 RADIX_NODE_HEAD_RUNLOCK(rnh); 4028 } 4029 4030 rnh = rt_tables_get_rnh(ti->data, AF_INET6); 4031 if (rnh != NULL) { 4032 RADIX_NODE_HEAD_RLOCK(rnh); 4033 error = rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg); 4034 RADIX_NODE_HEAD_RUNLOCK(rnh); 4035 } 4036 } 4037 4038 struct table_algo addr_kfib = { 4039 .name = "addr:kfib", 4040 .type = IPFW_TABLE_ADDR, 4041 .flags = TA_FLAG_READONLY, 4042 .ta_buf_size = 0, 4043 .init = ta_init_kfib, 4044 .destroy = ta_destroy_kfib, 4045 .foreach = ta_foreach_kfib, 4046 .dump_tentry = ta_dump_kfib_tentry, 4047 .find_tentry = ta_find_kfib_tentry, 4048 .dump_tinfo = ta_dump_kfib_tinfo, 4049 .print_config = ta_print_kfib_config, 4050 }; 4051 4052 void 4053 ipfw_table_algo_init(struct ip_fw_chain *ch) 4054 { 4055 size_t sz; 4056 4057 /* 4058 * Register all algorithms presented here. 4059 */ 4060 sz = sizeof(struct table_algo); 4061 ipfw_add_table_algo(ch, &addr_radix, sz, &addr_radix.idx); 4062 ipfw_add_table_algo(ch, &addr_hash, sz, &addr_hash.idx); 4063 ipfw_add_table_algo(ch, &iface_idx, sz, &iface_idx.idx); 4064 ipfw_add_table_algo(ch, &number_array, sz, &number_array.idx); 4065 ipfw_add_table_algo(ch, &flow_hash, sz, &flow_hash.idx); 4066 ipfw_add_table_algo(ch, &addr_kfib, sz, &addr_kfib.idx); 4067 } 4068 4069 void 4070 ipfw_table_algo_destroy(struct ip_fw_chain *ch) 4071 { 4072 4073 ipfw_del_table_algo(ch, addr_radix.idx); 4074 ipfw_del_table_algo(ch, addr_hash.idx); 4075 ipfw_del_table_algo(ch, iface_idx.idx); 4076 ipfw_del_table_algo(ch, number_array.idx); 4077 ipfw_del_table_algo(ch, flow_hash.idx); 4078 ipfw_del_table_algo(ch, addr_kfib.idx); 4079 } 4080 4081 4082