Linux Kernel Portability-Data type & Data Structure in Linux kernel (二)

在上一篇著重於Linux Kernel 的Portability。這一篇將著重於Linux Kernel的Data Structure。這裡要介紹的Data Structure包括了Linked lists、Queues、Maps、及Binary trees。

• Linked List

這裡直接講用法。Linux Kernel的Linked List是Double Linked List，而且List裡面的元素必須是list_head的structure。舉個例好了，我們要做到如下圖(A B C都是struct sample好了):

struct sample{
    struct list_head link;
    vold *content;
}
struct sample *A,*B,*C;

現在我們要把ABC串起來。首先我們建立一個叫list_head的Linked list的變數，並初始化它。常見的方法有兩種，結果是一樣的。

/**
*1. LIST_HEAD(name)
*2. INIT_LIST_HEAD
*/
//method 1
static LIST_HEAD(list_head);

//method 2
struct list_head list_head;
INIT_LIST_HEAD(&list_head);

接著假設我們要先加入A和C，利用list_add()將A加入到list_head後面。然後在將C加入到A後面。

//Add A after list_head,list_head is the head of the list
//e.g list_head->A
list_add(&A->link,&list_head);

//Add C after A e.g list_head->A->C
list_add(&C->link,&A->link);

接著，我們要利用list_add_tail將B加在C之前

//Add B before C e.g list_head->A->B->C
list_add_tail(&B->link,&C->link);

加完了之後我們要怎麼列出List裡面的項目呢？可以利用list_for_each來達成。

//list_for_each(struct list_head *cursor, struct list_head *list)
list_for_each(&A->link,&list_head){

}

更多的用法可見<linux/list.h>

• Queue 

Linux Kernel的queue叫做kfifo實做在kernel/kfifo.c 宣告在<linux/kfifo.h>。與我們所知的queue相同，kfifo支援enqueue(函式命名成inqueue)跟dequeue。同樣的，kfifo有兩個offset分別是記錄下一個插入位置的enqueue offset跟下一個取出位置的dequeue offset。

接下來介紹kfifo的使用方式分為 1. Declare  2. Enqueue/Dequeue 3. Other operation。

Declare 

a. 利用kfifo_alloc() 動態宣告   

struct kfifo fifo;
int ret;
      //宣告一個大小為PAGE_SIZE的queue
ret = kfifo_alloc(&kifo, PAGE_SIZE, GFP_KERNEL);
if (ret)
return ret;

b. 利用DECLARE_KFIFO(name, size)建立 INIT_KFIFO(name)初始化。

Enqueue/Dequeue

kfifo_in(fifo, buf, n) 將n byte的buf讓入fifo裡。如果fifo free的大小<n 則只會copy free 的size的資料 

kfifo_out(fifo, buf, n) copy n byte到buf中。如果fifo的大小<n 則只會copy fifo大小的data

kfifo_out_peek(fifo, buf, n) kfifo_out執行後data就會從fifo中刪除。如果想保留可以使用kfifo_out_peek

Other Operation 

kfifo_size(fifo) 取得fifo大小

kfifo_len(fifo) 取得fifo已使用大小

kfifo_avail(fifo) 取得fifo可使用大小

kfifo_is_empty(fifo) 判斷fifo是否為空

kfifo_is_full(fifo) 判斷fifo是否已滿

kfifo_reset(fifo) 清空fifo。

kfifo_free(fifo) free掉fifo

實際的操作範例

struct kfifo fifo;
int ret;

//宣告一個大小為PAGE_SIZE的queue
ret = kfifo_alloc(&kifo, PAGE_SIZE, GFP_KERNEL);
if (ret)
    return ret;
int i;
//插入32個size為sizeof(int)的[0,31]到fifo中
for (i = 0; i < 32; i++)
    kfifo_in(fifo, &i; sizeof(i));

unsigned int val;
int ret;

//從fifo讀取一個integer到val 中。資料不會被刪除
ret = kfifo_out_peek(fifo, &val, sizeof(val));
if (ret != sizeof(val))
    return -EINVAL;

printk(KERN_INFO “%u\n”, val); /* should print 0 */


/* while there is data in the queue ... */
while (kfifo_avail(fifo)) {
    unsigned int val;
    int ret;
    /* ... read it, one integer at a time */
    ret = kfifo_out(fifo, &val, sizeof(val));
    if (ret != sizeof(val))
        return -EINVAL;

    printk(KERN_INFO “%u\n”, val);
}

• Red-Black Tree

紅黑樹是一種semi-balanced binary tree(自平衡二元樹)。主要有以下六種性質：

1. 節點不是紅色就是黑色。
2. 根節點是黑色。
3. 所有葉子都是黑色（葉子是NIL節點 e.g不包含資料）。
4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
5. 從任一節點到其每個葉子的所有最短路徑都包含相同數目的黑色節點。

紅黑樹在Linux Kernel實作的地方是lib/rbtree.c宣告的地方在<linux/rbtree.h>。這裡直接以 driver/media/video/tegra/avp/avp.c裡面的實作來解釋rbtree的使用。avp.c定義了一個tegra_avp_info的struct，以下擷取其實做。要使用rbtree必須要宣告一個rb_root的變數如下：

struct tegra_avp_info {
 ...
 struct rb_root  endpoints;
        ...
};

要開始使用endpoints這個rbtree之前必須給他初始的值"RB_ROOT"如下：

static int tegra_avp_probe(struct platform_device *pdev)
{
    struct   *avp;
    avp = kzalloc(sizeof(struct tegra_avp_info), GFP_KERNEL);
    ...
    avp->endpoints = RB_ROOT;
    ...
}

Linux Kernel的rbtree不包含插入及搜尋的函式，下面同樣以avp的"插入"來說明。

static struct remote_info *remote_find(struct tegra_avp_info *avp, u32 local_id)
{
 struct rb_node *n = avp->endpoints.rb_node;
 struct remote_info *rinfo;

 while (n) {
  rinfo = rb_entry(n, struct remote_info, rb_node);

  if (local_id < rinfo->loc_id)
   n = n->rb_left;
  else if (local_id > rinfo->loc_id)
   n = n->rb_right;
  else
   return rinfo;
 }
 return NULL;
}

以上例，remote_find()實作搜尋的功能。while loop會traverse整個tree 直到找到相同的id。

static int remote_insert(struct tegra_avp_info *avp, struct remote_info *rinfo)
{
 struct rb_node **p;
 struct rb_node *parent;
 struct remote_info *tmp;

 p = &avp->endpoints.rb_node;
 parent = NULL;
 while (*p) {
  parent = *p;
  tmp = rb_entry(parent, struct remote_info, rb_node);

  if (rinfo->loc_id < tmp->loc_id)
   p = &(*p)->rb_left;
  else if (rinfo->loc_id > tmp->loc_id)
   p = &(*p)->rb_right;
  else {
   pr_info("%s: avp endpoint id=%x (%s) already exists\n",
    __func__, rinfo->loc_id,
    trpc_name(rinfo->trpc_ep));
   return -EEXIST;
  }
 }
 rb_link_node(&rinfo->rb_node, parent, p);
 rb_insert_color(&rinfo->rb_node, &avp->endpoints);
 rinfo_get(rinfo);
 return 0;
}

以上例，while loop會traverse rbtree去尋找適合的頁節點，然後透過rb_link_node()去link parent。接著再透過rb_insert_color()上色。

static void remote_remove(struct tegra_avp_info *avp, struct remote_info *rinfo)
{
 rb_erase(&rinfo->rb_node, &avp->endpoints);
 rinfo_put(rinfo);
}

刪除節點很簡單，只要呼叫rb_erase（）即可。

• Radix Tree

Radix Tree使用相對於Red Block Tree來說簡單許多。這裡以之前提過得irq實做為例看看Radix Tree怎麼使用。

Radix Tree實做在lib/radix- tree.c，下面以kernel/irqdesc.c來了解。

//Declare a radix tree called irq_desc_tree
static RADIX_TREE(irq_desc_tree, GFP_KERNEL);

static void irq_insert_desc(unsigned int irq, struct irq_desc *desc)
{
        //Insert  into irq_desc_tree
 radix_tree_insert(&irq_desc_tree, irq, desc);
}

struct irq_desc *irq_to_desc(unsigned int irq)
{
        //取得key為irq的value
 return radix_tree_lookup(&irq_desc_tree, irq);
}

static void delete_irq_desc(unsigned int irq)
{
        //刪除key為irq的pair
 radix_tree_delete(&irq_desc_tree, irq);
}

• Reference

Linux Kernel Development Third Edition 
Linux Device Drivers, Third Edition
Essential Linux Device Drivers
Writing Portable Device Driver
Trees I: Radix trees
Trees II: red-black trees

上一篇:Linux Kernel Portability-Data type & Data Structure in Linux kernel (一)