[Issue 10462] New: MDB_NEXT/MDB_NEXT_NODUP/MDB_PREV_NODUP on cursor returns re-inserted key after mdb_del+mdb_put empties and repopulates DUPSORT db
https://bugs.openldap.org/show_bug.cgi?id=10462
Issue ID: 10462 Summary: MDB_NEXT/MDB_NEXT_NODUP/MDB_PREV_NODUP on cursor returns re-inserted key after mdb_del+mdb_put empties and repopulates DUPSORT db Product: LMDB Version: 0.9.35 Hardware: x86_64 OS: Linux Status: UNCONFIRMED Keywords: needs_review Severity: normal Priority: --- Component: liblmdb Assignee: bugs@openldap.org Reporter: github@nicwatson.org Target Milestone: ---
Created attachment 1120 --> https://bugs.openldap.org/attachment.cgi?id=1120&action=edit C file that reproduces problem
Overview:
When a cursor is positioned on the only key in a MDB_DUPSORT database, and that key is deleted via mdb_del() then re-inserted via mdb_put() (both via the transaction API, not the cursor), subsequent mdb_cursor_get() with MDB_NEXT, MDB_NEXT_NODUP, or MDB_PREV_NODUP incorrectly returns the re-inserted key instead of MDB_NOTFOUND. This causes infinite loops in cursor traversal code.
The bug does not occur when there are multiple unique keys in the database — only when the delete empties the B-tree entirely.
Steps to Reproduce:
1. Create a MDB_DUPSORT database 2. Insert a single key with one or more dup values 3. Open a cursor and position it at the key via MDB_FIRST 4. Delete the key via mdb_del() (not mdb_cursor_del()) 5. Re-insert the same key via mdb_put() 6. Call mdb_cursor_get() with MDB_NEXT_NODUP
Reproducer program attached. (build with cc -o repro repro.c mdb.c midl.c -I. -lpthread):
Actual Results:
mdb_cursor_get(MDB_NEXT_NODUP) returns MDB_SUCCESS and the cursor is positioned at the re-inserted key. In a traversal loop, this causes an infinite loop.
Expected Results:
mdb_cursor_get(MDB_NEXT_NODUP) should return MDB_NOTFOUND since there are no more unique keys after the cursor's position.
Root Cause:
When mdb_del() removes the only key, mdb_rebalance() empties the B-tree and clears C_INITIALIZED on all cursors (mdb.c line ~8407). The mdb_cursor_del0() function had already set C_DEL on other cursors at the same position (line ~8555). After mdb_put() re-inserts data, mdb_cursor_next() sees !C_INITIALIZED and falls through to mdb_cursor_first() (line 5967-5968), ignoring the fact that C_DEL indicates the cursor's entry was deleted. The same issue affects mdb_cursor_prev() (line 6049-6053).
Proposed Fix:
In mdb_cursor_next() and mdb_cursor_prev(), when C_INITIALIZED is not set, check for C_DEL first. If C_DEL is set, the cursor was positioned at a deleted entry and should not fall through to first/last:
// mdb_cursor_next, line ~5967: if (!(mc->mc_flags & C_INITIALIZED)) { if (mc->mc_flags & C_DEL) return MDB_NOTFOUND; return mdb_cursor_first(mc, key, data); }
// mdb_cursor_prev, line ~6049: if (!(mc->mc_flags & C_INITIALIZED)) { if (mc->mc_flags & C_DEL) return MDB_NOTFOUND; rc = mdb_cursor_last(mc, key, data);
Build Date & Platform: LMDB 0.9.35, Linux 6.6.87, x86_64. Also confirmed on FreeBSD 14.3 with LMDB 0.9.33.
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #1 from Howard Chu hyc@openldap.org --- Please demonstrate the infinite loop, as the code you provided doesn't do that.
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #2 from Howard Chu hyc@openldap.org --- Also please demonstrate the working case, when the DB is not emptied.
https://bugs.openldap.org/show_bug.cgi?id=10462
Howard Chu hyc@openldap.org changed:
What |Removed |Added ---------------------------------------------------------------------------- Resolution|--- |INVALID Status|UNCONFIRMED |RESOLVED
--- Comment #3 from Howard Chu hyc@openldap.org --- Never mind the above requests.
The code works as designed. Once a cursor's state is ~C_INITIALIZED, any other former state is obsolete and irrelevant.
Any MDB_NEXT op is then always treated as MDB_FIRST.
https://bugs.openldap.org/show_bug.cgi?id=10462
Quanah Gibson-Mount quanah@openldap.org changed:
What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |VERIFIED
https://bugs.openldap.org/show_bug.cgi?id=10462
github@nicwatson.org github@nicwatson.org changed:
What |Removed |Added ---------------------------------------------------------------------------- Attachment #1120|0 |1 is obsolete| |
--- Comment #4 from github@nicwatson.org github@nicwatson.org --- Created attachment 1121 --> https://bugs.openldap.org/attachment.cgi?id=1121&action=edit MDB_NEXT_NODUP infinite loop with del + put in iteration loop
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #5 from github@nicwatson.org github@nicwatson.org --- Created attachment 1122 --> https://bugs.openldap.org/attachment.cgi?id=1122&action=edit multi-key case: works correctly
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #6 from github@nicwatson.org github@nicwatson.org --- Attached are the two requested test cases.
Infinite Loop (single-key DUPSORT db):
The original reproducer only called MDB_NEXT_NODUP once after the del+put. The infinite loop occurs when del+put happens inside a traversal loop -- each iteration empties and refills the tree, so every MDB_NEXT_NODUP falls back to mdb_cursor_first() and the loop never terminates.
See attached repro1.c.
Output:
start: key -> val1 BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 1) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 2) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 3) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 4) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 5) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 6) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 7) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 8) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 9) BUG: NEXT_NODUP returned SUCCESS -- key=key val=newval (iteration 10) BUG CONFIRMED: infinite loop, aborting.
Working case (multi-key DUPSORT db):
Same traversal pattern but with two keys. The delete never empties the tree, so C_INITIALIZED stays set and MDB_NEXT_NODUP follows the normal code path. No infinite loop.
See attached repro_multi.c.
Output:
visit 1: aaa -> val1 visit 2: bbb -> val2 done after 2 keys (expected 2)
Explanation:
The ~C_INITIALIZED -> MDB_FIRST fallback is the right default for a freshly opened cursor. But after mdb_del empties the tree, mdb_cursor_del0 sets C_DEL on other cursors at the same position to signal that their entry was deleted. mdb_rebalance then clears C_INITIALIZED because the tree is now empty.
The cursor now has C_DEL set but C_INITIALIZED cleared. The C_DEL flag carries meaningful state -- it tells mdb_cursor_next that the cursor's record was deleted and certain advances should be suppressed (this is already checked at line 5964 for MDB_NEXT_DUP). But the !C_INITIALIZED branch at line 5967 ignores C_DEL entirely, discarding that signal.
The result: MDB_NEXT_NODUP on a cursor whose entry was deleted behaves identically to MDB_FIRST, which is incorrect. In a traversal loop where each iteration deletes and re-inserts the sole key, this creates an infinite loop that is inescapable from user code.
The inconsistency is that deleting one of two keys works correctly (cursor advances to the next key), but deleting the only key does not (cursor rewinds to the beginning). The difference is solely whether the tree happened to empty, which is an internal detail invisible to the caller.
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #7 from Howard Chu hyc@openldap.org ---
The cursor now has C_DEL set but C_INITIALIZED cleared. The C_DEL flag
carries meaningful state
No. An uninitialized cursor has no meaningful state. A cursor on an empty DB has no meaningful state.
This bug report is invalid and the ticket is closed.
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #8 from github@nicwatson.org github@nicwatson.org --- The NEXT to FIRST fallback for uninitialized cursors is reasonable when the cursor has never been positioned. But mdb_rebalance clears C_INITIALIZED on cursors that were positioned, as evidenced by C_DEL still being set from the preceding mdb_cursor_del0. The combination !C_INITIALIZED && C_DEL represents a cursor that was valid, had its position deleted, and then had its initialization flag cleared because the tree emptied. In this state, NEXT returning FIRST creates an infinite loop.
The application has no way to detect or prevent this: there is no API to query cursor flags, the only probe (MDB_GET_CURRENT) has side effects that break other cursor operations, and whether the tree empties depends on internal B-tree state that the application cannot observe. An application doing a straightforward delete-and-reinsert in a loop with a cursor will hang with no indication of what went wrong.
Returning MDB_NOTFOUND when C_DEL is set preserves the existing NEXT to FIRST behavior for genuinely uninitialized cursors while fixing the infinite loop.
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #9 from Howard Chu hyc@openldap.org --- As in #10463, your inability to use LMDB correctly is not a bug in LMDB, and the ITS is not a help forum.
Deleting and reinserting all the exact same keys sounds like good way to waste a huge amount of time but I have no interest in exploring your use case here in the ITS.
https://bugs.openldap.org/show_bug.cgi?id=10462
Quanah Gibson-Mount quanah@openldap.org changed:
What |Removed |Added ---------------------------------------------------------------------------- Keywords|needs_review |
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #10 from github@nicwatson.org github@nicwatson.org --- Created attachment 1126 --> https://bugs.openldap.org/attachment.cgi?id=1126&action=edit more realistic scenario
Here is a more realistic scenario.
A DUPSORT database is used as a per-topic event index. A consumer opens a cursor and iterates topics with MDB_NEXT_NODUP, deleting consumed entries. In the same write transaction, new events arrive under a different topic. When the consumer deletes the last remaining topic and calls MDB_NEXT_NODUP, the cursor returns SUCCESS on the newly-inserted (different) topic instead of MDB_NOTFOUND.
/* Seed: one topic "alerts" with two events */ key = "alerts"; put(key, "event-001"); put(key, "event-002");
/* Consumer txn */ cursor_get(cursor, MDB_FIRST); /* positions on "alerts" */ mdb_del(txn, dbi, "alerts", NULL); /* delete all entries for this topic */ mdb_put(txn, dbi, "metrics", "cpu"); /* new event, different topic */ cursor_get(cursor, MDB_NEXT_NODUP); /* BUG: returns "metrics", should be NOTFOUND */
mdb_del sets C_DEL on tracking cursors (line 8569/8642), but when the delete empties the database, mdb_cursor_pop clears C_INITIALIZED (line 5490). In mdb_cursor_next, the !C_INITIALIZED check (line 5967) runs before the C_DEL check (line 5998), so it calls mdb_cursor_first() -- finding the newly-inserted key -- instead of returning MDB_NOTFOUND.
Full reproducer attached.
https://bugs.openldap.org/show_bug.cgi?id=10462
--- Comment #11 from Howard Chu hyc@openldap.org ---
mdb_del sets C_DEL on tracking cursors (line 8569/8642), but when the delete empties the database, mdb_cursor_pop clears C_INITIALIZED (line 5490). In mdb_cursor_next, the !C_INITIALIZED check (line 5967) runs before the C_DEL check (line 5998), so it calls mdb_cursor_first() -- finding the newly-inserted key -- instead of returning MDB_NOTFOUND.
Clearing C_INITIALIZED means the cursor is uninitialized. An uninitialized structure has no meaningful state. That is the definition of uninitialized.
A cursor is a structure to point at a location in a DB. In an empty DB there is nothing to point at.
The C_INITIALIZED check is done first because if it's not set, nothing else matters. Again, that's what being uninitialized means.
Quit trying to change what isn't broken in LMDB. Fix your stupid application.
Finish all your deletes before doing any inserts. Or use a counter to track how many records are present. And quit using the ITS for non-bug discussion. Use the openldap-technical mailing list for software help, which is what you're asking for here.
-
openldap-its＠openldap.org