dpf.c

来自「基于组件方式开发操作系统的OSKIT源代码」· C语言 代码 · 共 670 行 · 第 1/2 页

/*
 * Copyright (c) 1997 M.I.T.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by MIT.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */


/* 
 * Routines to insert and delete dpf filters.  Result is a valid dpf_iptr
 * function that can be called to demux packets.
 *
 * Biggest problem is that our code generation methodology is pretty 
 * exposed: front end has to know about the various optimizations and
 * when their invarients are violated.
 */
#include <dpf-internal.h>
#include <string.h>
#include <stddef.h>
#include <stdlib.h>
#include <malloc.h>
#include <hash.h>

Atom dpf_active[DPF_MAXFILT+1];/* pointer to last node in active filters */
Atom dpf_base;           	/* base of the tree */
struct atom dpf_fake_head; 	/* Bogus header node. */

static int dpf_overlap; /* did the inserted filter overlap? */
static int verbose;

static Atom dpf_merge(Atom dpf, struct ir *ir, int pid) ;

/* Compute log base 2 of x. */
unsigned log2(unsigned x) {
        unsigned i;

        demand(x && x == (x & -x), x is not a power of two!);
        for(i = 0; x; x >>= 1, i++)
                ;
        return i-1;
}

/* If parent has two or more kids, a is in an orlist. */
inline int orlist_p(Atom a) {
        Atom firstor = a->parent->kids.lh_first;
        return firstor && firstor->sibs.le_next;
}

/* Create an atom: many of these fields can be filled in to 0 by default. */
static Atom mkatom(Atom parent, int pid, struct ir ir) {
	Atom a;

	/* Should have a more efficient allocation mechanism */
	a = (Atom)calloc(1, sizeof *a);
	demand(a, Out of memory);

	LIST_INIT(&a->kids);
	a->parent = parent;
	a->pid = pid;
	a->ir = ir;
	return a;
}

/* returns 1 on equality, -1 on lhs equality, 0 on inequality. */
static int isequal(struct ir *ir1, struct ir *ir2) {
	if(ir1->u.eq.op != ir2->u.eq.op)
		return 0;

	/* is an eq? */
	if(iseq(ir1)) {
		/* check for structural equality */
		return (ir1->u.eq.offset != ir2->u.eq.offset || 
				ir1->u.eq.mask != ir2->u.eq.mask) ? 
			0 : ((ir1->u.eq.val == ir2->u.eq.val) ? 1 : -1);
	}
	demand(isshift(ir1), bogus op!);

	/* is a shift */
	return (ir1->u.shift.shift == ir2->u.shift.shift &&
		ir1->u.shift.offset == ir2->u.shift.offset &&
		ir1->u.shift.mask == ir2->u.shift.mask);
}

/*
 *  Create a string of atoms from IR. Returns the last one and pointer
 * to first. 
 */
static Atom swizzle(struct ir *ir, int pid, Atom *first, int alignment) {
        Atom a, n;

        for(n = *first = a = 0; !isend(ir); ir++, a = n) {
		n = mkatom(a, 0, *ir);
                if(a)
                        LIST_INSERT_HEAD(&a->kids, n, sibs);
                else
                        *first = n;
		if(isshift(ir))
			alignment = dpf_compute_alignment(&n->ir, alignment);
		n->ir.alignment = alignment;
        }
	if(!n)
		return 0;
        n->pid = pid;
        return n;
}

static Atom ht_lookup(Ht ht, uint32 val, int *coll_p, Atom **succ) {
	Atom hte, *last;
	int coll;

	for(coll = 0, last = &ht->ht[hash(ht, val)], hte = *last; hte; ) {
		if(hte->ir.u.eq.val == val)
			break;
		last = &hte->next;
		if((hte = hte->next))
			coll = 1;
	}
	if(coll_p)
		*coll_p = coll;
	if(succ)
		*succ = last;
	return hte;
}

static Ht ht_alloc(int n, int nbits) {
	Ht ht;
	int sz;

	/* Compute size in presence of struct hack */
	sz = sizeof *ht + (n - DPF_INITIAL_HTSZ) * sizeof(struct atom);

	ht = (Ht)calloc(1, sz);
        demand(ht, Out of memory);
        ht->htsz = n;
	ht->log2_sz = log2(n);
	ht->nbits = ht->nbits;
	return ht;
}

/*
 * Expand an existing hash table.
 */
static void ht_expand(Atom a) {
	Ht ht, newh;
        int n;
        Atom p, *l;

	ht = a->ht;
	n = ht->htsz * 2;
	newh = a->ht = ht_alloc(n, ht->nbits);

#if 0
	printf("expanding from %d to %d, ent = %d, coll = %d, nbits = %d\n", 
		ht->htsz, n, ht->ent, ht->coll, ht->nbits);
#endif

	newh->ent = ht->ent;
	newh->nterm = ht->nterm;
	newh->term = ht->term;
        for (p = a->kids.lh_first; p; p = p->sibs.le_next) {
                l = &newh->ht[hash(newh, p->ir.u.eq.val)];
		if((p->next = *l))
			newh->coll++;
		*l = p;
        }
        free((void *)ht);
}

/* should we regen? */
static inline int ht_regenp(Ht ht) {
	return ht->state != ht_state(ht);
}

/* Standard thing: hash into ht.  At some point we would rehash. */
static Atom ht_insert(Atom a, int pid, struct ir *ir) {
	Atom hte, *p;
	Ht ht;

	ht = a->ht;
	if(!(hte = ht_lookup(ht, ir->u.eq.val, 0, 0))) { 
		hte = mkatom(a, pid, *ir);
		LIST_INSERT_HEAD(&a->kids, hte, sibs);

		p = &ht->ht[hash(ht, ir->u.eq.val)];

                /* collision */
                if((hte->next = *p))
                        ++ht->coll;
		*p = hte;
		ht->ent++;

                /* Grow if possible */
                if(ht->coll && (ht->ent * 100 >> ht->log2_sz) >= DPF_HT_USAGE) {
                	ht_expand(a);
			ht->state = DPF_REGEN;
		} else if(ht_regenp(ht))
			ht->state = DPF_REGEN;
	}
	return hte;
}


/* 
 * Delete ht entry - complication from the ht organization.  Caller
 * must ensure that refcnt is 0.
 */
static void ht_delete(Atom a, uint32 val, int term) {
	Atom hte, *last;
	Ht ht;
	int coll_p;

	ht = a->ht;
	hte = ht_lookup(ht, val, &coll_p, &last);
	demand(hte, deleting a bogus hte);
	*last = hte->next;
	ht->ent--;

	demand((ht->term + ht->nterm) == a->refcnt, bogus summation!);
	ht->coll -= coll_p;
	demand(ht->coll >= 0, bogus collision index);

	/* regen if we are not about to demote hash table. */
	if(ht->ent > 1 && ht_regenp(ht))
		dpf_compile_atom(a);
}

/* Create a new hash table and insert a as its first entry.  */
static Atom ht_newht(Atom a) {
	Ht ht;
	Atom deq;

	/* make deq node */
	deq = mkatom(a->parent, 0, a->ir);

	/* insert deq in place of a */
	LIST_INSERT_BEFORE(a, deq, sibs);
	LIST_REMOVE(a, sibs);

	/* create a hash table */
	deq->ht = ht = ht_alloc(DPF_INITIAL_HTSZ, deq->ir.u.eq.nbits);
	deq->refcnt = a->refcnt;

	/* Insert a into hash table. */
	ht->ht[hash(ht, a->ir.u.eq.val)] = a;
	ht->ent = 1;
	if(a->kids.lh_first)
		ht->nterm = a->refcnt;
	else
		ht->term = a->refcnt;
	ht->state = DPF_REGEN;

	LIST_INSERT_HEAD(&deq->kids, a, sibs);	
	a->parent = deq;

	dpf_compile_atom(deq->parent);	/* fix parent to jump here. */
	dpf_compile_atom(a); 	/* atom is now a hte: regen. */
	return deq;
}

/* 
 * Insert before or with smaller nbits; used to enforce "longest
 * match" in the presence of atom coalescing.
 */
static void insert_or(Atom a, Atom new) {
	Atom succ;

	new->parent = a->parent;
	for(succ = 0; a; succ = a, a = a->sibs.le_next)
		if(a->ir.u.eq.nbits < new->ir.u.eq.nbits)
			break;
	if(a) {
		LIST_INSERT_BEFORE(a, new, sibs);
		/* a is no longer the first node: regen. */
		if(!succ) {
			dpf_compile_atom(a);

			/* parent jumps to us directly, regen if necessary. */
			dpf_compile_atom(a->parent);
		}
	} else {
		LIST_INSERT_AFTER(succ, new, sibs);
		/* succ is no longer the last atom: regen. */
		if(!a)
			dpf_compile_atom(succ);
	}
}

/*
 * Atom merge rules.  If two atoms: 
 *  - are identical, merge
 *  - are an eq & use the same mask, but compare to a different 
 * 	constants, create a hash table.
 *  - otherwise, iterate to next kid.  If no more, add as an or node.
 */
static Atom merge(Atom a, struct ir *ir, int pid) {
	Atom succ, last, first, hte, first_or;
	int res, alignment;

	alignment = DPF_MSG_ALIGN;
	succ = dpf_base;
	a = a->kids.lh_first;

	for(; a && !isend(ir); succ = a, a = a->kids.lh_first, ir++) {
		/* Walk down or's, checking for match. */
		for(res = 0, first_or = a; a; succ = a, a = a->sibs.le_next) 
			if((res = isequal(&a->ir, ir)))
				break;
		/* if new alignment, update. */
		if(a && isshift(&a->ir))
			alignment = a->ir.alignment; // a->ir.u.shift.align;