Bellyflop OS Report

Our implementation also trivially allowed us to implement partial frees. Since these are just another retype of the handed out capability, they will be accepted by the interface and the memory region will be freed.

However, trying to free a ram capability that has already been partially freed will result in an error, specifically LIB_ERR_FREE_LIST_DOUBLE_FREE. The following code snippet shows how to recreate this failure:

struct capref cap, split_cap;
...
mm_alloc(mm, total_size, &cap);
cap_retype(split_cap, cap, 0, ObjType_RAM, total_size / 2, 1);

mm_free(mm, split_cap);
// This call will result in a double free.
err = mm_free(mm, cap);

Instead, the user should retype the cap again to obtain a capability for the other half and free that.

To allow concurrent access to the memory manager all operations must first obtain a lock. This is needed since our memory server runs on a separate thread in the init domain. This means that memory allocations might happen concurrently.

Since the memory server needs to be able to fulfill nested allocation requests, the lock needs to be re-entrant.

The challenges of providing Memory Allocation as an RPC service are discussed in detail in section 6.2.

The memory manager will begin refilling the slab allocator for the region nodes when there are two or less blocks available. It will refill the free sections list slab allocator if there are at most free 32 blocks left. While there is no strict reasoning behind the choice of these numbers, there is at least some thought behind it:

For the region slab allocator it would technically be sufficient to refill it when there is just one block left. These nodes are only allocated when adding new memory regions. So when the last spot would be filled up, the memory allocator could use the memory in that region to refill this slab allocator. We chose to be slightly more conservative and refill when there are two blocks left.

The free section list slab allocator needs to be refilled sooner, since allocating memory can lead to the creation of new nodes as described earlier. We again choose a conservative number and refill at 32 free blocks.

We realized that mapping of large regions (which can not be mapped as Superpages) was very slow because we were mapping every single page as one mapping. We changed this by mapping as many pages combined as possible at the L3 Page table level (which is up to 512 pages). See 3.4 for results of this. Now there are a lot of empty slots in the L3 Child Mapping Caps array. The space for this could be optimized away by finding a more compact memory representation. We did not look into this.

To manage the state introduced by allowing lazy mapped regions, we introduce two data structures:

• •

  Used list: Used to identify the region type of region.

• •

  Mem Cap Store: To store and manage memory capabilities; needed to lazily map pages.

Allocating a lazily mapped region is now very simple. We first "allocate" a virtual address space by calling paging_alloc. And then add the virtual address region to the used list.

Whenever a page fault occurs, the page fault handler checks if the address was lazily mapped by checking the used list for lazily mapped regions and then starts the process of mapping the requested page. To do this, we do the following:

struct cap_list_header* cap_list;
cap_store_get_active(&st->lazy_mem_cap_store, base, &cap_list);
if (capref_is_null(cap_list->active_cap)) {
    err = frame_alloc(&frame, LAZY_MAP_CAP_SIZE, NULL);
    cap_list->active_cap = frame;
    cap_list->offset = 0;
}
paging_map_fixed_attr_internal(..., cap_list->active_cap, cap_list->offset,
                               BASE_PAGE_SIZE, ...);
cap_list->offset += BASE_PAGE_SIZE;
if(cap_list->offset == LAZY_MAP_CAP_SIZE){
    push_back_active(&st->lazy_mem_cap_store, cap_list);
}

This code tries to get the active memory capability. If it does not exist, it creates one of size LAZY_MAP_CAP_SIZE and sets it to be the active one. Then we map the page to the active capability at the provided offset. This means that in every step we carve out memory of the size of one page out of the active capability. In the end, we check if all memory of the capability has been mapped already and if so, we push back the active capability to become non-active.

Umapping a lazy mapped region works by just calling the normal unmap function. It checks if the region was lazily mapped and finds the region size. We then iterate over our page table data structure in this region and unmap every mapping that we find (which could in theory be none). We also remove the region from the used list and tell the cap store to release all the Memory Capabilities used for this lazy mapping.

Since the stack is malloced and mapped lazily with a big region, this implicitly makes the stack dynamically grow with actual memory. To detect stack overflows the region type of the region is the important part here, we basically only differentiate between Stack Memory and Not Stack Memory. When allocating the stack for a thread, we specify the region type to be REGION_TYPE_STACK. In order to now identify stack overflows, we add the following code to the page fault handler:

if (region_type == REGION_TYPE_STACK) {
    if ((lvaddr_t)requested_addr < region_base + BASE_PAGE_SIZE) {
        // We hit the guard page of the stack.
        USER_PANIC("Stack overflow detected!\n");
    }
}

This checks if are hitting the last page of the stack which acts as a "guard page" to detect stack overflows. This obviously does not work if the stack get directly overshoot by more than one page.

It is critical for the system to issue out unique domain identifiers as this functionality is needed for commands such as ‘ps’. In order to address this need we dedicated the top 8 bits of a domain identifier to the core number and the bottom 24 bits to a core level identifier which we incremented with each spawned domain. This is explain also in more detail in subsection 11.1.3.

In order to keep track of any spawned domains, we issue each kernel’s ‘init’ domain with a data structure called the ‘spawnstore‘. This is treated as a single source of truth regarding the status of active processes spawned by the relevant ‘init’ domain. Please note that that the ‘spawnstore’ does not care for domains spawned by ‘init’ domains in other cores. This obviously presents a challenge when querying for all the domains in the entire system, but we resolved this by simply querying every core’s ‘init’ process and then accumulating the results.

In order to keep the ‘spawnstore’ accurate, it becomes critical to ensure that we can “hook” into the exit event of any given process and notify the ‘spawnstore’. This was fairly trivial to attempt as we were able to simply overwrite the existing libc_exit call to inform the ‘spawnstore’ that our domain has just died. Here, we simply issued a InitProcessInformDeathRequest RPC call to the ‘init’ process. The exiting domain then spins while awaiting the ‘init’ process to first remove the domain from the ‘spawnstore’ and then remove it from the scheduler.

One of the first things that happen when spawning a process is that we setup the child’s capability space, as this is critical for the child process to do almost anything. The task of setting up the CSpace itself is fairly trivial, thanks to the various helper functions. However, figuring out how the capability space worked was challenging. It was essential to set up the L1_CNODE in the child process as it was necessary for a few other “child” capabilities to also be setup as well as for having a capability space where newly allocated capabilities could be stored in. In the case that we did not do this, the child domain would not have been able to allocate memory as in order to allocate memory there must be a valid ‘CSpace’ and to create a valid ‘CSpace’ there must be some memory. After creating an L1_CNODE along with an L2_CNODE, we now can map in the various critical capabilities into the child process. The child expects capabilities for LMP, the dispatcher, command line arguments and quite a few other capabilities.

In accordance with the ‘self-paging’ technique deployed in Barrelfish, the child process also needed the relevant information to enable ‘self-paging’ in its address space. This means that we need to pass in a root page table so that the child can continue to map in relevant page tables. This is achieved through mapping in a capability of type ObjType_VNode_AARCH64_l0 into the child process. The reason the ‘init’ domain needs to perform this action is due to the fact that the child is not capable of creating a new capability since it cannot map the associated memory region. It ultimately creates a dependency loop like in the above case with the capability nodes.

The initial process of ELF loading, is to look up the memory region of a corresponding binary file. This was done through the multiboot_find_module function which iterated through the existing modules and to obtain the module that matched the name of the requested module. Loading the ELF file after this, is mostly as simple as calling the elf_load function. This mapped the ELF segments to both the parent and the child domains, as a result of this it was also important to unmap each segment after the ELF binary was completely loaded. The function signature of the ELF setup is as follows, note the second argument as it is important for later.

static errval_t setup_load_elf(struct spawninfo *si, void **got_base_in_child_vspace)

One of the last steps performed when spawning a new domain is to setup the dispatcher. This process involves allocating a frame for a dispatcher capability and then mapping it over in the child’s capability space at the TASKCN_SLOT_DISPFRAME slot. Note the function signature for ELF loading from section 4.2.3 , we use the ‘got_base_in_child_vspace’ (or at least the pointer used here) and update the dispatcher data structure to reflect the location of the ‘.got’ section of the ELF file.

Like most other operating systems, we allow our modules to be spawned in with some arguments, in order to support this functionality we had to map in a new capability to the child in a specific slot in it’s capability space. This capability for the argument space was simply just 4096 bytes. However this was enough for our use case. We also map this capability to our virtual address space, this was done so that we can simply iterate over the arguments and write them to memory.

There are certain domains that may require spawning with additional capabilities attached. It would be irresponsible to hand these out for every spawned process, therefore we implemented the capacity to map in up to 3 capabilities as “Capability Arguments”. These “Capability Arguments” are mapped into a reserved area of the capability space. This feature was needed for the user level UART driver used to implement the shell as it required not just the UART device capability but also the GIC device capability. Please note that there is an expectation from the spawned domain that certain capabilities are in certain regions of the capability space, from here the user level process typically just maps these devices into its virtual address space. The interface for spawning with capability arguments now reflects the following function signature as a result.

errval_t spawn_load_argv_argcn(int argc, char *argv[], struct spawninfo *si,
                               domainid_t *pid, struct capref argcn0,
                               struct capref argcn1, struct capref argcn2)

While the function signature expects exactly 3 capability arguments, it is still possible to send less by simply sending a NULL_CAP. This capability is detected when setting up the capability space and then the process of mapping it into the child’s capability space is avoided.

To pass a paging state to the child, we do the following on a high level: We copy all the paging state into a new continuous memory area and fix all pointers to be relative to the start of this region. In the child process, we then walk through the paging state again and fix the relative addresses to its virtual memory address.

To do this we implemented the module Paging State Rebase, which implements the following interface:

size_t rebase_get_page_table_storage_size(struct page_table *pt);
errval_t rebase_to_relative_frame(struct paging_state *pst, void *buf, size_t buf_size,
                                  struct slot_allocator *slot_alloc);
void reconstruct_page_table(struct page_table *pt)

The tricky part here is to allocate enough space to fit the paging state in. rebase_get_page_table_storage_size() only gives the current storage size of the shadow paging table. But the moment we map a new area of memory (the place to put the serialized version of the shadow page table), we might change the storage size of the shadow page table again. We came up with this sophisticated schema that tries to calculate the number of possibly additional storage pages needed for adding the memory region. We do realize that this should be an iterative process trying to find a stable point, but this works for us. Apparently the *= 2 is generous enough:

size_t extra_ptables
        = num_pages / PTABLE_ENTRIES + num_pages / (PTABLE_ENTRIES * PTABLE_ENTRIES)
          + num_pages / (PTABLE_ENTRIES * PTABLE_ENTRIES * PTABLE_ENTRIES) + 3;
extra_ptables *= 2;

This tries to calculate for the worst case scenario where we walk over a page table boundary at every level. The rest of the implementation fixing pointers is then fairly simple.

We have to communicate with every core’s ‘init’ domain to get the system wide process information. This means that each core will get it’s request at slightly different times. This means that it is possible for a set of entries (let’s say the replies from core 0) to not reflect what it’s values would have been, by the time another set of entries arrived (for example on core 3). We could potentially solve this through some synchronization for these specific requests but we chose not to, as it is unlikely that the impact of this issue would be big enough to be of concern.

The space allocated for the arguments is simply 4096 bytes, it is fairly obvious as to why this is a limitation, we simply cannot use anything more than this figure. However, given our time limitations along with the fact that every argument our shell supports will sit comfortably within this limitation, it simply did not make sense to care about this.

Each LMP message is send with a set of flags. The interesting ones are:

• •

  LMP_FLAG_SYNC: Yield to target after successful transfer.

• •

  LMP_FLAG_YIELD: Yield to target if the message is undeliverable.

The naming of the flags is a bit unfortunate. We used LMP_SEND_FLAGS_DEFAULT (containing both SYNC and YIELD) for the majority of the course. However, this means that for big messages that are split into many smaller LMP messages, there’s a preemption after each successful message due to the SYNC flag.

In a similar spirit, for big messages it turned out crucial to increase the default LMP buffer size (DEFAULT_LMP_BUF_WORDS) which is equal to $2$ LMP messages. This means that there needs to be a preemption after every two messages. This is probably enough when using a different approach for sending big messages. However, given that we simply split big message into smaller ones, a small buffer meant a significant performance hit.

Figure 6.2 shows our benchmarks of SYNC and BUF (buffer) optimizations. The plot on the left shows that the optimizations do not affect small messages which fit into a single LMP message. This is expected since in all three experiments there is a preemption after the single LMP message is sent. However, the difference for bigger messages, 100B or 4 LMP messages in our case, is in orders of magnitude. Truth be told, while it is clear that many preemptions can be saved by these optimizations, we did not dig deeper into why is the difference so big (note that the y-axis is log scale).

We also performed an RTT benchmark with different sizes using SYNC and buffer optimizations. The Figure 6.3 shows very poor scaling of the implementation with SYNC and buffer optimizations. Sending 8KiB message takes 6 seconds. We attribute this to the big number of context switches that need to happen if the message is bigger than endpoints’ buffers.

Concretely, we set the buffer size to 10 messages ($10\cdot 32=320B$) and observe no slowdown for messages of smaller sizes than $320B$. The degradation starts with the 512B message.

When a big message is send, the receiver gets scheduled after the sender fills the buffer. Once the receiver reads the buffer, it just actively polls, waiting for new data. This can be trivially optimized by yielding to the sender when there’s no data to receive:

errval_t recv_single_lmp_msg_blocking(struct lmp_chan *chan,
                                      struct lmp_recv_msg *rcvbuf,
                                      struct capref *capref)
{
    // The yield-in-blocking-RECV optimization.
    while(!lmp_chan_can_recv(chan)) {
        thread_yield_dispatcher(chan->remote_cap);
    }

    errval_t err;
    do {
        err = lmp_chan_recv(chan, rcvbuf, capref);
    } while (err == LIB_ERR_NO_LMP_MSG);
}

With this optimization, we were able to get another 1000x speedup for big messages. Note that compared to the previous figure, the y-axis below is in microseconds. There is a noticeable jump in the graph for messages bigger than 2048. We did not dig deeper into this. Our guess is that the scheduler preempts to a different domain.

Hindsight. We ended up satisfied with the API we chose and the performance we obtained for the arbitrary-sized messages over LMP. We decided to not optimize further the big messages (by e.g., sending over frames) because it did not show up as a bottleneck while working on the project.

It is a bit sad that as we’ll see in the RPC section we ran into a bug which caused all RPC calls to take around 80ms. We were not able to resolve this bug and therefore our optimized LMP layer did not come to full fruition.

In the beginning, we used acks for every LMP package, then got rid of it by only acking the whole message. And then realizing that this is only needed for caps, and then realizing that there is the error SYS_ERR_LMP_CAPTRANSFER_DST_SLOT_OCCUPIED so we got rid of all the acks in the LMP protocol.

We support limiting the amount of memory a domain can get from the Memory server. The amount is controlled by a global define DEFAULT_MEMORY_QUOTA_B and defaults to 128MiB. Each memory capability returned to a domain is stored in the respective struct spawninfo of the domain. This way, we can clean up all memory that a domain requested once it exists.

Cleaning up the resources is not so straightforward, though, as for example memory frame’s might be shared across multiple domains. We don’t clean up the memory right now since nobody implemented the Capability project.

The ring-buffer operates in two different modes, one is a ‘write’ mode where the ring-buffer is used to relay information to another domain. In this mode of operation, writes occur by simply waiting for the status segment to be BUFFER_WAITING, this value indicates that the other domain is now waiting for input and therefore we can now write to the associated data segment of that specific cache line. For example, if we refer to figure 7.1 we can see the writer in the process of filing up the data slots for the second cache line, after this has happened the status segment of the second cache line will be set to BUFFER_READY and therefore will be available for the reading domain to read from.

As mentioned previously, the ring-buffer operates in two different modes, the ‘read’ mode is how a domain is able to receive a message from another domain. Here, we simply wait till our status segment is set to BUFFER_READY, this value indicates that the writing domain has a cache line worth of information ready to be consumed by the reading domain. In this case, we read these values into a buffer and update the status segment to BUFFER_WAITING, which will allow the writer to reuse this memory again.

One problem with how the ring-buffers work on ARM processors is that the ARM processors implement quite a weak form of memory consistency, in order to address this issue we had to add barriers before reading the status segments and barriers again before updating status registers. The barriers before the reading helped ensure that all memory was up to date and the barrier before updating ensured that all the read/write operations had propagated before the status was set.

The Figure 7.4 shows RTT scaling of our implementation of messages over UMP. First, it’s important to notice that for small messages the difference to LMP is small (16B over LMP takes 26$\mu$s and over UMP 17$\mu$s¹¹1These numbers should be taken with a grain of salt because we just took an average of many runs so we don’t know how the distribution looks.). However, for big messages, UMP scales much better. We attribute this to the fact that since the communication is cross-core, the reader and writer can process data in parallel and no context switches are needed as opposed to the LMP.

Hindsight. Similarly to the implementation of arbitrary-sized messaged over LMP, we ended up quite satisfied with our UMP channels. But again, they didn’t get to be fully appreciated because the RPC layer was our bottleneck by far. It would definitely be interesting to add a new "non-greedy" version of the UMP channels facilitating IPIs to see how big would be the performance hit.

Our problem with marshalling would actually never exist if we just had to support types with memory requirements known at compilation time like ints. We would just create a struct containing the request parameters, interpret it as bytes, send the bytes over, and interpret the bytes on the other side as the struct again. However, this solution breaks with types like strings or more generally arrays which might have unknown memory requirements at compilation time.

struct ProcessSpawnRequest {
    coreid_t coreid;
    char *cmdline;
};

The example above illustrates this issue. The char *cmdline is just a pointer instead of actual bytes of the string inside of the struct ProcessSpawnRequest.

Here is the final interface we use that did not require changes in the protobuf-c autogeneration:

enum RpcMethod {
  PROCESS_SPAWN = 0;

  // DO NOT CHANGE: Setting up LMP channels depends on this value being 9.
  SEND_LOCAL_LMP_EP = 9;
}

// ProcessSpawnRequest and ProcessSpawnResponse omitted.

message RpcRequestWrap {
  oneof data {
    ProcessSpawnRequest process_spawn = 2;
  }
}

message RpcResponseWrap {
  uint64 err = 1;

  oneof data {
    ProcessSpawnResponse process_spawn = 2;
  }
}

message RpcMessage {
  RpcMethod method = 1;

  oneof direction {
    RpcRequestWrap request = 2;
    RpcResponseWrap response = 3;
  }
}

"On the wire" we always send around the RpcMessage so that we always know which message type to deserialize the received bytes into. The RpcRequestWrap and RpcResponseWrap are used on the client-side as follows:

// Calls an RPC ‘method‘ with ‘request‘ payload and ‘request_cap‘ capability. Receives the
// response payload in callee-allocated ‘response‘ and response capability in ‘response_cap‘.
// In case of an error (remote or local), returns the corresponding error code.
errval_t aos_rpc_call(struct aos_rpc *rpc, RpcMethod method, RpcRequestWrap *request,
                      struct capref request_cap, RpcResponseWrap **response,
                      struct capref *response_cap);

errval_t aos_rpc_process_spawn(struct aos_rpc *rpc, char *cmdline, coreid_t core,
                               domainid_t *newpid) {
    ProcessSpawnRequest req = PROCESS_SPAWN_REQUEST__INIT;
    req.core = core;
    req.cmdline = cmdline;
    // A macro that creates RpcRequestWrap with the ‘req‘. The lowercase "init_process_spawn"
    // and uppercase "INIT_PROCESS_SPAWN" are needed for the field names in the macro.
    REQUEST_WRAP(req_wrap, init_process_spawn, INIT_PROCESS_SPAWN, &req);

    RpcResponseWrap *res_wrap = NULL;
    aos_rpc_call(rpc, RPC_METHOD__PROCESS_SPAWN, &req_wrap, NULL_CAP,
                       &res_wrap, NULL);

    *newpid = res_wrap->process_spawn->pid;
    // Destroy the callee-allocated response payload.
    RESPONSE_WRAP_DESTROY(res_wrap);

    return SYS_ERR_OK;
}

The interface is far from the ideal shown before, but it’s okay to justify the fact that now we can send requests and responses containing almost arbitrary data (ints, strings, arrays, nested proto messages, arrays of nested proto messages, you name it!).

Under the hood, the aos_rpc_call() puts the request into RpcMessage with the corresponding method and sends this serialized to the other endpoint. Then it receives a response RpcMessage, deserializes it and takes out the RpcResponseWrap to return it to the sender.

What remains is to discuss how this is handled on the server side. There’s not much magic to it – the global handler registered with the waitset takes out the RpcRequestWrap from the received RpcMessage, preallocates a response and calls the user-provided handler. The handler fills the response which is then put into RpcMessage and send to the caller.

The Protobuf layer currently incurs two memory copies when receiving: one to receive data from the underlying channel (LMP/UMP) and another to deserialize the data. Analogously for sending.

This can be brought down to just a single memory copy – when copying data to and from the underlying channel. The Protobuf-c has support for this, but since our bottleneck ended up being the 80ms bug, we didn’t implement this optimization.

Hindsight. Overall, we think it was a good idea to overengineer the RPCs a little. The API turned out okayish, causing occasional headaches, but concise enough for most cases. Compared to the initial design which required writing glue code ourselves, we went from trusting some ("battletest") glue codes to trusting all of them because they were generated.

The biggest takeaway though is to benchmark early. We only discovered the 80ms bug three days before the deadline. And sadly, we were not able to identify the root cause in time despite putting in decent hours.

For the user space UART to work, the terminal service expects a device capability to the UART device being mapped into one of the argument capability slots. We use the map_device_register function along with the relevant memory location data to map the device frame into our virtual address space. From here it is as simple as calling the lpuart_init function to initialise the driver.

Unfortunately, despite correctly (at least seemingly) configuring the GIC and the user space UART, we were unable to receive interrupts. In order to address this, we had to re-evaluate how input would work, the solution we eventually ended up going with was to simply read in a busy loop for input. While this did solve our problem, it did unfortunately introduce a large performance penalty.

Multiplexing output was quite trivial due to how we implemented the printf functionality. Whenever we received a whole string, we simply printed that out. This does mean that it is possible for a foreground domain to mangle output, however this is a user level error. Multiplexing input was however much harder. We achieved this through locks as described in the session management section 9.1.3.

Given the nature of Barellfish and its existing capability system, it does make sense to have a capability type for the serial input/output interface. This not only makes sense from an ergonomic perspective but may help deter the current existing attack vectors. For example, currently a process is capable of faking it’s pid in the request to the terminal service. This is obviously not the desired behaviour. Unfortunately, due to the complexity of the capability system we did not want to explore how to implement such a capability since we had other time pressing issues.

The consequence of having the lock on the serial interface means that a single process can hold onto the interface for an extended period of time. Unfortunately there are no solutions here to multiplex this better outright. The various other solutions require tradeoffs and we decided that the tradeoff offered via this central locking scheme was more attractive than other multiplexing methods, for example such as a newline character for example.

The provided driver only exposes an interface for transferring single blocks between the device and a physical memory location. Using this interface directly is clumsy which is why we create a wrapper around it. This wrapper provides functions for reading and writing multiple blocks and just parts of blocks to either physical or virtual addresses:

errval_t read_from_sd_offset(struct sd_wrapper *sd, void *dst, uint32_t sector,
                                uint32_t offset, uint32_t size);
errval_t write_to_sd_offset(struct sd_wrapper *sd, uint32_t sector,
                                uint32_t offset, const void *src, uint32_t size);

errval_t read_from_sd_to_paddr(struct sd_wrapper *sd, lpaddr_t paddr,
                                uint32_t sector, uint32_t size);
errval_t write_to_sd_from_paddr(struct sd_wrapper *sd, lpaddr_t paddr,
                                uint32_t sector, uint32_t size);

The first two functions allow reading and writing data of arbitrary sizes at any offset withing a block.

We will use the terms sector and block interchangeably. For both we assume 512 bytes.

When using read_from_sd_offset(), the block driver writes to an internal buffer. The desired chunks are then copied over to the buffer provided by the user. Writing works analogously.

The latter two calls do not buffer and thus require less copying. This results in them being slightly more restrictive, as they do not allow an offset and the size parameter has to be a multiple of the block size.

Our FAT32 provides the functionality to lookup, create, read, and modify both files and directories. It exposes the following API:

// Create and Delete Files or Directories.
errval_t fat32_create_file(struct fat32_file_system *fat, struct dir_entry *parent,
                            char *name, uint8_t attr, struct dir_entry *ret);
errval_t fat32_delete_file(struct fat32_file_system *fat, struct dir_entry *parent,
                            struct dir_entry *dir_entry);

// Read / Write / Append files.
errval_t fat32_read(struct fat32_file_system *fat, struct dir_entry *dir_entry,
                            void *buf, size_t pos, size_t bytes, size_t *ret_bytes);
errval_t fat32_write(struct fat32_file_system *fat, struct dir_entry *dir_entry,
                            void *buf, size_t pos, size_t bytes, size_t *ret_bytes);

// Uses read_from_sd_to_paddr to directly read the entire file into a frame.
errval_t fat32_readfile_to_frame(struct fat32_file_system *fat, struct dir_entry *dir_entry,
                                struct capref frame, size_t *ret_bytes);
// Truncate a file.
errval_t fat32_trunc(struct fat32_file_system *fat, struct dir_entry *dir_entry, size_t bytes);

// Find a file or directory by path.
errval_t fat32_resolve_path(struct fat32_file_system *fat, const char *path,
                            struct dir_entry *result);
// Find a file or directory in parent by name.
errval_t fat32_find_dirent(struct fat32_file_system *fat, struct dir_entry *parent,
                            char *filename, struct dir_entry *res);


// Finds the position and name of the next non-empty directory entry in parent after the given offset.
// Return FS_ERR_INDEX_BOUNDS if the end of the directory is reached.
errval_t read_next_dir_after_offset(struct fat32_file_system *fat, struct dir_entry *parent,
                                    uint64_t offset, char **ret_name, uint64_t *ret_idx);

Files and directories are represented as dir_entry structures which contain a copy of the FAT32 directory entry as well as the position of the directory entry on the disk. In general, files and directories are treated interchangeably. They can be distinguished by the directory bit in the attribute entry.

Not all operations are allowed on both directory entry types and will return FS_ERR_NOTFILE or FS_ERR_NOTDIR as appropriate. In general, lookup (find/resolve), creation, and deletion are defined for both. Reading, writing, and truncating are only allowed on files. To iterate through directories, we provide read_next_dir_after_offset.

Note that the create function will not check if a file or directory with that name already exists. This must be checked by the caller beforehand.

Delete will only remove directories if they are empty. We do not provide a direct interface to recursively delete a directory, since the function would have to check if files are still being used. This is out of scope for this layer (In fact, this is completely left up to the end user of the library).

This layer notably provides an offset based layer. Streaming functionality must be implemented on top. Unfortunately, this means that, for every operation, files have to be traversed from the beginning until the specified offset is reached. We made this choice to reduce the amount of state that has to be kept by the filesystem server. A streaming API would require the server to keep track of the position in the file for every user that opens it. Keeping in line with the design of Barrelfish, we instead outsource this responsibility to the user.

This design means that fast access to the file allocation table is critical. We achieve this using a fat cache.

The filesystem server exposes file operations using an RPC interface. It exposed interface can be found through the nameservice by looking up "FS/<mountpoint>". Since we only provide the filesystem for the SD card, we set this to be "FS/sdcard".

This allows multiple filesystems to be mounted as a sort of VFS. This is currently, however, not supported by the client side library.

The filesystem exposes the following RPC calls:

FS_OPEN                 // (path, flags) -> fd, size
FS_CREATE               // (path, flags, is_dir) -> fd
FS_CLOSE                // (fd) -> void
FS_READ                 // (fd, offset, size) -> data
FS_WRITE                // (fd, data, offset) -> size
FS_TRUNC                // (fd, size)
FS_OPENDIR              // (path) -> fd
FS_READNEXTDIR          // (fd, pos) -> filename
FS_DELETE               // (path) -> void       - Used for file & dirs
FS_READFILE_TO_FRAME    // (fd, frame_cap) -> size

Like the FAT32 library that backs these RPC calls, the position in the file is specified using offsets from the beginning of the file.

As the central point for file access to the mounted device, the server must ensure that two invariants are upheld. Firstly, there must never be more then one simultaneous read issued to the underlying block device. Secondly, write access to a file must always be exclusive while read accesses may overlap. These are needed to guarantee the consistency of the filesystem.

The first invariant is trivially upheld, since the server handles all incoming requests sequentially in a single "event handler loop".

To ensure the second invariant, the server tracks which files are opened and with which permissions. For a client, trying to open a file, this means the following: If the client wants to open the file with write permissions, it is only granted access if the file is not currently opened. If the client wants to read the file, the file must not already be opened with write permissions. Note, that the server does not keep track which processes have opened files or where in the file they are.

There can be multiple readers at a time, the server keeps track of the number of readers accessing it, so it knows when the file is not being accessed anymore. The following snippet shows the just described handle kept by the server:

struct file_handle {
    char *path;
    struct dir_entry dir_entry;
    uint32_t num_accessors;
    bool has_writer;
};

struct server_state {
    bool up;
    struct fat32_file_system fat;
    collections_hash_table *open_files;  // A hash table of FD -> file_handle
};

The client side library forms the glue between the general libc library and the RPC filesystem server.

Upon initialization the client library will establish a connection to the filesystem server for "/sdcard". The library exposes a virtually identical interface to the ramfs library on which it is based and provides a C wrapper for the servers RPC interface. It exposes the following interface to libc:

errval_t fatfs_open(void *st, const char *path, int flags, fatfs_handle_t *rethandle);
errval_t fatfs_create(void *st, const char *path, int flags, fatfs_handle_t *rethandle);
errval_t fatfs_remove(void *st, const char *path);
errval_t fatfs_read(void *st, fatfs_handle_t handle, void *buffer, size_t bytes,
                    size_t *bytes_read);
errval_t fatfs_read_file_to_frame(fatfs_mount_t st, const char *path, struct capref frame, size_t *bytes_read);
errval_t fatfs_write(void *st, fatfs_handle_t handle, const void *buffer, size_t bytes,
                     size_t *bytes_written);
errval_t fatfs_truncate(void *st, fatfs_handle_t handle, size_t bytes);
errval_t fatfs_tell(void *st, fatfs_handle_t handle, size_t *pos);
errval_t fatfs_stat(void *st, fatfs_handle_t inhandle, struct fs_fileinfo *info);
errval_t fatfs_seek(void *st, fatfs_handle_t handle, enum fs_seekpos whence, off_t offset);
errval_t fatfs_close(void *st, fatfs_handle_t inhandle);
errval_t fatfs_opendir(void *st, const char *path, fatfs_handle_t *rethandle);
errval_t fatfs_dir_read_next(void *st, fatfs_handle_t inhandle, char **retname,
                             struct fs_fileinfo *info);
errval_t fatfs_closedir(void *st, fatfs_handle_t dhandle);
errval_t fatfs_mkdir(void *st, const char *path);
errval_t fatfs_rmdir(void *st, const char *path);
errval_t fatfs_mount(const char *uri, fatfs_mount_t *retst);

Since the server does not track the position of the cursor for each process, the client library has to do this itself. It keeps a list of file handles that contain basic information about the files. This includes, the position of the cursor and the filesize. The client library is responsible for updating its own view information when modifying the file. This does not introduce consistency problems, since there can only ever be one writer per file at a time (provided there is no malicious actor as described above). As a result, operations like fstat, fseek, and ftell do not require an RPC. The filesystem server only needs to be accessed to open and close files or to access information that is on the block device.

Finally, we want to take a look at the end to end performance of issuing a filesystem operation from userspace.

We run the benchmark from a userspace program that is spawned after the filesystem server is set up. All measurements were run 30 times with a complete running OS. Append and read both operate on the first cluster (4KiB) of a file.

The results of this benchmark can be seen in figure 10.5. We only inspect the most prominent operations for the sake of brevity.

Opening a file takes $5494.12ms$, this is due to the fact that the call also needs to create the file. The implementation of fopen first checks if the file exists by trying to open it. When this fails, because the file does not exist yet, it triggers another RPC to create the file. This explains the additional delay compared to the direct create operation.

Appending the first block to a file file takes $5494.12ms$, which includes communication overhead and traversing the directory to obtain the file handle. It is important to note, that libc does not try to write the entire cluster in one attempt. Instead it breaks it into 1024 byte chunks and triggers RPCs for each. This explains the added overhead over the direct FAT32 Library call.

Reading is subjected to the same chunking. It thus also introduces overhead resulting in a median latency of $3840.11ms$.

Closing a file multiple orders of magnitude faster at $0.051$ since it does not require any block operations. It is just a lookup in a hashmap and an RPC.

As mentioned before in section 7.5, we had an implementation of primitive "service binding" even before the individual projects started. Each service operated on a unique "port" (int) and clients could bind to it over UMP, even cross core.

This required an extra routing table from ports to DIDs (Domain IDs) such that inits would know where to route the binding request. Later I show how I got rid of the ports to remove one indirection. This is because the Nameservice with the ports would have in total 3 indirections (Service name -> Port -> DID). I wanted to simplify this.

I wanted to connect intra-core client-service pairs via LMP and inter-core via UMP. UMP could be used for both cases, but even though I didn’t benchmark this, LMP should be intuitively faster intra-core than UMP because sending messages intra-core is the LMP’s very purpose.

Supporting the LMP connection creating is easy because sending capabilities over LMP is already supported. The client, however, does not necessarily have an existing connection to the service. So in order to exchange the client-service endpoint capabilities, we need to route through a common node, e.g., core’s init.

For UMP, one endpoint (client) needs to allocate the frame for the channel and send it over to the other endpoint (service). One idea would be to just send frame information like base address and size, and forge it on the receiving end. However, only init can forge a capability.

There are a few approaches for designing a binding scheme with support for sending capabilities as described above. The one I found the most simple is shown on the figure 11.1.

We see a client and serviceA on the same core 0. To connect to this service, the client sends its LMP endpoint over init to the serviceA. Afterward, this service finishes the binding via sending its remote connection, now directly to the client.

For an inter-core of client to serviceB, the client allocates a frame to back the new UMP connection. Then they send it over to serviceB via core 0 init and core 1 init.

There are two issues that need to be resolved. First, how does the init know over which channel to forward the capability. Second, the RPC channels from init to children domains don’t exist yet. Remember that our RPC channels are unidirectional and the channels we set up on process spawn are from child to init.

For routing, we assign each service a unique SID (Service ID) which contains its Domain ID and Local Service ID. The Domain ID itself consists of Core ID and Local Domain ID¹¹1Now that I’m writing this, maybe I could’ve picked the names a bit better.. How this this organized in memory is shown on figure 11.2.

The reason for not just using the Domain ID is that there can be multiple services in a single domain, hence Local Service ID.

A shortend form of the SIDs with the Local Service ID omitted can be seen on figure 11.1 under domain names. Now using SIDs in the requests as destinations, init will always know to which domain to forward the request.

Whenever a service gets registered, the init needs to be able to forward requests to it. Therefore, I lazily (only on the first call of nameservice_register() from a domain) establish a connection to init via an RPC method INIT_ESTABLISH_DOMAIN_SERVER. The important caveat here is that before establishing this connection, I spawn a thread which listens on the default waitset to be able to accept the connection. There are definitely nicer ways around this, but refactoring it ended up being a TODO :)

. During the design my teammates kept asking me if they’ll be able to send frame capabilities arbitrarily over the nameservice channels. So instead of making a simple ServiceConnect RPC with arguments like this:

message ServiceConnectRequest {
  int64 destination_sid = 1;

  enum Type {
    UMP = 0;
    LMP = 1;
  }
  Type type = 2;
}

I created a generic Route RPC which can route arbitrary request over the inits, thus allowing to send/receive capabilities with any request over nameservice channel. The request gets always routed directly, unless the underlying channel is UMP and we’re sending/receiving capabilities.

message RouteRequest {
  uint64 destination_sid = 1;

  RpcMethod method = 2;
  RpcRequestWrap inner_request = 3;
}

Then for example for a ServiceConnectRequest, I put it into the RouteRequest and send it over. Note that the ServiceConnectRequest then doesn’t need to contain the destination_sid because the layer above, RouteRequest, has it.

In the actual implementation, a Nameserver (usr/nameserver/main.c) is a service named "nameserver" with the following interface:

enum RpcMethod {
      NS_LOOKUP = 0;
      NS_REGISTER = 1;
      NS_ENUMERATE = 2;
      NS_DEREGISTER = 3;
}

message ServiceInfo {
  string name = 1;
  uint64 sid = 2;
}

message NsRegisterRequest {
  ServiceInfo service = 1;
}

message NsLookupRequest {
  string name = 1;
}

message NsLookupResponse {
  uint64 sid = 1;
}

// Enumerate and Deregister omitted for breviy.

When the Nameserver receives a Register request, it checks if a service with the given name already exists. If yes, an error is returned, otherwise the service gets registered. Registering a service just appends it to an internal collections_listnode. We do not check whether the request is coming from a "credible" source, i.e., if the DID of the caller corresponds to the DID found in the SID of the request.

Similarly, a lookup just takes a name, goes through the list of registered services, and if a hit is found returns the corresponding SID. I omit describing Deregister and Enumerate because there’s also nothing surprising there.

An interesting problem is how to bootstrap the Nameserver such that all domains including init can connect to it and then use it as just any other nameservice channel. The problem is that at the time the Nameserver is trying to nameservice_register() itself, there’s no Nameserver. And similarly, when clients are first trying to connect to the Nameserver via nameservice_lookup(), there’s no connection to Nameserver to resolve the name.

Therefore, I just take inspiration from the traditional networks and give our Nameserver a fixed SID. Namely it’s the first domain spawned after init on core 0, thus having the SID 0.1.0. Therefore, the first thing a Nameserver does after spawning is add itself to the records. This solves the Nameserver registering problem.

Now for the Nameserver lookup, the fixed SID also solves this problem because now we can just directly connect to a well-known fixed SID of the Nameserver with no need for a Nameserver lookup. We do this as part of the process-spawning. So when process’s main() is entered, the connection to the Nameserver is already established.

I had to add a few new interfaces in order to allow the Protobuf support. I omit them for brevity as they’re just mere wrappers over the RPC interface already seen in chapter 8. What I want to show though is how I "backsupport" the original API that we had to implement.

Recall the API for the nameservice_rpc() from the handout:

errval_t nameservice_rpc(nameservice_chan_t chan, void *message, size_t bytes,
                         void **response, size_t *response_bytes, struct capref tx_cap,
                         struct capref rx_cap);

To support this over protos, I created a ServiceBytes RPC method which wraps the user-provided buffer and then sens it over the Protobuf RPC interface.

message ServiceBytesRequest {
  bytes raw_bytes = 1;
}

message ServiceBytesResponse {
  bytes raw_bytes = 1;
}

This incurs an extra memory copy due to how the underlying RPC layer is implemented, but as discussed before it could be optimized away (see subsection 8.3.1).

In order to hide the underlying nameservice channel type, the provided interface uses a simple typedef of void *.

// nameserver.h
typedef struct void *nameservice_chan_t;

errval_t nameservice_rpc(nameservice_chan_t chan, void *message, size_t bytes,
                         void **response, size_t *response_bytes, struct capref tx_cap,
                         struct capref rx_cap);
// shell.c
nameservice_chan_t chan;
// WRONG, but compiles.
errval_t err = nameservice_rpc(&chan, ...);

As the snippet above shows, it’s very easy to mess up without the compiler complaining. This is what one of my teammates encountered early on, following the standard C mantra of defining local variable on stack and then passing down a pointer to it to get it filled with data. However, the chan here already is a pointer.

So after hunting down this bug I changed the opaque interface to use a forward declaration like this: void *.

// nameserver.h
typedef struct nameservice_chan *nameservice_chan_t;

// shell.c
nameservice_chan_t chan;
// WRONG, but doesn’t compile :)
errval_t err = nameservice_rpc(&chan, ...);

The Devq RX Manager is not an actual abstraction in the code itself since it is very simple. In order to read from the network, we dequeue a buffer from the RX device queue, call the Ethernet packet handler, and then return the buffer back to the RX queue.

The Devq TX Manager (struct devqtx_manager) manages the TX device queue of the enet controller. It is an abstraction around the queues that lets you conveniently get a pointer, such that the layer above can just write the bytes of the packet into the buffer. When the layer above is done, it can just pass that pointer and a size to the Devq TX Manager to enqueue and eventually send the packet over the network.

In the initialization of the Devq TX Manager, we create a linked list using statically allocated memory with one node for each slot in the Devq, this is possible since the size is known at compile time. We then create a list node for each block of memory that is handled by the Devq. For each of this block we can find the linked list node just by looking at the block’s address since the nodes of the linked list are store inside an array.

The Devq TX Manger needs to be thread safe since for example answering an ARP request and sending a UDP packet might happen concurrently. Devqs are not thread safe, this is why we have a mutex around the 2 methods exposed to the other layers. Next we will explain how we can get a free buffer and then send it.

The Ethernet layer provides the following interface to handle incoming packets and get the MAC address of the device in case another layer needs it.

void handle_ethernet(struct devq_buf* buf, size_t packet_length);
struct eth_addr ethernet_get_mac(void);

The Ethernet handler gets invoked by the Devq RX Manager for every packet that is received on the device and checks if the destination MAC address is a broadcast or the address of the device. If the packet is for this device, then the Ethernet handler looks at the ether type and calls the corresponding packet handler of the layer above with a pointer to the payload of the Ethernet packet as an argument.

In order to send an Ethernet packet, an Ethernet Send Context has to be created. This is an object that holds a pointer to an Ethernet header. This Ethernet header as has a file contains a filed payload that point to the payload. This context is retrieved by asking the Devq TX Manager for a new buffer and then casting it to the Ethernet header type and setting the source and destination MAC address, and the Ether Type as specified. Then the layer above can write to the payload buffer as it wishes and send the context by providing the payload length. This send method just forwards the call to the Devq TX Manager such that the packets actually gets send out. This is the interface provided by the ethernet layer.

struct eth_hdr {
    struct eth_addr dst;
    struct eth_addr src;
    uint16_t type;
    uint8_t payload[];
} __attribute__((__packed__));

struct eth_send_context {
    struct eth_hdr* pkt;
};

errval_t ethernet_get_context(
    struct eth_send_context *ret, struct eth_addr dst, uint16_t type);

errval_t ethernet_send_context(
    struct eth_send_context context, size_t payload_length);

TCP sessions are managed by a HashMap from the triplet (source port, destination port, destination ip) to the session state. The sessions state contains things like the current Sequence and Acknowledgment number we are at, but also the Send Window and a session mutex. The session mutex is required since we might send and receive packets for one session concurrently. So whenever we get the current connection session state for an incoming packet, the first thing we do is acquiring the session lock (obviously the HashMap is also guarded by its own mutex).

Since TCP requires packets to be resent when not acknowledged, we need to store packets till they got acknowledged. We store packets in one ring buffer per connection. Each of the slots in the ring buffer have a state that indicate if they are in use or not and a time field to indicate when a packet has been inserted into the buffer. Whenever we send a packet, we also copy the TCP header + payload into the ring buffer and set the slot to used. Whenever we receive an acknowledgement, we set all slots to in this ring buffer to unused that are included with this ack.

In order to actually retransmit packets, we set up a periodic event with the included deferred library. This periodic event walks over each session and checks the send ring buffers to retransmit packets that were sent longer than then Round Trip Time (of the session) times TCP_RETRANSMISSION_RTT_MULTIPLIER long ago.

In order to handle TCP servers, we just whitelist ports with a HashMap to allow a port to accept connections and answer to handshakes.

A user can initiate an ARPC RPC to the netsocket server to make sure, when sending a UDP packet to a new unseen IP, that the MAC address is known. Otherwise, it might happen that UDP send returns an MAC unknown error. This can be done by net_socket_arp_request(). TCP takes care of ARP requests on its own, and UDP can still answer to incoming packets since the network stack will remember the MAC.

This is how the user code looks to create a UDP socket and send a string over it.

struct udp_socket udp_socket;
udp_socket_create(&udp_socket, 1234);
udp_socket_send(&udp_socket, str_to_ip_addr("10.0.2.2"),
                1235, "Hello world\n", 12);
udp_socket_close(&tcp_socket);

This is how the user code looks to connect to a tcp server with a connection timeout:

struct tcp_socket tcp_socket;
tcp_connect(&tcp_socket, local_port, remote_port, ip_addr, timeout);
tcp_socket_send(&tcp_socket, "Hello world\n", 12);
tcp_socket_close(&tcp_socket);

Of course since the underlying is a UMP channel, we can register receives with TCP by calling tcp_socket_register_recv(...)

This is how the user code looks to implement a TCP server and accept incoming connections. Where tcp_recv_handler(..) is a function that handles incoming TCP packets in this connection. The socket returned is a TCP client sockets which can be used as previously discussed.

static void tcp_recv_handler(void *arg) {
    struct tcp_socket *tcp_socket = (struct tcp_socket *)arg;
    //...
    tcp_socket_recv(tcp_socket, &buf_ptr, &buflen);
    // ...
    tcp_socket_send(tcp_socket, buf_ptr, buflen);
}

static void handle_tcp_client(struct tcp_socket *tcp_socket) {
    tcp_socket_register_recv(tcp_socket, get_default_waitset(),
                             MKCLOSURE(tcp_recv_handler, tcp_socket));
}
// ....
struct tcp_server tcp_server;
tcp_server_create(&tcp_server, 1235, &handle_tcp_client)

We measured UDP and TCP throughput with a python application either sending or receiving data in a while loop till finished. We send 100 000 messages of size 1400 bytes (TCP might decide to split them into more messages), for the receive and send High Speed send connections, but only 100 messages for the normal send connections since they are really slow. For UDP we were sending packets at a rate of 90 Mbits to the Toradex device and counted how many made it there and were not dropped (the other way around there was no packet loss since my Linux machine can easily keep up with 30 Mbits). For TCP we were sending in a while loop, relying on the default TCP implementation on Ubuntu 20.04.4. To finish an experiment and end the time measurement, the remote side of the connection has to ACK the last packet by sending the string "END".

We were able to achieve great throughput results for UDP and TCP, which can be seen in figure 12.2. We can see here that High speed connection give an speed-up of up to 320x, this shows that actively waiting with a thread on something is way faster than waiting on something with a wait set.

We saw that we can achieve High throughput but also acceptable (not great though) latency. The user can now decide what it needs, for High Bandwidth applications it should use High Speed Channels but for low latency and low bandwidth requirement the normal channel should be used (e.g. for an ECHO server).

One clear limitation is that users when sending a UDP packet to a new destination first need to make an ARP Request RPC. The decision for this was made because many other options come with other disadvantages. For example, if we decide to buffer packets for an IP with an not replied ARP request: How many packets do we buffer? Do we buffer per user or per IP? If there is a cut of point, why provide buffering in the first place? When to delete the buffered IP packets if the MAC never becomes available? And the main concern here is if there is no buffer limit per user it is very easily even accidentally possible to let the ENET driver run out of memory by sending it packets for an unreachable destination.

Our code currently does not check IP, UDP, or TCP checksums on incoming packets.

This might cause weird behaviour if someone sends packets with wrong and to long lengths to the device. This might cause the ENET module to over walk the RX memory, cause a pagefault and die.

There is currently no way to ask for a random free source UDP or TCP port, the user basically has to try out some ports.

Obviously we did not implement a full TCP specification, so here is a list of the main simplifications we did. There are many more things that are not implemented from TCP like Options and Keep Alive messages (and much more…).

Currently, there is no clean up happening if a process dies without closing its sessions. Which means that a port can not be reused later if a user process dies without cleaning up.