From: Guus Sliepen Date: Mon, 6 Jun 2011 18:42:15 +0000 (+0200) Subject: Merge branch 'master' of git://tinc-vpn.org/tinc into 1.1 X-Git-Tag: release-1.1pre1~11 X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=commitdiff_plain;h=33f241d97852d7a171f1aaf1bda7f66356ff889e Merge branch 'master' of git://tinc-vpn.org/tinc into 1.1 Conflicts: NEWS configure.in doc/tincd.8.in lib/pidfile.c lib/pidfile.h lib/xalloc.h lib/xmalloc.c src/conf.c src/conf.h src/connection.c src/connection.h src/event.c src/graph.c src/graph.h src/net.c src/net.h src/node.h src/openssl/crypto.c src/process.c src/protocol.c src/protocol_key.c src/route.c --- 33f241d97852d7a171f1aaf1bda7f66356ff889e diff --cc NEWS index c48a0e80,4b2176e7..1a121551 --- a/NEWS +++ b/NEWS @@@ -1,9 -1,7 +1,11 @@@ -Version 1.0.15 not released yet +Version 1.1-cvs Work in progress + + * Use libevent to handle I/O events and timeouts. + + * Use splay trees instead of AVL trees. + * Fix ProcessPriority option under Windows. + Version 1.0.14 May 8 2011 * Fixed reading configuration files that do not end with a newline. Again. diff --cc configure.in index 22e5fb1f,1421b16a..0e12a365 --- a/configure.in +++ b/configure.in @@@ -126,10 -127,14 +126,10 @@@ AC_CHECK_TYPES([socklen_t, struct ether ) dnl Checks for library functions. -AC_FUNC_MEMCMP -AC_FUNC_ALLOCA AC_TYPE_SIGNAL - AC_CHECK_FUNCS([asprintf daemon fchmod flock ftime fork get_current_dir_name gettimeofday mlockall putenv random select strdup strerror strsignal strtol system time usleep unsetenv vsyslog writev], -AC_CHECK_FUNCS([asprintf daemon fchmod flock ftime fork get_current_dir_name gettimeofday mlockall pselect putenv random select strdup strerror strsignal strtol system unsetenv usleep vsyslog writev], ++AC_CHECK_FUNCS([asprintf daemon fchmod flock ftime fork get_current_dir_name gettimeofday mlockall pselect putenv random select strdup strerror strsignal strtol system time usleep unsetenv vsyslog writev], [], [], [#include "have.h"] ) -AC_FUNC_MALLOC -AC_FUNC_REALLOC dnl Support for SunOS diff --cc doc/tinc.texi index 7fc8909f,52a0eccf..7878db56 --- a/doc/tinc.texi +++ b/doc/tinc.texi @@@ -1636,7 -1638,22 +1636,9 @@@ You can also send the following signal Partially rereads configuration files. Connections to hosts whose host config file are removed are closed. New outgoing connections specified in @file{tinc.conf} will be made. + If the --logfile option is used, this will also close and reopen the log file, + useful when log rotation is used. -@item INT -Temporarily increases debug level to 5. -Send this signal again to revert to the original level. - -@item USR1 -Dumps the connection list to syslog. - -@item USR2 -Dumps virtual network device statistics, all known nodes, edges and subnets to syslog. - -@item WINCH -Purges all information remembered about unreachable nodes. - @end table @c ================================================================== diff --cc src/conf.c index 593cd0c2,1560541a..099b77da --- a/src/conf.c +++ b/src/conf.c @@@ -23,9 -23,10 +23,10 @@@ #include "system.h" -#include "avl_tree.h" +#include "splay_tree.h" #include "connection.h" #include "conf.h" + #include "list.h" #include "logger.h" #include "netutl.h" /* for str2address */ #include "protocol.h" diff --cc src/connection.c index 5beea4d9,e7ea9b2a..62bfccb6 --- a/src/connection.c +++ b/src/connection.c @@@ -21,14 -21,9 +21,12 @@@ #include "system.h" -#include "avl_tree.h" +#include "splay_tree.h" +#include "cipher.h" #include "conf.h" +#include "control_common.h" +#include "list.h" #include "logger.h" - #include "net.h" /* Don't ask. */ - #include "netutl.h" #include "subnet.h" #include "utils.h" #include "xalloc.h" diff --cc src/graph.c index 28be9d5f,9aadcd86..bb55dfdc --- a/src/graph.c +++ b/src/graph.c @@@ -104,129 -127,15 +105,107 @@@ void mst_kruskal(void) if(e->reverse->connection) e->reverse->connection->status.mst = true; - safe_edges++; - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight); + } +} - if(skipped) { - skipped = false; - next = edge_weight_tree->head; - continue; +/* Implementation of Dijkstra's algorithm. + Running time: O(N^2) +*/ + +static 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); - } - } ++ if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN) ++ update_node_udp(e->to, &e->address); + + 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); } } diff --cc src/linux/device.c index f95410c6,c7c1b65c..d36f3f67 --- a/src/linux/device.c +++ b/src/linux/device.c @@@ -20,10 -20,15 +20,11 @@@ #include "system.h" -#ifdef HAVE_LINUX_IF_TUN_H #include #define DEFAULT_DEVICE "/dev/net/tun" -#else -#define DEFAULT_DEVICE "/dev/tap0" -#endif #include "conf.h" + #include "device.h" #include "logger.h" #include "net.h" #include "route.h" diff --cc src/net.c index 67603f7d,c5193c5d..b299bf18 --- a/src/net.c +++ b/src/net.c @@@ -171,9 -238,9 +172,9 @@@ static void timeout_handler(int fd, sho if(c->status.pinged) { ifdebug(CONNECTIONS) logger(LOG_INFO, "%s (%s) didn't respond to PING in %ld seconds", c->name, c->hostname, now - c->last_ping_time); - c->status.timeout = true; terminate_connection(c, true); + continue; - } else if(c->last_ping_time + pinginterval < now) { + } else if(c->last_ping_time + pinginterval <= now) { send_ping(c); } } else { diff --cc src/net.h index 3a37fe17,b831cdd8..b24d2d4d --- a/src/net.h +++ b/src/net.h @@@ -125,14 -128,14 +125,14 @@@ extern int contradicting_del_edge #include "node.h" extern void retry_outgoing(outgoing_t *); -extern void handle_incoming_vpn_data(int); +extern void handle_incoming_vpn_data(int, short, void *); extern void finish_connecting(struct connection_t *); -extern void do_outgoing_connection(struct connection_t *); -extern bool handle_new_meta_connection(int); +extern bool do_outgoing_connection(struct connection_t *); +extern void handle_new_meta_connection(int, short, void *); extern int setup_listen_socket(const sockaddr_t *); extern int setup_vpn_in_socket(const sockaddr_t *); -extern void send_packet(const struct node_t *, vpn_packet_t *); +extern void send_packet(struct node_t *, vpn_packet_t *); - extern void receive_tcppacket(struct connection_t *, char *, int); + extern void receive_tcppacket(struct connection_t *, const char *, int); extern void broadcast_packet(const struct node_t *, vpn_packet_t *); extern bool setup_network(void); extern void setup_outgoing_connection(struct outgoing_t *); @@@ -143,13 -146,7 +143,13 @@@ extern void terminate_connection(struc extern void flush_queue(struct node_t *); extern bool read_rsa_public_key(struct connection_t *); extern void send_mtu_probe(struct node_t *); +extern void handle_device_data(int, short, void *); +extern void handle_meta_connection_data(int, short, void *); - extern void regenerate_key(); ++extern void regenerate_key(void); +extern void purge(void); +extern void retry(void); +extern int reload_configuration(void); - extern void load_all_subnets(); + extern void load_all_subnets(void); #ifndef HAVE_MINGW #define closesocket(s) close(s) diff --cc src/net_packet.c index 1af5026a,fe20a258..3627f31d --- a/src/net_packet.c +++ b/src/net_packet.c @@@ -36,16 -36,13 +36,15 @@@ #include LZO1X_H #endif -#include "avl_tree.h" +#include "splay_tree.h" +#include "cipher.h" #include "conf.h" #include "connection.h" +#include "crypto.h" +#include "digest.h" #include "device.h" #include "ethernet.h" -#include "event.h" #include "graph.h" - #include "list.h" #include "logger.h" #include "net.h" #include "netutl.h" diff --cc src/node.h index 41737372,07c7c49f..2f081863 --- a/src/node.h +++ b/src/node.h @@@ -21,11 -21,9 +21,10 @@@ #ifndef __TINC_NODE_H__ #define __TINC_NODE_H__ -#include "avl_tree.h" +#include "splay_tree.h" +#include "cipher.h" #include "connection.h" -#include "event.h" +#include "digest.h" - #include "list.h" #include "subnet.h" typedef struct node_status_t { diff --cc src/process.c index 8c6679b8,c6592371..ee5fce97 --- a/src/process.c +++ b/src/process.c @@@ -26,7 -25,9 +26,8 @@@ #include "device.h" #include "edge.h" #include "logger.h" + #include "net.h" #include "node.h" -#include "pidfile.h" #include "process.h" #include "subnet.h" #include "utils.h" diff --cc src/protocol.c index fd908949,aec00eee..650c5129 --- a/src/protocol.c +++ b/src/protocol.c @@@ -205,8 -214,8 +205,8 @@@ static void age_past_requests(int fd, s next = node->next; p = node->data; - if(p->firstseen + pinginterval < now) + if(p->firstseen + pinginterval <= now) - avl_delete_node(past_request_tree, node), deleted++; + splay_delete_node(past_request_tree, node), deleted++; else left++; } diff --cc src/utils.h index fddb8a67,f6ff7052..6f00e5a2 --- a/src/utils.h +++ b/src/utils.h @@@ -39,9 -38,8 +39,9 @@@ extern const char *winerror(int) #define sockwouldblock(x) ((x) == EWOULDBLOCK || (x) == EINTR) #define sockmsgsize(x) ((x) == EMSGSIZE) #define sockinprogress(x) ((x) == EINPROGRESS) +#define sockinuse(x) ((x) == EADDRINUSE) #endif - extern unsigned int bitfield_to_int(void *bitfield, size_t size); + extern unsigned int bitfield_to_int(const void *bitfield, size_t size); #endif /* __TINC_UTILS_H__ */