Processes are dynamic entities whose lifetimes range from a few milliseconds to months. Thus, the kernel must be able to handle many processes at the same time, and process descriptors are stored in dynamic memory rather than in the memory area permanently assigned to the kernel. Linux stores two different data structures for each process in a single 8 KB memory area: the process descriptor and the Kernel Mode process stack.

In Section 2.3, we learned that a process in Kernel Mode accesses a stack contained in the kernel data segment, which is different from the stack used by the process in User Mode. Since kernel control paths make little use of the stack, only a few thousand bytes of kernel stack are required. Therefore, 8 KB is ample space for the stack and the process descriptor.

Figure 3-2 shows how the two data structures are stored in the 2-page (8 KB) memory area. The process descriptor resides at the beginning of the memory area and the stack grows downward from the end.

Figure 3-2. Storing the process descriptor and the process kernel stack

The esp register is the CPU stack pointer, which is used to address the stack’s top location. On Intel systems, the stack starts at the end and grows toward the beginning of the memory area. Right after switching from User Mode to Kernel Mode, the kernel stack of a process is always empty, and therefore the esp register points to the byte immediately following the memory area.

The value of the esp is decremented as soon as data is written into the stack. Since the process descriptor is less than 1,000 bytes long, the kernel stack can expand up to 7,200 bytes.

The C language allows the process descriptor and the kernel stack of a process to be conveniently represented by means of the following union construct:

union task_union { 
    struct task_struct task; 
    unsigned long stack[2048]; 
};

The process descriptor shown in Figure 3-2 is stored starting at address 0x015fa000, and the stack is stored starting at address 0x015fc000. The value of the esp register points to the current top of the stack at 0x015fa878.

The kernel uses the alloc_task_struct and free_task_struct macros to allocate and release the 8 KB memory area storing a process descriptor and a kernel stack.

The close association between the process descriptor and the Kernel Mode stack just described offers a key benefit in terms of efficiency: the kernel can easily obtain the process descriptor pointer of the process currently running on a CPU from the value of the esp register. In fact, since the memory area is 8 KB (2¹³ bytes) long, all the kernel has to do is mask out the 13 least significant bits of esp to obtain the base address of the process descriptor. This is done by the current macro, which produces assembly language instructions like the following:

movl $0xffffe000, %ecx 
andl %esp, %ecx 
movl %ecx, p

After executing these three instructions, p contains the process descriptor pointer of the process running on the CPU that executes the instruction.^[18]

The current macro often appears in kernel code as a prefix to fields of the process descriptor. For example, current->pid returns the process ID of the process currently running on the CPU.

Another advantage of storing the process descriptor with the stack emerges on multiprocessor systems: the correct current process for each hardware processor can be derived just by checking the stack, as shown previously. Linux 2.0 did not store the kernel stack and the process descriptor together. Instead, it was forced to introduce a global static variable called current to identify the process descriptor of the running process. On multiprocessor systems, it was necessary to define current as an array—one element for each available CPU.

To allow an efficient search through processes of a given type (for instance, all processes in a runnable state), the kernel creates several lists of processes. Each list consists of pointers to process descriptors. A list pointer (that is, the field that each process uses to point to the next process) is embedded right in the process descriptor’s data structure. When you look at the C-language declaration of the task_struct structure, the descriptors may seem to turn in on themselves in a complicated recursive manner. However, the concept is no more complicated than any list, which is a data structure containing a pointer to the next instance of itself.

A circular doubly linked list (see Figure 3-3) links all existing process descriptors; we will call it the process list . The prev_task and next_task fields of each process descriptor are used to implement the list. The head of the list is the init_task descriptor; it is the ancestor of all processes, and is called process 0 or swapper (see Section 3.4.2 later in this chapter). The prev_task field of init_task points to the process descriptor inserted last in the list.

Figure 3-3. The process list

The SET_LINKS and REMOVE_LINKS macros are used to insert and to remove a process descriptor in the process list, respectively. These macros also take care of the parenthood relationship of the process (see Section 3.2.3 later in this chapter).

Another useful macro, called for_each_task, scans the whole process list. It is defined as:

#define for_each_task(p)  
    for (p = &init_task ; (p = p->next_task) != &init_task ; )

The macro is the loop control statement after which the kernel programmer supplies the loop. Notice how the init_task process descriptor just plays the role of list header. The macro starts by moving past init_task to the next task and continues until it reaches init_task again (thanks to the circularity of the list).

The process list is a special doubly linked list. However, as you may have noticed, the Linux kernel uses hundreds of doubly linked lists that store the various kernel data structures.

For each list, a set of primitive operations must be implemented: initializing the list, inserting and deleting an element, scanning the list, and so on. It would be both a waste of programmers’ efforts and a waste of memory to replicate the primitive operations for each different list.

Therefore, the Linux kernel defines the list_head data structure, whose fields next and prev represent the forward and back pointers of a generic doubly linked list element, respectively. It is important to note, however, that the pointers in a list_head field store the addresses of other list_head fields rather than the addresses of the whole data structures in which the list_head structure is included (see Figure 3-4).

Figure 3-4. A doubly linked list built with list_head data structures

A new list is created by using the LIST_HEAD(list_name) macro. It declares a new variable named list_name of type list_head, which is the conventional first element of the new list (much as init_task is the conventional first element of the process list).

Several functions and macros implement the primitives, including those shown in the following list.

When looking for a new process to run on the CPU, the kernel has to consider only the runnable processes (that is, the processes in the TASK_RUNNING state). Since it is rather inefficient to scan the whole process list, a doubly linked circular list of TASK_RUNNING processes called runqueue has been introduced. This list is implemented through the run_list field of type list_head in the process descriptor. As in the previous case, the init_task process descriptor plays the role of list header. The nr_running variable stores the total number of runnable processes.

The add_to_runqueue( ) function inserts a process descriptor at the beginning of the list, while del_from_runqueue( ) removes a process descriptor from the list. For scheduling purposes, two functions, move_first_runqueue( ) and move_last_runqueue( ), are provided to move a process descriptor to the beginning or the end of the runqueue, respectively. The task_on_runqueue( ) function checks whether a given process is inserted into the runqueue.

Finally, the wake_up_process( ) function is used to make a process runnable. It sets the process state to TASK_RUNNING and invokes add_to_runqueue( ) to insert the process in the runqueue list. It also forces the invocation of the scheduler when the process has a dynamic priority larger than that of the current process or, in SMP systems, that of a process currently executing on some other CPU (see Chapter 11).

In several circumstances, the kernel must be able to derive the process descriptor pointer corresponding to a PID. This occurs, for instance, in servicing the kill( ) system call. When process P1 wishes to send a signal to another process, P2, it invokes the kill( ) system call specifying the PID of P2 as the parameter. The kernel derives the process descriptor pointer from the PID and then extracts the pointer to the data structure that records the pending signals from P2’s process descriptor.

Scanning the process list sequentially and checking the pid fields of the process descriptors is feasible but rather inefficient. To speed up the search, a pidhash hash table consisting of PIDHASH_SZ elements has been introduced (PIDHASH_SZ is usually set to 1,024). The table entries contain process descriptor pointers. The PID is transformed into a table index using the pid_hashfn macro:

#define pid_hashfn(x) ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

As every basic computer science course explains, a hash function does not always ensure a one-to-one correspondence between PIDs and table indexes. Two different PIDs that hash into the same table index are said to be colliding .

Linux uses chaining to handle colliding PIDs; each table entry is a doubly linked list of colliding process descriptors. These lists are implemented by means of the pidhash_next and pidhash_pprev fields in the process descriptor. Figure 3-5 illustrates a pidhash table with two lists. The processes having PIDs 199 and 26,799 hash into the 200th element of the table, while the process having PID 26,800 hashes into the 217th element of the table.

Figure 3-5. The pidhash table and chained lists

Hashing with chaining is preferable to a linear transformation from PIDs to table indexes because at any given instance, the number of processes in the system is usually far below 32,767 (the maximum allowed PID). It is a waste of storage to define a table consisting of 32,768 entries, if, at any given instance, most such entries are unused.

The hash_pid( ) and unhash_pid( ) functions are invoked to insert and remove a process in the pidhash table, respectively. The find_task_by_pid( ) function searches the hash table and returns the process descriptor pointer of the process with a given PID (or a null pointer if it does not find the process).

Wait queues have several uses in the kernel, particularly for interrupt handling, process synchronization, and timing. Because these topics are discussed in later chapters, we’ll just say here that a process must often wait for some event to occur, such as for a disk operation to terminate, a system resource to be released, or a fixed interval of time to elapse. Wait queues implement conditional waits on events: a process wishing to wait for a specific event places itself in the proper wait queue and relinquishes control. Therefore, a wait queue represents a set of sleeping processes, which are woken up by the kernel when some condition becomes true.

Wait queues are implemented as doubly linked lists whose elements include pointers to process descriptors. Each wait queue is identified by a wait queue head , a data structure of type wait_queue_head_t:

struct _ _wait_queue_head {
    spinlock_t lock;
    struct list_head task_list;
};
typedef struct _ _wait_queue_head wait_queue_head_t;

Since wait queues are modified by interrupt handlers as well by major kernel functions, the doubly linked lists must be protected from concurrent accesses, which could induce unpredictable results (see Chapter 5). Synchronization is achieved by the lock spin lock in the wait queue head.

Elements of a wait queue list are of type wait_queue_t:

struct _ _wait_queue {
    unsigned int flags;
    struct task_struct * task;
    struct list_head task_list;
};
typedef struct _ _wait_queue wait_queue_t;

Each element in the wait queue list represents a sleeping process, which is waiting for some event to occur; its descriptor address is stored in the task field. However, it is not always convenient to wake up all sleeping processes in a wait queue.

For instance, if two or more processes are waiting for exclusive access to some resource to be released, it makes sense to wake up just one process in the wait queue. This process takes the resource, while the other processes continue to sleep. (This avoids a problem known as the “thundering herd,” with which multiple processes are awoken only to race for a resource that can be accessed by one of them, and the result is that remaining processes must once more be put back to sleep.)

Thus, there are two kinds of sleeping processes: exclusive processes (denoted by the value 1 in the flags field of the corresponding wait queue element) are selectively woken up by the kernel, while nonexclusive processes (denoted by the value 0 in flags) are always woken up by the kernel when the event occurs. A process waiting for a resource that can be granted to just one process at a time is a typical exclusive process. Processes waiting for an event like the termination of a disk operation are nonexclusive.

The add_wait_queue( ) function inserts a nonexclusive process in the first position of a wait queue list. The add_wait_queue_exclusive( ) function inserts an exclusive process in the last position of a wait queue list. The remove_wait_queue( ) function removes a process from a wait queue list. The waitqueue_active( ) function checks whether a given wait queue list is empty.

A new wait queue may be defined by using the DECLARE_WAIT_QUEUE_HEAD(name) macro, which statically declares and initializes a new wait queue head variable called name. The init_waitqueue_head( ) function may be used to initialize a wait queue head variable that was allocated dynamically.

A process wishing to wait for a specific condition can invoke any of the functions shown in the following list.

Notice that any process put to sleep by one of the above functions or macros is nonexclusive. Whenever the kernel wants to insert an exclusive process into a wait queue, it invokes add_wait_queue_exclusive( ) directly.

Processes inserted in a wait queue enter the TASK_RUNNING state by means of one of the following macros: wake_up, wake_up_nr, wake_up_all, wake_up_sync, wake_up_sync_nr, wake_up_interruptible, wake_up_interruptible_nr, wake_up_interruptible_all, wake_up_interruptible_sync, and wake_up_interruptible_sync_nr. We can understand what each of these ten macros does from its name:

For instance, the wake_up macro is equivalent to the following code fragment:

void wake_up(wait_queue_head_t *q)
{
    struct list_head *tmp;
    wait_queue_t *curr;

    list_for_each(tmp, &q->task_list) {
        curr = list_entry(tmp, wait_queue_t, task_list);
        wake_up_process(curr->task);
        if (curr->flags)
            break;
    }
}

The list_for_each macro scans all items in the doubly linked list of q. For each item, the list_entry macro computes the address of the correspondent wait_queue_t variable. The task field of this variable stores the pointer to the process descriptor, which is then passed to the wake_up_process( ) function. If the woken process is exclusive, the loop terminates. Since all nonexclusive processes are always at the beginning of the doubly linked list and all exclusive processes are at the end, the function always waken the nonexclusive processes and then wakes one exclusive process, if any exists.^[19] Notice that awoken processes are not removed from the wait queue. A process could be awoken while the wait condition is still false; in this case, the process may suspend itself again in the same wait queue.