Datasheet

Mauerer runc01.tex V2 - 09/04/2008 4:13pm Page 20
Chapter 1: Introduction and Overview
be assumed that the kernel still works as intended, and support is better left to the manufacturer of the
offending module.
Loading binary-only modules is not the only possibility for tainting a kernel. This happens also when,
for instance, the machine has experienced certain bad exceptions, when a SMP system is built with CPUs
that do not officially support multiprocessing by their specification, and other similar reasons.
1.3.12 Caching
The kernel uses caches to improve system performance. Data read from slow block devices are held
in RAM for a while, even if they are no longer needed at the time. When an application next accesses
the data, they can be read from fast RAM, thus bypassing the slow block device. Because the kernel
implements access to block devices by means of page memory mappings, caches are also organized into
pages, that is, whole pages are cached, thus giving rise to the name page cache.
The far less important buffer cache is used to cache data that are not organized into pages. On traditional
Unix systems, the buffer cache serves as the main system cache, and the same approach was used by
Linux a long, long time ago. By now, the buffer cache has mostly been superseded by the page cache.
1.3.13 List Handling
A recurring task in C programs is the handling of doubly linked lists. The kernel too is required to handle
such lists. Consequently, I will make frequent mention of the standard list implementation of the kernel
in the following chapters. At this point, I give a brief introduction to the list handling API.
Standard lists as provided by the kernel can be used to link data structures of any type with each other.
It is explicitly not type-safe. The data structures to be listed must contain an element of the
list_head
type; this accommodates the forward and back pointers. If a data structure is to be organized in several
lists — and this is not unusual — several
list_head elements are needed.
<list.h>
struct list_head {
struct list_head *next, *prev;
};
This element could be placed in a data structure as follows:
struct task_struct {
...
struct list_head run_list;
...
};
The starting point for linked lists is again an instance of list_head that is usually declared and initial-
ized by the
LIST_HEAD(list_name) macro. In this way, the kernel produces a cyclic list, as shown in
Figure 1-11. It permits access to the first and last element of a list in O(1), that is, in always the same,
constant time regardless of the list size.
20