1 files changed, 199 insertions, 0 deletions
diff --git a/src/route.c b/src/route.c
new file mode 100644
index 0000000..91b4944
--- /dev/null
+++ b/src/route.c
@@ -0,0 +1,199 @@
+/*
+  Copyright (c) 2013, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+
+#include "babel.h"
+#include "neigh.h"
+
+#include <stdlib.h>
+
+
+gp_babel_route_t* gp_babel_route_new(gmrf_context_t *ctx) {
+	gp_babel_route_t *a = calloc(1, sizeof(gp_babel_route_t));
+
+	a->metric.metric = a->feasibility_distance.metric = a->last_metric = GP_BABEL_INFINITY;
+
+	a->next = ctx->routes;
+	ctx->routes = a;
+
+	return a;
+}
+
+gp_babel_route_t* gp_babel_route_find(gmrf_context_t *ctx, const gp_babel_node_id_t *node) {
+	gp_babel_route_t *route;
+	for (route = ctx->routes; route; route = route->next) {
+		if (gp_babel_node_id_equal(&route->node, node))
+			return route;
+	}
+
+	return NULL;
+}
+
+gp_babel_route_t* gp_babel_route_get(gmrf_context_t *ctx, const gp_babel_node_id_t *node) {
+	gp_babel_route_t *route = gp_babel_route_find(ctx, node);
+
+	if (!route) {
+		route = gp_babel_route_new(ctx);
+		route->node = *node;
+	}
+
+	return route;
+}
+
+void gp_babel_route_free(gmrf_context_t *ctx, gp_babel_route_t *route) {
+	free(route);
+}
+
+gp_babel_nexthop_t* gp_babel_route_nexthop_find(const gp_babel_route_t *route, gp_babel_neigh_t *neigh) {
+	gp_babel_nexthop_t *nexthop;
+	for (nexthop = route->nexthops; nexthop; nexthop = nexthop->next) {
+		if (nexthop->neigh == neigh)
+			return nexthop;
+	}
+
+	return NULL;
+}
+
+gp_babel_nexthop_t* gp_babel_route_nexthop_new(gp_babel_route_t *route, gp_babel_neigh_t *neigh) {
+	gp_babel_nexthop_t *nexthop = calloc(1, sizeof(gp_babel_nexthop_t));
+	nexthop->neigh = neigh;
+
+	nexthop->next = route->nexthops;
+	route->nexthops = nexthop;
+
+	gp_babel_neigh_ref(neigh);
+
+	return nexthop;
+}
+
+static void maintain_nexthops(gmrf_context_t *ctx, gp_babel_route_t *route) {
+	gp_babel_nexthop_t **cur, **next;
+	for (cur = &route->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(ctx->gmrf);
+				nexthop->last_update += GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10;
+			}
+
+			continue;
+		}
+
+		if (gmrf_now(ctx->gmrf) > nexthop->last_update+GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10) {
+			if (nexthop->metric_seqno.metric == GP_BABEL_INFINITY) {
+				*cur = *next;
+				next = cur;
+
+				if (route->selected == nexthop)
+					route->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(ctx->gmrf) > nexthop->last_update+GP_BABEL_UPDATE_REQUEST_TIMEOUT(nexthop->interval)*10 && route->selected == nexthop) {
+			if (!nexthop->requested_update) {
+				gmrf_logf(ctx->gmrf, LOG_INFO, "route about to expire, requesting update");
+				gp_babel_send_route_request(ctx, NULL, nexthop->neigh, &route->node);
+				nexthop->requested_update = true;
+			}
+		}
+	}
+}
+
+static gp_babel_nexthop_t* select_nexthop(gmrf_context_t *ctx, const gp_babel_route_t *route) {
+	uint16_t ret_metric = GP_BABEL_INFINITY;
+	gp_babel_nexthop_t *ret = NULL;
+
+	gp_babel_nexthop_t *nexthop;
+	for (nexthop = route->nexthops; nexthop; nexthop = nexthop->next) {
+		if (!nexthop->neigh) /* local */
+			return nexthop;
+
+		if (!gp_babel_is_feasible(route, nexthop->metric_seqno))
+			continue;
+
+		uint32_t metric = nexthop->metric_seqno.metric + gp_babel_neigh_get_cost(ctx, nexthop->neigh);
+
+		if (metric < ret_metric) {
+			ret = nexthop;
+			ret_metric = metric;
+		}
+	}
+
+	return ret;
+}
+
+gp_babel_metric_seqno_t get_metric(gmrf_context_t *ctx, const gp_babel_route_t *route) {
+	if (route->selected) {
+		uint32_t metric = route->selected->metric_seqno.metric + gp_babel_neigh_get_cost(ctx, route->selected->neigh);
+
+		if (metric < GP_BABEL_INFINITY)
+			return (gp_babel_metric_seqno_t){metric, route->selected->metric_seqno.seqno};
+	}
+
+	return (gp_babel_metric_seqno_t){GP_BABEL_INFINITY, 0};
+}
+
+void gp_babel_route_update(gmrf_context_t *ctx, gp_babel_route_t *route) {
+	maintain_nexthops(ctx, route);
+
+	route->selected = select_nexthop(ctx, route);
+	route->metric = get_metric(ctx, route);
+
+	if (!route->selected)
+		gp_babel_send_seqno_request_for(ctx, NULL, route);
+
+	/* triggered updates */
+	/*int diff =  route->metric.metric - route->last_metric;
+
+	if (((route->last_metric == GP_BABEL_INFINITY) != (route->metric.metric == GP_BABEL_INFINITY))
+	    || diff <= -1024 || diff >= 384) {
+		gmrf_logf(gmrf, LOG_INFO, "route metric has changed significantly, sending updates");
+		gp_babel_update_enqueue(&route->node, route->type, route->key, NULL, route->metric.metric == GP_BABEL_INFINITY);
+	} */
+}
+
+void gp_babel_route_update_nexthop(gmrf_context_t *ctx, gp_babel_route_t *route, 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(ctx->gmrf);
+
+	gp_babel_route_update(ctx, route);
+}