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