Search

Creating a queue in linux kernel using list functions

In the post we saw how to create a stack using the list functions. In this post let us use the same list functions to implement a queue.

As we know a queue is a data structure that stores data in the first in first out order. That is the data that is entered first is read out first.

To create a queue using the list functions we can make use of the function list_add_tail



new: The new node to be added
head: Pointer to node before which the new node has to be added.

To make the list work as a queue we need keep inserting every new node before the head node, that is at the tail end of the list and when we read the list, we read from the front end. Thus the entry that is added first will be accessed first.

To demonstrate the operation of queue we will create a proc entry called as queue make it work like a queue.

To create the queue we will use the structure



queue_list : Used to create the linked list using the list functions.
data: Will hold the data to be stored.

In the init function we need to first create the proc entry and then intialize the linked list that we will be using for the queue.



create_new_proc_entry: Function for creation of the proc entry.





Next we need to define the file operations for the proc entry. To manipulate the queue we need two operations push and pop.



The function push_queue will be called when data is written into the queue and pop_queue will be called when data is read from the queue.

In push_queue we will use the function list_add_tail to add every new node behind the head.



In the function pop_queue, before attempting to read the queue, we need to ensure that the queue has data. This can be done using the function list_empty.



Which returns true if the list is empty.

In case the list is not empty, we need to pop out the first data from the list which can be done using the function list_first_entry.



ptr: Pointer to the head node of the list.
type: type of structure of which the head is member of
member: The name of the head node in the structre.
Thus the pop function will look as below.

The flag and the new_node are variables used to ensure that only one node is returned on every read of hte proc entry. The read function from user space will continue to read the proc entry as long as the return value is not zero. In the first pass,new_node=0, we will return the number of bytes of data transfered from one node and in the second pass,new_node=0, we will return 0 to terminate the read. Thus making sure that on every read data of exactly one node is returned. The flag variable works in the similar fashion when the queue is empty to return the string "Queue empty".

Thus the full code of queue will be



To compile the module use the make file.



Compile and insert the module into the kernel



To see the output

Thus we have written the 1,2,3,4 as data into 4 nodes with 4 being inserted last. Now to pop data out of the stack

No comments:

Post a Comment