diff options
| -rw-r--r-- | DESIGN | 33 | ||||
| -rw-r--r-- | src/ot_clean.c | 64 | ||||
| -rw-r--r-- | src/ot_fullscrape.c | 4 | ||||
| -rw-r--r-- | src/ot_stats.c | 14 | ||||
| -rw-r--r-- | src/ot_vector.c | 47 | ||||
| -rw-r--r-- | src/ot_vector.h | 2 | ||||
| -rw-r--r-- | src/trackerlogic.c | 118 | ||||
| -rw-r--r-- | src/trackerlogic.h | 39 | ||||
| -rw-r--r-- | tests/t_clean.c | 48 | ||||
| -rw-r--r-- | tests/t_vector.c | 61 |
10 files changed, 247 insertions, 183 deletions
| @@ -84,24 +84,29 @@ finish a sweep in OT_CLEAN_INTERVAL_MINUTES. At the default bucket count that | |||
| 84 | is one bucket every 117 ms. | 84 | is one bucket every 117 ms. |
| 85 | 85 | ||
| 86 | 86 | ||
| 87 | A torrent carries its hash, two peer-list pointers, a base and a down count, | 87 | A torrent carries its hash, one peerlist pointer, a base and a down count, 40 |
| 88 | 48 bytes on a 64-bit host, and the down count sits in what would otherwise be | 88 | bytes on a 64-bit host. The base and the down count live on the torrent, not |
| 89 | alignment padding. Each family's peer list, 32 bytes plus its peer vector, is | 89 | on a list, so a torrent kept only for its download count holds no list at all. |
| 90 | allocated on that family's first peer and freed when its last peer goes. The | 90 | The one peerlist, allocated on the first peer of either family and freed when |
| 91 | base and the down count live on the torrent rather than on a list, which is | 91 | the last peer of both goes, holds the two family vectors and a single seeder |
| 92 | what lets a list come and go: a torrent kept only for its download count holds | 92 | count. The peer count is not stored, since a vector's own size is the count |
| 93 | no list at all, and a single-family torrent holds one rather than two. | 93 | for a plain list and the sum of its buckets for a split one. That leaves the |
| 94 | seeder count the only tally to maintain, because seeding is a per-peer flag | ||
| 95 | and counting it would mean a walk. | ||
| 94 | 96 | ||
| 95 | This is paid for in the common shape of a large table. A tracker carrying | 97 | This is paid for in the common shape of a large table. A tracker carrying |
| 96 | millions of torrents averages close to two peers each, a few crowded swarms | 98 | millions of torrents averages close to two peers each, a few crowded swarms |
| 97 | over a long tail of near-empty ones, so fixed per-torrent cost, not peer | 99 | over a long tail of near-empty ones, so fixed per-torrent cost, not peer |
| 98 | payload, is most of resident memory. Allocating both lists for every torrent | 100 | payload, is most of resident memory. An earlier layout gave each torrent two |
| 99 | and keeping an idle torrent alive for a day to preserve one counter cost, on | 101 | always-allocated peer lists with their own counters and kept an idle torrent |
| 100 | glibc, 168 bytes per torrent before a peer; the layout above costs 48 for an | 102 | alive for a day to preserve one number: on glibc 168 bytes before a peer. The |
| 101 | empty torrent and 96 for a single-family one. The per-torrent counts are | 103 | merged layout costs 40 for an empty torrent and, on glibc, 136 for a |
| 102 | uint32: no single torrent holds 2^32 peers, and the four bytes saved against a | 104 | single-family one and 184 for a torrent carrying both. A torrent with peers in |
| 103 | size_t are multiplied by the torrent count. Global totals stay 64-bit. | 105 | both families now takes one allocation rather than two. The split is drawn |
| 104 | 106 | along the family distribution: empty and both-family torrents gain, a | |
| 107 | single-family torrent pays for the absent family's vector header. On jemalloc | ||
| 108 | the bins differ, so the per-shape figures do too, but the empty-torrent and | ||
| 109 | single-allocation gains hold on both. | ||
| 105 | 110 | ||
| 106 | A refused announce is answered over UDP with a well formed announce for an | 111 | A refused announce is answered over UDP with a well formed announce for an |
| 107 | empty swarm rather than with the error action. BEP 15 binds a client to the | 112 | 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 | |||
| 51 | return (peers - insert_point) / peer_size; | 51 | return (peers - insert_point) / peer_size; |
| 52 | } | 52 | } |
| 53 | 53 | ||
| 54 | /* Age one family's peers by timedout minutes. Frees the list and clears the | 54 | /* Age one family's peers by timedout minutes. Releases and zeroes the vector |
| 55 | slot once its last peer is gone, so an absent family costs nothing. */ | 55 | once its last peer is gone, so an empty family costs nothing. */ |
| 56 | static void clean_peer_list_family(ot_peerlist **slot, size_t peer_size, ot_time timedout) { | 56 | static void clean_family_vector(ot_vector *peer_vector, size_t peer_size, ot_time timedout, size_t *removed_seeders) { |
| 57 | ot_peerlist *peer_list = *slot; | 57 | ot_vector *bucket = peer_vector; |
| 58 | ot_vector *peer_vector; | 58 | size_t num_buckets = 1, peer_count; |
| 59 | size_t num_buckets = 1, removed_seeders = 0; | ||
| 60 | 59 | ||
| 61 | if (!peer_list) | 60 | if (OT_VECTOR_HASBUCKETS(peer_vector)) { |
| 62 | return; | ||
| 63 | |||
| 64 | peer_vector = &peer_list->peers; | ||
| 65 | if (OT_PEERLIST_HASBUCKETS(peer_list)) { | ||
| 66 | num_buckets = peer_vector->size; | 61 | num_buckets = peer_vector->size; |
| 67 | peer_vector = (ot_vector *)peer_vector->data; | 62 | bucket = (ot_vector *)peer_vector->data; |
| 68 | } | 63 | } |
| 69 | 64 | ||
| 70 | while (num_buckets--) { | 65 | while (num_buckets--) { |
| 71 | size_t removed_peers = clean_single_bucket(peer_vector->data, peer_vector->size, peer_size, timedout, &removed_seeders); | 66 | size_t removed_peers = clean_single_bucket(bucket->data, bucket->size, peer_size, timedout, removed_seeders); |
| 72 | peer_list->peer_count -= removed_peers; | 67 | bucket->size -= removed_peers; |
| 73 | peer_vector->size -= removed_peers; | ||
| 74 | if (removed_peers) | 68 | if (removed_peers) |
| 75 | vector_fixup_peers(peer_vector, peer_size); | 69 | vector_fixup_peers(bucket, peer_size); |
| 76 | 70 | ||
| 77 | /* Skip to next bucket, a vector containing peers */ | 71 | /* Skip to next bucket, a vector containing peers */ |
| 78 | ++peer_vector; | 72 | ++bucket; |
| 79 | } | 73 | } |
| 80 | 74 | ||
| 81 | peer_list->seed_count -= removed_seeders; | 75 | peer_count = vector_peer_count(peer_vector); |
| 82 | 76 | ||
| 83 | if (!peer_list->peer_count) { | 77 | /* Run dry: release the family (a collapsed bucket list or a plain vector) */ |
| 84 | free_peerlist(peer_list); | 78 | if (!peer_count) { |
| 85 | *slot = NULL; | 79 | free_peer_vector(peer_vector); |
| 80 | memset(peer_vector, 0, sizeof(*peer_vector)); | ||
| 86 | return; | 81 | return; |
| 87 | } | 82 | } |
| 88 | 83 | ||
| 89 | /* See if we need to convert the list from simple vector to bucket list */ | 84 | /* See if we need to convert the vector from simple to bucket list or back */ |
| 90 | if ((peer_list->peer_count > OT_PEER_BUCKET_MINCOUNT) || OT_PEERLIST_HASBUCKETS(peer_list)) | 85 | if ((peer_count > OT_PEER_BUCKET_MINCOUNT) || OT_VECTOR_HASBUCKETS(peer_vector)) |
| 91 | vector_redistribute_buckets(peer_list, peer_size); | 86 | vector_redistribute_buckets(peer_vector, peer_size, peer_count); |
| 92 | } | 87 | } |
| 93 | 88 | ||
| 94 | /* Clean a single torrent | 89 | /* Clean a single torrent |
| 95 | return 1 if torrent timed out | 90 | return 1 if torrent timed out |
| 96 | */ | 91 | */ |
| 97 | int clean_single_torrent(ot_torrent *torrent) { | 92 | int clean_single_torrent(ot_torrent *torrent) { |
| 98 | ot_time timedout = time_since_minutes(torrent->base); | 93 | ot_time timedout = time_since_minutes(torrent->base); |
| 94 | ot_peerlist *peer_list = torrent->peer_list; | ||
| 95 | size_t removed_seeders = 0; | ||
| 99 | 96 | ||
| 100 | /* Touched since the last sweep: nothing to do */ | 97 | /* Touched since the last sweep: nothing to do */ |
| 101 | if (!timedout) | 98 | if (!timedout) |
| @@ -107,7 +104,7 @@ int clean_single_torrent(ot_torrent *torrent) { | |||
| 107 | 104 | ||
| 108 | /* Already empty and nothing arrived before the peer timeout: keep it only | 105 | /* Already empty and nothing arrived before the peer timeout: keep it only |
| 109 | while a down count is worth remembering */ | 106 | while a down count is worth remembering */ |
| 110 | if (timedout > OT_PEER_TIMEOUT && !torrent->peer_list6 && !torrent->peer_list4) | 107 | if (timedout > OT_PEER_TIMEOUT && !peer_list) |
| 111 | return (torrent->down_count && timedout <= g_empty_torrent_timeout) ? 0 : 1; | 108 | return (torrent->down_count && timedout <= g_empty_torrent_timeout) ? 0 : 1; |
| 112 | 109 | ||
| 113 | /* Peers past the peer timeout are gone regardless, which caps how far the | 110 | /* Peers past the peer timeout are gone regardless, which caps how far the |
| @@ -115,10 +112,19 @@ int clean_single_torrent(ot_torrent *torrent) { | |||
| 115 | if (timedout > OT_PEER_TIMEOUT) | 112 | if (timedout > OT_PEER_TIMEOUT) |
| 116 | timedout = OT_PEER_TIMEOUT; | 113 | timedout = OT_PEER_TIMEOUT; |
| 117 | 114 | ||
| 118 | clean_peer_list_family(&torrent->peer_list6, OT_PEER_SIZE6, timedout); | 115 | if (peer_list) { |
| 119 | clean_peer_list_family(&torrent->peer_list4, OT_PEER_SIZE4, timedout); | 116 | clean_family_vector(&peer_list->peers6, OT_PEER_SIZE6, timedout, &removed_seeders); |
| 117 | clean_family_vector(&peer_list->peers4, OT_PEER_SIZE4, timedout, &removed_seeders); | ||
| 118 | peer_list->seed_count -= removed_seeders; | ||
| 119 | |||
| 120 | /* Both families gone: drop the peerlist, the torrent keeps only its count */ | ||
| 121 | if (!vector_peer_count(&peer_list->peers6) && !vector_peer_count(&peer_list->peers4)) { | ||
| 122 | free_peerlist(peer_list); | ||
| 123 | torrent->peer_list = peer_list = NULL; | ||
| 124 | } | ||
| 125 | } | ||
| 120 | 126 | ||
| 121 | if (torrent->peer_list6 || torrent->peer_list4) | 127 | if (peer_list) |
| 122 | torrent->base = time_now_minutes(); /* still carrying peers */ | 128 | torrent->base = time_now_minutes(); /* still carrying peers */ |
| 123 | else { | 129 | else { |
| 124 | /* Fell empty: hold base a peer timeout back so a later idle sweep makes | 130 | /* 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 | |||
| 90 | exactly that size */ | 90 | exactly that size */ |
| 91 | char *r = *cursor; | 91 | char *r = *cursor; |
| 92 | const char *r_end = r + OT_SCRAPE_MAXENTRYLEN; | 92 | const char *r_end = r + OT_SCRAPE_MAXENTRYLEN; |
| 93 | size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); | 93 | size_t seed_count = torrent_seed_count(torrent); |
| 94 | size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); | 94 | size_t peer_count = torrent_peer_count(torrent); |
| 95 | size_t down_count = torrent->down_count; | 95 | size_t down_count = torrent->down_count; |
| 96 | 96 | ||
| 97 | switch (mode & TASK_TASK_MASK) { | 97 | 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 | |||
| 243 | for (bucket = 0; bucket < OT_BUCKET_COUNT; ++bucket) { | 243 | for (bucket = 0; bucket < OT_BUCKET_COUNT; ++bucket) { |
| 244 | ot_vector *torrents_list = mutex_bucket_lock(bucket); | 244 | ot_vector *torrents_list = mutex_bucket_lock(bucket); |
| 245 | for (i = 0; i < torrents_list->size; ++i) { | 245 | for (i = 0; i < torrents_list->size; ++i) { |
| 246 | ot_peerlist *peer_list = (((ot_torrent *)(torrents_list->data))[i]).peer_list4; | 246 | ot_peerlist *peer_list = (((ot_torrent *)(torrents_list->data))[i]).peer_list; |
| 247 | ot_vector *bucket_list; | 247 | ot_vector *bucket_list; |
| 248 | int num_buckets = 1; | 248 | int num_buckets = 1; |
| 249 | 249 | ||
| 250 | if (!peer_list) | 250 | if (!peer_list) |
| 251 | continue; | 251 | continue; |
| 252 | bucket_list = &peer_list->peers; | 252 | bucket_list = &peer_list->peers4; /* /24 networks are an IPv4 notion */ |
| 253 | 253 | ||
| 254 | if (OT_PEERLIST_HASBUCKETS(peer_list)) { | 254 | if (OT_VECTOR_HASBUCKETS(bucket_list)) { |
| 255 | num_buckets = bucket_list->size; | 255 | num_buckets = bucket_list->size; |
| 256 | bucket_list = (ot_vector *)bucket_list->data; | 256 | bucket_list = (ot_vector *)bucket_list->data; |
| 257 | } | 257 | } |
| @@ -303,8 +303,8 @@ typedef struct { | |||
| 303 | static int torrent_statter(ot_torrent *torrent, uintptr_t data) { | 303 | static int torrent_statter(ot_torrent *torrent, uintptr_t data) { |
| 304 | torrent_stats *stats = (torrent_stats *)data; | 304 | torrent_stats *stats = (torrent_stats *)data; |
| 305 | stats->torrent_count++; | 305 | stats->torrent_count++; |
| 306 | stats->peer_count += peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); | 306 | stats->peer_count += torrent_peer_count(torrent); |
| 307 | stats->seed_count += peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); | 307 | stats->seed_count += torrent_seed_count(torrent); |
| 308 | return 0; | 308 | return 0; |
| 309 | } | 309 | } |
| 310 | 310 | ||
| @@ -347,8 +347,8 @@ void stats_top_txt(char **reply, const char *reply_end, size_t amount) { | |||
| 347 | ot_vector *torrents_list = mutex_bucket_lock(bucket); | 347 | ot_vector *torrents_list = mutex_bucket_lock(bucket); |
| 348 | for (j = 0; j < torrents_list->size; ++j) { | 348 | for (j = 0; j < torrents_list->size; ++j) { |
| 349 | ot_torrent *torrent = (ot_torrent *)(torrents_list->data) + j; | 349 | ot_torrent *torrent = (ot_torrent *)(torrents_list->data) + j; |
| 350 | size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); | 350 | size_t peer_count = torrent_peer_count(torrent); |
| 351 | size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); | 351 | size_t seed_count = torrent_seed_count(torrent); |
| 352 | size_t leech_count = peer_count - seed_count; | 352 | size_t leech_count = peer_count - seed_count; |
| 353 | 353 | ||
| 354 | stats_insert_into_highscore(peer_count, top100c, amount, &torrent->hash); | 354 | 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) { | |||
| 160 | 160 | ||
| 161 | end = ((ot_torrent *)vector->data) + vector->size; | 161 | end = ((ot_torrent *)vector->data) + vector->size; |
| 162 | 162 | ||
| 163 | free_peerlist(match->peer_list6); | 163 | free_peerlist(match->peer_list); |
| 164 | free_peerlist(match->peer_list4); | ||
| 165 | 164 | ||
| 166 | memmove(match, match + 1, sizeof(ot_torrent) * (end - match - 1)); | 165 | memmove(match, match + 1, sizeof(ot_torrent) * (end - match - 1)); |
| 167 | if ((--vector->size * OT_VECTOR_SHRINK_THRESH < vector->space) && (vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS)) { | 166 | 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) { | |||
| 180 | return; | 179 | return; |
| 181 | } | 180 | } |
| 182 | 181 | ||
| 183 | void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { | 182 | void vector_redistribute_buckets(ot_vector *peer_vector, size_t peer_size, size_t peer_count) { |
| 184 | size_t bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; | 183 | size_t bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; |
| 185 | ot_vector *bucket_list_new, *bucket_list_old = &peer_list->peers; | 184 | ot_vector *bucket_list_new, *bucket_list_old = peer_vector; |
| 186 | int (*sort_func)(const void *, const void *) = peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4; | 185 | int (*sort_func)(const void *, const void *) = peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4; |
| 187 | 186 | ||
| 188 | if (OT_PEERLIST_HASBUCKETS(peer_list)) { | 187 | if (OT_VECTOR_HASBUCKETS(peer_vector)) { |
| 189 | num_buckets_old = peer_list->peers.size; | 188 | num_buckets_old = peer_vector->size; |
| 190 | bucket_list_old = peer_list->peers.data; | 189 | bucket_list_old = peer_vector->data; |
| 191 | } | 190 | } |
| 192 | 191 | ||
| 193 | if (peer_list->peer_count < 255) | 192 | if (peer_count < 255) |
| 194 | num_buckets_new = 1; | 193 | num_buckets_new = 1; |
| 195 | else if (peer_list->peer_count > 8192) | 194 | else if (peer_count > 8192) |
| 196 | num_buckets_new = 64; | 195 | num_buckets_new = 64; |
| 197 | else if (peer_list->peer_count >= 512 && peer_list->peer_count < 4096) | 196 | else if (peer_count >= 512 && peer_count < 4096) |
| 198 | num_buckets_new = 16; | 197 | num_buckets_new = 16; |
| 199 | else if (peer_list->peer_count < 512 && num_buckets_old <= 16) | 198 | else if (peer_count < 512 && num_buckets_old <= 16) |
| 200 | num_buckets_new = num_buckets_old; | 199 | num_buckets_new = num_buckets_old; |
| 201 | else if (peer_list->peer_count < 512) | 200 | else if (peer_count < 512) |
| 202 | num_buckets_new = 1; | 201 | num_buckets_new = 1; |
| 203 | else if (peer_list->peer_count < 8192 && num_buckets_old > 1) | 202 | else if (peer_count < 8192 && num_buckets_old > 1) |
| 204 | num_buckets_new = num_buckets_old; | 203 | num_buckets_new = num_buckets_old; |
| 205 | else | 204 | else |
| 206 | num_buckets_new = 16; | 205 | num_buckets_new = 16; |
| @@ -214,7 +213,7 @@ void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { | |||
| 214 | return; | 213 | return; |
| 215 | 214 | ||
| 216 | bucket_size_new = OT_VECTOR_MIN_MEMBERS; | 215 | bucket_size_new = OT_VECTOR_MIN_MEMBERS; |
| 217 | while (bucket_size_new * num_buckets_new < peer_list->peer_count) | 216 | while (bucket_size_new * num_buckets_new < peer_count) |
| 218 | bucket_size_new *= OT_VECTOR_GROW_RATIO; | 217 | bucket_size_new *= OT_VECTOR_GROW_RATIO; |
| 219 | 218 | ||
| 220 | /* preallocate vectors to hold all peers */ | 219 | /* preallocate vectors to hold all peers */ |
| @@ -253,20 +252,20 @@ void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { | |||
| 253 | for (bucket = 0; bucket < num_buckets_new; ++bucket) | 252 | for (bucket = 0; bucket < num_buckets_new; ++bucket) |
| 254 | qsort(bucket_list_new[bucket].data, bucket_list_new[bucket].size, peer_size, sort_func); | 253 | qsort(bucket_list_new[bucket].data, bucket_list_new[bucket].size, peer_size, sort_func); |
| 255 | 254 | ||
| 256 | /* Everything worked fine. Now link new bucket_list to peer_list */ | 255 | /* Everything worked fine. Now link new bucket_list to the vector */ |
| 257 | if (OT_PEERLIST_HASBUCKETS(peer_list)) | 256 | if (OT_VECTOR_HASBUCKETS(peer_vector)) |
| 258 | vector_clean_list((ot_vector *)peer_list->peers.data, peer_list->peers.size); | 257 | vector_clean_list((ot_vector *)peer_vector->data, peer_vector->size); |
| 259 | else | 258 | else |
| 260 | free(peer_list->peers.data); | 259 | free(peer_vector->data); |
| 261 | 260 | ||
| 262 | if (num_buckets_new > 1) { | 261 | if (num_buckets_new > 1) { |
| 263 | peer_list->peers.data = bucket_list_new; | 262 | peer_vector->data = bucket_list_new; |
| 264 | peer_list->peers.size = num_buckets_new; | 263 | peer_vector->size = num_buckets_new; |
| 265 | peer_list->peers.space = 0; /* Magic marker for "is list of buckets" */ | 264 | peer_vector->space = 0; /* Magic marker for "is list of buckets" */ |
| 266 | } else { | 265 | } else { |
| 267 | peer_list->peers.data = bucket_list_new->data; | 266 | peer_vector->data = bucket_list_new->data; |
| 268 | peer_list->peers.size = bucket_list_new->size; | 267 | peer_vector->size = bucket_list_new->size; |
| 269 | peer_list->peers.space = bucket_list_new->space; | 268 | peer_vector->space = bucket_list_new->space; |
| 270 | free(bucket_list_new); | 269 | free(bucket_list_new); |
| 271 | } | 270 | } |
| 272 | } | 271 | } |
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_ | |||
| 32 | void vector_remove_torrent(ot_vector *vector, ot_torrent *match); | 32 | void vector_remove_torrent(ot_vector *vector, ot_torrent *match); |
| 33 | 33 | ||
| 34 | /* For ot_clean.c */ | 34 | /* For ot_clean.c */ |
| 35 | void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size); | 35 | void vector_redistribute_buckets(ot_vector *peer_vector, size_t peer_size, size_t peer_count); |
| 36 | void vector_fixup_peers(ot_vector *vector, size_t peer_size); | 36 | void vector_fixup_peers(ot_vector *vector, size_t peer_size); |
| 37 | void vector_clean_list(ot_vector *vector, size_t num_buckets); | 37 | void vector_clean_list(ot_vector *vector, size_t num_buckets); |
| 38 | 38 | ||
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 @@ | |||
| 28 | /* Forward declaration */ | 28 | /* Forward declaration */ |
| 29 | size_t return_peers_for_torrent(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply, PROTO_FLAG proto); | 29 | size_t return_peers_for_torrent(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply, PROTO_FLAG proto); |
| 30 | 30 | ||
| 31 | void free_peer_vector(ot_vector *peer_vector) { | ||
| 32 | if (OT_VECTOR_HASBUCKETS(peer_vector)) | ||
| 33 | vector_clean_list((ot_vector *)peer_vector->data, peer_vector->size); | ||
| 34 | else | ||
| 35 | free(peer_vector->data); /* free(NULL) on an absent family is fine */ | ||
| 36 | } | ||
| 37 | |||
| 31 | void free_peerlist(ot_peerlist *peer_list) { | 38 | void free_peerlist(ot_peerlist *peer_list) { |
| 32 | if (peer_list && peer_list->peers.data) { | 39 | if (!peer_list) |
| 33 | if (OT_PEERLIST_HASBUCKETS(peer_list)) | 40 | return; |
| 34 | vector_clean_list((ot_vector *)peer_list->peers.data, peer_list->peers.size); | 41 | free_peer_vector(&peer_list->peers6); |
| 35 | else | 42 | free_peer_vector(&peer_list->peers4); |
| 36 | free(peer_list->peers.data); | ||
| 37 | } | ||
| 38 | free(peer_list); | 43 | free(peer_list); |
| 39 | } | 44 | } |
| 40 | 45 | ||
| @@ -113,20 +118,17 @@ size_t add_peer_to_torrent_and_return_peers(PROTO_FLAG proto, struct ot_workstru | |||
| 113 | 118 | ||
| 114 | torrent->base = time_now_minutes(); | 119 | torrent->base = time_now_minutes(); |
| 115 | 120 | ||
| 116 | /* The announcing peer's family list is created on first use */ | 121 | /* The peerlist, holding both families, is created on the first peer */ |
| 117 | { | 122 | if (!torrent->peer_list && !(torrent->peer_list = calloc(1, sizeof(ot_peerlist)))) { |
| 118 | ot_peerlist **slot = peer_size == OT_PEER_SIZE6 ? &torrent->peer_list6 : &torrent->peer_list4; | 123 | if (delta_torrentcount) |
| 119 | if (!*slot && !(*slot = calloc(1, sizeof(ot_peerlist)))) { | 124 | vector_remove_torrent(torrents_list, torrent); |
| 120 | if (delta_torrentcount) | 125 | mutex_bucket_unlock_by_hash(*ws->hash, 0); |
| 121 | vector_remove_torrent(torrents_list, torrent); | 126 | return 0; |
| 122 | mutex_bucket_unlock_by_hash(*ws->hash, 0); | ||
| 123 | return 0; | ||
| 124 | } | ||
| 125 | peer_list = *slot; | ||
| 126 | } | 127 | } |
| 128 | peer_list = torrent->peer_list; | ||
| 127 | 129 | ||
| 128 | /* Check for peer in torrent */ | 130 | /* Check for peer in its family's vector */ |
| 129 | peer_dest = vector_find_or_insert_peer(&(peer_list->peers), peer_src, peer_size, &exactmatch); | 131 | peer_dest = vector_find_or_insert_peer(peer_size == OT_PEER_SIZE6 ? &peer_list->peers6 : &peer_list->peers4, peer_src, peer_size, &exactmatch); |
| 130 | if (!peer_dest) { | 132 | if (!peer_dest) { |
| 131 | mutex_bucket_unlock_by_hash(*ws->hash, delta_torrentcount); | 133 | mutex_bucket_unlock_by_hash(*ws->hash, delta_torrentcount); |
| 132 | return 0; | 134 | return 0; |
| @@ -149,7 +151,6 @@ size_t add_peer_to_torrent_and_return_peers(PROTO_FLAG proto, struct ot_workstru | |||
| 149 | livesync_tell(ws); | 151 | livesync_tell(ws); |
| 150 | #endif | 152 | #endif |
| 151 | 153 | ||
| 152 | peer_list->peer_count++; | ||
| 153 | if (OT_PEERFLAG(ws->peer) & PEER_FLAG_COMPLETED) { | 154 | if (OT_PEERFLAG(ws->peer) & PEER_FLAG_COMPLETED) { |
| 154 | torrent->down_count++; | 155 | torrent->down_count++; |
| 155 | stats_issue_event(ws, EVENT_COMPLETED, 0, 0); | 156 | 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 | |||
| 198 | return ws->reply_size; | 199 | return ws->reply_size; |
| 199 | } | 200 | } |
| 200 | 201 | ||
| 201 | static size_t return_peers_all(ot_peerlist *peer_list, size_t peer_size, char *reply) { | 202 | static size_t return_peers_all(ot_vector *peer_vector, size_t peer_size, size_t peer_count, char *reply) { |
| 202 | size_t bucket, num_buckets = 1; | 203 | size_t bucket, num_buckets = 1; |
| 203 | ot_vector *bucket_list = &peer_list->peers; | 204 | ot_vector *bucket_list = peer_vector; |
| 204 | size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); | 205 | size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); |
| 205 | size_t result = compare_size * peer_list->peer_count; | 206 | size_t result = compare_size * peer_count; |
| 206 | char *r_end = reply + result; | 207 | char *r_end = reply + result; |
| 207 | 208 | ||
| 208 | if (OT_PEERLIST_HASBUCKETS(peer_list)) { | 209 | if (OT_VECTOR_HASBUCKETS(peer_vector)) { |
| 209 | num_buckets = bucket_list->size; | 210 | num_buckets = bucket_list->size; |
| 210 | bucket_list = (ot_vector *)bucket_list->data; | 211 | bucket_list = (ot_vector *)bucket_list->data; |
| 211 | } | 212 | } |
| @@ -227,17 +228,17 @@ static size_t return_peers_all(ot_peerlist *peer_list, size_t peer_size, char *r | |||
| 227 | return result; | 228 | return result; |
| 228 | } | 229 | } |
| 229 | 230 | ||
| 230 | static size_t return_peers_selection(struct ot_workstruct *ws, ot_peerlist *peer_list, size_t peer_size, size_t amount, char *reply) { | 231 | 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) { |
| 231 | size_t bucket_offset, bucket_index = 0, num_buckets = 1; | 232 | size_t bucket_offset, bucket_index = 0, num_buckets = 1; |
| 232 | ot_vector *bucket_list = &peer_list->peers; | 233 | ot_vector *bucket_list = peer_vector; |
| 233 | unsigned int shifted_pc = peer_list->peer_count; | 234 | unsigned int shifted_pc = peer_count; |
| 234 | unsigned int shifted_step = 0; | 235 | unsigned int shifted_step = 0; |
| 235 | unsigned int shift = 0; | 236 | unsigned int shift = 0; |
| 236 | size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); | 237 | size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); |
| 237 | size_t result = compare_size * amount; | 238 | size_t result = compare_size * amount; |
| 238 | char *r_end = reply + result; | 239 | char *r_end = reply + result; |
| 239 | 240 | ||
| 240 | if (OT_PEERLIST_HASBUCKETS(peer_list)) { | 241 | if (OT_VECTOR_HASBUCKETS(peer_vector)) { |
| 241 | num_buckets = bucket_list->size; | 242 | num_buckets = bucket_list->size; |
| 242 | bucket_list = (ot_vector *)bucket_list->data; | 243 | bucket_list = (ot_vector *)bucket_list->data; |
| 243 | } | 244 | } |
| @@ -253,7 +254,7 @@ static size_t return_peers_selection(struct ot_workstruct *ws, ot_peerlist *peer | |||
| 253 | 254 | ||
| 254 | /* Initialize somewhere in the middle of peers so that | 255 | /* Initialize somewhere in the middle of peers so that |
| 255 | fixpoint's aliasing doesn't alway miss the same peers */ | 256 | fixpoint's aliasing doesn't alway miss the same peers */ |
| 256 | bucket_offset = nrand48(ws->rand48_state) % peer_list->peer_count; | 257 | bucket_offset = nrand48(ws->rand48_state) % peer_count; |
| 257 | 258 | ||
| 258 | while (amount--) { | 259 | while (amount--) { |
| 259 | ot_peer *peer; | 260 | ot_peer *peer; |
| @@ -281,10 +282,11 @@ static size_t return_peers_selection(struct ot_workstruct *ws, ot_peerlist *peer | |||
| 281 | static size_t return_peers_for_torrent_udp(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply) { | 282 | static size_t return_peers_for_torrent_udp(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply) { |
| 282 | char *r = reply; | 283 | char *r = reply; |
| 283 | size_t peer_size = peer_size_from_peer6(&ws->peer); | 284 | size_t peer_size = peer_size_from_peer6(&ws->peer); |
| 284 | ot_peerlist *peer_list = peer_size == OT_PEER_SIZE6 ? torrent->peer_list6 : torrent->peer_list4; | 285 | ot_peerlist *peer_list = torrent->peer_list; |
| 285 | size_t list_count = peerlist_peer_count(peer_list); | 286 | ot_vector *family = peer_size == OT_PEER_SIZE6 ? &peer_list->peers6 : &peer_list->peers4; |
| 286 | size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); | 287 | size_t list_count = vector_peer_count(family); |
| 287 | size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); | 288 | size_t peer_count = torrent_peer_count(torrent); |
| 289 | size_t seed_count = torrent_seed_count(torrent); | ||
| 288 | 290 | ||
| 289 | if (amount > list_count) | 291 | if (amount > list_count) |
| 290 | amount = list_count; | 292 | amount = list_count; |
| @@ -296,9 +298,9 @@ static size_t return_peers_for_torrent_udp(struct ot_workstruct *ws, ot_torrent | |||
| 296 | 298 | ||
| 297 | if (amount) { | 299 | if (amount) { |
| 298 | if (amount == list_count) | 300 | if (amount == list_count) |
| 299 | r += return_peers_all(peer_list, peer_size, r); | 301 | r += return_peers_all(family, peer_size, list_count, r); |
| 300 | else | 302 | else |
| 301 | r += return_peers_selection(ws, peer_list, peer_size, amount, r); | 303 | r += return_peers_selection(ws, family, peer_size, amount, list_count, r); |
| 302 | } | 304 | } |
| 303 | return r - reply; | 305 | return r - reply; |
| 304 | } | 306 | } |
| @@ -307,9 +309,10 @@ static size_t return_peers_for_torrent_tcp(struct ot_workstruct *ws, ot_torrent | |||
| 307 | char *r = reply; | 309 | char *r = reply; |
| 308 | const char *r_end = ws->outbuf + G_OUTBUF_SIZE; | 310 | const char *r_end = ws->outbuf + G_OUTBUF_SIZE; |
| 309 | int erval = OT_CLIENT_REQUEST_INTERVAL_RANDOM; | 311 | int erval = OT_CLIENT_REQUEST_INTERVAL_RANDOM; |
| 310 | size_t count6 = peerlist_peer_count(torrent->peer_list6); | 312 | ot_peerlist *peer_list = torrent->peer_list; |
| 311 | size_t count4 = peerlist_peer_count(torrent->peer_list4); | 313 | size_t count6 = vector_peer_count(&peer_list->peers6); |
| 312 | size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); | 314 | size_t count4 = vector_peer_count(&peer_list->peers4); |
| 315 | size_t seed_count = peer_list->seed_count; | ||
| 313 | size_t down_count = torrent->down_count; | 316 | size_t down_count = torrent->down_count; |
| 314 | size_t peer_count = count6 + count4 - seed_count; | 317 | size_t peer_count = count6 + count4 - seed_count; |
| 315 | 318 | ||
| @@ -355,17 +358,17 @@ static size_t return_peers_for_torrent_tcp(struct ot_workstruct *ws, ot_torrent | |||
| 355 | if (amount_v4) { | 358 | if (amount_v4) { |
| 356 | fmt_append(&r, r_end, PEERS_BENCODED4 "%zd:", OT_PEER_COMPARE_SIZE4 * amount_v4); | 359 | fmt_append(&r, r_end, PEERS_BENCODED4 "%zd:", OT_PEER_COMPARE_SIZE4 * amount_v4); |
| 357 | if (amount_v4 == count4) | 360 | if (amount_v4 == count4) |
| 358 | r += return_peers_all(torrent->peer_list4, OT_PEER_SIZE4, r); | 361 | r += return_peers_all(&peer_list->peers4, OT_PEER_SIZE4, count4, r); |
| 359 | else | 362 | else |
| 360 | r += return_peers_selection(ws, torrent->peer_list4, OT_PEER_SIZE4, amount_v4, r); | 363 | r += return_peers_selection(ws, &peer_list->peers4, OT_PEER_SIZE4, amount_v4, count4, r); |
| 361 | } | 364 | } |
| 362 | 365 | ||
| 363 | if (amount_v6) { | 366 | if (amount_v6) { |
| 364 | fmt_append(&r, r_end, PEERS_BENCODED6 "%zd:", OT_PEER_COMPARE_SIZE6 * amount_v6); | 367 | fmt_append(&r, r_end, PEERS_BENCODED6 "%zd:", OT_PEER_COMPARE_SIZE6 * amount_v6); |
| 365 | if (amount_v6 == count6) | 368 | if (amount_v6 == count6) |
| 366 | r += return_peers_all(torrent->peer_list6, OT_PEER_SIZE6, r); | 369 | r += return_peers_all(&peer_list->peers6, OT_PEER_SIZE6, count6, r); |
| 367 | else | 370 | else |
| 368 | r += return_peers_selection(ws, torrent->peer_list6, OT_PEER_SIZE6, amount_v6, r); | 371 | r += return_peers_selection(ws, &peer_list->peers6, OT_PEER_SIZE6, amount_v6, count6, r); |
| 369 | } | 372 | } |
| 370 | 373 | ||
| 371 | fmt_append(&r, r_end, "e"); | 374 | fmt_append(&r, r_end, "e"); |
| @@ -401,9 +404,9 @@ size_t return_udp_scrape_for_torrent(ot_hash const hash, char *reply) { | |||
| 401 | memset(reply, 0, 12); | 404 | memset(reply, 0, 12); |
| 402 | delta_torrentcount = -1; | 405 | delta_torrentcount = -1; |
| 403 | } else { | 406 | } else { |
| 404 | r[0] = htonl(peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4)); | 407 | r[0] = htonl(torrent_seed_count(torrent)); |
| 405 | r[1] = htonl(torrent->down_count); | 408 | r[1] = htonl(torrent->down_count); |
| 406 | 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)); | 409 | r[2] = htonl(torrent_peer_count(torrent) - torrent_seed_count(torrent)); |
| 407 | } | 410 | } |
| 408 | } | 411 | } |
| 409 | mutex_bucket_unlock_by_hash(hash, delta_torrentcount); | 412 | 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 | |||
| 430 | } else { | 433 | } else { |
| 431 | fmt_append(reply, reply_end, "20:"); | 434 | fmt_append(reply, reply_end, "20:"); |
| 432 | fmt_bytes(reply, reply_end, hash, sizeof(ot_hash)); | 435 | fmt_bytes(reply, reply_end, hash, sizeof(ot_hash)); |
| 433 | size_t seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); | 436 | size_t seed_count = torrent_seed_count(torrent); |
| 434 | size_t peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); | 437 | size_t peer_count = torrent_peer_count(torrent); |
| 435 | fmt_append(reply, reply_end, "d8:completei%zde10:downloadedi%zde10:incompletei%zdee", seed_count, (size_t)torrent->down_count, peer_count - seed_count); | 438 | fmt_append(reply, reply_end, "d8:completei%zde10:downloadedi%zde10:incompletei%zdee", seed_count, (size_t)torrent->down_count, peer_count - seed_count); |
| 436 | } | 439 | } |
| 437 | } | 440 | } |
| @@ -441,12 +444,10 @@ void return_tcp_scrape_for_torrent(ot_hash const *hash_list, size_t amount, char | |||
| 441 | fmt_append(reply, reply_end, "ee"); | 444 | fmt_append(reply, reply_end, "ee"); |
| 442 | } | 445 | } |
| 443 | 446 | ||
| 444 | static ot_peerlist dummy_list; | ||
| 445 | size_t remove_peer_from_torrent(PROTO_FLAG proto, struct ot_workstruct *ws) { | 447 | size_t remove_peer_from_torrent(PROTO_FLAG proto, struct ot_workstruct *ws) { |
| 446 | int exactmatch; | 448 | int exactmatch; |
| 447 | ot_vector *torrents_list = mutex_bucket_lock_by_hash(*ws->hash); | 449 | ot_vector *torrents_list = mutex_bucket_lock_by_hash(*ws->hash); |
| 448 | ot_torrent *torrent = vector_binary_search(ws->hash, torrents_list->data, torrents_list->size, sizeof(ot_torrent), OT_HASH_COMPARE_SIZE, &exactmatch); | 450 | ot_torrent *torrent = vector_binary_search(ws->hash, torrents_list->data, torrents_list->size, sizeof(ot_torrent), OT_HASH_COMPARE_SIZE, &exactmatch); |
| 449 | ot_peerlist *peer_list = &dummy_list; | ||
| 450 | size_t peer_size; /* initialized in next line */ | 451 | size_t peer_size; /* initialized in next line */ |
| 451 | ot_peer const *peer_src = peer_from_peer6(&ws->peer, &peer_size); | 452 | ot_peer const *peer_src = peer_from_peer6(&ws->peer, &peer_size); |
| 452 | size_t peer_count = 0, seed_count = 0; | 453 | 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) { | |||
| 458 | } | 459 | } |
| 459 | #endif | 460 | #endif |
| 460 | 461 | ||
| 461 | if (exactmatch) { | 462 | if (exactmatch && torrent->peer_list) { |
| 462 | peer_list = peer_size == OT_PEER_SIZE6 ? torrent->peer_list6 : torrent->peer_list4; | 463 | ot_vector *family = peer_size == OT_PEER_SIZE6 ? &torrent->peer_list->peers6 : &torrent->peer_list->peers4; |
| 463 | if (peer_list) { | 464 | if (vector_remove_peer(family, peer_src, peer_size) == 2) |
| 464 | switch (vector_remove_peer(&peer_list->peers, peer_src, peer_size)) { | 465 | torrent->peer_list->seed_count--; |
| 465 | case 2: | ||
| 466 | peer_list->seed_count--; /* Intentional fallthrough */ | ||
| 467 | case 1: | ||
| 468 | peer_list->peer_count--; /* Intentional fallthrough */ | ||
| 469 | default: | ||
| 470 | break; | ||
| 471 | } | ||
| 472 | } | ||
| 473 | 466 | ||
| 474 | peer_count = peerlist_peer_count(torrent->peer_list6) + peerlist_peer_count(torrent->peer_list4); | 467 | peer_count = torrent_peer_count(torrent); |
| 475 | seed_count = peerlist_seed_count(torrent->peer_list6) + peerlist_seed_count(torrent->peer_list4); | 468 | seed_count = torrent_seed_count(torrent); |
| 476 | } | 469 | } |
| 477 | 470 | ||
| 478 | if (proto == FLAG_TCP) { | 471 | if (proto == FLAG_TCP) { |
| @@ -621,8 +614,7 @@ void trackerlogic_deinit(void) { | |||
| 621 | if (torrents_list->size) { | 614 | if (torrents_list->size) { |
| 622 | for (j = 0; j < torrents_list->size; ++j) { | 615 | for (j = 0; j < torrents_list->size; ++j) { |
| 623 | ot_torrent *torrent = ((ot_torrent *)(torrents_list->data)) + j; | 616 | ot_torrent *torrent = ((ot_torrent *)(torrents_list->data)) + j; |
| 624 | free_peerlist(torrent->peer_list6); | 617 | free_peerlist(torrent->peer_list); |
| 625 | free_peerlist(torrent->peer_list4); | ||
| 626 | delta_torrentcount -= 1; | 618 | delta_torrentcount -= 1; |
| 627 | } | 619 | } |
| 628 | free(torrents_list->data); | 620 | 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; | |||
| 170 | typedef struct ot_peerlist ot_peerlist; | 170 | typedef struct ot_peerlist ot_peerlist; |
| 171 | typedef struct { | 171 | typedef struct { |
| 172 | ot_hash hash; | 172 | ot_hash hash; |
| 173 | ot_peerlist *peer_list6; /* NULL until the torrent has a v6 peer */ | 173 | ot_peerlist *peer_list; /* NULL until the torrent has a peer in either family */ |
| 174 | ot_peerlist *peer_list4; /* NULL until the torrent has a v4 peer */ | 174 | uint32_t base; /* epoch minutes, when the torrent was last cleaned */ |
| 175 | uint32_t base; /* minutes, when the torrent was last cleaned */ | 175 | uint32_t down_count; /* completed events */ |
| 176 | uint32_t down_count; /* completed events, summed over both families */ | ||
| 177 | } ot_torrent; | 176 | } ot_torrent; |
| 178 | 177 | ||
| 179 | #include "ot_vector.h" | 178 | #include "ot_vector.h" |
| 180 | 179 | ||
| 181 | struct ot_peerlist { | 180 | struct ot_peerlist { |
| 182 | uint32_t seed_count; | 181 | uint32_t seed_count; |
| 183 | uint32_t peer_count; | 182 | /* each family's peers: a normal vector, or a pointer to ot_vector[] buckets |
| 184 | /* normal peers vector or | 183 | when data != NULL and space == 0 (size then holds the bucket count) */ |
| 185 | pointer to ot_vector[32] buckets if data != NULL and space == 0 | 184 | ot_vector peers6; |
| 186 | */ | 185 | ot_vector peers4; |
| 187 | ot_vector peers; | ||
| 188 | }; | 186 | }; |
| 189 | #define OT_PEERLIST_HASBUCKETS(peer_list) ((peer_list)->peers.size > (peer_list)->peers.space) | ||
| 190 | 187 | ||
| 191 | static inline uint32_t peerlist_peer_count(const ot_peerlist *peer_list) { return peer_list ? peer_list->peer_count : 0; } | 188 | /* A peer vector becomes a bucket list of peer vectors, marker is size > space (usually 0) */ |
| 192 | static inline uint32_t peerlist_seed_count(const ot_peerlist *peer_list) { return peer_list ? peer_list->seed_count : 0; } | 189 | #define OT_VECTOR_HASBUCKETS(v) ((v)->size > (v)->space) |
| 190 | |||
| 191 | /* Peers in one family: a plain vector's size is the count, a bucket list's is | ||
| 192 | the sum of its buckets. O(1) for the small torrents that dominate a table. */ | ||
| 193 | static inline size_t vector_peer_count(const ot_vector *v) { | ||
| 194 | const ot_vector *b; | ||
| 195 | size_t n, total = 0; | ||
| 196 | if (!OT_VECTOR_HASBUCKETS(v)) | ||
| 197 | return v->size; | ||
| 198 | b = (const ot_vector *)v->data; | ||
| 199 | for (n = 0; n < v->size; ++n) | ||
| 200 | total += b[n].size; | ||
| 201 | return total; | ||
| 202 | } | ||
| 203 | static inline size_t torrent_peer_count(const ot_torrent *t) { | ||
| 204 | return t->peer_list ? vector_peer_count(&t->peer_list->peers6) + vector_peer_count(&t->peer_list->peers4) : 0; | ||
| 205 | } | ||
| 206 | static inline uint32_t torrent_seed_count(const ot_torrent *t) { return t->peer_list ? t->peer_list->seed_count : 0; } | ||
| 193 | 207 | ||
| 194 | /* The http replies the tracker counts when it has to refuse a request. */ | 208 | /* The http replies the tracker counts when it has to refuse a request. */ |
| 195 | enum { | 209 | enum { |
| @@ -314,5 +328,6 @@ void iterate_all_torrents(int (*for_each)(ot_torrent *torrent, uintptr_t data), | |||
| 314 | 328 | ||
| 315 | /* Helper, before it moves to its own object */ | 329 | /* Helper, before it moves to its own object */ |
| 316 | void free_peerlist(ot_peerlist *peer_list); | 330 | void free_peerlist(ot_peerlist *peer_list); |
| 331 | void free_peer_vector(ot_vector *peer_vector); | ||
| 317 | 332 | ||
| 318 | #endif | 333 | #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 | |||
| 33 | add_peer_to_torrent_and_return_peers(FLAG_TCP, ws, 0); | 33 | add_peer_to_torrent_and_return_peers(FLAG_TCP, ws, 0); |
| 34 | } | 34 | } |
| 35 | 35 | ||
| 36 | /* A distinct v4 peer addressed by two octets, to build swarms past 256 */ | ||
| 37 | static size_t announce_wide(struct ot_workstruct *ws, ot_hash *hash, unsigned int which, size_t amount) { | ||
| 38 | static const uint8_t v4mapped[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff, 0xff}; | ||
| 39 | |||
| 40 | ws->reply = ws->outbuf; | ||
| 41 | memset(&ws->peer, 0, sizeof(ws->peer)); | ||
| 42 | memcpy(&ws->peer, v4mapped, sizeof(v4mapped)); | ||
| 43 | ((uint8_t *)&ws->peer)[14] = (uint8_t)(which >> 8); | ||
| 44 | ((uint8_t *)&ws->peer)[15] = (uint8_t)which; | ||
| 45 | OT_SETPORT(&ws->peer, &(uint16_t){6881}); | ||
| 46 | ws->hash = hash; | ||
| 47 | return add_peer_to_torrent_and_return_peers(FLAG_TCP, ws, amount); | ||
| 48 | } | ||
| 49 | |||
| 36 | static size_t peers_in(ot_hash *hash) { | 50 | static size_t peers_in(ot_hash *hash) { |
| 37 | char reply[1024]; | 51 | char reply[1024]; |
| 38 | size_t len = return_udp_scrape_for_torrent(*hash, reply); | 52 | 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) { | |||
| 157 | workstruct_deinit(&ws); | 171 | workstruct_deinit(&ws); |
| 158 | } | 172 | } |
| 159 | 173 | ||
| 174 | static void case_a_bucketed_swarm_survives_clean_and_serves(void) { | ||
| 175 | struct ot_workstruct ws; | ||
| 176 | ot_hash hash; | ||
| 177 | ot_torrent *torrent; | ||
| 178 | unsigned int i; | ||
| 179 | const unsigned int n = 600; /* past OT_PEER_BUCKET_MINCOUNT (512) */ | ||
| 180 | |||
| 181 | test_case("a swarm large enough to be bucketed cleans, splits and serves without loss"); | ||
| 182 | memset(hash, 0x34, sizeof(hash)); | ||
| 183 | CHECK_INT(workstruct_init(&ws, G_INBUF_SIZE), 0); | ||
| 184 | |||
| 185 | for (i = 0; i < n; ++i) | ||
| 186 | announce_wide(&ws, &hash, i, 0); | ||
| 187 | CHECK_INT(peers_in(&hash), n); | ||
| 188 | |||
| 189 | torrent = torrent_of(&hash); | ||
| 190 | CHECK(torrent != NULL); | ||
| 191 | CHECK(torrent->peer_list != NULL); | ||
| 192 | |||
| 193 | /* A clean with a minute elapsed splits the flat vector into buckets */ | ||
| 194 | step_clock_back(torrent, -1); | ||
| 195 | CHECK_INT(clean_single_torrent(torrent), 0); | ||
| 196 | CHECK(torrent->peer_list != NULL); | ||
| 197 | CHECK_INT(OT_VECTOR_HASBUCKETS(&torrent->peer_list->peers4), 1); | ||
| 198 | CHECK_INT(peers_in(&hash), n); | ||
| 199 | |||
| 200 | /* Serve a selection back, which walks the bucket list */ | ||
| 201 | CHECK(announce_wide(&ws, &hash, 1, 200) > 0); | ||
| 202 | CHECK_INT(peers_in(&hash), n); | ||
| 203 | |||
| 204 | workstruct_deinit(&ws); | ||
| 205 | } | ||
| 206 | |||
| 160 | void test_clean(void) { | 207 | void test_clean(void) { |
| 161 | sigset_t hup; | 208 | sigset_t hup; |
| 162 | 209 | ||
| @@ -170,5 +217,6 @@ void test_clean(void) { | |||
| 170 | case_a_clock_that_went_back_keeps_the_swarm(); | 217 | case_a_clock_that_went_back_keeps_the_swarm(); |
| 171 | case_an_idle_swarm_still_ages_out(); | 218 | case_an_idle_swarm_still_ages_out(); |
| 172 | case_empty_torrent_timeout_bounds_a_counter_only_torrent(); | 219 | case_empty_torrent_timeout_bounds_a_counter_only_torrent(); |
| 220 | case_a_bucketed_swarm_survives_clean_and_serves(); | ||
| 173 | trackerlogic_deinit(); | 221 | trackerlogic_deinit(); |
| 174 | } | 222 | } |
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) { | |||
| 200 | into the first address byte, so the peers are distinct but arrive in no | 200 | into the first address byte, so the peers are distinct but arrive in no |
| 201 | particular order: a list generated in ascending order would come back | 201 | particular order: a list generated in ascending order would come back |
| 202 | sorted whether or not vector_redistribute_buckets sorted it. */ | 202 | sorted whether or not vector_redistribute_buckets sorted it. */ |
| 203 | static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) { | 203 | static void build_flat_vector(ot_vector *peers, size_t count) { |
| 204 | size_t i; | 204 | size_t i; |
| 205 | 205 | ||
| 206 | memset(peer_list, 0, sizeof(*peer_list)); | 206 | memset(peers, 0, sizeof(*peers)); |
| 207 | peer_list->peers.data = malloc(count * OT_PEER_SIZE4); | 207 | peers->data = malloc(count * OT_PEER_SIZE4); |
| 208 | peer_list->peers.size = count; | 208 | peers->size = count; |
| 209 | peer_list->peers.space = count; | 209 | peers->space = count; |
| 210 | peer_list->peer_count = count; | ||
| 211 | 210 | ||
| 212 | for (i = 0; i < count; ++i) { | 211 | for (i = 0; i < count; ++i) { |
| 213 | uint8_t *peer = (uint8_t *)peer_list->peers.data + i * OT_PEER_SIZE4; | 212 | uint8_t *peer = (uint8_t *)peers->data + i * OT_PEER_SIZE4; |
| 214 | 213 | ||
| 215 | memset(peer, 0, OT_PEER_SIZE4); | 214 | memset(peer, 0, OT_PEER_SIZE4); |
| 216 | peer[0] = (uint8_t)i; | 215 | peer[0] = (uint8_t)i; |
| @@ -222,19 +221,19 @@ static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) { | |||
| 222 | 221 | ||
| 223 | static void case_redistribute_holds_every_peer(void) { | 222 | static void case_redistribute_holds_every_peer(void) { |
| 224 | const size_t count = 513; | 223 | const size_t count = 513; |
| 225 | ot_peerlist peer_list; | 224 | ot_vector peers; |
| 226 | size_t bucket, total_size = 0, empty = 0, largest = 0; | 225 | size_t bucket, total_size = 0, empty = 0, largest = 0; |
| 227 | ot_vector *buckets; | 226 | ot_vector *buckets; |
| 228 | 227 | ||
| 229 | test_case("a peer list past the threshold is split into buckets"); | 228 | test_case("a peer list past the threshold is split into buckets"); |
| 230 | build_flat_peerlist(&peer_list, count); | 229 | build_flat_vector(&peers, count); |
| 231 | CHECK(peer_list.peers.data != NULL); | 230 | CHECK(peers.data != NULL); |
| 232 | vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); | 231 | vector_redistribute_buckets(&peers, OT_PEER_SIZE4, count); |
| 233 | CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1); | 232 | CHECK_INT(OT_VECTOR_HASBUCKETS(&peers), 1); |
| 234 | CHECK_INT(peer_list.peers.size, 16); | 233 | CHECK_INT(peers.size, 16); |
| 235 | 234 | ||
| 236 | buckets = peer_list.peers.data; | 235 | buckets = peers.data; |
| 237 | for (bucket = 0; bucket < peer_list.peers.size; ++bucket) { | 236 | for (bucket = 0; bucket < peers.size; ++bucket) { |
| 238 | total_size += buckets[bucket].size; | 237 | total_size += buckets[bucket].size; |
| 239 | if (!buckets[bucket].size) | 238 | if (!buckets[bucket].size) |
| 240 | ++empty; | 239 | ++empty; |
| @@ -252,23 +251,23 @@ static void case_redistribute_holds_every_peer(void) { | |||
| 252 | CHECK_INT(empty, 0); | 251 | CHECK_INT(empty, 0); |
| 253 | CHECK(largest < count / 2); | 252 | CHECK(largest < count / 2); |
| 254 | 253 | ||
| 255 | vector_clean_list(peer_list.peers.data, peer_list.peers.size); | 254 | vector_clean_list(peers.data, peers.size); |
| 256 | } | 255 | } |
| 257 | 256 | ||
| 258 | static void case_redistribute_sorts_each_bucket(void) { | 257 | static void case_redistribute_sorts_each_bucket(void) { |
| 259 | const size_t count = 1000; | 258 | const size_t count = 1000; |
| 260 | ot_peerlist peer_list; | 259 | ot_vector peers; |
| 261 | size_t bucket, i, out_of_order = 0; | 260 | size_t bucket, i, out_of_order = 0; |
| 262 | ot_vector *buckets; | 261 | ot_vector *buckets; |
| 263 | 262 | ||
| 264 | test_case("every bucket comes back sorted, so bsearch can be used on it"); | 263 | test_case("every bucket comes back sorted, so bsearch can be used on it"); |
| 265 | build_flat_peerlist(&peer_list, count); | 264 | build_flat_vector(&peers, count); |
| 266 | CHECK(peer_list.peers.data != NULL); | 265 | CHECK(peers.data != NULL); |
| 267 | vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); | 266 | vector_redistribute_buckets(&peers, OT_PEER_SIZE4, count); |
| 268 | CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1); | 267 | CHECK_INT(OT_VECTOR_HASBUCKETS(&peers), 1); |
| 269 | 268 | ||
| 270 | buckets = peer_list.peers.data; | 269 | buckets = peers.data; |
| 271 | for (bucket = 0; bucket < peer_list.peers.size; ++bucket) | 270 | for (bucket = 0; bucket < peers.size; ++bucket) |
| 272 | for (i = 1; i < buckets[bucket].size; ++i) { | 271 | for (i = 1; i < buckets[bucket].size; ++i) { |
| 273 | const uint8_t *prev = (uint8_t *)buckets[bucket].data + (i - 1) * OT_PEER_SIZE4; | 272 | const uint8_t *prev = (uint8_t *)buckets[bucket].data + (i - 1) * OT_PEER_SIZE4; |
| 274 | const uint8_t *next = (uint8_t *)buckets[bucket].data + i * OT_PEER_SIZE4; | 273 | 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) { | |||
| 278 | } | 277 | } |
| 279 | CHECK_INT(out_of_order, 0); | 278 | CHECK_INT(out_of_order, 0); |
| 280 | 279 | ||
| 281 | vector_clean_list(peer_list.peers.data, peer_list.peers.size); | 280 | vector_clean_list(peers.data, peers.size); |
| 282 | } | 281 | } |
| 283 | 282 | ||
| 284 | static void case_redistribute_below_threshold(void) { | 283 | static void case_redistribute_below_threshold(void) { |
| 285 | ot_peerlist peer_list; | 284 | ot_vector peers; |
| 286 | 285 | ||
| 287 | test_case("a small peer list is left flat"); | 286 | test_case("a small peer list is left flat"); |
| 288 | build_flat_peerlist(&peer_list, 100); | 287 | build_flat_vector(&peers, 100); |
| 289 | CHECK(peer_list.peers.data != NULL); | 288 | CHECK(peers.data != NULL); |
| 290 | vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); | 289 | vector_redistribute_buckets(&peers, OT_PEER_SIZE4, 100); |
| 291 | CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 0); | 290 | CHECK_INT(OT_VECTOR_HASBUCKETS(&peers), 0); |
| 292 | CHECK_INT(peer_list.peers.size, 100); | 291 | CHECK_INT(peers.size, 100); |
| 293 | free(peer_list.peers.data); | 292 | free(peers.data); |
| 294 | } | 293 | } |
| 295 | 294 | ||
| 296 | void test_vector(void) { | 295 | void test_vector(void) { |
