usr.sbin/pfctl/pfctl_optimize.c

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