Как использовать список ядра Linux для создания очереди

Приветствую!

В данной статье рассматривается использование реализации двусвязного списка ядра Linux.

Двусвязный список в ядре Linux реализован в файле include/linux/list.h. Мы будем использовать адаптированный вариант list.h [1], который отличается от оригинального возможностью использовать его в userspace. Например, создадим очередь — структуру данных с доступом к элементам по принципу «первый пришёл — первый вышел» для произвольного типа данных на основе list.h.

Для этого создаем структуру очереди и структуру элемента очереди:

Файл 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

Начало и завершение работы со структурой очереди будет производится соответственно fifo_init и fifo_exit. Второй аргумент fifo_init — это функция, которая будет вызываться при завершении работы с очередью. Данная функция служит для освобождения памяти, занимаемой элементом буфера, при завершении работы с буфером.

Добавление и извлечение данных производится при помощи fifo_push и fifo_pop соответственно. Данные в очереди хранятся по указателю, который передается вторым аргументом fifo_push, и возвращается fifo_pop.

Для выполнения однотипных операций над элементами очереди служит fifo_for_each. Вторым аргументом передается функция, реализующая требуемую операцию. Ниже приведена возможная реализация.

Файл fifo.с:

#include &ltstdlib.h&gt

#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;
}

В fifo_init инициализируется «голова» списка: INIT_LIST_HEAD(&(fifo->headlist)), устанавливается нулевая длина и метод для очистки памяти при завершении работы с очередью.

В fifo_exit производится «защищенный» проход по всем элементам списка. Для каждого элемента очереди производится освобождение памяти, выделенной под данные, после чего элемент удаляется из списка, а память, которую он занимал, освобождается.

В fifo_push выделяется память под элемент списка. Если эта операция произведена успешно, в элементе очереди сохраняется указатель на данные и элемент добавляется в хвост списка. Длина очереди, соответственно, увеличивается.

В fifo_pop сначала находится первый элемент очереди. Если список не пуст и такой элемент найден, сохраняется указатель на данные. Затем элемент удаляется из списка, а память, которую он использовал, освобождается. Длина очереди, соответственно, уменьшается.

Чтобы использовать эту реализацию очереди для некоторой произвольной структуры данных, необходимо создать метод free для освобождения памяти данных элемента при завершении работы с буфером, а также метод для типовой операции над элементами буфера, если он требуется.

В данном примере используются mydata_free, который служит для освобождения памяти, выделенной под данные элемента очереди, а также mydata_print — функция, которая выводит элементы очереди на экран. В качестве данных выступает тип float в структуре mydata.

Файл main.с:

#include &ltstdlib.h&gt

#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;
}

Функция main содержит тестовые операции с буфером.

Результат работы:

$ ./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

Используемые источники

1.Linux Kernel Linked List Explained (русский перевод)