microsoft / microsoft/snmalloc

`range_to_pow_2_blocks` can underflow `length` (`size_t`)

Open
#567 7 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

repro needed
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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.