- tor-commits - lists.torproject.org

[obfsproxy/master] Hoist (nearly-)ubiquitous includes and forward declarations to util.h.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 7184b10a0b08fd0cb7c5148be23898d38138f04e Author: Zack Weinberg <zackw(a)panix.com> Date: Mon Jul 25 16:26:55 2011 -0700 Hoist (nearly-)ubiquitous includes and forward declarations to util.h. --- src/container.h | 2 -- src/crypt.c | 3 --- src/crypt.h | 2 -- src/main.c | 2 -- src/network.c | 7 ------- src/network.h | 37 ++++--------------------------------- src/protocol.c | 4 ---- src/protocol.h | 33 ++++++++++++++------------------- src/protocols/dummy.c | 2 -- src/protocols/dummy.h | 3 +-- src/protocols/obfs2.c | 2 -- src/protocols/obfs2.h | 3 +-- src/sha256.c | 1 - src/sha256.h | 2 -- src/socks.c | 6 ------ src/socks.h | 4 ---- src/test/tinytest.c | 4 ---- src/util.c | 8 -------- src/util.h | 44 +++++++++++++++++++++++++++++++++++++++++--- 19 files changed, 61 insertions(+), 108 deletions(-) diff --git a/src/container.h b/src/container.h index e1c1a07..129e4f9 100644 --- a/src/container.h +++ b/src/container.h @@ -6,8 +6,6 @@ #ifndef CONTAINER_H #define CONTAINER_H -#include <stdlib.h> -#include <string.h> #include <time.h> /** A resizeable list of pointers, with associated helpful functionality. diff --git a/src/crypt.c b/src/crypt.c index 9019fc9..62d99fe 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -8,9 +8,6 @@ #include "crypt.h" #include <fcntl.h> -#include <limits.h> -#include <stdlib.h> -#include <string.h> #include <unistd.h> #include <openssl/opensslv.h> diff --git a/src/crypt.h b/src/crypt.h index beccda6..51bbc57 100644 --- a/src/crypt.h +++ b/src/crypt.h @@ -5,8 +5,6 @@ #ifndef CRYPT_H #define CRYPT_H -#include <stddef.h> /* for size_t */ - #define SHA256_LENGTH 32 /* Stream cipher state */ diff --git a/src/main.c b/src/main.c index cc69805..f6280c2 100644 --- a/src/main.c +++ b/src/main.c @@ -11,8 +11,6 @@ #include <errno.h> #include <signal.h> #include <stdio.h> -#include <stdlib.h> -#include <string.h> #include <event2/event.h> #include <event2/dns.h> diff --git a/src/network.c b/src/network.c index c4cf0c7..f7a94d3 100644 --- a/src/network.c +++ b/src/network.c @@ -13,18 +13,11 @@ #include "protocol.h" #include <errno.h> -#include <stdlib.h> -#include <string.h> #include <event2/buffer.h> #include <event2/bufferevent.h> #include <event2/bufferevent_struct.h> #include <event2/listener.h> -#include <event2/util.h> - -#ifdef _WIN32 -#include <ws2tcpip.h> /* socklen_t */ -#endif /* Terminology used in this file: diff --git a/src/network.h b/src/network.h index b6aa410..c5ef69e 100644 --- a/src/network.h +++ b/src/network.h @@ -5,51 +5,22 @@ #ifndef NETWORK_H #define NETWORK_H -struct event_base; -struct protocol_params_t; - -#define LSN_SIMPLE_CLIENT 1 -#define LSN_SIMPLE_SERVER 2 -#define LSN_SOCKS_CLIENT 3 - -enum recv_ret { - /* Everything went fine. */ - RECV_GOOD=0, - /* Something went bad. */ - RECV_BAD, - /* ...need...more...data... */ - RECV_INCOMPLETE, - - /* Originally needed by the obfs2 protocol but it might get other - users in the future. - It means: - "We have pending data that we have to send. You should do that by - calling proto_send() immediately." */ - RECV_SEND_PENDING -}; - /* returns 1 on success, 0 on failure */ -int create_listener(struct event_base *base, struct protocol_params_t *params); +int create_listener(struct event_base *base, protocol_params_t *params); void free_all_listeners(void); void start_shutdown(int barbaric); #ifdef NETWORK_PRIVATE -struct bufferevent; -struct evconnlistener; -struct socks_state_t; -struct protocol_t; -struct protocol_params_t; - typedef struct listener_t { + protocol_params_t *proto_params; struct evconnlistener *listener; - struct protocol_params_t *proto_params; } listener_t; typedef struct conn_t { - struct protocol_t *proto; - struct socks_state_t *socks_state; + protocol_t *proto; + socks_state_t *socks_state; struct bufferevent *upstream; struct bufferevent *downstream; unsigned int mode : 30; diff --git a/src/protocol.c b/src/protocol.c index a010d16..2966e06 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -8,10 +8,6 @@ #include "protocols/obfs2.h" #include "protocols/dummy.h" -#include <stdlib.h> -#include <string.h> - - /** All supported protocols should be put in this array. It's used by main.c. diff --git a/src/protocol.h b/src/protocol.h index c023720..246ad1c 100644 --- a/src/protocol.h +++ b/src/protocol.h @@ -5,11 +5,6 @@ #ifndef PROTOCOL_H #define PROTOCOL_H -#include "network.h" /* for recv_ret */ -#include <event2/util.h> /* for evutil_addrinfo */ - -struct evbuffer; - /** This struct defines the protocol-specific state for all connections opened from a particular listener. Each protocol may extend this @@ -17,12 +12,12 @@ struct evbuffer; member of a larger structure (standard fake-inheritance-in-C technique). */ -typedef struct protocol_params_t { - const struct protocol_vtable *vtable; +struct protocol_params_t { + const protocol_vtable *vtable; struct evutil_addrinfo *target_addr; struct evutil_addrinfo *listen_addr; int mode; -} protocol_params_t; +}; /** This struct defines the protocol-specific state for a particular @@ -30,9 +25,9 @@ typedef struct protocol_params_t { additional private data by embedding it as the first member of a larger structure. */ -typedef struct protocol_t { - const struct protocol_vtable *vtable; -} protocol_t; +struct protocol_t { + const protocol_vtable *vtable; +}; /** This struct defines a protocol and its methods; note that not all @@ -42,7 +37,7 @@ typedef struct protocol_t { principal interface between each individual protocol and generic code. At present there is a static list of these objects in protocol.c. */ -typedef struct protocol_vtable +struct protocol_vtable { /** The short name of this protocol. */ const char *name; @@ -78,19 +73,19 @@ typedef struct protocol_vtable struct evbuffer *source, struct evbuffer *dest); -} protocol_vtable; +}; /** Use this macro to define protocol_vtable objects; it ensures all the methods are in the correct order and enforces a consistent naming convention on protocol implementations. */ -#define DEFINE_PROTOCOL_VTABLE(name) \ - const struct protocol_vtable name##_vtable = { \ - #name, \ - name##_init, name##_fini, \ - name##_create, name##_destroy, \ - name##_handshake, name##_send, name##_recv \ +#define DEFINE_PROTOCOL_VTABLE(name) \ + const protocol_vtable name##_vtable = { \ + #name, \ + name##_init, name##_fini, \ + name##_create, name##_destroy, \ + name##_handshake, name##_send, name##_recv \ } protocol_params_t *proto_params_init(int n_options, diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index e6c4ca5..8ecce8f 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -7,8 +7,6 @@ #define PROTOCOL_DUMMY_PRIVATE #include "dummy.h" -#include <stdlib.h> -#include <string.h> #include <event2/buffer.h> /* type-safe downcast wrappers */ diff --git a/src/protocols/dummy.h b/src/protocols/dummy.h index 944fe1b..308c4f0 100644 --- a/src/protocols/dummy.h +++ b/src/protocols/dummy.h @@ -4,8 +4,7 @@ #ifndef PROTOCOL_DUMMY_H #define PROTOCOL_DUMMY_H -struct protocol_vtable; -extern const struct protocol_vtable dummy_vtable; +extern const protocol_vtable dummy_vtable; #ifdef PROTOCOL_DUMMY_PRIVATE diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 166c54a..6a6a975 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -7,8 +7,6 @@ #define PROTOCOL_OBFS2_PRIVATE #include "obfs2.h" -#include <stdlib.h> -#include <string.h> #include <event2/buffer.h> /* type-safe downcast wrappers */ diff --git a/src/protocols/obfs2.h b/src/protocols/obfs2.h index 107d15a..ce28217 100644 --- a/src/protocols/obfs2.h +++ b/src/protocols/obfs2.h @@ -5,8 +5,7 @@ #ifndef PROTOCOL_OBFS2_H #define PROTOCOL_OBFS2_H -struct protocol_vtable; -extern const struct protocol_vtable obfs2_vtable; +extern const protocol_vtable obfs2_vtable; #ifdef PROTOCOL_OBFS2_PRIVATE diff --git a/src/sha256.c b/src/sha256.c index 7d273ae..fccbde6 100644 --- a/src/sha256.c +++ b/src/sha256.c @@ -7,7 +7,6 @@ #include "util.h" #include "sha256.h" -#include <string.h> #include <arpa/inet.h> /* for htonl/ntohl */ #define STMT_BEGIN do { diff --git a/src/sha256.h b/src/sha256.h index b6a75be..6afdbfe 100644 --- a/src/sha256.h +++ b/src/sha256.h @@ -2,8 +2,6 @@ #ifndef SHA256_H #define SHA256_H -#include <stdint.h> - typedef struct sha256_state { uint64_t length; uint32_t state[8], curlen; diff --git a/src/socks.c b/src/socks.c index f1eada4..9941005 100644 --- a/src/socks.c +++ b/src/socks.c @@ -8,15 +8,9 @@ #include "socks.h" #include <errno.h> -#include <stdlib.h> -#include <string.h> #include <event2/buffer.h> -#ifdef _WIN32 -#include <ws2tcpip.h> /* sockaddr_in6 */ -#endif - /** General SOCKS5 idea: diff --git a/src/socks.h b/src/socks.h index db10cb5..a06a11e 100644 --- a/src/socks.h +++ b/src/socks.h @@ -5,10 +5,6 @@ #ifndef SOCKS_H #define SOCKS_H -typedef struct socks_state_t socks_state_t; -struct evbuffer; -struct sockaddr; - enum socks_status_t { /* Waiting for initial socks4 or socks5 message */ ST_WAITING, diff --git a/src/test/tinytest.c b/src/test/tinytest.c index 5151bcb..32e7b76 100644 --- a/src/test/tinytest.c +++ b/src/test/tinytest.c @@ -23,13 +23,9 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#include "tinytest.h" #include "tinytest_macros.h" #include <assert.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> #ifdef _WIN32 #define WIN32_LEAN_AND_MEAN diff --git a/src/util.c b/src/util.c index 8e63944..167e867 100644 --- a/src/util.c +++ b/src/util.c @@ -6,18 +6,10 @@ #include <errno.h> #include <fcntl.h> -#include <limits.h> #include <stdio.h> -#include <stdlib.h> -#include <string.h> #include <unistd.h> #include <event2/dns.h> -#include <event2/util.h> - -#ifdef _WIN32 -#include <ws2tcpip.h> /* addrinfo */ -#endif /** Any size_t larger than this amount is likely to be an underflow. */ #define SIZE_T_CEILING (SIZE_MAX/2 - 16) diff --git a/src/util.h b/src/util.h index cb98fbd..ede23e4 100644 --- a/src/util.h +++ b/src/util.h @@ -6,14 +6,25 @@ #define UTIL_H #include "config.h" + +#include <limits.h> #include <stdarg.h> /* va_list */ #include <stddef.h> /* size_t, ptrdiff_t, offsetof, NULL */ #include <stdint.h> /* intN_t, uintN_t */ +#include <stdlib.h> +#include <string.h> + #include <event2/util.h> /* evutil_addrinfo */ +#ifdef _WIN32 +#include <ws2tcpip.h> /* addrinfo (event2/util.h should do this, + but it doesn't) */ +#endif -struct sockaddr; -struct event_base; +struct bufferevent; +struct evconnlistener; +struct evbuffer; struct evdns_base; +struct event_base; /***** Type annotations. *****/ @@ -49,7 +60,34 @@ char *xstrndup(const char *s, size_t maxsize) ATTR_MALLOC; unsigned int ui64_log2(uint64_t u64); -/***** Network functions. *****/ +/***** Network types and functions. *****/ + +typedef struct protocol_t protocol_t; +typedef struct protocol_params_t protocol_params_t; +typedef struct protocol_vtable protocol_vtable; +typedef struct socks_state_t socks_state_t; + +enum recv_ret { + /* Everything went fine. */ + RECV_GOOD=0, + /* Something went bad. */ + RECV_BAD, + /* ...need...more...data... */ + RECV_INCOMPLETE, + + /* Originally needed by the obfs2 protocol but it might get other + users in the future. + It means: + "We have pending data that we have to send. You should do that by + calling proto_send() immediately." */ + RECV_SEND_PENDING +}; + +enum listen_mode { + LSN_SIMPLE_CLIENT = 1, + LSN_SIMPLE_SERVER, + LSN_SOCKS_CLIENT +}; struct evutil_addrinfo *resolve_address_port(const char *address, int nodns, int passive,

1 0

[obfsproxy/master] In preparation for importing Tor container.c, switch from bare __attribute__ to ATTR_* macros.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 94d44dd806b58dde92fdb82dd0c5ae12d649ef80 Author: Zack Weinberg <zackw(a)panix.com> Date: Mon Jul 18 14:15:50 2011 -0700 In preparation for importing Tor container.c, switch from bare __attribute__ to ATTR_* macros. --- src/main.c | 17 +++++++---------- src/protocols/dummy.c | 7 +++---- src/util.c | 2 +- src/util.h | 21 +++++++++++++-------- 4 files changed, 24 insertions(+), 23 deletions(-) diff --git a/src/main.c b/src/main.c index 21c4feb..c48f81a 100644 --- a/src/main.c +++ b/src/main.c @@ -2,27 +2,24 @@ See LICENSE for other credits and copying information */ -#include <stdlib.h> +#include "util.h" +#include "network.h" +#include "protocol.h" + #include <errno.h> +#include <signal.h> #include <stdio.h> +#include <stdlib.h> #include <string.h> -#include <signal.h> #include <event2/event.h> -#include "network.h" -#include "util.h" -#include "protocol.h" - -#ifndef __GNUC__ -#define __attribute__(x) -#endif /* The character that seperates multiple listeners in the cli */ #define SEPARATOR "+" /* Totally arbitrary. */ #define MAXPROTOCOLS 20 -static void usage(void) __attribute__((noreturn)); +static void usage(void) ATTR_NORETURN; static int handle_obfsproxy_args(const char **argv); static struct event_base *the_event_base=NULL; diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index d82818d..61cdf2b 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -116,14 +116,13 @@ dummy_destroy(struct protocol_t *proto) The dummy protocol just puts the data of 'source' in 'dest'. */ static int -dummy_handshake(struct protocol_t *proto __attribute__((unused)), - struct evbuffer *buf __attribute__((unused))) +dummy_handshake(struct protocol_t *proto, struct evbuffer *buf) { return 0; } static int -dummy_send(struct protocol_t *proto __attribute__((unused)), +dummy_send(struct protocol_t *proto, struct evbuffer *source, struct evbuffer *dest) { return evbuffer_add_buffer(dest,source); @@ -135,7 +134,7 @@ dummy_send(struct protocol_t *proto __attribute__((unused)), The dummy protocol just puts the data of 'source' into 'dest'. */ static enum recv_ret -dummy_recv(struct protocol_t *proto __attribute__((unused)), +dummy_recv(struct protocol_t *proto, struct evbuffer *source, struct evbuffer *dest) { if (evbuffer_add_buffer(dest,source)<0) diff --git a/src/util.c b/src/util.c index 6a0e4a0..ce25375 100644 --- a/src/util.c +++ b/src/util.c @@ -25,7 +25,7 @@ /**************************** Memory Allocation ******************************/ -static void __attribute__((noreturn)) +static void ATTR_NORETURN die_oom(void) { log_warn("Memory allocation failed: %s",strerror(errno)); diff --git a/src/util.h b/src/util.h index d909b53..0693930 100644 --- a/src/util.h +++ b/src/util.h @@ -11,6 +11,11 @@ #ifndef __GNUC__ #define __attribute__(x) /* nothing */ #endif +#define ATTR_MALLOC __attribute__((malloc)) +#define ATTR_NORETURN __attribute__((noreturn)) +#define ATTR_PRINTF_1 __attribute__((format(printf, 1, 2))) +#define ATTR_PRINTF_3 __attribute__((format(printf, 3, 4))) +#define ATTR_PURE __attribute__((pure)) struct sockaddr; struct event_base; @@ -23,11 +28,11 @@ struct evdns_base; allocate-memory-or-crash functions "xwhatever". Also, at this time I do not see a need for a free() wrapper. */ -void *xmalloc(size_t size) __attribute__((malloc)); /* does not clear memory */ -void *xzalloc(size_t size) __attribute__((malloc)); /* clears memory */ +void *xmalloc(size_t size) ATTR_MALLOC; /* does not clear memory */ +void *xzalloc(size_t size) ATTR_MALLOC; /* clears memory */ void *xrealloc(void *ptr, size_t size); -void *xmemdup(const void *ptr, size_t size) __attribute__((malloc)); -char *xstrdup(const char *s) __attribute__((malloc)); +void *xmemdup(const void *ptr, size_t size) ATTR_MALLOC; +char *xstrdup(const char *s) ATTR_MALLOC; /***** Network functions stuff. *****/ @@ -46,7 +51,7 @@ int obfs_vsnprintf(char *str, size_t size, const char *format, va_list args); int obfs_snprintf(char *str, size_t size, const char *format, ...) - __attribute__((format(printf, 3, 4))); + ATTR_PRINTF_3; /***** Doubly Linked List stuff. *****/ @@ -96,16 +101,16 @@ void close_obfsproxy_logfile(void); /** Warn-level severity: for messages that only appear when something has gone wrong. */ void log_warn(const char *format, ...) - __attribute__((format(printf, 1, 2))); + ATTR_PRINTF_1; /** Info-level severity: for messages that should be sent to the user during normal operation. */ void log_info(const char *format, ...) - __attribute__((format(printf, 1, 2))); + ATTR_PRINTF_1; /** Debug-level severity: for hyper-verbose messages of no interest to anybody but developers. */ void log_debug(const char *format, ...) - __attribute__((format(printf, 1, 2))); + ATTR_PRINTF_1; #endif

1 0

[obfsproxy/master] All .c files include util.h first. No .h file includes util.h. util.h includes config.h. tinytest_macros.h includes tinytest.h, stdio.h, stdlib.h, string.h.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 443a77087d139943af827688fdb0262f4df82959 Author: Zack Weinberg <zackw(a)panix.com> Date: Mon Jul 18 14:51:54 2011 -0700 All .c files include util.h first. No .h file includes util.h. util.h includes config.h. tinytest_macros.h includes tinytest.h, stdio.h, stdlib.h, string.h. --- src/crypt.c | 3 ++- src/main.c | 1 + src/network.c | 3 ++- src/network.h | 2 -- src/protocol.c | 3 ++- src/protocols/dummy.c | 3 ++- src/protocols/obfs2.c | 4 ++-- src/sha256.c | 3 ++- src/socks.c | 4 ++-- src/test/tinytest_macros.h | 5 +++++ src/test/unittest_crypt.c | 5 +---- src/test/unittest_obfs2.c | 7 +------ src/test/unittest_socks.c | 7 +------ src/util.h | 1 + 14 files changed, 24 insertions(+), 27 deletions(-) diff --git a/src/crypt.c b/src/crypt.c index 9984e24..e28e061 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -2,9 +2,10 @@ See LICENSE for other credits and copying information */ +#include "util.h" + #define CRYPT_PRIVATE #include "crypt.h" -#include "util.h" #include <fcntl.h> #include <limits.h> diff --git a/src/main.c b/src/main.c index c48f81a..a7aa298 100644 --- a/src/main.c +++ b/src/main.c @@ -3,6 +3,7 @@ */ #include "util.h" + #include "network.h" #include "protocol.h" diff --git a/src/network.c b/src/network.c index fcbb45c..35e4eaf 100644 --- a/src/network.c +++ b/src/network.c @@ -2,10 +2,11 @@ See LICENSE for other credits and copying information */ +#include "util.h" + #define NETWORK_PRIVATE #include "network.h" -#include "util.h" #include "main.h" #include "socks.h" #include "protocol.h" diff --git a/src/network.h b/src/network.h index ad54686..e631697 100644 --- a/src/network.h +++ b/src/network.h @@ -39,8 +39,6 @@ void start_shutdown(int barbaric); #ifdef NETWORK_PRIVATE -#include "util.h" - struct bufferevent; struct socks_state_t; struct protocol_t; diff --git a/src/protocol.c b/src/protocol.c index 4473a94..6abf7f1 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -2,10 +2,11 @@ See LICENSE for other credits and copying information */ +#include "util.h" + #include "protocol.h" #include "protocols/obfs2.h" #include "protocols/dummy.h" -#include "util.h" #include <stdlib.h> #include <string.h> diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index b1493ce..c65f7b5 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -2,9 +2,10 @@ See LICENSE for other credits and copying information */ +#include "../util.h" + #include "dummy.h" #include "../protocol.h" -#include "../util.h" #include <stdlib.h> #include <string.h> diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 5acd09e..f17af90 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -2,11 +2,11 @@ See LICENSE for other credits and copying information */ +#include "../util.h" + #define PROTOCOL_OBFS2_PRIVATE #include "obfs2.h" -#include "../util.h" - #include <stdlib.h> #include <string.h> diff --git a/src/sha256.c b/src/sha256.c index d303f5f..7d273ae 100644 --- a/src/sha256.c +++ b/src/sha256.c @@ -4,8 +4,9 @@ LibTomCrypt, version 1.6. Tor uses it on platforms where OpenSSL doesn't have a SHA256. */ -#include "sha256.h" #include "util.h" + +#include "sha256.h" #include <string.h> #include <arpa/inet.h> /* for htonl/ntohl */ diff --git a/src/socks.c b/src/socks.c index 6bd708f..333c787 100644 --- a/src/socks.c +++ b/src/socks.c @@ -2,11 +2,11 @@ See LICENSE for other credits and copying information */ +#include "util.h" + #define SOCKS_PRIVATE #include "socks.h" -#include "util.h" - #include <errno.h> #include <stdlib.h> #include <string.h> diff --git a/src/test/tinytest_macros.h b/src/test/tinytest_macros.h index 089616a..25ee7e2 100644 --- a/src/test/tinytest_macros.h +++ b/src/test/tinytest_macros.h @@ -26,6 +26,11 @@ #ifndef _TINYTEST_MACROS_H #define _TINYTEST_MACROS_H +#include "tinytest.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + /* Helpers for defining statement-like macros */ #define TT_STMT_BEGIN do { #define TT_STMT_END } while(0) diff --git a/src/test/unittest_crypt.c b/src/test/unittest_crypt.c index 5a3e2aa..a3574f6 100644 --- a/src/test/unittest_crypt.c +++ b/src/test/unittest_crypt.c @@ -2,15 +2,12 @@ See LICENSE for other credits and copying information */ -#include "tinytest.h" +#include "../util.h" #include "tinytest_macros.h" #define CRYPT_PRIVATE #include "../crypt.h" -#include <stdio.h> -#include <string.h> - /* Test vectors for sha256 */ static void test_crypt_hashvec(void *data) diff --git a/src/test/unittest_obfs2.c b/src/test/unittest_obfs2.c index 3ac4c42..099acd2 100644 --- a/src/test/unittest_obfs2.c +++ b/src/test/unittest_obfs2.c @@ -2,18 +2,13 @@ See LICENSE for other credits and copying information */ -#include "tinytest.h" +#include "../util.h" #include "tinytest_macros.h" #define PROTOCOL_OBFS2_PRIVATE #define CRYPT_PRIVATE #include "../protocols/obfs2.h" #include "../crypt.h" -#include "../util.h" - -#include <stdio.h> -#include <stdlib.h> -#include <string.h> #include <event2/buffer.h> diff --git a/src/test/unittest_socks.c b/src/test/unittest_socks.c index db4f120..9ba9e7e 100644 --- a/src/test/unittest_socks.c +++ b/src/test/unittest_socks.c @@ -2,17 +2,12 @@ See LICENSE for other credits and copying information */ -#include "tinytest.h" +#include "../util.h" #include "tinytest_macros.h" #define SOCKS_PRIVATE #include "../socks.h" #include "../crypt.h" -#include "../util.h" - -#include <stdio.h> -#include <stdlib.h> -#include <string.h> #include <event2/buffer.h> diff --git a/src/util.h b/src/util.h index 8e5dd77..d365cbc 100644 --- a/src/util.h +++ b/src/util.h @@ -5,6 +5,7 @@ #ifndef UTIL_H #define UTIL_H +#include "config.h" #include <stdarg.h> /* for va_list */ #include <stddef.h> /* size_t, offsetof, NULL, etc */

1 0

[obfsproxy/master] Introduce tt_mem_op and use it throughout existing tests.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 434162e6900a7ebb1a745cbd1fe3324e1f4c244b Author: Zack Weinberg <zackw(a)panix.com> Date: Mon Jul 18 16:35:28 2011 -0700 Introduce tt_mem_op and use it throughout existing tests. --- src/test/tinytest.c | 17 +++++++++++++++++ src/test/tinytest.h | 4 ++++ src/test/tinytest_macros.h | 12 ++++++++++++ src/test/unittest_crypt.c | 34 +++++++++++++++++----------------- src/test/unittest_obfs2.c | 20 ++++++++------------ src/test/unittest_socks.c | 28 ++++++++++++++-------------- 6 files changed, 72 insertions(+), 43 deletions(-) diff --git a/src/test/tinytest.c b/src/test/tinytest.c index e3107b2..5151bcb 100644 --- a/src/test/tinytest.c +++ b/src/test/tinytest.c @@ -367,3 +367,20 @@ _tinytest_set_test_skipped(void) cur_test_outcome = SKIP; } +char * +tt_base16_encode(const char *value, size_t vlen) +{ + static const char hex[] = "0123456789abcdef"; + char *print = malloc(vlen * 2 + 1); + char *p = print; + const char *v = value, *vl = value + vlen; + + assert(print); + while (v < vl) { + unsigned char c = *v++; + *p++ = hex[(c >> 4) & 0x0f]; + *p++ = hex[(c >> 0) & 0x0f]; + } + *p = '\0'; + return print; +} diff --git a/src/test/tinytest.h b/src/test/tinytest.h index cbe28b7..a3bdcfe 100644 --- a/src/test/tinytest.h +++ b/src/test/tinytest.h @@ -26,6 +26,8 @@ #ifndef _TINYTEST_H #define _TINYTEST_H +#include <stddef.h> /* size_t */ + /** Flag for a test that needs to run in a subprocess. */ #define TT_FORK (1<<0) /** Runtime flag for a test we've decided to skip. */ @@ -73,6 +75,8 @@ int _tinytest_get_verbosity(void); /** Implementation: Set a flag on tests matching a name; returns number * of tests that matched. */ int _tinytest_set_flag(struct testgroup_t *, const char *, unsigned long); +/** Implementation: Helper function for tt_mem_op. */ +char * tt_base16_encode(const char *value, size_t vlen); /** Set all tests in 'groups' matching the name 'named' to be skipped. */ #define tinytest_skip(groups, named) \ diff --git a/src/test/tinytest_macros.h b/src/test/tinytest_macros.h index 25ee7e2..f3e6d32 100644 --- a/src/test/tinytest_macros.h +++ b/src/test/tinytest_macros.h @@ -154,6 +154,9 @@ #define tt_assert_op_type(a,op,b,type,fmt) \ tt_assert_test_type(a,b,#a" "#op" "#b,type,(_val1 op _val2),fmt) +#define tt_bool_op(a,op,b) \ + tt_assert_test_type(a,b,#a" "#op" "#b,int,(!!_val1 op !!_val2),"%d") + #define tt_int_op(a,op,b) \ tt_assert_test_type(a,b,#a" "#op" "#b,long,(_val1 op _val2),"%ld") @@ -169,4 +172,13 @@ tt_assert_test_type(a,b,#a" "#op" "#b,const char *, \ (strcmp(_val1,_val2) op 0),"<%s>") +#define tt_mem_op(expr1, op, expr2, len) \ + tt_assert_test_fmt_type(expr1,expr2,#expr1" "#op" "#expr2, \ + const char *, \ + (memcmp(_val1, _val2, len) op 0), \ + char *, "%s", \ + { _print = tt_base16_encode(_value, len); }, \ + { free(_print); } \ + ); + #endif diff --git a/src/test/unittest_crypt.c b/src/test/unittest_crypt.c index a3574f6..aef4ead 100644 --- a/src/test/unittest_crypt.c +++ b/src/test/unittest_crypt.c @@ -20,10 +20,10 @@ test_crypt_hashvec(void *data) d = digest_new(); digest_update(d, (unsigned char*)"", 0); digest_getdigest(d, output, 32); - tt_int_op(0, ==, memcmp(output, - "\xe3\xb0\xc4\x42\x98\xfc\x1c\x14\x9a\xfb\xf4\xc8" - "\x99\x6f\xb9\x24\x27\xae\x41\xe4\x64\x9b\x93\x4c" - "\xa4\x95\x99\x1b\x78\x52\xb8\x55", 32)); + tt_mem_op(output, ==, + "\xe3\xb0\xc4\x42\x98\xfc\x1c\x14\x9a\xfb\xf4\xc8" + "\x99\x6f\xb9\x24\x27\xae\x41\xe4\x64\x9b\x93\x4c" + "\xa4\x95\x99\x1b\x78\x52\xb8\x55", 32); /* Second SHA256 test vector: Test for the 256-bit entry of: @@ -34,10 +34,10 @@ test_crypt_hashvec(void *data) "\x10\xb4\x70\xb1\x44\x78\x44\x11\xc9\x3a\x4d\x50\x45\x56\x83" "\x4d\xae\x3e\xa4\xa5\xbb", 32); digest_getdigest(d, output, 32); - tt_int_op(0, ==, memcmp(output, - "\x56\x05\x9e\x8c\xb3\xc2\x97\x8b\x19\x82\x08\xbf" - "\x5c\xa1\xe1\xea\x56\x59\xb7\x37\xa5\x06\x32\x4b" - "\x7c\xec\x75\xb5\xeb\xaf\x05\x7d", 32)); + tt_mem_op(output, ==, + "\x56\x05\x9e\x8c\xb3\xc2\x97\x8b\x19\x82\x08\xbf" + "\x5c\xa1\xe1\xea\x56\x59\xb7\x37\xa5\x06\x32\x4b" + "\x7c\xec\x75\xb5\xeb\xaf\x05\x7d", 32); /* Third SHA test vector: Test for the 1304-bit entry of: @@ -57,10 +57,10 @@ test_crypt_hashvec(void *data) "\x8a\x19\xc8\x18\xc2\xea\x2e\x9d\x4e\x2d\xe9\x19\x0c\x9d\xdd" "\xb8\x06", 163); digest_getdigest(d, output, 32); - tt_int_op(0, ==, memcmp(output, - "\xc9\x07\x18\x04\x43\xde\xe3\xcb\xcc\xb4\xc3\x13" - "\x28\xe6\x25\x15\x85\x27\xa5\x93\xb8\x78\xde\x1b" - "\x8e\x4b\xa3\x7f\x1d\x69\xfb\x66", 32)); + tt_mem_op(output, ==, + "\xc9\x07\x18\x04\x43\xde\xe3\xcb\xcc\xb4\xc3\x13" + "\x28\xe6\x25\x15\x85\x27\xa5\x93\xb8\x78\xde\x1b" + "\x8e\x4b\xa3\x7f\x1d\x69\xfb\x66", 32); /* XXX Try doing init, update, update, output. */ /* XXX add a base16-decode function so we can implement a tt_mem_op or @@ -114,13 +114,13 @@ test_crypt_aes1(void *data) for (i = 0; i < 4; i++) { tt_int_op(0, ==, crypt->pos); - tt_int_op(0, ==, memcmp(crypt->ivec, testvec[i].counter, 16)); + tt_mem_op(crypt->ivec, ==, testvec[i].counter, 16); memcpy(vec, testvec[i].plaintext, 16); stream_crypt(crypt, vec, 16); - tt_int_op(0, ==, memcmp(crypt->ecount_buf, testvec[i].keystream, 16)); - tt_int_op(0, ==, memcmp(vec, testvec[i].ciphertext, 16)); + tt_mem_op(crypt->ecount_buf, ==, testvec[i].keystream, 16); + tt_mem_op(vec, ==, testvec[i].ciphertext, 16); } end: @@ -147,7 +147,7 @@ test_crypt_aes2(void *data) stream_crypt(crypt1, res1, 16); stream_crypt(crypt2, res2, 16); - tt_int_op(0, !=, memcmp(res1, res2, 16)); + tt_mem_op(res1, !=, res2, 16); end: if (crypt1) @@ -169,7 +169,7 @@ test_crypt_rng(void *data) tt_int_op(0, ==, random_bytes(data1, 100)); tt_int_op(0, ==, random_bytes(data2, 100)); - tt_int_op(0, !=, memcmp(data1, data2, 100)); + tt_mem_op(data1, !=, data2, 100); end: ; diff --git a/src/test/unittest_obfs2.c b/src/test/unittest_obfs2.c index 099acd2..00fc12e 100644 --- a/src/test/unittest_obfs2.c +++ b/src/test/unittest_obfs2.c @@ -177,13 +177,11 @@ test_obfs2_handshake(void *state) /* The handshake is now complete. We should have: client's send_crypto == server's recv_crypto server's send_crypto == client's recv_crypto . */ - tt_int_op(0, ==, memcmp(client_state->send_crypto, - server_state->recv_crypto, - sizeof(crypt_t))); + tt_mem_op(client_state->send_crypto, ==, server_state->recv_crypto, + sizeof(crypt_t)); - tt_int_op(0, ==, memcmp(client_state->recv_crypto, - server_state->send_crypto, - sizeof(crypt_t))); + tt_mem_op(client_state->recv_crypto, ==, server_state->send_crypto, + sizeof(crypt_t)); end:; } @@ -353,13 +351,11 @@ test_obfs2_split_handshake(void *state) /* The handshake is finally complete. We should have: */ /* client's send_crypto == server's recv_crypto */ /* server's send_crypto == client's recv_crypto . */ - tt_int_op(0, ==, memcmp(client_state->send_crypto, - server_state->recv_crypto, - sizeof(crypt_t))); + tt_mem_op(client_state->send_crypto, ==, server_state->recv_crypto, + sizeof(crypt_t)); - tt_int_op(0, ==, memcmp(client_state->recv_crypto, - server_state->send_crypto, - sizeof(crypt_t))); + tt_mem_op(client_state->recv_crypto, ==, server_state->send_crypto, + sizeof(crypt_t)); end:; } diff --git a/src/test/unittest_socks.c b/src/test/unittest_socks.c index 9ba9e7e..c6039af 100644 --- a/src/test/unittest_socks.c +++ b/src/test/unittest_socks.c @@ -331,9 +331,9 @@ test_socks_socks5_request_reply(void *data) tt_assert(rep1[3] == SOCKS5_ATYP_IPV4); /* check address */ - tt_int_op(0, ==, memcmp(rep1+4, "\x7f\x00\x00\x01", 4)); + tt_mem_op(rep1+4, ==, "\x7f\x00\x00\x01", 4); /* check port */ - tt_int_op(0, ==, memcmp(rep1+4+4,"\x1c\xbd",2)); + tt_mem_op(rep1+4+4, ==, "\x1c\xbd", 2); /* emptying s->dest buffer before next test */ size_t buffer_len = evbuffer_get_length(s->dest); @@ -352,11 +352,11 @@ test_socks_socks5_request_reply(void *data) tt_assert(rep2[3] = SOCKS5_ATYP_IPV6); /* Test returned address against inet_pton(d:1:5:e:a:5:e:0) */ - tt_int_op(0, ==, memcmp(rep2+4, - "\x00\x0d\x00\x01\x00\x05\x00\x0e\x00" - "\x0a\x00\x05\x00\x0e\x00\x00", - 16)); - tt_int_op(0, ==, memcmp(rep2+4+16, "\x1c\xbd", 2)); + tt_mem_op(rep2+4, ==, + "\x00\x0d\x00\x01\x00\x05\x00\x0e\x00" + "\x0a\x00\x05\x00\x0e\x00\x00", + 16); + tt_mem_op(rep2+4+16, ==, "\x1c\xbd", 2); /* emptying dest buffer before next test */ buffer_len = evbuffer_get_length(s->dest); @@ -377,9 +377,9 @@ test_socks_socks5_request_reply(void *data) tt_assert(rep3[3] == SOCKS5_ATYP_FQDN); tt_assert(rep3[4] == strlen(fqdn)); /* check fqdn */ - tt_int_op(0, ==, memcmp(rep3+5,fqdn,strlen(fqdn))); + tt_mem_op(rep3+5, ==, fqdn,strlen(fqdn)); /* check port */ - tt_int_op(0, ==, memcmp(rep3+5+strlen(fqdn),"\x1c\xbd",2)); + tt_mem_op(rep3+5+strlen(fqdn), ==, "\x1c\xbd",2); /* Fourth test: We ask the server while having an empty parsereq and with a @@ -391,8 +391,8 @@ test_socks_socks5_request_reply(void *data) evbuffer_remove(s->dest,rep4,255); tt_assert(rep4[3] == SOCKS5_ATYP_IPV4); - tt_int_op(0, ==, memcmp(rep4+4,"\x00\x00\x00\x00",4)); - tt_int_op(0, ==, memcmp(rep4+4+4, "\x00\x00", 2)); + tt_mem_op(rep4+4, ==, "\x00\x00\x00\x00",4); + tt_mem_op(rep4+4+4, ==, "\x00\x00", 2); end:; } @@ -552,9 +552,9 @@ test_socks_socks4_request_reply(void *data) tt_assert(rep1[0] == '\x00'); tt_assert(rep1[1] == SOCKS4_SUCCESS); /* check port */ - tt_int_op(0, ==, memcmp(rep1+2,"\x1c\xbd",2)); + tt_mem_op(rep1+2, ==, "\x1c\xbd",2); /* check address */ - tt_int_op(0, ==, memcmp(rep1+2+2,"\x7f\x00\x00\x01", 4)); + tt_mem_op(rep1+2+2, ==, "\x7f\x00\x00\x01", 4); /* emptying dest buffer before next test */ size_t buffer_len = evbuffer_get_length(s->dest); @@ -574,7 +574,7 @@ test_socks_socks4_request_reply(void *data) tt_assert(rep2[1] == SOCKS4_FAILED); /* check port */ - tt_int_op(0, ==, memcmp(rep2+2,"\x1c\xbd",2)); + tt_mem_op(rep2+2, ==, "\x1c\xbd", 2); /* check address */ /* tt_str_op(rep1+2+2, ==, "www.test.example"); */

1 0

[obfsproxy/master] Switch from C-library assert to an obfs_assert/abort that go through the logging system
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 13e30cbac02e24cee9615e35d11fc71ab59fb8d1 Author: Zack Weinberg <zackw(a)panix.com> Date: Mon Jul 18 14:42:19 2011 -0700 Switch from C-library assert to an obfs_assert/abort that go through the logging system --- src/crypt.c | 5 +-- src/network.c | 19 ++++++------- src/protocol.c | 34 ++++++++++++------------ src/protocols/dummy.c | 1 - src/protocols/obfs2.c | 3 +- src/sha256.c | 4 +- src/socks.c | 15 +++++------ src/util.c | 66 ++++++++++++++++++++++++++++++++---------------- src/util.h | 20 +++++++++++++++ 9 files changed, 102 insertions(+), 65 deletions(-) diff --git a/src/crypt.c b/src/crypt.c index 722fc00..9984e24 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -6,7 +6,6 @@ #include "crypt.h" #include "util.h" -#include <assert.h> #include <fcntl.h> #include <limits.h> #include <stdlib.h> @@ -160,7 +159,7 @@ crypt_new(const uchar *key, size_t keylen) { crypt_t *k; - assert(keylen == AES_BLOCK_SIZE); + obfs_assert(keylen == AES_BLOCK_SIZE); k = xzalloc(sizeof(crypt_t)); AES_set_encrypt_key(key, AES_BLOCK_SIZE * CHAR_BIT, &k->key); @@ -173,7 +172,7 @@ crypt_new(const uchar *key, size_t keylen) void crypt_set_iv(crypt_t *key, const uchar *iv, size_t ivlen) { - assert(ivlen == sizeof(key->ivec)); + obfs_assert(ivlen == sizeof(key->ivec)); memcpy(key->ivec, iv, ivlen); } diff --git a/src/network.c b/src/network.c index fb770c9..fcbb45c 100644 --- a/src/network.c +++ b/src/network.c @@ -10,7 +10,6 @@ #include "socks.h" #include "protocol.h" -#include <assert.h> #include <errno.h> #include <stdlib.h> #include <string.h> @@ -96,7 +95,7 @@ close_all_connections(void) conn_t *conn = DOWNCAST(conn_t, dll_node, conn_list.head); conn_free(conn); /* removes it */ } - assert(!n_connections); + obfs_assert(!n_connections); } /** This function spawns a listener configured according to the @@ -226,7 +225,7 @@ simple_listener_cb(struct evconnlistener *evcl, bufferevent_setcb(conn->input, plaintext_read_cb, NULL, input_event_cb, conn); } else { - assert(conn->mode == LSN_SOCKS_CLIENT); + obfs_assert(conn->mode == LSN_SOCKS_CLIENT); bufferevent_setcb(conn->input, socks_read_cb, NULL, input_event_cb, conn); } @@ -303,7 +302,7 @@ conn_free(conn_t *conn) memset(conn, 0x99, sizeof(conn_t)); free(conn); - assert(n_connections>=0); + obfs_assert(n_connections>=0); log_debug("Connection destroyed. " "We currently have %d connections!", n_connections); @@ -336,19 +335,19 @@ socks_read_cb(struct bufferevent *bev, void *arg) conn_t *conn = arg; //struct bufferevent *other; enum socks_ret socks_ret; - assert(bev == conn->input); /* socks must be on the initial bufferevent */ + obfs_assert(bev == conn->input); /* socks must be on the initial bufferevent */ do { enum socks_status_t status = socks_state_get_status(conn->socks_state); if (status == ST_SENT_REPLY) { /* We shouldn't be here. */ - assert(0); + obfs_abort(); } else if (status == ST_HAVE_ADDR) { int af, r, port; const char *addr=NULL; r = socks_state_get_address(conn->socks_state, &af, &addr, &port); - assert(r==0); + obfs_assert(r==0); r = bufferevent_socket_connect_hostname(conn->output, get_evdns_base(), af, addr, port); @@ -461,7 +460,7 @@ static void input_event_cb(struct bufferevent *bev, short what, void *arg) { conn_t *conn = arg; - assert(bev == conn->input); + obfs_assert(bev == conn->input); if (what & (BEV_EVENT_EOF|BEV_EVENT_ERROR)) { log_warn("Got error: %s", @@ -478,7 +477,7 @@ static void output_event_cb(struct bufferevent *bev, short what, void *arg) { conn_t *conn = arg; - assert(bev == conn->output); + obfs_assert(bev == conn->output); /** If we got the BEV_EVENT_ERROR flag *AND* we are in socks mode @@ -532,7 +531,7 @@ output_event_cb(struct bufferevent *bev, short what, void *arg) struct sockaddr_storage ss; struct sockaddr *sa = (struct sockaddr*)&ss; socklen_t slen = sizeof(&ss); - assert(conn->socks_state); + obfs_assert(conn->socks_state); if (getpeername(bufferevent_getfd(bev), sa, &slen) == 0) { /* Figure out where we actually connected to so that we can tell the * socks client */ diff --git a/src/protocol.c b/src/protocol.c index 9aa1f8b..4473a94 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -5,8 +5,8 @@ #include "protocol.h" #include "protocols/obfs2.h" #include "protocols/dummy.h" +#include "util.h" -#include <assert.h> #include <stdlib.h> #include <string.h> @@ -50,7 +50,7 @@ proto_params_init(int n_options, const char *const *options) void proto_params_free(protocol_params_t *params) { - assert(params); + obfs_assert(params); if (params->target_address) free(params->target_address); @@ -70,9 +70,9 @@ proto_params_free(protocol_params_t *params) struct protocol_t * proto_create(protocol_params_t *params) { - assert(params); - assert(params->vtable); - assert(params->vtable->create); + obfs_assert(params); + obfs_assert(params->vtable); + obfs_assert(params->vtable->create); return params->vtable->create(params); } @@ -82,9 +82,9 @@ proto_create(protocol_params_t *params) */ int proto_handshake(struct protocol_t *proto, void *buf) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->handshake); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->handshake); return proto->vtable->handshake(proto, buf); } @@ -93,9 +93,9 @@ proto_handshake(struct protocol_t *proto, void *buf) { */ int proto_send(struct protocol_t *proto, void *source, void *dest) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->send); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->send); return proto->vtable->send(proto, source, dest); } @@ -104,9 +104,9 @@ proto_send(struct protocol_t *proto, void *source, void *dest) { */ enum recv_ret proto_recv(struct protocol_t *proto, void *source, void *dest) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->recv); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->recv); return proto->vtable->recv(proto, source, dest); } @@ -116,8 +116,8 @@ proto_recv(struct protocol_t *proto, void *source, void *dest) { */ void proto_destroy(struct protocol_t *proto) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->destroy); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->destroy); proto->vtable->destroy(proto); } diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index 61cdf2b..b1493ce 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -6,7 +6,6 @@ #include "../protocol.h" #include "../util.h" -#include <assert.h> #include <stdlib.h> #include <string.h> diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index c42d1c4..5acd09e 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -7,7 +7,6 @@ #include "../util.h" -#include <assert.h> #include <stdlib.h> #include <string.h> @@ -322,7 +321,7 @@ obfs2_handshake(struct protocol_t *s, struct evbuffer *buf) SEED | E_PAD_KEY( UINT32(MAGIC_VALUE) | UINT32(PADLEN) | WR(PADLEN) ) */ - assert(sizeof(magic) == 4); + obfs_assert(sizeof(magic) == 4); /* generate padlen */ if (random_bytes((uchar*)&plength, 4) < 0) diff --git a/src/sha256.c b/src/sha256.c index ff2cf21..d303f5f 100644 --- a/src/sha256.c +++ b/src/sha256.c @@ -5,7 +5,7 @@ have a SHA256. */ #include "sha256.h" -#include <assert.h> +#include "util.h" #include <string.h> #include <arpa/inet.h> /* for htonl/ntohl */ @@ -23,7 +23,7 @@ get_uint32(const void *ptr) memcpy(&val, ptr, 4); return val; } -#define LTC_ARGCHK(x) assert((x)) +#define LTC_ARGCHK(x) obfs_assert(x) #define CRYPT_OK 0 #define CRYPT_NOP -1 diff --git a/src/socks.c b/src/socks.c index b67455f..6bd708f 100644 --- a/src/socks.c +++ b/src/socks.c @@ -7,7 +7,6 @@ #include "util.h" -#include <assert.h> #include <errno.h> #include <stdlib.h> #include <string.h> @@ -189,19 +188,19 @@ socks5_handle_request(struct evbuffer *source, struct parsereq *parsereq) goto err; if (evbuffer_remove(source, destaddr, addrlen) != addrlen) - assert(0); + obfs_abort(); if (evbuffer_remove(source, (char *)&destport, 2) != 2) - assert(0); + obfs_abort(); destaddr[addrlen] = '\0'; if (af == AF_UNSPEC) { - assert(addrlen < sizeof(parsereq->addr)); + obfs_assert(addrlen < sizeof(parsereq->addr)); memcpy(parsereq->addr, destaddr, addrlen+1); } else { char a[16]; - assert(addrlen <= 16); + obfs_assert(addrlen <= 16); memcpy(a, destaddr, addrlen); if (evutil_inet_ntop(af, destaddr, parsereq->addr, sizeof(parsereq->addr)) == NULL) @@ -331,7 +330,7 @@ socks5_handle_negotiation(struct evbuffer *source, } if (evbuffer_remove(source, methods, nmethods) < 0) - assert(0); + obfs_abort(); for (found_noauth=0, i=0; i<nmethods ; i++) { if (methods[i] == SOCKS5_METHOD_NOAUTH) { @@ -477,7 +476,7 @@ handle_socks(struct evbuffer *source, struct evbuffer *dest, } /* ST_SENT_REPLY connections shouldn't be here! */ - assert(socks_state->state != ST_SENT_REPLY && + obfs_assert(socks_state->state != ST_SENT_REPLY && socks_state->state != ST_HAVE_ADDR); if (socks_state->version == 0) { @@ -527,7 +526,7 @@ handle_socks(struct evbuffer *source, struct evbuffer *dest, return SOCKS_CMD_NOT_CONNECT; } else if (r == SOCKS_BROKEN) goto broken; - assert(0); + obfs_abort(); } break; default: diff --git a/src/util.c b/src/util.c index ce25375..231c3a8 100644 --- a/src/util.c +++ b/src/util.c @@ -4,7 +4,6 @@ #include "util.h" -#include <assert.h> #include <errno.h> #include <fcntl.h> #include <limits.h> @@ -28,8 +27,7 @@ static void ATTR_NORETURN die_oom(void) { - log_warn("Memory allocation failed: %s",strerror(errno)); - exit(1); + log_error("Memory allocation failed: %s",strerror(errno)); } void * @@ -37,7 +35,7 @@ xmalloc(size_t size) { void *result; - assert(size < SIZE_T_CEILING); + obfs_assert(size < SIZE_T_CEILING); /* Some malloc() implementations return NULL when the input argument is zero. We don't bother detecting whether the implementation we're @@ -57,7 +55,7 @@ void * xrealloc(void *ptr, size_t size) { void *result; - assert (size < SIZE_T_CEILING); + obfs_assert (size < SIZE_T_CEILING); if (size == 0) size = 1; @@ -217,8 +215,8 @@ obfs_vsnprintf(char *str, size_t size, const char *format, va_list args) static void dll_insert_after(dll_t *list, dll_node_t *node, dll_node_t *new_node) { - assert(node); - assert(new_node); + obfs_assert(node); + obfs_assert(new_node); if (!list) return; @@ -238,8 +236,8 @@ dll_insert_after(dll_t *list, dll_node_t *node, dll_node_t *new_node) static void dll_insert_before(dll_t *list, dll_node_t *node, dll_node_t *new_node) { - assert(node); - assert(new_node); + obfs_assert(node); + obfs_assert(new_node); if (!list) return; @@ -266,7 +264,7 @@ dll_init(dll_t *list) static void dll_insert_beginning(dll_t *list, dll_node_t *node) { - assert(node); + obfs_assert(node); if (!list) return; @@ -288,8 +286,8 @@ dll_insert_beginning(dll_t *list, dll_node_t *node) int dll_append(dll_t *list, dll_node_t *node) { - assert(list); - assert(node); + obfs_assert(list); + obfs_assert(node); if (!list->tail) dll_insert_beginning(list, node); @@ -306,7 +304,7 @@ dll_append(dll_t *list, dll_node_t *node) void dll_remove(dll_t *list, dll_node_t *node) { - assert(node); + obfs_assert(node); if (!list) return; @@ -326,6 +324,10 @@ dll_remove(dll_t *list, dll_node_t *node) off tor. It's basicaly a stripped down version of tor's logging system. Thank you tor. */ +/* Note: obfs_assert and obfs_abort cannot be used anywhere in the + logging system, as they will recurse into the logging system and + cause an infinite loop. We use plain old abort(3) instead. */ + /* Size of maximum log entry, including newline and NULL byte. */ #define MAX_LOG_ENTRY 1024 /* String to append when a log entry doesn't fit in MAX_LOG_ENTRY. */ @@ -335,6 +337,7 @@ dll_remove(dll_t *list, dll_node_t *node) /** Logging severities */ +#define LOG_SEV_ERR 4 #define LOG_SEV_WARN 3 #define LOG_SEV_INFO 2 #define LOG_SEV_DEBUG 1 @@ -351,11 +354,12 @@ static const char * sev_to_string(int severity) { switch (severity) { + case LOG_SEV_ERR: return "error"; case LOG_SEV_WARN: return "warn"; case LOG_SEV_INFO: return "info"; case LOG_SEV_DEBUG: return "debug"; default: - assert(0); return "UNKNOWN"; + abort(); } } @@ -364,6 +368,8 @@ sev_to_string(int severity) static int string_to_sev(const char *string) { + if (!strcasecmp(string, "error")) + return LOG_SEV_ERR; if (!strcasecmp(string, "warn")) return LOG_SEV_WARN; else if (!strcasecmp(string, "info")) @@ -381,7 +387,8 @@ string_to_sev(const char *string) static int sev_is_valid(int severity) { - return (severity == LOG_SEV_WARN || + return (severity == LOG_SEV_ERR || + severity == LOG_SEV_WARN || severity == LOG_SEV_INFO || severity == LOG_SEV_DEBUG); } @@ -473,7 +480,8 @@ log_set_min_severity(const char* sev_string) static void logv(int severity, const char *format, va_list ap) { - assert(sev_is_valid(severity)); + if (!sev_is_valid(severity)) + abort(); if (logging_method == LOG_METHOD_NULL) return; @@ -500,7 +508,8 @@ logv(int severity, const char *format, va_list ap) size_t offset = buflen-TRUNCATED_STR_LEN; r = obfs_snprintf(buf+offset, TRUNCATED_STR_LEN+1, "%s", TRUNCATED_STR); - if (r < 0) assert(0); + if (r < 0) + abort(); } n = buflen; } else @@ -512,24 +521,26 @@ logv(int severity, const char *format, va_list ap) if (logging_method == LOG_METHOD_STDOUT) fprintf(stdout, "%s", buf); else if (logging_method == LOG_METHOD_FILE) { - assert(logging_logfile); + if (!logging_logfile) + abort(); if (write(logging_logfile, buf, strlen(buf)) < 0) - printf("%s(): Terrible write() error!!!\n", __func__); + abort(); } else - assert(0); + abort(); } /**** Public logging API. ****/ void -log_info(const char *format, ...) +log_error(const char *format, ...) { va_list ap; va_start(ap,format); - logv(LOG_SEV_INFO, format, ap); + logv(LOG_SEV_ERR, format, ap); va_end(ap); + exit(1); } void @@ -544,6 +555,17 @@ log_warn(const char *format, ...) } void +log_info(const char *format, ...) +{ + va_list ap; + va_start(ap,format); + + logv(LOG_SEV_INFO, format, ap); + + va_end(ap); +} + +void log_debug(const char *format, ...) { va_list ap; diff --git a/src/util.h b/src/util.h index 0693930..8e5dd77 100644 --- a/src/util.h +++ b/src/util.h @@ -98,6 +98,10 @@ void close_obfsproxy_logfile(void); /** The actual log-emitting functions */ +/** Fatal errors: the program cannot continue and will exit. */ +void log_error(const char *format, ...) + ATTR_PRINTF_1 ATTR_NORETURN; + /** Warn-level severity: for messages that only appear when something has gone wrong. */ void log_warn(const char *format, ...) @@ -113,4 +117,20 @@ void log_info(const char *format, ...) void log_debug(const char *format, ...) ATTR_PRINTF_1; +/** Assertion checking. We don't ever compile assertions out, and we + want precise control over the error messages, so we use our own + assertion macros. */ +#define obfs_assert(expr) \ + do { \ + if (!(expr)) \ + log_error("assertion failure at %s:%d: %s", \ + __FILE__, __LINE__, #expr); \ + } while (0) + +#define obfs_abort() \ + do { \ + log_error("aborted at %s:%d", __FILE__, __LINE__); \ + } while (0) + + #endif

1 0

[obfsproxy/master] Merge branch 'master' of git://git.torproject.org/obfsproxy
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit ab1b016d8a6ca5c3c7c2b79bd915eb2d02859d47 Merge: a3e63ea 17e8cb0 Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 09:57:38 2011 -0700 Merge branch 'master' of git://git.torproject.org/obfsproxy

1 0

[obfsproxy/master] Refactor crypt digest logic to reduce code duplication and overhead. Fix memory leaks in unittest_crypt.c and unittest.c.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit fc56b8b449d6be99c47447eea1060e8c2b898dde Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 11:40:20 2011 -0700 Refactor crypt digest logic to reduce code duplication and overhead. Fix memory leaks in unittest_crypt.c and unittest.c. --- src/crypt.c | 55 ++++++++------------------ src/test/unittest.c | 5 ++- src/test/unittest_crypt.c | 96 ++++++++++++++++++++------------------------ 3 files changed, 65 insertions(+), 91 deletions(-) diff --git a/src/crypt.c b/src/crypt.c index e338214..9019fc9 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -70,7 +70,13 @@ cleanup_crypto(void) Digests ===== */ -#ifdef USE_OPENSSL_SHA256 +#ifndef USE_OPENSSL_SHA256 +#define SHA256_CTX sha256_state +#define SHA256_Init(ctx) sha256_init(ctx) +#define SHA256_Update(ctx, buf, len) sha256_process(ctx, buf, len) +#define SHA256_Final(buf, ctx) sha256_done(ctx, buf) +#endif + struct digest_t { SHA256_CTX ctx; }; @@ -102,44 +108,17 @@ digest_update(digest_t *d, const uchar *buf, size_t len) size_t digest_getdigest(digest_t *d, uchar *buf, size_t len) { - uchar tmp[SHA256_LENGTH]; - int n = 32; - SHA256_Final(tmp, &d->ctx); - if (len < 32) - n = len; - memcpy(buf, tmp, n); - memset(tmp, 0, sizeof(tmp)); - return n; -} -#else -struct digest_t { - sha256_state ctx; -}; -digest_t * -digest_new(void) -{ - digest_t *d = xmalloc(sizeof(digest_t)); - sha256_init(&d->ctx); - return d; -} -void -digest_update(digest_t *d, const uchar *buf, size_t len) -{ - sha256_process(&d->ctx, buf, len); -} -size_t -digest_getdigest(digest_t *d, uchar *buf, size_t len) -{ - uchar tmp[SHA256_LENGTH]; - int n = 32; - sha256_done(&d->ctx, tmp); - if (len < 32) - n = len; - memcpy(buf, tmp, n); - memset(tmp, 0, sizeof(tmp)); - return n; + if (len >= SHA256_LENGTH) { + SHA256_Final(buf, &d->ctx); + return SHA256_LENGTH; + } else { + uchar tmp[SHA256_LENGTH]; + SHA256_Final(tmp, &d->ctx); + memcpy(buf, tmp, len); + memset(tmp, 0, SHA256_LENGTH); + return len; + } } -#endif void digest_free(digest_t *d) diff --git a/src/test/unittest.c b/src/test/unittest.c index 8974c87..f872550 100644 --- a/src/test/unittest.c +++ b/src/test/unittest.c @@ -21,6 +21,9 @@ struct testgroup_t groups[] = { int main(int argc, const char **argv) { + int rv; initialize_crypto(); - return tinytest_main(argc, argv, groups); + rv = tinytest_main(argc, argv, groups); + cleanup_crypto(); + return rv; } diff --git a/src/test/unittest_crypt.c b/src/test/unittest_crypt.c index aef4ead..112da20 100644 --- a/src/test/unittest_crypt.c +++ b/src/test/unittest_crypt.c @@ -12,63 +12,55 @@ static void test_crypt_hashvec(void *data) { + struct testvec + { + const char *input; + const char *output; + }; + static const struct testvec testvecs[] = { + /* All test vectors taken from http://csrc.nist.gov/groups/STM/cavp/#03 + Note: code below relies on there being no NUL bytes in any input. */ + /* 0 bits */ + { "", + "\xe3\xb0\xc4\x42\x98\xfc\x1c\x14\x9a\xfb\xf4\xc8\x99\x6f\xb9\x24" + "\x27\xae\x41\xe4\x64\x9b\x93\x4c\xa4\x95\x99\x1b\x78\x52\xb8\x55" }, + /* 256 bits */ + { "\x8c\xf5\x3d\x90\x07\x7d\xf9\xa0\x43\xbf\x8d\x10\xb4\x70\xb1\x44" + "\x78\x44\x11\xc9\x3a\x4d\x50\x45\x56\x83\x4d\xae\x3e\xa4\xa5\xbb", + "\x56\x05\x9e\x8c\xb3\xc2\x97\x8b\x19\x82\x08\xbf\x5c\xa1\xe1\xea" + "\x56\x59\xb7\x37\xa5\x06\x32\x4b\x7c\xec\x75\xb5\xeb\xaf\x05\x7d" }, + /* 1304 bits */ + { "\xeb\xac\xcc\x34\xd6\xd6\xd3\xd2\x1e\xd0\xad\x2b\xa7\xc0\x7c\x21" + "\xd2\x53\xc4\x81\x4f\x4a\xd8\x9d\x32\x36\x92\x37\x49\x7f\x47\xa1" + "\xad\xab\xfa\x23\x98\xdd\xd0\x9d\x76\x9c\xc4\x6d\x3f\xd6\x9c\x93" + "\x03\x25\x1c\x13\xc7\x50\x79\x9b\x8f\x15\x11\x66\xbc\x26\x58\x60" + "\x98\x71\x16\x8b\x30\xa4\xd0\xa1\x62\xf1\x83\xfb\x36\x0f\x99\xb1" + "\x72\x81\x15\x03\x68\x1a\x11\xf8\x13\xc1\x6a\x44\x62\x72\xba\x6f" + "\xd4\x85\x86\x34\x45\x33\xb9\x28\x08\x56\x51\x9c\x35\x70\x59\xc3" + "\x44\xef\x17\x18\xdb\xaf\x86\xfa\xe5\xc1\x07\x99\xe4\x6b\x53\x16" + "\x88\x6f\xb4\xe6\x80\x90\x75\x78\x90\x53\x96\x17\xe4\x03\xc5\x11" + "\xa4\xf7\x8a\x19\xc8\x18\xc2\xea\x2e\x9d\x4e\x2d\xe9\x19\x0c\x9d" + "\xdd\xb8\x06", + "\xc9\x07\x18\x04\x43\xde\xe3\xcb\xcc\xb4\xc3\x13\x28\xe6\x25\x15" + "\x85\x27\xa5\x93\xb8\x78\xde\x1b\x8e\x4b\xa3\x7f\x1d\x69\xfb\x66" }, + { NULL, NULL } + }; + digest_t *d; uchar output[32]; - - /* First SHA256 test vector: - Test for '\x00' */ - d = digest_new(); - digest_update(d, (unsigned char*)"", 0); - digest_getdigest(d, output, 32); - tt_mem_op(output, ==, - "\xe3\xb0\xc4\x42\x98\xfc\x1c\x14\x9a\xfb\xf4\xc8" - "\x99\x6f\xb9\x24\x27\xae\x41\xe4\x64\x9b\x93\x4c" - "\xa4\x95\x99\x1b\x78\x52\xb8\x55", 32); - - /* Second SHA256 test vector: - Test for the 256-bit entry of: - http://csrc.nist.gov/groups/STM/cavp/#03 */ - d = digest_new(); - digest_update(d, - (unsigned char*)"\x8c\xf5\x3d\x90\x07\x7d\xf9\xa0\x43\xbf\x8d" - "\x10\xb4\x70\xb1\x44\x78\x44\x11\xc9\x3a\x4d\x50\x45\x56\x83" - "\x4d\xae\x3e\xa4\xa5\xbb", 32); - digest_getdigest(d, output, 32); - tt_mem_op(output, ==, - "\x56\x05\x9e\x8c\xb3\xc2\x97\x8b\x19\x82\x08\xbf" - "\x5c\xa1\xe1\xea\x56\x59\xb7\x37\xa5\x06\x32\x4b" - "\x7c\xec\x75\xb5\xeb\xaf\x05\x7d", 32); - - /* Third SHA test vector: - Test for the 1304-bit entry of: - http://csrc.nist.gov/groups/STM/cavp/#03 */ - d = digest_new(); - digest_update(d, - (unsigned char*)"\xeb\xac\xcc\x34\xd6\xd6\xd3\xd2\x1e\xd0\xad" - "\x2b\xa7\xc0\x7c\x21\xd2\x53\xc4\x81\x4f\x4a\xd8\x9d\x32\x36" - "\x92\x37\x49\x7f\x47\xa1\xad\xab\xfa\x23\x98\xdd\xd0\x9d\x76" - "\x9c\xc4\x6d\x3f\xd6\x9c\x93\x03\x25\x1c\x13\xc7\x50\x79\x9b" - "\x8f\x15\x11\x66\xbc\x26\x58\x60\x98\x71\x16\x8b\x30\xa4\xd0" - "\xa1\x62\xf1\x83\xfb\x36\x0f\x99\xb1\x72\x81\x15\x03\x68\x1a" - "\x11\xf8\x13\xc1\x6a\x44\x62\x72\xba\x6f\xd4\x85\x86\x34\x45" - "\x33\xb9\x28\x08\x56\x51\x9c\x35\x70\x59\xc3\x44\xef\x17\x18" - "\xdb\xaf\x86\xfa\xe5\xc1\x07\x99\xe4\x6b\x53\x16\x88\x6f\xb4" - "\xe6\x80\x90\x75\x78\x90\x53\x96\x17\xe4\x03\xc5\x11\xa4\xf7" - "\x8a\x19\xc8\x18\xc2\xea\x2e\x9d\x4e\x2d\xe9\x19\x0c\x9d\xdd" - "\xb8\x06", 163); - digest_getdigest(d, output, 32); - tt_mem_op(output, ==, - "\xc9\x07\x18\x04\x43\xde\xe3\xcb\xcc\xb4\xc3\x13" - "\x28\xe6\x25\x15\x85\x27\xa5\x93\xb8\x78\xde\x1b" - "\x8e\x4b\xa3\x7f\x1d\x69\xfb\x66", 32); + int i; + for (i = 0; testvecs[i].input; i++) { + d = digest_new(); + digest_update(d, (unsigned char *) testvecs[i].input, + strlen(testvecs[i].input)); + digest_getdigest(d, output, 32); + digest_free(d); + tt_mem_op(output, ==, testvecs[i].output, 32); + } /* XXX Try doing init, update, update, output. */ - /* XXX add a base16-decode function so we can implement a tt_mem_op or - something */ - end: - if (d) - digest_free(d); + end:; } static void

1 0

[obfsproxy/master] Fix minor memory leaks in protocol-specific option parsing and a major one in obfs2.c:digest_new.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 2dd47ce6624d374932f7c212b1f719ad09143c5e Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 11:56:42 2011 -0700 Fix minor memory leaks in protocol-specific option parsing and a major one in obfs2.c:digest_new. --- src/protocols/dummy.c | 2 +- src/protocols/obfs2.c | 4 +++- 2 files changed, 4 insertions(+), 2 deletions(-) diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index c65f7b5..578182a 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -31,7 +31,7 @@ dummy_init(int n_options, const char *const *options) = xzalloc(sizeof(struct protocol_params_t)); if (parse_and_set_options(n_options, options, params) < 0) { - free(params); + proto_params_free(params); usage(); return NULL; } diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 5c9aedc..6688ebf 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -6,6 +6,7 @@ #define PROTOCOL_OBFS2_PRIVATE #include "obfs2.h" +#include "../protocol.h" #include <stdlib.h> #include <string.h> @@ -37,8 +38,8 @@ obfs2_init(int n_options, const char *const *options) = xzalloc(sizeof(struct protocol_params_t)); if (parse_and_set_options(n_options, options, params) < 0) { + proto_params_free(params); usage(); - free(params); return NULL; } @@ -181,6 +182,7 @@ derive_key(void *s, const char *keytype) d = digest_new(); digest_update(d, buf, sizeof(buf)); digest_getdigest(d, buf, sizeof(buf)); + digest_free(d); } }

1 0

[obfsproxy/master] Import container library from Tor.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit a76f6457e330d14d09d490d2c73f47ac2c7369c6 Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 09:56:07 2011 -0700 Import container library from Tor. * src/container.c, src/container.h, src/ht.h, src/test/unittest_container.c: New files. * Makefile.am: Add new files (and some old files that got missed). * src/test/unittest.c: Add test group for container library. * configure.ac: Check size of int. Check for 'inline'. * util.h: Include stdint.h (unconditionally for now). (xstrndup, ui64_log2, ascii_isspace, ascii_strstrip, ascii_strlower): New functions required by container.c. * util.c: Define said new functions. * crypt.h, crypt.c (random_int): Another function needed by container.c. --- Makefile.am | 5 + configure.ac | 18 +- src/container.c | 1441 +++++++++++++++++++++++++++++++++++++++++ src/container.h | 685 ++++++++++++++++++++ src/crypt.c | 24 + src/crypt.h | 5 + src/ht.h | 471 ++++++++++++++ src/test/unittest.c | 2 + src/test/unittest_container.c | 772 ++++++++++++++++++++++ src/util.c | 74 +++ src/util.h | 19 +- 11 files changed, 3514 insertions(+), 2 deletions(-) diff --git a/Makefile.am b/Makefile.am index 521ba24..ff518ad 100644 --- a/Makefile.am +++ b/Makefile.am @@ -9,6 +9,7 @@ noinst_LIBRARIES = libobfsproxy.a noinst_PROGRAMS = unittests libobfsproxy_a_SOURCES = \ + src/container.c \ src/crypt.c \ src/network.c \ src/protocol.c \ @@ -26,12 +27,16 @@ obfsproxy_SOURCES = \ unittests_SOURCES = \ src/test/tinytest.c \ src/test/unittest.c \ + src/test/unittest_container.c \ src/test/unittest_crypt.c \ src/test/unittest_obfs2.c \ src/test/unittest_socks.c noinst_HEADERS = \ + src/container.h \ src/crypt.h \ + src/ht.h \ + src/main.h \ src/network.h \ src/protocol.h \ src/sha256.h \ diff --git a/configure.ac b/configure.ac index 32b7138..fc82507 100644 --- a/configure.ac +++ b/configure.ac @@ -1,13 +1,22 @@ AC_PREREQ([2.61])dnl Possibly earlier will do, but this is what I have AC_INIT([obsproxy], [0.0]) AC_CONFIG_SRCDIR([src/main.c]) - AM_INIT_AUTOMAKE([foreign]) +dnl The stock definition of AC_INCLUDES_DEFAULT performs a whole bunch +dnl of completely unnecessary checks *even if* you override its +dnl mostly-useless default header list at invocation time. +dnl Replace it with a version that does nothing unless requested. +m4_pushdef([AC_INCLUDES_DEFAULT], [$1]) + +### Programs ### + AC_PROG_CC AC_PROG_RANLIB PKG_PROG_PKG_CONFIG +### Libraries ### + PKG_CHECK_MODULES([libevent], [libevent >= 2.0]) # Presently no need for libssl, only libcrypto. PKG_CHECK_MODULES([libcrypto], [libcrypto >= 0.9.7]) @@ -28,6 +37,13 @@ LIBS="$libevent_LIBS $libcrypto_LIBS" AX_LIB_WINSOCK2 LIBS="$save_LIBS" +### C features ### + +AC_C_INLINE +AC_CHECK_SIZEOF(int) + +### Output ### + AC_CONFIG_FILES([Makefile]) AC_CONFIG_HEADERS([config.h]) AC_OUTPUT diff --git a/src/container.c b/src/container.c new file mode 100644 index 0000000..b66a819 --- /dev/null +++ b/src/container.c @@ -0,0 +1,1441 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file container.c + * \brief Implements a smartlist (a resizable array) along + * with helper functions to use smartlists. Also includes + * hash table implementations of a string-to-void* map, and of + * a digest-to-void* map. + **/ + +#include "util.h" +#include "container.h" +#include "crypt.h" +#include "ht.h" + +/** All newly allocated smartlists have this capacity. */ +#define SMARTLIST_DEFAULT_CAPACITY 16 + +/** Allocate and return an empty smartlist. + */ +smartlist_t * +smartlist_create(void) +{ + smartlist_t *sl = xmalloc(sizeof(smartlist_t)); + sl->num_used = 0; + sl->capacity = SMARTLIST_DEFAULT_CAPACITY; + sl->list = xmalloc(sizeof(void *) * sl->capacity); + return sl; +} + +/** Deallocate a smartlist. Does not release storage associated with the + * list's elements. + */ +void +smartlist_free(smartlist_t *sl) +{ + if (!sl) + return; + free(sl->list); + free(sl); +} + +/** Remove all elements from the list. + */ +void +smartlist_clear(smartlist_t *sl) +{ + sl->num_used = 0; +} + +/** Make sure that sl can hold at least size entries. */ +static inline void +smartlist_ensure_capacity(smartlist_t *sl, int size) +{ + if (size > sl->capacity) { + int higher = sl->capacity * 2; + while (size > higher) + higher *= 2; + obfs_assert(higher > 0); /* detect overflow */ + sl->capacity = higher; + sl->list = xrealloc(sl->list, sizeof(void*)*sl->capacity); + } +} + +/** Append element to the end of the list. */ +void +smartlist_add(smartlist_t *sl, void *element) +{ + smartlist_ensure_capacity(sl, sl->num_used+1); + sl->list[sl->num_used++] = element; +} + +/** Append each element from S2 to the end of S1. */ +void +smartlist_add_all(smartlist_t *s1, const smartlist_t *s2) +{ + int new_size = s1->num_used + s2->num_used; + obfs_assert(new_size >= s1->num_used); /* check for overflow. */ + smartlist_ensure_capacity(s1, new_size); + memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*)); + s1->num_used = new_size; +} + +/** Remove all elements E from sl such that E==element. Preserve + * the order of any elements before E, but elements after E can be + * rearranged. + */ +void +smartlist_remove(smartlist_t *sl, const void *element) +{ + int i; + if (element == NULL) + return; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) { + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + } +} + +/** If sl is nonempty, remove and return the final element. Otherwise, + * return NULL. */ +void * +smartlist_pop_last(smartlist_t *sl) +{ + obfs_assert(sl); + if (sl->num_used) + return sl->list[--sl->num_used]; + else + return NULL; +} + +/** Reverse the order of the items in sl. */ +void +smartlist_reverse(smartlist_t *sl) +{ + int i, j; + void *tmp; + obfs_assert(sl); + for (i = 0, j = sl->num_used-1; i < j; ++i, --j) { + tmp = sl->list[i]; + sl->list[i] = sl->list[j]; + sl->list[j] = tmp; + } +} + +/** If there are any strings in sl equal to element, remove and free them. + * Does not preserve order. */ +void +smartlist_string_remove(smartlist_t *sl, const char *element) +{ + int i; + obfs_assert(sl); + obfs_assert(element); + for (i = 0; i < sl->num_used; ++i) { + if (!strcmp(element, sl->list[i])) { + free(sl->list[i]); + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + } + } +} + +/** Return true iff some element E of sl has E==element. + */ +int +smartlist_isin(const smartlist_t *sl, const void *element) +{ + int i; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) + return 1; + return 0; +} + +/** Return true iff sl has some element E such that + * !strcmp(E,element) + */ +int +smartlist_string_isin(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** If element is equal to an element of sl, return that + * element's index. Otherwise, return -1. */ +int +smartlist_string_pos(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return -1; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return i; + return -1; +} + +/** Return true iff sl has some element E such that + * !strcasecmp(E,element) + */ +int +smartlist_string_isin_case(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcasecmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** Return true iff sl has some element E such that E is equal + * to the decimal encoding of num. + */ +int +smartlist_string_num_isin(const smartlist_t *sl, int num) +{ + char buf[32]; /* long enough for 64-bit int, and then some. */ + obfs_snprintf(buf,sizeof(buf),"%d", num); + return smartlist_string_isin(sl, buf); +} + +/** Return true iff the two lists contain the same strings in the same + * order, or if they are both NULL. */ +int +smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2) +{ + if (sl1 == NULL) + return sl2 == NULL; + if (sl2 == NULL) + return 0; + if (smartlist_len(sl1) != smartlist_len(sl2)) + return 0; + SMARTLIST_FOREACH(sl1, const char *, cp1, { + const char *cp2 = smartlist_get(sl2, cp1_sl_idx); + if (strcmp(cp1, cp2)) + return 0; + }); + return 1; +} + +/** Return true iff sl has some element E such that + * !memcmp(E,element,SHA256_LENGTH) + */ +int +smartlist_digest_isin(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (!memcmp((const char*)sl->list[i],element,SHA256_LENGTH)) + return 1; + return 0; +} + +/** Return true iff some element E of sl2 has smartlist_isin(sl1,E). + */ +int +smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl2->num_used; i++) + if (smartlist_isin(sl1, sl2->list[i])) + return 1; + return 0; +} + +/** Remove every element E of sl1 such that !smartlist_isin(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl1->num_used; i++) + if (!smartlist_isin(sl2, sl1->list[i])) { + sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + } +} + +/** Remove every element E of sl1 such that smartlist_isin(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl2->num_used; i++) + smartlist_remove(sl1, sl2->list[i]); +} + +/** Remove the idxth element of sl; if idx is not the last + * element, swap the last element of sl into the idxth space. + */ +void +smartlist_del(smartlist_t *sl, int idx) +{ + obfs_assert(sl); + obfs_assert(idx>=0); + obfs_assert(idx < sl->num_used); + sl->list[idx] = sl->list[--sl->num_used]; +} + +/** Remove the idxth element of sl; if idx is not the last element, + * moving all subsequent elements back one space. Return the old value + * of the idxth element. + */ +void +smartlist_del_keeporder(smartlist_t *sl, int idx) +{ + obfs_assert(sl); + obfs_assert(idx>=0); + obfs_assert(idx < sl->num_used); + --sl->num_used; + if (idx < sl->num_used) + memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx)); +} + +/** Insert the value val as the new idxth element of + * sl, moving all items previously at idx or later + * forward one space. + */ +void +smartlist_insert(smartlist_t *sl, int idx, void *val) +{ + obfs_assert(sl); + obfs_assert(idx>=0); + obfs_assert(idx <= sl->num_used); + if (idx == sl->num_used) { + smartlist_add(sl, val); + } else { + smartlist_ensure_capacity(sl, sl->num_used+1); + /* Move other elements away */ + if (idx < sl->num_used) + memmove(sl->list + idx + 1, sl->list + idx, + sizeof(void*)*(sl->num_used-idx)); + sl->num_used++; + sl->list[idx] = val; + } +} + +/** + * Split a string str along all occurrences of sep, + * appending the (newly allocated) split strings, in order, to + * sl. Return the number of strings added to sl. + * + * If flags&SPLIT_SKIP_SPACE is true, remove initial and + * trailing space from each entry. + * If flags&SPLIT_IGNORE_BLANK is true, remove any entries + * of length 0. + * If flags&SPLIT_STRIP_SPACE is true, strip spaces from each + * split string. + * + * If max\>0, divide the string into no more than max pieces. If + * sep is NULL, split on any sequence of horizontal space. + */ +int +smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, + int flags, int max) +{ + const char *cp, *end, *next; + int n = 0; + + obfs_assert(sl); + obfs_assert(str); + + cp = str; + while (1) { + if (flags&SPLIT_SKIP_SPACE) { + while (ascii_isspace(*cp)) ++cp; + } + + if (max>0 && n == max-1) { + end = strchr(cp,'\0'); + } else if (sep) { + end = strstr(cp,sep); + if (!end) + end = strchr(cp,'\0'); + } else { + for (end = cp; *end && *end != '\t' && *end != ' '; ++end) + ; + } + + obfs_assert(end); + + if (!*end) { + next = NULL; + } else if (sep) { + next = end+strlen(sep); + } else { + next = end+1; + while (*next == '\t' || *next == ' ') + ++next; + } + + if (flags&SPLIT_SKIP_SPACE) { + while (end > cp && ascii_isspace(*(end-1))) + --end; + } + if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) { + char *string = xstrndup(cp, end-cp); + if (flags&SPLIT_STRIP_SPACE) + ascii_strstrip(string, " "); + smartlist_add(sl, string); + ++n; + } + if (!next) + break; + cp = next; + } + + return n; +} + +/** Allocate and return a new string containing the concatenation of + * the elements of sl, in order, separated by join. If + * terminate is true, also terminate the string with join. + * If len_out is not NULL, set len_out to the length of + * the returned string. Requires that every element of sl is + * NUL-terminated string. + */ +char * +smartlist_join_strings(smartlist_t *sl, const char *join, + int terminate, size_t *len_out) +{ + return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out); +} + +/** As smartlist_join_strings, but instead of separating/terminated with a + * NUL-terminated string join, uses the join_len-byte sequence + * at join. (Useful for generating a sequence of NUL-terminated + * strings.) + */ +char * +smartlist_join_strings2(smartlist_t *sl, const char *join, + size_t join_len, int terminate, size_t *len_out) +{ + int i; + size_t n = 0; + char *r = NULL, *dst, *src; + + obfs_assert(sl); + obfs_assert(join); + + if (terminate) + n = join_len; + + for (i = 0; i < sl->num_used; ++i) { + n += strlen(sl->list[i]); + if (i+1 < sl->num_used) /* avoid double-counting the last one */ + n += join_len; + } + dst = r = xmalloc(n+1); + for (i = 0; i < sl->num_used; ) { + for (src = sl->list[i]; *src; ) + *dst++ = *src++; + if (++i < sl->num_used) { + memcpy(dst, join, join_len); + dst += join_len; + } + } + if (terminate) { + memcpy(dst, join, join_len); + dst += join_len; + } + *dst = '\0'; + + if (len_out) + *len_out = dst-r; + return r; +} + +/** Sort the members of sl into an order defined by + * the ordering function compare, which returns less then 0 if a + * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b. + */ +void +smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)) +{ + if (!sl->num_used) + return; + qsort(sl->list, sl->num_used, sizeof(void*), + (int (*)(const void *,const void*))compare); +} + +/** Given a smartlist sl sorted with the function compare, + * return the most frequent member in the list. Break ties in favor of + * later elements. If the list is empty, return NULL. + */ +void * +smartlist_get_most_frequent(const smartlist_t *sl, + int (*compare)(const void **a, const void **b)) +{ + const void *most_frequent = NULL; + int most_frequent_count = 0; + + const void *cur = NULL; + int i, count=0; + + if (!sl->num_used) + return NULL; + for (i = 0; i < sl->num_used; ++i) { + const void *item = sl->list[i]; + if (cur && 0 == compare(&cur, &item)) { + ++count; + } else { + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + cur = item; + count = 1; + } + } + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + return (void*)most_frequent; +} + +/** Given a sorted smartlist sl and the comparison function used to + * sort it, remove all duplicate members. If free_fn is provided, calls + * free_fn on each duplicate. Otherwise, just removes them. Preserves order. + */ +void +smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *a)) +{ + int i; + for (i=1; i < sl->num_used; ++i) { + if (compare((const void **)&(sl->list[i-1]), + (const void **)&(sl->list[i])) == 0) { + if (free_fn) + free_fn(sl->list[i]); + smartlist_del_keeporder(sl, i--); + } + } +} + +/** Return a randomly chosen element of sl; or NULL if sl + * is empty. */ + +void * +smartlist_choose(const smartlist_t *sl) +{ + int len = smartlist_len(sl); + if (len) + return smartlist_get(sl, random_int(len)); + return NULL; /* no elements to choose from */ +} + +/** Scramble the elements of sl into a random order. */ +void +smartlist_shuffle(smartlist_t *sl) +{ + int i; + + /* From the end of the list to the front, choose at random from the + positions we haven't looked at yet, and swap that position into the + current position. Remember to give "no swap" the same probability as + any other swap. */ + for (i = smartlist_len(sl)-1; i > 0; --i) { + int j = random_int(i+1); + smartlist_swap(sl, i, j); + } +} + + +/** Assuming the members of sl are in order, return a pointer to the + * member that matches key. Ordering and matching are defined by a + * compare function that returns 0 on a match; less than 0 if key is + * less than member, and greater than 0 if key is greater then member. + */ +void * +smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)) +{ + int found, idx; + idx = smartlist_bsearch_idx(sl, key, compare, &found); + return found ? smartlist_get(sl, idx) : NULL; +} + +/** Assuming the members of sl are in order, return the index of the + * member that matches key. If no member matches, return the index of + * the first member greater than key, or smartlist_len(sl) if no member + * is greater than key. Set found_out to true on a match, to + * false otherwise. Ordering and matching are defined by a compare + * function that returns 0 on a match; less than 0 if key is less than member, + * and greater than 0 if key is greater then member. + */ +int +smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out) +{ + int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid; + + while (lo <= hi) { + mid = (lo + hi) / 2; + cmp = compare(key, (const void**) &(sl->list[mid])); + if (cmp>0) { /* key > sl[mid] */ + lo = mid+1; + } else if (cmp<0) { /* key < sl[mid] */ + hi = mid-1; + } else { /* key == sl[mid] */ + *found_out = 1; + return mid; + } + } + /* lo > hi. */ + { + obfs_assert(lo >= 0); + if (lo < smartlist_len(sl)) { + cmp = compare(key, (const void**) &(sl->list[lo])); + obfs_assert(cmp < 0); + } else if (smartlist_len(sl)) { + cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1])); + obfs_assert(cmp > 0); + } + } + *found_out = 0; + return lo; +} + +/** Helper: compare two const char **s. */ +static int +_compare_string_ptrs(const void **_a, const void **_b) +{ + return strcmp((const char*)*_a, (const char*)*_b); +} + +/** Sort a smartlist sl containing strings into lexically ascending + * order. */ +void +smartlist_sort_strings(smartlist_t *sl) +{ + smartlist_sort(sl, _compare_string_ptrs); +} + +/** Return the most frequent string in the sorted list sl */ +char * +smartlist_get_most_frequent_string(smartlist_t *sl) +{ + return smartlist_get_most_frequent(sl, _compare_string_ptrs); +} + +/** Remove duplicate strings from a sorted list, and free them with free(). + */ +void +smartlist_uniq_strings(smartlist_t *sl) +{ + smartlist_uniq(sl, _compare_string_ptrs, free); +} + +/* Heap-based priority queue implementation for O(lg N) insert and remove. + * Recall that the heap property is that, for every index I, h[I] < + * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]]. + * + * For us to remove items other than the topmost item, each item must store + * its own index within the heap. When calling the pqueue functions, tell + * them about the offset of the field that stores the index within the item. + * + * Example: + * + * typedef struct timer_t { + * struct timeval tv; + * int heap_index; + * } timer_t; + * + * static int compare(const void *p1, const void *p2) { + * const timer_t *t1 = p1, *t2 = p2; + * if (t1->tv.tv_sec < t2->tv.tv_sec) { + * return -1; + * } else if (t1->tv.tv_sec > t2->tv.tv_sec) { + * return 1; + * } else { + * return t1->tv.tv_usec - t2->tv_usec; + * } + * } + * + * void timer_heap_insert(smartlist_t *heap, timer_t *timer) { + * smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index), + * timer); + * } + * + * void timer_heap_pop(smartlist_t *heap) { + * return smartlist_pqueue_pop(heap, compare, + * STRUCT_OFFSET(timer_t, heap_index)); + * } + */ + +/** @{ */ +/** Functions to manipulate heap indices to find a node's parent and children. + * + * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x] + * = 2*x + 1. But this is C, so we have to adjust a little. */ +//#define LEFT_CHILD(i) ( ((i)+1)*2 - 1) +//#define RIGHT_CHILD(i) ( ((i)+1)*2 ) +//#define PARENT(i) ( ((i)+1)/2 - 1) +#define LEFT_CHILD(i) ( 2*(i) + 1 ) +#define RIGHT_CHILD(i) ( 2*(i) + 2 ) +#define PARENT(i) ( ((i)-1) / 2 ) +/** }@ */ + +/** @{ */ +/** Helper macros for heaps: Given a local variable idx_field_offset + * set to the offset of an integer index within the heap element structure, + * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to + * where p's index is stored. Given additionally a local smartlist sl, + * UPDATE_IDX(i) sets the index of the element at i to the correct + * value (that is, to i). + */ +#define IDXP(p) ((int*)( ((char*)(p)) + idx_field_offset )) + +#define UPDATE_IDX(i) do { \ + void *updated = sl->list[i]; \ + *IDXP(updated) = i; \ + } while (0) + +#define IDX_OF_ITEM(p) (*IDXP(p)) +/** @} */ + +/** Helper. sl may have at most one violation of the heap property: + * the item at idx may be greater than one or both of its children. + * Restore the heap property. */ +static inline void +smartlist_heapify(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + int idx) +{ + while (1) { + int left_idx = LEFT_CHILD(idx); + int best_idx; + + if (left_idx >= sl->num_used) + return; + if (compare(sl->list[idx],sl->list[left_idx]) < 0) + best_idx = idx; + else + best_idx = left_idx; + if (left_idx+1 < sl->num_used && + compare(sl->list[left_idx+1],sl->list[best_idx]) < 0) + best_idx = left_idx + 1; + + if (best_idx == idx) { + return; + } else { + void *tmp = sl->list[idx]; + sl->list[idx] = sl->list[best_idx]; + sl->list[best_idx] = tmp; + UPDATE_IDX(idx); + UPDATE_IDX(best_idx); + + idx = best_idx; + } + } +} + +/** Insert item into the heap stored in sl, where order is + * determined by compare and the offset of the item in the heap is + * stored in an int-typed field at position idx_field_offset within + * item. + */ +void +smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx; + smartlist_add(sl,item); + UPDATE_IDX(sl->num_used-1); + + for (idx = sl->num_used - 1; idx; ) { + int parent = PARENT(idx); + if (compare(sl->list[idx], sl->list[parent]) < 0) { + void *tmp = sl->list[parent]; + sl->list[parent] = sl->list[idx]; + sl->list[idx] = tmp; + UPDATE_IDX(parent); + UPDATE_IDX(idx); + idx = parent; + } else { + return; + } + } +} + +/** Remove and return the top-priority item from the heap stored in sl, + * where order is determined by compare and the item's position is + * stored at position idx_field_offset within the item. sl must + * not be empty. */ +void * +smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + void *top; + obfs_assert(sl->num_used); + + top = sl->list[0]; + *IDXP(top)=-1; + if (--sl->num_used) { + sl->list[0] = sl->list[sl->num_used]; + UPDATE_IDX(0); + smartlist_heapify(sl, compare, idx_field_offset, 0); + } + return top; +} + +/** Remove the item item from the heap stored in sl, + * where order is determined by compare and the item's position is + * stored at position idx_field_offset within the item. sl must + * not be empty. */ +void +smartlist_pqueue_remove(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx = IDX_OF_ITEM(item); + obfs_assert(idx >= 0); + obfs_assert(sl->list[idx] == item); + --sl->num_used; + *IDXP(item) = -1; + if (idx == sl->num_used) { + return; + } else { + sl->list[idx] = sl->list[sl->num_used]; + UPDATE_IDX(idx); + smartlist_heapify(sl, compare, idx_field_offset, idx); + } +} + +/** Assert that the heap property is correctly maintained by the heap stored + * in sl, where order is determined by compare. */ +void +smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + int i; + for (i = sl->num_used - 1; i >= 0; --i) { + if (i>0) + obfs_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0); + obfs_assert(IDX_OF_ITEM(sl->list[i]) == i); + } +} + +/** Helper: compare two SHA256_LENGTH digests. */ +static int +_compare_digests(const void **_a, const void **_b) +{ + return memcmp((const char*)*_a, (const char*)*_b, SHA256_LENGTH); +} + +/** Sort the list of SHA256_LENGTH-byte digests into ascending order. */ +void +smartlist_sort_digests(smartlist_t *sl) +{ + smartlist_sort(sl, _compare_digests); +} + +/** Remove duplicate digests from a sorted list, and free them with free(). + */ +void +smartlist_uniq_digests(smartlist_t *sl) +{ + smartlist_uniq(sl, _compare_digests, free); +} + +/** Helper: Declare an entry type and a map type to implement a mapping using + * ht.h. The map type will be called maptype. The key part of each + * entry is declared using the C declaration keydecl. All functions + * and types associated with the map get prefixed with prefix */ +#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \ + typedef struct prefix ## entry_t { \ + HT_ENTRY(prefix ## entry_t) node; \ + void *val; \ + keydecl; \ + } prefix ## entry_t; \ + struct maptype { \ + HT_HEAD(prefix ## impl, prefix ## entry_t) head; \ + } + +DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_); +DEFINE_MAP_STRUCTS(digestmap_t, char key[SHA256_LENGTH], digestmap_); + +/** Helper: compare strmap_entry_t objects by key value. */ +static inline int +strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b) +{ + return !strcmp(a->key, b->key); +} + +/** Helper: return a hash value for a strmap_entry_t. */ +static inline unsigned int +strmap_entry_hash(const strmap_entry_t *a) +{ + return ht_string_hash(a->key); +} + +/** Helper: compare digestmap_entry_t objects by key value. */ +static inline int +digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b) +{ + return !memcmp(a->key, b->key, SHA256_LENGTH); +} + +/** Helper: return a hash value for a digest_map_t. */ +static inline unsigned int +digestmap_entry_hash(const digestmap_entry_t *a) +{ +#if SIZEOF_INT != 8 + const uint32_t *p = (const uint32_t*)a->key; + return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]; +#else + const uint64_t *p = (const uint64_t*)a->key; + return p[0] ^ p[1]; +#endif +} + +HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq) +HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq, 0.6, malloc, realloc, free) + +HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq) +HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq, 0.6, malloc, realloc, free) + +/** Constructor to create a new empty map from strings to void*'s. + */ +strmap_t * +strmap_new(void) +{ + strmap_t *result; + result = xmalloc(sizeof(strmap_t)); + HT_INIT(strmap_impl, &result->head); + return result; +} + +/** Constructor to create a new empty map from digests to void*'s. + */ +digestmap_t * +digestmap_new(void) +{ + digestmap_t *result; + result = xmalloc(sizeof(digestmap_t)); + HT_INIT(digestmap_impl, &result->head); + return result; +} + +/** Set the current value for key to val. Returns the previous + * value for key if one was set, or NULL if one was not. + * + * This function makes a copy of key if necessary, but not of + * val. + */ +void * +strmap_set(strmap_t *map, const char *key, void *val) +{ + strmap_entry_t *resolve; + strmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + obfs_assert(val); + search.key = (char*)key; + resolve = HT_FIND(strmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + resolve->val = val; + return oldval; + } else { + resolve = xzalloc(sizeof(strmap_entry_t)); + resolve->key = xstrdup(key); + resolve->val = val; + obfs_assert(!HT_FIND(strmap_impl, &map->head, resolve)); + HT_INSERT(strmap_impl, &map->head, resolve); + return NULL; + } +} + +#define OPTIMIZED_DIGESTMAP_SET + +/** Like strmap_set() above but for digestmaps. */ +void * +digestmap_set(digestmap_t *map, const char *key, void *val) +{ +#ifndef OPTIMIZED_DIGESTMAP_SET + digestmap_entry_t *resolve; +#endif + digestmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + obfs_assert(val); + memcpy(&search.key, key, SHA256_LENGTH); +#ifndef OPTIMIZED_DIGESTMAP_SET + resolve = HT_FIND(digestmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + resolve->val = val; + return oldval; + } else { + resolve = xzalloc(sizeof(digestmap_entry_t)); + memcpy(resolve->key, key, SHA256_LENGTH); + resolve->val = val; + HT_INSERT(digestmap_impl, &map->head, resolve); + return NULL; + } +#else + /* We spend up to 5% of our time in this function, so the code below is + * meant to optimize the check/alloc/set cycle by avoiding the two trips to + * the hash table that we do in the unoptimized code above. (Each of + * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.) + */ + _HT_FIND_OR_INSERT(digestmap_impl, node, digestmap_entry_hash, &(map->head), + digestmap_entry_t, &search, ptr, + { + /* we found an entry. */ + oldval = (*ptr)->val; + (*ptr)->val = val; + return oldval; + }, + { + /* We didn't find the entry. */ + digestmap_entry_t *newent = + xzalloc(sizeof(digestmap_entry_t)); + memcpy(newent->key, key, SHA256_LENGTH); + newent->val = val; + _HT_FOI_INSERT(node, &(map->head), &search, newent, ptr); + return NULL; + }); +#endif +} + +/** Return the current value associated with key, or NULL if no + * value is set. + */ +void * +strmap_get(const strmap_t *map, const char *key) +{ + strmap_entry_t *resolve; + strmap_entry_t search; + obfs_assert(map); + obfs_assert(key); + search.key = (char*)key; + resolve = HT_FIND(strmap_impl, &map->head, &search); + if (resolve) { + return resolve->val; + } else { + return NULL; + } +} + +/** Like strmap_get() above but for digestmaps. */ +void * +digestmap_get(const digestmap_t *map, const char *key) +{ + digestmap_entry_t *resolve; + digestmap_entry_t search; + obfs_assert(map); + obfs_assert(key); + memcpy(&search.key, key, SHA256_LENGTH); + resolve = HT_FIND(digestmap_impl, &map->head, &search); + if (resolve) { + return resolve->val; + } else { + return NULL; + } +} + +/** Remove the value currently associated with key from the map. + * Return the value if one was set, or NULL if there was no entry for + * key. + * + * Note: you must free any storage associated with the returned value. + */ +void * +strmap_remove(strmap_t *map, const char *key) +{ + strmap_entry_t *resolve; + strmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + search.key = (char*)key; + resolve = HT_REMOVE(strmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + free(resolve->key); + free(resolve); + return oldval; + } else { + return NULL; + } +} + +/** Like strmap_remove() above but for digestmaps. */ +void * +digestmap_remove(digestmap_t *map, const char *key) +{ + digestmap_entry_t *resolve; + digestmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + memcpy(&search.key, key, SHA256_LENGTH); + resolve = HT_REMOVE(digestmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + free(resolve); + return oldval; + } else { + return NULL; + } +} + +/** Same as strmap_set, but first converts key to lowercase. */ +void * +strmap_set_lc(strmap_t *map, const char *key, void *val) +{ + /* We could be a little faster by using strcasecmp instead, and a separate + * type, but I don't think it matters. */ + void *v; + char *lc_key = xstrdup(key); + ascii_strlower(lc_key); + v = strmap_set(map,lc_key,val); + free(lc_key); + return v; +} + +/** Same as strmap_get, but first converts key to lowercase. */ +void * +strmap_get_lc(const strmap_t *map, const char *key) +{ + void *v; + char *lc_key = xstrdup(key); + ascii_strlower(lc_key); + v = strmap_get(map,lc_key); + free(lc_key); + return v; +} + +/** Same as strmap_remove, but first converts key to lowercase */ +void * +strmap_remove_lc(strmap_t *map, const char *key) +{ + void *v; + char *lc_key = xstrdup(key); + ascii_strlower(lc_key); + v = strmap_remove(map,lc_key); + free(lc_key); + return v; +} + +/** return an iterator pointer to the front of a map. + * + * Iterator example: + * + * \code + * // uppercase values in "map", removing empty values. + * + * strmap_iter_t *iter; + * const char *key; + * void *val; + * char *cp; + * + * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { + * strmap_iter_get(iter, &key, &val); + * cp = (char*)val; + * if (!*cp) { + * iter = strmap_iter_next_rmv(map,iter); + * free(val); + * } else { + * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); + * iter = strmap_iter_next(map,iter); + * } + * } + * \endcode + * + */ +strmap_iter_t * +strmap_iter_init(strmap_t *map) +{ + obfs_assert(map); + return HT_START(strmap_impl, &map->head); +} + +/** Start iterating through map. See strmap_iter_init() for example. */ +digestmap_iter_t * +digestmap_iter_init(digestmap_t *map) +{ + obfs_assert(map); + return HT_START(digestmap_impl, &map->head); +} + +/** Advance the iterator iter for map a single step to the next + * entry, and return its new value. */ +strmap_iter_t * +strmap_iter_next(strmap_t *map, strmap_iter_t *iter) +{ + obfs_assert(map); + obfs_assert(iter); + return HT_NEXT(strmap_impl, &map->head, iter); +} + +/** Advance the iterator iter for map a single step to the next entry, + * and return its new value. */ +digestmap_iter_t * +digestmap_iter_next(digestmap_t *map, digestmap_iter_t *iter) +{ + obfs_assert(map); + obfs_assert(iter); + return HT_NEXT(digestmap_impl, &map->head, iter); +} + +/** Advance the iterator iter a single step to the next entry, removing + * the current entry, and return its new value. + */ +strmap_iter_t * +strmap_iter_next_rmv(strmap_t *map, strmap_iter_t *iter) +{ + strmap_entry_t *rmv; + obfs_assert(map); + obfs_assert(iter); + obfs_assert(*iter); + rmv = *iter; + iter = HT_NEXT_RMV(strmap_impl, &map->head, iter); + free(rmv->key); + free(rmv); + return iter; +} + +/** Advance the iterator iter a single step to the next entry, removing + * the current entry, and return its new value. + */ +digestmap_iter_t * +digestmap_iter_next_rmv(digestmap_t *map, digestmap_iter_t *iter) +{ + digestmap_entry_t *rmv; + obfs_assert(map); + obfs_assert(iter); + obfs_assert(*iter); + rmv = *iter; + iter = HT_NEXT_RMV(digestmap_impl, &map->head, iter); + free(rmv); + return iter; +} + +/** Set *keyp and *valp to the current entry pointed to by + * iter. */ +void +strmap_iter_get(strmap_iter_t *iter, const char **keyp, void **valp) +{ + obfs_assert(iter); + obfs_assert(*iter); + obfs_assert(keyp); + obfs_assert(valp); + *keyp = (*iter)->key; + *valp = (*iter)->val; +} + +/** Set *keyp and *valp to the current entry pointed to by + * iter. */ +void +digestmap_iter_get(digestmap_iter_t *iter, const char **keyp, void **valp) +{ + obfs_assert(iter); + obfs_assert(*iter); + obfs_assert(keyp); + obfs_assert(valp); + *keyp = (*iter)->key; + *valp = (*iter)->val; +} + +/** Return true iff iter has advanced past the last entry of + * map. */ +int +strmap_iter_done(strmap_iter_t *iter) +{ + return iter == NULL; +} + +/** Return true iff iter has advanced past the last entry of + * map. */ +int +digestmap_iter_done(digestmap_iter_t *iter) +{ + return iter == NULL; +} + +/** Remove all entries from map, and deallocate storage for those + * entries. If free_val is provided, it is invoked on every value in + * map. + */ +void +strmap_free(strmap_t *map, void (*free_val)(void*)) +{ + strmap_entry_t **ent, **next, *this; + if (!map) + return; + + for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) { + this = *ent; + next = HT_NEXT_RMV(strmap_impl, &map->head, ent); + free(this->key); + if (free_val) + free_val(this->val); + free(this); + } + obfs_assert(HT_EMPTY(&map->head)); + HT_CLEAR(strmap_impl, &map->head); + free(map); +} + +/** Remove all entries from map, and deallocate storage for those + * entries. If free_val is provided, it is invoked on every value in + * map. + */ +void +digestmap_free(digestmap_t *map, void (*free_val)(void*)) +{ + digestmap_entry_t **ent, **next, *this; + if (!map) + return; + for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) { + this = *ent; + next = HT_NEXT_RMV(digestmap_impl, &map->head, ent); + if (free_val) + free_val(this->val); + free(this); + } + obfs_assert(HT_EMPTY(&map->head)); + HT_CLEAR(digestmap_impl, &map->head); + free(map); +} + +/** Fail with an assertion error if anything has gone wrong with the internal + * representation of map. */ +void +strmap_assert_ok(const strmap_t *map) +{ + obfs_assert(!_strmap_impl_HT_REP_IS_BAD(&map->head)); +} +/** Fail with an assertion error if anything has gone wrong with the internal + * representation of map. */ +void +digestmap_assert_ok(const digestmap_t *map) +{ + obfs_assert(!_digestmap_impl_HT_REP_IS_BAD(&map->head)); +} + +/** Return true iff map has no entries. */ +int +strmap_isempty(const strmap_t *map) +{ + return HT_EMPTY(&map->head); +} + +/** Return true iff map has no entries. */ +int +digestmap_isempty(const digestmap_t *map) +{ + return HT_EMPTY(&map->head); +} + +/** Return the number of items in map. */ +int +strmap_size(const strmap_t *map) +{ + return HT_SIZE(&map->head); +} + +/** Return the number of items in map. */ +int +digestmap_size(const digestmap_t *map) +{ + return HT_SIZE(&map->head); +} + +/** Declare a function called funcname that acts as a find_nth_FOO + * function for an array of type elt_t*. + * + * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding + * the kth element of an n-element list can be done in O(n). Then again, this + * implementation is not in critical path, and it is obviously correct. */ +#define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \ + static int \ + _cmp_ ## elt_t(const void *_a, const void *_b) \ + { \ + const elt_t *a = _a, *b = _b; \ + if (*a<*b) \ + return -1; \ + else if (*a>*b) \ + return 1; \ + else \ + return 0; \ + } \ + elt_t \ + funcname(elt_t *array, int n_elements, int nth) \ + { \ + obfs_assert(nth >= 0); \ + obfs_assert(nth < n_elements); \ + qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \ + return array[nth]; \ + } + +IMPLEMENT_ORDER_FUNC(find_nth_int, int) +IMPLEMENT_ORDER_FUNC(find_nth_time, time_t) +IMPLEMENT_ORDER_FUNC(find_nth_double, double) +IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t) +IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t) +IMPLEMENT_ORDER_FUNC(find_nth_long, long) + +/** Return a newly allocated digestset_t, optimized to hold a total of + * max_elements digests with a reasonably low false positive weight. */ +digestset_t * +digestset_new(int max_elements) +{ + /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k + * is the number of hash functions per entry, m is the bits in the array, + * and n is the number of elements inserted. For us, k==4, n<=max_elements, + * and m==n_bits= approximately max_elements*32. This gives + * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019 + * + * It would be more optimal in space vs false positives to get this false + * positive rate by going for k==13, and m==18.5n, but we also want to + * conserve CPU, and k==13 is pretty big. + */ + int n_bits = 1u << (ui64_log2(max_elements)+5); + digestset_t *r = xmalloc(sizeof(digestset_t)); + r->mask = n_bits - 1; + r->ba = bitarray_init_zero(n_bits); + return r; +} + +/** Free all storage held in set. */ +void +digestset_free(digestset_t *set) +{ + if (!set) + return; + bitarray_free(set->ba); + free(set); +} diff --git a/src/container.h b/src/container.h new file mode 100644 index 0000000..e1c1a07 --- /dev/null +++ b/src/container.h @@ -0,0 +1,685 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef CONTAINER_H +#define CONTAINER_H + +#include <stdlib.h> +#include <string.h> +#include <time.h> + +/** A resizeable list of pointers, with associated helpful functionality. + * + * The members of this struct are exposed only so that macros and inlines can + * use them; all access to smartlist internals should go through the functions + * and macros defined here. + **/ +typedef struct smartlist_t { + /** @{ */ + /** list has enough capacity to store exactly capacity elements + * before it needs to be resized. Only the first num_used (\<= + * capacity) elements point to valid data. + */ + void **list; + int num_used; + int capacity; + /** @} */ +} smartlist_t; + +smartlist_t *smartlist_create(void); +void smartlist_free(smartlist_t *sl); +void smartlist_clear(smartlist_t *sl); +void smartlist_add(smartlist_t *sl, void *element); +void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2); +void smartlist_remove(smartlist_t *sl, const void *element); +void *smartlist_pop_last(smartlist_t *sl); +void smartlist_reverse(smartlist_t *sl); +void smartlist_string_remove(smartlist_t *sl, const char *element); +int smartlist_isin(const smartlist_t *sl, const void *element) ATTR_PURE; +int smartlist_string_isin(const smartlist_t *sl, const char *element) + ATTR_PURE; +int smartlist_string_pos(const smartlist_t *, const char *elt) ATTR_PURE; +int smartlist_string_isin_case(const smartlist_t *sl, const char *element) + ATTR_PURE; +int smartlist_string_num_isin(const smartlist_t *sl, int num) ATTR_PURE; +int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2) + ATTR_PURE; +int smartlist_digest_isin(const smartlist_t *sl, const char *element) + ATTR_PURE; +int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2) + ATTR_PURE; +void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2); +void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2); + +#ifdef DEBUG_SMARTLIST +/** Return the number of items in sl. + */ +static inline int smartlist_len(const smartlist_t *sl) ATTR_PURE; +static inline int smartlist_len(const smartlist_t *sl) { + tor_assert(sl); + return (sl)->num_used; +} +/** Return the idxth element of sl. + */ +static inline void *smartlist_get(const smartlist_t *sl, int idx) ATTR_PURE; +static inline void *smartlist_get(const smartlist_t *sl, int idx) { + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(sl->num_used > idx); + return sl->list[idx]; +} +static inline void smartlist_set(smartlist_t *sl, int idx, void *val) { + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(sl->num_used > idx); + sl->list[idx] = val; +} +#else +#define smartlist_len(sl) ((sl)->num_used) +#define smartlist_get(sl, idx) ((sl)->list[idx]) +#define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val)) +#endif + +/** Exchange the elements at indices idx1 and idx2 of the + * smartlist sl. */ +static inline void smartlist_swap(smartlist_t *sl, int idx1, int idx2) +{ + if (idx1 != idx2) { + void *elt = smartlist_get(sl, idx1); + smartlist_set(sl, idx1, smartlist_get(sl, idx2)); + smartlist_set(sl, idx2, elt); + } +} + +void smartlist_del(smartlist_t *sl, int idx); +void smartlist_del_keeporder(smartlist_t *sl, int idx); +void smartlist_insert(smartlist_t *sl, int idx, void *val); +void smartlist_sort(smartlist_t *sl, + int (*compare)(const void **a, const void **b)); +void *smartlist_get_most_frequent(const smartlist_t *sl, + int (*compare)(const void **a, const void **b)); +void smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *elt)); + +void smartlist_shuffle(smartlist_t *sl); +void *smartlist_choose(const smartlist_t *sl); + +void smartlist_sort_strings(smartlist_t *sl); +void smartlist_sort_digests(smartlist_t *sl); + +char *smartlist_get_most_frequent_string(smartlist_t *sl); + +void smartlist_uniq_strings(smartlist_t *sl); +void smartlist_uniq_digests(smartlist_t *sl); +void *smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)) + ATTR_PURE; +int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out); + +void smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item); +void *smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset); +void smartlist_pqueue_remove(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item); +void smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset); + +#define SPLIT_SKIP_SPACE 0x01 +#define SPLIT_IGNORE_BLANK 0x02 +#define SPLIT_STRIP_SPACE 0x04 +int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, + int flags, int max); +char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, + size_t *len_out) ATTR_MALLOC; +char *smartlist_join_strings2(smartlist_t *sl, const char *join, + size_t join_len, int terminate, size_t *len_out) + ATTR_MALLOC; + +/** Iterate over the items in a smartlist sl, in order. For each item, + * assign it to a new local variable of type type named var, and + * execute the statement cmd. Inside the loop, the loop index can + * be accessed as var_sl_idx and the length of the list can be accessed + * as var_sl_len. + * + * NOTE: Do not change the length of the list while the loop is in progress, + * unless you adjust the _sl_len variable correspondingly. See second example + * below. + * + * Example use: + * <pre> + * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0); + * SMARTLIST_FOREACH(list, char *, cp, + * { + * printf("%d: %s\n", cp_sl_idx, cp); + * free(cp); + * }); + * smartlist_free(list); + * </pre> + * + * Example use (advanced): + * <pre> + * SMARTLIST_FOREACH(list, char *, cp, + * { + * if (!strcmp(cp, "junk")) { + * free(cp); + * SMARTLIST_DEL_CURRENT(list, cp); + * } + * }); + * </pre> + */ +/* Note: these macros use token pasting, and reach into smartlist internals. + * This can make them a little daunting. Here's the approximate unpacking of + * the above examples, for entertainment value: + * + * <pre> + * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0); + * { + * int cp_sl_idx, cp_sl_len = smartlist_len(list); + * char *cp; + * for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) { + * cp = smartlist_get(list, cp_sl_idx); + * printf("%d: %s\n", cp_sl_idx, cp); + * free(cp); + * } + * } + * smartlist_free(list); + * </pre> + * + * <pre> + * { + * int cp_sl_idx, cp_sl_len = smartlist_len(list); + * char *cp; + * for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) { + * cp = smartlist_get(list, cp_sl_idx); + * if (!strcmp(cp, "junk")) { + * free(cp); + * smartlist_del(list, cp_sl_idx); + * --cp_sl_idx; + * --cp_sl_len; + * } + * } + * } + * </pre> + */ +#define SMARTLIST_FOREACH_BEGIN(sl, type, var) \ + do { \ + int var ## _sl_idx, var ## _sl_len=(sl)->num_used; \ + type var; \ + for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len; \ + ++var ## _sl_idx) { \ + var = (sl)->list[var ## _sl_idx]; + +#define SMARTLIST_FOREACH_END(var) \ + var = NULL; \ + } } while (0) + +#define SMARTLIST_FOREACH(sl, type, var, cmd) \ + SMARTLIST_FOREACH_BEGIN(sl,type,var) { \ + cmd; \ + } SMARTLIST_FOREACH_END(var) + +/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed + * with the variable var, remove the current element in a way that + * won't confuse the loop. */ +#define SMARTLIST_DEL_CURRENT(sl, var) \ + do { \ + smartlist_del(sl, var ## _sl_idx); \ + --var ## _sl_idx; \ + --var ## _sl_len; \ + } while (0) + +/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed + * with the variable var, replace the current element with val. + * Does not deallocate the current value of var. + */ +#define SMARTLIST_REPLACE_CURRENT(sl, var, val) \ + do { \ + smartlist_set(sl, var ## _sl_idx, val); \ + } while (0) + +/* Helper: Given two lists of items, possibly of different types, such that + * both lists are sorted on some common field (as determined by a comparison + * expression cmpexpr), and such that one list (sl1) has no + * duplicates on the common field, loop through the lists in lockstep, and + * execute unmatched_var2 on items in var2 that do not appear in + * var1. + * + * WARNING: It isn't safe to add remove elements from either list while the + * loop is in progress. + * + * Example use: + * SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs, + * routerinfo_list, routerinfo_t *, ri, + * memcmp(rs->identity_digest, ri->identity_digest, 20), + * log_info(LD_GENERAL,"No match for %s", ri->nickname)) { + * log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs); + * } SMARTLIST_FOREACH_JOIN_END(rs, ri); + **/ +/* The example above unpacks (approximately) to: + * int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list); + * int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list); + * int rs_ri_cmp; + * routerstatus_t *rs; + * routerinfo_t *ri; + * for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) { + * ri = smartlist_get(routerinfo_list, ri_sl_idx); + * while (rs_sl_idx < rs_sl_len) { + * rs = smartlist_get(routerstatus_list, rs_sl_idx); + * rs_ri_cmp = memcmp(rs->identity_digest, ri->identity_digest, 20); + * if (rs_ri_cmp > 0) { + * break; + * } else if (rs_ri_cmp == 0) { + * goto matched_ri; + * } else { + * ++rs_sl_idx; + * } + * } + * log_info(LD_GENERAL,"No match for %s", ri->nickname); + * continue; + * matched_ri: { + * log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs); + * } + * } + */ +#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, \ + cmpexpr, unmatched_var2) \ + do { \ + int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used; \ + int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used; \ + int var1 ## _ ## var2 ## _cmp; \ + type1 var1; \ + type2 var2; \ + for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) { \ + var2 = (sl2)->list[var2##_sl_idx]; \ + while (var1##_sl_idx < var1##_sl_len) { \ + var1 = (sl1)->list[var1##_sl_idx]; \ + var1##_##var2##_cmp = (cmpexpr); \ + if (var1##_##var2##_cmp > 0) { \ + break; \ + } else if (var1##_##var2##_cmp == 0) { \ + goto matched_##var2; \ + } else { \ + ++var1##_sl_idx; \ + } \ + } \ + /* Ran out of v1, or no match for var2. */ \ + unmatched_var2; \ + continue; \ + matched_##var2: ; \ + +#define SMARTLIST_FOREACH_JOIN_END(var1, var2) \ + } \ + } while (0) + +#define DECLARE_MAP_FNS(maptype, keytype, prefix) \ + typedef struct maptype maptype; \ + typedef struct prefix##entry_t *prefix##iter_t; \ + maptype* prefix##new(void); \ + void* prefix##set(maptype *map, keytype key, void *val); \ + void* prefix##get(const maptype *map, keytype key); \ + void* prefix##remove(maptype *map, keytype key); \ + void prefix##free(maptype *map, void (*free_val)(void*)); \ + int prefix##isempty(const maptype *map); \ + int prefix##size(const maptype *map); \ + prefix##iter_t *prefix##iter_init(maptype *map); \ + prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \ + prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \ + void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \ + int prefix##iter_done(prefix##iter_t *iter); \ + void prefix##assert_ok(const maptype *map) + +/* Map from const char * to void *. Implemented with a hash table. */ +DECLARE_MAP_FNS(strmap_t, const char *, strmap_); +/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */ +DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_); + +#undef DECLARE_MAP_FNS + +/** Iterates over the key-value pairs in a map map in order. + * prefix is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_). + * The map's keys and values are of type keytype and valtype respectively; + * each iteration assigns them to keyvar and valvar. + * + * Example use: + * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { + * // use k and r + * } MAP_FOREACH_END. + */ +/* Unpacks to, approximately: + * { + * digestmap_iter_t *k_iter; + * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); + * k_iter = digestmap_iter_next(m, k_iter)) { + * const char *k; + * void *r_voidp; + * routerinfo_t *r; + * digestmap_iter_get(k_iter, &k, &r_voidp); + * r = r_voidp; + * // use k and r + * } + * } + */ +#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \ + do { \ + prefix##iter_t *keyvar##_iter; \ + for (keyvar##_iter = prefix##iter_init(map); \ + !prefix##iter_done(keyvar##_iter); \ + keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) { \ + keytype keyvar; \ + void *valvar##_voidp; \ + valtype valvar; \ + prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ + valvar = valvar##_voidp; + +/** As MAP_FOREACH, except allows members to be removed from the map + * during the iteration via MAP_DEL_CURRENT. Example use: + * + * Example use: + * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { + * if (is_very_old(r)) + * MAP_DEL_CURRENT(k); + * } MAP_FOREACH_END. + **/ +/* Unpacks to, approximately: + * { + * digestmap_iter_t *k_iter; + * int k_del=0; + * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); + * k_iter = k_del ? digestmap_iter_next(m, k_iter) + * : digestmap_iter_next_rmv(m, k_iter)) { + * const char *k; + * void *r_voidp; + * routerinfo_t *r; + * k_del=0; + * digestmap_iter_get(k_iter, &k, &r_voidp); + * r = r_voidp; + * if (is_very_old(r)) { + * k_del = 1; + * } + * } + * } + */ +#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \ + do { \ + prefix##iter_t *keyvar##_iter; \ + int keyvar##_del=0; \ + for (keyvar##_iter = prefix##iter_init(map); \ + !prefix##iter_done(keyvar##_iter); \ + keyvar##_iter = keyvar##_del ? \ + prefix##iter_next_rmv(map, keyvar##_iter) : \ + prefix##iter_next(map, keyvar##_iter)) { \ + keytype keyvar; \ + void *valvar##_voidp; \ + valtype valvar; \ + keyvar##_del=0; \ + prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ + valvar = valvar##_voidp; + +/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon + * member of the map. */ +#define MAP_DEL_CURRENT(keyvar) \ + do { \ + keyvar##_del = 1; \ + } while (0) + +/** Used to end a MAP_FOREACH() block. */ +#define MAP_FOREACH_END } while (0) + +/** As MAP_FOREACH, but does not require declaration of prefix or keytype. + * Example use: + * DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) { + * // use k and r + * } DIGESTMAP_FOREACH_END. + */ +#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar) + +/** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or + * keytype. + * Example use: + * DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) { + * if (is_very_old(r)) + * MAP_DEL_CURRENT(k); + * } DIGESTMAP_FOREACH_END. + */ +#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar) +/** Used to end a DIGESTMAP_FOREACH() block. */ +#define DIGESTMAP_FOREACH_END MAP_FOREACH_END + +#define STRMAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar) +#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar) +#define STRMAP_FOREACH_END MAP_FOREACH_END + +void* strmap_set_lc(strmap_t *map, const char *key, void *val); +void* strmap_get_lc(const strmap_t *map, const char *key); +void* strmap_remove_lc(strmap_t *map, const char *key); + +#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \ + typedef struct maptype maptype; \ + typedef struct prefix##iter_t prefix##iter_t; \ + static inline maptype* prefix##new(void) \ + { \ + return (maptype*)digestmap_new(); \ + } \ + static inline digestmap_t* prefix##to_digestmap(maptype *map) \ + { \ + return (digestmap_t*)map; \ + } \ + static inline valtype* prefix##get(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_get((digestmap_t*)map, key); \ + } \ + static inline valtype* prefix##set(maptype *map, const char *key, \ + valtype *val) \ + { \ + return (valtype*)digestmap_set((digestmap_t*)map, key, val); \ + } \ + static inline valtype* prefix##remove(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_remove((digestmap_t*)map, key); \ + } \ + static inline void prefix##free(maptype *map, void (*free_val)(void*)) \ + { \ + digestmap_free((digestmap_t*)map, free_val); \ + } \ + static inline int prefix##isempty(maptype *map) \ + { \ + return digestmap_isempty((digestmap_t*)map); \ + } \ + static inline int prefix##size(maptype *map) \ + { \ + return digestmap_size((digestmap_t*)map); \ + } \ + static inline prefix##iter_t *prefix##iter_init(maptype *map) \ + { \ + return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \ + } \ + static inline prefix##iter_t *prefix##iter_next(maptype *map, \ + prefix##iter_t *iter) \ + { \ + return (prefix##iter_t*) digestmap_iter_next( \ + (digestmap_t*)map, (digestmap_iter_t*)iter); \ + } \ + static inline prefix##iter_t *prefix##iter_next_rmv(maptype *map, \ + prefix##iter_t *iter) \ + { \ + return (prefix##iter_t*) digestmap_iter_next_rmv( \ + (digestmap_t*)map, (digestmap_iter_t*)iter); \ + } \ + static inline void prefix##iter_get(prefix##iter_t *iter, \ + const char **keyp, \ + valtype **valp) \ + { \ + void *v; \ + digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \ + *valp = v; \ + } \ + static inline int prefix##iter_done(prefix##iter_t *iter) \ + { \ + return digestmap_iter_done((digestmap_iter_t*)iter); \ + } + +#if SIZEOF_INT == 4 +#define BITARRAY_SHIFT 5 +#elif SIZEOF_INT == 8 +#define BITARRAY_SHIFT 6 +#else +#error "int is neither 4 nor 8 bytes. I can't deal with that." +#endif +#define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1) + +/** A random-access array of one-bit-wide elements. */ +typedef unsigned int bitarray_t; +/** Create a new bit array that can hold n_bits bits. */ +static inline bitarray_t * +bitarray_init_zero(unsigned int n_bits) +{ + /* round up to the next int. */ + size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT; + return xzalloc(sz*sizeof(unsigned int)); +} +/** Expand ba from holding n_bits_old to n_bits_new, + * clearing all new bits. Returns a possibly changed pointer to the + * bitarray. */ +static inline bitarray_t * +bitarray_expand(bitarray_t *ba, + unsigned int n_bits_old, unsigned int n_bits_new) +{ + size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT; + size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT; + char *ptr; + if (sz_new <= sz_old) + return ba; + ptr = xrealloc(ba, sz_new*sizeof(unsigned int)); + /* This memset does nothing to the older excess bytes. But they were + * already set to 0 by bitarry_init_zero. */ + memset(ptr+sz_old*sizeof(unsigned int), 0, + (sz_new-sz_old)*sizeof(unsigned int)); + return (bitarray_t*) ptr; +} +/** Free the bit array ba. */ +static inline void +bitarray_free(bitarray_t *ba) +{ + free(ba); +} +/** Set the bitth bit in b to 1. */ +static inline void +bitarray_set(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); +} +/** Set the bitth bit in b to 0. */ +static inline void +bitarray_clear(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK)); +} +/** Return true iff bitth bit in b is nonzero. NOTE: does + * not necessarily return 1 on true. */ +static inline unsigned int +bitarray_is_set(bitarray_t *b, int bit) +{ + return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK)); +} + +/** A set of digests, implemented as a Bloom filter. */ +typedef struct { + int mask; /**< One less than the number of bits in ba; always one less + * than a power of two. */ + bitarray_t *ba; /**< A bit array to implement the Bloom filter. */ +} digestset_t; + +#define BIT(n) ((n) & set->mask) +/** Add the digest digest to set. */ +static inline void +digestset_add(digestset_t *set, const char *digest) +{ + const uint32_t *p = (const uint32_t *)digest; + const uint32_t d1 = p[0] + (p[1]>>16); + const uint32_t d2 = p[1] + (p[2]>>16); + const uint32_t d3 = p[2] + (p[3]>>16); + const uint32_t d4 = p[3] + (p[0]>>16); + bitarray_set(set->ba, BIT(d1)); + bitarray_set(set->ba, BIT(d2)); + bitarray_set(set->ba, BIT(d3)); + bitarray_set(set->ba, BIT(d4)); +} + +/** If digest is in set, return nonzero. Otherwise, + * probably return zero. */ +static inline int +digestset_isin(const digestset_t *set, const char *digest) +{ + const uint32_t *p = (const uint32_t *)digest; + const uint32_t d1 = p[0] + (p[1]>>16); + const uint32_t d2 = p[1] + (p[2]>>16); + const uint32_t d3 = p[2] + (p[3]>>16); + const uint32_t d4 = p[3] + (p[0]>>16); + return bitarray_is_set(set->ba, BIT(d1)) && + bitarray_is_set(set->ba, BIT(d2)) && + bitarray_is_set(set->ba, BIT(d3)) && + bitarray_is_set(set->ba, BIT(d4)); +} +#undef BIT + +digestset_t *digestset_new(int max_elements); +void digestset_free(digestset_t* set); + +/* These functions, given an array of n_elements, return the + * nth lowest element. nth=0 gives the lowest element; + * n_elements-1 gives the highest; and (n_elements-1) / 2 gives + * the median. As a side effect, the elements of array are sorted. */ +int find_nth_int(int *array, int n_elements, int nth); +time_t find_nth_time(time_t *array, int n_elements, int nth); +double find_nth_double(double *array, int n_elements, int nth); +int32_t find_nth_int32(int32_t *array, int n_elements, int nth); +uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth); +long find_nth_long(long *array, int n_elements, int nth); +static inline int +median_int(int *array, int n_elements) +{ + return find_nth_int(array, n_elements, (n_elements-1)/2); +} +static inline time_t +median_time(time_t *array, int n_elements) +{ + return find_nth_time(array, n_elements, (n_elements-1)/2); +} +static inline double +median_double(double *array, int n_elements) +{ + return find_nth_double(array, n_elements, (n_elements-1)/2); +} +static inline uint32_t +median_uint32(uint32_t *array, int n_elements) +{ + return find_nth_uint32(array, n_elements, (n_elements-1)/2); +} +static inline int32_t +median_int32(int32_t *array, int n_elements) +{ + return find_nth_int32(array, n_elements, (n_elements-1)/2); +} +static inline long +median_long(long *array, int n_elements) +{ + return find_nth_long(array, n_elements, (n_elements-1)/2); +} + +#endif diff --git a/src/crypt.c b/src/crypt.c index e28e061..98516e6 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -211,3 +211,27 @@ random_bytes(uchar *buf, size_t buflen) { return RAND_bytes(buf, buflen) == 1 ? 0 : -1; } + + +/** Return a pseudorandom integer, chosen uniformly from the values + * between 0 and max-1 inclusive. max must be between 1 and + * INT_MAX+1, inclusive. */ +int +random_int(unsigned int max) +{ + unsigned int val; + unsigned int cutoff; + obfs_assert(max <= ((unsigned int)INT_MAX)+1); + obfs_assert(max > 0); /* don't div by 0 */ + + /* We ignore any values that are >= 'cutoff,' to avoid biasing the + * distribution with clipping at the upper end of unsigned int's + * range. + */ + cutoff = UINT_MAX - (UINT_MAX%max); + while (1) { + random_bytes((uchar*)&val, sizeof(val)); + if (val < cutoff) + return val % max; + } +} diff --git a/src/crypt.h b/src/crypt.h index 3f1e4df..beccda6 100644 --- a/src/crypt.h +++ b/src/crypt.h @@ -45,6 +45,11 @@ void crypt_free(crypt_t *); /** Set b to contain n random bytes. */ int random_bytes(uchar *b, size_t n); +/** Return a random integer in the range [0, max). + * 'max' must be between 1 and INT_MAX+1, inclusive. + */ +int random_int(unsigned int max); + #ifdef CRYPT_PRIVATE #include <openssl/aes.h> diff --git a/src/ht.h b/src/ht.h new file mode 100644 index 0000000..8c45db1 --- /dev/null +++ b/src/ht.h @@ -0,0 +1,471 @@ +/* Copyright (c) 2002, Christopher Clark. + * Copyright (c) 2005-2006, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See license at end. */ + +/* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ + +#ifndef HT_H +#define HT_H + +#define HT_HEAD(name, type) \ + struct name { \ + /* The hash table itself. */ \ + struct type **hth_table; \ + /* How long is the hash table? */ \ + unsigned hth_table_length; \ + /* How many elements does the table contain? */ \ + unsigned hth_n_entries; \ + /* How many elements will we allow in the table before resizing it? */ \ + unsigned hth_load_limit; \ + /* Position of hth_table_length in the primes table. */ \ + int hth_prime_idx; \ + } + +#define HT_INITIALIZER() \ + { NULL, 0, 0, 0, -1 } + +#define HT_ENTRY(type) \ + struct { \ + struct type *hte_next; \ + unsigned hte_hash; \ + } + +#define HT_EMPTY(head) \ + ((head)->hth_n_entries == 0) + +/* Helper: alias for the bucket containing 'elm'. */ +#define _HT_BUCKET(head, field, elm) \ + ((head)->hth_table[elm->field.hte_hash % head->hth_table_length]) + +/* How many elements in 'head'? */ +#define HT_SIZE(head) \ + ((head)->hth_n_entries) + +/* Return memory usage for a hashtable (not counting the entries themselves) */ +#define HT_MEM_USAGE(head) \ + (sizeof(*head) + (head)->hth_table_length * sizeof(void*)) + +#define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm)) +#define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm)) +#define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm)) +#define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm)) +#define HT_START(name, head) name##_HT_START(head) +#define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm)) +#define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm)) +#define HT_CLEAR(name, head) name##_HT_CLEAR(head) +#define HT_INIT(name, head) name##_HT_INIT(head) +/* Helper: */ +static inline unsigned +ht_improve_hash(unsigned h) +{ + /* Aim to protect against poor hash functions by adding logic here + * - logic taken from java 1.4 hashtable source */ + h += ~(h << 9); + h ^= ((h >> 14) | (h << 18)); /* >>> */ + h += (h << 4); + h ^= ((h >> 10) | (h << 22)); /* >>> */ + return h; +} + +#if 0 +/** Basic string hash function, from Java standard String.hashCode(). */ +static inline unsigned +ht_string_hash(const char *s) +{ + unsigned h = 0; + int m = 1; + while (*s) { + h += ((signed char)*s++)*m; + m = (m<<5)-1; /* m *= 31 */ + } + return h; +} +#endif + +/** Basic string hash function, from Python's str.__hash__() */ +static inline unsigned +ht_string_hash(const char *s) +{ + unsigned h; + const unsigned char *cp = (const unsigned char *)s; + h = *cp << 7; + while (*cp) { + h = (1000003*h) ^ *cp++; + } + /* This conversion truncates the length of the string, but that's ok. */ + h ^= (unsigned)(cp-(const unsigned char*)s); + return h; +} + +#define _HT_SET_HASH(elm, field, hashfn) \ + (elm)->field.hte_hash = hashfn(elm) + +#define HT_FOREACH(x, name, head) \ + for ((x) = HT_START(name, head); \ + (x) != NULL; \ + (x) = HT_NEXT(name, head, x)) + +#define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ + int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ + void name##_HT_CLEAR(struct name *ht); \ + int _##name##_HT_REP_IS_BAD(const struct name *ht); \ + static inline void \ + name##_HT_INIT(struct name *head) { \ + head->hth_table_length = 0; \ + head->hth_table = NULL; \ + head->hth_n_entries = 0; \ + head->hth_load_limit = 0; \ + head->hth_prime_idx = -1; \ + } \ + /* Helper: returns a pointer to the right location in the table \ + * 'head' to find or insert the element 'elm'. */ \ + static inline struct type ** \ + _##name##_HT_FIND_P(struct name *head, struct type *elm) \ + { \ + struct type **p; \ + if (!head->hth_table) \ + return NULL; \ + p = &_HT_BUCKET(head, field, elm); \ + while (*p) { \ + if (eqfn(*p, elm)) \ + return p; \ + p = &(*p)->field.hte_next; \ + } \ + return p; \ + } \ + /* Return a pointer to the element in the table 'head' matching 'elm', \ + * or NULL if no such element exists */ \ + static inline struct type * \ + name##_HT_FIND(const struct name *head, struct type *elm) \ + { \ + struct type **p; \ + struct name *h = (struct name *) head; \ + _HT_SET_HASH(elm, field, hashfn); \ + p = _##name##_HT_FIND_P(h, elm); \ + return p ? *p : NULL; \ + } \ + /* Insert the element 'elm' into the table 'head'. Do not call this \ + * function if the table might already contain a matching element. */ \ + static inline void \ + name##_HT_INSERT(struct name *head, struct type *elm) \ + { \ + struct type **p; \ + if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ + name##_HT_GROW(head, head->hth_n_entries+1); \ + ++head->hth_n_entries; \ + _HT_SET_HASH(elm, field, hashfn); \ + p = &_HT_BUCKET(head, field, elm); \ + elm->field.hte_next = *p; \ + *p = elm; \ + } \ + /* Insert the element 'elm' into the table 'head'. If there already \ + * a matching element in the table, replace that element and return \ + * it. */ \ + static inline struct type * \ + name##_HT_REPLACE(struct name *head, struct type *elm) \ + { \ + struct type **p, *r; \ + if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ + name##_HT_GROW(head, head->hth_n_entries+1); \ + _HT_SET_HASH(elm, field, hashfn); \ + p = _##name##_HT_FIND_P(head, elm); \ + r = *p; \ + *p = elm; \ + if (r && (r!=elm)) { \ + elm->field.hte_next = r->field.hte_next; \ + r->field.hte_next = NULL; \ + return r; \ + } else { \ + ++head->hth_n_entries; \ + return NULL; \ + } \ + } \ + /* Remove any element matching 'elm' from the table 'head'. If such \ + * an element is found, return it; otherwise return NULL. */ \ + static inline struct type * \ + name##_HT_REMOVE(struct name *head, struct type *elm) \ + { \ + struct type **p, *r; \ + _HT_SET_HASH(elm, field, hashfn); \ + p = _##name##_HT_FIND_P(head,elm); \ + if (!p || !*p) \ + return NULL; \ + r = *p; \ + *p = r->field.hte_next; \ + r->field.hte_next = NULL; \ + --head->hth_n_entries; \ + return r; \ + } \ + /* Invoke the function 'fn' on every element of the table 'head', \ + * using 'data' as its second argument. If the function returns \ + * nonzero, remove the most recently examined element before invoking \ + * the function again. */ \ + static inline void \ + name##_HT_FOREACH_FN(struct name *head, \ + int (*fn)(struct type *, void *), \ + void *data) \ + { \ + unsigned idx; \ + int remove; \ + struct type **p, **nextp, *next; \ + if (!head->hth_table) \ + return; \ + for (idx=0; idx < head->hth_table_length; ++idx) { \ + p = &head->hth_table[idx]; \ + while (*p) { \ + nextp = &(*p)->field.hte_next; \ + next = *nextp; \ + remove = fn(*p, data); \ + if (remove) { \ + --head->hth_n_entries; \ + *p = next; \ + } else { \ + p = nextp; \ + } \ + } \ + } \ + } \ + /* Return a pointer to the first element in the table 'head', under \ + * an arbitrary order. This order is stable under remove operations, \ + * but not under others. If the table is empty, return NULL. */ \ + static inline struct type ** \ + name##_HT_START(struct name *head) \ + { \ + unsigned b = 0; \ + while (b < head->hth_table_length) { \ + if (head->hth_table[b]) \ + return &head->hth_table[b]; \ + ++b; \ + } \ + return NULL; \ + } \ + /* Return the next element in 'head' after 'elm', under the arbitrary \ + * order used by HT_START. If there are no more elements, return \ + * NULL. If 'elm' is to be removed from the table, you must call \ + * this function for the next value before you remove it. \ + */ \ + static inline struct type ** \ + name##_HT_NEXT(struct name *head, struct type **elm) \ + { \ + if ((*elm)->field.hte_next) { \ + return &(*elm)->field.hte_next; \ + } else { \ + unsigned b = ((*elm)->field.hte_hash % head->hth_table_length)+1; \ + while (b < head->hth_table_length) { \ + if (head->hth_table[b]) \ + return &head->hth_table[b]; \ + ++b; \ + } \ + return NULL; \ + } \ + } \ + static inline struct type ** \ + name##_HT_NEXT_RMV(struct name *head, struct type **elm) \ + { \ + unsigned h = (*elm)->field.hte_hash; \ + *elm = (*elm)->field.hte_next; \ + --head->hth_n_entries; \ + if (*elm) { \ + return elm; \ + } else { \ + unsigned b = (h % head->hth_table_length)+1; \ + while (b < head->hth_table_length) { \ + if (head->hth_table[b]) \ + return &head->hth_table[b]; \ + ++b; \ + } \ + return NULL; \ + } \ + } + +#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ + reallocfn, freefn) \ + static unsigned name##_PRIMES[] = { \ + 53, 97, 193, 389, \ + 769, 1543, 3079, 6151, \ + 12289, 24593, 49157, 98317, \ + 196613, 393241, 786433, 1572869, \ + 3145739, 6291469, 12582917, 25165843, \ + 50331653, 100663319, 201326611, 402653189, \ + 805306457, 1610612741 \ + }; \ + static unsigned name##_N_PRIMES = \ + (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])); \ + /* Expand the internal table of 'head' until it is large enough to \ + * hold 'size' elements. Return 0 on success, -1 on allocation \ + * failure. */ \ + int \ + name##_HT_GROW(struct name *head, unsigned size) \ + { \ + unsigned new_len, new_load_limit; \ + int prime_idx; \ + struct type **new_table; \ + if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \ + return 0; \ + if (head->hth_load_limit > size) \ + return 0; \ + prime_idx = head->hth_prime_idx; \ + do { \ + new_len = name##_PRIMES[++prime_idx]; \ + new_load_limit = (unsigned)(load*new_len); \ + } while (new_load_limit <= size && \ + prime_idx < (int)name##_N_PRIMES); \ + if ((new_table = mallocfn(new_len*sizeof(struct type*)))) { \ + unsigned b; \ + memset(new_table, 0, new_len*sizeof(struct type*)); \ + for (b = 0; b < head->hth_table_length; ++b) { \ + struct type *elm, *next; \ + unsigned b2; \ + elm = head->hth_table[b]; \ + while (elm) { \ + next = elm->field.hte_next; \ + b2 = elm->field.hte_hash % new_len; \ + elm->field.hte_next = new_table[b2]; \ + new_table[b2] = elm; \ + elm = next; \ + } \ + } \ + if (head->hth_table) \ + freefn(head->hth_table); \ + head->hth_table = new_table; \ + } else { \ + unsigned b, b2; \ + new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \ + if (!new_table) return -1; \ + memset(new_table + head->hth_table_length, 0, \ + (new_len - head->hth_table_length)*sizeof(struct type*)); \ + for (b=0; b < head->hth_table_length; ++b) { \ + struct type *e, **pE; \ + for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { \ + b2 = e->field.hte_hash % new_len; \ + if (b2 == b) { \ + pE = &e->field.hte_next; \ + } else { \ + *pE = e->field.hte_next; \ + e->field.hte_next = new_table[b2]; \ + new_table[b2] = e; \ + } \ + } \ + } \ + head->hth_table = new_table; \ + } \ + head->hth_table_length = new_len; \ + head->hth_prime_idx = prime_idx; \ + head->hth_load_limit = new_load_limit; \ + return 0; \ + } \ + /* Free all storage held by 'head'. Does not free 'head' itself, or \ + * individual elements. */ \ + void \ + name##_HT_CLEAR(struct name *head) \ + { \ + if (head->hth_table) \ + freefn(head->hth_table); \ + head->hth_table_length = 0; \ + name##_HT_INIT(head); \ + } \ + /* Debugging helper: return false iff the representation of 'head' is \ + * internally consistent. */ \ + int \ + _##name##_HT_REP_IS_BAD(const struct name *head) \ + { \ + unsigned n, i; \ + struct type *elm; \ + if (!head->hth_table_length) { \ + if (!head->hth_table && !head->hth_n_entries && \ + !head->hth_load_limit && head->hth_prime_idx == -1) \ + return 0; \ + else \ + return 1; \ + } \ + if (!head->hth_table || head->hth_prime_idx < 0 || \ + !head->hth_load_limit) \ + return 2; \ + if (head->hth_n_entries > head->hth_load_limit) \ + return 3; \ + if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \ + return 4; \ + if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \ + return 5; \ + for (n = i = 0; i < head->hth_table_length; ++i) { \ + for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \ + if (elm->field.hte_hash != hashfn(elm)) \ + return 1000 + i; \ + if ((elm->field.hte_hash % head->hth_table_length) != i) \ + return 10000 + i; \ + ++n; \ + } \ + } \ + if (n != head->hth_n_entries) \ + return 6; \ + return 0; \ + } + +/** Implements an over-optimized "find and insert if absent" block; + * not meant for direct usage by typical code, or usage outside the critical + * path.*/ +#define _HT_FIND_OR_INSERT(name, field, hashfn, head, eltype, elm, var, y, n) \ + { \ + struct name *_##var##_head = head; \ + eltype **var; \ + if (!_##var##_head->hth_table || \ + _##var##_head->hth_n_entries >= _##var##_head->hth_load_limit) \ + name##_HT_GROW(_##var##_head, _##var##_head->hth_n_entries+1); \ + _HT_SET_HASH((elm), field, hashfn); \ + var = _##name##_HT_FIND_P(_##var##_head, (elm)); \ + if (*var) { \ + y; \ + } else { \ + n; \ + } \ + } +#define _HT_FOI_INSERT(field, head, elm, newent, var) \ + { \ + newent->field.hte_hash = (elm)->field.hte_hash; \ + newent->field.hte_next = NULL; \ + *var = newent; \ + ++((head)->hth_n_entries); \ + } + +/* + * Copyright 2005, Nick Mathewson. Implementation logic is adapted from code + * by Christopher Clark, retrofit to allow drop-in memory management, and to + * use the same interface as Niels Provos's HT_H. I'm not sure whether this + * is a derived work any more, but whether it is or not, the license below + * applies. + * + * Copyright (c) 2002, Christopher Clark + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of the original author; nor the names of any contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER + * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#endif + diff --git a/src/test/unittest.c b/src/test/unittest.c index 45757e9..8974c87 100644 --- a/src/test/unittest.c +++ b/src/test/unittest.c @@ -5,11 +5,13 @@ #include "tinytest.h" #include "../crypt.h" +extern struct testcase_t container_tests[]; extern struct testcase_t crypt_tests[]; extern struct testcase_t obfs2_tests[]; extern struct testcase_t socks_tests[]; struct testgroup_t groups[] = { + { "container/", container_tests }, { "crypt/", crypt_tests }, { "obfs2/", obfs2_tests }, { "socks/", socks_tests }, diff --git a/src/test/unittest_container.c b/src/test/unittest_container.c new file mode 100644 index 0000000..4731139 --- /dev/null +++ b/src/test/unittest_container.c @@ -0,0 +1,772 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "../util.h" +#include "tinytest_macros.h" + +#include "../container.h" +#include "../crypt.h" + +/** Helper: return a tristate based on comparing the strings in *a and + * *b. */ +static int +_compare_strs(const void **a, const void **b) +{ + const char *s1 = *a, *s2 = *b; + return strcmp(s1, s2); +} + +/** Helper: return a tristate based on comparing the strings in *a and + * *b, excluding a's first character, and ignoring case. */ +static int +_compare_without_first_ch(const void *a, const void **b) +{ + const char *s1 = a, *s2 = *b; + return strcasecmp(s1+1, s2); +} + +/** Run unit tests for basic dynamic-sized array functionality. */ +static void +test_container_smartlist_basic(void *unused) +{ + smartlist_t *sl; + + /* XXXX test sort_digests, uniq_strings, uniq_digests */ + + /* Test smartlist add, del_keeporder, insert, get. */ + sl = smartlist_create(); + smartlist_add(sl, (void*)1); + smartlist_add(sl, (void*)2); + smartlist_add(sl, (void*)3); + smartlist_add(sl, (void*)4); + smartlist_del_keeporder(sl, 1); + smartlist_insert(sl, 1, (void*)22); + smartlist_insert(sl, 0, (void*)0); + smartlist_insert(sl, 5, (void*)555); + tt_ptr_op(smartlist_get(sl,0), ==, (void*)0); + tt_ptr_op(smartlist_get(sl,1), ==, (void*)1); + tt_ptr_op(smartlist_get(sl,2), ==, (void*)22); + tt_ptr_op(smartlist_get(sl,3), ==, (void*)3); + tt_ptr_op(smartlist_get(sl,4), ==, (void*)4); + tt_ptr_op(smartlist_get(sl,5), ==, (void*)555); + /* Try deleting in the middle. */ + smartlist_del(sl, 1); + tt_ptr_op(smartlist_get(sl, 1), ==, (void*)555); + /* Try deleting at the end. */ + smartlist_del(sl, 4); + tt_int_op(smartlist_len(sl), ==, 4); + + /* test isin. */ + tt_assert(smartlist_isin(sl, (void*)3)); + tt_assert(!smartlist_isin(sl, (void*)99)); + + end: + smartlist_free(sl); +} + +/** Run unit tests for smartlist-of-strings functionality. */ +static void +test_container_smartlist_strings(void *unused) +{ + smartlist_t *sl = smartlist_create(); + char *cp=NULL, *cp_alloc=NULL; + size_t sz; + + /* Test split and join */ + tt_int_op(smartlist_len(sl), ==, 0); + smartlist_split_string(sl, "abc", ":", 0, 0); + tt_int_op(smartlist_len(sl), ==, 1); + tt_str_op(smartlist_get(sl, 0), ==, "abc"); + smartlist_split_string(sl, "a::bc::", "::", 0, 0); + tt_int_op(smartlist_len(sl), ==, 4); + tt_str_op(smartlist_get(sl, 1), ==, "a"); + tt_str_op(smartlist_get(sl, 2), ==, "bc"); + tt_str_op(smartlist_get(sl, 3), ==, ""); + cp_alloc = smartlist_join_strings(sl, "", 0, NULL); + tt_str_op(cp_alloc, ==, "abcabc"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "!", 0, NULL); + tt_str_op(cp_alloc, ==, "abc!a!bc!"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL); + tt_str_op(cp_alloc, ==, "abcXYaXYbcXY"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL); + tt_str_op(cp_alloc, ==, "abcXYaXYbcXYXY"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "", 1, NULL); + tt_str_op(cp_alloc, ==, "abcabc"); + free(cp_alloc); + + smartlist_split_string(sl, "/def/ /ghijk", "/", 0, 0); + tt_int_op(smartlist_len(sl), ==, 8); + tt_str_op(smartlist_get(sl, 4), ==, ""); + tt_str_op(smartlist_get(sl, 5), ==, "def"); + tt_str_op(smartlist_get(sl, 6), ==, " "); + tt_str_op(smartlist_get(sl, 7), ==, "ghijk"); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + smartlist_split_string(sl, "a,bbd,cdef", ",", SPLIT_SKIP_SPACE, 0); + tt_int_op(smartlist_len(sl), ==, 3); + tt_str_op(smartlist_get(sl,0), ==, "a"); + tt_str_op(smartlist_get(sl,1), ==, "bbd"); + tt_str_op(smartlist_get(sl,2), ==, "cdef"); + smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>", + SPLIT_SKIP_SPACE, 0); + tt_int_op(smartlist_len(sl), ==, 8); + tt_str_op(smartlist_get(sl,3), ==, "z"); + tt_str_op(smartlist_get(sl,4), ==, "zhasd"); + tt_str_op(smartlist_get(sl,5), ==, ""); + tt_str_op(smartlist_get(sl,6), ==, "bnud"); + tt_str_op(smartlist_get(sl,7), ==, ""); + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + smartlist_split_string(sl, " ab\tc \td ef ", NULL, + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 4); + tt_str_op(smartlist_get(sl,0), ==, "ab"); + tt_str_op(smartlist_get(sl,1), ==, "c"); + tt_str_op(smartlist_get(sl,2), ==, "d"); + tt_str_op(smartlist_get(sl,3), ==, "ef"); + smartlist_split_string(sl, "ghi\tj", NULL, + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 6); + tt_str_op(smartlist_get(sl,4), ==, "ghi"); + tt_str_op(smartlist_get(sl,5), ==, "j"); + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL); + tt_str_op(cp_alloc, ==, ""); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL); + tt_str_op(cp_alloc, ==, "XY"); + free(cp_alloc); + + smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 3); + tt_str_op(smartlist_get(sl, 0), ==, "z"); + tt_str_op(smartlist_get(sl, 1), ==, "zhasd"); + tt_str_op(smartlist_get(sl, 2), ==, "bnud"); + smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 2); + tt_int_op(smartlist_len(sl), ==, 5); + tt_str_op(smartlist_get(sl, 3), ==, "z"); + tt_str_op(smartlist_get(sl, 4), ==, "zhasd <> <> bnud<>"); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + smartlist_split_string(sl, "abcd\n", "\n", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 1); + tt_str_op(smartlist_get(sl, 0), ==, "abcd"); + smartlist_split_string(sl, "efgh", "\n", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 2); + tt_str_op(smartlist_get(sl, 1), ==, "efgh"); + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + /* Test swapping, shuffling, and sorting. */ + smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0); + tt_int_op(smartlist_len(sl), ==, 7); + smartlist_sort(sl, _compare_strs); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "and,arma,by,nickm,onion,router,the"); + free(cp_alloc); + smartlist_swap(sl, 1, 5); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "and,router,by,nickm,onion,arma,the"); + free(cp_alloc); + smartlist_shuffle(sl); + tt_int_op(smartlist_len(sl), ==, 7); + tt_assert(smartlist_string_isin(sl, "and")); + tt_assert(smartlist_string_isin(sl, "router")); + tt_assert(smartlist_string_isin(sl, "by")); + tt_assert(smartlist_string_isin(sl, "nickm")); + tt_assert(smartlist_string_isin(sl, "onion")); + tt_assert(smartlist_string_isin(sl, "arma")); + tt_assert(smartlist_string_isin(sl, "the")); + + /* Test bsearch. */ + smartlist_sort(sl, _compare_strs); + tt_str_op(smartlist_bsearch(sl, "zNicKM", + _compare_without_first_ch), ==, "nickm"); + tt_str_op(smartlist_bsearch(sl, " AND", _compare_without_first_ch), ==, "and"); + tt_ptr_op(smartlist_bsearch(sl, " ANz", _compare_without_first_ch), ==, NULL); + + /* Test bsearch_idx */ + { + int f; + tt_int_op(smartlist_bsearch_idx(sl," aaa",_compare_without_first_ch,&f), + ==, 0); + tt_int_op(f, ==, 0); + tt_int_op(smartlist_bsearch_idx(sl," and",_compare_without_first_ch,&f), + ==, 0); + tt_int_op(f, ==, 1); + tt_int_op(smartlist_bsearch_idx(sl," arm",_compare_without_first_ch,&f), + ==, 1); + tt_int_op(f, ==, 0); + tt_int_op(smartlist_bsearch_idx(sl," arma",_compare_without_first_ch,&f), + ==, 1); + tt_int_op(f, ==, 1); + tt_int_op(smartlist_bsearch_idx(sl," armb",_compare_without_first_ch,&f), + ==, 2); + tt_int_op(f, ==, 0); + tt_int_op(smartlist_bsearch_idx(sl," zzzz",_compare_without_first_ch,&f), + ==, 7); + tt_int_op(f, ==, 0); + } + + /* Test reverse() and pop_last() */ + smartlist_reverse(sl); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "the,router,onion,nickm,by,arma,and"); + free(cp_alloc); + cp_alloc = smartlist_pop_last(sl); + tt_str_op(cp_alloc, ==, "and"); + free(cp_alloc); + tt_int_op(smartlist_len(sl), ==, 6); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + cp_alloc = smartlist_pop_last(sl); + tt_ptr_op(cp_alloc, ==, NULL); + + /* Test uniq() */ + smartlist_split_string(sl, + "50,noon,radar,a,man,a,plan,a,canal,panama,radar,noon,50", + ",", 0, 0); + smartlist_sort(sl, _compare_strs); + smartlist_uniq(sl, _compare_strs, free); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "50,a,canal,man,noon,panama,plan,radar"); + free(cp_alloc); + + /* Test string_isin and isin_case and num_isin */ + tt_assert(smartlist_string_isin(sl, "noon")); + tt_assert(!smartlist_string_isin(sl, "noonoon")); + tt_assert(smartlist_string_isin_case(sl, "nOOn")); + tt_assert(!smartlist_string_isin_case(sl, "nooNooN")); + tt_assert(smartlist_string_num_isin(sl, 50)); + tt_assert(!smartlist_string_num_isin(sl, 60)); + + /* Test smartlist_choose */ + { + int i; + int allsame = 1; + int allin = 1; + void *first = smartlist_choose(sl); + tt_assert(smartlist_isin(sl, first)); + for (i = 0; i < 100; ++i) { + void *second = smartlist_choose(sl); + if (second != first) + allsame = 0; + if (!smartlist_isin(sl, second)) + allin = 0; + } + tt_assert(!allsame); + tt_assert(allin); + } + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + /* Test string_remove and remove and join_strings2 */ + smartlist_split_string(sl, + "Some say the Earth will end in ice and some in fire", + " ", 0, 0); + cp = smartlist_get(sl, 4); + tt_str_op(cp, ==, "will"); + smartlist_add(sl, cp); + smartlist_remove(sl, cp); + free(cp); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "Some,say,the,Earth,fire,end,in,ice,and,some,in"); + free(cp_alloc); + smartlist_string_remove(sl, "in"); + cp_alloc = smartlist_join_strings2(sl, "+XX", 1, 0, &sz); + tt_str_op(cp_alloc, ==, "Some+say+the+Earth+fire+end+some+ice+and"); + tt_int_op((int)sz, ==, 40); + + end: + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_free(sl); + free(cp_alloc); +} + +/** Run unit tests for smartlist set manipulation functions. */ +static void +test_container_smartlist_overlap(void *unused) +{ + smartlist_t *sl = smartlist_create(); + smartlist_t *ints = smartlist_create(); + smartlist_t *odds = smartlist_create(); + smartlist_t *evens = smartlist_create(); + smartlist_t *primes = smartlist_create(); + int i; + for (i=1; i < 10; i += 2) + smartlist_add(odds, (void*)(uintptr_t)i); + for (i=0; i < 10; i += 2) + smartlist_add(evens, (void*)(uintptr_t)i); + + /* add_all */ + smartlist_add_all(ints, odds); + smartlist_add_all(ints, evens); + tt_int_op(smartlist_len(ints), ==, 10); + + smartlist_add(primes, (void*)2); + smartlist_add(primes, (void*)3); + smartlist_add(primes, (void*)5); + smartlist_add(primes, (void*)7); + + /* overlap */ + tt_assert(smartlist_overlap(ints, odds)); + tt_assert(smartlist_overlap(odds, primes)); + tt_assert(smartlist_overlap(evens, primes)); + tt_assert(!smartlist_overlap(odds, evens)); + + /* intersect */ + smartlist_add_all(sl, odds); + smartlist_intersect(sl, primes); + tt_int_op(smartlist_len(sl), ==, 3); + tt_assert(smartlist_isin(sl, (void*)3)); + tt_assert(smartlist_isin(sl, (void*)5)); + tt_assert(smartlist_isin(sl, (void*)7)); + + /* subtract */ + smartlist_add_all(sl, primes); + smartlist_subtract(sl, odds); + tt_int_op(smartlist_len(sl), ==, 1); + tt_assert(smartlist_isin(sl, (void*)2)); + + end: + smartlist_free(odds); + smartlist_free(evens); + smartlist_free(ints); + smartlist_free(primes); + smartlist_free(sl); +} + +/** Run unit tests for smartlist-of-digests functions. */ +static void +test_container_smartlist_digests(void *unused) +{ + smartlist_t *sl = smartlist_create(); + + /* digest_isin. */ + smartlist_add(sl, xmemdup("AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH)); + smartlist_add(sl, xmemdup("\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH)); + smartlist_add(sl, xmemdup("\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH)); + tt_int_op(smartlist_digest_isin(NULL, "AAAAAAAAAAAAAAAAAAAA"), ==, 0); + tt_assert(smartlist_digest_isin(sl, "AAAAAAAAAAAAAAAAAAAA")); + tt_assert(smartlist_digest_isin(sl, "\00090AAB2AAAAaasdAAAAA")); + tt_int_op(smartlist_digest_isin(sl, "\00090AAB2AAABaasdAAAAA"), ==, 0); + + /* sort digests */ + smartlist_sort_digests(sl); + tt_mem_op(smartlist_get(sl, 0), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH); + tt_mem_op(smartlist_get(sl, 1), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH); + tt_mem_op(smartlist_get(sl, 2), ==, "AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH); + tt_int_op(smartlist_len(sl), ==, 3); + + /* uniq_digests */ + smartlist_uniq_digests(sl); + tt_int_op(smartlist_len(sl), ==, 2); + tt_mem_op(smartlist_get(sl, 0), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH); + tt_mem_op(smartlist_get(sl, 1), ==, "AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH); + + end: + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_free(sl); +} + +/** Run unit tests for concatenate-a-smartlist-of-strings functions. */ +static void +test_container_smartlist_join(void *unused) +{ + smartlist_t *sl = smartlist_create(); + smartlist_t *sl2 = smartlist_create(), *sl3 = smartlist_create(), + *sl4 = smartlist_create(); + char *joined=NULL; + /* unique, sorted. */ + smartlist_split_string(sl, + "Abashments Ambush Anchorman Bacon Banks Borscht " + "Bunks Inhumane Insurance Knish Know Manners " + "Maraschinos Stamina Sunbonnets Unicorns Wombats", + " ", 0, 0); + /* non-unique, sorted. */ + smartlist_split_string(sl2, + "Ambush Anchorman Anchorman Anemias Anemias Bacon " + "Crossbowmen Inhumane Insurance Knish Know Manners " + "Manners Maraschinos Wombats Wombats Work", + " ", 0, 0); + SMARTLIST_FOREACH_JOIN(sl, char *, cp1, + sl2, char *, cp2, + strcmp(cp1,cp2), + smartlist_add(sl3, cp2)) { + tt_str_op(cp1, ==, cp2); + smartlist_add(sl4, cp1); + } SMARTLIST_FOREACH_JOIN_END(cp1, cp2); + + SMARTLIST_FOREACH(sl3, const char *, cp, + tt_assert(smartlist_isin(sl2, cp) && + !smartlist_string_isin(sl, cp))); + SMARTLIST_FOREACH(sl4, const char *, cp, + tt_assert(smartlist_isin(sl, cp) && + smartlist_string_isin(sl2, cp))); + joined = smartlist_join_strings(sl3, ",", 0, NULL); + tt_str_op(joined, ==, "Anemias,Anemias,Crossbowmen,Work"); + free(joined); + joined = smartlist_join_strings(sl4, ",", 0, NULL); + tt_str_op(joined, ==, + "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance," + "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats"); + + end: + smartlist_free(sl4); + smartlist_free(sl3); + SMARTLIST_FOREACH(sl2, char *, cp, free(cp)); + smartlist_free(sl2); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_free(sl); + free(joined); +} + +/** Run unit tests for bitarray code */ +static void +test_container_bitarray(void *unused) +{ + bitarray_t *ba = NULL; + int i, j; + + ba = bitarray_init_zero(1); + tt_assert(ba); + tt_assert(! bitarray_is_set(ba, 0)); + bitarray_set(ba, 0); + tt_assert(bitarray_is_set(ba, 0)); + bitarray_clear(ba, 0); + tt_assert(! bitarray_is_set(ba, 0)); + bitarray_free(ba); + + ba = bitarray_init_zero(1023); + for (i = 1; i < 64; ) { + for (j = 0; j < 1023; ++j) { + if (j % i) + bitarray_set(ba, j); + else + bitarray_clear(ba, j); + } + for (j = 0; j < 1023; ++j) { + tt_bool_op(bitarray_is_set(ba, j), ==, j%i); + } + + if (i < 7) + ++i; + else if (i == 28) + i = 32; + else + i += 7; + } + + end: + if (ba) + bitarray_free(ba); +} + +/** Run unit tests for digest set code (implemented as a hashtable or as a + * bloom filter) */ +static void +test_container_digestset(void *unused) +{ + smartlist_t *included = smartlist_create(); + char d[SHA256_LENGTH]; + int i; + int ok = 1; + int false_positives = 0; + digestset_t *set = NULL; + + for (i = 0; i < 1000; ++i) { + random_bytes((uchar *)d, SHA256_LENGTH); + smartlist_add(included, xmemdup(d, SHA256_LENGTH)); + } + set = digestset_new(1000); + SMARTLIST_FOREACH(included, const char *, cp, + if (digestset_isin(set, cp)) + ok = 0); + tt_assert(ok); + SMARTLIST_FOREACH(included, const char *, cp, + digestset_add(set, cp)); + SMARTLIST_FOREACH(included, const char *, cp, + if (!digestset_isin(set, cp)) + ok = 0); + tt_assert(ok); + for (i = 0; i < 1000; ++i) { + random_bytes((uchar *)d, SHA256_LENGTH); + if (digestset_isin(set, d)) + ++false_positives; + } + tt_assert(false_positives < 50); /* Should be far lower. */ + + end: + if (set) + digestset_free(set); + SMARTLIST_FOREACH(included, char *, cp, free(cp)); + smartlist_free(included); +} + +typedef struct pq_entry_t { + const char *val; + int idx; +} pq_entry_t; + +/** Helper: return a tristate based on comparing two pq_entry_t values. */ +static int +_compare_strings_for_pqueue(const void *p1, const void *p2) +{ + const pq_entry_t *e1=p1, *e2=p2; + return strcmp(e1->val, e2->val); +} + +/** Run unit tests for heap-based priority queue functions. */ +static void +test_container_pqueue(void *unused) +{ + smartlist_t *sl = smartlist_create(); + int (*cmp)(const void *, const void*); + const int offset = offsetof(pq_entry_t, idx); +#define ENTRY(s) pq_entry_t s = { #s, -1 } + ENTRY(cows); + ENTRY(zebras); + ENTRY(fish); + ENTRY(frogs); + ENTRY(apples); + ENTRY(squid); + ENTRY(daschunds); + ENTRY(eggplants); + ENTRY(weissbier); + ENTRY(lobsters); + ENTRY(roquefort); + ENTRY(chinchillas); + ENTRY(fireflies); + +#define OK() smartlist_pqueue_assert_ok(sl, cmp, offset) + + cmp = _compare_strings_for_pqueue; + smartlist_pqueue_add(sl, cmp, offset, &cows); + smartlist_pqueue_add(sl, cmp, offset, &zebras); + smartlist_pqueue_add(sl, cmp, offset, &fish); + smartlist_pqueue_add(sl, cmp, offset, &frogs); + smartlist_pqueue_add(sl, cmp, offset, &apples); + smartlist_pqueue_add(sl, cmp, offset, &squid); + smartlist_pqueue_add(sl, cmp, offset, &daschunds); + smartlist_pqueue_add(sl, cmp, offset, &eggplants); + smartlist_pqueue_add(sl, cmp, offset, &weissbier); + smartlist_pqueue_add(sl, cmp, offset, &lobsters); + smartlist_pqueue_add(sl, cmp, offset, &roquefort); + + OK(); + + tt_int_op(smartlist_len(sl), ==, 11); + tt_ptr_op(smartlist_get(sl, 0), ==, &apples); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &apples); + tt_int_op(smartlist_len(sl), ==, 10); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &cows); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &daschunds); + smartlist_pqueue_add(sl, cmp, offset, &chinchillas); + OK(); + smartlist_pqueue_add(sl, cmp, offset, &fireflies); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &chinchillas); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &eggplants); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fireflies); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fish); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &frogs); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &lobsters); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &roquefort); + OK(); + tt_int_op(smartlist_len(sl), ==, 3); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &squid); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &weissbier); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &zebras); + tt_int_op(smartlist_len(sl), ==, 0); + OK(); + + /* Now test remove. */ + smartlist_pqueue_add(sl, cmp, offset, &cows); + smartlist_pqueue_add(sl, cmp, offset, &fish); + smartlist_pqueue_add(sl, cmp, offset, &frogs); + smartlist_pqueue_add(sl, cmp, offset, &apples); + smartlist_pqueue_add(sl, cmp, offset, &squid); + smartlist_pqueue_add(sl, cmp, offset, &zebras); + tt_int_op(smartlist_len(sl), ==, 6); + OK(); + smartlist_pqueue_remove(sl, cmp, offset, &zebras); + tt_int_op(smartlist_len(sl), ==, 5); + OK(); + smartlist_pqueue_remove(sl, cmp, offset, &cows); + tt_int_op(smartlist_len(sl), ==, 4); + OK(); + smartlist_pqueue_remove(sl, cmp, offset, &apples); + tt_int_op(smartlist_len(sl), ==, 3); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fish); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &frogs); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &squid); + tt_int_op(smartlist_len(sl), ==, 0); + OK(); + +#undef OK + + end: + + smartlist_free(sl); +} + +/** Run unit tests for string-to-void* map functions */ +static void +test_container_strmap(void *unused) +{ + strmap_t *map; + strmap_iter_t *iter; + const char *k; + void *v; + char *visited = NULL; + smartlist_t *found_keys = NULL; + + map = strmap_new(); + tt_assert(map); + tt_int_op(strmap_size(map), ==, 0); + tt_assert(strmap_isempty(map)); + v = strmap_set(map, "K1", (void*)99); + tt_ptr_op(v, ==, NULL); + tt_assert(!strmap_isempty(map)); + v = strmap_set(map, "K2", (void*)101); + tt_ptr_op(v, ==, NULL); + v = strmap_set(map, "K1", (void*)100); + tt_int_op((void*)99, ==, v); + tt_ptr_op(strmap_get(map, "K1"), ==, (void*)100); + tt_ptr_op(strmap_get(map, "K2"), ==, (void*)101); + tt_ptr_op(strmap_get(map, "K-not-there"), ==, NULL); + strmap_assert_ok(map); + + v = strmap_remove(map,"K2"); + strmap_assert_ok(map); + tt_ptr_op(v, ==, (void*)101); + tt_ptr_op(strmap_get(map, "K2"), ==, NULL); + tt_ptr_op(strmap_remove(map, "K2"), ==, NULL); + + strmap_set(map, "K2", (void*)101); + strmap_set(map, "K3", (void*)102); + strmap_set(map, "K4", (void*)103); + tt_int_op(strmap_size(map), ==, 4); + strmap_assert_ok(map); + strmap_set(map, "K5", (void*)104); + strmap_set(map, "K6", (void*)105); + strmap_assert_ok(map); + + /* Test iterator. */ + iter = strmap_iter_init(map); + found_keys = smartlist_create(); + while (!strmap_iter_done(iter)) { + strmap_iter_get(iter,&k,&v); + smartlist_add(found_keys, xstrdup(k)); + tt_ptr_op(v, ==, strmap_get(map, k)); + + if (!strcmp(k, "K2")) { + iter = strmap_iter_next_rmv(map,iter); + } else { + iter = strmap_iter_next(map,iter); + } + } + + /* Make sure we removed K2, but not the others. */ + tt_ptr_op(strmap_get(map, "K2"), ==, NULL); + tt_ptr_op(strmap_get(map, "K5"), ==, (void*)104); + /* Make sure we visited everyone once */ + smartlist_sort_strings(found_keys); + visited = smartlist_join_strings(found_keys, ":", 0, NULL); + tt_str_op(visited, ==, "K1:K2:K3:K4:K5:K6"); + + strmap_assert_ok(map); + /* Clean up after ourselves. */ + strmap_free(map, NULL); + map = NULL; + + /* Now try some lc functions. */ + map = strmap_new(); + strmap_set_lc(map,"Ab.C", (void*)1); + tt_ptr_op(strmap_get(map, "ab.c"), ==, (void*)1); + strmap_assert_ok(map); + tt_ptr_op(strmap_get_lc(map, "AB.C"), ==, (void*)1); + tt_ptr_op(strmap_get(map, "AB.C"), ==, NULL); + tt_ptr_op(strmap_remove_lc(map, "aB.C"), ==, (void*)1); + strmap_assert_ok(map); + tt_ptr_op(strmap_get_lc(map, "AB.C"), ==, NULL); + + end: + if (map) + strmap_free(map,NULL); + if (found_keys) { + SMARTLIST_FOREACH(found_keys, char *, cp, free(cp)); + smartlist_free(found_keys); + } + free(visited); +} + +/** Run unit tests for getting the median of a list. */ +static void +test_container_order_functions(void *unused) +{ + int lst[25], n = 0; + // int a=12,b=24,c=25,d=60,e=77; + +#define median() median_int(lst, n) + + lst[n++] = 12; + tt_int_op(median(), ==, 12); /* 12 */ + lst[n++] = 77; + //smartlist_shuffle(sl); + tt_int_op(median(), ==, 12); /* 12, 77 */ + lst[n++] = 77; + //smartlist_shuffle(sl); + tt_int_op(median(), ==, 77); /* 12, 77, 77 */ + lst[n++] = 24; + tt_int_op(median(), ==, 24); /* 12,24,77,77 */ + lst[n++] = 60; + lst[n++] = 12; + lst[n++] = 25; + //smartlist_shuffle(sl); + tt_int_op(median(), ==, 25); /* 12,12,24,25,60,77,77 */ +#undef median + + end: + ; +} + +#define T(name) \ + { #name, test_container_##name, 0, NULL, NULL } + +struct testcase_t container_tests[] = { + T(smartlist_basic), + T(smartlist_strings), + T(smartlist_overlap), + T(smartlist_digests), + T(smartlist_join), + T(bitarray), + T(digestset), + T(strmap), + T(pqueue), + T(order_functions), + END_OF_TESTCASES +}; + diff --git a/src/util.c b/src/util.c index 231c3a8..9b9fa48 100644 --- a/src/util.c +++ b/src/util.c @@ -88,6 +88,55 @@ xstrdup(const char *s) return xmemdup(s, strlen(s) + 1); } +char * +xstrndup(const char *s, size_t maxsize) +{ + char *copy; + size_t size; + /* strnlen is not in any standard :-( */ + for (size = 0; size < maxsize; size++) + if (s[size] == '\0') + break; + + copy = xmalloc(size + 1); + memcpy(copy, s, size); + copy[size] = '\0'; + return copy; +} + +/******************************** Mathematics ********************************/ + +unsigned int +ui64_log2(uint64_t u64) +{ + unsigned int r = 0; + if (u64 >= (((uint64_t)1)<<32)) { + u64 >>= 32; + r = 32; + } + if (u64 >= (((uint64_t)1)<<16)) { + u64 >>= 16; + r += 16; + } + if (u64 >= (((uint64_t)1)<<8)) { + u64 >>= 8; + r += 8; + } + if (u64 >= (((uint64_t)1)<<4)) { + u64 >>= 4; + r += 4; + } + if (u64 >= (((uint64_t)1)<<2)) { + u64 >>= 2; + r += 2; + } + if (u64 >= (((uint64_t)1)<<1)) { + u64 >>= 1; + r += 1; + } + return r; +} + /************************ Obfsproxy Network Routines *************************/ /** @@ -206,6 +255,31 @@ obfs_vsnprintf(char *str, size_t size, const char *format, va_list args) return -1; return r; } +/** Remove from the string s every character which appears in + * strip. */ +void +ascii_strstrip(char *s, const char *strip) +{ + char *read = s; + while (*read) { + if (strchr(strip, *read)) { + ++read; + } else { + *s++ = *read++; + } + } + *s = '\0'; +} + +void +ascii_strlower(char *s) +{ + while (*s) { + if (*s >= 'A' && *s <= 'Z') + *s = *s - 'A' + 'a'; + ++s; + } +} /************************ Doubly Linked List (DLL) ******************/ diff --git a/src/util.h b/src/util.h index d365cbc..e44a711 100644 --- a/src/util.h +++ b/src/util.h @@ -8,6 +8,7 @@ #include "config.h" #include <stdarg.h> /* for va_list */ #include <stddef.h> /* size_t, offsetof, NULL, etc */ +#include <stdint.h> /* intN_t, uintN_t */ #ifndef __GNUC__ #define __attribute__(x) /* nothing */ @@ -34,6 +35,11 @@ void *xzalloc(size_t size) ATTR_MALLOC; /* clears memory */ void *xrealloc(void *ptr, size_t size); void *xmemdup(const void *ptr, size_t size) ATTR_MALLOC; char *xstrdup(const char *s) ATTR_MALLOC; +char *xstrndup(const char *s, size_t maxsize) ATTR_MALLOC; + +/***** Math. *****/ + +unsigned int ui64_log2(uint64_t u64); /***** Network functions stuff. *****/ @@ -48,6 +54,18 @@ int init_evdns_base(struct event_base *base); /***** String functions stuff. *****/ +static inline int ascii_isspace(unsigned char c) +{ + return (c == ' ' || + c == '\t' || + c == '\r' || + c == '\n' || + c == '\v' || + c == '\f'); +} +void ascii_strstrip(char *s, const char *kill); +void ascii_strlower(char *s); + int obfs_vsnprintf(char *str, size_t size, const char *format, va_list args); int obfs_snprintf(char *str, size_t size, @@ -133,5 +151,4 @@ void log_debug(const char *format, ...) log_error("aborted at %s:%d", __FILE__, __LINE__); \ } while (0) - #endif

1 0

[obfsproxy/master] Fix a memory leak in obfs2.c:derive_padding_key (and be scrupulous about tearing down everything at shutdown time, too)
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit d4c299eeb58772fa9a76b8195ba8b803988f9938 Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 11:08:52 2011 -0700 Fix a memory leak in obfs2.c:derive_padding_key (and be scrupulous about tearing down everything at shutdown time, too) --- src/crypt.c | 4 ++-- src/main.c | 19 +++++++++++++++++-- src/protocols/obfs2.c | 10 ++-------- 3 files changed, 21 insertions(+), 12 deletions(-) diff --git a/src/crypt.c b/src/crypt.c index 98516e6..e338214 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -26,7 +26,7 @@ #endif /** - Initializes the obfs2 crypto subsystem. + Initializes the crypto subsystem. */ int initialize_crypto(void) @@ -58,7 +58,7 @@ initialize_crypto(void) } /** - Cleans up the obfs2 crypto subsystem. + Cleans up the crypto subsystem. */ void cleanup_crypto(void) diff --git a/src/main.c b/src/main.c index cf811fa..254be94 100644 --- a/src/main.c +++ b/src/main.c @@ -4,6 +4,7 @@ #include "util.h" +#include "crypt.h" #include "network.h" #include "protocol.h" @@ -14,6 +15,7 @@ #include <string.h> #include <event2/event.h> +#include <event2/dns.h> /* The character that seperates multiple listeners in the cli */ #define SEPARATOR "+" @@ -305,6 +307,12 @@ main(int argc, const char **argv) WSAStartup(0x101, &wsaData); #endif + /* Initialize crypto */ + if (initialize_crypto() < 0) { + log_warn("Can't initialize crypto; failing"); + return 1; + } + /* Initialize libevent */ the_event_base = event_base_new(); if (!the_event_base) { @@ -365,14 +373,21 @@ main(int argc, const char **argv) "%d survived.", n_protocols, actual_protocols,n_listeners); - /* run the event loop if at least a listener was created. */ + /* run the event loop if at least one listener was created. */ if (n_listeners) event_base_dispatch(the_event_base); log_info("Exiting."); - close_obfsproxy_logfile(); free_all_listeners(); + evdns_base_free(get_evdns_base(), 0); + event_free(sig_int); + event_free(sig_term); + event_base_free(the_event_base); + + cleanup_crypto(); + + close_obfsproxy_logfile(); free(protocol_options); free(n_options_array); free(protocols); diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index f17af90..5c9aedc 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -27,7 +27,6 @@ downcast(struct protocol_t *proto) /* This function parses 'options' and fills the protocol parameters structure 'params'. - It then fills the obfs2 vtable and initializes the crypto subsystem. Returns 0 on success, -1 on fail. */ @@ -43,12 +42,6 @@ obfs2_init(int n_options, const char *const *options) return NULL; } - if (initialize_crypto() < 0) { - log_warn("Can't initialize crypto; failing"); - free(params); - return NULL; - } - return params; } @@ -219,6 +212,7 @@ derive_padding_key(void *s, const uchar *seed, digest_update(c, state->secret_seed, OBFUSCATE_SEED_LENGTH); digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); + digest_free(c); if (seed_nonzero(state->secret_seed)) { digest_t *d; @@ -227,13 +221,13 @@ derive_padding_key(void *s, const uchar *seed, d = digest_new(); digest_update(d, buf, sizeof(buf)); digest_getdigest(d, buf, sizeof(buf)); + digest_free(d); } } cryptstate = crypt_new(buf, 16); crypt_set_iv(cryptstate, buf+16, 16); memset(buf, 0, 16); - digest_free(c); return cryptstate; }

1 0