pull request (net-next): ipsec-next 2018-12-18
Subsystems (4)
Steffen Klassert
maintainer1) Add xfrm policy selftest scripts.
From Florian Westphal.
2) Split inexact policies into four different search list classes and use the rbtree infrastructure to store/lookup the policies. This is to improve the policy lookup performance after the flowcache removal. Patches from Florian Westphal.
3) Various coding style fixes, from Colin Ian King.
4) Fix policy lookup logic after adding the inexact policy search tree infrastructure. From Florian Westphal.
5) Remove a useless remove BUG_ON from xfrm6_dst_ifdown. From Li RongQing.
6) Use the correct policy direction for lookups on hash rebuilding. From Florian Westphal.
Please pull or let me know if there are problems.
Thanks!
The following changes since commit 29e12207174a58ac8cab4914d0a7ce5e6c872646:
sfc: use the new __netdev_tx_sent_queue BQL optimisation (2018-11-08 20:01:29 -0800)
are available in the Git repository at:
git://git.kernel.org/pub/scm/linux/kernel/git/klassert/ipsec-next.git master
for you to fetch changes up to 77990464bb39eb0f5cd41e4f9e3d6411f2883cac:
xfrm: clean an indentation issue, remove a space (2018-12-10 12:30:40 +0100)
----------------------------------------------------------------
Colin Ian King (3):
af_key: fix indentation on declaration statement
xfrm: policy: add missing indentation
xfrm: clean an indentation issue, remove a space
Florian Westphal (13):
selftests: add xfrm policy test script
xfrm: security: iterate all, not inexact lists
xfrm: policy: split list insertion into a helper
xfrm: policy: return NULL when inexact search needed
xfrm: policy: store inexact policies in an rhashtable
xfrm: policy: consider if_id when hashing inexact policy
xfrm: policy: add inexact policy search tree infrastructure
xfrm: policy: store inexact policies in a tree ordered by destination address
xfrm: policy: check reinserted policies match their node
xfrm: policy: store inexact policies in a tree ordered by source address
xfrm: policy: add 2nd-level saddr trees for inexact policies
xfrm: policy: fix netlink/pf_key policy lookups
xfrm: policy: fix policy hash rebuild
Li RongQing (1):
xfrm6: remove BUG_ON from xfrm6_dst_ifdown
include/net/netns/xfrm.h | 2 + include/net/xfrm.h | 5 +- net/ipv6/xfrm6_policy.c | 1 - net/key/af_key.c | 2 +- net/xfrm/xfrm_policy.c | 1248 +++++++++++++++++++++++++--- tools/testing/selftests/net/Makefile | 3 +- tools/testing/selftests/net/xfrm_policy.sh | 302 +++++++ 7 files changed, 1428 insertions(+), 135 deletions(-) create mode 100755 tools/testing/selftests/net/xfrm_policy.sh
Steffen Klassert
maintainerPATCH 1/17 selftests: add xfrm policy test script
From: Florian Westphal <[email protected]>
add a script that adds a ipsec tunnel between two network namespaces plus following policies:
.0/24 -> ipsec tunnel
.240/28 -> bypass
.253/32 -> ipsec tunnel
Then check that .254 bypasses tunnel (match /28 exception), and .2 (match /24) and .253 (match direct policy) pass through the tunnel.
Abuses iptables to check if ping did resolve an ipsec policy or not.
Also adds a bunch of 'block' rules that are not supposed to match.
--- tools/testing/selftests/net/Makefile | 3 +- tools/testing/selftests/net/xfrm_policy.sh | 276 +++++++++++++++++++++ 2 files changed, 278 insertions(+), 1 deletion(-) create mode 100755 tools/testing/selftests/net/xfrm_policy.sh
tools/testing/selftests/net/Makefile +2 -1
@@ -4,7 +4,8 @@ CFLAGS = -Wall -Wl,--no-as-needed -O2 -g CFLAGS += -I../../../../usr/include/ -TEST_PROGS := run_netsocktests run_afpackettests test_bpf.sh netdevice.sh rtnetlink.sh +TEST_PROGS := run_netsocktests run_afpackettests test_bpf.sh netdevice.sh \ + rtnetlink.sh xfrm_policy.sh TEST_PROGS += fib_tests.sh fib-onlink-tests.sh pmtu.sh udpgso.sh ip_defrag.sh TEST_PROGS += udpgso_bench.sh fib_rule_tests.sh msg_zerocopy.sh psock_snd.sh TEST_PROGS += udpgro_bench.sh udpgro.sh
tools/testing/selftests/net/xfrm_policy.sh new file +276 -0
276 lines not on this page · raw message
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 2/17 xfrm: security: iterate all, not inexact lists
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
currently all non-socket policies are either hashed in the dst table, or placed on the 'inexact list'. When flushing, we first walk the table, then the (per-direction) inexact lists.
When we try and get rid of the inexact lists to having "n" inexact lists (e.g. per-af inexact lists, or sorted into a tree), this walk would become more complicated.
Simplify this: walk the 'all' list and skip socket policies during traversal so we don't need to handle exact and inexact policies separately anymore.
--- net/xfrm/xfrm_policy.c | 93 ++++++++++++------------------------------ 1 file changed, 26 insertions(+), 67 deletions(-)
net/xfrm/xfrm_policy.c +26 -67
@@ -892,36 +892,19 @@ EXPORT_SYMBOL(xfrm_policy_byid);static inline int xfrm_policy_flush_secctx_check (struct net *net,u8 type,bool task_valid) { -int dir, err =0 ; +struct xfrm_policy *pol; +int err =0 ; -for (dir =0 ; dir <XFRM_POLICY_MAX ; dir++) { -struct xfrm_policy *pol; -int i; +list_for_each_entry (pol, &net->xfrm.policy_all, walk.all) { +if (pol->walk.dead || +xfrm_policy_id2dir (pol->index) >=XFRM_POLICY_MAX || + pol->type != type) +continue ; -hlist_for_each_entry (pol, - &net->xfrm.policy_inexact[dir], bydst) { -if (pol->type != type) -continue ; - err =security_xfrm_policy_delete (pol->security); -if (err) { -xfrm_audit_policy_delete (pol,0 , task_valid); -return err; - } - } -for (i = net->xfrm.policy_bydst[dir].hmask; i >=0 ; i--) { -hlist_for_each_entry (pol, - net->xfrm.policy_bydst[dir].table + i, - bydst) { -if (pol->type != type) -continue ; - err =security_xfrm_policy_delete ( - pol->security); -if (err) { -xfrm_audit_policy_delete (pol,0 , - task_valid); -return err; - } - } + err =security_xfrm_policy_delete (pol->security); +if (err) { +xfrm_audit_policy_delete (pol,0 , task_valid); +return err; } }return err;
@@ -937,6 +920,7 @@ xfrm_policy_flush_secctx_check(struct net *net, u8 type, bool task_valid)int xfrm_policy_flush (struct net *net,u8 type,bool task_valid) {int dir, err =0 , cnt =0 ; +struct xfrm_policy *pol;spin_lock_bh (&net->xfrm.xfrm_policy_lock);
@@ -944,46 +928,21 @@ int xfrm_policy_flush(struct net *net, u8 type, bool task_valid)if (err) goto out; -for (dir =0 ; dir <XFRM_POLICY_MAX ; dir++) { -struct xfrm_policy *pol; -int i; - - again1: -hlist_for_each_entry (pol, - &net->xfrm.policy_inexact[dir], bydst) { -if (pol->type != type) -continue ; -__xfrm_policy_unlink (pol, dir); -spin_unlock_bh (&net->xfrm.xfrm_policy_lock); - cnt++; - -xfrm_audit_policy_delete (pol,1 , task_valid); - -xfrm_policy_kill (pol); - -spin_lock_bh (&net->xfrm.xfrm_policy_lock); - goto again1; - } - -for (i = net->xfrm.policy_bydst[dir].hmask; i >=0 ; i--) { - again2: -hlist_for_each_entry (pol, - net->xfrm.policy_bydst[dir].table + i, - bydst) { -if (pol->type != type) -continue ; -__xfrm_policy_unlink (pol, dir); -spin_unlock_bh (&net->xfrm.xfrm_policy_lock); - cnt++; - -xfrm_audit_policy_delete (pol,1 , task_valid); -xfrm_policy_kill (pol); - -spin_lock_bh (&net->xfrm.xfrm_policy_lock); - goto again2; - } - } +again: +list_for_each_entry (pol, &net->xfrm.policy_all, walk.all) { + dir =xfrm_policy_id2dir (pol->index); +if (pol->walk.dead || + dir >=XFRM_POLICY_MAX || + pol->type != type) +continue ; +__xfrm_policy_unlink (pol, dir); +spin_unlock_bh (&net->xfrm.xfrm_policy_lock); + cnt++; +xfrm_audit_policy_delete (pol,1 , task_valid); +xfrm_policy_kill (pol); +spin_lock_bh (&net->xfrm.xfrm_policy_lock); + goto again; }if (!cnt) err = -ESRCH ;
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 3/17 xfrm: policy: split list insertion into a helper
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
... so we can reuse this later without code duplication when we add policy to a second inexact list.
--- net/xfrm/xfrm_policy.c | 43 ++++++++++++++++++++++++++---------------- 1 file changed, 27 insertions(+), 16 deletions(-)
net/xfrm/xfrm_policy.c +27 -16
@@ -740,18 +740,12 @@ static bool xfrm_policy_mark_match(struct xfrm_policy *policy,return false; } -int xfrm_policy_insert (int dir,struct xfrm_policy *policy,int excl) +static struct xfrm_policy *xfrm_policy_insert_list (struct hlist_head *chain, +struct xfrm_policy *policy, +bool excl) { -struct net *net =xp_net (policy); -struct xfrm_policy *pol; -struct xfrm_policy *delpol; -struct hlist_head *chain; -struct hlist_node *newpos; +struct xfrm_policy *pol, *newpos =NULL , *delpol =NULL ; -spin_lock_bh (&net->xfrm.xfrm_policy_lock); - chain =policy_hash_bysel (net, &policy->selector, policy->family, dir); - delpol =NULL ; - newpos =NULL ;hlist_for_each_entry (pol, chain, bydst) { if (pol->type == policy->type && pol->if_id == policy->if_id &&
@@ -759,24 +753,41 @@ int xfrm_policy_insert(int dir, struct xfrm_policy *policy, int excl) xfrm_policy_mark_match(policy, pol) && xfrm_sec_ctx_match(pol->security, policy->security) && !WARN_ON(delpol)) { -if (excl) { -spin_unlock_bh (&net->xfrm.xfrm_policy_lock); -return -EEXIST ; - } +if (excl) +return ERR_PTR (-EEXIST ); delpol = pol;if (policy->priority > pol->priority)continue ; } else if (policy->priority >= pol->priority) { - newpos = &pol->bydst; + newpos = pol;continue ; }if (delpol)break ; }if (newpos) -hlist_add_behind_rcu (&policy->bydst, newpos); +hlist_add_behind_rcu (&policy->bydst, &newpos->bydst);else hlist_add_head_rcu (&policy->bydst, chain); + +return delpol; +} + +int xfrm_policy_insert (int dir,struct xfrm_policy *policy,int excl) +{ +struct net *net =xp_net (policy); +struct xfrm_policy *delpol; +struct hlist_head *chain; + +spin_lock_bh (&net->xfrm.xfrm_policy_lock); + chain =policy_hash_bysel (net, &policy->selector, policy->family, dir); + delpol =xfrm_policy_insert_list (chain, policy, excl); + +if (IS_ERR (delpol)) { +spin_unlock_bh (&net->xfrm.xfrm_policy_lock); +return PTR_ERR (delpol); + } +__xfrm_policy_link (policy, dir);/* After previous checking, family can either be AF_INET or AF_INET6 */
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 4/17 xfrm: policy: return NULL when inexact search needed
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
currently policy_hash_bysel() returns the hash bucket list (for exact policies), or the inexact list (when policy uses a prefix).
Searching this inexact list is slow, so it might be better to pre-sort inexact lists into a tree or another data structure for faster searching.
However, due to 'any' policies, that need to be searched in any case, doing so will require that 'inexact' policies need to be handled specially to decide the best search strategy. So change hash_bysel() and return NULL if the policy can't be handled via the policy hash table.
Right now, we simply use the inexact list when this happens, but future patch can then implement a different strategy.
--- net/xfrm/xfrm_policy.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-)
net/xfrm/xfrm_policy.c +11 -2
@@ -365,7 +365,7 @@ static struct hlist_head *policy_hash_bysel(struct net *net, hash =__sel_hash (sel, family, hmask, dbits, sbits);if (hash == hmask +1 ) -return &net->xfrm.policy_inexact[dir]; +return NULL ;return rcu_dereference_check (net->xfrm.policy_bydst[dir].table,lockdep_is_held (&net->xfrm.xfrm_policy_lock)) + hash;
@@ -625,6 +625,8 @@ static void xfrm_hash_rebuild(struct work_struct *work) chain =policy_hash_bysel (net, &policy->selector, policy->family,xfrm_policy_id2dir (policy->index)); +if (!chain) + chain = &net->xfrm.policy_inexact[dir];hlist_for_each_entry (pol, chain, bydst) {if (policy->priority >= pol->priority) newpos = &pol->bydst;
@@ -781,7 +783,12 @@ int xfrm_policy_insert(int dir, struct xfrm_policy *policy, int excl)spin_lock_bh (&net->xfrm.xfrm_policy_lock); chain =policy_hash_bysel (net, &policy->selector, policy->family, dir); - delpol =xfrm_policy_insert_list (chain, policy, excl); +if (chain) { + delpol =xfrm_policy_insert_list (chain, policy, excl); + }else { + chain = &net->xfrm.policy_inexact[dir]; + delpol =xfrm_policy_insert_list (chain, policy, excl); + }if (IS_ERR (delpol)) {spin_unlock_bh (&net->xfrm.xfrm_policy_lock);
@@ -829,6 +836,8 @@ struct xfrm_policy *xfrm_policy_bysel_ctx(struct net *net, u32 mark, u32 if_id, *err =0 ;spin_lock_bh (&net->xfrm.xfrm_policy_lock); chain =policy_hash_bysel (net, sel, sel->family, dir); +if (!chain) + chain = &net->xfrm.policy_inexact[dir]; ret =NULL ;hlist_for_each_entry (pol, chain, bydst) { if (pol->type == type &&
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 5/17 xfrm: policy: store inexact policies in an rhashtable
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
Switch packet-path lookups for inexact policies to rhashtable.
In this initial version, we now no longer need to search policies with non-matching address family and type.
Next patch will add the if_id as well so lookups from the xfrm interface driver only need to search inexact policies for that device.
Future patches will augment the hlist in each rhash bucket with a tree and pre-sort policies according to daddr/prefix.
A single rhashtable is used. In order to avoid a full rhashtable walk on netns exit, the bins get placed on a pernet list, i.e. we add almost no cost for network namespaces that had no xfrm policies.
The inexact lists are kept in place, and policies are added to both the per-rhash-inexact list and a pernet one.
The latter is needed for the control plane to handle migrate -- these requests do not consider the if_id, so if we'd remove the inexact_list now we would have to search all hash buckets and then figure out which matching policy candidate is the most recent one -- this appears a bit harder than just keeping the 'old' inexact list for this purpose.
--- include/net/netns/xfrm.h | 2 + include/net/xfrm.h | 1 + net/xfrm/xfrm_policy.c | 350 +++++++++++++++++++++++++++++++++++++-- 3 files changed, 335 insertions(+), 18 deletions(-)
include/net/netns/xfrm.h +2 -0
@@ -5,6 +5,7 @@#include <linux/list.h> #include <linux/wait.h> #include <linux/workqueue.h> +#include <linux/rhashtable-types.h> #include <linux/xfrm.h> #include <net/dst_ops.h>
@@ -53,6 +54,7 @@ struct netns_xfrm {unsigned int policy_count[XFRM_POLICY_MAX *2 ];struct work_struct policy_hash_work;struct xfrm_policy_hthresh policy_hthresh; +struct list_head inexact_bins;struct sock *nlsk;
include/net/xfrm.h +1 -0
@@ -596,6 +596,7 @@ struct xfrm_policy {u16 family;struct xfrm_sec_ctx *security;struct xfrm_tmpl xfrm_vec[XFRM_MAX_DEPTH ]; +struct hlist_node bydst_inexact_list;struct rcu_head rcu; };
net/xfrm/xfrm_policy.c +332 -18
518 lines not on this page · raw message
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 6/17 xfrm: policy: consider if_id when hashing inexact policy
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
This avoids searches of polices that cannot match in the first place due to different interface id by placing them in different bins.
--- net/xfrm/xfrm_policy.c | 25 ++++++++++++++++--------- 1 file changed, 16 insertions(+), 9 deletions(-)
net/xfrm/xfrm_policy.c +16 -9
@@ -48,6 +48,7 @@ struct xfrm_flo {struct xfrm_pol_inexact_key {possible_net_t net; +u32 if_id;u16 family;u8 dir, type; };
@@ -85,11 +86,12 @@ static struct xfrm_policy *__xfrm_policy_unlink(struct xfrm_policy *pol, int dir);static struct xfrm_pol_inexact_bin * -xfrm_policy_inexact_lookup (struct net *net,u8 type,u16 family,u8 dir); +xfrm_policy_inexact_lookup (struct net *net,u8 type,u16 family,u8 dir, +u32 if_id);static struct xfrm_pol_inexact_bin *xfrm_policy_inexact_lookup_rcu (struct net *net, -u8 type,u16 family,u8 dir); +u8 type,u16 family,u8 dir,u32 if_id);static struct xfrm_policy *xfrm_policy_insert_list (struct hlist_head *chain,struct xfrm_policy *policy,bool excl);
@@ -618,6 +620,7 @@ xfrm_policy_inexact_alloc_bin(const struct xfrm_policy *pol, u8 dir) .family = pol->family, .type = pol->type, .dir = dir, + .if_id = pol->if_id, };struct net *net =xp_net (pol);
@@ -925,7 +928,8 @@ static u32 xfrm_pol_bin_key(const void *data, u32 len, u32 seed)const struct xfrm_pol_inexact_key *k = data;u32 a = k->type <<24 | k->dir <<16 | k->family; -return jhash_2words (a,net_hash_mix (read_pnet (&k->net)), seed); +return jhash_3words (a, k->if_id,net_hash_mix (read_pnet (&k->net)), + seed); }static u32 xfrm_pol_bin_obj (const void *data,u32 len,u32 seed)
@@ -957,7 +961,7 @@ static int xfrm_pol_bin_cmp(struct rhashtable_compare_arg *arg,if (ret)return ret; -return 0 ; +return b->k.if_id ^ key->if_id; }static const struct rhashtable_params xfrm_pol_inexact_params = {
@@ -1094,7 +1098,7 @@ struct xfrm_policy *xfrm_policy_bysel_ctx(struct net *net, u32 mark, u32 if_id, chain =policy_hash_bysel (net, sel, sel->family, dir);if (!chain) { bin =xfrm_policy_inexact_lookup (net, type, - sel->family, dir); + sel->family, dir, if_id);if (!bin) {spin_unlock_bh (&net->xfrm.xfrm_policy_lock);return NULL ;
@@ -1335,12 +1339,14 @@ static int xfrm_policy_match(const struct xfrm_policy *pol, }static struct xfrm_pol_inexact_bin * -xfrm_policy_inexact_lookup_rcu (struct net *net,u8 type,u16 family,u8 dir) +xfrm_policy_inexact_lookup_rcu (struct net *net,u8 type,u16 family, +u8 dir,u32 if_id) {struct xfrm_pol_inexact_key k = { .family = family, .type = type, .dir = dir, + .if_id = if_id, };write_pnet (&k.net, net);
@@ -1350,14 +1356,15 @@ xfrm_policy_inexact_lookup_rcu(struct net *net, u8 type, u16 family, u8 dir) }static struct xfrm_pol_inexact_bin * -xfrm_policy_inexact_lookup (struct net *net,u8 type,u16 family,u8 dir) +xfrm_policy_inexact_lookup (struct net *net,u8 type,u16 family, +u8 dir,u32 if_id) {struct xfrm_pol_inexact_bin *bin;lockdep_assert_held (&net->xfrm.xfrm_policy_lock);rcu_read_lock (); - bin =xfrm_policy_inexact_lookup_rcu (net, type, family, dir); + bin =xfrm_policy_inexact_lookup_rcu (net, type, family, dir, if_id);rcu_read_unlock ();return bin;
@@ -1405,7 +1412,7 @@ static struct xfrm_policy *xfrm_policy_lookup_bytype(struct net *net, u8 type,break ; } } - bin =xfrm_policy_inexact_lookup_rcu (net, type, family, dir); + bin =xfrm_policy_inexact_lookup_rcu (net, type, family, dir, if_id);if (!bin) goto skip_inexact; chain = &bin->hhead;
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 7/17 xfrm: policy: add inexact policy search tree infrastructure
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
At this time inexact policies are all searched in-order until the first match is found. After removal of the flow cache, this resolution has to be performed for every packetm resulting in major slowdown when number of inexact policies is high.
This adds infrastructure to later sort inexact policies into a tree. This only introduces a single class: any:any.
Next patch will add a search tree to pre-sort policies that have a fixed daddr/prefixlen, so in this patch the any:any class will still be used for all policies.
--- include/net/xfrm.h | 1 + net/xfrm/xfrm_policy.c | 301 +++++++++++++++++++++++++++++++++-------- 2 files changed, 248 insertions(+), 54 deletions(-)
include/net/xfrm.h +1 -0
@@ -577,6 +577,7 @@ struct xfrm_policy {/* This lock only affects elements except for entry. */ rwlock_t lock;refcount_t refcnt; +u32 pos;struct timer_list timer;atomic_t genid;
net/xfrm/xfrm_policy.c +247 -54
450 lines not on this page · raw message
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 8/17 xfrm: policy: store inexact policies in a tree ordered by destination address
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
This adds inexact lists per destination network, stored in a search tree.
Inexact lookups now return two 'candidate lists', the 'any' policies ('any' destionations), and a list of policies that share same daddr/prefix.
Next patch will add a second search tree for 'saddr:any' policies so we can avoid placing those on the 'any:any' list too.
--- include/net/xfrm.h | 1 + net/xfrm/xfrm_policy.c | 333 ++++++++++++++++++++++++++++++++++++++++- 2 files changed, 328 insertions(+), 6 deletions(-)
include/net/xfrm.h +1 -0
@@ -590,6 +590,7 @@ struct xfrm_policy {struct xfrm_lifetime_cur curlft;struct xfrm_policy_walk_entry walk;struct xfrm_policy_queue polq; +bool bydst_reinsert;u8 type;u8 action;u8 flags;
net/xfrm/xfrm_policy.c +327 -6
402 lines not on this page · raw message
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 9/17 xfrm: policy: check reinserted policies match their node
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
validate the re-inserted policies match the lookup node. Policies that fail this test won't be returned in the candidate set.
This is enabled by default for now, it should not cause noticeable reinsert slow down.
Such reinserts are needed when we have to merge an existing node (e.g. for 10.0.0.0/28 because a overlapping subnet was added (e.g. 10.0.0.0/24), so whenever this happens existing policies have to be placed on the list of the new node.
--- net/xfrm/xfrm_policy.c | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)
net/xfrm/xfrm_policy.c +32 -0
@@ -806,10 +806,16 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net, struct xfrm_pol_inexact_node *n, u16 family) { +unsigned int matched_s, matched_d;struct hlist_node *newpos =NULL ;struct xfrm_policy *policy, *p; + matched_s =0 ; + matched_d =0 ; +list_for_each_entry_reverse (policy, &net->xfrm.policy_all, walk.all) { +bool matches_s, matches_d; +if (!policy->bydst_reinsert)continue ;
@@ -827,6 +833,32 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net,hlist_add_behind (&policy->bydst, newpos); else hlist_add_head(&policy->bydst, &n->hhead); + +/* paranoia checks follow. +* Check that the reinserted policy matches at least +* saddr or daddr for current node prefix. +* +* Matching both is fine, matching saddr in one policy +* (but not daddr) and then matching only daddr in another +* is a bug. +*/ + matches_s =xfrm_policy_addr_delta (&policy->selector.saddr, + &n->addr, + n->prefixlen, + family) ==0 ; + matches_d =xfrm_policy_addr_delta (&policy->selector.daddr, + &n->addr, + n->prefixlen, + family) ==0 ; +if (matches_s && matches_d) +continue ; + +WARN_ON_ONCE (!matches_s && !matches_d); +if (matches_s) + matched_s++; +if (matches_d) + matched_d++; +WARN_ON_ONCE (matched_s && matched_d); } }
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 10/17 xfrm: policy: store inexact policies in a tree ordered by source address
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
This adds the 'saddr:any' search class. It contains all policies that have a fixed saddr/prefixlen, but 'any' destination.
--- net/xfrm/xfrm_policy.c | 46 ++++++++++++++++++++++++++++++++++++++---- 1 file changed, 42 insertions(+), 4 deletions(-)
net/xfrm/xfrm_policy.c +42 -4
@@ -71,11 +71,20 @@ struct xfrm_pol_inexact_node {* | | * | +- coarse policies and all any:daddr policies * | +* +---- root_s: sorted by saddr:prefix +* | | +* | xfrm_pol_inexact_node +* | | +* | + root: unused +* | | +* | + hhead: saddr:any policies +* | * +---- coarse policies and all any:any policies * -* Lookups return two candidate lists: +* Lookups return three candidate lists: * 1. any:any list from top-level xfrm_pol_inexact_bin * 2. any:daddr list from daddr tree +* 2. saddr:any list from saddr tree * * This result set then needs to be searched for the policy with * the lowest priority. If two results have same prio, youngest one wins.
@@ -98,12 +107,16 @@ struct xfrm_pol_inexact_bin {/* tree sorted by daddr/prefix */ struct rb_root root_d; +/* tree sorted by saddr/prefix */ +struct rb_root root_s; +/* slow path below */ struct list_head inexact_bins;struct rcu_head rcu; };enum xfrm_pol_inexact_candidate_type { +XFRM_POL_CAND_SADDR ,XFRM_POL_CAND_DADDR ,XFRM_POL_CAND_ANY ,
@@ -696,6 +709,7 @@ xfrm_policy_inexact_alloc_bin(const struct xfrm_policy *pol, u8 dir) bin->k = k;INIT_HLIST_HEAD (&bin->hhead); bin->root_d =RB_ROOT ; + bin->root_s =RB_ROOT ;seqcount_init (&bin->count); prev = rhashtable_lookup_get_insert_key(&xfrm_policy_inexact_table,
@@ -980,9 +994,10 @@ static void __xfrm_policy_inexact_prune_bin(struct xfrm_pol_inexact_bin *b, bool {write_seqcount_begin (&b->count);xfrm_policy_inexact_gc_tree (&b->root_d, net_exit); +xfrm_policy_inexact_gc_tree (&b->root_s, net_exit);write_seqcount_end (&b->count); -if (!RB_EMPTY_ROOT (&b->root_d) || +if (!RB_EMPTY_ROOT (&b->root_d) || !RB_EMPTY_ROOT (&b->root_s) || !hlist_empty (&b->hhead)) {WARN_ON_ONCE (net_exit);return ;
@@ -1027,11 +1042,29 @@ xfrm_policy_inexact_alloc_chain(struct xfrm_pol_inexact_bin *bin,if (xfrm_policy_inexact_insert_use_any_list (policy))return &bin->hhead; -if (xfrm_pol_inexact_addr_use_any_list (&policy->selector.daddr, +/* saddr is wildcard */ +if (xfrm_pol_inexact_addr_use_any_list (&policy->selector.saddr, policy->family, - policy->selector.prefixlen_d)) + policy->selector.prefixlen_s))return &bin->hhead; +if (xfrm_pol_inexact_addr_use_any_list (&policy->selector.daddr, + policy->family, + policy->selector.prefixlen_d)) { +write_seqcount_begin (&bin->count); + n =xfrm_policy_inexact_insert_node (net, + &bin->root_s, + &policy->selector.saddr, + policy->family, + policy->selector.prefixlen_s, + dir); +write_seqcount_end (&bin->count); +if (!n) +return NULL ; + +return &n->hhead; + } +/* daddr is fixed */ write_seqcount_begin (&bin->count); n = xfrm_policy_inexact_insert_node(net,
@@ -1826,6 +1859,11 @@ xfrm_policy_find_inexact_candidates(struct xfrm_pol_inexact_candidates *cand,if (n) cand->res[XFRM_POL_CAND_DADDR ] = &n->hhead; + n =xfrm_policy_lookup_inexact_addr (&b->root_s, &b->count, saddr, + family); +if (n) + cand->res[XFRM_POL_CAND_SADDR ] = &n->hhead; +return true; }
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 11/17 xfrm: policy: add 2nd-level saddr trees for inexact policies
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
This adds the fourth and final search class, containing policies where both saddr and daddr have prefix lengths (i.e., not wildcards).
Inexact policies now end up in one of the following four search classes:
1. "Any:Any" list, containing policies where both saddr and daddr are wildcards or have very coarse prefixes, e.g. 10.0.0.0/8 and the like.
2. "saddr:any" list, containing policies with a fixed saddr/prefixlen, but without destination restrictions.
These lists are stored in rbtree nodes; each node contains those policies matching saddr/prefixlen.
3. "Any:daddr" list. Similar to 2), except for policies where only the destinations are specified.
4. "saddr:daddr" lists, containing only those policies that match the given source/destination network.
The root of the saddr/daddr nodes gets stored in the nodes of the 'daddr' tree.
This diagram illustrates the list classes, and their placement in the lookup hierarchy:
xfrm_pol_inexact_bin = hash(dir,type,family,if_id);
|
+---- root_d: sorted by daddr:prefix
| |
| xfrm_pol_inexact_node
| |
| +- root: sorted by saddr/prefix
| | |
| | xfrm_pol_inexact_node
| | |
| | + root: unused
| | |
| | + hhead: saddr:daddr policies
| |
| +- coarse policies and all any:daddr policies
|
+---- root_s: sorted by saddr:prefix
| |
| xfrm_pol_inexact_node
| |
| + root: unused
| |
| + hhead: saddr:any policies
|
+---- coarse policies and all any:any policies
lookup for an inexact policy returns pointers to the four relevant list classes, after which each of the lists needs to be searched for the policy with the higher priority.
This will only speed up lookups in case we have many policies and a sizeable portion of these have disjunct saddr/daddr addresses.
--- net/xfrm/xfrm_policy.c | 118 +++++++++++++++++++++++++++++++++++++---- 1 file changed, 108 insertions(+), 10 deletions(-)
net/xfrm/xfrm_policy.c +108 -10
@@ -58,6 +58,8 @@ struct xfrm_pol_inexact_node { };u8 prefixlen; +struct rb_root root; +/* the policies matching this node, can be empty list */ struct hlist_head hhead; };
@@ -69,6 +71,14 @@ struct xfrm_pol_inexact_node {* | | * | xfrm_pol_inexact_node * | | +* | +- root: sorted by saddr/prefix +* | | | +* | | xfrm_pol_inexact_node +* | | | +* | | + root: unused +* | | | +* | | + hhead: saddr:daddr policies +* | | * | +- coarse policies and all any:daddr policies * | * +---- root_s: sorted by saddr:prefix
@@ -81,10 +91,11 @@ struct xfrm_pol_inexact_node {* | * +---- coarse policies and all any:any policies * -* Lookups return three candidate lists: +* Lookups return four candidate lists: * 1. any:any list from top-level xfrm_pol_inexact_bin * 2. any:daddr list from daddr tree -* 2. saddr:any list from saddr tree +* 3. saddr:daddr list from 2nd level daddr tree +* 4. saddr:any list from saddr tree * * This result set then needs to be searched for the policy with * the lowest priority. If two results have same prio, youngest one wins.
@@ -116,6 +127,7 @@ struct xfrm_pol_inexact_bin { };enum xfrm_pol_inexact_candidate_type { +XFRM_POL_CAND_BOTH ,XFRM_POL_CAND_SADDR ,XFRM_POL_CAND_DADDR ,XFRM_POL_CAND_ANY ,
@@ -876,13 +888,82 @@ static void xfrm_policy_inexact_list_reinsert(struct net *net, } } +static void xfrm_policy_inexact_node_reinsert (struct net *net, +struct xfrm_pol_inexact_node *n, +struct rb_root *new, +u16 family) +{ +struct rb_node **p, *parent =NULL ; +struct xfrm_pol_inexact_node *node; + +/* we should not have another subtree here */ +WARN_ON_ONCE (!RB_EMPTY_ROOT (&n->root)); + + p = &new->rb_node; +while (*p) { +u8 prefixlen; +int delta; + + parent = *p; + node = rb_entry(*p, struct xfrm_pol_inexact_node, node); + + prefixlen =min (node->prefixlen, n->prefixlen); + + delta =xfrm_policy_addr_delta (&n->addr, &node->addr, + prefixlen, family); +if (delta <0 ) { + p = &parent->rb_left; + }else if (delta >0 ) { + p = &parent->rb_right; + }else { +struct xfrm_policy *tmp; + +hlist_for_each_entry (tmp, &node->hhead, bydst) + tmp->bydst_reinsert = true; +hlist_for_each_entry (tmp, &n->hhead, bydst) + tmp->bydst_reinsert = true; + +INIT_HLIST_HEAD (&node->hhead); +xfrm_policy_inexact_list_reinsert (net, node, family); + +if (node->prefixlen == n->prefixlen) { +kfree_rcu (n, rcu); +return ; + } + +rb_erase (*p, new); +kfree_rcu (n, rcu); + n = node; + n->prefixlen = prefixlen; + *p = new->rb_node; + parent =NULL ; + } + } + +rb_link_node_rcu (&n->node, parent, p); +rb_insert_color (&n->node, new); +} +/* merge nodes v and n */ static void xfrm_policy_inexact_node_merge (struct net *net,struct xfrm_pol_inexact_node *v,struct xfrm_pol_inexact_node *n,u16 family) { +struct xfrm_pol_inexact_node *node;struct xfrm_policy *tmp; +struct rb_node *rnode; + +/* To-be-merged node v has a subtree. +* +* Dismantle it and insert its nodes to n->root. +*/ +while ((rnode =rb_first (&v->root)) !=NULL ) { + node = rb_entry(rnode, struct xfrm_pol_inexact_node, node); +rb_erase (&node->node, &v->root); +xfrm_policy_inexact_node_reinsert (net, node, &n->root, + family); + }hlist_for_each_entry (tmp, &v->hhead, bydst) tmp->bydst_reinsert = true;
@@ -978,9 +1059,10 @@ static void xfrm_policy_inexact_gc_tree(struct rb_root *r, bool rm)while (rn) { node = rb_entry(rn, struct xfrm_pol_inexact_node, node); +xfrm_policy_inexact_gc_tree (&node->root, rm); rn =rb_next (rn); -if (!hlist_empty (&node->hhead)) { +if (!hlist_empty (&node->hhead) || !RB_EMPTY_ROOT (&node->root)) {WARN_ON_ONCE (rm);continue ; }
@@ -1042,12 +1124,6 @@ xfrm_policy_inexact_alloc_chain(struct xfrm_pol_inexact_bin *bin,if (xfrm_policy_inexact_insert_use_any_list (policy))return &bin->hhead; -/* saddr is wildcard */ -if (xfrm_pol_inexact_addr_use_any_list (&policy->selector.saddr, - policy->family, - policy->selector.prefixlen_s)) -return &bin->hhead; -if (xfrm_pol_inexact_addr_use_any_list (&policy->selector.daddr, policy->family, policy->selector.prefixlen_d)) {
@@ -1075,6 +1151,23 @@ xfrm_policy_inexact_alloc_chain(struct xfrm_pol_inexact_bin *bin,write_seqcount_end (&bin->count);if (!n)return NULL ; + +/* saddr is wildcard */ +if (xfrm_pol_inexact_addr_use_any_list (&policy->selector.saddr, + policy->family, + policy->selector.prefixlen_s)) +return &n->hhead; + +write_seqcount_begin (&bin->count); + n =xfrm_policy_inexact_insert_node (net, + &n->root, + &policy->selector.saddr, + policy->family, + policy->selector.prefixlen_s, dir); +write_seqcount_end (&bin->count); +if (!n) +return NULL ; +return &n->hhead; }
@@ -1856,8 +1949,13 @@ xfrm_policy_find_inexact_candidates(struct xfrm_pol_inexact_candidates *cand, n =xfrm_policy_lookup_inexact_addr (&b->root_d, &b->count, daddr, family); -if (n) +if (n) { cand->res[XFRM_POL_CAND_DADDR ] = &n->hhead; + n =xfrm_policy_lookup_inexact_addr (&n->root, &b->count, saddr, + family); +if (n) + cand->res[XFRM_POL_CAND_BOTH ] = &n->hhead; + } n =xfrm_policy_lookup_inexact_addr (&b->root_s, &b->count, saddr, family);
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 12/17 af_key: fix indentation on declaration statement
In reply to Steffen KlassertFrom: Colin Ian King <[email protected]>
There is an indentation issue before the declaration of xfrm_ctx. Remove spaces and replace with a tab.
--- net/key/af_key.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/key/af_key.c +1 -1
@@ -2020,7 +2020,7 @@ parse_ipsecrequests(struct xfrm_policy *xp, struct sadb_x_policy *pol)static inline int pfkey_xfrm_policy2sec_ctx_size (const struct xfrm_policy *xp) { -struct xfrm_sec_ctx *xfrm_ctx = xp->security; +struct xfrm_sec_ctx *xfrm_ctx = xp->security;if (xfrm_ctx) {int len =sizeof (struct sadb_x_sec_ctx );
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 13/17 xfrm: policy: add missing indentation
In reply to Steffen KlassertFrom: Colin Ian King <[email protected]>
There is a missing indentation before the goto statement. Add it.
--- net/xfrm/xfrm_policy.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/xfrm/xfrm_policy.c +1 -1
@@ -2782,7 +2782,7 @@ static void xfrm_policy_queue_process(struct timer_list *t) pq->timeout = pq->timeout <<1 ;if (!mod_timer (&pq->hold_timer, jiffies + pq->timeout))xfrm_pol_hold (pol); - goto out; + goto out; }dst_release (dst);
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 14/17 xfrm: policy: fix netlink/pf_key policy lookups
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
Colin Ian King says:
Static analysis with CoverityScan found a potential issue [..] It seems that pointer pol is set to NULL and then a check to see if it is non-null is used to set pol to tmp; howeverm this check is always going to be false because pol is always NULL.
Fix this and update test script to catch this. Updated script only:
./xfrm_policy.sh ; echo $?
RTNETLINK answers: No such file or directory
FAIL: ip -net ns3 xfrm policy get src 10.0.1.0/24 dst 10.0.2.0/24 dir out RTNETLINK answers: No such file or directory
[..]
PASS: policy before exception matches
PASS: ping to .254 bypassed ipsec tunnel
PASS: direct policy matches
PASS: policy matches
1
--- net/xfrm/xfrm_policy.c | 5 ++- tools/testing/selftests/net/xfrm_policy.sh | 38 ++++++++++++++++++---- 2 files changed, 36 insertions(+), 7 deletions(-)
net/xfrm/xfrm_policy.c +4 -1
@@ -1663,7 +1663,10 @@ struct xfrm_policy *xfrm_policy_bysel_ctx(struct net *net, u32 mark, u32 if_id, tmp =__xfrm_policy_bysel_ctx (cand.res[i], mark, if_id, type, dir, sel, ctx); -if (tmp && pol && tmp->pos < pol->pos) +if (!tmp) +continue ; + +if (!pol || tmp->pos < pol->pos) pol = tmp; } }else {
tools/testing/selftests/net/xfrm_policy.sh +32 -6
@@ -21,6 +21,7 @@ # Kselftest framework requirement - SKIP code is 4. ksft_skip=4 ret=0 +policy_checks_ok=1 KEY_SHA=0xdeadbeef1234567890abcdefabcdefabcdefabcd KEY_AES=0x0123456789abcdef0123456789012345
@@ -45,6 +46,26 @@ do_esp() { ip -net $ns xfrm policy add src $rnet dst $lnet dir fwd tmpl src $remote dst $me proto esp mode tunnel priority 100 action allow } +do_esp_policy_get_check() { + local ns=$1 + local lnet=$2 + local rnet=$3 + + ip -net $ns xfrm policy get src $lnet dst $rnet dir out > /dev/null + if [ $? -ne 0 ] && [ $policy_checks_ok -eq 1 ] ;then + policy_checks_ok=0 + echo "FAIL: ip -net $ns xfrm policy get src $lnet dst $rnet dir out" + ret=1 + fi + + ip -net $ns xfrm policy get src $rnet dst $lnet dir fwd > /dev/null + if [ $? -ne 0 ] && [ $policy_checks_ok -eq 1 ] ;then + policy_checks_ok=0 + echo "FAIL: ip -net $ns xfrm policy get src $rnet dst $lnet dir fwd" + ret=1 + fi +} + do_exception() { local ns=$1 local me=$2
@@ -112,31 +133,31 @@ check_xfrm() { # 1: iptables -m policy rule count != 0 rval=$1 ip=$2 - ret=0 + lret=0 ip netns exec ns1 ping -q -c 1 10.0.2.$ip > /dev/null check_ipt_policy_count ns3 if [ $? -ne $rval ] ; then - ret=1 + lret=1 fi check_ipt_policy_count ns4 if [ $? -ne $rval ] ; then - ret=1 + lret=1 fi ip netns exec ns2 ping -q -c 1 10.0.1.$ip > /dev/null check_ipt_policy_count ns3 if [ $? -ne $rval ] ; then - ret=1 + lret=1 fi check_ipt_policy_count ns4 if [ $? -ne $rval ] ; then - ret=1 + lret=1 fi - return $ret + return $lret } #check for needed privileges
@@ -227,6 +248,11 @@ do_esp ns4 dead:3::10 dead:3::1 dead:2::/64 dead:1::/64 $SPI2 $SPI1 do_dummies4 ns3 do_dummies6 ns4 +do_esp_policy_get_check ns3 10.0.1.0/24 10.0.2.0/24 +do_esp_policy_get_check ns4 10.0.2.0/24 10.0.1.0/24 +do_esp_policy_get_check ns3 dead:1::/64 dead:2::/64 +do_esp_policy_get_check ns4 dead:2::/64 dead:1::/64 + # ping to .254 should use ipsec, exception is not installed. check_xfrm 1 254 if [ $? -ne 0 ]; then
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 15/17 xfrm6: remove BUG_ON from xfrm6_dst_ifdown
In reply to Steffen KlassertFrom: Li RongQing <[email protected]>
if loopback_idev is NULL pointer, and the following access of loopback_idev will trigger panic, which is same as BUG_ON
--- net/ipv6/xfrm6_policy.c | 1 - 1 file changed, 1 deletion(-)
net/ipv6/xfrm6_policy.c +0 -1
@@ -262,7 +262,6 @@ static void xfrm6_dst_ifdown(struct dst_entry *dst, struct net_device *dev,if (xdst->u.rt6.rt6i_idev->dev == dev) {struct inet6_dev *loopback_idev =in6_dev_get (dev_net (dev)->loopback_dev); -BUG_ON (!loopback_idev); do { in6_dev_put(xdst->u.rt6.rt6i_idev);
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 16/17 xfrm: policy: fix policy hash rebuild
In reply to Steffen KlassertFrom: Florian Westphal <[email protected]>
Dan Carpenter reports following static checker warning:
net/xfrm/xfrm_policy.c:1316 xfrm_hash_rebuild()
warn: 'dir' is out of bounds '3' vs '2'
| 1280 /* reset the bydst and inexact table in all directions */
| 1281 xfrm_hash_reset_inexact_table(net);
| 1282
| 1283 for (dir = 0; dir < XFRM_POLICY_MAX; dir++) {
| ^^^^^^^^^^^^^^^^^^^^^
|dir == XFRM_POLICY_MAX at the end of this loop.
| 1304 /* re-insert all policies by order of creation */
| 1305 list_for_each_entry_reverse(policy, &net->xfrm.policy_all, walk.all) {
[..]
| 1314 xfrm_policy_id2dir(policy->index));
| 1315 if (!chain) {
| 1316 void *p = xfrm_policy_inexact_insert(policy, dir, 0);Fix this by updating 'dir' based on current policy. Otherwise, the inexact policies won't be found anymore during lookup, as they get hashed to a bogus bin.
--- net/xfrm/xfrm_policy.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)
net/xfrm/xfrm_policy.c +5 -4
@@ -1303,15 +1303,16 @@ static void xfrm_hash_rebuild(struct work_struct *work)/* re-insert all policies by order of creation */ list_for_each_entry_reverse (policy, &net->xfrm.policy_all, walk.all) { -if (policy->walk.dead || -xfrm_policy_id2dir (policy->index) >=XFRM_POLICY_MAX ) { +if (policy->walk.dead) +continue ; + dir =xfrm_policy_id2dir (policy->index); +if (dir >=XFRM_POLICY_MAX ) {/* skip socket policies */ continue ; } newpos =NULL ; chain =policy_hash_bysel (net, &policy->selector, - policy->family, -xfrm_policy_id2dir (policy->index)); + policy->family, dir);if (!chain) {void *p =xfrm_policy_inexact_insert (policy, dir,0 );
Signature · 1 line
2.17.1
Steffen Klassert
maintainerPATCH 17/17 xfrm: clean an indentation issue, remove a space
In reply to Steffen KlassertFrom: Colin Ian King <[email protected]>
Trivial fix to clean up indentation issue, remove an extraneous space.
--- include/net/xfrm.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
include/net/xfrm.h +1 -1
@@ -1970,7 +1970,7 @@ static inline void xfrm_dev_state_delete(struct xfrm_state *x)static inline void xfrm_dev_state_free (struct xfrm_state *x) {struct xfrm_state_offload *xso = &x->xso; -struct net_device *dev = xso->dev; +struct net_device *dev = xso->dev;if (dev && dev->xfrmdev_ops) {if (dev->xfrmdev_ops->xdo_dev_state_free)
Signature · 1 line
2.17.1
David Miller
maintainerFrom: Steffen Klassert <[email protected]>
Date: Tue, 18 Dec 2018 12:59:39 +0100
Quoted 14 lines
1) Add xfrm policy selftest scripts.
From Florian Westphal.2) Split inexact policies into four different search list classes and use the rbtree infrastructure to store/lookup the policies. This is to improve the policy lookup performance after the flowcache removal. Patches from Florian Westphal.
3) Various coding style fixes, from Colin Ian King.
4) Fix policy lookup logic after adding the inexact policy search tree infrastructure. From Florian Westphal.
Quoted 7 lines
5) Remove a useless remove
BUG_ONfromxfrm6_dst_ifdown. From Li RongQing.6) Use the correct policy direction for lookups on hash rebuilding. From Florian Westphal.
Please pull or let me know if there are problems.
Pulled, thanks Steffen.