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) contaier_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 |= (unsigned long)p; /* 不影响rb节点的颜色属性　*/
}

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

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

//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)++; // 极高性能，无需任何同步指令