March 2014 - tor-commits - lists.torproject.org

[tor/master] Merge remote-tracking branch 'public/bug10169_023' into bug10169_024
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit 05d8111eedee9e11e4bb1c42e93ae2fc168d52ec Merge: 5c45a33 fd28754 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 12:39:15 2014 -0500 Merge remote-tracking branch 'public/bug10169_023' into bug10169_024 src/or/buffers.c | 18 +++++++++++++----- src/or/buffers.h | 2 +- src/or/circuitlist.c | 13 +++++++++++++ 3 files changed, 27 insertions(+), 6 deletions(-)

1 0

[tor/master] Add tests for buffer time tracking.
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit 52d222aafbc21d674624fdd4c8fc834a40af69c7 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jan 9 12:47:24 2014 -0500 Add tests for buffer time tracking. --- src/common/compat_libevent.c | 14 +++++++- src/common/compat_libevent.h | 3 ++ src/test/test_buffers.c | 73 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 89 insertions(+), 1 deletion(-) diff --git a/src/common/compat_libevent.c b/src/common/compat_libevent.c index 4d0fff8..b7987bc 100644 --- a/src/common/compat_libevent.c +++ b/src/common/compat_libevent.c @@ -626,7 +626,9 @@ tor_add_bufferevent_to_rate_limit_group(struct bufferevent *bev, } #endif -#if defined(LIBEVENT_VERSION_NUMBER) && LIBEVENT_VERSION_NUMBER >= V(2,1,1) + +#if defined(LIBEVENT_VERSION_NUMBER) && LIBEVENT_VERSION_NUMBER >= V(2,1,1) \ + && !defined(TOR_UNIT_TESTS) void tor_gettimeofday_cached(struct timeval *tv) { @@ -659,5 +661,15 @@ tor_gettimeofday_cache_clear(void) { cached_time_hires.tv_sec = 0; } + +#ifdef TOR_UNIT_TESTS +/** For testing: force-update the cached time to a given value. */ +void +tor_gettimeofday_cache_set(const struct timeval *tv) +{ + tor_assert(tv); + memcpy(&cached_time_hires, tv, sizeof(*tv)); +} +#endif #endif diff --git a/src/common/compat_libevent.h b/src/common/compat_libevent.h index fda8733..17e0523 100644 --- a/src/common/compat_libevent.h +++ b/src/common/compat_libevent.h @@ -91,6 +91,9 @@ int tor_add_bufferevent_to_rate_limit_group(struct bufferevent *bev, void tor_gettimeofday_cached(struct timeval *tv); void tor_gettimeofday_cache_clear(void); +#ifdef TOR_UNIT_TESTS +void tor_gettimeofday_cache_set(const struct timeval *tv); +#endif #endif diff --git a/src/test/test_buffers.c b/src/test/test_buffers.c index ab1e5df..a410770 100644 --- a/src/test/test_buffers.c +++ b/src/test/test_buffers.c @@ -516,6 +516,78 @@ test_buffer_allocation_tracking(void *arg) buf_shrink_freelists(1); } +static void +test_buffer_time_tracking(void *arg) +{ + buf_t *buf=NULL, *buf2=NULL; + struct timeval tv0; + const time_t START = 1389288246; + const uint32_t START_MSEC = (uint32_t) ((uint64_t)START * 1000); + int i; + char tmp[4096]; + (void)arg; + + crypto_rand(tmp, sizeof(tmp)); + + tv0.tv_sec = START; + tv0.tv_usec = 0; + + buf = buf_new_with_capacity(3000); /* rounds up to next power of 2. */ + tt_assert(buf); + + /* Empty buffer means the timestamp is 0. */ + tt_int_op(0, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC)); + tt_int_op(0, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+1000)); + + tor_gettimeofday_cache_set(&tv0); + write_to_buf("ABCDEFG", 7, buf); + tt_int_op(1000, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+1000)); + + buf2 = buf_copy(buf); + tt_assert(buf2); + tt_int_op(1234, ==, buf_get_oldest_chunk_timestamp(buf2, START_MSEC+1234)); + + /* Now add more bytes; enough to overflow the first chunk. */ + tv0.tv_usec += 123 * 1000; + tor_gettimeofday_cache_set(&tv0); + for (i = 0; i < 600; ++i) + write_to_buf("ABCDEFG", 7, buf); + tt_int_op(4207, ==, buf_datalen(buf)); + + /* The oldest bytes are still in the front. */ + tt_int_op(2000, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+2000)); + + /* Once those bytes are dropped, the chunk is still on the first + * timestamp. */ + fetch_from_buf(tmp, 100, buf); + tt_int_op(2000, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+2000)); + + /* But once we discard the whole first chunk, we get the data in the second + * chunk. */ + fetch_from_buf(tmp, 4000, buf); + tt_int_op(107, ==, buf_datalen(buf)); + tt_int_op(2000, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+2123)); + + /* This time we'll be grabbing a chunk from the freelist, and making sure + its time gets updated */ + tv0.tv_sec += 5; + tv0.tv_usec = 617*1000; + tor_gettimeofday_cache_set(&tv0); + for (i = 0; i < 600; ++i) + write_to_buf("ABCDEFG", 7, buf); + tt_int_op(4307, ==, buf_datalen(buf)); + + tt_int_op(2000, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+2123)); + fetch_from_buf(tmp, 4000, buf); + fetch_from_buf(tmp, 306, buf); + tt_int_op(0, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+5617)); + tt_int_op(383, ==, buf_get_oldest_chunk_timestamp(buf, START_MSEC+6000)); + + done: + buf_free(buf); + buf_free(buf2); +} + struct testcase_t buffer_tests[] = { { "basic", test_buffers_basic, TT_FORK, NULL, NULL }, { "copy", test_buffer_copy, TT_FORK, NULL, NULL }, @@ -523,6 +595,7 @@ struct testcase_t buffer_tests[] = { { "ext_or_cmd", test_buffer_ext_or_cmd, TT_FORK, NULL, NULL }, { "allocation_tracking", test_buffer_allocation_tracking, TT_FORK, NULL, NULL }, + { "time_tracking", test_buffer_time_tracking, TT_FORK, NULL, NULL }, END_OF_TESTCASES };

1 0

[tor/master] Merge remote-tracking branch 'public/bug10169_024' into bug10169_025_v2
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit 87fb1e324c1b3214765c46bec3d9ec6adc3fa83d Merge: 10d4d3e 05d8111 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 12:44:58 2014 -0500 Merge remote-tracking branch 'public/bug10169_024' into bug10169_025_v2 Conflicts: src/or/circuitlist.c changes/bug10169 | 4 ++ changes/bug9686 | 3 + doc/tor.1.txt | 10 ++-- src/or/buffers.c | 59 ++++++++++++++++++-- src/or/buffers.h | 5 +- src/or/circuitlist.c | 151 +++++++++++++++++++++++++++++++++++++++++--------- src/or/config.c | 9 +-- src/or/or.h | 8 ++- src/or/relay.c | 3 +- 9 files changed, 207 insertions(+), 45 deletions(-) diff --cc src/or/circuitlist.c index 9474896,3081035..eb65230 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@@ -1612,8 -1513,40 +1612,40 @@@ marked_circuit_free_cells(circuit_t *ci cell_queue_clear(& TO_OR_CIRCUIT(circ)->p_chan_cells); } + /** Aggressively free buffer contents on all the buffers of all streams in the + * list starting at stream. Return the number of bytes recovered. */ + static size_t + marked_circuit_streams_free_bytes(edge_connection_t *stream) + { + size_t result = 0; + for ( ; stream; stream = stream->next_stream) { + connection_t *conn = TO_CONN(stream); + if (conn->inbuf) { + result += buf_allocation(conn->inbuf); + buf_clear(conn->inbuf); + } + if (conn->outbuf) { + result += buf_allocation(conn->outbuf); + buf_clear(conn->outbuf); + } + } + return result; + } + + /** Aggressively free buffer contents on all the buffers of all streams on + * circuit c. Return the number of bytes recovered. */ + static size_t + marked_circuit_free_stream_bytes(circuit_t *c) + { + if (CIRCUIT_IS_ORIGIN(c)) { + return marked_circuit_streams_free_bytes(TO_ORIGIN_CIRCUIT(c)->p_streams); + } else { + return marked_circuit_streams_free_bytes(TO_OR_CIRCUIT(c)->n_streams); + } + } + /** Return the number of cells used by the circuit c's cell queues. */ -static size_t +STATIC size_t n_cells_in_circ_queues(const circuit_t *c) { size_t n = c->n_chan_cells.n; @@@ -1700,17 -1691,17 +1792,17 @@@ circuits_handle_oom(size_t current_allo if (current_allocation <= mem_target) return; mem_to_recover = current_allocation - mem_target; - n_cells_to_remove = CEIL_DIV(mem_to_recover, packed_cell_mem_cost()); } + tor_gettimeofday_cached(&now); + now_ms = (uint32_t)tv_to_msec(&now); + /* This algorithm itself assumes that you've got enough memory slack * to actually run it. */ - TOR_LIST_FOREACH(circ, &global_circuitlist, head) - for (circ = global_circuitlist; circ; circ = circ->next) { ++ TOR_LIST_FOREACH(circ, &global_circuitlist, head) { + circ->age_tmp = circuit_max_queued_item_age(circ, now_ms); smartlist_add(circlist, circ); - - /* Set circcomp_now_tmp so that the sort can work. */ - tor_gettimeofday_cached(&now); - circcomp_now_tmp = (uint32_t)tv_to_msec(&now); + } /* This is O(n log n); there are faster algorithms we could use instead. * Let's hope this doesn't happen enough to be in the critical path. */

1 0

[tor/master] Start writing tests for 10169.
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit f425cf833852c4e1b4660cbba6190d04b070f6b6 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat Jan 4 13:30:56 2014 -0500 Start writing tests for 10169. Now we cover more chunk allocation functions. --- src/or/buffers.c | 23 +++++++- src/or/buffers.h | 3 + src/test/test_buffers.c | 148 ++++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 170 insertions(+), 4 deletions(-) diff --git a/src/or/buffers.c b/src/or/buffers.c index c084075..271964c 100644 --- a/src/or/buffers.c +++ b/src/or/buffers.c @@ -423,9 +423,10 @@ struct buf_t { * * If nulterminate is true, ensure that there is a 0 byte in * buf->head->mem right after all the data. */ -static void +STATIC void buf_pullup(buf_t *buf, size_t bytes, int nulterminate) { + /* XXXX nothing uses nulterminate; remove it. */ chunk_t *dest, *src; size_t capacity; if (!buf->head) @@ -497,6 +498,20 @@ buf_pullup(buf_t *buf, size_t bytes, int nulterminate) check(); } +#ifdef TOR_UNIT_TESTS +void +buf_get_first_chunk_data(const buf_t *buf, const char **cp, size_t *sz) +{ + if (!buf || !buf->head) { + *cp = NULL; + *sz = 0; + } else { + *cp = buf->head->data; + *sz = buf->head->datalen; + } +} +#endif + /** Resize buf so it won't hold extra memory that we haven't been * using lately. */ @@ -551,6 +566,12 @@ buf_new(void) 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) diff --git a/src/or/buffers.h b/src/or/buffers.h index 70539bf..a201282 100644 --- a/src/or/buffers.h +++ b/src/or/buffers.h @@ -16,6 +16,7 @@ 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); void buf_clear(buf_t *buf); buf_t *buf_copy(const buf_t *buf); @@ -103,6 +104,8 @@ void assert_buf_ok(buf_t *buf); #ifdef BUFFERS_PRIVATE STATIC int buf_find_string_offset(const buf_t *buf, const char *s, size_t n); +STATIC void buf_pullup(buf_t *buf, size_t bytes, int nulterminate); +void buf_get_first_chunk_data(const buf_t *buf, const char **cp, size_t *sz); #endif #endif diff --git a/src/test/test_buffers.c b/src/test/test_buffers.c index a009faa..bd958b6 100644 --- a/src/test/test_buffers.c +++ b/src/test/test_buffers.c @@ -193,7 +193,120 @@ test_buffers_basic(void *arg) buf_free(buf); if (buf2) buf_free(buf2); + buf_shrink_freelists(1); } + +static void +test_buffer_pullup(void *arg) +{ + buf_t *buf; + char *stuff, *tmp; + const char *cp; + size_t sz; + (void)arg; + stuff = tor_malloc(16384); + tmp = tor_malloc(16384); + + /* Note: this test doesn't check the nulterminate argument to buf_pullup, + since nothing actually uses it. We should remove it some time. */ + + buf = buf_new_with_capacity(3000); /* rounds up to next power of 2. */ + + tt_assert(buf); + tt_int_op(buf_get_default_chunk_size(buf), ==, 4096); + + tt_int_op(buf_get_total_allocation(), ==, 0); + + /* There are a bunch of cases for pullup. One is the trivial case. Let's + mess around with an empty buffer. */ + buf_pullup(buf, 16, 1); + buf_get_first_chunk_data(buf, &cp, &sz); + tt_ptr_op(cp, ==, NULL); + tt_ptr_op(sz, ==, 0); + + /* Let's make sure nothing got allocated */ + tt_int_op(buf_get_total_allocation(), ==, 0); + + /* Case 1: everything puts into the first chunk with some moving. */ + + /* Let's add some data. */ + crypto_rand(stuff, 16384); + write_to_buf(stuff, 3000, buf); + write_to_buf(stuff+3000, 3000, buf); + buf_get_first_chunk_data(buf, &cp, &sz); + tt_ptr_op(cp, !=, NULL); + tt_int_op(sz, <=, 4096); + + /* Make room for 3000 bytes in the first chunk, so that the pullup-move code + * can get tested. */ + tt_int_op(fetch_from_buf(tmp, 3000, buf), ==, 3000); + test_memeq(tmp, stuff, 3000); + buf_pullup(buf, 2048, 0); + assert_buf_ok(buf); + buf_get_first_chunk_data(buf, &cp, &sz); + tt_ptr_op(cp, !=, NULL); + tt_int_op(sz, >=, 2048); + test_memeq(cp, stuff+3000, 2048); + tt_int_op(3000, ==, buf_datalen(buf)); + tt_int_op(fetch_from_buf(tmp, 3000, buf), ==, 0); + test_memeq(tmp, stuff+3000, 2048); + + buf_free(buf); + + /* Now try the large-chunk case. */ + buf = buf_new_with_capacity(3000); /* rounds up to next power of 2. */ + write_to_buf(stuff, 4000, buf); + write_to_buf(stuff+4000, 4000, buf); + write_to_buf(stuff+8000, 4000, buf); + write_to_buf(stuff+12000, 4000, buf); + tt_int_op(buf_datalen(buf), ==, 16000); + buf_get_first_chunk_data(buf, &cp, &sz); + tt_ptr_op(cp, !=, NULL); + tt_int_op(sz, <=, 4096); + + buf_pullup(buf, 12500, 0); + assert_buf_ok(buf); + buf_get_first_chunk_data(buf, &cp, &sz); + tt_ptr_op(cp, !=, NULL); + tt_int_op(sz, >=, 12500); + test_memeq(cp, stuff, 12500); + tt_int_op(buf_datalen(buf), ==, 16000); + + fetch_from_buf(tmp, 12400, buf); + test_memeq(tmp, stuff, 12400); + tt_int_op(buf_datalen(buf), ==, 3600); + fetch_from_buf(tmp, 3500, buf); + test_memeq(tmp, stuff+12400, 3500); + fetch_from_buf(tmp, 100, buf); + test_memeq(tmp, stuff+15900, 10); + + buf_free(buf); + + /* Make sure that the pull-up-whole-buffer case works */ + buf = buf_new_with_capacity(3000); /* rounds up to next power of 2. */ + write_to_buf(stuff, 4000, buf); + write_to_buf(stuff+4000, 4000, buf); + fetch_from_buf(tmp, 100, buf); /* dump 100 bytes from first chunk */ + buf_pullup(buf, 16000, 0); /* Way too much. */ + assert_buf_ok(buf); + buf_get_first_chunk_data(buf, &cp, &sz); + tt_ptr_op(cp, !=, NULL); + tt_int_op(sz, ==, 7900); + test_memeq(cp, stuff+100, 7900); + + buf_free(buf); + buf = NULL; + + buf_shrink_freelists(1); + + tt_int_op(buf_get_total_allocation(), ==, 0); + done: + buf_free(buf); + buf_shrink_freelists(1); + tor_free(stuff); + tor_free(tmp); +} + static void test_buffer_copy(void *arg) { @@ -257,6 +370,7 @@ test_buffer_copy(void *arg) generic_buffer_free(buf); if (buf2) generic_buffer_free(buf2); + buf_shrink_freelists(1); } static void @@ -331,12 +445,40 @@ test_buffer_ext_or_cmd(void *arg) ext_or_cmd_free(cmd); generic_buffer_free(buf); tor_free(tmp); + buf_shrink_freelists(1); +} + +static void +test_buffer_allocation_tracking(void *arg) +{ + buf_t *buf1 = NULL, *buf2 = NULL; + + (void)arg; + + tt_int_op(buf_get_total_allocation(), ==, 0); + + buf1 = buf_new(); + tt_assert(buf1); + buf2 = buf_new(); + tt_assert(buf2); + + //xXXXXXX buf_add + + tt_int_op(buf_get_total_allocation(), ==, 0); + + done: + buf_free(buf1); + buf_free(buf2); + buf_shrink_freelists(1); } struct testcase_t buffer_tests[] = { - { "basic", test_buffers_basic, 0, NULL, NULL }, - { "copy", test_buffer_copy, 0, NULL, NULL }, - { "ext_or_cmd", test_buffer_ext_or_cmd, 0, NULL, NULL }, + { "basic", test_buffers_basic, TT_FORK, NULL, NULL }, + { "copy", test_buffer_copy, TT_FORK, NULL, NULL }, + { "pullup", test_buffer_pullup, TT_FORK, NULL, NULL }, + { "ext_or_cmd", test_buffer_ext_or_cmd, TT_FORK, NULL, NULL }, + { "allocation_tracking", test_buffer_allocation_tracking, TT_FORK, + NULL, NULL }, END_OF_TESTCASES };

1 0

[tor/master] Debugging code inbuffers.c for debugging chunk allocation.
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit eb6f433bdbd6cf44e1f35272ed04a6c0e14f3c2d Author: Nick Mathewson <nickm(a)torproject.org> Date: Fri Jan 3 13:56:46 2014 -0500 Debugging code inbuffers.c for debugging chunk allocation. Currently on; will disable later in this branch. --- src/or/buffers.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) diff --git a/src/or/buffers.c b/src/or/buffers.c index 50b1d9b..c084075 100644 --- a/src/or/buffers.c +++ b/src/or/buffers.c @@ -62,6 +62,8 @@ static int parse_socks_client(const uint8_t *data, size_t datalen, int state, char **reason, ssize_t *drain_out); +#define DEBUG_CHUNK_ALLOC + /* Chunk manipulation functions */ /** A single chunk on a buffer or in a freelist. */ @@ -69,6 +71,9 @@ typedef struct chunk_t { struct chunk_t *next; /**< The next chunk on the buffer or freelist. */ 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 in truncated ms since epoch * when this chunk was inserted. */ @@ -179,6 +184,9 @@ chunk_free_unchecked(chunk_t *chunk) } else { if (freelist) ++freelist->n_free; +#ifdef DEBUG_CHUNK_ALLOC + tor_assert(alloc == chunk->DBG_alloc); +#endif tor_assert(total_bytes_allocated_in_chunks >= alloc); total_bytes_allocated_in_chunks -= alloc; tor_free(chunk); @@ -207,6 +215,9 @@ chunk_new_with_alloc_size(size_t alloc) else ++n_freelist_miss; ch = tor_malloc(alloc); +#ifdef DEBUG_CHUNK_ALLOC + ch->DBG_alloc = alloc; +#endif total_bytes_allocated_in_chunks += alloc; } ch->next = NULL; @@ -221,6 +232,9 @@ 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); @@ -232,6 +246,9 @@ chunk_new_with_alloc_size(size_t alloc) 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]; @@ -251,6 +268,10 @@ chunk_grow(chunk_t *chunk, size_t sz) chunk = tor_realloc(chunk, CHUNK_ALLOC_SIZE(sz)); chunk->memlen = sz; chunk->data = chunk->mem + offset; +#ifdef DEBUG_CHUNK_ALLOC + tor_assert(chunk->DBG_alloc == CHUNK_ALLOC_SIZE(memlen_orig)); + chunk->DBG_alloc = CHUNK_ALLOC_SIZE(sz); +#endif total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(sz) - CHUNK_ALLOC_SIZE(memlen_orig); return chunk; } @@ -315,6 +336,9 @@ buf_shrink_freelists(int free_all) *chp = NULL; while (chunk) { chunk_t *next = chunk->next; +#ifdef DEBUG_CHUNK_ALLOC + tor_assert(chunk->DBG_alloc == CHUNK_ALLOC_SIZE(chunk->memlen)); +#endif tor_assert(total_bytes_allocated_in_chunks >= CHUNK_ALLOC_SIZE(chunk->memlen)); total_bytes_allocated_in_chunks -= CHUNK_ALLOC_SIZE(chunk->memlen); total_freed += CHUNK_ALLOC_SIZE(chunk->memlen); @@ -588,6 +612,9 @@ 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;

1 0

[tor/master] Several tests for buffer allocation
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit d379fc6e0ffce916753e5ef1ac0783703d150fa5 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Jan 5 22:27:37 2014 -0500 Several tests for buffer allocation --- src/test/test_buffers.c | 46 +++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 45 insertions(+), 1 deletion(-) diff --git a/src/test/test_buffers.c b/src/test/test_buffers.c index bd958b6..ab1e5df 100644 --- a/src/test/test_buffers.c +++ b/src/test/test_buffers.c @@ -451,10 +451,13 @@ test_buffer_ext_or_cmd(void *arg) static void test_buffer_allocation_tracking(void *arg) { + char *junk = tor_malloc(16384); buf_t *buf1 = NULL, *buf2 = NULL; + int i; (void)arg; + crypto_rand(junk, 16384); tt_int_op(buf_get_total_allocation(), ==, 0); buf1 = buf_new(); @@ -462,8 +465,49 @@ test_buffer_allocation_tracking(void *arg) buf2 = buf_new(); tt_assert(buf2); - //xXXXXXX buf_add + tt_int_op(buf_allocation(buf1), ==, 0); + tt_int_op(buf_get_total_allocation(), ==, 0); + + write_to_buf(junk, 4000, buf1); + write_to_buf(junk, 4000, buf1); + write_to_buf(junk, 4000, buf1); + write_to_buf(junk, 4000, buf1); + tt_int_op(buf_allocation(buf1), ==, 16384); + fetch_from_buf(junk, 100, buf1); + tt_int_op(buf_allocation(buf1), ==, 16384); /* still 4 4k chunks */ + + tt_int_op(buf_get_total_allocation(), ==, 16384); + + fetch_from_buf(junk, 4096, buf1); /* drop a 1k chunk... */ + tt_int_op(buf_allocation(buf1), ==, 3*4096); /* now 3 4k chunks */ + + tt_int_op(buf_get_total_allocation(), ==, 16384); /* that chunk went onto + the freelist. */ + + write_to_buf(junk, 4000, buf2); + tt_int_op(buf_allocation(buf2), ==, 4096); /* another 4k chunk. */ + tt_int_op(buf_get_total_allocation(), ==, 16384); /* that chunk came from + the freelist. */ + write_to_buf(junk, 4000, buf2); + tt_int_op(buf_allocation(buf2), ==, 8192); /* another 4k chunk. */ + tt_int_op(buf_get_total_allocation(), ==, 5*4096); /* that chunk was new. */ + + /* Make a really huge buffer */ + for (i = 0; i < 1000; ++i) { + write_to_buf(junk, 4000, buf2); + } + tt_int_op(buf_allocation(buf2), >=, 4008000); + tt_int_op(buf_get_total_allocation(), >=, 4008000); + buf_free(buf2); + buf2 = NULL; + + tt_int_op(buf_get_total_allocation(), <, 4008000); + buf_shrink_freelists(1); + tt_int_op(buf_get_total_allocation(), ==, buf_allocation(buf1)); + buf_free(buf1); + buf1 = NULL; + buf_shrink_freelists(1); tt_int_op(buf_get_total_allocation(), ==, 0); done:

1 0

[tor/master] Refactor OOM-handling functions for more testability
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit 9a07ec751ff73062b958a8fc9f8437bed72e144c Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Jan 13 09:52:07 2014 -0500 Refactor OOM-handling functions for more testability This patch splits out some of the functions in OOM handling so that it's easier to check them without involving the rest of Tor or requiring that the circuits be "wired up". --- src/or/circuitlist.c | 6 +++--- src/or/circuitlist.h | 4 ++-- src/or/relay.c | 11 +++++++++-- src/or/relay.h | 2 ++ 4 files changed, 16 insertions(+), 7 deletions(-) diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index eb65230..618a42e 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -1435,9 +1435,9 @@ circuit_mark_all_dirty_circs_as_unusable(void) * - If circ->rend_splice is set (we are the midpoint of a joined * rendezvous stream), then mark the other circuit to close as well. */ -void -circuit_mark_for_close_(circuit_t *circ, int reason, int line, - const char *file) +MOCK_IMPL(void, +circuit_mark_for_close_, (circuit_t *circ, int reason, int line, + const char *file)) { int orig_reason = reason; /* Passed to the controller */ assert_circuit_ok(circ); diff --git a/src/or/circuitlist.h b/src/or/circuitlist.h index 1c8cf7d..a6340c1 100644 --- a/src/or/circuitlist.h +++ b/src/or/circuitlist.h @@ -53,8 +53,8 @@ origin_circuit_t *circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info, int flags); void circuit_mark_all_unused_circs(void); void circuit_mark_all_dirty_circs_as_unusable(void); -void circuit_mark_for_close_(circuit_t *circ, int reason, - int line, const char *file); +MOCK_DECL(void, circuit_mark_for_close_, (circuit_t *circ, int reason, + int line, const char *file)); int circuit_get_cpath_len(origin_circuit_t *circ); void circuit_clear_cpath(origin_circuit_t *circ); crypt_path_t *circuit_get_cpath_hop(origin_circuit_t *circ, int hopnum); diff --git a/src/or/relay.c b/src/or/relay.c index 041a9e8..dbc1710 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -2199,12 +2199,19 @@ packed_cell_mem_cost(void) return sizeof(packed_cell_t) + MP_POOL_ITEM_OVERHEAD; } +/** DOCDOC */ +STATIC size_t +cell_queues_get_total_allocation(void) +{ + return total_cells_allocated * packed_cell_mem_cost(); +} + /** Check whether we've got too much space used for cells. If so, * call the OOM handler and return 1. Otherwise, return 0. */ -static int +STATIC int cell_queues_check_size(void) { - size_t alloc = total_cells_allocated * packed_cell_mem_cost(); + size_t alloc = cell_queues_get_total_allocation(); alloc += buf_get_total_allocation(); if (alloc >= get_options()->MaxMemInQueues) { circuits_handle_oom(alloc); diff --git a/src/or/relay.h b/src/or/relay.h index 20eecfb..2c7d0d8 100644 --- a/src/or/relay.h +++ b/src/or/relay.h @@ -85,6 +85,8 @@ STATIC int connected_cell_parse(const relay_header_t *rh, const cell_t *cell, tor_addr_t *addr_out, int *ttl_out); STATIC packed_cell_t *packed_cell_new(void); STATIC packed_cell_t *cell_queue_pop(cell_queue_t *queue); +STATIC size_t cell_queues_get_total_allocation(void); +STATIC int cell_queues_check_size(void); #endif #endif

1 0

[tor/master] Initial unit tests for OOM handling
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit 48877e24a880be41e4dad50f5ebb6e0671e9f92f Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Jan 13 14:15:33 2014 -0500 Initial unit tests for OOM handling --- src/test/include.am | 1 + src/test/test.c | 2 + src/test/test_oom.c | 199 +++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 202 insertions(+) diff --git a/src/test/include.am b/src/test/include.am index 5f978b5..b2db659 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -32,6 +32,7 @@ src_test_test_SOURCES = \ src/test/test_introduce.c \ src/test/test_logging.c \ src/test/test_microdesc.c \ + src/test/test_oom.c \ src/test/test_options.c \ src/test/test_pt.c \ src/test/test_replay.c \ diff --git a/src/test/test.c b/src/test/test.c index 522f2af..47ca8e3 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -1627,6 +1627,7 @@ extern struct testcase_t logging_tests[]; extern struct testcase_t backtrace_tests[]; extern struct testcase_t hs_tests[]; extern struct testcase_t nodelist_tests[]; +extern struct testcase_t oom_tests[]; static struct testgroup_t testgroups[] = { { "", test_array }, @@ -1652,6 +1653,7 @@ static struct testgroup_t testgroups[] = { { "control/", controller_event_tests }, { "hs/", hs_tests }, { "nodelist/", nodelist_tests }, + { "oom/", oom_tests }, END_OF_GROUPS }; diff --git a/src/test/test_oom.c b/src/test/test_oom.c new file mode 100644 index 0000000..3b636e6 --- /dev/null +++ b/src/test/test_oom.c @@ -0,0 +1,199 @@ +/* Copyright (c) 2014, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/* Unit tests for OOM handling logic */ + +#define RELAY_PRIVATE +#define BUFFERS_PRIVATE +#define CIRCUITLIST_PRIVATE +#include "or.h" +#include "buffers.h" +#include "circuitlist.h" +#include "compat_libevent.h" +#include "connection.h" +#include "config.h" +#include "mempool.h" +#include "relay.h" +#include "test.h" + +/* small replacement mock for circuit_mark_for_close_ to avoid doing all + * the other bookkeeping that comes with marking circuits. */ +static void +circuit_mark_for_close_dummy_(circuit_t *circ, int reason, int line, + const char *file) +{ + (void) reason; + if (circ->marked_for_close) { + TT_FAIL(("Circuit already marked for close at %s:%d, but we are marking " + "it again at %s:%d", + circ->marked_for_close_file, (int)circ->marked_for_close, + file, line)); + } + + circ->marked_for_close = line; + circ->marked_for_close_file = file; +} + +static circuit_t * +dummy_or_circuit_new(int n_p_cells, int n_n_cells) +{ + or_circuit_t *circ = or_circuit_new(0, NULL); + int i; + cell_t cell; + + for (i=0; i < n_p_cells; ++i) { + crypto_rand((void*)&cell, sizeof(cell)); + cell_queue_append_packed_copy(TO_CIRCUIT(circ), &circ->p_chan_cells, + 0, &cell, 1, 0); + } + + for (i=0; i < n_n_cells; ++i) { + crypto_rand((void*)&cell, sizeof(cell)); + cell_queue_append_packed_copy(TO_CIRCUIT(circ), + &TO_CIRCUIT(circ)->n_chan_cells, + 1, &cell, 1, 0); + } + + TO_CIRCUIT(circ)->purpose = CIRCUIT_PURPOSE_OR; + return TO_CIRCUIT(circ); +} + +static circuit_t * +dummy_origin_circuit_new(int n_cells) +{ + origin_circuit_t *circ = origin_circuit_new(); + int i; + cell_t cell; + + for (i=0; i < n_cells; ++i) { + crypto_rand((void*)&cell, sizeof(cell)); + cell_queue_append_packed_copy(TO_CIRCUIT(circ), + &TO_CIRCUIT(circ)->n_chan_cells, + 1, &cell, 1, 0); + } + + TO_CIRCUIT(circ)->purpose = CIRCUIT_PURPOSE_C_GENERAL; + return TO_CIRCUIT(circ); +} + +#if 0 +static void +add_bytes_to_buf(generic_buffer_t *buf, size_t n_bytes) +{ + char b[3000]; + + while (n_bytes) { + size_t this_add = n_bytes > sizeof(buf) ? sizeof(buf) : n_bytes; + crypto_rand(b, sizeof(b)); + generic_buffer_add(buf, b, this_add); + n_bytes -= this_add; + } +} + +static edge_connection_t * +dummy_edge_conn_new(int type, size_t in_bytes, size_t out_bytes) +{ + edge_connection_t *conn = edge_connection_new(type, AF_INET); + + /* We add these bytes directly to the buffers, to avoid all the + * edge connection read/write machinery. */ + add_bytes_to_buf(TO_CONN(conn)->inbuf, in_bytes); + add_bytes_to_buf(TO_CONN(conn)->outbuf, out_bytes); + + return conn; +} +#endif + +/** Run unit tests for buffers.c */ +static void +test_oom_circbuf(void *arg) +{ + or_options_t *options = get_options_mutable(); + circuit_t *c1 = NULL, *c2 = NULL, *c3 = NULL, *c4 = NULL; + struct timeval tv = { 1389631048, 0 }; + + (void) arg; + + MOCK(circuit_mark_for_close_, circuit_mark_for_close_dummy_); + init_cell_pool(); + + /* Far too low for real life. */ + options->MaxMemInQueues = 256*packed_cell_mem_cost(); + options->CellStatistics = 0; + + tt_int_op(cell_queues_check_size(), ==, 0); /* We don't start out OOM. */ + tt_int_op(cell_queues_get_total_allocation(), ==, 0); + tt_int_op(buf_get_total_allocation(), ==, 0); + + /* Now we're going to fake up some circuits and get them added to the global + circuit list. */ + tv.tv_usec = 0; + tor_gettimeofday_cache_set(&tv); + c1 = dummy_origin_circuit_new(30); + tv.tv_usec = 10*1000; + tor_gettimeofday_cache_set(&tv); + c2 = dummy_or_circuit_new(20, 20); + + tt_int_op(packed_cell_mem_cost(), ==, + sizeof(packed_cell_t) + MP_POOL_ITEM_OVERHEAD); + tt_int_op(cell_queues_get_total_allocation(), ==, + packed_cell_mem_cost() * 70); + tt_int_op(cell_queues_check_size(), ==, 0); /* We are still not OOM */ + + tv.tv_usec = 20*1000; + tor_gettimeofday_cache_set(&tv); + c3 = dummy_or_circuit_new(100, 85); + tt_int_op(cell_queues_check_size(), ==, 0); /* We are still not OOM */ + tt_int_op(cell_queues_get_total_allocation(), ==, + packed_cell_mem_cost() * 255); + + tv.tv_usec = 30*1000; + tor_gettimeofday_cache_set(&tv); + /* Adding this cell will trigger our OOM handler. */ + c4 = dummy_or_circuit_new(2, 0); + + tt_int_op(cell_queues_get_total_allocation(), ==, + packed_cell_mem_cost() * 257); + + tt_int_op(cell_queues_check_size(), ==, 1); /* We are now OOM */ + + tt_assert(c1->marked_for_close); + tt_assert(! c2->marked_for_close); + tt_assert(! c3->marked_for_close); + tt_assert(! c4->marked_for_close); + + tt_int_op(cell_queues_get_total_allocation(), ==, + packed_cell_mem_cost() * (257 - 30)); + + circuit_free(c1); + tv.tv_usec = 0; + tor_gettimeofday_cache_set(&tv); /* go back in time */ + c1 = dummy_or_circuit_new(90, 0); + + tv.tv_usec = 40*1000; /* go back to the future */ + tor_gettimeofday_cache_set(&tv); + + tt_int_op(cell_queues_check_size(), ==, 1); /* We are now OOM */ + + tt_assert(c1->marked_for_close); + tt_assert(! c2->marked_for_close); + tt_assert(! c3->marked_for_close); + tt_assert(! c4->marked_for_close); + + tt_int_op(cell_queues_get_total_allocation(), ==, + packed_cell_mem_cost() * (257 - 30)); + + done: + circuit_free(c1); + circuit_free(c2); + circuit_free(c3); + circuit_free(c4); + + UNMOCK(circuit_mark_for_close_); +} + +struct testcase_t oom_tests[] = { + { "circbuf", test_oom_circbuf, TT_FORK, NULL, NULL }, + END_OF_TESTCASES +}; +

1 0

[tor/master] Merge branch 'bug10169_025_v2'
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit ab225aaf28d7a25a58b5f11f1c59ded80570b594 Merge: bfa0e02 bb37544 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 4 11:03:30 2014 -0500 Merge branch 'bug10169_025_v2' Conflicts: src/test/test.c changes/bug10169 | 4 + changes/bug9686 | 3 + doc/tor.1.txt | 10 +- src/common/compat_libevent.c | 44 +++++- src/common/compat_libevent.h | 4 + src/or/buffers.c | 109 ++++++++++++- src/or/buffers.h | 8 +- src/or/circuitlist.c | 167 ++++++++++++++++---- src/or/circuitlist.h | 7 +- src/or/config.c | 9 +- src/or/or.h | 8 +- src/or/relay.c | 17 ++- src/or/relay.h | 2 + src/test/include.am | 1 + src/test/test.c | 2 + src/test/test_buffers.c | 265 +++++++++++++++++++++++++++++++- src/test/test_oom.c | 348 ++++++++++++++++++++++++++++++++++++++++++ 17 files changed, 946 insertions(+), 62 deletions(-) diff --cc src/test/test.c index 2529e29,47ca8e3..9ca3f29 --- a/src/test/test.c +++ b/src/test/test.c @@@ -1629,7 -1627,7 +1629,8 @@@ extern struct testcase_t logging_tests[ extern struct testcase_t backtrace_tests[]; extern struct testcase_t hs_tests[]; extern struct testcase_t nodelist_tests[]; +extern struct testcase_t routerkeys_tests[]; + extern struct testcase_t oom_tests[]; static struct testgroup_t testgroups[] = { { "", test_array }, @@@ -1655,7 -1653,7 +1656,8 @@@ { "control/", controller_event_tests }, { "hs/", hs_tests }, { "nodelist/", nodelist_tests }, + { "routerkeys/", routerkeys_tests }, + { "oom/", oom_tests }, END_OF_GROUPS };

1 0

[tor/master] Monotonize the OOM-killer data timers
by nickm＠torproject.org 04 Mar '14

04 Mar '14

commit 833d027778ba97020fb5ded1d94e4b21fbcab766 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 26 09:51:30 2014 -0500 Monotonize the OOM-killer data timers In a couple of places, to implement the OOM-circuit-killer defense against sniper attacks, we have counters to remember the age of cells or data chunks. These timers were based on wall clock time, which can move backwards, thus giving roll-over results for our age calculation. This commit creates a low-budget monotonic time, based on ratcheting gettimeofday(), so that even in the event of a time rollback, we don't do anything _really_ stupid. A future version of Tor should update this function to do something even less stupid here, like employ clock_gettime() or its kin. --- src/common/compat_libevent.c | 30 ++++++++++++++++++++++++++++++ src/common/compat_libevent.h | 1 + src/or/buffers.c | 2 +- src/or/circuitlist.c | 2 +- src/or/relay.c | 2 +- 5 files changed, 34 insertions(+), 3 deletions(-) diff --git a/src/common/compat_libevent.c b/src/common/compat_libevent.c index 6655ca8..77f8495 100644 --- a/src/common/compat_libevent.c +++ b/src/common/compat_libevent.c @@ -724,3 +724,33 @@ tor_gettimeofday_cache_clear(void) } #endif +/** + * As tor_gettimeofday_cached, but can never move backwards in time. + * + * The returned value may diverge from wall-clock time, since wall-clock time + * can trivially be adjusted backwards, and this can't. Don't mix wall-clock + * time with these values in the same calculation. + * + * Depending on implementation, this function may or may not "smooth out" huge + * jumps forward in wall-clock time. It may or may not keep its results + * advancing forward (as opposed to stalling) if the wall-clock time goes + * backwards. The current implementation does neither of of these. + * + * This function is not thread-safe; do not call it outside the main thread. + * + * In future versions of Tor, this may return a time does not have its + * origin at the Unix epoch. + */ +void +tor_gettimeofday_cached_monotonic(struct timeval *tv) +{ + struct timeval last_tv = { 0, 0 }; + + tor_gettimeofday_cached(tv); + if (timercmp(tv, &last_tv, <)) { + memcpy(tv, &last_tv, sizeof(struct timeval)); + } else { + memcpy(&last_tv, tv, sizeof(struct timeval)); + } +} + diff --git a/src/common/compat_libevent.h b/src/common/compat_libevent.h index 56285ef..3190f13 100644 --- a/src/common/compat_libevent.h +++ b/src/common/compat_libevent.h @@ -90,6 +90,7 @@ int tor_add_bufferevent_to_rate_limit_group(struct bufferevent *bev, void tor_gettimeofday_cached(struct timeval *tv); void tor_gettimeofday_cache_clear(void); +void tor_gettimeofday_cached_monotonic(struct timeval *tv); #endif diff --git a/src/or/buffers.c b/src/or/buffers.c index 352e60a..b16ee6e 100644 --- a/src/or/buffers.c +++ b/src/or/buffers.c @@ -632,7 +632,7 @@ buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped) chunk = chunk_new_with_alloc_size(preferred_chunk_size(capacity)); } - tor_gettimeofday_cached(&now); + tor_gettimeofday_cached_monotonic(&now); chunk->inserted_time = (uint32_t)tv_to_msec(&now); if (buf->tail) { diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index 45fc95b..0534e35 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -1551,7 +1551,7 @@ circuits_handle_oom(size_t current_allocation) mem_to_recover = current_allocation - mem_target; } - tor_gettimeofday_cached(&now); + tor_gettimeofday_cached_monotonic(&now); now_ms = (uint32_t)tv_to_msec(&now); /* This algorithm itself assumes that you've got enough memory slack diff --git a/src/or/relay.c b/src/or/relay.c index e6d0f50..4cbc8fa 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -1906,7 +1906,7 @@ cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell) { struct timeval now; packed_cell_t *copy = packed_cell_copy(cell); - tor_gettimeofday_cached(&now); + tor_gettimeofday_cached_monotonic(&now); copy->inserted_time = (uint32_t)tv_to_msec(&now); /* Remember the time when this cell was put in the queue. */

1 0