Linux Kernel - Red/Black Trees

Question

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);

Answer 1

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.