tree: fix array underruns found by ubsan.

* tree.c (tn_find_low): In this function it may happen that
we are looking for a low bound that is beyond the highest value in the
tree. In this situation, tdi->lastnode is nil; the loop that walks back
up the path will not find it, and underrun. Now the word before
the path array is the tree_iter_state, which is zero. That zero word
terminates the loop so things work by fluke.
(tr_find_rebuild_scapegoat): Firstly, since in this function we
pre-decrement ti->depth, we guard the whole thing by ti->depth > 0.
This is just a precaution; the algorithm guarantees that a scapegoat
will be found, so this will not recurse to the depth == 0 case.
The main fix here is this:  we sometimes call tr_rebuild in the
case when the parent is the root node. In that case, there is no
grandparent. The path is empty and we are accessing before the array
to try to fetch the nonexistent grandparent. Again, by fluke,
there is a zero there thanks to the tree_iter_state which turns
into a null pointer that tells tr_rebuild that the node has no parent.
The correct way is to check the depth and pass nil as the grandparent
if ti->depth is zero.

1 files changed, 17 insertions, 11 deletions

diff --git a/tree.c b/tree.c
index f46cabdb..a2127bbc 100644
--- a/tree.c
+++ b/tree.c
@@ -293,10 +293,12 @@ static void tn_find_low(val node, struct tree_diter *tdi,
       }
     }
 
-    while (trit->path[trit->depth - 1] != tdi->lastnode)
+    if (tdi->lastnode) {
+      while (trit->path[trit->depth - 1] != tdi->lastnode)
+        trit->depth--;
       trit->depth--;
-    trit->depth--;
-    trit->state = tr_find_low_prepared;
+      trit->state = tr_find_low_prepared;
+    }
   }
 }
 
@@ -349,14 +351,18 @@ static void tr_find_rebuild_scapegoat(val tree, struct tree *tr,
                                       struct tree_iter *ti,
                                       val child, ucnum child_size)
 {
-  val parent = ti->path[--ti->depth];
-  ucnum parent_size = tn_size_one_child(parent, child, child_size);
-  ucnum sib_size = parent_size - child_size;
-
-  if (2 * child_size > parent_size || 2 * sib_size > parent_size)
-    tr_rebuild(tree, tr, parent, ti->path[ti->depth - 1], parent_size);
-  else
-    tr_find_rebuild_scapegoat(tree, tr, ti, parent, parent_size);
+  if (ti->depth > 0) {
+    val parent = ti->path[--ti->depth];
+    ucnum parent_size = tn_size_one_child(parent, child, child_size);
+    ucnum sib_size = parent_size - child_size;
+
+    if (2 * child_size > parent_size || 2 * sib_size > parent_size) {
+      val grandparent = if2(ti->depth > 0, ti->path[ti->depth - 1]);
+      tr_rebuild(tree, tr, parent, grandparent, parent_size);
+    } else {
+      tr_find_rebuild_scapegoat(tree, tr, ti, parent, parent_size);
+    }
+  }
 }
 
 static void tr_insert(val tree, struct tree *tr, struct tree_iter *ti,