libdb 5.3.34: custom comparator equality is ignored for inline keys on P_HASH_UNSORTED pages

[xint-io]

Summary

libdb 5.3.34 has a Hash lookup defect when a key is stored inline on a legacy P_HASH_UNSORTED page and the application configures a custom comparator that preserves the database's historical comparison. Version 5.3.34 accepts this older page format without an explicit database upgrade, so the page can persist after an application moves to the newer library; opening the file alone does not trigger the defect because the comparator must be set explicitly. In __ham_getindex_unsorted, the inline-key custom-comparator branch calls the comparator but fails to store its zero result, so it reports an equal stored key as absent. Consequently, DB->get returns DB_NOTFOUND for an existing key, and DB->put(..., DB_NOOVERWRITE) can return success and persist a duplicate even though duplicates are disabled.

Environment

Item	Value
Target source	Berkeley DB 5.3.34: (August 3, 2026), commit c4811dc871e313033993e95baa5b6525057c5911
Historical producer	Berkeley DB 4.5.20: (September 20, 2006), tag v4.5.20, commit c4abd8bf6266d112e79f1544a0277337f378e36b
Reproduction build	fresh release build in source/build-issue: ../dist/configure CFLAGS='-O2 -g'
Host	Ubuntu 26.04 LTS, Linux 7.0.0-30-generic, x86_64, gcc 15.2.0
Access method	Hash on-disk format version 8, with a legacy page (P_HASH_UNSORTED)
Operations	DB->get; DB->put with DB_NOOVERWRITE

Steps to reproduce

1. Berkeley DB 4.5.20 creates and closes a Hash database with a key stored directly on a data page (an inline key).
2. Build the application against libdb 5.3.34. Before DB->open, call DB->set_h_compare with the byte_compare callback shown below.
3. The application opens the same file without running DB->upgrade or db_upgrade. The data page remains a legacy page (P_HASH_UNSORTED).
4. While that page remains P_HASH_UNSORTED, the application calls DB->get or DB->put(..., DB_NOOVERWRITE) for the stored key.
5. For the controls, repeat each read or write without DB->set_h_compare. Both read cases use the unchanged producer file. Each write case starts from a separate copy.

Complete release reproduction

Compile the following source against 4.5.20 as the producer and against 5.3.34 as the reader and writer. Save it as repro-native.c.

#include <db.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>

/*
 * Expected: DB->get finds a stored key after the comparator reports equality,
 * and DB_NOOVERWRITE returns DB_KEYEXIST without adding a second record.
 * Each control removes only DB->set_h_compare from the corresponding trigger.
 */

#define PAGE_SIZE 512		/* Page size selected by the producer. */
#define PAGE_TYPE_OFFSET 25	/* PAGE.type byte in both tested formats. */
#define P_HASHMETA 8	/* Exact libdb P_HASHMETA page-type value. */
#define P_HASH_UNSORTED 2	/* Exact libdb P_HASH_UNSORTED page-type value. */
#define P_HASH 13	/* Exact libdb P_HASH page-type value. */
#define ACCOUNT_COUNT 20

#if DB_VERSION_MAJOR > 4 || \
    (DB_VERSION_MAJOR == 4 && DB_VERSION_MINOR >= 6)
static unsigned long comparator_calls;
static unsigned long comparator_equalities;
#endif

static void
fail_db(const char *operation, int ret)
{
	fprintf(stderr, "%s failed: %s (%d)\n", operation, db_strerror(ret), ret);
	exit(2);
}

static void
set_record(DBT *key, DBT *data, char *key_buf, char *data_buf, int number)
{
	memset(key, 0, sizeof(*key));
	memset(data, 0, sizeof(*data));
	snprintf(key_buf, 16, "acct%04d", number);
	snprintf(data_buf, 32, "balance=%d", 100 * number);
	key->data = key_buf;
	key->size = (u_int32_t)strlen(key_buf);
	data->data = data_buf;
	data->size = (u_int32_t)strlen(data_buf);
}

static void
produce_legacy(const char *path)
{
	DB *db;
	DBT key, data;
	char key_buf[16], data_buf[32];
	int i, ret;

	if (access(path, F_OK) == 0) {
		fprintf(stderr, "%s already exists\n", path);
		exit(2);
	}
	if ((ret = db_create(&db, NULL, 0)) != 0)
		fail_db("db_create", ret);
	if ((ret = db->set_pagesize(db, PAGE_SIZE)) != 0) {
		(void)db->close(db, 0);
		fail_db("DB->set_pagesize", ret);
	}
	if ((ret = db->open(db, NULL, path, NULL, DB_HASH,
	    DB_CREATE, 0600)) != 0) {
		(void)db->close(db, 0);
		fail_db("DB->open", ret);
	}
	for (i = 0; i < ACCOUNT_COUNT; i++) {
		set_record(&key, &data, key_buf, data_buf, i);
		if ((ret = db->put(db, NULL, &key, &data, 0)) != 0)
			fail_db("DB->put", ret);
	}
	if ((ret = db->close(db, 0)) != 0)
		fail_db("DB->close", ret);
	printf("producer_libdb=%s\n", db_version(NULL, NULL, NULL));
	printf("producer_records=%d\n", ACCOUNT_COUNT);
}

#if DB_VERSION_MAJOR > 4 || \
    (DB_VERSION_MAJOR == 4 && DB_VERSION_MINOR >= 6)
static int
byte_compare(DB *db, const DBT *left, const DBT *right)
{
	size_t length;
	int ret;

	(void)db;
	comparator_calls++;
	length = left->size < right->size ? left->size : right->size;
	ret = memcmp(left->data, right->data, length);
	if (ret == 0)
		ret = left->size < right->size ? -1 :
		    left->size > right->size ? 1 : 0;
	if (ret == 0)
		comparator_equalities++;
	return ret;
}

static DB *
open_db(const char *path, int custom, u_int32_t flags)
{
	DB *db;
	int ret;

	if ((ret = db_create(&db, NULL, 0)) != 0)
		fail_db("db_create", ret);
	if (custom && (ret = db->set_h_compare(db, byte_compare)) != 0) {
		(void)db->close(db, 0);
		fail_db("DB->set_h_compare", ret);
	}
	if ((ret = db->open(db, NULL, path, NULL, DB_HASH, flags, 0600)) != 0) {
		(void)db->close(db, 0);
		fail_db("DB->open", ret);
	}
	return db;
}

static void
fail_system(const char *operation)
{
	perror(operation);
	exit(2);
}

static const char *
page_type_name(unsigned char type)
{
	switch (type) {
	case P_HASHMETA:
		return "P_HASHMETA";
	case P_HASH_UNSORTED:
		return "P_HASH_UNSORTED";
	case P_HASH:
		return "P_HASH";
	default:
		return NULL;
	}
}

static int
count_unsorted_pages(const char *path, const char *label)
{
	struct stat state;
	unsigned char type;
	const char *name;
	off_t offset;
	int fd, count = 0;

	if (stat(path, &state) != 0)
		fail_system("stat database");
	if (state.st_size <= 0 || state.st_size % PAGE_SIZE != 0) {
		fprintf(stderr, "database is not page aligned\n");
		exit(2);
	}
	if ((fd = open(path, O_RDONLY)) < 0)
		fail_system("open database");
	printf("%s=", label);
	for (offset = 0; offset < state.st_size; offset += PAGE_SIZE) {
		if (pread(fd, &type, 1, offset + PAGE_TYPE_OFFSET) != 1)
			fail_system("pread page type");
		name = page_type_name(type);
		if (name == NULL) {
			fprintf(stderr, "%s: unknown page type %u at offset %lld\n",
			    label, (unsigned)type, (long long)offset);
			(void)close(fd);
			exit(2);
		}
		printf(" %s", name);
		if (type == P_HASH_UNSORTED)
			count++;
	}
	printf(" unsorted_pages=%d\n", count);
	if (close(fd) != 0)
		fail_system("close database");
	return count;
}

static void
count_records(const char *path, int *records, int *target_records)
{
	DB *db;
	DBC *cursor;
	DBT key, data;
	int ret;

	u_int32_t db_flags;

	db = open_db(path, 0, DB_RDONLY);
	if ((ret = db->get_flags(db, &db_flags)) != 0)
		fail_db("DB->get_flags", ret);
	printf("db_flags=0x%x DB_DUP=%s DB_DUPSORT=%s\n", db_flags,
	    (db_flags & DB_DUP) == 0 ? "absent" : "present",
	    (db_flags & DB_DUPSORT) == 0 ? "absent" : "present");
	if ((db_flags & (DB_DUP | DB_DUPSORT)) != 0) {
		fprintf(stderr, "database unexpectedly permits duplicates\n");
		exit(2);
	}
	if ((ret = db->cursor(db, NULL, &cursor, 0)) != 0)
		fail_db("DB->cursor", ret);
	memset(&key, 0, sizeof(key));
	memset(&data, 0, sizeof(data));
	*records = *target_records = 0;
	while ((ret = cursor->get(cursor, &key, &data, DB_NEXT)) == 0) {
		(*records)++;
		if (key.size == 8 && memcmp(key.data, "acct0000", 8) == 0)
			(*target_records)++;
	}
	if (ret != DB_NOTFOUND)
		fail_db("DBcursor->get", ret);
	if ((ret = cursor->close(cursor)) != 0)
		fail_db("DBC->close", ret);
	if ((ret = db->close(db, 0)) != 0)
		fail_db("DB->close", ret);
}

static int
lookup_existing(const char *path, int custom)
{
	DB *db;
	DBT key, data;
	char key_buf[16], data_buf[32];
	const char *lookup_state;
	int ret, close_ret;

	comparator_calls = comparator_equalities = 0;
	db = open_db(path, custom, DB_RDONLY);
	set_record(&key, &data, key_buf, data_buf, 0);
	ret = db->get(db, NULL, &key, &data, 0);
	if (ret == 0 && (data.size != 9 || memcmp(data.data, "balance=0", 9) != 0)) {
		fprintf(stderr, "lookup returned an unexpected value\n");
		exit(2);
	}
	close_ret = db->close(db, 0);
	if (close_ret != 0)
		fail_db("DB->close", close_ret);
	if (ret == 0)
		lookup_state = "present";
	else if (ret == DB_NOTFOUND)
		lookup_state = "absent";
	else
		lookup_state = "error";
	if (custom)
		printf("read_trigger DB->get=%d (%s) lookup=%s comparator_calls=%lu "
		    "comparator_equalities=%lu\n", ret,
		    ret == 0 ? "unexpected" : db_strerror(ret), lookup_state,
		    comparator_calls, comparator_equalities);
	else
		printf("read_control DB->get=%d (%s) %s comparator_calls=%lu "
		    "comparator_equalities=%lu\n", ret,
		    ret == 0 ? "success" : db_strerror(ret),
		    ret == 0 ? "value=balance=0" : "value=unavailable",
		    comparator_calls, comparator_equalities);
	return ret;
}

static int
put_nooverwrite(const char *path, int custom, int *records,
    int *target_records, int *post_unsorted_pages)
{
	DB *db;
	DBT key, data;
	char key_buf[16], data_buf[32];
	int ret, close_ret;

	comparator_calls = comparator_equalities = 0;
	db = open_db(path, custom, 0);
	set_record(&key, &data, key_buf, data_buf, 0);
	data.data = (void *)"balance=999999";
	data.size = 14;
	ret = db->put(db, NULL, &key, &data, DB_NOOVERWRITE);
	close_ret = db->close(db, 0);
	if (close_ret != 0)
		fail_db("DB->close", close_ret);
	*post_unsorted_pages = count_unsorted_pages(path, "post_put_page_types");
	count_records(path, records, target_records);
	printf("%s DB->put(DB_NOOVERWRITE)=%d (%s) comparator_calls=%lu "
	    "comparator_equalities=%lu records=%d target_key_records=%d\n",
	    custom ? "trigger" : "control", ret,
	    ret == 0 ? "success" : db_strerror(ret), comparator_calls,
	    comparator_equalities, *records, *target_records);
	return ret;
}
#endif

int
main(int argc, char **argv)
{
	const char *version;
	int major, minor, patch;
#if DB_VERSION_MAJOR > 4 || \
    (DB_VERSION_MAJOR == 4 && DB_VERSION_MINOR >= 6)
	int ret, records, target_records;
	int initial_unsorted_pages, post_unsorted_pages;
#endif

	if (argc != 3 || (strcmp(argv[1], "produce") != 0 &&
	    strcmp(argv[1], "read-control") != 0 &&
	    strcmp(argv[1], "read-trigger") != 0 &&
	    strcmp(argv[1], "control") != 0 && strcmp(argv[1], "trigger") != 0)) {
		fprintf(stderr, "usage: %s produce|read-control|read-trigger|control|trigger DATABASE\n", argv[0]);
		return 2;
	}
	version = db_version(&major, &minor, &patch);
	printf("library=%s\n", version);
	if (strcmp(argv[1], "produce") == 0) {
		if (major != 4 || minor != 5 || patch != 20)
			return 2;
		produce_legacy(argv[2]);
		return 0;
	}
#if DB_VERSION_MAJOR > 4 || \
    (DB_VERSION_MAJOR == 4 && DB_VERSION_MINOR >= 6)
	if (major != 5 || minor != 3 || patch != 34)
		return 2;
	if (strcmp(argv[1], "read-control") == 0 ||
	    strcmp(argv[1], "read-trigger") == 0) {
		if (count_unsorted_pages(argv[2], "read_page_types") < 1)
			return 2;
		ret = lookup_existing(argv[2], strcmp(argv[1], "read-trigger") == 0);
		if (strcmp(argv[1], "read-control") == 0) {
			if (ret != 0)
				return 1;
			printf("read_control_result=present_key_retrieved\n");
		} else {
			if (ret != DB_NOTFOUND || comparator_equalities < 1)
				return 1;
			printf("read_trigger_result=false_not_found_reproduced\n");
		}
		return 0;
	}
	initial_unsorted_pages = count_unsorted_pages(argv[2], "initial_page_types");
	if (initial_unsorted_pages < 1)
		return 2;
	ret = put_nooverwrite(argv[2], strcmp(argv[1], "trigger") == 0,
	    &records, &target_records, &post_unsorted_pages);
	if (strcmp(argv[1], "control") == 0) {
		if (ret != DB_KEYEXIST || records != ACCOUNT_COUNT ||
		    target_records != 1 || post_unsorted_pages != initial_unsorted_pages)
			return 1;
		printf("control_result=DB_KEYEXIST_and_no_duplicate\n");
	} else {
		if (ret != 0 || comparator_equalities < 1 ||
		    records != ACCOUNT_COUNT + 1 || target_records != 2 ||
		    post_unsorted_pages != initial_unsorted_pages - 1)
			return 1;
		printf("trigger_result=duplicate_logical_key_reproduced\n");
	}
	return 0;
#else
	fprintf(stderr, "reader mode requires libdb 5.3.34\n");
	return 2;
#endif
}

Run the reproduction in a fresh directory that contains repro-native.c:

set -eu

git clone https://github.com/berkeleydb/libdb.git source
git -C source checkout --detach c4811dc871e313033993e95baa5b6525057c5911
test "$(git -C source rev-parse HEAD)" = c4811dc871e313033993e95baa5b6525057c5911
test "$(git -C source rev-parse 'v4.5.20^{commit}')" = c4abd8bf6266d112e79f1544a0277337f378e36b

mkdir legacy-source source/build-issue
git -C source archive c4abd8bf6266d112e79f1544a0277337f378e36b | tar -x -C legacy-source

(
    cd legacy-source/build_unix
    ../dist/configure --disable-shared --enable-static --disable-java \
        --disable-tcl --without-rpc CFLAGS='-O2 -g'
    make -j12
)
(
    cd source/build-issue
    ../dist/configure CFLAGS='-O2 -g'
    make -j12
)

cc -O2 -g -std=gnu99 -Ilegacy-source/build_unix repro-native.c \
    legacy-source/build_unix/libdb.a \
    $(sed -n 's/^LDFLAGS=[[:space:]]*//p' legacy-source/build_unix/Makefile | head -1) \
    $(sed -n 's/^LIBS=[[:space:]]*//p' legacy-source/build_unix/Makefile | head -1) \
    -o producer
cc -O2 -g -std=gnu99 -Isource/build-issue repro-native.c \
    source/build-issue/libdb.a \
    $(sed -n 's/^LDFLAGS=[[:space:]]*//p' source/build-issue/Makefile | head -1) \
    $(sed -n 's/^LIBS=[[:space:]]*//p' source/build-issue/Makefile | head -1) \
    -o reader

mkdir run
cd run
../producer produce base.db
cp base.db baseline.db
../reader read-control base.db
cmp baseline.db base.db
../reader read-trigger base.db
cmp baseline.db base.db
cp baseline.db control.db
cp baseline.db trigger.db
../reader control control.db
cmp baseline.db control.db
../reader trigger trigger.db
if cmp -s baseline.db trigger.db; then
    echo "trigger.db unexpectedly matches baseline.db" >&2
    exit 1
else
    cmp_status=$?
    [ "$cmp_status" -eq 1 ] || exit "$cmp_status"
fi

Expected result

The 4.6 upgrade guide describes the change from unsorted to sorted Hash pages as backward-compatible:

The format changes are entirely backward-compatible, and no database upgrades are needed.

Version 5.3.34 accepts the tested 4.5.20 Hash file and retains a lookup path for P_HASH_UNSORTED pages.

Hash comparators were added in Berkeley DB 4.6, so the 4.5.20 producer used the built-in byte-by-byte comparison. For an existing database, DB->set_h_compare requires a comparator that implements the comparison used when the database was created (dbset_h_compare.md, lines 16-22).

The byte_compare callback in the reproduction meets that requirement for every key used. It produces the same ordering and equality as the built-in comparison. Under the callback contract, a return value of 0 means that the search key and stored key are equal (lines 38-44).

DB->get returns DB_NOTFOUND only if the specified key is absent (dbget.md, line 34). DB->get must therefore retrieve the stored record. DB_NOOVERWRITE must return DB_KEYEXIST without inserting another record when the primary key already exists (dbput.md, lines 56-62).

Actual result

The 5.3.34 release build produced these results with the database created by 4.5.20:

Case	Comparator	Result
Read control	omitted	DB->get returns 0 and retrieves the existing value
Read trigger	returns 0 when comparing the search key with the stored key	DB->get returns DB_NOTFOUND
Write control	omitted	DB_NOOVERWRITE returns DB_KEYEXIST; one record has the key
Write trigger	returns 0 when comparing the search key with the stored key	DB_NOOVERWRITE returns 0; two records have identical key bytes after close and reopen

The read cases leave the producer file unchanged, and the write control leaves its copy byte-identical to the baseline. The write trigger changes the affected page from P_HASH_UNSORTED to the current P_HASH type and stores the second record. DB->get_flags reports neither DB_DUP nor DB_DUPSORT.

Analysis

Root cause

1. __ham_getindex sends a P_HASH_UNSORTED page to __ham_getindex_unsorted. That function initializes res to 1 (line 666).
2. For an inline key (H_KEYDATA), the custom-comparator branch uses h_compare only to reject a nonzero result (lines 684-689). When h_compare returns 0, the branch does not assign 0 to res, so res retains its nonzero value. __ham_getindex_unsorted sets match to 0 only when res is 0. It therefore reports this equal key as not found (lines 704-709). The built-in and sorted-page branches do assign their comparison results (lines 690-693, lines 814-824).
3. The Hash cursor calls __ham_lookup for a DB_SET operation (hash.c, lines 529-534). Because no entry is marked as found, __ham_lookup returns DB_NOTFOUND; DB->get returns that cursor result (db_iface.c, lines 802-815).
4. For DB_NOOVERWRITE, __hamc_put returns DB_KEYEXIST only after a successful lookup. The false DB_NOTFOUND instead sends the operation to __ham_add_el. In the reproduced write, __ham_add_el sorts the affected P_HASH_UNSORTED page. The sort invalidates the saved insertion position, so __ham_add_el searches again to calculate a new index. The second search finds the key, but no DB_NOOVERWRITE check is repeated. __ham_add_el then calls __ham_insertpair with the new index (sorting; second search and insertion).

Impact and scope

The false DB_NOTFOUND can make an application run its missing-record handling for a stored key. On writes, it defeats DB_NOOVERWRITE as a create-if-absent guard. DB->put returns 0 and stores a second byte-identical key although duplicate keys are disabled.

The faulty branch requires all of the following:

• a Hash file that 5.3.34 accepts, with the affected page still P_HASH_UNSORTED;
• an inline key on that page; and
• an explicit custom comparator that returns 0 when it compares the search key with the stored key.

A new Hash handle initializes h_compare to NULL, so opening the older file alone does not trigger this defect.

The reproduction uses an unmodified, native-byte-order file produced by Berkeley DB 4.5.20. It uses equal-length keys and nontransactional calls without a database environment. Equal-length off-page keys take a separate branch that passes the comparison result through __db_moff (lines 672-681); the reproduction does not exercise that branch.

After libdb sorts the affected page, later lookups no longer use the faulty P_HASH_UNSORTED branch. For the tested native-byte-order version-8 file, DB->upgrade selects the 4.6 Hash conversion and database pass. DB->upgrade uses a page-type table that sends each P_HASH_UNSORTED page to the sorting callback. If libdb 5.3.34 inserts on that page before the reported DB->get or DB->put(..., DB_NOOVERWRITE) call, the insertion also sorts the page (hash_page.c, lines 2599-2602).

In the reproduced write, sorting occurs only after the false miss. The sort prevents later misses through this branch, but it does not remove the inserted duplicate.

[gburd]

Thanks — this is an exemplary report (precise line citations, trigger + control + variant, release and debug builds agreeing, deterministic repeats). We've confirmed it and it's being worked.

Status: I verified #138, #139 and #140 directly against the source, and #140 is being treated as the highest priority (heap out-of-bounds write in release builds, since the bounds DB_ASSERT is diagnostic-only). Fixes for all five are in flight on separate branches.

Two things your reports changed beyond the individual bugs:

1. We've retracted the overclaimed docs (docs(ssi): retract overclaimed serializability guarantees #141, merged): rfc/0003 no longer asserts the commit-time pivot check is "race-free" or that markers are "bounded", and DB_TXN_SNAPSHOT's API page now carries a known-limitation note so applications don't rely on serializability alone until the fixes land with tests. Shipping a guarantee we don't fully keep was the worst part of this.
2. We're fixing the root-cause class, not just libdb 5.3.34: incomplete replication commit lock lists can violate client transaction isolation #140. That bug exists because SSI added a new lock mode (DB_LOCK_SIREAD) without auditing the pre-existing sites that enumerate modes exhaustively. We're doing that audit and adding a CI check so the class can't silently return.

We're also adding the test tiers that should have caught these: an isolation/anomaly checker that validates committed state against some serial order (including landing a write while a peer is inside commit, which is what #136 needs), and a resource-accounting soak tier (which would have caught #137 and #138 mechanically). Your --control/--late methodology is being adopted as our own bug bar.

On #136 specifically: we also noted your separate observation that two records on different pages of one B-tree detect no conflict at all, even in the control. We're treating that as potentially the more significant half and testing it explicitly.

[gburd]

Fixed on master in #144.

Your analysis was exactly right, and the investigation found a second bug in the same branch:

1. The inline-key (H_KEYDATA) custom-comparator path in __ham_getindex_unsorted called t->h_compare() and discarded the result, so res stayed at its initial 1 and an equal key was reported absent.
2. The stored-key DBT was built with the search key's length rather than the stored key's, so a search key that merely prefixed a stored key compared equal.

The fix records the comparator result and uses LEN_HKEY() for the stored key, matching what __ham_getindex_sorted already does.

Regression gate: test/db/run_hash_unsorted_cmp.sh + hash_unsorted_cmp.c. It manufactures the legacy P_HASH_UNSORTED fixture the same way run_upgrade.sh does — no old library and no committed binary blob — then asserts all four behaviours. Verified it has teeth by reverting only the engine fix:

	with fix	fix reverted
get target key	0 (found)	(pre-fix: not found)
get prefix-of-stored	DB_NOTFOUND	equal=10 (wrongly equal)
put(DB_NOOVERWRITE)	DB_KEYEXIST, 21 records, 1 copy	0 success, 22 records, 2 copies

That last row is your reported silent corruption of the uniqueness invariant, reproduced and then closed.

Also worth noting why no existing test caught this: the branch needs a legacy page and an explicitly configured comparator simultaneously — test093 sets a comparator but only over current-format sorted pages, and run_upgrade.sh reads legacy pages but never sets a comparator. test001/003/011/093 hash + btree and the upgrade test all still pass.

Thanks again — this was a clean, well-isolated report.