kernel hacker修炼之道之调度器与时间系统-PID 哈希表

浅析linux内核调度器与时间系统之PID 哈希表

作者：李万鹏

首先看一下kernel中的哈希表的数据结构，哈希表头：

struct hlist_head {
	struct hlist_node *first;
};

链表头是hlist_head，注意这是一个双向链表但不循环。first字段指向第一个节点。

哈希表节点：

struct hlist_node {
	struct hlist_node *next, **pprev;
};

这里的next指向下一个节点，pprev字段存放了上一个next字段的地址。即*(second->pprev) = = first->next。

内核中经常需要通过进程的PID来获得进程描述符task_struct，顺序扫描进程链表并检查进程描述符的pid字段是可行但相当低效的。为了加速查找引入4个散列表，因为进程包含了表示不同类型的PID的字段，而且每个字段需要它自己的散列表。

4个散列表和进程描述符中的相关字段：

Hash表的类型 字段名 说明

PIDTYPE_PID pid 进程的PID

PIDTYPE_TGID tgid 线程组领头进程的PID

PIDTYPE_PGID pgrp 进程组领头进程的PID

PIDTYPE_SID session 会话领头进程的PID

内核初始化期间为4个散列表分配空间，并把它们的地址存入pid_hash数组。在start_kernel函数中调用了pidhash_init:

void __init pidhash_init(void)
{
	int i, j, pidhash_size;
	unsigned long megabytes = nr_kernel_pages >> (20 - PAGE_SHIFT);

	pidhash_shift = max(4, fls(megabytes * 4));
	pidhash_shift = min(12, pidhash_shift);
	pidhash_size = 1 << pidhash_shift;

	printk("PID hash table entries: %d (order: %d, %Zd bytes)\n",
		pidhash_size, pidhash_shift,
		PIDTYPE_MAX * pidhash_size * sizeof(struct hlist_head));

	for (i = 0; i < PIDTYPE_MAX; i++) {
		pid_hash[i] = alloc_bootmem(pidhash_size *
					sizeof(*(pid_hash[i])));
		if (!pid_hash[i])
			panic("Could not alloc pidhash!\n");
		for (j = 0; j < pidhash_size; j++)
			INIT_HLIST_HEAD(&pid_hash[i][j]);
	}
}

pidhash_shift是表索引的长度，注意这里有个printk，我系统启动的打印信息有这么一行：

[    0.000000] PID hash table entries: 4096 (order: 12, 16384 bytes)

说明我系统的pidhash_shift为12，这个值依赖于系统RAM的大小。例如：一个拥有512MB的RAM，每个散列表拥有4个页框，可以拥有2048个表项。pidhash_init函数中使用alloc_bootmem分配器为散列表分配内存(这是alloc_page，slab还未初始化)，pid_hash的第一维是散列表，第二维是每个散列表中的散列地址。每个地址会对应一个链表，所以这里初始化链表头，如下图：

PIDTYPE_MAX就是散列表的个数，在pid.h中有一个枚举：

enum pid_type
{
	PIDTYPE_PID,
	PIDTYPE_TGID,
	PIDTYPE_PGID,
	PIDTYPE_SID,
	PIDTYPE_MAX
};

用pid_hashfn宏把PID转化为表索引，即哈希地址：

#define pid_hashfn(x)    hash_long((unsigned long)x, pidhash_shift)

在32位体系结构中hash_long等价于：

unsigned long hash_long(unsigned long val, unsigned int bits)
{
       unsigned long hash = val * 0x9e370001UL;
       return hash >> (32 - bits);
}

这里我们使pidhash_shift为11，这样表索引的范围为0～2047，hash_long相当于(pid*0x9e370001)>>21。PID从0～32767会产生冲突，这里解决冲突的方法就是使用链表。如上图，PID号为199的和PID为29384的进程产生了冲突，被链在同一个哈希地址的链表上。

(199*0x9e370001)>>21 = 199，(29384*0x9e370001)>>21 = 199。

下面来看一下task_struct的pid字段，在task_struct中有：

struct pid pids[PIDTYPE_MAX];

struct pid
{
	int nr;
	struct hlist_node pid_chain;
	struct list_head pid_list;
};

nr是进程的PID，pid_chain是将发生冲突的pid链在这个pid_chain链表上，pid_list字段是同一个线程组，会话组或进程组的链接在pid_list链表上，如下图：

这个图里，PID为246的和PID为4351的pid发成冲突，所以链接在pid_chain链表上。同一个线程组的PID为4351的三个进程链接到pid_list上。