Efficient allocation bits

[steveblackburn]

Maintaining a bit within side metadata that marks the start of every object is necessary for a number of collector algorithms and for standard implementations of interior pointers. Such a bit also has other more general advantages such as fast checks of address validity (useful for correctness and for conservative collection), and for linear memory scans.

MMTk has some implementations of this, but we do not yet have an implementation that is sufficiently high performance that can be left 'turned on'.

[qinsoon]

We need to introduce an alloc bit implementation. It sets a bit in the side metadata for objects allocated so we know the start of objects. This can be used to support internal pointer and heap iteration. What we can possibly do is to have a new feature global_alloc_bit, and in the future, internal_pointer or heap_iteration should rely on the feature. Only when the feature global_alloc_bit is enabled, we will set the bit in the post_alloc(). Otherwise, there should be no overhead.

Some policies such as MallocSpace already implemented their own alloc bits (local side metadata spec). In such cases, we do not need both global and their local alloc bits. We should think about how to implement this properly: either skip the global alloc bit for those policies, or skip the local one when the global_alloc_bit feature is enabled.

[qinsoon]

A rough plan for the implementation:

• Create a new module util::alloc_bit.
• Create a new feature global_alloc_bit.
• Create a new global side metadata for the alloc bit. 1 bit per min object size.
  • update the constants in util::metadata::side_metadata::constants
  • Provide functions like set_alloc_bit, unset_alloc_bit, test_alloc_bit, bulk_zero_alloc_bit.
• Add the alloc bit spec to plans:
  • In SideMetadataSpecs::new_global_specs(), add the spec to the vector if the global_alloc_bit feature is enabled.
  • In the constructor of the marksweep plan, add the side metadata spec if the global_alloc_bit feature is NOT enabled.
• Set bit in initialize_object_metadata() for each policy:
  • In MallocSpace, always set alloc bit
  • In other policies, set alloc bit if global_alloc_bit is enabled.
• Unset/zero bits for each policy:
  • immortal spaces: no need to unset
  • copy space: bulk zero the bits when a space is released
  • malloc space: unset the bit when an object is freed
  • large object space: check release() and sweep_large_pages(). I think we need to change the PR's release_pages() so the PR tells the space what pages have been released and the space can bulk zero the alloc bits for it.
• Remove the alloc bit spec in MallocSpace, and change all the related functions to use the functions from the new alloc bit module.

[javadamiri]

Depending on how you mmap the side metadata space for alloc bit, (e.g. if it is eagerly mmaped), you may need special considerations for including it in the global specs list of a plan.
For example, you should take care to avoid mapping alloc bit twice.

In marksweep, there is the ACTIVE_CHUNK_METADATA_SPEC side metadata spec, which is used in conjunction with the alloc-bit to make sure the chunk's metadata is mapped before checking its content.
I'm not sure about your implementation, but you may also need to consider this.
I will add here if I remember anything else.

[qinsoon]

This is done in #390.