Request for more complicated list examples

[dabek]

Firstly, thanks for working on this library - I've found it very useful!

I have a question about constructing lists. I'll be happy with just hearing your answer here, but I think this is also something worth including in examples. There is only one example, ml_new_list, which creates a static 5 element list. But what if we want to do something more complicated, where the list has a dynamic length? Here is my attempt:

caml!(make_list, |length|, <dest>, {
    let length = length.i32_val();
    let mut list = ocaml::List::new();
    for i in 1..length {
        list.push_hd(i.to_value())
    }
    dest = list.into()
} -> dest);

external make_list: int -> int list = "make_list"

let () = 
  Printf.printf "Calling \"make_list\"...\n";
  flush(stdout);
  let l = make_list 100000 in
  Printf.printf "...done\n";
  flush(stdout);
  Printf.printf "%d\n" (List.length l);
  ()

On my machine, this can

• print the expected output, if we reduce 100000 number to something much smaller
• segfault in above form
• infinite loop if I remove the printf statements
• print a senseless output (like 87376) if I add some other printf statements in-between

I think this is fair, because we are not obeying the rules of living in harmony with the garbage collector. In particular, our mut list is a local variable that is not specified using CAMLlocal macro (only dest and length are). So I think what happens, is that one of the allocations performed by push_hd triggers garbage collection run, which doesn't see anything pointing to our list and happily collects it, leaving the system in undefined state.

I can't just change mut list to a type defined with CAMLlocal, because they have incompatible types (ocaml::List vs ocaml::Value). How is ocaml::List intended to be used then?

[zshipko]

Hey, thanks for writing this up. To be honest, I hadn't really considered how to use the List type beyond the list! macro and List::from, and even those are poorly implemented.

It looks like I will need to figure out a good way for List to interact with the OCaml garbage collector safely. I'm guessing that if you had a static list! declaration with 100000 items (like your example) it would cause similar problems for the reasons you mentioned above. In the meantime, I guess you could use an array instead of a list.

I will think about it and update this issue once I've figured out a good solution -- although the best solution may be to remove List altogether.

I'm also happy to discuss this further if you have any ideas!

[dabek]

I hacked around the list issue by using the lower level interface directly (and basically re-doing what the higher level API does, while avoiding the mentioned bug):

let mut tmp = ocaml::core::mlvalues::UNIT;
let mut res = ocaml::core::mlvalues::UNIT;
caml_param!(tmp, res);

res = ocaml::core::mlvalues::empty_list();

for v in ... {
      tmp = ocaml::core::alloc::caml_alloc(2, 0);
      ocaml::core::memory::store_field(tmp, 0, v);
      ocaml::core::memory::store_field(tmp, 1, res);
      res = tmp;
}
ocaml::Value::new(res)

Now all the values we allocate are always pointed to by either tmp or res, which are "registered" with GC by caml_param!.

The program I'm building made more progress through test cases, but was still segfaulting. The next suspicious part was the tuple! macro. It seems to suffer from similar issue. The docs say

The first argument of Store_field and Store_double_field must be a variable declared by CAMLparam* or a parameter declared by CAMLlocal* to ensure that a garbage collection triggered by the evaluation of the other arguments will not invalidate the first argument after it is computed.

During execution of this macro, dst variable over here is the only pointer to what becomes a first argument of Store_field (inside dst.set(...)), and it's not a CAMLlocal.

Rewriting all the tuple! macros in a similar low level way as I dealt with list stopped the segfaults for now.

This makes me think that the whole higher level API might be flawed in that way, and for now it's better to stick with the functions from src/core/ only.

[zshipko]

I started a branch: fix-types where I've added a local parameter to the Array, List and Tuple types. Despite making the API a little confusing, I think it should be sufficient to fix the issues.

This means instead of List::new() with no arguments, you will now need to pass a mutable reference to a value created using caml_local.

In the case of List.push_hd, that function also takes a local argument, since it performs allocation internally.

The make_list implementation now looks like this:

  caml!(ml_make_list, |length|, <tmp, dest>, {
      let length = length.i32_val();
      let mut list = ocaml::List::new(&mut dest);
      for v in 0..length {
          list.push_hd(&mut tmp, Value::i32(v));
      }  
  } -> dest);

I will go over the new API a little more before releasing since, but feel free to test it out and let me know if you find any issues too. This stuff is pretty tricky, so I'm happy to have another pair of eyes looking at it. Thanks again for bringing this to my attention.

[dabek]

I think it is possible to keep the API unchanged. The part that now forces it's awkwardness is that we are limiting valid values to params/locals defined in the outermost caml! macro, which forces the need to pass the values that internal functions need from outside.

But there is nothing limiting the internal functions from registering more locals, exactly the same way function defined with caml! macro does. So for example, some could change from

pub fn some<V: ToValue>(v: V) -> Value {
  let mut x = Self::alloc(1, Tag::Zero);
  x.store_field(0, v.to_value());
  x
}

to

pub fn some<V: ToValue>(v: V) -> Value {
  let caml_frame = crate::core::memory::caml_local_roots;
  let mut x = ocaml::core::mlvalues::UNIT;
  caml_param!(x);
  x = Self::alloc(1, Tag::Zero);
  x.store_field(0, v.to_value());
  crate::core::memory::caml_local_roots = caml_frame;
  x
}

( or some slightly cleaner version utilizing more macros), which (I believe) solves GC problems without changing API.

[zshipko]

Okay, I think I have a working solution now.

I added a new macro called caml_frame to the fix-types branch. This is used to take care of the whole caml_local_roots song and dance and allows use to write something like this to get a fresh value:

let v = caml_frame!(|x| {
    x = Value::alloc(3, Tag::Zero);
    x.store_field(0, Value::i32(0));
    x.store_field(1, Value::i32(1));
    x.store_field(2, Value::i32(2));
    x
});

I've wrapped all internal allocation of values in the high-level API using caml_frame, and it seems to be behaving correctly now as far as I can tell -- I'm happy to be proven wrong, so let me know if you uncover any further issues.

If it works for you, I will merge this and release it to crates.io after checking everything over once more later this week.

[dabek]

I'll try to integrate the updated version into my project sometime next week and let you know if it works. But from just looking at the code, few places still look sketchy. For example, Tuple::from: during the execution of new, value created by caml_alloc_tuple is now "protected" by caml_frame, but this ends at the end of that function - local roots are reverted back to what it was before the call. In the caller, mut t becomes a dangling reference again that can get garbage collected during subsequent calls to set. There should be a caml_frame! surrounding the body of Tuple::from too.

Basically to make it 100% correct there can be never a "let (mut) _ =" definition of variable that is, or internally contains core::mlvalues::Value - all such definitions must go through caml_local/caml_frame or similar.

In general, this is really tricky to get right without a complicated enough application utilizing it, or investing more in stress testing, since it is all likely to work for simple to medium examples, and then blow up in undebuggable way for a bigger one when the "right" sequence of GC runs hits the hidden bug.

If I were to write an artificial stress test, I would go with randomly generating (and printing?) Ocaml values utilizing as many macros as possible (so, something like: generate random length lists of random variants, where variant arms are either 0-ary, a tuple of several possible lengths, a record with few simple fields. For bonus points you can make it tree-like (so let's say one of the record fields can also be the random list of records etc.). There is still some risk that the generated structure will be for some reason too regular and miss the bug, but less serious.

Alternatively, you can try forcing more GC runs to increase the probability of uncovering bugs. For example, instrumenting memory:store_field to perform a GC.full_major() might uncover all the cases where a dangling reference is passed to this function.

[zshipko]

Thanks, I will take a look at the Tuple functions you mentioned, as well as do a more general sweep for similar behavior then try to write some stress tests when I get the chance.

[dabek]

Just a quick update on what I eventually did, since I promised taking a look at most recent version - the next step in my project required storing pointers to OCaml allocated values in a HashMap, which have once again ran into the same problem of GC changing them under our feet.

We've concluded that there is no way to accomplish it with the high level caml_alloc API (that this library is also utilizing) and ended up rewriting it on an even lower level, manually allocating memory blocks outside of the heap and forming them to look right.

You can see examples in https://github.com/facebook/hhvm/commit/01eacbeabc9917adbd7d3228740c41e68c12d91e and https://github.com/facebook/hhvm/commit/8055b562b037efd1354c31e23415e99a11d0f1a5. I think what we ended up needing might be out of scope of this library, so feel free to close this issue if you think that the use cases you wanted to support work well enough.

Thanks again for your help!

[zshipko]

Interesting, thanks for sharing! I will read through that sometime soon.

I am going to close this and publish a new (non-beta) release with the changes that came from this thread, I really appreciate you bringing this to my attention in the first place.