home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / kaffe-0.5p4-src.tgz / tar.out / contrib / kaffe / kaffevm / gc-incremental.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  6KB  |  290 lines
  1. /*
  2.  * gc-incremental.c
  3.  * The garbage collector.
  4.  *
  5.  * WORK IN PROGRESS - DO NOT USE !!
  6.  *
  7.  * Copyright (c) 1996 Systems Architecture Research Centre,
  8.  *           City University, London, UK.
  9.  *
  10.  * See the file "license.terms" for information on usage and redistribution
  11.  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  12.  *
  13.  * Written by Tim Wilkinson <tim@sarc.city.ac.uk>, August 1996.
  14.  */
  15.  
  16. #define    MDBG(s) s
  17.  
  18. #include "config.h"
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <assert.h>
  22. #include <stdarg.h>
  23. #if defined(HAVE_MALLOC_H)
  24. #include <malloc.h>
  25. #endif
  26. #include "gtypes.h"
  27. #include "access.h"
  28. #include "object.h"
  29. #include "constants.h"
  30. #include "classMethod.h"
  31. #include "thread.h"
  32. #include "gc.h"
  33.  
  34. extern thread* finalman;
  35. extern thread* garbageman;
  36. extern thread* liveThreads;
  37.  
  38. int gcpoolsize = DEFAULT_POOLSIZE;
  39.  
  40. static void* poolBase;        /* Base of malloced pool */
  41. static void* allocBase;        /* Base of allocatable pool */
  42. static void* allocPtr;        /* Current point in allocatable pool */
  43. static void* allocLimit;    /* Limit of allocatable pool */
  44. static uintp allocSize;        /* Size of allocatable pool */
  45. static mapEntry* mapBase;    /* Base of modified map */
  46. static int pgsize;
  47. static freePool freelists[NR_FREELISTS];
  48.  
  49. static gcHead* greyHead;
  50. static gcHead* greyTail;
  51. static gcHead* rootList;
  52. static gcHead dummyObject[1];
  53.  
  54. static void scanMem(void*, void*);
  55. static void garbageCollect(void);
  56.  
  57. /*
  58.  * Initialise garbage system.
  59.  */
  60. void
  61. initGc(void)
  62. {
  63.     uint32 i;
  64.  
  65.     /* Allocate the total GC pool */
  66.     poolBase = malloc(gcpoolsize);
  67.     assert(poolBase != 0);
  68.  
  69.     /* Find the pagesize */
  70. #if defined(HAVE_GETPAGESIZE)
  71.     pgsize = getpagesize();
  72. #else
  73.     pgsize = 1024;    /* A relatively sensible default */
  74. #endif
  75.  
  76.     /* Allocation will be made in units of 64 bytes (object's are
  77.      * at least 32 bytes anyhow).  We will therefore allocate a
  78.      * map with a byte per 64 byte block.  This is used so we can
  79.      * determine which objects have been modified during the mutator's
  80.      * execution and so help with later garbage collection.
  81.      */
  82.     i = gcpoolsize / MAP_UNIT_SIZE;
  83.     i = (i + pgsize - 1) & -pgsize;    /* Round up to pagesize */
  84.  
  85.     mapBase = poolBase;
  86.     allocBase = poolBase + i;
  87.     allocLimit = poolBase + gcpoolsize;
  88.     allocPtr = allocBase;
  89.     allocSize = allocLimit - allocBase;
  90.  
  91.     /* Initialise freelists */
  92.     for (i = 0; i < NR_FREELISTS; i++) {
  93.         freelists[i].first = 0;
  94.         freelists[i].size = MAP_UNIT_SIZE << i;
  95.     }
  96.  
  97.     /* Add a dummy object to the grey list */
  98.     greyHead = dummyObject;
  99.     greyTail = dummyObject;
  100. }
  101.  
  102. /*
  103.  * Primitive object allocation.
  104.  */
  105. void*
  106. newObject(int sz, classes* class, int arraysz, bool root)
  107. {
  108.     freePool* flist;
  109.     object* obj;
  110.     int tsz;
  111.  
  112.     flist = freelists;
  113.  
  114.     tsz = (sz + sizeof(object)) >> MAP_UNIT_SHIFT;
  115.     while (tsz != 0) {
  116.         tsz = tsz >> 1;
  117.         flist++;
  118.     }
  119.  
  120.     /* 'flist' is now a pointer into the relevant freelist */
  121.  
  122.     if (flist->first != 0) {
  123.         obj = (object*)flist->first;
  124.         flist->first = flist->first->next;
  125.     }
  126.     else {
  127.         obj = (object*)allocPtr;
  128.         allocPtr = allocPtr + flist->size;
  129.         if (allocPtr >= allocLimit) {
  130.             assert("Out of space" == 0);
  131.         }
  132.     }
  133.  
  134.     /* Mark the beginning of the object */
  135.     ADDR2MAP(obj)->flags = MAP_ALLOC;
  136.  
  137.     /* Fill in gc details */
  138.     obj->gc.colour = COLOUR_WHITE;
  139.     obj->gc.size = sz;
  140.     obj->gc.nextGrey = 0;
  141.     obj->gc.nextRoot = 0;
  142.  
  143.     /* Fill in object details */
  144.     obj->size = arraysz;
  145.     obj->dtable = (class != 0 ? class->dtable : 0);
  146.  
  147.     /* If object is a root, add it to the root list */
  148.     if (root) {
  149.         obj->gc.nextRoot = rootList;
  150.         rootList = &obj->gc;
  151.     }
  152.  
  153.     {
  154.         static int _cnt = 0;
  155.         if (++_cnt % 100 == 0) {
  156.             garbageCollect();
  157.         }
  158.     }
  159.  
  160.     return (obj);
  161. }
  162.  
  163. /*
  164.  * Garbage collect objects.
  165.  */
  166. static
  167. void
  168. garbageCollect(void)
  169. {
  170.     thread* tid;
  171.     gcHead* ref;
  172.     void* base;
  173.  
  174.     /* Reset with a dummy object */
  175.     greyHead = dummyObject;
  176.     greyTail = dummyObject;
  177.  
  178.     /* Grey the known root objects */
  179.     for (ref = rootList; ref != 0; ref = ref->nextRoot) {
  180.         if (IS_WHITEOBJECT(ref)) {
  181.             GREYOBJECT(ref);
  182. MDBG(            printf("Marking %x\n", ref);            )
  183.         }
  184.     }
  185.  
  186.     /* Scan each live thread, greying the thread objects and scanning
  187.      * the stacks.
  188.      */
  189.     for (tid = liveThreads; tid != 0; tid = tid->PrivateInfo->nextlive) {
  190.         if (IS_WHITEOBJECT(tid)) {
  191.             GREYOBJECT(tid);
  192. MDBG(            printf("Marking %x\n", tid);            )
  193.         }
  194.         scanMem(tid->PrivateInfo->restorePoint, tid->PrivateInfo->stackEnd);
  195.     }
  196.  
  197.     /* Walk down the grey list, scanning each object for references to
  198.      * other objects (skipping the dummy object).
  199.      */
  200.     for (ref = greyHead->nextGrey; ref != 0; ref = ref->nextGrey) {
  201.         base = (void*)(((object*)ref)+1);
  202.         ref->colour = COLOUR_BLACK;
  203.         scanMem(base, base + ref->size);
  204.     }
  205. }
  206.  
  207. /*
  208.  * Scan an area of memory for valid object references.
  209.  */
  210. static
  211. void
  212. scanMem(void* from, void* to)
  213. {
  214.     void** base;
  215.  
  216.     for (base = (void**)from; (void*)base < to; base++) {
  217.         if (VALID_HEAPADDR(*base) && VALID_OBJECT(*base) && IS_WHITEOBJECT(*base)) {
  218.             GREYOBJECT(*base);
  219. MDBG(            printf("Marking %x\n", *base);            )
  220.         }
  221.     }
  222. }
  223.  
  224. /*
  225.  * Finaliser.
  226.  * Finalises any objects which have been garbage collected before
  227.  *   deleting them.
  228.  */
  229. void
  230. finaliserMan(void)
  231. {
  232.     /* All threads start with interrupts disabled */
  233.     intsRestore();
  234.  
  235.     lockMutex(&finalman->obj);
  236.     for (;;) {
  237.         waitCond(&finalman->obj, waitforever);
  238.     }
  239. }
  240.  
  241. /*
  242.  * Garbage collector.
  243.  *  Run the garbage collector.
  244.  */
  245. void
  246. gcMan(void)
  247. {
  248.     /* All threads start with interrupts disabled */
  249.     intsRestore();
  250.  
  251.     lockMutex(&garbageman->obj);
  252.     for (;;) {
  253.                 waitCond(&garbageman->obj, waitforever);
  254.  
  255.         /* Run the garbage collector */
  256.         garbageCollect();
  257.  
  258.         /* If there's garbage, finalise it */
  259.         if (finalman != 0) {
  260.             lockMutex(&finalman->obj);
  261.             signalCond(&finalman->obj);
  262.             unlockMutex(&finalman->obj);
  263.         }
  264.     }
  265. }
  266.  
  267. /*
  268.  * Invoke the garbage collector (if we have one)
  269.  */
  270. void
  271. invokeGarbageCollector(void)
  272. {
  273.     if (garbageman != 0) {
  274.         lockMutex(&garbageman->obj);
  275.         signalCond(&garbageman->obj);
  276.         unlockMutex(&garbageman->obj);
  277.     }
  278. }
  279.  
  280. /*
  281.  * Add an object to the garbage collection system.
  282.  */
  283. void
  284. soft_addtogc(gcHead* obj)
  285. {
  286.     assert(IS_WHITEOBJECT(obj));
  287.     GREYOBJECT(obj);
  288. MDBG(    printf("Adding mark for %x\n", obj);                    )
  289. }
  290.