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]