KernelAnalysis-HOWTO

13. Utility functions

13.1 list_entry [include/linux/list.h]

Definition:

#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

Meaning:

"list_entry" macro is used to retrieve a parent struct pointer, by using only one of internal struct pointer.

Example:

struct __wait_queue {
   unsigned int flags; 
   struct task_struct * task; 
   struct list_head task_list;
};
struct list_head { 
   struct list_head *next, *prev; 
};

// and with type definition:
typedef struct __wait_queue wait_queue_t;

// we'll have
wait_queue_t *out list_entry(tmp, wait_queue_t, task_list);

// where tmp point to list_head

So, in this case, by means of *tmp pointer [list_head] we retrieve an *out pointer [wait_queue_t].

 ____________ <---- *out [we calculate that]
|flags       |             /|\
|task *-->   |              |
|task_list   |<----    list_entry
|  prev * -->|    |         |
|  next * -->|    |         |
|____________|    ----- *tmp [we have this]
 

13.2 Sleep

Sleep code

Files:

• kernel/sched.c
• include/linux/sched.h
• include/linux/wait.h
• include/linux/list.h

Functions:

• interruptible_sleep_on
• interruptible_sleep_on_timeout
• sleep_on
• sleep_on_timeout

Called functions:

• init_waitqueue_entry
• __add_wait_queue
• list_add
• __list_add
• __remove_wait_queue

InterCallings Analysis:

|sleep_on
   |init_waitqueue_entry  --
   |__add_wait_queue        |   enqueuing request to resource list
      |list_add              |
         |__list_add        -- 
   |schedule              ---     waiting for request to be executed
      |__remove_wait_queue --   
      |list_del              |   dequeuing request from resource list
         |__list_del        -- 
 

Description:

Under Linux each resource (ideally an object shared between many users and many processes), , has a queue to manage ALL tasks requesting it.

This queue is called "wait queue" and it consists of many items we'll call the"wait queue element":

***   wait queue structure [include/linux/wait.h]  ***


struct __wait_queue {
   unsigned int flags; 
   struct task_struct * task; 
   struct list_head task_list;
}
struct list_head { 
   struct list_head *next, *prev; 
};

Graphic working:

        ***  wait queue element  ***

                             /|\
                              |
       <--[prev *, flags, task *, next *]-->
 
                     


                 ***  wait queue list ***  
 
          /|\           /|\           /|\                /|\
           |             |             |                  |
--> <--[task1]--> <--[task2]--> <--[task3]--> .... <--[taskN]--> <--
|                                                                  |
|__________________________________________________________________|
          

           
              ***   wait queue head ***

       task1 <--[prev *, lock, next *]--> taskN
   
 

"wait queue head" point to first (with next *) and last (with prev *) elements of the "wait queue list".

When a new element has to be added, "__add_wait_queue" [include/linux/wait.h] is called, after which the generic routine "list_add" [include/linux/wait.h], will be executed:

***   function list_add [include/linux/list.h]  ***

// classic double link list insert
static __inline__ void __list_add (struct list_head * new,  \
                                   struct list_head * prev, \
                                   struct list_head * next) { 
   next->prev = new; 
   new->next = next; 
   new->prev = prev; 
   prev->next = new; 
}

To complete the description, we see also "__list_del" [include/linux/list.h] function called by "list_del" [include/linux/list.h] inside "remove_wait_queue" [include/linux/wait.h]:

***   function list_del [include/linux/list.h]  ***


// classic double link list delete
static __inline__ void __list_del (struct list_head * prev, struct list_head * next) { 
   next->prev = prev; 
   prev->next = next; 
}

Stack consideration

A typical list (or queue) is usually managed allocating it into the Heap (see Cap.10 for Heap and Stack definition and about where variables are allocated). Otherwise here, we statically allocate Wait Queue data in a local variable (Stack), then function is interrupted by scheduling, in the end, (returning from scheduling) we'll erase local variable.

  new task <----|          task1 <------|          task2 <------|
                |                       |                       |
                |                       |                       | 
|..........|    |       |..........|    |       |..........|    | 
|wait.flags|    |       |wait.flags|    |       |wait.flags|    |
|wait.task_|____|       |wait.task_|____|       |wait.task_|____|   
|wait.prev |-->         |wait.prev |-->         |wait.prev |-->
|wait.next |-->         |wait.next |-->         |wait.next |-->   
|..        |            |..        |            |..        |    
|schedule()|            |schedule()|            |schedule()|     
|..........|            |..........|            |..........|    
|__________|            |__________|            |__________|     
 
   Stack                   Stack                   Stack