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: import-tinc-1.1~486 X-Git-Url: http://git.meshlink.io/?p=meshlink;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.c index 4aed59f5,00000000..6ea904a5 mode 100644,000000..100644 --- a/src/utils.c +++ b/src/utils.c @@@ -1,76 -1,0 +1,76 @@@ +/* + utils.c -- gathering of some stupid small functions + Copyright (C) 1999-2005 Ivo Timmermans + 2000-2009 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 + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +*/ + +#include "system.h" + +#include "../src/logger.h" +#include "utils.h" + +static const char hexadecimals[] = "0123456789ABCDEF"; + +static int charhex2bin(char c) { + if(isdigit(c)) + return c - '0'; + else + return toupper(c) - 'A' + 10; +} + + +void hex2bin(char *src, char *dst, int length) { + int i; + for(i = 0; i < length; i++) + dst[i] = charhex2bin(src[i * 2]) * 16 + charhex2bin(src[i * 2 + 1]); +} + +void bin2hex(char *src, char *dst, int length) { + int i; + for(i = length - 1; i >= 0; i--) { + dst[i * 2 + 1] = hexadecimals[(unsigned char) src[i] & 15]; + dst[i * 2] = hexadecimals[(unsigned char) src[i] >> 4]; + } +} + +#if defined(HAVE_MINGW) || defined(HAVE_CYGWIN) +#ifdef HAVE_CYGWIN +#include +#endif + +const char *winerror(int err) { + static char buf[1024], *newline; + + if (!FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS, + NULL, err, MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT), buf, sizeof(buf), NULL)) { + strncpy(buf, "(unable to format errormessage)", sizeof(buf)); + }; + + if((newline = strchr(buf, '\r'))) + *newline = '\0'; + + return buf; +} +#endif + - unsigned int bitfield_to_int(void *bitfield, size_t size) { ++unsigned int bitfield_to_int(const void *bitfield, size_t size) { + unsigned int value = 0; + if(size > sizeof value) + size = sizeof value; + memcpy(&value, bitfield, size); + return value; +} diff --cc src/utils.h index fddb8a67,00000000..6f00e5a2 mode 100644,000000..100644 --- a/src/utils.h +++ b/src/utils.h @@@ -1,47 -1,0 +1,47 @@@ +/* + utils.h -- header file for utils.c + Copyright (C) 1999-2005 Ivo Timmermans + 2000-2009 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 + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +*/ + +#ifndef __TINC_UTILS_H__ +#define __TINC_UTILS_H__ + +extern void hex2bin(char *src, char *dst, int length); +extern void bin2hex(char *src, char *dst, int length); + +#ifdef HAVE_MINGW +extern const char *winerror(int); +#define strerror(x) ((x)>0?strerror(x):winerror(GetLastError())) +#define sockerrno WSAGetLastError() +#define sockstrerror(x) winerror(x) +#define sockwouldblock(x) ((x) == WSAEWOULDBLOCK || (x) == WSAEINTR) +#define sockmsgsize(x) ((x) == WSAEMSGSIZE) +#define sockinprogress(x) ((x) == WSAEINPROGRESS || (x) == WSAEWOULDBLOCK) +#define sockinuse(x) ((x) == WSAEADDRINUSE) +#else +#define sockerrno errno +#define sockstrerror(x) strerror(x) +#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__ */