netfilter: nf_tables: avoid chain re-validation if possible

In the Linux kernel, the following vulnerability has been resolved:

netfilter: nf_tables: avoid chain re-validation if possible

Hamza Mahfooz reports cpu soft lock-ups in

nft_chain_validate():

watchdog: BUG: soft lockup - CPU#1 stuck for 27s! [iptables-nft-re:37547]

[..]

RIP: 0010:nft_chain_validate+0xcb/0x110 [nf_tables]

[..]

nft_immediate_validate+0x36/0x50 [nf_tables]

nft_chain_validate+0xc9/0x110 [nf_tables]

nft_immediate_validate+0x36/0x50 [nf_tables]

nft_chain_validate+0xc9/0x110 [nf_tables]

nft_immediate_validate+0x36/0x50 [nf_tables]

nft_chain_validate+0xc9/0x110 [nf_tables]

nft_immediate_validate+0x36/0x50 [nf_tables]

nft_chain_validate+0xc9/0x110 [nf_tables]

nft_immediate_validate+0x36/0x50 [nf_tables]

nft_chain_validate+0xc9/0x110 [nf_tables]

nft_immediate_validate+0x36/0x50 [nf_tables]

nft_chain_validate+0xc9/0x110 [nf_tables]

nft_table_validate+0x6b/0xb0 [nf_tables]

nf_tables_validate+0x8b/0xa0 [nf_tables]

nf_tables_commit+0x1df/0x1eb0 [nf_tables]

[..]

Currently nf_tables will traverse the entire table (chain graph), starting

from the entry points (base chains), exploring all possible paths

(chain jumps). But there are cases where we could avoid revalidation.

Consider:

1 input -> j2 -> j3

2 input -> j2 -> j3

3 input -> j1 -> j2 -> j3

Then the second rule does not need to revalidate j2, and, by extension j3,

because this was already checked during validation of the first rule.

We need to validate it only for rule 3.

This is needed because chain loop detection also ensures we do not exceed

the jump stack: Just because we know that j2 is cycle free, its last jump

might now exceed the allowed stack size. We also need to update all

reachable chains with the new largest observed call depth.

Care has to be taken to revalidate even if the chain depth won't be an

issue: chain validation also ensures that expressions are not called from

invalid base chains. For example, the masquerade expression can only be

called from NAT postrouting base chains.

Therefore we also need to keep record of the base chain context (type,

hooknum) and revalidate if the chain becomes reachable from a different

hook location.