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]

Reply via email to