Linux Kernel - Red/Black Trees

Я пытаюсь реализовать красное/черное дерево в Linux на task_struct с помощью кода от linux/rbtree.h. Я могу правильно вставить красное/черное дерево в отдельном пространстве в ядре, таком как модуль, но когда я пытаюсь получить тот же код для работы с rb_root, объявленным либо в task_struct, либо в task_struct->files_struct, я получаю SEGFAULT каждый раз, когда я пытаюсь вставить.Linux Kernel - Red/Black Trees

Вот код:

В 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. Может ли корневой узел не добавляться в эти структуры?

Любые советы приветствуются. Я пробовал почти все, что мог придумать.

Edit:

Я получаю 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);

источник

2010-04-20 CodeRanger

Может ли это иметь какое-либо отношение к тому, как я добавляю новый узел. Я просто делаю struct mytype __name__ для выделения пространства, а затем добавляю его, используя вставку выше. мне нужно использовать malloc (или kmalloc), или я могу просто выделить новый узел, как я это делаю? – CodeRanger

Не могут ли значения указателя на корень и/или данные быть ожидаемыми? Возможно, было бы полезно добавить

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

до while() петля.

источник

2010-04-20 16:24:28 ctuffli

Я получаю SEGFAULT в следующей строке при попытке печати и любой строке, которая обращается к дереву. С этой строкой вы должны понять, как я обрабатываю указатели. rb_entry и rb_first - это методы, уже доступные в ядре. current - указатель на структуру задачи (текущий рабочий процесс), а tree - это мой корневой узел (не указатель), который является членом структуры задачи. rb_first необходимо передать указатель * rb_root. Я делаю это неправильно. printk (KERN_CRIT "node =% d \ n", rb_entry (rb_first (& (current-> tree)), struct rb_tree_struct, node) -> fd_key); – CodeRanger

Linux Kernel - Red/Black Trees

ответ

Смежные вопросы