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

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

Herbert Xu wrote:
> On Thu, Mar 18, 2010 at 09:30:58PM +0200, Timo Teräs wrote:
>> Now, these created xfrm_dst gets cached in policy->bundles
>> with ref count zero and not deleted until garbage collection
>> is required. That's how xfrm_find_bundle tries to reuse them
>> (but it does O(n) lookup).
> 
> Yes but the way you're caching it in the policy means that it
> only helps if two consecutive packets happen to match the same
> bundle.  If your traffic mix was such that each packet required
> a different bundle, then we're back to where we started.
> 
> That's why I was asking for you to directly cache the xfrm_dst
> objects in the flow cache.

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.

And this is even more useful with the gre+esp. No matter what
I send inside gre (with private IPs), it ends up being routed
to more limited set of outer public IP parties. The bundle
lookup happens with the public-IP flow, so the speed up works
even better.

>> Actually no. As the pmtu case showed, it's more likely that
>> xfrm_dst needs to be regenerated, but the policy stays the
>> same since policy db isn't touched that often. If we keep
>> them separately we can almost most of the time avoid doing
>> policy lookup which is also O(n). Also the currently cache
>> entry validation is needs to check policy's bundles_genid
>> before allowing touching of xfrm_dst. Otherwise we would have
>> to keep global bundle_genid, and we'd lose the parent pointer
>> on cache miss.
> A back-pointer does not require an O(n) lookup.

True. But if we go and prune a bundle due to it being bad or
needing garbage collection we need to invalidate all bundles
pointers, and we cannot access the back-pointer. Alternatively
we need to keep xfrm_dst references again in the flow cache
requiring an expensive iteration of all flow cache entries
whenever a xfrm_dst needs to be deleted (which happens often).

- Timo