121 	t_key key;  member
218 #define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)  argument
220 static inline unsigned long get_index(t_key key, struct key_vector *kv)  in get_index()  argument
222 	unsigned long index = key ^ kv->key;  in get_index()
353 static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)  in leaf_new()  argument
364 	l->key = key;  in leaf_new()
376 static struct key_vector *tnode_new(t_key key, int pos, int bits)  in tnode_new()  argument
398 	tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;  in tnode_new()
468 static inline void put_child_root(struct key_vector *tp, t_key key,  in put_child_root()  argument
474 		put_child(tp, get_index(key, tp), n);  in put_child_root()
516 	put_child_root(tp, tn->key, tn);  in replace()
545 	tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);  in inflate()
568 			put_child(tn, get_index(inode->key, tn), inode);  in inflate()
596 		node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);  in inflate()
599 		node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);  in inflate()
640 	tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);  in halve()
664 		inode = tnode_new(node0->key, oldtnode->pos, 1);  in halve()
699 	put_child_root(tp, oldtnode->key, n);  in collapse()
853 	unsigned long cindex = get_index(tn->key, tp);  in resize()
936 					struct key_vector **tp, u32 key)  in fib_find_node()  argument
948 		index = get_cindex(key, n);  in fib_find_node()
1110 			   struct fib_alias *new, t_key key)  in fib_insert_node()  argument
1114 	l = leaf_new(key, new);  in fib_insert_node()
1119 	n = get_child(tp, get_index(key, tp));  in fib_insert_node()
1130 		tn = tnode_new(key, __fls(key ^ n->key), 1);  in fib_insert_node()
1136 		put_child(tn, get_index(key, tn) ^ 1, n);  in fib_insert_node()
1139 		put_child_root(tp, key, tn);  in fib_insert_node()
1149 	put_child_root(tp, key, l);  in fib_insert_node()
1161 			    struct fib_alias *fa, t_key key)  in fib_insert_alias()  argument
1164 		return fib_insert_node(t, tp, new, key);  in fib_insert_alias()
1195 static bool fib_valid_key_len(u32 key, u8 plen, struct netlink_ext_ack *extack)  in fib_valid_key_len()  argument
1202 	if ((plen < KEYLENGTH) && (key << plen)) {  in fib_valid_key_len()
1226 	u32 key;  in fib_table_insert()  local
1229 	key = ntohl(cfg->fc_dst);  in fib_table_insert()
1231 	if (!fib_valid_key_len(key, plen, extack))  in fib_table_insert()
1234 	pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);  in fib_table_insert()
1243 	l = fib_find_node(t, &tp, key);  in fib_table_insert()
1324 							       key, plen,  in fib_table_insert()
1333 			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,  in fib_table_insert()
1378 	err = fib_insert_alias(t, tp, l, new_fa, fa, key);  in fib_table_insert()
1383 	l = l ? l : fib_find_node(t, &tp, key);  in fib_table_insert()
1394 		err = call_fib_entry_notifiers(net, fib_event, key, plen,  in fib_table_insert()
1404 	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, new_fa->tb_id,  in fib_table_insert()
1419 static inline t_key prefix_mismatch(t_key key, struct key_vector *n)  in prefix_mismatch()  argument
1421 	t_key prefix = n->key;  in prefix_mismatch()
1423 	return (key ^ prefix) & (prefix | -prefix);  in prefix_mismatch()
1451 	const t_key key = ntohl(flp->daddr);  in fib_table_lookup()  local
1472 		index = get_cindex(key, n);  in fib_table_lookup()
1517 		if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))  in fib_table_lookup()
1541 				t_key pkey = pn->key;  in fib_table_lookup()
1570 	index = key ^ n->key;  in fib_table_lookup()
1625 			res->prefix = htonl(n->key);  in fib_table_lookup()
1667 		put_child_root(tp, l->key, NULL);  in fib_remove_alias()
1682 static void fib_notify_alias_delete(struct net *net, u32 key,  in fib_notify_alias_delete()  argument
1708 	call_fib_entry_notifiers(net, fib_event, key, KEYLENGTH - slen,  in fib_notify_alias_delete()
1722 	u32 key;  in fib_table_delete()  local
1724 	key = ntohl(cfg->fc_dst);  in fib_table_delete()
1726 	if (!fib_valid_key_len(key, plen, extack))  in fib_table_delete()
1729 	l = fib_find_node(t, &tp, key);  in fib_table_delete()
1738 	pr_debug("Deleting %08x/%d dsfield=0x%02x t=%p\n", key, plen,  in fib_table_delete()
1767 	fib_notify_alias_delete(net, key, &l->leaf, fa_to_delete, extack);  in fib_table_delete()
1768 	rtmsg_fib(RTM_DELROUTE, htonl(key), fa_to_delete, plen, tb->tb_id,  in fib_table_delete()
1785 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)  in leaf_walk_rcu()  argument
1794 		cindex = (key > pn->key) ? get_index(key, pn) : 0;  in leaf_walk_rcu()
1805 		if (IS_LEAF(n) && (n->key >= key))  in leaf_walk_rcu()
1813 			t_key pkey = pn->key;  in leaf_walk_rcu()
1855 			t_key pkey = pn->key;  in fib_trie_free()
1864 			put_child_root(pn, n->key, NULL);  in fib_trie_free()
1890 		put_child_root(pn, n->key, NULL);  in fib_trie_free()
1907 	t_key key = 0;  in fib_trie_unmerge()  local
1918 	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {  in fib_trie_unmerge()
1936 				local_l = fib_find_node(lt, &local_tp, l->key);  in fib_trie_unmerge()
1939 					     NULL, l->key)) {  in fib_trie_unmerge()
1946 		key = l->key + 1;  in fib_trie_unmerge()
1947 		if (key < l->key)  in fib_trie_unmerge()
1973 			t_key pkey = pn->key;  in fib_table_flush_external()
2021 			put_child_root(pn, n->key, NULL);  in fib_table_flush_external()
2044 			t_key pkey = pn->key;  in fib_table_flush()
2092 			fib_notify_alias_delete(net, n->key, &n->leaf, fa,  in fib_table_flush()
2095 				rtmsg_fib(RTM_DELROUTE, htonl(n->key), fa,  in fib_table_flush()
2107 			put_child_root(pn, n->key, NULL);  in fib_table_flush()
2129 			t_key pkey = pn->key;  in __fib_info_notify_update()
2158 			rtmsg_fib(RTM_NEWROUTE, htonl(n->key), fa,  in __fib_info_notify_update()
2204 					      l->key, KEYLENGTH - fa->fa_slen,  in fib_leaf_notify()
2217 	t_key key = 0;  in fib_table_notify()  local
2220 	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {  in fib_table_notify()
2225 		key = l->key + 1;  in fib_table_notify()
2227 		if (key < l->key)  in fib_table_notify()
2274 	__be32 xkey = htonl(l->key);  in fn_trie_dump_leaf()
2365 	t_key key = cb->args[3];  in fib_table_dump()  local
2370 	if (count && !key)  in fib_table_dump()
2373 	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {  in fib_table_dump()
2378 			cb->args[3] = key;  in fib_table_dump()
2384 		key = l->key + 1;  in fib_table_dump()
2390 		if (key < l->key)  in fib_table_dump()
2394 	cb->args[3] = key;  in fib_table_dump()
2485 		pkey = pn->key;  in fib_trie_get_next()
2807 		__be32 prf = htonl(n->key);  in fib_trie_seq_show()
2815 		__be32 val = htonl(n->key);  in fib_trie_seq_show()
2853 	t_key	key;  member
2860 	t_key key;  in fib_route_get_idx()  local
2864 		key = iter->key;  in fib_route_get_idx()
2867 		key = 0;  in fib_route_get_idx()
2872 	while ((l = leaf_walk_rcu(tp, key)) && (pos-- > 0)) {  in fib_route_get_idx()
2873 		key = l->key + 1;  in fib_route_get_idx()
2878 		if (!key)  in fib_route_get_idx()
2883 		iter->key = l->key;	/* remember it */  in fib_route_get_idx()
2911 	iter->key = KEY_MAX;  in fib_route_seq_start()
2920 	t_key key = iter->key + 1;  in fib_route_seq_next()  local
2925 	if ((v == SEQ_START_TOKEN) || key)  in fib_route_seq_next()
2926 		l = leaf_walk_rcu(&iter->tnode, key);  in fib_route_seq_next()
2929 		iter->key = l->key;  in fib_route_seq_next()
2983 	prefix = htonl(l->key);  in fib_route_seq_show()