From 8f520e52d7d4081a0835374c7a448116baac64ab Mon Sep 17 00:00:00 2001 From: Dirk Engling Date: Mon, 2 Nov 2026 20:39:26 +0100 Subject: Turn the bucket count into a knob, but keep cleaner wake-ups at a constant rate --- DESIGN | 37 ++++++++++++++++++++++++++++++++++++- Makefile | 6 ++++++ ot_clean.c | 40 ++++++++++++++++++++++++---------------- ot_clean.h | 13 +++++++++++-- tests/t_mutex.c | 2 +- trackerlogic.h | 5 +++++ 6 files changed, 83 insertions(+), 20 deletions(-) diff --git a/DESIGN b/DESIGN index ff37706..5abeb4a 100644 --- a/DESIGN +++ b/DESIGN @@ -16,7 +16,7 @@ A connection carries one request and closes. Keep-alive works and is rarely asked for. Statistics are approximate on purpose. Counters are per thread and summed -when read, so a /stats read can under-report once. Nothing drifts. +when read, so a /stats read can under-report once. Decisions @@ -60,9 +60,44 @@ connections, the filter serves more requests than no filter, not fewer, so it is not the denial of service vector that FreeBSD-SA-02:26 once described. +The torrent table is split into 2^OT_BUCKET_COUNT_BITS buckets, 1024 by +default, set from the Makefile. Inserting a torrent opens a slot in a sorted +vector, so the bytes moved grow with the bucket's occupancy. Insert cost per +torrent, Linux: + + 2^10 2^12 2^14 2^16 + 200k 466 ns 439 ns + 1M 834 ns 579 ns 529 ns + 4M 2348 ns 1163 ns 770 ns 674 ns + +Re-announcing an existing torrent moves by under ten per cent over the same +range, so the cost is paid while the torrent population is built and not in +steady state. Below a few hundred thousand torrents there is nothing to win. +2^14 captures most of the gain for two per cent more resident memory. + +The cleaner's wake rate does not follow the bucket count. A cap of ten wakes +a second sets the sleep, and a wake cleans as many buckets as it must to +finish a sweep in OT_CLEAN_INTERVAL_MINUTES. At the default bucket count that +is one bucket every 117 ms. + + Paths not taken --------------- +A keyed hash for the bucket index. Info hashes are SHA-1 output and already +uniform, so it changes no distribution. It would buy resistance to deliberate +bucket flooding and cost the ordering a full scrape depends on: buckets are +ordered by hash prefix and sorted within, so walking them emits the sorted +dictionary bencode wants, with no sort and no copy. + +Cache line padding for the per-bucket locks and vector headers. The +contention it was meant to remove is not there. On glibc, where a 48-byte +mutex straddles a line, padding gains 3 to 8 per cent, but gains as much at +one thread where no false sharing can exist, and scaling from one to eight +threads is identical either way. On FreeBSD, where eight 8-byte mutexes share +a line and the risk should be highest, padding is 15 per cent slower at one +thread and neutral to 6 per cent slower at four and eight. + accf_http, the HTTP-aware accept filter. It duplicates a parser the tracker has anyway, puts more kernel code in the path, and holds a connection that sends "GET /" and stops, which accf_data hands straight over. diff --git a/Makefile b/Makefile index f124be8..993f0ae 100644 --- a/Makefile +++ b/Makefile @@ -20,6 +20,12 @@ STRIP?=strip #FEATURES+=-DWANT_DEV_RANDOM FEATURES+=-DWANT_FULLSCRAPE +# Buckets the torrent table is split into, as a power of two, 8 to 16. More +# buckets make inserting a new torrent cheaper and cost memory, which is worth +# it for a tracker carrying millions of torrents and not for one carrying +# thousands. DESIGN has the measurements. +FEATURES+=-DOT_BUCKET_COUNT_BITS=10 + #FEATURES+=-D_DEBUG_HTTPERROR #FEATURES+=-D_DEBUG_RANDOMTORRENTS diff --git a/ot_clean.c b/ot_clean.c index e1d1971..f181e83 100644 --- a/ot_clean.c +++ b/ot_clean.c @@ -125,26 +125,34 @@ static void clean_sleep(void) { pthread_mutex_unlock(&g_clean_mutex); } -/* Clean up all peers in current bucket, remove timedout pools and - torrents */ +/* Clean up all peers in one bucket, remove timedout pools and torrents */ +static void clean_bucket(size_t bucket) { + ot_vector *torrents_list = mutex_bucket_lock((int)bucket); + size_t toffs; + int delta_torrentcount = 0; + + for (toffs = 0; toffs < torrents_list->size; ++toffs) { + ot_torrent *torrent = ((ot_torrent *)(torrents_list->data)) + toffs; + if (clean_single_torrent(torrent)) { + vector_remove_torrent(torrents_list, torrent); + --delta_torrentcount; + --toffs; + } + } + mutex_bucket_unlock((int)bucket, delta_torrentcount); +} + static void *clean_worker(void *args) { (void)args; while (1) { size_t bucket = OT_BUCKET_COUNT; - while (bucket--) { - ot_vector *torrents_list = mutex_bucket_lock(bucket); - size_t toffs; - int delta_torrentcount = 0; - - for (toffs = 0; toffs < torrents_list->size; ++toffs) { - ot_torrent *torrent = ((ot_torrent *)(torrents_list->data)) + toffs; - if (clean_single_torrent(torrent)) { - vector_remove_torrent(torrents_list, torrent); - --delta_torrentcount; - --toffs; - } - } - mutex_bucket_unlock(bucket, delta_torrentcount); + while (bucket) { + size_t todo = bucket < OT_CLEAN_BUCKETS_PER_WAKE ? bucket : OT_CLEAN_BUCKETS_PER_WAKE; + + /* One bucket is locked at a time, however many a wake gets through */ + while (todo--) + clean_bucket(--bucket); + if (!g_opentracker_running) return NULL; clean_sleep(); diff --git a/ot_clean.h b/ot_clean.h index e069ee0..0592791 100644 --- a/ot_clean.h +++ b/ot_clean.h @@ -9,8 +9,17 @@ /* The amount of time a clean cycle should take */ #define OT_CLEAN_INTERVAL_MINUTES 2 -/* So after each bucket wait 1 / OT_BUCKET_COUNT intervals */ -#define OT_CLEAN_SLEEP (((OT_CLEAN_INTERVAL_MINUTES) * 60 * 1000000) / (OT_BUCKET_COUNT)) +/* How often the cleaner may wake. A full sweep takes OT_CLEAN_INTERVAL_MINUTES. + The clean operations per wake is goverend by OT_BUCKET_COUNT_BITS, + set by the Makefile. + At the default of 1024 buckets this works out at one bucket every + 117 ms. */ +#define OT_CLEAN_MAX_WAKES_PER_SECOND 10 + +#define OT_CLEAN_WAKE_BUDGET ((OT_CLEAN_INTERVAL_MINUTES) * 60 * (OT_CLEAN_MAX_WAKES_PER_SECOND)) +#define OT_CLEAN_BUCKETS_PER_WAKE (((OT_BUCKET_COUNT) + (OT_CLEAN_WAKE_BUDGET) - 1) / (OT_CLEAN_WAKE_BUDGET)) +#define OT_CLEAN_WAKES ((OT_BUCKET_COUNT) / (OT_CLEAN_BUCKETS_PER_WAKE)) +#define OT_CLEAN_SLEEP (((OT_CLEAN_INTERVAL_MINUTES) * 60 * 1000000) / (OT_CLEAN_WAKES)) void clean_init(void); void clean_deinit(void); diff --git a/tests/t_mutex.c b/tests/t_mutex.c index e54e2fa..c0c41cc 100644 --- a/tests/t_mutex.c +++ b/tests/t_mutex.c @@ -24,7 +24,7 @@ static void hash_for_bucket(ot_hash hash, int bucket) { } static void case_a_hash_names_its_bucket(void) { - static const int buckets[] = {0, 1, 2, 17, 511, 512, OT_BUCKET_COUNT - 1}; + static const int buckets[] = {0, 1, 2, 17, OT_BUCKET_COUNT / 2 - 1, OT_BUCKET_COUNT / 2, OT_BUCKET_COUNT - 1}; size_t i; test_case("a hash is served by the bucket its leading bits name"); diff --git a/trackerlogic.h b/trackerlogic.h index 338e4e6..7292d36 100644 --- a/trackerlogic.h +++ b/trackerlogic.h @@ -62,7 +62,12 @@ typedef struct { /* We maintain a list of 1024 pointers to sorted list of ot_torrent structs Sort key is, of course, its hash */ +/* Set from the Makefile, 8 to 16. More buckets means shorter vectors and a + cheaper insert, which only pays for a tracker carrying millions of + torrents; see DESIGN. */ +#ifndef OT_BUCKET_COUNT_BITS #define OT_BUCKET_COUNT_BITS 10 +#endif #define OT_BUCKET_COUNT (1 << OT_BUCKET_COUNT_BITS) #define OT_BUCKET_COUNT_SHIFT (32 - OT_BUCKET_COUNT_BITS) -- cgit v1.3