Linux® emulation in FreeBSD

2.2.1 Communication between kernel and user space process

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).

2.2.2 Communication between processes

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.

2.2.3 Process management

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).

2.2.4 Thread management

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

2.3.1 Technical details

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.

2.4.1 Technical details

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

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);

#define CLONE_SIGNAL (CLONE_SIGHAND | CLONE_THREAD)

3.2.1 Locking primitives

Contributed by: Attilio Rao <attilio@FreeBSD.org>

The FreeBSD synchronization primitive set is based on the idea to supply a rather huge number of different primitives in a way that the better one can be used for every particular, appropriate situation.

To a high level point of view you can consider three kinds of synchronization primitives in the FreeBSD kernel:

• atomic operations and memory barriers

• locks

• scheduling barriers

Below there are descriptions for the 3 families. For every lock, you should really check the linked manpage (where possible) for more detailed explanations.

3.2.2 Proc structure

Various emulation layers sometimes require some additional per-process data. It can manage separate structures (a list, a tree etc.) containing these data for every process but this tends to be slow and memory consuming. To solve this problem the FreeBSD proc structure contains p_emuldata, which is a void pointer to some emulation layer specific data. This proc entry is protected by the proc mutex.

The FreeBSD proc structure contains a p_sysent entry that identifies, which ABI this process is running. In fact, it is a pointer to the sysentvec described above. So by comparing this pointer to the address where the sysentvec structure for the given ABI is stored we can effectively determine whether the process belongs to our emulation layer. The code typically looks like:

if (__predict_true(p->p_sysent != &elf_Linux_sysvec))
	  return;

As you can see, we effectively use the __predict_true modifier to collapse the most common case (FreeBSD process) to a simple return operation thus preserving high performance. This code should be turned into a macro because currently it is not very flexible, i.e. we do not support Linux64 emulation nor A.OUT Linux processes on i386.

3.2.3 VFS

The FreeBSD VFS subsystem is very complex but the Linux emulation layer uses just a small subset via a well defined API. It can either operate on vnodes or file handlers. Vnode represents a virtual vnode, i.e. representation of a node in VFS. Another representation is a file handler, which represents an opened file from the perspective of a process. A file handler can represent a socket or an ordinary file. A file handler contains a pointer to its vnode. More then one file handler can point to the same vnode.

4.1.1 Linux prepsyscall

Linux passes arguments to syscalls via registers (that is why it is limited to 6 parameters on i386) while FreeBSD uses the stack. The Linux prepsyscall routine must copy parameters from registers to the stack. The order of the registers is: %ebx, %ecx, %edx, %esi, %edi, %ebp. The catch is that this is true for only most of the syscalls. Some (most notably clone) uses a different order but it is luckily easy to fix by inserting a dummy parameter in the linux_clone prototype.

4.1.2 Syscall writing

Every syscall implemented in the Linuxulator must have its prototype with various flags in syscalls.master. The form of the file is:

...
	AUE_FORK STD		{ int linux_fork(void); }
...
	AUE_CLOSE NOPROTO	{ int close(int fd); }
...

The first column represents the syscall number. The second column is for auditing support. The third column represents the syscall type. It is either STD, OBSOL, NOPROTO and UNIMPL. STD is a standard syscall with full prototype and implementation. OBSOL is obsolete and defines just the prototype. NOPROTO means that the syscall is implemented elsewhere so do not prepend ABI prefix, etc. UNIMPL means that the syscall will be substituted with the nosys syscall (a syscall just printing out a message about the syscall not being implemented and returning ENOSYS).

From syscalls.master a script generates three files: linux_syscall.h, linux_proto.h and linux_sysent.c. The linux_syscall.h contains definitions of syscall names and their numerical value, e.g.:

...
#define LINUX_SYS_linux_fork 2
...
#define LINUX_SYS_close 6
...

The linux_proto.h contains structure definitions of arguments to every syscall, e.g.:

struct linux_fork_args {
  register_t dummy;
};

And finally, linux_sysent.c contains structure describing the system entry table, used to actually dispatch a syscall, e.g.:

{ 0, (sy_call_t *)linux_fork, AUE_FORK, NULL, 0, 0 }, /* 2 = linux_fork */
{ AS(close_args), (sy_call_t *)close, AUE_CLOSE, NULL, 0, 0 }, /* 6 = close */

As you can see linux_fork is implemented in Linuxulator itself so the definition is of STD type and has no argument, which is exhibited by the dummy argument structure. On the other hand close is just an alias for real FreeBSD close(2) so it has no linux arguments structure associated and in the system entry table it is not prefixed with linux as it calls the real close(2) in the kernel.

4.1.3 Dummy syscalls

The Linux emulation layer is not complete, as some syscalls are not implemented properly and some are not implemented at all. The emulation layer employs a facility to mark unimplemented syscalls with the DUMMY macro. These dummy definitions reside in linux_dummy.c in a form of DUMMY(syscall);, which is then translated to various syscall auxiliary files and the implementation consists of printing a message saying that this syscall is not implemented. The UNIMPL prototype is not used because we want to be able to identify the name of the syscall that was called in order to know what syscalls are more important to implement.

4.2.1 Linux sendsig

This routine first checks whether the signal has been installed with a SA_SIGINFO in which case it calls linux_rt_sendsig routine instead. Furthermore, it allocates (or reuses an already existing) signal handle context, then it builds a list of arguments for the signal handler. It translates the signal number based on the signal translation table, assigns a handler, translates sigset. Then it saves context for the sigreturn routine (various registers, translated trap number and signal mask). Finally, it copies out the signal context to the userspace and prepares context for the actual signal handler to run.

4.2.2 linux_rt_sendsig

This routine is similar to linux_sendsig just the signal context preparation is different. It adds siginfo, ucontext, and some POSIX parts. It might be worth considering whether those two functions could not be merged with a benefit of less code duplication and possibly even faster execution.

4.2.3 linux_sigreturn

This syscall is used for return from the signal handler. It does some security checks and restores the original process context. It also unmasks the signal in process signal mask.

5.2.1 Runtime determining of 2.6 emulation

The Linux emulation layer in FreeBSD supports runtime setting of the emulated version. This is done via sysctl(8), namely compat.linux.osrelease, which is set to 2.4.2 by default (as of April 2007) and with all Linux versions up to 2.6 it just determined what uname(1) outputs. It is different with 2.6 emulation where setting this sysctl(8) affects runtime behaviour of the emulation layer. When set to 2.6.x it sets the value of linux_use_linux26 while setting to something else keeps it unset. This variable (plus per-prison variables of the very same kind) determines whether 2.6 infrastructure (mainly PID mangling) is used in the code or not. The version setting is done system-wide and this affects all Linux processes. The sysctl(8) should not be changed when running any Linux binary as it might harm things.

5.2.2 Linux processes and thread identifiers

The semantics of Linux threading are a little confusing and uses entirely different nomenclature to FreeBSD. A process in Linux consists of a struct task embedding two identifier fields - PID and TGID. PID is not a process ID but it is a thread ID. The TGID identifies a thread group in other words a process. For single-threaded process the PID equals the TGID.

The thread in NPTL is just an ordinary process that happens to have TGID not equal to PID and have a group leader not equal to itself (and shared VM etc. of course). Everything else happens in the same way as to an ordinary process. There is no separation of a shared status to some external structure like in FreeBSD. This creates some duplication of information and possible data inconsistency. The Linux kernel seems to use task -> group information in some places and task information elsewhere and it is really not very consistent and looks error-prone.

Every NPTL thread is created by a call to the clone syscall with a specific set of flags (more in the next subsection). The NPTL implements strict 1:1 threading.

In FreeBSD we emulate NPTL threads with ordinary FreeBSD processes that share VM space, etc. and the PID gymnastic is just mimicked in the emulation specific structure attached to the process. The structure attached to the process looks like:

struct linux_emuldata {
  pid_t pid;

  int *child_set_tid; /* in clone(): Child.s TID to set on clone */
  int *child_clear_tid;/* in clone(): Child.s TID to clear on exit */

  struct linux_emuldata_shared *shared;

  int pdeath_signal; /* parent death signal */

  LIST_ENTRY(linux_emuldata) threads; /* list of linux threads */
};

The PID is used to identify the FreeBSD process that attaches this structure. The child_se_tid and child_clear_tid are used for TID address copyout when a process exits and is created. The shared pointer points to a structure shared among threads. The pdeath_signal variable identifies the parent death signal and the threads pointer is used to link this structure to the list of threads. The linux_emuldata_shared structure looks like:

struct linux_emuldata_shared {

  int refs;

  pid_t group_pid;

  LIST_HEAD(, linux_emuldata) threads; /* head of list of linux threads */
};

The refs is a reference counter being used to determine when we can free the structure to avoid memory leaks. The group_pid is to identify PID ( = TGID) of the whole process ( = thread group). The threads pointer is the head of the list of threads in the process.

The linux_emuldata structure can be obtained from the process using em_find. The prototype of the function is:

struct linux_emuldata *em_find(struct proc *, int locked);

Here, proc is the process we want the emuldata structure from and the locked parameter determines whether we want to lock or not. The accepted values are EMUL_DOLOCK and EMUL_DOUNLOCK. More about locking later.

5.2.3 PID mangling

Because of the described different view knowing what a process ID and thread ID is between FreeBSD and Linux we have to translate the view somehow. We do it by PID mangling. This means that we fake what a PID (=TGID) and TID (=PID) is between kernel and userland. The rule of thumb is that in kernel (in Linuxulator) PID = PID and TGID = shared -> group pid and to userland we present PID = shared -> group_pid and TID = proc -> p_pid. The PID member of linux_emuldata structure is a FreeBSD PID.

The above affects mainly getpid, getppid, gettid syscalls. Where we use PID/TGID respectively. In copyout of TIDs in child_clear_tid and child_set_tid we copy out FreeBSD PID.

5.2.4 Clone syscall

The clone syscall is the way threads are created in Linux. The syscall prototype looks like this:

int linux_clone(l_int flags, void *stack, void *parent_tidptr, int dummy,
void * child_tidptr);

The flags parameter tells the syscall how exactly the processes should be cloned. As described above, Linux can create processes sharing various things independently, for example two processes can share file descriptors but not VM, etc. Last byte of the flags parameter is the exit signal of the newly created process. The stack parameter if non-NULL tells, where the thread stack is and if it is NULL we are supposed to copy-on-write the calling process stack (i.e. do what normal fork(2) routine does). The parent_tidptr parameter is used as an address for copying out process PID (i.e. thread id) once the process is sufficiently instantiated but is not runnable yet. The dummy parameter is here because of the very strange calling convention of this syscall on i386. It uses the registers directly and does not let the compiler do it what results in the need of a dummy syscall. The child_tidptr parameter is used as an address for copying out PID once the process has finished forking and when the process exits.

The syscall itself proceeds by setting corresponding flags depending on the flags passed in. For example, CLONE_VM maps to RFMEM (sharing of VM), etc. The only nit here is CLONE_FS and CLONE_FILES because FreeBSD does not allow setting this separately so we fake it by not setting RFFDG (copying of fd table and other fs information) if either of these is defined. This does not cause any problems, because those flags are always set together. After setting the flags the process is forked using the internal fork1 routine, the process is instrumented not to be put on a run queue, i.e. not to be set runnable. After the forking is done we possibly reparent the newly created process to emulate CLONE_PARENT semantics. Next part is creating the emulation data. Threads in Linux does not signal their parents so we set exit signal to be 0 to disable this. After that setting of child_set_tid and child_clear_tid is performed enabling the functionality later in the code. At this point we copy out the PID to the address specified by parent_tidptr. The setting of process stack is done by simply rewriting thread frame %esp register (%rsp on amd64). Next part is setting up TLS for the newly created process. After this vfork(2) semantics might be emulated and finally the newly created process is put on a run queue and copying out its PID to the parent process via clone return value is done.

The clone syscall is able and in fact is used for emulating classic fork(2) and vfork(2) syscalls. Newer glibc in a case of 2.6 kernel uses clone to implement fork(2) and vfork(2) syscalls.

5.2.5 Locking

The locking is implemented to be per-subsystem because we do not expect a lot of contention on these. There are two locks: emul_lock used to protect manipulating of linux_emuldata and emul_shared_lock used to manipulate linux_emuldata_shared. The emul_lock is a nonsleepable blocking mutex while emul_shared_lock is a sleepable blocking sx_lock. Because of the per-subsystem locking we can coalesce some locks and that is why the em find offers the non-locking access.

5.3.1 Introduction to threading

Threads in computer science are entities within a process that can be scheduled independently from each other. The threads in the process share process wide data (file descriptors, etc.) but also have their own stack for their own data. Sometimes there is a need for process-wide data specific to a given thread. Imagine a name of the thread in execution or something like that. The traditional UNIX threading API, pthreads provides a way to do it via pthread_key_create(3), pthread_setspecific(3) and pthread_getspecific(3) where a thread can create a key to the thread local data and using pthread_getspecific(3) or pthread_getspecific(3) to manipulate those data. You can easily see that this is not the most comfortable way this could be accomplished. So various producers of C/C++ compilers introduced a better way. They defined a new modifier keyword thread that specifies that a variable is thread specific. A new method of accessing such variables was developed as well (at least on i386). The pthreads method tends to be implemented in userspace as a trivial lookup table. The performance of such a solution is not very good. So the new method uses (on i386) segment registers to address a segment, where TLS area is stored so the actual accessing of a thread variable is just appending the segment register to the address thus addressing via it. The segment registers are usually %gs and %fs acting like segment selectors. Every thread has its own area where the thread local data are stored and the segment must be loaded on every context switch. This method is very fast and used almost exclusively in the whole i386 UNIX world. Both FreeBSD and Linux implement this approach and it yields very good results. The only drawback is the need to reload the segment on every context switch which can slowdown context switches. FreeBSD tries to avoid this overhead by using only 1 segment descriptor for this while Linux uses 3. Interesting thing is that almost nothing uses more than 1 descriptor (only Wine seems to use 2) so Linux pays this unnecessary price for context switches.

5.3.2 Segments on i386

The i386 architecture implements the so called segments. A segment is a description of an area of memory. The base address (bottom) of the memory area, the end of it (ceiling), type, protection, etc. The memory described by a segment can be accessed using segment selector registers (%cs, %ds, %ss, %es, %fs, %gs). For example let us suppose we have a segment which base address is 0x1234 and length and this code:

mov %edx,%gs:0x10

This will load the content of the %edx register into memory location 0x1244. Some segment registers have a special use, for example %cs is used for code segment and %ss is used for stack segment but %fs and %gs are generally unused. Segments are either stored in a global GDT table or in a local LDT table. LDT is accessed via an entry in the GDT. The LDT can store more types of segments. LDT can be per process. Both tables define up to 8191 entries.

5.3.3 Implementation on Linux i386

There are two main ways of setting up TLS in Linux. It can be set when cloning a process using the clone syscall or it can call set_thread_area. When a process passes CLONE_SETTLS flag to clone, the kernel expects the memory pointed to by the %esi register a Linux user space representation of a segment, which gets translated to the machine representation of a segment and loaded into a GDT slot. The GDT slot can be specified with a number or -1 can be used meaning that the system itself should choose the first free slot. In practice, the vast majority of programs use only one TLS entry and does not care about the number of the entry. We exploit this in the emulation and in fact depend on it.

5.3.4 Emulation of Linux TLS

5.4.1 Introduction to synchronization

Threads need some kind of synchronization and POSIX provides some of them: mutexes for mutual exclusion, read-write locks for mutual exclusion with biased ratio of reads and writes and condition variables for signaling a status change. It is interesting to note that POSIX threading API lacks support for semaphores. Those synchronization routines implementations are heavily dependant on the type threading support we have. In pure 1:M (userspace) model the implementation can be solely done in userspace and thus be very fast (the condition variables will probably end up being implemented using signals, i.e. not fast) and simple. In 1:1 model, the situation is also quite clear - the threads must be synchronized using kernel facilities (which is very slow because a syscall must be performed). The mixed M:N scenario just combines the first and second approach or rely solely on kernel. Threads synchronization is a vital part of thread-enabled programming and its performance can affect resulting program a lot. Recent benchmarks on FreeBSD operating system showed that an improved sx_lock implementation yielded 40% speedup in ZFS (a heavy sx user), this is in-kernel stuff but it shows clearly how important the performance of synchronization primitives is.

Threaded programs should be written with as little contention on locks as possible. Otherwise, instead of doing useful work the thread just waits on a lock. Because of this, the most well written threaded programs show little locks contention.

5.4.2 Futexes introduction

Linux implements 1:1 threading, i.e. it has to use in-kernel synchronization primitives. As stated earlier, well written threaded programs have little lock contention. So a typical sequence could be performed as two atomic increase/decrease mutex reference counter, which is very fast, as presented by the following example:

pthread_mutex_lock(&mutex);
....
pthread_mutex_unlock(&mutex);

1:1 threading forces us to perform two syscalls for those mutex calls, which is very slow.

The solution Linux 2.6 implements is called futexes. Futexes implement the check for contention in userspace and call kernel primitives only in a case of contention. Thus the typical case takes place without any kernel intervention. This yields reasonably fast and flexible synchronization primitives implementation.

5.4.3 Futex API

The futex syscall looks like this:

int futex(void *uaddr, int op, int val, struct timespec *timeout, void *uaddr2, int val3);

In this example uaddr is an address of the mutex in userspace, op is an operation we are about to perform and the other parameters have per-operation meaning.

Futexes implement the following operations:

• FUTEX_WAIT

• FUTEX_WAKE

• FUTEX_FD

• FUTEX_REQUEUE

• FUTEX_CMP_REQUEUE

• FUTEX_WAKE_OP

5.4.4 Futex emulation in FreeBSD

The futex emulation in FreeBSD is taken from NetBSD and further extended by us. It is placed in linux_futex.c and linux_futex.h files. The futex structure looks like:

struct futex {
  void *f_uaddr;
  int f_refcount;

  LIST_ENTRY(futex) f_list;

  TAILQ_HEAD(lf_waiting_paroc, waiting_proc) f_waiting_proc;
};

And the structure waiting_proc is:

struct waiting_proc {

  struct thread *wp_t;

  struct futex *wp_new_futex;

  TAILQ_ENTRY(waiting_proc) wp_list;
};

oldval = *uaddr2
*uaddr2 = oldval OP oparg

5.5.1 *at family of syscalls

During development of Linux 2.6.16 kernel, the *at syscalls were added. Those syscalls (openat for example) work exactly like their at-less counterparts with the slight exception of the dirfd parameter. This parameter changes where the given file, on which the syscall is to be performed, is. When the filename parameter is absolute dirfd is ignored but when the path to the file is relative, it comes to the play. The dirfd parameter is a directory relative to which the relative pathname is checked. The dirfd parameter is a file descriptor of some directory or AT_FDCWD. So for example the openat syscall can be like this:

file descriptor 123 = /tmp/foo/, current working directory = /tmp/

openat(123, /tmp/bah\, flags, mode)	/* opens /tmp/bah */
openat(123, bah\, flags, mode)		/* opens /tmp/foo/bah */
openat(AT_FDWCWD, bah\, flags, mode)	/* opens /tmp/bah */
openat(stdio, bah\, flags, mode)	/* returns error because stdio is not a directory */

This infrastructure is necessary to avoid races when opening files outside the working directory. Imagine that a process consists of two threads, thread A and thread B. Thread A issues open(./tmp/foo/bah., flags, mode) and before returning it gets preempted and thread B runs. Thread B does not care about the needs of thread A and renames or removes /tmp/foo/. We got a race. To avoid this we can open /tmp/foo and use it as dirfd for openat syscall. This also enables user to implement per-thread working directories.

Linux family of *at syscalls contains: linux_openat, linux_mkdirat, linux_mknodat, linux_fchownat, linux_futimesat, linux_fstatat64, linux_unlinkat, linux_renameat, linux_linkat, linux_symlinkat, linux_readlinkat, linux_fchmodat and linux_faccessat. All these are implemented using the modified namei(9) routine and simple wrapping layer.

openat() --> kern_openat() --> vn_open() -> namei()

5.5.2 Ioctl

The ioctl interface is quite fragile due to its generality. We have to bear in mind that devices differ between Linux and FreeBSD so some care must be applied to do ioctl emulation work right. The ioctl handling is implemented in linux_ioctl.c, where linux_ioctl function is defined. This function simply iterates over sets of ioctl handlers to find a handler that implements a given command. The ioctl syscall has three parameters, the file descriptor, command and an argument. The command is a 16-bit number, which in theory is divided into high 8 bits determining class of the ioctl command and low 8 bits, which are the actual command within the given set. The emulation takes advantage of this division. We implement handlers for each set, like sound_handler or disk_handler. Each handler has a maximum command and a minimum command defined, which is used for determining what handler is used. There are slight problems with this approach because Linux does not use the set division consistently so sometimes ioctls for a different set are inside a set they should not belong to (SCSI generic ioctls inside cdrom set, etc.). FreeBSD currently does not implement many Linux ioctls (compared to NetBSD, for example) but the plan is to port those from NetBSD. The trend is to use Linux ioctls even in the native FreeBSD drivers because of the easy porting of applications.

5.5.3 Debugging

Every syscall should be debuggable. For this purpose we introduce a small infrastructure. We have the ldebug facility, which tells whether a given syscall should be debugged (settable via a sysctl). For printing we have LMSG and ARGS macros. Those are used for altering a printable string for uniform debugging messages.