routingtable: rewrite core functions

When removing by peer, prev needs to be set to *nptr in order to
traverse that part of the trie.

The other remove by IP function can simply be removed, as it's not in
use.

The root freeing function can use pre-order traversal instead of
post-order.

The pre-order traversal code in general is now a nice iterator macro.

The common bits function can use the fast fls instructions and the match
function can be rewritten to simply compare common bits.

While we're at it, let's add tons of new tests, randomized checking
against a dumb implementation, and graphviz output.

And in general, it's nice to clean things up.

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

1 files changed, 2 insertions, 15 deletions

diff --git a/src/config.c b/src/config.c
index 2736377..a5a25c9 100644
--- a/src/config.c
+++ b/src/config.c
@@ -209,20 +209,6 @@ static inline int use_data(struct data_remaining *data, size_t size)
 	return 0;
 }
 
-static int calculate_ipmasks_size(void *ctx, struct wireguard_peer *peer, union nf_inet_addr ip, u8 cidr, int family)
-{
-	size_t *count = ctx;
-	*count += sizeof(struct wgipmask);
-	return 0;
-}
-
-static size_t calculate_peers_size(struct wireguard_device *wg)
-{
-	size_t len = peer_total_count(wg) * sizeof(struct wgpeer);
-	routing_table_walk_ips(&wg->peer_routing_table, &len, calculate_ipmasks_size);
-	return len;
-}
-
 static int populate_ipmask(void *ctx, union nf_inet_addr ip, u8 cidr, int family)
 {
 	int ret;
@@ -305,7 +291,8 @@ int config_get_device(struct wireguard_device *wg, void __user *user_device)
 	mutex_lock(&wg->device_update_lock);
 
 	if (!user_device) {
-		ret = calculate_peers_size(wg);
+		ret = peer_total_count(wg) * sizeof(struct wgpeer)
+		    + routing_table_count_nodes(&wg->peer_routing_table) * sizeof(struct wgipmask);
 		goto out;
 	}