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-simple.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  11KB  |  509 lines
  1. /*
  2.  * gc-simple.c
  3.  * The garbage collector.
  4.  *
  5.  * Copyright (c) 1996 Systems Architecture Research Centre,
  6.  *           City University, London, UK.
  7.  *
  8.  * See the file "license.terms" for information on usage and redistribution
  9.  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  10.  *
  11.  * Written by Tim Wilkinson <tim@sarc.city.ac.uk>, February 1996.
  12.  */
  13.  
  14. /* #define    NOGC    /* Turn off garbage collection */
  15.  
  16. #define    DBG(s)
  17. #define    MDBG(s)
  18. #define    FDBG(s)
  19. #define    ADBG(s)
  20. #define    RDBG(s)
  21. #define    TDBG(s)
  22.  
  23. #include "config.h"
  24. #include <stdio.h>
  25. #include <stdlib.h>
  26. #include <assert.h>
  27. #include <stdarg.h>
  28. #if defined(HAVE_MALLOC_H)
  29. #include <malloc.h>
  30. #endif
  31. #include "gtypes.h"
  32. #include "access.h"
  33. #include "object.h"
  34. #include "constants.h"
  35. #include "classMethod.h"
  36. #include "baseClasses.h"
  37. #include "lookup.h"
  38. #include "thread.h"
  39. #include "gc.h"
  40. #include "locks.h"
  41. #include "slots.h"
  42. #include "external.h"
  43. #include "errors.h"
  44. #include "machine.h"
  45. #include "md.h"
  46. #include "flags.h"
  47.  
  48. extern classes* ThreadClass;
  49. extern strpair* finalpair;
  50. extern thread* finalman;
  51. extern thread* garbageman;
  52. extern thread* liveThreads;
  53. extern thread* currentThread;
  54.  
  55. static gcRef* refTable[GCREFTABLESZ];
  56. static int refTableIdx;
  57. static gcRef* freeRef;
  58. static gcRef* permList;
  59. static void* minGcMemory = (void*)-1;
  60. static void* maxGcMemory = (void*)0;
  61. static gcRef* garbageObjects;
  62. static gcRef* walkTail;
  63.  
  64. static struct {
  65.     int    mark;
  66.     int    total;
  67.     int64    time;
  68. } gcStats;
  69.  
  70. static void markObject(object*);
  71. static void walkObject(gcRef*);
  72. static void garbageCollect(void);
  73. static gcRef* validReference(object*);
  74.  
  75. extern int64 currentTime(void);
  76.  
  77. /*
  78.  * Initialise garbage system.
  79.  */
  80. void
  81. initGc(void)
  82. {
  83.     /* Does nothing */
  84. }
  85.  
  86. /*
  87.  * Primitive object allocation.
  88.  */
  89. void*
  90. newObject(int sz, classes* class, int arraysz, bool perm)
  91. {
  92.     static uintp allocSize = 0;
  93.     object* obj;
  94.     gcRef* table;
  95.     gcRef* ref;
  96.     int i;
  97.  
  98.     sz += sizeof(object);
  99.  
  100. ADBG(    printf("newObject size %d\n", sz);            )
  101.  
  102.     obj = (object*)calloc(sz, sizeof(char));
  103.     if (obj == 0) {
  104.         throwException(OutOfMemoryError);
  105.     }
  106.  
  107.     /* Invoke garbage collection when necessary */
  108.     allocSize += sz;
  109.     if (allocSize > GCTRIGSIZE) {
  110.         allocSize = 0;
  111.         invokeGarbageCollector();
  112.     }
  113.  
  114.     /* Fill in object information */
  115.     obj->size = arraysz;
  116.     obj->dtable = (class != 0 ? class->dtable : 0);
  117.  
  118. #if defined(NOGC)
  119.     return (obj);
  120. #endif
  121.  
  122.     /* Reset min and max memory pointers */
  123.     if ((void*)obj < minGcMemory) {
  124.         minGcMemory = (void*)obj;
  125.     }
  126.     if ((void*)obj > maxGcMemory) {
  127.         maxGcMemory = (void*)obj;
  128.     }
  129.  
  130.     ref = freeRef;
  131.     if (ref != 0) {
  132.         freeRef = freeRef->next;
  133.     }
  134.     else {
  135.         assert(refTableIdx < GCREFTABLESZ);
  136.         table = malloc(sizeof(gcRef) * GCREFMAX);
  137.         assert(table != 0);
  138.  
  139.         /* Build into free list */
  140.         for (i = 0; i < GCREFMAX; i++) {
  141.             table[i].flags = GC_FREE;
  142.             table[i].next = &table[i+1];
  143.             table[i].idx = i + (refTableIdx * GCREFMAX);
  144.         }
  145.         table[GCREFMAX-1].next = 0;
  146.         freeRef = &table[1];
  147.         ref = &table[0];
  148.  
  149.         refTable[refTableIdx] = table;
  150.         refTableIdx++;
  151.     }
  152.  
  153.     assert(ref->flags == GC_FREE);
  154.  
  155.     /* Make ref point at object, and object point at ref */
  156.     obj->gc.idx = ref->idx;
  157.     ref->obj = obj;
  158.     ref->flags = GC_UNMARK;
  159.     ref->next = 0;
  160.  
  161.     /* If object is permenant, put it on the perm list */
  162.     if (perm == true) {
  163.         ref->next = permList;
  164.         permList = ref;
  165.     }
  166.  
  167.     gcStats.total++;
  168.  
  169. RDBG(    printf("Adding new object 0x%x at index %d - %s\n", obj, obj->gc.idx, obj->dtable ? obj->dtable->class->name : "<none>"); )
  170.  
  171.     return (obj);
  172. }
  173.  
  174. /*
  175.  * Invoke the garbage collector (if we have one)
  176.  */
  177. void
  178. invokeGarbageCollector(void)
  179. {
  180. #if defined(NOGC)
  181.     return;
  182. #endif
  183.     if (garbageman != 0) {
  184.         lockMutex(&garbageman->obj);
  185.         signalCond(&garbageman->obj);
  186.         unlockMutex(&garbageman->obj);
  187.     }
  188. }
  189.  
  190. /*
  191.  * Is object reference a real object?
  192.  */
  193. static
  194. gcRef*
  195. validReference(object* o)
  196. {
  197.     gcRef* ref;
  198.  
  199.     /* Null references are not objects */
  200.     if (o == 0) {
  201.         return (0);
  202.     }
  203.  
  204.     /* Validate object address.  To be a real object it must lie
  205.        inside the malloced memory pool, and its index must refer to
  206.        a GC entry which refers to it. */
  207.     if ((void*)o < minGcMemory || (void*)o > maxGcMemory) {
  208.         return (0);
  209.     }
  210.  
  211.     /* Check alignment - should be pointer aligned */
  212.     if (((uintp)o) % sizeof(void*) != 0) {
  213.         return (0);
  214.     }
  215.     ref = refTable[(o->gc.idx / GCREFMAX) % GCREFTABLESZ];
  216.     if (ref == 0) {
  217.         return (0);
  218.     }
  219.     ref = &ref[o->gc.idx % GCREFMAX];
  220.     if (ref->obj != o) {
  221.         return (0);
  222.     }
  223.  
  224.     /*
  225.      * If object is unmarked, then we should return it and
  226.      * let the system recurse though it.  If not, we should
  227.      * return 0 so the system will not recurse.
  228.      */
  229.     if (ref->flags == GC_UNMARK || ref->flags == GC_UNMARK2) {
  230.         return (ref);
  231.     }
  232.     else {
  233.         return (0);
  234.     }
  235. }
  236.  
  237. /*
  238.  * Garbage collect objects.
  239.  */
  240. static
  241. void
  242. garbageCollect(void)
  243. {
  244.     int i;
  245.     thread* tid;
  246.     object** ptr;
  247.     gcRef* ref;
  248.     int j;
  249.     gcRef* table;
  250.     int64 tms;
  251.     int64 tme;
  252.  
  253. #if defined(NOGC)
  254.     return;
  255. #endif
  256.  
  257. DBG(    printf("Garbage collecting ... \n");                )
  258.  
  259.     tms = currentTime();
  260.     gcStats.mark = 0;
  261.  
  262.     /* Scan the permentant object list */
  263.     assert(permList != 0);
  264.     walkTail = permList;
  265.     walkTail->flags = GC_MARK;
  266.     for (ref = permList->next; ref != 0; ref = ref->next) {
  267.         markObject(ref->obj);
  268.     }
  269.  
  270.         /* Scan each live thread */
  271.     for (tid = liveThreads; tid != 0; tid = tid->PrivateInfo->nextlive) {
  272.         markObject(&tid->obj);
  273.         for (ptr = (object**)tid->PrivateInfo->restorePoint; ptr < (object**)tid->PrivateInfo->stackEnd; ptr++) {
  274.             markObject(*ptr);
  275.         }
  276.     }
  277.  
  278.     /* Now scan walk list - which will add more to the walk list - until
  279.      * it is exausted.
  280.      */
  281.     for (ref = permList; ref != walkTail; ref = ref->walk) {
  282.         walkObject(ref);
  283.     }
  284.     walkObject(ref);    /* And the last one */
  285.  
  286.     /* Look through object table for unmarked objects which must be
  287.      * finalises.  Attach them to the garbage list and then reference
  288.      * them (so any objects the reference are not garbaged).
  289.      */
  290.     for (j = 0; j < refTableIdx; j++) {
  291.         table = refTable[j];
  292.         for (i = 0; i < GCREFMAX; i++) {
  293.             if (table[i].flags == GC_UNMARK &&
  294.                 table[i].obj->dtable->class->final == true) {
  295.                 markObject(table[i].obj);
  296.                 table[i].flags = GC_GARBAGE;
  297.                 table[i].next = garbageObjects;
  298.                 garbageObjects = &table[i];
  299.             }
  300.         }
  301.     }
  302.  
  303.     /* Continue to scan walk list until it is exausted again.  We've
  304.      * already done the current 'ref' so skip it.
  305.      */
  306.     while (ref != walkTail) {
  307.         ref = ref->walk;
  308.         walkObject(ref);
  309.     }
  310.  
  311.     /* Now look through object table for objects which have not
  312.        been marked.  These can be freed. */
  313.     for (j = 0; j < refTableIdx; j++) {
  314.         table = refTable[j];
  315.         for (i = 0; i < GCREFMAX; i++) {
  316.             switch(table[i].flags) {
  317.             case GC_GARBAGE:
  318.             case GC_GARBAGE2:
  319.             case GC_FREE:
  320.                 break;
  321.  
  322.             case GC_MARK:
  323.                 table[i].flags = GC_UNMARK; /* For next time */
  324.                 break;
  325.  
  326.             case GC_UNMARK:
  327.                 assert(table[i].obj->dtable->class->final == false);
  328.                 table[i].flags = GC_GARBAGE2;
  329.                 table[i].next = garbageObjects;
  330.                 garbageObjects = &table[i];
  331.                 break;
  332.  
  333.             case GC_UNMARK2:
  334.                 /* Object not marked - free */
  335.                 table[i].flags = GC_GARBAGE2;
  336.                 table[i].next = garbageObjects;
  337.                 garbageObjects = &table[i];
  338.                 break;
  339.             }
  340.         }
  341.     }
  342.  
  343. DBG(    printf("Garbage collecting ... done.\n");            )
  344.  
  345.     if (flag_gc) {
  346.         tme = currentTime();
  347.         gcStats.time += (tme - tms);
  348.         fprintf(stderr, "<GC: total %d, marked %d, freeing %d, time %dms (%dms)>\n", gcStats.total, gcStats.mark, gcStats.total - gcStats.mark, (int)(tme - tms), (int)gcStats.time);
  349.     }
  350. }
  351.  
  352. /*
  353.  * Given an object, mark it and follow any object references it contains.
  354.  */
  355. static
  356. void
  357. markObject(object* o)
  358. {
  359.     gcRef* ref;
  360.  
  361.     /* Null object, invalid object or already visited? */
  362.     ref = validReference(o);
  363.     if (ref == 0) {
  364.         return;
  365.     }
  366.  
  367. MDBG(    printf("Marking object 0x%x at index %d - %s\n", o, o->gc.idx, o->dtable ? o->dtable->class->name : "<none>"); )
  368.  
  369.     /* Mark and add to walk list */
  370.     walkTail->walk = ref;
  371.     walkTail = ref;
  372.     ref->flags = GC_MARK;
  373.  
  374.     gcStats.mark++;
  375. }
  376.  
  377. static
  378. void
  379. walkObject(gcRef* ref)
  380. {
  381.     int i;
  382.     classes* class;
  383.     object** objdata;
  384.  
  385.     class = ref->obj->dtable->class;
  386.  
  387.     /* Mark the class object */
  388.     markObject(&class->head);
  389.  
  390.     /* If this is a class object, mark the static fields and constants */
  391.     if (class == ClassClass) {
  392.         class = (classes*)ref->obj;
  393.         markObject(&class->superclass->head);
  394.         objdata = (object**)class->staticFields;
  395.         for (i = 0; i < class->sfsize; i++) {
  396.             markObject(objdata[i]);
  397.         }
  398.         if (class->constants != 0) {
  399.             objdata = (object**)class->constants->data;
  400.             for (i = class->constants->size - 1; i >= 0; i--) {
  401.                 markObject(objdata[i]);
  402.             }
  403.         }
  404.     }
  405.     /* Otherwise, if a normal object ... */
  406.     else if (class->sig[0] == 'L') {
  407.         objdata = (object**)(ref->obj+1);
  408.         for (i = 0; i < class->fsize; i++) {
  409.             markObject(objdata[i]);
  410.         }
  411.     }
  412.     /* Otherwise, if a array of objects ... */
  413.     else if (class->sig[0] == '[' &&
  414.          (class->sig[1] == 'L' || class->sig[1] == '[')) {
  415.         objdata = (object**)(ref->obj+1);
  416.         for (i = 0; i < ref->obj->size; i++) {
  417.             markObject(objdata[i]);
  418.         }
  419.     }
  420. }
  421.  
  422. /*
  423.  * Finaliser.
  424.  * Finalises any objects which have been garbage collected before
  425.  *   deleting them.
  426.  */
  427. void
  428. finaliserMan(void)
  429. {
  430.     object* obj;
  431.     gcRef* ref;
  432.     methods* meth;
  433.  
  434.     /* All threads start with interrupts disabled */
  435.     intsRestore();
  436.  
  437.     lockMutex(¤tThread->obj);
  438.     for (;;) {
  439.         while (garbageObjects) {
  440.             ref = garbageObjects;
  441.             garbageObjects = garbageObjects->next;
  442.  
  443.             assert(ref->flags == GC_GARBAGE || ref->flags == GC_GARBAGE2);
  444.             obj = ref->obj;
  445.  
  446.             /* Finalise object if necessary */
  447.             if (ref->flags == GC_GARBAGE) {
  448.                 meth = findMethod(obj->dtable->class, finalpair);
  449.                 assert(meth != 0);
  450. FDBG(                printf("Finalise object 0x%x(%d) %s\n", obj,
  451.                 ref->idx, obj->dtable->class->name);        )
  452.                 CALL_KAFFE_FUNCTION(meth, obj);
  453.                 /* Don't free it cause it might live */
  454.                 ref->flags = GC_UNMARK2;
  455.                 ref->next = 0;
  456.                 continue;
  457.             }
  458.             /* Special handling for threads */
  459.             if (obj->dtable->class == ThreadClass) {
  460.                 free(((thread*)obj)->PrivateInfo);
  461. TDBG(                printf("Freeing thread 0x%x(%d)\n",
  462.                     obj, ref->idx);            )
  463.  
  464.             }
  465.             /* Don't handle classes yet */
  466.             assert(obj->dtable->class != ClassClass);
  467.  
  468.             /* Put entry onto freelist */
  469.             ref->flags = GC_FREE;
  470.             ref->next = freeRef;
  471.             freeRef = ref;
  472.  
  473.             /* Free the object */
  474. FDBG(            printf("Freeing object 0x%x(%d) %s\n", obj,
  475.                 ref->idx, obj->dtable->class->name);    )
  476.             free(obj);
  477.  
  478.             gcStats.total--;
  479.         }
  480.         waitCond(¤tThread->obj, waitforever);
  481.     }
  482. }
  483.  
  484. /*
  485.  * Garbage collector.
  486.  *  Run the garbage collector.
  487.  */
  488. void
  489. gcMan(void)
  490. {
  491.     /* All threads start with interrupts disabled */
  492.     intsRestore();
  493.  
  494.     lockMutex(¤tThread->obj);
  495.     for (;;) {
  496.                 waitCond(¤tThread->obj, waitforever);
  497.  
  498.         /* Run the garbage collector */
  499.         garbageCollect();
  500.  
  501.         /* If there's garbage, finalise it */
  502.         if (garbageObjects != 0 && finalman != 0) {
  503.             lockMutex(&finalman->obj);
  504.             signalCond(&finalman->obj);
  505.             unlockMutex(&finalman->obj);
  506.         }
  507.     }
  508. }
  509.