Linux 内核 - 红/黑树
我正在尝试使用 linux/rbtree.h 中的代码在 Linux 中为每个 task_struct 实现一棵红/黑树。我可以将红/黑树正确插入内核中的独立空间（例如模块），但是当我尝试使用相同的代码来使用 task_struct< 中声明的 rb_root 运行时/code> 或 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);
I'm trying to implement a red/black tree in Linux per task_struct using code from linux/rbtree.h. I can get a red/black tree inserting properly in a standalone space in the kernel such as a module but when I try to get the same code to function with the rb_root declared in either task_struct or task_struct->files_struct, I get a SEGFAULT everytime I try an insert.
Here's some code:
In task_struct I create a rb_root struct for my tree (not a pointer).
In init_task.h, macro INIT_TASK(tsk), I set this equal to RB_ROOT.
To do an insert, I use this code:
rb_insert(&(current->fd_tree), &rbnode);
This is where the issue occurs.
My insert command is the standard insert that is documented in all RBTree documentation for the kernel:
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;
}
Is there something I'm missing?
Some reason this would work fine if I made a tree root outside of task_struct? If I make rb_root inside of a module this insert works fine. But once I put the actual tree root in the task_struct or even in the task_struct->files_struct, I get a SEGFAULT. Can a root node not be added in these structs?
Any tips are greatly appreciated. I've tried nearly everything I can think of.
Edit:
I get a SEGFAULT on the following line when trying to print and any line that accesses the tree. With this line you should get the understanding of how I'm handling the pointers. rb_entry and rb_first are methods already available in the kernel. current is a pointer to a task struct (current working process) and tree is my root node (not a pointer) which is a member of the task struct (I added). rb_first needs to pass a pointer *rb_root. I'm doing this wrong.
printk(KERN_CRIT "node=%d\n", rb_entry(rb_first(&(current->tree)), struct rb_tree_struct, node)->fd_key);
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是否 root 和/或 data 的指针值不是您所期望的？ 添加可能会很有用。
在
while()循环之前Could it be the pointer values of root and/or data aren't what you expect? It might be useful to add
before the
while()loop.