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

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

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

struct k_list { struct list_head queue_list; char *data; };

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.

int queue_init (void) { create_new_proc_entry(); head=kmalloc(sizeof(struct list_head *),GFP_KERNEL); INIT_LIST_HEAD(head); emp_len=strlen(empty); return 0; }

create_new_proc_entry: Function for creation of the proc entry.

void create_new_proc_entry(void) { proc_create("queue",0,NULL,&proc_fops); }

INIT_LIST_HEAD(head) : Initalizing the linked head pointer of the linked list.

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

struct file_operations proc_fops = { read: pop_queue, write: push_queue };

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.

int push_queue(struct file *filp,const char *buf,size_t count,loff_t *offp) { msg=kmalloc(10*sizeof(char),GFP_KERNEL); temp=copy_from_user(msg,buf,count); node=kmalloc(sizeof(struct k_list *),GFP_KERNEL); node->data=msg; list_add_tail(&node->queue_list,head); return count; }

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.

int list_empty(const struct list_head *head)

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.

list_first_entry(ptr, type, member)

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. int pop_queue(struct file *filp,char *buf,size_t count,loff_t *offp ) { if(list_empty(head)){ msg=empty; if(flag==1) { ret=emp_len; flag=0; } else if(flag==0){ ret=0; flag=1; } temp=copy_to_user(buf,msg, count); printk(KERN_INFO "\nStack empty\n"); return ret; } if(new_node == 1) { node=list_first_entry(head,struct k_list ,queue_list); msg=node->data; ret=strlen(msg); new_node=0; } if(count>ret) { count=ret; } ret=ret-count; temp=copy_to_user(buf,msg, count); printk(KERN_INFO "\n data = %s \n" ,msg); if(count==0) { list_del(&node->queue_list); new_node=1; } return count; }

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

#include <linux/module.h>#include <linux/kernel.h>#include <linux/proc_fs.h>#include<linux/sched.h>#include <asm/uaccess.h>#include <linux/slab.h> int len,temp,i=0,ret; char *empty="Queue Empty \n"; int emp_len,flag=1; struct k_list { struct list_head queue_list; char *data; }; static struct k_list *node; struct list_head *head; struct list_head test_head; int new_node=1; char *msg; int pop_queue(struct file *filp,char *buf,size_t count,loff_t *offp ) { if(list_empty(head)){ msg=empty; if(flag==1) { ret=emp_len; flag=0; } else if(flag==0){ ret=0; flag=1; } temp=copy_to_user(buf,msg, count); printk(KERN_INFO "\nStack empty\n"); return ret; } if(new_node == 1) { node=list_first_entry(head,struct k_list ,queue_list); msg=node->data; ret=strlen(msg); new_node=0; } if(count>ret) { count=ret; } ret=ret-count; temp=copy_to_user(buf,msg, count); printk(KERN_INFO "\n data = %s \n" ,msg); if(count==0) { list_del(&node->queue_list); new_node=1; } return count; } int push_queue(struct file *filp,const char *buf,size_t count,loff_t *offp) { msg=kmalloc(10*sizeof(char),GFP_KERNEL); temp=copy_from_user(msg,buf,count); node=kmalloc(sizeof(struct k_list *),GFP_KERNEL); node->data=msg; list_add_tail(&node->queue_list,head); return count; } struct file_operations proc_fops = { read: pop_queue, write: push_queue }; void create_new_proc_entry(void) { proc_create("queue",0,NULL,&proc_fops); } int queue_init (void) { create_new_proc_entry(); head=kmalloc(sizeof(struct list_head *),GFP_KERNEL); INIT_LIST_HEAD(head); emp_len=strlen(empty); return 0; } void queue_cleanup(void) { remove_proc_entry("queue",NULL); } MODULE_LICENSE("GPL"); module_init(queue_init); module_exit(queue_cleanup);

To compile the module use the make file.

ifneq ($(KERNELRELEASE),) obj-m := queue_list.o else KERNELDIR ?= /lib/modules/$(shell uname -r)/build PWD := $(shell pwd) default: $(MAKE) -C $(KERNELDIR) M=$(PWD) modules clean: $(MAKE) -C $(KERNELDIR) M=$(PWD) clean endif

Compile and insert the module into the kernel

$ make $ insmod stack_list.ko

To see the output

$ echo "1" > /proc/queue $ echo "2" > /proc/queue $ echo "3" > /proc/queue $ echo "4" > /proc/queue 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 $ cat /proc/queue 1 $ cat /proc/queue 2 $ cat /proc/queue 3 $ cat /proc/queue 4 $ cat /proc/queue Queue Empty