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         .init           = ta_init_radix,
 520         .destroy        = ta_destroy_radix,
 521         .prepare_add    = ta_prepare_add_cidr,
 522         .prepare_del    = ta_prepare_del_cidr,
 523         .add            = ta_add_cidr,
 524         .del            = ta_del_cidr,
 525         .flush_entry    = ta_flush_cidr_entry,
 526         .foreach        = ta_foreach_radix,
 527         .dump_tentry    = ta_dump_radix_tentry,
 528         .find_tentry    = ta_find_radix_tentry,
 529 };
 530
 531
 532 /*
 533  * cidr:hash cmds
 534  *
 535  *
 536  * ti->data:
 537  * [inv.mask4][inv.mask6][log2hsize4][log2hsize6]
 538  * [        8][        8[          8][         8]
 539  *
 540  * inv.mask4: 32 - mask
 541  * inv.mask6:
 542  * 1) _slow lookup: mask
 543  * 2) _aligned: (128 - mask) / 8
 544  * 3) _64: 8
 545  */
 546
 547 struct chashentry;
 548
 549 SLIST_HEAD(chashbhead, chashentry);
 550
 551 struct chash_cfg {
 552         struct chashbhead *head4;
 553         struct chashbhead *head6;
 554         size_t  size4;
 555         size_t  size6;
 556         size_t  items;
 557         uint8_t mask4;
 558         uint8_t mask6;
 559 };
 560
 561 struct chashentry {
 562         SLIST_ENTRY(chashentry) next;
 563         uint32_t        value;
 564         uint32_t        type;
 565         union {
 566                 uint32_t        a4;     /* Host format */
 567                 struct in6_addr a6;     /* Network format */
 568         } a;
 569 };
 570
 571 static __inline uint32_t
 572 hash_ip(uint32_t addr, int hsize)
 573 {
 574
 575         return (addr % (hsize - 1));
 576 }
 577
 578 static __inline uint32_t
 579 hash_ip6(struct in6_addr *addr6, int hsize)
 580 {
 581         uint32_t i;
 582
 583         i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1] ^
 584             addr6->s6_addr32[2] ^ addr6->s6_addr32[3];
 585
 586         return (i % (hsize - 1));
 587 }
 588
 589
 590 static __inline uint16_t
 591 hash_ip64(struct in6_addr *addr6, int hsize)
 592 {
 593         uint32_t i;
 594
 595         i = addr6->s6_addr32[0] ^ addr6->s6_addr32[1];
 596
 597         return (i % (hsize - 1));
 598 }
 599
 600
 601 static __inline uint32_t
 602 hash_ip6_slow(struct in6_addr *addr6, void *key, int mask, int hsize)
 603 {
 604         struct in6_addr mask6;
 605
 606         ipv6_writemask(&mask6, mask);
 607         memcpy(addr6, key, sizeof(struct in6_addr));
 608         APPLY_MASK(addr6, &mask6);
 609         return (hash_ip6(addr6, hsize));
 610 }
 611
 612 static __inline uint32_t
 613 hash_ip6_al(struct in6_addr *addr6, void *key, int mask, int hsize)
 614 {
 615         uint64_t *paddr;
 616
 617         paddr = (uint64_t *)addr6;
 618         *paddr = 0;
 619         *(paddr + 1) = 0;
 620         memcpy(addr6, key, mask);
 621         return (hash_ip6(addr6, hsize));
 622 }
 623
 624 static int
 625 ta_lookup_chash_slow(struct table_info *ti, void *key, uint32_t keylen,
 626     uint32_t *val)
 627 {
 628         struct chashbhead *head;
 629         struct chashentry *ent;
 630         uint16_t hash, hsize;
 631         uint8_t imask;
 632
 633         if (keylen == sizeof(in_addr_t)) {
 634                 head = (struct chashbhead *)ti->state;
 635                 imask = ti->data >> 24;
 636                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 637                 uint32_t a;
 638                 a = ntohl(*((in_addr_t *)key));
 639                 a = a >> imask;
 640                 hash = hash_ip(a, hsize);
 641                 SLIST_FOREACH(ent, &head[hash], next) {
 642                         if (ent->a.a4 == a) {
 643                                 *val = ent->value;
 644                                 return (1);
 645                         }
 646                 }
 647         } else {
 648                 /* IPv6: worst scenario: non-round mask */
 649                 struct in6_addr addr6;
 650                 head = (struct chashbhead *)ti->xstate;
 651                 imask = (ti->data & 0xFF0000) >> 16;
 652                 hsize = 1 << (ti->data & 0xFF);
 653                 hash = hash_ip6_slow(&addr6, key, imask, hsize);
 654                 SLIST_FOREACH(ent, &head[hash], next) {
 655                         if (memcmp(&ent->a.a6, &addr6, 16) == 0) {
 656                                 *val = ent->value;
 657                                 return (1);
 658                         }
 659                 }
 660         }
 661
 662         return (0);
 663 }
 664
 665 static int
 666 ta_lookup_chash_aligned(struct table_info *ti, void *key, uint32_t keylen,
 667     uint32_t *val)
 668 {
 669         struct chashbhead *head;
 670         struct chashentry *ent;
 671         uint16_t hash, hsize;
 672         uint8_t imask;
 673
 674         if (keylen == sizeof(in_addr_t)) {
 675                 head = (struct chashbhead *)ti->state;
 676                 imask = ti->data >> 24;
 677                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 678                 uint32_t a;
 679                 a = ntohl(*((in_addr_t *)key));
 680                 a = a >> imask;
 681                 hash = hash_ip(a, hsize);
 682                 SLIST_FOREACH(ent, &head[hash], next) {
 683                         if (ent->a.a4 == a) {
 684                                 *val = ent->value;
 685                                 return (1);
 686                         }
 687                 }
 688         } else {
 689                 /* IPv6: aligned to 8bit mask */
 690                 struct in6_addr addr6;
 691                 uint64_t *paddr, *ptmp;
 692                 head = (struct chashbhead *)ti->xstate;
 693                 imask = (ti->data & 0xFF0000) >> 16;
 694                 hsize = 1 << (ti->data & 0xFF);
 695
 696                 hash = hash_ip6_al(&addr6, key, imask, hsize);
 697                 paddr = (uint64_t *)&addr6;
 698                 SLIST_FOREACH(ent, &head[hash], next) {
 699                         ptmp = (uint64_t *)&ent->a.a6;
 700                         if (paddr[0] == ptmp[0] && paddr[1] == ptmp[1]) {
 701                                 *val = ent->value;
 702                                 return (1);
 703                         }
 704                 }
 705         }
 706
 707         return (0);
 708 }
 709
 710 static int
 711 ta_lookup_chash_64(struct table_info *ti, void *key, uint32_t keylen,
 712     uint32_t *val)
 713 {
 714         struct chashbhead *head;
 715         struct chashentry *ent;
 716         uint16_t hash, hsize;
 717         uint8_t imask;
 718
 719         if (keylen == sizeof(in_addr_t)) {
 720                 head = (struct chashbhead *)ti->state;
 721                 imask = ti->data >> 24;
 722                 hsize = 1 << ((ti->data & 0xFFFF) >> 8);
 723                 uint32_t a;
 724                 a = ntohl(*((in_addr_t *)key));
 725                 a = a >> imask;
 726                 hash = hash_ip(a, hsize);
 727                 SLIST_FOREACH(ent, &head[hash], next) {
 728                         if (ent->a.a4 == a) {
 729                                 *val = ent->value;
 730                                 return (1);
 731                         }
 732                 }
 733         } else {
 734                 /* IPv6: /64 */
 735                 uint64_t a6, *paddr;
 736                 head = (struct chashbhead *)ti->xstate;
 737                 paddr = (uint64_t *)key;
 738                 hsize = 1 << (ti->data & 0xFF);
 739                 a6 = *paddr;
 740                 hash = hash_ip64((struct in6_addr *)key, hsize);
 741                 SLIST_FOREACH(ent, &head[hash], next) {
 742                         paddr = (uint64_t *)&ent->a.a6;
 743                         if (a6 == *paddr) {
 744                                 *val = ent->value;
 745                                 return (1);
 746                         }
 747                 }
 748         }
 749
 750         return (0);
 751 }
 752
 753 static int
 754 chash_parse_opts(struct chash_cfg *ccfg, char *data)
 755 {
 756         char *pdel, *pend, *s;
 757         int mask4, mask6;
 758
 759         mask4 = ccfg->mask4;
 760         mask6 = ccfg->mask6;
 761
 762         if (data == NULL)
 763                 return (0);
 764         if ((pdel = strchr(data, ' ')) == NULL)
 765                 return (0);
 766         while (*pdel == ' ')
 767                 pdel++;
 768         if (strncmp(pdel, "masks=", 6) != 0)
 769                 return (EINVAL);
 770         if ((s = strchr(pdel, ' ')) != NULL)
 771                 *s++ = '\0';
 772
 773         pdel += 6;
 774         /* Need /XX[,/YY] */
 775         if (*pdel++ != '/')
 776                 return (EINVAL);
 777         mask4 = strtol(pdel, &pend, 10);
 778         if (*pend == ',') {
 779                 /* ,/YY */
 780                 pdel = pend + 1;
 781                 if (*pdel++ != '/')
 782                         return (EINVAL);
 783                 mask6 = strtol(pdel, &pend, 10);
 784                 if (*pend != '\0')
 785                         return (EINVAL);
 786         } else if (*pend != '\0')
 787                 return (EINVAL);
 788
 789         if (mask4 < 0 || mask4 > 32 || mask6 < 0 || mask6 > 128)
 790                 return (EINVAL);
 791
 792         ccfg->mask4 = mask4;
 793         ccfg->mask6 = mask6;
 794
 795         return (0);
 796 }
 797
 798 static void
 799 ta_print_chash_config(void *ta_state, struct table_info *ti, char *buf,
 800     size_t bufsize)
 801 {
 802         struct chash_cfg *ccfg;
 803
 804         ccfg = (struct chash_cfg *)ta_state;
 805
 806         if (ccfg->mask4 != 32 || ccfg->mask6 != 128)
 807                 snprintf(buf, bufsize, "%s masks=/%d,/%d", "cidr:hash",
 808                     ccfg->mask4, ccfg->mask6);
 809         else
 810                 snprintf(buf, bufsize, "%s", "cidr:hash");
 811 }
 812
 813
 814 /*
 815  * New table.
 816  * We assume 'data' to be either NULL or the following format:
 817  * 'cidr:hash [masks=/32[,/128]]'
 818  */
 819 static int
 820 ta_init_chash(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
 821     char *data)
 822 {
 823         int error, i;
 824         int v4, v6;
 825         struct chash_cfg *ccfg;
 826
 827         ccfg = malloc(sizeof(struct chash_cfg), M_IPFW, M_WAITOK | M_ZERO);
 828
 829         ccfg->mask4 = 32;
 830         ccfg->mask6 = 128;
 831
 832         if ((error = chash_parse_opts(ccfg, data)) != 0) {
 833                 free(ccfg, M_IPFW);
 834                 return (error);
 835         }
 836
 837         v4 = 7;
 838         v6 = 7;
 839         ccfg->size4 = 1 << v4;
 840         ccfg->size6 = 1 << v6;
 841
 842         ccfg->head4 = malloc(sizeof(struct chashbhead) * ccfg->size4, M_IPFW,
 843             M_WAITOK | M_ZERO);
 844         ccfg->head6 = malloc(sizeof(struct chashbhead) * ccfg->size6, M_IPFW,
 845             M_WAITOK | M_ZERO);
 846         for (i = 0; i < ccfg->size4; i++)
 847                 SLIST_INIT(&ccfg->head4[i]);
 848         for (i = 0; i < ccfg->size6; i++)
 849                 SLIST_INIT(&ccfg->head6[i]);
 850
 851
 852         *ta_state = ccfg;
 853         ti->state = ccfg->head4;
 854         ti->xstate = ccfg->head6;
 855
 856         /* Store data depending on v6 mask length */
 857         if (ccfg->mask6 == 64) {
 858                 ti->data = (32 - ccfg->mask4) << 24 | (128 - ccfg->mask6) << 16 |
 859                     v4 << 8 | v6;
 860                 ti->lookup = ta_lookup_chash_64;
 861         } else if ((ccfg->mask6  % 8) == 0) {
 862                 ti->data = (32 - ccfg->mask4) << 24 |
 863                     ccfg->mask6 << 13 | v4 << 8 | v6;
 864                 ti->lookup = ta_lookup_chash_aligned;
 865         } else {
 866                 /* don't do that! */
 867                 ti->data = (32 - ccfg->mask4) << 24 |
 868                     ccfg->mask6 << 16 | v4 << 8 | v6;
 869                 ti->lookup = ta_lookup_chash_slow;
 870         }
 871
 872         return (0);
 873 }
 874
 875 static void
 876 ta_destroy_chash(void *ta_state, struct table_info *ti)
 877 {
 878         struct chash_cfg *ccfg;
 879         struct chashentry *ent, *ent_next;
 880         int i;
 881
 882         ccfg = (struct chash_cfg *)ta_state;
 883
 884         for (i = 0; i < ccfg->size4; i++)
 885                 SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
 886                         free(ent, M_IPFW_TBL);
 887
 888         for (i = 0; i < ccfg->size6; i++)
 889                 SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
 890                         free(ent, M_IPFW_TBL);
 891
 892         free(ccfg->head4, M_IPFW);
 893         free(ccfg->head6, M_IPFW);
 894 }
 895
 896 static int
 897 ta_dump_chash_tentry(void *ta_state, struct table_info *ti, void *e,
 898     ipfw_obj_tentry *tent)
 899 {
 900         struct chash_cfg *ccfg;
 901         struct chashentry *ent;
 902
 903         ccfg = (struct chash_cfg *)ta_state;
 904         ent = (struct chashentry *)e;
 905
 906         if (ent->type == AF_INET) {
 907                 tent->k.addr.s_addr = htonl(ent->a.a4 << (32 - ccfg->mask4));
 908                 tent->masklen = ccfg->mask4;
 909                 tent->subtype = AF_INET;
 910                 tent->value = ent->value;
 911 #ifdef INET6
 912         } else {
 913                 memcpy(&tent->k, &ent->a.a6, sizeof(struct in6_addr));
 914                 tent->masklen = ccfg->mask6;
 915                 tent->subtype = AF_INET6;
 916                 tent->value = ent->value;
 917 #endif
 918         }
 919
 920         return (0);
 921 }
 922
 923 static int
 924 ta_find_chash_tentry(void *ta_state, struct table_info *ti, void *key,
 925     uint32_t keylen, ipfw_obj_tentry *tent)
 926 {
 927 #if 0
 928         struct radix_node_head *rnh;
 929         void *e;
 930
 931         e = NULL;
 932         if (keylen == sizeof(in_addr_t)) {
 933                 struct sockaddr_in sa;
 934                 KEY_LEN(sa) = KEY_LEN_INET;
 935                 sa.sin_addr.s_addr = *((in_addr_t *)key);
 936                 rnh = (struct radix_node_head *)ti->state;
 937                 e = rnh->rnh_matchaddr(&sa, rnh);
 938         } else {
 939                 struct sa_in6 sa6;
 940                 KEY_LEN(sa6) = KEY_LEN_INET6;
 941                 memcpy(&sa6.sin6_addr, key, sizeof(struct in6_addr));
 942                 rnh = (struct radix_node_head *)ti->xstate;
 943                 e = rnh->rnh_matchaddr(&sa6, rnh);
 944         }
 945
 946         if (e != NULL) {
 947                 ta_dump_radix_tentry(ta_state, ti, e, tent);
 948                 return (0);
 949         }
 950 #endif
 951         return (ENOENT);
 952 }
 953
 954 static void
 955 ta_foreach_chash(void *ta_state, struct table_info *ti, ta_foreach_f *f,
 956     void *arg)
 957 {
 958         struct chash_cfg *ccfg;
 959         struct chashentry *ent, *ent_next;
 960         int i;
 961
 962         ccfg = (struct chash_cfg *)ta_state;
 963
 964         for (i = 0; i < ccfg->size4; i++)
 965                 SLIST_FOREACH_SAFE(ent, &ccfg->head4[i], next, ent_next)
 966                         f(ent, arg);
 967
 968         for (i = 0; i < ccfg->size6; i++)
 969                 SLIST_FOREACH_SAFE(ent, &ccfg->head6[i], next, ent_next)
 970                         f(ent, arg);
 971 }
 972
 973
 974 struct ta_buf_chash
 975 {
 976         void *ent_ptr;
 977         int type;
 978         union {
 979                 uint32_t        a4;
 980                 struct in6_addr a6;
 981         } a;
 982 };
 983
 984 static int
 985 ta_prepare_add_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
 986     void *ta_buf)
 987 {
 988         struct ta_buf_chash *tb;
 989         struct chashentry *ent;
 990         int mlen;
 991         struct in6_addr mask6;
 992
 993         tb = (struct ta_buf_chash *)ta_buf;
 994         memset(tb, 0, sizeof(struct ta_buf_chash));
 995
 996         mlen = tei->masklen;
 997
 998         if (tei->subtype == AF_INET) {
 999 #ifdef INET
1000                 if (mlen > 32)
1001                         return (EINVAL);
1002                 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1003                 ent->value = tei->value;
1004                 ent->type = AF_INET;
1005
1006                 /* Calculate mask */
1007                 ent->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1008                 tb->ent_ptr = ent;
1009 #endif
1010 #ifdef INET6
1011         } else if (tei->subtype == AF_INET6) {
1012                 /* IPv6 case */
1013                 if (mlen > 128)
1014                         return (EINVAL);
1015                 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_WAITOK | M_ZERO);
1016                 ent->value = tei->value;
1017                 ent->type = AF_INET6;
1018
1019                 ipv6_writemask(&mask6, mlen);
1020                 memcpy(&ent->a.a6, tei->paddr, sizeof(struct in6_addr));
1021                 APPLY_MASK(&ent->a.a6, &mask6);
1022                 tb->ent_ptr = ent;
1023 #endif
1024         } else {
1025                 /* Unknown CIDR type */
1026                 return (EINVAL);
1027         }
1028
1029         return (0);
1030 }
1031
1032 static int
1033 ta_add_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1034     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1035 {
1036         struct chash_cfg *ccfg;
1037         struct chashbhead *head;
1038         struct chashentry *ent, *tmp;
1039         struct ta_buf_chash *tb;
1040         int exists;
1041         uint32_t hash;
1042
1043         ccfg = (struct chash_cfg *)ta_state;
1044         tb = (struct ta_buf_chash *)ta_buf;
1045         ent = (struct chashentry *)tb->ent_ptr;
1046         hash = 0;
1047         exists = 0;
1048
1049         if (tei->subtype == AF_INET) {
1050                 if (tei->masklen != ccfg->mask4)
1051                         return (EINVAL);
1052                 head = ccfg->head4;
1053                 hash = hash_ip(ent->a.a4, ccfg->size4);
1054                 /* Check for existence */
1055                 SLIST_FOREACH(tmp, &head[hash], next) {
1056                         if (tmp->a.a4 == ent->a.a4) {
1057                                 exists = 1;
1058                                 break;
1059                         }
1060                 }
1061         } else {
1062                 if (tei->masklen != ccfg->mask6)
1063                         return (EINVAL);
1064                 head = ccfg->head6;
1065                 if (tei->masklen == 64)
1066                         hash = hash_ip64(&ent->a.a6, ccfg->size6);
1067                 else
1068                         hash = hash_ip6(&ent->a.a6, ccfg->size6);
1069                 /* Check for existence */
1070                 SLIST_FOREACH(tmp, &head[hash], next) {
1071                         if (memcmp(&tmp->a.a6, &ent->a.a6, 16)) {
1072                                 exists = 1;
1073                                 break;
1074                         }
1075                 }
1076         }
1077
1078         if (exists == 1) {
1079                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1080                         return (EEXIST);
1081                 /* Record already exists. Update value if we're asked to */
1082                 tmp->value = tei->value;
1083                 /* Indicate that update has happened instead of addition */
1084                 tei->flags |= TEI_FLAGS_UPDATED;
1085                 *pnum = 0;
1086         } else {
1087                 SLIST_INSERT_HEAD(&head[hash], ent, next);
1088                 tb->ent_ptr = NULL;
1089                 *pnum = 1;
1090         }
1091
1092         return (0);
1093 }
1094
1095 static int
1096 ta_prepare_del_chash(struct ip_fw_chain *ch, struct tentry_info *tei,
1097     void *ta_buf)
1098 {
1099         struct ta_buf_chash *tb;
1100         int mlen;
1101         struct in6_addr mask6;
1102
1103         tb = (struct ta_buf_chash *)ta_buf;
1104         memset(tb, 0, sizeof(struct ta_buf_chash));
1105
1106         mlen = tei->masklen;
1107
1108         if (tei->subtype == AF_INET) {
1109 #ifdef INET
1110                 if (mlen > 32)
1111                         return (EINVAL);
1112                 tb->type = AF_INET;
1113
1114                 /* Calculate masked address */
1115                 tb->a.a4 = ntohl(*((in_addr_t *)tei->paddr)) >> (32 - mlen);
1116 #endif
1117 #ifdef INET6
1118         } else if (tei->subtype == AF_INET6) {
1119                 /* IPv6 case */
1120                 if (mlen > 128)
1121                         return (EINVAL);
1122                 tb->type = AF_INET6;
1123
1124                 ipv6_writemask(&mask6, mlen);
1125                 memcpy(&tb->a.a6, tei->paddr, sizeof(struct in6_addr));
1126                 APPLY_MASK(&tb->a.a6, &mask6);
1127 #endif
1128         } else {
1129                 /* Unknown CIDR type */
1130                 return (EINVAL);
1131         }
1132
1133         return (0);
1134 }
1135
1136 static int
1137 ta_del_chash(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1138     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1139 {
1140         struct chash_cfg *ccfg;
1141         struct chashbhead *head;
1142         struct chashentry *ent, *tmp_next;
1143         struct ta_buf_chash *tb;
1144         uint32_t hash;
1145
1146         ccfg = (struct chash_cfg *)ta_state;
1147         tb = (struct ta_buf_chash *)ta_buf;
1148
1149         if (tei->subtype == AF_INET) {
1150                 if (tei->masklen != ccfg->mask4)
1151                         return (EINVAL);
1152                 head = ccfg->head4;
1153                 hash = hash_ip(tb->a.a4, ccfg->size4);
1154
1155                 SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1156                         if (ent->a.a4 == tb->a.a4) {
1157                                 SLIST_REMOVE(&head[hash], ent, chashentry,next);
1158                                 *pnum = 1;
1159                                 return (0);
1160                         }
1161                 }
1162         } else {
1163                 if (tei->masklen != ccfg->mask6)
1164                         return (EINVAL);
1165                 head = ccfg->head6;
1166                 if (tei->masklen == 64)
1167                         hash = hash_ip64(&tb->a.a6, ccfg->size6);
1168                 else
1169                         hash = hash_ip6(&tb->a.a6, ccfg->size6);
1170
1171                 SLIST_FOREACH_SAFE(ent, &head[hash], next, tmp_next) {
1172                         if (memcmp(&ent->a.a6, &tb->a.a6, 16)) {
1173                                 SLIST_REMOVE(&head[hash], ent, chashentry,next);
1174                                 *pnum = 1;
1175                                 return (0);
1176                         }
1177                 }
1178         }
1179
1180         return (ENOENT);
1181 }
1182
1183 static void
1184 ta_flush_chash_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1185     void *ta_buf)
1186 {
1187         struct ta_buf_chash *tb;
1188
1189         tb = (struct ta_buf_chash *)ta_buf;
1190
1191         if (tb->ent_ptr != NULL)
1192                 free(tb->ent_ptr, M_IPFW_TBL);
1193 }
1194
1195 struct table_algo cidr_hash = {
1196         .name           = "cidr:hash",
1197         .init           = ta_init_chash,
1198         .destroy        = ta_destroy_chash,
1199         .prepare_add    = ta_prepare_add_chash,
1200         .prepare_del    = ta_prepare_del_chash,
1201         .add            = ta_add_chash,
1202         .del            = ta_del_chash,
1203         .flush_entry    = ta_flush_chash_entry,
1204         .foreach        = ta_foreach_chash,
1205         .dump_tentry    = ta_dump_chash_tentry,
1206         .find_tentry    = ta_find_chash_tentry,
1207         .print_config   = ta_print_chash_config,
1208 };
1209
1210
1211 /*
1212  * Iface table cmds.
1213  *
1214  * Implementation:
1215  *
1216  * Runtime part:
1217  * - sorted array of "struct ifidx" pointed by ti->state.
1218  *   Array is allocated with routing up to IFIDX_CHUNK. Only existing
1219  *   interfaces are stored in array, however its allocated size is
1220  *   sufficient to hold all table records if needed.
1221  * - current array size is stored in ti->data
1222  *
1223  * Table data:
1224  * - "struct iftable_cfg" is allocated to store table state (ta_state).
1225  * - All table records are stored inside namedobj instance.
1226  *
1227  */
1228
1229 struct ifidx {
1230         uint16_t        kidx;
1231         uint16_t        spare;
1232         uint32_t        value;
1233 };
1234
1235 struct iftable_cfg;
1236
1237 struct ifentry {
1238         struct named_object     no;
1239         struct ipfw_ifc         ic;
1240         struct iftable_cfg      *icfg;
1241         uint32_t                value;
1242         int                     linked;
1243 };
1244
1245 struct iftable_cfg {
1246         struct namedobj_instance        *ii;
1247         struct ip_fw_chain      *ch;
1248         struct table_info       *ti;
1249         void    *main_ptr;
1250         size_t  size;   /* Number of items allocated in array */
1251         size_t  count;  /* Number of all items */
1252         size_t  used;   /* Number of items _active_ now */
1253 };
1254
1255 #define IFIDX_CHUNK     16
1256
1257 int compare_ifidx(const void *k, const void *v);
1258 static void if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex);
1259
1260 int
1261 compare_ifidx(const void *k, const void *v)
1262 {
1263         struct ifidx *ifidx;
1264         uint16_t key;
1265
1266         key = *((uint16_t *)k);
1267         ifidx = (struct ifidx *)v;
1268
1269         if (key < ifidx->kidx)
1270                 return (-1);
1271         else if (key > ifidx->kidx)
1272                 return (1);
1273
1274         return (0);
1275 }
1276
1277 /*
1278  * Adds item @item with key @key into ascending-sorted array @base.
1279  * Assumes @base has enough additional storage.
1280  *
1281  * Returns 1 on success, 0 on duplicate key.
1282  */
1283 static int
1284 badd(const void *key, void *item, void *base, size_t nmemb,
1285     size_t size, int (*compar) (const void *, const void *))
1286 {
1287         int min, max, mid, shift, res;
1288         caddr_t paddr;
1289
1290         if (nmemb == 0) {
1291                 memcpy(base, item, size);
1292                 return (1);
1293         }
1294
1295         /* Binary search */
1296         min = 0;
1297         max = nmemb - 1;
1298         mid = 0;
1299         while (min <= max) {
1300                 mid = (min + max) / 2;
1301                 res = compar(key, (const void *)((caddr_t)base + mid * size));
1302                 if (res == 0)
1303                         return (0);
1304
1305                 if (res > 0)
1306                          min = mid + 1;
1307                 else
1308                          max = mid - 1;
1309         }
1310
1311         /* Item not found. */
1312         res = compar(key, (const void *)((caddr_t)base + mid * size));
1313         if (res > 0)
1314                 shift = mid + 1;
1315         else
1316                 shift = mid;
1317
1318         paddr = (caddr_t)base + shift * size;
1319         if (nmemb > shift)
1320                 memmove(paddr + size, paddr, (nmemb - shift) * size);
1321
1322         memcpy(paddr, item, size);
1323
1324         return (1);
1325 }
1326
1327 /*
1328  * Deletes item with key @key from ascending-sorted array @base.
1329  *
1330  * Returns 1 on success, 0 for non-existent key.
1331  */
1332 static int
1333 bdel(const void *key, void *base, size_t nmemb, size_t size,
1334     int (*compar) (const void *, const void *))
1335 {
1336         caddr_t item;
1337         size_t sz;
1338
1339         item = (caddr_t)bsearch(key, base, nmemb, size, compar);
1340
1341         if (item == NULL)
1342                 return (0);
1343
1344         sz = (caddr_t)base + nmemb * size - item;
1345
1346         if (sz > 0)
1347                 memmove(item, item + size, sz);
1348
1349         return (1);
1350 }
1351
1352 static struct ifidx *
1353 ifidx_find(struct table_info *ti, void *key)
1354 {
1355         struct ifidx *ifi;
1356
1357         ifi = bsearch(key, ti->state, ti->data, sizeof(struct ifidx),
1358             compare_ifidx);
1359
1360         return (ifi);
1361 }
1362
1363 static int
1364 ta_lookup_ifidx(struct table_info *ti, void *key, uint32_t keylen,
1365     uint32_t *val)
1366 {
1367         struct ifidx *ifi;
1368
1369         ifi = ifidx_find(ti, key);
1370
1371         if (ifi != NULL) {
1372                 *val = ifi->value;
1373                 return (1);
1374         }
1375
1376         return (0);
1377 }
1378
1379 static int
1380 ta_init_ifidx(struct ip_fw_chain *ch, void **ta_state, struct table_info *ti,
1381     char *data)
1382 {
1383         struct iftable_cfg *icfg;
1384
1385         icfg = malloc(sizeof(struct iftable_cfg), M_IPFW, M_WAITOK | M_ZERO);
1386
1387         icfg->ii = ipfw_objhash_create(16);
1388         icfg->main_ptr = malloc(sizeof(struct ifidx) * IFIDX_CHUNK,  M_IPFW,
1389             M_WAITOK | M_ZERO);
1390         icfg->size = IFIDX_CHUNK;
1391         icfg->ch = ch;
1392
1393         *ta_state = icfg;
1394         ti->state = icfg->main_ptr;
1395         ti->lookup = ta_lookup_ifidx;
1396
1397         return (0);
1398 }
1399
1400 /*
1401  * Handle tableinfo @ti pointer change (on table array resize).
1402  */
1403 static void
1404 ta_change_ti_ifidx(void *ta_state, struct table_info *ti)
1405 {
1406         struct iftable_cfg *icfg;
1407
1408         icfg = (struct iftable_cfg *)ta_state;
1409         icfg->ti = ti;
1410 }
1411
1412 static void
1413 destroy_ifidx_locked(struct namedobj_instance *ii, struct named_object *no,
1414     void *arg)
1415 {
1416         struct ifentry *ife;
1417         struct ip_fw_chain *ch;
1418
1419         ch = (struct ip_fw_chain *)arg;
1420         ife = (struct ifentry *)no;
1421
1422         ipfw_iface_del_notify(ch, &ife->ic);
1423         free(ife, M_IPFW_TBL);
1424 }
1425
1426
1427 /*
1428  * Destroys table @ti
1429  */
1430 static void
1431 ta_destroy_ifidx(void *ta_state, struct table_info *ti)
1432 {
1433         struct iftable_cfg *icfg;
1434         struct ip_fw_chain *ch;
1435
1436         icfg = (struct iftable_cfg *)ta_state;
1437         ch = icfg->ch;
1438
1439         if (icfg->main_ptr != NULL)
1440                 free(icfg->main_ptr, M_IPFW);
1441
1442         ipfw_objhash_foreach(icfg->ii, destroy_ifidx_locked, ch);
1443
1444         ipfw_objhash_destroy(icfg->ii);
1445
1446         free(icfg, M_IPFW);
1447 }
1448
1449 struct ta_buf_ifidx
1450 {
1451         struct ifentry *ife;
1452         uint32_t value;
1453 };
1454
1455 /*
1456  * Prepare state to add to the table:
1457  * allocate ifentry and reference needed interface.
1458  */
1459 static int
1460 ta_prepare_add_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1461     void *ta_buf)
1462 {
1463         struct ta_buf_ifidx *tb;
1464         char *ifname;
1465         struct ifentry *ife;
1466
1467         tb = (struct ta_buf_ifidx *)ta_buf;
1468         memset(tb, 0, sizeof(struct ta_buf_ifidx));
1469
1470         /* Check if string is terminated */
1471         ifname = (char *)tei->paddr;
1472         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1473                 return (EINVAL);
1474
1475         ife = malloc(sizeof(struct ifentry), M_IPFW_TBL, M_WAITOK | M_ZERO);
1476         ife->value = tei->value;
1477         ife->ic.cb = if_notifier;
1478         ife->ic.cbdata = ife;
1479
1480         if (ipfw_iface_ref(ch, ifname, &ife->ic) != 0)
1481                 return (EINVAL);
1482
1483         /* Use ipfw_iface 'ifname' field as stable storage */
1484         ife->no.name = ife->ic.iface->ifname;
1485
1486         tb->ife = ife;
1487
1488         return (0);
1489 }
1490
1491 static int
1492 ta_add_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1493     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1494 {
1495         struct iftable_cfg *icfg;
1496         struct ifentry *ife, *tmp;
1497         struct ta_buf_ifidx *tb;
1498         struct ipfw_iface *iif;
1499         struct ifidx *ifi;
1500         char *ifname;
1501
1502         tb = (struct ta_buf_ifidx *)ta_buf;
1503         ifname = (char *)tei->paddr;
1504         icfg = (struct iftable_cfg *)ta_state;
1505         ife = tb->ife;
1506
1507         ife->icfg = icfg;
1508
1509         tmp = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1510
1511         if (tmp != NULL) {
1512                 if ((tei->flags & TEI_FLAGS_UPDATE) == 0)
1513                         return (EEXIST);
1514
1515                 /* We need to update value */
1516                 iif = tmp->ic.iface;
1517                 tmp->value = ife->value;
1518
1519                 if (iif->resolved != 0) {
1520                         /* We need to update runtime value, too */
1521                         ifi = ifidx_find(ti, &iif->ifindex);
1522                         ifi->value = ife->value;
1523                 }
1524
1525                 /* Indicate that update has happened instead of addition */
1526                 tei->flags |= TEI_FLAGS_UPDATED;
1527                 *pnum = 0;
1528                 return (0);
1529         }
1530
1531         /* Link to internal list */
1532         ipfw_objhash_add(icfg->ii, &ife->no);
1533
1534         /* Link notifier (possible running its callback) */
1535         ipfw_iface_add_notify(icfg->ch, &ife->ic);
1536         icfg->count++;
1537
1538         if (icfg->count + 1 == icfg->size) {
1539                 /* Notify core we need to grow */
1540                 *pflags = icfg->size + IFIDX_CHUNK;
1541         }
1542
1543         tb->ife = NULL;
1544         *pnum = 1;
1545
1546         return (0);
1547 }
1548
1549 /*
1550  * Prepare to delete key from table.
1551  * Do basic interface name checks.
1552  */
1553 static int
1554 ta_prepare_del_ifidx(struct ip_fw_chain *ch, struct tentry_info *tei,
1555     void *ta_buf)
1556 {
1557         struct ta_buf_ifidx *tb;
1558         char *ifname;
1559
1560         tb = (struct ta_buf_ifidx *)ta_buf;
1561         memset(tb, 0, sizeof(struct ta_buf_ifidx));
1562
1563         /* Check if string is terminated */
1564         ifname = (char *)tei->paddr;
1565         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1566                 return (EINVAL);
1567
1568         return (0);
1569 }
1570
1571 /*
1572  * Remove key from both configuration list and
1573  * runtime array. Removed interface notification.
1574  */
1575 static int
1576 ta_del_ifidx(void *ta_state, struct table_info *ti, struct tentry_info *tei,
1577     void *ta_buf, uint64_t *pflags, uint32_t *pnum)
1578 {
1579         struct iftable_cfg *icfg;
1580         struct ifentry *ife;
1581         struct ta_buf_ifidx *tb;
1582         char *ifname;
1583         uint16_t ifindex;
1584         int res;
1585
1586         tb = (struct ta_buf_ifidx *)ta_buf;
1587         ifname = (char *)tei->paddr;
1588         icfg = (struct iftable_cfg *)ta_state;
1589         ife = tb->ife;
1590
1591         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1592
1593         if (ife == NULL)
1594                 return (ENOENT);
1595
1596         if (ife->linked != 0) {
1597                 /* We have to remove item from runtime */
1598                 ifindex = ife->ic.iface->ifindex;
1599
1600                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
1601                     sizeof(struct ifidx), compare_ifidx);
1602
1603                 KASSERT(res == 1, ("index %d does not exist", ifindex));
1604                 icfg->used--;
1605                 ti->data = icfg->used;
1606                 ife->linked = 0;
1607         }
1608
1609         /* Unlink from local list */
1610         ipfw_objhash_del(icfg->ii, &ife->no);
1611         /* Unlink notifier */
1612         ipfw_iface_del_notify(icfg->ch, &ife->ic);
1613
1614         icfg->count--;
1615
1616         tb->ife = ife;
1617         *pnum = 1;
1618
1619         return (0);
1620 }
1621
1622 /*
1623  * Flush deleted entry.
1624  * Drops interface reference and frees entry.
1625  */
1626 static void
1627 ta_flush_ifidx_entry(struct ip_fw_chain *ch, struct tentry_info *tei,
1628     void *ta_buf)
1629 {
1630         struct ta_buf_ifidx *tb;
1631
1632         tb = (struct ta_buf_ifidx *)ta_buf;
1633
1634         if (tb->ife != NULL) {
1635                 /* Unlink first */
1636                 ipfw_iface_unref(ch, &tb->ife->ic);
1637                 free(tb->ife, M_IPFW_TBL);
1638         }
1639 }
1640
1641
1642 /*
1643  * Handle interface announce/withdrawal for particular table.
1644  * Every real runtime array modification happens here.
1645  */
1646 static void
1647 if_notifier(struct ip_fw_chain *ch, void *cbdata, uint16_t ifindex)
1648 {
1649         struct ifentry *ife;
1650         struct ifidx ifi;
1651         struct iftable_cfg *icfg;
1652         struct table_info *ti;
1653         int res;
1654
1655         ife = (struct ifentry *)cbdata;
1656         icfg = ife->icfg;
1657         ti = icfg->ti;
1658
1659         KASSERT(ti != NULL, ("ti=NULL, check change_ti handler"));
1660
1661         if (ife->linked == 0 && ifindex != 0) {
1662                 /* Interface announce */
1663                 ifi.kidx = ifindex;
1664                 ifi.spare = 0;
1665                 ifi.value = ife->value;
1666                 res = badd(&ifindex, &ifi, icfg->main_ptr, icfg->used,
1667                     sizeof(struct ifidx), compare_ifidx);
1668                 KASSERT(res == 1, ("index %d already exists", ifindex));
1669                 icfg->used++;
1670                 ti->data = icfg->used;
1671                 ife->linked = 1;
1672         } else if (ife->linked != 0 && ifindex == 0) {
1673                 /* Interface withdrawal */
1674                 ifindex = ife->ic.iface->ifindex;
1675
1676                 res = bdel(&ifindex, icfg->main_ptr, icfg->used,
1677                     sizeof(struct ifidx), compare_ifidx);
1678
1679                 KASSERT(res == 1, ("index %d does not exist", ifindex));
1680                 icfg->used--;
1681                 ti->data = icfg->used;
1682                 ife->linked = 0;
1683         }
1684 }
1685
1686
1687 /*
1688  * Table growing callbacks.
1689  */
1690
1691 struct mod_ifidx {
1692         void    *main_ptr;
1693         size_t  size;
1694 };
1695
1696 /*
1697  * Allocate ned, larger runtime ifidx array.
1698  */
1699 static int
1700 ta_prepare_mod_ifidx(void *ta_buf, uint64_t *pflags)
1701 {
1702         struct mod_ifidx *mi;
1703
1704         mi = (struct mod_ifidx *)ta_buf;
1705
1706         memset(mi, 0, sizeof(struct mod_ifidx));
1707         mi->size = *pflags;
1708         mi->main_ptr = malloc(sizeof(struct ifidx) * mi->size, M_IPFW,
1709             M_WAITOK | M_ZERO);
1710
1711         return (0);
1712 }
1713
1714 /*
1715  * Copy data from old runtime array to new one.
1716  */
1717 static int
1718 ta_fill_mod_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1719     uint64_t *pflags)
1720 {
1721         struct mod_ifidx *mi;
1722         struct iftable_cfg *icfg;
1723
1724         mi = (struct mod_ifidx *)ta_buf;
1725         icfg = (struct iftable_cfg *)ta_state;
1726
1727         /* Check if we still need to grow array */
1728         if (icfg->size >= mi->size) {
1729                 *pflags = 0;
1730                 return (0);
1731         }
1732
1733         memcpy(mi->main_ptr, icfg->main_ptr, icfg->used * sizeof(struct ifidx));
1734
1735         return (0);
1736 }
1737
1738 /*
1739  * Switch old & new arrays.
1740  */
1741 static int
1742 ta_modify_ifidx(void *ta_state, struct table_info *ti, void *ta_buf,
1743     uint64_t pflags)
1744 {
1745         struct mod_ifidx *mi;
1746         struct iftable_cfg *icfg;
1747         void *old_ptr;
1748
1749         mi = (struct mod_ifidx *)ta_buf;
1750         icfg = (struct iftable_cfg *)ta_state;
1751
1752         old_ptr = icfg->main_ptr;
1753         icfg->main_ptr = mi->main_ptr;
1754         icfg->size = mi->size;
1755         ti->state = icfg->main_ptr;
1756
1757         mi->main_ptr = old_ptr;
1758
1759         return (0);
1760 }
1761
1762 /*
1763  * Free unneded array.
1764  */
1765 static void
1766 ta_flush_mod_ifidx(void *ta_buf)
1767 {
1768         struct mod_ifidx *mi;
1769
1770         mi = (struct mod_ifidx *)ta_buf;
1771         if (mi->main_ptr != NULL)
1772                 free(mi->main_ptr, M_IPFW);
1773 }
1774
1775 static int
1776 ta_dump_ifidx_tentry(void *ta_state, struct table_info *ti, void *e,
1777     ipfw_obj_tentry *tent)
1778 {
1779         struct ifentry *ife;
1780
1781         ife = (struct ifentry *)e;
1782
1783         tent->masklen = 8 * IF_NAMESIZE;
1784         memcpy(&tent->k, ife->no.name, IF_NAMESIZE);
1785         tent->value = ife->value;
1786
1787         return (0);
1788 }
1789
1790 static int
1791 ta_find_ifidx_tentry(void *ta_state, struct table_info *ti, void *key,
1792     uint32_t keylen, ipfw_obj_tentry *tent)
1793 {
1794         struct iftable_cfg *icfg;
1795         struct ifentry *ife;
1796         char *ifname;
1797
1798         icfg = (struct iftable_cfg *)ta_state;
1799         ifname = (char *)key;
1800
1801         if (strnlen(ifname, IF_NAMESIZE) == IF_NAMESIZE)
1802                 return (EINVAL);
1803
1804         ife = (struct ifentry *)ipfw_objhash_lookup_name(icfg->ii, 0, ifname);
1805
1806         if (ife != NULL) {
1807                 ta_dump_ifidx_tentry(ta_state, ti, ife, tent);
1808                 return (0);
1809         }
1810
1811         return (ENOENT);
1812 }
1813
1814 struct wa_ifidx {
1815         ta_foreach_f    *f;
1816         void            *arg;
1817 };
1818
1819 static void
1820 foreach_ifidx(struct namedobj_instance *ii, struct named_object *no,
1821     void *arg)
1822 {
1823         struct ifentry *ife;
1824         struct wa_ifidx *wa;
1825
1826         ife = (struct ifentry *)no;
1827         wa = (struct wa_ifidx *)arg;
1828
1829         wa->f(ife, wa->arg);
1830 }
1831
1832 static void
1833 ta_foreach_ifidx(void *ta_state, struct table_info *ti, ta_foreach_f *f,
1834     void *arg)
1835 {
1836         struct iftable_cfg *icfg;
1837         struct wa_ifidx wa;
1838
1839         icfg = (struct iftable_cfg *)ta_state;
1840
1841         wa.f = f;
1842         wa.arg = arg;
1843
1844         ipfw_objhash_foreach(icfg->ii, foreach_ifidx, &wa);
1845 }
1846
1847 struct table_algo iface_idx = {
1848         .name           = "iface:array",
1849         .init           = ta_init_ifidx,
1850         .destroy        = ta_destroy_ifidx,
1851         .prepare_add    = ta_prepare_add_ifidx,
1852         .prepare_del    = ta_prepare_del_ifidx,
1853         .add            = ta_add_ifidx,
1854         .del            = ta_del_ifidx,
1855         .flush_entry    = ta_flush_ifidx_entry,
1856         .foreach        = ta_foreach_ifidx,
1857         .dump_tentry    = ta_dump_ifidx_tentry,
1858         .find_tentry    = ta_find_ifidx_tentry,
1859         .prepare_mod    = ta_prepare_mod_ifidx,
1860         .fill_mod       = ta_fill_mod_ifidx,
1861         .modify         = ta_modify_ifidx,
1862         .flush_mod      = ta_flush_mod_ifidx,
1863         .change_ti      = ta_change_ti_ifidx,
1864 };
1865
1866 void
1867 ipfw_table_algo_init(struct ip_fw_chain *ch)
1868 {
1869         size_t sz;
1870
1871         /*
1872          * Register all algorithms presented here.
1873          */
1874         sz = sizeof(struct table_algo);
1875         ipfw_add_table_algo(ch, &cidr_radix, sz, &cidr_radix.idx);
1876         ipfw_add_table_algo(ch, &cidr_hash, sz, &cidr_hash.idx);
1877         ipfw_add_table_algo(ch, &iface_idx, sz, &iface_idx.idx);
1878 }
1879
1880 void
1881 ipfw_table_algo_destroy(struct ip_fw_chain *ch)
1882 {
1883
1884         ipfw_del_table_algo(ch, cidr_radix.idx);
1885         ipfw_del_table_algo(ch, cidr_hash.idx);
1886         ipfw_del_table_algo(ch, iface_idx.idx);
1887 }
1888
1889