allowedips: maintain per-peer list of allowedips

This makes `wg show` and `wg showconf` and the like significantly
faster, since we don't have to iterate through every node of the trie
for every single peer. It also makes netlink cursor resumption much less
problematic, since we're just iterating through a list, rather than
having to save a traversal stack.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>

1 files changed, 19 insertions, 14 deletions

diff --git a/src/allowedips.h b/src/allowedips.h
index 29e15a2..e5c83ca 100644
--- a/src/allowedips.h
+++ b/src/allowedips.h
@@ -11,7 +11,23 @@
 #include <linux/ipv6.h>
 
 struct wg_peer;
-struct allowedips_node;
+
+struct allowedips_node {
+	struct wg_peer __rcu *peer;
+	struct allowedips_node __rcu *bit[2];
+	/* While it may seem scandalous that we waste space for v4,
+	 * we're alloc'ing to the nearest power of 2 anyway, so this
+	 * doesn't actually make a difference.
+	 */
+	u8 bits[16] __aligned(__alignof(u64));
+	u8 cidr, bit_at_a, bit_at_b, bitlen;
+
+	/* Keep rarely used list at bottom to be beyond cache line. */
+	union {
+		struct list_head peer_list;
+		struct rcu_head rcu;
+	};
+};
 
 struct allowedips {
 	struct allowedips_node __rcu *root4;
@@ -19,13 +35,6 @@ struct allowedips {
 	u64 seq;
 };
 
-struct allowedips_cursor {
-	u64 seq;
-	struct allowedips_node *stack[128];
-	unsigned int len;
-	bool second_half;
-};
-
 void wg_allowedips_init(struct allowedips *table);
 void wg_allowedips_free(struct allowedips *table, struct mutex *mutex);
 int wg_allowedips_insert_v4(struct allowedips *table, const struct in_addr *ip,
@@ -34,12 +43,8 @@ int wg_allowedips_insert_v6(struct allowedips *table, const struct in6_addr *ip,
 			    u8 cidr, struct wg_peer *peer, struct mutex *lock);
 void wg_allowedips_remove_by_peer(struct allowedips *table,
 				  struct wg_peer *peer, struct mutex *lock);
-int wg_allowedips_walk_by_peer(struct allowedips *table,
-			       struct allowedips_cursor *cursor,
-			       struct wg_peer *peer,
-			       int (*func)(void *ctx, const u8 *ip, u8 cidr,
-					   int family),
-			       void *ctx, struct mutex *lock);
+/* The ip input pointer should be __aligned(__alignof(u64))) */
+int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr);
 
 /* These return a strong reference to a peer: */
 struct wg_peer *wg_allowedips_lookup_dst(struct allowedips *table,