hanhan博客 - Linux 内核基础知识

Linux 内核基础知识

2023-3-4

[已归档]Linux 内核入门

实验：GCC 编译

本实验使用交叉编译器演示一下 gcc 的编译过程。首先编写一个简单的 C 语言程序，如代码清单 1 所示，并将其命名为 test.c。

代码清单 1 test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PAGE_SIZE 4096
#define MAX_SIZE 100*PAGE_SIZE
int main()
{
char* buf = (char*)malloc(MAX_SIZE);
memset(buf, 0, MAX_SIZE);
printf("buffer address=0x%p\n", buf);
free(buf);
return 0;
}

1. 预处理

gcc 的 -E 选项表示，只进行预处理阶段，不进行汇编、编译、链接的后续步骤。

tim@tim-vmwarevirtualplatform:~$ aarch64-linux-gnu-gcc -E test.c -o test.i

打开生成的 test.i 文件，可以看到其中添加了包含的头文件信息。

-E 可以简单记忆成 prEprocessing。

2. 汇编

gcc 的 -S 选项表示生成汇编代码。

tim@tim-vmwarevirtualplatform:~$ aarch64-linux-gnu-gcc -E test.i -o test.s

打开生成的 test.s 文件，可以看到生成的汇编代码。

-S 可以简单记忆成 aSsembly。

3. 编译

gcc 的 -c 选项表示编译生成二进制文件。

tim@tim-vmwarevirtualplatform:~$ aarch64-linux-gnu-gcc -c test.s -o test.o

-c 可以简单记忆成 compile。

4. 链接

最后一步是链接操作，将多个二进制文件（比如包含 printf 实现的二进制文件）链接到一起。此处我们使用静态链接，防止目标平台的库文件和我们交叉编译环境的库文件不一致。

tim@tim-vmwarevirtualplatform:~$ aarch64-linux-gnu-gcc test.o -o test --static

本地实验会提示找不到文件的链接错误，应该是链接环境有误，可以通过 --sysroot 指定。

但是我直接下载了发布好的交叉编译环境，发现直接没有问题了。

我们将最终生成的可执行文件放到 qemu 上执行。在《Linux 系统基础知识》中已经配置好，可以将文件放在 kmodules 目录中进行“共享”。

benshushu:mnt# ./test
buffer address=0x0xffffbb342010

实验：内核链表

本实验学习 Linux 内核中的链表机制，其相关接口函数定义在 include/linux/list.h 头文件中。此处，我们学习它的途径是将其移植到用户态中，并加以使用。

Linux 链表和我们平时使用的模板链表有些区别，它只定义链接信息，而不定义数据信息。

代码清单 2 include/linux/types.h

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

使用不同数据的话，需要将 list_head 封装其中。

struct num {
int i;
struct list_head list;
};

这涉及到一个问题，如何通过 list_head 获取到包含数据信息的结构体？如代码清单 3 所示，Linux 中采取的方法是使用当前 list_head 所在的位置，减去它在结构体中的偏移位置，就是整个结构体的首地址。我们可以通过完整的结构体访问各种想要的信息。

代码清单 3 include/linux/kernel.h

#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
((type *)(__mptr - offsetof(type, member))); })

最关键的思路就是 container_of() 函数。其他接口我们了解一下，当成 STL 的接口函数来进行使用就可以。这边介绍一下几个后续使用到的接口函数：

1. LIST_HEAD ：定义一个初始化好了的头节点。其前指针和后指针都指向头节点自己。

2. list_add_tail(new, head) ：将指定的新节点（new）添加到指定链表中（链表头节点 head）。

3. list_for_each_entry(pos, head, member) ：循环遍历指定的链表（链表头节点 head）。pos 是迭代的变量，它是包含 list_head 的完整结构体变量名；member 是 list_head 在 pos 结构体中的成员名称。

4. list_for_each_entry_safe(pos, n, head, member) ：和 list_for_each_entry 一样也是循环遍历指定的链表（链表头节点 head）。加了 safe 后缀，主要是用于删除节点场景，它能安全的删除当前遍历的节点，而不影响后续的遍历。实现方式就是传入的 n 这个临时指针，它会预先存储下一个节点的信息。

5. list_del(entry) ：删除指定节点。

移植工作

头文件的移植主要是删除不必要的内核头文件，以及手动添加需要的定义。操作并不复杂，没移植好编译也会报错，依据报错信息进行调整修改即可。

代码清单 4 移植的 list.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/
struct list_head {
struct list_head* next, * prev;
};
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
((type *)(__mptr - offsetof(type, member))); })
# define POISON_POINTER_DELTA 0
#define LIST_POISON1 ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x200 + POISON_POINTER_DELTA)
#define WRITE_ONCE(x, val) (*((volatile typeof(x) *) &(x)) = (val))
#define READ_ONCE(x) (*((volatile typeof(x) *)&(x)))
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head* list)
{
WRITE_ONCE(list->next, list);
list->prev = list;
}
static inline int __list_add_valid(struct list_head* new,
struct list_head* prev,
struct list_head* next)
{
return 1;
}
static inline int __list_del_entry_valid(struct list_head* entry)
{
return 1;
}
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(struct list_head* new,
struct list_head* prev,
struct list_head* next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head* new, struct list_head* head)
{
__list_add(new, head, head->next);
}
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head* new, struct list_head* head)
{
__list_add(new, head->prev, head);
}
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head* prev, struct list_head* next)
{
next->prev = prev;
WRITE_ONCE(prev->next, next);
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
static inline void __list_del_entry(struct list_head* entry)
{
if (!__list_del_entry_valid(entry))
return;
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head* entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head* old,
struct list_head* new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
static inline void list_replace_init(struct list_head* old,
struct list_head* new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
}
/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static inline void list_del_init(struct list_head* entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head* list, struct list_head* head)
{
__list_del_entry(list);
list_add(list, head);
}
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head* list,
struct list_head* head)
{
__list_del_entry(list);
list_add_tail(list, head);
}
/**
* list_bulk_move_tail - move a subsection of a list to its tail
* @head: the head that will follow our entry
* @first: first entry to move
* @last: last entry to move, can be the same as first
*
* Move all entries between @first and including @last before @head.
* All three entries must belong to the same linked list.
*/
static inline void list_bulk_move_tail(struct list_head* head,
struct list_head* first,
struct list_head* last)
{
first->prev->next = last->next;
last->next->prev = first->prev;
head->prev->next = first;
first->prev = head->prev;
last->next = head;
head->prev = last;
}
/**
* list_is_last - tests whether @list is the last entry in list @head
* @list: the entry to test
* @head: the head of the list
*/
static inline int list_is_last(const struct list_head* list,
const struct list_head* head)
{
return list->next == head;
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(const struct list_head* head)
{
return READ_ONCE(head->next) == head;
}
/**
* list_empty_careful - tests whether a list is empty and not being modified
* @head: the list to test
*
* Description:
* tests whether a list is empty _and_ checks that no other CPU might be
* in the process of modifying either member (next or prev)
*
* NOTE: using list_empty_careful() without synchronization
* can only be safe if the only activity that can happen
* to the list entry is list_del_init(). Eg. it cannot be used
* if another CPU could re-list_add() it.
*/
static inline int list_empty_careful(const struct list_head* head)
{
struct list_head* next = head->next;
return (next == head) && (next == head->prev);
}
/**
* list_rotate_left - rotate the list to the left
* @head: the head of the list
*/
static inline void list_rotate_left(struct list_head* head)
{
struct list_head* first;
if (!list_empty(head)) {
first = head->next;
list_move_tail(first, head);
}
}
/**
* list_is_singular - tests whether a list has just one entry.
* @head: the list to test.
*/
static inline int list_is_singular(const struct list_head* head)
{
return !list_empty(head) && (head->next == head->prev);
}
static inline void __list_cut_position(struct list_head* list,
struct list_head* head, struct list_head* entry)
{
struct list_head* new_first = entry->next;
list->next = head->next;
list->next->prev = list;
list->prev = entry;
entry->next = list;
head->next = new_first;
new_first->prev = head;
}
/**
* list_cut_position - cut a list into two
* @list: a new list to add all removed entries
* @head: a list with entries
* @entry: an entry within head, could be the head itself
* and if so we won't cut the list
*
* This helper moves the initial part of @head, up to and
* including @entry, from @head to @list. You should
* pass on @entry an element you know is on @head. @list
* should be an empty list or a list you do not care about
* losing its data.
*
*/
static inline void list_cut_position(struct list_head* list,
struct list_head* head, struct list_head* entry)
{
if (list_empty(head))
return;
if (list_is_singular(head) &&
(head->next != entry && head != entry))
return;
if (entry == head)
INIT_LIST_HEAD(list);
else
__list_cut_position(list, head, entry);
}
/**
* list_cut_before - cut a list into two, before given entry
* @list: a new list to add all removed entries
* @head: a list with entries
* @entry: an entry within head, could be the head itself
*
* This helper moves the initial part of @head, up to but
* excluding @entry, from @head to @list. You should pass
* in @entry an element you know is on @head. @list should
* be an empty list or a list you do not care about losing
* its data.
* If @entry == @head, all entries on @head are moved to
* @list.
*/
static inline void list_cut_before(struct list_head* list,
struct list_head* head,
struct list_head* entry)
{
if (head->next == entry) {
INIT_LIST_HEAD(list);
return;
}
list->next = head->next;
list->next->prev = list;
list->prev = entry->prev;
list->prev->next = list;
head->next = entry;
entry->prev = head;
}
static inline void __list_splice(const struct list_head* list,
struct list_head* prev,
struct list_head* next)
{
struct list_head* first = list->next;
struct list_head* last = list->prev;
first->prev = prev;
prev->next = first;
last->next = next;
next->prev = last;
}
/**
* list_splice - join two lists, this is designed for stacks
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(const struct list_head* list,
struct list_head* head)
{
if (!list_empty(list))
__list_splice(list, head, head->next);
}
/**
* list_splice_tail - join two lists, each list being a queue
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice_tail(struct list_head* list,
struct list_head* head)
{
if (!list_empty(list))
__list_splice(list, head->prev, head);
}
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static inline void list_splice_init(struct list_head* list,
struct list_head* head)
{
if (!list_empty(list)) {
__list_splice(list, head, head->next);
INIT_LIST_HEAD(list);
}
}
/**
* list_splice_tail_init - join two lists and reinitialise the emptied list
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* Each of the lists is a queue.
* The list at @list is reinitialised
*/
static inline void list_splice_tail_init(struct list_head* list,
struct list_head* head)
{
if (!list_empty(list)) {
__list_splice(list, head->prev, head);
INIT_LIST_HEAD(list);
}
}
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
/**
* list_first_entry - get the first element from a list
* @ptr: the list head to take the element from.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*
* Note, that list is expected to be not empty.
*/
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
/**
* list_last_entry - get the last element from a list
* @ptr: the list head to take the element from.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*
* Note, that list is expected to be not empty.
*/
#define list_last_entry(ptr, type, member) \
list_entry((ptr)->prev, type, member)
/**
* list_first_entry_or_null - get the first element from a list
* @ptr: the list head to take the element from.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*
* Note that if the list is empty, it returns NULL.
*/
#define list_first_entry_or_null(ptr, type, member) ({ \
struct list_head *head__ = (ptr); \
struct list_head *pos__ = READ_ONCE(head__->next); \
pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
})
/**
* list_next_entry - get the next element in list
* @pos: the type * to cursor
* @member: the name of the list_head within the struct.
*/
#define list_next_entry(pos, member) \
list_entry((pos)->member.next, typeof(*(pos)), member)
/**
* list_prev_entry - get the prev element in list
* @pos: the type * to cursor
* @member: the name of the list_head within the struct.
*/
#define list_prev_entry(pos, member) \
list_entry((pos)->member.prev, typeof(*(pos)), member)
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/**
* list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev)
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_next_entry(pos, member))
/**
* list_for_each_entry_reverse - iterate backwards over list of given type.
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_last_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_prev_entry(pos, member))
/**
* list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
* @pos: the type * to use as a start point
* @head: the head of the list
* @member: the name of the list_head within the struct.
*
* Prepares a pos entry for use as a start point in list_for_each_entry_continue().
*/
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
/**
* list_for_each_entry_continue - continue iteration over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Continue to iterate over list of given type, continuing after
* the current position.
*/
#define list_for_each_entry_continue(pos, head, member) \
for (pos = list_next_entry(pos, member); \
&pos->member != (head); \
pos = list_next_entry(pos, member))
/**
* list_for_each_entry_continue_reverse - iterate backwards from the given point
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Start to iterate over list of given type backwards, continuing after
* the current position.
*/
#define list_for_each_entry_continue_reverse(pos, head, member) \
for (pos = list_prev_entry(pos, member); \
&pos->member != (head); \
pos = list_prev_entry(pos, member))
/**
* list_for_each_entry_from - iterate over list of given type from the current point
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Iterate over list of given type, continuing from current position.
*/
#define list_for_each_entry_from(pos, head, member) \
for (; &pos->member != (head); \
pos = list_next_entry(pos, member))
/**
* list_for_each_entry_from_reverse - iterate backwards over list of given type
* from the current point
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Iterate backwards over list of given type, continuing from current position.
*/
#define list_for_each_entry_from_reverse(pos, head, member) \
for (; &pos->member != (head); \
pos = list_prev_entry(pos, member))
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member), \
n = list_next_entry(pos, member); \
&pos->member != (head); \
pos = n, n = list_next_entry(n, member))
/**
* list_for_each_entry_safe_continue - continue list iteration safe against removal
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Iterate over list of given type, continuing after current point,
* safe against removal of list entry.
*/
#define list_for_each_entry_safe_continue(pos, n, head, member) \
for (pos = list_next_entry(pos, member), \
n = list_next_entry(pos, member); \
&pos->member != (head); \
pos = n, n = list_next_entry(n, member))
/**
* list_for_each_entry_safe_from - iterate over list from current point safe against removal
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Iterate over list of given type from current point, safe against
* removal of list entry.
*/
#define list_for_each_entry_safe_from(pos, n, head, member) \
for (n = list_next_entry(pos, member); \
&pos->member != (head); \
pos = n, n = list_next_entry(n, member))
/**
* list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Iterate backwards over list of given type, safe against removal
* of list entry.
*/
#define list_for_each_entry_safe_reverse(pos, n, head, member) \
for (pos = list_last_entry(head, typeof(*pos), member), \
n = list_prev_entry(pos, member); \
&pos->member != (head); \
pos = n, n = list_prev_entry(n, member))
/**
* list_safe_reset_next - reset a stale list_for_each_entry_safe loop
* @pos: the loop cursor used in the list_for_each_entry_safe loop
* @n: temporary storage used in list_for_each_entry_safe
* @member: the name of the list_head within the struct.
*
* list_safe_reset_next is not safe to use in general if the list may be
* modified concurrently (eg. the lock is dropped in the loop body). An
* exception to this is if the cursor element (pos) is pinned in the list,
* and list_safe_reset_next is called after re-taking the lock and before
* completing the current iteration of the loop body.
*/
#define list_safe_reset_next(pos, n, member) \
n = list_next_entry(pos, member)
/*
* Double linked lists with a single pointer list head.
* Mostly useful for hash tables where the two pointer list head is
* too wasteful.
* You lose the ability to access the tail in O(1).
*/
#endif

验证

移植好头文件之后，我们就可以写样例进行测试了。

如代码清单 5 所示，我们先初始化链表 test_list；然后往其中依次添加 100 个元素（list_add_tail）；接着进行遍历打印（list_for_each_entry）；最后释放链表分配的内存（list_for_each_entry_safe、list_del）。

代码清单 5 list 样例

#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct num {
int i;
struct list_head list;
};
int main()
{
LIST_HEAD(test_list);
int i;
struct num* num;
struct num* num1;
/* Add */
printf("add 100 element into list\n");
for (i = 0; i < 100; i++)
{
num = (struct num*)malloc(sizeof(struct num));
num->i = i;
list_add_tail(&num->list, &test_list);
}
i = 0;
/* print list */
printf("print the list\n");
list_for_each_entry(num, &test_list, list)
{
printf("%2d ", num->i);
if ((i + 1) % 10 == 0)
printf("\n");
i++;
}
printf("\n");
/* Delete */
list_for_each_entry_safe(num, num1, &test_list, list)
{
list_del(&num->list);
free(num);
}
if (list_empty(&test_list))
printf("Free test_list successfully\n");
return 0;
}

机制中会利用到 typeof。这是 GNU C 扩展特有的，所以虽然是移植到用户态，VS编译器还是不能使用。

在 linux 上编译验证。

tim@tim-vmwarevirtualplatform:~$ gcc list.c -o list
tim@tim-vmwarevirtualplatform:~$ ./list
add 100 element into list
print the list
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
Free test_list successfully

实验：红黑树

本实验介绍 Linux 内核中的红黑树。红黑树的具体实现和概念就不介绍了，可以参考《算法导论》，这边介绍一下内核中定义的接口。相关接口函数在 include/linux/rbtree.h 头文件中定义。

1. rb_node ：红黑树节点的定义，包含左、右子节点指针，以及父节点的颜色。

struct rb_node {
unsigned long __rb_parent_color;
struct rb_node* rb_right;
struct rb_node* rb_left;
} __attribute__((aligned(sizeof(long))));

__rb_parent_color 即存储父节点的颜色，也存储父节点的指针。

低两位是存储颜色信息的。可以这么做的原因是 aligned(sizeof(long)) 对齐的缘故。

2. RB_ROOT ：定义红黑树的根节点。其实就是一个指向指向 NULL 的 rb_node。

3. rb_link_node、rb_insert_color ：插入的基本操作组合，和《算法导论》里的操作是一样的。rb_link_node 先将新节点插入到红黑树指定的位置，不涉及平衡调整。rb_insert_color 进行平衡调整。

4. rb_erase ：删除一个节点，并进行平衡调整。

5. rb_entry ：根据节点指针获取节点所属的结构体指针。这在上一节链表中已经了解过，是通过 container_of 实现的。

6. rb_first、rb_next ：rb_first 返回红黑树中的第一个节点。rb_next 返回指定节点的下一个节点。红黑树的遍历可以通过先获取 rb_first，在通过 rb_next 迭代实现。

这边可以学习一下 rb_next 的源码思路，因为之前写的二叉树遍历都是递归实现的。

首先 Linux 内核红黑树的大小存储顺序也是先序遍历的：先左子树、再根节点、再右子树。能迭代获取是因为存储了父节点信息。

获取一个节点的下一个节点：首先下一个节点肯定在右子树中，而且是右子树中最小的，即最左边的节点。如果没有右子树，从递归的流程上看，此时要进行递归回升了。如何判断是回升的哪个阶段：首先获取当前节点的父节点，如果当前节点是父节点的左孩子，那么下一个节点就是父节点（因为顺序是左子树->根）；如果当前节点是父节点的右孩子，代表本轮左子树->根->右子树的遍历已经完成，还需要继续递归回升，即继续查看父节点的父节点。以此类推。

内核中使用红黑树

我们先学习在内核环境使用红黑树。如代码清单 1 所示，在模块加载时我们往红黑树中插入节点，并打印遍历；模块卸载时，删除红黑树中的各个节点，并释放相关内存。

代码清单 6 内核中使用红黑树

#include <linux/init.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/mm.h>
#include <linux/rbtree.h>
MODULE_AUTHOR("Tim");
MODULE_DESCRIPTION(" ");
MODULE_LICENSE("GPL");
struct mytype
{
struct rb_node node;
int key;
};
struct rb_root mytree = RB_ROOT;
struct mytype* my_search(struct rb_root* root, int new)
{
struct rb_node* node = root->rb_node;
while (node)
{
struct mytype* data = container_of(node, struct mytype, node);
if (data->key > new)
node = node->rb_left;
else if (data->key < new)
node = node->rb_right;
else
return data;
}
return NULL;
}
int my_insert(struct rb_root* root, struct mytype* data)
{
struct rb_node** new = &(root->rb_node), * parent = NULL;
/* Figure out where to put new node */
while (*new)
{
struct mytype* this = container_of(*new, struct mytype, node);
parent = *new;
if (this->key > data->key)
new = &((*new)->rb_left);
else if (this->key < data->key)
new = &((*new)->rb_right);
else
return -1;
}
/* Add new node and rebalance tree */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return 0;
}
static int __init my_init(void)
{
int i;
struct mytype* data;
struct rb_node* node;
for (i = 0; i < 20; i += 2)
{
data = kmalloc(sizeof(struct mytype), GFP_KERNEL);
data->key = i;
my_insert(&mytree, data);
}
/* list all tree */
for (node = rb_first(&mytree); node; node = rb_next(node))
printk("key=%d\n", rb_entry(node, struct mytype, node)->key);
return 0;
}
static void __exit my_exit(void)
{
struct mytype* data;
struct rb_node* node;
for (node = rb_first(&mytree); node; )
{
data = rb_entry(node, struct mytype, node);
node = rb_next(node);
if (data)
{
rb_erase(&data->node, &mytree);
printk("erase key=%d\n", data->key);
kfree(data);
}
}
}
module_init(my_init);
module_exit(my_exit);

代码清单 2 时配套的 Makefile，编译后可以得到后缀为 ko 的内核模块文件。

代码清单 7 Makefile

BASEINCLUDE ?= /lib/modules/`uname -r`/build
obj-m := kernel_rbtree.o
all :
$(MAKE) -C $(BASEINCLUDE) M=$(PWD) modules;
clean:
$(MAKE) -C $(BASEINCLUDE) M=$(PWD) clean;
rm -f *.ko;

我们依次执行加载模块（insmod 命令）和卸载模块（rmmod 命令），观察打印的日志。

benshushu:mnt# insmod kernel_rbtree.ko
[ 397.092774] kernel_rbtree: loading out-of-tree module taints kernel.
[ 397.218984] key=0
[ 397.220627] key=2
[ 397.220743] key=4
[ 397.220825] key=6
[ 397.220916] key=8
[ 397.221032] key=10
[ 397.221143] key=12
[ 397.222381] key=14
[ 397.231708] key=16
[ 397.231900] key=18
benshushu:mnt# rmmod kernel_rbtree
[ 412.039057] erase key=0
[ 412.055859] erase key=2
[ 412.056499] erase key=4
[ 412.057642] erase key=6
[ 412.075173] erase key=8
[ 412.075880] erase key=10
[ 412.076525] erase key=12
[ 412.077179] erase key=14
[ 412.077854] erase key=16
[ 412.086132] erase key=18

移植红黑树

接着我们跟链表一样，将内核的红黑树代码移植到内核态使用。移植的操作和链表移植的操作是一样的。

代码清单 8 移植的 rbtree.h

/*
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
linux/include/linux/rbtree.h
To use rbtrees you'll have to implement your own insert and search cores.
This will avoid us to use callbacks and to drop drammatically performances.
I know it's not the cleaner way, but in C (not in C++) to get
performances and genericity...
See Documentation/rbtree.txt for documentation and samples.
*/
#ifndef _LINUX_RBTREE_H
#define _LINUX_RBTREE_H
#define NULL ((void *)0)
#define bool int
#define true 1
#define false 0
#define rcu_assign_pointer(p, v) (p) = (v)
#define WRITE_ONCE(x, val) (*((volatile typeof(x) *) &(x)) = (val))
#define unlikely(x) __builtin_expect(!!(x), 0)
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
((type *)(__mptr - offsetof(type, member))); })
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 */
struct rb_root {
struct rb_node* rb_node;
};
/*
* Leftmost-cached rbtrees.
*
* We do not cache the rightmost node based on footprint
* size vs number of potential users that could benefit
* from O(1) rb_last(). Just not worth it, users that want
* this feature can always implement the logic explicitly.
* Furthermore, users that want to cache both pointers may
* find it a bit asymmetric, but that's ok.
*/
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node* rb_leftmost;
};
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
#define RB_ROOT (struct rb_root) { NULL, }
#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
/* 'empty' nodes are nodes that are known not to 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))
extern void rb_insert_color(struct rb_node*, struct rb_root*);
extern void rb_erase(struct rb_node*, struct rb_root*);
/* Find logical next and previous nodes in a tree */
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 void rb_insert_color_cached(struct rb_node*,
struct rb_root_cached*, bool);
extern void rb_erase_cached(struct rb_node* node, struct rb_root_cached*);
/* Same as rb_first(), but O(1) */
#define rb_first_cached(root) (root)->rb_leftmost
/* Postorder iteration - always visit the parent after its children */
extern struct rb_node* rb_first_postorder(const struct rb_root*);
extern struct rb_node* rb_next_postorder(const struct rb_node*);
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
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);
extern void rb_replace_node_cached(struct rb_node* victim, struct rb_node* new,
struct rb_root_cached* root);
static inline void rb_link_node(struct rb_node* node, struct rb_node* parent,
struct rb_node** rb_link)
{
node->__rb_parent_color = (unsigned long)parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;
}
static inline void rb_link_node_rcu(struct rb_node* node, struct rb_node* parent,
struct rb_node** rb_link)
{
node->__rb_parent_color = (unsigned long)parent;
node->rb_left = node->rb_right = NULL;
rcu_assign_pointer(*rb_link, node);
}
#define rb_entry_safe(ptr, type, member) \
({ typeof(ptr) ____ptr = (ptr); \
____ptr ? rb_entry(____ptr, type, member) : NULL; \
})
/**
* rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
* given type allowing the backing memory of @pos to be invalidated
*
* @pos: the 'type *' to use as a loop cursor.
* @n: another 'type *' to use as temporary storage
* @root: 'rb_root *' of the rbtree.
* @field: the name of the rb_node field within 'type'.
*
* rbtree_postorder_for_each_entry_safe() provides a similar guarantee as
* list_for_each_entry_safe() and allows the iteration to continue independent
* of changes to @pos by the body of the loop.
*
* Note, however, that it cannot handle other modifications that re-order the
* rbtree it is iterating over. This includes calling rb_erase() on @pos, as
* rb_erase() may rebalance the tree, causing us to miss some nodes.
*/
#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
typeof(*pos), field); 1; }); \
pos = n)
#endif /* _LINUX_RBTREE_H */

代码清单 9 移植的 rbtree_augmented.h

#pragma once
/*
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
(C) 2012 Michel Lespinasse <walken@google.com>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
linux/include/linux/rbtree_augmented.h
*/
#ifndef _LINUX_RBTREE_AUGMENTED_H
#define _LINUX_RBTREE_AUGMENTED_H
#include "rbtree.h"
# define __always_inline inline
/*
* Please note - only struct rb_augment_callbacks and the prototypes for
* rb_insert_augmented() and rb_erase_augmented() are intended to be public.
* The rest are implementation details you are not expected to depend on.
*
* See Documentation/rbtree.txt for documentation and samples.
*/
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);
};
extern void __rb_insert_augmented(struct rb_node* node,
struct rb_root* root,
bool newleft, struct rb_node** leftmost,
void (*augment_rotate)(struct rb_node* old, struct rb_node* new));
/*
* Fixup the rbtree and update the augmented information when rebalancing.
*
* On insertion, the user must update the augmented information on the path
* leading to the inserted node, then call rb_link_node() as usual and
* rb_insert_augmented() instead of the usual rb_insert_color() call.
* If rb_insert_augmented() rebalances the rbtree, it will callback into
* a user provided function to update the augmented information on the
* affected subtrees.
*/
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, false, NULL, augment->rotate);
}
static inline void
rb_insert_augmented_cached(struct rb_node* node,
struct rb_root_cached* root, bool newleft,
const struct rb_augment_callbacks* augment)
{
__rb_insert_augmented(node, &root->rb_root,
newleft, &root->rb_leftmost, augment->rotate);
}
#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
rbtype, rbaugmented, rbcompute) \
static 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 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 \
};
#define RB_RED 0
#define RB_BLACK 1
#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
#define __rb_color(pc) ((pc) & 1)
#define __rb_is_black(pc) __rb_color(pc)
#define __rb_is_red(pc) (!__rb_color(pc))
#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
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;
}
static inline void
__rb_change_child(struct rb_node* old, struct rb_node* new,
struct rb_node* parent, struct rb_root* root)
{
if (parent) {
if (parent->rb_left == old)
WRITE_ONCE(parent->rb_left, new);
else
WRITE_ONCE(parent->rb_right, new);
}
else
WRITE_ONCE(root->rb_node, new);
}
static inline void
__rb_change_child_rcu(struct rb_node* old, struct rb_node* new,
struct rb_node* parent, struct rb_root* root)
{
if (parent) {
if (parent->rb_left == old)
rcu_assign_pointer(parent->rb_left, new);
else
rcu_assign_pointer(parent->rb_right, new);
}
else
rcu_assign_pointer(root->rb_node, new);
}
extern void __rb_erase_color(struct rb_node* parent, struct rb_root* root,
void (*augment_rotate)(struct rb_node* old, struct rb_node* new));
static __always_inline struct rb_node*
__rb_erase_augmented(struct rb_node* node, struct rb_root* root,
struct rb_node** leftmost,
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;
unsigned long pc;
if (leftmost && node == *leftmost)
*leftmost = rb_next(node);
if (!tmp) {
/*
* Case 1: node to erase has no more than 1 child (easy!)
*
* Note that if there is one child it must be red due to 5)
* and node must be black due to 4). We adjust colors locally
* so as to bypass __rb_erase_color() later on.
*/
pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, child, parent, root);
if (child) {
child->__rb_parent_color = pc;
rebalance = NULL;
}
else
rebalance = __rb_is_black(pc) ? parent : NULL;
tmp = parent;
}
else if (!child) {
/* Still case 1, but this time the child is node->rb_left */
tmp->__rb_parent_color = pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, tmp, parent, root);
rebalance = NULL;
tmp = parent;
}
else {
struct rb_node* successor = child, * child2;
tmp = child->rb_left;
if (!tmp) {
/*
* Case 2: node's successor is its right child
*
* (n) (s)
* / \ / \
* (x) (s) -> (x) (c)
* \
* (c)
*/
parent = successor;
child2 = successor->rb_right;
augment->copy(node, successor);
}
else {
/*
* Case 3: node's successor is leftmost under
* node's right child subtree
*
* (n) (s)
* / \ / \
* (x) (y) -> (x) (y)
* / /
* (p) (p)
* / /
* (s) (c)
* \
* (c)
*/
do {
parent = successor;
successor = tmp;
tmp = tmp->rb_left;
} while (tmp);
child2 = successor->rb_right;
WRITE_ONCE(parent->rb_left, child2);
WRITE_ONCE(successor->rb_right, child);
rb_set_parent(child, successor);
augment->copy(node, successor);
augment->propagate(parent, successor);
}
tmp = node->rb_left;
WRITE_ONCE(successor->rb_left, tmp);
rb_set_parent(tmp, successor);
pc = node->__rb_parent_color;
tmp = __rb_parent(pc);
__rb_change_child(node, successor, tmp, root);
if (child2) {
successor->__rb_parent_color = pc;
rb_set_parent_color(child2, parent, RB_BLACK);
rebalance = NULL;
}
else {
unsigned long pc2 = successor->__rb_parent_color;
successor->__rb_parent_color = pc;
rebalance = __rb_is_black(pc2) ? parent : NULL;
}
tmp = successor;
}
augment->propagate(tmp, NULL);
return rebalance;
}
static __always_inline void
rb_erase_augmented(struct rb_node* node, struct rb_root* root,
const struct rb_augment_callbacks* augment)
{
struct rb_node* rebalance = __rb_erase_augmented(node, root,
NULL, augment);
if (rebalance)
__rb_erase_color(rebalance, root, augment->rotate);
}
static __always_inline void
rb_erase_augmented_cached(struct rb_node* node, struct rb_root_cached* root,
const struct rb_augment_callbacks* augment)
{
struct rb_node* rebalance = __rb_erase_augmented(node, &root->rb_root,
&root->rb_leftmost,
augment);
if (rebalance)
__rb_erase_color(rebalance, &root->rb_root, augment->rotate);
}
#endif /* _LINUX_RBTREE_AUGMENTED_H */

代码清单 10 移植的 rbtree.c

/*
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
(C) 2012 Michel Lespinasse <walken@google.com>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
linux/lib/rbtree.c
*/
#include "rbtree_augmented.h"
#define EXPORT_SYMBOL(x)
/*
* red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
*
* 1) A node is either red or black
* 2) The root is black
* 3) All leaves (NULL) are black
* 4) Both children of every red node are black
* 5) Every simple path from root to leaves contains the same number
* of black nodes.
*
* 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
* consecutive red nodes in a path and every red node is therefore followed by
* a black. So if B is the number of black nodes on every simple path (as per
* 5), then the longest possible path due to 4 is 2B.
*
* We shall indicate color with case, where black nodes are uppercase and red
* nodes will be lowercase. Unknown color nodes shall be drawn as red within
* parentheses and have some accompanying text comment.
*/
/*
* Notes on lockless lookups:
*
* All stores to the tree structure (rb_left and rb_right) must be done using
* WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
* tree structure as seen in program order.
*
* These two requirements will allow lockless iteration of the tree -- not
* correct iteration mind you, tree rotations are not atomic so a lookup might
* miss entire subtrees.
*
* But they do guarantee that any such traversal will only see valid elements
* and that it will indeed complete -- does not get stuck in a loop.
*
* It also guarantees that if the lookup returns an element it is the 'correct'
* one. But not returning an element does _NOT_ mean it's not present.
*
* NOTE:
*
* Stores to __rb_parent_color are not important for simple lookups so those
* are left undone as of now. Nor did I check for loops involving parent
* pointers.
*/
static inline void rb_set_black(struct rb_node* rb)
{
rb->__rb_parent_color |= RB_BLACK;
}
static inline struct rb_node* rb_red_parent(struct rb_node* red)
{
return (struct rb_node*)red->__rb_parent_color;
}
/*
* Helper function for rotations:
* - old's parent and color get assigned to new
* - old gets assigned new as a parent and 'color' as a color.
*/
static inline void
__rb_rotate_set_parents(struct rb_node* old, struct rb_node* new,
struct rb_root* root, int color)
{
struct rb_node* parent = rb_parent(old);
new->__rb_parent_color = old->__rb_parent_color;
rb_set_parent_color(old, new, color);
__rb_change_child(old, new, parent, root);
}
static __always_inline void
__rb_insert(struct rb_node* node, struct rb_root* root,
bool newleft, struct rb_node** leftmost,
void (*augment_rotate)(struct rb_node* old, struct rb_node* new))
{
struct rb_node* parent = rb_red_parent(node), * gparent, * tmp;
if (newleft)
*leftmost = node;
while (true) {
/*
* Loop invariant: node is red.
*/
if (unlikely(!parent)) {
/*
* The inserted node is root. Either this is the
* first node, or we recursed at Case 1 below and
* are no longer violating 4).
*/
rb_set_parent_color(node, NULL, RB_BLACK);
break;
}
/*
* If there is a black parent, we are done.
* Otherwise, take some corrective action as,
* per 4), we don't want a red root or two
* consecutive red nodes.
*/
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 1 - node's uncle is red (color flips).
*
* G g
* / \ / \
* p u --> P U
* / /
* n n
*
* However, since g's parent might be red, and
* 4) does not allow this, we need to recurse
* at g.
*/
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 2 - node's uncle is black and node is
* the parent's right child (left rotate at parent).
*
* G G
* / \ / \
* p U --> n U
* \ /
* n p
*
* This still leaves us in violation of 4), the
* continuation into Case 3 will fix that.
*/
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 3 - node's uncle is black and node is
* the parent's left child (right rotate at gparent).
*
* G P
* / \ / \
* p U --> n g
* / \
* n U
*/
WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
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 {
tmp = gparent->rb_left;
if (tmp && rb_is_red(tmp)) {
/* Case 1 - color flips */
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_left;
if (node == tmp) {
/* Case 2 - right rotate at parent */
tmp = node->rb_right;
WRITE_ONCE(parent->rb_left, tmp);
WRITE_ONCE(node->rb_right, 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_left;
}
/* Case 3 - left rotate at gparent */
WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
WRITE_ONCE(parent->rb_left, 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;
}
}
}
/*
* Inline version for rb_erase() use - we want to be able to inline
* and eliminate the dummy_rotate callback there
*/
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) {
/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/
sibling = parent->rb_right;
if (node != sibling) { /* node == parent->rb_left */
if (rb_is_red(sibling)) {
/*
* Case 1 - left rotate at parent
*
* P S
* / \ / \
* N s --> p Sr
* / \ / \
* Sl Sr N Sl
*/
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 - sibling color flip
* (p could be either color here)
*
* (p) (p)
* / \ / \
* N S --> N s
* / \ / \
* Sl Sr Sl Sr
*
* This leaves us violating 5) which
* can be fixed by flipping p to black
* if it was red, or by recursing at p.
* p is red when coming from Case 1.
*/
rb_set_parent_color(sibling, parent,
RB_RED);
if (rb_is_red(parent))
rb_set_black(parent);
else {
node = parent;
parent = rb_parent(node);
if (parent)
continue;
}
break;
}
/*
* Case 3 - right rotate at sibling
* (p could be either color here)
*
* (p) (p)
* / \ / \
* N S --> N sl
* / \ \
* sl Sr S
* \
* Sr
*
* Note: p might be red, and then both
* p and sl are red after rotation(which
* breaks property 4). This is fixed in
* Case 4 (in __rb_rotate_set_parents()
* which set sl the color of p
* and set p RB_BLACK)
*
* (p) (sl)
* / \ / \
* N sl --> P S
* \ / \
* S N Sr
* \
* Sr
*/
tmp1 = tmp2->rb_right;
WRITE_ONCE(sibling->rb_left, tmp1);
WRITE_ONCE(tmp2->rb_right, sibling);
WRITE_ONCE(parent->rb_right, tmp2);
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
/*
* Case 4 - left rotate at parent + color flips
* (p and sl could be either color here.
* After rotation, p becomes black, s acquires
* p's color, and sl keeps its color)
*
* (p) (s)
* / \ / \
* N S --> P Sr
* / \ / \
* (sl) sr N (sl)
*/
tmp2 = sibling->rb_left;
WRITE_ONCE(parent->rb_right, tmp2);
WRITE_ONCE(sibling->rb_left, parent);
rb_set_parent_color(tmp1, sibling, RB_BLACK);
if (tmp2)
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
augment_rotate(parent, sibling);
break;
}
else {
sibling = parent->rb_left;
if (rb_is_red(sibling)) {
/* Case 1 - right rotate at parent */
tmp1 = sibling->rb_right;
WRITE_ONCE(parent->rb_left, tmp1);
WRITE_ONCE(sibling->rb_right, 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_left;
if (!tmp1 || rb_is_black(tmp1)) {
tmp2 = sibling->rb_right;
if (!tmp2 || rb_is_black(tmp2)) {
/* Case 2 - sibling color flip */
rb_set_parent_color(sibling, parent,
RB_RED);
if (rb_is_red(parent))
rb_set_black(parent);
else {
node = parent;
parent = rb_parent(node);
if (parent)
continue;
}
break;
}
/* Case 3 - left rotate at sibling */
tmp1 = tmp2->rb_left;
WRITE_ONCE(sibling->rb_right, tmp1);
WRITE_ONCE(tmp2->rb_left, sibling);
WRITE_ONCE(parent->rb_left, tmp2);
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
/* Case 4 - right rotate at parent + color flips */
tmp2 = sibling->rb_right;
WRITE_ONCE(parent->rb_left, tmp2);
WRITE_ONCE(sibling->rb_right, parent);
rb_set_parent_color(tmp1, sibling, RB_BLACK);
if (tmp2)
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
augment_rotate(parent, sibling);
break;
}
}
}
/* Non-inline version for rb_erase_augmented() use */
void __rb_erase_color(struct rb_node* parent, struct rb_root* root,
void (*augment_rotate)(struct rb_node* old, struct rb_node* new))
{
____rb_erase_color(parent, root, augment_rotate);
}
EXPORT_SYMBOL(__rb_erase_color);
/*
* Non-augmented rbtree manipulation functions.
*
* We use dummy augmented callbacks here, and have the compiler optimize them
* out of the rb_insert_color() and rb_erase() function definitions.
*/
static inline void dummy_propagate(struct rb_node* node, struct rb_node* stop) {}
static inline void dummy_copy(struct rb_node* old, struct rb_node* new) {}
static inline void dummy_rotate(struct rb_node* old, struct rb_node* new) {}
static const struct rb_augment_callbacks dummy_callbacks = {
.propagate = dummy_propagate,
.copy = dummy_copy,
.rotate = dummy_rotate
};
void rb_insert_color(struct rb_node* node, struct rb_root* root)
{
__rb_insert(node, root, false, NULL, dummy_rotate);
}
EXPORT_SYMBOL(rb_insert_color);
void rb_erase(struct rb_node* node, struct rb_root* root)
{
struct rb_node* rebalance;
rebalance = __rb_erase_augmented(node, root,
NULL, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase);
void rb_insert_color_cached(struct rb_node* node,
struct rb_root_cached* root, bool leftmost)
{
__rb_insert(node, &root->rb_root, leftmost,
&root->rb_leftmost, dummy_rotate);
}
EXPORT_SYMBOL(rb_insert_color_cached);
void rb_erase_cached(struct rb_node* node, struct rb_root_cached* root)
{
struct rb_node* rebalance;
rebalance = __rb_erase_augmented(node, &root->rb_root,
&root->rb_leftmost, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, &root->rb_root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase_cached);
/*
* Augmented rbtree manipulation functions.
*
* This instantiates the same __always_inline functions as in the non-augmented
* case, but this time with user-defined callbacks.
*/
void __rb_insert_augmented(struct rb_node* node, struct rb_root* root,
bool newleft, struct rb_node** leftmost,
void (*augment_rotate)(struct rb_node* old, struct rb_node* new))
{
__rb_insert(node, root, newleft, leftmost, augment_rotate);
}
EXPORT_SYMBOL(__rb_insert_augmented);
/*
* This function returns the first node (in sort order) of the tree.
*/
struct rb_node* rb_first(const struct rb_root* root)
{
struct rb_node* n;
n = root->rb_node;
if (!n)
return NULL;
while (n->rb_left)
n = n->rb_left;
return n;
}
EXPORT_SYMBOL(rb_first);
struct rb_node* rb_last(const struct rb_root* root)
{
struct rb_node* n;
n = root->rb_node;
if (!n)
return NULL;
while (n->rb_right)
n = n->rb_right;
return n;
}
EXPORT_SYMBOL(rb_last);
struct rb_node* rb_next(const struct rb_node* node)
{
struct rb_node* parent;
if (RB_EMPTY_NODE(node))
return NULL;
/*
* If we have a right-hand child, go down and then left as far
* as we can.
*/
if (node->rb_right) {
node = node->rb_right;
while (node->rb_left)
node = node->rb_left;
return (struct rb_node*)node;
}
/*
* No right-hand children. Everything down and left is smaller than us,
* so any 'next' node must be in the general direction of our parent.
* Go up the tree; any time the ancestor is a right-hand child of its
* parent, keep going up. First time it's a left-hand child of its
* parent, said parent is our 'next' node.
*/
while ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
return parent;
}
EXPORT_SYMBOL(rb_next);
struct rb_node* rb_prev(const struct rb_node* node)
{
struct rb_node* parent;
if (RB_EMPTY_NODE(node))
return NULL;
/*
* If we have a left-hand child, go down and then right as far
* as we can.
*/
if (node->rb_left) {
node = node->rb_left;
while (node->rb_right)
node = node->rb_right;
return (struct rb_node*)node;
}
/*
* No left-hand children. Go up till we find an ancestor which
* is a right-hand child of its parent.
*/
while ((parent = rb_parent(node)) && node == parent->rb_left)
node = parent;
return parent;
}
EXPORT_SYMBOL(rb_prev);
void rb_replace_node(struct rb_node* victim, struct rb_node* new,
struct rb_root* root)
{
struct rb_node* parent = rb_parent(victim);
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
/* Set the surrounding nodes to point to the replacement */
if (victim->rb_left)
rb_set_parent(victim->rb_left, new);
if (victim->rb_right)
rb_set_parent(victim->rb_right, new);
__rb_change_child(victim, new, parent, root);
}
EXPORT_SYMBOL(rb_replace_node);
void rb_replace_node_cached(struct rb_node* victim, struct rb_node* new,
struct rb_root_cached* root)
{
rb_replace_node(victim, new, &root->rb_root);
if (root->rb_leftmost == victim)
root->rb_leftmost = new;
}
EXPORT_SYMBOL(rb_replace_node_cached);
void rb_replace_node_rcu(struct rb_node* victim, struct rb_node* new,
struct rb_root* root)
{
struct rb_node* parent = rb_parent(victim);
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
/* Set the surrounding nodes to point to the replacement */
if (victim->rb_left)
rb_set_parent(victim->rb_left, new);
if (victim->rb_right)
rb_set_parent(victim->rb_right, new);
/* Set the parent's pointer to the new node last after an RCU barrier
* so that the pointers onwards are seen to be set correctly when doing
* an RCU walk over the tree.
*/
__rb_change_child_rcu(victim, new, parent, root);
}
EXPORT_SYMBOL(rb_replace_node_rcu);
static struct rb_node* rb_left_deepest_node(const struct rb_node* node)
{
for (;;) {
if (node->rb_left)
node = node->rb_left;
else if (node->rb_right)
node = node->rb_right;
else
return (struct rb_node*)node;
}
}
struct rb_node* rb_next_postorder(const struct rb_node* node)
{
const struct rb_node* parent;
if (!node)
return NULL;
parent = rb_parent(node);
/* If we're sitting on node, we've already seen our children */
if (parent && node == parent->rb_left && parent->rb_right) {
/* If we are the parent's left node, go to the parent's right
* node then all the way down to the left */
return rb_left_deepest_node(parent->rb_right);
}
else
/* Otherwise we are the parent's right node, and the parent
* should be next */
return (struct rb_node*)parent;
}
EXPORT_SYMBOL(rb_next_postorder);
struct rb_node* rb_first_postorder(const struct rb_root* root)
{
if (!root->rb_node)
return NULL;
return rb_left_deepest_node(root->rb_node);
}
EXPORT_SYMBOL(rb_first_postorder);

代码清单 11 是移植好的测试代码，基本和内核测试代码是一样的使用。其中 check() 函数是新的，它的作用是检查红黑树的正确性。检查包括：插入的内容顺序是否正确；是否没有相邻的红色节点；根的左右子树的黑节点数量是否相等。

代码清单 11 用户态代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "rbtree_augmented.h"
#define NODES 10000
struct test_node
{
struct rb_node rb;
int key;
int val;
int augmented;
};
static struct rb_root root = RB_ROOT;
static struct test_node nodes[NODES];
static void insert(struct test_node* node, struct rb_root* root)
{
struct rb_node** new = &(root->rb_node), * parent = NULL;
int key = node->key;
while (*new)
{
parent = *new;
if (key < rb_entry(parent, struct test_node, rb)->key)
new = &parent->rb_left;
else
new = &parent->rb_right;
}
rb_link_node(&node->rb, parent, new);
rb_insert_color(&node->rb, root);
}
void erase(struct test_node* node, struct rb_root* root)
{
rb_erase(&node->rb, root);
}
static int black_path_count(struct rb_node* rb)
{
int count;
for (count = 0; rb; rb = rb_parent(rb))
count += !rb_is_red(rb);
return count;
}
static void check(int nr_nodes)
{
struct rb_node* rb;
int count = 0, blacks = 0;
int prev_key = 0;
for (rb = rb_first(&root); rb; rb = rb_next(rb))
{
struct test_node* node = rb_entry(rb, struct test_node, rb);
if (node->key < prev_key)
printf("[WARN] node->key(%d) < prev_key(%d)\n", node->key, prev_key);
if (rb_is_red(rb) && (!rb_parent(rb) || rb_is_red(rb_parent(rb))))
printf("[WARN] two red nodes\n");
if (!count)
blacks = black_path_count(rb);
else if ((!rb->rb_left || !rb->rb_right) && (blacks != black_path_count(rb)))
printf("[WARN] black count wrong\n");
prev_key = node->key;
count++;
}
}
void print_rbtree(struct rb_root* tree)
{
struct rb_node* node;
for (node = rb_first(tree); node; node = rb_next(node))
printf("%d ", rb_entry(node, struct test_node, rb)->key);
printf("\n");
}
int search_rbtree(struct rb_root* tree, int num)
{
struct rb_node* node;
for (node = rb_first(tree); node; node = rb_next(node))
{
if (num == rb_entry(node, struct test_node, rb)->key)
return true;
}
return false;
}
int main()
{
int i, j;
int num;
for (i = 0; i < NODES; i++)
{
nodes[i].key = i;
nodes[i].val = i;
}
/* insert */
for (j = 0; j < NODES; j++)
{
insert(nodes + j, &root);
}
/* check */
check(0);
//print_rbtree(&root);
while (1)
{
num = -2;
printf("Please input the num which you want to search in rbtree.\n");
printf("The input num should be 0 <= input num < 10000\n");
printf("Input -1 to exit\n");
printf(">>> ");
scanf("%d", &num);
if (num == -1)
goto exit;
if (num < 0 || num > 10000)
{
printf("WARNNING: Invalild input number!\n");
continue;
}
if (search_rbtree(&root, num))
printf("RESULT: Found %d in the rbtree\n", num);
else
printf("RESULT: Not Found %d in the rbtree\n", num);
}
exit:
/* erase */
for (j = 0; j < NODES; j++)
erase(nodes + j, &root);
return 0;
}

Tongtong