Fix the expire hashmap remove code

2 files changed, 42 insertions, 27 deletions

diff --git a/src/peers.c b/src/peers.c
index 5942021..f54f2e3 100644
--- a/src/peers.c
+++ b/src/peers.c
@@ -18,7 +18,6 @@ static void dbgl_id(struct infohash* id) {
 	}
 }
 
-
 int allocate_hashtable() {
 	memset(&peer_status, 0, sizeof(struct peer_status));
 
@@ -170,31 +169,36 @@ void expire_hashes(time_t now) {
 
 		if(difftime(now, entry->last_seen + HASH_TIMEOUT) < 0.0) continue;
 
-		// Find the last hash that collides with us
-		uint64_t entry_hash = hash(&entry->key, peer_table_size);
-		size_t last_in_slot = i;
+		// The entry is expired, remove it from the table
+		// This is a standard linear probing hashtable removal. current_slot is
+		// the "hole" we are currently trying to fill in with something. in
+		// doing so we have to find the next connected slot that can go here
+		// (has a hash value smaller than the slot index) and copy it in. That
+		// leaves us with a new "hole" we then have to fill in.
+		// @PERF This is a little naive. In chains with a long series of
+		// matching hashes, we will end up copying each. We could probably
+		// speed that up a little by allowing reordering.
+		size_t current_hole = i;
+		size_t head = current_hole;
 		while(true) {
-			size_t next = (last_in_slot + 1) % peer_table_size;
-			assert(next != i);
-
-			// There can't be holes in the chain
-			if(!peer_table[next].set) break;
-
-			// If the two hashes are different we've reached the end of the probe chain
-			uint64_t next_hash = hash(&peer_table[next].key, peer_table_size);
-			if(next_hash != entry_hash) break;
-
-			last_in_slot = next;
-		}
-
-		// If some hashes were chained on us, we copy the last one into our slot
-		if(last_in_slot != i) {
-			*entry = peer_table[last_in_slot];
-			entry = &peer_table[last_in_slot];
+			head = (head + 1) % peer_table_size;
+			assert(head != i);
+
+			// If there's nothing in the chain that can be copied into the
+			// "hole" then we're done. Everything we skipped can stay.
+			if(!peer_table[head].set) break;
+
+			// Check if the head slot could have been placed here
+			uint64_t next_hash = hash(&peer_table[head].key, peer_table_size);
+			if(next_hash <= current_hole) {
+				// Then copy it over
+				peer_table[current_hole] = peer_table[head];
+				// And try to fill in this new "hole"
+				current_hole = head;
+			}
 		}
 
-		// Remove the slot
-		entry->set = false;
+		peer_table[current_hole].set = false;
 		peer_table_load--;
 		prom_counter_inc(hash_expired, NULL);
 	}
diff --git a/test/peers.c b/test/peers.c
index 49bf6c1..b31186b 100644
--- a/test/peers.c
+++ b/test/peers.c
@@ -106,17 +106,28 @@ void test_grows() {
 void test_expired() {
 	allocate_hashtable();
 
+	// @FRAGILE Theres a complication with linear probing where earlier
+	// displacements cause later slots to also displace. We are forcing that
+	// case here while making sure that the one we want to retain is the one
+	// displaced from the slot right after the ones that expire. That means the
+	// values of these infohashes are tightly coupled to the hash function.
+	// I don't have any way to assert that.
+
 	struct infohash sometorrent = {.inner={0x0034048f, 0x08000020, 0x00888880, 0x02008460, 0x0ab00521}};
-	struct infohash other = {.inner={0x0034048f, 0x08000020, 0x00888880, 0x02008470, 0x0ab00521}};
+	struct infohash samehash = {.inner={0x0034048f, 0x08000020, 0x00888880, 0x02008470, 0x0ab00521}};
+	struct infohash nexthash = {.inner={0x0034048f, 0x08000020, 0x00888880, 0x02008470, 0x0ab00522}};
 	struct addr addr = (struct addr){.ip = IP(128,0,0,1), .port = 0};
 	struct addr other_addr = (struct addr){.ip = IP(128,0,0,1), .port = 1};
 
 	int rc = add_peer(&sometorrent, &addr, 0);
 	TEST_ASSERT_EQUAL(0, rc);
-	rc = add_peer(&other, &addr, 0);
+	rc = add_peer(&samehash, &addr, 0);
+	TEST_ASSERT_EQUAL(0, rc);
+	rc = add_peer(&nexthash, &addr, 0);
 	TEST_ASSERT_EQUAL(0, rc);
 
-	rc = add_peer(&other, &other_addr, 1);
+	// Add a peer later, should refresh the hash
+	rc = add_peer(&nexthash, &other_addr, 2);
 	TEST_ASSERT_EQUAL(0, rc);
 
 	expire_hashes(HASH_TIMEOUT + 1);
@@ -132,7 +143,7 @@ void test_expired() {
 	{
 		struct addr* found;
 		size_t found_len;
-		get_peers(&other, &found, &found_len);
+		get_peers(&nexthash, &found, &found_len);
 		TEST_ASSERT_NOT_NULL(found);
 		TEST_ASSERT_EQUAL(2, found_len);
 	}