Reimplement Obj.reachable_word using a hash table to detect sharing #9678

xavierleroy · 2020-06-14T14:40:07Z

The previous implementation (caml_obj_reachable_words in runtime/obj.c) was modifying the mark bits of block headers to detect sharing. This is not compatible with Multicore OCaml.

The marshaler used to play the same trick. In #9353 it was modified to use a hash table instead of mark bits to track blocks already seen.

Likewise, this PR reimplements caml_obj_reachable_words to use a hash table.

The implementation reuses the hash table used to detect sharing during marshaling and other bits of the marshaler, hence the function caml_obj_reachable_words was moved to runtime/extern.c.

A change of semantics is required in no-naked-pointers mode. Currently, Obj.reachable_word does not count data that is statically allocated outside the OCaml heap, e.g. ocamlopt-generated structured constants. In no-naked-pointers mode and later in Multicore OCaml we want to get rid of the page table, and will have no way to distinguish statically-allocated data from heap-allocated data, and we must count both.

The above is the first commit of this PR, 50d51c4.

Now there is a funny test that checks that Obj.reachable_word on a structured constant returns 0 in native-code (because out-of-heap static allocation) and the actual size in bytecode. This test fails in no-naked-pointers mode, because the actual size is returned in both case. Hence, commit a31cbc1 splits the funny test into its own file, and conditionalizes the test on the fact that naked pointers are supported.

To support this, commit bb13bb5 adds a naked_pointers action to ocamltest.

To enable that, commit 3e92cae teaches configure to put a NAKED_POINTERS={true,false} in Makefile.config. (Before, the "naked pointer" info was only in runtime/caml/m.h)

Phew.

Special mention to @alainfrisch (original author of Obj.reachable_words) and to @shindere (for the configure and testing aspects).

hhugo · 2020-06-15T11:51:55Z

runtime/extern.c

+      mlsize_t sz = Wosize_hd(hd);
+      /* Infix pointer: go back to containing closure */
+      if (tag == Infix_tag) {
+        v = v - Infix_offset_hd(hd);


Should we check if v was already visited here ?

No need to. I chose to enter the closure itself in the hash table, but not its infix pointers. Sharing will be detected and recorded after we go back to the containing closure.

Right, that makes sense.

xavierleroy · 2020-06-21T08:30:11Z

This PR needs to be reviewed.

jhjourdan

It should be better to reorder the commits of this PR, to make sure that tests succeed even in intermediary commits, for easier bisecting.

The documentation of Obj.rachable_words need to be updated to the new behavior.

Apart from that, this looks good to me.

jhjourdan · 2020-06-22T11:30:19Z

runtime/extern.c

+    }
+    /* Pop one more item to traverse, if any */
+    if (sp == extern_stack) break;
+    v = *((sp->v)++);


Suggested change

v = *((sp->v)++);

v = *(sp->v++);

Spurious parentheses (just because I like nitpicking).

This was patterned after line 831. I like the extra parentheses because otherwise I tend to read this as sp->(v++), which makes no sense of course.

We have NAKED_POINTERS=false if configured with --disable-naked-pointers, NAKED_POINTERS=true otherwise.

xavierleroy · 2020-06-22T12:25:48Z

It should be better to reorder the commits of this PR, to make sure that tests succeed even in intermediary commits, for easier bisecting.

Right. Done!

The documentation of Obj.rachable_words need to be updated to the new behavior.

Done.

I'll wait some more to give @shindere a chance to comment on the changes to configure and ocamltest.

shindere · 2020-06-22T13:37:50Z

Xavier Leroy (2020/06/22 05:26 -0700):

I'll wait some more to give @shindere a chance to comment on the changes to configure and ocamltest.

Sorry for the delay, will do my best to review promptly.

shindere · 2020-06-22T15:35:42Z

Re: the "naked_pointers" ocamltest action, I think it would be better to add it to `ocaml_actions` rather than to the `builtin _actions` module because it is specific to the OCaml compiler. Think of `builtin_actions` as actions that could be relevant to otehr contexts than the one of the OCaml compiler. Also, regarding the text associated with this action, could it be made clearer? Currently it just mentions the "target". In the absence of any precision, I'd tend to understand it at the target CPU or host or platform, whereas, IIUC, naked pointers are more a property of the runtime system, right? If this is true, then it could perhaps be clarified by explicitly saying the "target runtime". The rest of the configure and ocamltest related bits looks good to me, thanks for having waited and my apologies for the delay!

xavierleroy · 2020-06-22T17:35:57Z

Re: the "naked_pointers" ocamltest action, I think it would be better to
add it to ocaml_actions rather than to the builtin _actions module
because it is specific to the OCaml compiler. Think of builtin_actions
as actions that could be relevant to otehr contexts than the one of the
OCaml compiler.

I was unaware of this distinction, but I just followed what was already done. The following actions are in builtin_actions:

hasinstrumentedruntime
hasunix
libunix
libwin32unix
hassysthreads
hasstr
windows
not_windows
bsd
not_bsd
macos
arch32
arch64
arch_arm
arch_arm64
arch_power
function_sections
has_symlink

The naked_pointers test is conceptually very similar to hasinstrumentedruntime or function_sections: it's a characteristic of the runtime system.

Also, regarding the text associated with this action, could it be made
clearer?

Again I copied function_sections which says "Target supports function sections". But I'm happy to put "Runtime system supports naked pointers", that's more precise indeed.

It succeeds if the runtime system supports naked pointers, and fails otherwise (e.g. if configured with --disable-naked-pointers).

Part of the test makes sense only if the runtime system supports naked pointers and has a page table to distinguish major heap pointers from out-of-heap pointers. This part is split off in a new test, lib-obj/reachable_words_np.ml, conditionalized on "naked_pointers".

The previous implementation (caml_obj_reachable_words in runtime/obj.c) was using the mark bits of block headers to detect sharing. This is not compatible with Multicore OCaml. This commit reimplements caml_obj_reachable_words to detect sharing with a hash table of addresses already seen. The implementation reuses the hash table used to detect sharing during marshaling (commit 67ada54), and other bits of the marshaler, hence the function caml_obj_reachable_words was moved to runtime/extern.c. In no-naked-pointers mode, to anticipate the disappearance of the page table, statically-allocated blocks cannot be treated specially and will be counted towards the size. This change of semantics is mentioned in the documentation for Obj.reachable_words.

shindere · 2020-06-22T18:13:22Z

Xavier Leroy (2020/06/22 10:36 -0700):

> Re: the "naked_pointers" ocamltest action, I think it would be better to add it to `ocaml_actions` rather than to the `builtin _actions` module because it is specific to the OCaml compiler. Think of `builtin_actions` as actions that could be relevant to otehr contexts than the one of the OCaml compiler. I was unaware of this distinction, but I just followed what was already done. The following actions are in `builtin_actions`: ``` hasinstrumentedruntime hasunix libunix libwin32unix hassysthreads hasstr windows not_windows bsd not_bsd macos arch32 arch64 arch_arm arch_arm64 arch_power function_sections has_symlink ``` The `naked_pointers` test is conceptually very similar to `hasinstrumentedruntime` or `function_sections`: it's a characteristic of the runtime system.

Yeah, some of these seem okay to have here but some others should definitely be moved to ocaml_actions, but that's okay, no need to bother here.

> Also, regarding the text associated with this action, could it be made clearer? Again I copied `function_sections` which says "Target supports function sections". But I'm happy to put "Runtime system supports naked pointers", that's more precise indeed.

I should have complained at the time. :) Is's nice if you don't mind clarifying. Thanks a lot.

xavierleroy added the multicore-prerequisite label Jun 14, 2020

hhugo reviewed Jun 15, 2020

View reviewed changes

xavierleroy mentioned this pull request Jun 15, 2020

Introduce and use an Is_naked_pointer(v) macro in the runtime #9685

Closed

xavierleroy mentioned this pull request Jun 21, 2020

The end of the page table is near #9698

Merged

jhjourdan approved these changes Jun 22, 2020

View reviewed changes

configure: add a NAKED_POINTERS parameter to Makefile.config

41227a1

We have NAKED_POINTERS=false if configured with --disable-naked-pointers, NAKED_POINTERS=true otherwise.

xavierleroy added a commit to xavierleroy/ocaml that referenced this pull request Jun 22, 2020

Changes entry for ocaml#9678

4fce17a

xavierleroy force-pushed the reachable-words branch from a31cbc1 to 4fce17a Compare June 22, 2020 12:24

xavierleroy added 4 commits June 22, 2020 19:37

ocamltest: add the "naked_pointers" action

133102c

It succeeds if the runtime system supports naked pointers, and fails otherwise (e.g. if configured with --disable-naked-pointers).

Changes entry for ocaml#9678

7e4ef62

xavierleroy force-pushed the reachable-words branch from 4fce17a to 7e4ef62 Compare June 22, 2020 17:38

xavierleroy merged commit 607bd8d into ocaml:trunk Jun 23, 2020

xavierleroy deleted the reachable-words branch June 23, 2020 07:53

ctk21 mentioned this pull request Mar 18, 2021

Re-enable lib-obj and asmcomp/is_static tests ocaml-multicore/ocaml-multicore#503

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Reimplement Obj.reachable_word using a hash table to detect sharing #9678

Reimplement Obj.reachable_word using a hash table to detect sharing #9678

xavierleroy commented Jun 14, 2020

hhugo Jun 15, 2020

xavierleroy Jun 15, 2020

hhugo Jun 15, 2020 •

edited

Loading

xavierleroy commented Jun 21, 2020

jhjourdan left a comment

jhjourdan Jun 22, 2020

xavierleroy Jun 22, 2020

xavierleroy commented Jun 22, 2020

shindere commented Jun 22, 2020 via email

shindere commented Jun 22, 2020 via email

xavierleroy commented Jun 22, 2020

shindere commented Jun 22, 2020 via email

Reimplement Obj.reachable_word using a hash table to detect sharing #9678

Reimplement Obj.reachable_word using a hash table to detect sharing #9678

Conversation

xavierleroy commented Jun 14, 2020

hhugo Jun 15, 2020

Choose a reason for hiding this comment

xavierleroy Jun 15, 2020

Choose a reason for hiding this comment

hhugo Jun 15, 2020 • edited Loading

Choose a reason for hiding this comment

xavierleroy commented Jun 21, 2020

jhjourdan left a comment

Choose a reason for hiding this comment

jhjourdan Jun 22, 2020

Choose a reason for hiding this comment

xavierleroy Jun 22, 2020

Choose a reason for hiding this comment

xavierleroy commented Jun 22, 2020

shindere commented Jun 22, 2020 via email

shindere commented Jun 22, 2020 via email

xavierleroy commented Jun 22, 2020

shindere commented Jun 22, 2020 via email

hhugo Jun 15, 2020 •

edited

Loading