X-Git-Url: http://git.meshlink.io/?a=blobdiff_plain;f=src%2Fgraph.c;h=34af237e0b228ed8547b6ee6de460bd854614cee;hb=cbcb7c1e64318a80dd72e5b09b45ab16e56e47de;hp=396e35a3e68d2e9373a6dde4a753402ad7d4228f;hpb=57991e264202ad83e2c1b663777b358bf5573652;p=meshlink diff --git a/src/graph.c b/src/graph.c index 396e35a3..34af237e 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,7 +1,6 @@ /* graph.c -- graph algorithms - Copyright (C) 2001-2013 Guus Sliepen , - 2001-2005 Ivo Timmermans + Copyright (C) 2014 Guus Sliepen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -45,17 +44,14 @@ #include "system.h" #include "connection.h" -#include "device.h" #include "edge.h" #include "graph.h" #include "list.h" #include "logger.h" -#include "names.h" +#include "meshlink_internal.h" #include "netutl.h" #include "node.h" #include "protocol.h" -#include "script.h" -#include "subnet.h" #include "utils.h" #include "xalloc.h" #include "graph.h" @@ -65,22 +61,22 @@ Please note that sorting on weight is already done by add_edge(). */ -static void mst_kruskal(void) { +static void mst_kruskal(meshlink_handle_t *mesh) { /* Clear MST status on connections */ - for list_each(connection_t, c, connection_list) + for list_each(connection_t, c, mesh->connections) c->status.mst = false; logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Running Kruskal's algorithm:"); /* Clear visited status on nodes */ - for splay_each(node_t, n, node_tree) + for splay_each(node_t, n, mesh->nodes) n->status.visited = false; /* Starting point */ - for splay_each(edge_t, e, edge_weight_tree) { + for splay_each(edge_t, e, mesh->edges) { if(e->from->status.reachable) { e->from->status.visited = true; break; @@ -91,7 +87,7 @@ static void mst_kruskal(void) { bool skipped = false; - for splay_each(edge_t, e, edge_weight_tree) { + for splay_each(edge_t, e, mesh->edges) { if(!e->reverse || (e->from->status.visited == e->to->status.visited)) { skipped = true; continue; @@ -110,7 +106,7 @@ static void mst_kruskal(void) { if(skipped) { skipped = false; - next = edge_weight_tree->head; + next = mesh->edges->head; } } } @@ -119,26 +115,26 @@ static void mst_kruskal(void) { Running time: O(E) */ -static void sssp_bfs(void) { +static void sssp_bfs(meshlink_handle_t *mesh) { list_t *todo_list = list_alloc(NULL); /* Clear visited status on nodes */ - for splay_each(node_t, n, node_tree) { + for splay_each(node_t, n, mesh->nodes) { n->status.visited = false; n->status.indirect = true; n->distance = -1; } - /* Begin with myself */ + /* Begin with mesh->self */ - myself->status.visited = true; - myself->status.indirect = false; - myself->nexthop = myself; - myself->prevedge = NULL; - myself->via = myself; - myself->distance = 0; - list_insert_head(todo_list, myself); + mesh->self->status.visited = true; + mesh->self->status.indirect = false; + mesh->self->nexthop = mesh->self; + mesh->self->prevedge = NULL; + mesh->self->via = mesh->self; + mesh->self->distance = 0; + list_insert_head(todo_list, mesh->self); /* Loop while todo_list is filled */ @@ -178,14 +174,14 @@ static void sssp_bfs(void) { e->to->status.visited = true; e->to->status.indirect = indirect; - e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; + e->to->nexthop = (n->nexthop == mesh->self) ? e->to : n->nexthop; e->to->prevedge = e; e->to->via = indirect ? n->via : e->to; e->to->options = e->options; e->to->distance = n->distance + 1; if(!e->to->status.reachable || (e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)) - update_node_udp(e->to, &e->address); + update_node_udp(mesh, e->to, &e->address); list_insert_tail(todo_list, e->to); } @@ -197,13 +193,13 @@ static void sssp_bfs(void) { list_free(todo_list); } -static void check_reachability(void) { +static void check_reachability(meshlink_handle_t *mesh) { /* Check reachability status. */ - for splay_each(node_t, n, node_tree) { + for splay_each(node_t, n, mesh->nodes) { if(n->status.visited != n->status.reachable) { n->status.reachable = !n->status.reachable; - n->last_state_change = now.tv_sec; + n->last_state_change = mesh->loop.now.tv_sec; if(n->status.reachable) { logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became reachable", @@ -213,16 +209,11 @@ static void check_reachability(void) { n->name, n->hostname); } - if(experimental && OPTION_VERSION(n->options) >= 2) - n->status.sptps = true; - /* TODO: only clear status.validkey if node is unreachable? */ n->status.validkey = false; - if(n->status.sptps) { - sptps_stop(&n->sptps); - n->status.waitingforkey = false; - } + sptps_stop(&n->sptps); + n->status.waitingforkey = false; n->last_req_key = 0; n->status.udp_confirmed = false; @@ -230,55 +221,25 @@ static void check_reachability(void) { n->minmtu = 0; n->mtuprobes = 0; - timeout_del(&n->mtutimeout); - - char *name; - char *address; - char *port; - char *envp[8] = {NULL}; - - xasprintf(&envp[0], "NETNAME=%s", netname ? : ""); - xasprintf(&envp[1], "DEVICE=%s", device ? : ""); - xasprintf(&envp[2], "INTERFACE=%s", iface ? : ""); - xasprintf(&envp[3], "NODE=%s", n->name); - sockaddr2str(&n->address, &address, &port); - xasprintf(&envp[4], "REMOTEADDRESS=%s", address); - xasprintf(&envp[5], "REMOTEPORT=%s", port); - xasprintf(&envp[6], "NAME=%s", myself->name); - - execute_script(n->status.reachable ? "host-up" : "host-down", envp); - - xasprintf(&name, n->status.reachable ? "hosts/%s-up" : "hosts/%s-down", n->name); - execute_script(name, envp); - - free(name); - free(address); - free(port); - - for(int i = 0; i < 7; i++) - free(envp[i]); + timeout_del(&mesh->loop, &n->mtutimeout); - subnet_update(n, NULL, n->status.reachable); + if(mesh->node_status_cb) + mesh->node_status_cb(mesh, (meshlink_node_t *)n, n->status.reachable); if(!n->status.reachable) { - update_node_udp(n, NULL); + update_node_udp(mesh, n, NULL); memset(&n->status, 0, sizeof n->status); n->options = 0; } else if(n->connection) { - if(n->status.sptps) { - if(n->connection->outgoing) - send_req_key(n); - } else { - send_ans_key(n); - } + if(n->connection->outgoing) + send_req_key(mesh, n); } } } } -void graph(void) { - subnet_cache_flush(); - sssp_bfs(); - check_reachability(); - mst_kruskal(); +void graph(meshlink_handle_t *mesh) { + sssp_bfs(mesh); + check_reachability(mesh); + mst_kruskal(mesh); }