optimize.c

该软件根据网络数据生成NetFlow记录。NetFlow可用于网络规划、负载均衡、安全监控等

		/* XXX Need to check that there are no data dependencies
		   between dp0 and dp1.  Currently, the code generator
		   will not produce such dependencies. */
		samep = &JF(*samep);
	}
#ifdef notdef
	/* XXX This doesn't cover everything. */
	for (i = 0; i < N_ATOMS; ++i)
		if ((*samep)->val[i] != pred->val[i])
			return;
#endif
	/* Pull up the node. */
	pull = *samep;
	*samep = JF(pull);
	JF(pull) = *diffp;

	/*
	 * At the top of the chain, each predecessor needs to point at the
	 * pulled up node.  Inside the chain, there is only one predecessor
	 * to worry about.
	 */
	if (at_top) {
		for (ep = b->in_edges; ep != 0; ep = ep->next) {
			if (JT(ep->pred) == b)
				JT(ep->pred) = pull;
			else
				JF(ep->pred) = pull;
		}
	}
	else
		*diffp = pull;

	done = 0;
}

static void
and_pullup(b)
	struct block *b;
{
	int val, at_top;
	struct block *pull;
	struct block **diffp, **samep;
	struct edge *ep;

	ep = b->in_edges;
	if (ep == 0)
		return;

	/*
	 * Make sure each predecessor loads the same value.
	 */
	val = ep->pred->val[A_ATOM];
	for (ep = ep->next; ep != 0; ep = ep->next)
		if (val != ep->pred->val[A_ATOM])
			return;

	if (JT(b->in_edges->pred) == b)
		diffp = &JT(b->in_edges->pred);
	else
		diffp = &JF(b->in_edges->pred);

	at_top = 1;
	while (1) {
		if (*diffp == 0)
			return;

		if (JF(*diffp) != JF(b))
			return;

		if (!SET_MEMBER((*diffp)->dom, b->id))
			return;

		if ((*diffp)->val[A_ATOM] != val)
			break;

		diffp = &JT(*diffp);
		at_top = 0;
	}
	samep = &JT(*diffp);
	while (1) {
		if (*samep == 0)
			return;

		if (JF(*samep) != JF(b))
			return;

		if (!SET_MEMBER((*samep)->dom, b->id))
			return;

		if ((*samep)->val[A_ATOM] == val)
			break;

		/* XXX Need to check that there are no data dependencies
		   between diffp and samep.  Currently, the code generator
		   will not produce such dependencies. */
		samep = &JT(*samep);
	}
#ifdef notdef
	/* XXX This doesn't cover everything. */
	for (i = 0; i < N_ATOMS; ++i)
		if ((*samep)->val[i] != pred->val[i])
			return;
#endif
	/* Pull up the node. */
	pull = *samep;
	*samep = JT(pull);
	JT(pull) = *diffp;

	/*
	 * At the top of the chain, each predecessor needs to point at the
	 * pulled up node.  Inside the chain, there is only one predecessor
	 * to worry about.
	 */
	if (at_top) {
		for (ep = b->in_edges; ep != 0; ep = ep->next) {
			if (JT(ep->pred) == b)
				JT(ep->pred) = pull;
			else
				JF(ep->pred) = pull;
		}
	}
	else
		*diffp = pull;

	done = 0;
}

static void
opt_blks(root, do_stmts)
	struct block *root;
	int do_stmts;
{
	int i, maxlevel;
	struct block *p;

	init_val();
	maxlevel = root->level;
	for (i = maxlevel; i >= 0; --i)
		for (p = levels[i]; p; p = p->link)
			opt_blk(p, do_stmts);

	if (do_stmts)
		/*
		 * No point trying to move branches; it can't possibly
		 * make a difference at this point.
		 */
		return;

	for (i = 1; i <= maxlevel; ++i) {
		for (p = levels[i]; p; p = p->link) {
			opt_j(&p->et);
			opt_j(&p->ef);
		}
	}
	for (i = 1; i <= maxlevel; ++i) {
		for (p = levels[i]; p; p = p->link) {
			or_pullup(p);
			and_pullup(p);
		}
	}
}

static inline void
link_inedge(parent, child)
	struct edge *parent;
	struct block *child;
{
	parent->next = child->in_edges;
	child->in_edges = parent;
}

static void
find_inedges(root)
	struct block *root;
{
	int i;
	struct block *b;

	for (i = 0; i < n_blocks; ++i)
		blocks[i]->in_edges = 0;

	/*
	 * 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 = levels[i]; b != 0; b = b->link) {
			link_inedge(&b->et, JT(b));
			link_inedge(&b->ef, JF(b));
		}
	}
}

static void
opt_root(b)
	struct block **b;
{
	struct slist *tmp, *s;

	s = (*b)->stmts;
	(*b)->stmts = 0;
	while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b))
		*b = JT(*b);

	tmp = (*b)->stmts;
	if (tmp != 0)
		sappend(s, tmp);
	(*b)->stmts = s;

	/*
	 * If the root node is a return, then there is no
	 * point executing any statements (since the bpf machine
	 * has no side effects).
	 */
	if (BPF_CLASS((*b)->s.code) == BPF_RET)
		(*b)->stmts = 0;
}

static void
opt_loop(root, do_stmts)
	struct block *root;
	int do_stmts;
{

#ifdef BDEBUG
	if (dflag > 1)
		opt_dump(root);
#endif
	do {
		done = 1;
		find_levels(root);
		find_dom(root);
		find_closure(root);
		find_inedges(root);
		find_ud(root);
		find_edom(root);
		opt_blks(root, do_stmts);
#ifdef BDEBUG
		if (dflag > 1)
			opt_dump(root);
#endif
	} while (!done);
}

/*
 * Optimize the filter code in its dag representation.
 */
void
bpf_optimize(rootp)
	struct block **rootp;
{
	struct block *root;

	root = *rootp;

	opt_init(root);
	opt_loop(root, 0);
	opt_loop(root, 1);
	intern_blocks(root);
	opt_root(rootp);
	opt_cleanup();
}

static void
make_marks(p)
	struct block *p;
{
	if (!isMarked(p)) {
		Mark(p);
		if (BPF_CLASS(p->s.code) != BPF_RET) {
			make_marks(JT(p));
			make_marks(JF(p));
		}
	}
}

/*
 * Mark code array such that isMarked(i) is true
 * only for nodes that are alive.
 */
static void
mark_code(p)
	struct block *p;
{
	cur_mark += 1;
	make_marks(p);
}

/*
 * True iff the two stmt lists load the same value from the packet into
 * the accumulator.
 */
static int
eq_slist(x, y)
	struct slist *x, *y;
{
	while (1) {
		while (x && x->s.code == NOP)
			x = x->next;
		while (y && y->s.code == NOP)
			y = y->next;
		if (x == 0)
			return y == 0;
		if (y == 0)
			return x == 0;
		if (x->s.code != y->s.code || x->s.k != y->s.k)
			return 0;
		x = x->next;
		y = y->next;
	}
}

static inline int
eq_blk(b0, b1)
	struct block *b0, *b1;
{
	if (b0->s.code == b1->s.code &&
	    b0->s.k == b1->s.k &&
	    b0->et.succ == b1->et.succ &&
	    b0->ef.succ == b1->ef.succ)
		return eq_slist(b0->stmts, b1->stmts);
	return 0;
}

static void
intern_blocks(root)
	struct block *root;
{
	struct block *p;
	int i, j;
	int done;
 top:
	done = 1;
	for (i = 0; i < n_blocks; ++i)
		blocks[i]->link = 0;

	mark_code(root);

	for (i = n_blocks - 1; --i >= 0; ) {
		if (!isMarked(blocks[i]))
			continue;
		for (j = i + 1; j < n_blocks; ++j) {
			if (!isMarked(blocks[j]))
				continue;
			if (eq_blk(blocks[i], blocks[j])) {
				blocks[i]->link = blocks[j]->link ?
					blocks[j]->link : blocks[j];
				break;
			}
		}
	}
	for (i = 0; i < n_blocks; ++i) {
		p = blocks[i];
		if (JT(p) == 0)
			continue;
		if (JT(p)->link) {
			done = 0;
			JT(p) = JT(p)->link;
		}
		if (JF(p)->link) {
			done = 0;
			JF(p) = JF(p)->link;
		}
	}
	if (!done)
		goto top;
}

static void
opt_cleanup()
{
	free((void *)vnode_base);
	free((void *)vmap);
	free((void *)edges);
	free((void *)space);
	free((void *)levels);
	free((void *)blocks);
}

/*
 * Return the number of stmts in 's'.
 */
static int
slength(s)
	struct slist *s;
{
	int n = 0;

	for (; s; s = s->next)
		if (s->s.code != NOP)
			++n;
	return n;
}

/*
 * Return the number of nodes reachable by 'p'.
 * All nodes should be initially unmarked.
 */
static int
count_blocks(p)
	struct block *p;
{
	if (p == 0 || isMarked(p))
		return 0;
	Mark(p);
	return count_blocks(JT(p)) + count_blocks(JF(p)) + 1;
}

/*
 * Do a depth first search on the flow graph, numbering the
 * the basic blocks, and entering them into the 'blocks' array.`
 */
static void
number_blks_r(p)
	struct block *p;
{
	int n;

	if (p == 0 || isMarked(p))
		return;

	Mark(p);
	n = n_blocks++;
	p->id = n;
	blocks[n] = p;

	number_blks_r(JT(p));
	number_blks_r(JF(p));
}

/*
 * Return the number of stmts in the flowgraph reachable by 'p'.
 * The nodes should be unmarked before calling.
 */
static int
count_stmts(p)
	struct block *p;
{
	int n;

	if (p == 0 || isMarked(p))
		return 0;
	Mark(p);
	n = count_stmts(JT(p)) + count_stmts(JF(p));
	return slength(p->stmts) + n + 1;
}

/*
 * Allocate memory.  All allocation is done before optimization
 * is begun.  A linear bound on the size of all data structures is computed
 * from the total number of blocks and/or statements.
 */
static void
opt_init(root)
	struct block *root;
{
	bpf_u_int32 *p;
	int i, n, max_stmts;

	/*
	 * First, count the blocks, so we can malloc an array to map
	 * block number to block.  Then, put the blocks into the array.
	 */
	unMarkAll();
	n = count_blocks(root);
	blocks = (struct block **)malloc(n * sizeof(*blocks));
	unMarkAll();
	n_blocks = 0;
	number_blks_r(root);

	n_edges = 2 * n_blocks;
	edges = (struct edge **)malloc(n_edges * sizeof(*edges));

	/*
	 * The number of levels is bounded by the number of nodes.
	 */
	levels = (struct block **)malloc(n_blocks * sizeof(*levels));

	edgewords = n_edges / (8 * sizeof(bpf_u_int32)) + 1;
	nodewords = n_blocks / (8 * sizeof(bpf_u_int32)) + 1;

	/* XXX */
	space = (bpf_u_int32 *)malloc(2 * n_blocks * nodewords * sizeof(*space)
				 + n_edges * edgewords * sizeof(*space));
	p = space;
	all_dom_sets = p;
	for (i = 0; i < n; ++i) {
		blocks[i]->dom = p;
		p += nodewords;
	}
	all_closure_sets = p;
	for (i = 0; i < n; ++i) {
		blocks[i]->closure = p;
		p += nodewords;
	}
	all_edge_sets = p;
	for (i = 0; i < n; ++i) {
		register struct block *b = blocks[i];

		b->et.edom = p;
		p += edgewords;
		b->ef.edom = p;
		p += edgewords;
		b->et.id = i;
		edges[i] = &b->et;
		b->ef.id = n_blocks + i;
		edges[n_blocks + i] = &b->ef;
		b->et.pred = b;
		b->ef.pred = b;
	}
	max_stmts = 0;
	for (i = 0; i < n; ++i)
		max_stmts += slength(blocks[i]->stmts) + 1;
	/*
	 * We allocate at most 3 value numbers per statement,
	 * so this is an upper bound on the number of valnodes
	 * we'll need.
	 */
	maxval = 3 * max_stmts;
	vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap));
	vnode_base = (struct valnode *)malloc(maxval * sizeof(*vmap));
}

/*
 * Some pointers used to convert the basic block form of the code,
 * into the array form that BPF requires.  'fstart' will point to
 * the malloc'd array while 'ftail' is used during the recursive traversal.
 */
static struct bpf_insn *fstart;
static struct bpf_insn *ftail;

#ifdef BDEBUG
int bids[1000];
#endif

/*
 * Returns true if successful.  Returns false if a branch has
 * an offset that is too large.  If so, we have marked that
 * branch so that on a subsequent iteration, it will be treated
 * properly.
 */
static int
convert_code_r(p)
	struct block *p;
{
	struct bpf_insn *dst;
	struct slist *src;
	int slen;
	u_int off;
	int extrajmps;		/* number of extra jumps inserted */

	if (p == 0 || isMarked(p))
		return (1);
	Mark(p);

	if (convert_code_r(JF(p)) == 0)
		return (0);
	if (convert_code_r(JT(p)) == 0)
		return (0);

	slen = slength(p->stmts);
	dst = ftail -= (slen + 1 + p->longjt + p->longjf);
		/* inflate length by any extra jumps */

	p->offset = dst - fstart;

	for (src = p->stmts; src; src = src->next) {
		if (src->s.code == NOP)
			continue;
		dst->code = (u_short)src->s.code;
		dst->k = src->s.k;
		++dst;
	}
#ifdef BDEBUG
	bids[dst - fstart] = p->id + 1;
#endif
	dst->code = (u_short)p->s.code;
	dst->k = p->s.k;
	if (JT(p)) {
		extrajmps = 0;
		off = JT(p)->offset - (p->offset + slen) - 1;
		if (off >= 256) {
		    /* offset too large for branch, must add a jump */
		    if (p->longjt == 0) {
		    	/* mark this instruction and retry */
			p->longjt++;
			return(0);
		    }
		    /* branch if T to following jump */
		    dst->jt = extrajmps;
		    extrajmps++;
		    dst[extrajmps].code = BPF_JMP|BPF_JA;
		    dst[extrajmps].k = off - extrajmps;
		}
		else
		    dst->jt = off;
		off = JF(p)->offset - (p->offset + slen) - 1;
		if (off >= 256) {
		    /* offset too large for branch, must add a jump */
		    if (p->longjf == 0) {
		    	/* mark this instruction and retry */
			p->longjf++;
			return(0);
		    }
		    /* branch if F to following jump */
		    /* if two jumps are inserted, F goes to second one */
		    dst->jf = extrajmps;
		    extrajmps++;
		    dst[extrajmps].code = BPF_JMP|BPF_JA;
		    dst[extrajmps].k = off - extrajmps;
		}
		else
		    dst->jf = off;
	}
	return (1);
}


/*
 * Convert flowgraph intermediate representation to the
 * BPF array representation.  Set *lenp to the number of instructions.
 */
struct bpf_insn *
icode_to_fcode(root, lenp)
	struct block *root;
	int *lenp;
{
	int n;
	struct bpf_insn *fp;

	/*
	 * Loop doing convert_codr_r() until no branches remain
	 * with too-large offsets.
	 */
	while (1) {
	    unMarkAll();
	    n = *lenp = count_stmts(root);
    
	    fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
	    memset((char *)fp, 0, sizeof(*fp) * n);
	    fstart = fp;
	    ftail = fp + n;
    
	    unMarkAll();
	    if (convert_code_r(root))
		break;
	    free(fp);
	}

	return fp;
}

#ifdef BDEBUG
static void
opt_dump(root)
	struct block *root;
{
	struct bpf_program f;

	memset(bids, 0, sizeof bids);
	f.bf_insns = icode_to_fcode(root, &f.bf_len);
	bpf_dump(&f, 1);
	putchar('\n');
	free((char *)f.bf_insns);
}
#endif