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