Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1763030
  • 博文数量: 145
  • 博客积分: 8668
  • 博客等级: 中将
  • 技术积分: 3911
  • 用 户 组: 普通用户
  • 注册时间: 2007-03-09 21:21
个人简介

work hard

文章分类

全部博文(145)

文章存档

2016年(1)

2015年(1)

2014年(1)

2013年(12)

2012年(3)

2011年(9)

2010年(34)

2009年(55)

2008年(20)

2007年(9)

分类: C/C++

2013-08-02 14:04:27

原文连接: http://blog.csdn.net/zhanglei4214/article/details/6767288

在Linux内核中,hlist(哈希链表)使用非常广泛。本文将对其数据结构和核心函数进行分析。

和hlist相关的数据结构有两个(1)hlist_head (2)hlist_node


  1. struct hlist_head {  
  2.         struct hlist_node *first;  
  3. };  
  4.   
  5. struct hlist_node {  
  6.         struct hlist_node *next, **pprev;  
  7. };  
顾名思义, hlist_head表示哈希表的头结点。 哈希表中每一个entry(hlist_head)所对应的都是一个链表(hlist),该链表的结点由hlist_node表示。


 hlist_head结构体只有一个域,即first。 first指针指向该hlist链表的第一个节点。

hlist_node结构体有两个域,next 和pprev。 next指针很容易理解,它指向下个hlist_node结点,倘若该节点是链表的最后一个节点,next指向NULL。

pprev是一个二级指针, 它指向前一个节点的next指针。为什么我们需要这样一个指针呢?它的好处是什么?

在回答这个问题之前,我们先研究另一个问题:为什么散列表的实现需要两个不同的数据结构?

散列表的目的是为了方便快速的查找,所以散列表通常是一个比较大的数组,否则“冲突”的概率会非常大, 这样也就失去了散列表的意义。如何做到既能维护一张大表,又能不使用过多的内存呢?就只能从数据结构上下功夫了。所以对于散列表的每个entry,它的结构体中只存放一个指针,解决了占用空间的问题。现在又出现了另一个问题:数据结构不一致。显然,如果hlist_node采用传统的next,prev指针, 对于第一个节点和后面其他节点的处理会不一致。这样并不优雅,而且效率上也有损失。

hlist_node巧妙地将pprev指向上一个节点的next指针的地址,由于hlist_head和hlist_node指向的下一个节点的指针类型相同,这样就解决了通用性!

下面我们再来看一看hlist_node这样设计之后,插入 删除这些基本操作会有什么不一样。


  1. static inline void __hlist_del(struct hlist_node *n)  
  2. {  
  3.         struct hlist_node *next = n->next;  
  4.         struct hlist_node **pprev = n->pprev;  
  5.         *pprev = next;  
  6.         if (next)  
  7.                 next->pprev = pprev;  
  8. }  
__hlist_del用于删除节点n。


首先获取n的下一个节点next, n->pprev指向n的前一个节点的next指针的地址, 这样×pprev就代表n前一个节点的下一个节点(现在即n本身),第三行代码*pprev=next;就将n的前一个节点和下一个节点关联起来了。至此,n节点的前一个节点的关联工作就完成了,现在再来完成下一个节点的关联工作。如果n是链表的最后一个节点,那么n->next即为空, 则无需任何操作,否则,next->pprev = pprev。

给链表增加一个节点需要考虑两个条件:(1)是否为链表的首个节点(2)普通节点。


  1. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)  
  2.  {  
  3.          struct hlist_node *first = h->first;  
  4.          n->next = first;  
  5.          if (first)  
  6.                  first->pprev = &n->next;  
  7.          h->first = n;  
  8.          n->pprev = &h->first;  
  9.  }  
首先讨论条件(1)。


first = h->first; 获取当前链表的首个节点;

n->next = fist;  将n作为链表的首个节点,让first往后靠;

先来看最后一行 n->pprev - &h->first; 将n的pprev指向hlist_head的first指针,至此关于节点n的关联工作就做完了。

再来看倒数第二行 h->first = n; 将节点h的关联工作做完;

最后我们再来看原先的第一个节点的关联工作,对于它来说,仅仅需要更新一下pprev的关联信息: first->pprev = &n->next;

接下来讨论条件(2)。 这里也包括两种情况:a)插在当前节点的前面b)插在当前节点的后面


  1. /* next must be != NULL */  
  2.  static inline void hlist_add_before(struct hlist_node *n,  
  3.                                          struct hlist_node *next)  
  4.  {  
  5.          n->pprev = next->pprev;  
  6.          n->next = next;  
  7.          next->pprev = &n->next;  
  8.          *(n->pprev) = n;  
  9.  }  

先讨论情况a) 将节点n 插到next之前  (n是新插入的节点)

还是一个一个节点的搞定(一共三个节点), 先搞定节点n

n->pprev = next->prev;   将 next 的pprev 赋值给n->pprev  n取代next的位置

n->next = next;   将next作为n的下一个节点, 至此节点n的关联动作完成。

next->pprev = &n->next; next的关联动作完成。

*(n->pprev) = n;   n->pprev表示n的前一个节点的next指针; *(n->pprev)则表示n的前一个节点next指针所指向下一个节点的内容, 这里将n赋值给它,正好完成它的关联工作。


  1. static inline void hlist_add_after(struct hlist_node *n,  
  2.                                          struct hlist_node *next)  
  3.  {  
  4.          next->next = n->next;  
  5.          n->next = next;  
  6.          next->pprev = &n->next;  
  7.    
  8.          if(next->next)  
  9.                  next->next->pprev  = &next->next;  
  10.  }  
再来看情况b) 将结点next插入到n之后 (next是新插入的节点)


具体步骤就不分析了。 应该也很容易。

下面我还要介绍一个函数:


  1. static inline int hlist_unhashed(const struct hlist_node *h)  
  2.  {  
  3.          return !h->pprev;  
  4.  }  
这个函数的目的是判断该节点是否已经存在hash表中。这里处理得很巧妙。 判断前一个节点的next指向的地址是否为空。



最后我们看一个具体的例子,Linux内核是如何管理pid的。(正好和上一篇介绍pid的文章相呼应:))   基于内核3.0.3

内核初始化时要调用pidhash_init()创建哈希表。 该函数会在 start_kernel()函数里被调用(init/main.c Line 509)


  1. void __init pidhash_init(void)  
  2.  {  
  3.          int i, pidhash_size;  
  4.    
  5.          pid_hash = alloc_large_system_hash("PID"sizeof(*pid_hash), 0, 18,  
  6.                                             HASH_EARLY | HASH_SMALL,  
  7.                                             &pidhash_shift, NULL, 4096);  
  8.          pidhash_size = 1 << pidhash_shift;  
  9.    
  10.          for (i = 0; i < pidhash_size; i++)  
  11.                  INIT_HLIST_HEAD(&pid_hash[i]);  
  12.  }  
从这个函数可以看到内核会在slab上分配一个大小为pidhash_size的数组,然后为每一个entry进行初始化(INIT_HLIST_HEAD)


在alloc_pid函数里


  1. struct pid *alloc_pid(struct pid_namespace *ns)  
  2.  {  
  3.          struct pid *pid;  
  4.          enum pid_type type;  
  5.          int i, nr;  
  6.          struct pid_namespace *tmp;  
  7.          struct upid *upid;  
  8.    
  9.          pid = kmem_cache_alloc(ns->pid_cachep, GFP_KERNEL);  /×在slab上分配pid结构体×/  
  10.          if (!pid)  
  11.                  goto out;  
  12.    
  13.          tmp = ns;  
  14.          for (i = ns->level; i >= 0; i--) {       /×虽然这里是for循环,实际只会运行一次,因为现在只支持global namespace即ns->level=0×/  
  15.                  nr = alloc_pidmap(tmp);          /×在各级pid_namespace上寻找并分配pid的值×/  
  16.                  if (nr < 0)  
  17.                          goto out_free;  
  18.    
  19.                  pid->numbers[i].nr = nr;  
  20.                  pid->numbers[i].ns = tmp;  
  21.                  tmp = tmp->parent;  
  22.          }  
  23.    
  24.          get_pid_ns(ns);  
  25.          pid->level = ns->level;  
  26.          atomic_set(&pid->count, 1);  
  27.          for (type = 0; type < PIDTYPE_MAX; ++type)  
  28.                  INIT_HLIST_HEAD(&pid->tasks[type]);     
  29.    
  30.          upid = pid->numbers + ns->level;  
  31.          spin_lock_irq(&pidmap_lock);  
  32.          for ( ; upid >= pid->numbers; --upid)  
  33.                  hlist_add_head_rcu(&upid->pid_chain,  
  34.                                  &pid_hash[pid_hashfn(upid->nr, upid->ns)]);   /×将各级namespace中的upid插入pidhash的哈希表里×/  
  35.          spin_unlock_irq(&pidmap_lock);  
  36.    
  37.  out:  
  38.          return pid;  
  39.    
  40.  out_free:  
  41.          while (++i <= ns->level)  
  42.                  free_pidmap(pid->numbers + i);  
  43.    
  44.          kmem_cache_free(ns->pid_cachep, pid);  
  45.          pid = NULL;  
  46.          goto out;  
  47.  }  



注:

(1)本文中如果发现任何错误请帮我指出。 非常感谢!

(2)欢迎和大家进行交流。

(3)本文系原创,如需转载请标明出处。






阅读(3662) | 评论(1) | 转发(2) |
给主人留下些什么吧!~~

星闪夜空2015-11-19 10:50:13

godbach大神,我觉得您“从这个函数可以看到内核会在slab上分配一个大小为pidhash_size的数组”这句话有些问题,我认为应该是从bootmem分配的数组。

评论热议
请登录后评论。

登录 注册