contrib/pf/pfctl/pfctl_optimize.c

   1 /*      $OpenBSD: pfctl_optimize.c,v 1.5 2005/01/03 15:18:10 frantzen Exp $ */
   2
   3 /*
   4  * Copyright (c) 2004 Mike Frantzen <frantzen@openbsd.org>
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 #include <sys/types.h>
  20 #include <sys/ioctl.h>
  21 #include <sys/socket.h>
  22
  23 #include <net/if.h>
  24 #include <net/pfvar.h>
  25
  26 #include <netinet/in.h>
  27 #include <arpa/inet.h>
  28
  29 #include <assert.h>
  30 #include <ctype.h>
  31 #include <err.h>
  32 #include <errno.h>
  33 #include <stddef.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include "pfctl_parser.h"
  39 #include "pfctl.h"
  40
  41 /* The size at which a table becomes faster than individual rules */
  42 #define TABLE_THRESHOLD         6
  43
  44
  45 /* #define OPT_DEBUG    1 */
  46 #ifdef OPT_DEBUG
  47 # define DEBUG(str, v...) \
  48         printf("%s: " str "\n", __FUNCTION__ , ## v)
  49 #else
  50 # define DEBUG(str, v...) ((void)0)
  51 #endif
  52
  53
  54 /*
  55  * A container that lets us sort a superblock to optimize the skip step jumps
  56  */
  57 struct pf_skip_step {
  58         int                             ps_count;       /* number of items */
  59         TAILQ_HEAD( , pf_opt_rule)      ps_rules;
  60         TAILQ_ENTRY(pf_skip_step)       ps_entry;
  61 };
  62
  63
  64 /*
  65  * A superblock is a block of adjacent rules of similar action.  If there
  66  * are five PASS rules in a row, they all become members of a superblock.
  67  * Once we have a superblock, we are free to re-order any rules within it
  68  * in order to improve performance; if a packet is passed, it doesn't matter
  69  * who passed it.
  70  */
  71 struct superblock {
  72         TAILQ_HEAD( , pf_opt_rule)               sb_rules;
  73         TAILQ_ENTRY(superblock)                  sb_entry;
  74         struct superblock                       *sb_profiled_block;
  75         TAILQ_HEAD(skiplist, pf_skip_step)       sb_skipsteps[PF_SKIP_COUNT];
  76 };
  77 TAILQ_HEAD(superblocks, superblock);
  78
  79
  80 /*
  81  * Description of the PF rule structure.
  82  */
  83 enum {
  84     BARRIER,    /* the presence of the field puts the rule in it's own block */
  85     BREAK,      /* the field may not differ between rules in a superblock */
  86     NOMERGE,    /* the field may not differ between rules when combined */
  87     COMBINED,   /* the field may itself be combined with other rules */
  88     DC,         /* we just don't care about the field */
  89     NEVER};     /* we should never see this field set?!? */
  90 struct pf_rule_field {
  91         const char      *prf_name;
  92         int              prf_type;
  93         size_t           prf_offset;
  94         size_t           prf_size;
  95 } pf_rule_desc[] = {
  96 #define PF_RULE_FIELD(field, ty)        \
  97     {#field,                            \
  98     ty,                                 \
  99     offsetof(struct pf_rule, field),    \
 100     sizeof(((struct pf_rule *)0)->field)}
 101
 102
 103     /*
 104      * The presence of these fields in a rule put the rule in it's own
 105      * superblock.  Thus it will not be optimized.  It also prevents the
 106      * rule from being re-ordered at all.
 107      */
 108     PF_RULE_FIELD(label,                BARRIER),
 109     PF_RULE_FIELD(prob,                 BARRIER),
 110     PF_RULE_FIELD(max_states,           BARRIER),
 111     PF_RULE_FIELD(max_src_nodes,        BARRIER),
 112
 113     /*
 114      * These fields must be the same between all rules in the same superblock.
 115      * These rules are allowed to be re-ordered but only among like rules.
 116      * For instance we can re-order all 'tag "foo"' rules because they have the
 117      * same tag.  But we can not re-order between a 'tag "foo"' and a
 118      * 'tag "bar"' since that would change the meaning of the ruleset.
 119      */
 120     PF_RULE_FIELD(tagname,              BREAK),
 121     PF_RULE_FIELD(keep_state,           BREAK),
 122     PF_RULE_FIELD(qname,                BREAK),
 123     PF_RULE_FIELD(rt,                   BREAK),
 124     PF_RULE_FIELD(allow_opts,           BREAK),
 125     PF_RULE_FIELD(rule_flag,            BREAK),
 126     PF_RULE_FIELD(action,               BREAK),
 127
 128     /*
 129      * Any fields not listed in this structure act as BREAK fields
 130      */
 131
 132
 133     /*
 134      * These fields must not differ when we merge two rules together but
 135      * their difference isn't enough to put the rules in different superblocks.
 136      * There are no problems re-ordering any rules with these fields.
 137      */
 138     PF_RULE_FIELD(af,                   NOMERGE),
 139     PF_RULE_FIELD(ifnot,                NOMERGE),
 140     PF_RULE_FIELD(ifname,               NOMERGE),
 141     PF_RULE_FIELD(match_tag_not,        NOMERGE),
 142     PF_RULE_FIELD(match_tagname,        NOMERGE),
 143     PF_RULE_FIELD(os_fingerprint,       NOMERGE),
 144     PF_RULE_FIELD(timeout,              NOMERGE),
 145     PF_RULE_FIELD(return_icmp,          NOMERGE),
 146     PF_RULE_FIELD(return_icmp6,         NOMERGE),
 147     PF_RULE_FIELD(uid,                  NOMERGE),
 148     PF_RULE_FIELD(gid,                  NOMERGE),
 149     PF_RULE_FIELD(direction,            NOMERGE),
 150     PF_RULE_FIELD(proto,                NOMERGE),
 151     PF_RULE_FIELD(type,                 NOMERGE),
 152     PF_RULE_FIELD(code,                 NOMERGE),
 153     PF_RULE_FIELD(flags,                NOMERGE),
 154     PF_RULE_FIELD(flagset,              NOMERGE),
 155     PF_RULE_FIELD(tos,                  NOMERGE),
 156     PF_RULE_FIELD(src.port,             NOMERGE),
 157     PF_RULE_FIELD(dst.port,             NOMERGE),
 158     PF_RULE_FIELD(src.port_op,          NOMERGE),
 159     PF_RULE_FIELD(dst.port_op,          NOMERGE),
 160     PF_RULE_FIELD(src.neg,              NOMERGE),
 161     PF_RULE_FIELD(dst.neg,              NOMERGE),
 162
 163     /* These fields can be merged */
 164     PF_RULE_FIELD(src.addr,             COMBINED),
 165     PF_RULE_FIELD(dst.addr,             COMBINED),
 166
 167     /* We just don't care about these fields.  They're set by the kernel */
 168     PF_RULE_FIELD(skip,                 DC),
 169     PF_RULE_FIELD(evaluations,          DC),
 170     PF_RULE_FIELD(packets,              DC),
 171     PF_RULE_FIELD(bytes,                DC),
 172     PF_RULE_FIELD(kif,                  DC),
 173     PF_RULE_FIELD(anchor,               DC),
 174     PF_RULE_FIELD(states,               DC),
 175     PF_RULE_FIELD(src_nodes,            DC),
 176     PF_RULE_FIELD(nr,                   DC),
 177     PF_RULE_FIELD(entries,              DC),
 178     PF_RULE_FIELD(qid,                  DC),
 179     PF_RULE_FIELD(pqid,                 DC),
 180     PF_RULE_FIELD(anchor_relative,      DC),
 181     PF_RULE_FIELD(anchor_wildcard,      DC),
 182
 183     /* These fields should never be set in a PASS/BLOCK rule */
 184     PF_RULE_FIELD(natpass,              NEVER),
 185     PF_RULE_FIELD(max_mss,              NEVER),
 186     PF_RULE_FIELD(min_ttl,              NEVER),
 187 };
 188
 189
 190
 191 int     add_opt_table(struct pfctl *, struct pf_opt_tbl **, sa_family_t,
 192             struct pf_rule_addr *);
 193 int     addrs_combineable(struct pf_rule_addr *, struct pf_rule_addr *);
 194 int     addrs_equal(struct pf_rule_addr *, struct pf_rule_addr *);
 195 int     block_feedback(struct pfctl *, struct superblock *);
 196 int     combine_rules(struct pfctl *, struct superblock *);
 197 void    comparable_rule(struct pf_rule *, const struct pf_rule *, int);
 198 int     construct_superblocks(struct pfctl *, struct pf_opt_queue *,
 199             struct superblocks *);
 200 void    exclude_supersets(struct pf_rule *, struct pf_rule *);
 201 int     load_feedback_profile(struct pfctl *, struct superblocks *);
 202 int     optimize_superblock(struct pfctl *, struct superblock *);
 203 int     pf_opt_create_table(struct pfctl *, struct pf_opt_tbl *);
 204 void    remove_from_skipsteps(struct skiplist *, struct superblock *,
 205             struct pf_opt_rule *, struct pf_skip_step *);
 206 int     remove_identical_rules(struct pfctl *, struct superblock *);
 207 int     reorder_rules(struct pfctl *, struct superblock *, int);
 208 int     rules_combineable(struct pf_rule *, struct pf_rule *);
 209 void    skip_append(struct superblock *, int, struct pf_skip_step *,
 210             struct pf_opt_rule *);
 211 int     skip_compare(int, struct pf_skip_step *, struct pf_opt_rule *);
 212 void    skip_init(void);
 213 int     skip_cmp_af(struct pf_rule *, struct pf_rule *);
 214 int     skip_cmp_dir(struct pf_rule *, struct pf_rule *);
 215 int     skip_cmp_dst_addr(struct pf_rule *, struct pf_rule *);
 216 int     skip_cmp_dst_port(struct pf_rule *, struct pf_rule *);
 217 int     skip_cmp_ifp(struct pf_rule *, struct pf_rule *);
 218 int     skip_cmp_proto(struct pf_rule *, struct pf_rule *);
 219 int     skip_cmp_src_addr(struct pf_rule *, struct pf_rule *);
 220 int     skip_cmp_src_port(struct pf_rule *, struct pf_rule *);
 221 int     superblock_inclusive(struct superblock *, struct pf_opt_rule *);
 222 void    superblock_free(struct pfctl *, struct superblock *);
 223
 224
 225 int (*skip_comparitors[PF_SKIP_COUNT])(struct pf_rule *, struct pf_rule *);
 226 const char *skip_comparitors_names[PF_SKIP_COUNT];
 227 #define PF_SKIP_COMPARITORS {                           \
 228     { "ifp", PF_SKIP_IFP, skip_cmp_ifp },               \
 229     { "dir", PF_SKIP_DIR, skip_cmp_dir },               \
 230     { "af", PF_SKIP_AF, skip_cmp_af },                  \
 231     { "proto", PF_SKIP_PROTO, skip_cmp_proto },         \
 232     { "saddr", PF_SKIP_SRC_ADDR, skip_cmp_src_addr },   \
 233     { "sport", PF_SKIP_SRC_PORT, skip_cmp_src_port },   \
 234     { "daddr", PF_SKIP_DST_ADDR, skip_cmp_dst_addr },   \
 235     { "dport", PF_SKIP_DST_PORT, skip_cmp_dst_port }    \
 236 }
 237
 238 struct pfr_buffer table_buffer;
 239 int table_identifier;
 240
 241
 242 int
 243 pfctl_optimize_rules(struct pfctl *pf)
 244 {
 245         struct superblocks superblocks;
 246         struct superblock *block;
 247         struct pf_opt_rule *por;
 248         int nr;
 249
 250         DEBUG("optimizing ruleset");
 251         memset(&table_buffer, 0, sizeof(table_buffer));
 252         skip_init();
 253
 254         if (TAILQ_FIRST(&pf->opt_queue))
 255                 nr = TAILQ_FIRST(&pf->opt_queue)->por_rule.nr;
 256
 257         TAILQ_INIT(&superblocks);
 258         if (construct_superblocks(pf, &pf->opt_queue, &superblocks))
 259                 goto error;
 260
 261         if (pf->opts & PF_OPT_OPTIMIZE_PROFILE) {
 262                 if (load_feedback_profile(pf, &superblocks))
 263                         goto error;
 264         }
 265
 266         TAILQ_FOREACH(block, &superblocks, sb_entry) {
 267                 if (optimize_superblock(pf, block))
 268                         goto error;
 269         }
 270
 271
 272         /*
 273          * Optimizations are done so we turn off the optimization flag and
 274          * put the rules right back into the regular codepath.
 275          */
 276         pf->opts &= ~PF_OPT_OPTIMIZE;
 277
 278         while ((block = TAILQ_FIRST(&superblocks))) {
 279                 TAILQ_REMOVE(&superblocks, block, sb_entry);
 280
 281                 while ((por = TAILQ_FIRST(&block->sb_rules))) {
 282                         TAILQ_REMOVE(&block->sb_rules, por, por_entry);
 283                         por->por_rule.nr = nr++;
 284                         if (pfctl_add_rule(pf, &por->por_rule,
 285                             por->por_anchor)) {
 286                                 free(por);
 287                                 goto error;
 288                         }
 289                         free(por);
 290                 }
 291                 free(block);
 292         }
 293
 294         return (0);
 295
 296 error:
 297         while ((por = TAILQ_FIRST(&pf->opt_queue))) {
 298                 TAILQ_REMOVE(&pf->opt_queue, por, por_entry);
 299                 if (por->por_src_tbl) {
 300                         pfr_buf_clear(por->por_src_tbl->pt_buf);
 301                         free(por->por_src_tbl->pt_buf);
 302                         free(por->por_src_tbl);
 303                 }
 304                 if (por->por_dst_tbl) {
 305                         pfr_buf_clear(por->por_dst_tbl->pt_buf);
 306                         free(por->por_dst_tbl->pt_buf);
 307                         free(por->por_dst_tbl);
 308                 }
 309                 free(por);
 310         }
 311         while ((block = TAILQ_FIRST(&superblocks))) {
 312                 TAILQ_REMOVE(&superblocks, block, sb_entry);
 313                 superblock_free(pf, block);
 314         }
 315         return (1);
 316 }
 317
 318
 319 /*
 320  * Go ahead and optimize a superblock
 321  */
 322 int
 323 optimize_superblock(struct pfctl *pf, struct superblock *block)
 324 {
 325 #ifdef OPT_DEBUG
 326         struct pf_opt_rule *por;
 327 #endif /* OPT_DEBUG */
 328
 329         /* We have a few optimization passes:
 330          *   1) remove duplicate rules or rules that are a subset of other
 331          *      rules
 332          *   2) combine otherwise identical rules with different IP addresses
 333          *      into a single rule and put the addresses in a table.
 334          *   3) re-order the rules to improve kernel skip steps
 335          *   4) re-order the 'quick' rules based on feedback from the
 336          *      active ruleset statistics
 337          *
 338          * XXX combine_rules() doesn't combine v4 and v6 rules.  would just
 339          *     have to keep af in the table container, make af 'COMBINE' and
 340          *     twiddle the af on the merged rule
 341          * XXX maybe add a weighting to the metric on skipsteps when doing
 342          *     reordering.  sometimes two sequential tables will be better
 343          *     that four consecutive interfaces.
 344          * XXX need to adjust the skipstep count of everything after PROTO,
 345          *     since they aren't actually checked on a proto mismatch in
 346          *     pf_test_{tcp, udp, icmp}()
 347          * XXX should i treat proto=0, af=0 or dir=0 special in skepstep
 348          *     calculation since they are a DC?
 349          * XXX keep last skiplist of last superblock to influence this
 350          *     superblock.  '5 inet6 log' should make '3 inet6' come before '4
 351          *     inet' in the next superblock.
 352          * XXX would be useful to add tables for ports
 353          * XXX we can also re-order some mutually exclusive superblocks to
 354          *     try merging superblocks before any of these optimization passes.
 355          *     for instance a single 'log in' rule in the middle of non-logging
 356          *     out rules.
 357          */
 358
 359         /* shortcut.  there will be alot of 1-rule superblocks */
 360         if (!TAILQ_NEXT(TAILQ_FIRST(&block->sb_rules), por_entry))
 361                 return (0);
 362
 363 #ifdef OPT_DEBUG
 364         printf("--- Superblock ---\n");
 365         TAILQ_FOREACH(por, &block->sb_rules, por_entry) {
 366                 printf("  ");
 367                 print_rule(&por->por_rule, por->por_anchor, 1);
 368         }
 369 #endif /* OPT_DEBUG */
 370
 371
 372         if (remove_identical_rules(pf, block))
 373                 return (1);
 374         if (combine_rules(pf, block))
 375                 return (1);
 376         if ((pf->opts & PF_OPT_OPTIMIZE_PROFILE) &&
 377             TAILQ_FIRST(&block->sb_rules)->por_rule.quick &&
 378             block->sb_profiled_block) {
 379                 if (block_feedback(pf, block))
 380                         return (1);
 381         } else if (reorder_rules(pf, block, 0)) {
 382                 return (1);
 383         }
 384
 385         /*
 386          * Don't add any optimization passes below reorder_rules().  It will
 387          * have divided superblocks into smaller blocks for further refinement
 388          * and doesn't put them back together again.  What once was a true
 389          * superblock might have been split into multiple superblocks.
 390          */
 391
 392 #ifdef OPT_DEBUG
 393         printf("--- END Superblock ---\n");
 394 #endif /* OPT_DEBUG */
 395         return (0);
 396 }
 397
 398
 399 /*
 400  * Optimization pass #1: remove identical rules
 401  */
 402 int
 403 remove_identical_rules(struct pfctl *pf, struct superblock *block)
 404 {
 405         struct pf_opt_rule *por1, *por2, *por_next, *por2_next;
 406         struct pf_rule a, a2, b, b2;
 407
 408         for (por1 = TAILQ_FIRST(&block->sb_rules); por1; por1 = por_next) {
 409                 por_next = TAILQ_NEXT(por1, por_entry);
 410                 for (por2 = por_next; por2; por2 = por2_next) {
 411                         por2_next = TAILQ_NEXT(por2, por_entry);
 412                         comparable_rule(&a, &por1->por_rule, DC);
 413                         comparable_rule(&b, &por2->por_rule, DC);
 414                         memcpy(&a2, &a, sizeof(a2));
 415                         memcpy(&b2, &b, sizeof(b2));
 416
 417                         exclude_supersets(&a, &b);
 418                         exclude_supersets(&b2, &a2);
 419                         if (memcmp(&a, &b, sizeof(a)) == 0) {
 420                                 DEBUG("removing identical rule  nr%d = *nr%d*",
 421                                     por1->por_rule.nr, por2->por_rule.nr);
 422                                 TAILQ_REMOVE(&block->sb_rules, por2, por_entry);
 423                                 if (por_next == por2)
 424                                         por_next = TAILQ_NEXT(por1, por_entry);
 425                                 free(por2);
 426                         } else if (memcmp(&a2, &b2, sizeof(a2)) == 0) {
 427                                 DEBUG("removing identical rule  *nr%d* = nr%d",
 428                                     por1->por_rule.nr, por2->por_rule.nr);
 429                                 TAILQ_REMOVE(&block->sb_rules, por1, por_entry);
 430                                 free(por1);
 431                                 break;
 432                         }
 433                 }
 434         }
 435
 436         return (0);
 437 }
 438
 439
 440 /*
 441  * Optimization pass #2: combine similar rules with different addresses
 442  * into a single rule and a table
 443  */
 444 int
 445 combine_rules(struct pfctl *pf, struct superblock *block)
 446 {
 447         struct pf_opt_rule *p1, *p2, *por_next;
 448         int src_eq, dst_eq;
 449
 450         if ((pf->loadopt & PFCTL_FLAG_TABLE) == 0) {
 451                 warnx("Must enable table loading for optimizations");
 452                 return (1);
 453         }
 454
 455         /* First we make a pass to combine the rules.  O(n log n) */
 456         TAILQ_FOREACH(p1, &block->sb_rules, por_entry) {
 457                 for (p2 = TAILQ_NEXT(p1, por_entry); p2; p2 = por_next) {
 458                         por_next = TAILQ_NEXT(p2, por_entry);
 459
 460                         src_eq = addrs_equal(&p1->por_rule.src,
 461                             &p2->por_rule.src);
 462                         dst_eq = addrs_equal(&p1->por_rule.dst,
 463                             &p2->por_rule.dst);
 464
 465                         if (src_eq && !dst_eq && p1->por_src_tbl == NULL &&
 466                             p2->por_dst_tbl == NULL &&
 467                             p2->por_src_tbl == NULL &&
 468                             rules_combineable(&p1->por_rule, &p2->por_rule) &&
 469                             addrs_combineable(&p1->por_rule.dst,
 470                             &p2->por_rule.dst)) {
 471                                 DEBUG("can combine rules  nr%d = nr%d",
 472                                     p1->por_rule.nr, p2->por_rule.nr);
 473                                 if (p1->por_dst_tbl == NULL &&
 474                                     add_opt_table(pf, &p1->por_dst_tbl,
 475                                     p1->por_rule.af, &p1->por_rule.dst))
 476                                         return (1);
 477                                 if (add_opt_table(pf, &p1->por_dst_tbl,
 478                                     p1->por_rule.af, &p2->por_rule.dst))
 479                                         return (1);
 480                                 p2->por_dst_tbl = p1->por_dst_tbl;
 481                                 if (p1->por_dst_tbl->pt_rulecount >=
 482                                     TABLE_THRESHOLD) {
 483                                         TAILQ_REMOVE(&block->sb_rules, p2,
 484                                             por_entry);
 485                                         free(p2);
 486                                 }
 487                         } else if (!src_eq && dst_eq && p1->por_dst_tbl == NULL
 488                             && p2->por_src_tbl == NULL &&
 489                             p2->por_dst_tbl == NULL &&
 490                             rules_combineable(&p1->por_rule, &p2->por_rule) &&
 491                             addrs_combineable(&p1->por_rule.src,
 492                             &p2->por_rule.src)) {
 493                                 DEBUG("can combine rules  nr%d = nr%d",
 494                                     p1->por_rule.nr, p2->por_rule.nr);
 495                                 if (p1->por_src_tbl == NULL &&
 496                                     add_opt_table(pf, &p1->por_src_tbl,
 497                                     p1->por_rule.af, &p1->por_rule.src))
 498                                         return (1);
 499                                 if (add_opt_table(pf, &p1->por_src_tbl,
 500                                     p1->por_rule.af, &p2->por_rule.src))
 501                                         return (1);
 502                                 p2->por_src_tbl = p1->por_src_tbl;
 503                                 if (p1->por_src_tbl->pt_rulecount >=
 504                                     TABLE_THRESHOLD) {
 505                                         TAILQ_REMOVE(&block->sb_rules, p2,
 506                                             por_entry);
 507                                         free(p2);
 508                                 }
 509                         }
 510                 }
 511         }
 512
 513
 514         /*
 515          * Then we make a final pass to create a valid table name and
 516          * insert the name into the rules.
 517          */
 518         for (p1 = TAILQ_FIRST(&block->sb_rules); p1; p1 = por_next) {
 519                 por_next = TAILQ_NEXT(p1, por_entry);
 520                 assert(p1->por_src_tbl == NULL || p1->por_dst_tbl == NULL);
 521
 522                 if (p1->por_src_tbl && p1->por_src_tbl->pt_rulecount >=
 523                     TABLE_THRESHOLD) {
 524                         if (p1->por_src_tbl->pt_generated) {
 525                                 /* This rule is included in a table */
 526                                 TAILQ_REMOVE(&block->sb_rules, p1, por_entry);
 527                                 free(p1);
 528                                 continue;
 529                         }
 530                         p1->por_src_tbl->pt_generated = 1;
 531
 532                         if ((pf->opts & PF_OPT_NOACTION) == 0 &&
 533                             pf_opt_create_table(pf, p1->por_src_tbl))
 534                                 return (1);
 535
 536                         pf->tdirty = 1;
 537
 538                         if (pf->opts & PF_OPT_VERBOSE)
 539                                 print_tabledef(p1->por_src_tbl->pt_name,
 540                                     PFR_TFLAG_CONST, 1,
 541                                     &p1->por_src_tbl->pt_nodes);
 542
 543                         memset(&p1->por_rule.src.addr, 0,
 544                             sizeof(p1->por_rule.src.addr));
 545                         p1->por_rule.src.addr.type = PF_ADDR_TABLE;
 546                         strlcpy(p1->por_rule.src.addr.v.tblname,
 547                             p1->por_src_tbl->pt_name,
 548                             sizeof(p1->por_rule.src.addr.v.tblname));
 549
 550                         pfr_buf_clear(p1->por_src_tbl->pt_buf);
 551                         free(p1->por_src_tbl->pt_buf);
 552                         p1->por_src_tbl->pt_buf = NULL;
 553                 }
 554                 if (p1->por_dst_tbl && p1->por_dst_tbl->pt_rulecount >=
 555                     TABLE_THRESHOLD) {
 556                         if (p1->por_dst_tbl->pt_generated) {
 557                                 /* This rule is included in a table */
 558                                 TAILQ_REMOVE(&block->sb_rules, p1, por_entry);
 559                                 free(p1);
 560                                 continue;
 561                         }
 562                         p1->por_dst_tbl->pt_generated = 1;
 563
 564                         if ((pf->opts & PF_OPT_NOACTION) == 0 &&
 565                             pf_opt_create_table(pf, p1->por_dst_tbl))
 566                                 return (1);
 567                         pf->tdirty = 1;
 568
 569                         if (pf->opts & PF_OPT_VERBOSE)
 570                                 print_tabledef(p1->por_dst_tbl->pt_name,
 571                                     PFR_TFLAG_CONST, 1,
 572                                     &p1->por_dst_tbl->pt_nodes);
 573
 574                         memset(&p1->por_rule.dst.addr, 0,
 575                             sizeof(p1->por_rule.dst.addr));
 576                         p1->por_rule.dst.addr.type = PF_ADDR_TABLE;
 577                         strlcpy(p1->por_rule.dst.addr.v.tblname,
 578                             p1->por_dst_tbl->pt_name,
 579                             sizeof(p1->por_rule.dst.addr.v.tblname));
 580
 581                         pfr_buf_clear(p1->por_dst_tbl->pt_buf);
 582                         free(p1->por_dst_tbl->pt_buf);
 583                         p1->por_dst_tbl->pt_buf = NULL;
 584                 }
 585         }
 586
 587         return (0);
 588 }
 589
 590
 591 /*
 592  * Optimization pass #3: re-order rules to improve skip steps
 593  */
 594 int
 595 reorder_rules(struct pfctl *pf, struct superblock *block, int depth)
 596 {
 597         struct superblock *newblock;
 598         struct pf_skip_step *skiplist;
 599         struct pf_opt_rule *por;
 600         int i, largest, largest_list, rule_count = 0;
 601         TAILQ_HEAD( , pf_opt_rule) head;
 602
 603         /*
 604          * Calculate the best-case skip steps.  We put each rule in a list
 605          * of other rules with common fields
 606          */
 607         for (i = 0; i < PF_SKIP_COUNT; i++) {
 608                 TAILQ_FOREACH(por, &block->sb_rules, por_entry) {
 609                         TAILQ_FOREACH(skiplist, &block->sb_skipsteps[i],
 610                             ps_entry) {
 611                                 if (skip_compare(i, skiplist, por) == 0)
 612                                         break;
 613                         }
 614                         if (skiplist == NULL) {
 615                                 if ((skiplist = calloc(1, sizeof(*skiplist))) ==
 616                                     NULL)
 617                                         err(1, "calloc");
 618                                 TAILQ_INIT(&skiplist->ps_rules);
 619                                 TAILQ_INSERT_TAIL(&block->sb_skipsteps[i],
 620                                     skiplist, ps_entry);
 621                         }
 622                         skip_append(block, i, skiplist, por);
 623                 }
 624         }
 625
 626         TAILQ_FOREACH(por, &block->sb_rules, por_entry)
 627                 rule_count++;
 628
 629         /*
 630          * Now we're going to ignore any fields that are identical between
 631          * all of the rules in the superblock and those fields which differ
 632          * between every rule in the superblock.
 633          */
 634         largest = 0;
 635         for (i = 0; i < PF_SKIP_COUNT; i++) {
 636                 skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]);
 637                 if (skiplist->ps_count == rule_count) {
 638                         DEBUG("(%d) original skipstep '%s' is all rules",
 639                             depth, skip_comparitors_names[i]);
 640                         skiplist->ps_count = 0;
 641                 } else if (skiplist->ps_count == 1) {
 642                         skiplist->ps_count = 0;
 643                 } else {
 644                         DEBUG("(%d) original skipstep '%s' largest jump is %d",
 645                             depth, skip_comparitors_names[i],
 646                             skiplist->ps_count);
 647                         if (skiplist->ps_count > largest)
 648                                 largest = skiplist->ps_count;
 649                 }
 650         }
 651         if (largest == 0) {
 652                 /* Ugh.  There is NO commonality in the superblock on which
 653                  * optimize the skipsteps optimization.
 654                  */
 655                 goto done;
 656         }
 657
 658         /*
 659          * Now we're going to empty the superblock rule list and re-create
 660          * it based on a more optimal skipstep order.
 661          */
 662         TAILQ_INIT(&head);
 663         while ((por = TAILQ_FIRST(&block->sb_rules))) {
 664                 TAILQ_REMOVE(&block->sb_rules, por, por_entry);
 665                 TAILQ_INSERT_TAIL(&head, por, por_entry);
 666         }
 667
 668
 669         while (!TAILQ_EMPTY(&head)) {
 670                 largest = 1;
 671
 672                 /*
 673                  * Find the most useful skip steps remaining
 674                  */
 675                 for (i = 0; i < PF_SKIP_COUNT; i++) {
 676                         skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]);
 677                         if (skiplist->ps_count > largest) {
 678                                 largest = skiplist->ps_count;
 679                                 largest_list = i;
 680                         }
 681                 }
 682
 683                 if (largest <= 1) {
 684                         /*
 685                          * Nothing useful left.  Leave remaining rules in order.
 686                          */
 687                         DEBUG("(%d) no more commonality for skip steps", depth);
 688                         while ((por = TAILQ_FIRST(&head))) {
 689                                 TAILQ_REMOVE(&head, por, por_entry);
 690                                 TAILQ_INSERT_TAIL(&block->sb_rules, por,
 691                                     por_entry);
 692                         }
 693                 } else {
 694                         /*
 695                          * There is commonality.  Extract those common rules
 696                          * and place them in the ruleset adjacent to each
 697                          * other.
 698                          */
 699                         skiplist = TAILQ_FIRST(&block->sb_skipsteps[
 700                             largest_list]);
 701                         DEBUG("(%d) skipstep '%s' largest jump is %d @ #%d",
 702                             depth, skip_comparitors_names[largest_list],
 703                             largest, TAILQ_FIRST(&TAILQ_FIRST(&block->
 704                             sb_skipsteps [largest_list])->ps_rules)->
 705                             por_rule.nr);
 706                         TAILQ_REMOVE(&block->sb_skipsteps[largest_list],
 707                             skiplist, ps_entry);
 708
 709
 710                         /*
 711                          * There may be further commonality inside these
 712                          * rules.  So we'll split them off into they're own
 713                          * superblock and pass it back into the optimizer.
 714                          */
 715                         if (skiplist->ps_count > 2) {
 716                                 if ((newblock = calloc(1, sizeof(*newblock)))
 717                                     == NULL) {
 718                                         warn("calloc");
 719                                         return (1);
 720                                 }
 721                                 TAILQ_INIT(&newblock->sb_rules);
 722                                 for (i = 0; i < PF_SKIP_COUNT; i++)
 723                                         TAILQ_INIT(&newblock->sb_skipsteps[i]);
 724                                 TAILQ_INSERT_BEFORE(block, newblock, sb_entry);
 725                                 DEBUG("(%d) splitting off %d rules from superblock @ #%d",
 726                                     depth, skiplist->ps_count,
 727                                     TAILQ_FIRST(&skiplist->ps_rules)->
 728                                     por_rule.nr);
 729                         } else {
 730                                 newblock = block;
 731                         }
 732
 733                         while ((por = TAILQ_FIRST(&skiplist->ps_rules))) {
 734                                 TAILQ_REMOVE(&head, por, por_entry);
 735                                 TAILQ_REMOVE(&skiplist->ps_rules, por,
 736                                     por_skip_entry[largest_list]);
 737                                 TAILQ_INSERT_TAIL(&newblock->sb_rules, por,
 738                                     por_entry);
 739
 740                                 /* Remove this rule from all other skiplists */
 741                                 remove_from_skipsteps(&block->sb_skipsteps[
 742                                     largest_list], block, por, skiplist);
 743                         }
 744                         free(skiplist);
 745                         if (newblock != block)
 746                                 if (reorder_rules(pf, newblock, depth + 1))
 747                                         return (1);
 748                 }
 749         }
 750
 751 done:
 752         for (i = 0; i < PF_SKIP_COUNT; i++) {
 753                 while ((skiplist = TAILQ_FIRST(&block->sb_skipsteps[i]))) {
 754                         TAILQ_REMOVE(&block->sb_skipsteps[i], skiplist,
 755                             ps_entry);
 756                         free(skiplist);
 757                 }
 758         }
 759
 760         return (0);
 761 }
 762
 763
 764 /*
 765  * Optimization pass #4: re-order 'quick' rules based on feedback from the
 766  * currently running ruleset
 767  */
 768 int
 769 block_feedback(struct pfctl *pf, struct superblock *block)
 770 {
 771         TAILQ_HEAD( , pf_opt_rule) queue;
 772         struct pf_opt_rule *por1, *por2;
 773         u_int64_t total_count = 0;
 774         struct pf_rule a, b;
 775
 776
 777         /*
 778          * Walk through all of the profiled superblock's rules and copy
 779          * the counters onto our rules.
 780          */
 781         TAILQ_FOREACH(por1, &block->sb_profiled_block->sb_rules, por_entry) {
 782                 comparable_rule(&a, &por1->por_rule, DC);
 783                 total_count += por1->por_rule.packets;
 784                 TAILQ_FOREACH(por2, &block->sb_rules, por_entry) {
 785                         if (por2->por_profile_count)
 786                                 continue;
 787                         comparable_rule(&b, &por2->por_rule, DC);
 788                         if (memcmp(&a, &b, sizeof(a)) == 0) {
 789                                 por2->por_profile_count =
 790                                     por1->por_rule.packets;
 791                                 break;
 792                         }
 793                 }
 794         }
 795         superblock_free(pf, block->sb_profiled_block);
 796         block->sb_profiled_block = NULL;
 797
 798         /*
 799          * Now we pull all of the rules off the superblock and re-insert them
 800          * in sorted order.
 801          */
 802
 803         TAILQ_INIT(&queue);
 804         while ((por1 = TAILQ_FIRST(&block->sb_rules)) != NULL) {
 805                 TAILQ_REMOVE(&block->sb_rules, por1, por_entry);
 806                 TAILQ_INSERT_TAIL(&queue, por1, por_entry);
 807         }
 808
 809         while ((por1 = TAILQ_FIRST(&queue)) != NULL) {
 810                 TAILQ_REMOVE(&queue, por1, por_entry);
 811 /* XXX I should sort all of the unused rules based on skip steps */
 812                 TAILQ_FOREACH(por2, &block->sb_rules, por_entry) {
 813                         if (por1->por_profile_count > por2->por_profile_count) {
 814                                 TAILQ_INSERT_BEFORE(por2, por1, por_entry);
 815                                 break;
 816                         }
 817                 }
 818                 if (por2 == TAILQ_END(&block->sb_rules))
 819                         TAILQ_INSERT_TAIL(&block->sb_rules, por1, por_entry);
 820         }
 821
 822         return (0);
 823 }
 824
 825
 826 /*
 827  * Load the current ruleset from the kernel and try to associate them with
 828  * the ruleset we're optimizing.
 829  */
 830 int
 831 load_feedback_profile(struct pfctl *pf, struct superblocks *superblocks)
 832 {
 833         struct superblock *block, *blockcur;
 834         struct superblocks prof_superblocks;
 835         struct pf_opt_rule *por;
 836         struct pf_opt_queue queue;
 837         struct pfioc_rule pr;
 838         struct pf_rule a, b;
 839         int nr, mnr;
 840
 841         TAILQ_INIT(&queue);
 842         TAILQ_INIT(&prof_superblocks);
 843
 844         memset(&pr, 0, sizeof(pr));
 845         pr.rule.action = PF_PASS;
 846         if (ioctl(pf->dev, DIOCGETRULES, &pr)) {
 847                 warn("DIOCGETRULES");
 848                 return (1);
 849         }
 850         mnr = pr.nr;
 851
 852         DEBUG("Loading %d active rules for a feedback profile", mnr);
 853         for (nr = 0; nr < mnr; ++nr) {
 854                 if ((por = calloc(1, sizeof(*por))) == NULL) {
 855                         warn("calloc");
 856                         return (1);
 857                 }
 858                 pr.nr = nr;
 859                 if (ioctl(pf->dev, DIOCGETRULE, &pr)) {
 860                         warn("DIOCGETRULES");
 861                         return (1);
 862                 }
 863                 memcpy(&por->por_rule, &pr.rule, sizeof(por->por_rule));
 864                 strlcpy(por->por_anchor, pr.anchor_call,
 865                     sizeof(por->por_anchor));
 866                 if (TAILQ_EMPTY(&por->por_rule.rpool.list))
 867                         memset(&por->por_rule.rpool, 0,
 868                             sizeof(por->por_rule.rpool));
 869                 TAILQ_INSERT_TAIL(&queue, por, por_entry);
 870
 871                 /* XXX pfctl_get_pool(pf->dev, &pr.rule.rpool, nr, pr.ticket,
 872                  *         PF_PASS, pf->anchor) ???
 873                  * ... pfctl_clear_pool(&pr.rule.rpool)
 874                  */
 875         }
 876
 877         if (construct_superblocks(pf, &queue, &prof_superblocks))
 878                 return (1);
 879
 880
 881         /*
 882          * Now we try to associate the active ruleset's superblocks with
 883          * the superblocks we're compiling.
 884          */
 885         block = TAILQ_FIRST(superblocks);
 886         blockcur = TAILQ_FIRST(&prof_superblocks);
 887         while (block && blockcur) {
 888                 comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule,
 889                     BREAK);
 890                 comparable_rule(&b, &TAILQ_FIRST(&blockcur->sb_rules)->por_rule,
 891                     BREAK);
 892                 if (memcmp(&a, &b, sizeof(a)) == 0) {
 893                         /* The two superblocks lined up */
 894                         block->sb_profiled_block = blockcur;
 895                 } else {
 896                         DEBUG("superblocks don't line up between #%d and #%d",
 897                             TAILQ_FIRST(&block->sb_rules)->por_rule.nr,
 898                             TAILQ_FIRST(&blockcur->sb_rules)->por_rule.nr);
 899                         break;
 900                 }
 901                 block = TAILQ_NEXT(block, sb_entry);
 902                 blockcur = TAILQ_NEXT(blockcur, sb_entry);
 903         }
 904
 905
 906
 907         /* Free any superblocks we couldn't link */
 908         while (blockcur) {
 909                 block = TAILQ_NEXT(blockcur, sb_entry);
 910                 superblock_free(pf, blockcur);
 911                 blockcur = block;
 912         }
 913         return (0);
 914 }
 915
 916
 917 /*
 918  * Compare a rule to a skiplist to see if the rule is a member
 919  */
 920 int
 921 skip_compare(int skipnum, struct pf_skip_step *skiplist,
 922     struct pf_opt_rule *por)
 923 {
 924         struct pf_rule *a, *b;
 925         if (skipnum >= PF_SKIP_COUNT || skipnum < 0)
 926                 errx(1, "skip_compare() out of bounds");
 927         a = &por->por_rule;
 928         b = &TAILQ_FIRST(&skiplist->ps_rules)->por_rule;
 929
 930         return ((skip_comparitors[skipnum])(a, b));
 931 }
 932
 933
 934 /*
 935  * Add a rule to a skiplist
 936  */
 937 void
 938 skip_append(struct superblock *superblock, int skipnum,
 939     struct pf_skip_step *skiplist, struct pf_opt_rule *por)
 940 {
 941         struct pf_skip_step *prev;
 942
 943         skiplist->ps_count++;
 944         TAILQ_INSERT_TAIL(&skiplist->ps_rules, por, por_skip_entry[skipnum]);
 945
 946         /* Keep the list of skiplists sorted by whichever is larger */
 947         while ((prev = TAILQ_PREV(skiplist, skiplist, ps_entry)) &&
 948             prev->ps_count < skiplist->ps_count) {
 949                 TAILQ_REMOVE(&superblock->sb_skipsteps[skipnum],
 950                     skiplist, ps_entry);
 951                 TAILQ_INSERT_BEFORE(prev, skiplist, ps_entry);
 952         }
 953 }
 954
 955
 956 /*
 957  * Remove a rule from the other skiplist calculations.
 958  */
 959 void
 960 remove_from_skipsteps(struct skiplist *head, struct superblock *block,
 961     struct pf_opt_rule *por, struct pf_skip_step *active_list)
 962 {
 963         struct pf_skip_step *sk, *next;
 964         struct pf_opt_rule *p2;
 965         int i, found;
 966
 967         for (i = 0; i < PF_SKIP_COUNT; i++) {
 968                 sk = TAILQ_FIRST(&block->sb_skipsteps[i]);
 969                 if (sk == NULL || sk == active_list || sk->ps_count <= 1)
 970                         continue;
 971                 found = 0;
 972                 do {
 973                         TAILQ_FOREACH(p2, &sk->ps_rules, por_skip_entry[i])
 974                                 if (p2 == por) {
 975                                         TAILQ_REMOVE(&sk->ps_rules, p2,
 976                                             por_skip_entry[i]);
 977                                         found = 1;
 978                                         sk->ps_count--;
 979                                         break;
 980                                 }
 981                 } while (!found && (sk = TAILQ_NEXT(sk, ps_entry)));
 982                 if (found && sk) {
 983                         /* Does this change the sorting order? */
 984                         while ((next = TAILQ_NEXT(sk, ps_entry)) &&
 985                             next->ps_count > sk->ps_count) {
 986                                 TAILQ_REMOVE(head, sk, ps_entry);
 987                                 TAILQ_INSERT_AFTER(head, next, sk, ps_entry);
 988                         }
 989 #ifdef OPT_DEBUG
 990                         next = TAILQ_NEXT(sk, ps_entry);
 991                         assert(next == NULL || next->ps_count <= sk->ps_count);
 992 #endif /* OPT_DEBUG */
 993                 }
 994         }
 995 }
 996
 997
 998 /* Compare two rules AF field for skiplist construction */
 999 int
1000 skip_cmp_af(struct pf_rule *a, struct pf_rule *b)
1001 {
1002         if (a->af != b->af || a->af == 0)
1003                 return (1);
1004         return (0);
1005 }
1006
1007 /* Compare two rules DIRECTION field for skiplist construction */
1008 int
1009 skip_cmp_dir(struct pf_rule *a, struct pf_rule *b)
1010 {
1011         if (a->direction == 0 || a->direction != b->direction)
1012                 return (1);
1013         return (0);
1014 }
1015
1016 /* Compare two rules DST Address field for skiplist construction */
1017 int
1018 skip_cmp_dst_addr(struct pf_rule *a, struct pf_rule *b)
1019 {
1020         if (a->dst.neg != b->dst.neg ||
1021             a->dst.addr.type != b->dst.addr.type)
1022                 return (1);
1023         /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1024          *    && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1025          *    a->proto == IPPROTO_ICMP
1026          *      return (1);
1027          */
1028         switch (a->dst.addr.type) {
1029         case PF_ADDR_ADDRMASK:
1030                 if (memcmp(&a->dst.addr.v.a.addr, &b->dst.addr.v.a.addr,
1031                     sizeof(a->dst.addr.v.a.addr)) ||
1032                     memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask,
1033                     sizeof(a->dst.addr.v.a.mask)) ||
1034                     (a->dst.addr.v.a.addr.addr32[0] == 0 &&
1035                     a->dst.addr.v.a.addr.addr32[1] == 0 &&
1036                     a->dst.addr.v.a.addr.addr32[2] == 0 &&
1037                     a->dst.addr.v.a.addr.addr32[3] == 0))
1038                         return (1);
1039                 return (0);
1040         case PF_ADDR_DYNIFTL:
1041                 if (strcmp(a->dst.addr.v.ifname, b->dst.addr.v.ifname) != 0 ||
1042                     a->dst.addr.iflags != a->dst.addr.iflags ||
1043                     memcmp(&a->dst.addr.v.a.mask, &b->dst.addr.v.a.mask,
1044                     sizeof(a->dst.addr.v.a.mask)))
1045                         return (1);
1046                 return (0);
1047         case PF_ADDR_NOROUTE:
1048                 return (0);
1049         case PF_ADDR_TABLE:
1050                 return (strcmp(a->dst.addr.v.tblname, b->dst.addr.v.tblname));
1051         }
1052         return (1);
1053 }
1054
1055 /* Compare two rules DST port field for skiplist construction */
1056 int
1057 skip_cmp_dst_port(struct pf_rule *a, struct pf_rule *b)
1058 {
1059         /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1060          *    && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1061          *    a->proto == IPPROTO_ICMP
1062          *      return (1);
1063          */
1064         if (a->dst.port_op == PF_OP_NONE || a->dst.port_op != b->dst.port_op ||
1065             a->dst.port[0] != b->dst.port[0] ||
1066             a->dst.port[1] != b->dst.port[1])
1067                 return (1);
1068         return (0);
1069 }
1070
1071 /* Compare two rules IFP field for skiplist construction */
1072 int
1073 skip_cmp_ifp(struct pf_rule *a, struct pf_rule *b)
1074 {
1075         if (strcmp(a->ifname, b->ifname) || a->ifname[0] == '\0')
1076                 return (1);
1077         return (a->ifnot != b->ifnot);
1078 }
1079
1080 /* Compare two rules PROTO field for skiplist construction */
1081 int
1082 skip_cmp_proto(struct pf_rule *a, struct pf_rule *b)
1083 {
1084         return (a->proto != b->proto || a->proto == 0);
1085 }
1086
1087 /* Compare two rules SRC addr field for skiplist construction */
1088 int
1089 skip_cmp_src_addr(struct pf_rule *a, struct pf_rule *b)
1090 {
1091         if (a->src.neg != b->src.neg ||
1092             a->src.addr.type != b->src.addr.type)
1093                 return (1);
1094         /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1095          *    && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1096          *    a->proto == IPPROTO_ICMP
1097          *      return (1);
1098          */
1099         switch (a->src.addr.type) {
1100         case PF_ADDR_ADDRMASK:
1101                 if (memcmp(&a->src.addr.v.a.addr, &b->src.addr.v.a.addr,
1102                     sizeof(a->src.addr.v.a.addr)) ||
1103                     memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask,
1104                     sizeof(a->src.addr.v.a.mask)) ||
1105                     (a->src.addr.v.a.addr.addr32[0] == 0 &&
1106                     a->src.addr.v.a.addr.addr32[1] == 0 &&
1107                     a->src.addr.v.a.addr.addr32[2] == 0 &&
1108                     a->src.addr.v.a.addr.addr32[3] == 0))
1109                         return (1);
1110                 return (0);
1111         case PF_ADDR_DYNIFTL:
1112                 if (strcmp(a->src.addr.v.ifname, b->src.addr.v.ifname) != 0 ||
1113                     a->src.addr.iflags != a->src.addr.iflags ||
1114                     memcmp(&a->src.addr.v.a.mask, &b->src.addr.v.a.mask,
1115                     sizeof(a->src.addr.v.a.mask)))
1116                         return (1);
1117                 return (0);
1118         case PF_ADDR_NOROUTE:
1119                 return (0);
1120         case PF_ADDR_TABLE:
1121                 return (strcmp(a->src.addr.v.tblname, b->src.addr.v.tblname));
1122         }
1123         return (1);
1124 }
1125
1126 /* Compare two rules SRC port field for skiplist construction */
1127 int
1128 skip_cmp_src_port(struct pf_rule *a, struct pf_rule *b)
1129 {
1130         if (a->src.port_op == PF_OP_NONE || a->src.port_op != b->src.port_op ||
1131             a->src.port[0] != b->src.port[0] ||
1132             a->src.port[1] != b->src.port[1])
1133                 return (1);
1134         /* XXX if (a->proto != b->proto && a->proto != 0 && b->proto != 0
1135          *    && (a->proto == IPPROTO_TCP || a->proto == IPPROTO_UDP ||
1136          *    a->proto == IPPROTO_ICMP
1137          *      return (1);
1138          */
1139         return (0);
1140 }
1141
1142
1143 void
1144 skip_init(void)
1145 {
1146         struct {
1147                 char *name;
1148                 int skipnum;
1149                 int (*func)(struct pf_rule *, struct pf_rule *);
1150         } comps[] = PF_SKIP_COMPARITORS;
1151         int skipnum, i;
1152
1153         for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++) {
1154                 for (i = 0; i < sizeof(comps)/sizeof(*comps); i++)
1155                         if (comps[i].skipnum == skipnum) {
1156                                 skip_comparitors[skipnum] = comps[i].func;
1157                                 skip_comparitors_names[skipnum] = comps[i].name;
1158                         }
1159         }
1160         for (skipnum = 0; skipnum < PF_SKIP_COUNT; skipnum++)
1161                 if (skip_comparitors[skipnum] == NULL)
1162                         errx(1, "Need to add skip step comparitor to pfctl?!");
1163 }
1164
1165 /*
1166  * Add a host/netmask to a table
1167  */
1168 int
1169 add_opt_table(struct pfctl *pf, struct pf_opt_tbl **tbl, sa_family_t af,
1170     struct pf_rule_addr *addr)
1171 {
1172 #ifdef OPT_DEBUG
1173         char buf[128];
1174 #endif /* OPT_DEBUG */
1175         static int tablenum = 0;
1176         struct node_host node_host;
1177
1178         if (*tbl == NULL) {
1179                 if ((*tbl = calloc(1, sizeof(**tbl))) == NULL ||
1180                     ((*tbl)->pt_buf = calloc(1, sizeof(*(*tbl)->pt_buf))) ==
1181                     NULL)
1182                         err(1, "calloc");
1183                 (*tbl)->pt_buf->pfrb_type = PFRB_ADDRS;
1184                 SIMPLEQ_INIT(&(*tbl)->pt_nodes);
1185
1186                 /* This is just a temporary table name */
1187                 snprintf((*tbl)->pt_name, sizeof((*tbl)->pt_name), "%s%d",
1188                     PF_OPT_TABLE_PREFIX, tablenum++);
1189                 DEBUG("creating table <%s>", (*tbl)->pt_name);
1190         }
1191
1192         memset(&node_host, 0, sizeof(node_host));
1193         node_host.af = af;
1194         node_host.addr = addr->addr;
1195
1196 #ifdef OPT_DEBUG
1197         DEBUG("<%s> adding %s/%d", (*tbl)->pt_name, inet_ntop(af,
1198             &node_host.addr.v.a.addr, buf, sizeof(buf)),
1199             unmask(&node_host.addr.v.a.mask, af));
1200 #endif /* OPT_DEBUG */
1201
1202         if (append_addr_host((*tbl)->pt_buf, &node_host, 0, 0)) {
1203                 warn("failed to add host");
1204                 return (1);
1205         }
1206         if (pf->opts & PF_OPT_VERBOSE) {
1207                 struct node_tinit *ti;
1208
1209                 if ((ti = calloc(1, sizeof(*ti))) == NULL)
1210                         err(1, "malloc");
1211                 if ((ti->host = malloc(sizeof(*ti->host))) == NULL)
1212                         err(1, "malloc");
1213                 memcpy(ti->host, &node_host, sizeof(*ti->host));
1214                 SIMPLEQ_INSERT_TAIL(&(*tbl)->pt_nodes, ti, entries);
1215         }
1216
1217         (*tbl)->pt_rulecount++;
1218         if ((*tbl)->pt_rulecount == TABLE_THRESHOLD)
1219                 DEBUG("table <%s> now faster than skip steps", (*tbl)->pt_name);
1220
1221         return (0);
1222 }
1223
1224
1225 /*
1226  * Do the dirty work of choosing an unused table name and creating it.
1227  * (be careful with the table name, it might already be used in another anchor)
1228  */
1229 int
1230 pf_opt_create_table(struct pfctl *pf, struct pf_opt_tbl *tbl)
1231 {
1232         static int tablenum;
1233         struct pfr_table *t;
1234
1235         if (table_buffer.pfrb_type == 0) {
1236                 /* Initialize the list of tables */
1237                 table_buffer.pfrb_type = PFRB_TABLES;
1238                 for (;;) {
1239                         pfr_buf_grow(&table_buffer, table_buffer.pfrb_size);
1240                         table_buffer.pfrb_size = table_buffer.pfrb_msize;
1241                         if (pfr_get_tables(NULL, table_buffer.pfrb_caddr,
1242                             &table_buffer.pfrb_size, PFR_FLAG_ALLRSETS))
1243                                 err(1, "pfr_get_tables");
1244                         if (table_buffer.pfrb_size <= table_buffer.pfrb_msize)
1245                                 break;
1246                 }
1247                 table_identifier = arc4random();
1248         }
1249
1250         /* XXX would be *really* nice to avoid duplicating identical tables */
1251
1252         /* Now we have to pick a table name that isn't used */
1253 again:
1254         DEBUG("translating temporary table <%s> to <%s%x_%d>", tbl->pt_name,
1255             PF_OPT_TABLE_PREFIX, table_identifier, tablenum);
1256         snprintf(tbl->pt_name, sizeof(tbl->pt_name), "%s%x_%d",
1257             PF_OPT_TABLE_PREFIX, table_identifier, tablenum);
1258         PFRB_FOREACH(t, &table_buffer) {
1259                 if (strcasecmp(t->pfrt_name, tbl->pt_name) == 0) {
1260                         /* Collision.  Try again */
1261                         DEBUG("wow, table <%s> in use.  trying again",
1262                             tbl->pt_name);
1263                         table_identifier = arc4random();
1264                         goto again;
1265                 }
1266         }
1267         tablenum++;
1268
1269
1270         if (pfctl_define_table(tbl->pt_name, PFR_TFLAG_CONST, 1, pf->anchor,
1271             tbl->pt_buf, pf->tticket)) {
1272                 warn("failed to create table %s", tbl->pt_name);
1273                 return (1);
1274         }
1275         return (0);
1276 }
1277
1278 /*
1279  * Partition the flat ruleset into a list of distinct superblocks
1280  */
1281 int
1282 construct_superblocks(struct pfctl *pf, struct pf_opt_queue *opt_queue,
1283     struct superblocks *superblocks)
1284 {
1285         struct superblock *block = NULL;
1286         struct pf_opt_rule *por;
1287         int i;
1288
1289         while (!TAILQ_EMPTY(opt_queue)) {
1290                 por = TAILQ_FIRST(opt_queue);
1291                 TAILQ_REMOVE(opt_queue, por, por_entry);
1292                 if (block == NULL || !superblock_inclusive(block, por)) {
1293                         if ((block = calloc(1, sizeof(*block))) == NULL) {
1294                                 warn("calloc");
1295                                 return (1);
1296                         }
1297                         TAILQ_INIT(&block->sb_rules);
1298                         for (i = 0; i < PF_SKIP_COUNT; i++)
1299                                 TAILQ_INIT(&block->sb_skipsteps[i]);
1300                         TAILQ_INSERT_TAIL(superblocks, block, sb_entry);
1301                 }
1302                 TAILQ_INSERT_TAIL(&block->sb_rules, por, por_entry);
1303         }
1304
1305         return (0);
1306 }
1307
1308
1309 /*
1310  * Compare two rule addresses
1311  */
1312 int
1313 addrs_equal(struct pf_rule_addr *a, struct pf_rule_addr *b)
1314 {
1315         if (a->neg != b->neg)
1316                 return (0);
1317         return (memcmp(&a->addr, &b->addr, sizeof(a->addr)) == 0);
1318 }
1319
1320
1321 /*
1322  * The addresses are not equal, but can we combine them into one table?
1323  */
1324 int
1325 addrs_combineable(struct pf_rule_addr *a, struct pf_rule_addr *b)
1326 {
1327         if (a->addr.type != PF_ADDR_ADDRMASK ||
1328             b->addr.type != PF_ADDR_ADDRMASK)
1329                 return (0);
1330         if (a->neg != b->neg || a->port_op != b->port_op ||
1331             a->port[0] != b->port[0] || a->port[1] != b->port[1])
1332                 return (0);
1333         return (1);
1334 }
1335
1336
1337 /*
1338  * Are we allowed to combine these two rules
1339  */
1340 int
1341 rules_combineable(struct pf_rule *p1, struct pf_rule *p2)
1342 {
1343         struct pf_rule a, b;
1344
1345         comparable_rule(&a, p1, COMBINED);
1346         comparable_rule(&b, p2, COMBINED);
1347         return (memcmp(&a, &b, sizeof(a)) == 0);
1348 }
1349
1350
1351 /*
1352  * Can a rule be included inside a superblock
1353  */
1354 int
1355 superblock_inclusive(struct superblock *block, struct pf_opt_rule *por)
1356 {
1357         struct pf_rule a, b;
1358         int i, j;
1359
1360         /* First check for hard breaks */
1361         for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++) {
1362                 if (pf_rule_desc[i].prf_type == BARRIER) {
1363                         for (j = 0; j < pf_rule_desc[i].prf_size; j++)
1364                                 if (((char *)&por->por_rule)[j +
1365                                     pf_rule_desc[i].prf_offset] != 0)
1366                                         return (0);
1367                 }
1368         }
1369
1370         /* 'anchor' heads and per-rule src-track are also hard breaks */
1371         if (por->por_anchor[0] != '\0' ||
1372             (por->por_rule.rule_flag & PFRULE_RULESRCTRACK))
1373                 return (0);
1374
1375         comparable_rule(&a, &TAILQ_FIRST(&block->sb_rules)->por_rule, NOMERGE);
1376         comparable_rule(&b, &por->por_rule, NOMERGE);
1377         if (strcmp(TAILQ_FIRST(&block->sb_rules)->por_anchor,
1378             por->por_anchor) == 0 && memcmp(&a, &b, sizeof(a)) == 0)
1379                 return (1);
1380
1381 #ifdef OPT_DEBUG
1382         for (i = 0; i < sizeof(por->por_rule); i++) {
1383                 int closest = -1;
1384                 if (((u_int8_t *)&a)[i] != ((u_int8_t *)&b)[i]) {
1385                         for (j = 0; j < sizeof(pf_rule_desc) /
1386                             sizeof(*pf_rule_desc); j++) {
1387                                 if (i >= pf_rule_desc[j].prf_offset &&
1388                                     i < pf_rule_desc[j].prf_offset +
1389                                     pf_rule_desc[j].prf_size) {
1390                                         DEBUG("superblock break @ %d due to %s",
1391                                             por->por_rule.nr,
1392                                             pf_rule_desc[j].prf_name);
1393                                         return (0);
1394                                 }
1395                                 if (i > pf_rule_desc[j].prf_offset) {
1396                                         if (closest == -1 ||
1397                                             i-pf_rule_desc[j].prf_offset <
1398                                             i-pf_rule_desc[closest].prf_offset)
1399                                                 closest = j;
1400                                 }
1401                         }
1402
1403                         if (closest >= 0)
1404                                 DEBUG("superblock break @ %d on %s+%xh",
1405                                     por->por_rule.nr,
1406                                     pf_rule_desc[closest].prf_name,
1407                                     i - pf_rule_desc[closest].prf_offset -
1408                                     pf_rule_desc[closest].prf_size);
1409                         else
1410                                 DEBUG("superblock break @ %d on field @ %d",
1411                                     por->por_rule.nr, i);
1412                         return (0);
1413                 }
1414         }
1415 #endif /* OPT_DEBUG */
1416
1417         return (0);
1418 }
1419
1420
1421 /*
1422  * Make a rule that can directly compared by memcmp()
1423  */
1424 void
1425 comparable_rule(struct pf_rule *dst, const struct pf_rule *src, int type)
1426 {
1427         int i;
1428         /*
1429          * To simplify the comparison, we just zero out the fields that are
1430          * allowed to be different and then do a simple memcmp()
1431          */
1432         memcpy(dst, src, sizeof(*dst));
1433         for (i = 0; i < sizeof(pf_rule_desc)/sizeof(*pf_rule_desc); i++)
1434                 if (pf_rule_desc[i].prf_type >= type) {
1435 #ifdef OPT_DEBUG
1436                         assert(pf_rule_desc[i].prf_type != NEVER ||
1437                             *(((char *)dst) + pf_rule_desc[i].prf_offset) == 0);
1438 #endif /* OPT_DEBUG */
1439                         memset(((char *)dst) + pf_rule_desc[i].prf_offset, 0,
1440                             pf_rule_desc[i].prf_size);
1441                 }
1442 }
1443
1444
1445 /*
1446  * Remove superset information from two rules so we can directly compare them
1447  * with memcmp()
1448  */
1449 void
1450 exclude_supersets(struct pf_rule *super, struct pf_rule *sub)
1451 {
1452         if (super->ifname[0] == '\0')
1453                 memset(sub->ifname, 0, sizeof(sub->ifname));
1454         if (super->direction == PF_INOUT)
1455                 sub->direction = PF_INOUT;
1456         if ((super->proto == 0 || super->proto == sub->proto) &&
1457             super->flags == 0 && super->flagset == 0 && (sub->flags ||
1458             sub->flagset)) {
1459                 sub->flags = super->flags;
1460                 sub->flagset = super->flagset;
1461         }
1462         if (super->proto == 0)
1463                 sub->proto = 0;
1464
1465         if (super->src.port_op == 0) {
1466                 sub->src.port_op = 0;
1467                 sub->src.port[0] = 0;
1468                 sub->src.port[1] = 0;
1469         }
1470         if (super->dst.port_op == 0) {
1471                 sub->dst.port_op = 0;
1472                 sub->dst.port[0] = 0;
1473                 sub->dst.port[1] = 0;
1474         }
1475
1476         if (super->src.addr.type == PF_ADDR_ADDRMASK && !super->src.neg &&
1477             !sub->src.neg && super->src.addr.v.a.mask.addr32[0] == 0 &&
1478             super->src.addr.v.a.mask.addr32[1] == 0 &&
1479             super->src.addr.v.a.mask.addr32[2] == 0 &&
1480             super->src.addr.v.a.mask.addr32[3] == 0)
1481                 memset(&sub->src.addr, 0, sizeof(sub->src.addr));
1482         else if (super->src.addr.type == PF_ADDR_ADDRMASK &&
1483             sub->src.addr.type == PF_ADDR_ADDRMASK &&
1484             super->src.neg == sub->src.neg &&
1485             super->af == sub->af &&
1486             unmask(&super->src.addr.v.a.mask, super->af) <
1487             unmask(&sub->src.addr.v.a.mask, sub->af) &&
1488             super->src.addr.v.a.addr.addr32[0] ==
1489             (sub->src.addr.v.a.addr.addr32[0] &
1490             super->src.addr.v.a.mask.addr32[0]) &&
1491             super->src.addr.v.a.addr.addr32[1] ==
1492             (sub->src.addr.v.a.addr.addr32[1] &
1493             super->src.addr.v.a.mask.addr32[1]) &&
1494             super->src.addr.v.a.addr.addr32[2] ==
1495             (sub->src.addr.v.a.addr.addr32[2] &
1496             super->src.addr.v.a.mask.addr32[2]) &&
1497             super->src.addr.v.a.addr.addr32[3] ==
1498             (sub->src.addr.v.a.addr.addr32[3] &
1499             super->src.addr.v.a.mask.addr32[3])) {
1500                 /* sub->src.addr is a subset of super->src.addr/mask */
1501                 memcpy(&sub->src.addr, &super->src.addr, sizeof(sub->src.addr));
1502         }
1503
1504         if (super->dst.addr.type == PF_ADDR_ADDRMASK && !super->dst.neg &&
1505             !sub->dst.neg && super->dst.addr.v.a.mask.addr32[0] == 0 &&
1506             super->dst.addr.v.a.mask.addr32[1] == 0 &&
1507             super->dst.addr.v.a.mask.addr32[2] == 0 &&
1508             super->dst.addr.v.a.mask.addr32[3] == 0)
1509                 memset(&sub->dst.addr, 0, sizeof(sub->dst.addr));
1510         else if (super->dst.addr.type == PF_ADDR_ADDRMASK &&
1511             sub->dst.addr.type == PF_ADDR_ADDRMASK &&
1512             super->dst.neg == sub->dst.neg &&
1513             super->af == sub->af &&
1514             unmask(&super->dst.addr.v.a.mask, super->af) <
1515             unmask(&sub->dst.addr.v.a.mask, sub->af) &&
1516             super->dst.addr.v.a.addr.addr32[0] ==
1517             (sub->dst.addr.v.a.addr.addr32[0] &
1518             super->dst.addr.v.a.mask.addr32[0]) &&
1519             super->dst.addr.v.a.addr.addr32[1] ==
1520             (sub->dst.addr.v.a.addr.addr32[1] &
1521             super->dst.addr.v.a.mask.addr32[1]) &&
1522             super->dst.addr.v.a.addr.addr32[2] ==
1523             (sub->dst.addr.v.a.addr.addr32[2] &
1524             super->dst.addr.v.a.mask.addr32[2]) &&
1525             super->dst.addr.v.a.addr.addr32[3] ==
1526             (sub->dst.addr.v.a.addr.addr32[3] &
1527             super->dst.addr.v.a.mask.addr32[3])) {
1528                 /* sub->dst.addr is a subset of super->dst.addr/mask */
1529                 memcpy(&sub->dst.addr, &super->dst.addr, sizeof(sub->dst.addr));
1530         }
1531
1532         if (super->af == 0)
1533                 sub->af = 0;
1534 }
1535
1536
1537 void
1538 superblock_free(struct pfctl *pf, struct superblock *block)
1539 {
1540         struct pf_opt_rule *por;
1541         while ((por = TAILQ_FIRST(&block->sb_rules))) {
1542                 TAILQ_REMOVE(&block->sb_rules, por, por_entry);
1543                 if (por->por_src_tbl) {
1544                         if (por->por_src_tbl->pt_buf) {
1545                                 pfr_buf_clear(por->por_src_tbl->pt_buf);
1546                                 free(por->por_src_tbl->pt_buf);
1547                         }
1548                         free(por->por_src_tbl);
1549                 }
1550                 if (por->por_dst_tbl) {
1551                         if (por->por_dst_tbl->pt_buf) {
1552                                 pfr_buf_clear(por->por_dst_tbl->pt_buf);
1553                                 free(por->por_dst_tbl->pt_buf);
1554                         }
1555                         free(por->por_dst_tbl);
1556                 }
1557                 free(por);
1558         }
1559         if (block->sb_profiled_block)
1560                 superblock_free(pf, block->sb_profiled_block);
1561         free(block);
1562 }
1563