[Olsr-dev] Potential Bug and Fix in lq_avl.c

[Hannes Gredler]

karim,

the avl implementation is pretty solid. - if you see corruptions then
in most cases you have directly touched avl datastructures (without
using the avl_ () call API.

to give you an example - when i was doing the SPF re-implementation
of olsrd i had several crashes of this kind as well, and it turned out
that i was chenging the key values without removing the node from the tree.

in your example given belwo you should find out who initally corrupts the
tree rather than mitigating the effects of the tree corruption.

HTH,

/hannes


On Thu, Jun 07, 2007 at 02:24:44PM -0700, Karim Seada wrote:
|    Dear All,
|    It seems to me that there is a bug in lq_avl.c that causes the system
|    to crash under some scenarios.  In my application, the crash sometimes
|    happens at the beginning when a node is joining the network, or in
|    another scenario of 3 nodes, when one of the nodes leaves the network,
|    one of the 2 remaining nodes crashes.
|    I traced the reason for the crash and it happens through the following
|    functions at lq_route.c and lq_avl.c:  olsr_calculate
|    _lq_routing_table() -> add_vertex() ->  avl_insert() -> post_insert()
|    -> rotate_left()
|    ///////////////////////////////////////////////////////////////////////
|    ////////////////////////////////////
|    static void rotate_left (struct avl_tree *tree, struct avl_node *node)
|    {
|       struct avl_node *right, *parent;
| 
|       right = node->right;
|       parent = node->parent;
|       right->parent = parent;
|       node->parent = right;
|    ///////////////////////////////////////////////////////////////////////
|    ////////////////////////////////////////
|    In some cases right is NULL, causing right->parent to cause a
|    segmentation fault.
|    To fix this problem I added:
|    if (!right) return;
|    before
|    right->parent = parent;
|    (and a similar check to rotate_right: if (!left) return; before
|    left->parent = parent;)
|    which seems to be working fine in my small topology.
|    I haven't looked into the code in detail, so I would appreciate if
|    other developers who are more involved with the code let me know if
|    that makes sense and whether this fix is sufficient and does not have
|    other consequuences.
|    Best Regards,
|    Karim

| -- 
| Olsr-dev mailing list
| (spam-protected)
| https://lists.olsr.org/mailman/listinfo/olsr-dev