contrib/libpcap/optimize.c

223 #define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)
379 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
390 		find_levels_r(opt_state, ic, JT(b));
391 		find_levels_r(opt_state, ic, JF(b));
396 	b->link = opt_state->levels[level];
397 	opt_state->levels[level] = b;
402  * N_LEVELS at the root.  The opt_state->levels[] array points to the
407 find_levels(opt_state_t *opt_state, struct icode *ic)
409 	memset((char *)opt_state->levels, 0, opt_state->n_blocks * sizeof(*opt_state->levels));
411 	find_levels_r(opt_state, ic, ic->root);
419 find_dom(opt_state_t *opt_state, struct block *root)
429 	x = opt_state->all_dom_sets;
433 	i = opt_state->n_blocks * opt_state->nodewords;
439 	for (i = opt_state->nodewords; i != 0;) {
446 		for (b = opt_state->levels[level]; b; b = b->link) {
450 			SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
451 			SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
457 propedom(opt_state_t *opt_state, struct edge *ep)
461 		SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
462 		SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
471 find_edom(opt_state_t *opt_state, struct block *root)
478 	x = opt_state->all_edge_sets;
482 	for (i = opt_state->n_edges * opt_state->edgewords; i != 0; ) {
488 	memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
489 	memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
491 		for (b = opt_state->levels[level]; b != 0; b = b->link) {
492 			propedom(opt_state, &b->et);
493 			propedom(opt_state, &b->ef);
506 find_closure(opt_state_t *opt_state, struct block *root)
514 	memset((char *)opt_state->all_closure_sets, 0,
515 	      opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets));
519 		for (b = opt_state->levels[level]; b; b = b->link) {
523 			SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
524 			SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
685 find_ud(opt_state_t *opt_state, struct block *root)
696 		for (p = opt_state->levels[i]; p; p = p->link) {
702 		for (p = opt_state->levels[i]; p; p = p->link) {
709 init_val(opt_state_t *opt_state)
711 	opt_state->curval = 0;
712 	opt_state->next_vnode = opt_state->vnode_base;
713 	memset((char *)opt_state->vmap, 0, opt_state->maxval * sizeof(*opt_state->vmap));
714 	memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl);
727 F(opt_state_t *opt_state, int code, bpf_u_int32 v0, bpf_u_int32 v1)
736 	for (p = opt_state->hashtbl[hash]; p; p = p->next)
744 	 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
751 	val = ++opt_state->curval;
754 		opt_state->vmap[val].const_val = v0;
755 		opt_state->vmap[val].is_const = 1;
757 	p = opt_state->next_vnode++;
762 	p->next = opt_state->hashtbl[hash];
763 	opt_state->hashtbl[hash] = p;
782 fold_op(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 v0, bpf_u_int32 v1)
786 	a = opt_state->vmap[v0].const_val;
787 	b = opt_state->vmap[v1].const_val;
804 			opt_error(opt_state, "division by zero");
810 			opt_error(opt_state, "modulus by zero");
870 	opt_state->non_branch_movement_performed = 1;
871 	opt_state->done = 0;
892 opt_peep(opt_state_t *opt_state, struct block *b)
930 			opt_state->non_branch_movement_performed = 1;
931 			opt_state->done = 0;
945 			opt_state->non_branch_movement_performed = 1;
946 			opt_state->done = 0;
1028 			opt_state->non_branch_movement_performed = 1;
1029 			opt_state->done = 0;
1047 			if (opt_state->vmap[val].is_const) {
1057 				b->s.k += opt_state->vmap[val].const_val;
1062 				opt_state->non_branch_movement_performed = 1;
1063 				opt_state->done = 0;
1079 				opt_state->non_branch_movement_performed = 1;
1080 				opt_state->done = 0;
1095 			opt_state->non_branch_movement_performed = 1;
1096 			opt_state->done = 0;
1113 			opt_state->non_branch_movement_performed = 1;
1114 			opt_state->done = 0;
1134 	if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) {
1135 		bpf_u_int32 v = opt_state->vmap[val].const_val;
1144 	if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
1145 		bpf_u_int32 v = opt_state->vmap[val].const_val;
1171 			opt_state->non_branch_movement_performed = 1;
1172 			opt_state->done = 0;
1188 opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
1198 		v = F(opt_state, s->code, s->k, 0L);
1206 		if (alter && opt_state->vmap[v].is_const) {
1208 			s->k += opt_state->vmap[v].const_val;
1209 			v = F(opt_state, s->code, s->k, 0L);
1213 			opt_state->non_branch_movement_performed = 1;
1214 			opt_state->done = 0;
1217 			v = F(opt_state, s->code, s->k, v);
1222 		v = F(opt_state, s->code, 0L, 0L);
1237 		v = F(opt_state, s->code, s->k, 0L);
1242 		if (alter && opt_state->vmap[val[A_ATOM]].is_const) {
1260 			s->k = 0U - opt_state->vmap[val[A_ATOM]].const_val;
1264 			val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], 0L);
1303 					opt_error(opt_state,
1306 					opt_error(opt_state,
1309 			if (opt_state->vmap[val[A_ATOM]].is_const) {
1310 				fold_op(opt_state, s, val[A_ATOM], K(s->k));
1315 		val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], K(s->k));
1329 		if (alter && opt_state->vmap[val[X_ATOM]].is_const) {
1330 			if (opt_state->vmap[val[A_ATOM]].is_const) {
1331 				fold_op(opt_state, s, val[A_ATOM], val[X_ATOM]);
1336 				s->k = opt_state->vmap[val[X_ATOM]].const_val;
1339 					opt_error(opt_state,
1344 				opt_state->non_branch_movement_performed = 1;
1345 				opt_state->done = 0;
1347 					F(opt_state, s->code, val[A_ATOM], K(s->k));
1358 		if (alter && opt_state->vmap[val[A_ATOM]].is_const
1359 		    && opt_state->vmap[val[A_ATOM]].const_val == 0) {
1377 		val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], val[X_ATOM]);
1386 		if (alter && opt_state->vmap[v].is_const) {
1388 			s->k = opt_state->vmap[v].const_val;
1392 			opt_state->non_branch_movement_performed = 1;
1393 			opt_state->done = 0;
1404 		if (alter && opt_state->vmap[v].is_const) {
1406 			s->k = opt_state->vmap[v].const_val;
1410 			opt_state->non_branch_movement_performed = 1;
1411 			opt_state->done = 0;
1427 deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[])
1446 			opt_state->non_branch_movement_performed = 1;
1447 			opt_state->done = 0;
1455 opt_deadstores(opt_state_t *opt_state, register struct block *b)
1464 		deadstmt(opt_state, &s->s, last);
1465 	deadstmt(opt_state, &b->s, last);
1473 			opt_state->non_branch_movement_performed = 1;
1474 			opt_state->done = 0;
1479 opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts)
1529 		opt_stmt(opt_state, &s->s, b->val, do_stmts);
1567 			opt_state->non_branch_movement_performed = 1;
1568 			opt_state->done = 0;
1571 		opt_peep(opt_state, b);
1572 		opt_deadstores(opt_state, b);
1693 opt_j(opt_state_t *opt_state, struct edge *ep)
1739 			opt_state->non_branch_movement_performed = 1;
1740 			opt_state->done = 0;
1752 	for (i = 0; i < opt_state->edgewords; ++i) {
1762 			target = fold_edge(ep->succ, opt_state->edges[k]);
1785 				opt_state->done = 0;
1818 or_pullup(opt_state_t *opt_state, struct block *b)
1978 	opt_state->done = 0;
1982 and_pullup(opt_state_t *opt_state, struct block *b)
2074 	opt_state->done = 0;
2078 opt_blks(opt_state_t *opt_state, struct icode *ic, int do_stmts)
2083 	init_val(opt_state);
2086 	find_inedges(opt_state, ic->root);
2088 		for (p = opt_state->levels[i]; p; p = p->link)
2089 			opt_blk(opt_state, p, do_stmts);
2112 		for (p = opt_state->levels[i]; p; p = p->link) {
2113 			opt_j(opt_state, &p->et);
2114 			opt_j(opt_state, &p->ef);
2118 	find_inedges(opt_state, ic->root);
2120 		for (p = opt_state->levels[i]; p; p = p->link) {
2121 			or_pullup(opt_state, p);
2122 			and_pullup(opt_state, p);
2135 find_inedges(opt_state_t *opt_state, struct block *root)
2141 	for (i = 0; i < opt_state->n_blocks; ++i)
2142 		opt_state->blocks[i]->in_edges = 0;
2149 		for (b = opt_state->levels[level]; b != 0; b = b->link) {
2181 opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts)
2187 		opt_dump(opt_state, ic);
2196 		opt_state->done = 1;
2200 		opt_state->non_branch_movement_performed = 0;
2201 		find_levels(opt_state, ic);
2202 		find_dom(opt_state, ic->root);
2203 		find_closure(opt_state, ic->root);
2204 		find_ud(opt_state, ic->root);
2205 		find_edom(opt_state, ic->root);
2206 		opt_blks(opt_state, ic, do_stmts);
2209 			printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done);
2210 			opt_dump(opt_state, ic);
2217 		if (opt_state->done) {
2229 		if (opt_state->non_branch_movement_performed) {
2253 				opt_state->done = 1;
2267 	opt_state_t opt_state;
2269 	memset(&opt_state, 0, sizeof(opt_state));
2270 	opt_state.errbuf = errbuf;
2271 	opt_state.non_branch_movement_performed = 0;
2272 	if (setjmp(opt_state.top_ctx)) {
2273 		opt_cleanup(&opt_state);
2276 	opt_init(&opt_state, ic);
2277 	opt_loop(&opt_state, ic, 0);
2278 	opt_loop(&opt_state, ic, 1);
2279 	intern_blocks(&opt_state, ic);
2283 		opt_dump(&opt_state, ic);
2290 		opt_dump(&opt_state, ic);
2293 	opt_cleanup(&opt_state);
2355 intern_blocks(opt_state_t *opt_state, struct icode *ic)
2362 	for (i = 0; i < opt_state->n_blocks; ++i)
2363 		opt_state->blocks[i]->link = 0;
2367 	for (i = opt_state->n_blocks - 1; i != 0; ) {
2369 		if (!isMarked(ic, opt_state->blocks[i]))
2371 		for (j = i + 1; j < opt_state->n_blocks; ++j) {
2372 			if (!isMarked(ic, opt_state->blocks[j]))
2374 			if (eq_blk(opt_state->blocks[i], opt_state->blocks[j])) {
2375 				opt_state->blocks[i]->link = opt_state->blocks[j]->link ?
2376 					opt_state->blocks[j]->link : opt_state->blocks[j];
2381 	for (i = 0; i < opt_state->n_blocks; ++i) {
2382 		p = opt_state->blocks[i];
2399 opt_cleanup(opt_state_t *opt_state)
2401 	free((void *)opt_state->vnode_base);
2402 	free((void *)opt_state->vmap);
2403 	free((void *)opt_state->edges);
2404 	free((void *)opt_state->space);
2405 	free((void *)opt_state->levels);
2406 	free((void *)opt_state->blocks);
2413 opt_error(opt_state_t *opt_state, const char *fmt, ...)
2417 	if (opt_state->errbuf != NULL) {
2419 		(void)vsnprintf(opt_state->errbuf,
2423 	longjmp(opt_state->top_ctx, 1);
2462 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p)
2470 	n = opt_state->n_blocks++;
2471 	if (opt_state->n_blocks == 0) {
2475 		opt_error(opt_state, "filter is too complex to optimize");
2478 	opt_state->blocks[n] = p;
2480 	number_blks_r(opt_state, ic, JT(p));
2481 	number_blks_r(opt_state, ic, JF(p));
2520 opt_init(opt_state_t *opt_state, struct icode *ic)
2533 	opt_state->blocks = (struct block **)calloc(n, sizeof(*opt_state->blocks));
2534 	if (opt_state->blocks == NULL)
2535 		opt_error(opt_state, "malloc");
2537 	opt_state->n_blocks = 0;
2538 	number_blks_r(opt_state, ic, ic->root);
2543 	if (opt_state->n_blocks == 0)
2544 		opt_error(opt_state, "filter has no instructions; please report this as a libpcap issue");
2546 	opt_state->n_edges = 2 * opt_state->n_blocks;
2547 	if ((opt_state->n_edges / 2) != opt_state->n_blocks) {
2551 		opt_error(opt_state, "filter is too complex to optimize");
2553 	opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges));
2554 	if (opt_state->edges == NULL) {
2555 		opt_error(opt_state, "malloc");
2561 	opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels));
2562 	if (opt_state->levels == NULL) {
2563 		opt_error(opt_state, "malloc");
2566 	opt_state->edgewords = opt_state->n_edges / BITS_PER_WORD + 1;
2567 	opt_state->nodewords = opt_state->n_blocks / BITS_PER_WORD + 1;
2570 	 * Make sure opt_state->n_blocks * opt_state->nodewords fits
2574 	product = opt_state->n_blocks * opt_state->nodewords;
2575 	if ((product / opt_state->n_blocks) != opt_state->nodewords) {
2581 		opt_error(opt_state, "filter is too complex to optimize");
2588 	block_memsize = (size_t)2 * product * sizeof(*opt_state->space);
2589 	if ((block_memsize / product) != 2 * sizeof(*opt_state->space)) {
2590 		opt_error(opt_state, "filter is too complex to optimize");
2594 	 * Make sure opt_state->n_edges * opt_state->edgewords fits
2598 	product = opt_state->n_edges * opt_state->edgewords;
2599 	if ((product / opt_state->n_edges) != opt_state->edgewords) {
2600 		opt_error(opt_state, "filter is too complex to optimize");
2607 	edge_memsize = (size_t)product * sizeof(*opt_state->space);
2608 	if (edge_memsize / product != sizeof(*opt_state->space)) {
2609 		opt_error(opt_state, "filter is too complex to optimize");
2617 		opt_error(opt_state, "filter is too complex to optimize");
2621 	opt_state->space = (bpf_u_int32 *)malloc(block_memsize + edge_memsize);
2622 	if (opt_state->space == NULL) {
2623 		opt_error(opt_state, "malloc");
2625 	p = opt_state->space;
2626 	opt_state->all_dom_sets = p;
2628 		opt_state->blocks[i]->dom = p;
2629 		p += opt_state->nodewords;
2631 	opt_state->all_closure_sets = p;
2633 		opt_state->blocks[i]->closure = p;
2634 		p += opt_state->nodewords;
2636 	opt_state->all_edge_sets = p;
2638 		register struct block *b = opt_state->blocks[i];
2641 		p += opt_state->edgewords;
2643 		p += opt_state->edgewords;
2645 		opt_state->edges[i] = &b->et;
2646 		b->ef.id = opt_state->n_blocks + i;
2647 		opt_state->edges[opt_state->n_blocks + i] = &b->ef;
2653 		max_stmts += slength(opt_state->blocks[i]->stmts) + 1;
2659 	opt_state->maxval = 3 * max_stmts;
2660 	opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap));
2661 	if (opt_state->vmap == NULL) {
2662 		opt_error(opt_state, "malloc");
2664 	opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base));
2665 	if (opt_state->vnode_base == NULL) {
2666 		opt_error(opt_state, "malloc");
3083 opt_dump(opt_state_t *opt_state, struct icode *ic)
3097 		opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf);