June 2018 - tor-commits - lists.torproject.org

[tor/master] Rectify include paths after container split (automatic)
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit b8be8265b6dc477efe591ccdb14fcd4b044dd241 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 15:40:15 2018 -0400 Rectify include paths after container split (automatic) --- src/common/address.c | 2 +- src/common/address.h | 2 +- src/common/address_set.c | 2 +- src/common/compat.c | 2 +- src/common/compat_time.c | 2 +- src/common/compat_winthreads.c | 2 +- src/common/confline.c | 2 +- src/common/confline.h | 2 +- src/common/log.c | 2 +- src/common/memarea.c | 2 +- src/common/sandbox.c | 2 +- src/common/storagedir.c | 2 +- src/common/util.c | 2 +- src/common/util_bug.c | 2 +- src/lib/container/container.c | 2 +- src/lib/crypt_ops/crypto.c | 2 +- src/lib/crypt_ops/crypto_curve25519.c | 2 +- src/lib/crypt_ops/crypto_digest.c | 2 +- src/lib/crypt_ops/crypto_digest.h | 2 +- src/lib/crypt_ops/crypto_format.c | 2 +- src/lib/crypt_ops/crypto_rand.c | 2 +- src/lib/tls/tortls.c | 2 +- src/or/hs_client.c | 2 +- src/or/hs_descriptor.h | 2 +- src/or/or.h | 2 +- src/or/parsecommon.h | 2 +- src/or/protover.h | 2 +- src/test/test_bridges.c | 2 +- src/test/test_dir_common.c | 2 +- src/test/test_guardfraction.c | 2 +- src/test/test_routerlist.c | 2 +- 31 files changed, 31 insertions(+), 31 deletions(-) diff --git a/src/common/address.c b/src/common/address.c index f135f1ffd..27f8c4efe 100644 --- a/src/common/address.c +++ b/src/common/address.c @@ -40,7 +40,7 @@ #include "common/util_format.h" #include "common/address.h" #include "common/torlog.h" -#include "common/container.h" +#include "lib/container/container.h" #include "common/sandbox.h" #ifdef HAVE_SYS_TIME_H diff --git a/src/common/address.h b/src/common/address.h index 6986143f6..b8fccd81e 100644 --- a/src/common/address.h +++ b/src/common/address.h @@ -15,7 +15,7 @@ #include "orconfig.h" #include "lib/cc/torint.h" #include "common/compat.h" -#include "common/container.h" +#include "lib/container/container.h" #include "common/util_bug.h" #ifdef ADDRESS_PRIVATE diff --git a/src/common/address_set.c b/src/common/address_set.c index 65c4cbf1e..d30343b1c 100644 --- a/src/common/address_set.c +++ b/src/common/address_set.c @@ -14,7 +14,7 @@ #include "common/address_set.h" #include "common/address.h" #include "common/compat.h" -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto_rand.h" #include "common/util.h" #include "siphash.h" diff --git a/src/common/compat.c b/src/common/compat.c index dece798bc..577ebe757 100644 --- a/src/common/compat.c +++ b/src/common/compat.c @@ -126,7 +126,7 @@ SecureZeroMemory(PVOID ptr, SIZE_T cnt) #include "common/torlog.h" #include "common/util.h" -#include "common/container.h" +#include "lib/container/container.h" #include "common/address.h" #include "common/sandbox.h" diff --git a/src/common/compat_time.c b/src/common/compat_time.c index da323e55a..032c4e43a 100644 --- a/src/common/compat_time.c +++ b/src/common/compat_time.c @@ -37,7 +37,7 @@ #include "lib/err/torerr.h" #include "common/torlog.h" #include "common/util.h" -#include "common/container.h" +#include "lib/container/container.h" #ifndef HAVE_GETTIMEOFDAY #ifdef HAVE_FTIME diff --git a/src/common/compat_winthreads.c b/src/common/compat_winthreads.c index 95e70d06b..eeb0b9751 100644 --- a/src/common/compat_winthreads.c +++ b/src/common/compat_winthreads.c @@ -16,7 +16,7 @@ #include <windows.h> #include <process.h> #include "common/util.h" -#include "common/container.h" +#include "lib/container/container.h" #include "common/torlog.h" /* This value is more or less total cargo-cult */ diff --git a/src/common/confline.c b/src/common/confline.c index 2ea2e9c3b..7343c5f52 100644 --- a/src/common/confline.c +++ b/src/common/confline.c @@ -8,7 +8,7 @@ #include "common/confline.h" #include "common/torlog.h" #include "common/util.h" -#include "common/container.h" +#include "lib/container/container.h" static int config_get_lines_aux(const char *string, config_line_t **result, int extended, int allow_include, diff --git a/src/common/confline.h b/src/common/confline.h index 4cc8286fc..10af34a0a 100644 --- a/src/common/confline.h +++ b/src/common/confline.h @@ -7,7 +7,7 @@ #ifndef TOR_CONFLINE_H #define TOR_CONFLINE_H -#include "common/container.h" +#include "lib/container/container.h" /** Ordinary configuration line. */ #define CONFIG_LINE_NORMAL 0 diff --git a/src/common/log.c b/src/common/log.c index 928a3fba8..8ea686a12 100644 --- a/src/common/log.c +++ b/src/common/log.c @@ -33,7 +33,7 @@ #include "common/util.h" #define LOG_PRIVATE #include "common/torlog.h" -#include "common/container.h" +#include "lib/container/container.h" #include "lib/err/torerr.h" #ifdef HAVE_ANDROID_LOG_H diff --git a/src/common/memarea.c b/src/common/memarea.c index 12ad9c511..ef6b78ecc 100644 --- a/src/common/memarea.c +++ b/src/common/memarea.c @@ -13,7 +13,7 @@ #include "common/util.h" #include "common/compat.h" #include "common/torlog.h" -#include "common/container.h" +#include "lib/container/container.h" #ifndef DISABLE_MEMORY_SENTINELS diff --git a/src/common/sandbox.c b/src/common/sandbox.c index a33463f74..e67cedf0b 100644 --- a/src/common/sandbox.c +++ b/src/common/sandbox.c @@ -33,7 +33,7 @@ #include <stdlib.h> #include "common/sandbox.h" -#include "common/container.h" +#include "lib/container/container.h" #include "lib/err/torerr.h" #include "common/torlog.h" #include "lib/cc/torint.h" diff --git a/src/common/storagedir.c b/src/common/storagedir.c index ee80bcc53..f3270ce7b 100644 --- a/src/common/storagedir.c +++ b/src/common/storagedir.c @@ -1,7 +1,7 @@ /* Copyright (c) 2017-2018, The Tor Project, Inc. */ /* See LICENSE for licensing information */ -#include "common/container.h" +#include "lib/container/container.h" #include "common/compat.h" #include "common/confline.h" #include "common/memarea.h" diff --git a/src/common/util.c b/src/common/util.c index fbb2fed39..cd8ff93a3 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -18,7 +18,7 @@ #include "common/torlog.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/cc/torint.h" -#include "common/container.h" +#include "lib/container/container.h" #include "common/address.h" #include "common/sandbox.h" #include "lib/err/backtrace.h" diff --git a/src/common/util_bug.c b/src/common/util_bug.c index 524d48c68..3b249bdfc 100644 --- a/src/common/util_bug.c +++ b/src/common/util_bug.c @@ -11,7 +11,7 @@ #include "common/util_bug.h" #include "common/torlog.h" #include "lib/err/backtrace.h" -#include "common/container.h" +#include "lib/container/container.h" #ifdef __COVERITY__ int bug_macro_deadcode_dummy__ = 0; diff --git a/src/lib/container/container.c b/src/lib/container/container.c index a7810ba90..d31044fe2 100644 --- a/src/lib/container/container.c +++ b/src/lib/container/container.c @@ -12,7 +12,7 @@ **/ #include "common/util.h" -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto_digest.h" #include <stdlib.h> diff --git a/src/lib/crypt_ops/crypto.c b/src/lib/crypt_ops/crypto.c index b562578c5..de7e271d3 100644 --- a/src/lib/crypt_ops/crypto.c +++ b/src/lib/crypt_ops/crypto.c @@ -66,7 +66,7 @@ ENABLE_GCC_WARNING(redundant-decls) #include "lib/cc/torint.h" #include "lib/crypt_ops/aes.h" #include "common/util.h" -#include "common/container.h" +#include "lib/container/container.h" #include "common/compat.h" #include "common/sandbox.h" #include "common/util_format.h" diff --git a/src/lib/crypt_ops/crypto_curve25519.c b/src/lib/crypt_ops/crypto_curve25519.c index 8302483d8..1e7a45625 100644 --- a/src/lib/crypt_ops/crypto_curve25519.c +++ b/src/lib/crypt_ops/crypto_curve25519.c @@ -20,7 +20,7 @@ #ifdef HAVE_SYS_STAT_H #include <sys/stat.h> #endif -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto_curve25519.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/crypt_ops/crypto_format.h" diff --git a/src/lib/crypt_ops/crypto_digest.c b/src/lib/crypt_ops/crypto_digest.c index 44494337c..d746aaaca 100644 --- a/src/lib/crypt_ops/crypto_digest.c +++ b/src/lib/crypt_ops/crypto_digest.c @@ -10,7 +10,7 @@ * operations. **/ -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/crypt_ops/crypto_openssl_mgt.h" #include "lib/crypt_ops/crypto_util.h" diff --git a/src/lib/crypt_ops/crypto_digest.h b/src/lib/crypt_ops/crypto_digest.h index 96ac03850..129258245 100644 --- a/src/lib/crypt_ops/crypto_digest.h +++ b/src/lib/crypt_ops/crypto_digest.h @@ -15,7 +15,7 @@ #include <stdio.h> -#include "common/container.h" +#include "lib/container/container.h" #include "lib/cc/torint.h" /** Length of the output of our message digest. */ diff --git a/src/lib/crypt_ops/crypto_format.c b/src/lib/crypt_ops/crypto_format.c index 07008eff2..246f28716 100644 --- a/src/lib/crypt_ops/crypto_format.c +++ b/src/lib/crypt_ops/crypto_format.c @@ -14,7 +14,7 @@ #ifdef HAVE_SYS_STAT_H #include <sys/stat.h> #endif -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto_curve25519.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/crypt_ops/crypto_ed25519.h" diff --git a/src/lib/crypt_ops/crypto_rand.c b/src/lib/crypt_ops/crypto_rand.c index 0bd7b078c..af258abea 100644 --- a/src/lib/crypt_ops/crypto_rand.c +++ b/src/lib/crypt_ops/crypto_rand.c @@ -21,7 +21,7 @@ #include <wincrypt.h> #endif /* defined(_WIN32) */ -#include "common/container.h" +#include "lib/container/container.h" #include "common/compat.h" #include "lib/crypt_ops/compat_openssl.h" #include "lib/crypt_ops/crypto_util.h" diff --git a/src/lib/tls/tortls.c b/src/lib/tls/tortls.c index ac45175c7..ea3a42054 100644 --- a/src/lib/tls/tortls.c +++ b/src/lib/tls/tortls.c @@ -55,7 +55,7 @@ ENABLE_GCC_WARNING(redundant-decls) #include "lib/tls/tortls.h" #include "common/util.h" #include "common/torlog.h" -#include "common/container.h" +#include "lib/container/container.h" #include <string.h> #ifdef OPENSSL_1_1_API diff --git a/src/or/hs_client.c b/src/or/hs_client.c index 90a3fb3dc..a977fa44f 100644 --- a/src/or/hs_client.c +++ b/src/or/hs_client.c @@ -16,7 +16,7 @@ #include "or/config.h" #include "or/connection.h" #include "or/connection_edge.h" -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_util.h" #include "or/directory.h" diff --git a/src/or/hs_descriptor.h b/src/or/hs_descriptor.h index 5478edc89..640136f48 100644 --- a/src/or/hs_descriptor.h +++ b/src/or/hs_descriptor.h @@ -13,7 +13,7 @@ #include "or/or.h" #include "common/address.h" -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto.h" #include "lib/crypt_ops/crypto_ed25519.h" #include "trunnel/ed25519_cert.h" /* needed for trunnel */ diff --git a/src/or/or.h b/src/or/or.h index cb7e84e68..c70123934 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -69,7 +69,7 @@ #include "lib/crypt_ops/crypto_hkdf.h" #include "lib/tls/tortls.h" #include "common/torlog.h" -#include "common/container.h" +#include "lib/container/container.h" #include "lib/compress/compress.h" #include "common/address.h" #include "common/compat_libevent.h" diff --git a/src/or/parsecommon.h b/src/or/parsecommon.h index 93e62a559..c786bcc54 100644 --- a/src/or/parsecommon.h +++ b/src/or/parsecommon.h @@ -9,7 +9,7 @@ #ifndef TOR_PARSECOMMON_H #define TOR_PARSECOMMON_H -#include "common/container.h" +#include "lib/container/container.h" #include "lib/crypt_ops/crypto.h" #include "common/memarea.h" diff --git a/src/or/protover.h b/src/or/protover.h index 6236ed133..99502645c 100644 --- a/src/or/protover.h +++ b/src/or/protover.h @@ -9,7 +9,7 @@ #ifndef TOR_PROTOVER_H #define TOR_PROTOVER_H -#include "common/container.h" +#include "lib/container/container.h" /** The first version of Tor that included "proto" entries in its * descriptors. Authorities should use this to decide whether to diff --git a/src/test/test_bridges.c b/src/test/test_bridges.c index c1de731b2..127b58762 100644 --- a/src/test/test_bridges.c +++ b/src/test/test_bridges.c @@ -15,7 +15,7 @@ #include "common/address.h" #include "or/bridges.h" #include "or/config.h" -#include "common/container.h" +#include "lib/container/container.h" #include "or/transports.h" #include "common/util.h" diff --git a/src/test/test_dir_common.c b/src/test/test_dir_common.c index 6933800eb..5212810b7 100644 --- a/src/test/test_dir_common.c +++ b/src/test/test_dir_common.c @@ -6,7 +6,7 @@ #include "orconfig.h" #define DIRVOTE_PRIVATE #include "test/test.h" -#include "common/container.h" +#include "lib/container/container.h" #include "or/or.h" #include "or/dirauth/dirvote.h" #include "or/nodelist.h" diff --git a/src/test/test_guardfraction.c b/src/test/test_guardfraction.c index fc451b162..12e64d0e7 100644 --- a/src/test/test_guardfraction.c +++ b/src/test/test_guardfraction.c @@ -9,7 +9,7 @@ #include "or/or.h" #include "or/config.h" #include "or/dirserv.h" -#include "common/container.h" +#include "lib/container/container.h" #include "or/entrynodes.h" #include "common/util.h" #include "or/routerparse.h" diff --git a/src/test/test_routerlist.c b/src/test/test_routerlist.c index e8f847833..5011e2285 100644 --- a/src/test/test_routerlist.c +++ b/src/test/test_routerlist.c @@ -16,7 +16,7 @@ #include "or/or.h" #include "or/config.h" #include "or/connection.h" -#include "common/container.h" +#include "lib/container/container.h" #include "or/control.h" #include "lib/crypt_ops/crypto_rand.h" #include "or/directory.h"

1 0

[tor/master] Refactor container into a library.
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit 77dff00b18fc70acdb2939dd20197a0044d41fe5 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 15:39:36 2018 -0400 Refactor container into a library. --- .gitignore | 2 ++ Makefile.am | 2 ++ src/common/include.am | 2 -- src/include.am | 1 + src/{common => lib/container}/container.c | 0 src/{common => lib/container}/container.h | 0 src/lib/container/include.am | 17 +++++++++++++++++ src/rust/build.rs | 1 + 8 files changed, 23 insertions(+), 2 deletions(-) diff --git a/.gitignore b/.gitignore index c5da8e423..deb369381 100644 --- a/.gitignore +++ b/.gitignore @@ -165,6 +165,8 @@ uptime-*.json /src/lib/libcurve25519_donna.a /src/lib/libtor-compress.a /src/lib/libtor-compress-testing.a +/src/lib/libtor-container.a +/src/lib/libtor-container-testing.a /src/lib/libtor-crypt-ops.a /src/lib/libtor-crypt-ops-testing.a /src/lib/libtor-ctime.a diff --git a/Makefile.am b/Makefile.am index 960417df9..1b71e478f 100644 --- a/Makefile.am +++ b/Makefile.am @@ -40,6 +40,7 @@ endif # "Common" libraries used to link tor's utility code. TOR_UTIL_LIBS = \ src/common/libor.a \ + src/lib/libtor-container.a \ src/lib/libtor-malloc.a \ src/lib/libtor-err.a \ src/lib/libtor-ctime.a @@ -48,6 +49,7 @@ TOR_UTIL_LIBS = \ # and tests) TOR_UTIL_TESTING_LIBS = \ src/common/libor-testing.a \ + src/lib/libtor-container-testing.a \ src/lib/libtor-malloc-testing.a \ src/lib/libtor-err-testing.a \ src/lib/libtor-ctime-testing.a diff --git a/src/common/include.am b/src/common/include.am index 29bbdd769..422397886 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -38,7 +38,6 @@ LIBOR_A_SRC = \ src/common/compat_threads.c \ src/common/compat_time.c \ src/common/confline.c \ - src/common/container.c \ src/common/log.c \ src/common/memarea.c \ src/common/util.c \ @@ -87,7 +86,6 @@ COMMONHEADERS = \ src/common/compat_threads.h \ src/common/compat_time.h \ src/common/confline.h \ - src/common/container.h \ src/common/handles.h \ src/common/memarea.h \ src/common/linux_syscalls.inc \ diff --git a/src/include.am b/src/include.am index 46569a4b4..9fa901c41 100644 --- a/src/include.am +++ b/src/include.am @@ -3,6 +3,7 @@ include src/lib/err/include.am include src/lib/cc/include.am include src/lib/ctime/include.am include src/lib/compress/include.am +include src/lib/container/include.am include src/lib/crypt_ops/include.am include src/lib/include.libdonna.am include src/lib/malloc/include.am diff --git a/src/common/container.c b/src/lib/container/container.c similarity index 100% rename from src/common/container.c rename to src/lib/container/container.c diff --git a/src/common/container.h b/src/lib/container/container.h similarity index 100% rename from src/common/container.h rename to src/lib/container/container.h diff --git a/src/lib/container/include.am b/src/lib/container/include.am new file mode 100644 index 000000000..d7648c80c --- /dev/null +++ b/src/lib/container/include.am @@ -0,0 +1,17 @@ + +noinst_LIBRARIES += src/lib/libtor-container.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-container-testing.a +endif + +src_lib_libtor_container_a_SOURCES = \ + src/lib/container/container.c + +src_lib_libtor_container_testing_a_SOURCES = \ + $(src_lib_libtor_container_a_SOURCES) +src_lib_libtor_container_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_container_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/container/container.h diff --git a/src/rust/build.rs b/src/rust/build.rs index acbedd4d4..a4f38d3b4 100644 --- a/src/rust/build.rs +++ b/src/rust/build.rs @@ -151,6 +151,7 @@ pub fn main() { // moving forward! cfg.component("tor-crypt-ops-testing"); cfg.component("or-testing"); + cfg.component("tor-container-testing"); cfg.component("tor-malloc"); cfg.component("tor-err-testing"); cfg.component("or-event-testing");

1 0

[tor/master] Split container.c based on container types, and minimize includes
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit 657ff55408d82f49fc9599cb662702cdc0995f08 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 16:25:31 2018 -0400 Split container.c based on container types, and minimize includes Minimizing includes revealed other places includes were necessary. --- src/common/util_bug.h | 1 + src/lib/container/bitarray.h | 80 +++ src/lib/container/bloomfilt.c | 49 ++ src/lib/container/bloomfilt.h | 58 ++ src/lib/container/container.h | 745 +------------------------ src/lib/container/include.am | 12 +- src/lib/container/map.c | 413 ++++++++++++++ src/lib/container/map.h | 255 +++++++++ src/lib/container/order.c | 51 ++ src/lib/container/order.h | 54 ++ src/lib/container/{container.c => smartlist.c} | 461 +-------------- src/lib/container/smartlist.h | 351 ++++++++++++ src/lib/malloc/util_malloc.c | 1 - src/lib/malloc/util_malloc.h | 2 + 14 files changed, 1332 insertions(+), 1201 deletions(-) diff --git a/src/common/util_bug.h b/src/common/util_bug.h index 9659f59b7..fb5ab25c1 100644 --- a/src/common/util_bug.h +++ b/src/common/util_bug.h @@ -37,6 +37,7 @@ #define TOR_UTIL_BUG_H #include "orconfig.h" +#include <stdlib.h> #include "common/compat.h" #include "lib/testsupport/testsupport.h" diff --git a/src/lib/container/bitarray.h b/src/lib/container/bitarray.h new file mode 100644 index 000000000..2cea433fb --- /dev/null +++ b/src/lib/container/bitarray.h @@ -0,0 +1,80 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_BITARRAY_H +#define TOR_BITARRAY_H + +#include "orconfig.h" +#include <string.h> +#include "lib/cc/torint.h" +#include "lib/malloc/util_malloc.h" + +#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 /* SIZEOF_INT == 4 || ... */ +#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 tor_calloc(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 = tor_reallocarray(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) +{ + tor_free(ba); +} +#define bitarray_free(ba) FREE_AND_NULL(bitarray_t, bitarray_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)); +} + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/bloomfilt.c b/src/lib/container/bloomfilt.c new file mode 100644 index 000000000..4847408ee --- /dev/null +++ b/src/lib/container/bloomfilt.c @@ -0,0 +1,49 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, 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 <stdlib.h> +#include "lib/malloc/util_malloc.h" +#include "lib/container/bloomfilt.h" +#include "common/util.h" // For tor_log2 + +/** 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 << (tor_log2(max_elements)+5); + digestset_t *r = tor_malloc(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); + tor_free(set); +} diff --git a/src/lib/container/bloomfilt.h b/src/lib/container/bloomfilt.h new file mode 100644 index 000000000..adcdb10fc --- /dev/null +++ b/src/lib/container/bloomfilt.h @@ -0,0 +1,58 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_BLOOMFILT_H +#define TOR_BLOOMFILT_H + +#include "orconfig.h" +#include "lib/cc/torint.h" +#include "lib/container/bitarray.h" +#include "siphash.h" + +/** 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 uint64_t x = siphash24g(digest, 20); + const uint32_t d1 = (uint32_t) x; + const uint32_t d2 = (uint32_t)( (x>>16) + x); + const uint32_t d3 = (uint32_t)( (x>>32) + x); + const uint32_t d4 = (uint32_t)( (x>>48) + x); + 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_contains(const digestset_t *set, const char *digest) +{ + const uint64_t x = siphash24g(digest, 20); + const uint32_t d1 = (uint32_t) x; + const uint32_t d2 = (uint32_t)( (x>>16) + x); + const uint32_t d3 = (uint32_t)( (x>>32) + x); + const uint32_t d4 = (uint32_t)( (x>>48) + x); + 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); +#define digestset_free(set) FREE_AND_NULL(digestset_t, digestset_free_, (set)) + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/container.h b/src/lib/container/container.h index c45bfc359..ba8983846 100644 --- a/src/lib/container/container.h +++ b/src/lib/container/container.h @@ -6,745 +6,10 @@ #ifndef TOR_CONTAINER_H #define TOR_CONTAINER_H -#include <stddef.h> -#include <stdlib.h> -#include <string.h> - -#include "lib/cc/compat_compiler.h" -#include "lib/cc/torint.h" -#include "lib/testsupport/testsupport.h" -#include "lib/malloc/util_malloc.h" -#include "common/util_bug.h" -#include "siphash.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; - -MOCK_DECL(smartlist_t *, smartlist_new, (void)); -MOCK_DECL(void, smartlist_free_, (smartlist_t *sl)); -#define smartlist_free(sl) FREE_AND_NULL(smartlist_t, smartlist_free_, (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_add_strdup(struct smartlist_t *sl, const char *string); -void smartlist_remove(smartlist_t *sl, const void *element); -void smartlist_remove_keeporder(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_contains(const smartlist_t *sl, const void *element); -int smartlist_contains_string(const smartlist_t *sl, const char *element); -int smartlist_pos(const smartlist_t *sl, const void *element); -int smartlist_string_pos(const smartlist_t *, const char *elt); -int smartlist_contains_string_case(const smartlist_t *sl, const char *element); -int smartlist_contains_int_as_string(const smartlist_t *sl, int num); -int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2); -int smartlist_contains_digest(const smartlist_t *sl, const char *element); -int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2); -int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2); -void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2); -void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2); - -/* smartlist_choose() is defined in crypto.[ch] */ -#ifdef DEBUG_SMARTLIST -/** Return the number of items in sl. - */ -static inline int smartlist_len(const smartlist_t *sl); -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); -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 /* !(defined(DEBUG_SMARTLIST)) */ -#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 /* defined(DEBUG_SMARTLIST) */ - -/** 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), - int *count_out); -#define smartlist_get_most_frequent(sl, compare) \ - smartlist_get_most_frequent_((sl), (compare), NULL) -void smartlist_uniq(smartlist_t *sl, - int (*compare)(const void **a, const void **b), - void (*free_fn)(void *elt)); - -void smartlist_sort_strings(smartlist_t *sl); -void smartlist_sort_digests(smartlist_t *sl); -void smartlist_sort_digests256(smartlist_t *sl); -void smartlist_sort_pointers(smartlist_t *sl); - -const char *smartlist_get_most_frequent_string(smartlist_t *sl); -const char *smartlist_get_most_frequent_string_(smartlist_t *sl, - int *count_out); -const uint8_t *smartlist_get_most_frequent_digest256(smartlist_t *sl); - -void smartlist_uniq_strings(smartlist_t *sl); -void smartlist_uniq_digests(smartlist_t *sl); -void smartlist_uniq_digests256(smartlist_t *sl); -void *smartlist_bsearch(smartlist_t *sl, const void *key, - int (*compare)(const void *key, const void **member)); -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 statements inside the loop body. 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_BEGIN(list, char *, cp) { - * printf("%d: %s\n", cp_sl_idx, cp); - * tor_free(cp); - * } SMARTLIST_FOREACH_END(cp); - * smartlist_free(list); - * </pre> - * - * Example use (advanced): - * <pre> - * SMARTLIST_FOREACH_BEGIN(list, char *, cp) { - * if (!strcmp(cp, "junk")) { - * tor_free(cp); - * SMARTLIST_DEL_CURRENT(list, cp); - * } - * } SMARTLIST_FOREACH_END(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); - * tor_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")) { - * tor_free(cp); - * smartlist_del(list, cp_sl_idx); - * --cp_sl_idx; - * --cp_sl_len; - * } - * } - * } - * </pre> - */ -#define SMARTLIST_FOREACH_BEGIN(sl, type, var) \ - STMT_BEGIN \ - 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; \ - (void) var ## _sl_idx; \ - } STMT_END - -/** - * An alias for SMARTLIST_FOREACH_BEGIN and SMARTLIST_FOREACH_END, using - * cmd as the loop body. This wrapper is here for convenience with - * very short loops. - * - * By convention, we do not use this for loops which nest, or for loops over - * 10 lines or so. Use SMARTLIST_FOREACH_{BEGIN,END} for those. - */ -#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) \ - STMT_BEGIN \ - smartlist_del(sl, var ## _sl_idx); \ - --var ## _sl_idx; \ - --var ## _sl_len; \ - STMT_END - -/** 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_KEEPORDER(sl, var) \ - STMT_BEGIN \ - smartlist_del_keeporder(sl, var ## _sl_idx); \ - --var ## _sl_idx; \ - --var ## _sl_len; \ - STMT_END - -/** 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) \ - STMT_BEGIN \ - smartlist_set(sl, var ## _sl_idx, val); \ - STMT_END - -/* 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, - * tor_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 = tor_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) \ - STMT_BEGIN \ - 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) \ - } \ - STMT_END - -#define DECLARE_MAP_FNS(maptype, keytype, prefix) \ - typedef struct maptype maptype; \ - typedef struct prefix##entry_t *prefix##iter_t; \ - MOCK_DECL(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); \ - MOCK_DECL(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_); -/* Map from const uint8_t[DIGEST256_LEN] to void *. Implemented with a hash - * table. */ -DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_); - -#define MAP_FREE_AND_NULL(maptype, map, fn) \ - do { \ - maptype ## _free_((map), (fn)); \ - (map) = NULL; \ - } while (0) - -#define strmap_free(map, fn) MAP_FREE_AND_NULL(strmap, (map), (fn)) -#define digestmap_free(map, fn) MAP_FREE_AND_NULL(digestmap, (map), (fn)) -#define digest256map_free(map, fn) MAP_FREE_AND_NULL(digest256map, (map), (fn)) - -#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) \ - STMT_BEGIN \ - 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) \ - STMT_BEGIN \ - 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) \ - STMT_BEGIN \ - keyvar##_del = 1; \ - STMT_END - -/** Used to end a MAP_FOREACH() block. */ -#define MAP_FOREACH_END } STMT_END ; - -/** 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 DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \ - MAP_FOREACH(digest256map_, map, const uint8_t *, keyvar, valtype, valvar) -#define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ - MAP_FOREACH_MODIFY(digest256map_, map, const uint8_t *, \ - keyvar, valtype, valvar) -#define DIGEST256MAP_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; \ - ATTR_UNUSED static inline maptype* \ - prefix##new(void) \ - { \ - return (maptype*)digestmap_new(); \ - } \ - ATTR_UNUSED static inline digestmap_t* \ - prefix##to_digestmap(maptype *map) \ - { \ - return (digestmap_t*)map; \ - } \ - ATTR_UNUSED static inline valtype* \ - prefix##get(maptype *map, const char *key) \ - { \ - return (valtype*)digestmap_get((digestmap_t*)map, key); \ - } \ - ATTR_UNUSED static inline valtype* \ - prefix##set(maptype *map, const char *key, valtype *val) \ - { \ - return (valtype*)digestmap_set((digestmap_t*)map, key, val); \ - } \ - ATTR_UNUSED static inline valtype* \ - prefix##remove(maptype *map, const char *key) \ - { \ - return (valtype*)digestmap_remove((digestmap_t*)map, key); \ - } \ - ATTR_UNUSED static inline void \ - prefix##f##ree_(maptype *map, void (*free_val)(void*)) \ - { \ - digestmap_free_((digestmap_t*)map, free_val); \ - } \ - ATTR_UNUSED static inline int \ - prefix##isempty(maptype *map) \ - { \ - return digestmap_isempty((digestmap_t*)map); \ - } \ - ATTR_UNUSED static inline int \ - prefix##size(maptype *map) \ - { \ - return digestmap_size((digestmap_t*)map); \ - } \ - ATTR_UNUSED static inline \ - prefix##iter_t *prefix##iter_init(maptype *map) \ - { \ - return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \ - } \ - ATTR_UNUSED 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); \ - } \ - ATTR_UNUSED 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); \ - } \ - ATTR_UNUSED 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; \ - } \ - ATTR_UNUSED 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 /* SIZEOF_INT == 4 || ... */ -#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 tor_calloc(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 = tor_reallocarray(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) -{ - tor_free(ba); -} -#define bitarray_free(ba) FREE_AND_NULL(bitarray_t, bitarray_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 uint64_t x = siphash24g(digest, 20); - const uint32_t d1 = (uint32_t) x; - const uint32_t d2 = (uint32_t)( (x>>16) + x); - const uint32_t d3 = (uint32_t)( (x>>32) + x); - const uint32_t d4 = (uint32_t)( (x>>48) + x); - 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_contains(const digestset_t *set, const char *digest) -{ - const uint64_t x = siphash24g(digest, 20); - const uint32_t d1 = (uint32_t) x; - const uint32_t d2 = (uint32_t)( (x>>16) + x); - const uint32_t d3 = (uint32_t)( (x>>32) + x); - const uint32_t d4 = (uint32_t)( (x>>48) + x); - 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); -#define digestset_free(set) FREE_AND_NULL(digestset_t, digestset_free_, (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 uint32_t -third_quartile_uint32(uint32_t *array, int n_elements) -{ - return find_nth_uint32(array, n_elements, (n_elements*3)/4); -} +#include "lib/container/smartlist.h" +#include "lib/container/map.h" +#include "lib/container/bitarray.h" +#include "lib/container/bloomfilt.h" +#include "lib/container/order.h" #endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/include.am b/src/lib/container/include.am index d7648c80c..e2994674a 100644 --- a/src/lib/container/include.am +++ b/src/lib/container/include.am @@ -6,7 +6,10 @@ noinst_LIBRARIES += src/lib/libtor-container-testing.a endif src_lib_libtor_container_a_SOURCES = \ - src/lib/container/container.c + src/lib/container/bloomfilt.c \ + src/lib/container/map.c \ + src/lib/container/order.c \ + src/lib/container/smartlist.c src_lib_libtor_container_testing_a_SOURCES = \ $(src_lib_libtor_container_a_SOURCES) @@ -14,4 +17,9 @@ src_lib_libtor_container_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) src_lib_libtor_container_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) noinst_HEADERS += \ - src/lib/container/container.h + src/lib/container/bitarray.h \ + src/lib/container/bloomfilt.h \ + src/lib/container/container.h \ + src/lib/container/map.h \ + src/lib/container/order.h \ + src/lib/container/smartlist.h diff --git a/src/lib/container/map.c b/src/lib/container/map.c new file mode 100644 index 000000000..227fb8f5e --- /dev/null +++ b/src/lib/container/map.c @@ -0,0 +1,413 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, 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 "lib/container/map.h" +#include "lib/ctime/di_ops.h" +#include "lib/crypt_ops/crypto_digest.h" + +#include "common/util_bug.h" +#include "common/util.h" // For strlower + +#include <stdlib.h> +#include <string.h> + +#include "ht.h" + +/** 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[DIGEST_LEN], digestmap_); +DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_); + +/** 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 (unsigned) siphash24g(a->key, strlen(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 tor_memeq(a->key, b->key, DIGEST_LEN); +} + +/** Helper: return a hash value for a digest_map_t. */ +static inline unsigned int +digestmap_entry_hash(const digestmap_entry_t *a) +{ + return (unsigned) siphash24g(a->key, DIGEST_LEN); +} + +/** Helper: compare digestmap_entry_t objects by key value. */ +static inline int +digest256map_entries_eq(const digest256map_entry_t *a, + const digest256map_entry_t *b) +{ + return tor_memeq(a->key, b->key, DIGEST256_LEN); +} + +/** Helper: return a hash value for a digest_map_t. */ +static inline unsigned int +digest256map_entry_hash(const digest256map_entry_t *a) +{ + return (unsigned) siphash24g(a->key, DIGEST256_LEN); +} + +HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq) +HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) + +HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq) +HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) + +HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node, + digest256map_entry_hash, + digest256map_entries_eq) +HT_GENERATE2(digest256map_impl, digest256map_entry_t, node, + digest256map_entry_hash, + digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_) + +#define strmap_entry_free(ent) \ + FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent)) +#define digestmap_entry_free(ent) \ + FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent)) +#define digest256map_entry_free(ent) \ + FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent)) + +static inline void +strmap_entry_free_(strmap_entry_t *ent) +{ + tor_free(ent->key); + tor_free(ent); +} +static inline void +digestmap_entry_free_(digestmap_entry_t *ent) +{ + tor_free(ent); +} +static inline void +digest256map_entry_free_(digest256map_entry_t *ent) +{ + tor_free(ent); +} + +static inline void +strmap_assign_tmp_key(strmap_entry_t *ent, const char *key) +{ + ent->key = (char*)key; +} +static inline void +digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key) +{ + memcpy(ent->key, key, DIGEST_LEN); +} +static inline void +digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key) +{ + memcpy(ent->key, key, DIGEST256_LEN); +} +static inline void +strmap_assign_key(strmap_entry_t *ent, const char *key) +{ + ent->key = tor_strdup(key); +} +static inline void +digestmap_assign_key(digestmap_entry_t *ent, const char *key) +{ + memcpy(ent->key, key, DIGEST_LEN); +} +static inline void +digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key) +{ + memcpy(ent->key, key, DIGEST256_LEN); +} + +/** + * Macro: implement all the functions for a map that are declared in + * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a + * prefix_entry_free_() function to free entries (and their keys), a + * prefix_assign_tmp_key() function to temporarily set a stack-allocated + * entry to hold a key, and a prefix_assign_key() function to set a + * heap-allocated entry to hold a key. + */ +#define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \ + /** Create and return a new empty map. */ \ + MOCK_IMPL(maptype *, \ + prefix##_new,(void)) \ + { \ + maptype *result; \ + result = tor_malloc(sizeof(maptype)); \ + HT_INIT(prefix##_impl, &result->head); \ + return result; \ + } \ + \ + /** Return the item from map whose key matches key, or \ + * NULL if no such value exists. */ \ + void * \ + prefix##_get(const maptype *map, const keytype key) \ + { \ + prefix ##_entry_t *resolve; \ + prefix ##_entry_t search; \ + tor_assert(map); \ + tor_assert(key); \ + prefix ##_assign_tmp_key(&search, key); \ + resolve = HT_FIND(prefix ##_impl, &map->head, &search); \ + if (resolve) { \ + return resolve->val; \ + } else { \ + return NULL; \ + } \ + } \ + \ + /** Add an entry to map mapping key to val; \ + * return the previous value, or NULL if no such value existed. */ \ + void * \ + prefix##_set(maptype *map, const keytype key, void *val) \ + { \ + prefix##_entry_t search; \ + void *oldval; \ + tor_assert(map); \ + tor_assert(key); \ + tor_assert(val); \ + prefix##_assign_tmp_key(&search, key); \ + /* We a lot 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 would do in the unoptimized */ \ + /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \ + /* HT_SET_HASH and HT_FIND_P.) */ \ + HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \ + &(map->head), \ + prefix##_entry_t, &search, ptr, \ + { \ + /* we found an entry. */ \ + oldval = (*ptr)->val; \ + (*ptr)->val = val; \ + return oldval; \ + }, \ + { \ + /* We didn't find the entry. */ \ + prefix##_entry_t *newent = \ + tor_malloc_zero(sizeof(prefix##_entry_t)); \ + prefix##_assign_key(newent, key); \ + newent->val = val; \ + HT_FOI_INSERT_(node, &(map->head), \ + &search, newent, ptr); \ + 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 * \ + prefix##_remove(maptype *map, const keytype key) \ + { \ + prefix##_entry_t *resolve; \ + prefix##_entry_t search; \ + void *oldval; \ + tor_assert(map); \ + tor_assert(key); \ + prefix##_assign_tmp_key(&search, key); \ + resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \ + if (resolve) { \ + oldval = resolve->val; \ + prefix##_entry_free(resolve); \ + return oldval; \ + } else { \ + return NULL; \ + } \ + } \ + \ + /** Return the number of elements in map. */ \ + int \ + prefix##_size(const maptype *map) \ + { \ + return HT_SIZE(&map->head); \ + } \ + \ + /** Return true iff map has no entries. */ \ + int \ + prefix##_isempty(const maptype *map) \ + { \ + return HT_EMPTY(&map->head); \ + } \ + \ + /** Assert that map is not corrupt. */ \ + void \ + prefix##_assert_ok(const maptype *map) \ + { \ + tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \ + } \ + \ + /** Remove all entries from map, and deallocate storage for \ + * those entries. If free_val is provided, invoked it every value in \ + * map. */ \ + MOCK_IMPL(void, \ + prefix##_free_, (maptype *map, void (*free_val)(void*))) \ + { \ + prefix##_entry_t **ent, **next, *this; \ + if (!map) \ + return; \ + for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \ + ent = next) { \ + this = *ent; \ + next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \ + if (free_val) \ + free_val(this->val); \ + prefix##_entry_free(this); \ + } \ + tor_assert(HT_EMPTY(&map->head)); \ + HT_CLEAR(prefix##_impl, &map->head); \ + tor_free(map); \ + } \ + \ + /** 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); \ + */ \ + prefix##_iter_t * \ + prefix##_iter_init(maptype *map) \ + { \ + tor_assert(map); \ + return HT_START(prefix##_impl, &map->head); \ + } \ + \ + /** Advance iter a single step to the next entry, and return \ + * its new value. */ \ + prefix##_iter_t * \ + prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \ + { \ + tor_assert(map); \ + tor_assert(iter); \ + return HT_NEXT(prefix##_impl, &map->head, iter); \ + } \ + /** Advance iter a single step to the next entry, removing the \ + * current entry, and return its new value. */ \ + prefix##_iter_t * \ + prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \ + { \ + prefix##_entry_t *rmv; \ + tor_assert(map); \ + tor_assert(iter); \ + tor_assert(*iter); \ + rmv = *iter; \ + iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \ + prefix##_entry_free(rmv); \ + return iter; \ + } \ + /** Set *keyp and *valp to the current entry pointed \ + * to by iter. */ \ + void \ + prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \ + void **valp) \ + { \ + tor_assert(iter); \ + tor_assert(*iter); \ + tor_assert(keyp); \ + tor_assert(valp); \ + *keyp = (*iter)->key; \ + *valp = (*iter)->val; \ + } \ + /** Return true iff iter has advanced past the last entry of \ + * map. */ \ + int \ + prefix##_iter_done(prefix##_iter_t *iter) \ + { \ + return iter == NULL; \ + } + +IMPLEMENT_MAP_FNS(strmap_t, char *, strmap) +IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap) +IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map) + +/** 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 = tor_strdup(key); + tor_strlower(lc_key); + v = strmap_set(map,lc_key,val); + tor_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 = tor_strdup(key); + tor_strlower(lc_key); + v = strmap_get(map,lc_key); + tor_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 = tor_strdup(key); + tor_strlower(lc_key); + v = strmap_remove(map,lc_key); + tor_free(lc_key); + return v; +} diff --git a/src/lib/container/map.h b/src/lib/container/map.h new file mode 100644 index 000000000..ac21c2871 --- /dev/null +++ b/src/lib/container/map.h @@ -0,0 +1,255 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_MAP_H +#define TOR_MAP_H + +#include "lib/testsupport/testsupport.h" +#include "lib/cc/torint.h" + +#include "siphash.h" + +#define DECLARE_MAP_FNS(maptype, keytype, prefix) \ + typedef struct maptype maptype; \ + typedef struct prefix##entry_t *prefix##iter_t; \ + MOCK_DECL(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); \ + MOCK_DECL(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_); +/* Map from const uint8_t[DIGEST256_LEN] to void *. Implemented with a hash + * table. */ +DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_); + +#define MAP_FREE_AND_NULL(maptype, map, fn) \ + do { \ + maptype ## _free_((map), (fn)); \ + (map) = NULL; \ + } while (0) + +#define strmap_free(map, fn) MAP_FREE_AND_NULL(strmap, (map), (fn)) +#define digestmap_free(map, fn) MAP_FREE_AND_NULL(digestmap, (map), (fn)) +#define digest256map_free(map, fn) MAP_FREE_AND_NULL(digest256map, (map), (fn)) + +#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) \ + STMT_BEGIN \ + 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) \ + STMT_BEGIN \ + 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) \ + STMT_BEGIN \ + keyvar##_del = 1; \ + STMT_END + +/** Used to end a MAP_FOREACH() block. */ +#define MAP_FOREACH_END } STMT_END ; + +/** 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 DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(digest256map_, map, const uint8_t *, keyvar, valtype, valvar) +#define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(digest256map_, map, const uint8_t *, \ + keyvar, valtype, valvar) +#define DIGEST256MAP_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; \ + ATTR_UNUSED static inline maptype* \ + prefix##new(void) \ + { \ + return (maptype*)digestmap_new(); \ + } \ + ATTR_UNUSED static inline digestmap_t* \ + prefix##to_digestmap(maptype *map) \ + { \ + return (digestmap_t*)map; \ + } \ + ATTR_UNUSED static inline valtype* \ + prefix##get(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_get((digestmap_t*)map, key); \ + } \ + ATTR_UNUSED static inline valtype* \ + prefix##set(maptype *map, const char *key, valtype *val) \ + { \ + return (valtype*)digestmap_set((digestmap_t*)map, key, val); \ + } \ + ATTR_UNUSED static inline valtype* \ + prefix##remove(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_remove((digestmap_t*)map, key); \ + } \ + ATTR_UNUSED static inline void \ + prefix##f##ree_(maptype *map, void (*free_val)(void*)) \ + { \ + digestmap_free_((digestmap_t*)map, free_val); \ + } \ + ATTR_UNUSED static inline int \ + prefix##isempty(maptype *map) \ + { \ + return digestmap_isempty((digestmap_t*)map); \ + } \ + ATTR_UNUSED static inline int \ + prefix##size(maptype *map) \ + { \ + return digestmap_size((digestmap_t*)map); \ + } \ + ATTR_UNUSED static inline \ + prefix##iter_t *prefix##iter_init(maptype *map) \ + { \ + return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \ + } \ + ATTR_UNUSED 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); \ + } \ + ATTR_UNUSED 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); \ + } \ + ATTR_UNUSED 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; \ + } \ + ATTR_UNUSED static inline int \ + prefix##iter_done(prefix##iter_t *iter) \ + { \ + return digestmap_iter_done((digestmap_iter_t*)iter); \ + } + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/order.c b/src/lib/container/order.c new file mode 100644 index 000000000..599f83300 --- /dev/null +++ b/src/lib/container/order.c @@ -0,0 +1,51 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, 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 <stdlib.h> + +#include "lib/container/order.h" +#include "common/util_bug.h" + +/** 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) \ + { \ + tor_assert(nth >= 0); \ + tor_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) diff --git a/src/lib/container/order.h b/src/lib/container/order.h new file mode 100644 index 000000000..bd23750d5 --- /dev/null +++ b/src/lib/container/order.h @@ -0,0 +1,54 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_ORDER_H +#define TOR_ORDER_H + +#include "lib/cc/compat_compiler.h" +#include "lib/cc/torint.h" + +/* 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 uint32_t +third_quartile_uint32(uint32_t *array, int n_elements) +{ + return find_nth_uint32(array, n_elements, (n_elements*3)/4); +} + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/container.c b/src/lib/container/smartlist.c similarity index 56% rename from src/lib/container/container.c rename to src/lib/container/smartlist.c index d31044fe2..6aef72854 100644 --- a/src/lib/container/container.c +++ b/src/lib/container/smartlist.c @@ -11,15 +11,15 @@ * a digest-to-void* map. **/ +#include "lib/malloc/util_malloc.h" +#include "lib/container/smartlist.h" #include "common/util.h" -#include "lib/container/container.h" #include "lib/crypt_ops/crypto_digest.h" +#include "lib/ctime/di_ops.h" #include <stdlib.h> #include <string.h> -#include "ht.h" - /** All newly allocated smartlists have this capacity. */ #define SMARTLIST_DEFAULT_CAPACITY 16 @@ -1092,458 +1092,3 @@ smartlist_uniq_digests256(smartlist_t *sl) { smartlist_uniq(sl, compare_digests256_, tor_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[DIGEST_LEN], digestmap_); -DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_); - -/** 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 (unsigned) siphash24g(a->key, strlen(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 tor_memeq(a->key, b->key, DIGEST_LEN); -} - -/** Helper: return a hash value for a digest_map_t. */ -static inline unsigned int -digestmap_entry_hash(const digestmap_entry_t *a) -{ - return (unsigned) siphash24g(a->key, DIGEST_LEN); -} - -/** Helper: compare digestmap_entry_t objects by key value. */ -static inline int -digest256map_entries_eq(const digest256map_entry_t *a, - const digest256map_entry_t *b) -{ - return tor_memeq(a->key, b->key, DIGEST256_LEN); -} - -/** Helper: return a hash value for a digest_map_t. */ -static inline unsigned int -digest256map_entry_hash(const digest256map_entry_t *a) -{ - return (unsigned) siphash24g(a->key, DIGEST256_LEN); -} - -HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, - strmap_entries_eq) -HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash, - strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) - -HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, - digestmap_entries_eq) -HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, - digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) - -HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node, - digest256map_entry_hash, - digest256map_entries_eq) -HT_GENERATE2(digest256map_impl, digest256map_entry_t, node, - digest256map_entry_hash, - digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_) - -#define strmap_entry_free(ent) \ - FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent)) -#define digestmap_entry_free(ent) \ - FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent)) -#define digest256map_entry_free(ent) \ - FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent)) - -static inline void -strmap_entry_free_(strmap_entry_t *ent) -{ - tor_free(ent->key); - tor_free(ent); -} -static inline void -digestmap_entry_free_(digestmap_entry_t *ent) -{ - tor_free(ent); -} -static inline void -digest256map_entry_free_(digest256map_entry_t *ent) -{ - tor_free(ent); -} - -static inline void -strmap_assign_tmp_key(strmap_entry_t *ent, const char *key) -{ - ent->key = (char*)key; -} -static inline void -digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key) -{ - memcpy(ent->key, key, DIGEST_LEN); -} -static inline void -digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key) -{ - memcpy(ent->key, key, DIGEST256_LEN); -} -static inline void -strmap_assign_key(strmap_entry_t *ent, const char *key) -{ - ent->key = tor_strdup(key); -} -static inline void -digestmap_assign_key(digestmap_entry_t *ent, const char *key) -{ - memcpy(ent->key, key, DIGEST_LEN); -} -static inline void -digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key) -{ - memcpy(ent->key, key, DIGEST256_LEN); -} - -/** - * Macro: implement all the functions for a map that are declared in - * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a - * prefix_entry_free_() function to free entries (and their keys), a - * prefix_assign_tmp_key() function to temporarily set a stack-allocated - * entry to hold a key, and a prefix_assign_key() function to set a - * heap-allocated entry to hold a key. - */ -#define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \ - /** Create and return a new empty map. */ \ - MOCK_IMPL(maptype *, \ - prefix##_new,(void)) \ - { \ - maptype *result; \ - result = tor_malloc(sizeof(maptype)); \ - HT_INIT(prefix##_impl, &result->head); \ - return result; \ - } \ - \ - /** Return the item from map whose key matches key, or \ - * NULL if no such value exists. */ \ - void * \ - prefix##_get(const maptype *map, const keytype key) \ - { \ - prefix ##_entry_t *resolve; \ - prefix ##_entry_t search; \ - tor_assert(map); \ - tor_assert(key); \ - prefix ##_assign_tmp_key(&search, key); \ - resolve = HT_FIND(prefix ##_impl, &map->head, &search); \ - if (resolve) { \ - return resolve->val; \ - } else { \ - return NULL; \ - } \ - } \ - \ - /** Add an entry to map mapping key to val; \ - * return the previous value, or NULL if no such value existed. */ \ - void * \ - prefix##_set(maptype *map, const keytype key, void *val) \ - { \ - prefix##_entry_t search; \ - void *oldval; \ - tor_assert(map); \ - tor_assert(key); \ - tor_assert(val); \ - prefix##_assign_tmp_key(&search, key); \ - /* We a lot 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 would do in the unoptimized */ \ - /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \ - /* HT_SET_HASH and HT_FIND_P.) */ \ - HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \ - &(map->head), \ - prefix##_entry_t, &search, ptr, \ - { \ - /* we found an entry. */ \ - oldval = (*ptr)->val; \ - (*ptr)->val = val; \ - return oldval; \ - }, \ - { \ - /* We didn't find the entry. */ \ - prefix##_entry_t *newent = \ - tor_malloc_zero(sizeof(prefix##_entry_t)); \ - prefix##_assign_key(newent, key); \ - newent->val = val; \ - HT_FOI_INSERT_(node, &(map->head), \ - &search, newent, ptr); \ - 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 * \ - prefix##_remove(maptype *map, const keytype key) \ - { \ - prefix##_entry_t *resolve; \ - prefix##_entry_t search; \ - void *oldval; \ - tor_assert(map); \ - tor_assert(key); \ - prefix##_assign_tmp_key(&search, key); \ - resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \ - if (resolve) { \ - oldval = resolve->val; \ - prefix##_entry_free(resolve); \ - return oldval; \ - } else { \ - return NULL; \ - } \ - } \ - \ - /** Return the number of elements in map. */ \ - int \ - prefix##_size(const maptype *map) \ - { \ - return HT_SIZE(&map->head); \ - } \ - \ - /** Return true iff map has no entries. */ \ - int \ - prefix##_isempty(const maptype *map) \ - { \ - return HT_EMPTY(&map->head); \ - } \ - \ - /** Assert that map is not corrupt. */ \ - void \ - prefix##_assert_ok(const maptype *map) \ - { \ - tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \ - } \ - \ - /** Remove all entries from map, and deallocate storage for \ - * those entries. If free_val is provided, invoked it every value in \ - * map. */ \ - MOCK_IMPL(void, \ - prefix##_free_, (maptype *map, void (*free_val)(void*))) \ - { \ - prefix##_entry_t **ent, **next, *this; \ - if (!map) \ - return; \ - for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \ - ent = next) { \ - this = *ent; \ - next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \ - if (free_val) \ - free_val(this->val); \ - prefix##_entry_free(this); \ - } \ - tor_assert(HT_EMPTY(&map->head)); \ - HT_CLEAR(prefix##_impl, &map->head); \ - tor_free(map); \ - } \ - \ - /** 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); \ - */ \ - prefix##_iter_t * \ - prefix##_iter_init(maptype *map) \ - { \ - tor_assert(map); \ - return HT_START(prefix##_impl, &map->head); \ - } \ - \ - /** Advance iter a single step to the next entry, and return \ - * its new value. */ \ - prefix##_iter_t * \ - prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \ - { \ - tor_assert(map); \ - tor_assert(iter); \ - return HT_NEXT(prefix##_impl, &map->head, iter); \ - } \ - /** Advance iter a single step to the next entry, removing the \ - * current entry, and return its new value. */ \ - prefix##_iter_t * \ - prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \ - { \ - prefix##_entry_t *rmv; \ - tor_assert(map); \ - tor_assert(iter); \ - tor_assert(*iter); \ - rmv = *iter; \ - iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \ - prefix##_entry_free(rmv); \ - return iter; \ - } \ - /** Set *keyp and *valp to the current entry pointed \ - * to by iter. */ \ - void \ - prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \ - void **valp) \ - { \ - tor_assert(iter); \ - tor_assert(*iter); \ - tor_assert(keyp); \ - tor_assert(valp); \ - *keyp = (*iter)->key; \ - *valp = (*iter)->val; \ - } \ - /** Return true iff iter has advanced past the last entry of \ - * map. */ \ - int \ - prefix##_iter_done(prefix##_iter_t *iter) \ - { \ - return iter == NULL; \ - } - -IMPLEMENT_MAP_FNS(strmap_t, char *, strmap) -IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap) -IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map) - -/** 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 = tor_strdup(key); - tor_strlower(lc_key); - v = strmap_set(map,lc_key,val); - tor_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 = tor_strdup(key); - tor_strlower(lc_key); - v = strmap_get(map,lc_key); - tor_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 = tor_strdup(key); - tor_strlower(lc_key); - v = strmap_remove(map,lc_key); - tor_free(lc_key); - return v; -} - -/** 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) \ - { \ - tor_assert(nth >= 0); \ - tor_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 << (tor_log2(max_elements)+5); - digestset_t *r = tor_malloc(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); - tor_free(set); -} diff --git a/src/lib/container/smartlist.h b/src/lib/container/smartlist.h new file mode 100644 index 000000000..7b80a9fed --- /dev/null +++ b/src/lib/container/smartlist.h @@ -0,0 +1,351 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_SMARTLIST_H +#define TOR_SMARTLIST_H + +#include <stddef.h> +#include "lib/cc/compat_compiler.h" +#include "common/util_bug.h" +#include "lib/testsupport/testsupport.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; + +MOCK_DECL(smartlist_t *, smartlist_new, (void)); +MOCK_DECL(void, smartlist_free_, (smartlist_t *sl)); +#define smartlist_free(sl) FREE_AND_NULL(smartlist_t, smartlist_free_, (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_add_strdup(struct smartlist_t *sl, const char *string); +void smartlist_remove(smartlist_t *sl, const void *element); +void smartlist_remove_keeporder(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_contains(const smartlist_t *sl, const void *element); +int smartlist_contains_string(const smartlist_t *sl, const char *element); +int smartlist_pos(const smartlist_t *sl, const void *element); +int smartlist_string_pos(const smartlist_t *, const char *elt); +int smartlist_contains_string_case(const smartlist_t *sl, const char *element); +int smartlist_contains_int_as_string(const smartlist_t *sl, int num); +int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2); +int smartlist_contains_digest(const smartlist_t *sl, const char *element); +int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2); +int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2); +void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2); +void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2); + +/* smartlist_choose() is defined in crypto.[ch] */ +#ifdef DEBUG_SMARTLIST +/** Return the number of items in sl. + */ +static inline int smartlist_len(const smartlist_t *sl); +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); +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 /* !(defined(DEBUG_SMARTLIST)) */ +#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 /* defined(DEBUG_SMARTLIST) */ + +/** 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), + int *count_out); +#define smartlist_get_most_frequent(sl, compare) \ + smartlist_get_most_frequent_((sl), (compare), NULL) +void smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *elt)); + +void smartlist_sort_strings(smartlist_t *sl); +void smartlist_sort_digests(smartlist_t *sl); +void smartlist_sort_digests256(smartlist_t *sl); +void smartlist_sort_pointers(smartlist_t *sl); + +const char *smartlist_get_most_frequent_string(smartlist_t *sl); +const char *smartlist_get_most_frequent_string_(smartlist_t *sl, + int *count_out); +const uint8_t *smartlist_get_most_frequent_digest256(smartlist_t *sl); + +void smartlist_uniq_strings(smartlist_t *sl); +void smartlist_uniq_digests(smartlist_t *sl); +void smartlist_uniq_digests256(smartlist_t *sl); +void *smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)); +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 statements inside the loop body. 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_BEGIN(list, char *, cp) { + * printf("%d: %s\n", cp_sl_idx, cp); + * tor_free(cp); + * } SMARTLIST_FOREACH_END(cp); + * smartlist_free(list); + * </pre> + * + * Example use (advanced): + * <pre> + * SMARTLIST_FOREACH_BEGIN(list, char *, cp) { + * if (!strcmp(cp, "junk")) { + * tor_free(cp); + * SMARTLIST_DEL_CURRENT(list, cp); + * } + * } SMARTLIST_FOREACH_END(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); + * tor_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")) { + * tor_free(cp); + * smartlist_del(list, cp_sl_idx); + * --cp_sl_idx; + * --cp_sl_len; + * } + * } + * } + * </pre> + */ +#define SMARTLIST_FOREACH_BEGIN(sl, type, var) \ + STMT_BEGIN \ + 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; \ + (void) var ## _sl_idx; \ + } STMT_END + +/** + * An alias for SMARTLIST_FOREACH_BEGIN and SMARTLIST_FOREACH_END, using + * cmd as the loop body. This wrapper is here for convenience with + * very short loops. + * + * By convention, we do not use this for loops which nest, or for loops over + * 10 lines or so. Use SMARTLIST_FOREACH_{BEGIN,END} for those. + */ +#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) \ + STMT_BEGIN \ + smartlist_del(sl, var ## _sl_idx); \ + --var ## _sl_idx; \ + --var ## _sl_len; \ + STMT_END + +/** 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_KEEPORDER(sl, var) \ + STMT_BEGIN \ + smartlist_del_keeporder(sl, var ## _sl_idx); \ + --var ## _sl_idx; \ + --var ## _sl_len; \ + STMT_END + +/** 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) \ + STMT_BEGIN \ + smartlist_set(sl, var ## _sl_idx, val); \ + STMT_END + +/* 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, + * tor_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 = tor_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) \ + STMT_BEGIN \ + 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) \ + } \ + STMT_END + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/malloc/util_malloc.c b/src/lib/malloc/util_malloc.c index 4a0b3a933..f3b0e50c7 100644 --- a/src/lib/malloc/util_malloc.c +++ b/src/lib/malloc/util_malloc.c @@ -12,7 +12,6 @@ #include "orconfig.h" #include <stdlib.h> -#include <stddef.h> #include <string.h> #include "lib/testsupport/testsupport.h" diff --git a/src/lib/malloc/util_malloc.h b/src/lib/malloc/util_malloc.h index 3da40351c..88ecc0453 100644 --- a/src/lib/malloc/util_malloc.h +++ b/src/lib/malloc/util_malloc.h @@ -11,6 +11,8 @@ #ifndef TOR_UTIL_MALLOC_H #define TOR_UTIL_MALLOC_H +#include <stddef.h> +#include <stdlib.h> #include "lib/cc/compat_compiler.h" /* Memory management */

1 0

[tor/master] Remove container->crypto dependency
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit 932b4d0a4342ec281b6f692f23453d6c46026c18 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 16:34:00 2018 -0400 Remove container->crypto dependency Containers were using crypto_digest.h, just to see the value of DIGEST_LEN. Moved those constants into a new defs module. --- src/include.am | 1 + src/lib/container/map.c | 2 +- src/lib/container/smartlist.c | 2 +- src/lib/crypt_ops/.may_include | 1 + src/lib/crypt_ops/crypto_digest.c | 1 - src/lib/crypt_ops/crypto_digest.h | 10 +--------- src/lib/defs/.may_include | 1 + src/lib/defs/digest_sizes.h | 18 ++++++++++++++++++ src/lib/defs/include.am | 3 +++ 9 files changed, 27 insertions(+), 12 deletions(-) diff --git a/src/include.am b/src/include.am index 9fa901c41..581fd69c7 100644 --- a/src/include.am +++ b/src/include.am @@ -5,6 +5,7 @@ include src/lib/ctime/include.am include src/lib/compress/include.am include src/lib/container/include.am include src/lib/crypt_ops/include.am +include src/lib/defs/include.am include src/lib/include.libdonna.am include src/lib/malloc/include.am include src/lib/testsupport/include.am diff --git a/src/lib/container/map.c b/src/lib/container/map.c index 227fb8f5e..508680e4a 100644 --- a/src/lib/container/map.c +++ b/src/lib/container/map.c @@ -13,7 +13,7 @@ #include "lib/container/map.h" #include "lib/ctime/di_ops.h" -#include "lib/crypt_ops/crypto_digest.h" +#include "lib/defs/digest_sizes.h" #include "common/util_bug.h" #include "common/util.h" // For strlower diff --git a/src/lib/container/smartlist.c b/src/lib/container/smartlist.c index 0fe11c670..2d861f566 100644 --- a/src/lib/container/smartlist.c +++ b/src/lib/container/smartlist.c @@ -15,7 +15,7 @@ #include "lib/container/smartlist.h" #include "lib/err/torerr.h" #include "common/util.h" // For strstrip. -#include "lib/crypt_ops/crypto_digest.h" +#include "lib/defs/digest_sizes.h" #include "lib/ctime/di_ops.h" #include <stdlib.h> diff --git a/src/lib/crypt_ops/.may_include b/src/lib/crypt_ops/.may_include index 6eefec158..4f415f876 100644 --- a/src/lib/crypt_ops/.may_include +++ b/src/lib/crypt_ops/.may_include @@ -2,6 +2,7 @@ orconfig.h lib/cc/*.h lib/crypt_ops/*.h lib/ctime/*.h +lib/defs/*.h lib/err/*.h lib/testsupport/testsupport.h diff --git a/src/lib/crypt_ops/crypto_digest.c b/src/lib/crypt_ops/crypto_digest.c index d746aaaca..b6ec2b284 100644 --- a/src/lib/crypt_ops/crypto_digest.c +++ b/src/lib/crypt_ops/crypto_digest.c @@ -580,4 +580,3 @@ crypto_xof_free_(crypto_xof_t *xof) memwipe(xof, 0, sizeof(crypto_xof_t)); tor_free(xof); } - diff --git a/src/lib/crypt_ops/crypto_digest.h b/src/lib/crypt_ops/crypto_digest.h index 129258245..63e8bec70 100644 --- a/src/lib/crypt_ops/crypto_digest.h +++ b/src/lib/crypt_ops/crypto_digest.h @@ -17,14 +17,7 @@ #include "lib/container/container.h" #include "lib/cc/torint.h" - -/** Length of the output of our message digest. */ -#define DIGEST_LEN 20 -/** Length of the output of our second (improved) message digests. (For now - * this is just sha256, but it could be any other 256-bit digest.) */ -#define DIGEST256_LEN 32 -/** Length of the output of our 64-bit optimized message digests (SHA512). */ -#define DIGEST512_LEN 64 +#include "lib/defs/digest_sizes.h" /** Length of a sha1 message digest when encoded in base32 with trailing = * signs removed. */ @@ -133,4 +126,3 @@ digest_algorithm_t crypto_digest_get_algorithm(crypto_digest_t *digest); #endif #endif /* !defined(TOR_CRYPTO_DIGEST_H) */ - diff --git a/src/lib/defs/.may_include b/src/lib/defs/.may_include new file mode 100644 index 000000000..2b06e8519 --- /dev/null +++ b/src/lib/defs/.may_include @@ -0,0 +1 @@ +orconfig.h diff --git a/src/lib/defs/digest_sizes.h b/src/lib/defs/digest_sizes.h new file mode 100644 index 000000000..f426fff20 --- /dev/null +++ b/src/lib/defs/digest_sizes.h @@ -0,0 +1,18 @@ +/* Copyright (c) 2001, Matej Pfajfar. + * Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_DIGEST_SIZES_H +#define TOR_DIGEST_SIZES_H + +/** Length of the output of our message digest. */ +#define DIGEST_LEN 20 +/** Length of the output of our second (improved) message digests. (For now + * this is just sha256, but it could be any other 256-bit digest.) */ +#define DIGEST256_LEN 32 +/** Length of the output of our 64-bit optimized message digests (SHA512). */ +#define DIGEST512_LEN 64 + +#endif diff --git a/src/lib/defs/include.am b/src/lib/defs/include.am new file mode 100644 index 000000000..861406c01 --- /dev/null +++ b/src/lib/defs/include.am @@ -0,0 +1,3 @@ + +noinst_HEADERS += \ + digest_sizes.h

1 0

[tor/master] Move STRUCT_VAR_P to compat_compiler.
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit 479c2ab503a3a051200339a7df9a99dcfb0ed976 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 16:29:24 2018 -0400 Move STRUCT_VAR_P to compat_compiler. --- src/common/util.h | 11 ----------- src/lib/cc/compat_compiler.h | 11 +++++++++++ src/lib/container/smartlist.c | 3 ++- 3 files changed, 13 insertions(+), 12 deletions(-) diff --git a/src/common/util.h b/src/common/util.h index 1c889082b..916bddc1f 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -41,17 +41,6 @@ uint64_t tor_ntohll(uint64_t a); void tor_log_mallinfo(int severity); -/** Macro: yield a pointer to the field at position off within the - * structure st. Example: - * <pre> - * struct a { int foo; int bar; } x; - * off_t bar_offset = offsetof(struct a, bar); - * int *bar_p = STRUCT_VAR_P(&x, bar_offset); - * *bar_p = 3; - * </pre> - */ -#define STRUCT_VAR_P(st, off) ((void*) ( ((char*)(st)) + (off) ) ) - /** Macro: yield a pointer to an enclosing structure given a pointer to * a substructure at offset off. Example: * <pre> diff --git a/src/lib/cc/compat_compiler.h b/src/lib/cc/compat_compiler.h index 31e84bcc5..763c3d06d 100644 --- a/src/lib/cc/compat_compiler.h +++ b/src/lib/cc/compat_compiler.h @@ -242,4 +242,15 @@ #error Unknown: SIZEOF_INTPTR_T #endif /* (SIZEOF_INTPTR_T == SIZEOF_INT) || ... */ +/** Macro: yield a pointer to the field at position off within the + * structure st. Example: + * <pre> + * struct a { int foo; int bar; } x; + * off_t bar_offset = offsetof(struct a, bar); + * int *bar_p = STRUCT_VAR_P(&x, bar_offset); + * *bar_p = 3; + * </pre> + */ +#define STRUCT_VAR_P(st, off) ((void*) ( ((char*)(st)) + (off) ) ) + #endif /* !defined(TOR_COMPAT_H) */ diff --git a/src/lib/container/smartlist.c b/src/lib/container/smartlist.c index 6aef72854..0fe11c670 100644 --- a/src/lib/container/smartlist.c +++ b/src/lib/container/smartlist.c @@ -13,7 +13,8 @@ #include "lib/malloc/util_malloc.h" #include "lib/container/smartlist.h" -#include "common/util.h" +#include "lib/err/torerr.h" +#include "common/util.h" // For strstrip. #include "lib/crypt_ops/crypto_digest.h" #include "lib/ctime/di_ops.h"

1 0

[tor/master] Remove bloom filters, order statistics, and bitarrays from container.h
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit 50a5954003a0478273d9e2c1a546e641e763a997 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 16:48:54 2018 -0400 Remove bloom filters, order statistics, and bitarrays from container.h --- src/common/address_set.c | 3 +-- src/common/util_bug.c | 1 + src/lib/container/container.h | 3 --- src/lib/crypt_ops/crypto_digest.h | 3 +-- src/lib/defs/include.am | 2 +- src/or/confparse.c | 4 ++-- src/or/consdiff.c | 1 - src/or/consdiff.h | 3 ++- src/or/dirauth/dirvote.c | 2 ++ src/or/dirserv.c | 3 ++- src/or/entrynodes.c | 3 ++- src/or/geoip.c | 3 ++- src/or/rephist.c | 4 +++- src/or/routerlist.c | 3 ++- src/or/routerparse.c | 3 ++- src/or/routerset.c | 3 +-- src/or/routerset.h | 3 ++- src/test/bench.c | 3 ++- src/test/test_circuitlist.c | 3 ++- src/test/test_containers.c | 5 ++++- src/test/test_entrynodes.c | 3 ++- 21 files changed, 36 insertions(+), 25 deletions(-) diff --git a/src/common/address_set.c b/src/common/address_set.c index d30343b1c..f4c5f581c 100644 --- a/src/common/address_set.c +++ b/src/common/address_set.c @@ -14,7 +14,7 @@ #include "common/address_set.h" #include "common/address.h" #include "common/compat.h" -#include "lib/container/container.h" +#include "lib/container/bitarray.h" #include "lib/crypt_ops/crypto_rand.h" #include "common/util.h" #include "siphash.h" @@ -126,4 +126,3 @@ address_set_probably_contains(address_set_t *set, } return matches == N_BITS_PER_ITEM; } - diff --git a/src/common/util_bug.c b/src/common/util_bug.c index 3b249bdfc..3d86131e7 100644 --- a/src/common/util_bug.c +++ b/src/common/util_bug.c @@ -12,6 +12,7 @@ #include "common/torlog.h" #include "lib/err/backtrace.h" #include "lib/container/container.h" +#include "lib/malloc/util_malloc.h" #ifdef __COVERITY__ int bug_macro_deadcode_dummy__ = 0; diff --git a/src/lib/container/container.h b/src/lib/container/container.h index ba8983846..1d0a47749 100644 --- a/src/lib/container/container.h +++ b/src/lib/container/container.h @@ -8,8 +8,5 @@ #include "lib/container/smartlist.h" #include "lib/container/map.h" -#include "lib/container/bitarray.h" -#include "lib/container/bloomfilt.h" -#include "lib/container/order.h" #endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/crypt_ops/crypto_digest.h b/src/lib/crypt_ops/crypto_digest.h index 63e8bec70..628224a03 100644 --- a/src/lib/crypt_ops/crypto_digest.h +++ b/src/lib/crypt_ops/crypto_digest.h @@ -13,11 +13,10 @@ #ifndef TOR_CRYPTO_DIGEST_H #define TOR_CRYPTO_DIGEST_H -#include <stdio.h> - #include "lib/container/container.h" #include "lib/cc/torint.h" #include "lib/defs/digest_sizes.h" +#include "lib/malloc/util_malloc.h" /** Length of a sha1 message digest when encoded in base32 with trailing = * signs removed. */ diff --git a/src/lib/defs/include.am b/src/lib/defs/include.am index 861406c01..ff48cff07 100644 --- a/src/lib/defs/include.am +++ b/src/lib/defs/include.am @@ -1,3 +1,3 @@ noinst_HEADERS += \ - digest_sizes.h + src/lib/defs/digest_sizes.h diff --git a/src/or/confparse.c b/src/or/confparse.c index e88c4f72d..b38e06c6a 100644 --- a/src/or/confparse.c +++ b/src/or/confparse.c @@ -1,4 +1,3 @@ - /* Copyright (c) 2001 Matej Pfajfar. * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. @@ -26,6 +25,8 @@ #include "or/confparse.h" #include "or/routerset.h" +#include "lib/container/bitarray.h" + static uint64_t config_parse_memunit(const char *s, int *ok); static int config_parse_msec_interval(const char *s, int *ok); static int config_parse_interval(const char *s, int *ok); @@ -1186,4 +1187,3 @@ config_parse_interval(const char *s, int *ok) } return (int)r; } - diff --git a/src/or/consdiff.c b/src/or/consdiff.c index 59e27c0ae..6d000997f 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -1412,4 +1412,3 @@ looks_like_a_consensus_diff(const char *document, size_t len) return (len >= strlen(ns_diff_version) && fast_memeq(document, ns_diff_version, strlen(ns_diff_version))); } - diff --git a/src/or/consdiff.h b/src/or/consdiff.h index 3f73b8536..1cae59a1a 100644 --- a/src/or/consdiff.h +++ b/src/or/consdiff.h @@ -15,6 +15,8 @@ char *consensus_diff_apply(const char *consensus, int looks_like_a_consensus_diff(const char *document, size_t len); #ifdef CONSDIFF_PRIVATE +#include "lib/container/bitarray.h" + struct memarea_t; /** Line type used for constructing consensus diffs. Each of these lines @@ -95,4 +97,3 @@ MOCK_DECL(STATIC int, #endif /* defined(CONSDIFF_PRIVATE) */ #endif /* !defined(TOR_CONSDIFF_H) */ - diff --git a/src/or/dirauth/dirvote.c b/src/or/dirauth/dirvote.c index 16439905a..85a0d3e70 100644 --- a/src/or/dirauth/dirvote.c +++ b/src/or/dirauth/dirvote.c @@ -43,6 +43,8 @@ #include "or/vote_routerstatus_st.h" #include "or/vote_timing_st.h" +#include "lib/container/order.h" + /** * \file dirvote.c * \brief Functions to compute directory consensus, and schedule voting. diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 077135841..655c13326 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -46,6 +46,8 @@ #include "or/tor_version_st.h" #include "or/vote_routerstatus_st.h" +#include "lib/container/order.h" + /** * \file dirserv.c * \brief Directory server core implementation. Manages directory @@ -3591,4 +3593,3 @@ dirserv_free_all(void) dirserv_clear_measured_bw_cache(); } - diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index 1fb621590..3c63d3c1c 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -142,6 +142,8 @@ #include "or/node_st.h" #include "or/origin_circuit_st.h" +#include "lib/container/bloomfilt.h" + /** A list of existing guard selection contexts. */ static smartlist_t *guard_contexts = NULL; /** The currently enabled guard selection context. */ @@ -3687,4 +3689,3 @@ entry_guards_free_all(void) } circuit_build_times_free_timeouts(get_circuit_build_times_mutable()); } - diff --git a/src/or/geoip.c b/src/or/geoip.c index 634ee707b..330477e4c 100644 --- a/src/or/geoip.c +++ b/src/or/geoip.c @@ -38,6 +38,8 @@ #include "or/geoip.h" #include "or/routerlist.h" +#include "lib/container/order.h" + static void init_geoip_countries(void); /** An entry from the GeoIP IPv4 file: maps an IPv4 range to a country. */ @@ -1884,4 +1886,3 @@ geoip_free_all(void) memset(geoip_digest, 0, sizeof(geoip_digest)); memset(geoip6_digest, 0, sizeof(geoip6_digest)); } - diff --git a/src/or/rephist.c b/src/or/rephist.c index a1cfc4932..2103eecdf 100644 --- a/src/or/rephist.c +++ b/src/or/rephist.c @@ -92,6 +92,9 @@ #include "or/networkstatus_st.h" #include "or/or_circuit_st.h" +#include "lib/container/bloomfilt.h" +#include "lib/container/order.h" + static void bw_arrays_init(void); static void predicted_ports_alloc(void); @@ -3208,4 +3211,3 @@ rep_hist_free_all(void) tor_assert_nonfatal(rephist_total_alloc == 0); tor_assert_nonfatal_once(rephist_total_num == 0); } - diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 97b3270f5..5af09fad2 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -137,6 +137,8 @@ #include "or/routerlist_st.h" #include "or/vote_routerstatus_st.h" +#include "lib/container/bloomfilt.h" + // #define DEBUG_ROUTERLIST /****************************************************************************/ @@ -5836,4 +5838,3 @@ refresh_all_country_info(void) nodelist_refresh_countries(); } - diff --git a/src/or/routerparse.c b/src/or/routerparse.c index a0426b96c..91475cd51 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -98,6 +98,8 @@ #include "or/vote_microdesc_hash_st.h" #include "or/vote_routerstatus_st.h" +#include "lib/container/bloomfilt.h" + #undef log #include <math.h> @@ -5684,4 +5686,3 @@ routerparse_free_all(void) { dump_desc_fifo_cleanup(); } - diff --git a/src/or/routerset.c b/src/or/routerset.c index 231ae152a..61b7dc121 100644 --- a/src/or/routerset.c +++ b/src/or/routerset.c @@ -1,5 +1,5 @@ /* Copyright (c) 2001 Matej Pfajfar. - * Copyright (c) 2001-2004, Roger Dingledine. +n * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. * Copyright (c) 2007-2018, The Tor Project, Inc. */ /* See LICENSE for licensing information */ @@ -460,4 +460,3 @@ routerset_free_(routerset_t *routerset) bitarray_free(routerset->countries); tor_free(routerset); } - diff --git a/src/or/routerset.h b/src/or/routerset.h index 5293c0ebf..8a13ca042 100644 --- a/src/or/routerset.h +++ b/src/or/routerset.h @@ -45,6 +45,8 @@ void routerset_free_(routerset_t *routerset); int routerset_len(const routerset_t *set); #ifdef ROUTERSET_PRIVATE +#include "lib/container/bitarray.h" + STATIC char * routerset_get_countryname(const char *c); STATIC int routerset_contains(const routerset_t *set, const tor_addr_t *addr, uint16_t orport, @@ -85,4 +87,3 @@ struct routerset_t { }; #endif /* defined(ROUTERSET_PRIVATE) */ #endif /* !defined(TOR_ROUTERSET_H) */ - diff --git a/src/test/bench.c b/src/test/bench.c index 49ac7269e..3cfdd0ae4 100644 --- a/src/test/bench.c +++ b/src/test/bench.c @@ -29,6 +29,8 @@ #include "or/cell_st.h" #include "or/or_circuit_st.h" +#include "lib/container/bloomfilt.h" + #if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_PROCESS_CPUTIME_ID) static uint64_t nanostart; static inline uint64_t @@ -741,4 +743,3 @@ main(int argc, const char **argv) return 0; } - diff --git a/src/test/test_circuitlist.c b/src/test/test_circuitlist.c index 96de2eed0..4aa7c596e 100644 --- a/src/test/test_circuitlist.c +++ b/src/test/test_circuitlist.c @@ -17,6 +17,8 @@ #include "or/or_circuit_st.h" #include "or/origin_circuit_st.h" +#include "lib/container/bitarray.h" + static channel_t * new_fake_channel(void) { @@ -470,4 +472,3 @@ struct testcase_t circuitlist_tests[] = { TT_FORK, NULL, NULL }, END_OF_TESTCASES }; - diff --git a/src/test/test_containers.c b/src/test/test_containers.c index efc6a181f..f45082be0 100644 --- a/src/test/test_containers.c +++ b/src/test/test_containers.c @@ -9,6 +9,10 @@ #include "or/fp_pair.h" #include "test/test.h" +#include "lib/container/bitarray.h" +#include "lib/container/bloomfilt.h" +#include "lib/container/order.h" + /** Helper: return a tristate based on comparing the strings in *a and * *b. */ static int @@ -1295,4 +1299,3 @@ struct testcase_t container_tests[] = { CONTAINER(smartlist_strings_eq, 0), END_OF_TESTCASES }; - diff --git a/src/test/test_entrynodes.c b/src/test/test_entrynodes.c index 2391e10cd..4d37d0fe8 100644 --- a/src/test/test_entrynodes.c +++ b/src/test/test_entrynodes.c @@ -43,6 +43,8 @@ #include "test/test_helpers.h" #include "test/log_test_helpers.h" +#include "lib/container/bloomfilt.h" + /* TODO: * choose_random_entry() test with state set. * @@ -3074,4 +3076,3 @@ struct testcase_t entrynodes_tests[] = { END_OF_TESTCASES }; -

1 0

[tor/master] Remove map from container.h
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit 9cf6fc91b1d0870dab8bf87feb9132e7e0de2808 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 16:52:58 2018 -0400 Remove map from container.h --- src/common/address.c | 2 +- src/common/sandbox.c | 4 +++- src/lib/container/container.h | 1 - src/lib/crypt_ops/.may_include | 2 ++ src/lib/crypt_ops/crypto.c | 2 ++ src/or/or.h | 3 ++- 6 files changed, 10 insertions(+), 4 deletions(-) diff --git a/src/common/address.c b/src/common/address.c index 27f8c4efe..f9e5cc5c7 100644 --- a/src/common/address.c +++ b/src/common/address.c @@ -42,6 +42,7 @@ #include "common/torlog.h" #include "lib/container/container.h" #include "common/sandbox.h" +#include "siphash.h" #ifdef HAVE_SYS_TIME_H #include <sys/time.h> @@ -2169,4 +2170,3 @@ tor_addr_port_eq(const tor_addr_port_t *a, { return tor_addr_eq(&a->addr, &b->addr) && a->port == b->port; } - diff --git a/src/common/sandbox.c b/src/common/sandbox.c index e67cedf0b..7e88ec9dd 100644 --- a/src/common/sandbox.c +++ b/src/common/sandbox.c @@ -33,7 +33,7 @@ #include <stdlib.h> #include "common/sandbox.h" -#include "lib/container/container.h" +#include "lib/container/map.h" #include "lib/err/torerr.h" #include "common/torlog.h" #include "lib/cc/torint.h" @@ -42,6 +42,8 @@ #include "ht.h" +#include "siphash.h" + #define DEBUGGING_CLOSE #if defined(USE_LIBSECCOMP) diff --git a/src/lib/container/container.h b/src/lib/container/container.h index 1d0a47749..6912ae31e 100644 --- a/src/lib/container/container.h +++ b/src/lib/container/container.h @@ -7,6 +7,5 @@ #define TOR_CONTAINER_H #include "lib/container/smartlist.h" -#include "lib/container/map.h" #endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/crypt_ops/.may_include b/src/lib/crypt_ops/.may_include index 4f415f876..94275c1d9 100644 --- a/src/lib/crypt_ops/.may_include +++ b/src/lib/crypt_ops/.may_include @@ -11,5 +11,7 @@ trunnel/pwbox.h keccak-tiny/*.h ed25519/*.h +siphash.h + # XXX I'd like to remove this. common/*.h diff --git a/src/lib/crypt_ops/crypto.c b/src/lib/crypt_ops/crypto.c index de7e271d3..9b1c38041 100644 --- a/src/lib/crypt_ops/crypto.c +++ b/src/lib/crypt_ops/crypto.c @@ -73,6 +73,8 @@ ENABLE_GCC_WARNING(redundant-decls) #include "keccak-tiny/keccak-tiny.h" +#include "siphash.h" + /** Boolean: has OpenSSL's crypto been initialized? */ static int crypto_early_initialized_ = 0; diff --git a/src/or/or.h b/src/or/or.h index c70123934..5c2a6d300 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -69,7 +69,8 @@ #include "lib/crypt_ops/crypto_hkdf.h" #include "lib/tls/tortls.h" #include "common/torlog.h" -#include "lib/container/container.h" +#include "lib/container/smartlist.h" +#include "lib/container/map.h" #include "lib/compress/compress.h" #include "common/address.h" #include "common/compat_libevent.h"

1 0

[tor/master] Expunge container.h
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit c2a558a346cf1f4db8751eb5c6dfecaab760a652 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 17:03:45 2018 -0400 Expunge container.h --- src/common/address.h | 1 - src/common/compat_time.c | 1 - src/common/compat_winthreads.c | 1 - src/common/memarea.c | 1 - src/lib/container/container.h | 9 --------- src/lib/container/include.am | 1 - src/lib/container/map.c | 2 +- src/lib/crypt_ops/crypto.c | 1 - src/lib/crypt_ops/crypto_curve25519.c | 1 - src/or/hs_client.c | 1 - src/or/hs_descriptor.h | 1 - src/test/test_bridges.c | 1 - src/test/test_dir_common.c | 1 - src/test/test_guardfraction.c | 1 - src/test/test_routerlist.c | 1 - 15 files changed, 1 insertion(+), 23 deletions(-) diff --git a/src/common/address.h b/src/common/address.h index 87f29fc28..8abff072c 100644 --- a/src/common/address.h +++ b/src/common/address.h @@ -15,7 +15,6 @@ #include "orconfig.h" #include "lib/cc/torint.h" #include "common/compat.h" -#include "lib/container/container.h" #include "common/util_bug.h" #ifdef ADDRESS_PRIVATE diff --git a/src/common/compat_time.c b/src/common/compat_time.c index 032c4e43a..4bb64f1e8 100644 --- a/src/common/compat_time.c +++ b/src/common/compat_time.c @@ -37,7 +37,6 @@ #include "lib/err/torerr.h" #include "common/torlog.h" #include "common/util.h" -#include "lib/container/container.h" #ifndef HAVE_GETTIMEOFDAY #ifdef HAVE_FTIME diff --git a/src/common/compat_winthreads.c b/src/common/compat_winthreads.c index eeb0b9751..807c7b4ae 100644 --- a/src/common/compat_winthreads.c +++ b/src/common/compat_winthreads.c @@ -16,7 +16,6 @@ #include <windows.h> #include <process.h> #include "common/util.h" -#include "lib/container/container.h" #include "common/torlog.h" /* This value is more or less total cargo-cult */ diff --git a/src/common/memarea.c b/src/common/memarea.c index ef6b78ecc..ec10f0222 100644 --- a/src/common/memarea.c +++ b/src/common/memarea.c @@ -13,7 +13,6 @@ #include "common/util.h" #include "common/compat.h" #include "common/torlog.h" -#include "lib/container/container.h" #ifndef DISABLE_MEMORY_SENTINELS diff --git a/src/lib/container/container.h b/src/lib/container/container.h deleted file mode 100644 index 3dc70e635..000000000 --- a/src/lib/container/container.h +++ /dev/null @@ -1,9 +0,0 @@ -/* Copyright (c) 2003-2004, Roger Dingledine - * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2018, The Tor Project, Inc. */ -/* See LICENSE for licensing information */ - -#ifndef TOR_CONTAINER_H -#define TOR_CONTAINER_H - -#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/include.am b/src/lib/container/include.am index e2994674a..0e7acdff9 100644 --- a/src/lib/container/include.am +++ b/src/lib/container/include.am @@ -19,7 +19,6 @@ src_lib_libtor_container_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) noinst_HEADERS += \ src/lib/container/bitarray.h \ src/lib/container/bloomfilt.h \ - src/lib/container/container.h \ src/lib/container/map.h \ src/lib/container/order.h \ src/lib/container/smartlist.h diff --git a/src/lib/container/map.c b/src/lib/container/map.c index 508680e4a..f6b0f73c1 100644 --- a/src/lib/container/map.c +++ b/src/lib/container/map.c @@ -158,7 +158,7 @@ digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key) /** * Macro: implement all the functions for a map that are declared in - * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a + * map.h by the DECLARE_MAP_FNS() macro. You must additionally define a * prefix_entry_free_() function to free entries (and their keys), a * prefix_assign_tmp_key() function to temporarily set a stack-allocated * entry to hold a key, and a prefix_assign_key() function to set a diff --git a/src/lib/crypt_ops/crypto.c b/src/lib/crypt_ops/crypto.c index 9b1c38041..46026b6ac 100644 --- a/src/lib/crypt_ops/crypto.c +++ b/src/lib/crypt_ops/crypto.c @@ -66,7 +66,6 @@ ENABLE_GCC_WARNING(redundant-decls) #include "lib/cc/torint.h" #include "lib/crypt_ops/aes.h" #include "common/util.h" -#include "lib/container/container.h" #include "common/compat.h" #include "common/sandbox.h" #include "common/util_format.h" diff --git a/src/lib/crypt_ops/crypto_curve25519.c b/src/lib/crypt_ops/crypto_curve25519.c index 1e7a45625..03225f1c1 100644 --- a/src/lib/crypt_ops/crypto_curve25519.c +++ b/src/lib/crypt_ops/crypto_curve25519.c @@ -20,7 +20,6 @@ #ifdef HAVE_SYS_STAT_H #include <sys/stat.h> #endif -#include "lib/container/container.h" #include "lib/crypt_ops/crypto_curve25519.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/crypt_ops/crypto_format.h" diff --git a/src/or/hs_client.c b/src/or/hs_client.c index a977fa44f..faccfae50 100644 --- a/src/or/hs_client.c +++ b/src/or/hs_client.c @@ -16,7 +16,6 @@ #include "or/config.h" #include "or/connection.h" #include "or/connection_edge.h" -#include "lib/container/container.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_util.h" #include "or/directory.h" diff --git a/src/or/hs_descriptor.h b/src/or/hs_descriptor.h index 640136f48..219b93444 100644 --- a/src/or/hs_descriptor.h +++ b/src/or/hs_descriptor.h @@ -13,7 +13,6 @@ #include "or/or.h" #include "common/address.h" -#include "lib/container/container.h" #include "lib/crypt_ops/crypto.h" #include "lib/crypt_ops/crypto_ed25519.h" #include "trunnel/ed25519_cert.h" /* needed for trunnel */ diff --git a/src/test/test_bridges.c b/src/test/test_bridges.c index 127b58762..747984140 100644 --- a/src/test/test_bridges.c +++ b/src/test/test_bridges.c @@ -15,7 +15,6 @@ #include "common/address.h" #include "or/bridges.h" #include "or/config.h" -#include "lib/container/container.h" #include "or/transports.h" #include "common/util.h" diff --git a/src/test/test_dir_common.c b/src/test/test_dir_common.c index 5212810b7..a758421cd 100644 --- a/src/test/test_dir_common.c +++ b/src/test/test_dir_common.c @@ -6,7 +6,6 @@ #include "orconfig.h" #define DIRVOTE_PRIVATE #include "test/test.h" -#include "lib/container/container.h" #include "or/or.h" #include "or/dirauth/dirvote.h" #include "or/nodelist.h" diff --git a/src/test/test_guardfraction.c b/src/test/test_guardfraction.c index 12e64d0e7..b7737cafa 100644 --- a/src/test/test_guardfraction.c +++ b/src/test/test_guardfraction.c @@ -9,7 +9,6 @@ #include "or/or.h" #include "or/config.h" #include "or/dirserv.h" -#include "lib/container/container.h" #include "or/entrynodes.h" #include "common/util.h" #include "or/routerparse.h" diff --git a/src/test/test_routerlist.c b/src/test/test_routerlist.c index 5011e2285..5da42c133 100644 --- a/src/test/test_routerlist.c +++ b/src/test/test_routerlist.c @@ -16,7 +16,6 @@ #include "or/or.h" #include "or/config.h" #include "or/connection.h" -#include "lib/container/container.h" #include "or/control.h" #include "lib/crypt_ops/crypto_rand.h" #include "or/directory.h"

1 0

[tor/master] Extract smartlist.h from container.h
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit de508c5f50af855742b59579afd6c9c328eb7cd6 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 17:00:48 2018 -0400 Extract smartlist.h from container.h --- src/common/address.c | 2 +- src/common/address.h | 23 ++++++++++++----------- src/common/compat.c | 3 +-- src/common/confline.c | 3 +-- src/common/confline.h | 5 ++--- src/common/log.c | 2 +- src/common/storagedir.c | 3 +-- src/common/util.c | 2 +- src/common/util_bug.c | 4 +++- src/lib/container/container.h | 2 -- src/lib/crypt_ops/crypto_digest.c | 2 +- src/lib/crypt_ops/crypto_digest.h | 3 ++- src/lib/crypt_ops/crypto_format.c | 3 +-- src/lib/crypt_ops/crypto_rand.c | 3 +-- src/lib/tls/tortls.c | 2 +- src/or/parsecommon.c | 2 +- src/or/parsecommon.h | 13 +++++++------ src/or/protover.h | 11 +++++------ 18 files changed, 42 insertions(+), 46 deletions(-) diff --git a/src/common/address.c b/src/common/address.c index f9e5cc5c7..f2cddd394 100644 --- a/src/common/address.c +++ b/src/common/address.c @@ -40,7 +40,7 @@ #include "common/util_format.h" #include "common/address.h" #include "common/torlog.h" -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "common/sandbox.h" #include "siphash.h" diff --git a/src/common/address.h b/src/common/address.h index b8fccd81e..87f29fc28 100644 --- a/src/common/address.h +++ b/src/common/address.h @@ -207,10 +207,11 @@ const char * fmt_addr32(uint32_t addr); MOCK_DECL(int,get_interface_address6,(int severity, sa_family_t family, tor_addr_t *addr)); -void interface_address6_list_free_(smartlist_t * addrs);// XXXX +struct smartlist_t; +void interface_address6_list_free_(struct smartlist_t * addrs);// XXXX #define interface_address6_list_free(addrs) \ - FREE_AND_NULL(smartlist_t, interface_address6_list_free_, (addrs)) -MOCK_DECL(smartlist_t *,get_interface_address6_list,(int severity, + FREE_AND_NULL(struct smartlist_t, interface_address6_list_free_, (addrs)) +MOCK_DECL(struct smartlist_t *,get_interface_address6_list,(int severity, sa_family_t family, int include_internal)); @@ -336,7 +337,7 @@ MOCK_DECL(int,get_interface_address,(int severity, uint32_t *addr)); * Returns NULL on failure. * Use free_interface_address_list to free the returned list. */ -static inline smartlist_t * +static inline struct smartlist_t * get_interface_address_list(int severity, int include_internal) { return get_interface_address6_list(severity, AF_INET, include_internal); @@ -347,30 +348,30 @@ int tor_addr_port_eq(const tor_addr_port_t *a, const tor_addr_port_t *b); #ifdef ADDRESS_PRIVATE -MOCK_DECL(smartlist_t *,get_interface_addresses_raw,(int severity, +MOCK_DECL(struct smartlist_t *,get_interface_addresses_raw,(int severity, sa_family_t family)); MOCK_DECL(int,get_interface_address6_via_udp_socket_hack,(int severity, sa_family_t family, tor_addr_t *addr)); #ifdef HAVE_IFADDRS_TO_SMARTLIST -STATIC smartlist_t *ifaddrs_to_smartlist(const struct ifaddrs *ifa, +STATIC struct smartlist_t *ifaddrs_to_smartlist(const struct ifaddrs *ifa, sa_family_t family); -STATIC smartlist_t *get_interface_addresses_ifaddrs(int severity, +STATIC struct smartlist_t *get_interface_addresses_ifaddrs(int severity, sa_family_t family); #endif /* defined(HAVE_IFADDRS_TO_SMARTLIST) */ #ifdef HAVE_IP_ADAPTER_TO_SMARTLIST -STATIC smartlist_t *ip_adapter_addresses_to_smartlist( +STATIC struct smartlist_t *ip_adapter_addresses_to_smartlist( const IP_ADAPTER_ADDRESSES *addresses); -STATIC smartlist_t *get_interface_addresses_win32(int severity, +STATIC struct smartlist_t *get_interface_addresses_win32(int severity, sa_family_t family); #endif /* defined(HAVE_IP_ADAPTER_TO_SMARTLIST) */ #ifdef HAVE_IFCONF_TO_SMARTLIST -STATIC smartlist_t *ifreq_to_smartlist(char *ifr, +STATIC struct smartlist_t *ifreq_to_smartlist(char *ifr, size_t buflen); -STATIC smartlist_t *get_interface_addresses_ioctl(int severity, +STATIC struct smartlist_t *get_interface_addresses_ioctl(int severity, sa_family_t family); #endif /* defined(HAVE_IFCONF_TO_SMARTLIST) */ diff --git a/src/common/compat.c b/src/common/compat.c index 577ebe757..9462195ba 100644 --- a/src/common/compat.c +++ b/src/common/compat.c @@ -126,7 +126,7 @@ SecureZeroMemory(PVOID ptr, SIZE_T cnt) #include "common/torlog.h" #include "common/util.h" -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "common/address.h" #include "common/sandbox.h" @@ -3527,4 +3527,3 @@ tor_get_avail_disk_space(const char *path) return -1; #endif /* defined(HAVE_STATVFS) || ... */ } - diff --git a/src/common/confline.c b/src/common/confline.c index 7343c5f52..76f5ac04e 100644 --- a/src/common/confline.c +++ b/src/common/confline.c @@ -8,7 +8,7 @@ #include "common/confline.h" #include "common/torlog.h" #include "common/util.h" -#include "lib/container/container.h" +#include "lib/container/smartlist.h" static int config_get_lines_aux(const char *string, config_line_t **result, int extended, int allow_include, @@ -535,4 +535,3 @@ parse_config_line_from_str_verbose(const char *line, char **key_out, return line; } - diff --git a/src/common/confline.h b/src/common/confline.h index 10af34a0a..d1f6fdb7e 100644 --- a/src/common/confline.h +++ b/src/common/confline.h @@ -7,7 +7,7 @@ #ifndef TOR_CONFLINE_H #define TOR_CONFLINE_H -#include "lib/container/container.h" +struct smartlist_t; /** Ordinary configuration line. */ #define CONFIG_LINE_NORMAL 0 @@ -47,7 +47,7 @@ int config_count_key(const config_line_t *a, const char *key); int config_get_lines(const char *string, config_line_t **result, int extended); int config_get_lines_include(const char *string, config_line_t **result, int extended, int *has_include, - smartlist_t *opened_lst); + struct smartlist_t *opened_lst); void config_free_lines_(config_line_t *front); #define config_free_lines(front) \ do { \ @@ -58,4 +58,3 @@ const char *parse_config_line_from_str_verbose(const char *line, char **key_out, char **value_out, const char **err_out); #endif /* !defined(TOR_CONFLINE_H) */ - diff --git a/src/common/log.c b/src/common/log.c index 8ea686a12..5224a2197 100644 --- a/src/common/log.c +++ b/src/common/log.c @@ -33,7 +33,7 @@ #include "common/util.h" #define LOG_PRIVATE #include "common/torlog.h" -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "lib/err/torerr.h" #ifdef HAVE_ANDROID_LOG_H diff --git a/src/common/storagedir.c b/src/common/storagedir.c index f3270ce7b..82a5e1b21 100644 --- a/src/common/storagedir.c +++ b/src/common/storagedir.c @@ -1,7 +1,7 @@ /* Copyright (c) 2017-2018, The Tor Project, Inc. */ /* See LICENSE for licensing information */ -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "common/compat.h" #include "common/confline.h" #include "common/memarea.h" @@ -583,4 +583,3 @@ storage_dir_get_max_files(storage_dir_t *d) { return d->max_files; } - diff --git a/src/common/util.c b/src/common/util.c index cd8ff93a3..877368af5 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -18,7 +18,7 @@ #include "common/torlog.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/cc/torint.h" -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "common/address.h" #include "common/sandbox.h" #include "lib/err/backtrace.h" diff --git a/src/common/util_bug.c b/src/common/util_bug.c index 3d86131e7..7d6dc0750 100644 --- a/src/common/util_bug.c +++ b/src/common/util_bug.c @@ -11,7 +11,9 @@ #include "common/util_bug.h" #include "common/torlog.h" #include "lib/err/backtrace.h" -#include "lib/container/container.h" +#ifdef TOR_UNIT_TESTS +#include "lib/container/smartlist.h" +#endif #include "lib/malloc/util_malloc.h" #ifdef __COVERITY__ diff --git a/src/lib/container/container.h b/src/lib/container/container.h index 6912ae31e..3dc70e635 100644 --- a/src/lib/container/container.h +++ b/src/lib/container/container.h @@ -6,6 +6,4 @@ #ifndef TOR_CONTAINER_H #define TOR_CONTAINER_H -#include "lib/container/smartlist.h" - #endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/crypt_ops/crypto_digest.c b/src/lib/crypt_ops/crypto_digest.c index b6ec2b284..b1aede3a8 100644 --- a/src/lib/crypt_ops/crypto_digest.c +++ b/src/lib/crypt_ops/crypto_digest.c @@ -10,7 +10,7 @@ * operations. **/ -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/crypt_ops/crypto_openssl_mgt.h" #include "lib/crypt_ops/crypto_util.h" diff --git a/src/lib/crypt_ops/crypto_digest.h b/src/lib/crypt_ops/crypto_digest.h index 628224a03..15bc5ad5b 100644 --- a/src/lib/crypt_ops/crypto_digest.h +++ b/src/lib/crypt_ops/crypto_digest.h @@ -13,7 +13,6 @@ #ifndef TOR_CRYPTO_DIGEST_H #define TOR_CRYPTO_DIGEST_H -#include "lib/container/container.h" #include "lib/cc/torint.h" #include "lib/defs/digest_sizes.h" #include "lib/malloc/util_malloc.h" @@ -70,6 +69,8 @@ typedef struct { typedef struct crypto_digest_t crypto_digest_t; typedef struct crypto_xof_t crypto_xof_t; +struct smartlist_t; + /* SHA-1 and other digests */ int crypto_digest(char *digest, const char *m, size_t len); int crypto_digest256(char *digest, const char *m, size_t len, diff --git a/src/lib/crypt_ops/crypto_format.c b/src/lib/crypt_ops/crypto_format.c index 246f28716..2d28090aa 100644 --- a/src/lib/crypt_ops/crypto_format.c +++ b/src/lib/crypt_ops/crypto_format.c @@ -14,7 +14,7 @@ #ifdef HAVE_SYS_STAT_H #include <sys/stat.h> #endif -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "lib/crypt_ops/crypto_curve25519.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/crypt_ops/crypto_ed25519.h" @@ -296,4 +296,3 @@ digest256_from_base64(char *digest, const char *d64) else return -1; } - diff --git a/src/lib/crypt_ops/crypto_rand.c b/src/lib/crypt_ops/crypto_rand.c index af258abea..0d41a207e 100644 --- a/src/lib/crypt_ops/crypto_rand.c +++ b/src/lib/crypt_ops/crypto_rand.c @@ -21,7 +21,7 @@ #include <wincrypt.h> #endif /* defined(_WIN32) */ -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include "common/compat.h" #include "lib/crypt_ops/compat_openssl.h" #include "lib/crypt_ops/crypto_util.h" @@ -612,4 +612,3 @@ crypto_force_rand_ssleay(void) } #endif /* !defined(CRYPTO_RAND_PRIVATE) */ - diff --git a/src/lib/tls/tortls.c b/src/lib/tls/tortls.c index ea3a42054..eb8a91b42 100644 --- a/src/lib/tls/tortls.c +++ b/src/lib/tls/tortls.c @@ -55,7 +55,7 @@ ENABLE_GCC_WARNING(redundant-decls) #include "lib/tls/tortls.h" #include "common/util.h" #include "common/torlog.h" -#include "lib/container/container.h" +#include "lib/container/smartlist.h" #include <string.h> #ifdef OPENSSL_1_1_API diff --git a/src/or/parsecommon.c b/src/or/parsecommon.c index 09c7d665f..298d3658b 100644 --- a/src/or/parsecommon.c +++ b/src/or/parsecommon.c @@ -9,6 +9,7 @@ #include "or/parsecommon.h" #include "common/torlog.h" #include "common/util_format.h" +#include "lib/container/smartlist.h" #define MIN_ANNOTATION A_PURPOSE #define MAX_ANNOTATION A_UNKNOWN_ @@ -448,4 +449,3 @@ find_all_by_keyword(const smartlist_t *s, directory_keyword k) }); return out; } - diff --git a/src/or/parsecommon.h b/src/or/parsecommon.h index c786bcc54..fc61c514a 100644 --- a/src/or/parsecommon.h +++ b/src/or/parsecommon.h @@ -9,10 +9,11 @@ #ifndef TOR_PARSECOMMON_H #define TOR_PARSECOMMON_H -#include "lib/container/container.h" #include "lib/crypt_ops/crypto.h" #include "common/memarea.h" +struct smartlist_t; + /** Enumeration of possible token types. The ones starting with K_ correspond * to directory 'keywords'. A_ is for an annotation, R or C is related to * hidden services, ERR_ is an error in the tokenizing process, EOF_ is an @@ -299,7 +300,7 @@ void token_clear(directory_token_t *tok); int tokenize_string(memarea_t *area, const char *start, const char *end, - smartlist_t *out, + struct smartlist_t *out, token_rule_t *table, int flags); directory_token_t *get_next_token(memarea_t *area, @@ -307,16 +308,16 @@ directory_token_t *get_next_token(memarea_t *area, const char *eos, token_rule_t *table); -directory_token_t *find_by_keyword_(smartlist_t *s, +directory_token_t *find_by_keyword_(struct smartlist_t *s, directory_keyword keyword, const char *keyword_str); #define find_by_keyword(s, keyword) \ find_by_keyword_((s), (keyword), #keyword) -directory_token_t *find_opt_by_keyword(const smartlist_t *s, +directory_token_t *find_opt_by_keyword(const struct smartlist_t *s, directory_keyword keyword); -smartlist_t * find_all_by_keyword(const smartlist_t *s, directory_keyword k); +struct smartlist_t * find_all_by_keyword(const struct smartlist_t *s, + directory_keyword k); #endif /* !defined(TOR_PARSECOMMON_H) */ - diff --git a/src/or/protover.h b/src/or/protover.h index 99502645c..aab311e96 100644 --- a/src/or/protover.h +++ b/src/or/protover.h @@ -9,7 +9,7 @@ #ifndef TOR_PROTOVER_H #define TOR_PROTOVER_H -#include "lib/container/container.h" +struct smartlist_t; /** The first version of Tor that included "proto" entries in its * descriptors. Authorities should use this to decide whether to @@ -47,7 +47,7 @@ int protover_all_supported(const char *s, char **missing); int protover_is_supported_here(protocol_type_t pr, uint32_t ver); const char *protover_get_supported_protocols(void); -char *protover_compute_vote(const smartlist_t *list_of_proto_strings, +char *protover_compute_vote(const struct smartlist_t *list_of_proto_strings, int threshold); const char *protover_compute_for_old_tor(const char *version); int protocol_list_supports_protocol(const char *list, protocol_type_t tp, @@ -75,12 +75,12 @@ typedef struct proto_entry_t { */ char *name; /** Smartlist of proto_range_t */ - smartlist_t *ranges; + struct smartlist_t *ranges; } proto_entry_t; #if !defined(HAVE_RUST) && defined(TOR_UNIT_TESTS) -STATIC smartlist_t *parse_protocol_list(const char *s); -STATIC char *encode_protocol_list(const smartlist_t *sl); +STATIC struct smartlist_t *parse_protocol_list(const char *s); +STATIC char *encode_protocol_list(const struct smartlist_t *sl); STATIC const char *protocol_type_to_str(protocol_type_t pr); STATIC int str_to_protocol_type(const char *s, protocol_type_t *pr_out); STATIC void proto_entry_free_(proto_entry_t *entry); @@ -92,4 +92,3 @@ STATIC void proto_entry_free_(proto_entry_t *entry); #endif /* defined(PROTOVER_PRIVATE) */ #endif /* !defined(TOR_PROTOVER_H) */ -

1 0

[tor/master] Extract our code for answering "what time is it right now".
by nickm＠torproject.org 26 Jun '18

26 Jun '18

commit 9426751b72e922b5ee2b00bcc6158f5651a81014 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jun 21 17:33:49 2018 -0400 Extract our code for answering "what time is it right now". The other time stuff is higher-level --- .gitignore | 2 + Makefile.am | 2 + src/common/compat_time.c | 53 ----------------------- src/common/compat_time.h | 5 +-- src/common/log.c | 2 + src/common/util.c | 31 -------------- src/common/util.h | 10 +---- src/include.am | 1 + src/lib/wallclock/.may_include | 4 ++ src/lib/wallclock/approx_time.c | 38 +++++++++++++++++ src/lib/wallclock/approx_time.h | 20 +++++++++ src/lib/wallclock/include.am | 19 +++++++++ src/lib/wallclock/tor_gettimeofday.c | 82 ++++++++++++++++++++++++++++++++++++ src/lib/wallclock/tor_gettimeofday.h | 15 +++++++ 14 files changed, 188 insertions(+), 96 deletions(-) diff --git a/.gitignore b/.gitignore index deb369381..343517fdf 100644 --- a/.gitignore +++ b/.gitignore @@ -178,6 +178,8 @@ uptime-*.json /src/lib/libtor-tls.a /src/lib/libtor-tls-testing.a /src/lib/libtor-trace.a +/src/lib/libtor-wallclock.a +/src/lib/libtor-wallclock-testing.a # /src/or/ /src/or/Makefile diff --git a/Makefile.am b/Makefile.am index 1b71e478f..a83041fbe 100644 --- a/Makefile.am +++ b/Makefile.am @@ -42,6 +42,7 @@ TOR_UTIL_LIBS = \ src/common/libor.a \ src/lib/libtor-container.a \ src/lib/libtor-malloc.a \ + src/lib/libtor-wallclock.a \ src/lib/libtor-err.a \ src/lib/libtor-ctime.a @@ -51,6 +52,7 @@ TOR_UTIL_TESTING_LIBS = \ src/common/libor-testing.a \ src/lib/libtor-container-testing.a \ src/lib/libtor-malloc-testing.a \ + src/lib/libtor-wallclock-testing.a \ src/lib/libtor-err-testing.a \ src/lib/libtor-ctime-testing.a diff --git a/src/common/compat_time.c b/src/common/compat_time.c index 4bb64f1e8..d3cbd02c6 100644 --- a/src/common/compat_time.c +++ b/src/common/compat_time.c @@ -38,12 +38,6 @@ #include "common/torlog.h" #include "common/util.h" -#ifndef HAVE_GETTIMEOFDAY -#ifdef HAVE_FTIME -#include <sys/timeb.h> -#endif -#endif - #ifdef _WIN32 #undef HAVE_CLOCK_GETTIME #endif @@ -68,53 +62,6 @@ tor_sleep_msec(int msec) } #endif /* defined(TOR_UNIT_TESTS) */ -/** Set *timeval to the current time of day. On error, log and terminate. - * (Same as gettimeofday(timeval,NULL), but never returns -1.) - */ -MOCK_IMPL(void, -tor_gettimeofday, (struct timeval *timeval)) -{ -#ifdef _WIN32 - /* Epoch bias copied from perl: number of units between windows epoch and - * Unix epoch. */ -#define EPOCH_BIAS U64_LITERAL(116444736000000000) -#define UNITS_PER_SEC U64_LITERAL(10000000) -#define USEC_PER_SEC U64_LITERAL(1000000) -#define UNITS_PER_USEC U64_LITERAL(10) - union { - uint64_t ft_64; - FILETIME ft_ft; - } ft; - /* number of 100-nsec units since Jan 1, 1601 */ - GetSystemTimeAsFileTime(&ft.ft_ft); - if (ft.ft_64 < EPOCH_BIAS) { - /* LCOV_EXCL_START */ - log_err(LD_GENERAL,"System time is before 1970; failing."); - exit(1); // exit ok: system clock is broken. - /* LCOV_EXCL_STOP */ - } - ft.ft_64 -= EPOCH_BIAS; - timeval->tv_sec = (unsigned) (ft.ft_64 / UNITS_PER_SEC); - timeval->tv_usec = (unsigned) ((ft.ft_64 / UNITS_PER_USEC) % USEC_PER_SEC); -#elif defined(HAVE_GETTIMEOFDAY) - if (gettimeofday(timeval, NULL)) { - /* LCOV_EXCL_START */ - /* If gettimeofday dies, we have either given a bad timezone (we didn't), - or segfaulted.*/ - raw_assert_unreached_msg("gettimeofday failed"); - /* LCOV_EXCL_STOP */ - } -#elif defined(HAVE_FTIME) - struct timeb tb; - ftime(&tb); - timeval->tv_sec = tb.time; - timeval->tv_usec = tb.millitm * 1000; -#else -#error "No way to get time." -#endif /* defined(_WIN32) || ... */ - return; -} - #define ONE_MILLION ((int64_t) (1000 * 1000)) #define ONE_BILLION ((int64_t) (1000 * 1000 * 1000)) diff --git a/src/common/compat_time.h b/src/common/compat_time.h index 71d94cb86..2f7e87a63 100644 --- a/src/common/compat_time.h +++ b/src/common/compat_time.h @@ -19,6 +19,8 @@ #define TOR_COMPAT_TIME_H #include "orconfig.h" +#include "lib/wallclock/tor_gettimeofday.h" + #ifdef _WIN32 #undef HAVE_CLOCK_GETTIME #endif @@ -200,8 +202,6 @@ monotime_coarse_diff_msec32(const monotime_coarse_t *start, #endif } -MOCK_DECL(void, tor_gettimeofday, (struct timeval *timeval)); - #ifdef TOR_UNIT_TESTS void tor_sleep_msec(int msec); @@ -230,4 +230,3 @@ void monotime_reset_ratchets_for_testing(void); #endif /* defined(COMPAT_TIME_PRIVATE) */ #endif /* !defined(TOR_COMPAT_TIME_H) */ - diff --git a/src/common/log.c b/src/common/log.c index 5224a2197..f452c7413 100644 --- a/src/common/log.c +++ b/src/common/log.c @@ -35,6 +35,8 @@ #include "common/torlog.h" #include "lib/container/smartlist.h" #include "lib/err/torerr.h" +#include "lib/wallclock/tor_gettimeofday.h" +#include "lib/wallclock/approx_time.h" #ifdef HAVE_ANDROID_LOG_H #include <android/log.h> diff --git a/src/common/util.c b/src/common/util.c index 877368af5..358a68fd7 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -1799,37 +1799,6 @@ format_time_interval(char *out, size_t out_len, long interval) } /* ===== - * Cached time - * ===== */ - -#ifndef TIME_IS_FAST -/** Cached estimate of the current time. Updated around once per second; - * may be a few seconds off if we are really busy. This is a hack to avoid - * calling time(NULL) (which not everybody has optimized) on critical paths. - */ -static time_t cached_approx_time = 0; - -/** Return a cached estimate of the current time from when - * update_approx_time() was last called. This is a hack to avoid calling - * time(NULL) on critical paths: please do not even think of calling it - * anywhere else. */ -time_t -approx_time(void) -{ - return cached_approx_time; -} - -/** Update the cached estimate of the current time. This function SHOULD be - * called once per second, and MUST be called before the first call to - * get_approx_time. */ -void -update_approx_time(time_t now) -{ - cached_approx_time = now; -} -#endif /* !defined(TIME_IS_FAST) */ - -/* ===== * Rate limiting * ===== */ diff --git a/src/common/util.h b/src/common/util.h index 916bddc1f..f2df84b19 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -24,6 +24,7 @@ #endif #include "lib/err/torerr.h" #include "lib/malloc/util_malloc.h" +#include "lib/wallclock/approx_time.h" #include "common/util_bug.h" #ifndef O_BINARY @@ -178,15 +179,6 @@ int parse_iso_time_nospace(const char *cp, time_t *t); int parse_http_time(const char *buf, struct tm *tm); int format_time_interval(char *out, size_t out_len, long interval); -/* Cached time */ -#ifdef TIME_IS_FAST -#define approx_time() time(NULL) -#define update_approx_time(t) STMT_NIL -#else -time_t approx_time(void); -void update_approx_time(time_t now); -#endif /* defined(TIME_IS_FAST) */ - /* Rate-limiter */ /** A ratelim_t remembers how often an event is occurring, and how often diff --git a/src/include.am b/src/include.am index 581fd69c7..a2c0cc88b 100644 --- a/src/include.am +++ b/src/include.am @@ -11,6 +11,7 @@ include src/lib/malloc/include.am include src/lib/testsupport/include.am include src/lib/tls/include.am include src/lib/trace/include.am +include src/lib/wallclock/include.am include src/common/include.am include src/trunnel/include.am include src/or/include.am diff --git a/src/lib/wallclock/.may_include b/src/lib/wallclock/.may_include new file mode 100644 index 000000000..686d9196f --- /dev/null +++ b/src/lib/wallclock/.may_include @@ -0,0 +1,4 @@ +orconfig.h +lib/err/*.h +lib/wallclock/*.h +lib/testsupport/*.h diff --git a/src/lib/wallclock/approx_time.c b/src/lib/wallclock/approx_time.c new file mode 100644 index 000000000..2528954f1 --- /dev/null +++ b/src/lib/wallclock/approx_time.c @@ -0,0 +1,38 @@ +/* Copyright (c) 2003, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "orconfig.h" +#include "lib/wallclock/approx_time.h" + +/* ===== + * Cached time + * ===== */ + +#ifndef TIME_IS_FAST +/** Cached estimate of the current time. Updated around once per second; + * may be a few seconds off if we are really busy. This is a hack to avoid + * calling time(NULL) (which not everybody has optimized) on critical paths. + */ +static time_t cached_approx_time = 0; + +/** Return a cached estimate of the current time from when + * update_approx_time() was last called. This is a hack to avoid calling + * time(NULL) on critical paths: please do not even think of calling it + * anywhere else. */ +time_t +approx_time(void) +{ + return cached_approx_time; +} + +/** Update the cached estimate of the current time. This function SHOULD be + * called once per second, and MUST be called before the first call to + * get_approx_time. */ +void +update_approx_time(time_t now) +{ + cached_approx_time = now; +} +#endif /* !defined(TIME_IS_FAST) */ diff --git a/src/lib/wallclock/approx_time.h b/src/lib/wallclock/approx_time.h new file mode 100644 index 000000000..c57ff5bcd --- /dev/null +++ b/src/lib/wallclock/approx_time.h @@ -0,0 +1,20 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_APPROX_TIME_H +#define TOR_APPROX_TIME_H + +#include <time.h> + +/* Cached time */ +#ifdef TIME_IS_FAST +#define approx_time() time(NULL) +#define update_approx_time(t) STMT_NIL +#else +time_t approx_time(void); +void update_approx_time(time_t now); +#endif /* defined(TIME_IS_FAST) */ + +#endif diff --git a/src/lib/wallclock/include.am b/src/lib/wallclock/include.am new file mode 100644 index 000000000..d414eb468 --- /dev/null +++ b/src/lib/wallclock/include.am @@ -0,0 +1,19 @@ + +noinst_LIBRARIES += src/lib/libtor-wallclock.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-wallclock-testing.a +endif + +src_lib_libtor_wallclock_a_SOURCES = \ + src/lib/wallclock/approx_time.c \ + src/lib/wallclock/tor_gettimeofday.c + +src_lib_libtor_wallclock_testing_a_SOURCES = \ + $(src_lib_libtor_wallclock_a_SOURCES) +src_lib_libtor_wallclock_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_wallclock_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/wallclock/approx_time.h \ + src/lib/wallclock/tor_gettimeofday.h diff --git a/src/lib/wallclock/tor_gettimeofday.c b/src/lib/wallclock/tor_gettimeofday.c new file mode 100644 index 000000000..83081d9c9 --- /dev/null +++ b/src/lib/wallclock/tor_gettimeofday.c @@ -0,0 +1,82 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file compat_time.c + * \brief Portable wrappers for finding out the current time, running + * timers, etc. + **/ + +#include "orconfig.h" +#include "lib/err/torerr.h" +#include "lib/wallclock/tor_gettimeofday.h" + +#include <stddef.h> +#include <stdlib.h> + +#ifdef HAVE_SYS_TIME_H +#include <sys/time.h> +#endif + +#ifdef _WIN32 +#include <windows.h> +#endif + +#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif + +#ifndef HAVE_GETTIMEOFDAY +#ifdef HAVE_FTIME +#include <sys/timeb.h> +#endif +#endif + +/** Set *timeval to the current time of day. On error, log and terminate. + * (Same as gettimeofday(timeval,NULL), but never returns -1.) + */ +MOCK_IMPL(void, +tor_gettimeofday, (struct timeval *timeval)) +{ +#ifdef _WIN32 + /* Epoch bias copied from perl: number of units between windows epoch and + * Unix epoch. */ +#define EPOCH_BIAS U64_LITERAL(116444736000000000) +#define UNITS_PER_SEC U64_LITERAL(10000000) +#define USEC_PER_SEC U64_LITERAL(1000000) +#define UNITS_PER_USEC U64_LITERAL(10) + union { + uint64_t ft_64; + FILETIME ft_ft; + } ft; + /* number of 100-nsec units since Jan 1, 1601 */ + GetSystemTimeAsFileTime(&ft.ft_ft); + if (ft.ft_64 < EPOCH_BIAS) { + /* LCOV_EXCL_START */ + log_err(LD_GENERAL,"System time is before 1970; failing."); + exit(1); // exit ok: system clock is broken. + /* LCOV_EXCL_STOP */ + } + ft.ft_64 -= EPOCH_BIAS; + timeval->tv_sec = (unsigned) (ft.ft_64 / UNITS_PER_SEC); + timeval->tv_usec = (unsigned) ((ft.ft_64 / UNITS_PER_USEC) % USEC_PER_SEC); +#elif defined(HAVE_GETTIMEOFDAY) + if (gettimeofday(timeval, NULL)) { + /* LCOV_EXCL_START */ + /* If gettimeofday dies, we have either given a bad timezone (we didn't), + or segfaulted.*/ + raw_assert_unreached_msg("gettimeofday failed"); + /* LCOV_EXCL_STOP */ + } +#elif defined(HAVE_FTIME) + struct timeb tb; + ftime(&tb); + timeval->tv_sec = tb.time; + timeval->tv_usec = tb.millitm * 1000; +#else +#error "No way to get time." +#endif /* defined(_WIN32) || ... */ + return; +} diff --git a/src/lib/wallclock/tor_gettimeofday.h b/src/lib/wallclock/tor_gettimeofday.h new file mode 100644 index 000000000..728ad9565 --- /dev/null +++ b/src/lib/wallclock/tor_gettimeofday.h @@ -0,0 +1,15 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_GETTIMEOFDAY_H +#define TOR_GETTIMEOFDAY_H + +#include "lib/testsupport/testsupport.h" + +struct timeval; + +MOCK_DECL(void, tor_gettimeofday, (struct timeval *timeval)); + +#endif

1 0