Subject: Re: bug#58639: 29.0.50; [noverlay] Nested overlay iteration in GC

From: Stefan Monnier <[email-masked]>
Date: Wed, 19 Oct 2022 13:29:02 -0400

> Stefan, looks like recursive calls to 'mark_buffer' are not only
> possible but common.  For this to be a problem for overlays, all it
> takes is an overlay property to somehow reference a second buffer.
> Boom, you get nested overlay iteration.

Duh, of course!

> Two easy fixes I can think of:
> a) Break the recursion while marking with a queue, rather than a stack.
>    To bound the size of the queue do this only for buffers.

Actually, the alloc.c code already has that, so it's a trivial change.

> b) Add a specialized itree iteration function for gc.  In fact,
>    properties already have one that we can copy:
>
>     extern void traverse_intervals_noorder (
>         INTERVAL,
>         void (*) (INTERVAL, void *), void *);

We even have better: just undo commit b8fbd42f0a7caa4cd9e2d50dd4e4b2101ac78acd

Or use the (100% guaranteed untested) code below.

The good thing about using `ITREE_FOREACH` in the GC is that it checks
that we're not running the GC from within an `ITREE_FOREACH` loop.

Side comment about `traverse_intervals_noorder`: I added this function
back when I played with using splay trees for `intervals.c`, which
worked well except that it occasionally created "pathologically" deep
trees, hence the need for `traverse_intervals_noorder` to keep the
recursion depth in O(log N).

> I like (b) so much I'll work on it now.

Fine by me :-)

        Stefan

diff --git a/src/alloc.c b/src/alloc.c
index 00f2991f250..555df997dfb 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6531,9 +6531,13 @@ mark_buffer (struct buffer *buffer)
   if (!BUFFER_LIVE_P (buffer))
       mark_object (BVAR (buffer, undo_list));
 
-  struct interval_node *node;
-  ITREE_FOREACH (node, buffer->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING)
-    mark_object (node->data);
+  {
+    ptrdiff_t sp = mark_stk.sp;
+    struct interval_node *node;
+    ITREE_FOREACH (node, buffer->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING)
+      mark_stack_push_value (node->data);
+    process_mark_stack (sp);
+  }
 
   /* If this is an indirect buffer, mark its base buffer.  */
   if (buffer->base_buffer &&