linux-kernel - Linux 内核 - 红/黑树

Question

我正在尝试使用 linux/rbtree.h 中的代码在 Linux 中的每个 task_struct 中实现一个红/黑树。我可以在内核的独立空间(例如模块)中正确插入红/黑树，但是当我尝试使相同的代码与 task_struct< 中声明的 rb_root 一起运行时 或 task_struct->files_struct，我每次尝试插入时都会得到一个 SEGFAULT。

这是一些代码:

在 task_struct 中，我为我的树创建了一个 rb_root 结构(不是指针)。在 init_task.h 中，宏 INIT_TASK(tsk)，我将其设置为等于 RB_ROOT。要插入，我使用以下代码:

rb_insert(&(current->fd_tree), &rbnode);

这就是问题发生的地方。

我的插入命令是标准插入命令，它记录在所有 RBTree 内核文档中:

  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);
        int result = strcmp(data->keystring, this->keystring);

        parent = *new;
        if (result < 0)
            new = &((*new)->rb_left);
        else if (result > 0)
            new = &((*new)->rb_right);
        else
            return FALSE;
    }

    /* Add new node and rebalance tree. */
    rb_link_node(&data->node, parent, new);
    rb_insert_color(&data->node, root);

    return TRUE;
  }

有什么我想念的吗？

如果我在 task_struct 之外创建一个树根，这会正常工作吗？如果我在模块内创建 rb_root，则此插入工作正常。但是一旦我将实际的树根放入 task_struct 甚至 task_struct->files_struct 中，我就会得到一个 SEGFAULT。这些结构体可以不加根节点吗？

非常感谢任何提示。我已经尝试了几乎所有我能想到的方法。

---

编辑:

尝试打印和访问树的任何行时，我在下一行得到一个 SEGFAULT。通过这一行，您应该了解我是如何处理指针的。 rb_entry 和 rb_first 是内核中已经可用的方法。 current 是指向任务结构(当前工作进程)的指针，树是我的根节点(不是指针)，它是任务结构(我添加的)的成员。 rb_first需要传递一个指针*rb_root。我做错了。

printk(KERN_CRIT "node=%d\n", rb_entry(rb_first(&(current->tree)), struct rb_tree_struct, node)->fd_key);

Answer 1

会不会是 root 和/或 data 的指针值不是您所期望的？添加可能有用

printk("%s: root=%p data=%p\n", __func__, root, data);

在 while() 循环之前。