Comment author: @edwintorok

I have measured the performance and code size impact of implementing my suggestion #2.

There is no measurable performance difference (all differences are within the standard deviation, and are <1%)

1. time make one DIR=tests/misc
   without patch: 80.91s avg, 0.04s stdev
   with patch: 80.99s avg, 0.3s stdev
   +0.07s, +0.09%
2. time make one DIR=tests/misc-unsafe:
   without patch: 74.68s avg, 0.76s stdev
   with patch: 74.98avg, 0.24s stdev
   +0.28s, +0.38%
3. time make world.opt:
   without patch: 188.73s, 1.43s stdev
   with patch: 187.661s, 1.55s stdev
   -1.12s, -0.59%

Code size for ocamlopt.opt:
without patch: 2481760
with patch: 2684640
+202880, +8.1%

I think this stack check could be eliminated when -unsafe is specified, and then you'd get back the original code size.

Measurements done on Debian unstable, x86_64, Intel(R) Core(TM)2 Quad CPU Q9550 @ 2.83GHz, 4GB RAM.

Comment author: @edwintorok

Attached the patch I used to test performance/codesize.
It is for amd64 only, I attached it only as an example.
It should be extended for other architectures, and take -unsafe into consideration.

Comment author: @damiendoligez

Using CPS is a bad idea here, you don't want to bog down the machine by filling the whole memory just because of one buggy program. Stacks are limited for a good reason.

Comment author: @ygrek

Here is another example (from caml-list, "Segmentation faults in unexpected places" by Peter Frey at Tue, 9 Aug 2011 18:16:00 -0400) :

$ cat a.ml

let stol len = (* create some bogus int list of length len *)
let head = ref [] in for i = 0 to pred len do head := i :: !head
done; !head

let () =
let limit = int_of_string (Sys.argv.(1)) in
let str_list = stol limit in
let stupid_copy = List.fold_right (fun x l -> x :: l) str_list [] in
Printf.printf"List copied with fold_right; len:%i\n" (List.length stupid_copy)

$ uname -rms
Linux 2.6.38-bpo.2-amd64 x86_64
$ ulimit -s
8192
$ ./a 261900
List copied with fold_right; len:261900
$ ./a 261900
Segmentation fault (core dumped)
$ ./a 261900
List copied with fold_right; len:261900
$ ./a 261900
Fatal error: exception Stack_overflow
$ ./a 261900
List copied with fold_right; len:261900
$ ./a 261900
List copied with fold_right; len:261900

Note the random crashing.

In this case offending C function is caml_call_gc and descendants :

Core was generated by `./a 261900'.
Program terminated with signal 11, Segmentation fault.
#0 0x000000000041f097 in caml_fl_allocate ()
(gdb) bt
#0 0x000000000041f097 in caml_fl_allocate ()
#1 0x0000000000413319 in caml_alloc_shr ()
#2 0x0000000000412538 in caml_oldify_one ()
#3 0x0000000000410d0c in caml_oldify_local_roots ()
#4 0x0000000000412750 in caml_empty_minor_heap ()
#5 0x0000000000412879 in caml_minor_collection ()
#6 0x0000000000411891 in caml_garbage_collection ()
#7 0x000000000041df16 in caml_call_gc ()
#8 0x00000000004061b4 in camlA__fun_1042 ()
#9 0x0000000000408fe2 in camlList__fold_right_1084 ()
#10 0x0000000000408fe2 in camlList__fold_right_1084 ()
#11 0x0000000000408fe2 in camlList__fold_right_1084 ()

Comment author: gerd

This seems to be difficult to solve. I think a strategy could be based on two ideas:

• Edwin's idea of guaranteeing a certain minimum of free stack. I like
  this idea. This can even be optimized - you don't need to do the stack
  check before every call to C, but only at the beginning of every recursion,
  assuming that only a let rec can grow the stack too much. Even more
  fine-grained schemes could be worked out (e.g. do the check only at every
  entry or recursion point of a function, and only if the function contains
  calls to C).

  This measure would already protect the vast majority of C stubs.

• C functions needing more stack space have to protect themselves. If the
  function is part of the Ocaml runtime, one could do stack checks at
  safe points where raising an exception does not hurt (we would need a
  global flag for marking such safe points, so that the sigsegv handler
  knows that). This would probably work well for compare, marshal, hash.
  I'm a bit wondering what's going wrong in the GC. AFAIK there are no
  unlimited recursions.

Comment author: @xavierleroy

I implemented a 90% complete fix (commits r12159 and r12160) whereas the stack "touch", checking that 4K words of stack are available and raising Stack_overflow otherwise, is performed in the asm glue between ocamlopt-generated code and the OCaml runtime system, namely in glue functions caml_c_call and caml_call_gc.

A good thing about this solution is that correct stack backtraces are generated, since caml_bottom_of_stack and caml_last_return_address are properly set up before the stack touch. Another good thing is that no extra code is generated by ocamlopt.

A weakness, compared with the original proposal, is that no stack touch is performed (yet) before calls to "noalloc" C functions, which do not go through caml_c_call. I need to run more experiments to assess the overhead of this solution, esp. when calling small functions from the math library.

The fix is currently implemented for x86 (32 and 64 bits) under Linux, BSD and MacOS X, as well as PowerPC under MacOS X. Testing on production code is most welcome.

The 4K words should be enough to run the GC and most of the OCaml runtime functions, with the notable exception of hashing, marshaling and unmarshaling, which are recursive. An iterative reimplementation of these functions can be considered but is nontrivial work.