]> git.baikalelectronics.ru Git - kernel.git/commit
[XFRM]: Speed up xfrm_policy and xfrm_state walking
authorTimo Teras <timo.teras@iki.fi>
Fri, 29 Feb 2008 05:31:08 +0000 (21:31 -0800)
committerDavid S. Miller <davem@davemloft.net>
Fri, 29 Feb 2008 05:31:08 +0000 (21:31 -0800)
commit01c45a948e637258a65693ce9a62c33dfc31e20b
tree056ec93f192f31640f32983c9e11bc7ce1c0692f
parentd163bc905e548b59f8b54a9637e542cde14812a5
[XFRM]: Speed up xfrm_policy and xfrm_state walking

Change xfrm_policy and xfrm_state walking algorithm from O(n^2) to O(n).
This is achieved adding the entries to one more list which is used
solely for walking the entries.

This also fixes some races where the dump can have duplicate or missing
entries when the SPD/SADB is modified during an ongoing dump.

Dumping SADB with 20000 entries using "time ip xfrm state" the sys
time dropped from 1.012s to 0.080s.

Signed-off-by: Timo Teras <timo.teras@iki.fi>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/linux/xfrm.h
include/net/xfrm.h
net/key/af_key.c
net/xfrm/xfrm_policy.c
net/xfrm/xfrm_state.c
net/xfrm/xfrm_user.c