Cyrus' Paperbox

Linux内核数据结构及系统调用

学习笔记 操作系统 · 约 17 分钟阅读

Linux 内核编程及编译 #

Linux 内核所用编程语言

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

Linux 内核编译常用工具

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;

基于区间的分支选择 # 

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

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

支持参数个数可变的宏 #

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

#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 函数

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

GCC 内建函数 #

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

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

在标准 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)。

范例：

Linux 系统调用实现机制 #

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

与普通过程调用的区别

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

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

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

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

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

系统调用号

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

系统调用实现机制

系统调用的实现要领

Linux 内核常用数据结构 #

链表

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

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

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

//<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-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+ 树、平衡二叉树、红黑树

// 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-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) ……