L'implementazione della lista concatenata del kernel Linux
 
La lista concatenata e' un importante struttura dati la quale permette un grande numero di memorizzazioni con efficente manipolazione di dati. La maggior parte del codice del kernel e' stato scritto con l'aiuto di questa struttura dati. In questo modo la maggior parte della complessita' del codice del kernel (la struttura dei dati) dipende dall'implementazione di quella struttura di dati. E' possibile scrivere del proprio codice ma la sua cattiva progettazione puo' dare cattive prestazioni. Un buon sistema operativo dovrebbe dare non solo stabilita' ma anche buone prestazioni. Cosi' ero curioso di sapere come linux implementa la lista concatenata. E' una lista circolare singolarmente concatenata o una lista doppiamente concatenata o una lista circolare doppiamente concatenata ?

Ci sono diversi file di librerie dove la maggior parte delle funzioni dovrebbero essere state dichiarate? Si la mia ricerca e' terminata a

"/usr/src/linux/include/linux/list.h".

Ho potuto vedere che tutti i tipi di funzioni sono dichiarati qui. Prima di parlare di tutte queste funzioni dovrei dire qualcosa circa come il kernel di linux adotta strategie per compilare efficenti implementazioni.

Esso ha un unico stile per implementare lo scorrimento, l'aggiunta, la cancellazione di nodi in una lista circolare concatenata. Siccome e' circolare, son si ha bisogno di pensare al nodo di testa o al nodo di coda. Basta semplicemente prendere un nodo e seguire i puntatori fino a che non si torna al punto di partenza. Questo approccio rimuove l'implementazione extra "head node". Cosi' ogni routine semplicemente ha bisogno di un puntatore ad un singolo elemento nella lista e questo potrebbe essere un qualsiasi elemento. Ci si puo' meravigliare di vedere l'implementazione. Normalmente si usa dichiarare la lista concatenata tipo:

struct my_list{
 int data,
 struct my_list *prev;
 struct my_list *next;
};

Ma se si vuole adottare l'implementazione stile linux allora si potrebbe scrivere tipo

struct my_list{
 struct list_head list; //linux kernel list implementation//
 int data;
};
struct list_head { //Declared in list.h file
 struct list_head *next;
 struct list_head *prev;
}

Adesso notare il nome della struttura "list_node". Gli sviluppatori di Linux hanno preso il nome pensando al fatto che non c'e' un nodo alla testa nella lista. Tutti i nodi potrebbero agire da nodo di testa. Il "puntatore *next" punta all'elemento successivo e il "puntatore *prev" puntera' all'elemento precedente. Grazie all'implementazione della ingegnosa lista di Linux. Ci si puo' dimenticare il concetto di primo nodo e ultimo nodo. Si puo' soltanto comparare la lista come un grande ciclo senza primo ne' ultimo. Ci sono molte ingegnose implementazioni di ogni funzione. Si sonsiglia di scorrere il file list.h. E' ben documentato. Non potrebbe essere fatta migliore documentazione di questa. Sono certo, e' possibile capirlo in un'ora.

Adesso possono venire in mente alcune domande:-)

1.) Perche' dovrei imparare l'implementazione dell'esecuzione della lista concatenata del kernel di linux, potendo scrivere il mio proprio codice o potendo prendere la libreria della lista concatenata da un qualsiasi altro posto?

2) Come posso usare la libreria della lista concatenata di linux nelle mie aplicazioni in user space? Quale sarebbe il beneficio che porei avere usando questa libreria?

Si, provo a dare risposta a queste due domande. Se non si e' soddisfatti delle mie risposte, prego lasciare un commento...


Domanda No 1:

1) Se si desidera immaginarsi come un futuro hacker del kernel di linux, si deve imparare questa strategia. Posso suggerire un libro "linux Kernel Development" del rinomato hacker del kernel Robert Love. Leggere l'Appendice-A
"Tutti i nuovi utenti devono usare l'uscita interfase, siamo seri, non reinventiamo la ruota"

2) Creare vari tipi di Strutture Dati: E' possibile costruire qualsiasi struttura dati si ha in mente.
3) Portabilita': Altrimenti non sarebbe stata messa nell'albero principale dei sorgenti del kernel di linux.
4) E' da imparare. readibility: Si, e' facile da imparare, si possono imparare tutte le funzioni in un'ora di studio rigoroso.
5) Complessita'. Si rimarrebbe meravigliati che tutte queste funzioni sono O(1), significa che esse vengono eseguite con tempo costante senza tener conto della dimensione della lista.


Risposte: Quesito No.2:

Con alcune modifiche minori, si puo' includere questo file header list.h dentro la propria applicazione in userspace. E' un file header singolo. Molto maneggevole! Occorre fare:

 a)Rimuovere #ifdef __KERNE__ e la sua #endif
 b)Rimuovere tutte le righe #include
 c)Rimuovere le relative funczioni rcu (molte di loro sono la')

Si, sto' lavorando su questa lista per pubblicare il mio proprio file list.h. Ho gia' implementato l'esecuzione generica della mia propria lista circolare doppiamente concatenata e ho scritto lo stesso programma con aiuto del file "list.h" e del compare

Potreste inoltre............

P.S: Il kernel usa la lista collegata per memorizzare la lista dei task, ogni task_struct del processo e' un elemento nella lista collegata.
dare un'acchiata a questo 

link... http://lxr.linux.no/ident?i=list_add

Si capira' automaticamente la funzione del list_add e quante volte e' stata chiamata:-)

Risorse: Sezione
Ho letto dall'articolo. Provare a capire dall'articolo. E naturalmente dovrei condividere con voi.

Dare un'occhiata:

Ref 1: "Linux Kernel Development"-Robert Love Appendix -A
Ref 2: Linux kernel linked list for user space (http://www-unix.mcs.anl.gov/~kazutomo/list/index.html)
Ref 3: Linux Kernel Linked List Explained (http://isis.poly.edu/kulesh/stuff/src/klist/)

Happy Hacking...