Initial nexthop maintenance implementation

Mostly taken from the FFD project, and quite incomplete.

6 files changed, 178 insertions, 18 deletions

diff --git a/src/announce.c b/src/announce.c
index 1891341..1d17a02 100644
--- a/src/announce.c
+++ b/src/announce.c
@@ -33,7 +33,7 @@
 gp_babel_announce_t* gp_babel_announce_new(gmrf_t *gmrf, gmrf_context_t *ctx) {
 	gp_babel_announce_t *a = calloc(1, sizeof(gp_babel_announce_t));
 
-	a->metric.metric = a->feasibility_distance.metric = a->last_metric = 0xffff;
+	a->metric.metric = a->feasibility_distance.metric = a->last_metric = GP_BABEL_INFINITY;
 
 	a->next = ctx->announces;
 	ctx->announces = a;
@@ -91,3 +91,113 @@ gp_babel_nexthop_t* gp_babel_announce_nexthop_new(gp_babel_announce_t *announce,
 
 	return nexthop;
 }
+
+static void maintain_nexthops(gmrf_t *gmrf, gp_babel_announce_t *announce) {
+	gp_babel_nexthop_t **cur, **next;
+	for (cur = &announce->nexthops; *cur; cur = next) {
+		gp_babel_nexthop_t *nexthop = *cur;
+		next = &nexthop->next;
+
+		if (!nexthop->neigh) /* local */
+			continue;
+
+		if (!nexthop->neigh->iface) {
+			if (nexthop->metric_seqno.metric != GP_BABEL_INFINITY) {
+				nexthop->metric_seqno.metric = GP_BABEL_INFINITY;
+				nexthop->last_update = gmrf_now(gmrf);
+				nexthop->last_update += GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10;
+			}
+
+			continue;
+		}
+
+		if (gmrf_now(gmrf) > nexthop->last_update+GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10) {
+			if (nexthop->metric_seqno.metric == GP_BABEL_INFINITY) {
+				*cur = *next;
+				next = cur;
+
+				if (announce->selected == nexthop)
+					announce->selected = NULL;
+
+				gp_babel_neigh_unref(nexthop->neigh);
+
+				free(nexthop);
+			}
+			else {
+				nexthop->metric_seqno.metric = GP_BABEL_INFINITY;
+				nexthop->last_update += GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10;
+			}
+		}
+		else if (gmrf_now(gmrf) > nexthop->last_update+GP_BABEL_UPDATE_REQUEST_TIMEOUT(nexthop->interval)*10 && announce->selected == nexthop) {
+			if (!nexthop->requested_update) {
+				gmrf_logf(gmrf, LOG_INFO, "announce about to expire, requesting update");
+				// gp_babel_send_announce_request(nexthop->neigh->iface, nexthop->neigh, announce->node, announce->type, announce->key, false);
+				nexthop->requested_update = true;
+			}
+		}
+	}
+}
+
+static gp_babel_nexthop_t* select_nexthop(gmrf_t *gmrf, const gp_babel_announce_t *announce) {
+	uint16_t ret_metric = GP_BABEL_INFINITY;
+	gp_babel_nexthop_t *ret = NULL;
+
+	gp_babel_nexthop_t *nexthop;
+	for (nexthop = announce->nexthops; nexthop; nexthop = nexthop->next) {
+		if (!nexthop->neigh) /* local */
+			return nexthop;
+
+		if (!gp_babel_is_feasible(announce, nexthop->metric_seqno))
+			continue;
+
+		uint32_t metric = nexthop->metric_seqno.metric + gp_babel_neigh_get_cost(gmrf, nexthop->neigh);
+
+		if (metric < ret_metric) {
+			ret = nexthop;
+			ret_metric = metric;
+		}
+	}
+
+	return ret;
+}
+
+gp_babel_metric_seqno_t get_metric(gmrf_t *gmrf, const gp_babel_announce_t *announce) {
+	if (announce->selected) {
+		uint32_t metric = announce->selected->metric_seqno.metric + gp_babel_neigh_get_cost(gmrf, announce->selected->neigh);
+
+		if (metric < GP_BABEL_INFINITY)
+			return (gp_babel_metric_seqno_t){metric, announce->selected->metric_seqno.seqno};
+	}
+
+	return (gp_babel_metric_seqno_t){GP_BABEL_INFINITY, 0};
+}
+
+void gp_babel_announce_update(gmrf_t *gmrf, gp_babel_announce_t *announce) {
+	maintain_nexthops(gmrf, announce);
+
+	announce->selected = select_nexthop(gmrf, announce);
+	announce->metric = get_metric(gmrf, announce);
+
+	//if (!announce->selected)
+	//	gp_babel_send_seqno_request_for(NULL, announce);
+
+	/* triggered updates */
+	/*int diff =  announce->metric.metric - announce->last_metric;
+
+	if (((announce->last_metric == GP_BABEL_INFINITY) != (announce->metric.metric == GP_BABEL_INFINITY))
+	    || diff <= -1024 || diff >= 384) {
+		gmrf_logf(gmrf, LOG_INFO, "announce metric has changed significantly, sending updates");
+		gp_babel_update_enqueue(&announce->node, announce->type, announce->key, NULL, announce->metric.metric == GP_BABEL_INFINITY);
+	} */
+}
+
+void gp_babel_announce_update_nexthop(gmrf_t *gmrf, gp_babel_announce_t *announce, gp_babel_nexthop_t *nexthop, gp_babel_metric_seqno_t ms, uint16_t interval) {
+	nexthop->metric_seqno = ms;
+	nexthop->interval = interval;
+	nexthop->requested_update = false;
+
+	if (ms.metric != GP_BABEL_INFINITY)
+		nexthop->last_update = gmrf_now(gmrf);
+
+	gp_babel_announce_update(gmrf, announce);
+}
diff --git a/src/babel.c b/src/babel.c
index 4177100..7e5e003 100644
--- a/src/babel.c
+++ b/src/babel.c
@@ -52,9 +52,7 @@ static void send_updates(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
 	}
 }
 
-static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
-	gmrf_schedule(gmrf, maintenance, NULL, GP_BABEL_MAINTENANCE_INTERVAL*10);
-
+static void maintain_neighbours(gmrf_t *gmrf, gmrf_context_t *ctx) {
 	gp_babel_iface_t *iface;
 	for (iface = ctx->interfaces; iface; iface = iface->next) {
 		gp_babel_neigh_t **cur, **next;
@@ -62,7 +60,7 @@ static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
 			gp_babel_neigh_t *neigh = *cur;
 			next = &neigh->next;
 
-			if (gp_babel_neigh_get_rxcost(gmrf, neigh) == 0xffff && gp_babel_neigh_get_txcost(gmrf, neigh) == 0xffff && !neigh->ref) {
+			if (gp_babel_neigh_get_rxcost(gmrf, neigh) == GP_BABEL_INFINITY && gp_babel_neigh_get_txcost(gmrf, neigh) == GP_BABEL_INFINITY && !neigh->ref) {
 				*cur = *next;
 				next = cur;
 				free(neigh);
@@ -79,12 +77,58 @@ static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
 	}
 }
 
+static void maintain_announces(gmrf_t *gmrf, gmrf_context_t *ctx) {
+	gp_babel_announce_t **cur, **next;
+	for (cur = &ctx->announces; *cur; cur = next) {
+		gp_babel_announce_t *announce = *cur;
+		next = &announce->next;
+
+		gp_babel_announce_update(gmrf, announce);
+
+		if (!announce->nexthops) {
+			*cur = *next;
+			next = cur;
+			gp_babel_announce_free(gmrf, ctx, announce);
+
+			continue;
+		}
+
+		gmrf_logf(gmrf, LOG_DEBUG, "node %04x%04x, type %04x, announce %04x (%u, seqno=%04x):",
+			  ntohl(*(uint32_t*)announce->node.id), ntohl(*(uint32_t*)(announce->node.id+4)),
+			  announce->type, announce->key, announce->metric.metric, announce->metric.seqno);
+
+		gp_babel_nexthop_t *nexthop;
+		for (nexthop = announce->nexthops; nexthop; nexthop = nexthop->next) {
+			gp_babel_neigh_t *neigh = nexthop->neigh;
+
+			if (!neigh) {
+				gmrf_logf(gmrf, LOG_DEBUG, "        local");
+				continue;
+			}
+
+			gmrf_logf(gmrf, LOG_DEBUG, "        nexthop: %02x:%02x:%02x:%02x:%02x:%02x:%02x:%02x[%s] (%u, seqno=%04x, cost=%u%s)",
+				  neigh->addr.d[0], neigh->addr.d[1], neigh->addr.d[2], neigh->addr.d[3],
+				  neigh->addr.d[4], neigh->addr.d[5], neigh->addr.d[6], neigh->addr.d[7],
+				  neigh->iface ? gmrf_iface_get_name(gmrf, neigh->iface->gmrf_iface) : NULL,
+				  nexthop->metric_seqno.metric, nexthop->metric_seqno.seqno, gp_babel_neigh_get_cost(gmrf, neigh),
+				  (nexthop == announce->selected) ? ", selected" : "");
+		}
+	}
+}
+
+static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
+	gmrf_schedule(gmrf, maintenance, NULL, GP_BABEL_MAINTENANCE_INTERVAL*10);
+
+	maintain_neighbours(gmrf, ctx);
+	maintain_announces(gmrf, ctx);
+}
+
 gmrf_context_t* gmrf_protocol_init(gmrf_t *gmrf) {
 	gmrf_logf(gmrf, LOG_INFO, "initalizing...");
 
 	gmrf_schedule(gmrf, send_hellos, NULL, GP_BABEL_HELLO_INTERVAL*10);
 	gmrf_schedule(gmrf, send_updates, NULL, GP_BABEL_UPDATE_INTERVAL*10);
-	gmrf_schedule(gmrf, maintenance, NULL, GP_BABEL_MAINTENANCE_INTERVAL*10);
+	gmrf_schedule(gmrf, maintenance, NULL, 0);
 
 	gmrf_context_t *ctx = calloc(1, sizeof(gmrf_context_t));
 	gmrf_random_bytes(gmrf, &ctx->self, sizeof(gp_babel_node_id_t));
@@ -94,6 +138,8 @@ gmrf_context_t* gmrf_protocol_init(gmrf_t *gmrf) {
 	announce->type = 1;
 	announce->key = 1337;
 
+	announce->nexthops = announce->selected = calloc(1, sizeof(gp_babel_nexthop_t));
+
 	return ctx;
 }
 
diff --git a/src/babel.h b/src/babel.h
index 3e9b3fd..52abfd5 100644
--- a/src/babel.h
+++ b/src/babel.h
@@ -41,6 +41,8 @@
 
 #define GP_BABEL_HELLO_TIMEOUT(interval) (16*(interval))
 #define GP_BABEL_IHU_TIMEOUT(interval) ((interval)*7/2)
+#define GP_BABEL_UPDATE_TIMEOUT(interval) ((interval)*7/2) /* 3.5 intervals */
+#define GP_BABEL_UPDATE_REQUEST_TIMEOUT(interval) ((interval)*13/4) /* 3.25 intervals */
 
 #define GP_BABEL_MAINTENANCE_INTERVAL GP_BABEL_HELLO_INTERVAL
 
@@ -169,9 +171,11 @@ void gp_babel_send_update(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_iface_t *i
 gp_babel_announce_t* gp_babel_announce_new(gmrf_t *gmrf, gmrf_context_t *ctx);
 gp_babel_announce_t* gp_babel_announce_find(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_node_id_t *node, uint16_t type, uint16_t key);
 gp_babel_announce_t* gp_babel_announce_get(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_node_id_t *node, uint16_t type, uint16_t key);
+void gp_babel_announce_update(gmrf_t *gmrf, gp_babel_announce_t *announce);
 void gp_babel_announce_free(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_announce_t *announce);
 
 gp_babel_nexthop_t* gp_babel_announce_nexthop_new(gp_babel_announce_t *announce, gp_babel_neigh_t *neigh);
 gp_babel_nexthop_t* gp_babel_announce_nexthop_find(const gp_babel_announce_t *announce, gp_babel_neigh_t *neigh);
+void gp_babel_announce_update_nexthop(gmrf_t *gmrf, gp_babel_announce_t *announce, gp_babel_nexthop_t *nexthop, gp_babel_metric_seqno_t ms, uint16_t interval);
 
 #endif /* _GMRF_PROTO_BABEL_BABEL_H_ */
diff --git a/src/neigh.c b/src/neigh.c
index bbef746..b89e284 100644
--- a/src/neigh.c
+++ b/src/neigh.c
@@ -40,7 +40,7 @@ gp_babel_neigh_t* gp_babel_neigh_get(gp_babel_iface_t *iface, const gmrf_addr_t
 		neigh->last_ihu = gmrf_time_unspec;
 		neigh->addr = *addr;
 
-		neigh->txcost = 0xffff;
+		neigh->txcost = GP_BABEL_INFINITY;
 	}
 
 	return neigh;
@@ -66,25 +66,25 @@ void gp_babel_neigh_unref(gp_babel_neigh_t *neigh) {
 
 uint16_t gp_babel_neigh_get_rxcost(gmrf_t *gmrf, const gp_babel_neigh_t *neigh) {
 	if (!neigh->hello_log || !neigh->hello_interval || !neigh->iface)
-		return 0xffff;
+		return GP_BABEL_INFINITY;
 
 	int timediff = (gmrf_now(gmrf) - neigh->last_hello)/10;
 	int shift = (timediff - neigh->hello_interval/2)/neigh->hello_interval;
 
 	if (shift >= 16)
-		return 0xffff;
+		return GP_BABEL_INFINITY;
 
 	int received = __builtin_popcount((neigh->hello_log << shift) & 0xffff);
 
 	if (received == 0)
-		return 0xffff;
+		return GP_BABEL_INFINITY;
 	else
 		return (0x1000/received);
 }
 
 uint16_t gp_babel_neigh_get_txcost(gmrf_t *gmrf, const gp_babel_neigh_t *neigh) {
 	if ((gmrf_now(gmrf) - neigh->last_ihu)/10 > GP_BABEL_IHU_TIMEOUT(neigh->ihu_interval) || !neigh->iface)
-		return 0xffff;
+		return GP_BABEL_INFINITY;
 	else
 		return neigh->txcost;
 }
@@ -99,8 +99,8 @@ uint16_t gp_babel_neigh_get_cost(gmrf_t *gmrf, const gp_babel_neigh_t *neigh) {
 
 	uint32_t cost = (txcost * gp_babel_neigh_get_rxcost(gmrf, neigh)) >> 8;
 
-	if (cost > 0xffff)
-		return 0xffff;
+	if (cost > GP_BABEL_INFINITY)
+		return GP_BABEL_INFINITY;
 	else
 		return cost;
 }
diff --git a/src/send.c b/src/send.c
index f566fee..b35d009 100644
--- a/src/send.c
+++ b/src/send.c
@@ -163,14 +163,14 @@ void gp_babel_send_update(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_iface_t *i
 	gp_babel_packet_buf_t *buf = gp_babel_packet_alloca(GP_BABEL_PACKET_MAX);
 
 	if (announce) {
-		add_update(buf, NULL, announce, with_data, iface || neigh);
+		add_update(buf, NULL, announce, with_data, neigh);
 	}
 	else {
 		gp_babel_node_id_t node_id = gp_babel_node_id_unspec;
 
 		gp_babel_announce_t *a;
 		for (a = ctx->announces; a; a = a->next) {
-			if (!add_update(buf, &node_id, a, with_data, iface || neigh)) {
+			if (!add_update(buf, &node_id, a, with_data, neigh)) {
 				if (neigh)
 					send_neigh(gmrf, neigh, &buf->packet);
 				else
@@ -179,7 +179,7 @@ void gp_babel_send_update(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_iface_t *i
 				node_id = gp_babel_node_id_unspec;
 				buf->packet.len = 0;
 
-				if (!add_update(buf, &node_id, a, with_data, iface || neigh)) {
+				if (!add_update(buf, &node_id, a, with_data, neigh)) {
 					gmrf_logf(gmrf, LOG_ERR, "add_update failed");
 					return;
 				}
diff --git a/src/tlv_types.c b/src/tlv_types.c
index b860784..9b4c215 100644
--- a/src/tlv_types.c
+++ b/src/tlv_types.c
@@ -81,7 +81,7 @@ static void handle_tlv_hello(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_t
 		if (abs((int16_t)(seqno - seqexp)) > 16) {
 			gmrf_logf(gmrf, LOG_INFO, "neighbour was reset.");
 			neigh->hello_log = 0;
-			neigh->txcost = 0xffff;
+			neigh->txcost = GP_BABEL_INFINITY;
 		}
 		else {
 			int16_t seqdiff = seqno - neigh->last_seqno;
@@ -212,7 +212,7 @@ static void handle_tlv_update(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_
 
 	gmrf_logf(gmrf, LOG_DEBUG, "the update was accepted.");
 
-	//gp_babel_announce_update_nexthop(announce, nexthop, ms, ntohs(tlv_update->interval));
+	gp_babel_announce_update_nexthop(gmrf, announce, nexthop, ms, ntohs(tlv_update->interval));
 }
 
 static void handle_tlv(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_tlv_type_t type, const void *data, size_t len, void *arg) {