Bigarray sub-arrays counted towards total out-of-heap memory usage

[codido]

The following code snippet demonstrates the issue:

module A1 = Bigarray.Array1

let rec sum_bigarray arr sum =
  match A1.dim arr with
  | 0 -> sum
  | len ->
      let sum = sum + A1.get arr 0 in
      let remaining = A1.sub arr 1 (len - 1) in
      sum_bigarray remaining sum

let () =
  let arr = A1.init Bigarray.Int Bigarray.c_layout 1_000_000 Fun.id in
  Printf.printf "sum: %d\n%!" @@ sum_bigarray arr 0

From a quick look, it appears that creating sub-arrays of bigarrays may result in excessive GC cycles. For example, running the above snippet, the top offenders according to perf are:

    55.29%  main.exe  main.exe              [.] pool_sweep
    12.18%  main.exe  main.exe              [.] caml_darken.part.0
     9.38%  main.exe  main.exe              [.] caml_scan_global_roots
     3.71%  main.exe  main.exe              [.] caml_darken
     2.49%  main.exe  main.exe              [.] mark
     1.99%  main.exe  main.exe              [.] major_collection_slice
     1.06%  main.exe  main.exe              [.] caml_scan_stack

From what I can tell, the out-of-heap amount is increased as a result of calling caml_ba_alloc even if no out-of-heap memory is actually being allocated. To make things worse, since caml_ba_sub calls caml_ba_alloc with the original dimensions, the size of the whole (original) bigarray is counted towards the total out-of-heap memory.

[gasche]

I looked at the code, agree that there is an issue worth fixing, and discuss some options I see to fix the bug. Hopefully people who know bigarrays better can chime in with preference regarding potential fixes.

caml_ba_alloc is defined as follows:

/* [caml_ba_alloc] will allocate a new bigarray object in the heap.
   If [data] is NULL, the memory for the contents is also allocated
   (with [malloc]) by [caml_ba_alloc].
   [data] cannot point into the OCaml heap.
   [dim] may point into an object in the OCaml heap.
*/
CAMLexport value
caml_ba_alloc(int flags, int num_dims, void * data, intnat * dim)

Currently its caml_alloc_custom_mem call counts the bigarray external memory for all GC-tracked bigarrays, which is (as pointed out by @codido) not appropriate for "proxied" bigarrays that share their external memory.

I see two different approaches to fix the issue:

1. in caml_ba_alloc, we can stop counting the external memory when data is not NULL. In bigarray.c, this change is correct: a non-NULL field is passed exactly for bigarrays that reuse another's memory. But this could lead to under-counting external memory for user code that performs its own external allocation before calling caml_ba_alloc -- it passes explicit data, which is really owned by the bigarray.
2. we could provide a separate caml_ba_alloc_proxied function for bigarrays that share their data with an existing bigarray, and use that in bigarray.c. This is slightly more invasive, but it guarantees the absence of under-counting in user code using caml_ba_alloc.

Note that for some user code the same over-counting may occur (as in the runtime) and so (1) would also fix the issue in user code while (2) would keep over-counting (if the user does not update their code to use caml_ba_alloc_proxied).

Another solution might be to tune caml_update_proxy to reduce GC pressure from external memory, after caml_ba_alloc increased it -- as if the corresponding external memory had just been deallocated. This sounds bizarre to me.

[gasche]

I thought more about this and now believe that approach (1) is always the right choice when the flags parameter contains the MANAGED flag: in this case, the caller (either the runtime or an external user) claims that the memory passed is already owned by the OCaml heap, so it has already been accounted for and we should not increase the GC pacing.

I propose PR #12493 with a bugfix, which is fairly small/uninvasive. With this bugfix, the proposed testcase terminates immediately.

[gasche]

Thinking more about this, I am not sure what semantics a user should have in mind when calling caml_ba_alloc with the MANAGED flag and a non-NULL data argument:

1. my interpretation: data is already owned by the OCaml heap
2. another reasonable interpretation: the user is transferring ownership of the external data to the OCaml heap (they will not free it, it is now the GC's duty)

This bugfix assumes (1), but (2) is also a possibility. In this case the calls to caml_ba_alloc in the subarray/slicing functions are wrong and should be fixed by introducing a generalized allocation function to tweak the GC-pacing logic.

[gasche]

I looked at some user code found through Github code search, and I can see several cases where I believe that the MANAGED flag is used to transfer ownership of newly-allocated memory to the OCaml GC:

• https://github.com/bcpierce00/unison/blob/7aaac7bd85720d04799bd06a5aa512ab1377adee/src/bytearray_stubs.c#L17
• https://github.com/janestreet/core/blob/6d1f19342a98cd718c0f9a59e2e82bc1449a0c2d/core/src/bigstring_stubs.c#L92
• https://github.com/kit-ty-kate/mirage-solo5/blob/c747922fa1f0c412386df99b0986d8c4a45f52ee/lib/bindings/alloc_pages_stubs.c#L62

The fix proposed in #12493 would be incorrect in this case -- where I believe we should increase GC pacing, so I closed that issue.

I think that a better fix would be to introduce an alloc function whose caller can indicate that they are reusing external memory already tracked in the OCaml heap.

[codido]

@gasche, thanks so much for the prompt response and fix!

Regarding the ownership transfer use case you mentioned, it seems a bit fragile due to the prerequisites for the transferred memory block (must reside on the same heap, freeable with free()). Case in point, out of the three examples you noted above, it looks like two might be problematic?

For the unison case, unless I'm missing something, the data transferred does not necessarily point directly to memory allocated by malloc, so freeing it later on could result in memory corruption.

For the core case, wouldn't the GC pace be a bit off here? It looks like caml_ba_alloc is called with the original dim, so the GC pace would be increased by that amount and not by the new size, and moreover, not sure the old (freed) allocation size is taken into account?

Not suggesting that there's anything wrong with your change however, just that it's a tad tricky to get it right :)

[gasche]

Good points.

1. in the unison case, the memory is allocated by caml_output_value_to_malloc, which one may reasonably expect to just call malloc, but in fact calls caml_stat_alloc_noexc, which may (in pooling mode) return a pointer into a larger allocation with some metadata. I would still claim that the unison code is morally correct, and the runtime should make it work by using a real malloc in the public caml_output_value_to_malloc, and using a separate caml_output_value_to_stat_alloc function for runtime tracking needs.

2. in the core case, the code allocates a new Bigarray with the same dimension as the previous bigarray, and then mutates its dimension array after the fact. This is a bug in the user code (for external memory accounting), which should instead compute the correct dimensions first and then allocate. Once this independent bug is fixed the code should (I think?) work as expected.

[codido]

Regarding (2), even if it did that, would the old memory block size (that's now freed) be accounted for?

[gasche]

(Indeed, this was an unsatisfying suggestion and I edited it out in the meantime.)

[gasche]

Digging a bit further: there is more code on the web that assumes that caml_output_to_malloc can then be freed, for example:

• https://github.com/facebook/hhvm/blob/9b47b200a774f95097034652cc5c7b3fda30dee5/hphp/hack/src/shmffi/ocaml_blob.rs#L220
  https://github.com/facebook/hhvm/blob/9b47b200a774f95097034652cc5c7b3fda30dee5/hphp/hack/src/shmffi/ocaml_blob.rs#L198

• https://github.com/facebook/pyre-check/blob/9f71c27b1b4cfee518841c6e98cd52b006fa712f/hack_parallel/hack_parallel/heap/hh_shared.c#L1670
  https://github.com/facebook/pyre-check/blob/9f71c27b1b4cfee518841c6e98cd52b006fa712f/hack_parallel/hack_parallel/heap/hh_shared.c#L1715

And just for fun there is also code that uses caml_stat_free:

• https://github.com/xavierleroy/ocamlmpi/blob/3ff7aedf05216722ec08b2aabab1af84f595f37c/msgs.c#L51-L56

[gasche]

(Xavier sent me his own fixes for this and I need to do the work of comparing them and blessing one of them for upstreaming. I hope to get to it soon.)