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 the ability to use it in userspace. For example, create a queue - a data structure with access to the elements according to the “first come, first come out” principle 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 start and end of the queue structure will be done by fifo_init and fifo_exit, respectively. The second argument, fifo_init, is the function that will be called when the queue is completed. This function is used to release the memory occupied by the buffer element when completing work with the buffer.

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

To perform single-type operations on queue elements, use fifo_for_each. The second argument is the function that implements the requested operation. The following is a possible implementation.

Fifo.c file:

 #include <stdlib.h> #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 fifo_init initializes the “head” of the list: INIT_LIST_HEAD (& (fifo-> headlist)), sets the zero length and method for clearing the memory when quitting.

In the fifo_exit, a “protected” passage is performed on all elements of the list. For each element of the queue, the memory allocated for the data is released, after which the element is removed from the list, and the memory it occupied is released.

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 the 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. The item is then removed from the list, and the memory it used is released. The queue length is reduced accordingly.

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

This example uses mydata_free, which serves to free up memory allocated for the data of the queue element, and also mydata_print, a function that displays the elements of the queue on the screen. The data type is float in the mydata structure.

Main.c file:

 #include <stdlib.h> #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 a buffer.

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)