else { 
} else { 
fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res){	struct trie *t = (struct trie *) tb->tb_data;	int plen, ret = 0;	struct node *n;	struct tnode *pn;	int pos, bits;	t_key key=ntohl(flp->fl4_dst);	int chopped_off;	t_key cindex = 0;	int current_prefix_length = KEYLENGTH;	n = t->trie;	read_lock(&fib_lock);	if (!n)		goto failed;#ifdef CONFIG_IP_FIB_TRIE_STATS	t->stats.gets++;#endif	/* Just a leaf? */	if (IS_LEAF(n)) {		if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)			goto found;		goto failed;	}	pn = (struct tnode *) n;	chopped_off = 0;        while (pn) {		pos = pn->pos;		bits = pn->bits;		if (!chopped_off)			cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);		n = tnode_get_child(pn, cindex);		if (n == NULL) {#ifdef CONFIG_IP_FIB_TRIE_STATS			t->stats.null_node_hit++;#endif			goto backtrace;		}		if (IS_TNODE(n)) {#define HL_OPTIMIZE#ifdef HL_OPTIMIZE			struct tnode *cn = (struct tnode *)n;			t_key node_prefix, key_prefix, pref_mismatch;			int mp;			/*			 * It's a tnode, and we can do some extra checks here if we			 * like, to avoid descending into a dead-end branch.			 * This tnode is in the parent's child array at index			 * key[p_pos..p_pos+p_bits] but potentially with some bits			 * chopped off, so in reality the index may be just a			 * subprefix, padded with zero at the end.			 * We can also take a look at any skipped bits in this			 * tnode - everything up to p_pos is supposed to be ok,			 * and the non-chopped bits of the index (se previous			 * paragraph) are also guaranteed ok, but the rest is			 * considered unknown.			 *			 * The skipped bits are key[pos+bits..cn->pos].			 */					/* If current_prefix_length < pos+bits, we are already doing			 * actual prefix  matching, which means everything from			 * pos+(bits-chopped_off) onward must be zero along some			 * branch of this subtree - otherwise there is *no* valid			 * prefix present. Here we can only check the skipped			 * bits. Remember, since we have already indexed into the			 * parent's child array, we know that the bits we chopped of			 * *are* zero.			 */			/* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */					if (current_prefix_length < pos+bits) {				if (tkey_extract_bits(cn->key, current_prefix_length,						      cn->pos - current_prefix_length) != 0 ||				    !(cn->child[0]))					goto backtrace;			}			/*			 * If chopped_off=0, the index is fully validated and we			 * only need to look at the skipped bits for this, the new,			 * tnode. What we actually want to do is to find out if			 * these skipped bits match our key perfectly, or if we will			 * have to count on finding a matching prefix further down,			 * because if we do, we would like to have some way of			 * verifying the existence of such a prefix at this point.			 */			/* The only thing we can do at this point is to verify that			 * any such matching prefix can indeed be a prefix to our			 * key, and if the bits in the node we are inspecting that			 * do not match our key are not ZERO, this cannot be true.			 * Thus, find out where there is a mismatch (before cn->pos)			 * and verify that all the mismatching bits are zero in the			 * new tnode's key.			 */			/* Note: We aren't very concerned about the piece of the key			 * that precede pn->pos+pn->bits, since these have already been			 * checked. The bits after cn->pos aren't checked since these are			 * by definition "unknown" at this point. Thus, what we want to			 * see is if we are about to enter the "prefix matching" state,			 * and in that case verify that the skipped bits that will prevail			 * throughout this subtree are zero, as they have to be if we are			 * to find a matching prefix.			 */			node_prefix = MASK_PFX(cn->key, cn->pos);			key_prefix = MASK_PFX(key, cn->pos);			pref_mismatch = key_prefix^node_prefix;			mp = 0;			/* In short: If skipped bits in this node do not match the search			 * key, enter the "prefix matching" state.directly.			 */			if (pref_mismatch) {				while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {					mp++;					pref_mismatch = pref_mismatch <<1;				}				key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);							if (key_prefix != 0)					goto backtrace;				if (current_prefix_length >= cn->pos)					current_prefix_length=mp;		       }#endif		       pn = (struct tnode *)n; /* Descend */		       chopped_off = 0;		       continue;		}		if (IS_LEAF(n)) {			if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)				goto found;	       }backtrace:		chopped_off++;		/* As zero don't change the child key (cindex) */		while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1)))) {			chopped_off++;		}		/* Decrease current_... with bits chopped off */		if (current_prefix_length > pn->pos + pn->bits - chopped_off)			current_prefix_length = pn->pos + pn->bits - chopped_off;			/*		 * Either we do the actual chop off according or if we have		 * chopped off all bits in this tnode walk up to our parent.		 */		if (chopped_off <= pn->bits)			cindex &= ~(1 << (chopped_off-1));		else {			if (NODE_PARENT(pn) == NULL)				goto failed;					/* Get Child's index */			cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);			pn = NODE_PARENT(pn);			chopped_off = 0;#ifdef CONFIG_IP_FIB_TRIE_STATS			t->stats.backtrack++;#endif			goto backtrace;		}	}failed:	ret = 1;found:	read_unlock(&fib_lock);	return ret;}
4520	/local/tlutelli/issta_data/temp/c/2005_temp/2005/4520/91b9a277fc4d207249e459a455abf804ebb5499d/fib_trie.c/buggy/net/ipv4/fib_trie.c