DESCRIPTION

X15 is an open source real-time microkernel intended to provide a performant and scalable environment for cache-coherent multiprocessor machines.

Section 9 of the manual describes kernel interfaces, both internal and provided to application code hosted in kernel mode.

Among the features provided are :

Modules

The module is the functional unit around which kernel sources are organized. A single module is made up of at least one public header file. There is usually also an opaque implementation file. An implementation header can complement the module for inline functions and private structures allowed to be allocated from the stack. Finally, a type-only header can also be present in order to avoid circular inclusions.

The files of a module must strictly be named according to the module name. Here are the name patterns for each file of a module :

<module>.c

Opaque implementation.

<module>.h

Public header.

<module>_i.h

Implementation header.

<module>_types.h

Type-only header.

Components

Modules are grouped into components, with one directory per component. The main components are :

arch

Architecture-specific modules, located in arch/<arch>.

test

Test modules.

vm

Virtual memory system.

kern

Machine-independent modules that don’t belong in another component.

PREEMPTIVE MULTITHREADING

The X15 kernel provides threads which can be preempted at almost any time, in both kernel and user space. They have an associated scheduling policy and priority. Currently, the available scheduling policies are :

Fair scheduling (FS)

A non real-time, proportionally fair policy.

First-in, first-out fixed priority (FIFO)

A real-time, fixed-priority based FIFO policy.

Round-robin (RR)

A real-time, fixed-priority based policy with round-robin among same priority threads.

In addition, the kernel provides many thread synchronization facilities. The relevant modules are :

condition

Condition variable.

cpu

Architecture-specific processor interface which provides interrupt control functions.

mutex

Mutual exclusion lock.

rcu

Read-Copy Update (RCU) lockless synchronization.

semaphore

Semaphore.

sleepq

Low level sleep queue.

thread

Preemptive thread scheduling.

work

Work queue of deferred asynchronous lightweight jobs.

All wait functions on synchronization objects can be time-bounded. This includes waiting for a mutex lock, a condition variable, or a semaphore.

Mutex implementations

In order to best satisfy either overall performance or latencies, the kernel provides several mutex implementations for the interface provided by the mutex module. Note that, whatever implementation is selected, the rtmutex module is always available. The mutex implementations are :

mutex_adaptive

Adaptive spinning mutex, spinning instead of sleeping if the owner is running, in the hope the critical section is short and the mutex will be unlocked soon, to avoid expensive sleep/wakeup operations. This implementation should improve overall performance at the cost of increased latencies.

mutex_pi

Real-time mutex with priority inheritance. This implementation is a wrapper in front of the rtmutex module. It should improve latencies at the cost of overall performance.

mutex_plain

Default mutex, immediately sleeping on contention.

GENERIC DEVELOPMENT TOOLS

Along with the kernel sources are a set of generic data structures and other development tools :

bitmap

Arbitrary-length bit array.

bulletin

Publish-subscribe mechanism.

cbuf

Circular byte buffer.

clock

Low resolution clock.

error

Common errors and error handling functions.

hash

Hash functions for integers and strings.

hlist

Doubly-linked list specialized for forward traversals and O(1) removals.

kmem

Object caching and general purpose memory allocator.

list

Doubly-linked list.

macros

Useful generic macros.

perfmon

Performance monitoring.

rbtree

Red-black tree.

rdxtree

Radix tree (with integer keys).

slist

Singly-linked list.

syscnt

Generic 64-bits counter.

timer

Low resolution timer.

X15 doesn’t provide a generic queue interface, because the requirements often vary too much. Similarly, it doesn’t provide a hash table interface. Instead, users can easily build specialized queues, hash tables and ring buffers on top of the provided facilities.

See cenv(9) for information about the subset of standard C interfaces supported.

MULTIPROCESSOR SUPPORT

The X15 kernel is designed to support hardware with multiple processors. The scheduler should scale well up to 16-32 processors, with one run queue per processor. Threads can be bound to a specific set of processors, or temporarily pinned for short durations. Non real-time threads can be spontaneously migrated between processors in order to maximize processor utility.

Here are some modules related to multiprocessor support :

atomic

Inter-processor atomic operations.

cpumap

Specialized bitmaps representing processor sets.

percpu

Per-processor data.

spinlock

Inter-processor spin locks.

sref

Scalable multiprocessor reference counters.

thread

Preemptive thread scheduling.

xcall

Low level inter-processor function calls.

VIRTUAL MEMORY

TODO Write when the virtual memory system is rewritten.

REAL-TIME

X15 complies with all the requirements of a real-time multiprocessor system. It is a fully preemptible kernel with short, bounded preemption-based critical sections. It provides real-time scheduling policies and a complete priority inheritance algorithm. Preemption and interrupts are clearly decoupled so that interrupts can remain enabled as much as possible. Multiprocessor synchronization uses rigorously fair spin locks. The modules related to real-time are :

rtmutex

Mutual exclusion with priority inheritance.

spinlock

Inter-processor spin locks.

thread

Preemptive thread scheduling.

trap

Interrupt and exception handling.

turnstile

Low level priority propagation capable sleep queue.

Priority inheritance can also be enabled for regular mutexes. Please read Victor Yodaiken’s report Against Priority Inheritance in order to fully understand the implications of relying on priority inheritance.

TODO Separate man page with more description

PORTABILITY

Despite the fact that the kernel currently only supports the x86 architecture, which will remain the reference port, the code is already very portable, thanks to a clear separation between architecture-specific and machine-independent modules, as well as good programming practice, in particular regarding type widths, endianness, and memory models.

Ports are located in the arch directory. Here are the modules that must provide interfaces expected by the machine-independent layer :

atomic

Architecture-specific support for atomic instructions.

cpu

Processor interface.

pmap

Physical mappings, the MMU driver.

strace

Stack tracing.

tcb

Thread control block.

trap

Interrupt and exception handling.

The machine-independent code assumes either an ILP32 or LP64 data model, and a completely relaxed memory model as allowed by the C11 specification.

X15 currently requires a memory management unit, but that may change in the future.

SEE