tock
RFC: Process Memory: move `driver_num` from grant pointers table to the allocated grant itself.
Currently, the top of a process's memory looks something like this:
// Mem. Addr.
// 0x0040000 ┌────────────────────────────────────
// │ DriverNumN [0x1]
// │ GrantPointerN [0x003FFC8]
// │ ...
// │ DriverNum1 [0x60000]
// │ GrantPointer1 [0x003FFC0]
// │ DriverNum0
// │ GrantPointer0 [0x0000000 (NULL)]
// ├────────────────────────────────────
// │ Pending Upcall Queue
// ├────────────────────────────────────
// │ Process Control Block
// 0x003FFE0 ├──────────────────────────────────── Grant Region ┐
// │ GrantDataN │
// 0x003FFC8 ├──────────────────────────────────── │
// │ GrantData1 ▼
// 0x003FF20 ├────────────────────────────────────
// │
// │ --unallocated--
// │
// └────────────────────────────────────
where an array of (GrantPointer, DriverNum) tuples are stored at the top of the process memory. The length of that array is equal to the number of created grants setup in main.rs.
On Hail, there are 14 grants, so that array unconditionally takes up 112 bytes. Because we need some mechanism to track where allocated grants actually exist, having the array of GrantPointers probably makes sense (56 bytes on Hail), and Tock has included that array since the beginning.
However, adding the DriverNum so we have a mapping of syscall driver number to grant number is a new addition. These 56 bytes are used whether or not the process ever actually uses each of the grants. We might want to consider whether we want to unconditionally use this memory for every process.
Alternative
Instead of including DriverNum in the grant pointer table, we could instead include it at the beginning of the allocated grant if the grant is ever allocated. The allocated grant would then look like:
// ┌────────────────────────────────────
// │ T (grant type)
// ├────────────────────────────────────
// │ Padding
// ├────────────────────────────────────
// │ ...
// │ SavedUpcall Table
// ├────────────────────────────────────
// │ Number of Upcalls
// ├────────────────────────────────────
// │ DriverNum
//@GrantPtr ->└────────────────────────────────────
This would then only use space to store DriverNum if the grant is actually allocated. This saves 4 bytes of process memory per grant created but never allocated.
Downside 1
Ok there is a reason this is an issue not a PR. Changing this would mean every subscribe() call would require an additional memory access.
Some rough psuedocode for what looking up the grant after a subscribe() would look like:
index = 0
while index < num_grants:
grant_ptr = *(start_of_grant_ptr_table + index)
if grant_ptr != NULL:
driver_num = *grant_ptr
if driver_num == subscribe.driver_num:
# Found matching grant
I'm not really convinced this is a huge deal.
Downside 2
There is a software engineering downside. Right now, the grant pointer table is completely "owned" by ProcessStandard, and it can directly implement process.lookup_grant_from_driver_num(). In this new approach, the driver num is stored in the allocated grant, which is under the purview of grant.rs. So, I'm not entirely sure what the code would look like for kernel.rs to access the correct grant number when a subscribe syscall occurs.
Related idea:
Move upcall queue to grant regions as well.
Currently we statically allocate 10 pending upcalls for each process. That takes up 360 bytes of RAM even if the process never requests an upcall, and it can overflow if the process has 11 pending upcalls. As far as I know the 10 number is arbitrary.
Instead, we could allocate upcall queue space with the allocated grants. I could imagine different implementations:
- Each stored upcall gets effectively a "pending" bit. Since the kernel already manages upcalls, it would just add more fields to the stored upcall slot in the allocated grant. Each UpcallId could only have one pending upcall.
- Each grant gets its own upcall queue. When the grant is allocated, the kernel also includes an upcall queue in the allocated space. The number of slots in the queue would be fixed, but could either be requested by the capsule, or a fixed amount, or based on the number of upcalls that capsule uses.
- The upcall queue could be its own region in the grant space, much like it is now, but would only be allocated once a grant is allocated. It could be re-allocated as more grants are allocated, to allow it to grow.
Downsides
There would be extra overhead when allocating grants. Upcalls may not be balanced among grant regions, and some capsules may have their upcalls fail even though there are other slots available in other grant regions.
- Each stored upcall gets effectively a "pending" bit. Since the kernel already manages upcalls, it would just add more fields to the stored upcall slot in the allocated grant. Each UpcallId could only have one pending upcall.
Just a note, some drivers, like touch that fires a lot of upcalls, might need to schedule several upcall instances of the same upcall.
