From 632960a33eb8d23925b2bbef24d5065de7280aef Mon Sep 17 00:00:00 2001 From: Dirk Engling Date: Sun, 25 Oct 2026 13:00:17 +0100 Subject: Clean up peer re-distribution between single bucket vectors and bucket lists, add tests --- ot_vector.c | 8 ++--- tests/t_vector.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 107 insertions(+), 5 deletions(-) diff --git a/ot_vector.c b/ot_vector.c index c4cd171..7f18246 100644 --- a/ot_vector.c +++ b/ot_vector.c @@ -8,7 +8,6 @@ #include #include #include -#include /* Opentracker */ #include "trackerlogic.h" @@ -174,7 +173,7 @@ void vector_clean_list(ot_vector *vector, size_t num_buckets) { } void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { - size_t tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; + size_t bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; ot_vector *bucket_list_new, *bucket_list_old = &peer_list->peers; int (*sort_func)(const void *, const void *) = peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4; @@ -205,11 +204,10 @@ void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { bucket_list_new = malloc(num_buckets_new * sizeof(ot_vector)); if (!bucket_list_new) return; - bzero(bucket_list_new, num_buckets_new * sizeof(ot_vector)); + memset(bucket_list_new, 0, num_buckets_new * sizeof(ot_vector)); - tmp = peer_list->peer_count / num_buckets_new; bucket_size_new = OT_VECTOR_MIN_MEMBERS; - while (bucket_size_new < tmp) + while (bucket_size_new * num_buckets_new < peer_list->peer_count) bucket_size_new *= OT_VECTOR_GROW_RATIO; /* preallocate vectors to hold all peers */ diff --git a/tests/t_vector.c b/tests/t_vector.c index fee336b..a8186b2 100644 --- a/tests/t_vector.c +++ b/tests/t_vector.c @@ -4,10 +4,12 @@ $id$ */ /* System */ +#include #include #include /* Opentracker */ +#include "ot_vector.h" #include "trackerlogic.h" #include "test.h" @@ -149,6 +151,105 @@ static void case_insert_compare_prefix(void) { free(vector.data); } +/* ------------------------------------------------- bucket redistribution */ + +/* A flat peer list of count distinct v4 peers. The low byte of the index goes + into the first address byte, so the peers are distinct but arrive in no + particular order: a list generated in ascending order would come back + sorted whether or not vector_redistribute_buckets sorted it. */ +static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) { + size_t i; + + memset(peer_list, 0, sizeof(*peer_list)); + peer_list->peers.data = malloc(count * OT_PEER_SIZE4); + peer_list->peers.size = count; + peer_list->peers.space = count; + peer_list->peer_count = count; + + for (i = 0; i < count; ++i) { + uint8_t *peer = (uint8_t *)peer_list->peers.data + i * OT_PEER_SIZE4; + + memset(peer, 0, OT_PEER_SIZE4); + peer[0] = (uint8_t)i; + peer[1] = (uint8_t)(i >> 8); + peer[2] = (uint8_t)(i >> 16); + peer[3] = 1; + } +} + +static void case_redistribute_holds_every_peer(void) { + const size_t count = 513; + ot_peerlist peer_list; + size_t bucket, total_size = 0, empty = 0, largest = 0; + ot_vector *buckets; + + test_case("a peer list past the threshold is split into buckets"); + build_flat_peerlist(&peer_list, count); + CHECK(peer_list.peers.data != NULL); + vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); + CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1); + CHECK_INT(peer_list.peers.size, 16); + + buckets = peer_list.peers.data; + for (bucket = 0; bucket < peer_list.peers.size; ++bucket) { + total_size += buckets[bucket].size; + if (!buckets[bucket].size) + ++empty; + if (buckets[bucket].size > largest) + largest = buckets[bucket].size; + } + + test_case("no peer is lost on the way"); + CHECK_INT(total_size, count); + + /* The point of the exercise is that a lookup only searches one bucket, so + a hash that piled everything into one would defeat it. The input and the + hash are both fixed, so this is not a matter of luck. */ + test_case("and they are spread over the buckets rather than piled up"); + CHECK_INT(empty, 0); + CHECK(largest < count / 2); + + vector_clean_list(peer_list.peers.data, peer_list.peers.size); +} + +static void case_redistribute_sorts_each_bucket(void) { + const size_t count = 1000; + ot_peerlist peer_list; + size_t bucket, i, out_of_order = 0; + ot_vector *buckets; + + test_case("every bucket comes back sorted, so bsearch can be used on it"); + build_flat_peerlist(&peer_list, count); + CHECK(peer_list.peers.data != NULL); + vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); + CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1); + + buckets = peer_list.peers.data; + for (bucket = 0; bucket < peer_list.peers.size; ++bucket) + for (i = 1; i < buckets[bucket].size; ++i) { + const uint8_t *prev = (uint8_t *)buckets[bucket].data + (i - 1) * OT_PEER_SIZE4; + const uint8_t *next = (uint8_t *)buckets[bucket].data + i * OT_PEER_SIZE4; + + if (memcmp(prev, next, OT_PEER_COMPARE_SIZE4) >= 0) + ++out_of_order; + } + CHECK_INT(out_of_order, 0); + + vector_clean_list(peer_list.peers.data, peer_list.peers.size); +} + +static void case_redistribute_below_threshold(void) { + ot_peerlist peer_list; + + test_case("a small peer list is left flat"); + build_flat_peerlist(&peer_list, 100); + CHECK(peer_list.peers.data != NULL); + vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4); + CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 0); + CHECK_INT(peer_list.peers.size, 100); + free(peer_list.peers.data); +} + void test_vector(void) { case_search_finds_member(); case_search_finds_first_and_last(); @@ -158,4 +259,7 @@ void test_vector(void) { case_insert_keeps_order(); case_insert_finds_existing(); case_insert_compare_prefix(); + case_redistribute_holds_every_peer(); + case_redistribute_sorts_each_bucket(); + case_redistribute_below_threshold(); } -- cgit v1.3