[Kos-dev] Re: Meditations de la journee

[d2]

Bonjour,

>>>>> "Thomas" == Thomas Petazzoni <thomas.petazzoni@enix.org> writes:
    Thomas> Ouais, mais j'ai peur que cette regle ne suffise pas. En
    Thomas> effet, on risque (je sais pas) d'avoir besoin de parcourir
    Thomas> l'arbre dans l'autre sens. Et alors la on va etre dans la
    Thomas> merde.

J'avoue que je ne vois pas non plus de contre-exemple pour le
moment. On pourrait par exemple craindre les loockups de '..', mais en
fait ils ne semblent pas dangereux, puisqu'on a alors des graphes
orientes cycliques (a cause des '..') plutot que des arbres. Ce qui
voudrait dire que le lookup de '..' revient a parcourir l'arbre
toujours dans le sens de la descente pere -> fils.

Si on veut parcourir dans les 2 sens (en imaginant que ce soit
necessaire), il faudrait splitter en 2 le lock de chaque noeud : un
lock (ou compteur de ref) pour etre sur que le noeud ne disparait pas
(pas supprime de l'arbre, pas kfree()) pdt qu'on le regarde de pres,
et un lock sur la liste des fils. Genre :

  struct node {
    lock node_lock; /* ou compteur de ref, ou lock+ref_cnt */

    struct node *parent;
    lock children_lock;
    struct node *cildren;

    ctruct node *prev, *next;

    ...data...
  }

Parce que dans ce cas, quand on descend vers les fils, on fait :

  lock(node->node_lock); /* On atomic_inc(node->node_ref_cnt) */
  ## travailler sur le noeud;
  lock_read(node->cildren_lock)
  unlock(node->node_lock); /* On atomic_dec(node->node_ref_cnt) */
  ## choisir un fils;
  lock(fils->node_lock); /* On atomic_inc(fils->node_ref_cnt) */
  unlock_read(node->children_lock);
  ## node = fils;
  ## travailler sur le noeud...


Quand on remonte vers les parents :

  lock(node->node_lock); /* On atomic_inc(node->node_ref_cnt) */
  ## travailler sur le noeud
  lock(node->parent->node_lock); /* On atomic_inc(node->parent->node_ref_cnt) */
  unlock(node->node_lock); /* On atomic_dec(node->node_ref_cnt) */
  ## travailler sur le noeud...

Je pense que ca marche (aucune garantie : a verifier de tres pres),
tant qu'en cours de route on ne renverse pas le sens de la marche : si
on descend, on descend jusqu'a ce qu'on relache tout lock, et on ne
choisit pas de remonter en cours de route alors qu'on possede tjs un
noeud locké. Idem si on remonte.

A noter qu'on peut remplacer, ou completer, le node_lock par un
compteur de references plutot qu'un spinlock. Parce que ce qui compte
qd on fait lock(node->node_lock), c'est que le noeud ne soit pas
supprime en cours de route ; ce n'est pas d'avoir une exclusivite
quelconque sur le noeud, *sauf* si '## travailler sur le noeud'
requiert une telle exclusivite.

Bonne journee,

-- 
d2