The unloadable runtime proposal

## Problem description

Currently (as of the latest trunk revision) the runtime cannot be unloaded in a clean way — that is, without leaking resources. Once `caml_startup` is called, and during the program execution, the runtime performs allocations using the `malloc` implementation provided by the C runtime. Allocated with `malloc` are: the stack, the heap sections, code fragments, custom operations, various buffers and tables, none of which is freed explicitly by the runtime.

If the OCaml program is compiled into a standalone executable, then nothing is wrong with those allocations, since the operating system will handle the cleanup once the process exits. However, in case when the program is compiled as a shared library, which is to be loaded and unloaded by a foreign application (e.g. written in C++), unloading the library results in memory leaks. Moreover, heap values are not finalised, and the dependent shared libraries (those loaded by Dynlink) are never freed.

In my particular case, the shared library (an OCaml program combined with the runtime) is loaded and unloaded repeatedly by a proprietary software system written in Delphi, which knows nothing about OCaml, but which exposes a plugin API, and which expects each plugin to be responsible for cleaning up its resources on unloading. Given that the OCaml's runtime does not support unloading properly, each such "unloading" results in a several-megabyte memory leak, as well as the leakage of all the dependent DLLs' handles, thus disallowing to hot-swap the libraries without restarting the process (on Windows).

In contrast, no such problems arise with the nice and friendly runtime of the Glasgow Haskell Compiler. Its glorious [API](http://www.haskell.org/ghc/docs/latest/html/users_guide/ffi-ghc.html#using-own-main) provides not only the `hs_init` function (a counterpart to `caml_startup`), but also `hs_exit`, which can be used to shut down the runtime properly. There can be multiple calls to `hs_init`, and each can be matched with an independent call to `hs_exit`. Lovely! So, if your business requirements involve cleanly unloading a shared library, then OCaml eats dust, while Haskell delivers. Shame on us!

It is thus proposed to add a similar facility to OCaml, by implementing the `caml_shutdown` function.

The proposal is possibly related to [#PR385](http://caml.inria.fr/mantis/view.php?id=385), which is reported in French and is 13 years old. [Googling](https://www.google.ru/search?q=caml_cleanup) for `caml_cleanup` reveals that other people have previously expressed interest in such a facility, which means it's not only a personal whim of the proposal's author, but something that can make OCaml more useful to a considerable number of users.


## Proposed solution

Attached to the proposal is a working implementation of the author's vision of how should an unloadable runtime be implemented. Implementation details follow.


### Dealing with allocations in the C heap

In order to avoid memory leaks, each outstanding call to `malloc` must be paired with a corresponding call to `free` on shutdown. An ugly way to solve the problem involves locating all points of unresolved allocation inside the runtime's source code, figuring out how to free the memory correctly in each particular case, meticulously writing a lot of stupid boilerplate code, and eventually polluting the namespace with numerous "cleanup" functions — not nice at all.

A proper way involves using a memory manager.

Instead of allocating memory directly in the C heap, we can maintain a memory pool, enabling us to easily free all the heap-allocated memory once we've decided to shut the runtime down. If we only cared about supporting Windows, then we could use [HeapCreate](http://msdn.microsoft.com/en-us/library/windows/desktop/aa366599%28v=vs.85%29.aspx) and associated machinery. Unfortunately, there is no standard alternative to HeapCreate on Unix, so, for maximum portability, the best solution would be to bundle a simple memory manager with the runtime itself.

In the proposed implementation, the memory management layer is built on top of [Halloc](http://swapped.cc/halloc), which is a thin wrapper around `malloc` and `free` that allows to specify dependencies between memory blocks, by storing additional information inside each block's header.

Thankfully, most operations with the C heap are already wrapped in `caml_stat_*` functions, so it was no big deal to change the implementation. Someplace in the runtime, there were direct calls to `malloc`, `calloc`, `realloc`, `strdup` and `free`, which had to be replaced with calls to `caml_stat_*`. The `caml_stat_*_noexc` functions were added for compatibility with `malloc` and friends, which never throw an OCaml exception. Perhaps we should get rid of the exceptions altogether in such situations (allocation errors) and simply kill the process with `caml_fatal_error`? This is [how it's done](https://github.com/ghc/ghc/blob/master/rts/RtsUtils.c) in GHC, and I don't see a problem with this approach.

Maintaining the pool comes at a price:
1) Each block's header takes 3 machine words of additional space.
2) Allocations and deallocations suffer a constant time overhead, which should be absolutely negligible, given that `malloc` and `free` operations typically constitute only a marginal bit of the runtime's lifetime (an educated guess).
3) Care must be taken to ensure that each block allocated with `caml_stat_alloc` is further operated on using only the `caml_stat_*` functions, otherwise we're asking for segfaults and memory corruption, since "normal" blocks do not start with a header.

I certainly could simplify Halloc, by making it support only flat, non-hierarchical pools. As a result, the block header would only take 2 words, and bookkeeping would become a bit faster. However, hierarchical memory pool may come handy with the [reentrant runtime](https://github.com/lucasaiu/ocaml), which (AFAIK) doesn't support freeing the thread-local storage yet. For instance, there could be one global pool as well as several dependent thread-local pools. There already is the [extensible buffer](https://github.com/lucasaiu/ocaml/blob/master/byterun/extensible_buffer.h) data structure in the reentrant runtime, the planned purpose of which, I suppose, is to be used for implementing thread-local storage. However, it is just a bump allocator, which is terrific for performance and horrific for flexibility. It doesn't allow freeing the blocks in arbitrary order, and I don't see how could it be used to store all that stuff that is being allocated with `malloc` right now.


### Finalising the `Custom` blocks

`caml_finalise_heap` handles finalisation of `Custom`-tagged heap values. The algorithm:
1) Let all heap values become White (by finishing the major cycle).
2) Forcibly sweep the heap, disregarding both local and global roots. Eventually, all `Custom` values are finalised.

We don't need to worry about `Custom` block finalisers disrupting the state of the GC or allocating new values, [because they simply can't](http://caml.inria.fr/pub/docs/manual-ocaml/intfc.html#sec449).


### Handling Gc.finalise

Not only `Custom` blocks need to be finalised, but also those values that have associated finalisers registered with the `Gc.finalise` facility. Handling those values is tricky, because their finalisers are implemented in OCaml, and may themselves allocate finalisable values. In fact, it makes the problem fundamentally unsolvable.

What we _can_ do, however, is to use a heuristic solution which would work well enough in typical cases. For instance, we can simply ignore those values that are allocated by finalisers (and make it a documented behavior of `caml_shutdown`). `caml_final_do_all_calls` implements such a solution, by moving all values from the finalisable set into the finalising set, then triggering a single wave of finalisations (in the correct order, according to the documented semantics of `Gc.finalise`).

A question to those fluent in the runtime internals: why does `caml_final_update` unroll `Forward` values? If a lazy value is passed to a finaliser, wouldn't then the unrolling be handled by an explicit call to Lazy.force, inside the finaliser itself?


### Unloading shared libraries

If a bytecode module statically depends on a set shared libraries (specified in the `DLL` section of the compiled module), then the runtime loads those libraries on startup and stores their handles in a global table. Those libraries must be unloaded explicitly, which is what the new `caml_free_shared_libs` function does.

A strange thing: on Unix (and Unix only), `caml_dlopen` uses the `RTLD_NODELETE` flag, which disables unloading completely, leading to unavoidable leaks. The flag was added 12 years ago by Jacques Garrigue as part of a [huge commit](https://github.com/ocaml/ocaml/commit/0a8236066f945c6026337dd4ea9342a9034f7987), which, apart from adding that flag, doesn't seem to be anyhow related to handling shared libraries.

The flag is removed in my patch, because I couldn't make any sense of it.


### Wrapping it all up

Now that all stages of runtime shutdown are implemented, it's time to figure out the correct order of running them:
* Obviously, `caml_stat_destroy_pool` is the most destructive stage. Once it is triggered, the runtime becomes full of dangling pointers. Therefore, this stage must come _last_ in `caml_shutdown`.
* `caml_final_do_all_calls` triggers OCaml-implemented finalisers; thus it depends on both heap values and loaded shared libraries. It must come _first_.
* `caml_finalise_heap` triggers C-implemented finalisers. Those finalisers may depend on availability of shared libraries. It means that `caml_free_shared_libs` must come strictly _after_ the heap finalisation.


## Demonstration

The [provided set of test programs](https://github.com/cakeplus/caml_shutdown_testcase) can be used, in conjunction with memory debugging tools like Valgrind (on Unix) and DrMemory (on Windows), to demonstrate plausibility of the provided implementation of `caml_shutdown`.

Available `make` targets:
* `leak_test` and `leak_test.opt` build a C application that starts the embedded OCaml runtime, calls a function from the embedded OCaml module, then shuts the runtime down.
* `leak_test_loop` compiles an OCaml program into a shared library using `ocamlc -output-obj`. It also builds a C application that simulates loading and unloading the library dynamically, in an endless loop, calling a function from the embedded OCaml module on each iteration.

Performing a test on one of my real world applications revealed a suspicious leak:
```
mrm@counterfeit-monkey:~/projects/_MY/_GEOTEC/fitsolve$ valgrind --leak-check=full --show-reachable=yes fitsolve -f porosity.pr
==15302== Memcheck, a memory error detector
==15302== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==15302== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==15302== Command: /usr/bin/primec -f halim2.pr
==15302==
==15302==
==15302== HEAP SUMMARY:
==15302==     in use at exit: 32 bytes in 1 blocks
==15302==   total heap usage: 550 allocs, 549 frees, 9,400,464 bytes allocated
==15302==
==15302== 32 bytes in 1 blocks are still reachable in loss record 1 of 1
==15302==    at 0x4C29DB4: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15302==    by 0x512F59F: _dlerror_run (dlerror.c:142)
==15302==    by 0x512EFC0: dlopen@@GLIBC_2.2.5 (dlopen.c:88)
==15302==    by 0x41D231: caml_dlopen (in /home/mrm/.opam/4.03.0local+git-caml_shutdown/bin/ocamlrun)
==15302==    by 0x41C68F: caml_build_primitive_table (in /home/mrm/.opam/4.03.0local+git-caml_shutdown/bin/ocamlrun)
==15302==    by 0x4206E5: caml_main (in /home/mrm/.opam/4.03.0local+git-caml_shutdown/bin/ocamlrun)
==15302==    by 0x41D363: main (in /home/mrm/.opam/4.03.0local+git-caml_shutdown/bin/ocamlrun)
==15302==
==15302== LEAK SUMMARY:
==15302==    definitely lost: 0 bytes in 0 blocks
==15302==    indirectly lost: 0 bytes in 0 blocks
==15302==      possibly lost: 0 bytes in 0 blocks
==15302==    still reachable: 32 bytes in 1 blocks
==15302==         suppressed: 0 bytes in 0 blocks
==15302==
==15302== For counts of detected and suppressed errors, rerun with: -v
==15302== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 3 from 3)
```

Most likely it is a bug either in Glibc or Valgrind itself. I couldn't figure it out. The leak is not cumulative: it doesn't matter if I change `dynlink.c` so that it load/unloads the same library multiple times instead of doing it once — the "leak" stays constant, so I suggest we simply ignore it.