net/ipv4/fib_trie.c

78 				   int dst_len, struct fib_alias *fa,
85 		.fi = fa->fa_info,
86 		.dscp = fa->fa_dscp,
87 		.type = fa->fa_type,
88 		.tb_id = fa->tb_id,
95 				    int dst_len, struct fib_alias *fa,
102 		.fi = fa->fa_info,
103 		.dscp = fa->fa_dscp,
104 		.type = fa->fa_type,
105 		.tb_id = fa->tb_id,
297 	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
298 	kmem_cache_free(fn_alias_kmem, fa);
301 static inline void alias_free_mem_rcu(struct fib_alias *fa)
303 	call_rcu(&fa->rcu, __alias_free_mem);
354 static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
368 	l->slen = fa->fa_slen;
372 	hlist_add_head(&fa->fa_list, &l->leaf);
987 	struct fib_alias *fa;
992 	hlist_for_each_entry(fa, fah, fa_list) {
994 		u8 __fa_dscp = inet_dscp_to_dsfield(fa->fa_dscp);
997 		if (fa->fa_slen < slen)
999 		if (fa->fa_slen != slen)
1001 		if (fa->tb_id > tb_id)
1003 		if (fa->tb_id != tb_id)
1006 			return fa;
1009 		if (fa->fa_info->fib_priority >= prio || __fa_dscp < __dscp)
1010 			return fa;
1022 	struct fib_alias *fa;
1034 	hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
1035 		if (fa->fa_slen == slen && fa->tb_id == fri->tb_id &&
1036 		    fa->fa_dscp == fri->dscp && fa->fa_info == fri->fi &&
1037 		    fa->fa_type == fri->type)
1038 			return fa;
1162 			    struct fib_alias *fa, t_key key)
1167 	if (fa) {
1168 		hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
1178 			fa = last;
1181 		if (fa)
1182 			hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);
1220 	struct fib_alias *fa, *new_fa;
1245 	fa = l ? fib_find_alias(&l->leaf, slen, dscp, fi->fib_priority,
1248 	/* Now fa, if non-NULL, points to the first fib alias
1252 	 * If fa is NULL, we will need to allocate a new one and
1257 	if (fa && fa->fa_dscp == dscp &&
1258 	    fa->fa_info->fib_priority == fi->fib_priority) {
1270 		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1273 		fa_first = fa;
1274 		hlist_for_each_entry_from(fa, fa_list) {
1275 			if ((fa->fa_slen != slen) ||
1276 			    (fa->tb_id != tb->tb_id) ||
1277 			    (fa->fa_dscp != dscp))
1279 			if (fa->fa_info->fib_priority != fi->fib_priority)
1281 			if (fa->fa_type == cfg->fc_type &&
1282 			    fa->fa_info == fi) {
1283 				fa_match = fa;
1293 			fa = fa_first;
1295 				if (fa == fa_match)
1304 			fi_drop = fa->fa_info;
1305 			new_fa->fa_dscp = fa->fa_dscp;
1308 			state = fa->fa_state;
1310 			new_fa->fa_slen = fa->fa_slen;
1317 			hlist_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1319 			if (fib_find_alias(&l->leaf, fa->fa_slen, 0, 0,
1329 							  &fa->fa_list);
1337 			alias_free_mem_rcu(fa);
1355 			fa = fa_first;
1379 	err = fib_insert_alias(t, tp, l, new_fa, fa, key);
1454 	struct fib_alias *fa;
1574 	hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
1575 		struct fib_info *fi = fa->fa_info;
1579 		if ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen < KEYLENGTH)) {
1580 			if (index >= (1ul << fa->fa_slen))
1583 		if (fa->fa_dscp &&
1584 		    inet_dscp_to_dsfield(fa->fa_dscp) != flp->flowi4_tos)
1589 		if (fa->fa_info->fib_scope < flp->flowi4_scope)
1591 		fib_alias_accessed(fa);
1592 		err = fib_props[fa->fa_type].error;
1627 			res->prefixlen = KEYLENGTH - fa->fa_slen;
1630 			res->type = fa->fa_type;
1656 	struct fib_alias *fa = hlist_entry(pprev, typeof(*fa), fa_list.next);
1673 	/* only access fa if it is pointing at the last valid hlist_node */
1678 	l->slen = fa->fa_slen;
1679 	node_pull_suffix(tp, fa->fa_slen);
1717 	struct fib_alias *fa, *fa_to_delete;
1734 	fa = fib_find_alias(&l->leaf, slen, dscp, 0, tb->tb_id, false);
1735 	if (!fa)
1742 	hlist_for_each_entry_from(fa, fa_list) {
1743 		struct fib_info *fi = fa->fa_info;
1745 		if ((fa->fa_slen != slen) ||
1746 		    (fa->tb_id != tb->tb_id) ||
1747 		    (fa->fa_dscp != dscp))
1750 		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1752 		     fa->fa_info->fib_scope == cfg->fc_scope) &&
1759 			fa_to_delete = fa;
1848 	struct fib_alias *fa;
1885 		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
1886 			hlist_del_rcu(&fa->fa_list);
1887 			alias_free_mem_rcu(fa);
1905 	struct fib_alias *fa;
1921 		hlist_for_each_entry(fa, &l->leaf, fa_list) {
1924 			if (local_tb->tb_id != fa->tb_id)
1927 			/* clone fa for new local table */
1932 			memcpy(new_fa, fa, sizeof(*fa));
1965 	struct fib_alias *fa;
2003 		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
2007 			if (tb->tb_id != fa->tb_id) {
2008 				hlist_del_rcu(&fa->fa_list);
2009 				alias_free_mem_rcu(fa);
2014 			slen = fa->fa_slen;
2035 	struct fib_alias *fa;
2074 		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
2075 			struct fib_info *fi = fa->fa_info;
2077 			if (!fi || tb->tb_id != fa->tb_id ||
2079 			     !fib_props[fa->fa_type].error)) {
2080 				slen = fa->fa_slen;
2087 			if (!flush_all && fib_props[fa->fa_type].error) {
2088 				slen = fa->fa_slen;
2092 			fib_notify_alias_delete(net, n->key, &n->leaf, fa,
2095 				rtmsg_fib(RTM_DELROUTE, htonl(n->key), fa,
2096 					  KEYLENGTH - fa->fa_slen, tb->tb_id, &info, 0);
2097 			hlist_del_rcu(&fa->fa_list);
2098 			fib_release_info(fa->fa_info);
2099 			alias_free_mem_rcu(fa);
2123 	struct fib_alias *fa;
2152 		hlist_for_each_entry(fa, &n->leaf, fa_list) {
2153 			struct fib_info *fi = fa->fa_info;
2155 			if (!fi || !fi->nh_updated || fa->tb_id != tb->tb_id)
2158 			rtmsg_fib(RTM_NEWROUTE, htonl(n->key), fa,
2159 				  KEYLENGTH - fa->fa_slen, tb->tb_id,
2183 	struct fib_alias *fa;
2187 	hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
2188 		struct fib_info *fi = fa->fa_info;
2196 		if (tb->tb_id != fa->tb_id)
2199 		if (fa->fa_slen == last_slen)
2202 		last_slen = fa->fa_slen;
2204 					      l->key, KEYLENGTH - fa->fa_slen,
2205 					      fa, extack);
2276 	struct fib_alias *fa;
2287 	hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
2288 		struct fib_info *fi = fa->fa_info;
2295 		if (tb->tb_id != fa->tb_id)
2299 			if (filter->rt_type && fa->fa_type != filter->rt_type)
2318 				fri.dst_len = KEYLENGTH - fa->fa_slen;
2319 				fri.dscp = fa->fa_dscp;
2320 				fri.type = fa->fa_type;
2321 				fri.offload = READ_ONCE(fa->offload);
2322 				fri.trap = READ_ONCE(fa->trap);
2323 				fri.offload_failed = READ_ONCE(fa->offload_failed);
2534 			struct fib_alias *fa;
2541 			hlist_for_each_entry_rcu(fa, &n->leaf, fa_list)
2816 		struct fib_alias *fa;
2821 		hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
2826 				   KEYLENGTH - fa->fa_slen,
2828 					     fa->fa_info->fib_scope),
2830 					    fa->fa_type));
2831 			if (fa->fa_dscp)
2833 					   inet_dscp_to_dsfield(fa->fa_dscp));
2972 	struct fib_alias *fa;
2985 	hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
2986 		struct fib_info *fi = fa->fa_info;
2987 		__be32 mask = inet_make_mask(KEYLENGTH - fa->fa_slen);
2988 		unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2990 		if ((fa->fa_type == RTN_BROADCAST) ||
2991 		    (fa->fa_type == RTN_MULTICAST))
2994 		if (fa->tb_id != tb->tb_id)