openldap-bugs June 2026

openldap-bugs@openldap.org

1 participants
67 discussions

[Issue 10526] New: back-mdb: mdb_idl_intersection is O(ID-gap), not O(n), when a short candidate list is ANDed with a range
by openldap-its＠openldap.org 02 Jul '26

02 Jul '26

https://bugs.openldap.org/show_bug.cgi?id=10526 Issue ID: 10526 Summary: back-mdb: mdb_idl_intersection is O(ID-gap), not O(n), when a short candidate list is ANDed with a range Product: OpenLDAP Version: 2.5.20 Hardware: All OS: Linux Status: UNCONFIRMED Keywords: needs_review Severity: normal Priority: --- Component: backends Assignee: bugs(a)openldap.org Reporter: choeger(a)open-xchange.com Target Milestone: --- Created attachment 1157 --> https://bugs.openldap.org/attachment.cgi?id=1157&action=edit the patch above ---------------------------------------------------------------------------- Note The below report including the patch has been generated by Claude Opus 4.8. I built packages based on the OpenLDAP-LTB project version v2.5.20 and verified in our problematic production deployment. This refers to the following thread: https://lists.openldap.org/hyperkitty/list/openldap-technical@openldap.org/… End Note ---------------------------------------------------------------------------- SUMMARY ------- AND-filter searches can be orders of magnitude slower than the size of their result set warrants. mdb_idl_intersection() falls back to a generic element-at-a-time merge whose cost is proportional to the distance in ID space between candidate IDs, not to the number of candidates. When one operand is a range (any indexed term matching more than the IDL range threshold, e.g. a common objectClass) and the other is a short list of IDs that are widely separated, the merge walks the range one ID at a time across the entire gap. This is common in practice: filters of the form (&(objectClass=X)(someAttr=val)...) hit it whenever someAttr matches a small number of entries whose IDs happen to be far apart and objectClass=X is stored as a range that does not fully cover that span. ENVIRONMENT ----------- - OpenLDAP 2.5.19, slapd back-mdb. - ~4.6M entries. An attribute is indexed eq and a given value normally matches exactly one entry. A common objectClass value matches ~2,000,000 entries and is therefore stored as an IDL range (it exceeds MDB_idl_db_max; see servers/slapd/back-mdb/idl.c:467, "No room, convert to a range"). SYMPTOM ------- Query: (&(objectClass=<common>)(<almost-unique-attr>=<value>)(<attr>=*)) The filter resolves to a single entry in all cases. - When <almost-unique-attr>=<value> matches ONE entry: the search is very fast. - When it matches TWO entries whose IDs are far apart (here 1759457 and 2731413, a gap of ~972,000), the same search becomes roughly 20x slower, even though the AND still yields a single entry. perf shows nearly all CPU in mdb_idl_next() and mdb_idl_intersection(). Enabling LDAP_DEBUG_FILTER and inspecting the per-term candidate counts confirms the broad term is a range; gdb in mdb_idl_intersection shows idmin/idmax equal to the two widely separated IDs. Neither index_hash64 nor dropping the substring index changes the timing; the cost is not in the index key lookups, it is in the candidate intersection. ROOT CAUSE ---------- In servers/slapd/back-mdb/idl.c, mdb_idl_intersection() has fast paths for both-ranges, for idmin==idmax, and for "range fully covers list". Anything that misses those falls into a generic merge: cursora = cursorb = idmin; ida = mdb_idl_first( a, &cursora ); idb = mdb_idl_first( b, &cursorb ); cursorc = 0; while( ida <= idmax || idb <= idmax ) { if( ida == idb ) { a[++cursorc] = ida; ida = mdb_idl_next( a, &cursora ); idb = mdb_idl_next( b, &cursorb ); } else if ( ida < idb ) { ida = mdb_idl_next( a, &cursora ); } else { idb = mdb_idl_next( b, &cursorb ); } } For a range, mdb_idl_next() returns ++(*cursor), i.e. consecutive integers. So when b is a range that does not fully cover list a (the "range fully covers list" shortcut is missed because the non-matching list member lies outside the range bounds), the loop advances idb one integer at a time from idmin to idmax. With the two matches ~972,000 apart, that is ~972,000 iterations per search. The single-match case is fast only because it lands on the idmin==idmax or "range fully covers list" shortcut; it has nothing to do with the index. The same loop is also O(gap) for the list-vs-list case (a populous list ANDed with a short, widely-spread list): it walks the populous list across the gap. mdb_idl_intersection() is reached for every non-first term of an AND filter via list_candidates() in servers/slapd/back-mdb/filterindex.c. REPRODUCTION (without specific data) ------------------------------------ 1. Load a DB where some indexed attribute value V matches more than MDB_idl_db_max entries (so V is stored as a range), and where the range's [lo,hi] does not span the whole DB. 2. Pick another indexed attribute A and two entries that share a value W on A, such that one of them is NOT in V's range and their IDs are far apart. 3. Time (&(A=W)) vs (&(V)(A=W)) repeatedly. The second is dramatically slower despite returning fewer (or equal) entries. A standalone harness that extracts the real 2.5.19 IDL routines, cross-checks a fixed mdb_idl_intersection against brute-force set intersection, and benchmarks the pathology is attached (idl_intersection_test.c). PROPOSED FIX ------------ mdb_idl_intersection() never needs to iterate a range. After the existing "range fully covers list" shortcut: - If b is a range, the result is just the members of list a that fall within [first,last]: iterate the (bounded) list, test each against the bounds. O(|a|) instead of O(range width). - If both a and b are lists, keep the sorted merge but, when the cursors diverge, binary-search (mdb_idl_search) the lagging list forward to the other's current value rather than stepping one element at a time. Each catch-up becomes O(log n) instead of O(gap). Result ordering (ascending) and the a[0] count convention are preserved, as is the swap/copy-back behaviour. The in-place writes are safe: the write index (cursorc, number of matches) never exceeds the read index. Patch against OPENLDAP_REL_ENG_2_5_19 (applies cleanly to RE25 and master HEAD as well); also attached as mdb-idl-intersection.patch: --- a/servers/slapd/back-mdb/idl.c +++ b/servers/slapd/back-mdb/idl.c @@ -759,23 +759,49 @@ goto done; } - /* Fine, do the intersection one element at a time. - * First advance to idmin in both IDLs. + /* If b is a range (and does not fully cover a, handled above), the + * intersection is just the elements of list a that fall within the + * range bounds. Walk the (bounded) list, never the (potentially huge) + * range: O(|a|), not O(range width). */ - cursora = cursorb = idmin; - ida = mdb_idl_first( a, &cursora ); - idb = mdb_idl_first( b, &cursorb ); - cursorc = 0; + if ( MDB_IDL_IS_RANGE( b ) ) { + ID lo = MDB_IDL_RANGE_FIRST( b ); + ID hi = MDB_IDL_RANGE_LAST( b ); + cursorc = 0; + for ( ida = mdb_idl_first( a, &cursora ); + ida != NOID; + ida = mdb_idl_next( a, &cursora ) ) { + if ( ida < lo ) + continue; + if ( ida > hi ) + break; + a[++cursorc] = ida; + } + a[0] = cursorc; + goto done; + } - while( ida <= idmax || idb <= idmax ) { - if( ida == idb ) { + /* Both a and b are lists. Sorted-merge intersection, but when the two + * cursors diverge, binary-search the lagging list forward to the other's + * current value instead of stepping one element at a time. This keeps a + * large gap in one list (e.g. two widely separated matches intersected + * against a populous list) from forcing a linear scan of the other list + * across the whole gap: each catch-up is O(log n) rather than O(gap). + */ + cursora = mdb_idl_search( a, idmin ); + cursorb = mdb_idl_search( b, idmin ); + cursorc = 0; + while ( cursora <= a[0] && cursorb <= b[0] ) { + ida = a[cursora]; + idb = b[cursorb]; + if ( ida == idb ) { a[++cursorc] = ida; - ida = mdb_idl_next( a, &cursora ); - idb = mdb_idl_next( b, &cursorb ); + cursora++; + cursorb++; } else if ( ida < idb ) { - ida = mdb_idl_next( a, &cursora ); + cursora = mdb_idl_search( a, idb ); } else { - idb = mdb_idl_next( b, &cursorb ); + cursorb = mdb_idl_search( b, ida ); } } a[0] = cursorc; TESTING ------- Using the attached harness (the patched function is byte-for-byte the shipped code): - Correctness: 400,000 randomized trials (two seeds) over zero/list/range operands of varied sizes and gaps, in both argument orders, cross-checked against brute-force set intersection. Zero mismatches. - The reported case, list {1759457, 2731413} intersected with a 2,000,000-entry range [1 .. 2731412] that does not cover the upper member, 1200 iterations: original: 2.54 s, 1,166,348,400 mdb_idl_next calls, result count = 1 fixed: ~0 s, 1,200 mdb_idl_next calls, result count = 1 - Single-value baseline (original): ~0 s, 0 mdb_idl_next calls, confirming the original is fast only for the single-match case. -- You are receiving this mail because: You are on the CC list for the issue.

1 21

[Bug 9223] New: Add support for incremental backup
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=9223 Bug ID: 9223 Summary: Add support for incremental backup Product: LMDB Version: unspecified Hardware: All OS: All Status: UNCONFIRMED Severity: normal Priority: --- Component: liblmdb Assignee: bugs(a)openldap.org Reporter: quanah(a)openldap.org Target Milestone: --- For LMDB 1.0, add support for incremental backups -- You are receiving this mail because: You are on the CC list for the bug.

1 6

[Issue 10518] New: Every write transaction leaks a mutex on Windows
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=10518 Issue ID: 10518 Summary: Every write transaction leaks a mutex on Windows Product: LMDB Version: unspecified Hardware: x86_64 OS: Windows Status: UNCONFIRMED Keywords: needs_review Severity: normal Priority: --- Component: liblmdb Assignee: bugs(a)openldap.org Reporter: bhargavabhat(a)gmail.com Target Milestone: --- Created attachment 1152 --> https://bugs.openldap.org/attachment.cgi?id=1152&action=edit Create and use the mutex for the duration of the env I see that on master3 branch, every write transaction leaks a mutex. LMDB creates a new mutex on every non-read-only transaction in `mdb_txn_renew0`. In `mdb_txn_end`, when the write transaction finishes, it sets `mode` to 0 and unlocks it. ``` if (!txn->mt_parent) { env->me_txn = NULL; mode = 0; if (env->me_txns) UNLOCK_MUTEX(env->me_wmutex); } ``` Later, it does this. ``` if (mode & MDB_END_FREE) { if (!F_ISSET(txn->mt_flags, MDB_TXN_RDONLY)) pthread_mutex_destroy(&txn->mt_child_mutex); // never reached free(txn); } ``` So we just don't close the mutex. It's probably not a big deal on non-Windows platforms, but on Windows, the number of handles owned by the process keeps increasing which limits the total number of write transactions we can do in the lifetime of the process. I didn't really understand why we need to create a mutex on every non-read-only transaction. Can we just tie the lifetime of the mutex to the environment instead of the transaction? I'm attaching a patch which tries to fix it. -- You are receiving this mail because: You are on the CC list for the issue.

1 9

[Issue 9496] New: Some writes missing from database
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=9496 Issue ID: 9496 Summary: Some writes missing from database Product: LMDB Version: unspecified Hardware: All OS: All Status: UNCONFIRMED Severity: normal Priority: --- Component: liblmdb Assignee: bugs(a)openldap.org Reporter: igfoo(a)github.com Target Milestone: --- With the attached test program, some of my database writes appear not to actually be written to the database. For example, a run may look like this: $ ./run.sh All done. All finished 1802 test.txt foo_200 is missing bar_200 is missing foo_404 is missing bar_404 is missing foo_407 is missing bar_407 is missing The script that I am using to run the program is below. This is using mdb.master 52bc29ee2efccf09c650598635cd42a50b6ecffe on Linux, with an ext4 filesystem. Is this an LMDB bug, or is there a bug in my code? Thanks Ian #!/bin/sh set -e if ! [ -d lmdb ] then rm -rf lmdb git clone https://github.com/LMDB/lmdb.git INSTALL_DIR="`pwd`/inst" cd lmdb/libraries/liblmdb make install prefix="$INSTALL_DIR" cd ../../.. fi gcc -Wall -Werror -Iinst/include loop.c inst/lib/liblmdb.a -o loop -pthread rm -f test.db test.db-lock ./loop echo "All finished" mdb_dump -np test.db > test.txt wc -l test.txt for i in `seq 100 999` do if ! grep -q "foo_$i" test.txt then echo "foo_$i is missing" fi if ! grep -q "bar_$i" test.txt then echo "bar_$i is missing" fi done -- You are receiving this mail because: You are on the CC list for the issue.

1 18

[Issue 9619] New: mdb_env_copy2 with MDB_CP_COMPACT in mdb.master3 produces corrupt mdb file
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=9619 Issue ID: 9619 Summary: mdb_env_copy2 with MDB_CP_COMPACT in mdb.master3 produces corrupt mdb file Product: LMDB Version: 0.9.29 Hardware: All OS: Windows Status: UNCONFIRMED Severity: normal Priority: --- Component: liblmdb Assignee: bugs(a)openldap.org Reporter: kriszyp(a)gmail.com Target Milestone: --- When copying an LMDB database with mdb_env_copy2 with the MDB_CP_COMPACT with mdb.master3, the resulting mdb file seems to be corrupt and when using it in LMDB, I get segmentation faults. Copying without the compacting flag seems to work fine. I apologize, I know this is not a very good issue report, as I haven't had a chance to actually narrow this down to a more reproducible/isolated case, or look for how to patch. I thought I would report in case there are any ideas on what could cause this. The segmentation faults always seem to be memory write faults (as opposed to try fault on trying to read). Or perhaps the current backup/copying functionality is eventually going to be replaced by incremental backup/copying anyway (https://twitter.com/hyc_symas/status/1315651814096875520). I'll try to update this if I get a chance to investigate more, but otherwise feel free to ignore/consider low-priority since the work around is easy. -- You are receiving this mail because: You are on the CC list for the issue.

1 14

[Issue 10395] New: Support multiple readers on uncommitted changes
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=10395 Issue ID: 10395 Summary: Support multiple readers on uncommitted changes Product: LMDB Version: unspecified Hardware: All OS: All Status: UNCONFIRMED Keywords: needs_review Severity: normal Priority: --- Component: liblmdb Assignee: bugs(a)openldap.org Reporter: renault.cle(a)gmail.com Target Milestone: --- Created attachment 1086 --> https://bugs.openldap.org/attachment.cgi?id=1086&action=edit A patch to support multiple readers on uncommitted changes Hello, The attached patch is not meant to be merged immediately into LMDB. Still, it demonstrates how I added a helpful feature to the key-value store: reading uncommitted changes from multiple transactions. I am conscious that the patch still requires some work and uses non-C99 features, i.e., atomics are C11, which could be a blocker for it to be merged upstream. I would also be delighted to merge these changes under a flag/define to ensure we don't impact other users with non-C99 stuff. The main feature we need at Meilisearch is to read uncommitted changes from multiple threads, compute parallel post-processing of different data structures [1], and speed up the search requests. We could have done the post-processing in a following transaction by opening multiple read transactions, but this would mean that the post-processed data structure would not include newly inserted or modified document IDs. Both data structures would be desync. Regarding the design choice, I decided to follow the same design as the nested write transactions: use the parent argument of the mdb_txn_begin [2], and allow the MDB_RDONLY flag, which was disallowed when the parent argument was non-NULL [3]. I find it clear enough that, by calling the mdb_txn_begin function with these arguments, you can call it multiple times (I need to update the doc) to obtain nested read-only transactions from the parent write transaction. ret = mdb_txn_begin(env, parent_txn, MDB_RDONLY, new_nested_rtxn); Note that this early proposal lacks security and error handling. The generated transactions are fake-read-only and actually write transactions that share the underlying parent allocations and data structures. This is unsafe and must be changed or reviewed carefully, but most importantly, we need to add read-only capabilities to these transactions to disallow writes. Using a Rust wrapper on top of LMDB, I wrapped the fake read-only transactions into ReadTxn, which disallows any writes at compile time. However, I haven't checked the conflict database creations or openings. The main issues I encountered were concurrent free of the main shared data structures when the different threads owning the transactions were dropping the transactions simultaneously. So, I decided to implement the equivalent of an ARC to free resources only when the last nested transaction was freed. I can share numbers about how this feature improves the post-processing by 4x-9x or from 1200s to 120s [1]. You can look at this PR, which I would be happy to merge once an improved version of this patch lands on LMDB upstream. I would be very happy if you could guide me a bit on how I could improve this patch to make it mergeable into LMDB. We want to contribute useful features like this to LMDB and not keep a deviant fork. LMDB works great; we are happy about it, and its performance is predictable. Have a lovely week, kero [1]: https://github.com/meilisearch/meilisearch/pull/5307 [2]: https://github.com/LMDB/lmdb/blob/14d6629bc8a9fe40d8a6bee1bf71c45afe7576b6/… [3]: https://github.com/LMDB/lmdb/blob/14d6629bc8a9fe40d8a6bee1bf71c45afe7576b6/… -- You are receiving this mail because: You are on the CC list for the issue.

1 32

[Issue 8346] lmdb memory leak with MDB_VL32
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=8346 Quanah Gibson-Mount <quanah(a)openldap.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |VERIFIED -- You are receiving this mail because: You are on the CC list for the issue.

1 0

[Issue 8174] mdb_drop(,MAIN_DBI,) leaks pages of named DBs
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=8174 Quanah Gibson-Mount <quanah(a)openldap.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |VERIFIED -- You are receiving this mail because: You are on the CC list for the issue.

1 0

[Issue 10428] New: Make larger key sizes available at compile time
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=10428 Issue ID: 10428 Summary: Make larger key sizes available at compile time Product: LMDB Version: unspecified Hardware: All OS: All Status: UNCONFIRMED Keywords: needs_review Severity: normal Priority: --- Component: liblmdb Assignee: bugs(a)openldap.org Reporter: marlowsd(a)gmail.com Target Milestone: --- I discovered that I can increase the key size to 1982 bytes with the following patch ``` *************** *** 1053,1059 **** #define METADATA(p) ((void *)((char *)(p) + PAGEHDRSZ)) /** ITS#7713, change PAGEBASE to handle 65536 byte pages */ ! #define PAGEBASE ((MDB_DEVEL) ? PAGEHDRSZ : 0) /** Number of nodes on a page */ #define NUMKEYS(p) ((MP_LOWER(p) - (PAGEHDRSZ-PAGEBASE)) >> 1) --- 1054,1061 ---- #define METADATA(p) ((void *)((char *)(p) + PAGEHDRSZ)) /** ITS#7713, change PAGEBASE to handle 65536 byte pages */ ! #define PAGEBASE PAGEHDRSZ ! // #define PAGEBASE ((MDB_DEVEL) ? PAGEHDRSZ : 0) /** Number of nodes on a page */ #define NUMKEYS(p) ((MP_LOWER(p) - (PAGEHDRSZ-PAGEBASE)) >> 1) ``` and then passing `-DMDB_MAXKEYSIZE=0` at compile time. I didn't want to use `MDB_DEVEL` because this is for a production use case. Is this feature ready to be widely used? If so, could it be given a compile-time (or run-time) flag please? Background: this is for Glean (https://github.com/facebookincubator/Glean/pull/663), this page explains our DB structure https://glean.software/docs/implementation/db/. -- You are receiving this mail because: You are on the CC list for the issue.

1 6

[Issue 8579] LMDB: me_fd should be O_CLOEXEC on POSIX systems
by openldap-its＠openldap.org 30 Jun '26

30 Jun '26

https://bugs.openldap.org/show_bug.cgi?id=8579 Quanah Gibson-Mount <quanah(a)openldap.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |VERIFIED -- You are receiving this mail because: You are on the CC list for the issue.

1 0

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

openldap-bugs June 2026