commit beb3a5fe1526d58b92596fec235c4c41e2698850
parent b628ffeb6234c58d0921756b9a34ac601870f09a
Author: David Goulet <dgoulet@torproject.org>
Date: Wed, 18 Dec 2024 11:04:00 -0500
hs: Use downloaded counter for HSDir OOM cache cleanup
The OOM cache cleanup is now done by looking at the downloaded counter. The
cleanup process start at 0 and increment it to the next lowest value until
enough bytes have been removed.
This process could be expensive for large amount of descriptors in the cache
but since it is very expensive to increment counters, most cleanup should
happen within a tight range of downloaded counter target.
Fixes #40996
Signed-off-by: David Goulet <dgoulet@torproject.org>
Diffstat:
4 files changed, 85 insertions(+), 34 deletions(-)
diff --git a/src/core/or/relay.c b/src/core/or/relay.c
@@ -2941,7 +2941,7 @@ cell_queues_check_size(void)
if (hs_cache_total > get_options()->MaxMemInQueues / 5) {
const size_t bytes_to_remove =
hs_cache_total - (size_t)(get_options()->MaxMemInQueues / 10);
- removed = hs_cache_handle_oom(now, bytes_to_remove);
+ removed = hs_cache_handle_oom(bytes_to_remove);
oom_stats_n_bytes_removed_hsdir += removed;
alloc -= removed;
}
diff --git a/src/feature/hs/hs_cache.c b/src/feature/hs/hs_cache.c
@@ -224,6 +224,71 @@ cache_lookup_v3_as_dir(const char *query, const char **desc_out)
return -1;
}
+/** Clean the v3 cache by removing entries that are below or equal the
+ * downloaded target.
+ *
+ * Stop when the max_remove_bytes is reached. It is possible that more bytes
+ * are removed if max_remove_bytes is not aligned on cache entry size.
+ *
+ * Return the amount of bytes freed. The next_lowest param is set to the
+ * lowest n_downloaded value in the cache that is above target.
+ *
+ * If both next_lowest and returned value are 0, the cache is empty. */
+STATIC size_t
+cache_clean_v3_by_downloaded_as_dir(const uint64_t target,
+ const size_t max_remove_bytes,
+ uint64_t *next_lowest)
+{
+ size_t bytes_removed = 0;
+ uint64_t lowest = 0;
+
+ if (!hs_cache_v3_dir) { /* No cache to clean. Just return. */
+ goto end;
+ }
+
+ log_info(LD_REND, "Cleaning HS cache for downloaded target of %" PRIu64
+ ". Maximum bytes to removed: %zu",
+ target, max_remove_bytes);
+
+ DIGEST256MAP_FOREACH_MODIFY(hs_cache_v3_dir, key,
+ hs_cache_dir_descriptor_t *, entry) {
+ /* Downloaded counter is above target, ignore. Record next lowest. */
+ if (entry->n_downloaded > target) {
+ if (lowest == 0 || lowest > entry->n_downloaded) {
+ lowest = entry->n_downloaded;
+ }
+ continue;
+ }
+ /* We have removed enough, avoid cleaning this entry. Reason we continue
+ * the loop is so we can find the next lowest value. Yes, with many
+ * entries, this could be expensive but this is only called during OOM
+ * cleanup which should be fairly rare. */
+ if (bytes_removed >= max_remove_bytes) {
+ continue;
+ }
+ size_t entry_size = cache_get_dir_entry_size(entry);
+ /* Logging. */
+ {
+ char key_b64[BASE64_DIGEST256_LEN + 1];
+ digest256_to_base64(key_b64, (const char *) key);
+ log_info(LD_REND, "Removing v3 descriptor '%s' from HSDir cache. "
+ "Downloaded %" PRIu64 " times and size of %zu bytes",
+ safe_str_client(key_b64), entry->n_downloaded, entry_size);
+ }
+ /* Remove it from our cache. */
+ MAP_DEL_CURRENT(key);
+ bytes_removed += entry_size;
+ /* Entry is not in the cache anymore, destroy it. */
+ cache_dir_desc_free(entry);
+ /* Update our cache entry allocation size for the OOM. */
+ hs_cache_decrement_allocation(entry_size);
+ } DIGEST256MAP_FOREACH_END;
+
+ end:
+ *next_lowest = lowest;
+ return bytes_removed;
+}
+
/** Clean the v3 cache by removing any entry that has expired using the
* <b>global_cutoff</b> value. If <b>global_cutoff</b> is 0, the cleaning
* process will use the lifetime found in the plaintext data section. Return
@@ -1087,45 +1152,28 @@ hs_cache_client_new_auth_parse(const ed25519_public_key_t *service_pk)
* min_remove_bytes if the caches get emptied out so the caller should be
* aware of this. */
size_t
-hs_cache_handle_oom(time_t now, size_t min_remove_bytes)
+hs_cache_handle_oom(size_t min_remove_bytes)
{
- time_t k;
size_t bytes_removed = 0;
+ /* The downloaded counter value to remove. Start at 0 and increment to the
+ * next lowest value in the cache. */
+ uint64_t target = 0;
/* Our OOM handler called with 0 bytes to remove is a code flow error. */
tor_assert(min_remove_bytes != 0);
- /* The algorithm is as follow. K is the oldest expected descriptor age.
- *
- * 1) Deallocate all entries from v3 cache that are older than K hours
- * 2.1) If the amount of remove bytes has been reached, stop.
- * 2) Set K = K - 1 hour and repeat process until K is < 0.
- *
- * This ends up being O(Kn).
- */
-
- /* Set K to the oldest expected age in seconds which is the maximum
- * lifetime of a cache entry. */
- k = hs_cache_max_entry_lifetime();
-
+ /* Loop until we have an empty cache or we have removed enough bytes. */
do {
- time_t cutoff;
-
- /* If K becomes negative, it means we've empty the caches so stop and
- * return what we were able to cleanup. */
- if (k < 0) {
+ /* This is valid due to the loop condition. At the start, min_remove_bytes
+ * can't be 0. */
+ size_t bytes_to_free = (min_remove_bytes - bytes_removed);
+ size_t bytes_freed =
+ cache_clean_v3_by_downloaded_as_dir(target, bytes_to_free, &target);
+ if (bytes_freed == 0 && target == 0) {
+ /* Indicate that the cache is empty. */
break;
}
- /* Compute a cutoff value with K and the current time. */
- cutoff = now - k;
-
- if (bytes_removed < min_remove_bytes) {
- /* We haven't remove enough bytes so clean v3 cache. */
- bytes_removed += cache_clean_v3_as_dir(now, cutoff);
- /* Decrement K by a post period to shorten the cutoff, Two minutes
- * if we are a testing network, or one hour otherwise. */
- k -= get_options()->TestingTorNetwork ? 120 : 3600;
- }
+ bytes_removed += bytes_freed;
} while (bytes_removed < min_remove_bytes);
return bytes_removed;
diff --git a/src/feature/hs/hs_cache.h b/src/feature/hs/hs_cache.h
@@ -87,7 +87,7 @@ hs_cache_max_entry_lifetime(void)
void hs_cache_init(void);
void hs_cache_free_all(void);
void hs_cache_clean_as_dir(time_t now);
-size_t hs_cache_handle_oom(time_t now, size_t min_remove_bytes);
+size_t hs_cache_handle_oom(size_t min_remove_bytes);
unsigned int hs_cache_get_max_descriptor_size(void);
@@ -150,6 +150,9 @@ typedef struct hs_cache_client_descriptor_t {
} hs_cache_client_descriptor_t;
STATIC size_t cache_clean_v3_as_dir(time_t now, time_t global_cutoff);
+STATIC size_t cache_clean_v3_by_downloaded_as_dir(const uint64_t target,
+ const size_t min_remove_bytes,
+ uint64_t *next_lowest);
STATIC hs_cache_client_descriptor_t *
lookup_v3_desc_as_client(const uint8_t *key);
diff --git a/src/test/test_hs_cache.c b/src/test/test_hs_cache.c
@@ -90,7 +90,7 @@ test_directory(void *arg)
tt_str_op(desc_out, OP_EQ, desc1_str);
/* Tell our OOM to run and to at least remove a byte which will result in
* removing the descriptor from our cache. */
- oom_size = hs_cache_handle_oom(time(NULL), 1);
+ oom_size = hs_cache_handle_oom(1);
tt_int_op(oom_size, OP_GE, 1);
ret = hs_cache_lookup_as_dir(3, helper_get_hsdir_query(desc1), NULL);
tt_int_op(ret, OP_EQ, 0);
@@ -127,7 +127,7 @@ test_directory(void *arg)
NULL);
tt_int_op(ret, OP_EQ, 0);
/* Cleanup our entire cache. */
- oom_size = hs_cache_handle_oom(time(NULL), 1);
+ oom_size = hs_cache_handle_oom(1);
tt_int_op(oom_size, OP_GE, 1);
hs_descriptor_free(desc_zero_lifetime);
tor_free(desc_zero_lifetime_str);
