X-Git-Url: https://git.tcpdump.org/libpcap/blobdiff_plain/e67d61b9b3025469f6a1036d1d009d23a2b94244..02d7ed17b6d8bf1a461f9794781f45785e25623c:/optimize.c diff --git a/optimize.c b/optimize.c index 748fc42b..6bbda956 100644 --- a/optimize.c +++ b/optimize.c @@ -22,16 +22,31 @@ */ #ifndef lint static const char rcsid[] _U_ = - "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.80 2004-11-09 01:20:18 guy Exp $ (LBL)"; + "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.91 2008-01-02 04:16:46 guy Exp $ (LBL)"; #endif #ifdef HAVE_CONFIG_H #include "config.h" #endif +#ifdef WIN32 +#include +#else /* WIN32 */ +#if HAVE_INTTYPES_H +#include +#elif HAVE_STDINT_H +#include +#endif +#ifdef HAVE_SYS_BITYPES_H +#include +#endif +#include +#endif /* WIN32 */ + #include #include #include +#include #include @@ -47,6 +62,15 @@ static const char rcsid[] _U_ = extern int dflag; #endif +#if defined(MSDOS) && !defined(__DJGPP__) +extern int _w32_ffs (int mask); +#define ffs _w32_ffs +#endif + +#if defined(WIN32) && defined (_MSC_VER) +int ffs(int mask); +#endif + /* * Represents a deleted instruction. */ @@ -128,10 +152,10 @@ static void deadstmt(struct stmt *, struct stmt *[]); static void opt_deadstores(struct block *); static struct block *fold_edge(struct block *, struct edge *); static inline int eq_blk(struct block *, struct block *); -static int slength(struct slist *); +static u_int slength(struct slist *); static int count_blocks(struct block *); static void number_blks_r(struct block *); -static int count_stmts(struct block *); +static u_int count_stmts(struct block *); static int convert_code_r(struct block *); #ifdef BDEBUG static void opt_dump(struct block *); @@ -432,10 +456,12 @@ atomdef(s) * Compute the sets of registers used, defined, and killed by 'b'. * * "Used" means that a statement in 'b' uses the register before any - * statement in 'b' defines it. + * statement in 'b' defines it, i.e. it uses the value left in + * that register by a predecessor block of this block. * "Defined" means that a statement in 'b' defines it. * "Killed" means that a statement in 'b' defines it before any - * statement in 'b' uses it. + * statement in 'b' uses it, i.e. it kills the value left in that + * register by a predecessor block of this block. */ static void compute_local_ud(b) @@ -616,7 +642,7 @@ fold_op(s, v0, v1) struct stmt *s; int v0, v1; { - bpf_int32 a, b; + bpf_u_int32 a, b; a = vmap[v0].const_val; b = vmap[v1].const_val; @@ -701,12 +727,20 @@ opt_peep(b) last = s; for (/*empty*/; /*empty*/; s = next) { + /* + * Skip over nops. + */ s = this_op(s); if (s == 0) - break; + break; /* nothing left in the block */ + + /* + * Find the next real instruction after that one + * (skipping nops). + */ next = this_op(s->next); if (next == 0) - break; + break; /* no next instruction */ last = next; /* @@ -745,6 +779,12 @@ opt_peep(b) if (ATOMELEM(b->out_use, X_ATOM)) continue; + /* + * Check that the instruction following the ldi + * is an addx, or it's an ldxms with an addx + * following it (with 0 or more nops between the + * ldxms and addx). + */ if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B)) add = next; else @@ -752,20 +792,23 @@ opt_peep(b) if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X)) continue; + /* + * Check that a tax follows that (with 0 or more + * nops between them). + */ tax = this_op(add->next); if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX)) continue; + /* + * Check that an ild follows that (with 0 or more + * nops between them). + */ ild = this_op(tax->next); if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD || BPF_MODE(ild->s.code) != BPF_IND) continue; /* - * XXX We need to check that X is not - * subsequently used. We know we can eliminate the - * accumulator modifications since it is defined - * by the last stmt of this sequence. - * * We want to turn this sequence: * * (004) ldi #0x2 {s} @@ -782,6 +825,16 @@ opt_peep(b) * (007) nop * (008) ild [x+2] * + * XXX We need to check that X is not + * subsequently used, because we want to change + * what'll be in it after this sequence. + * + * We know we can eliminate the accumulator + * modifications earlier in the sequence since + * it is defined by the last stmt of this sequence + * (i.e., the last statement of the sequence loads + * a value into the accumulator, so we can eliminate + * earlier operations on the accumulator). */ ild->s.k += s->s.k; s->s.code = NOP; @@ -870,6 +923,17 @@ opt_peep(b) if (b->s.k == 0xffffffff) JF(b) = JT(b); } + /* + * If we're comparing against the index register, and the index + * register is a known constant, we can just compare against that + * constant. + */ + val = b->val[X_ATOM]; + if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) { + bpf_int32 v = vmap[val].const_val; + b->s.code &= ~BPF_X; + b->s.k = v; + } /* * If the accumulator is a known constant, we can compute the * comparison result. @@ -1168,16 +1232,30 @@ opt_blk(b, do_stmts) /* * Initialize the atom values. - * If we have no predecessors, everything is undefined. - * Otherwise, we inherent our values from our predecessors. - * If any register has an ambiguous value (i.e. control paths are - * merging) give it the undefined value of 0. */ p = b->in_edges; - if (p == 0) + if (p == 0) { + /* + * We have no predecessors, so everything is undefined + * upon entry to this block. + */ memset((char *)b->val, 0, sizeof(b->val)); - else { + } else { + /* + * Inherit values from our predecessors. + * + * First, get the values from the predecessor along the + * first edge leading to this node. + */ memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val)); + /* + * Now look at all the other nodes leading to this node. + * If, for the predecessor along that edge, a register + * has a different value from the one we have (i.e., + * control paths are merging, and the merging paths + * assign different values to that register), give the + * register the undefined value of 0. + */ while ((p = p->next) != NULL) { for (i = 0; i < N_ATOMS; ++i) if (b->val[i] != p->pred->val[i]) @@ -1285,9 +1363,9 @@ fold_edge(child, ep) if (oval0 == oval1) /* - * The operands are identical, so the - * result is true if a true branch was - * taken to get here, otherwise false. + * The operands of the branch instructions are + * identical, so the result is true if a true + * branch was taken to get here, otherwise false. */ return sense ? JT(child) : JF(child); @@ -1295,8 +1373,16 @@ fold_edge(child, ep) /* * At this point, we only know the comparison if we * came down the true branch, and it was an equality - * comparison with a constant. We rely on the fact that - * distinct constants have distinct value numbers. + * comparison with a constant. + * + * I.e., if we came down the true branch, and the branch + * was an equality comparison with a constant, we know the + * accumulator contains that constant. If we came down + * the false branch, or the comparison wasn't with a + * constant, we don't know what was in the accumulator. + * + * We rely on the fact that distinct constants have distinct + * value numbers. */ return JF(child); @@ -1766,9 +1852,9 @@ intern_blocks(root) { struct block *p; int i, j; - int done; + int done1; /* don't shadow global */ top: - done = 1; + done1 = 1; for (i = 0; i < n_blocks; ++i) blocks[i]->link = 0; @@ -1792,15 +1878,15 @@ intern_blocks(root) if (JT(p) == 0) continue; if (JT(p)->link) { - done = 0; + done1 = 0; JT(p) = JT(p)->link; } if (JF(p)->link) { - done = 0; + done1 = 0; JF(p) = JF(p)->link; } } - if (!done) + if (!done1) goto top; } @@ -1818,11 +1904,11 @@ opt_cleanup() /* * Return the number of stmts in 's'. */ -static int +static u_int slength(s) struct slist *s; { - int n = 0; + u_int n = 0; for (; s; s = s->next) if (s->s.code != NOP) @@ -1884,11 +1970,11 @@ number_blks_r(p) * * an extra long jump if the false branch requires it (p->longjf). */ -static int +static u_int count_stmts(p) struct block *p; { - int n; + u_int n; if (p == 0 || isMarked(p)) return 0; @@ -1915,7 +2001,7 @@ opt_init(root) */ unMarkAll(); n = count_blocks(root); - blocks = (struct block **)malloc(n * sizeof(*blocks)); + blocks = (struct block **)calloc(n, sizeof(*blocks)); if (blocks == NULL) bpf_error("malloc"); unMarkAll(); @@ -1923,14 +2009,14 @@ opt_init(root) number_blks_r(root); n_edges = 2 * n_blocks; - edges = (struct edge **)malloc(n_edges * sizeof(*edges)); + edges = (struct edge **)calloc(n_edges, sizeof(*edges)); if (edges == NULL) bpf_error("malloc"); /* * The number of levels is bounded by the number of nodes. */ - levels = (struct block **)malloc(n_blocks * sizeof(*levels)); + levels = (struct block **)calloc(n_blocks, sizeof(*levels)); if (levels == NULL) bpf_error("malloc"); @@ -1977,8 +2063,8 @@ opt_init(root) * we'll need. */ maxval = 3 * max_stmts; - vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap)); - vnode_base = (struct valnode *)malloc(maxval * sizeof(*vnode_base)); + vmap = (struct vmapinfo *)calloc(maxval, sizeof(*vmap)); + vnode_base = (struct valnode *)calloc(maxval, sizeof(*vnode_base)); if (vmap == NULL || vnode_base == NULL) bpf_error("malloc"); } @@ -2067,7 +2153,7 @@ convert_code_r(p) { int i; int jt, jf; - char *ljerr = "%s for block-local relative jump: off=%d"; + const char *ljerr = "%s for block-local relative jump: off=%d"; #if 0 printf("code=%x off=%d %x %x\n", src->s.code, @@ -2159,13 +2245,27 @@ filled: /* * Convert flowgraph intermediate representation to the * BPF array representation. Set *lenp to the number of instructions. + * + * This routine does *NOT* leak the memory pointed to by fp. It *must + * not* do free(fp) before returning fp; doing so would make no sense, + * as the BPF array pointed to by the return value of icode_to_fcode() + * must be valid - it's being returned for use in a bpf_program structure. + * + * If it appears that icode_to_fcode() is leaking, the problem is that + * the program using pcap_compile() is failing to free the memory in + * the BPF program when it's done - the leak is in the program, not in + * the routine that happens to be allocating the memory. (By analogy, if + * a program calls fopen() without ever calling fclose() on the FILE *, + * it will leak the FILE structure; the leak is not in fopen(), it's in + * the program.) Change the program to use pcap_freecode() when it's + * done with the filter program. See the pcap man page. */ struct bpf_insn * icode_to_fcode(root, lenp) struct block *root; - int *lenp; + u_int *lenp; { - int n; + u_int n; struct bpf_insn *fp; /* @@ -2205,6 +2305,15 @@ install_bpf_program(pcap_t *p, struct bpf_program *fp) { size_t prog_size; + /* + * Validate the program. + */ + if (!bpf_validate(fp->bf_insns, fp->bf_len)) { + snprintf(p->errbuf, sizeof(p->errbuf), + "BPF program is not valid"); + return (-1); + } + /* * Free up any already installed program. */