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