Microkernel Construction Lecture Notes

Monolithic operating system kernels abstract from the hardware and offer more convenient services such as threads, address spaces, files, synchronization primitives, ... to applications. New features are added by adding code to the kernel, which leads to code size explosion, e.g. in the Linux kernel. In order to fulfill physical memory management tasks, fair scheduling, and hardware management tasks, monolithic kernels have all their code execute in the privileged processor mode. Hence each subsystem (file system, networking stack, ...) and each driver must be fully trusted, as malicious or faulty code can affect the whole system.

Another problem with monolithic kernels is their poor maintainability: As all subsystems share the same binary, it is easy to take shortcuts and directly access data structures of other subsystems from anywhere. As a consequence, changing the structures can require changes throughout the kernel and thus hampers development.

If the subsystems had clean interfaces, whose use would be enforced by the compiler (layered, modular, or object-oriented kernels), at least the second problem (maintenance) could be solved, but the first one (robustness) still remains as long as all submodules share the same address space.

The goal of microkernel-based operating systems is to minimize the amount of code that is executed in the privileged processor mode. For this purpose, each driver and each convenience OS subsystem is moved into an unprivileged user-level application, a so called server. Only a slim layer beneath the servers executes in privileged mode and only deals with safety critical tasks such as granting access to physical memory/devices, routing interrupts to the appropriate driver, and communication between the threads/address spaces.

Such a scheme would allow to execute multiple operating systems on top of the microkernel at the same time (virtualization), run special services directly on top of the microkernel (no high-level OS involved), or provide real-time services next to general purpose services without having to port the latter to a real time-capable OS.

Due to the separation of the subsystems and drivers into different address spaces, clean interfaces are required and enforced by offering only a limited communication API. As a consequence, both the robustness of the resulting system as well as its maintainability should improve compared with the monolithic approach.

However, early microkernel-based OSes such as IBM's Workplace OS and early microkernels such as Mach uncovered a significant performance penalty due to the dramatically increased number of context switches: Instead of referencing data structures in some submodule, microkernel-based systems need to issue a request-IPC to the server, switch to its address space, probably copy the requested data into kernel buffers and/or the client's address space, switch back to the client's address space, and finally access the data.

Two lessons are to be learned from these projects: Communication across address space boundaries is the most frequently used service in microkernel-based systems and, consequently, this operation must be as fast as possible. The whole microkernel must be designed to allow for really fast IPC. To achieve this, the target architecture must be carefully analyzed for possible performance features (e.g., sysenter/sysexit on x86) and bottlenecks (avoid slow DRAM accesses, obey cache structure during layout of the central data structures, avoid mandatory TLB flush on context switch if possible, minimize kernel impact on branch prediction logic, ...).

The L4 microkernel, which is the basis for this lecture, was designed from scratch (rather than stripping existing systems down) and implemented to provide fast IPC. It offers two abstractions: Threads to abstract from the CPU, and address spaces to protect threads against each other. In order to be able to manipulate these abstractions, the L4 kernel also provides two mechanisms: inter-process communication (IPC) allows threads to communicate and to synchronize, whereas mapping allows to recursively populate address spaces.

The kernel maps all hardware properties to these abstractions: All activities (including I/O devices) are represented in threads, interrupts are transformed into an IPC from the device thread to the driver thread. Pagefaults are wrapped into a pagefault IPC from the faulting thread to another thread that is responsible for providing memory (a so-called pager), and (physical) memory is given to an address space by mapping memory from the pager (the pager itself requests the memory from its respective pager, the root pager idempotently maps physical memory to its clients on demand).

These two abstractions (threads and address spaces) are just one of potentially many valid choices. However, the provided abstractions should be chosen so that everything that needs to be managed in privileged mode for reasons of

is managed by the microkernel (in privileged mode), and everything else is delegated to unprivileged user-mode tasks.

An additional criterion is to avoid duplicated functionality in the kernel: There should always be exactly one way to do a job, no more and no less. As a consequence, all abstractions and mechanisms must be general enough to allow all desired uses. On the other hand, all abstractions and mechanisms must be orthogonal, so that none can be emulated using the others (no superfluous abstractions or mechanisms are allowed inside the microkernel ^[1]).

To this end, threads must be represented by a data structure that can hold all the CPU state, including the current instruction pointer, the stack pointer, the contents of general purpose registers and special purpose registers (e.g., floating point or status registers) contents. Additionally, to enable controlled switching between threads (scheduling), scheduling parameters such as thread priorities, time slice lengths, and thread status (e.g., running, ready, blocked, invalid) are also required. All this information is stored in so-called TCBs, which will be discussed in more detail in Chapter 4, TCBs.

Switching threads is conceptually easy:

However, two problems arise: First, TCBs must be protected kernel objects, so that no thread on user-level can manipulate other threads' states. Furthermore, threads must not be allowed to modify even their own TCB, if/as the TCBs contain scheduling information (e.g., the remaining timeslice length).

As a consequence, thread switches must (most of the time, see Chapter 10, Local IPC) be performed by the kernel, which means that the kernel must run in order to do so. If the kernel is running, the user-level state of the thread must be preserved somewhere in order to be able to correctly resume it. For this second problem, some hardware support on entering the kernel is required: On kernel entry, the user-level CPU state could be saved on a stack (x86), or the kernel can use a different set of CPU state (register banks, found in MIPS or Itanium machines).

On stack-based machines (x86), a thread switch thus requires the following steps:

Concerning the stack being used in kernel mode, different models are possible. The kernel stack should always be different from the user-level stack for security reasons: First, the user can set up an invalid stack pointer before entering kernel mode, loading a well-known, valid stack pointer on kernel entry is likely to be easier than validating the current value. Secondly, the kernel entry might be caused by a page fault on the user-level stack. Storing user-level state on this stack in order to handle the page fault will thus raise further page faults (accesses the same non-mapped memory) which can never be handled.

The presented models differ in the number of kernel-level stacks.

Code to cooperatively switch threads in kernel mode on x86:

/* save all registers on the stack */
pusha

/* compute TCB address of current thread
 * (esp already points to the end of the TCB,
 * i.e., the top of the kernel stack)
 */
mov     esp, ebp
and     -sizeof_tcb, ebp

/* assume: edi = address of TCB of B */
mov     esp, TCB_Off_esp(ebp)
mov     TCB_Off_esp(edi), esp

/* setup kernel stack for next kernel entry */
add     sizeof_tcb, edi
mov     edi, 0(esp0_ptr)

/* restore all registers from the stack */
popa

Intel traditionally offered the int n instruction to allow software interrupts, which are handled exactly like hardware interrupts: When the user executes the int instruction, the hardware

After this, the handler function can store the remaining registers on the kernel-level stack and call a C-function to implement the requested service. Having completed the request, the kernel restores the user-level registers (or stores results in there, depending on the API/ABI), and returns to user-mode using the iret (return from interrupt) instruction, which atomically pops the user-level %eip/%cs and the %esp/%ss pairs as well as the flags from the kernel stack and enables interrupts again.

The int instruction is easy to use, as the kernel needs to handle interrupts anyways (at least timer interrupts for time-sliced, round robin scheduling and inter-processor interrupts for inter-processor IPC), so the infrastructure is there already.

On the other hand, using int is quite slow, especially due to the memory lookup of both the kernel stack pointer (%esp0) and the entry point of the handler routine in the interrupt descriptor table (IDT). As kernel entries/syscalls are frequent (especially in microkernel-based systems), Intel introduced a less costly alternative kernel entry facility via the sysenter/sysexit instructions. ^[4]

These new instructions avoid memory lookups by providing CPU-internal special purpose registers (model-specific registers, MSRs) to store a single entry point into the kernel as well as a single kernel stack pointer to load on kernel entry via sysenter. Furthermore these instructions effectively disable segmentation by setting up flat segments (full 4 GB segments starting at linear/virtual address 0), which allows to skip additional costly segmentation-related checks on mode changes between kernel-mode and user-mode. As most of today's operating systems (including L4) ignore segmentation and use flat segments already (using only paging for access control and physical memory management), this is usually not a problem (but see Chapter 9, Small Spaces).

As sysenter always jumps to the same handler routine in the kernel, an argument (a register) would be required to select one of the syscalls offered by the kernel. Instead of sacrificing a register for this purpose, L4 implements only the most frequently used system call, namely IPC, via sysenter, all other system calls use the traditional kernel entry method via int and either have an explicit argument denoting the system call number or use different interrupt vectors (int 0x80, int 0x81, ...) for the different system calls.

As L4 aims not only at maximum speed but also at portability, systems without the (relatively) new sysenter instruction shall also be supported and the optimal method of entering the kernel shall be selected at runtime. A problem here is that the stack layout after kernel entry via sysenter differs from the layout after using int: Using sysenter, the hardware only

Nothing is stored on the stack, the user-level instruction pointer and stack pointer to use when returning to user-level must be passed in registers (by convention and because sysexit expects them there, %eip is passed in %edx and %esp in %ecx).

In order to obtain a stack layout that matches the int entry path, the sysenter handler (in the kernel) first stores the user %eip (passed from user-level in the register %edx) and the user %esp (from %ecx) as well as the error code ("IPC syscall") on the stack at the "correct" locations. The segment registers (%cs, %ss) are always flat and thus need not be stored (they are still correct and in place since thread creation), and the flags are undefined after the IPC syscall as per the microkernel API and thus need not be stored as well.

mov     (esp), esp              /* load esp from TSS.esp0 */
sub     $20, esp                /* create interrupt frame */
mov     ecx, 16(esp)      /* store %esp and %eip where... */
mov     edx, 4(esp)         /* ... the HW would have done */
mov     $5, (esp)                 /* indicate IPC syscall */

Having set up this stack frame, the sysenter handler can jump right to the int entry code to handle the rest, thus enabling faster kernel entry and compatibility without any code duplication.

A similar problem arises for threads that execute in virtual x86 mode (real mode): Whenever they cause a kernel entry/exception, all segment registers are pushed onto the kernel stack before setting up the regular exception frame. To accommodate for this, L4 makes %esp0 point to the real top-of-stack only before switching to a virtual x86-mode thread; in all other (the usual) cases, %esp0 points to 4 words before the top-of-stack, effectively pretending the next kernel entry would have pushed 4 nonsense words before its stack frame. This allows to address, e.g. the user-level return address (%eip) at a fixed offset in the kernel stack under all circumstances and thus simplifies the kernel code by avoiding special cases.

The return path via sysexit has to load the user-level %eip and %esp (from the stack) into %edx and %ecx respectively and must enable interrupts prior to issuing the sysexit instruction. All of this plus segment register reloading and checking would also be done by the iret instruction on the traditional exit path, but much slower.

mov     16(esp), ecx    /* load %esp and %eip from where iret would */
mov     4(esp), edx
sti                              /* enable interrupts as iret would */
sysexit                                      /* return to user mode */

In normal (i.e., expected) use, TCBs have to be located for three reasons:

mov     thread_id, eax
mov     eax, ebp
and     mask_thread_no, eax
add     offset, eax

cmp     TCB_Off_Myself(eax), ebp
jne     invalid_thread_id

mov     thread_id, eax
mov     eax, ebp
and     mask_thread_no, eax
shr     threadno_shift, eax
add     offset, eax

cmp     TCB_Off_Myself(eax), ebp
jne     invalid_thread_id

mov     thread_id, eax
mov     eax, ebp
and     mask_thread_no, eax
mov     thread_table(4*eax), eax

cmp     TCB_Off_Myself(eax), ebp
jne     invalid_thread_id

The TCB array with its 256k entries of 2 kByte each requires 512 MB of memory. For obvious reasons, the microkernel should not claim 512 MB of physical memory from the start on but should rather grow only on demand. Thus the TCB array is allocated only in virtual memory. The first access to a page in the TCB array will cause a pagefault, which is handled specially by the kernel:

This is a variant of the copy-on-write scheme, which saves memory even if a malicious user-level thread probes every thread ID in the system; there will only be a single physical frame mapped multiple times into the TCB array. The initial pagefaults can be avoided by premapping the 0-filled page to back the whole TCB array. Afterwards, only the first TCB modification on each page will cause a pagefault.

	This scheme works both for standard (4 kB) pages and for superpages. If the TCB array should be backed with superpages, still a small 0-filled page can be used to back the unused parts. However, simplicity dictates that the first write requires a superpage to be mapped (otherwise physical memory management, which aims at allowing later promotion to superpages, becomes veeeery difficult)!

In the indirect TCB addressing scheme, the lookup table should not be backed by a shared 0-filled read-only frame, but rather by a dedicated, writable frame containing the virtual address of the first TCB in every word: As long as the first TCB is read-only mapped to the 0-page, all accesses to any TCB will fail at the validation of the thread ID. Once the first TCB is allocated (and thus mapped to a writeable page), all invalid acceses will still fail the validation procedure (the requested thread ID does not match the thread ID in the first TCB). This guarantees that reading from the lookup table always yields a valid pointer into the TCB array, thus avoiding additional checks (the 0-page would yield NULL-pointers, which would have to be checked for). If the lookup table is integrated into the superpage that also stores the initial portion of the TCB array, this page must still be allocated exclusively and writable from the beginning; only the remaining parts of the TCB array can/should use the 0-mapping trick as described earlier.

Having proposed to dedicate 512 MB of virtual address space to TCBs, this is the right time to look at the address space layout to show how this fits in. Generally, there are two possible approaches to store the kernel code and data: One can use an address space dedicated to the kernel, which would require an address space switch whenever a user-level thread invokes a system call, or one can split the 32 bit (4 GB) virtual address space into a user region and a kernel region. As address space switches are comparatively expensive on the main target platform (x86) due to untagged TLBs (also see Chapter 9, Small Spaces), logically splitting the address space is the preferred way to go.

When implementing communication primitives, one fundamental design decision has to be made: Shall the sender block until the IPC operation returns (successfully or not) or shall the sending thread continue immediately and let the kernel deal with the actual message transfer?

The latter case (asynchronous send) usually requires

Buffering messages in the kernel makes the kernel vulnerable for denial-of-service attacks (e.g., by letting threads send messages that will never be received). Furthermore, copying the messages twice not only wastes processor cycles, but also increases the kernel's cache (and probably TLB) footprint.

Assuming that IPC is the most frequently invoked microkernel service, L4 implements only synchronous IPC, which allows to keep the message in the sender's address space until it can be copied to the receiver. This scheme avoids both the in-kernel buffers and a second copy of the message plus the sender can be informed about success or failure when the IPC operation returns.

For message-based communication, at least two primitives are required:

These operations allow for two threads to communicate with each other and prevent interference from other threads: The receiver only accepts messages from the intended sender, aka closed receive). Other threads must wait until the receiver accepts messages from them. However, servers that offer their services to all threads are difficult to implement using the closed receive primitive for two reasons:

Avoiding these problems, the kernel should offer an additional primitive (known as an open receive):

Looking at the (expected) common interaction patterns in a multi-server system, clients will typically send requests to servers and then wait for the answer (cf. RPC). If in such a scenario the client is preempted after having sent the request but before having issued the accompanying receive, the server might try to deliver the result (answer message) to the client before the client is receiving. As a consequence, the server would block and thus be prevented from servicing other requests. To solve this problem, two approaches can be considered:

Combined send-and-receive primitives could be:

	call is the typical client-side primitive when requesting a service, whereas reply-and-wait would be the primitive most suitable for the server (send answer to client A and wait for requests from any client). The third combination has yet to proof its worth, but comes for free (see the section called "Operation and Addresses").

Depending on the size of the messages to be transferred, we can distinguish three message types:

	Besides memory pages, other resources can be mapped as well (e.g., access to I/O ports on IA32).

The distinction becomes important when implementing the IPC primitives, as we shall discuss in Chapter 6, IPC Implementation.

In order to enable threads to recover from a (blocking) communication attempt with an unresponsive (malicious, faulty, or uncooperative) partner, the duration of each IPC operation can be bounded with a number of timeouts.

For every IPC operation, a number of parameters such as the intended receiver, the type and contents of the message and the desired operation (send, receive, call, ...), or the desired timeouts (if any) must be specified. Clever encoding of these can avoid superfluous memory accesses and thus help to make IPC fast.

Message Content

The message itself is stored in 64 word-wide virtual message registers (MR₀ .. MR₆₃), each of which is realized either in a physical processor register or in a thread-local region of memory (see the section called "Virtual Registers and the UTCB").

The message itself consists of a message tag in MR₀, followed by 0..63 untyped words (which are simply copied during an IPC), followed by 0..63 typed words. Typed words (or typed items) are interpreted by the kernel and serve to encode strings and mappings.

String Items

String items instruct the kernel to copy a contiguous region of memory (a "string") from the sender's address space to the receiver's address space. To this end, string items must convey

• the length of the string (in bytes) and
• the start address of the string in the sender's address space.

The first word in a string item ( string specifier) consists of the following fields:

continue bit (C, bit 0)

The least significant bit is set to indicate that another typed item follows after the string item.

cacheability hints (hh, bits 1..2)

The next two bits can be used to instruct the kernel to bypass the L2 and or L1 cache when copying (if supported by the hardware).

type bit (bit 3)

The next bit is 0 to indicate that this is a string item (map and grant items set this bit to 1).

number of substrings - 1 (N, bits 4..8)

Each string item can specify up to 64 start positions of substrings of the same size. Together with the same property of receive string items, this allows to efficiently encode scatter/gather string IPC.

compound string bit (c, bit 9)

Indicates that another string item follows and is to be considered to be part of the same string (allows scatter/gather strings with substrings of different sizes).

length of substrings - 1 (bits 10..31/63)

The remaining bits in the string specifier specify the length of the substrings in bytes. As 0 byte long strings would be useless, the "length - 1" is stored, allowing up to 4 MB of data per substring (on 32 bit systems).

The N+1 words that follow the string specifier denote the start addresses of the substrings, which need not be aligned and thus require a full word each.

Map Items

Map items enable the sending thread to establish a region of shared memory with the receiver. In order to allow the mapper the restrict access from the "mappee" to the memory (e.g., read only), map items must specify

• the start address and length of the virtual address region to share and
• the rights to be granted to the receiver (e.g., read-only).

Since multiple map items should be allowed in each message, but only a single receive window can be specified by the receiver (arbitrarily large, but only one, see the section called "Receive Buffers"), each map item also specifies an offset within the receive window.

All this is encoded in two words. The first word of a map item consists of:

continue bit (C, bit 0)

The least significant bit is set to indicate that another typed item follows after the string item.

type bits (bits 1..3)

Map items are identified by the value 4 (0b100) here. (Grant items require a value of 5 (0b101), string items use 0b0hh.)

reserved bits (bits 4..9)

Must be 0 for now.

send base address (bits 10..31/63)

The remaining bits specify the 22 or 54 (on 64 bit systems) most significant bits of the offset in the receive window (see Chapter 8, Virtual Memory Mapping). As fpages cover at least 1024 = 2¹⁰ byte and must be naturally aligned, the unspecified least significant 10 bits must be 0 and need not be stored.

Grant Items

Grant items allow to map an fpage and to remove it from the sender's address space, the fpage is effectively moved to the receiver's address space.

In their encoding, grant items differ from map items only in the first bit of the type field (bit 1 of the send base): Map items set this bit to 0, grant items set it to 1.

	The effect of the grant operation cannot be achieved with any series of map and unmap operations and is thus a required additional, not a redundant operation (also see Chapter 8, Virtual Memory Mapping for the effects of grant on derived mappings and the mapping database).

Message Format

In order to properly decode the message, the first message register (the message tag) always provides some meta-information about the remaining message:

number of untyped words (u, bits 0..5)

The number of untyped words following the tag. These are copied during IPC but not interpreted by the kernel.

number of typed words (t, bits 6..11)

The number of typed words (not items), that (always) follow the untyped words. These are interpreted by the kernel and trigger string copy, map, or grant operations.

flags (bits 12..15)

The flags in the message tag are used to signal the use of a kernel-based IPC control mechanism (IPC propagation or IPC redirection), indicate inter-processor IPCs, and to store the error indicator after the IPC.

The flags are typically set by the kernel for inspection by the receiver and the sender (error bit).

label (bits 16..31/63)

The remaining bits in the message tag can be used to transport the first bits of data to the receiver. The kernel uses the label to label synthesized messages (page fault IPC, exception IPC, ...), so that a single thread can be both the pager and the exception handler of another thread.

As the message tag describes the message, it must be inspected on every IPC and should thus be passed to the kernel in a register rather than via memory.

	The following elaboration mainly focuses on single-processor systems, i.e., only one thread executes on the CPU at any time. Furthermore, we assume a strict priority-based scheduling strategy with fixed priorities and round-robin per priority level as provided by L4 (see Chapter 7, Dispatching), though the ideas presented should apply more generally as well.

The implementation of synchronous IPC primitives (send, receive, and combined operations such as call or reply-and-wait) are tightly related to scheduling: Whenever a thread waits for an IPC partner (trying to send to a thread that is currently not accepting messages, or trying to receive a message while none is pending), the thread is blocked and another thread needs to be scheduled.

Conversely, if the send phase of a call operation completes, the sender will wait for the response of the receiver. This (common!) case can be improved by avoiding to go through the scheduler and instead dispatch the receiver thread directly, allowing it to use the remainder of the sender's timeslice to start fulfilling its request. Executing the receiver in the sender's timeslice is called ((timeslice donation)); the sender would block anyway (after the call), but instead of losing its assigned CPU time, the sender passes it on the receiver so that the latter can do some work on the sender's behalf.

This approach is fair in all respects if the sender used the call primitive:

Besides a call to a waiting receiver, other (attempted) IPC operations also require dispatching/scheduling actions:

IPC operations that only transfer messages in the message registers (no strings, no mappings) are called short IPC. Under the assumption that call style IPC is prevalent in microkernel-based systems and that the receiver (often a server) is waiting, such a short IPC can on uni-processor machines be implemented via a (simplified) thread switch, carrying at least part of the message in the register file as follows

Short IPC, meaning IPC with its message solely contained in untyped message registers without strings or mappings, is (assumed to be) the most frequent kernel operation in microkernel-based systems. This justifies taking special care on its implementation to avoid most of the possible performance problems (cache misses, TLB misses, memory references in general, down to microarchitectural effects such as pipeline stalls and flushes or instruction scheduling; the latter shall not be discussed here in more detail).

In order to retain in full control over these effects, L4 features two IPC paths:

The selection between the two IPC paths is made at the beginning of the IPC entry point by checking the above criteria. If any criterion for the fast path is violated, the code branches off to (calls) the C code, otherwise the fast path is used.

Long IPC denotes all IPC that includes string items or map/grant items, i.e., typed items. The complexity of these operations in conjunction with accessing the required data structures makes an assembly "fast path" implementation infeasible. Additionally, due to the string copy or pagetable manipulation, the cost of long IPC are generally so high that such a fast path would not pay that much and is thus not provided (also saves maintenance overhead).

Long IPC requires the following steps:

We want to enable interrupts during string copy operations in order to keep the interrupt latency low: Each string can be up to 4 MB in size, the pure copy time approaches the length of a timer tick (order of milliseconds). We must disable interrupts afterwards as the thread switch and other kernel code assumes atomicity.

We must allow for pagefaults to be handled during string IPC, which requires that we prevent the reactivation of any of the partners. Otherwise another thread might concurrently be allowed to send a message to the receiver, partly overwriting its message registers and wreaking havoc. The sender must not continue before having sent the message so that it cannot mess with its message registers (besides other reasons).

The approach taken by L4 to avoid such problems is to lock both partners' TCBs while the interrupts are still disabled. Locking simply means to set their thread states to locked_running (sender) and locked_waiting (receiver), which are different from both ready/running and waiting and thus prevent anyone from communicating with or dispatching these threads.

We defer a detailed description on mapping IPC until Chapter 8, Virtual Memory Mapping to present it in its natural context, so that the remainder of this chapter will focus on string IPC. Also keep in mind that this description of the IPC operations disregards the multi-processor case and thus ignores the additional SMP-safe locking requirements on accessing TCBs and such. The L4 implementation is SMP safe.

String IPC provides a means to safely (guarded by the kernel) copy large amounts of data between address spaces. Though not strictly required (short IPC would suffice), providing string IPC offers a much more comfortable and more efficient solution to this task than short IPC could do while still keeping many of the IPC properties: synchronous, atomic message transfer (the sender continues only after the message has been transferred completely) from sender defined data into memory locations that are designated as such by the receiver. Furthermore, kernel-mediated string IPC guarantees that the originator of the accepted string data is known, as the sender's true identity (thread ID) is conveyed to the receiver during the IPC (a matter of trust).

On multi-processor machines, each CPU should be able to perform a string IPC in parallel with all other CPUs. A single temp. mapping area in the kernel, however, would prohibit such parallelism and instead require locking and synchronization on the shared resource "mapping area".

As a workaround, each CPU can be given a private temp. mapping area in a distinct region within the kernel memory space. In effect, this approach allocates not one but N (the number of CPUs in the system) mapping areas in the kernel, each one being used exclusively by one CPU; no additional locking to access the mapping area is required. However, this approach requires to limit the max. number of CPUs at compile time so that the kernel memory regions can be reserved. If the kernel is compiled for up to 32 CPUs but only 2 are present, 30 x 8 MB of virtual kernel memory are wasted. What's more, this approach does not scale well to larger, many-core systems with 100s or CPUs: one cannot dedicate 100 x 8 MB of the 1 GB of kernel memory to mapping areas!

As an alternative, L4 uses CPU-local memory: Each CPU has its own copy of the top-level pagetables and can thus establish its own temporary mapping area without disturbing the other CPU's mapping areas. This approach not only scales better (you just need to duplicate the top-level pagetable (4 kB) instead of the mapping area (8 MB)), but also restricts the mapping area to the same virtual addresses on all CPUs, which makes programming easier (instead of using map_area[get_current_cpu()] you can now simply access map_area from all CPUs and still have it map to different receive buffers on each CPU).

Whenever L4 must choose the next thread to run, it consults its built in scheduler. The scheduler uses

In principle, the scheduler starts at the array entry for the highest priority and checks if there is a thread ready to run (array entry is not nil). In this case, the thread is selected for dispatch, otherwise, the array is searched in order of decreasing priorities. If no thread is ready to run, a special idle thread is dispatched.

When the current thread blocks, yields, or exhausts its timeslice, the next thread in that priority class is dispatched and given a new timeslice. Additionally, the pointer to the currently running thread in the array is updated to point to the selected thread.

Timeslice accounting is slightly inaccurate as it happens in the handler of the periodic timer interrupt by subtracting the length of the timer period from the remaining timeslice length. If the remaining timeslice becomes zero or negative, it is said to be exhausted, causing an immediate scheduling process. If the thread blocks in between two timer ticks, the next thread will start with only half a timer period till the next timer tick. Whether it is billed a whole timer period or whether this case is correctly accounted for is beyond the author's knowledge.

Usually, threads have priorities around 100 on L4. To avoid checking the priority levels 255..101 for runnable threads, L4 remembers the highest priority with a runnable thread and only checks at and below that level during scheduling.

This so-called "highest active priority" must be updated whenever a thread with a higher priority becomes ready to run, and should be updated whenever the currently highest active priority level becomes empty (because the last thread on that level blocks). Both events can easily be registered in the kernel.

On x86, further optimizations are possible for sparsely populated priority arrays: x86 offers a bsr (bit scan reverse) instruction, which can be used to locate the index of the most significant set (1) bit in a word. If we maintain an bitfield of 256 bits (8 32-bit words), i.e., one "active" bit per priority level, we can use this instruction to locate the highest active priority without searching the array at all.

The current implementation always folds 16 priority levels into one bit, reducing the length of the bitfield to search to 16 bits. This approach requires to scan up to 15 (empty) arrays entries in the order of decreasing priorities to identify the real highest active priority and complicates the conditions under which a bit can be cleared. The reasons for not using 32 bits are unclear, there is even no apparent benefit of using only one word instead of 8: Both cache utilisation and TLB coverage would favor the 256 bit bitfield, no difference with respect to branch prediction logic is obvious.

Finding the next thread to run can be quite time consuming (esp. if no bsr instruction can be used) and should thus be preemptible itself, in order to achieve a low interrupt latency. If the scheduler were to execute in the context of the current thread (the one that is to be replaced), this goal would be hard to achieve: On interrupts, the current state of the interrupted thread would be saved, the (in-kernel) interrupt handler would still execute on the stack of the current thread and possibly invoke the scheduler again. When the current thread is scheduled again, it would resume its preempted scheduling activity, although the thread itself should continue! Additionally, the interrupt handler and nested scheduler consume space on the threads kernel stack, which, being included in the TCB, is quite limited.

Solving all these problems, L4 uses a dedicated thread for the scheduling decisions. This thread is never resumed after preemption but rather started anew, discarding its previous state (the scheduling-relevant data structures have possibly changed since the scheduler has been preempted, so a fresh start is recommended). This property also removes the requirement for an exceptionally large kernel stack; except for a single interrupt handler, nothing will be nested on top of the scheduler.

The consequences of this model are that dispatching via the scheduler requires two thread switches: first from the current to the dispatcher thread, and then from dispatcher to the next thread. However, as the dispatcher never executes in user mode, it does not have an associated address space, so that switching there is cheap (no address space switch, no TLB flush). As it is never referenced from user mode, it can even do without a thread ID, which further allows to freely place (and size) its stack; it need not be included in any TCB.

L4 uses circular ready lists per priority level. If these lists were maintained eagerly, a thread would have to be removed whenever it blocks (e.g., during a call IPC, waiting for the reply). Removing a thread from the ready list requires touching its preceding list element (to update its next pointer) as well as touching its successor list element (to update its prev pointer) in addition to the list element itself. With the list being embedded in TCBs, this translates to having to touch three TCBs (predecessor, successor, and current), each one probably covered by a different TLB entry. Though we cannot avoid touching the current TCB, and though we will probably switch to the next thread anyways, so touching the successor list element does not "waste" a TLB entry for the single purpose of updating the ready list, touching the predecessor TCB solely serves the purpose of keeping the ready list up-to-date. The possible TLB miss on touching the predecessor TCB can be avoided by maintaining the ready lists lazily as follows.

Instead of removing a blocking thread's TCB from the ready list immediately, we just leave it in there and simply set its state to blocked. If a thread that is selected for dispatching is marked as blocked, we remove it from the list and dispatch the next thread. This lazy handling of ready lists is called lazy dispatching.

... and what does this scheme buy us?!?

Threads that are blocked during IPC can be unblocked either by completing their IPC (partner arrives and accepts/delivers a message) or by aborting it due to a timeout. With many blocked threads in a system it would be infeasible to check all blocked threads' timeouts on each timer interrupt (aka tick). Instead, L4 maintains a (more or less ordered, see below) list of timeouts, with the one closest to its expiry at the head of the list. This only requires to check a single timeout at each tick (and would even allow tickless implementations, setting the timer to min(timeslice length, earliest timeout) on each kernel exit), but requires a clever data structure to keep track of the timeouts.

Since timeouts could be created with every IPC, inserting them into the "list" must be fast. Under the assumption that most timeouts are never actually raised (they are usually used to recover from error conditions/deadlocks/false assumptions; under normal conditions they are cancelled once the IPC completes), canceling a timeout must also be cheap. With the same argument (raised timeouts indicate some error in the application), handling an expired timeout may be more expensive.

Both unsorted and sorted true lists do not meet our requirements: Unsorted lists take O(n) time to find the nearest timeout, sorted lists take O(n) time to insert a new element.

Using (balanced) trees to maintain the timeouts would probably allow cheap lookup/insert operations (O(1), O(log n)), but are deemed to be too complicated ^[8] and expensive (probably in terms of time (e.g., reorganizing an AVL tree) and memory (>= 3 pointers per tree node instead of 1 or 2 in lists)).

Anyway, an epoch-based multi-list scheme has been proposed for L4. ^[9] The idea is to define two absolute times on system startup, e_soon and e_late, with e_soon being several micro- or milliseconds from now on and e_late being approx. an order of magnitude later. We can now use an ordered list (aka soon list) for the nearly expired timeouts (those that fire before e_soon), an unsorted list (aka late late list) for timeouts in the far future (firing after e_late), and another unsorted list (aka late list) for timeouts in between the other two (at or after e_soon but before e_late).

Insertion into the sorted soon list is cheap because (hopefully) there is only a small number of timeouts stored in that list (e_soon should be chosen to maintain this property). Insertion into the unsorted late and late late lists is cheap because we can simply append (or prepend) new timeouts (O(1)). To facilitate quick removal of cancelled timeouts, we can store a pointer to the timeout list entry in the associated TCB (O(1)). As the current design precludes any thread from having more than one active timeout, we can even go further and include a wakeup list node in the TCBs (as is done with the ready lists as well), removing the necessity to store a pointer to the list node.

Once e_soon is reached, a correction phase is required (note that the soon list is empty at this time!): First, we define a new e_soon in the near future, then we iterate over the late list, moving all timeouts that fire before the new e_soon into the (sorted) soon list and continue.

Whenever we reach the updated e_soon, we process the late list as just described. Only once we reach e_late do we need to inspect the timeouts in the late late list; which we process similar to the late correction above: First update e_late, then iterate over all entries from the late late list and move them into the (sorted) soon list (if expiry is before e_soon) or the late list (if expiry is before e_late).

The epochs serve to reduce the sorting efforts (only nearly expired timeouts are sorted), the late list keeps the cost of the late correction phase small (if e_late is not too far in the future), and the probably costly late late correction phase handles the remaining (long-term) timeouts.

Note that the correction phases are only required once the current time exceeds e_soon or e_late: The insertion strategy guarantees that no timeout in the late or late late lists can be missed (all expiry times are later than e_soon or e_late, respectively).

As an additional optimization, we can reuse the lazy dispatching idea: Instead of removing the timeout list element when a timeout is cancelled, we can leave it in the list and just set its expiry time to never. Such items can be removed from the lists (at a low cost) during correction phases or can be reused for the next timeout iff it falls into the same late/late late list (the soon list must always be sorted).