# Linux 进程PID创建原理
知识推理
我们可以站在设计者的角度来解决这个问题，直接来知识推理：
- PID代表了进程（包括LWP，轻量级进程，也即线程，之前有讲过）的ID
- PID可以被复用，毕竟进程的PCB（进程控制块）被销毁了，肯定要归还PID的
- 那么我们就需要一个容器来管理PID的分配和回收
- PID只是一个数字而已（0---N（最大上限））
- 通过上述分析，我们得出特性：保存数字最简单、快捷、空间复杂度低是我们的需求
- 很容易联想到位图（这就够了）
既然决定了使用位图来表示0---N的PID，那么这时我们就可以继续联想，CPU有没有提供一些指令集，让我们来操作位图呢？答案是必须的，肯定有特殊指令集来加速位图的访问，因为我们使用位图就是要足够的快，那么我们来看这两个I386的指令：
- BTS -- Bit Test and Set (位测试并置位)
- BTS 指令先将指定位的值存储到 CF 标志中，然后设置该位的值（0或者1）
- mov $0x80, %al # 将 1000 0000 放入到ax的低8位中
- btsl $7, %eax # 将eax的第7位（下标从0开始），那么这时由于al的第7位已经是1，所以在执行 bts 指令后，这个 1 会被存在 CF 中，然后对该位置 1 ，置位后 eax 自然是 0x80
- SBB -- Integer Subtraction with Borrow（整数减法与借位）
- eg：SBB EAX, imm32【intel 汇编语法，imm32为32位立即数】。将源操作数 imm32 和 Eflags 中CF（进位）标志位相加，然后减掉 EAX中原来的值，然后将结果放入到目的操作数EAX中。也即：EAX = imm32 + CF -EAX
那么我们来看看如何使用这两个指令来设置bit位，同时获取设置之前的值。看如下代码：
- 我们使用bts 指令将 addr的第nr位设置为1，之前的结果放在了CF标志位中
- 我们使用sbb指令执行：oldbit = oldbit + CF - oldbit ，这时很容易得出：oldbit = CF，也即我们取出了CF标志位中的值
# AT&T语法 这里我们令：nr为要设置的bit位 addr为bit为的起始地址 oldbit为nr位被设置为1之前的值（0或者1）
btsl nr,addr
sbbl oldbit,oldbit
那么我们趁热打铁，看看接下来我们要使用的linux内核函数test_and_set_bit的原理。肯定有读者不会内联汇编，不过不打紧，我就已经翻译成了上面的汇编。不过还是得说下怎么来的，内联汇编中从输出也即 =r 这里开始就是0下标，往后就是1、2，所以这里得出%0 ： oldbit ，%1：ADDR，%2：nr
#define ADDR (*(volatile long *) addr) // 将addr转为long指针同时解引用，这时可以获取addr指向的内存单元中的32 为值，I386为32位机，所以这里 long为32位
static __inline__ int test_and_set_bit(int nr, volatile unsigned long * addr)
{
int oldbit;
// 别慌，内联汇编而已，我书里有讲
__asm__ __volatile__( LOCK_PREFIX // 锁前缀，用于保证 btsl 指令的原子性
"btsl %2,%1 // 等于：btsl nr,addr
sbbl %0,%0 " // 等于：sbbl oldbit,oldbit
:"=r" (oldbit),"=m" (ADDR)
:"Ir" (nr) : "memory");
return oldbit;
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Linux源码分析
在了解以上知识后，现在我们之前来看linux内核的源码，在创建进程时如何分配PID。我们很容易的得出结论：调用alloc_pidmap函数分配PID。
asmlinkage int sys_fork(struct pt_regs regs) // 创建进程系统调用入口
{
return do_fork(SIGCHLD, regs.esp, ®s, 0, NULL, NULL);
}
long do_fork(unsigned long clone_flags,
unsigned long stack_start,
struct pt_regs *regs,
unsigned long stack_size,
int __user *parent_tidptr,
int __user *child_tidptr){
struct task_struct *p;
...
p = copy_process(clone_flags, stack_start, regs, stack_size, parent_tidptr, child_tidptr); // 从当前进程，也即创建进程的父进程的资源信息中拷贝并设置 PCB（task_struct） 信息
...
}
struct task_struct *copy_process(unsigned long clone_flags,
unsigned long stack_start,
struct pt_regs *regs,
unsigned long stack_size,
int __user *parent_tidptr,
int __user *child_tidptr){
...
if (clone_flags & CLONE_IDLETASK) // 内核线程的IDEL线程 总是为0
p->pid = 0;
else { // 其他进程，调用alloc_pidmap函数分配PID
p->pid = alloc_pidmap();
if (p->pid == -1)
goto bad_fork_cleanup;
}
...
}
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
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
接下来我们来分析alloc_pidmap函数即可。通过源码我们得知：
- 进程分配的最大PID个数由 PID_MAX_DEFAULT 来控制，最大为 PID_MAX_LIMIT
- 分配pid时，首先尝试通过 last_pid + 1 来计算偏移量来计算pid
- 如果last_pid分配失效，那么我们只能通过扫描位图数组中的位图，来寻找可用的pid
/*
* 最大400万个pid
*/
\#define PID_MAX_LIMIT (4*1024*1024)
/*
* 控制分配给进程的默认最大pid 32768
*/
\#define PID_MAX_DEFAULT 0x8000
// 一个page页的移位大小
\#define PAGE_SHIFT 12
// 一个page页的大小 2^12 = 4 KB
\#define PAGE_SIZE (1UL << PAGE_SHIFT)
// 总共有需要多少个 byte（entry） ，这里除8，就是算出多少个entry
\#define PIDMAP_ENTRIES (PID_MAX_LIMIT/PAGE_SIZE/8)
// 每一页的bit位数
\#define BITS_PER_PAGE (PAGE_SIZE*8)
// 每一页bit位的掩码，用于和pid计算 offset 偏移量，也即要设置的页的bit位 nr
\#define BITS_PER_PAGE_MASK (BITS_PER_PAGE-1)
// 用于表示一个页 4kb 中的位图结构。我们可以得出一页最多能表示的位为：4KB * 1024 * 8 = 32768 bit
typedef struct pidmap {
atomic_t nr_free; // 可用的位个数
void *page; // page页的地址
} pidmap_t;
// 全局位图数组
static pidmap_t pidmap_array[PIDMAP_ENTRIES] =
{ [ 0 ... PIDMAP_ENTRIES-1 ] = { ATOMIC_INIT(BITS_PER_PAGE), NULL } };
// 最大pid为限制进程的 32768
int pid_max = PID_MAX_DEFAULT;
// 当前最后一个进程的pid
int last_pid;
// 当达到最大的pid_max时，重置last_pid 为 RESERVED_PIDS （为何为300？因为内核线程的id分配通常小于300，所以如果从0开始，没有意义，内核线程将不会销毁，那么更不会归还PID）
\#define RESERVED_PIDS 300
// 初始化位图数组的第一项
void __init pidmap_init(void)
{
int i;
pidmap_array->page = (void *)get_zeroed_page(GFP_KERNEL); // 分配一页空页
set_bit(0, pidmap_array->page); // 将第0位置1 （进程0位特殊内核线程IDLE TASK）
atomic_dec(&pidmap_array->nr_free); // 减少可用个数
...
}
// 分配可用位图
int alloc_pidmap(void)
{
int pid, offset, max_steps = PIDMAP_ENTRIES + 1; // 最大寻找可用位图entry的step
pidmap_t *map;
pid = last_pid + 1; // 将最后分配的进程pid + 1
if (pid >= pid_max) // 达到最大限制，那么还原pid为300
pid = RESERVED_PIDS;
offset = pid & BITS_PER_PAGE_MASK; // 计算要设置的page页的位偏移量
map = pidmap_array + pid / BITS_PER_PAGE; // 获取当前要设置的map结构（很容易计算：数组起始地址 + 当前pid / 每一页的数量 【这里算出了偏移量】 = pidmap_array数组的首地址 + 偏移量 联想下指针的 *(p+N)操作遍历数组）
if (likely(map->page && !test_and_set_bit(offset, map->page))) { // 存放位图的page页存在，且test_and_set_bit 设置成功，并且返回的oldbit为0，那么获取pid成功。减少当前map的可用位数，同时更新last_pid
return_pid:
atomic_dec(&map->nr_free);
last_pid = pid;
return pid;
}
if (!offset || !atomic_read(&map->nr_free)) { // 偏移量为0（被IDEL TASK用）或者 当前位图中的位已经分配完，那么查找下一个可用的位图
next_map:
map = next_free_map(map, &max_steps);
if (!map) // pidmap_array数组遍历完毕还是没找到，那么失败退出
goto failure;
offset = 0; // 重置偏移量，表示从新找到的map的第0个bit处开始找，因为这里已经不是第一个map的0下标，所以没有问题
}
/*
* 查找当前获取到的位图的可用的bit位
*/
scan_more:
offset = find_next_zero_bit(map->page, BITS_PER_PAGE, offset);
if (offset >= BITS_PER_PAGE) // 查找了当前map所有的bit位，都没有找到，那么继续获取下一个map
goto next_map;
if (test_and_set_bit(offset, map->page)) // 找到可用位，那么原子性设置该位，设置失败，那么继续执行scan_more，找到可用的位
goto scan_more;
/* 通过扫描位图，获取到pid，那么我们首先获取到当前位所处的页，然后根据每页的数量BITS_PER_PAGE和当前偏移量来计算PID，很简单：每页BITS_PER_PAGE个位，那么只需要 当前map的页 * BITS_PER_PAGE + 偏移量即可 */
pid = (map - pidmap_array) * BITS_PER_PAGE + offset;
goto return_pid; // 返回pid
failure: // 失败后返回-1
return -1;
}
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191