From f6b8c7da66bf93a9505b397661616cc4af2a34f6 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 6 Nov 2018 18:05:14 -0500 Subject: Move buffers.c out of lib/containers to resolve a circularity. --- src/app/main/main.c | 2 +- src/core/mainloop/connection.c | 2 +- src/core/mainloop/mainloop.c | 2 +- src/core/or/circuitlist.c | 2 +- src/core/or/connection_edge.c | 2 +- src/core/or/connection_or.c | 2 +- src/core/or/or.h | 2 +- src/core/or/relay.c | 2 +- src/core/or/scheduler.c | 2 +- src/core/or/scheduler_kist.c | 2 +- src/core/proto/proto_cell.c | 2 +- src/core/proto/proto_control0.c | 2 +- src/core/proto/proto_ext_or.c | 2 +- src/core/proto/proto_http.c | 2 +- src/core/proto/proto_socks.c | 2 +- src/feature/control/control.c | 2 +- src/feature/stats/geoip_stats.c | 2 +- src/include.am | 1 + src/lib/buf/.may_include | 10 + src/lib/buf/buffers.c | 925 ++++++++++++++++++++++++++++++++++++++ src/lib/buf/buffers.h | 122 +++++ src/lib/buf/include.am | 17 + src/lib/compress/.may_include | 1 + src/lib/compress/compress_buf.c | 2 +- src/lib/container/.may_include | 3 - src/lib/container/buffers.c | 925 -------------------------------------- src/lib/container/buffers.h | 122 ----- src/lib/container/include.am | 2 - src/lib/net/.may_include | 1 + src/lib/net/buffers_net.c | 2 +- src/lib/tls/.may_include | 1 + src/lib/tls/buffers_tls.c | 2 +- src/test/fuzz/fuzz_http.c | 2 +- src/test/fuzz/fuzz_http_connect.c | 2 +- src/test/fuzz/fuzz_socks.c | 2 +- src/test/test.c | 2 +- src/test/test_buffers.c | 2 +- src/test/test_channelpadding.c | 2 +- src/test/test_channeltls.c | 2 +- src/test/test_extorport.c | 2 +- src/test/test_helpers.c | 2 +- src/test/test_oom.c | 2 +- src/test/test_proto_http.c | 2 +- src/test/test_proto_misc.c | 2 +- src/test/test_routerlist.c | 2 +- src/test/test_socks.c | 2 +- src/test/test_util.c | 2 +- 47 files changed, 1113 insertions(+), 1087 deletions(-) create mode 100644 src/lib/buf/.may_include create mode 100644 src/lib/buf/buffers.c create mode 100644 src/lib/buf/buffers.h create mode 100644 src/lib/buf/include.am delete mode 100644 src/lib/container/buffers.c delete mode 100644 src/lib/container/buffers.h (limited to 'src') diff --git a/src/app/main/main.c b/src/app/main/main.c index b8dcb852d2..653a393fe4 100644 --- a/src/app/main/main.c +++ b/src/app/main/main.c @@ -67,7 +67,7 @@ #include "feature/stats/predict_ports.h" #include "feature/stats/rephist.h" #include "lib/compress/compress.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_s2k.h" #include "lib/geoip/geoip.h" diff --git a/src/core/mainloop/connection.c b/src/core/mainloop/connection.c index 1198a01ad9..8058077cd5 100644 --- a/src/core/mainloop/connection.c +++ b/src/core/mainloop/connection.c @@ -57,7 +57,7 @@ #define CONNECTION_PRIVATE #include "core/or/or.h" #include "feature/client/bridges.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/tls/buffers_tls.h" #include "lib/err/backtrace.h" diff --git a/src/core/mainloop/mainloop.c b/src/core/mainloop/mainloop.c index 7eff82fee4..8edee9d29d 100644 --- a/src/core/mainloop/mainloop.c +++ b/src/core/mainloop/mainloop.c @@ -95,7 +95,7 @@ #include "feature/stats/geoip_stats.h" #include "feature/stats/predict_ports.h" #include "feature/stats/rephist.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/err/backtrace.h" #include "lib/tls/buffers_tls.h" diff --git a/src/core/or/circuitlist.c b/src/core/or/circuitlist.c index 35efc6541f..0aa21000a1 100644 --- a/src/core/or/circuitlist.c +++ b/src/core/or/circuitlist.c @@ -94,7 +94,7 @@ #include "lib/compress/compress_lzma.h" #include "lib/compress/compress_zlib.h" #include "lib/compress/compress_zstd.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "ht.h" diff --git a/src/core/or/connection_edge.c b/src/core/or/connection_edge.c index 58aefcf8f2..a69c907319 100644 --- a/src/core/or/connection_edge.c +++ b/src/core/or/connection_edge.c @@ -97,7 +97,7 @@ #include "feature/rend/rendservice.h" #include "feature/stats/predict_ports.h" #include "feature/stats/rephist.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/crypt_ops/crypto_util.h" #include "core/or/cell_st.h" diff --git a/src/core/or/connection_or.c b/src/core/or/connection_or.c index 65f4e28c92..f231fda123 100644 --- a/src/core/or/connection_or.c +++ b/src/core/or/connection_or.c @@ -22,7 +22,7 @@ **/ #include "core/or/or.h" #include "feature/client/bridges.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" /* * Define this so we get channel internal functions, since we're implementing * part of a subclass (channel_tls_t). diff --git a/src/core/or/or.h b/src/core/or/or.h index acf092c8dc..0c4995cfd6 100644 --- a/src/core/or/or.h +++ b/src/core/or/or.h @@ -26,7 +26,7 @@ #include "lib/cc/compat_compiler.h" #include "lib/cc/torint.h" #include "lib/container/map.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/container/smartlist.h" #include "lib/crypt_ops/crypto_cipher.h" #include "lib/crypt_ops/crypto_rsa.h" diff --git a/src/core/or/relay.c b/src/core/or/relay.c index 510d96c648..2e92f2a55d 100644 --- a/src/core/or/relay.c +++ b/src/core/or/relay.c @@ -49,7 +49,7 @@ #include "core/or/or.h" #include "feature/client/addressmap.h" #include "lib/err/backtrace.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/or/channel.h" #include "feature/client/circpathbias.h" #include "core/or/circuitbuild.h" diff --git a/src/core/or/scheduler.c b/src/core/or/scheduler.c index 326e0d65d9..937e7e45db 100644 --- a/src/core/or/scheduler.c +++ b/src/core/or/scheduler.c @@ -9,7 +9,7 @@ #define SCHEDULER_KIST_PRIVATE #include "core/or/scheduler.h" #include "core/mainloop/mainloop.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #define TOR_CHANNEL_INTERNAL_ #include "core/or/channeltls.h" #include "lib/evloop/compat_libevent.h" diff --git a/src/core/or/scheduler_kist.c b/src/core/or/scheduler_kist.c index f112ea6357..3ed0f1a5e2 100644 --- a/src/core/or/scheduler_kist.c +++ b/src/core/or/scheduler_kist.c @@ -4,7 +4,7 @@ #define SCHEDULER_KIST_PRIVATE #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "app/config/config.h" #include "core/mainloop/connection.h" #include "feature/nodelist/networkstatus.h" diff --git a/src/core/proto/proto_cell.c b/src/core/proto/proto_cell.c index 49b07663d7..70278cd488 100644 --- a/src/core/proto/proto_cell.c +++ b/src/core/proto/proto_cell.c @@ -5,7 +5,7 @@ /* See LICENSE for licensing information */ #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/proto/proto_cell.h" #include "core/or/connection_or.h" diff --git a/src/core/proto/proto_control0.c b/src/core/proto/proto_control0.c index d26c69753a..a770a061a7 100644 --- a/src/core/proto/proto_control0.c +++ b/src/core/proto/proto_control0.c @@ -5,7 +5,7 @@ /* See LICENSE for licensing information */ #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/proto/proto_control0.h" /** Return 1 iff buf looks more like it has an (obsolete) v0 controller diff --git a/src/core/proto/proto_ext_or.c b/src/core/proto/proto_ext_or.c index 04bec4e6b9..fe36f6b396 100644 --- a/src/core/proto/proto_ext_or.c +++ b/src/core/proto/proto_ext_or.c @@ -5,7 +5,7 @@ /* See LICENSE for licensing information */ #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "feature/relay/ext_orport.h" #include "core/proto/proto_ext_or.h" diff --git a/src/core/proto/proto_http.c b/src/core/proto/proto_http.c index 37298d1284..4ce9ba02f5 100644 --- a/src/core/proto/proto_http.c +++ b/src/core/proto/proto_http.c @@ -6,7 +6,7 @@ #define PROTO_HTTP_PRIVATE #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/proto/proto_http.h" /** Return true if cmd looks like a HTTP (proxy) request. */ diff --git a/src/core/proto/proto_socks.c b/src/core/proto/proto_socks.c index e23da7730b..4071f34f0d 100644 --- a/src/core/proto/proto_socks.c +++ b/src/core/proto/proto_socks.c @@ -6,7 +6,7 @@ #include "core/or/or.h" #include "feature/client/addressmap.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/mainloop/connection.h" #include "feature/control/control.h" #include "app/config/config.h" diff --git a/src/feature/control/control.c b/src/feature/control/control.c index b31b448e96..11e722c3a8 100644 --- a/src/feature/control/control.c +++ b/src/feature/control/control.c @@ -87,7 +87,7 @@ #include "feature/rend/rendservice.h" #include "feature/stats/geoip_stats.h" #include "feature/stats/predict_ports.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_util.h" #include "lib/encoding/confline.h" diff --git a/src/feature/stats/geoip_stats.c b/src/feature/stats/geoip_stats.c index 1a4f8ddfb0..3106c6c82c 100644 --- a/src/feature/stats/geoip_stats.c +++ b/src/feature/stats/geoip_stats.c @@ -30,7 +30,7 @@ #include "core/or/or.h" #include "ht.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "app/config/config.h" #include "feature/control/control.h" #include "feature/client/dnsserv.h" diff --git a/src/include.am b/src/include.am index 8279499936..9070a69a03 100644 --- a/src/include.am +++ b/src/include.am @@ -1,5 +1,6 @@ include src/ext/include.am include src/lib/arch/include.am +include src/lib/buf/include.am include src/lib/err/include.am include src/lib/cc/include.am include src/lib/ctime/include.am diff --git a/src/lib/buf/.may_include b/src/lib/buf/.may_include new file mode 100644 index 0000000000..c4be73bce2 --- /dev/null +++ b/src/lib/buf/.may_include @@ -0,0 +1,10 @@ +orconfig.h + +lib/buf/*.h +lib/cc/*.h +lib/ctime/*.h +lib/malloc/*.h +lib/testsupport/*.h +lib/log/*.h +lib/string/*.h +lib/time/*.h diff --git a/src/lib/buf/buffers.c b/src/lib/buf/buffers.c new file mode 100644 index 0000000000..495c5ec453 --- /dev/null +++ b/src/lib/buf/buffers.c @@ -0,0 +1,925 @@ +/* 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 buffers.c + * \brief Implements a generic buffer interface. + * + * A buf_t is a (fairly) opaque byte-oriented FIFO that can read to or flush + * from memory, sockets, file descriptors, TLS connections, or another buf_t. + * Buffers are implemented as linked lists of memory chunks. + * + * All socket-backed and TLS-based connection_t objects have a pair of + * buffers: one for incoming data, and one for outcoming data. These are fed + * and drained from functions in connection.c, trigged by events that are + * monitored in main.c. + * + * This module only handles the buffer implementation itself. To use a buffer + * with the network, a compressor, or a TLS connection, see the other buffer_* + * modules. + **/ + +#define BUFFERS_PRIVATE +#include "orconfig.h" +#include +#include "lib/buf/buffers.h" +#include "lib/cc/torint.h" +#include "lib/log/log.h" +#include "lib/log/util_bug.h" +#include "lib/ctime/di_ops.h" +#include "lib/malloc/malloc.h" +#include "lib/string/printf.h" +#include "lib/time/compat_time.h" + +#ifdef HAVE_UNISTD_H +#include +#endif + +#include +#include + +//#define PARANOIA + +#ifdef PARANOIA +/** Helper: If PARANOIA is defined, assert that the buffer in local variable + * buf is well-formed. */ +#define check() STMT_BEGIN buf_assert_ok(buf); STMT_END +#else +#define check() STMT_NIL +#endif /* defined(PARANOIA) */ + +/* Implementation notes: + * + * After flirting with memmove, and dallying with ring-buffers, we're finally + * getting up to speed with the 1970s and implementing buffers as a linked + * list of small chunks. Each buffer has such a list; data is removed from + * the head of the list, and added at the tail. The list is singly linked, + * and the buffer keeps a pointer to the head and the tail. + * + * Every chunk, except the tail, contains at least one byte of data. Data in + * each chunk is contiguous. + * + * When you need to treat the first N characters on a buffer as a contiguous + * string, use the buf_pullup function to make them so. Don't do this more + * than necessary. + * + * The major free Unix kernels have handled buffers like this since, like, + * forever. + */ + +/* Chunk manipulation functions */ + +#define CHUNK_HEADER_LEN offsetof(chunk_t, mem[0]) + +/* We leave this many NUL bytes at the end of the buffer. */ +#ifdef DISABLE_MEMORY_SENTINELS +#define SENTINEL_LEN 0 +#else +#define SENTINEL_LEN 4 +#endif + +/* Header size plus NUL bytes at the end */ +#define CHUNK_OVERHEAD (CHUNK_HEADER_LEN + SENTINEL_LEN) + +/** Return the number of bytes needed to allocate a chunk to hold + * memlen bytes. */ +#define CHUNK_ALLOC_SIZE(memlen) (CHUNK_OVERHEAD + (memlen)) +/** Return the number of usable bytes in a chunk allocated with + * malloc(memlen). */ +#define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_OVERHEAD) + +#define DEBUG_SENTINEL + +#if defined(DEBUG_SENTINEL) && !defined(DISABLE_MEMORY_SENTINELS) +#define DBG_S(s) s +#else +#define DBG_S(s) (void)0 +#endif + +#ifdef DISABLE_MEMORY_SENTINELS +#define CHUNK_SET_SENTINEL(chunk, alloclen) STMT_NIL +#else +#define CHUNK_SET_SENTINEL(chunk, alloclen) do { \ + uint8_t *a = (uint8_t*) &(chunk)->mem[(chunk)->memlen]; \ + DBG_S(uint8_t *b = &((uint8_t*)(chunk))[(alloclen)-SENTINEL_LEN]); \ + DBG_S(tor_assert(a == b)); \ + memset(a,0,SENTINEL_LEN); \ + } while (0) +#endif /* defined(DISABLE_MEMORY_SENTINELS) */ + +/** Move all bytes stored in chunk to the front of chunk->mem, + * to free up space at the end. */ +static inline void +chunk_repack(chunk_t *chunk) +{ + if (chunk->datalen && chunk->data != &chunk->mem[0]) { + memmove(chunk->mem, chunk->data, chunk->datalen); + } + chunk->data = &chunk->mem[0]; +} + +/** Keep track of total size of allocated chunks for consistency asserts */ +static size_t total_bytes_allocated_in_chunks = 0; +static void +buf_chunk_free_unchecked(chunk_t *chunk) +{ + if (!chunk) + return; +#ifdef DEBUG_CHUNK_ALLOC + tor_assert(CHUNK_ALLOC_SIZE(chunk->memlen) == chunk->DBG_alloc); +#endif + tor_assert(total_bytes_allocated_in_chunks >= + CHUNK_ALLOC_SIZE(chunk->memlen)); + total_bytes_allocated_in_chunks -= CHUNK_ALLOC_SIZE(chunk->memlen); + tor_free(chunk); +} +static inline chunk_t * +chunk_new_with_alloc_size(size_t alloc) +{ + chunk_t *ch; + ch = tor_malloc(alloc); + ch->next = NULL; + ch->datalen = 0; +#ifdef DEBUG_CHUNK_ALLOC + ch->DBG_alloc = alloc; +#endif + ch->memlen = CHUNK_SIZE_WITH_ALLOC(alloc); + total_bytes_allocated_in_chunks += alloc; + ch->data = &ch->mem[0]; + CHUNK_SET_SENTINEL(ch, alloc); + return ch; +} + +/** Expand chunk until it can hold sz bytes, and return a + * new pointer to chunk. Old pointers are no longer valid. */ +static inline chunk_t * +chunk_grow(chunk_t *chunk, size_t sz) +{ + off_t offset; + const size_t memlen_orig = chunk->memlen; + const size_t orig_alloc = CHUNK_ALLOC_SIZE(memlen_orig); + const size_t new_alloc = CHUNK_ALLOC_SIZE(sz); + tor_assert(sz > chunk->memlen); + offset = chunk->data - chunk->mem; + chunk = tor_realloc(chunk, new_alloc); + chunk->memlen = sz; + chunk->data = chunk->mem + offset; +#ifdef DEBUG_CHUNK_ALLOC + tor_assert(chunk->DBG_alloc == orig_alloc); + chunk->DBG_alloc = new_alloc; +#endif + total_bytes_allocated_in_chunks += new_alloc - orig_alloc; + CHUNK_SET_SENTINEL(chunk, new_alloc); + return chunk; +} + +/** Every chunk should take up at least this many bytes. */ +#define MIN_CHUNK_ALLOC 256 +/** No chunk should take up more than this many bytes. */ +#define MAX_CHUNK_ALLOC 65536 + +/** Return the allocation size we'd like to use to hold target + * bytes. */ +size_t +buf_preferred_chunk_size(size_t target) +{ + tor_assert(target <= SIZE_T_CEILING - CHUNK_OVERHEAD); + if (CHUNK_ALLOC_SIZE(target) >= MAX_CHUNK_ALLOC) + return CHUNK_ALLOC_SIZE(target); + size_t sz = MIN_CHUNK_ALLOC; + while (CHUNK_SIZE_WITH_ALLOC(sz) < target) { + sz <<= 1; + } + return sz; +} + +/** Collapse data from the first N chunks from buf into buf->head, + * growing it as necessary, until buf->head has the first bytes bytes + * of data from the buffer, or until buf->head has all the data in buf. + * + * Set *head_out to point to the first byte of available data, and + * *len_out to the number of bytes of data available at + * *head_out. Note that *len_out may be more or less than + * bytes, depending on the number of bytes available. + */ +void +buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out) +{ + chunk_t *dest, *src; + size_t capacity; + if (!buf->head) { + *head_out = NULL; + *len_out = 0; + return; + } + + check(); + if (buf->datalen < bytes) + bytes = buf->datalen; + + capacity = bytes; + if (buf->head->datalen >= bytes) { + *head_out = buf->head->data; + *len_out = buf->head->datalen; + return; + } + + if (buf->head->memlen >= capacity) { + /* We don't need to grow the first chunk, but we might need to repack it.*/ + size_t needed = capacity - buf->head->datalen; + if (CHUNK_REMAINING_CAPACITY(buf->head) < needed) + chunk_repack(buf->head); + tor_assert(CHUNK_REMAINING_CAPACITY(buf->head) >= needed); + } else { + chunk_t *newhead; + size_t newsize; + /* We need to grow the chunk. */ + chunk_repack(buf->head); + newsize = CHUNK_SIZE_WITH_ALLOC(buf_preferred_chunk_size(capacity)); + newhead = chunk_grow(buf->head, newsize); + tor_assert(newhead->memlen >= capacity); + if (newhead != buf->head) { + if (buf->tail == buf->head) + buf->tail = newhead; + buf->head = newhead; + } + } + + dest = buf->head; + while (dest->datalen < bytes) { + size_t n = bytes - dest->datalen; + src = dest->next; + tor_assert(src); + if (n >= src->datalen) { + memcpy(CHUNK_WRITE_PTR(dest), src->data, src->datalen); + dest->datalen += src->datalen; + dest->next = src->next; + if (buf->tail == src) + buf->tail = dest; + buf_chunk_free_unchecked(src); + } else { + memcpy(CHUNK_WRITE_PTR(dest), src->data, n); + dest->datalen += n; + src->data += n; + src->datalen -= n; + tor_assert(dest->datalen == bytes); + } + } + + check(); + *head_out = buf->head->data; + *len_out = buf->head->datalen; +} + +#ifdef TOR_UNIT_TESTS +/* Write sz bytes from cp into a newly allocated buffer buf. + * Returns NULL when passed a NULL cp or zero sz. + * Asserts on failure: only for use in unit tests. + * buf must be freed using buf_free(). */ +buf_t * +buf_new_with_data(const char *cp, size_t sz) +{ + /* Validate arguments */ + if (!cp || sz <= 0) { + return NULL; + } + + tor_assert(sz < SSIZE_T_CEILING); + + /* Allocate a buffer */ + buf_t *buf = buf_new_with_capacity(sz); + tor_assert(buf); + buf_assert_ok(buf); + tor_assert(!buf->head); + + /* Allocate a chunk that is sz bytes long */ + buf->head = chunk_new_with_alloc_size(CHUNK_ALLOC_SIZE(sz)); + buf->tail = buf->head; + tor_assert(buf->head); + buf_assert_ok(buf); + tor_assert(buf_allocation(buf) >= sz); + + /* Copy the data and size the buffers */ + tor_assert(sz <= buf_slack(buf)); + tor_assert(sz <= CHUNK_REMAINING_CAPACITY(buf->head)); + memcpy(&buf->head->mem[0], cp, sz); + buf->datalen = sz; + buf->head->datalen = sz; + buf->head->data = &buf->head->mem[0]; + buf_assert_ok(buf); + + /* Make sure everything is large enough */ + tor_assert(buf_allocation(buf) >= sz); + tor_assert(buf_allocation(buf) >= buf_datalen(buf) + buf_slack(buf)); + /* Does the buffer implementation allocate more than the requested size? + * (for example, by rounding up). If so, these checks will fail. */ + tor_assert(buf_datalen(buf) == sz); + tor_assert(buf_slack(buf) == 0); + + return buf; +} +#endif /* defined(TOR_UNIT_TESTS) */ + +/** Remove the first n bytes from buf. */ +void +buf_drain(buf_t *buf, size_t n) +{ + tor_assert(buf->datalen >= n); + while (n) { + tor_assert(buf->head); + if (buf->head->datalen > n) { + buf->head->datalen -= n; + buf->head->data += n; + buf->datalen -= n; + return; + } else { + chunk_t *victim = buf->head; + n -= victim->datalen; + buf->datalen -= victim->datalen; + buf->head = victim->next; + if (buf->tail == victim) + buf->tail = NULL; + buf_chunk_free_unchecked(victim); + } + } + check(); +} + +/** Create and return a new buf with default chunk capacity size. + */ +buf_t * +buf_new_with_capacity(size_t size) +{ + buf_t *b = buf_new(); + b->default_chunk_size = buf_preferred_chunk_size(size); + return b; +} + +/** Allocate and return a new buffer with default capacity. */ +buf_t * +buf_new(void) +{ + buf_t *buf = tor_malloc_zero(sizeof(buf_t)); + buf->magic = BUFFER_MAGIC; + buf->default_chunk_size = 4096; + return buf; +} + +size_t +buf_get_default_chunk_size(const buf_t *buf) +{ + return buf->default_chunk_size; +} + +/** Remove all data from buf. */ +void +buf_clear(buf_t *buf) +{ + chunk_t *chunk, *next; + buf->datalen = 0; + for (chunk = buf->head; chunk; chunk = next) { + next = chunk->next; + buf_chunk_free_unchecked(chunk); + } + buf->head = buf->tail = NULL; +} + +/** Return the number of bytes stored in buf */ +MOCK_IMPL(size_t, +buf_datalen, (const buf_t *buf)) +{ + return buf->datalen; +} + +/** Return the total length of all chunks used in buf. */ +size_t +buf_allocation(const buf_t *buf) +{ + size_t total = 0; + const chunk_t *chunk; + for (chunk = buf->head; chunk; chunk = chunk->next) { + total += CHUNK_ALLOC_SIZE(chunk->memlen); + } + return total; +} + +/** Return the number of bytes that can be added to buf without + * performing any additional allocation. */ +size_t +buf_slack(const buf_t *buf) +{ + if (!buf->tail) + return 0; + else + return CHUNK_REMAINING_CAPACITY(buf->tail); +} + +/** Release storage held by buf. */ +void +buf_free_(buf_t *buf) +{ + if (!buf) + return; + + buf_clear(buf); + buf->magic = 0xdeadbeef; + tor_free(buf); +} + +/** Return a new copy of in_chunk */ +static chunk_t * +chunk_copy(const chunk_t *in_chunk) +{ + chunk_t *newch = tor_memdup(in_chunk, CHUNK_ALLOC_SIZE(in_chunk->memlen)); + total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(in_chunk->memlen); +#ifdef DEBUG_CHUNK_ALLOC + newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen); +#endif + newch->next = NULL; + if (in_chunk->data) { + off_t offset = in_chunk->data - in_chunk->mem; + newch->data = newch->mem + offset; + } + return newch; +} + +/** Return a new copy of buf */ +buf_t * +buf_copy(const buf_t *buf) +{ + chunk_t *ch; + buf_t *out = buf_new(); + out->default_chunk_size = buf->default_chunk_size; + for (ch = buf->head; ch; ch = ch->next) { + chunk_t *newch = chunk_copy(ch); + if (out->tail) { + out->tail->next = newch; + out->tail = newch; + } else { + out->head = out->tail = newch; + } + } + out->datalen = buf->datalen; + return out; +} + +/** Append a new chunk with enough capacity to hold capacity bytes to + * the tail of buf. If capped, don't allocate a chunk bigger + * than MAX_CHUNK_ALLOC. */ +chunk_t * +buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped) +{ + chunk_t *chunk; + + if (CHUNK_ALLOC_SIZE(capacity) < buf->default_chunk_size) { + chunk = chunk_new_with_alloc_size(buf->default_chunk_size); + } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) { + chunk = chunk_new_with_alloc_size(MAX_CHUNK_ALLOC); + } else { + chunk = chunk_new_with_alloc_size(buf_preferred_chunk_size(capacity)); + } + + chunk->inserted_time = monotime_coarse_get_stamp(); + + if (buf->tail) { + tor_assert(buf->head); + buf->tail->next = chunk; + buf->tail = chunk; + } else { + tor_assert(!buf->head); + buf->head = buf->tail = chunk; + } + check(); + return chunk; +} + +/** Return the age of the oldest chunk in the buffer buf, in + * timestamp units. Requires the current monotonic timestamp as its + * input now. + */ +uint32_t +buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now) +{ + if (buf->head) { + return now - buf->head->inserted_time; + } else { + return 0; + } +} + +size_t +buf_get_total_allocation(void) +{ + return total_bytes_allocated_in_chunks; +} + +/** Append string_len bytes from string to the end of + * buf. + * + * Return the new length of the buffer on success, -1 on failure. + */ +int +buf_add(buf_t *buf, const char *string, size_t string_len) +{ + if (!string_len) + return (int)buf->datalen; + check(); + + if (BUG(buf->datalen >= INT_MAX)) + return -1; + if (BUG(buf->datalen >= INT_MAX - string_len)) + return -1; + + while (string_len) { + size_t copy; + if (!buf->tail || !CHUNK_REMAINING_CAPACITY(buf->tail)) + buf_add_chunk_with_capacity(buf, string_len, 1); + + copy = CHUNK_REMAINING_CAPACITY(buf->tail); + if (copy > string_len) + copy = string_len; + memcpy(CHUNK_WRITE_PTR(buf->tail), string, copy); + string_len -= copy; + string += copy; + buf->datalen += copy; + buf->tail->datalen += copy; + } + + check(); + tor_assert(buf->datalen < INT_MAX); + return (int)buf->datalen; +} + +/** Add a nul-terminated string to buf, not including the + * terminating NUL. */ +void +buf_add_string(buf_t *buf, const char *string) +{ + buf_add(buf, string, strlen(string)); +} + +/** As tor_snprintf, but write the results into a buf_t */ +void +buf_add_printf(buf_t *buf, const char *format, ...) +{ + va_list ap; + va_start(ap,format); + buf_add_vprintf(buf, format, ap); + va_end(ap); +} + +/** As tor_vsnprintf, but write the results into a buf_t. */ +void +buf_add_vprintf(buf_t *buf, const char *format, va_list args) +{ + /* XXXX Faster implementations are easy enough, but let's optimize later */ + char *tmp; + tor_vasprintf(&tmp, format, args); + buf_add(buf, tmp, strlen(tmp)); + tor_free(tmp); +} + +/** Return a heap-allocated string containing the contents of buf, plus + * a NUL byte. If sz_out is provided, set *sz_out to the length + * of the returned string, not including the terminating NUL. */ +char * +buf_extract(buf_t *buf, size_t *sz_out) +{ + tor_assert(buf); + + size_t sz = buf_datalen(buf); + char *result; + result = tor_malloc(sz+1); + buf_peek(buf, result, sz); + result[sz] = 0; + if (sz_out) + *sz_out = sz; + return result; +} + +/** Helper: copy the first string_len bytes from buf + * onto string. + */ +void +buf_peek(const buf_t *buf, char *string, size_t string_len) +{ + chunk_t *chunk; + + tor_assert(string); + /* make sure we don't ask for too much */ + tor_assert(string_len <= buf->datalen); + /* buf_assert_ok(buf); */ + + chunk = buf->head; + while (string_len) { + size_t copy = string_len; + tor_assert(chunk); + if (chunk->datalen < copy) + copy = chunk->datalen; + memcpy(string, chunk->data, copy); + string_len -= copy; + string += copy; + chunk = chunk->next; + } +} + +/** Remove string_len bytes from the front of buf, and store + * them into string. Return the new buffer size. string_len + * must be \<= the number of bytes on the buffer. + */ +int +buf_get_bytes(buf_t *buf, char *string, size_t string_len) +{ + /* There must be string_len bytes in buf; write them onto string, + * then memmove buf back (that is, remove them from buf). + * + * Return the number of bytes still on the buffer. */ + + check(); + buf_peek(buf, string, string_len); + buf_drain(buf, string_len); + check(); + tor_assert(buf->datalen < INT_MAX); + return (int)buf->datalen; +} + +/** Move up to *buf_flushlen bytes from buf_in to + * buf_out, and modify *buf_flushlen appropriately. + * Return the number of bytes actually copied. + */ +int +buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen) +{ + /* We can do way better here, but this doesn't turn up in any profiles. */ + char b[4096]; + size_t cp, len; + + if (BUG(buf_out->datalen >= INT_MAX)) + return -1; + if (BUG(buf_out->datalen >= INT_MAX - *buf_flushlen)) + return -1; + + len = *buf_flushlen; + if (len > buf_in->datalen) + len = buf_in->datalen; + + cp = len; /* Remember the number of bytes we intend to copy. */ + tor_assert(cp < INT_MAX); + while (len) { + /* This isn't the most efficient implementation one could imagine, since + * it does two copies instead of 1, but I kinda doubt that this will be + * critical path. */ + size_t n = len > sizeof(b) ? sizeof(b) : len; + buf_get_bytes(buf_in, b, n); + buf_add(buf_out, b, n); + len -= n; + } + *buf_flushlen -= cp; + return (int)cp; +} + +/** Moves all data from buf_in to buf_out, without copying. + */ +void +buf_move_all(buf_t *buf_out, buf_t *buf_in) +{ + tor_assert(buf_out); + if (!buf_in) + return; + + if (buf_out->head == NULL) { + buf_out->head = buf_in->head; + buf_out->tail = buf_in->tail; + } else { + buf_out->tail->next = buf_in->head; + buf_out->tail = buf_in->tail; + } + + buf_out->datalen += buf_in->datalen; + buf_in->head = buf_in->tail = NULL; + buf_in->datalen = 0; +} + +/** Internal structure: represents a position in a buffer. */ +typedef struct buf_pos_t { + const chunk_t *chunk; /**< Which chunk are we pointing to? */ + int pos;/**< Which character inside the chunk's data are we pointing to? */ + size_t chunk_pos; /**< Total length of all previous chunks. */ +} buf_pos_t; + +/** Initialize out to point to the first character of buf.*/ +static void +buf_pos_init(const buf_t *buf, buf_pos_t *out) +{ + out->chunk = buf->head; + out->pos = 0; + out->chunk_pos = 0; +} + +/** Advance out to the first appearance of ch at the current + * position of out, or later. Return -1 if no instances are found; + * otherwise returns the absolute position of the character. */ +static off_t +buf_find_pos_of_char(char ch, buf_pos_t *out) +{ + const chunk_t *chunk; + int pos; + tor_assert(out); + if (out->chunk) { + if (out->chunk->datalen) { + tor_assert(out->pos < (off_t)out->chunk->datalen); + } else { + tor_assert(out->pos == 0); + } + } + pos = out->pos; + for (chunk = out->chunk; chunk; chunk = chunk->next) { + char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos); + if (cp) { + out->chunk = chunk; + tor_assert(cp - chunk->data < INT_MAX); + out->pos = (int)(cp - chunk->data); + return out->chunk_pos + out->pos; + } else { + out->chunk_pos += chunk->datalen; + pos = 0; + } + } + return -1; +} + +/** Advance pos by a single character, if there are any more characters + * in the buffer. Returns 0 on success, -1 on failure. */ +static inline int +buf_pos_inc(buf_pos_t *pos) +{ + ++pos->pos; + if (pos->pos == (off_t)pos->chunk->datalen) { + if (!pos->chunk->next) + return -1; + pos->chunk_pos += pos->chunk->datalen; + pos->chunk = pos->chunk->next; + pos->pos = 0; + } + return 0; +} + +/** Return true iff the n-character string in s appears + * (verbatim) at pos. */ +static int +buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n) +{ + buf_pos_t p; + if (!n) + return 1; + + memcpy(&p, pos, sizeof(p)); + + while (1) { + char ch = p.chunk->data[p.pos]; + if (ch != *s) + return 0; + ++s; + /* If we're out of characters that don't match, we match. Check this + * _before_ we test incrementing pos, in case we're at the end of the + * string. */ + if (--n == 0) + return 1; + if (buf_pos_inc(&p)<0) + return 0; + } +} + +/** Return the first position in buf at which the n-character + * string s occurs, or -1 if it does not occur. */ +int +buf_find_string_offset(const buf_t *buf, const char *s, size_t n) +{ + buf_pos_t pos; + buf_pos_init(buf, &pos); + while (buf_find_pos_of_char(*s, &pos) >= 0) { + if (buf_matches_at_pos(&pos, s, n)) { + tor_assert(pos.chunk_pos + pos.pos < INT_MAX); + return (int)(pos.chunk_pos + pos.pos); + } else { + if (buf_pos_inc(&pos)<0) + return -1; + } + } + return -1; +} + +/** Return 1 iff buf starts with cmd. cmd must be a null + * terminated string, of no more than PEEK_BUF_STARTSWITH_MAX bytes. */ +int +buf_peek_startswith(const buf_t *buf, const char *cmd) +{ + char tmp[PEEK_BUF_STARTSWITH_MAX]; + size_t clen = strlen(cmd); + if (clen == 0) + return 1; + if (BUG(clen > sizeof(tmp))) + return 0; + if (buf->datalen < clen) + return 0; + buf_peek(buf, tmp, clen); + return fast_memeq(tmp, cmd, clen); +} + +/** Return the index within buf at which ch first appears, + * or -1 if ch does not appear on buf. */ +static off_t +buf_find_offset_of_char(buf_t *buf, char ch) +{ + chunk_t *chunk; + off_t offset = 0; + for (chunk = buf->head; chunk; chunk = chunk->next) { + char *cp = memchr(chunk->data, ch, chunk->datalen); + if (cp) + return offset + (cp - chunk->data); + else + offset += chunk->datalen; + } + return -1; +} + +/** Try to read a single LF-terminated line from buf, and write it + * (including the LF), NUL-terminated, into the *data_len byte buffer + * at data_out. Set *data_len to the number of bytes in the + * line, not counting the terminating NUL. Return 1 if we read a whole line, + * return 0 if we don't have a whole line yet, and return -1 if the line + * length exceeds *data_len. + */ +int +buf_get_line(buf_t *buf, char *data_out, size_t *data_len) +{ + size_t sz; + off_t offset; + + if (!buf->head) + return 0; + + offset = buf_find_offset_of_char(buf, '\n'); + if (offset < 0) + return 0; + sz = (size_t) offset; + if (sz+2 > *data_len) { + *data_len = sz + 2; + return -1; + } + buf_get_bytes(buf, data_out, sz+1); + data_out[sz+1] = '\0'; + *data_len = sz+1; + return 1; +} + +/** Set *output to contain a copy of the data in *input */ +int +buf_set_to_copy(buf_t **output, + const buf_t *input) +{ + if (*output) + buf_free(*output); + *output = buf_copy(input); + return 0; +} + +/** Log an error and exit if buf is corrupted. + */ +void +buf_assert_ok(buf_t *buf) +{ + tor_assert(buf); + tor_assert(buf->magic == BUFFER_MAGIC); + + if (! buf->head) { + tor_assert(!buf->tail); + tor_assert(buf->datalen == 0); + } else { + chunk_t *ch; + size_t total = 0; + tor_assert(buf->tail); + for (ch = buf->head; ch; ch = ch->next) { + total += ch->datalen; + tor_assert(ch->datalen <= ch->memlen); + tor_assert(ch->data >= &ch->mem[0]); + tor_assert(ch->data <= &ch->mem[0]+ch->memlen); + if (ch->data == &ch->mem[0]+ch->memlen) { + /* LCOV_EXCL_START */ + static int warned = 0; + if (! warned) { + log_warn(LD_BUG, "Invariant violation in buf.c related to #15083"); + warned = 1; + } + /* LCOV_EXCL_STOP */ + } + tor_assert(ch->data+ch->datalen <= &ch->mem[0] + ch->memlen); + if (!ch->next) + tor_assert(ch == buf->tail); + } + tor_assert(buf->datalen == total); + } +} diff --git a/src/lib/buf/buffers.h b/src/lib/buf/buffers.h new file mode 100644 index 0000000000..c48f83cfc7 --- /dev/null +++ b/src/lib/buf/buffers.h @@ -0,0 +1,122 @@ +/* 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 buffers.h + * + * \brief Header file for buffers.c. + **/ + +#ifndef TOR_BUFFERS_H +#define TOR_BUFFERS_H + +#include "lib/cc/compat_compiler.h" +#include "lib/cc/torint.h" +#include "lib/testsupport/testsupport.h" + +#include + +typedef struct buf_t buf_t; + +buf_t *buf_new(void); +buf_t *buf_new_with_capacity(size_t size); +size_t buf_get_default_chunk_size(const buf_t *buf); +void buf_free_(buf_t *buf); +#define buf_free(b) FREE_AND_NULL(buf_t, buf_free_, (b)) +void buf_clear(buf_t *buf); +buf_t *buf_copy(const buf_t *buf); + +MOCK_DECL(size_t, buf_datalen, (const buf_t *buf)); +size_t buf_allocation(const buf_t *buf); +size_t buf_slack(const buf_t *buf); + +uint32_t buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now); +size_t buf_get_total_allocation(void); + +int buf_add(buf_t *buf, const char *string, size_t string_len); +void buf_add_string(buf_t *buf, const char *string); +void buf_add_printf(buf_t *buf, const char *format, ...) + CHECK_PRINTF(2, 3); +void buf_add_vprintf(buf_t *buf, const char *format, va_list args) + CHECK_PRINTF(2, 0); +int buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen); +void buf_move_all(buf_t *buf_out, buf_t *buf_in); +void buf_peek(const buf_t *buf, char *string, size_t string_len); +void buf_drain(buf_t *buf, size_t n); +int buf_get_bytes(buf_t *buf, char *string, size_t string_len); +int buf_get_line(buf_t *buf, char *data_out, size_t *data_len); + +#define PEEK_BUF_STARTSWITH_MAX 16 +int buf_peek_startswith(const buf_t *buf, const char *cmd); + +int buf_set_to_copy(buf_t **output, + const buf_t *input); + +void buf_assert_ok(buf_t *buf); + +int buf_find_string_offset(const buf_t *buf, const char *s, size_t n); +void buf_pullup(buf_t *buf, size_t bytes, + const char **head_out, size_t *len_out); +char *buf_extract(buf_t *buf, size_t *sz_out); + +#ifdef BUFFERS_PRIVATE +#ifdef TOR_UNIT_TESTS +buf_t *buf_new_with_data(const char *cp, size_t sz); +#endif +size_t buf_preferred_chunk_size(size_t target); + +#define DEBUG_CHUNK_ALLOC +/** A single chunk on a buffer. */ +typedef struct chunk_t { + struct chunk_t *next; /**< The next chunk on the buffer. */ + size_t datalen; /**< The number of bytes stored in this chunk */ + size_t memlen; /**< The number of usable bytes of storage in mem. */ +#ifdef DEBUG_CHUNK_ALLOC + size_t DBG_alloc; +#endif + char *data; /**< A pointer to the first byte of data stored in mem. */ + uint32_t inserted_time; /**< Timestamp when this chunk was inserted. */ + char mem[FLEXIBLE_ARRAY_MEMBER]; /**< The actual memory used for storage in + * this chunk. */ +} chunk_t; + +/** Magic value for buf_t.magic, to catch pointer errors. */ +#define BUFFER_MAGIC 0xB0FFF312u +/** A resizeable buffer, optimized for reading and writing. */ +struct buf_t { + uint32_t magic; /**< Magic cookie for debugging: Must be set to + * BUFFER_MAGIC. */ + size_t datalen; /**< How many bytes is this buffer holding right now? */ + size_t default_chunk_size; /**< Don't allocate any chunks smaller than + * this for this buffer. */ + chunk_t *head; /**< First chunk in the list, or NULL for none. */ + chunk_t *tail; /**< Last chunk in the list, or NULL for none. */ +}; + +chunk_t *buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped); +/** If a read onto the end of a chunk would be smaller than this number, then + * just start a new chunk. */ +#define MIN_READ_LEN 8 + +/** Return the number of bytes that can be written onto chunk without + * running out of space. */ +static inline size_t +CHUNK_REMAINING_CAPACITY(const chunk_t *chunk) +{ + return (chunk->mem + chunk->memlen) - (chunk->data + chunk->datalen); +} + +/** Return the next character in chunk onto which data can be appended. + * If the chunk is full, this might be off the end of chunk->mem. */ +static inline char * +CHUNK_WRITE_PTR(chunk_t *chunk) +{ + return chunk->data + chunk->datalen; +} + +#endif /* defined(BUFFERS_PRIVATE) */ + +#endif /* !defined(TOR_BUFFERS_H) */ diff --git a/src/lib/buf/include.am b/src/lib/buf/include.am new file mode 100644 index 0000000000..3338c3dbdb --- /dev/null +++ b/src/lib/buf/include.am @@ -0,0 +1,17 @@ + +noinst_LIBRARIES += src/lib/libtor-buf.a + +if UNITTESTS_ENABLED +noinst_LIBRARIES += src/lib/libtor-buf-testing.a +endif + +src_lib_libtor_buf_a_SOURCES = \ + src/lib/buf/buffers.c + +src_lib_libtor_buf_testing_a_SOURCES = \ + $(src_lib_libtor_buf_a_SOURCES) +src_lib_libtor_buf_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) +src_lib_libtor_buf_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) + +noinst_HEADERS += \ + src/lib/buf/buffers.h diff --git a/src/lib/compress/.may_include b/src/lib/compress/.may_include index 4870259ec9..6cd80086e6 100644 --- a/src/lib/compress/.may_include +++ b/src/lib/compress/.may_include @@ -1,5 +1,6 @@ orconfig.h lib/arch/*.h +lib/buf/*.h lib/cc/*.h lib/compress/*.h lib/container/*.h diff --git a/src/lib/compress/compress_buf.c b/src/lib/compress/compress_buf.c index 63ee9e0102..ecf76ee078 100644 --- a/src/lib/compress/compress_buf.c +++ b/src/lib/compress/compress_buf.c @@ -11,7 +11,7 @@ #define BUFFERS_PRIVATE #include "lib/cc/compat_compiler.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/compress/compress.h" #include "lib/log/util_bug.h" diff --git a/src/lib/container/.may_include b/src/lib/container/.may_include index 90de5eda40..76e5843728 100644 --- a/src/lib/container/.may_include +++ b/src/lib/container/.may_include @@ -11,8 +11,5 @@ lib/testsupport/testsupport.h lib/intmath/*.h lib/log/*.h -# XXXX I am unsure about this one. It's only here for buffers.c -lib/time/*.h - ht.h siphash.h diff --git a/src/lib/container/buffers.c b/src/lib/container/buffers.c deleted file mode 100644 index 87d782d7ef..0000000000 --- a/src/lib/container/buffers.c +++ /dev/null @@ -1,925 +0,0 @@ -/* 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 buffers.c - * \brief Implements a generic buffer interface. - * - * A buf_t is a (fairly) opaque byte-oriented FIFO that can read to or flush - * from memory, sockets, file descriptors, TLS connections, or another buf_t. - * Buffers are implemented as linked lists of memory chunks. - * - * All socket-backed and TLS-based connection_t objects have a pair of - * buffers: one for incoming data, and one for outcoming data. These are fed - * and drained from functions in connection.c, trigged by events that are - * monitored in main.c. - * - * This module only handles the buffer implementation itself. To use a buffer - * with the network, a compressor, or a TLS connection, see the other buffer_* - * modules. - **/ - -#define BUFFERS_PRIVATE -#include "orconfig.h" -#include -#include "lib/container/buffers.h" -#include "lib/cc/torint.h" -#include "lib/log/log.h" -#include "lib/log/util_bug.h" -#include "lib/ctime/di_ops.h" -#include "lib/malloc/malloc.h" -#include "lib/string/printf.h" -#include "lib/time/compat_time.h" - -#ifdef HAVE_UNISTD_H -#include -#endif - -#include -#include - -//#define PARANOIA - -#ifdef PARANOIA -/** Helper: If PARANOIA is defined, assert that the buffer in local variable - * buf is well-formed. */ -#define check() STMT_BEGIN buf_assert_ok(buf); STMT_END -#else -#define check() STMT_NIL -#endif /* defined(PARANOIA) */ - -/* Implementation notes: - * - * After flirting with memmove, and dallying with ring-buffers, we're finally - * getting up to speed with the 1970s and implementing buffers as a linked - * list of small chunks. Each buffer has such a list; data is removed from - * the head of the list, and added at the tail. The list is singly linked, - * and the buffer keeps a pointer to the head and the tail. - * - * Every chunk, except the tail, contains at least one byte of data. Data in - * each chunk is contiguous. - * - * When you need to treat the first N characters on a buffer as a contiguous - * string, use the buf_pullup function to make them so. Don't do this more - * than necessary. - * - * The major free Unix kernels have handled buffers like this since, like, - * forever. - */ - -/* Chunk manipulation functions */ - -#define CHUNK_HEADER_LEN offsetof(chunk_t, mem[0]) - -/* We leave this many NUL bytes at the end of the buffer. */ -#ifdef DISABLE_MEMORY_SENTINELS -#define SENTINEL_LEN 0 -#else -#define SENTINEL_LEN 4 -#endif - -/* Header size plus NUL bytes at the end */ -#define CHUNK_OVERHEAD (CHUNK_HEADER_LEN + SENTINEL_LEN) - -/** Return the number of bytes needed to allocate a chunk to hold - * memlen bytes. */ -#define CHUNK_ALLOC_SIZE(memlen) (CHUNK_OVERHEAD + (memlen)) -/** Return the number of usable bytes in a chunk allocated with - * malloc(memlen). */ -#define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_OVERHEAD) - -#define DEBUG_SENTINEL - -#if defined(DEBUG_SENTINEL) && !defined(DISABLE_MEMORY_SENTINELS) -#define DBG_S(s) s -#else -#define DBG_S(s) (void)0 -#endif - -#ifdef DISABLE_MEMORY_SENTINELS -#define CHUNK_SET_SENTINEL(chunk, alloclen) STMT_NIL -#else -#define CHUNK_SET_SENTINEL(chunk, alloclen) do { \ - uint8_t *a = (uint8_t*) &(chunk)->mem[(chunk)->memlen]; \ - DBG_S(uint8_t *b = &((uint8_t*)(chunk))[(alloclen)-SENTINEL_LEN]); \ - DBG_S(tor_assert(a == b)); \ - memset(a,0,SENTINEL_LEN); \ - } while (0) -#endif /* defined(DISABLE_MEMORY_SENTINELS) */ - -/** Move all bytes stored in chunk to the front of chunk->mem, - * to free up space at the end. */ -static inline void -chunk_repack(chunk_t *chunk) -{ - if (chunk->datalen && chunk->data != &chunk->mem[0]) { - memmove(chunk->mem, chunk->data, chunk->datalen); - } - chunk->data = &chunk->mem[0]; -} - -/** Keep track of total size of allocated chunks for consistency asserts */ -static size_t total_bytes_allocated_in_chunks = 0; -static void -buf_chunk_free_unchecked(chunk_t *chunk) -{ - if (!chunk) - return; -#ifdef DEBUG_CHUNK_ALLOC - tor_assert(CHUNK_ALLOC_SIZE(chunk->memlen) == chunk->DBG_alloc); -#endif - tor_assert(total_bytes_allocated_in_chunks >= - CHUNK_ALLOC_SIZE(chunk->memlen)); - total_bytes_allocated_in_chunks -= CHUNK_ALLOC_SIZE(chunk->memlen); - tor_free(chunk); -} -static inline chunk_t * -chunk_new_with_alloc_size(size_t alloc) -{ - chunk_t *ch; - ch = tor_malloc(alloc); - ch->next = NULL; - ch->datalen = 0; -#ifdef DEBUG_CHUNK_ALLOC - ch->DBG_alloc = alloc; -#endif - ch->memlen = CHUNK_SIZE_WITH_ALLOC(alloc); - total_bytes_allocated_in_chunks += alloc; - ch->data = &ch->mem[0]; - CHUNK_SET_SENTINEL(ch, alloc); - return ch; -} - -/** Expand chunk until it can hold sz bytes, and return a - * new pointer to chunk. Old pointers are no longer valid. */ -static inline chunk_t * -chunk_grow(chunk_t *chunk, size_t sz) -{ - off_t offset; - const size_t memlen_orig = chunk->memlen; - const size_t orig_alloc = CHUNK_ALLOC_SIZE(memlen_orig); - const size_t new_alloc = CHUNK_ALLOC_SIZE(sz); - tor_assert(sz > chunk->memlen); - offset = chunk->data - chunk->mem; - chunk = tor_realloc(chunk, new_alloc); - chunk->memlen = sz; - chunk->data = chunk->mem + offset; -#ifdef DEBUG_CHUNK_ALLOC - tor_assert(chunk->DBG_alloc == orig_alloc); - chunk->DBG_alloc = new_alloc; -#endif - total_bytes_allocated_in_chunks += new_alloc - orig_alloc; - CHUNK_SET_SENTINEL(chunk, new_alloc); - return chunk; -} - -/** Every chunk should take up at least this many bytes. */ -#define MIN_CHUNK_ALLOC 256 -/** No chunk should take up more than this many bytes. */ -#define MAX_CHUNK_ALLOC 65536 - -/** Return the allocation size we'd like to use to hold target - * bytes. */ -size_t -buf_preferred_chunk_size(size_t target) -{ - tor_assert(target <= SIZE_T_CEILING - CHUNK_OVERHEAD); - if (CHUNK_ALLOC_SIZE(target) >= MAX_CHUNK_ALLOC) - return CHUNK_ALLOC_SIZE(target); - size_t sz = MIN_CHUNK_ALLOC; - while (CHUNK_SIZE_WITH_ALLOC(sz) < target) { - sz <<= 1; - } - return sz; -} - -/** Collapse data from the first N chunks from buf into buf->head, - * growing it as necessary, until buf->head has the first bytes bytes - * of data from the buffer, or until buf->head has all the data in buf. - * - * Set *head_out to point to the first byte of available data, and - * *len_out to the number of bytes of data available at - * *head_out. Note that *len_out may be more or less than - * bytes, depending on the number of bytes available. - */ -void -buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out) -{ - chunk_t *dest, *src; - size_t capacity; - if (!buf->head) { - *head_out = NULL; - *len_out = 0; - return; - } - - check(); - if (buf->datalen < bytes) - bytes = buf->datalen; - - capacity = bytes; - if (buf->head->datalen >= bytes) { - *head_out = buf->head->data; - *len_out = buf->head->datalen; - return; - } - - if (buf->head->memlen >= capacity) { - /* We don't need to grow the first chunk, but we might need to repack it.*/ - size_t needed = capacity - buf->head->datalen; - if (CHUNK_REMAINING_CAPACITY(buf->head) < needed) - chunk_repack(buf->head); - tor_assert(CHUNK_REMAINING_CAPACITY(buf->head) >= needed); - } else { - chunk_t *newhead; - size_t newsize; - /* We need to grow the chunk. */ - chunk_repack(buf->head); - newsize = CHUNK_SIZE_WITH_ALLOC(buf_preferred_chunk_size(capacity)); - newhead = chunk_grow(buf->head, newsize); - tor_assert(newhead->memlen >= capacity); - if (newhead != buf->head) { - if (buf->tail == buf->head) - buf->tail = newhead; - buf->head = newhead; - } - } - - dest = buf->head; - while (dest->datalen < bytes) { - size_t n = bytes - dest->datalen; - src = dest->next; - tor_assert(src); - if (n >= src->datalen) { - memcpy(CHUNK_WRITE_PTR(dest), src->data, src->datalen); - dest->datalen += src->datalen; - dest->next = src->next; - if (buf->tail == src) - buf->tail = dest; - buf_chunk_free_unchecked(src); - } else { - memcpy(CHUNK_WRITE_PTR(dest), src->data, n); - dest->datalen += n; - src->data += n; - src->datalen -= n; - tor_assert(dest->datalen == bytes); - } - } - - check(); - *head_out = buf->head->data; - *len_out = buf->head->datalen; -} - -#ifdef TOR_UNIT_TESTS -/* Write sz bytes from cp into a newly allocated buffer buf. - * Returns NULL when passed a NULL cp or zero sz. - * Asserts on failure: only for use in unit tests. - * buf must be freed using buf_free(). */ -buf_t * -buf_new_with_data(const char *cp, size_t sz) -{ - /* Validate arguments */ - if (!cp || sz <= 0) { - return NULL; - } - - tor_assert(sz < SSIZE_T_CEILING); - - /* Allocate a buffer */ - buf_t *buf = buf_new_with_capacity(sz); - tor_assert(buf); - buf_assert_ok(buf); - tor_assert(!buf->head); - - /* Allocate a chunk that is sz bytes long */ - buf->head = chunk_new_with_alloc_size(CHUNK_ALLOC_SIZE(sz)); - buf->tail = buf->head; - tor_assert(buf->head); - buf_assert_ok(buf); - tor_assert(buf_allocation(buf) >= sz); - - /* Copy the data and size the buffers */ - tor_assert(sz <= buf_slack(buf)); - tor_assert(sz <= CHUNK_REMAINING_CAPACITY(buf->head)); - memcpy(&buf->head->mem[0], cp, sz); - buf->datalen = sz; - buf->head->datalen = sz; - buf->head->data = &buf->head->mem[0]; - buf_assert_ok(buf); - - /* Make sure everything is large enough */ - tor_assert(buf_allocation(buf) >= sz); - tor_assert(buf_allocation(buf) >= buf_datalen(buf) + buf_slack(buf)); - /* Does the buffer implementation allocate more than the requested size? - * (for example, by rounding up). If so, these checks will fail. */ - tor_assert(buf_datalen(buf) == sz); - tor_assert(buf_slack(buf) == 0); - - return buf; -} -#endif /* defined(TOR_UNIT_TESTS) */ - -/** Remove the first n bytes from buf. */ -void -buf_drain(buf_t *buf, size_t n) -{ - tor_assert(buf->datalen >= n); - while (n) { - tor_assert(buf->head); - if (buf->head->datalen > n) { - buf->head->datalen -= n; - buf->head->data += n; - buf->datalen -= n; - return; - } else { - chunk_t *victim = buf->head; - n -= victim->datalen; - buf->datalen -= victim->datalen; - buf->head = victim->next; - if (buf->tail == victim) - buf->tail = NULL; - buf_chunk_free_unchecked(victim); - } - } - check(); -} - -/** Create and return a new buf with default chunk capacity size. - */ -buf_t * -buf_new_with_capacity(size_t size) -{ - buf_t *b = buf_new(); - b->default_chunk_size = buf_preferred_chunk_size(size); - return b; -} - -/** Allocate and return a new buffer with default capacity. */ -buf_t * -buf_new(void) -{ - buf_t *buf = tor_malloc_zero(sizeof(buf_t)); - buf->magic = BUFFER_MAGIC; - buf->default_chunk_size = 4096; - return buf; -} - -size_t -buf_get_default_chunk_size(const buf_t *buf) -{ - return buf->default_chunk_size; -} - -/** Remove all data from buf. */ -void -buf_clear(buf_t *buf) -{ - chunk_t *chunk, *next; - buf->datalen = 0; - for (chunk = buf->head; chunk; chunk = next) { - next = chunk->next; - buf_chunk_free_unchecked(chunk); - } - buf->head = buf->tail = NULL; -} - -/** Return the number of bytes stored in buf */ -MOCK_IMPL(size_t, -buf_datalen, (const buf_t *buf)) -{ - return buf->datalen; -} - -/** Return the total length of all chunks used in buf. */ -size_t -buf_allocation(const buf_t *buf) -{ - size_t total = 0; - const chunk_t *chunk; - for (chunk = buf->head; chunk; chunk = chunk->next) { - total += CHUNK_ALLOC_SIZE(chunk->memlen); - } - return total; -} - -/** Return the number of bytes that can be added to buf without - * performing any additional allocation. */ -size_t -buf_slack(const buf_t *buf) -{ - if (!buf->tail) - return 0; - else - return CHUNK_REMAINING_CAPACITY(buf->tail); -} - -/** Release storage held by buf. */ -void -buf_free_(buf_t *buf) -{ - if (!buf) - return; - - buf_clear(buf); - buf->magic = 0xdeadbeef; - tor_free(buf); -} - -/** Return a new copy of in_chunk */ -static chunk_t * -chunk_copy(const chunk_t *in_chunk) -{ - chunk_t *newch = tor_memdup(in_chunk, CHUNK_ALLOC_SIZE(in_chunk->memlen)); - total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(in_chunk->memlen); -#ifdef DEBUG_CHUNK_ALLOC - newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen); -#endif - newch->next = NULL; - if (in_chunk->data) { - off_t offset = in_chunk->data - in_chunk->mem; - newch->data = newch->mem + offset; - } - return newch; -} - -/** Return a new copy of buf */ -buf_t * -buf_copy(const buf_t *buf) -{ - chunk_t *ch; - buf_t *out = buf_new(); - out->default_chunk_size = buf->default_chunk_size; - for (ch = buf->head; ch; ch = ch->next) { - chunk_t *newch = chunk_copy(ch); - if (out->tail) { - out->tail->next = newch; - out->tail = newch; - } else { - out->head = out->tail = newch; - } - } - out->datalen = buf->datalen; - return out; -} - -/** Append a new chunk with enough capacity to hold capacity bytes to - * the tail of buf. If capped, don't allocate a chunk bigger - * than MAX_CHUNK_ALLOC. */ -chunk_t * -buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped) -{ - chunk_t *chunk; - - if (CHUNK_ALLOC_SIZE(capacity) < buf->default_chunk_size) { - chunk = chunk_new_with_alloc_size(buf->default_chunk_size); - } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) { - chunk = chunk_new_with_alloc_size(MAX_CHUNK_ALLOC); - } else { - chunk = chunk_new_with_alloc_size(buf_preferred_chunk_size(capacity)); - } - - chunk->inserted_time = monotime_coarse_get_stamp(); - - if (buf->tail) { - tor_assert(buf->head); - buf->tail->next = chunk; - buf->tail = chunk; - } else { - tor_assert(!buf->head); - buf->head = buf->tail = chunk; - } - check(); - return chunk; -} - -/** Return the age of the oldest chunk in the buffer buf, in - * timestamp units. Requires the current monotonic timestamp as its - * input now. - */ -uint32_t -buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now) -{ - if (buf->head) { - return now - buf->head->inserted_time; - } else { - return 0; - } -} - -size_t -buf_get_total_allocation(void) -{ - return total_bytes_allocated_in_chunks; -} - -/** Append string_len bytes from string to the end of - * buf. - * - * Return the new length of the buffer on success, -1 on failure. - */ -int -buf_add(buf_t *buf, const char *string, size_t string_len) -{ - if (!string_len) - return (int)buf->datalen; - check(); - - if (BUG(buf->datalen >= INT_MAX)) - return -1; - if (BUG(buf->datalen >= INT_MAX - string_len)) - return -1; - - while (string_len) { - size_t copy; - if (!buf->tail || !CHUNK_REMAINING_CAPACITY(buf->tail)) - buf_add_chunk_with_capacity(buf, string_len, 1); - - copy = CHUNK_REMAINING_CAPACITY(buf->tail); - if (copy > string_len) - copy = string_len; - memcpy(CHUNK_WRITE_PTR(buf->tail), string, copy); - string_len -= copy; - string += copy; - buf->datalen += copy; - buf->tail->datalen += copy; - } - - check(); - tor_assert(buf->datalen < INT_MAX); - return (int)buf->datalen; -} - -/** Add a nul-terminated string to buf, not including the - * terminating NUL. */ -void -buf_add_string(buf_t *buf, const char *string) -{ - buf_add(buf, string, strlen(string)); -} - -/** As tor_snprintf, but write the results into a buf_t */ -void -buf_add_printf(buf_t *buf, const char *format, ...) -{ - va_list ap; - va_start(ap,format); - buf_add_vprintf(buf, format, ap); - va_end(ap); -} - -/** As tor_vsnprintf, but write the results into a buf_t. */ -void -buf_add_vprintf(buf_t *buf, const char *format, va_list args) -{ - /* XXXX Faster implementations are easy enough, but let's optimize later */ - char *tmp; - tor_vasprintf(&tmp, format, args); - buf_add(buf, tmp, strlen(tmp)); - tor_free(tmp); -} - -/** Return a heap-allocated string containing the contents of buf, plus - * a NUL byte. If sz_out is provided, set *sz_out to the length - * of the returned string, not including the terminating NUL. */ -char * -buf_extract(buf_t *buf, size_t *sz_out) -{ - tor_assert(buf); - - size_t sz = buf_datalen(buf); - char *result; - result = tor_malloc(sz+1); - buf_peek(buf, result, sz); - result[sz] = 0; - if (sz_out) - *sz_out = sz; - return result; -} - -/** Helper: copy the first string_len bytes from buf - * onto string. - */ -void -buf_peek(const buf_t *buf, char *string, size_t string_len) -{ - chunk_t *chunk; - - tor_assert(string); - /* make sure we don't ask for too much */ - tor_assert(string_len <= buf->datalen); - /* buf_assert_ok(buf); */ - - chunk = buf->head; - while (string_len) { - size_t copy = string_len; - tor_assert(chunk); - if (chunk->datalen < copy) - copy = chunk->datalen; - memcpy(string, chunk->data, copy); - string_len -= copy; - string += copy; - chunk = chunk->next; - } -} - -/** Remove string_len bytes from the front of buf, and store - * them into string. Return the new buffer size. string_len - * must be \<= the number of bytes on the buffer. - */ -int -buf_get_bytes(buf_t *buf, char *string, size_t string_len) -{ - /* There must be string_len bytes in buf; write them onto string, - * then memmove buf back (that is, remove them from buf). - * - * Return the number of bytes still on the buffer. */ - - check(); - buf_peek(buf, string, string_len); - buf_drain(buf, string_len); - check(); - tor_assert(buf->datalen < INT_MAX); - return (int)buf->datalen; -} - -/** Move up to *buf_flushlen bytes from buf_in to - * buf_out, and modify *buf_flushlen appropriately. - * Return the number of bytes actually copied. - */ -int -buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen) -{ - /* We can do way better here, but this doesn't turn up in any profiles. */ - char b[4096]; - size_t cp, len; - - if (BUG(buf_out->datalen >= INT_MAX)) - return -1; - if (BUG(buf_out->datalen >= INT_MAX - *buf_flushlen)) - return -1; - - len = *buf_flushlen; - if (len > buf_in->datalen) - len = buf_in->datalen; - - cp = len; /* Remember the number of bytes we intend to copy. */ - tor_assert(cp < INT_MAX); - while (len) { - /* This isn't the most efficient implementation one could imagine, since - * it does two copies instead of 1, but I kinda doubt that this will be - * critical path. */ - size_t n = len > sizeof(b) ? sizeof(b) : len; - buf_get_bytes(buf_in, b, n); - buf_add(buf_out, b, n); - len -= n; - } - *buf_flushlen -= cp; - return (int)cp; -} - -/** Moves all data from buf_in to buf_out, without copying. - */ -void -buf_move_all(buf_t *buf_out, buf_t *buf_in) -{ - tor_assert(buf_out); - if (!buf_in) - return; - - if (buf_out->head == NULL) { - buf_out->head = buf_in->head; - buf_out->tail = buf_in->tail; - } else { - buf_out->tail->next = buf_in->head; - buf_out->tail = buf_in->tail; - } - - buf_out->datalen += buf_in->datalen; - buf_in->head = buf_in->tail = NULL; - buf_in->datalen = 0; -} - -/** Internal structure: represents a position in a buffer. */ -typedef struct buf_pos_t { - const chunk_t *chunk; /**< Which chunk are we pointing to? */ - int pos;/**< Which character inside the chunk's data are we pointing to? */ - size_t chunk_pos; /**< Total length of all previous chunks. */ -} buf_pos_t; - -/** Initialize out to point to the first character of buf.*/ -static void -buf_pos_init(const buf_t *buf, buf_pos_t *out) -{ - out->chunk = buf->head; - out->pos = 0; - out->chunk_pos = 0; -} - -/** Advance out to the first appearance of ch at the current - * position of out, or later. Return -1 if no instances are found; - * otherwise returns the absolute position of the character. */ -static off_t -buf_find_pos_of_char(char ch, buf_pos_t *out) -{ - const chunk_t *chunk; - int pos; - tor_assert(out); - if (out->chunk) { - if (out->chunk->datalen) { - tor_assert(out->pos < (off_t)out->chunk->datalen); - } else { - tor_assert(out->pos == 0); - } - } - pos = out->pos; - for (chunk = out->chunk; chunk; chunk = chunk->next) { - char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos); - if (cp) { - out->chunk = chunk; - tor_assert(cp - chunk->data < INT_MAX); - out->pos = (int)(cp - chunk->data); - return out->chunk_pos + out->pos; - } else { - out->chunk_pos += chunk->datalen; - pos = 0; - } - } - return -1; -} - -/** Advance pos by a single character, if there are any more characters - * in the buffer. Returns 0 on success, -1 on failure. */ -static inline int -buf_pos_inc(buf_pos_t *pos) -{ - ++pos->pos; - if (pos->pos == (off_t)pos->chunk->datalen) { - if (!pos->chunk->next) - return -1; - pos->chunk_pos += pos->chunk->datalen; - pos->chunk = pos->chunk->next; - pos->pos = 0; - } - return 0; -} - -/** Return true iff the n-character string in s appears - * (verbatim) at pos. */ -static int -buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n) -{ - buf_pos_t p; - if (!n) - return 1; - - memcpy(&p, pos, sizeof(p)); - - while (1) { - char ch = p.chunk->data[p.pos]; - if (ch != *s) - return 0; - ++s; - /* If we're out of characters that don't match, we match. Check this - * _before_ we test incrementing pos, in case we're at the end of the - * string. */ - if (--n == 0) - return 1; - if (buf_pos_inc(&p)<0) - return 0; - } -} - -/** Return the first position in buf at which the n-character - * string s occurs, or -1 if it does not occur. */ -int -buf_find_string_offset(const buf_t *buf, const char *s, size_t n) -{ - buf_pos_t pos; - buf_pos_init(buf, &pos); - while (buf_find_pos_of_char(*s, &pos) >= 0) { - if (buf_matches_at_pos(&pos, s, n)) { - tor_assert(pos.chunk_pos + pos.pos < INT_MAX); - return (int)(pos.chunk_pos + pos.pos); - } else { - if (buf_pos_inc(&pos)<0) - return -1; - } - } - return -1; -} - -/** Return 1 iff buf starts with cmd. cmd must be a null - * terminated string, of no more than PEEK_BUF_STARTSWITH_MAX bytes. */ -int -buf_peek_startswith(const buf_t *buf, const char *cmd) -{ - char tmp[PEEK_BUF_STARTSWITH_MAX]; - size_t clen = strlen(cmd); - if (clen == 0) - return 1; - if (BUG(clen > sizeof(tmp))) - return 0; - if (buf->datalen < clen) - return 0; - buf_peek(buf, tmp, clen); - return fast_memeq(tmp, cmd, clen); -} - -/** Return the index within buf at which ch first appears, - * or -1 if ch does not appear on buf. */ -static off_t -buf_find_offset_of_char(buf_t *buf, char ch) -{ - chunk_t *chunk; - off_t offset = 0; - for (chunk = buf->head; chunk; chunk = chunk->next) { - char *cp = memchr(chunk->data, ch, chunk->datalen); - if (cp) - return offset + (cp - chunk->data); - else - offset += chunk->datalen; - } - return -1; -} - -/** Try to read a single LF-terminated line from buf, and write it - * (including the LF), NUL-terminated, into the *data_len byte buffer - * at data_out. Set *data_len to the number of bytes in the - * line, not counting the terminating NUL. Return 1 if we read a whole line, - * return 0 if we don't have a whole line yet, and return -1 if the line - * length exceeds *data_len. - */ -int -buf_get_line(buf_t *buf, char *data_out, size_t *data_len) -{ - size_t sz; - off_t offset; - - if (!buf->head) - return 0; - - offset = buf_find_offset_of_char(buf, '\n'); - if (offset < 0) - return 0; - sz = (size_t) offset; - if (sz+2 > *data_len) { - *data_len = sz + 2; - return -1; - } - buf_get_bytes(buf, data_out, sz+1); - data_out[sz+1] = '\0'; - *data_len = sz+1; - return 1; -} - -/** Set *output to contain a copy of the data in *input */ -int -buf_set_to_copy(buf_t **output, - const buf_t *input) -{ - if (*output) - buf_free(*output); - *output = buf_copy(input); - return 0; -} - -/** Log an error and exit if buf is corrupted. - */ -void -buf_assert_ok(buf_t *buf) -{ - tor_assert(buf); - tor_assert(buf->magic == BUFFER_MAGIC); - - if (! buf->head) { - tor_assert(!buf->tail); - tor_assert(buf->datalen == 0); - } else { - chunk_t *ch; - size_t total = 0; - tor_assert(buf->tail); - for (ch = buf->head; ch; ch = ch->next) { - total += ch->datalen; - tor_assert(ch->datalen <= ch->memlen); - tor_assert(ch->data >= &ch->mem[0]); - tor_assert(ch->data <= &ch->mem[0]+ch->memlen); - if (ch->data == &ch->mem[0]+ch->memlen) { - /* LCOV_EXCL_START */ - static int warned = 0; - if (! warned) { - log_warn(LD_BUG, "Invariant violation in buf.c related to #15083"); - warned = 1; - } - /* LCOV_EXCL_STOP */ - } - tor_assert(ch->data+ch->datalen <= &ch->mem[0] + ch->memlen); - if (!ch->next) - tor_assert(ch == buf->tail); - } - tor_assert(buf->datalen == total); - } -} diff --git a/src/lib/container/buffers.h b/src/lib/container/buffers.h deleted file mode 100644 index c48f83cfc7..0000000000 --- a/src/lib/container/buffers.h +++ /dev/null @@ -1,122 +0,0 @@ -/* 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 buffers.h - * - * \brief Header file for buffers.c. - **/ - -#ifndef TOR_BUFFERS_H -#define TOR_BUFFERS_H - -#include "lib/cc/compat_compiler.h" -#include "lib/cc/torint.h" -#include "lib/testsupport/testsupport.h" - -#include - -typedef struct buf_t buf_t; - -buf_t *buf_new(void); -buf_t *buf_new_with_capacity(size_t size); -size_t buf_get_default_chunk_size(const buf_t *buf); -void buf_free_(buf_t *buf); -#define buf_free(b) FREE_AND_NULL(buf_t, buf_free_, (b)) -void buf_clear(buf_t *buf); -buf_t *buf_copy(const buf_t *buf); - -MOCK_DECL(size_t, buf_datalen, (const buf_t *buf)); -size_t buf_allocation(const buf_t *buf); -size_t buf_slack(const buf_t *buf); - -uint32_t buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now); -size_t buf_get_total_allocation(void); - -int buf_add(buf_t *buf, const char *string, size_t string_len); -void buf_add_string(buf_t *buf, const char *string); -void buf_add_printf(buf_t *buf, const char *format, ...) - CHECK_PRINTF(2, 3); -void buf_add_vprintf(buf_t *buf, const char *format, va_list args) - CHECK_PRINTF(2, 0); -int buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen); -void buf_move_all(buf_t *buf_out, buf_t *buf_in); -void buf_peek(const buf_t *buf, char *string, size_t string_len); -void buf_drain(buf_t *buf, size_t n); -int buf_get_bytes(buf_t *buf, char *string, size_t string_len); -int buf_get_line(buf_t *buf, char *data_out, size_t *data_len); - -#define PEEK_BUF_STARTSWITH_MAX 16 -int buf_peek_startswith(const buf_t *buf, const char *cmd); - -int buf_set_to_copy(buf_t **output, - const buf_t *input); - -void buf_assert_ok(buf_t *buf); - -int buf_find_string_offset(const buf_t *buf, const char *s, size_t n); -void buf_pullup(buf_t *buf, size_t bytes, - const char **head_out, size_t *len_out); -char *buf_extract(buf_t *buf, size_t *sz_out); - -#ifdef BUFFERS_PRIVATE -#ifdef TOR_UNIT_TESTS -buf_t *buf_new_with_data(const char *cp, size_t sz); -#endif -size_t buf_preferred_chunk_size(size_t target); - -#define DEBUG_CHUNK_ALLOC -/** A single chunk on a buffer. */ -typedef struct chunk_t { - struct chunk_t *next; /**< The next chunk on the buffer. */ - size_t datalen; /**< The number of bytes stored in this chunk */ - size_t memlen; /**< The number of usable bytes of storage in mem. */ -#ifdef DEBUG_CHUNK_ALLOC - size_t DBG_alloc; -#endif - char *data; /**< A pointer to the first byte of data stored in mem. */ - uint32_t inserted_time; /**< Timestamp when this chunk was inserted. */ - char mem[FLEXIBLE_ARRAY_MEMBER]; /**< The actual memory used for storage in - * this chunk. */ -} chunk_t; - -/** Magic value for buf_t.magic, to catch pointer errors. */ -#define BUFFER_MAGIC 0xB0FFF312u -/** A resizeable buffer, optimized for reading and writing. */ -struct buf_t { - uint32_t magic; /**< Magic cookie for debugging: Must be set to - * BUFFER_MAGIC. */ - size_t datalen; /**< How many bytes is this buffer holding right now? */ - size_t default_chunk_size; /**< Don't allocate any chunks smaller than - * this for this buffer. */ - chunk_t *head; /**< First chunk in the list, or NULL for none. */ - chunk_t *tail; /**< Last chunk in the list, or NULL for none. */ -}; - -chunk_t *buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped); -/** If a read onto the end of a chunk would be smaller than this number, then - * just start a new chunk. */ -#define MIN_READ_LEN 8 - -/** Return the number of bytes that can be written onto chunk without - * running out of space. */ -static inline size_t -CHUNK_REMAINING_CAPACITY(const chunk_t *chunk) -{ - return (chunk->mem + chunk->memlen) - (chunk->data + chunk->datalen); -} - -/** Return the next character in chunk onto which data can be appended. - * If the chunk is full, this might be off the end of chunk->mem. */ -static inline char * -CHUNK_WRITE_PTR(chunk_t *chunk) -{ - return chunk->data + chunk->datalen; -} - -#endif /* defined(BUFFERS_PRIVATE) */ - -#endif /* !defined(TOR_BUFFERS_H) */ diff --git a/src/lib/container/include.am b/src/lib/container/include.am index e6492098b5..032e4033da 100644 --- a/src/lib/container/include.am +++ b/src/lib/container/include.am @@ -7,7 +7,6 @@ endif src_lib_libtor_container_a_SOURCES = \ src/lib/container/bloomfilt.c \ - src/lib/container/buffers.c \ src/lib/container/map.c \ src/lib/container/order.c \ src/lib/container/smartlist.c @@ -20,7 +19,6 @@ src_lib_libtor_container_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) noinst_HEADERS += \ src/lib/container/bitarray.h \ src/lib/container/bloomfilt.h \ - src/lib/container/buffers.h \ src/lib/container/handles.h \ src/lib/container/map.h \ src/lib/container/order.h \ diff --git a/src/lib/net/.may_include b/src/lib/net/.may_include index f93f0e1552..d34aaed2ca 100644 --- a/src/lib/net/.may_include +++ b/src/lib/net/.may_include @@ -3,6 +3,7 @@ siphash.h ht.h lib/arch/*.h +lib/buf/*.h lib/cc/*.h lib/container/*.h lib/ctime/*.h diff --git a/src/lib/net/buffers_net.c b/src/lib/net/buffers_net.c index c52ea2784e..b0936e9928 100644 --- a/src/lib/net/buffers_net.c +++ b/src/lib/net/buffers_net.c @@ -11,7 +11,7 @@ #define BUFFERS_PRIVATE #include "lib/net/buffers_net.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/log/log.h" #include "lib/log/util_bug.h" #include "lib/net/nettypes.h" diff --git a/src/lib/tls/.may_include b/src/lib/tls/.may_include index 79301bc318..069181b70e 100644 --- a/src/lib/tls/.may_include +++ b/src/lib/tls/.may_include @@ -1,6 +1,7 @@ orconfig.h lib/arch/*.h +lib/buf/*.h lib/cc/*.h lib/container/*.h lib/crypt_ops/*.h diff --git a/src/lib/tls/buffers_tls.c b/src/lib/tls/buffers_tls.c index 69ae4f7fc0..b4059292ea 100644 --- a/src/lib/tls/buffers_tls.c +++ b/src/lib/tls/buffers_tls.c @@ -12,7 +12,7 @@ #define BUFFERS_PRIVATE #include "orconfig.h" #include -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/tls/buffers_tls.h" #include "lib/cc/torint.h" #include "lib/log/log.h" diff --git a/src/test/fuzz/fuzz_http.c b/src/test/fuzz/fuzz_http.c index 06483282bc..4341bfabae 100644 --- a/src/test/fuzz/fuzz_http.c +++ b/src/test/fuzz/fuzz_http.c @@ -8,7 +8,7 @@ #include "core/or/or.h" #include "lib/err/backtrace.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "app/config/config.h" #include "core/mainloop/connection.h" #include "feature/dircache/dircache.h" diff --git a/src/test/fuzz/fuzz_http_connect.c b/src/test/fuzz/fuzz_http_connect.c index ca007a2c7f..e03d9e29d8 100644 --- a/src/test/fuzz/fuzz_http_connect.c +++ b/src/test/fuzz/fuzz_http_connect.c @@ -8,7 +8,7 @@ #include "core/or/or.h" #include "lib/err/backtrace.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "app/config/config.h" #include "core/mainloop/connection.h" #include "core/or/connection_edge.h" diff --git a/src/test/fuzz/fuzz_socks.c b/src/test/fuzz/fuzz_socks.c index 14c25304b1..2d93bea924 100644 --- a/src/test/fuzz/fuzz_socks.c +++ b/src/test/fuzz/fuzz_socks.c @@ -6,7 +6,7 @@ #define BUFFERS_PRIVATE #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/err/backtrace.h" #include "lib/log/log.h" #include "core/proto/proto_socks.h" diff --git a/src/test/test.c b/src/test/test.c index 17b736d305..a654030fac 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -37,7 +37,7 @@ #include "core/or/or.h" #include "lib/err/backtrace.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/or/circuitlist.h" #include "core/or/circuitstats.h" #include "lib/compress/compress.h" diff --git a/src/test/test_buffers.c b/src/test/test_buffers.c index 477066f699..85e7b8d90a 100644 --- a/src/test/test_buffers.c +++ b/src/test/test_buffers.c @@ -6,7 +6,7 @@ #define BUFFERS_PRIVATE #define PROTO_HTTP_PRIVATE #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "lib/tls/buffers_tls.h" #include "lib/tls/tortls.h" #include "lib/compress/compress.h" diff --git a/src/test/test_channelpadding.c b/src/test/test_channelpadding.c index 0fd60d0a92..bdd7c5f0a6 100644 --- a/src/test/test_channelpadding.c +++ b/src/test/test_channelpadding.c @@ -21,7 +21,7 @@ #include "test/log_test_helpers.h" #include "lib/tls/tortls.h" #include "lib/evloop/timers.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/or/cell_st.h" #include "feature/nodelist/networkstatus_st.h" diff --git a/src/test/test_channeltls.c b/src/test/test_channeltls.c index 787a30a85d..44d623561b 100644 --- a/src/test/test_channeltls.c +++ b/src/test/test_channeltls.c @@ -8,7 +8,7 @@ #define TOR_CHANNEL_INTERNAL_ #include "core/or/or.h" #include "lib/net/address.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/or/channel.h" #include "core/or/channeltls.h" #include "core/mainloop/connection.h" diff --git a/src/test/test_extorport.c b/src/test/test_extorport.c index 71be9131c7..432a9ea5e3 100644 --- a/src/test/test_extorport.c +++ b/src/test/test_extorport.c @@ -5,7 +5,7 @@ #define EXT_ORPORT_PRIVATE #define MAINLOOP_PRIVATE #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/mainloop/connection.h" #include "core/or/connection_or.h" #include "app/config/config.h" diff --git a/src/test/test_helpers.c b/src/test/test_helpers.c index 6ac73bff5c..b7bda16494 100644 --- a/src/test/test_helpers.c +++ b/src/test/test_helpers.c @@ -14,7 +14,7 @@ #include "orconfig.h" #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "app/config/config.h" #include "app/config/confparse.h" #include "core/mainloop/connection.h" diff --git a/src/test/test_oom.c b/src/test/test_oom.c index 313a6b3114..f84dc0764b 100644 --- a/src/test/test_oom.c +++ b/src/test/test_oom.c @@ -8,7 +8,7 @@ #define CIRCUITLIST_PRIVATE #define CONNECTION_PRIVATE #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/or/circuitlist.h" #include "lib/evloop/compat_libevent.h" #include "core/mainloop/connection.h" diff --git a/src/test/test_proto_http.c b/src/test/test_proto_http.c index 1cfa0a752c..b4e8278423 100644 --- a/src/test/test_proto_http.c +++ b/src/test/test_proto_http.c @@ -8,7 +8,7 @@ #include "core/or/or.h" #include "test/test.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/proto/proto_http.h" #include "test/log_test_helpers.h" diff --git a/src/test/test_proto_misc.c b/src/test/test_proto_misc.c index 1fcb763421..f7f6f69667 100644 --- a/src/test/test_proto_misc.c +++ b/src/test/test_proto_misc.c @@ -8,7 +8,7 @@ #include "core/or/or.h" #include "test/test.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "core/or/connection_or.h" #include "feature/relay/ext_orport.h" #include "core/proto/proto_cell.h" diff --git a/src/test/test_routerlist.c b/src/test/test_routerlist.c index 1071a095fe..167b7a35ce 100644 --- a/src/test/test_routerlist.c +++ b/src/test/test_routerlist.c @@ -46,7 +46,7 @@ #include "feature/nodelist/routerstatus_st.h" #include "lib/encoding/confline.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "test/test.h" #include "test/test_dir_common.h" diff --git a/src/test/test_socks.c b/src/test/test_socks.c index 7f6d8a48f1..d430f4329b 100644 --- a/src/test/test_socks.c +++ b/src/test/test_socks.c @@ -4,7 +4,7 @@ /* See LICENSE for licensing information */ #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "app/config/config.h" #include "core/mainloop/connection.h" #include "core/proto/proto_socks.h" diff --git a/src/test/test_util.c b/src/test/test_util.c index bcface64fd..2b4d64e42e 100644 --- a/src/test/test_util.c +++ b/src/test/test_util.c @@ -13,7 +13,7 @@ #define SUBPROCESS_PRIVATE #include "lib/testsupport/testsupport.h" #include "core/or/or.h" -#include "lib/container/buffers.h" +#include "lib/buf/buffers.h" #include "app/config/config.h" #include "feature/control/control.h" #include "feature/client/transports.h" -- cgit v1.2.3-54-g00ecf