linux 进程管理-----pid哈希链表

linux 进程管理-----pid哈希链表 2011-04-27 14:14:51

分类： LINUX

 

为了较快的从给定的pid值得到相应的宿主结构（进程描述符）指针，内核采用了pid哈希链表结构。

首先，以下的问题要理解：

1）为什么pid哈希链表只定义2048或者4096项（根据你的内存大小确定）？直接定义为pid最大值不是最好吗？

我们都知道，查找的最快方式就是数组了，可以在常数的时间内完成查找。假如我们的pid最大值为32768，那么我们完全可以定义一个 struct task_struct* name[32768];进而可以最快速的从给定的pid值中找到其相应的宿主结构。也就是指向该pid进程的进程描述符指针。

然而，这确实一种不理智的方法。虽然进程PID的最大值为32768，但是，我们在实际应用中所能用的pid值要平均值要远远低于这个值。这样的话，会造成大量的物理空间浪费。假如我们用到了2768个pid，那么还有30000*4bytes的空间浪费。

2）特殊情况的需求

设想这样一种情况：假设内核必须回收一个给定pid值的线程组内的所有线程，（线程组内的所有线程的pid值都是相同的）在上述数组形式的定义中，是无法完成的。

而我们要做的是必须为这种形式的线程组（pid值相同）组织成一个链表。这个链表的节点，就是这个线程组内的全部线程。

而pid哈希链表能很好的完成上述的1）2）两点。

下面我们看一下内核对pid哈希链表的定义和初始化过程以及相关的操作。

static struct hlist_head *pid_hash[PIDTYPE_MAX];
系统在初始化期间手动的创建了一个含有PIDTYPE_MAX个元素的指针数组。
用于存放指向hash桶的指针。
并且在start_kernel期间调用pidhash_init函数对hash桶进行初始化。
303 void __init pidhash_init(void)
     /*  */
 304 {
 305         int i, j, pidhash_size;
 306         unsigned long megabytes = nr_kernel_pages >> (20 - PAGE_SHIFT);
 307
 308         pidhash_shift = max(10, fls(megabytes * 4));
 309         pidhash_shift = min(12, pidhash_shift);
 310         pidhash_size = 1 << pidhash_shift;
 311
 312         printk("PID hash table entries: %d (order: %d, %Zd bytes)\n",
 313                 pidhash_size, pidhash_shift,
 314                 PIDTYPE_MAX * pidhash_size * sizeof(struct hlist_head));
 315        #######以上为桶的大小设置和桶中含有的entry个数设置
     #######dmesg结果显示：PID hash table entries: 4096 (order: 12, 16384 bytes)
     #######pidhash_size(桶大小）：4096*4bytes entries:4096
     #######也就是说桶中存有4096个指针，指针指向struct hlist_node结构
 316         for (i = 0; i < PIDTYPE_MAX; i++) {
 317                 pid_hash[i] = alloc_bootmem(pidhash_size *
 318                                         sizeof(*(pid_hash[i])));
     #######在系统启动期间slab和alloc分配器都还没有建立好
     #######采用allocbootmem内存分配器对系统初始化期间的内存进行分配
 319                 if (!pid_hash[i])
 320                         panic("Could not alloc pidhash!\n");
 321                 for (j = 0; j < pidhash_size; j++)
 322                         INIT_HLIST_HEAD(&pid_hash[i][j]);
     #######将桶中指向struct hlist_node 结构的指针first初始化为NULL
 323         }
经过这个函数 pid哈希链表 被初始化完成。

 

与此同时，start_kernel期间也对pid位图进行了相应的初始化。利用pid位图对进程pid号进行管理是一种简单并且高效的形式。（bit：0代表这个pid可以使用bit：1代表这个pid已经被占用）

系统在初始化期间手动的为表示进程pid号的位图分配空间并且初始化。

  50 typedef struct pidmap {
  51 atomic_t nr_free;
  52 void *page;
  53 } pidmap_t;

  55 static pidmap_t pidmap_array[PIDMAP_ENTRIES] =
  56 { [ 0 ... PIDMAP_ENTRIES-1 ] = { ATOMIC_INIT(BITS_PER_PAGE), NULL } };

位图初始化期间：利用get_zeroed_page函数为位图提供一个物理上的页框，并且此页框被实现初始化为0.

这样，一个大小为4K的物理页框，可以表示的进程号个数为：4*1024*8=32768；

但是有一点我们要主要：由于进程号0的特殊性，我们事先将其设置为不可用，也就是将位图的0号位设置为1，并把相应表示目前可用的pid号的个数减1.

326 void __init pidmap_init(void)
     /* */
 327 {
 328 int i;
 329
 330 pidmap_array->page = (void *)get_zeroed_page(GFP_KERNEL);
 331 set_bit(0, pidmap_array->page);
 332 atomic_dec(&pidmap_array->nr_free);
 333
 334 /*
 335 * Allocate PID 0, and hash it via all PID types:
 336 */
 337
 338 for (i = 0; i < PIDTYPE_MAX; i++)
 339 attach_pid(current, i, 0);
 340 }

上述代码通过attach_pid函数将0号进程进行hash，将其hash到上面已经初始化好的hash链表桶中。

我们知道每个进程中都有：struct pid pids[PIDTYPE_MAX]；而hash链表正是通过这个结构进行链接。

上述函数中，首先通过find_pid函数在指定类型和nr号的哈希链表中查找pid结构。如果找到则返回指向struct pid的指针 否则返回NULL。

接下来的代码根据find_pid的返回值，做出相应的动作。

1）pid为NULL，说明新attach的包含struct pid的进程描述符是哈希链表的第一个元素，将其插入头结点之后，并将struct pid的pid_list字段设置为NULL。struct list_head pid_list是由于连接具有相同nr号的进程描述符的连接件。

2）pid不为NULL,说明相应的哈希链表中已经存在了nr号为“nr”的进程描述符，我们只需将我们的进程描述符attach到相应的哈希链表的进程链表中。

 

通过上面的两个函数我们还可以得知：所有桶中（一般为4个）0号索引对应的哈希链表的第一个进程描述符元素都为0号进程的进程描述符。

而与attach_pid函数对应的操作为dettach_pid：将pid所在的进程描述符从对应的pid哈希链表中删除，这个函数的定义如下：

 192 void fastcall detach_pid(task_t *task, enum pid_type type)
     /* */
 193 {
 194 int tmp, nr;
 195
 196 nr = __detach_pid(task, type);
 197 if (!nr)
 198 return;
 199
 200 for (tmp = PIDTYPE_MAX; --tmp >= 0; )
 201 if (tmp != type && find_pid(tmp, nr))
 202 return;
 203
 204 free_pidmap(nr);
 205 }

核心函数为__detach_pid(task,type)

166 static fastcall int __detach_pid(task_t *task, enum pid_type type)
     /* */
 167 {
 168 struct pid *pid, *pid_next;
 169 int nr = 0;
 170
 171 pid = &task->pids[type];
 172 if (!hlist_unhashed(&pid->pid_chain)) {
 173
 174 if (list_empty(&pid->pid_list)) {
 175 nr = pid->nr;
 176 hlist_del_rcu(&pid->pid_chain);
 177 } else {
 178 pid_next = list_entry(pid->pid_list.next,
 179 struct pid, pid_list);
 180 /* insert next pid from pid_list to hash */
 181 hlist_replace_rcu(&pid->pid_chain,
 182 &pid_next->pid_chain);
 183 }
 184 }
 185
 186 list_del_rcu(&pid->pid_list);
 187 pid->nr = 0;
 188
 189 return nr;
 190 }

函数首先判断task指向的进程是否已经被hash进pid哈希链表，注意有可能是哈希链表中的进程链表。

如果不是哈希链表的节点，直接将其从所在的进程链表中删除。此时返回nr=0，我们后面可以看到，detach_pid函数根据nr值来判断是否需要将pid位图中相应的pid位清0，以此来使继续可以被使用。

如果是hash链表中的节点，还要判断

1）是否此哈希链表节点所在的进程链表只有这个节点。如果是将nr设置为pid->nr 并将这个节点删除

2）如果哈希链表节点所在的进程链表还有别的节点。那么用下一个节点replace这个节点。注意此时并未设置nr的值。也就是说返回的nr=0

当从__datach_pid返回后，接下来的任务就是判断是否需要将pid对应的pid位图中相应的位清0

1）如果nr=0，不需要清0 函数直接返回。通过上面我们知道，函数在两种情况下会返回nr=0 ：

  一，进程链表非空（此时暗指的含义就是这个pid还被其余的进程/线程使用着，不能在位图中将其释放； 

  二，删除的就是nr=0的进程描述符。这是也不需要在位图中将其释放；因为0号pid比较特殊是不允许其他进程使用的。

2）如果nr不等于0，还要判断在其他类型的哈希链表中是否存在这样的进程描述符，如果存在也表明其正在使用不能释放。

如果上述两步都没有return那么的确是需要将pid位图中想的pid表示位清0，以供系统使用。

上述的代码中有一处理解容易出现问题：

 200 for (tmp = PIDTYPE_MAX; --tmp >= 0; )
 201 if (tmp != type && find_pid(tmp, nr))
 202 return;

为什么只搜索其他类型的hash链表而不处理我们刚刚将其删pid的类型的hash链表呢？因为对于刚刚删除的进程描述符的类型的hash链表 我们应经用nr的值来表明是否需要清位图位了。

如果nr=0那么删除的进程描述符所在的进程链表是非空的---不必删除

如果进程链表是空的那么nr=pid-->nr我们不考虑0号pid那么这个nr一定为非0就说明我这个类型的hash链表不用这个进程号了 你查查其他类型的hash链表是否还使用吧。

如果其他有一个在使用，OK 不删返回。如果都不用，那么我就清理门户pidbitmap 相应位设置为0了。