*/
#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 <pcap-stdinc.h>
+#else /* WIN32 */
+#if HAVE_INTTYPES_H
+#include <inttypes.h>
+#elif HAVE_STDINT_H
+#include <stdint.h>
+#endif
+#ifdef HAVE_SYS_BITYPES_H
+#include <sys/bitypes.h>
+#endif
+#include <sys/types.h>
+#endif /* WIN32 */
+
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
+#include <string.h>
#include <errno.h>
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.
*/
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 *);
* 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)
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;
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;
/*
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
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}
* (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;
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.
/*
* 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])
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);
/*
* 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);
{
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;
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;
}
/*
* 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)
*
* 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;
*/
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();
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");
* 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");
}
{
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,
/*
* 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;
/*
{
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.
*/
projects / libpcap / blobdiff