improve safety of `ForkJoin.alloc` with compiler-generated default values

[shwestrick]

Introduced in 456c9c2, the function ForkJoin.alloc: int -> 'a array performs GC-safe parallel initialization of a polymorphic array. The implementation relies on monomorphization as well as an "uninitialization" primitive introduced in 946385f, called _prim "Array_uninit".

This "uninitialization" primitive sets an array cell to a GC-safe bogus value. Roughly speaking, the idea is to set every pointer-valued field to a "null" value, which in MLton takes the form of a bogus objptr. The GC checks for (and never traces) bogus objptrs, so we get GC-safety.

However, at the source level, ForkJoin.alloc is somewhat unsafe. If an uninitialized array contains pointer data, then reading from the array can return a bogus objptr, which could crash the program.

This is not a problem specific to MLton or MaPLe. Any "safe" language runs into a similar issue, and there are well-known solutions. For example, Go has zero values, where every type has a well-defined default value. This is very similar to what MaPLe is currently doing, but one difference is that Go has a source-level notion of nil pointers, which raises the unsafety issue to the source level. In other words, Go forces the programmer to think about nil pointers, which weakens the safety guarantees of the language and simplifies the implementation of the compiler and run-time system. MaPLe has no source-level notion of pointers, and would benefit greatly from a better solution.

I feel like a very reasonable (and perhaps not too difficult to implement) solution would just be to generate a default value for every type at which an "array uninitialization" occurs. This way, rather than setting pointer data to a bogus value, we could set it to a pre-determined global default. This would ensure that ForkJoin.alloc is always type-safe at the source level.

[MatthewFluet]

I don't understand the proposed solution.

I do understand the issue, that ForkJoin.alloc returns a array that has been initialized with bogus objptrs, but, for elements that actually contain objptrs, accessing those bogus objptrs is not safe.

I'm not sure how a "compiler-generated default value" would help. How would you guarantee that that compiler-generated default value, when accessed by user code (along the same code path that it was accessing a bogus objptr), would be handled correctly?

Why not just ForkJoin.Array.tabulate : int * (int -> 'a) -> 'a array and/or ForkJoin.Array.array: int * 'a -> 'a array, requiring the client to provide a suitable default value?

fun array (int, x: 'a) : 'a =
  let
    val a = ArrayExtra.Raw.alloc n
    val _ =
      if ArrayExtra.Raw.uninitIsNop a then ()
      else parfor 10000 (0, n) (fn i => ArrayExtra.Raw.unsafeUninit (a, i))
    val a = ArrayExtra.Raw.unsafeToArray a
    val _ = parfor 10000 (0, n) (fn i => Array.update (a, i, x))
  in
    a
  end

I'm guessing that you are trying to avoid needing to do two loops over the array. If the array elements really are proper objptrs, then it isn't clear that one can do so safely (with the current GC). The point of the Raw.alloc is to allocate an array with a header that says that it has elements with no objptrs; therefore, any GC will byte-for-byte copy the array without attempting to trace any elements. The bogus objptrs written into each element are preserved by this byte-for-byte copy should a GC be invoked before the array has been fully initialized. Then the Raw.unsafeToArray switches the object header to say that it has elements with objptrs; now it is safe to "trace" this array, because the GC will see bogus objptrs everywhere.

If one were to try to simplify to:

fun array (int, x: 'a) : 'a =
  let
    val a = ArrayExtra.Raw.alloc n
    val a = ArrayExtra.Raw.unsafeToArray a
    val _ = parfor 10000 (0, n) (fn i => Array.update (a, i, x))
  in
    a
  end

then the GC could attempt to interpret "garbage" data as an objptr for tracing. This is because the Raw.alloc just does a bump-pointer allocation, leaving any "old"/"garbage" data that happened to be in that segment of the heap in the array.

And, if one were to try to simplify to:

fun array (int, x: 'a) : 'a =
  let
    val a = ArrayExtra.Raw.alloc n
    val _ = parfor 10000 (0, n) (fn i => Array.Raw.update (a, i, x)) (* Raw.update doesn't exist *)
    val a = ArrayExtra.Raw.unsafeToArray a
  in
    a
   end

then the GC would not update the objptrs in the array when tracing and then clients could encounter dangling pointers. This is because the Raw.alloc allocates an array with a header that says that it has elements with no objptrs, so the GC doesn't attempt to trace/forward any elements.

Maybe what you are interested in is being able to efficiently support initializations of (int * int * int) option arrays with NONE. This case has the property that the representation of an (int * int * int) option element is an objptr, where it is a "proper" objptr for SOME and a "bogus" objptr for NONE. In this special case, then the second simplification above would be valid.

One might be able to work towards a version like:

fun array (int, x: 'a) : 'a =
  let
    val a = ArrayExtra.Raw.alloc n
  in
    if ArrayExtra.Raw.isUninitVal (a, x) then
      let
        val _ = parfor 10000 (0, n) (fn i => Array.Raw.update (a, i, x)) (* Raw.update doesn't exist *)
        val a = ArrayExtra.Raw.unsafeToArray a
      in
        a
      end
    else
      let
        val _ =
          if ArrayExtra.Raw.uninitIsNop a then ()
          else parfor 10000 (0, n) (fn i => ArrayExtra.Raw.unsafeUninit (a, i))
        val a = ArrayExtra.Raw.unsafeToArray a
        val _ = parfor 10000 (0, n) (fn i => Array.update (a, i, x))
      in
        a
      end
  end

Adding Array.Raw.update would be easy. Adding Raw.isUnitVal: 'a Raw.array * 'a -> bool is a little trickier, because we would want it to commute with and not inhibit flattening. That is, an ((int * int) option * bool) array initialized with (NONE, true) should take the fast path, if the array is flattened.

[shwestrick]

I'm guessing that you are trying to avoid needing to do two loops over the array. If the array elements really are proper objptrs, then it isn't clear that one can do so safely (with the current GC).

Ah! Perhaps you're worried about the GC-safety of the default elements? This is a good point.

So, I guess this proposal would need to modify the GC slightly too. Here's an idea: we could put the statically generated default elements into a global pinned heap space. Their addresses would therefore be fixed throughout execution. Forwarding a default-generated element would be disallowed. This would make it irrelevant whether or not the GC traces a pointer into a default element, so we would get GC-safety across the header switch, from raw to actual. (I'm picturing that the implementation of ForkJoin.alloc would mostly unchanged. We would still use the header-switch trick.)

I'm guessing that you are trying to avoid needing to do two loops over the array.

And yes, to come back to this point: I have in mind a performance goal. The goal is for array allocation to be constant-time if there are no pointers post-flattening.

Unfortunately, the semantics of Array.array(n,x) is incompatible with this goal, because it always pays the initialization cost no matter what. And, in our benchmarks and libraries we've found lots of situations where arrays need to be initialized in a manner which doesn't align with Array.tabulate(n,f). A good example is the implementation of the three-phase blocked scan, specifically the initialization of the output array in the third phase of the algorithm.

The proposal here would just be a small modification of our current initialization trick. The implementation of ForkJoin.alloc would be exactly the same as it is now, but we would give a new semantics for Raw.unsafeUninit. I'm picturing the new semantics would be:

Raw.unsafeUninit(a,i): 
  for each component j of a[i]:
    if possibly-garbage bytes at a[i][j] is type-safe, then do nothing
    else, initialize a[i][j] to a statically-generated default

[shwestrick]

It occurs to me also that Raw.unsafeUninit would need to know the "target" header of the array. We could probably pass in some sort of description as argument. (And then, rather than changing the definition of Raw.unsafeUninit, perhaps it would be easier to just provide a new primitive with the new semantics.)

[MatthewFluet]

I'm guessing that you are trying to avoid needing to do two loops over the array. If the array elements really are proper objptrs, then it isn't clear that one can do so safely (with the current GC).

Ah! Perhaps you're worried about the GC-safety of the default elements? This is a good point.

So, I guess this proposal would need to modify the GC slightly too. Here's an idea: we could put the statically generated default elements into a global pinned heap space. Their addresses would therefore be fixed throughout execution. Forwarding a default-generated element would be disallowed. This would make it irrelevant whether or not the GC traces a pointer into a default element, so we would get GC-safety across the header switch, from raw to actual. (I'm picturing that the implementation of ForkJoin.alloc would mostly unchanged. We would still use the header-switch trick.)

I guess that would work, but seems a little fragile.

I'm guessing that you are trying to avoid needing to do two loops over the array.

And yes, to come back to this point: I have in mind a performance goal. The goal is for array allocation to be constant-time if there are no pointers post-flattening.

I think that you can only get constant time and safe if all of the components of the array are word or real types -- i.e., types for which all bit patterns are valid values. I don't think that you can avoid the initialization with bool or enum-like datatypes.

Unfortunately, the semantics of Array.array(n,x) is incompatible with this goal, because it always pays the initialization cost no matter what. And, in our benchmarks and libraries we've found lots of situations where arrays need to be initialized in a manner which doesn't align with Array.tabulate(n,f). A good example is the implementation of the three-phase blocked scan, specifically the initialization of the output array in the third phase of the algorithm.

The proposal here would just be a small modification of our current initialization trick. The implementation of ForkJoin.alloc would be exactly the same as it is now, but we would give a new semantics for Raw.unsafeUninit. I'm picturing the new semantics would be:

Raw.unsafeUninit(a,i): 
  for each component j of a[i]:
    if possibly-garbage bytes at a[i][j] is type-safe, then do nothing
    else, initialize a[i][j] to a statically-generated default

Ah, that could work.

[shwestrick]

I guess that would work, but seems a little fragile.

A big scary warning comment would definitely be needed in a few places :)

I think that you can only get constant time and safe if all of the components of the array are word or real types -- i.e., types for which all bit patterns are valid values. I don't think that you can avoid the initialization with bool or enum-like datatypes.

Ah! That's a good point. I was wondering which types this would and wouldn't work for.