SFTSpaceMap::get_checked doesn't check out-of-heap addresses

[wks]

SFTMap::get_checked(address) should get the SFT for the address, and it should return EmptySpaceSFT if the address does not belong to any space. For SFTSpaceMap, it maintains a small array of 32 entries, one for each space.

However, SFTSpaceMap::addr_to_index simply extracts the bit 45 to 41 from the address and uses those five bits as the index. It works if the address is actually in one of the spaces. However, when used for the purpose of VO bits check (is_mmtk_object), the input can be an arbitrary address. Using the same algorithm, it may yield funny results such as telling me

• address: 0xff040104ca4008, index: 2, sft len: 32, space: immortal
• address: 0x16608296ea09198, index: 4, sft len: 32, space: nonmoving
• address: 0xd7de430f21ef9400, index: 1, sft len: 32, space: immix
• address: 0xf1378995f50025e8, index: 4, sft len: 32, space: nonmoving

VO bits have been working find so far because FragmentedMapper::get_or_optionally_allocate_slab_table(addr, allocate) happy accepts those ridiculous addresses (e.g. 0xf1378995f50025e8), gets their metadata addresses (e.g. 0x3c4ea2657d40097, which I have no idea how it computed that), computes their base addresses (e.g. 0x3c4ea2657d40097 -> 0x3c4ea2640000000), computes the hash (e.g. 0x3c4ea2640000000 -> 720), and fails to find 0x3c4ea2640000000 in the hash table. This will cause is_mapped_address to simply return false and report that it is not a valid MMTk address.

Then I found the problem when I was debugging the experimental MultiLevelMapper in #1337. It only governs a fixed address range, and if attempts to look up the slabs table with an address outside the address space range (which I set to 1<<48), it will result in an indexing error.

Solution

We can solve the problem by either performing address range check in SFTSpaceMap::addr_to_index, or in is_mmtk_object::check_object_reference.

But more importantly, we should clarify the contract of SFTMap::get_checked(address), particularly make it clear whether the caller is allowed to pass an address that is

1. not the raw address of a valid ObjectReference, or
2. not within any allocated object, or
3. not within any mapped memory, or
4. not within the range of any space, or
5. not within the MMTk-managed heap address range, or
6. not within the address size of the architecture (e.g. 48 bits for x86_64).

My preliminary thought is that SFTMap is most often used for dispatching by valid ObjectReference. In that case, we should reflect this by providing a method such as SFTMap::from_object(object: ObjectReference). If we dispatch from interior pointers, addresses in a line, block, chunk, etc, we should provide methods that explicitly allows such accesses. And as a last resort, we may provide a variant of get_checked that accepts absolutely any address. For SFTSpaceMap, it only needs to do a range check before extracting the bits to compute index.

[qinsoon]

VO bits have been working find so far because FragmentedMapper::get_or_optionally_allocate_slab_table(addr, allocate) happy accepts those ridiculous addresses (e.g. 0xf1378995f50025e8), gets their metadata addresses (e.g. 0x3c4ea2657d40097, which I have no idea how it computed that), computes their base addresses (e.g. 0x3c4ea2657d40097 -> 0x3c4ea2640000000), computes the hash (e.g. 0x3c4ea2640000000 -> 720), and fails to find 0x3c4ea2640000000 in the hash table. This will cause is_mapped_address to simply return false and report that it is not a valid MMTk address.

This part actually is expected. It is the side metadata module that computes from an arbitrary data address to its metadata address (regardless whether it is in the heap or not), and then query the Mmapper whether the metadata address is mapped. For an off heap address, its metadata address is not mapped.

we should clarify the contract of SFTMap::get_checked(address)

The function states that it takes an arbitrary address. So this is a bug for SFTSpaceMap's implementation of get_checked. We probably should just call has_sft_entry in get_checked.

mmtk-core/src/policy/sft_map.rs

Lines 29 to 32 in 7fe0e05

	/// Get SFT for the address. The address can be arbitrary. For out-of-bound access, an empty SFT will be returned.
	/// We only provide the checked version for `get()`, as it may be used to query arbitrary objects and addresses. Other methods like `update/clear/etc` are
	/// mostly used inside MMTk, and in most cases, we know that they are within our space address range.
	fn get_checked(&self, address: Address) -> &dyn SFT;