From 8d4ac42ceb67a93fc1e5c0d045819597c5da47d0 Mon Sep 17 00:00:00 2001
From: Guus Sliepen <guus@meshlink.io>
Date: Mon, 14 Oct 2019 21:34:54 +0200
Subject: [PATCH] Remove support for broadcast packets.

This is not used in MeshLink. Removing support for this also means we no
longer have to calculate a minimum spanning tree whenever the graph is
updated.
---
 src/connection.h |  2 +-
 src/graph.c      | 60 ------------------------------------------------
 src/net.h        |  1 -
 src/net_packet.c | 16 -------------
 4 files changed, 1 insertion(+), 78 deletions(-)

diff --git a/src/connection.h b/src/connection.h
index ef688549..25e122d0 100644
--- a/src/connection.h
+++ b/src/connection.h
@@ -34,7 +34,7 @@ typedef struct connection_status_t {
 	uint16_t pinged: 1;                 /* sent ping */
 	uint16_t active: 1;                 /* 1 if active.. */
 	uint16_t connecting: 1;             /* 1 if we are waiting for a non-blocking connect() to finish */
-	uint16_t mst: 1;                    /* 1 if this connection is part of a minimum spanning tree */
+	uint16_t unused: 1;
 	uint16_t control: 1;                /* 1 if this is a control connection */
 	uint16_t pcap: 1;                   /* 1 if this is a control connection requesting packet capture */
 	uint16_t log: 1;                    /* 1 if this is a control connection requesting log dump */
diff --git a/src/graph.c b/src/graph.c
index d86ac4a8..9955ea41 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -56,65 +56,6 @@
 #include "xalloc.h"
 #include "graph.h"
 
-/* Implementation of Kruskal's algorithm.
-   Running time: O(EN)
-   Please note that sorting on weight is already done by add_edge().
-*/
-
-static void mst_kruskal(meshlink_handle_t *mesh) {
-	/* Clear MST status on connections */
-
-	for list_each(connection_t, c, mesh->connections) {
-		c->status.mst = false;
-	}
-
-	logger(mesh, MESHLINK_DEBUG, "Running Kruskal's algorithm:");
-
-	/* Clear visited status on nodes */
-
-	for splay_each(node_t, n, mesh->nodes) {
-		n->status.visited = false;
-	}
-
-	/* Starting point */
-
-	for splay_each(edge_t, e, mesh->edges) {
-		if(e->from->status.reachable) {
-			e->from->status.visited = true;
-			break;
-		}
-	}
-
-	/* Add safe edges */
-
-	bool skipped = false;
-
-	for splay_each(edge_t, e, mesh->edges) {
-		if(!e->reverse || (e->from->status.visited == e->to->status.visited)) {
-			skipped = true;
-			continue;
-		}
-
-		e->from->status.visited = true;
-		e->to->status.visited = true;
-
-		if(e->connection) {
-			e->connection->status.mst = true;
-		}
-
-		if(e->reverse->connection) {
-			e->reverse->connection->status.mst = true;
-		}
-
-		logger(mesh, MESHLINK_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight);
-
-		if(skipped) {
-			skipped = false;
-			next = mesh->edges->head;
-		}
-	}
-}
-
 /* Implementation of a simple breadth-first search algorithm.
    Running time: O(E)
 */
@@ -252,5 +193,4 @@ static void check_reachability(meshlink_handle_t *mesh) {
 void graph(meshlink_handle_t *mesh) {
 	sssp_bfs(mesh);
 	check_reachability(mesh);
-	mst_kruskal(mesh);
 }
diff --git a/src/net.h b/src/net.h
index 8ff07088..4da61bd4 100644
--- a/src/net.h
+++ b/src/net.h
@@ -89,7 +89,6 @@ extern int setup_vpn_in_socket(struct meshlink_handle *mesh, const sockaddr_t *)
 extern bool send_sptps_data(void *handle, uint8_t type, const void *data, size_t len);
 extern bool receive_sptps_record(void *handle, uint8_t type, const void *data, uint16_t len);
 extern void send_packet(struct meshlink_handle *mesh, struct node_t *, struct vpn_packet_t *);
-extern void broadcast_packet(struct meshlink_handle *mesh, const struct node_t *, struct vpn_packet_t *);
 extern char *get_name(struct meshlink_handle *mesh);
 extern void load_all_nodes(struct meshlink_handle *mesh);
 extern bool setup_myself_reloadable(struct meshlink_handle *mesh);
diff --git a/src/net_packet.c b/src/net_packet.c
index e4f3295a..53228369 100644
--- a/src/net_packet.c
+++ b/src/net_packet.c
@@ -477,22 +477,6 @@ void send_packet(meshlink_handle_t *mesh, node_t *n, vpn_packet_t *packet) {
 	return;
 }
 
-/* Broadcast a packet using the minimum spanning tree */
-
-void broadcast_packet(meshlink_handle_t *mesh, const node_t *from, vpn_packet_t *packet) {
-	// Always give ourself a copy of the packet.
-	if(from != mesh->self) {
-		send_packet(mesh, mesh->self, packet);
-	}
-
-	logger(mesh, MESHLINK_INFO, "Broadcasting packet of %d bytes from %s", packet->len, from->name);
-
-	for list_each(connection_t, c, mesh->connections)
-		if(c->status.active && c->status.mst && c != from->nexthop->connection) {
-			send_packet(mesh, c->node, packet);
-		}
-}
-
 static node_t *try_harder(meshlink_handle_t *mesh, const sockaddr_t *from, const vpn_packet_t *pkt) {
 	node_t *n = NULL;
 	bool hard = false;
-- 
2.39.2