bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

classic Classic list List threaded Threaded
49 messages Options
123
Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen

Hello,

Traversing a `stream-of-directory-files' over a huge directory hierarchy
crashes my Emacs.

Here is a recipe: I have a file
"/home/micha/Treasure/today/stream-crash.el" with these contents:

#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-

(require 'stream)

(seq-doseq (_file (stream-of-directory-files
                   "/home/micha" t nil t nil
                   (lambda (file) (and (file-readable-p file) (file-regular-p file)))))
  nil)
#+end_src

Then I

micha> emacs -Q -L /home/micha/software/elpa/packages/stream\
                -l /home/micha/Treasure/today/stream-crash.el

and I get a segfault after ~ 1 minute.

This kind of crash only seems to occur when the traversed directory is
sufficiently large.


Thanks in advance,

Michael.


In GNU Emacs 26.0.91 (build 2, x86_64-pc-linux-gnu, GTK+ Version 3.22.28)
 of 2018-02-26 built on drachen
Repository revision: ea8f9fd7be138708a52aad418d09d5d4ca6b2a7e
Windowing system distributor 'The X.Org Foundation', version 11.0.11906000
System Description: Debian GNU/Linux testing (buster)




Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Eli Zaretskii
On February 27, 2018 11:22:26 AM GMT+02:00, Michael Heerdegen <[hidden email]> wrote:

>
> Hello,
>
> Traversing a `stream-of-directory-files' over a huge directory
> hierarchy
> crashes my Emacs.
>
> Here is a recipe: I have a file
> "/home/micha/Treasure/today/stream-crash.el" with these contents:
>
> #+begin_src emacs-lisp
> ;; -*- lexical-binding: t -*-
>
> (require 'stream)
>
> (seq-doseq (_file (stream-of-directory-files
>                    "/home/micha" t nil t nil
>   (lambda (file) (and (file-readable-p file) (file-regular-p file)))))
>   nil)
> #+end_src
>
> Then I
>
> micha> emacs -Q -L /home/micha/software/elpa/packages/stream\
>                 -l /home/micha/Treasure/today/stream-crash.el
>
> and I get a segfault after ~ 1 minute.
>
> This kind of crash only seems to occur when the traversed directory is
> sufficiently large.


I guess it's a stack overflow: that function recurses into subdirectories.

To avoid such problems, the function should be rewritten to work by BFS, not DFS.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
Eli Zaretskii <[hidden email]> writes:

> I guess it's a stack overflow: that function recurses into
> subdirectories.
>
> To avoid such problems, the function should be rewritten to work by
> BFS, not DFS.

Here is the backtrace I'm now able to produce.  Looks like the crash
happens in gc:

| [lots of more lines like these cut]
| #104019 0x00000000005e0526 in mark_object (arg=XIL(0x5a15413)) at alloc.c:6624
| #104020 0x00000000005dfab5 in mark_vectorlike (ptr=0x5a584e0) at alloc.c:6227
| #104021 0x00000000005e0526 in mark_object (arg=XIL(0x5bd7cf3)) at alloc.c:6624
| #104022 0x00000000005dfab5 in mark_vectorlike (ptr=0x5873a80) at alloc.c:6227
| #104023 0x00000000005e0526 in mark_object (arg=XIL(0x5bd7cb3)) at alloc.c:6624
| #104024 0x00000000006070ea in mark_specpdl (first=0x58a1348, ptr=0x58a1b90) at eval.c:3868
| #104025 0x00000000006856b2 in mark_one_thread (thread=0xcd5340 <main_thread>) at thread.c:614
| #104026 0x00000000006857c7 in mark_threads_callback (ignore=0x0) at thread.c:649
| #104027 0x00000000005dda03 in flush_stack_call_func (func=0x685781 <mark_threads_callback>, arg=0x0) at alloc.c:5220
| #104028 0x00000000006857f5 in mark_threads () at thread.c:656
| #104029 0x00000000005df2d2 in garbage_collect_1 (end=0x7fffffff63f0) at alloc.c:5997
| #104030 0x00000000005df929 in Fgarbage_collect () at alloc.c:6168
| #104031 0x000000000055746c in maybe_gc () at lisp.h:4749
| #104032 0x00000000006047cb in Ffuncall (nargs=4, args=0x7fffffff64d0) at eval.c:2751
| #104033 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f83c4), vector=XIL(0x3255bb5), maxdepth=make_number(13), args_template=make_number(128), nargs=2, args=0x7fffffff6b38) at bytecode.c:629
| #104034 0x000000000060529c in funcall_lambda (fun=XIL(0x3255c15), nargs=2, arg_vector=0x7fffffff6b38) at eval.c:2970
| #104035 0x00000000006048d4 in Ffuncall (nargs=3, args=0x7fffffff6b30) at eval.c:2771
| #104036 0x000000000060395b in Fapply (nargs=3, args=0x7fffffff6b30) at eval.c:2346
| #104037 0x0000000000604b87 in funcall_subr (subr=0xc3d7c0 <Sapply>, numargs=3, args=0x7fffffff6b30) at eval.c:2824
| #104038 0x0000000000604890 in Ffuncall (nargs=4, args=0x7fffffff6b28) at eval.c:2769
| #104039 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f83e4), vector=XIL(0x15372775), maxdepth=make_number(8), args_template=make_number(256), nargs=0, args=0x7fffffff6ff8) at bytecode.c:629
| #104040 0x000000000060529c in funcall_lambda (fun=XIL(0x153727c5), nargs=0, arg_vector=0x7fffffff6ff8) at eval.c:2970
| #104041 0x00000000006048d4 in Ffuncall (nargs=1, args=0x7fffffff6ff0) at eval.c:2771
| #104042 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42b7ad4), vector=XIL(0x930825), maxdepth=make_number(2), args_template=make_number(257), nargs=1, args=0x7fffffff7460) at bytecode.c:629
| #104043 0x000000000060529c in funcall_lambda (fun=XIL(0x3b73d75), nargs=1, arg_vector=0x7fffffff7458) at eval.c:2970
| #104044 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffff7450) at eval.c:2771
| #104045 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f82f4), vector=XIL(0x3255aa5), maxdepth=make_number(3), args_template=make_number(257), nargs=1, args=0x7fffffff78e0) at bytecode.c:629
| #104046 0x000000000060529c in funcall_lambda (fun=XIL(0x3255ab5), nargs=1, arg_vector=0x7fffffff78d8) at eval.c:2970
| #104047 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffff78d0) at eval.c:2771
| #104048 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f83e4), vector=XIL(0x153727f5), maxdepth=make_number(8), args_template=make_number(256), nargs=0, args=0x7fffffff7da8) at bytecode.c:629
| #104049 0x000000000060529c in funcall_lambda (fun=XIL(0x15372845), nargs=0, arg_vector=0x7fffffff7da8) at eval.c:2970
| #104050 0x00000000006048d4 in Ffuncall (nargs=1, args=0x7fffffff7da0) at eval.c:2771
| #104051 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42b7ad4), vector=XIL(0x930825), maxdepth=make_number(2), args_template=make_number(257), nargs=1, args=0x7fffffff8210) at bytecode.c:629
| #104052 0x000000000060529c in funcall_lambda (fun=XIL(0x3b73d75), nargs=1, arg_vector=0x7fffffff8208) at eval.c:2970
| #104053 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffff8200) at eval.c:2771
| #104054 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f82f4), vector=XIL(0x3255aa5), maxdepth=make_number(3), args_template=make_number(257), nargs=1, args=0x7fffffff8690) at bytecode.c:629
| #104055 0x000000000060529c in funcall_lambda (fun=XIL(0x3255ab5), nargs=1, arg_vector=0x7fffffff8688) at eval.c:2970
| #104056 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffff8680) at eval.c:2771
| #104057 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f83e4), vector=XIL(0x15372875), maxdepth=make_number(8), args_template=make_number(256), nargs=0, args=0x7fffffff8b58) at bytecode.c:629
| #104058 0x000000000060529c in funcall_lambda (fun=XIL(0x153728c5), nargs=0, arg_vector=0x7fffffff8b58) at eval.c:2970
| #104059 0x00000000006048d4 in Ffuncall (nargs=1, args=0x7fffffff8b50) at eval.c:2771
| #104060 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42b7ad4), vector=XIL(0x930825), maxdepth=make_number(2), args_template=make_number(257), nargs=1, args=0x7fffffff8fc0) at bytecode.c:629
| #104061 0x000000000060529c in funcall_lambda (fun=XIL(0x3b73d75), nargs=1, arg_vector=0x7fffffff8fb8) at eval.c:2970
| #104062 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffff8fb0) at eval.c:2771
| #104063 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f82f4), vector=XIL(0x3255aa5), maxdepth=make_number(3), args_template=make_number(257), nargs=1, args=0x7fffffff9440) at bytecode.c:629
| #104064 0x000000000060529c in funcall_lambda (fun=XIL(0x3255ab5), nargs=1, arg_vector=0x7fffffff9438) at eval.c:2970
| #104065 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffff9430) at eval.c:2771
| #104066 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f83e4), vector=XIL(0x153728f5), maxdepth=make_number(8), args_template=make_number(256), nargs=0, args=0x7fffffff9908) at bytecode.c:629
| #104067 0x000000000060529c in funcall_lambda (fun=XIL(0x15372945), nargs=0, arg_vector=0x7fffffff9908) at eval.c:2970
| #104068 0x00000000006048d4 in Ffuncall (nargs=1, args=0x7fffffff9900) at eval.c:2771
| #104069 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42b7ad4), vector=XIL(0x930825), maxdepth=make_number(2), args_template=make_number(257), nargs=1, args=0x7fffffff9d70) at bytecode.c:629
| #104070 0x000000000060529c in funcall_lambda (fun=XIL(0x3b73d75), nargs=1, arg_vector=0x7fffffff9d68) at eval.c:2970
| #104071 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffff9d60) at eval.c:2771
| #104072 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f82f4), vector=XIL(0x3255aa5), maxdepth=make_number(3), args_template=make_number(257), nargs=1, args=0x7fffffffa1e8) at bytecode.c:629
| #104073 0x000000000060529c in funcall_lambda (fun=XIL(0x3255ab5), nargs=1, arg_vector=0x7fffffffa1e0) at eval.c:2970
| #104074 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffffa1d8) at eval.c:2771
| #104075 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f8c64), vector=XIL(0x153729a5), maxdepth=make_number(7), args_template=make_number(256), nargs=0, args=0x7fffffffa6a8) at bytecode.c:629
| #104076 0x000000000060529c in funcall_lambda (fun=XIL(0x153729f5), nargs=0, arg_vector=0x7fffffffa6a8) at eval.c:2970
| #104077 0x00000000006048d4 in Ffuncall (nargs=1, args=0x7fffffffa6a0) at eval.c:2771
| #104078 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42b7ad4), vector=XIL(0x930825), maxdepth=make_number(2), args_template=make_number(257), nargs=1, args=0x7fffffffab10) at bytecode.c:629
| #104079 0x000000000060529c in funcall_lambda (fun=XIL(0x3b73d75), nargs=1, arg_vector=0x7fffffffab08) at eval.c:2970
| #104080 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffffab00) at eval.c:2771
| #104081 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f82f4), vector=XIL(0x3255aa5), maxdepth=make_number(3), args_template=make_number(257), nargs=1, args=0x7fffffffaf88) at bytecode.c:629
| #104082 0x000000000060529c in funcall_lambda (fun=XIL(0x3255ab5), nargs=1, arg_vector=0x7fffffffaf80) at eval.c:2970
| #104083 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffffaf78) at eval.c:2771
| #104084 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42f8c04), vector=XIL(0x331ede5), maxdepth=make_number(5), args_template=make_number(514), nargs=2, args=0x7fffffffb5d0) at bytecode.c:629
| #104085 0x000000000060529c in funcall_lambda (fun=XIL(0x331ee05), nargs=2, arg_vector=0x7fffffffb5c0) at eval.c:2970
| #104086 0x00000000006048d4 in Ffuncall (nargs=3, args=0x7fffffffb5b8) at eval.c:2771
| #104087 0x000000000060390d in Fapply (nargs=4, args=0x7fffffffb5b8) at eval.c:2342
| #104088 0x0000000000604b87 in funcall_subr (subr=0xc3d7c0 <Sapply>, numargs=4, args=0x7fffffffb5b8) at eval.c:2824
| #104089 0x0000000000604890 in Ffuncall (nargs=5, args=0x7fffffffb5b0) at eval.c:2769
| #104090 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x42fb574), vector=XIL(0x425f285), maxdepth=make_number(15), args_template=make_number(642), nargs=2, args=0x7fffffffba40) at bytecode.c:629
| #104091 0x000000000060529c in funcall_lambda (fun=XIL(0x425f305), nargs=2, arg_vector=0x7fffffffba30) at eval.c:2970
| #104092 0x000000000060500d in apply_lambda (fun=XIL(0x425f305), args=XIL(0x5bd89c3), count=30) at eval.c:2906
| #104093 0x0000000000603602 in eval_sub (form=XIL(0x5bd89d3)) at eval.c:2279
| #104094 0x0000000000632c69 in readevalloop_eager_expand_eval (val=XIL(0x5bd8a73), macroexpand=XIL(0xda5d0)) at lread.c:1850
| #104095 0x00000000006335f0 in readevalloop (readcharfun=XIL(0x5b75ce5), infile0=0x0, sourcename=XIL(0x55c2e14), printflag=false, unibyte=XIL(0), readfun=XIL(0), start=XIL(0), end=XIL(0)) at lread.c:2036
| #104096 0x0000000000633a0a in Feval_buffer (buffer=XIL(0), printflag=XIL(0), filename=XIL(0x56ea3c4), unibyte=XIL(0), do_allow_print=XIL(0)) at lread.c:2103
| #104097 0x0000000000604d25 in funcall_subr (subr=0xc40240 <Seval_buffer>, numargs=0, args=0x7fffffffbfa0) at eval.c:2856
| #104098 0x0000000000604890 in Ffuncall (nargs=1, args=0x7fffffffbf98) at eval.c:2769
| #104099 0x00000000005fc8f7 in Ffuncall_interactively (nargs=1, args=0x7fffffffbf98) at callint.c:252
| #104100 0x0000000000604b87 in funcall_subr (subr=0xc3cfc0 <Sfuncall_interactively>, numargs=1, args=0x7fffffffbf98) at eval.c:2824
| #104101 0x0000000000604890 in Ffuncall (nargs=2, args=0x7fffffffbf90) at eval.c:2769
| #104102 0x00000000005fec50 in Fcall_interactively (function=XIL(0xad320), record_flag=XIL(0xaad0), keys=XIL(0x5a55745)) at callint.c:854
| #104103 0x0000000000604cac in funcall_subr (subr=0xc3d000 <Scall_interactively>, numargs=3, args=0x7fffffffc300) at eval.c:2849
| #104104 0x0000000000604890 in Ffuncall (nargs=4, args=0x7fffffffc2f8) at eval.c:2769
| #104105 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x9f4bec), vector=XIL(0x9f4c0d), maxdepth=make_number(13), args_template=make_number(1025), nargs=2, args=0x7fffffffc868) at bytecode.c:629
| #104106 0x000000000060529c in funcall_lambda (fun=XIL(0x9f4bbd), nargs=2, arg_vector=0x7fffffffc858) at eval.c:2970
| #104107 0x00000000006048d4 in Ffuncall (nargs=3, args=0x7fffffffc850) at eval.c:2771
| #104108 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x9f489c), vector=XIL(0x9f48bd), maxdepth=make_number(15), args_template=make_number(769), nargs=3, args=0x7fffffffce00) at bytecode.c:629
| #104109 0x000000000060529c in funcall_lambda (fun=XIL(0x9f485d), nargs=3, arg_vector=0x7fffffffcde8) at eval.c:2970
| #104110 0x00000000006048d4 in Ffuncall (nargs=4, args=0x7fffffffcde0) at eval.c:2771
| #104111 0x0000000000603cdb in Fapply (nargs=2, args=0x7fffffffcfc0) at eval.c:2389
| #104112 0x0000000000604b87 in funcall_subr (subr=0xc3d7c0 <Sapply>, numargs=2, args=0x7fffffffcfc0) at eval.c:2824
| #104113 0x0000000000604890 in Ffuncall (nargs=3, args=0x7fffffffcfb8) at eval.c:2769
| #104114 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x505da94), vector=XIL(0x5044095), maxdepth=make_number(3), args_template=XIL(0), nargs=0, args=0x0) at bytecode.c:629
| #104115 0x0000000000605615 in funcall_lambda (fun=XIL(0x50c3185), nargs=5, arg_vector=0x5044095) at eval.c:3052
| #104116 0x00000000006048d4 in Ffuncall (nargs=6, args=0x7fffffffd450) at eval.c:2771
| #104117 0x0000000000603cdb in Fapply (nargs=3, args=0x7fffffffd648) at eval.c:2389
| #104118 0x0000000000604b87 in funcall_subr (subr=0xc3d7c0 <Sapply>, numargs=3, args=0x7fffffffd648) at eval.c:2824
| #104119 0x0000000000604890 in Ffuncall (nargs=4, args=0x7fffffffd640) at eval.c:2769
| #104120 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x14402c4), vector=XIL(0x50441c5), maxdepth=make_number(5), args_template=make_number(128), nargs=4, args=0x7fffffffdbf0) at bytecode.c:629
| #104121 0x000000000060529c in funcall_lambda (fun=XIL(0x50441f5), nargs=4, arg_vector=0x7fffffffdbf0) at eval.c:2970
| #104122 0x00000000006048d4 in Ffuncall (nargs=5, args=0x7fffffffdbe8) at eval.c:2771
| #104123 0x00000000005fc8f7 in Ffuncall_interactively (nargs=5, args=0x7fffffffdbe8) at callint.c:252
| #104124 0x0000000000604b87 in funcall_subr (subr=0xc3cfc0 <Sfuncall_interactively>, numargs=5, args=0x7fffffffdbe8) at eval.c:2824
| #104125 0x0000000000604890 in Ffuncall (nargs=6, args=0x7fffffffdbe0) at eval.c:2769
| #104126 0x0000000000603cdb in Fapply (nargs=3, args=0x7fffffffdd90) at eval.c:2389
| #104127 0x00000000005fcd7d in Fcall_interactively (function=XIL(0xda3c0), record_flag=XIL(0), keys=XIL(0x5a3e0a5)) at callint.c:389
| #104128 0x0000000000604cac in funcall_subr (subr=0xc3d000 <Scall_interactively>, numargs=3, args=0x7fffffffdfe0) at eval.c:2849
| #104129 0x0000000000604890 in Ffuncall (nargs=4, args=0x7fffffffdfd8) at eval.c:2769
| #104130 0x000000000064cc41 in exec_byte_code (bytestr=XIL(0x9f4bec), vector=XIL(0x9f4c0d), maxdepth=make_number(13), args_template=make_number(1025), nargs=1, args=0x7fffffffe520) at bytecode.c:629
| #104131 0x000000000060529c in funcall_lambda (fun=XIL(0x9f4bbd), nargs=1, arg_vector=0x7fffffffe518) at eval.c:2970
| #104132 0x00000000006048d4 in Ffuncall (nargs=2, args=0x7fffffffe510) at eval.c:2771
| #104133 0x00000000006042a0 in call1 (fn=XIL(0x3f00), arg1=XIL(0xda3c0)) at eval.c:2620
| #104134 0x000000000055ec02 in command_loop_1 () at keyboard.c:1482
| #104135 0x00000000006013b2 in internal_condition_case (bfun=0x55e45e <command_loop_1>, handlers=XIL(0x5250), hfun=0x55dc1d <cmd_error>) at eval.c:1332
| #104136 0x000000000055e151 in command_loop_2 (ignore=XIL(0)) at keyboard.c:1110
| #104137 0x0000000000600c94 in internal_catch (tag=XIL(0xc6f0), func=0x55e124 <command_loop_2>, arg=XIL(0)) at eval.c:1097
| #104138 0x000000000055e0ef in command_loop () at keyboard.c:1089
| #104139 0x000000000055d7ef in recursive_edit_1 () at keyboard.c:695
| #104140 0x000000000055d970 in Frecursive_edit () at keyboard.c:766
| #104141 0x000000000055b5f0 in main (argc=1, argv=0x7fffffffe9f8) at emacs.c:1713
| Cannot access memory at address 0x7fffff66ff4f



Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

> Here is the backtrace I'm now able to produce.  Looks like the crash
> happens in gc.

Here is a much simpler example that crashes as well:

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


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Eli Zaretskii
In reply to this post by Michael Heerdegen
> From: Michael Heerdegen <[hidden email]>
> Cc: [hidden email], [hidden email]
> Date: Tue, 27 Feb 2018 12:39:47 +0100
>
> Eli Zaretskii <[hidden email]> writes:
>
> > I guess it's a stack overflow: that function recurses into
> > subdirectories.
> >
> > To avoid such problems, the function should be rewritten to work by
> > BFS, not DFS.
>
> Here is the backtrace I'm now able to produce.  Looks like the crash
> happens in gc:

GC is deeply-recursive, and you have exacerbated that by using up a
lot of stack.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Eli Zaretskii
In reply to this post by Michael Heerdegen
> From: Michael Heerdegen <[hidden email]>
> Cc: [hidden email],  [hidden email]
> 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?



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Noam Postavsky
Eli Zaretskii <[hidden email]> writes:

>> From: Michael Heerdegen <[hidden email]>
>> Cc: [hidden email],  [hidden email]
>> 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.

Doesn't look recursive to me, it expands to a call to seq-do, which uses
a simple loop.

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

I don't have a quick answer for the general case, but I think it's a bug
in stream.el that it's creating such large structures in the first
place.  As far as I understand it, the point of streams is to handle
long lists by encoding them as

    (FIRST-VALUE . FUNCTION-TO-PRODUCE-REST-OF-LIST)
 
so as to avoid allocating large amounts of memory.  Is there an easy way
to find out what the large structures are, and where they are coming
from?



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
Noam Postavsky <[hidden email]> writes:

> >> #+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.
>
> Doesn't look recursive to me, it expands to a call to seq-do, which uses
> a simple loop.

I was imprecise, I meant that the streams are defined recursively (most
of the time).  Though, it's a delayed type of recursion.  Anyway, I
think that this doesn't matter here.

> > Does anyone has a reasonable idea for avoiding the crash in such
> > programs?
>
> I don't have a quick answer for the general case, but I think it's a bug
> in stream.el that it's creating such large structures in the first
> place.  As far as I understand it, the point of streams is to handle
> long lists by encoding them as
>
>     (FIRST-VALUE . FUNCTION-TO-PRODUCE-REST-OF-LIST)

Yes, that's exactly how it's implemented.  When requesting more elements
from the stream, that becomes

      (FIRST-VALUE .
        (SECOND-VALUE . FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST))

When we loop over the string, the cons whose car is the FIRST-VALUE,
let's call it cons1, is immediately thrown away, and we continue with

      (SECOND-VALUE . FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST)

etc.

AFAIU the problem is that the cons1 still exists in memory until garbage
collection kicks in.  When that happens, the cons1 points to a largely
recursive cons structure, though this structure is never referenced from
Lisp in this form.
 
> so as to avoid allocating large amounts of memory.  Is there an easy way
> to find out what the large structures are, and where they are coming
> from?

I think I've answered that.  At least, I think so.  What I don't
understand is that when I force the `seq-doseq' to call
`garbace-collect' explicitly every 1000 cycles, or so, it doesn't help:
the crash still happens after generating ~ 70 000 elements, or some
more, but I can't avoid the crash, no matter how often I call gc.  So
I'm not sure whether these long lists are the problem or something else.
The FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST looks harmless when I print
it, even after thousands of iterations, so I would not understand why
that could be problematic.  streams.el implements things in a way that
these rest functions are not deeply nested lambdas.


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
In reply to this post by Eli Zaretskii
Hello,

I had written that

> > (seq-doseq (_ (stream-range 1 1000000)) nil)

crashes.  CC'ing Nicolas, the author of stream.el.

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

I would appreciate any effort to fix that, because it seems that
currently streams are broken by design, and there is no way to fix that
from the Lisp implementation.

Yes, we could implement iterators instead of streams - that's what we
get when we avoid the consing.  But it's something different and not
always an alternative, depending on what you want to do.


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Nicolas Petton-2
Michael Heerdegen <[hidden email]> writes:

> Hello,

Hi,

> I had written that
>
>> > (seq-doseq (_ (stream-range 1 1000000)) nil)
>
> crashes.  CC'ing Nicolas, the author of stream.el.

Thanks, I'll look into it.

Cheers,
Nico

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Eli Zaretskii
In reply to this post by Michael Heerdegen
> From: Michael Heerdegen <[hidden email]>
> Cc: Eli Zaretskii <[hidden email]>,  [hidden email]
> Date: Wed, 28 Feb 2018 11:58:49 +0100
>
> >     (FIRST-VALUE . FUNCTION-TO-PRODUCE-REST-OF-LIST)
>
> Yes, that's exactly how it's implemented.  When requesting more elements
> from the stream, that becomes
>
>       (FIRST-VALUE .
>         (SECOND-VALUE . FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST))
>
> When we loop over the string, the cons whose car is the FIRST-VALUE,
> let's call it cons1, is immediately thrown away, and we continue with
>
>       (SECOND-VALUE . FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST)
>
> etc.

How do you see that the car is immediately thrown away?

> AFAIU the problem is that the cons1 still exists in memory until garbage
> collection kicks in.  When that happens, the cons1 points to a largely
> recursive cons structure, though this structure is never referenced from
> Lisp in this form.

What is "cons1" in this context?



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
Eli Zaretskii <[hidden email]> writes:

> How do you see that the car is immediately thrown away?

After expansion and dispatch, this is what gets executed:

#+begin_src emacs-lisp
(let ((stream (stream-range 1 1000000)))
  (while (not (stream-empty-p stream))
    (funcall #'ignore (stream-first stream))
    (setq stream (stream-rest stream))))
#+end_src

Creating an element and throwing away the outermost cons alternate.

> > AFAIU the problem is that the cons1 still exists in memory until
> > garbage collection kicks in.  When that happens, the cons1 points to
> > a largely recursive cons structure, though this structure is never
> > referenced from Lisp in this form.

> What is "cons1" in this context?

I said it some lines above: I defined it as name of the "first cons",
i.e. the original stream.  The return value of `stream-range' in the
above example.


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Eli Zaretskii
> From: Michael Heerdegen <[hidden email]>
> Cc: [hidden email],  [hidden email]
> Date: Wed, 28 Feb 2018 17:20:53 +0100
>
> Eli Zaretskii <[hidden email]> writes:
>
> > How do you see that the car is immediately thrown away?
>
> After expansion and dispatch, this is what gets executed:
>
> #+begin_src emacs-lisp
> (let ((stream (stream-range 1 1000000)))
>   (while (not (stream-empty-p stream))
>     (funcall #'ignore (stream-first stream))
>     (setq stream (stream-rest stream))))
> #+end_src
>
> Creating an element and throwing away the outermost cons alternate.

I don't think it's thrown away from the POV of GC.  But you can easily
see what is going on if you trace the GC on the C level.  You should
be able to see which object causes recursion in mark_object.  I didn't
look long enough, but what I did see looks very much like the entire
unwound stream.




Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
Eli Zaretskii <[hidden email]> writes:

> I don't think it's thrown away from the POV of GC.  But you can easily
> see what is going on if you trace the GC on the C level.  You should
> be able to see which object causes recursion in mark_object.  I didn't
> look long enough, but what I did see looks very much like the entire
> unwound stream.

I have an idea what could be going on.  In the stream-range example,
this is how the stream is build:

#+begin_src emacs-lisp
(list stream--identifier
      (let
          (forced val)
        (lambda
          (&optional check)
          (if
              check
              forced
            (unless
                forced
              (setf
               val
               (progn
                 (cons
                  start
                  (stream-range (+ start step) end step))))
              (setf forced t))
            val))))
#+end_src

The inner `stream-range' call results in a closure, and I guess that
this closure includes a reference to the outside VAL, which is the
stream from one step back (though there isn't a lexical reference to the
variable...does that make sense?)

So there could be a chain of references via closure variables back to
the first cons.


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Daniel Colascione-5
In reply to this post by Eli Zaretskii
On 02/27/2018 10:08 AM, Eli Zaretskii wrote:

>> From: Michael Heerdegen <[hidden email]>
>> Cc: [hidden email],  [hidden email]
>> 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.




Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

> The inner `stream-range' call results in a closure, and I guess that
> this closure includes a reference to the outside VAL, which is the
> stream from one step back (though there isn't a lexical reference to the
> variable...does that make sense?)

This is probably only a part of the puzzle.  Some examples:

test1.el: This is more or less the `stream-range' example reimplemented
without dependencies so that it works in emacs -Q:

#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-

(defun my-range (start)
  (let (forced val)
    (lambda ()
      (unless forced
        (setq val (cons start (my-range (1+ start)))
              forced t))
      val)))

(defun my-test ()
  (let ((range-object (my-range 1))
        current-cons)
    (while (< (car (setq current-cons (funcall range-object))) (* 1000 1000))
      (message "%d" (car current-cons))
      (setq range-object (cdr current-cons)))))

(my-test)
#+end_src

Loading this file test1.el crashes Emacs - but if you compile it,
loading the compiled file doesn't crash.  This is what I expected from
my previous thoughts, because only the uncompiled closures include a
reference to the outer VALs.


test2.el:

#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-

(require 'stream)

(let ((stream (stream-range 1 1000000)))
  (stream-flush stream))
#+end_src

This traverses the whole stream ignoring the elements.  Loading this
file crashes Emacs, no matter if compiled or not.  I'm surprised it
doesn't work even when compiled.


test3.el:

#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-

(require 'stream)

(let ((stream (stream-range 1 1000000)))
  (while (not (stream-empty-p stream))
    (cl-callf stream-rest stream)))
#+end_src

This is semantically exactly like test2.el, only the call to
`stream-flush' has been replaced by literally writing out the
definition.  Nonetheless, the compiled file suddenly doesn't crash Emacs
when loaded.  Loading the uncompiled file test3.el still crashes.

Seems that whether we get a crash or not depends on details in the
implementation of lexical-binding.

Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Eli Zaretskii
> From: Michael Heerdegen <[hidden email]>
> Cc: [hidden email],  [hidden email]
> Date: Thu, 01 Mar 2018 12:25:43 +0100
>
> Seems that whether we get a crash or not depends on details in the
> implementation of lexical-binding.

Byte compilation doesn't just produce byte code, it also changes the
code into an equivalent one, but "equivalence" in this context doesn't
include side effects like stack usage.  As an extreme example,
consider a tail-recursive program that the byte compiler converts (or
at least might convert theoretically) into a loop.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Noam Postavsky
In reply to this post by Daniel Colascione-5
On Thu, Mar 1, 2018 at 5:44 AM, Daniel Colascione <[hidden email]> wrote:

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

Agreed, but could you please open a new thread for it? AFAICT, this
bug thread is about streams.el functions producing structures
proportional in size to the length of the entire stream, which is a
bug in itself, regardless of whether or not the GC can handle the
result.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Michael Heerdegen
Noam Postavsky <[hidden email]> writes:

> Agreed, but could you please open a new thread for it? AFAICT, this
> bug thread is about streams.el functions producing structures
> proportional in size to the length of the entire stream, which is a
> bug in itself, regardless of whether or not the GC can handle the
> result.

No, it is a feature: we want streams to produce these structures,
streams are delayed lists, not just iterators.  Lists are also
potentially unlimited nested conses, and that's not a bug.  Streams are
the same realized with delayed conses.


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

Noam Postavsky
On Thu, Mar 1, 2018 at 11:54 AM, Michael Heerdegen
<[hidden email]> wrote:

> Noam Postavsky <[hidden email]> writes:
>
>> Agreed, but could you please open a new thread for it? AFAICT, this
>> bug thread is about streams.el functions producing structures
>> proportional in size to the length of the entire stream, which is a
>> bug in itself, regardless of whether or not the GC can handle the
>> result.
>
> No, it is a feature: we want streams to produce these structures,
> streams are delayed lists, not just iterators.  Lists are also
> potentially unlimited nested conses, and that's not a bug.  Streams are
> the same realized with delayed conses.

Maybe I've misunderstood, but is it not the case that iterating over
(stream-range 1 n) should require only a constant amount of memory,
regardless of the value of n?



123