X-Git-Url: https://git.tcpdump.org/libpcap/blobdiff_plain/1c26c7de8a932fc5c1802246fa048bc00bca691e..9df01dba7d4a698dbfec57e678e5a73dae93fa6d:/optimize.c?ds=sidebyside diff --git a/optimize.c b/optimize.c index 00154197..283a6de3 100644 --- a/optimize.c +++ b/optimize.c @@ -30,6 +30,7 @@ #include #include #include +#include #include #include @@ -212,17 +213,17 @@ lowest_set_bit(int mask) */ struct valnode { int code; - int v0, v1; - int val; + bpf_u_int32 v0, v1; + int val; /* the value number */ struct valnode *next; }; /* Integer constants mapped with the load immediate opcode. */ -#define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0L) +#define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U) struct vmapinfo { int is_const; - bpf_int32 const_val; + bpf_u_int32 const_val; }; typedef struct { @@ -312,8 +313,8 @@ typedef struct { #define MODULUS 213 struct valnode *hashtbl[MODULUS]; - int curval; - int maxval; + bpf_u_int32 curval; + bpf_u_int32 maxval; struct vmapinfo *vmap; struct valnode *vnode_base; @@ -350,7 +351,7 @@ static void intern_blocks(opt_state_t *, struct icode *); static void find_inedges(opt_state_t *, struct block *); #ifdef BDEBUG -static void opt_dump(compiler_state_t *, struct icode *); +static void opt_dump(opt_state_t *, struct icode *); #endif #ifndef MAX @@ -495,8 +496,11 @@ find_closure(opt_state_t *opt_state, struct block *root) } /* - * Return the register number that is used by s. If A and X are both - * used, return AX_ATOM. If no register is used, return -1. + * Return the register number that is used by s. + * + * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X + * are used, the scratch memory location's number if a scratch memory + * location is used (e.g., 0 for M[0]), or -1 if none of those are used. * * The implementation should probably change to an array access. */ @@ -516,8 +520,12 @@ atomuse(struct stmt *s) case BPF_LD: case BPF_LDX: + /* + * As there are fewer than 2^31 memory locations, + * s->k should be convertable to int without problems. + */ return (BPF_MODE(c) == BPF_IND) ? X_ATOM : - (BPF_MODE(c) == BPF_MEM) ? s->k : -1; + (BPF_MODE(c) == BPF_MEM) ? (int)s->k : -1; case BPF_ST: return A_ATOM; @@ -675,21 +683,40 @@ init_val(opt_state_t *opt_state) memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl); } -/* Because we really don't have an IR, this stuff is a little messy. */ -static int -F(opt_state_t *opt_state, int code, int v0, int v1) +/* + * Because we really don't have an IR, this stuff is a little messy. + * + * This routine looks in the table of existing value number for a value + * with generated from an operation with the specified opcode and + * the specified values. If it finds it, it returns its value number, + * otherwise it makes a new entry in the table and returns the + * value number of that entry. + */ +static bpf_u_int32 +F(opt_state_t *opt_state, int code, bpf_u_int32 v0, bpf_u_int32 v1) { u_int hash; - int val; + bpf_u_int32 val; struct valnode *p; - hash = (u_int)code ^ ((u_int)v0 << 4) ^ ((u_int)v1 << 8); + hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8); hash %= MODULUS; for (p = opt_state->hashtbl[hash]; p; p = p->next) if (p->code == code && p->v0 == v0 && p->v1 == v1) return p->val; + /* + * Not found. Allocate a new value, and assign it a new + * value number. + * + * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we + * increment it before using it as the new value number, which + * means we never assign VAL_UNKNOWN. + * + * XXX - unless we overflow, but we probably won't have 2^32-1 + * values; we treat 32 bits as effectively infinite. + */ val = ++opt_state->curval; if (BPF_MODE(code) == BPF_IMM && (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) { @@ -708,7 +735,7 @@ F(opt_state_t *opt_state, int code, int v0, int v1) } static inline void -vstore(struct stmt *s, int *valp, int newval, int alter) +vstore(struct stmt *s, bpf_u_int32 *valp, bpf_u_int32 newval, int alter) { if (alter && newval != VAL_UNKNOWN && *valp == newval) s->code = NOP; @@ -721,7 +748,7 @@ vstore(struct stmt *s, int *valp, int newval, int alter) * (Unary operators are handled elsewhere.) */ static void -fold_op(opt_state_t *opt_state, struct stmt *s, int v0, int v1) +fold_op(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 v0, bpf_u_int32 v1) { bpf_u_int32 a, b; @@ -831,7 +858,7 @@ opt_peep(opt_state_t *opt_state, struct block *b) { struct slist *s; struct slist *next, *last; - int val; + bpf_u_int32 val; s = b->stmts; if (s == 0) @@ -1032,7 +1059,7 @@ opt_peep(opt_state_t *opt_state, struct block *b) if (b->s.code == (BPF_JMP|BPF_K|BPF_JSET)) { if (b->s.k == 0) JT(b) = JF(b); - if ((u_int)b->s.k == 0xffffffffU) + if (b->s.k == 0xffffffffU) JF(b) = JT(b); } /* @@ -1042,7 +1069,7 @@ opt_peep(opt_state_t *opt_state, struct block *b) */ val = b->val[X_ATOM]; if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) { - bpf_int32 v = opt_state->vmap[val].const_val; + bpf_u_int32 v = opt_state->vmap[val].const_val; b->s.code &= ~BPF_X; b->s.k = v; } @@ -1052,7 +1079,7 @@ opt_peep(opt_state_t *opt_state, struct block *b) */ val = b->val[A_ATOM]; if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) { - bpf_int32 v = opt_state->vmap[val].const_val; + bpf_u_int32 v = opt_state->vmap[val].const_val; switch (BPF_OP(b->s.code)) { case BPF_JEQ: @@ -1060,11 +1087,11 @@ opt_peep(opt_state_t *opt_state, struct block *b) break; case BPF_JGT: - v = (unsigned)v > (unsigned)b->s.k; + v = v > b->s.k; break; case BPF_JGE: - v = (unsigned)v >= (unsigned)b->s.k; + v = v >= b->s.k; break; case BPF_JSET: @@ -1090,10 +1117,10 @@ opt_peep(opt_state_t *opt_state, struct block *b) * evaluation and code transformations weren't folded together. */ static void -opt_stmt(opt_state_t *opt_state, struct stmt *s, int val[], int alter) +opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter) { int op; - int v; + bpf_u_int32 v; switch (s->code) { @@ -1142,7 +1169,23 @@ opt_stmt(opt_state_t *opt_state, struct stmt *s, int val[], int alter) case BPF_ALU|BPF_NEG: if (alter && opt_state->vmap[val[A_ATOM]].is_const) { s->code = BPF_LD|BPF_IMM; - s->k = -opt_state->vmap[val[A_ATOM]].const_val; + /* + * Do this negation as unsigned arithmetic; that's + * what modern BPF engines do, and it guarantees + * that all possible values can be negated. (Yeah, + * negating 0x80000000, the minimum signed 32-bit + * two's-complement value, results in 0x80000000, + * so it's still negative, but we *should* be doing + * all unsigned arithmetic here, to match what + * modern BPF engines do.) + * + * Express it as 0U - (unsigned value) so that we + * don't get compiler warnings about negating an + * unsigned value and don't get UBSan warnings + * about the result of negating 0x80000000 being + * undefined. + */ + s->k = 0U - opt_state->vmap[val[A_ATOM]].const_val; val[A_ATOM] = K(s->k); } else @@ -1219,14 +1262,8 @@ opt_stmt(opt_state_t *opt_state, struct stmt *s, int val[], int alter) else { s->code = BPF_ALU|BPF_K|op; s->k = opt_state->vmap[val[X_ATOM]].const_val; - /* - * XXX - we need to make up our minds - * as to what integers are signed and - * what integers are unsigned in BPF - * programs and in our IR. - */ if ((op == BPF_LSH || op == BPF_RSH) && - (s->k < 0 || s->k > 31)) + s->k > 31) opt_error(opt_state, "shift by more than 31 bits"); opt_state->done = 0; @@ -1352,7 +1389,7 @@ opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts) struct slist *s; struct edge *p; int i; - bpf_int32 aval, xval; + bpf_u_int32 aval, xval; #if 0 for (s = b->stmts; s && s->next; s = s->next) @@ -1471,7 +1508,7 @@ static struct block * fold_edge(struct block *child, struct edge *ep) { int sense; - int aval0, aval1, oval0, oval1; + bpf_u_int32 aval0, aval1, oval0, oval1; int code = ep->code; if (code < 0) { @@ -1577,7 +1614,8 @@ opt_j(opt_state_t *opt_state, struct edge *ep) static void or_pullup(opt_state_t *opt_state, struct block *b) { - int val, at_top; + bpf_u_int32 val; + int at_top; struct block *pull; struct block **diffp, **samep; struct edge *ep; @@ -1669,7 +1707,8 @@ or_pullup(opt_state_t *opt_state, struct block *b) static void and_pullup(opt_state_t *opt_state, struct block *b) { - int val, at_top; + bpf_u_int32 val; + int at_top; struct block *pull; struct block **diffp, **samep; struct edge *ep; @@ -1853,7 +1892,7 @@ opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts) #ifdef BDEBUG if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) { printf("opt_loop(root, %d) begin\n", do_stmts); - opt_dump(cstate, ic); + opt_dump(opt_state, ic); } #endif do { @@ -1867,7 +1906,7 @@ opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts) #ifdef BDEBUG if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) { printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done); - opt_dump(cstate, ic); + opt_dump(opt_state, ic); } #endif } while (!opt_state->done); @@ -1895,14 +1934,14 @@ bpf_optimize(struct icode *ic, char *errbuf) #ifdef BDEBUG if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) { printf("after intern_blocks()\n"); - opt_dump(cstate, ic); + opt_dump(&opt_state, ic); } #endif opt_root(&ic->root); #ifdef BDEBUG if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) { printf("after opt_root()\n"); - opt_dump(cstate, ic); + opt_dump(&opt_state, ic); } #endif opt_cleanup(&opt_state); @@ -2030,7 +2069,7 @@ opt_error(opt_state_t *opt_state, const char *fmt, ...) if (opt_state->errbuf != NULL) { va_start(ap, fmt); - (void)pcap_vsnprintf(opt_state->errbuf, + (void)vsnprintf(opt_state->errbuf, PCAP_ERRBUF_SIZE, fmt, ap); va_end(ap); } @@ -2143,7 +2182,6 @@ opt_init(opt_state_t *opt_state, struct icode *ic) opt_state->n_edges = 2 * opt_state->n_blocks; opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges)); if (opt_state->edges == NULL) { - free(opt_state->blocks); opt_error(opt_state, "malloc"); } @@ -2152,8 +2190,6 @@ opt_init(opt_state_t *opt_state, struct icode *ic) */ opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels)); if (opt_state->levels == NULL) { - free(opt_state->edges); - free(opt_state->blocks); opt_error(opt_state, "malloc"); } @@ -2164,9 +2200,6 @@ opt_init(opt_state_t *opt_state, struct icode *ic) opt_state->space = (bpf_u_int32 *)malloc(2 * opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->space) + opt_state->n_edges * opt_state->edgewords * sizeof(*opt_state->space)); if (opt_state->space == NULL) { - free(opt_state->levels); - free(opt_state->edges); - free(opt_state->blocks); opt_error(opt_state, "malloc"); } p = opt_state->space; @@ -2206,19 +2239,10 @@ opt_init(opt_state_t *opt_state, struct icode *ic) opt_state->maxval = 3 * max_stmts; opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap)); if (opt_state->vmap == NULL) { - free(opt_state->space); - free(opt_state->levels); - free(opt_state->edges); - free(opt_state->blocks); opt_error(opt_state, "malloc"); } opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base)); if (opt_state->vnode_base == NULL) { - free(opt_state->vmap); - free(opt_state->space); - free(opt_state->levels); - free(opt_state->edges); - free(opt_state->blocks); opt_error(opt_state, "malloc"); } } @@ -2438,7 +2462,7 @@ filled: * done with the filter program. See the pcap man page. */ struct bpf_insn * -icode_to_fcode(struct icode *ic, struct block *root, u_int *lenp, +icode_to_fcode(struct icode *ic, struct block *root, u_int *lenp, char *errbuf) { u_int n; @@ -2462,7 +2486,7 @@ icode_to_fcode(struct icode *ic, struct block *root, u_int *lenp, fp = (struct bpf_insn *)malloc(sizeof(*fp) * n); if (fp == NULL) { - (void)pcap_snprintf(errbuf, PCAP_ERRBUF_SIZE, + (void)snprintf(errbuf, PCAP_ERRBUF_SIZE, "malloc"); free(fp); return NULL; @@ -2489,7 +2513,7 @@ conv_error(conv_state_t *conv_state, const char *fmt, ...) va_list ap; va_start(ap, fmt); - (void)pcap_vsnprintf(conv_state->errbuf, + (void)vsnprintf(conv_state->errbuf, PCAP_ERRBUF_SIZE, fmt, ap); va_end(ap); longjmp(conv_state->top_ctx, 1); @@ -2513,7 +2537,7 @@ install_bpf_program(pcap_t *p, struct bpf_program *fp) * Validate the program. */ if (!pcap_validate_filter(fp->bf_insns, fp->bf_len)) { - pcap_snprintf(p->errbuf, sizeof(p->errbuf), + snprintf(p->errbuf, sizeof(p->errbuf), "BPF program is not valid"); return (-1); } @@ -2605,16 +2629,16 @@ dot_dump_edge(struct icode *ic, struct block *block, FILE *out) * After install graphviz on http://www.graphviz.org/, save it as bpf.dot * and run `dot -Tpng -O bpf.dot' to draw the graph. */ -static void -dot_dump(compiler_state_t *cstate, struct icode *ic) +static int +dot_dump(struct icode *ic, char *errbuf) { struct bpf_program f; FILE *out = stdout; memset(bids, 0, sizeof bids); - f.bf_insns = icode_to_fcode(cstate, ic, ic->root, &f.bf_len); + f.bf_insns = icode_to_fcode(ic, ic->root, &f.bf_len, errbuf); if (f.bf_insns == NULL) - return; + return -1; fprintf(out, "digraph BPF {\n"); unMarkAll(ic); @@ -2624,32 +2648,39 @@ dot_dump(compiler_state_t *cstate, struct icode *ic) fprintf(out, "}\n"); free((char *)f.bf_insns); + return 0; } -static void -plain_dump(compiler_state_t *cstate, struct icode *ic) +static int +plain_dump(struct icode *ic, char *errbuf) { struct bpf_program f; memset(bids, 0, sizeof bids); - f.bf_insns = icode_to_fcode(cstate, ic, ic->root, &f.bf_len); + f.bf_insns = icode_to_fcode(ic, ic->root, &f.bf_len, errbuf); if (f.bf_insns == NULL) - return; + return -1; bpf_dump(&f, 1); putchar('\n'); free((char *)f.bf_insns); + return 0; } static void -opt_dump(compiler_state_t *cstate, struct icode *ic) +opt_dump(opt_state_t *opt_state, struct icode *ic) { + int status; + char errbuf[PCAP_ERRBUF_SIZE]; + /* * If the CFG, in DOT format, is requested, output it rather than * the code that would be generated from that graph. */ if (pcap_print_dot_graph) - dot_dump(cstate, ic); + status = dot_dump(ic, errbuf); else - plain_dump(cstate, ic); + status = plain_dump(ic, errbuf); + if (status == -1) + opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf); } #endif