将项目添加到Linux内核链接列表 [英] Adding items to a Linux kernel linked list

问题描述

我在代码中使用 linux/list.h 来实现队列/堆栈行为.头/尾添加的API如下:

I am using linux/list.h in my code for implementing queue/stack behavior. The API for adding at head/tail is as below:

static inline void list_add(struct list_head *new, struct list_head *head)
{
         __list_add(new, head, head->next);
}

类似用于 list_add_tail .令人惊讶的是，它什么也不返回( void )，因此这意味着使用此API向内核添加列表始终是成功的.我知道这里没有 full 的概念，但是如果无法为新节点分配内存以及其他可能的原因怎么办?

Similar is for list_add_tail. Surprisingly, it returns nothing (void), so does it mean that addition to list in kernel using this API is always successful. I know that there is no concept of full here but what if memory allocation for new node is not available and other possible reasons?

推荐答案

list API不会动态分配任何内存.我自己发现这件事有些令人费解.这里的问题是 Linux 是用 C 编写的，而不是 C++，而是以一种非常面向对象的方式实现的东西，但在 C 中它看起来像是由内而外.它的工作方式如下(这也适用于其他几种Linux API，例如 kobj ):

The list API does not dynamically allocate any memory. I found this thing a bit puzzling, myself. Problem here is that Linux is written in C, not C++, but implements things in a quite object-oriented way, but in C it looks like inside out. It works as follows (this applies to several other Linux APIs, too, e.g. kobj):

您定义一些 struct ，它应该是列表的成员.与通常想到的链接列表相反，该对象不会通过分配一些不透明的列表项并具有指向实际对象的指针而放入列表中，因此您将 struct list_head 设置为实际上是您的 struct 的成员:

You define some struct, which should be member of a list. In opposite of how you would usually think of linked lists, this object won't be put into the list by allocating some opaque list item and have a pointer pointing to your actual object, you make struct list_head an actual a member of your struct:

struct something {
    struct list_head list;
    uint8_t some_datum;
    uint16_t some_other_datum;
    void *a_pointer;
};

您的列表将是独立 struct list_head :

static LIST_HEAD(list_of_somethings);

要将元素添加到 list_of_somethings 中，您现在将执行类似的操作

To add elements to list_of_somethings you now would do something like

struct something *s = kmalloc(sizeof(*s), GFP_KERNEL);
s->some_datum = 23;
s->some_other_datum = 0xdeadbeef;
s->a_pointer = current;
list_add(&s->list, &list_of_somethings);

换句话说，您已经分配了元素.这看起来很怪异，但是像f * ck一样优雅.这种设计模式"允许在C语言中使用类型不透明的列表，而这在另一种情况下很难做到:列表本身只是一堆指向每个结构的 struct list_head 其他.当您知道要作为程序员使用的实际 struct 时，您知道此 struct 的哪个元素是实际的 list_head 并可以使用 container_of 宏以获取指向您最终放入列表的 struct 的指针:

In other words, you have the element allocated already. This looks completely weird, but is elegant as f*ck. This "design-pattern" allows to have type-opaque lists in C, which would not be easy to do in another way: A list on its own is just a bunch of struct list_heads pointing to each other. As you know which actual struct you are expeting as a programmer, you know which element of this struct is the actual list_head and can use the container_of macro to get the pointer to the eventual struct you put into the list:

struct list_head *p = &list_of_somethings.next;
struct something *s = container_of(p, struct something, list);
pr_notice("some data = %i\n", s->some_data);

请注意，代表列表本身的实际 struct list_head 由< linux/list.h> 中定义的迭代宏(即

Notice that the actual struct list_head representing the list itself is handled specially by the iteration macros defined in <linux/list.h>, i.e.

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

list_of_somethings 的地址将用于确定迭代是否到达列表的末尾(或实际上再次到达列表对象).这也是为什么将一个空列表定义为具有 next 和 prev 指向 struct list_head 本身的原因.

The address of list_of_somethings will be used to determine whether iterating reached the end of the list (or actually the list-object again). This is also the reason, why an empty list is defined as having next and prev point to the struct list_head itself.

我也需要一些时间来解决这个问题.;)

I needed some time to wrap my head around this, too. ;)

这篇关于将项目添加到Linux内核链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！