range_to_pow_2_blocks can underflow length (size_t)

[pentelbart]

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.

[pentelbart]

Example values for this are: 0x40b2d000 and 0 for base and length respectively.

[mjp41]

So would

    ...
    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);

    if (base >= end)
      return;

    bool first = true;
    ...

Fix the issue?

[pentelbart]

So would

    ...
    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);

    if (base >= end)
      return;

    bool first = true;
    ...

Fix the issue?

A version of that adjusted for the fact that these are CapPtr appears to, however this issue sometimes is coy about presenting. Tentatively yes.

[pentelbart]

Does missing the call to f potentially have consequences in those cases?

[nwf]

Should we be asserting that we call this function only with lengths >= bits::one_at_bit(MIN_BITS)? Where is that not true?

[mjp41]

Does missing the call to f potentially have consequences in those cases?

It shouldn't mater if we don't call f. It should be callable multiple times, and zero.

Should we be asserting that we call this function only with lengths >= bits::one_at_bit(MIN_BITS)? Where is that not true?

That sounds like a good assert to add.

@pentelbart how did your system end up calling this code with zero?

[pentelbart]

It was called from LargeBuddyRange::refill and the original allocation was 131,072 bytes, however the stack trace obscured some arguments further down the call stack so it's hard to be definite.