[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>
diff --git a/include/net/xfrm.h b/include/net/xfrm.h
index eea7785..9b62056 100644
--- a/include/net/xfrm.h
+++ b/include/net/xfrm.h
@@ -121,6 +121,7 @@
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_policy
{
struct xfrm_policy *next;
+ struct list_head bytype;
struct hlist_node bydst;
struct hlist_node byidx;
@@ -1160,6 +1162,18 @@
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 @@
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 @@
#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,