microsoft / microsoft/snmalloc
`range_to_pow_2_blocks` can underflow `length` (`size_t`)
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 2k
- Forks
- 138
- Avg merge
- 11h 19m
- Merged PRs (30d)
- 5
Description
From backend_helpers/range_helpers.h
template<size_t MIN_BITS, SNMALLOC_CONCEPT(capptr::IsBound) B, typename F>
void range_to_pow_2_blocks(CapPtr<void, B> base, size_t length, F f)
{
auto end = pointer_offset(base, length);
base = pointer_align_up(base, bits::one_at_bit(MIN_BITS));
end = pointer_align_down(end, bits::one_at_bit(MIN_BITS));
length = pointer_diff(base, end);
bool first = true;
// Find the minimum set of maximally aligned blocks in this range.
// Each block's alignment and size are equal.
while (length >= sizeof(void*))
{
size_t base_align_bits = bits::ctz(address_cast(base));
size_t length_align_bits = (bits::BITS - 1) - bits::clz(length);
size_t align_bits = bits::min(base_align_bits, length_align_bits);
size_t align = bits::one_at_bit(align_bits);
/*
* Now that we have found a maximally-aligned block, we can set bounds
* and be certain that we won't hit representation imprecision.
*/
f(base, align, first);
first = false;
base = pointer_offset(base, align);
length -= align;
}
}
Length can underflow here. As a result, the loop calls f(base, align, first) on ever-increasing values for base. This leads to runtime length-violations on CHERI RISC-V.
I've taken a blunt instrument to this locally in the form of:
...
base = pointer_offset(base, align);
if (length < align)
return;
length -= align;
...
This eliminates the crashes I was seeing, but I'm not sure this is the proper solution.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in src/snmalloc/backend_helpers/range_helpers.h at range_to_pow_2_blocks and inspect how alignment changes length before the loop subtracts each block. Reproduce the CHERI RISC-V runtime length violation described in the issue, then verify that the function no longer underflows length or calls f with invalid bounds.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100