stojkomilos opened a new pull request, #573:
URL: https://github.com/apache/datasketches-cpp/pull/573

   `kll_sketch::update(item)` copies `item` into the sketch after 
`internal_update()`. If `item` refers to an item of the same sketch and level 0 
is full, `internal_update()` compacts first. The compaction can destroy that 
item or free `items_`, so `update()` then reads freed memory.
   
   This PR copies `item` before `internal_update()` when level 0 is full. 
Updates when level 0 has free space do not change.
   
   ## Master
   
   This is proost's test from #569 (see the next section), with `k = 200` 
instead of 5000, so that the 201st update triggers the first compaction:
   
   ```cpp
   TEST_CASE("kll sketch: update with aliased item during compaction", 
"[kll_sketch]") {
     const uint16_t k = 200;
     kll_sketch<std::string> sketch(k);
   
     for (int i = 0; i < kll_constants::DEFAULT_K; ++i) {
       sketch.update(std::string(64, 'x') + std::to_string(i));
     }
   
     REQUIRE(sketch.get_n() == kll_constants::DEFAULT_K);
   
     const std::string& item = sketch.begin()->first;
     const std::string expected = item;
   
     // Triggers compaction
     sketch.update(item);
   
     REQUIRE(sketch.get_n() == kll_constants::DEFAULT_K + 1);
   
     uint32_t count = 0;
     for (const auto& entry : sketch) {
       if (entry.first == expected) {
         ++count;
       }
     }
     REQUIRE(count == 2);
   }
   ```
   
   On master (98c6b742), with GCC 10.5 and 10 runs per build:
   
   - `-O3`: fails 10/10 with `std::bad_alloc`.
   - `-O1 -fsanitize=address`: `heap-use-after-free` 10/10. The read is in 
`update()` at `kll_sketch_impl.hpp:185`. The memory was freed in 
`add_empty_top_level_to_completely_full_sketch()` (`:742`), called from 
`compress_while_updating()` (`:662`) and `internal_update()` (`:202`).
   
   `sketch.update(sketch.get_quantile(0.5))` on a `kll_sketch<std::string>` 
hits the same bug, because `get_quantile()` returns a reference into the 
sketch. On master it reports `heap-use-after-free` under ASan. With this PR, 
the added item equals the median.
   
   ## #569
   
   #569 ("perf: kll_sketch grows its items buffer by 8x up to k") grows 
`items_` lazily, so `internal_update()` also frees the buffer when it grows it: 
at 200, 1600 and 12800 items. proost found this case with the test in [this 
comment](https://github.com/apache/datasketches-cpp/pull/569#discussion_r4533743827):
   
   ```cpp
   TEST_CASE("kll sketch: update with aliased item during buffer growth", 
"[kll_sketch]") {
     const uint16_t k = 5000;
     kll_sketch<std::string> sketch(k);
   
     for (int i = 0; i < kll_constants::DEFAULT_K; ++i) {
       sketch.update(std::string(64, 'x') + std::to_string(i));
     }
   
     REQUIRE(sketch.get_n() == kll_constants::DEFAULT_K);
   
     const std::string& item = sketch.begin()->first;
     const std::string expected = item;
   
     // Triggers grow_items()
     sketch.update(item);
   
     REQUIRE(sketch.get_n() == kll_constants::DEFAULT_K + 1);
   
     uint32_t count = 0;
     for (const auto& entry : sketch) {
       if (entry.first == expected) {
         ++count;
       }
     }
     REQUIRE(count == 2);
   }
   ```
   
   On master this test passes, because a sketch with k = 5000 allocates 5000 
items at the start, so the 201st update has free space. On #569 (0ad21a2b) the 
buffer starts at 200 items, and the 201st update grows it:
   
   - `-O3`: fails 10/10 with `std::bad_alloc`.
   - `-O1 -fsanitize=address`: `heap-use-after-free` 10/10. The read is in 
`update()` at `kll_sketch_impl.hpp:185`. The memory was freed in `grow_items()` 
(`:779`), called from `internal_update()` (`:204`).
   
   The fix in this PR covers both cases, because both the growth and the 
compaction happen only when level 0 is full. With this PR merged into #569, 
proost's test passes 10/10 in both builds.
   
   ## Tests
   
   **Added**
   
   - `kll sketch: update with aliased item during compaction` (1 test): the 
master repro above. The compaction leaves level 0 with only the new item, so 
the test asserts that `begin()` is that item with weight 1, instead of counting 
matches.
   
   **Test strength:** without the fix, the new test fails 10/10 in each build: 
`std::bad_alloc` at `-O3`, `heap-use-after-free` at `-O1` with ASan, and an 
empty `begin()` item at `-O0` with ASan.
   
   This pull request and its description were written by Isaac.
   


-- 
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