Add GC.auto_compact / GC.auto_compact=(flag) by tenderlove · Pull Request #3547 · ruby/ruby

tenderlove · 2020-09-15T23:50:19Z

This PR adds support for automatic GC compaction on major collections.

GC.enable_autocompact enables the feature and GC.disable_autocompact disables the feature. The feature is disabled by default.

This patch makes object movement happen at the same time as page sweep. When one page finishes sweeping, that page is filled.

Sweep + Move Phase

During sweep, we keep a pointer to the current sweeping page. This pointer is kept in heap->sweeping_page. At the beginning of sweep, this is the first element of the heap's linked list.

At the same time, the compaction process points at the last page in the heap, and that is stored in heap->compact_cursor here.

Incremental sweeping sweeps one page at a time in the gc_page_sweep function. At the end of that function, we call gc_fill_swept_page. gc_fill_swept_page fills the page that was just swept and moves the movement cursor towards the sweeping cursor.

When the sweeping cursor and the movement cursor meet, sweeping is paused, and references are updated. This can happen in 2 ways, the sweeping cursor "runs in to the moving cursor" which is here. Or the moving cursor runs in to the sweep cursor which happens here.

Either way, the sweep step is paused and references are updated.

Reference Updating

Reference updating hasn't changed, but since reference updating happens before the GC finishes a cycle, it must take in to account garbage objects here.

Read Barrier

During the sweep phase, some objects may touch other objects. For example, T_CLASS must remove itself from a parent class.

class A; end
class B < A; end

const_set(:B, nil)

When B is freed, it must remove itself from A's subclasses. But what if A moved? To fix this, I've introduced a read barrier. The read barrier protects heap_page_body using mprotect. If something tries to read from the page, an exception will occur and we can move all objects back to the page (invalidate the movement).

The lock function is here.
The unlock function is here.

It uses sigaction to catch the exception here.

Cross Platform

mprotect and sigaction are not cross platform, they doesn't work on Windows. On Windows the read barrier uses exception handlers that are built in to Windows. I implemented them here.

The read barrier seems to work on all platforms we're testing.

ioquatix · 2020-09-16T03:43:26Z

Would an interface like GC.autocompact= true/false make more sense? Along with GC.autocompact?

ioquatix · 2020-09-16T03:49:46Z

  def self.compact
-    Primitive.rb_gc_compact
+    Primitive.gc_start_internal true, true, true, true
+    Primitive.gc_compact_stats


Where does Primitive come from? It's a pretty nice interface.

This is new in master. I think ko1 introduced it. I'm very excited about Primitive

So it can invoke C functions?

FWIW it's from https://bugs.ruby-lang.org/issues/16254 + my suggestion to rename to Primitive.name like in TruffleRuby (and similar in Rubinius before that).

ioquatix · 2020-09-16T04:10:08Z

I don't fully understand everything that's going on here but I tried to give some basic feedback. If you want to talk duck to me about it, I'm happy to quack through it with you.

tenderlove · 2020-09-16T18:15:03Z

Would an interface like GC.autocompact= true/false make more sense? Along with GC.autocompact?

Possibly. I'm going to open a ticket on Redmine so we can discuss the interface there.

tenderlove · 2020-09-16T18:40:19Z

I posted a Redmine issue here

This commit eliminates the linked list stored in `T_MOVED` and reuses the pinning bits for eliminating `T_MOVED` slots. Instead of writing to the heap, we can reuse the pinning bits to find `T_MOVED` slots. `gc_move` is updated to pin the source slot. The source slot cannot be marked because no object should hold a reference to a `T_MOVED` address after references are updated. Bit truth table: | Mark Bit | Pin Bit | Slot Identity | | :------- | :------ | :------------ | | On | On | Pinned Object | | On | Off | Marked Object | | Off | Off | Garbage | | Off | On | T_MOVED |

This reverts commit 62ce8f9.

Since we combine compact and sweep the free pointer is probably not empty.

The call cache is a weak map and sometimes it can reference classes which will be collected. In the case it points to a collected class, update the class pointer to 0 (an uninitialized call cache)

Some objects that are protected by write barriers want to pin objects. One example is an identity hash. Identity hash is protected by a write barrier, but the keys to the hash cannot move as they are based on memory location. During incremental marking, if a reference is written to one of these objects, the reference is marked via the write barrier even though the mark function on the object would have marked *and* pinned it. To fix this, we will pin every reference that is marked via incremental marking because we cannot know if the object would have pinned its reference

Checking if T_NONE is marked is kind of an error, so lets just check the mark bits directly

If we don't call the marking function on the object, we need to assume the object must be pinned

This commit runs the compactor on every major GC

Compaction only updates references for "live" objects. But it depends on the "before_sweep" flag on a page to figure out which objects are live. If we're compacting, set the before_sweep flag so we don't try to update references on garbage objects

For example, objects that are in the finalizers table. They will be pinned but not marked. Since that is the case, the read barrier should ensure the type is T_MOVED before moving objects back.

We should only update objects on blocks that have live objects. If the objects are live, they won't have ASAN protection, so we should also remove the ASAN calls in order to catch bugs

Marked objects will not be "remarked" after the write barrier executes. Since we can't know whether or not the object would have pinned the reference that was written, we have to take a conservative approach and pin all references written via the write barrier

T_MOVED objects can get pushed on to the stack right before the final compact step. If this happens, the read barriers will get removed before anything has a chance to read from that address. This commit scans the stack when we finish compaction, looking for any moved addresses that happened to get pushed on the stack. If it finds any, it reverts those moves.

Mutating the object id map can cause the map to resize and that can cause a GC. The GC may read from the object id map *while* the map is being mutated, and that isn't safe. This commit disables the GC when mutating the object id map so that the GC won't see the map in an inconsistent state.

This commit lets us sort the heap by empty slots so that we can pack objects to the empty side of the heap

ioquatix reviewed Sep 16, 2020

View reviewed changes

Comment thread gc.c Outdated

ioquatix reviewed Sep 16, 2020

View reviewed changes

Comment thread gc.c

ioquatix reviewed Sep 16, 2020

View reviewed changes

Comment thread gc.c

tenderlove force-pushed the autocompact branch from 8a4d8fa to af469bc Compare September 16, 2020 17:21

tenderlove force-pushed the autocompact branch 3 times, most recently from 15b31d3 to 361e9f5 Compare September 22, 2020 20:47

tenderlove force-pushed the autocompact branch 4 times, most recently from 2a665b0 to 63abf9d Compare October 2, 2020 19:02

tenderlove force-pushed the autocompact branch from cd9e0ad to 859f673 Compare October 6, 2020 23:24

tenderlove force-pushed the autocompact branch 3 times, most recently from 6f6234a to b7a11b9 Compare October 16, 2020 19:30

tenderlove mentioned this pull request Oct 16, 2020

Enable auto-compaction by default #3316

Draft

tenderlove changed the title ~~Add GC.enable_autocompact / GC.disable_autocompact~~ Add GC.auto_compact / GC.auto_compact=(flag) Oct 16, 2020

tenderlove force-pushed the autocompact branch 4 times, most recently from c60f527 to 7aba46f Compare October 22, 2020 18:20

tenderlove added 4 commits November 2, 2020 09:17

Revert "Revert "Combine sweeping and moving""

22b351b

This reverts commit 62ce8f9.

The free pointer is probably not empty

72cb604

Since we combine compact and sweep the free pointer is probably not empty.

compact pt 2

9156ad0

tenderlove added 25 commits November 2, 2020 09:17

The call cache is a weak map, so clear garbage

15b3f8b

The call cache is a weak map and sometimes it can reference classes which will be collected. In the case it points to a collected class, update the class pointer to 0 (an uninitialized call cache)

cme objects are weak references too, we need to fix thsm

08b22ad

lock vm inside read barrier

c90bae7

We may move objects on to T_NONE

25dd401

Checking if T_NONE is marked is kind of an error, so lets just check the mark bits directly

Both incremental WB branches need to pin the object

a8aa5c0

If we don't call the marking function on the object, we need to assume the object must be pinned

Try compacting on major GC

a564c62

This commit runs the compactor on every major GC

Add autocompact enable / disable flags

7c92052

expose compact info and test it

49c762d

Refactor flags so we only need one

de5efc1

fix indentation

b1eda95

increment compaction count after compaction finishes

c4ef5ff

remove docs

ad3862b

fix ASAN errors

f9fef20

only update the references of live objects

b49db4f

Some objects get pinned but not marked on half-filled pages.

3d8a633

For example, objects that are in the finalizers table. They will be pinned but not marked. Since that is the case, the read barrier should ensure the type is T_MOVED before moving objects back.

add stats about total number of moved objects per compaction

46a3fc7

prevent GC entry when updating generic ivar table

cfff0c9

Only update references on blocks with live objects

fea9b2c

We should only update objects on blocks that have live objects. If the objects are live, they won't have ASAN protection, so we should also remove the ASAN calls in order to catch bugs

rename auto compact methods

fd63ecf

run the build

a4e836c

tenderlove force-pushed the autocompact branch from 7aba46f to a4e836c Compare November 2, 2020 17:17

tenderlove added 3 commits November 2, 2020 12:19

Update NEWS

6c4275e

Fix heap sorting

3dc423d

This commit lets us sort the heap by empty slots so that we can pack objects to the empty side of the heap

double heap size if requested

f599003

tenderlove force-pushed the autocompact branch from fe19215 to f599003 Compare November 2, 2020 21:52

Navigation Menu

Uh oh!

Add GC.auto_compact / GC.auto_compact=(flag) - #3547

Add GC.auto_compact / GC.auto_compact=(flag)#3547
tenderlove wants to merge 61 commits into
ruby:masterfrom
Shopify:autocompact

tenderlove commented Sep 15, 2020 •

edited

Loading

Uh oh!

ioquatix commented Sep 16, 2020 •

edited

Loading

Uh oh!

ioquatix Sep 16, 2020 •

edited

Loading

Uh oh!

tenderlove Sep 16, 2020

Uh oh!

ioquatix Sep 16, 2020

Uh oh!

eregon Sep 16, 2020

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ioquatix commented Sep 16, 2020 •

edited

Loading

Uh oh!

tenderlove commented Sep 16, 2020

Uh oh!

tenderlove commented Sep 16, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Conversation

tenderlove commented Sep 15, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Sweep + Move Phase

Reference Updating

Read Barrier

Cross Platform

Uh oh!

ioquatix commented Sep 16, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ioquatix Sep 16, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tenderlove Sep 16, 2020

Choose a reason for hiding this comment

Uh oh!

ioquatix Sep 16, 2020

Choose a reason for hiding this comment

Uh oh!

eregon Sep 16, 2020

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ioquatix commented Sep 16, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tenderlove commented Sep 16, 2020

Uh oh!

tenderlove commented Sep 16, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

tenderlove commented Sep 15, 2020 •

edited

Loading

ioquatix commented Sep 16, 2020 •

edited

Loading

ioquatix Sep 16, 2020 •

edited

Loading

ioquatix commented Sep 16, 2020 •

edited

Loading