summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--DESIGN33
-rw-r--r--src/ot_clean.c64
-rw-r--r--src/ot_fullscrape.c4
-rw-r--r--src/ot_stats.c14
-rw-r--r--src/ot_vector.c47
-rw-r--r--src/ot_vector.h2
-rw-r--r--src/trackerlogic.c118
-rw-r--r--src/trackerlogic.h39
-rw-r--r--tests/t_clean.c48
-rw-r--r--tests/t_vector.c61
10 files changed, 247 insertions, 183 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
84is one bucket every 117 ms. 84is one bucket every 117 ms.
85 85
86 86
87A torrent carries its hash, two peer-list pointers, a base and a down count, 87A torrent carries its hash, one peerlist pointer, a base and a down count, 40
8848 bytes on a 64-bit host, and the down count sits in what would otherwise be 88bytes on a 64-bit host. The base and the down count live on the torrent, not
89alignment padding. Each family's peer list, 32 bytes plus its peer vector, is 89on a list, so a torrent kept only for its download count holds no list at all.
90allocated on that family's first peer and freed when its last peer goes. The 90The one peerlist, allocated on the first peer of either family and freed when
91base and the down count live on the torrent rather than on a list, which is 91the last peer of both goes, holds the two family vectors and a single seeder
92what lets a list come and go: a torrent kept only for its download count holds 92count. The peer count is not stored, since a vector's own size is the count
93no list at all, and a single-family torrent holds one rather than two. 93for a plain list and the sum of its buckets for a split one. That leaves the
94seeder count the only tally to maintain, because seeding is a per-peer flag
95and counting it would mean a walk.
94 96
95This is paid for in the common shape of a large table. A tracker carrying 97This is paid for in the common shape of a large table. A tracker carrying
96millions of torrents averages close to two peers each, a few crowded swarms 98millions of torrents averages close to two peers each, a few crowded swarms
97over a long tail of near-empty ones, so fixed per-torrent cost, not peer 99over a long tail of near-empty ones, so fixed per-torrent cost, not peer
98payload, is most of resident memory. Allocating both lists for every torrent 100payload, is most of resident memory. An earlier layout gave each torrent two
99and keeping an idle torrent alive for a day to preserve one counter cost, on 101always-allocated peer lists with their own counters and kept an idle torrent
100glibc, 168 bytes per torrent before a peer; the layout above costs 48 for an 102alive for a day to preserve one number: on glibc 168 bytes before a peer. The
101empty torrent and 96 for a single-family one. The per-torrent counts are 103merged layout costs 40 for an empty torrent and, on glibc, 136 for a
102uint32: no single torrent holds 2^32 peers, and the four bytes saved against a 104single-family one and 184 for a torrent carrying both. A torrent with peers in
103size_t are multiplied by the torrent count. Global totals stay 64-bit. 105both families now takes one allocation rather than two. The split is drawn
104 106along the family distribution: empty and both-family torrents gain, a
107single-family torrent pays for the absent family's vector header. On jemalloc
108the bins differ, so the per-shape figures do too, but the empty-torrent and
109single-allocation gains hold on both.
105 110
106A refused announce is answered over UDP with a well formed announce for an 111A refused announce is answered over UDP with a well formed announce for an
107empty swarm rather than with the error action. BEP 15 binds a client to the 112empty 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. */
56static void clean_peer_list_family(ot_peerlist **slot, size_t peer_size, ot_time timedout) { 56static 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*/
97int clean_single_torrent(ot_torrent *torrent) { 92int 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 {
303static int torrent_statter(ot_torrent *torrent, uintptr_t data) { 303static 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
183void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { 182void 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_
32void vector_remove_torrent(ot_vector *vector, ot_torrent *match); 32void vector_remove_torrent(ot_vector *vector, ot_torrent *match);
33 33
34/* For ot_clean.c */ 34/* For ot_clean.c */
35void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size); 35void vector_redistribute_buckets(ot_vector *peer_vector, size_t peer_size, size_t peer_count);
36void vector_fixup_peers(ot_vector *vector, size_t peer_size); 36void vector_fixup_peers(ot_vector *vector, size_t peer_size);
37void vector_clean_list(ot_vector *vector, size_t num_buckets); 37void 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 */
29size_t return_peers_for_torrent(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply, PROTO_FLAG proto); 29size_t return_peers_for_torrent(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply, PROTO_FLAG proto);
30 30
31void 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
31void free_peerlist(ot_peerlist *peer_list) { 38void 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
201static size_t return_peers_all(ot_peerlist *peer_list, size_t peer_size, char *reply) { 202static 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
230static size_t return_peers_selection(struct ot_workstruct *ws, ot_peerlist *peer_list, size_t peer_size, size_t amount, char *reply) { 231static 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
281static size_t return_peers_for_torrent_udp(struct ot_workstruct *ws, ot_torrent *torrent, size_t amount, char *reply) { 282static 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
444static ot_peerlist dummy_list;
445size_t remove_peer_from_torrent(PROTO_FLAG proto, struct ot_workstruct *ws) { 447size_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;
170typedef struct ot_peerlist ot_peerlist; 170typedef struct ot_peerlist ot_peerlist;
171typedef struct { 171typedef 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
181struct ot_peerlist { 180struct 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
191static 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) */
192static 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. */
193static 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}
203static 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}
206static 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. */
195enum { 209enum {
@@ -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 */
316void free_peerlist(ot_peerlist *peer_list); 330void free_peerlist(ot_peerlist *peer_list);
331void 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 */
37static 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
36static size_t peers_in(ot_hash *hash) { 50static 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
174static 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
160void test_clean(void) { 207void 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. */
203static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) { 203static 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
223static void case_redistribute_holds_every_peer(void) { 222static 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
258static void case_redistribute_sorts_each_bucket(void) { 257static 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
284static void case_redistribute_below_threshold(void) { 283static 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
296void test_vector(void) { 295void test_vector(void) {