out-of-heap data structures

out-of-heap data structures

[oleg]

Xavier Leroy wrote:
> There is one caveat: ad-hoc polymorphic primitives (structural
> equality and comparisons, marshaling, hashing) will not work on data
> structures that reside outside of the Caml heap.  The reason is that
> these primitives treat out-of-heap pointers as opaque data.  There is
> a special case (the "Is_atom" test) for pointers that correspond to
> ocamlopt-generated static data, but extending this special case is
> nonobvious.

Actually, MetaOCaml has done such an extension. The extension is
general purpose and backward compatible. Furthermore, no base OCaml
sources were harmed in the process: there is no need to recompile
ocamlopt or the standard library. The linking of the final executable
does require a few extra flags.


The Is_atom test in the ocamlopt-produced executables checks if the
address of the tested value falls within the data segment of the
executable. Alas, if we permit dynamic loading of ocaml-opt compiled
code, static data no longer reside in one segment (within one
continuous range of virtual addresses). Therefore, modifications are
necessary.

Native MetaOCaml (or, to be precise, the dynamic linking part of it)
has carried out such modifications. The Is_atom test now reads

CAMLextern struct DYNlimits caml_static_data_limits; /* in new ndl.c */
#define Is_atom(v) \
  ((((char *)(v) >= caml_static_data_start \
     && (char *)(v) < caml_static_data_end) \
    || ((v) >= Atom(0) && (v) <= Atom(255))\
    || (caml_static_data_limits.used != 0 && \
	within_DYNlimitsP((void *)v,&caml_static_data_limits))))

The change is fully backward-compatible: if no dynamic linking is used
(or if the data segment is indeed contiguous), the field
caml_static_data_limits.used has the value 0 and Is_atom works exactly
as before. The additional cost then is dereferencing of a static
address -- which could be as few as two instructions (test and branch)
on some architectures.

It seems the extension can be used for maintaining `out-of-heap' OCaml
structures. One can have as many such heaps as needed. One merely need
to register the range of these extra-heap addresses.

The code can be found in the directory natdyn of the current MetaOCaml
distribution, specifically files mlvalues.h and ndl.c. The Makefile
contains the necessary voodoo to get the changes take effect.