https://bugs.kde.org/show_bug.cgi?id=434926
--- Comment #21 from James C. Owens <[email protected]> --- I have been working on index-removal batching and on reconciling the index against the filesystem, which took me through WriteTransaction::removeRecursively(). I think there is a second reading of the backtrace in this report worth recording. This is not an argument against the corruption diagnosis -- it is that the signature here is reproducible with a database that is entirely well-formed, so the backtrace alone does not distinguish the two. The signature reproduces without any corruption ----------------------------------------------- removeRecursively(quint64) has no depth cap, no visited set and no cycle detection. Its only guard is "if (id)". So it is unbounded by construction, whatever malformed the tree -- a cycle in the id tree is enough. Building one takes two ordinary addDocument() calls: Database db(dir.path()); db.open(Database::CreateDatabase); const quint64 idA = 900001, idB = 900002; Document a; a.setId(idA); a.setParentId(idB); a.setUrl(...); a.addTerm("t"); Document b; b.setId(idB); b.setParentId(idA); b.setUrl(...); b.addTerm("t"); { Transaction tr(&db, Transaction::ReadWrite); tr.addDocument(a); tr.addDocument(b); tr.commit(); } // control: the cycle is real -- documentUrl(idA) returns empty because // the walk to the root never terminates { Transaction tr(&db, Transaction::ReadWrite); tr.removeRecursively(idA); // never returns tr.commit(); } Against pristine 6.16.0 this takes SIGSEGV after 87,196 recursive frames (~96 bytes of stack per frame on the default 8 MB stack). The backtrace has the same shape as the one in comment 0: the innermost frames are inside liblmdb beneath a DB getter, and everything above them is an unbroken wall of Baloo::WriteTransaction::removeRecursively. #0-#3 liblmdb ... mdb_get #4 Baloo::IdTreeDB::get #5 Baloo::DocumentUrlDB::getChildren #6 Baloo::WriteTransaction::removeRecursively #7... Baloo::WriteTransaction::removeRecursively (x 87,196) Why stack exhaustion here always presents as an LMDB fault ---------------------------------------------------------- At the moment the recursion runs out of stack, the deepest call in flight is whichever LMDB read the recursion happens to be doing. So the fault lands inside liblmdb regardless of the cause, and the top frames of the backtrace look like a bad read from the database even when the database is fine. In the core above, the faulting address was adjacent to the stack pointer (si_addr = 0x7fff35777fe8, rsp = 0x7fff35777fe0), while every liblmdb mapping was in the 0x7f3392... range -- hundreds of gigabytes away in the address space. That is a stack overflow, not a wild pointer into a mapping. If anyone still has a core from this crash, those two things separate the cases immediately: - si_addr at or near rsp, with a very large total frame count: stack exhaustion in the recursion. The database may be perfectly valid. - si_addr inside the LMDB mapping, with a normal frame count: a genuine bad read. The 56 consecutive removeRecursively frames in comment 0 (#8 through #63) are consistent with either, since a backtrace of a deep recursion is usually truncated by the reporting tool. A multi-parent id tree is representable through the ordinary API ---------------------------------------------------------------- DocumentUrlDB::add() inserts the id into the new parent's child vector and overwrites idFilenameDb[id].parentId, but it never removes the id from its previous parent's vector. updateUrl() does that unlink correctly, and so does del(); add() does not. So calling addDocument() for an id already present under a different parent leaves that id a child of both parents. At that point the id tree is a DAG rather than a tree, reached entirely through the normal write path with no corruption involved. How that might arise in the field -- inferred, not demonstrated --------------------------------------------------------------- Document ids are (st_dev, st_ino). Documents for files deleted while baloo was not watching are never removed, because nothing walks the indexed tree looking for vanished files, so ghost entries accumulate. Inode reuse can then hand a live file the id of a ghost that still sits under a different parent, which creates the second parent edge above. I want to be explicit that this last step is a hypothesis. I have not demonstrated inode reuse producing a cycle, and I am not claiming it is what happened in this report. I am recording it because it is a mechanism that needs no corruption, and because the same inode-reuse edge case is already known to be awkward elsewhere in baloo. A separate merge request is being prepared for this --------------------------------------------------- I intend to file a merge request that fixes the unbounded recursion itself. It will be separate from the index-removal work I am currently preparing, deliberately: that series is about batching and reconciliation, and a repair to the id-tree structure is different scope. The approach bounds the node domain rather than the recursion depth. A depth cap is the obvious guard and I think it would be a mistake -- it bounds path length while leaving path count unbounded, so on a branching structure it converts a fast SIGSEGV, which at least aborts the write transaction and releases LMDB's single writer lock, into a very long walk that holds that lock and blocks every other writer. The set of nodes, by contrast, is finite and enumerable, so tracking which have been visited bounds the traversal at O(V+E) whatever the topology. That also localises the defect precisely. A child encountered while it is still on the current recursion stack is a back edge, and that edge is the cycle. Breaking that single edge out of the parent's child vector lets the removal run to completion rather than aborting, and the break can be logged, so a future report of this kind is diagnosable from the journal instead of from a core. The same bookkeeping incidentally fixes the multi-parent DAG case described above, which does not hang today but is re-walked once per distinct path rather than once per node. I will link the merge request here once it is up. Tested against 6.16.0. removeRecursively(quint64) is byte-identical on master (28390ddc), and documenturldb.cpp is unchanged since 6.16.0. The predicated overload removeRecursively(quint64, shouldDelete) added since 6.16 has the same unbounded property. -- You are receiving this mail because: You are watching all bug changes.
