diff --git a/documentation/content/en/articles/linux-emulation/_index.adoc b/documentation/content/en/articles/linux-emulation/_index.adoc index a252df5f54..425e1b6c9f 100644 --- a/documentation/content/en/articles/linux-emulation/_index.adoc +++ b/documentation/content/en/articles/linux-emulation/_index.adoc @@ -1,1436 +1,1436 @@ --- title: Linux® emulation in FreeBSD authors: - author: Roman Divacky email: rdivacky@FreeBSD.org description: A technical description about the internals of the Linux emulation layer in FreeBSD trademarks: ["freebsd", "ibm", "adobe", "netbsd", "realnetworks", "oracle", "linux", "sun", "general"] tags: ["Emulation", "Linuxulator", "kernel", "FreeBSD"] --- = Linux(R) emulation in FreeBSD :doctype: article :toc: macro :toclevels: 1 :icons: font :sectnums: :sectnumlevels: 6 :source-highlighter: rouge :experimental: :images-path: articles/linux-emulation/ ifdef::env-beastie[] ifdef::backend-html5[] include::shared/authors.adoc[] include::shared/mirrors.adoc[] include::shared/releases.adoc[] include::shared/attributes/attributes-{{% lang %}}.adoc[] include::shared/{{% lang %}}/teams.adoc[] include::shared/{{% lang %}}/mailing-lists.adoc[] include::shared/{{% lang %}}/urls.adoc[] :imagesdir: ../../../images/{images-path} endif::[] ifdef::backend-pdf,backend-epub3[] include::../../../../shared/asciidoctor.adoc[] endif::[] endif::[] ifndef::env-beastie[] include::../../../../../shared/asciidoctor.adoc[] endif::[] [.abstract-title] Abstract This masters thesis deals with updating the Linux(R) emulation layer (the so called _Linuxulator_). The task was to update the layer to match the functionality of Linux(R) 2.6. As a reference implementation, the Linux(R) 2.6.16 kernel was chosen. The concept is loosely based on the NetBSD implementation. Most of the work was done in the summer of 2006 as a part of the Google Summer of Code students program. The focus was on bringing the _NPTL_ (new POSIX(R) thread library) support into the emulation layer, including _TLS_ (thread local storage), _futexes_ (fast user space mutexes), _PID mangling_, and some other minor things. Many small problems were identified and fixed in the process. My work was integrated into the main FreeBSD source repository and will be shipped in the upcoming 7.0R release. We, the emulation development team, are working on making the Linux(R) 2.6 emulation the default emulation layer in FreeBSD. ''' toc::[] [[intro]] == Introduction In the last few years the open source UNIX(R) based operating systems started to be widely deployed on server and client machines. Among these operating systems I would like to point out two: FreeBSD, for its BSD heritage, time proven code base and many interesting features and Linux(R) for its wide user base, enthusiastic open developer community and support from large companies. FreeBSD tends to be used on server class machines serving heavy duty networking tasks with less usage on desktop class machines for ordinary users. While Linux(R) has the same usage on servers, but it is used much more by home based users. This leads to a situation where there are many binary only programs available for Linux(R) that lack support for FreeBSD. Naturally, a need for the ability to run Linux(R) binaries on a FreeBSD system arises and this is what this thesis deals with: the emulation of the Linux(R) kernel in the FreeBSD operating system. During the Summer of 2006 Google Inc. sponsored a project which focused on extending the Linux(R) emulation layer (the so called Linuxulator) in FreeBSD to include Linux(R) 2.6 facilities. This thesis is written as a part of this project. [[inside]] == A look inside... 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(R) primitives like what a PID is, what a thread is, etc. In the third subsection we talk about how UNIX(R) on UNIX(R) emulation could be done in general. [[what-is-unix]] === What is UNIX(R) UNIX(R) 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(R) development soon forked into two main ways: the BSDs and System III/V families. They mutually influenced themselves by growing a common UNIX(R) 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(R) 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(R)-like operating systems. These days the most influential ones are Linux(R), Solaris, and possibly (to some extent) FreeBSD. There are in-company UNIX(R) derivatives (AIX, HP-UX etc.), but these have been more and more migrated to the aforementioned systems. Let us summarize typical UNIX(R) characteristics. [[tech-details]] === Technical details 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(R) API to the user space. The most important ones are covered below. [[kern-proc-comm]] ==== Communication between kernel and user space process Common UNIX(R) 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 man:swapon[2] syscall and the syscall number 132 is man:mkfifo[2]. Some syscalls need parameters, which are passed from the user-space to the kernel-space in various ways (implementation dependent). 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). [[proc-proc-comm]] ==== 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. [[proc-mgmt]] ==== Process management Kernel instances are processed first in the system (so called init). Every running process can create its identical copy using the man: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 man:exec[3] syscall. Some modifications of this syscall were introduced but all serve the same basic purpose. Processes end their lives by calling the man:exit[2] syscall. Every process is identified by a unique number called PID. Every process has a defined parent (identified by its PID). [[thread-mgmt]] ==== Thread management Traditional UNIX(R) does not define any API nor implementation for threading, while POSIX(R) 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(R) 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 [[what-is-freebsd]] === What is FreeBSD? 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(R) so it could be claimed that it is a true UNIX(R) 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(R)-based operating system with all the features of UNIX(R). 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(R)-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(R)-emulation of Linux(R) 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(R) Actively developed emulations are the Linux(R) layer and various FreeBSD-on-FreeBSD layers. Others are not supposed to work properly nor be usable these days. [[freebsd-tech-details]] ==== Technical details FreeBSD is traditional flavor of UNIX(R) 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-sys-entries]] ===== System entries FreeBSD has an abstraction called an execution class loader, which is a wedge into the man: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. [[freebsd-syscalls]] ===== Syscalls 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 [.filename]#sys/i386/i386/exception.s#), which prepares arguments (i.e. copies them on to the stack) for a call to a C function man:syscall[2] (defined in [.filename]#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. [[freebsd-traps]] ===== Traps 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 [.filename]#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()`. [[freebsd-exits]] ===== Exits 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-unix-primitives]] ===== UNIX(R) primitives FreeBSD operating system adheres to the traditional UNIX(R) 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 man: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. Due to 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). [[what-is-linux]] === What is Linux(R) Linux(R) is a UNIX(R)-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 today, with wide support from companies such as IBM or Google, Linux(R) is being associated with its fast development pace, full hardware support and benevolent dictator model of organization. Linux(R) 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(R)-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(R) 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(R) can only be obtained in a binary form so recompilation for other operating systems is impossible. Most of the Linux(R) development happens in a Git version control system. Git is a distributed system so there is no central source of the Linux(R) code, but some branches are considered prominent and official. The version number scheme implemented by Linux(R) 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 [3]. [[linux-tech-details]] ==== Technical details Linux(R) follows the traditional UNIX(R) 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(R) 2.6 on the i386(TM) architecture. This information was taken from [2]. [[linux-syscalls]] ===== Syscalls Syscalls in Linux(R) 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(R) 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(R) uses different calling convention (most notably the `clone` syscall). [[linux-traps]] ===== Traps The trap handlers are introduced in [.filename]#arch/i386/kernel/traps.c# and most of these handlers live in [.filename]#arch/i386/kernel/entry.S#, where handling of the traps happens. [[linux-exits]] ===== Exits Return from the syscall is managed by syscall man: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. [[linux-unix-primitives]] ===== UNIX(R) primitives In the 2.6 version, the Linux(R) operating system redefined some of the traditional UNIX(R) primitives, notably PID, TID and thread. PID is defined not to be unique for every process, so for some processes (threads) man:getppid[2] returns the same value. Unique identification of process is provided by TID. This is because _NPTL_ (New POSIX(R) Thread Library) defines threads to be normal processes (so called 1:1 threading). Spawning a new process in Linux(R) 2.6 happens using the `clone` syscall (fork variants are reimplemented using it). This clone syscall defines a set of flags that affect behavior 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 man:pthread_create[3] in NPTL defines the clone flags like this: [.programlisting] .... 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 [.programlisting] .... #define CLONE_SIGNAL (CLONE_SIGHAND | CLONE_THREAD) .... the last 0 means no signal is sent when any of the threads exits. [[what-is-emu]] === What is emulation 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(R) on UNIX(R), which is exactly the case, where only a thin layer of translation is sufficient to provide full emulation. The UNIX(R) 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(R) API. Most programs can live with a very limited set of syscalls working. Those syscalls tend to be the oldest ones (man:read[2]/man:write[2], man:fork[2] family, man:signal[3] handling, man:exit[3], man:socket[2] API) hence it is easy to emulate because their semantics is shared among all UNIX(R)es, which exist todays. [[freebsd-emulation]] == Emulation === How emulation works in FreeBSD As stated earlier, FreeBSD supports running binaries from several other UNIX(R)es. This works because FreeBSD has an abstraction called the execution class loader. This wedges into the man:execve[2] syscall, so when man:execve[2] is about to execute a binary it examines its type. There are basically two types of binaries in FreeBSD. Shell-like text scripts which are identified by `#!` as their first two characters and normal (typically _ELF_) binaries, which are a representation of a compiled executable object. The vast majority (one could say all of them) of binaries in FreeBSD are from type ELF. ELF files contain a header, which specifies the OS ABI for this ELF file. By reading this information, the operating system can accurately determine what type of binary the given file is. Every OS ABI must be registered in the FreeBSD kernel. This applies to the FreeBSD native OS ABI, as well. So when man:execve[2] executes a binary it iterates through the list of registered APIs and when it finds the right one it starts to use the information contained in the OS ABI description (its syscall table, `errno` translation table, etc.). So every time the process calls a syscall, it uses its own set of syscalls instead of some global one. This effectively provides a very elegant and easy way of supporting execution of various binary formats. The nature of emulation of different OSes (and also some other subsystems) led developers to invite a handler event mechanism. There are various places in the kernel, where a list of event handlers are called. Every subsystem can register an event handler and they are called accordingly. For example, when a process exits there is a handler called that possibly cleans up whatever the subsystem needs to be cleaned. Those simple facilities provide basically everything that is needed for the emulation infrastructure and in fact these are basically the only things necessary to implement the Linux(R) emulation layer. [[freebsd-common-primitives]] === Common primitives in the FreeBSD kernel Emulation layers need some support from the operating system. I am going to describe some of the supported primitives in the FreeBSD operating system. [[freebsd-locking-primitives]] ==== Locking primitives Contributed by: `{attilio}` 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. [[freebsd-atomic-op]] ===== Atomic operations and memory barriers Atomic operations are implemented through a set of functions performing simple arithmetics on memory operands in an atomic way with respect to external events (interrupts, preemption, etc.). Atomic operations can guarantee atomicity just on small data types (in the magnitude order of the `.long.` architecture C data type), so should be rarely used directly in the end-level code, if not only for very simple operations (like flag setting in a bitmap, for example). In fact, it is rather simple and common to write down a wrong semantic based on just atomic operations (usually referred as lock-less). The FreeBSD kernel offers a way to perform atomic operations in conjunction with a memory barrier. The memory barriers will guarantee that an atomic operation will happen following some specified ordering with respect to other memory accesses. For example, if we need that an atomic operation happen just after all other pending writes (in terms of instructions reordering buffers activities) are completed, we need to explicitly use a memory barrier in conjunction to this atomic operation. So it is simple to understand why memory barriers play a key role for higher-level locks building (just as refcounts, mutexes, etc.). For a detailed explanatory on atomic operations, please refer to man:atomic[9]. It is far, however, noting that atomic operations (and memory barriers as well) should ideally only be used for building front-ending locks (as mutexes). [[freebsd-refcounts]] ===== Refcounts Refcounts are interfaces for handling reference counters. They are implemented through atomic operations and are intended to be used just for cases, where the reference counter is the only one thing to be protected, so even something like a spin-mutex is deprecated. Using the refcount interface for structures, where a mutex is already used is often wrong since we should probably close the reference counter in some already protected paths. A manpage discussing refcount does not exist currently, just check [.filename]#sys/refcount.h# for an overview of the existing API. [[freebsd-locks]] ===== Locks FreeBSD kernel has huge classes of locks. Every lock is defined by some peculiar properties, but probably the most important is the event linked to contesting holders (or in other terms, the behavior of threads unable to acquire the lock). FreeBSD's locking scheme presents three different behaviors for contenders: . spinning . blocking . sleeping [NOTE] ==== numbers are not casual ==== [[freebsd-spinlocks]] ===== Spinning locks Spin locks let waiters to spin until they cannot acquire the lock. An important matter do deal with is when a thread contests on a spin lock if it is not descheduled. Since the FreeBSD kernel is preemptive, this exposes spin lock at the risk of deadlocks that can be solved just disabling interrupts while they are acquired. For this and other reasons (like lack of priority propagation support, poorness in load balancing schemes between CPUs, etc.), spin locks are intended to protect very small paths of code, or ideally not to be used at all if not explicitly requested (explained later). [[freebsd-blocking]] ===== Blocking Block locks let waiters to be descheduled and blocked until the lock owner does not drop it and wakes up one or more contenders. To avoid starvation issues, blocking locks do priority propagation from the waiters to the owner. Block locks must be implemented through the turnstile interface and are intended to be the most used kind of locks in the kernel, if no particular conditions are met. [[freebsd-sleeping]] ===== Sleeping Sleep locks let waiters to be descheduled and fall asleep until the lock holder does not drop it and wakes up one or more waiters. Since sleep locks are intended to protect large paths of code and to cater asynchronous events, they do not do any form of priority propagation. They must be implemented through the man:sleepqueue[9] interface. The order used to acquire locks is very important, not only for the possibility to deadlock due at lock order reversals, but even because lock acquisition should follow specific rules linked to locks natures. If you give a look at the table above, the practical rule is that if a thread holds a lock of level n (where the level is the number listed close to the kind of lock) it is not allowed to acquire a lock of superior levels, since this would break the specified semantic for a path. For example, if a thread holds a block lock (level 2), it is allowed to acquire a spin lock (level 1) but not a sleep lock (level 3), since block locks are intended to protect smaller paths than sleep lock (these rules are not about atomic operations or scheduling barriers, however). This is a list of lock with their respective behaviors: * spin mutex - spinning - man:mutex[9] * sleep mutex - blocking - man:mutex[9] * pool mutex - blocking - man:mtx[pool] * sleep family - sleeping - man:sleep[9] pause tsleep msleep msleep spin msleep rw msleep sx * condvar - sleeping - man:condvar[9] * rwlock - blocking - man:rwlock[9] * sxlock - sleeping - man:sx[9] * lockmgr - sleeping - man:lockmgr[9] * semaphores - sleeping - man:sema[9] Among these locks only mutexes, sxlocks, rwlocks and lockmgrs are intended to handle recursion, but currently recursion is only supported by mutexes and lockmgrs. [[freebsd-scheduling]] ===== Scheduling barriers Scheduling barriers are intended to be used to drive scheduling of threading. They consist mainly of three different stubs: * critical sections (and preemption) * sched_bind * sched_pin Generally, these should be used only in a particular context and even if they can often replace locks, they should be avoided because they do not let the diagnose of simple eventual problems with locking debugging tools (as man:witness[4]). [[freebsd-critical]] ===== Critical sections The FreeBSD kernel has been made preemptive basically to deal with interrupt threads. In fact, to avoid high interrupt latency, time-sharing priority threads can be preempted by interrupt threads (in this way, they do not need to wait to be scheduled as the normal path previews). Preemption, however, introduces new racing points that need to be handled, as well. Often, to deal with preemption, the simplest thing to do is to completely disable it. A critical section defines a piece of code (borderlined by the pair of functions man:critical_enter[9] and man:critical_exit[9], where preemption is guaranteed to not happen (until the protected code is fully executed). This can often replace a lock effectively but should be used carefully to not lose the whole advantage that preemption brings. [[freebsd-schedpin]] ===== sched_pin/sched_unpin Another way to deal with preemption is the `sched_pin()` interface. If a piece of code is closed in the `sched_pin()` and `sched_unpin()` pair of functions it is guaranteed that the respective thread, even if it can be preempted, it will always be executed on the same CPU. Pinning is very effective in the particular case when we have to access at per-cpu datas and we assume other threads will not change those data. The latter condition will determine a critical section as a too strong condition for our code. [[freebsd-schedbind]] ===== sched_bind/sched_unbind `sched_bind` is an API used to bind a thread to a particular CPU for all the time it executes the code, until a `sched_unbind` function call does not unbind it. This feature has a key role in situations where you cannot trust the current state of CPUs (for example, at very early stages of boot), as you want to avoid your thread to migrate on inactive CPUs. Since `sched_bind` and `sched_unbind` manipulate internal scheduler structures, they need to be enclosed in `sched_lock` acquisition/releasing when used. [[freebsd-proc]] ==== 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: [.programlisting] .... if (__predict_true(p->p_sysent != &elf_Linux(R)_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 Linux(R)64 emulation nor A.OUT Linux(R) processes on i386. [[freebsd-vfs]] ==== VFS The FreeBSD VFS subsystem is very complex but the Linux(R) 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. [[freebsd-namei]] ===== namei The man:namei[9] routine is a central entry point to pathname lookup and translation. It traverses the path point by point from the starting point to the end point using lookup function, which is internal to VFS. The man:namei[9] syscall can cope with symlinks, absolute and relative paths. When a path is looked up using man:namei[9] it is inputed to the name cache. This behavior can be suppressed. This routine is used all over the kernel and its performance is very critical. [[freebsd-vn]] ===== vn_fullpath The man:vn_fullpath[9] function takes the best effort to traverse VFS name cache and returns a path for a given (locked) vnode. This process is unreliable but works just fine for the most common cases. The unreliability is because it relies on VFS cache (it does not traverse the on medium structures), it does not work with hardlinks, etc. This routine is used in several places in the Linuxulator. [[freebsd-vnode]] ===== Vnode operations * `fgetvp` - given a thread and a file descriptor number it returns the associated vnode * man:vn_lock[9] - locks a vnode * `vn_unlock` - unlocks a vnode * man:VOP_READDIR[9] - reads a directory referenced by a vnode * man:VOP_GETATTR[9] - gets attributes of a file or a directory referenced by a vnode * man:VOP_LOOKUP[9] - looks up a path to a given directory * man:VOP_OPEN[9] - opens a file referenced by a vnode * man:VOP_CLOSE[9] - closes a file referenced by a vnode * man:vput[9] - decrements the use count for a vnode and unlocks it * man:vrele[9] - decrements the use count for a vnode * man:vref[9] - increments the use count for a vnode [[freebsd-file-handler]] ===== File handler operations * `fget` - given a thread and a file descriptor number it returns associated file handler and references it * `fdrop` - drops a reference to a file handler * `fhold` - references a file handler [[md]] == Linux(R) emulation layer -MD part This section deals with implementation of Linux(R) emulation layer in FreeBSD operating system. It first describes the machine dependent part talking about how and where interaction between userland and kernel is implemented. It talks about syscalls, signals, ptrace, traps, stack fixup. This part discusses i386 but it is written generally so other architectures should not differ very much. The next part is the machine independent part of the Linuxulator. This section only covers i386 and ELF handling. A.OUT is obsolete and untested. [[syscall-handling]] === Syscall handling Syscall handling is mostly written in [.filename]#linux_sysvec.c#, which covers most of the routines pointed out in the `sysentvec` structure. When a Linux(R) process running on FreeBSD issues a syscall, the general syscall routine calls linux prepsyscall routine for the Linux(R) ABI. [[linux-prepsyscall]] ==== Linux(R) prepsyscall Linux(R) passes arguments to syscalls via registers (that is why it is limited to 6 parameters on i386) while FreeBSD uses the stack. The Linux(R) 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. [[syscall-writing]] ==== Syscall writing Every syscall implemented in the Linuxulator must have its prototype with various flags in [.filename]#syscalls.master#. The form of the file is: [.programlisting] .... ... 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 [.filename]#syscalls.master# a script generates three files: [.filename]#linux_syscall.h#, [.filename]#linux_proto.h# and [.filename]#linux_sysent.c#. The [.filename]#linux_syscall.h# contains definitions of syscall names and their numerical value, e.g.: [.programlisting] .... ... #define LINUX_SYS_linux_fork 2 ... #define LINUX_SYS_close 6 ... .... The [.filename]#linux_proto.h# contains structure definitions of arguments to every syscall, e.g.: [.programlisting] .... struct linux_fork_args { register_t dummy; }; .... And finally, [.filename]#linux_sysent.c# contains structure describing the system entry table, used to actually dispatch a syscall, e.g.: [.programlisting] .... { 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 man: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 man:close[2] in the kernel. [[dummy-syscalls]] ==== Dummy syscalls The Linux(R) 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 [.filename]#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 to know what syscalls are more important to implement. [[signal-handling]] === Signal handling Signal handling is done generally in the FreeBSD kernel for all binary compatibilities with a call to a compat-dependent layer. Linux(R) compatibility layer defines `linux_sendsig` routine for this purpose. [[linux-sendsig]] ==== Linux(R) 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. [[linux-rt-sendsig]] ==== linux_rt_sendsig This routine is similar to `linux_sendsig` just the signal context preparation is different. It adds `siginfo`, `ucontext`, and some POSIX(R) 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. [[linux-sigreturn]] ==== 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. [[ptrace]] === Ptrace Many UNIX(R) derivates implement the man:ptrace[2] syscall to allow various tracking and debugging features. This facility enables the tracing process to obtain various information about the traced process, like register dumps, any memory from the process address space, etc. and also to trace the process like in stepping an instruction or between system entries (syscalls and traps). man:ptrace[2] also lets you set various information in the traced process (registers etc.). man:ptrace[2] is a UNIX(R)-wide standard implemented in most UNIX(R)es around the world. Linux(R) emulation in FreeBSD implements the man:ptrace[2] facility in [.filename]#linux_ptrace.c#. The routines for converting registers between Linux(R) and FreeBSD and the actual man:ptrace[2] syscall emulation syscall. The syscall is a long switch block that implements its counterpart in FreeBSD for every man:ptrace[2] command. The man:ptrace[2] commands are mostly equal between Linux(R) and FreeBSD so usually just a small modification is needed. For example, `PT_GETREGS` in Linux(R) operates on direct data while FreeBSD uses a pointer to the data so after performing a (native) man:ptrace[2] syscall, a copyout must be done to preserve Linux(R) semantics. The man:ptrace[2] implementation in Linuxulator has some known weaknesses. There have been panics seen when using `strace` (which is a man:ptrace[2] consumer) in the Linuxulator environment. Also `PT_SYSCALL` is not implemented. [[traps]] === Traps Whenever a Linux(R) process running in the emulation layer traps the trap itself is handled transparently with the only exception of the trap translation. Linux(R) and FreeBSD differs in opinion on what a trap is so this is dealt with here. The code is actually very short: [.programlisting] .... static int translate_traps(int signal, int trap_code) { if (signal != SIGBUS) return signal; switch (trap_code) { case T_PROTFLT: case T_TSSFLT: case T_DOUBLEFLT: case T_PAGEFLT: return SIGSEGV; default: return signal; } } .... [[stack-fixup]] === Stack fixup The RTLD run-time link-editor expects so called AUX tags on stack during an `execve` so a fixup must be done to ensure this. Of course, every RTLD system is different so the emulation layer must provide its own stack fixup routine to do this. So does Linuxulator. The `elf_linux_fixup` simply copies out AUX tags to the stack and adjusts the stack of the user space process to point right after those tags. So RTLD works in a smart way. [[aout-support]] === A.OUT support The Linux(R) emulation layer on i386 also supports Linux(R) A.OUT binaries. Pretty much everything described in the previous sections must be implemented for A.OUT support (beside traps translation and signals sending). The support for A.OUT binaries is no longer maintained, especially the 2.6 emulation does not work with it but this does not cause any problem, as the linux-base in ports probably do not support A.OUT binaries at all. This support will probably be removed in future. Most of the stuff necessary for loading Linux(R) A.OUT binaries is in [.filename]#imgact_linux.c# file. [[mi]] == Linux(R) emulation layer -MI part This section talks about machine independent part of the Linuxulator. It covers the emulation infrastructure needed for Linux(R) 2.6 emulation, the thread local storage (TLS) implementation (on i386) and futexes. Then we talk briefly about some syscalls. [[nptl-desc]] === Description of NPTL One of the major areas of progress in development of Linux(R) 2.6 was threading. Prior to 2.6, the Linux(R) threading support was implemented in the linuxthreads library. The library was a partial implementation of POSIX(R) threading. The threading was implemented using separate processes for each thread using the `clone` syscall to let them share the address space (and other things). The main weaknesses of this approach was that every thread had a different PID, signal handling was broken (from the pthreads perspective), etc. Also the performance was not very good (use of `SIGUSR` signals for threads synchronization, kernel resource consumption, etc.) so to overcome these problems a new threading system was developed and named NPTL. The NPTL library focused on two things but a third thing came along so it is usually considered a part of NPTL. Those two things were embedding of threads into a process structure and futexes. The additional third thing was TLS, which is not directly required by NPTL but the whole NPTL userland library depends on it. Those improvements yielded in much improved performance and standards conformance. NPTL is a standard threading library in Linux(R) systems these days. The FreeBSD Linuxulator implementation approaches the NPTL in three main areas. The TLS, futexes and PID mangling, which is meant to simulate the Linux(R) threads. Further sections describe each of these areas. [[linux26-emu]] === Linux(R) 2.6 emulation infrastructure These sections deal with the way Linux(R) threads are managed and how we simulate that in FreeBSD. [[linux26-runtime]] ==== Runtime determining of 2.6 emulation The Linux(R) emulation layer in FreeBSD supports runtime setting of the emulated version. This is done via man:sysctl[8], namely `compat.linux.osrelease`. Setting this man:sysctl[8] affects runtime behavior 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(R) processes. The man:sysctl[8] should not be changed when running any Linux(R) binary as it might harm things. [[linux-proc-thread]] ==== Linux(R) processes and thread identifiers The semantics of Linux(R) threading are a little confusing and uses entirely different nomenclature to FreeBSD. A process in Linux(R) 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(R) 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: [.programlisting] .... 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: [.programlisting] .... 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: [.programlisting] .... 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. [[pid-mangling]] ==== PID mangling As there is a difference in view as what to the idea of a process ID and thread ID is between FreeBSD and Linux(R) 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. [[clone-syscall]] ==== Clone syscall The `clone` syscall is the way threads are created in Linux(R). The syscall prototype looks like this: [.programlisting] .... 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(R) 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 man: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(R) 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 man: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 man:fork[2] and man:vfork[2] syscalls. Newer glibc in a case of 2.6 kernel uses `clone` to implement man:fork[2] and man:vfork[2] syscalls. [[locking]] ==== 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`. Due to of the per-subsystem locking we can coalesce some locks and that is why the em find offers the non-locking access. [[tls]] === TLS This section deals with TLS also known as thread local storage. [[trheading-intro]] ==== 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(R) threading API, pthreads provides a way to do it via man:pthread_key_create[3], man:pthread_setspecific[3] and man:pthread_getspecific[3] where a thread can create a key to the thread local data and using man:pthread_getspecific[3] or man: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(R) world. Both FreeBSD and Linux(R) 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(R) uses 3. Interesting thing is that almost nothing uses more than 1 descriptor (only Wine seems to use 2) so Linux(R) pays this unnecessary price for context switches. [[i386-segs]] ==== 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: [.programlisting] .... 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. [[linux-i386]] ==== Implementation on Linux(R) i386 There are two main ways of setting up TLS in Linux(R). 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(R) 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. [[tls-emu]] ==== Emulation of Linux(R) TLS [[tls-i386]] ===== i386 Loading of TLS for the current thread happens by calling `set_thread_area` while loading TLS for a second process in `clone` is done in the separate block in `clone`. Those two functions are very similar. The only difference being the actual loading of the GDT segment, which happens on the next context switch for the newly created process while `set_thread_area` must load this directly. The code basically does this. It copies the Linux(R) form segment descriptor from the userland. The code checks for the number of the descriptor but because this differs between FreeBSD and Linux(R) we fake it a little. We only support indexes of 6, 3 and -1. The 6 is genuine Linux(R) number, 3 is genuine FreeBSD one and -1 means autoselection. Then we set the descriptor number to constant 3 and copy out this to the userspace. We rely on the userspace process using the number from the descriptor but this works most of the time (have never seen a case where this did not work) as the userspace process typically passes in 1. Then we convert the descriptor from the Linux(R) form to a machine dependant form (i.e. operating system independent form) and copy this to the FreeBSD defined segment descriptor. Finally we can load it. We assign the descriptor to threads PCB (process control block) and load the `%gs` segment using `load_gs`. This loading must be done in a critical section so that nothing can interrupt us. The `CLONE_SETTLS` case works exactly like this just the loading using `load_gs` is not performed. The segment used for this (segment number 3) is shared for this use between FreeBSD processes and Linux(R) processes so the Linux(R) emulation layer does not add any overhead over plain FreeBSD. [[tls-amd64]] ===== amd64 The amd64 implementation is similar to the i386 one but there was initially no 32bit segment descriptor used for this purpose (hence not even native 32bit TLS users worked) so we had to add such a segment and implement its loading on every context switch (when a flag signaling use of 32bit is set). Apart from this the TLS loading is exactly the same just the segment numbers are different and the descriptor format and the loading differs slightly. [[futexes]] === Futexes [[sync-intro]] ==== Introduction to synchronization Threads need some kind of synchronization and POSIX(R) 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(R) 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. As a result of this, the most well written threaded programs show little locks contention. [[futex-intro]] ==== Futexes introduction Linux(R) 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: [.programlisting] .... 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(R) 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. [[futex-api]] ==== Futex API The futex syscall looks like this: [.programlisting] .... 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` [[futex-wait]] ===== FUTEX_WAIT This operation verifies that on address `uaddr` the value `val` is written. If not, `EWOULDBLOCK` is returned, otherwise the thread is queued on the futex and gets suspended. If the argument `timeout` is non-zero it specifies the maximum time for the sleeping, otherwise the sleeping is infinite. [[futex-wake]] ===== FUTEX_WAKE This operation takes a futex at `uaddr` and wakes up `val` first futexes queued on this futex. [[futex-fd]] ===== FUTEX_FD This operations associates a file descriptor with a given futex. [[futex-requeue]] ===== FUTEX_REQUEUE This operation takes `val` threads queued on futex at `uaddr`, wakes them up, and takes `val2` next threads and requeues them on futex at `uaddr2`. [[futex-cmp-requeue]] ===== FUTEX_CMP_REQUEUE This operation does the same as `FUTEX_REQUEUE` but it checks that `val3` equals to `val` first. [[futex-wake-op]] ===== FUTEX_WAKE_OP This operation performs an atomic operation on `val3` (which contains coded some other value) and `uaddr`. Then it wakes up `val` threads on futex at `uaddr` and if the atomic operation returned a positive number it wakes up `val2` threads on futex at `uaddr2`. The operations implemented in `FUTEX_WAKE_OP`: * `FUTEX_OP_SET` * `FUTEX_OP_ADD` * `FUTEX_OP_OR` * `FUTEX_OP_AND` * `FUTEX_OP_XOR` [NOTE] ==== There is no `val2` parameter in the futex prototype. The `val2` is taken from the `struct timespec *timeout` parameter for operations `FUTEX_REQUEUE`, `FUTEX_CMP_REQUEUE` and `FUTEX_WAKE_OP`. ==== [[futex-emu]] ==== 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 [.filename]#linux_futex.h# files. The `futex` structure looks like: [.programlisting] .... 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: [.programlisting] .... struct waiting_proc { struct thread *wp_t; struct futex *wp_new_futex; TAILQ_ENTRY(waiting_proc) wp_list; }; .... [[futex-get]] ===== futex_get / futex_put A futex is obtained using the `futex_get` function, which searches a linear list of futexes and returns the found one or creates a new futex. When releasing a futex from the use we call the `futex_put` function, which decreases a reference counter of the futex and if the refcount reaches zero it is released. [[futex-sleep]] ===== futex_sleep When a futex queues a thread for sleeping it creates a `working_proc` structure and puts this structure to the list inside the futex structure then it just performs a man:tsleep[9] to suspend the thread. The sleep can be timed out. After man:tsleep[9] returns (the thread was woken up or it timed out) the `working_proc` structure is removed from the list and is destroyed. All this is done in the `futex_sleep` function. If we got woken up from `futex_wake` we have `wp_new_futex` set so we sleep on it. This way the actual requeueing is done in this function. [[futex-wake-2]] ===== futex_wake Waking up a thread sleeping on a futex is performed in the `futex_wake` function. First in this function we mimic the strange Linux(R) behavior, where it wakes up N threads for all operations, the only exception is that the REQUEUE operations are performed on N+1 threads. But this usually does not make any difference as we are waking up all threads. Next in the function in the loop we wake up n threads, after this we check if there is a new futex for requeueing. If so, we requeue up to n2 threads on the new futex. This cooperates with `futex_sleep`. [[futex-wake-op-2]] ===== futex_wake_op The `FUTEX_WAKE_OP` operation is quite complicated. First we obtain two futexes at addresses `uaddr` and `uaddr2` then we perform the atomic operation using `val3` and `uaddr2`. Then `val` waiters on the first futex is woken up and if the atomic operation condition holds we wake up `val2` (i.e. `timeout`) waiter on the second futex. [[futex-atomic-op]] ===== futex atomic operation The atomic operation takes two parameters `encoded_op` and `uaddr`. The encoded operation encodes the operation itself, comparing value, operation argument, and comparing argument. The pseudocode for the operation is like this one: [.programlisting] .... oldval = *uaddr2 *uaddr2 = oldval OP oparg .... And this is done atomically. First a copying in of the number at `uaddr` is performed and the operation is done. The code handles page faults and if no page fault occurs `oldval` is compared to `cmparg` argument with cmp comparator. [[futex-locking]] ===== Futex locking Futex implementation uses two lock lists protecting `sx_lock` and global locks (either Giant or another `sx_lock`). Every operation is performed locked from the start to the very end. [[syscall-impl]] === Various syscalls implementation In this section I am going to describe some smaller syscalls that are worth mentioning because their implementation is not obvious or those syscalls are interesting from other point of view. [[syscall-at]] ==== *at family of syscalls During development of Linux(R) 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: [.programlisting] .... 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 [.filename]#/tmp/foo/#. We got a race. To avoid this we can open [.filename]#/tmp/foo# and use it as `dirfd` for `openat` syscall. This also enables user to implement per-thread working directories. Linux(R) 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 man:namei[9] routine and simple wrapping layer. [[implementation]] ===== Implementation The implementation is done by altering the man:namei[9] routine (described above) to take additional parameter `dirfd` in its `nameidata` structure, which specifies the starting point of the pathname lookup instead of using the current working directory every time. The resolution of `dirfd` from file descriptor number to a vnode is done in native *at syscalls. When `dirfd` is `AT_FDCWD` the `dvp` entry in `nameidata` structure is `NULL` but when `dirfd` is a different number we obtain a file for this file descriptor, check whether this file is valid and if there is vnode attached to it then we get a vnode. Then we check this vnode for being a directory. In the actual man:namei[9] routine we simply substitute the `dvp` vnode for `dp` variable in the man:namei[9] function, which determines the starting point. The man:namei[9] is not used directly but via a trace of different functions on various levels. For example the `openat` goes like this: [.programlisting] .... openat() --> kern_openat() --> vn_open() -> namei() .... For this reason `kern_open` and `vn_open` must be altered to incorporate the additional `dirfd` parameter. No compat layer is created for those because there are not many users of this and the users can be easily converted. This general implementation enables FreeBSD to implement their own *at syscalls. This is being discussed right now. [[ioctl]] ==== Ioctl The ioctl interface is quite fragile due to its generality. We have to bear in mind that devices differ between Linux(R) and FreeBSD so some care must be applied to do ioctl emulation work right. The ioctl handling is implemented in [.filename]#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(R) 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(R) ioctls (compared to NetBSD, for example) but the plan is to port those from NetBSD. The trend is to use Linux(R) ioctls even in the native FreeBSD drivers because of the easy porting of applications. [[debugging]] ==== 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. [[conclusion]] == Conclusion [[results]] === Results As of April 2007 the Linux(R) emulation layer is capable of emulating the Linux(R) 2.6.16 kernel quite well. The remaining problems concern futexes, unfinished *at family of syscalls, problematic signals delivery, missing `epoll` and `inotify` and probably some bugs we have not discovered yet. Despite this we are capable of running basically all the Linux(R) programs included in FreeBSD Ports Collection with Fedora Core 4 at 2.6.16 and there are some rudimentary reports of success with Fedora Core 6 at 2.6.16. The Fedora Core 6 linux_base was recently committed enabling some further testing of the emulation layer and giving us some more hints where we should put our effort in implementing missing stuff. We are able to run the most used applications like package:www/linux-firefox[], package:net-im/skype[] and some games from the Ports Collection. Some of the programs exhibit bad behavior under 2.6 emulation but this is currently under investigation and hopefully will be fixed soon. The only big application that is known not to work is the Linux(R) Java(TM) Development Kit and this is because of the requirement of `epoll` facility which is not directly related to the Linux(R) kernel 2.6. We hope to enable 2.6.16 emulation by default some time after FreeBSD 7.0 is released at least to expose the 2.6 emulation parts for some wider testing. Once this is done we can switch to Fedora Core 6 linux_base, which is the ultimate plan. [[future-work]] === Future work Future work should focus on fixing the remaining issues with futexes, implement the rest of the *at family of syscalls, fix the signal delivery and possibly implement the `epoll` and `inotify` facilities. We hope to be able to run the most important programs flawlessly soon, so we will be able to switch to the 2.6 emulation by default and make the Fedora Core 6 the default linux_base because our currently used Fedora Core 4 is not supported any more. The other possible goal is to share our code with NetBSD and DragonflyBSD. NetBSD has some support for 2.6 emulation but its far from finished and not really tested. DragonflyBSD has expressed some interest in porting the 2.6 improvements. Generally, as Linux(R) develops we would like to keep up with their development, implementing newly added syscalls. Splice comes to mind first. Some already implemented syscalls are also suboptimal, for example `mremap` and others. Some performance improvements can also be made, finer grained locking and others. [[team]] === Team I cooperated on this project with (in alphabetical order): * `{jhb}` * `{kib}` * Emmanuel Dreyfus * Scot Hetzel * `{jkim}` * `{netchild}` * `{ssouhlal}` * Li Xiao * `{davidxu}` I would like to thank all those people for their advice, code reviews and general support. [[literatures]] == Literatures -. Marshall Kirk McKusick - George V. Nevile-Neil. Design and Implementation of the FreeBSD operating system. Addison-Wesley, 2005. +. Marshall Kirk McKusick - George V. Neville-Neil. Design and Implementation of the FreeBSD operating system. Addison-Wesley, 2005. . https://tldp.org[https://tldp.org] . https://www.kernel.org[https://www.kernel.org] diff --git a/documentation/content/es/articles/linux-emulation/_index.adoc b/documentation/content/es/articles/linux-emulation/_index.adoc index 19b4c23c12..14772edc88 100644 --- a/documentation/content/es/articles/linux-emulation/_index.adoc +++ b/documentation/content/es/articles/linux-emulation/_index.adoc @@ -1,973 +1,973 @@ --- authors: - author: 'Roman Divacky' email: rdivacky@FreeBSD.org description: 'Una descripción técnica acerca del funcionamiento interno de la capa de emulación Linux en FreeBSD' tags: ["Emulation", "Linuxulator", "kernel", "FreeBSD"] title: 'Emulación Linux(R) en FreeBSD' trademarks: ["freebsd", "ibm", "adobe", "netbsd", "realnetworks", "oracle", "linux", "sun", "general"] --- = Emulación Linux(R) en FreeBSD :doctype: article :toc: macro :toclevels: 1 :icons: font :sectnums: :sectnumlevels: 6 :source-highlighter: rouge :experimental: :images-path: articles/linux-emulation/ ifdef::env-beastie[] ifdef::backend-html5[] include::shared/authors.adoc[] include::shared/mirrors.adoc[] include::shared/releases.adoc[] include::shared/attributes/attributes-{{% lang %}}.adoc[] include::shared/{{% lang %}}/teams.adoc[] include::shared/{{% lang %}}/mailing-lists.adoc[] include::shared/{{% lang %}}/urls.adoc[] :imagesdir: ../../../images/{images-path} endif::[] ifdef::backend-pdf,backend-epub3[] include::../../../../shared/asciidoctor.adoc[] endif::[] endif::[] ifndef::env-beastie[] include::../../../../../shared/asciidoctor.adoc[] endif::[] [.abstract-title] Resumen Esta tesis doctoral trata sobre cómo actualizar la capa de emulación de Linux(R) (también llamada _Linuxulator_). La tarea consistía en actualizar dicha capa para alcanzar en funcionalidad a Linux(R) 2.6. Como implementación de referencia se escogió el kernel Linux(R) 2.6.16. El concepto se basa ligeramente en la implementación de NetBSD. La mayoría del trabajo se realizó en el verano de 2006 como parte del programa de estudiantes Google Summer of Code. El foco se situó en añadir soporte para _NPTL_ (la nueva librería de hilos POSIX(R)) a la capa de emulación, incluyento _TLS_ (almacenamiento local para hilos), _futexes_ (mutex rápidos en espacio de usuario), _PID mangling_ y otras cosas menores. En el proceso se identificaron y arreglaron muchos problemas menores. Mi trabajo se integró en el repositorio fuente principal de FreeBSD y estará disponible en la próxima versión 7.0R. Los miembros del equipo de desarrollo de emulación estamos trabajando para que la emulación de Linux(R) 2.6 sea la capa de emulación por defecto en FreeBSD. ''' toc::[] [[intro]] == Introducción En los últimos años, los sistemas operativos basados en el código abierto de UNIX(R) han empezado a ser desplegados ampliamente tanto en máquinas cliente como servidores. Entre estos sistemas operativos me gustaría resaltar dos: FreeBSD, por su herencia BSD, base de código que resiste el paso del tiempo y por tener muchas características interesantes y Linux(R) por su amplio número de usuarios, comunidad de desarrolladores entusiasta y abierta y el apoyo de grandes corporaciones. FreeBSD se suele utilizar en máquinas de tipo servidor que realizan duras tareas intensivas de red con menos uso en máquinas de tipo escritorio para usuarios ordinarios. Aunque Linux(R) tiene el mismo uso en servidores, es mucho más usado por usuarios en sus casas. Esto lleva a una situación en la que hay muchos programas sólo disponibles en forma binaria para Linux(R) y que no tienen soporte para FreeBSD. Naturalmente, surge la necesidad de ejecutar binarios de Linux(R) en un sistema FreeBSD y eso es de lo que trata esta tesis: la emulación del kernel Linux(R) en el sistema operativo FreeBSD. En el verano de 2006 Google Inc. patrocinó un proyecto enfocado en extender la capa de emulación Linux(R) (el llamado Linuxulator) en FreeBSD para incluir las capacidades de Linux(R) 2.6. Esta tesis se escribió como parte de este proyecto. [[inside]] == Una mirada al interior … En esta sección vamos a describir cada sistema operativo en cuestión. Cómo manejan las llamadas al sistema, trapframes, etc., todo lo que sea bajo nivel. También describimos la manera en la que entienden primitivas comunes de UNIX(R) como qué es un PID, qué es un hilo, etc. En la tercera subsección hablamos acerca de cómo se podría hacer emulación UNIX(R) sobre UNIX(R) de forma general. [[what-is-unix]] === Qué es UNIX(R) UNIX(R) es un sistema operativo con una larga historia que ha influenciado a casi todos los sistemas operativos que se utilizan actualmente. Comenzando en 1960, su desarrollo continúa en la actualidad (aunque en diferentes proyectos). El desarrollo de UNIX(R) pronto se dividió en dos ramas principales: las familias BSD y System III/V. Ambas se influenciaron mutuamente haciendo crecer el estándar UNIX(R). Entre las contribuciones que se originaron en BSD podemos nombrar la memoria virtual, las redes TCP/IP, FFS, y muchos otros. La rama System V aportó las primitivas SysV de comunicación entre procesos, el copy-on-write, etc. UNIX(R) en sí mismo ya no existe pero sus ideas se han usado en muchos otros sistemas operativos por todo el mundo formando así los llamados sistemas operativos tipo UNIX(R). Actualmente los más influyentes son Linux(R), Solaris, y posiblemente (hasta cierto punto) FreeBSD. Hay derivados de UNIX(R) internos en algunas compañías (AIX, HP-UX etc.) pero estos han sido migrados cada vez más a los sistemas mencionados anteriormente. Resumamos las características típicas de UNIX(R). [[tech-details]] === Detalles técnicos Cada programa en ejecución constituye un proceso que representa el estado de la computación. Un proceso en ejecución se divide entre espacio del kernel y espacio de usuario. Algunas operaciones sólo se pueden hacer en espacio de kernel (tratar con hardware etc.), pero el proceso debería pasar la mayoría de su vida en espacio de usuario. El kernel es donde tienen lugar la gestión de los procesos, hardware y los detalles de bajo nivel. El kernel proporciona al espacio de usuario un API UNIX(R) estándar y unificado. Las más importantes se tratan abajo. [[kern-proc-comm]] ==== Comunicación entre el kernel y el proceso de espacio de usuario El API común de UNIX(R) define llamadas al sistema como forma de ejecutar comandos en el kernel desde espacio de usuario. La implementación más habitual es utilizar una interrupción o una instrucción especializada (como las instrucciones `SYSENTER`/`SYSCALL` en ia32). Las llamadas al sistema se definen mediante un número. Por ejemplo en FreeBSD, la llamada al sistema número 85 es la llamada al sistema de man:swapon[2] y la llamada al sistema número 132 es man:mkfifo[2]. Algunas llamadas al sistema necesitan parámetros, que son pasados desde espacio de usuario a espacio de kernel de varias formas (dependiendo de la implementación). Las llamadas al sistema son síncronas. Otra forma posible de comunicarse es mediante un _trap_. Los traps (trampas) ocurren de forma asíncrona después de que ocurra algún evento (división por cero, fallo de página, etc.). Un trap puede ser transparente para un proceso (error de página) o puede resultar en una reacción como enviar una _señal_ (división por cero). [[proc-proc-comm]] ==== Comunicación entre procesos Hay otras API (System V IPC, memoria compartida, etc.) pero la API más importante es la señal. Las señales son enviadas por procesos o por el kernel y recibidas por procesos. Algunas señales pueden ser ignoradas o manejadas por una rutina proporcionada por el usuario, otras dan como resultado una acción predefinida que no se puede alterar ni ignorar. [[proc-mgmt]] ==== Gestión de procesos Las instancias del kernel se procesan las primeras en el sistema (llamado init). Cada proceso en ejecución puede crear una copia idéntica a sí mismo utilizando la llamada al sistema man:fork[2]. Se han introducido algunas versiones ligeramente modificadas de esta llamada pero la semántica es básicamente la misma. Cada proceso en ejecución se puede convertir en otro proceso utilizando la llamada al sistema man:exec[3]. Se han introducido algunas modificaciones a esta llamada pero todas tienen básicamente el mismo propósito. Los procesos terminan sus vidas invocando la llamada al sistema man:exit[2]. Cada proceso se identifica por un número único llamado PID. Cada proceso tiene definido un padre (identificado por su PID). [[thread-mgmt]] ==== Gestión de hilos Los UNIX(R) tradicionales no definen ni un API ni una implementación para hilos, mientras que POSIX(R) define un API para hilos pero la implementación no está definida. Tradicionalmente había dos formas de implementar hilos. Manejarlos como procesos separados (modelo 1:1) o envolver todo el grupo de hilos en un proceso y manejar los hilos en espacio de usuario (modelo 1:N). Comparando las características principales de cada aproximación: Hilos 1: 1 - hilos pesados - el usuario no puede alterar la planificación (ligeramente mitigado por el API de POSIX(R)) + no es necesario un recubrimiento para la llamada al sistema + puede utilizar varias CPU Hilos 1: N + hilos ligeros + el usuario puede modificar fácilmente la planificación - las llamadas al sistema necesitan estar recubiertas - no puede utilizar más de una CPU [[what-is-freebsd]] === ¿Qué es FreeBSD? El proyecto FreeBSD es uno de los sistemas operativos open source más antiguos que están actualmente disponibles para uso diario. Es un descendiente directo del UNIX(R) genuino así que se podría afirmar que es un UNIX(R) verdadero aunque asuntos con las licencias no permiten hacerlo. El inicio del proyecto data de principios de los 90 cuando un grupo de usuarios de BSD parchearon el sistema operativo 386BSD. Basado en este conjunto de parches surgió un nuevo sistema operativo llamado FreeBSD debido a su licencia liberal. Otro grupo creó el sistema operativo NetBSD pensando en diferentes objetivos . Nos centraremos en FreeBSD. FreeBSD es un sistema operativo moderno basado en UNIX(R) con todas las características de UNIX(R). Multitarea preemptiva, capacidades multiusuario, redes TCP/IP, protección de memoria, soporte para multiprocesamiento simétrico, memoria virtual con cache de buffer y VM fusionadas, todo está ahí. Una de las características interesantes y extremadamente útiles es la habilidad de emular otros sistemas operativos tipo UNIX(R). A fecha de Diciembre de 2006 en el desarrollo de 7-CURRENT, se soportan las siguientes características de emulación: * Emulación FreeBSD/i386 en FreeBSD/amd64 * Emulación FreeBSD/i386 en FreeBSD/ia64 * Emulación del sistema operativo Linux(R) en FreeBSD * Emulación NDIS de la interfaz de controladores de red de Windows * Emulación NetBSD del sistema operativo NetBSD * Soporte PECoff para ejecutables PECoff FreeBSD * Emulación del UNIX(R) System V revision 4 Las emulaciones activamente en desarrollo son la capa de Linux(R) y las capas de FreeBSD sobre FreeBSD. Otras no están soportadas para funcionar correctamente o no son utilizables actualmente. [[freebsd-tech-details]] ==== Detalles técnicos FreeBSD es una versión tradicional de UNIX(R) en el sentido en el que divide la ejecución de los procesos en dos mitades: espacio de kernel y ejecución en espacio de usuario. Hay dos tipos de entradas al kernel para los procesos: una llamada al sistema y un trap. Sólo hay una forma de volver. En las siguientes secciones se describirán las tres puertas desde/hacia el kernel. Toda la descripción aplica a la arquitectura i386 ya que el Linuxulator sólo existe ahí pero el concepto es similar para otras arquitecturas. La información se ha tomado de [1] y del código fuente. [[freebsd-sys-entries]] ===== Entradas del sistema FreeBSD tiene una abstracción denominada cargador de clases de ejecución que es un enganche a la llamada al sistema man:execve[2]. Esta emplea una estructura `sysentvec` que describe el ABI de un ejecutable. Contiene cosas como la tabla de traducción de errno, la tabla de traducción de señales, varias funciones para satisfacer las necesidades de las llamadas al sistema (fixups de la pila, volcado de cores, etc). Cada ABI que el kernel de FreeBSD quiera soportar debe definir esta estructura puesto que es utilizada después el código de procesamiento de la llamada al sistema y en algunos otros sitios. Las entradas al sistema se manejan mediante manejadores de traps donde podemos acceder al espacio del kernel y de usuario al mismo tiempo. [[freebsd-syscalls]] ===== Llamadas al sistema Las llamadas al sistema en FreeBSD se llevan a cabo ejecutando la interrupción `0x80` con el registro `%eax` establecido al número de la llamada deseado y con los argumentos pasados en la pila. Cuando un proceso realiza una interrupción `0x80`, se invoca el manejador de trap de llamada al sistema `int0x80` (definido en [.filename]#sys/i386/i386/exception.s#), el cual prepara los argumentos (es decir, los copia a la pila) para llamar a una función C man:syscall[2] (definida en [.filename]#sys/i386/i386/trap.c#) que procesa el marco de trap pasado. El procesamiento consiste en preparar la llamada al sistema (dependiendo de la entrada de `sysvec`), determinar si la llamada es de 32 o 64 bit (cambia el tamaño de los parámetros), luego copiar los parámetros incluyendo la llamada al sistema. Después, se ejecuta la llamada al sistema real procesando el código de retorno (casos especiales para los errores `ERESTART` y `EJUSTRETURN`). Por último se planifica un `userret()`, cambiando el proceso de nuevo a espacio de usuario. Los parámetros para la llamada al sistema real se pasan con la forma de los argumentos `struct thread *td`, `struct syscall args *` donde el segundo parámetro es un puntero a la estructura de parámetros copiada. [[freebsd-traps]] ===== Trampas El manejo de traps en FreeBSD es similar al manejo de llamadas al sistema. Siempre que ocurre un trap, se llama a un manejador en ensamblador. Se elige entre todos los traps, aquellas con registros empujados a la pila o traps de llamadas dependiendo del tipo de trap. Este controlador prepara argumentos para una llamada a una función C `trap()` (definida en [.filename]#sys/i386/i386/trap.c#), que luego procesa el trap ocurrido. Después del procesamiento, puede enviar una señal al proceso y / o salir al espacio de usuario usando `userret()`. [[freebsd-exits]] ===== Salida Las salidas del kernel al espacio de usuario ocurren usando la rutina en ensamblador `doreti` independientemente de si se ingresó al kernel mediante un trap o mediante una llamada al sistema. Esto restaura el estado del programa desde la pila y vuelve al espacio de usuario. [[freebsd-unix-primitives]] ===== Primitivas UNIX(R) El sistema operativo FreeBSD sigue el esquema tradicional UNIX(R), donde cada proceso tiene un número único de identificación, el llamado _PID_ (Process ID). Los números PID se generan o linealmente o de forma aleatoria en el rango `0` a `PID_MAX`. La generación de números PID se hace usando una búsqueda lineal en el espacio PID. Cada hilo en un proceso recibe el mismo número PID como resultado de llamar a man:getpid[2]. Actualmente hay dos formas de implementar multihilo en FreeBSD. La primera es M:N seguido del modelo 1:1. La librería usada por defecto es multihilo M:N (`libpthread`) y puedes cambiar en tiempo de ejecución a multihilo 1:1 (`libthr`). El plan es cambiar pronto a la librería 1:1 por defecto. Aunque estas dos librerías utilizan las mismas primitivas del kernel, se acceden mediante APIs diferentes. La librería M:N utiliza la familia `kse_*` de llamadas al sistema mientras que la librería 1:1 utiliza la familia `thr_*` de llamadas al sistema. Debido a esto, no hay un concepto general de ID de hilo compartido entre el kernel y el espacio de usuario. Por supuesto, ambas librerías implementan el API de ID de hilo de pthread. Cada hilo del kernel (descrito por `struct thread`) tiene el identificador tid pero no es directamente accesible desde espacio de usuario y sólo sirve para cubrir necesidades del kernel. También se usa para la librería 1:1 como el ID de hilo de pthread pero este manejo es interno a la librería y no se puede depender de él. Como se indicó anteriormente, hay dos implementaciones de multihilo en FreeBSD. La biblioteca M:N divide el trabajo entre el espacio del kernel y el espacio de usuario. El hilo es una entidad que se planifica en el kernel, pero puede representar varios hilos en espacio de usuario. M hilos en espacio de usuario se asignan a N hilos del núcleo, lo que ahorra recursos y mantiene la capacidad de explotar el paralelismo de multiprocesador. Se puede obtener más información sobre la implementación en la página del manual o en [1]. La biblioteca 1:1 mapea directamente un hilo de espacio de usuario a un hilo del kernel, lo que simplifica enormemente el esquema. Ninguno de estos diseños implementa un mecanismo de equidad (se implementó un mecanismo de este tipo, pero se eliminó recientemente porque causaba una grave lentitud y hacía que el código fuera más difícil de tratar). [[what-is-linux]] === Qué es Linux(R) Linux(R) es un kernel de tipo UNIX(R) desarrollado originalmente por Linus Torvalds, y al que ahora contribuye un enorme número de programadores en todo el mundo. Desde sus primeros comienzos hasta ahora, con amplio apoyo de compañías como IBM o Google, Linux(R) se ha asociado con su rápido ritmo de desarrollo, amplio soporte hardware y su modelo de organización de tipo dictador benevolente. El desarrollo de Linux(R) comenzó como un hobby en 1991 en la Universidad de Helsinki en Finlandia. Desde entonces ha adquirido todas las características de un sistema operativo moderno tipo UNIX(R): multiprocesamiento, soporte multiusuario, memoria virtual, redes, básicamente lo tiene todo. También hay características altamente avanzadas como virtualización, etc. A fecha de 2006 Linux(R) parece ser el sistema operativo open source más ampliamente usado con soporte de empresas de software independientes como Oracle, RealNetworks, Adobe, etc. La mayoría del software comercial que se distribuye para Linux(R) sólo se puede obtener en forma binaria de forma que recompilar para otros sistemas operativos es imposible. La mayoría del desarrollo de Linux(R) tiene lugar en el sistema de control de versiones Git. Git es un sistema distribuido de forma que no hay una fuente de código central de Linux(R), pero algunas ramas se consideran prominentes y oficiales. El esquema de numeración de versiones implementado por Linux(R) consiste en cuatro números A.B.C.D. El desarrollo actual tiene lugar en 2.6.C.C, donde C representa la versión mayor, donde se cambian o añaden nuevas características mientras que D es la versión menor sólo para arreglos de bugs. Se puede obtener más información en [3]. [[linux-tech-details]] ==== Detalles técnicos Linux(R) sigue el esquema tradicional UNIX(R) de dividir la ejecución de un proceso en dos partes: espacio de kernel y espacio de usuario. Al kernel se puede entrar de dos formas: vía trap o vía llamada al sistema. La vuelta se maneja de una sola forma. La descripción que sigue aplica a Linux(R) 2.6 en la arquitectura i386(TM). La información se ha obtenido de [2]. [[linux-syscalls]] ===== Llamadas al sistema Las llamadas al sistema en Linux(R) se realizan (en espacio de usuario) utilizando las macros `syscallX` donde X se sustituye por el número que representa el número de parámetros de la llamada al sistema. Esta macro traduce a un código que carga el registro `%eax` con un número de llamada al sistema y ejecuta la interrupción `0x80`. Después de la llamada al sistema se llama a return, que traslada valores de retorno negativos a valores positivos `errno` y establece `res` a `-1` en caso de error. Cada vez que se llama a la interrupción `0x80` el proceso entra en el kernel en un manejador de llamada al sistema. Esta rutina salva todos los registros en la pila y llama a la entrada de llamada al sistema seleccionada. Nótese que la convención de llamadas de Linux(R) espera que los parámetros de la llamada al sistema se pasen vía registros como se muestra aquí: . parámetro -> `%ebx` . parámetro -> `%ecx` . parámetro -> `%edx` . parámetro -> `%esi` . parámetro -> `%edi` . parámetro -> `%ebp` Hay algunas excepciones a esta regla, donde Linux(R) utiliza una convención de llamadas diferente (principalmente en la llamada al sistema `clone`). [[linux-traps]] ===== Trampas Los manejadores de traps se encuentran en [.filename]#arch/i386/kernel/traps.c# y la mayoría de estos manejadores viven en [.filename]#arch/i386/kernel/entry.S#, donde ocurre el manejo de los traps. [[linux-exits]] ===== Salida La vuelta de la llamada al sistema se gestiona mediante la llamada al sistema man:exit[3] que comprueba que el proceso no tenga trabajo sin finalizar, luego comprueba si hemos utilizado los selectores proporcionados por el usuario. Si esto sucede se aplica un fix a la pila y finalmente se restauran los registros desde la pila y el proceso vuelve a espacio de usuario. [[linux-unix-primitives]] ===== Primitivas UNIX(R) En la versión 2.6, el sistema operativo Linux(R) redefinió algunas de las primitivas tradicionales de UNIX(R), en particular PID, TID e hilo. PID no se define como único para cada proceso, así que para algunos procesos (hilos) man:getpid[2] devuelve el mismo valor. La identificación única de proceso se proporciona mediante TID. Esto es así porque _NPTL_ (New POSIX(R) Thread Library) define los hilos como procesos normales (el llamado multihilo 1:1). Crear un nuevo proceso en Linux(R) 2.6 se hace utilizando la llamada al sistema `clone` (las variantes de fork se reimplementan usando esta). Esta llamada al sistema clone define una serie de flags que afecta el comportamiento de los procesos clonados respecto a la implementación del multihilo. La semántica es un poco difusa ya que no hay un único flag para decirle a la llamada al sistema que cree un hilo. Las banderas de clonado implementadas son: * `CLONE_VM` - los procesos comparten su espacio de memoria * `CLONE_FS` - comparte umask, cwd y namespace (espacio de nombres) * `CLONE_FILES` - comparte ficheros abiertos * `CLONE_SIGHAND` - comparte manejadores de señales y señales bloqueadas * `CLONE_PARENT` - comparte padre * `CLONE_THREAD` - sé un hilo (más explicación abajo) * `CLONE_NEWNS` - nuevo espacio de nombres * `CLONE_SYSVSEM` - comparte estructuras para deshacer operaciones en semáforos de SysV * `CLONE_SETTLS` - establece TLS en la dirección proporcionada * `CLONE_PARENT_SETTID` - establece TID en el padre * `CLONE_CHILD_CLEARTID` - borra TID en el hijo * `CLONE_CHILD_SETTID` - establece TID en el hijo `CLONE_PARENT` establece el padre real al padre del llamante. Esto es útil para los hilos porque si el hilo A crea el hilo B queremos que el padre del hilo B sea todo el grupo de hilos. `CLONE_THREAD` hace exactamente lo mismo que `CLONE_PARENT`, `CLONE_VM` y `CLONE_SIGHAND`, reescribe el PID para que sea igual al PID del llamante, blanquea la señal exit y se une al grupo de hilos. `CLONE_SETTLS` establece las entradas GDT para el manjeo de TLS. El conjunto de flags `CLONE_*_*TID` establece/borra la dirección proporcionada por el usuario a TID o 0. Como puedes ver `CLONE_THREAD` hace la mayor parte del trabajo y no parece encajar muy bien en el esquema. La intención original no está clara (incluso para los autores, según los comentarios en el código), pero creo que originalmente había un flag de hilo, que luego se dividió entre muchos otros flags pero esta separación nunca se terminó por completo. Tampoco está claro para qué sirve esta partición, ya que glibc no la usa, por lo que solo el uso a mano de clone permite al programador acceder a estas funciones. Para programas no multihilo el PID y el TID son iguales. Para programas multihilo el PID y el TID del primer hilo son el mismo y cada hilo que se crea comparte el mismo PID y se le asigna un TID único (porque se pasa `CLONE_THREAD`) también se comparte el padre en todos los procesos que forman este programa multihilo. El código que implementa man:pthread_create[3] en NPTL define los flags de clone así: [.programlisting] .... 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); .... `CLONE_SIGNAL` se define como [.programlisting] .... #define CLONE_SIGNAL (CLONE_SIGHAND | CLONE_THREAD) .... el último 0 significa que no se envía ninguna señal cuando alguno de los hilos sale. [[what-is-emu]] === Que es la emulación Según una definición de diccionario, la emulación es la capacidad de un programa o dispositivo para imitar otro programa o dispositivo. Esto se logra proporcionando la misma reacción a un estímulo dado que la que produce el objeto emulado. En la práctica, en el mundo del software hay principalmente tres tipos de emulación: un programa utilizado para emular una máquina (QEMU, varios emuladores de consola de juegos, etc.), emulación de software de una instalación de hardware (emuladores OpenGL, emulación de unidades de punto flotante, etc.) y emulación del sistema operativo (ya sea en el núcleo del sistema operativo o como un programa de espacio de usuario). La emulación se usa generalmente en un lugar donde usar el componente original no es factible ni posible en absoluto. Por ejemplo, alguien podría querer usar un programa desarrollado para un sistema operativo diferente al que usa. Entonces la emulación es útil. A veces no hay otra forma que usar la emulación, por ejemplo, cuando el dispositivo de hardware que intentas utilizar no existe (todavía/más), no hay otra forma que la emulación. Esto sucede a menudo cuando se traslada un sistema operativo a una plataforma nueva (inexistente). A veces es más barato emular. Desde el punto de vista de la implementación, hay dos enfoques principales para la implementación de la emulación. Puedes emular todo, aceptando posibles entradas del objeto original, manteniendo el estado interno y emitiendo la salida correcta según el estado y/o la entrada. Este tipo de emulación no requiere condiciones especiales y básicamente se puede implementar en cualquier lugar para cualquier dispositivo/programa. El inconveniente es que implementar tal emulación es bastante difícil, requiere mucho tiempo y es propenso a errores. En algunos casos, podemos utilizar un enfoque más simple. Imagina que quieres emular una impresora que imprime de izquierda a derecha en una impresora que imprime de derecha a izquierda. Es obvio que no hay necesidad de una capa de emulación compleja, pero basta con invertir el texto impreso. A veces, el entorno de emulación es muy similar al emulado, por lo que solo se necesita una capa fina de traducción para proporcionar una emulación completamente funcional. Como puedes ver, esto es mucho menos exigente de implementar, por lo que consume menos tiempo y es menos propenso a errores que el enfoque anterior. Pero la condición necesaria es que los dos entornos sean lo suficientemente similares. El tercer enfoque combina los dos anteriores. La mayoría de las veces los objetos no brindan las mismas capacidades, por lo que en el caso de emular el más potente en el menos potente, tenemos que emular las características faltantes con la emulación completa descrita anteriormente. Esta tesis trata de la emulación de UNIX(R) en UNIX(R), que es exactamente el caso, donde una fina capa de traducción es suficiente para proporcionar emulación completa. El API UNIX(R) consiste en un conjunto de llamadas al sistema, las cuales están normalmente autocontenidas y no afectan al estado global del kernel. Hay algunas llamadas al sistema que afectan el estado interno, pero esto se puede solucionar proporcionando algunas estructuras que mantienen el estado adicional. Ninguna emulación es perfecta y las emulaciones tienden a carecer de algunas partes, pero esto no suele causar inconvenientes graves. Imagina un emulador de consola de juegos que emula todo menos la salida de música. No hay duda de que los juegos se pueden jugar y se puede usar el emulador. Puede que no sea tan cómodo como la consola de juegos original, pero es un compromiso aceptable entre precio y comodidad. Lo mismo aplica al API de UNIX(R). La mayoría de los programas pueden vivir con un conjunto muy limitado de llamadas al sistema funcionales. Esas llamadas al sistemas suelen ser las más antiguas (man:read[2]/man:write[2], la familia man:fork[2], manejo de man:signal[3], man:exit[3], man:socket[2] API) y por lo tanto es fácil de emular porque sus semánticas se comparten entre todos los UNIX(R) que existen a día de hoy. [[freebsd-emulation]] == Emulación === Cómo funciona la emulación en FreeBSD Como se ha mencionado antes, FreeBSD suporta ejecutar binarios de otros UNIX(R). Esto funciona porque FreeBSD tiene una capa de abstracción llamada el cargador de clases de ejecución. Este se inserta en la llamada al sistema man:execve[2] de forma que cuando man:execve[2] está a punto de ejecutar un binario examina su tipo. Básicamente, existen dos tipos de binarios en FreeBSD. Scripts de texto tipo shell que se identifican por `#!` como sus dos primeros caracteres y binarios (typically _ELF_) normales, que son una representación de un objeto compilado ejecutable. La gran mayoría (se podría decir que todos) de los binarios en FreeBSD son del tipo ELF. Los archivos ELF contienen un encabezado, que especifica la ABI del sistema operativo para este archivo ELF. Al leer esta información, el sistema operativo puede determinar con precisión de qué tipo de binario es el archivo dado. Cada ABI de sistema operativo tiene que estar registrada en el kernel de FreeBSD. Esto aplica también al ABI nativo de FreeBSD. Cuando man:execve[2] ejecuta un binario itera por la lista de APIs registradas y cuando encuentra la correcta usa la información contenida en la descripción del ABI (su tabla de llamadas al sistema, tabla de traducción de `errno`, etc.). Así que cada vez que un proceso realiza una llamada al sistema, utiliza su propio conjunto de llamadas al sistema en lugar de uno global. Esto de forma efectiva proporciona una forma muy elegante de soportar la ejecución de varios formatos binarios. La naturaleza de la emulación de diferentes sistemas operativos (y también algunos otros subsistemas) llevó a los desarrolladores a introducir un mecanismo de manejadores de eventos. Hay varios lugares en el kernel, donde se llama a una lista de manejadores de eventos. Cada subsistema puede registrar un manejador de eventos y se los llama en consecuencia. Por ejemplo, cuando un proceso termina, se llama a un manejador que posiblemente limpia lo que sea que el subsistema necesite que se limpie. Esos simples servicios básicamente proporcionan todo lo que se necesita para la infraestructura de emulación y de hecho esto es básicamente lo único necesario para implementar la capa de emulación Linux(R). [[freebsd-common-primitives]] === Primitivas comunes en el kernel de FreeBSD Las capas de emulación necesitan soporte del sistema operativo. Voy a describir algunas de las primitivas soportadas en el sistema operativo FreeBSD. [[freebsd-locking-primitives]] ==== Primitivas de bloqueo Aportado por: `{attilio}` El conjunto de primitivas de sincronización de FreeBSD se basa en la idea de suministrar un número bastante grande de primitivas diferentes de manera que se pueda utilizar la mejor para cada situación particular y apropiada. Desde un punto de vista de alto nivel, puede considerar tres tipos de primitivas de sincronización en el kernel de FreeBSD: * operaciones atómicas y barreras de memoria * Locks * barreras de planificación A continuación hay descripciones de las 3 familias. Para cada bloqueo, deberías consultar la página de manual vinculada (cuando sea posible) para obtener explicaciones más detalladas. [[freebsd-atomic-op]] ===== Operaciones atómicas y barreras de memoria Las operaciones atómicas se implementan a través de un conjunto de funciones que realizan aritmética simple sobre operandos de memoria de forma atómica con respecto a eventos externos (interrupciones, apropiación, etc.). Las operaciones atómicas pueden garantizar la atomicidad solo en tipos de datos pequeños (en el orden de magnitud del tipo de datos `.long.` de arquitectura C), por lo que rara vez se debe usar directamente en el código de nivel final, sino solo para operaciones muy simples (como la configuración de flags en un mapa de bits, por ejemplo). De hecho, es bastante simple y común escribir una semántica incorrecta basada solo en operaciones atómicas (generalmente llamadas "sin bloqueo"). El kernel de FreeBSD ofrece una forma de realizar operaciones atómicas junto con una barrera de memoria. Las barreras de memoria garantizarán que ocurra una operación atómica siguiendo un orden específico con respecto a otros accesos a la memoria. Por ejemplo, si necesitamos que ocurra una operación atómica justo después de que se completen todas las demás escrituras pendientes (en términos de instrucciones que reordenan las actividades de buffer), necesitamos usar explícitamente una barrera de memoria junto con esta operación atómica. Por lo tanto, es sencillo entender por qué las barreras de memoria juegan un papel clave para la construcción de bloqueos de alto nivel (como refcounts, mutexes, etc.). Para obtener una explicación detallada sobre las operaciones atómicas, consulte man:atomic[9]. Sin embargo, se está lejos de señalar que las operaciones atómicas (y las barreras de memoria también) deberían idealmente usarse solo para construir bloqueos frontales (como mutex). [[freebsd-refcounts]] ===== Contadores de referencias Los refcounts son interfaces para manejar contadores de referencia. Se implementan a través de operaciones atómicas y están destinadas a usarse solo en casos donde el contador de referencia es lo único que debe protegerse, por lo que incluso algo como un spin-mutex está en desuso. El uso de la interfaz refcount para estructuras, donde ya se usa un mutex, a menudo es incorrecto, ya que probablemente deberíamos cerrar el contador de referencia en algunas rutas ya protegidas. Actualmente no existe una página de manual que discuta refcount, solo lee [.filename]#sys/refcount.h# para obtener una descripción general de la API existente. [[freebsd-locks]] ===== Locks El kernel de FreeBSD tiene muchas clases de bloqueos. Cada bloqueo está definido por algunas propiedades peculiares, pero probablemente la más importante es el evento vinculado a los elementos que compiten (o en otros términos, el comportamiento de los hilos que no pueden adquirir el bloqueo). El esquema de bloqueo de FreeBSD presenta tres comportamientos diferentes para los contendientes: . iterando . bloqueo . dormir [NOTE] ==== los números no son casuales ==== [[freebsd-spinlocks]] ===== Spin locks Los spinlocks permiten a los que esperan iterar indefinidamente hasta que no pueden adquirir el lock. Un asunto importante que tratar es cuando un hilo compite en un spinlock si no se desplanifica su ejecución. Dado que el kernel de FreeBSD es preventivo, esto expone el spinlock al riesgo de interbloqueos que pueden resolverse simplemente deshabilitando las interrupciones mientras se adquieren. Por esta y otras razones (como la falta de soporte de propagación de prioridad, deficiencias en los esquemas de equilibrio de carga entre las CPU, etc.), los spinlocks están destinados a proteger rutas de código muy pequeñas o, idealmente, no deben usarse en absoluto si no se solicitan explícitamente (explicado más adelante). [[freebsd-blocking]] ===== Bloqueo Los locks de bloques permiten que los que esperan sean desprogramados y bloqueados hasta que el propietario del lock no lo libere y despierte a uno o más contendientes. Para evitar problemas de inanición, los locks de bloque propagan la prioridad de los que esperan al propietario. Los locks de bloque deben implementarse a través de la interfaz turnstile y están destinados a ser el tipo de bloqueo más utilizado en el núcleo, si no se cumplen condiciones particulares. [[freebsd-sleeping]] ===== Dormir Los sleep lock permiten a los que esperan ser desplanificados y ponerse a dormir hasta que el elemento que tiene el lock no lo libere y despierte a uno o más de los elementos dormidos. Puesto que los sleep locks están pensados para proteger grandes rutas de código y de abastecer eventos asíncronos, no hacen ningún tipo de propagación de prioridad. Se deben implementar mediante la interfaz man:sleepqueue[9]. El orden utilizado para adquirir locks es muy importante, no solo por la posibilidad de interbloqueo debido a las inversiones de orden de lock, sino incluso porque la adquisición de locks debe seguir reglas específicas vinculadas a la naturaleza de los locks. Si echas un vistazo a la tabla de arriba, la regla práctica es que si un hilo tiene un lock de nivel n (donde el nivel es el número listado cerca del tipo de lock) no está permitido adquirir un lock de niveles superiores , ya que esto rompería la semántica especificada para una ruta. Por ejemplo, si un hilo tiene un lock de bloque (nivel 2), se le permite adquirir un spin lock (nivel 1) pero no un sleep lock (nivel 3), ya que los locks de bloque están destinados a proteger rutas más pequeñas que el bloqueo de suspensión (sin embargo, estas reglas no se refieren a operaciones atómicas o barreras de programación). Esta es una lista de bloqueo con sus respectivos comportamientos: * spin mutex - iterativo - man:mutex[9] * sleep mutex - bloqueante - man:mutex[9] * pool mutex - bloqueante - man:mtx[pool] * sleep family - suspendido - man:sleep[9] pause tsleep msleep msleep spin msleep rw msleep sx * condvar - suspendido - man:condvar[9] * rwlock - bloqueante - man:rwlock[9] * sxlock - suspendido - man:sx[9] * lockmgr - bloqueante - man:lockmgr[9] * semaphores - bloqueante - man:sema[9] Entre estos bloqueos, solo los mutex, sxlocks, rwlocks y lockmgrs están pensados para manejar recursividad, pero actualmente la recursividad solo es compatible con mutexes y lockmgrs. [[freebsd-scheduling]] ===== Barreras de programación Las barreras de programación están destinadas a utilizarse para impulsar la programación multihilo. Consisten principalmente en tres elementos diferentes: * secciones críticas (y preemptividad) * sched_bind * sched_pin Normalmente, estos sólo se deberían utilizar en un contexto particular e incluso aunque muchas veces pueden reemplazar a los locks, se deberían evitar porque no permiten el diagnóstico de problemas simples con las herramientas de depuración de locking (como man:witness[4]). [[freebsd-critical]] ===== Secciones críticas El kernel de FreeBSD se ha hecho preemptivo básicamente para tratar con hilos de interrupción. De hecho, para evitar una latencia de interrupción alta, los hilos de tiempo compartido con prioridad pueden ser reemplazados por hilos de interrupción (de esta manera, no necesitan esperar para ser programados como vistas previas de la ruta normal). Un kernel preemptivo, sin embargo, introduce nuevos puntos de carrera que también deben manejarse. A menudo, para hacer frente a la preemptividad, lo más sencillo es desactivarla por completo. Una sección crítica define un fragmento de código (delimitado por el par de funciones man:critical_enter[9] y man:critical_exit[9], donde se garantiza que la preemptividad no ocurrirá hasta que el código protegido se ejecute por completo). Esto a menudo puede reemplazar un lock de manera efectiva, pero debe usarse con cuidado para no perder toda la ventaja que brinda la preemptividad. [[freebsd-schedpin]] ===== sched_pin/sched_unpin Otra forma de lidiar con la preemptividad es la interfaz `sched_pin()`. Si un fragmento de código está cerrado en el par de funciones `sched_pin()` y `sched_unpin()`, se garantiza que el hilo respectivo, incluso si puede ser reemplazado, siempre se ejecutará en la misma CPU. La fijación (pinning) es muy eficaz en el caso particular en que tenemos que acceder a datos por CPU y asumimos que otros hilos no cambiarán esos datos. La última condición determinará una sección crítica como una condición demasiado fuerte para nuestro código. [[freebsd-schedbind]] ===== sched_bind/sched_unbind `sched_bind` es una API que se utiliza para vincular un hilo a una CPU en particular durante todo el tiempo que ejecuta el código, hasta que no lo desvincula la llamada a la función `sched_unbind`. Esta función tiene un papel clave en situaciones en las que no puedes confiar en el estado actual de las CPU (por ejemplo, en las primeras etapas del arranque), ya que deseas evitar que tu hilo migre a CPUs inactivas. Como `sched_bin` y `sched_unbind` manipulan las estructuras internas del planificador, es necesario que estén dentro de la adquisición/liberación `sched_lock` cuando se usan. [[freebsd-proc]] ==== Estructura de proceso Varias capas de emulación a veces requieren algunos datos adicionales por proceso. Puede administrar estructuras separadas (una lista, un árbol, etc.) que contienen estos datos para cada proceso, pero esto tiende a ser lento y consume memoria. Para solucionar este problema la estructura `proc` de FreeBSD contiene `p_emuldata`, que es un puntero vacío a algunos datos específicos de la capa de emulación. La entrada a este `proc` está protegida por el mutex proc. La estructura `proc` de FreeBSD contiene una entrada `p_sysent` que identifica qué ABI está ejecutando este proceso. De hecho, es un puntero al `sysentvec` descrito arriba. Entonces, comparando este punto con la dirección donde se almacena la estructura `sysentvec` para la ABI dada podemos determinar si el proceso corresponde a nuestra capa de emulación. El código típicamente se parece a esto: [.programlisting] .... if (__predict_true(p->p_sysent != &elf_Linux(R)_sysvec)) return; .... Como puedes ver, utilizamos el modificador `__predict_true` para colapsar el caso más común (proceso de FreeBSD) a una simple operación de retorno preservando así un alto rendimiento. Este código debería convertirse en una macro porque actualmente no es muy flexible, es decir no soportamos emulación Linux(R)64 o procesos Linux(R) A.OUT en i386. [[freebsd-vfs]] ==== VFS El subsistema VFS de FreeBSD es muy complejo pero la capa de emulación de Linux(R) sólo usa una pequeña parte mediante una API bien definida. Puede operar con vnodes o con manejadores de ficheros. Vnode representa un nodo virtual, es decir es la representación de un nodo en VFS. Otra representación es un manejador de fichero que representa un fichero abierto desde la perspectiva de un proceso. Un manejador de fichero puede representar un socket o un fichero ordinario. Un manejador de fichero contiene un puntero a su vnode. Varios manejadores de fichero pueden apuntar al mismo vnode. [[freebsd-namei]] ===== namei La rutina man:namei[9] es el punto central de entrada para la búsqueda de rutas y su traducción. Recorre la ruta punto por punto desde el comienzo hasta el fin utilizando una función de búsqueda que es interna a VFS. La llamada al sistema man:namei[9] puede manejar enlaces simbólicos y rutas absolutas y relativas. Cuando se busca una ruta con man:namei[9] se introduce en la caché de nombres. Este comportamiento se puede eliminar. Esta rutina se usa en todo el kernel y su rendimiento es altamente crítico. [[freebsd-vn]] ===== vn_fullpath La función man:vn_fullpath[9] hace todo lo posible por recorrerse la caché de nombres de VFS y devolver la ruta para un vnode (bloqueado) dado. Este proceso no es fiable pero funciona bien para los casos más comunes. Esta falta de fiabilidad se produce porque depende de la caché de VFS (no recorre las estructuras del medio en cuestión), no funciona con enlaces duros, etc. Esta rutina se usa en varios sitios en el Linuxulator. [[freebsd-vnode]] ===== Operaciones de vnode * `fgetvp` - dado un hilo y un número de descriptor de fichero devuelve el vnode asociado * man:vn_lock[9] - bloquea un vnode * `vn_unlock` - desbloquea un vnode * man:VOP_READDIR[9] - lee un directorio referenciado por un vnode * man:VOP_GETATTR[9] - obtiene los atributos de un fichero o directorio referenciados por un vnode * man:VOP_LOOKUP[9] - busca una ruta a un directorio dado * man:VOP_OPEN[9] - abre un fichero referenciado por un vnode * man:VOP_CLOSE[9] - cierra un fichero referenciado por un vnode * man:vput[9] - decrementa al contador de uso de un vnode y lo desbloquea * man:vrele[9] - decrementa el contador de uso de un vnode * man:vref[9] - incrementa el contador de uso de un vnode [[freebsd-file-handler]] ===== Operaciones del controlador de archivos * `fget` - dado un hilo y un número de descriptor de fichero devuelve el manejador de fichero asociado y lo referencia * `fdrop` - elimina una referencia al menejador de fichero * `fhold` - referencia un manejador de fichero [[md]] == Parte MD de la capa de emulación de Linux(R) Esta sección trata de la implementación de la capa de emulación Linux(R) en el sistema operativo FreeBSD. Primero describe la parte que depende de la arquitectura hablando sobre cómo y dónde se implementa la interacción entre el kernel y el espacio de usuario. Habla acerca de llamadas al sistema, señales, ptrace, traps, arreglos de la pila. Esta parte trata sobre i386 pero está escrita de forma general de forma que otras arquitecturas no deberían ser muy diferentes. La siguiente parte es la parte del Linuxulator independiente de la arquitectura. Esta sección sólo cubre el manejo de i386 y ELF. A.OUT está obsoleto y sin probar. [[syscall-handling]] === Manejo de llamadas al sistema El manejo de llamadas al sistema está escrito principalmente en [.filename]#linux_sysvec.c#, el cual cubre la mayoría de las rutinas indicadas en la estructura `sysentvec`. Cuando un proceso Linux(R) que se ejecuta en FreeBSD realiza una llamada al sistema, la rutina general de llamadas al sistema llama a la rutina linux prepsyscall para el ABI de Linux(R). [[linux-prepsyscall]] ==== Linux(R) prepsyscall Linux(R) pasa los argumentos a las llamadas al sistema mediante registros (por eso está limitado a 6 parámetros en i386) mientras que FreeBSD utiliza la pila. La rutina prepsyscall de Linux(R) debe copiar los parámetros desde los registros a la pila. El orden de los registros es: `%ebx`, `%ecx`, `%edx`, `%esi`, `%edi`, `%ebp`. El truco es que esto es verdad sólo para la _mayoría_ de las llamadas al sistema. Algunas (principalmente `clone`) utiliza un orden distinto pero se puede arreglar fácilmente introduciendo un parámetro dummy en el prototipo de `linux_clone`. [[syscall-writing]] ==== Escritura de syscall Cada llamada al sistema implementada en el Linuxulator debe tener su prototipo con varios flags en [.filename]#syscalls.master#. La forma del archivo es: [.programlisting] .... ... AUE_FORK STD { int linux_fork(void); } ... AUE_CLOSE NOPROTO { int close(int fd); } ... .... La primera columna representa el número de llamada al sistema. La segunda columna es para proporcionar auditoría. La tercera columna representa el tipo de llamada al sistema. Es una de `STD`, `OBSOL`, `NOPROTO` o `UNIMPL`. `STD` es una llamada al sistema estándar con un prototipo e implementación completas. `OBSOL` es una llamada obsoleta que define sólo el prototipo. `NOPROTO` significa que la llamada al sistema está implementada en otro sitio así que no hay que añadir el prefijo del ABI, etc. `UNIMPL` significa que la llamada al sistema será sustituida por la llamada `nosys` (una llamada al sistema que tan sólo muestra un mensaje diciendo que la llamada no está implementada y que devuelve `ENOSYS`). A partir de [.filename]#syscalls.master# un script genera tres ficheros: [.filename]#linux_syscall.h#, [.filename]#linux_proto.h# y [.filename]#linux_sysent.c#. [.filename]#linux_syscall.h# contiene las definiciones de los nombres de las llamadas al sistema y sus valores numéricos, ejemplo: [.programlisting] .... ... #define LINUX_SYS_linux_fork 2 ... #define LINUX_SYS_close 6 ... .... [.filename]#linux_proto.h# contiene definiciones de estructuras de argumentos de todas las llamadas al sistema, ejemplo: [.programlisting] .... struct linux_fork_args { register_t dummy; }; .... Y finalmente, [.filename]#linux_sysent.c# contiene una estructura que describe la tabla de entrada del sistema, utilizada para enviar una llamada al sistema, por ejemplo: [.programlisting] .... { 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 */ .... Como puedes ver `linux_fork` se implementa en el propio Linuxulator de modo que la definición de su tipo es `STD` y no tiene argumentos lo que se ve por la estructura de argumentos dummy. Por otro lado `close` es sólo un alias para la llamada man:close[2] real de FreeBSD de forma que no tiene una estructura de argumentos de linux asociada y en la tabla de entrada al sistema no tiene un prefijo "linux" ya que llama a la función man:close[2] real del kernel. [[dummy-syscalls]] ==== Llamadas al sistema ficticias La capa de emulación de Linux(R) no es completa ya que algunas llamadas al sistema no están implementadas de forma adecuada y otras no están implementadas en absoluto. La capa de emulación utiliza un método para marcar las llamadas al sistema no implementadas con la macro `DUMMY`. Estas definiciones dummy se encuentran en [.filename]#linux_dummy.c# en la forma `DUMMY(syscall)`, que luego se traduce a varios ficheros auxiliares de llamadas al sistema y cuya implementación consiste en imprimir un mensaje diciendo que la llamada no está implementada. El prototipo `UNIMPL` no se utiliza porque queremos ser capaces de identificar el nombre de la llamada al sistema que fue invocada con el fin de saber qué llamadas al sistema son importantes de implementar. [[signal-handling]] === Manejo de señales El manejo de señales se hace normalmente en el kernel de FreeBSD para todas las compatibilidades binarias con una llamada a la capa compat-dependiente. La capa de compatibilidad Linux(R) define la rutina `linux_sendsig` con este propósito. [[linux-sendsig]] ==== Linux(R) sendsig Esta rutina comprueba primero si la señal se ha instalado con un `SA_SIGINFO` en cuyo caso llama en su lugar a la rutina `linux_rt_sendsig`. Además, asigna (o reutiliza uno existente) un contexto de manejador de señal ya existente, luego crea una lista de argumentos para el manejador de señal. Traduce el número de señal basado en la tabla de traducción de señales, asigna un manejador, traduce sigset. Luego guarda contexto para la rutina `sigreturn` (varios registros, número de trap traducido y máscara de señal). Finalmente, copia el contexto de la señal al espacio de usuario y prepara el contexto para que se ejecute el manejador de señal real. [[linux-rt-sendsig]] ==== linux_rt_sendsig Esta rutina es similar a `linux_sendsig`, sólo es diferente la preparación del contexto de la señal. Añade `siginfo`, `ucontext` y algunas partes POSIX(R). Podría ser interesante considerar si esas dos funciones podrían fusionarse en una sola con el beneficio de una menor duplicación de código y una posible ejecución de código más rápida. [[linux-sigreturn]] ==== linux_sigreturn Esta llamada al sistema se utiliza para la devolución desde controlador de señales. Realiza algunas comprobaciones de seguridad y restaura el contexto del proceso original. También desenmascara la señal en la máscara de señal de proceso. [[ptrace]] === Ptrace Muchos derivados de UNIX(R) implementan la llamada al sistema man:ptrace[2] para proporcionar diversas características de depuración y traza. Estas características permiten la traza de un proceso para obtener información valiosa acerca del proceso que es trazado, como volcado de registros, cualquier posición de memoria del espacio de direcciones del proceso, etc. y también para trazar procesos para saltar una instrucción o entre entradas al sistema (llamadas al sistema y traps). man:ptrace[2] también te permite establecer información en los procesos trazados (registros, etc). man:ptrace[2] es un estándar ampliamente disponible e implementado en la mayoría de UNIX(R) en todo el mundo. La emulación de Linux(R) en FreeBSD implementa las características de man:ptrace[2] en [.filename]#linux_ptrace.c#. Las rutinas para convertir registros entre Linux(R) y FreeBSD y la llamada al systema real de la emulación de man:ptrace[2]. La llamada al sistema es un gran bloque switch que implementa su parte contraria en FreeBSD para cada comando de man:ptrace[2]. Los comandos de man:ptrace[2] son mayoritariamente iguales entre Linux(R) y FreeBSD de forma que normalmente sólo se necesita una pequeña modificación. Por ejemplo `PT_GETREGS` en Linux(R) opera sobre datos directamente mientras que en FreeBSD utiliza un puntero a los datos de forma que después de ejecutar una llamada a man:ptrace[2] nativo, se debe hacer un copyout para preservar la semántica de Linux(R). La implementación de man:ptrace[2] en el Linuxulator tiene algunas debilidades. Ha habido algunos "panics" cuando se ha usado `strace` (que consume man:ptrace[2]) en el entorno del Linuxulator. Tampoco se ha implementado `PT_SYSCALL`. [[traps]] === Trampas En cualquier momento en el que un proceso Linux(R) está ejecutándose en un trap de la capa de emulación la propia trap en sí misma es manejada de forma transparente con excepción de la traducción del trap. Linux(R) y FreeBSD tienen opiniones diferentes sobre lo que es un trap y cómo manejarlas. El código es normalmente muy corto: [.programlisting] .... static int translate_traps(int signal, int trap_code) { if (signal != SIGBUS) return signal; switch (trap_code) { case T_PROTFLT: case T_TSSFLT: case T_DOUBLEFLT: case T_PAGEFLT: return SIGSEGV; default: return signal; } } .... [[stack-fixup]] === Reparación de pila El editor de enlaces en tiempo de ejecución de (RTLD) espera las llamadas etiquetas AUX en la pila durante una llamada a `execve` por lo que se debe realizar una reparación para garantizar esto. Por supuesto, cada sistema RTLD es diferente, por lo que la capa de emulación debe proporcionar su propia rutina de reparación de la pila para hacer esto. Linuxulator también. `elf_linux_fixup` simplemente copia las etiquetas AUX a la pila y ajusta la pila del proceso de espacio de usuario para que apunte justo después de esas etiquetas. Entonces RTLD funciona de manera inteligente. [[aout-support]] === soporte A.OUT La capa de emulación Linux(R) en i386 también soporta binarios A.OUT de Linux(R). Básicamente todo lo descrito en las secciones anteriores se tiene que implementar para el soporte de A.OUT (además de traducción de traps y envío de señales). El soporte de binarios A.OUT ya no se mantiene, en concreto la emulación de 2.6 ya no trabaja con ello pero esto no causa ningún problema ya que linux-base en ports probablemente no soporta en absoluto los binarios A.OUT. Es probable que se quite el soporte en el futuro. La mayoría de lo necesario para cargar binarios A.OUT de Linux(R) está en el fichero [.filename]#imgact_linux.c#. [[mi]] == Parte MI de la capa de emulación Linux(R) Esta sección trata acerca de la parte del Linuxulator que es independiente de la arquitectura. Cubre la infraestructura de emulación necesaria para Linux(R) 2.6, la implementación en i386 del almacenamiento local para hilos (TLS) y futexes. Después hablamos brevemente acerca de algunas llamadas al sistema. [[nptl-desc]] === Descripción de NPTL Una de las áreas de mayor progreso en el desarrollo de Linux(R) 2.6 fue el multihilo. Antes de 2.6, el soporte de multihilo de Linux(R) estaba implementado en la librería linuxthreads. La librería era una implementación parcial de hilos POSIX(R). El sistema de hilos se implementó utilizando procesos separados para cada hilo utilizando la llamada al sistema `clone` para dejarles compartir el espacio de direcciones (y otras cosas). La principal debilidad de esta aproximación era que cada hilo tenía un PID diferente, el envío de señales estaba roto (desde la perspectiva de pthreads), etc. Tampoco el rendimiento era muy bueno (uso de señales `SIGUSR` para sincronización de hilos, consumo de recursos del kernel, etc.) de forma que para solucionar estos problemas se desarrolló un nuevo sistema de hilos que se llamó NPTL. La librería NPTL se centraba en dos cosas pero una tercera surgió de forma que se considera parte de NPTL. Esas dos cosas eran introducir hilos en la estructura de un proceso y los futexes. La tercera cosa adicional fue TLS, que no es necesaria directamente para NPTL pero toda la librería NPTL en espacio de usuario depende de ello. Todas estas mejoras resultaron en mucho mejor rendimiento y adhesión a los estándares. NPTL es a día de hoy una librería de hilos estándar en los sistemas Linux(R). La implementación del Linuxulator de FreeBSD se aproxima a la NTPL en tres áreas principales. TLS, futexes y renombrado de PID que se utiliza para simular hilos de Linux(R). Secciones posteriores describen cada una de estas áreas. [[linux26-emu]] === Infraestructura de emulación de Linux(R) 2.6 Estas secciones tratan con la forma en la que se gestionan los hilos de Linux(R) y cómo lo simulamos en FreeBSD. [[linux26-runtime]] ==== Determinación del entorno de ejecución de la emulación 2.6 La capa de emulación de Linux(R) en FreeBSD soporta la configuración del entorno de ejecución de la versión emulada. Esto se hace vía man:sysctl[8], en concreto `compat.linux.osrelease`. Establecer esta man:sysctl[8] afecta al comportamiento del entorno de ejecución de la capa de emulación. Cuando se establece a 2.6.x se establece el valor de `linux_use_linux26` mientras que si se establece a otra cosa no se pone nada. Esta variable (más las variables correspondientes del mismo tipo por cada jail) determinan qué infraestructura 2.6 (principalmente PID mangling) se usa o no en el código. El establecimiento de la versión se realiza en todo el sistema y afecta a todos los procesos Linux(R). man:sysctl[8] no se debería cambiar cuando un binario Linux(R) se está ejecutando ya que podría romper algo. [[linux-proc-thread]] ==== Procesos Linux(R) e identificadores de hilos Las semánticas de los hilos en Linux(R) son un poco confusas y utilizan una nomenclatura completamente diferente a la utilizada en FreeBSD. Un proceso en Linux(R) consiste en una `struct task` que contiene dos campos identificadores PID y TGID. PID _no_ es el ID del proceso sino el ID del hilo. El TGID identifica a un grupo de hilos o en otras palabras, a un proceso. Para procesos monohilo el PID es igual al TGID. El hilo en NPTL es tan sólo un proceso ordinario que resulta que tiene un TGID que no es igual al PID y que tiene un líder de grupo que no es él mismo (y VM compartida etc. por supuesto). Todo lo demás sucede de la misma forma que en un proceso ordinario. No hay separación entre un estado compartido y una estructura externa como en FreeBSD. Esto crea algo de información duplicada y una posible inconsistencia de datos. El kernel de Linux(R) aparentemente utiliza la información de task->group en algunos sitios y la información de la tarea en otros sitios y no es muy consistente y es propensa a errores. Cada hilo NPTL se crea mediante una llamada a la llamada al sistema `clone` con un conjunto específico de flags (más en la siguiente subsección). La librería NPTL implementa un mecanismo de hilos estricto 1:1. En FreeBSD emulamos hilos NPTL con procesos FreeBSD ordinarios que comparten espacio VM, etc. y la gimnasia que se hace con el PID simplemente se imita en la estructura específica de emulación adjunta al proceso. La estructura adjunta al proceso se ve así: [.programlisting] .... 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 */ }; .... El PID se utiliza para identificar el proceso de FreeBSD que contiene esta estructura. Los campos `child_se_tid` y `child_clear_tid` se usan para hacer un copyout de la dirección del TID cuando un proceso sale y es creado. El puntero `shared` apunta a una estructura compartida entre los hilos. La variable `pdeath_signal` identifica la señal de morir del padre y el punto `threads` se utiliza para enlazar esta estructura a la lista de hilos. La estructura `linux_emuldata_shared` tiene este aspecto: [.programlisting] .... struct linux_emuldata_shared { int refs; pid_t group_pid; LIST_HEAD(, linux_emuldata) threads; /* head of list of linux threads */ }; .... `refs` es un contador de referencias que se usa para determinar cuándo liberar la estructura para evitar pérdidas de memoria. `group_id` se usa para identificar el PID (=TGID) de todo el proceso (=grupo de hilos). El puntero `threads` es la cabecera de la lista de hilos en el proceso. La estructura `linux_emuldata` se puede obtener a partir del proceso utilizando `em_find`. El prototipo de la función es: [.programlisting] .... struct linux_emuldata *em_find(struct proc *, int locked); .... Aquí, `proc` es el proceso del cual queremos la estructura emuldata y el parámetro locked determina si queremos o no bloquear. Los valores aceptados son `EMUL_DOLOCK` y `EMUL_DOUNLOCK`. Más acerca de esto después. [[pid-mangling]] ==== Ajuste de PID Puesto que hay una diferencia en la visión en cuanto a la idea de ID de proceso e ID de hilo entre FreeBSD y Linux(R) tenemos que traducir esa visión de algún modo. Lo hacemos modificando el PID. Esto significa que falseamos lo que son el PID (=TGID) y el TID (=PID) entre el kernel y el espacio de usuario. La regla básica es que en el kernel (en el Linuxulator) PID = PID y TGID = shared -> group pid y que en espacio de usuario presentamos `PID = shared -> group_pid` y `TID = proc -> p_pid`. El miembro PID de la estructura `linux_emuldata` es un PID de FreeBSD. Lo descrito arriba afecta principalmente a las llamadas al sistema getpid, getppid y gettid. Donde utilizamos PID/TGID respectivamente. Al hacer el copyout de los TID en `child_clear_tid` y `child_set_tid` copiamos hacia afuera el PID de FreeBSD. [[clone-syscall]] ==== Llamada al sistema clone La llamada al sistema `clone` es la forma en la que se crean hilos en Linux(R). El prototipo de la llamada es como este: [.programlisting] .... int linux_clone(l_int flags, void *stack, void *parent_tidptr, int dummy, void * child_tidptr); .... El parámetro `flags` le dice a la llamada al sistema cómo se tiene que clonar el proceso exactamente. Como se ha descrito arriba, Linux(R) puede crear procesos compartiendo varias cosas de forma independiente, por ejemplo dos procesos pueden compartir descriptores de ficheros pero no VM, etc. El último byte del parámetro `flags` es la señal de salida del proceso recién creado. El parámetro `stack` si no es `NULL` indica dónde está la pila del hilo y si es `NULL` se supone que debemos hacer un copy-on-write de la pila del proceso que llama (es decir hacer lo que hace la rutina man:fork[2] normal). El parámetro `parent_tidptr` se usa como dirección para copiar hacia afuera el PID del proceso (es decir, el id del hilo) una vez que el proceso está suficientemente instanciado pero todavía no es ejecutable. El parámetro `dummy` está aquí por la convención de llamada tan extraña que tiene esta llamada al sistema en i386. Usa los registros directamente y deja que lo haga el compilador por lo que se necesita una llamada al sistema dummy. El parámetro `child_tidptr` se usa como dirección para copiar hacia afuera el PID una vez que el proceso ha terminado de crearse y cuando el proceso sale. La llamada al sistema en sí procede estableciendo los flags correspondientes dependiendo de los flags que se le hayan pasado. Por ejemplo, `CLONE_VM` se corresponde con RFMEM (compartir VM), etc. El único detalle aquí son `CLONE_FS` y `CLONE_FILES` porque FreeBSD no permite establecerlos por separado por lo que lo falseamos al no establecer RFFDG (la copia de la tabla de descriptores de fichero y otra información de sistemas de ficheros) si alguno de los dos está definido. Esto no causa problemas porque esos dos flags siempre se establecen juntos. Después de establecer los flags el proceso se bifurca utilizando la rutina interna `fork1`, se insta a que el proceso no sea puesto en una cola de ejecución, es decir no se establece como ejecutable. Después de terminar el bifurcado posiblemente establezcamos el padre al nuevo proceso creado para emular la semántica de `CLONE_PARENT`. La siguiente parte es crear los datos de emulación. Los hilos en Linux(R) no señalizan a sus padres de forma que establecemos la señal exit a 0 para desabilitar esto. Después se establecen `child_set_tid` y `child_clear_tid` activando esta funcionalidad posteriormente en el código. En este punto copiamos el PID hacia afuera en la dirección especificada por `parent_tidptr`. La configuración de la pila del proceso se realiza simplemente reescribiendo el registro de marco de hilo `%esp` (`%rsp` en amd64). La siguiente parte es configurar TLS para el proceso recién creado. Después de esto ya se pueden emular las semánticas de man:vfork[2] y finalmente el proceso creado se pone en una cola de ejecución y se copia su PID en el proceso padre mediante el valor de retorno de `clone`. La llamada al sistema `clone` es capaz y de hecho se usa para emular las llamadas al sistema clásicas man:fork[2] y man:vfork[2]. Versiones nuevas de glibc funcionando con kernels 2.6 usan `clone` para implementar las llamadas a man:fork[2] y man:vfork[2]. [[locking]] ==== Bloqueos El mecanismo de bloqueo se implementa por cada subsistema porque no esperamos en ellos mucha contención. Hay dos locks: `emul_lock` se usa para manipular de forma segura `linux_emuldata` y `emul_shared_lock` se usa para manipular `linux_emuldata_shared`. `emul_lcok` es un mutex con el que no se puede dormir mientras que `emul_shared_lock` es un `sx_lock` con el que se puede dormir. Debido al mecanismo de bloqueo por subsistema podemos juntar algunos locks y por eso em_find proporciona acceso sin necesidad de bloqueos. [[tls]] === TLS Esta sección trata sobre TLS, también conocido como almacenamiento local de hilos. [[trheading-intro]] ==== Introducción al manejo de hilos Los hilos en ciencias de la computación son entidades en un proceso que pueden ser planificadas de forma independiente al resto de hilos. Los hilos de un proceso comparten muchos datos del proceso (descriptores de fichero, etc) pero también tienen su propia pila para sus propios datos. Algunas veces hay necesidad para tener datos de nivel de proceso pero específicos para un determinado hilo. Imagina el nombre de un hilo en ejecución o algo así. El API de hilos tradicional de UNIX(R), pthreads proporciona un método para hacerlo mediante man:pthread_key_create[3], man:pthread_setspecific[3] y man:pthread_getspecific[3] donde un hilo puede crear una clave para el dato local del hilo y manipular ese dato mediante man:pthread_getspecific[3] o man:pthread_getspecific[3]. Se definió una nueva palabra clave que especifica que una variable es específica de un hilo. Puedes ver que esta no es la forma más cómoda de conseguir este objetivo. De forma que varios creadores de compiladores de C/C++ introdujeron un mecanismo mejor. También se desarrolló un nuevo método para acceder a dichas variables (al menos en i386). El método de pthreads se suele implementar en espacio de usuario como una tabla de búsqueda trivial. El rendimiento de esta solución no es muy bueno. El nuevo método utiliza registros de segmento (en i386) para direccionar un segmento donde se almacena el área TLS de forma que el acceso real a la variable del hilo consisten en añadir el registro del segmento a la dirección y acceder mediante ella. Los registros de segmento son normalmente `%gs` y `%fs` y actúan como selectores de segmentos. Cada hilo tiene su propia área donde se almacenan lo datos locales al hilo y el segmento se tiene que cargar en cada cambio de contexto. Este método es muy rápido y se utiliza casi en exclusiva en el mundo i386 de UNIX(R). Tanto FreeBSD como Linux(R) implementan esta aproximación y se obtienen muy buenos resultados. El único problema es la necesidad de recargar el segmento en cada cambio de contexto lo que puede hacer los cambios de contexto más lentos. FreeBSD intenta evitar esta sobrecargar utilizando sólo 1 descriptor de segmento para esto mientras que Linux(R) utiliza 3. Algo interesante es que prácticamente nada utiliza más de 1 descriptor (sólo Wine parece utilizar 2) de forma que Linux(R) para un precio innecesario por los cambios de contexto. [[i386-segs]] ==== Segmentos en i386 La arquitectura i386 implementa los llamados segmentos. Un segmento es una descripción de un área de memoria. La dirección base (abajo) del área de memoria, el final (techo), tipo, protección, etc. Se puede acceder a la memoria descrita por un segmento utilizando un registro de selección de segmento (`%cs`, `%ds`, `%ss`, `%es`, `%fs`, `%gs`). Por ejemplo supongamos que tenemos un segmento cuya dirección base es 0x1234 y también tenemos su longitud y este código: [.programlisting] .... mov %edx,%gs:0x10 .... Esto cargará el contenido del registro `%edx` en la ubicación de memoria 0x1244. Algunos registros de segmento tienen un uso especial, por ejemplo `%cs` se utiliza para el segmento de código y `%ss` se utiliza para el segmento de pila pero `%fs` y `%gs` generalmente no se utilizan. Los segmentos se almacenan en una tabla GDT global o en una tabla LDT local. Se accede a LDT a través de una entrada en el GDT. El LDT puede almacenar más tipos de segmentos. LDT puede ser por proceso. Ambas tablas definen hasta 8191 entradas. [[linux-i386]] ==== Implementación en Linux(R) i386 Hay dos formas principales de establecer TLS en Linux(R). Se puede establecer cuando se clona un proceso con la llamada al sistema `clone` o se puede llamar a `set_thread_area`. Cuando un proceso para el flag `CLONE_SETTLS` a `clone`, el kernel espera que la memoria apuntada por el registro `%esi` sea una representación en espacio de usuario de un segmento Linux(R) que se traduce a la representación máquina de un segmento y se carga en una entrada de la GDT. La entrada de la GDT se puede especificar con un número o se puede usar -1 que significa que el sistema puede escoger la primera entrada que encuentre libre. En la práctica, la gran mayoría de programas utilizan sólo una entrada TLS y no se preocupan acerca del número de la misma. Aprovechamos esto en la emulación y de hecho dependemos de ello. [[tls-emu]] ==== Emulación del TLS de Linux(R) [[tls-i386]] ===== i386 La carga del TLS del hilo actual se realiza llamando a `set_thread_area` mientras que la carga del TLS para un segundo proceso en `clone` se realiza en el bloque separado en `clone`. Estas dos funciones son muy parecidas. La única diferencia es la carga del segmento GDT que sucede en el siguiente cambio de contexto para el nuevo proceso creado mientras que `set_thread_area` tiene que cargarlos directamente. El código básicamente hace esto. Copia la forma Linux(R) del descriptor de segmento desde el espacio de usuario. El código comprueba el número del descriptor pero como difieren entre FreeBSD y Linux(R) lo falseamos un poco. Sólo soportamos los índices 6, 3 y -1. El 6 es un número genuino de Linux(R), el tres es genuino de FreeBSD y el -1 significa autoselección. Después establecemos el número del descriptor de forma constante a 3 y lo copiamos de vuelva a espacio de usuario. Dependemos de que el proceso en espacio de usuario use el número del descriptor pero esto funciona casi siempre (no he visto nunca un caso donde no funciones) ya que el proceso de espacio de usuario normalmente pasa -1. Después convertimos el descriptor de la forma Linux(R) a una forma dependiente de la máquina (es decir forma independiente del sistema operativo) y lo copiamos al descriptor de segmento definido en FreeBSD. Finalmente podemos cargarlo. Asignamos el descriptor en los PCB (bloque de control de proceso) de los hilos y cargamos el segmento `%gs` utilizando `load_gs`. Esta carga se tiene que hacer dentro de una sección crítica de forma que nada la interrumpa. El caso `CLONE_SETTLS` funciona exactamente así salvo que no se realiza la carga utilizando `load_gs`. El segmento que se usa para esto (número de segmento 3) se comparte para este uso entre los procesos de FreeBSD y de Linux(R) de forma que la capa de emulación Linux(R) no añade nada de sobrecarga respecto al funcionamiento normal de FreeBSD. [[tls-amd64]] ===== amd64 La implementación de amd64 es similar a la de i386, pero inicialmente no se utilizó un descriptor de segmento de 32 bits para este propósito (por lo tanto, ni siquiera los usuarios nativos de TLS de 32 bits funcionaban), por lo que tuvimos que agregar dicho segmento e implementar su carga en cada cambio de contexto (cuando se establece el flag de uso de 32 bits). Aparte de esto, la carga de TLS es exactamente la misma, solo que los números de segmento son diferentes y el formato del descriptor y la carga difieren ligeramente. [[futexes]] === Futexes [[sync-intro]] ==== Introducción a la sincronización Los hilos necesitan algún tipo de sincronización y POSIX(R) proporciona algunos de ellos: mutex para exclusión mutua, locks de lectura y escritura para exclusión mutua con una proporción sesgada de lecturas y escrituras y variables de condición para señalar un cambio de estado. Es interesante notar que la API de hilos de POSIX(R) carece de soporte para semáforos. Esas implementaciones de rutinas de sincronización dependen en gran medida del tipo de soporte de hilos que tenemos. En el modelo puro 1:M (espacio de usuario), la implementación se puede realizar únicamente en el espacio de usuario y, por lo tanto, es muy rápida (las variables de condición probablemente terminarán implementándose mediante señales, es decir, no tan rápido) y simple. En el modelo 1:1, la situación también es bastante clara: los hilos deben sincronizarse utilizando las primitivas del kernel (lo cual es muy lento porque se debe realizar una llamada al sistema). El escenario mixto M:N simplemente combina el primer y segundo enfoque o se basa únicamente en el kernel. La sincronización de hilos es una parte vital de la programación habilitada para hilos y su rendimiento puede afectar mucho al programa resultante. Pruebas de rendimiento recientes en el sistema operativo FreeBSD mostraron que una implementación mejorada de sx_lock producía un 40% de aceleración en _ZFS_ (un usuario intensivo de sx), esto es algo dentro del kernel pero muestra claramente cuán importante es el rendimiento de las primitivas de sincronización. Los programas multihilo se deberían escribir con la menor contención posible. De otro modo en lugar de hacer trabajo útil el hilo simplemente espera en un bloqueo. Como resultado los programas mejores escritos muestran poca contención en bloqueos. [[futex-intro]] ==== Introducción a los futexes Linux(R) implementa multihilo 1:1, es decir tiene que utilizar primitivas de sincronización dentro del kernel. Como se ha dicho antes, un programa bien escrito tiene poca contención. Así que una secuencia típica se podría realizar como dos incrementos/decrementos de contadores de referencia mutex atómicos, lo que es muy rápido, como se muestra en el siguiente ejemplo: [.programlisting] .... pthread_mutex_lock(&mutex); ... pthread_mutex_unlock(&mutex); .... El modelo 1:1 nos obliga a realizar dos llamadas al sistema para esas llamadas mutex, lo cual es muy lento. La solución que implementa Linux(R) 2.6 se llama futexes. Los futexes implementan la comprobación de la contención en espacio de usuario y llaman al kernel sólo en caso de contención. Por lo tanto el caso típico tiene lugar sin intervención del kernel. Esto ofrece una implementación de primitivas de sincronización razonablemente rápidas y flexibles. [[futex-api]] ==== Futex API La llamada al sistema futex se ve así: [.programlisting] .... int futex(void *uaddr, int op, int val, struct timespec *timeout, void *uaddr2, int val3); .... En este ejemplo `uaddr` es una dirección del mutex en espacio de usuario, `op` es una operación que estamos a punto de realizar y los otros parámetros tienen significados por operación. Los Futexes implementan las siguientes operaciones: * `FUTEX_WAIT` * `FUTEX_WAKE` * `FUTEX_FD` * `FUTEX_REQUEUE` * `FUTEX_CMP_REQUEUE` * `FUTEX_WAKE_OP` [[futex-wait]] ===== FUTEX_WAIT Esta operación verifica que se ha escrito el valor `val` en la dirección `uaddr`. Si no, se devuelve `EWOULDBLOCK`, de otro modo el hilo se encola en el futex y se suspende. Si el argumento `timeout` no es cero entonces especifica el tiempo máximo para estar durmiendo, de lo contrario se duerme indefinidamente. [[futex-wake]] ===== FUTEX_WAKE Esta operación toma un futex en la dirección `uaddr` y despierta los primeros `val` futexes encolados en el futex. [[futex-fd]] ===== FUTEX_FD Esta operación asocia un descriptor de archivo con un futex dado. [[futex-requeue]] ===== FUTEX_REQUEUE Esta operación toma `val` hilos encolados en el futex que está en la dirección `uaddr`, los despierta y toma los siguientes `val2` hilos y los reencola en el futex en la dirección `uaddr2`. [[futex-cmp-requeue]] ===== FUTEX_CMP_REQUEUE Esta operación hace lo mismo que `FUTEX_REQUEUE` pero primero comprueba que `val3` sea igual que `val`. [[futex-wake-op]] ===== FUTEX_WAKE_OP Esta operación realiza una operación atómica en `val3` (que contiene otro valor codificado) y `uaddr`. Después despierta `val` hilos en el futex de la dirección `uaddr` y si la operación atómica devolvió un número positivo despierta `val2` hilos en el futex de la dirección `uaddr2`. Las operaciones implementadas en `FUTEX_WAKE_OP`: * `FUTEX_OP_SET` * `FUTEX_OP_ADD` * `FUTEX_OP_OR` * `FUTEX_OP_AND` * `FUTEX_OP_XOR` [NOTE] ==== No hay parámetro `val2` en el prototipo de futex. `val2` se toma del parámetro `struct timespec *timeout` para las operaciones `FUTEX_REQUEUE`, `FUTEX_CMP_REQUEUE` y `FUTEX_WAKE_OP`. ==== [[futex-emu]] ==== Emulación Futex en FreeBSD La emulación de futex en FreeBSD ha sido importada de NetBSD y después extendida por nosotros. Se encuentra en los ficheros `linux_futex.c` y [.filename]#linux_futex.h#. La estructura `futex` tiene este aspecto: [.programlisting] .... struct futex { void *f_uaddr; int f_refcount; LIST_ENTRY(futex) f_list; TAILQ_HEAD(lf_waiting_paroc, waiting_proc) f_waiting_proc; }; .... Y la estructura `waiting_proc` es: [.programlisting] .... struct waiting_proc { struct thread *wp_t; struct futex *wp_new_futex; TAILQ_ENTRY(waiting_proc) wp_list; }; .... [[futex-get]] ===== futex_get / futex_put Un futex se obtiene utilizando la función `futex_get`, que busca en una lista lineal de futexes y devuelve el encontrado o crea un nuevo futex. Cuando liberamos un futex llamamos a la función `futex_put`, que disminuye un contador de referencia del futex y si el refcount llega a cero lo libera. [[futex-sleep]] ===== futex_sleep Cuando un futex encola un hilo para que duerma crea una estructura `working_proc` y la pone en la lista dentro de la estructura del futext, después simplemente llama a man:tsleep[9] para suspender el hilo. El tiempo de suspensión puede finalizar por timeout. Después de volver the man:tsleep[9] (el hilo ha sido despertado o ha ocurrido un timeout) se quita la estructura `working_proc` de la lista y se destruye. Todo esto se hace en la función `futex_sleep`. Si se nos despertó con `futex_wak` tenemos `wp_new_futex` establecido de forma que lo utilizamos para dormir. De este modo el reencolado en realidad se hace en esta función. [[futex-wake-2]] ===== futex_wake Despertar a un hilo que está durmiendo en un futex se hace con la función `futex_wake`. En esta función lo primero que hacemos es imitar el extraño comportamiento de Linux(R), donde despierta N hilos para todas las operaciones, la únca excepción es que las operaciones REQUEUE se hacen en N+1 hilos. Pero normalmente esto no supone ninguna diferencia ya que estamos despertando todos los hilos. Lo siguiente en la función es el bucle en el que despertamos n hilos, después comprobamos si hay algún futex nuevo para reencolar. Si es así, reencolamos un máximo de n2 hilos en el nuevo futex. Esto coopera con `futex_sleep`. [[futex-wake-op-2]] ===== futex_wake_op La operación `FUTEX_WAKE_OP` is bastante complicada. Primero obtenemos dos futex en las direcciones `uaddr` y `uaddr2` después realizamos una operación atómica usando `val3` y `uaddr2`. Después se despierta a `val` hilos que estuvieran durmiendo y si se cumple la condición de la operación atómica despertamos `val2` (es decir `timeout`) hilos durmientes en el segundo futex. [[futex-atomic-op]] ===== operación atómica futex La operación atómica toma dos parámetros `encoded_op` y `uaddr`. La operación codificada codifica la operación en sí, comparando valor, argumento de operación y argumento de comparación. El pseudocódigo para la operación es como este: [.programlisting] .... oldval = *uaddr2 *uaddr2 = oldval OP oparg .... Y esto se hace automáticamente. Primero se realiza la copia del número en `uaddr` y la operación ha terminado. El código maneja fallos de página y si no ocurre ningún se compara `oldval` con `cmparg` con el comparador cmp. [[futex-locking]] ===== Bloqueo futex La implementación de futex utiliza dos listas de bloqueo que protegen `sx_lock` y locks globales (ya sea Giant u otro `sx_lock`). Cada operación se realiza estando bloqueada desde el principio hasta el final. [[syscall-impl]] === Implementación de varias llamadas al sistema En esta sección voy a describir algunas llamadas al sistema más pequeñas que vale la pena mencionar porque su implementación no es obvia o esas llamadas al sistema son interesantes desde otro punto de vista. [[syscall-at]] ==== Familia de llamadas al sistema *at Durante el desarrollo del kernel 2.6.16 de Linux(R) se añadieron las llamadas al sistema *at. Esas llamadas (`openat` por ejemplo) funcionan igual que sus pares sin `at` con la pequeña diferencia del parámetro `dirfd`. Este parámetro cambia con el fichero dado sobre el que se va a realizar la llamada al sistema. Cuando el parámetro `filename` es absoluto `dirfd` es ignorado pero cuando la ruta al fichero es relativa, entra en juego. El parámetro `dirfd` es un directorio relativo al cual se comprueba la ruta relativa. El parámetro `dirfd` es un descriptor de fichero de algún directorio o `AT_FDCWD`. Por ejemplo la llamada al sistema `openat` podría ser así: [.programlisting] .... descriptor de fichero 123 = /tmp/foo/, directorio de trabajo actual = /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 */ .... Esta infraestructura es necesaria para evitar condiciones de carrera cuando se abren ficheros fuera del directorio de trabajo actual. Imagina un proceso que consiste en dos hilos, hilo A e hilo B. El hilo A realiza `open(./tmp/foo/bah., flags, mode)` y antes de volver es desalojado y se ejecuta el hilo B. El hilo B no se preocupa por las necesidades del hilo A y renombra o elimina [.filename]#/tmp/foo/#. Tenemos una condición de carrera. Para evitar esto podemos abrir [.filename]#/tmp/foo# y utilizarlo como `dirfd` en la llamada al sistema `openat`. Esto permite al usuario implementar directorios de trabajo por hilo. La familia *at de llamadas al sistema de Linux(R) contiene: `linux_openat`, `linux_mkdirat`, `linux_mknodat`, `linux_fchownat`, `linux_futimesat`, `linux_fstatat64`, `linux_unlinkat`, `linux_renameat`, `linux_linkat`, `linux_symlinkat`, `linux_readlinkat`, `linux_fchmodat` y `linux_faccessat`. Todas se implementan utilizando la rutina modificada man:nami[9] y una sencilla capa de envoltorio. [[implementation]] ===== Implementación La implementación se hace modificando la rutina man:namei[9] (descrita arriba) para que tenga un parámetro adicional `dirfd` en su estructura `nameidata`, que especifica el punto de comienzo de la búsqueda de la ruta en lugar de utilizar el directorio de trabajo cada vez. La resolución de `dirfd` a vnode a partir del número de descriptor de fichero se hace en las llamadas al sistema *at nativas. Cuando `dirfd` es `AT_FDCWD` la entrada `dvp` en la estructura `nameidata` es `NULL` pero cuando `dirfd` otro número obtenemos el fichero para este descriptor de fichero, comprobamos si el fichero es válido y si tiene un vnode asociado lo obtenemos. Después comprobamos que el vnode sea un directorio. En la rutina man:namei[9] real simplemente sustituimos el vnode `dvp` por la variable `dp` en la función man:namei[9] que determina el punto de comienzo. man:namei[9] no se usa directamente sino mediante una traza de diferentes funciones a diferentes niveles. Por ejemplo `openat` hace esto: [.programlisting] .... openat() --> kern_openat() --> vn_open() -> namei() .... Por esta razón `kern_open` y `vn_open` deben modificarse para incorporar el parámetro adicional `dirfd`. No se crea una capa de compatibilidad para aquellos porque no hay muchos usuarios de esta y los usuarios se pueden convertir fácilmente. Esta implementación general permite a FreeBSD implementar su propio *at llamadas al sistema. Esto está siendo discutido ahora mismo. [[ioctl]] ==== Ioctl La interfaz ioctl es bastante frágil debido a su genericidad. Tenemos que tener en cuenta que los dispositivos difieren entre Linux(R) y FreeBSD, por lo que se debe tener cuidado para que la emulación de ioctl funcione correctamente. El manejo de ioctl se implementa en `linux_ioctl.c`, donde se define la función `linux_ioctl`. Esta función simplemente itera sobre conjuntos de manejadores ioctl para encontrar un manejador que implemente un comando dado. La llamada al sistema ioctl tiene tres parámetros, el descriptor de archivo, el comando y un argumento. El comando es un número de 16 bits, que en teoría se divide en 8 bits altos que determinan la clase del comando ioctl y 8 bits bajos, que son el comando real dentro del conjunto dado. La emulación aprovecha esta división. Implementamos controladores para cada conjunto, como `sound_handler` o `disk_handler`.Cada controlador tiene un comando máximo y un comando mínimo definido, que se utiliza para determinar qué controlador se utiliza. Hay leves problemas con este enfoque porque Linux(R) no usa la división de conjuntos de manera consistente, por lo que a veces los ioctls de un conjunto diferente están dentro de un conjunto al que no deberían pertenecer (ioctls genéricos SCSI dentro del conjunto cdrom, etc.). FreeBSD actualmente no implementa muchos ioctls de Linux(R) (en comparación con NetBSD, por ejemplo) pero el plan es portarlos de NetBSD. La tendencia es usar ioctls de Linux(R) incluso en los controladores nativos de FreeBSD debido a la fácil migración de las aplicaciones. [[debugging]] ==== Depuración Cada llamada al sistema debería ser depurable. Para ello introducimos una pequeña infraestructura. Tenemos la función ldebug, que indica si una llamada al sistema determinada debe depurarse (configurable mediante un sysctl). Para imprimir tenemos macros LMSG y ARGS. Se utilizan para alterar una cadena imprimible para mensajes de depuración uniformes. [[conclusion]] == Conclusión [[results]] === Resultados A fecha de abril de 2007 la capa de emulación de Linux(R) es capaz de emular el kernel Linux(R) 2.6.16 bastante bien. Los problemas que quedan son sobre futexes, la familia de llamadas al sistema *at sin terminar, problemas con el envío de señales, la ausencia de `epoll` y `inotify` y probablemente algunos bugs que no se han descubierto todavía. A pesar de esto somos capaces de ejecutar básicamente todos los programas Linux(R) incluidos en la colección de ports con Fedora Core 4 en 2.6.16 y hay algunos informes rudimentarios de éxito con Fedora Core 6 en 2.6.16. El linux_base de Fedora Core 6 se añadió al repositorio recientemente permitiendo más pruebas de la capa de emulación y dándonos más pistas sobre dónde debemos poner el esfuerzo para implementar las cosas que faltan. Somos capaces de ejecutar las aplicaciones más usadas como package:www/linux-firefox[], package:net-im/skype[] y algunos juegos de la colección de ports. Algunos programas tienen un mal comportamiento bajo la emulación de 2.6 pero se está investigando y con suerte se solucionará pronto. La única aplicación grande que se sabe que no funciona es el Java(TM) Development Kit de Linux(R). Esto es porque requiere `epoll` el cual no está directamente relacionado con el kernel Linux(R) 2.6. Esperamos habilitar la emulación 2.6.16 por defecto algún tiempo después del lanzamiento de FreeBSD 7.0 al menos para exponer las partes de la emulación 2.6 para pruebas más amplias. Una vez hecho esto, podemos cambiar a Fedora Core 6 linux_base, que es el plan definitivo. [[future-work]] === Trabajo futuro El trabajo futuro debe centrarse en solucionar los problemas restantes con futexes, implementar el resto de la familia de llamadas al sistema *at, arreglar el envío de señales y posiblemente implementar `epoll` y `inotify`. Esperamos poder ejecutar pronto los programas más importantes sin problemas, por lo que podremos cambiar a la emulación 2.6 por defecto y hacer que Fedora Core 6 sea la linux_base predeterminada porque nuestro Fedora Core 4 que usamos actualmente ya no es compatible. El otro objetivo posible es compartir nuestro código con NetBSD y DragonflyBSD. NetBSD tiene algo de soporte para la emulación 2.6 pero está lejos de estar terminado y no se ha probado realmente. DragonflyBSD ha expresado cierto interés en portar las mejoras 2.6. En general, conforme se desarrolla Linux(R) nos gustaría seguir actualizados con su desarrollo, implementando las nuevas llamadas al sistema. Splice se me viene a la cabeza. Algunas de las llamadas al sistema ya implementadas son subóbtimas, por ejemplo `mremap` y otras. Se pueden hacer algunas mejoras de rendimiento, bloqueos más finos y otras cosas. [[team]] === Equipo Colaboré en este proyecto con (en orden alfabético): * `{jhb}` * `{kib}` * Emmanuel Dreyfus * Scot Hetzel * `{jkim}` * `{netchild}` * `{ssouhlal}` * Li Xiao * `{davidxu}` Me gustaría agradecer a todas esas personas por sus consejos, revisiones de código y apoyo general. [[literatures]] == Bibliografía -. Marshall Kirk McKusick - George V. Nevile-Neil. Diseño e implementación del sistema operativo FreeBSD. Addison-Wesley, 2005. +. Marshall Kirk McKusick - George V. Neville-Neil. Diseño e implementación del sistema operativo FreeBSD. Addison-Wesley, 2005. . https://tldp.org[https://tldp.org] . https://www.kernel.org[https://www.kernel.org] diff --git a/documentation/content/pt-br/articles/linux-emulation/_index.adoc b/documentation/content/pt-br/articles/linux-emulation/_index.adoc index 27ae1fe7ca..5e0a712e05 100644 --- a/documentation/content/pt-br/articles/linux-emulation/_index.adoc +++ b/documentation/content/pt-br/articles/linux-emulation/_index.adoc @@ -1,973 +1,973 @@ --- authors: - author: 'Roman Divacky' email: rdivacky@FreeBSD.org description: 'Uma descrição técnica sobre os internals da camada de emulação do Linux no FreeBSD' tags: ["Emulation", "Linuxulator", "kernel", "FreeBSD"] title: 'Emulação do Linux® no FreeBSD' trademarks: ["freebsd", "ibm", "adobe", "netbsd", "realnetworks", "oracle", "linux", "sun", "general"] --- = Emulação do Linux(R) no FreeBSD :doctype: article :toc: macro :toclevels: 1 :icons: font :sectnums: :sectnumlevels: 6 :source-highlighter: rouge :experimental: :images-path: articles/linux-emulation/ ifdef::env-beastie[] ifdef::backend-html5[] include::shared/authors.adoc[] include::shared/mirrors.adoc[] include::shared/releases.adoc[] include::shared/attributes/attributes-{{% lang %}}.adoc[] include::shared/{{% lang %}}/teams.adoc[] include::shared/{{% lang %}}/mailing-lists.adoc[] include::shared/{{% lang %}}/urls.adoc[] :imagesdir: ../../../images/{images-path} endif::[] ifdef::backend-pdf,backend-epub3[] include::../../../../shared/asciidoctor.adoc[] endif::[] endif::[] ifndef::env-beastie[] include::../../../../../shared/asciidoctor.adoc[] endif::[] [.abstract-title] Resumo Esta tese de mestrado trata da atualização da camada de emulação do Linux(R) (chamada de _Linuxulator_). A tarefa consistiu em atualizar a camada para corresponder à funcionalidade do Linux(R) 2.6. Como implementação de referência, foi escolhido o kernel Linux(R) 2.6.16. O conceito é vagamente baseado na implementação do NetBSD. A maior parte do trabalho foi realizada no verão de 2006 como parte do programa de estudantes do Google Summer of Code. O foco foi trazer o suporte do _NPTL_ (nova biblioteca de threads POSIX(R)) para a camada de emulação, incluindo _TLS_ (armazenamento local de threads), _futexes_ (mutexes de espaço do usuário rápidos), _PID mangling_ e algumas outras pequenas coisas. Muitos problemas pequenos foram identificados e corrigidos durante o processo. Meu trabalho foi integrado ao repositório principal do FreeBSD e será incluído na próxima versão 7.0R. Nós, a equipe de desenvolvimento de emulação, estamos trabalhando para tornar a emulação do Linux(R) 2.6 a camada de emulação padrão no FreeBSD. ''' toc::[] [[intro]] == Introdução Nos últimos anos, os sistemas operacionais de código aberto baseados em UNIX(R) começaram a ser amplamente implantados em servidores e máquinas clientes. Entre esses sistemas operacionais, gostaria de destacar dois: o FreeBSD, por sua herança BSD, código comprovado ao longo do tempo e muitos recursos interessantes, e o Linux(R), por sua ampla base de usuários, comunidade de desenvolvedores entusiastas e apoio de grandes empresas. O FreeBSD tende a ser usado em máquinas de classe servidor que executam tarefas de rede intensivas, com menos uso em máquinas de classe desktop para usuários comuns. Enquanto o Linux(R) tem o mesmo uso em servidores, mas é usado muito mais por usuários domésticos. Isso leva a uma situação em que há muitos programas somente binários disponíveis para Linux(R) que não possuem suporte para o FreeBSD. Naturalmente, surge a necessidade da capacidade de executar binários Linux(R) em um sistema FreeBSD e é isso que esta tese trata: a emulação do kernel Linux(R) no sistema operacional FreeBSD. Durante o verão de 2006, a Google Inc. patrocinou um projeto que se concentrou na extensão da camada de emulação do Linux® (chamada de Linuxulator) no FreeBSD para incluir as funcionalidades do Linux® 2.6. Esta tese foi escrita como parte deste projeto. [[inside]] == Uma olhada por dentro... Nesta seção, vamos descrever cada sistema operacional em questão. Como eles lidam com syscalls, trapframes, etc., tudo o que é de baixo nível. Também descrevemos a maneira como eles entendem os recursos comuns do UNIX(R), como o que é um PID, o que é uma thread, etc. Na terceira subseção, falamos sobre como a emulação do UNIX(R) em cima do UNIX(R) poderia ser feita de maneira geral. [[what-is-unix]] === O que é UNIX(R) UNIX(R) é um sistema operacional com uma longa história que influenciou praticamente todos os outros sistemas operacionais atualmente em uso. Desde os anos 1960, seu desenvolvimento continua até os dias de hoje (embora em projetos diferentes). O desenvolvimento do UNIX(R) logo se dividiu em duas principais vertentes: as famílias BSDs e System III/V. Elas se influenciaram mutuamente ao adotar um padrão comum para o UNIX(R). Entre as contribuições originadas no BSD, podemos citar memória virtual, rede TCP/IP, FFS e muitas outras. O branch do System V contribuiu com primitivas de comunicação interprocesso do SysV, copy-on-write, etc. O UNIX(R) em si não existe mais, mas suas ideias foram utilizadas por muitos outros sistemas operacionais ao redor do mundo, formando o que chamamos de sistemas operacionais semelhantes ao UNIX(R). Nos dias atuais, os mais influentes são Linux(R), Solaris e possivelmente (em certa medida) o FreeBSD. Existem também derivados do UNIX(R) desenvolvidos por empresas (AIX, HP-UX etc.), mas eles têm migrado cada vez mais para os sistemas mencionados anteriormente. Vamos resumir as características típicas do UNIX(R). [[tech-details]] === Detalhes técnicos Cada programa em execução constitui um processo que representa um estado da computação. Um processo em execução é dividido entre o espaço do kernel e o espaço do usuário. Algumas operações só podem ser realizadas a partir do espaço do kernel (lidar com hardware etc.), mas o processo deve passar a maior parte de sua vida útil no espaço do usuário. O kernel é onde ocorre o gerenciamento dos processos, hardware e detalhes de baixo nível. O kernel fornece uma API UNIX(R) padronizada e unificada para o espaço do usuário. As mais importantes estão descritas abaixo. [[kern-proc-comm]] ==== Comunicação entre o kernel e o processo de espaço do usuário A API comum do UNIX(R) define uma syscall como uma forma de emitir comandos de um processo do espaço do usuário para o kernel. A implementação mais comum é feita por meio de uma interrupção ou instrução especializada (pense nas instruções `SYSENTER`/`SYSCALL` para ia32). As syscalls são definidas por um número. Por exemplo, no FreeBSD, o número da syscall 85 é a man:swapon[2] e o número da syscall 132 é a man:mkfifo[2]. Algumas syscalls requerem parâmetros, que são passados do espaço do usuário para o espaço do kernel de várias maneiras (dependendo da implementação). As syscalls são síncronas. Outra forma possível de comunicação é por meio de uma _trap_. As traps ocorrem de forma assíncrona após algum evento ocorrer (divisão por zero, falta de página etc.). Uma trap pode ser transparente para um processo (falta de página) ou pode resultar em uma reação, como o envio de um _sinal_ (divisão por zero). [[proc-proc-comm]] ==== Comunicação entre processos Existem outras APIs (System V IPC, memória compartilhada, etc.), mas a API mais importante é o sinal. Os sinais são enviados por processos ou pelo kernel e recebidos por processos. Alguns sinais podem ser ignorados ou tratados por uma rotina fornecida pelo usuário, enquanto outros resultam em uma ação predefinida que não pode ser alterada ou ignorada. [[proc-mgmt]] ==== Gerenciamento de processos As instâncias do kernel são processadas primeiro no sistema (chamado de init). Todo processo em execução pode criar uma cópia idêntica de si mesmo usando a syscall man:fork[2]. Algumas versões ligeiramente modificadas dessa syscall foram introduzidas, mas a semântica básica é a mesma. Todo processo em execução pode se transformar em outro processo usando a syscall man:exec[3]. Foram introduzidas algumas modificações nessa syscall, mas todas servem ao mesmo propósito básico. Os processos encerram suas vidas chamando a syscall man:exit[2]. Cada processo é identificado por um número único chamado PID. Todo processo possui um processo pai (parent) definido (identificado pelo seu PID). [[thread-mgmt]] ==== Gerenciamento de threads No traditional UNIX(R), não é definida nenhuma API nem implementação para threads, enquanto o POSIX(R) define sua API de threads, mas a implementação é indefinida. Tradicionalmente, havia duas maneiras de implementar threads. Tratá-los como processos separados (threading 1:1) ou envolver todo o grupo de threads em um único processo e gerenciar as threads no espaço do usuário (threading 1:N). Vamos comparar as principais características de cada abordagem: 1:1 threading - Threads pesadas - O agendamento não pode ser alterado pelo usuário (ligeiramente atenuada pela API POSIX(R)) + não necessita de envolvimento do syscall + pode utilizar várias CPUs 1: N threading + threads leves + agendamento pode ser facilmente alterado pelo usuário - As chamadas de sistema devem ser encapsuladas - Não pode utilizar mais do que uma CPU [[what-is-freebsd]] === O que é o FreeBSD? O projeto FreeBSD é um dos sistemas operacionais de código aberto mais antigos atualmente disponíveis para uso diário. É um descendente direto do UNIX(R) genuíno, portanto, poderia ser considerado um verdadeiro UNIX(R), embora questões de licenciamento não permitam isso. O início do projeto remonta ao início dos anos 1990, quando um grupo de usuários do BSD modificou o sistema operacional 386BSD. Com base neste conjunto de patches, um novo sistema operacional surgiu, chamado FreeBSD por causa de sua licença liberal. Outro grupo criou o sistema operacional NetBSD com objetivos diferentes em mente. Vamos nos concentrar no FreeBSD. O FreeBSD é um sistema operacional baseado em UNIX(R) moderno, com todos os recursos do UNIX(R). Multitarefa preemptiva, facilidades multiusuário, rede TCP/IP, proteção de memória, suporte a multiprocessamento simétrico , memória virtual com cache de memória e buffer combinados, todos estão presentes. Uma das características interessantes e extremamente úteis é a capacidade de emular outros sistemas operacionais semelhantes ao UNIX(R). A partir de dezembro de 2006 e do desenvolvimento 7-CURRENT, as seguintes funcionalidades de emulação são suportadas: * Emulação FreeBSD/i386 no FreeBSD/amd64 * Emulação de FreeBSD/i386 no FreeBSD/ia64 * Emulação do sistema operacional Linux(R) no FreeBSD * Emulação de NDIS da interface de drivers de rede do Windows * Emulação de NetBSD do sistema operacional NetBSD * Suporte PECoff para executáveis PECoff do FreeBSD * SVR4-emulação do UNIX(R) da revisão 4 do System V As emulações desenvolvidas ativamente são a camada Linux(R) e várias camadas FreeBSD-on-FreeBSD. Outras não devem funcionar corretamente ou serem utilizáveis atualmente. [[freebsd-tech-details]] ==== Detalhes técnicos O FreeBSD é uma variante tradicional do UNIX(R) no sentido de dividir a execução dos processos em dois espaços: espaço do kernel e espaço do usuário. Existem dois tipos de entrada de processo no kernel: uma syscall e uma armadilha (trap). Existe apenas uma maneira de retornar. Nas seções subsequentes, descreveremos os três portões de/para o kernel. Toda a descrição se aplica à arquitetura i386, já que o Linuxulator existe apenas lá, mas o conceito é semelhante em outras arquiteturas. As informações foram retiradas de [1] e do código-fonte. [[freebsd-sys-entries]] ===== Entradas do sistema O O FreeBSD tem uma abstração chamada de carregador de classe de execução, que é uma cunha no syscall man:execve[2]. Isso utiliza uma estrutura `sysentvec`, que descreve uma ABI executável. Ela contém coisas como uma tabela de tradução de errno, uma tabela de tradução de sinais, várias funções para atender às necessidades de syscall (ajuste de pilha, coredumping, etc.). Cada ABI que o kernel do FreeBSD deseja suportar deve definir essa estrutura, pois ela é usada posteriormente no código de processamento de syscall e em alguns outros lugares. As entradas do sistema são tratadas por manipuladores de interrupção, onde podemos acessar tanto o espaço do kernel quanto o espaço do usuário de uma só vez. [[freebsd-syscalls]] ===== Syscalls As chamadas de sistema (syscalls) no FreeBSD são realizadas executando a interrupção `0x80` com o registro `%eax` definido para o número desejado da syscall e os argumentos passados na pilha. Quando um processo emite a interrupção `0x80`, o tratador de interrupção `int0x80` da syscall é acionado (definido em [.filename]#sys/i386/i386/exception.s#), que prepara os argumentos (ou seja, copia-os para a pilha) para uma chamada à função C man:syscall[2] (definida em [.filename]#sys/i386/i386/trap.c#), que processa o trapframe passado. O processamento consiste em preparar a syscall (dependendo da entrada `sysvec`), determinar se a syscall é de 32 bits ou 64 bits (alterando o tamanho dos parâmetros), em seguida, os parâmetros são copiados, incluindo a syscall. Em seguida, a função da syscall real é executada com o processamento do código de retorno (casos especiais para erros `ERESTART` e `EJUSTRETURN`). Por fim, é agendado um `userret()`, alternando o processo de volta para o espaço do usuário. Os parâmetros para o manipulador da syscall real são passados na forma de `struct thread *td`, `struct syscall args *`, em que o segundo parâmetro é um ponteiro para a estrutura de parâmetros copiada. [[freebsd-traps]] ===== Armadilhas (Traps) O tratamento de traps no FreeBSD é semelhante ao tratamento de syscalls. Sempre que ocorre uma trap, um manipulador em assembly é chamado. Ele é escolhido entre alltraps, alltraps com registradores empurrados ou calltrap, dependendo do tipo de trap. Esse manipulador prepara os argumentos para uma chamada à função em C `trap()` (definida em [.filename]#sys/i386/i386/trap.c#), que então processa a trap ocorrida. Após o processamento, pode ser enviado um sinal para o processo e/ou retornar para o espaço do usuário usando `userret()`. [[freebsd-exits]] ===== Saídas As saídas do kernel para o espaço do usuário acontecem usando a rotina em assembly `doreti`, independentemente se o kernel foi acessado por uma interrupção (trap) ou por uma chamada de sistema. Isso restaura o status do programa da pilha e retorna para o espaço do usuário. [[freebsd-unix-primitives]] ===== Primitivas do UNIX(R) O sistema operacional FreeBSD adere ao esquema tradicional do UNIX(R), onde cada processo possui um número de identificação exclusivo, chamado de _PID_ (Process ID). Os números de PID são alocados linearmente ou aleatoriamente, variando de `0` a `PID_MAX`. A alocação dos números de PID é feita usando busca linear no espaço de PID. Cada thread em um processo recebe o mesmo número de PID como resultado da chamada do man:getpid[2]. Atualmente, existem duas maneiras de implementar threading no FreeBSD. A primeira maneira é a modelagem de threads M:N, seguida pelo modelo de thread 1:1. A biblioteca padrão usada é a de thread M:N (`libpthread`), e você pode alternar em tempo de execução para a thread 1:1 (`libthr`). O plano é mudar em breve para a biblioteca 1:1 por padrão. Embora essas duas bibliotecas usem as mesmas primitivas do kernel, elas são acessadas por meio de APIs diferentes. A biblioteca M:N usa a família de syscalls `kse_*`, enquanto a biblioteca 1:1 usa a família de syscalls `thr_*`. Devido a isso, não há um conceito geral de ID de thread compartilhado entre o espaço do kernel e o espaço do usuário. Claro, ambas as bibliotecas de threads implementam a API de ID de thread pthread. Cada thread do kernel (conforme descrito por `struct thread`) tem um identificador `td tid`, mas isso não é acessível diretamente do espaço do usuário e serve exclusivamente às necessidades do kernel. Também é usado para a biblioteca de thread 1:1 como ID de thread pthread, mas o tratamento disso é interno à biblioteca e não se pode confiar. Como mencionado anteriormente, existem duas implementações de threading no FreeBSD. A biblioteca M:N divide o trabalho entre o espaço do kernel e o espaço do usuário. Uma thread é uma entidade agendada no kernel, mas pode representar vários threads no espaço do usuário. M threads no espaço do usuário são mapeadas para N threads no kernel, economizando recursos e aproveitando o paralelismo de multiprocessadores. Mais informações sobre a implementação podem ser obtidas na página do manual ou [1]. A biblioteca 1:1 mapeia diretamente um thread do espaço do usuário para um thread do kernel, simplificando bastante o esquema. Nenhum desses designs implementa um mecanismo de justiça (um mecanismo desse tipo foi implementado, mas foi removido recentemente porque causava uma desaceleração significativa e tornava o código mais difícil de lidar). [[what-is-linux]] === O que é o Linux(R) O Linux(R) é um kernel semelhante ao UNIX(R) originalmente desenvolvido por Linus Torvalds e que agora recebe contribuições de uma grande comunidade de programadores ao redor do mundo. Desde os seus humildes começos até os dias de hoje, com amplo suporte de empresas como IBM e Google, o Linux(R) é associado à sua rápida velocidade de desenvolvimento, suporte completo de hardware e modelo de organização com um ditador benevolente. O desenvolvimento do Linux(R) começou em 1991 como um projeto de hobby na Universidade de Helsinki, na Finlândia. Desde então, ele adquiriu todas as características de um sistema operacional moderno semelhante ao UNIX(R): suporte a multiprocessamento, suporte a vários usuários, memória virtual, rede, basicamente tudo está presente. Existem também recursos altamente avançados, como virtualização, entre outros. A partir de 2006, o Linux(R) parece ser o sistema operacional de código aberto mais amplamente utilizado, com suporte de fornecedores independentes de software como Oracle, RealNetworks, Adobe, etc. A maioria do software comercial distribuído para Linux(R) só está disponível em forma binária, tornando impossível a recompilação para outros sistemas operacionais. A maioria do desenvolvimento do Linux(R) ocorre em um sistema de controle de versão chamado Git. O Git é um sistema distribuído, então não há uma fonte central do código do Linux(R), mas alguns branches são considerados proeminentes e oficiais. O esquema de numeração de versão implementado pelo Linux(R) consiste em quatro números A.B.C.D. Atualmente, o desenvolvimento ocorre na versão 2.6.C.D, onde C representa a versão principal, onde novos recursos são adicionados ou alterados, enquanto D é uma versão menor para correções de bugs apenas. Mais informações podem ser obtidas em [3]. [[linux-tech-details]] ==== Detalhes técnicos Linux(R) segue o esquema tradicional do UNIX(R) de dividir a execução de um processo em duas partes: o espaço do kernel e o espaço do usuário. O kernel pode ser acessado de duas maneiras: por meio de uma interrupção (trap) ou por meio de uma chamada de sistema (syscall). O retorno é tratado apenas de uma maneira. A descrição a seguir se aplica ao Linux(R) 2.6 na arquitetura i386(TM). Essas informações foram obtidas em [2]. [[linux-syscalls]] ===== Syscalls As chamadas de sistema no Linux(R) são realizadas (no espaço do usuário) usando macros `syscallX`, em que X substitui um número representando a quantidade de parâmetros da chamada de sistema específica. Essa macro é traduzida para um código que carrega o registro `%eax` com o número da chamada de sistema e executa a interrupção `0x80`. Após o retorno da chamada de sistema, é feita a chamada para tratar o retorno, que converte valores de retorno negativos em valores `errno` positivos e define `res` como `-1` em caso de erro. Sempre que a interrupção `0x80` é chamada, o processo entra no kernel no tratador de interrupção de chamada de sistema. Essa rotina salva todos os registros na pilha e chama a entrada da chamada de sistema selecionada. Observa-se que a convenção de chamada do Linux(R) espera que os parâmetros da chamada de sistema sejam passados via registros, como mostrado aqui: . parameter -> `%ebx` . parameter -> `%ecx` . parameter -> `%edx` . parameter -> `%esi` . parameter -> `%edi` . parameter -> `%ebp` Existem algumas exceções a isso, onde o Linux(R) usa convenções de chamada diferentes (a mais notável é a chamada de sistema `clone`). [[linux-traps]] ===== Armadilhas (Traps) Os tratadores de exceção são introduzidos em [.filename]#arch/i386/kernel/traps.c# e a maioria desses tratadores ficam localizados em [.filename]#arch/i386/kernel/entry.S#, onde o tratamento das exceções ocorre. [[linux-exits]] ===== Saídas O retorno da chamada de sistema é gerenciado pela função `exit` do sistema, que verifica se o processo possui trabalho inacabado e, em seguida, verifica se foram utilizados seletores fornecidos pelo usuário. Se isso ocorrer, é aplicada uma correção de pilha e, finalmente, os registros são restaurados da pilha e o processo retorna ao espaço do usuário. [[linux-unix-primitives]] ===== Primitivas do UNIX(R) Na versão 2.6, o sistema operacional Linux(R) redefiniu algumas das primitivas tradicionais do UNIX(R), principalmente PID, TID e thread. O PID não é mais definido como único para cada processo, portanto, para alguns processos (threads), a função man:getppid[2] retorna o mesmo valor. A identificação única de um processo é fornecida pelo TID. Isso ocorre porque o _NPTL_ (New POSIX(R) Thread Library) define threads como processos normais (chamados de 1:1 threading). A criação de um novo processo no Linux(R) 2.6 ocorre usando a chamada de sistema `clone` (as variantes de fork são reimplementadas usando essa chamada). Essa chamada clone define um conjunto de flags que afetam o comportamento do processo clonado em relação à implementação de threads. A semântica é um pouco complexa, pois não há uma única flag que indique à chamada de sistema para criar uma thread. Flags de clone implementados são: * `CLONE_VM` - os processos compartilham seu espaço de memória * `CLONE_FS` - compartilha umask, cwd e namespace * `CLONE_FILES` - compartilha arquivos abertos * `CLONE_SIGHAND` - compartilha manipuladores de sinal e sinais bloqueados * `CLONE_PARENT` - compartilha o processo pai * `CLONE_THREAD` - ser uma thread (mais explicações abaixo) * `CLONE_NEWNS` - novo namespace * `CLONE_SYSVSEM` - compartilha estruturas de reversão SysV * `CLONE_SETTLS` - configura o TLS no endereço fornecido * `CLONE_PARENT_SETTID` - define o TID (Thread ID) no processo pai * `CLONE_CHILD_CLEARTID` - limpa o TID (Thread ID) no processo filho * `CLONE_CHILD_SETTID` - define o TID (Thread ID) no processo filho A `CLONE_PARENT` define o pai real como o pai do chamador. Isso é útil para threads, porque se a thread A cria a thread B, queremos que a thread B tenha o mesmo pai do grupo de threads inteiro. A `CLONE_THREAD` faz exatamente a mesma coisa que `CLONE_PARENT`, `CLONE_VM` e `CLONE_SIGHAND`, reescreve o PID para ser o mesmo do chamador, define o sinal de saída como nenhum (none) e entra no grupo de threads. A `CLONE_SETTLS` configura as entradas do GDT (Global Descriptor Table) para manipulação de TLS (Thread Local Storage). O conjunto de flags `CLONE_*_*TID` define ou limpa o endereço fornecido pelo usuário para o TID ou 0. Como você pode ver, o `CLONE_THREAD` faz a maior parte do trabalho e parece não se encaixar muito bem no esquema. A intenção original é incerta (até mesmo para os autores, de acordo com comentários no código), mas acredito que originalmente existia uma única flag de threading, que foi posteriormente dividida entre muitas outras flags, mas essa separação nunca foi totalmente concluída. Também não está claro para que serve essa partição, já que a glibc não a utiliza, então apenas o uso manual do clone permite que um programador acesse esses recursos. Para programas não-threaded, o PID e TID são os mesmos. Para programas threaded, o PID e TID da primeira thread são os mesmos, e cada thread criada compartilha o mesmo PID e recebe um TID único (porque `CLONE_THREAD` é passado), também o pai é compartilhado por todos os processos que formam esse programa threaded. O código que implementa o man:pthread_create[3] em NPTL define as flags de clone da seguinte forma: [.programlisting] .... 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); .... A `CLONE_SIGNAL` é definida como [.programlisting] .... #define CLONE_SIGNAL (CLONE_SIGHAND | CLONE_THREAD) .... o último 0 significa que nenhum sinal é enviado quando qualquer uma das threads finaliza. [[what-is-emu]] === O que é emulação De acordo com a definição de dicionário, emulação é a capacidade de um programa ou dispositivo imitar outro programa ou dispositivo. Isso é alcançado ao fornecer a mesma reação a um estímulo dado como o objeto emulado. Na prática, o mundo do software geralmente vê três tipos de emulação: um programa usado para emular uma máquina (QEMU, vários emuladores de consoles de jogos, etc.), emulação de software de uma funcionalidade de hardware (emuladores de OpenGL, emulação de unidades de ponto flutuante, etc.) e emulação de sistemas operacionais (seja no núcleo do sistema operacional ou como um programa no espaço do usuário). A emulação é geralmente utilizada em situações em que não é viável ou possível utilizar o componente original. Por exemplo, alguém pode querer usar um programa desenvolvido para um sistema operacional diferente do que estão usando. Nesse caso, a emulação é útil. Às vezes, não há outra opção além da emulação - por exemplo, quando o dispositivo de hardware que você está tentando usar não existe (ainda/não mais), não há outra opção além da emulação. Isso ocorre com frequência ao portar um sistema operacional para uma plataforma nova (e inexistente). Às vezes, é apenas mais econômico utilizar a emulação. Olhando a partir de um ponto de vista de implementação, existem duas abordagens principais para a implementação da emulação. Você pode emular o objeto inteiro - aceitando possíveis entradas do objeto original, mantendo o estado interno e emitindo a saída correta com base no estado e/ou na entrada. Esse tipo de emulação não requer condições especiais e basicamente pode ser implementado em qualquer lugar para qualquer dispositivo/programa. A desvantagem é que a implementação de tal emulação é bastante difícil, demorada e propensa a erros. Em alguns casos, podemos usar uma abordagem mais simples. Imagine que você queira emular uma impressora que imprime da esquerda para a direita em uma impressora que imprime da direita para a esquerda. É óbvio que não há necessidade de uma camada de emulação complexa, apenas reverter o texto impresso é suficiente. Às vezes, o ambiente de emulação é muito semelhante ao ambiente emulado, então apenas uma fina camada de tradução é necessária para fornecer uma emulação totalmente funcional! Como você pode ver, isso é muito menos exigente de ser implementado, portanto, menos demorado e propenso a erros em comparação com a abordagem anterior. Mas a condição necessária é que os dois ambientes sejam suficientemente semelhantes. A terceira abordagem combina as duas anteriores. Na maioria das vezes, os objetos não fornecem as mesmas capacidades, então, ao emular um objeto mais poderoso em um objeto menos poderoso, temos que emular os recursos ausentes com emulação completa descrita anteriormente. Esta tese de mestrado trata da emulação do UNIX(R) em UNIX(R), que é exatamente o caso em que apenas uma camada fina de tradução é suficiente para fornecer uma emulação completa. A API do UNIX(R) consiste em um conjunto de syscalls, que geralmente são autônomas e não afetam algum estado global do kernel. Existem algumas syscalls que afetam o estado interno, mas isso pode ser resolvido fornecendo algumas estruturas que mantêm o estado extra. Nenhuma emulação é perfeita e emulações tendem a ter algumas partes ausentes, mas isso geralmente não causa grandes inconvenientes. Imagine um emulador de console de jogos que emula tudo, exceto a saída de música. Sem dúvida, os jogos são jogáveis e é possível usar o emulador. Pode não ser tão confortável quanto o console de jogos original, mas é um compromisso aceitável entre preço e conforto. O mesmo acontece com a API do UNIX(R). A maioria dos programas pode funcionar com um conjunto muito limitado de syscalls. Essas syscalls tendem a ser as mais antigas (man:read[2]/man:write[2], família man:fork[2], manipulação de man:signal[3], man:exit[3], API man:socket[2]), o que torna mais fácil a emulação, pois sua semântica é compartilhada entre todos os sistemas UNIX(R) existentes hoje em dia. [[freebsd-emulation]] == Emulação === Como funciona a emulação no FreeBSD Como mencionado anteriormente, o FreeBSD suporta a execução de binários de vários outros sistemas UNIX(R). Isso é possível porque o FreeBSD possui uma abstração chamada de "execução do carregador de classe" (execution class loader). Isso é inserido na chamada de sistema man:execve[2], então quando o man:execve[2] está prestes a executar um binário, ele examina o tipo do binário. Existem basicamente dois tipos de binários no FreeBSD. Scripts de texto semelhantes a shell, que são identificados pelos primeiros dois caracteres `#!`, e binários normais (geralmente ELF), que são uma representação de um objeto executável compilado. A grande maioria (pode-se dizer que todos) os binários no FreeBSD são do tipo ELF. Os arquivos ELF contêm um cabeçalho que especifica a ABI do sistema operacional para este arquivo ELF. Lendo essa informação, o sistema operacional pode determinar com precisão qual é o tipo de arquivo binário. Cada ABI de sistema operacional deve ser registrada no kernel do FreeBSD. Isso também se aplica à ABI nativa do FreeBSD. Portanto, quando o man:execve[2] executa um binário, ele itera pela lista de APIs registradas e, quando encontra a correspondente, começa a usar as informações contidas na descrição da ABI do sistema operacional (sua tabela de syscalls, tabela de tradução de `errno`, etc.). Portanto, cada vez que o processo chama uma syscall, ele usa seu próprio conjunto de syscalls em vez de um conjunto global. Isso fornece uma maneira muito elegante e fácil de oferecer suporte à execução de vários formatos binários. A natureza da emulação de diferentes sistemas operacionais (e também de outros subsistemas) levou os desenvolvedores a adotarem um mecanismo de tratamento de eventos. Existem vários pontos no kernel em que uma lista de manipuladores de eventos é chamada. Cada subsistema pode registrar um manipulador de evento e eles são chamados de acordo. Por exemplo, quando um processo é encerrado, é chamado um manipulador que possivelmente realiza a limpeza necessária no subsistema. Essas facilidades simples fornecem basicamente tudo o que é necessário para a infraestrutura de emulação e, na verdade, são basicamente as únicas coisas necessárias para implementar a camada de emulação do Linux(R). [[freebsd-common-primitives]] === Primitivas comuns no kernel do FreeBSD As camadas de emulação precisam de suporte por parte do sistema operacional. Vou descrever alguns dos primitivos suportados no sistema operacional FreeBSD. [[freebsd-locking-primitives]] ==== Primitivas de Bloqueio Contribuído por: `{attilio}` O conjunto de primitivas de sincronização do FreeBSD é baseado na idéia de fornecer um grande número de diferentes primitivas de uma maneira que a melhor possa ser usada para cada situação específica e apropriada. Para um ponto de vista de alto nível, você pode considerar três tipos de primitivas de sincronização no kernel do FreeBSD: * operações atômicas e barreiras de memória * locks * barreiras de agendamento Abaixo estão as descrições das 3 famílias. Para cada trava, é recomendado verificar a página do manual vinculada (quando possível) para obter explicações mais detalhadas. [[freebsd-atomic-op]] ===== Operações atômicas e barreiras de memória As operações atômicas são implementadas por meio de um conjunto de funções que realizam operações aritméticas simples em operandos de memória de maneira atômica em relação a eventos externos (interrupções, preempção, etc.). As operações atômicas podem garantir atomicidade apenas em tipos de dados pequenos (da ordem de magnitude do tipo de dados C `.long.` da arquitetura), portanto, devem ser raramente usadas diretamente no código de nível final, a menos que seja apenas para operações muito simples (como definir uma bandeira em um bitmap, por exemplo). Na verdade, é bastante simples e comum escrever uma semântica errada baseada apenas em operações atômicas (geralmente referidas como "sem bloqueio"). O kernel do FreeBSD oferece uma maneira de realizar operações atômicas em conjunto com uma barreira de memória. As barreiras de memória garantem que uma operação atômica ocorra seguindo alguma ordem especificada em relação a outros acessos à memória. Por exemplo, se precisamos que uma operação atômica ocorra logo após todas as gravações pendentes (em termos de reordenação de instruções nos buffers) sejam concluídas, precisamos usar explicitamente uma barreira de memória em conjunto com essa operação atômica. Portanto, é fácil entender por que as barreiras de memória desempenham um papel fundamental na construção de travas de nível superior (como refcount, mutexes, etc.). Para uma explicação detalhada sobre as operações atômicas, consulte o man:atomic[9]. No entanto, é importante notar que as operações atômicas (assim como as barreiras de memória) idealmente devem ser usadas apenas para a construção de travas de nível superior (como mutexes). [[freebsd-refcounts]] ===== Refcounts Refcounts são interfaces para lidar com contadores de referência. Eles são implementados por meio de operações atômicas e destinam-se a serem usados apenas em casos em que o contador de referência é a única coisa a ser protegida, então até mesmo algo como um spin-mutex é considerado obsoleto. O uso da interface refcount para estruturas em que já é usado um mutex geralmente está incorreto, pois provavelmente devemos fechar o contador de referência em algum caminho já protegido. Atualmente, não existe uma página de manual que discuta refcount, apenas verifique [.filename]#sys/refcount.h# para obter uma visão geral da API existente. [[freebsd-locks]] ===== Locks O kernel do FreeBSD possui várias classes de locks. Cada lock é definido por algumas propriedades específicas, mas provavelmente a mais importante é o evento vinculado aos detentores em disputa (ou em outras palavras, o comportamento das threads incapazes de adquirir o lock). O esquema de locking do FreeBSD apresenta três comportamentos diferentes para os contendores: . spinning . blocking . sleeping [NOTE] ==== números não são casuais ==== [[freebsd-spinlocks]] ===== Spinning locks Spin locks permitem que os aguardantes fiquem girando em um loop até que não possam adquirir o lock. Uma questão importante a lidar é quando uma thread disputa um spin lock se ela não for despachada. Como o kernel do FreeBSD é preemptivo, isso expõe o spin lock ao risco de deadlocks que podem ser resolvidos desabilitando as interrupções enquanto eles são adquiridos. Por esse e outros motivos (como a falta de suporte à propagação de prioridade, deficiência em esquemas de balanceamento de carga entre CPUs, etc.), os spin locks são destinados a proteger trechos muito pequenos de código, ou idealmente não devem ser usados se não forem explicitamente solicitados (explicado posteriormente). [[freebsd-blocking]] ===== Bloqueio Block locks let waiters to be descheduled and blocked until the lock owner does not drop it and wakes up one or more contenders. To avoid starvation issues, blocking locks do priority propagation from the waiters to the owner. Block locks must be implemented through the turnstile interface and are intended to be the most used kind of locks in the kernel, if no particular conditions are met. [[freebsd-sleeping]] ===== Sleeping As travas de suspensão (sleep locks) permitem que os processos em espera sejam despachados (descheduled ) e adormeçam até que o detentor da trava a solte e acorde um ou mais processos em espera. Como as travas de suspensão são projetadas para proteger grandes trechos de código e lidar com eventos assíncronos, elas não realizam qualquer forma de propagação de prioridade. Elas devem ser implementadas por meio da interface man:sleepqueue[9]. A ordem usada para adquirir locks é muito importante, não apenas devido à possibilidade de deadlock devido a inversões na ordem dos locks, mas também porque a aquisição de locks deve seguir regras específicas relacionadas às naturezas dos locks. Se você observar a tabela acima, a regra prática é que se um thread possui um lock de nível n (onde o nível é o número listado próximo ao tipo de lock), ele não pode adquirir um lock de níveis superiores, pois isso quebraria a semântica especificada para um determinado caminho. Por exemplo, se um thread possui um bloqueio de bloqueio (nível 2), é permitido adquirir um lock de rotação (nível 1), mas não um lock de suspensão (nível 3), pois os bloqueios de bloqueio são destinados a proteger caminhos menores do que os bloqueios de suspensão (essas regras não se aplicam a operações atômicas ou barreiras de agendamento, no entanto). Esta é uma lista de bloqueio com seus respectivos comportamentos: * spin mutex - girando - man:mutex[9] * Sleep mutex - bloqueio - man:mutex[9] * pool mutex - blocking - man:mtx[pool] * A família de funções de suspensão (sleep family) - sleeping - man:sleep[9] pause tsleep msleep msleep spin msleep rw msleep sx * condvar - sleeping - man:condvar[9] * rwlock - blocking - man:rwlock[9] * sxlock - sleeping - man:sx[9] * lockmgr - sleeping - man:lockmgr[9] * semáforos - sleeping - man:sema[9] Entre esses bloqueios, apenas mutexes, sxlocks, rwlocks e lockmgrs são destinados a tratar recursão, mas atualmente a recursão é suportada apenas por mutexes e lockmgrs. [[freebsd-scheduling]] ===== Barreiras de agendamento Scheduling barriers are intended to be used to drive scheduling of threading. They consist mainly of three different stubs: * seções críticas (e preempção) * sched_bind * sched_pin Em geral, esses devem ser usados apenas em um contexto específico e, mesmo que possam substituir bloqueios em muitos casos, eles devem ser evitados porque não permitem diagnosticar problemas simples com ferramentas de depuração de bloqueio (como man:witness[4]). [[freebsd-critical]] ===== Seções críticas The FreeBSD kernel has been made preemptive basically to deal with interrupt threads. In fact, to avoid high interrupt latency, time-sharing priority threads can be preempted by interrupt threads (in this way, they do not need to wait to be scheduled as the normal path previews). Preemption, however, introduces new racing points that need to be handled, as well. Often, to deal with preemption, the simplest thing to do is to completely disable it. A critical section defines a piece of code (borderlined by the pair of functions man:critical_enter[9] and man:critical_exit[9], where preemption is guaranteed to not happen (until the protected code is fully executed). This can often replace a lock effectively but should be used carefully to not lose the whole advantage that preemption brings. [[freebsd-schedpin]] ===== sched_pin/sched_unpin Outra forma de lidar com a preempção é a interface `sched_pin()`. Se um trecho de código é envolvido pelas funções `sched_pin()` e `sched_unpin()`, é garantido que a respectiva thread, mesmo que possa ser preemptada, será sempre executada na mesma CPU. Fixar (pinning) é muito efetivo no caso particular em que precisamos acessar dados específicos de cada CPU e assumimos que outras threads não alterarão esses dados. A última condição determinará uma seção crítica como uma condição muito rigorosa para nosso código. [[freebsd-schedbind]] ===== sched_bind/sched_unbind `sched_bind` is an API used to bind a thread to a particular CPU for all the time it executes the code, until a `sched_unbind` function call does not unbind it. This feature has a key role in situations where you cannot trust the current state of CPUs (for example, at very early stages of boot), as you want to avoid your thread to migrate on inactive CPUs. Since `sched_bind` and `sched_unbind` manipulate internal scheduler structures, they need to be enclosed in `sched_lock` acquisition/releasing when used. [[freebsd-proc]] ==== Estrutura Proc Em algumas camadas de emulação, às vezes é necessário ter dados adicionais específicos para cada processo. Pode-se gerenciar estruturas separadas (como uma lista, uma árvore etc.) que contenham esses dados para cada processo, mas isso pode ser lento e consumir muita memória. Para resolver esse problema, a estrutura `proc` do FreeBSD contém o campo `p_emuldata`, que é um ponteiro vazio para dados específicos da camada de emulação. Essa entrada `proc` é protegida pelo mutex do processo. A estrutura `proc` do FreeBSD contém uma entrada `p_sysent` que identifica qual ABI esse processo está executando. Na verdade, é um ponteiro para a estrutura `sysentvec` descrita anteriormente. Portanto, ao comparar esse ponteiro com o endereço onde a estrutura `sysentvec` para a ABI específica está armazenada, podemos determinar efetivamente se o processo pertence à nossa camada de emulação. O código geralmente se parece com: [.programlisting] .... if (__predict_true(p->p_sysent != &elf_Linux(R)_sysvec)) return; .... Como você pode ver, usamos efetivamente o modificador `__predict_true` para colapsar o caso mais comum (processo FreeBSD) em uma simples operação de retorno, preservando assim o alto desempenho. Esse código deve ser transformado em uma macro porque atualmente não é muito flexível, ou seja, não suportamos emulação Linux(R)64 nem processos Linux(R) A.OUT em i386. [[freebsd-vfs]] ==== VFS O subsistema VFS do FreeBSD é muito complexo, mas a camada de emulação do Linux(R) utiliza apenas um pequeno subconjunto por meio de uma API bem definida. Ela pode operar em vnodes ou manipuladores de arquivo. Vnode representa um vnode virtual, ou seja, uma representação de um nó no VFS. Outra representação é um manipulador de arquivo, que representa um arquivo aberto do ponto de vista de um processo. Um manipulador de arquivo pode representar um socket ou um arquivo comum. Um manipulador de arquivo contém um ponteiro para seu vnode. Mais de um manipulador de arquivo pode apontar para o mesmo vnode. [[freebsd-namei]] ===== namei A rotina man:namei[9] é um ponto de entrada central para a pesquisa e tradução de caminhos de nomes. Ela percorre o caminho ponto a ponto, do ponto de partida ao ponto final, usando a função de pesquisa, que é interna ao VFS. A chamada man:namei[9] pode lidar com links simbólicos, caminhos absolutos e relativos. Quando um caminho é pesquisado usando man:namei[9], ele é inserido no cache de nomes. Esse comportamento pode ser suprimido. Essa rotina é usada em todo o kernel e seu desempenho é muito crítico. [[freebsd-vn]] ===== vn_fullpath A função man:vn_fullpath[9] faz o melhor esforço para percorrer o cache de nomes do VFS e retorna um caminho para um vnode específico (bloqueado). Esse processo é não confiável, mas funciona muito bem na maioria dos casos comuns. A falta de confiabilidade ocorre porque ela depende do cache do VFS (não percorre as estruturas no meio físico) e não funciona com links rígidos, entre outras limitações. Essa rotina é usada em vários lugares no Linuxulator. [[freebsd-vnode]] ===== Operações de vnode * `fgetvp` - dado um thread e um número de descritor de arquivo, ele retorna o vnode associado * man:vn_lock[9] - bloqueia um vnode * `vn_unlock` - desbloqueia um vnode * man:VOP_READDIR[9] - lê um diretório referenciado por um vnode * man:VOP_GETATTR[9] - obtém atributos de um arquivo ou diretório referenciado por um vnode * man:VOP_LOOKUP[9] - busca um caminho para um diretório específico * man:VOP_OPEN[9] - abre um arquivo referenciado por um vnode * man:VOP_CLOSE[9] - fecha um arquivo referenciado por um vnode * man:vput[9] - decrementa a contagem de uso de um vnode e desbloqueia * man:vrele[9] - diminui o contador de uso para um vnode * man:vref[9] - incrementa a contagem de uso de um vnode [[freebsd-file-handler]] ===== Operações do manipulador de arquivos * `fget` - dado um thread e um número de descritor de arquivo, ele retorna o file handler associado e o referencia * `fdrop` - remove uma referência a um file handler * `fhold` - referencia um file handler [[md]] == A camada de emulação do Linux(R) - parte MD Esta seção trata da implementação da camada de emulação do Linux(R) no sistema operacional FreeBSD. Ela descreve primeiramente a parte dependente da máquina, abordando como e onde a interação entre o espaço do usuário e o kernel é implementada. Ela fala sobre syscalls, sinais, ptrace, traps e ajuste de pilha. Essa parte discute o i386, mas é escrita de forma geral, então outras arquiteturas não devem diferir muito. A próxima parte é a parte independente da máquina do Linuxulator. Esta seção aborda apenas o i386 e o tratamento de arquivos ELF. O formato A.OUT está obsoleto e não foi testado. [[syscall-handling]] === Manipulação de Syscall O tratamento de syscalls é principalmente escrito em [.filename]#linux_sysvec.c#, que abrange a maioria das rotinas apontadas na estrutura `sysentvec`. Quando um processo do Linux(R) em execução no FreeBSD faz uma syscall, a rotina geral de syscall chama a rotina linux prepsyscall para a ABI do Linux(R). [[linux-prepsyscall]] ==== Linux(R) prepsyscall No Linux(R), os argumentos das syscalls são passados via registradores (por isso é limitado a 6 parâmetros no i386), enquanto no FreeBSD eles são passados pela pilha. A rotina linux prepsyscall deve copiar os parâmetros dos registradores para a pilha. A ordem dos registradores é: `%ebx`, `%ecx`, `%edx`, `%esi`, `%edi`, `%ebp`. A questão é que isso é verdade apenas para _a maioria_ das syscalls. Algumas (mais notavelmente `clone`) usam uma ordem diferente, mas felizmente é fácil corrigir isso inserindo um parâmetro fictício no protótipo `linux_clone`. [[syscall-writing]] ==== Escrevendo syscall Cada chamada de sistema implementada no Linuxulator deve ter seu protótipo com várias flags no arquivo `syscalls.master`. A estrutura do arquivo é a seguinte: [.programlisting] .... ... AUE_FORK STD { int linux_fork(void); } ... AUE_CLOSE NOPROTO { int close(int fd); } ... .... A primeira coluna representa o número da syscall. A segunda coluna é para suporte de auditoria. A terceira coluna representa o tipo de syscall. Pode ser `STD`, `OBSOL`, `NOPROTO` ou `UNIMPL`. `STD` é uma syscall padrão com protótipo e implementação completos. `OBSOL` é obsoleta e define apenas o protótipo. `NOPROTO` significa que a syscall é implementada em outro lugar, então não é necessário adicionar o prefixo ABI, etc. `UNIMPL` significa que a syscall será substituída pela syscall `nosys` (uma syscall que apenas imprime uma mensagem informando que a syscall não está implementada e retorna `ENOSYS`). Do [.filename]#syscalls.master#, um script gera três arquivos: [.filename]#linux_syscall.h#, [.filename]#linux_proto.h# e [.filename]#linux_sysent.c#. O arquivo [.filename]#linux_syscall.h# contém as definições dos nomes das syscalls e seus valores numéricos, por exemplo: [.programlisting] .... ... #define LINUX_SYS_linux_fork 2 ... #define LINUX_SYS_close 6 ... .... O [.filename]#linux_proto.h# contém definições de estrutura de argumentos para cada syscall, por exemplo: [.programlisting] .... struct linux_fork_args { register_t dummy; }; .... E finalmente, o [.filename]#linux_sysent.c# contém uma estrutura descrevendo a tabela de entrada do sistema, usada para realmente enviar um syscall, por exemplo: [.programlisting] .... { 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 */ .... Como você pode ver, `linux_fork` é implementado no próprio Linuxulator, então a definição é do tipo `STD` e não tem argumentos, o que é exibido pela estrutura de argumentos fictícia. Por outro lado, `close` é apenas um alias para o verdadeiro man:close[2] do FreeBSD, então não possui uma estrutura de argumentos específica do Linux associada e na tabela de entrada do sistema não é prefixado com linux, pois chama o verdadeiro man:close[2] no kernel. [[dummy-syscalls]] ==== Dummy syscalls The Linux(R) 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 [.filename]#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 to know what syscalls are more important to implement. [[signal-handling]] === Manuseio de signals O tratamento de sinais é feito geralmente no kernel do FreeBSD para todas as compatibilidades binárias com uma chamada a uma camada dependente de compatibilidade. A camada de compatibilidade do Linux(R) define a rotina `linux_sendsig` para este propósito. [[linux-sendsig]] ==== Linux(R) sendsig Essa rotina primeiro verifica se o sinal foi instalado com `SA_SIGINFO`, caso contrário, ela chama a rotina `linux_rt_sendsig`. Além disso, aloca (ou reutiliza um já existente) o contexto do manipulador de sinal, em seguida, constrói uma lista de argumentos para o manipulador de sinal. Traduz o número do sinal com base na tabela de tradução de sinais, atribui um manipulador e traduz o conjunto de sinais. Em seguida, salva o contexto para a rotina `sigreturn` (diversos registradores, número de interrupção traduzido e máscara de sinais). Por fim, copia o contexto do sinal para o espaço do usuário e prepara o contexto para a execução real do manipulador de sinal. [[linux-rt-sendsig]] ==== linux_rt_sendsig Esta rotina é semelhante à `linux_sendsig`, mas a preparação do contexto do sinal é diferente. Ela adiciona `siginfo`, `ucontext` e algumas partes POSIX(R). Pode valer a pena considerar se essas duas funções não poderiam ser mescladas com o benefício de menos duplicação de código e possivelmente até execução mais rápida. [[linux-sigreturn]] ==== linux_sigreturn Essa chamada de sistema é usada para retornar do manipulador de sinal. Ela realiza algumas verificações de segurança e restaura o contexto original do processo. Além disso, desativa o sinal na máscara de sinais do processo. [[ptrace]] === Ptrace Many UNIX(R) derivates implement the man:ptrace[2] syscall to allow various tracking and debugging features. This facility enables the tracing process to obtain various information about the traced process, like register dumps, any memory from the process address space, etc. and also to trace the process like in stepping an instruction or between system entries (syscalls and traps). man:ptrace[2] also lets you set various information in the traced process (registers etc.). man:ptrace[2] is a UNIX(R)-wide standard implemented in most UNIX(R)es around the world. A emulação do Linux(R) no FreeBSD implementa a facilidade man:ptrace[2] em [.filename]#linux_ptrace.c#. As rotinas de conversão de registradores entre Linux(R) e FreeBSD e a própria syscall de emulação man:ptrace[2]. A syscall é um longo bloco switch que implementa seu equivalente no FreeBSD para cada comando man:ptrace[2]. Os comandos man:ptrace[2] são principalmente iguais entre Linux(R) e FreeBSD, então geralmente apenas uma pequena modificação é necessária. Por exemplo, `PT_GETREGS` no Linux(R) opera em dados diretos, enquanto o FreeBSD usa um ponteiro para os dados, então após a execução de uma syscall man:ptrace[2] (nativa), é necessário fazer uma cópia dos dados usando copyout para preservar a semântica do Linux(R). A implementação man:ptrace[2] no Linuxulator tem algumas fraquezas conhecidas. Houve panes vistas ao usar `strace` (que é um consumidor man:ptrace[2]) no ambiente Linuxulator. Além disso, `PT_SYSCALL` não está implementado. [[traps]] === Armadilhas (Traps) Sempre que um processo Linux(R) executando na camada de emulação sofre uma interrupção, a própria interrupção é tratada de forma transparente com a única exceção da tradução da interrupção. O Linux(R) e o FreeBSD diferem em suas opiniões sobre o que é uma interrupção, então isso é tratado aqui. O código é realmente muito curto: [.programlisting] .... static int translate_traps(int signal, int trap_code) { if (signal != SIGBUS) return signal; switch (trap_code) { case T_PROTFLT: case T_TSSFLT: case T_DOUBLEFLT: case T_PAGEFLT: return SIGSEGV; default: return signal; } } .... [[stack-fixup]] === Correção de pilha O link-editor em tempo de execução RTLD espera que as chamadas AUX estejam presentes na pilha durante um `execve`, então é necessário fazer um ajuste para garantir isso. Naturalmente, cada sistema RTLD é diferente, então a camada de emulação deve fornecer sua própria rotina de ajuste da pilha para realizar isso. Isso também se aplica ao Linuxulator. A função `elf_linux_fixup` simplesmente copia as chamadas AUX para a pilha e ajusta o ponteiro da pilha do processo de espaço de usuário para apontar imediatamente após essas chamadas. Dessa forma, o RTLD funciona de maneira inteligente. [[aout-support]] === Suporte para A.OUT A camada de emulação do Linux(R) no i386 também suporta binários A.OUT do Linux(R). Praticamente tudo o que foi descrito nas seções anteriores deve ser implementado para oferecer suporte ao formato A.OUT (exceto a tradução de traps e o envio de sinais). O suporte para binários A.OUT não é mais mantido, especialmente a emulação 2.6 não funciona com esse formato. No entanto, isso não causa nenhum problema, já que o linux-base nos ports provavelmente não suporta binários A.OUT. Esse suporte provavelmente será removido no futuro. A maior parte do necessário para carregar binários A.OUT do Linux(R) está no arquivo [.filename]#imgact_linux.c#. [[mi]] == Camada de emulação do Linux(R) - Parte MI Esta seção aborda a parte independente de máquina do Linuxulator. Ela cobre a infraestrutura de emulação necessária para a emulação do Linux(R) 2.6, a implementação do armazenamento local de threads (TLS) (em i386) e futexes. Em seguida, falamos brevemente sobre algumas syscalls. [[nptl-desc]] === Descrição do NPTL Um dos principais avanços no desenvolvimento do Linux(R) 2.6 foi a implementação de threads. Antes do 2.6, o suporte a threading no Linux(R) era implementado na biblioteca linuxthreads. Essa biblioteca era uma implementação parcial da threading POSIX(R). A threading era implementada usando processos separados para cada thread, usando a syscall `clone` para permitir que compartilhassem o espaço de endereçamento (e outras coisas). As principais fraquezas dessa abordagem eram que cada thread tinha um PID diferente, o tratamento de sinais era problemático (do ponto de vista do pthreads), etc. Além disso, o desempenho não era muito bom (uso de sinais `SIGUSR` para sincronização de threads, consumo de recursos do kernel, etc.), então, para superar esses problemas, um novo sistema de threading foi desenvolvido e chamado de NPTL. A biblioteca NPTL concentrou-se em duas coisas, mas uma terceira acabou sendo incluída e é geralmente considerada parte do NPTL. Essas duas coisas eram a incorporação de threads em uma estrutura de processo e futexes. A terceira coisa adicional foi TLS (Thread-Local Storage), que não é diretamente exigida pelo NPTL, mas toda a biblioteca NPTL do espaço do usuário depende dela. Essas melhorias resultaram em um desempenho muito melhorado e conformidade com padrões. O NPTL é uma biblioteca padrão de threading em sistemas Linux(R) nos dias de hoje. A implementação do Linuxulator no FreeBSD aborda o NPTL em três áreas principais. O TLS (Thread-Local Storage), os futexes e a manipulação de PID, que tem como objetivo simular as threads do Linux(R). Seções adicionais descrevem cada uma dessas áreas em detalhes. [[linux26-emu]] === Infraestrutura de emulação do Linux(R) 2.6 Essas seções lidam com a forma como as threads do Linux(R) são gerenciadas e como simulamos isso no FreeBSD. [[linux26-runtime]] ==== Determinação de tempo de execução de emulação 2.6 A camada de emulação do Linux(R) no FreeBSD suporta a configuração em tempo de execução da versão emulada. Isso é feito por meio do man:sysctl[8], mais especificamente através do parâmetro `compat.linux.osrelease`. Configurar esse man:sysctl[8] afeta o comportamento em tempo de execução da camada de emulação. Ao definir para 2.6.x, ele define o valor de `linux_use_linux26`, enquanto definir para qualquer outro valor mantém esse valor como indefinido. Essa variável (juntamente com as variáveis específicas de cada prisão) determina se a infraestrutura 2.6 (principalmente o processo de manipulação de PID) é usada no código ou não. A configuração da versão é feita em todo o sistema e isso afeta todos os processos do Linux(R). O man:sysctl[8] não deve ser alterado ao executar qualquer binário do Linux(R), pois isso pode causar problemas. [[linux-proc-thread]] ==== Processos e Identificadores de Thread no Linux(R) A semântica de threading no Linux(R) é um pouco confusa e utiliza uma nomenclatura completamente diferente do FreeBSD. Em um processo no Linux(R), há uma estrutura chamada `struct task` que contém dois campos de identificação - PID e TGID. O PID _não_ é um identificador de processo, mas sim um identificador de thread. O TGID identifica um grupo de threads, ou seja, um processo. Para processos com apenas uma thread, o PID é igual ao TGID. No NPTL, uma thread é apenas um processo comum que tem o TGID diferente do PID e tem um líder de grupo diferente de si mesmo (além de compartilhar a memória virtual, é claro). Todo o resto acontece da mesma maneira que em um processo comum. Não há separação de um status compartilhado em uma estrutura externa, como no FreeBSD. Isso cria alguma duplicação de informações e possíveis inconsistências de dados. O kernel do Linux(R) parece usar informações de tarefa -> grupo em alguns lugares e informações de tarefa em outros lugares, e isso realmente não é muito consistente e parece propenso a erros. Cada thread NPTL é criado por meio de uma chamada ao syscall `clone` com um conjunto específico de flags (mais detalhes na próxima subseção). O NPTL implementa uma estrita relação de threading 1:1. No FreeBSD nós emulamos threads NPTL com processos comuns do FreeBSD que compartilham espaço de VM, etc. e a ginástica PID é apenas imitada na estrutura específica de emulação anexada ao processo. A estrutura anexada ao processo se parece com: [.programlisting] .... 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 */ }; .... O PID é usado para identificar o processo FreeBSD que se conecta a esta estrutura. Os campos `child_se_tid` e `child_clear_tid` são usados para copiar o endereço TID quando um processo termina ou é criado. O ponteiro `shared` aponta para uma estrutura compartilhada entre as threads. A variável `pdeath_signal` identifica o sinal de término do pai e o ponteiro `threads` é usado para vincular essa estrutura à lista de threads. A estrutura `linux_emuldata_shared` se parece com: [.programlisting] .... struct linux_emuldata_shared { int refs; pid_t group_pid; LIST_HEAD(, linux_emuldata) threads; /* head of list of linux threads */ }; .... O campo `refs` é um contador de referências usado para determinar quando podemos liberar a estrutura para evitar vazamentos de memória. O campo `group_pid` é usado para identificar o PID ( = TGID) do processo completo ( = grupo de threads). O ponteiro `threads` é a cabeça da lista de threads no processo. A estrutura `linux_emuldata` pode ser obtida do processo usando `em_find`. O protótipo da função é: [.programlisting] .... struct linux_emuldata *em_find(struct proc *, int locked); .... Aqui, `proc` é o processo do qual queremos obter a estrutura emuldata e o parâmetro `locked` determina se queremos realizar o bloqueio ou não. Os valores aceitos são `EMUL_DOLOCK` e `EMUL_DOUNLOCK`. Mais sobre bloqueio será explicado posteriormente. [[pid-mangling]] ==== Maqueando PID Devido à diferença na interpretação do conceito de PID e TID entre o FreeBSD e o Linux(R), precisamos fazer uma tradução para conciliar essas visões. Fazemos isso através da manipulação de PIDs. Isso significa que simulamos o que seria um PID (=TGID) e TID (=PID) entre o kernel e o espaço do usuário. A regra geral é que, no kernel (no Linuxulator), PID = PID e TGID = shared->group_pid, e no espaço do usuário apresentamos `PID = shared->group_pid` e `TID = proc->p_pid`. O membro PID da estrutura `linux_emuldata` é um PID do FreeBSD. A situação acima afeta principalmente as chamadas de sistema getpid, getppid e gettid. Nelas, utilizamos o PID/TGID respectivamente. Na cópia de TIDs em `child_clear_tid` e `child_set_tid`, copiamos o PID do FreeBSD. [[clone-syscall]] ==== syscall Clone A chamada de sistema `clone` é a forma como as threads são criadas no Linux(R). O protótipo da syscall é assim: [.programlisting] .... int linux_clone(l_int flags, void *stack, void *parent_tidptr, int dummy, void * child_tidptr); .... O parâmetro `flags` informa à syscall como exatamente os processos devem ser clonados. Como descrito anteriormente, o Linux(R) pode criar processos que compartilham várias coisas de forma independente, por exemplo, dois processos podem compartilhar descritores de arquivo, mas não a VM, etc. O último byte do parâmetro `flags` é o sinal de saída do novo processo criado. O parâmetro `stack`, se não for `NULL`, indica onde está a pilha da thread, e se for `NULL`, devemos fazer uma cópia em escrita-compartilhada da pilha do processo chamador (ou seja, fazer o que a rotina normal do man:fork[2] faz). O parâmetro `parent_tidptr` é usado como endereço para copiar o PID do processo (ou seja, ID da thread) assim que o processo estiver suficientemente instanciado, mas ainda não estiver em execução. O parâmetro `dummy` está aqui por causa da convenção de chamada muito estranha dessa syscall no i386. Ela usa os registradores diretamente e não permite que o compilador o faça, o que resulta na necessidade de um syscall dummy. O parâmetro `child_tidptr` é usado como endereço para copiar o PID assim que o processo terminar de criar um novo processo e quando o processo terminar. A syscall em si prossegue configurando as flags correspondentes com base nas flags passadas. Por exemplo, `CLONE_VM` mapeia para RFMEM (compartilhamento de VM), etc. O único detalhe aqui é `CLONE_FS` e `CLONE_FILES`, porque o FreeBSD não permite configurar isso separadamente, então simulamos não configurando RFFDG (cópia da tabela de descritores de arquivo e outras informações do sistema de arquivos) se algum desses estiver definido. Isso não causa problemas, porque essas flags são sempre configuradas juntas. Após configurar as flags, o processo é bifurcado usando a rotina interna `fork1`, e instruímos o processo a não ser colocado em uma fila de execução, ou seja, não ser definido como executável. Depois que a bifurcação é concluída, possivelmente reparentamos o processo recém-criado para emular a semântica `CLONE_PARENT`. A próxima parte é a criação dos dados de emulação. As threads no Linux(R) não sinalizam seus pais, então definimos o sinal de saída como 0 para desativar isso. Em seguida, é feita a configuração de `child_set_tid` e `child_clear_tid`, habilitando a funcionalidade posteriormente no código. Nesse ponto, copiamos o PID para o endereço especificado por `parent_tidptr`. A configuração da pilha do processo é feita simplesmente reescrevendo o registro `%esp` do quadro da thread (`%rsp` no amd64). A próxima parte é configurar o TLS para o processo recém-criado. Após isso, as semânticas de man:vfork[2] podem ser emuladas e, finalmente, o processo recém-criado é colocado em uma fila de execução e a cópia de seu PID para o processo pai é feita por meio do valor de retorno do `clone`. O syscall `clone` é capaz e, de fato, é usado para emular as chamadas de sistema clássicas man:fork[2] e man:vfork[2]. O glibc mais recente, no caso do kernel 2.6, usa `clone` para implementar as chamadas de sistema man:fork[2] e man:vfork[2]. [[locking]] ==== Bloqueio O sistema de bloqueio é implementado por subsistema, pois não esperamos muita contenção nesses pontos. Existem dois bloqueios: `emul_lock`, usado para proteger a manipulação de `linux_emuldata`, e `emul_shared_lock`, usado para manipular `linux_emuldata_shared`. O `emul_lock` é uma mutex de bloqueio não adormecível, enquanto o `emul_shared_lock` é um bloqueio `sx_lock` de bloqueio adormecível. Devido ao bloqueio por subsistema, podemos combinar alguns bloqueios e é por isso que a função `em_find` oferece acesso sem bloqueio. [[tls]] === TLS Esta seção trata do TLS também conhecido como armazenamento local de thread. [[trheading-intro]] ==== Introdução ao threading As threads na ciência da computação são entidades dentro de um processo que podem ser agendadas independentemente umas das outras. As threads no processo compartilham dados em todo o processo (descritores de arquivos, etc.), mas também possuem sua própria pilha para seus próprios dados. Às vezes, há necessidade de dados específicos de um thread em todo o processo, como o nome do thread em execução, por exemplo. A API de threads tradicional do UNIX(R), pthreads, oferece uma maneira de fazer isso usando as funções `pthread_key_create`, `pthread_setspecific` e `pthread_getspecific`, onde um thread pode criar uma chave para os dados específicos do thread local e manipular esses dados usando as funções `pthread_setspecific` e `pthread_getspecific`. É fácil perceber que essa não é a maneira mais conveniente de fazer isso. Portanto, vários fabricantes de compiladores C/C++ introduziram uma maneira melhor. Eles definiram uma nova palavra-chave de modificação, `thread`, que especifica que uma variável é específica de um thread. Também foi desenvolvido um novo método de acesso a essas variáveis, pelo menos na arquitetura i386. O método tradicional do pthreads tende a ser implementado no espaço do usuário como uma tabela de pesquisa trivial. O desempenho de tal solução não é muito bom. Portanto, o novo método usa (no i386) registradores de segmento para endereçar um segmento, onde a área TLS é armazenada, de modo que o acesso real a uma variável do thread é apenas a concatenação do registrador de segmento ao endereço, permitindo o acesso direto através do registrador de segmento. Os registradores de segmento geralmente são `%gs` e `%fs`, agindo como seletores de segmento. Cada thread tem sua própria área onde os dados locais do thread são armazenados, e o registrador de segmento precisa ser carregado em cada troca de contexto. Esse método é muito rápido e amplamente usado em todo o mundo UNIX(R) na arquitetura i386. Tanto o FreeBSD quanto o Linux(R) implementam essa abordagem e obtêm resultados muito bons. A única desvantagem é a necessidade de recarregar o segmento em cada troca de contexto, o que pode retardar as trocas de contexto. O FreeBSD tenta evitar essa sobrecarga usando apenas um descritor de segmento para isso, enquanto o Linux(R) usa 3. É interessante observar que quase nada usa mais de 1 descritor (apenas o Wine parece usar 2), então o Linux(R) paga um preço desnecessário pelas trocas de contexto. [[i386-segs]] ==== Segmentos em i386 A arquitetura i386 implementa os chamados segmentos. Um segmento é uma descrição de uma área de memória. Ele contém informações como o endereço base (início) da área de memória, o final (teto), tipo, proteção, etc. A memória descrita por um segmento pode ser acessada usando registradores de seleção de segmento (`%cs`, `%ds`, `%ss`, `%es`, `%fs`, `%gs`). Por exemplo, vamos supor que temos um segmento cujo endereço base é 0x1234 e comprimento e o seguinte código: [.programlisting] .... mov %edx,%gs:0x10 .... Isso irá carregar o conteúdo do registro `%edx` no endereço de memória 0x1244. Alguns registradores de segmento têm um uso especial, por exemplo, `%cs` é usado para o segmento de código e `%ss` é usado para o segmento de pilha, mas `%fs` e `%gs` geralmente não são usados. Os segmentos são armazenados em uma tabela global GDT ou em uma tabela local LDT. A LDT é acessada por meio de uma entrada na GDT. A LDT pode armazenar mais tipos de segmentos. A LDT pode ser por processo. Ambas as tabelas definem até 8191 entradas. [[linux-i386]] ==== Implementação no Linux(R) i386 Existem duas principais maneiras de configurar o TLS no Linux(R). Pode ser definido ao clonar um processo usando a chamada de sistema `clone` ou pode chamar `set_thread_area`. Quando um processo passa a flag `CLONE_SETTLS` para `clone`, o kernel espera que a memória apontada pelo registro `%esi` seja uma representação do espaço do usuário Linux(R) de um segmento, que é traduzido para a representação do segmento da máquina e carregado em um slot GDT. O slot GDT pode ser especificado com um número ou -1 pode ser usado, o que significa que o sistema deve escolher automaticamente o primeiro slot livre. Na prática, a grande maioria dos programas usa apenas uma entrada TLS e não se preocupa com o número da entrada. Exploramos isso na emulação e, na verdade, dependemos disso. [[tls-emu]] ==== Emulação de TLS do Linux(R) [[tls-i386]] ===== i386 O carregamento do TLS para a thread atual é feito chamando `set_thread_area`, enquanto o carregamento do TLS para um segundo processo no `clone` é feito em um bloco separado no `clone`. Essas duas funções são muito semelhantes. A única diferença é o carregamento real do segmento GDT, que ocorre na próxima troca de contexto para o processo recém-criado, enquanto o `set_thread_area` deve carregar isso diretamente. O código basicamente faz isso. Ele copia o descritor do segmento no formato Linux(R) do espaço do usuário. O código verifica o número do descritor, mas como isso difere entre FreeBSD e Linux(R), nós fazemos uma pequena manipulação. Nós suportamos apenas os índices 6, 3 e -1. O 6 é um número genuíno do Linux(R), o 3 é um número genuíno do FreeBSD e -1 significa seleção automática. Em seguida, definimos o número do descritor como o valor constante 3 e copiamos isso de volta para o espaço do usuário. Nós confiamos no processo do espaço do usuário usando o número do descritor, e isso funciona na maioria das vezes (nunca vi um caso em que isso não funcionasse), pois o processo do espaço do usuário normalmente passa o número 1. Em seguida, convertemos o descritor do formato Linux(R) para um formato dependente da máquina (ou seja, independente do sistema operacional) e copiamos isso para o descritor de segmento definido no FreeBSD. Finalmente, podemos carregá-lo. Atribuímos o descritor ao PCB (process control block) das threads e carregamos o segmento `%gs` usando `load_gs`. Esse carregamento deve ser feito em uma seção crítica para que nada possa nos interromper. O caso `CLONE_SETTLS` funciona exatamente da mesma maneira, apenas o carregamento usando `load_gs` não é realizado. O segmento usado para isso (número do segmento 3) é compartilhado entre processos FreeBSD e processos Linux(R), portanto, a camada de emulação do Linux(R) não adiciona nenhum overhead além do FreeBSD puro. [[tls-amd64]] ===== amd64 A implementação do amd64 é semelhante à do i386, mas inicialmente não havia um descritor de segmento de 32 bits usado para esse propósito (portanto, nem mesmo os usuários nativos de TLS de 32 bits funcionavam), então tivemos que adicionar esse segmento e implementar seu carregamento em cada troca de contexto (quando uma flag sinalizando o uso de 32 bits é definida). Além disso, o carregamento de TLS é exatamente o mesmo, apenas os números de segmento são diferentes e o formato do descritor e o carregamento diferem um pouco. [[futexes]] === Futexes [[sync-intro]] ==== Introdução à sincronização As threads necessitam de algum tipo de sincronização, o POSIX(R) fornece alguns mecanismos de sincronização, como mutexes para exclusão mútua, read-write locks para exclusão mútua com uma proporção enviesada de leituras e escritas, e variáveis de condição para sinalizar mudanças de status. É interessante notar que a API de threads POSIX(R) não oferece suporte para semáforos. A implementação dessas rotinas de sincronização depende fortemente do tipo de suporte a threading disponível. Em um modelo puro 1:M (userspace), a implementação pode ser feita exclusivamente no espaço de usuário, resultando em uma abordagem rápida e simples (embora as variáveis de condição possam ser implementadas usando sinais, o que pode ser mais lento). Em um modelo 1:1, as threads devem ser sincronizadas usando recursos do kernel, o que pode ser mais lento devido à necessidade de chamadas de sistema. O cenário misto M:N combina as abordagens anteriormente mencionadas ou depende exclusivamente do kernel. A sincronização de threads é uma parte vital da programação com threads, e seu desempenho pode afetar significativamente o programa resultante. Testes recentes no sistema operacional FreeBSD demonstraram um aumento de desempenho de 40% na implementação aprimorada do sx_lock no _ZFS_ (que faz uso intensivo de primitivas de sincronização). Embora esse exemplo se refira a operações no kernel, ele destaca a importância de primitivas de sincronização eficientes para o desempenho geral. Programas com threads devem ser escritos com o mínimo possível de contenção em locks. Caso contrário, em vez de realizar um trabalho útil, a thread apenas espera em um lock. Como resultado disso, os programas com threads bem escritos mostram pouca contenção em locks. [[futex-intro]] ==== Introdução a Futexes O Linux(R) implementa threading 1:1, ou seja, ele utiliza primitivas de sincronização no kernel. Como mencionado anteriormente, programas com threads bem escritos têm pouca contenção em locks. Assim, uma sequência típica pode ser realizada com o aumento/diminuição atômica do contador de referência do mutex, o que é muito rápido, conforme apresentado no seguinte exemplo: [.programlisting] .... pthread_mutex_lock(&mutex); ... pthread_mutex_unlock(&mutex); .... O threading 1:1 nos força a executar dois syscalls para as chamadas mutex, o que é muito lento. A solução implementada pelo Linux(R) 2.6 é chamada de "futexes". Os futexes implementam a verificação de contenção no espaço do usuário e chamam as primitivas do kernel apenas em caso de contenção. Dessa forma, o caso típico ocorre sem qualquer intervenção do kernel. Isso resulta em uma implementação de primitivas de sincronização razoavelmente rápida e flexível. [[futex-api]] ==== API do Futex A syscall do futex é assim: [.programlisting] .... int futex(void *uaddr, int op, int val, struct timespec *timeout, void *uaddr2, int val3); .... Neste exemplo, `uaddr` é o endereço do mutex no espaço do usuário, `op` é a operação que estamos prestes a realizar e os outros parâmetros têm significado específico para cada operação. Futexes implementam as seguintes operações: * `FUTEX_WAIT` * `FUTEX_WAKE` * `FUTEX_FD` * `FUTEX_REQUEUE` * `FUTEX_CMP_REQUEUE` * `FUTEX_WAKE_OP` [[futex-wait]] ===== FUTEX_WAIT Essa operação verifica se o valor `val` está escrito no endereço `uaddr`. Se não estiver, retorna `EWOULDBLOCK`. Caso contrário, a thread é colocada na fila do futex e é suspensa. Se o argumento `timeout` for diferente de zero, ele especifica o tempo máximo de suspensão. Caso contrário, a suspensão é infinita. [[futex-wake]] ===== FUTEX_WAKE Essa operação pega um futex em `uaddr` e acorda os primeiros `val` futexes na fila desse futex. [[futex-fd]] ===== FUTEX_FD Esta operação associa um descritor de arquivo com um determinado futex. [[futex-requeue]] ===== FUTEX_REQUEUE Essa operação pega `val` threads na fila do futex em `uaddr`, acorda-as e pega `val2` threads seguintes e as coloca novamente na fila do futex em `uaddr2`. [[futex-cmp-requeue]] ===== FUTEX_CMP_REQUEUE Essa operação faz o mesmo que `FUTEX_REQUEUE`, mas verifica primeiro se `val3` é igual a `val`. [[futex-wake-op]] ===== FUTEX_WAKE_OP Essa operação realiza uma operação atômica em `val3` (que contém codificado algum outro valor) e `uaddr`. Em seguida, acorda `val` threads no futex em `uaddr` e, se a operação atômica retornar um número positivo, acorda `val2` threads no futex em `uaddr2`. As operações implementadas em FUTEX_WAKE_OP são: * `FUTEX_OP_SET` * `FUTEX_OP_ADD` * `FUTEX_OP_OR` * `FUTEX_OP_AND` * `FUTEX_OP_XOR` [NOTE] ==== Não há parâmetro `val2` no protótipo do futex. O `val2` é obtido do parâmetro `struct timespec *timeout` para as operações `FUTEX_REQUEUE`, `FUTEX_CMP_REQUEUE` e `FUTEX_WAKE_OP`. ==== [[futex-emu]] ==== Emulação de Futex no FreeBSD A emulação de futex no FreeBSD é baseada no NetBSD e posteriormente estendida por nós. Ela é implementada nos arquivos `linux_futex.c` e [.filename]#linux_futex.h#. A estrutura `futex` se parece com: [.programlisting] .... struct futex { void *f_uaddr; int f_refcount; LIST_ENTRY(futex) f_list; TAILQ_HEAD(lf_waiting_paroc, waiting_proc) f_waiting_proc; }; .... E a estrutura `waiting_proc` é: [.programlisting] .... struct waiting_proc { struct thread *wp_t; struct futex *wp_new_futex; TAILQ_ENTRY(waiting_proc) wp_list; }; .... [[futex-get]] ===== futex_get / futex_put Um futex é obtido usando a função `futex_get`, que busca em uma lista linear de futexes e retorna o encontrado ou cria um novo futex. Ao liberar um futex do uso, chamamos a função `futex_put`, que diminui um contador de referência do futex e, se o contador de referência chegar a zero, ele é liberado. [[futex-sleep]] ===== futex_sleep Quando um futex coloca uma thread em espera, ele cria uma estrutura `working_proc` e a coloca na lista dentro da estrutura do futex. Em seguida, ele executa um `man:tsleep[9]` para suspender a thread. A suspensão pode ter um tempo limite. Após o retorno do `man:tsleep[9]` (quando a thread foi acordada ou quando expirou o tempo limite), a estrutura `working_proc` é removida da lista e destruída. Tudo isso é feito na função `futex_sleep`. Se acordamos de um `futex_wake`, `wp_new_futex` é definido para que durmamos nele. Dessa forma, o reenfileiramento real é feito nessa função. [[futex-wake-2]] ===== futex_wake Acordar uma thread que está dormindo em um futex é realizado na função `futex_wake`. Primeiro, nesta função, imitamos o comportamento estranho do Linux(R), onde ele acorda N threads para todas as operações, com a única exceção de que as operações REQUEUE são realizadas em N+1 threads. Mas isso geralmente não faz diferença, pois estamos acordando todas as threads. Em seguida, no loop da função, acordamos n threads e, em seguida, verificamos se há um novo futex para reenfileiramento. Se houver, reenfileiramos até n2 threads no novo futex. Isso coopera com a função `futex_sleep`. [[futex-wake-op-2]] ===== futex_wake_op A operação `FUTEX_WAKE_OP` é bastante complexa. Primeiro, obtemos dois futexes nos endereços `uaddr` e `uaddr2`, em seguida, realizamos a operação atômica usando `val3` e `uaddr2`. Em seguida, acordamos as threads em espera com valor `val` no primeiro futex e, se a condição da operação atômica for satisfeita, acordamos a thread em espera com valor `val2` (ou seja, `timeout`) no segundo futex. [[futex-atomic-op]] ===== operação atômica futex A operação atômica recebe dois parâmetros: `encoded_op` e `uaddr`. A operação codificada codifica a própria operação, o valor de comparação, o argumento da operação e o argumento de comparação. O pseudocódigo para a operação é semelhante a este: [.programlisting] .... oldval = *uaddr2 *uaddr2 = oldval OP oparg .... E isso é feito atomicamente. Primeiro, é feita uma cópia do número em `uaddr` e, em seguida, a operação é realizada. O código lida com faltas de página e, se nenhuma falta de página ocorrer, `oldval` é comparado com o argumento `cmparg` usando o comparador `cmp`. [[futex-locking]] ===== Bloqueio Futex A implementação do futex utiliza duas listas de bloqueio para proteger o `sx_lock` e os bloqueios globais (seja Giant ou outro `sx_lock`). Cada operação é realizada com bloqueio desde o início até o final. [[syscall-impl]] === Implementação de várias syscalls Nesta seção, descreverei algumas syscalls menores que merecem destaque, pois sua implementação não é óbvia ou as syscalls são interessantes de outro ponto de vista. [[syscall-at]] ==== *na família de syscalls Durante o desenvolvimento do kernel Linux(R) 2.6.16, as chamadas de sistema *at foram adicionadas. Essas chamadas de sistema (`openat`, por exemplo) funcionam exatamente como suas contrapartes sem o "at", com a pequena exceção do parâmetro `dirfd`. Esse parâmetro altera onde o arquivo fornecido, no qual a chamada de sistema será executada, está localizado. Quando o parâmetro `filename` é absoluto, o `dirfd` é ignorado, mas quando o caminho para o arquivo é relativo, ele entra em jogo. O parâmetro `dirfd` é um diretório relativo ao qual o caminho relativo do arquivo é verificado. O `dirfd` é um descritor de arquivo de algum diretório ou `AT_FDCWD`. Portanto, por exemplo, a chamada de sistema `openat` pode ser assim: [.programlisting] .... 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 */ .... Essa infraestrutura é necessária para evitar corridas ao abrir arquivos fora do diretório de trabalho. Imagine que um processo consista em dois threads, thread A e thread B. A thread A chama `open(./tmp/foo/bah., flags, mode)` e antes de retornar, ela é preemptada e a thread B é executada. A thread B não se importa com as necessidades da thread A e renomeia ou remove [.filename]#/tmp/foo/#. Temos uma corrida. Para evitar isso, podemos abrir [.filename]#/tmp/foo# e usá-lo como `dirfd` para a chamada de sistema `openat`. Isso também permite que o usuário implemente diretórios de trabalho específicos por thread. A família de syscalls *at do Linux(R) contém: `linux_openat`, `linux_mkdirat`, `linux_mknodat`, `linux_fchownat`, `linux_futimesat`, `linux_fstatat64`, `linux_unlinkat`, `linux_renameat`, `linux_linkat`, `linux_symlinkat`, `linux_readlinkat`, `linux_fchmodat` e `linux_faccessat`. Todas essas syscalls são implementadas usando a rotina modificada man:namei[9] e uma camada de encapsulamento simples. [[implementation]] ===== Implementação A implementação é feita alterando a rotina man:namei[9] (descrita anteriormente) para receber um parâmetro adicional `dirfd` em sua estrutura `nameidata`, que especifica o ponto de partida da pesquisa do caminho em vez de usar o diretório de trabalho atual todas as vezes. A resolução do `dirfd` do número de descritor de arquivo para um vnode é feita nas syscalls *at nativas. Quando `dirfd` é `AT_FDCWD`, a entrada `dvp` na estrutura `nameidata` é `NULL`, mas quando `dirfd` é um número diferente, obtemos um arquivo para esse descritor de arquivo, verificamos se esse arquivo é válido e, se houver um vnode associado a ele, obtemos um vnode. Em seguida, verificamos se esse vnode é um diretório. Na própria rotina man:namei[9], simplesmente substituímos o vnode `dvp` pela variável `dp`, que determina o ponto de partida. A rotina man:namei[9] não é usada diretamente, mas sim através de uma sequência de diferentes funções em vários níveis. Por exemplo, o `openat` funciona da seguinte maneira: [.programlisting] .... openat() --> kern_openat() --> vn_open() -> namei() .... Por esse motivo, `kern_open` e `vn_open` devem ser alterados para incorporar o parâmetro adicional `dirfd`. Nenhuma camada de compatibilidade é criada para essas funções porque não há muitos usuários desse recurso e os usuários existentes podem ser facilmente convertidos. Essa implementação geral permite que o FreeBSD implemente seus próprios syscalls *at. Isso está sendo discutido atualmente. [[ioctl]] ==== Ioctl A interface ioctl é bastante frágil devido à sua generalidade. Devemos ter em mente que os dispositivos diferem entre o Linux(R) e o FreeBSD, então é necessário ter cuidado para garantir que a emulação do ioctl funcione corretamente. O tratamento do ioctl é implementado em [.filename]#linux_ioctl.c#, onde a função `linux_ioctl` é definida. Essa função simplesmente itera sobre conjuntos de manipuladores de ioctl para encontrar um manipulador que implemente um determinado comando. A chamada de sistema ioctl possui três parâmetros: o descritor de arquivo, o comando e um argumento. O comando é um número de 16 bits, que teoricamente é dividido em 8 bits superiores que determinam a classe do comando ioctl e 8 bits inferiores, que são o comando real dentro do conjunto dado. A emulação aproveita essa divisão. Implementamos manipuladores para cada conjunto, como `sound_handler` ou `disk_handler`. Cada manipulador possui um comando máximo e um comando mínimo definido, que é usado para determinar qual manipulador será usado. Existem pequenos problemas com essa abordagem porque o Linux(R) não usa a divisão de conjunto de forma consistente, então às vezes os ioctl de um conjunto diferente estão dentro de um conjunto ao qual não deveriam pertencer (ioctl genéricos do SCSI dentro do conjunto de cdrom, etc.). Atualmente, o FreeBSD não implementa muitos ioctl do Linux(R) (em comparação com o NetBSD, por exemplo), mas o plano é portá-los do NetBSD. A tendência é usar os ioctl do Linux(R) mesmo nos drivers nativos do FreeBSD devido à facilidade de portar aplicativos. [[debugging]] ==== Depuração Cada chamada de sistema deve ser passível de depuração. Para esse propósito, introduzimos uma pequena infraestrutura. Temos a facilidade ldebug, que indica se uma determinada chamada de sistema deve ser depurada (configurável através de um sysctl). Para impressão, temos as macros LMSG e ARGS. Essas macros são usadas para modificar uma string imprimível para mensagens de depuração uniformes. [[conclusion]] == Conclusão [[results]] === Resultados A partir de abril de 2007, a camada de emulação do Linux(R) é capaz de emular bem o kernel Linux(R) 2.6.16. Os problemas restantes envolvem futexes, chamadas de sistema inacabadas da família *at, entrega problemática de sinais, falta de suporte a `epoll` e `inotify`, e provavelmente alguns bugs que ainda não foram descobertos. Apesar disso, somos capazes de executar basicamente todos os programas Linux(R) incluídos na Coleção de Ports do FreeBSD com o Fedora Core 4 no kernel 2.6.16, e existem alguns relatos rudimentares de sucesso com o Fedora Core 6 no kernel 2.6.16. O linux_base do Fedora Core 6 foi recentemente adicionado, permitindo testes adicionais da camada de emulação e fornecendo mais informações sobre onde devemos concentrar nossos esforços na implementação do que está faltando. Somos capazes de executar os aplicativos mais usados, como o pacote `www/linux-firefox`, o pacote `net-im/skype` e alguns jogos da Coleção de Ports. Alguns desses programas apresentam comportamento inadequado sob a emulação do 2.6, mas isso está atualmente em investigação e esperamos que seja corrigido em breve. O único grande aplicativo conhecido por não funcionar é o Java(TM) Development Kit do Linux(R), devido ao requisito da facilidade `epoll`, que não está diretamente relacionada ao kernel do Linux(R) 2.6. Esperamos habilitar a emulação do 2.6.16 como padrão algum tempo depois do lançamento do FreeBSD 7.0, pelo menos para expor as partes de emulação 2.6 para um teste mais amplo. Uma vez feito isso, podemos mudar para o linux_base do Fedora Core 6, que é o plano final. [[future-work]] === Trabalho futuro O trabalho futuro deve se concentrar em corrigir os problemas restantes com futexes, implementar o restante da família de chamadas de sistema *at, corrigir a entrega de sinais e possivelmente implementar as facilidades `epoll` e `inotify`. Esperamos poder executar os programas mais importantes com perfeição em breve, por isso poderemos alternar para a emulação 2.6 por padrão e fazer do Fedora Core 6 o linux_base padrão porque o nosso atualmente usado Fedora Core 4 não é mais suportado. Outro objetivo possível é compartilhar nosso código com o NetBSD e o DragonflyBSD. O NetBSD tem algum suporte para emulação 2.6, mas está longe de estar completo e não foi realmente testado. O DragonflyBSD mostrou interesse em portar as melhorias do 2.6. Em geral, à medida que o Linux(R) se desenvolve, gostaríamos de acompanhar o seu desenvolvimento, implementando as novas chamadas de sistema adicionadas. O `splice` é uma delas que vem à mente em primeiro lugar. Algumas chamadas de sistema já implementadas também podem ser aprimoradas, por exemplo, `mremap` e outras. Também podem ser feitas melhorias de desempenho, como bloqueio mais refinado e outros. [[team]] === Equipe Eu colaborei neste projeto com (em ordem alfabética): * `{jhb}` * `{kib}` * Emmanuel Dreyfus * Scot Hetzel * `{jkim}` * `{netchild}` * `{ssouhlal}` * Li Xiao * `{davidxu}` Gostaria de agradecer a todas as pessoas por seus conselhos, revisões de código e apoio geral. [[literatures]] == Literaturas -. Marshall Kirk McKusick - George V. Nevile-Neil. Design and Implementation of the FreeBSD operating system. Addison-Wesley, 2005. +. Marshall Kirk McKusick - George V. Neville-Neil. Design and Implementation of the FreeBSD operating system. Addison-Wesley, 2005. . https://tldp.org[https://tldp.org] . https://www.kernel.org[https://www.kernel.org]