Operating system kernel internals and system calls

Kernel data structures

Kernel data structures are analogous to those used in standard programming:

• Array: This is the simplest structure; the main memory is physically an array of bytes. Its disadvantages include a fixed size and the difficulty of adding and removing items in the middle.
• List: It is most commonly implemented as a linked list and it allows changing its size and inserting and removing items in the middle.
• Stack: This is a sequentially ordered data structure that uses LIFO for adding and removing items. It is used in memory to store local variables when a function is called.
• Queue: This is a sequentially ordered data structure using FIFO. It’s often used for buffers.

• Tree: Represents data hierarchically through parent-child relationships.

  • Binary search tree: This is a tree with at most two children per parent, usually the left one < right one.
• Hashmap: associates key-value pairs using hash functions.
• Bitmap: string of $𝑛$ binary digits. Useful to pack booleans space-efficiently.

Overview of operating system services

OS programming

System calls

System calls serve as the interface between kernel mode and user mode. In programming, they are almost never called directly. Instead, there are API wrappers like:

• Win32 for Windows;
• POSIX API for POSIX systems;
• Java API for the JVM;

Usually there are 3 layers of decoupling between applications and hardware:

• API: Defines the functions available for the programmer writing the source code;
• ABI: Defines the syscall parameters and their number, which must correspond between the kernel and the app;
• ISA: This is the set of instructions that the compiler can use; it depends on the processor (commonly x86-64 or arm);

Linkers and loaders

When code is compiled, the following happens:

1. The code is compiled into object files, designed to be loaded into any memory location.
2. The linker combines these objects into a single binary executable.
3. The program is saved to disk.

When the program needs execution:

1. The loader reads the executable from the disk.
2. It determines if it needs to load other dynamic libraries (.dll on Windows, .so on UNIX).
3. Once everything is loaded, it updates pointer locations inside the executable to point to the correct addresses in the virtual memory space where the program is loaded.

System call implementation

Apps compiled on one system typically don’t work on another. Each OS provides its own set of syscalls, equivalently one could say that each OS defines its own ABI.

In assembly, a number is assigned to each syscall, then a special instruction executes it with the given parameters:

section .data
    msg db "Hello, World!", 0xA
    len equ $ - msg;

section .text
    global _start

_start:
    mov rax, 1    ; set sys_write number
    mov rdi, 1    ; file descriptor for stdout
    mov rsi, msg  ; message address
    mov rdx, len  ; message length
    syscall

    mov rax, 60   ; set sys_exit number
    xor rdi, rdi  ; set exit code to 0
    syscall

The status of the system call and any return values are stored in specific registers.

Parameter passing

There are three methods to pass parameters to the OS:

• parameters in registers;
• parameters stored in a block of memory;
• parameters pushed to the stack and popped by the kernel;

Registers

Registers are small and limited in number, but they are extremely fast memory locations.

• General purpose registers are used to store temporary values, intermediate calculations or function arguments. Examples are RAX, RBX, RSI, RDI, SP.

• Special purpose registers have a predefined usage:

  • instruction pointer: points to the location in memory of the next instruction to execute;
  • control registers: used to configure CPU behavior (memory protection, paging);

Mechanism to manage system calls

Legacy systems utilized a mechanism called Direct Execution. In DE, the OS sets up the process, calls main, and then leaves it until it returns from main. Syscalls were implemented simply as function calls, so the program could do anything it wanted.

The OS couldn’t ensure that the program didn’t do anything that could be harmful. Now, with the introduction of some hardware support, the OS can define a set of instructions that the user is not allowed to execute in a trap table. This is how Limited Direct Execution (LDE) is implemented.

Each entry in the table points to a trap handler, which is called when the program calls one of those instructions.

In modern Linux, the table is referred to as Interrupt Descriptor Table. The IDT not only stores syscall handlers; it also defines handlers for exceptions like division by zero or page faults and handlers for hardware interrupts.

Now a program uses the syscall instruction, on that moment, the CPU fires the syscall interrupt and switches to kernel mode. The kernel can allow or reject the syscall in a protected environment, then it returns and the CPU switches back to user mode and continues to execute the process.

Timer interrupt for stopping process execution

LDE can also be used to allow the OS to retake control of the CPU to prevent processes from running indefinitely.

The mechanism is quite simple:

1. The OS defines a timer that triggers an interrupt every $𝑛$ fractions of a second.
2. The process executes.
3. When the interrupt fires, the kernel regains control and can decide to let the process continue executing or to do a context switch to another process.