X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fgraph.c;h=3cc99c65606c2409814f0715d36586d9f211f506;hp=5a0aab0ba7bd04979198492ef7ab3854b251484c;hb=ff306f0cdaedb50de1472e7c1fb55de922a6ca60;hpb=108b238915c5f58b3d94ab433dc5d04e064c2b11 diff --git a/src/graph.c b/src/graph.c index 5a0aab0b..3cc99c65 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,6 +1,6 @@ /* graph.c -- graph algorithms - Copyright (C) 2001-2009 Guus Sliepen , + Copyright (C) 2001-2012 Guus Sliepen , 2001-2005 Ivo Timmermans This program is free software; you can redistribute it and/or modify @@ -44,51 +44,49 @@ #include "system.h" -#include "splay_tree.h" #include "config.h" #include "connection.h" #include "device.h" #include "edge.h" +#include "graph.h" +#include "list.h" #include "logger.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(). */ -void mst_kruskal(void) { - splay_node_t *node, *next; - edge_t *e; - node_t *n; - connection_t *c; - +static void mst_kruskal(void) { /* Clear MST status on connections */ - for(node = connection_tree->head; node; node = node->next) { - c = node->data; + for(list_node_t *node = connection_list->head; node; node = node->next) { + connection_t *c = node->data; c->status.mst = false; } - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:"); + logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Running Kruskal's algorithm:"); /* Clear visited status on nodes */ - for(node = node_tree->head; node; node = node->next) { - n = node->data; + for(splay_node_t *node = node_tree->head; node; node = node->next) { + node_t *n = node->data; n->status.visited = false; } /* Add safe edges */ - for(node = edge_weight_tree->head; node; node = next) { + for(splay_node_t *node = edge_weight_tree->head, *next; node; node = next) { next = node->next; - e = node->data; + edge_t *e = node->data; if(!e->reverse || (e->from->status.visited && e->to->status.visited)) continue; @@ -102,140 +100,16 @@ void mst_kruskal(void) { if(e->reverse->connection) e->reverse->connection->status.mst = true; - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, + logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight); } } -/* Implementation of Dijkstra's algorithm. - Running time: O(N^2) -*/ - -void sssp_dijkstra(void) { - splay_node_t *node, *to; - edge_t *e; - node_t *n, *m; - list_t *todo_list; - list_node_t *lnode, *nnode; - bool indirect; - - todo_list = list_alloc(NULL); - - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Dijkstra's algorithm:"); - - /* Clear visited status on nodes */ - - for(node = node_tree->head; node; node = node->next) { - n = node->data; - n->status.visited = false; - n->status.indirect = true; - n->distance = -1; - } - - /* Begin with myself */ - - myself->status.indirect = false; - myself->nexthop = myself; - myself->via = myself; - myself->distance = 0; - list_insert_head(todo_list, myself); - - /* Loop while todo_list is filled */ - - while(todo_list->head) { - n = NULL; - nnode = NULL; - - /* Select node from todo_list with smallest distance */ - - for(lnode = todo_list->head; lnode; lnode = lnode->next) { - m = lnode->data; - if(!n || m->status.indirect < n->status.indirect || m->distance < n->distance) { - n = m; - nnode = lnode; - } - } - - /* Mark this node as visited and remove it from the todo_list */ - - n->status.visited = true; - list_unlink_node(todo_list, nnode); - - /* Update distance of neighbours and add them to the todo_list */ - - for(to = n->edge_tree->head; to; to = to->next) { /* "to" is the edge connected to "from" */ - e = to->data; - - if(e->to->status.visited || !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. - We are currently examining the edge e right of n from n: - - - If e->reverse->address != n->address, then e->to is probably - not reachable for the nodes left of n. We do as if the indirectdata - flag is set on edge e. - - If edge e provides for better reachability of e->to, update e->to. - */ - - if(e->to->distance < 0) - list_insert_tail(todo_list, e->to); - - indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address)); - - if(e->to->distance >= 0 && (!e->to->status.indirect || indirect) && e->to->distance <= n->distance + e->weight) - continue; - - e->to->distance = n->distance + e->weight; - e->to->status.indirect = indirect; - e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; - e->to->via = indirect ? n->via : e->to; - e->to->options = e->options; - - if(sockaddrcmp(&e->to->address, &e->address)) { - node = splay_unlink(node_udp_tree, e->to); - sockaddrfree(&e->to->address); - sockaddrcpy(&e->to->address, &e->address); - - if(e->to->hostname) - free(e->to->hostname); - - e->to->hostname = sockaddr2hostname(&e->to->address); - - if(node) - splay_insert_node(node_udp_tree, node); - - if(e->to->options & OPTION_PMTU_DISCOVERY) { - e->to->mtuprobes = 0; - e->to->minmtu = 0; - e->to->maxmtu = MTU; - if(e->to->status.validkey) - send_mtu_probe(e->to); - } - } - - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Updating edge %s - %s weight %d distance %d", e->from->name, - e->to->name, e->weight, e->to->distance); - } - } - - list_free(todo_list); -} - /* Implementation of a simple breadth-first search algorithm. Running time: O(E) */ -void sssp_bfs(void) { +static void sssp_bfs(void) { splay_node_t *node, *to; edge_t *e; node_t *n; @@ -251,6 +125,7 @@ void sssp_bfs(void) { n = node->data; n->status.visited = false; n->status.indirect = true; + n->distance = -1; } /* Begin with myself */ @@ -258,13 +133,17 @@ void sssp_bfs(void) { 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); /* Loop while todo_list is filled */ for(from = todo_list->head; from; from = todonext) { /* "from" is the node from which we start */ n = from->data; + if(n->distance < 0) + abort(); for(to = n->edge_tree->head; to; to = to->next) { /* "to" is the edge connected to "from" */ e = to->data; @@ -284,28 +163,28 @@ void sssp_bfs(void) { n->address is set to the e->address of the edge left of n to n. We are currently examining the edge e right of n from n: - - If e->reverse->address != n->address, then e->to is probably - not reachable for the nodes left of n. We do as if the indirectdata - flag is set on edge e. - If edge e provides for better reachability of e->to, update e->to and (re)add it to the todo_list to (re)examine the reachability of nodes behind it. */ - indirect = n->status.indirect || e->options & OPTION_INDIRECT - || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address)); + indirect = n->status.indirect || e->options & OPTION_INDIRECT; if(e->to->status.visited - && (!e->to->status.indirect || indirect)) + && (!e->to->status.indirect || indirect) + && (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->prevedge = e; e->to->via = indirect ? n->via : e->to; e->to->options = e->options; + e->to->distance = n->distance + 1; - if(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(e->to, &e->address); list_insert_tail(todo_list, e->to); @@ -318,7 +197,7 @@ void sssp_bfs(void) { list_free(todo_list); } -void check_reachability() { +static void check_reachability(void) { splay_node_t *node, *next; node_t *n; char *name; @@ -334,25 +213,34 @@ void check_reachability() { if(n->status.visited != n->status.reachable) { n->status.reachable = !n->status.reachable; + n->last_state_change = time(NULL); if(n->status.reachable) { - ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable", + logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became reachable", n->name, n->hostname); } else { - ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable", + logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became unreachable", 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; - n->status.waitingforkey = false; + if(n->status.sptps) { + sptps_stop(&n->sptps); + n->status.waitingforkey = false; + } + n->last_req_key = 0; n->maxmtu = MTU; n->minmtu = 0; n->mtuprobes = 0; - event_del(&n->mtuevent); + if(timeout_initialized(&n->mtuevent)) + event_del(&n->mtuevent); xasprintf(&envp[0], "NETNAME=%s", netname ? : ""); xasprintf(&envp[1], "DEVICE=%s", device ? : ""); @@ -378,49 +266,24 @@ void check_reachability() { free(envp[i]); subnet_update(n, NULL, n->status.reachable); - } - } -} - -/* Dump nodes and edges to a graphviz file. - - The file can be converted to an image with - dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true -*/ - -int dump_graph(struct evbuffer *out) { - splay_node_t *node; - node_t *n; - edge_t *e; - if(evbuffer_add_printf(out, "digraph {\n") == -1) - return errno; - - /* dump all nodes first */ - for(node = node_tree->head; node; node = node->next) { - n = node->data; - if(evbuffer_add_printf(out, " %s [label = \"%s\"];\n", - n->name, n->name) == -1) - return errno; - } - - /* now dump all edges */ - for(node = edge_weight_tree->head; node; node = node->next) { - e = node->data; - if(evbuffer_add_printf(out, " %s -> %s;\n", - e->from->name, e->to->name) == -1) - return errno; + if(!n->status.reachable) { + update_node_udp(n, NULL); + } else if(n->connection) { + if(n->status.sptps) { + if(n->connection->outgoing) + send_req_key(n); + } else { + send_ans_key(n); + } + } + } } - - if(evbuffer_add_printf(out, "}\n") == -1) - return errno; - - return 0; } void graph(void) { - subnet_cache_flush(); - sssp_dijkstra(); + subnet_cache_flush(); + sssp_bfs(); check_reachability(); mst_kruskal(); }