From 589cb500fa5a6df13fa9634d0071922ec11fce17 Mon Sep 17 00:00:00 2001 From: Dirk Engling Date: Sat, 7 Nov 2026 19:39:01 +0100 Subject: Unify the peerlists for v4 and v6 This commit finishes what started with unifying v4 and v6 trackers, from then on, torrents carried a peer list per family, with obvious redundancies. With the race to save memory, these became burdening enough that now these peerlist pointers have been moved into a single struct, holding both v4 and v6 peers in their respective ot_vectors, so the per- torrent cost shrunk by another pointer's size. Each peerlist also lost its peer count cache, as in most cases, it's trivial to load it directly from the ot_vector's entry count. The seed counts that were kept per family only to be aggregated later for every consumer, are also merged now. Total savings depend on the tracker's actual load. In some corner cases, where only one address family dominates the torrents, we actually use a few bytes more in the ot_vector for the absent family, but even that mostly becomes noise: before it actually adds to the memory load, the peer payload will be the deciding factor. Most wins are on what often is experienced on trackers: A long tail of abandoned torrents now needs eight fewer bytes, slipping into a smaller allocation unit on glibc's allocator. --- DESIGN | 33 ++++++++------- src/ot_clean.c | 64 +++++++++++++++------------- src/ot_fullscrape.c | 4 +- src/ot_stats.c | 14 +++---- src/ot_vector.c | 47 ++++++++++----------- src/ot_vector.h | 2 +- src/trackerlogic.c | 118 ++++++++++++++++++++++++---------------------------- src/trackerlogic.h | 39 +++++++++++------ tests/t_clean.c | 48 +++++++++++++++++++++ tests/t_vector.c | 63 ++++++++++++++-------------- 10 files changed, 248 insertions(+), 184 deletions(-) diff --git a/DESIGN b/DESIGN index a32eeb8..f089a3d 100644 --- a/DESIGN +++ b/DESIGN @@ -84,24 +84,29 @@ finish a sweep in OT_CLEAN_INTERVAL_MINUTES. At the default bucket count that is one bucket every 117 ms. -A torrent carries its hash, two peer-list pointers, a base and a down count, -48 bytes on a 64-bit host, and the down count sits in what would otherwise be -alignment padding. Each family's peer list, 32 bytes plus its peer vector, is -allocated on that family's first peer and freed when its last peer goes. The -base and the down count live on the torrent rather than on a list, which is -what lets a list come and go: a torrent kept only for its download count holds -no list at all, and a single-family torrent holds one rather than two. +A torrent carries its hash, one peerlist pointer, a base and a down count, 40 +bytes on a 64-bit host. The base and the down count live on the torrent, not +on a list, so a torrent kept only for its download count holds no list at all. +The one peerlist, allocated on the first peer of either family and freed when +the last peer of both goes, holds the two family vectors and a single seeder +count. The peer count is not stored, since a vector's own size is the count +for a plain list and the sum of its buckets for a split one. That leaves the +seeder count the only tally to maintain, because seeding is a per-peer flag +and counting it would mean a walk. This is paid for in the common shape of a large table. A tracker carrying millions of torrents averages close to two peers each, a few crowded swarms over a long tail of near-empty ones, so fixed per-torrent cost, not peer -payload, is most of resident memory. Allocating both lists for every torrent -and keeping an idle torrent alive for a day to preserve one counter cost, on -glibc, 168 bytes per torrent before a peer; the layout above costs 48 for an -empty torrent and 96 for a single-family one. The per-torrent counts are -uint32: no single torrent holds 2^32 peers, and the four bytes saved against a -size_t are multiplied by the torrent count. Global totals stay 64-bit. - +payload, is most of resident memory. An earlier layout gave each torrent two +always-allocated peer lists with their own counters and kept an idle torrent +alive for a day to preserve one number: on glibc 168 bytes before a peer. The +merged layout costs 40 for an empty torrent and, on glibc, 136 for a +single-family one and 184 for a torrent carrying both. A torrent with peers in +both families now takes one allocation rather than two. The split is drawn +along the family distribution: empty and both-family torrents gain, a +single-family torrent pays for the absent family's vector header. On jemalloc +the bins differ, so the per-shape figures do too, but the empty-torrent and +single-allocation gains hold on both. A refused announce is answered over UDP with a well formed announce for an empty swarm rather than with the error action. BEP 15 binds a client to the diff --git a/src/ot_clean.c b/src/ot_clean.c index 9e2186f..130bd2a 100644 --- a/src/ot_clean.c +++ b/src/ot_clean.c @@ -51,51 +51,48 @@ static ssize_t clean_single_bucket(ot_peer *peers, size_t peer_count, size_t pee return (peers - insert_point) / peer_size; } -/* Age one family's peers by timedout minutes. Frees the list and clears the - slot once its last peer is gone, so an absent family costs nothing. */ -static void clean_peer_list_family(ot_peerlist **slot, size_t peer_size, ot_time timedout) { - ot_peerlist *peer_list = *slot; - ot_vector *peer_vector; - size_t num_buckets = 1, removed_seeders = 0; - - if (!peer_list) - return; +/* Age one family's peers by timedout minutes. Releases and zeroes the vector + once its last peer is gone, so an empty family costs nothing. */ +static void clean_family_vector(ot_vector *peer_vector, size_t peer_size, ot_time timedout, size_t *removed_seeders) { + ot_vector *bucket = peer_vector; + size_t num_buckets = 1, peer_count; - peer_vector = &peer_list->peers; - if (OT_PEERLIST_HASBUCKETS(peer_list)) { + if (OT_VECTOR_HASBUCKETS(peer_vector)) { num_buckets = peer_vector->size; - peer_vector = (ot_vector *)peer_vector->data; + bucket = (ot_vector *)peer_vector->data; } while (num_buckets--) { - size_t removed_peers = clean_single_bucket(peer_vector->data, peer_vector->size, peer_size, timedout, &removed_seeders); - peer_list->peer_count -= removed_peers; - peer_vector->size -= removed_peers; + size_t removed_peers = clean_single_bucket(bucket->data, bucket->size, peer_size, timedout, removed_seeders); + bucket->size -= removed_peers; if (removed_peers) - vector_fixup_peers(peer_vector, peer_size); + vector_fixup_peers(bucket, peer_size); /* Skip to next bucket, a vector containing peers */ - ++peer_vector; + ++bucket; } - peer_list->seed_count -= removed_seeders; + peer_count = vector_peer_count(peer_vector); - if (!peer_list->peer_count) { - free_peerlist(peer_list); - *slot = NULL; + /* Run dry: release the family (a collapsed bucket list or a plain vector) */ + if (!peer_count) { + free_peer_vector(peer_vector); + memset(peer_vector, 0, sizeof(*peer_vector)); return; } - /* See if we need to convert the list from simple vector to bucket list */ - if ((peer_list->peer_count > OT_PEER_BUCKET_MINCOUNT) || OT_PEERLIST_HASBUCKETS(peer_list)) - vector_redistribute_buckets(peer_list, peer_size); + /* See if we need to convert the vector from simple to bucket list or back */ + if ((peer_count > OT_PEER_BUCKET_MINCOUNT) || OT_VECTOR_HASBUCKETS(peer_vector)) + vector_redistribute_buckets(peer_vector, peer_size, peer_count); } /* Clean a single torrent return 1 if torrent timed out */ int clean_single_torrent(ot_torrent *torrent) { - ot_time timedout = time_since_minutes(torrent->base); + ot_time timedout = time_since_minutes(torrent->base); + ot_peerlist *peer_list = torrent->peer_list; + size_t removed_seeders = 0; /* Touched since the last sweep: nothing to do */ if (!timedout) @@ -107,7 +104,7 @@ int clean_single_torrent(ot_torrent *torrent) { /* Already empty and nothing arrived before the peer timeout: keep it only while a down count is worth remembering */ - if (timedout > OT_PEER_TIMEOUT && !torrent->peer_list6 && !torrent->peer_list4) + if (timedout > OT_PEER_TIMEOUT && !peer_list) return (torrent->down_count && timedout <= g_empty_torrent_timeout) ? 0 : 1; /* Peers past the peer timeout are gone regardless, which caps how far the @@ -115,10 +112,19 @@ int clean_single_torrent(ot_torrent *torrent) { if (timedout > OT_PEER_TIMEOUT) timedout = OT_PEER_TIMEOUT; - clean_peer_list_family(&torrent->peer_list6, OT_PEER_SIZE6, timedout); - clean_peer_list_family(&torrent->peer_list4, OT_PEER_SIZE4, timedout); + if (peer_list) { + clean_family_vector(&peer_list->peers6, OT_PEER_SIZE6, timedout, &removed_seeders); + clean_family_vector(&peer_list->peers4, OT_PEER_SIZE4, timedout, &removed_seeders); + peer_list->seed_count -= removed_seeders; + + /* Both families gone: drop the peerlist, the torrent keeps only its count */ + if (!vector_peer_count(&peer_list->peers6) && !vector_peer_count(&peer_list->peers4)) { + free_peerlist(peer_list); + torrent->peer_list = peer_list = NULL; + } + } - if (torrent->peer_list6 || torrent->peer_list4) + if (peer_list) torrent->base = time_now_minutes(); /* still carrying peers */ else { /* Fell empty: hold base a peer timeout back so a later idle sweep makes diff --git a/src/ot_fullscrape.c b/src/ot_fullscrape.c index 9fae444..787b508 100644 --- a/src/ot_fullscrape.c +++ b/src/ot_fullscrape.c @@ -90,8 +90,8 @@ static void fullscrape_write_one( ot_tasktype mode, char **cursor, ot_torrent *t exactly that size */ char *r = *cursor; const char *r_end = r + OT_SCRAPE_MAXENTRYLEN; - size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); - size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); + size_t seed_count = torrent_seed_count(torrent); + size_t peer_count = torrent_peer_count(torrent); size_t down_count = torrent->down_count; switch (mode & TASK_TASK_MASK) { diff --git a/src/ot_stats.c b/src/ot_stats.c index 9e2eabe..0e2fc67 100644 --- a/src/ot_stats.c +++ b/src/ot_stats.c @@ -243,15 +243,15 @@ static void stats_slash24s_txt(char **reply, const char *reply_end, size_t amoun for (bucket = 0; bucket < OT_BUCKET_COUNT; ++bucket) { ot_vector *torrents_list = mutex_bucket_lock(bucket); for (i = 0; i < torrents_list->size; ++i) { - ot_peerlist *peer_list = (((ot_torrent *)(torrents_list->data))[i]).peer_list4; + ot_peerlist *peer_list = (((ot_torrent *)(torrents_list->data))[i]).peer_list; ot_vector *bucket_list; int num_buckets = 1; if (!peer_list) continue; - bucket_list = &peer_list->peers; + bucket_list = &peer_list->peers4; /* /24 networks are an IPv4 notion */ - if (OT_PEERLIST_HASBUCKETS(peer_list)) { + if (OT_VECTOR_HASBUCKETS(bucket_list)) { num_buckets = bucket_list->size; bucket_list = (ot_vector *)bucket_list->data; } @@ -303,8 +303,8 @@ typedef struct { static int torrent_statter(ot_torrent *torrent, uintptr_t data) { torrent_stats *stats = (torrent_stats *)data; stats->torrent_count++; - stats->peer_count += peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); - stats->seed_count += peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); + stats->peer_count += torrent_peer_count(torrent); + stats->seed_count += torrent_seed_count(torrent); return 0; } @@ -347,8 +347,8 @@ void stats_top_txt(char **reply, const char *reply_end, size_t amount) { ot_vector *torrents_list = mutex_bucket_lock(bucket); for (j = 0; j < torrents_list->size; ++j) { ot_torrent *torrent = (ot_torrent *)(torrents_list->data) + j; - size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); - size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); + size_t peer_count = torrent_peer_count(torrent); + size_t seed_count = torrent_seed_count(torrent); size_t leech_count = peer_count - seed_count; stats_insert_into_highscore(peer_count, top100c, amount, &torrent->hash); diff --git a/src/ot_vector.c b/src/ot_vector.c index 23dfb10..ef38919 100644 --- a/src/ot_vector.c +++ b/src/ot_vector.c @@ -160,8 +160,7 @@ void vector_remove_torrent(ot_vector *vector, ot_torrent *match) { end = ((ot_torrent *)vector->data) + vector->size; - free_peerlist(match->peer_list6); - free_peerlist(match->peer_list4); + free_peerlist(match->peer_list); memmove(match, match + 1, sizeof(ot_torrent) * (end - match - 1)); if ((--vector->size * OT_VECTOR_SHRINK_THRESH < vector->space) && (vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS)) { @@ -180,27 +179,27 @@ void vector_clean_list(ot_vector *vector, size_t num_buckets) { return; } -void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { +void vector_redistribute_buckets(ot_vector *peer_vector, size_t peer_size, size_t peer_count) { size_t bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; - ot_vector *bucket_list_new, *bucket_list_old = &peer_list->peers; + ot_vector *bucket_list_new, *bucket_list_old = peer_vector; int (*sort_func)(const void *, const void *) = peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4; - if (OT_PEERLIST_HASBUCKETS(peer_list)) { - num_buckets_old = peer_list->peers.size; - bucket_list_old = peer_list->peers.data; + if (OT_VECTOR_HASBUCKETS(peer_vector)) { + num_buckets_old = peer_vector->size; + bucket_list_old = peer_vector->data; } - if (peer_list->peer_count < 255) + if (peer_count < 255) num_buckets_new = 1; - else if (peer_list->peer_count > 8192) + else if (peer_count > 8192) num_buckets_new = 64; - else if (peer_list->peer_count >= 512 && peer_list->peer_count < 4096) + else if (peer_count >= 512 && peer_count < 4096) num_buckets_new = 16; - else if (peer_list->peer_count < 512 && num_buckets_old <= 16) + else if (peer_count < 512 && num_buckets_old <= 16) num_buckets_new = num_buckets_old; - else if (peer_list->peer_count < 512) + else if (peer_count < 512) num_buckets_new = 1; - else if (peer_list->peer_count < 8192 && num_buckets_old > 1) + else if (peer_count < 8192 && num_buckets_old > 1) num_buckets_new = num_buckets_old; else num_buckets_new = 16; @@ -214,7 +213,7 @@ void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { return; bucket_size_new = OT_VECTOR_MIN_MEMBERS; - while (bucket_size_new * num_buckets_new < peer_list->peer_count) + while (bucket_size_new * num_buckets_new < peer_count) bucket_size_new *= OT_VECTOR_GROW_RATIO; /* preallocate vectors to hold all peers */ @@ -253,20 +252,20 @@ void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { for (bucket = 0; bucket < num_buckets_new; ++bucket) qsort(bucket_list_new[bucket].data, bucket_list_new[bucket].size, peer_size, sort_func); - /* Everything worked fine. Now link new bucket_list to peer_list */ - if (OT_PEERLIST_HASBUCKETS(peer_list)) - vector_clean_list((ot_vector *)peer_list->peers.data, peer_list->peers.size); + /* Everything worked fine. Now link new bucket_list to the vector */ + if (OT_VECTOR_HASBUCKETS(peer_vector)) + vector_clean_list((ot_vector *)peer_vector->data, peer_vector->size); else - free(peer_list->peers.data); + free(peer_vector->data); if (num_buckets_new > 1) { - peer_list->peers.data = bucket_list_new; - peer_list->peers.size = num_buckets_new; - peer_list->peers.space = 0; /* Magic marker for "is list of buckets" */ + peer_vector->data = bucket_list_new; + peer_vector->size = num_buckets_new; + peer_vector->space = 0; /* Magic marker for "is list of buckets" */ } else { - peer_list->peers.data = bucket_list_new->data; - peer_list->peers.size = bucket_list_new->size; - peer_list->peers.space = bucket_list_new->space; + peer_vector->data = bucket_list_new->data; + peer_vector->size = bucket_list_new->size; + peer_vector->space = bucket_list_new->space; free(bucket_list_new); } } diff --git a/src/ot_vector.h b/src/ot_vector.h index 8a5ba86..1a73fcf 100644 --- a/src/ot_vector.h +++ b/src/ot_vector.h @@ -32,7 +32,7 @@ int vector_remove_peer(ot_vector *vector, ot_peer const *peer, size_t peer_ void vector_remove_torrent(ot_vector *vector, ot_torrent *match); /* For ot_clean.c */ -void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size); +void vector_redistribute_buckets(ot_vector *peer_vector, size_t peer_size, size_t peer_count); void vector_fixup_peers(ot_vector *vector, size_t peer_size); void vector_clean_list(ot_vector *vector, size_t num_buckets); diff --git a/src/trackerlogic.c b/src/trackerlogic.c index 6b0659c..4ba3a41 100644 --- a/src/trackerlogic.c +++ b/src/trackerlogic.c @@ -28,13 +28,18 @@ /* Forward declaration */ size_t return_peers_for_torrent(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply, PROTO_FLAG proto); +void free_peer_vector(ot_vector *peer_vector) { + if (OT_VECTOR_HASBUCKETS(peer_vector)) + vector_clean_list((ot_vector *)peer_vector->data, peer_vector->size); + else + free(peer_vector->data); /* free(NULL) on an absent family is fine */ +} + void free_peerlist(ot_peerlist *peer_list) { - if (peer_list && peer_list->peers.data) { - if (OT_PEERLIST_HASBUCKETS(peer_list)) - vector_clean_list((ot_vector *)peer_list->peers.data, peer_list->peers.size); - else - free(peer_list->peers.data); - } + if (!peer_list) + return; + free_peer_vector(&peer_list->peers6); + free_peer_vector(&peer_list->peers4); free(peer_list); } @@ -113,20 +118,17 @@ size_t add_peer_to_torrent_and_return_peers(PROTO_FLAG proto, struct ot_workstru torrent->base = time_now_minutes(); - /* The announcing peer's family list is created on first use */ - { - ot_peerlist **slot = peer_size == OT_PEER_SIZE6 ? &torrent->peer_list6 : &torrent->peer_list4; - if (!*slot && !(*slot = calloc(1, sizeof(ot_peerlist)))) { - if (delta_torrentcount) - vector_remove_torrent(torrents_list, torrent); - mutex_bucket_unlock_by_hash(*ws->hash, 0); - return 0; - } - peer_list = *slot; + /* The peerlist, holding both families, is created on the first peer */ + if (!torrent->peer_list && !(torrent->peer_list = calloc(1, sizeof(ot_peerlist)))) { + if (delta_torrentcount) + vector_remove_torrent(torrents_list, torrent); + mutex_bucket_unlock_by_hash(*ws->hash, 0); + return 0; } + peer_list = torrent->peer_list; - /* Check for peer in torrent */ - peer_dest = vector_find_or_insert_peer(&(peer_list->peers), peer_src, peer_size, &exactmatch); + /* Check for peer in its family's vector */ + peer_dest = vector_find_or_insert_peer(peer_size == OT_PEER_SIZE6 ? &peer_list->peers6 : &peer_list->peers4, peer_src, peer_size, &exactmatch); if (!peer_dest) { mutex_bucket_unlock_by_hash(*ws->hash, delta_torrentcount); return 0; @@ -149,7 +151,6 @@ size_t add_peer_to_torrent_and_return_peers(PROTO_FLAG proto, struct ot_workstru livesync_tell(ws); #endif - peer_list->peer_count++; if (OT_PEERFLAG(ws->peer) & PEER_FLAG_COMPLETED) { torrent->down_count++; stats_issue_event(ws, EVENT_COMPLETED, 0, 0); @@ -198,14 +199,14 @@ size_t add_peer_to_torrent_and_return_peers(PROTO_FLAG proto, struct ot_workstru return ws->reply_size; } -static size_t return_peers_all(ot_peerlist *peer_list, size_t peer_size, char *reply) { +static size_t return_peers_all(ot_vector *peer_vector, size_t peer_size, size_t peer_count, char *reply) { size_t bucket, num_buckets = 1; - ot_vector *bucket_list = &peer_list->peers; + ot_vector *bucket_list = peer_vector; size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); - size_t result = compare_size * peer_list->peer_count; + size_t result = compare_size * peer_count; char *r_end = reply + result; - if (OT_PEERLIST_HASBUCKETS(peer_list)) { + if (OT_VECTOR_HASBUCKETS(peer_vector)) { num_buckets = bucket_list->size; bucket_list = (ot_vector *)bucket_list->data; } @@ -227,17 +228,17 @@ static size_t return_peers_all(ot_peerlist *peer_list, size_t peer_size, char *r return result; } -static size_t return_peers_selection(struct ot_workstruct *ws, ot_peerlist *peer_list, size_t peer_size, size_t amount, char *reply) { +static size_t return_peers_selection(struct ot_workstruct *ws, ot_vector *peer_vector, size_t peer_size, size_t amount, size_t peer_count, char *reply) { size_t bucket_offset, bucket_index = 0, num_buckets = 1; - ot_vector *bucket_list = &peer_list->peers; - unsigned int shifted_pc = peer_list->peer_count; + ot_vector *bucket_list = peer_vector; + unsigned int shifted_pc = peer_count; unsigned int shifted_step = 0; unsigned int shift = 0; size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); size_t result = compare_size * amount; char *r_end = reply + result; - if (OT_PEERLIST_HASBUCKETS(peer_list)) { + if (OT_VECTOR_HASBUCKETS(peer_vector)) { num_buckets = bucket_list->size; bucket_list = (ot_vector *)bucket_list->data; } @@ -253,7 +254,7 @@ static size_t return_peers_selection(struct ot_workstruct *ws, ot_peerlist *peer /* Initialize somewhere in the middle of peers so that fixpoint's aliasing doesn't alway miss the same peers */ - bucket_offset = nrand48(ws->rand48_state) % peer_list->peer_count; + bucket_offset = nrand48(ws->rand48_state) % peer_count; while (amount--) { ot_peer *peer; @@ -281,10 +282,11 @@ static size_t return_peers_selection(struct ot_workstruct *ws, ot_peerlist *peer static size_t return_peers_for_torrent_udp(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply) { char *r = reply; size_t peer_size = peer_size_from_peer6(&ws->peer); - ot_peerlist *peer_list = peer_size == OT_PEER_SIZE6 ? torrent->peer_list6 : torrent->peer_list4; - size_t list_count = peerlist_peer_count(peer_list); - size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); - size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); + ot_peerlist *peer_list = torrent->peer_list; + ot_vector *family = peer_size == OT_PEER_SIZE6 ? &peer_list->peers6 : &peer_list->peers4; + size_t list_count = vector_peer_count(family); + size_t peer_count = torrent_peer_count(torrent); + size_t seed_count = torrent_seed_count(torrent); if (amount > list_count) amount = list_count; @@ -296,9 +298,9 @@ static size_t return_peers_for_torrent_udp(struct ot_workstruct *ws, ot_torrent if (amount) { if (amount == list_count) - r += return_peers_all(peer_list, peer_size, r); + r += return_peers_all(family, peer_size, list_count, r); else - r += return_peers_selection(ws, peer_list, peer_size, amount, r); + r += return_peers_selection(ws, family, peer_size, amount, list_count, r); } return r - reply; } @@ -307,9 +309,10 @@ static size_t return_peers_for_torrent_tcp(struct ot_workstruct *ws, ot_torrent char *r = reply; const char *r_end = ws->outbuf + G_OUTBUF_SIZE; int erval = OT_CLIENT_REQUEST_INTERVAL_RANDOM; - size_t count6 = peerlist_peer_count(torrent->peer_list6); - size_t count4 = peerlist_peer_count(torrent->peer_list4); - size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); + ot_peerlist *peer_list = torrent->peer_list; + size_t count6 = vector_peer_count(&peer_list->peers6); + size_t count4 = vector_peer_count(&peer_list->peers4); + size_t seed_count = peer_list->seed_count; size_t down_count = torrent->down_count; size_t peer_count = count6 + count4 - seed_count; @@ -355,17 +358,17 @@ static size_t return_peers_for_torrent_tcp(struct ot_workstruct *ws, ot_torrent if (amount_v4) { fmt_append(&r, r_end, PEERS_BENCODED4 "%zd:", OT_PEER_COMPARE_SIZE4 * amount_v4); if (amount_v4 == count4) - r += return_peers_all(torrent->peer_list4, OT_PEER_SIZE4, r); + r += return_peers_all(&peer_list->peers4, OT_PEER_SIZE4, count4, r); else - r += return_peers_selection(ws, torrent->peer_list4, OT_PEER_SIZE4, amount_v4, r); + r += return_peers_selection(ws, &peer_list->peers4, OT_PEER_SIZE4, amount_v4, count4, r); } if (amount_v6) { fmt_append(&r, r_end, PEERS_BENCODED6 "%zd:", OT_PEER_COMPARE_SIZE6 * amount_v6); if (amount_v6 == count6) - r += return_peers_all(torrent->peer_list6, OT_PEER_SIZE6, r); + r += return_peers_all(&peer_list->peers6, OT_PEER_SIZE6, count6, r); else - r += return_peers_selection(ws, torrent->peer_list6, OT_PEER_SIZE6, amount_v6, r); + r += return_peers_selection(ws, &peer_list->peers6, OT_PEER_SIZE6, amount_v6, count6, r); } fmt_append(&r, r_end, "e"); @@ -401,9 +404,9 @@ size_t return_udp_scrape_for_torrent(ot_hash const hash, char *reply) { memset(reply, 0, 12); delta_torrentcount = -1; } else { - r[0] = htonl(peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4)); + r[0] = htonl(torrent_seed_count(torrent)); r[1] = htonl(torrent->down_count); - r[2] = htonl(peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4) - peerlist_seed_count(torrent->peer_list6) - peerlist_seed_count(torrent->peer_list4)); + r[2] = htonl(torrent_peer_count(torrent) - torrent_seed_count(torrent)); } } mutex_bucket_unlock_by_hash(hash, delta_torrentcount); @@ -430,8 +433,8 @@ void return_tcp_scrape_for_torrent(ot_hash const *hash_list, size_t amount, char } else { fmt_append(reply, reply_end, "20:"); fmt_bytes(reply, reply_end, hash, sizeof(ot_hash)); - size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); - size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); + size_t seed_count = torrent_seed_count(torrent); + size_t peer_count = torrent_peer_count(torrent); fmt_append(reply, reply_end, "d8:completei%zde10:downloadedi%zde10:incompletei%zdee", seed_count, (size_t)torrent->down_count, peer_count - seed_count); } } @@ -441,12 +444,10 @@ void return_tcp_scrape_for_torrent(ot_hash const *hash_list, size_t amount, char fmt_append(reply, reply_end, "ee"); } -static ot_peerlist dummy_list; size_t remove_peer_from_torrent(PROTO_FLAG proto, struct ot_workstruct *ws) { int exactmatch; ot_vector *torrents_list = mutex_bucket_lock_by_hash(*ws->hash); ot_torrent *torrent = vector_binary_search(ws->hash, torrents_list->data, torrents_list->size, sizeof(ot_torrent), OT_HASH_COMPARE_SIZE, &exactmatch); - ot_peerlist *peer_list = &dummy_list; size_t peer_size; /* initialized in next line */ ot_peer const *peer_src = peer_from_peer6(&ws->peer, &peer_size); size_t peer_count = 0, seed_count = 0; @@ -458,21 +459,13 @@ size_t remove_peer_from_torrent(PROTO_FLAG proto, struct ot_workstruct *ws) { } #endif - if (exactmatch) { - peer_list = peer_size == OT_PEER_SIZE6 ? torrent->peer_list6 : torrent->peer_list4; - if (peer_list) { - switch (vector_remove_peer(&peer_list->peers, peer_src, peer_size)) { - case 2: - peer_list->seed_count--; /* Intentional fallthrough */ - case 1: - peer_list->peer_count--; /* Intentional fallthrough */ - default: - break; - } - } + if (exactmatch && torrent->peer_list) { + ot_vector *family = peer_size == OT_PEER_SIZE6 ? &torrent->peer_list->peers6 : &torrent->peer_list->peers4; + if (vector_remove_peer(family, peer_src, peer_size) == 2) + torrent->peer_list->seed_count--; - peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); - seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); + peer_count = torrent_peer_count(torrent); + seed_count = torrent_seed_count(torrent); } if (proto == FLAG_TCP) { @@ -621,8 +614,7 @@ void trackerlogic_deinit(void) { if (torrents_list->size) { for (j = 0; j < torrents_list->size; ++j) { ot_torrent *torrent = ((ot_torrent *)(torrents_list->data)) + j; - free_peerlist(torrent->peer_list6); - free_peerlist(torrent->peer_list4); + free_peerlist(torrent->peer_list); delta_torrentcount -= 1; } free(torrents_list->data); diff --git a/src/trackerlogic.h b/src/trackerlogic.h index c4b7774..dd8a48c 100644 --- a/src/trackerlogic.h +++ b/src/trackerlogic.h @@ -170,26 +170,40 @@ struct ot_peerlist; typedef struct ot_peerlist ot_peerlist; typedef struct { ot_hash hash; - ot_peerlist *peer_list6; /* NULL until the torrent has a v6 peer */ - ot_peerlist *peer_list4; /* NULL until the torrent has a v4 peer */ - uint32_t base; /* minutes, when the torrent was last cleaned */ - uint32_t down_count; /* completed events, summed over both families */ + ot_peerlist *peer_list; /* NULL until the torrent has a peer in either family */ + uint32_t base; /* epoch minutes, when the torrent was last cleaned */ + uint32_t down_count; /* completed events */ } ot_torrent; #include "ot_vector.h" struct ot_peerlist { uint32_t seed_count; - uint32_t peer_count; - /* normal peers vector or - pointer to ot_vector[32] buckets if data != NULL and space == 0 - */ - ot_vector peers; + /* each family's peers: a normal vector, or a pointer to ot_vector[] buckets + when data != NULL and space == 0 (size then holds the bucket count) */ + ot_vector peers6; + ot_vector peers4; }; -#define OT_PEERLIST_HASBUCKETS(peer_list) ((peer_list)->peers.size > (peer_list)->peers.space) -static inline uint32_t peerlist_peer_count(const ot_peerlist *peer_list) { return peer_list ? peer_list->peer_count : 0; } -static inline uint32_t peerlist_seed_count(const ot_peerlist *peer_list) { return peer_list ? peer_list->seed_count : 0; } +/* A peer vector becomes a bucket list of peer vectors, marker is size > space (usually 0) */ +#define OT_VECTOR_HASBUCKETS(v) ((v)->size > (v)->space) + +/* Peers in one family: a plain vector's size is the count, a bucket list's is + the sum of its buckets. O(1) for the small torrents that dominate a table. */ +static inline size_t vector_peer_count(const ot_vector *v) { + const ot_vector *b; + size_t n, total = 0; + if (!OT_VECTOR_HASBUCKETS(v)) + return v->size; + b = (const ot_vector *)v->data; + for (n = 0; n < v->size; ++n) + total += b[n].size; + return total; +} +static inline size_t torrent_peer_count(const ot_torrent *t) { + return t->peer_list ? vector_peer_count(&t->peer_list->peers6) + vector_peer_count(&t->peer_list->peers4) : 0; +} +static inline uint32_t torrent_seed_count(const ot_torrent *t) { return t->peer_list ? t->peer_list->seed_count : 0; } /* The http replies the tracker counts when it has to refuse a request. */ enum { @@ -314,5 +328,6 @@ void iterate_all_torrents(int (*for_each)(ot_torrent *torrent, uintptr_t data), /* Helper, before it moves to its own object */ void free_peerlist(ot_peerlist *peer_list); +void free_peer_vector(ot_vector *peer_vector); #endif diff --git a/tests/t_clean.c b/tests/t_clean.c index 0237cc6..ce17bc3 100644 --- a/tests/t_clean.c +++ b/tests/t_clean.c @@ -33,6 +33,20 @@ static void announce(struct ot_workstruct *ws, ot_hash *hash, uint8_t last_octet add_peer_to_torrent_and_return_peers(FLAG_TCP, ws, 0); } +/* A distinct v4 peer addressed by two octets, to build swarms past 256 */ +static size_t announce_wide(struct ot_workstruct *ws, ot_hash *hash, unsigned int which, size_t amount) { + static const uint8_t v4mapped[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff, 0xff}; + + ws->reply = ws->outbuf; + memset(&ws->peer, 0, sizeof(ws->peer)); + memcpy(&ws->peer, v4mapped, sizeof(v4mapped)); + ((uint8_t *)&ws->peer)[14] = (uint8_t)(which >> 8); + ((uint8_t *)&ws->peer)[15] = (uint8_t)which; + OT_SETPORT(&ws->peer, &(uint16_t){6881}); + ws->hash = hash; + return add_peer_to_torrent_and_return_peers(FLAG_TCP, ws, amount); +} + static size_t peers_in(ot_hash *hash) { char reply[1024]; size_t len = return_udp_scrape_for_torrent(*hash, reply); @@ -157,6 +171,39 @@ static void case_empty_torrent_timeout_bounds_a_counter_only_torrent(void) { workstruct_deinit(&ws); } +static void case_a_bucketed_swarm_survives_clean_and_serves(void) { + struct ot_workstruct ws; + ot_hash hash; + ot_torrent *torrent; + unsigned int i; + const unsigned int n = 600; /* past OT_PEER_BUCKET_MINCOUNT (512) */ + + test_case("a swarm large enough to be bucketed cleans, splits and serves without loss"); + memset(hash, 0x34, sizeof(hash)); + CHECK_INT(workstruct_init(&ws, G_INBUF_SIZE), 0); + + for (i = 0; i < n; ++i) + announce_wide(&ws, &hash, i, 0); + CHECK_INT(peers_in(&hash), n); + + torrent = torrent_of(&hash); + CHECK(torrent != NULL); + CHECK(torrent->peer_list != NULL); + + /* A clean with a minute elapsed splits the flat vector into buckets */ + step_clock_back(torrent, -1); + CHECK_INT(clean_single_torrent(torrent), 0); + CHECK(torrent->peer_list != NULL); + CHECK_INT(OT_VECTOR_HASBUCKETS(&torrent->peer_list->peers4), 1); + CHECK_INT(peers_in(&hash), n); + + /* Serve a selection back, which walks the bucket list */ + CHECK(announce_wide(&ws, &hash, 1, 200) > 0); + CHECK_INT(peers_in(&hash), n); + + workstruct_deinit(&ws); +} + void test_clean(void) { sigset_t hup; @@ -170,5 +217,6 @@ void test_clean(void) { case_a_clock_that_went_back_keeps_the_swarm(); case_an_idle_swarm_still_ages_out(); case_empty_torrent_timeout_bounds_a_counter_only_torrent(); + case_a_bucketed_swarm_survives_clean_and_serves(); trackerlogic_deinit(); } diff --git a/tests/t_vector.c b/tests/t_vector.c index f0a9bf7..42ce31a 100644 --- a/tests/t_vector.c +++ b/tests/t_vector.c @@ -200,17 +200,16 @@ static void case_insert_compare_prefix(void) { into the first address byte, so the peers are distinct but arrive in no particular order: a list generated in ascending order would come back sorted whether or not vector_redistribute_buckets sorted it. */ -static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) { +static void build_flat_vector(ot_vector *peers, size_t count) { size_t i; - memset(peer_list, 0, sizeof(*peer_list)); - peer_list->peers.data = malloc(count * OT_PEER_SIZE4); - peer_list->peers.size = count; - peer_list->peers.space = count; - peer_list->peer_count = count; + memset(peers, 0, sizeof(*peers)); + peers->data = malloc(count * OT_PEER_SIZE4); + peers->size = count; + peers->space = count; for (i = 0; i < count; ++i) { - uint8_t *peer = (uint8_t *)peer_list->peers.data + i * OT_PEER_SIZE4; + uint8_t *peer = (uint8_t *)peers->data + i * OT_PEER_SIZE4; memset(peer, 0, OT_PEER_SIZE4); peer[0] = (uint8_t)i; @@ -222,19 +221,19 @@ static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) { static void case_redistribute_holds_every_peer(void) { const size_t count = 513; - ot_peerlist peer_list; + ot_vector peers; size_t bucket, total_size = 0, empty = 0, largest = 0; ot_vector *buckets; test_case("a peer list past the threshold is split into buckets"); - build_flat_peerlist(&peer_list, count); - CHECK(peer_list.peers.data != NULL); - vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); - CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1); - CHECK_INT(peer_list.peers.size, 16); - - buckets = peer_list.peers.data; - for (bucket = 0; bucket < peer_list.peers.size; ++bucket) { + build_flat_vector(&peers, count); + CHECK(peers.data != NULL); + vector_redistribute_buckets(&peers, OT_PEER_SIZE4, count); + CHECK_INT(OT_VECTOR_HASBUCKETS(&peers), 1); + CHECK_INT(peers.size, 16); + + buckets = peers.data; + for (bucket = 0; bucket < peers.size; ++bucket) { total_size += buckets[bucket].size; if (!buckets[bucket].size) ++empty; @@ -252,23 +251,23 @@ static void case_redistribute_holds_every_peer(void) { CHECK_INT(empty, 0); CHECK(largest < count / 2); - vector_clean_list(peer_list.peers.data, peer_list.peers.size); + vector_clean_list(peers.data, peers.size); } static void case_redistribute_sorts_each_bucket(void) { const size_t count = 1000; - ot_peerlist peer_list; + ot_vector peers; size_t bucket, i, out_of_order = 0; ot_vector *buckets; test_case("every bucket comes back sorted, so bsearch can be used on it"); - build_flat_peerlist(&peer_list, count); - CHECK(peer_list.peers.data != NULL); - vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); - CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1); + build_flat_vector(&peers, count); + CHECK(peers.data != NULL); + vector_redistribute_buckets(&peers, OT_PEER_SIZE4, count); + CHECK_INT(OT_VECTOR_HASBUCKETS(&peers), 1); - buckets = peer_list.peers.data; - for (bucket = 0; bucket < peer_list.peers.size; ++bucket) + buckets = peers.data; + for (bucket = 0; bucket < peers.size; ++bucket) for (i = 1; i < buckets[bucket].size; ++i) { const uint8_t *prev = (uint8_t *)buckets[bucket].data + (i - 1) * OT_PEER_SIZE4; const uint8_t *next = (uint8_t *)buckets[bucket].data + i * OT_PEER_SIZE4; @@ -278,19 +277,19 @@ static void case_redistribute_sorts_each_bucket(void) { } CHECK_INT(out_of_order, 0); - vector_clean_list(peer_list.peers.data, peer_list.peers.size); + vector_clean_list(peers.data, peers.size); } static void case_redistribute_below_threshold(void) { - ot_peerlist peer_list; + ot_vector peers; test_case("a small peer list is left flat"); - build_flat_peerlist(&peer_list, 100); - CHECK(peer_list.peers.data != NULL); - vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); - CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 0); - CHECK_INT(peer_list.peers.size, 100); - free(peer_list.peers.data); + build_flat_vector(&peers, 100); + CHECK(peers.data != NULL); + vector_redistribute_buckets(&peers, OT_PEER_SIZE4, 100); + CHECK_INT(OT_VECTOR_HASBUCKETS(&peers), 0); + CHECK_INT(peers.size, 100); + free(peers.data); } void test_vector(void) { -- cgit v1.3