leerho opened a new pull request, #574: URL: https://github.com/apache/datasketches-cpp/pull/574
## Problem `kll_sketch::merge()` doesn't keep the basic exception guarantee when an allocation fails while merging levels above level zero. `merge_higher_levels()` moves this sketch's items into a work buffer, frees the item storage, and only then allocates the new storage. If that allocation throws, `items_` still points at the freed storage, and the sketch's levels still describe items that were moved out. Using or destroying the sketch afterwards is a use-after-free. ASan reports it with an allocator that fails on purpose. Only the application's allocator can trigger this, by failing during a merge in estimation mode. The serialized format is not involved. The same code is in 5.3.0 and 5.3.1. ## Fix The number of levels and items after compression depends only on the level sizes, not on the item values. A new helper, `kll_helper::predict_compress()`, computes that result from the level sizes, mirroring the level loop of `general_compress()`. `merge_higher_levels()` now does all of its allocations before it moves any items: - the new item storage, if the capacity changes - the space for the final levels, using `levels_.reserve()` It then checks that `general_compress()` produced the predicted result. The merge results are unchanged. ## Tests - New `kll_sketch_merge_failure_test.cpp`. It fails each allocation of a merge in turn. Targets are empty, in exact mode, or in estimation mode, and sources are smaller or larger than the target, passed as lvalues and as rvalues. After each failure, the test checks that the target can still be queried, updated, merged into and round-tripped. It also checks that an lvalue source is unchanged and that nothing leaks. Without the fix, this test fails under ASan with the use-after-free. - The whole KLL suite passes under ASan and UBSan, and the prediction check held in every merge. I also checked it on 9,600 randomized merges with k from 8 to 1000 and n up to 2·10^6. ## Related - This came up while adding allocation-failure tests to #558, which moves KLL item storage to first use. The two branches merge cleanly, and the KLL tests pass on the combination. - It also merges cleanly with #573, #569, #567 and #542. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
