alloc: initial `TryBox` implementation

[00xc]

Introduce the alloc submodule and the TryBox type, a fork of the upstream alloc crate and Box type respectively. The new type behaves exactly like Box, except it only supports fallible allocations, meaning that users must always handle potential errors.

Users must also explicitly set the allocator to use. Using a specific allocator by default like the standard library does is complicated. The standard library uses whichever allocator is set as global (via the #[global_allocator] macro), which can be accessed via a global instance (alloc::alloc::Global). However, the global instance is gated behind an unstable feature, and the macro cannot be reimplemented because it is a compiler intrinsic. As a workaround, one may add new higher level types in the future which use a specific allocator by default.

The new TryBox does not support unsized types (e.g. [T] pr dyn Trait), since that requires unstable features. On the other hand, it has a few extra methods for convenience like try_default_in(), try_clone() and try_clone_in().

This PR also includes a new type, GlobalBox, which uses the global SVSM allocator (SvsmAllocator), and is meant to be used as a replacement for the regular Box type.

TODO:

• [X] Implement SvsmAlloc for SvsmAllocator
• [X] Implement GlobalBox, a wrapper which uses the SvsmAllocator transparently.
• [x] Replace Box uses with GlobalBox. NOTE: there is a single instance that cannot be replaced, see comment below.

TODO in future PRs:

• Introduce TryArc
• Introduce TryRc
• Introduce TryVec / RawVec
• Introduce TryString
• Introduce other collections (not used for now).

[00xc]

For review I suggest taking a look at the public API via make doc, and diffing against upstream alloc (library/alloc/ in upstream Rust).

[p4zuu]

Looks good to me at the moment. Just a few questions:

• Do you have a plan for easy maintenance in the future? Eg. easy update when upstream alloc gets updated
• Did you pull the boxed unit tests from upstream? Anyway, miri doesn't find issue with them :)

[joergroedel]

Thanks for working in this, I think it is going into the right direction.

I particularly like that the box only supports fallible allocations, forcing users to handle allocation errors. This might actually become a reason to not switch back to the standard library once these features become stable there.

A few things I noticed:

• The Allocator trait is defined in mod.rs, please move it to a separate file
• The name SvsmBox is too much tied to the SVSM. With the planned move to cargo workspaces this code will likely end up in its own crate. Maybe name it TryBox or CheckedBox or something like that? The SVSM can then use it to define its own types with different backend allocators (Suggestion: Maybe defining an allocator-specific type can be done via a macro)

[00xc]

Looks good to me at the moment. Just a few questions:

• Do you have a plan for easy maintenance in the future? Eg. easy update when upstream alloc gets updated

Not really, other than diffing I don't see much that can be done sadly. On the other hand, this code should not require heavy maintenance as we likely don't want many more features. One exception would be, as I mentioned in the PR description, the support for unsized types - when the required features are stabilized, we will likely want to add those.

• Did you pull the boxed unit tests from upstream? Anyway, miri doesn't find issue with them :)

No, I wrote those to ensure that everything worked as expected, as there are some slight syntax changes I had to perform to avoid nightly features. Upstream does have tests but most rely on parts of the Box type that we do not support. At some point I'll revisit them to ensure that we use as much tests from upstream as possible.

[00xc]

A few things I noticed:

• The Allocator trait is defined in mod.rs, please move it to a separate file

I simply placed in mod.rs everything that is not strictly pulled from upstream, which I think its not a bad practice in itself. Anyhow, I'll eventually move everything into a separate file and use mod.rs to replace upstream's lib.rs.

EDIT: technically I pulled the Allocator (i.e. SvsmAlloc) trait from the core library. I cannot import it normally because it is gated behind a nightly feature.

• The name SvsmBox is too much tied to the SVSM. With the planned move to cargo workspaces this code will likely end up in its own crate. Maybe name it TryBox or CheckedBox or something like that? The SVSM can then use it to define its own types with different backend allocators (Suggestion: Maybe defining an allocator-specific type can be done via a macro)

Yeah the name change makes sense, I'll add it to the next version of the PR. For default allocator types, I think we can even use typedefs (but I have not tested it). Something like:

static ALLOCATOR: SvsmAllocator = SvsmAllocator::new();
// ...
pub type GlobalBox<T> = TryBox<T, A = ALLOCATOR>;

[00xc]

• Renamed SvsmBox to TryBox
• Renamed SvsmUnique to Unique (private type)
• Renamed SvsmAlloc to Allocator.

[00xc]

static ALLOCATOR: SvsmAllocator = SvsmAllocator::new();
// ...
pub type GlobalBox<T> = TryBox<T, A = ALLOCATOR>;

Just verified that this does not really work. But we can do:

pub struct GlobalBox<T>(TryBox<T, &'static SvsmAllocator>);

impl<T> GlobalBox<T> {
    pub fn try_new(val: T) -> Result<Self, SvsmError> {
        let inner = TryBox::try_new_in(val, &ALLOCATOR)?;
        Ok(Self(inner))
    }
}

I'll add something like this to this PR soon.

[00xc]

There is currently an use of the old Box in the Mapping struct in the mm/vm/mapping code that cannot be replaced:

pub struct Mapping {
    mapping: RWLock<Box<dyn VirtualMapping>>,
}

This is because dyn VirtualMapping is unsized, and TryBox does not work with those, as it requires unstable features to implement that support. There are some potential reworks that could be done to the virtual mapping code to avoid using an unsized item, such as using enums instead of dynamic dispatch, but for the purposes of this PR I'll leave this Box use unchanged

[00xc]

There is currently an use of the old Box in the Mapping struct in the mm/vm/mapping code that cannot be replaced:

pub struct Mapping {
    mapping: RWLock<Box<dyn VirtualMapping>>,
}

This is because dyn VirtualMapping is unsized, and TryBox does not work with those, as it requires unstable features to implement that support.

I've been digging into this and we might actually be able to get it working for unsized types. The main issue to replace the use above (as far as I can tell) is that CoerceUnsized is unstable. This means that TryBox<T, A> cannot be transparently coerced into TryBox<dyn Trait, A>.

To solve this, I've come up with a macro that will do this for us. With regular coercion, we could simply do:

trait MyTrait {}
impl MyTrait for usize {}

let boxed = Box::new(5usize);
let dynamic: Box<dyn MyTrait> = boxed;

But we need to do:

trait MyTrait {}
impl MyTrait for usize {}

let boxed = TryBox::try_new_in(5usize, Allocator)?;
let dynamic = trybox_upcast!(boxed, MyTrait);

[00xc]

• Unsized types now work.
• Replaced the last remaining use of Box with GlobalBox.
• Rebased on top of the workspace changes.

[00xc]

Added a new test and rebased on main.

[00xc]

Rebased on main and fixed conflicts