Skip to contentSkip to conversation

: Speed up xfrm_policy and xfrm_state walking

PATCH RESEND Superseded Timo Teräs 2 participants 4 messages Feb 1, 2008 – Feb 29, 2008

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH RESEND 1/1 : 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.

---

 include/linux/xfrm.h   |    3 +-
 include/net/xfrm.h     |   52 ++++++++++++++++++++++++++++++-
 net/key/af_key.c       |   22 +++++++++++--
 net/xfrm/xfrm_policy.c |   79 ++++++++++++++++++++++++++++--------------------
 net/xfrm/xfrm_state.c  |   53 ++++++++++++++++++++++----------
 net/xfrm/xfrm_user.c   |   71 ++++++++++++++++++++++++++-----------------
 6 files changed, 195 insertions(+), 85 deletions(-)
include/linux/xfrm.h +2 -1
index e31b8c8..0c82c80 100644
@@ -113,7 +113,8 @@ enum
 {
 	XFRM_POLICY_TYPE_MAIN	= 0,
 	XFRM_POLICY_TYPE_SUB	= 1,
-	XFRM_POLICY_TYPE_MAX	= 2
+	XFRM_POLICY_TYPE_MAX	= 2,
+	XFRM_POLICY_TYPE_ANY	= 255
 };
 
 enum
include/net/xfrm.h +50 -2

82 lines not on this page · raw message

net/key/af_key.c +18 -4
index 16b72b5..d24bb9c 100644
@@ -1742,12 +1742,18 @@ static int pfkey_dump(struct sock *sk, struct sk_buff *skb, struct sadb_msg *hdr
 {
 	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,6 +1786,7 @@ static int check_reqid(struct xfrm_policy *xp, int dir, int count, void *ptr)
 
 static u32 gen_reqid(void)
 {
+	struct xfrm_policy_walk walk;
 	u32 start;
 	static u32 reqid = IPSEC_MANUAL_REQID_MAX;
 
@@ -1788,9 +1795,10 @@ static u32 gen_reqid(void)
 		++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);
+		if (xfrm_policy_walk(&walk, check_reqid, (void*)&reqid) != -EEXIST)
 			return reqid;
+		xfrm_policy_walk_done(&walk);
 	} while (reqid != start);
 	return 0;
 }
@@ -2664,8 +2672,14 @@ static int dump_sp(struct xfrm_policy *xp, int dir, int count, void *ptr)
 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;
+
+	xfrm_policy_walk_init(&walk, XFRM_POLICY_TYPE_MAIN);
+	rc = xfrm_policy_walk(&walk, dump_sp, &data);
+	xfrm_policy_walk_done(&walk);
 
-	return xfrm_policy_walk(XFRM_POLICY_TYPE_MAIN, dump_sp, &data);
+	return rc;
 }
 
 static int key_notify_policy_flush(struct km_event *c)
net/xfrm/xfrm_policy.c +46 -33

133 lines not on this page · raw message

net/xfrm/xfrm_state.c +36 -17

96 lines not on this page · raw message

net/xfrm/xfrm_user.c +43 -28

160 lines not on this page · raw message

Signature · 1 line
1.5.2.5
maintainer
#1 lore raw

From: Timo_Teräs <[email protected]>
Date: Fri, 01 Feb 2008 16:58:04 +0200

Quoted 11 lines
net/key/af_key.c +1 -0
@@ -1780,6 +1786,7 @@ static int check_reqid(struct xfrm_policy *xp, int dir, int count, void *ptr)
 
 static u32 gen_reqid(void)
 {
+	struct xfrm_policy_walk walk;
 	u32 start;
 	static u32 reqid = IPSEC_MANUAL_REQID_MAX;
 
@@ -1788,9 +1795,10 @@ static u32 gen_reqid(void)
 		++reqid;
 		if (reqid == 0)

net/key/af_key.c static u32 gen_reqid(void) · line 1804

Quoted 10 lines
net/key/af_key.c +3 -2
 			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);
+		if (xfrm_policy_walk(&walk, check_reqid, (void*)&reqid) != -EEXIST)
 			return reqid;
+		xfrm_policy_walk_done(&walk);
 	} while (reqid != start);
 	return 0;
 }

This will potentially leak walk->policy in the != -EEXIST case.

I think what needs to happen is we invoke xfrm_policy_walk_done() unconditionally, then we'll potentially return reqid.

#2 lore raw

PATCH v2 1/1 : 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.

---

Quoted 4 lines · David Miller

This will potentially leak walk->policy in the != -EEXIST case.

I think what needs to happen is we invoke xfrm_policy_walk_done() unconditionally, then we'll potentially return reqid.

Good catch. Fixed as suggested.

Also the walk context structure layout was changed to align better on 64-bit machines as suggested by Margit Schubert-While.

 include/linux/xfrm.h   |    3 +-
 include/net/xfrm.h     |   52 ++++++++++++++++++++++++++++++-
 net/key/af_key.c       |   24 ++++++++++++--
 net/xfrm/xfrm_policy.c |   79 ++++++++++++++++++++++++++++--------------------
 net/xfrm/xfrm_state.c  |   53 ++++++++++++++++++++++----------
 net/xfrm/xfrm_user.c   |   71 ++++++++++++++++++++++++++-----------------
 6 files changed, 197 insertions(+), 85 deletions(-)
include/linux/xfrm.h +2 -1
index e31b8c8..0c82c80 100644
@@ -113,7 +113,8 @@ enum
 {
 	XFRM_POLICY_TYPE_MAIN	= 0,
 	XFRM_POLICY_TYPE_SUB	= 1,
-	XFRM_POLICY_TYPE_MAX	= 2
+	XFRM_POLICY_TYPE_MAX	= 2,
+	XFRM_POLICY_TYPE_ANY	= 255
 };
 
 enum
include/net/xfrm.h +50 -2

82 lines not on this page · raw message

net/key/af_key.c +20 -4
index 1c85392..0d7c195 100644
@@ -1742,12 +1742,18 @@ static int pfkey_dump(struct sock *sk, struct sk_buff *skb, struct sadb_msg *hdr
 {
 	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 int check_reqid(struct xfrm_policy *xp, int dir, int count, void *ptr)
 
 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 @@ static u32 gen_reqid(void)
 		++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 dump_sp(struct xfrm_policy *xp, int dir, int count, void *ptr)
 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;
+
+	xfrm_policy_walk_init(&walk, XFRM_POLICY_TYPE_MAIN);
+	rc = xfrm_policy_walk(&walk, dump_sp, &data);
+	xfrm_policy_walk_done(&walk);
 
-	return xfrm_policy_walk(XFRM_POLICY_TYPE_MAIN, dump_sp, &data);
+	return rc;
 }
 
 static int key_notify_policy_flush(struct km_event *c)
net/xfrm/xfrm_policy.c +46 -33

133 lines not on this page · raw message

net/xfrm/xfrm_state.c +36 -17

96 lines not on this page · raw message

net/xfrm/xfrm_user.c +43 -28

160 lines not on this page · raw message

Signature · 1 line
1.5.2.5
maintainer Applied
#3 lore raw

From: Timo_Teräs <[email protected]>
Date: Fri, 15 Feb 2008 20:22:54 +0200

Quoted 11 lines

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.

Applied, although this will make add/delete slightly slower.

Could you do that AF_KEY dumping patch you talked about? I change my mind, we can do it.

THanks.