Not unlike the distinction between Child and Local for capabilities, we should also include a VSpace state which denotes that it is being prepared for a child's usage.

Consider as an example the creation of a child process in a child process: https://github.com/auxoncorp/ferros/blob/ad3807bcd7a98bfc1f487a24339a7d2670ad4f3c/qemu-test/test-project/src/grandkid_process_runs.rs#L65-L72

It is of course standard to be operating on a child's VSpace; what is not standard here, is that this child intends to create a child of its own. That's why we map pages into its address space and move the capabilities to the child's CSpace. The child will use this mapped region as scratch for creating its own child's stack. ~It is for this use case that we'd like to have a state in vspace_state for a process's VSpace whose intent is to beget children.~¹ This state shall also add type-level guardrails to prevent a developer from mixing local and child capabilities, &c.

1. See comment below regarding a CNodeRole index.

Summary

Now that we have WUTBuddy::alloc_strong, we can provide the same API that Allocator::get_untyped gives us, but we can do it with WUTBuddy underneath! We can also use something buddy-like for tracking device memory, however, it will need to be supplemented with the ability to look things up by physical address which I'll get into later in this issue.

Implementation details

I. Allocation is Janus-like

Where one face looks at general memory, the other at device memory. This results in the effective erasure of Allocator as we know it and from its ashes rises a WUTBuddy backed general memory allocator and a split-based allocator for device memory.

pub struct UntypedAllocator {
    uts: WUTBuddy<role::Local, memory_kind::General>,
}

pub struct DeviceUntypedAllocator {
    device_uts: ArrayVec<[WUntyped<memory_kind::Device>; MAX_DEVICE_UTS]>,
}

Both of these allocators could join the BootInfo family, making there be a single bootstrap call which returns these two objects as part of the boot info structure¹.

Work that this entails

1. WUntypeds do not have memory kinds associated with them. This will likely be the most amount of work as it'll result in threading it into all of the WUntyped usages.
2. A change to allow the construction of the two types above which uses the memory_kind sorting hat to separate device from general memory.
3. For weak_ut_buddy to be able to be constructed around a set of untypeds rather than just one.

II. get_untyped

Its API could remain the same, but I think it will want to return the error from WUTbuddy::alloc_strong for cases where splitting is involved and we get into syscall-land.

Work this entails

1. Delete a lot of code in micro_alloc.rs and make get_untyped delegate to alloc_strong.

III. Device Memory

For device memory, we need something like a buddy allocator, but our lookups aren't about sizes exclusively; they're also about physical addresses. We also have the desire to take only the relevant chunk of some oversized "device region", as mentioned in #30. For this use case, we want our implementation to do 4 things:

1. Find the region in which the device resides.
2. Find the granule(s) in that region in which the device resides.
3. Split that thing up so we can have at that device.
4. Hold on to the caps that come out the other end of those splits and update their respective physical addresses.

Our existing buddy allocator implementations use size as the sorting criterion; we want a slightly different implementation which uses physical addresses as the search criterion, where size only comes into play after we've located the target region.

Before I get into a suggested implementation I'd like to mention a conjecture w/r/t the salience of the type-level tracking of the size of device untypeds: I don't think it matters. We need size like an afterthought so we know how to split—we're not trying to prevent an over-allocation on device memory. Its depletion as a resource is binary, not gradual; the capability to the desired device is there or it is not.

How I imagine this works is as a simple ArrayVec holding WUntypeds whose paddr we're also tracking a lá seL4_UntypedDesc. Lookups search through the vector and find the region the desired device resides in and it's extracted from the list. If it needs to be split, it is—buddy style, and then the new caps are pushed into the vector².

Work this entails

1. Adding paddrs to WUntypeds³.
2. The implementation of the algorithm described above.

Footnotes

1. This I am still unsure of and could be persuaded either way.
2. This is of course pretty memory-thrashy, particularly the drop-and-put-back-together part. This naive implementation's viability is currently pending a response from @jonlamb-gh w/r/t whether this is ever used in the fault path.
3. Only on memory_kind::Device untypeds to reduce intrusion?

By "simultaneous" I mean that VSpace should not provide both modes of mapping at the same time. When it does, we must keep track of the regions created in uses of map_region_at_addr to prevent overlaps in usages of map_region.

Regarding the VMM's use of this: The VM's VSpace should always be in the map_region_at_addr mode. This is counter to a typical process which starts in map_region_at_addr mode to service the user image mapping but then transitions to the mode of "map a region, I don't care where". A future_next_addr member could be added to the "map at" state which gets moved when any region exceeds it.

The seL4 kernel supports running on an ARMv8 ISA, application profile, so should ferros.

It's worth noting that the AAarch32 execution state of ARMv8-A is compatible with an ARMv7-A implementation that includes the Visualization Extensions. This allows us to run 32-bit guest at EL0/EL1 in a 64-bit vmm at EL2 (assuming the exception handling path exist).

Also note that GNU and Linux documentation (except for Redhat and Fedora distributions) sometimes refers to AArch64 as ARM64.

Hardware virtual memory objects

AArch64 supports three different translation granules. These define the block size at the lowest level of translation table and control the size of translation tables in use.

seL4 has picked a translation granule of 4 KB, with the following page sizes:

• seL4_PageBits = 4 KB at level 3
• seL4_LargePageBits = 2 MB at level 2
• seL4_HugePageBits = 1 GB at level 1

In the AArch64 state, there are four levels of paging structures:

• PageGlobalDirectory at level 0
• PageUpperDirectory at level 1
• PageDirectory at level 2
• PageTable at level 3

Where a the VSpace is realized as a PageGlobalDirectory.

All paging structures are indexed by 9 bits of the virtual address, therefore each level can address 2^9 = 512 slots.

Virtual address translation table lookup with 4 KB pages

In the case of a 4 KB granule, the hardware can use a 4-level look up process. The 48-bit address has nine address bits for each level translated (that is, 512 entries each), with the final 12 bits selecting a byte within the 4 KB coming directly from the original address.

Bits [47:39] of the virtual address index into the 512 entry L0 table. Each of these table entries spans a 512 GB range and points to an L1 table. Within that 512 entry L1 table, bits [38:30] are used as index to select an entry and each entry points to either a 1 GB block or an L2 table.

Bits [29:21] index into a 512 entry L2 table and each entry points to a 2 MB block or next table level. At the last level, bits [20:12] index into a 512 entry L3 table and each entry points to a 4 KB block.

+--------+--------+--------+--------+--------+--------+--------+--------+
|63    56|55    48|47    40|39    32|31    24|23    16|15     8|7      0|
+--------+--------+--------+--------+--------+--------+--------+--------+
 |                 |         |         |         |         |
 |                 |         |         |         |         v
 |                 |         |         |         |   [11:0]  in-page offset
 |                 |         |         |         +-> [20:12] L3 index
 |                 |         |         +-----------> [29:21] L2 index
 |                 |         +---------------------> [38:30] L1 index
 |                 +-------------------------------> [47:39] L0 index
 +-------------------------------------------------> [63] TTBR0/1

Virtual memory attributes

When mapping memory, consider the cacheability:

• If cacheable == true, use seL4_ARCH_Default_VMAttributes
• If cacheable == false, use seL4_ARCH_Uncached_VMAttributes

Work tasks

• Add arm64 module with all of the respective architecture const's
• Add aarch64 specific translation and paging constructors
• Move architecture specific TCB manipulation into a module

References

• Translation tables in ARMv8-A
• ARMv8-A Address Translation
• Fundamentals of ARMv8-A

Summary

The VMM process will be self-hosted in the sense that it is managing its own memory. The main goal of this work is to separate the creation of a process from the use of that process's VSpace. In the existing process creation, ReadyProcess::new takes a mutable reference to the process's VSpace, this borrow prevents placing a VSpace into a child's process parameters.

This issue proposes a new type of process, one that is self-hosted.

Implementation Details

Logistics

in userland/process, the existing implementation becomes StandardProcess and a new process type, SelfHosted, is added to the module.

SelfHosted

~SelfHosted's constructor takes a stack addr for the child and the local region for stack setup:~

pub fn new<T: RetypeForSetup>(
    child_stack_addr: usize,
    cspace: LocalCap<ChildCNode>,
    parent_mapped_region: MappedMemoryRegion<StackPageCount, shared_status::Exclusive>,
    parent_cnode: &LocalCap<LocalCNode>,
    function_descriptor: extern "C" fn(T) -> (),
    process_parameter: SetupVer<T>,
    ipc_buffer_ut: LocalCap<Untyped<PageBits>>,
    tcb_ut: LocalCap<Untyped<<ThreadControlBlock as DirectRetype>::SizeBits>>,
    slots: LocalCNodeSlots<PrepareThreadCNodeSlots>,
    priority_authority: &LocalCap<ThreadPriorityAuthority>,
    fault_source: Option<crate::userland::FaultSource<role::Child>>,
) -> Result<Self, ProcessSetupError>;

~At its call site, the stack regions should already be configured:~

let (unmapped_stack_pages, _) =
    parent_mapped_region.share(page_slots, parent_cnode, CapRights::RW)?;
let mapped_stack_pages =
    vspace.map_shared_region_and_consume(unmapped_stack_pages, CapRights::RW)?;
let stack_pointer =
    mapped_stack_pages.vaddr() + mapped_stack_pages.size() - param_size_on_stack;

let params = SelfHostedParams { vspace };

// Now we setup the process _without_ using the vspace.
let proc = SelfHosted::new(
    stack_pointer,
    child_cnode,
    local_mapped_region,
    &cnode,
    child_main,
    params,
    ut,
    ut,
    slots,
    tpa,
    Some(fault_source),
)?;

See comment below for an update to this API.

ProcType (optional)

There's likely some code reuse both in the funneling into some overlap with standard process creation but also in the common behavior. Consider a

impl<P: ProcType> P {
     // Common things
}

solution to capture some of the overlap where SelfHosted and StandardProcess both implement ProcType.

... or make a different struct to do the same thing. We need to take a large device untyped and carve it up on demand to get a single page device untyped at a requested address.

A seL4 VCPU object enables a thread to perform instructions and operations as if it were running at a higher privilege level. Higher privilege levels typically have access to additional machine registers and other pieces of state, the VCPU object acts as storage for that state.

Note that the VCpuRegister variants are different for each architecture.

There is some opportunity to have distinct Bound and Unbound VCPU types, where the process of binding an unbound VCPU to a TCB yields a bound VCPU type.

We should wrap the underlying capability to expose these methods:

/// Bind a TCB to a virtual CPU.
///
/// When a TCB has a bound VCpu it is allowed to
/// have the mode field of the cpsr register set
/// to values other than user.
/// It is allowed to have any value other than hypervisor.
pub fn bind_tcb(&mut self, tcb: &mut LocalCap<ThreadControlBlock>) -> Result<(), SeL4Error>;

/// Inject an IRQ to a virtual CPU.
pub fn inject_irq(
        &mut self,
        virq: u16,
        priority: u8,
        group: u8,
        index: u8,
) -> Result<(), SeL4Error>;

/// Read a virtual CPU register.
pub fn read_register(&self, reg: VCpuRegister) -> Result<usize, SeL4Error>;

/// Write a virtual CPU register.
pub fn write_register(&mut self, reg: VCpuRegister, value: usize) -> Result<(), SeL4Error>;

The VMM will need to map specific regions into the IPA for the guest, so VSpace will need something akin to VSpace::map_region_at_addr:

pub fn map_region_at_addr<SizeBits: Unsigned>(
    &mut self,
    vaddr: Vaddr,
    region: UnmappedRegion<SizeBits>,
    rights: CapRights,
) -> Result<(), VSpaceError> {
    if self.overlaps_with_previously_mapped(vaddr) {
        return Err(VSpaceError::RegionOverlaps);
    } else {
        self.map_layer(...)
    }
}

Where VSpace::overlaps_with_previously_mapped uses a bit of new state added to VSpace:

// Maybe this comes from a configuration item in sel4.toml?
const NUM_SPECIFIC_REGIONS: usize = ...;

struct VSpace<VSS> {
    //....
    mapped_regions: [(Vaddr, Vaddr); NUM_SPECIFIC_REGIONS],
}

impl VSpace<...> {
    fn overlaps_with_previously_mapped(&self, vaddr: Vaddr) -> bool {
        for (head, size) in self.mapped_regions {
            if vaddr > head && vaddr < head + size {
                return true
            }
        }
        false
    }
}

Some caveats:

1. There is a performance cost here and map_region_at_specific_addr is in the fault-path for the VMM, the hottest part w.r.t. to meeting a guest's expectations on memory accesses. It is likely that we don't want to do the overlapping check on every call, but instead to elide it in our code altogether, allowing the map_region_at_specific_addr call to fail in the kernel, amortizing that cost.
2. We'll need to update the existing map_region functions to make use of the new state, as it is likely that the cost of letting the kernel tell us about an overlap, one page at a time, is in its worst case more than what could be reasonably amortized. Imagine failing through a region of a few hundred megabytes, or even a gigabyte, one page at a time.

This rolls up into https://github.com/auxoncorp/engineering-planning/issues/3 and is blocked by #9.

warning: unused `core::result::Result` that must be used
   --> ferros/src/userland/multi_consumer.rs:705:5
    |
705 |     consumer_vspace.skip_pages(1);
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(unused_must_use)]` on by default
    = note: this `Result` may be an `Err` variant, which should be handled

warning: unused `core::result::Result` that must be used
   --> ferros/src/userland/multi_consumer.rs:713:5
    |
713 |     consumer_vspace.skip_pages(1);
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: this `Result` may be an `Err` variant, which should be handled

We need to hand a lot, but not all, of the irqcontrol slots to the VMM process, but still maintain some of them for local device drivers (uart to talk to the control plane, for example)

In an aarch64 build, the child processes don't seem to be able to use their VSpaces. The access for the pc faults before the process even starts, and it also cannot dump its stack:

vm fault on code at address 0x44ae98 with status 0x82000006
in thread 0xff800fff2c00 "child of: 'rootserver'" at address 0x44ae98
With stack:
0x312000: INVALID
0x312008: INVALID
0x312010: INVALID
0x312018: INVALID
0x312020: INVALID
0x312028: INVALID
0x312030: INVALID
0x312038: INVALID
0x312040: INVALID
0x312048: INVALID
0x312050: INVALID
0x312058: INVALID
0x312060: INVALID
0x312068: INVALID
0x312070: INVALID
0x312078: INVALID

My best effort at translating what that status means (0x82000006) I gather from some arm documentation on the instruction fault status register:

b000110 access flag fault, page

This leads me to wonder if there are some broken details w/r/t rights? flags? settings for paging mapping when using aarch64.

Here's some information on the meaning of access flags: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0211k/Caceaije.html

However, I'm unsure what or how those tie into the use of CapRight in seL4.

The example system added in #87 currently does not run on real hardware yet, it requires additional configuration around IOMUXing, clocks and ENET phy initialization.

As of nightly 2020–07–15, cargo has its own feature for cross compiling the sysroot (see build-std) in a .cargo/config.toml

[unstable]
build-std = ["core", "compiler_builtins"]
build-std-features = ["compiler-builtins-mem"]

We no longer need to use cargo-xbuild to do this.

The implementation of Badge::are_all_overlapping_bits_set() should be updated to reflect the masking behavior it's used for, instead of returning true if any bits overlap.