ruby-changes:29969
From: ko1 <ko1@a...>
Date: Wed, 17 Jul 2013 14:55:50 +0900 (JST)
Subject: [ruby-changes:29969] ko1:r42021 (trunk): * gc.c: re-design the heap structure.
ko1 2013-07-17 14:55:39 +0900 (Wed, 17 Jul 2013) New Revision: 42021 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42021 Log: * gc.c: re-design the heap structure. (1) The heap is consists of a set of slots. (2) Each "slot" has a "slot_body". slot::start and slot::limit specify RVALUE beginning address and number of RVALUE in a "slot_body". (3) "slot_body" contains a pointer to slot (slot_body::header::slot) and an array of RVALUE. (4) heap::sorted is an array of "slots", sorted by an address of slot::body. See https://bugs.ruby-lang.org/projects/ruby-trunk/wiki/GC_design for more details (figure). * gc.c: Avoid "heaps" terminology. It is ambiguous. Modified files: trunk/ChangeLog trunk/gc.c Index: ChangeLog =================================================================== --- ChangeLog (revision 42020) +++ ChangeLog (revision 42021) @@ -1,3 +1,21 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Wed Jul 17 14:31:13 2013 Koichi Sasada <ko1@a...> + + * gc.c: re-design the heap structure. + + (1) The heap is consists of a set of slots. + (2) Each "slot" has a "slot_body". + slot::start and slot::limit specify RVALUE beginning address + and number of RVALUE in a "slot_body". + (3) "slot_body" contains a pointer to slot (slot_body::header::slot) + and an array of RVALUE. + (4) heap::sorted is an array of "slots", sorted by an address of + slot::body. + + See https://bugs.ruby-lang.org/projects/ruby-trunk/wiki/GC_design + for more details (figure). + + * gc.c: Avoid "heaps" terminology. It is ambiguous. + Wed Jul 17 13:29:16 2013 Koichi Sasada <ko1@a...> * gc.c: fix heaps_header and heaps_slot to reduce memory consumption. Index: gc.c =================================================================== --- gc.c (revision 42020) +++ gc.c (revision 42021) @@ -263,8 +263,14 @@ enum { https://github.com/ruby/ruby/blob/trunk/gc.c#L263 BITS_BITLENGTH = ( BITS_SIZE * CHAR_BIT ) }; -struct heaps_header { - struct heaps_slot *base; +struct heap_slot_header { + struct heap_slot *slot; +}; + +struct heap_slot_body { + struct heap_slot_header header; + /* char gap[]; */ + /* RVALUE values[]; */ }; struct gc_list { @@ -300,14 +306,14 @@ typedef struct rb_objspace { https://github.com/ruby/ruby/blob/trunk/gc.c#L306 } malloc_params; struct { size_t increment; - struct heaps_slot *ptr; - struct heaps_slot *sweep_slots; - struct heaps_slot *free_slots; - struct heaps_header **sorted; + struct heap_slot *slots; + struct heap_slot *sweep_slots; + struct heap_slot *free_slots; + struct heap_slot **sorted; size_t length; size_t used; RVALUE *range[2]; - struct heaps_header *freed; + struct heap_slot_body *freed; size_t free_num; size_t free_min; size_t final_num; @@ -361,7 +367,7 @@ typedef struct rb_objspace { https://github.com/ruby/ruby/blob/trunk/gc.c#L367 /* temporary profiling space */ double gc_sweep_start_time; size_t total_allocated_object_num_at_gc_start; - size_t heaps_used_at_gc_start; + size_t heap_used_at_gc_start; } profile; struct gc_list *global_list; size_t count; @@ -409,21 +415,21 @@ enum { https://github.com/ruby/ruby/blob/trunk/gc.c#L415 HEAP_ALIGN_MASK = (~(~0UL << HEAP_ALIGN_LOG)), REQUIRED_SIZE_BY_MALLOC = (sizeof(size_t) * 5), HEAP_SIZE = (HEAP_ALIGN - REQUIRED_SIZE_BY_MALLOC), - HEAP_OBJ_LIMIT = (unsigned int)((HEAP_SIZE - sizeof(struct heaps_header))/sizeof(struct RVALUE)), + HEAP_OBJ_LIMIT = (unsigned int)((HEAP_SIZE - sizeof(struct heap_slot_header))/sizeof(struct RVALUE)), HEAP_BITMAP_LIMIT = CEILDIV(CEILDIV(HEAP_SIZE, sizeof(struct RVALUE)), BITS_BITLENGTH), HEAP_BITMAP_SIZE = ( BITS_SIZE * HEAP_BITMAP_LIMIT), HEAP_BITMAP_PLANES = USE_RGENGC ? 3 : 1 /* RGENGC: mark bits, rememberset bits and oldgen bits */ }; -struct heaps_slot { - struct heaps_header *header; +struct heap_slot { + struct heap_slot_body *body; RVALUE *start; size_t limit; RVALUE *freelist; - struct heaps_slot *next; - struct heaps_slot *prev; - struct heaps_slot *free_next; + struct heap_slot *next; + struct heap_slot *prev; + struct heap_slot *free_next; bits_t mark_bits[HEAP_BITMAP_LIMIT]; #if USE_RGENGC @@ -437,9 +443,9 @@ struct heaps_slot { https://github.com/ruby/ruby/blob/trunk/gc.c#L443 #endif }; -#define HEAP_HEADER(p) ((struct heaps_header *)(p)) -#define GET_HEAP_HEADER(x) (HEAP_HEADER((bits_t)(x) & ~(HEAP_ALIGN_MASK))) -#define GET_HEAP_SLOT(x) (GET_HEAP_HEADER(x)->base) +#define GET_SLOT_BODY(x) ((struct heap_slot_body *)((bits_t)(x) & ~(HEAP_ALIGN_MASK))) +#define GET_SLOT_HEADER(x) (&GET_SLOT_BODY(x)->header) +#define GET_HEAP_SLOT(x) (GET_SLOT_HEADER(x)->slot) #define GET_HEAP_MARK_BITS(x) (&GET_HEAP_SLOT(x)->mark_bits[0]) #define GET_HEAP_REMEMBERSET_BITS(x) (&GET_HEAP_SLOT(x)->rememberset_bits[0]) #define GET_HEAP_OLDGEN_BITS(x) (&GET_HEAP_SLOT(x)->oldgen_bits[0]) @@ -465,13 +471,13 @@ VALUE *ruby_initial_gc_stress_ptr = &rb_ https://github.com/ruby/ruby/blob/trunk/gc.c#L471 #define malloc_increase objspace->malloc_params.increase #define malloc_increase2 objspace->malloc_params.increase2 #define malloc_allocated_size objspace->malloc_params.allocated_size -#define heaps objspace->heap.ptr -#define heaps_length objspace->heap.length -#define heaps_used objspace->heap.used +#define heap_slots objspace->heap.slots +#define heap_length objspace->heap.length +#define heap_used objspace->heap.used #define lomem objspace->heap.range[0] #define himem objspace->heap.range[1] -#define heaps_inc objspace->heap.increment -#define heaps_freed objspace->heap.freed +#define heap_inc objspace->heap.increment +#define heap_freed objspace->heap.freed #define dont_gc objspace->flags.dont_gc #define during_gc objspace->flags.during_gc #define finalizing objspace->flags.finalizing @@ -606,13 +612,14 @@ RVALUE_PROMOTE(VALUE obj) https://github.com/ruby/ruby/blob/trunk/gc.c#L612 static inline int is_before_sweep(VALUE obj) { - struct heaps_slot *slot; + struct heap_slot *slot; rb_objspace_t *objspace = &rb_objspace; if (is_lazy_sweeping(objspace)) { slot = objspace->heap.sweep_slots; while (slot) { - if (slot->header == GET_HEAP_HEADER(obj)) + if (slot->body == GET_SLOT_BODY(obj)) { return TRUE; + } slot = slot->next; } } @@ -692,12 +699,12 @@ rb_objspace_free(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L699 } if (objspace->heap.sorted) { size_t i; - for (i = 0; i < heaps_used; ++i) { + for (i = 0; i < heap_used; ++i) { aligned_free(objspace->heap.sorted[i]); } free(objspace->heap.sorted); - heaps_used = 0; - heaps = 0; + heap_used = 0; + heap_slots = 0; } free_stack_chunks(&objspace->mark_stack); free(objspace); @@ -711,19 +718,19 @@ rb_global_variable(VALUE *var) https://github.com/ruby/ruby/blob/trunk/gc.c#L718 } static void -allocate_sorted_heaps(rb_objspace_t *objspace, size_t next_heaps_length) +allocate_sorted_array(rb_objspace_t *objspace, size_t next_heap_length) { - struct heaps_header **p; + struct heap_slot **p; size_t size; - size = next_heaps_length*sizeof(struct heaps_header *); + size = next_heap_length * sizeof(struct heap_slot *); - if (heaps_used > 0) { - p = (struct heaps_header **)realloc(objspace->heap.sorted, size); + if (heap_used > 0) { + p = (struct heap_slot **)realloc(objspace->heap.sorted, size); if (p) objspace->heap.sorted = p; } else { - p = objspace->heap.sorted = (struct heaps_header **)malloc(size); + p = objspace->heap.sorted = (struct heap_slot **)malloc(size); } if (p == 0) { @@ -733,7 +740,7 @@ allocate_sorted_heaps(rb_objspace_t *obj https://github.com/ruby/ruby/blob/trunk/gc.c#L740 } static inline void -slot_add_freeobj(rb_objspace_t *objspace, struct heaps_slot *slot, VALUE obj) +slot_add_freeobj(rb_objspace_t *objspace, struct heap_slot *slot, VALUE obj) { RVALUE *p = (RVALUE *)obj; p->as.free.flags = 0; @@ -743,7 +750,7 @@ slot_add_freeobj(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L750 } static inline void -heaps_add_freeslot(rb_objspace_t *objspace, struct heaps_slot *slot) +heap_add_freeslot(rb_objspace_t *objspace, struct heap_slot *slot) { if (slot->freelist) { slot->free_next = objspace->heap.free_slots; @@ -755,99 +762,98 @@ static void https://github.com/ruby/ruby/blob/trunk/gc.c#L762 assign_heap_slot(rb_objspace_t *objspace) { RVALUE *start, *end, *p; - struct heaps_slot *slot; - struct heaps_header *header = 0; + struct heap_slot *slot; + struct heap_slot_body *slot_body = 0; size_t hi, lo, mid; size_t limit = HEAP_OBJ_LIMIT; - /* assign heaps_header entry (with RVALUEs area) */ - header = (struct heaps_header *)aligned_malloc(HEAP_ALIGN, HEAP_SIZE); - if (header == 0) { + /* assign heap_slot body (contains heap_slot_header and RVALUEs) */ + slot_body = (struct heap_slot_body *)aligned_malloc(HEAP_ALIGN, HEAP_SIZE); + if (slot_body == 0) { during_gc = 0; rb_memerror(); } - /* assign heaps_slot entry */ - slot = (struct heaps_slot *)malloc(sizeof(struct heaps_slot)); + /* assign heap_slot entry */ + slot = (struct heap_slot *)malloc(sizeof(struct heap_slot)); if (slot == 0) { - aligned_free(header); + aligned_free(slot_body); during_gc = 0; rb_memerror(); } - MEMZERO((void*)slot, struct heaps_slot, 1); + MEMZERO((void*)slot, struct heap_slot, 1); - slot->header = header; + slot->body = slot_body; - slot->next = objspace->heap.ptr; - if (objspace->heap.ptr) objspace->heap.ptr->prev = slot; - objspace->heap.ptr = slot; + slot->next = objspace->heap.slots; + if (objspace->heap.slots) objspace->heap.slots->prev = slot; + objspace->heap.slots = slot; /* adjust obj_limit (object number available in this slot) */ - start = (RVALUE*)((VALUE)header + sizeof(struct heaps_header)); + start = (RVALUE*)((VALUE)slot_body + sizeof(struct heap_slot_header)); if ((VALUE)start % sizeof(RVALUE) != 0) { int delta = sizeof(RVALUE) - ((VALUE)start % sizeof(RVALUE)); start = (RVALUE*)((VALUE)start + delta); - limit = (HEAP_SIZE - (size_t)((VALUE)start - (VALUE)header))/sizeof(RVALUE); + limit = (HEAP_SIZE - (size_t)((VALUE)start - (VALUE)slot_body))/sizeof(RVALUE); } end = start + limit; /* setup objspace->heap.sorted */ lo = 0; - hi = heaps_used; + hi = heap_used; while (lo < hi) { - struct heaps_header *mid_header; + struct heap_slot *mid_slot; mid = (lo + hi) / 2; - mid_header = objspace->heap.sorted[mid]; - if (mid_header < header) { + mid_slot = objspace->heap.sorted[mid]; + if (mid_slot->body < slot_body) { lo = mid + 1; } - else if (mid_header > header) { + else if (mid_slot->body > slot_body) { hi = mid; } else { - rb_bug("same heap slot is allocated: %p at %"PRIuVALUE, (void *)header, (VALUE)mid); + rb_bug("same heap slot is allocated: %p at %"PRIuVALUE, (void *)slot_body, (VALUE)mid); } } - if (hi < heaps_used) { - MEMMOVE(&objspace->heap.sorted[hi+1], &objspace->heap.sorted[hi], struct heaps_header*, heaps_used - hi); + if (hi < heap_used) { + MEMMOVE(&objspace->heap.sorted[hi+1], &objspace->heap.sorted[hi], struct heap_slot_header*, heap_used - hi); } - objspace->heap.sorted[hi] = header; - /* setup header and slot */ - header->base = slot; + /* setup slot */ slot->start = start; slot->limit = limit; + slot_body->header.slot = objspace->heap.sorted[hi] = slot; if (lomem == 0 || lomem > start) lomem = start; if (himem < end) himem = end; - heaps_used++; + heap_used++; for (p = start; p != end; p++) { rgengc_report(3, objspace, "assign_heap_slot: %p (%s) is added to freelist\n", p, obj_type_name((VALUE)p)); slot_add_freeobj(objspace, slot, (VALUE)p); } - heaps_add_freeslot(objspace, slot); + heap_add_freeslot(objspace, slot); } static void add_heap_slots(rb_objspace_t *objspace, size_t add) { size_t i; - size_t next_heaps_length; + size_t next_heap_length; - next_heaps_length = heaps_used + add; + next_heap_length = heap_used + add; - if (next_heaps_length > heaps_length) { - allocate_sorted_heaps(objspace, next_heaps_length); - heaps_length = next_heaps_length; + if (next_heap_length > heap_length) { + allocate_sorted_array(objspace, next_heap_length); + heap_length = next_heap_length; } for (i = 0; i < add; i++) { assign_heap_slot(objspace); } - heaps_inc = 0; + heap_inc = 0; } static void @@ -875,39 +881,39 @@ initial_expand_heap(rb_objspace_t *objsp https://github.com/ruby/ruby/blob/trunk/gc.c#L881 { size_t min_size = initial_heap_min_slots / HEAP_OBJ_LIMIT; - if (min_size > heaps_used) { - add_heap_slots(objspace, min_size - heaps_used); + if (min_size > heap_used) { + add_heap_slots(objspace, min_size - heap_used); } } static void -set_heaps_increment(rb_objspace_t *objspace) +set_heap_increment(rb_objspace_t *objspace) { - size_t next_heaps_length = (size_t)(heaps_used * initial_growth_factor); + size_t next_heap_length = (size_t)(heap_used * initial_growth_factor); - if (next_heaps_length == heaps_used) { - next_heaps_length++; + if (next_heap_length == heap_used) { + next_heap_length++; } - heaps_inc = next_heaps_length - heaps_used; + heap_inc = next_heap_length - heap_used; - rgengc_report(5, objspace, "set_heaps_increment: heaps_length: %d, next_heaps_length: %d, heaps_inc: %d\n", - heaps_length, next_heaps_length, heaps_inc); + rgengc_report(5, objspace, "set_heap_increment: heap_length: %d, next_heap_length: %d, heap_inc: %d\n", + heap_length, next_heap_length, heap_inc); - if (next_heaps_length > heaps_length) { - allocate_sorted_heaps(objspace, next_heaps_length); - heaps_length = next_heaps_length; + if (next_heap_length > heap_length) { + allocate_sorted_array(objspace, next_heap_length); + heap_length = next_heap_length; } } static int -heaps_increment(rb_objspace_t *objspace) +heap_increment(rb_objspace_t *objspace) { - rgengc_report(5, objspace, "heaps_increment: heaps_inc: %d\n", heaps_inc); + rgengc_report(5, objspace, "heap_increment: heap_inc: %d\n", heap_inc); - if (heaps_inc > 0) { + if (heap_inc > 0) { assign_heap_slot(objspace); - heaps_inc--; + heap_inc--; return TRUE; } return FALSE; @@ -918,9 +924,9 @@ ready_to_gc(rb_objspace_t *objspace) https://github.com/ruby/ruby/blob/trunk/gc.c#L924 { if (dont_gc || during_gc) { if (!objspace->freelist && !objspace->heap.free_slots) { - if (!heaps_increment(objspace)) { - set_heaps_increment(objspace); - heaps_increment(objspace); + if (!heap_increment(objspace)) { + set_heap_increment(objspace); + heap_increment(objspace); } } return FALSE; @@ -928,11 +934,11 @@ ready_to_gc(rb_objspace_t *objspace) https://github.com/ruby/ruby/blob/trunk/gc.c#L934 return TRUE; } -static struct heaps_slot * -heaps_prepare_freeslot(rb_objspace_t *objspace) +static struct heap_slot * +heap_prepare_freeslot(rb_objspace_t *objspace) { if (!GC_ENABLE_LAZY_SWEEP && objspace->flags.dont_lazy_sweep) { - if (heaps_increment(objspace) == 0 && + if (heap_increment(objspace) == 0 && garbage_collect(objspace, FALSE, TRUE, GPR_FLAG_NEWOBJ) == 0) { goto err; } @@ -944,7 +950,7 @@ heaps_prepare_freeslot(rb_objspace_t *ob https://github.com/ruby/ruby/blob/trunk/gc.c#L950 during_gc++; if ((is_lazy_sweeping(objspace) && lazy_sweep(objspace)) || - heaps_increment(objspace)) { + heap_increment(objspace)) { goto ok; } @@ -962,14 +968,14 @@ heaps_prepare_freeslot(rb_objspace_t *ob https://github.com/ruby/ruby/blob/trunk/gc.c#L968 return objspace->heap.free_slots; } -static inline struct heaps_slot * -heaps_get_freeslot(rb_objspace_t *objspace) +static inline struct heap_slot * +heap_get_freeslot(rb_objspace_t *objspace) { - struct heaps_slot *slot; + struct heap_slot *slot; slot = objspace->heap.free_slots; while (slot == NULL) { - slot = heaps_prepare_freeslot(objspace); + slot = heap_prepare_freeslot(objspace); } objspace->heap.free_slots = slot->free_next; @@ -982,7 +988,7 @@ get_freeobj(rb_objspace_t *objspace) https://github.com/ruby/ruby/blob/trunk/gc.c#L988 RVALUE *p = objspace->freelist; while (UNLIKELY(p == NULL)) { - struct heaps_slot *slot = heaps_get_freeslot(objspace); + struct heap_slot *slot = heap_get_freeslot(objspace); p = objspace->freelist = slot->freelist; } objspace->freelist = p->as.free.next; @@ -1132,7 +1138,7 @@ static inline int https://github.com/ruby/ruby/blob/trunk/gc.c#L1138 is_pointer_to_heap(rb_objspace_t *objspace, void *ptr) { register RVALUE *p = RANY(ptr); - register struct heaps_header *heap; + register struct heap_slot *slot; register size_t hi, lo, mid; if (p < lomem || p > himem) return FALSE; @@ -1140,13 +1146,14 @@ is_pointer_to_heap(rb_objspace_t *objspa https://github.com/ruby/ruby/blob/trunk/gc.c#L1146 /* check if p looks like a pointer using bsearch*/ lo = 0; - hi = heaps_used; + hi = heap_used; while (lo < hi) { mid = (lo + hi) / 2; - heap = objspace->heap.sorted[mid]; - if (heap->base->start <= p) { - if (p < heap->base->start + heap->base->limit) + slot = objspace->heap.sorted[mid]; + if (slot->start <= p) { + if (p < slot->start + slot->limit) { return TRUE; + } lo = mid + 1; } else { @@ -1187,14 +1194,14 @@ rb_free_const_table(st_table *tbl) https://github.com/ruby/ruby/blob/trunk/gc.c#L1194 } static void -unlink_heap_slot(rb_objspace_t *objspace, struct heaps_slot *slot) +unlink_heap_slot(rb_objspace_t *objspace, struct heap_slot *slot) { if (slot->prev) slot->prev->next = slot->next; if (slot->next) slot->next->prev = slot->prev; - if (heaps == slot) - heaps = slot->next; + if (heap_slots == slot) + heap_slots = slot->next; if (objspace->heap.sweep_slots == slot) objspace->heap.sweep_slots = slot->next; slot->prev = NULL; @@ -1202,20 +1209,20 @@ unlink_heap_slot(rb_objspace_t *objspace https://github.com/ruby/ruby/blob/trunk/gc.c#L1209 } static void -free_unused_heaps(rb_objspace_t *objspace) +free_unused_slots(rb_objspace_t *objspace) { size_t i, j; - struct heaps_header *last = 0; + struct heap_slot_body *last = 0; - for (i = j = 1; j < heaps_used; i++) { - if (objspace->heap.sorted[i]->base->limit == 0) { + for (i = j = 1; j < heap_used; i++) { + if (objspace->heap.sorted[i]->limit == 0) { if (!last) { - last = objspace->heap.sorted[i]; + last = objspace->heap.sorted[i]->body; } else { - aligned_free(objspace->heap.sorted[i]); + aligned_free(objspace->heap.sorted[i]->body); } - heaps_used--; + heap_used--; } else { if (i != j) { @@ -1225,9 +1232,9 @@ free_unused_heaps(rb_objspace_t *objspac https://github.com/ruby/ruby/blob/trunk/gc.c#L1232 } } if (last) { - if (last < heaps_freed) { - aligned_free(heaps_freed); - heaps_freed = last; + if (last < heap_freed) { + aligned_free(heap_freed); + heap_freed = last; } else { aligned_free(last); @@ -1415,17 +1422,17 @@ objspace_each_objects(VALUE arg) https://github.com/ruby/ruby/blob/trunk/gc.c#L1422 volatile VALUE v; i = 0; - while (i < heaps_used) { + while (i < heap_used) { while (0 < i && (uintptr_t)membase < (uintptr_t)objspace->heap.sorted[i-1]) i--; - while (i < heaps_used && (uintptr_t)objspace->heap.sorted[i] <= (uintptr_t)membase) + while (i < heap_used && (uintptr_t)objspace->heap.sorted[i] <= (uintptr_t)membase) i++; - if (heaps_used <= i) + if (heap_used <= i) break; membase = (RVALUE *)objspace->heap.sorted[i]; - pstart = objspace->heap.sorted[i]->base->start; - pend = pstart + objspace->heap.sorted[i]->base->limit; + pstart = objspace->heap.sorted[i]->start; + pend = pstart + objspace->heap.sorted[i]->limit; for (; pstart != pend; pstart++) { if (pstart->as.basic.flags) { @@ -1788,7 +1795,7 @@ finalize_list(rb_objspace_t *objspace, R https://github.com/ (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/