Implementing stack using the list functions in kernel

In the posts "Creating a linked list in linux kernel" and "Using list_del to delete a node" saw how to use the in built functions of a kernel to build a linked list. One of the main applications of linked list could be the implementation of stack. In this post, let us make use of the list functions available in the kernel to implement a stack.

A stack, as we know, is a data structure that stores elements in the order of first in last out. So when ever we write or push data into the stack, the data needs to be added as a node at the end of the list and when we read data from the stack we need to read data from the last node of the list and then delete the corresponding node. To implement a stack using a list, we need to keep track of the last element that gets inserted into the list, because when ever we need to read from the stack we need to return the data stored in the last node.

To implement the stack operation using list functions, we will make use of the function

void list_add(struct list_head *new, struct list_head *head)

Where
new: The new node to be added to the list
head: Is the node after which the new node has to be added.
If we have to implement a linked list from scratch we would have had to take care of all the pointer manipulations when inserting data into the list or removing data from the list. But as we have the required help, as built in functions, all we need to do is call the right function with the right arguments.

To show the operation of a stack we will make use of a proc entry. We will create proc entry named as "stack" and make it behave as a stack. We will use the following structure as the node

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

test_list: Will be used to create the linked list using the built in functions of kernel
data: To hold the data of the list.

The first thing we will have to do, to implement a stack using proc entry is create a linked list and create a proc entry in the init function.

int stack_init (void) { create_new_proc_entry(); INIT_LIST_HEAD(&test_head); tail=&test_head; emp_len=strlen(empty); return 0; }

create_new_proc_entry : Function to create a new proc entry.

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

INIT_LIST_HEAD: Initialize the linked list with the head node as test_head.

tail=&test_head; : With no data in the stack the tail and the head point to the same node.

emp_len=strlen(empty): "empty" is the message to the printed when the stack is empty and strlen returns the length of the string.

Once the initialization is done we need to associate the functions for push, writing data to stack and pop, reading data from stack.

struct file_operations proc_fops = { read: pop_stack, write: push_stack };

Now we need to implement the functions pop_stack and push and stack.

push_stack:

int push_stack(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(&node->test_list,tail); cnt++; tail=&(node->test_list); return count; }

msg=kmalloc(10*sizeof(char),GFP_KERNEL): allocate memory for the data to be received from the user space.
temp=copy_from_user(msg,buf,count): copy the data from user space into the memory allocated
node=kmalloc(sizeof(struct k_list *),GFP_KERNEL): Allocate a new node.
node->data=msg: Assign the data received to the node.
list_add(&node->test_list,tail): Add the new node to the list. Note that we are passing the node after which the new node has to be added as tail. This makes sure that the list behaves as a stack.
cnt++: Increase the count of nodes that are present in the list.
tail=&(node->test_list): Change the node to point to the new node of the list. Note that we are assigning the address of test_list to tail and not the address of the node.

pop_stack:

int pop_stack(struct file *filp,char *buf,size_t count,loff_t *offp ) { if(cnt == 0 ){ 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=container_of(tail,struct k_list ,test_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) { tail=((node->test_list).prev); list_del(&node->test_list); cnt--; new_node=1; } return count; }

In the pop operation we pop the last element inserted into the stack and then delete the node. According to the push_stack function, the variable tail points to the last element inserted into the stack.

According the standard practice followed in the the kernel, the read operation has to return the number of bytes of data transfered to the user space and user space functions continue to read as long as they do not get a 0 as return value indicating end of the read operation.

To make the proc entry work as a stack, we need to make sure that every read operation return only one node. To ensure this, in the above code we have used a variables new_node and flag, which after returning the data of one node or empty stack, respectively, makes the return value to 0, which ensures the read is terminated.

While popping data out of stack, we need to first check if the stack has data in it. This is done by comparing tail with test_head. If test is pointing to test_head it means the stack is empty and we return the string "Stack Empty". This is implemented by following piece of code

if(tail == &test_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; }

On the other hand if stack has data in it.

if(new_node == 1) { node=container_of(tail,struct k_list ,test_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) { tail=((node->test_list).prev); list_del(&node->test_list); cnt--; new_node=1; } return count; }

node=container_of(tail,struct k_list ,test_list): Get the pointer to the node which has the tail, last node of the list, as its member.
msg=node->data : Assign the data in the node to msg
ret=strlen(msg): Get the length of data to be transfered.
new_node=0: set new_node to 0, to indicate one node has been read. if(count>ret) { count=ret; } ret=ret-count;

Set count value to sting length, if count is larger than string length and reduce the variable ret by count value.
ret become 0 when ever the count valur is greater than ret.
temp=copy_to_user(buf,msg, count): Copy msg to user space.
if(count==0) { tail=((node->test_list).prev); list_del(&node->test_list); cnt--; new_node=1; }

Once all the data from the node has been transferred count becomes 0, not we need to change the tail to point to the node previous to the current node.

tail=((node->test_list).prev): Assign to tail the address of test_list of previous node.
list_del(&node->test_list): delete the node from the list.
new_node=1: Set new_node to 1 for the read of next node.

The full code for the kernel module looks as below.

stack_list.c

int len,temp,cnt,i=0,ret; char *empty="Stack Empty \n"; int emp_len,flag=1; struct k_list { struct list_head test_list; char *data; }; static struct k_list *node; struct list_head *tail; struct list_head test_head; int new_node=1; char *msg; int pop_stack(struct file *filp,char *buf,size_t count,loff_t *offp ) { if(tail == &test_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=container_of(tail,struct k_list ,test_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) { tail=((node->test_list).prev); list_del(&node->test_list); cnt--; new_node=1; } return count; } int push_stack(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(&node->test_list,tail); cnt++; tail=&(node->test_list); return count; } struct file_operations proc_fops = { read: pop_stack, write: push_stack }; void create_new_proc_entry(void) { proc_create("stack",0,NULL,&proc_fops); } int stack_init (void) { create_new_proc_entry(); INIT_LIST_HEAD(&test_head); tail=&test_head; emp_len=strlen(empty); return 0; } void stack_cleanup(void) { remove_proc_entry("stack",NULL); } MODULE_LICENSE("GPL"); module_init(stack_init); module_exit(stack_cleanup);

To compile the module use the make file.

ifneq ($(KERNELRELEASE),) obj-m := stack_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/stack $ echo "2" > /proc/stack $ echo "3" > /proc/stack $ echo "4" > /proc/stack

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/stack 4 $ cat /proc/stack 3 $ cat /proc/stack 2 $ cat /proc/stack 1 $ cat /proc/stack Stack Empty

Thus we can see that the proc entry is operating as a stack.

Related posts

Implementing stack using the list functions in kernel-2
Creating a read write proc entry in kernel versions above 3.10
Pointer to structure from its member pointer: container_of