How a binary runs: OS level

How the processes are created

Executable binary is read from disk and code and static data are loaded into memory. Some memory must be allocated for the program’s run-time stack (or just stack). C convention programs use the stack for local variables, function parameters, and return addresses; the OS allocates this memory and gives it to the process. In C convention programs, the heap is used for explicitly requested dynamically-allocated data; programs request such space by calling malloc() and free it explicitly by calling free(). The heap will be small at first; as the program runs, and requests more memory via the malloc() library API.

• Malloc, sbrk, mmap

**sbrk: **when the heap segment is full, we can allocate more pages to it by making a syscall which maps more RAM available physical space to the virtual space of the program, allocating an entry in the page table. Legacy now.

Mmap: It allows us to avoid expensive CPU cycles while handling data copying form filesystem. It maps data/file from disk into memory without cpu handling copying.

Malloc: Used to allocate space on the already available heap segment.

Initially, heap segment only has 1 node with total heap size and next available space pointer(which will be zero initially).

Say we need 100 bytes of data(using malloc); then we take 100 bytes from current head ptr, and moves the head after that allocated space.

Head is moved to heap.size - allocated.len + allocated.size.len(4 bytes) and a magical.size(4 bytes, which is added for verification of the allocated object).

After some more allocations,

Apart from malloc, we also have a free system call which deallocates given object. Once we have deallocated that object, we put back a heap node size and next. Here, the next will not be 0; it will point to the next available heap node.

After few more deallocation, we will have

Now let’s say if we need to allocate space of 3,900 bytes, we don’t have that much space available in a single heap node. Due to this, we also have a call list algorithm which combines adjacent free spaces, which will result in a free space of 4,088 bytes. As a result, we would be able to allocate required space for object without needing to issue another sbrk system call.

In UNIX systems, each process by default has three open file descriptors, for standard input, output, and error; these descriptors let programs easily read input from the terminal as well as print output to the screen.

During its life cycle, the process can be in one of the three states:Running, Ready(process is ready to be executed but the os hasn’t scheduled it yet), Blocked. (zombie and orphaned too)

Being moved from ready to running means the process has been scheduled; being moved from running to ready means the process has been descheduled. Once a process has become blocked (e.g., by initiating an I/O operation), the OS will keep it as such until some event occurs (e.g., I/O completion); at that point, the process moves to the ready state again (and potentially immediately to running again, if the OS so decides).

Note: A process could be placed in a **final **state where it has exited but has not yet been cleaned up (in UNIX-based systems, this is called the **zombie **state). Usually happens when a parent process hasn’t called wait on the status of the child process. As a result, the OS hasn’t cleaned the process up.

OS uses Process list to store information about each process. It also has different fields to store information related to what’s the current process that’s running, when I/O is getting completed, etc., and with the data of each process log list (where it’s memory starts, what its instruction pointer is, what’s the stack pointer). This information is stored in a C data structure which is called process control block(struct proc).

• Fork, exec and wait

Fork basically in the memory, like copies the memory space which is code, static, heap and stack while changing this stack pointer to pointer at the new location so it just creates a copy and the fork command for parent will return the process id of the child and for child it will return zero that way we can distinguish which process is which.

What is exec? For the current process that is running, it goes in the memory. It changes the code static variable to be the data of the new program that it is running, and then it re-initializes the stack and the heap. That way, exec doesn’t create another process. It just rewrites the memory space of the current running process.

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <unistd.h>
4 #include <string.h>
5 #include <sys/wait.h>
6
7 int main(int argc, char *argv[])
8
9{
10 printf("hello world (pid:%d)\n", (int) getpid());
11 int rc = fork();
12 if (rc < 0) { // fork failed; exit
13 fprintf(stderr, "fork failed\n");
14 exit(1);
15 } else if (rc == 0) { // child (new process)
16 printf("hello, I am child (pid:%d)\n", (int) getpid());
17 char *myargs[3];
18 myargs[0] = strdup("wc"); // program: "wc" (word count)
19 myargs[1] = strdup("p3.c"); // argument: file to count
20 myargs[2] = NULL; // marks end of array
21 execvp(myargs[0], myargs); // runs word count
22 printf("this shouldn’t print out");
23 } else { // parent goes down this path (main)
24 int wc = wait(NULL);
25 printf("hello, I am parent of %d (wc:%d) (pid:%d)\n",
26 rc, wc, (int) getpid());
27 }
28 return 0;
29 }

wc -c a.txt > output.txt

For above command terminal, firstly folks, and creates a copy of itself. Then, it overrides its memory space using exec of WC command and copies that its code and static variables. Then, since there are three file descriptors of the new child process, it closes the standard out and replaces the standard out file descriptor with the new open file descriptor of output.txt. That way, this whole command is just a single process. It’s not that; it creates two processes: one is for reading the word count and another one for out writing the output file.

wc -c a.txt | tee output.txt

Versus what this command does: it creates two separate child processes, one for doing the wc count and another one for t. Then, this pipe function, what it does is between one process and another process, it creates a kernel pipe where the output of the wc command is the input of that pipe and the input of the t command is the output of that pipe. It is fundamentally different from the file descriptor.

Limited Direct Execution

The purpose of OS is to provide a safe execution environment with limited access to the code, while also having the ability to interrupt it without compromising on the performance speed. If the code that we are executing always passes through the OS, it will be a performance bottleneck. To avoid this, we have direct execution. The compiled binary has instructions, and these instructions are directly executed on the CPU.

How will we decide? There are two problems:

1. How do we ensure that only permissioned access to disk or system resources is allowed.

2. If this code is executed and the OS code is not executing, then how will we yield control back to the OS?

For solving the first problem, there are two execution modes supported by the hardware:

1. User mode(ring 3)

2. Kernel mode(ring 0)

In the user mode, only CPU usage is allowed; no access to disk or system resources is allowed. If the program wants to do some I/O, it needs to issue system calls. These system calls have handlers in sys-call table which is created by os during init(in kernel mode). The program issues a interrupt (int T_SYSCALL) to change to ring 0, with rax register having system call number to reference sys call table. Moving from ring 3 to ring 0 is called trap, which basically means trap into the kernel.

For example, if a system call to read the disk of a specified file is issued, there will be a trap instruction issued. This trap instruction will be pointing to a code where permissions will be checked, and only access to the specific file will be provided. These trap code will be executing in the kernel mode, so it can perform actions that are allowed, and this code is not modified or written by the executing binary.

This trap table is created during the boot time when the operations are being performed in the kernel mode by the OS.

And for solving the second problem, there are two approaches:

1. Cooperative: we can trust that the program will yield control.

2. Non-cooperative: there’s a timer interrupt which is executed every few milliseconds, which yields back the control to the OS. This timer interrupt is issued by the hardware. When your binary is executing, after few x milliseconds, the control is yielded back to the OS. The OS then checks whether a context switch or something should happen. If the OS finds that the context switch needs to happen, it saves the PCB variables in the case tech and then this control is passed to the OS. It checks whether the switch needs to be made. If the switch needs to be made, it again saves these variables into the stack, into the memory block of that program in the memory. The registers are copied into the OS, into the case tech, and then the return from trap instruction is issued to resume the execution of the program B.

Links:

• https://pages.cs.wisc.edu/~remzi/OSTEP/, covering processes, process API, and limited direct execution under virtualization.