sys/netpfil/ipfw/ip_fw_table_algo.c

   1 /*-
   2  * Copyright (c) 2004 Ruslan Ermilov and Vsevolod Lobko.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  23  * SUCH DAMAGE.
  24  */
  25
  26 #include <sys/cdefs.h>
  27 __FBSDID("$FreeBSD: projects/ipfw/sys/netpfil/ipfw/ip_fw_table.c 267384 2014-06-12 09:59:11Z melifaro $");
  28
  29 /*
  30  * Lookup table algorithms.
  31  *
  32  */
  33
  34 #include "opt_ipfw.h"
  35 #include "opt_inet.h"
  36 #ifndef INET
  37 #error IPFIREWALL requires INET.
  38 #endif /* INET */
  39 #include "opt_inet6.h"
  40
  41 #include <sys/param.h>
  42 #include <sys/systm.h>
  43 #include <sys/malloc.h>
  44 #include <sys/kernel.h>
  45 #include <sys/lock.h>
  46 #include <sys/rwlock.h>
  47 #include <sys/socket.h>
  48 #include <sys/queue.h>
  49 #include <net/if.h>     /* ip_fw.h requires IFNAMSIZ */
  50 #include <net/radix.h>
  51 #include <net/route.h>
  52 #include <net/vnet.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 static MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
  62
  63 static int badd(const void *key, void *item, void *base, size_t nmemb,
  64     size_t size, int (*compar) (const void *, const void *));
  65 static int bdel(const void *key, void *base, size_t nmemb, size_t size,
  66     int (*compar) (const void *, const void *));
  67
  68
  69 /*
  70  * CIDR implementation using radix
  71  *
  72  */
  73
  74 /*
  75  * The radix code expects addr and mask to be array of bytes,
  76  * with the first byte being the length of the array. rn_inithead
  77  * is called with the offset in bits of the lookup key within the
  78  * array. If we use a sockaddr_in as the underlying type,
  79  * sin_len is conveniently located at offset 0, sin_addr is at
  80  * offset 4 and normally aligned.
  81  * But for portability, let's avoid assumption and make the code explicit
  82  */
  83 #define KEY_LEN(v)      *((uint8_t *)&(v))
  84 /*
  85  * Do not require radix to compare more than actual IPv4/IPv6 address
  86  */
  87 #define KEY_LEN_INET    (offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))
  88 #define KEY_LEN_INET6   (offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr))
  89
  90 #define OFF_LEN_INET    (8 * offsetof(struct sockaddr_in, sin_addr))
  91 #define OFF_LEN_INET6   (8 * offsetof(struct sa_in6, sin6_addr))
  92
  93 struct radix_cidr_entry {
  94         struct radix_node       rn[2];
  95         struct sockaddr_in      addr;
  96         uint32_t                value;
  97         uint8_t                 masklen;
  98 };
  99
 100 struct sa_in6 {
 101         uint8_t                 sin6_len;
 102         uint8_t                 sin6_family;
 103         uint8_t                 pad[2];
 104         struct in6_addr         sin6_addr;
 105 };
 106
 107 struct radix_cidr_xentry {
 108         struct radix_node       rn[2];
 109         struct sa_in6           addr6;
 110         uint32_t                value;
 111         uint8_t                 masklen;
 112 };
 113
 114 static int
 115 ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
 116     uint32_t *val)
 117 {
 118         struct radix_node_head *rnh;
 119
 120         if (keylen == sizeof(in_addr_t)) {
 121                 struct radix_cidr_entry *ent;
 122                 struct sockaddr_in sa;
 123                 KEY_LEN(sa) = KEY_LEN_INET;
 124                 sa.sin_addr.s_addr = *((in_addr_t *)key);
 125                 rnh = (struct radix_node_head *)ti->state;
 126                 ent = (struct radix_cidr_entry *)(rnh->rnh_matchaddr(&sa, rnh));
 127                 if (ent != NULL) {
 128                         *val = ent->value;
 129                         return (1);
 130                 }
 131         } else {
 132                 struct radix_cidr_xentry *xent;
 133                 struct sa_in6 sa6;
 134                 KEY_LEN(sa6) = KEY_LEN_INET6;
 135                 memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
 136                 rnh = (struct radix_node_head *)ti->xstate;
 137                 xent = (struct radix_cidr_xentry *)(rnh->rnh_matchaddr(&sa6, rnh));
 138                 if (xent != NULL) {
 139                         *val = xent->value;
 140                         return (1);
 141                 }
 142         }
 143
 144         return (0);
 145 }
 146
 147 /*
 148  * New table
 149  */
 150 static int
 151 ta_init_radix(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
 152     char *data, uint8_t tflags)
 153 {
 154
 155         if (!rn_inithead(&ti->state, OFF_LEN_INET))
 156                 return (ENOMEM);
 157         if (!rn_inithead(&ti->xstate, OFF_LEN_INET6)) {
 158                 rn_detachhead(&ti->state);
 159                 return (ENOMEM);
 160         }
 161
 162         *ta_state = NULL;
 163         ti->lookup = ta_lookup_radix;
 164
 165         return (0);
 166 }
 167
 168 static int
 169 flush_table_entry(struct radix_node *rn, void *arg)
 170 {
 171         struct radix_node_head * const rnh = arg;
 172         struct radix_cidr_entry *ent;
 173
 174         ent = (struct radix_cidr_entry *)
 175             rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);
 176         if (ent != NULL)
 177                 free(ent, M_IPFW_TBL);
 178         return (0);
 179 }
 180
 181 static void
 182 ta_destroy_radix(void *ta_state, struct table_info *ti)
 183 {
 184         struct radix_node_head *rnh;
 185
 186         rnh = (struct radix_node_head *)(ti->state);
 187         rnh->rnh_walktree(rnh, flush_table_entry, rnh);
 188         rn_detachhead(&ti->state);
 189
 190         rnh = (struct radix_node_head *)(ti->xstate);
 191         rnh->rnh_walktree(rnh, flush_table_entry, rnh);
 192         rn_detachhead(&ti->xstate);
 193 }
 194
 195 static int
 196 ta_dump_radix_tentry(void *ta_state, struct table_info *ti, void *e,
 197     ipfw_obj_tentry *tent)
 198 {
 199         struct radix_cidr_entry *n;
 200         struct radix_cidr_xentry *xn;
 201
 202         n = (struct radix_cidr_entry *)e;
 203
 204         /* Guess IPv4/IPv6 radix by sockaddr family */
 205         if (n->addr.sin_family == AF_INET) {
 206                 tent->k.addr.s_addr = n->addr.sin_addr.s_addr;
 207                 tent->masklen = n->masklen;
 208                 tent->subtype = AF_INET;
 209                 tent->value = n->value;
 210 #ifdef INET6
 211         } else {
 212                 xn = (struct radix_cidr_xentry *)e;
 213                 memcpy(&tent->k, &xn->addr6.sin6_addr, sizeof(struct in6_addr));
 214                 tent->masklen = xn->masklen;
 215                 tent->subtype = AF_INET6;
 216                 tent->value = xn->value;
 217 #endif
 218         }
 219
 220         return (0);
 221 }
 222
 223 static int
 224 ta_find_radix_tentry(void *ta_state, struct table_info *ti,
 225     ipfw_obj_tentry *tent)
 226 {
 227         struct radix_node_head *rnh;
 228         void *e;
 229
 230         e = NULL;
 231         if (tent->subtype == AF_INET) {
 232                 struct sockaddr_in sa;
 233                 KEY_LEN(sa) = KEY_LEN_INET;
 234                 sa.sin_addr.s_addr = tent->k.addr.s_addr;
 235                 rnh = (struct radix_node_head *)ti->state;
 236                 e = rnh->rnh_matchaddr(&sa, rnh);
 237         } else {
 238                 struct sa_in6 sa6;
 239                 KEY_LEN(sa6) = KEY_LEN_INET6;
 240                 memcpy(&sa6.sin6_addr, &tent->k.addr6, sizeof(struct in6_addr));
 241                 rnh = (struct radix_node_head *)ti->xstate;
 242                 e = rnh->rnh_matchaddr(&sa6, rnh);
 243         }
 244
 245         if (e != NULL) {
 246                 ta_dump_radix_tentry(ta_state, ti, e, tent);
 247                 return (0);
 248         }
 249
 250         return (ENOENT);
 251 }
 252
 253 static void
 254 ta_foreach_radix(void *ta_state, struct table_info *ti, ta_foreach_f *f,
 255     void *arg)
 256 {
 257         struct radix_node_head *rnh;
 258
 259         rnh = (struct radix_node_head *)(ti->state);
 260         rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg);
 261
 262         rnh = (struct radix_node_head *)(ti->xstate);
 263         rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg);
 264 }
 265
 266
 267 struct ta_buf_cidr
 268 {
 269         void *ent_ptr;
 270         struct sockaddr *addr_ptr;
 271         struct sockaddr *mask_ptr;
 272         union {
 273                 struct {
 274                         struct sockaddr_in sa;
 275                         struct sockaddr_in ma;
 276                 } a4;
 277                 struct {
 278                         struct sa_in6 sa;
 279                         struct sa_in6 ma;
 280                 } a6;
 281         } addr;
 282 };
 283
 284 #ifdef INET6
 285 static inline void
 286 ipv6_writemask(struct in6_addr *addr6, uint8_t mask)
 287 {
 288         uint32_t *cp;
 289
 290         for (cp = (uint32_t *)addr6; mask >= 32; mask -= 32)
 291                 *cp++ = 0xFFFFFFFF;
 292         *cp = htonl(mask ? ~((1 << (32 - mask)) - 1) : 0);
 293 }
 294 #endif
 295
 296 static void
 297 tei_to_sockaddr_ent(struct tentry_info *tei, struct sockaddr *sa,
 298     struct sockaddr *ma, int *set_mask)
 299 {
 300         int mlen;
 301         struct sockaddr_in *addr, *mask;
 302         struct sockaddr_in6 *addr6, *mask6;
 303         in_addr_t a4;
 304
 305         mlen = tei->masklen;
 306
 307         if (tei->subtype == AF_INET) {
 308 #ifdef INET
 309                 addr = (struct sockaddr_in *)sa;
 310                 mask = (struct sockaddr_in *)ma;
 311                 /* Set 'total' structure length */
 312                 KEY_LEN(*addr) = KEY_LEN_INET;
 313                 KEY_LEN(*mask) = KEY_LEN_INET;
 314                 addr->sin_family = AF_INET;
 315                 mask->sin_addr.s_addr =
 316                     htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
 317                 a4 = *((in_addr_t *)tei->paddr);
 318                 addr->sin_addr.s_addr = a4 & mask->sin_addr.s_addr;
 319                 if (mlen != 32)
 320                         *set_mask = 1;
 321                 else
 322                         *set_mask = 0;
 323 #endif
 324 #ifdef INET6
 325         } else if (tei->subtype == AF_INET6) {
 326                 /* IPv6 case */
 327                 addr6 = (struct sockaddr_in6 *)sa;
 328                 mask6 = (struct sockaddr_in6 *)ma;
 329                 /* Set 'total' structure length */
 330                 KEY_LEN(*addr6) = KEY_LEN_INET6;
 331                 KEY_LEN(*mask6) = KEY_LEN_INET6;
 332                 addr6->sin6_family = AF_INET6;
 333                 ipv6_writemask(&mask6->sin6_addr, mlen);
 334                 memcpy(&addr6->sin6_addr, tei->paddr, sizeof(struct in6_addr));
 335                 APPLY_MASK(&addr6->sin6_addr, &mask6->sin6_addr);
 336                 if (mlen != 128)
 337                         *set_mask = 1;
 338                 else
 339                         *set_mask = 0;
 340         }
 341 #endif
 342 }
 343
 344 static int
 345 ta_prepare_add_cidr(struct ip_fw_chain *ch, struct tentry_info *tei,
 346     void *ta_buf)
 347 {
 348         struct ta_buf_cidr *tb;
 349         struct radix_cidr_entry *ent;
 350         struct radix_cidr_xentry *xent;
 351         struct sockaddr *addr, *mask;
 352         int mlen, set_mask;
 353
 354         tb = (struct ta_buf_cidr *)ta_buf;
 355
 356         mlen = tei->masklen;
 357         set_mask = 0;
 358
 359         if (tei->subtype == AF_INET) {
 360 #ifdef INET
 361                 if (mlen > 32)
 362                         return (EINVAL);
 363                 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
 364                 ent->value = tei->value;
 365                 ent->masklen = mlen;
 366
 367                 addr = (struct sockaddr *)&ent->addr;
 368                 mask = (struct sockaddr *)&tb->addr.a4.ma;
 369                 tb->ent_ptr = ent;
 370 #endif
 371 #ifdef INET6
 372         } else if (tei->subtype == AF_INET6) {
 373                 /* IPv6 case */
 374                 if (mlen > 128)
 375                         return (EINVAL);
 376                 xent = malloc(sizeof(*xent), M_IPFW_TBL, M_WAITOK | M_ZERO);
 377                 xent->value = tei->value;
 378                 xent->masklen = mlen;
 379
 380                 addr = (struct sockaddr *)&xent->addr6;
 381                 mask = (struct sockaddr *)&tb->addr.a6.ma;
 382                 tb->ent_ptr = xent;
 383 #endif
 384         } else {
 385                 /* Unknown CIDR type */
 386                 return (EINVAL);
 387         }
 388
 389         tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
 390         /* Set pointers */
 391         tb->addr_ptr = addr;
 392         if (set_mask != 0)
 393                 tb->mask_ptr = mask;
 394
 395         return (0);
 396 }
 397
 398 static int
 399 ta_add_cidr(void *ta_state, struct table_info *ti, struct tentry_info *tei,
 400     void *ta_buf, uint32_t *pnum)
 401 {
 402         struct radix_node_head *rnh;
 403         struct radix_node *rn;
 404         struct ta_buf_cidr *tb;
 405         uint32_t *old_value, value;
 406
 407         tb = (struct ta_buf_cidr *)ta_buf;
 408
 409         if (tei->subtype == AF_INET)
 410                 rnh = ti->state;
 411         else
 412                 rnh = ti->xstate;
 413
 414         /* Search for an entry first */
 415         rn = rnh->rnh_lookup(tb->addr_ptr, tb->mask_ptr, rnh);
 416         if (rn != NULL) {
 417                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
 418                         return (EEXIST);
 419                 /* Record already exists. Update value if we're asked to */
 420                 if (tei->subtype == AF_INET)
 421                         old_value = &((struct radix_cidr_entry *)rn)->value;
 422                 else
 423                         old_value = &((struct radix_cidr_xentry *)rn)->value;
 424
 425                 value = *old_value;
 426                 *old_value = tei->value;
 427                 tei->value = value;
 428
 429                 /* Indicate that update has happened instead of addition */
 430                 tei->flags |= TEI_FLAGS_UPDATED;
 431                 *pnum = 0;
 432
 433                 return (0);
 434         }
 435
 436         if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
 437                 return (EFBIG);
 438
 439         rn = rnh->rnh_addaddr(tb->addr_ptr, tb->mask_ptr, rnh, tb->ent_ptr);
 440         if (rn == NULL) {
 441                 /* Unknown error */
 442                 return (EINVAL);
 443         }
 444
 445         tb->ent_ptr = NULL;
 446         *pnum = 1;
 447
 448         return (0);
 449 }
 450
 451 static int
 452 ta_prepare_del_cidr(struct ip_fw_chain *ch, struct tentry_info *tei,
 453     void *ta_buf)
 454 {
 455         struct ta_buf_cidr *tb;
 456         struct sockaddr *addr, *mask;
 457         int mlen, set_mask;
 458
 459         tb = (struct ta_buf_cidr *)ta_buf;
 460
 461         mlen = tei->masklen;
 462         set_mask = 0;
 463
 464         if (tei->subtype == AF_INET) {
 465                 if (mlen > 32)
 466                         return (EINVAL);
 467
 468                 addr = (struct sockaddr *)&tb->addr.a4.sa;
 469                 mask = (struct sockaddr *)&tb->addr.a4.ma;
 470 #ifdef INET6
 471         } else if (tei->subtype == AF_INET6) {
 472                 if (mlen > 128)
 473                         return (EINVAL);
 474
 475                 addr = (struct sockaddr *)&tb->addr.a6.sa;
 476                 mask = (struct sockaddr *)&tb->addr.a6.ma;
 477 #endif
 478         } else
 479                 return (EINVAL);
 480
 481         tei_to_sockaddr_ent(tei, addr, mask, &set_mask);
 482         tb->addr_ptr = addr;
 483         if (set_mask != 0)
 484                 tb->mask_ptr = mask;
 485
 486         return (0);
 487 }
 488
 489 static int
 490 ta_del_cidr(void *ta_state, struct table_info *ti, struct tentry_info *tei,
 491     void *ta_buf, uint32_t *pnum)
 492 {
 493         struct radix_node_head *rnh;
 494         struct radix_node *rn;
 495         struct ta_buf_cidr *tb;
 496
 497         tb = (struct ta_buf_cidr *)ta_buf;
 498
 499         if (tei->subtype == AF_INET)
 500                 rnh = ti->state;
 501         else
 502                 rnh = ti->xstate;
 503
 504         rn = rnh->rnh_deladdr(tb->addr_ptr, tb->mask_ptr, rnh);
 505
 506         /* Save entry value to @tei */
 507         if (tei->subtype == AF_INET)
 508                 tei->value = ((struct radix_cidr_entry *)rn)->value;
 509         else
 510                 tei->value = ((struct radix_cidr_xentry *)rn)->value;
 511
 512         tb->ent_ptr = rn;
 513
 514         if (rn == NULL)
 515                 return (ENOENT);
 516
 517         *pnum = 1;
 518
 519         return (0);
 520 }
 521
 522 static void
 523 ta_flush_cidr_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
 524     void *ta_buf)
 525 {
 526         struct ta_buf_cidr *tb;
 527
 528         tb = (struct ta_buf_cidr *)ta_buf;
 529
 530         if (tb->ent_ptr != NULL)
 531                 free(tb->ent_ptr, M_IPFW_TBL);
 532 }
 533
 534 static int
 535 ta_has_space_radix(void *ta_state, struct table_info *ti, uint32_t count,
 536     uint64_t *pflags)
 537 {
 538
 539         /*
 540          * radix does not not require additional memory allocations
 541          * other than nodes itself. Adding new masks to the tree do
 542          * but we don't have any API to call (and we don't known which
 543          * sizes do we need).
 544          */
 545         return (1);
 546 }
 547
 548 struct table_algo cidr_radix = {
 549         .name           = "cidr:radix",
 550         .type           = IPFW_TABLE_CIDR,
 551         .flags          = TA_FLAG_DEFAULT,
 552         .ta_buf_size    = sizeof(struct ta_buf_cidr),
 553         .init           = ta_init_radix,
 554         .destroy        = ta_destroy_radix,
 555         .prepare_add    = ta_prepare_add_cidr,
 556         .prepare_del    = ta_prepare_del_cidr,
 557         .add            = ta_add_cidr,
 558         .del            = ta_del_cidr,
 559         .flush_entry    = ta_flush_cidr_entry,
 560         .foreach        = ta_foreach_radix,
 561         .dump_tentry    = ta_dump_radix_tentry,
 562         .find_tentry    = ta_find_radix_tentry,
 563         .has_space      = ta_has_space_radix,
 564 };
 565
 566
 567 /*
 568  * cidr:hash cmds
 569  *
 570  *
 571  * ti->data:
 572  * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
 573  * [        8][        8[          8][         8]
 574  *
 575  * inv.mask4: 32 - mask
 576  * inv.mask6:
 577  * 1) _slow lookup: mask
 578  * 2) _aligned: (128 - mask) / 8
 579  * 3) _64: 8
 580  *
 581  *
 582  * pflags:
 583  * [v4=1/v6=0][hsize]
 584  * [       32][   32]
 585  */
 586
 587 struct chashentry;
 588
 589 SLIST_HEAD(chashbhead, chashentry);
 590
 591 struct chash_cfg {
 592         struct chashbhead *head4;
 593         struct chashbhead *head6;
 594         size_t  size4;
 595         size_t  size6;
 596         size_t  items4;
 597         size_t  items6;
 598         uint8_t mask4;
 599         uint8_t mask6;
 600 };
 601
 602 struct chashentry {
 603         SLIST_ENTRY(chashentry) next;
 604         uint32_t        value;
 605         uint32_t        type;
 606         union {
 607                 uint32_t        a4;     /* Host format */
 608                 struct in6_addr a6;     /* Network format */
 609         } a;
 610 };
 611
 612 static __inline uint32_t
 613 hash_ip(uint32_t addr, int hsize)
 614 {
 615
 616         return (addr % (hsize - 1));
 617 }
 618
 619 static __inline uint32_t
 620 hash_ip6(struct in6_addr *addr6, int hsize)
 621 {
 622         uint32_t i;
 623
 624         i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1] ^
 625             addr6->s6_addr32[2] ^ addr6->s6_addr32[3];
 626
 627         return (i % (hsize - 1));
 628 }
 629
 630
 631 static __inline uint16_t
 632 hash_ip64(struct in6_addr *addr6, int hsize)
 633 {
 634         uint32_t i;
 635
 636         i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1];
 637
 638         return (i % (hsize - 1));
 639 }
 640
 641
 642 static __inline uint32_t
 643 hash_ip6_slow(struct in6_addr *addr6, void *key, int mask, int hsize)
 644 {
 645         struct in6_addr mask6;
 646
 647         ipv6_writemask(&mask6, mask);
 648         memcpy(addr6, key, sizeof(struct in6_addr));
 649         APPLY_MASK(addr6, &mask6);
 650         return (hash_ip6(addr6, hsize));
 651 }
 652
 653 static __inline uint32_t
 654 hash_ip6_al(struct in6_addr *addr6, void *key, int mask, int hsize)
 655 {
 656         uint64_t *paddr;
 657
 658         paddr = (uint64_t *)addr6;
 659         *paddr = 0;
 660         *(paddr + 1) = 0;
 661         memcpy(addr6, key, mask);
 662         return (hash_ip6(addr6, hsize));
 663 }
 664
 665 static int
 666 ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
 667     uint32_t *val)
 668 {
 669         struct chashbhead *head;
 670         struct chashentry *ent;
 671         uint16_t hash, hsize;
 672         uint8_t imask;
 673
 674         if (keylen == sizeof(in_addr_t)) {
 675                 head = (struct chashbhead *)ti->state;
 676                 imask = ti->data >> 24;
 677                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 678                 uint32_t a;
 679                 a = ntohl(*((in_addr_t *)key));
 680                 a = a >> imask;
 681                 hash = hash_ip(a, hsize);
 682                 SLIST_FOREACH(ent, &head[hash], next) {
 683                         if (ent->a.a4 == a) {
 684                                 *val = ent->value;
 685                                 return (1);
 686                         }
 687                 }
 688         } else {
 689                 /* IPv6: worst scenario: non-round mask */
 690                 struct in6_addr addr6;
 691                 head = (struct chashbhead *)ti->xstate;
 692                 imask = (ti->data & 0xFF0000) >> 16;
 693                 hsize = 1 << (ti->data & 0xFF);
 694                 hash = hash_ip6_slow(&addr6, key, imask, hsize);
 695                 SLIST_FOREACH(ent, &head[hash], next) {
 696                         if (memcmp(&ent->a.a6, &addr6, 16) == 0) {
 697                                 *val = ent->value;
 698                                 return (1);
 699                         }
 700                 }
 701         }
 702
 703         return (0);
 704 }
 705
 706 static int
 707 ta_lookup_chash_aligned(struct table_info *ti, void *key, uint32_t keylen,
 708     uint32_t *val)
 709 {
 710         struct chashbhead *head;
 711         struct chashentry *ent;
 712         uint16_t hash, hsize;
 713         uint8_t imask;
 714
 715         if (keylen == sizeof(in_addr_t)) {
 716                 head = (struct chashbhead *)ti->state;
 717                 imask = ti->data >> 24;
 718                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 719                 uint32_t a;
 720                 a = ntohl(*((in_addr_t *)key));
 721                 a = a >> imask;
 722                 hash = hash_ip(a, hsize);
 723                 SLIST_FOREACH(ent, &head[hash], next) {
 724                         if (ent->a.a4 == a) {
 725                                 *val = ent->value;
 726                                 return (1);
 727                         }
 728                 }
 729         } else {
 730                 /* IPv6: aligned to 8bit mask */
 731                 struct in6_addr addr6;
 732                 uint64_t *paddr, *ptmp;
 733                 head = (struct chashbhead *)ti->xstate;
 734                 imask = (ti->data & 0xFF0000) >> 16;
 735                 hsize = 1 << (ti->data & 0xFF);
 736
 737                 hash = hash_ip6_al(&addr6, key, imask, hsize);
 738                 paddr = (uint64_t *)&addr6;
 739                 SLIST_FOREACH(ent, &head[hash], next) {
 740                         ptmp = (uint64_t *)&ent->a.a6;
 741                         if (paddr[0] == ptmp[0] && paddr[1] == ptmp[1]) {
 742                                 *val = ent->value;
 743                                 return (1);
 744                         }
 745                 }
 746         }
 747
 748         return (0);
 749 }
 750
 751 static int
 752 ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
 753     uint32_t *val)
 754 {
 755         struct chashbhead *head;
 756         struct chashentry *ent;
 757         uint16_t hash, hsize;
 758         uint8_t imask;
 759
 760         if (keylen == sizeof(in_addr_t)) {
 761                 head = (struct chashbhead *)ti->state;
 762                 imask = ti->data >> 24;
 763                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 764                 uint32_t a;
 765                 a = ntohl(*((in_addr_t *)key));
 766                 a = a >> imask;
 767                 hash = hash_ip(a, hsize);
 768                 SLIST_FOREACH(ent, &head[hash], next) {
 769                         if (ent->a.a4 == a) {
 770                                 *val = ent->value;
 771                                 return (1);
 772                         }
 773                 }
 774         } else {
 775                 /* IPv6: /64 */
 776                 uint64_t a6, *paddr;
 777                 head = (struct chashbhead *)ti->xstate;
 778                 paddr = (uint64_t *)key;
 779                 hsize = 1 << (ti->data & 0xFF);
 780                 a6 = *paddr;
 781                 hash = hash_ip64((struct in6_addr *)key, hsize);
 782                 SLIST_FOREACH(ent, &head[hash], next) {
 783                         paddr = (uint64_t *)&ent->a.a6;
 784                         if (a6 == *paddr) {
 785                                 *val = ent->value;
 786                                 return (1);
 787                         }
 788                 }
 789         }
 790
 791         return (0);
 792 }
 793
 794 static int
 795 chash_parse_opts(struct chash_cfg *ccfg, char *data)
 796 {
 797         char *pdel, *pend, *s;
 798         int mask4, mask6;
 799
 800         mask4 = ccfg->mask4;
 801         mask6 = ccfg->mask6;
 802
 803         if (data == NULL)
 804                 return (0);
 805         if ((pdel = strchr(data, ' ')) == NULL)
 806                 return (0);
 807         while (*pdel == ' ')
 808                 pdel++;
 809         if (strncmp(pdel, "masks=", 6) != 0)
 810                 return (EINVAL);
 811         if ((s = strchr(pdel, ' ')) != NULL)
 812                 *s++ = '\0';
 813
 814         pdel += 6;
 815         /* Need /XX[,/YY] */
 816         if (*pdel++ != '/')
 817                 return (EINVAL);
 818         mask4 = strtol(pdel, &pend, 10);
 819         if (*pend == ',') {
 820                 /* ,/YY */
 821                 pdel = pend + 1;
 822                 if (*pdel++ != '/')
 823                         return (EINVAL);
 824                 mask6 = strtol(pdel, &pend, 10);
 825                 if (*pend != '\0')
 826                         return (EINVAL);
 827         } else if (*pend != '\0')
 828                 return (EINVAL);
 829
 830         if (mask4 < 0 || mask4 > 32 || mask6 < 0 || mask6 > 128)
 831                 return (EINVAL);
 832
 833         ccfg->mask4 = mask4;
 834         ccfg->mask6 = mask6;
 835
 836         return (0);
 837 }
 838
 839 static void
 840 ta_print_chash_config(void *ta_state, struct table_info *ti, char *buf,
 841     size_t bufsize)
 842 {
 843         struct chash_cfg *ccfg;
 844
 845         ccfg = (struct chash_cfg *)ta_state;
 846
 847         if (ccfg->mask4 != 32 || ccfg->mask6 != 128)
 848                 snprintf(buf, bufsize, "%s masks=/%d,/%d", "cidr:hash",
 849                     ccfg->mask4, ccfg->mask6);
 850         else
 851                 snprintf(buf, bufsize, "%s", "cidr:hash");
 852 }
 853
 854 static int
 855 log2(uint32_t v)
 856 {
 857         uint32_t r;
 858
 859         r = 0;
 860         while (v >>= 1)
 861                 r++;
 862
 863         return (r);
 864 }
 865
 866 /*
 867  * New table.
 868  * We assume 'data' to be either NULL or the following format:
 869  * 'cidr:hash [masks=/32[,/128]]'
 870  */
 871 static int
 872 ta_init_chash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
 873     char *data, uint8_t tflags)
 874 {
 875         int error, i;
 876         uint32_t hsize;
 877         struct chash_cfg *ccfg;
 878
 879         ccfg = malloc(sizeof(struct chash_cfg), M_IPFW, M_WAITOK | M_ZERO);
 880
 881         ccfg->mask4 = 32;
 882         ccfg->mask6 = 128;
 883
 884         if ((error = chash_parse_opts(ccfg, data)) != 0) {
 885                 free(ccfg, M_IPFW);
 886                 return (error);
 887         }
 888
 889         ccfg->size4 = 128;
 890         ccfg->size6 = 128;
 891
 892         ccfg->head4 = malloc(sizeof(struct chashbhead) * ccfg->size4, M_IPFW,
 893             M_WAITOK | M_ZERO);
 894         ccfg->head6 = malloc(sizeof(struct chashbhead) * ccfg->size6, M_IPFW,
 895             M_WAITOK | M_ZERO);
 896         for (i = 0; i < ccfg->size4; i++)
 897                 SLIST_INIT(&ccfg->head4[i]);
 898         for (i = 0; i < ccfg->size6; i++)
 899                 SLIST_INIT(&ccfg->head6[i]);
 900
 901
 902         *ta_state = ccfg;
 903         ti->state = ccfg->head4;
 904         ti->xstate = ccfg->head6;
 905
 906         /* Store data depending on v6 mask length */
 907         hsize = log2(ccfg->size4) << 8 | log2(ccfg->size6);
 908         if (ccfg->mask6 == 64) {
 909                 ti->data = (32 - ccfg->mask4) << 24 | (128 - ccfg->mask6) << 16|
 910                     hsize;
 911                 ti->lookup = ta_lookup_chash_64;
 912         } else if ((ccfg->mask6  % 8) == 0) {
 913                 ti->data = (32 - ccfg->mask4) << 24 |
 914                     ccfg->mask6 << 13 | hsize;
 915                 ti->lookup = ta_lookup_chash_aligned;
 916         } else {
 917                 /* don't do that! */
 918                 ti->data = (32 - ccfg->mask4) << 24 |
 919                     ccfg->mask6 << 16 | hsize;
 920                 ti->lookup = ta_lookup_chash_slow;
 921         }
 922
 923         return (0);
 924 }
 925
 926 static void
 927 ta_destroy_chash(void *ta_state, struct table_info *ti)
 928 {
 929         struct chash_cfg *ccfg;
 930         struct chashentry *ent, *ent_next;
 931         int i;
 932
 933         ccfg = (struct chash_cfg *)ta_state;
 934
 935         for (i = 0; i < ccfg->size4; i++)
 936                 SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
 937                         free(ent, M_IPFW_TBL);
 938
 939         for (i = 0; i < ccfg->size6; i++)
 940                 SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
 941                         free(ent, M_IPFW_TBL);
 942
 943         free(ccfg->head4, M_IPFW);
 944         free(ccfg->head6, M_IPFW);
 945
 946         free(ccfg, M_IPFW);
 947 }
 948
 949 static int
 950 ta_dump_chash_tentry(void *ta_state, struct table_info *ti, void *e,
 951     ipfw_obj_tentry *tent)
 952 {
 953         struct chash_cfg *ccfg;
 954         struct chashentry *ent;
 955
 956         ccfg = (struct chash_cfg *)ta_state;
 957         ent = (struct chashentry *)e;
 958
 959         if (ent->type == AF_INET) {
 960                 tent->k.addr.s_addr = htonl(ent->a.a4 << (32 - ccfg->mask4));
 961                 tent->masklen = ccfg->mask4;
 962                 tent->subtype = AF_INET;
 963                 tent->value = ent->value;
 964 #ifdef INET6
 965         } else {
 966                 memcpy(&tent->k, &ent->a.a6, sizeof(struct in6_addr));
 967                 tent->masklen = ccfg->mask6;
 968                 tent->subtype = AF_INET6;
 969                 tent->value = ent->value;
 970 #endif
 971         }
 972
 973         return (0);
 974 }
 975
 976 static uint32_t
 977 hash_ent(struct chashentry *ent, int af, int mlen, uint32_t size)
 978 {
 979         uint32_t hash;
 980
 981         if (af == AF_INET) {
 982                 hash = hash_ip(ent->a.a4, size);
 983         } else {
 984                 if (mlen == 64)
 985                         hash = hash_ip64(&ent->a.a6, size);
 986                 else
 987                         hash = hash_ip6(&ent->a.a6, size);
 988         }
 989
 990         return (hash);
 991 }
 992
 993 static int
 994 tei_to_chash_ent(struct tentry_info *tei, struct chashentry *ent)
 995 {
 996         struct in6_addr mask6;
 997         int mlen;
 998
 999
1000         mlen = tei->masklen;
1001
1002         if (tei->subtype == AF_INET) {
1003 #ifdef INET
1004                 if (mlen > 32)
1005                         return (EINVAL);
1006                 ent->type = AF_INET;
1007
1008                 /* Calculate masked address */
1009                 ent->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1010 #endif
1011 #ifdef INET6
1012         } else if (tei->subtype == AF_INET6) {
1013                 /* IPv6 case */
1014                 if (mlen > 128)
1015                         return (EINVAL);
1016                 ent->type = AF_INET6;
1017
1018                 ipv6_writemask(&mask6, mlen);
1019                 memcpy(&ent->a.a6, tei->paddr, sizeof(struct in6_addr));
1020                 APPLY_MASK(&ent->a.a6, &mask6);
1021 #endif
1022         } else {
1023                 /* Unknown CIDR type */
1024                 return (EINVAL);
1025         }
1026         ent->value = tei->value;
1027
1028         return (0);
1029 }
1030
1031
1032 static int
1033 ta_find_chash_tentry(void *ta_state, struct table_info *ti,
1034     ipfw_obj_tentry *tent)
1035 {
1036         struct chash_cfg *ccfg;
1037         struct chashbhead *head;
1038         struct chashentry ent, *tmp;
1039         struct tentry_info tei;
1040         int error;
1041         uint32_t hash;
1042
1043         ccfg = (struct chash_cfg *)ta_state;
1044
1045         memset(&ent, 0, sizeof(ent));
1046         memset(&tei, 0, sizeof(tei));
1047
1048         if (tent->subtype == AF_INET) {
1049                 tei.paddr = &tent->k.addr;
1050                 tei.masklen = ccfg->mask4;
1051                 tei.subtype = AF_INET;
1052
1053                 if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
1054                         return (error);
1055
1056                 head = ccfg->head4;
1057                 hash = hash_ent(&ent, AF_INET, ccfg->mask4, ccfg->size4);
1058                 /* Check for existence */
1059                 SLIST_FOREACH(tmp, &head[hash], next) {
1060                         if (tmp->a.a4 != ent.a.a4)
1061                                 continue;
1062
1063                         ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1064                         return (0);
1065                 }
1066         } else {
1067                 tei.paddr = &tent->k.addr6;
1068                 tei.masklen = ccfg->mask6;
1069                 tei.subtype = AF_INET6;
1070
1071                 if ((error = tei_to_chash_ent(&tei, &ent)) != 0)
1072                         return (error);
1073
1074                 head = ccfg->head6;
1075                 hash = hash_ent(&ent, AF_INET6, ccfg->mask6, ccfg->size6);
1076                 /* Check for existence */
1077                 SLIST_FOREACH(tmp, &head[hash], next) {
1078                         if (memcmp(&tmp->a.a6, &ent.a.a6, 16) != 0)
1079                                 continue;
1080                         ta_dump_chash_tentry(ta_state, ti, tmp, tent);
1081                         return (0);
1082                 }
1083         }
1084
1085         return (ENOENT);
1086 }
1087
1088 static void
1089 ta_foreach_chash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
1090     void *arg)
1091 {
1092         struct chash_cfg *ccfg;
1093         struct chashentry *ent, *ent_next;
1094         int i;
1095
1096         ccfg = (struct chash_cfg *)ta_state;
1097
1098         for (i = 0; i < ccfg->size4; i++)
1099                 SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
1100                         f(ent, arg);
1101
1102         for (i = 0; i < ccfg->size6; i++)
1103                 SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
1104                         f(ent, arg);
1105 }
1106
1107
1108 struct ta_buf_chash
1109 {
1110         void *ent_ptr;
1111         struct chashentry ent;
1112 };
1113
1114 static int
1115 ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1116     void *ta_buf)
1117 {
1118         struct ta_buf_chash *tb;
1119         struct chashentry *ent;
1120         int error;
1121
1122         tb = (struct ta_buf_chash *)ta_buf;
1123
1124         ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1125
1126         error = tei_to_chash_ent(tei, ent);
1127         if (error != 0) {
1128                 free(ent, M_IPFW_TBL);
1129                 return (error);
1130         }
1131         tb->ent_ptr = ent;
1132
1133         return (0);
1134 }
1135
1136 static int
1137 ta_add_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1138     void *ta_buf, uint32_t *pnum)
1139 {
1140         struct chash_cfg *ccfg;
1141         struct chashbhead *head;
1142         struct chashentry *ent, *tmp;
1143         struct ta_buf_chash *tb;
1144         int exists;
1145         uint32_t hash, value;
1146
1147         ccfg = (struct chash_cfg *)ta_state;
1148         tb = (struct ta_buf_chash *)ta_buf;
1149         ent = (struct chashentry *)tb->ent_ptr;
1150         hash = 0;
1151         exists = 0;
1152
1153         if (tei->subtype == AF_INET) {
1154                 if (tei->masklen != ccfg->mask4)
1155                         return (EINVAL);
1156                 head = ccfg->head4;
1157                 hash = hash_ent(ent, AF_INET, ccfg->mask4, ccfg->size4);
1158
1159                 /* Check for existence */
1160                 SLIST_FOREACH(tmp, &head[hash], next) {
1161                         if (tmp->a.a4 == ent->a.a4) {
1162                                 exists = 1;
1163                                 break;
1164                         }
1165                 }
1166         } else {
1167                 if (tei->masklen != ccfg->mask6)
1168                         return (EINVAL);
1169                 head = ccfg->head6;
1170                 hash = hash_ent(ent, AF_INET6, ccfg->mask6, ccfg->size6);
1171                 /* Check for existence */
1172                 SLIST_FOREACH(tmp, &head[hash], next) {
1173                         if (memcmp(&tmp->a.a6, &ent->a.a6, 16) == 0) {
1174                                 exists = 1;
1175                                 break;
1176                         }
1177                 }
1178         }
1179
1180         if (exists == 1) {
1181                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1182                         return (EEXIST);
1183                 /* Record already exists. Update value if we're asked to */
1184                 value = tmp->value;
1185                 tmp->value = tei->value;
1186                 tei->value = value;
1187                 /* Indicate that update has happened instead of addition */
1188                 tei->flags |= TEI_FLAGS_UPDATED;
1189                 *pnum = 0;
1190         } else {
1191                 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
1192                         return (EFBIG);
1193                 SLIST_INSERT_HEAD(&head[hash], ent, next);
1194                 tb->ent_ptr = NULL;
1195                 *pnum = 1;
1196
1197                 /* Update counters */
1198                 if (tei->subtype == AF_INET)
1199                         ccfg->items4++;
1200                 else
1201                         ccfg->items6++;
1202         }
1203
1204         return (0);
1205 }
1206
1207 static int
1208 ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1209     void *ta_buf)
1210 {
1211         struct ta_buf_chash *tb;
1212
1213         tb = (struct ta_buf_chash *)ta_buf;
1214
1215         return (tei_to_chash_ent(tei, &tb->ent));
1216 }
1217
1218 static int
1219 ta_del_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1220     void *ta_buf, uint32_t *pnum)
1221 {
1222         struct chash_cfg *ccfg;
1223         struct chashbhead *head;
1224         struct chashentry *ent, *tmp_next, *dent;
1225         struct ta_buf_chash *tb;
1226         uint32_t hash;
1227
1228         ccfg = (struct chash_cfg *)ta_state;
1229         tb = (struct ta_buf_chash *)ta_buf;
1230         dent = &tb->ent;
1231
1232         if (tei->subtype == AF_INET) {
1233                 if (tei->masklen != ccfg->mask4)
1234                         return (EINVAL);
1235                 head = ccfg->head4;
1236                 hash = hash_ent(dent, AF_INET, ccfg->mask4, ccfg->size4);
1237
1238                 SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1239                         if (ent->a.a4 != dent->a.a4)
1240                                 continue;
1241
1242                         SLIST_REMOVE(&head[hash], ent, chashentry, next);
1243                         ccfg->items4--;
1244                         tb->ent_ptr = ent;
1245                         tei->value = ent->value;
1246                         *pnum = 1;
1247                         return (0);
1248                 }
1249         } else {
1250                 if (tei->masklen != ccfg->mask6)
1251                         return (EINVAL);
1252                 head = ccfg->head6;
1253                 hash = hash_ent(dent, AF_INET6, ccfg->mask6, ccfg->size6);
1254                 SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1255                         if (memcmp(&ent->a.a6, &dent->a.a6, 16) != 0)
1256                                 continue;
1257
1258                         SLIST_REMOVE(&head[hash], ent, chashentry, next);
1259                         ccfg->items6--;
1260                         tb->ent_ptr = ent;
1261                         tei->value = ent->value;
1262                         *pnum = 1;
1263                         return (0);
1264                 }
1265         }
1266
1267         return (ENOENT);
1268 }
1269
1270 static void
1271 ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1272     void *ta_buf)
1273 {
1274         struct ta_buf_chash *tb;
1275
1276         tb = (struct ta_buf_chash *)ta_buf;
1277
1278         if (tb->ent_ptr != NULL)
1279                 free(tb->ent_ptr, M_IPFW_TBL);
1280 }
1281
1282 /*
1283  * Hash growing callbacks.
1284  */
1285
1286 struct mod_item {
1287         void    *main_ptr;
1288         size_t  size;
1289         void    *main_ptr6;
1290         size_t  size6;
1291 };
1292
1293 static int
1294 ta_has_space_chash(void *ta_state, struct table_info *ti, uint32_t count,
1295     uint64_t *pflags)
1296 {
1297         struct chash_cfg *cfg;
1298         uint64_t data;
1299
1300         /*
1301          * Since we don't know exact number of IPv4/IPv6 records in @count,
1302          * ignore non-zero @count value at all. Check current hash sizes
1303          * and return appropriate data.
1304          */
1305
1306         cfg = (struct chash_cfg *)ta_state;
1307
1308         data = 0;
1309         if (cfg->items4 > cfg->size4 && cfg->size4 < 65536)
1310                 data |= (cfg->size4 * 2) << 16;
1311         if (cfg->items6 > cfg->size6 && cfg->size6 < 65536)
1312                 data |= cfg->size6 * 2;
1313
1314         if (data != 0) {
1315                 *pflags = data;
1316                 return (0);
1317         }
1318
1319         return (1);
1320 }
1321
1322 /*
1323  * Allocate new, larger chash.
1324  */
1325 static int
1326 ta_prepare_mod_chash(void *ta_buf, uint64_t *pflags)
1327 {
1328         struct mod_item *mi;
1329         struct chashbhead *head;
1330         int i;
1331
1332         mi = (struct mod_item *)ta_buf;
1333
1334         memset(mi, 0, sizeof(struct mod_item));
1335         mi->size = (*pflags >> 16) & 0xFFFF;
1336         mi->size6 = *pflags & 0xFFFF;
1337         if (mi->size > 0) {
1338                 head = malloc(sizeof(struct chashbhead) * mi->size,
1339                     M_IPFW, M_WAITOK | M_ZERO);
1340                 for (i = 0; i < mi->size; i++)
1341                         SLIST_INIT(&head[i]);
1342                 mi->main_ptr = head;
1343         }
1344
1345         if (mi->size6 > 0) {
1346                 head = malloc(sizeof(struct chashbhead) * mi->size6,
1347                     M_IPFW, M_WAITOK | M_ZERO);
1348                 for (i = 0; i < mi->size6; i++)
1349                         SLIST_INIT(&head[i]);
1350                 mi->main_ptr6 = head;
1351         }
1352
1353         return (0);
1354 }
1355
1356 /*
1357  * Copy data from old runtime array to new one.
1358  */
1359 static int
1360 ta_fill_mod_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1361     uint64_t *pflags)
1362 {
1363
1364         /* In is not possible to do rehash if we're not holidng WLOCK. */
1365         return (0);
1366 }
1367
1368 /*
1369  * Switch old & new arrays.
1370  */
1371 static int
1372 ta_modify_chash(void *ta_state, struct table_info *ti, void *ta_buf,
1373     uint64_t pflags)
1374 {
1375         struct mod_item *mi;
1376         struct chash_cfg *cfg;
1377         struct chashbhead *old_head, *new_head;
1378         struct chashentry *ent, *ent_next;
1379         int af, i, mlen;
1380         uint32_t nhash;
1381         size_t old_size, new_size;
1382
1383         mi = (struct mod_item *)ta_buf;
1384         cfg = (struct chash_cfg *)ta_state;
1385
1386         /* Check which hash we need to grow and do we still need that */
1387         if (mi->size > 0 && cfg->size4 < mi->size) {
1388                 new_head = (struct chashbhead *)mi->main_ptr;
1389                 new_size = mi->size;
1390                 old_size = cfg->size4;
1391                 old_head = ti->state;
1392                 mlen = cfg->mask4;
1393                 af = AF_INET;
1394
1395                 for (i = 0; i < old_size; i++) {
1396                         SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
1397                                 nhash = hash_ent(ent, af, mlen, new_size);
1398                                 SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
1399                         }
1400                 }
1401
1402                 ti->state = new_head;
1403                 cfg->head4 = new_head;
1404                 cfg->size4 = mi->size;
1405                 mi->main_ptr = old_head;
1406         }
1407
1408         if (mi->size6 > 0 && cfg->size6 < mi->size6) {
1409                 new_head = (struct chashbhead *)mi->main_ptr6;
1410                 new_size = mi->size6;
1411                 old_size = cfg->size6;
1412                 old_head = ti->xstate;
1413                 mlen = cfg->mask6;
1414                 af = AF_INET6;
1415
1416                 for (i = 0; i < old_size; i++) {
1417                         SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
1418                                 nhash = hash_ent(ent, af, mlen, new_size);
1419                                 SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
1420                         }
1421                 }
1422
1423                 ti->xstate = new_head;
1424                 cfg->head6 = new_head;
1425                 cfg->size6 = mi->size6;
1426                 mi->main_ptr6 = old_head;
1427         }
1428
1429         /* Update lower 32 bits with new values */
1430         ti->data &= 0xFFFFFFFF00000000;
1431         ti->data |= log2(cfg->size4) << 8 | log2(cfg->size6);
1432
1433         return (0);
1434 }
1435
1436 /*
1437  * Free unneded array.
1438  */
1439 static void
1440 ta_flush_mod_chash(void *ta_buf)
1441 {
1442         struct mod_item *mi;
1443
1444         mi = (struct mod_item *)ta_buf;
1445         if (mi->main_ptr != NULL)
1446                 free(mi->main_ptr, M_IPFW);
1447         if (mi->main_ptr6 != NULL)
1448                 free(mi->main_ptr6, M_IPFW);
1449 }
1450
1451 struct table_algo cidr_hash = {
1452         .name           = "cidr:hash",
1453         .type           = IPFW_TABLE_CIDR,
1454         .ta_buf_size    = sizeof(struct ta_buf_chash),
1455         .init           = ta_init_chash,
1456         .destroy        = ta_destroy_chash,
1457         .prepare_add    = ta_prepare_add_chash,
1458         .prepare_del    = ta_prepare_del_chash,
1459         .add            = ta_add_chash,
1460         .del            = ta_del_chash,
1461         .flush_entry    = ta_flush_chash_entry,
1462         .foreach        = ta_foreach_chash,
1463         .dump_tentry    = ta_dump_chash_tentry,
1464         .find_tentry    = ta_find_chash_tentry,
1465         .print_config   = ta_print_chash_config,
1466         .has_space      = ta_has_space_chash,
1467         .prepare_mod    = ta_prepare_mod_chash,
1468         .fill_mod       = ta_fill_mod_chash,
1469         .modify         = ta_modify_chash,
1470         .flush_mod      = ta_flush_mod_chash,
1471 };
1472
1473
1474 /*
1475  * Iface table cmds.
1476  *
1477  * Implementation:
1478  *
1479  * Runtime part:
1480  * - sorted array of "struct ifidx" pointed by ti->state.
1481  *   Array is allocated with rounding up to IFIDX_CHUNK. Only existing
1482  *   interfaces are stored in array, however its allocated size is
1483  *   sufficient to hold all table records if needed.
1484  * - current array size is stored in ti->data
1485  *
1486  * Table data:
1487  * - "struct iftable_cfg" is allocated to store table state (ta_state).
1488  * - All table records are stored inside namedobj instance.
1489  *
1490  */
1491
1492 struct ifidx {
1493         uint16_t        kidx;
1494         uint16_t        spare;
1495         uint32_t        value;
1496 };
1497
1498 struct iftable_cfg;
1499
1500 struct ifentry {
1501         struct named_object     no;
1502         struct ipfw_ifc         ic;
1503         struct iftable_cfg      *icfg;
1504         uint32_t                value;
1505         int                     linked;
1506 };
1507
1508 struct iftable_cfg {
1509         struct namedobj_instance        *ii;
1510         struct ip_fw_chain      *ch;
1511         struct table_info       *ti;
1512         void    *main_ptr;
1513         size_t  size;   /* Number of items allocated in array */
1514         size_t  count;  /* Number of all items */
1515         size_t  used;   /* Number of items _active_ now */
1516 };
1517
1518 #define IFIDX_CHUNK     16
1519
1520 int compare_ifidx(const void *k, const void *v);
1521 static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
1522
1523 int
1524 compare_ifidx(const void *k, const void *v)
1525 {
1526         struct ifidx *ifidx;
1527         uint16_t key;
1528
1529         key = *((uint16_t *)k);
1530         ifidx = (struct ifidx *)v;
1531
1532         if (key < ifidx->kidx)
1533                 return (-1);
1534         else if (key > ifidx->kidx)
1535                 return (1);
1536
1537         return (0);
1538 }
1539
1540 /*
1541  * Adds item @item with key @key into ascending-sorted array @base.
1542  * Assumes @base has enough additional storage.
1543  *
1544  * Returns 1 on success, 0 on duplicate key.
1545  */
1546 static int
1547 badd(const void *key, void *item, void *base, size_t nmemb,
1548     size_t size, int (*compar) (const void *, const void *))
1549 {
1550         int min, max, mid, shift, res;
1551         caddr_t paddr;
1552
1553         if (nmemb == 0) {
1554                 memcpy(base, item, size);
1555                 return (1);
1556         }
1557
1558         /* Binary search */
1559         min = 0;
1560         max = nmemb - 1;
1561         mid = 0;
1562         while (min <= max) {
1563                 mid = (min + max) / 2;
1564                 res = compar(key, (const void *)((caddr_t)base + mid * size));
1565                 if (res == 0)
1566                         return (0);
1567
1568                 if (res > 0)
1569                          min = mid + 1;
1570                 else
1571                          max = mid - 1;
1572         }
1573
1574         /* Item not found. */
1575         res = compar(key, (const void *)((caddr_t)base + mid * size));
1576         if (res > 0)
1577                 shift = mid + 1;
1578         else
1579                 shift = mid;
1580
1581         paddr = (caddr_t)base + shift * size;
1582         if (nmemb > shift)
1583                 memmove(paddr + size, paddr, (nmemb - shift) * size);
1584
1585         memcpy(paddr, item, size);
1586
1587         return (1);
1588 }
1589
1590 /*
1591  * Deletes item with key @key from ascending-sorted array @base.
1592  *
1593  * Returns 1 on success, 0 for non-existent key.
1594  */
1595 static int
1596 bdel(const void *key, void *base, size_t nmemb, size_t size,
1597     int (*compar) (const void *, const void *))
1598 {
1599         caddr_t item;
1600         size_t sz;
1601
1602         item = (caddr_t)bsearch(key, base, nmemb, size, compar);
1603
1604         if (item == NULL)
1605                 return (0);
1606
1607         sz = (caddr_t)base + nmemb * size - item;
1608
1609         if (sz > 0)
1610                 memmove(item, item + size, sz);
1611
1612         return (1);
1613 }
1614
1615 static struct ifidx *
1616 ifidx_find(struct table_info *ti, void *key)
1617 {
1618         struct ifidx *ifi;
1619
1620         ifi = bsearch(key, ti->state, ti->data, sizeof(struct ifidx),
1621             compare_ifidx);
1622
1623         return (ifi);
1624 }
1625
1626 static int
1627 ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
1628     uint32_t *val)
1629 {
1630         struct ifidx *ifi;
1631
1632         ifi = ifidx_find(ti, key);
1633
1634         if (ifi != NULL) {
1635                 *val = ifi->value;
1636                 return (1);
1637         }
1638
1639         return (0);
1640 }
1641
1642 static int
1643 ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
1644     char *data, uint8_t tflags)
1645 {
1646         struct iftable_cfg *icfg;
1647
1648         icfg = malloc(sizeof(struct iftable_cfg), M_IPFW, M_WAITOK | M_ZERO);
1649
1650         icfg->ii = ipfw_objhash_create(16);
1651         icfg->main_ptr = malloc(sizeof(struct ifidx) * IFIDX_CHUNK,  M_IPFW,
1652             M_WAITOK | M_ZERO);
1653         icfg->size = IFIDX_CHUNK;
1654         icfg->ch = ch;
1655
1656         *ta_state = icfg;
1657         ti->state = icfg->main_ptr;
1658         ti->lookup = ta_lookup_ifidx;
1659
1660         return (0);
1661 }
1662
1663 /*
1664  * Handle tableinfo @ti pointer change (on table array resize).
1665  */
1666 static void
1667 ta_change_ti_ifidx(void *ta_state, struct table_info *ti)
1668 {
1669         struct iftable_cfg *icfg;
1670
1671         icfg = (struct iftable_cfg *)ta_state;
1672         icfg->ti = ti;
1673 }
1674
1675 static void
1676 destroy_ifidx_locked(struct namedobj_instance *ii, struct named_object *no,
1677     void *arg)
1678 {
1679         struct ifentry *ife;
1680         struct ip_fw_chain *ch;
1681
1682         ch = (struct ip_fw_chain *)arg;
1683         ife = (struct ifentry *)no;
1684
1685         ipfw_iface_del_notify(ch, &ife->ic);
1686         free(ife, M_IPFW_TBL);
1687 }
1688
1689
1690 /*
1691  * Destroys table @ti
1692  */
1693 static void
1694 ta_destroy_ifidx(void *ta_state, struct table_info *ti)
1695 {
1696         struct iftable_cfg *icfg;
1697         struct ip_fw_chain *ch;
1698
1699         icfg = (struct iftable_cfg *)ta_state;
1700         ch = icfg->ch;
1701
1702         if (icfg->main_ptr != NULL)
1703                 free(icfg->main_ptr, M_IPFW);
1704
1705         ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
1706
1707         ipfw_objhash_destroy(icfg->ii);
1708
1709         free(icfg, M_IPFW);
1710 }
1711
1712 struct ta_buf_ifidx
1713 {
1714         struct ifentry *ife;
1715         uint32_t value;
1716 };
1717
1718 /*
1719  * Prepare state to add to the table:
1720  * allocate ifentry and reference needed interface.
1721  */
1722 static int
1723 ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1724     void *ta_buf)
1725 {
1726         struct ta_buf_ifidx *tb;
1727         char *ifname;
1728         struct ifentry *ife;
1729
1730         tb = (struct ta_buf_ifidx *)ta_buf;
1731
1732         /* Check if string is terminated */
1733         ifname = (char *)tei->paddr;
1734         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1735                 return (EINVAL);
1736
1737         ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
1738         ife->value = tei->value;
1739         ife->ic.cb = if_notifier;
1740         ife->ic.cbdata = ife;
1741
1742         if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0)
1743                 return (EINVAL);
1744
1745         /* Use ipfw_iface 'ifname' field as stable storage */
1746         ife->no.name = ife->ic.iface->ifname;
1747
1748         tb->ife = ife;
1749
1750         return (0);
1751 }
1752
1753 static int
1754 ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1755     void *ta_buf, uint32_t *pnum)
1756 {
1757         struct iftable_cfg *icfg;
1758         struct ifentry *ife, *tmp;
1759         struct ta_buf_ifidx *tb;
1760         struct ipfw_iface *iif;
1761         struct ifidx *ifi;
1762         char *ifname;
1763         uint32_t value;
1764
1765         tb = (struct ta_buf_ifidx *)ta_buf;
1766         ifname = (char *)tei->paddr;
1767         icfg = (struct iftable_cfg *)ta_state;
1768         ife = tb->ife;
1769
1770         ife->icfg = icfg;
1771
1772         tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1773
1774         if (tmp != NULL) {
1775                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1776                         return (EEXIST);
1777
1778                 /* Exchange values in @tmp and @tei */
1779                 value = tmp->value;
1780                 tmp->value = tei->value;
1781                 tei->value = value;
1782
1783                 iif = tmp->ic.iface;
1784                 if (iif->resolved != 0) {
1785                         /* We have to update runtime value, too */
1786                         ifi = ifidx_find(ti, &iif->ifindex);
1787                         ifi->value = ife->value;
1788                 }
1789
1790                 /* Indicate that update has happened instead of addition */
1791                 tei->flags |= TEI_FLAGS_UPDATED;
1792                 *pnum = 0;
1793                 return (0);
1794         }
1795
1796         if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
1797                 return (EFBIG);
1798
1799         /* Link to internal list */
1800         ipfw_objhash_add(icfg->ii, &ife->no);
1801
1802         /* Link notifier (possible running its callback) */
1803         ipfw_iface_add_notify(icfg->ch, &ife->ic);
1804         icfg->count++;
1805
1806         tb->ife = NULL;
1807         *pnum = 1;
1808
1809         return (0);
1810 }
1811
1812 /*
1813  * Prepare to delete key from table.
1814  * Do basic interface name checks.
1815  */
1816 static int
1817 ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1818     void *ta_buf)
1819 {
1820         struct ta_buf_ifidx *tb;
1821         char *ifname;
1822
1823         tb = (struct ta_buf_ifidx *)ta_buf;
1824
1825         /* Check if string is terminated */
1826         ifname = (char *)tei->paddr;
1827         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1828                 return (EINVAL);
1829
1830         return (0);
1831 }
1832
1833 /*
1834  * Remove key from both configuration list and
1835  * runtime array. Removed interface notification.
1836  */
1837 static int
1838 ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1839     void *ta_buf, uint32_t *pnum)
1840 {
1841         struct iftable_cfg *icfg;
1842         struct ifentry *ife;
1843         struct ta_buf_ifidx *tb;
1844         char *ifname;
1845         uint16_t ifindex;
1846         int res;
1847
1848         tb = (struct ta_buf_ifidx *)ta_buf;
1849         ifname = (char *)tei->paddr;
1850         icfg = (struct iftable_cfg *)ta_state;
1851         ife = tb->ife;
1852
1853         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1854
1855         if (ife == NULL)
1856                 return (ENOENT);
1857
1858         if (ife->linked != 0) {
1859                 /* We have to remove item from runtime */
1860                 ifindex = ife->ic.iface->ifindex;
1861
1862                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
1863                     sizeof(struct ifidx), compare_ifidx);
1864
1865                 KASSERT(res == 1, ("index %d does not exist", ifindex));
1866                 icfg->used--;
1867                 ti->data = icfg->used;
1868                 ife->linked = 0;
1869         }
1870
1871         /* Unlink from local list */
1872         ipfw_objhash_del(icfg->ii, &ife->no);
1873         /* Unlink notifier */
1874         ipfw_iface_del_notify(icfg->ch, &ife->ic);
1875
1876         icfg->count--;
1877         tei->value = ife->value;
1878
1879         tb->ife = ife;
1880         *pnum = 1;
1881
1882         return (0);
1883 }
1884
1885 /*
1886  * Flush deleted entry.
1887  * Drops interface reference and frees entry.
1888  */
1889 static void
1890 ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1891     void *ta_buf)
1892 {
1893         struct ta_buf_ifidx *tb;
1894
1895         tb = (struct ta_buf_ifidx *)ta_buf;
1896
1897         if (tb->ife != NULL) {
1898                 /* Unlink first */
1899                 ipfw_iface_unref(ch, &tb->ife->ic);
1900                 free(tb->ife, M_IPFW_TBL);
1901         }
1902 }
1903
1904
1905 /*
1906  * Handle interface announce/withdrawal for particular table.
1907  * Every real runtime array modification happens here.
1908  */
1909 static void
1910 if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
1911 {
1912         struct ifentry *ife;
1913         struct ifidx ifi;
1914         struct iftable_cfg *icfg;
1915         struct table_info *ti;
1916         int res;
1917
1918         ife = (struct ifentry *)cbdata;
1919         icfg = ife->icfg;
1920         ti = icfg->ti;
1921
1922         KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
1923
1924         if (ife->linked == 0 && ifindex != 0) {
1925                 /* Interface announce */
1926                 ifi.kidx = ifindex;
1927                 ifi.spare = 0;
1928                 ifi.value = ife->value;
1929                 res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used,
1930                     sizeof(struct ifidx), compare_ifidx);
1931                 KASSERT(res == 1, ("index %d already exists", ifindex));
1932                 icfg->used++;
1933                 ti->data = icfg->used;
1934                 ife->linked = 1;
1935         } else if (ife->linked != 0 && ifindex == 0) {
1936                 /* Interface withdrawal */
1937                 ifindex = ife->ic.iface->ifindex;
1938
1939                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
1940                     sizeof(struct ifidx), compare_ifidx);
1941
1942                 KASSERT(res == 1, ("index %d does not exist", ifindex));
1943                 icfg->used--;
1944                 ti->data = icfg->used;
1945                 ife->linked = 0;
1946         }
1947 }
1948
1949
1950 /*
1951  * Table growing callbacks.
1952  */
1953
1954 struct mod_ifidx {
1955         void    *main_ptr;
1956         size_t  size;
1957 };
1958
1959 static int
1960 ta_has_space_ifidx(void *ta_state, struct table_info *ti, uint32_t count,
1961     uint64_t *pflags)
1962 {
1963         struct iftable_cfg *cfg;
1964
1965         cfg = (struct iftable_cfg *)ta_state;
1966
1967         if (cfg->count + count > cfg->size) {
1968                 *pflags = roundup2(cfg->count + count, IFIDX_CHUNK);
1969                 return (0);
1970         }
1971
1972         return (1);
1973 }
1974
1975 /*
1976  * Allocate ned, larger runtime ifidx array.
1977  */
1978 static int
1979 ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
1980 {
1981         struct mod_ifidx *mi;
1982
1983         mi = (struct mod_ifidx *)ta_buf;
1984
1985         memset(mi, 0, sizeof(struct mod_ifidx));
1986         mi->size = *pflags;
1987         mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
1988             M_WAITOK | M_ZERO);
1989
1990         return (0);
1991 }
1992
1993 /*
1994  * Copy data from old runtime array to new one.
1995  */
1996 static int
1997 ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1998     uint64_t *pflags)
1999 {
2000         struct mod_ifidx *mi;
2001         struct iftable_cfg *icfg;
2002
2003         mi = (struct mod_ifidx *)ta_buf;
2004         icfg = (struct iftable_cfg *)ta_state;
2005
2006         /* Check if we still need to grow array */
2007         if (icfg->size >= mi->size) {
2008                 *pflags = 0;
2009                 return (0);
2010         }
2011
2012         memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
2013
2014         return (0);
2015 }
2016
2017 /*
2018  * Switch old & new arrays.
2019  */
2020 static int
2021 ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
2022     uint64_t pflags)
2023 {
2024         struct mod_ifidx *mi;
2025         struct iftable_cfg *icfg;
2026         void *old_ptr;
2027
2028         mi = (struct mod_ifidx *)ta_buf;
2029         icfg = (struct iftable_cfg *)ta_state;
2030
2031         old_ptr = icfg->main_ptr;
2032         icfg->main_ptr = mi->main_ptr;
2033         icfg->size = mi->size;
2034         ti->state = icfg->main_ptr;
2035
2036         mi->main_ptr = old_ptr;
2037
2038         return (0);
2039 }
2040
2041 /*
2042  * Free unneded array.
2043  */
2044 static void
2045 ta_flush_mod_ifidx(void *ta_buf)
2046 {
2047         struct mod_ifidx *mi;
2048
2049         mi = (struct mod_ifidx *)ta_buf;
2050         if (mi->main_ptr != NULL)
2051                 free(mi->main_ptr, M_IPFW);
2052 }
2053
2054 static int
2055 ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
2056     ipfw_obj_tentry *tent)
2057 {
2058         struct ifentry *ife;
2059
2060         ife = (struct ifentry *)e;
2061
2062         tent->masklen = 8 * IF_NAMESIZE;
2063         memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
2064         tent->value = ife->value;
2065
2066         return (0);
2067 }
2068
2069 static int
2070 ta_find_ifidx_tentry(void *ta_state, struct table_info *ti,
2071     ipfw_obj_tentry *tent)
2072 {
2073         struct iftable_cfg *icfg;
2074         struct ifentry *ife;
2075         char *ifname;
2076
2077         icfg = (struct iftable_cfg *)ta_state;
2078         ifname = tent->k.iface;
2079
2080         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
2081                 return (EINVAL);
2082
2083         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
2084
2085         if (ife != NULL) {
2086                 ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
2087                 return (0);
2088         }
2089
2090         return (ENOENT);
2091 }
2092
2093 struct wa_ifidx {
2094         ta_foreach_f    *f;
2095         void            *arg;
2096 };
2097
2098 static void
2099 foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
2100     void *arg)
2101 {
2102         struct ifentry *ife;
2103         struct wa_ifidx *wa;
2104
2105         ife = (struct ifentry *)no;
2106         wa = (struct wa_ifidx *)arg;
2107
2108         wa->f(ife, wa->arg);
2109 }
2110
2111 static void
2112 ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2113     void *arg)
2114 {
2115         struct iftable_cfg *icfg;
2116         struct wa_ifidx wa;
2117
2118         icfg = (struct iftable_cfg *)ta_state;
2119
2120         wa.f = f;
2121         wa.arg = arg;
2122
2123         ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
2124 }
2125
2126 struct table_algo iface_idx = {
2127         .name           = "iface:array",
2128         .type           = IPFW_TABLE_INTERFACE,
2129         .flags          = TA_FLAG_DEFAULT,
2130         .ta_buf_size    = sizeof(struct ta_buf_ifidx),
2131         .init           = ta_init_ifidx,
2132         .destroy        = ta_destroy_ifidx,
2133         .prepare_add    = ta_prepare_add_ifidx,
2134         .prepare_del    = ta_prepare_del_ifidx,
2135         .add            = ta_add_ifidx,
2136         .del            = ta_del_ifidx,
2137         .flush_entry    = ta_flush_ifidx_entry,
2138         .foreach        = ta_foreach_ifidx,
2139         .dump_tentry    = ta_dump_ifidx_tentry,
2140         .find_tentry    = ta_find_ifidx_tentry,
2141         .has_space      = ta_has_space_ifidx,
2142         .prepare_mod    = ta_prepare_mod_ifidx,
2143         .fill_mod       = ta_fill_mod_ifidx,
2144         .modify         = ta_modify_ifidx,
2145         .flush_mod      = ta_flush_mod_ifidx,
2146         .change_ti      = ta_change_ti_ifidx,
2147 };
2148
2149 /*
2150  * Number array cmds.
2151  *
2152  * Implementation:
2153  *
2154  * Runtime part:
2155  * - sorted array of "struct numarray" pointed by ti->state.
2156  *   Array is allocated with rounding up to NUMARRAY_CHUNK.
2157  * - current array size is stored in ti->data
2158  *
2159  */
2160
2161 struct numarray {
2162         uint32_t        number;
2163         uint32_t        value;
2164 };
2165
2166 struct numarray_cfg {
2167         void    *main_ptr;
2168         size_t  size;   /* Number of items allocated in array */
2169         size_t  used;   /* Number of items _active_ now */
2170 };
2171
2172 #define NUMARRAY_CHUNK  16
2173
2174 int compare_numarray(const void *k, const void *v);
2175
2176 int
2177 compare_numarray(const void *k, const void *v)
2178 {
2179         struct numarray *na;
2180         uint32_t key;
2181
2182         key = *((uint32_t *)k);
2183         na = (struct numarray *)v;
2184
2185         if (key < na->number)
2186                 return (-1);
2187         else if (key > na->number)
2188                 return (1);
2189
2190         return (0);
2191 }
2192
2193 static struct numarray *
2194 numarray_find(struct table_info *ti, void *key)
2195 {
2196         struct numarray *ri;
2197
2198         ri = bsearch(key, ti->state, ti->data, sizeof(struct numarray),
2199             compare_ifidx);
2200
2201         return (ri);
2202 }
2203
2204 static int
2205 ta_lookup_numarray(struct table_info *ti, void *key, uint32_t keylen,
2206     uint32_t *val)
2207 {
2208         struct numarray *ri;
2209
2210         ri = numarray_find(ti, key);
2211
2212         if (ri != NULL) {
2213                 *val = ri->value;
2214                 return (1);
2215         }
2216
2217         return (0);
2218 }
2219
2220 static int
2221 ta_init_numarray(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2222     char *data, uint8_t tflags)
2223 {
2224         struct numarray_cfg *cfg;
2225
2226         cfg = malloc(sizeof(*cfg), M_IPFW, M_WAITOK | M_ZERO);
2227
2228         cfg->size = NUMARRAY_CHUNK;
2229         cfg->main_ptr = malloc(sizeof(struct numarray) * cfg->size, M_IPFW,
2230             M_WAITOK | M_ZERO);
2231
2232         *ta_state = cfg;
2233         ti->state = cfg->main_ptr;
2234         ti->lookup = ta_lookup_numarray;
2235
2236         return (0);
2237 }
2238
2239 /*
2240  * Destroys table @ti
2241  */
2242 static void
2243 ta_destroy_numarray(void *ta_state, struct table_info *ti)
2244 {
2245         struct numarray_cfg *cfg;
2246
2247         cfg = (struct numarray_cfg *)ta_state;
2248
2249         if (cfg->main_ptr != NULL)
2250                 free(cfg->main_ptr, M_IPFW);
2251
2252         free(cfg, M_IPFW);
2253 }
2254
2255 struct ta_buf_numarray
2256 {
2257         struct numarray na;
2258 };
2259
2260 /*
2261  * Prepare for addition/deletion to an array.
2262  */
2263 static int
2264 ta_prepare_add_numarray(struct ip_fw_chain *ch, struct tentry_info *tei,
2265     void *ta_buf)
2266 {
2267         struct ta_buf_numarray *tb;
2268
2269         tb = (struct ta_buf_numarray *)ta_buf;
2270
2271         tb->na.number = *((uint32_t *)tei->paddr);
2272         tb->na.value = tei->value;
2273
2274         return (0);
2275 }
2276
2277 static int
2278 ta_add_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2279     void *ta_buf, uint32_t *pnum)
2280 {
2281         struct numarray_cfg *cfg;
2282         struct ta_buf_numarray *tb;
2283         struct numarray *ri;
2284         int res;
2285         uint32_t value;
2286
2287         tb = (struct ta_buf_numarray*)ta_buf;
2288         cfg = (struct numarray_cfg *)ta_state;
2289
2290         ri = numarray_find(ti, &tb->na.number);
2291
2292         if (ri != NULL) {
2293                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2294                         return (EEXIST);
2295
2296                 /* Exchange values between ri and @tei */
2297                 value = ri->value;
2298                 ri->value = tei->value;
2299                 tei->value = value;
2300                 /* Indicate that update has happened instead of addition */
2301                 tei->flags |= TEI_FLAGS_UPDATED;
2302                 *pnum = 0;
2303                 return (0);
2304         }
2305
2306         if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2307                 return (EFBIG);
2308
2309         res = badd(&tb->na.number, &tb->na, cfg->main_ptr, cfg->used,
2310             sizeof(struct numarray), compare_numarray);
2311
2312         KASSERT(res == 1, ("number %d already exists", tb->na.number));
2313         cfg->used++;
2314         ti->data = cfg->used;
2315         *pnum = 1;
2316
2317         return (0);
2318 }
2319
2320 /*
2321  * Remove key from both configuration list and
2322  * runtime array. Removed interface notification.
2323  */
2324 static int
2325 ta_del_numarray(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2326     void *ta_buf, uint32_t *pnum)
2327 {
2328         struct numarray_cfg *cfg;
2329         struct ta_buf_numarray *tb;
2330         struct numarray *ri;
2331         int res;
2332
2333         tb = (struct ta_buf_numarray *)ta_buf;
2334         cfg = (struct numarray_cfg *)ta_state;
2335
2336         ri = numarray_find(ti, &tb->na.number);
2337         if (ri == NULL)
2338                 return (ENOENT);
2339
2340         tei->value = ri->value;
2341
2342         res = bdel(&tb->na.number, cfg->main_ptr, cfg->used,
2343             sizeof(struct numarray), compare_numarray);
2344
2345         KASSERT(res == 1, ("number %u does not exist", tb->na.number));
2346         cfg->used--;
2347         ti->data = cfg->used;
2348         *pnum = 1;
2349
2350         return (0);
2351 }
2352
2353 static void
2354 ta_flush_numarray_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
2355     void *ta_buf)
2356 {
2357
2358         /* Do nothing */
2359 }
2360
2361
2362 /*
2363  * Table growing callbacks.
2364  */
2365
2366 static int
2367 ta_has_space_numarray(void *ta_state, struct table_info *ti, uint32_t count,
2368     uint64_t *pflags)
2369 {
2370         struct numarray_cfg *cfg;
2371
2372         cfg = (struct numarray_cfg *)ta_state;
2373
2374         if (cfg->used + count > cfg->size) {
2375                 *pflags = roundup2(cfg->used + count, NUMARRAY_CHUNK);
2376                 return (0);
2377         }
2378
2379         return (1);
2380 }
2381
2382 /*
2383  * Allocate new, larger runtime array.
2384  */
2385 static int
2386 ta_prepare_mod_numarray(void *ta_buf, uint64_t *pflags)
2387 {
2388         struct mod_item *mi;
2389
2390         mi = (struct mod_item *)ta_buf;
2391
2392         memset(mi, 0, sizeof(struct mod_item));
2393         mi->size = *pflags;
2394         mi->main_ptr = malloc(sizeof(struct numarray) * mi->size, M_IPFW,
2395             M_WAITOK | M_ZERO);
2396
2397         return (0);
2398 }
2399
2400 /*
2401  * Copy data from old runtime array to new one.
2402  */
2403 static int
2404 ta_fill_mod_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2405     uint64_t *pflags)
2406 {
2407         struct mod_item *mi;
2408         struct numarray_cfg *cfg;
2409
2410         mi = (struct mod_item *)ta_buf;
2411         cfg = (struct numarray_cfg *)ta_state;
2412
2413         /* Check if we still need to grow array */
2414         if (cfg->size >= mi->size) {
2415                 *pflags = 0;
2416                 return (0);
2417         }
2418
2419         memcpy(mi->main_ptr, cfg->main_ptr, cfg->used * sizeof(struct numarray));
2420
2421         return (0);
2422 }
2423
2424 /*
2425  * Switch old & new arrays.
2426  */
2427 static int
2428 ta_modify_numarray(void *ta_state, struct table_info *ti, void *ta_buf,
2429     uint64_t pflags)
2430 {
2431         struct mod_item *mi;
2432         struct numarray_cfg *cfg;
2433         void *old_ptr;
2434
2435         mi = (struct mod_item *)ta_buf;
2436         cfg = (struct numarray_cfg *)ta_state;
2437
2438         old_ptr = cfg->main_ptr;
2439         cfg->main_ptr = mi->main_ptr;
2440         cfg->size = mi->size;
2441         ti->state = cfg->main_ptr;
2442
2443         mi->main_ptr = old_ptr;
2444
2445         return (0);
2446 }
2447
2448 /*
2449  * Free unneded array.
2450  */
2451 static void
2452 ta_flush_mod_numarray(void *ta_buf)
2453 {
2454         struct mod_item *mi;
2455
2456         mi = (struct mod_item *)ta_buf;
2457         if (mi->main_ptr != NULL)
2458                 free(mi->main_ptr, M_IPFW);
2459 }
2460
2461 static int
2462 ta_dump_numarray_tentry(void *ta_state, struct table_info *ti, void *e,
2463     ipfw_obj_tentry *tent)
2464 {
2465         struct numarray *na;
2466
2467         na = (struct numarray *)e;
2468
2469         tent->k.key = na->number;
2470         tent->value = na->value;
2471
2472         return (0);
2473 }
2474
2475 static int
2476 ta_find_numarray_tentry(void *ta_state, struct table_info *ti,
2477     ipfw_obj_tentry *tent)
2478 {
2479         struct numarray_cfg *cfg;
2480         struct numarray *ri;
2481
2482         cfg = (struct numarray_cfg *)ta_state;
2483
2484         ri = numarray_find(ti, &tent->k.key);
2485
2486         if (ri != NULL) {
2487                 ta_dump_numarray_tentry(ta_state, ti, ri, tent);
2488                 return (0);
2489         }
2490
2491         return (ENOENT);
2492 }
2493
2494 static void
2495 ta_foreach_numarray(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2496     void *arg)
2497 {
2498         struct numarray_cfg *cfg;
2499         struct numarray *array;
2500         int i;
2501
2502         cfg = (struct numarray_cfg *)ta_state;
2503         array = cfg->main_ptr;
2504
2505         for (i = 0; i < cfg->used; i++)
2506                 f(&array[i], arg);
2507 }
2508
2509 struct table_algo number_array = {
2510         .name           = "number:array",
2511         .type           = IPFW_TABLE_NUMBER,
2512         .ta_buf_size    = sizeof(struct ta_buf_numarray),
2513         .init           = ta_init_numarray,
2514         .destroy        = ta_destroy_numarray,
2515         .prepare_add    = ta_prepare_add_numarray,
2516         .prepare_del    = ta_prepare_add_numarray,
2517         .add            = ta_add_numarray,
2518         .del            = ta_del_numarray,
2519         .flush_entry    = ta_flush_numarray_entry,
2520         .foreach        = ta_foreach_numarray,
2521         .dump_tentry    = ta_dump_numarray_tentry,
2522         .find_tentry    = ta_find_numarray_tentry,
2523         .has_space      = ta_has_space_numarray,
2524         .prepare_mod    = ta_prepare_mod_numarray,
2525         .fill_mod       = ta_fill_mod_numarray,
2526         .modify         = ta_modify_numarray,
2527         .flush_mod      = ta_flush_mod_numarray,
2528 };
2529
2530 /*
2531  * flow:hash cmds
2532  *
2533  *
2534  * ti->data:
2535  * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
2536  * [        8][        8[          8][         8]
2537  *
2538  * inv.mask4: 32 - mask
2539  * inv.mask6:
2540  * 1) _slow lookup: mask
2541  * 2) _aligned: (128 - mask) / 8
2542  * 3) _64: 8
2543  *
2544  *
2545  * pflags:
2546  * [hsize4][hsize6]
2547  * [    16][    16]
2548  */
2549
2550 struct fhashentry;
2551
2552 SLIST_HEAD(fhashbhead, fhashentry);
2553
2554 struct fhashentry {
2555         SLIST_ENTRY(fhashentry) next;
2556         uint8_t         af;
2557         uint8_t         proto;
2558         uint16_t        spare0;
2559         uint16_t        dport;
2560         uint16_t        sport;
2561         uint32_t        value;
2562         uint32_t        spare1;
2563 };
2564
2565 struct fhashentry4 {
2566         struct fhashentry       e;
2567         struct in_addr          dip;
2568         struct in_addr          sip;
2569 };
2570
2571 struct fhashentry6 {
2572         struct fhashentry       e;
2573         struct in6_addr         dip6;
2574         struct in6_addr         sip6;
2575 };
2576
2577 struct fhash_cfg {
2578         struct fhashbhead       *head;
2579         size_t                  size;
2580         size_t                  items;
2581         struct fhashentry4      fe4;
2582         struct fhashentry6      fe6;
2583 };
2584
2585 static __inline int
2586 cmp_flow_ent(struct fhashentry *a, struct fhashentry *b, size_t sz)
2587 {
2588         uint64_t *ka, *kb;
2589
2590         ka = (uint64_t *)(&a->next + 1);
2591         kb = (uint64_t *)(&b->next + 1);
2592
2593         if (*ka == *kb && (memcmp(a + 1, b + 1, sz) == 0))
2594                 return (1);
2595
2596         return (0);
2597 }
2598
2599 static __inline uint32_t
2600 hash_flow4(struct fhashentry4 *f, int hsize)
2601 {
2602         uint32_t i;
2603
2604         i = (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.sport);
2605
2606         return (i % (hsize - 1));
2607 }
2608
2609 static __inline uint32_t
2610 hash_flow6(struct fhashentry6 *f, int hsize)
2611 {
2612         uint32_t i;
2613
2614         i = (f->dip6.__u6_addr.__u6_addr32[2]) ^
2615             (f->dip6.__u6_addr.__u6_addr32[3]) ^
2616             (f->sip6.__u6_addr.__u6_addr32[2]) ^
2617             (f->sip6.__u6_addr.__u6_addr32[3]) ^
2618             (f->e.dport) ^ (f->e.sport);
2619
2620         return (i % (hsize - 1));
2621 }
2622
2623 static uint32_t
2624 hash_flow_ent(struct fhashentry *ent, uint32_t size)
2625 {
2626         uint32_t hash;
2627
2628         if (ent->af == AF_INET) {
2629                 hash = hash_flow4((struct fhashentry4 *)ent, size);
2630         } else {
2631                 hash = hash_flow6((struct fhashentry6 *)ent, size);
2632         }
2633
2634         return (hash);
2635 }
2636
2637 static int
2638 ta_lookup_fhash(struct table_info *ti, void *key, uint32_t keylen,
2639     uint32_t *val)
2640 {
2641         struct fhashbhead *head;
2642         struct fhashentry *ent;
2643         struct fhashentry4 *m4;
2644         struct ipfw_flow_id *id;
2645         uint16_t hash, hsize;
2646
2647         id = (struct ipfw_flow_id *)key;
2648         head = (struct fhashbhead *)ti->state;
2649         hsize = ti->data;
2650         m4 = (struct fhashentry4 *)ti->xstate;
2651
2652         if (id->addr_type == 4) {
2653                 struct fhashentry4 f;
2654
2655                 /* Copy hash mask */
2656                 f = *m4;
2657
2658                 f.dip.s_addr &= id->dst_ip;
2659                 f.sip.s_addr &= id->src_ip;
2660                 f.e.dport &= id->dst_port;
2661                 f.e.sport &= id->src_port;
2662                 f.e.proto &= id->proto;
2663                 hash = hash_flow4(&f, hsize);
2664                 SLIST_FOREACH(ent, &head[hash], next) {
2665                         if (cmp_flow_ent(ent, &f.e, 2 * 4) != 0) {
2666                                 *val = ent->value;
2667                                 return (1);
2668                         }
2669                 }
2670         } else if (id->addr_type == 6) {
2671                 struct fhashentry6 f;
2672                 uint64_t *fp, *idp;
2673
2674                 /* Copy hash mask */
2675                 f = *((struct fhashentry6 *)(m4 + 1));
2676
2677                 /* Handle lack of __u6_addr.__u6_addr64 */
2678                 fp = (uint64_t *)&f.dip6;
2679                 idp = (uint64_t *)&id->dst_ip6;
2680                 /* src IPv6 is stored after dst IPv6 */
2681                 *fp++ &= *idp++;
2682                 *fp++ &= *idp++;
2683                 *fp++ &= *idp++;
2684                 *fp &= *idp;
2685                 f.e.dport &= id->dst_port;
2686                 f.e.sport &= id->src_port;
2687                 f.e.proto &= id->proto;
2688                 hash = hash_flow6(&f, hsize);
2689                 SLIST_FOREACH(ent, &head[hash], next) {
2690                         if (cmp_flow_ent(ent, &f.e, 2 * 16) != 0) {
2691                                 *val = ent->value;
2692                                 return (1);
2693                         }
2694                 }
2695         }
2696
2697         return (0);
2698 }
2699
2700 /*
2701  * New table.
2702  */
2703 static int
2704 ta_init_fhash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
2705     char *data, uint8_t tflags)
2706 {
2707         int i;
2708         struct fhash_cfg *cfg;
2709         struct fhashentry4 *fe4;
2710         struct fhashentry6 *fe6;
2711
2712         cfg = malloc(sizeof(struct fhash_cfg), M_IPFW, M_WAITOK | M_ZERO);
2713
2714         cfg->size = 512;
2715
2716         cfg->head = malloc(sizeof(struct fhashbhead) * cfg->size, M_IPFW,
2717             M_WAITOK | M_ZERO);
2718         for (i = 0; i < cfg->size; i++)
2719                 SLIST_INIT(&cfg->head[i]);
2720
2721         /* Fill in fe masks based on @tflags */
2722         fe4 = &cfg->fe4;
2723         fe6 = &cfg->fe6;
2724         if (tflags & IPFW_TFFLAG_SRCIP) {
2725                 memset(&fe4->sip, 0xFF, sizeof(fe4->sip));
2726                 memset(&fe6->sip6, 0xFF, sizeof(fe6->sip6));
2727         }
2728         if (tflags & IPFW_TFFLAG_DSTIP) {
2729                 memset(&fe4->dip, 0xFF, sizeof(fe4->dip));
2730                 memset(&fe6->dip6, 0xFF, sizeof(fe6->dip6));
2731         }
2732         if (tflags & IPFW_TFFLAG_SRCPORT) {
2733                 memset(&fe4->e.sport, 0xFF, sizeof(fe4->e.sport));
2734                 memset(&fe6->e.sport, 0xFF, sizeof(fe6->e.sport));
2735         }
2736         if (tflags & IPFW_TFFLAG_DSTPORT) {
2737                 memset(&fe4->e.dport, 0xFF, sizeof(fe4->e.dport));
2738                 memset(&fe6->e.dport, 0xFF, sizeof(fe6->e.dport));
2739         }
2740         if (tflags & IPFW_TFFLAG_PROTO) {
2741                 memset(&fe4->e.proto, 0xFF, sizeof(fe4->e.proto));
2742                 memset(&fe6->e.proto, 0xFF, sizeof(fe6->e.proto));
2743         }
2744
2745         fe4->e.af = AF_INET;
2746         fe6->e.af = AF_INET6;
2747
2748         *ta_state = cfg;
2749         ti->state = cfg->head;
2750         ti->xstate = &cfg->fe4;
2751         ti->data = cfg->size;
2752         ti->lookup = ta_lookup_fhash;
2753
2754         return (0);
2755 }
2756
2757 static void
2758 ta_destroy_fhash(void *ta_state, struct table_info *ti)
2759 {
2760         struct fhash_cfg *cfg;
2761         struct fhashentry *ent, *ent_next;
2762         int i;
2763
2764         cfg = (struct fhash_cfg *)ta_state;
2765
2766         for (i = 0; i < cfg->size; i++)
2767                 SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next)
2768                         free(ent, M_IPFW_TBL);
2769
2770         free(cfg->head, M_IPFW);
2771         free(cfg, M_IPFW);
2772 }
2773
2774 static int
2775 ta_dump_fhash_tentry(void *ta_state, struct table_info *ti, void *e,
2776     ipfw_obj_tentry *tent)
2777 {
2778         struct fhash_cfg *cfg;
2779         struct fhashentry *ent;
2780         struct fhashentry4 *fe4;
2781         struct fhashentry6 *fe6;
2782         struct tflow_entry *tfe;
2783
2784         cfg = (struct fhash_cfg *)ta_state;
2785         ent = (struct fhashentry *)e;
2786         tfe = &tent->k.flow;
2787
2788         tfe->af = ent->af;
2789         tfe->proto = ent->proto;
2790         tfe->dport = htons(ent->dport);
2791         tfe->sport = htons(ent->sport);
2792         tent->value = ent->value;
2793         tent->subtype = ent->af;
2794
2795         if (ent->af == AF_INET) {
2796                 fe4 = (struct fhashentry4 *)ent;
2797                 tfe->a.a4.sip.s_addr = htonl(fe4->sip.s_addr);
2798                 tfe->a.a4.dip.s_addr = htonl(fe4->dip.s_addr);
2799                 tent->masklen = 32;
2800 #ifdef INET6
2801         } else {
2802                 fe6 = (struct fhashentry6 *)ent;
2803                 tfe->a.a6.sip6 = fe6->sip6;
2804                 tfe->a.a6.dip6 = fe6->dip6;
2805                 tent->masklen = 128;
2806 #endif
2807         }
2808
2809         return (0);
2810 }
2811
2812 static int
2813 tei_to_fhash_ent(struct tentry_info *tei, struct fhashentry *ent)
2814 {
2815         struct fhashentry4 *fe4;
2816         struct fhashentry6 *fe6;
2817         struct tflow_entry *tfe;
2818
2819         tfe = (struct tflow_entry *)tei->paddr;
2820
2821         ent->af = tei->subtype;
2822         ent->proto = tfe->proto;
2823         ent->value = tei->value;
2824         ent->dport = ntohs(tfe->dport);
2825         ent->sport = ntohs(tfe->sport);
2826
2827         if (tei->subtype == AF_INET) {
2828 #ifdef INET
2829                 fe4 = (struct fhashentry4 *)ent;
2830                 fe4->sip.s_addr = ntohl(tfe->a.a4.sip.s_addr);
2831                 fe4->dip.s_addr = ntohl(tfe->a.a4.dip.s_addr);
2832 #endif
2833 #ifdef INET6
2834         } else if (tei->subtype == AF_INET6) {
2835                 fe6 = (struct fhashentry6 *)ent;
2836                 fe6->sip6 = tfe->a.a6.sip6;
2837                 fe6->dip6 = tfe->a.a6.dip6;
2838 #endif
2839         } else {
2840                 /* Unknown CIDR type */
2841                 return (EINVAL);
2842         }
2843
2844         return (0);
2845 }
2846
2847
2848 static int
2849 ta_find_fhash_tentry(void *ta_state, struct table_info *ti,
2850     ipfw_obj_tentry *tent)
2851 {
2852         struct fhash_cfg *cfg;
2853         struct fhashbhead *head;
2854         struct fhashentry *ent, *tmp;
2855         struct fhashentry6 fe6;
2856         struct tentry_info tei;
2857         int error;
2858         uint32_t hash;
2859         size_t sz;
2860
2861         cfg = (struct fhash_cfg *)ta_state;
2862
2863         ent = &fe6.e;
2864
2865         memset(&fe6, 0, sizeof(fe6));
2866         memset(&tei, 0, sizeof(tei));
2867
2868         tei.paddr = &tent->k.flow;
2869         tei.subtype = tent->subtype;
2870
2871         if ((error = tei_to_fhash_ent(&tei, ent)) != 0)
2872                 return (error);
2873
2874         head = cfg->head;
2875         hash = hash_flow_ent(ent, cfg->size);
2876
2877         if (tei.subtype == AF_INET)
2878                 sz = 2 * sizeof(struct in_addr);
2879         else
2880                 sz = 2 * sizeof(struct in6_addr);
2881
2882         /* Check for existence */
2883         SLIST_FOREACH(tmp, &head[hash], next) {
2884                 if (cmp_flow_ent(tmp, ent, sz) != 0) {
2885                         ta_dump_fhash_tentry(ta_state, ti, tmp, tent);
2886                         return (0);
2887                 }
2888         }
2889
2890         return (ENOENT);
2891 }
2892
2893 static void
2894 ta_foreach_fhash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
2895     void *arg)
2896 {
2897         struct fhash_cfg *cfg;
2898         struct fhashentry *ent, *ent_next;
2899         int i;
2900
2901         cfg = (struct fhash_cfg *)ta_state;
2902
2903         for (i = 0; i < cfg->size; i++)
2904                 SLIST_FOREACH_SAFE(ent, &cfg->head[i], next, ent_next)
2905                         f(ent, arg);
2906 }
2907
2908
2909 struct ta_buf_fhash
2910 {
2911         void *ent_ptr;
2912         struct fhashentry6 fe6;
2913 };
2914
2915 static int
2916 ta_prepare_add_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
2917     void *ta_buf)
2918 {
2919         struct ta_buf_fhash *tb;
2920         struct fhashentry *ent;
2921         size_t sz;
2922         int error;
2923
2924         tb = (struct ta_buf_fhash *)ta_buf;
2925
2926         if (tei->subtype == AF_INET)
2927                 sz = sizeof(struct fhashentry4);
2928         else if (tei->subtype == AF_INET6)
2929                 sz = sizeof(struct fhashentry6);
2930         else
2931                 return (EINVAL);
2932
2933         ent = malloc(sz, M_IPFW_TBL, M_WAITOK | M_ZERO);
2934
2935         error = tei_to_fhash_ent(tei, ent);
2936         if (error != 0) {
2937                 free(ent, M_IPFW_TBL);
2938                 return (error);
2939         }
2940         tb->ent_ptr = ent;
2941
2942         return (0);
2943 }
2944
2945 static int
2946 ta_add_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
2947     void *ta_buf, uint32_t *pnum)
2948 {
2949         struct fhash_cfg *cfg;
2950         struct fhashbhead *head;
2951         struct fhashentry *ent, *tmp;
2952         struct ta_buf_fhash *tb;
2953         int exists;
2954         uint32_t hash, value;
2955         size_t sz;
2956
2957         cfg = (struct fhash_cfg *)ta_state;
2958         tb = (struct ta_buf_fhash *)ta_buf;
2959         ent = (struct fhashentry *)tb->ent_ptr;
2960         exists = 0;
2961
2962         head = cfg->head;
2963         hash = hash_flow_ent(ent, cfg->size);
2964
2965         if (tei->subtype == AF_INET)
2966                 sz = 2 * sizeof(struct in_addr);
2967         else
2968                 sz = 2 * sizeof(struct in6_addr);
2969
2970         /* Check for existence */
2971         SLIST_FOREACH(tmp, &head[hash], next) {
2972                 if (cmp_flow_ent(tmp, ent, sz) != 0) {
2973                         exists = 1;
2974                         break;
2975                 }
2976         }
2977
2978         if (exists == 1) {
2979                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
2980                         return (EEXIST);
2981                 /* Record already exists. Update value if we're asked to */
2982                 /* Exchange values between tmp and @tei */
2983                 value = tmp->value;
2984                 tmp->value = tei->value;
2985                 tei->value = value;
2986                 /* Indicate that update has happened instead of addition */
2987                 tei->flags |= TEI_FLAGS_UPDATED;
2988                 *pnum = 0;
2989         } else {
2990                 if ((tei->flags & TEI_FLAGS_DONTADD) != 0)
2991                         return (EFBIG);
2992
2993                 SLIST_INSERT_HEAD(&head[hash], ent, next);
2994                 tb->ent_ptr = NULL;
2995                 *pnum = 1;
2996
2997                 /* Update counters and check if we need to grow hash */
2998                 cfg->items++;
2999         }
3000
3001         return (0);
3002 }
3003
3004 static int
3005 ta_prepare_del_fhash(struct ip_fw_chain *ch, struct tentry_info *tei,
3006     void *ta_buf)
3007 {
3008         struct ta_buf_fhash *tb;
3009
3010         tb = (struct ta_buf_fhash *)ta_buf;
3011
3012         return (tei_to_fhash_ent(tei, &tb->fe6.e));
3013 }
3014
3015 static int
3016 ta_del_fhash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
3017     void *ta_buf, uint32_t *pnum)
3018 {
3019         struct fhash_cfg *cfg;
3020         struct fhashbhead *head;
3021         struct fhashentry *ent, *tmp;
3022         struct ta_buf_fhash *tb;
3023         uint32_t hash;
3024         size_t sz;
3025
3026         cfg = (struct fhash_cfg *)ta_state;
3027         tb = (struct ta_buf_fhash *)ta_buf;
3028         ent = &tb->fe6.e;
3029
3030         head = cfg->head;
3031         hash = hash_flow_ent(ent, cfg->size);
3032
3033         if (tei->subtype == AF_INET)
3034                 sz = 2 * sizeof(struct in_addr);
3035         else
3036                 sz = 2 * sizeof(struct in6_addr);
3037
3038         /* Check for existence */
3039         SLIST_FOREACH(tmp, &head[hash], next) {
3040                 if (cmp_flow_ent(tmp, ent, sz) == 0)
3041                         continue;
3042
3043                 SLIST_REMOVE(&head[hash], tmp, fhashentry, next);
3044                 tei->value = tmp->value;
3045                 *pnum = 1;
3046                 cfg->items--;
3047                 tb->ent_ptr = tmp;
3048                 return (0);
3049         }
3050
3051         return (ENOENT);
3052 }
3053
3054 static void
3055 ta_flush_fhash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
3056     void *ta_buf)
3057 {
3058         struct ta_buf_fhash *tb;
3059
3060         tb = (struct ta_buf_fhash *)ta_buf;
3061
3062         if (tb->ent_ptr != NULL)
3063                 free(tb->ent_ptr, M_IPFW_TBL);
3064 }
3065
3066 /*
3067  * Hash growing callbacks.
3068  */
3069
3070 static int
3071 ta_has_space_fhash(void *ta_state, struct table_info *ti, uint32_t count,
3072     uint64_t *pflags)
3073 {
3074         struct fhash_cfg *cfg;
3075
3076         cfg = (struct fhash_cfg *)ta_state;
3077
3078         if (cfg->items > cfg->size && cfg->size < 65536) {
3079                 *pflags = cfg->size * 2;
3080                 return (0);
3081         }
3082
3083         return (1);
3084 }
3085
3086 /*
3087  * Allocate new, larger fhash.
3088  */
3089 static int
3090 ta_prepare_mod_fhash(void *ta_buf, uint64_t *pflags)
3091 {
3092         struct mod_item *mi;
3093         struct fhashbhead *head;
3094         int i;
3095
3096         mi = (struct mod_item *)ta_buf;
3097
3098         memset(mi, 0, sizeof(struct mod_item));
3099         mi->size = *pflags;
3100         head = malloc(sizeof(struct fhashbhead) * mi->size, M_IPFW,
3101             M_WAITOK | M_ZERO);
3102         for (i = 0; i < mi->size; i++)
3103                 SLIST_INIT(&head[i]);
3104
3105         mi->main_ptr = head;
3106
3107         return (0);
3108 }
3109
3110 /*
3111  * Copy data from old runtime array to new one.
3112  */
3113 static int
3114 ta_fill_mod_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3115     uint64_t *pflags)
3116 {
3117
3118         /* In is not possible to do rehash if we're not holidng WLOCK. */
3119         return (0);
3120 }
3121
3122
3123 /*
3124  * Switch old & new arrays.
3125  */
3126 static int
3127 ta_modify_fhash(void *ta_state, struct table_info *ti, void *ta_buf,
3128     uint64_t pflags)
3129 {
3130         struct mod_item *mi;
3131         struct fhash_cfg *cfg;
3132         struct fhashbhead *old_head, *new_head;
3133         struct fhashentry *ent, *ent_next;
3134         int i;
3135         uint32_t nhash;
3136         size_t old_size;
3137
3138         mi = (struct mod_item *)ta_buf;
3139         cfg = (struct fhash_cfg *)ta_state;
3140
3141         /* Check which hash we need to grow and do we still need that */
3142         old_size = cfg->size;
3143         old_head = ti->state;
3144
3145         if (old_size >= mi->size)
3146                 return (0);
3147
3148         new_head = (struct fhashbhead *)mi->main_ptr;
3149         for (i = 0; i < old_size; i++) {
3150                 SLIST_FOREACH_SAFE(ent, &old_head[i], next, ent_next) {
3151                         nhash = hash_flow_ent(ent, mi->size);
3152                         SLIST_INSERT_HEAD(&new_head[nhash], ent, next);
3153                 }
3154         }
3155
3156         ti->state = new_head;
3157         ti->data = mi->size;
3158         cfg->head = new_head;
3159         cfg->size = mi->size;
3160
3161         mi->main_ptr = old_head;
3162
3163         return (0);
3164 }
3165
3166 /*
3167  * Free unneded array.
3168  */
3169 static void
3170 ta_flush_mod_fhash(void *ta_buf)
3171 {
3172         struct mod_item *mi;
3173
3174         mi = (struct mod_item *)ta_buf;
3175         if (mi->main_ptr != NULL)
3176                 free(mi->main_ptr, M_IPFW);
3177 }
3178
3179 struct table_algo flow_hash = {
3180         .name           = "flow:hash",
3181         .type           = IPFW_TABLE_FLOW,
3182         .flags          = TA_FLAG_DEFAULT,
3183         .ta_buf_size    = sizeof(struct ta_buf_fhash),
3184         .init           = ta_init_fhash,
3185         .destroy        = ta_destroy_fhash,
3186         .prepare_add    = ta_prepare_add_fhash,
3187         .prepare_del    = ta_prepare_del_fhash,
3188         .add            = ta_add_fhash,
3189         .del            = ta_del_fhash,
3190         .flush_entry    = ta_flush_fhash_entry,
3191         .foreach        = ta_foreach_fhash,
3192         .dump_tentry    = ta_dump_fhash_tentry,
3193         .find_tentry    = ta_find_fhash_tentry,
3194         .has_space      = ta_has_space_fhash,
3195         .prepare_mod    = ta_prepare_mod_fhash,
3196         .fill_mod       = ta_fill_mod_fhash,
3197         .modify         = ta_modify_fhash,
3198         .flush_mod      = ta_flush_mod_fhash,
3199 };
3200 void
3201 ipfw_table_algo_init(struct ip_fw_chain *ch)
3202 {
3203         size_t sz;
3204
3205         /*
3206          * Register all algorithms presented here.
3207          */
3208         sz = sizeof(struct table_algo);
3209         ipfw_add_table_algo(ch, &cidr_radix, sz, &cidr_radix.idx);
3210         ipfw_add_table_algo(ch, &cidr_hash, sz, &cidr_hash.idx);
3211         ipfw_add_table_algo(ch, &iface_idx, sz, &iface_idx.idx);
3212         ipfw_add_table_algo(ch, &number_array, sz, &number_array.idx);
3213         ipfw_add_table_algo(ch, &flow_hash, sz, &flow_hash.idx);
3214 }
3215
3216 void
3217 ipfw_table_algo_destroy(struct ip_fw_chain *ch)
3218 {
3219
3220         ipfw_del_table_algo(ch, cidr_radix.idx);
3221         ipfw_del_table_algo(ch, cidr_hash.idx);
3222         ipfw_del_table_algo(ch, iface_idx.idx);
3223         ipfw_del_table_algo(ch, number_array.idx);
3224         ipfw_del_table_algo(ch, flow_hash.idx);
3225 }
3226
3227