From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#58639: 29.0.50; [noverlay] Nested overlay iteration in GC Date: Wed, 19 Oct 2022 13:29:02 -0400 Message-ID: References: <87r0z3py0n.fsf@rfc20.org> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="17603"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: 58639@debbugs.gnu.org To: Matt Armstrong Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Wed Oct 19 19:30:18 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1olCtW-0004IM-3E for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 19 Oct 2022 19:30:18 +0200 Original-Received: from localhost ([::1]:56124 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1olCtU-0002U1-N1 for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 19 Oct 2022 13:30:16 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57404) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1olCtG-0002RY-IA for bug-gnu-emacs@gnu.org; Wed, 19 Oct 2022 13:30:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:60905) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1olCtG-0007x7-9T for bug-gnu-emacs@gnu.org; Wed, 19 Oct 2022 13:30:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1olCtG-00060M-2U for bug-gnu-emacs@gnu.org; Wed, 19 Oct 2022 13:30:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 19 Oct 2022 17:30:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58639 X-GNU-PR-Package: emacs Original-Received: via spool by 58639-submit@debbugs.gnu.org id=B58639.166620055422995 (code B ref 58639); Wed, 19 Oct 2022 17:30:01 +0000 Original-Received: (at 58639) by debbugs.gnu.org; 19 Oct 2022 17:29:14 +0000 Original-Received: from localhost ([127.0.0.1]:59981 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1olCsT-0005yp-TE for submit@debbugs.gnu.org; Wed, 19 Oct 2022 13:29:14 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:29853) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1olCsR-0005yW-Bv for 58639@debbugs.gnu.org; Wed, 19 Oct 2022 13:29:12 -0400 Original-Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 61F5D4412B0; Wed, 19 Oct 2022 13:29:05 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id D2F214412A4; Wed, 19 Oct 2022 13:29:03 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1666200543; bh=Mep2eFZ0zExcKbnkyJlqn7ZY+prc3xeRisO28YA4O/Y=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=AYwrL2IvQ6kylKsIDO3iP0Jgedh0LIv4fvpoWuDEfsecVGzBI1Lz/dWAhMu7/k5MF V+zLmpkDR/vQFf7ktbqNXKHTvOuQCoDBPRJ6+/v7S80hfDmrhL3pcsE6QKkoJYLePC U6mG7cQjYtkAhcg37lW2mPRzCGKv6jOPvRlRmgP44NC4j3PCGnoYC6WFgetCGdpZZZ xtbI+DoGhMm3289oRQy0TiPi80iQtrGzCXiIgETxaaQnjKzpFFUj10whsUkXNd8HqS zud+/dNNK28FMvqKri4o7/ccdcdeldzB3kVcpX8XtSNiWkbKWujiLxx8pY+I7CVM6Z RLmTfGDqXSSDw== Original-Received: from lechazo (lechon.iro.umontreal.ca [132.204.27.242]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id A6B39120F35; Wed, 19 Oct 2022 13:29:03 -0400 (EDT) In-Reply-To: <87r0z3py0n.fsf@rfc20.org> (Matt Armstrong's message of "Wed, 19 Oct 2022 09:40:40 -0700") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:245883 Archived-At: > 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 &&