xfrm: policy: add inexact policy search tree
Subsystems (4)
cover xfrm: policy: add inexact policy search tree
This series attempts to improve xfrm policy lookup performance when a lot of (several hundred or even thousands) inexact policies exist on a system.
On insert, a policy is either placed in hash table (all direct (/32 for ipv4, /128 policies, or all policies matching a user-configured threshold). All other policies get inserted into inexact list as per priority.
Lookup then scans inexact list for first matching entry.
This series instead makes it so that inexact policy is added to exactly one of four different search list 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 policies that match the given source/destination network.
The root of the saddr/daddr tree is 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
First we obtain inexact bin by hashing direction, family and other 'must match' criteria.
Next, we search root_d using packets' destination ip address. If we find a matching node, we search that nodes' source address tree using packets src address.
We also search the bins root_s tree using packets source address.
This initial lookup now has created a 'candidate set' consisting of up to four hlist heads to the four search classes.
Each list gets scanned for first matching entry.
Out of those up the one with the highest priority is chosen. In case several policies had same priority, most recent one is used to match old behaviour.
Locking rules:
insert requires net->xfrm.xfrm_policy_lock spinlock held + BH off (no change to current kernel).
Insert/removal of a tree node needs increment of its sequence count.
lookup requires rcu read lock, lookups in a tree need to sample the sequence count of the bin that tree is located in as well and re-try in case it has changed.
Results on my kvm test setup, using 4 netns:
# 1.2 1.1 3.1 3.10 2.1 2.2
# eth1 eth1 veth0 veth0 eth1 eth1 # ns1 ---- ns3 ----- ns4 ---- ns2
ns3 and ns4 are connected via ipsec tunnel.
'Dummy policies' below means that i created 1k non-matching policies in both ns3 and ns4.
20 parallel netperf (mbits, unidirectional TCP_STREAM):
normal:
993.518000 (no dummy policies)
796.32 (with dummy policies)
patched:
991.335 (no dummy policies)
989.684 (with dummy policies)
20 parallel TCP_RR, trans. per second:
normal:
32413.930000 (no dummy policies)
17725.970000 (with dummy policies)
patched:
32314.51 (no dummy policies)
32326.190000 (with dummy policies)
caveats:
1. Won't work unless large part of policies have no common saddr/daddr pairs. Extreme example: adding 10k 0.0.0.0/0 -> 0.0.0.0/0
policies may require search of all policies, just like current kernel.
2. The policy add sequence
a daddr 10.0.0.0/26
b daddr 10.0.0.64/26
c daddr 10.0.0.0/24
When c gets added, search nodes for a and b have to be merged with the new subnet, as it contains both.
This also means that a single policy rule with a small subnet value can cause severe tree degradation and thus longer search lists.
3. Causes (small) performance degradation when setup only has few policies.
4. Policies need an additional hlist, as MIGRATE doesn't consider if_id, but the patchset makes the if_id part of the initial hash lookup. Could be avoided by not considering if_id as part of initial bin lookup, but then increases list length a lot when we have lots of xfrm interfaces.
5. In oder to solve 'two matching candidates have same priority, which takes precedence?' problem I added a number to xfrm_policy struct that maps to its index in the complete inexact list.
This was necessary to make sure same sequence of policy-add commands keeps on returning same lookup result compared to older kernel.
This work doesn't prevent us from re-adding a new flow caching scheme, but so far i found no good solution (all have various DoS or degradation issues).
Comments or questions welcome.
Florian Westphal (11):
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
include/net/netns/xfrm.h | 2 include/net/xfrm.h | 3 net/xfrm/xfrm_policy.c | 1234 ++++++++++++++++++++++++++--- tools/testing/selftests/net/Makefile | 3 tools/testing/selftests/net/xfrm_policy.sh | 276 ++++++ 5 files changed, 1391 insertions(+), 127 deletions(-)
PATCH 1/11 selftests: add xfrm policy test script
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_EXTENDED := in_netns.sh
tools/testing/selftests/net/xfrm_policy.sh new file +276 -0
276 lines not on this page · raw message
Signature · 1 line
2.18.1
PATCH 2/11 xfrm: security: iterate all, not inexact lists
In reply to Florian Westphalcurrently 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.18.1
PATCH 3/11 xfrm: policy: split list insertion into a helper
In reply to Florian Westphal... 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.18.1
PATCH 4/11 xfrm: policy: return NULL when inexact search needed
In reply to Florian Westphalcurrently 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.18.1
PATCH 5/11 xfrm: policy: store inexact policies in an rhashtable
In reply to Florian WestphalSwitch 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.18.1
PATCH 6/11 xfrm: policy: consider if_id when hashing inexact policy
In reply to Florian WestphalThis 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.18.1
PATCH 7/11 xfrm: policy: add inexact policy search tree infrastructure
In reply to Florian WestphalAt 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.18.1
PATCH 8/11 xfrm: policy: store inexact policies in a tree ordered by destination address
In reply to Florian WestphalThis 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.18.1
PATCH 9/11 xfrm: policy: check reinserted policies match their node
In reply to Florian Westphalvalidate 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.18.1
PATCH 10/11 xfrm: policy: store inexact policies in a tree ordered by source address
In reply to Florian WestphalThis 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.18.1
PATCH 11/11 xfrm: policy: add 2nd-level saddr trees for inexact policies
In reply to Florian WestphalThis 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.18.1
From: Florian Westphal <[email protected]>
Date: Wed, 7 Nov 2018 23:00:30 +0100
Quoted 26 lines
This series attempts to improve xfrm policy lookup performance when a lot of (several hundred or even thousands) inexact policies exist on a system.
On insert, a policy is either placed in hash table (all direct (/32 for ipv4, /128 policies, or all policies matching a user-configured threshold). All other policies get inserted into inexact list as per priority.
Lookup then scans inexact list for first matching entry.
This series instead makes it so that inexact policy is added to exactly one of four different search list 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 policies that match the given source/destination network.The root of the saddr/daddr tree is stored in the nodes of the 'daddr' tree.
...
Quoted 1 line
Comments or questions welcome.
This looks really great. Nice work Florian.
Steffen Klassert
maintainerQuoted 27 lines · David Miller
From: Florian Westphal <[email protected]>
Date: Wed, 7 Nov 2018 23:00:30 +0100Quoted 24 lines
This series attempts to improve xfrm policy lookup performance when a lot of (several hundred or even thousands) inexact policies exist on a system.
On insert, a policy is either placed in hash table (all direct (/32 for ipv4, /128 policies, or all policies matching a user-configured threshold). All other policies get inserted into inexact list as per priority.
Lookup then scans inexact list for first matching entry.
This series instead makes it so that inexact policy is added to exactly one of four different search list 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 policies that match the given source/destination network.
Quoted 6 lines
Quoted 2 lines
The root of the saddr/daddr tree is stored in the nodes of the 'daddr' tree.
...
Quoted 1 line
Comments or questions welcome.
Acked-by David S. Miller <[email protected]>
This is now applied to ipsec-next, thanks a lot
for your work Florian!