From 4c563f7669c10a12354b72b518c2287ffc6ebfb3 Mon Sep 17 00:00:00 2001 From: Timo Teras Date: Thu, 28 Feb 2008 21:31:08 -0800 Subject: [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 Signed-off-by: David S. Miller --- include/net/xfrm.h | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 50 insertions(+), 2 deletions(-) (limited to 'include/net/xfrm.h') 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, -- cgit v1.2.3-70-g09d2