Before this patch we had 3 loops walking a hash chain to delete records:
tdb_do_delete() to find the predecessor of the record that was to be deleted. tdb_count_dead(), the name says it all and tdb_purge_dead() to give back all dead records from a chain to the freelist.
This patch introduces tdb_trim_dead that walks a hash chain just once. While it does so it counts the number of dead records, and all records beyond tdb->max_dead_records are moved to the freelist.
Normal record deletion now works by always marking a record as dead in step 1 and then calling tdb_trim_dead. This is made safe against circular chains by doing the slow chain walk only in the case when we did not delete a dead record during our walk.
It changes our dynamics a bit:
When deleting a record with non-zero max_dead_records, now we always leave that number of records around when deleting, doing a blocking lock on the freelist when we found too many dead records.
Previously when exceeding max_dead_records we wiped all dead records to start accumulating them from scratch, assuming we could lock the freelist in a nonblocking fashion.
The net effect for an uncontended freelist is the same: In tdb_allocate() we still completely hand over all dead records to the freelist when we could lock it, it just happens later than without this patch.
This means for a lightly loaded system we will potentially leave more dead records around in databases like locking.tdb. However, on a heavily loaded system we become more predictable: If the freelist is so heavily contended that across many deletes we can't get hold of it, previously we accumulated more dead records than max_dead_records would allow. This is a really lowlevel tradeoff that is likely hard to measure, but to me becoming more deterministic without sacrificing too much parallelism (we keep more dead records around) is worth trying.
500a729a556 tdb: Make record deletion circular-chain safe
lib/tdb/common/freelist.c | 11 +++
lib/tdb/common/tdb.c | 217 +++++++++++++++++++++++--------------------
lib/tdb/common/tdb_private.h | 3 +-
3 files changed, 129 insertions(+), 102 deletions(-)