X-Git-Url: http://git.meshlink.io/?p=meshlink;a=blobdiff_plain;f=src%2Fgraph.c;h=b0e0b77a198a408cd2d88aecb2c4debde09022d3;hp=86b62a51189af649eef68e1b4d631925c6e17976;hb=963c5055505f2fc117cd5efa06eaa02c9b2bf85d;hpb=0b8b23e0dd7219344543f135ca0aeba8a4a42d48 diff --git a/src/graph.c b/src/graph.c index 86b62a51..b0e0b77a 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,7 +1,6 @@ /* graph.c -- graph algorithms - Copyright (C) 2001-2012 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 @@ -37,111 +36,69 @@ For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a simple breadth-first search is presented here. - The SSSP algorithm will also be used to determine whether nodes are directly, - indirectly or not reachable from the source. It will also set the correct - destination address and port of a node if possible. + The SSSP algorithm will also be used to determine whether nodes are + reachable from the source. It will also set the correct destination address + and port of a node if possible. */ #include "system.h" -#include "config.h" #include "connection.h" -#include "device.h" #include "edge.h" #include "graph.h" #include "list.h" #include "logger.h" +#include "meshlink_internal.h" #include "netutl.h" #include "node.h" -#include "process.h" #include "protocol.h" -#include "subnet.h" #include "utils.h" #include "xalloc.h" #include "graph.h" -/* Implementation of Kruskal's algorithm. - Running time: O(E) - Please note that sorting on weight is already done by add_edge(). -*/ - -static void mst_kruskal(void) { - /* Clear MST status on connections */ - - for list_each(connection_t, c, connection_list) - 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) - n->status.visited = false; - - /* Add safe edges */ - - for splay_each(edge_t, e, edge_weight_tree) { - if(!e->reverse || (e->from->status.visited && e->to->status.visited)) - 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(DEBUG_SCARY_THINGS, LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, - e->to->name, e->weight); - } -} - /* Implementation of a simple breadth-first search algorithm. 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 = mesh->threadstarted; + mesh->self->nexthop = mesh->self; + mesh->self->prevedge = NULL; + mesh->self->distance = 0; + list_insert_head(todo_list, mesh->self); /* Loop while todo_list is filled */ - for list_each(node_t, n, todo_list) { /* "n" is the node from which we start */ - logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Examining edges from %s", n->name); + for list_each(node_t, n, todo_list) { /* "n" is the node from which we start */ + logger(mesh, MESHLINK_DEBUG, " Examining edges from %s", n->name); - if(n->distance < 0) + if(n->distance < 0) { abort(); + } - for splay_each(edge_t, e, n->edge_tree) { /* "e" is the edge connected to "from" */ - if(!e->reverse) + for splay_each(edge_t, e, n->edge_tree) { /* "e" is the edge connected to "from" */ + if(!e->reverse) { continue; + } /* Situation: - / - / + / + / ----->(n)---e-->(e->to) - \ - \ + \ + \ Where e is an edge, (n) and (e->to) are nodes. n->address is set to the e->address of the edge left of n to n. @@ -152,23 +109,19 @@ static void sssp_bfs(void) { of nodes behind it. */ - bool indirect = n->status.indirect || e->options & OPTION_INDIRECT; - if(e->to->status.visited - && (!e->to->status.indirect || indirect) - && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->weight)) + && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->weight)) { continue; + } 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); + if(!e->to->status.reachable || (e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)) { + update_node_udp(mesh, e->to, &e->address); + } list_insert_tail(todo_list, e->to); } @@ -180,86 +133,113 @@ 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) { - if(n->status.visited != n->status.reachable) { - n->status.reachable = !n->status.reachable; - n->last_state_change = time(NULL); - - if(n->status.reachable) { - logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became reachable", - n->name, n->hostname); - } else { - logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became unreachable", - n->name, n->hostname); - } + int reachable = -1; /* Don't count ourself */ - if(experimental && OPTION_VERSION(n->options) >= 2) - n->status.sptps = true; + for splay_each(node_t, n, mesh->nodes) { + if(n->status.visited) { + reachable++; + } - /* TODO: only clear status.validkey if node is unreachable? */ + /* Check for nodes that have changed session_id */ + if(n->status.visited && n->prevedge && n->prevedge->reverse->session_id != n->session_id) { + n->session_id = n->prevedge->reverse->session_id; - n->status.validkey = false; - if(n->status.sptps) { + if(n->utcp) { + utcp_abort_all_connections(n->utcp); + } + + if(n->status.visited == n->status.reachable) { + /* This session replaces the previous one without changing reachability status. + * We still need to reset the UDP SPTPS state. + */ + n->status.validkey = false; sptps_stop(&n->sptps); n->status.waitingforkey = false; + n->last_req_key = 0; + + n->status.udp_confirmed = false; + n->maxmtu = MTU; + n->minmtu = 0; + n->mtuprobes = 0; + + timeout_del(&mesh->loop, &n->mtutimeout); } - n->last_req_key = 0; + } - n->maxmtu = MTU; - n->minmtu = 0; - n->mtuprobes = 0; + if(n->status.visited != n->status.reachable) { + n->status.reachable = !n->status.reachable; + n->status.dirty = true; - if(timeout_initialized(&n->mtuevent)) - event_del(&n->mtuevent); + if(!n->status.blacklisted) { + if(n->status.reachable) { + logger(mesh, MESHLINK_DEBUG, "Node %s became reachable", n->name); + bool first_time_reachable = !n->last_reachable; + n->last_reachable = time(NULL); - char *name; - char *address; - char *port; - char *envp[7]; + if(first_time_reachable) { + if(!node_write_config(mesh, n)) { + logger(mesh, MESHLINK_WARNING, "Could not write host config file for node %s!\n", n->name); - 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); - envp[6] = NULL; + } + } + } else { + logger(mesh, MESHLINK_DEBUG, "Node %s became unreachable", n->name); + n->last_unreachable = time(NULL); + } + } - execute_script(n->status.reachable ? "host-up" : "host-down", envp); + /* TODO: only clear status.validkey if node is unreachable? */ - xasprintf(&name, n->status.reachable ? "hosts/%s-up" : "hosts/%s-down", n->name); - execute_script(name, envp); + n->status.validkey = false; + sptps_stop(&n->sptps); + n->status.waitingforkey = false; + n->last_req_key = 0; - free(name); - free(address); - free(port); + n->status.udp_confirmed = false; + n->maxmtu = MTU; + n->minmtu = 0; + n->mtuprobes = 0; - for(int i = 0; i < 6; i++) - free(envp[i]); + timeout_del(&mesh->loop, &n->mtutimeout); - subnet_update(n, NULL, n->status.reachable); + if(!n->status.blacklisted) { + update_node_status(mesh, n); + } if(!n->status.reachable) { - update_node_udp(n, NULL); + update_node_udp(mesh, n, NULL); + n->status.broadcast = false; } else if(n->connection) { - if(n->status.sptps) { - if(n->connection->outgoing) - send_req_key(n); - } else { - send_ans_key(n); + if(n->connection->status.initiator) { + send_req_key(mesh, n); } } + + if(n->utcp) { + utcp_offline(n->utcp, !n->status.reachable); + } } } + + if(mesh->reachable != reachable) { + if(!reachable) { + mesh->last_unreachable = mesh->loop.now.tv_sec; + + if(mesh->threadstarted) { + timeout_set(&mesh->loop, &mesh->periodictimer, &(struct timespec) { + 0, prng(mesh, TIMER_FUDGE) + }); + } + } + + mesh->reachable = reachable; + } } -void graph(void) { - subnet_cache_flush(); - sssp_bfs(); - check_reachability(); - mst_kruskal(); +void graph(meshlink_handle_t *mesh) { + sssp_bfs(mesh); + check_reachability(mesh); }