sbin/pfctl/pfctl_optimize.c

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