Linux Kernel Architecture

Mauerer app03.tex V1 - 09/04/2008 6:11pm Page 1200

Appendix C: Notes on C

C.1.9 Pointer Arithmetic

Normally, pointers may be used for computations in C only if they have an explicit type; for example,

int *orlong *. Otherwise, it is not possible to establish which increment steps are to be used. The

GNU compiler circumnavigates this restriction and supports arithmetic withvoidpointers and func-

tion pointers — these are also used by the kernel at various points. In both cases, the increment step

is 1 byte.

Interestingly, GCC had at least once support for abit-addressablearchitecture — the Texas Instruments

34010 processor. Incrementing a pointer on this machine means that the memory position is advanced by

one bit, not one byte — a feature that did not quite become ubiquitous. While the pure existence of the

machine would most likely not be worth mentioning here, the fact that Andrew Morton — one of the key

persons for the development of the 2.6 kernel series — once wrote a real-time kernel for this processor

certainly does. You can download the source code fromwww.zip.com.au/~akpm/.

C.2 Standard Data Structures

and Techniques of the Kernel

In its C sources, the kernel adopts a number of methods and approaches that are essential to the program-

ming of operating systems but that are not normally used in C programs. This section discusses these

techniques, as well as standard data structures that are needed time and time again and are therefore

implemented as small, universal libraries.

C.2.1 Reference Counters

Instances of data structures required for a longer period are allocated by the kernel in its dynamic mem-

ory space. Once an instance is no longer needed, the allocated memory space can be returned to memory

management, as in normal C programs. This is not a problem if only one kernel component in a control

path is accessing the instance. In this case, it is easy to determine exactly when the memory space is no

longer needed. Complications arise when several processes or kernel threads access the same instance,

because they then share resources. The copy-on-write method and the shared usage of different process

resources by cloning tasks are examples of situations in which an instance of a data structure is needed

at several places. In this case, the kernel does not know when the data are no longer required and when

it can return the associated memory space.

To solve this problem, the kernel employs a technique used in the implementation of hard links. Data

structures are provided with ausageorreference counterwhich indicates at how many points in the kernel

the resource is in use. The usage counter is an atomic integer variable that is embedded somewhere in

the data structure and is usually namedcount, as in the following example:

struct shared {

...

atomic_t count;

...

}

The allocation routine distinguishes two cases. If no suitable instance is present, a new instance is created

and its usage counter is initialized to 1. If a suitable instance is present (which can be checked with the