From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Daniel Colascione Newsgroups: gmane.emacs.bugs Subject: bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files' Date: Thu, 1 Mar 2018 02:44:54 -0800 Message-ID: <5d5ccb32-434a-cda9-67c4-c60abeb450df@dancol.org> References: <87inaiss6l.fsf@web.de> <6FCF6ACA-4F29-4B6B-BE9D-D7130C6E9495@gnu.org> <87fu5moe4c.fsf@web.de> <877eqyocro.fsf@web.de> <83zi3uz4nb.fsf@gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: blaine.gmane.org 1519901053 21305 195.159.176.226 (1 Mar 2018 10:44:13 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 1 Mar 2018 10:44:13 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 Cc: 30626@debbugs.gnu.org To: Eli Zaretskii , Michael Heerdegen Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Thu Mar 01 11:44:09 2018 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1erLh2-0004ut-8N for geb-bug-gnu-emacs@m.gmane.org; Thu, 01 Mar 2018 11:44:08 +0100 Original-Received: from localhost ([::1]:55490 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1erLj4-0003BY-4F for geb-bug-gnu-emacs@m.gmane.org; Thu, 01 Mar 2018 05:46:14 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:52296) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1erLix-0003B8-3h for bug-gnu-emacs@gnu.org; Thu, 01 Mar 2018 05:46:08 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1erLis-0005gy-3m for bug-gnu-emacs@gnu.org; Thu, 01 Mar 2018 05:46:07 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:58591) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1erLir-0005gV-VU for bug-gnu-emacs@gnu.org; Thu, 01 Mar 2018 05:46:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1erLir-000072-Iz for bug-gnu-emacs@gnu.org; Thu, 01 Mar 2018 05:46:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Daniel Colascione Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 01 Mar 2018 10:46:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 30626 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 30626-submit@debbugs.gnu.org id=B30626.1519901106369 (code B ref 30626); Thu, 01 Mar 2018 10:46:01 +0000 Original-Received: (at 30626) by debbugs.gnu.org; 1 Mar 2018 10:45:06 +0000 Original-Received: from localhost ([127.0.0.1]:38255 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1erLhw-00005r-T4 for submit@debbugs.gnu.org; Thu, 01 Mar 2018 05:45:05 -0500 Original-Received: from dancol.org ([96.126.100.184]:50764) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1erLhu-00005j-Sg for 30626@debbugs.gnu.org; Thu, 01 Mar 2018 05:45:03 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=dancol.org; s=x; h=Content-Transfer-Encoding:Content-Type:In-Reply-To:MIME-Version:Date:Message-ID:From:References:Cc:To:Subject; bh=47QOjUHy9W4RZVnnFpob9g/wL0IisNhoraMPdnKwYx8=; b=EKGrQ9UcEqHk9Pr+BMTmoF9v/n+/nqogSBWcd186s4GxOMGPZugy0ajJsTQQ+s8D2D2p9pEHWrZ/PT6uMInuzzrh4ydbTnQAsoe5rbu32zLi8QIyXspqezqB3//dY76JiDqhaLjJiuLb4LCfE2p+0ntEYh8LPHMSjQwEqNs3mzYTisP4uHK4dLrcuUVTA9WweHL+WGBa9tVW5BiceBh4ON5MsElyfx6KoiT5byfnpwewg4I6UFjwpk7sVOyg1POGtGwRHZvpv+/djkEaNjkuBR704RTZq3kqZ34mVFfpbMprEgqq5tD3xEHsIEJ8Zk/RcfBH0QafHaEmjpfCXLRjlw==; Original-Received: from [172.92.145.124] (helo=[192.168.86.27]) by dancol.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) (envelope-from ) id 1erLht-00015c-7W; Thu, 01 Mar 2018 02:45:01 -0800 In-Reply-To: <83zi3uz4nb.fsf@gnu.org> Content-Language: en-US X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 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.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:143779 Archived-At: On 02/27/2018 10:08 AM, Eli Zaretskii wrote: >> From: Michael Heerdegen >> Cc: bug-gnu-emacs@gnu.org, 30626@debbugs.gnu.org >> Date: Tue, 27 Feb 2018 13:08:59 +0100 >> >> #+begin_src emacs-lisp >> (seq-doseq (_ (stream-range 1 1000000)) nil) >> #+end_src >> >> Note that this is executed as a loop due how to streams are implemented, >> although the definition of `seq-doseq' looks recursive. But it seems >> that gc has a problem with the large number of conses created when >> processing that. > > What can we do instead in such cases? Stack-overflow protection > cannot work in GC, so you are shooting yourself in the foot by > creating such large recursive structures. By the time we get to GC, > where the problem will happen, it's too late, because the memory was > already allocated. > > Does anyone has a reasonable idea for avoiding the crash in such > programs? We need to fix GC being deeply recursive once and for all. Tweaking stack sizes on various platforms and trying to spot-fix GC for the occasional deeply recursive structure is annoying. Here's my proposal: Turn garbage_collect_1 into a queue-draining loop, initializing the object queue with the GC roots before draining it. We'll make mark_object put an object on this queue, turning the existing mark_object code into a mark_queued_object function. garbage_collect_1 will just call mark_queued_object in a loop; mark_queued_object can call mark_object, but since mark_object just enqueues an object and doesn't recurse, we can't exhaust the stack with deep object graphs. (We'll repurpose the mark bit to mean that the object is on the to-mark queue; by the time we fully drain the queue, just before we sweep, the mark bit will have the same meaning it does now.) We can't allocate memory to hold the queue during GC, so we'll have to pre-allocate it. We can implement the queue as a list of queue blocks, where each queue block is an array of 16k or so Lisp_Objects. During allocation, we'll just make sure we have one Lisp_Object queue-block slot for every non-self-representing Lisp object we allocate. Since we know that we'll have enough queue blocks for the worst GC case, we can have mark_object pull queue blocks from a free list, aborting if for some reason it ever runs out of queue blocks. (The previous paragraph guarantees we won't.) garbage_collect_1 will churn through these heap blocks and place each back on the free list after it's called mark_queued_object on every Lisp_Object in the queue block. In this way, in non-pathological cases of GC, we'll end up using the same few queue blocks over and over. That's a nice optimization, because we can MADV_DONTNEED unused queue blocks so the OS doesn't actually have to remember their contents. In this way, I think we can make the current GC model recursion-proof without drastically changing how we allocate Lisp objects. The additional memory requirements should be modest: it's basically one Lisp_Object per Lisp object allocated. The naive version of this scheme needs about 4.6MB of overhead on my current 20MB Emacs heap, but it should be possible to reduce the overhead significantly by taking advantage of the block allocation we do for conses and other types --- we can put whole blocks on the queue instead of pointers to individual block parts, so we can get away with a much smaller queue. Under this approach, the reserved-queue-block scheme would impose an overhead of somewhere around 1MB on the same heap. This amount of overhead seems reasonable. We may end up actually using less memory that we would for recursive mark_object stack invocation.