usr.sbin/pfctl/pfctl_optimize.c

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