| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Tue, 18 Dec 2018 12:59:50 +0100
From: Steffen Klassert <steffen.klassert@...unet.com>
To: David Miller <davem@...emloft.net>
CC: Herbert Xu <herbert@...dor.apana.org.au>,
Steffen Klassert <steffen.klassert@...unet.com>,
<netdev@...r.kernel.org>
Subject: [PATCH 11/17] xfrm: policy: add 2nd-level saddr trees for inexact policies
From: Florian Westphal <fw@...len.de>
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.
Signed-off-by: Florian Westphal <fw@...len.de>
Acked-by: David S. Miller <davem@...emloft.net>
Signed-off-by: Steffen Klassert <steffen.klassert@...unet.com>
---
net/xfrm/xfrm_policy.c | 118 +++++++++++++++++++++++++++++++++++++----
1 file changed, 108 insertions(+), 10 deletions(-)
diff --git a/net/xfrm/xfrm_policy.c b/net/xfrm/xfrm_policy.c
index 38e33326c856..bd80b8a4322f 100644
--- a/net/xfrm/xfrm_policy.c
+++ b/net/xfrm/xfrm_policy.c
@@ -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);
--
2.17.1
Powered by blists - more mailing lists