Segfault or infinite loop in 'caml_unregister_frametable'

[recoules]

Dear developers,

I am playing with JIT, compiling small codes, registering and unregistering frame tables.
Usually, when something goes wrong, it is because I messed with the runtime, but this time, it seems there is a possible bug in the function caml_unregister_frametable:

ocaml/runtime/roots_nat.c

Lines 208 to 229 in 679b500

	void caml_unregister_frametable(intnat *table) {
	intnat len, j;
	link *lnk;
	link *previous = frametables;
	frame_descr * d;
	len = *table;
	d = (frame_descr *)(table + 1);
	for (j = 0; j < len; j++) {
	remove_entry(d);
	d = next_frame_descr(d);
	}
	iter_list(frametables,lnk) {
	if(lnk->data == table) {
	previous->next = lnk->next;
	caml_stat_free(lnk);
	break;
	}
	previous = lnk;
	}
	}

For me, it does not take into account that the root of the list (frametables) can be the one we "unregister".
Thus, I would make the following changes at lines 221-228:

if (frametables->data == table) {
  lnk = frametables;
  frametables = frametables->next;
  caml_stat_free(lnk); 
} else {
  iter_list(frametables->next,lnk) { 
     if(lnk->data == table) { 
       previous->next = lnk->next; 
       caml_stat_free(lnk); 
       break; 
     } 
     previous = lnk; 
   }
}

Regards,

[recoules]

Note that this is for OCaml 4.xx but I think something like this could be easily added to OCaml 5.

In fact, it seems like it will be easier because it only has to remove the link from frametable and wait the frame_descriptors to be rebuilt, "if needed", when a new table is added. I think it is not an issue if the hash table still contains "dead" entries as long as we can release the external memory allocated for table.

[gasche]

This bug should be absent from 5.x, and has been fixed for future 4.x releases by merging @recoules' own #11636. Thanks! (With apologies for the sizeable delay here.)

[recoules]

Hi @gasche,

This bug seems indeed absent to 5.x version because there is no longer a caml_unregister_frametable function.
I think it is an issue because it is no longer possible to detach some code when it becomes unused -- it is a source of memory leak (future-proof).

I think the function caml_unregister_frametable can be restored and should do the following:

• remove the frametable from the caml_frametable_list in the current_frame_descrs (so if the hashtable is rebuilt, it will not contain the unregistered entries);
• replace the frame_descr entries in the hashtable by a dummy frame_descr (e.g. with retaddr = -1) to simply invalidate the entry without "costly" removing.

This way, the memory block of the frametable can be freed without worries about use-after-free or segfault error.

I should be able to create a PR if you want.

[gasche]

On paper I agree with the idea of restoring removed functionality.

Note that touching the frametables is more cumbersome in the multicore runtime due to the synchronization needs -- modifying this requires doing a stop-the-world pause, so expect 20 extra lines of boilerplate to do this.

Before you put the work of doing this and we review it, it may help however to ensure that some people are actually going to use the code. Are you still working on JIT experiments yourself where this would hep you? (Do you have a pointer somewhere to the sort of experiments that you are making?)

[recoules]

Are you still working on JIT experiments yourself where this would hep you?

Yes I do and plan to submit a paper at JFLA on that topic (thankfully it is simple-blind, all that's left is to write it down...).
Things will be made public soon. For now, it is not an issue because I stick with 4.14.

The idea is that the closure of the JITed function keep alive the frame table of its code. If the closure is garbage collected (meaning the function will never be called again), we unregister the frame table.

Note that touching the frametables is more cumbersome in the multicore runtime due to the synchronization needs -- modifying this requires doing a stop-the-world pause, so expect 20 extra lines of boilerplate to do this.

Yes, I saw this. In the same vein, it also passes from single table to array of tables. I will have to think a little bit about all of this but it should be ok.

Question: the unregistering will be called during garbage collection, so already in a stop-the-world. Can it cause some issues or will the lock simply return immediately?

[gasche]

Question: the unregistering will be called during garbage collection, so already in a stop-the-world. Can it cause some issues or will the lock simply return immediately?

If you were to put unregistering calls within the garbage-collection C code, you would need to write the code as already being part of a STW handler. If you are thinking of unregistering from a finaliser, forget it, the interactions with other parts of the runtime will be unreasonably difficult to work with. You probably have to implement delayed collection in this case, in the sense that a finaliser would just write down information about frames to be removed in a worklist somewhere, and then your own code (not running during GC) would look into the list once in a while and perform the actual removal if it is non-empty.

[recoules]

Sound reasonable. I will add a pending list unregistering the table before allocating a new one.
(in fact, it already how I handled the bug of the current issue to wait for the changes to be applied)

[recoules]

Hi @gasche,

I think I will soon have something working for a caml_unregister_frametables(void **frametables, int ntables).
I still have to update my experiments to work with OCaml 5 and test if everything is working as expected.

Yet, I am wondering why modification of the global hashtable should always be in a STW event.
Of course, if we are about to reallocate and refill the table, we need to STW, but for me, light addition or deletion could be done without STW, using a simple mutex only for writes.
Maybe I am wrong, but my point is that data race (read/write) should not be an issue:

• if a domain is going to add an entry and another one is reading the table (it should not happen really often since I believe the table is mostly read during GC work), the code the entry is referring can not have been used yet, then the entry can not be the one the reader is looking for => NULL or a new entry will not change the behavior of the reader;
• if a domain is going to remove an entry and another one is reading the table, the code the entry is referring should no longer be in use, then the entry can not be the one the reader is looking for => a dummy entry or the old entry will not change the behavior of the reader.
  Races (write/write) will not happen due to the mutex.

Am I missing something ?

[gasche]

Adding a STW section around the global state update was fairly simple and could reuse most of the 4.14 code. On the other hand, if we want to allow read/write races on frametable entries, we must make them atomic accesses, think about the memory order we need and its performance impact for reads in the GC. This is a more complex change to consider.

@gadmm proposed/sketched an atomic-rather-than-STW approach in #11926 (comment) , and you might want to consider that approach. Personally I would stick to the STW approach unless you see a performance need for faster writes.

[recoules]

Thank you @gasche. I think @gadmm summarized my "intuition" in:

Synchronization is avoided for readers because each version is monotonous and each intermediate state of the table is a valid hash table.

if we want to allow read/write races on frametable entries, we must make them atomic accesses

I think that, on the contrary, we do not need it since whatever the intermediate or final state the reader reads, it is valid (according to the fact that caml_registering_frametables or caml_unregistering_frametables are called correctly).

Personally I would stick to the STW approach unless you see a performance need for faster writes.

Sounds fair. For now, I have no benchmark that requires a performance improvement.
But, my idea was: if we could remove an entry without a STW, it will make it easier for "users" to call caml_unregister_frametables in a finalizer (in my mind, the best place to put some cleaning/release stuff) and remove the need for every "user" (ok, for now I am the only one ^^) to add an ad'hoc pending list in their code. And then, if the work has been done to remove an entry outside a STW, it should be quite easy to do it for adding an entry too.

If you think it could be interesting, I would be glad to perform some experiments on it (on my free time, so it may take quite some time).

Also, as a side remark/question, do you know why caml_get_frame_descrs and caml_next_frame_descriptor return/take a plain caml_frame_descrs structure instead of a pointer to the struct ?

[gasche]

My understand of concurrent C code is that whenever there is a race, the code has undefined behavior (UB) unless the racing accesses are atomic operations. They do not need to be "strong" (sequentially consistent) atomic accesses, they could be relaxed or something else, but they need to be atomic operations.

We could remove an entry without a STW, it will make it easier for "users" to call caml_unregister_frametables in a finalizer

If you need the convenience of a finaliser, you could use Gc.finalise on the OCaml side; such "OCaml finalisers" are given full runtime access, so they can also run STW sections.

If you think it could be interesting, I would be glad to perform some experiments on it (on my free time, so it may take quite some time).

I think that having proper atomic frametables would be an improvement over the current state of the code, but it's a lot of work and will add some amount of complexity. In your stead I would not prioritize this, but this is of course your choice.

Also, as a side remark/question, do you know why caml_get_frame_descrs and caml_next_frame_descriptor return/take a plain caml_frame_descrs structure instead of a pointer to the struct ?

I am not sure. I suspect that it comes from the previous, more complex implementation of frametables that we had in 5.0, with several frametable_version values in flight at any given time. At that time it may have been important to copy the structure (instead of sharing it) to avoid races. See: https://github.com/ocaml/ocaml/blob/5.0/runtime/frame_descriptors.c