sys/netpfil/ipfw/ip_fw_table_algo.c

   1 /*-
   2  * Copyright (c) 2014 Yandex LLC
   3  * Copyright (c) 2014 Alexander V. Chernikov
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #include <sys/cdefs.h>
  28 __FBSDID("$FreeBSD$");
  29
  30 /*
  31  * Lookup table algorithms.
  32  *
  33  */
  34
  35 #include "opt_ipfw.h"
  36 #include "opt_inet.h"
  37 #ifndef INET
  38 #error IPFIREWALL requires INET.
  39 #endif /* INET */
  40 #include "opt_inet6.h"
  41
  42 #include <sys/param.h>
  43 #include <sys/systm.h>
  44 #include <sys/malloc.h>
  45 #include <sys/kernel.h>
  46 #include <sys/lock.h>
  47 #include <sys/rwlock.h>
  48 #include <sys/rmlock.h>
  49 #include <sys/socket.h>
  50 #include <sys/queue.h>
  51 #include <net/if.h>     /* ip_fw.h requires IFNAMSIZ */
  52 #include <net/radix.h>
  53 #include <net/route.h>
  54 #include <net/route/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
 284 MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
 285
 286 /*
 287  * Utility structures/functions common to more than one algo
 288  */
 289
 290 struct mod_item {
 291         void    *main_ptr;
 292         size_t  size;
 293         void    *main_ptr6;
 294         size_t  size6;
 295 };
 296
 297 static int badd(const void *key, void *item, void *base, size_t nmemb,
 298     size_t size, int (*compar) (const void *, const void *));
 299 static 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
 327 struct radix_addr_entry {
 328         struct radix_node       rn[2];
 329         struct sockaddr_in      addr;
 330         uint32_t                value;
 331         uint8_t                 masklen;
 332 };
 333
 334 struct sa_in6 {
 335         uint8_t                 sin6_len;
 336         uint8_t                 sin6_family;
 337         uint8_t                 pad[2];
 338         struct in6_addr         sin6_addr;
 339 };
 340
 341 struct radix_addr_xentry {
 342         struct radix_node       rn[2];
 343         struct sa_in6           addr6;
 344         uint32_t                value;
 345         uint8_t                 masklen;
 346 };
 347
 348 struct radix_cfg {
 349         struct radix_node_head  *head4;
 350         struct radix_node_head  *head6;
 351         size_t                  count4;
 352         size_t                  count6;
 353 };
 354
 355 struct 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
 372 static int ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
 373     uint32_t *val);
 374 static int ta_init_radix(struct ip_fw_chain *ch, void **ta_state,
 375     struct table_info *ti, char *data, uint8_t tflags);
 376 static int flush_radix_entry(struct radix_node *rn, void *arg);
 377 static void ta_destroy_radix(void *ta_state, struct table_info *ti);
 378 static void ta_dump_radix_tinfo(void *ta_state, struct table_info *ti,
 379     ipfw_ta_tinfo *tinfo);
 380 static int ta_dump_radix_tentry(void *ta_state, struct table_info *ti,
 381     void *e, ipfw_obj_tentry *tent);
 382 static int ta_find_radix_tentry(void *ta_state, struct table_info *ti,
 383     ipfw_obj_tentry *tent);
 384 static void ta_foreach_radix(void *ta_state, struct table_info *ti,
 385     ta_foreach_f *f, void *arg);
 386 static void tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
 387     struct sockaddr *ma, int *set_mask);
 388 static int ta_prepare_add_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
 389     void *ta_buf);
 390 static int ta_add_radix(void *ta_state, struct table_info *ti,
 391     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
 392 static int ta_prepare_del_radix(struct ip_fw_chain *ch, struct tentry_info *tei,
 393     void *ta_buf);
 394 static int ta_del_radix(void *ta_state, struct table_info *ti,
 395     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
 396 static void ta_flush_radix_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
 397     void *ta_buf);
 398 static int ta_need_modify_radix(void *ta_state, struct table_info *ti,
 399     uint32_t count, uint64_t *pflags);
 400
 401 static int
 402 ta_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  */
 437 static int
 438 ta_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
 458 static int
 459 flush_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
 471 static void
 472 ta_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  */
 493 static void
 494 ta_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
 509 static int
 510 ta_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
 540 static int
 541 ta_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
 570 static void
 571 ta_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
 585 static inline void ipv6_writemask(struct in6_addr *addr6, uint8_t mask);
 586
 587 static inline void
 588 ipv6_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
 599 static void
 600 tei_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
 651 static int
 652 ta_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
 705 static int
 706 ta_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
 768 static int
 769 ta_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
 806 static int
 807 ta_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
 845 static void
 846 ta_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
 857 static int
 858 ta_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
 871 struct 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
 911 struct chashentry;
 912
 913 SLIST_HEAD(chashbhead, chashentry);
 914
 915 struct 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
 926 struct 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
 936 struct ta_buf_chash
 937 {
 938         void *ent_ptr;
 939         struct chashentry ent;
 940 };
 941
 942 #ifdef INET
 943 static __inline uint32_t hash_ip(uint32_t addr, int hsize);
 944 #endif
 945 #ifdef INET6
 946 static __inline uint32_t hash_ip6(struct in6_addr *addr6, int hsize);
 947 static __inline uint16_t hash_ip64(struct in6_addr *addr6, int hsize);
 948 static __inline uint32_t hash_ip6_slow(struct in6_addr *addr6, void *key,
 949     int mask, int hsize);
 950 static __inline uint32_t hash_ip6_al(struct in6_addr *addr6, void *key, int mask,
 951     int hsize);
 952 #endif
 953 static int ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
 954     uint32_t *val);
 955 static int ta_lookup_chash_aligned(struct table_info *ti, void *key,
 956     uint32_t keylen, uint32_t *val);
 957 static int ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
 958     uint32_t *val);
 959 static int chash_parse_opts(struct chash_cfg *cfg, char *data);
 960 static void ta_print_chash_config(void *ta_state, struct table_info *ti,
 961     char *buf, size_t bufsize);
 962 static int ta_log2(uint32_t v);
 963 static int ta_init_chash(struct ip_fw_chain *ch, void **ta_state,
 964     struct table_info *ti, char *data, uint8_t tflags);
 965 static void ta_destroy_chash(void *ta_state, struct table_info *ti);
 966 static void ta_dump_chash_tinfo(void *ta_state, struct table_info *ti,
 967     ipfw_ta_tinfo *tinfo);
 968 static int ta_dump_chash_tentry(void *ta_state, struct table_info *ti,
 969     void *e, ipfw_obj_tentry *tent);
 970 static uint32_t hash_ent(struct chashentry *ent, int af, int mlen,
 971     uint32_t size);
 972 static int tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent);
 973 static int ta_find_chash_tentry(void *ta_state, struct table_info *ti,
 974     ipfw_obj_tentry *tent);
 975 static void ta_foreach_chash(void *ta_state, struct table_info *ti,
 976     ta_foreach_f *f, void *arg);
 977 static int ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
 978     void *ta_buf);
 979 static int ta_add_chash(void *ta_state, struct table_info *ti,
 980     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
 981 static int ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
 982     void *ta_buf);
 983 static int ta_del_chash(void *ta_state, struct table_info *ti,
 984     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
 985 static void ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
 986     void *ta_buf);
 987 static int ta_need_modify_chash(void *ta_state, struct table_info *ti,
 988     uint32_t count, uint64_t *pflags);
 989 static int ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags);
 990 static int ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
 991     uint64_t *pflags);
 992 static void ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
 993     uint64_t pflags);
 994 static void ta_flush_mod_chash(void *ta_buf);
 995
 996
 997 #ifdef INET
 998 static __inline uint32_t
 999 hash_ip(uint32_t addr, int hsize)
1000 {
1001
1002         return (addr % (hsize - 1));
1003 }
1004 #endif
1005
1006 #ifdef INET6
1007 static __inline uint32_t
1008 hash_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
1019 static __inline uint16_t
1020 hash_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
1030 static __inline uint32_t
1031 hash_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
1041 static __inline uint32_t
1042 hash_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
1054 static int
1055 ta_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
1099 static int
1100 ta_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
1148 static int
1149 ta_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
1195 static int
1196 chash_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
1240 static void
1241 ta_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
1255 static int
1256 ta_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  */
1272 static int
1273 ta_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
1327 static void
1328 ta_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
1350 static void
1351 ta_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
1368 static int
1369 ta_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
1395 static uint32_t
1396 hash_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
1418 static int
1419 tei_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
1457 static int
1458 ta_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
1513 static void
1514 ta_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
1532 static int
1533 ta_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
1554 static int
1555 ta_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
1629 static int
1630 ta_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
1640 static int
1641 ta_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
1692 static void
1693 ta_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
1708 static int
1709 ta_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  */
1740 static int
1741 ta_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  */
1774 static int
1775 ta_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  */
1786 static void
1787 ta_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  */
1852 static void
1853 ta_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
1864 struct 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
1906 struct ifidx {
1907         uint16_t        kidx;
1908         uint16_t        spare;
1909         uint32_t        value;
1910 };
1911 #define DEFAULT_IFIDX_SIZE      64
1912
1913 struct iftable_cfg;
1914
1915 struct 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
1923 struct 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
1933 struct ta_buf_ifidx
1934 {
1935         struct ifentry *ife;
1936         uint32_t value;
1937 };
1938
1939 int compare_ifidx(const void *k, const void *v);
1940 static struct ifidx * ifidx_find(struct table_info *ti, void *key);
1941 static int ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
1942     uint32_t *val);
1943 static int ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state,
1944     struct table_info *ti, char *data, uint8_t tflags);
1945 static void ta_change_ti_ifidx(void *ta_state, struct table_info *ti);
1946 static int destroy_ifidx_locked(struct namedobj_instance *ii,
1947     struct named_object *no, void *arg);
1948 static void ta_destroy_ifidx(void *ta_state, struct table_info *ti);
1949 static void ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti,
1950     ipfw_ta_tinfo *tinfo);
1951 static int ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1952     void *ta_buf);
1953 static int ta_add_ifidx(void *ta_state, struct table_info *ti,
1954     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1955 static int ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1956     void *ta_buf);
1957 static int ta_del_ifidx(void *ta_state, struct table_info *ti,
1958     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
1959 static void ta_flush_ifidx_entry(struct ip_fw_chain *ch,
1960     struct tentry_info *tei, void *ta_buf);
1961 static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
1962 static int ta_need_modify_ifidx(void *ta_state, struct table_info *ti,
1963     uint32_t count, uint64_t *pflags);
1964 static int ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags);
1965 static int ta_fill_mod_ifidx(void *ta_state, struct table_info *ti,
1966     void *ta_buf, uint64_t *pflags);
1967 static void ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1968     uint64_t pflags);
1969 static void ta_flush_mod_ifidx(void *ta_buf);
1970 static int ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
1971     ipfw_obj_tentry *tent);
1972 static int ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
1973     ipfw_obj_tentry *tent);
1974 static int foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
1975     void *arg);
1976 static void ta_foreach_ifidx(void *ta_state, struct table_info *ti,
1977     ta_foreach_f *f, void *arg);
1978
1979 int
1980 compare_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  */
2002 static int
2003 badd(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  */
2051 static int
2052 bdel(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
2071 static struct ifidx *
2072 ifidx_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
2082 static int
2083 ta_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
2098 static int
2099 ta_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  */
2122 static void
2123 ta_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
2131 static int
2132 destroy_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  */
2151 static void
2152 ta_destroy_ifidx(void *ta_state, struct table_info *ti)
2153 {
2154         struct iftable_cfg *icfg;
2155         struct ip_fw_chain *ch;
2156
2157         icfg = (struct iftable_cfg *)ta_state;
2158         ch = icfg->ch;
2159
2160         if (icfg->main_ptr != NULL)
2161                 free(icfg->main_ptr, M_IPFW);
2162
2163         IPFW_UH_WLOCK(ch);
2164         ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
2165         IPFW_UH_WUNLOCK(ch);
2166
2167         ipfw_objhash_destroy(icfg->ii);
2168
2169         free(icfg, M_IPFW);
2170 }
2171
2172 /*
2173  * Provide algo-specific table info
2174  */
2175 static void
2176 ta_dump_ifidx_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2177 {
2178         struct iftable_cfg *cfg;
2179
2180         cfg = (struct iftable_cfg *)ta_state;
2181
2182         tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2183         tinfo->size4 = cfg->size;
2184         tinfo->count4 = cfg->used;
2185         tinfo->itemsize4 = sizeof(struct ifidx);
2186 }
2187
2188 /*
2189  * Prepare state to add to the table:
2190  * allocate ifentry and reference needed interface.
2191  */
2192 static int
2193 ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2194     void *ta_buf)
2195 {
2196         struct ta_buf_ifidx *tb;
2197         char *ifname;
2198         struct ifentry *ife;
2199
2200         tb = (struct ta_buf_ifidx *)ta_buf;
2201
2202         /* Check if string is terminated */
2203         ifname = (char *)tei->paddr;
2204         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2205                 return (EINVAL);
2206
2207         ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
2208         ife->ic.cb = if_notifier;
2209         ife->ic.cbdata = ife;
2210
2211         if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0) {
2212                 free(ife, M_IPFW_TBL);
2213                 return (EINVAL);
2214         }
2215
2216         /* Use ipfw_iface 'ifname' field as stable storage */
2217         ife->no.name = ife->ic.iface->ifname;
2218
2219         tb->ife = ife;
2220
2221         return (0);
2222 }
2223
2224 static int
2225 ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2226     void *ta_buf, uint32_t *pnum)
2227 {
2228         struct iftable_cfg *icfg;
2229         struct ifentry *ife, *tmp;
2230         struct ta_buf_ifidx *tb;
2231         struct ipfw_iface *iif;
2232         struct ifidx *ifi;
2233         char *ifname;
2234         uint32_t value;
2235
2236         tb = (struct ta_buf_ifidx *)ta_buf;
2237         ifname = (char *)tei->paddr;
2238         icfg = (struct iftable_cfg *)ta_state;
2239         ife = tb->ife;
2240
2241         ife->icfg = icfg;
2242         ife->value = tei->value;
2243
2244         tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2245
2246         if (tmp != NULL) {
2247                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2248                         return (EEXIST);
2249
2250                 /* Exchange values in @tmp and @tei */
2251                 value = tmp->value;
2252                 tmp->value = tei->value;
2253                 tei->value = value;
2254
2255                 iif = tmp->ic.iface;
2256                 if (iif->resolved != 0) {
2257                         /* We have to update runtime value, too */
2258                         ifi = ifidx_find(ti, &iif->ifindex);
2259                         ifi->value = ife->value;
2260                 }
2261
2262                 /* Indicate that update has happened instead of addition */
2263                 tei->flags |= TEI_FLAGS_UPDATED;
2264                 *pnum = 0;
2265                 return (0);
2266         }
2267
2268         if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2269                 return (EFBIG);
2270
2271         /* Link to internal list */
2272         ipfw_objhash_add(icfg->ii, &ife->no);
2273
2274         /* Link notifier (possible running its callback) */
2275         ipfw_iface_add_notify(icfg->ch, &ife->ic);
2276         icfg->count++;
2277
2278         tb->ife = NULL;
2279         *pnum = 1;
2280
2281         return (0);
2282 }
2283
2284 /*
2285  * Prepare to delete key from table.
2286  * Do basic interface name checks.
2287  */
2288 static int
2289 ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
2290     void *ta_buf)
2291 {
2292         struct ta_buf_ifidx *tb;
2293         char *ifname;
2294
2295         tb = (struct ta_buf_ifidx *)ta_buf;
2296
2297         /* Check if string is terminated */
2298         ifname = (char *)tei->paddr;
2299         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2300                 return (EINVAL);
2301
2302         return (0);
2303 }
2304
2305 /*
2306  * Remove key from both configuration list and
2307  * runtime array. Removed interface notification.
2308  */
2309 static int
2310 ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2311     void *ta_buf, uint32_t *pnum)
2312 {
2313         struct iftable_cfg *icfg;
2314         struct ifentry *ife;
2315         struct ta_buf_ifidx *tb;
2316         char *ifname;
2317         uint16_t ifindex;
2318         int res;
2319
2320         tb = (struct ta_buf_ifidx *)ta_buf;
2321         ifname = (char *)tei->paddr;
2322         icfg = (struct iftable_cfg *)ta_state;
2323
2324         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2325
2326         if (ife == NULL)
2327                 return (ENOENT);
2328
2329         if (ife->linked != 0) {
2330                 /* We have to remove item from runtime */
2331                 ifindex = ife->ic.iface->ifindex;
2332
2333                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2334                     sizeof(struct ifidx), compare_ifidx);
2335
2336                 KASSERT(res == 1, ("index %d does not exist", ifindex));
2337                 icfg->used--;
2338                 ti->data = icfg->used;
2339                 ife->linked = 0;
2340         }
2341
2342         /* Unlink from local list */
2343         ipfw_objhash_del(icfg->ii, &ife->no);
2344         /* Unlink notifier and deref */
2345         ipfw_iface_del_notify(icfg->ch, &ife->ic);
2346         ipfw_iface_unref(icfg->ch, &ife->ic);
2347
2348         icfg->count--;
2349         tei->value = ife->value;
2350
2351         tb->ife = ife;
2352         *pnum = 1;
2353
2354         return (0);
2355 }
2356
2357 /*
2358  * Flush deleted entry.
2359  * Drops interface reference and frees entry.
2360  */
2361 static void
2362 ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2363     void *ta_buf)
2364 {
2365         struct ta_buf_ifidx *tb;
2366
2367         tb = (struct ta_buf_ifidx *)ta_buf;
2368
2369         if (tb->ife != NULL)
2370                 free(tb->ife, M_IPFW_TBL);
2371 }
2372
2373
2374 /*
2375  * Handle interface announce/withdrawal for particular table.
2376  * Every real runtime array modification happens here.
2377  */
2378 static void
2379 if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
2380 {
2381         struct ifentry *ife;
2382         struct ifidx ifi;
2383         struct iftable_cfg *icfg;
2384         struct table_info *ti;
2385         int res;
2386
2387         ife = (struct ifentry *)cbdata;
2388         icfg = ife->icfg;
2389         ti = icfg->ti;
2390
2391         KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
2392
2393         if (ife->linked == 0 && ifindex != 0) {
2394                 /* Interface announce */
2395                 ifi.kidx = ifindex;
2396                 ifi.spare = 0;
2397                 ifi.value = ife->value;
2398                 res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used,
2399                     sizeof(struct ifidx), compare_ifidx);
2400                 KASSERT(res == 1, ("index %d already exists", ifindex));
2401                 icfg->used++;
2402                 ti->data = icfg->used;
2403                 ife->linked = 1;
2404         } else if (ife->linked != 0 && ifindex == 0) {
2405                 /* Interface withdrawal */
2406                 ifindex = ife->ic.iface->ifindex;
2407
2408                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
2409                     sizeof(struct ifidx), compare_ifidx);
2410
2411                 KASSERT(res == 1, ("index %d does not exist", ifindex));
2412                 icfg->used--;
2413                 ti->data = icfg->used;
2414                 ife->linked = 0;
2415         }
2416 }
2417
2418
2419 /*
2420  * Table growing callbacks.
2421  */
2422
2423 static int
2424 ta_need_modify_ifidx(void *ta_state, struct table_info *ti, uint32_t count,
2425     uint64_t *pflags)
2426 {
2427         struct iftable_cfg *cfg;
2428         uint32_t size;
2429
2430         cfg = (struct iftable_cfg *)ta_state;
2431
2432         size = cfg->size;
2433         while (size < cfg->count + count)
2434                 size *= 2;
2435
2436         if (size != cfg->size) {
2437                 *pflags = size;
2438                 return (1);
2439         }
2440
2441         return (0);
2442 }
2443
2444 /*
2445  * Allocate ned, larger runtime ifidx array.
2446  */
2447 static int
2448 ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
2449 {
2450         struct mod_item *mi;
2451
2452         mi = (struct mod_item *)ta_buf;
2453
2454         memset(mi, 0, sizeof(struct mod_item));
2455         mi->size = *pflags;
2456         mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
2457             M_WAITOK | M_ZERO);
2458
2459         return (0);
2460 }
2461
2462 /*
2463  * Copy data from old runtime array to new one.
2464  */
2465 static int
2466 ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2467     uint64_t *pflags)
2468 {
2469         struct mod_item *mi;
2470         struct iftable_cfg *icfg;
2471
2472         mi = (struct mod_item *)ta_buf;
2473         icfg = (struct iftable_cfg *)ta_state;
2474
2475         /* Check if we still need to grow array */
2476         if (icfg->size >= mi->size) {
2477                 *pflags = 0;
2478                 return (0);
2479         }
2480
2481         memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
2482
2483         return (0);
2484 }
2485
2486 /*
2487  * Switch old & new arrays.
2488  */
2489 static void
2490 ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2491     uint64_t pflags)
2492 {
2493         struct mod_item *mi;
2494         struct iftable_cfg *icfg;
2495         void *old_ptr;
2496
2497         mi = (struct mod_item *)ta_buf;
2498         icfg = (struct iftable_cfg *)ta_state;
2499
2500         old_ptr = icfg->main_ptr;
2501         icfg->main_ptr = mi->main_ptr;
2502         icfg->size = mi->size;
2503         ti->state = icfg->main_ptr;
2504
2505         mi->main_ptr = old_ptr;
2506 }
2507
2508 /*
2509  * Free unneded array.
2510  */
2511 static void
2512 ta_flush_mod_ifidx(void *ta_buf)
2513 {
2514         struct mod_item *mi;
2515
2516         mi = (struct mod_item *)ta_buf;
2517         if (mi->main_ptr != NULL)
2518                 free(mi->main_ptr, M_IPFW);
2519 }
2520
2521 static int
2522 ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
2523     ipfw_obj_tentry *tent)
2524 {
2525         struct ifentry *ife;
2526
2527         ife = (struct ifentry *)e;
2528
2529         tent->masklen = 8 * IF_NAMESIZE;
2530         memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
2531         tent->v.kidx = ife->value;
2532
2533         return (0);
2534 }
2535
2536 static int
2537 ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
2538     ipfw_obj_tentry *tent)
2539 {
2540         struct iftable_cfg *icfg;
2541         struct ifentry *ife;
2542         char *ifname;
2543
2544         icfg = (struct iftable_cfg *)ta_state;
2545         ifname = tent->k.iface;
2546
2547         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2548                 return (EINVAL);
2549
2550         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2551
2552         if (ife != NULL) {
2553                 ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
2554                 return (0);
2555         }
2556
2557         return (ENOENT);
2558 }
2559
2560 struct wa_ifidx {
2561         ta_foreach_f    *f;
2562         void            *arg;
2563 };
2564
2565 static int
2566 foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
2567     void *arg)
2568 {
2569         struct ifentry *ife;
2570         struct wa_ifidx *wa;
2571
2572         ife = (struct ifentry *)no;
2573         wa = (struct wa_ifidx *)arg;
2574
2575         wa->f(ife, wa->arg);
2576         return (0);
2577 }
2578
2579 static void
2580 ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2581     void *arg)
2582 {
2583         struct iftable_cfg *icfg;
2584         struct wa_ifidx wa;
2585
2586         icfg = (struct iftable_cfg *)ta_state;
2587
2588         wa.f = f;
2589         wa.arg = arg;
2590
2591         ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
2592 }
2593
2594 struct table_algo iface_idx = {
2595         .name           = "iface:array",
2596         .type           = IPFW_TABLE_INTERFACE,
2597         .flags          = TA_FLAG_DEFAULT,
2598         .ta_buf_size    = sizeof(struct ta_buf_ifidx),
2599         .init           = ta_init_ifidx,
2600         .destroy        = ta_destroy_ifidx,
2601         .prepare_add    = ta_prepare_add_ifidx,
2602         .prepare_del    = ta_prepare_del_ifidx,
2603         .add            = ta_add_ifidx,
2604         .del            = ta_del_ifidx,
2605         .flush_entry    = ta_flush_ifidx_entry,
2606         .foreach        = ta_foreach_ifidx,
2607         .dump_tentry    = ta_dump_ifidx_tentry,
2608         .find_tentry    = ta_find_ifidx_tentry,
2609         .dump_tinfo     = ta_dump_ifidx_tinfo,
2610         .need_modify    = ta_need_modify_ifidx,
2611         .prepare_mod    = ta_prepare_mod_ifidx,
2612         .fill_mod       = ta_fill_mod_ifidx,
2613         .modify         = ta_modify_ifidx,
2614         .flush_mod      = ta_flush_mod_ifidx,
2615         .change_ti      = ta_change_ti_ifidx,
2616 };
2617
2618 /*
2619  * Number array cmds.
2620  *
2621  * Implementation:
2622  *
2623  * Runtime part:
2624  * - sorted array of "struct numarray" pointed by ti->state.
2625  *   Array is allocated with rounding up to NUMARRAY_CHUNK.
2626  * - current array size is stored in ti->data
2627  *
2628  */
2629
2630 struct numarray {
2631         uint32_t        number;
2632         uint32_t        value;
2633 };
2634
2635 struct numarray_cfg {
2636         void    *main_ptr;
2637         size_t  size;   /* Number of items allocated in array */
2638         size_t  used;   /* Number of items _active_ now */
2639 };
2640
2641 struct ta_buf_numarray
2642 {
2643         struct numarray na;
2644 };
2645
2646 int compare_numarray(const void *k, const void *v);
2647 static struct numarray *numarray_find(struct table_info *ti, void *key);
2648 static int ta_lookup_numarray(struct table_info *ti, void *key,
2649     uint32_t keylen, uint32_t *val);
2650 static int ta_init_numarray(struct ip_fw_chain *ch, void **ta_state,
2651     struct table_info *ti, char *data, uint8_t tflags);
2652 static void ta_destroy_numarray(void *ta_state, struct table_info *ti);
2653 static void ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti,
2654     ipfw_ta_tinfo *tinfo);
2655 static int ta_prepare_add_numarray(struct ip_fw_chain *ch,
2656     struct tentry_info *tei, void *ta_buf);
2657 static int ta_add_numarray(void *ta_state, struct table_info *ti,
2658     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2659 static int ta_del_numarray(void *ta_state, struct table_info *ti,
2660     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
2661 static void ta_flush_numarray_entry(struct ip_fw_chain *ch,
2662     struct tentry_info *tei, void *ta_buf);
2663 static int ta_need_modify_numarray(void *ta_state, struct table_info *ti,
2664     uint32_t count, uint64_t *pflags);
2665 static int ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags);
2666 static int ta_fill_mod_numarray(void *ta_state, struct table_info *ti,
2667     void *ta_buf, uint64_t *pflags);
2668 static void ta_modify_numarray(void *ta_state, struct table_info *ti,
2669     void *ta_buf, uint64_t pflags);
2670 static void ta_flush_mod_numarray(void *ta_buf);
2671 static int ta_dump_numarray_tentry(void *ta_state, struct table_info *ti,
2672     void *e, ipfw_obj_tentry *tent);
2673 static int ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2674     ipfw_obj_tentry *tent);
2675 static void ta_foreach_numarray(void *ta_state, struct table_info *ti,
2676     ta_foreach_f *f, void *arg);
2677
2678 int
2679 compare_numarray(const void *k, const void *v)
2680 {
2681         const struct numarray *na;
2682         uint32_t key;
2683
2684         key = *((const uint32_t *)k);
2685         na = (const struct numarray *)v;
2686
2687         if (key < na->number)
2688                 return (-1);
2689         else if (key > na->number)
2690                 return (1);
2691
2692         return (0);
2693 }
2694
2695 static struct numarray *
2696 numarray_find(struct table_info *ti, void *key)
2697 {
2698         struct numarray *ri;
2699
2700         ri = bsearch(key, ti->state, ti->data, sizeof(struct numarray),
2701             compare_ifidx);
2702
2703         return (ri);
2704 }
2705
2706 static int
2707 ta_lookup_numarray(struct table_info *ti, void *key, uint32_t keylen,
2708     uint32_t *val)
2709 {
2710         struct numarray *ri;
2711
2712         ri = numarray_find(ti, key);
2713
2714         if (ri != NULL) {
2715                 *val = ri->value;
2716                 return (1);
2717         }
2718
2719         return (0);
2720 }
2721
2722 static int
2723 ta_init_numarray(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2724     char *data, uint8_t tflags)
2725 {
2726         struct numarray_cfg *cfg;
2727
2728         cfg = malloc(sizeof(*cfg), M_IPFW, M_WAITOK | M_ZERO);
2729
2730         cfg->size = 16;
2731         cfg->main_ptr = malloc(sizeof(struct numarray) * cfg->size, M_IPFW,
2732             M_WAITOK | M_ZERO);
2733
2734         *ta_state = cfg;
2735         ti->state = cfg->main_ptr;
2736         ti->lookup = ta_lookup_numarray;
2737
2738         return (0);
2739 }
2740
2741 /*
2742  * Destroys table @ti
2743  */
2744 static void
2745 ta_destroy_numarray(void *ta_state, struct table_info *ti)
2746 {
2747         struct numarray_cfg *cfg;
2748
2749         cfg = (struct numarray_cfg *)ta_state;
2750
2751         if (cfg->main_ptr != NULL)
2752                 free(cfg->main_ptr, M_IPFW);
2753
2754         free(cfg, M_IPFW);
2755 }
2756
2757 /*
2758  * Provide algo-specific table info
2759  */
2760 static void
2761 ta_dump_numarray_tinfo(void *ta_state, struct table_info *ti, ipfw_ta_tinfo *tinfo)
2762 {
2763         struct numarray_cfg *cfg;
2764
2765         cfg = (struct numarray_cfg *)ta_state;
2766
2767         tinfo->taclass4 = IPFW_TACLASS_ARRAY;
2768         tinfo->size4 = cfg->size;
2769         tinfo->count4 = cfg->used;
2770         tinfo->itemsize4 = sizeof(struct numarray);
2771 }
2772
2773 /*
2774  * Prepare for addition/deletion to an array.
2775  */
2776 static int
2777 ta_prepare_add_numarray(struct ip_fw_chain *ch, struct tentry_info *tei,
2778     void *ta_buf)
2779 {
2780         struct ta_buf_numarray *tb;
2781
2782         tb = (struct ta_buf_numarray *)ta_buf;
2783
2784         tb->na.number = *((uint32_t *)tei->paddr);
2785
2786         return (0);
2787 }
2788
2789 static int
2790 ta_add_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2791     void *ta_buf, uint32_t *pnum)
2792 {
2793         struct numarray_cfg *cfg;
2794         struct ta_buf_numarray *tb;
2795         struct numarray *ri;
2796         int res;
2797         uint32_t value;
2798
2799         tb = (struct ta_buf_numarray *)ta_buf;
2800         cfg = (struct numarray_cfg *)ta_state;
2801
2802         /* Read current value from @tei */
2803         tb->na.value = tei->value;
2804
2805         ri = numarray_find(ti, &tb->na.number);
2806
2807         if (ri != NULL) {
2808                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2809                         return (EEXIST);
2810
2811                 /* Exchange values between ri and @tei */
2812                 value = ri->value;
2813                 ri->value = tei->value;
2814                 tei->value = value;
2815                 /* Indicate that update has happened instead of addition */
2816                 tei->flags |= TEI_FLAGS_UPDATED;
2817                 *pnum = 0;
2818                 return (0);
2819         }
2820
2821         if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2822                 return (EFBIG);
2823
2824         res = badd(&tb->na.number, &tb->na, cfg->main_ptr, cfg->used,
2825             sizeof(struct numarray), compare_numarray);
2826
2827         KASSERT(res == 1, ("number %d already exists", tb->na.number));
2828         cfg->used++;
2829         ti->data = cfg->used;
2830         *pnum = 1;
2831
2832         return (0);
2833 }
2834
2835 /*
2836  * Remove key from both configuration list and
2837  * runtime array. Removed interface notification.
2838  */
2839 static int
2840 ta_del_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2841     void *ta_buf, uint32_t *pnum)
2842 {
2843         struct numarray_cfg *cfg;
2844         struct ta_buf_numarray *tb;
2845         struct numarray *ri;
2846         int res;
2847
2848         tb = (struct ta_buf_numarray *)ta_buf;
2849         cfg = (struct numarray_cfg *)ta_state;
2850
2851         ri = numarray_find(ti, &tb->na.number);
2852         if (ri == NULL)
2853                 return (ENOENT);
2854
2855         tei->value = ri->value;
2856
2857         res = bdel(&tb->na.number, cfg->main_ptr, cfg->used,
2858             sizeof(struct numarray), compare_numarray);
2859
2860         KASSERT(res == 1, ("number %u does not exist", tb->na.number));
2861         cfg->used--;
2862         ti->data = cfg->used;
2863         *pnum = 1;
2864
2865         return (0);
2866 }
2867
2868 static void
2869 ta_flush_numarray_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2870     void *ta_buf)
2871 {
2872
2873         /* We don't have any state, do nothing */
2874 }
2875
2876
2877 /*
2878  * Table growing callbacks.
2879  */
2880
2881 static int
2882 ta_need_modify_numarray(void *ta_state, struct table_info *ti, uint32_t count,
2883     uint64_t *pflags)
2884 {
2885         struct numarray_cfg *cfg;
2886         size_t size;
2887
2888         cfg = (struct numarray_cfg *)ta_state;
2889
2890         size = cfg->size;
2891         while (size < cfg->used + count)
2892                 size *= 2;
2893
2894         if (size != cfg->size) {
2895                 *pflags = size;
2896                 return (1);
2897         }
2898
2899         return (0);
2900 }
2901
2902 /*
2903  * Allocate new, larger runtime array.
2904  */
2905 static int
2906 ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags)
2907 {
2908         struct mod_item *mi;
2909
2910         mi = (struct mod_item *)ta_buf;
2911
2912         memset(mi, 0, sizeof(struct mod_item));
2913         mi->size = *pflags;
2914         mi->main_ptr = malloc(sizeof(struct numarray) * mi->size, M_IPFW,
2915             M_WAITOK | M_ZERO);
2916
2917         return (0);
2918 }
2919
2920 /*
2921  * Copy data from old runtime array to new one.
2922  */
2923 static int
2924 ta_fill_mod_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2925     uint64_t *pflags)
2926 {
2927         struct mod_item *mi;
2928         struct numarray_cfg *cfg;
2929
2930         mi = (struct mod_item *)ta_buf;
2931         cfg = (struct numarray_cfg *)ta_state;
2932
2933         /* Check if we still need to grow array */
2934         if (cfg->size >= mi->size) {
2935                 *pflags = 0;
2936                 return (0);
2937         }
2938
2939         memcpy(mi->main_ptr, cfg->main_ptr, cfg->used * sizeof(struct numarray));
2940
2941         return (0);
2942 }
2943
2944 /*
2945  * Switch old & new arrays.
2946  */
2947 static void
2948 ta_modify_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2949     uint64_t pflags)
2950 {
2951         struct mod_item *mi;
2952         struct numarray_cfg *cfg;
2953         void *old_ptr;
2954
2955         mi = (struct mod_item *)ta_buf;
2956         cfg = (struct numarray_cfg *)ta_state;
2957
2958         old_ptr = cfg->main_ptr;
2959         cfg->main_ptr = mi->main_ptr;
2960         cfg->size = mi->size;
2961         ti->state = cfg->main_ptr;
2962
2963         mi->main_ptr = old_ptr;
2964 }
2965
2966 /*
2967  * Free unneded array.
2968  */
2969 static void
2970 ta_flush_mod_numarray(void *ta_buf)
2971 {
2972         struct mod_item *mi;
2973
2974         mi = (struct mod_item *)ta_buf;
2975         if (mi->main_ptr != NULL)
2976                 free(mi->main_ptr, M_IPFW);
2977 }
2978
2979 static int
2980 ta_dump_numarray_tentry(void *ta_state, struct table_info *ti, void *e,
2981     ipfw_obj_tentry *tent)
2982 {
2983         struct numarray *na;
2984
2985         na = (struct numarray *)e;
2986
2987         tent->k.key = na->number;
2988         tent->v.kidx = na->value;
2989
2990         return (0);
2991 }
2992
2993 static int
2994 ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2995     ipfw_obj_tentry *tent)
2996 {
2997         struct numarray_cfg *cfg;
2998         struct numarray *ri;
2999
3000         cfg = (struct numarray_cfg *)ta_state;
3001
3002         ri = numarray_find(ti, &tent->k.key);
3003
3004         if (ri != NULL) {
3005                 ta_dump_numarray_tentry(ta_state, ti, ri, tent);
3006                 return (0);
3007         }
3008
3009         return (ENOENT);
3010 }
3011
3012 static void
3013 ta_foreach_numarray(void *ta_state, struct table_info *ti, ta_foreach_f *f,
3014     void *arg)
3015 {
3016         struct numarray_cfg *cfg;
3017         struct numarray *array;
3018         int i;
3019
3020         cfg = (struct numarray_cfg *)ta_state;
3021         array = cfg->main_ptr;
3022
3023         for (i = 0; i < cfg->used; i++)
3024                 f(&array[i], arg);
3025 }
3026
3027 struct table_algo number_array = {
3028         .name           = "number:array",
3029         .type           = IPFW_TABLE_NUMBER,
3030         .ta_buf_size    = sizeof(struct ta_buf_numarray),
3031         .init           = ta_init_numarray,
3032         .destroy        = ta_destroy_numarray,
3033         .prepare_add    = ta_prepare_add_numarray,
3034         .prepare_del    = ta_prepare_add_numarray,
3035         .add            = ta_add_numarray,
3036         .del            = ta_del_numarray,
3037         .flush_entry    = ta_flush_numarray_entry,
3038         .foreach        = ta_foreach_numarray,
3039         .dump_tentry    = ta_dump_numarray_tentry,
3040         .find_tentry    = ta_find_numarray_tentry,
3041         .dump_tinfo     = ta_dump_numarray_tinfo,
3042         .need_modify    = ta_need_modify_numarray,
3043         .prepare_mod    = ta_prepare_mod_numarray,
3044         .fill_mod       = ta_fill_mod_numarray,
3045         .modify         = ta_modify_numarray,
3046         .flush_mod      = ta_flush_mod_numarray,
3047 };
3048
3049 /*
3050  * flow:hash cmds
3051  *
3052  *
3053  * ti->data:
3054  * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
3055  * [        8][        8[          8][         8]
3056  *
3057  * inv.mask4: 32 - mask
3058  * inv.mask6:
3059  * 1) _slow lookup: mask
3060  * 2) _aligned: (128 - mask) / 8
3061  * 3) _64: 8
3062  *
3063  *
3064  * pflags:
3065  * [hsize4][hsize6]
3066  * [    16][    16]
3067  */
3068
3069 struct fhashentry;
3070
3071 SLIST_HEAD(fhashbhead, fhashentry);
3072
3073 struct fhashentry {
3074         SLIST_ENTRY(fhashentry) next;
3075         uint8_t         af;
3076         uint8_t         proto;
3077         uint16_t        spare0;
3078         uint16_t        dport;
3079         uint16_t        sport;
3080         uint32_t        value;
3081         uint32_t        spare1;
3082 };
3083
3084 struct fhashentry4 {
3085         struct fhashentry       e;
3086         struct in_addr          dip;
3087         struct in_addr          sip;
3088 };
3089
3090 struct fhashentry6 {
3091         struct fhashentry       e;
3092         struct in6_addr         dip6;
3093         struct in6_addr         sip6;
3094 };
3095
3096 struct fhash_cfg {
3097         struct fhashbhead       *head;
3098         size_t                  size;
3099         size_t                  items;
3100         struct fhashentry4      fe4;
3101         struct fhashentry6      fe6;
3102 };
3103
3104 struct ta_buf_fhash {
3105         void    *ent_ptr;
3106         struct fhashentry6 fe6;
3107 };
3108
3109 static __inline int cmp_flow_ent(struct fhashentry *a,
3110     struct fhashentry *b, size_t sz);
3111 static __inline uint32_t hash_flow4(struct fhashentry4 *f, int hsize);
3112 static __inline uint32_t hash_flow6(struct fhashentry6 *f, int hsize);
3113 static uint32_t hash_flow_ent(struct fhashentry *ent, uint32_t size);
3114 static int ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3115     uint32_t *val);
3116 static int ta_init_fhash(struct ip_fw_chain *ch, void **ta_state,
3117 struct table_info *ti, char *data, uint8_t tflags);
3118 static void ta_destroy_fhash(void *ta_state, struct table_info *ti);
3119 static void ta_dump_fhash_tinfo(void *ta_state, struct table_info *ti,
3120     ipfw_ta_tinfo *tinfo);
3121 static int ta_dump_fhash_tentry(void *ta_state, struct table_info *ti,
3122     void *e, ipfw_obj_tentry *tent);
3123 static int tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent);
3124 static int ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
3125     ipfw_obj_tentry *tent);
3126 static void ta_foreach_fhash(void *ta_state, struct table_info *ti,
3127     ta_foreach_f *f, void *arg);
3128 static int ta_prepare_add_fhash(struct ip_fw_chain *ch,
3129     struct tentry_info *tei, void *ta_buf);
3130 static int ta_add_fhash(void *ta_state, struct table_info *ti,
3131     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3132 static int ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3133     void *ta_buf);
3134 static int ta_del_fhash(void *ta_state, struct table_info *ti,
3135     struct tentry_info *tei, void *ta_buf, uint32_t *pnum);
3136 static void ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3137     void *ta_buf);
3138 static int ta_need_modify_fhash(void *ta_state, struct table_info *ti,
3139     uint32_t count, uint64_t *pflags);
3140 static int ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags);
3141 static int ta_fill_mod_fhash(void *ta_state, struct table_info *ti,
3142     void *ta_buf, uint64_t *pflags);
3143 static void ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3144     uint64_t pflags);
3145 static void ta_flush_mod_fhash(void *ta_buf);
3146
3147 static __inline int
3148 cmp_flow_ent(struct fhashentry *a, struct fhashentry *b, size_t sz)
3149 {
3150         uint64_t *ka, *kb;
3151
3152         ka = (uint64_t *)(&a->next + 1);
3153         kb = (uint64_t *)(&b->next + 1);
3154
3155         if (*ka == *kb && (memcmp(a + 1, b + 1, sz) == 0))
3156                 return (1);
3157
3158         return (0);
3159 }
3160
3161 static __inline uint32_t
3162 hash_flow4(struct fhashentry4 *f, int hsize)
3163 {
3164         uint32_t i;
3165
3166         i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport);
3167
3168         return (i % (hsize - 1));
3169 }
3170
3171 static __inline uint32_t
3172 hash_flow6(struct fhashentry6 *f, int hsize)
3173 {
3174         uint32_t i;
3175
3176         i = (f->dip6.__u6_addr.__u6_addr32[2]) ^
3177             (f->dip6.__u6_addr.__u6_addr32[3]) ^
3178             (f->sip6.__u6_addr.__u6_addr32[2]) ^
3179             (f->sip6.__u6_addr.__u6_addr32[3]) ^
3180             (f->e.dport) ^ (f->e.sport);
3181
3182         return (i % (hsize - 1));
3183 }
3184
3185 static uint32_t
3186 hash_flow_ent(struct fhashentry *ent, uint32_t size)
3187 {
3188         uint32_t hash;
3189
3190         if (ent->af == AF_INET) {
3191                 hash = hash_flow4((struct fhashentry4 *)ent, size);
3192         } else {
3193                 hash = hash_flow6((struct fhashentry6 *)ent, size);
3194         }
3195
3196         return (hash);
3197 }
3198
3199 static int
3200 ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
3201     uint32_t *val)
3202 {
3203         struct fhashbhead *head;
3204         struct fhashentry *ent;
3205         struct fhashentry4 *m4;
3206         struct ipfw_flow_id *id;
3207         uint32_t hsize;
3208         uint16_t hash;
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  */
3266 static int
3267 ta_init_fhash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
3268     char *data, uint8_t tflags)
3269 {
3270         struct fhash_cfg *cfg;
3271         struct fhashentry4 *fe4;
3272         struct fhashentry6 *fe6;
3273         u_int i;
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
3320 static void
3321 ta_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  */
3340 static void
3341 ta_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
3355 static int
3356 ta_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
3395 static int
3396 tei_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
3434 static int
3435 ta_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
3479 static void
3480 ta_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
3494 static int
3495 ta_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
3524 static int
3525 ta_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
3586 static int
3587 ta_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
3597 static int
3598 ta_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
3636 static void
3637 ta_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
3652 static int
3653 ta_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  */
3671 static int
3672 ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags)
3673 {
3674         struct mod_item *mi;
3675         struct fhashbhead *head;
3676         u_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  */
3695 static int
3696 ta_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  */
3707 static void
3708 ta_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  */
3744 static void
3745 ta_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
3754 struct 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
3788 static int ta_lookup_kfib(struct table_info *ti, void *key, uint32_t keylen,
3789     uint32_t *val);
3790 static int kfib_parse_opts(int *pfib, char *data);
3791 static void ta_print_kfib_config(void *ta_state, struct table_info *ti,
3792     char *buf, size_t bufsize);
3793 static int ta_init_kfib(struct ip_fw_chain *ch, void **ta_state,
3794     struct table_info *ti, char *data, uint8_t tflags);
3795 static void ta_destroy_kfib(void *ta_state, struct table_info *ti);
3796 static void ta_dump_kfib_tinfo(void *ta_state, struct table_info *ti,
3797     ipfw_ta_tinfo *tinfo);
3798 static int contigmask(uint8_t *p, int len);
3799 static int ta_dump_kfib_tentry(void *ta_state, struct table_info *ti, void *e,
3800     ipfw_obj_tentry *tent);
3801 static int ta_dump_kfib_tentry_int(struct sockaddr *paddr,
3802     struct sockaddr *pmask, ipfw_obj_tentry *tent);
3803 static int ta_find_kfib_tentry(void *ta_state, struct table_info *ti,
3804     ipfw_obj_tentry *tent);
3805 static void ta_foreach_kfib(void *ta_state, struct table_info *ti,
3806     ta_foreach_f *f, void *arg);
3807
3808
3809 static int
3810 ta_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' */
3845 static int
3846 kfib_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
3873 static void
3874 ta_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
3884 static int
3885 ta_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  */
3906 static void
3907 ta_destroy_kfib(void *ta_state, struct table_info *ti)
3908 {
3909
3910 }
3911
3912 /*
3913  * Provide algo-specific table info
3914  */
3915 static void
3916 ta_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
3928 static int
3929 contigmask(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
3943 static int
3944 ta_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
3954 static int
3955 ta_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
4004 static int
4005 ta_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
4047 static void
4048 ta_foreach_kfib(void *ta_state, struct table_info *ti, ta_foreach_f *f,
4049     void *arg)
4050 {
4051         RIB_RLOCK_TRACKER;
4052         struct rib_head *rh;
4053         int error;
4054
4055         rh = rt_tables_get_rnh(ti->data, AF_INET);
4056         if (rh != NULL) {
4057                 RIB_RLOCK(rh);
4058                 error = rh->rnh_walktree(&rh->head, (walktree_f_t *)f, arg);
4059                 RIB_RUNLOCK(rh);
4060         }
4061
4062         rh = rt_tables_get_rnh(ti->data, AF_INET6);
4063         if (rh != NULL) {
4064                 RIB_RLOCK(rh);
4065                 error = rh->rnh_walktree(&rh->head, (walktree_f_t *)f, arg);
4066                 RIB_RUNLOCK(rh);
4067         }
4068 }
4069
4070 struct table_algo addr_kfib = {
4071         .name           = "addr:kfib",
4072         .type           = IPFW_TABLE_ADDR,
4073         .flags          = TA_FLAG_READONLY,
4074         .ta_buf_size    = 0,
4075         .init           = ta_init_kfib,
4076         .destroy        = ta_destroy_kfib,
4077         .foreach        = ta_foreach_kfib,
4078         .dump_tentry    = ta_dump_kfib_tentry,
4079         .find_tentry    = ta_find_kfib_tentry,
4080         .dump_tinfo     = ta_dump_kfib_tinfo,
4081         .print_config   = ta_print_kfib_config,
4082 };
4083
4084 void
4085 ipfw_table_algo_init(struct ip_fw_chain *ch)
4086 {
4087         size_t sz;
4088
4089         /*
4090          * Register all algorithms presented here.
4091          */
4092         sz = sizeof(struct table_algo);
4093         ipfw_add_table_algo(ch, &addr_radix, sz, &addr_radix.idx);
4094         ipfw_add_table_algo(ch, &addr_hash, sz, &addr_hash.idx);
4095         ipfw_add_table_algo(ch, &iface_idx, sz, &iface_idx.idx);
4096         ipfw_add_table_algo(ch, &number_array, sz, &number_array.idx);
4097         ipfw_add_table_algo(ch, &flow_hash, sz, &flow_hash.idx);
4098         ipfw_add_table_algo(ch, &addr_kfib, sz, &addr_kfib.idx);
4099 }
4100
4101 void
4102 ipfw_table_algo_destroy(struct ip_fw_chain *ch)
4103 {
4104
4105         ipfw_del_table_algo(ch, addr_radix.idx);
4106         ipfw_del_table_algo(ch, addr_hash.idx);
4107         ipfw_del_table_algo(ch, iface_idx.idx);
4108         ipfw_del_table_algo(ch, number_array.idx);
4109         ipfw_del_table_algo(ch, flow_hash.idx);
4110         ipfw_del_table_algo(ch, addr_kfib.idx);
4111 }
4112
4113