diff options
author | Nick Mathewson <nickm@torproject.org> | 2018-06-26 11:27:33 -0400 |
---|---|---|
committer | Nick Mathewson <nickm@torproject.org> | 2018-06-26 11:27:33 -0400 |
commit | 92d8284a9792267514cbe21f3ce1564f6ad0e10b (patch) | |
tree | f4a82d867c9fb863f7a3f56a2baffb509a2af5c5 /src/lib | |
parent | b4e23dba930cbb8168151e1fe9dcf280615d6f3b (diff) | |
parent | 1b93b065fc3eb52fe5674d6df05c71c505ed1ef3 (diff) | |
download | tor-92d8284a9792267514cbe21f3ce1564f6ad0e10b.tar.gz tor-92d8284a9792267514cbe21f3ce1564f6ad0e10b.zip |
Merge branch 'log_dependencies'
Diffstat (limited to 'src/lib')
94 files changed, 7373 insertions, 55 deletions
diff --git a/src/lib/cc/compat_compiler.h b/src/lib/cc/compat_compiler.h index 31e84bcc5b..67d945cfaf 100644 --- a/src/lib/cc/compat_compiler.h +++ b/src/lib/cc/compat_compiler.h @@ -242,4 +242,18 @@ #error Unknown: SIZEOF_INTPTR_T #endif /* (SIZEOF_INTPTR_T == SIZEOF_INT) || ... */ +/** Macro: yield a pointer to the field at position <b>off</b> within the + * structure <b>st</b>. 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: Yields the number of elements in array x. */ +#define ARRAY_LENGTH(x) ((sizeof(x)) / sizeof(x[0])) + #endif /* !defined(TOR_COMPAT_H) */ diff --git a/src/lib/compress/.may_include b/src/lib/compress/.may_include index 70528a7df0..3f69dd1333 100644 --- a/src/lib/compress/.may_include +++ b/src/lib/compress/.may_include @@ -1,6 +1,7 @@ orconfig.h lib/cc/*.h lib/compress/*.h +lib/log/*.h # XXX I'd like to remove this. common/*.h diff --git a/src/lib/compress/compress.c b/src/lib/compress/compress.c index cb130b693b..64f10b45ce 100644 --- a/src/lib/compress/compress.c +++ b/src/lib/compress/compress.c @@ -20,7 +20,7 @@ #endif #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/compress/compress.h" #include "lib/compress/compress_lzma.h" #include "lib/compress/compress_none.h" diff --git a/src/lib/compress/compress_lzma.c b/src/lib/compress/compress_lzma.c index 921aaa1d72..e7f3680b28 100644 --- a/src/lib/compress/compress_lzma.c +++ b/src/lib/compress/compress_lzma.c @@ -14,7 +14,7 @@ #include "orconfig.h" #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/compress/compress.h" #include "lib/compress/compress_lzma.h" diff --git a/src/lib/compress/compress_none.c b/src/lib/compress/compress_none.c index 05a27e5cc3..11f99d82e6 100644 --- a/src/lib/compress/compress_none.c +++ b/src/lib/compress/compress_none.c @@ -17,7 +17,7 @@ #include "orconfig.h" #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/compress/compress.h" #include "lib/compress/compress_none.h" diff --git a/src/lib/compress/compress_zlib.c b/src/lib/compress/compress_zlib.c index 56dda8a2de..7cba1150ed 100644 --- a/src/lib/compress/compress_zlib.c +++ b/src/lib/compress/compress_zlib.c @@ -14,7 +14,7 @@ #include "orconfig.h" #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/compress/compress.h" #include "lib/compress/compress_zlib.h" diff --git a/src/lib/compress/compress_zstd.c b/src/lib/compress/compress_zstd.c index 37204ab5ef..f24c7a5abc 100644 --- a/src/lib/compress/compress_zstd.c +++ b/src/lib/compress/compress_zstd.c @@ -14,7 +14,7 @@ #include "orconfig.h" #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/compress/compress.h" #include "lib/compress/compress_zstd.h" diff --git a/src/lib/container/.may_include b/src/lib/container/.may_include new file mode 100644 index 0000000000..1114ad8453 --- /dev/null +++ b/src/lib/container/.may_include @@ -0,0 +1,16 @@ +orconfig.h +lib/cc/*.h +lib/container/*.h +lib/ctime/*.h +lib/defs/*.h +lib/malloc/*.h +lib/err/*.h +lib/string/*.h +lib/testsupport/testsupport.h +lib/intmath/*.h + +ht.h +siphash.h + +# XXX I'd like to remove this. +lib/log/util_bug.h diff --git a/src/lib/container/bitarray.h b/src/lib/container/bitarray.h new file mode 100644 index 0000000000..2cea433fb0 --- /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 <b>n_bits</b> 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 <b>ba</b> from holding <b>n_bits_old</b> to <b>n_bits_new</b>, + * 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 <b>ba</b>. */ +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 <b>bit</b>th bit in <b>b</b> to 1. */ +static inline void +bitarray_set(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); +} +/** Set the <b>bit</b>th bit in <b>b</b> to 0. */ +static inline void +bitarray_clear(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK)); +} +/** Return true iff <b>bit</b>th bit in <b>b</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 0000000000..cbb4d13e5d --- /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 "lib/intmath/bits.h" + +/** Return a newly allocated digestset_t, optimized to hold a total of + * <b>max_elements</b> 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 <b>set</b>. */ +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 0000000000..adcdb10fc3 --- /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 <b>ba</b>; 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 <b>digest</b> to <b>set</b>. */ +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 <b>digest</b> is in <b>set</b>, return nonzero. Otherwise, + * <em>probably</em> 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/include.am b/src/lib/container/include.am new file mode 100644 index 0000000000..0e7acdff97 --- /dev/null +++ b/src/lib/container/include.am @@ -0,0 +1,24 @@ + +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/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) +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/bitarray.h \ + src/lib/container/bloomfilt.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 0000000000..5f280b3169 --- /dev/null +++ b/src/lib/container/map.c @@ -0,0 +1,414 @@ +/* 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/defs/digest_sizes.h" +#include "lib/string/util_string.h" +#include "lib/malloc/util_malloc.h" + +#include "lib/log/util_bug.h" + +#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 <b>maptype</b>. The key part of each + * entry is declared using the C declaration <b>keydecl</b>. All functions + * and types associated with the map get prefixed with <b>prefix</b> */ +#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 + * 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 + * 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 <b>map</b> whose key matches <b>key</b>, 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 <b>map</b> mapping <b>key</b> to <b>val</b>; \ + * 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 <b>key</b> from the map. \ + * Return the value if one was set, or NULL if there was no entry for \ + * <b>key</b>. \ + * \ + * 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 <b>map</b>. */ \ + int \ + prefix##_size(const maptype *map) \ + { \ + return HT_SIZE(&map->head); \ + } \ + \ + /** Return true iff <b>map</b> has no entries. */ \ + int \ + prefix##_isempty(const maptype *map) \ + { \ + return HT_EMPTY(&map->head); \ + } \ + \ + /** Assert that <b>map</b> is not corrupt. */ \ + void \ + prefix##_assert_ok(const maptype *map) \ + { \ + tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \ + } \ + \ + /** Remove all entries from <b>map</b>, and deallocate storage for \ + * those entries. If free_val is provided, invoked it every value in \ + * <b>map</b>. */ \ + 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 <b>iterator</b> 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 <b>iter</b> 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 <b>iter</b> 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 *<b>keyp</b> and *<b>valp</b> 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 <b>iter</b> has advanced past the last entry of \ + * <b>map</b>. */ \ + 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 <b>key</b> 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 <b>key</b> 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 <b>key</b> 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 0000000000..ac21c28718 --- /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 <b>map</b> in order. + * <b>prefix</b> 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 0000000000..4fdd51d996 --- /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 "lib/log/util_bug.h" + +/** Declare a function called <b>funcname</b> that acts as a find_nth_FOO + * function for an array of type <b>elt_t</b>*. + * + * 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 0000000000..bd23750d54 --- /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 <b>array</b> of <b>n_elements</b>, return the + * <b>nth</b> lowest element. <b>nth</b>=0 gives the lowest element; + * <b>n_elements</b>-1 gives the highest; and (<b>n_elements</b>-1) / 2 gives + * the median. As a side effect, the elements of <b>array</b> 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/smartlist.c b/src/lib/container/smartlist.c new file mode 100644 index 0000000000..852a32810d --- /dev/null +++ b/src/lib/container/smartlist.c @@ -0,0 +1,1124 @@ +/* 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/malloc/util_malloc.h" +#include "lib/container/smartlist.h" +#include "lib/err/torerr.h" +#include "lib/malloc/util_malloc.h" +#include "lib/defs/digest_sizes.h" +#include "lib/ctime/di_ops.h" +#include "lib/string/compat_ctype.h" +#include "lib/string/util_string.h" +#include "lib/string/printf.h" + +#include "lib/log/util_bug.h" + +#include <stdlib.h> +#include <string.h> + +/** All newly allocated smartlists have this capacity. */ +#define SMARTLIST_DEFAULT_CAPACITY 16 + +/** Allocate and return an empty smartlist. + */ +MOCK_IMPL(smartlist_t *, +smartlist_new,(void)) +{ + smartlist_t *sl = tor_malloc(sizeof(smartlist_t)); + sl->num_used = 0; + sl->capacity = SMARTLIST_DEFAULT_CAPACITY; + sl->list = tor_calloc(sizeof(void *), sl->capacity); + return sl; +} + +/** Deallocate a smartlist. Does not release storage associated with the + * list's elements. + */ +MOCK_IMPL(void, +smartlist_free_,(smartlist_t *sl)) +{ + if (!sl) + return; + tor_free(sl->list); + tor_free(sl); +} + +/** Remove all elements from the list. + */ +void +smartlist_clear(smartlist_t *sl) +{ + memset(sl->list, 0, sizeof(void *) * sl->num_used); + sl->num_used = 0; +} + +#if SIZE_MAX < INT_MAX +#error "We don't support systems where size_t is smaller than int." +#endif + +/** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */ +static inline void +smartlist_ensure_capacity(smartlist_t *sl, size_t size) +{ + /* Set MAX_CAPACITY to MIN(INT_MAX, SIZE_MAX / sizeof(void*)) */ +#if (SIZE_MAX/SIZEOF_VOID_P) > INT_MAX +#define MAX_CAPACITY (INT_MAX) +#else +#define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*)))) +#endif + + raw_assert(size <= MAX_CAPACITY); + + if (size > (size_t) sl->capacity) { + size_t higher = (size_t) sl->capacity; + if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) { + higher = MAX_CAPACITY; + } else { + while (size > higher) + higher *= 2; + } + sl->list = tor_reallocarray(sl->list, sizeof(void *), + ((size_t)higher)); + memset(sl->list + sl->capacity, 0, + sizeof(void *) * (higher - sl->capacity)); + sl->capacity = (int) higher; + } +#undef ASSERT_CAPACITY +#undef MAX_CAPACITY +} + +/** Append element to the end of the list. */ +void +smartlist_add(smartlist_t *sl, void *element) +{ + smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1); + sl->list[sl->num_used++] = element; +} + +/** Append each element from S2 to the end of S1. */ +void +smartlist_add_all(smartlist_t *s1, const smartlist_t *s2) +{ + size_t new_size = (size_t)s1->num_used + (size_t)s2->num_used; + tor_assert(new_size >= (size_t) s1->num_used); /* check for overflow. */ + smartlist_ensure_capacity(s1, new_size); + memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*)); + tor_assert(new_size <= INT_MAX); /* redundant. */ + s1->num_used = (int) new_size; +} + +/** Append a copy of string to sl */ +void +smartlist_add_strdup(struct smartlist_t *sl, const char *string) +{ + char *copy; + + copy = tor_strdup(string); + + smartlist_add(sl, copy); +} + +/** Append the string produced by tor_asprintf(<b>pattern</b>, <b>...</b>) + * to <b>sl</b>. */ +void +smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern, ...) +{ + va_list ap; + va_start(ap, pattern); + smartlist_add_vasprintf(sl, pattern, ap); + va_end(ap); +} + +/** va_list-based backend of smartlist_add_asprintf. */ +void +smartlist_add_vasprintf(struct smartlist_t *sl, const char *pattern, + va_list args) +{ + char *str = NULL; + + tor_vasprintf(&str, pattern, args); + tor_assert(str != NULL); + + smartlist_add(sl, str); +} + +/** Remove all elements E from sl such that E==element. Preserve + * the order of any elements before E, but elements after E can be + * rearranged. + */ +void +smartlist_remove(smartlist_t *sl, const void *element) +{ + int i; + if (element == NULL) + return; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) { + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + sl->list[sl->num_used] = NULL; + } +} + +/** As <b>smartlist_remove</b>, but do not change the order of + * any elements not removed */ +void +smartlist_remove_keeporder(smartlist_t *sl, const void *element) +{ + int i, j, num_used_orig = sl->num_used; + if (element == NULL) + return; + + for (i=j=0; j < num_used_orig; ++j) { + if (sl->list[j] == element) { + --sl->num_used; + } else { + sl->list[i++] = sl->list[j]; + } + } +} + +/** If <b>sl</b> is nonempty, remove and return the final element. Otherwise, + * return NULL. */ +void * +smartlist_pop_last(smartlist_t *sl) +{ + tor_assert(sl); + if (sl->num_used) { + void *tmp = sl->list[--sl->num_used]; + sl->list[sl->num_used] = NULL; + return tmp; + } else + return NULL; +} + +/** Reverse the order of the items in <b>sl</b>. */ +void +smartlist_reverse(smartlist_t *sl) +{ + int i, j; + void *tmp; + tor_assert(sl); + for (i = 0, j = sl->num_used-1; i < j; ++i, --j) { + tmp = sl->list[i]; + sl->list[i] = sl->list[j]; + sl->list[j] = tmp; + } +} + +/** If there are any strings in sl equal to element, remove and free them. + * Does not preserve order. */ +void +smartlist_string_remove(smartlist_t *sl, const char *element) +{ + int i; + tor_assert(sl); + tor_assert(element); + for (i = 0; i < sl->num_used; ++i) { + if (!strcmp(element, sl->list[i])) { + tor_free(sl->list[i]); + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + sl->list[sl->num_used] = NULL; + } + } +} + +/** Return true iff some element E of sl has E==element. + */ +int +smartlist_contains(const smartlist_t *sl, const void *element) +{ + int i; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) + return 1; + return 0; +} + +/** Return true iff <b>sl</b> has some element E such that + * !strcmp(E,<b>element</b>) + */ +int +smartlist_contains_string(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** If <b>element</b> is equal to an element of <b>sl</b>, return that + * element's index. Otherwise, return -1. */ +int +smartlist_string_pos(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return -1; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return i; + return -1; +} + +/** If <b>element</b> is the same pointer as an element of <b>sl</b>, return + * that element's index. Otherwise, return -1. */ +int +smartlist_pos(const smartlist_t *sl, const void *element) +{ + int i; + if (!sl) return -1; + for (i=0; i < sl->num_used; i++) + if (element == sl->list[i]) + return i; + return -1; +} + +/** Return true iff <b>sl</b> has some element E such that + * !strcasecmp(E,<b>element</b>) + */ +int +smartlist_contains_string_case(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcasecmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** Return true iff <b>sl</b> has some element E such that E is equal + * to the decimal encoding of <b>num</b>. + */ +int +smartlist_contains_int_as_string(const smartlist_t *sl, int num) +{ + char buf[32]; /* long enough for 64-bit int, and then some. */ + tor_snprintf(buf,sizeof(buf),"%d", num); + return smartlist_contains_string(sl, buf); +} + +/** Return true iff the two lists contain the same strings in the same + * order, or if they are both NULL. */ +int +smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2) +{ + if (sl1 == NULL) + return sl2 == NULL; + if (sl2 == NULL) + return 0; + if (smartlist_len(sl1) != smartlist_len(sl2)) + return 0; + SMARTLIST_FOREACH(sl1, const char *, cp1, { + const char *cp2 = smartlist_get(sl2, cp1_sl_idx); + if (strcmp(cp1, cp2)) + return 0; + }); + return 1; +} + +/** Return true iff the two lists contain the same int pointer values in + * the same order, or if they are both NULL. */ +int +smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2) +{ + if (sl1 == NULL) + return sl2 == NULL; + if (sl2 == NULL) + return 0; + if (smartlist_len(sl1) != smartlist_len(sl2)) + return 0; + SMARTLIST_FOREACH(sl1, int *, cp1, { + int *cp2 = smartlist_get(sl2, cp1_sl_idx); + if (*cp1 != *cp2) + return 0; + }); + return 1; +} + +/** Return true iff <b>sl</b> has some element E such that + * tor_memeq(E,<b>element</b>,DIGEST_LEN) + */ +int +smartlist_contains_digest(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN)) + return 1; + return 0; +} + +/** Return true iff some element E of sl2 has smartlist_contains(sl1,E). + */ +int +smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl2->num_used; i++) + if (smartlist_contains(sl1, sl2->list[i])) + return 1; + return 0; +} + +/** Remove every element E of sl1 such that !smartlist_contains(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl1->num_used; i++) + if (!smartlist_contains(sl2, sl1->list[i])) { + sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + sl1->list[sl1->num_used] = NULL; + } +} + +/** Remove every element E of sl1 such that smartlist_contains(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl2->num_used; i++) + smartlist_remove(sl1, sl2->list[i]); +} + +/** Remove the <b>idx</b>th element of sl; if idx is not the last + * element, swap the last element of sl into the <b>idx</b>th space. + */ +void +smartlist_del(smartlist_t *sl, int idx) +{ + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(idx < sl->num_used); + sl->list[idx] = sl->list[--sl->num_used]; + sl->list[sl->num_used] = NULL; +} + +/** Remove the <b>idx</b>th element of sl; if idx is not the last element, + * moving all subsequent elements back one space. Return the old value + * of the <b>idx</b>th element. + */ +void +smartlist_del_keeporder(smartlist_t *sl, int idx) +{ + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(idx < sl->num_used); + --sl->num_used; + if (idx < sl->num_used) + memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx)); + sl->list[sl->num_used] = NULL; +} + +/** Insert the value <b>val</b> as the new <b>idx</b>th element of + * <b>sl</b>, moving all items previously at <b>idx</b> or later + * forward one space. + */ +void +smartlist_insert(smartlist_t *sl, int idx, void *val) +{ + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(idx <= sl->num_used); + if (idx == sl->num_used) { + smartlist_add(sl, val); + } else { + smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1); + /* Move other elements away */ + if (idx < sl->num_used) + memmove(sl->list + idx + 1, sl->list + idx, + sizeof(void*)*(sl->num_used-idx)); + sl->num_used++; + sl->list[idx] = val; + } +} + +/** + * Split a string <b>str</b> along all occurrences of <b>sep</b>, + * appending the (newly allocated) split strings, in order, to + * <b>sl</b>. Return the number of strings added to <b>sl</b>. + * + * If <b>flags</b>&SPLIT_SKIP_SPACE is true, remove initial and + * trailing space from each entry. + * If <b>flags</b>&SPLIT_IGNORE_BLANK is true, remove any entries + * of length 0. + * If <b>flags</b>&SPLIT_STRIP_SPACE is true, strip spaces from each + * split string. + * + * If <b>max</b>\>0, divide the string into no more than <b>max</b> pieces. If + * <b>sep</b> is NULL, split on any sequence of horizontal space. + */ +int +smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, + int flags, int max) +{ + const char *cp, *end, *next; + int n = 0; + + tor_assert(sl); + tor_assert(str); + + cp = str; + while (1) { + if (flags&SPLIT_SKIP_SPACE) { + while (TOR_ISSPACE(*cp)) ++cp; + } + + if (max>0 && n == max-1) { + end = strchr(cp,'\0'); + } else if (sep) { + end = strstr(cp,sep); + if (!end) + end = strchr(cp,'\0'); + } else { + for (end = cp; *end && *end != '\t' && *end != ' '; ++end) + ; + } + + tor_assert(end); + + if (!*end) { + next = NULL; + } else if (sep) { + next = end+strlen(sep); + } else { + next = end+1; + while (*next == '\t' || *next == ' ') + ++next; + } + + if (flags&SPLIT_SKIP_SPACE) { + while (end > cp && TOR_ISSPACE(*(end-1))) + --end; + } + if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) { + char *string = tor_strndup(cp, end-cp); + if (flags&SPLIT_STRIP_SPACE) + tor_strstrip(string, " "); + smartlist_add(sl, string); + ++n; + } + if (!next) + break; + cp = next; + } + + return n; +} + +/** Allocate and return a new string containing the concatenation of + * the elements of <b>sl</b>, in order, separated by <b>join</b>. If + * <b>terminate</b> is true, also terminate the string with <b>join</b>. + * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of + * the returned string. Requires that every element of <b>sl</b> is + * NUL-terminated string. + */ +char * +smartlist_join_strings(smartlist_t *sl, const char *join, + int terminate, size_t *len_out) +{ + return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out); +} + +/** As smartlist_join_strings, but instead of separating/terminated with a + * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence + * at <b>join</b>. (Useful for generating a sequence of NUL-terminated + * strings.) + */ +char * +smartlist_join_strings2(smartlist_t *sl, const char *join, + size_t join_len, int terminate, size_t *len_out) +{ + int i; + size_t n = 0; + char *r = NULL, *dst, *src; + + tor_assert(sl); + tor_assert(join); + + if (terminate) + n = join_len; + + for (i = 0; i < sl->num_used; ++i) { + n += strlen(sl->list[i]); + if (i+1 < sl->num_used) /* avoid double-counting the last one */ + n += join_len; + } + dst = r = tor_malloc(n+1); + for (i = 0; i < sl->num_used; ) { + for (src = sl->list[i]; *src; ) + *dst++ = *src++; + if (++i < sl->num_used) { + memcpy(dst, join, join_len); + dst += join_len; + } + } + if (terminate) { + memcpy(dst, join, join_len); + dst += join_len; + } + *dst = '\0'; + + if (len_out) + *len_out = dst-r; + return r; +} + +/** Sort the members of <b>sl</b> into an order defined by + * the ordering function <b>compare</b>, which returns less then 0 if a + * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b. + */ +void +smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)) +{ + if (!sl->num_used) + return; + qsort(sl->list, sl->num_used, sizeof(void*), + (int (*)(const void *,const void*))compare); +} + +/** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>, + * return the most frequent member in the list. Break ties in favor of + * later elements. If the list is empty, return NULL. If count_out is + * non-null, set it to the count of the most frequent member. + */ +void * +smartlist_get_most_frequent_(const smartlist_t *sl, + int (*compare)(const void **a, const void **b), + int *count_out) +{ + const void *most_frequent = NULL; + int most_frequent_count = 0; + + const void *cur = NULL; + int i, count=0; + + if (!sl->num_used) { + if (count_out) + *count_out = 0; + return NULL; + } + for (i = 0; i < sl->num_used; ++i) { + const void *item = sl->list[i]; + if (cur && 0 == compare(&cur, &item)) { + ++count; + } else { + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + cur = item; + count = 1; + } + } + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + if (count_out) + *count_out = most_frequent_count; + return (void*)most_frequent; +} + +/** Given a sorted smartlist <b>sl</b> and the comparison function used to + * sort it, remove all duplicate members. If free_fn is provided, calls + * free_fn on each duplicate. Otherwise, just removes them. Preserves order. + */ +void +smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *a)) +{ + int i; + for (i=1; i < sl->num_used; ++i) { + if (compare((const void **)&(sl->list[i-1]), + (const void **)&(sl->list[i])) == 0) { + if (free_fn) + free_fn(sl->list[i]); + smartlist_del_keeporder(sl, i--); + } + } +} + +/** Assuming the members of <b>sl</b> are in order, return a pointer to the + * member that matches <b>key</b>. Ordering and matching are defined by a + * <b>compare</b> function that returns 0 on a match; less than 0 if key is + * less than member, and greater than 0 if key is greater then member. + */ +void * +smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)) +{ + int found, idx; + idx = smartlist_bsearch_idx(sl, key, compare, &found); + return found ? smartlist_get(sl, idx) : NULL; +} + +/** Assuming the members of <b>sl</b> are in order, return the index of the + * member that matches <b>key</b>. If no member matches, return the index of + * the first member greater than <b>key</b>, or smartlist_len(sl) if no member + * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to + * false otherwise. Ordering and matching are defined by a <b>compare</b> + * function that returns 0 on a match; less than 0 if key is less than member, + * and greater than 0 if key is greater then member. + */ +int +smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out) +{ + int hi, lo, cmp, mid, len, diff; + + tor_assert(sl); + tor_assert(compare); + tor_assert(found_out); + + len = smartlist_len(sl); + + /* Check for the trivial case of a zero-length list */ + if (len == 0) { + *found_out = 0; + /* We already know smartlist_len(sl) is 0 in this case */ + return 0; + } + + /* Okay, we have a real search to do */ + tor_assert(len > 0); + lo = 0; + hi = len - 1; + + /* + * These invariants are always true: + * + * For all i such that 0 <= i < lo, sl[i] < key + * For all i such that hi < i <= len, sl[i] > key + */ + + while (lo <= hi) { + diff = hi - lo; + /* + * We want mid = (lo + hi) / 2, but that could lead to overflow, so + * instead diff = hi - lo (non-negative because of loop condition), and + * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2). + */ + mid = lo + (diff / 2); + cmp = compare(key, (const void**) &(sl->list[mid])); + if (cmp == 0) { + /* sl[mid] == key; we found it */ + *found_out = 1; + return mid; + } else if (cmp > 0) { + /* + * key > sl[mid] and an index i such that sl[i] == key must + * have i > mid if it exists. + */ + + /* + * Since lo <= mid <= hi, hi can only decrease on each iteration (by + * being set to mid - 1) and hi is initially len - 1, mid < len should + * always hold, and this is not symmetric with the left end of list + * mid > 0 test below. A key greater than the right end of the list + * should eventually lead to lo == hi == mid == len - 1, and then + * we set lo to len below and fall out to the same exit we hit for + * a key in the middle of the list but not matching. Thus, we just + * assert for consistency here rather than handle a mid == len case. + */ + tor_assert(mid < len); + /* Move lo to the element immediately after sl[mid] */ + lo = mid + 1; + } else { + /* This should always be true in this case */ + tor_assert(cmp < 0); + + /* + * key < sl[mid] and an index i such that sl[i] == key must + * have i < mid if it exists. + */ + + if (mid > 0) { + /* Normal case, move hi to the element immediately before sl[mid] */ + hi = mid - 1; + } else { + /* These should always be true in this case */ + tor_assert(mid == lo); + tor_assert(mid == 0); + /* + * We were at the beginning of the list and concluded that every + * element e compares e > key. + */ + *found_out = 0; + return 0; + } + } + } + + /* + * lo > hi; we have no element matching key but we have elements falling + * on both sides of it. The lo index points to the first element > key. + */ + tor_assert(lo == hi + 1); /* All other cases should have been handled */ + tor_assert(lo >= 0); + tor_assert(lo <= len); + tor_assert(hi >= 0); + tor_assert(hi <= len); + + if (lo < len) { + cmp = compare(key, (const void **) &(sl->list[lo])); + tor_assert(cmp < 0); + } else { + cmp = compare(key, (const void **) &(sl->list[len-1])); + tor_assert(cmp > 0); + } + + *found_out = 0; + return lo; +} + +/** Helper: compare two const char **s. */ +static int +compare_string_ptrs_(const void **_a, const void **_b) +{ + return strcmp((const char*)*_a, (const char*)*_b); +} + +/** Sort a smartlist <b>sl</b> containing strings into lexically ascending + * order. */ +void +smartlist_sort_strings(smartlist_t *sl) +{ + smartlist_sort(sl, compare_string_ptrs_); +} + +/** Return the most frequent string in the sorted list <b>sl</b> */ +const char * +smartlist_get_most_frequent_string(smartlist_t *sl) +{ + return smartlist_get_most_frequent(sl, compare_string_ptrs_); +} + +/** Return the most frequent string in the sorted list <b>sl</b>. + * If <b>count_out</b> is provided, set <b>count_out</b> to the + * number of times that string appears. + */ +const char * +smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out) +{ + return smartlist_get_most_frequent_(sl, compare_string_ptrs_, count_out); +} + +/** Remove duplicate strings from a sorted list, and free them with tor_free(). + */ +void +smartlist_uniq_strings(smartlist_t *sl) +{ + smartlist_uniq(sl, compare_string_ptrs_, tor_free_); +} + +/** Helper: compare two pointers. */ +static int +compare_ptrs_(const void **_a, const void **_b) +{ + const void *a = *_a, *b = *_b; + if (a<b) + return -1; + else if (a==b) + return 0; + else + return 1; +} + +/** Sort <b>sl</b> in ascending order of the pointers it contains. */ +void +smartlist_sort_pointers(smartlist_t *sl) +{ + smartlist_sort(sl, compare_ptrs_); +} + +/* Heap-based priority queue implementation for O(lg N) insert and remove. + * Recall that the heap property is that, for every index I, h[I] < + * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]]. + * + * For us to remove items other than the topmost item, each item must store + * its own index within the heap. When calling the pqueue functions, tell + * them about the offset of the field that stores the index within the item. + * + * Example: + * + * typedef struct timer_t { + * struct timeval tv; + * int heap_index; + * } timer_t; + * + * static int compare(const void *p1, const void *p2) { + * const timer_t *t1 = p1, *t2 = p2; + * if (t1->tv.tv_sec < t2->tv.tv_sec) { + * return -1; + * } else if (t1->tv.tv_sec > t2->tv.tv_sec) { + * return 1; + * } else { + * return t1->tv.tv_usec - t2->tv_usec; + * } + * } + * + * void timer_heap_insert(smartlist_t *heap, timer_t *timer) { + * smartlist_pqueue_add(heap, compare, offsetof(timer_t, heap_index), + * timer); + * } + * + * void timer_heap_pop(smartlist_t *heap) { + * return smartlist_pqueue_pop(heap, compare, + * offsetof(timer_t, heap_index)); + * } + */ + +/** @{ */ +/** Functions to manipulate heap indices to find a node's parent and children. + * + * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x] + * = 2*x + 1. But this is C, so we have to adjust a little. */ + +/* MAX_PARENT_IDX is the largest IDX in the smartlist which might have + * children whose indices fit inside an int. + * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2; + * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1; + * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size. + */ +#define MAX_PARENT_IDX ((INT_MAX - 2) / 2) +/* If this is true, then i is small enough to potentially have children + * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */ +#define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX) +#define LEFT_CHILD(i) ( 2*(i) + 1 ) +#define RIGHT_CHILD(i) ( 2*(i) + 2 ) +#define PARENT(i) ( ((i)-1) / 2 ) +/** }@ */ + +/** @{ */ +/** Helper macros for heaps: Given a local variable <b>idx_field_offset</b> + * set to the offset of an integer index within the heap element structure, + * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to + * where p's index is stored. Given additionally a local smartlist <b>sl</b>, + * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct + * value (that is, to <b>i</b>). + */ +#define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset)) + +#define UPDATE_IDX(i) do { \ + void *updated = sl->list[i]; \ + *IDXP(updated) = i; \ + } while (0) + +#define IDX_OF_ITEM(p) (*IDXP(p)) +/** @} */ + +/** Helper. <b>sl</b> may have at most one violation of the heap property: + * the item at <b>idx</b> may be greater than one or both of its children. + * Restore the heap property. */ +static inline void +smartlist_heapify(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + int idx) +{ + while (1) { + if (! IDX_MAY_HAVE_CHILDREN(idx)) { + /* idx is so large that it cannot have any children, since doing so + * would mean the smartlist was over-capacity. Therefore it cannot + * violate the heap property by being greater than a child (since it + * doesn't have any). */ + return; + } + + int left_idx = LEFT_CHILD(idx); + int best_idx; + + if (left_idx >= sl->num_used) + return; + if (compare(sl->list[idx],sl->list[left_idx]) < 0) + best_idx = idx; + else + best_idx = left_idx; + if (left_idx+1 < sl->num_used && + compare(sl->list[left_idx+1],sl->list[best_idx]) < 0) + best_idx = left_idx + 1; + + if (best_idx == idx) { + return; + } else { + void *tmp = sl->list[idx]; + sl->list[idx] = sl->list[best_idx]; + sl->list[best_idx] = tmp; + UPDATE_IDX(idx); + UPDATE_IDX(best_idx); + + idx = best_idx; + } + } +} + +/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is + * determined by <b>compare</b> and the offset of the item in the heap is + * stored in an int-typed field at position <b>idx_field_offset</b> within + * item. + */ +void +smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx; + smartlist_add(sl,item); + UPDATE_IDX(sl->num_used-1); + + for (idx = sl->num_used - 1; idx; ) { + int parent = PARENT(idx); + if (compare(sl->list[idx], sl->list[parent]) < 0) { + void *tmp = sl->list[parent]; + sl->list[parent] = sl->list[idx]; + sl->list[idx] = tmp; + UPDATE_IDX(parent); + UPDATE_IDX(idx); + idx = parent; + } else { + return; + } + } +} + +/** Remove and return the top-priority item from the heap stored in <b>sl</b>, + * where order is determined by <b>compare</b> and the item's position is + * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must + * not be empty. */ +void * +smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + void *top; + tor_assert(sl->num_used); + + top = sl->list[0]; + *IDXP(top)=-1; + if (--sl->num_used) { + sl->list[0] = sl->list[sl->num_used]; + sl->list[sl->num_used] = NULL; + UPDATE_IDX(0); + smartlist_heapify(sl, compare, idx_field_offset, 0); + } + sl->list[sl->num_used] = NULL; + return top; +} + +/** Remove the item <b>item</b> from the heap stored in <b>sl</b>, + * where order is determined by <b>compare</b> and the item's position is + * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must + * not be empty. */ +void +smartlist_pqueue_remove(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx = IDX_OF_ITEM(item); + tor_assert(idx >= 0); + tor_assert(sl->list[idx] == item); + --sl->num_used; + *IDXP(item) = -1; + if (idx == sl->num_used) { + sl->list[sl->num_used] = NULL; + return; + } else { + sl->list[idx] = sl->list[sl->num_used]; + sl->list[sl->num_used] = NULL; + UPDATE_IDX(idx); + smartlist_heapify(sl, compare, idx_field_offset, idx); + } +} + +/** Assert that the heap property is correctly maintained by the heap stored + * in <b>sl</b>, where order is determined by <b>compare</b>. */ +void +smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + int i; + for (i = sl->num_used - 1; i >= 0; --i) { + if (i>0) + tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0); + tor_assert(IDX_OF_ITEM(sl->list[i]) == i); + } +} + +/** Helper: compare two DIGEST_LEN digests. */ +static int +compare_digests_(const void **_a, const void **_b) +{ + return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN); +} + +/** Sort the list of DIGEST_LEN-byte digests into ascending order. */ +void +smartlist_sort_digests(smartlist_t *sl) +{ + smartlist_sort(sl, compare_digests_); +} + +/** Remove duplicate digests from a sorted list, and free them with tor_free(). + */ +void +smartlist_uniq_digests(smartlist_t *sl) +{ + smartlist_uniq(sl, compare_digests_, tor_free_); +} + +/** Helper: compare two DIGEST256_LEN digests. */ +static int +compare_digests256_(const void **_a, const void **_b) +{ + return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); +} + +/** Sort the list of DIGEST256_LEN-byte digests into ascending order. */ +void +smartlist_sort_digests256(smartlist_t *sl) +{ + smartlist_sort(sl, compare_digests256_); +} + +/** Return the most frequent member of the sorted list of DIGEST256_LEN + * digests in <b>sl</b> */ +const uint8_t * +smartlist_get_most_frequent_digest256(smartlist_t *sl) +{ + return smartlist_get_most_frequent(sl, compare_digests256_); +} + +/** Remove duplicate 256-bit digests from a sorted list, and free them with + * tor_free(). + */ +void +smartlist_uniq_digests256(smartlist_t *sl) +{ + smartlist_uniq(sl, compare_digests256_, tor_free_); +} diff --git a/src/lib/container/smartlist.h b/src/lib/container/smartlist.h new file mode 100644 index 0000000000..c202e134f9 --- /dev/null +++ b/src/lib/container/smartlist.h @@ -0,0 +1,360 @@ +/* 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 <stdarg.h> + +#include "lib/cc/compat_compiler.h" +#include "lib/cc/torint.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 { + /** @{ */ + /** <b>list</b> has enough capacity to store exactly <b>capacity</b> elements + * before it needs to be resized. Only the first <b>num_used</b> (\<= + * 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_add_asprintf(struct smartlist_t *sl, const char *pattern, ...) + CHECK_PRINTF(2, 3); +void smartlist_add_vasprintf(struct smartlist_t *sl, const char *pattern, + va_list args) + CHECK_PRINTF(2, 0); +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 +#include "lib/err/torerr.h" +#include <stdlib.h> +/** 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) { + raw_assert(sl); + return (sl)->num_used; +} +/** Return the <b>idx</b>th 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) { + raw_assert(sl); + raw_assert(idx>=0); + raw_assert(sl->num_used > idx); + return sl->list[idx]; +} +static inline void smartlist_set(smartlist_t *sl, int idx, void *val) { + raw_assert(sl); + raw_assert(idx>=0); + raw_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 <b>idx1</b> and <b>idx2</b> of the + * smartlist <b>sl</b>. */ +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 <b>sl</b>, in order. For each item, + * assign it to a new local variable of type <b>type</b> named <b>var</b>, and + * execute the statements inside the loop body. Inside the loop, the loop + * index can be accessed as <b>var</b>_sl_idx and the length of the list can + * be accessed as <b>var</b>_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 + * <b>cmd</b> 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 <b>sl</b> indexed + * with the variable <b>var</b>, 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 <b>sl</b> indexed + * with the variable <b>var</b>, 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 <b>sl</b> indexed + * with the variable <b>var</b>, replace the current element with <b>val</b>. + * Does not deallocate the current value of <b>var</b>. + */ +#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 <b>cmpexpr</b>), and such that one list (<b>sl1</b>) has no + * duplicates on the common field, loop through the lists in lockstep, and + * execute <b>unmatched_var2</b> 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/crypt_ops/.may_include b/src/lib/crypt_ops/.may_include index 6eefec1581..8031bb9bcc 100644 --- a/src/lib/crypt_ops/.may_include +++ b/src/lib/crypt_ops/.may_include @@ -1,14 +1,22 @@ orconfig.h lib/cc/*.h +lib/container/*.h lib/crypt_ops/*.h lib/ctime/*.h +lib/defs/*.h +lib/malloc/*.h lib/err/*.h +lib/intmath/*.h +lib/string/*.h lib/testsupport/testsupport.h +lib/log/*.h 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/aes.c b/src/lib/crypt_ops/aes.c index c421453fdd..3a66e369c9 100644 --- a/src/lib/crypt_ops/aes.c +++ b/src/lib/crypt_ops/aes.c @@ -38,7 +38,7 @@ ENABLE_GCC_WARNING(redundant-decls) #include "common/compat.h" #include "lib/crypt_ops/aes.h" #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/ctime/di_ops.h" #ifdef ANDROID diff --git a/src/lib/crypt_ops/crypto.c b/src/lib/crypt_ops/crypto.c index b562578c59..fcd6945c84 100644 --- a/src/lib/crypt_ops/crypto.c +++ b/src/lib/crypt_ops/crypto.c @@ -62,17 +62,18 @@ ENABLE_GCC_WARNING(redundant-decls) #include <unistd.h> #endif -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/cc/torint.h" #include "lib/crypt_ops/aes.h" #include "common/util.h" -#include "common/container.h" #include "common/compat.h" #include "common/sandbox.h" #include "common/util_format.h" #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/lib/crypt_ops/crypto_curve25519.c b/src/lib/crypt_ops/crypto_curve25519.c index 8302483d87..276ff208aa 100644 --- a/src/lib/crypt_ops/crypto_curve25519.c +++ b/src/lib/crypt_ops/crypto_curve25519.c @@ -20,14 +20,13 @@ #ifdef HAVE_SYS_STAT_H #include <sys/stat.h> #endif -#include "common/container.h" #include "lib/crypt_ops/crypto_curve25519.h" #include "lib/crypt_ops/crypto_digest.h" #include "lib/crypt_ops/crypto_format.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_util.h" #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "ed25519/donna/ed25519_donna_tor.h" diff --git a/src/lib/crypt_ops/crypto_dh.c b/src/lib/crypt_ops/crypto_dh.c index 2442dae55e..daa9842934 100644 --- a/src/lib/crypt_ops/crypto_dh.c +++ b/src/lib/crypt_ops/crypto_dh.c @@ -23,7 +23,7 @@ ENABLE_GCC_WARNING(redundant-decls) #include <openssl/bn.h> -#include "common/torlog.h" +#include "lib/log/torlog.h" /** A structure to hold the first half (x, g^x) of a Diffie-Hellman handshake * while we're waiting for the second.*/ diff --git a/src/lib/crypt_ops/crypto_digest.c b/src/lib/crypt_ops/crypto_digest.c index 44494337c4..a505435935 100644 --- a/src/lib/crypt_ops/crypto_digest.c +++ b/src/lib/crypt_ops/crypto_digest.c @@ -10,11 +10,11 @@ * operations. **/ -#include "common/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" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "keccak-tiny/keccak-tiny.h" @@ -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 96ac038507..15bc5ad5b9 100644 --- a/src/lib/crypt_ops/crypto_digest.h +++ b/src/lib/crypt_ops/crypto_digest.h @@ -13,18 +13,9 @@ #ifndef TOR_CRYPTO_DIGEST_H #define TOR_CRYPTO_DIGEST_H -#include <stdio.h> - -#include "common/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" +#include "lib/malloc/util_malloc.h" /** Length of a sha1 message digest when encoded in base32 with trailing = * signs removed. */ @@ -78,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, @@ -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/crypt_ops/crypto_ed25519.c b/src/lib/crypt_ops/crypto_ed25519.c index ca1030b0ae..5655fbf508 100644 --- a/src/lib/crypt_ops/crypto_ed25519.c +++ b/src/lib/crypt_ops/crypto_ed25519.c @@ -27,7 +27,7 @@ #include "lib/crypt_ops/crypto_format.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "common/util.h" #include "common/util_format.h" diff --git a/src/lib/crypt_ops/crypto_format.c b/src/lib/crypt_ops/crypto_format.c index 07008eff2e..888c0794ec 100644 --- a/src/lib/crypt_ops/crypto_format.c +++ b/src/lib/crypt_ops/crypto_format.c @@ -14,15 +14,16 @@ #ifdef HAVE_SYS_STAT_H #include <sys/stat.h> #endif -#include "common/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" #include "lib/crypt_ops/crypto_format.h" #include "lib/crypt_ops/crypto_util.h" +#include "lib/string/util_string.h" #include "common/util.h" #include "common/util_format.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" /** Write the <b>datalen</b> bytes from <b>data</b> to the file named * <b>fname</b> in the tagged-data format. This format contains a @@ -296,4 +297,3 @@ digest256_from_base64(char *digest, const char *d64) else return -1; } - diff --git a/src/lib/crypt_ops/crypto_openssl_mgt.c b/src/lib/crypt_ops/crypto_openssl_mgt.c index b18717a112..2c2c2048e9 100644 --- a/src/lib/crypt_ops/crypto_openssl_mgt.c +++ b/src/lib/crypt_ops/crypto_openssl_mgt.c @@ -12,6 +12,7 @@ #include "lib/crypt_ops/compat_openssl.h" #include "lib/crypt_ops/crypto_openssl_mgt.h" +#include "lib/string/util_string.h" DISABLE_GCC_WARNING(redundant-decls) @@ -158,4 +159,3 @@ crypto_openssl_free_all(void) } #endif /* !defined(NEW_THREAD_API) */ } - diff --git a/src/lib/crypt_ops/crypto_pwbox.c b/src/lib/crypt_ops/crypto_pwbox.c index 9a315d42da..6944f8ab52 100644 --- a/src/lib/crypt_ops/crypto_pwbox.c +++ b/src/lib/crypt_ops/crypto_pwbox.c @@ -15,6 +15,7 @@ #include "lib/crypt_ops/crypto_s2k.h" #include "lib/crypt_ops/crypto_util.h" #include "lib/ctime/di_ops.h" +#include "lib/intmath/muldiv.h" #include "common/util.h" #include "trunnel/pwbox.h" @@ -212,4 +213,3 @@ crypto_unpwbox(uint8_t **out, size_t *outlen_out, memwipe(keys, 0, sizeof(keys)); return rv; } - diff --git a/src/lib/crypt_ops/crypto_rand.c b/src/lib/crypt_ops/crypto_rand.c index 0bd7b078c5..bff32c7ec6 100644 --- a/src/lib/crypt_ops/crypto_rand.c +++ b/src/lib/crypt_ops/crypto_rand.c @@ -21,13 +21,13 @@ #include <wincrypt.h> #endif /* defined(_WIN32) */ -#include "common/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" #include "common/sandbox.h" #include "lib/testsupport/testsupport.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "common/util.h" #include "common/util_format.h" @@ -612,4 +612,3 @@ crypto_force_rand_ssleay(void) } #endif /* !defined(CRYPTO_RAND_PRIVATE) */ - diff --git a/src/lib/crypt_ops/crypto_rsa.c b/src/lib/crypt_ops/crypto_rsa.c index a20d47132c..3f2f8544f7 100644 --- a/src/lib/crypt_ops/crypto_rsa.c +++ b/src/lib/crypt_ops/crypto_rsa.c @@ -33,7 +33,7 @@ DISABLE_GCC_WARNING(redundant-decls) ENABLE_GCC_WARNING(redundant-decls) -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "common/util.h" #include "common/util_format.h" diff --git a/src/lib/crypt_ops/crypto_rsa.h b/src/lib/crypt_ops/crypto_rsa.h index 3faec12378..75255c9cc8 100644 --- a/src/lib/crypt_ops/crypto_rsa.h +++ b/src/lib/crypt_ops/crypto_rsa.h @@ -21,7 +21,7 @@ #include "lib/testsupport/testsupport.h" #include "common/compat.h" #include "common/util.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" /** Length of our public keys. */ #define PK_BYTES (1024/8) diff --git a/src/lib/crypt_ops/crypto_util.c b/src/lib/crypt_ops/crypto_util.c index 8ef0690c15..db88805a78 100644 --- a/src/lib/crypt_ops/crypto_util.c +++ b/src/lib/crypt_ops/crypto_util.c @@ -32,7 +32,7 @@ DISABLE_GCC_WARNING(redundant-decls) ENABLE_GCC_WARNING(redundant-decls) -#include "common/torlog.h" +#include "lib/log/torlog.h" /** * Destroy the <b>sz</b> bytes of data stored at <b>mem</b>, setting them to diff --git a/src/lib/ctime/.may_include b/src/lib/ctime/.may_include index 72d854c374..e74669bce1 100644 --- a/src/lib/ctime/.may_include +++ b/src/lib/ctime/.may_include @@ -1,6 +1,5 @@ orconfig.h lib/cc/*.h lib/ctime/*.h - -# XXXX I'd like to remove this -common/util.h +lib/err/*.h +lib/malloc/*.h diff --git a/src/lib/ctime/di_ops.c b/src/lib/ctime/di_ops.c index 407131c448..287ff6080a 100644 --- a/src/lib/ctime/di_ops.c +++ b/src/lib/ctime/di_ops.c @@ -8,7 +8,10 @@ #include "orconfig.h" #include "lib/ctime/di_ops.h" -#include "common/util.h" +#include "lib/err/torerr.h" +#include "lib/malloc/util_malloc.h" + +#include <string.h> /** * Timing-safe version of memcmp. As memcmp, compare the <b>sz</b> bytes at @@ -170,8 +173,8 @@ dimap_add_entry(di_digest256_map_t **map, di_digest256_map_t *new_ent; { void *old_val = dimap_search(*map, key, NULL); - tor_assert(! old_val); - tor_assert(val); + raw_assert(! old_val); + raw_assert(val); } new_ent = tor_malloc_zero(sizeof(di_digest256_map_t)); new_ent->next = *map; @@ -263,10 +266,10 @@ select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, rand_val = INT64_MAX; } } - tor_assert(total_so_far == total); - tor_assert(n_chosen == 1); - tor_assert(i_chosen >= 0); - tor_assert(i_chosen < n_entries); + raw_assert(total_so_far == total); + raw_assert(n_chosen == 1); + raw_assert(i_chosen >= 0); + raw_assert(i_chosen < n_entries); return i_chosen; } diff --git a/src/lib/defs/.may_include b/src/lib/defs/.may_include new file mode 100644 index 0000000000..2b06e8519c --- /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 0000000000..f426fff20d --- /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 0000000000..ff48cff07c --- /dev/null +++ b/src/lib/defs/include.am @@ -0,0 +1,3 @@ + +noinst_HEADERS += \ + src/lib/defs/digest_sizes.h diff --git a/src/lib/fdio/.may_include b/src/lib/fdio/.may_include new file mode 100644 index 0000000000..30fd277b81 --- /dev/null +++ b/src/lib/fdio/.may_include @@ -0,0 +1,4 @@ +orconfig.h +lib/cc/*.h +lib/err/*.h +lib/fdio/*.h diff --git a/src/lib/fdio/fdio.c b/src/lib/fdio/fdio.c new file mode 100644 index 0000000000..b622074329 --- /dev/null +++ b/src/lib/fdio/fdio.c @@ -0,0 +1,109 @@ +/* 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 */ + +#include "orconfig.h" + +#ifdef HAVE_UNISTD_H +#include <unistd.h> +#endif +#ifdef _WIN32 +#include <windows.h> +#endif + +#include "lib/fdio/fdio.h" +#include "lib/cc/torint.h" +#include "lib/err/torerr.h" + +#include <stdlib.h> + +/** @{ */ +/** Some old versions of Unix didn't define constants for these values, + * and instead expect you to say 0, 1, or 2. */ +#ifndef SEEK_SET +#define SEEK_SET 0 +#endif +#ifndef SEEK_CUR +#define SEEK_CUR 1 +#endif +#ifndef SEEK_END +#define SEEK_END 2 +#endif +/** @} */ + +/** Return the position of <b>fd</b> with respect to the start of the file. */ +off_t +tor_fd_getpos(int fd) +{ +#ifdef _WIN32 + return (off_t) _lseek(fd, 0, SEEK_CUR); +#else + return (off_t) lseek(fd, 0, SEEK_CUR); +#endif +} + +/** Move <b>fd</b> to the end of the file. Return -1 on error, 0 on success. + * If the file is a pipe, do nothing and succeed. + **/ +int +tor_fd_seekend(int fd) +{ +#ifdef _WIN32 + return _lseek(fd, 0, SEEK_END) < 0 ? -1 : 0; +#else + off_t rc = lseek(fd, 0, SEEK_END) < 0 ? -1 : 0; +#ifdef ESPIPE + /* If we get an error and ESPIPE, then it's a pipe or a socket of a fifo: + * no need to worry. */ + if (rc < 0 && errno == ESPIPE) + rc = 0; +#endif /* defined(ESPIPE) */ + return (rc < 0) ? -1 : 0; +#endif /* defined(_WIN32) */ +} + +/** Move <b>fd</b> to position <b>pos</b> in the file. Return -1 on error, 0 + * on success. */ +int +tor_fd_setpos(int fd, off_t pos) +{ +#ifdef _WIN32 + return _lseek(fd, pos, SEEK_SET) < 0 ? -1 : 0; +#else + return lseek(fd, pos, SEEK_SET) < 0 ? -1 : 0; +#endif +} + +/** Replacement for ftruncate(fd, 0): move to the front of the file and remove + * all the rest of the file. Return -1 on error, 0 on success. */ +int +tor_ftruncate(int fd) +{ + /* Rumor has it that some versions of ftruncate do not move the file pointer. + */ + if (tor_fd_setpos(fd, 0) < 0) + return -1; + +#ifdef _WIN32 + return _chsize(fd, 0); +#else + return ftruncate(fd, 0); +#endif +} + +/** Minimal version of write_all, for use by logging. */ +int +write_all_to_fd(int fd, const char *buf, size_t count) +{ + size_t written = 0; + raw_assert(count < SSIZE_MAX); + + while (written < count) { + ssize_t result = write(fd, buf+written, count-written); + if (result<0) + return -1; + written += result; + } + return 0; +} diff --git a/src/lib/fdio/fdio.h b/src/lib/fdio/fdio.h new file mode 100644 index 0000000000..8cc4a04658 --- /dev/null +++ b/src/lib/fdio/fdio.h @@ -0,0 +1,17 @@ +/* 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_FDIO_H +#define TOR_FDIO_H + +#include <stddef.h> + +off_t tor_fd_getpos(int fd); +int tor_fd_setpos(int fd, off_t pos); +int tor_fd_seekend(int fd); +int tor_ftruncate(int fd); +int write_all_to_fd(int fd, const char *buf, size_t count); + +#endif /* !defined(TOR_FDIO_H) */ diff --git a/src/lib/fdio/include.am b/src/lib/fdio/include.am new file mode 100644 index 0000000000..6c18f00a0d --- /dev/null +++ b/src/lib/fdio/include.am @@ -0,0 +1,17 @@ + +noinst_LIBRARIES += src/lib/libtor-fdio.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-fdio-testing.a +endif + +src_lib_libtor_fdio_a_SOURCES = \ + src/lib/fdio/fdio.c + +src_lib_libtor_fdio_testing_a_SOURCES = \ + $(src_lib_libtor_fdio_a_SOURCES) +src_lib_libtor_fdio_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_fdio_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/fdio/fdio.h diff --git a/src/lib/intmath/.may_include b/src/lib/intmath/.may_include new file mode 100644 index 0000000000..d96c112220 --- /dev/null +++ b/src/lib/intmath/.may_include @@ -0,0 +1,4 @@ +orconfig.h +lib/cc/*.h +lib/err/*.h +lib/intmath/*.h diff --git a/src/lib/intmath/addsub.c b/src/lib/intmath/addsub.c new file mode 100644 index 0000000000..816c5a2bd7 --- /dev/null +++ b/src/lib/intmath/addsub.c @@ -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 */ + +#include "lib/intmath/addsub.h" +#include "lib/cc/compat_compiler.h" + +/* Helper: safely add two uint32_t's, capping at UINT32_MAX rather + * than overflow */ +uint32_t +tor_add_u32_nowrap(uint32_t a, uint32_t b) +{ + /* a+b > UINT32_MAX check, without overflow */ + if (PREDICT_UNLIKELY(a > UINT32_MAX - b)) { + return UINT32_MAX; + } else { + return a+b; + } +} diff --git a/src/lib/intmath/addsub.h b/src/lib/intmath/addsub.h new file mode 100644 index 0000000000..5277adfa49 --- /dev/null +++ b/src/lib/intmath/addsub.h @@ -0,0 +1,13 @@ +/* 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_INTMATH_ADDSUB_H +#define TOR_INTMATH_ADDSUB_H + +#include "lib/cc/torint.h" + +uint32_t tor_add_u32_nowrap(uint32_t a, uint32_t b); + +#endif /* !defined(TOR_INTMATH_MULDIV_H) */ diff --git a/src/lib/intmath/bits.c b/src/lib/intmath/bits.c new file mode 100644 index 0000000000..85d901f71b --- /dev/null +++ b/src/lib/intmath/bits.c @@ -0,0 +1,88 @@ +/* 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 */ + +#include "lib/intmath/bits.h" + +/** Returns floor(log2(u64)). If u64 is 0, (incorrectly) returns 0. */ +int +tor_log2(uint64_t u64) +{ + int r = 0; + if (u64 >= (U64_LITERAL(1)<<32)) { + u64 >>= 32; + r = 32; + } + if (u64 >= (U64_LITERAL(1)<<16)) { + u64 >>= 16; + r += 16; + } + if (u64 >= (U64_LITERAL(1)<<8)) { + u64 >>= 8; + r += 8; + } + if (u64 >= (U64_LITERAL(1)<<4)) { + u64 >>= 4; + r += 4; + } + if (u64 >= (U64_LITERAL(1)<<2)) { + u64 >>= 2; + r += 2; + } + if (u64 >= (U64_LITERAL(1)<<1)) { + // u64 >>= 1; // not using this any more. + r += 1; + } + return r; +} + +/** Return the power of 2 in range [1,UINT64_MAX] closest to <b>u64</b>. If + * there are two powers of 2 equally close, round down. */ +uint64_t +round_to_power_of_2(uint64_t u64) +{ + int lg2; + uint64_t low; + uint64_t high; + if (u64 == 0) + return 1; + + lg2 = tor_log2(u64); + low = U64_LITERAL(1) << lg2; + + if (lg2 == 63) + return low; + + high = U64_LITERAL(1) << (lg2+1); + if (high - u64 < u64 - low) + return high; + else + return low; +} + +/** Return the number of bits set in <b>v</b>. */ +int +n_bits_set_u8(uint8_t v) +{ + static const int nybble_table[] = { + 0, /* 0000 */ + 1, /* 0001 */ + 1, /* 0010 */ + 2, /* 0011 */ + 1, /* 0100 */ + 2, /* 0101 */ + 2, /* 0110 */ + 3, /* 0111 */ + 1, /* 1000 */ + 2, /* 1001 */ + 2, /* 1010 */ + 3, /* 1011 */ + 2, /* 1100 */ + 3, /* 1101 */ + 3, /* 1110 */ + 4, /* 1111 */ + }; + + return nybble_table[v & 15] + nybble_table[v>>4]; +} diff --git a/src/lib/intmath/bits.h b/src/lib/intmath/bits.h new file mode 100644 index 0000000000..70f855089c --- /dev/null +++ b/src/lib/intmath/bits.h @@ -0,0 +1,16 @@ +/* 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_INTMATH_BITS_H +#define TOR_INTMATH_BITS_H + +#include "lib/cc/torint.h" +#include "lib/cc/compat_compiler.h" + +int tor_log2(uint64_t u64) ATTR_CONST; +uint64_t round_to_power_of_2(uint64_t u64); +int n_bits_set_u8(uint8_t v); + +#endif /* !defined(TOR_INTMATH_BITS_H) */ diff --git a/src/lib/intmath/cmp.h b/src/lib/intmath/cmp.h new file mode 100644 index 0000000000..90ea3ca079 --- /dev/null +++ b/src/lib/intmath/cmp.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_INTMATH_CMP_H +#define TOR_INTMATH_CMP_H + +/* Return <b>v</b> if it's between <b>min</b> and <b>max</b>. Otherwise + * return <b>min</b> if <b>v</b> is smaller than <b>min</b>, or <b>max</b> if + * <b>b</b> is larger than <b>max</b>. + * + * Requires that <b>min</b> is no more than <b>max</b>. May evaluate any of + * its arguments more than once! */ +#define CLAMP(min,v,max) \ + ( ((v) < (min)) ? (min) : \ + ((v) > (max)) ? (max) : \ + (v) ) + +#endif /* !defined(TOR_INTMATH_CMP_H) */ diff --git a/src/lib/intmath/include.am b/src/lib/intmath/include.am new file mode 100644 index 0000000000..40459d106d --- /dev/null +++ b/src/lib/intmath/include.am @@ -0,0 +1,22 @@ + +noinst_LIBRARIES += src/lib/libtor-intmath.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-intmath-testing.a +endif + +src_lib_libtor_intmath_a_SOURCES = \ + src/lib/intmath/addsub.c \ + src/lib/intmath/bits.c \ + src/lib/intmath/muldiv.c + +src_lib_libtor_intmath_testing_a_SOURCES = \ + $(src_lib_libtor_intmath_a_SOURCES) +src_lib_libtor_intmath_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_intmath_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/intmath/addsub.h \ + src/lib/intmath/cmp.h \ + src/lib/intmath/bits.h \ + src/lib/intmath/muldiv.h diff --git a/src/lib/intmath/muldiv.c b/src/lib/intmath/muldiv.c new file mode 100644 index 0000000000..3e627b237a --- /dev/null +++ b/src/lib/intmath/muldiv.c @@ -0,0 +1,75 @@ +/* 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 */ + +#include "lib/intmath/muldiv.h" +#include "lib/err/torerr.h" + +#include <stdlib.h> + +/** Return the lowest x such that x is at least <b>number</b>, and x modulo + * <b>divisor</b> == 0. If no such x can be expressed as an unsigned, return + * UINT_MAX. Asserts if divisor is zero. */ +unsigned +round_to_next_multiple_of(unsigned number, unsigned divisor) +{ + raw_assert(divisor > 0); + if (UINT_MAX - divisor + 1 < number) + return UINT_MAX; + number += divisor - 1; + number -= number % divisor; + return number; +} + +/** Return the lowest x such that x is at least <b>number</b>, and x modulo + * <b>divisor</b> == 0. If no such x can be expressed as a uint32_t, return + * UINT32_MAX. Asserts if divisor is zero. */ +uint32_t +round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor) +{ + raw_assert(divisor > 0); + if (UINT32_MAX - divisor + 1 < number) + return UINT32_MAX; + + number += divisor - 1; + number -= number % divisor; + return number; +} + +/** Return the lowest x such that x is at least <b>number</b>, and x modulo + * <b>divisor</b> == 0. If no such x can be expressed as a uint64_t, return + * UINT64_MAX. Asserts if divisor is zero. */ +uint64_t +round_uint64_to_next_multiple_of(uint64_t number, uint64_t divisor) +{ + raw_assert(divisor > 0); + if (UINT64_MAX - divisor + 1 < number) + return UINT64_MAX; + number += divisor - 1; + number -= number % divisor; + return number; +} + +/* Helper: return greatest common divisor of a,b */ +static uint64_t +gcd64(uint64_t a, uint64_t b) +{ + while (b) { + uint64_t t = b; + b = a % b; + a = t; + } + return a; +} + +/* Given a fraction *<b>numer</b> / *<b>denom</b>, simplify it. + * Requires that the denominator is greater than 0. */ +void +simplify_fraction64(uint64_t *numer, uint64_t *denom) +{ + raw_assert(denom); + uint64_t gcd = gcd64(*numer, *denom); + *numer /= gcd; + *denom /= gcd; +} diff --git a/src/lib/intmath/muldiv.h b/src/lib/intmath/muldiv.h new file mode 100644 index 0000000000..de76d9eb68 --- /dev/null +++ b/src/lib/intmath/muldiv.h @@ -0,0 +1,22 @@ +/* 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_INTMATH_MULDIV_H +#define TOR_INTMATH_MULDIV_H + +#include "lib/cc/torint.h" + +unsigned round_to_next_multiple_of(unsigned number, unsigned divisor); +uint32_t round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor); +uint64_t round_uint64_to_next_multiple_of(uint64_t number, uint64_t divisor); + +void simplify_fraction64(uint64_t *numer, uint64_t *denom); + +/* Compute the CEIL of <b>a</b> divided by <b>b</b>, for nonnegative <b>a</b> + * and positive <b>b</b>. Works on integer types only. Not defined if a+(b-1) + * can overflow. */ +#define CEIL_DIV(a,b) (((a)+((b)-1))/(b)) + +#endif /* !defined(TOR_INTMATH_MULDIV_H) */ diff --git a/src/lib/lock/.may_include b/src/lib/lock/.may_include new file mode 100644 index 0000000000..9522e3af49 --- /dev/null +++ b/src/lib/lock/.may_include @@ -0,0 +1,5 @@ +orconfig.h +lib/cc/*.h +lib/err/*.h +lib/lock/*.h +lib/malloc/*.h diff --git a/src/lib/lock/compat_mutex.c b/src/lib/lock/compat_mutex.c new file mode 100644 index 0000000000..e0f6224a83 --- /dev/null +++ b/src/lib/lock/compat_mutex.c @@ -0,0 +1,34 @@ +/* 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 */ + +#include "lib/lock/compat_mutex.h" +#include "lib/malloc/util_malloc.h" + +/** Return a newly allocated, ready-for-use mutex. */ +tor_mutex_t * +tor_mutex_new(void) +{ + tor_mutex_t *m = tor_malloc_zero(sizeof(tor_mutex_t)); + tor_mutex_init(m); + return m; +} +/** Return a newly allocated, ready-for-use mutex. This one might be + * non-recursive, if that's faster. */ +tor_mutex_t * +tor_mutex_new_nonrecursive(void) +{ + tor_mutex_t *m = tor_malloc_zero(sizeof(tor_mutex_t)); + tor_mutex_init_nonrecursive(m); + return m; +} +/** Release all storage and system resources held by <b>m</b>. */ +void +tor_mutex_free_(tor_mutex_t *m) +{ + if (!m) + return; + tor_mutex_uninit(m); + tor_free(m); +} diff --git a/src/lib/lock/compat_mutex.h b/src/lib/lock/compat_mutex.h new file mode 100644 index 0000000000..92978086ac --- /dev/null +++ b/src/lib/lock/compat_mutex.h @@ -0,0 +1,60 @@ +/* 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_COMPAT_MUTEX_H +#define TOR_COMPAT_MUTEX_H + +#include "orconfig.h" +#include "lib/cc/torint.h" +#include "lib/malloc/util_malloc.h" + +#if defined(HAVE_PTHREAD_H) && !defined(_WIN32) +#include <pthread.h> +#endif + +#if defined(_WIN32) +#include <windows.h> +#endif + +#if defined(_WIN32) +#define USE_WIN32_THREADS +#elif defined(HAVE_PTHREAD_H) && defined(HAVE_PTHREAD_CREATE) +#define USE_PTHREADS +#else +#error "No threading system was found" +#endif /* defined(_WIN32) || ... */ + +/* Because we use threads instead of processes on most platforms (Windows, + * Linux, etc), we need locking for them. On platforms with poor thread + * support or broken gethostbyname_r, these functions are no-ops. */ + +/** A generic lock structure for multithreaded builds. */ +typedef struct tor_mutex_t { +#if defined(USE_WIN32_THREADS) + /** Windows-only: on windows, we implement locks with CRITICAL_SECTIONS. */ + CRITICAL_SECTION mutex; +#elif defined(USE_PTHREADS) + /** Pthreads-only: with pthreads, we implement locks with + * pthread_mutex_t. */ + pthread_mutex_t mutex; +#else + /** No-threads only: Dummy variable so that tor_mutex_t takes up space. */ + int _unused; +#endif /* defined(USE_WIN32_MUTEX) || ... */ +} tor_mutex_t; + +tor_mutex_t *tor_mutex_new(void); +tor_mutex_t *tor_mutex_new_nonrecursive(void); +void tor_mutex_init(tor_mutex_t *m); +void tor_mutex_init_nonrecursive(tor_mutex_t *m); +void tor_mutex_acquire(tor_mutex_t *m); +void tor_mutex_release(tor_mutex_t *m); +void tor_mutex_free_(tor_mutex_t *m); +#define tor_mutex_free(m) FREE_AND_NULL(tor_mutex_t, tor_mutex_free_, (m)) +void tor_mutex_uninit(tor_mutex_t *m); + +void tor_locking_init(void); + +#endif /* !defined(TOR_COMPAT_MUTEX_H) */ diff --git a/src/lib/lock/compat_mutex_pthreads.c b/src/lib/lock/compat_mutex_pthreads.c new file mode 100644 index 0000000000..390da4fb81 --- /dev/null +++ b/src/lib/lock/compat_mutex_pthreads.c @@ -0,0 +1,97 @@ +/* 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 */ + +#include "lib/lock/compat_mutex.h" +#include "lib/cc/compat_compiler.h" +#include "lib/err/torerr.h" + +/** A mutex attribute that we're going to use to tell pthreads that we want + * "recursive" mutexes (i.e., once we can re-lock if we're already holding + * them.) */ +static pthread_mutexattr_t attr_recursive; +static int attr_initialized = 0; + +void +tor_locking_init(void) +{ + if (!attr_initialized) { + pthread_mutexattr_init(&attr_recursive); + pthread_mutexattr_settype(&attr_recursive, PTHREAD_MUTEX_RECURSIVE); + attr_initialized = 1; + } +} + +/** Initialize <b>mutex</b> so it can be locked. Every mutex must be set + * up with tor_mutex_init() or tor_mutex_new(); not both. */ +void +tor_mutex_init(tor_mutex_t *mutex) +{ + if (PREDICT_UNLIKELY(!attr_initialized)) + tor_locking_init(); // LCOV_EXCL_LINE + const int err = pthread_mutex_init(&mutex->mutex, &attr_recursive); + if (PREDICT_UNLIKELY(err)) { + // LCOV_EXCL_START + raw_assert_unreached_msg("Error creating a mutex."); + // LCOV_EXCL_STOP + } +} + +/** As tor_mutex_init, but initialize a mutex suitable that may be + * non-recursive, if the OS supports that. */ +void +tor_mutex_init_nonrecursive(tor_mutex_t *mutex) +{ + int err; + if (!attr_initialized) + tor_locking_init(); // LCOV_EXCL_LINE + err = pthread_mutex_init(&mutex->mutex, NULL); + if (PREDICT_UNLIKELY(err)) { + // LCOV_EXCL_START + raw_assert_unreached_msg("Error creating a mutex."); + // LCOV_EXCL_STOP + } +} + +/** Wait until <b>m</b> is free, then acquire it. */ +void +tor_mutex_acquire(tor_mutex_t *m) +{ + int err; + raw_assert(m); + err = pthread_mutex_lock(&m->mutex); + if (PREDICT_UNLIKELY(err)) { + // LCOV_EXCL_START + raw_assert_unreached_msg("Error locking a mutex."); + // LCOV_EXCL_STOP + } +} +/** Release the lock <b>m</b> so another thread can have it. */ +void +tor_mutex_release(tor_mutex_t *m) +{ + int err; + raw_assert(m); + err = pthread_mutex_unlock(&m->mutex); + if (PREDICT_UNLIKELY(err)) { + // LCOV_EXCL_START + raw_assert_unreached_msg("Error unlocking a mutex."); + // LCOV_EXCL_STOP + } +} +/** Clean up the mutex <b>m</b> so that it no longer uses any system + * resources. Does not free <b>m</b>. This function must only be called on + * mutexes from tor_mutex_init(). */ +void +tor_mutex_uninit(tor_mutex_t *m) +{ + int err; + raw_assert(m); + err = pthread_mutex_destroy(&m->mutex); + if (PREDICT_UNLIKELY(err)) { + // LCOV_EXCL_START + raw_assert_unreached_msg("Error destroying a mutex."); + // LCOV_EXCL_STOP + } +} diff --git a/src/lib/lock/compat_mutex_winthreads.c b/src/lib/lock/compat_mutex_winthreads.c new file mode 100644 index 0000000000..32be288c7f --- /dev/null +++ b/src/lib/lock/compat_mutex_winthreads.c @@ -0,0 +1,40 @@ +/* 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 */ + +#include "lib/lock/compat_mutex.h" +#include "lib/err/torerr.h" + +void +tor_locking_init(void) +{ +} + +void +tor_mutex_init(tor_mutex_t *m) +{ + InitializeCriticalSection(&m->mutex); +} +void +tor_mutex_init_nonrecursive(tor_mutex_t *m) +{ + InitializeCriticalSection(&m->mutex); +} + +void +tor_mutex_uninit(tor_mutex_t *m) +{ + DeleteCriticalSection(&m->mutex); +} +void +tor_mutex_acquire(tor_mutex_t *m) +{ + raw_assert(m); + EnterCriticalSection(&m->mutex); +} +void +tor_mutex_release(tor_mutex_t *m) +{ + LeaveCriticalSection(&m->mutex); +} diff --git a/src/lib/lock/include.am b/src/lib/lock/include.am new file mode 100644 index 0000000000..4e6f444347 --- /dev/null +++ b/src/lib/lock/include.am @@ -0,0 +1,24 @@ + +noinst_LIBRARIES += src/lib/libtor-lock.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-lock-testing.a +endif + +src_lib_libtor_lock_a_SOURCES = \ + src/lib/lock/compat_mutex.c + +if THREADS_PTHREADS +src_lib_libtor_lock_a_SOURCES += src/lib/lock/compat_mutex_pthreads.c +endif +if THREADS_WIN32 +src_lib_libtor_lock_a_SOURCES += src/lib/lock/compat_mutex_winthreads.c +endif + +src_lib_libtor_lock_testing_a_SOURCES = \ + $(src_lib_libtor_lock_a_SOURCES) +src_lib_libtor_lock_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_lock_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/lock/compat_mutex.h diff --git a/src/lib/log/.may_include b/src/lib/log/.may_include new file mode 100644 index 0000000000..36a164cce0 --- /dev/null +++ b/src/lib/log/.may_include @@ -0,0 +1,15 @@ +orconfig.h + +lib/cc/*.h +lib/container/smartlist.h +lib/err/*.h +lib/fdio/*.h +lib/intmath/*.h +lib/lock/*.h +lib/log/*.h +lib/malloc/*.h +lib/string/*.h +lib/testsupport/*.h +lib/wallclock/*.h + +micro-revision.i
\ No newline at end of file diff --git a/src/lib/log/include.am b/src/lib/log/include.am new file mode 100644 index 0000000000..bbe345de7a --- /dev/null +++ b/src/lib/log/include.am @@ -0,0 +1,24 @@ + +noinst_LIBRARIES += src/lib/libtor-log.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-log-testing.a +endif + +src_lib_libtor_log_a_SOURCES = \ + src/lib/log/ratelim.c \ + src/lib/log/torlog.c \ + src/lib/log/util_bug.c + +src_lib_libtor_log_testing_a_SOURCES = \ + $(src_lib_libtor_log_a_SOURCES) +src_lib_libtor_log_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_log_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +src/lib/log/torlog.$(OBJEXT) \ + src/lib/log/src_lib_libtor_log_testing_a-torlog.$(OBJEXT): micro-revision.i + +noinst_HEADERS += \ + src/lib/log/ratelim.h \ + src/lib/log/torlog.h \ + src/lib/log/util_bug.h diff --git a/src/lib/log/ratelim.c b/src/lib/log/ratelim.c new file mode 100644 index 0000000000..677c499110 --- /dev/null +++ b/src/lib/log/ratelim.c @@ -0,0 +1,55 @@ +/* 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 */ + +#include "lib/log/ratelim.h" +#include "lib/malloc/util_malloc.h" +#include "lib/string/printf.h" + +/** If the rate-limiter <b>lim</b> is ready at <b>now</b>, return the number + * of calls to rate_limit_is_ready (including this one!) since the last time + * rate_limit_is_ready returned nonzero. Otherwise return 0. + * If the call number hits <b>RATELIM_TOOMANY</b> limit, drop a warning + * about this event and stop counting. */ +static int +rate_limit_is_ready(ratelim_t *lim, time_t now) +{ + if (lim->rate + lim->last_allowed <= now) { + int res = lim->n_calls_since_last_time + 1; + lim->last_allowed = now; + lim->n_calls_since_last_time = 0; + return res; + } else { + if (lim->n_calls_since_last_time <= RATELIM_TOOMANY) { + ++lim->n_calls_since_last_time; + } + + return 0; + } +} + +/** If the rate-limiter <b>lim</b> is ready at <b>now</b>, return a newly + * allocated string indicating how many messages were suppressed, suitable to + * append to a log message. Otherwise return NULL. */ +char * +rate_limit_log(ratelim_t *lim, time_t now) +{ + int n; + if ((n = rate_limit_is_ready(lim, now))) { + if (n == 1) { + return tor_strdup(""); + } else { + char *cp=NULL; + const char *opt_over = (n >= RATELIM_TOOMANY) ? "over " : ""; + /* XXXX this is not exactly correct: the messages could have occurred + * any time between the old value of lim->allowed and now. */ + tor_asprintf(&cp, + " [%s%d similar message(s) suppressed in last %d seconds]", + opt_over, n-1, lim->rate); + return cp; + } + } else { + return NULL; + } +} diff --git a/src/lib/log/ratelim.h b/src/lib/log/ratelim.h new file mode 100644 index 0000000000..4ee6c5fed4 --- /dev/null +++ b/src/lib/log/ratelim.h @@ -0,0 +1,48 @@ +/* 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_RATELIM_H +#define TOR_RATELIM_H + +#include <time.h> + +/* Rate-limiter */ + +/** A ratelim_t remembers how often an event is occurring, and how often + * it's allowed to occur. Typical usage is something like: + * + <pre> + if (possibly_very_frequent_event()) { + const int INTERVAL = 300; + static ratelim_t warning_limit = RATELIM_INIT(INTERVAL); + char *m; + if ((m = rate_limit_log(&warning_limit, approx_time()))) { + log_warn(LD_GENERAL, "The event occurred!%s", m); + tor_free(m); + } + } + </pre> + + As a convenience wrapper for logging, you can replace the above with: + <pre> + if (possibly_very_frequent_event()) { + static ratelim_t warning_limit = RATELIM_INIT(300); + log_fn_ratelim(&warning_limit, LOG_WARN, LD_GENERAL, + "The event occurred!"); + } + </pre> + */ +typedef struct ratelim_t { + int rate; + time_t last_allowed; + int n_calls_since_last_time; +} ratelim_t; + +#define RATELIM_INIT(r) { (r), 0, 0 } +#define RATELIM_TOOMANY (16*1000*1000) + +char *rate_limit_log(ratelim_t *lim, time_t now); + +#endif diff --git a/src/lib/log/torlog.c b/src/lib/log/torlog.c new file mode 100644 index 0000000000..5709dd8199 --- /dev/null +++ b/src/lib/log/torlog.c @@ -0,0 +1,1486 @@ +/* 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 */ + +/** + * \file log.c + * \brief Functions to send messages to log files or the console. + **/ + +#include "orconfig.h" +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#ifdef HAVE_SYS_TIME_H +#include <sys/time.h> +#endif +#ifdef HAVE_TIME_H +#include <time.h> +#endif +#ifdef HAVE_UNISTD_H +#include <unistd.h> +#endif +#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_FCNTL_H +#include <fcntl.h> +#endif + +#define LOG_PRIVATE +#include "lib/log/torlog.h" +#include "lib/log/ratelim.h" +#include "lib/lock/compat_mutex.h" +#include "lib/container/smartlist.h" +#include "lib/err/torerr.h" +#include "lib/intmath/bits.h" +#include "lib/string/compat_string.h" +#include "lib/string/printf.h" +#include "lib/malloc/util_malloc.h" +#include "lib/string/util_string.h" +#include "lib/wallclock/tor_gettimeofday.h" +#include "lib/wallclock/approx_time.h" +#include "lib/wallclock/tm_cvt.h" +#include "lib/fdio/fdio.h" + +#ifdef HAVE_ANDROID_LOG_H +#include <android/log.h> +#endif // HAVE_ANDROID_LOG_H. + +/** Given a severity, yields an index into log_severity_list_t.masks to use + * for that severity. */ +#define SEVERITY_MASK_IDX(sev) ((sev) - LOG_ERR) + +/** @{ */ +/** The string we stick at the end of a log message when it is too long, + * and its length. */ +#define TRUNCATED_STR "[...truncated]" +#define TRUNCATED_STR_LEN 14 +/** @} */ + +/** Defining compile-time constants for Tor log levels (used by the Rust + * log wrapper at src/rust/tor_log) */ +const int LOG_WARN_ = LOG_WARN; +const int LOG_NOTICE_ = LOG_NOTICE; +const log_domain_mask_t LD_GENERAL_ = LD_GENERAL; +const log_domain_mask_t LD_NET_ = LD_NET; + +/** Information for a single logfile; only used in log.c */ +typedef struct logfile_t { + struct logfile_t *next; /**< Next logfile_t in the linked list. */ + char *filename; /**< Filename to open. */ + int fd; /**< fd to receive log messages, or -1 for none. */ + int seems_dead; /**< Boolean: true if the stream seems to be kaput. */ + int needs_close; /**< Boolean: true if the stream gets closed on shutdown. */ + int is_temporary; /**< Boolean: close after initializing logging subsystem.*/ + int is_syslog; /**< Boolean: send messages to syslog. */ + int is_android; /**< Boolean: send messages to Android's log subsystem. */ + char *android_tag; /**< Identity Tag used in Android's log subsystem. */ + log_callback callback; /**< If not NULL, send messages to this function. */ + log_severity_list_t *severities; /**< Which severity of messages should we + * log for each log domain? */ +} logfile_t; + +static void log_free_(logfile_t *victim); +#define log_free(lg) \ + FREE_AND_NULL(logfile_t, log_free_, (lg)) + +/** Helper: map a log severity to descriptive string. */ +static inline const char * +sev_to_string(int severity) +{ + switch (severity) { + case LOG_DEBUG: return "debug"; + case LOG_INFO: return "info"; + case LOG_NOTICE: return "notice"; + case LOG_WARN: return "warn"; + case LOG_ERR: return "err"; + default: /* Call assert, not tor_assert, since tor_assert + * calls log on failure. */ + raw_assert_unreached(); return "UNKNOWN"; // LCOV_EXCL_LINE + } +} + +/** Helper: decide whether to include the function name in the log message. */ +static inline int +should_log_function_name(log_domain_mask_t domain, int severity) +{ + switch (severity) { + case LOG_DEBUG: + case LOG_INFO: + /* All debugging messages occur in interesting places. */ + return (domain & LD_NOFUNCNAME) == 0; + case LOG_NOTICE: + case LOG_WARN: + case LOG_ERR: + /* We care about places where bugs occur. */ + return (domain & (LD_BUG|LD_NOFUNCNAME)) == LD_BUG; + default: + /* Call assert, not tor_assert, since tor_assert calls log on failure. */ + raw_assert(0); return 0; // LCOV_EXCL_LINE + } +} + +#ifdef HAVE_ANDROID_LOG_H +/** Helper function to convert Tor's log severity into the matching + * Android log priority. + */ +static int +severity_to_android_log_priority(int severity) +{ + switch (severity) { + case LOG_DEBUG: + return ANDROID_LOG_VERBOSE; + case LOG_INFO: + return ANDROID_LOG_DEBUG; + case LOG_NOTICE: + return ANDROID_LOG_INFO; + case LOG_WARN: + return ANDROID_LOG_WARN; + case LOG_ERR: + return ANDROID_LOG_ERROR; + default: + // LCOV_EXCL_START + raw_assert(0); + return 0; + // LCOV_EXCL_STOP + } +} +#endif // HAVE_ANDROID_LOG_H. + +/** A mutex to guard changes to logfiles and logging. */ +static tor_mutex_t log_mutex; +/** True iff we have initialized log_mutex */ +static int log_mutex_initialized = 0; + +/** Linked list of logfile_t. */ +static logfile_t *logfiles = NULL; +/** Boolean: do we report logging domains? */ +static int log_domains_are_logged = 0; + +#ifdef HAVE_SYSLOG_H +/** The number of open syslog log handlers that we have. When this reaches 0, + * we can close our connection to the syslog facility. */ +static int syslog_count = 0; +#endif + +/** Represents a log message that we are going to send to callback-driven + * loggers once we can do so in a non-reentrant way. */ +typedef struct pending_log_message_t { + int severity; /**< The severity of the message */ + log_domain_mask_t domain; /**< The domain of the message */ + char *fullmsg; /**< The message, with all decorations */ + char *msg; /**< The content of the message */ +} pending_log_message_t; + +/** Log messages waiting to be replayed onto callback-based logs */ +static smartlist_t *pending_cb_messages = NULL; + +/** Callback to invoke when pending_cb_messages becomes nonempty. */ +static pending_callback_callback pending_cb_cb = NULL; + +/** Log messages waiting to be replayed once the logging system is initialized. + */ +static smartlist_t *pending_startup_messages = NULL; + +/** Number of bytes of messages queued in pending_startup_messages. (This is + * the length of the messages, not the number of bytes used to store + * them.) */ +static size_t pending_startup_messages_len; + +/** True iff we should store messages while waiting for the logs to get + * configured. */ +static int queue_startup_messages = 1; + +/** True iff __PRETTY_FUNCTION__ includes parenthesized arguments. */ +static int pretty_fn_has_parens = 0; + +/** Don't store more than this many bytes of messages while waiting for the + * logs to get configured. */ +#define MAX_STARTUP_MSG_LEN (1<<16) + +/** Lock the log_mutex to prevent others from changing the logfile_t list */ +#define LOCK_LOGS() STMT_BEGIN \ + raw_assert(log_mutex_initialized); \ + tor_mutex_acquire(&log_mutex); \ + STMT_END +/** Unlock the log_mutex */ +#define UNLOCK_LOGS() STMT_BEGIN \ + raw_assert(log_mutex_initialized); \ + tor_mutex_release(&log_mutex); \ + STMT_END + +/** What's the lowest log level anybody cares about? Checking this lets us + * bail out early from log_debug if we aren't debugging. */ +int log_global_min_severity_ = LOG_NOTICE; + +static void delete_log(logfile_t *victim); +static void close_log(logfile_t *victim); + +static char *domain_to_string(log_domain_mask_t domain, + char *buf, size_t buflen); +static inline char *format_msg(char *buf, size_t buf_len, + log_domain_mask_t domain, int severity, const char *funcname, + const char *suffix, + const char *format, va_list ap, size_t *msg_len_out) + CHECK_PRINTF(7,0); + +/** Name of the application: used to generate the message we write at the + * start of each new log. */ +static char *appname = NULL; + +/** Set the "application name" for the logs to <b>name</b>: we'll use this + * name in the message we write when starting up, and at the start of each new + * log. + * + * Tor uses this string to write the version number to the log file. */ +void +log_set_application_name(const char *name) +{ + tor_free(appname); + appname = name ? tor_strdup(name) : NULL; +} + +/** Return true if some of the running logs might be interested in a log + * message of the given severity in the given domains. If this function + * returns true, the log message might be ignored anyway, but if it returns + * false, it is definitely_ safe not to log the message. */ +int +log_message_is_interesting(int severity, log_domain_mask_t domain) +{ + (void) domain; + return (severity <= log_global_min_severity_); +} + +/** + * As tor_log, but takes an optional function name, and does not treat its + * <b>string</b> as a printf format. + * + * For use by Rust integration. + */ +void +tor_log_string(int severity, log_domain_mask_t domain, + const char *function, const char *string) +{ + log_fn_(severity, domain, function, "%s", string); +} + +/** Log time granularity in milliseconds. */ +static int log_time_granularity = 1; + +/** Define log time granularity for all logs to be <b>granularity_msec</b> + * milliseconds. */ +void +set_log_time_granularity(int granularity_msec) +{ + log_time_granularity = granularity_msec; + tor_log_sigsafe_err_set_granularity(granularity_msec); +} + +/** Helper: Write the standard prefix for log lines to a + * <b>buf_len</b> character buffer in <b>buf</b>. + */ +static inline size_t +log_prefix_(char *buf, size_t buf_len, int severity) +{ + time_t t; + struct timeval now; + struct tm tm; + size_t n; + int r, ms; + + tor_gettimeofday(&now); + t = (time_t)now.tv_sec; + ms = (int)now.tv_usec / 1000; + if (log_time_granularity >= 1000) { + t -= t % (log_time_granularity / 1000); + ms = 0; + } else { + ms -= ((int)now.tv_usec / 1000) % log_time_granularity; + } + + n = strftime(buf, buf_len, "%b %d %H:%M:%S", + tor_localtime_r_msg(&t, &tm, NULL)); + r = tor_snprintf(buf+n, buf_len-n, ".%.3i [%s] ", ms, + sev_to_string(severity)); + + if (r<0) + return buf_len-1; + else + return n+r; +} + +/** If lf refers to an actual file that we have just opened, and the file + * contains no data, log an "opening new logfile" message at the top. + * + * Return -1 if the log is broken and needs to be deleted, else return 0. + */ +static int +log_tor_version(logfile_t *lf, int reset) +{ + char buf[256]; + size_t n; + int is_new; + + if (!lf->needs_close) + /* If it doesn't get closed, it isn't really a file. */ + return 0; + if (lf->is_temporary) + /* If it's temporary, it isn't really a file. */ + return 0; + + is_new = lf->fd >= 0 && tor_fd_getpos(lf->fd) == 0; + + if (reset && !is_new) + /* We are resetting, but we aren't at the start of the file; no + * need to log again. */ + return 0; + n = log_prefix_(buf, sizeof(buf), LOG_NOTICE); + if (appname) { + tor_snprintf(buf+n, sizeof(buf)-n, + "%s opening %slog file.\n", appname, is_new?"new ":""); + } else { + tor_snprintf(buf+n, sizeof(buf)-n, + "Tor %s opening %slog file.\n", VERSION, is_new?"new ":""); + } + if (write_all_to_fd(lf->fd, buf, strlen(buf)) < 0) /* error */ + return -1; /* failed */ + return 0; +} + +static const char bug_suffix[] = " (on Tor " VERSION +#ifndef _MSC_VER + " " +#include "micro-revision.i" +#endif + ")"; + +/** Helper: Format a log message into a fixed-sized buffer. (This is + * factored out of <b>logv</b> so that we never format a message more + * than once.) Return a pointer to the first character of the message + * portion of the formatted string. + */ +static inline char * +format_msg(char *buf, size_t buf_len, + log_domain_mask_t domain, int severity, const char *funcname, + const char *suffix, + const char *format, va_list ap, size_t *msg_len_out) +{ + size_t n; + int r; + char *end_of_prefix; + char *buf_end; + + raw_assert(buf_len >= 16); /* prevent integer underflow and stupidity */ + buf_len -= 2; /* subtract 2 characters so we have room for \n\0 */ + buf_end = buf+buf_len; /* point *after* the last char we can write to */ + + n = log_prefix_(buf, buf_len, severity); + end_of_prefix = buf+n; + + if (log_domains_are_logged) { + char *cp = buf+n; + if (cp == buf_end) goto format_msg_no_room_for_domains; + *cp++ = '{'; + if (cp == buf_end) goto format_msg_no_room_for_domains; + cp = domain_to_string(domain, cp, (buf+buf_len-cp)); + if (cp == buf_end) goto format_msg_no_room_for_domains; + *cp++ = '}'; + if (cp == buf_end) goto format_msg_no_room_for_domains; + *cp++ = ' '; + if (cp == buf_end) goto format_msg_no_room_for_domains; + end_of_prefix = cp; + n = cp-buf; + format_msg_no_room_for_domains: + /* This will leave end_of_prefix and n unchanged, and thus cause + * whatever log domain string we had written to be clobbered. */ + ; + } + + if (funcname && should_log_function_name(domain, severity)) { + r = tor_snprintf(buf+n, buf_len-n, + pretty_fn_has_parens ? "%s: " : "%s(): ", + funcname); + if (r<0) + n = strlen(buf); + else + n += r; + } + + if (domain == LD_BUG && buf_len-n > 6) { + memcpy(buf+n, "Bug: ", 6); + n += 5; + } + + r = tor_vsnprintf(buf+n,buf_len-n,format,ap); + if (r < 0) { + /* The message was too long; overwrite the end of the buffer with + * "[...truncated]" */ + if (buf_len >= TRUNCATED_STR_LEN) { + size_t offset = buf_len-TRUNCATED_STR_LEN; + /* We have an extra 2 characters after buf_len to hold the \n\0, + * so it's safe to add 1 to the size here. */ + strlcpy(buf+offset, TRUNCATED_STR, buf_len-offset+1); + } + /* Set 'n' to the end of the buffer, where we'll be writing \n\0. + * Since we already subtracted 2 from buf_len, this is safe.*/ + n = buf_len; + } else { + n += r; + if (suffix) { + size_t suffix_len = strlen(suffix); + if (buf_len-n >= suffix_len) { + memcpy(buf+n, suffix, suffix_len); + n += suffix_len; + } + } + } + + if (domain == LD_BUG && + buf_len - n > strlen(bug_suffix)+1) { + memcpy(buf+n, bug_suffix, strlen(bug_suffix)); + n += strlen(bug_suffix); + } + + buf[n]='\n'; + buf[n+1]='\0'; + *msg_len_out = n+1; + return end_of_prefix; +} + +/* Create a new pending_log_message_t with appropriate values */ +static pending_log_message_t * +pending_log_message_new(int severity, log_domain_mask_t domain, + const char *fullmsg, const char *shortmsg) +{ + pending_log_message_t *m = tor_malloc(sizeof(pending_log_message_t)); + m->severity = severity; + m->domain = domain; + m->fullmsg = fullmsg ? tor_strdup(fullmsg) : NULL; + m->msg = tor_strdup(shortmsg); + return m; +} + +#define pending_log_message_free(msg) \ + FREE_AND_NULL(pending_log_message_t, pending_log_message_free_, (msg)) + +/** Release all storage held by <b>msg</b>. */ +static void +pending_log_message_free_(pending_log_message_t *msg) +{ + if (!msg) + return; + tor_free(msg->msg); + tor_free(msg->fullmsg); + tor_free(msg); +} + +/** Helper function: returns true iff the log file, given in <b>lf</b>, is + * handled externally via the system log API, the Android logging API, or is an + * external callback function. */ +static inline int +logfile_is_external(const logfile_t *lf) +{ + raw_assert(lf); + return lf->is_syslog || lf->is_android || lf->callback; +} + +/** Return true iff <b>lf</b> would like to receive a message with the + * specified <b>severity</b> in the specified <b>domain</b>. + */ +static inline int +logfile_wants_message(const logfile_t *lf, int severity, + log_domain_mask_t domain) +{ + if (! (lf->severities->masks[SEVERITY_MASK_IDX(severity)] & domain)) { + return 0; + } + if (! (lf->fd >= 0 || logfile_is_external(lf))) { + return 0; + } + if (lf->seems_dead) { + return 0; + } + + return 1; +} + +/** Send a message to <b>lf</b>. The full message, with time prefix and + * severity, is in <b>buf</b>. The message itself is in + * <b>msg_after_prefix</b>. If <b>callbacks_deferred</b> points to true, then + * we already deferred this message for pending callbacks and don't need to do + * it again. Otherwise, if we need to do it, do it, and set + * <b>callbacks_deferred</b> to 1. */ +static inline void +logfile_deliver(logfile_t *lf, const char *buf, size_t msg_len, + const char *msg_after_prefix, log_domain_mask_t domain, + int severity, int *callbacks_deferred) +{ + + if (lf->is_syslog) { +#ifdef HAVE_SYSLOG_H +#ifdef MAXLINE + /* Some syslog implementations have limits on the length of what you can + * pass them, and some very old ones do not detect overflow so well. + * Regrettably, they call their maximum line length MAXLINE. */ +#if MAXLINE < 64 +#warn "MAXLINE is a very low number; it might not be from syslog.h after all" +#endif + char *m = msg_after_prefix; + if (msg_len >= MAXLINE) + m = tor_strndup(msg_after_prefix, MAXLINE-1); + syslog(severity, "%s", m); + if (m != msg_after_prefix) { + tor_free(m); + } +#else /* !(defined(MAXLINE)) */ + /* We have syslog but not MAXLINE. That's promising! */ + syslog(severity, "%s", msg_after_prefix); +#endif /* defined(MAXLINE) */ +#endif /* defined(HAVE_SYSLOG_H) */ + } else if (lf->is_android) { +#ifdef HAVE_ANDROID_LOG_H + int priority = severity_to_android_log_priority(severity); + __android_log_write(priority, lf->android_tag, msg_after_prefix); +#endif // HAVE_ANDROID_LOG_H. + } else if (lf->callback) { + if (domain & LD_NOCB) { + if (!*callbacks_deferred && pending_cb_messages) { + smartlist_add(pending_cb_messages, + pending_log_message_new(severity,domain,NULL,msg_after_prefix)); + *callbacks_deferred = 1; + if (smartlist_len(pending_cb_messages) == 1 && pending_cb_cb) { + pending_cb_cb(); + } + } + } else { + lf->callback(severity, domain, msg_after_prefix); + } + } else { + if (write_all_to_fd(lf->fd, buf, msg_len) < 0) { /* error */ + /* don't log the error! mark this log entry to be blown away, and + * continue. */ + lf->seems_dead = 1; + } + } +} + +/** Helper: sends a message to the appropriate logfiles, at loglevel + * <b>severity</b>. If provided, <b>funcname</b> is prepended to the + * message. The actual message is derived as from tor_snprintf(format,ap). + */ +MOCK_IMPL(STATIC void, +logv,(int severity, log_domain_mask_t domain, const char *funcname, + const char *suffix, const char *format, va_list ap)) +{ + char buf[10240]; + size_t msg_len = 0; + int formatted = 0; + logfile_t *lf; + char *end_of_prefix=NULL; + int callbacks_deferred = 0; + + /* Call assert, not raw_assert, since raw_assert calls log on failure. */ + raw_assert(format); + /* check that severity is sane. Overrunning the masks array leads to + * interesting and hard to diagnose effects */ + raw_assert(severity >= LOG_ERR && severity <= LOG_DEBUG); + /* check that we've initialised the log mutex before we try to lock it */ + raw_assert(log_mutex_initialized); + LOCK_LOGS(); + + if ((! (domain & LD_NOCB)) && pending_cb_messages + && smartlist_len(pending_cb_messages)) + flush_pending_log_callbacks(); + + if (queue_startup_messages && + pending_startup_messages_len < MAX_STARTUP_MSG_LEN) { + end_of_prefix = + format_msg(buf, sizeof(buf), domain, severity, funcname, suffix, + format, ap, &msg_len); + formatted = 1; + + smartlist_add(pending_startup_messages, + pending_log_message_new(severity,domain,buf,end_of_prefix)); + pending_startup_messages_len += msg_len; + } + + for (lf = logfiles; lf; lf = lf->next) { + if (! logfile_wants_message(lf, severity, domain)) + continue; + + if (!formatted) { + end_of_prefix = + format_msg(buf, sizeof(buf), domain, severity, funcname, suffix, + format, ap, &msg_len); + formatted = 1; + } + + logfile_deliver(lf, buf, msg_len, end_of_prefix, domain, severity, + &callbacks_deferred); + } + UNLOCK_LOGS(); +} + +/** Output a message to the log. It gets logged to all logfiles that + * care about messages with <b>severity</b> in <b>domain</b>. The content + * is formatted printf-style based on <b>format</b> and extra arguments. + * */ +void +tor_log(int severity, log_domain_mask_t domain, const char *format, ...) +{ + va_list ap; + if (severity > log_global_min_severity_) + return; + va_start(ap,format); +#ifdef TOR_UNIT_TESTS + if (domain & LD_NO_MOCK) + logv__real(severity, domain, NULL, NULL, format, ap); + else +#endif + logv(severity, domain, NULL, NULL, format, ap); + va_end(ap); +} + +/** Helper function; return true iff the <b>n</b>-element array <b>array</b> + * contains <b>item</b>. */ +static int +int_array_contains(const int *array, int n, int item) +{ + int j; + for (j = 0; j < n; ++j) { + if (array[j] == item) + return 1; + } + return 0; +} + +/** Function to call whenever the list of logs changes to get ready to log + * from signal handlers. */ +void +tor_log_update_sigsafe_err_fds(void) +{ + const logfile_t *lf; + int found_real_stderr = 0; + + int fds[TOR_SIGSAFE_LOG_MAX_FDS]; + int n_fds; + + LOCK_LOGS(); + /* Reserve the first one for stderr. This is safe because when we daemonize, + * we dup2 /dev/null to stderr, */ + fds[0] = STDERR_FILENO; + n_fds = 1; + + for (lf = logfiles; lf; lf = lf->next) { + /* Don't try callback to the control port, or syslogs: We can't + * do them from a signal handler. Don't try stdout: we always do stderr. + */ + if (lf->is_temporary || logfile_is_external(lf) + || lf->seems_dead || lf->fd < 0) + continue; + if (lf->severities->masks[SEVERITY_MASK_IDX(LOG_ERR)] & + (LD_BUG|LD_GENERAL)) { + if (lf->fd == STDERR_FILENO) + found_real_stderr = 1; + /* Avoid duplicates */ + if (int_array_contains(fds, n_fds, lf->fd)) + continue; + fds[n_fds++] = lf->fd; + if (n_fds == TOR_SIGSAFE_LOG_MAX_FDS) + break; + } + } + + if (!found_real_stderr && + int_array_contains(fds, n_fds, STDOUT_FILENO)) { + /* Don't use a virtual stderr when we're also logging to stdout. */ + raw_assert(n_fds >= 2); /* Don't raw_assert inside log fns */ + fds[0] = fds[--n_fds]; + } + + UNLOCK_LOGS(); + + tor_log_set_sigsafe_err_fds(fds, n_fds); +} + +/** Add to <b>out</b> a copy of every currently configured log file name. Used + * to enable access to these filenames with the sandbox code. */ +void +tor_log_get_logfile_names(smartlist_t *out) +{ + logfile_t *lf; + raw_assert(out); + + LOCK_LOGS(); + + for (lf = logfiles; lf; lf = lf->next) { + if (lf->is_temporary || logfile_is_external(lf)) + continue; + if (lf->filename == NULL) + continue; + smartlist_add_strdup(out, lf->filename); + } + + UNLOCK_LOGS(); +} + +/** Implementation of the log_fn backend, used when we have + * variadic macros. All arguments are as for log_fn, except for + * <b>fn</b>, which is the name of the calling functions. */ +void +log_fn_(int severity, log_domain_mask_t domain, const char *fn, + const char *format, ...) +{ + va_list ap; + if (severity > log_global_min_severity_) + return; + va_start(ap,format); + logv(severity, domain, fn, NULL, format, ap); + va_end(ap); +} +void +log_fn_ratelim_(ratelim_t *ratelim, int severity, log_domain_mask_t domain, + const char *fn, const char *format, ...) +{ + va_list ap; + char *m; + if (severity > log_global_min_severity_) + return; + m = rate_limit_log(ratelim, approx_time()); + if (m == NULL) + return; + va_start(ap, format); + logv(severity, domain, fn, m, format, ap); + va_end(ap); + tor_free(m); +} + +/** Free all storage held by <b>victim</b>. */ +static void +log_free_(logfile_t *victim) +{ + if (!victim) + return; + tor_free(victim->severities); + tor_free(victim->filename); + tor_free(victim->android_tag); + tor_free(victim); +} + +/** Close all open log files, and free other static memory. */ +void +logs_free_all(void) +{ + logfile_t *victim, *next; + smartlist_t *messages, *messages2; + LOCK_LOGS(); + next = logfiles; + logfiles = NULL; + messages = pending_cb_messages; + pending_cb_messages = NULL; + pending_cb_cb = NULL; + messages2 = pending_startup_messages; + pending_startup_messages = NULL; + UNLOCK_LOGS(); + while (next) { + victim = next; + next = next->next; + close_log(victim); + log_free(victim); + } + tor_free(appname); + + SMARTLIST_FOREACH(messages, pending_log_message_t *, msg, { + pending_log_message_free(msg); + }); + smartlist_free(messages); + + if (messages2) { + SMARTLIST_FOREACH(messages2, pending_log_message_t *, msg, { + pending_log_message_free(msg); + }); + smartlist_free(messages2); + } + + /* We _could_ destroy the log mutex here, but that would screw up any logs + * that happened between here and the end of execution. */ +} + +/** Remove and free the log entry <b>victim</b> from the linked-list + * logfiles (it is probably present, but it might not be due to thread + * racing issues). After this function is called, the caller shouldn't + * refer to <b>victim</b> anymore. + * + * Long-term, we need to do something about races in the log subsystem + * in general. See bug 222 for more details. + */ +static void +delete_log(logfile_t *victim) +{ + logfile_t *tmpl; + if (victim == logfiles) + logfiles = victim->next; + else { + for (tmpl = logfiles; tmpl && tmpl->next != victim; tmpl=tmpl->next) ; +// raw_assert(tmpl); +// raw_assert(tmpl->next == victim); + if (!tmpl) + return; + tmpl->next = victim->next; + } + log_free(victim); +} + +/** Helper: release system resources (but not memory) held by a single + * logfile_t. */ +static void +close_log(logfile_t *victim) +{ + if (victim->needs_close && victim->fd >= 0) { + close(victim->fd); + victim->fd = -1; + } else if (victim->is_syslog) { +#ifdef HAVE_SYSLOG_H + if (--syslog_count == 0) { + /* There are no other syslogs; close the logging facility. */ + closelog(); + } +#endif /* defined(HAVE_SYSLOG_H) */ + } +} + +/** Adjust a log severity configuration in <b>severity_out</b> to contain + * every domain between <b>loglevelMin</b> and <b>loglevelMax</b>, inclusive. + */ +void +set_log_severity_config(int loglevelMin, int loglevelMax, + log_severity_list_t *severity_out) +{ + int i; + raw_assert(loglevelMin >= loglevelMax); + raw_assert(loglevelMin >= LOG_ERR && loglevelMin <= LOG_DEBUG); + raw_assert(loglevelMax >= LOG_ERR && loglevelMax <= LOG_DEBUG); + memset(severity_out, 0, sizeof(log_severity_list_t)); + for (i = loglevelMin; i >= loglevelMax; --i) { + severity_out->masks[SEVERITY_MASK_IDX(i)] = ~0u; + } +} + +/** Add a log handler named <b>name</b> to send all messages in <b>severity</b> + * to <b>fd</b>. Copies <b>severity</b>. Helper: does no locking. */ +static void +add_stream_log_impl(const log_severity_list_t *severity, + const char *name, int fd) +{ + logfile_t *lf; + lf = tor_malloc_zero(sizeof(logfile_t)); + lf->fd = fd; + lf->filename = tor_strdup(name); + lf->severities = tor_memdup(severity, sizeof(log_severity_list_t)); + lf->next = logfiles; + + logfiles = lf; + log_global_min_severity_ = get_min_log_level(); +} + +/** Add a log handler named <b>name</b> to send all messages in <b>severity</b> + * to <b>fd</b>. Steals a reference to <b>severity</b>; the caller must + * not use it after calling this function. */ +void +add_stream_log(const log_severity_list_t *severity, const char *name, int fd) +{ + LOCK_LOGS(); + add_stream_log_impl(severity, name, fd); + UNLOCK_LOGS(); +} + +/** Initialize the global logging facility */ +void +init_logging(int disable_startup_queue) +{ + if (!log_mutex_initialized) { + tor_mutex_init(&log_mutex); + log_mutex_initialized = 1; + } +#ifdef __GNUC__ + if (strchr(__PRETTY_FUNCTION__, '(')) { + pretty_fn_has_parens = 1; + } +#endif + if (pending_cb_messages == NULL) + pending_cb_messages = smartlist_new(); + if (disable_startup_queue) + queue_startup_messages = 0; + if (pending_startup_messages == NULL && queue_startup_messages) { + pending_startup_messages = smartlist_new(); + } +} + +/** Set whether we report logging domains as a part of our log messages. + */ +void +logs_set_domain_logging(int enabled) +{ + LOCK_LOGS(); + log_domains_are_logged = enabled; + UNLOCK_LOGS(); +} + +/** Add a log handler to receive messages during startup (before the real + * logs are initialized). + */ +void +add_temp_log(int min_severity) +{ + log_severity_list_t *s = tor_malloc_zero(sizeof(log_severity_list_t)); + set_log_severity_config(min_severity, LOG_ERR, s); + LOCK_LOGS(); + add_stream_log_impl(s, "<temp>", fileno(stdout)); + tor_free(s); + logfiles->is_temporary = 1; + UNLOCK_LOGS(); +} + +/** + * Register "cb" as the callback to call when there are new pending log + * callbacks to be flushed with flush_pending_log_callbacks(). + * + * Note that this callback, if present, can be invoked from any thread. + * + * This callback must not log. + * + * It is intentional that this function contains the name "callback" twice: it + * sets a "callback" to be called on the condition that there is a "pending + * callback". + **/ +void +logs_set_pending_callback_callback(pending_callback_callback cb) +{ + pending_cb_cb = cb; +} + +/** + * Add a log handler to send messages in <b>severity</b> + * to the function <b>cb</b>. + */ +int +add_callback_log(const log_severity_list_t *severity, log_callback cb) +{ + logfile_t *lf; + lf = tor_malloc_zero(sizeof(logfile_t)); + lf->fd = -1; + lf->severities = tor_memdup(severity, sizeof(log_severity_list_t)); + lf->filename = tor_strdup("<callback>"); + lf->callback = cb; + lf->next = logfiles; + + LOCK_LOGS(); + logfiles = lf; + log_global_min_severity_ = get_min_log_level(); + UNLOCK_LOGS(); + return 0; +} + +/** Adjust the configured severity of any logs whose callback function is + * <b>cb</b>. */ +void +change_callback_log_severity(int loglevelMin, int loglevelMax, + log_callback cb) +{ + logfile_t *lf; + log_severity_list_t severities; + set_log_severity_config(loglevelMin, loglevelMax, &severities); + LOCK_LOGS(); + for (lf = logfiles; lf; lf = lf->next) { + if (lf->callback == cb) { + memcpy(lf->severities, &severities, sizeof(severities)); + } + } + log_global_min_severity_ = get_min_log_level(); + UNLOCK_LOGS(); +} + +/** If there are any log messages that were generated with LD_NOCB waiting to + * be sent to callback-based loggers, send them now. */ +void +flush_pending_log_callbacks(void) +{ + logfile_t *lf; + smartlist_t *messages, *messages_tmp; + + LOCK_LOGS(); + if (!pending_cb_messages || 0 == smartlist_len(pending_cb_messages)) { + UNLOCK_LOGS(); + return; + } + + messages = pending_cb_messages; + pending_cb_messages = smartlist_new(); + do { + SMARTLIST_FOREACH_BEGIN(messages, pending_log_message_t *, msg) { + const int severity = msg->severity; + const int domain = msg->domain; + for (lf = logfiles; lf; lf = lf->next) { + if (! lf->callback || lf->seems_dead || + ! (lf->severities->masks[SEVERITY_MASK_IDX(severity)] & domain)) { + continue; + } + lf->callback(severity, domain, msg->msg); + } + pending_log_message_free(msg); + } SMARTLIST_FOREACH_END(msg); + smartlist_clear(messages); + + messages_tmp = pending_cb_messages; + pending_cb_messages = messages; + messages = messages_tmp; + } while (smartlist_len(messages)); + + smartlist_free(messages); + + UNLOCK_LOGS(); +} + +/** Flush all the messages we stored from startup while waiting for log + * initialization. + */ +void +flush_log_messages_from_startup(void) +{ + logfile_t *lf; + + LOCK_LOGS(); + queue_startup_messages = 0; + pending_startup_messages_len = 0; + if (! pending_startup_messages) + goto out; + + SMARTLIST_FOREACH_BEGIN(pending_startup_messages, pending_log_message_t *, + msg) { + int callbacks_deferred = 0; + for (lf = logfiles; lf; lf = lf->next) { + if (! logfile_wants_message(lf, msg->severity, msg->domain)) + continue; + + /* We configure a temporary startup log that goes to stdout, so we + * shouldn't replay to stdout/stderr*/ + if (lf->fd == STDOUT_FILENO || lf->fd == STDERR_FILENO) { + continue; + } + + logfile_deliver(lf, msg->fullmsg, strlen(msg->fullmsg), msg->msg, + msg->domain, msg->severity, &callbacks_deferred); + } + pending_log_message_free(msg); + } SMARTLIST_FOREACH_END(msg); + smartlist_free(pending_startup_messages); + pending_startup_messages = NULL; + + out: + UNLOCK_LOGS(); +} + +/** Close any log handlers added by add_temp_log() or marked by + * mark_logs_temp(). */ +void +close_temp_logs(void) +{ + logfile_t *lf, **p; + + LOCK_LOGS(); + for (p = &logfiles; *p; ) { + if ((*p)->is_temporary) { + lf = *p; + /* we use *p here to handle the edge case of the head of the list */ + *p = (*p)->next; + close_log(lf); + log_free(lf); + } else { + p = &((*p)->next); + } + } + + log_global_min_severity_ = get_min_log_level(); + UNLOCK_LOGS(); +} + +/** Make all currently temporary logs (set to be closed by close_temp_logs) + * live again, and close all non-temporary logs. */ +void +rollback_log_changes(void) +{ + logfile_t *lf; + LOCK_LOGS(); + for (lf = logfiles; lf; lf = lf->next) + lf->is_temporary = ! lf->is_temporary; + UNLOCK_LOGS(); + close_temp_logs(); +} + +/** Configure all log handles to be closed by close_temp_logs(). */ +void +mark_logs_temp(void) +{ + logfile_t *lf; + LOCK_LOGS(); + for (lf = logfiles; lf; lf = lf->next) + lf->is_temporary = 1; + UNLOCK_LOGS(); +} + +/** + * Add a log handler to send messages to <b>filename</b> via <b>fd</b>. If + * opening the logfile failed, -1 is returned and errno is set appropriately + * (by open(2)). Takes ownership of fd. + */ +int +add_file_log(const log_severity_list_t *severity, + const char *filename, + int fd) +{ + logfile_t *lf; + + if (fd<0) + return -1; + if (tor_fd_seekend(fd)<0) { + close(fd); + return -1; + } + + LOCK_LOGS(); + add_stream_log_impl(severity, filename, fd); + logfiles->needs_close = 1; + lf = logfiles; + log_global_min_severity_ = get_min_log_level(); + + if (log_tor_version(lf, 0) < 0) { + delete_log(lf); + } + UNLOCK_LOGS(); + + return 0; +} + +#ifdef HAVE_SYSLOG_H +/** + * Add a log handler to send messages to they system log facility. + * + * If this is the first log handler, opens syslog with ident Tor or + * Tor-<syslog_identity_tag> if that is not NULL. + */ +int +add_syslog_log(const log_severity_list_t *severity, + const char* syslog_identity_tag) +{ + logfile_t *lf; + if (syslog_count++ == 0) { + /* This is the first syslog. */ + static char buf[256]; + if (syslog_identity_tag) { + tor_snprintf(buf, sizeof(buf), "Tor-%s", syslog_identity_tag); + } else { + tor_snprintf(buf, sizeof(buf), "Tor"); + } + openlog(buf, LOG_PID | LOG_NDELAY, LOGFACILITY); + } + + lf = tor_malloc_zero(sizeof(logfile_t)); + lf->fd = -1; + lf->severities = tor_memdup(severity, sizeof(log_severity_list_t)); + lf->filename = tor_strdup("<syslog>"); + lf->is_syslog = 1; + + LOCK_LOGS(); + lf->next = logfiles; + logfiles = lf; + log_global_min_severity_ = get_min_log_level(); + UNLOCK_LOGS(); + return 0; +} +#endif /* defined(HAVE_SYSLOG_H) */ + +#ifdef HAVE_ANDROID_LOG_H +/** + * Add a log handler to send messages to the Android platform log facility. + */ +int +add_android_log(const log_severity_list_t *severity, + const char *android_tag) +{ + logfile_t *lf = NULL; + + lf = tor_malloc_zero(sizeof(logfile_t)); + lf->fd = -1; + lf->severities = tor_memdup(severity, sizeof(log_severity_list_t)); + lf->filename = tor_strdup("<android>"); + lf->is_android = 1; + + if (android_tag == NULL) + lf->android_tag = tor_strdup("Tor"); + else { + char buf[256]; + tor_snprintf(buf, sizeof(buf), "Tor-%s", android_tag); + lf->android_tag = tor_strdup(buf); + } + + LOCK_LOGS(); + lf->next = logfiles; + logfiles = lf; + log_global_min_severity_ = get_min_log_level(); + UNLOCK_LOGS(); + return 0; +} +#endif // HAVE_ANDROID_LOG_H. + +/** If <b>level</b> is a valid log severity, return the corresponding + * numeric value. Otherwise, return -1. */ +int +parse_log_level(const char *level) +{ + if (!strcasecmp(level, "err")) + return LOG_ERR; + if (!strcasecmp(level, "warn")) + return LOG_WARN; + if (!strcasecmp(level, "notice")) + return LOG_NOTICE; + if (!strcasecmp(level, "info")) + return LOG_INFO; + if (!strcasecmp(level, "debug")) + return LOG_DEBUG; + return -1; +} + +/** Return the string equivalent of a given log level. */ +const char * +log_level_to_string(int level) +{ + return sev_to_string(level); +} + +/** NULL-terminated array of names for log domains such that domain_list[dom] + * is a description of <b>dom</b>. + * + * Remember to update doc/tor.1.txt if you modify this list. + * */ +static const char *domain_list[] = { + "GENERAL", "CRYPTO", "NET", "CONFIG", "FS", "PROTOCOL", "MM", + "HTTP", "APP", "CONTROL", "CIRC", "REND", "BUG", "DIR", "DIRSERV", + "OR", "EDGE", "ACCT", "HIST", "HANDSHAKE", "HEARTBEAT", "CHANNEL", + "SCHED", "GUARD", "CONSDIFF", "DOS", NULL +}; + +/** Return a bitmask for the log domain for which <b>domain</b> is the name, + * or 0 if there is no such name. */ +static log_domain_mask_t +parse_log_domain(const char *domain) +{ + int i; + for (i=0; domain_list[i]; ++i) { + if (!strcasecmp(domain, domain_list[i])) + return (1u<<i); + } + return 0; +} + +/** Translate a bitmask of log domains to a string. */ +static char * +domain_to_string(log_domain_mask_t domain, char *buf, size_t buflen) +{ + char *cp = buf; + char *eos = buf+buflen; + + buf[0] = '\0'; + if (! domain) + return buf; + while (1) { + const char *d; + int bit = tor_log2(domain); + size_t n; + if ((unsigned)bit >= ARRAY_LENGTH(domain_list)-1 || + bit >= N_LOGGING_DOMAINS) { + tor_snprintf(buf, buflen, "<BUG:Unknown domain %lx>", (long)domain); + return buf+strlen(buf); + } + d = domain_list[bit]; + n = strlcpy(cp, d, eos-cp); + if (n >= buflen) { + tor_snprintf(buf, buflen, "<BUG:Truncating domain %lx>", (long)domain); + return buf+strlen(buf); + } + cp += n; + domain &= ~(1<<bit); + + if (domain == 0 || (eos-cp) < 2) + return cp; + + memcpy(cp, ",", 2); /*Nul-terminated ,"*/ + cp++; + } +} + +/** Parse a log severity pattern in *<b>cfg_ptr</b>. Advance cfg_ptr after + * the end of the severityPattern. Set the value of <b>severity_out</b> to + * the parsed pattern. Return 0 on success, -1 on failure. + * + * The syntax for a SeverityPattern is: + * <pre> + * SeverityPattern = *(DomainSeverity SP)* DomainSeverity + * DomainSeverity = (DomainList SP)? SeverityRange + * SeverityRange = MinSeverity ("-" MaxSeverity )? + * DomainList = "[" (SP? DomainSpec SP? ",") SP? DomainSpec "]" + * DomainSpec = "*" | Domain | "~" Domain + * </pre> + * A missing MaxSeverity defaults to ERR. Severities and domains are + * case-insensitive. "~" indicates negation for a domain; negation happens + * last inside a DomainList. Only one SeverityRange without a DomainList is + * allowed per line. + */ +int +parse_log_severity_config(const char **cfg_ptr, + log_severity_list_t *severity_out) +{ + const char *cfg = *cfg_ptr; + int got_anything = 0; + int got_an_unqualified_range = 0; + memset(severity_out, 0, sizeof(*severity_out)); + + cfg = eat_whitespace(cfg); + while (*cfg) { + const char *dash, *space; + char *sev_lo, *sev_hi; + int low, high, i; + log_domain_mask_t domains = ~0u; + + if (*cfg == '[') { + int err = 0; + char *domains_str; + smartlist_t *domains_list; + log_domain_mask_t neg_domains = 0; + const char *closebracket = strchr(cfg, ']'); + if (!closebracket) + return -1; + domains = 0; + domains_str = tor_strndup(cfg+1, closebracket-cfg-1); + domains_list = smartlist_new(); + smartlist_split_string(domains_list, domains_str, ",", SPLIT_SKIP_SPACE, + -1); + tor_free(domains_str); + SMARTLIST_FOREACH_BEGIN(domains_list, const char *, domain) { + if (!strcmp(domain, "*")) { + domains = ~0u; + } else { + int d; + int negate=0; + if (*domain == '~') { + negate = 1; + ++domain; + } + d = parse_log_domain(domain); + if (!d) { + log_warn(LD_CONFIG, "No such logging domain as %s", domain); + err = 1; + } else { + if (negate) + neg_domains |= d; + else + domains |= d; + } + } + } SMARTLIST_FOREACH_END(domain); + SMARTLIST_FOREACH(domains_list, char *, d, tor_free(d)); + smartlist_free(domains_list); + if (err) + return -1; + if (domains == 0 && neg_domains) + domains = ~neg_domains; + else + domains &= ~neg_domains; + cfg = eat_whitespace(closebracket+1); + } else { + ++got_an_unqualified_range; + } + if (!strcasecmpstart(cfg, "file") || + !strcasecmpstart(cfg, "stderr") || + !strcasecmpstart(cfg, "stdout") || + !strcasecmpstart(cfg, "syslog") || + !strcasecmpstart(cfg, "android")) { + goto done; + } + if (got_an_unqualified_range > 1) + return -1; + + space = find_whitespace(cfg); + dash = strchr(cfg, '-'); + if (dash && dash < space) { + sev_lo = tor_strndup(cfg, dash-cfg); + sev_hi = tor_strndup(dash+1, space-(dash+1)); + } else { + sev_lo = tor_strndup(cfg, space-cfg); + sev_hi = tor_strdup("ERR"); + } + low = parse_log_level(sev_lo); + high = parse_log_level(sev_hi); + tor_free(sev_lo); + tor_free(sev_hi); + if (low == -1) + return -1; + if (high == -1) + return -1; + + got_anything = 1; + for (i=low; i >= high; --i) + severity_out->masks[SEVERITY_MASK_IDX(i)] |= domains; + + cfg = eat_whitespace(space); + } + + done: + *cfg_ptr = cfg; + return got_anything ? 0 : -1; +} + +/** Return the least severe log level that any current log is interested in. */ +int +get_min_log_level(void) +{ + logfile_t *lf; + int i; + int min = LOG_ERR; + for (lf = logfiles; lf; lf = lf->next) { + for (i = LOG_DEBUG; i > min; --i) + if (lf->severities->masks[SEVERITY_MASK_IDX(i)]) + min = i; + } + return min; +} + +/** Switch all logs to output at most verbose level. */ +void +switch_logs_debug(void) +{ + logfile_t *lf; + int i; + LOCK_LOGS(); + for (lf = logfiles; lf; lf=lf->next) { + for (i = LOG_DEBUG; i >= LOG_ERR; --i) + lf->severities->masks[SEVERITY_MASK_IDX(i)] = ~0u; + } + log_global_min_severity_ = get_min_log_level(); + UNLOCK_LOGS(); +} + +/** Truncate all the log files. */ +void +truncate_logs(void) +{ + logfile_t *lf; + for (lf = logfiles; lf; lf = lf->next) { + if (lf->fd >= 0) { + tor_ftruncate(lf->fd); + } + } +} diff --git a/src/lib/log/torlog.h b/src/lib/log/torlog.h new file mode 100644 index 0000000000..c24b638191 --- /dev/null +++ b/src/lib/log/torlog.h @@ -0,0 +1,276 @@ +/* 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 */ + +/** + * \file torlog.h + * + * \brief Headers for log.c + **/ + +#ifndef TOR_TORLOG_H + +#include <stdarg.h> +#include "lib/cc/torint.h" +#include "lib/cc/compat_compiler.h" +#include "lib/testsupport/testsupport.h" + +#ifdef HAVE_SYSLOG_H +#include <syslog.h> +#define LOG_WARN LOG_WARNING +#if LOG_DEBUG < LOG_ERR +#error "Your syslog.h thinks high numbers are more important. " \ + "We aren't prepared to deal with that." +#endif +#else /* !(defined(HAVE_SYSLOG_H)) */ +/* Note: Syslog's logging code refers to priorities, with 0 being the most + * important. Thus, all our comparisons needed to be reversed when we added + * syslog support. + * + * The upshot of this is that comments about log levels may be messed up: for + * "maximum severity" read "most severe" and "numerically *lowest* severity". + */ + +/** Debug-level severity: for hyper-verbose messages of no interest to + * anybody but developers. */ +#define LOG_DEBUG 7 +/** Info-level severity: for messages that appear frequently during normal + * operation. */ +#define LOG_INFO 6 +/** Notice-level severity: for messages that appear infrequently + * during normal operation; that the user will probably care about; + * and that are not errors. + */ +#define LOG_NOTICE 5 +/** Warn-level severity: for messages that only appear when something has gone + * wrong. */ +#define LOG_WARN 4 +/** Error-level severity: for messages that only appear when something has gone + * very wrong, and the Tor process can no longer proceed. */ +#define LOG_ERR 3 +#endif /* defined(HAVE_SYSLOG_H) */ + +/* Logging domains */ + +/** Catch-all for miscellaneous events and fatal errors. */ +#define LD_GENERAL (1u<<0) +/** The cryptography subsystem. */ +#define LD_CRYPTO (1u<<1) +/** Networking. */ +#define LD_NET (1u<<2) +/** Parsing and acting on our configuration. */ +#define LD_CONFIG (1u<<3) +/** Reading and writing from the filesystem. */ +#define LD_FS (1u<<4) +/** Other servers' (non)compliance with the Tor protocol. */ +#define LD_PROTOCOL (1u<<5) +/** Memory management. */ +#define LD_MM (1u<<6) +/** HTTP implementation. */ +#define LD_HTTP (1u<<7) +/** Application (socks) requests. */ +#define LD_APP (1u<<8) +/** Communication via the controller protocol. */ +#define LD_CONTROL (1u<<9) +/** Building, using, and managing circuits. */ +#define LD_CIRC (1u<<10) +/** Hidden services. */ +#define LD_REND (1u<<11) +/** Internal errors in this Tor process. */ +#define LD_BUG (1u<<12) +/** Learning and using information about Tor servers. */ +#define LD_DIR (1u<<13) +/** Learning and using information about Tor servers. */ +#define LD_DIRSERV (1u<<14) +/** Onion routing protocol. */ +#define LD_OR (1u<<15) +/** Generic edge-connection functionality. */ +#define LD_EDGE (1u<<16) +#define LD_EXIT LD_EDGE +/** Bandwidth accounting. */ +#define LD_ACCT (1u<<17) +/** Router history */ +#define LD_HIST (1u<<18) +/** OR handshaking */ +#define LD_HANDSHAKE (1u<<19) +/** Heartbeat messages */ +#define LD_HEARTBEAT (1u<<20) +/** Abstract channel_t code */ +#define LD_CHANNEL (1u<<21) +/** Scheduler */ +#define LD_SCHED (1u<<22) +/** Guard nodes */ +#define LD_GUARD (1u<<23) +/** Generation and application of consensus diffs. */ +#define LD_CONSDIFF (1u<<24) +/** Denial of Service mitigation. */ +#define LD_DOS (1u<<25) +/** Number of logging domains in the code. */ +#define N_LOGGING_DOMAINS 26 + +/** This log message is not safe to send to a callback-based logger + * immediately. Used as a flag, not a log domain. */ +#define LD_NOCB (1u<<31) +/** This log message should not include a function name, even if it otherwise + * would. Used as a flag, not a log domain. */ +#define LD_NOFUNCNAME (1u<<30) + +#ifdef TOR_UNIT_TESTS +/** This log message should not be intercepted by mock_saving_logv */ +#define LD_NO_MOCK (1u<<29) +#endif + +/** Mask of zero or more log domains, OR'd together. */ +typedef uint32_t log_domain_mask_t; + +/** Configures which severities are logged for each logging domain for a given + * log target. */ +typedef struct log_severity_list_t { + /** For each log severity, a bitmask of which domains a given logger is + * logging. */ + log_domain_mask_t masks[LOG_DEBUG-LOG_ERR+1]; +} log_severity_list_t; + +/** Callback type used for add_callback_log. */ +typedef void (*log_callback)(int severity, uint32_t domain, const char *msg); + +void init_logging(int disable_startup_queue); +int parse_log_level(const char *level); +const char *log_level_to_string(int level); +int parse_log_severity_config(const char **cfg, + log_severity_list_t *severity_out); +void set_log_severity_config(int minSeverity, int maxSeverity, + log_severity_list_t *severity_out); +void add_stream_log(const log_severity_list_t *severity, const char *name, + int fd); +int add_file_log(const log_severity_list_t *severity, + const char *filename, + int fd); + +#ifdef HAVE_SYSLOG_H +int add_syslog_log(const log_severity_list_t *severity, + const char* syslog_identity_tag); +#endif // HAVE_SYSLOG_H. +#ifdef HAVE_ANDROID_LOG_H +int add_android_log(const log_severity_list_t *severity, + const char *android_identity_tag); +#endif // HAVE_ANDROID_LOG_H. +int add_callback_log(const log_severity_list_t *severity, log_callback cb); +typedef void (*pending_callback_callback)(void); +void logs_set_pending_callback_callback(pending_callback_callback cb); +void logs_set_domain_logging(int enabled); +int get_min_log_level(void); +void switch_logs_debug(void); +void logs_free_all(void); +void add_temp_log(int min_severity); +void close_temp_logs(void); +void rollback_log_changes(void); +void mark_logs_temp(void); +void change_callback_log_severity(int loglevelMin, int loglevelMax, + log_callback cb); +void flush_pending_log_callbacks(void); +void flush_log_messages_from_startup(void); +void log_set_application_name(const char *name); +void set_log_time_granularity(int granularity_msec); +void truncate_logs(void); + +void tor_log(int severity, log_domain_mask_t domain, const char *format, ...) + CHECK_PRINTF(3,4); + +void tor_log_update_sigsafe_err_fds(void); + +struct smartlist_t; +void tor_log_get_logfile_names(struct smartlist_t *out); + +extern int log_global_min_severity_; + +void log_fn_(int severity, log_domain_mask_t domain, + const char *funcname, const char *format, ...) + CHECK_PRINTF(4,5); +struct ratelim_t; +void log_fn_ratelim_(struct ratelim_t *ratelim, int severity, + log_domain_mask_t domain, const char *funcname, + const char *format, ...) + CHECK_PRINTF(5,6); + +int log_message_is_interesting(int severity, log_domain_mask_t domain); +void tor_log_string(int severity, log_domain_mask_t domain, + const char *function, const char *string); + +#if defined(__GNUC__) && __GNUC__ <= 3 + +/* These are the GCC varidaic macros, so that older versions of GCC don't + * break. */ + +/** Log a message at level <b>severity</b>, using a pretty-printed version + * of the current function name. */ +#define log_fn(severity, domain, args...) \ + log_fn_(severity, domain, __FUNCTION__, args) +/** As log_fn, but use <b>ratelim</b> (an instance of ratelim_t) to control + * the frequency at which messages can appear. + */ +#define log_fn_ratelim(ratelim, severity, domain, args...) \ + log_fn_ratelim_(ratelim, severity, domain, __FUNCTION__, args) +#define log_debug(domain, args...) \ + STMT_BEGIN \ + if (PREDICT_UNLIKELY(log_global_min_severity_ == LOG_DEBUG)) \ + log_fn_(LOG_DEBUG, domain, __FUNCTION__, args); \ + STMT_END +#define log_info(domain, args...) \ + log_fn_(LOG_INFO, domain, __FUNCTION__, args) +#define log_notice(domain, args...) \ + log_fn_(LOG_NOTICE, domain, __FUNCTION__, args) +#define log_warn(domain, args...) \ + log_fn_(LOG_WARN, domain, __FUNCTION__, args) +#define log_err(domain, args...) \ + log_fn_(LOG_ERR, domain, __FUNCTION__, args) + +#else /* !(defined(__GNUC__) && __GNUC__ <= 3) */ + +/* Here are the c99 variadic macros, to work with non-GCC compilers */ + +#define log_debug(domain, args, ...) \ + STMT_BEGIN \ + if (PREDICT_UNLIKELY(log_global_min_severity_ == LOG_DEBUG)) \ + log_fn_(LOG_DEBUG, domain, __FUNCTION__, args, ##__VA_ARGS__); \ + STMT_END +#define log_info(domain, args,...) \ + log_fn_(LOG_INFO, domain, __FUNCTION__, args, ##__VA_ARGS__) +#define log_notice(domain, args,...) \ + log_fn_(LOG_NOTICE, domain, __FUNCTION__, args, ##__VA_ARGS__) +#define log_warn(domain, args,...) \ + log_fn_(LOG_WARN, domain, __FUNCTION__, args, ##__VA_ARGS__) +#define log_err(domain, args,...) \ + log_fn_(LOG_ERR, domain, __FUNCTION__, args, ##__VA_ARGS__) +/** Log a message at level <b>severity</b>, using a pretty-printed version + * of the current function name. */ +#define log_fn(severity, domain, args,...) \ + log_fn_(severity, domain, __FUNCTION__, args, ##__VA_ARGS__) +/** As log_fn, but use <b>ratelim</b> (an instance of ratelim_t) to control + * the frequency at which messages can appear. + */ +#define log_fn_ratelim(ratelim, severity, domain, args,...) \ + log_fn_ratelim_(ratelim, severity, domain, __FUNCTION__, \ + args, ##__VA_ARGS__) +#endif /* defined(__GNUC__) && __GNUC__ <= 3 */ + +/** This defines log levels that are linked in the Rust log module, rather + * than re-defining these in both Rust and C. + * + * C_RUST_COUPLED src/rust/tor_log LogSeverity, LogDomain + */ +extern const int LOG_WARN_; +extern const int LOG_NOTICE_; +extern const log_domain_mask_t LD_NET_; +extern const log_domain_mask_t LD_GENERAL_; + +#ifdef LOG_PRIVATE +MOCK_DECL(STATIC void, logv, (int severity, log_domain_mask_t domain, + const char *funcname, const char *suffix, const char *format, + va_list ap) CHECK_PRINTF(5,0)); +#endif + +# define TOR_TORLOG_H +#endif /* !defined(TOR_TORLOG_H) */ diff --git a/src/lib/log/util_bug.c b/src/lib/log/util_bug.c new file mode 100644 index 0000000000..161b65e0bf --- /dev/null +++ b/src/lib/log/util_bug.c @@ -0,0 +1,150 @@ +/* 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 */ + +/** + * \file util_bug.c + **/ + +#include "orconfig.h" +#include "lib/log/util_bug.h" +#include "lib/log/torlog.h" +#include "lib/err/backtrace.h" +#ifdef TOR_UNIT_TESTS +#include "lib/container/smartlist.h" +#endif +#include "lib/malloc/util_malloc.h" +#include "lib/string/printf.h" + +#include <string.h> + +#ifdef __COVERITY__ +int bug_macro_deadcode_dummy__ = 0; +#endif + +#ifdef TOR_UNIT_TESTS +static void (*failed_assertion_cb)(void) = NULL; +static int n_bugs_to_capture = 0; +static smartlist_t *bug_messages = NULL; +#define capturing_bugs() (bug_messages != NULL && n_bugs_to_capture) +void +tor_capture_bugs_(int n) +{ + tor_end_capture_bugs_(); + bug_messages = smartlist_new(); + n_bugs_to_capture = n; +} +void +tor_end_capture_bugs_(void) +{ + n_bugs_to_capture = 0; + if (!bug_messages) + return; + SMARTLIST_FOREACH(bug_messages, char *, cp, tor_free(cp)); + smartlist_free(bug_messages); + bug_messages = NULL; +} +const smartlist_t * +tor_get_captured_bug_log_(void) +{ + return bug_messages; +} +static void +add_captured_bug(const char *s) +{ + --n_bugs_to_capture; + smartlist_add_strdup(bug_messages, s); +} +/** Set a callback to be invoked when we get any tor_bug_occurred_ + * invocation. We use this in the unit tests so that a nonfatal + * assertion failure can also count as a test failure. + */ +void +tor_set_failed_assertion_callback(void (*fn)(void)) +{ + failed_assertion_cb = fn; +} +#else /* !(defined(TOR_UNIT_TESTS)) */ +#define capturing_bugs() (0) +#define add_captured_bug(s) do { } while (0) +#endif /* defined(TOR_UNIT_TESTS) */ + +/** Helper for tor_assert: report the assertion failure. */ +void +tor_assertion_failed_(const char *fname, unsigned int line, + const char *func, const char *expr) +{ + char buf[256]; + log_err(LD_BUG, "%s:%u: %s: Assertion %s failed; aborting.", + fname, line, func, expr); + tor_snprintf(buf, sizeof(buf), + "Assertion %s failed in %s at %s:%u", + expr, func, fname, line); + log_backtrace(LOG_ERR, LD_BUG, buf); +} + +/** Helper for tor_assert_nonfatal: report the assertion failure. */ +void +tor_bug_occurred_(const char *fname, unsigned int line, + const char *func, const char *expr, + int once) +{ + char buf[256]; + const char *once_str = once ? + " (Future instances of this warning will be silenced.)": ""; + if (! expr) { + if (capturing_bugs()) { + add_captured_bug("This line should not have been reached."); + return; + } + log_warn(LD_BUG, "%s:%u: %s: This line should not have been reached.%s", + fname, line, func, once_str); + tor_snprintf(buf, sizeof(buf), + "Line unexpectedly reached at %s at %s:%u", + func, fname, line); + } else { + if (capturing_bugs()) { + add_captured_bug(expr); + return; + } + log_warn(LD_BUG, "%s:%u: %s: Non-fatal assertion %s failed.%s", + fname, line, func, expr, once_str); + tor_snprintf(buf, sizeof(buf), + "Non-fatal assertion %s failed in %s at %s:%u", + expr, func, fname, line); + } + log_backtrace(LOG_WARN, LD_BUG, buf); + +#ifdef TOR_UNIT_TESTS + if (failed_assertion_cb) { + failed_assertion_cb(); + } +#endif +} + +#ifdef _WIN32 +/** Take a filename and return a pointer to its final element. This + * function is called on __FILE__ to fix a MSVC nit where __FILE__ + * contains the full path to the file. This is bad, because it + * confuses users to find the home directory of the person who + * compiled the binary in their warning messages. + */ +const char * +tor_fix_source_file(const char *fname) +{ + const char *cp1, *cp2, *r; + cp1 = strrchr(fname, '/'); + cp2 = strrchr(fname, '\\'); + if (cp1 && cp2) { + r = (cp1<cp2)?(cp2+1):(cp1+1); + } else if (cp1) { + r = cp1+1; + } else if (cp2) { + r = cp2+1; + } else { + r = fname; + } + return r; +} +#endif /* defined(_WIN32) */ diff --git a/src/lib/log/util_bug.h b/src/lib/log/util_bug.h new file mode 100644 index 0000000000..a0753c807b --- /dev/null +++ b/src/lib/log/util_bug.h @@ -0,0 +1,210 @@ +/* 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 util_bug.h + * + * \brief Macros to manage assertions, fatal and non-fatal. + * + * Guidelines: All the different kinds of assertion in this file are for + * bug-checking only. Don't write code that can assert based on bad inputs. + * + * We provide two kinds of assertion here: "fatal" and "nonfatal". Use + * nonfatal assertions for any bug you can reasonably recover from -- and + * please, try to recover! Many severe bugs in Tor have been caused by using + * a regular assertion when a nonfatal assertion would have been better. + * + * If you need to check a condition with a nonfatal assertion, AND recover + * from that same condition, consider using the BUG() macro inside a + * conditional. For example: + * + * <code> + * // wrong -- use tor_assert_nonfatal() if you just want an assertion. + * BUG(ptr == NULL); + * + * // okay, but needlessly verbose + * tor_assert_nonfatal(ptr != NULL); + * if (ptr == NULL) { ... } + * + * // this is how we do it: + * if (BUG(ptr == NULL)) { ... } + * </code> + **/ + +#ifndef TOR_UTIL_BUG_H +#define TOR_UTIL_BUG_H + +#include "orconfig.h" +#include "lib/cc/compat_compiler.h" +#include "lib/log/torlog.h" +#include "lib/testsupport/testsupport.h" + +/* Replace assert() with a variant that sends failures to the log before + * calling assert() normally. + */ +#ifdef NDEBUG +/* Nobody should ever want to build with NDEBUG set. 99% of our asserts will + * be outside the critical path anyway, so it's silly to disable bug-checking + * throughout the entire program just because a few asserts are slowing you + * down. Profile, optimize the critical path, and keep debugging on. + * + * And I'm not just saying that because some of our asserts check + * security-critical properties. + */ +#error "Sorry; we don't support building with NDEBUG." +#endif /* defined(NDEBUG) */ + +/* Sometimes we don't want to use assertions during branch coverage tests; it + * leads to tons of unreached branches which in reality are only assertions we + * didn't hit. */ +#if defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) +#define tor_assert(a) STMT_BEGIN \ + (void)(a); \ + STMT_END +#else +/** Like assert(3), but send assertion failures to the log as well as to + * stderr. */ +#define tor_assert(expr) STMT_BEGIN \ + if (PREDICT_UNLIKELY(!(expr))) { \ + tor_assertion_failed_(SHORT_FILE__, __LINE__, __func__, #expr); \ + abort(); \ + } STMT_END +#endif /* defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) */ + +#define tor_assert_unreached() tor_assert(0) + +/* Non-fatal bug assertions. The "unreached" variants mean "this line should + * never be reached." The "once" variants mean "Don't log a warning more than + * once". + * + * The 'BUG' macro checks a boolean condition and logs an error message if it + * is true. Example usage: + * if (BUG(x == NULL)) + * return -1; + */ + +#ifdef __COVERITY__ +extern int bug_macro_deadcode_dummy__; +#undef BUG +// Coverity defines this in global headers; let's override it. This is a +// magic coverity-only preprocessor thing. +// We use this "deadcode_dummy__" trick to prevent coverity from +// complaining about unreachable bug cases. +#nodef BUG(x) ((x)?(__coverity_panic__(),1):(0+bug_macro_deadcode_dummy__)) +#endif /* defined(__COVERITY__) */ + +#if defined(__COVERITY__) || defined(__clang_analyzer__) +// We're running with a static analysis tool: let's treat even nonfatal +// assertion failures as something that we need to avoid. +#define ALL_BUGS_ARE_FATAL +#endif + +#ifdef ALL_BUGS_ARE_FATAL +#define tor_assert_nonfatal_unreached() tor_assert(0) +#define tor_assert_nonfatal(cond) tor_assert((cond)) +#define tor_assert_nonfatal_unreached_once() tor_assert(0) +#define tor_assert_nonfatal_once(cond) tor_assert((cond)) +#define BUG(cond) \ + (PREDICT_UNLIKELY(cond) ? \ + (tor_assertion_failed_(SHORT_FILE__,__LINE__,__func__,"!("#cond")"), \ + abort(), 1) \ + : 0) +#elif defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) +#define tor_assert_nonfatal_unreached() STMT_NIL +#define tor_assert_nonfatal(cond) ((void)(cond)) +#define tor_assert_nonfatal_unreached_once() STMT_NIL +#define tor_assert_nonfatal_once(cond) ((void)(cond)) +#define BUG(cond) (PREDICT_UNLIKELY(cond) ? 1 : 0) +#else /* Normal case, !ALL_BUGS_ARE_FATAL, !DISABLE_ASSERTS_IN_UNIT_TESTS */ +#define tor_assert_nonfatal_unreached() STMT_BEGIN \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, NULL, 0); \ + STMT_END +#define tor_assert_nonfatal(cond) STMT_BEGIN \ + if (PREDICT_UNLIKELY(!(cond))) { \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 0); \ + } \ + STMT_END +#define tor_assert_nonfatal_unreached_once() STMT_BEGIN \ + static int warning_logged__ = 0; \ + if (!warning_logged__) { \ + warning_logged__ = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, NULL, 1); \ + } \ + STMT_END +#define tor_assert_nonfatal_once(cond) STMT_BEGIN \ + static int warning_logged__ = 0; \ + if (!warning_logged__ && PREDICT_UNLIKELY(!(cond))) { \ + warning_logged__ = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 1); \ + } \ + STMT_END +#define BUG(cond) \ + (PREDICT_UNLIKELY(cond) ? \ + (tor_bug_occurred_(SHORT_FILE__,__LINE__,__func__,"!("#cond")",0), 1) \ + : 0) +#endif /* defined(ALL_BUGS_ARE_FATAL) || ... */ + +#ifdef __GNUC__ +#define IF_BUG_ONCE__(cond,var) \ + if (( { \ + static int var = 0; \ + int bool_result = (cond); \ + if (PREDICT_UNLIKELY(bool_result) && !var) { \ + var = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, \ + "!("#cond")", 1); \ + } \ + PREDICT_UNLIKELY(bool_result); } )) +#else /* !(defined(__GNUC__)) */ +#define IF_BUG_ONCE__(cond,var) \ + static int var = 0; \ + if (PREDICT_UNLIKELY(cond) ? \ + (var ? 1 : \ + (var=1, \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, \ + "!("#cond")", 1), \ + 1)) \ + : 0) +#endif /* defined(__GNUC__) */ +#define IF_BUG_ONCE_VARNAME_(a) \ + warning_logged_on_ ## a ## __ +#define IF_BUG_ONCE_VARNAME__(a) \ + IF_BUG_ONCE_VARNAME_(a) + +/** This macro behaves as 'if (bug(x))', except that it only logs its + * warning once, no matter how many times it triggers. + */ + +#define IF_BUG_ONCE(cond) \ + IF_BUG_ONCE__((cond), \ + IF_BUG_ONCE_VARNAME__(__LINE__)) + +/** Define this if you want Tor to crash when any problem comes up, + * so you can get a coredump and track things down. */ +// #define tor_fragile_assert() tor_assert_unreached(0) +#define tor_fragile_assert() tor_assert_nonfatal_unreached_once() + +void tor_assertion_failed_(const char *fname, unsigned int line, + const char *func, const char *expr); +void tor_bug_occurred_(const char *fname, unsigned int line, + const char *func, const char *expr, + int once); + +#ifdef _WIN32 +#define SHORT_FILE__ (tor_fix_source_file(__FILE__)) +const char *tor_fix_source_file(const char *fname); +#else +#define SHORT_FILE__ (__FILE__) +#define tor_fix_source_file(s) (s) +#endif /* defined(_WIN32) */ + +#ifdef TOR_UNIT_TESTS +void tor_capture_bugs_(int n); +void tor_end_capture_bugs_(void); +const struct smartlist_t *tor_get_captured_bug_log_(void); +void tor_set_failed_assertion_callback(void (*fn)(void)); +#endif /* defined(TOR_UNIT_TESTS) */ + +#endif /* !defined(TOR_UTIL_BUG_H) */ diff --git a/src/lib/malloc/.may_include b/src/lib/malloc/.may_include new file mode 100644 index 0000000000..cc62bb1013 --- /dev/null +++ b/src/lib/malloc/.may_include @@ -0,0 +1,6 @@ +orconfig.h + +lib/cc/*.h +lib/err/*.h +lib/malloc/*.h +lib/testsupport/testsupport.h diff --git a/src/lib/malloc/include.am b/src/lib/malloc/include.am new file mode 100644 index 0000000000..b4c5cae54d --- /dev/null +++ b/src/lib/malloc/include.am @@ -0,0 +1,17 @@ + +noinst_LIBRARIES += src/lib/libtor-malloc.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-malloc-testing.a +endif + +src_lib_libtor_malloc_a_SOURCES = \ + src/lib/malloc/util_malloc.c + +src_lib_libtor_malloc_testing_a_SOURCES = \ + $(src_lib_libtor_malloc_a_SOURCES) +src_lib_libtor_malloc_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_malloc_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/malloc/util_malloc.h diff --git a/src/lib/malloc/util_malloc.c b/src/lib/malloc/util_malloc.c new file mode 100644 index 0000000000..f3b0e50c70 --- /dev/null +++ b/src/lib/malloc/util_malloc.c @@ -0,0 +1,230 @@ +/* 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 */ + +/** + * \file util_malloc.c + * \brief Wrappers for C malloc code, and replacements for items that + * may be missing. + **/ + +#include "orconfig.h" + +#include <stdlib.h> +#include <string.h> + +#include "lib/testsupport/testsupport.h" +#define UTIL_MALLOC_PRIVATE +#include "lib/malloc/util_malloc.h" +#include "lib/cc/torint.h" +#include "lib/err/torerr.h" + +#ifdef __clang_analyzer__ +#undef MALLOC_ZERO_WORKS +#endif + +/** Allocate a chunk of <b>size</b> bytes of memory, and return a pointer to + * result. On error, log and terminate the process. (Same as malloc(size), + * but never returns NULL.) + */ +void * +tor_malloc_(size_t size) +{ + void *result; + + raw_assert(size < SIZE_T_CEILING); + +#ifndef MALLOC_ZERO_WORKS + /* Some libc mallocs don't work when size==0. Override them. */ + if (size==0) { + size=1; + } +#endif /* !defined(MALLOC_ZERO_WORKS) */ + + result = raw_malloc(size); + + if (PREDICT_UNLIKELY(result == NULL)) { + /* LCOV_EXCL_START */ + /* If these functions die within a worker process, they won't call + * spawn_exit, but that's ok, since the parent will run out of memory soon + * anyway. */ + raw_assert_unreached_msg("Out of memory on malloc(). Dying."); + /* LCOV_EXCL_STOP */ + } + return result; +} + +/** Allocate a chunk of <b>size</b> bytes of memory, fill the memory with + * zero bytes, and return a pointer to the result. Log and terminate + * the process on error. (Same as calloc(size,1), but never returns NULL.) + */ +void * +tor_malloc_zero_(size_t size) +{ + /* You may ask yourself, "wouldn't it be smart to use calloc instead of + * malloc+memset? Perhaps libc's calloc knows some nifty optimization trick + * we don't!" Indeed it does, but its optimizations are only a big win when + * we're allocating something very big (it knows if it just got the memory + * from the OS in a pre-zeroed state). We don't want to use tor_malloc_zero + * for big stuff, so we don't bother with calloc. */ + void *result = tor_malloc_(size); + memset(result, 0, size); + return result; +} + +/* The square root of SIZE_MAX + 1. If a is less than this, and b is less + * than this, then a*b is less than SIZE_MAX. (For example, if size_t is + * 32 bits, then SIZE_MAX is 0xffffffff and this value is 0x10000. If a and + * b are less than this, then their product is at most (65535*65535) == + * 0xfffe0001. */ +#define SQRT_SIZE_MAX_P1 (((size_t)1) << (sizeof(size_t)*4)) + +/** Return non-zero if and only if the product of the arguments is exact, + * and cannot overflow. */ +STATIC int +size_mul_check(const size_t x, const size_t y) +{ + /* This first check is equivalent to + (x < SQRT_SIZE_MAX_P1 && y < SQRT_SIZE_MAX_P1) + + Rationale: if either one of x or y is >= SQRT_SIZE_MAX_P1, then it + will have some bit set in its most significant half. + */ + return ((x|y) < SQRT_SIZE_MAX_P1 || + y == 0 || + x <= SIZE_MAX / y); +} + +/** Allocate a chunk of <b>nmemb</b>*<b>size</b> bytes of memory, fill + * the memory with zero bytes, and return a pointer to the result. + * Log and terminate the process on error. (Same as + * calloc(<b>nmemb</b>,<b>size</b>), but never returns NULL.) + * The second argument (<b>size</b>) should preferably be non-zero + * and a compile-time constant. + */ +void * +tor_calloc_(size_t nmemb, size_t size) +{ + raw_assert(size_mul_check(nmemb, size)); + return tor_malloc_zero_((nmemb * size)); +} + +/** Change the size of the memory block pointed to by <b>ptr</b> to <b>size</b> + * bytes long; return the new memory block. On error, log and + * terminate. (Like realloc(ptr,size), but never returns NULL.) + */ +void * +tor_realloc_(void *ptr, size_t size) +{ + void *result; + + raw_assert(size < SIZE_T_CEILING); + +#ifndef MALLOC_ZERO_WORKS + /* Some libc mallocs don't work when size==0. Override them. */ + if (size==0) { + size=1; + } +#endif /* !defined(MALLOC_ZERO_WORKS) */ + + result = raw_realloc(ptr, size); + + if (PREDICT_UNLIKELY(result == NULL)) { + /* LCOV_EXCL_START */ + raw_assert_unreached_msg("Out of memory on realloc(). Dying."); + /* LCOV_EXCL_STOP */ + } + return result; +} + +/** + * Try to realloc <b>ptr</b> so that it takes up sz1 * sz2 bytes. Check for + * overflow. Unlike other allocation functions, return NULL on overflow. + */ +void * +tor_reallocarray_(void *ptr, size_t sz1, size_t sz2) +{ + /* XXXX we can make this return 0, but we would need to check all the + * reallocarray users. */ + raw_assert(size_mul_check(sz1, sz2)); + + return tor_realloc(ptr, (sz1 * sz2)); +} + +/** Return a newly allocated copy of the NUL-terminated string s. On + * error, log and terminate. (Like strdup(s), but never returns + * NULL.) + */ +char * +tor_strdup_(const char *s) +{ + char *duplicate; + raw_assert(s); + + duplicate = raw_strdup(s); + + if (PREDICT_UNLIKELY(duplicate == NULL)) { + /* LCOV_EXCL_START */ + raw_assert_unreached_msg("Out of memory on strdup(). Dying."); + /* LCOV_EXCL_STOP */ + } + return duplicate; +} + +/** Allocate and return a new string containing the first <b>n</b> + * characters of <b>s</b>. If <b>s</b> is longer than <b>n</b> + * characters, only the first <b>n</b> are copied. The result is + * always NUL-terminated. (Like strndup(s,n), but never returns + * NULL.) + */ +char * +tor_strndup_(const char *s, size_t n) +{ + char *duplicate; + raw_assert(s); + raw_assert(n < SIZE_T_CEILING); + duplicate = tor_malloc_((n+1)); + /* Performance note: Ordinarily we prefer strlcpy to strncpy. But + * this function gets called a whole lot, and platform strncpy is + * much faster than strlcpy when strlen(s) is much longer than n. + */ + strncpy(duplicate, s, n); + duplicate[n]='\0'; + return duplicate; +} + +/** Allocate a chunk of <b>len</b> bytes, with the same contents as the + * <b>len</b> bytes starting at <b>mem</b>. */ +void * +tor_memdup_(const void *mem, size_t len) +{ + char *duplicate; + raw_assert(len < SIZE_T_CEILING); + raw_assert(mem); + duplicate = tor_malloc_(len); + memcpy(duplicate, mem, len); + return duplicate; +} + +/** As tor_memdup(), but add an extra 0 byte at the end of the resulting + * memory. */ +void * +tor_memdup_nulterm_(const void *mem, size_t len) +{ + char *duplicate; + raw_assert(len < SIZE_T_CEILING+1); + raw_assert(mem); + duplicate = tor_malloc_(len+1); + memcpy(duplicate, mem, len); + duplicate[len] = '\0'; + return duplicate; +} + +/** Helper for places that need to take a function pointer to the right + * spelling of "free()". */ +void +tor_free_(void *mem) +{ + tor_free(mem); +} diff --git a/src/lib/malloc/util_malloc.h b/src/lib/malloc/util_malloc.h new file mode 100644 index 0000000000..88ecc04530 --- /dev/null +++ b/src/lib/malloc/util_malloc.h @@ -0,0 +1,92 @@ +/* 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 util_malloc.h + * \brief Headers for util_malloc.c + **/ + +#ifndef TOR_UTIL_MALLOC_H +#define TOR_UTIL_MALLOC_H + +#include <stddef.h> +#include <stdlib.h> +#include "lib/cc/compat_compiler.h" + +/* Memory management */ +void *tor_malloc_(size_t size) ATTR_MALLOC; +void *tor_malloc_zero_(size_t size) ATTR_MALLOC; +void *tor_calloc_(size_t nmemb, size_t size) ATTR_MALLOC; +void *tor_realloc_(void *ptr, size_t size); +void *tor_reallocarray_(void *ptr, size_t size1, size_t size2); +char *tor_strdup_(const char *s) ATTR_MALLOC ATTR_NONNULL((1)); +char *tor_strndup_(const char *s, size_t n) + ATTR_MALLOC ATTR_NONNULL((1)); +void *tor_memdup_(const void *mem, size_t len) + ATTR_MALLOC ATTR_NONNULL((1)); +void *tor_memdup_nulterm_(const void *mem, size_t len) + ATTR_MALLOC ATTR_NONNULL((1)); +void tor_free_(void *mem); + +/** Release memory allocated by tor_malloc, tor_realloc, tor_strdup, + * etc. Unlike the free() function, the tor_free() macro sets the + * pointer value to NULL after freeing it. + * + * This is a macro. If you need a function pointer to release memory from + * tor_malloc(), use tor_free_(). + * + * Note that this macro takes the address of the pointer it is going to + * free and clear. If that pointer is stored with a nonstandard + * alignment (eg because of a "packed" pragma) it is not correct to use + * tor_free(). + */ +#ifdef __GNUC__ +#define tor_free(p) STMT_BEGIN \ + typeof(&(p)) tor_free__tmpvar = &(p); \ + raw_free(*tor_free__tmpvar); \ + *tor_free__tmpvar=NULL; \ + STMT_END +#else +#define tor_free(p) STMT_BEGIN \ + raw_free(p); \ + (p)=NULL; \ + STMT_END +#endif + +#define tor_malloc(size) tor_malloc_(size) +#define tor_malloc_zero(size) tor_malloc_zero_(size) +#define tor_calloc(nmemb,size) tor_calloc_(nmemb, size) +#define tor_realloc(ptr, size) tor_realloc_(ptr, size) +#define tor_reallocarray(ptr, sz1, sz2) \ + tor_reallocarray_((ptr), (sz1), (sz2)) +#define tor_strdup(s) tor_strdup_(s) +#define tor_strndup(s, n) tor_strndup_(s, n) +#define tor_memdup(s, n) tor_memdup_(s, n) +#define tor_memdup_nulterm(s, n) tor_memdup_nulterm_(s, n) + +/* Aliases for the underlying system malloc/realloc/free. Only use + * them to indicate "I really want the underlying system function, I know + * what I'm doing." */ +#define raw_malloc malloc +#define raw_realloc realloc +#define raw_free free +#define raw_strdup strdup + +/* Helper macro: free a variable of type 'typename' using freefn, and + * set the variable to NULL. + */ +#define FREE_AND_NULL(typename, freefn, var) \ + do { \ + /* only evaluate (var) once. */ \ + typename **tmp__free__ptr ## freefn = &(var); \ + freefn(*tmp__free__ptr ## freefn); \ + (*tmp__free__ptr ## freefn) = NULL; \ + } while (0) + +#ifdef UTIL_MALLOC_PRIVATE +STATIC int size_mul_check(const size_t x, const size_t y); +#endif + +#endif /* !defined(TOR_UTIL_MALLOC_H) */ diff --git a/src/lib/string/.may_include b/src/lib/string/.may_include new file mode 100644 index 0000000000..c5d7718616 --- /dev/null +++ b/src/lib/string/.may_include @@ -0,0 +1,9 @@ +orconfig.h +lib/cc/*.h +lib/err/*.h +lib/malloc/*.h +lib/ctime/*.h +lib/string/*.h + +strlcat.c +strlcpy.c diff --git a/src/lib/string/compat_ctype.c b/src/lib/string/compat_ctype.c new file mode 100644 index 0000000000..d1d4ce0ffc --- /dev/null +++ b/src/lib/string/compat_ctype.c @@ -0,0 +1,67 @@ +/* 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 */ + +#include "lib/string/compat_ctype.h" + +/** + * Tables to implement ctypes-replacement TOR_IS*() functions. Each table + * has 256 bits to look up whether a character is in some set or not. This + * fails on non-ASCII platforms, but it is hard to find a platform whose + * character set is not a superset of ASCII nowadays. */ + +/**@{*/ +const uint32_t TOR_ISALPHA_TABLE[8] = + { 0, 0, 0x7fffffe, 0x7fffffe, 0, 0, 0, 0 }; +const uint32_t TOR_ISALNUM_TABLE[8] = + { 0, 0x3ff0000, 0x7fffffe, 0x7fffffe, 0, 0, 0, 0 }; +const uint32_t TOR_ISSPACE_TABLE[8] = { 0x3e00, 0x1, 0, 0, 0, 0, 0, 0 }; +const uint32_t TOR_ISXDIGIT_TABLE[8] = + { 0, 0x3ff0000, 0x7e, 0x7e, 0, 0, 0, 0 }; +const uint32_t TOR_ISDIGIT_TABLE[8] = { 0, 0x3ff0000, 0, 0, 0, 0, 0, 0 }; +const uint32_t TOR_ISPRINT_TABLE[8] = + { 0, 0xffffffff, 0xffffffff, 0x7fffffff, 0, 0, 0, 0x0 }; +const uint32_t TOR_ISUPPER_TABLE[8] = { 0, 0, 0x7fffffe, 0, 0, 0, 0, 0 }; +const uint32_t TOR_ISLOWER_TABLE[8] = { 0, 0, 0, 0x7fffffe, 0, 0, 0, 0 }; + +/** Upper-casing and lowercasing tables to map characters to upper/lowercase + * equivalents. Used by tor_toupper() and tor_tolower(). */ +/**@{*/ +const uint8_t TOR_TOUPPER_TABLE[256] = { + 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, + 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31, + 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47, + 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63, + 64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79, + 80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95, + 96,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79, + 80,81,82,83,84,85,86,87,88,89,90,123,124,125,126,127, + 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143, + 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159, + 160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175, + 176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191, + 192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207, + 208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223, + 224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239, + 240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255, +}; +const uint8_t TOR_TOLOWER_TABLE[256] = { + 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, + 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31, + 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47, + 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63, + 64,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111, + 112,113,114,115,116,117,118,119,120,121,122,91,92,93,94,95, + 96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111, + 112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127, + 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143, + 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159, + 160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175, + 176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191, + 192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207, + 208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223, + 224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239, + 240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255, +}; +/**@}*/ diff --git a/src/lib/string/compat_ctype.h b/src/lib/string/compat_ctype.h new file mode 100644 index 0000000000..530a10270f --- /dev/null +++ b/src/lib/string/compat_ctype.h @@ -0,0 +1,62 @@ +/* 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_COMPAT_CTYPE_H +#define TOR_COMPAT_CTYPE_H + +#include "orconfig.h" +#include "lib/cc/torint.h" + +/* Much of the time when we're checking ctypes, we're doing spec compliance, + * which all assumes we're doing ASCII. */ +#define DECLARE_CTYPE_FN(name) \ + static int TOR_##name(char c); \ + extern const uint32_t TOR_##name##_TABLE[]; \ + static inline int TOR_##name(char c) { \ + uint8_t u = c; \ + return !!(TOR_##name##_TABLE[(u >> 5) & 7] & (1u << (u & 31))); \ + } +DECLARE_CTYPE_FN(ISALPHA) +DECLARE_CTYPE_FN(ISALNUM) +DECLARE_CTYPE_FN(ISSPACE) +DECLARE_CTYPE_FN(ISDIGIT) +DECLARE_CTYPE_FN(ISXDIGIT) +DECLARE_CTYPE_FN(ISPRINT) +DECLARE_CTYPE_FN(ISLOWER) +DECLARE_CTYPE_FN(ISUPPER) +extern const uint8_t TOR_TOUPPER_TABLE[]; +extern const uint8_t TOR_TOLOWER_TABLE[]; +#define TOR_TOLOWER(c) (TOR_TOLOWER_TABLE[(uint8_t)c]) +#define TOR_TOUPPER(c) (TOR_TOUPPER_TABLE[(uint8_t)c]) + +static inline int hex_decode_digit(char c); + +/** Helper: given a hex digit, return its value, or -1 if it isn't hex. */ +static inline int +hex_decode_digit(char c) +{ + switch (c) { + case '0': return 0; + case '1': return 1; + case '2': return 2; + case '3': return 3; + case '4': return 4; + case '5': return 5; + case '6': return 6; + case '7': return 7; + case '8': return 8; + case '9': return 9; + case 'A': case 'a': return 10; + case 'B': case 'b': return 11; + case 'C': case 'c': return 12; + case 'D': case 'd': return 13; + case 'E': case 'e': return 14; + case 'F': case 'f': return 15; + default: + return -1; + } +} + +#endif /* !defined(TOR_COMPAT_CTYPE_H) */ diff --git a/src/lib/string/compat_string.c b/src/lib/string/compat_string.c new file mode 100644 index 0000000000..6df1bc4a1d --- /dev/null +++ b/src/lib/string/compat_string.c @@ -0,0 +1,14 @@ +/* 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 */ + +#include "lib/string/compat_string.h" + +/* Inline the strl functions if the platform doesn't have them. */ +#ifndef HAVE_STRLCPY +#include "strlcpy.c" +#endif +#ifndef HAVE_STRLCAT +#include "strlcat.c" +#endif diff --git a/src/lib/string/compat_string.h b/src/lib/string/compat_string.h new file mode 100644 index 0000000000..212d08b7ae --- /dev/null +++ b/src/lib/string/compat_string.h @@ -0,0 +1,39 @@ +/* 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_COMPAT_STRING_H +#define TOR_COMPAT_STRING_H + +#include "orconfig.h" +#include "lib/cc/compat_compiler.h" + +#include <stddef.h> + +/* ===== String compatibility */ +#ifdef _WIN32 +/* Windows names string functions differently from most other platforms. */ +#define strncasecmp _strnicmp +#define strcasecmp _stricmp +#endif + +#if defined __APPLE__ +/* On OSX 10.9 and later, the overlap-checking code for strlcat would + * appear to have a severe bug that can sometimes cause aborts in Tor. + * Instead, use the non-checking variants. This is sad. + * + * See https://trac.torproject.org/projects/tor/ticket/15205 + */ +#undef strlcat +#undef strlcpy +#endif /* defined __APPLE__ */ + +#ifndef HAVE_STRLCAT +size_t strlcat(char *dst, const char *src, size_t siz) ATTR_NONNULL((1,2)); +#endif +#ifndef HAVE_STRLCPY +size_t strlcpy(char *dst, const char *src, size_t siz) ATTR_NONNULL((1,2)); +#endif + +#endif diff --git a/src/lib/string/include.am b/src/lib/string/include.am new file mode 100644 index 0000000000..e532d5030f --- /dev/null +++ b/src/lib/string/include.am @@ -0,0 +1,25 @@ + +noinst_LIBRARIES += src/lib/libtor-string.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-string-testing.a +endif + +src_lib_libtor_string_a_SOURCES = \ + src/lib/string/compat_ctype.c \ + src/lib/string/compat_string.c \ + src/lib/string/util_string.c \ + src/lib/string/printf.c \ + src/lib/string/scanf.c + +src_lib_libtor_string_testing_a_SOURCES = \ + $(src_lib_libtor_string_a_SOURCES) +src_lib_libtor_string_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_string_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/string/compat_ctype.h \ + src/lib/string/compat_string.h \ + src/lib/string/util_string.h \ + src/lib/string/printf.h \ + src/lib/string/scanf.h diff --git a/src/lib/string/printf.c b/src/lib/string/printf.c new file mode 100644 index 0000000000..4443e25fb4 --- /dev/null +++ b/src/lib/string/printf.c @@ -0,0 +1,152 @@ +/* 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 */ + +#include "lib/string/printf.h" +#include "lib/err/torerr.h" +#include "lib/cc/torint.h" +#include "lib/malloc/util_malloc.h" + +#include <stdlib.h> +#include <stdio.h> + +/** Replacement for snprintf. Differs from platform snprintf in two + * ways: First, always NUL-terminates its output. Second, always + * returns -1 if the result is truncated. (Note that this return + * behavior does <i>not</i> conform to C99; it just happens to be + * easier to emulate "return -1" with conformant implementations than + * it is to emulate "return number that would be written" with + * non-conformant implementations.) */ +int +tor_snprintf(char *str, size_t size, const char *format, ...) +{ + va_list ap; + int r; + va_start(ap,format); + r = tor_vsnprintf(str,size,format,ap); + va_end(ap); + return r; +} + +/** Replacement for vsnprintf; behavior differs as tor_snprintf differs from + * snprintf. + */ +int +tor_vsnprintf(char *str, size_t size, const char *format, va_list args) +{ + int r; + if (size == 0) + return -1; /* no place for the NUL */ + if (size > SIZE_T_CEILING) + return -1; +#ifdef _WIN32 + r = _vsnprintf(str, size, format, args); +#else + r = vsnprintf(str, size, format, args); +#endif + str[size-1] = '\0'; + if (r < 0 || r >= (ssize_t)size) + return -1; + return r; +} + +/** + * Portable asprintf implementation. Does a printf() into a newly malloc'd + * string. Sets *<b>strp</b> to this string, and returns its length (not + * including the terminating NUL character). + * + * You can treat this function as if its implementation were something like + <pre> + char buf[_INFINITY_]; + tor_snprintf(buf, sizeof(buf), fmt, args); + *strp = tor_strdup(buf); + return strlen(*strp): + </pre> + * Where _INFINITY_ is an imaginary constant so big that any string can fit + * into it. + */ +int +tor_asprintf(char **strp, const char *fmt, ...) +{ + int r; + va_list args; + va_start(args, fmt); + r = tor_vasprintf(strp, fmt, args); + va_end(args); + if (!*strp || r < 0) { + /* LCOV_EXCL_START */ + raw_assert_unreached_msg("Internal error in asprintf"); + /* LCOV_EXCL_STOP */ + } + return r; +} + +/** + * Portable vasprintf implementation. Does a printf() into a newly malloc'd + * string. Differs from regular vasprintf in the same ways that + * tor_asprintf() differs from regular asprintf. + */ +int +tor_vasprintf(char **strp, const char *fmt, va_list args) +{ + /* use a temporary variable in case *strp is in args. */ + char *strp_tmp=NULL; +#ifdef HAVE_VASPRINTF + /* If the platform gives us one, use it. */ + int r = vasprintf(&strp_tmp, fmt, args); + if (r < 0) + *strp = NULL; + else + *strp = strp_tmp; + return r; +#elif defined(HAVE__VSCPRINTF) + /* On Windows, _vsnprintf won't tell us the length of the string if it + * overflows, so we need to use _vcsprintf to tell how much to allocate */ + int len, r; + va_list tmp_args; + va_copy(tmp_args, args); + len = _vscprintf(fmt, tmp_args); + va_end(tmp_args); + if (len < 0) { + *strp = NULL; + return -1; + } + strp_tmp = tor_malloc(len + 1); + r = _vsnprintf(strp_tmp, len+1, fmt, args); + if (r != len) { + tor_free(strp_tmp); + *strp = NULL; + return -1; + } + *strp = strp_tmp; + return len; +#else + /* Everywhere else, we have a decent vsnprintf that tells us how many + * characters we need. We give it a try on a short buffer first, since + * it might be nice to avoid the second vsnprintf call. + */ + char buf[128]; + int len, r; + va_list tmp_args; + va_copy(tmp_args, args); + /* vsnprintf() was properly checked but tor_vsnprintf() available so + * why not use it? */ + len = tor_vsnprintf(buf, sizeof(buf), fmt, tmp_args); + va_end(tmp_args); + if (len < (int)sizeof(buf)) { + *strp = tor_strdup(buf); + return len; + } + strp_tmp = tor_malloc(len+1); + /* use of tor_vsnprintf() will ensure string is null terminated */ + r = tor_vsnprintf(strp_tmp, len+1, fmt, args); + if (r != len) { + tor_free(strp_tmp); + *strp = NULL; + return -1; + } + *strp = strp_tmp; + return len; +#endif /* defined(HAVE_VASPRINTF) || ... */ +} diff --git a/src/lib/string/printf.h b/src/lib/string/printf.h new file mode 100644 index 0000000000..2f46206545 --- /dev/null +++ b/src/lib/string/printf.h @@ -0,0 +1,25 @@ +/* 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_UTIL_PRINTF_H +#define TOR_UTIL_PRINTF_H + +#include "orconfig.h" +#include "lib/cc/compat_compiler.h" + +#include <stdarg.h> +#include <stddef.h> + +int tor_snprintf(char *str, size_t size, const char *format, ...) + CHECK_PRINTF(3,4) ATTR_NONNULL((1,3)); +int tor_vsnprintf(char *str, size_t size, const char *format, va_list args) + CHECK_PRINTF(3,0) ATTR_NONNULL((1,3)); + +int tor_asprintf(char **strp, const char *fmt, ...) + CHECK_PRINTF(2,3); +int tor_vasprintf(char **strp, const char *fmt, va_list args) + CHECK_PRINTF(2,0); + +#endif /* !defined(TOR_UTIL_STRING_H) */ diff --git a/src/lib/string/scanf.c b/src/lib/string/scanf.c new file mode 100644 index 0000000000..0c5082799c --- /dev/null +++ b/src/lib/string/scanf.c @@ -0,0 +1,312 @@ +/* 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 */ + +#include "lib/string/scanf.h" +#include "lib/string/compat_ctype.h" +#include "lib/cc/torint.h" +#include "lib/err/torerr.h" + +#include <stdlib.h> + +#define MAX_SCANF_WIDTH 9999 + +/** Helper: given an ASCII-encoded decimal digit, return its numeric value. + * NOTE: requires that its input be in-bounds. */ +static int +digit_to_num(char d) +{ + int num = ((int)d) - (int)'0'; + raw_assert(num <= 9 && num >= 0); + return num; +} + +/** Helper: Read an unsigned int from *<b>bufp</b> of up to <b>width</b> + * characters. (Handle arbitrary width if <b>width</b> is less than 0.) On + * success, store the result in <b>out</b>, advance bufp to the next + * character, and return 0. On failure, return -1. */ +static int +scan_unsigned(const char **bufp, unsigned long *out, int width, unsigned base) +{ + unsigned long result = 0; + int scanned_so_far = 0; + const int hex = base==16; + raw_assert(base == 10 || base == 16); + if (!bufp || !*bufp || !out) + return -1; + if (width<0) + width=MAX_SCANF_WIDTH; + + while (**bufp && (hex?TOR_ISXDIGIT(**bufp):TOR_ISDIGIT(**bufp)) + && scanned_so_far < width) { + unsigned digit = hex?hex_decode_digit(*(*bufp)++):digit_to_num(*(*bufp)++); + // Check for overflow beforehand, without actually causing any overflow + // This preserves functionality on compilers that don't wrap overflow + // (i.e. that trap or optimise away overflow) + // result * base + digit > ULONG_MAX + // result * base > ULONG_MAX - digit + if (result > (ULONG_MAX - digit)/base) + return -1; /* Processing this digit would overflow */ + result = result * base + digit; + ++scanned_so_far; + } + + if (!scanned_so_far) /* No actual digits scanned */ + return -1; + + *out = result; + return 0; +} + +/** Helper: Read an signed int from *<b>bufp</b> of up to <b>width</b> + * characters. (Handle arbitrary width if <b>width</b> is less than 0.) On + * success, store the result in <b>out</b>, advance bufp to the next + * character, and return 0. On failure, return -1. */ +static int +scan_signed(const char **bufp, long *out, int width) +{ + int neg = 0; + unsigned long result = 0; + + if (!bufp || !*bufp || !out) + return -1; + if (width<0) + width=MAX_SCANF_WIDTH; + + if (**bufp == '-') { + neg = 1; + ++*bufp; + --width; + } + + if (scan_unsigned(bufp, &result, width, 10) < 0) + return -1; + + if (neg && result > 0) { + if (result > ((unsigned long)LONG_MAX) + 1) + return -1; /* Underflow */ + else if (result == ((unsigned long)LONG_MAX) + 1) + *out = LONG_MIN; + else { + /* We once had a far more clever no-overflow conversion here, but + * some versions of GCC apparently ran it into the ground. Now + * we just check for LONG_MIN explicitly. + */ + *out = -(long)result; + } + } else { + if (result > LONG_MAX) + return -1; /* Overflow */ + *out = (long)result; + } + + return 0; +} + +/** Helper: Read a decimal-formatted double from *<b>bufp</b> of up to + * <b>width</b> characters. (Handle arbitrary width if <b>width</b> is less + * than 0.) On success, store the result in <b>out</b>, advance bufp to the + * next character, and return 0. On failure, return -1. */ +static int +scan_double(const char **bufp, double *out, int width) +{ + int neg = 0; + double result = 0; + int scanned_so_far = 0; + + if (!bufp || !*bufp || !out) + return -1; + if (width<0) + width=MAX_SCANF_WIDTH; + + if (**bufp == '-') { + neg = 1; + ++*bufp; + } + + while (**bufp && TOR_ISDIGIT(**bufp) && scanned_so_far < width) { + const int digit = digit_to_num(*(*bufp)++); + result = result * 10 + digit; + ++scanned_so_far; + } + if (**bufp == '.') { + double fracval = 0, denominator = 1; + ++*bufp; + ++scanned_so_far; + while (**bufp && TOR_ISDIGIT(**bufp) && scanned_so_far < width) { + const int digit = digit_to_num(*(*bufp)++); + fracval = fracval * 10 + digit; + denominator *= 10; + ++scanned_so_far; + } + result += fracval / denominator; + } + + if (!scanned_so_far) /* No actual digits scanned */ + return -1; + + *out = neg ? -result : result; + return 0; +} + +/** Helper: copy up to <b>width</b> non-space characters from <b>bufp</b> to + * <b>out</b>. Make sure <b>out</b> is nul-terminated. Advance <b>bufp</b> + * to the next non-space character or the EOS. */ +static int +scan_string(const char **bufp, char *out, int width) +{ + int scanned_so_far = 0; + if (!bufp || !out || width < 0) + return -1; + while (**bufp && ! TOR_ISSPACE(**bufp) && scanned_so_far < width) { + *out++ = *(*bufp)++; + ++scanned_so_far; + } + *out = '\0'; + return 0; +} + +/** Locale-independent, minimal, no-surprises scanf variant, accepting only a + * restricted pattern format. For more info on what it supports, see + * tor_sscanf() documentation. */ +int +tor_vsscanf(const char *buf, const char *pattern, va_list ap) +{ + int n_matched = 0; + + while (*pattern) { + if (*pattern != '%') { + if (*buf == *pattern) { + ++buf; + ++pattern; + continue; + } else { + return n_matched; + } + } else { + int width = -1; + int longmod = 0; + ++pattern; + if (TOR_ISDIGIT(*pattern)) { + width = digit_to_num(*pattern++); + while (TOR_ISDIGIT(*pattern)) { + width *= 10; + width += digit_to_num(*pattern++); + if (width > MAX_SCANF_WIDTH) + return -1; + } + if (!width) /* No zero-width things. */ + return -1; + } + if (*pattern == 'l') { + longmod = 1; + ++pattern; + } + if (*pattern == 'u' || *pattern == 'x') { + unsigned long u; + const int base = (*pattern == 'u') ? 10 : 16; + if (!*buf) + return n_matched; + if (scan_unsigned(&buf, &u, width, base)<0) + return n_matched; + if (longmod) { + unsigned long *out = va_arg(ap, unsigned long *); + *out = u; + } else { + unsigned *out = va_arg(ap, unsigned *); + if (u > UINT_MAX) + return n_matched; + *out = (unsigned) u; + } + ++pattern; + ++n_matched; + } else if (*pattern == 'f') { + double *d = va_arg(ap, double *); + if (!longmod) + return -1; /* float not supported */ + if (!*buf) + return n_matched; + if (scan_double(&buf, d, width)<0) + return n_matched; + ++pattern; + ++n_matched; + } else if (*pattern == 'd') { + long lng=0; + if (scan_signed(&buf, &lng, width)<0) + return n_matched; + if (longmod) { + long *out = va_arg(ap, long *); + *out = lng; + } else { + int *out = va_arg(ap, int *); +#if LONG_MAX > INT_MAX + if (lng < INT_MIN || lng > INT_MAX) + return n_matched; +#endif + *out = (int)lng; + } + ++pattern; + ++n_matched; + } else if (*pattern == 's') { + char *s = va_arg(ap, char *); + if (longmod) + return -1; + if (width < 0) + return -1; + if (scan_string(&buf, s, width)<0) + return n_matched; + ++pattern; + ++n_matched; + } else if (*pattern == 'c') { + char *ch = va_arg(ap, char *); + if (longmod) + return -1; + if (width != -1) + return -1; + if (!*buf) + return n_matched; + *ch = *buf++; + ++pattern; + ++n_matched; + } else if (*pattern == '%') { + if (*buf != '%') + return n_matched; + if (longmod) + return -1; + ++buf; + ++pattern; + } else { + return -1; /* Unrecognized pattern component. */ + } + } + } + + return n_matched; +} + +/** Minimal sscanf replacement: parse <b>buf</b> according to <b>pattern</b> + * and store the results in the corresponding argument fields. Differs from + * sscanf in that: + * <ul><li>It only handles %u, %lu, %x, %lx, %[NUM]s, %d, %ld, %lf, and %c. + * <li>It only handles decimal inputs for %lf. (12.3, not 1.23e1) + * <li>It does not handle arbitrarily long widths. + * <li>Numbers do not consume any space characters. + * <li>It is locale-independent. + * <li>%u and %x do not consume any space. + * <li>It returns -1 on malformed patterns.</ul> + * + * (As with other locale-independent functions, we need this to parse data that + * is in ASCII without worrying that the C library's locale-handling will make + * miscellaneous characters look like numbers, spaces, and so on.) + */ +int +tor_sscanf(const char *buf, const char *pattern, ...) +{ + int r; + va_list ap; + va_start(ap, pattern); + r = tor_vsscanf(buf, pattern, ap); + va_end(ap); + return r; +} diff --git a/src/lib/string/scanf.h b/src/lib/string/scanf.h new file mode 100644 index 0000000000..9cfa9cc6c1 --- /dev/null +++ b/src/lib/string/scanf.h @@ -0,0 +1,19 @@ +/* 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_UTIL_SCANF_H +#define TOR_UTIL_SCANF_H + +#include "orconfig.h" +#include "lib/cc/compat_compiler.h" + +#include <stdarg.h> + +int tor_vsscanf(const char *buf, const char *pattern, va_list ap) \ + CHECK_SCANF(2, 0); +int tor_sscanf(const char *buf, const char *pattern, ...) + CHECK_SCANF(2, 3); + +#endif /* !defined(TOR_UTIL_STRING_H) */ diff --git a/src/lib/string/util_string.c b/src/lib/string/util_string.c new file mode 100644 index 0000000000..aba37fcc00 --- /dev/null +++ b/src/lib/string/util_string.c @@ -0,0 +1,340 @@ +/* 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 */ + +#include "lib/string/util_string.h" +#include "lib/string/compat_ctype.h" +#include "lib/err/torerr.h" +#include "lib/ctime/di_ops.h" + +#include <string.h> +#include <stdlib.h> + +/** Remove from the string <b>s</b> every character which appears in + * <b>strip</b>. */ +void +tor_strstrip(char *s, const char *strip) +{ + char *readp = s; + while (*readp) { + if (strchr(strip, *readp)) { + ++readp; + } else { + *s++ = *readp++; + } + } + *s = '\0'; +} + +/** Convert all alphabetic characters in the nul-terminated string <b>s</b> to + * lowercase. */ +void +tor_strlower(char *s) +{ + while (*s) { + *s = TOR_TOLOWER(*s); + ++s; + } +} + +/** Convert all alphabetic characters in the nul-terminated string <b>s</b> to + * lowercase. */ +void +tor_strupper(char *s) +{ + while (*s) { + *s = TOR_TOUPPER(*s); + ++s; + } +} + +/** Return 1 if every character in <b>s</b> is printable, else return 0. + */ +int +tor_strisprint(const char *s) +{ + while (*s) { + if (!TOR_ISPRINT(*s)) + return 0; + s++; + } + return 1; +} + +/** Return 1 if no character in <b>s</b> is uppercase, else return 0. + */ +int +tor_strisnonupper(const char *s) +{ + while (*s) { + if (TOR_ISUPPER(*s)) + return 0; + s++; + } + return 1; +} + +/** Return true iff every character in <b>s</b> is whitespace space; else + * return false. */ +int +tor_strisspace(const char *s) +{ + while (*s) { + if (!TOR_ISSPACE(*s)) + return 0; + s++; + } + return 1; +} + +/** As strcmp, except that either string may be NULL. The NULL string is + * considered to be before any non-NULL string. */ +int +strcmp_opt(const char *s1, const char *s2) +{ + if (!s1) { + if (!s2) + return 0; + else + return -1; + } else if (!s2) { + return 1; + } else { + return strcmp(s1, s2); + } +} + +/** Compares the first strlen(s2) characters of s1 with s2. Returns as for + * strcmp. + */ +int +strcmpstart(const char *s1, const char *s2) +{ + size_t n = strlen(s2); + return strncmp(s1, s2, n); +} + +/** Compare the s1_len-byte string <b>s1</b> with <b>s2</b>, + * without depending on a terminating nul in s1. Sorting order is first by + * length, then lexically; return values are as for strcmp. + */ +int +strcmp_len(const char *s1, const char *s2, size_t s1_len) +{ + size_t s2_len = strlen(s2); + if (s1_len < s2_len) + return -1; + if (s1_len > s2_len) + return 1; + return fast_memcmp(s1, s2, s2_len); +} + +/** Compares the first strlen(s2) characters of s1 with s2. Returns as for + * strcasecmp. + */ +int +strcasecmpstart(const char *s1, const char *s2) +{ + size_t n = strlen(s2); + return strncasecmp(s1, s2, n); +} + +/** Compares the last strlen(s2) characters of s1 with s2. Returns as for + * strcmp. + */ +int +strcmpend(const char *s1, const char *s2) +{ + size_t n1 = strlen(s1), n2 = strlen(s2); + if (n2>n1) + return strcmp(s1,s2); + else + return strncmp(s1+(n1-n2), s2, n2); +} + +/** Compares the last strlen(s2) characters of s1 with s2. Returns as for + * strcasecmp. + */ +int +strcasecmpend(const char *s1, const char *s2) +{ + size_t n1 = strlen(s1), n2 = strlen(s2); + if (n2>n1) /* then they can't be the same; figure out which is bigger */ + return strcasecmp(s1,s2); + else + return strncasecmp(s1+(n1-n2), s2, n2); +} + +/** Return a pointer to the first char of s that is not whitespace and + * not a comment, or to the terminating NUL if no such character exists. + */ +const char * +eat_whitespace(const char *s) +{ + raw_assert(s); + + while (1) { + switch (*s) { + case '\0': + default: + return s; + case ' ': + case '\t': + case '\n': + case '\r': + ++s; + break; + case '#': + ++s; + while (*s && *s != '\n') + ++s; + } + } +} + +/** Return a pointer to the first char of s that is not whitespace and + * not a comment, or to the terminating NUL if no such character exists. + */ +const char * +eat_whitespace_eos(const char *s, const char *eos) +{ + raw_assert(s); + raw_assert(eos && s <= eos); + + while (s < eos) { + switch (*s) { + case '\0': + default: + return s; + case ' ': + case '\t': + case '\n': + case '\r': + ++s; + break; + case '#': + ++s; + while (s < eos && *s && *s != '\n') + ++s; + } + } + return s; +} + +/** Return a pointer to the first char of s that is not a space or a tab + * or a \\r, or to the terminating NUL if no such character exists. */ +const char * +eat_whitespace_no_nl(const char *s) +{ + while (*s == ' ' || *s == '\t' || *s == '\r') + ++s; + return s; +} + +/** As eat_whitespace_no_nl, but stop at <b>eos</b> whether we have + * found a non-whitespace character or not. */ +const char * +eat_whitespace_eos_no_nl(const char *s, const char *eos) +{ + while (s < eos && (*s == ' ' || *s == '\t' || *s == '\r')) + ++s; + return s; +} + +/** Return a pointer to the first char of s that is whitespace or <b>#</b>, + * or to the terminating NUL if no such character exists. + */ +const char * +find_whitespace(const char *s) +{ + /* tor_assert(s); */ + while (1) { + switch (*s) + { + case '\0': + case '#': + case ' ': + case '\r': + case '\n': + case '\t': + return s; + default: + ++s; + } + } +} + +/** As find_whitespace, but stop at <b>eos</b> whether we have found a + * whitespace or not. */ +const char * +find_whitespace_eos(const char *s, const char *eos) +{ + /* tor_assert(s); */ + while (s < eos) { + switch (*s) + { + case '\0': + case '#': + case ' ': + case '\r': + case '\n': + case '\t': + return s; + default: + ++s; + } + } + return s; +} + +/** Return the first occurrence of <b>needle</b> in <b>haystack</b> that + * occurs at the start of a line (that is, at the beginning of <b>haystack</b> + * or immediately after a newline). Return NULL if no such string is found. + */ +const char * +find_str_at_start_of_line(const char *haystack, const char *needle) +{ + size_t needle_len = strlen(needle); + + do { + if (!strncmp(haystack, needle, needle_len)) + return haystack; + + haystack = strchr(haystack, '\n'); + if (!haystack) + return NULL; + else + ++haystack; + } while (*haystack); + + return NULL; +} + +/** Returns true if <b>string</b> could be a C identifier. + A C identifier must begin with a letter or an underscore and the + rest of its characters can be letters, numbers or underscores. No + length limit is imposed. */ +int +string_is_C_identifier(const char *string) +{ + size_t iter; + size_t length = strlen(string); + if (!length) + return 0; + + for (iter = 0; iter < length ; iter++) { + if (iter == 0) { + if (!(TOR_ISALPHA(string[iter]) || + string[iter] == '_')) + return 0; + } else { + if (!(TOR_ISALPHA(string[iter]) || + TOR_ISDIGIT(string[iter]) || + string[iter] == '_')) + return 0; + } + } + + return 1; +} diff --git a/src/lib/string/util_string.h b/src/lib/string/util_string.h new file mode 100644 index 0000000000..f194c36373 --- /dev/null +++ b/src/lib/string/util_string.h @@ -0,0 +1,42 @@ +/* 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_UTIL_STRING_H +#define TOR_UTIL_STRING_H + +#include "orconfig.h" +#include "lib/cc/compat_compiler.h" + +#include <stddef.h> + +/** Allowable characters in a hexadecimal string. */ +#define HEX_CHARACTERS "0123456789ABCDEFabcdef" +void tor_strlower(char *s) ATTR_NONNULL((1)); +void tor_strupper(char *s) ATTR_NONNULL((1)); +int tor_strisprint(const char *s) ATTR_NONNULL((1)); +int tor_strisnonupper(const char *s) ATTR_NONNULL((1)); +int tor_strisspace(const char *s); +int strcmp_opt(const char *s1, const char *s2); +int strcmpstart(const char *s1, const char *s2) ATTR_NONNULL((1,2)); +int strcmp_len(const char *s1, const char *s2, size_t len) ATTR_NONNULL((1,2)); +int strcasecmpstart(const char *s1, const char *s2) ATTR_NONNULL((1,2)); +int strcmpend(const char *s1, const char *s2) ATTR_NONNULL((1,2)); +int strcasecmpend(const char *s1, const char *s2) ATTR_NONNULL((1,2)); +int fast_memcmpstart(const void *mem, size_t memlen, const char *prefix); + +void tor_strstrip(char *s, const char *strip) ATTR_NONNULL((1,2)); + +const char *eat_whitespace(const char *s); +const char *eat_whitespace_eos(const char *s, const char *eos); +const char *eat_whitespace_no_nl(const char *s); +const char *eat_whitespace_eos_no_nl(const char *s, const char *eos); +const char *find_whitespace(const char *s); +const char *find_whitespace_eos(const char *s, const char *eos); +const char *find_str_at_start_of_line(const char *haystack, + const char *needle); + +int string_is_C_identifier(const char *string); + +#endif /* !defined(TOR_UTIL_STRING_H) */ diff --git a/src/lib/tls/.may_include b/src/lib/tls/.may_include index 22792b6bfc..a2d84165f0 100644 --- a/src/lib/tls/.may_include +++ b/src/lib/tls/.may_include @@ -1,9 +1,11 @@ orconfig.h lib/cc/*.h +lib/container/*.h lib/crypt_ops/*.h lib/err/*.h lib/testsupport/testsupport.h lib/tls/*.h +lib/log/*.h ciphers.inc diff --git a/src/lib/tls/buffers_tls.c b/src/lib/tls/buffers_tls.c index 55c3ac334b..ac78b6501b 100644 --- a/src/lib/tls/buffers_tls.c +++ b/src/lib/tls/buffers_tls.c @@ -12,7 +12,7 @@ #include "common/compat.h" #include "common/util.h" #include "lib/cc/torint.h" -#include "common/torlog.h" +#include "lib/log/torlog.h" #include "lib/tls/tortls.h" #ifdef HAVE_UNISTD_H #include <unistd.h> diff --git a/src/lib/tls/tortls.c b/src/lib/tls/tortls.c index ac45175c7d..6fa0611f1d 100644 --- a/src/lib/tls/tortls.c +++ b/src/lib/tls/tortls.c @@ -54,8 +54,8 @@ ENABLE_GCC_WARNING(redundant-decls) #define TORTLS_PRIVATE #include "lib/tls/tortls.h" #include "common/util.h" -#include "common/torlog.h" -#include "common/container.h" +#include "lib/log/torlog.h" +#include "lib/container/smartlist.h" #include <string.h> #ifdef OPENSSL_1_1_API diff --git a/src/lib/trace/.may_include b/src/lib/trace/.may_include index 694c8405ec..45cd13676b 100644 --- a/src/lib/trace/.may_include +++ b/src/lib/trace/.may_include @@ -1,5 +1,3 @@ orconfig.h +lib/log/*.h lib/trace/*.h - -# XXXX -common/torlog.h diff --git a/src/lib/trace/debug.h b/src/lib/trace/debug.h index 0241f2ccf8..9b5d9d05c8 100644 --- a/src/lib/trace/debug.h +++ b/src/lib/trace/debug.h @@ -4,7 +4,7 @@ #ifndef TOR_TRACE_LOG_DEBUG_H #define TOR_TRACE_LOG_DEBUG_H -#include "common/torlog.h" +#include "lib/log/torlog.h" /* Stringify pre-processor trick. */ #define XSTR(d) STR(d) diff --git a/src/lib/wallclock/.may_include b/src/lib/wallclock/.may_include new file mode 100644 index 0000000000..dc010da063 --- /dev/null +++ b/src/lib/wallclock/.may_include @@ -0,0 +1,6 @@ +orconfig.h +lib/cc/*.h +lib/err/*.h +lib/wallclock/*.h +lib/string/*.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 0000000000..2528954f13 --- /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 0000000000..c57ff5bcd3 --- /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 0000000000..7b735e97ee --- /dev/null +++ b/src/lib/wallclock/include.am @@ -0,0 +1,21 @@ + +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/tm_cvt.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/tm_cvt.h \ + src/lib/wallclock/tor_gettimeofday.h diff --git a/src/lib/wallclock/tm_cvt.c b/src/lib/wallclock/tm_cvt.c new file mode 100644 index 0000000000..987b0ffebf --- /dev/null +++ b/src/lib/wallclock/tm_cvt.c @@ -0,0 +1,195 @@ +/* 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 */ + +#include "orconfig.h" +#include "lib/cc/torint.h" +#include "lib/cc/compat_compiler.h" +#include "lib/wallclock/tm_cvt.h" +#include "lib/string/printf.h" +#include "lib/err/torerr.h" + +#include <errno.h> +#include <time.h> +#include <string.h> +#include <stdlib.h> + +#if !defined(_WIN32) +/** Defined iff we need to add locks when defining fake versions of reentrant + * versions of time-related functions. */ +#define TIME_FNS_NEED_LOCKS +#endif + +/** Helper: Deal with confused or out-of-bounds values from localtime_r and + * friends. (On some platforms, they can give out-of-bounds values or can + * return NULL.) If <b>islocal</b>, this is a localtime result; otherwise + * it's from gmtime. The function returns <b>r</b>, when given <b>timep</b> + * as its input. If we need to store new results, store them in + * <b>resultbuf</b>. */ +static struct tm * +correct_tm(int islocal, const time_t *timep, struct tm *resultbuf, + struct tm *r, char **err_out) +{ + const char *outcome; + + if (PREDICT_LIKELY(r)) { + /* We can't strftime dates after 9999 CE, and we want to avoid dates + * before 1 CE (avoiding the year 0 issue and negative years). */ + if (r->tm_year > 8099) { + r->tm_year = 8099; + r->tm_mon = 11; + r->tm_mday = 31; + r->tm_yday = 364; + r->tm_wday = 6; + r->tm_hour = 23; + r->tm_min = 59; + r->tm_sec = 59; + } else if (r->tm_year < (1-1900)) { + r->tm_year = (1-1900); + r->tm_mon = 0; + r->tm_mday = 1; + r->tm_yday = 0; + r->tm_wday = 0; + r->tm_hour = 0; + r->tm_min = 0; + r->tm_sec = 0; + } + return r; + } + + /* If we get here, gmtime or localtime returned NULL. It might have done + * this because of overrun or underrun, or it might have done it because of + * some other weird issue. */ + if (timep) { + if (*timep < 0) { + r = resultbuf; + r->tm_year = 70; /* 1970 CE */ + r->tm_mon = 0; + r->tm_mday = 1; + r->tm_yday = 0; + r->tm_wday = 0; + r->tm_hour = 0; + r->tm_min = 0 ; + r->tm_sec = 0; + outcome = "Rounding up to 1970"; + goto done; + } else if (*timep >= INT32_MAX) { + /* Rounding down to INT32_MAX isn't so great, but keep in mind that we + * only do it if gmtime/localtime tells us NULL. */ + r = resultbuf; + r->tm_year = 137; /* 2037 CE */ + r->tm_mon = 11; + r->tm_mday = 31; + r->tm_yday = 364; + r->tm_wday = 6; + r->tm_hour = 23; + r->tm_min = 59; + r->tm_sec = 59; + outcome = "Rounding down to 2037"; + goto done; + } + } + + /* If we get here, then gmtime/localtime failed without getting an extreme + * value for *timep */ + /* LCOV_EXCL_START */ + r = resultbuf; + memset(resultbuf, 0, sizeof(struct tm)); + outcome="can't recover"; + /* LCOV_EXCL_STOP */ + done: + if (err_out) { + tor_asprintf(err_out, "%s("I64_FORMAT") failed with error %s: %s", + islocal?"localtime":"gmtime", + timep?I64_PRINTF_ARG(*timep):0, + strerror(errno), + outcome); + } + return r; +} + +/** @{ */ +/** As localtime_r, but defined for platforms that don't have it: + * + * Convert *<b>timep</b> to a struct tm in local time, and store the value in + * *<b>result</b>. Return the result on success, or NULL on failure. + */ +#ifdef HAVE_LOCALTIME_R +struct tm * +tor_localtime_r_msg(const time_t *timep, struct tm *result, char **err_out) +{ + struct tm *r; + r = localtime_r(timep, result); + return correct_tm(1, timep, result, r, err_out); +} +#elif defined(TIME_FNS_NEED_LOCKS) +struct tm * +tor_localtime_r_msg(const time_t *timep, struct tm *result, char **err_out) +{ + struct tm *r; + static tor_mutex_t *m=NULL; + if (!m) { m=tor_mutex_new(); } + raw_assert(result); + tor_mutex_acquire(m); + r = localtime(timep); + if (r) + memcpy(result, r, sizeof(struct tm)); + tor_mutex_release(m); + return correct_tm(1, timep, result, r, err_out); +} +#else +struct tm * +tor_localtime_r_msg(const time_t *timep, struct tm *result, char **err_out) +{ + struct tm *r; + raw_assert(result); + r = localtime(timep); + if (r) + memcpy(result, r, sizeof(struct tm)); + return correct_tm(1, timep, result, r, err_out); +} +#endif /* defined(HAVE_LOCALTIME_R) || ... */ +/** @} */ + +/** @{ */ +/** As gmtime_r, but defined for platforms that don't have it: + * + * Convert *<b>timep</b> to a struct tm in UTC, and store the value in + * *<b>result</b>. Return the result on success, or NULL on failure. + */ +#ifdef HAVE_GMTIME_R +struct tm * +tor_gmtime_r_msg(const time_t *timep, struct tm *result, char **err_out) +{ + struct tm *r; + r = gmtime_r(timep, result); + return correct_tm(0, timep, result, r, err_out); +} +#elif defined(TIME_FNS_NEED_LOCKS) +struct tm * +tor_gmtime_r_msg(const time_t *timep, struct tm *result, char **err_out) +{ + struct tm *r; + static tor_mutex_t *m=NULL; + if (!m) { m=tor_mutex_new(); } + raw_assert(result); + tor_mutex_acquire(m); + r = gmtime(timep); + if (r) + memcpy(result, r, sizeof(struct tm)); + tor_mutex_release(m); + return correct_tm(0, timep, result, r, err_out); +} +#else +struct tm * +tor_gmtime_r_msg(const time_t *timep, struct tm *result, char **err_out) +{ + struct tm *r; + raw_assert(result); + r = gmtime(timep); + if (r) + memcpy(result, r, sizeof(struct tm)); + return correct_tm(0, timep, result, r, err_out); +} +#endif /* defined(HAVE_GMTIME_R) || ... */ diff --git a/src/lib/wallclock/tm_cvt.h b/src/lib/wallclock/tm_cvt.h new file mode 100644 index 0000000000..4d87acd4fa --- /dev/null +++ b/src/lib/wallclock/tm_cvt.h @@ -0,0 +1,17 @@ +/* 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_WALLCLOCK_TM_CVT_H +#define TOR_WALLCLOCK_TM_CVT_H + +#include <sys/types.h> + +struct tm; +struct tm *tor_localtime_r_msg(const time_t *timep, struct tm *result, + char **err_out); +struct tm *tor_gmtime_r_msg(const time_t *timep, struct tm *result, + char **err_out); + +#endif diff --git a/src/lib/wallclock/tor_gettimeofday.c b/src/lib/wallclock/tor_gettimeofday.c new file mode 100644 index 0000000000..74a6405720 --- /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 "lib/cc/torint.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 */ + raw_assert_unreached_msg("System time is before 1970; failing."); + /* 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 0000000000..728ad9565d --- /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 |