Skip to content

i1.39.11

i1.39.11: chore(hll): sync hyperloglog.c with valkey upstream (#7961)
@romange romange tagged this 30 Jul 11:52 
* chore(hll): sync hyperloglog.c with valkey upstream

Re-syncs src/redis/hyperloglog.c, forked from valkey 56ec1ff1c two years
ago, with upstream 06d30f293, and keeps upstream's formatting so future
syncs stay cheap.

Imported from upstream:
- CVE-2025-32023: run-length overflow guards on every sparse opcode, not
  just VAL. A payload whose XZERO runs sum past INT_MAX wrapped the `idx`
  cursor negative and wrote a register through a wild pointer.
- AVX2 and ARM NEON hllMergeDense()/hllDenseCompress() kernels and their
  runtime dispatchers; PFMERGE and multi-key PFCOUNT now go through them.
  src/redis/config.h gains upstream's HAVE_X86_SIMD, HAVE_ARM_NEON,
  ATTRIBUTE_TARGET_* and VALKEY_NO_SANITIZE macros.

Three Dragonfly-local bugs the sync exposed:
- pfcountMulti() merged into the raw register array HLL_HDR_SIZE bytes
  too low, so every multi-key PFCOUNT dropped 16 registers and counted 16
  zeroed ones instead.
- `goto promote` in hllSparseSet() jumped over the `sds hll`
  initialization, leaving the promote path reading an uninitialized
  pointer.
- pfadd_sparse() invalidated the cached cardinality through a header
  pointer captured before hllSparseAdd(), which may have reallocated or
  freed the sds string.

Divergence from upstream drops from 2139 to 767 differing lines. Of those,
72 are in the shared library half and every one is load-bearing (robj ->
sds*, HLL_SPARSE_MAX_BYTES, the `promoted` out-param, includes, `#if 0`
markers); the other 695 are upstream's command/reply layer against the
HllBufferPtr API that replaces it. The provenance note lives in
hyperloglog.h so it costs nothing against upstream.

Adds 5 tests to hll_family_test.cc, each checked to fail against the
unfixed code - the CVE one SIGSEGVs. The SIMD equality test builds dense
HLLs covering all 64 register values (PFADD data only fills the low bits)
and was mutation-tested against 4 injected kernel faults. The promote test
now reaches hllSparseSet()'s promote branch through PFADD rather than by
calling it directly: MurmurHash64A is invertible, so an element hashing to
35 zero bits above the register index is constructed instead of searched
for. The NEON path is syntax-checked for aarch64 with clang but not run
locally.

Adds 5 --bench benchmarks over the hyperloglog.c API, comparing the AVX2
and NEON kernels against the scalar fallbacks they replace. Built with
`./helio/blaze.sh -release && cd build-opt && ninja hll_family_test`, then
run pinned to one core (the gtest filter matters - without it the 21 tests
run first; a debug build penalizes the scalar C loops far more than
production does):

  $ taskset -c 4 build-opt/hll_family_test --bench --gtest_filter=-'*' \
      --benchmark_min_time=0.5s

  Run on (24 X 5482 MHz CPU s)
  CPU Caches:
    L1 Data 32 KiB (x12)
    L1 Instruction 32 KiB (x12)
    L2 Unified 1024 KiB (x12)
    L3 Unified 32768 KiB (x2)
  Load Average: 1.02, 1.10, 1.73
  ***WARNING*** CPU scaling is enabled, the benchmark real time
  measurements may be noisy and will incur extra overhead.
  ***WARNING*** ASLR is enabled, the results may have unreproducible
  noise in them.
  ------------------------------------------------------------------
  Benchmark                              Time         CPU  Iterations
  ------------------------------------------------------------------
  BM_HllMergeDense/simd:0            12582 ns    12582 ns       41273
  BM_HllMergeDense/simd:1              383 ns      383 ns     1821945
  BM_HllDenseCompress/simd:0         66762 ns    66761 ns       10226
  BM_HllDenseCompress/simd:1           466 ns      466 ns     1502399
  BM_HllDenseCompressUnchained        3676 ns     3676 ns      187047
  BM_PfMerge/simd:0/sources:1        77648 ns    77647 ns        8997
  BM_PfMerge/simd:1/sources:1          944 ns      944 ns      744688
  BM_PfMerge/simd:0/sources:8       154197 ns   154198 ns        4529
  BM_PfMerge/simd:1/sources:8         3625 ns     3624 ns      193324
  BM_PfCountMulti/simd:0/sources:1   15164 ns    15164 ns       46004
  BM_PfCountMulti/simd:1/sources:1    3760 ns     3760 ns      186322
  BM_PfCountMulti/simd:0/sources:8   92929 ns    92930 ns        7535
  BM_PfCountMulti/simd:1/sources:8    6446 ns     6446 ns      108804

(The items_per_second column is dropped above to stay inside 100 columns;
it is derived from Time and adds nothing.)

Read BM_HllDenseCompress/simd:0 with care. That scalar loop is a
store-forwarding dependency chain costing ~20 cycles per register, so most
of its apparent 145x gap is the stall rather than vector width.
BM_HllDenseCompressUnchained packs the same bytes without the chain - it
is a scalar reference, CHECKed byte-identical against hllDenseCompress() -
and puts the vectorization win at ~8x. BM_HllMergeDense has no such
problem, so its 29x is a genuine width-bound result.

Co-Authored-By: Claude <noreply@anthropic.com>
Signed-off-by: Roman Gershman <roman@dragonflydb.io>

* fix: data race when using hll

---------

Signed-off-by: Roman Gershman <roman@dragonflydb.io>
Co-authored-by: Claude <noreply@anthropic.com>
Assets 2
Loading