leerho commented on PR #565:
URL: https://github.com/apache/datasketches-cpp/pull/565#issuecomment-6812330196
@clee704 one more check for the updatable SET path, in addition to the two I
requested above: the table must be no more than 3/4 full, that is
`4·couponCount <= 3·2^lgArrInts`. A valid writer always grows or promotes the
table before it gets fuller than that, and the Java reader now has the same
check (apache/datasketches-java#799). Without it, a table can be completely
full with a matching count, and the first update of a new coupon after
deserializing throws "Key not found and no empty slots!".
To save you guessing, here is all of the updatable-path hardening as one
diff against your branch (563bbef0), the two earlier checks included. It is the
same in both `newSet` overloads in `hll/include/CouponHashSet-internal.hpp`:
- The `lgArrInts` range and the 3/4-full checks go right after the existing
`if (lgArrInts < hll_constants::LG_INIT_SET_SIZE)` recompute, before anything
uses `lgArrInts`. In the bytes reader that's before `couponsInArray` is
computed, so `1 << lgArrInts` is never evaluated with an out-of-range shift. In
the stream reader it's before the sketch is allocated. The lower bound needs no
check, because the recompute already guarantees `lgArrInts >= LG_INIT_SET_SIZE`.
- The 3/4-full product is computed in `uint64_t`, so a large `couponCount`
can't overflow it.
- The count check goes after the table is copied in. In the stream reader it
goes after a stream-state check, so a short read is reported as a read error
rather than as a count mismatch.
```diff
--- a/hll/include/CouponHashSet-internal.hpp
+++ b/hll/include/CouponHashSet-internal.hpp
@@ -23,4 +23,5 @@
#include "CouponHashSet.hpp"
+#include <algorithm>
#include <cstring>
#include <exception>
@@ -101,4 +102,17 @@ CouponHashSet<A>* CouponHashSet<A>::newSet(const void*
bytes, size_t len, const
lgArrInts = HllUtil<>::computeLgArrInts(SET, couponCount, lgK);
}
+ if (!compactFlag) {
+ // lgArrInts >= LG_INIT_SET_SIZE here, because of the recompute above
+ if (lgArrInts > lgK - 3) {
+ throw std::invalid_argument("Attempt to deserialize invalid updatable
CouponHashSet with lgArrInts > lgK - 3. Found lgArrInts: "
+ + std::to_string(lgArrInts) + ", lgK: " +
std::to_string(lgK));
+ }
+ // a valid writer grows or promotes the table before it is more than
3/4 full
+ if (static_cast<uint64_t>(hll_constants::RESIZE_DENOM) * couponCount
+ > static_cast<uint64_t>(hll_constants::RESIZE_NUMER) << lgArrInts) {
+ throw std::invalid_argument("Attempt to deserialize invalid updatable
CouponHashSet that is more than 3/4 full. Found couponCount: "
+ + std::to_string(couponCount) + ",
lgArrInts: " + std::to_string(lgArrInts));
+ }
+ }
// Don't set couponCount in sketch here;
// we'll set later if updatable, and increment with updates if compact
@@ -126,4 +140,10 @@ CouponHashSet<A>* CouponHashSet<A>::newSet(const void*
bytes, size_t len, const
data + hll_constants::HASH_SET_INT_ARR_START,
couponsInArray * sizeof(uint32_t));
+ const auto nonEmpty = std::count_if(sketch->coupons_.begin(),
sketch->coupons_.end(),
+ [](uint32_t c) { return c !=
hll_constants::EMPTY; });
+ if (static_cast<uint64_t>(nonEmpty) != couponCount) {
+ throw std::invalid_argument("Attempt to deserialize invalid updatable
CouponHashSet with couponCount != number of coupons. Found couponCount: "
+ + std::to_string(couponCount) + ",
coupons: " + std::to_string(nonEmpty));
+ }
}
@@ -173,4 +193,17 @@ CouponHashSet<A>*
CouponHashSet<A>::newSet(std::istream& is, const A& allocator)
lgArrInts = HllUtil<>::computeLgArrInts(SET, couponCount, lgK);
}
+ if (!compactFlag) {
+ // lgArrInts >= LG_INIT_SET_SIZE here, because of the recompute above
+ if (lgArrInts > lgK - 3) {
+ throw std::invalid_argument("Attempt to deserialize invalid updatable
CouponHashSet with lgArrInts > lgK - 3. Found lgArrInts: "
+ + std::to_string(lgArrInts) + ", lgK: " +
std::to_string(lgK));
+ }
+ // a valid writer grows or promotes the table before it is more than
3/4 full
+ if (static_cast<uint64_t>(hll_constants::RESIZE_DENOM) * couponCount
+ > static_cast<uint64_t>(hll_constants::RESIZE_NUMER) << lgArrInts) {
+ throw std::invalid_argument("Attempt to deserialize invalid updatable
CouponHashSet that is more than 3/4 full. Found couponCount: "
+ + std::to_string(couponCount) + ",
lgArrInts: " + std::to_string(lgArrInts));
+ }
+ }
auto sketch = HllUtil<A>::template newObject<CouponHashSet<A>>(allocator,
lgK, tgtHllType, allocator);
@@ -190,4 +223,11 @@ CouponHashSet<A>*
CouponHashSet<A>::newSet(std::istream& is, const A& allocator)
// for stream processing, read entire list so read pointer ends up set
correctly
read(is, sketch->coupons_.data(), sketch->coupons_.size() *
sizeof(uint32_t));
+ if (!is.good()) { throw std::runtime_error("error reading from
std::istream"); }
+ const auto nonEmpty = std::count_if(sketch->coupons_.begin(),
sketch->coupons_.end(),
+ [](uint32_t c) { return c !=
hll_constants::EMPTY; });
+ if (static_cast<uint64_t>(nonEmpty) != couponCount) {
+ throw std::invalid_argument("Attempt to deserialize invalid updatable
CouponHashSet with couponCount != number of coupons. Found couponCount: "
+ + std::to_string(couponCount) + ",
coupons: " + std::to_string(nonEmpty));
+ }
}
```
I applied this to your branch locally. `hll_test` passes under ASan and
UBSan. I also patched a valid updatable image (lgK 12, HLL_8, 200 items,
lgArrInts 9) in several ways, and both readers behave as expected:
- The unpatched image is accepted.
- `lgArrInts` set to 10 or 33 is rejected.
- `couponCount` off by ±1 is rejected.
- A completely full table with a matching count is rejected.
- A table at exactly 3/4 full (384 coupons) is accepted and can still be
updated.
You don't need to add tests for these. We'll add corrupt-image tests that
match the Java ones after this is merged.
--
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]