X-Git-Url: https://git.tcpdump.org/libpcap/blobdiff_plain/f2d84366a864f7b41f59ef47334f6a53aa914b32..574bb301ff796c0840a285c0433d6885f9afdbca:/optimize.c

diff --git a/optimize.c b/optimize.c
index 9c8aa95c..2c9c4b39 100644
--- a/optimize.c
+++ b/optimize.c
@@ -103,7 +103,7 @@ pcap_set_print_dot_graph(int value)
  * Takes a 32-bit integer as an argument.
  *
  * If handed a non-zero value, returns the index of the lowest set bit,
- * counting upwards fro zero.
+ * counting upwards from zero.
  *
  * If handed zero, the results are platform- and compiler-dependent.
  * Keep it out of the light, don't give it any water, don't feed it
@@ -115,7 +115,7 @@ pcap_set_print_dot_graph(int value)
   /*
    * GCC 3.4 and later; we have __builtin_ctz().
    */
-  #define lowest_set_bit(mask) __builtin_ctz(mask)
+  #define lowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
 #elif defined(_MSC_VER)
   /*
    * Visual Studio; we support only 2005 and later, so use
@@ -127,7 +127,7 @@ pcap_set_print_dot_graph(int value)
 #pragma intrinsic(_BitScanForward)
 #endif
 
-static __forceinline int
+static __forceinline u_int
 lowest_set_bit(int mask)
 {
 	unsigned long bit;
@@ -138,14 +138,14 @@ lowest_set_bit(int mask)
 	 */
 	if (_BitScanForward(&bit, (unsigned int)mask) == 0)
 		abort();	/* mask is zero */
-	return (int)bit;
+	return (u_int)bit;
 }
 #elif defined(MSDOS) && defined(__DJGPP__)
   /*
    * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
    * we've already included.
    */
-  #define lowest_set_bit(mask)	(ffs((mask)) - 1)
+  #define lowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
 #elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
   /*
    * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
@@ -153,18 +153,18 @@ lowest_set_bit(int mask)
    * of the Single UNIX Specification).
    */
   #include <strings.h>
-  #define lowest_set_bit(mask)	(ffs((mask)) - 1)
+  #define lowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
 #else
 /*
  * None of the above.
  * Use a perfect-hash-function-based function.
  */
-static int
+static u_int
 lowest_set_bit(int mask)
 {
 	unsigned int v = (unsigned int)mask;
 
-	static const int MultiplyDeBruijnBitPosition[32] = {
+	static const u_int MultiplyDeBruijnBitPosition[32] = {
 		0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
 		31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
 	};
@@ -257,17 +257,17 @@ typedef struct {
 	 */
 	int non_branch_movement_performed;
 
-	int n_blocks;
+	u_int n_blocks;		/* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
 	struct block **blocks;
-	int n_edges;
+	u_int n_edges;		/* twice n_blocks, so guaranteed to be > 0 */
 	struct edge **edges;
 
 	/*
 	 * A bit vector set representation of the dominators.
 	 * We round up the set size to the next power of two.
 	 */
-	int nodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits */
-	int edgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits */
+	u_int nodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
+	u_int edgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
 	struct block **levels;
 	bpf_u_int32 *space;
 
@@ -292,32 +292,35 @@ typedef struct {
 
 /*
  * a := a intersect b
+ * n must be guaranteed to be > 0
  */
 #define SET_INTERSECT(a, b, n)\
 {\
 	register bpf_u_int32 *_x = a, *_y = b;\
-	register int _n = n;\
-	while (--_n >= 0) *_x++ &= *_y++;\
+	register u_int _n = n;\
+	do *_x++ &= *_y++; while (--_n != 0);\
 }
 
 /*
  * a := a - b
+ * n must be guaranteed to be > 0
  */
 #define SET_SUBTRACT(a, b, n)\
 {\
 	register bpf_u_int32 *_x = a, *_y = b;\
-	register int _n = n;\
-	while (--_n >= 0) *_x++ &=~ *_y++;\
+	register u_int _n = n;\
+	do *_x++ &=~ *_y++; while (--_n != 0);\
 }
 
 /*
  * a := a union b
+ * n must be guaranteed to be > 0
  */
 #define SET_UNION(a, b, n)\
 {\
 	register bpf_u_int32 *_x = a, *_y = b;\
-	register int _n = n;\
-	while (--_n >= 0) *_x++ |= *_y++;\
+	register u_int _n = n;\
+	do *_x++ |= *_y++; while (--_n != 0);\
 }
 
 	uset all_dom_sets;
@@ -414,7 +417,8 @@ find_levels(opt_state_t *opt_state, struct icode *ic)
 static void
 find_dom(opt_state_t *opt_state, struct block *root)
 {
-	int i;
+	u_int i;
+	int level;
 	struct block *b;
 	bpf_u_int32 *x;
 
@@ -422,16 +426,23 @@ find_dom(opt_state_t *opt_state, struct block *root)
 	 * Initialize sets to contain all nodes.
 	 */
 	x = opt_state->all_dom_sets;
+	/*
+	 * In opt_init(), we've made sure the product doesn't overflow.
+	 */
 	i = opt_state->n_blocks * opt_state->nodewords;
-	while (--i >= 0)
+	while (i != 0) {
+		--i;
 		*x++ = 0xFFFFFFFFU;
+	}
 	/* Root starts off empty. */
-	for (i = opt_state->nodewords; --i >= 0;)
+	for (i = opt_state->nodewords; i != 0;) {
+		--i;
 		root->dom[i] = 0;
+	}
 
 	/* root->level is the highest level no found. */
-	for (i = root->level; i >= 0; --i) {
-		for (b = opt_state->levels[i]; b; b = b->link) {
+	for (level = root->level; level >= 0; --level) {
+		for (b = opt_state->levels[level]; b; b = b->link) {
 			SET_INSERT(b->dom, b->id);
 			if (JT(b) == 0)
 				continue;
@@ -458,19 +469,25 @@ propedom(opt_state_t *opt_state, struct edge *ep)
 static void
 find_edom(opt_state_t *opt_state, struct block *root)
 {
-	int i;
+	u_int i;
 	uset x;
+	int level;
 	struct block *b;
 
 	x = opt_state->all_edge_sets;
-	for (i = opt_state->n_edges * opt_state->edgewords; --i >= 0; )
+	/*
+	 * In opt_init(), we've made sure the product doesn't overflow.
+	 */
+	for (i = opt_state->n_edges * opt_state->edgewords; i != 0; ) {
+		--i;
 		x[i] = 0xFFFFFFFFU;
+	}
 
 	/* root->level is the highest level no found. */
 	memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
 	memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
-	for (i = root->level; i >= 0; --i) {
-		for (b = opt_state->levels[i]; b != 0; b = b->link) {
+	for (level = root->level; level >= 0; --level) {
+		for (b = opt_state->levels[level]; b != 0; b = b->link) {
 			propedom(opt_state, &b->et);
 			propedom(opt_state, &b->ef);
 		}
@@ -487,7 +504,7 @@ find_edom(opt_state_t *opt_state, struct block *root)
 static void
 find_closure(opt_state_t *opt_state, struct block *root)
 {
-	int i;
+	int level;
 	struct block *b;
 
 	/*
@@ -497,8 +514,8 @@ find_closure(opt_state_t *opt_state, struct block *root)
 	      opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets));
 
 	/* root->level is the highest level no found. */
-	for (i = root->level; i >= 0; --i) {
-		for (b = opt_state->levels[i]; b; b = b->link) {
+	for (level = root->level; level >= 0; --level) {
+		for (b = opt_state->levels[level]; b; b = b->link) {
 			SET_INSERT(b->closure, b->id);
 			if (JT(b) == 0)
 				continue;
@@ -1674,7 +1691,7 @@ fold_edge(struct block *child, struct edge *ep)
 static void
 opt_j(opt_state_t *opt_state, struct edge *ep)
 {
-	register int i, k;
+	register u_int i, k;
 	register struct block *target;
 
 	/*
@@ -2116,7 +2133,8 @@ link_inedge(struct edge *parent, struct block *child)
 static void
 find_inedges(opt_state_t *opt_state, struct block *root)
 {
-	int i;
+	u_int i;
+	int level;
 	struct block *b;
 
 	for (i = 0; i < opt_state->n_blocks; ++i)
@@ -2126,8 +2144,8 @@ find_inedges(opt_state_t *opt_state, struct block *root)
 	 * Traverse the graph, adding each edge to the predecessor
 	 * list of its successors.  Skip the leaves (i.e. level 0).
 	 */
-	for (i = root->level; i > 0; --i) {
-		for (b = opt_state->levels[i]; b != 0; b = b->link) {
+	for (level = root->level; level > 0; --level) {
+		for (b = opt_state->levels[level]; b != 0; b = b->link) {
 			link_inedge(&b->et, JT(b));
 			link_inedge(&b->ef, JF(b));
 		}
@@ -2336,7 +2354,7 @@ static void
 intern_blocks(opt_state_t *opt_state, struct icode *ic)
 {
 	struct block *p;
-	int i, j;
+	u_int i, j;
 	int done1; /* don't shadow global */
  top:
 	done1 = 1;
@@ -2345,7 +2363,8 @@ intern_blocks(opt_state_t *opt_state, struct icode *ic)
 
 	mark_code(ic);
 
-	for (i = opt_state->n_blocks - 1; --i >= 0; ) {
+	for (i = opt_state->n_blocks - 1; i != 0; ) {
+		--i;
 		if (!isMarked(ic, opt_state->blocks[i]))
 			continue;
 		for (j = i + 1; j < opt_state->n_blocks; ++j) {
@@ -2438,13 +2457,19 @@ count_blocks(struct icode *ic, struct block *p)
 static void
 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p)
 {
-	int n;
+	u_int n;
 
 	if (p == 0 || isMarked(ic, p))
 		return;
 
 	Mark(ic, p);
 	n = opt_state->n_blocks++;
+	if (opt_state->n_blocks == 0) {
+		/*
+		 * Overflow.
+		 */
+		opt_error(opt_state, "filter is too complex to optimize");
+	}
 	p->id = n;
 	opt_state->blocks[n] = p;
 
@@ -2492,6 +2517,8 @@ opt_init(opt_state_t *opt_state, struct icode *ic)
 {
 	bpf_u_int32 *p;
 	int i, n, max_stmts;
+	u_int product;
+	size_t block_memsize, edge_memsize;
 
 	/*
 	 * First, count the blocks, so we can malloc an array to map
@@ -2506,7 +2533,19 @@ opt_init(opt_state_t *opt_state, struct icode *ic)
 	opt_state->n_blocks = 0;
 	number_blks_r(opt_state, ic, ic->root);
 
+	/*
+	 * This "should not happen".
+	 */
+	if (opt_state->n_blocks == 0)
+		opt_error(opt_state, "filter has no instructions; please report this as a libpcap issue");
+
 	opt_state->n_edges = 2 * opt_state->n_blocks;
+	if ((opt_state->n_edges / 2) != opt_state->n_blocks) {
+		/*
+		 * Overflow.
+		 */
+		opt_error(opt_state, "filter is too complex to optimize");
+	}
 	opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges));
 	if (opt_state->edges == NULL) {
 		opt_error(opt_state, "malloc");
@@ -2523,9 +2562,59 @@ opt_init(opt_state_t *opt_state, struct icode *ic)
 	opt_state->edgewords = opt_state->n_edges / BITS_PER_WORD + 1;
 	opt_state->nodewords = opt_state->n_blocks / BITS_PER_WORD + 1;
 
+	/*
+	 * Make sure opt_state->n_blocks * opt_state->nodewords fits
+	 * in a u_int; we use it as a u_int number-of-iterations
+	 * value.
+	 */
+	product = opt_state->n_blocks * opt_state->nodewords;
+	if ((product / opt_state->n_blocks) != opt_state->nodewords) {
+		/*
+		 * XXX - just punt and don't try to optimize?
+		 * In practice, this is unlikely to happen with
+		 * a normal filter.
+		 */
+		opt_error(opt_state, "filter is too complex to optimize");
+	}
+
+	/*
+	 * Make sure the total memory required for that doesn't
+	 * overflow.
+	 */
+	block_memsize = (size_t)2 * product * sizeof(*opt_state->space);
+	if ((block_memsize / product) != 2 * sizeof(*opt_state->space)) {
+		opt_error(opt_state, "filter is too complex to optimize");
+	}
+
+	/*
+	 * Make sure opt_state->n_edges * opt_state->edgewords fits
+	 * in a u_int; we use it as a u_int number-of-iterations
+	 * value.
+	 */
+	product = opt_state->n_edges * opt_state->edgewords;
+	if ((product / opt_state->n_edges) != opt_state->edgewords) {
+		opt_error(opt_state, "filter is too complex to optimize");
+	}
+
+	/*
+	 * Make sure the total memory required for that doesn't
+	 * overflow.
+	 */
+	edge_memsize = (size_t)product * sizeof(*opt_state->space);
+	if (edge_memsize / product != sizeof(*opt_state->space)) {
+		opt_error(opt_state, "filter is too complex to optimize");
+	}
+
+	/*
+	 * Make sure the total memory required for both of them dosn't
+	 * overflow.
+	 */
+	if (block_memsize > SIZE_MAX - edge_memsize) {
+		opt_error(opt_state, "filter is too complex to optimize");
+	}
+
 	/* XXX */
-	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));
+	opt_state->space = (bpf_u_int32 *)malloc(block_memsize + edge_memsize);
 	if (opt_state->space == NULL) {
 		opt_error(opt_state, "malloc");
 	}
@@ -2599,7 +2688,6 @@ convert_code_r(conv_state_t *conv_state, struct icode *ic, struct block *p)
 	struct slist *src;
 	u_int slen;
 	u_int off;
-	u_int extrajmps;	/* number of extra jumps inserted */
 	struct slist **offset = NULL;
 
 	if (p == 0 || isMarked(ic, p))
@@ -2723,7 +2811,8 @@ filled:
 	dst->code = (u_short)p->s.code;
 	dst->k = p->s.k;
 	if (JT(p)) {
-		extrajmps = 0;
+		/* number of extra jumps inserted */
+		u_char extrajmps = 0;
 		off = JT(p)->offset - (p->offset + slen) - 1;
 		if (off >= 256) {
 		    /* offset too large for branch, must add a jump */
@@ -2732,12 +2821,7 @@ filled:
 			p->longjt++;
 			return(0);
 		    }
-		    /* branch if T to following jump */
-		    if (extrajmps >= 256) {
-			conv_error(conv_state, "too many extra jumps");
-			/*NOTREACHED*/
-		    }
-		    dst->jt = (u_char)extrajmps;
+		    dst->jt = extrajmps;
 		    extrajmps++;
 		    dst[extrajmps].code = BPF_JMP|BPF_JA;
 		    dst[extrajmps].k = off - extrajmps;
@@ -2754,11 +2838,7 @@ filled:
 		    }
 		    /* branch if F to following jump */
 		    /* if two jumps are inserted, F goes to second one */
-		    if (extrajmps >= 256) {
-			conv_error(conv_state, "too many extra jumps");
-			/*NOTREACHED*/
-		    }
-		    dst->jf = (u_char)extrajmps;
+		    dst->jf = extrajmps;
 		    extrajmps++;
 		    dst[extrajmps].code = BPF_JMP|BPF_JA;
 		    dst[extrajmps].k = off - extrajmps;
@@ -2901,7 +2981,7 @@ dot_dump_node(struct icode *ic, struct block *block, struct bpf_program *prog,
 	icount = slength(block->stmts) + 1 + block->longjt + block->longjf;
 	noffset = min(block->offset + icount, (int)prog->bf_len);
 
-	fprintf(out, "\tblock%d [shape=ellipse, id=\"block-%d\" label=\"BLOCK%d\\n", block->id, block->id, block->id);
+	fprintf(out, "\tblock%u [shape=ellipse, id=\"block-%u\" label=\"BLOCK%u\\n", block->id, block->id, block->id);
 	for (i = block->offset; i < noffset; i++) {
 		fprintf(out, "\\n%s", bpf_image(prog->bf_insns + i, i));
 	}
@@ -2928,9 +3008,9 @@ dot_dump_edge(struct icode *ic, struct block *block, FILE *out)
 	Mark(ic, block);
 
 	if (JT(block)) {
-		fprintf(out, "\t\"block%d\":se -> \"block%d\":n [label=\"T\"]; \n",
+		fprintf(out, "\t\"block%u\":se -> \"block%u\":n [label=\"T\"]; \n",
 				block->id, JT(block)->id);
-		fprintf(out, "\t\"block%d\":sw -> \"block%d\":n [label=\"F\"]; \n",
+		fprintf(out, "\t\"block%u\":sw -> \"block%u\":n [label=\"F\"]; \n",
 			   block->id, JF(block)->id);
 	}
 	dot_dump_edge(ic, JT(block), out);