Incorrect align_allocate and get_maximum_aligned_size

[qinsoon]

Java MMTk object size assumption

Our code about allocation and alignment calculation is ported from Java MMTk. There is an assumption about Java MMTk that an object size is always a multiple of known alignment. (code)

if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(size == Conversions.roundDown(size, knownAlignment));

known_alignment means we know the actual alignment of the current allocation cursor, e.g. the start of a cell (free list allocator), or the start of a page (large object allocator). known_alignment is a multiple of min alignment. So in Java MMTk, an object size is always a multiple of min alignment. When we do not have an actual known_alignment, MIN_ALIGNMENT is used instead.

With this assumption, we know that the start of an allocation is aligned to min alignment, and the size is aligned to min alignment. Then we know that at the end of an allocation, the address is always aligned to min alignment. That means when we start the next allocation, the address is aligned to min alignment. (code)

VM.assertions._assert(region.toWord().and(Word.fromIntSignExtend(MIN_ALIGNMENT - 1)).isZero());

This is also why Java MMTk often uses MIN_ALIGNMENT as the default value for known_alignment.

  public static Address alignAllocation(Address region, int alignment, int offset) {
    return alignAllocation(region, alignment, offset, MIN_ALIGNMENT, true);
  }

  public static int getMaximumAlignedSize(int size, int alignment) {
    return getMaximumAlignedSize(size, alignment, MIN_ALIGNMENT);
  }

Java MMTk also assumes the alignment offset is a multiple of minimal alignment. (code)

VM.assertions._assert((offset & (MIN_ALIGNMENT - 1)) == 0);

We initially ported all the code from Java MMTk, so mmtk-core also has those assumptions.

Rust MMTk: ALLOC_END_ALIGNMENT

We noticed that the assertion about object size failed, and changed that assertion in #140 by introducing a VM-specific constant ALLOC_END_ALIGNMENT. This allows the VM to specify the alignment at the end of an allocation (start + size), and when we calculate the alignment of the next allocation, we know the current cursor is at least aligned to ALLOC_END_ALIGNMENT.

mmtk-core/src/util/alloc/allocator.rs

Line 58 in 06237f1

debug_assert!(region.is_aligned_to(VM::ALLOC_END_ALIGNMENT));

With this change, a VM can call MMTk with arbitrary object sizes. However, though we changed the assertion, we did not correctly change some of the code that still needs this object size assumption to work. For example,

mmtk-core/src/util/alloc/allocator.rs

Lines 23 to 39 in 06237f1

	#[inline(always)]
	pub fn align_allocation_no_fill<VM: VMBinding>(
	region: Address,
	alignment: usize,
	offset: isize,
	) -> Address {
	align_allocation_inner::<VM>(region, alignment, offset, VM::MIN_ALIGNMENT, false)
	}
	#[inline(always)]
	pub fn align_allocation<VM: VMBinding>(
	region: Address,
	alignment: usize,
	offset: isize,
	) -> Address {
	align_allocation_inner::<VM>(region, alignment, offset, VM::MIN_ALIGNMENT, true)
	}

• we should use ALLOC_END_ALIGNMENT instead.
• We should also use known_alignment whenever we know the known alignment, e.g. mimalloc allocator's cell is aligned to address size, large object allocator's allocation is aligned to pages.

Bug in Java MMTk?

Java MMTk calculates aligned size without using offset. (code)
(MIN_ALIGNMENT = 4, MAX_ALIGNMENT = 8 for Java MMTk/JikesRVM)

  public static int getMaximumAlignedSize(int size, int alignment, int knownAlignment) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(size == Conversions.roundDown(size, knownAlignment));
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(knownAlignment >= MIN_ALIGNMENT);

    if (MAX_ALIGNMENT <= MIN_ALIGNMENT || alignment <= knownAlignment) {
      return size;
    } else {
      return size + alignment - knownAlignment;
    }
  }

I think this is incorrect. For example, when we try allocate an object of size = 8, alignment = 8, offset = 4 in a free list cell that is aligned to 8 (knownAlignment = 8). As alignment <= knowAlignment, this method will simply return the size 8. But we need at least 12 bytes to accomodate the request of size = 8, alignment = 8, offset = 4 with a cursor aligned at 8.

Similarly under those conditions, alignAllocation also just returns region without any alignment padding. (code)

    // No alignment ever required.
    if (alignment <= knownAlignment || MAX_ALIGNMENT <= MIN_ALIGNMENT)
      return region;

• We possibly need to pass offset to get_maximum_aligned_size. When offset is not used, or is zero, we can do the simple check as what it is now. Otherwise, we will have to compute the alignment padding, and count that into the size.

[qinsoon]

About align_allocate, there are two issues:

• Our contract is unclear with the bindings: do we allow arbitrary object size (unaligned object size) or not?
• If a binding gives arbitrary object size, we are not doing alignment properly.

We can change ALLOC_END_ALIGNMENT to SIZE_ALIGNMENT. We can use different approaches to align objects depending on whether the size is aligned or not.

[k-sareen]

Our LinearScan code also assumes that the object sizes are multiples of MIN_ALIGNMENT:

mmtk-core/src/util/linear_scan.rs

Lines 52 to 57 in 0d6ef2c

	if let Some(object) = is_object {
	self.cursor += S::size(object);
	return Some(object);
	} else {
	self.cursor += VM::MIN_ALIGNMENT;
	}