n = t->trie; 
rcu_read_lock(); 
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;	struct tnode *cn;	t_key node_prefix, key_prefix, pref_mismatch;	int mp;	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_LEAF(n)) {			if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)				goto found;			else				goto backtrace;		}#define HL_OPTIMIZE#ifdef HL_OPTIMIZE		cn = (struct tnode *)n;		/*		 * 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;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;}
10457	/local/tlutelli/issta_data/temp/c/2005_temp/2005/10457/2373ce1ca04dd46bf2b8b0f9a799eb2a90da92fb/fib_trie.c/buggy/net/ipv4/fib_trie.c