1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
|
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 microkernel. Its purpose is to provide the basic
foundations for an operating system or a hosted application.
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>>
* <<posix_like_interface,POSIX-like interface>>
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/llsync::
Lockless synchronization, similar to Linux Read-Copy Update (RCU).
module:kern/mutex::
Mutual exclusion lock.
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.
[[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/error::
Common errors and error handling functions.
module:kern/kmem::
Object caching and general purpose memory allocator.
module:kern/list::
Linked list.
module:kern/macros::
Useful generic macros.
module:kern/printk::
Formatted output functions.
module:kern/rbtree::
Red-black tree.
module:kern/rdxtree::
Radix tree (with integer keys).
module:kern/sprintf::
Formatted string functions.
module:kern/syscnt::
Generic 64-bits counter.
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 and hash tables on top
of the provided facilities. Hash functions may be provided in the future.
[[multiprocessor_support]]
MULTIPROCESSOR SUPPORT
----------------------
The X15 kernel is designed to support hardware with multiple processors.
The scheduler should scale well up to one hundred 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:arch/mb::
Inter-processor memory barriers.
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 almost all the requirements of a true hard 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 X15 doesn't yet comply with all the requirements for hard real-time.
For that, it still needs a high resolution timer system.
[[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/mb::
Memory barriers.
module:arch/param::
Miscellaneous parameters.
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.
X15 currently requires a memory management unit, but that may change in
the future. In addition, the machine-independent code assumes an almost
completely relaxed memory model, but still expects no reordering between
dependent loads. This model closely matches the ARM family of processors.
[[posix_like_interface]]
POSIX-LIKE INTERFACE
--------------------
Many of the functions provided by the kernel match well-known POSIX
interfaces. In particular, this is true for standard integer types,
memory and string functions, and multithreading. While the thread module
doesn't comply with POSIX, it was designed so that adding a lightweight
wrapper could easily be done. Users must keep in mind that the behaviour
of some interfaces are not meant to comply with POSIX regarding certain
details; they are only meant to be POSIX-like.
SEE
---
manpage:style
{x15-operating-system}
|