Class 8: Internal Kernel Interfaces, part III

Date: 21.04.2026

Resources

Note

These resources are intended to be used with the kernel debugging tools. Please refer to the Kernel debuggers section in the Class 7 materials for details on how to use them.

Blocking operations

Wait queues

A process that must wait for a certain event to occur (e.g., completion of an I/O operation, or arrival of data in a FIFO queue), is removed from the ready process queue and placed in the waitqueues The process state changes from TASK_RUNNING to TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE. The structure representing the head of the list in which such processes are placed is wait_queue_head_t, defined in the linux/wait.h file.

Selected operations:

DECLARE_WAIT_QUEUE_HEAD(name).

Before using wait_queue you need to initialize it.

wait_event(name, cond).

puts the process in the wait queue in a signal-resistant state (TASK_UNINTERRUPTIBLE) and sleeping until the cond occurs

wait_event_interruptible(name, cond).

as above, but transitioning to the TASK_INTERRUPTIBLE state. (the arrival of a signal will cause a transition to the TASK_RUNNING state), returns 0 if cond has occurred, -ERESTARTSYS if interrupted by a signal

wait_event_timeout(name,cond,timeout).

like wait_event, but with waking up after the specified timeout even if cond has not occurred

wait_event_interruptible_timeout(name,cond,timeout).

as above, but transition to TASK_INTERRUPTIBLE state.

wake_up(name).

wakes up all waiting processes without the WQ_FLAG_EXCLUSIVE flag set, and one that has it set. Note: the function does not remove the process from the waiting queue - the process will 'remove' itself, after resuming operation

wake_up_interruptible(name).

as above, but only for processes in TASK_INTERRUPTIBLE state.

wake_up_all(name).

insert all processes (in state TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE). located in the waiting queue to the ready process queue

The above operations are defined in linux/sched.h (except the first one, defined in linux/wait.h).

When using wait queues, care should be taken to avoid races. For example, if we are a reader and we want to wait for the writer to write any data to a lock-protected buffer, the waiting code might look like this:

/* definitions */
DEFINE_MUTEX(lock);
DECLARE_WAIT_QUEUE_HEAD(queue);
int pos_read, pos_write;
char *buffer;

/* loading a byte */
char character;
/* locking */
mutex_lock(&block);
/* check if we already have data to read */
while (pos_read == pos_write) {
    /* we don't have - we need to remove the lock so that the writer can do anything */
    mutex_unlock(&block);
    /* we are waiting for a write - the condition ensures that we don't wait,
       if the writer has updated pos_write between the time we gave up the lock,
       and we joined the queue - otherwise the
       writer's wake_up would not cover our process and we would wait
       much longer (perhaps forever). The condition is checked
       after being added to the waiting queue, but before the actual
       waiting. */
    wait_event(queue, pos_read != pos_write);
    /* wait_event only ensures that at some point since the call
       pos_read != pos_write occurred, but some other thread may have
       emptied the buffer in the meantime - we can't assume anything
       until we check this condition while holding the lock - so we take the
       lock and check the while condition again, until we get it */
    mutex_lock(&block);
}
/* successful - we can read the character */.
character = buffer[pos_read++];
mutex_unlock(&block);

Waiting for completion

This is a rather strange variant of the semaphore:

  • we create a structure struct completion, which initially has a value of 0

  • we can perform the complete operation, which increases the value of the structure by 1

  • we can perform the wait_for_completion operation (or its variants), which waits, until the structure has a positive value, then decreases it by 1

  • we can perform the complete_all operation, which permanently sets the value of the structure to UINT_MAX (all waiting threads are woken up, all further executions of complete and wait_for_completion will be no-ops)

Here is a typical use of the 'wait for completion' mechanism:

struct completion event;

init_completion(&event);

/* .. pass a pointer to event to whoever is to wake up .... */

wait_for_completion(&event);

The wake-up caller calls:

complete(&event)

when the appropriate time arrives.

The implementation is in the kernel/sched/completion.c file, while the structure itself is declared in linux/completion.h.

Other useful kernel features

The kernel library contains many other ready-to-use functions, which can prove useful when writing a great variety of drivers. Among the more useful ones can be mentioned:

linux/idr.h.

int map into void * with dynamic identifier allocation

linux/kref.h.

easy reference counting

linux/bitmap.h

efficient bitmap arrays

linux/btree.h.

B-trees

linux/bug.h, asm-generic/bug.h.

Reporting critical errors in the driver code resulting from code defects and warnings (something like assert)

linux/circ_buf.h.

cyclic buffers

linux/hash.h.

simple hash functions

linux/kernel.h.

Miscellaneous simple functions:

ALIGN(x,a).

aligns x down to a multiple of a (a must be a power of two)

PTR_ALIGN(p, a).

as above, but on pointers

IS_ALIGNED(x, a).

checks if x is already aligned

ARRAY_SIZE(arr).

array size arr

DIV_ROUND_UP(n,d).

n/d, rounding up.

roundup(x, y).

rounds x up to a multiple of y.

upper_32_bits(x), lower_32_bits(x).

as in the name

might_sleep().

denotes where the code can sleep, helps with debugging (throws error if spinlock debugging is enabled and spinlock is held)

min(x,y), max(x,y).

as in the name

clamp(val, min, max).

val clipped to the range [min, max].

linux/kobject.h.

general object type with reference counting and visibility in sysfs (among others, cdev and device are based on them).

linux/parser.h.

a simple parser for options

linux/rbtree.h.

red-black trees