logo标签列表

C: Linux内核数据结构中的内置链表用法

clinux-kernelkernel
5
我正在尝试将一个系统调用添加到我的Linux内核中，并且使用内置的链表结构会非常有优势，因为我正在修改task_struct（通过添加链表），而task_struct中已经有了很多struct list_head以便于其他目的。为了保持一致性，我想继续使用这个数据结构。
我遇到的问题是，我并不完全理解如何使用这个结构。例如，我看到他们有“struct list_head children”。然而，这个结构的实现只是一个“*next”和“*last”。
我已经查阅了在线示例，每个示例都说，好吧，制作一个...
struct node{
    int data;
    struct list_head list;
};

但是这不会表明我应该在我的task_struct中包括哪种数据结构。
struct node list;

如果我使用list_head，我不太明白如何初始化结构以包含我想要的数据。

基本上，我想添加一个系统调用的链表，并将它们作为char*（可读格式）的链表附加到进程中。

目前，获取系统调用信息的语义并不重要... 我只需要弄清楚如何让链表与task_struct一起工作。

编辑：例如我想做什么：

我已经获得了一个函数执行的系统调用列表。 我将这些保留在单独的char*变量中。 我想在进程的task_struct中添加一个列表，以跟踪所有这些系统调用。

例如

进程'abc'调用 printf 〜> 等同于“WriteScreen” getchar 〜> 等同于“ReadKey”

现在我有一个用户空间代码，其中包含这两个字符串。 我调用一个系统调用（每个标记一次），将这些系统调用与该进程进行“标记”。

在这两个调用之后，“abc”的task_struct具有列表

abc->task_struct->tag_list

此列表包含“WriteScreen”和“ReadKey”。

稍后，我将使用这些标记打印调用WriteScreen、ReadKey等进程的列表。在找到如何使用列表适当地存储附加到进程的字符串之后，将实现这些内容。

3个回答
4

因此，与其创建进程列表（task_struct），你要完成的是每个进程的列表。

这意味着每个进程都将拥有自己的列表，即自己的列表头。

除了next/prev指针之外，该列表还将存储单个数据片段，实际上是一个字符串（可以是字符串本身或指向其他地方的指针）。

因此，列表节点将会是：

struct my_node {
    struct list_head list;
    char data[100]; // arbitrarily set to 100; could be also char*
}

task_struct应该增加一个新的列表头：

struct task_struct {
  // many members that contains info about a process
  ...

  struct list_head my_list;
}

是的。你会注意到，无论是进程属于列表还是列表属于进程，成员都是相同的；只是它的使用不同。

现在，当一个进程被创建时，你应该初始化列表头（因为每个进程都有一个新的列表）：

struct task_struct *new_process;
INIT_LIST_HEAD(&new_process->my_list);

为了插入一个新的节点（假设你已经创建并分配了内存并初始化了其数据）：
struct my_node *node; 
struct task_struct *a_process;

[... my_node initialized ...]
[... a_proccess obtained somehow ...]

list_add_tail(&node->list, &a_process->my_list);

要遍历元素：

struct my_node *p;
struct task_struct *a_process

// list is the member name (yes, the member name) of your list inside my_node
list_for_each_entry(p, &a_process->my_list, list) {
  // do whatever you want with p
}

编辑：

请注意，您有其他方法可以完成您尝试做的事情，而不必诉诸复杂的链表。

例如，您可以分配一个单一的字符数组，并通过某些字符（逗号、句号等）将字符串列表进行编码。这样做：

"WriteScreen,ReadKey\0"

在这种情况下，您应该注意缓冲区限制，以免溢出。另一方面，您不必担心分配和释放列表节点。
2

关于Linux内核链表的详细参考资料，请访问http://www.makelinux.net/ldd3/chp-11-sect-5。

您可以按照以下方式初始化结构体：

struct node node_var = {
    .data = 0,
    .list = LIST_HEAD_INIT(node_var.list)
}

您可以像这样遍历列表：
struct list_head *phead;
list_for_each(phead, node_var.list)
{
   struct node * pnode = list_entry(phead, struct node node_var, list);
   // Do what you may with the pnode.
}

确实看起来很奇怪。我们通过使用指向struct list_head字段的指针来获得指向struct node类型的指针。这个魔法是由list_entry内部调用的container_of宏完成的。

希望我有所帮助。

2

编辑：在提问者提供更清晰的解释之前，本答案已经给出。

你应该只向task_struct添加一个新成员：

struct task_struct {
  // many members that contains info about a process
  ...
  // then come the lists that a process may participate
  ...
  // then you amend with your new list
  struct list_head my_list;
}

这种增强本身不会有任何作用，因为没有人会更改或访问此成员。

您应该在其他地方声明列表头部（例如全局变量），然后可以开始向列表中添加进程（task_struct）。

LIST_HEAD(my_list_head); // this will declare, define and initialize a new variable:
                         // an empty list.

Linux内核中的链表宏将为您处理一切。
task_struct *a_given_process; // assigned elsewhere, maybe passed as parameter to current function
list_add_tail(&a_given_process->my_list, my_list_head); // an example

编辑：

遍历项目：

struct task_struct *p;

// my_list_head is the head of your list (declared with LIST_HEAD)
// my_list is the member name (yes, the member name) of your list inside task_struct
list_for_each_entry(p, my_list_head, my_list) {
  // do whatever you want with p
}
另外，这似乎有点像它将包含进程本身的列表，而不是每个进程的char*列表？我读错了吗？ - Aserian
@Aserian 是的，该列表包含进程本身。 - rslemos
Linux内核链表的实现非常聪明。当我第一次掌握其内部工作原理时（大约10年前），我感到非常惊叹。你应该花些时间仔细理解它。只要这样做，你的C语言技能肯定会有很大提高。我的确有所进步。 - rslemos
好的，我会尽力弄清楚。连接列表后，如何检索数据还不是很确定？ - Aserian
@Aserian 使用 list_for_each_entry 宏（类似于 for 循环遍历列表中的条目）。我将编辑答案以举例说明。 - rslemos
显示剩余7条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接