-
Notifications
You must be signed in to change notification settings - Fork 1.2k
Avoid tearing in Array.sub #13950
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Avoid tearing in Array.sub #13950
Conversation
|
I wrote an Array.sub microbenchmark (sources). Implementations compared:
On arrays of size 200, when In other words, this PR makes Array.sub 2x slower on small arrays. I think that we should use a |
d42687e to
9a7c0e8
Compare
|
I added an |
The second domain is necessarily spawned from the first domain. Wouldn't the (single) domain lock enforce the synchronization you need? |
|
Re. caml_domain_alone, see #13952 where I documented my reasoning for why this is safe. |
|
I have added a fast path as suggested. |
gasche
left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I'm happy with the current version -- with minor comments.
Co-authored-by: Gabriel Scherer <[email protected]>
52287f0 to
37ea325
Compare
|
The CI failures seem broadly unrelated to this PR.
The The The code of the test, with the initialization, read and publication annotated by myself: let () = Random.self_init ()
let num_domains = 4
let iters = 1_000_000
let len = 10_000
let table = Weak.create len
let go () =
for i = 1 to 1_000_000 do
let s = string_of_int i in (* STRING INITIALIZATION *)
let h = String.hash s mod len in
begin match Weak.get table h with
| None -> ()
| Some s' -> assert (String.hash s' (* CONCURRENT STRING READ *) mod len = h)
end;
Weak.set table h (Some s) (* PUBLICATION *)
done
let () =
let domains = Array.init (num_domains - 1) (fun _ -> Domain.spawn go) in
go ();
Array.iter Domain.join domains;
print_endline "ok"This is unrelated to the present PR but also an issue worth fixing. (I don't understand what needs to be done: maybe we really don't have enough synchronization here, or maybe we need some more opt-out code to teach TSan about our publish-safety assumptions.) |
Avoid tearing in Array.sub (cherry picked from commit 331b5e6)
A few weeks ago, @jmid discovered a type safety bug ocaml-multicore/multicoretests#528 happening when using the Dynarray module in parallel.
It appears that the root cause is probably in
Array.sub, which, in some cases, callsmemcpy. Depending on what assembly instructionsmemcpyis compiled to (which can vary a great deal depending on the platform), the reads fromainArray.sub a ofs lenare not necessarily word-per-word; which, if writes are made toaconcurrently, can cause tearing and fill the new array with garbage values.Closing in on the bug was possible thanks to helpful comments and testing work from @jmid, @gasche and @shym.
The bug was observed when using musl, presumably because
memcpycompiles to different code in that case. But it’s hardly a musl-specific problem. As @shym noted, building OCaml with glibc but withCFLAGS=-Osresults inmemcpycopying data byte-per-byte.Fix details
memcpy, we need to enforce that the source array is read word-wise. To achieve this, I’m using relaxed atomic loads.MaybeI have been proven wrong, see below.memcpycould be used ifcaml_domain_alone ()is true, as is done elsewhere, but I’m not entirely sure that it’s correct: without any synchronisation, it is in principle possible that a second domain is spawned and writes to the aray before the memcpy/memmove is finished. But I’m happy to be proven wrong.