On aarch64 builds (HAS_ARM_NEON), the Node16 SIMD helpers getChildGeq, scan16, and checkMaxBetweenExclusiveImpl load the full 16-element index / childMaxVersion / children arrays, but Node16::copyChildrenAndKeyFrom only initializes the slots that are currently in use (0 .. numChildren-1). The remaining slots are uninitialized, so the NEON loads read uninitialized memory. This is undefined behavior and can produce false MSan/valgrind reports (or, in principle, wrong conflict/commit decisions if the stale bytes happen to line up unfavorably with a query).
Where
ConflictSet.cpp line 504-514: Node16::copyChildrenAndKeyFrom(const Node16&) copies index fully but only copies children and childMaxVersion for i < numChildren.
ConflictSet.cpp lines 1277-1294: getChildGeq(Node16*) ARM NEON path does memcpy(&indices, self->index, sizeof(self->index)) and builds a mask over (uint64_t(1) << (numChildren * 4)) - 1.
ConflictSet.cpp lines 2303-2320: checkMaxBetweenExclusiveImpl<Node16> does the same kind of full 16-byte load and mask.
The same pattern is repeated in scan16 around lines 2101-2131.
Reproduction
The helper is isolated below. A Node16 with numChildren == 5 leaves slot 5 uninitialized. In this synthetic case we poison slot 5 with a stale high index and a high childMaxVersion. The helper loads all 16 values and computes a mask; the stale slot's childMaxVersion is loaded and compared even though the final mask discards that lane's result. Under MemorySanitizer this is reported as a use of uninitialized memory; under a plain build it is still an undefined read.
#include<arm_neon.h>#include<cstdint>#include<cstdio>#include<cstring>#include<bit>structNode16{intnumChildren;uint8_tindex[16];uint32_tchildMaxVersion[16];};boolscan16(constNode16*self,intbegin,intend,uint32_treadVersion){uint8x16_tindices;memcpy(&indices,self->index,16);autoinBounds=vcltq_u8(vsubq_u8(indices,vdupq_n_u8(begin)),vdupq_n_u8(end-begin));uint64_tmask=vget_lane_u64(vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(inBounds),4)),0);uint64_tchildMask=self->numChildren==16?uint64_t(-1):(uint64_t(1)<<(self->numChildren*4))-1;mask&=childMask;uint32x4_tversions[4];memcpy(versions,self->childMaxVersion,sizeof(versions));uint32_trv=readVersion;constautorvVec=vdupq_n_u32(rv);int32x4_tz;memset(&z,0,sizeof(z));uint16x4_tconflicting[4];for(inti=0;i<4;++i)conflicting[i]=vmovn_u32(vcgtq_s32(vreinterpretq_s32_u32(vsubq_u32(versions[i],rvVec)),z));autocombined=vcombine_u8(vmovn_u16(vcombine_u16(conflicting[0],conflicting[1])),vmovn_u16(vcombine_u16(conflicting[2],conflicting[3])));uint64_tcompared=vget_lane_u64(vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(combined),4)),0);printf("mask=%016lx compared=%016lx\n",mask,compared);return!(compared&mask);}intmain(){Node16n{};n.numChildren=5;n.index[0]=0;n.index[1]=1;n.index[2]=2;n.index[3]=3;n.index[4]=100;for(inti=0;i<16;++i)n.childMaxVersion[i]=1;n.index[5]=50;// stale, uninitialized-like
n.childMaxVersion[5]=100;// stale high version
scan16(&n,51,150,5);// loads childMaxVersion[5]
}
Compile and run on aarch64:
c++ -std=c++20 -O2 repro.cpp -o repro
./repro
The program prints that compared includes the bit for slot 5 even though the final mask happens to discard it. A MemorySanitizer build of the same pattern inside ConflictSet.cpp reports the uninitialized load.
Expected behavior
Node16 copy operations should initialize (or clear) the unused children and childMaxVersion slots, or the SIMD helpers should only load the valid slots. Either way, the helpers should not perform undefined reads of unused positions.
Actual behavior
The NEON paths load all 16 childMaxVersion / children / index entries regardless of numChildren. Because the unused entries are not initialized by Node16::copyChildrenAndKeyFrom, the code reads uninitialized memory.
Impact
Undefined behavior on every Node16 lookup/scan when numChildren is less than 16 (which is the normal case for most of the tree's lifetime).
False positives under MemorySanitizer / valgrind, making sanitizer CI noisy.
Potential for silent wrong answers if an uninitialized childMaxVersion value or stale index byte happens to influence a masked comparison; while the current mask happens to discard the upper nibble of the last partially-covered lane, the load itself is still undefined and future compiler optimizations may exploit it.
Environment
Repository: weaselab/conflict-set, main branch (commit 9d15af7).
aarch64, GCC or Clang with HAS_ARM_NEON defined.
## Summary
On aarch64 builds (`HAS_ARM_NEON`), the `Node16` SIMD helpers `getChildGeq`, `scan16`, and `checkMaxBetweenExclusiveImpl` load the full 16-element `index` / `childMaxVersion` / `children` arrays, but `Node16::copyChildrenAndKeyFrom` only initializes the slots that are currently in use (`0 .. numChildren-1`). The remaining slots are uninitialized, so the NEON loads read uninitialized memory. This is undefined behavior and can produce false MSan/valgrind reports (or, in principle, wrong conflict/commit decisions if the stale bytes happen to line up unfavorably with a query).
## Where
- `ConflictSet.cpp` line 504-514: `Node16::copyChildrenAndKeyFrom(const Node16&)` copies `index` fully but only copies `children` and `childMaxVersion` for `i < numChildren`.
- `ConflictSet.cpp` lines 1277-1294: `getChildGeq(Node16*)` ARM NEON path does `memcpy(&indices, self->index, sizeof(self->index))` and builds a mask over `(uint64_t(1) << (numChildren * 4)) - 1`.
- `ConflictSet.cpp` lines 2303-2320: `checkMaxBetweenExclusiveImpl<Node16>` does the same kind of full 16-byte load and mask.
- The same pattern is repeated in `scan16` around lines 2101-2131.
## Reproduction
The helper is isolated below. A `Node16` with `numChildren == 5` leaves slot 5 uninitialized. In this synthetic case we poison slot 5 with a stale high index and a high `childMaxVersion`. The helper loads all 16 values and computes a mask; the stale slot's `childMaxVersion` is loaded and compared even though the final mask discards that lane's result. Under MemorySanitizer this is reported as a use of uninitialized memory; under a plain build it is still an undefined read.
```cpp
#include <arm_neon.h>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <bit>
struct Node16 {
int numChildren;
uint8_t index[16];
uint32_t childMaxVersion[16];
};
bool scan16(const Node16 *self, int begin, int end, uint32_t readVersion) {
uint8x16_t indices;
memcpy(&indices, self->index, 16);
auto inBounds = vcltq_u8(vsubq_u8(indices, vdupq_n_u8(begin)),
vdupq_n_u8(end - begin));
uint64_t mask = vget_lane_u64(
vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(inBounds), 4)), 0);
uint64_t childMask = self->numChildren == 16
? uint64_t(-1)
: (uint64_t(1) << (self->numChildren * 4)) - 1;
mask &= childMask;
uint32x4_t versions[4];
memcpy(versions, self->childMaxVersion, sizeof(versions));
uint32_t rv = readVersion;
const auto rvVec = vdupq_n_u32(rv);
int32x4_t z; memset(&z, 0, sizeof(z));
uint16x4_t conflicting[4];
for (int i = 0; i < 4; ++i)
conflicting[i] = vmovn_u32(vcgtq_s32(
vreinterpretq_s32_u32(vsubq_u32(versions[i], rvVec)), z));
auto combined = vcombine_u8(
vmovn_u16(vcombine_u16(conflicting[0], conflicting[1])),
vmovn_u16(vcombine_u16(conflicting[2], conflicting[3])));
uint64_t compared = vget_lane_u64(
vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(combined), 4)), 0);
printf("mask=%016lx compared=%016lx\n", mask, compared);
return !(compared & mask);
}
int main() {
Node16 n{};
n.numChildren = 5;
n.index[0] = 0; n.index[1] = 1; n.index[2] = 2;
n.index[3] = 3; n.index[4] = 100;
for (int i = 0; i < 16; ++i) n.childMaxVersion[i] = 1;
n.index[5] = 50; // stale, uninitialized-like
n.childMaxVersion[5] = 100; // stale high version
scan16(&n, 51, 150, 5); // loads childMaxVersion[5]
}
```
Compile and run on aarch64:
```sh
c++ -std=c++20 -O2 repro.cpp -o repro
./repro
```
The program prints that `compared` includes the bit for slot 5 even though the final mask happens to discard it. A MemorySanitizer build of the same pattern inside `ConflictSet.cpp` reports the uninitialized load.
## Expected behavior
`Node16` copy operations should initialize (or clear) the unused `children` and `childMaxVersion` slots, or the SIMD helpers should only load the valid slots. Either way, the helpers should not perform undefined reads of unused positions.
## Actual behavior
The NEON paths load all 16 `childMaxVersion` / `children` / `index` entries regardless of `numChildren`. Because the unused entries are not initialized by `Node16::copyChildrenAndKeyFrom`, the code reads uninitialized memory.
## Impact
- Undefined behavior on every `Node16` lookup/scan when `numChildren` is less than 16 (which is the normal case for most of the tree's lifetime).
- False positives under MemorySanitizer / valgrind, making sanitizer CI noisy.
- Potential for silent wrong answers if an uninitialized `childMaxVersion` value or stale `index` byte happens to influence a masked comparison; while the current mask happens to discard the upper nibble of the last partially-covered lane, the load itself is still undefined and future compiler optimizations may exploit it.
## Environment
- Repository: `weaselab/conflict-set`, `main` branch (commit `9d15af7`).
- aarch64, GCC or Clang with `HAS_ARM_NEON` defined.
This was all written under the assumption that the rules were basically what valgrind tracks, but after reading https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf#subsection.6.7.4 I think this report is accurate. It's fixed on main for x86, and msan even reported it with -O0. Unfortunately it doesn't seem to report it with -O0 on arm, so we can't do red->green exactly. We can just use the same approach with implementing it in assembly (where it's not UB) as we did for x86
This was all written under the assumption that the rules were basically what valgrind tracks, but after reading https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf#subsection.6.7.4 I think this report is accurate. It's fixed on main for x86, and msan even reported it with -O0. Unfortunately it doesn't seem to report it with -O0 on arm, so we can't do red->green exactly. We can just use the same approach with implementing it in assembly (where it's not UB) as we did for x86
weaselbot
was assigned by andrew2026-08-03 02:26:50 +00:00
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
Summary
On aarch64 builds (
HAS_ARM_NEON), theNode16SIMD helpersgetChildGeq,scan16, andcheckMaxBetweenExclusiveImplload the full 16-elementindex/childMaxVersion/childrenarrays, butNode16::copyChildrenAndKeyFromonly initializes the slots that are currently in use (0 .. numChildren-1). The remaining slots are uninitialized, so the NEON loads read uninitialized memory. This is undefined behavior and can produce false MSan/valgrind reports (or, in principle, wrong conflict/commit decisions if the stale bytes happen to line up unfavorably with a query).Where
ConflictSet.cppline 504-514:Node16::copyChildrenAndKeyFrom(const Node16&)copiesindexfully but only copieschildrenandchildMaxVersionfori < numChildren.ConflictSet.cpplines 1277-1294:getChildGeq(Node16*)ARM NEON path doesmemcpy(&indices, self->index, sizeof(self->index))and builds a mask over(uint64_t(1) << (numChildren * 4)) - 1.ConflictSet.cpplines 2303-2320:checkMaxBetweenExclusiveImpl<Node16>does the same kind of full 16-byte load and mask.scan16around lines 2101-2131.Reproduction
The helper is isolated below. A
Node16withnumChildren == 5leaves slot 5 uninitialized. In this synthetic case we poison slot 5 with a stale high index and a highchildMaxVersion. The helper loads all 16 values and computes a mask; the stale slot'schildMaxVersionis loaded and compared even though the final mask discards that lane's result. Under MemorySanitizer this is reported as a use of uninitialized memory; under a plain build it is still an undefined read.Compile and run on aarch64:
The program prints that
comparedincludes the bit for slot 5 even though the final mask happens to discard it. A MemorySanitizer build of the same pattern insideConflictSet.cppreports the uninitialized load.Expected behavior
Node16copy operations should initialize (or clear) the unusedchildrenandchildMaxVersionslots, or the SIMD helpers should only load the valid slots. Either way, the helpers should not perform undefined reads of unused positions.Actual behavior
The NEON paths load all 16
childMaxVersion/children/indexentries regardless ofnumChildren. Because the unused entries are not initialized byNode16::copyChildrenAndKeyFrom, the code reads uninitialized memory.Impact
Node16lookup/scan whennumChildrenis less than 16 (which is the normal case for most of the tree's lifetime).childMaxVersionvalue or staleindexbyte happens to influence a masked comparison; while the current mask happens to discard the upper nibble of the last partially-covered lane, the load itself is still undefined and future compiler optimizations may exploit it.Environment
weaselab/conflict-set,mainbranch (commit9d15af7).HAS_ARM_NEONdefined.This was all written under the assumption that the rules were basically what valgrind tracks, but after reading https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf#subsection.6.7.4 I think this report is accurate. It's fixed on main for x86, and msan even reported it with -O0. Unfortunately it doesn't seem to report it with -O0 on arm, so we can't do red->green exactly. We can just use the same approach with implementing it in assembly (where it's not UB) as we did for x86