前言

在《[apue] 进程控制那些事儿 》一文中，曾提到进程 ID 并不是唯一的，在整个系统运行期间一个进程 ID 可能会出现好多次。

> ./pid fork and exec child 18687 [18687] child running wait child 18687 return 0 fork and exec child 18688 [18688] child running wait child 18688 return 0 fork and exec child 18689 ... wait child 18683 return 0 fork and exec child 18684 [18684] child running wait child 18684 return 0 fork and exec child 18685 [18685] child running wait child 18685 return 0 fork and exec child 18687 [18687] child running wait child 18687 return 0 duplicated pid find: 18687, total 31930, elapse 8

如果一直不停的 fork 子进程，在 Linux 上大约 8 秒就会得到重复的 pid，在 macOS 上大约是一分多钟。

... [32765] child running wait child 32765 return 0 fork and exec child 32766 [32766] child running wait child 32766 return 0 fork and exec child 32767 [32767] child running wait child 32767 return 0 fork and exec child 300 [300] child running wait child 300 return 0 fork and exec child 313 [313] child running wait child 313 return 0 fork and exec child 314 [314] child running wait child 314 return 0 ...

并且在 Linux 上 pid 的分配范围是 [300, 32768)，约 3W 个；在 macOS 上是 [100，99999)，约 10W 个。

为何会产生这种差异？Linux 上是如何检索并分配空闲 pid 的？带着这个问题，找出系统对应的内核源码看个究竟。

源码分析

和《[kernel] 带着问题看源码 —— setreuid 何时更新 saved-set-uid (SUID)》一样，这里使用 bootlin 查看内核 3.10.0 版本源码，关于 bootlin 的简单介绍也可以参考那篇文章。

进程 ID 是在 fork 时分配的，所以先搜索 sys_fork：

整个搜索过程大概是 sys_fork -> do_fork -> copy_process -> alloc_pid -> alloc_pidmap，下面分别说明。

copy_process

sys_fork & do_fork 都比较简单，其中 do_fork 主要调用 copy_process 复制进程内容，这个函数很长，直接搜索关键字 pid ：

 /*  * This creates a new process as a copy of the old one,  * but does not actually start it yet.  *  * It copies the registers, and all the appropriate  * parts of the process environment (as per the clone  * flags). The actual kick-off is left to the caller.  */ static struct task_struct *copy_process(unsigned long clone_flags,                     unsigned long stack_start,                     unsigned long stack_size,                     int __user *child_tidptr,                     struct pid *pid,                     int trace) {     int retval;     struct task_struct *p;      ...     /* copy all the process information */     retval = copy_semundo(clone_flags, p);     if (retval)         goto bad_fork_cleanup_audit;     retval = copy_files(clone_flags, p);     if (retval)         goto bad_fork_cleanup_semundo;     retval = copy_fs(clone_flags, p);     if (retval)         goto bad_fork_cleanup_files;     retval = copy_sighand(clone_flags, p);     if (retval)         goto bad_fork_cleanup_fs;     retval = copy_signal(clone_flags, p);     if (retval)         goto bad_fork_cleanup_sighand;     retval = copy_mm(clone_flags, p);     if (retval)         goto bad_fork_cleanup_signal;     retval = copy_namespaces(clone_flags, p);     if (retval)         goto bad_fork_cleanup_mm;     retval = copy_io(clone_flags, p);     if (retval)         goto bad_fork_cleanup_namespaces;     retval = copy_thread(clone_flags, stack_start, stack_size, p);     if (retval)         goto bad_fork_cleanup_io;      if (pid != &init_struct_pid) {         retval = -ENOMEM;         pid = alloc_pid(p->nsproxy->pid_ns);         if (!pid)             goto bad_fork_cleanup_io;     }      p->pid = pid_nr(pid);     p->tgid = p->pid;      ...     if (likely(p->pid)) {         ptrace_init_task(p, (clone_flags & CLONE_PTRACE) || trace);          if (thread_group_leader(p)) {             if (is_child_reaper(pid)) {                 ns_of_pid(pid)->child_reaper = p;                 p->signal->flags |= SIGNAL_UNKILLABLE;             }              p->signal->leader_pid = pid;             p->signal->tty = tty_kref_get(current->signal->tty);             attach_pid(p, PIDTYPE_PGID, task_pgrp(current));             attach_pid(p, PIDTYPE_SID, task_session(current));             list_add_tail(&p->sibling, &p->real_parent->children);             list_add_tail_rcu(&p->tasks, &init_task.tasks);             __this_cpu_inc(process_counts);         }         attach_pid(p, PIDTYPE_PID, pid);         nr_threads++;     }      ...     return p;  bad_fork_free_pid:     if (pid != &init_struct_pid)         free_pid(pid); bad_fork_cleanup_io:     if (p->io_context)         exit_io_context(p); bad_fork_cleanup_namespaces:     exit_task_namespaces(p); bad_fork_cleanup_mm:     if (p->mm)         mmput(p->mm); bad_fork_cleanup_signal:     if (!(clone_flags & CLONE_THREAD))         free_signal_struct(p->signal); bad_fork_cleanup_sighand:     __cleanup_sighand(p->sighand); bad_fork_cleanup_fs:     exit_fs(p); /* blocking */ bad_fork_cleanup_files:     exit_files(p); /* blocking */ bad_fork_cleanup_semundo:     exit_sem(p); bad_fork_cleanup_audit:     audit_free(p); bad_fork_cleanup_policy:     perf_event_free_task(p);     if (clone_flags & CLONE_THREAD)         threadgroup_change_end(current);     cgroup_exit(p, 0);     delayacct_tsk_free(p);     module_put(task_thread_info(p)->exec_domain->module); bad_fork_cleanup_count:     atomic_dec(&p->cred->user->processes);     exit_creds(p); bad_fork_free:     free_task(p); fork_out:     return ERR_PTR(retval); }

copy_process 的核心就是各种资源的拷贝，表现为 copy_xxx 函数的调用，如果有对应的 copy 函数失败了，会 goto 到整个函数末尾的 bad_fork_cleanup_xxx 标签进行清理，copy 调用与清理顺序是相反的，保证路径上的所有资源能得到正确释放。

在 copy_xxx 调用的末尾，搜到了一段与 pid 分配相关的代码：

    if (pid != &init_struct_pid) {         retval = -ENOMEM;         pid = alloc_pid(p->nsproxy->pid_ns);         if (!pid)             goto bad_fork_cleanup_io;     }      p->pid = pid_nr(pid);     p->tgid = p->pid;

首先判断进程不是 init 进程才给分配 pid (参数 pid 在 do_fork 调用 copy_process 时设置为 NULL，所以这里 if 条件为 true 可以进入)，然后通过 alloc_pid 为进程分配新的 pid。

在继续分析 alloc_pid 之前，先把搜索到的另一段包含 pid 代码浏览下：

    if (likely(p->pid)) {         ptrace_init_task(p, (clone_flags & CLONE_PTRACE) || trace);          if (thread_group_leader(p)) {             if (is_child_reaper(pid)) {                 ns_of_pid(pid)->child_reaper = p;                 p->signal->flags |= SIGNAL_UNKILLABLE;             }              p->signal->leader_pid = pid;             p->signal->tty = tty_kref_get(current->signal->tty);             attach_pid(p, PIDTYPE_PGID, task_pgrp(current));             attach_pid(p, PIDTYPE_SID, task_session(current));             list_add_tail(&p->sibling, &p->real_parent->children);             list_add_tail_rcu(&p->tasks, &init_task.tasks);             __this_cpu_inc(process_counts);         }         attach_pid(p, PIDTYPE_PID, pid);         nr_threads++;     }

如果 pid 分配成功，将它们设置到进程结构中以便生效，主要工作在 attach_pid，限于篇幅就不深入研究了。

alloc_pid

代码不长，就不删减了：

 struct pid *alloc_pid(struct pid_namespace *ns) {     struct pid *pid;     enum pid_type type;     int i, nr;     struct pid_namespace *tmp;     struct upid *upid;      pid = kmem_cache_alloc(ns->pid_cachep, GFP_KERNEL);     if (!pid)         goto out;      tmp = ns;     pid->level = ns->level;     for (i = ns->level; i >= 0; i--) {         nr = alloc_pidmap(tmp);         if (nr < 0)             goto out_free;          pid->numbers[i].nr = nr;         pid->numbers[i].ns = tmp;         tmp = tmp->parent;     }      if (unlikely(is_child_reaper(pid))) {         if (pid_ns_prepare_proc(ns))             goto out_free;     }      get_pid_ns(ns);     atomic_set(&pid->count, 1);     for (type = 0; type < PIDTYPE_MAX; ++type)         INIT_HLIST_HEAD(&pid->tasks[type]);      upid = pid->numbers + ns->level;     spin_lock_irq(&pidmap_lock);     if (!(ns->nr_hashed & PIDNS_HASH_ADDING))         goto out_unlock;     for ( ; upid >= pid->numbers; --upid) {         hlist_add_head_rcu(&upid->pid_chain,                 &pid_hash[pid_hashfn(upid->nr, upid->ns)]);         upid->ns->nr_hashed++;     }     spin_unlock_irq(&pidmap_lock);  out:     return pid;  out_unlock:     spin_unlock_irq(&pidmap_lock); out_free:     while (++i <= ns->level)         free_pidmap(pid->numbers + i);      kmem_cache_free(ns->pid_cachep, pid);     pid = NULL;     goto out; }

代码不长但是看得云里雾里，查找了一些相关资料，3.10 内核为了支持容器，通过各种 namespace 做资源隔离，与 pid 相关的就是 pid_namespace 啦。这东西还可以嵌套、还可以对上层可见，所以做的很复杂，可以开一个单独的文章去讲它了。这里为了不偏离主题，暂时搁置，直接看 alloc_pidmap 完事儿，感兴趣的可以参考附录 6。

alloc_pidmap

到这里才涉及到本文核心，每一行都很重要，就不做删减了：

static int alloc_pidmap(struct pid_namespace *pid_ns) {     int i, offset, max_scan, pid, last = pid_ns->last_pid;     struct pidmap *map;      pid = last + 1;     if (pid >= pid_max)         pid = RESERVED_PIDS;     offset = pid & BITS_PER_PAGE_MASK;     map = &pid_ns->pidmap[pid/BITS_PER_PAGE];     /*      * If last_pid points into the middle of the map->page we      * want to scan this bitmap block twice, the second time      * we start with offset == 0 (or RESERVED_PIDS).      */     max_scan = DIV_ROUND_UP(pid_max, BITS_PER_PAGE) - !offset;     for (i = 0; i <= max_scan; ++i) {         if (unlikely(!map->page)) {             void *page = kzalloc(PAGE_SIZE, GFP_KERNEL);             /*              * Free the page if someone raced with us              * installing it:              */             spin_lock_irq(&pidmap_lock);             if (!map->page) {                 map->page = page;                 page = NULL;             }             spin_unlock_irq(&pidmap_lock);             kfree(page);             if (unlikely(!map->page))                 break;         }         if (likely(atomic_read(&map->nr_free))) {             for ( ; ; ) {                 if (!test_and_set_bit(offset, map->page)) {                     atomic_dec(&map->nr_free);                     set_last_pid(pid_ns, last, pid);                     return pid;                 }                 offset = find_next_offset(map, offset);                 if (offset >= BITS_PER_PAGE)                     break;                 pid = mk_pid(pid_ns, map, offset);                 if (pid >= pid_max)                     break;             }         }         if (map < &pid_ns->pidmap[(pid_max-1)/BITS_PER_PAGE]) {             ++map;             offset = 0;         } else {             map = &pid_ns->pidmap[0];             offset = RESERVED_PIDS;             if (unlikely(last == offset))                 break;         }         pid = mk_pid(pid_ns, map, offset);     }     return -1; }

Linux 实现 pid 快速检索的关键，就是通过位图这种数据结构，在系统页大小为 4K 的情况下，一个页就可以表示 4096 * 8 = 32768 个 ID，这个数据刚好是《[apue] 进程控制那些事儿 》中实测的最大进程 ID 值，看起来 Linux 只用一个内存页就解决了 pid 的快速检索、分配、释放等问题，兼顾了性能与准确性，不得不说确实精妙。

pid 范围

继续进行之前，先确定几个常量的值：

/* PAGE_SHIFT determines the page size */ #define PAGE_SHIFT	12 #define PAGE_SIZE	(_AC(1,UL) << PAGE_SHIFT) #define PAGE_MASK	(~(PAGE_SIZE-1))      /*  * This controls the default maximum pid allocated to a process  */ #define PID_MAX_DEFAULT (CONFIG_BASE_SMALL ? 0x1000 : 0x8000)  /*  * A maximum of 4 million PIDs should be enough for a while.  * [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.]  */ #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 :  	(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))      /*  * Define a minimum number of pids per cpu.  Heuristically based  * on original pid max of 32k for 32 cpus.  Also, increase the  * minimum settable value for pid_max on the running system based  * on similar defaults.  See kernel/pid.c:pidmap_init() for details.  */ #define PIDS_PER_CPU_DEFAULT    1024 #define PIDS_PER_CPU_MIN    8   #define BITS_PER_PAGE		(PAGE_SIZE * 8) #define BITS_PER_PAGE_MASK	(BITS_PER_PAGE-1)  #define PIDMAP_ENTRIES		((PID_MAX_LIMIT+BITS_PER_PAGE-1)/BITS_PER_PAGE)       int pid_max = PID_MAX_DEFAULT;  #define RESERVED_PIDS		300  int pid_max_min = RESERVED_PIDS + 1; int pid_max_max = PID_MAX_LIMIT;

它们受页大小、系统位数、CONFIG_BASE_SMALL 宏的影响，宏仅用于内存受限系统，可以理解为总为 0。列表看下 4K、8K 页大小与 32 位、64 位系统场景下各个常量的取值：

结论：

• 32 位系统 pid 上限为 32768
• 64 位系统 pid 上限为 4194304 (400 W+)
• 32 位系统只需要 1 个页面就可以存储所有 pid
• 64 位系统需要 128 个页面存储所有 pid，不过具体使用几个页面视 PAGE_SIZE 大小而定

搜索 pid_max 全局变量的引用，发现还有下面的逻辑：

void __init pidmap_init(void) {     /* Veryify no one has done anything silly */     BUILD_BUG_ON(PID_MAX_LIMIT >= PIDNS_HASH_ADDING);      /* bump default and minimum pid_max based on number of cpus */     pid_max = min(pid_max_max, max_t(int, pid_max,                 PIDS_PER_CPU_DEFAULT * num_possible_cpus()));     pid_max_min = max_t(int, pid_max_min,                 PIDS_PER_CPU_MIN * num_possible_cpus());     pr_info("pid_max: default: %u minimum: %un", pid_max, pid_max_min);      init_pid_ns.pidmap[0].page = kzalloc(PAGE_SIZE, GFP_KERNEL);     /* Reserve PID 0. We never call free_pidmap(0) */     set_bit(0, init_pid_ns.pidmap[0].page);     atomic_dec(&init_pid_ns.pidmap[0].nr_free);     init_pid_ns.nr_hashed = PIDNS_HASH_ADDING;      init_pid_ns.pid_cachep = KMEM_CACHE(pid,             SLAB_HWCACHE_ALIGN | SLAB_PANIC); }

重点看 pid_max & pid_max_min，它们会受系统 CPU 核数影响，对于我测试机：

> uname -p x86_64 > getconf PAGE_SIZE 4096 > cat /proc/cpuinfo | grep 'processor' | wc -l 2 > cat /proc/cpuinfo | grep 'cpu cores' | wc -l 2

为 64 位系统，页大小 4K，共有 2 * 2 = 4 个核，PID_MAX_LIMIT = 4194304、PID_MAX_DEFAULT = 32768、pid_max_cores (按核数计算的 PID_MAX 上限) 为 1024 * 4 = 4096、pid_min_cores (按核数计算的 PID_MAX 下限) 为 8 *４= 32；初始化时 pid_max = 32768、pid_max_max = 4194304、pid_max_min = 301；经过 pidmap_init 后，pid_max 被设置为 min (pid_max_max, max (pid_max, pid_max_cores)) = 32768、pid_max_min 被设置为 max (pid_max_min, pid_min_cores) = 301。

这里有一行 pr_info 打印了最终的 pid_max & pid_max_min 的值，通过 dmesg 查看：

> dmesg | grep pid_max [    0.621979] pid_max: default: 32768 minimum: 301

与预期相符。

CPU 核数超过多少时会影响 pid_max 上限？简单计算一下： 32768 / 1024 = 32。当总核数超过 32 时，pid_max 的上限才会超过 32768；CPU 核数超过多少时会影响 pid_max 下限？301 / 4 = 75，当总核数超过 75 时，pid_max 的下限才会超过 301。下表列出了 64 位系统 4K 页面不同核数对应的 pid max 的上下限值：

可见虽然 pid_max 能到 400W+，实际根据核数计算的话没有那么多，pidmap 数组仅占用个位数的槽位。

另外 pid_max 也可以通过 proc 文件系统调整：

> su Password: $ echo 131072 > /proc/sys/kernel/pid_max $ cat /proc/sys/kernel/pid_max 131072 $ suspend  [1]+  Stopped                 su > ./pid ... [20004] child running wait child 20004 return 0 duplicated pid find: 20004, total 129344, elapse 74

经过测试，未调整前使用测试程序仅能遍历 31930 个 pid，调整到 131072 后可以遍历 129344 个 pid，看来是实时生效了。

搜索相关的代码，发现在 kernel/sysctl.c 中有如下逻辑：

static struct ctl_table kern_table[] = {     ...     {         .procname= "pid_max",         .data= &pid_max,         .maxlen= sizeof (int),         .mode= 0644,         .proc_handler= proc_dointvec_minmax,         .extra1= &pid_max_min,         .extra2= &pid_max_max,     },     ...     { } };

看起来 proc 文件系统是搭建在 ctl_table 数组之上，后者直接包含了要被修改的全局变量地址，实现"实时"修改。而且，ctl_table 还通过对 pid_max_min & pid_max_max 标识了修改的范围，如果输入超过了范围将返回错误：

$ echo 300 > /proc/sys/kernel/pid_max bash: echo: write error: Invalid argument $ echo 4194305 > /proc/sys/kernel/pid_max bash: echo: write error: Invalid argument

可以实时修改 pid_max  的另外一个原因还与 PIDMAP_ENTRIES 有关，详情见下节。

最后补充一点，pidmap_init 是在 start_kernel 中调用的，后者又被 BIOS setup 程序所调用，整体调用链是这样：

boot/head.S -> start_kernel -> pidmap_init

start_kernel 中就是一堆 xxx_init 初始化调用：

 asmlinkage void __init start_kernel(void) {     char * command_line;     extern const struct kernel_param __start___param[], __stop___param[];      /*      * Need to run as early as possible, to initialize the      * lockdep hash:      */     lockdep_init();     smp_setup_processor_id();     debug_objects_early_init();      /*      * Set up the the initial canary ASAP:      */     boot_init_stack_canary();      cgroup_init_early();      local_irq_disable();     early_boot_irqs_disabled = true;      /*      * Interrupts are still disabled. Do necessary setups, then      * enable them      */     boot_cpu_init();     page_address_init();     pr_notice("%s", linux_banner);     setup_arch(&command_line);     mm_init_owner(&init_mm, &init_task);     mm_init_cpumask(&init_mm);     setup_command_line(command_line);     setup_nr_cpu_ids();     setup_per_cpu_areas();     smp_prepare_boot_cpu();/* arch-specific boot-cpu hooks */      build_all_zonelists(NULL, NULL);     page_alloc_init();      pr_notice("Kernel command line: %sn", boot_command_line);     parse_early_param();     parse_args("Booting kernel", static_command_line, __start___param,             __stop___param - __start___param,             -1, -1, &unknown_bootoption);      jump_label_init();      /*      * These use large bootmem allocations and must precede      * kmem_cache_init()      */     setup_log_buf(0);     pidhash_init();     vfs_caches_init_early();     sort_main_extable();     trap_init();     mm_init();      /*      * Set up the scheduler prior starting any interrupts (such as the      * timer interrupt). Full topology setup happens at smp_init()      * time - but meanwhile we still have a functioning scheduler.      */     sched_init();     /*      * Disable preemption - early bootup scheduling is extremely      * fragile until we cpu_idle() for the first time.      */     preempt_disable();     if (WARN(!irqs_disabled(), "Interrupts were enabled *very* early, fixing itn"))         local_irq_disable();     idr_init_cache();     perf_event_init();     rcu_init();     tick_nohz_init();     radix_tree_init();     /* init some links before init_ISA_irqs() */     early_irq_init();     init_IRQ();     tick_init();     init_timers();     hrtimers_init();     softirq_init();     timekeeping_init();     time_init();     profile_init();     call_function_init();     WARN(!irqs_disabled(), "Interrupts were enabled earlyn");     early_boot_irqs_disabled = false;     local_irq_enable();      kmem_cache_init_late();      /*      * HACK ALERT! This is early. We're enabling the console before      * we've done PCI setups etc, and console_init() must be aware of      * this. But we do want output early, in case something goes wrong.      */     console_init();     if (panic_later)         panic(panic_later, panic_param);      lockdep_info();      /*      * Need to run this when irqs are enabled, because it wants      * to self-test [hard/soft]-irqs on/off lock inversion bugs      * too:      */     locking_selftest();  #ifdef CONFIG_BLK_DEV_INITRD     if (initrd_start && !initrd_below_start_ok &&             page_to_pfn(virt_to_page((void *)initrd_start)) < min_low_pfn) {         pr_crit("initrd overwritten (0x%08lx < 0x%08lx) - disabling it.n",                 page_to_pfn(virt_to_page((void *)initrd_start)),                 min_low_pfn);         initrd_start = 0;     } #endif     page_cgroup_init();     debug_objects_mem_init();     kmemleak_init();     setup_per_cpu_pageset();     numa_policy_init();     if (late_time_init)         late_time_init();     sched_clock_init();     calibrate_delay();     pidmap_init();     anon_vma_init(); #ifdef CONFIG_X86     if (efi_enabled(EFI_RUNTIME_SERVICES))         efi_enter_virtual_mode(); #endif     thread_info_cache_init();     cred_init();     fork_init(totalram_pages);     proc_caches_init();     buffer_init();     key_init();     security_init();     dbg_late_init();     vfs_caches_init(totalram_pages);     signals_init();     /* rootfs populating might need page-writeback */     page_writeback_init(); #ifdef CONFIG_PROC_FS     proc_root_init(); #endif     cgroup_init();     cpuset_init();     taskstats_init_early();     delayacct_init();      check_bugs();      acpi_early_init(); /* before LAPIC and SMP init */     sfi_init_late();      if (efi_enabled(EFI_RUNTIME_SERVICES)) {         efi_late_init();         efi_free_boot_services();     }      ftrace_init();      /* Do the rest non-__init'ed, we're now alive */     rest_init(); }

类似 Linux 0.11 中的 main。

pid 分配

先看看 pid 在 Linux 中是如何存放的：

struct pidmap {     atomic_t nr_free;     void *page; };  struct pid_namespace {     ...     struct pidmap pidmap[PIDMAP_ENTRIES];     int last_pid;     ... };

做个简单说明：

• pidmap.page 指向分配的内存页
• pidmap.nr_free 表示空闲的 pid 数量，如果为零就表示分配满了，不必浪费时间检索
• pid_namespace.pidmap 数组用于存储多个 pidmap，数组大小是固定的，以 64 位 4K 页面计算是 128；实际并不分配这么多，与上一节中的 pid_max 有关，并且是在分配 pid 时才分配相关的页面，属于懒加载策略，这也是上一节可以实时修改 pid_max 值的原因之一
• pid_namespace.last_pid 用于记录上次分配位置，方便下次继续检索空闲 pid

下面进入代码。

初始化

    pid = last + 1;     if (pid >= pid_max)         pid = RESERVED_PIDS;     offset = pid & BITS_PER_PAGE_MASK;     map = &pid_ns->pidmap[pid/BITS_PER_PAGE];

函数开头，已经完成了下面的工作：

• 将起始检索位置设置为 last 的下个位置、达到最大位置时回卷 (pid)
• 确定起始 pid 所在页面 (map)
• 确定起始 pid 所在页中的位偏移 (offset)

这里简单补充一点位图的相关操作：

• pid / BITS_PER_PAGE：获取 bit 所在位图的索引，对于测试机这里总为 0 (只分配一个内存页)；
• pid & BITS_PER_PAGE_MAX：获取 bit 在位图内部偏移，与操作相当于取余，而性能更好

经过处理，可使用 pid_ns->pidmap[map].page[offset] 定位这个 pid (注：page[offset] 是种形象的写法，表示页面中第 N 位，实际需要使用位操作宏)。

遍历页面

    max_scan = DIV_ROUND_UP(pid_max, BITS_PER_PAGE) - !offset;     for (i = 0; i <= max_scan; ++i) {         if (unlikely(!map->page)) {             ...         }         if (likely(atomic_read(&map->nr_free))) {             ...         }         if (map < &pid_ns->pidmap[(pid_max-1)/BITS_PER_PAGE]) {             ++map;             offset = 0;         } else {             map = &pid_ns->pidmap[0];             offset = RESERVED_PIDS;             if (unlikely(last == offset))                 break;         }         pid = mk_pid(pid_ns, map, offset);     }

做个简单说明：

• 外层 for 循环用来遍历 pidmap 数组，对于测试机遍历次数 max_scan == 1，会遍历两遍
  • 第一遍是 (last_pid, max_pid)
  • 第二遍是 (RESERVED_PIDS, last_pid]
  • 保证即使 last_pid 位于页面中间，也能完整的遍历整个 bitmap
• 第一个 if 用于首次访问时分配内存页
• 第二个 if 用于当前 pidmap 内搜索空闲 pid
• 第三个 if 用于判断是否遍历到 pidmap 数组末尾。注意 map 是个 pidmap 指针，所以需要对比地址；(pid_max-1)/BITS_PER_PAGE 就是最后一个有效 pidmap 的索引
  • 若未超过末尾，递增 map 指向下一个 pidmap，重置 offset 为 0
  • 若超过末尾，回卷 map 指向第一个 pidmap，offset 设置为 RESERVED_PIDS
    • 若回卷后到了之前遍历的位置 (last)，说明所有 pid 均已耗尽，退出外层 for 循环
• 根据新的位置生成 pid 继续上面的尝试

对于回卷后 offset = RESERVED_PIDS 有个疑问——是否设置为 pid_max_min 更为合理？否则打破了之前设置 pid_max_min 的努力，特别是当 CPU 核数大于 75 时，pid_max_min 是有可能超过 300 的。

列表考察下“不同的页面数” & “pid 是否位于页面第一个位置” (offset == 0) 对于多次遍历的影响：

表中根据页面数和 offset 推算出了 max_scan 的值，从而得到遍历次数，example 列每一子列都是一个独立的用例，其中：N-rear 表示第 N 页的后半部分，N-front 表示前半部分，不带后缀的就是整页遍历。逗号分隔的数字表示一个可能的页面遍历顺序。

从表中可以观察到，当 offset == 0 时，整个页面是从头到尾遍历的，不需要多一次遍历；而当 offset > 0 时，页面是从中间开始遍历的，需要多一次遍历。这就是代码 - !offset 蕴藏的奥妙：当 offset == 0 时会减去一次多余的遍历！

下面考察下第一次进入的场景 (以测试机为例)：

/*  * PID-map pages start out as NULL, they get allocated upon  * first use and are never deallocated. This way a low pid_max  * value does not cause lots of bitmaps to be allocated, but  * the scheme scales to up to 4 million PIDs, runtime.  */ struct pid_namespace init_pid_ns = {     .kref = {         .refcount       = ATOMIC_INIT(2),     },     .pidmap = {         [ 0 ... PIDMAP_ENTRIES-1] = { ATOMIC_INIT(BITS_PER_PAGE), NULL }     },     .last_pid = 0,     .level = 0,     .child_reaper = &init_task,     .user_ns = &init_user_ns,     .proc_inum = PROC_PID_INIT_INO, }; EXPORT_SYMBOL_GPL(init_pid_ns);

last_pid 初始化为 0，所以初始 pid = 1，offset != 0，遍历次数为 2。不过因为是首次分配，找到第一个空闲的 pid 就会返回，不会真正遍历 2 次。这里我有个疑惑：空闲的 pid 会返回 < RESERVED_PIDS 的值吗？这与观察到的现象不符，看起来有什么地方设置了 last_pid，使其从 RESERVED_PIDS 开始，不过搜索整个库也没有找到与 RESERVED_PIDS、pid_max_min、last_pid 相关的代码，暂时存疑。

再考察运行中的情况，offset > 0，遍历次数仍然为 2，会先遍历后半部分，如没有找到空闲 pid，设置 offset = RESERVED_PIDS、同页面再进行第 2 次遍历，此时遍历前半部分，符合预期。

多页面的情况与此类似，就不再推理了。

页面分配

        if (unlikely(!map->page)) {             void *page = kzalloc(PAGE_SIZE, GFP_KERNEL);             /*              * Free the page if someone raced with us              * installing it:              */             spin_lock_irq(&pidmap_lock);             if (!map->page) {                 map->page = page;                 page = NULL;             }             spin_unlock_irq(&pidmap_lock);             kfree(page);             if (unlikely(!map->page))                 break;         }

之前讲过，页面采用懒加载策略，所以每次进来得先判断下内存页是否分配，如果未分配，调用 kzalloc 进行分配，注意在设置 map->page 时使用了自旋锁保证多线程安全性。若分配页面成功但设置失败，释放内存页面，直接使用别人分配好的页面；若页面分配失败，则直接中断外层 for 循环、失败退出。

页内遍历

        if (likely(atomic_read(&map->nr_free))) {             for ( ; ; ) {                 if (!test_and_set_bit(offset, map->page)) {                     atomic_dec(&map->nr_free);                     set_last_pid(pid_ns, last, pid);                     return pid;                 }                 offset = find_next_offset(map, offset);                 if (offset >= BITS_PER_PAGE)                     break;                 pid = mk_pid(pid_ns, map, offset);                 if (pid >= pid_max)                     break;             }         }

检查 map->nr_free 字段，若大于 0 表示还有空闲 pid，进入页面查找，否则跳过。第一次分配页面时会将内容全部设置为 0，但 nr_free 是在另外的地方初始化的：

    .pidmap = {         [ 0 ... PIDMAP_ENTRIES-1] = { ATOMIC_INIT(BITS_PER_PAGE), NULL }     },

它将被设置为 BITS_PER_PAGE，对于 4K 页面就是 32768。接下来通过两个宏进行空闲位查找：test_and_set_bit & find_next_offset，前者是一个位操作宏，后者也差不多：

#define find_next_offset(map, off)					 		find_next_zero_bit((map)->page, BITS_PER_PAGE, off)

委托给 find_next_zero_bit，这个位操作函数。定义位于汇编语言中，太过底层没有贴上来，不过看名称应该能猜个七七八八。因为是整数位操作，可以使用一些类似 atomic 的手段保证多线程安全，所以这里没有施加额外的锁，例如对于 test_and_set_bit 来说，返回 0 就是设置成功，那就能保证同一时间没有其它线程在设置同一个比特位，是线程安全的；反之，返回 1 表示已有其它线程占了这个坑，咱们就只能继续“负重前行”了~

对于占坑成功的线程，atomic_dec 减少空闲 nr_free 数，注意在占坑和减少计数之间还是有其它线程插进来的可能，这会导致插入线程以为有坑位实际上没有，从而白遍历一遍。不过这样做不会产生错误结果，且这个间隔也比较短，插进来的机率并不高。

在返回新 pid 之前记得更新 pid_namespace.last_pid：

/*  * We might be racing with someone else trying to set pid_ns->last_pid  * at the pid allocation time (there's also a sysctl for this, but racing  * with this one is OK, see comment in kernel/pid_namespace.c about it).  * We want the winner to have the "later" value, because if the  * "earlier" value prevails, then a pid may get reused immediately.  *  * Since pids rollover, it is not sufficient to just pick the bigger  * value.  We have to consider where we started counting from.  *  * 'base' is the value of pid_ns->last_pid that we observed when  * we started looking for a pid.  *  * 'pid' is the pid that we eventually found.  */ static void set_last_pid(struct pid_namespace *pid_ns, int base, int pid) {     int prev;     int last_write = base;     do {         prev = last_write;         last_write = cmpxchg(&pid_ns->last_pid, prev, pid);     } while ((prev != last_write) && (pid_before(base, last_write, pid))); }  /*  * If we started walking pids at 'base', is 'a' seen before 'b'?  */ static int pid_before(int base, int a, int b) {     /*      * This is the same as saying      *      * (a - base + MAXUINT) % MAXUINT < (b - base + MAXUINT) % MAXUINT      * and that mapping orders 'a' and 'b' with respect to 'base'.      */     return (unsigned)(a - base) < (unsigned)(b - base); }

更新也得考虑线程竞争的问题：这里在判断 compare_exchange 的返回值之外，还判断了新的 last_pid (last_write) 和给定的 pid 参数哪个距离原 last_pid (base) 更远，只设置更远的那个，从而保证在竞争后，last_pid 能反应更真实的情况。

内层 for 是无穷循环且 offset 单调增长，需要一个结束条件，这就是 offset > BITS_PER_PAGE；另外一个条件是pid >= pid_max，这个主要用于 max_pid 不是整数页面的情况，例如 43 个 CPU 核对应的 pid_max = 44032，占用 2 个内存页且第二页并不完整 (44032 - 32768 = 11264，< 32768)，此时就需要通过来终止内层遍历了。为些需要根据最新 offset 更新当前遍历的 pid：

static inline int mk_pid(struct pid_namespace *pid_ns,         struct pidmap *map, int off) {     return (map - pid_ns->pidmap)*BITS_PER_PAGE + off; }

细心的读者可能发现了，对于 pid 位于页面中间的场景，回卷后第二次遍历该页面时，仍然是从头遍历到尾，没有在中间提前结束 (last_pid)，多遍历了 N-rear 这部分。

对于这一点，我是这样理解的：这一点点浪费其实微不足道，多写几个 if 判断节约的 CPU 时间可能还补偿不了指令流水被打断造成的性能损失。

pid 释放

进程结束时释放 pid，由于之前说过的原因，Linux 支持容器需要对 pid 进行 namespace 隔离，导致这一块前期的逻辑有点偏离主题 (且没太看懂)，就看看具体的 pid 释放过程得了：

static void free_pidmap(struct upid *upid) {     int nr = upid->nr;     struct pidmap *map = upid->ns->pidmap + nr / BITS_PER_PAGE;     int offset = nr & BITS_PER_PAGE_MASK;      clear_bit(offset, map->page);     atomic_inc(&map->nr_free); }

还是经典的 nr / BITS_PER_PAGE 确认页面索引、nr & BITS_PER_PAGE_MASK 确认 pid 所在比特位偏移；一个 clear_bit 优雅的将比特位清零；一个 atomic_inc 优雅的增加页面剩余空闲 pid 数。简洁明了，毋庸多言。

内核小知识

第一次看内核源码，发现有很多有趣的东西，下面一一说明。

likely & unlikely

很多 if 条件中都有这个，不清楚是干什么的，翻来定义看一看：

# ifndef likely #  define likely(x)	(__builtin_expect(!!(x), 1)) # endif # ifndef unlikely #  define unlikely(x)	(__builtin_expect(!!(x), 0)) # endif

条件 x 使用 !! 处理后将由整数变为 0 或 1，然后传递给 __builtin_expect，likely 第二个参数为 1，unlikely 为 0。经过一翻 google，这个是编译器 (gcc) 提供的分支预测优化函数：

long __builtin_expect(long exp, long c);

第一个参数是条件；第二个是期望值，必需是编译期常量；函数返回值为 exp 参数。GCC v2.96 引入，用来帮助编译器生成汇编代码，如果期望值为 1，编译器将条件失败放在 jmp 语句；如果期望值为 0，编译器将条件成功放在 jmp 语句。实现更小概率的指令跳转，这样做的目的是提升 CPU 指令流水成功率，从而提升性能。

        if (unlikely(!map->page)) {             void *page = kzalloc(PAGE_SIZE, GFP_KERNEL);             /*              * Free the page if someone raced with us              * installing it:              */             spin_lock_irq(&pidmap_lock);             if (!map->page) {                 map->page = page;                 page = NULL;             }             spin_unlock_irq(&pidmap_lock);             kfree(page);             if (unlikely(!map->page))                 break;         }         if (likely(atomic_read(&map->nr_free))) {             for ( ; ; ) {                 if (!test_and_set_bit(offset, map->page)) {                     atomic_dec(&map->nr_free);                     set_last_pid(pid_ns, last, pid);                     return pid;                 }                 offset = find_next_offset(map, offset);                 if (offset >= BITS_PER_PAGE)                     break;                 pid = mk_pid(pid_ns, map, offset);                 if (pid >= pid_max)                     break;             }         }

以页面分配和页内遍历为例，这里有 1 个 likely 和 2 个 unlikely，分别说明：

• 第一个 unlikely 用来判断页面是否为空，除第一次进入外，其它情况下此页面都是已分配状态，所以 !map->page 倾向于 0，这里使用 unlikely；
• 第二个 unlikely 用来判断页面是否分配失败，正常情况下 !map->page 倾向于 0，这里使用 unlikely；
• 第三个 likely 用来判断页面是否已分配完毕，正常情况下 atomic_read(&map->nr_free) 结果倾向于 > 0，这里使用 likely。

总结一下，likely & unlikely 并不改变条件结果本身，在判断是否进入条件时完全可以忽略它们！如果大部分场景进入条件，使用 likely；如果大多数场景不进入条件，使用 unlikely。

为何编译器不能自己做这个工作？深入想想，代码只有在执行时才能知道哪些条件经常返回 true，而这已经离开编译型语言生成机器代码太远了，所以需要程序员提前告知编译器怎么生成代码。对于解释执行的语言，这方面可能稍好一些。

最后，如果程序员也不清楚哪种场景占优，最好就留空什么也不添加，千万不要画蛇添足。

pr_info 输出

这个是在 pidmap_init 中遇到的，看看定义：

#ifndef pr_fmt #define pr_fmt(fmt) fmt #endif  #define pr_emerg(fmt, ...)  	printk(KERN_EMERG pr_fmt(fmt), ##__VA_ARGS__) #define pr_alert(fmt, ...)  	printk(KERN_ALERT pr_fmt(fmt), ##__VA_ARGS__) #define pr_crit(fmt, ...)  	printk(KERN_CRIT pr_fmt(fmt), ##__VA_ARGS__) #define pr_err(fmt, ...)  	printk(KERN_ERR pr_fmt(fmt), ##__VA_ARGS__) #define pr_warning(fmt, ...)  	printk(KERN_WARNING pr_fmt(fmt), ##__VA_ARGS__) #define pr_warn pr_warning #define pr_notice(fmt, ...)  	printk(KERN_NOTICE pr_fmt(fmt), ##__VA_ARGS__) #define pr_info(fmt, ...)  	printk(KERN_INFO pr_fmt(fmt), ##__VA_ARGS__) #define pr_cont(fmt, ...)  	printk(KERN_CONT fmt, ##__VA_ARGS__)

原来就是 printk 的包装，pr_info 使用的级别是 KERN_INFO。下面是网上搜到的 printk 分派图：

打到 console 的是系统初始化时在屏幕输出的，一闪而过不太容易看，所以这里是使用基于 /dev/kmsg 的方式，具体点就是直接使用 dmesg：

$ dmesg | grep -C 10 pid_max [    0.000000] Hierarchical RCU implementation. [    0.000000]  RCU restricting CPUs from NR_CPUS=5120 to nr_cpu_ids=2. [    0.000000] NR_IRQS:327936 nr_irqs:440 0 [    0.000000] Console: colour VGA+ 80x25 [    0.000000] console [tty0] enabled [    0.000000] console [ttyS0] enabled [    0.000000] allocated 436207616 bytes of page_cgroup [    0.000000] please try 'cgroup_disable=memory' option if you don't want memory cgroups [    0.000000] tsc: Detected 2394.374 MHz processor [    0.620597] Calibrating delay loop (skipped) preset value.. 4788.74 BogoMIPS (lpj=2394374) [    0.621979] pid_max: default: 32768 minimum: 301 [    0.622732] Security Framework initialized [    0.623423] SELinux:  Initializing. [    0.624063] SELinux:  Starting in permissive mode [    0.624064] Yama: becoming mindful. [    0.625585] Dentry cache hash table entries: 2097152 (order: 12, 16777216 bytes) [    0.629691] Inode-cache hash table entries: 1048576 (order: 11, 8388608 bytes) [    0.632167] Mount-cache hash table entries: 32768 (order: 6, 262144 bytes) [    0.633123] Mountpoint-cache hash table entries: 32768 (order: 6, 262144 bytes) [    0.634607] Initializing cgroup subsys memory [    0.635326] Initializing cgroup subsys devices

也可以直接 cat /dev/kmsg：

$ cat /dev/kmsg | grep -C 10 pid_max 6,144,0,-;Hierarchical RCU implementation. 6,145,0,-;x09RCU restricting CPUs from NR_CPUS=5120 to nr_cpu_ids=2. 6,146,0,-;NR_IRQS:327936 nr_irqs:440 0 6,147,0,-;Console: colour VGA+ 80x25 6,148,0,-;console [tty0] enabled 6,149,0,-;console [ttyS0] enabled 6,150,0,-;allocated 436207616 bytes of page_cgroup 6,151,0,-;please try 'cgroup_disable=memory' option if you don't want memory cgroups 6,152,0,-;tsc: Detected 2394.374 MHz processor 6,153,620597,-;Calibrating delay loop (skipped) preset value.. 4788.74 BogoMIPS (lpj=2394374) 6,154,621979,-;pid_max: default: 32768 minimum: 301 6,155,622732,-;Security Framework initialized 6,156,623423,-;SELinux:  Initializing. 7,157,624063,-;SELinux:  Starting in permissive mode 6,158,624064,-;Yama: becoming mindful. 6,159,625585,-;Dentry cache hash table entries: 2097152 (order: 12, 16777216 bytes) 6,160,629691,-;Inode-cache hash table entries: 1048576 (order: 11, 8388608 bytes) 6,161,632167,-;Mount-cache hash table entries: 32768 (order: 6, 262144 bytes) 6,162,633123,-;Mountpoint-cache hash table entries: 32768 (order: 6, 262144 bytes) 6,163,634607,-;Initializing cgroup subsys memory 6,164,635326,-;Initializing cgroup subsys devices

这种会 hang 在结尾，需要 Ctrl+C 才能退出。甚至也可以自己写程序捞取：

/* The glibc interface */ #include <sys/klog.h>  int klogctl(int type, char *bufp, int len);

不过与前两个不同，它是基于 /proc/kmsg 的，cat 查看这个文件内容通常为空，与 /dev/kmesg 还有一些区别。限于篇幅就不一一介绍了，感兴趣的读者自己 man 查看下吧。

参考

[1]. Linux内核入门-- likely和unlikely

[2]. Linux内核输出的日志去哪里了

[3]. Pid Namespace 详解

[4]. namaspace之pid namespace

[5]. struct pid & pid_namespace

[6]. 一文看懂Linux进程ID的内核管理

[9]. linux系统pid的最大值研究

[10]. What is CONFIG_BASE_SMALL=0