slab-alloc: Create mechanism for supporting time in no-std and no-os

[joshlf]

Currently, in util::workingset, we use std::time::Instant to keep track of time. Instead, we need some mechanism (probably a trait) for keeping track of time that is agnostic to implementation, an implementation of this mechanism for a no-std environment (where OS support is present), and a mechanism for allowing the user to provide their own implementation for no-os environments.

Progress:

• [ ] Create a mechanism for abstracting over time, create an implementation of this mechanism that is backed by std::time::Instant, and update util::workingset to use this mechanism.
• [ ] Create an implementation of this mechanism that does not rely on std, but only on OS-provided functionality (e.g., libc on Unix and kernel32 on Windows).
• [ ] Modify the slab allocator code to allow the user to provide their own implementation of this mechanism.

[shivanth]

I would like to take a shot at this..

[joshlf]

Sure thing! I'm happy to mentor, so let me know if you have any questions, want to discuss approaches/designs, etc.

[shivanth]

Here's what I'm thinking. Let's extract two, and only two, functions

fn refresh(&mut self, secs: u64) -> Option<T> 
fn refresh_now(&mut self, secs: u64, now: U) -> Option<T> 

into a trait. Then the current WorkingSet can be changed into an impl for this new trait with minimum effort. A user implemented mechanism will implement this trait , taking a type U instead of std::time::Instant and implement its own logic.

[joshlf]

So I've actually been thinking about getting rid of the WorkingSet entirely since it's only used in one place (I was originally planning on using it in a magazine caching implementation that didn't end up getting included). Given that, it might be easier to make a Time trait instead.

There are multiple designs for it, but my guess is that at a minimum it'd have a function fn now() -> Self. I could see a couple of possible designs:

• fn diff(&self, other: Self) -> std::time::Duration
• fn secs_since(&self, other: Self) -> u32
• fn secs_elapsed(&self, other: Self, secs: u32) -> bool

How do you feel about that approach? If you take a look at the WorkingSet implementation and where we use it, you'll see that it's somewhat more convoluted and ugly than it needs to be. I think that getting rid of it would make the code simpler and cleaner. I'm happy to hear other opinions though!

[shivanth]

Sounds Good. Looks like secs_elapsed can have a default implementation based on secs_since. + You still have dependency on std::time::Duration for the diff function 😄 . If only we could do everything in u32 ...

[joshlf]

Hey, so @ezrosent and I discussed this last night, and he had an interesting idea - curious what you think of it. It'd be nice to be able to have the notion of "time" be pretty abstract so it can include things like CPU cycle counters (which would make it easy for us to implement a no-std version without the user needing to provide their own mechanism to query for the current time). However, this makes the duration type opaque, but that's probably fine. It just means that if you want to supply a concrete duration, you need to know the specific concrete type that's being used for Time. It'd make that trait look something like this:

pub trait Time {
    type Duration: Ord;

    fn now() -> Self;
    fn since(&self, other: Self) -> Self::Duration;
}

If you had a concrete type, say with Duration = u32, representing a cycle count, then you could still construct a constant out of it. So you could still have code configure what the period of the working set algorithm is, for example.

Upside: gets rid of the dependency on std::time::Duration.

[ezrosent]

+1 I was thinking that it doesn't even have to be a cycle count. The slab allocator could itself implement this trait. (Or a small struct containing allocation statistics). It would of course change the semantics of the working set algorithm, but it could be accommodated by a trait along the lines of the one proposed above.