Subversion Repositories HelenOS-doc

Compare Revisions

Ignore whitespace Rev 44 → Rev 45

/design/trunk/src/ch_intro.xml
4,28 → 4,7
 
<title>Introduction</title>
 
<para> <mediaobject id="helenos">
<imageobject role="html">
<imagedata align="center" width="197" fileref="images/helenos.gif" format="GIF" />
</imageobject>
<imageobject role="fop">
<imagedata style="antialiasing:true" align="center" fileref="images.vector/helenos.svg" format="SVG" />
</imageobject>
</mediaobject></para>
 
<para>The HelenOS project is an effort to develop an easily portable, light
but durable operating system. HelenOS supports SMP, multitasking and
multithreading on both 32-bit and 64-bit, little-endian and big-endian,
processor architectures, among wich are AMD64/EM64T (x86-64), IA-32, IA-64
(Itanium), 32-bit MIPS, 32-bit PowerPC and SPARC V9.</para>
 
<para>This manual should help you understanding design concepts of different
part of the operating system.</para>
 
<para>In case you are interested in our project or have any questions about
it, feel free to subscribe to our <ulink
url="http://www.helenos.eu/?reason=list">mailing list</ulink>. We are
looking for people to join our team or to merely try out our system and
become our beta testers.</para>
<para>This book describes the design and principles of the HelenOS operating
system from the perspective of its microkernel as well as from the
perspective of its userspace drivers and server tasks.</para>
</chapter>
/design/trunk/src/ch_synchronization.xml
7,13 → 7,13
<section>
<title>Introduction</title>
 
<para>The HelenOS operating system is designed to make use of parallelism
offered by hardware and to exploit concurrency of both the kernel and
userspace tasks. This is achieved through multiprocessor support and
several levels of multiprogramming (i.e. multitasking, multithreading and
through userspace pseudo threads). However, such a highly concurrent
environment needs safe and efficient ways to handle mutual exclusion and
synchronization of many execution flows.</para>
<para>The HelenOS operating system is designed to make use of the
parallelism offered by the hardware and to exploit concurrency of both the
kernel and userspace tasks. This is achieved through multiprocessor
support and several levels of multiprogramming such as multitasking,
multithreading and also through userspace pseudo threads. However, such a
highly concurrent environment needs safe and efficient ways to handle
mutual exclusion and synchronization of many execution flows.</para>
</section>
 
<section>
22,8 → 22,8
<section>
<title>Spinlocks</title>
 
<para>The basic mutual exclusion primitive is the spinlock. Spinlock
implements busy waiting for an availability of a memory lock (i.e.
<para>The basic mutual exclusion primitive is the spinlock. The spinlock
implements active waiting for the availability of a memory lock (i.e.
simple variable) in a multiprocessor-safe manner. This safety is
achieved through the use of a specialized, architecture-dependent,
atomic test-and-set operation which either locks the spinlock (i.e. sets
30,21 → 30,22
the variable) or, provided that it is already locked, leaves it
unaltered. In any case, the test-and-set operation returns a value, thus
signalling either success (i.e. zero return value) or failure (i.e.
non-zero value) in acquiring the lock. Note that this makes the
non-zero value) in acquiring the lock. Note that this makes a
fundamental difference between the naive algorithm that doesn't use the
atomic operation and the spinlock algortihm. While the naive algorithm
is prone to race conditions on SMP configuratinos and thus is completely
is prone to race conditions on SMP configurations and thus is completely
SMP-unsafe, the spinlock algorithm eliminates the possibility of race
conditions and is suitable for mutual exclusion use.</para>
 
<para>The semantics of the test-and-set operation is that the spinlock
remains unavailable until this operation called on the respective
spinlock returns zero. HelenOS builds two functions on top of
test-and-set operation. The first is the unconditional attempt to
acquire the spinlock and is called <emphasis>spinlock_lock</emphasis>.
It simply loops until test-and-set returns zero. The other operation,
spinlock returns zero. HelenOS builds two functions on top of the
test-and-set operation. The first function is the unconditional attempt
to acquire the spinlock and is called
<emphasis>spinlock_lock</emphasis>. It simply loops until the
test-and-set returns a zero value. The other function,
<emphasis>spinlock_trylock</emphasis>, is the conditional lock operation
and calls the test-and-set only once to find out wheter it managed to
and calls the test-and-set only once to find out whether it managed to
acquire the spinlock or not. The conditional operation is useful in
situations in which an algorithm cannot acquire more spinlocks in the
proper order and a deadlock cannot be avoided. In such a case, the
51,44 → 52,45
algorithm would detect the danger and instead of possibly deadlocking
the system it would simply release some spinlocks it already holds and
retry the whole operation with the hope that it will succeed next time.
The unlock operation, <emphasis>spinlock_unlock</emphasis>, is quite
easy - it merely clears the spinlock variable.</para>
The unlock function, <emphasis>spinlock_unlock</emphasis>, is quite easy
- it merely clears the spinlock variable.</para>
 
<para>Nevertheless, there is a special issue related to hardware
optimizations that modern processors implement. Particularily
problematic is the out-of-order execution of instructions within the
critical section protected by a spinlock. The processors are always
optimizations that modern processors implement. Particularly problematic
is the out-of-order execution of instructions within the critical
section protected by a spinlock. The processors are always
self-consistent so that they can carry out speculatively executed
instructions in the right order with regard to dependencies among those
instructions. However, the dependency between instructions inside the
critical section and those that implement locking and unlocking of the
respective spinlock is not implicit on some processor architectures and
the processor needs to be explicitly told about each occurrence of such
a dependency. Therefore, HelenOS adds architecture-specific hooks to all
<emphasis>spinlock_lock</emphasis>,
respective spinlock is not implicit on some processor architectures. As
a result, the processor needs to be explicitly told about each
occurrence of such a dependency. Therefore, HelenOS adds
architecture-specific hooks to all <emphasis>spinlock_lock</emphasis>,
<emphasis>spinlock_trylock</emphasis> and
<emphasis>spinlock_unlock</emphasis> to prevent the instructions inside
the critical section from bleeding out. On some architectures, these
hooks can be a no-op because the dependencies are implicitly there
because of the special properties of locking and unlocking instructions.
However, other architectures need to instrument these hooks with
different memory barriers, depending on what operations can bleed
out.</para>
<emphasis>spinlock_unlock</emphasis> functions to prevent the
instructions inside the critical section from permeating out. On some
architectures, these hooks can be void because the dependencies are
implicitly there because of the special properties of locking and
unlocking instructions. However, other architectures need to instrument
these hooks with different memory barriers, depending on what operations
could permeate out.</para>
 
<para>Spinlocks have one significant drawback: when held for longer time
periods, they harm both parallelism and concurrency. Processor executing
<emphasis>spinlock_lock</emphasis> does not do any fruitful work and is
effectively halted until it can grab the lock and proceed. Similarily,
other threads cannot execute on the processor that holds the spinlock
because the kernel disables preemption on that processor when a spinlock
is held. The reason behind disabling preemption is priority inversion
problem avoidance. For the same reason, threads are strongly discouraged
from sleeping when they hold a spinlock.</para>
periods, they harm both parallelism and concurrency. The processor
executing <emphasis>spinlock_lock</emphasis> does not do any fruitful
work and is effectively halted until it can grab the lock and proceed.
Similarily, other execution flows cannot execute on the processor that
holds the spinlock because the kernel disables preemption on that
processor when a spinlock is held. The reason behind disabling
preemption is priority inversion problem avoidance. For the same reason,
threads are strongly discouraged from sleeping when they hold a
spinlock.</para>
 
<para>To summarize, spinlocks represent very simple and essential mutual
exclusion primitive for SMP systems. On the other hand, spinlocks scale
poorly because of the active loop they are based on. Therefore,
spinlocks are used in HelenOS only for a short-time mutual exclusion and
spinlocks are used in HelenOS only for short-time mutual exclusion and
in cases where the mutual exclusion is required out of thread context.
Lastly, spinlocks are used in the construction of passive
synchronization primitives.</para>
102,14 → 104,14
<title>Wait queues</title>
 
<para>A wait queue is the basic passive synchronization primitive on
which all other passive synchronization primitives build. Simply put, it
allows a thread to sleep until an event associated with the particular
wait queue occurs. Multiple threads are notified about incoming events
in first come, first served fashion. Moreover, should the event come
before any thread waits for it, it is recorded in the wait queue as a
missed wakeup and later forwarded to the first thread that decides to
wait in the queue. The inner structures of the wait queue are protected
by a spinlock.</para>
which all other passive synchronization primitives are built. Simply
put, it allows a thread to sleep until an event associated with the
particular wait queue occurs. Multiple threads are notified about
incoming events in a first come, first served fashion. Moreover, should
the event come before any thread waits for it, it is recorded in the
wait queue as a missed wakeup and later forwarded to the first thread
that decides to wait in the queue. The inner structures of the wait
queue are protected by a spinlock.</para>
 
<para>The thread that wants to wait for a wait queue event uses the
<emphasis>waitq_sleep_timeout</emphasis> function. The algorithm then
124,18 → 126,19
<listitem>
<para>another thread calls <emphasis>waitq_wakeup</emphasis> and the
thread is the first thread in the wait queue's list of sleeping
threads</para>
threads;</para>
</listitem>
 
<listitem>
<para>another thread calls
<emphasis>waitq_interrupt_sleep</emphasis> on the sleeping
thread</para>
thread;</para>
</listitem>
 
<listitem>
<para>the sleep timeouts provided that none of the previous occurred
within a specified time limit; the limit can be infinity</para>
<para>the sleep times out provided that none of the previous
occurred within a specified time limit; the limit can be
infinity.</para>
</listitem>
</orderedlist>
 
142,26 → 145,27
<para>All five possibilities (immediate return on success, immediate
return on failure, wakeup after sleep, interruption and timeout) are
distinguishable by the return value of
<emphasis>waitq_sleep_timeout</emphasis>. The ability to interrupt a
sleeping thread is essential for externally initiated thread termination
and the ability to wait only for a certain amount of time is used, for
instance, to passively delay thread execution by several microseconds or
even seconds in <emphasis>thread_sleep</emphasis> function. Because all
other passive kernel synchronization primitives are based on wait
queues, they also have the option of being interrutped and, more
importantly, can timeout. All of them also implement the conditional
operation. Furthemore, this very fundamental interface reaches up to the
implementation of futexes - userspace synchronization primitive, which
makes it possible for a userspace thread to request synchronization
operation with a timeout or a conditional operation.</para>
<emphasis>waitq_sleep_timeout</emphasis>. Being able to interrupt a
sleeping thread is essential for externally initiated thread
termination. The ability to wait only for a certain amount of time is
used, for instance, to passively delay thread execution by several
microseconds or even seconds in <emphasis>thread_sleep</emphasis>
function. Due to the fact that all other passive kernel synchronization
primitives are based on wait queues, they also have the option of being
interrutped and, more importantly, can timeout. All of them also
implement the conditional operation. Furthemore, this very fundamental
interface reaches up to the implementation of futexes - userspace
synchronization primitive, which makes it possible for a userspace
thread to request a synchronization operation with a timeout or a
conditional operation.</para>
 
<para>From the description above, it should be apparent, that when a
sleeping thread is woken by <emphasis>waitq_wakeup</emphasis> or when
<emphasis>waitq_sleep_timeout</emphasis> succeeds immediatelly, the
thread can be sure the event has come and the thread need not and should
not verify this fact. This approach is called direct hand-off and is
characteristic for all passive HelenOS synchronization primitives with
one exception described below.</para>
<emphasis>waitq_sleep_timeout</emphasis> succeeds immediately, the
thread can be sure that the event has occurred. The thread need not and
should not verify this fact. This approach is called direct hand-off and
is characteristic for all passive HelenOS synchronization primitives,
with the exception as described below.</para>
</section>
 
<section>
171,7 → 175,7
missed wakeups is equal to the number of threads that will not block in
<emphasis>watiq_sleep_timeout</emphasis> and would immediately succeed
instead. On the other hand, semaphores are synchronization primitives
that will let predefined amount of threads in its critical section and
that will let predefined amount of threads into its critical section and
block any other threads above this count. However, these two cases are
exactly the same. Semaphores in HelenOS are therefore implemented as
wait queues with a single semantic change: their wait queue is
192,13 → 196,13
<section>
<title>Mutexes</title>
 
<para>Mutexes are are sometimes referred to as binary sempahores. That
means that mutexes are like semaphores that allow only one thread in its
<para>Mutexes are sometimes referred to as binary sempahores. That means
that mutexes are like semaphores that allow only one thread in its
critical section. Indeed, mutexes in HelenOS are implemented exactly in
this way: they are built atop semaphores. From another point of view,
they can be viewed as spinlocks without busy waiting. Their semaphore
heritage provides good basics for both conditional operation and
operation with timeout. The locking operation is called
this way: they are built on top of semaphores. From another point of
view, they can be viewed as spinlocks without busy waiting. Their
semaphore heritage provides good basics for both conditional operation
and operation with timeout. The locking operation is called
<emphasis>mutex_lock</emphasis>, the conditional locking operation is
called <emphasis>mutex_trylock</emphasis> and the unlocking operation is
called <emphasis>mutex_unlock</emphasis>.</para>
209,26 → 213,26
 
<para>Reader/writer locks, or rwlocks, are by far the most complicated
synchronization primitive within the kernel. The goal of these locks is
to improve concurrency of applications in which threads need to
synchronize access to a shared resource and that access can be
to improve concurrency of applications, in which threads need to
synchronize access to a shared resource, and that access can be
partitioned into a read-only mode and a write mode. Reader/writer locks
should make it possible for several, possibly many, readers to enter the
critical section, provided that no writer is currently in the critical
section, or to be in the critical section contemporarily. Writers are
allowed to enter the critical section only individually, provided that
no reader is in the critical section already. Applications in which the
majority of operations can be done in the read-only mode can benefit
no reader is in the critical section already. Applications, in which the
majority of operations can be done in the read-only mode, can benefit
from increased concurrency created by reader/writer locks.</para>
 
<para>During reader/writer locks construction, a decision should be made
<para>During reader/writer lock construction, a decision should be made
whether readers will be prefered over writers or whether writers will be
prefered over readers in cases when the lock is not currently held and
both a reader and a writer want to gain the lock. Some operating systems
prefer one group over the other, creating thus a possibility for
starving the unprefered group. In the HelenOS operating system, none of
the two groups is prefered. The lock is granted on the first come, first
the two groups is prefered. The lock is granted on a first come, first
served basis with the additional note that readers are granted the lock
in biggest possible batches.</para>
in the biggest possible batch.</para>
 
<para>With this policy and the timeout modes of operation, the direct
hand-off becomes much more complicated. For instance, a writer leaving
235,15 → 239,15
the critical section must wake up all leading readers in the rwlock's
wait queue or one leading writer or no-one if no thread is waiting.
Similarily, the last reader leaving the critical section must wakeup the
sleeping writer, if there are any sleeping threads at all. As another
example, if a writer at the beginning of the rwlock's wait queue
timeouts and the lock is held by at least one reader, the timeouting
writer must first wake up all readers that follow him in the queue prior
to signalling the timeout itself and giving up.</para>
sleeping writer if there are any sleeping threads left at all. As
another example, if a writer at the beginning of the rwlock's wait queue
times out and the lock is held by at least one reader, the writer which
has timed out must first wake up all readers that follow him in the
queue prior to signalling the timeout itself and giving up.</para>
 
<para>Because of the issues mentioned in the previous paragraph, the
reader/writer locks imlpementation needs to walk the rwlock wait queue's
list of sleeping threads directly in order to find out the type of
<para>Due to the issues mentioned in the previous paragraph, the
reader/writer lock imlpementation needs to walk the rwlock wait queue's
list of sleeping threads directly, in order to find out the type of
access that the queueing threads demand. This makes the code difficult
to understand and dependent on the internal implementation of the wait
queue. Nevertheless, it remains unclear to the authors of HelenOS
258,7 → 262,7
the exclusive mutex. If it succeeds, the writer is granted the rwlock.
However, if the operation fails (e.g. times out), the writer must check
for potential readers at the head of the list of sleeping threads
associated with the mutex's wait queue and proceed according to the
associated with the mutex's wait queue and then proceed according to the
procedure outlined above.</para>
 
<para>The exclusive mutex plays an important role in reader
268,19 → 272,19
 
<orderedlist>
<listitem>
<para>there are other readers in the critical section</para>
<para>there are other readers in the critical section and</para>
</listitem>
 
<listitem>
<para>there are no sleeping threads waiting for the exclusive
mutex</para>
mutex.</para>
</listitem>
</orderedlist>
 
<para>If both conditions are true, the reader will bypass the mutex,
increment the number of readers in the critical section and enter the
critical section. Note that if there are any sleeping threads at the
beginning of the wait queue, the first of them must be a writer. If the
increment the number of readers in the critical section and then enter
the critical section. Note that if there are any sleeping threads at the
beginning of the wait queue, the first must be a writer. If the
conditions are not fulfilled, the reader normally waits until the
exclusive mutex is granted to it.</para>
</section>
/design/trunk/src/ch_arch_overview.xml
5,9 → 5,8
<title>Architecture overview</title>
 
<section>
<title>Scheme</title>
 
<para><mediaobject id="arch1">
<para>
<mediaobject id="arch1">
<imageobject role="html">
<imagedata fileref="images/arch1.png" format="PNG" />
</imageobject>
15,134 → 14,30
<imageobject role="fop">
<imagedata fileref="images.vector/arch1.svg" format="SVG" />
</imageobject>
</mediaobject></para>
</mediaobject>
</para>
</section>
 
<section>
<title>Kernel primitives</title>
<para>The HelenOS operating system is designed as a relatively small
microkernel assisted with a set of userspace drivers and server tasks.
HelenOS is not very radical in what subsystems should or should not be
implemented in the kernel - in some cases, both kernel and userspace
drivers exist. The reason for creating the system as a microkernel is
prosaic. Even though it is initially more difficult to get the same level
of functionality from a microkernel than it is in the case of a simple
monolithic kernel, a microkernel is much easier to maintain once the
pieces have been put to work together. Therefore, the kernel of HelenOS,
as well as the essential userspace libraries thereof can be maintained by
only a few developers who understand them completely. In addition, a
microkernel based operating system reaches completion sooner than
monolithic kernels as the system can be used even without some traditional
subsystems (e.g. block devices, filesystems and networking).</para>
 
<para><termdef><glossterm>Thread</glossterm> is the basic execution
primitive.</termdef></para>
 
<para><termdef><glossterm>Thread context</glossterm> represents state of
the <emphasis>thread</emphasis>. Thread context is built of the context
registers contents, FPU state and the stack.</termdef></para>
 
<para><termdef><glossterm>Task</glossterm> is a multi-purpose entity,
serving to incorporate set if its threads, provide common address space to its threads,
be an end-point in IPC.</termdef></para>
 
<para><termdef><glossterm>Address space area</glossterm> is a mutually
disjunctive range of memory with the code, stack and data.
</termdef></para>
 
<para><termdef><glossterm>Address space</glossterm> is a aggregating
entity for address space areas, connecting them to the task.
</termdef></para>
<para>HelenOS is comprised of the kernel and userspace server tasks. The
kernel provides scheduling, memory management and IPC. It also contains
essential device drivers that control the system clock and other devices
necessary to guarantee a safe environment. Userspace communicates with the
kernel through </para>
</section>
 
<section>
<title>Monolithic microkernel</title>
 
<para>Though HelenOS was initially planned as a microkernel, we were
trying to avoid several issues, connected with microkernels, such as much
higher overhead during memory management and hardware operations. For this
reason some of the subsystems, that are to be implemented as servers in
classic microkernel design, were implemented as a part of kernel, thus
minimizing this overhead.</para>
 
<formalpara>
<title>Memory management</title>
 
<para>HelenOS has all its memory
management functionality in the kernel, available to the memory
management server via the set of syscalls.</para>
</formalpara>
 
<formalpara>
<title>Kernel device drivers</title>
 
<para>HelenOS kernel has some of the very basic device drivers
<itemizedlist>
<listitem>
ACPI
</listitem>
 
<listitem>
APIC
</listitem>
 
<listitem>
SMP configuration
</listitem>
 
<listitem>
System clock
</listitem>
 
<listitem>
Interrupt controllers
</listitem>
 
<listitem>
Console and frame buffer
</listitem>
 
</itemizedlist></para>
</formalpara>
</section>
 
<section>
<title>IPC</title>
 
<para>HelenOS IPC is designed in analogy with telephone communication.
Each task has an <emphasis>answerbox</emphasis> and a set of
<emphasis>phones</emphasis> to call another tasks' answerboxes.</para>
 
<para>Communication is possible after the connection is established, and
can be either <emphasis>asynchronious</emphasis> or
<emphasis>synchronious</emphasis>.</para>
</section>
 
<section>
<title>Functionality model</title>
 
<para>As you know, microkernel design is very simple, just enough to
provide communication facility for tasks. Most of the OS functionality is
performed by server tasks, that are running in userspace. Thus most of the
system calls in monolithic kernels, are the IPC calls on server tasks in
microkernels.</para>
 
<para>Moreover, problems experience the device drivers. Running in the
user space, device driver still needs to recieve interrupts and access
hardware directly.</para>
 
<para>This raises two major problems in microkernels: <orderedlist
numeration="loweralpha">
<listitem>
What is the recipient address of the server (e.g. "memory manager" or a specific device driver) ?
</listitem>
 
<listitem>
How this server task is going to access hardware or kernel while running in the user mode?
</listitem>
</orderedlist></para>
 
<formalpara id="intro_ns">
<title>Name server</title>
 
<para>As every microkernel, HelenOS has a "Name server" task with "well
known" IPC address, that connects user task to any server just by the
string service indentification.</para>
</formalpara>
 
<formalpara id="intro_ddi">
<title>Device driver interface</title>
 
<para>Device drivers use special syscalls to map physical memory areas
into their address space, to map port regions (mostly ia32). Interrupts
are delivered to the device driver task by the standard IPC
means.</para>
</formalpara>
</section>
</chapter>
/design/trunk/src/ch_memory_management.xml
270,23 → 270,24
</imageobject>
</mediaobject></para>
 
<para>In buddy allocator, memory is broken down into power-of-two
sized naturally aligned blocks. These blocks are organized in an array
of lists in which list with index i contains all unallocated blocks of
the size <mathphrase>2<superscript>i</superscript></mathphrase>. The
index i is called the order of block. Should there be two adjacent
equally sized blocks in list <mathphrase>i</mathphrase> (i.e.
buddies), the buddy allocator would coalesce them and put the
resulting block in list <mathphrase>i + 1</mathphrase>, provided that
the resulting block would be naturally aligned. Similarily, when the
allocator is asked to allocate a block of size
<para>In the buddy allocator, the memory is broken down into
power-of-two sized naturally aligned blocks. These blocks are
organized in an array of lists, in which the list with index i
contains all unallocated blocks of size
<mathphrase>2<superscript>i</superscript></mathphrase>. The index i is
called the order of block. Should there be two adjacent equally sized
blocks in the list i<mathphrase> </mathphrase>(i.e. buddies), the
buddy allocator would coalesce them and put the resulting block in
list <mathphrase>i + 1</mathphrase>, provided that the resulting block
would be naturally aligned. Similarily, when the allocator is asked to
allocate a block of size
<mathphrase>2<superscript>i</superscript></mathphrase>, it first tries
to satisfy the request from list with index i. If the request cannot
be satisfied (i.e. the list i is empty), the buddy allocator will try
to allocate and split larger block from list with index i + 1. Both of
these algorithms are recursive. The recursion ends either when there
are no blocks to coalesce in the former case or when there are no
blocks that can be split in the latter case.</para>
to satisfy the request from the list with index i. If the request
cannot be satisfied (i.e. the list i is empty), the buddy allocator
will try to allocate and split a larger block from the list with index
i + 1. Both of these algorithms are recursive. The recursion ends
either when there are no blocks to coalesce in the former case or when
there are no blocks that can be split in the latter case.</para>
 
<!--graphic fileref="images/mm1.png" format="EPS" /-->
 
305,11 → 306,11
be easily specialized to serve one particular task. It knows nothing
about the nature of memory it helps to allocate. In order to beat the
lack of this knowledge, the buddy allocator exports an interface that
each of its clients is required to implement. When supplied an
each of its clients is required to implement. When supplied with an
implementation of this interface, the buddy allocator can use
specialized external functions to find buddy for a block, split and
specialized external functions to find a buddy for a block, split and
coalesce blocks, manipulate block order and mark blocks busy or
available. For precize documentation of this interface, refer to
available. For precise documentation of this interface, refer to
<emphasis>"HelenOS Generic Kernel Reference Manual"</emphasis>.</para>
 
<formalpara>
324,15 → 325,16
The first entity keeps the order of the whole block. Other entities
within the block are assigned the magic value
<constant>BUDDY_INNER_BLOCK</constant>. This is especially important
for effective identification of buddies in one-dimensional array
for effective identification of buddies in a one-dimensional array
because the entity that represents a potential buddy cannot be
associated with <constant>BUDDY_INNER_BLOCK</constant> (i.e. if it
is associated with <constant>BUDDY_INNER_BLOCK</constant> then it is
not a buddy).</para>
 
<para>Buddy allocator always uses first frame to represent frame
block. This frame contains <varname>buddy_order</varname> variable
to provide information about the block size it actually represents (
<para>The buddy allocator always uses the first frame to represent
the frame block. This frame contains <varname>buddy_order</varname>
variable to provide information about the block size it actually
represents (
<mathphrase>2<superscript>buddy_order</superscript></mathphrase>
frames block). Other frames in block have this value set to magic
<constant>BUDDY_INNER_BLOCK</constant> that is much greater than