[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 <[email protected]>
Signed-off-by: David S. Miller <[email protected]>
diff --git a/net/key/af_key.c b/net/key/af_key.c
index 8b5f486..7cb6f12 100644
--- a/net/key/af_key.c
+++ b/net/key/af_key.c
@@ -1742,12 +1742,18 @@
{
u8 proto;
struct pfkey_dump_data data = { .skb = skb, .hdr = hdr, .sk = sk };
+ struct xfrm_state_walk walk;
+ int rc;
proto = pfkey_satype2proto(hdr->sadb_msg_satype);
if (proto == 0)
return -EINVAL;
- return xfrm_state_walk(proto, dump_sa, &data);
+ xfrm_state_walk_init(&walk, proto);
+ rc = xfrm_state_walk(&walk, dump_sa, &data);
+ xfrm_state_walk_done(&walk);
+
+ return rc;
}
static int pfkey_promisc(struct sock *sk, struct sk_buff *skb, struct sadb_msg *hdr, void **ext_hdrs)
@@ -1780,7 +1786,9 @@
static u32 gen_reqid(void)
{
+ struct xfrm_policy_walk walk;
u32 start;
+ int rc;
static u32 reqid = IPSEC_MANUAL_REQID_MAX;
start = reqid;
@@ -1788,8 +1796,10 @@
++reqid;
if (reqid == 0)
reqid = IPSEC_MANUAL_REQID_MAX+1;
- if (xfrm_policy_walk(XFRM_POLICY_TYPE_MAIN, check_reqid,
- (void*)&reqid) != -EEXIST)
+ xfrm_policy_walk_init(&walk, XFRM_POLICY_TYPE_MAIN);
+ rc = xfrm_policy_walk(&walk, check_reqid, (void*)&reqid);
+ xfrm_policy_walk_done(&walk);
+ if (rc != -EEXIST)
return reqid;
} while (reqid != start);
return 0;
@@ -2665,8 +2675,14 @@
static int pfkey_spddump(struct sock *sk, struct sk_buff *skb, struct sadb_msg *hdr, void **ext_hdrs)
{
struct pfkey_dump_data data = { .skb = skb, .hdr = hdr, .sk = sk };
+ struct xfrm_policy_walk walk;
+ int rc;
- return xfrm_policy_walk(XFRM_POLICY_TYPE_MAIN, dump_sp, &data);
+ xfrm_policy_walk_init(&walk, XFRM_POLICY_TYPE_MAIN);
+ rc = xfrm_policy_walk(&walk, dump_sp, &data);
+ xfrm_policy_walk_done(&walk);
+
+ return rc;
}
static int key_notify_policy_flush(struct km_event *c)
