diff options
| -rw-r--r-- | src/peers.c | 54 | ||||
| -rw-r--r-- | test/peers.c | 19 |
2 files changed, 46 insertions, 27 deletions
diff --git a/src/peers.c b/src/peers.c index 5942021..dad3e55 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)); @@ -168,33 +167,42 @@ void expire_hashes(time_t now) { struct peer_entry *entry = &peer_table[i]; if(!entry->set) continue; + dbg("Last_seen %p: %ld", i, entry->last_seen); 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); + dbg("Hash %p <= %p", next_hash, current_hole); + if(next_hash <= current_hole) { + dbg("Copy %p to %p", head, 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; + dbg("Removing %p", current_hole); + 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); } |