list_for_each and list_entry

The linux kernel provides a lot of macros to help us iterate through the list of processes running in the system.
The task_struct structure of all the processes running in the system are stored as a circular doubly linked list and there are number of macros/functions available which help us iterate through this list.

In this post we will look at the use of list_for_each and list_entry to iterate through the list. These two functions are generic functions for linked list in the kernel, we use them in this example to iterate through the list of proceeses.  These macros and functions are defined in linx/list.h

list_for_each("argument1","argument2") : Where argument1 is a temporary variable of type  "list_head" which will hold the current value of the list.
argument2 is agian a variable of type "list_head" but this is the head node of the list which has to be traversed.
list_head is the data type used when making use of the linked list provided in the kernel.

list_entry(ptr,type,member): This is macro uses the container_of() macro to return a pointer to the structure "type" that contains "member" which is of the type "ptr"

The code below creates a proc entry "ps_list". Which when read, lists out the siblings of the grandparent of the current process .

task = current->parent->parent   returns the grandparent of the current process which is assigned to "task"

list_for_each(list,&task->sibling): In this loop the siblings of "task" are repeatedly assigned to "list".

Each sibling will be located in its own task_stuct and to get the name of the sibling we need to know the address of the structure in which the sibling resides. Hence we used the "list_entry " macro as follows

task1=list_entry(list,struct task_struct,sibling); 

The above call, returns the pointer to the structure "task_struct" that contains the "sibling".

Once the pointer to task_struct is known, we can print the process  name and process id using
task1->comm and task1->pid.


**********************************************proc_list_entry.c***********************
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/proc_fs.h>
#include<linux/sched.h>




int read_proc(char *buf,char **start,off_t offset,int count,int *eof,void *data ) 
{
int len=0;
struct task_struct *task, *task1;
struct list_head *list;
task = current->parent->parent;
printk(KERN_INFO "%s", task->comm);


list_for_each(list,&task->sibling) {


task1=list_entry(list,struct task_struct,sibling);
       len  += sprintf(buf+len, "\n %s %d \n",task1->comm,task1->pid);
  }


   
return len;
}


void create_new_proc_entry() 
{
create_proc_read_entry("ps_list",0,NULL,read_proc,NULL);


}




int functn_init (void) {
int ret;

create_new_proc_entry();
return 0;
}


void functn_cleanup(void) {
printk(KERN_INFO "In cleanup");
remove_proc_entry("ps_list",NULL);
}


MODULE_LICENSE("GPL");
module_init(functn_init);
module_exit(functn_cleanup);
******************************************************************************


**********************makefile*******************************************
KERNELDIR ?= /lib/modules/$(shell uname -r)/build 
obj-m := proc_list_entry.o
PWD := $(shell pwd)
all:
make -C $(KERNELDIR) M=$(PWD) modules
clean:
rm *.o *.mod.c *.order *.markers
********************************************************************

Run the following commands to see the output


$ make
$ sudo insmod proc_list_entry.ko 
$ cat /proc/ps_list 

You shuold be able to see a list of process names and their "pids".

You can verify the ouput by comparing it with the output of the command "pstree" which gives a tree structure output of all the processes
in the system.

Overview of compiling Kernel Modules

Here is look in the steps involved in compilation of a kernel module, the journey from the .c file to the .ko .

The makefile that is used to build kernel module generally looks a follows.



*******************************makefile*****************************************

ifneq ($(KERNELRELEASE),)
   obj-m := modulename.o
else

KERNELDIR ?= /lib/modules/$(shell uname -r)/build

PWD := $(shell pwd)

default:
    $(MAKE) -C $(KERNELDIR) M=$(PWD) modules 
endif

***********************************************************************************
The 2.6 kernels use a kbuild system to build the kernel modules and to compile an external module also the same has to be used. Hence in the makefile that we write we will have to use the makefile that is present in the kernel source tree.

Two passes are made of the above makefile, in the first pass we call make from the command line. As we are not sure about the location of the kernel source  tree location the first "if" condition turns out to be false and in the else part we set the KERNELDIR to the path to the makefile of the kernel which is by default present in the location /lib/modules/"kernel version"/build.
and then call make again.
note :  uname -r retunrs the kernel version.

The default target gets called if we do not mention any target in the command line.
Here we call make again, but with  the option -C to tell "make" to use the makefile present in the directory being passed as argument after -C, which is the path to kernel makefile.
The M option tells the kernel makefile that we are building external kernel modules and the same are present at the location passed as an absolute path after "M". 
The target "modules" is passed to mean that modules located in the currnet directory have to be compiled. The default working is also the same and hence should work even if it is not passed.

The second pass of the makefile is done by the kbuild system which reads only the assignment of "obj-m := modulename.o"  from the makefile.

Now the kbuild system know that it has to build "modulename.ko" and will look for "modulename.c" or "modulename.S" for the source. In case these files are not persent in the directory passed to "M" , the compiling will stop with an error.

If the files are present the source file is compiled to a "modulname.o",  and "modulename.mod.c" is created which is compiled to "modulename.mod.o".
The modulename.mod.c is a file that basically contains the information about the module (Version information etc).
The modulename.o and the modulename.mod.o are linked together by modpost in the next stage to create the "modulename.ko" .

A few other files that get created are
"module.symvers": This will contain any of external symbols that is defined in your module and hence not present in the module.symvers of the kernel .

"modules.order" : In case you are compiling multiple modules together, it will list out the order in which the compilation and creation of .ko takes

"module.markers" : This lists out all the markers placed in the your module code. A marker placed in code provides a hook to call a function (probe)   that you can provide at runtime

Script to Compare two files line by line

Here is a script to compare two files line by line. The script compares two files that are given as input on the command line and outputs only the lines that are different between the two files .
It sure is not the most optimal script, but it works :-)

For eg let us take these two files
file1:

123
456
789

file2:
123
456
432


Save the above script as compare.sh and give execute permission to the script

$ chmod +x compare.sh

Run the script as follows.

$ ./compare.sh file1 file2
output :
Differing lines are
789
432

*****************************************compare.sh*******************
#!/bin/bash
if [ $# -ne 2 ]; then
    echo " Usage compare fil1 file2"
    exit
fi
      

i=0
while read line1
do
        flag=1
   while read line2
   do

    if [ "$line1" == "$line2" ];  then
        flag=0
        fi

   done < $2
        if [ $flag -eq 1 ]; then
             lines[i]=$line1
        ((i++))
    fi
done < $1

while read line1
do
        flag=1
   while read line2
   do

    if [ "$line1" == "$line2" ];  then
        flag=0
        fi

   done < $1
        if [ $flag -eq 1 ]; then
             lines[i]=$line1
         ((i++))
    fi
done < $2

echo "Differing lines are"
for((j=0;j<i;j++))
do
echo ${lines[j]}
done

*********************************************************************

using "for_each_process" in proc entry

The linux kernel, as any other system, has a lot of proccesses running at any given time.

The task_struct structure defined in sched.h stores all the details of every process that exists in the system, and all the processes in turn are stored in a circular double linked list.

Just to undertand the how to access the fields of task_struct and iterate through the various tasks in the system, here is a simlple module that creates a proc entry which when read, lists out all name and pid of all the processes running currently.

The code makes use of a macro called "for_each_process" which is defined in "linux/sched.h". This function iterate through the list of all the processes. #include<linux/module.h> #include<linux/kernel.h> #include <linux/proc_fs.h> #include<linux/sched.h> int read_proc(char *buf,char **start,off_t offset,int count,int *eof,void *data ) { int len=0; struct task_struct *task_list; for_each_process(task_list) { len += sprintf(buf+len, "\n %s %d \n",task_list->comm,task_list->pid); } return len; } void create_new_proc_entry() { create_proc_read_entry("ps_list",0,NULL,read_proc,NULL); } int functn_init (void) { int ret; create_new_proc_entry(); return 0; } void functn_cleanup(void) { remove_proc_entry("ps_list",NULL); } MODULE_LICENSE("GPL"); module_init(functn_init); module_exit(functn_cleanup);

In the read_proc function, "for_each_process" is called, which assigns to the variable task_list, which is of the kind "struct task_struct", the task_struct structure of one process after another as they are stored in the linked list in the kernel.

The task_list in turn is used to print the name ,task_list->comm, and the pid, task_list->pid of the process.

To see the output use the following makefile.

KERNELDIR ?= /lib/modules/$(shell uname -r)/build obj-m := proces_listdo.o PWD := $(shell pwd) all: make -C $(KERNELDIR) M=$(PWD) modules clean: rm *.o *.mod.c *.order *.markers

Run the following commands

$ make $sudo insmod process_list.ko $ cat /proc/ps_list
In the output you should see a list of process names and their pids for eg.

init 1 kthreadd 2 migration/0 3 ksoftirqd/0 4 watchdog/0 5 events/0 6 khelper 7

To understand about proc entries and creating proc entries you can refer to the posts "Creating proc entry"

Kernel Thread Creation - 3

In  the previous posts about kernel threads, the threads that we created exited by themselves and there was no need to call kthread_stop .
Let us look at an example where we will make the thread wait as long as kthread_stop is not called.

Once the job of the thread is done, if we want the thread to wait until kthread_stop is called, we need to make use of kthread_should_stop call. This function keep polling for kthread_stop and returns "TRUE" only when kthread_stop is called.
Hence in our example code we will change the state of the thread from "RUNNING" to "TASK_INTERRUPTIBLE" once our job is over and keep waiting in a loop as long as kthread_stop is not called.

The only difference will be the addition of the following code in the function that executes as the thread

set_current_state(TASK_INTERRUPTIBLE);
while (!kthread_should_stop())
{
   schedule();
   set_current_state(TASK_INTERRUPTIBLE);
}
set_current_state(TASK_RUNNING);

The schedule is used to let the processor do some thing else while this thread waits for the call. But the kernel will schedule this thread again at some time, when the state of the thread will become "RUNNING". Thus before calling schedule again we change the state to TASK_INTERRUPTIBLE .
Hence the modified thread_fn function looks as follows , the rest of the code is same as in Kernel Threads -1

#################################################
int thread_fn() {

unsigned long j0,j1;
int delay = 60*HZ;
j0 = jiffies;
j1 = j0 + delay;

while (time_before(jiffies, j1))
        schedule();
printk(KERN_INFO "In thread1");


set_current_state(TASK_INTERRUPTIBLE);
while (!kthread_should_stop())
{
   schedule();
   set_current_state(TASK_INTERRUPTIBLE);
}
set_current_state(TASK_RUNNING);

return 0;
}

###################################################