How to use the Linux kernel list to create a queue

Greetings!

This article discusses the use of the implementation of the doubly linked list of the Linux kernel.

A doubly linked list in the Linux kernel is implemented in the include / linux / list.h file . We will use an adapted version of list.h [1], which differs from the original one in using userspace. For example, create a queue - a data structure with access to elements on a first-come-first-out basis for an arbitrary data type based on list.h.

To do this, create a queue structure and a queue element structure:

File fifo.h:

#ifndef FIFO_H
#define FIFO_H
#include "list.h"
struct fifo_item
{
    void* data;             // указатель на произвольные данные
    struct list_head list;  // структура двусвязного списка
};
struct fifo
{
    struct list_head headlist;              // двусвязный список
    int length;                             // длина
    void (*item_free)(struct fifo_item*);   // метод освобождения памяти при удалении элемента
};
// создание и удаление
int fifo_init(struct fifo * fifo, void (*item_free)(struct fifo_item*));
int fifo_exit(struct fifo * fifo);
// добавление и извлечение данных
int fifo_push(struct fifo * fifo, void* data);
void* fifo_pop(struct fifo * fifo);
// операция над каждым элементом
int fifo_for_each(struct fifo * fifo, void (*func)(struct fifo_item*));
#endif

The beginning and completion of work with the queue structure will be made by fifo_init and fifo_exit, respectively. The second argument to fifo_init is the function that will be called when the queue is completed. This function is used to free the memory occupied by the buffer element upon completion of work with the buffer.

Adding and retrieving data is done using fifo_push and fifo_pop, respectively. The data in the queue is stored by the pointer, which is passed by the second argument of fifo_push, and fifo_pop is returned.

Fifo_for_each is used to perform operations of the same type on queue elements. The second argument is the function that implements the required operation. The following is a possible implementation.

Fifo.s file:

#include 
#include "fifo.h"
int fifo_init(struct fifo *fifo, void (*item_free)(struct fifo_item*))
{
    INIT_LIST_HEAD(&(fifo->headlist));
    fifo->length = 0;
    fifo->item_free = item_free;
    return 0;
}
int fifo_exit(struct fifo* fifo)
{
    int res = 0;
    struct list_head *pos, *q;
    struct fifo_item* item;
    list_for_each_safe(pos, q, &(fifo->headlist))
    {
        item = list_entry(pos, struct fifo_item, list);
        fifo->item_free(item);
        list_del(pos);
        free(item);
    }
    return res;
}
int fifo_push(struct fifo* fifo, void* data)
{
    int res = -1;
    struct fifo_item* item;
    item = (struct fifo_item*)malloc(sizeof(struct fifo_item));
    if(NULL != item)
    {
        item->data = data;
        list_add_tail(&(item->list), &(fifo->headlist));
        fifo->length++;
    }
    return res;
}
void* fifo_pop(struct fifo* fifo)
{
    void* res = NULL;
    struct fifo_item* item = list_entry(fifo->headlist.next, struct fifo_item, list);
    if(!list_empty(&(fifo->headlist)))
    {
        res = item->data;
        list_del(&(item->list));
        free(item);
        fifo->length--;
    }
    return res;
}
int fifo_for_each(struct fifo* fifo, void (*func)(struct fifo_item*))
{
    int res = 0;
    struct fifo_item* item;
    list_for_each_entry(item, &(fifo->headlist), list)
    func(item);
    return res;
}

The head of the list is initialized in fifo_init: INIT_LIST_HEAD (& (fifo-> headlist)), the length is set to zero, and the method for clearing memory at the end of the queue is set.

Fifo_exit makes a “protected” pass through all elements of the list. For each element of the queue, the memory allocated for the data is released, after which the element is deleted from the list, and the memory that it occupied is freed.

In fifo_push, memory is allocated for the list item. If this operation is successful, a pointer to the data is stored in the queue element and the element is added to the tail of the list. The length of the queue, respectively, increases.

In fifo_pop, the first element of the queue is located first. If the list is not empty and such an element is found, a pointer to the data is stored. Then the item is removed from the list, and the memory that it used is freed. The length of the queue, respectively, is reduced.

To use this queue implementation for some arbitrary data structure, you need to create a free method to free the data memory of the element when you finish working with the buffer, as well as a method for a typical operation on buffer elements, if required.

In this example, mydata_free is used, which is used to free the memory allocated for the data of the queue element, as well as mydata_print - a function that displays the elements of the queue on the screen. The data is the float type in the mydata structure.

Main.c file:

#include 
#include "fifo.h"
struct mydata
{
    float value;
};
void* mydata_create(void)
{
    return (struct mydata *)malloc(sizeof(struct mydata));
}
void mydata_free(struct fifo_item* item)
{
    free(item->data);
}
void mydata_print(struct fifo_item* item)
{
    struct mydata* data = (struct mydata*)item->data;
    printf("item: %f\n", data->value );
}
int main()
{
    int i;
    struct fifo myfifo;
    struct mydata* newdata;
    // начало работы с FIFO
    fifo_init(&myfifo, mydata_free);
    for(i = 0; i < 10; i++)
    {
        // новые данные
        newdata = mydata_create();
        if(!newdata)
        {
            return -1;
        }
        newdata->value = (float)i*0.1;
        // добавляем в FIFO
        fifo_push(&myfifo, newdata);
    }
    // печать данных
    printf("FIFO:\n");
    fifo_for_each(&myfifo, mydata_print);
    printf("\n");
    do
    {
        newdata = fifo_pop(&myfifo);
        if(newdata)
        {
            printf("pop: %f\n", newdata->value );
        }
        if(myfifo.length == 5)
        {
            printf("\nFIFO:\n");
            fifo_for_each(&myfifo, mydata_print);
            printf("\n");
        }
    } while(newdata);
    // конец работы с FIFO
    fifo_exit(&myfifo);
    return 0;
}

The main function contains test operations with the buffer.

The result of work:

$ ./testfifo 
FIFO:
item: 0.000000
item: 0.100000
item: 0.200000
item: 0.300000
item: 0.400000
item: 0.500000
item: 0.600000
item: 0.700000
item: 0.800000
item: 0.900000
pop: 0.000000
pop: 0.100000
pop: 0.200000
pop: 0.300000
pop: 0.400000
FIFO:
item: 0.500000
item: 0.600000
item: 0.700000
item: 0.800000
item: 0.900000
pop: 0.500000
pop: 0.600000
pop: 0.700000
pop: 0.800000
pop: 0.900000

Sources used

1. Linux Kernel Linked List Explained (Russian translation)