X-Git-Url: http://git.meshlink.io/?p=meshlink;a=blobdiff_plain;f=src%2Fgraph.c;h=9955ea41644721a208041de60860329158998e04;hp=caf33f5e064921ad66f87e1f2bd0e55b0be244f7;hb=8d4ac42ceb67a93fc1e5c0d045819597c5da47d0;hpb=76c7550c8ab0e9c0ee14a9c396baa008cfb9bc42 diff --git a/src/graph.c b/src/graph.c index caf33f5e..9955ea41 100644 --- a/src/graph.c +++ b/src/graph.c @@ -36,9 +36,9 @@ 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" @@ -56,61 +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) */ @@ -122,17 +67,14 @@ static void sssp_bfs(meshlink_handle_t *mesh) { for splay_each(node_t, n, mesh->nodes) { n->status.visited = false; - n->status.indirect = true; n->distance = -1; } /* Begin with mesh->self */ 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); @@ -141,12 +83,14 @@ static void sssp_bfs(meshlink_handle_t *mesh) { 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) + if(!e->reverse) { continue; + } /* Situation: @@ -165,23 +109,19 @@ static void sssp_bfs(meshlink_handle_t *mesh) { 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 == 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)) + 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); } @@ -197,16 +137,23 @@ static void check_reachability(meshlink_handle_t *mesh) { /* Check reachability status. */ for splay_each(node_t, n, mesh->nodes) { + /* 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; + + if(n->utcp) { + utcp_abort_all_connections(n->utcp); + } + } + if(n->status.visited != n->status.reachable) { n->status.reachable = !n->status.reachable; n->last_state_change = mesh->loop.now.tv_sec; if(n->status.reachable) { - logger(mesh, MESHLINK_DEBUG, "Node %s (%s) became reachable", - n->name, n->hostname); + logger(mesh, MESHLINK_DEBUG, "Node %s became reachable", n->name); } else { - logger(mesh, MESHLINK_DEBUG, "Node %s (%s) became unreachable", - n->name, n->hostname); + logger(mesh, MESHLINK_DEBUG, "Node %s became unreachable", n->name); } /* TODO: only clear status.validkey if node is unreachable? */ @@ -223,15 +170,21 @@ static void check_reachability(meshlink_handle_t *mesh) { timeout_del(&mesh->loop, &n->mtutimeout); - update_node_status(mesh, n); + if(!n->status.blacklisted) { + update_node_status(mesh, n); + } if(!n->status.reachable) { update_node_udp(mesh, n, NULL); - memset(&n->status, 0, sizeof(n)->status); - n->options = 0; + n->status.broadcast = false; } else if(n->connection) { - if(n->connection->outgoing) + if(n->connection->status.initiator) { send_req_key(mesh, n); + } + } + + if(n->utcp) { + utcp_offline(n->utcp, !n->status.reachable); } } } @@ -240,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); }