Linux Kernel - Red/Black Trees
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);
Could it be the pointer values of root and/or data aren't what you expect? It might be useful to add
printk("%s: root=%p data=%p\n", __func__, root, data);
before the while()
loop.
精彩评论