ruby-changes:66425
From: Aaron <ko1@a...>
Date: Fri, 4 Jun 2021 05:57:17 +0900 (JST)
Subject: [ruby-changes:66425] 38c5f2737f (master): Support an arbitrary number of header bits (< BITS_BITLENGTH)
https://git.ruby-lang.org/ruby.git/commit/?id=38c5f2737f From 38c5f2737f8a62efce93595c8b6c6ea1d6b5e739 Mon Sep 17 00:00:00 2001 From: Aaron Patterson <tenderlove@r...> Date: Tue, 1 Jun 2021 16:28:35 -0700 Subject: Support an arbitrary number of header bits (< BITS_BITLENGTH) NUM_IN_PAGE(page->start) will sometimes return a 0 or a 1 depending on how the alignment of the 40 byte slots work out. This commit uses the NUM_IN_PAGE function to shift the bitmap down on the first bitmap plane. Iterating on the first bitmap plane is "special", but this commit allows us to align object addresses on something besides 40 bytes, and also eliminates the need to fill guard bits. --- gc.c | 555 ++++++++++++++++++++++++++++++++++++++----------------------------- 1 file changed, 312 insertions(+), 243 deletions(-) diff --git a/gc.c b/gc.c index 18d4f32..892449f 100644 --- a/gc.c +++ b/gc.c @@ -5191,92 +5191,224 @@ gc_compact_finish(rb_objspace_t *objspace, rb_heap_t *heap) https://github.com/ruby/ruby/blob/trunk/gc.c#L5191 objspace->flags.during_compacting = FALSE; } +struct gc_sweep_context { + struct heap_page *page; + int final_slots; + int freed_slots; + int empty_slots; +}; + +static inline void +gc_fill_swept_page_plane(rb_objspace_t *objspace, rb_heap_t *heap, intptr_t p, bits_t bitset, bool * finished_compacting, struct gc_sweep_context *ctx) +{ + struct heap_page * sweep_page = ctx->page; + + if (bitset) { + do { + if (bitset & 1) { + VALUE dest = (VALUE)p; + + GC_ASSERT(MARKED_IN_BITMAP(GET_HEAP_PINNED_BITS(dest), dest)); + GC_ASSERT(!MARKED_IN_BITMAP(GET_HEAP_MARK_BITS(dest), dest)); + + CLEAR_IN_BITMAP(GET_HEAP_PINNED_BITS(dest), dest); + + if (*finished_compacting) { + if (BUILTIN_TYPE(dest) == T_NONE) { + ctx->empty_slots++; + } + else { + ctx->freed_slots++; + } + (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)dest, sizeof(RVALUE)); + heap_page_add_freeobj(objspace, sweep_page, dest); + } + else { + /* Zombie slots don't get marked, but we can't reuse + * their memory until they have their finalizers run.*/ + if (BUILTIN_TYPE(dest) != T_ZOMBIE) { + if(!try_move(objspace, heap, sweep_page, dest)) { + *finished_compacting = true; + (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE)); + gc_report(5, objspace, "Quit compacting, couldn't find an object to move\n"); + if (BUILTIN_TYPE(dest) == T_NONE) { + ctx->empty_slots++; + } + else { + ctx->freed_slots++; + } + heap_page_add_freeobj(objspace, sweep_page, dest); + gc_report(3, objspace, "page_sweep: %s is added to freelist\n", obj_info(dest)); + } + else { + //moved_slots++; + } + } + } + } + p += sizeof(RVALUE); + bitset >>= 1; + } while (bitset); + } +} + static bool -gc_fill_swept_page(rb_objspace_t *objspace, rb_heap_t *heap, struct heap_page *sweep_page, int *freed_slots, int *empty_slots) +gc_fill_swept_page(rb_objspace_t *objspace, rb_heap_t *heap, struct heap_page *sweep_page, struct gc_sweep_context *ctx) { /* Find any pinned but not marked objects and try to fill those slots */ - int i; - int moved_slots = 0; bool finished_compacting = false; bits_t *mark_bits, *pin_bits; bits_t bitset; - RVALUE *p, *offset; + RVALUE *p; mark_bits = sweep_page->mark_bits; pin_bits = sweep_page->pinned_bits; p = sweep_page->start; - offset = p - NUM_IN_PAGE(p); struct heap_page * cursor = heap->compact_cursor; unlock_page_body(objspace, GET_PAGE_BODY(cursor->start)); - for (i=0; i < HEAP_PAGE_BITMAP_LIMIT; i++) { + /* *Want to move* objects are pinned but not marked. */ + bitset = pin_bits[0] & ~mark_bits[0]; + bitset >>= NUM_IN_PAGE(p); // Skip header / dead space bits + gc_fill_swept_page_plane(objspace ,heap, (intptr_t)p, bitset, &finished_compacting, ctx); + p += (BITS_BITLENGTH - NUM_IN_PAGE(p)); + + for (int i = 1; i < HEAP_PAGE_BITMAP_LIMIT; i++) { /* *Want to move* objects are pinned but not marked. */ bitset = pin_bits[i] & ~mark_bits[i]; + gc_fill_swept_page_plane(objspace ,heap, (intptr_t)p, bitset, &finished_compacting, ctx); + p += BITS_BITLENGTH; + } - if (bitset) { - p = offset + i * BITS_BITLENGTH; - do { - if (bitset & 1) { - VALUE dest = (VALUE)p; + lock_page_body(objspace, GET_PAGE_BODY(heap->compact_cursor->start)); - GC_ASSERT(MARKED_IN_BITMAP(GET_HEAP_PINNED_BITS(dest), dest)); - GC_ASSERT(!MARKED_IN_BITMAP(GET_HEAP_MARK_BITS(dest), dest)); + return finished_compacting; +} - CLEAR_IN_BITMAP(GET_HEAP_PINNED_BITS(dest), dest); +static inline void +gc_plane_sweep(rb_objspace_t *objspace, rb_heap_t *heap, intptr_t p, bits_t bitset, struct gc_sweep_context *ctx) +{ + struct heap_page * sweep_page = ctx->page; - if (finished_compacting) { - if (BUILTIN_TYPE(dest) == T_NONE) { - (*empty_slots)++; + do { + VALUE vp = (VALUE)p; + asan_unpoison_object(vp, false); + if (bitset & 1) { + switch (BUILTIN_TYPE(vp)) { + default: /* majority case */ + gc_report(2, objspace, "page_sweep: free %p\n", (void *)p); +#if RGENGC_CHECK_MODE + if (!is_full_marking(objspace)) { + if (RVALUE_OLD_P(vp)) rb_bug("page_sweep: %p - old while minor GC.", (void *)p); + if (rgengc_remembered_sweep(objspace, vp)) rb_bug("page_sweep: %p - remembered.", (void *)p); + } +#endif + if (obj_free(objspace, vp)) { + ctx->final_slots++; + } + else { + if (heap->compact_cursor) { + /* We *want* to fill this slot */ + MARK_IN_BITMAP(GET_HEAP_PINNED_BITS(vp), vp); } else { - (*freed_slots)++; + (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE)); + heap_page_add_freeobj(objspace, sweep_page, vp); + gc_report(3, objspace, "page_sweep: %s is added to freelist\n", obj_info(vp)); + ctx->freed_slots++; + } + + } + break; + + /* minor cases */ + case T_PAYLOAD: + { + int plen = RPAYLOAD_LEN(vp); + ctx->freed_slots += plen; + + (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)vp, sizeof(RVALUE)); + heap_page_add_freeobj(objspace, sweep_page, vp); + + // This loop causes slots *following this slot* to be marked as + // T_NONE. On the next iteration of this sweep loop, the T_NONE slots + // can be double counted. Mutating the bit plane is difficult because it's + // copied to a local variable. So we would need special logic to mutate + // local bitmap plane (stored in `bitset`) plane, versus T_PAYLOAD objects that span + // bitplanes. (Imagine a T_PAYLOAD at positions 0-3 versus positions 62-65, + // their mark bits would be on different planes. We would have to mutate only `bitset` + // for the first case, but `bitset` and `bits[i+1]` for the second + for (int i = 1; i < plen; i++) { + VALUE pbody = vp + i * sizeof(RVALUE); + + (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)pbody, sizeof(RVALUE)); + heap_page_add_freeobj(objspace, sweep_page, pbody); + + // Lets set a bit on the object so that the T_NONE branch + // will know to avoid double counting this slot. + FL_SET(pbody, FL_FROM_PAYLOAD); } - (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)dest, sizeof(RVALUE)); - heap_page_add_freeobj(objspace, sweep_page, dest); + } + break; + case T_MOVED: + if (objspace->flags.during_compacting) { + /* The sweep cursor shouldn't have made it to any + * T_MOVED slots while the compact flag is enabled. + * The sweep cursor and compact cursor move in + * opposite directions, and when they meet references will + * get updated and "during_compacting" should get disabled */ + rb_bug("T_MOVED shouldn't be seen until compaction is finished\n"); + } + gc_report(3, objspace, "page_sweep: %s is added to freelist\n", obj_info(vp)); + if (FL_TEST(vp, FL_FROM_FREELIST)) { + ctx->empty_slots++; (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/