Kernel Facilities & Helper Funcitons

Understanding container_of_macro

Bering in mind this structure:

struct person {

    int age;

    char *name:

}

By only having a pointer on age or name, one can retrive the whole structure wrapping (containing) that pointer. As the name says, container_of macro is udes to find the container of the given filed of a structure. The macro is defined in include/linux/kernel.h and looks like:

#define container_of(ptr, type, member) ({    \

    const typeof(((type *)0)->member) *__mptr = (ptr);    \

    (type *)((char *)__mptr - offset(type, member)); })

container_of(pinter, container_type, container_field);

• pointer: This is the pointer to the field in the structure.
• container_type: This is the type of the structure wrapping (containing) the pointer.
• container_filed: This is the name of the filed to which pointer points inside the structure.

Example:

struct {

    int age;

    char *name;

}

struct person somebody;

[...]

char *the_name_ptr = somebody.name;

struct person *the_person;

the_person = container_of(the_name_ptr, strcut person, name);

Linked Lists

Kernel developers only implement circular double linked list because this structure allows you to implement FIFO and LIFO, and kernel developers take care to mantain a minimal set of code. The header to be added in the code in order to support lists is <linux/list.h>. The data structure at the core of list implementation in the kernel is struct list_head structure, defined as the following:

struct list_head {

    struct list_head *next, *prev;

}

The struct list_head is used in both the head and the list and each node. In the world of the kernel, before a data structure can be represented as a linked list, that structure must embed a struct list_head field. For example, let's create a list of cars:

struct car {

    int door_number;

    char *color;

    char *model;

}

Before we can create a list for the car, we must change its structure in order to embed a struct list_head field. The structure becomes:

struct car {

    int door_number;

    char *color;

    char *model;

    struct list_head list; /* Kernel's list structure */

}

Creating and initializing the list (Dynamic method)

The dynamic method consists of a struct list_head and initializies it with the INIT_LIST_HEAD macro:

struct list_head my_list;

INIT_LIST_HEAD(&my_list);

INIT_LIST_HEAD definition is defined as follows:

static inline void INIT_LIST_HEAD(struct list_head *list) {

    list->next = list;

    list->prev = list;

}

(Static method)

Static allocation is made through the LIST_HEAD macro:

LIST_HEAD(my_lyst);

LIST_HEAD definition is defined as follows:

# define LIST_HEAD(name) \

    struct list_head name = LIST_HEAD_INIT(name)

Te folowing it its expansion:

#define LIST_HEAD_INIT(name) { &(name), &(name)}

Creating a list node

To create new nodes, just create our data struct instance, and initialize their embedded list_head field. Using the car example, it will give the following:

strcut car *blackcar = kzmalloc(sizeof(struct car), GFP_KERNEL);

INIT_LIST_HEAD(&blackcar->list);

Adding a list node

The kernel provides list_add to add a new entry to the list, which is a wrapper around the internal function __list_add:

void list_add(struct list_head *new, struct list_head *head);

static inline void list_add(struct list_head *new, struct list_head *head) {

    __list_add(new, head, head->next);

}

__list_add will take two known entries as a parameter, and inserts your elements between them. Its implementation in the kernel is quite easy:

static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)

{

    next->prev = new;

    new->next= next;

    new->prev = prev;

    prev->next = new;

}

The following is an example of adding two cars in our list:

list_add(&redcar->list,  &carlist);

list_add(&bluecar->list,  &carlist);

The other function to add an entry into the list is:

void list_add_tail(struct list_head *new, struct list_head *head);

The following is an example of adding two cars in our list:

list_add_tail(&redcar->list,  &carlist);

list_add_tail(&bluecar->list,  &carlist);

This mode can be used to implement a queue.

Deleting a node from the list

Deleting a node is strightforward:

void list_del(struct list_head *entry);

An example:

list_del(&redcar->list);

list_del disconnects the prev and next pointers of the given entry. The memory allocated for the node is not freed yet; you need to do that manually with kfree.

Macro list_for_each_entry

#define list_for_each_entry(pos, head, member) \

    for (pos = list_entry((head)->next, typeof(*pos), member); \

        &pos->member != (head); \

        pos = list_entry(pos->member.next, typeof(*pos), member))

#define list_entry(ptr, type, member) \

    container_of(ptr, type, member)

Example:

struct car *acar; /* loop counter */

int blue_car_num = 0;

/* 'list' is the name of the list_head struct in our data structure */

list_for_each_entry(acar, carlist, list) {

    if (acar->color == "blue")

        blue_car_num++;

}

Kernel sleeping mechanism

Sleeping is a mechanism by which a process relaxes a processor, with the posibility of handling another process. The reason why a processor can sleep could be for sensing data availability, or waiting for a resource to be free.

The kernel scheduler manages a list of tasks to run, known as a run queue. Sleeping processes are not scheduled anymore, since they are removes from tat run queue. Unless its state changes (taht is, wake up), a sleeping process will never be executed.

Wait queue

Wait queues are essentially used to process blocked I/O, to wait for particular conditions to be true, and to sense data or resource availability. To understand how it works, let's have a look at its structure in include/linux/wait.h:

struct __wait_queue {

    unsigned int flags;

#define WQ_FLAG_EXCLUSIVE 0x01

    void *private;

    wait_queue_funct_t func;

    struct list_head task_list;

}

As you can see task_list is a list. Every process you want to sleep is queued in that list and put into a sleep state until a condition becomes true. The wait queue can be seen as nothing but a simple list og processes and a lock.

Static declaration:

DECALRE_WAIT_QUEUE_HEAD(name);

Dynamic decalration:

wait_queue_head_t my_wait_queue;

init_waitqueue_head(&my_wait_queue);

Blocking:

/* block the current task (porcess) in the wait queue if CONDITIONis false */

int wait_event_interruptible(wait_queue_head_t q, CONDITION);

Unblokcing:

/*  wake up one process sleeping in the wait queue if CONDITION above has become true */

void wake_up_interruptible(wait_queue_head_t *q);

wait_event_interruptible does not continuously poll, but sumple evaluates the condition when it is calles. If the condition is false, the process is put into a TASK_INTERRUPTIBLE state and removed from the run queue. The condition is then only rechecked each time you call wake_up_interruptible in the wait queue. If the condition os true when wake_up_interruptible runs, a process in the wait queue will be awakened, and its state set to TASK_RUNNING. Processes are awakened int he order they are put to sleep. To awaken all processes waiting in the queue, you should use wake_up_interruptible_all.

Example:

/**

 * @file queue.c

 * @author  Oscar Gomez Fuente <oscargomezf@gmail.com>

 * @ingroup iElectronic

 * @version $Rev$

 * @date $Date$

 * @section DESCRIPTION

 *    Kernel Linux example with queues

 */

#include <linux/module.h>

#include <linux/init.h>

#include <linux/sched.h>

#include <linux/time.h>

#include <linux/delay.h>

#include <linux/workqueue.h>

static DECLARE_WAIT_QUEUE_HEAD(my_work_queue);

static int condition = 0;

/* declare work queue */

static struct work_struct my_work;

static void work_handler(struct work_struct *work)

{

    printk("[INFO] Wait queue module handler %s\n", __FUNCTION__);

    msleep(5000);

    printk("[INFO] Wake up the sleeping module\n");

    condition = 1;

    wake_up_interruptible(&my_work_queue);

}

static int __init my_init(void)

{

    printk("[INFO] Wait queue example init\n");

    INIT_WORK(&my_work, work_handler);

    schedule_work(&my_work);

    printk("[INFO] Going to sleep %s\n", __FUNCTION__);

    wait_event_interruptible(my_work_queue, condition != 0);

    printk("[INFO] Woken up by the work job\n");

    return 0;

}

static void __exit my_exit(void)

{

    printk("[INFO] Wait queue example exit\n");

}

module_init(my_init);

module_exit(my_exit);

MODULE_LICENSE("GPL");

MODULE_DESCRIPTION("Queue example");

MODULE_AUTHOR("Oscar Gomez Fuente <oscargomezf@gmail.com>");

Result:

[ 1828.891702] [INFO] Wait queue example init

[ 1828.891712] [INFO] Going to sleep my_init

[ 1828.891848] [INFO] Wait queue module handler work_handler

[ 1833.914136] [INFO] Wake up the sleeping module

[ 1833.914147] [INFO] Woken up by the work job

[ 1857.634460] [INFO] Wait queue example exit

Delay and timer management

Time is one of the most used resources, right after memory. It is used to do almost everything: defer work, sleep, scheduling, timeout, and many other tasks.

There are two categories of time. The kernel uses absolute time to know what time it is, that is, the date and time of the day, whereas relative time is used by, for example, the kernel schedule. For obasolute time, there is a hardware chip calles real-time clock (RTC). To handle relaives time, the kernel relies on a CPU feature (pheripheral), called a timer, which, from the kernel's point of view, is called a kernel timer. Kernel timers are what we will talk about in this section.

Kernel timers are classified into two different parts:

• Standard timers, or system timers.
• High-resolution timers.

Standard timers

Standard timers are kernel timers operating on the granularity of jiffies.

Jiffies and HZ

A jiffy is a kernel function unit of time declared in <linux/jiffies.h>. To understand jiffies, we need to introduce a new constant HZ, which is the number of times jiffies is incremented in one second. Each increment is called a tick. In other words, HZ represents the size of a jiffy. HZ depends on the hardware and on the kernel version, and also determines how frequently the clock interrupt fires. This is configurable on some architecture, fixed on other ones.

What it means is that jiffies is incremented HZ times everey sencond. If HZ = 1000, then it is incremented 1000 times (one tick every 1/1000 seconds). Once defined, the Porgrammable Interrupt Timer (PIT), which is a hardware component, is programmed with the value in order to increment jiffies the PIT interrupt comes in.

Depending on the platform, jiffies can lead to overflow. On a 32-bit system, HZ = 1000 will result in about 50 days duration only, whereas the duration is about 600 million years on a 64-bit system. By storing jiffies in a 64-bit variable, the problem is solved. A second variable has then been introduced and defined in <linux/jiffies.h>.:

extern u64 jiffies_64;

In this manner on 32-bit systems, jiffies will point to low-order 32-bits, and jiffies_64 will point to high-order bits. On 64-bit platforms, jiffies = jiffies_64.

Timers API

A timer is represented in the kernel as an instance of timer_list:

#include <linux/timer.h>

struct timer_liust {

    struct list_head entry;

    unsigned long expires;

    struct tvec_t_base_s *base;

    void (*function)(unsigned long);

    unsigned long data;

}

expires is an absolute value in jiffies. entry is a double linked list. data is optional, and passed to the callback function.

Timer setup initialization

The following are steps to initialize timers:

1. Setting up the timer: Set up the timer, feeding the user-defined callback and data:

void setup_timer( struct timer_list *timer, \

                  void (*function)(unsigned long), \

                  unsigned long data);

One can also use this:

void init_timer(struct timer_list *timer);

setup_timer is wrapped around init_timer.

2. Setting the expiration timer: When the timer is initialized, we need to set its expiration before the callback gets fired:

int mod_timer(struct timer_list *timer, unsigned long expires);

3. Releasing the timer: When you are done with the timer, it needs to be realeased.

void del_timer(struct timer_list *timer);

int del_timer_sync(struct timer_list *timer);

del_timer retruns void whether it has deactivated a pending timer or not. Its return value is 0 on an inactivate timer, or 1 on an active one. The last, del_timer_sync, waits for the handler to finish its execution, even those that may happend on another CPU. You should not hold a lock preventing the handleer's completion, otherwise it will result in a dead lock. You should release the timer in the module cleanup routine. You can independently check whether the timer is running or not:

int timer_pending(const struct timer_list *timer);

This functionchecks whether there are any fired timer callbacks pending.

Standard timer example

/**

 * @file timer.c

 * @author  Oscar Gomez Fuente <oscargomezf@gmail.com>

 * @ingroup iElectronic

 * @version $Rev$

 * @date $Date$

 * @section DESCRIPTION

 *    Kernel Linux example with timers

 */

#include <linux/init.h>

#include <linux/kernel.h>

#include <linux/module.h>

#include <linux/timer.h>

#include <linux/version.h>

static struct timer_list my_timer;

#if LINUX_VERSION_CODE < KERNEL_VERSION(4,14,0)

void my_timer_callback(unsigned long data)

{

#else

void my_timer_callback(struct timer_list *t)

{

#endif

    int ret;

    pr_info("[INFO] %s called (%ld).\n", __FUNCTION__, jiffies);

    ret = mod_timer(&my_timer, jiffies + msecs_to_jiffies(1000));

    if (ret)

        pr_info("[INFO] Timer firing failed");

    pr_info("[INFO] Setup timer to fire in 1000msec (%ld)\n", jiffies);

}

static int __init my_init(void)

{

    int ret;

    pr_info("[INFO] Timer module loaded\n");

#if LINUX_VERSION_CODE < KERNEL_VERSION(4,14,0)

    pr_info("[INFO] LINUX_VERSION_CODE < KERNEL_VERSION(4,14,0)\n");

    /*init_timer(&my_timer);

    my_timer.data = (unsigned long) 0;

    my_timer.function = my_timer_callback;*/

    setup_timer(&my_timer, my_timer_callback, 0);

    /*my_timer.expires = (unsigned long)(jiffies + msecs_to_jiffies(300));

    pr_info("[INFO] Timer firing failed");*/

#else

    pr_info("[INFO] LINUX_VERSION_CODE > KERNEL_VERSION(4,14,0)\n");

    timer_setup(&my_timer, my_timer_callback, 0);

    /* the third argument may include TIMER_* flags */

#endif

    ret = mod_timer(&my_timer, jiffies + msecs_to_jiffies(1000));

    if (ret)

        pr_info("[INFO] Timer firing failed");

    pr_info("[INFO] Setup timer to fire in 1000msec (%ld)\n", jiffies);

   return 0;

}

static void __exit my_exit(void)

{

    int ret;

    ret = del_timer(&my_timer);

    if (ret)

        pr_info("[INFO] The timer is still in use...");

    pr_info("[INFO] Timer module unloaded\n");

}

module_init(my_init);

module_exit(my_exit);

MODULE_LICENSE("GPL");

MODULE_DESCRIPTION("Timer example");

MODULE_AUTHOR("Oscar Gomez Fuente <oscargomezf@gmail.com>");

High resolution timers (HRTs)

Standard timers are less accurate and do not suit real-time applications. High-resolution timers, introduced in kernel 2.6.16 (and enabled by CONFIG_HIGH_RES_TIMERS option in the kernel configuration) have a resolution of microseconds (up yo milliseconds, depending on the platform), compared to milliseconds on standard timers. The standard timers depends on HZ (since the relay on jiffies), whereas HRT implementation is based on ktime.

Kernel and hardware must support an HRT before being used on your system. In other words, there must be an arch-dependent code implemented to access your hardware HRTs.

HRT API

The required headers are:

#include <linux/hrtimer.h>

An HRT is represented in he kernel as an instance of hrtimer:

struct hrtimer {

    struct timerqueue_node node;

    ktime_t _softexpires;

    enum hrtimer_restart (*function)(struct hrtimer *);

    enum hrtimer_clock_base *base;

    u8 state;

    u8 is_rel;

}

HRT setup initialization

1. Initialization the hrtimer: Before initialization, you need to set up a ktime, which represents time duration. We will see how to achieve that in the following example:

void hrtimer_init(struct hrtimer *timer, clockid_t which_clock, enum hrtimer_mode mode);

2. Starting hrtimer: hrtimer can be started as shown in the following example:

int hrtimer_start(struct hrtimer *timer, ktime_t time, cons enum hrtimer_mode mode);

mode represents the expire mode. It should be HRTTIMER_MODE_ABS for an absolute time value, or HRTIMER_MODE_REL for a time value relative to now.

3. hrtimer cancellation: You can either cancel the timer or see whether it is possible to cancel it or not:

int hrtimer_cancel(struct hrtimer *timer);

int hrtimer_try_to_cancel(struct hrtimer *timer);

Both return 0 when the timer is not active and 1 when the timer is active. The difference between these two functions is that hrtimer_try_to_cancel fails if the timer is active or its callback is running, retruning -1, whereas hrtimer_cancel will wait until the callback finishes.

We can independently check whether the hrtimer's callback is still running with the following:

int hrtimer_callback_running(struct hrtimer *timer);

Remember hrtimer_try_to_cancel internally calls hrtimer_callback_running.

In order to prevent the timer from automatically restarting, the hrtimer callback function must return HRTIMER_NORESTART.

You can check wheter HRTs are available on your system by doing the folowing:

• By looking in the kernel config file, which should contain something like CONFIG_HIGH_RES_TIMERS=y.

$ zcat /proc/configs.gz | grep CONFIG_HIGH_RES_TIMERS

• By loking at the cat /proc/timer_list | grep resolution results. The .resolution entry must show 1 nsecs and the event_handler must show hrtimer_interrupts.
• By using the clock_getres system call.
• From within the kernel code, by using:

#ifdef CONFIG_HIGH_RES_TIMERS

With HRTs enabled on your system, the accurate of sleep and timer system calls do not depend on jiffies any more, but they are still as accurate as HRTs are. It is the reason why some systems do not support nanosleep(), for example.

Example:

/**

 * @file hrtimer.c

 * @author  Oscar Gomez Fuente <oscargomezf@gmail.com>

 * @ingroup iElectronic

 * @version $Rev$

 * @date $Date$

 * @section DESCRIPTION

 *    Kernel Linux example with high resolution timers

 */

#include <linux/init.h>

#include <linux/kernel.h>

#include <linux/module.h>

#include <linux/hrtimer.h>

#include <linux/ktime.h>

unsigned long timer_interval_ns = 1000 * 1E6;

static struct hrtimer my_hrtimer;

enum hrtimer_restart timer_callback(struct hrtimer *timer_for_restart)

{

    ktime_t currtime;

    ktime_t interval;

    currtime  = ktime_get();

    interval = ktime_set(0, timer_interval_ns); 

    hrtimer_forward(timer_for_restart, currtime, interval);

    pr_info("[INFO] timer_callback every 1000 msec\n");

    return HRTIMER_RESTART;

}

static int __init my_init(void)

{

    ktime_t ktime;

    pr_info("[INFO] Timer module loaded\n");

    ktime = ktime_set(0, timer_interval_ns);

    hrtimer_init(&my_hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);

    my_hrtimer.function = &timer_callback;

    hrtimer_start(&my_hrtimer, ktime, HRTIMER_MODE_REL);

    return 0;

}

static void __exit my_exit(void)

{

    int ret;

    ret = hrtimer_cancel(&my_hrtimer);

    if (ret)

       pr_info("[INFO] The timer was still in use...\n");

    pr_info("[INFO] HR Timer module uninstalling\n");

    pr_info("[INFO] Timer module unloaded\n");

}

module_init(my_init);

module_exit(my_exit);

MODULE_LICENSE("GPL");

MODULE_DESCRIPTION("HRTimer example");

MODULE_AUTHOR("Oscar Gomez Fuente <oscargomezf@gmail.com>");

Dynamic tick/tickless kernel

With previous HZ options, the kernel is interrupted HZ timesper second in order to reschedule tasks, even in an idle state. If HZ is set to 1000, there will be 1000 kernel interruptions per second, preventing the CPU from being idle for a long time, thus affecting CPU power consumption.

Now let's look at a kernel with fixed or predefined ticks, where the ticks are disabled until some task need to be performed. We call such a kernel a ticklees kernel. In fact, tick activation is scheduled, based on the next action. This right name should be dynamic tick kernel. The kernel is responsible for task scheduling, ann matains a list of runnable tasks (the run queue) in the system. When here is no task to schedule, the scheduler switches to idle thread, which enables dynamic tick by disabling the peiodic tick until the next timer expires (a new task is queued for processing).

Delays and sleep in he kernel

There are two types of delays, depending on the context your code runs in: atomic or nanotomic. The mandatory header to handle delays in the kernel is #include <linux/delay.h>.

Atomic context

Tasks in the atomic context (such as ISR) can't sleep, and can't be scheduled; it is the reason why busy-waits loops are used for delaying purpose in an atomic context. The kernel exposes the Xdelay family of functions that will spend time in a busy loop, long (based on jiffies) enough to achieve the desried delay:

• ndelay(unsigned long nsecs).
• udelay(unsigned long usecs).
• mdelay(unsigned long msecs).

Nanoatomic context

In a nanoatomic context, the kernel provides the sleep[_range] family of functions and which function to use depends on how long you need to delay by:

• udelay(unsigned long usecs): Busy-wait loop based. You should use this function if you need to sleep for a few micro-seconds (<~10).
• usleep_range(unsigned long min, unsigned long max): Relies on hrtimers, and it is recommendable to let this sleep for a few ~ microsenconds or small mseconds (10 us - 20 ms), avoiding the busy-wait loop of udelay().
• msleep(unsigned long msecs): Backed by jiffies/legacy_timers. You should use this for larger, msecs sleep (10 ms+).

Kernel locking mechanism