diff options
| author | Timo Teras <timo.teras@iki.fi> | 2008-02-28 21:31:08 -0800 |
|---|---|---|
| committer | David S. Miller <davem@davemloft.net> | 2008-02-28 21:31:08 -0800 |
| commit | 4c563f7669c10a12354b72b518c2287ffc6ebfb3 (patch) | |
| tree | 056ec93f192f31640f32983c9e11bc7ce1c0692f /include | |
| parent | 1e04d530705280770e003ac8db516722cca54758 (diff) | |
[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>
Diffstat (limited to 'include')
| -rw-r--r-- | include/linux/xfrm.h | 3 | ||||
| -rw-r--r-- | include/net/xfrm.h | 52 |
2 files changed, 52 insertions, 3 deletions
diff --git a/include/linux/xfrm.h b/include/linux/xfrm.h index e31b8c84f2c..0c82c80b277 100644 --- a/include/linux/xfrm.h +++ b/include/linux/xfrm.h @@ -113,7 +113,8 @@ enum { XFRM_POLICY_TYPE_MAIN = 0, XFRM_POLICY_TYPE_SUB = 1, - XFRM_POLICY_TYPE_MAX = 2 + XFRM_POLICY_TYPE_MAX = 2, + XFRM_POLICY_TYPE_ANY = 255 }; enum diff --git a/include/net/xfrm.h b/include/net/xfrm.h index eea7785cc75..9b620566519 100644 --- a/include/net/xfrm.h +++ b/include/net/xfrm.h @@ -121,6 +121,7 @@ extern struct mutex xfrm_cfg_mutex; struct xfrm_state { /* Note: bydst is re-used during gc */ + struct list_head all; struct hlist_node bydst; struct hlist_node bysrc; struct hlist_node byspi; @@ -424,6 +425,7 @@ struct xfrm_tmpl struct xfrm_policy { struct xfrm_policy *next; + struct list_head bytype; struct hlist_node bydst; struct hlist_node byidx; @@ -1160,6 +1162,18 @@ struct xfrm6_tunnel { int priority; }; +struct xfrm_state_walk { + struct xfrm_state *state; + int count; + u8 proto; +}; + +struct xfrm_policy_walk { + struct xfrm_policy *policy; + int count; + u8 type, cur_type; +}; + extern void xfrm_init(void); extern void xfrm4_init(void); extern void xfrm_state_init(void); @@ -1184,7 +1198,23 @@ static inline void xfrm6_fini(void) extern int xfrm_proc_init(void); #endif -extern int xfrm_state_walk(u8 proto, int (*func)(struct xfrm_state *, int, void*), void *); +static inline void xfrm_state_walk_init(struct xfrm_state_walk *walk, u8 proto) +{ + walk->proto = proto; + walk->state = NULL; + walk->count = 0; +} + +static inline void xfrm_state_walk_done(struct xfrm_state_walk *walk) +{ + if (walk->state != NULL) { + xfrm_state_put(walk->state); + walk->state = NULL; + } +} + +extern int xfrm_state_walk(struct xfrm_state_walk *walk, + int (*func)(struct xfrm_state *, int, void*), void *); extern struct xfrm_state *xfrm_state_alloc(void); extern struct xfrm_state *xfrm_state_find(xfrm_address_t *daddr, xfrm_address_t *saddr, struct flowi *fl, struct xfrm_tmpl *tmpl, @@ -1306,7 +1336,25 @@ static inline int xfrm4_udp_encap_rcv(struct sock *sk, struct sk_buff *skb) #endif struct xfrm_policy *xfrm_policy_alloc(gfp_t gfp); -extern int xfrm_policy_walk(u8 type, int (*func)(struct xfrm_policy *, int, int, void*), void *); + +static inline void xfrm_policy_walk_init(struct xfrm_policy_walk *walk, u8 type) +{ + walk->cur_type = XFRM_POLICY_TYPE_MAIN; + walk->type = type; + walk->policy = NULL; + walk->count = 0; +} + +static inline void xfrm_policy_walk_done(struct xfrm_policy_walk *walk) +{ + if (walk->policy != NULL) { + xfrm_pol_put(walk->policy); + walk->policy = NULL; + } +} + +extern int xfrm_policy_walk(struct xfrm_policy_walk *walk, + int (*func)(struct xfrm_policy *, int, int, void*), void *); int xfrm_policy_insert(int dir, struct xfrm_policy *policy, int excl); struct xfrm_policy *xfrm_policy_bysel_ctx(u8 type, int dir, struct xfrm_selector *sel, |