Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> 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.

I don't see code for a mark *queue*.  I see one for a stack.  What am I
missing?  (admittedly, I was kinda lazy and just searched for the word
"queue", then paged through rather quickly, failing to spot anything...)


>> 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

Attached, with cosmetic changes to the original.

But I also added an eassert(!busy) right before `gc-post-hook', to
hopefully still retain some of the checking for the issue you were
originally trying find.


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

Looks like it would work, but I didn't like the idea of throwing all the
overlays on a stack during GC, since the count can become large.


> 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.

Ah, good point.

I suppose my patch demotes the checking in GC to just an eassert.  Let
me know what you think of that.

I was up to now thinking that the issue was that GC itself couldn't nest
with ITREE_FOREACH, but that isn't really it.  It is that we don't want
ELisp to run during ITREE_FOREACH *at all* because any ELisp might cause
a nested ITREE_FOREACH.

Is there someplace even more fundamental we can put a check for this?
Maybe Ffuncall?  We really want a "die if ELisp code runs" thing.


> 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).

Definitely a side conversation.  :-) I don't think
`traverse_intervals_noorder` caps depth at O(log N) for arbitrarily
shaped trees like splay trees.  Counter example: Construct a tree where
every left child has two children, and every right child only one
additional right child.  In this wildly unbalanced tree 1/3 of the nodes
have two children, so `traverse_intervals_noorder` will recurse 1/3 N
times and so take O(N) stack space.  But, the trick will save a lot of
stack in the common cases that splay trees can often have (long chains
of single-child nodes), so I see why you wrote it that way.