Allocation: Add copyspaces

We will now change your MyGC plan from one that cannot collect garbage into one that implements the semispace algorithm. The first step of this is to add the two copyspaces, and allow collectors to allocate memory into them. This involves adding two copyspaces, the code to properly initialise and prepare the new spaces, and a copy context.

Change the plan constraints

Firstly, change the plan constraints. Some of these constraints are not used at the moment, but it's good to set them properly regardless.

Look in plan/plan_constraints.rs. PlanConstraints lists all the possible options for plan-specific constraints. At the moment, MYGC_CONSTRAINTS in mygc/global.rs should be using the default value for PlanConstraints. We will make the following changes:

  1. Initialize gc_header_bits to 2. We reserve 2 bits in the header for GC use.
  2. Initialize moves_objects to true.

Finished code (step 1-3):

pub const MYGC_CONSTRAINTS: PlanConstraints = PlanConstraints {
    moves_objects: true,
    ..PlanConstraints::default()
};

Change the plan implementation

Next, in mygc/global.rs, replace the old immortal (nogc) space with two copyspaces.

Imports

To the import statement block:

  1. Replace crate::plan::global::{BasePlan, NoCopy}; with use crate::plan::global::BasePlan;. This collector is going to use copying, so there's no point to importing NoCopy any more.
  2. Add use crate::plan::global::CommonPlan;. Semispace uses the common plan, which includes an immortal space and a large object space, rather than the base plan. Any garbage collected plan should use CommonPlan.
  3. Add use std::sync::atomic::{AtomicBool, Ordering};. These are going to be used to store an indicator of which copyspace is the tospace.
  4. Delete #[allow(unused_imports)].

Finished code (step 1):

#![allow(unused)]
fn main() {
use crate::plan::global::BasePlan; //Modify
use crate::plan::global::CommonPlan; // Add
use crate::plan::global::{CreateGeneralPlanArgs, CreateSpecificPlanArgs};
use crate::plan::mygc::mutator::ALLOCATOR_MAPPING;
use crate::plan::mygc::gc_work::MyGCWorkContext;
use crate::plan::AllocationSemantics;
use crate::plan::Plan;
use crate::plan::PlanConstraints;
use crate::policy::copyspace::CopySpace; // Add
use crate::policy::space::Space;
use crate::scheduler::*; // Modify
use crate::util::alloc::allocators::AllocatorSelector;
use crate::util::copy::*;
use crate::util::heap::VMRequest;
use crate::util::heap::gc_trigger::SpaceStats;
use crate::util::metadata::side_metadata::SideMetadataContext;
use crate::util::opaque_pointer::*;
use crate::vm::VMBinding;
use enum_map::EnumMap;
use std::sync::atomic::{AtomicBool, Ordering}; // Add
}

Struct MyGC

Change pub struct MyGC<VM: VMBinding> to add new instance variables.

  1. Delete the existing fields in the constructor.
  2. Add pub hi: AtomicBool,. This is a thread-safe bool, indicating which copyspace is the tospace.
  3. Add pub copyspace0: CopySpace<VM>, and pub copyspace1: CopySpace<VM>,. These are the two copyspaces.
  4. Add pub common: CommonPlan<VM>,. This holds an instance of the common plan.

Finished code (step 2):

#![allow(unused)]
fn main() {
#[derive(HasSpaces, PlanTraceObject)]
pub struct MyGC<VM: VMBinding> {
    pub hi: AtomicBool,
    #[space]
    #[copy_semantics(CopySemantics::DefaultCopy)]
    pub copyspace0: CopySpace<VM>,
    #[space]
    #[copy_semantics(CopySemantics::DefaultCopy)]
    pub copyspace1: CopySpace<VM>,
    #[parent]
    pub common: CommonPlan<VM>,
}
}

Note that MyGC now also derives PlanTraceObject besides HasSpaces, and we have attributes on some fields. These attributes tell MMTk's macros how to generate code to visit each space of this plan as well as trace objects in this plan. Although there are other approaches that you can implement object tracing, in this tutorial we use the macros, as it is the simplest. Make sure you import the macros. We will discuss on what those attributes mean in later sections.

#![allow(unused)]
fn main() {
use mmtk_macros::{HasSpaces, PlanTraceObject};
}

Implement the Plan trait for MyGC

Constructor

Change fn new(). This section initialises and prepares the objects in MyGC that you just defined.

  1. Delete the definition of mygc_space. Instead, we will define the two copyspaces here.
  2. Define one of the copyspaces by adding the following code:
#![allow(unused)]
fn main() {
            copyspace0: CopySpace::new(plan_args.get_space_args("copyspace0", true, false, VMRequest::discontiguous()), false),
}
  1. Create another copyspace, called copyspace1, defining it as a fromspace instead of a tospace. (Hint: the definitions for copyspaces are in src/policy/copyspace.rs.)
  2. Finally, replace the old MyGC initializer.
#![allow(unused)]
fn main() {
    fn new(args: CreateGeneralPlanArgs<VM>) -> Self {
        // Modify
        let mut plan_args = CreateSpecificPlanArgs {
            global_args: args,
            constraints: &MYGC_CONSTRAINTS,
            global_side_metadata_specs: SideMetadataContext::new_global_specs(&[]),
        };

        let res = MyGC {
            hi: AtomicBool::new(false),
            copyspace0: CopySpace::new(plan_args.get_space_args("copyspace0", true, false, VMRequest::discontiguous()), false),
            copyspace1: CopySpace::new(plan_args.get_space_args("copyspace1", true, false, VMRequest::discontiguous()), true),
            common: CommonPlan::new(plan_args),
        };

        res.verify_side_metadata_sanity();

        res
    }
}

Access MyGC spaces

Add a new section of methods for MyGC:

#![allow(unused)]
fn main() {
impl<VM: VMBinding> MyGC<VM> {
}
}

To this, add two helper methods, tospace(&self) and fromspace(&self). They both have return type &CopySpace<VM>, and return a reference to the tospace and fromspace respectively. tospace() (see below) returns a reference to the tospace, and fromspace() returns a reference to the fromspace.

We also add another two helper methods to get tospace_mut(&mut self) and fromspace_mut(&mut self). Those will be used later when we implement collection for our GC plan.

#![allow(unused)]
fn main() {
    pub fn tospace(&self) -> &CopySpace<VM> {
        if self.hi.load(Ordering::SeqCst) {
            &self.copyspace1
        } else {
            &self.copyspace0
        }
    }

    pub fn fromspace(&self) -> &CopySpace<VM> {
        if self.hi.load(Ordering::SeqCst) {
            &self.copyspace0
        } else {
            &self.copyspace1
        }
    }

    pub fn tospace_mut(&mut self) -> &mut CopySpace<VM> {
        if self.hi.load(Ordering::SeqCst) {
            &mut self.copyspace1
        } else {
            &mut self.copyspace0
        }
    }

    pub fn fromspace_mut(&mut self) -> &mut CopySpace<VM> {
        if self.hi.load(Ordering::SeqCst) {
            &mut self.copyspace0
        } else {
            &mut self.copyspace1
        }
    }
}

Other methods in the Plan trait

The trait Plan requires a common() method that should return a reference to the common plan. Implement this method now.

#![allow(unused)]
fn main() {
    fn common(&self) -> &CommonPlan<VM> {
        &self.common
    }
}

Find the helper method base and change it so that it calls the base plan through the common plan.

#![allow(unused)]
fn main() {
    fn base(&self) -> &BasePlan<VM> {
        &self.common.base
    }

    fn base_mut(&mut self) -> &mut BasePlan<Self::VM> {
        &mut self.common.base
    }
}

The trait Plan requires collection_required() method to know when we should trigger a collection. We can just use the implementation in the BasePlan.

#![allow(unused)]
fn main() {
    fn collection_required(&self, space_full: bool, _space: Option<SpaceStats<Self::VM>>) -> bool {
        self.base().collection_required(self, space_full)
    }
}

Find the method get_pages_used. Replace the current body with self.tospace().reserved_pages() + self.common.get_pages_used(), to correctly count the pages contained in the tospace and the common plan spaces (which will be explained later).

#![allow(unused)]
fn main() {
    fn get_used_pages(&self) -> usize {
        self.tospace().reserved_pages() + self.common.get_used_pages()
    }
}

Add and override the following helper function:

#![allow(unused)]
fn main() {
    fn get_collection_reserved_pages(&self) -> usize {
        self.tospace().reserved_pages()
    }
}

Change the mutator definition

Next, we need to change the mutator, in mutator.rs, to allocate to the tospace, and to the two spaces controlled by the common plan.

Imports

Change the following import statements:

  1. Add use super::MyGC;.
  2. Add use crate::util::alloc::BumpAllocator;.
  3. Delete use crate::plan::mygc::MyGC;.
#![allow(unused)]
fn main() {
use super::MyGC; // Add
use crate::MMTK;
use crate::plan::barriers::NoBarrier;
use crate::plan::mutator_context::Mutator;
use crate::plan::mutator_context::MutatorConfig;
use crate::plan::AllocationSemantics;
use crate::util::alloc::allocators::{AllocatorSelector, Allocators};
use crate::util::alloc::BumpAllocator;
use crate::util::opaque_pointer::*;
use crate::vm::VMBinding;
use crate::plan::mutator_context::{
    create_allocator_mapping, create_space_mapping, ReservedAllocators,
};
use enum_map::EnumMap;
// Remove crate::plan::mygc::MyGC
// Remove mygc_mutator_noop
}

Allocator mapping

In lazy_static!, make the following changes to ALLOCATOR_MAPPING, which maps the required allocation semantics to the corresponding allocators. For example, for Default, we allocate using the first bump pointer allocator (BumpPointer(0)):

  1. Define a ReservedAllocators instance to declare that we need one bump allocator.
  2. Map the common plan allocators using create_allocator_mapping.
  3. Map Default to BumpPointer(0).
#![allow(unused)]
fn main() {
const RESERVED_ALLOCATORS: ReservedAllocators = ReservedAllocators {
    n_bump_pointer: 1,
    ..ReservedAllocators::DEFAULT
};

lazy_static! {
    pub static ref ALLOCATOR_MAPPING: EnumMap<AllocationSemantics, AllocatorSelector> = {
        let mut map = create_allocator_mapping(RESERVED_ALLOCATORS, true);
        map[AllocationSemantics::Default] = AllocatorSelector::BumpPointer(0);
        map
    };
}
}

Space mapping

Next, in create_mygc_mutator, change which allocator is allocated to what space in space_mapping. Note that the space allocation is formatted as a list of tuples. For example, the first bump pointer allocator (BumpPointer(0)) is bound with tospace.

Downcast the dynamic Plan type to MyGC so we can access specific spaces in MyGC.

#![allow(unused)]
fn main() {
    let mygc = mmtk.get_plan().downcast_ref::<MyGC<VM>>().unwrap();
}

Then, use mygc to access the spaces in MyGC.

  1. BumpPointer(0) should map to the tospace.
  2. Other common plan allocators should be mapped using create_space_mapping.
  3. None of the above should be dereferenced (ie, they should not have the & prefix).
#![allow(unused)]
fn main() {
        space_mapping: Box::new({
            let mut vec = create_space_mapping(RESERVED_ALLOCATORS, true, mygc);
            vec.push((AllocatorSelector::BumpPointer(0), mygc.tospace()));
            vec
        }),
}

The create_space_mapping and create_allocator_mapping call that have appeared all of a sudden in these past 2 steps, are parts of the MMTk common plan itself. They are used to construct allocator-space mappings for the spaces defined by the common plan:

  1. The immortal space is used for objects that the virtual machine or a library never expects to die.
  2. The large object space is needed because MMTk handles particularly large objects differently to normal objects, as the space overhead of copying large objects is very high. Instead, this space is used by a free list allocator in the common plan to avoid having to copy them.
  3. The read-only space is used to store all the immutable objects.
  4. The code spaces are used for VM generated code objects.

With this, you should have the allocation working, but not garbage collection. Try building again. If you run HelloWorld or Fannkunchredux, they should work. DaCapo's lusearch should fail, as it requires garbage to be collected.