From: jamal <[EMAIL PROTECTED]>
Date: Tue, 20 Dec 2005 08:47:12 -0500
> On Mon, 2005-19-12 at 23:38 -0800, David S. Miller wrote:
> > Every time we build a bundle, we add each xfrm_dst into a list
> > hung off of the xfrm_state.
> >
> "build a bundle" as in when the policy tmpl is resolved?
Correct.
> > The remaining gap is the policy bundle list. That's the remaining
> > inefficient data structure that limits performance in this area, but
> > this patch makes it no worse and no better.
>
> Why is the policy bundle list inefficient?
It's a stupid linked list and we have to traverse the thing
on every route lookup. It's not too bad if we cache the
route in a socket, but for routing and other non-cached
paths, it's serious overhead.
The routing lookup path gets us to xfrm_lookup(). That uses
the flow cache to find the policy, and using that we do
xfrm_find_bundle() which walks that linked list trying to
find an exact match, on ipv4 this looks like:
static struct dst_entry *
__xfrm4_find_bundle(struct flowi *fl, struct xfrm_policy *policy)
{
struct dst_entry *dst;
read_lock_bh(&policy->lock);
for (dst = policy->bundles; dst; dst = dst->next) {
struct xfrm_dst *xdst = (struct xfrm_dst*)dst;
if (xdst->u.rt.fl.oif == fl->oif && /*XXX*/
xdst->u.rt.fl.fl4_dst == fl->fl4_dst &&
xdst->u.rt.fl.fl4_src == fl->fl4_src &&
xfrm_bundle_ok(xdst, fl, AF_INET)) {
dst_clone(dst);
break;
}
}
read_unlock_bh(&policy->lock);
return dst;
}
Deeper, in xfrm_bundle_ok() we do xfrm_selector_match(), so the
bundles have to be precisely keyed. There are some redundant
checks in these paths that could be eliminated with some refinements.
But the policy bundle list itself should probably be turned into
a hash, or as Alexey suggests in xfrm_lookup():
/* Try to find matching bundle.
*
* LATER: help from flow cache. It is optional, this
* is required only for output policy.
*/
dst = xfrm_find_bundle(fl, policy, family);
We could also dampen the locking a bit by moving the policy and
bundle lookup path over to RCU. The flow cache is per-cpu with
no locking, so that's pretty sane already.
So, there is a lot of fixing up we can do here. :-)
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
