LinuxKernel-进程

[toc]

进程、轻量级进程和线程

进程是资源分配的实体,而线程是作业调度的基本单位。Linux使用轻量级进程来支持多线程应用程序,轻量级进程之间可以共享一部分资源,诸如地址空间、打开的文件等,通过将轻量级进程和线程关联起来就可以实现多线程应用程序。

进程描述符

进程描述符包含了与一个进程有关的所有信息,内容相当复杂。

进程的状态

可运行状态 TASK_RUNNING

此时,程序已被挂入运行队列,处于准备运行状态。一旦获得处理器使用权,即可进入运行状态。当进程获得处理器而运行时 ,state的值仍然为TASK_RUNNING,并不发生改变;但Linux会把一个专门用来指向当前运行任务的指针current指向它,以表示它是一个正在运行的进程。

可中断的等待状态 TASK_INTERRUPTIBLE

进程等待某些资源,被挂起。产生硬件中断、获得系统资源或传递一个信号都可能可以唤醒进程。

不可中断等待状态 TASK_UNINTERRUPTIBLE

这个状态被应用在内核中某些场景中,比如当进程需要对磁盘进行读写,而此刻正在DMA中进行着数据到内存的拷贝,如果这时进程休眠被打断(比如强制退出信号)那么很可能会出现问题,所以这时进程就会处于不可被打断的状态下。

暂停状态 TASK_STOPPED

收到SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU信号后,进入暂停状态。

跟踪状态 TASK_TRACED

程序由debugger程序暂停。

僵死状态 EXIT_ZOMBIE

子进程结束后父进程未调用wait类系统调用,则子进程成为僵尸进程。

僵尸撤销状态 EXIT_DEAD

进程即将释放它的所有资源,为了防止其余线程执行wait指令,将zombie状态转为dead状态。

标识一个进程

由于进程描述符与进程严格的一一对应,所以大部分对进程的引用是通过描述符指针进行的。

另一方面,也允许使用pid标识一个进程。对于一个多线程的进程而言,每个线程(即轻量级进程)都使用领头线程的pid,该值被存入进程描述符的tgid字段;当调用getpid系统调用时,返回的是tgid的值而不是pid的值,从这方面而言,可以说一个多线程应用的所有线程由相同的pid。

对于每个进程来说,Linux将两个相关的数据结构紧凑的存放在内存中,一个是与进程描述符有关的小数据结构thread_info, 另一个是内核态的进程堆栈。这块存储区域通常为2个页框,当几乎找不到连续的2个页框时,可以在编译时设置允许他们跨越一个单独的页框。thread_info占用最低的52个字节,栈从高地址往下增长,因而最多可以占用8140个字节。使用这种结构,则内核可以通过屏蔽esp寄存器的低12位获得thread_info的有效地址,效率较高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct thread_info {
struct task_struct *task; /* main task structure */
struct exec_domain *exec_domain; /* execution domain */
unsigned long flags; /* low level flags */
unsigned long status; /* thread-synchronous flags */
__u32 cpu; /* current CPU */
__s32 preempt_count; /* 0 => preemptable, <0 => BUG */


mm_segment_t addr_limit; /* thread address space:
0-0xBFFFFFFF for user-thead
0-0xFFFFFFFF for kernel-thread
*/
struct restart_block restart_block;

unsigned long previous_esp; /* ESP of the previous stack in case
of nested (IRQ) stacks
*/
__u8 supervisor_stack[0];
};

内核链表

双向链表

对于每个链表都实现一套源于操作会造成较大的浪费,因而Linux内核定义了list_head的结构。

1
2
3
struct list_head {
struct list_head *next, *prev;
};

针对这个双向链表,有一些宏、函数操作。

初始化

LIST_HEAD_INIT和LIST_HEAD都可以进行初始化(实质做的事情其实就是令前驱和后继都指向自身),不同的是前者需要提供一个实体的指针,而后者直接通过一个名称即可创建。

1
2
3
4
5
6
7
8
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

增删改查类

事实上,这里实现的双向链表是有头节点的,因而list_add函数是头插入;此外,有头节点这一特点也方便了之后的遍历等操作。

1
2
3
4
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
static inline int list_empty(const struct list_head *head);
static inline void list_splice(struct list_head *list, struct list_head *head); //从head位置将list拼入当前链表

删除操作比较有趣,他会调用内部函数删除当前链表头,同时将当前元素的双向指针设置为一些非零的地址。这样当非法访问到这些未被初始化的指针时,会产生缺页错误,从而方便我们进一步诊断问题。

1
2
3
4
5
6
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}

接下来是一些宏操作。

获取入口

list_entry返回一个类型为type、含有名为member地址位ptr的list_head的成员的结构体的地址, 实现方法又进一步调用了include/linux/kernel.h中的container_of宏和include/linux/stddef.h的offsetof宏。

1
2
3
4
5
6
7
8
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
1
2
3
4
5
6
7
8
9
10
11
12
/**
* container_of - cast a member of a structure out to the containing structure
*
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

1
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

对于offsetof宏而言,基地址选为0或其余任何值都不影响,选为0方便计算而已

对于container_of宏而言,第一步利用typeof获取member应有的类型,并将ptr赋给中间变量mptr。事实上完全可以省去这一步直接用ptr减去偏移量,不省略的原因在于,利用编译器在编译阶段对类型进行检查,保证ptr确实是member对应类型的指针。第二步是将该指针转换为char*类型并与偏移量相减,这也是一个值的注意的地方,指针相减并不是一般的数值相减,如果两个int指针相减,结果会是实际代数相减的1/4。所以为了获得实际的地址,我们应当把mptr指针强制转换为char 或void,这样就能获得包含该地址的结构体的首地址辣!

遍历

有两种方式进行遍历,prefetch是gcc用来提高效率的函数,用来预取数据,而__list_for_each则是最简单的遍历方式,linux代码开发者提示我们仅当链表较短时才使用他。

NOTE:仔细考察循环的方式,会发现并不会遍历到包含head的结构体,这就是存在头节点在链表遍历中的一个优势。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)

/**
* __list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*
* This variant differs from list_for_each() in that it's the
* simplest possible list iteration code, no prefetching is done.
* Use this for code that knows the list to be very short (empty
* or 1 entry) most of the time.
*/
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)

接下来说明一下prefetch函数。 预取

通过给 CPU 发送一个特殊的 hint 来表明之后某段内存区域马上会被访问,是可能的。在 Intel 64 架构上使用 prefetch 指令来达到这个目的。该指令接收一个内存地址;CPU 会在最近尽量将这些内容载入到缓存中。这样做可以防止 cache miss。

prefetch 使用得好可以很高效,不过一定要进行测试。prefetch 操作应该在数据被访问前进行,但不能和执行执行的时间间隔太接近。缓存的预载是异步进行的,也就是说数据载入和紧跟着的指令执行几乎是同时发生的。如果预取和数据访问时间太接近的话,CPU 可能来不及把数据载入到 cache,数据访问就发生了。这时候就会有 cache-miss。

另外还需要理解一点,与数据访问操作距离的 “近” 和 “远” 指的是指令执行的序列中的指令位置。考虑到程序的结构,我们不应该把 prefetch 放在同一函数内,而应放在数据放问之前的其它位置。可以放在完全不同的另外一个模块,例如,在日志模块中,一般在数据访问之前很可能会被调用到。不过真的这样做将会对代码的可读性造成极大的负面影响,并引入不明显的模块间依赖,这里说的是一种破罐破摔的技巧了。

在 C 语言中使用 prefetch,只需要使用 GCC 内置的:

1
Void __builtin_prefetch (const void *addr, ...)

编译器会自动把这个 prefetch 替换为对应架构下的 prefetch 汇编指令。

除了地址之外,函数还接收两个参数,两个数值常量。

  1. 该地址是读(传 0,默认值)还是写(传1)?
  2. 局部性有多强?3 表示最大,一直到 0 表示最小。0 的话表示这个值在使用过之后可以立刻从 cache 中清除,3 表示所以级别的 cache 都应该继续保持该值。

只要 CPU 能够预测下一次内存访问发生在什么位置,那么就会自己进行预取操作。预取在连续的内存访问情况下可以工作得很好,例如进行数组遍历的时候。如果进行随机内存访问的时候,预取就不是那么得高效了。

对应的,有另一种直接返回包含list_head的结构体的指针的遍历方式list_for_each_entry。

1
2
3
4
5
6
7
8
9
10
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop counter.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))

相应的,也有倒序遍历list_for_each_prev(pos, head)和list_for_each_entry_reverse(pos, head, member) ,这里不予赘述。

此外,观察上述遍历代码可以发现,并不支持在遍历时删除一些链表元素,因而链表开发者提供一种安全的遍历方式,使用一个中间变量获得当前链表头的下一个位置,从而允许我们在遍历时删除当前元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop counter.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)


/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop counter.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))

除了上述说明的一些操作,还有rcu、conitnue等一些其余的功能,暂不进行深入学习。

哈希链表

Linux 内核 hlist 详解

首先给出hlist的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* Double linked lists with a single pointer list head.
* Mostly useful for hash tables where the two pointer list head is
* too wasteful.
* You lose the ability to access the tail in O(1).
*/

struct hlist_head {
struct hlist_node *first;
};

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

使用两个数据结构进行设计是有深意的。首先对于一个哈希表而言,其必定存在大量的表项以尽可能避免冲突,因而对于每一项而言我们仅给他一个哈希链表的指针(即first),接下来我们使用pprev双指针来维护一致性,具体来说,我们可以考虑删除的情形:对于一个有前驱和后继的传统节点而言,删除一个元素n可以使用如下的方式:

1
2
n->prev->next = n->next;
n->next->prev = n->prev;

但是在这里这个方法并不奏效。对于除了首节点以外的所有节点,上述删除方式都是正确的,但是对于首节点而言,n->prev并不含有next指针,此方法不可行。如果单独考虑首节点的情况,不仅不优美更会影响效率。因而内核链表设计者给出了这样的方案,并不使用prev指向前一个节点,而是使用pprev指向前一个节点的next域,这其实是一个不影响功能实现的进一步细化,使得首节点也能很好地保持一致性。

参考下述的删除代码会有一个更好的理解。无论将要删除的节点位于链表何处,下述代码都能正确的运行。

1
2
3
4
5
6
7
8
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}

对于插入操作而言hlist和list大同小异,值的注意的是hlist并不是循环链表,因而在插入到链表结尾的时候需要注意以下空指针的情况。

对于遍历操作而言,涉及到一个GNU C的一个特性,该特性往往广泛应用于宏中。

1
2
3
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
pos = pos->next)

GNU C允许用小括号括起来的复合语句出现在一个表达式中。

例如:

1
2
3
4
5
int a = ({ int b = 8;
int c = 99;
b + c;
b + c - 10;
});

结果a = b + c - 10 = 97

因而在上述遍历中,该宏利用该特性在自增前偷偷利用prefetch预取数据,同时利用1来保证不影响结果,十分精妙。

对于“宿主”的遍历则如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* hlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop counter.
* @pos: the &struct hlist_node to use as a loop counter.
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry(tpos, pos, head, member) \
for (pos = (head)->first; \
pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)

这里pos是中间变量,tpos才是暴露出的接口指针。由于hlist没有头节点,而是以NULL作为遍历的结束,所以有必要引入pos来辅助遍历和判断遍历的结束。

此外hlist也实现了safe版本以供任意的删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
pos = n)

/**
* hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @tpos: the type * to use as a loop counter.
* @pos: the &struct hlist_node to use as a loop counter.
* @n: another &struct hlist_node to use as temporary storage
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
for (pos = (head)->first; \
pos && ({ n = pos->next; 1; }) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = n)

进程链表

进程链表将所有进程的描述符连接起来,每个tast_struct结构都包含一个list_head类型的tasks字段。

SET_LINKS和REMOVE_LINK宏可以从进程链表中插入、删除一个进程描述符,这些宏考虑了进程间地父子关系。具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define remove_parent(p)	list_del_init(&(p)->sibling)
#define add_parent(p, parent) list_add_tail(&(p)->sibling,&(parent)->children)

#define REMOVE_LINKS(p) do { \
if (thread_group_leader(p)) \
list_del_init(&(p)->tasks); \
remove_parent(p); \
} while (0)

#define SET_LINKS(p) do { \
if (thread_group_leader(p)) \
list_add_tail(&(p)->tasks,&init_task.tasks); \
add_parent(p, (p)->parent); \
} while (0)REMOVE_LINKS

在执行插入、删除操作前会检查当前进程是否是线程组组长,如果是的话则会额外地在进程链表头(init_task描述符,0进程或swapper进程的描述符)中进行插入删除,不然则只在线程父亲的chilidren链表中进行修改。

另一个常用的宏是for_each_process,该宏会遍历整个进程链表。

1
2
3
#define next_task(p)	list_entry((p)->tasks.next, struct task_struct, tasks)
#define for_each_process(p) \
for (p = &init_task ; (p = next_task(p)) != &init_task ; )

Linux早先的内核将所有可运行的进程放在一个链表中,每次调度不得不遍历整个链表以寻找最优进程。Linux2.6有所不同,它会在固定的时间内选出一个“最佳”的进程,花费的时间与可运行的进程数无关,在后面的章节会进行详细的说明。

进程间的关系

进程0和进程1是内核创建的,进程1(init)是所有进程的祖先。

在进程描述符中,有一些字段表示进程的亲属关系。

也有一些字段表示其非亲属关系。

pidhash表

内核经常需要通过pid值查找到对应的进程描述符指针,因而内核使用4个散列表加快查询速度。

散列表结构即为之前提到的哈希链表结构,每个表项内容存储一个指针。一个散列表的长度依赖于可用RAM的容量,一个系统拥有512MB的RAM,那么每个散列表就被存放在4个页框中,可以拥有2048个表项。 这句话是书上给出的,并不清楚如何从512MB的RAM推出只有2048个表项,也不能够明白为什么4个页框能拥有2048个表项。。。因而决定查阅一番源码:

首先给出pidhash表的初始化代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
* The pid hash table is scaled according to the amount of memory in the
* machine. From a minimum of 16 slots up to 4096 slots at one gigabyte or
* more.
*/
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]);
}
}

在具体深入探究原理之前,先说明几个有趣的小知识点:

  • %zd 用于输出size_t类型

  • 由于enum本质是用整数来一一对应枚举类型的,所以pidhash使用了如下的一种枚举类型enum pid_type

1
2
3
4
5
6
7
8
enum pid_type
{
PIDTYPE_PID,
PIDTYPE_TGID,
PIDTYPE_PGID,
PIDTYPE_SID,
PIDTYPE_MAX
};

此后即可使用PIDTYPE_MAX来初始化数组大小,用PIDTYPE_xxx来选择一维数组。其本质是用enum来代替人为define,十分值得学习。

  • bootmem分配器。Bootmem 内存分配器 这里我们暂时不过多地关注bottmem分配器的原理,留个坑有缘再见吧。。大概说来这个分配器是内核在引导时的一个物理内存分配器,它的实现简单,使用bitmap对内存进行管理,缺点在于bitmap不适合分配大物理内存,会消耗较多的时间空间。

  • fls函数,即find_the_last_bit_set。返回输入参数的最高有效bit位(从低位往左数最后的有效bit位)的序号,该序号与常规0起始序号不同,它是1起始的(当没有有效位时返回0)。

接下来考察一下pid哈希表的长度到底是如何确定的。。使用了nr_kernel_pages来确定megabytes的值,而前者大概是内存管理中的一个概念,留待后续第八章学完后补坑。。大体上暂时可以明确每个哈希表项内容就是之前学习的hlist的内容,也就是一个指针,在代码中可以看到使用sizeof来保证可移植性,那么此处就暂时到底,之后有缘相见。。

很多函数都使用hash_long ,他本质上做的是val*0x9e370001UL再截断到规定的位数。0x9e370001UL是一个神秘的数字,在源码中他被命名为GOLDEN_RATIO_PRIME, 其实这个数是对$2^{32}$做黄金分割后选取的最靠近分割点的素数,这样结果会比较满意,Knuth这么建议道。。

Linux利用链表来处理pid冲突的情况。当pid映射到了一个表项时,就用hlist将他们串起来。不过由于要追踪进程间的关系,pid散列表需要的数据结构十分复杂。比如,为了回收一个线程组的所有进程,那么通过tgid查只会返回一个进程描述符,为了更快的回收所有的资源,内核必须为每个线程组保留一个进程链表;同样的对于进程组、会话组都有类似的问题。事实上,pid使用如下的结构来方便地解决上述问题:

1
2
3
4
5
6
7
8
struct pid
{
/* Try to keep pid_chain in the same cacheline as nr for find_pid */
int nr;
struct hlist_node pid_chain;
/* list of pids with the same nr, only one of them is in the hash */
struct list_head pid_list;
};

其中,nr为pid号,pid_chain将哈希表中所有冲突的描述符串起来,而pid_list则将该组下所有的进程串起来。

最后介绍一些处理pid表的宏:

pid_task通过pid结构体中的链表指针返回整个进程描述符的地址,本质是对list_entry的一个应用。

1
2
#define pid_task(elem, type) \
list_entry(elem, struct task_struct, pids[type].pid_list)

do_while控制语句。遍历type类型(4个中1个)的链表中所有nr为who地内容,暴露task作为进程描述符接口。

1
2
3
4
5
6
7
8
9
10
11
12
#define do_each_task_pid(who, type, task)				\
if ((task = find_task_by_pid_type(type, who))) { \
prefetch((task)->pids[type].pid_list.next); \
do {

#define while_each_task_pid(who, type, task) \
} while (task = pid_task((task)->pids[type].pid_list.next,\
type), \
prefetch((task)->pids[type].pid_list.next), \
hlist_unhashed(&(task)->pids[type].pid_chain)); \
} \

返回type类型的pid链表中指定nr号的一个pid结构体。

1
2
3
4
5
6
7
8
9
10
11
12
struct pid * fastcall find_pid(enum pid_type type, int nr)
{
struct hlist_node *elem;
struct pid *pid;

hlist_for_each_entry(pid, elem,
&pid_hash[type][pid_hashfn(nr)], pid_chain) {
if (pid->nr == nr)
return pid;
}
return NULL;
}

attach_pid: 把task指向任务描述符插入到type类类表中nr号的位置,无论task之前nr号为多少都会置为给定的nr。

错误: 如果插入哈希表时没有冲突,那么直接加入并初始化task的pid_list链;如果产生了冲突,那么初始化task的pid_chain(但不加入!)并将pid_list链在之前冲突的进程的pid_list下面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int fastcall attach_pid(task_t *task, enum pid_type type, int nr)
{
struct pid *pid, *task_pid;

task_pid = &task->pids[type];
pid = find_pid(type, nr);
if (pid == NULL) {
hlist_add_head(&task_pid->pid_chain,
&pid_hash[type][pid_hashfn(nr)]);
INIT_LIST_HEAD(&task_pid->pid_list);
} else {
INIT_HLIST_NODE(&task_pid->pid_chain);
list_add_tail(&task_pid->pid_list, &pid->pid_list);
}
task_pid->nr = nr;

return 0;
}

??最开始读完这段代码还以为自己之前对于pid_chain和pid_list的理解有误。。仔细考虑一番后发现其实并没有错。这段代码if-else的逻辑并不是用于区分是否产生哈希冲突的,而是用于区分是否已经存在一个组长进程。本身pid_chain的结构就已经能够自动地处理哈希冲突了,所以我们只需要不重不漏的维护这个结构即可。

正确的说明:插入哈希表时如果不存在同一个nr的进程,那么应该新建一个哈希表项并加入pid_chain链中;如果存在同一个nr的进程,此时不是说明哈希表产生了冲突,而是说明有一个组长进程或类似的进程已经加入了,那么已经不再需要向pid_chain链中加入新节点,直接将当前节点缀到之前加入过的pid的pid_list后面即可。

通过阅读这段代码,能让人对于linux内核设计者对链表的设计思路有更加深刻的理解。。。按照个人以往的编程方式,大概率会用链表将一整个结构串起来,通过一个指针访问需要的结构,而不是将链表指针内嵌到结构中,学习到了。

上述代码的fastcall是一种调用方式,速度是更快,它通过寄存器ECX和EDX传递2个字,后面更多的仍然压栈。函数的调用规则(cdecl,stdcall,fastcall,pascal)

(10月30日勘误:fastcall的实现并未标准化!不同编译器的实现不同,上述贴出的博客实际是microsoft/gcc的标准,而另有一种Borland fastcall,其顺序为从左至右,三个参数分别为EAX, EDX和ECX, 在i386上的某些版本Linux也使用了此约定 X86调用约定

detach_pid:删除type链表中task对应的进程描述符。

hlist_unhashed检测某个哈希表节点是否没有被加入到散列表中,有可能某节点仅仅被初始化但尚未被加入到链表中。所以第一层if判断如果失败则无需修改pid_chain相关的表项内容,但如果加入了哈希表中,则应该对应在哈希表中执行一些操作。如果当前进程的pid_list下还有一些其余的进程,那么应该将pid_list下一个进程的chain再链回去保证哈希表的正确;如果只有当前一个进程占用了这个pid号,则应该考虑释放这个pid号供后续的进程使用。具体来说是通过一个循环检查其余类型的pidhash表中是否有人仍然在使用该号码,如果无人使用,则可以在pidmap中对该位进行清除供后人使用。

不过不太明白为什么有可能会出现没有加入到散列表的pid项??

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static fastcall int __detach_pid(task_t *task, enum pid_type type)
{
struct pid *pid, *pid_next;
int nr = 0;

pid = &task->pids[type];
if (!hlist_unhashed(&pid->pid_chain)) {
hlist_del(&pid->pid_chain);

if (list_empty(&pid->pid_list))
nr = pid->nr;
else {
pid_next = list_entry(pid->pid_list.next,
struct pid, pid_list);
/* insert next pid from pid_list to hash */
hlist_add_head(&pid_next->pid_chain,
&pid_hash[tynext_threadpe][pid_hashfn(pid_next->nr)]);
}
}

list_del(&pid->pid_list);
pid->nr = 0;

return nr;
}

void fastcall detach_pid(task_t *task, enum pid_type type)
{
int tmp, nr;

nr = __detach_pid(task, type);
if (!nr)
return;

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

free_pidmap(nr);
}

next_thread(task)返回TGID链表中task的下一个线程的描述符地址。由于pid_list是的双向循环链表,所以对传统的进程应用该函数会返回本身的描述符地址。

1
2
3
4
task_t fastcall *next_thread(const task_t *p)
{
return pid_task(p->pids[PIDTYPE_TGID].pid_list.next, PIDTYPE_TGID);
}

进程的组织

内核将所有处于TASK_RUNNING的进程组织在运行队列链表中,对于INTERRUPTTIBLE和UNINTERRUPTTIBLE状态进程则使用等待队列进行维护,对处于STOPPED、EXIT_ZOMBIE、EXIT_DEAD等简单的状态的进程不单独设计链表。

等待队列

等待队列由双向链表实现,每个元素中有一个睡眠进程,通过task_list字段串在同一个链表中;每个等待队列都有一个等待队列头,并通过自旋锁保证对双向链表的互斥访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct __wait_queue wait_queue_t;
struct __wait_queue {
unsigned int flags;
#define WQ_FLAG_EXCLUSIVE 0x01
struct task_struct * task;
wait_queue_func_t func;
struct list_head task_list;
};

struct __wait_queue_head {
spinlock_t lock;
struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;

并不懂自旋锁 学习一下 噢原来自旋锁其实就是忙等待的方式,如果需要的锁已被占用,则间隔一段时间再次不断尝试。当锁被持有时间较短时,自旋锁可以避免过多的进程调度和线程切换,因而经常被用于内核中。

当某个事件发生后,并不应该总是唤醒所有睡眠的进程。如多个进程正在等待某一个互斥资源时,而该资源仅能被一个进程占用,此时唤醒所有进程并无意义,仅需唤醒其中一个进程即可。因而在链表节点中存在flags字段用于区分互斥进程和非互斥进程,当flags字段为1时内核有选择的进行唤醒,而当flags字段为0时总是被唤醒。书上说这是“雷鸣般兽群”问题。。。神秘。。看到一篇博客说是“惊群”问题,这个可能还跟准确些。。Linux中的惊群问题/

对等待队列的操作

初始化

与之前见过的许多内核代码一样,对等待队列的初始化也有宏和函数两种方式,其中default_wake_function是在后续章节讲要讨论的try_to_wake_up函数的一个简单封装。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define __WAITQUEUE_INITIALIZER(name, tsk) {				\
.task = tsk, \
.func = default_wake_function, \
.task_list = { NULL, NULL } }

#define DECLARE_WAITQUEUE(name, tsk) \
wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk)

#define __WAIT_QUEUE_HEAD_INITIALIZER(name) { \
.lock = SPIN_LOCK_UNLOCKED, \
.task_list = { &(name).task_list, &(name).task_list } }

#define DECLARE_WAIT_QUEUE_HEAD(name) \
wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

static inline void init_waitqueue_head(wait_queue_head_t *q)
{
q->lock = SPIN_LOCK_UNLOCKED;
INIT_LIST_HEAD(&q->task_list);
}

static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
{
q->flags = 0;
q->task = p;
q->func = default_wake_function;
}

static inline void init_waitqueue_func_entry(wait_queue_t *q,
wait_queue_func_t func)
{
q->flags = 0;
q->task = NULL;
q->func = func;
}

DEFINE_WAIT初始化也可以用于声明一个链表节点变量,自动使用当前CPU上运行的进程描述符和autoremove_wake_function作为唤醒函数,这个唤醒函数如果成功唤醒进程,则调用list_del_init将该进程从WL中删除,否则不进行其他操作,函数执行结束,返回结果。

1
2
3
4
5
6
7
8
#define DEFINE_WAIT(name)						\
wait_queue_t name = { \
.task = current, \
.func = autoremove_wake_function, \
.task_list = { .next = &(name).task_list, \
.prev = &(name).task_list, \
}, \
}
增删改查

add_wait_queue将非互斥进程插入链表头,add_wait_queue_tail将非互斥进程插入链表尾,add_wait_queue_exclusive_locked则将一个互斥进程插入到链表尾,remove_wait_queue从WL中删去一个进程,waitqueue_active检查一个给定的WL是否非空。

设置唤醒条件

使用sleep_on函数对当前进程操作,设置为UNINTERRUPTIBLE状态并插入到对应的等待队列中,接下来调用调度程序选取另一个程序进行运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define	SLEEP_ON_VAR					\
unsigned long flags; \
wait_queue_t wait; \
init_waitqueue_entry(&wait, current);

#define SLEEP_ON_HEAD \
spin_lock_irqsave(&q->lock,flags); \
__add_wait_queue(q, &wait); \
spin_unlock(&q->lock);

#define SLEEP_ON_TAIL \
spin_lock_irq(&q->lock); \
__remove_wait_queue(q, &wait); \
spin_unlock_irqrestore(&q->lock, flags);


void fastcall __sched sleep_on(wait_queue_head_t *q)
{
SLEEP_ON_VAR

current->state = TASK_UNINTERRUPTIBLE;

SLEEP_ON_HEAD
schedule();
SLEEP_ON_TAIL
}

其中SLEEP_ON_VAR定义了等待队列的元素并使用当前的进程对其进行初始化,SLEEP_ON_HEAD使用自旋锁向等待队列中加入一个元素,SLEEP_ON_TAIL使用自旋锁从等待队列中删去任务。

interruptible_sleep_on几乎与之类似,不同之处只在于设置的状态不同,因而接收一个信号即可唤醒该进程。

sleep_on_timeout 和interruptible_sleep_on_timeout也与上述的两个函数类似,但它允许调用者定义一个时间间隔,经过该时间后内核将唤醒该进程。

1
2
3
4
5
6
7
8
9
10
11
12
long fastcall __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
{
SLEEP_ON_VAR

current->state = TASK_UNINTERRUPTIBLE;

SLEEP_ON_HEAD
timeout = schedule_timeout(timeout);
SLEEP_ON_TAIL

return timeout;
}

prepare_to_wait、prepare_to_wait_exclusive和finish_wait函数往往成套使用,用于提供更加丰富的循环控制方式。what is the difference between simple sleeping (using wait_event_*() functions) and advanced sleeping (using prepare_to_wait() function)? 而到底有何用处感觉并不太理解。。。有缘相见

对于非互斥的wait方式,使用&= ~WQ_FLAG_EXCLUSIVE来复位,对于互斥的方式则使用 |= WQ_FLAG_EXCLUSIVE来置位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void fastcall
prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
unsigned long flags;

wait->flags &= ~WQ_FLAG_EXCLUSIVE;
spin_lock_irqsave(&q->lock, flags);
if (list_empty(&wait->task_list))
__add_wait_queue(q, wait);
/*
* don't alter the task state if this is just going to
* queue an async wait queue callback
*/
if (is_sync_wait(wait))
set_current_state(state);
spin_unlock_irqrestore(&q->lock, flags);
}

void fastcall finish_wait(wait_queue_head_t *q, wait_queue_t *wait)
{
unsigned long flags;

__set_current_state(TASK_RUNNING);
/*
* We can check for list emptiness outside the lock
* IFF:
* - we use the "careful" check that verifies both
* the next and prev pointers, so that there cannot
* be any half-pending updates in progress on other
* CPU's that we haven't seen yet (and that might
* still change the stack area.
* and
* - all other users take the lock (ie we can only
* have _one_ other CPU that looks at or modifies
* the list).
*/
if (!list_empty_careful(&wait->task_list)) {
spin_lock_irqsave(&q->lock, flags);
list_del_init(&wait->task_list);
spin_unlock_irqrestore(&q->lock, flags);
}
}

wait_event和wait_event_interruptible使调用进程在等待队列上睡眠,一直到条件满足为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define __wait_event(wq, condition) 					\
do { \
DEFINE_WAIT(__wait); \
\
for (;;) { \
prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE); \
if (condition) \
break; \
schedule(); \
} \
finish_wait(&wq, &__wait); \
} while (0)

#define wait_event(wq, condition) \
do { \
if (condition) \
break; \
__wait_event(wq, condition); \
} while (0)

为了插入一个互斥进程,必须使用prepare_to_wait_exclusive或者add_wait_queue_exclusive进行插入,其余的所有函数都将以非互斥方式插入。

此外,除非使用DEFINE_WAIT或finish_wait,否则内核必须在唤醒等待进程后从等待队列中删除对应的元素。

进程的唤醒

在kernel/sched.c中定义了一些基本的唤醒函数。__wake_up_common是所有wake家族的核心函数,传入参数q为等待队列头,mode决定可否中断,nr_exclusive决定唤醒的互斥进程的数量,sync决定是同步唤醒sync,还是异步唤醒 async,key一般是NULL;通过函数注释可知,采用互斥唤醒时,不仅仅会唤醒一定数量的互斥进程,还会唤醒所有的非互斥进程

当该函数遍历等待队列,通过curr获取当前选取的进程描述符,通过判断该进程的信息和传入参数的关系进行一些操作。在说明这个看上去比较复杂的if语句前,我们先阐述一个容易让人忽视但十分重要的小细节:在一个等待等待队列中,一定是所有的非互斥进程在队列的开始位置,所有的互斥进程在队列的结束位置;这一点可以通过之前讨论过的如何添加一个互斥进程的方式得到印证。得知这一点后,wake函数中的if判断则容易理解了。。首先检查当前进程的唤醒函数是否已经有效地唤醒了进程(返回1),接下来检查互斥情况,当进程的flag标志为0时说明此时仍然是非互斥进程,应当继续进行循环;而当flag标志为1时,根据上述说明的布局结构可以保证此时已经尝试唤醒了所有非互斥进程,接下来只需要唤醒指定数量的互斥进程即可,因而if逻辑的后面一部分便是执行这样的业务逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
* wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
* number) then we wake all the non-exclusive tasks and one exclusive task.
*
* There are circumstances in which we can try to wake a task which has already
* started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
* zero in this (rare) case, and we handle it by continuing to scan the queue.
*/
static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
int nr_exclusive, int sync, void *key)
{
struct list_head *tmp, *next;

list_for_each_safe(tmp, next, &q->task_list) {
wait_queue_t *curr;
unsigned flags;
curr = list_entry(tmp, wait_queue_t, task_list);
flags = curr->flags;
if (curr->func(curr, mode, sync, key) &&
(flags & WQ_FLAG_EXCLUSIVE) &&
!--nr_exclusive)
break;
}
}

/**
* __wake_up - wake up threads blocked on a waitqueue.
* @q: the waitqueue
* @mode: which threads
* @nr_exclusive: how many wake-one or wake-many threads to wake up
*/
void fastcall __wake_up(wait_queue_head_t *q, unsigned int mode,
int nr_exclusive, void *key)
{
unsigned long flags;

spin_lock_irqsave(&q->lock, flags);
__wake_up_common(q, mode, nr_exclusive, 0, key);
spin_unlock_irqrestore(&q->lock, flags);
}

以__wake_up函数为核心,有如下的若干变体,这些宏均被定义在include/linux/wait.h中。

所有这些宏都考虑了处于可中断睡眠状态的进程,当一个宏不包含字符串interruptible则它会尝试唤醒所有的进程;名字中还有nr或all的宏会唤醒对应数量的互斥进程。

特别说明一下最后两个宏使用的函数:

  • __wake_up_locked:实现的功能同wake_up;区别在于此函数用于在调用此函数时,用户已经手动 spin_lock了此等待队列头的lock,这个函数存在的原因是同一个spin_lock在同一个线程中不能递归加锁。
  • __wake_up_sync:此函数唤醒一个进程后不会令其抢占CPU,不会改变之前使用CPU的进程情况;而对于其余的宏而言,调用它们时往往还检查唤醒进程的优先级,如果优先级高于系统中正在运行的进程,会在必要时调用schedule函数。。
1
2
3
4
5
6
7
8
#define wake_up(x)			__wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1, NULL)
#define wake_up_nr(x, nr) __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, nr, NULL)
#define wake_up_all(x) __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 0, NULL)
#define wake_up_interruptible(x) __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
#define wake_up_interruptible_nr(x, nr) __wake_up(x, TASK_INTERRUPTIBLE, nr, NULL)
#define wake_up_interruptible_all(x) __wake_up(x, TASK_INTERRUPTIBLE, 0, NULL)
#define wake_up_locked(x) __wake_up_locked((x), TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE)
#define wake_up_interruptible_sync(x) __wake_up_sync((x),TASK_INTERRUPTIBLE, 1)

进程资源限制

每个进程都有一组相关的资源限制,避免了用户过分使用系统资源。

当前进程的资源限制存放在current->signal->rlim字段下,该字段是rlimit结构的数组,每个资源限制对应一个数组元素。

1
2
3
4
struct rlimit {
unsigned long rlim_cur;
unsigned long rlim_max;
};

进程切换

为了控制进程的执行,内核必须有能力挂起进程和恢复进程的运行,这种行为被称为进程切换、任务切换或上下文切换。

硬件上下文

进程恢复执行前必须装入寄存器的一组数据被称为硬件上下文。Linux中硬件上下文一部分放在TSS段,剩余部分存放在内核堆栈中。

早期Linux版本利用x86体系的硬件支持,通过far jmp跳到新进程的TSS的段选择符来进行进程切换,CPU自动保存原本的硬件上下文,并装入新的硬件上下文。但出于下述原因,Linux2.6使用软件来进行进程切换:

  • 通过一组mov指令切换时,可以较好地检查装入数据的合法性,防止寄存器被恶意用户篡改。
  • 两种方法所需要的时间相同。

进程切换只发生在内核态。在进程切换前,用户态进程的寄存器已经保存在内核堆栈上。

任务状态段

x86体系提供了一个特殊的段结构TSS来存放硬件上下文。尽管Linux不使用硬件上下文切换,但是要求它为每个CPU创建一个TSS。有如下的两个主要原因:

  • 当某个CPU从用户态切换到内核态时,它从TSS中获取内核态堆栈的地址(后续章节会进一步说明
  • 当用户态进程试图通过in、out指令访问io端口时,CPU访问TSS段中的IO许可证位图检查该进程是否拥有相应的权限。

每当进程切换时,内核都将更新TSS中的某些字段;因而TSS段只反映CPU上当前运行的进程的特权级,而不为每个进程都保留TSS段。

TSS的段描述符S标志被清零,以说明TSS是系统段的情况;type为11、9表示这是一个TSS段;在intel的原始设计中,每个进程都有一个TSS段,因而type字段的第二个有效位被称为busy位,如果进程正在被执行则置为1,不过在Linux设计中每个CPU都只有一个TSS段,对应的是正在执行的进程,因而busy字段总是为1

thread字段

当进程切换时,硬件上下文必须保存在别处,因而Linux为CPU保留TSS而不是对每个进程保留TSS。在进程描述符中有一个类型为thread_struct的trhead字段,只要进程被切换出去,内核就把硬件上下文保存在这个结构中。

下面是i386架构下的硬件上下文内容。这个数据结构段不包括诸如eax、ebx的通用寄存器,他们的值保存在内核堆栈中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct thread_struct {
/* cached TLS descriptors. */
struct desc_struct tls_array[GDT_ENTRY_TLS_ENTRIES];
unsigned long esp0;

unsigned long sysenter_cs;
unsigned long eip;
unsigned long esp;
unsigned long fs;
unsigned long gs;
/* Hardware debugging registers */
unsigned long debugreg[8]; /* %%db0-7 debug registers */
/* fault info */
unsigned long cr2, trap_no, error_code;
/* floating point info */
union i387_union i387;
/* virtual 86 mode info */
struct vm86_struct __user * vm86_info;
unsigned long screen_bitmap;
unsigned long v86flags, v86mask, saved_esp0;
unsigned int saved_fs, saved_gs;
/* IO permissions */
unsigned long *io_bitmap_ptr;
/* max allowed port in the bitmap, in bytes: */
unsigned long io_bitmap_max;
};

执行进程切换

进程只可能在schedule函数执行时切换,后续章节会仔细叙述,这里我们只关注内核如何执行一个进程切换。

本质上说,进程切换由两步组成:

  • 切换页全局目录以安装一个新的地址空间,后续章节再具体说明
  • 切换内核堆栈和硬件上下文

switch_to宏

switch_to存在于include/asm-i386/system.h头中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define switch_to(prev,next,last) do {					\
unsigned long esi,edi; \
asm volatile("pushfl\n\t" \
"pushl %%ebp\n\t" \
"movl %%esp,%0\n\t" /* save ESP */ \
"movl %5,%%esp\n\t" /* restore ESP */ \
"movl $1f,%1\n\t" /* save EIP */ \
"pushl %6\n\t" /* restore EIP */ \
"jmp __switch_to\n" \
"1:\t" \
"popl %%ebp\n\t" \
"popfl" \
:"=m" (prev->thread.esp),"=m" (prev->thread.eip), \
"=a" (last),"=S" (esi),"=D" (edi) \
:"m" (next->thread.esp),"m" (next->thread.eip), \
"2" (prev), "d" (next)); \
} while (0)

首先说明宏中的标记1涉及的一些语法。

Need to figure out the meaning of following inline assembly code 博客告诉了我们movl $1f, %1是什么意思:这里$1f并不是一个通常的立即数,而是标号为1的代码的地址f表示从当前位置向后搜索到的第一个标号为1的代码,另有参数b表示向前搜索的标号。将1f 保存在到prev->eip中,这样当控制权从某个地方再次回到了prev进程后,代码就会从标号1指向的指令开始执行。

为了做测试,我写了非常挫的一些代码。。不加任何选项的编译下述会产生错误,加上-no-pie后才可以成功编译,这个错误的产生大概是因为$1f的原因。。Options for Code Generation Conventions 查阅GCC官方文档学习一下-fpic, -fPIC, -fpie, -fPIE这四个选项的意思。-fpic会产生position-independent code(PIC),通常用于共享库中。在该选项下,常量通过一个全局偏移表(global offset table, GOT)来访问,受到机器的限制,当该偏移表过大时,可以使用-fPIC选项,该选项允许更大的偏移表;-fpie, -fPIE是类似的功能,不过该选项只会产生用于链接为可知性文件的代码。

g++默认会加入pie选项,这产生了错误,因而加上-no-pie通知g++才能成功编译下述代码。。。具体原因不深入考究(),只能猜测是因为$1f指向了一段代码的地址,那么用pie的相对地址可能就会有一点问题?emm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
"=a" (last),"=S" (esi),"=D" (edi) \
:"m" (next->thread.esp),"m" (next->thread.eip), \
"2" (prev), "d" (next));
int main(int argc,char **argv){
int x = 1145;
void *y, *z;
__asm__ volatile(
"lea %2, %%eax\n\t"
"movl %%eax, %0 \n\t"
"movl $1f, %1\n\t"
"1:"
"xorl %%eax, %%eax"
: "=m"(y), "=m"(z)
: "m"(x)
: "eax"
);
printf("%p %p %p\n", y, &x, z);
return 0;
}

继续讨论switch_to宏的流程:

  • 将%eflags, %ebp压入prev的内核栈
  • 将%esp存储到prev.thread的字段esp中
  • 将next对应的esp存入到%esp寄存器中,此时由于esp的载入内核栈已经切换到了next对应的内核栈。根据之前在标识一个进程中所描述的结构我们直到,内核栈和进程描述符的地址是紧挨着的,所以切换内核栈也就意味着改变了当前的进程。
  • 将标号1对应的地址存放在prev.thread的eip字段中,这样当prev进程重新获得CPU时会从标号1处的代码开始执行。单纯修改thread.eip的值肯定是不能实现这个功能的,猜测其余地方会加载此处的thread.eip到%eip中?也有可能是根据函数调用栈的结构来指定返回的地址(感觉大概率是这样 不知道)? 当执行标号1处的代码时,prev首先将之前保存在prev栈中%ebp, %eflags都按顺序弹栈。由于当prev再次获得CPU时,一定是某些其他的进程调用switch_to函数,并且参数next是这里的prev,所以根据之前的说明可以保证esp已经替换成了prev的esp,因而标号1处直接弹栈是正确无误的,确实是对prev栈进行操作的。
  • 将next->thread.eip压入next的内核栈后,调用__switch_to宏。 (为什么要压入eip?)压入eip本质上是手动设置返回地址。首先要注意到jmp和call调用过程的不同之处,jmp是直接跳转,而call会将ip或ip+cs压入栈中再跳转;当跳转对象是一个过程时,过程结束后会调用ret指令,而ret本质就是pop ip, 因而当调用的过程__switch_to完成后,就会执行之前我们人工压栈的指令,即next->thread.eip,十分精妙。

除了汇编代码中的操作,在操作数列表中也隐含了一些操作。注意到操作数中%0, %1, %5, %6都是内存寻址方式,而剩余的一些操作数则都利用到了寄存器。在内联代码执行前,首先将prev存入到%eax寄存器、next存入到%edx寄存器,在代码执行完后,将%esi、%edi的内容输出到c语言变量esi与edi中,并将%eax的内容输出到last参数中。这里着重说明一下last参数的意义:该参数在switch_to宏中是一个输出变量,用于保存上一次是谁切换到了prev进程。由于进程总在不停地切换,仅仅知道prev即将切换到next是不够的,进一步知道之前是谁切换到了prev往往会很有用。考察整个代码可以知道,在prev开始切换时,会将自身的进程描述符地址保存到%eax寄存器中,在经过漫长的等待后prev又获得了CPU,此时上一位转手CPU的进程也一定冻结于未完成的switch_to宏中(因为进程切换只会发生在精心设计的函数中),自然也就已经将自身的地址覆盖在%eax中了,那么prev继续执行未完成的switch_to,执行标号1的代码,全部代码完成后将%eax寄存器的内容存入到last变量中,就能实现了通过last变量记录上一位转让CPU给prev的进程描述符地址。

最后,为啥要保存%esi, %edi呢?idk…但是这篇博客可能有一些参考价值 switch_to函数为什么要保存esi/edi/ebx/ebp? 我没有去深入探究GCC会如何处理内联汇编,也可能是因为调用switch_to宏的上下文可能有需求?暂时留坑。。

__switch_to函数

选取了i386的__switch_to函数,位于arch/i386/kernel/process.h文件中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
* switch_to(x,yn) should switch tasks from x to y.
*
* We fsave/fwait so that an exception goes off at the right time
* (as a call from the fsave or fwait in effect) rather than to
* the wrong process. Lazy FP saving no longer makes any sense
* with modern CPU's, and this simplifies a lot of things (SMP
* and UP become the same).
*
* NOTE! We used to use the x86 hardware context switching. The
* reason for not using it any more becomes apparent when you
* try to recover gracefully from saved state that is no longer
* valid (stale segment register values in particular). With the
* hardware task-switch, there is no way to fix up bad state in
* a reasonable manner.
*
* The fact that Intel documents the hardware task-switching to
* be slow is a fairly red herring - this code is not noticeably
* faster. However, there _is_ some room for improvement here,
* so the performance issues may eventually be a valid point.
* More important, however, is the fact that this allows us much
* more flexibility.
*
* The return value (in %eax) will be the "prev" task after
* the task-switch, and shows up in ret_from_fork in entry.S,
* for example.
*/
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
struct thread_struct *prev = &prev_p->thread,
*next = &next_p->thread;
int cpu = smp_processor_id();
struct tss_struct *tss = &per_cpu(init_tss, cpu);

/* never put a printk in __switch_to... printk() calls wake_up*() indirectly */

__unlazy_fpu(prev_p);

/*
* Reload esp0, LDT and the page table pointer:
*/
load_esp0(tss, next);

/*
* Load the per-thread Thread-Local Storage descriptor.
*/
load_TLS(next, cpu);

/*
* Save away %fs and %gs. No need to save %es and %ds, as
* those are always kernel segments while inside the kernel.
*/
asm volatile("movl %%fs,%0":"=m" (*(int *)&prev->fs));
asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->gs));

/*
* Restore %fs and %gs if needed.
*/
if (unlikely(prev->fs | prev->gs | next->fs | next->gs)) {
loadsegment(fs, next->fs);
loadsegment(gs, next->gs);
}

/*
* Now maybe reload the debug registers
*/
if (unlikely(next->debugreg[7])) {
loaddebug(next, 0);
loaddebug(next, 1);
loaddebug(next, 2);
loaddebug(next, 3);
/* no 4 and 5 */
loaddebug(next, 6);
loaddebug(next, 7);
}

if (unlikely(prev->io_bitmap_ptr || next->io_bitmap_ptr))
handle_io_bitmap(next, tss);

return prev_p;
}

关于fastcall,由于switch_to宏将prev和next分别存入到了%eax和%edx中,因而我认为此处的fastcall采用了Borland fastcall的实现(上文的pidhash表中的某处对此有更详细的说明),从左到右按照EAX, EDX和ECX的顺序读取参数;另一种猜测可能才更加是真实情况,那就是使用__attribute__regparm关键字指定函数取参数的方式,由于在代码中尚未发现这两个关键字,所以我最开始就排除了这种可能性,但事实上可以在编译内核时通过添加-mregparm=2选项实现寄存器传参 况且ULK自己都说是用regparm和attribute了,由gcc编译程序实现。。。

  • 首先看到的是smp_processor_id,(道听途说)该宏实际读取的是cpu_number的percpu变量,会从当前进程的thread_info结构中的cpu字段获得下标并将其保存在cpu局部变量中,关于这个变量在第五章会详细说明,这里只需要知道该函数会读取当前cpu的id;接下来根据所获得的cpu号初始化一个新的tss结构,使用next对应的esp0对其进行初始化。load_esp0的定义无法被vscode搜索到。。。其实就在/include/asm-i386/processor.h中,grep天下第一。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    static inline void load_esp0(struct tss_struct *tss, struct thread_struct *thread)
    {
    tss->esp0 = thread->esp0;
    /* This can only happen when SEP is enabled, no need to test "SEP"arately */
    if (unlikely(tss->ss1 != thread->sysenter_cs)) {
    tss->ss1 = thread->sysenter_cs;
    wrmsr(MSR_IA32_SYSENTER_CS, thread->sysenter_cs, 0);
    }
    }

  • 接下来看到unlazy_fpu函数,它会有选择保存prev进程中FPU、MMX、XMM寄存器中的内容,在本章博客后续的内容中会进一步说明它。
  • 然后将next使用的线程局部存储(Thread-Specific Data)段装入本地CPU的GDT中,这段代码藏在include/asm-i386/desc.h中,这里GDT_ENTRY_TLS_MIN定义为6。TSD用于多线程程序中变量的保护访问,这种类型的数据,程序中的每个线程都会分别维护一份变量副本。

    1
    2
    3
    4
    5
    6
    static inline void load_TLS(struct thread_struct *t, unsigned int cpu)
    {
    #define C(i) per_cpu(cpu_gdt_table, cpu)[GDT_ENTRY_TLS_MIN + i] = t->tls_array[i]
    C(0); C(1); C(2);
    #undef C
    }
  • 将fs和gs段寄存器的内容保存在prev相关字段中,并检查fs或gs段寄存器是否被prev或next中的任意一个使用(即非0),如果被使用则将next对应的段寄存器内容写回到fs和gs中。代码中首先用内联汇编存储了fs、gs的内容到prev相关字段,然后通过一个if判断对应四个值是否全0来决定是否要写回next的段寄存器结果。有意思的是,在查找unlikely宏的时候甚至用到了高深的正则表达式匹配方案egrep -r "^([^f]|[^i]f)+ unlikely\(" *,还蛮有意思的qaq egrep是拓展的正则匹配方案,可以直接使用诸如+, ?这类的符号。 linux中likely()和unlikely() unlikelylikely宏完全不影响if判断的结果,他们只是用于提示编译器更多关于“分支跳转”的情况,使得编译器更好的优化代码。loadsegment(seg, value)宏实现的功能正如上所述,但是内部实现还稍微更加复杂一些,因为当它检测到一个无效的段寄存器值时会采用一种fix-up的修正方法,在第十章会继续讨论这个宏,该宏存在于/include/asm-i386/system.h中。

  • next_p->thread.debugreg数组的内容装在db寄存器中,只有当next在使用调试寄存器时被挂起才需要进行这种操作。至此我们已经知道了C语言宏中###不同的用处了:# 可以将宏参数进行字符串化操作,而##则实现参数的拼接。C语言宏定义##连接符和#符的使用(转载)
1
2
3
4
#define loaddebug(thread,register) \
__asm__("movl %0,%%db" #register \
: /* no output */ \
:"r" (thread->debugreg[register]))
  • 当prev或next进程有自己IO位图时,应当对IO位图进行一些操作。由于进程很少修改IO权限位图,所以仅当进程即将实际访问IO端口时,真实位图才被拷贝进CPU的TSS中。结合代码可知,当next不具有自己的位图时,IOMAP的偏移量为一个指定的宏常量,真实值为0x8000,当next拥有自己的位图,且十分凑巧地与tss中的位图是同一个,那么直接修改偏移量为真实值;剩余的一种情况就是,next拥有自己位图,且不是tss中的同一个,需要更新位图到tss中,那么就将采用lazy模式,将偏移设置为一个指定宏常量,真实值为0x9000。当next尝试访问一个IO端口时,0x8000和0x9000都是tss段外地址,会产生异常,如果产生0x8000的异常,则函数发送一个SIGSEGV给用户进程;如果是0x9000的异常,则一场处理函数把进程位图拷贝到TSS中,把IO位图的偏移设置为实际偏移,并再一次执行汇编语言指令(啥汇编指令)。
1
2
3
4
5
6
7
8
9
10
11
12
13
static inline void
handle_io_bitmap(struct thread_struct *next, struct tss_struct *tss)
{
if (!next->io_bitmap_ptr) {
tss->io_bitmap_base = INVALID_IO_BITMAP_OFFSET;
return;
}
if (likely(next == tss->io_bitmap_owner)) {
tss->io_bitmap_base = IO_BITMAP_OFFSET;
return;
}
tss->io_bitmap_base = INVALID_IO_BITMAP_OFFSET_LAZY;
}
  • 最后一步,return prev。虽然看上去很简单,但还是蛮精妙的。由于我们希望保证%eax始终存储switch_to函数中被替换的进程描述符的地址,因而在经过__switch_to时我们应该采取一定的措施保护%eax的结果不被改变。这里用到了一个缺省的特点:C函数中的return默认会将值传递给%eax,因而实际上return prev实现的汇编操作为movl %edi, %eax; ret;,这样就保护了eax寄存器的内容。随后next进程即将从之前压入进程内核栈next->thread.eip的位置继续执行;如果next此前从未被挂起,则会从ret_from_fock()函数的起始位置开始(参考本博客后续fork、clone相关内容)。ULK上关于这个的表述大概率是错误的,它说next会从此前压入栈中的1号地址开始执行,根据我对这两个函数如此大篇幅的思考、理解,etahr我认为这是错误的XD。

保存与加载FPU、MMX和XMM寄存器

从80486DX开始,算术浮点单元(floating-poting unit, FPU)开始被集成到CPU中。为了兼容旧模式,浮点算术函数使用ESCAPE指令来执行,这些指令作用于包含在CPU中的浮点寄存器集。当一个进程使用ESCAPE指令,那么浮点寄存器的内容也属于硬件上下文,应当被保存。

在之后的Pentium模型中,Intel引入了一个新的汇编指令集,叫做MMX指令,用于加速多媒体应用程序的执行。MMX指令也作用于FPU的浮点寄存器,这样做的话缺点在于编程者无法将浮点指令和MMX指令混用,优点在于OS设计者能够忽略新的指令集,使得浮点单元的状态切换代码可以不加修改地应用到MMX指令集上。

MMX加速了多媒体应用的执行,因为它们在内部引入了单指令多数据流水线(single-instruction multiple-data, SIMD)PentiumIII模型拓展了这种SIMD地能力,引入了SSE拓展(Streaming SIMD Exetensions),该拓展为处理8个128位的寄存器(叫做XMM寄存器)的浮点值增加了功能;该寄存器不与FPU/MMX的寄存器重叠,因而可以与FPU/MMX指令混用。PentiumIV还引入了SSE2拓展,支持高精度的浮点值,与SSE使用同一XMM寄存器集。

80x86微处理器并不在TSS中自动保存FPU、MMX和XMM寄存器,但它提供了某种硬件支持,能在需要时保存这些寄存器的值:

  • 当硬件上下文切换时,设置TS标志

  • 当TS标志被设置时,执行ESCAPE、MMX、SSE等指令,控制单元就产生一个Device not available异常

TS标志的存在使得lazy模式成为可能,只有当真正需要协处理器时才恢复浮点寄存器的内容。

在进程描述符中有一个专门为了上述几个寄存器的选择性装入而引入的数据结构。

1
2
3
4
5
union i387_union {
struct i387_fsave_struct fsave;
struct i387_fxsave_struct fxsave;
struct i387_soft_struct soft;
};

对于老旧的无协处理器地CPU使用软件模拟协处理器,使用soft结构;对于有协处理器、MMX单元的CPU模型使用fsave结构;对于有SSE、SSE2拓展功能的CPU模型则使用fxsave结构。

在进程描述符中含有两个相应的标志:

  • 包含在thread_info描述符下status字段中的TS_USEDFPU标志。表示进程在当前执行过程中是否使用过FPU、MMX、XMM寄存器。
  • 包含在task_struct描述符下flags字段中的PF_USED_MATH标志,表示thread.i387子字段的内容是否有意义。在下述两种情况下该位会被清零(无意义):
    • 进程调用execve系统调用
    • 用户态下的一个进程开始执行一个信号处理程序(参见十一章)由于信号处理程序和原始进程的执行流是异步的,因而浮点寄存器的内容对信号处理程序来说可能是无意义的,不过由于内核在处理信号前会在i387结构体中保存浮点寄存器、处理完信号后恢复寄存器,所以信号处理程序可以使用数学协处理器。

保存FPU寄存器

fpu相关处理代码存在于/include/asm-i386/i387.h

__switch_to中我们调用过__unlazy_fpu函数,该函数检查TS标志位是否被置位,置位意味着prev使用过了相应的指令,内核必须保存相关的硬件上下文。

1
2
3
4
#define __unlazy_fpu( tsk ) do { \
if ((tsk)->thread_info->status & TS_USEDFPU) \
save_init_fpu( tsk ); \
} while (0)

save_init_fpu函数主要完成下述操作:

  • 把FPU内容转储到prev的进程描述符中,然后初始化FPU。如果使用到了SSE扩展,也应该实现类似的操作。这两个操作由一对功能强大的汇编指令完成。
  • 复位prev的TS标志。
  • 调用stts宏设置cr0的TS标志。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define stts() write_cr0(8 | read_cr0())

/*
* These must be called with preempt disabled
*/
static inline void __save_init_fpu( struct task_struct *tsk )
{
if ( cpu_has_fxsr ) {
asm volatile( "fxsave %0 ; fnclex"
: "=m" (tsk->thread.i387.fxsave) );
} else {
asm volatile( "fnsave %0 ; fwait"
: "=m" (tsk->thread.i387.fsave) );
}
tsk->thread_info->status &= ~TS_USEDFPU;
}


/*
* These disable preemption on their own and are safe
*/
static inline void save_init_fpu( struct task_struct *tsk )
{
preempt_disable();
__save_init_fpu(tsk);
stts();
preempt_enable();
}

装载FPU寄存器

当next进程恢复执行时,由于lazy模式浮点寄存器的内容尚未恢复;不过cr0的TS标志已经被__unlazy_fpu设置,因而当next第一次尝试执行相关指令时会产生一个异常;一场处理程序运行math_state_restore函数进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* 'math_state_restore()' saves the current math information in the
* old math state array, and gets the new ones from the current task
*
* Careful.. There are problems with IBM-designed IRQ13 behaviour.
* Don't touch unless you *really* know how it works.
*
* Must be called with kernel preemption disabled (in this case,
* local interrupts are disabled at the call-site in entry.S).
*/
asmlinkage void math_state_restore(struct pt_regs regs)
{
struct thread_info *thread = current_thread_info();
struct task_struct *tsk = thread->task;

clts(); /* Allow maths ops (or we recurse) */
if (!tsk_used_math(tsk))
init_fpu(tsk);
restore_fpu(tsk);
thread->status |= TS_USEDFPU; /* So we fnsave on switch_to() */
}

该函数首先清cr0的TS标志,接下来检查i387字段是否有效,如果字段无效则调用init_fpu,该函数初始化i387字段,并将PF_USED_MATH标志置位,然后在restore_fpu函数中同样通过一对强力的汇编指令将保存在i387中的寄存器内容载入FPU寄存器,最后将thread中的TS使用标志置位。

内核态使用FPU、MMX和SSE/SSE2单元

内核在使用这些单元时应当避免干扰用户态进程的计算,因而:

  • 在使用协处理器前,如果用户设置了TS_USEDFPU标志,内核必须调用kernel_fpu_begin(),其本质是save_init_fpu()来保护寄存器的内容,然后重新设置cr0的TS标志。
  • 在使用完协处理器后,内核必须调用kernel_fpu_end()来设置cr0的TS标志。

稍后在用户执行协处理器指令时,math_state_restore将恢复寄存器内容。

事实上,当用户态在使用协处理器时,内核执行kernel_fpu_begin 的时间会相当长,以至于无法达到加速的目的;因而内核只有在有限的场合能够使用这些单元,典型情况如:移动、清除大内存区字段,计算校验和等。

创建进程