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