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

Karim Seada (spam-protected)
Thu Jun 7 23:24:44 CEST 2007

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

To fix this problem I added:
if (!right) return;
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

Best Regards,
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20070607/16600ecf/attachment.html>

More information about the Olsr-dev mailing list