In this section we are going to describe every operating system in question. How they deal with syscalls, trapframes etc., all the low-level stuff. We also describe the way they understand common UNIX® primitives like what a PID is, what a thread is, etc. In the third subsection we talk about how UNIX® on UNIX® emulation could be done in general.
UNIX® is an operating system with a long history that has influenced almost every other operating system currently in use. Starting in the 1960s, its development continues to this day (although in different projects). UNIX® development soon forked into two main ways: the BSDs and System III/V families. They mutually influenced themselves by growing a common UNIX® standard. Among the contributions originated in BSD we can name virtual memory, TCP/IP networking, FFS, and many others. The System V branch contributed to SysV interprocess communication primitives, copy-on-write, etc. UNIX® itself does not exist any more but its ideas have been used by many other operating systems world wide thus forming the so called UNIX®-like operating systems. These days the most influential ones are Linux®, Solaris, and possibly (to some extent) FreeBSD. There are in-company UNIX® derivatives (AIX, HP-UX etc.), but these have been more and more migrated to the aforementioned systems. Let us summarize typical UNIX® characteristics.
Every running program constitutes a process that represents a state of the computation. Running process is divided between kernel-space and user-space. Some operations can be done only from kernel space (dealing with hardware etc.), but the process should spend most of its lifetime in the user space. The kernel is where the management of the processes, hardware, and low-level details take place. The kernel provides a standard unified UNIX® API to the user space. The most important ones are covered below.
Common UNIX® API defines a syscall as a way to issue commands
from a user space process to the kernel. The most common
implementation is either by using an interrupt or specialized
instruction (think of
SYSENTER/SYSCALL instructions
for ia32). Syscalls are defined by a number. For example in FreeBSD,
the syscall number 85 is the swapon(2) syscall and the
syscall number 132 is mkfifo(2). Some syscalls need
parameters, which are passed from the user-space to the kernel-space
in various ways (implementation dependant). Syscalls are
synchronous.
Another possible way to communicate is by using a trap. Traps occur asynchronously after some event occurs (division by zero, page fault etc.). A trap can be transparent for a process (page fault) or can result in a reaction like sending a signal (division by zero).
There are other APIs (System V IPC, shared memory etc.) but the single most important API is signal. Signals are sent by processes or by the kernel and received by processes. Some signals can be ignored or handled by a user supplied routine, some result in a predefined action that cannot be altered or ignored.
Kernel instances are processed first in the system (so called init). Every running process can create its identical copy using the fork(2) syscall. Some slightly modified versions of this syscall were introduced but the basic semantic is the same. Every running process can morph into some other process using the exec(3) syscall. Some modifications of this syscall were introduced but all serve the same basic purpose. Processes end their lives by calling the exit(2) syscall. Every process is identified by a unique number called PID. Every process has a defined parent (identified by its PID).
Traditional UNIX® does not define any API nor implementation for threading, while POSIX® defines its threading API but the implementation is undefined. Traditionally there were two ways of implementing threads. Handling them as separate processes (1:1 threading) or envelope the whole thread group in one process and managing the threading in userspace (1:N threading). Comparing main features of each approach:
1:1 threading
- heavyweight threads
- the scheduling cannot be altered by the user (slightly mitigated by the POSIX® API)
+ no syscall wrapping necessary
+ can utilize multiple CPUs
1:N threading
+ lightweight threads
+ scheduling can be easily altered by the user
- syscalls must be wrapped
- cannot utilize more than one CPU
The FreeBSD project is one of the oldest open source operating systems currently available for daily use. It is a direct descendant of the genuine UNIX® so it could be claimed that it is a true UNIX® although licensing issues do not permit that. The start of the project dates back to the early 1990's when a crew of fellow BSD users patched the 386BSD operating system. Based on this patchkit a new operating system arose named FreeBSD for its liberal license. Another group created the NetBSD operating system with different goals in mind. We will focus on FreeBSD.
FreeBSD is a modern UNIX®-based operating system with all the features of UNIX®. Preemptive multitasking, multiuser facilities, TCP/IP networking, memory protection, symmetric multiprocessing support, virtual memory with merged VM and buffer cache, they are all there. One of the interesting and extremely useful features is the ability to emulate other UNIX®-like operating systems. As of December 2006 and 7-CURRENT development, the following emulation functionalities are supported:
FreeBSD/i386 emulation on FreeBSD/amd64
FreeBSD/i386 emulation on FreeBSD/ia64
Linux®-emulation of Linux® operating system on FreeBSD
NDIS-emulation of Windows networking drivers interface
NetBSD-emulation of NetBSD operating system
PECoff-support for PECoff FreeBSD executables
SVR4-emulation of System V revision 4 UNIX®
Actively developed emulations are the Linux® layer and various FreeBSD-on-FreeBSD layers. Others are not supposed to work properly nor be usable these days.
FreeBSD development happens in a central CVS repository where only a selected team of so called committers can write. This repository possesses several branches; the most interesting are the HEAD branch, in FreeBSD nomenclature called -CURRENT, and RELENG_X branches, where X stands for a number indicating a major version of FreeBSD. As of December 2006, there are development branches for 6.X development (RELENG_6) and for the 5.X development (RELENG_5). Other branches are closed and not actively maintained or only fed with security patches by the Security Officer of the FreeBSD project.
Historically the active development was done in the HEAD branch so
it was considered extremely unstable and supposed to happen to break
at any time. This is not true any more as the
Perforce (commercial version control system)
repository was introduced so that active development happen there.
There are many branches in Perforce where
development of certain parts of the system happens and these branches
are from time to time merged back to the main CVS repository thus
effectively putting the given feature to the FreeBSD operating system.
The same happened with the rdivacky_linuxolator
branch where development of this thesis code was going on.
More info about the FreeBSD operating system can be found at [2].
FreeBSD is traditional flavor of UNIX® in the sense of dividing the run of processes into two halves: kernel space and user space run. There are two types of process entry to the kernel: a syscall and a trap. There is only one way to return. In the subsequent sections we will describe the three gates to/from the kernel. The whole description applies to the i386 architecture as the Linuxulator only exists there but the concept is similar on other architectures. The information was taken from [1] and the source code.
FreeBSD has an abstraction called an execution class loader,
which is a wedge into the execve(2) syscall. This employs a
structure sysentvec, which describes an
executable ABI. It contains things like errno translation table,
signal translation table, various functions to serve syscall needs
(stack fixup, coredumping, etc.). Every ABI the FreeBSD kernel wants
to support must define this structure, as it is used later in the
syscall processing code and at some other places. System entries
are handled by trap handlers, where we can access both the
kernel-space and the user-space at once.
Syscalls on FreeBSD are issued by executing interrupt
0x80 with register %eax set
to a desired syscall number with arguments passed on the stack.
When a process issues an interrupt 0x80, the
int0x80 syscall trap handler is issued (defined
in sys/i386/i386/exception.s), which prepares
arguments (i.e. copies them on to the stack) for a
call to a C function syscall(2) (defined in
sys/i386/i386/trap.c), which processes the
passed in trapframe. The processing consists of preparing the
syscall (depending on the sysvec entry),
determining if the syscall is 32-bit or 64-bit one (changes size
of the parameters), then the parameters are copied, including the
syscall. Next, the actual syscall function is executed with
processing of the return code (special cases for
ERESTART and EJUSTRETURN
errors). Finally an userret() is scheduled,
switching the process back to the users-pace. The parameters to
the actual syscall handler are passed in the form of
struct thread *td,
struct syscall args * arguments where the second
parameter is a pointer to the copied in structure of
parameters.
Handling of traps in FreeBSD is similar to the handling of
syscalls. Whenever a trap occurs, an assembler handler is called.
It is chosen between alltraps, alltraps with regs pushed or
calltrap depending on the type of the trap. This handler prepares
arguments for a call to a C function trap()
(defined in sys/i386/i386/trap.c), which then
processes the occurred trap. After the processing it might send a
signal to the process and/or exit to userland using
userret().
Exits from kernel to userspace happen using the assembler
routine doreti regardless of whether the kernel
was entered via a trap or via a syscall. This restores the program
status from the stack and returns to the userspace.
FreeBSD operating system adheres to the traditional UNIX® scheme,
where every process has a unique identification number, the so
called PID (Process ID). PID numbers are
allocated either linearly or randomly ranging from
0 to PID_MAX. The allocation
of PID numbers is done using linear searching of PID space. Every
thread in a process receives the same PID number as result of the
getpid(2) call.
There are currently two ways to implement threading in FreeBSD.
The first way is M:N threading followed by the 1:1 threading model.
The default library used is M:N threading
(libpthread) and you can switch at runtime to
1:1 threading (libthr). The plan is to switch
to 1:1 library by default soon. Although those two libraries use
the same kernel primitives, they are accessed through different
API(es). The M:N library uses the kse_* family
of syscalls while the 1:1 library uses the thr_*
family of syscalls. Because of this, there is no general concept
of thread ID shared between kernel and userspace. Of course, both
threading libraries implement the pthread thread ID API. Every
kernel thread (as described by struct thread)
has td tid identifier but this is not directly accessible
from userland and solely serves the kernel's needs. It is also
used for 1:1 threading library as pthread's thread ID but handling
of this is internal to the library and cannot be relied on.
As stated previously there are two implementations of threading in FreeBSD. The M:N library divides the work between kernel space and userspace. Thread is an entity that gets scheduled in the kernel but it can represent various number of userspace threads. M userspace threads get mapped to N kernel threads thus saving resources while keeping the ability to exploit multiprocessor parallelism. Further information about the implementation can be obtained from the man page or [1]. The 1:1 library directly maps a userland thread to a kernel thread thus greatly simplifying the scheme. None of these designs implement a fairness mechanism (such a mechanism was implemented but it was removed recently because it caused serious slowdown and made the code more difficult to deal with).
Linux® is a UNIX®-like kernel originally developed by Linus Torvalds, and now being contributed to by a massive crowd of programmers all around the world. From its mere beginnings to todays, with wide support from companies such as IBM or Google, Linux® is being associated with its fast development pace, full hardware support and benevolent dictator model of organization.
Linux® development started in 1991 as a hobbyist project at University of Helsinki in Finland. Since then it has obtained all the features of a modern UNIX®-like OS: multiprocessing, multiuser support, virtual memory, networking, basically everything is there. There are also highly advanced features like virtualization etc.
As of 2006 Linux® seems to be the most widely used open source operating system with support from independent software vendors like Oracle, RealNetworks, Adobe, etc. Most of the commercial software distributed for Linux® can only be obtained in a binary form so recompilation for other operating systems is impossible.
Most of the Linux® development happens in a Git version control system. Git is a distributed system so there is no central source of the Linux® code, but some branches are considered prominent and official. The version number scheme implemented by Linux® consists of four numbers A.B.C.D. Currently development happens in 2.6.C.D, where C represents major version, where new features are added or changed while D is a minor version for bugfixes only.
More information can be obtained from [4].
Linux® follows the traditional UNIX® scheme of dividing the run of a process in two halves: the kernel and user space. The kernel can be entered in two ways: via a trap or via a syscall. The return is handled only in one way. The further description applies to Linux® 2.6 on the i386™ architecture. This information was taken from [3].
Syscalls in Linux® are performed (in userspace) using
syscallX macros where X substitutes a number
representing the number of parameters of the given syscall. This
macro translates to a code that loads %eax
register with a number of the syscall and executes interrupt
0x80. After this syscall return is called,
which translates negative return values to positive
errno values and sets res to
-1 in case of an error. Whenever the interrupt
0x80 is called the process enters the kernel in
system call trap handler. This routine saves all registers on the
stack and calls the selected syscall entry. Note that the Linux®
calling convention expects parameters to the syscall to be passed
via registers as shown here:
parameter -> %ebx
parameter -> %ecx
parameter -> %edx
parameter -> %esi
parameter -> %edi
parameter -> %ebp
There are some exceptions to this, where Linux® uses different
calling convention (most notably the clone
syscall).
The trap handlers are introduced in
arch/i386/kernel/traps.c and most of these
handlers live in arch/i386/kernel/entry.S,
where handling of the traps happens.
Return from the syscall is managed by syscall exit(3), which checks for the process having unfinished work, then checks whether we used user-supplied selectors. If this happens stack fixing is applied and finally the registers are restored from the stack and the process returns to the userspace.
In the 2.6 version, the Linux® operating system redefined some
of the traditional UNIX® primitives, notably PID, TID and thread.
PID is defined not to be unique for every process, so for some
processes (threads) getppid(2) returns the same value. Unique
identification of process is provided by TID. This is because
NPTL (New POSIX® Thread Library) defines
threads to be normal processes (so called 1:1 threading). Spawning
a new process in Linux® 2.6 happens using the
clone syscall (fork variants are reimplemented using
it). This clone syscall defines a set of flags that affect
behaviour of the cloning process regarding thread implementation.
The semantic is a bit fuzzy as there is no single flag telling the
syscall to create a thread.
Implemented clone flags are:
CLONE_VM - processes share their memory
space
CLONE_FS - share umask, cwd and
namespace
CLONE_FILES - share open
files
CLONE_SIGHAND - share signal handlers
and blocked signals
CLONE_PARENT - share parent
CLONE_THREAD - be thread (further
explanation below)
CLONE_NEWNS - new namespace
CLONE_SYSVSEM - share SysV undo
structures
CLONE_SETTLS - setup TLS at supplied
address
CLONE_PARENT_SETTID - set TID in the
parent
CLONE_CHILD_CLEARTID - clear TID in the
child
CLONE_CHILD_SETTID - set TID in the
child
CLONE_PARENT sets the real parent to the
parent of the caller. This is useful for threads because if thread
A creates thread B we want thread B to be parented to the parent of
the whole thread group. CLONE_THREAD does
exactly the same thing as CLONE_PARENT,
CLONE_VM and CLONE_SIGHAND,
rewrites PID to be the same as PID of the caller, sets exit signal
to be none and enters the thread group.
CLONE_SETTLS sets up GDT entries for TLS
handling. The CLONE_*_*TID set of flags
sets/clears user supplied address to TID or 0.
As you can see the CLONE_THREAD does most
of the work and does not seem to fit the scheme very well. The
original intention is unclear (even for authors, according to
comments in the code) but I think originally there was one
threading flag, which was then parcelled among many other flags
but this separation was never fully finished. It is also unclear
what this partition is good for as glibc does not use that so only
hand-written use of the clone permits a programmer to access this
features.
For non-threaded programs the PID and TID are the same. For
threaded programs the first thread PID and TID are the same and
every created thread shares the same PID and gets assigned a
unique TID (because CLONE_THREAD is passed in)
also parent is shared for all processes forming this threaded
program.
The code that implements pthread_create(3) in NPTL defines the clone flags like this:
int clone_flags = (CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGNAL | CLONE_SETTLS | CLONE_PARENT_SETTID | CLONE_CHILD_CLEARTID | CLONE_SYSVSEM #if __ASSUME_NO_CLONE_DETACHED == 0 | CLONE_DETACHED #endif | 0);
The CLONE_SIGNAL is defined like
#define CLONE_SIGNAL (CLONE_SIGHAND | CLONE_THREAD)
the last 0 means no signal is sent when any of the threads exits.
According to a dictionary definition, emulation is the ability of a program or device to imitate another program or device. This is achieved by providing the same reaction to a given stimulus as the emulated object. In practice, the software world mostly sees three types of emulation - a program used to emulate a machine (QEMU, various game console emulators etc.), software emulation of a hardware facility (OpenGL emulators, floating point units emulation etc.) and operating system emulation (either in kernel of the operating system or as a userspace program).
Emulation is usually used in a place, where using the original component is not feasible nor possible at all. For example someone might want to use a program developed for a different operating system than they use. Then emulation comes in handy. Sometimes there is no other way but to use emulation - e.g. when the hardware device you try to use does not exist (yet/anymore) then there is no other way but emulation. This happens often when porting an operating system to a new (non-existent) platform. Sometimes it is just cheaper to emulate.
Looking from an implementation point of view, there are two main approaches to the implementation of emulation. You can either emulate the whole thing - accepting possible inputs of the original object, maintaining inner state and emitting correct output based on the state and/or input. This kind of emulation does not require any special conditions and basically can be implemented anywhere for any device/program. The drawback is that implementing such emulation is quite difficult, time-consuming and error-prone. In some cases we can use a simpler approach. Imagine you want to emulate a printer that prints from left to right on a printer that prints from right to left. It is obvious that there is no need for a complex emulation layer but simply reversing of the printed text is sufficient. Sometimes the emulating environment is very similar to the emulated one so just a thin layer of some translation is necessary to provide fully working emulation! As you can see this is much less demanding to implement, so less time-consuming and error-prone than the previous approach. But the necessary condition is that the two environments must be similar enough. The third approach combines the two previous. Most of the time the objects do not provide the same capabilities so in a case of emulating the more powerful one on the less powerful we have to emulate the missing features with full emulation described above.
This master thesis deals with emulation of UNIX® on UNIX®, which is exactly the case, where only a thin layer of translation is sufficient to provide full emulation. The UNIX® API consists of a set of syscalls, which are usually self contained and do not affect some global kernel state.
There are a few syscalls that affect inner state but this can be dealt with by providing some structures that maintain the extra state.
No emulation is perfect and emulations tend to lack some parts but this usually does not cause any serious drawbacks. Imagine a game console emulator that emulates everything but music output. No doubt that the games are playable and one can use the emulator. It might not be that comfortable as the original game console but its an acceptable compromise between price and comfort.
The same goes with the UNIX® API. Most programs can live with a very limited set of syscalls working. Those syscalls tend to be the oldest ones (read(2)/write(2), fork(2) family, signal(3) handling, exit(3), socket(2) API) hence it is easy to emulate because their semantics is shared among all UNIX®es, which exist todays.
All FreeBSD documents are available for download at http://ftp.FreeBSD.org/pub/FreeBSD/doc/
Questions that are not answered by the
documentation may be
sent to <[email protected]>.
Send questions about this document to <[email protected]>.