J'essaye d'implémenter un arbre rouge/noir sous Linux par task_struct en utilisant le code linux/rbtree.h
. Je peux obtenir un arbre rouge/noir insérant correctement dans un espace autonome dans le noyau comme un module mais quand j'essaye d'obtenir le même code pour fonctionner avec le rb_root
déclaré dans task_struct
ou task_struct->files_struct
, je reçois un SEGFAULT
chaque fois que j'essaie un insérer.Noyau Linux - Arbres Rouge/Noir
Voici quelques code:
En task_struct créer un struct rb_root
pour mon arbre (pas un pointeur). Dans init_task.h
, macro INIT_TASK(tsk)
, j'ai défini cela égal à RB_ROOT
. Pour faire un insert, j'utilise ce code:
rb_insert(&(current->fd_tree), &rbnode);
C'est là le problème se produit.
Ma commande d'insertion est l'insert standard qui est documenté dans tous les documents RBTree pour le noyau:
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;
}
Y at-il quelque chose que je suis absent?
Une raison pour que cela fonctionne correctement si j'ai fait une racine d'arbre en dehors de task_struct
? Si je fais rb_root
à l'intérieur d'un module, cet insert fonctionne correctement. Mais une fois que j'ai mis la racine de l'arbre réelle dans le task_struct
ou même dans le task_struct->files_struct
, je reçois un SEGFAULT
. Un nœud racine ne peut-il pas être ajouté dans ces structures?
Tous les conseils sont grandement appréciés. J'ai essayé presque tout ce que je peux penser.
Edit:
je reçois un SEGFAULT
sur la ligne suivante en essayant d'imprimer et de toute ligne qui accède à l'arbre. Avec cette ligne, vous devriez comprendre comment je gère les pointeurs. rb_entry
et rb_first
sont des méthodes déjà disponibles dans le noyau. current
est un pointeur vers une structure de tâche (processus de travail courant) et l'arbre est mon noeud racine (pas un pointeur) qui est un membre de la structure de tâche (j'ai ajouté). rb_first
doit passer un pointeur *rb_root
. Je fais ça mal.
printk(KERN_CRIT "node=%d\n", rb_entry(rb_first(&(current->tree)), struct rb_tree_struct, node)->fd_key);
Cela peut-il avoir quelque chose à voir avec la façon dont j'ajoute un nouveau nœud. Je fais juste struct mytype __name__ pour allouer de l'espace puis l'ajouter en utilisant l'insert ci-dessus. Dois-je utiliser le malloc (ou le kmalloc) ou puis-je juste allouer un nouveau nœud comme je le fais? – CodeRanger