Slate VM: /home/briantrice/src/slate-language/src/vm/gc.cpp Source File

00001 #include "slate.hpp"
00002 #ifdef SLATE_USE_MMAP
00003 #include <sys/mman.h>
00004 #endif
00005 
00006 
00007 void assert_good_object(struct object_heap* oh, struct Object* obj) {
00008   assert(obj->payloadSize < 40 * MB);
00009   assert(obj->objectSize < 40 * MB);
00010   assert(object_is_young(oh, obj) || object_is_old(oh, obj));
00011   assert(object_is_young(oh, (struct Object*)obj->map) || object_is_old(oh, (struct Object*)obj->map));
00012   assert(!object_is_free(obj));
00013   assert(!object_is_free((struct Object*)obj->map));
00014 }
00015 
00016 #ifdef GC_BUG_CHECK
00017 
00018 void heap_integrity_check(struct object_heap* oh, byte_t* memory, word_t memorySize) {
00019   struct Object* o = (struct Object*)memory;
00020   printf("GC integrity check...\n");
00021 
00022   while (object_in_memory(oh, o, memory, memorySize)) {
00023 
00024     if (object_is_free(o)) {
00025       assert(heap_what_points_to(oh, o, 0) == 0);
00026     } else {
00027       assert_good_object(oh, o);
00028     }
00029     o = object_after(oh, o);
00030   }
00031 }
00032 
00033 #endif
00034 
00035 
00036 
00037 bool_t object_is_marked(struct object_heap* heap, struct Object* o) {
00038 
00039   return (object_markbit(o) == heap->mark_color);
00040 }
00041 
00042 
00043 void method_flush_cache(struct object_heap* oh, struct Symbol* selector) {
00044   struct MethodCacheEntry* cacheEntry;
00045   if (selector == (struct Symbol*)oh->cached.nil || selector == NULL) {
00046 #if 1
00047     fill_bytes_with((byte_t*)oh->methodCache, METHOD_CACHE_SIZE*sizeof(struct MethodCacheEntry), 0);
00048 #else
00049     /*flush only things that pointed to young memory*/
00050     word_t i, j;
00051     for (i = 0; i < METHOD_CACHE_SIZE; i++) {
00052       cacheEntry = &oh->methodCache[i];
00053       if (object_is_young(oh, (struct Object*)cacheEntry->selector) || object_is_young(oh, (struct Object*)cacheEntry->method)) goto zero;
00054       for (j = 0; j < METHOD_CACHE_ARITY; j++) {
00055         if (object_is_young(oh, (struct Object*)cacheEntry->maps[j])) goto zero;
00056       }
00057       /*it only points to old (same addressed) memory so leave it*/
00058       return;
00059     zero:
00060       fill_bytes_with((byte_t*)oh->methodCache, METHOD_CACHE_SIZE*sizeof(struct MethodCacheEntry), 0);
00061     }
00062 #endif
00063   } else {
00064     word_t i;
00065     for (i = 0; i < METHOD_CACHE_SIZE; i++) {
00066       if ((cacheEntry = &oh->methodCache[i])->selector == selector) cacheEntry->selector = (struct Symbol*)oh->cached.nil;
00067     }
00068   }
00069 }
00070 
00071 struct Object* heap_make_free_space(struct object_heap* oh, struct Object* obj, word_t words) {
00072 
00073   assert(words > 0);
00074 
00075 #ifdef PRINT_DEBUG
00076   printf("Making %" PRIdPTR " words of free space at: %p\n", words, (void*)start);
00077 #endif
00078 
00079 
00080   object_set_format(obj, TYPE_OBJECT);
00081   object_set_size(obj, words);
00082   payload_set_size(obj, 0); /*zero it out or old memory will haunt us*/
00083   obj->map = NULL;
00084   /*fix should we mark this?*/
00085   object_set_idhash(obj, ID_HASH_FREE);
00086 #ifdef GC_MARK_FREED_MEMORY
00087   fill_bytes_with((byte_t*)(obj+1), words*sizeof(word_t)-sizeof(struct Object), 0xFE);
00088 #endif
00089   return obj;
00090 }
00091 
00092 struct Object* heap_make_used_space(struct object_heap* oh, struct Object* obj, word_t words) {
00093   struct Object* x = heap_make_free_space(oh, obj, words);
00094   object_set_idhash(obj, heap_new_hash(oh));
00095   return x;
00096 }
00097 
00098 
00099 void heap_zero_pin_counts_from(struct object_heap* oh, byte_t* memory, word_t memorySize) {
00100 
00101   struct Object* o = (struct Object*)memory;
00102 
00103   while (object_in_memory(oh, o, memory, memorySize)) {
00104     if (!object_is_free(o)) {
00105       object_zero_pin_count(o);
00106     }
00107     o = object_after(oh, o);
00108   }
00109 
00110 
00111 }
00112 
00113 
00114 bool_t heap_initialize(struct object_heap* oh, word_t size, word_t limit, word_t young_limit, word_t next_hash, word_t special_oop, word_t cdid) {
00115 #ifdef SLATE_USE_MMAP
00116   void* oldStart = (void*)0x10000000;
00117   void* youngStart = (void*)0x80000000;
00118 #endif
00119   oh->memoryOldLimit = limit;
00120   oh->memoryYoungLimit = young_limit;
00121 
00122   oh->memoryOldSize = size;
00123   oh->memoryYoungSize = young_limit;
00124 
00125 #ifdef SLATE_USE_MMAP
00126   assert((byte_t*)oldStart + limit < (byte_t*) youngStart);
00127   oh->memoryOld = (byte_t*)mmap((void*)oldStart, limit, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|0x20, -1, 0);
00128   oh->memoryYoung = (byte_t*)mmap((void*)youngStart, young_limit, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|0x20, -1, 0);
00129 #else
00130   oh->memoryOld = (byte_t*)malloc(limit);
00131   oh->memoryYoung = (byte_t*)malloc(young_limit);
00132 #endif
00133   oh->rememberedOldObjects.clear();
00134   oh->doFullGCNext = 1;
00135   /*perror("err: ");*/
00136   if (oh->memoryOld == NULL || oh->memoryOld == (void*)-1
00137       || oh->memoryYoung == NULL || oh->memoryYoung == (void*)-1) {
00138     fprintf(stderr, "Initial GC allocation of memory failed.\n");
00139     return 0;
00140   }
00141 
00142   oh->nextFree = (struct Object*)oh->memoryYoung;
00143   oh->nextOldFree = (struct Object*)oh->memoryOld;
00144   heap_make_free_space(oh, oh->nextFree, oh->memoryYoungSize / sizeof(word_t));
00145 
00146 
00147   oh->special_objects_oop = (struct OopArray*)((byte_t*)oh->memoryOld + special_oop);
00148   oh->lastHash = next_hash;
00149   oh->current_dispatch_id = cdid;
00150   oh->interrupt_flag = 0;
00151   oh->mark_color = 1;
00152   oh->markStackSize = 4 * MB;
00153   oh->markStackPosition = 0;
00154   oh->markStack = (struct Object**)malloc(oh->markStackSize * sizeof(struct Object*));
00155   
00156   assert(oh->markStack != NULL);
00157 
00158   return 1;
00159 }
00160 
00161 void heap_close(struct object_heap* oh) {
00162 #ifdef SLATE_USE_MMAP
00163   munmap(oh->memoryOld, oh->memoryOldLimit);
00164   munmap(oh->memoryYoung, oh->memoryYoungLimit);
00165 #else
00166   free(oh->memoryOld);
00167   free(oh->memoryYoung);
00168 #endif
00169 }
00170 bool_t object_is_pinned(struct object_heap* oh, struct Object* x) {
00171   return object_pin_count(x) > 0;
00172 }
00173 
00174 bool_t object_is_remembered(struct object_heap* oh, struct Object* x) {
00175   if (object_is_old(oh, x)) {
00176     oh->rememberedOldObjects.find(x) != oh->rememberedOldObjects.end();
00177   }
00178   return 0;
00179   
00180 }
00181 
00182 struct Object* heap_find_first_young_free(struct object_heap* oh, struct Object* obj, word_t bytes) {
00183   while (object_in_memory(oh, obj, oh->memoryYoung, oh->memoryYoungSize)) {
00184     if (object_is_free(obj) && object_total_size(obj) >= bytes) return obj;
00185     obj = object_after(oh, obj);
00186   }
00187   return NULL;
00188 }
00189 
00190 struct Object* heap_find_first_old_free(struct object_heap* oh, struct Object* obj, word_t bytes) {
00191   while (object_in_memory(oh, obj, oh->memoryOld, oh->memoryOldSize)) {
00192     if (object_is_free(obj) && object_total_size(obj) >= bytes) return obj;
00193     obj = object_after(oh, obj);
00194   }
00195   return NULL;
00196 }
00197 
00198 
00199 struct Object* gc_allocate_old(struct object_heap* oh, word_t bytes) {
00200   word_t words = bytes / sizeof(word_t);
00201   assert(bytes % sizeof(word_t) == 0);
00202 
00203   if (!object_in_memory(oh, oh->nextOldFree, oh->memoryOld, oh->memoryOldSize)) {
00204     oh->nextOldFree = (struct Object*)oh->memoryOld;
00205   }
00206 
00207   oh->nextOldFree = heap_find_first_old_free(oh, oh->nextOldFree, bytes + sizeof(struct Object));
00208 
00209   if (oh->nextOldFree == NULL) {
00210     assert(oh->memoryOldSize+bytes < oh->memoryOldLimit);
00211     oh->nextOldFree = (struct Object*)(oh->memoryOld + oh->memoryOldSize);
00212     heap_make_used_space(oh, oh->nextOldFree, words);
00213     oh->memoryOldSize += bytes;
00214     return oh->nextOldFree;
00215 
00216   } else {
00217     struct Object* next;
00218     word_t oldsize;
00219     oldsize = object_word_size(oh->nextOldFree);
00220     heap_make_used_space(oh, oh->nextOldFree, words);
00221     next = object_after(oh, oh->nextOldFree);
00222     heap_make_free_space(oh, next, oldsize - words);
00223     return oh->nextOldFree;
00224   }
00225 
00226 }
00227 
00228 
00229 struct Object* gc_allocate(struct object_heap* oh, word_t bytes) {
00230   bool_t already_scavenged = 0, already_full_gc = 0;
00231   struct Object* next;
00232   word_t oldsize;
00233   word_t words = bytes / sizeof(word_t);
00234 
00235   assert(bytes % sizeof(word_t) == 0);
00236 
00237  start:
00238   if (!object_in_memory(oh, oh->nextFree, oh->memoryYoung, oh->memoryYoungSize)) {
00239     oh->nextFree = (struct Object*)oh->memoryYoung;
00240   }
00241   /*fix also look for things the exact same size*/
00242   /*plus room to break in half*/
00243   oh->nextFree = heap_find_first_young_free(oh, oh->nextFree, bytes + sizeof(struct Object));
00244   if (oh->nextFree == NULL) {
00245     if (!already_scavenged) {
00246       if (oh->doFullGCNext) {
00247         heap_full_gc(oh);
00248       } else {
00249         heap_gc(oh);
00250       }
00251       already_scavenged = 1;
00252 
00253     } else if (!already_full_gc) {
00254       already_full_gc = 1;
00255       heap_full_gc(oh);
00256     } else {
00257       //heap_print_objects(oh, oh->memoryYoung, oh->memoryYoungSize);
00258       //print_backtrace(oh);
00259       printf("Couldn't allocate %" PRIdPTR " bytes... using oldspace\n", bytes + sizeof(struct Object));
00260       return gc_allocate_old(oh, bytes);
00261       //assert(0);
00262     }
00263     oh->nextFree = (struct Object*)oh->memoryYoung;
00264     goto start;
00265   }
00266   /*we break the space in half if we can*/
00267   oldsize = object_word_size(oh->nextFree);
00268   heap_make_used_space(oh, oh->nextFree, words);
00269   next = object_after(oh, oh->nextFree);
00270   heap_make_free_space(oh, next, oldsize - words);
00271   return oh->nextFree;
00272   
00273 }
00274 
00275 void object_forward_pointers_to(struct object_heap* oh, struct Object* o, struct Object* x, struct Object* y) {
00276 
00277   word_t offset, limit;
00278   if (o->map == (struct Map*)x) {
00279     heap_store_into(oh, o, y);
00280     o->map = (struct Map*)y;
00281   }
00282   offset = object_first_slot_offset(o);
00283   limit = object_last_oop_offset(o) + sizeof(word_t);
00284   for (; offset != limit; offset += sizeof(word_t)) {
00285     struct Object* val = object_slot_value_at_offset(o, offset);
00286     if (val == x) {
00287 #ifdef PRINT_DEBUG
00288       printf("Forwarding pointer in "); print_type(oh, o); printf(" to "); print_type(oh, y);
00289 #endif
00290       object_slot_value_at_offset_put(oh, o, offset, y);
00291     }
00292   }
00293 }
00294 
00295 
00296 
00297 void heap_free_object(struct object_heap* oh, struct Object* obj) {
00298 #ifdef PRINT_DEBUG_GC_MARKINGS
00299   printf("freeing "); print_object(obj);
00300 #endif
00301   //fixme
00302   //  oh->optimizedMethods.erase((struct CompiledMethod*)obj);
00303 
00304 #ifdef GC_BUG_CHECK
00305   assert(!object_is_pinned(oh, obj));
00306 #endif
00307 
00308   /*we also might want to optimize the removal if we are profiling*/
00309   if (oh->currentlyProfiling) {
00310     profiler_delete_method(oh, obj);
00311   }
00312 
00313   if (object_is_old(oh, obj)) {
00314     oh->rememberedOldObjects.erase(obj);
00315   }
00316 
00317   heap_make_free_space(oh, obj, object_word_size(obj));
00318 
00319 }
00320 
00321 
00322 void heap_finish_gc(struct object_heap* oh) {
00323   method_flush_cache(oh, NULL);
00324   /*  cache_specials(oh);*/
00325 }
00326 
00327 
00328 void heap_finish_full_gc(struct object_heap* oh) {
00329   oh->doFullGCNext = 0;
00330   heap_finish_gc(oh);
00331 }
00332 
00333 
00334 
00335 void heap_start_gc(struct object_heap* oh) {
00336   oh->mark_color ^= MARK_MASK;
00337   oh->markStackPosition = 0;
00338 }
00339 
00340 
00341 void heap_remember_old_object(struct object_heap* oh, struct Object* x) {
00342   if (object_is_old(oh, x) && !object_is_smallint(x)) {
00343 #if 0
00344     printf("remembering "); print_object(x);
00345 #endif
00346     oh->rememberedOldObjects.insert(x);
00347   }
00348   
00349 }
00350 
00351 
00352 
00353 /*adds something to the mark stack and mark it if it isn't marked already*/
00354 void heap_mark(struct object_heap* oh, struct Object* obj) {
00355 #ifdef GC_BUG_CHECK
00356   assert_good_object(oh, obj);
00357 #endif
00358 
00359   if (object_markbit(obj) == oh->mark_color) return;
00360 #ifdef PRINT_DEBUG_GC_MARKINGS
00361   printf("marking "); print_object(obj);
00362 #endif
00363   object_set_mark(oh, obj);
00364   
00365   if (oh->markStackPosition + 1 >=oh->markStackSize) {
00366     oh->markStackSize *= 2;
00367 #ifdef PRINT_DEBUG
00368     printf("Growing mark stack to %" PRIdPTR "\n", oh->markStackSize);
00369 #endif
00370     oh->markStack = (struct Object**)realloc(oh->markStack, oh->markStackSize * sizeof(struct Object*));
00371     assert(oh->markStack);
00372   }
00373   oh->markStack[oh->markStackPosition++] = obj;
00374 }
00375 
00376 
00377 void heap_mark_specials(struct object_heap* oh, bool_t mark_old) {
00378   word_t i;
00379   for (i = 0; i < array_size(oh->special_objects_oop); i++) {
00380     struct Object* obj = oh->special_objects_oop->elements[i];
00381     if (!mark_old && object_is_old(oh, obj)) continue;
00382     if (object_is_smallint(obj)) continue;
00383     heap_mark(oh, obj);
00384   }
00385 
00386 }
00387 
00388 void heap_mark_interpreter_stack(struct object_heap* oh, bool_t mark_old) {
00389   word_t i;
00390   for (i = 0; i < oh->cached.interpreter->stackPointer; i++) {
00391     struct Object* obj = oh->cached.interpreter->stack->elements[i];
00392     if (object_is_smallint(obj)) continue;
00393     if (!mark_old && object_is_old(oh, obj)) continue;
00394     heap_mark(oh, obj);
00395   }
00396 
00397 }
00398 
00399 void heap_mark_fields(struct object_heap* oh, struct Object* o) {
00400   word_t offset, limit;
00401   heap_mark(oh, (struct Object*)o->map);
00402   offset = object_first_slot_offset(o);
00403   limit = object_last_oop_offset(o) + sizeof(word_t);
00404   for (; offset != limit; offset += sizeof(word_t)) {
00405     struct Object* val = object_slot_value_at_offset(o, offset);
00406     if (!object_is_smallint(val)) {
00407       heap_mark(oh, val);
00408     }
00409   }
00410 
00411 
00412 }
00413 
00414 void heap_mark_recursively(struct object_heap* oh, bool_t mark_old) {
00415 
00416   while (oh->markStackPosition > 0) {
00417     struct Object* obj;
00418     oh->markStackPosition--;
00419     obj = oh->markStack[oh->markStackPosition];
00420     if (!mark_old && object_is_old(oh, obj)) continue;
00421     heap_mark_fields(oh, obj);
00422   }
00423 
00424 }
00425 
00426 void heap_free_and_coalesce_unmarked(struct object_heap* oh, byte_t* memory, word_t memorySize) {
00427   struct Object* obj = (struct Object*) memory;
00428   struct Object* prev = obj;
00429   word_t freed_words = 0, coalesce_count = 0, free_count = 0, object_count = 0;
00430   while (object_in_memory(oh, obj, memory, memorySize)) {
00431     object_count++;
00432     if (!object_is_free(obj) && !object_is_marked(oh, obj)) {
00433       free_count++;
00434       freed_words += object_word_size(obj);
00435       heap_free_object(oh, obj);
00436     }
00437     if (object_is_free(obj) && object_is_free(prev) && obj != prev) {
00438       heap_make_free_space(oh, prev, object_word_size(obj)+object_word_size(prev));
00439       coalesce_count++;
00440       obj = object_after(oh, prev);
00441     } else {
00442       prev = obj;
00443       obj = object_after(oh, obj);
00444     }
00445     
00446   }
00447 
00448   if ((memory == oh->memoryOld) && (free_count == 0 || (object_count / free_count > 2))) {
00449     oh->doFullGCNext = 1;
00450   }
00451 
00452 #ifdef PRINT_DEBUG_GC_1
00453   if (!oh->quietGC) {
00454     printf("GC freed %" PRIdPTR " of %" PRIdPTR " %s objects\n", 
00455            free_count, object_count, ((memory == oh->memoryOld)? "old":"new"));
00456     printf("GC coalesced %" PRIdPTR " times\n", coalesce_count);
00457   }
00458 #endif
00459 }
00460 
00461 void heap_unmark_all(struct object_heap* oh, byte_t* memory, word_t memorySize) {
00462   struct Object* obj = (struct Object*) memory;
00463 
00464   while (object_in_memory(oh, obj, memory, memorySize)) {
00465 #ifdef PRINT_DEBUG_GC_MARKINGS
00466     printf("unmarking "); print_object(obj);
00467 #endif
00468     object_unmark(oh, obj);
00469     obj = object_after(oh, obj);
00470   }
00471 
00472 }
00473 
00474 
00475 
00476 
00477 void heap_update_forwarded_pointers(struct object_heap* oh, byte_t* memory, word_t memorySize) {
00478   struct Object* o = (struct Object*) memory;
00479  
00480   while (object_in_memory(oh, o, memory, memorySize)) {
00481     word_t offset, limit;
00482     if (object_is_free(o)) goto next;
00483     while (object_hash((struct Object*)o->map) == ID_HASH_FORWARDED) {
00484       o->map = (struct Map*)((struct ForwardedObject*)(o->map))->target;
00485     }
00486     assert(!object_is_free((struct Object*)o->map));
00487     offset = object_first_slot_offset(o);
00488     limit = object_last_oop_offset(o) + sizeof(word_t);
00489     for (; offset != limit; offset += sizeof(word_t)) {
00490       struct Object* val = object_slot_value_at_offset(o, offset);
00491       while (!object_is_smallint(val) && object_hash(val) == ID_HASH_FORWARDED) {
00492         object_slot_value_at_offset_put(oh, o, offset, (val=((struct ForwardedObject*)val)->target));
00493       }
00494       assert(object_is_smallint(val) || !object_is_free(val));
00495 
00496     }
00497   next:
00498     o = object_after(oh, o);
00499   }
00500 
00501 
00502 }
00503 
00504 void heap_notice_forwarded_object(struct object_heap* oh, struct Object* from, struct Object* to) {
00505   if (oh->currentlyProfiling) {
00506     //fixme ignore objects that aren't methods
00507     profiler_notice_forwarded_object(oh, from, to);
00508   }
00509 }
00510 
00511 
00512 void heap_tenure(struct object_heap* oh) {
00513   /*bring all marked young objects to old generation*/
00514   word_t tenure_count = 0, pin_count = 0, object_count = 0, free_count = 0;
00515   struct Object* obj = (struct Object*) oh->memoryYoung;
00516   struct Object* prev;
00517   /* fixme.. can't do this right now */
00518   /*  if (oh->gcTenureCount++ % 20 == 0) {*/
00519   oh->nextOldFree = (struct Object*)oh->memoryOld;
00520   /*  }*/
00521   
00522   oh->tenuredObjects.clear();
00523 
00524   while (object_in_memory(oh, obj, oh->memoryYoung, oh->memoryYoungSize)) {
00525     /*if it's still there in the young section, move it to the old section */
00526     if (object_is_free(obj)) {
00527       obj = object_after(oh, obj);
00528       continue;
00529     }
00530 
00531     object_count++;
00532     if (!object_is_marked(oh, obj)) {
00533       free_count++;
00534       heap_free_object(oh, obj);
00535     }
00536     if (object_is_pinned(oh, obj)) {
00537       pin_count++;
00538     } else {
00539       if (!object_is_free(obj)) {
00540         struct Object* tenure_start = gc_allocate_old(oh, object_total_size(obj));
00541         tenure_count++;
00542         copy_words_into((word_t*)obj, object_word_size(obj), (word_t*) tenure_start);
00543 #ifdef PRINT_DEBUG_GC_MARKINGS
00544         printf("tenuring from "); print_object(obj);
00545         printf("tenuring to "); print_object(tenure_start);
00546 #endif
00547         oh->tenuredObjects.push_back(tenure_start);
00548 
00549         heap_notice_forwarded_object(oh, obj, tenure_start);
00550         ((struct ForwardedObject*) obj)->target = tenure_start;
00551         object_set_idhash(obj, ID_HASH_FORWARDED);
00552       }
00553     }
00554     obj = object_after(oh, obj);
00555   }
00556 #ifdef PRINT_DEBUG_GC_1
00557   if (!oh->quietGC) {
00558     printf("Full GC freed %" PRIdPTR " young objects and tenured %" PRIdPTR " of %" PRIdPTR " objects (%" PRIdPTR " pinned)\n", 
00559            free_count, tenure_count, object_count, pin_count);
00560   }
00561 #endif
00562 
00563   heap_update_forwarded_pointers(oh, oh->memoryOld, oh->memoryOldSize);
00564   /*fixed objects in the young space need to have their pointers updated also*/
00565   heap_update_forwarded_pointers(oh, oh->memoryYoung, oh->memoryYoungSize);
00566 
00567   // see what tenured objects need to be added to our remembered set
00568   for (size_t i = 0; i < oh->tenuredObjects.size(); i++) {
00569     struct Object* o = oh->tenuredObjects[i];
00570     word_t offset, limit;
00571     if (object_is_young(oh, (struct Object*)o->map)) {
00572       heap_remember_old_object(oh, o);
00573       continue;
00574     }
00575     offset = object_first_slot_offset(o);
00576     limit = object_last_oop_offset(o) + sizeof(word_t);
00577     for (; offset != limit; offset += sizeof(word_t)) {
00578       struct Object* val = object_slot_value_at_offset(o, offset);
00579       if (!object_is_smallint(val) && object_is_young(oh, val)) {
00580         heap_remember_old_object(oh, o);
00581         break;
00582       }
00583     }
00584   }
00585 
00586 
00587   /*we coalesce after it has been tenured so we don't erase forwarding pointers */
00588   /*todo do lazily*/
00589   obj = (struct Object*) oh->memoryYoung;
00590   prev = obj;
00591   while (object_in_memory(oh, obj, oh->memoryYoung, oh->memoryYoungSize)) {
00592     /*coalesce free spaces*/
00593     if (object_is_free(obj) && object_is_free(prev) && obj != prev) {
00594       heap_make_free_space(oh, prev, object_word_size(obj)+object_word_size(prev));
00595       obj = object_after(oh, prev);
00596     } else {
00597       prev = obj;
00598       obj = object_after(oh, obj);
00599     }
00600 
00601   }
00602 
00603 
00604   oh->nextFree = (struct Object*)oh->memoryYoung;
00605 
00606 }
00607 
00608 
00609 void heap_mark_remembered(struct object_heap* oh) {
00610   word_t object_count = 0, remember_count = 0;
00611   std::vector<struct Object*> badRemembered;
00612 
00613   for (std::set<struct Object*>::iterator i = oh->rememberedOldObjects.begin();
00614        i != oh->rememberedOldObjects.end();
00615        i++) {
00616     struct Object* o = *i;
00617     word_t offset, limit, foundSomething;
00618     object_count++;
00619     foundSomething = 0;
00620 
00621     if (object_is_young(oh, (struct Object*)o->map)) {
00622       remember_count++;
00623       foundSomething = 1;
00624       heap_mark(oh, (struct Object*)o->map);
00625     }
00626 
00627     offset = object_first_slot_offset(o);
00628     limit = object_last_oop_offset(o) + sizeof(word_t);
00629     for (; offset != limit; offset += sizeof(word_t)) {
00630       struct Object* val = object_slot_value_at_offset(o, offset);
00631       if (!object_is_smallint(val) && object_is_young(oh, val)) {
00632         remember_count++;
00633         foundSomething = 1;
00634         heap_mark(oh, val);
00635       }
00636     }
00637     if (foundSomething == 0 || object_is_young(oh, o)) {
00638       //oh->rememberedOldObjects.erase(i);
00639       badRemembered.push_back(o);
00640     }
00641 
00642   }
00643 
00644 #ifdef PRINT_DEBUG_GC_3
00645   if (!oh->quietGC) {
00646     printf("Removing %" PRIdPTR " entries from the remembered table\n", badRemembered.size());
00647   }
00648 #endif
00649 
00650   for (size_t i = 0; i < badRemembered.size(); i++) {
00651     oh->rememberedOldObjects.erase(badRemembered[i]);
00652   }
00653 
00654 
00655 #ifdef PRINT_DEBUG_GC_2
00656   if (!oh->quietGC) {
00657     printf("Young GC found %" PRIdPTR " old objects pointing to %" PRIdPTR " young objects\n", 
00658            object_count, remember_count);
00659   }
00660 #endif
00661 
00662 }
00663 
00664 
00665 void heap_mark_pinned_young(struct object_heap* oh) {
00666   struct Object* obj = (struct Object*) oh->memoryYoung;
00667   while (object_in_memory(oh, obj, oh->memoryYoung, oh->memoryYoungSize)) {
00668     if (object_hash(obj) < ID_HASH_RESERVED && object_pin_count(obj) > 0) heap_mark(oh, obj);
00669     obj = object_after(oh, obj);
00670   }
00671 }
00672 
00673 void heap_mark_pinned_old(struct object_heap* oh) {
00674   struct Object* obj = (struct Object*) oh->memoryOld;
00675   while (object_in_memory(oh, obj, oh->memoryOld, oh->memoryOldSize)) {
00676     if (object_hash(obj) < ID_HASH_RESERVED && object_pin_count(obj) > 0) heap_mark(oh, obj);
00677     obj = object_after(oh, obj);
00678   }
00679 
00680 }
00681 
00682 
00683 void heap_pin_c_stack_diff(struct object_heap* oh) {
00684   word_t stackTop;
00685   word_t** stack = (word_t**)oh->stackBottom;
00686   while ((void*)stack > (void*)&stackTop) {
00687     struct Object* obj = (struct Object*)*stack;
00688     if ((object_is_young(oh, obj) || object_is_old(oh, obj))
00689         && !object_is_smallint(obj)
00690         && !object_is_marked(oh, obj)) {
00691       print_object(obj);
00692     }
00693     stack--;
00694    }
00695  
00696  }
00697 
00698 
00699 void heap_full_gc(struct object_heap* oh) {
00700   heap_start_gc(oh);
00701   heap_unmark_all(oh, oh->memoryOld, oh->memoryOldSize);
00702   heap_unmark_all(oh, oh->memoryYoung, oh->memoryYoungSize);
00703   heap_mark_pinned_young(oh);
00704   heap_mark_pinned_old(oh);
00705   heap_mark_specials(oh, 1);
00706   heap_mark_interpreter_stack(oh, 1);
00707   heap_mark_recursively(oh, 1);
00708 
00709 #ifdef GC_BUG_CHECK
00710   heap_pin_c_stack_diff(oh);
00711 #endif
00712 
00713   //this frees the old objects
00714   heap_free_and_coalesce_unmarked(oh, oh->memoryOld, oh->memoryOldSize);
00715   //this frees the young objects and moves them over
00716   heap_tenure(oh);
00717 #ifdef GC_BUG_CHECK
00718   heap_integrity_check(oh, oh->memoryOld, oh->memoryOldSize);
00719   heap_integrity_check(oh, oh->memoryYoung, oh->memoryYoungSize);
00720 #endif
00721   heap_finish_full_gc(oh);
00722 }
00723 
00724 void heap_gc(struct object_heap* oh) {
00725 #ifndef ALWAYS_FULL_GC
00726   heap_start_gc(oh);
00727   heap_unmark_all(oh, oh->memoryYoung, oh->memoryYoungSize);
00728   heap_mark_pinned_young(oh);
00729   heap_mark_specials(oh, 0);
00730   heap_mark_interpreter_stack(oh, 0);
00731   heap_mark_remembered(oh);
00732   heap_mark_recursively(oh, 0);
00733 #ifdef GC_BUG_CHECK
00734   heap_pin_c_stack_diff(oh);
00735 #endif
00736   // this frees the young objects
00737   heap_free_and_coalesce_unmarked(oh, oh->memoryYoung, oh->memoryYoungSize);
00738 
00739   oh->nextFree = (struct Object*)oh->memoryYoung;
00740 #ifdef GC_BUG_CHECK
00741   heap_integrity_check(oh, oh->memoryYoung, oh->memoryYoungSize);
00742 #endif
00743 
00744   heap_finish_gc(oh);
00745 #else
00746   heap_full_gc(oh);
00747 #endif
00748 }
00749 
00750 
00751 
00752 
00753 void heap_forward_from(struct object_heap* oh, struct Object* x, struct Object* y, byte_t* memory, word_t memorySize) {
00754   struct Object* o = (struct Object*)memory;
00755 
00756   while (object_in_memory(oh, o, memory, memorySize)) {
00757     /*print_object(o);*/
00758     if (!object_is_free(o)) {
00759       object_forward_pointers_to(oh, o, x, y);
00760     }
00761 
00762     o = object_after(oh, o);
00763   }
00764 
00765 
00766 }
00767 
00768 void heap_forward(struct object_heap* oh, struct Object* x, struct Object* y) {
00769 
00770   heap_forward_from(oh, x, y, oh->memoryOld, oh->memoryOldSize);
00771   heap_forward_from(oh, x, y, oh->memoryYoung, oh->memoryYoungSize);
00772 #ifdef GC_BUG_CHECK
00773   assert(heap_what_points_to(oh, x, 1) == 0);
00774 #endif
00775   heap_free_object(oh, x);
00776 }
00777 
00778 
00779 struct Object* heap_allocate_with_payload(struct object_heap* oh, word_t words, word_t payload_size) {
00780 
00781   struct Object* o;
00782   /*word aligned payload*/
00783   word_t size = words*sizeof(word_t) + ((payload_size + sizeof(word_t) - 1) & ~(sizeof(word_t) - 1));
00784   o = gc_allocate(oh, size);
00785 
00786   object_set_format(o, TYPE_BYTE_ARRAY);
00787   payload_set_size(o, payload_size);
00788   object_set_size(o, words);
00789   object_set_mark(oh, o);
00790   object_zero_pin_count(o);
00791   assert(!object_is_free(o));
00792   return o;
00793 }
00794 
00795 struct Object* heap_allocate(struct object_heap* oh, word_t words) {
00796   return heap_allocate_with_payload(oh, words, 0);
00797 }
00798 
00799 struct Object* heap_clone(struct object_heap* oh, struct Object* proto) {
00800   struct Object* newObj;
00801   //usually the caller should pin the objects but here we make an exception
00802   //if this got GC'd, then the copy_words_into would get garbage
00803   Pinned<struct Object> pinnedProto(oh);
00804   pinnedProto = proto;
00805   
00806   if (object_type(proto) == TYPE_OBJECT) {
00807     newObj = heap_allocate(oh, object_size(proto));
00808   } else {
00809     newObj = heap_allocate_with_payload(oh, object_size(proto), payload_size(proto));
00810   }
00811 
00812   object_set_format(newObj, object_type(proto));
00813 
00814   object_set_idhash(newObj, heap_new_hash(oh));
00815   copy_words_into((word_t*)inc_ptr(proto, HEADER_SIZE),
00816                   object_word_size(proto) - HEADER_SIZE_WORDS,
00817                   (word_t*)inc_ptr(newObj, HEADER_SIZE));
00818 
00819   return newObj;
00820 }
00821 
00822 
00823 struct Object* heap_clone_special(struct object_heap* oh, word_t special_index) {
00824   return heap_clone(oh, get_special(oh, special_index));
00825 }
00826 
00827 struct Map* heap_clone_map(struct object_heap* oh, struct Map* map) {
00828   return (struct Map*)heap_clone(oh, (struct Object*)map);
00829 }
00830 
00831 struct ByteArray* heap_new_float(struct object_heap* oh) {
00832   return (struct ByteArray*)heap_clone_special(oh, SPECIAL_OOP_FLOAT_PROTO);
00833 }
00834 
00835 struct OopArray* heap_clone_oop_array_sized(struct object_heap* oh, struct Object* proto, word_t size) {
00836 
00837   struct Object* newObj = heap_allocate_with_payload(oh, object_size(proto), size * sizeof(struct Object*));
00838   object_set_format(newObj, TYPE_OOP_ARRAY);
00839 
00840   object_set_idhash(newObj, heap_new_hash(oh));
00841   /*copy everything but the header bits*/
00842 
00843   copy_words_into((word_t *) inc_ptr(proto, HEADER_SIZE),
00844                   object_size(proto) - HEADER_SIZE_WORDS,
00845                   (word_t*) inc_ptr(newObj, HEADER_SIZE));
00846 
00847   fill_words_with((word_t*)newObj  + object_size(proto), size, (word_t)oh->cached.nil);
00848 
00849   return (struct OopArray*) newObj;
00850 }
00851 
00852 struct ByteArray* heap_clone_byte_array_sized(struct object_heap* oh, struct Object* proto, word_t bytes) {
00853 
00854   struct Object* newObj = heap_allocate_with_payload(oh, object_size(proto), bytes);
00855   object_set_format(newObj, TYPE_BYTE_ARRAY);
00856 
00857   object_set_idhash(newObj, heap_new_hash(oh));
00858   /*copy everything but the header bits*/
00859 
00860   copy_words_into((word_t *) inc_ptr(proto, HEADER_SIZE),
00861                   object_size(proto) - HEADER_SIZE_WORDS,
00862                   (word_t*) inc_ptr(newObj, HEADER_SIZE));
00863 
00864   /*assumption that we are word aligned*/
00865   fill_bytes_with((byte_t*)((word_t*)newObj  + object_size(proto)), (bytes+ sizeof(word_t) - 1) / sizeof(word_t) * sizeof(word_t), 0);
00866 
00867   return (struct ByteArray*) newObj;
00868 }
00869 
00870 
00871 struct ByteArray* heap_new_byte_array_with(struct object_heap* oh, word_t byte_size, byte_t* bytes) {
00872   struct ByteArray* arr = heap_clone_byte_array_sized(oh, get_special(oh, SPECIAL_OOP_BYTE_ARRAY_PROTO), byte_size);
00873   word_t i;
00874   for (i = 0; i < byte_size; i++) {
00875     byte_array_set_element(arr, i, bytes[i]);
00876   }
00877   return arr;
00878 }
00879 
00880 
00881 struct ByteArray* heap_new_string_with(struct object_heap* oh, word_t byte_size, byte_t* bytes) {
00882   struct ByteArray* arr = heap_clone_byte_array_sized(oh, get_special(oh, SPECIAL_OOP_ASCII_PROTO), byte_size);
00883   word_t i;
00884   for (i = 0; i < byte_size; i++) {
00885     byte_array_set_element(arr, i, bytes[i]);
00886   }
00887   return arr;
00888 }
00889 
00890