Linux 内核之旅：基础知识

// 说明：获得结构体 (TYPE) 的变量成员 (MEMBER) 在此结构体中的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

// 说明：根据结构体 (type) 变量中的域成员变量 (member) 的指针 (ptr) 来获取指向整个结构体变量的指针
#define container_of(ptr, type, member) ({          \
    const typeof(((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

struct list_head {
	struct list_head *next, *prev;
};

struct student{// 结构体 student 本身就是一个链表节点
	struct student *prev;
	struct student *next;
	char name[64];
	char id[64];
}

struct student{
	struct list_head list_node;// 链表节点
	char name[64];
	char id[64];
};

struct hlist_head {
	struct hlist_node *first;
};

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

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	n->next = first; // 新节点的 next 指针指向原头结点
	if (first)
		first->pprev = &n->next;// 原头结点的 pprev 指向新节点的 next 字段
	WRITE_ONCE(h->first, n);//first 指针指向新的节点（更换了头结点）
	n->pprev = &h->first;// 此时 n 是链表的头结点, 将它的 pprev 指向 list_head 的 first 字段
}

static inline void __hlist_del(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;

	WRITE_ONCE(*pprev, next); // pprev 指向的是前一个节点的 next 指针, 当该节点是头节点时指向 hlist_head 的 first, 两种情况下不论该节点是一般的节点还是头结点都可以通过这个操作删除掉所需删除的节点
	if (next)
		next->pprev = pprev;// 使删除节点的后一个节点的 pprev 指向删除节点的前一个节点的 next 字段，节点成功删除
}

#define hlist_entry(ptr, type, member) container_of(ptr,type,member)

struct upid {
	/* Try to keep pid_chain in the same cacheline as nr for find_vpid */
	int nr;
	struct pid_namespace *ns;
	struct hlist_node pid_chain;        //hash list 中的 node
};

struct pid
{
	atomic_t count;
	unsigned int level;
	/* lists of tasks that use this pid */
	struct hlist_head tasks[PIDTYPE_MAX];   // 数组头节点
	struct rcu_head rcu;
	struct upid numbers[1];		//柔性数组，可扩展为多个
};

struct pid_link
{
	struct hlist_node node;
	struct pid *pid;
};

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/rculist.h#L584
#define hlist_for_each_entry_rcu(pos, head, member)			\
	for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
			typeof(*(pos)), member);			\
		pos;							\
		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
			&(pos)->member)), typeof(*(pos)), member))

static struct hlist_head *pid_hash;	//全局hashtable

struct upid {
	/* Try to keep pid_chain in the same cacheline as nr for find_vpid */
	int nr;
	struct pid_namespace *ns;
	struct hlist_node pid_chain;
};

struct pid *find_pid_ns(int nr, struct pid_namespace *ns)
{
	struct upid *pnr;
	//
	hlist_for_each_entry_rcu(pnr,
			&pid_hash[pid_hashfn(nr, ns)], pid_chain)
		if (pnr->nr == nr && pnr->ns == ns)
			return container_of(pnr, struct pid,
					numbers[ns->level]);
	
		return NULL;
}

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/pid.h#L178
#define do_each_pid_task(pid, type, task)				\
	do {								\
		if ((pid) != NULL)					\
			hlist_for_each_entry_rcu((task),		\
				&(pid)->tasks[type], pids[type].node) {

static bool has_stopped_jobs(struct pid *pgrp)
{
	struct task_struct *p;

	do_each_pid_task(pgrp, PIDTYPE_PGID, p) {
		if (p->signal->flags & SIGNAL_STOP_STOPPED)
			return true;
	} while_each_pid_task(pgrp, PIDTYPE_PGID, p);

	return false;
}

struct pid {
    // ...
    struct hlist_head tasks[PIDTYPE_MAX];  // 每个pid有自己的任务链表
    // ...
};

struct task_struct {
    // ...
    struct pid_link pids[PIDTYPE_MAX];     // 链接到对应pid的tasks链表
    // ...
};

struct pid_link {
    struct hlist_node node;   // ← 这就是member参数指向的节点
    struct pid *pid;
};

struct task_struct *task;                    // pos: 遍历时的当前任务
struct hlist_head *head = &pid->tasks[type]; // head: PID的任务链表头
                                            // member: pids[type].node

hlist_for_each_entry_rcu(task, head, pids[type].node) {
    // 处理每个task
	......
}

    rcu_read_lock(); // 禁用抢占，标记进入读端临界区
    hlist_for_each_entry_rcu(pos, head, member) {
        // 安全地引用 pos，但不能在其中睡眠（除非是可睡眠 RCU）
    }
    rcu_read_unlock(); // 退出临界区

static inline void hlist_add_head_rcu(struct hlist_node *n, struct hlist_head *h){
    struct hlist_node *first = h->first;
    n->next = first;
    n->pprev = &h->first;
    // 非常重要
    rcu_assign_pointer(hlist_first_rcu(h), n);
    if (first) 
        first->pprev = &n->next;
}

static struct hlist_head *pid_hash;

// lock define
static  __cacheline_aligned_in_smp DEFINE_SPINLOCK(pidmap_lock);

//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/pid.c#L338
struct pid *alloc_pid(struct pid_namespace *ns)
{
    ......

    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;
    /* 1. 写者必须显式加锁，保证同一时间只有一个写者在修改链表 */
	spin_lock_irq(&pidmap_lock);
	if (!(ns->nr_hashed & PIDNS_HASH_ADDING))
		goto out_unlock;
	for ( ; upid >= pid->numbers; --upid) {
        /* 2. 调用 RCU 写端函数，此时由于有 spinlock，不会有第二个写者来干扰指针修改 */
		hlist_add_head_rcu(&upid->pid_chain,
				&pid_hash[pid_hashfn(upid->nr, upid->ns)]);
		upid->ns->nr_hashed++;
	}

    /* 3. 解锁 */
	spin_unlock_irq(&pidmap_lock);

	return pid;
    ......
}

//假设一个哈希表节点 my_node
// 1. 写者必须持有锁来防止多个写者冲突
spin_lock(&my_lock);

//2. 调用写端 API 将节点从链表中断开
// 此时读者依然可以通过旧指针访问该节点，所以不能立即 kfree
hlist_del_rcu(&my_node->list_member);

spin_unlock(&my_lock);

// 3. 等待所有读者完成（宽限期）
synchronize_rcu();

// 4. 只有到了这里，物理释放才是安全的
kfree(my_node);

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

#define  rb_parent(r) ((struct rb_node*)((r)->__rb_parent_color & ~3))

/* 'empty' nodes are nodes that are known not be inserted in an rbtree */
#define RB_EMPTY_NODE(node)	\
	((node)->__rb_parent_color == (unsigned long)(node))

#define RB_CLEAR_NODE(node)	\
	((node)->__rb_parent_color = (unsigned long)(node))

/* 其他一些辅助宏　*/

#define RB_RED   0
#define RB_BLACK 1

#define RB_ROOT (struct rb_root){NULL,}

#define rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)

/* 设置parent的相关内联函数　*/

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; /* 保留颜色位，替换父节点指针　*/
}

static inline void rb_set_parent_color(struct rb_node *rb, struct rb_node *p, int color)
{
	rb->__rb_parent_color = (unsigned long)p | color; /* 指定rb节点的颜色属性　*/
}

/* 初始化新节点的内联函数　*/

static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)
{
	/**
     * 设置其双亲节点的首地址(根节点的双亲节点为NULL),且颜色属性为黑色
	 */
	node->__rb_parent_color = (unsigned long)parent;

	node->rb_left = node->rb_right = NULL;
	/**
	 * 指向新节点
	 */
	*rb_link = node;
}

// https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/rbtree.h#L64
// RCU 安全的左右子节点访问宏
#define rb_entry_safe(ptr, type, member) \
	({ typeof(ptr) ____ptr = (ptr); \
	   ____ptr ? rb_entry(____ptr, type, member) : NULL; \
	})

// https://elixir.bootlin.com/linux/v4.11.6/source/lib/rbtree.c
// 左旋时，旧节点的右子变为新的子树根
// 写者使用 WRITE_ONCE 保证指针赋值的原子可见性
// 读者通过 rcu_dereference(node->rb_left) 或 rcu_dereference(node->rb_right) 安全读取

// 在 RCU 读临界区内遍历红黑树
struct my_node *my_rbtree_search(struct rb_root *root, long key)
{
    struct rb_node *node;

    rcu_read_lock();
    node = rcu_dereference(root->rb_node);
    while (node) {
        struct my_node *data = rb_entry(node, struct my_node, rb);
        if (key < data->key)
            node = rcu_dereference(node->rb_left);
        else if (key > data->key)
            node = rcu_dereference(node->rb_right);
        else {
            rcu_read_unlock();
            return data;
        }
    }
    rcu_read_unlock();
    return NULL;
}

// https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/rbtree_augmented.h#L44
struct rb_augment_callbacks {
    void (*propagate)(struct rb_node *node, struct rb_node *stop);
    void (*copy)(struct rb_node *old, struct rb_node *new);
    void (*rotate)(struct rb_node *old, struct rb_node *new);
};

// https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L335
// 计算单个节点的 subtree_gap
static long vma_compute_subtree_gap(struct vm_area_struct *vma)
{
    unsigned long max = vma->vm_start;
    // 当前节点与前驱之间的 gap
    if (vma->vm_prev)
        max -= vma->vm_prev->vm_end;
    // 与左子树的最大 gap 取最大值
    if (vma->vm_rb.rb_left) {
        unsigned long subtree_gap =
            rb_entry(vma->vm_rb.rb_left, struct vm_area_struct, vm_rb)
                ->rb_subtree_gap;
        if (subtree_gap > max)
            max = subtree_gap;
    }
    // 与右子树的最大 gap 取最大值
    if (vma->vm_rb.rb_right) {
        unsigned long subtree_gap =
            rb_entry(vma->vm_rb.rb_right, struct vm_area_struct, vm_rb)
                ->rb_subtree_gap;
        if (subtree_gap > max)
            max = subtree_gap;
    }
    return max;
}

// propagate 回调：从 node 向上到 stop 逐级更新 rb_subtree_gap
static void vma_gap_callbacks_propagate(struct rb_node *rb, struct rb_node *stop)
{
    while (rb != stop) {
        struct vm_area_struct *node = rb_entry(rb, struct vm_area_struct, vm_rb);
        unsigned long augmented = vma_compute_subtree_gap(node);
        if (node->rb_subtree_gap == augmented)
            break;  // 剪枝：值未变化则无需继续向上
        node->rb_subtree_gap = augmented;
        rb = rb_parent(&node->vm_rb);
    }
}

// rotate 回调：旋转后先更新降级节点（old），再更新升级节点（new）
static void vma_gap_callbacks_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
{
    struct vm_area_struct *old = rb_entry(rb_old, struct vm_area_struct, vm_rb);
    struct vm_area_struct *new = rb_entry(rb_new, struct vm_area_struct, vm_rb);
    // old 现在是 new 的子节点，先算 old
    old->rb_subtree_gap = vma_compute_subtree_gap(old);
    // 再算 new（包含了 old 的信息）
    new->rb_subtree_gap = vma_compute_subtree_gap(new);
}

// https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/rbtree_augmented.h
void rb_insert_augmented(struct rb_node *node, struct rb_root *root,
                         const struct rb_augment_callbacks *augment);
void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                        const struct rb_augment_callbacks *augment);

// 典型的红黑树插入（以 VMA 为例简化）
void my_insert(struct rb_root *root, struct my_node *new)
{
    struct rb_node **link = &root->rb_node;
    struct rb_node *parent = NULL;

    // 标准 BST 查找插入位置
    while (*link) {
        struct my_node *entry = rb_entry(*link, struct my_node, rb);
        parent = *link;
        if (new->key < entry->key)
            link = &(*link)->rb_left;
        else
            link = &(*link)->rb_right;
    }

    // 阶段一：链接新节点（红色，无子节点）
    rb_link_node(&new->rb, parent, link);
    // 阶段二：修复平衡
    rb_insert_color(&new->rb, root);
}

// https://elixir.bootlin.com/linux/v4.11.6/source/lib/rbtree.c#L92
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
    __rb_insert(node, root, dummy_rotate);
}

// __rb_insert 的核心逻辑（简化注释版）
static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
    struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

    while (true) {
        // Case 1: 插入的是根节点 -> 直接染黑
        if (!parent) {
            rb_set_parent_color(node, NULL, RB_BLACK);
            break;
        }

        // Case 2: 父节点是黑色 → 无需修复，红黑树性质未被破坏
        if (rb_is_black(parent))
            break;

        gparent = rb_red_parent(parent);

        // 父节点是红色，需要修复（违反"红色节点的子节点必须是黑色"）
        tmp = gparent->rb_right;
        if (parent != tmp) {    // parent == gparent->rb_left
            if (tmp && rb_is_red(tmp)) {
                // Case 3: 叔叔节点也是红色
                // 将父和叔都染黑，祖父染红，然后对祖父继续向上修复
                rb_set_parent_color(tmp, gparent, RB_BLACK);
                rb_set_parent_color(parent, gparent, RB_BLACK);
                node = gparent;
                parent = rb_parent(node);
                rb_set_parent_color(node, parent, RB_RED);
                continue;
            }

            tmp = parent->rb_right;
            if (node == tmp) {
                // Case 4: 叔叔是黑色，且当前节点是右子（LR 情况）
                // 先对 parent 左旋，转化为 Case 5
                tmp = node->rb_left;
                WRITE_ONCE(parent->rb_right, tmp);
                WRITE_ONCE(node->rb_left, parent);
                if (tmp)
                    rb_set_parent_color(tmp, parent, RB_BLACK);
                rb_set_parent_color(parent, node, RB_RED);
                augment_rotate(parent, node);
                parent = node;
                tmp = node->rb_right;
            }

            // Case 5: 叔叔是黑色，当前节点是左子（LL 情况）
            // 对 gparent 右旋，parent 变成子树根
            WRITE_ONCE(gparent->rb_left, tmp);  // gparent 的左子改为 parent 的右子
            WRITE_ONCE(parent->rb_right, gparent);
            if (tmp)
                rb_set_parent_color(tmp, gparent, RB_BLACK);
            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
            augment_rotate(gparent, parent);
            break;
        } else {
            // 镜像情况（parent == gparent->rb_right），逻辑对称
            // ...（省略，与上面左右对称）
        }
    }
}

// https://elixir.bootlin.com/linux/v4.11.6/source/lib/rbtree.c#L275
void rb_erase(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *rebalance;
    rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
    if (rebalance)
        ____rb_erase_color(rebalance, root, dummy_rotate);
}

// https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/rbtree_augmented.h#L131
// 简化的核心逻辑
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
             const struct rb_augment_callbacks *augment)
{
    struct rb_node *child = node->rb_right;
    struct rb_node *tmp = node->rb_left;
    struct rb_node *parent, *rebalance;

    if (!tmp) {
        // Case A: 无左子 → 用右子直接替换
        // 如果被删节点是黑色且替换节点（child）为空或黑色，需要 rebalance
        parent = rb_parent(node);
        __rb_change_child(node, child, parent, root);
        rebalance = ... ;  // 需要修复的起点
    } else if (!child) {
        // Case B: 无右子 → 用左子直接替换
        parent = rb_parent(node);
        __rb_change_child(node, tmp, parent, root);
        rebalance = ... ;
    } else {
        // Case C: 有两个子节点 → 找中序后继替换
        struct rb_node *successor = child, *child2;

        // 找最小的右子树节点（后继）
        tmp = child->rb_left;
        if (!tmp) {
            // 后继就是右子节点本身
            child2 = successor->rb_right;
            parent = successor;
        } else {
            // 后继在右子树的最左边
            do {
                parent = successor;
                successor = tmp;
                tmp = tmp->rb_left;
            } while (tmp);
            child2 = successor->rb_right;
            parent->rb_left = child2;
            successor->rb_right = child;
            rb_set_parent(child, successor);
        }

        // 用 successor 替换 node 的位置
        tmp = node->rb_left;
        successor->rb_left = tmp;
        rb_set_parent(tmp, successor);

        // 继承 node 的颜色
        // augment->copy(node, successor);
        __rb_change_child(node, successor, rb_parent(node), root);

        // 如果删除的是黑色节点，需要从 child2 开始修复
        rebalance = ... ;
    }

    // 调用 augment->propagate 从 parent 向上更新聚合信息
    augment->propagate(parent, NULL);
    return rebalance;
}

// https://elixir.bootlin.com/linux/v4.11.6/source/lib/rbtree.c#L197
// 简化的核心逻辑
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
    struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;

    while (true) {
        sibling = parent->rb_right;
        if (node != sibling) {  // node 是左子
            if (rb_is_red(sibling)) {
                // Case 1: 兄弟是红色
                // 对 parent 左旋，兄弟和父交换颜色
                // 转化为 Case 2/3/4
                tmp1 = sibling->rb_left;
                WRITE_ONCE(parent->rb_right, tmp1);
                WRITE_ONCE(sibling->rb_left, parent);
                rb_set_parent_color(tmp1, parent, RB_BLACK);
                __rb_rotate_set_parents(parent, sibling, root, RB_RED);
                augment_rotate(parent, sibling);
                sibling = tmp1;
            }
            tmp1 = sibling->rb_right;
            if (!tmp1 || rb_is_black(tmp1)) {
                tmp2 = sibling->rb_left;
                if (!tmp2 || rb_is_black(tmp2)) {
                    // Case 2: 兄弟的两个子节点都是黑色
                    // 将兄弟染红，黑色缺失上移到 parent
                    rb_set_parent_color(sibling, parent, RB_RED);
                    if (rb_is_red(parent)) {
                        rb_set_black(parent);  // parent 是红色 → 染黑即可终止
                    } else {
                        node = parent;
                        parent = rb_parent(node);
                        if (parent)
                            continue;  // 继续向上修复
                    }
                    break;
                }
                // Case 3: 兄弟的远侄是黑色，近侄是红色
                // 对兄弟右旋，转化为 Case 4
                tmp1 = tmp2->rb_right;
                WRITE_ONCE(sibling->rb_left, tmp1);
                WRITE_ONCE(tmp2->rb_right, sibling);
                // ...更新颜色和父指针
                augment_rotate(sibling, tmp2);
                tmp1 = sibling;
                sibling = tmp2;
            }
            // Case 4: 兄弟的远侄是红色
            // 对 parent 左旋，兄弟继承 parent 颜色，parent 和远侄染黑
            WRITE_ONCE(parent->rb_right, sibling->rb_left);
            WRITE_ONCE(sibling->rb_left, parent);
            rb_set_parent_color(tmp1, sibling, RB_BLACK);
            __rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
            augment_rotate(parent, sibling);
            break;  // Case 4 一定能终止
        } else {
            // 镜像情况（node 是右子），逻辑对称
            // ...
        }
    }
}

//https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L2097
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
	struct rb_node *rb_node;
	struct vm_area_struct *vma;

	/* Check the cache first. */
	vma = vmacache_find(mm, addr);
	if (likely(vma))
		return vma;

	rb_node = mm->mm_rb.rb_node;

	while (rb_node) {
		struct vm_area_struct *tmp;

		tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);

		if (tmp->vm_end > addr) {
			vma = tmp;
			if (tmp->vm_start <= addr){
				//命中条件，跳出查找过程
				break;
			}
			rb_node = rb_node->rb_left;
		} else
			rb_node = rb_node->rb_right;
	}

	if (vma)
		vmacache_update(addr, vma);
	return vma;
}

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/mm.h#L2169
static inline unsigned long
vm_unmapped_area(struct vm_unmapped_area_info *info)
{
	if (info->flags & VM_UNMAPPED_AREA_TOPDOWN)
		return unmapped_area_topdown(info);
	else
		return unmapped_area(info);
}

unsigned long
//https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L2002
arch_get_unmapped_area_topdown(struct file *filp, const unsigned long addr0,
			  const unsigned long len, const unsigned long pgoff,
			  const unsigned long flags)
{
	struct vm_area_struct *vma;
	struct mm_struct *mm = current->mm;
	unsigned long addr = addr0;
	struct vm_unmapped_area_info info;

	/* requested length too big for entire address space */
	if (len > TASK_SIZE - mmap_min_addr)
		return -ENOMEM;

	if (flags & MAP_FIXED)
		return addr;

	/* requesting a specific address */
	if (addr) {
		addr = PAGE_ALIGN(addr);
		vma = find_vma(mm, addr);
		if (TASK_SIZE - len >= addr && addr >= mmap_min_addr &&
				(!vma || addr + len <= vma->vm_start))
			return addr;
	}

	info.flags = VM_UNMAPPED_AREA_TOPDOWN;
	info.length = len;
	info.low_limit = max(PAGE_SIZE, mmap_min_addr);
	info.high_limit = mm->mmap_base;
	info.align_mask = 0;
    //
	addr = vm_unmapped_area(&info);

	/*
	 * A failed mmap() very likely causes application failure,
	 * so fall back to the bottom-up function here. This scenario
	 * can happen with large stack limits and large mmap()
	 * allocations.
	 */
	if (offset_in_page(addr)) {
		VM_BUG_ON(addr != -ENOMEM);
		info.flags = 0;
		info.low_limit = TASK_UNMAPPED_BASE;
		info.high_limit = TASK_SIZE;
		addr = vm_unmapped_area(&info);
	}

	return addr;
}

//unmapped_area_topdown：精髓在于优先寻找尽可能高的地址，同时利用 rb_subtree_gap 进行剪枝
//https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L1855
unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
{
	struct mm_struct *mm = current->mm;
	struct vm_area_struct *vma;
	unsigned long length, low_limit, high_limit, gap_start, gap_end;

	/* Adjust search length to account for worst case alignment overhead */
	length = info->length + info->align_mask;
	if (length < info->length)
		return -ENOMEM;

	/*
	 * Adjust search limits by the desired length.
	 * See implementation comment at top of unmapped_area().
	 */
	gap_end = info->high_limit;
	if (gap_end < length)
		return -ENOMEM;
	high_limit = gap_end - length;

	if (info->low_limit > high_limit)
		return -ENOMEM;
	low_limit = info->low_limit + length;

	/* Check highest gap, which does not precede any rbtree node */
    // 第一阶段：优先检查"最高处"的空隙
    // 在红黑树之外，从进程已有的最后一个 VMA 结束地址到 high_limit 之间，往往存在一个巨大的未映射区域
    // 既然是顶向下查找，这里是逻辑上的第一首选。如果这里够大，直接收工
    // 就不需要走rbtree寻找了
    // gap_start<= gap_start成立，说明high_limit在较高位置，gap_start在较低位置，长度可分配
	gap_start = mm->highest_vm_end;
	if (gap_start <= high_limit)
		goto found_highest;

	/* Check if rbtree root looks promising */
	if (RB_EMPTY_ROOT(&mm->mm_rb))
		return -ENOMEM;
    
    //第二阶段：根节点整体判断
    //如果最高处没位置，就需要进行rbtree查找
    //利用 rb_subtree_gap 秒杀所有不可能的情况。如果根节点记录的最大空隙都塞不下 length，直接报内存不足
	vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
	if (vma->rb_subtree_gap < length)
		return -ENOMEM;

    //第三阶段：带剪枝的高地址优先深度搜索（中序遍历，顺序是：右 -> 中 -> 左）
	while (true) {
		/* Visit right subtree if it looks promising */
		gap_start = vma->vm_prev ? vma->vm_prev->vm_end : 0;
        //1. 尝试右子树（更高地址）
		if (gap_start <= high_limit && vma->vm_rb.rb_right) {
			struct vm_area_struct *right =
				rb_entry(vma->vm_rb.rb_right,
					 struct vm_area_struct, vm_rb);
			if (right->rb_subtree_gap >= length) {
                //右子树代表了更高地址的 VMA。如果右子树里有足够大的 gap，立刻进入右子树
				vma = right;
				continue;
			}
		}

        //2. 右子树不满足，检查当前 Gap
        //检查当前节点 vma 和它前一个节点 vma_prev 之间的缝隙。如果够大，由于是从右往左找的，这个位置就是目前能找到的最高合法位置
check_current:
		/* Check if current node has a suitable gap */
		gap_end = vma->vm_start;
		if (gap_end < low_limit)
			return -ENOMEM;
		if (gap_start <= high_limit && gap_end - gap_start >= length)
			goto found;

        //3. 都不满足，尝试左子树（更低地址）
        //只有右边和中间都行不通时，才被迫向左走，寻找低地址区域
		/* Visit left subtree if it looks promising */
		if (vma->vm_rb.rb_left) {
			struct vm_area_struct *left =
				rb_entry(vma->vm_rb.rb_left,
					 struct vm_area_struct, vm_rb);
			if (left->rb_subtree_gap >= length) {
				vma = left;
				continue;
			}
		}

		/* Go back up the rbtree to find next candidate node */
        // 4. 复杂的回溯逻辑（见上面分析）
        // 当一棵子树找完了（或者被剪枝了），必须回到父节点：
        // 如果是从右子树回来的：意味着比父节点地址高的区域都找过了，没合适的。那么下一步就该检查父节点自身的 gap，不行再看左子树
        // 如果是从左子树回来的：意味着这棵子树及其父节点全部找遍了，继续向上回溯
		while (true) {
			struct rb_node *prev = &vma->vm_rb;
			if (!rb_parent(prev))
				return -ENOMEM;
			vma = rb_entry(rb_parent(prev),
				       struct vm_area_struct, vm_rb);
			if (prev == vma->vm_rb.rb_right) {  // 如果是从右边回来的
				gap_start = vma->vm_prev ?
					vma->vm_prev->vm_end : 0;
				goto check_current; // 那么接下来该查当前节点和左边了
			}
		}
	}

// 结果对齐：从 Gap 转换到 Address
// 由于是顶向下，需要返回这个 Gap 里的最高地址
found:
	/* We found a suitable gap. Clip it with the original high_limit. */
	if (gap_end > info->high_limit)
		gap_end = info->high_limit;

found_highest:
	/* Compute highest gap address at the desired alignment */
	gap_end -= info->length;
    //细节：先减去长度，再进行向下对齐。这保证了分配出的 [return_addr, return_addr + length) 一定落在 Gap 内部且满足对齐要求
	gap_end -= (gap_end - info->align_offset) & info->align_mask;

	VM_BUG_ON(gap_end < info->low_limit);
	VM_BUG_ON(gap_end < gap_start);
	return gap_end;
}

// https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L381
// 用宏自动生成 propagate / copy / rotate 三个回调函数
RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
		     unsigned long, rb_subtree_gap, vma_compute_subtree_gap)

static void vma_gap_callbacks_propagate(struct rb_node *rb, struct rb_node *stop)
{
    while (rb != stop) {
        struct vm_area_struct *node =
            rb_entry(rb, struct vm_area_struct, vm_rb);
        unsigned long augmented = vma_compute_subtree_gap(node);
        // 剪枝：如果重新计算的值与当前值相同，说明上层也不会变，提前终止
        if (node->rb_subtree_gap == augmented)
            break;
        node->rb_subtree_gap = augmented;
        rb = rb_parent(&node->vm_rb);
    }
}

static void vma_gap_callbacks_copy(struct rb_node *rb_old, struct rb_node *rb_new)
{
    struct vm_area_struct *old =
        rb_entry(rb_old, struct vm_area_struct, vm_rb);
    struct vm_area_struct *new =
        rb_entry(rb_new, struct vm_area_struct, vm_rb);
    // 新节点继承旧节点的子树 gap 值
    new->rb_subtree_gap = old->rb_subtree_gap;
}

static void vma_gap_callbacks_rotate(struct rb_node *rb_old,
                     struct rb_node *rb_new)
{
    struct vm_area_struct *old =
        rb_entry(rb_old, struct vm_area_struct, vm_rb);
    struct vm_area_struct *new =
        rb_entry(rb_new, struct vm_area_struct, vm_rb);
    // 先更新降级节点，再更新升级节点
    old->rb_subtree_gap = vma_compute_subtree_gap(old);
    new->rb_subtree_gap = vma_compute_subtree_gap(new);
}

//https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L537
void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
		struct rb_node **rb_link, struct rb_node *rb_parent)
{
	/* Update tracking information for the gap following the new vma. */
	if (vma->vm_next)
		vma_gap_update(vma->vm_next);
	else
		mm->highest_vm_end = vma->vm_end;

	/*
	 * vma->vm_prev wasn't known when we followed the rbtree to find the
	 * correct insertion point for that vma. As a result, we could not
	 * update the vma vm_rb parents rb_subtree_gap values on the way down.
	 * So, we first insert the vma with a zero rb_subtree_gap value
	 * (to be consistent with what we did on the way down), and then
	 * immediately update the gap to the correct value. Finally we
	 * rebalance the rbtree after all augmented values have been set.
	 */
	rb_link_node(&vma->vm_rb, rb_parent, rb_link);
	vma->rb_subtree_gap = 0;
	vma_gap_update(vma);
	vma_rb_insert(vma, &mm->mm_rb);
}

//https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L398
static inline void vma_rb_insert(struct vm_area_struct *vma,
				 struct rb_root *root)
{
	/* All rb_subtree_gap values must be consistent prior to insertion */
	validate_mm_rb(root, NULL);

	rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks);
}

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/rbtree_augmented.h#L57
static inline void
rb_insert_augmented(struct rb_node *node, struct rb_root *root,
		    const struct rb_augment_callbacks *augment)
{
	__rb_insert_augmented(node, root, augment->rotate);
}

//https://elixir.bootlin.com/linux/v4.11.6/source/lib/rbtree.c#L457
void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	__rb_insert(node, root, augment_rotate);
}

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/rbtree_augmented.h#L92
#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
			     rbtype, rbaugmented, rbcompute)		\
static inline void							\
rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
{									\
	while (rb != stop) {						\
		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
		rbtype augmented = rbcompute(node);			\
		if (node->rbaugmented == augmented)			\
			break;						\
		node->rbaugmented = augmented;				\
		rb = rb_parent(&node->rbfield);				\
	}								\
}									\
static inline void							\
rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
{									\
	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
	new->rbaugmented = old->rbaugmented;				\
}									\
static void								\
rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
{									\
	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
	new->rbaugmented = old->rbaugmented;				\
	old->rbaugmented = rbcompute(old);				\
}									\
rbstatic const struct rb_augment_callbacks rbname = {			\
	.propagate = rbname ## _propagate,				\
	.copy = rbname ## _copy,					\
	.rotate = rbname ## _rotate					\
};

// https://elixir.bootlin.com/linux/v4.11.6/source/mm/mmap.c#L389
static void vma_gap_update(struct vm_area_struct *vma)
{
    // 重新计算当前节点的 rb_subtree_gap 并触发 propagate
    vma_gap_callbacks_propagate(&vma->vm_rb, NULL);
}

struct __wait_queue_head {
    spinlock_t lock;	//lock 字段用于保护等待队列在多核环境下数据被破坏
    struct list_head task_list;	//task_list 字段用于保存等待资源的进程列表
};

struct __wait_queue {
    unsigned int flags;	// 重要：可以设置为 WQ_FLAG_EXCLUSIVE，表示等待的进程应该独占资源（解决惊群现象）
    void *private;	//一般用于保存等待进程的进程描述符 task_struct，也可以设置为NULL（epoll下的acceptfd）
    wait_queue_func_t func;	//唤醒函数，一般设置为 default_wake_function() 函数，当然也可以设置为自定义的唤醒函数
    struct list_head task_list;	//用于链接其他等待资源的进程
};

void init_waitqueue_head(wait_queue_head_t *q)
{
    spin_lock_init(&q->lock);
    INIT_LIST_HEAD(&q->task_list);
}

// init_waitqueue_entry 初始化为系统默认的等待唤醒函数
static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
{
    q->flags = 0;
    q->private = p;
    q->func = default_wake_function;
}

//可以通过调用 init_waitqueue_func_entry() 函数来初始化为自定义的唤醒函数
static inline void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)
{
    q->flags = 0;
    q->private = NULL;
    q->func = func;
}

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

    wait->flags &= ~WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&q->lock, flags);
    __add_wait_queue(q, wait);
    spin_unlock_irqrestore(&q->lock, flags);
}

static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
    list_add(&new->task_list, &head->task_list);
}

set_current_state(TASK_INTERRUPTIBLE);	//把当前进程运行状态设置为可中断休眠状态`TASK_INTERRUPTIBLE`
schedule();	//调用 schedule() 函数可以使当前进程让出CPU，切换到其他进程执行

wait_event(wq_head, condition)
wait_event_timeout(wq_head, condition, timeout) 
wait_event_interruptible(wq_head, condition)
wait_event_interruptible_timeout(wq_head, condition, timeout)

wake_up(&wq_head)
wake_up_interruptible(&wq_head)
wake_up_nr(&wq_head, nr)
wake_up_interruptible_nr(&wq_head, nr)
wake_up_interruptible_all(&wq_head)

static void __wake_up_common(wait_queue_head_t *q, 
    unsigned int mode, int nr_exclusive, int sync, void *key)
{
    wait_queue_t *curr, *next;

    list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
        unsigned flags = curr->flags;

        if (curr->func(curr, mode, sync, key) &&
                (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
            break;
    }
}

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/wait.h#L266
#define ___wait_event(wq, condition, state, exclusive, ret, cmd)	\
({									\
	__label__ __out;						\
	wait_queue_t __wait;						\
	long __ret = ret;	/* explicit shadow */			\
									\
	init_wait_entry(&__wait, exclusive ? WQ_FLAG_EXCLUSIVE : 0);	\
	for (;;) {							\
		long __int = prepare_to_wait_event(&wq, &__wait, state);\
									\
        // 被唤醒后再次检查condition是否满足
		if (condition)						\
			break;						\
									\
		if (___wait_is_interruptible(state) && __int) {		\
			__ret = __int;					\
			goto __out;					\
		}							\
									\
        //内置schedule实现，让出CPU
		cmd;							\
	}								\
	finish_wait(&wq, &__wait);					\
__out:	__ret;								\
})

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

	__set_current_state(TASK_RUNNING);

	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);
	}
}

// waker 端（生产者/事件产生方）
some_shared_flag = true;          // ① 先更新 condition
wake_up(&my_wait_queue);          // ② 再唤醒等待者

// waiter 端（消费者/等待方）
wait_event(my_wait_queue, some_shared_flag == true);

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/pagemap.h#L497
static inline void wait_on_page_locked(struct page *page)
{
	if (PageLocked(page))
		wait_on_page_bit(compound_head(page), PG_locked);
}

#define PAGE_WAIT_TABLE_SIZE (1 << 8)
wait_queue_head_t page_wait_table[PAGE_WAIT_TABLE_SIZE];

wait_queue_head_t *page_waitqueue(struct page *page)
{
    return &page_wait_table[hash_ptr(page, PAGE_WAIT_TABLE_BITS)];
}

//https://elixir.bootlin.com/linux/v4.11.6/source/mm/filemap.c#L912
void add_page_wait_queue(struct page *page, wait_queue_t *waiter)
{
	wait_queue_head_t *q = page_waitqueue(page);
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__add_wait_queue(q, waiter);
	SetPageWaiters(page);
	spin_unlock_irqrestore(&q->lock, flags);
}
EXPORT_SYMBOL_GPL(add_page_wait_queue);

//https://elixir.bootlin.com/linux/v4.11.6/source/fs/eventpoll.c#L230
struct eppoll_entry {
	/* List header used to link this structure to the "struct epitem" */
	struct list_head llink;

	/* The "base" pointer is set to the container "struct epitem" */
	struct epitem *base;

	/*
	 * Wait queue item that will be linked to the target file wait
	 * queue head.
	 */
	wait_queue_t wait;

	/* The wait queue head that linked the "wait" wait queue item */
	wait_queue_head_t *whead;
};

//在 get_task_struct 中增加进程引用计数：
atomic_inc(&t->usage); // 确保多 CPU 同时增加计数时不会冲突

//https://elixir.bootlin.com/linux/v4.11.6/source/kernel/pid.c#L475
struct task_struct *get_pid_task(struct pid *pid, enum pid_type type)
{
	struct task_struct *result;
    //这个操作保证了：在它增加 task_struct 的引用计数之前，没有任何一个 CPU 能够彻底销毁这个进程对象
	rcu_read_lock();
	result = pid_task(pid, type);
	if (result)
		get_task_struct(result);
	rcu_read_unlock();
	return result;
}

    spin_lock(&rq->lock); // 获取运行队列锁
    // ... 修改任务状态 ...
    spin_unlock(&rq->lock);

    down(&sem);   // 如果锁被占用，进程进入 TASK_UNINTERRUPTIBLE 状态
    // ... 执行复杂的磁盘或设备操作 ...
    up(&sem);     // 释放并唤醒等待者

    mutex_lock(&inode->i_mutex); 
    // ... 操作文件 inode ...
    mutex_unlock(&inode->i_mutex);

    down_read(&mm->mmap_sem); // 多个线程可以同时查找虚拟内存区域 (VMA)
    // ... 查找地址空间 ...
    up_read(&mm->mmap_sem);

    unsigned int *count = this_cpu_ptr(&net_stats);
    (*count)++; // 极高性能，无需任何同步指令