[XFRM]: Speed up xfrm_policy and xfrm_state walking
Change xfrm_policy and xfrm_state walking algorithm from O(n^2) to O(n).
This is achieved adding the entries to one more list which is used
solely for walking the entries.
This also fixes some races where the dump can have duplicate or missing
entries when the SPD/SADB is modified during an ongoing dump.
Dumping SADB with 20000 entries using "time ip xfrm state" the sys
time dropped from 1.012s to 0.080s.
Signed-off-by: Timo Teras <timo.teras@iki.fi>
Signed-off-by: David S. Miller <davem@davemloft.net>
diff --git a/net/xfrm/xfrm_user.c b/net/xfrm/xfrm_user.c
index f971ca5..f5fd5b3 100644
--- a/net/xfrm/xfrm_user.c
+++ b/net/xfrm/xfrm_user.c
@@ -532,8 +532,6 @@
struct sk_buff *out_skb;
u32 nlmsg_seq;
u16 nlmsg_flags;
- int start_idx;
- int this_idx;
};
static int copy_sec_ctx(struct xfrm_sec_ctx *s, struct sk_buff *skb)
@@ -600,9 +598,6 @@
struct nlmsghdr *nlh;
int err;
- if (sp->this_idx < sp->start_idx)
- goto out;
-
nlh = nlmsg_put(skb, NETLINK_CB(in_skb).pid, sp->nlmsg_seq,
XFRM_MSG_NEWSA, sizeof(*p), sp->nlmsg_flags);
if (nlh == NULL)
@@ -615,8 +610,6 @@
goto nla_put_failure;
nlmsg_end(skb, nlh);
-out:
- sp->this_idx++;
return 0;
nla_put_failure:
@@ -624,18 +617,32 @@
return err;
}
+static int xfrm_dump_sa_done(struct netlink_callback *cb)
+{
+ struct xfrm_state_walk *walk = (struct xfrm_state_walk *) &cb->args[1];
+ xfrm_state_walk_done(walk);
+ return 0;
+}
+
static int xfrm_dump_sa(struct sk_buff *skb, struct netlink_callback *cb)
{
+ struct xfrm_state_walk *walk = (struct xfrm_state_walk *) &cb->args[1];
struct xfrm_dump_info info;
+ BUILD_BUG_ON(sizeof(struct xfrm_state_walk) >
+ sizeof(cb->args) - sizeof(cb->args[0]));
+
info.in_skb = cb->skb;
info.out_skb = skb;
info.nlmsg_seq = cb->nlh->nlmsg_seq;
info.nlmsg_flags = NLM_F_MULTI;
- info.this_idx = 0;
- info.start_idx = cb->args[0];
- (void) xfrm_state_walk(0, dump_one_state, &info);
- cb->args[0] = info.this_idx;
+
+ if (!cb->args[0]) {
+ cb->args[0] = 1;
+ xfrm_state_walk_init(walk, 0);
+ }
+
+ (void) xfrm_state_walk(walk, dump_one_state, &info);
return skb->len;
}
@@ -654,7 +661,6 @@
info.out_skb = skb;
info.nlmsg_seq = seq;
info.nlmsg_flags = 0;
- info.this_idx = info.start_idx = 0;
if (dump_one_state(x, 0, &info)) {
kfree_skb(skb);
@@ -1232,9 +1238,6 @@
struct sk_buff *skb = sp->out_skb;
struct nlmsghdr *nlh;
- if (sp->this_idx < sp->start_idx)
- goto out;
-
nlh = nlmsg_put(skb, NETLINK_CB(in_skb).pid, sp->nlmsg_seq,
XFRM_MSG_NEWPOLICY, sizeof(*p), sp->nlmsg_flags);
if (nlh == NULL)
@@ -1250,8 +1253,6 @@
goto nlmsg_failure;
nlmsg_end(skb, nlh);
-out:
- sp->this_idx++;
return 0;
nlmsg_failure:
@@ -1259,21 +1260,33 @@
return -EMSGSIZE;
}
+static int xfrm_dump_policy_done(struct netlink_callback *cb)
+{
+ struct xfrm_policy_walk *walk = (struct xfrm_policy_walk *) &cb->args[1];
+
+ xfrm_policy_walk_done(walk);
+ return 0;
+}
+
static int xfrm_dump_policy(struct sk_buff *skb, struct netlink_callback *cb)
{
+ struct xfrm_policy_walk *walk = (struct xfrm_policy_walk *) &cb->args[1];
struct xfrm_dump_info info;
+ BUILD_BUG_ON(sizeof(struct xfrm_policy_walk) >
+ sizeof(cb->args) - sizeof(cb->args[0]));
+
info.in_skb = cb->skb;
info.out_skb = skb;
info.nlmsg_seq = cb->nlh->nlmsg_seq;
info.nlmsg_flags = NLM_F_MULTI;
- info.this_idx = 0;
- info.start_idx = cb->args[0];
- (void) xfrm_policy_walk(XFRM_POLICY_TYPE_MAIN, dump_one_policy, &info);
-#ifdef CONFIG_XFRM_SUB_POLICY
- (void) xfrm_policy_walk(XFRM_POLICY_TYPE_SUB, dump_one_policy, &info);
-#endif
- cb->args[0] = info.this_idx;
+
+ if (!cb->args[0]) {
+ cb->args[0] = 1;
+ xfrm_policy_walk_init(walk, XFRM_POLICY_TYPE_ANY);
+ }
+
+ (void) xfrm_policy_walk(walk, dump_one_policy, &info);
return skb->len;
}
@@ -1293,7 +1306,6 @@
info.out_skb = skb;
info.nlmsg_seq = seq;
info.nlmsg_flags = 0;
- info.this_idx = info.start_idx = 0;
if (dump_one_policy(xp, dir, 0, &info) < 0) {
kfree_skb(skb);
@@ -1891,15 +1903,18 @@
static struct xfrm_link {
int (*doit)(struct sk_buff *, struct nlmsghdr *, struct nlattr **);
int (*dump)(struct sk_buff *, struct netlink_callback *);
+ int (*done)(struct netlink_callback *);
} xfrm_dispatch[XFRM_NR_MSGTYPES] = {
[XFRM_MSG_NEWSA - XFRM_MSG_BASE] = { .doit = xfrm_add_sa },
[XFRM_MSG_DELSA - XFRM_MSG_BASE] = { .doit = xfrm_del_sa },
[XFRM_MSG_GETSA - XFRM_MSG_BASE] = { .doit = xfrm_get_sa,
- .dump = xfrm_dump_sa },
+ .dump = xfrm_dump_sa,
+ .done = xfrm_dump_sa_done },
[XFRM_MSG_NEWPOLICY - XFRM_MSG_BASE] = { .doit = xfrm_add_policy },
[XFRM_MSG_DELPOLICY - XFRM_MSG_BASE] = { .doit = xfrm_get_policy },
[XFRM_MSG_GETPOLICY - XFRM_MSG_BASE] = { .doit = xfrm_get_policy,
- .dump = xfrm_dump_policy },
+ .dump = xfrm_dump_policy,
+ .done = xfrm_dump_policy_done },
[XFRM_MSG_ALLOCSPI - XFRM_MSG_BASE] = { .doit = xfrm_alloc_userspi },
[XFRM_MSG_ACQUIRE - XFRM_MSG_BASE] = { .doit = xfrm_add_acquire },
[XFRM_MSG_EXPIRE - XFRM_MSG_BASE] = { .doit = xfrm_add_sa_expire },
@@ -1938,7 +1953,7 @@
if (link->dump == NULL)
return -EINVAL;
- return netlink_dump_start(xfrm_nl, skb, nlh, link->dump, NULL);
+ return netlink_dump_start(xfrm_nl, skb, nlh, link->dump, link->done);
}
err = nlmsg_parse(nlh, xfrm_msg_min[type], attrs, XFRMA_MAX,