Two-step spaces instantiation

[wks]

TL;DR: Some info for creating spaces (such as the sizes and locations of discontiguous spaces) can only be determined when all spaces have been specified (i.e. when all contiguous spaces are placed). Instead of creating spaces and mutating them, let's make the Plan specify all spaces first so that the information of all spaces are available when creating them.

Related issue: #853

Status quo

Deciding whether a space is contiguous

Currently, when a Plan create spaces that it doesn't care whether it is contiguous or discontiguous, it calls VMRequest::discontiguous(). However, inside VMRequest::discontiguous(), if vm_layout().force_use_contiguous_spaces() is true, it will secretly create a VMRequest::Extent instead. This is not graceful because plans say "discontiguous" but may eventually get a contigous space. Plans should be able to express the idea of "I don't care" directly.

Patching spaces after creating spaces

The problem can be seen obviously in MMTK::new(). It calls create_plan which creates the Plan and all Space instances. But after that, it still needs to call VM_MAP.boot() (which does nothing) and VM_MAP.finalize_static_space_map which computes the range of discontiguous spaces. This is the root cause of the global mutable references to internal fields of many spaces and page resources. More specifically,

• Map32 keeps a shared_fl_map: Vec<Option<NonNull<CommonFreeListPageResource>>> in order to fix the start address of each space.

(Note: Map64::fl_page_resources and Map64::fl_map existed for a different reason. See #953 They should be removed, but are unrelated to this issue.)

Indices of spaces

Several places need "space index". For example,

• The SpaceDescriptor gives each space an index. That index is encoded into the descriptor, and can be used to look up a index-to-space mappings (Map64::high_water, Map64::base_address, and Map64::fl_map. The last one should be removed).
• The DenseChunkMap gives each space an index, too. That index is used to look up the second level of the SFT.

The two indices are assigned in two different places, and are not the same. This is redundant. We should be able to assign a unique index to each space.

(Note: Actually, as we discussed before (See this PR and this Zulip topic) , SpaceDescriptor and SFT serve similar purposes (looking up metadata and operations, respectively, given an address).)

Proposed changes

Instead of letting the plan (and sub-structures such as Gen, CommonPlan and BasePlan) create spaces immediately, we create spaces in multiple steps:

1. Specify the spaces to create and their requirements (contiguous/discontiguous, freelist/monotonic/external, ...)
2. Compute the ranges of each space
3. Create each space

Simple example

Suppose we want to create a GenImmix plan. In this example we simply flatten all spaces into one scope.

let mut space_placer = SpacePlacer::new(); // Can we have a better name?

// specify the requirements
let immix_f: Future<SpacePlacement> = space_placer.specify(DontCare, FreeList, AsBigAsPossible);
let nursery_f: Future<SpacePlacement> = space_placer.specify(Contiguous, Monotonic, FixedExtent(32*MiB));
let los_f: Future<SpacePlacement> = space_placer.specify(DontCare, FreeList, AsBigAsPossible);
let vm_space_f: Future<SpacePlacement> = space_placer.specify(Contiguous, External, FixedRange(VM_START, VM_END));

// Determine the places
space_placer.place();

// Construct concrete spaces
let vm_space = {
    let place = vm_space_f.get();
    VMSpace::new("vm_space", place.start, other_space_args)
};
let los = {
    let place = los_f.get();
    LargeObjectSpace::new("los", place.is_contigous, place.start, other_space_args)
};
let nursery = {
    let place = nursery_f.get();
    CopySpace::new("nursery", place.is_contigous, place.start, place.end, other_space_args)
};
let immix = {
    let place = immix_f.get();
    ImmixSpace::new("immix_mature", place.is_contigous, place.start, other_space_args)
};

The main idea is, the Plan gets a Future<SpacePlacement> before creating spaces. The SpacePlacer promises to give it a placement descriptor after calling space_placer.place(). Then the concrete SpacePlacement will provide information about the space-placing decisions made by the SpacePlacer, such as whether the space is contiguous, where it starts (and ends if it cares), etc.

Complex example

In reality, a Plan is implemented as nested structs. We can specify spaces from outside in, and construct spaces from inside out.

impl GenImmix {
    fn new() -> Self {
        let mut space_placer = SpacePlacer::new();

        // Specify the spaces at the current level
        let immix_f: Future<SpacePlacement> = space_placer.specify(DontCare, FreeList, AsBigAsPossible);

        // Let the nested structs specify and construct its spaces
        let common_gen = CommonGenPlan::new(&mut space_placer);

        // Finish creating my spaces
        let immix = {
            let place = immix_f.get();
            ImmixSpace::new("immix_mature", place.is_contigous, place.start, other_space_args)
        };

        // other things...
    }
}

impl CommonGenPlan {
    fn new(space_placer: &mut SpacePlacer) -> Self {
        // We borrowed the space_placer from parent.

        // Specify the spaces at the current level
        let nursery_f: Future<SpacePlacement> = space_placer.specify(Contiguous, Monotonic, FixedExtent(32*MiB));
        
        // Let the nested structs specify and construct its spaces
        let common = CommonPlan::new(&mut space_placer);

        // Finish creating my spaces
        let nursery = {
            let place = nursery_f.get();
            CopySpace::new("nursery", place.is_contigous, place.start, place.end, other_space_args)
        };

        // other things...
    }
}

In BasePlan, we can call SpacePlacer::place() to trigger the placement.

impl BasePlan {
    fn new(space_placer: &mut SpacePlacer) -> Self {
        // Specify code_space, code_lo_space, ro_space, vm_space if enabled
        // ...

        // Actually call place()
        space_placer.place();

        // Actually instantiate code_space, code_lo_space, ro_space, vm_space if enabled
        // ...
    }
}