commit 3033ba9f5ec8eb4dea3e6778f6d7546cacf7ae57 Author: Nick Mathewson <nickm@torproject.org> Date: Sun Jan 4 20:05:29 2015 -0500 When OOM, free cached hidden service descriptors too. --- changes/bug13806 | 8 ++++ src/or/main.c | 2 +- src/or/or.h | 2 + src/or/relay.c | 12 +++++ src/or/rendcommon.c | 121 ++++++++++++++++++++++++++++++++++++++++++--------- src/or/rendcommon.h | 4 +- 6 files changed, 126 insertions(+), 23 deletions(-) diff --git a/changes/bug13806 b/changes/bug13806 new file mode 100644 index 0000000..0a6b268 --- /dev/null +++ b/changes/bug13806 @@ -0,0 +1,8 @@ + o Minor features (DOS resistance): + - Count the total number of bytes used storing hidden service descriptors + against the value of MaxMemInQueues. If we're low on memory, and more + than 20% of our memory is used holding hidden service descriptors, free + them until no more than 10% of our memory holds hidden service + descriptors. Free the least recently fetched descriptors first. + Resolves ticket 13806. + diff --git a/src/or/main.c b/src/or/main.c index 58e3ad3..3ee9644 100644 --- a/src/or/main.c +++ b/src/or/main.c @@ -1437,7 +1437,7 @@ run_scheduled_events(time_t now) if (time_to_clean_caches < now) { rep_history_clean(now - options->RephistTrackTime); rend_cache_clean(now); - rend_cache_clean_v2_descs_as_dir(now); + rend_cache_clean_v2_descs_as_dir(now, 0); microdesc_cache_rebuild(NULL, 0); #define CLEAN_CACHES_INTERVAL (30*60) time_to_clean_caches = now + CLEAN_CACHES_INTERVAL; diff --git a/src/or/or.h b/src/or/or.h index ee86697..d978719 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -4939,6 +4939,8 @@ typedef struct rend_service_descriptor_t { typedef struct rend_cache_entry_t { size_t len; /**< Length of <b>desc</b> */ time_t received; /**< When was the descriptor received? */ + time_t last_served; /**< When did we last write this one to somebody? + * (HSDir only) */ char *desc; /**< Service descriptor */ rend_service_descriptor_t *parsed; /**< Parsed value of 'desc' */ } rend_cache_entry_t; diff --git a/src/or/relay.c b/src/or/relay.c index b95e584..50070b7 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -2441,7 +2441,19 @@ cell_queues_check_size(void) size_t alloc = cell_queues_get_total_allocation(); alloc += buf_get_total_allocation(); alloc += tor_zlib_get_total_allocation(); + const size_t rend_cache_total = rend_cache_get_total_allocation(); + alloc += rend_cache_total; if (alloc >= get_options()->MaxMemInQueues) { + /* If we're spending over 20% of the memory limit on hidden service + * descriptors, free them until we're down to 10%. + */ + if (rend_cache_total > get_options()->MaxMemInQueues / 5) { + const size_t bytes_to_remove = + rend_cache_total - (get_options()->MaxMemInQueues / 10); + rend_cache_clean_v2_descs_as_dir(time(NULL), bytes_to_remove); + alloc -= rend_cache_total; + alloc += rend_cache_get_total_allocation(); + } circuits_handle_oom(alloc); return 1; } diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c index e779ecf..d85e323 100644 --- a/src/or/rendcommon.c +++ b/src/or/rendcommon.c @@ -704,6 +704,9 @@ static strmap_t *rend_cache = NULL; * directories. */ static digestmap_t *rend_cache_v2_dir = NULL; +/** DOCDOC */ +static size_t rend_cache_total_allocation = 0; + /** Initializes the service descriptor cache. */ void @@ -713,12 +716,64 @@ rend_cache_init(void) rend_cache_v2_dir = digestmap_new(); } +/** Return the approximate number of bytes needed to hold <b>e</b>. */ +static size_t +rend_cache_entry_allocation(const rend_cache_entry_t *e) +{ + if (!e) + return 0; + + /* This doesn't count intro_nodes or key size */ + return sizeof(*e) + e->len + sizeof(*e->parsed); +} + +/** DOCDOC */ +size_t +rend_cache_get_total_allocation(void) +{ + return rend_cache_total_allocation; +} + +/** Decrement the total bytes attributed to the rendezvous cache by n. */ +static void +rend_cache_decrement_allocation(size_t n) +{ + static int have_underflowed = 0; + + if (rend_cache_total_allocation >= n) { + rend_cache_total_allocation -= n; + } else { + rend_cache_total_allocation = 0; + if (! have_underflowed) { + have_underflowed = 1; + log_warn(LD_BUG, "Underflow in rend_cache_decrement_allocation"); + } + } +} + +/** Increase the total bytes attributed to the rendezvous cache by n. */ +static void +rend_cache_increment_allocation(size_t n) +{ + static int have_overflowed = 0; + if (rend_cache_total_allocation <= SIZE_MAX - n) { + rend_cache_total_allocation += n; + } else { + rend_cache_total_allocation = SIZE_MAX; + if (! have_overflowed) { + have_overflowed = 1; + log_warn(LD_BUG, "Overflow in rend_cache_increment_allocation"); + } + } +} + /** Helper: free storage held by a single service descriptor cache entry. */ static void rend_cache_entry_free(rend_cache_entry_t *e) { if (!e) return; + rend_cache_decrement_allocation(rend_cache_entry_allocation(e)); rend_service_descriptor_free(e->parsed); tor_free(e->desc); tor_free(e); @@ -740,6 +795,7 @@ rend_cache_free_all(void) digestmap_free(rend_cache_v2_dir, rend_cache_entry_free_); rend_cache = NULL; rend_cache_v2_dir = NULL; + rend_cache_total_allocation = 0; } /** Removes all old entries from the service descriptor cache. @@ -777,31 +833,46 @@ rend_cache_purge(void) } /** Remove all old v2 descriptors and those for which this hidden service - * directory is not responsible for any more. */ + * directory is not responsible for any more. + * + * If at all possible, remove at least <b>force_remove</b> bytes of data. + */ void -rend_cache_clean_v2_descs_as_dir(time_t now) +rend_cache_clean_v2_descs_as_dir(time_t now, size_t force_remove) { digestmap_iter_t *iter; time_t cutoff = now - REND_CACHE_MAX_AGE - REND_CACHE_MAX_SKEW; - for (iter = digestmap_iter_init(rend_cache_v2_dir); - !digestmap_iter_done(iter); ) { - const char *key; - void *val; - rend_cache_entry_t *ent; - digestmap_iter_get(iter, &key, &val); - ent = val; - if (ent->parsed->timestamp < cutoff || - !hid_serv_responsible_for_desc_id(key)) { - char key_base32[REND_DESC_ID_V2_LEN_BASE32 + 1]; - base32_encode(key_base32, sizeof(key_base32), key, DIGEST_LEN); - log_info(LD_REND, "Removing descriptor with ID '%s' from cache", - safe_str_client(key_base32)); - iter = digestmap_iter_next_rmv(rend_cache_v2_dir, iter); - rend_cache_entry_free(ent); - } else { - iter = digestmap_iter_next(rend_cache_v2_dir, iter); + const int LAST_SERVED_CUTOFF_STEP = 1800; + time_t last_served_cutoff = cutoff; + size_t bytes_removed = 0; + do { + for (iter = digestmap_iter_init(rend_cache_v2_dir); + !digestmap_iter_done(iter); ) { + const char *key; + void *val; + rend_cache_entry_t *ent; + digestmap_iter_get(iter, &key, &val); + ent = val; + if (ent->parsed->timestamp < cutoff || + ent->last_served < last_served_cutoff || + !hid_serv_responsible_for_desc_id(key)) { + char key_base32[REND_DESC_ID_V2_LEN_BASE32 + 1]; + base32_encode(key_base32, sizeof(key_base32), key, DIGEST_LEN); + log_info(LD_REND, "Removing descriptor with ID '%s' from cache", + safe_str_client(key_base32)); + bytes_removed += rend_cache_entry_allocation(ent); + iter = digestmap_iter_next_rmv(rend_cache_v2_dir, iter); + rend_cache_entry_free(ent); + } else { + iter = digestmap_iter_next(rend_cache_v2_dir, iter); + } } - } + + /* In case we didn't remove enough bytes, advance the cutoff a little. */ + last_served_cutoff += LAST_SERVED_CUTOFF_STEP; + if (last_served_cutoff > now) + break; + } while (bytes_removed < force_remove); } /** Determines whether <b>a</b> is in the interval of <b>b</b> (excluded) and @@ -903,6 +974,7 @@ rend_cache_lookup_v2_desc_as_dir(const char *desc_id, const char **desc) e = digestmap_get(rend_cache_v2_dir, desc_id_digest); if (e) { *desc = e->desc; + e->last_served = approx_time(); return 1; } return 0; @@ -993,7 +1065,13 @@ rend_cache_store_v2_desc_as_dir(const char *desc) if (!e) { e = tor_malloc_zero(sizeof(rend_cache_entry_t)); digestmap_set(rend_cache_v2_dir, desc_id, e); + /* Treat something just uploaded as having been served a little + * while ago, so that flooding with new descriptors doesn't help + * too much. + */ + e->last_served = approx_time() - 3600; } else { + rend_cache_decrement_allocation(rend_cache_entry_allocation(e)); rend_service_descriptor_free(e->parsed); tor_free(e->desc); } @@ -1001,6 +1079,7 @@ rend_cache_store_v2_desc_as_dir(const char *desc) e->parsed = parsed; e->desc = tor_strndup(current_desc, encoded_size); e->len = encoded_size; + rend_cache_increment_allocation(rend_cache_entry_allocation(e)); log_info(LD_REND, "Successfully stored service descriptor with desc ID " "'%s' and len %d.", safe_str(desc_id_base32), (int)encoded_size); @@ -1189,6 +1268,7 @@ rend_cache_store_v2_desc_as_client(const char *desc, e = tor_malloc_zero(sizeof(rend_cache_entry_t)); strmap_set_lc(rend_cache, key, e); } else { + rend_cache_decrement_allocation(rend_cache_entry_allocation(e)); rend_service_descriptor_free(e->parsed); tor_free(e->desc); } @@ -1197,6 +1277,7 @@ rend_cache_store_v2_desc_as_client(const char *desc, e->desc = tor_malloc_zero(encoded_size + 1); strlcpy(e->desc, desc, encoded_size + 1); e->len = encoded_size; + rend_cache_increment_allocation(rend_cache_entry_allocation(e)); log_debug(LD_REND,"Successfully stored rend desc '%s', len %d.", safe_str_client(service_id), (int)encoded_size); return RCS_OKAY; diff --git a/src/or/rendcommon.h b/src/or/rendcommon.h index 186326a..1d02bb4 100644 --- a/src/or/rendcommon.h +++ b/src/or/rendcommon.h @@ -33,7 +33,7 @@ void rend_intro_point_free(rend_intro_point_t *intro); void rend_cache_init(void); void rend_cache_clean(time_t now); -void rend_cache_clean_v2_descs_as_dir(time_t now); +void rend_cache_clean_v2_descs_as_dir(time_t now, size_t min_to_remove); void rend_cache_purge(void); void rend_cache_free_all(void); int rend_valid_service_id(const char *query); @@ -51,7 +51,6 @@ rend_cache_store_status_t rend_cache_store_v2_desc_as_dir(const char *desc); rend_cache_store_status_t rend_cache_store_v2_desc_as_client(const char *desc, const char *desc_id_base32, const rend_data_t *rend_query); - int rend_encode_v2_descriptors(smartlist_t *descs_out, rend_service_descriptor_t *desc, time_t now, uint8_t period, rend_auth_type_t auth_type, @@ -64,6 +63,7 @@ int rend_id_is_in_interval(const char *a, const char *b, const char *c); void rend_get_descriptor_id_bytes(char *descriptor_id_out, const char *service_id, const char *secret_id_part); +size_t rend_cache_get_total_allocation(void); #endif