Re: [PATCH] xfrm: cache bundle lookup results in flow cache

["Timo Teräs" <timo.teras@iki.fi>]

Timo Teräs wrote:
> Herbert Xu wrote:
>> On Fri, Mar 19, 2010 at 07:48:57AM +0200, Timo Teräs wrote:
>>> But it always matches. The caching happens using the inner
>>> flow. Inner flow always matches with the same bundle unless
>>> the bundle expires or goes stale. What happens is that I get
>>> multiple cache entries per-inner flow each referencing to the
>>> same bundle.
>>
>> Sorry for being slow, but if it always matches, doesn't that mean
>> you'll only have a single bundle in the policy bundle list? IOW
>> why do we need this at all?
> 
> No. The bundle created for specific flow, matches always later
> that flow.

Just figured that's it's easier to explain with an example.

We have SPD:
	10.1.0.0/16 - 10.2.0.0/16 tunnel
		1.2.3.4 - 4.3.2.1

Now we get n+1 clients to connect to server in 10.2.0.1.
They each get separate bundle, since the xfrm_dst will be
created and search using flow id's like:
	src 10.1.x.x dst 10.2.0.1

So there's one xfrm_policy and xfrm_state, but n+1
xfrm_dst's.

Since the flow cache caches the result of lookups on the
inner flow "10.1.x.x->10.2.0.1" basis, it always returns
matching valid bundle in O(1) time unless the xfrm_dst
expired.

Currently it's looked up with O(n) search in find_bundle.

Same thing happens with wildcard transport mode SPD's.

E.g. SPD:
	0.0.0.0/0 - 0.0.0.0/0 proto gre, transport

We are talking with gre to n+1 tunnel destinations.
We get n+1 xfrm_dst's in that xfrm_policy. Flow cache
works on inner flow using flows like:
	src 1.2.3.4 dst 4.3.2.1 proto gre
And can keep in cache the right policy always, and
the bundle to use as long as it stays valid.

Hopefully this explains why I think the patch is
useful.

- Timo