clee704 opened a new issue, #551: URL: https://github.com/apache/datasketches-cpp/issues/551
When an allocation inside `hll_sketch_alloc` throws, the sketch can leak memory, reject every later value, report an inflated estimate without any error, or crash on a later update. We expected the basic exception guarantee: after a call fails, the sketch is still usable and nothing has leaked. Everything below reproduces on tag 5.1.0 and on master at be33db5 (2026-10-18), built with GCC 13.3 and `-std=c++17` on Linux x86-64. The reproducer uses a counting allocator as the sketch's allocator type. It throws `std::bad_alloc` on the Nth `allocate` call, so each run injects exactly one failure. All runs use HLL_4. The reproducer source is at the end of this issue. ### 1. Storage leaks when a constructor throws after placement new Several functions allocate storage from the allocator and construct an object in it with placement new. When that constructor throws, for example because its own vector allocation fails, nothing returns the storage to the allocator: - the sketch constructor, [HllSketch-internal.hpp L45-L53](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketch-internal.hpp#L45-L53) - `CouponList::copy`, [CouponList-internal.hpp L61-L63](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/CouponList-internal.hpp#L61-L63), which the copy constructor uses ([HllSketch-internal.hpp L75-L77](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketch-internal.hpp#L75-L77)) - `promoteListToSet`, [HllSketchImplFactory.hpp L58](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketchImplFactory.hpp#L58) - `newHll`, [HllSketchImplFactory.hpp L109-L122](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketchImplFactory.hpp#L109-L122), and `reset`, [HllSketchImplFactory.hpp L132](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketchImplFactory.hpp#L132) - `CouponList::newList`, [CouponList-internal.hpp L117](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/CouponList-internal.hpp#L117) and [CouponList-internal.hpp L166](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/CouponList-internal.hpp#L166) - `AuxHashMap::newAuxHashMap`, [AuxHashMap-internal.hpp L39-L41](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/AuxHashMap-internal.hpp#L39-L41) Construction with lg_k=12. Allocation 0 is the list object and allocation 1 is its coupon array: ``` construction, start_full_size=false fail allocation 0: threw=1 leaked_blocks=0 fail allocation 1: threw=1 leaked_blocks=1 ``` The update runs in sections 2 and 4 show the same leak in `promoteListToSet` (allocation 1), `newHll` (allocation 7) and `newAuxHashMap` (allocations 15 and 17). The copy, `reset` and `newList` cases follow from the same code pattern; the reproducer does not exercise them. ### 2. A failed list promotion leaves the sketch full `CouponList::couponUpdate` stores the coupon and increments the coupon count before it promotes the list. If the promotion throws, the list stays full, and every later update with a new value throws `std::runtime_error("Array invalid: no empties and no duplicates")`. The estimate stays at 8. The list and set code is shared by all three target types. `promoteListToSet` and `promoteListOrSetToHll` also hold the new set or array in a raw pointer while they copy coupons into it, so an exception from that loop would leak it. The reproducer does not reach this case. - [CouponList-internal.hpp L283-L304](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/CouponList-internal.hpp#L283-L304) (`CouponList::couponUpdate`) - [HllSketchImplFactory.hpp L56-L63](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketchImplFactory.hpp#L56-L63) (`promoteListToSet`) and [HllSketchImplFactory.hpp L66-L75](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketchImplFactory.hpp#L66-L75) (`promoteListOrSetToHll`) lg_k=12, 1000 distinct values; the estimate is 996 when no allocation fails. Allocation 0 is the hash set, allocation 1 is its coupon array, and allocation 7 is the byte array of the HLL array: ``` fail allocation 0: bad_alloc=1 other_exceptions=992 ("Array invalid: no empties and no duplicates") estimate=8 leaked_blocks=0 fail allocation 1: bad_alloc=1 other_exceptions=992 ("Array invalid: no empties and no duplicates") estimate=8 leaked_blocks=1 fail allocation 7: bad_alloc=1 other_exceptions=0 estimate=996 leaked_blocks=1 ``` ### 3. Copy assignment frees the current implementation before copying `operator=(const hll_sketch_alloc&)` passes `sketch_impl` to its deleter ([HllSketch-internal.hpp L98](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketch-internal.hpp#L98)) and then copies `other` ([HllSketch-internal.hpp L99](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketch-internal.hpp#L99)). If the copy throws, `sketch_impl` still points to the freed implementation. The destructor then calls `get_deleter()` on it and frees it again ([HllSketch-internal.hpp L70](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/HllSketch-internal.hpp#L70)). AddressSanitizer output, abbreviated: ``` ERROR: AddressSanitizer: heap-use-after-free on address 0x506000000020 READ of size 8 at 0x506000000020 thread T0 #0 in datasketches::hll_sketch_alloc<test_allocator<unsigned char> >::~hll_sketch_alloc() hll/include/HllSketch-internal.hpp:70 0x506000000020 is located 0 bytes inside of 56-byte region [0x506000000020,0x506000000058) freed by thread T0 here: #7 in datasketches::hll_sketch_alloc<test_allocator<unsigned char> >::operator=(datasketches::hll_sketch_alloc<test_allocator<unsigned char> > const&) hll/include/HllSketch-internal.hpp:98 ``` ### 4. HLL_4: a failed aux map allocation corrupts the sketch **Slot marked as an exception without an aux entry.** When a value becomes an exception, `Hll4Array::internalHll4Update` updates the HIP and KxQ accumulators ([Hll4Array-internal.hpp L184](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L184)), writes `AUX_TOKEN` into the slot ([Hll4Array-internal.hpp L212](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L212)), and only then creates the aux map ([Hll4Array-internal.hpp L214](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L214)) and adds the entry ([Hll4Array-internal.hpp L217](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L217)). If either step throws, the slot holds `AUX_TOKEN` without an aux entry. When this was the first exce ption, `auxHashMap_` is still null, and the next larger value for that slot calls `mustFindValueFor` through the null pointer ([Hll4Array-internal.hpp L180](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L180)). If a later exception creates the aux map first, converting the sketch to HLL_8 throws `std::invalid_argument("slotNo not found")`. lg_k=4, `start_full_size=true`. Only the first aux map allocation fails; the second update targets the same slot. The build without sanitizers exits with SIGSEGV. AddressSanitizer output, abbreviated: ``` first value 14441 -> slot 1, register value 15; second value 805951 -> same slot, register value 17 first update threw std::bad_alloc ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 The signal is caused by a READ memory access. #0 in datasketches::AuxHashMap<test_allocator<unsigned char> >::mustFindValueFor(unsigned int) const hll/include/AuxHashMap-internal.hpp:197 #1 in datasketches::Hll4Array<test_allocator<unsigned char> >::internalHll4Update(unsigned int, unsigned char) hll/include/Hll4Array-internal.hpp:180 #2 in datasketches::Hll4Array<test_allocator<unsigned char> >::internalCouponUpdate(unsigned int) hll/include/Hll4Array-internal.hpp:152 ``` lg_k=16. Allocation 12, the first aux map, fails; 20,000 values are added and the sketch is then converted to HLL_8. The reproducer does not catch the conversion's exception: ``` update exceptions=1 estimate=20092 serialized_bytes=32812 terminate called after throwing an instance of 'std::invalid_argument' what(): slotNo not found: 35393 ``` **Partial `curMin` increase.** `shiftToBiggerCurMin` decrements every 4-bit slot ([Hll4Array-internal.hpp L258-L272](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L258-L272)) and then scans the old aux map. Entries that are no longer exceptions get their slot set to 14 ([Hll4Array-internal.hpp L300](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L300)); the first remaining exception creates the new aux map ([Hll4Array-internal.hpp L305](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L305)). If that allocation throws, the slots stay decremented and some may already hold 14, while `curMin_` and `numAtCurMin_` keep their old values ([Hll4Array-internal.hpp L330-L331](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/h ll/include/Hll4Array-internal.hpp#L330-L331) is not reached). Later updates raise no exception, but the final estimate is inflated. `newAuxMap` is also a raw pointer, so an exception from `mustAdd` ([Hll4Array-internal.hpp L308](https://github.com/apache/datasketches-cpp/blob/be33db564a4011bded6ded7b09d6d27b08ef4984/hll/include/Hll4Array-internal.hpp#L308)) would leak it. lg_k=16, 2,000,000 distinct values; the estimate is 1,992,195 when no allocation fails. Allocations 14 and 15 are the new aux map and its entry array at the first `curMin` increase; 16 and 17 are the same at the second: ``` fail allocation 14: bad_alloc=1 other_exceptions=0 estimate=5624809 leaked_blocks=0 fail allocation 15: bad_alloc=1 other_exceptions=0 estimate=5624809 leaked_blocks=1 fail allocation 16: bad_alloc=1 other_exceptions=0 estimate=2474766 leaked_blocks=0 fail allocation 17: bad_alloc=1 other_exceptions=0 estimate=2474766 leaked_blocks=1 ``` ### Possible fixes - Allocate and construct through one helper that returns the storage to the allocator when the constructor throws, and use it at each placement new above. - Hold a new implementation in a `std::unique_ptr` with its deleter until promotion or copying finishes. - In `CouponList::couponUpdate`, promote before storing the coupon, or undo the store and the count when promotion throws. - Implement copy assignment as copy-and-swap. - In `Hll4Array::internalHll4Update`, create the aux map and reserve its entry before changing the slot or the HIP and KxQ accumulators. - In `shiftToBiggerCurMin`, build the new aux map in a `std::unique_ptr` before changing any slot, so that a failed allocation leaves the sketch unchanged. We can send a pull request with these changes. <details> <summary>Reproducer (repro.cpp)</summary> ```cpp // Allocation-failure behavior of datasketches::hll_sketch_alloc. // // test_allocator counts live blocks and throws std::bad_alloc on the Nth // allocate() call after arm(N). Each run injects exactly one failure. // // ./repro sweep construction and update sweeps; reports leaked blocks // ./repro assign copy assignment whose copy fails (run under ASan) // ./repro trace <lg_k> <n> lists every HLL_4 allocation while updating n values // ./repro hll4 <lg_k> <n> HLL_4 update sweep, one child process per failed allocation // ./repro orphan <lg_k> <fail> <n> HLL_4: fail allocation <fail>, update n values, convert to HLL_8 // ./repro nullaux HLL_4: fail the first aux map allocation, then update the same slot // // Build: g++ -std=c++17 -O2 -g -I <datasketches>/hll/include -I <datasketches>/common/include repro.cpp // Add -fsanitize=address for assign and nullaux. #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <new> #include <stdexcept> #include <string> #include <typeinfo> #include <sys/wait.h> #include <unistd.h> #include "hll.hpp" namespace { long g_live = 0; long g_calls = 0; long g_fail_at = -1; bool g_failed = false; bool g_trace = false; long g_trace_index = 0; long g_current_value = -1; void arm(long n) { g_calls = 0; g_fail_at = n; g_failed = false; } void disarm() { g_fail_at = -1; } } // namespace template <typename T> struct test_allocator { using value_type = T; test_allocator() = default; template <typename U> test_allocator(const test_allocator<U>&) noexcept {} T* allocate(std::size_t n) { if (g_fail_at >= 0 && g_calls++ == g_fail_at) { g_failed = true; throw std::bad_alloc(); } ++g_live; if (g_trace) { std::printf(" allocation %ld at value %ld: %zu bytes for %s\n", g_trace_index++, g_current_value, n * sizeof(T), typeid(T).name()); } return static_cast<T*>(::operator new(n * sizeof(T))); } void deallocate(T* p, std::size_t) noexcept { --g_live; ::operator delete(p); } }; template <typename T, typename U> bool operator==(const test_allocator<T>&, const test_allocator<U>&) { return true; } template <typename T, typename U> bool operator!=(const test_allocator<T>&, const test_allocator<U>&) { return false; } using sketch = datasketches::hll_sketch_alloc<test_allocator<uint8_t>>; static void construction_sweep(bool full_size) { std::printf("construction, start_full_size=%s\n", full_size ? "true" : "false"); for (long n = 0;; ++n) { arm(n); bool threw = false; try { sketch s(12, datasketches::HLL_4, full_size); } catch (const std::bad_alloc&) { threw = true; } disarm(); if (!g_failed) break; std::printf(" fail allocation %ld: threw=%d leaked_blocks=%ld\n", n, threw, g_live); g_live = 0; } } // Updates a sketch with `values` distinct values while allocation N fails. // Exceptions from update() are counted and the loop continues. static void update_sweep(uint8_t lg_k, int values) { std::printf("update, lg_k=%u, %d distinct values\n", lg_k, values); for (long n = 0;; ++n) { long leaked = 0; int bad_alloc = 0, other = 0; std::string other_what; double estimate = 0; { sketch s(lg_k, datasketches::HLL_4); arm(n); for (int v = 0; v < values; ++v) { try { s.update(static_cast<uint64_t>(v)); } catch (const std::bad_alloc&) { ++bad_alloc; } catch (const std::exception& e) { if (other++ == 0) other_what = e.what(); } } disarm(); estimate = s.get_estimate(); } leaked = g_live; g_live = 0; if (!g_failed) { std::printf(" no failure: estimate=%.0f leaked_blocks=%ld\n", estimate, leaked); break; } std::printf(" fail allocation %ld: bad_alloc=%d other_exceptions=%d%s%s%s estimate=%.0f leaked_blocks=%ld\n", n, bad_alloc, other, other ? " (\"" : "", other ? other_what.c_str() : "", other ? "\")" : "", estimate, leaked); } } // Same as update_sweep, but runs each injected failure in a child process so // that a crash is reported instead of ending the sweep. static void forked_update_sweep(uint8_t lg_k, datasketches::target_hll_type type, long values) { std::printf("update in child process, lg_k=%u, type=%d, %ld distinct values\n", lg_k, (int)type, values); std::fflush(stdout); for (long n = 0;; ++n) { int fds[2]; if (pipe(fds) != 0) return; pid_t pid = fork(); if (pid == 0) { close(fds[0]); long bad_alloc = 0, other = 0, leaked = 0; std::string other_what; double estimate = 0; { sketch s(lg_k, type); if (n >= 0) arm(n); for (long v = 0; v < values; ++v) { try { s.update(static_cast<uint64_t>(v)); } catch (const std::bad_alloc&) { ++bad_alloc; } catch (const std::exception& e) { if (other++ == 0) other_what = e.what(); } } disarm(); estimate = s.get_estimate(); } leaked = g_live; char buf[512]; int len = std::snprintf(buf, sizeof buf, "%d bad_alloc=%ld other_exceptions=%ld%s%s%s estimate=%.0f leaked_blocks=%ld", g_failed ? 1 : 0, bad_alloc, other, other ? " (\"" : "", other ? other_what.c_str() : "", other ? "\")" : "", estimate, leaked); if (write(fds[1], buf, len) < 0) _exit(3); _exit(0); } close(fds[1]); char buf[512] = {0}; ssize_t got = read(fds[0], buf, sizeof buf - 1); close(fds[0]); int status = 0; waitpid(pid, &status, 0); if (WIFSIGNALED(status)) { std::printf(" fail allocation %ld: child killed by signal %d\n", n, WTERMSIG(status)); continue; } if (got <= 0) { std::printf(" fail allocation %ld: no result\n", n); continue; } if (buf[0] == '0') { std::printf(" no failure injected (%ld allocations): %s\n", n, buf + 2); break; } std::printf(" fail allocation %ld: %s\n", n, buf + 2); std::fflush(stdout); } } static void assign_after_failed_copy() { sketch a(12, datasketches::HLL_4); sketch b(12, datasketches::HLL_4); b.update(1); arm(0); try { a = b; } catch (const std::bad_alloc&) { std::printf("copy assignment threw std::bad_alloc\n"); } disarm(); std::printf("destroying the assigned-to sketch\n"); } int main(int argc, char** argv) { const char* mode = argc > 1 ? argv[1] : "sweep"; if (std::strcmp(mode, "sweep") == 0) { construction_sweep(false); construction_sweep(true); update_sweep(12, 1000); update_sweep(7, 200); } else if (std::strcmp(mode, "trace") == 0 && argc > 3) { sketch s(static_cast<uint8_t>(std::atoi(argv[2])), datasketches::HLL_4); g_trace = true; for (long v = 0; v < std::atol(argv[3]); ++v) { g_current_value = v; s.update(static_cast<uint64_t>(v)); } g_trace = false; } else if (std::strcmp(mode, "hll4") == 0 && argc > 3) { forked_update_sweep(static_cast<uint8_t>(std::atoi(argv[2])), datasketches::HLL_4, std::atol(argv[3])); } else if (std::strcmp(mode, "orphan") == 0 && argc > 4) { // Fails allocation N during HLL_4 updates, then converts the sketch to HLL_8. sketch s(static_cast<uint8_t>(std::atoi(argv[2])), datasketches::HLL_4); arm(std::atol(argv[3])); long failures = 0; for (long v = 0; v < std::atol(argv[4]); ++v) { try { s.update(static_cast<uint64_t>(v)); } catch (const std::exception&) { ++failures; } } disarm(); std::printf("update exceptions=%ld estimate=%.0f serialized_bytes=%zu\n", failures, s.get_estimate(), s.serialize_compact().size()); std::fflush(stdout); sketch s8(s, datasketches::HLL_8); std::printf("converted to HLL_8: estimate=%.0f\n", s8.get_estimate()); } else if (std::strcmp(mode, "nullaux") == 0) { // HLL_4, lg_k=4, full size. The first allocation after construction is the aux map. // Fail only that allocation, then update the same slot with a higher value. using util = datasketches::HllUtil<test_allocator<uint8_t>>; auto slot_and_value = [](uint64_t v, uint32_t& slot, uint8_t& value) { HashState h; util::hash(&v, sizeof(v), datasketches::DEFAULT_SEED, h); const uint32_t c = util::coupon(h); slot = util::getLow26(c) & 15u; value = util::getValue(c); }; uint64_t first = 0, second = 0; uint32_t first_slot = 0, slot = 0; uint8_t first_value = 0, value = 0; for (uint64_t v = 0;; ++v) { slot_and_value(v, slot, value); if (value == 15) { first = v; first_slot = slot; first_value = value; break; } } for (uint64_t v = 0;; ++v) { slot_and_value(v, slot, value); if (slot == first_slot && value >= 16) { second = v; break; } } std::printf("first value %llu -> slot %u, register value %u; second value %llu -> same slot, register value %u\n", (unsigned long long)first, first_slot, first_value, (unsigned long long)second, value); sketch s(4, datasketches::HLL_4, true); arm(0); try { s.update(first); } catch (const std::bad_alloc&) { std::printf("first update threw std::bad_alloc\n"); } disarm(); std::fflush(stdout); s.update(second); std::printf("second update returned; estimate=%.1f\n", s.get_estimate()); } else if (std::strcmp(mode, "assign") == 0) { assign_after_failed_copy(); } return 0; } ``` </details> -- 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]
