[XFRM] Optimize SA dumping

[XFRM] Optimize SA dumping

[jamal]

[-- Attachment #1: Type: text/plain, Size: 81 bytes --]


Ok, heres is the SA version and the numbers.
Against net-2.6.20

cheers,
jamal


[-- Attachment #2: xfrm_sa_dumpopt --]
[-- Type: text/plain, Size: 2475 bytes --]

[XFRM] Optimize SA dumping

Same comments as in "[XFRM] Optimize policy dumping"

Again, the same issue as in the policy optimization; we could do better
only if we didnt have to do bending backwards to make pfkey happy.
In the future we could move some of this burden to pfkey itself.
For now this is better than whats there today.

The numbers are (20K SAs):

------
1) before the change ..
speedopolis:~# time ./ip xf sta

real    0m5.321s
user    0m0.004s
sys     0m5.316s

2) after the change ...
speedopolis:~# time ./ip x state

real    0m1.994s
user    0m0.000s
sys     0m1.992s
------

Signed-off-by: Jamal Hadi Salim <hadi@cyberus.ca>

---
commit 8a0f11d0e7197624341ab0536fbf24af5cb67e2b
tree 48dc4e907733e9c6989e7c4e8ac9bcd72c4d26b6
parent 0355ced4a81a1af96b4531680e9c593d3967a5f1
author Jamal Hadi Salim <hadi@cyberus.ca> Sun, 03 Dec 2006 10:29:50 -0500
committer Jamal Hadi Salim <hadi@cyberus.ca> Sun, 03 Dec 2006 10:29:50 -0500

 net/xfrm/xfrm_state.c |   38 +++++++++++++++++++++++---------------
 1 files changed, 23 insertions(+), 15 deletions(-)

diff --git a/net/xfrm/xfrm_state.c b/net/xfrm/xfrm_state.c
index 864962b..148b148 100644
--- a/net/xfrm/xfrm_state.c
+++ b/net/xfrm/xfrm_state.c
@@ -1099,32 +1099,40 @@ int xfrm_state_walk(u8 proto, int (*func)(struct xfrm_state *, int, void*),
 		    void *data)
 {
 	int i;
-	struct xfrm_state *x;
 	struct hlist_node *entry;
+	struct xfrm_state *x, *send_x = NULL, *last_x = NULL;
 	int count = 0;
-	int err = 0;
+	int err = -ENOENT;
 
 	spin_lock_bh(&xfrm_state_lock);
-	for (i = 0; i <= xfrm_state_hmask; i++) {
-		hlist_for_each_entry(x, entry, xfrm_state_bydst+i, bydst) {
-			if (xfrm_id_proto_match(x->id.proto, proto))
-				count++;
-		}
-	}
-	if (count == 0) {
-		err = -ENOENT;
-		goto out;
-	}
 
 	for (i = 0; i <= xfrm_state_hmask; i++) {
 		hlist_for_each_entry(x, entry, xfrm_state_bydst+i, bydst) {
+			if (count && send_x != last_x) {
+				err = func(send_x, count, data);
+				if (err)
+					goto out;
+				send_x = NULL;
+			}
 			if (!xfrm_id_proto_match(x->id.proto, proto))
 				continue;
-			err = func(x, --count, data);
-			if (err)
-				goto out;
+
+			if (!count) {
+				last_x = send_x = x;
+			} else {
+				send_x = last_x;
+				last_x = x;
+			}
+			count++;
 		}
 	}
+
+	if (send_x && send_x != last_x) 
+		err = func(send_x, count, data);
+	if (count) {
+		BUG_TRAP(last_x == NULL);
+		err = func(last_x, 0, data);
+	}
 out:
 	spin_unlock_bh(&xfrm_state_lock);
 	return err;

Re: [XFRM] Optimize SA dumping

[Patrick McHardy]

jamal wrote:
>  	for (i = 0; i <= xfrm_state_hmask; i++) {
>  		hlist_for_each_entry(x, entry, xfrm_state_bydst+i, bydst) {
> +			if (count && send_x != last_x) {
> +				err = func(send_x, count, data);
> +				if (err)
> +					goto out;
> +				send_x = NULL;
> +			}
>  			if (!xfrm_id_proto_match(x->id.proto, proto))
>  				continue;

After you sent send_x and set it to NULL, it will be different from
last_x (since that is != NULL) and the NULL pointer will be given
to func() when continuing here.

> -			err = func(x, --count, data);
> -			if (err)
> -				goto out;
> +
> +			if (!count) {
> +				last_x = send_x = x;
> +			} else {
> +				send_x = last_x;
> +				last_x = x;
> +			}
> +			count++;
>  		}
>  	}

Re: [XFRM] Optimize SA dumping

[jamal]

On Mon, 2006-04-12 at 13:36 +0100, Patrick McHardy wrote:
> jamal wrote:
> >  	for (i = 0; i <= xfrm_state_hmask; i++) {
> >  		hlist_for_each_entry(x, entry, xfrm_state_bydst+i, bydst) {
> > +			if (count && send_x != last_x) {
> > +				err = func(send_x, count, data);
> > +				if (err)
> > +					goto out;
> > +				send_x = NULL;
> > +			}
> >  			if (!xfrm_id_proto_match(x->id.proto, proto))
> >  				continue;
> 
> After you sent send_x and set it to NULL, it will be different from
> last_x (since that is != NULL) and the NULL pointer will be given
> to func() when continuing here.
> 

This one you lost me. Can you give me an example? one or two SAs found?

In any case, if i go the done callback approach, I can get rid of all
this tracking thing ...

cheers,
jamal

> > -			err = func(x, --count, data);
> > -			if (err)
> > -				goto out;
> > +
> > +			if (!count) {
> > +				last_x = send_x = x;
> > +			} else {
> > +				send_x = last_x;
> > +				last_x = x;
> > +			}
> > +			count++;
> >  		}
> >  	}
> 
> 
> 
> 

Re: [XFRM] Optimize SA dumping

[Patrick McHardy]

jamal wrote:
> On Mon, 2006-04-12 at 13:36 +0100, Patrick McHardy wrote:
> 
>>jamal wrote:
>>
>>> 	for (i = 0; i <= xfrm_state_hmask; i++) {
>>> 		hlist_for_each_entry(x, entry, xfrm_state_bydst+i, bydst) {
>>>+			if (count && send_x != last_x) {
>>>+				err = func(send_x, count, data);
>>>+				if (err)
>>>+					goto out;
>>>+				send_x = NULL;
>>>+			}
>>> 			if (!xfrm_id_proto_match(x->id.proto, proto))
>>> 				continue;
>>
>>After you sent send_x and set it to NULL, it will be different from
>>last_x (since that is != NULL) and the NULL pointer will be given
>>to func() when continuing here.
>>
> 
> 
> This one you lost me. Can you give me an example? one or two SAs found?

More than three SAs, so we have:

send_x = last_x = NULL

1. iteration:

send_x = last_x = first policy

2. iteration:

send_x = first policy
last_x = second policy

3. iteration:

dump send_x, set send_x = NULL
continue at continue statement

4. iteration:

We have send_x = NULL and last_x != NULL, so send_x != last_x,
leading to dump(NULL, ...)

> In any case, if i go the done callback approach, I can get rid of all
> this tracking thing ...

I need to read your other mail first before commenting on this :)

Re: [XFRM] Optimize SA dumping

[jamal]

On Mon, 2006-04-12 at 14:39 +0100, Patrick McHardy wrote:
...
...
> 4. iteration:
> 
> We have send_x = NULL and last_x != NULL, so send_x != last_x,
> leading to dump(NULL, ...)
> 

Ok, that is a very easy fix i.e just have 
         (send_x && send_x != last_x) 
as is done when the loop is exited. I thought i did that.

But i dont know if i even wanna fix that; consider the callback approach
i mentioned earlier.

> > In any case, if i go the done callback approach, I can get rid of all
> > this tracking thing ...
> 
> I need to read your other mail first before commenting on this :)

There is one key thing to observe: 
The count parameter is only used by pfkey; this is because the RFC
requires that we set the last entry to zero. So all that counting done
in the original codes first loop (which is huge overhead if you have a
large number of rules) is just so that we can achieve that ;->

By doing a callback, we move the burden of storing any state to pfkey
and free xfrm.


cheers,
jamal