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