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

[Karim Seada]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20070607/16600ecf/attachment.html>