Linux 内核编程及编译 #

Linux 内核所用编程语言

• C 语言
• 汇编语言

Linux 内核代码已超 2 千万行、接近 3 千万行

Linux 内核编译常用工具

• GCC（GNU Compiler Collection）
  • GCC 不仅支持 C 语言，还扩展支持了 C++、Java、Go 等语言
  • GCC 支持多种不同的硬件平台，如 x86、ARM、MIPS、LoongArch 等体系结构

GCC 编译流程

Linux 内核编程技巧 #

语句表达式 #

语句表达式（即括号内的复合语句）

宏构造利器：语句表达式 - Linux内核中语句表达式的使用 - 嵌入式C语言自我修养 | 宅学部落

• 旨在使宏定义变得更加安全

#define max(x,y) ((x)>(y)?(x):(y))

#基于整型数据的改进
#define max(x,y) \
({ int _x=(x), _y=(y); _x > _y ? _x : _y; })

# 基于未知数据类型的改进
#define max(x, y) ({			\
	typeof(x) _x = (x);		\
	typeof(y) _y = (y);		\
	(void) (&_x == &_y);		\
	_x > _y ? _x : _y; })

零长数组（变长数组） #

在定义数据结构时非常有用、不占用结构体空间

struct T_Line
{
 int length;
 char contents[];
};

typedef struct
{
	unsigned int meg_len; //至少包含一个成员
	char msg_data[];	  //变长数组成员必须是结构体最后一个
} MsgBuffer;

使用：

//内存申请
p_buffer = (MsgBuffer *)malloc(sizeof(MsgBuffer) + sizeof(int) * cur_len);
if(NULL != p_buffer){
	p_buffer->msg_len = cur_len;
	memcpy(p_buffer->data,data,cur_len);
}
//内存释放
free(p_buffer);
p_buffer = NULL;

基于区间的分支选择 #

• 注意…两边均有空格
• 对于 ASCII 码或整数范围指定非常有用

static int local_atoi(const char *name)
{
	int val = 0;
	for (;; name++) {
		switch (*name) {
		case '0' ... '9':
			val = 10*val+(*name-'0');
			break;
		default:
			return val;
		}
	}
}

基于成员名的灵活初始化 #

• 标准 C 语言要求数组或结构体初始化必须顺序出现
• GNU C 则可通过指定索引或结构体成员名初始化

支持参数个数可变的宏 #

主要应用于输出操作类函数里

#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, ...) \

VA_ARGS 为编译器保留字段，预处理伊始把参数传递给被定义的宏，而当宏调用展开时，实参便传递给了替换后的 printk 函数

面向编译检查与优化的属性声明 #

• 函数属性：noreturn、const、format、interrupt、isr
• 语法格式：attribute((<属性列表>))
• 变量/类型属性：aligned、packed、sections

GCC 内建函数 #

GCC 内建函数（以 builtin 作为函数名前缀）

• Linux 内核常用内建函数
  • • __builtin_constant_p(x): 用来判断编译时 x 是否就可确定为常量。
  • __builtin_expect(exp, c): 寓意 exp==c 的概率很大，从而可用来引导 GCC 编译器进行条件分支预测。这也即根据最有可能执行的分支实施指令序列优化处理，使指令尽可能顺序执行以提高 CPU 预取效率。
  • __builtin_prefetch(const void* addr, int rw, int locality): 主动进行数据预取，即使用地址 addr 内存单元的值之前就将其取值加载到高速缓存 cache 里，从而减少延迟和改善性能。

关于函数形参存放位置的指定 #

在标准 C 语言中，函数形参在传入实参时会涉及参数存放位置问题。

对于 x86 体系结构来说，函数参数和局部变量均被存放到函数局部堆栈里。

而对于 ARM 体系结构，函数参数按照 ATPCS（ARM Procedure Call Standard）标准进行传递。具体来说，前五个参数存放在寄存器 R0~R4 中，超出之后的参数则被存放在局部堆栈中。

为此，ARM 平台没有定义自身的 asmlinkage 宏，而直接引用内核的 asmlinkage 宏，即：

#define asmlinkage CPP_ASMLINKAGE

整型常数后缀 ul #

在 C 语言中，数字常量会被隐式处理为 int 类型，因此两个 int 类型的数据相加可能导致溢出。为了避免这种情况，可以使用 ul 后缀，将 int 类型的数据强制转换为无符号长整类型 (unsigned long)。

范例：

• 1 表示有符号整数（int）1。
• 1ul 表示无符号长整类型数（unsigned long）1。

Linux 系统调用实现机制 #

定义: 系统过程→系统服务→系统调用命令

与普通过程调用的区别

• 运行在不同的系统状态
• 软中断进入机制
• 返回及重新调度问题
• 嵌套调用

如何从用户空间进入内核空间？

• 软中断/陷入机制（int 指令）

如何跳转至系统调用总控程序模块？

• 中断向量表（函数指针数组：整数索引⬄函数）

如何跳转至特定系统调用处理函数？

• 系统调用表（函数指针数组：整数索引⬄函数）

如何从内核空间返回用户空间？

• （软）中断返回机制（ret 指令）

系统调用应用编程举例说明

• 简单用户程序例子
  • 从一个文件读取数据，再将它们拷贝到另一文件中（两个文件名已获得）
• 系统调用分析
  • 源数据文件打开
  • 目标数据文件创建
  • 文件数据读入到缓冲
  • 缓冲数据写出到文件
  • 关闭数据文件

系统调用号

/usr/include/asm/unistd.h :

（1）#include <asm/unistd_32.h>⬄/usr/include/asm/unistd_32.h
	#define __NR_read	3
	#define __NR_write	4
	#define __NR_open	5
	#define __NR_close	6
	#define __NR_creat	8


（2）#include <asm/unistd_64.h>⬄/usr/include/asm/unistd_64.h
	#define __NR_read	0
	#define __NR_write	1
	#define __NR_open	2
	#define __NR_close	3
	#define __NR_creat	85

系统调用表

系统调用号与系统调用之间的联系建立在系统调用表 sys_call_table 中，本质上利用函数指针数组实现

/usr/include/unistd.h:

extern long int syscall(long int __sysno, ...) __THROW;

_syscall2(long, open, const char*, filename, int, flags);
_syscall2(long, creat, const char*, filename, int, flags);
_syscall3(ssize_t, read, unsigned, fd, char*, buf, size_t, count);
_syscall3(ssize_t, write, unsigned, fd, char*, buf, size_t, count);
_syscall1(void, close, unsigned, fd);

//实现
FUNPTRTYPE sys_call_table[] = {sys_read, sys_write, sys_open, sys_close, …, sys_creat, …};

系统调用实现机制

系统调用的实现要领

• 设置系统调用号和参数
  • 系统调用号（指定寄存器/内存单元）
  • 参数（直接寄存器 、间接参数表指针）
  • UNIX(CHMK 命令)/DOS(INT21 软中断)
• 系统调用命令的一般性处理
  • 将处理机状态由用户态转为系统态
  • 保护 CPU 现场，将 PSW、PC、系统调用号、用户栈指针、通用寄存器等压入堆栈
  • 用户定义参数送至指定位置
• 分析系统调用类型，转相应处理子程序
  • 中断和陷入向量表、系统调用表

Linux 内核常用数据结构 #

链表

数组要求占用连续存储空间且无法动态扩展，含若干结点（均由有效数据和指针两部分组成）

单向链表、双向链表、Linux 内核链表类属机制

• Linux 内核链表类型定义

//<linux-4.8.8/include/linux/types.h>
struct list_head {
 struct list_head *next, *prev;
};

• Linux 内核链表结点添加/删除/替换操作函数

//<linux-4.8.8/include/linux/list.h>
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
static inline void list_del(struct list_head *entry);
static inline void list_replace(struct list_head *old, struct list_head *new);

• Linux 内核链表遍历操作宏

//<linux-4.8.8/include/linux/list.h>
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
	for (pos = (head)->prev; pos != (head); pos = pos->prev)

红黑树

广泛用于内核内存管理和进程调度

二叉树、B- 树、B+ 树、平衡二叉树、红黑树

• B 树与 B+ 树
  • B- 树（B 树，平衡多叉树）
    • 一棵 m 阶 B 树是一棵平衡的 m 路查找树
    • B- 树或者是空树，或者是满足下列性质的树：
      • 1、每个结点最多拥有 m 棵子树；
      • 2、具有 k 棵子树的非叶结点包含 k-1 个关键字（从小到大排列，且对应左子树结点均小、右子树结点均大）；
      • 3、除根结点以外的所有非叶结点拥有至少⌈m/2⌉棵子树；
      • 4、非空 B 树的根结点拥有至少一个关键字及两棵子树
      • 5、所有的叶子结点都位于同一层
  • B+ 树（B 树 + 索引顺序访问方法）
    • 叶子结点存储关键字及相应记录的地址，叶子结点以上各层作为索引使用
    • 一棵 m 阶的 B+ 树定义如下：
      • 1、每个结点至多有 m 个子女；
      • 2、除根结点外，每个结点至少有 [m/2] 个子女，根结点至少有两个子女；
      • 3、有 k 个子女的结点必有 k 个关键字
    • B+ 树的查找与 B 树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止
• 平衡二叉树（Balanced Binary Tree）
  • 一棵空树；或其左右两棵子树的高度差的绝对值不超过 1，且左右两棵子树均为平衡二叉树
• 红黑树（平衡二叉树变体：左右子树高度差可能大于 1，但平衡代价低）
  • 每个结点或红或黑（非红即黑）的二叉排序树
  • 根结点为黑色，每个叶结点也均为黑色
  • 若结点为红色，则两个子结点都为黑色父结点一定为黑色
  • 从一个内部结点到其所有叶结点的各简单路径上的黑色结点数量都是相同的存在黑色子结点的结点一定有两个子结点
  • 优点在于所有重要操作（包括插入、删除、搜索）的时间复杂度均为 O(log n)
  • 着色规则
    • 添加新的结点，默认颜色为红色。（可能破坏红黑树性质/要求）
    • 若为根结点位置，直接修正为黑色
    • 若非根结点位置
      • 如果父结点为黑色，无需任何操作
      • 如果父结点为红色
        • 若叔叔结点为红色，则将父结点和叔叔结点都设置为黑色、同时将非根结点的祖父结点设置为红色
        • 若叔叔结点为黑色，则将父结点设置为黑色、祖父结点设置为红色，并以父结点为支点旋转祖父结点
  • Linux 内核红黑树实现

// linux-4.8.8/include/linux/rbtree.h
struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
struct rb_root {
	struct rb_node *rb_node;
};

• 红黑树相关操作函数

extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root 
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);
extern struct rb_node *rb_first_postorder(const struct rb_root *);
extern struct rb_node *rb_next_postorder(const struct rb_node *);
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,			    struct rb_root *root);
extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,				struct rb_root *root);
……
//也参linux-4.8.8/lib/rbtree.c
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));

• 红黑树在处理器调度中的应用

// linux-4.8.8/include/linux/sched.h 
……
struct sched_entity {
	struct load_weight	load; 
	struct rb_node		run_node;
 ……
#ifdef CONFIG_FAIR_GROUP_SCHED
	int			depth;
	struct sched_entity	*parent;
	struct cfs_rq		*cfs_rq;
 ……
#endif
 ……
};

// linux-4.8.8/kernel/sched/sched.h
struct cfs_rq {
	struct load_weight load;
	unsigned int nr_running, h_nr_running;
	u64 exec_clock;
	u64 min_vruntime;
#ifndef CONFIG_64BIT
	u64 min_vruntime_copy;
#endif
	struct rb_root tasks_timeline;
	struct rb_node *rb_leftmost;
	struct sched_entity *curr, *next, *last, *skip;
……
};

循环缓冲

• 解决生产者和消费者数据传输问题的经典模型

• 数据元素传输后其他数据元素无需前移故而高效

• Linux 内核循环缓冲实现

//linux-4.8.8/include/linux/kfifo.h
struct __kfifo {
	unsigned int	in;
	unsigned int	out;
	unsigned int	mask;
	unsigned int	esize;
	void		*data;
};
#define INIT_KFIFO(fifo) ……
#define DEFINE_KFIFO(fifo, type, size) ……
static inline unsigned int __must_check__kfifo_uint_must_check_helper(unsigned int val) { … }
static inline int __must_check__kfifo_int_must_check_helper(int val) { … }
#define kfifo_alloc(fifo, size, gfp_mask) ……