contrib/libpcap/optimize.c

221 #define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)
377 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
388 		find_levels_r(opt_state, ic, JT(b));
389 		find_levels_r(opt_state, ic, JF(b));
394 	b->link = opt_state->levels[level];
395 	opt_state->levels[level] = b;
400  * N_LEVELS at the root.  The opt_state->levels[] array points to the
405 find_levels(opt_state_t *opt_state, struct icode *ic)
407 	memset((char *)opt_state->levels, 0, opt_state->n_blocks * sizeof(*opt_state->levels));
409 	find_levels_r(opt_state, ic, ic->root);
417 find_dom(opt_state_t *opt_state, struct block *root)
427 	x = opt_state->all_dom_sets;
431 	i = opt_state->n_blocks * opt_state->nodewords;
437 	for (i = opt_state->nodewords; i != 0;) {
444 		for (b = opt_state->levels[level]; b; b = b->link) {
448 			SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
449 			SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
455 propedom(opt_state_t *opt_state, struct edge *ep)
459 		SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
460 		SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
469 find_edom(opt_state_t *opt_state, struct block *root)
476 	x = opt_state->all_edge_sets;
480 	for (i = opt_state->n_edges * opt_state->edgewords; i != 0; ) {
486 	memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
487 	memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
489 		for (b = opt_state->levels[level]; b != 0; b = b->link) {
490 			propedom(opt_state, &b->et);
491 			propedom(opt_state, &b->ef);
504 find_closure(opt_state_t *opt_state, struct block *root)
512 	memset((char *)opt_state->all_closure_sets, 0,
513 	      opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets));
517 		for (b = opt_state->levels[level]; b; b = b->link) {
521 			SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
522 			SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
683 find_ud(opt_state_t *opt_state, struct block *root)
694 		for (p = opt_state->levels[i]; p; p = p->link) {
700 		for (p = opt_state->levels[i]; p; p = p->link) {
707 init_val(opt_state_t *opt_state)
709 	opt_state->curval = 0;
710 	opt_state->next_vnode = opt_state->vnode_base;
711 	memset((char *)opt_state->vmap, 0, opt_state->maxval * sizeof(*opt_state->vmap));
712 	memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl);
725 F(opt_state_t *opt_state, int code, bpf_u_int32 v0, bpf_u_int32 v1)
734 	for (p = opt_state->hashtbl[hash]; p; p = p->next)
742 	 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
749 	val = ++opt_state->curval;
752 		opt_state->vmap[val].const_val = v0;
753 		opt_state->vmap[val].is_const = 1;
755 	p = opt_state->next_vnode++;
760 	p->next = opt_state->hashtbl[hash];
761 	opt_state->hashtbl[hash] = p;
780 fold_op(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 v0, bpf_u_int32 v1)
784 	a = opt_state->vmap[v0].const_val;
785 	b = opt_state->vmap[v1].const_val;
802 			opt_error(opt_state, "division by zero");
808 			opt_error(opt_state, "modulus by zero");
868 	opt_state->non_branch_movement_performed = 1;
869 	opt_state->done = 0;
890 opt_peep(opt_state_t *opt_state, struct block *b)
928 			opt_state->non_branch_movement_performed = 1;
929 			opt_state->done = 0;
943 			opt_state->non_branch_movement_performed = 1;
944 			opt_state->done = 0;
1026 			opt_state->non_branch_movement_performed = 1;
1027 			opt_state->done = 0;
1045 			if (opt_state->vmap[val].is_const) {
1055 				b->s.k += opt_state->vmap[val].const_val;
1060 				opt_state->non_branch_movement_performed = 1;
1061 				opt_state->done = 0;
1077 				opt_state->non_branch_movement_performed = 1;
1078 				opt_state->done = 0;
1093 			opt_state->non_branch_movement_performed = 1;
1094 			opt_state->done = 0;
1111 			opt_state->non_branch_movement_performed = 1;
1112 			opt_state->done = 0;
1132 	if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) {
1133 		bpf_u_int32 v = opt_state->vmap[val].const_val;
1142 	if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
1143 		bpf_u_int32 v = opt_state->vmap[val].const_val;
1169 			opt_state->non_branch_movement_performed = 1;
1170 			opt_state->done = 0;
1186 opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
1196 		v = F(opt_state, s->code, s->k, 0L);
1204 		if (alter && opt_state->vmap[v].is_const) {
1206 			s->k += opt_state->vmap[v].const_val;
1207 			v = F(opt_state, s->code, s->k, 0L);
1211 			opt_state->non_branch_movement_performed = 1;
1212 			opt_state->done = 0;
1215 			v = F(opt_state, s->code, s->k, v);
1220 		v = F(opt_state, s->code, 0L, 0L);
1235 		v = F(opt_state, s->code, s->k, 0L);
1240 		if (alter && opt_state->vmap[val[A_ATOM]].is_const) {
1258 			s->k = 0U - opt_state->vmap[val[A_ATOM]].const_val;
1262 			val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], 0L);
1301 					opt_error(opt_state,
1304 					opt_error(opt_state,
1307 			if (opt_state->vmap[val[A_ATOM]].is_const) {
1308 				fold_op(opt_state, s, val[A_ATOM], K(s->k));
1313 		val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], K(s->k));
1327 		if (alter && opt_state->vmap[val[X_ATOM]].is_const) {
1328 			if (opt_state->vmap[val[A_ATOM]].is_const) {
1329 				fold_op(opt_state, s, val[A_ATOM], val[X_ATOM]);
1334 				s->k = opt_state->vmap[val[X_ATOM]].const_val;
1337 					opt_error(opt_state,
1342 				opt_state->non_branch_movement_performed = 1;
1343 				opt_state->done = 0;
1345 					F(opt_state, s->code, val[A_ATOM], K(s->k));
1356 		if (alter && opt_state->vmap[val[A_ATOM]].is_const
1357 		    && opt_state->vmap[val[A_ATOM]].const_val == 0) {
1375 		val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], val[X_ATOM]);
1384 		if (alter && opt_state->vmap[v].is_const) {
1386 			s->k = opt_state->vmap[v].const_val;
1390 			opt_state->non_branch_movement_performed = 1;
1391 			opt_state->done = 0;
1402 		if (alter && opt_state->vmap[v].is_const) {
1404 			s->k = opt_state->vmap[v].const_val;
1408 			opt_state->non_branch_movement_performed = 1;
1409 			opt_state->done = 0;
1425 deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[])
1444 			opt_state->non_branch_movement_performed = 1;
1445 			opt_state->done = 0;
1453 opt_deadstores(opt_state_t *opt_state, register struct block *b)
1462 		deadstmt(opt_state, &s->s, last);
1463 	deadstmt(opt_state, &b->s, last);
1477 			opt_state->non_branch_movement_performed = 1;
1478 			opt_state->done = 0;
1483 opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts)
1533 		opt_stmt(opt_state, &s->s, b->val, do_stmts);
1571 			opt_state->non_branch_movement_performed = 1;
1572 			opt_state->done = 0;
1575 		opt_peep(opt_state, b);
1576 		opt_deadstores(opt_state, b);
1697 opt_j(opt_state_t *opt_state, struct edge *ep)
1743 			opt_state->non_branch_movement_performed = 1;
1744 			opt_state->done = 0;
1756 	for (i = 0; i < opt_state->edgewords; ++i) {
1766 			target = fold_edge(ep->succ, opt_state->edges[k]);
1789 				opt_state->done = 0;
1822 or_pullup(opt_state_t *opt_state, struct block *b, struct block *root)
1982 	opt_state->done = 0;
1987 	find_dom(opt_state, root);
1991 and_pullup(opt_state_t *opt_state, struct block *b, struct block *root)
2083 	opt_state->done = 0;
2088 	find_dom(opt_state, root);
2092 opt_blks(opt_state_t *opt_state, struct icode *ic, int do_stmts)
2097 	init_val(opt_state);
2100 	find_inedges(opt_state, ic->root);
2102 		for (p = opt_state->levels[i]; p; p = p->link)
2103 			opt_blk(opt_state, p, do_stmts);
2126 		for (p = opt_state->levels[i]; p; p = p->link) {
2127 			opt_j(opt_state, &p->et);
2128 			opt_j(opt_state, &p->ef);
2132 	find_inedges(opt_state, ic->root);
2134 		for (p = opt_state->levels[i]; p; p = p->link) {
2135 			or_pullup(opt_state, p, ic->root);
2136 			and_pullup(opt_state, p, ic->root);
2149 find_inedges(opt_state_t *opt_state, struct block *root)
2155 	for (i = 0; i < opt_state->n_blocks; ++i)
2156 		opt_state->blocks[i]->in_edges = 0;
2163 		for (b = opt_state->levels[level]; b != 0; b = b->link) {
2195 opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts)
2201 		opt_dump(opt_state, ic);
2210 		opt_state->done = 1;
2214 		opt_state->non_branch_movement_performed = 0;
2215 		find_levels(opt_state, ic);
2216 		find_dom(opt_state, ic->root);
2217 		find_closure(opt_state, ic->root);
2218 		find_ud(opt_state, ic->root);
2219 		find_edom(opt_state, ic->root);
2220 		opt_blks(opt_state, ic, do_stmts);
2223 			printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done);
2224 			opt_dump(opt_state, ic);
2231 		if (opt_state->done) {
2243 		if (opt_state->non_branch_movement_performed) {
2267 				opt_state->done = 1;
2281 	opt_state_t opt_state;
2283 	memset(&opt_state, 0, sizeof(opt_state));
2284 	opt_state.errbuf = errbuf;
2285 	opt_state.non_branch_movement_performed = 0;
2286 	if (setjmp(opt_state.top_ctx)) {
2287 		opt_cleanup(&opt_state);
2290 	opt_init(&opt_state, ic);
2291 	opt_loop(&opt_state, ic, 0);
2292 	opt_loop(&opt_state, ic, 1);
2293 	intern_blocks(&opt_state, ic);
2297 		opt_dump(&opt_state, ic);
2304 		opt_dump(&opt_state, ic);
2307 	opt_cleanup(&opt_state);
2369 intern_blocks(opt_state_t *opt_state, struct icode *ic)
2376 	for (i = 0; i < opt_state->n_blocks; ++i)
2377 		opt_state->blocks[i]->link = 0;
2381 	for (i = opt_state->n_blocks - 1; i != 0; ) {
2383 		if (!isMarked(ic, opt_state->blocks[i]))
2385 		for (j = i + 1; j < opt_state->n_blocks; ++j) {
2386 			if (!isMarked(ic, opt_state->blocks[j]))
2388 			if (eq_blk(opt_state->blocks[i], opt_state->blocks[j])) {
2389 				opt_state->blocks[i]->link = opt_state->blocks[j]->link ?
2390 					opt_state->blocks[j]->link : opt_state->blocks[j];
2395 	for (i = 0; i < opt_state->n_blocks; ++i) {
2396 		p = opt_state->blocks[i];
2413 opt_cleanup(opt_state_t *opt_state)
2415 	free((void *)opt_state->vnode_base);
2416 	free((void *)opt_state->vmap);
2417 	free((void *)opt_state->edges);
2418 	free((void *)opt_state->space);
2419 	free((void *)opt_state->levels);
2420 	free((void *)opt_state->blocks);
2427 opt_error(opt_state_t *opt_state, const char *fmt, ...)
2431 	if (opt_state->errbuf != NULL) {
2433 		(void)vsnprintf(opt_state->errbuf,
2437 	longjmp(opt_state->top_ctx, 1);
2476 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p)
2484 	n = opt_state->n_blocks++;
2485 	if (opt_state->n_blocks == 0) {
2489 		opt_error(opt_state, "filter is too complex to optimize");
2492 	opt_state->blocks[n] = p;
2494 	number_blks_r(opt_state, ic, JT(p));
2495 	number_blks_r(opt_state, ic, JF(p));
2534 opt_init(opt_state_t *opt_state, struct icode *ic)
2547 	opt_state->blocks = (struct block **)calloc(n, sizeof(*opt_state->blocks));
2548 	if (opt_state->blocks == NULL)
2549 		opt_error(opt_state, "malloc");
2551 	opt_state->n_blocks = 0;
2552 	number_blks_r(opt_state, ic, ic->root);
2557 	if (opt_state->n_blocks == 0)
2558 		opt_error(opt_state, "filter has no instructions; please report this as a libpcap issue");
2560 	opt_state->n_edges = 2 * opt_state->n_blocks;
2561 	if ((opt_state->n_edges / 2) != opt_state->n_blocks) {
2565 		opt_error(opt_state, "filter is too complex to optimize");
2567 	opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges));
2568 	if (opt_state->edges == NULL) {
2569 		opt_error(opt_state, "malloc");
2575 	opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels));
2576 	if (opt_state->levels == NULL) {
2577 		opt_error(opt_state, "malloc");
2580 	opt_state->edgewords = opt_state->n_edges / BITS_PER_WORD + 1;
2581 	opt_state->nodewords = opt_state->n_blocks / BITS_PER_WORD + 1;
2584 	 * Make sure opt_state->n_blocks * opt_state->nodewords fits
2588 	product = opt_state->n_blocks * opt_state->nodewords;
2589 	if ((product / opt_state->n_blocks) != opt_state->nodewords) {
2595 		opt_error(opt_state, "filter is too complex to optimize");
2602 	block_memsize = (size_t)2 * product * sizeof(*opt_state->space);
2603 	if ((block_memsize / product) != 2 * sizeof(*opt_state->space)) {
2604 		opt_error(opt_state, "filter is too complex to optimize");
2608 	 * Make sure opt_state->n_edges * opt_state->edgewords fits
2612 	product = opt_state->n_edges * opt_state->edgewords;
2613 	if ((product / opt_state->n_edges) != opt_state->edgewords) {
2614 		opt_error(opt_state, "filter is too complex to optimize");
2621 	edge_memsize = (size_t)product * sizeof(*opt_state->space);
2622 	if (edge_memsize / product != sizeof(*opt_state->space)) {
2623 		opt_error(opt_state, "filter is too complex to optimize");
2631 		opt_error(opt_state, "filter is too complex to optimize");
2635 	opt_state->space = (bpf_u_int32 *)malloc(block_memsize + edge_memsize);
2636 	if (opt_state->space == NULL) {
2637 		opt_error(opt_state, "malloc");
2639 	p = opt_state->space;
2640 	opt_state->all_dom_sets = p;
2642 		opt_state->blocks[i]->dom = p;
2643 		p += opt_state->nodewords;
2645 	opt_state->all_closure_sets = p;
2647 		opt_state->blocks[i]->closure = p;
2648 		p += opt_state->nodewords;
2650 	opt_state->all_edge_sets = p;
2652 		register struct block *b = opt_state->blocks[i];
2655 		p += opt_state->edgewords;
2657 		p += opt_state->edgewords;
2659 		opt_state->edges[i] = &b->et;
2660 		b->ef.id = opt_state->n_blocks + i;
2661 		opt_state->edges[opt_state->n_blocks + i] = &b->ef;
2667 		max_stmts += slength(opt_state->blocks[i]->stmts) + 1;
2673 	opt_state->maxval = 3 * max_stmts;
2674 	opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap));
2675 	if (opt_state->vmap == NULL) {
2676 		opt_error(opt_state, "malloc");
2678 	opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base));
2679 	if (opt_state->vnode_base == NULL) {
2680 		opt_error(opt_state, "malloc");
3097 opt_dump(opt_state_t *opt_state, struct icode *ic)
3111 		opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf);