Linux内核常用C语言技巧数据结构和算法

Algorithm

发布日期: 2023-10-31

文章字数: 1.9k

阅读时长: 7 分

阅读次数:

1.Linux内核中常用C语言技巧

GCC的C编译器对C语言进行了很多扩充，称为GUN C语言。

1.1语句表达式

语句表达式可以使用循环、跳转和局部变量，通常用在宏定义中。

# define max(a,b) ((a) > (b) ? (a) : (b))
/***
调用 max(i++, j++),宏的作用是文本替换得到
(i++) > (j++) ? (i++) : (j++)
在条件部分被计算一次，结果部分还被计算一次，会导致安全问题。
***/

当知道ab类型时的写法

#define maxint(a,b) \
  ({int _a=(a), _b=(b); \
  _a > _b ? _a : _b;})

不知道ab类型, typeof可以构造新的类型

<include/linux/kernel.h>
#define min(x,y)({ \
  typeof(x) _min1 = (x); \
  typeof(y) _min2 = (y); \
  (void) (&_min1 == &_min2); \  
  /***
  &_min1得到min1的指针，编译时，如果两个指针类型不同会报错。
  void只是想利用语句表达式进行类型检查,而不需要比较的结果。
  为什么要比较地址，不直接比较值？
  claude的回答：
  即使编译器对_min1和_min2做优化,转换为寄存器变量,指针地址比较仍可用；
  指针地址比较也可以作用于结构体等非基本类型。
  ***/
  _min1 < _min2 ? _min1 : _min2; \
})

1.2标号元素

标准C语言要求数组或者结构体初始化必须固定顺序。但GUN C可以指定要初始化的，没有初始化的为0或者NULL，而且顺序可以不固定。以下是C内核中的一段代码示例:

static struct usb_driver usb_storage_driver = {     
  .owner         = THIS_MODULE,      
  .name          = "usb-storage",       
  .probe         = storage_probe,      
  .disconnect    = storage_disconnect,      
  .id_table      = storage_usb_ids, 
};

1.3可变参数的宏

<include/linux/printk.h>
# define pr_debug(fmt, ...) \ //...是可变化参数
  dynamic_pr_debug(fmt, ##__VA_ARGS__) //__VA_ARGS__编译器保留字段
//预处理时参数传给宏，调用宏时传给dynamic_pr_debug函数

1.4函数属性、变量属性核类型属性

//属性语法格式
__attribute__ ((attribute-list))

void __attribute__ ((noreturn)) die(void);
//告诉die函数，从不返回值

static inline u32 __attribute_const__ read_cpuid_cachetype(void)
{
  return read_cpuid(CTR_EL0)
} 
//只调用函数一次，再次调用时返回第一次结果就行

struct xx{
  //表示变量或者结构体成员的最小对齐格式
  //以8字节对齐方式分配xx数据结构
}__aligned(8);

不过还有更复杂的函数属性。函数属性的宏定义在compiler-gcc.h中，在使用时它们不一定都有__attribute字符串在。

1.5内建函数

以_builtin作为前缀（当然有的已经被宏定义过了）

__builtin_constant_p(x)判断在编译时是否就能确定为常量，返回1或0

__builtin_expect(exp, c)表示exp==c的概率很大，引导GCC做条件分支预测，提高CPU预取指令正确率

#define LIKELY(X) __builtin_expect(!!(x), 1) //x很可能为真
#define UNLIKELY(X) __builtin_expect(!!(x), 0) //x很可能为假
//!!是为了确保是bool值

__builtin_prefetch(const void *addr, int rw, int locality)主动预取，在使用addr的值之前把这个值加入到cache，rw指读写属性，locality指局部性强弱
```
#define prefetch(x) __builtin_prefetch(x)
#define prefetchw(x) __builtin_prefetch(x, 1)
```

1.6 UL

在数字定义时在后面加上UL后缀，这会把int类型强制转化为unsigned long，防止两个int相加溢出。

2.Linux内核中常用数据结构和算法

Linux内核有的数据结构非常常用因此封装好了一系列的数据结构以及和相关函数操作。

2.1链表

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

因为链表的数据区是各不相同的，所以是纯链表封装没有数据区。使用方式是嵌入到其他数据结构，如在page中嵌入lru链表的节点这样就加入了LRU链表。

<include/linux/mm_types.h>
struct page{
  ...
  struct list_head lru;
  ...
};

链表的初始化是将两个指针指向自身

<include/linux/list.h>
//动态初始化
static inline void INIT_LIST_HEAD(struct list_head *list){
  list->next = list;
  list->next = list;
}

//静态初始化，宏定义的展开结果是一个包含两个指针的结构，这两个指针都指向name自身
#define LIST_HEAD_INIT(name) {&(name), &(name)} 
//然后把上个结构体封装
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

inline是一个关键字，通常用于指示编译器在编译时将函数的代码插入到函数调用的地方，而不是像普通函数那样进行函数调用。因为函数调用通常涉及一定的开销，如参数传递、栈帧设置等，而inline函数可以减少这些开销。这样的函数被声明为内联函数，编译器会尝试在函数调用的地方直接插入函数体的代码。这可以提高函数调用的效率，特别是对于小而简单的函数。如果函数体过于复杂，内联可能会导致代码膨胀，反而降低性能。不过，最终是否内联函数由编译器决定。

添加节点到链表

<include/linux/list.h>
//添加到表头
void list_add(struct list_head *new, struct list_head *head)
//添加到表尾
void list_add_tail(struct list_head *new, struct list_head *head)

遍历节点接口

#define list_for_each(pos, head) \
  for (pos=(head)->next; pos!=(head); pos=pos->next)

但是主要还是访问这个节点嵌入的数据结构，比如前面提到的page结构体里的其他成员该怎么办？

#define list_entry(ptr, type, member) container_of(ptr, type, member)
/*
container_of宏定义在kernel头文件中
container_of先将0地址转化为type结构体指针，_mptr=ptr，类比page里lru成员的地址（因为假设在遍历LRU链表）
获取member在type结构体中的偏移量，type—>member，即page结构体中lru的偏移量
ptr-offset得到这个结构体的真实地址，现在这个指针指向page了
 */
 
 //真实案例
 <drivers/block/osdblk.c>
 //这个函数传入的参数不用管
 static ssize_t class_osdblk_list(struct class *c,
                struct class_attribute *attr, char *data){
    int n = 0;
    struct list_head *tmp; //当前遍历到的节点

    list_for_each(tmp, &osdblkdev_list){
      struct osdblk_device *osdev; //这个链表本来串连起来的结构体

      osdev = list_entry(tmp, struct osdblk_device, node);
      //链表的一个节点作为osdblk_device的结构体成员，名称是node

      //现在可以对拿到的结构体做一系列操作了
      n += sprintf(data+n, "%d %d ...", osdev->id, osdev->major, ...)
    }
    return n;
  }

2.2无锁环形缓冲区

环形缓冲区属于生产者-消费者模型的经典算法，好处是当一个元素被消耗后，其余元素不需要移动存储位置，减少复制操作。通过移动读指针和写指针实现缓冲区数据的读取和写入。内核使用KFIFO无锁环形缓冲区“first in first out”.

创建KFIFO

<include/linux/kfifo.h>
//动态分配
int kfifo_alloc(fifo, size, gfp_mask)
/*
创建大小为size的环形缓冲区
fifo指向kfifo数据结构
gfp_mask是内存分配的掩码
 */
//静态分配
#define DEFINE_KFIFO(fifo, type, size)
#define INIT_KFIFO(fifo)

入列

int kfifo_in(fifo, buf, n)
//将buf指针指向的n个元素复制到环形缓冲区

出列

#define kfifo_out(fifo, buf, n)
//从fifo复制n个到buf

获取缓冲区大小

#define kfifo_size(fifo) //缓冲区大小
#define kfifo_len(fifo)  //有多少有效数据元素
#define kfifo_is_empty(fifo) //是否为空
#define kfifo_is_full(fifo) //是否已满

与用户空间交互

#define kfifo_from_user(fifo, from, len, copied)
//将from指向的用户空间中len个数据元素复制到KFIFO中，最后一个参数copied表示成功复制了几个元素
#define kfifo_to_user(fifo, to, len, copied)