path: root/doc/intro.9.txt

INTRO(9)
========
:doctype:       manpage
:man source:    X15
:man manual:    X15 Kernel Developer{rsquo}s Manual

NAME
----

intro - introduction to kernel interfaces

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 :

* <<preemptive_multithreading,Preemptive multithreading>>
* <<generic_development_tools,Generic development tools>>
* <<multiprocessor_support,Multiprocessor support>>
* <<virtual_memoru,Virtual memory>>
* <<real_time,Real-time>>
* <<portability,Portability>>

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]]
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 :

module:kern/condition::
  Condition variable.
module:arch/cpu::
  Architecture-specific processor interface which provides interrupt
  control functions.
module:kern/mutex::
  Mutual exclusion lock.
module:kern/rcu::
  Read-Copy Update (RCU) lockless synchronization.
module:kern/semaphore::
  Semaphore.
module:kern/sleepq::
  Low level sleep queue.
module:kern/thread::
  Preemptive thread scheduling.
module:kern/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 :

module_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.
module_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.
module_mutex:plain::
  Default mutex, immediately sleeping on contention.

[[generic_development_tools]]
GENERIC DEVELOPMENT TOOLS
-------------------------

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

module:kern/bitmap::
  Arbitrary-length bit array.
module:kern/bulletin::
  Publish-subscribe mechanism.
module:kern/cbuf::
  Circular byte buffer.
module:kern/clock::
  Low resolution clock.
module:kern/error::
  Common errors and error handling functions.
module:kern/hash::
  Hash functions for integers and strings.
module:kern/hlist::
  Doubly-linked list specialized for forward traversals and O(1) removals.
module:kern/kmem::
  Object caching and general purpose memory allocator.
module:kern/list::
  Doubly-linked list.
module:kern/macros::
  Useful generic macros.
module:kern/rbtree::
  Red-black tree.
module:kern/rdxtree::
  Radix tree (with integer keys).
module:kern/slist::
  Singly-linked list.
module:kern/syscnt::
  Generic 64-bits counter.
module:kern/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 manpage:cenv for information about the subset of standard C interfaces
supported.

[[multiprocessor_support]]
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 :

module:kern/atomic::
  Inter-processor atomic operations.
module:kern/cpumap::
  Specialized bitmaps representing processor sets.
module:kern/percpu::
  Per-processor data.
module:kern/spinlock::
  Inter-processor spin locks.
module:kern/sref::
  Scalable multiprocessor reference counters.
module:kern/thread::
  Preemptive thread scheduling.
module:kern/xcall::
  Low level inter-processor function calls.

[[virtual_memoru]]
VIRTUAL MEMORY
--------------

TODO Write when the virtual memory system is rewritten.

[[real_time]]
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 :

module:kern/rtmutex::
  Mutual exclusion with priority inheritance.
module:kern/spinlock::
  Inter-processor spin locks.
module:kern/thread::
  Preemptive thread scheduling.
module:arch/trap::
  Interrupt and exception handling.
module:kern/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]]
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 :

module:arch/atomic::
  Architecture-specific support for atomic instructions.
module:arch/cpu::
  Processor interface.
module:arch/pmap::
  Physical mappings, the MMU driver.
module:arch/strace::
  Stack tracing.
module:arch/tcb::
  Thread control block.
module:arch/trap::
  Interrupt and exception handling.

The machine-independent code assumes 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
---

manpage:cenv

manpage:init

manpage:style

manpage:xbuild

{x15-operating-system}