Tock Application ID Implementation PoCs

README.md

Tock Application IDs implementation PoCs

This Gist contains two potential implementation methods for application IDs in the kernel.

While the variant using const_generics checks the return width of the application id byte-array at compile time, the variant using assoc_constants compiles on stable and is likely to be optimized in similar ways, since the AppId trait is never used dynamically and hence the compiler will know that the reference points to an underlying type of fixed length.

assoc_constants.rs

// The AppId trait, which must always return a fixed-size ID, although
// this cannot be guaranteed when using associated constants
//
// Most likely (because we're never operating on a dymaic reference and
// hence don't use vtables) the kernel will still know the underlying
// slice length and optimize accordingly
trait AppId {
    const LENGTH: usize;

    fn as_bytes<'a>(&'a self) -> &'a [u8];
    fn compressed(&self) -> [u8; 4];
}

// Process and Kernel are just types to show how the ID would be used
// and mock the target structure
struct Process<I: AppId> {
    app_id: I,
}
impl<I: AppId> Process<I> {
    fn new(id: I) -> Process<I> {
        Process { app_id: id }
    }

    fn id<'a>(&'a self) -> &'a I {
        &self.app_id
    }
}

struct Kernel<'a, I: 'a + AppId> {
    processes: &'a [Process<I>],
}
impl<'a, I: 'a + AppId> Kernel<'a, I> {
    fn init(processes: &'a [Process<I>]) -> Kernel<'a, I> {
        Kernel { processes }
    }

    fn compressed_ids(&self) -> impl Iterator<Item = [u8; 4]> + '_ {
        self.processes.iter().map(|p| p.id().compressed())
    }
}

// Just a dummy ID which is static, such that DefaultAppId can work
// without leaking memory
static DUMMY_APP_ID: [u8; 48] = [0; 48];

// TODO: This could optionally guarantee alignment
//
// It's probably not possible to guarantee alignment for all
// implementors of the AppId trait though
struct DefaultAppId(&'static [u8; 48]);
impl DefaultAppId {
    fn dummy() -> DefaultAppId {
        DefaultAppId(&DUMMY_APP_ID)
    }
}
impl AppId for DefaultAppId {
    const LENGTH: usize = 48;

    fn as_bytes<'a>(&'a self) -> &'a [u8] {
        self.0
    }

    // TODO: This should probably be a trucated hash instead
    fn compressed(&self) -> [u8; 4] {
        [self.0[0], self.0[1], self.0[2], self.0[3]]
    }
}

// Alternative appid implementation, storing the id in kernel RAM
// (dynamically generated at startup)
//
// This avoids having to dynamically allocate 'static memory regions
// for each process that should be loaded
struct SmallInRamAppId([u8; 4]);
impl AppId for SmallInRamAppId {
    // This would compile fine with LENGTH = 5, which is bad
    const LENGTH: usize = 4;

    fn as_bytes<'a>(&'a self) -> &'a [u8] {
        &self.0
    }

    fn compressed(&self) -> [u8; 4] {
        self.0
    }
}

// Show that everything works
fn main() {
    let processes = [Process::new(DefaultAppId::dummy())];
    let kernel = Kernel::init(&processes);

    for id in kernel.compressed_ids() {
        println!("Compressed App ID: {:?}", id);
    }
}

const_generics.rs

#![feature(const_generics)]

// The AppId trait, which is const-generic over the ID size and
// therefore can return fixed-size slices as part of its methods
trait AppId<const L: usize> {
    fn as_bytes<'a>(&'a self) -> &'a [u8; L];
    fn compressed(&self) -> [u8; 4];
}

// Process and Kernel are just types to show how the ID would be used
// and mock the target structure
struct Process<const L: usize, I: AppId<L>> {
    app_id: I,
}
impl<const L: usize, I: AppId<L>> Process<L, I> {
    fn new(id: I) -> Process<L, I> {
        Process { app_id: id }
    }

    fn id<'a>(&'a self) -> &'a I {
        &self.app_id
    }
}

struct Kernel<'a, const L: usize, I: 'a + AppId<L>> {
    processes: &'a [Process<L, I>],
}
impl<'a, const L: usize, I: 'a + AppId<L>> Kernel<'a, L, I> {
    fn init(processes: &'a [Process<L, I>]) -> Kernel<'a, L, I> {
        Kernel { processes }
    }

    fn compressed_ids(&self) -> impl Iterator<Item = [u8; 4]> + '_ {
        self.processes.iter().map(|p| p.id().compressed())
    }
}

// Just a dummy ID which is static, such that DefaultAppId can work
// without leaking memory
static DUMMY_APP_ID: [u8; 48] = [0; 48];

// TODO: This could optionally guarantee alignment
//
// It's probably not possible to guarantee alignment for all
// implementors of the AppId trait though
struct DefaultAppId(&'static [u8; 48]);
impl DefaultAppId {
    fn dummy() -> DefaultAppId {
        DefaultAppId(&DUMMY_APP_ID)
    }
}
impl AppId<48> for DefaultAppId {
    fn as_bytes<'a>(&'a self) -> &'a [u8; 48] {
        &self.0
    }

    // TODO: This should probably be a trucated hash instead
    fn compressed(&self) -> [u8; 4] {
        [self.0[0], self.0[1], self.0[2], self.0[3]]
    }
}

// Alternative appid implementation, storing the id in kernel RAM
// (dynamically generated at startup)
//
// This avoids having to dynamically allocate 'static memory regions
// for each process that should be loaded
struct SmallInRamAppId([u8; 4]);
impl AppId<4> for SmallInRamAppId {
    fn as_bytes<'a>(&'a self) -> &'a [u8; 4] {
        &self.0
    }

    fn compressed(&self) -> [u8; 4] {
        self.0
    }
}

// Show that everything works
fn main() {
    let processes = [Process::new(DefaultAppId::dummy())];
    let kernel = Kernel::init(&processes);

    for id in kernel.compressed_ids() {
        println!("Compressed App ID: {:?}", id);
    }
}