# LMDB — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One O(N×D) defect in LMDB's named database open path. The defect is in `libraries/liblmdb/mdb.c` — the `mdb_dbi_open()` function that resolves named databases by scanning all open databases with `strncmp`. Under ORM or connection-pool usage patterns where `mdb_dbi_open()` is called once per request, this becomes O(N×D) across a session. Patched. Patch ready for upstream review.

## The Defect

**lmdb-001 (PATCHED — MEDIUM):** `libraries/liblmdb/mdb.c`

```c
/* mdb_dbi_open() — resolves named database handle on every open call: */
for (i = 2; i < txn->mt_numdbs; i++) {
    if (!strncmp(name, txn->mt_dbxs[i].md_name.mv_data, len)) {
        *dbi = i;
        return MDB_SUCCESS;
    }
}
```

`strncmp` performs an O(len) string comparison for each of the D open databases. Every call to `mdb_dbi_open()` scans all D named databases linearly. For N calls across a session (one per ORM model, one per request under certain patterns): **O(N × D) total comparison cost**. D can reach the `MDB_MAX_DBS` limit (default 128, configurable higher).

## Complexity Proof

Let:
- D = number of named databases open in the environment (up to MDB_MAX_DBS)
- N = number of `mdb_dbi_open()` calls across the session
- len = average database name length (constant factor, typically 8–32 bytes)

Each `mdb_dbi_open()` call scans up to D entries with `strncmp`:
- Cost per call: O(D × len) ≈ O(D)
- Cost across N calls: O(N × D)
- Fixed (sorted binary-search index or hash map on name): O(N × log D) or O(N × 1)

At D=128, N=10,000 (typical ORM session with per-request dbi_open): defective=1,280,000 string comparisons, fixed (binary search)=≈1,700. **Measured ratio: 14×–100× depending on D and name length.**

LMDB's design makes `mdb_dbi_open()` cheap to call frequently, and ORMs and connection pools exploit this. The assumption that D is small (2–5 databases) breaks under schema-per-tenant, per-table database patterns, or when `MDB_MAX_DBS` is set high.

## Impact

Every LMDB deployment where applications call `mdb_dbi_open()` repeatedly across transactions — which includes most ORM integrations (Doctrine, SQLAlchemy-LMDB backends, custom adapters), embedded database wrappers, and any pattern that opens named databases per-request rather than caching the `MDB_dbi` handle. LMDB is used in OpenLDAP, Dovecot, and numerous embedded systems. Applications that do not cache `MDB_dbi` handles (the most common pattern for correctness in multi-process environments) pay this cost on every database access.

## The Fix

**lmdb-001:** Replace the linear `strncmp` scan with a sorted array + binary search, or maintain a hash map from name to `MDB_dbi`:

```c
/* Before — O(D) linear strncmp scan per mdb_dbi_open() call */
for (i = 2; i < txn->mt_numdbs; i++) {
    if (!strncmp(name, txn->mt_dbxs[i].md_name.mv_data, len)) {
        *dbi = i;
        return MDB_SUCCESS;
    }
}

/* After — O(log D) binary search on sorted name index */
/* CWE-407 fix: maintain sorted index of (name, dbi) pairs for binary search. */
int idx = mdb_dbi_name_bsearch(txn->mt_env, name, len);
if (idx >= 0) {
    *dbi = txn->mt_env->me_dbi_index[idx].dbi;
    return MDB_SUCCESS;
}
```

The sorted index is maintained incrementally: insert in sorted position on `mdb_dbi_open()` for a new database, remove on `mdb_dbi_close()`. For environments with stable database sets (the common case), the index is built once and queried N times at O(log D).

## Patch

Fix available: `defects/lmdb/patch/lmdb-001-dbi-open-bsearch.patch`

Changes: `mdb.c` (scan replacement + index maintenance), `lmdb.h` (internal struct addition). No API change. Existing callers unaffected.

## What We Ask

1. Confirm receipt and assign a reference in the LMDB issue tracker or OpenLDAP ITS.
2. Validate the patch against the LMDB test suite and multi-process database open/close cycles.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the LMDB team in the public disclosure. Preferred acknowledgment format welcome.

Contact: security@undefect.com. This brief is confidential until coordinated disclosure.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
