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