ipv4: fix fnhe dump record multiplication
Subsystems (3)
RFC PATCH 1/1 ipv4: fix fnhe dump record multiplication
Fix the multiplication of the FNHE records during dump: Check in fnhe_dump_bucket() that the dumped record destination address falls within the key (prefix, prefixlen) of the FIB leaf that is being dumped.
FNHE table records can be dumped multiple times to netlink on RTM_GETROUTE command with NLM_F_DUMP flag - either to "ip route show cache" or to any routing daemon. The multiplication is substantial under specific conditions - it can produce over 120M netlink messages in one dump. It happens if there is one shared struct fib_nh linked through struct fib_info (->fib_nh) from many leafs in FIB over struct fib_alias.
This situation can be triggered by importing a full BGP table over GRE tunnel. In this case there are ~800k routes that translates to ~120k leafs in FIB that all ulimately links the same next-hop (the other end of the GRE tunnel). The GRE tunnel creates one FNHE record for each destination IP that is routed to the tunnel because of PMTU. In my case I had around 1000 PMTU records after a few minutes in a lab connected to the public internet so the FNHE dump produced 120M records that easily stalled BIRD routing daemon as described here:
http://trubka.network.cz/pipermail/bird-users/2022-January/015897.html
(There is a work-around already committed to BIRD that removes unnecessary dumps of FNHE.)
--- include/net/route.h | 3 ++- net/ipv4/fib_trie.c | 3 ++- net/ipv4/route.c | 25 ++++++++++++++++++++++--- 3 files changed, 26 insertions(+), 5 deletions(-)
include/net/route.h +2 -1
@@ -244,7 +244,8 @@ void rt_del_uncached_list(struct rtable *rt);int fib_dump_info_fnhe (struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fib_info *fi, -int *fa_index,int fa_start,unsigned int flags); +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen);static inline void ip_rt_put (struct rtable *rt) {
net/ipv4/fib_trie.c +2 -1
@@ -2313,7 +2313,8 @@ static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,if (filter->dump_exceptions) { err =fib_dump_info_fnhe (skb, cb, tb->tb_id, fi, - &i_fa, s_fa, flags); + &i_fa, s_fa, flags, xkey, + (KEYLENGTH - fa->fa_slen));if (err <0 ) goto stop; }
net/ipv4/route.c +22 -3
@@ -3049,10 +3049,25 @@ static int rt_fill_info(struct net *net, __be32 dst, __be32 src,return -EMSGSIZE ; } +static int fnhe_daddr_check (__be32 daddr,struct net *net,u32 table_id, +__be32 prefix,unsigned char prefixlen) +{ +struct flowi4 fl4 = { .daddr = daddr }; +struct fib_table *tb =fib_get_table (net, table_id); +struct fib_result res; +int err =fib_table_lookup (tb, &fl4, &res,FIB_LOOKUP_NOREF ); + +if (!err && res.prefix == prefix && res.prefixlen == prefixlen) +return 1 ; + +return 0 ; +} +static int fnhe_dump_bucket (struct net *net,struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fnhe_hash_bucket *bucket,int genid, -int *fa_index,int fa_start,unsigned int flags) +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen) {int i;
@@ -3067,6 +3082,9 @@ static int fnhe_dump_bucket(struct net *net, struct sk_buff *skb,if (*fa_index < fa_start) goto next; +if (!fnhe_daddr_check (fnhe->fnhe_daddr, net, table_id, prefix, prefixlen)) + goto next; +if (fnhe->fnhe_genid != genid) goto next;
@@ -3096,7 +3114,8 @@ static int fnhe_dump_bucket(struct net *net, struct sk_buff *skb,int fib_dump_info_fnhe (struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fib_info *fi, -int *fa_index,int fa_start,unsigned int flags) +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen) {struct net *net =sock_net (cb->skb->sk);int nhsel, genid =fnhe_genid (net);
@@ -3115,7 +3134,7 @@ int fib_dump_info_fnhe(struct sk_buff *skb, struct netlink_callback *cb,if (bucket) err =fnhe_dump_bucket (net, skb, cb, table_id, bucket, genid, fa_index, fa_start, - flags); + flags, prefix, prefixlen);rcu_read_unlock ();if (err)return err;
Signature · 1 line
2.25.1
[ cc Stefano and Ido ]
Quoted 63 lines · Tomas Hlavacek
Fix the multiplication of the FNHE records during dump: Check in
fnhe_dump_bucket()that the dumped record destination address falls within the key (prefix, prefixlen) of the FIB leaf that is being dumped.FNHE table records can be dumped multiple times to netlink on
RTM_GETROUTEcommand withNLM_F_DUMPflag - either to "ip route show cache" or to any routing daemon. The multiplication is substantial under specific conditions - it can produce over 120M netlink messages in one dump. It happens if there is one shared structfib_nhlinked through structfib_info(->fib_nh) from many leafs in FIB over structfib_alias.This situation can be triggered by importing a full BGP table over GRE tunnel. In this case there are ~800k routes that translates to ~120k leafs in FIB that all ulimately links the same next-hop (the other end of the GRE tunnel). The GRE tunnel creates one FNHE record for each destination IP that is routed to the tunnel because of PMTU. In my case I had around 1000 PMTU records after a few minutes in a lab connected to the public internet so the FNHE dump produced 120M records that easily stalled BIRD routing daemon as described here:
http://trubka.network.cz/pipermail/bird-users/2022-January/015897.html
(There is a work-around already committed to BIRD that removes unnecessary dumps of FNHE.)Signed-off-by Tomas Hlavacek <[email protected]>--- include/net/route.h | 3 ++- net/ipv4/fib_trie.c | 3 ++- net/ipv4/route.c | 25 ++++++++++++++++++++++--- 3 files changed, 26 insertions(+), 5 deletions(-)include/net/route.h +2
-1@@ -244,7 +244,8 @@ void rt_del_uncached_list(struct rtable *rt);int fib_dump_info_fnhe (struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fib_info *fi, -int *fa_index,int fa_start,unsigned int flags); +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen);static inline void ip_rt_put (struct rtable *rt) {net/ipv4/fib_trie.c +2
-1@@ -2313,7 +2313,8 @@ static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,if (filter->dump_exceptions) { err =fib_dump_info_fnhe (skb, cb, tb->tb_id, fi, - &i_fa, s_fa, flags); + &i_fa, s_fa, flags, xkey, + (KEYLENGTH - fa->fa_slen));if (err <0 ) goto stop; }net/ipv4/route.c +0
-0
net/ipv4/route.c static int rt_fill_info(struct net *net, __be32 dst, __be32 src, · line 3058
Quoted 10 lines
net/ipv4/route.c +7
-0@@ -3049,10 +3049,25 @@ static int rt_fill_info(struct net *net, __be32 dst, __be32 src,return -EMSGSIZE ; } +static int fnhe_daddr_check (__be32 daddr,struct net *net,u32 table_id, +__be32 prefix,unsigned char prefixlen) +{ +struct flowi4 fl4 = { .daddr = daddr }; +struct fib_table *tb =fib_get_table (net, table_id); +struct fib_result res; +int err =fib_table_lookup (tb, &fl4, &res,FIB_LOOKUP_NOREF );
I get the fundamental problem you want to solve. I think a fib lookup on each nexthop exception for each leaf is a heavyweight solution this is going to add up to significant overhead.
The fundamental problem you are trying to solve is to not walk the exceptions for a fib_info more than once. A fib_info can be used with many fib_entries so perhaps the solution is to walk the fib_info structs that exist in fib_info_hash outside of the trie walk.
Quoted 45 lines
net/ipv4/route.c +15
-3+ +if (!err && res.prefix == prefix && res.prefixlen == prefixlen) +return 1 ; + +return 0 ; +} +static int fnhe_dump_bucket (struct net *net,struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fnhe_hash_bucket *bucket,int genid, -int *fa_index,int fa_start,unsigned int flags) +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen) {int i;@@ -3067,6 +3082,9 @@ static int fnhe_dump_bucket(struct net *net, struct sk_buff *skb,if (*fa_index < fa_start) goto next; +if (!fnhe_daddr_check (fnhe->fnhe_daddr, net, table_id, prefix, prefixlen)) + goto next; +if (fnhe->fnhe_genid != genid) goto next;@@ -3096,7 +3114,8 @@ static int fnhe_dump_bucket(struct net *net, struct sk_buff *skb,int fib_dump_info_fnhe (struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fib_info *fi, -int *fa_index,int fa_start,unsigned int flags) +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen) {struct net *net =sock_net (cb->skb->sk);int nhsel, genid =fnhe_genid (net);@@ -3115,7 +3134,7 @@ int fib_dump_info_fnhe(struct sk_buff *skb, struct netlink_callback *cb,if (bucket) err =fnhe_dump_bucket (net, skb, cb, table_id, bucket, genid, fa_index, fa_start, - flags); + flags, prefix, prefixlen);rcu_read_unlock ();if (err)return err;
Quoted 69 lines · David Ahern
[ cc Stefano and Ido ]
Quoted 66 lines · Tomas Hlavacek
Fix the multiplication of the FNHE records during dump: Check in
fnhe_dump_bucket()that the dumped record destination address falls within the key (prefix, prefixlen) of the FIB leaf that is being dumped.FNHE table records can be dumped multiple times to netlink on
RTM_GETROUTEcommand withNLM_F_DUMPflag - either to "ip route show cache" or to any routing daemon. The multiplication is substantial under specific conditions - it can produce over 120M netlink messages in one dump. It happens if there is one shared structfib_nhlinked through structfib_info(->fib_nh) from many leafs in FIB over structfib_alias.This situation can be triggered by importing a full BGP table over GRE tunnel. In this case there are ~800k routes that translates to ~120k leafs in FIB that all ulimately links the same next-hop (the other end of the GRE tunnel). The GRE tunnel creates one FNHE record for each destination IP that is routed to the tunnel because of PMTU. In my case I had around 1000 PMTU records after a few minutes in a lab connected to the public internet so the FNHE dump produced 120M records that easily stalled BIRD routing daemon as described here:
http://trubka.network.cz/pipermail/bird-users/2022-January/015897.html
(There is a work-around already committed to BIRD that removes unnecessary dumps of FNHE.)Signed-off-by Tomas Hlavacek <[email protected]>--- include/net/route.h | 3 ++- net/ipv4/fib_trie.c | 3 ++- net/ipv4/route.c | 25 ++++++++++++++++++++++--- 3 files changed, 26 insertions(+), 5 deletions(-)include/net/route.h +2
-1@@ -244,7 +244,8 @@ void rt_del_uncached_list(struct rtable *rt);int fib_dump_info_fnhe (struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fib_info *fi, -int *fa_index,int fa_start,unsigned int flags); +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen);static inline void ip_rt_put (struct rtable *rt) {net/ipv4/fib_trie.c +2
-1@@ -2313,7 +2313,8 @@ static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,if (filter->dump_exceptions) { err =fib_dump_info_fnhe (skb, cb, tb->tb_id, fi, - &i_fa, s_fa, flags); + &i_fa, s_fa, flags, xkey, + (KEYLENGTH - fa->fa_slen));if (err <0 ) goto stop; }net/ipv4/route.c +0
-0@@ -3049,10 +3049,25 @@ static int rt_fill_info(struct net *net, __be32 dst, __be32 src,return -EMSGSIZE ; }
Quoted 11 lines
net/ipv4/route.c static int rt_fill_info(struct net *net, __be32 dst, __be32 src, · line 3058
Quoted 7 lines
net/ipv4/route.c +7
-0+static int fnhe_daddr_check (__be32 daddr,struct net *net,u32 table_id, +__be32 prefix,unsigned char prefixlen) +{ +struct flowi4 fl4 = { .daddr = daddr }; +struct fib_table *tb =fib_get_table (net, table_id); +struct fib_result res; +int err =fib_table_lookup (tb, &fl4, &res,FIB_LOOKUP_NOREF );I get the fundamental problem you want to solve. I think a fib lookup on each nexthop exception for each leaf is a heavyweight solution this is going to add up to significant overhead.
I agree
Quoted 5 lines
The fundamental problem you are trying to solve is to not walk the exceptions for a
fib_infomore than once. Afib_infocan be used with manyfib_entriesso perhaps the solution is to walk thefib_infostructs that exist infib_info_hashoutside of the trie walk.
Sounds like a good idea, though I'm not sure how difficult to implement. If a dump needs to be restarted, then the netlink callback arguments need to differentiate between the place in the FIB trie where the dump was stopped and the FIB info hash table.
Also, isn't the problem also present in IPv6 when nexthop objects are used? In the legacy model, IPv6 nexthops are not shared (which means exceptions are not dumped multiple times), but with nexthop objects they can be shared.
Quoted 48 lines
Quoted 47 lines
net/ipv4/route.c +15
-3+ +if (!err && res.prefix == prefix && res.prefixlen == prefixlen) +return 1 ; + +return 0 ; +} +static int fnhe_dump_bucket (struct net *net,struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fnhe_hash_bucket *bucket,int genid, -int *fa_index,int fa_start,unsigned int flags) +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen) {int i;@@ -3067,6 +3082,9 @@ static int fnhe_dump_bucket(struct net *net, struct sk_buff *skb,if (*fa_index < fa_start) goto next; +if (!fnhe_daddr_check (fnhe->fnhe_daddr, net, table_id, prefix, prefixlen)) + goto next; +if (fnhe->fnhe_genid != genid) goto next;@@ -3096,7 +3114,8 @@ static int fnhe_dump_bucket(struct net *net, struct sk_buff *skb,int fib_dump_info_fnhe (struct sk_buff *skb,struct netlink_callback *cb,u32 table_id,struct fib_info *fi, -int *fa_index,int fa_start,unsigned int flags) +int *fa_index,int fa_start,unsigned int flags, +__be32 prefix,unsigned char prefixlen) {struct net *net =sock_net (cb->skb->sk);int nhsel, genid =fnhe_genid (net);@@ -3115,7 +3134,7 @@ int fib_dump_info_fnhe(struct sk_buff *skb, struct netlink_callback *cb,if (bucket) err =fnhe_dump_bucket (net, skb, cb, table_id, bucket, genid, fa_index, fa_start, - flags); + flags, prefix, prefixlen);rcu_read_unlock ();if (err)return err;