13. Funzioni di comune utilizzo

13.1 list_entry [include/linux/list.h]

Definizione

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

Significato:

La macro "list_entry" viene usata per ricavare il puntatore ad una struttura utilizzando soltanto un elemento interno alla struttura.

Esempio

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

// e con la definizione del tipo:
typedef struct __wait_queue wait_queue_t;

// avremo:
wait_queue_t *out list_entry(tmp, wait_queue_t, task_list);

// dove tmp punta a list_head

Quindi, in questo caso, usando il puntatore *tmp [list_head] troviamo il puntatore *out [wait_queue_t].

 ____________ <---- *out [abbiamo calcolato questo]
|flags       |             /|\
|task *-->   |              |
|task_list   |<----    list_entry
|  prev * -->|    |         |
|  next * -->|    |         |
|____________|    ----- *tmp [partendo da questo]
 

13.2 Sleep

Codice di Sleep

Files:

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

Funzioni:

• interruptible_sleep_on
• interruptible_sleep_on_timeout
• sleep_on
• sleep_on_timeout

Funzioni chiamate:

• init_waitqueue_entry
• __add_wait_queue
• list_add
• __list_add
• __remove_wait_queue

InterCallings Analysis:

|sleep_on
   |init_waitqueue_entry  --
   |__add_wait_queue        |   Accodamento della richiesta sulla lista della risorsa
      |list_add              |
         |__list_add        -- 
   |schedule              ---     Attesa che la richiesta venga eseguita
      |__remove_wait_queue --   
      |list_del              |   Disaccodamento richiesta dalla lista della risorsa
         |__list_del        -- 
 

Descrizione:

Ogni risorsa (in teoria ogni oggetto condiviso tra piu' utenti e piu' processi), ha una cosa per gestire TUTTI i Tasks che la richiedono.

Questo metodo di accodamento viene chiamato "wait queue" e consiste di molti elementi chiamati"wait queue element":

***   struttura wait queue [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; 
};

Rappresentazione grafica:

        ***  elemento wait queue  ***

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


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

           
              ***   Testa wait queue ***

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

La Testa "wait queue" punta al primo (con next *) e last (com prev *) all'ultimo della lista "wait queue".

Quando deve venire inserito un nuovo elemento viene chiamata la "__add_wait_queue" [include/linux/wait.h], dopo di che verra' eseguita la generica routine "list_add" [include/linux/wait.h]:

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

// classico inserimento doppio linkato
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; 
}

Per completare la descrizione vediamo anche la "__list_del" [include/linux/list.h] chiamata da "list_del" [include/linux/list.h] all'interno di "remove_wait_queue" [include/linux/wait.h]:

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


// classica cancellazione doppio linkato
static __inline__ void __list_del (struct list_head * prev, struct list_head * next) { 
   next->prev = prev; 
   prev->next = next; 
}

Considerazioni sullo Stack

Una lista tipica (o coda) viene normalmente gestita allocandola nello Heap (si veda il Cap.10 per definizioni e gestione delle variabili nello Heap e nello Stack).

Qui invece, allochiamo ''Wait Queue'' in una variabile locale (quindi nello Stack), dopo di che la funzione viene interrotta dalla schedulazione e, al risveglio, la variabile locale verra' cancellata

  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

Hosting by: hurra.com
Generated: 2007-01-26 17:56:17