Skip to content
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

Recompacting the heap can segfault with best-fit #9736

Closed
lpw25 opened this issue Jul 3, 2020 · 4 comments
Closed

Recompacting the heap can segfault with best-fit #9736

lpw25 opened this issue Jul 3, 2020 · 4 comments

Comments

@lpw25
Copy link
Contributor

lpw25 commented Jul 3, 2020

When compaction has finished rearranging all the blocks into the earliest chunks, it has to add any left over space in the remaining chunks to the free list. Which it does with the call to caml_make_free_blocks currently on line 423 of compact.c. Whilst not generally guaranteed by calls to this function, historically this would always produce Caml_blue blocks because they could not be merged with anything else around them. With best-fit however, these blocks make now be Caml_white if they are less than 16 words.

Making the new free blocks Caml_white is not normally a problem, because they will only be seen by sweep_slice which does not care about their contents. However, very rarely a "recompaction" is triggered, which immediately does a second compaction. Compaction scans Caml_white blocks looking for pointers to reverse. Since the data in these Caml_white blocks is essentially arbitrary this can easily segfault.

I'm not sure what the best fix is. The blocks going onto the freelist could possibly be given a no scan tag. The compactor could possibly treat Caml_white blocks as free. Either or those seems fine to me, but I'm not confident enough in my knowledge of all the invariants in the GC to make the decision.

@lpw25
Copy link
Contributor Author

lpw25 commented Jul 3, 2020

cc @damiendoligez

@damiendoligez
Copy link
Member

Nice catch, but I don't think it can be triggered on 64-bit. Here's why:

  • recompaction only happens when there is a single heap chunk and "too much" free space (i.e. much more than mandated by the space_overhead parameter).
  • on a 64-bit architecture, the free space will be a single block, much larger than the 16-field limit, so it will be blue.

Still, the bug could trigger on 32-bit. Moreover, I would like to maintain the property that compaction can be done whenever the major GC is idle (i.e. at the end of any sweep phase) and it is broken by this remnant business. I'll submit a PR soon.

@lpw25
Copy link
Contributor Author

lpw25 commented Jul 8, 2020

To be clear, I found this bug by it happening on a 64bit machine. I think that recompaction can happen with more than one heap chunk, and indeed in the case where I saw this bug recompaction was triggered with 3 heap chunks. The small block was not in the large chunk with left-over space but in one of the smaller chunks.

@damiendoligez
Copy link
Member

Oh that's right I didn't think of this case.

@lpw25 lpw25 closed this as completed in 85e4563 Jul 15, 2020
lpw25 added a commit that referenced this issue Jul 15, 2020
The best-fit allocator must prepare the heap for compaction. Fixes #9736
lukemaurer pushed a commit to janestreet/ocaml that referenced this issue Jul 16, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
damiendoligez added a commit that referenced this issue Jul 17, 2020
damiendoligez added a commit that referenced this issue Jul 17, 2020
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 3, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 4, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 5, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 7, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 10, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 10, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 17, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 18, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 19, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 20, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Aug 28, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Sep 2, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Sep 2, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Sep 2, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
mshinwell pushed a commit to mshinwell/ocaml that referenced this issue Sep 7, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
gretay-js pushed a commit to gretay-js/ocaml that referenced this issue Sep 29, 2020
The best-fit allocator must prepare the heap for compaction. Fixes ocaml#9736
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants