From: tenderlove@... Date: 2019-02-27T22:26:50+00:00 Subject: [ruby-core:91635] [Ruby trunk Feature#15626] Manual Compaction for MRI's GC (`GC.compact`) Issue #15626 has been updated by tenderlovemaking (Aaron Patterson). File after_compact-1.png added File before_compact-1.png added File after_compact-0.png added File before_compact-0.png added I've tested the compactor with a Rails application, and I want to share my results. I added the middleware below: ```ruby # This file is used by Rack-based servers to start the application. require_relative 'config/environment' require 'objspace' $COUNT = 0 class CompactHeap def initialize app @app = app end def call env x = @app.call env GC.start File.open("before_compact-#{$COUNT}.txt", 'w') do |f| ObjectSpace.dump_all(output: f) end GC.compact File.open("after_compact-#{$COUNT}.txt", 'w') do |f| ObjectSpace.dump_all(output: f) end $COUNT += 1 x end end use CompactHeap run Rails.application ``` The above middleware will: 1. Run the web request 2. Run the GC 3. Dump the heap 4. Compact the heap 5. Dump the heap This gives us an idea what the heap looks like after a request, but before and after compaction. I've attached visualizations of the heap for two requests. Each visualization is a PNG file that represents the heap. Each column of the image represents a page in the heap. Columns are two pixels wide. Each square in the column represents a slot. Slots are 2px by 2px squares. Red squares are slots that have an unmovable (pinned) object. Black squares are slots that have a moveable object. Other squares are empty slots. The first image "before-compact-0.png" is before a compaction has ever occurred. You can see there are many unfilled pages. Of the 582 pages, 98 are full, and 484 have empty slots. After compaction "after-compact-0.png", there are 576 pages, 411 full, and 165 have empty slots. Subsequent requests have similar looking heaps to "after-compact-0" (as expected). The program I used to generate these visualizations can be found here: https://gist.githubusercontent.com/tenderlove/578cfb4ce677465d0a8ceb4362928a89/raw/41798db55154b235059f1414a8bb18cd955d1ace/heapviz.rb I'll publish the Rails application I used to generate these graphs and add a link here. :) ---------------------------------------- Feature #15626: Manual Compaction for MRI's GC (`GC.compact`) https://bugs.ruby-lang.org/issues/15626#change-76896 * Author: tenderlovemaking (Aaron Patterson) * Status: Open * Priority: Normal * Assignee: * Target version: ---------------------------------------- Hi, I've attached a patch that implements a compactor for MRI. I'll try to describe the patch in detail below, but the biggest user facing changes are: 1. A new method `GC.compact` that can be called from Ruby 2. C extensions have a new "after compaction" callback they can register 3. Introduction of new marking functions that allow objects to be marked, but not "pinned" to the same location 4. A function to get the new location of an object (to be used from the "after compaction" callback) # Compactor for RGenGC This document describes the compactor implementation for RGenGC. This patch adds a new method to Ruby, `GC.compact` which will compact the objects in the heap. What follows is a description of the algorithm, along with achievements and technical challenges. ## Steps for Compaction These are the high level steps taken in `GC.compact` are as follows: 1. Full GC 2. Move objects 3. Update references 4. Full GC ### Step One, Full GC Not all objects in Ruby's heap can move. In particular, C extensions may hold references to VALUE pointers. If the VALUE pointers move, the C extension may not be able to find them and will get a SEGV or possibly wrong data. To prevent this, a new "pinning" table was introduced. Any object marked via `rb_gc_mark` is "pinned" and is not allowed to move. C extensions must mark their references in order to keep them alive. Since C extensions use `rb_gc_mark` to mark a reference, we know not to move that reference. In order to ensure all references get marked, we perform a full GC. New functions, `rb_gc_mark_no_pin`, etc were introduced and used internally. These functions keeps the object alive but without pinning the reference. Summary: Perform a full GC so that objects marked with `rb_gc_mark` do not move. ### Step Two, Move Objects This compactor uses a "two finger" algorithm which was introduced in "The Programming Language LISP: Its Operation and Applications" (page 228)[^1]. Two pointers point at each side of the heap, if one slot is empty, and the other is moveable, it swaps places and leaves a `T_MOVED` object that contains a forwarding address. In Ruby, the algorithm looks something like this: ```ruby def compact heap = [ ... ] # many slots left = 0 right = heap.length - 1 while left < right left_slot = heap[left] right_slot = heap[right] if is_empty?(left_slot) && !is_empty?(right_slot) && can_move?(right_slot) swap(left, right) heap[right] = T_MOVED.new(left) # leave forwarding address end while !is_empty?(heap[left]) left += 1 end while is_empty?(heap[right]) || !can_move?(heap[right]) right -= 1 end end end ``` If we have a heap with 6 slots, before compaction it might look something like this: ``` ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� Before Compaction ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������������������������������������������� Slot Index ��� 1 ��� 2 ��� 3 ��� 4 ��� 5 ��� 6 ��� ��������������������������������������������������������������������������������������������������������������� Slot Contents ��� A ��� B ���Empty���Empty��� C ��� D ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������������������������������������������� ``` After compaction, but before reference update, it will look like this: ``` ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� After Compaction ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������������������������������������������� Slot Index ��� 1 ��� 2 ��� 3 ��� 4 ��� 5 ��� 6 ��� ��������������������������������������������������������������������������������������������������������������� Slot Contents ��� A ��� B ��� D ��� C ���MOVED���MOVED��� ��� ��� ��� ��� ���TO 4 ���TO 3 ��� ��������������������������������������������������������������������������������������������������������������� ``` Slots 5 and 6 contain `T_MOVED` objects that point to the new locations of D and C objects. ### Step Three, Update References After objects have moved, references are updated. This is a matter of updating any references to use the forwarding address rather than the original location. For example, if object A has a reference to C, and B a reference to D: ``` ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� Before Compaction ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������������������������������������������� Slot Index ��� 1 ��� 2 ��� 3 ��� 4 ��� 5 ��� 6 ��� ��������������������������������������������������������������������������������������������������������������� Slot Contents ��� A ��� B ���Empty���Empty��� C ��� D ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������������������������������������������� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������� ��� ��������������������������������������������������������������������������� ``` After compaction, but before updating references, the heap will look like this: ``` ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� After Compaction ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������������������������������������������� Slot Index ��� 1 ��� 2 ��� 3 ��� 4 ��� 5 ��� 6 ��� ��������������������������������������������������������������������������������������������������������������� Slot Contents ��� A ��� B ��� D ��� C ���MOVED���MOVED��� ��� ��� ��� ��� ���TO 4 ���TO 3 ��� ��������������������������������������������������������������������������������������������������������������� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������� ��� ��������������������������������������������������������������������������� ``` The update references step looks at each object in the heap, checks to see if it references any moved slots, then updates the reference to use the new location. In Ruby, it looks like this: ```ruby def update_references heap.each do |slot| next if is_empty?(slot) || is_moved?(slot) slot.references.each_with_index do |child, i| if is_moved?(child) slot.set_reference(i, child.new_location) end end end end ``` After reference updates, the heap will look like this: ``` ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� After Ref Updates ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������������������������������������������������������������� Slot Index ��� 1 ��� 2 ��� 3 ��� 4 ��� 5 ��� 6 ��� ��������������������������������������������������������������������������������������������������������������� Slot Contents ��� A ��� B ��� D ��� C ���MOVED���MOVED��� ��� ��� ��� ��� ���TO 4 ���TO 3 ��� ��������������������������������������������������������������������������������������������������������������� ��� ��� ��� ��� ��� ��� ��� ��� ��������������������������������������������������������� ��������������������� ``` ### Step Four, Full GC After references have been updated, a full GC is performed. This converts the `T_MOVED` slots back in to `T_EMPTY` slots. The GC automatically takes care of this because no object should reference a `T_MOVED` slot. ## Non Moving Objects Non moving objects are: 1. Objects on the stack 2. Objects marked with `rb_gc_mark` 3. Hash key objects ### Objects on the stack The stack should not be mutated, so these are pinned. ### Objects marked with `rb_gc_mark` As mentioned earlier, any object marked with `rb_gc_mark` may not move because a C extension may hold a reference. Here is an excerpt from Yajl, a JSON parser. This is the mark function it uses: ```c static void yajl_encoder_wrapper_mark(void * wrapper) { yajl_encoder_wrapper * w = wrapper; if (w) { rb_gc_mark(w->on_progress_callback); rb_gc_mark(w->terminator); } } obj = Data_Make_Struct(klass, yajl_encoder_wrapper, yajl_encoder_wrapper_mark, yajl_encoder_wrapper_free, wrapper); ``` The values in this mark function `w->on_progress_callback` and `w->terminator` will not move since they are pinned by `rb_gc_mark`. ### Hash key objects Certain hash keys will not move. Most objects use their address as the hash value. If the object moves, the hash value could change, so hash keys are not allowed to move. There is an exception for string objects. String objects calculate their hash based on the bytes in the string. Since the bytes in the string do not change after move, they are allowed to move. Most hash keys in large programs are strings, so only allowing string keys to move seemed enough. ## Special Considerations ### Object ID `Object#object_id` bases its value from the address of the object. For example: ```ruby x = Object.new id = x.object_id GC.compact # `x` moves id == x.object_id # `id` should be same as `x.object_id` ``` We expect the object id to remain the same regardless of compaction. To deal with `object_id`, two hashes were introduced. One hash contains a map of the object to the *seen* object id. The second map contains all seen object ids. The maps are updated any time `object_id` is called, an object moves, or an object is freed. object_id implementation in Ruby: ```ruby $obj_to_id = {} $id_to_obj = {} class Object def object_id if $obj_to_id.key?(address) # Second call to object_id on this object return $obj_to_id[address] else # First call to object_id on this object addr = self.address loop do if $seen_ids.key?(addr) # Resolve conflict addr += sizeof(RVALUE) else $obj_to_id[self.address] = addr $id_to_obj[addr] = self return addr end end end end private def address # returns address in memory of object end end ``` During compaction: ```ruby def compact heap = [ ... ] # many slots while left < right dest_slot = heap[left] source_slot = heap[right] if moving?(source_slot) if $obj_to_id.key?(source_slot.address) id = $obj_to_id.delete(source_slot.address) $obj_to_id[dest_slot.address] = id $id_to_obj[id] = dest_slot.address end # etc end end end ``` During Free: ```ruby def free(obj) if $obj_to_id.key?(obj.address) $seen_ids.delete($obj_to_id.delete(obj.address)) end end ``` ### ObjectSpace._id2ref When generating an object id, in the case of a collision, the address is incremented by 40. This enables `_id2ref` to determine there is a VALUE pointer and round trip the object correctly. ## Compaction Support for C extensions Any object marked with `rb_gc_mark` will be "pinned" and cannot move. C extensions mark objects via `rb_gc_mark`, so this ensures that pointers in C stay valid. However, some C extensions may want to support reference movement. ### Reference Movement in C extensions In order to maintain backwards compatibility, if a C extension holds a reference to a VALUE, the VALUE should not move. Going forward, C extensions can support moving VALUEs. To support moving VALUEs, a C extension should change `rb_gc_mark` to `rb_gc_mark_no_pin`, then implement a new callback that is called during compaction that gives the extension an opportunity to update its own references. A new function `rb_gc_new_location` will return the new location for a particular VALUE. Here is an example for autoload from `variable.c`. A new compaction callback is registered, `autoload_i_compact`: ```c static const rb_data_type_t autoload_data_i_type = { "autoload_i", {autoload_i_mark, autoload_i_free, autoload_i_memsize, autoload_i_compact}, 0, 0, RUBY_TYPED_FREE_IMMEDIATELY }; ``` The mark function changes to *mark* references, but *not* pin them: ```c static void autoload_i_mark(void *ptr) { struct autoload_data_i *p = ptr; rb_gc_mark_no_pin(p->feature); /* allow GC to free us if no modules refer to this via autoload_const.ad */ if (list_empty(&p->constants)) { rb_hash_delete(autoload_featuremap, p->feature); } } ``` After the heap is compacted, any C extensions that registered a "compaction" callback will be called and have a chance to update internal references. The autoload compaction function is like this: ```c static void autoload_i_compact(void *ptr) { struct autoload_data_i *p = ptr; p->feature = rb_gc_new_location(p->feature); ``` The compaction callback asks for the new location for the `p->feature` reference. `rb_gc_new_location` will either return the current value of `p->feature` (in the case the VALUE did not move), or the new location. ## Reference Verification and Testing After compaction, objects that have moved are changed to `T_MOVED` objects with forwarding addresses. Once all references are updated, no object should point to a `T_MOVED` slot. We can say that before and after compaction, no object should ever point at a `T_MOVED` slot. So if a `T_MOVED` object is ever pushed on to the mark queue, there is a bug. `push_mark_stack` has a check for `T_MOVED` objects, and will crash if a `T_MOVED` object is ever pushed on to the mark stack. A method `GC.verify_compaction_references` was added that doubles the available heap size, then compacts the heap. Since the heap has doubled in size, any object that can move will move. Any references to `T_MOVED` objects will be caught during the GC phase after compaction. ## Known Issue Safety for C extensions depends entirely on C extensions marking their references. If a C extension does not mark a reference, the compactor assumes that the object is safe to move. This can cause an error in the following situation, when there is an object graph like this: ``` ��������������������������������������������������� ��������������������������������������������������� ��� Ruby Object ��� ��� Ruby Object ��� ��� Implemented ��� ��� Implemented ��� ��� in Ruby ��� ��� in C ��� ��� ��� ��� ��� ��������������������������������������������������� ��������������������������������������������������� ��� ��� ��� ��� ��� NOT Marked ��� Marked ��� ��� ��� ��������������������������������������������������� ��� ��� ��� ��� ��� ��� Ruby Object ��� ��������������� ��������� ��� ��� ��� ��������������������������������������������������� ``` If the C extension contains a reference to an object, but expects the object not to move because a Ruby object contains a reference, then the target Ruby object *may* move and the reference in the C extension will be wrong. I like to call these "ghost references" because the GC cannot see them but they will come back to haunt you. The solution to this is either: 1. Change the C extension to `rb_gc_mark` the object 2. Remove the reference from the C extension One example of this situation was fixed here: https://github.com/msgpack/msgpack-ruby/issues/133 ## Summary Backwards compatibility with C extensions is maintained by "pinning" any references marked with `rb_gc_mark`. A full mark *must* be done before compacting to discover all pinned references. A new callback for C extensions is introduced so that C extensions can support compaction. C extensions that wish to support compaction must use the new callback, `rb_gc_mark_no_pin`, and `rb_gc_new_location`. C extensions that maintain pointers but do not mark those pointers may SEGV. We can use `GC.verify_compaction_references` to discover these issues. [^1]: See also "The Garbage Collection Handbook" page 32 ---Files-------------------------------- 0001-Compacting-GC-for-MRI.patch (76.5 KB) before_compact-0.png (111 KB) after_compact-0.png (80.6 KB) before_compact-1.png (81.2 KB) after_compact-1.png (79.4 KB) -- https://bugs.ruby-lang.org/ Unsubscribe: