ruby-changes:31309
From: ko1 <ko1@a...>
Date: Tue, 22 Oct 2013 19:28:37 +0900 (JST)
Subject: [ruby-changes:31309] ko1:r43388 (trunk): * gc.c: allow multiple heaps.
ko1 2013-10-22 19:28:31 +0900 (Tue, 22 Oct 2013) New Revision: 43388 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=43388 Log: * gc.c: allow multiple heaps. Now, objects are managed by page. And a set of pages is called heap. This commit supports multiple heaps in the object space. * Functions heap_* and rb_heap_t manages heap data structure. * Functions heap_page_* and struct heap_page manage page data strcuture. * Functions heap_pagse_* and struct rb_objspace_t::heap_pages maintains all pages. For example, pagaes are allocated from the heap_pages. See https://bugs.ruby-lang.org/projects/ruby-trunk/wiki/GC_design and https://bugs.ruby-lang.org/attachments/4015/data-heap_structure_with_multiple_heaps.png for more deitals. Now, there is only one heap called `eden', which is a space for all new generated objects. Modified files: trunk/ChangeLog trunk/gc.c Index: ChangeLog =================================================================== --- ChangeLog (revision 43387) +++ ChangeLog (revision 43388) @@ -1,3 +1,23 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Tue Oct 22 19:19:05 2013 Koichi Sasada <ko1@a...> + + * gc.c: allow multiple heaps. + Now, objects are managed by page. And a set of pages is called heap. + This commit supports multiple heaps in the object space. + + * Functions heap_* and rb_heap_t manages heap data structure. + * Functions heap_page_* and struct heap_page manage page data + strcuture. + * Functions heap_pagse_* and struct rb_objspace_t::heap_pages + maintains all pages. + For example, pagaes are allocated from the heap_pages. + + See https://bugs.ruby-lang.org/projects/ruby-trunk/wiki/GC_design + and https://bugs.ruby-lang.org/attachments/4015/data-heap_structure_with_multiple_heaps.png + for more deitals. + + Now, there is only one heap called `eden', which is a space for all + new generated objects. + Tue Oct 22 18:26:12 2013 Tanaka Akira <akr@f...> * lib/pp.rb (object_address_group): Use Kernel#to_s to obtain the class Index: gc.c =================================================================== --- gc.c (revision 43387) +++ gc.c (revision 43388) @@ -318,20 +318,14 @@ typedef struct mark_stack { https://github.com/ruby/ruby/blob/trunk/gc.c#L318 size_t unused_cache_size; } mark_stack_t; -struct heap { +typedef struct rb_heap_struct { struct heap_page *pages; struct heap_page *free_pages; struct heap_page *using_page; struct heap_page *sweep_pages; - size_t used; - size_t length; - size_t increment; - size_t limit; - size_t swept_num; - size_t free_min; - size_t final_num; - size_t do_heap_free; -}; + RVALUE *freelist; + size_t used; /* total page count in a heap */ +} rb_heap_t; typedef struct rb_objspace { struct { @@ -343,9 +337,24 @@ typedef struct rb_objspace { https://github.com/ruby/ruby/blob/trunk/gc.c#L337 #endif } malloc_params; - struct heap heap; - struct heap_page **heap_sorted_pages; - RVALUE *heap_range[2]; + rb_heap_t eden_heap; + + struct { + struct heap_page **sorted; + size_t used; + size_t length; + size_t increment; + RVALUE *range[2]; + + size_t limit; + size_t swept_num; + size_t free_min; + size_t do_heap_free; + + /* final */ + size_t final_num; + RVALUE *deferred_final; + } heap_pages; struct { int dont_gc; @@ -353,10 +362,7 @@ typedef struct rb_objspace { https://github.com/ruby/ruby/blob/trunk/gc.c#L362 int during_gc; rb_atomic_t finalizing; } flags; - struct { - st_table *table; - RVALUE *deferred; - } final; + st_table *finalizer_table; mark_stack_t mark_stack; struct { int run; @@ -403,7 +409,6 @@ typedef struct rb_objspace { https://github.com/ruby/ruby/blob/trunk/gc.c#L409 size_t total_freed_object_num; rb_event_flag_t hook_events; /* this place may be affinity with memory cache */ VALUE gc_stress; - RVALUE *freelist; struct mark_func_data_struct { void *data; @@ -499,19 +504,23 @@ VALUE *ruby_initial_gc_stress_ptr = &rb_ https://github.com/ruby/ruby/blob/trunk/gc.c#L504 #define malloc_limit objspace->malloc_params.limit #define malloc_increase objspace->malloc_params.increase #define malloc_allocated_size objspace->malloc_params.allocated_size -#define heap_pages objspace->heap.pages -#define heap_length objspace->heap.length -#define heap_used objspace->heap.used -#define heap_limit objspace->heap.limit -#define heap_sorted_pages objspace->heap_sorted_pages -#define heap_lomem objspace->heap_range[0] -#define heap_himem objspace->heap_range[1] -#define heap_inc objspace->heap.increment +#define heap_pages_sorted objspace->heap_pages.sorted +#define heap_pages_used objspace->heap_pages.used +#define heap_pages_length objspace->heap_pages.length +#define heap_pages_increment objspace->heap_pages.increment +#define heap_pages_lomem objspace->heap_pages.range[0] +#define heap_pages_himem objspace->heap_pages.range[1] +#define heap_pages_limit objspace->heap_pages.limit +#define heap_pages_swept_num objspace->heap_pages.swept_num +#define heap_pages_free_min objspace->heap_pages.free_min +#define heap_pages_do_heap_free objspace->heap_pages.do_heap_free +#define heap_pages_final_num objspace->heap_pages.final_num +#define heap_pages_deferred_final objspace->heap_pages.deferred_final +#define heap_eden (&objspace->eden_heap) #define dont_gc objspace->flags.dont_gc #define during_gc objspace->flags.during_gc #define finalizing objspace->flags.finalizing -#define finalizer_table objspace->final.table -#define deferred_final_list objspace->final.deferred +#define finalizer_table objspace->finalizer_table #define global_List objspace->global_list #define ruby_gc_stress objspace->gc_stress #define monitor_level objspace->rgengc.monitor_level @@ -524,8 +533,7 @@ VALUE *ruby_initial_gc_stress_ptr = &rb_ https://github.com/ruby/ruby/blob/trunk/gc.c#L533 #define initial_free_min initial_params.initial_free_min #define initial_growth_factor initial_params.initial_growth_factor -#define is_lazy_sweeping(objspace) ((objspace)->heap.sweep_pages != 0) - +#define is_lazy_sweeping(heap) ((heap)->sweep_pages != 0) #if SIZEOF_LONG == SIZEOF_VOIDP # define nonspecial_obj_id(obj) (VALUE)((SIGNED_VALUE)(obj)|FIXNUM_FLAG) # define obj_id_to_ref(objid) ((objid) ^ FIXNUM_FLAG) /* unset FIXNUM_FLAG */ @@ -551,7 +559,6 @@ static void rb_objspace_call_finalizer(r https://github.com/ruby/ruby/blob/trunk/gc.c#L559 static VALUE define_final0(VALUE obj, VALUE block); VALUE rb_define_final(VALUE obj, VALUE block); VALUE rb_undefine_final(VALUE obj); -static void run_final(rb_objspace_t *objspace, VALUE obj); static void negative_size_allocation_error(const char *); static void *aligned_malloc(size_t, size_t); @@ -561,10 +568,12 @@ static void init_mark_stack(mark_stack_t https://github.com/ruby/ruby/blob/trunk/gc.c#L568 static VALUE lazy_sweep_enable(void); static int ready_to_gc(rb_objspace_t *objspace); +static int heap_ready_to_gc(rb_objspace_t *objspace, rb_heap_t *heap); static int garbage_collect(rb_objspace_t *, int full_mark, int immediate_sweep, int reason); static int garbage_collect_body(rb_objspace_t *, int full_mark, int immediate_sweep, int reason); -static int gc_lazy_sweep(rb_objspace_t *objspace); +static int gc_heap_lazy_sweep(rb_objspace_t *objspace, rb_heap_t *heap); static void gc_rest_sweep(rb_objspace_t *objspace); +static void gc_heap_rest_sweep(rb_objspace_t *objspace, rb_heap_t *heap); static void gc_mark_stacked_objects(rb_objspace_t *); static void gc_mark(rb_objspace_t *objspace, VALUE ptr); @@ -592,8 +601,8 @@ static const char *obj_type_name(VALUE o https://github.com/ruby/ruby/blob/trunk/gc.c#L601 #if USE_RGENGC static int rgengc_remembered(rb_objspace_t *objspace, VALUE obj); static int rgengc_remember(rb_objspace_t *objspace, VALUE obj); -static void rgengc_mark_and_rememberset_clear(rb_objspace_t *objspace); -static void rgengc_rememberset_mark(rb_objspace_t *objspace); +static void rgengc_mark_and_rememberset_clear(rb_objspace_t *objspace, rb_heap_t *heap); +static void rgengc_rememberset_mark(rb_objspace_t *objspace, rb_heap_t *heap); #define FL_TEST2(x,f) ((RGENGC_CHECK_MODE && SPECIAL_CONST_P(x)) ? (rb_bug("FL_TEST2: SPECIAL_CONST"), 0) : FL_TEST_RAW((x),(f)) != 0) #define FL_SET2(x,f) do {if (RGENGC_CHECK_MODE && SPECIAL_CONST_P(x)) rb_bug("FL_SET2: SPECIAL_CONST"); RBASIC(x)->flags |= (f);} while (0) @@ -646,12 +655,11 @@ RVALUE_PROMOTE(VALUE obj) https://github.com/ruby/ruby/blob/trunk/gc.c#L655 } static inline int -is_before_sweep(VALUE obj) +heap_is_before_sweep(VALUE obj, rb_heap_t *heap) { struct heap_page *page; - rb_objspace_t *objspace = &rb_objspace; - if (is_lazy_sweeping(objspace)) { - page = objspace->heap.sweep_pages; + if (is_lazy_sweeping(heap)) { + page = heap->sweep_pages; while (page) { if (page->body == GET_PAGE_BODY(obj)) { return TRUE; @@ -662,6 +670,13 @@ is_before_sweep(VALUE obj) https://github.com/ruby/ruby/blob/trunk/gc.c#L670 return FALSE; } +static inline int +is_before_sweep(VALUE obj) +{ + rb_objspace_t *objspace = &rb_objspace; + return heap_is_before_sweep(obj, heap_eden); +} + static inline void RVALUE_DEMOTE(VALUE obj) { @@ -701,6 +716,7 @@ rb_objspace_free(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L716 free(objspace->profile.records); objspace->profile.records = 0; } + if (global_List) { struct gc_list *list, *next; for (list = global_List; list; list = next) { @@ -708,15 +724,20 @@ rb_objspace_free(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L724 xfree(list); } } - if (heap_sorted_pages) { + if (heap_pages_sorted) { size_t i; - for (i = 0; i < heap_used; ++i) { - free_heap_page(objspace, heap_sorted_pages[i]); + for (i = 0; i < heap_pages_used; ++i) { + free_heap_page(objspace, heap_pages_sorted[i]); } - free(heap_sorted_pages); - heap_used = 0; - heap_limit = 0; - heap_pages = 0; + free(heap_pages_sorted); + heap_pages_used = 0; + heap_pages_length = 0; + heap_pages_lomem = 0; + heap_pages_himem = 0; + heap_pages_limit = 0; + + objspace->eden_heap.used = 0; + objspace->eden_heap.pages = 0; } free_stack_chunks(&objspace->mark_stack); free(objspace); @@ -724,24 +745,28 @@ rb_objspace_free(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L745 #endif static void -heap_allocate_sorted_array(rb_objspace_t *objspace, size_t next_heap_length) +heap_pages_expand_sorted(rb_objspace_t *objspace, size_t next_used_limit) { - struct heap_page **p; - size_t size; + if (next_used_limit > heap_pages_length) { + struct heap_page **sorted; + size_t size = next_used_limit * sizeof(struct heap_page *); - size = next_heap_length * sizeof(struct heap_page *); + rgengc_report(3, objspace, "heap_pages_expand_sorted: next_used_limit: %d, size: %d\n", (int)next_used_limit, (int)size); - if (heap_used > 0) { - p = (struct heap_page **)realloc(heap_sorted_pages, size); - if (p) heap_sorted_pages = p; - } - else { - p = heap_sorted_pages = (struct heap_page **)malloc(size); - } + if (heap_pages_length > 0) { + sorted = (struct heap_page **)realloc(heap_pages_sorted, size); + if (sorted) heap_pages_sorted = sorted; + } + else { + sorted = heap_pages_sorted = (struct heap_page **)malloc(size); + } - if (p == 0) { - during_gc = 0; - rb_memerror(); + if (sorted == 0) { + during_gc = 0; + rb_memerror(); + } + + heap_pages_length = next_used_limit; } } @@ -756,19 +781,19 @@ heap_page_add_freeobj(rb_objspace_t *obj https://github.com/ruby/ruby/blob/trunk/gc.c#L781 } static inline void -heap_add_freepage(rb_objspace_t *objspace, struct heap_page *page) +heap_add_freepage(rb_objspace_t *objspace, rb_heap_t *heap, struct heap_page *page) { if (page->freelist) { - page->free_next = objspace->heap.free_pages; - objspace->heap.free_pages = page; + page->free_next = heap->free_pages; + heap->free_pages = page; } } -static void -heap_assign_page(rb_objspace_t *objspace) +static struct heap_page * +heap_page_allocate(rb_objspace_t *objspace) { - RVALUE *start, *end, *p; struct heap_page *page; + RVALUE *start, *end, *p; struct heap_page_body *page_body = 0; size_t hi, lo, mid; size_t limit = HEAP_OBJ_LIMIT; @@ -791,10 +816,6 @@ heap_assign_page(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L816 page->body = page_body; - page->next = objspace->heap.pages; - if (objspace->heap.pages) objspace->heap.pages->prev = page; - objspace->heap.pages = page; - /* adjust obj_limit (object number available in this page) */ start = (RVALUE*)((VALUE)page_body + sizeof(struct heap_page_header)); if ((VALUE)start % sizeof(RVALUE) != 0) { @@ -804,14 +825,14 @@ heap_assign_page(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L825 } end = start + limit; - /* setup heap_sorted_pages */ + /* setup heap_pages_sorted */ lo = 0; - hi = heap_used; + hi = heap_pages_used; while (lo < hi) { struct heap_page *mid_page; mid = (lo + hi) / 2; - mid_page = heap_sorted_pages[mid]; + mid_page = heap_pages_sorted[mid]; if (mid_page->body < page_body) { lo = mid + 1; } @@ -822,51 +843,60 @@ heap_assign_page(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L843 rb_bug("same heap page is allocated: %p at %"PRIuVALUE, (void *)page_body, (VALUE)mid); } } - if (hi < heap_used) { - MEMMOVE(&heap_sorted_pages[hi+1], &heap_sorted_pages[hi], struct heap_page_header*, heap_used - hi); + if (hi < heap_pages_used) { + MEMMOVE(&heap_pages_sorted[hi+1], &heap_pages_sorted[hi], struct heap_page_header*, heap_pages_used - hi); } + if (heap_pages_lomem == 0 || heap_pages_lomem > start) heap_pages_lomem = start; + if (heap_pages_himem < end) heap_pages_himem = end; + + heap_pages_limit += limit; + heap_pages_used++; + assert(heap_pages_used <= heap_pages_length); - /* setup page */ page->start = start; page->limit = limit; - page_body->header.page = heap_sorted_pages[hi] = page; - - if (heap_lomem == 0 || heap_lomem > start) heap_lomem = start; - if (heap_himem < end) heap_himem = end; - heap_used++; - heap_limit += limit; + page_body->header.page = heap_pages_sorted[hi] = page; for (p = start; p != end; p++) { rgengc_report(3, objspace, "assign_heap_page: %p is added to freelist\n"); heap_page_add_freeobj(objspace, page, (VALUE)p); } - heap_add_freepage(objspace, page); + return page; +} + +static void +heap_assign_page(rb_objspace_t *objspace, rb_heap_t *heap) +{ + struct heap_page *page = heap_page_allocate(objspace); + + page->next = heap->pages; + if (heap->pages) heap->pages->prev = page; + heap->pages = page; + heap->used++; + + heap_add_freepage(objspace, heap, page); } static void -heap_add_pages(rb_objspace_t *objspace, size_t add) +heap_add_pages(rb_objspace_t *objspace, rb_heap_t *heap, size_t add) { size_t i; - size_t next_heap_length; - next_heap_length = heap_used + add; - - if (next_heap_length > heap_length) { - heap_allocate_sorted_array(objspace, next_heap_length); - heap_length = next_heap_length; - } + heap_pages_expand_sorted(objspace, heap_pages_used + add); for (i = 0; i < add; i++) { - heap_assign_page(objspace); + heap_assign_page(objspace, heap); } - heap_inc = 0; + + heap_pages_increment = 0; } static void -heap_init(rb_objspace_t *objspace) +heap_pages_init(rb_objspace_t *objspace) { - heap_add_pages(objspace, initial_heap_min_slots / HEAP_OBJ_LIMIT); + heap_add_pages(objspace, heap_eden, initial_heap_min_slots / HEAP_OBJ_LIMIT); + init_mark_stack(&objspace->mark_stack); #ifdef USE_SIGALTSTACK @@ -884,55 +914,45 @@ heap_init(rb_objspace_t *objspace) https://github.com/ruby/ruby/blob/trunk/gc.c#L914 } static void -heap_set_increment(rb_objspace_t *objspace) +heap_pages_set_increment(rb_objspace_t *objspace) { - size_t next_heap_length = (size_t)(heap_used * initial_growth_factor); - - if (next_heap_length == heap_used) { - next_heap_length++; - } + size_t next_used_limit = (size_t)(heap_pages_used * initial_growth_factor); + if (next_used_limit == heap_pages_used) next_used_limit++; + heap_pages_increment = next_used_limit - heap_pages_used; + heap_pages_expand_sorted(objspace, next_used_limit); - heap_inc = next_heap_length - heap_used; - - rgengc_report(5, objspace, "heap_set_increment: heap_length: %d, next_heap_length: %d, heap_inc: %d\n", - heap_length, next_heap_length, heap_inc); - - if (next_heap_length > heap_length) { - heap_allocate_sorted_array(objspace, next_heap_length); - heap_length = next_heap_length; - } + rgengc_report(5, objspace, "heap_pages_set_increment: length: %d, next_used_limit: %d\n", (int)heap_pages_length, (int)next_used_limit); } static int -heap_increment(rb_objspace_t *objspace) +heap_increment(rb_objspace_t *objspace, rb_heap_t *heap) { - rgengc_report(5, objspace, "heap_increment: heap_inc: %d\n", heap_inc); + rgengc_report(5, objspace, "heap_increment: length: %d, used: %d, inc: %d\n", (int)heap_pages_length, (int)heap_pages_used, (int)heap_pages_increment); - if (heap_inc > 0) { - heap_assign_page(objspace); - heap_inc--; + if (heap_pages_increment > 0) { + heap_pages_increment--; + heap_assign_page(objspace, heap); return TRUE; } return FALSE; } static struct heap_page * -heap_prepare_freepage(rb_objspace_t *objspace) +heap_prepare_freepage(rb_objspace_t *objspace, rb_heap_t *heap) { if (!GC_ENABLE_LAZY_SWEEP && objspace->flags.dont_lazy_sweep) { - if (heap_increment(objspace) == 0 && + if (heap_increment(objspace, heap) == 0 && garbage_collect(objspace, FALSE, TRUE, GPR_FLAG_NEWOBJ) == 0) { goto err; } goto ok; } - if (!ready_to_gc(objspace)) return objspace->heap.free_pages; + if (!heap_ready_to_gc(objspace, heap)) return heap->free_pages; during_gc++; - if ((is_lazy_sweeping(objspace) && gc_lazy_sweep(objspace)) || - heap_increment(objspace)) { + if ((is_lazy_sweeping(heap) && gc_heap_lazy_sweep(objspace, heap)) || heap_increment(objspace, heap)) { goto ok; } @@ -947,35 +967,35 @@ heap_prepare_freepage(rb_objspace_t *obj https://github.com/ruby/ruby/blob/trunk/gc.c#L967 } ok: during_gc = 0; - return objspace->heap.free_pages; + return heap->free_pages; } static inline struct heap_page * -heap_get_freepage(rb_objspace_t *objspace) +heap_get_freepage(rb_objspace_t *objspace, rb_heap_t *heap) { struct heap_page *page; - page = objspace->heap.free_pages; + page = heap->free_pages; while (page == NULL) { - page = heap_prepare_freepage(objspace); + page = heap_prepare_freepage(objspace, heap); } - objspace->heap.free_pages = page->free_next; + heap->free_pages = page->free_next; return page; } static inline VALUE -heap_get_freeobj(rb_objspace_t *objspace) +heap_get_freeobj(rb_objspace_t *objspace, rb_heap_t *heap) { - RVALUE *p = objspace->freelist; + RVALUE *p = heap->freelist; while (UNLIKELY(p == NULL)) { - struct heap_page *page = heap_get_freepage(objspace); - objspace->heap.using_page = page; - p = objspace->freelist = page->freelist; + struct heap_page *page = heap_get_freepage(objspace, heap); + heap->using_page = page; + p = heap->freelist = page->freelist; page->freelist = NULL; } - objspace->freelist = p->as.free.next; + heap->freelist = p->as.free.next; return (VALUE)p; } @@ -1019,7 +1039,7 @@ newobj_of(VALUE klass, VALUE flags, VALU https://github.com/ruby/ruby/blob/trunk/gc.c#L1039 } } - obj = heap_get_freeobj(objspace); + obj = heap_get_freeobj(objspace, heap_eden); /* OBJSETUP */ RBASIC(obj)->flags = flags; @@ -1126,15 +1146,15 @@ is_pointer_to_heap(rb_objspace_t *objspa https://github.com/ruby/ruby/blob/trunk/gc.c#L1146 register struct heap_page *page; register size_t hi, lo, mid; - if (p < heap_lomem || p > heap_himem) return FALSE; + if (p < heap_pages_lomem || p > heap_pages_himem) return FALSE; if ((VALUE)p % sizeof(RVALUE) != 0) return FALSE; /* check if p looks like a pointer using bsearch*/ lo = 0; - hi = heap_used; + hi = heap_pages_used; while (lo < hi) { mid = (lo + hi) / 2; - page = heap_sorted_pages[mid]; + page = heap_pages_sorted[mid]; if (page->start <= p) { if (p (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/
