Optimize policy dumping

From RFC 2367:

net/xfrm/xfrm_policy.c +36 -30

index 64d3938..c8a98ca 100644
@@ -860,57 +860,70 @@ EXPORT_SYMBOL(xfrm_policy_flush);
 int xfrm_policy_walk(u8 type, int (*func)(struct xfrm_policy *, int, int, void*),
 		     void *data)
 {
-	struct xfrm_policy *pol;
 	struct hlist_node *entry;
-	int dir, count, error;
+	int dir = 0, last_dir = 0, count = 0, error = -ENOENT;
+	struct xfrm_policy *pol = NULL, *send_pol = NULL, *last_pol = NULL;
 
 	read_lock_bh(&xfrm_policy_lock);
-	count = 0;
+
 	for (dir = 0; dir < 2*XFRM_POLICY_MAX; dir++) {
 		struct hlist_head *table = xfrm_policy_bydst[dir].table;
 		int i;
 
 		hlist_for_each_entry(pol, entry,
 				     &xfrm_policy_inexact[dir], bydst) {
-			if (pol->type == type)
-				count++;
-		}
-		for (i = xfrm_policy_bydst[dir].hmask; i >= 0; i--) {
-			hlist_for_each_entry(pol, entry, table + i, bydst) {
-				if (pol->type == type)
-					count++;
+			if (count && send_pol && send_pol != last_pol) {
+				error = func(send_pol, dir % XFRM_POLICY_MAX, count, data);
+				if (error)
+					goto out;
+				send_pol = NULL;
 			}
-		}
-	}
-
-	if (count == 0) {
-		error = -ENOENT;
-		goto out;
-	}
-
-	for (dir = 0; dir < 2*XFRM_POLICY_MAX; dir++) {
-		struct hlist_head *table = xfrm_policy_bydst[dir].table;
-		int i;
 
-		hlist_for_each_entry(pol, entry,
-				     &xfrm_policy_inexact[dir], bydst) {
 			if (pol->type != type)
 				continue;
-			error = func(pol, dir % XFRM_POLICY_MAX, --count, data);
-			if (error)
-				goto out;
+
+			if (!count) {
+				last_pol = send_pol = pol;
+			} else {
+				send_pol = last_pol;
+				last_pol = pol;
+			}
+
+			last_dir = dir;
+			count++;
 		}
+
 		for (i = xfrm_policy_bydst[dir].hmask; i >= 0; i--) {
 			hlist_for_each_entry(pol, entry, table + i, bydst) {
+				if (count && send_pol && send_pol != last_pol) {
+					error = func(send_pol, dir % XFRM_POLICY_MAX, count, data);
+					send_pol = NULL;
+					if (error)
+						goto out;
+				}
 				if (pol->type != type)
 					continue;
-				error = func(pol, dir % XFRM_POLICY_MAX, --count, data);
-				if (error)
-					goto out;
+				if (!count) {
+					last_pol = send_pol = pol;
+				} else {
+					send_pol = last_pol;
+					last_pol = pol;
+				}
+				last_dir = dir;
+				count++;
 			}
 		}
 	}
-	error = 0;
+
+	if (send_pol && send_pol != last_pol) {
+		error = func(send_pol, last_dir % XFRM_POLICY_MAX, count, data);

A few cases that will behave incorrectly:

- two policies in xfrm_policy_inexact with the same direction:
after the first iteration we have last_pol = send_pol = first policy and no messages sent, after the second iteration we have send_pol = first policy, last_pol = second policy and still no messages sent. Since send_pol && send_pol != last_pol, the second to last block will send send_pol with last_dir, since count > 0 the last block will send send_pol again. So we get two times the first policy and zero times the second one.

- same case as above, but policies in opposite directions. The first policy will again be sent twice, but with last_dir, which is the direction of the second policy.

- three policies in xfrm_policy_inexact, two with similar direction, one with opposite direction. The first two iterations look similar and no policies are dumped, during the third iteration we have count && send_pol && send_pol != last_pol. So send_pol (the first policy) is sent, but with direction dir, which is at that time the opposite direction of the policy.

I guess its easy to construct more cases. In general I don't see how remebering only the last direction can work since two policies with potentially different directions are remembered. Within the loop you always use dir, which also look wrong.

All very valid points.
Yikes, the directionality is not something i thought clearly about or tested well. I can fix this but this code will only get fuglier. How about the following approach:

I add a new callback which is passed in the invocation to walk. This callback is invoked at the end to signal the end of the walk, sort of what done() does in netlink.
netlink doesnt use this call but pfkey does. So the burden is then moved to pfkey to keep track of the stoopid count.

Thoughts?

Quoted 11 lines · jamal

All very valid points.
Yikes, the directionality is not something i thought clearly about or tested well. I can fix this but this code will only get fuglier. How about the following approach:

I add a new callback which is passed in the invocation to walk. This callback is invoked at the end to signal the end of the walk, sort of what done() does in netlink.
netlink doesnt use this call but pfkey does. So the burden is then moved to pfkey to keep track of the stoopid count.

Quoted 1 line

Thoughts?

I think the complications come from the fact that you remeber two policies, but only one seems necessary. How about this (completely untested) patch? It simply uses increasing sequence numbers for all but the last entry and uses zero for the last one.

I think the complications come from the fact that you remeber two policies, but only one seems necessary. How about this (completely untested) patch? It simply uses increasing sequence numbers for all but the last entry and uses zero for the last one.

And the same for SAs.

Quoted 5 lines · Patrick McHardy

I think the complications come from the fact that you remeber two policies, but only one seems necessary. How about this (completely untested) patch? It simply uses increasing sequence numbers for all but the last entry and uses zero for the last one.

I could give this a try in about 2 hours. But why dont you like the callback approach? You have to admit, this is hairy code.

Both ways are fine I guess. But the counting has almost no overhead with the patch I sent, so I'm not sure if its worth adding a callback (which still needs to get the last policy/SA as argument, so that part won't get any nicer).

BTW, I'm not sure whether there are further requirements than those you quoted, but according to that text, using 1 for all but the last message would be fine as well :)

Quoted 5 lines · Patrick McHardy

Both ways are fine I guess. But the counting has almost no overhead with the patch I sent, so I'm not sure if its worth adding a callback (which still needs to get the last policy/SA as argument, so that part won't get any nicer).

The only arguement for the callback is it will lead to eventually having some semi-reliable dump for pfkey. But i think that is a separate issue to be tackled later.

I am actually scratching my head a little as to what happens when the pfkey socket recv is full.

Quoted 5 lines · Patrick McHardy

I think the complications come from the fact that you remeber two policies, but only one seems necessary. How about this (completely untested) patch? It simply uses increasing sequence numbers for all but the last entry and uses zero for the last one.

I could give this a try in about 2 hours. But why dont you like the callback approach? You have to admit, this is hairy code.

Quoted 2 lines

And the same for SAs.

The SA has less things to remember, so it is easier; but i will apply this and test it and if it meets the requirements I will look into converting the SA to the same scheme.

cheers,
jamal

Patrick,

Your approach is much cleaner. Let me give these a few tests then I will repost later today; forget about the callback approach for now.

Quoted 5 lines · jamal

Patrick,

Your approach is much cleaner. Let me give these a few tests then I will repost later today; forget about the callback approach for now.

I have just applied the policy patch; havent compiled or tested (the setup takes me a while to put together). But by staring, I am seeing that you will end up with the same thing of sending a NULL or the same entry twice.

Consider a simple hypothetical test. You have one one entry in the xfrm_policy_inexact table that matches. It happens to be the fifth out of 10 elements. You find it at the 5th iteration. At the sixth iteration you send it and last becomes null.

All the way down, you call func with a NULL entry. You could add a check to make sure it only gets invoked when last is not null, but the result is in such a case, you will never send a 0 count element. I am sure there could be other tricky scenarios like this that could be constructed.

Thoughts.

Quoted 7 lines · jamal

All the way down, you call func with a NULL entry. You could add a check to make sure it only gets invoked when last is not null, but the result is in such a case, you will never send a 0 count element. I am sure there could be other tricky scenarios like this that could be constructed.

Thoughts.

Double sending can't happen, but you're right about potentially sending a NULL ptr when after setting it to NULL we don't find any other matching elements.

This patch should fix it (and is even simpler), by moving the check for pol->type != type before sending, we make sure that last always contains a valid element unless count == 0.

Also fixed an incorrect gcc warning about last_dir potentially being used uninitialized.

This patch should fix it (and is even simpler), by moving the check for pol->type != type before sending, we make sure that last always contains a valid element unless count == 0.

Also fixed an incorrect gcc warning about last_dir potentially being used uninitialized.

Ok, both looked good except for the test of a single entry. This was because you would break out of the loop with count of 0. The patch against yours would look like something attached for the state case. Dont forget there are two spots on the policy side of things;->

You can either submit both patches or i could later today. If you do, please look at some of the comments i made in the first patch and include them.

jamal wrote:

I'd prefer if you did it since you're already testing the thing :)