sys/netpfil/ipfw/ip_fw_table_algo.c

   1 /*-
   2  * Copyright (c) 2004 Ruslan Ermilov and Vsevolod Lobko.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  23  * SUCH DAMAGE.
  24  */
  25
  26 #include <sys/cdefs.h>
  27 __FBSDID("$FreeBSD: projects/ipfw/sys/netpfil/ipfw/ip_fw_table.c 267384 2014-06-12 09:59:11Z melifaro $");
  28
  29 /*
  30  * Lookup table algorithms.
  31  *
  32  */
  33
  34 #include "opt_ipfw.h"
  35 #include "opt_inet.h"
  36 #ifndef INET
  37 #error IPFIREWALL requires INET.
  38 #endif /* INET */
  39 #include "opt_inet6.h"
  40
  41 #include <sys/param.h>
  42 #include <sys/systm.h>
  43 #include <sys/malloc.h>
  44 #include <sys/kernel.h>
  45 #include <sys/lock.h>
  46 #include <sys/rwlock.h>
  47 #include <sys/socket.h>
  48 #include <sys/queue.h>
  49 #include <net/if.h>     /* ip_fw.h requires IFNAMSIZ */
  50 #include <net/radix.h>
  51 #include <net/route.h>
  52 #include <net/vnet.h>
  53
  54 #include <netinet/in.h>
  55 #include <netinet/ip_var.h>     /* struct ipfw_rule_ref */
  56 #include <netinet/ip_fw.h>
  57
  58 #include <netpfil/ipfw/ip_fw_private.h>
  59 #include <netpfil/ipfw/ip_fw_table.h>
  60
  61 static MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
  62
  63 static int badd(const void *key, void *item, void *base, size_t nmemb,
  64     size_t size, int (*compar) (const void *, const void *));
  65 static int bdel(const void *key, void *base, size_t nmemb, size_t size,
  66     int (*compar) (const void *, const void *));
  67
  68
  69 /*
  70  * CIDR implementation using radix
  71  *
  72  */
  73
  74 /*
  75  * The radix code expects addr and mask to be array of bytes,
  76  * with the first byte being the length of the array. rn_inithead
  77  * is called with the offset in bits of the lookup key within the
  78  * array. If we use a sockaddr_in as the underlying type,
  79  * sin_len is conveniently located at offset 0, sin_addr is at
  80  * offset 4 and normally aligned.
  81  * But for portability, let's avoid assumption and make the code explicit
  82  */
  83 #define KEY_LEN(v)      *((uint8_t *)&(v))
  84 /*
  85  * Do not require radix to compare more than actual IPv4/IPv6 address
  86  */
  87 #define KEY_LEN_INET    (offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))
  88 #define KEY_LEN_INET6   (offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr))
  89
  90 #define OFF_LEN_INET    (8 * offsetof(struct sockaddr_in, sin_addr))
  91 #define OFF_LEN_INET6   (8 * offsetof(struct sa_in6, sin6_addr))
  92
  93 struct radix_cidr_entry {
  94         struct radix_node       rn[2];
  95         struct sockaddr_in      addr;
  96         uint32_t                value;
  97         uint8_t                 masklen;
  98 };
  99
 100 struct sa_in6 {
 101         uint8_t                 sin6_len;
 102         uint8_t                 sin6_family;
 103         uint8_t                 pad[2];
 104         struct in6_addr         sin6_addr;
 105 };
 106
 107 struct radix_cidr_xentry {
 108         struct radix_node       rn[2];
 109         struct sa_in6           addr6;
 110         uint32_t                value;
 111         uint8_t                 masklen;
 112 };
 113
 114 static int
 115 ta_lookup_radix(struct table_info *ti, void *key, uint32_t keylen,
 116     uint32_t *val)
 117 {
 118         struct radix_node_head *rnh;
 119
 120         if (keylen == sizeof(in_addr_t)) {
 121                 struct radix_cidr_entry *ent;
 122                 struct sockaddr_in sa;
 123                 KEY_LEN(sa) = KEY_LEN_INET;
 124                 sa.sin_addr.s_addr = *((in_addr_t *)key);
 125                 rnh = (struct radix_node_head *)ti->state;
 126                 ent = (struct radix_cidr_entry *)(rnh->rnh_matchaddr(&sa, rnh));
 127                 if (ent != NULL) {
 128                         *val = ent->value;
 129                         return (1);
 130                 }
 131         } else {
 132                 struct radix_cidr_xentry *xent;
 133                 struct sa_in6 sa6;
 134                 KEY_LEN(sa6) = KEY_LEN_INET6;
 135                 memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
 136                 rnh = (struct radix_node_head *)ti->xstate;
 137                 xent = (struct radix_cidr_xentry *)(rnh->rnh_matchaddr(&sa6, rnh));
 138                 if (xent != NULL) {
 139                         *val = xent->value;
 140                         return (1);
 141                 }
 142         }
 143
 144         return (0);
 145 }
 146
 147 /*
 148  * New table
 149  */
 150 static int
 151 ta_init_radix(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
 152     char *data)
 153 {
 154
 155         if (!rn_inithead(&ti->state, OFF_LEN_INET))
 156                 return (ENOMEM);
 157         if (!rn_inithead(&ti->xstate, OFF_LEN_INET6)) {
 158                 rn_detachhead(&ti->state);
 159                 return (ENOMEM);
 160         }
 161
 162         *ta_state = NULL;
 163         ti->lookup = ta_lookup_radix;
 164
 165         return (0);
 166 }
 167
 168 static int
 169 flush_table_entry(struct radix_node *rn, void *arg)
 170 {
 171         struct radix_node_head * const rnh = arg;
 172         struct radix_cidr_entry *ent;
 173
 174         ent = (struct radix_cidr_entry *)
 175             rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);
 176         if (ent != NULL)
 177                 free(ent, M_IPFW_TBL);
 178         return (0);
 179 }
 180
 181 static void
 182 ta_destroy_radix(void *ta_state, struct table_info *ti)
 183 {
 184         struct radix_node_head *rnh;
 185
 186         rnh = (struct radix_node_head *)(ti->state);
 187         rnh->rnh_walktree(rnh, flush_table_entry, rnh);
 188         rn_detachhead(&ti->state);
 189
 190         rnh = (struct radix_node_head *)(ti->xstate);
 191         rnh->rnh_walktree(rnh, flush_table_entry, rnh);
 192         rn_detachhead(&ti->xstate);
 193 }
 194
 195 static int
 196 ta_dump_radix_tentry(void *ta_state, struct table_info *ti, void *e,
 197     ipfw_obj_tentry *tent)
 198 {
 199         struct radix_cidr_entry *n;
 200         struct radix_cidr_xentry *xn;
 201
 202         n = (struct radix_cidr_entry *)e;
 203
 204         /* Guess IPv4/IPv6 radix by sockaddr family */
 205         if (n->addr.sin_family == AF_INET) {
 206                 tent->k.addr.s_addr = n->addr.sin_addr.s_addr;
 207                 tent->masklen = n->masklen;
 208                 tent->subtype = AF_INET;
 209                 tent->value = n->value;
 210 #ifdef INET6
 211         } else {
 212                 xn = (struct radix_cidr_xentry *)e;
 213                 memcpy(&tent->k, &xn->addr6.sin6_addr, sizeof(struct in6_addr));
 214                 tent->masklen = xn->masklen;
 215                 tent->subtype = AF_INET6;
 216                 tent->value = xn->value;
 217 #endif
 218         }
 219
 220         return (0);
 221 }
 222
 223 static int
 224 ta_find_radix_tentry(void *ta_state, struct table_info *ti, void *key,
 225     uint32_t keylen, ipfw_obj_tentry *tent)
 226 {
 227         struct radix_node_head *rnh;
 228         void *e;
 229
 230         e = NULL;
 231         if (keylen == sizeof(in_addr_t)) {
 232                 struct sockaddr_in sa;
 233                 KEY_LEN(sa) = KEY_LEN_INET;
 234                 sa.sin_addr.s_addr = *((in_addr_t *)key);
 235                 rnh = (struct radix_node_head *)ti->state;
 236                 e = rnh->rnh_matchaddr(&sa, rnh);
 237         } else {
 238                 struct sa_in6 sa6;
 239                 KEY_LEN(sa6) = KEY_LEN_INET6;
 240                 memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
 241                 rnh = (struct radix_node_head *)ti->xstate;
 242                 e = rnh->rnh_matchaddr(&sa6, rnh);
 243         }
 244
 245         if (e != NULL) {
 246                 ta_dump_radix_tentry(ta_state, ti, e, tent);
 247                 return (0);
 248         }
 249
 250         return (ENOENT);
 251 }
 252
 253 static void
 254 ta_foreach_radix(void *ta_state, struct table_info *ti, ta_foreach_f *f,
 255     void *arg)
 256 {
 257         struct radix_node_head *rnh;
 258
 259         rnh = (struct radix_node_head *)(ti->state);
 260         rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg);
 261
 262         rnh = (struct radix_node_head *)(ti->xstate);
 263         rnh->rnh_walktree(rnh, (walktree_f_t *)f, arg);
 264 }
 265
 266
 267 struct ta_buf_cidr
 268 {
 269         struct sockaddr *addr_ptr;
 270         struct sockaddr *mask_ptr;
 271         void *ent_ptr;
 272         union {
 273                 struct {
 274                         struct sockaddr_in sa;
 275                         struct sockaddr_in ma;
 276                 } a4;
 277                 struct {
 278                         struct sa_in6 sa;
 279                         struct sa_in6 ma;
 280                 } a6;
 281         } addr;
 282 };
 283
 284 #ifdef INET6
 285 static inline void
 286 ipv6_writemask(struct in6_addr *addr6, uint8_t mask)
 287 {
 288         uint32_t *cp;
 289
 290         for (cp = (uint32_t *)addr6; mask >= 32; mask -= 32)
 291                 *cp++ = 0xFFFFFFFF;
 292         *cp = htonl(mask ? ~((1 << (32 - mask)) - 1) : 0);
 293 }
 294 #endif
 295
 296
 297 static int
 298 ta_prepare_add_cidr(struct ip_fw_chain *ch, struct tentry_info *tei,
 299     void *ta_buf)
 300 {
 301         struct ta_buf_cidr *tb;
 302         struct radix_cidr_entry *ent;
 303         struct radix_cidr_xentry *xent;
 304         in_addr_t addr;
 305         struct sockaddr_in *mask;
 306         struct sa_in6 *mask6;
 307         int mlen;
 308
 309         tb = (struct ta_buf_cidr *)ta_buf;
 310         memset(tb, 0, sizeof(struct ta_buf_cidr));
 311
 312         mlen = tei->masklen;
 313
 314         if (tei->subtype == AF_INET) {
 315 #ifdef INET
 316                 if (mlen > 32)
 317                         return (EINVAL);
 318                 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
 319                 ent->value = tei->value;
 320                 mask = &tb->addr.a4.ma;
 321                 /* Set 'total' structure length */
 322                 KEY_LEN(ent->addr) = KEY_LEN_INET;
 323                 KEY_LEN(*mask) = KEY_LEN_INET;
 324                 ent->addr.sin_family = AF_INET;
 325                 mask->sin_addr.s_addr =
 326                     htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
 327                 addr = *((in_addr_t *)tei->paddr);
 328                 ent->addr.sin_addr.s_addr = addr & mask->sin_addr.s_addr;
 329                 ent->masklen = mlen;
 330                 /* Set pointers */
 331                 tb->ent_ptr = ent;
 332                 tb->addr_ptr = (struct sockaddr *)&ent->addr;
 333                 if (mlen != 32)
 334                         tb->mask_ptr = (struct sockaddr *)mask;
 335 #endif
 336 #ifdef INET6
 337         } else if (tei->subtype == AF_INET6) {
 338                 /* IPv6 case */
 339                 if (mlen > 128)
 340                         return (EINVAL);
 341                 xent = malloc(sizeof(*xent), M_IPFW_TBL, M_WAITOK | M_ZERO);
 342                 xent->value = tei->value;
 343                 mask6 = &tb->addr.a6.ma;
 344                 /* Set 'total' structure length */
 345                 KEY_LEN(xent->addr6) = KEY_LEN_INET6;
 346                 KEY_LEN(*mask6) = KEY_LEN_INET6;
 347                 xent->addr6.sin6_family = AF_INET6;
 348                 ipv6_writemask(&mask6->sin6_addr, mlen);
 349                 memcpy(&xent->addr6.sin6_addr, tei->paddr,
 350                     sizeof(struct in6_addr));
 351                 APPLY_MASK(&xent->addr6.sin6_addr, &mask6->sin6_addr);
 352                 xent->masklen = mlen;
 353                 /* Set pointers */
 354                 tb->ent_ptr = xent;
 355                 tb->addr_ptr = (struct sockaddr *)&xent->addr6;
 356                 if (mlen != 128)
 357                         tb->mask_ptr = (struct sockaddr *)mask6;
 358 #endif
 359         } else {
 360                 /* Unknown CIDR type */
 361                 return (EINVAL);
 362         }
 363
 364         return (0);
 365 }
 366
 367 static int
 368 ta_add_cidr(void *ta_state, struct table_info *ti, struct tentry_info *tei,
 369     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
 370 {
 371         struct radix_node_head *rnh;
 372         struct radix_node *rn;
 373         struct ta_buf_cidr *tb;
 374         uint32_t value;
 375
 376         tb = (struct ta_buf_cidr *)ta_buf;
 377
 378         if (tei->subtype == AF_INET)
 379                 rnh = ti->state;
 380         else
 381                 rnh = ti->xstate;
 382
 383         rn = rnh->rnh_addaddr(tb->addr_ptr, tb->mask_ptr, rnh, tb->ent_ptr);
 384
 385         if (rn == NULL) {
 386                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
 387                         return (EEXIST);
 388                 /* Record already exists. Update value if we're asked to */
 389                 rn = rnh->rnh_lookup(tb->addr_ptr, tb->mask_ptr, rnh);
 390                 if (rn == NULL) {
 391
 392                         /*
 393                          * Radix may have failed addition for other reasons
 394                          * like failure in mask allocation code.
 395                          */
 396                         return (EINVAL);
 397                 }
 398
 399                 if (tei->subtype == AF_INET) {
 400                         /* IPv4. */
 401                         value = ((struct radix_cidr_entry *)tb->ent_ptr)->value;
 402                         ((struct radix_cidr_entry *)rn)->value = value;
 403                 } else {
 404                         /* IPv6 */
 405                         value = ((struct radix_cidr_xentry *)tb->ent_ptr)->value;
 406                         ((struct radix_cidr_xentry *)rn)->value = value;
 407                 }
 408
 409                 /* Indicate that update has happened instead of addition */
 410                 tei->flags |= TEI_FLAGS_UPDATED;
 411                 *pnum = 0;
 412
 413                 return (0);
 414         }
 415
 416         tb->ent_ptr = NULL;
 417         *pnum = 1;
 418
 419         return (0);
 420 }
 421
 422 static int
 423 ta_prepare_del_cidr(struct ip_fw_chain *ch, struct tentry_info *tei,
 424     void *ta_buf)
 425 {
 426         struct ta_buf_cidr *tb;
 427         struct sockaddr_in sa, mask;
 428         struct sa_in6 sa6, mask6;
 429         in_addr_t addr;
 430         int mlen;
 431
 432         tb = (struct ta_buf_cidr *)ta_buf;
 433         memset(tb, 0, sizeof(struct ta_buf_cidr));
 434
 435         mlen = tei->masklen;
 436
 437         if (tei->subtype == AF_INET) {
 438                 if (mlen > 32)
 439                         return (EINVAL);
 440                 memset(&sa, 0, sizeof(struct sockaddr_in));
 441                 memset(&mask, 0, sizeof(struct sockaddr_in));
 442                 /* Set 'total' structure length */
 443                 KEY_LEN(sa) = KEY_LEN_INET;
 444                 KEY_LEN(mask) = KEY_LEN_INET;
 445                 mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
 446                 addr = *((in_addr_t *)tei->paddr);
 447                 sa.sin_addr.s_addr = addr & mask.sin_addr.s_addr;
 448                 tb->addr.a4.sa = sa;
 449                 tb->addr.a4.ma = mask;
 450                 tb->addr_ptr = (struct sockaddr *)&tb->addr.a4.sa;
 451                 if (mlen != 32)
 452                         tb->mask_ptr = (struct sockaddr *)&tb->addr.a4.ma;
 453 #ifdef INET6
 454         } else if (tei->subtype == AF_INET6) {
 455                 if (mlen > 128)
 456                         return (EINVAL);
 457                 memset(&sa6, 0, sizeof(struct sa_in6));
 458                 memset(&mask6, 0, sizeof(struct sa_in6));
 459                 /* Set 'total' structure length */
 460                 KEY_LEN(sa6) = KEY_LEN_INET6;
 461                 KEY_LEN(mask6) = KEY_LEN_INET6;
 462                 ipv6_writemask(&mask6.sin6_addr, mlen);
 463                 memcpy(&sa6.sin6_addr, tei->paddr,
 464                     sizeof(struct in6_addr));
 465                 APPLY_MASK(&sa6.sin6_addr, &mask6.sin6_addr);
 466                 tb->addr.a6.sa = sa6;
 467                 tb->addr.a6.ma = mask6;
 468                 tb->addr_ptr = (struct sockaddr *)&tb->addr.a6.sa;
 469                 if (mlen != 128)
 470                         tb->mask_ptr = (struct sockaddr *)&tb->addr.a6.ma;
 471 #endif
 472         } else
 473                 return (EINVAL);
 474
 475         return (0);
 476 }
 477
 478 static int
 479 ta_del_cidr(void *ta_state, struct table_info *ti, struct tentry_info *tei,
 480     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
 481 {
 482         struct radix_node_head *rnh;
 483         struct radix_node *rn;
 484         struct ta_buf_cidr *tb;
 485
 486         tb = (struct ta_buf_cidr *)ta_buf;
 487
 488         if (tei->subtype == AF_INET)
 489                 rnh = ti->state;
 490         else
 491                 rnh = ti->xstate;
 492
 493         rn = rnh->rnh_deladdr(tb->addr_ptr, tb->mask_ptr, rnh);
 494
 495         tb->ent_ptr = rn;
 496
 497         if (rn == NULL)
 498                 return (ENOENT);
 499
 500         *pnum = 1;
 501
 502         return (0);
 503 }
 504
 505 static void
 506 ta_flush_cidr_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
 507     void *ta_buf)
 508 {
 509         struct ta_buf_cidr *tb;
 510
 511         tb = (struct ta_buf_cidr *)ta_buf;
 512
 513         if (tb->ent_ptr != NULL)
 514                 free(tb->ent_ptr, M_IPFW_TBL);
 515 }
 516
 517 struct table_algo cidr_radix = {
 518         .name           = "cidr:radix",
 519         .type           = IPFW_TABLE_CIDR,
 520         .init           = ta_init_radix,
 521         .destroy        = ta_destroy_radix,
 522         .prepare_add    = ta_prepare_add_cidr,
 523         .prepare_del    = ta_prepare_del_cidr,
 524         .add            = ta_add_cidr,
 525         .del            = ta_del_cidr,
 526         .flush_entry    = ta_flush_cidr_entry,
 527         .foreach        = ta_foreach_radix,
 528         .dump_tentry    = ta_dump_radix_tentry,
 529         .find_tentry    = ta_find_radix_tentry,
 530 };
 531
 532
 533 /*
 534  * cidr:hash cmds
 535  *
 536  *
 537  * ti->data:
 538  * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
 539  * [        8][        8[          8][         8]
 540  *
 541  * inv.mask4: 32 - mask
 542  * inv.mask6:
 543  * 1) _slow lookup: mask
 544  * 2) _aligned: (128 - mask) / 8
 545  * 3) _64: 8
 546  */
 547
 548 struct chashentry;
 549
 550 SLIST_HEAD(chashbhead, chashentry);
 551
 552 struct chash_cfg {
 553         struct chashbhead *head4;
 554         struct chashbhead *head6;
 555         size_t  size4;
 556         size_t  size6;
 557         size_t  items;
 558         uint8_t mask4;
 559         uint8_t mask6;
 560 };
 561
 562 struct chashentry {
 563         SLIST_ENTRY(chashentry) next;
 564         uint32_t        value;
 565         uint32_t        type;
 566         union {
 567                 uint32_t        a4;     /* Host format */
 568                 struct in6_addr a6;     /* Network format */
 569         } a;
 570 };
 571
 572 static __inline uint32_t
 573 hash_ip(uint32_t addr, int hsize)
 574 {
 575
 576         return (addr % (hsize - 1));
 577 }
 578
 579 static __inline uint32_t
 580 hash_ip6(struct in6_addr *addr6, int hsize)
 581 {
 582         uint32_t i;
 583
 584         i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1] ^
 585             addr6->s6_addr32[2] ^ addr6->s6_addr32[3];
 586
 587         return (i % (hsize - 1));
 588 }
 589
 590
 591 static __inline uint16_t
 592 hash_ip64(struct in6_addr *addr6, int hsize)
 593 {
 594         uint32_t i;
 595
 596         i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1];
 597
 598         return (i % (hsize - 1));
 599 }
 600
 601
 602 static __inline uint32_t
 603 hash_ip6_slow(struct in6_addr *addr6, void *key, int mask, int hsize)
 604 {
 605         struct in6_addr mask6;
 606
 607         ipv6_writemask(&mask6, mask);
 608         memcpy(addr6, key, sizeof(struct in6_addr));
 609         APPLY_MASK(addr6, &mask6);
 610         return (hash_ip6(addr6, hsize));
 611 }
 612
 613 static __inline uint32_t
 614 hash_ip6_al(struct in6_addr *addr6, void *key, int mask, int hsize)
 615 {
 616         uint64_t *paddr;
 617
 618         paddr = (uint64_t *)addr6;
 619         *paddr = 0;
 620         *(paddr + 1) = 0;
 621         memcpy(addr6, key, mask);
 622         return (hash_ip6(addr6, hsize));
 623 }
 624
 625 static int
 626 ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
 627     uint32_t *val)
 628 {
 629         struct chashbhead *head;
 630         struct chashentry *ent;
 631         uint16_t hash, hsize;
 632         uint8_t imask;
 633
 634         if (keylen == sizeof(in_addr_t)) {
 635                 head = (struct chashbhead *)ti->state;
 636                 imask = ti->data >> 24;
 637                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 638                 uint32_t a;
 639                 a = ntohl(*((in_addr_t *)key));
 640                 a = a >> imask;
 641                 hash = hash_ip(a, hsize);
 642                 SLIST_FOREACH(ent, &head[hash], next) {
 643                         if (ent->a.a4 == a) {
 644                                 *val = ent->value;
 645                                 return (1);
 646                         }
 647                 }
 648         } else {
 649                 /* IPv6: worst scenario: non-round mask */
 650                 struct in6_addr addr6;
 651                 head = (struct chashbhead *)ti->xstate;
 652                 imask = (ti->data & 0xFF0000) >> 16;
 653                 hsize = 1 << (ti->data & 0xFF);
 654                 hash = hash_ip6_slow(&addr6, key, imask, hsize);
 655                 SLIST_FOREACH(ent, &head[hash], next) {
 656                         if (memcmp(&ent->a.a6, &addr6, 16) == 0) {
 657                                 *val = ent->value;
 658                                 return (1);
 659                         }
 660                 }
 661         }
 662
 663         return (0);
 664 }
 665
 666 static int
 667 ta_lookup_chash_aligned(struct table_info *ti, void *key, uint32_t keylen,
 668     uint32_t *val)
 669 {
 670         struct chashbhead *head;
 671         struct chashentry *ent;
 672         uint16_t hash, hsize;
 673         uint8_t imask;
 674
 675         if (keylen == sizeof(in_addr_t)) {
 676                 head = (struct chashbhead *)ti->state;
 677                 imask = ti->data >> 24;
 678                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 679                 uint32_t a;
 680                 a = ntohl(*((in_addr_t *)key));
 681                 a = a >> imask;
 682                 hash = hash_ip(a, hsize);
 683                 SLIST_FOREACH(ent, &head[hash], next) {
 684                         if (ent->a.a4 == a) {
 685                                 *val = ent->value;
 686                                 return (1);
 687                         }
 688                 }
 689         } else {
 690                 /* IPv6: aligned to 8bit mask */
 691                 struct in6_addr addr6;
 692                 uint64_t *paddr, *ptmp;
 693                 head = (struct chashbhead *)ti->xstate;
 694                 imask = (ti->data & 0xFF0000) >> 16;
 695                 hsize = 1 << (ti->data & 0xFF);
 696
 697                 hash = hash_ip6_al(&addr6, key, imask, hsize);
 698                 paddr = (uint64_t *)&addr6;
 699                 SLIST_FOREACH(ent, &head[hash], next) {
 700                         ptmp = (uint64_t *)&ent->a.a6;
 701                         if (paddr[0] == ptmp[0] && paddr[1] == ptmp[1]) {
 702                                 *val = ent->value;
 703                                 return (1);
 704                         }
 705                 }
 706         }
 707
 708         return (0);
 709 }
 710
 711 static int
 712 ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
 713     uint32_t *val)
 714 {
 715         struct chashbhead *head;
 716         struct chashentry *ent;
 717         uint16_t hash, hsize;
 718         uint8_t imask;
 719
 720         if (keylen == sizeof(in_addr_t)) {
 721                 head = (struct chashbhead *)ti->state;
 722                 imask = ti->data >> 24;
 723                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 724                 uint32_t a;
 725                 a = ntohl(*((in_addr_t *)key));
 726                 a = a >> imask;
 727                 hash = hash_ip(a, hsize);
 728                 SLIST_FOREACH(ent, &head[hash], next) {
 729                         if (ent->a.a4 == a) {
 730                                 *val = ent->value;
 731                                 return (1);
 732                         }
 733                 }
 734         } else {
 735                 /* IPv6: /64 */
 736                 uint64_t a6, *paddr;
 737                 head = (struct chashbhead *)ti->xstate;
 738                 paddr = (uint64_t *)key;
 739                 hsize = 1 << (ti->data & 0xFF);
 740                 a6 = *paddr;
 741                 hash = hash_ip64((struct in6_addr *)key, hsize);
 742                 SLIST_FOREACH(ent, &head[hash], next) {
 743                         paddr = (uint64_t *)&ent->a.a6;
 744                         if (a6 == *paddr) {
 745                                 *val = ent->value;
 746                                 return (1);
 747                         }
 748                 }
 749         }
 750
 751         return (0);
 752 }
 753
 754 static int
 755 chash_parse_opts(struct chash_cfg *ccfg, char *data)
 756 {
 757         char *pdel, *pend, *s;
 758         int mask4, mask6;
 759
 760         mask4 = ccfg->mask4;
 761         mask6 = ccfg->mask6;
 762
 763         if (data == NULL)
 764                 return (0);
 765         if ((pdel = strchr(data, ' ')) == NULL)
 766                 return (0);
 767         while (*pdel == ' ')
 768                 pdel++;
 769         if (strncmp(pdel, "masks=", 6) != 0)
 770                 return (EINVAL);
 771         if ((s = strchr(pdel, ' ')) != NULL)
 772                 *s++ = '\0';
 773
 774         pdel += 6;
 775         /* Need /XX[,/YY] */
 776         if (*pdel++ != '/')
 777                 return (EINVAL);
 778         mask4 = strtol(pdel, &pend, 10);
 779         if (*pend == ',') {
 780                 /* ,/YY */
 781                 pdel = pend + 1;
 782                 if (*pdel++ != '/')
 783                         return (EINVAL);
 784                 mask6 = strtol(pdel, &pend, 10);
 785                 if (*pend != '\0')
 786                         return (EINVAL);
 787         } else if (*pend != '\0')
 788                 return (EINVAL);
 789
 790         if (mask4 < 0 || mask4 > 32 || mask6 < 0 || mask6 > 128)
 791                 return (EINVAL);
 792
 793         ccfg->mask4 = mask4;
 794         ccfg->mask6 = mask6;
 795
 796         return (0);
 797 }
 798
 799 static void
 800 ta_print_chash_config(void *ta_state, struct table_info *ti, char *buf,
 801     size_t bufsize)
 802 {
 803         struct chash_cfg *ccfg;
 804
 805         ccfg = (struct chash_cfg *)ta_state;
 806
 807         if (ccfg->mask4 != 32 || ccfg->mask6 != 128)
 808                 snprintf(buf, bufsize, "%s masks=/%d,/%d", "cidr:hash",
 809                     ccfg->mask4, ccfg->mask6);
 810         else
 811                 snprintf(buf, bufsize, "%s", "cidr:hash");
 812 }
 813
 814
 815 /*
 816  * New table.
 817  * We assume 'data' to be either NULL or the following format:
 818  * 'cidr:hash [masks=/32[,/128]]'
 819  */
 820 static int
 821 ta_init_chash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
 822     char *data)
 823 {
 824         int error, i;
 825         int v4, v6;
 826         struct chash_cfg *ccfg;
 827
 828         ccfg = malloc(sizeof(struct chash_cfg), M_IPFW, M_WAITOK | M_ZERO);
 829
 830         ccfg->mask4 = 32;
 831         ccfg->mask6 = 128;
 832
 833         if ((error = chash_parse_opts(ccfg, data)) != 0) {
 834                 free(ccfg, M_IPFW);
 835                 return (error);
 836         }
 837
 838         v4 = 7;
 839         v6 = 7;
 840         ccfg->size4 = 1 << v4;
 841         ccfg->size6 = 1 << v6;
 842
 843         ccfg->head4 = malloc(sizeof(struct chashbhead) * ccfg->size4, M_IPFW,
 844             M_WAITOK | M_ZERO);
 845         ccfg->head6 = malloc(sizeof(struct chashbhead) * ccfg->size6, M_IPFW,
 846             M_WAITOK | M_ZERO);
 847         for (i = 0; i < ccfg->size4; i++)
 848                 SLIST_INIT(&ccfg->head4[i]);
 849         for (i = 0; i < ccfg->size6; i++)
 850                 SLIST_INIT(&ccfg->head6[i]);
 851
 852
 853         *ta_state = ccfg;
 854         ti->state = ccfg->head4;
 855         ti->xstate = ccfg->head6;
 856
 857         /* Store data depending on v6 mask length */
 858         if (ccfg->mask6 == 64) {
 859                 ti->data = (32 - ccfg->mask4) << 24 | (128 - ccfg->mask6) << 16 |
 860                     v4 << 8 | v6;
 861                 ti->lookup = ta_lookup_chash_64;
 862         } else if ((ccfg->mask6  % 8) == 0) {
 863                 ti->data = (32 - ccfg->mask4) << 24 |
 864                     ccfg->mask6 << 13 | v4 << 8 | v6;
 865                 ti->lookup = ta_lookup_chash_aligned;
 866         } else {
 867                 /* don't do that! */
 868                 ti->data = (32 - ccfg->mask4) << 24 |
 869                     ccfg->mask6 << 16 | v4 << 8 | v6;
 870                 ti->lookup = ta_lookup_chash_slow;
 871         }
 872
 873         return (0);
 874 }
 875
 876 static void
 877 ta_destroy_chash(void *ta_state, struct table_info *ti)
 878 {
 879         struct chash_cfg *ccfg;
 880         struct chashentry *ent, *ent_next;
 881         int i;
 882
 883         ccfg = (struct chash_cfg *)ta_state;
 884
 885         for (i = 0; i < ccfg->size4; i++)
 886                 SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
 887                         free(ent, M_IPFW_TBL);
 888
 889         for (i = 0; i < ccfg->size6; i++)
 890                 SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
 891                         free(ent, M_IPFW_TBL);
 892
 893         free(ccfg->head4, M_IPFW);
 894         free(ccfg->head6, M_IPFW);
 895 }
 896
 897 static int
 898 ta_dump_chash_tentry(void *ta_state, struct table_info *ti, void *e,
 899     ipfw_obj_tentry *tent)
 900 {
 901         struct chash_cfg *ccfg;
 902         struct chashentry *ent;
 903
 904         ccfg = (struct chash_cfg *)ta_state;
 905         ent = (struct chashentry *)e;
 906
 907         if (ent->type == AF_INET) {
 908                 tent->k.addr.s_addr = htonl(ent->a.a4 << (32 - ccfg->mask4));
 909                 tent->masklen = ccfg->mask4;
 910                 tent->subtype = AF_INET;
 911                 tent->value = ent->value;
 912 #ifdef INET6
 913         } else {
 914                 memcpy(&tent->k, &ent->a.a6, sizeof(struct in6_addr));
 915                 tent->masklen = ccfg->mask6;
 916                 tent->subtype = AF_INET6;
 917                 tent->value = ent->value;
 918 #endif
 919         }
 920
 921         return (0);
 922 }
 923
 924 static int
 925 ta_find_chash_tentry(void *ta_state, struct table_info *ti, void *key,
 926     uint32_t keylen, ipfw_obj_tentry *tent)
 927 {
 928 #if 0
 929         struct radix_node_head *rnh;
 930         void *e;
 931
 932         e = NULL;
 933         if (keylen == sizeof(in_addr_t)) {
 934                 struct sockaddr_in sa;
 935                 KEY_LEN(sa) = KEY_LEN_INET;
 936                 sa.sin_addr.s_addr = *((in_addr_t *)key);
 937                 rnh = (struct radix_node_head *)ti->state;
 938                 e = rnh->rnh_matchaddr(&sa, rnh);
 939         } else {
 940                 struct sa_in6 sa6;
 941                 KEY_LEN(sa6) = KEY_LEN_INET6;
 942                 memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
 943                 rnh = (struct radix_node_head *)ti->xstate;
 944                 e = rnh->rnh_matchaddr(&sa6, rnh);
 945         }
 946
 947         if (e != NULL) {
 948                 ta_dump_radix_tentry(ta_state, ti, e, tent);
 949                 return (0);
 950         }
 951 #endif
 952         return (ENOENT);
 953 }
 954
 955 static void
 956 ta_foreach_chash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
 957     void *arg)
 958 {
 959         struct chash_cfg *ccfg;
 960         struct chashentry *ent, *ent_next;
 961         int i;
 962
 963         ccfg = (struct chash_cfg *)ta_state;
 964
 965         for (i = 0; i < ccfg->size4; i++)
 966                 SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
 967                         f(ent, arg);
 968
 969         for (i = 0; i < ccfg->size6; i++)
 970                 SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
 971                         f(ent, arg);
 972 }
 973
 974
 975 struct ta_buf_chash
 976 {
 977         void *ent_ptr;
 978         int type;
 979         union {
 980                 uint32_t        a4;
 981                 struct in6_addr a6;
 982         } a;
 983 };
 984
 985 static int
 986 ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
 987     void *ta_buf)
 988 {
 989         struct ta_buf_chash *tb;
 990         struct chashentry *ent;
 991         int mlen;
 992         struct in6_addr mask6;
 993
 994         tb = (struct ta_buf_chash *)ta_buf;
 995         memset(tb, 0, sizeof(struct ta_buf_chash));
 996
 997         mlen = tei->masklen;
 998
 999         if (tei->subtype == AF_INET) {
1000 #ifdef INET
1001                 if (mlen > 32)
1002                         return (EINVAL);
1003                 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1004                 ent->value = tei->value;
1005                 ent->type = AF_INET;
1006
1007                 /* Calculate mask */
1008                 ent->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1009                 tb->ent_ptr = ent;
1010 #endif
1011 #ifdef INET6
1012         } else if (tei->subtype == AF_INET6) {
1013                 /* IPv6 case */
1014                 if (mlen > 128)
1015                         return (EINVAL);
1016                 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1017                 ent->value = tei->value;
1018                 ent->type = AF_INET6;
1019
1020                 ipv6_writemask(&mask6, mlen);
1021                 memcpy(&ent->a.a6, tei->paddr, sizeof(struct in6_addr));
1022                 APPLY_MASK(&ent->a.a6, &mask6);
1023                 tb->ent_ptr = ent;
1024 #endif
1025         } else {
1026                 /* Unknown CIDR type */
1027                 return (EINVAL);
1028         }
1029
1030         return (0);
1031 }
1032
1033 static int
1034 ta_add_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1035     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1036 {
1037         struct chash_cfg *ccfg;
1038         struct chashbhead *head;
1039         struct chashentry *ent, *tmp;
1040         struct ta_buf_chash *tb;
1041         int exists;
1042         uint32_t hash;
1043
1044         ccfg = (struct chash_cfg *)ta_state;
1045         tb = (struct ta_buf_chash *)ta_buf;
1046         ent = (struct chashentry *)tb->ent_ptr;
1047         hash = 0;
1048         exists = 0;
1049
1050         if (tei->subtype == AF_INET) {
1051                 if (tei->masklen != ccfg->mask4)
1052                         return (EINVAL);
1053                 head = ccfg->head4;
1054                 hash = hash_ip(ent->a.a4, ccfg->size4);
1055                 /* Check for existence */
1056                 SLIST_FOREACH(tmp, &head[hash], next) {
1057                         if (tmp->a.a4 == ent->a.a4) {
1058                                 exists = 1;
1059                                 break;
1060                         }
1061                 }
1062         } else {
1063                 if (tei->masklen != ccfg->mask6)
1064                         return (EINVAL);
1065                 head = ccfg->head6;
1066                 if (tei->masklen == 64)
1067                         hash = hash_ip64(&ent->a.a6, ccfg->size6);
1068                 else
1069                         hash = hash_ip6(&ent->a.a6, ccfg->size6);
1070                 /* Check for existence */
1071                 SLIST_FOREACH(tmp, &head[hash], next) {
1072                         if (memcmp(&tmp->a.a6, &ent->a.a6, 16)) {
1073                                 exists = 1;
1074                                 break;
1075                         }
1076                 }
1077         }
1078
1079         if (exists == 1) {
1080                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1081                         return (EEXIST);
1082                 /* Record already exists. Update value if we're asked to */
1083                 tmp->value = tei->value;
1084                 /* Indicate that update has happened instead of addition */
1085                 tei->flags |= TEI_FLAGS_UPDATED;
1086                 *pnum = 0;
1087         } else {
1088                 SLIST_INSERT_HEAD(&head[hash], ent, next);
1089                 tb->ent_ptr = NULL;
1090                 *pnum = 1;
1091         }
1092
1093         return (0);
1094 }
1095
1096 static int
1097 ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1098     void *ta_buf)
1099 {
1100         struct ta_buf_chash *tb;
1101         int mlen;
1102         struct in6_addr mask6;
1103
1104         tb = (struct ta_buf_chash *)ta_buf;
1105         memset(tb, 0, sizeof(struct ta_buf_chash));
1106
1107         mlen = tei->masklen;
1108
1109         if (tei->subtype == AF_INET) {
1110 #ifdef INET
1111                 if (mlen > 32)
1112                         return (EINVAL);
1113                 tb->type = AF_INET;
1114
1115                 /* Calculate masked address */
1116                 tb->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1117 #endif
1118 #ifdef INET6
1119         } else if (tei->subtype == AF_INET6) {
1120                 /* IPv6 case */
1121                 if (mlen > 128)
1122                         return (EINVAL);
1123                 tb->type = AF_INET6;
1124
1125                 ipv6_writemask(&mask6, mlen);
1126                 memcpy(&tb->a.a6, tei->paddr, sizeof(struct in6_addr));
1127                 APPLY_MASK(&tb->a.a6, &mask6);
1128 #endif
1129         } else {
1130                 /* Unknown CIDR type */
1131                 return (EINVAL);
1132         }
1133
1134         return (0);
1135 }
1136
1137 static int
1138 ta_del_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1139     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1140 {
1141         struct chash_cfg *ccfg;
1142         struct chashbhead *head;
1143         struct chashentry *ent, *tmp_next;
1144         struct ta_buf_chash *tb;
1145         uint32_t hash;
1146
1147         ccfg = (struct chash_cfg *)ta_state;
1148         tb = (struct ta_buf_chash *)ta_buf;
1149
1150         if (tei->subtype == AF_INET) {
1151                 if (tei->masklen != ccfg->mask4)
1152                         return (EINVAL);
1153                 head = ccfg->head4;
1154                 hash = hash_ip(tb->a.a4, ccfg->size4);
1155
1156                 SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1157                         if (ent->a.a4 == tb->a.a4) {
1158                                 SLIST_REMOVE(&head[hash], ent, chashentry,next);
1159                                 *pnum = 1;
1160                                 return (0);
1161                         }
1162                 }
1163         } else {
1164                 if (tei->masklen != ccfg->mask6)
1165                         return (EINVAL);
1166                 head = ccfg->head6;
1167                 if (tei->masklen == 64)
1168                         hash = hash_ip64(&tb->a.a6, ccfg->size6);
1169                 else
1170                         hash = hash_ip6(&tb->a.a6, ccfg->size6);
1171
1172                 SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1173                         if (memcmp(&ent->a.a6, &tb->a.a6, 16)) {
1174                                 SLIST_REMOVE(&head[hash], ent, chashentry,next);
1175                                 *pnum = 1;
1176                                 return (0);
1177                         }
1178                 }
1179         }
1180
1181         return (ENOENT);
1182 }
1183
1184 static void
1185 ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1186     void *ta_buf)
1187 {
1188         struct ta_buf_chash *tb;
1189
1190         tb = (struct ta_buf_chash *)ta_buf;
1191
1192         if (tb->ent_ptr != NULL)
1193                 free(tb->ent_ptr, M_IPFW_TBL);
1194 }
1195
1196 struct table_algo cidr_hash = {
1197         .name           = "cidr:hash",
1198         .type           = IPFW_TABLE_CIDR,
1199         .init           = ta_init_chash,
1200         .destroy        = ta_destroy_chash,
1201         .prepare_add    = ta_prepare_add_chash,
1202         .prepare_del    = ta_prepare_del_chash,
1203         .add            = ta_add_chash,
1204         .del            = ta_del_chash,
1205         .flush_entry    = ta_flush_chash_entry,
1206         .foreach        = ta_foreach_chash,
1207         .dump_tentry    = ta_dump_chash_tentry,
1208         .find_tentry    = ta_find_chash_tentry,
1209         .print_config   = ta_print_chash_config,
1210 };
1211
1212
1213 /*
1214  * Iface table cmds.
1215  *
1216  * Implementation:
1217  *
1218  * Runtime part:
1219  * - sorted array of "struct ifidx" pointed by ti->state.
1220  *   Array is allocated with routing up to IFIDX_CHUNK. Only existing
1221  *   interfaces are stored in array, however its allocated size is
1222  *   sufficient to hold all table records if needed.
1223  * - current array size is stored in ti->data
1224  *
1225  * Table data:
1226  * - "struct iftable_cfg" is allocated to store table state (ta_state).
1227  * - All table records are stored inside namedobj instance.
1228  *
1229  */
1230
1231 struct ifidx {
1232         uint16_t        kidx;
1233         uint16_t        spare;
1234         uint32_t        value;
1235 };
1236
1237 struct iftable_cfg;
1238
1239 struct ifentry {
1240         struct named_object     no;
1241         struct ipfw_ifc         ic;
1242         struct iftable_cfg      *icfg;
1243         uint32_t                value;
1244         int                     linked;
1245 };
1246
1247 struct iftable_cfg {
1248         struct namedobj_instance        *ii;
1249         struct ip_fw_chain      *ch;
1250         struct table_info       *ti;
1251         void    *main_ptr;
1252         size_t  size;   /* Number of items allocated in array */
1253         size_t  count;  /* Number of all items */
1254         size_t  used;   /* Number of items _active_ now */
1255 };
1256
1257 #define IFIDX_CHUNK     16
1258
1259 int compare_ifidx(const void *k, const void *v);
1260 static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
1261
1262 int
1263 compare_ifidx(const void *k, const void *v)
1264 {
1265         struct ifidx *ifidx;
1266         uint16_t key;
1267
1268         key = *((uint16_t *)k);
1269         ifidx = (struct ifidx *)v;
1270
1271         if (key < ifidx->kidx)
1272                 return (-1);
1273         else if (key > ifidx->kidx)
1274                 return (1);
1275
1276         return (0);
1277 }
1278
1279 /*
1280  * Adds item @item with key @key into ascending-sorted array @base.
1281  * Assumes @base has enough additional storage.
1282  *
1283  * Returns 1 on success, 0 on duplicate key.
1284  */
1285 static int
1286 badd(const void *key, void *item, void *base, size_t nmemb,
1287     size_t size, int (*compar) (const void *, const void *))
1288 {
1289         int min, max, mid, shift, res;
1290         caddr_t paddr;
1291
1292         if (nmemb == 0) {
1293                 memcpy(base, item, size);
1294                 return (1);
1295         }
1296
1297         /* Binary search */
1298         min = 0;
1299         max = nmemb - 1;
1300         mid = 0;
1301         while (min <= max) {
1302                 mid = (min + max) / 2;
1303                 res = compar(key, (const void *)((caddr_t)base + mid * size));
1304                 if (res == 0)
1305                         return (0);
1306
1307                 if (res > 0)
1308                          min = mid + 1;
1309                 else
1310                          max = mid - 1;
1311         }
1312
1313         /* Item not found. */
1314         res = compar(key, (const void *)((caddr_t)base + mid * size));
1315         if (res > 0)
1316                 shift = mid + 1;
1317         else
1318                 shift = mid;
1319
1320         paddr = (caddr_t)base + shift * size;
1321         if (nmemb > shift)
1322                 memmove(paddr + size, paddr, (nmemb - shift) * size);
1323
1324         memcpy(paddr, item, size);
1325
1326         return (1);
1327 }
1328
1329 /*
1330  * Deletes item with key @key from ascending-sorted array @base.
1331  *
1332  * Returns 1 on success, 0 for non-existent key.
1333  */
1334 static int
1335 bdel(const void *key, void *base, size_t nmemb, size_t size,
1336     int (*compar) (const void *, const void *))
1337 {
1338         caddr_t item;
1339         size_t sz;
1340
1341         item = (caddr_t)bsearch(key, base, nmemb, size, compar);
1342
1343         if (item == NULL)
1344                 return (0);
1345
1346         sz = (caddr_t)base + nmemb * size - item;
1347
1348         if (sz > 0)
1349                 memmove(item, item + size, sz);
1350
1351         return (1);
1352 }
1353
1354 static struct ifidx *
1355 ifidx_find(struct table_info *ti, void *key)
1356 {
1357         struct ifidx *ifi;
1358
1359         ifi = bsearch(key, ti->state, ti->data, sizeof(struct ifidx),
1360             compare_ifidx);
1361
1362         return (ifi);
1363 }
1364
1365 static int
1366 ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
1367     uint32_t *val)
1368 {
1369         struct ifidx *ifi;
1370
1371         ifi = ifidx_find(ti, key);
1372
1373         if (ifi != NULL) {
1374                 *val = ifi->value;
1375                 return (1);
1376         }
1377
1378         return (0);
1379 }
1380
1381 static int
1382 ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
1383     char *data)
1384 {
1385         struct iftable_cfg *icfg;
1386
1387         icfg = malloc(sizeof(struct iftable_cfg), M_IPFW, M_WAITOK | M_ZERO);
1388
1389         icfg->ii = ipfw_objhash_create(16);
1390         icfg->main_ptr = malloc(sizeof(struct ifidx) * IFIDX_CHUNK,  M_IPFW,
1391             M_WAITOK | M_ZERO);
1392         icfg->size = IFIDX_CHUNK;
1393         icfg->ch = ch;
1394
1395         *ta_state = icfg;
1396         ti->state = icfg->main_ptr;
1397         ti->lookup = ta_lookup_ifidx;
1398
1399         return (0);
1400 }
1401
1402 /*
1403  * Handle tableinfo @ti pointer change (on table array resize).
1404  */
1405 static void
1406 ta_change_ti_ifidx(void *ta_state, struct table_info *ti)
1407 {
1408         struct iftable_cfg *icfg;
1409
1410         icfg = (struct iftable_cfg *)ta_state;
1411         icfg->ti = ti;
1412 }
1413
1414 static void
1415 destroy_ifidx_locked(struct namedobj_instance *ii, struct named_object *no,
1416     void *arg)
1417 {
1418         struct ifentry *ife;
1419         struct ip_fw_chain *ch;
1420
1421         ch = (struct ip_fw_chain *)arg;
1422         ife = (struct ifentry *)no;
1423
1424         ipfw_iface_del_notify(ch, &ife->ic);
1425         free(ife, M_IPFW_TBL);
1426 }
1427
1428
1429 /*
1430  * Destroys table @ti
1431  */
1432 static void
1433 ta_destroy_ifidx(void *ta_state, struct table_info *ti)
1434 {
1435         struct iftable_cfg *icfg;
1436         struct ip_fw_chain *ch;
1437
1438         icfg = (struct iftable_cfg *)ta_state;
1439         ch = icfg->ch;
1440
1441         if (icfg->main_ptr != NULL)
1442                 free(icfg->main_ptr, M_IPFW);
1443
1444         ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
1445
1446         ipfw_objhash_destroy(icfg->ii);
1447
1448         free(icfg, M_IPFW);
1449 }
1450
1451 struct ta_buf_ifidx
1452 {
1453         struct ifentry *ife;
1454         uint32_t value;
1455 };
1456
1457 /*
1458  * Prepare state to add to the table:
1459  * allocate ifentry and reference needed interface.
1460  */
1461 static int
1462 ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1463     void *ta_buf)
1464 {
1465         struct ta_buf_ifidx *tb;
1466         char *ifname;
1467         struct ifentry *ife;
1468
1469         tb = (struct ta_buf_ifidx *)ta_buf;
1470         memset(tb, 0, sizeof(struct ta_buf_ifidx));
1471
1472         /* Check if string is terminated */
1473         ifname = (char *)tei->paddr;
1474         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1475                 return (EINVAL);
1476
1477         ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
1478         ife->value = tei->value;
1479         ife->ic.cb = if_notifier;
1480         ife->ic.cbdata = ife;
1481
1482         if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0)
1483                 return (EINVAL);
1484
1485         /* Use ipfw_iface 'ifname' field as stable storage */
1486         ife->no.name = ife->ic.iface->ifname;
1487
1488         tb->ife = ife;
1489
1490         return (0);
1491 }
1492
1493 static int
1494 ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1495     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1496 {
1497         struct iftable_cfg *icfg;
1498         struct ifentry *ife, *tmp;
1499         struct ta_buf_ifidx *tb;
1500         struct ipfw_iface *iif;
1501         struct ifidx *ifi;
1502         char *ifname;
1503
1504         tb = (struct ta_buf_ifidx *)ta_buf;
1505         ifname = (char *)tei->paddr;
1506         icfg = (struct iftable_cfg *)ta_state;
1507         ife = tb->ife;
1508
1509         ife->icfg = icfg;
1510
1511         tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1512
1513         if (tmp != NULL) {
1514                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1515                         return (EEXIST);
1516
1517                 /* We need to update value */
1518                 iif = tmp->ic.iface;
1519                 tmp->value = ife->value;
1520
1521                 if (iif->resolved != 0) {
1522                         /* We need to update runtime value, too */
1523                         ifi = ifidx_find(ti, &iif->ifindex);
1524                         ifi->value = ife->value;
1525                 }
1526
1527                 /* Indicate that update has happened instead of addition */
1528                 tei->flags |= TEI_FLAGS_UPDATED;
1529                 *pnum = 0;
1530                 return (0);
1531         }
1532
1533         /* Link to internal list */
1534         ipfw_objhash_add(icfg->ii, &ife->no);
1535
1536         /* Link notifier (possible running its callback) */
1537         ipfw_iface_add_notify(icfg->ch, &ife->ic);
1538         icfg->count++;
1539
1540         if (icfg->count + 1 == icfg->size) {
1541                 /* Notify core we need to grow */
1542                 *pflags = icfg->size + IFIDX_CHUNK;
1543         }
1544
1545         tb->ife = NULL;
1546         *pnum = 1;
1547
1548         return (0);
1549 }
1550
1551 /*
1552  * Prepare to delete key from table.
1553  * Do basic interface name checks.
1554  */
1555 static int
1556 ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1557     void *ta_buf)
1558 {
1559         struct ta_buf_ifidx *tb;
1560         char *ifname;
1561
1562         tb = (struct ta_buf_ifidx *)ta_buf;
1563         memset(tb, 0, sizeof(struct ta_buf_ifidx));
1564
1565         /* Check if string is terminated */
1566         ifname = (char *)tei->paddr;
1567         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1568                 return (EINVAL);
1569
1570         return (0);
1571 }
1572
1573 /*
1574  * Remove key from both configuration list and
1575  * runtime array. Removed interface notification.
1576  */
1577 static int
1578 ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1579     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1580 {
1581         struct iftable_cfg *icfg;
1582         struct ifentry *ife;
1583         struct ta_buf_ifidx *tb;
1584         char *ifname;
1585         uint16_t ifindex;
1586         int res;
1587
1588         tb = (struct ta_buf_ifidx *)ta_buf;
1589         ifname = (char *)tei->paddr;
1590         icfg = (struct iftable_cfg *)ta_state;
1591         ife = tb->ife;
1592
1593         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1594
1595         if (ife == NULL)
1596                 return (ENOENT);
1597
1598         if (ife->linked != 0) {
1599                 /* We have to remove item from runtime */
1600                 ifindex = ife->ic.iface->ifindex;
1601
1602                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
1603                     sizeof(struct ifidx), compare_ifidx);
1604
1605                 KASSERT(res == 1, ("index %d does not exist", ifindex));
1606                 icfg->used--;
1607                 ti->data = icfg->used;
1608                 ife->linked = 0;
1609         }
1610
1611         /* Unlink from local list */
1612         ipfw_objhash_del(icfg->ii, &ife->no);
1613         /* Unlink notifier */
1614         ipfw_iface_del_notify(icfg->ch, &ife->ic);
1615
1616         icfg->count--;
1617
1618         tb->ife = ife;
1619         *pnum = 1;
1620
1621         return (0);
1622 }
1623
1624 /*
1625  * Flush deleted entry.
1626  * Drops interface reference and frees entry.
1627  */
1628 static void
1629 ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1630     void *ta_buf)
1631 {
1632         struct ta_buf_ifidx *tb;
1633
1634         tb = (struct ta_buf_ifidx *)ta_buf;
1635
1636         if (tb->ife != NULL) {
1637                 /* Unlink first */
1638                 ipfw_iface_unref(ch, &tb->ife->ic);
1639                 free(tb->ife, M_IPFW_TBL);
1640         }
1641 }
1642
1643
1644 /*
1645  * Handle interface announce/withdrawal for particular table.
1646  * Every real runtime array modification happens here.
1647  */
1648 static void
1649 if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
1650 {
1651         struct ifentry *ife;
1652         struct ifidx ifi;
1653         struct iftable_cfg *icfg;
1654         struct table_info *ti;
1655         int res;
1656
1657         ife = (struct ifentry *)cbdata;
1658         icfg = ife->icfg;
1659         ti = icfg->ti;
1660
1661         KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
1662
1663         if (ife->linked == 0 && ifindex != 0) {
1664                 /* Interface announce */
1665                 ifi.kidx = ifindex;
1666                 ifi.spare = 0;
1667                 ifi.value = ife->value;
1668                 res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used,
1669                     sizeof(struct ifidx), compare_ifidx);
1670                 KASSERT(res == 1, ("index %d already exists", ifindex));
1671                 icfg->used++;
1672                 ti->data = icfg->used;
1673                 ife->linked = 1;
1674         } else if (ife->linked != 0 && ifindex == 0) {
1675                 /* Interface withdrawal */
1676                 ifindex = ife->ic.iface->ifindex;
1677
1678                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
1679                     sizeof(struct ifidx), compare_ifidx);
1680
1681                 KASSERT(res == 1, ("index %d does not exist", ifindex));
1682                 icfg->used--;
1683                 ti->data = icfg->used;
1684                 ife->linked = 0;
1685         }
1686 }
1687
1688
1689 /*
1690  * Table growing callbacks.
1691  */
1692
1693 struct mod_ifidx {
1694         void    *main_ptr;
1695         size_t  size;
1696 };
1697
1698 /*
1699  * Allocate ned, larger runtime ifidx array.
1700  */
1701 static int
1702 ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
1703 {
1704         struct mod_ifidx *mi;
1705
1706         mi = (struct mod_ifidx *)ta_buf;
1707
1708         memset(mi, 0, sizeof(struct mod_ifidx));
1709         mi->size = *pflags;
1710         mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
1711             M_WAITOK | M_ZERO);
1712
1713         return (0);
1714 }
1715
1716 /*
1717  * Copy data from old runtime array to new one.
1718  */
1719 static int
1720 ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1721     uint64_t *pflags)
1722 {
1723         struct mod_ifidx *mi;
1724         struct iftable_cfg *icfg;
1725
1726         mi = (struct mod_ifidx *)ta_buf;
1727         icfg = (struct iftable_cfg *)ta_state;
1728
1729         /* Check if we still need to grow array */
1730         if (icfg->size >= mi->size) {
1731                 *pflags = 0;
1732                 return (0);
1733         }
1734
1735         memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
1736
1737         return (0);
1738 }
1739
1740 /*
1741  * Switch old & new arrays.
1742  */
1743 static int
1744 ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1745     uint64_t pflags)
1746 {
1747         struct mod_ifidx *mi;
1748         struct iftable_cfg *icfg;
1749         void *old_ptr;
1750
1751         mi = (struct mod_ifidx *)ta_buf;
1752         icfg = (struct iftable_cfg *)ta_state;
1753
1754         old_ptr = icfg->main_ptr;
1755         icfg->main_ptr = mi->main_ptr;
1756         icfg->size = mi->size;
1757         ti->state = icfg->main_ptr;
1758
1759         mi->main_ptr = old_ptr;
1760
1761         return (0);
1762 }
1763
1764 /*
1765  * Free unneded array.
1766  */
1767 static void
1768 ta_flush_mod_ifidx(void *ta_buf)
1769 {
1770         struct mod_ifidx *mi;
1771
1772         mi = (struct mod_ifidx *)ta_buf;
1773         if (mi->main_ptr != NULL)
1774                 free(mi->main_ptr, M_IPFW);
1775 }
1776
1777 static int
1778 ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
1779     ipfw_obj_tentry *tent)
1780 {
1781         struct ifentry *ife;
1782
1783         ife = (struct ifentry *)e;
1784
1785         tent->masklen = 8 * IF_NAMESIZE;
1786         memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
1787         tent->value = ife->value;
1788
1789         return (0);
1790 }
1791
1792 static int
1793 ta_find_ifidx_tentry(void *ta_state, struct table_info *ti, void *key,
1794     uint32_t keylen, ipfw_obj_tentry *tent)
1795 {
1796         struct iftable_cfg *icfg;
1797         struct ifentry *ife;
1798         char *ifname;
1799
1800         icfg = (struct iftable_cfg *)ta_state;
1801         ifname = (char *)key;
1802
1803         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1804                 return (EINVAL);
1805
1806         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1807
1808         if (ife != NULL) {
1809                 ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
1810                 return (0);
1811         }
1812
1813         return (ENOENT);
1814 }
1815
1816 struct wa_ifidx {
1817         ta_foreach_f    *f;
1818         void            *arg;
1819 };
1820
1821 static void
1822 foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
1823     void *arg)
1824 {
1825         struct ifentry *ife;
1826         struct wa_ifidx *wa;
1827
1828         ife = (struct ifentry *)no;
1829         wa = (struct wa_ifidx *)arg;
1830
1831         wa->f(ife, wa->arg);
1832 }
1833
1834 static void
1835 ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
1836     void *arg)
1837 {
1838         struct iftable_cfg *icfg;
1839         struct wa_ifidx wa;
1840
1841         icfg = (struct iftable_cfg *)ta_state;
1842
1843         wa.f = f;
1844         wa.arg = arg;
1845
1846         ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
1847 }
1848
1849 struct table_algo iface_idx = {
1850         .name           = "iface:array",
1851         .type           = IPFW_TABLE_INTERFACE,
1852         .init           = ta_init_ifidx,
1853         .destroy        = ta_destroy_ifidx,
1854         .prepare_add    = ta_prepare_add_ifidx,
1855         .prepare_del    = ta_prepare_del_ifidx,
1856         .add            = ta_add_ifidx,
1857         .del            = ta_del_ifidx,
1858         .flush_entry    = ta_flush_ifidx_entry,
1859         .foreach        = ta_foreach_ifidx,
1860         .dump_tentry    = ta_dump_ifidx_tentry,
1861         .find_tentry    = ta_find_ifidx_tentry,
1862         .prepare_mod    = ta_prepare_mod_ifidx,
1863         .fill_mod       = ta_fill_mod_ifidx,
1864         .modify         = ta_modify_ifidx,
1865         .flush_mod      = ta_flush_mod_ifidx,
1866         .change_ti      = ta_change_ti_ifidx,
1867 };
1868
1869 void
1870 ipfw_table_algo_init(struct ip_fw_chain *ch)
1871 {
1872         size_t sz;
1873
1874         /*
1875          * Register all algorithms presented here.
1876          */
1877         sz = sizeof(struct table_algo);
1878         ipfw_add_table_algo(ch, &cidr_radix, sz, &cidr_radix.idx);
1879         ipfw_add_table_algo(ch, &cidr_hash, sz, &cidr_hash.idx);
1880         ipfw_add_table_algo(ch, &iface_idx, sz, &iface_idx.idx);
1881 }
1882
1883 void
1884 ipfw_table_algo_destroy(struct ip_fw_chain *ch)
1885 {
1886
1887         ipfw_del_table_algo(ch, cidr_radix.idx);
1888         ipfw_del_table_algo(ch, cidr_hash.idx);
1889         ipfw_del_table_algo(ch, iface_idx.idx);
1890 }
1891
1892