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