The hash_table implementation's setOldestVersion enters an infinite loop (hangs forever) when its garbage-collection pass erases every entry in the map while keyUpdates is still greater than zero. This is triggered by valid input that satisfies all documented API preconditions.
voidsetOldestVersion(int64_toldestVersion){if(oldestVersion<=this->oldestVersion){return;}this->oldestVersion=oldestVersion;if(keyUpdates<100){// line 55
return;}autoiter=map.find(removalKey);while(keyUpdates>0){// line 59
if(iter==map.end()){iter=map.begin();// line 61 — == end() once the map is empty
}for(;iter!=map.end();--keyUpdates){// line 63 — never executes on empty map
if(iter->second<=oldestVersion){iter=map.erase(iter);}else{++iter;}}}...}
addWrites increments keyUpdates += 2 per write (HashTable.cpp:46). The GC runs once keyUpdates >= 100 (line 55), and the inner for loop decrements keyUpdates by exactly 1 per entry visited (erased or not). If every entry has version <= oldestVersion, all entries are erased, but keyUpdates was charged at 2× the entry count, so it remains > 0 after the map is emptied. On the next while iteration, iter == map.end() is reset to map.begin(), which is also end() for an empty map; the for loop body therefore never runs and keyUpdates is never decremented again — the while (keyUpdates > 0) loop spins forever.
Reproduction (minimal, valid input)
Compile a small C program against hash_table/libconflict-set.so:
#include"ConflictSet.h"#include<stdio.h>intmain(void){ConflictSet*cs=ConflictSet_create(0);/* 50 point writes at version 1 -> keyUpdates = 100, GC enabled */for(inti=0;i<50;++i){charkey[8];snprintf(key,sizeofkey,"k%06d",i);ConflictSet_WriteRangew={{(constuint8_t*)key,7},{0,0}};ConflictSet_addWrites(cs,&w,1,1);}/* All entries have version 1 <= oldestVersion 1 -> all erased,
keyUpdates remains 50 > 0, map empty -> infinite loop. */ConflictSet_setOldestVersion(cs,1);printf("returned\n");/* never reached */ConflictSet_destroy(cs);return0;}
All preconditions are respected: writeVersion (1) >= previous newest (0); oldestVersion (1) >= previous oldest (0) and <= newest (1).
Observed behavior
$ timeout 5 ./ht_test
Added 50 keys at version 1. Calling setOldestVersion(1)...
$ echo $? # 124 -> killed by timeout (hung)
setOldestVersion never returns. The equivalent sequence run against radix_tree/libconflict-set.so returns normally (the radix-tree GC, gcScanStep, is fuel-bounded and not affected).
A control case where some entries survive (e.g. 60 keys at v1 + 60 keys at v100, then setOldestVersion(50)) returns normally, confirming the hang is specifically the empty-map spin.
Impact
The hash_table implementation is a shipped, linkable library (hash_table/libconflict-set.so, built by CMake, exposed via the implementation="hash_table" option in conflict_set.py, and used by RealDataBench). Any caller that advances oldestVersion past the versions of all currently-extant point writes — a normal operational action once a workload drains — hangs the process forever. This is a liveness/denial-of-service defect on valid input.
The existing test_hash_table_getBytes regression test does not catch this because it only adds a single write (keyUpdates = 2 < 100, so GC never runs).
Suggested fix
The GC loop must terminate when the map is exhausted. For example, break out of the while loop (or set keyUpdates = 0) when an entire pass completes without visiting any entry (i.e. when map.begin() == map.end()), instead of unconditionally re-entering the for loop on an empty map.
## Defect
The `hash_table` implementation's `setOldestVersion` enters an infinite loop (hangs forever) when its garbage-collection pass erases every entry in the map while `keyUpdates` is still greater than zero. This is triggered by valid input that satisfies all documented API preconditions.
## Location
`HashTable.cpp`, `ConflictSet::Impl::setOldestVersion` (lines 50–76):
```cpp
void setOldestVersion(int64_t oldestVersion) {
if (oldestVersion <= this->oldestVersion) {
return;
}
this->oldestVersion = oldestVersion;
if (keyUpdates < 100) { // line 55
return;
}
auto iter = map.find(removalKey);
while (keyUpdates > 0) { // line 59
if (iter == map.end()) {
iter = map.begin(); // line 61 — == end() once the map is empty
}
for (; iter != map.end(); --keyUpdates) { // line 63 — never executes on empty map
if (iter->second <= oldestVersion) {
iter = map.erase(iter);
} else {
++iter;
}
}
}
...
}
```
`addWrites` increments `keyUpdates += 2` per write (`HashTable.cpp:46`). The GC runs once `keyUpdates >= 100` (line 55), and the inner `for` loop decrements `keyUpdates` by exactly 1 per entry **visited** (erased or not). If every entry has `version <= oldestVersion`, all entries are erased, but `keyUpdates` was charged at 2× the entry count, so it remains `> 0` after the map is emptied. On the next `while` iteration, `iter == map.end()` is reset to `map.begin()`, which is also `end()` for an empty map; the `for` loop body therefore never runs and `keyUpdates` is never decremented again — the `while (keyUpdates > 0)` loop spins forever.
## Reproduction (minimal, valid input)
Compile a small C program against `hash_table/libconflict-set.so`:
```c
#include "ConflictSet.h"
#include <stdio.h>
int main(void) {
ConflictSet *cs = ConflictSet_create(0);
/* 50 point writes at version 1 -> keyUpdates = 100, GC enabled */
for (int i = 0; i < 50; ++i) {
char key[8]; snprintf(key, sizeof key, "k%06d", i);
ConflictSet_WriteRange w = { { (const uint8_t*)key, 7 }, { 0, 0 } };
ConflictSet_addWrites(cs, &w, 1, 1);
}
/* All entries have version 1 <= oldestVersion 1 -> all erased,
keyUpdates remains 50 > 0, map empty -> infinite loop. */
ConflictSet_setOldestVersion(cs, 1);
printf("returned\n"); /* never reached */
ConflictSet_destroy(cs);
return 0;
}
```
All preconditions are respected: `writeVersion` (1) >= previous newest (0); `oldestVersion` (1) >= previous oldest (0) and <= newest (1).
## Observed behavior
```
$ timeout 5 ./ht_test
Added 50 keys at version 1. Calling setOldestVersion(1)...
$ echo $? # 124 -> killed by timeout (hung)
```
`setOldestVersion` never returns. The equivalent sequence run against `radix_tree/libconflict-set.so` returns normally (the radix-tree GC, `gcScanStep`, is fuel-bounded and not affected).
A control case where some entries survive (e.g. 60 keys at v1 + 60 keys at v100, then `setOldestVersion(50)`) returns normally, confirming the hang is specifically the empty-map spin.
## Impact
The hash_table implementation is a shipped, linkable library (`hash_table/libconflict-set.so`, built by CMake, exposed via the `implementation="hash_table"` option in `conflict_set.py`, and used by `RealDataBench`). Any caller that advances `oldestVersion` past the versions of all currently-extant point writes — a normal operational action once a workload drains — hangs the process forever. This is a liveness/denial-of-service defect on valid input.
The existing `test_hash_table_getBytes` regression test does not catch this because it only adds a single write (`keyUpdates = 2 < 100`, so GC never runs).
## Suggested fix
The GC loop must terminate when the map is exhausted. For example, break out of the `while` loop (or set `keyUpdates = 0`) when an entire pass completes without visiting any entry (i.e. when `map.begin() == map.end()`), instead of unconditionally re-entering the `for` loop on an empty map.
weaselbot
was assigned by andrew2026-08-16 12:04:24 +00:00
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
Defect
The
hash_tableimplementation'ssetOldestVersionenters an infinite loop (hangs forever) when its garbage-collection pass erases every entry in the map whilekeyUpdatesis still greater than zero. This is triggered by valid input that satisfies all documented API preconditions.Location
HashTable.cpp,ConflictSet::Impl::setOldestVersion(lines 50–76):addWritesincrementskeyUpdates += 2per write (HashTable.cpp:46). The GC runs oncekeyUpdates >= 100(line 55), and the innerforloop decrementskeyUpdatesby exactly 1 per entry visited (erased or not). If every entry hasversion <= oldestVersion, all entries are erased, butkeyUpdateswas charged at 2× the entry count, so it remains> 0after the map is emptied. On the nextwhileiteration,iter == map.end()is reset tomap.begin(), which is alsoend()for an empty map; theforloop body therefore never runs andkeyUpdatesis never decremented again — thewhile (keyUpdates > 0)loop spins forever.Reproduction (minimal, valid input)
Compile a small C program against
hash_table/libconflict-set.so:All preconditions are respected:
writeVersion(1) >= previous newest (0);oldestVersion(1) >= previous oldest (0) and <= newest (1).Observed behavior
setOldestVersionnever returns. The equivalent sequence run againstradix_tree/libconflict-set.soreturns normally (the radix-tree GC,gcScanStep, is fuel-bounded and not affected).A control case where some entries survive (e.g. 60 keys at v1 + 60 keys at v100, then
setOldestVersion(50)) returns normally, confirming the hang is specifically the empty-map spin.Impact
The hash_table implementation is a shipped, linkable library (
hash_table/libconflict-set.so, built by CMake, exposed via theimplementation="hash_table"option inconflict_set.py, and used byRealDataBench). Any caller that advancesoldestVersionpast the versions of all currently-extant point writes — a normal operational action once a workload drains — hangs the process forever. This is a liveness/denial-of-service defect on valid input.The existing
test_hash_table_getBytesregression test does not catch this because it only adds a single write (keyUpdates = 2 < 100, so GC never runs).Suggested fix
The GC loop must terminate when the map is exhausted. For example, break out of the
whileloop (or setkeyUpdates = 0) when an entire pass completes without visiting any entry (i.e. whenmap.begin() == map.end()), instead of unconditionally re-entering theforloop on an empty map.Hash table isn’t shipped, but fix it anyway