BRUMM:A Case for Predictable Memory Reclamation

To understand these different ways of using user memory, this section takes a closer look at the architecture of the OS used throughout this paper. The L4Re microkernel, running in the privileged CPU mode, implements only the minimal set of mechanisms that are required to support applications and services in user mode. The core abstractions that the kernel provides are kernel objects and memory mappings. Kernel objects [10] are abstractions for interacting with the system, such as IPC gates for inter-process communication, semaphores and interrupts for coordination, factories for limiting the usage of kernel memory, and threads and tasks for process management. Applications can only interact with kernel objects via capabilities in their local capability space. Process $A$ on the left side of Figure 2 highlights that the capability space is simply a per-task list of capabilities inside the kernel – analogous to the file descriptor table in Linux.

User-space applications index this table in system calls via capability selectors as shown on the bottom left of the figure. Capabilities to kernel objects can also be shared with other applications, for example, to allow two applications to use a shared semaphore for coordination.

For this paper, memory mappings are particularly relevant. On the architectural side, a mapping is simply the insertion of a physical frame’s address into a page table, making the frame’s memory accessible to a process. Memory mappings are ubiquitously used in L4Re, for example, for loading the binary of new processes into their address space, for providing anonymous memory, or for fast shared memory communication. Memory management is handled in user space following a capability-based permission management – similar to the capabilities for kernel objects. To this end, processes gain access to pages of main memory as part of a capability exchange. For example, processes commonly allocate anonymous memory pages for their heap by requesting them from a memory service via inter-process communication (IPC). This memory service has a lot of free, unused memory pages mapped into its own address space. It can then reply to the IPC inquiry by sending a capability referring to one of its own, unused memory pages.

The operation of sharing such a page mapping, map, is depicted in the center of Figure 2 – process $A$ maps a page referring to frame 0xE from its own address space into the page table of $B$. This mapping operation is realized by the kernel via two actions. First, the kernel inserts an entry referring to frame 0xE into the page table of $B$. Second, the kernel records the new mapping of the page frame in the mapping database. This database is depicted on the right side of Figure 2. The kernel records the new mapping (in the address space of $B$) as a child node of the source mapping (in the address space of $A$). The derivation relations between these nodes form the derivation tree, which is stored in the mapping database for each frame in L4Re. In Figure 2, the nodes $A_2$, $B_1$, and $B_2$ form the capability derivation tree for the frame 0xE. Thus, the mapping database remembers who mapped which page to whom; even when $B$ shares a page frame with itself. This record keeping is essential so that applications can reclaim memory they have shared with others and then reuse it safely. For example, process $A$ can instruct the kernel to remove all page mappings derived from $A_2$ using the unmap system call. The kernel then uses the mapping database to recursively remove the mappings $B_1$ and $B_2$ from $B$ – a mechanism known as capability revocation; importantly, $A$ does not need to explicitly enumerate or even know about $B_2$. User-space memory managers can use this recursive unmapping to implement demand paging and to ensure that memory is returned on process termination. However, the kernel also needs to clean up the associated management structures when reclaiming memory. The thereby induced latency is the primary subject for the Brumm accounting mechanism.

This section examines the question: Can an existing accounting mechanism function as a proxy for reclamation latency enforcement? Stated differently: Does a system operator need the explicit reclamation latency accounting of Brumm or could they instead set a budget for a different resource while limiting reclamation latency just as accurately? Take kernel memory accounting as an example: Limiting the amount of kernel memory a process can use also limits the number of memory mappings a process can create. Every entry in the mapping database and every new frame for the page table requires kernel memory. Thus, setting a budget for kernel memory usage does, ultimately, also limit memory mapping reclamation latency. However, this accounting metric is neither accurate nor sufficient.

To show that existing budgeting metrics are not accurate, we compare two microbenchmarks. These benchmarks measure the latency of the unmap system call in two antipodal settings:

• $\mathrm{■}$

  “Single Frame”: In the first benchmark, the same page is mapped to many locations in the same address space, creating a very wide subtree of depth one in the mapping database. Notably, only a single frame is referenced and so only a single frame of user-space memory is used.

• $\mathrm{■}$

  “Many Frames”: The second benchmark allocates many frames of user-space memory. Each frame is mapped only once, creating a single new entry in the mapping database of each frame. In contrast to the first benchmark, there are many, small subtrees in the mapping databases that need to be considered during the unmap system call.

The problem analysis considers four different budgeting metrics: the preparation time of the benchmark, the number of mapping system calls performed during the preparation phase, the amount of kernel memory taken up by the benchmark application, and the usage of user-space memory frames. Using the kernel memory metric as an example, a benchmark run looks as follows: First, the benchmark application measures the current kernel memory utilization. Then, in the preparation phase, it creates many memory mappings using either the “Single Frame” or the “Many Frames” benchmark – varying the number of memory mappings from run to run. Afterwards, the application measures the kernel memory usage again. Finally, the created memory mappings are unmapped and the latency of this system call, the reclamation latency, is measured.

Figure 3 shows four scatter plots: They compare the reclamation latency of benchmark runs with the four accounting metrics.

Considering the upper-left plot of Figure 3, the “Many Frames” benchmark takes consistently longer to reclaim than the “Single Frame” benchmark when looking at data points with the same preparation time. The ratio between reclamation latency and preparation time is $0.17$ for the “Single Frame” benchmark, compared to $0.48$ for “Many Frames”. The same relationship emerges when plotting against the number of system calls. The “Many Frames” benchmark has again a higher ratio with $632$ reclamation latency cycles per system call performed during preparation – compared to the ratio of $216$ for the other benchmark. The third accounting metric, kernel memory, shows similar behavior. Reclaiming memory mappings that take up around $4$ MiB of kernel memory in the “Single Frame” benchmark only takes $38\times {10}^6$ cycles. When the mappings are prepared like in the second benchmark, reclamation takes far longer – $116\times {10}^6$ cycles – even though the same $4$ MiB of kernel memory are used for the mapping structures. Unsurprisingly, the benchmarks look even more different when considering the user memory usage. By its construction, the “Single Frame” benchmark only uses a single frame of user memory but creates many mappings for it. These mappings need considerable time to be reclaimed. Because user memory accounting cannot detect excessive usage of memory mappings, it is fundamentally not viable for predicting reclamation latency. But also the other three accounting metrics do not accurately predict reclamation latency as is highlighted by how vastly different the two benchmarks behave in the plots of Figure 3.

There are additional, practical considerations that rule out the use of preparation time and kernel memory utilization as proxies for reclamation latency. Limiting the preparation time, i.e., the runtime of customer workloads on an edge cloud, just to prevent maliciously high reclamation latency is not a justifiable trade off. This would rule out any occasional long-running services from the outset; this is not practical. Kernel memory accounting is also problematic because it does not follow the mapping derivation tree. If a subordinate process shares memory with some unrelated process, such as a shared network service, the mapping database entries for the shared mappings are not accounted to the kernel memory quota of the subordinate process. Instead, they are accounted towards the shared service. Kernel memory accounting is not aware of the recursive nature of memory mapping inheritance. Furthermore, kernel memory is not only used for memory mappings but for all kinds of kernel-internal state. Thus, heavily restricting kernel memory budgets to limit reclamation latency can also prevent benign processes from creating large kernel objects such as thread objects. We argue that Brumm is the only accounting solution for reclamation latency that does not unduly restrict benign resource allocations; it predicts and accounts for memory reclamation latency explicitly.

Motivated by the edge cloud use case, we assume a system setup with a central controller process that spawns and terminates applications – shown in the top left of Figure 4.

The spawned applications need main memory to store data and operate on. This memory is provided by a memory service that holds the available page frames in the system and manages page allocations for the applications. On Linux, the memory management is integrated into the monolithic kernel [31]. In contrast, the memory service is a separate user-space process in L4Re [10], like it is in many other microkernel systems [27, 2, 17, 18]. The memory service provides applications with pages of anonymous memory. These pages need to be accessible from the application’s address space. The kernel performs these necessary mapping operations and the included page table management as seen on the right side of Figure 4. These operations involve the kernel managing state objects that take up kernel memory. Applications might even share pages with other processes in the system, resulting in more state that the kernel has to manage. All of the memory service’s and kernel’s state describing the page allocations has to be eventually cleaned up.

For our design of Brumm, reclamation starts when the controller instructs the memory service to reclaim all pages handed out to one of its child applications¹¹1Because our Brumm design is only concerned with user-space memory reclamation, we do not examine the deletion of kernel objects referenced by the child. The reclamation of kernel objects is an interesting future topic but orthogonal to the analysis of memory mappings in this paper. – shown on the left of Figure 4. The memory service enumerates all allocations that belong to the child and then instructs the kernel to unmap all these pages from the child’s address space. If the child has granted other processes access to these pages via mapping operations, the kernel will recursively revoke these page mappings too. For this, the kernel consults its mapping information database. The memory service can therefore be sure that no process can access the reclaimed memory and it is safe to reuse. Figure 4 depicts an example of a derived memory mapping, “Mapping $a_1^{\prime }$”. All these cleanup steps need to be accounted for in Brumm.

To implement the accounting, the controller needs to create a kind of budget object that denotes the limit for the reclamation latency of the memory handed out to child applications. This concept of an accounting structure is similar to Linux cgroups [30] and L4Re factories [10]. Like with these existing techniques, the quota object is stored inside the kernel and created by the controller. To limit the reclamation latency, accounting is done in advance. Whenever the memory service or the kernel create a state object for managing memory allocations, the expected cleanup time is accounted towards a quota object. Regardless of the OS, the primary state objects to consider are the allocation state in the memory service and the mapping and page-table information inside the kernel. Brumm requires an OS-specific model that links state allocations to expected cleanup times. In the implementation section we derive such a model for the L4Re microkernel. For our Brumm mechanism, we assume that any allocation of state objects increases the future reclamation latency; thus, our model behaves monotonically. Furthermore, we rule out any external influence on the reclamation latency. Changes on one side of the overall system state must not prolong the reclamation of unrelated, accounted memory mappings. In our prototypical implementation, this requires some caution in memory allocation as later discussed in Section 6.1.

Putting it all together, the operation flow using Brumm is shown in Figure 4. The controller creates a new quota object with a limited reclamation latency budget before spawning a new subordinate process group. The memory service is responsible for providing the new processes with main memory. The controller instructs the memory service to only allocate and hand out memory under the governance of the child’s reclamation quota. Any changes to the memory subsystem regarding the child will be accounted towards the quota object. This includes, for example, the expected reclamation latency of “Mapping $a_1$”. Should an operation, like creating a shared mapping between processes, exhaust the quota, the kernel will deny the offending operation. This makes sure that the budgets in the Brumm design can reliably set limits to the reclamation latency for main memory even when applications misbehave. This prevents unexpectedly long cleanup operations that keep the OS busy.

The first step in deploying Brumm is to obtain reliable estimates of the time spent on individual sub-operations in the kernel and the memory service during reclamation of given-out user memory. We call this the profiling phase of Brumm. Once these per-operation latencies are known, the Brumm quota subsystem is configured to use these values when accounting against reclamation latency quotas.

Estimating latencies in the profiling phase is not straightforward. The runtime of sub-operations can vary drastically across executions depending on the hardware state; for example, differences in CPU caches can result in different execution times. We rely on measurement-based timing analysis [36] for our prototype. Brumm can simply use the mean execution time – determined by measurement on the target system – for all sub-operation latency estimates. Alternatively, designers may apply a static worst-case execution time analysis to the kernel and memory service source code to arrive at an upper bound for the execution time of every sub-operation. Similarly, the system designer could empirically determine tail latency estimates for every sub-operation in the kernel’s memory subsystem. However, using worst-case estimates for the individual sub-operations is likely too pessimistic. The Brumm quota mechanism aggregates latency estimates. It is extremely unlikely that all sub-operations in a long memory unmapping operation execute exceptionally slow. Thus, using the mean estimate for all operations is likely sufficient for cloud use cases.

After the profiling phase, the designer profiles actual, realistic workloads. In the edge cloud scenario, these workloads could be containers with web servers or databases. The system designer uses the quota system of Brumm to monitor the peak consumption of the reclamation latency budget. The measured peaks give a realistic baseline of “benign” reclamation latencies – values that should already be acceptable for the higher-level scheduling and billing policies of the cloud operator.

Armed with this baseline, the controller process can set a hard reclamation latency budget for each subordinate process group. The budget is chosen as the observed maximum latency plus a modest safety margin to absorb occasional variations. From this point on, the kernel checks any attempt by a child process to allocate additional state in the memory subsystem against the remaining quota. If the operation will cause the estimated reclamation latency to exceed the allotted budget, the kernel denies the request.

In other words, Brumm introduces a completely independent budget that accounts for the expected time needed to clean up an application’s memory. This budget is enforced regardless of the current availability of other resources, guaranteeing that the system can always reclaim memory within the prescribed latency bound. System designers can therefore reason about isolation and predictability at the level of reclamation latency, shielding against any rough, malicious application that uses the memory management subsystem to threaten system availability.

We want to reflect on the effort required to adopt Brumm to a new platform. We differentiate two kinds of platform changes: a different OS and a different hardware configuration. Adopting Brumm for a new OS requires manual code analysis and implementation effort. Developers have to identify the source code locations that contribute to the reclamation latency of memory mappings. For microkernels, this is commonly the code path handling capability revocation. Developers may need to extend the OS’s performance tracing to measure the latency of all the sub-operations along the reclamation code path. Furthermore, developers must implement the reclamation latency accounting in the code that handles allocating memory and creating corresponding page mappings.

With all these code changes at hand, adopting the implementation to a new hardware configuration such as a different architecture or different CPU is rather straightforward and can be automated. The system integrator needs to execute the profiling phase – as discussed in the previous section – to measure the latency of the individual sub-operations in the reclamation code path. These measured latencies are then used to configure the Brumm accounting for the OS installation. We imagine that this step can easily be automated and performed at boot time whenever the system’s hardware configuration has changed. For the prototype discussed in the section below, we did not yet implement this automation step.

The first step in predicting reclamation latency is to understand how that latency is composed. A significant amount of this time is spent outside the kernel in the controller and in the memory service, which initiates reclamation after receiving a signal, which, for example, can be due to a cloud client exceeding its compute-time budget. Because the current prototype does not target a precise use case, we deliberately omit this external overhead and focus on the kernel-internal management structures.

When the controller decides that a child’s memory must be reclaimed, the memory service eventually issues an unmap request to the kernel. Figure 5 illustrates the anatomy of this unmap system call.

The request begins with a system-call entry ; the time spent in this transition is denoted by $t_{\mathrm{syscall}}$. Through the system call, the service supplies a virtual address range that it wishes to unmap. Consequently, the kernel’s unmap logic has to walk the process’s page table in order to enumerate every page/mapping that falls within the specified range. We call the set of these pages $P$. For each page $p\in P$ the kernel must locate the corresponding entry in the global mapping database . We denote the time required for such a lookup $t_{\mathrm{lookup}}$. All mappings that are derived from the pages contained in range $P$ must be removed not only from the child itself but also from any other processes that inherited access rights to these page frames. Thus, once a mapping entry for page $p$ has been found, the kernel proceeds to traverse the subtree of descendants in the mapping database. We denote the set of all descendants of $p$ as $D_p$. The data layout of the mapping database is only logically a tree but physically a depth-first linked list; this is visualized by the two different arrow styles in Figure 5. Thus, all descendants of $p$ lie in a linear list structure. Brumm does not need to consider the hierarchical, logical structure of the database for estimating reclamation latency. As shown by the two orange boxes in the center of the figure, the traversal is performed twice: first to delete the page-table entries in each descendant’s address space ($t_{\mathrm{pt}}$ per descendant) and second to erase the corresponding records from the mapping database ($t_{\mathrm{map}}$ per descendant) . The time needed to leave the kernel again and return back to the memory service is also accounted towards $t_{\mathrm{syscall}}$ .

Summing the contributions of all pages in the range yields the overall unmap latency

which captures the essential components that Brumm must account for when estimating reclamation time. This formula also highlights why simply counting the total number of mapping database entries – ${\sum }_{p\in P}|D_p|$ – does not result in an accurate accounting. Looking up a mapping under question for a particular frame in the mapping database takes a bit of time ($t_{\mathrm{lookup}}$), but the kernel can then walk the derivation subtree below this mapping without performing lookups again. This is also the major factor why the “Single Frame” and “Many Frames” benchmarks behave differently in Section 2.2. Thus, we will make sure to specifically account for the lookup latency in the following implementation.

The prototypical implementation of Brumm is currently confined to the core kernel mechanisms: At present, there is no dedicated controller process nor a special memory service. Nevertheless, all of the kernel-side building blocks required for a functional prototype have been realized and they are already being exercised in the measurements presented later in the paper. These implemented building blocks include the tracing of sub-operations, the kernel-internal reclamation latency accounting, and the corresponding user-space-facing quota API via system calls.

Central to the current implementation is a new kernel object for accounting the estimated reclamation latency – see the right box in Figure 6.

User-space processes are able to create an instance of this quota object; in the proposed Brumm design, the creator would be the controller process. The kernel initializes the object’s remaining_quota with the desired reclamation latency budget. The creator process receives a capability to the new object. When a process maps a region of memory into another process it may also specify the capability to a quota object. If such a capability is given, the kernel automatically attributes the expected reclamation latency of the newly created mapping to the remaining quota stored in the quota object. In a final system, this step would be performed by the memory service on behalf of the controller, either eagerly during the IPC that requests the memory mapping or lazily when the mapping is established as a result of page-fault handling.

Internally, the kernel links the child’s mapping entry, which is inserted into the global mapping database, to the quota object. At the same time, the kernel deducts the estimated costs of the lookup operation ($t_{\mathrm{lookup}}$) as well as the page-table update and mapping-database removal costs ($t_{\mathrm{pt}}$ and $t_{\mathrm{map}}$) from the remaining_quota. Whenever later a descendant mapping is created for a mapping that already references a quota object, the kernel again subtracts $t_{\mathrm{pt}}$ and $t_{\mathrm{map}}$ in anticipation of the future traversal of the mapping database. Importantly, the kernel does not subtract $t_{\mathrm{lookup}}$: The lookup operation is only considered for the first mapping in a quota-accounted subtree, which is reflected by is_first in the Mapping class – see Figure 6. Conversely, when a mapping is removed, the previously reserved quota is returned to the quota object, thereby restoring the budget for subsequent operations.

The system call overhead ($t_{\mathrm{syscall}}$) cannot be accounted from inside the kernel. Because the memory service performs allocation management in user space, only it knows how many individual system calls will be required to unmap all allocations belonging to a child process. Following the microkernel principle, the L4Re kernel has no knowledge of the semantic meaning of mappings in virtual address spaces. It only implements the mechanism of mapping frames into page tables.

When the controller instructs the memory service to reclaim a child’s memory, the service first initiates deletion of the quota object. This deletion request does not immediately free the quota – because kernel objects may still hold references to it – but it locks (is_locked) the object; no further allocations can consume the budget while reclamation proceeds. After the lock is in place, the memory service issues the unmap system call; the kernel’s accounting guarantees that the unmap will complete within the specified reclamation time budget.

The numerical values for $t_{\mathrm{lookup}}$ (lookup_cost in Figure 6) and the combined $t_{\mathrm{pt}}+t_{\mathrm{map}}$ (mapdb_cost) are not hard-coded in the kernel. Instead, they are supplied by the controller at the moment the quota object is created. Because the parameters are set at run time, system designers can experiment with different latency models, update the values on the fly, and run multiple varieties of tests without recompiling the kernel or rebooting the system.

All measurements are performed on a dual-socket server featuring two Intel Xeon Platinum 8358 CPUs (32 cores per CPU) and $512$ GiB of main memory. We disabled both simultaneous multithreading (Hyper-Threading) and temporary overclocking (Turbo Boost). Furthermore, the benchmarks set the CPU’s pstate configuration to the maximum-performance mode. The kernel is configured to support a multi-core system. However, we mainly look at single-core benchmarks for this evaluation; most benchmarks are executed on a single CPU core. The general idea of Brumm is nevertheless extensible to multi-core systems as we argue in Section 6.2. All benchmarks in this section are using the x86 time stamp counter for measuring latencies. The depicted latency values are thus given in reference clock cycles which are proportional to wall-clock time.

Throughout this section, we will use a deliberately artificial benchmark to assess the latency of kernel operations involving memory mappings. This “Random Map” benchmark starts out with a contiguous range of pages within a single address space. Starting from this base range, the benchmark recursively creates child mappings in the same address space forming an inheritance tree of page mappings for each frame in the base range. The number of child mappings to create is randomized; thus, the kernel’s mapping databases will look quite chaotic with mapping hierarchies of random width and depth. After this setup phase, the benchmark uses the unmap system call on the base range to trigger a recursive reclamation of all the memory mappings. By exercising a wide variety of mapping configurations, the benchmark is able to expose a wide spectrum of sub-operations that occur during an unmap system call, including slower paths.

To obtain the kernel-side latency estimates required by Brumm, we must first determine the latencies of the individual kernel operations that are subtracted from the reclamation-latency quota: the system-call overhead ($t_{\mathrm{syscall}}$), the mapping-lookup cost ($t_{\mathrm{lookup}}$), the page-table update cost ($t_{\mathrm{pt}}$), and the mapping-database removal cost ($t_{\mathrm{map}}$). In principle, these values could be derived by means of static timing analysis, yielding a worst-case execution time (WCET) for a given hardware platform. In practice however, no ready-to-use workflow exists for performing WCET analysis on the L4Re microkernel running on x86 systems; developing such workflows is out of scope for this work. Consequently, we resort to a straightforward measurement-based timing analysis [36]. By measuring the actual execution on real hardware, we can obtain average or tail latency figures that are sufficient for the non-hard-real-time scenarios we target – namely workloads in edge clouds. This approach is also common in industry, where measurement-based timing analysis is frequently employed to estimate worst-case system behavior [1]. Because the choice of timing-analysis technique is orthogonal to the Brumm design, future work could replace the empirical values with statically-derived WCET numbers without affecting the rest of the mechanism.

The individual latency numbers are measured as follows. The $t_{\mathrm{syscall}}$ component is obtained by timing a no-operation unmap system call; this captures the full round-trip latency from user space into the kernel and back. The remaining three components – $t_{\mathrm{lookup}}$, $t_{\mathrm{pt}}$, and $t_{\mathrm{map}}$ – are measured using in-kernel trace points during the “Random Map” benchmark. Before and after each lookup, each page-table manipulation, and each mapping-database operation, the kernel writes a timestamp into its trace buffer. After the benchmark finishes, the buffer is extracted and the timestamps are post-processed to yield the individual latency values.

The benchmark results are depicted in Figure 7, which shows one plot for each of the latency values to estimate.

The plots contain cumulative distribution functions for the measured latencies in reference clock cycles. In the top-left plot, nearly all of the measured values for the no-operation unmap system call are close to the mean latency of $458$ cycles and the 99th percentile of $468$ cycles. There is an outlier at $2122$ cycles, showing that a system call can occasionally take $4.6$ times longer than the mean. The plot for $t_{\mathrm{lookup}}$ shows a larger variance. While the mean is at a low $652$ cycles, the percentile value is at $1299$ cycles. The other two plots for $t_{\mathrm{pt}}$ and $t_{\mathrm{map}}$ show a similarly high variance with mean values at $144$ cycles/$289$ cycles and 99th percentiles at $444$ cycles/$608$ cycles, respectively. We suspect that the severe outliers are mainly due to the complex x86 architecture with its speculative mispredictions, cache misses, device interrupts, and firmware executions. Furthermore, the periodic timer interrupts of the L4Re scheduler can occasionally delay benchmark executions. Nevertheless, we can deduce mean and tail-latency estimates from these measurements to make reclamation latency predictions.

To evaluate how well the Brumm accounting mechanism can predict the reclamation latency of a memory unmap operation, we again use the “Random Map” benchmark. This time, we use the reclamation-quota object that we added to the kernel in Section 4.2. This object records the two values required for the estimation: the number of pages that belong to the unmap request ($|P|$) and the total number of descendant mappings that have to be processed (${\sum }_{p\in P}|D_p|$). With these values at hand, we can apply Equation 1 to compute a prediction for the total latency of this exact unmap system call. At the same time, we also measure the real unmap latency from the moment the benchmark program issues the unmap system call until the kernel returns control to user space. Thus, each benchmark run records the predicted and measured latency values.

The benchmark results are plotted on the left of Figure 8.

Each individual experiment appears as three dots (one real measurement and two predictions); the horizontal axis orders the points by increasing measured latency, while the vertical axis shows the corresponding latency values (both for predicted and for measured latency). For every benchmark run, we display two predictions: one obtained by inserting the average values of the four sub-operation latencies ($t_{\mathrm{syscall}}$, $t_{\mathrm{lookup}}$, $t_{\mathrm{pt}}$, and $t_{\mathrm{map}}$) shown in Figure 7, and another that uses the tail latency (99th-percentile) values of the same distributions. The predictions are plotted with the same x-coordinate as the measured value to which they refer.

As anticipated, the tail-latency-based prediction systematically overshoots the actual execution time. For example, the rightmost datapoints of the left plot yield a latency overestimation of $3.9$ times (71 versus 277 million cycles). This pessimism would be undesirable for the cloud-oriented scenario that motivated Brumm, where overly conservative budgets could restrict benign edge workloads unduly. Even the prediction based on average component latencies exhibits a noticeable overestimation, although the difference is considerably smaller than with the tail latency model. The predicted latency using the mean – again for the rightmost datapoints – is about 114 million cycles ($61$ % over the measured latency). To connect back to the problem analysis (Section 2.2), we also perform measurements using the “Single Frame” and “Many Frames” benchmarks. These benchmarks – on the right side of Figure 8 – show similar results.

We attribute the residual overestimation – even for the mean predictions – primarily to the measurement methodology used for obtaining the sub-operation latencies. During the latency analysis the kernel wrote timestamps into the trace buffer, which increased the execution time of the sub-operations. Consequently, the values fed into the model are larger than the true costs that are incurred when the kernel runs without tracing. If the evaluation were repeated on a platform that is amenable to static timing analysis without measurements, these artifacts might disappear and the predictions would become tighter.

Despite the systematic bias, the average-based prediction is meaningful: It provides a consistent overestimation that stays within the same order of magnitude as the real reclamation latency. This property enables a controller to allocate a reclamation time budget that is safe (i.e., never exceeded) while still being realistic enough to avoid limiting cloud tenants.

The reclamation latency budgeting introduced by the Brumm implementation inevitably influences the performance of both mapping and unmapping operations. In order to keep track of the budget, the kernel must execute a few extra instructions each time a mapping is created or destroyed: The kernel’s logic accesses the quota object, changes its reference count, and updates the bookkeeping field remaining_quota. Moreover, the code path now contains additional conditional branches that decide whether quota accounting is required for a particular mapping. Even when a process does not make use of reclamation quotas, the execution still traverses these branches, which adds a small amount of latency.

To quantify this impact, we evaluate the three distinct configurations

• $\mathrm{■}$

  “Disabled” – the accounting code is completely removed for the kernel at compile time,

• $\mathrm{■}$

  “Available” – the kernel contains the accounting code, but the benchmarks do not use any quota objects, and

• $\mathrm{■}$

  “Used” – the benchmarks actually instruct the kernel to perform reclamation budget accounting for the mappings touched in the tested system calls.

We first measure the latency of simple mapping and unmapping system calls using the “Random Map” benchmark. The map system call, inherently, touches only a single entry in the mapping database and updates a single, corresponding page-table entry. To capture simple unmapping system calls, we alter the “Random Map” benchmark to delete memory mappings starting from the leaves of the mapping hierarchy. Thus, no recursive reclamation is ever triggered and only a single mapping is removed at a time. The results, visualized as box plots in Figure 9, show only little performance loss.

The y-axes encode the configuration and the measured latencies on the x-axes are nearly the same in all configurations. More precisely, the median latencies of mapping a single page in the “Disabled” and the “Used” setting are not too far from each other – $1450$ cycles versus $1596$ cycles ($+10\%$). For unmapping only a single page with no children in the inheritance tree (a leaf), the latencies in both settings are even closer – $2848$ cycles versus $2916$ cycles ($+2.4\%$). This is likely due to the high overhead of the system call and kernel entry itself in all configurations. The few additional branches and the fast quota object manipulations therefore do not severely affect the latency of these simple system calls.

The situation changes when we again consider the unmodified “Random Map” benchmark with its large, recursive unmap operation. For each mapping configuration, we execute the unmap system call thrice – once for each kernel configuration. The latency values are sorted according to the “Disabled” measurement so that each triple of points can be compared directly. As shown in Figure 10, an overhead is only observed when the quota mechanism is actually employed.

As an example, we have a look at the values at index $170$. While the “Disabled” (55 million cycles) and the “Available” (57 million cycles) system call latencies are close, the “Used” setting results in a $28$ % higher latency of 71 million cycles. In the latter configuration, the kernel must perform reference count updates on the quota object and adjust the stored quota for every descendant mapping that is traversed, which explains the increase in latency compared with the other two settings. In contrast to the overhead results above, the latency of the kernel entry and exit becomes negligible for these long system calls. We also still see some additional potential for filigree optimizations, for example, by aggregating updates to the quota object, which happen in rapid successions for large, accounted mapping database subtrees.

The latency estimation of our Brumm implementation is currently only designed to be used in single-core scenarios; thus, accounting might not be as accurate on multi-core systems. Nevertheless, we evaluate the performance implications of the current implementation on multi-core systems. We adapted the “Single Frame” benchmark to a multi-core scenario in two variants: First, we designed the “Independent” benchmark. It splits the “Single Frame” benchmark among multiple processes and uses a different memory frame for each process. Thus, we expect only little sharing among these processes. In contrast, the “Shared” benchmark executes multiple instances of the “Single Frame” benchmark on threads of the same process and uses the same physical frame for all memory mappings. All benchmarks first perform memory mapping system calls and then a single unmap on the created mapping data structure. The combined latency of these two phases is measured and shown in Figure 11.

The single-core overhead of accounting follows the trend of Figure 10. Splitting the workload among multiple cores with little sharing in the “Independent” setting results in a longer execution time. This is likely due to some residual sharing in the mapping database design of the L4Re microkernel. Using the Brumm accounting in this multi-core benchmark results in an overhead partially due to atomic operations on the shared quota. The plot on the right (“Shared”) shows that sharing a lot of state in a multi-core setting drastically reduces performance. The performance is further reduced when compiling the Brumm implementation into the kernel. This might be due to increases in code and data structure sizes of the kernel.

Although mapping operations in the kernel are slower for the modified L4Re sources, we think that the overhead introduced by reclamation budget accounting is tolerable given the strong guarantees it provides towards bounded memory reclamation latency.

A first limitation concerns the cost of locating a particular entry in the kernel’s mapping database based on its virtual address in the address space. In L4Re, this database is organized as a depth-first linked list of mappings that reflects the inheritance tree of a frame. Consequently, the time required to find a mapping ($t_{\mathrm{lookup}}$) is not necessarily constant: It grows with the number of entries that precede the target mapping in the list – not only its depth in the inheritance tree. For the purpose of estimating unmap system call latency, we therefore made a simplifying assumption: Every accounted mapping resides at a fixed inheritance depth and no ancestor has any other child. This assumption is reasonable for the isolated process group scenarios that motivate our work; the memory manager can enforce this requirement by issuing mappings only from a predetermined depth in the inheritance hierarchy of each frame.

The assumption does impose a restriction on how the memory service may hand out mappings. If the service were to allocate the same physical frame to several process groups, e.g., to share a library or a zero page, then the inheritance tree would contain multiple top-level siblings and the lookup cost would no longer be constant. Future work can address this issue in two ways: An ad-hoc solution that avoids performance interference is to eagerly copy shared resources into distinct frames for each group – thereby preserving the constant-time lookup property. A more general solution has to implement a constant- or logarithmic-time lookup from a page-table entry to the corresponding mapping-database entry (e.g., by employing a maple tree in a similar way like Linux uses for virtual memory area lookups [32]).

A second limitation arises from the locking discipline employed by L4Re’s mapping database. When a frame’s mapping tree is traversed or modified, the kernel holds a lock on that specific tree. Consequently, an unmap request issued by the memory allocator may have to wait for another process that currently holds the lock to finish its operation. The waiting time, fortunately, is bounded: The lock-holding thread performs at most one operation per mapping-database entry and the total number of entries it may touch is already accounted for in the reclamation quota. Hence, any additional latency introduced by a locked frame is proportional to the reclamation budget that has already been granted to the process group. Assuming that the memory allocator has the higher scheduling priority, the unmap system call of the memory allocator should continue right after the lock is released by the offending application. In future extensions, Brumm could explicitly model these lock-induced delays by analyzing the code paths that may retain a frame lock and adding the corresponding worst-case latencies to the reclamation time estimate.

Finally, a production-grade implementation would also have to account for the overhead incurred by the controller that initiates reclamation and by the memory allocator that finally frees the reclaimed pages from its internal data structures. These costs are highly dependent on the concrete use case (e.g., the size of the allocator’s bookkeeping structures or the communication mechanism between the controller and the memory service). We therefore omitted these latencies from the prototype evaluation. We leave a systematic treatment of these additional latencies to future work, as they do not affect the fundamental feasibility of bounded user-space memory reclamation demonstrated by Brumm.

The general idea and most of the implementation of Brumm is already applicable to multi-core use cases. We can already support application threads running and using the reclamation latency accounting in the kernel’s memory subsystem on multiple cores in parallel, as shown by our multi-core overhead benchmarks in Section 5.4. The quota object already uses atomic instructions at the appropriate places. We generally assume that only a single thread is doing the cleanup as it is already inherent by the unmap system call of the L4Re microkernel. Because the Brumm quota object supports locking (see Section 4.2), it cannot happen that the quota is used by an application for new mapping database entries while a reclamation/unmap operation by the memory service is in progress. However, there are still some specifics that need to be considered when assessing the sub-operation latencies for the quota predictions. Importantly, inter-CPU translation lookaside buffer (TLB) shootdowns are rather slow [34] and can drastically increase the latency of an unmap system call. These shootdowns – and the associated inter-processor interrupts – are required after removing page table entries to ensure that no TLB on any involved CPU still has stale entries for these page translations. Thus, future work on the Brumm implementation will have to consider the worst case for TLB shootdowns: How long could a full TLB shootdown take that is performed on all CPUs that the to-be-reclaimed memory was used on? Overall, there is still some work to be done on the side of latency predictions and performance evaluation to fully support multi-core workloads. Nevertheless, our approach is clearly applicable to multiprocessing systems.

The capability system of the seL4 microkernel [9] is comparable to the one of L4Re. Both have capability derivation trees, i.e., they support delegation and inheritance, for access permissions to page frames [33]. It should be possible to implement the design of Brumm analogously in the seL4 microkernel. seL4 would even allow us to elevate the Brumm design to a more generic kind of memory resource: untyped memory. This kind of kernel object represents main memory, which the system can split, use for kernel objects, or utilize in user space. Implementing a reclamation latency budgeting mechanism for untyped memory would yield predictable cleanup times for all kinds of memory usage in the system. However, the implementation of an accounting system would likely be far more involved because untyped memory can hold all kinds of kernel objects present in an seL4 system. Furthermore, a Brumm implementation on seL4 could make use of existing work on statically analyzing the WCET of kernel operations [5]. This could help to find guaranteed WCET bounds for the sub-operations in the memory reclamation path of the kernel.

Brumm is less applicable to the monolithic Linux kernel. Linux has no capability system for applications’ memory; i.e., it is not possible to recursively revoke handed-out shared memory in Linux. The ownership of memory pages is not clearly defined in Linux: For example, the decision which cgroup is charged for memory shared between multiple cgroups is in-deterministic [30]. In general, Linux does not provide a mechanism to reclaim mappings of individual physical frames as many microkernel do. Instead, Linux relies on the out-of-memory (OOM) killer to terminate processes that hold on to memory. Thus, one possible way to reclaim handed-out anonymous memory is to terminate a subordinate process group, for example, by terminating a whole PID namespace [29] or relying on the cgroup’s OOM killer [30]. Instead of focusing on user-space memory reclamation like in Brumm, one should instead perform reclamation latency accounting for the termination of entire process groups. This is similar to the design idea of our prior work [21], i.e., considering the cleanup latency of all kernel objects, which we realized on the M3 microkernel [3]. However, implementing such an all-encompassing reclamation accounting in the large, monolithic Linux kernel is presumably very invasive.

Overall, the idea of Brumm is most applicable to kernels with memory capabilities or hierarchical memory mapping databases as reclamation latency accounting can follow these data structures. Nevertheless, the more general concept of reclamation latency budgeting for cleanup operations is universally applicable as long as there is any form of resource grouping, such as capability derivation subtrees or cgroups.