hash_table: addWrites never advances oldestVersion to newestVersion - 2e9, so reads that fell out of the 2-billion-version window return Conflict/Commit instead of TooOld
#98
addWrites' documented postcondition is not implemented by the hash_table
implementation: it never records writeVersion as newestVersion, and never
advances oldestVersion to newestVersion - two billion. As a result, check() returns Conflict/Commit where the interface says TooOld for any
read whose readVersion fell out of the two-billion-version window.
include/ConflictSet.h (C++ section, lines 85-91; identical C text at 228-236):
* @post Writes (writes[i], writeVersion) are recorded for every i < count,
* and `newestVersion` becomes `writeVersion`. `oldestVersion` advances only
* as far as necessary: it becomes the larger of its previous value and
* `newestVersion - two billion`. Calling with `count == 0` adds no write;
* `newestVersion` (and possibly `oldestVersion`) still advance. */
void addWrites(const WriteRange *writes, int count, int64_t writeVersion);
and the class-level invariant (lines 26-29):
* All versions are >= 0. `oldestVersion` is the smallest version a subsequent
* `check` can read and `newestVersion` is the largest version passed to
* `addWrites` or the constructor. `oldestVersion <= newestVersion`, and
* `oldestVersion >= newestVersion - two billion`.
This is not a new requirement: commit a68ad5d ("Interface change! Return
TooOld after 2e9 versions — Even if setOldestVersion wasn't called") added it
deliberately to both real implementations. The radix tree advances oldestVersionFullPrecision in addWrites (ConflictSet.cpp:5178-5181, 5189-5192), and the skip list keeps a newestVersion and applies the rule in check (SkipList.cpp:722, 744, 795-796, 899). HashTable.cpp predates
that commit (added in 8bf3aa7) and was never updated.
Where
HashTable.cpp:21-48 — ConflictSet::Impl has no newestVersion member at
all; addWrites (lines 39-48) only writes into map and bumps keyUpdates:
struct__attribute__((visibility("hidden")))ConflictSet::Impl{Impl(int64_toldestVersion):oldestVersion(oldestVersion){}voidcheck(constConflictSet::ReadRange*reads,ConflictSet::Result*results,intcount)const{...if(version<oldestVersion){// line 29: no newestVersion - 2e9 rule
results[i]=TooOld;continue;}...}voidaddWrites(constConflictSet::WriteRange*writes,intcount,int64_twriteVersion){for(inti=0;i<count;++i){// line 41: newestVersion never updated
...
so oldestVersion stays at whatever was passed to the constructor / setOldestVersion, and check cannot know that ancient read versions are
supposed to report TooOld.
Reproduction
Using the repo's own conflict_set.py wrapper and a normal build:
fromconflict_setimport*build_dir="build"defprobe_with_write(impl,version):withConflictSet(0,build_dir=build_dir,implementation=impl)ascs:cs.addWrites(version,write(b"k"))returncs.check(read(0,b"k"))[0]defprobe_empty_write(impl,version):withConflictSet(0,build_dir=build_dir,implementation=impl)ascs:cs.addWrites(version)# no writes, but newestVersion advancesreturncs.check(read(0,b"k"))[0]forimplin("radix_tree","skip_list","hash_table"):print(impl,probe_with_write(impl,2**32).name)forimplin("radix_tree","skip_list","hash_table"):print(impl,probe_empty_write(impl,2**32).name)
The second case shows the count == 0 half of the postcondition ("newestVersion
(and possibly oldestVersion) still advance") is also unimplemented: the hash
table discards writeVersion entirely.
Expected vs actual
Expected (per the addWrites postcondition and the oldestVersion >= newestVersion - two billion invariant): after addWrites(..., 2**32), oldestVersion >= 2**32 - 2e9, so check on readVersion == 0 is TooOld.
Actual: HashTable.cpp reports Conflict (with a write) or Commit (with count == 0), i.e. it tells the caller the read is still evaluable long after
the two-billion-version window has been exceeded.
With the skip list this exact mistake was a real bug (#87): the version window
is what tells a caller "this read version is too old, retry"; a caller that
switches to the hash_table implementation silently loses that signal.
Why the test suite doesn't catch it
DebugConflictSet in test_conflict_set.py only bisimulates skip_list
against radix_tree; the hash table is only smoke-tested for point reads
(test_hash_table_getBytes, test_hash_table_setOldestVersion_empties_map),
never across a version jump larger than two billion.
test_two_billion_versions (added in the same commit a68ad5d) runs through DebugConflictSet, so it never exercises hash_table, and it asserts nothing
about the results — it would pass even if all three implementations agreed on
the wrong answer.
RealDataBench.cpp/Bench.cpp use read versions within a few hundred of newestVersion, so the window is never crossed when the hash table is
benchmarked.
Suggested fix
Mirror what SkipList.cpp does: add an int64_t newestVersion member, set it
in addWrites (assert(writeVersion >= newestVersion); newestVersion = writeVersion;
before the loop, so it also advances for count == 0), and in check treat version < newestVersion - 2e9 as TooOld. (Or advance oldestVersion in addWrites like the radix tree, since this implementation stores full 64-bit
versions.)
## Summary
`addWrites`' documented postcondition is not implemented by the `hash_table`
implementation: it never records `writeVersion` as `newestVersion`, and never
advances `oldestVersion` to `newestVersion - two billion`. As a result,
`check()` returns `Conflict`/`Commit` where the interface says `TooOld` for any
read whose `readVersion` fell out of the two-billion-version window.
`include/ConflictSet.h` (C++ section, lines 85-91; identical C text at 228-236):
```
* @post Writes (writes[i], writeVersion) are recorded for every i < count,
* and `newestVersion` becomes `writeVersion`. `oldestVersion` advances only
* as far as necessary: it becomes the larger of its previous value and
* `newestVersion - two billion`. Calling with `count == 0` adds no write;
* `newestVersion` (and possibly `oldestVersion`) still advance. */
void addWrites(const WriteRange *writes, int count, int64_t writeVersion);
```
and the class-level invariant (lines 26-29):
```
* All versions are >= 0. `oldestVersion` is the smallest version a subsequent
* `check` can read and `newestVersion` is the largest version passed to
* `addWrites` or the constructor. `oldestVersion <= newestVersion`, and
* `oldestVersion >= newestVersion - two billion`.
```
This is not a new requirement: commit `a68ad5d` ("Interface change! Return
TooOld after 2e9 versions — Even if setOldestVersion wasn't called") added it
deliberately to both real implementations. The radix tree advances
`oldestVersionFullPrecision` in `addWrites` (`ConflictSet.cpp:5178-5181`,
`5189-5192`), and the skip list keeps a `newestVersion` and applies the rule in
`check` (`SkipList.cpp:722`, `744`, `795-796`, `899`). `HashTable.cpp` predates
that commit (added in `8bf3aa7`) and was never updated.
## Where
`HashTable.cpp:21-48` — `ConflictSet::Impl` has no `newestVersion` member at
all; `addWrites` (lines 39-48) only writes into `map` and bumps `keyUpdates`:
```cpp
struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
Impl(int64_t oldestVersion) : oldestVersion(oldestVersion) {}
void check(const ConflictSet::ReadRange *reads, ConflictSet::Result *results,
int count) const {
...
if (version < oldestVersion) { // line 29: no newestVersion - 2e9 rule
results[i] = TooOld;
continue;
}
...
}
void addWrites(const ConflictSet::WriteRange *writes, int count,
int64_t writeVersion) {
for (int i = 0; i < count; ++i) { // line 41: newestVersion never updated
...
```
so `oldestVersion` stays at whatever was passed to the constructor /
`setOldestVersion`, and `check` cannot know that ancient read versions are
supposed to report `TooOld`.
## Reproduction
Using the repo's own `conflict_set.py` wrapper and a normal build:
```python
from conflict_set import *
build_dir = "build"
def probe_with_write(impl, version):
with ConflictSet(0, build_dir=build_dir, implementation=impl) as cs:
cs.addWrites(version, write(b"k"))
return cs.check(read(0, b"k"))[0]
def probe_empty_write(impl, version):
with ConflictSet(0, build_dir=build_dir, implementation=impl) as cs:
cs.addWrites(version) # no writes, but newestVersion advances
return cs.check(read(0, b"k"))[0]
for impl in ("radix_tree", "skip_list", "hash_table"):
print(impl, probe_with_write(impl, 2**32).name)
for impl in ("radix_tree", "skip_list", "hash_table"):
print(impl, probe_empty_write(impl, 2**32).name)
```
Observed (Debug build at `e23018c`):
```
radix_tree TOO_OLD
skip_list TOO_OLD
hash_table CONFLICT <-- expected TOO_OLD
radix_tree TOO_OLD
skip_list TOO_OLD
hash_table COMMIT <-- expected TOO_OLD
```
The second case shows the `count == 0` half of the postcondition ("`newestVersion`
(and possibly `oldestVersion`) still advance") is also unimplemented: the hash
table discards `writeVersion` entirely.
## Expected vs actual
* Expected (per the `addWrites` postcondition and the `oldestVersion >=
newestVersion - two billion` invariant): after `addWrites(..., 2**32)`,
`oldestVersion >= 2**32 - 2e9`, so `check` on `readVersion == 0` is `TooOld`.
* Actual: `HashTable.cpp` reports `Conflict` (with a write) or `Commit` (with
`count == 0`), i.e. it tells the caller the read is still evaluable long after
the two-billion-version window has been exceeded.
With the skip list this exact mistake was a real bug (#87): the version window
is what tells a caller "this read version is too old, retry"; a caller that
switches to the `hash_table` implementation silently loses that signal.
## Why the test suite doesn't catch it
* `DebugConflictSet` in `test_conflict_set.py` only bisimulates `skip_list`
against `radix_tree`; the hash table is only smoke-tested for point reads
(`test_hash_table_getBytes`, `test_hash_table_setOldestVersion_empties_map`),
never across a version jump larger than two billion.
* `test_two_billion_versions` (added in the same commit `a68ad5d`) runs through
`DebugConflictSet`, so it never exercises `hash_table`, and it asserts nothing
about the results — it would pass even if all three implementations agreed on
the wrong answer.
* `RealDataBench.cpp`/`Bench.cpp` use read versions within a few hundred of
`newestVersion`, so the window is never crossed when the hash table is
benchmarked.
## Suggested fix
Mirror what `SkipList.cpp` does: add an `int64_t newestVersion` member, set it
in `addWrites` (`assert(writeVersion >= newestVersion); newestVersion = writeVersion;`
before the loop, so it also advances for `count == 0`), and in `check` treat
`version < newestVersion - 2e9` as `TooOld`. (Or advance `oldestVersion` in
`addWrites` like the radix tree, since this implementation stores full 64-bit
versions.)
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.
Summary
addWrites' documented postcondition is not implemented by thehash_tableimplementation: it never records
writeVersionasnewestVersion, and neveradvances
oldestVersiontonewestVersion - two billion. As a result,check()returnsConflict/Commitwhere the interface saysTooOldfor anyread whose
readVersionfell out of the two-billion-version window.include/ConflictSet.h(C++ section, lines 85-91; identical C text at 228-236):and the class-level invariant (lines 26-29):
This is not a new requirement: commit
a68ad5d("Interface change! ReturnTooOld after 2e9 versions — Even if setOldestVersion wasn't called") added it
deliberately to both real implementations. The radix tree advances
oldestVersionFullPrecisioninaddWrites(ConflictSet.cpp:5178-5181,5189-5192), and the skip list keeps anewestVersionand applies the rule incheck(SkipList.cpp:722,744,795-796,899).HashTable.cpppredatesthat commit (added in
8bf3aa7) and was never updated.Where
HashTable.cpp:21-48—ConflictSet::Implhas nonewestVersionmember atall;
addWrites(lines 39-48) only writes intomapand bumpskeyUpdates:so
oldestVersionstays at whatever was passed to the constructor /setOldestVersion, andcheckcannot know that ancient read versions aresupposed to report
TooOld.Reproduction
Using the repo's own
conflict_set.pywrapper and a normal build:Observed (Debug build at
e23018c):The second case shows the
count == 0half of the postcondition ("newestVersion(and possibly
oldestVersion) still advance") is also unimplemented: the hashtable discards
writeVersionentirely.Expected vs actual
addWritespostcondition and theoldestVersion >= newestVersion - two billioninvariant): afteraddWrites(..., 2**32),oldestVersion >= 2**32 - 2e9, socheckonreadVersion == 0isTooOld.HashTable.cppreportsConflict(with a write) orCommit(withcount == 0), i.e. it tells the caller the read is still evaluable long afterthe two-billion-version window has been exceeded.
With the skip list this exact mistake was a real bug (#87): the version window
is what tells a caller "this read version is too old, retry"; a caller that
switches to the
hash_tableimplementation silently loses that signal.Why the test suite doesn't catch it
DebugConflictSetintest_conflict_set.pyonly bisimulatesskip_listagainst
radix_tree; the hash table is only smoke-tested for point reads(
test_hash_table_getBytes,test_hash_table_setOldestVersion_empties_map),never across a version jump larger than two billion.
test_two_billion_versions(added in the same commita68ad5d) runs throughDebugConflictSet, so it never exerciseshash_table, and it asserts nothingabout the results — it would pass even if all three implementations agreed on
the wrong answer.
RealDataBench.cpp/Bench.cppuse read versions within a few hundred ofnewestVersion, so the window is never crossed when the hash table isbenchmarked.
Suggested fix
Mirror what
SkipList.cppdoes: add anint64_t newestVersionmember, set itin
addWrites(assert(writeVersion >= newestVersion); newestVersion = writeVersion;before the loop, so it also advances for
count == 0), and inchecktreatversion < newestVersion - 2e9asTooOld. (Or advanceoldestVersioninaddWriteslike the radix tree, since this implementation stores full 64-bitversions.)