Wait queues

While writing modules there might be situations where one might have to wait for input some condition to occur before proceeding further. Tasks that need such behavior can make use of the sleep functionality available in the kernel.
In Linux sleeping is handled by a data structure called wait queue, which is nothing but a list of processes waiting for an input or  event. 
The post explains an example module that makes use of the concept of sleeping.

To manage a wait queue ,we need a structure of the kind wait_queue_head_t, which is defined in linux/wait.h.

Wait queue head can be initialized in the following ways
Statically using :

DECLARE_WAIT_QUEUE_HEAD(name);

Dynamically using :


wait_queue_head_t my_queue;
init_waitqueue_head(name);

Where the "name" is the name of the queue on which task  will be put to sleep.

Once the wait queue has been created, we can put a task to sleep on the queue we created using one of the following.

wait_event("queue","condition") : The task will keep waiting on the queue as long as the condition does not become true.If put to sleep using this call, the task can not be interrupted.

wait_event_interruptible("queue","condition") : similar to wait_event, but it can be interrupted by other signals too. It is always preferable to use this interruptible way of sleeping so that the task can be stopped in case the condition never becomes true.

wait_event_timeout("queue","condition","timeout") : The task will sleep on the queue until the condition becomes
true or the timeout mentioned expires, which ever occurs first. The timeout is expressed in jiffies. Task can not be interrupted before the timeout if the condition does not become true.

wait_event_interruptible_timeout("queue","condition","timeout") : Similar to wait_event_timeout but it can be interrupted.

Once a task has been put to sleep we need to wake it up , which can be done using following :

wake_up(queue)  : In case the task has been put to non interruptible sleep.
wake_up_interruptible (queue) : In case the task has been put to an interruptible sleep.

The example below is the module that we created in "Writing a character driver from scratch".
A flag has been added to the module, which is verified when the module is read by any application. If the
flag is set to "n", then the task will be put to sleep as long as the value of the flag is not changed.

The modified read looks as follows.


ssize_t read(struct file *filp, char *buff, size_t count, loff_t *offp) {
    unsigned long ret;
    printk(KERN_INFO "Inside read \n");
    wait_event_interruptible(queue, flag != 'n'); // putting to sleep if flag is equal to "n".
    printk(KERN_INFO "Woken Up");
    ret = copy_to_user(buff, char_arr.array, count); // Sending data to user space.
    return ret;
}


To change the flag the module makes use of a proc entry. We can write a character to the proc entry /proc/wait, and the same will be assigned to flag. Then the wake_up is called to wake_up the sleeping tasks.

The code for the proc entry is as follows.

int write_proc(struct file *file,const char *buffer,unsigned long count,void *data)
{
int ret=0;
printk(KERN_INFO "procfile_write /proc/wait called");
ret = __get_user(flag,buffer); // The value sent by the user is assigned to flag.
wake_up_interruptible(&queue); //wake up all the tasks waiting on the queue.
return ret;
}

Here is complete code for the module.

######################read_wait.c##############################


#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/fs.h> // required for various structures related to files liked fops.
#include <asm/uaccess.h> // required for copy_from and copy_to user functions
#include <linux/semaphore.h>
#include <linux/cdev.h>
#include <linux/proc_fs.h>
#include <linux/wait.h> // Required for the wait queues
#include <linux/sched.h> // Required for task states (TASK_INTERRUPTIBLE etc )


static int Major;
struct proc_dir_entry *Our_Proc_File;
wait_queue_head_t queue;
char flag = 'n';


struct device {
    char array[100];
    struct semaphore sem;
}char_arr;


int open(struct inode *inode, struct file *filp)
{
   
    printk(KERN_INFO "Inside open \n");
    if(down_interruptible(&char_arr.sem)) {
        printk(KERN_INFO " could not hold semaphore");
        return -1;
    }
    return 0;
}


int release(struct inode *inode, struct file *filp) {
    printk (KERN_INFO "Inside close \n");
    printk(KERN_INFO "Releasing semaphore");
    up(&char_arr.sem);
    return 0;
}


ssize_t read(struct file *filp, char *buff, size_t count, loff_t *offp) {
    unsigned long ret;
    printk("Inside read \n");
    wait_event_interruptible(queue, flag != 'n');
    printk(KERN_INFO "Woken Up");
    ret = copy_to_user(buff, char_arr.array, count);
    return ret;
}


ssize_t write(struct file *filp, const char *buff, size_t count, loff_t *offp) {   
    unsigned long ret;
    printk(KERN_INFO "Inside write \n");
    ret =    copy_from_user(char_arr.array, buff, count);
    return ret;
}






int write_proc(struct file *file,const char *buffer,unsigned long count,void *data)
{
int ret=0;
printk(KERN_INFO "procfile_write /proc/wait called");
ret = __get_user(flag,buffer);
printk(KERN_INFO "%c",flag);
wake_up_interruptible(&queue);
return ret;
}


void create_new_proc_entry()
{
Our_Proc_File = create_proc_entry("wait", 0666, NULL);
   
    if(Our_Proc_File == NULL) {
        remove_proc_entry("wait", NULL);
        printk(KERN_ALERT "Error: could not initialize /proc/wait\n");
        return -ENOMEM;
    }
    Our_Proc_File->write_proc = write_proc;
    printk(KERN_INFO "/proc/wait created \n");
   
}


struct file_operations fops = {
    read:        read,
    write:        write,
    open:         open,
    release:    release
};




struct cdev *kernel_cdev;




int char_arr_init (void) {
    int ret;
    dev_t dev_no,dev;


    kernel_cdev = cdev_alloc();   
     kernel_cdev->ops = &fops;
    kernel_cdev->owner = THIS_MODULE;
    printk (" Inside init module\n");
     ret = alloc_chrdev_region( &dev_no , 0, 1,"chr_arr_dev");
    if (ret < 0) {
        printk("Major number allocation is failed\n");
        return ret;   
    }
   
    Major = MAJOR(dev_no);
    dev = MKDEV(Major,0);
    sema_init(&char_arr.sem,1);   
    printk (" The major number for your device is %d\n", Major);
    ret = cdev_add( kernel_cdev,dev,1);
    if(ret < 0 )
    {
    printk(KERN_INFO "Unable to allocate cdev");
    return ret;
    }
    init_waitqueue_head(&queue);
    create_new_proc_entry();
    return 0;
}


void char_arr_cleanup(void) {
    printk(KERN_INFO " Inside cleanup_module\n");
    remove_proc_entry("wait",NULL);
    cdev_del(kernel_cdev);
    unregister_chrdev_region(Major, 1);
}
MODULE_LICENSE("GPL");   
module_init(char_arr_init);
module_exit(char_arr_cleanup);
#################################################################


########################Makefile####################################
ifneq ($(KERNELRELEASE),)
   obj-m := read_wait.o
else


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


PWD := $(shell pwd)


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


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




To test the example we will need a user application to read write from the device. The following can be used for the same.




###########################user_app.c#############################
#include <stdio.h>
#include <fcntl.h>




main ( ) {
        int i,fd;
        char ch, write_buf[100], read_buf[100];


        fd = open("/dev/temp", O_RDWR);


        if (fd == -1)
        {
                printf("Error in opening file \n");
                exit(-1);
        }
        printf ("Press r to read from device or w to write the device ");
        scanf ("%c", &ch); 




        switch (ch) {
                case 'w':
                       printf (" Enter the data to be written into device");
                        scanf (" %[^\n]", write_buf);
                        write(fd, write_buf, sizeof(write_buf));
                        break;
                case 'r':


                        read(fd, read_buf, sizeof(read_buf));
                        printf ("The data in the device is %s\n", read_buf);
                        break;


                default:
                        printf("Wrong choice \n");
                        break;
        }
        close(fd);
}


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




Note: To understand the module completely you can go through the post "Writing a character driver from scratch".

To check the working of the code run the following commands

$ make
$ sudo insmod read_wait.ko
$ dmesg   //   You should see the major number allocated to the module, note the  same. Assume  it is 250.
$ sudo mknod /dev/temp c 250 0
$ cc user_app.c
$ sudo ./a.out
Press r to read from device or w to write the device  w     // Writing data to the device
 Enter the data to be written into device 1234


$ sudo ./a.out
Press r to read from device or w to write the device  r  // (Now the task should go sleep)

Open another terminal and run the command

$ echo "y" > /proc/wait

Now go back to the previous terminal, the read should have woken up and displayed the contents of the that we wrote before.

Ubuntu 10.04 no login prompt

Problem: Ubuntu 10.04 boots till the login music comes but after that the login prompt does not appear.

The solutions found online for similar problems are

reconfiguring gdm
Uninstall and reinstall GDM
run fsck on the filesystem.

But none of them solved my problem .

After going through all the possible logs in the system, found a possible pointer to the problem, zlib-1.2.5
I had installed  zlib-1.2.5 from source as it was required for the qemu.
After uninstalling zlib and rebooting the system, every thing was back to normal :-). Here are the steps to be followed. 

 Once the system booted to the first screen with no login prompt

1. Hit cntrl+alt+f1 to go to the text mode login. 
2. login in the text mode with your credentials
3. change directory to where the zlib source is located
4. run the command "sudo make uninstall"
5. now reboot using "sudo reboot"

Your login prompt back, have fun :-) 

Note: This solution might or might not work for you as it depends on what caused your problem

Current Process

Linux maintains a the structure of the kind "task_struct" for every process that runs in the system. This structure defined in  "linux/sched.h".
It maintains various data of a process like the process id, name, memory related information etc.
While writing a module if we want to get information about the current process that is running in the kernel, we need to read the "task_struct" of the
corresponding process. The kernel provides a easy way to do this by providing a macro by the name "current", which always returns a pointer to the "task_struct" of the current executing process.
The implementation of the current pointer can change from one architecture to other, in the standard x86 architecture the pointer is read from the process stack Each process has a structure of the kind thread_info which is always stored at the end of the stack. The thread_info in turn has a pointer to the "task_struct" of the process. As the location of the thread_info is fixed in the stack, we can access it easily using the stack pointer and the stack size.
For eg: if the stack size is 8KB the 13 Least significant bits can be masked to get a pointer to the thread_info structure. The pointer to the "task_stuct" is obtained by dereferencing the member "task" of the structure which is the pointer to "task_struct".

Example for using the current pointer. 

Let us try to write a module that created a proc entry "process_data" and when read, it returns the information of the current process by making use of the macro current.
To learn about proc entry creation you can refer to Creating proc entry

To be able to access "current" we will need to include the file "linux/sched.h" . In the function read_proc we print the "name" and "process id" of the
current process using "current->comm" and "current->pid" respectively. Other fields of the structure task_struct can also we referred to in the similar way.

***************************current_proc.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;
 len = sprintf(buf,"\n Name :%s \n Process id: %d\n ",current->comm,current->pid);
printk(KERN_INFO "Inside the proc entry");
return len;
}

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

}


int char_arr_init (void) {
   
    create_new_proc_entry();
    return 0;
}

void char_arr_cleanup(void) {
    printk(KERN_INFO " Inside cleanup_module\n");
    remove_proc_entry("process_data",NULL);
}
MODULE_LICENSE("GPL");   
module_init(char_arr_init);
module_exit(char_arr_cleanup);
********************************************************************************************

**************************Makefile***************************************************
ifneq ($(KERNELRELEASE),)
   obj-m := current_proc.o
else

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

PWD := $(shell pwd)

default:
    $(MAKE) -C $(KERNELDIR) M=$(PWD) modules 
endif
clean:
    $(MAKE) -C $(KERNELDIR)  M=$(PWD) clean
*******************************************************************************
Run the following commands to see the output

$ make
$ sudo insmod current_proc.ko
$ cat /proc/process_data
Note: The output will always give process name as "cat" as that is what we are using to read the proc entry.

Types of cache Miss

Cache Miss :  When the address from which the processor wants to read or write is not present in the cache, the same has to be fetched from the main memory. This is termed as cache miss.
Due to a cache miss the processor has to wait for longer time for data as it has to be fetched from the main memory, this time is termed as Miss Penalty.
Miss penalty = "Time to look up in cache" + "Time to fetch from the main memory".
More details about the working of cache is given in


The cache misses as classified into three categories

1. Compulsory Misses
2. Conflict Misses
3. Capacity Misses

Compulsory Misses:

When the system is turned on, the cache does not have any valid data in it and hence the first few reads and writes will always miss in the cache. These misses are termed as compulsory misses as they will always occur when a system turns on.
The figure below describes the same.

Conflict Misses :

Let us take the example of a direct mapped cache . In a direct mapped cache the main memory address can be mapped only to a specific block in the cache. As the main memory will always be bigger in size than the cache, multiple memory addresses can be mapped to one cache block. For e.g. : If we have 32 Bytes of main memory and 8 bytes of cache,each block being 1 byte. Block0,Block8,Block16,Block24 of main memory will all be mapped to Block0 of the cache.  If Block0 of main memory is cached and the processor wants to read Block8 of main memory, then the Block8 will have to be moved into the cache, removing Block0 from cache. If processor wants to read Block0 again, it will be a miss as it was replaced by Block8. Thus because of the conflict between Block0 and Block1 leads to the cache misses, hence these types of misses are termed as conflict misses. 
The figure below explains the same.

Higher associative can reduce the conflict misses. For e.g.: If the same cache above was a 2 way set associative cache, then both Block0 and Block8 would map o set0 which would have two blocks in it and hence both block0 and block8 could have been cached.


Capacity Misses:

When all the blocks in a cache are occupied any new data that will be needed will always lead to a miss as there is no place to store the data and
the new data will replace some of the old block thus keeping the cache full. The same is depicted in the figure below.

Capacity misses can be reduced by a larger cache size as bigger the cache, longer it would take to fill it up completely.