link list

  1. struct list_element {
  2.   void *data;
  3.   struct list_element *next;
  4. }

double linklist

  1. struct list_element {
  2.   void *data;
  3.   struct list_element *prev;
  4.   struct list_element *next;
  5. }

list_header

  1. struct list_head{
  2.     struct list_head *next;
  3.     struct list_head *prev;
  4. }
  1. struct fox {
  2.     unsigned long tail_length;
  3.     unsigned long weight;
  4.     bool is_fantastic;
  5.     struct list_head list;
  6. }

container_of

use the macro container_of, we can easily find the parent struct containing any given member variable. the offset of a given variable into a structure is fixed by the ABI at compile time.

  1. #define container_of(ptr, type, member) ({ \
  2.     const typeof( ((type *)0)->member) * __mptr = (ptr); \
  3.     (type *)((char *)__mptr - offsetof(type, member));})
  1. #defnine list_entry(ptr, type, member) \
  2.     container_of(ptr, type, member)

例子

  1. struct container {
  2.   int some_other_data;
  3.   int this_data;
  4. }
  6. struct container *my_container;
  7. int *my_ptr = &my_container->this_data;
  8. my_container = container_of(my_ptr, struct container, this_data);
  10. my_ptr:           表示指向this_data的指针
  11. struct container: 表示包含this_data的结构体
  12. this_data:        表示my_ptr在struct container中的字段名

define a linked list

  1. struct fox *red_fox;
  2. red_fox = kmalloc(sizeof(*red_fox), GFP_KERNEL);
  3. red_fox->tail_length = 40;
  4. red_fox->weight = 6;
  5. red_fox->is_fantastic = false;
  6. INIT_LIST_HEAD(&red_fox->list);
  8. // or
  9. struct fox red_fox = {
  10.   .tail_length = 40,
  11.   .weight = 6,
  12.   .list  = LIST_HEAD_INIT(red_fox. list),
  13. };

iterator

  1. struct list_head *p;
  2. struct fox *f;
  4. list_for_each(p, &fox_list)  {
  5.     f = list_entry(p, struct fox, list);
  6. }
  1. list_for_each_entry(pos, head, member);

here, pos is a pointer to the object containing the list_head nodes.

  1. struct fox *f;
  2. list_for_each_entry(f, &fox_list, list) {
  3.     // for each iteration f points to the next fox structure
  4. }

in real example, from inotify, the kernel’s filesystem notification system:

  1. static struct inotify_watch *inode_find_handle(struct inode *inode,
  2.                                                struct inotify_handle *ih)
  3. {
  4.    struct inotify_watch *watch;
  5.    list_for_each_entry(watch, &inode->inotify_watches, i_list) {
  6.        if (watch->ih == ih) {
  7.            return watch;
  8.        }
  9.    }
  10.     return NULL;
  11. }

this function iterates over all the entries in the inode->inotify_watches list, each entry is of type struct inotify_watch and the list_head in that structure is named i_list.

list_for_each_entry_safe

list_for_each_entry_safe(pos, next, head, member)

The next pointer is used by the list_for_each_entry_safe() macro to store the next entry in the list, we can use this macro to remove the element while iterator the list

Queue

kfifo

Creating queue

int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);

This function creates and initializes a kfifo with a queue of size bytes. The kernel uses the gfp mask gfp_mask to allocate the queue. upon success, it return 0, otherwise it return negtive error code.

struct kfifo fifo;
int ret;
ret = kfifo_alloc(&fifo, PAGE_SIZE, GFP_KERNEL);
if (ret) 
    return ret;

enqueue

unsigned int i;
for (i = 0; i < 32; i++)
    kfifo_in(fifo, &i, sizeof(i));

Map

struct idr id_huh; // define idr
idr_init(&id_huh); // initialize idr