home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / smalltalk-1.1.1 / mstoop.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-12  |  30.2 KB  |  1,275 lines
  1. /***********************************************************************
  2.  *
  3.  *    Object Table maintenance module.
  4.  *
  5.  ***********************************************************************/
  6.  
  7. /***********************************************************************
  8.  *
  9.  * Copyright (C) 1990, 1991 Free Software Foundation, Inc.
  10.  * Written by Steve Byrne.
  11.  *
  12.  * This file is part of GNU Smalltalk.
  13.  *
  14.  * GNU Smalltalk is free software; you can redistribute it and/or modify it
  15.  * under the terms of the GNU General Public License as published by the Free
  16.  * Software Foundation; either version 1, or (at your option) any later 
  17.  * version.
  18.  * 
  19.  * GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20.  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
  21.  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  22.  * more details.
  23.  * 
  24.  * You should have received a copy of the GNU General Public License along with
  25.  * GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26.  * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27.  *
  28.  ***********************************************************************/
  29.  
  30.  
  31. /*
  32.  *    Change Log
  33.  * ============================================================================
  34.  * Author      Date       Change 
  35.  * sbyrne     8 Apr 90      Changed oopFree to oopValid to fix the bug with
  36.  *              someInstance losing after GC's due to objects that
  37.  *              have non-free OOP table entries, but point to freed
  38.  *              objects.
  39.  *
  40.  * sbyrne     7 Apr 90      Increased mem space size to 4M.  This can be
  41.  *              decreased as necessary.
  42.  *
  43.  * sbyrne    24 Feb 90      Update to change log: there are no longer any
  44.  *              explicitly allocated OOPs due to the new symbol table
  45.  *              structure; the comment below is now a noop.
  46.  *
  47.  * sbyrne    20 Sep 89      Added oop table slot GC'ing.  I'm not dealing with
  48.  *              oop table slots that are explictly allocated; I
  49.  *              believe that most OOP slots are not explicitly chosen
  50.  *              and so not running the incremental reclaimer for that
  51.  *              case shouldn't hurt us.
  52.  *
  53.  * sbyrne    12 Sep 89      Much of the garbage collector's operation depends on
  54.  *              the fact that only 1 flip will occur between any two
  55.  *              operations (such as a compilation, or a byte-code).
  56.  *              The code would be much more complex if this were not
  57.  *              the case, and I'm not sure that things would even be
  58.  *              possible if this were not the case.  Anyway, there is
  59.  *              code in this routine to check for that eventuality
  60.  *              and to halt the system if it occurs.
  61.  *
  62.  * sbyrne     6 Sep 89      started implementing the garbage collector (YAY!!!)
  63.  *
  64.  * sbyrne    13 Jan 89      Created.
  65.  *
  66.  */
  67.  
  68.  
  69. #include <stdio.h>
  70. #include "mst.h"
  71. #include "mstoop.h"
  72. #include "mstdict.h"
  73. #include "mstsave.h"
  74. #include "mstcomp.h"
  75.  
  76. /* Size of the object semi spaces, in bytes */
  77. #define    K        1024
  78.  
  79. #ifndef atarist
  80. #define MEM_SPACE_SIZE        (4 * K * K) 
  81. #else
  82. #define MEM_SPACE_SIZE        (1152 * K) 
  83. #endif
  84.  
  85. #define oopReclaimFactor    4 /* how many oops to reclaim per oop alloc */
  86. /* #define INLINE_MACROS */
  87.  
  88.  
  89. /* Define this flag to turn on debugging code for OOP table management */
  90. /* #define OOP_DEBUGGING */
  91.  
  92.  
  93.  
  94. #define alignSize(size) \
  95.  ( ((size) + DOUBLE_ALIGNMENT - 1) & ~(DOUBLE_ALIGNMENT - 1) )
  96.  
  97. #define objSpace(obj) \
  98.   ((char *)(obj) >= spaces[1].space)
  99.  
  100.  
  101. typedef struct CompiledMethodStruct *Method;
  102.  
  103. extern Boolean        regressionTesting;
  104.  
  105. /* These are the real OOPS for nil, true, and false */
  106. OOP            nilOOP, trueOOP, falseOOP;
  107.  
  108. /* The OOP table.  This contains a pointer to the object, and some flag
  109.    bits indicating which semispace the pointed-to object lives in.  Some
  110.    of the bits indicate the difference between the allocated length (stored 
  111.    in the object itself, and the real length, for things like byte strings 
  112.    that may not be an even multiple of 4 (== sizeof(void *)). */
  113. struct OOPStruct    oopTable[TOTAL_OOP_TABLE_SLOTS];
  114.  
  115. /* This is the head of the free list.  The free list is maintained in the 
  116.    oop table.  Each OOP on the free list has a bit indicating that it's free,
  117.    a pointer to the next free OOP, and a pointer to the previous free OOP.
  118.    when this points at NIL, we're out of space */
  119. OOP            freeOOPs;
  120. int            numFreeOOPs;
  121.  
  122. /* The indices of which is the current new space (toSpace) and which is
  123.    the current old space (fromSpace).  At GC flip time, these two are 
  124.    interchanged. */
  125. char/*int*/        fromSpace, toSpace;
  126.  
  127. Boolean            gcFlipped, gcState, gcMessage;
  128. int            gcFlipCounter;
  129.  
  130.  
  131. /* This vector holds the storage for all the Character objects in the system.
  132.    Since all character objects are unique, we pre-allocate space for 256 of
  133.    them, and treat them as special built-ins when doing garbage collection.*/
  134. CharObject        charObjectTable[NUM_CHAR_OBJECTS];
  135.  
  136. /* This is "nil" object in the system.  That is, the single instance of the
  137.    UndefinedObject class, which is called "nil". */
  138. struct NilObjectStruct    nilObject;
  139.  
  140. /* These represent the two boolean objects in the system, true and false.
  141.    This is the object storage for those two objects. 
  142.    false == &booleanObjects[0], true == &booleanObjects[1] */
  143. struct BooleanObjectStruct booleanObjects[2];
  144.  
  145. struct memorySpaceStruct {
  146.   char        *space;
  147.   char        *allocPtr;
  148.   char        *copyPtr;
  149.   char        *scanPtr;
  150.   unsigned long    size;
  151. };
  152.  
  153. /* These two variables represent information about the semispaces.  spaces
  154.    holds the information for each semispace (basically the pointer to the
  155.    base of the space, and the pointers into it for allocation, copying, and
  156.    scanning.  curSpace holds the address of one of the two semispace data
  157.    structures, and is used by the garbage collector */
  158. static struct memorySpaceStruct spaces[2];
  159. static struct memorySpaceStruct *curSpace;
  160.  
  161. static Object        curObject;
  162. static long        curObjectSize, copyQuota;
  163. static double        copyRate;
  164. static double        copyRateAdjustment = 1.50; /* copy 50% more than last time */
  165. static long        oopTableIndex;
  166.  
  167. static Object        moveObject();
  168. static void        initCharObject(), moveRootOOPs(),
  169.             initSpace(), markBuiltinOOPs(), 
  170.             copyReferencedObjects(), finishOOPScan(), clearOldOOPs();
  171.  
  172. #ifdef remove_soon /* Tue May 15 01:23:08 1990 */
  173. /**/static char marks[TOTAL_OOP_TABLE_SLOTS];
  174. /**/static void zeroMarks();
  175. /**/static int traceOOPStuff = 0;
  176. #endif /* remove_soon Tue May 15 01:23:08 1990 */
  177. /*
  178.  *    void initOOPTable()
  179.  *
  180.  * Description
  181.  *
  182.  *    Initialize the OOP table.  Initially, all the OOPs are on the OOP free
  183.  *    list so that's just how we initialize them.  We do as much
  184.  *    initialization as we can, but we're called before classses are
  185.  *    defined, so things that have definite classes must wait until
  186.  *    the classes are defined.
  187.  *
  188.  */
  189. void initOOPTable()
  190. {
  191.   int        i;
  192.  
  193. #ifdef remove_soon /* Mon May 14 23:41:50 1990 */
  194. /**/zeroMarks();
  195. #endif /* remove_soon Mon May 14 23:41:50 1990 */
  196.  
  197.   numFreeOOPs = OOP_TABLE_SIZE;
  198.  
  199.   for (i = 0; i < OOP_TABLE_SIZE; i++) {
  200.     oopTable[i].object = (Object)&oopTable[i+1];
  201.     oopTable[i].isFree = 1;    /* setting this free bit */
  202.   }
  203.   oopTable[i-1].object = nil;
  204.  
  205.   freeOOPs = oopTable;
  206.  
  207.   nilOOP    = &oopTable[nilOOPIndex];
  208.   trueOOP    = &oopTable[trueOOPIndex];
  209.   falseOOP    = &oopTable[falseOOPIndex];
  210.  
  211.   nilOOP->isFree        = trueOOP->isFree    = falseOOP->isFree    = 0;
  212.   nilOOP->emptyBytes    = trueOOP->emptyBytes    = falseOOP->emptyBytes    = 0;
  213.  
  214.   nilOOP->object    = (Object)&nilObject;
  215.   nilObject.objSize    = ROUNDED_WORDS(sizeof(struct NilObjectStruct));
  216.  
  217.   trueOOP->object        = (Object)&booleanObjects[0];
  218.   falseOOP->object        = (Object)&booleanObjects[1];
  219.   booleanObjects[0].objSize    = ROUNDED_WORDS(sizeof(struct BooleanObjectStruct));
  220.   booleanObjects[1].objSize    = ROUNDED_WORDS(sizeof(struct BooleanObjectStruct));
  221.   booleanObjects[0].booleanValue= trueOOP;
  222.   booleanObjects[1].booleanValue= falseOOP;
  223. }
  224.  
  225.  
  226. /*
  227.  *    void initNil()
  228.  *
  229.  * Description
  230.  *
  231.  *    Initialize the "nil" object.
  232.  *
  233.  */
  234. void initNil()
  235. {
  236.   nilObject.objClass    = undefinedObjectClass;
  237. }
  238.  
  239. /*
  240.  *    void initBooleans()
  241.  *
  242.  * Description
  243.  *
  244.  *    Initialize the two boolean objects, after their respective classes have
  245.  *    been created.
  246.  *
  247.  */
  248. void initBooleans()
  249. {
  250.   booleanObjects[0].objClass    = trueClass;
  251.   booleanObjects[1].objClass    = falseClass;
  252. }
  253.  
  254. /*
  255.  *    void initCharTable()
  256.  *
  257.  * Description
  258.  *
  259.  *    Initialize the instances of the class Character, after that class has
  260.  *    been created.
  261.  *
  262.  */
  263. void initCharTable()
  264. {
  265.   int        i;
  266.  
  267.   for (i = 0; i < NUM_CHAR_OBJECTS; i++) {
  268.     initCharObject(i);
  269.     oopTable[i + CHAR_OBJECT_BASE].object = (Object)&charObjectTable[i];
  270.     oopTable[i + CHAR_OBJECT_BASE].isFree = 0;
  271.     oopTable[i + CHAR_OBJECT_BASE].emptyBytes = 0;
  272.   }
  273. }
  274.  
  275. /*
  276.  *    static void initCharObject(i)
  277.  *
  278.  * Description
  279.  *
  280.  *    Initialize a single character object.
  281.  *
  282.  * Inputs
  283.  *
  284.  *    i     : The index of the character object, in the range 0..255.
  285.  *
  286.  */
  287. static void initCharObject(i)
  288. int    i;
  289. {
  290.   charObjectTable[i].objSize = ROUNDED_WORDS(sizeof(CharObject));
  291.   charObjectTable[i].objClass = charClass;
  292.   charObjectTable[i].charVal = i;
  293. }
  294.  
  295. /*
  296.  *    void fixupMetaclassObjects()
  297.  *
  298.  * Description
  299.  *
  300.  *    Called after the fundamental class hierarchy has been defined, this
  301.  *    function goes through and fixes up all the objects in the oop table
  302.  *    that don't have a objClass (objClass == nilOOP).  It's a
  303.  *    chicken-and-egg problem: the metaclassClass doesn't yet exist when the
  304.  *    hierarchy is put together, so after it's created, we have to go back
  305.  *    and fix all the metaclasses that we created.
  306.  *
  307.  */
  308. void fixupMetaclassObjects()
  309. {
  310.   int        i;
  311.  
  312.   for (i = 0; i < OOP_TABLE_SIZE; i++) {
  313.     if (!oopTable[i].isFree && isNil(oopTable[i].object->objClass)) {
  314.       oopTable[i].object->objClass = metaclassClass;
  315.     }
  316.   }
  317. }
  318.  
  319. /*
  320.  *    OOP findAnInstance(classOOP)
  321.  *
  322.  * Description
  323.  *
  324.  *    Finds and returns an instance of the class CLASSOOP.  Returns "nil" if
  325.  *    there are no instances present.
  326.  *
  327.  * Inputs
  328.  *
  329.  *    classOOP: 
  330.  *        OOP for a class for which to find an instance
  331.  *
  332.  * Outputs
  333.  *
  334.  *    The first instance of the given class in the OOP table.
  335.  */
  336. OOP findAnInstance(classOOP)
  337. OOP    classOOP;
  338. {
  339.   int        i;
  340.  
  341.   for (i = 0; i < OOP_TABLE_SIZE; i++) {
  342.     if (!oopTable[i].isFree && oopTable[i].object->objClass == classOOP) {
  343.       return (&oopTable[i]);
  344.     }
  345.   }
  346.  
  347.   return (nilOOP);
  348. }
  349.  
  350. /*
  351.  *    long oopIndex(oop)
  352.  *
  353.  * Description
  354.  *
  355.  *    Returns the index within the OOP table of the given OOP.
  356.  *
  357.  * Inputs
  358.  *
  359.  *    oop   : OOP to return index of
  360.  *
  361.  * Outputs
  362.  *
  363.  *    Returned index in the OOP table, in range 0..TOTAL_OOP_TABLE_SLOTS.
  364.  */
  365. long oopIndex(oop)
  366. OOP    oop;
  367. {
  368.   return (oop - oopTable);
  369. }
  370.  
  371. /*
  372.  *    Boolean oopIndexValid(index)
  373.  *
  374.  * Description
  375.  *
  376.  *    Checks to see if index represents a valid OOP.
  377.  *
  378.  * Inputs
  379.  *
  380.  *    index : a long index into the OOP table, apparently 1 based due to
  381.  *        being called from Smalltalk via a primitive.
  382.  *
  383.  * Outputs
  384.  *
  385.  *    True if the index represents a valid OOP table element, false
  386.  *    otherwise.
  387.  */
  388. Boolean oopIndexValid(index)
  389. long    index;
  390. {
  391.   return (index >= 1 && index <= TOTAL_OOP_TABLE_SLOTS);
  392. }
  393.  
  394. #ifndef INLINE_MACROS
  395.  
  396. OOP oopAt(index)
  397. long    index;
  398. {
  399.   return (oopAtMac(index));
  400. }
  401.  
  402. #endif  /* INLINE_MACROS */
  403.  
  404. void swapObjects(oop1, oop2)
  405. OOP    oop1, oop2;
  406. {
  407.   struct OOPStruct tempOOP;
  408.  
  409.   tempOOP = *oop2;
  410.   *oop2 = *oop1;
  411.   *oop1 = tempOOP;
  412. }
  413.  
  414. OOP charOOPAt(c)
  415. Byte    c;
  416. {
  417.   return (&oopTable[c + CHAR_OBJECT_BASE]);
  418. }
  419.  
  420. Byte charOOPValue(charOOP)
  421. OOP    charOOP;
  422. {
  423.   return (charOOP - &oopTable[CHAR_OBJECT_BASE]);
  424. }
  425.  
  426. void printObject(oop)
  427. OOP    oop;
  428. {
  429.   if (isInt(oop)) {
  430.     printf("%d", toInt(oop));
  431.   } else if (isNil(oop)) {
  432.     printf("nil");
  433.   } else if (oop == trueOOP) {
  434.     printf("true");
  435.   } else if (oop == falseOOP) {
  436.     printf("false");
  437.   } else if (oopClass(oop) == charClass) {
  438.     printf("$%c", charOOPValue(oop));
  439.   } else if (oopClass(oop) == floatClass) {
  440.     printf("%#g", floatOOPValue(oop));
  441.   } else if (oopClass(oop) == symbolClass) {
  442.     printf("#"); printSymbol(oop);
  443.   } else if (oopClass(oop) == stringClass) {
  444.     /* ### have to quote embedded quote chars */
  445.     printf("'");
  446.     printString(oop);
  447.     printf("'");
  448.   } else {
  449.     printOOPConstructor(oop);
  450.   }
  451. }
  452.  
  453. Boolean oopValid(oop)
  454. OOP    oop;
  455. {
  456.   return (!oop->isFree && (oop->oddMark || oop->evenMark));
  457. }
  458.  
  459. #ifndef INLINE_MACROS
  460.  
  461. Boolean oopAvailable(index)
  462. long    index;
  463. {
  464.   return (oopAvailableMac(index);
  465. }
  466.  
  467. #endif /* INLINE_MACROS */
  468.  
  469. /*
  470.  *    OOP allocOOP(obj)
  471.  *
  472.  * Description
  473.  *
  474.  *    Given an object OBJ, this routine allocates an OOP table slot for it
  475.  *    and returns it.  It marks the OOP so that it indicates the object is in
  476.  *    new space, and that the oop has been referenced on this pass (to keep
  477.  *    the OOP table reaper from reclaiming this OOP).
  478.  *
  479.  * Inputs
  480.  *
  481.  *    obj   : Object that the new OOP should point to.
  482.  *
  483.  * Outputs
  484.  *
  485.  *    An OOP, which is the address of an element in the OOP table.
  486.  */
  487. OOP allocOOP(obj)
  488. Object    obj;
  489. {
  490.   OOP        oop;
  491.   int        i;
  492.  
  493.   for (i = 0; i < oopReclaimFactor; i++) {
  494.     if (oopTableIndex >= OOP_TABLE_SIZE) {
  495.       break;
  496.     }
  497.     oop = &oopTable[oopTableIndex++];
  498.     if (!oop->isFree) {
  499.       if (!oop->evenMark && !oop->oddMark) {
  500. #ifdef remove_soon /* Mon May 14 23:42:47 1990 */
  501. /**/if (traceOOPStuff) {
  502. /**/printf("freeing %d\n", oopTableIndex - 1);
  503. /**/}
  504. #endif /* remove_soon Mon May 14 23:42:47 1990 */
  505. #ifdef remove_soon /* Tue May 15 02:23:58 1990 */
  506. /**/    if (marks[oopTableIndex - 1]) {
  507. /**/      printf("freeling link %d\n", oopTableIndex -1 );
  508. /**/    }
  509. #endif /* remove_soon Tue May 15 02:23:58 1990 */
  510.     /* we've found a dead one...add it to the free list */
  511.     numFreeOOPs++;
  512.     oop->object = (Object)freeOOPs;
  513.     freeOOPs = oop;
  514.     freeOOPs->isFree = true;
  515.       } else if (toSpace) {
  516. #ifdef remove_soon /* Mon May 14 23:42:54 1990 */
  517. /**/if (oop == &oopTable[100]) {    /* ### */
  518. /**/printf("clearing 101 even\n");
  519. /**/}
  520. #endif /* remove_soon Mon May 14 23:42:54 1990 */
  521.     oop->evenMark = 0;
  522. #ifdef remove_soon /* Tue May 15 02:23:47 1990 */
  523. /**/    if (marks[oopTableIndex - 1]) {
  524. /**/      printf("even marking %d\n", oopTableIndex -1 );
  525. /**/    }
  526. #endif /* remove_soon Tue May 15 02:23:47 1990 */
  527.       } else {
  528. #ifdef remove_soon /* Mon May 14 23:42:59 1990 */
  529. /**/if (oop == &oopTable[100]) {    /* ### */
  530. /**/printf("clearing 101 odd\n");
  531. /**/}
  532. #endif /* remove_soon Mon May 14 23:42:59 1990 */
  533.     oop->oddMark = 0;
  534. #ifdef remove_soon /* Tue May 15 02:23:31 1990 */
  535. /**/    if (marks[oopTableIndex - 1]) {
  536. /**/      printf("odd marking %d\n", oopTableIndex -1);
  537. /**/    }
  538. #endif /* remove_soon Tue May 15 02:23:31 1990 */
  539.       }
  540. #ifdef remove_soon /* Mon May 14 23:42:19 1990 */
  541. /**/if (traceOOPStuff) 
  542. /**/{ int i;
  543. /**/
  544. /**/  i = oop - oopTable;
  545. /**/if (marks[i] != 0) {
  546. /**/  printf("AllocOOP: oop %d value %d even %d odd %d\n", i, marks[i],
  547. /**/     oop->evenMark, oop->oddMark);
  548. /**/}
  549. /**/marks[i] = 2;            /* mark as freed */
  550. /**/}
  551. #endif /* remove_soon Mon May 14 23:42:19 1990 */
  552.     }
  553.   }
  554.  
  555.   oop = freeOOPs;
  556.  
  557.   numFreeOOPs--;
  558.  
  559.   if (oop == nil) {
  560.     errorf("Ran out of OOP Table slots!!!");
  561.     exit(1);
  562.     /* ### this needs to be fixed */
  563.   }
  564.  
  565.   if (!oop->isFree) {
  566.     errorf("Allocating allocated OOP!!!");
  567.     exit(0);
  568.   }
  569.  
  570.   freeOOPs = (OOP)oop->object;
  571.  
  572.   if (objSpace(obj) != toSpace) {
  573.     obj = moveObject(obj);
  574.   }
  575.  
  576. #ifdef remove_soon /* Mon May 14 23:43:09 1990 */
  577. /**/if (oop == &oopTable[100] || oop == &oopTable[123]) {    /* ### */
  578. /**/printf("allocating %d\n", oop - oopTable);
  579. /**/debug();
  580. /**/}
  581. #endif /* remove_soon Mon May 14 23:43:09 1990 */
  582.  
  583.   oop->object = obj;
  584.   oop->isFree = false;
  585.   oop->emptyBytes = 0;
  586.   oop->inSpace = toSpace;
  587.   oop->oddMark = toSpace;
  588.   oop->evenMark = !toSpace;
  589.  
  590. #ifdef remove_soon /* Mon May 14 23:42:32 1990 */
  591. /**/{ extern int okToPrint;
  592. /**/if (traceOOPStuff && okToPrint) {
  593. /**/  static Boolean dumped = false;
  594. /**/  if (!dumped) {
  595. /**/    OOP        o;
  596. /**/    dumped = true;
  597. /**/    for (o = oopTable; o < oop; o++) {
  598. /**/      printf("Object %d is ", o - oopTable); printObject(o);
  599. /**/      printf("\n");
  600. /**/    }
  601. /**/  }
  602. /**/if (oop - oopTable > 23000) {
  603. /**/  printf("Allocated %d = ", oop - oopTable); printObject(oop); 
  604. /**/  printf("\n");
  605. /**/}
  606. /**/}
  607. /**/}
  608. #endif /* remove_soon Mon May 14 23:42:32 1990 */
  609. #ifdef remove_soon /* Tue May 15 02:23:14 1990 */
  610. /**/
  611. /**/  if (oopClass(oop) == symLinkClass) {
  612. /**/    marks[oop - oopTable] = 1;
  613. /**/    printf("Allocating link %d: ", oop-oopTable);
  614. /**/    printSymLink(oop);
  615. /**/    printf("\n");
  616. /**/  }
  617. #endif /* remove_soon Tue May 15 02:23:14 1990 */
  618.  
  619.   return (oop);
  620. }
  621.  
  622.  
  623. /*
  624.  *    void setOOPObject(oop, object)
  625.  *
  626.  * Description
  627.  *
  628.  *    Sets the object of OOP to be OBJECT.  Makes sure that the object is in
  629.  *    new space before it assigns it to OOP.
  630.  *
  631.  * Inputs
  632.  *
  633.  *    oop   : an OOP table entry to be assigned into
  634.  *    object: an object that the OOP should point to.
  635.  *
  636.  */
  637. void setOOPObject(oop, object)
  638. OOP    oop;
  639. Object    object;
  640. {
  641.   if (objSpace(object) != toSpace) {
  642.     object = moveObject(object);
  643.   }
  644.   oop->object = object;
  645.   oop->inSpace = toSpace;
  646. }
  647.  
  648. /*
  649.  *    void initMem()
  650.  *
  651.  * Description
  652.  *
  653.  *    Initialize the memory allocator.  Both semispaces are allocated, and
  654.  *    the various garbage collection flags are set to their initial values.
  655.  *
  656.  */
  657. void initMem()
  658. {
  659.   int        i;
  660.  
  661.   for (i = 0; i < 2; i++) {
  662.     spaces[i].space = (char *)malloc(MEM_SPACE_SIZE);
  663.     if (spaces[i].space == NULL) {
  664.       printf("Malloc failure; you're out of paging/swapping space\n");
  665.       exit(1);
  666.     }
  667.     initSpace(&spaces[i]);
  668.   }
  669.  
  670.   curSpace = &spaces[0];
  671.   toSpace = 0;
  672.   fromSpace = !toSpace;
  673.   gcFlipped = false;
  674.   gcState = false;
  675.   gcMessage = true;
  676.   copyRate = 0.0;        /* don't copy anything until first flip */
  677.   copyQuota = 0;
  678.   oopTableIndex = 0;
  679.   markBuiltinOOPs();
  680.   clearGCFlipFlags();
  681. }
  682.  
  683. Object curSpaceAddr()
  684. {
  685.   return ((Object)curSpace->space);
  686. }
  687.  
  688. void setSpaceInfo(size)
  689. long    size;
  690. {
  691.   curSpace->copyPtr = curSpace->scanPtr = curSpace->space + size;
  692.   curSpace->size -= size;
  693. }
  694.  
  695. #ifndef INLINE_MACROS
  696.  
  697. void clearGCFlipFlags()
  698. {
  699.   clearGCFlipFlagsMac();
  700. }
  701.  
  702. #endif /* INLINE_MACROS */
  703.  
  704. /*
  705.  *    Object allocObj(size)
  706.  *
  707.  * Description
  708.  *
  709.  *    Allocate and return space for an object of SIZE bytes.  This basically
  710.  *    means moving the allocation pointer for the current space down by SIZE
  711.  *    bytes, and, if there isn't enough space left, flipping the garbage
  712.  *    collector to switch semispaces.  The space is merely allocated; it is
  713.  *    not initialized.
  714.  *
  715.  * Inputs
  716.  *
  717.  *    size  : size in bytes of the object to allocate.  This will be rounded
  718.  *        by this routine up to a suitable boundary, typically to a 4
  719.  *        byte boundary.
  720.  *
  721.  * Outputs
  722.  *
  723.  *    Address of the newly allocated object.
  724.  */
  725. Object allocObj(size)
  726. long    size;
  727. {
  728.   size = alignSize(size);
  729.  
  730.   copyReferencedObjects((long)(size * copyRate));
  731.   curSpace->allocPtr -= size;
  732.   if (curSpace->allocPtr <= curSpace->copyPtr) {
  733.     gcFlip();
  734.     curSpace->allocPtr -= size;
  735.   }
  736.     
  737.   return ((Object)curSpace->allocPtr);
  738. }
  739.  
  740.  
  741. /*
  742.  *    static void copyReferencedObjects(numBytes)
  743.  *
  744.  * Description
  745.  *
  746.  *    This is the heart of the garbage collector.  It is told that NUMBYTES
  747.  *    have been allocated, and it sweeps through a proportional number of
  748.  *    objects that have been copied into new space, looking for references to
  749.  *    objects that are still in old space.  It has to special case
  750.  *    CompiledMethod objects due to their unusual structure.  It uses global
  751.  *    variables to preserve its state so that it can sweep through only as
  752.  *    many objects as it wants, and resume sweeping on the next allocation
  753.  *    where it left off.
  754.  *
  755.  * Inputs
  756.  *
  757.  *    numBytes: 
  758.  *        The number of bytes that have been allocated.  Used as a
  759.  *        parameter that controls how much space to sweep on this
  760.  *        iteration.
  761.  *
  762.  */
  763. static void copyReferencedObjects(numBytes)
  764. long    numBytes;
  765. {
  766.   Object    result, object;
  767.   OOP        curClass;
  768.   InstanceSpec    instanceSpec;
  769.   int        stepSize, i;
  770.   Method    method;
  771.  
  772.   copyQuota += numBytes;
  773.   while (curSpace->scanPtr < curSpace->copyPtr
  774.      && copyQuota > 0) { /* there's more to scan */
  775.     if (curObject == nil) {
  776.       /* if there is no current object, start off with the object's class */
  777.       object = (Object)curSpace->scanPtr;
  778.       curClass = object->objClass;
  779.       maybeMoveOOP(curClass);
  780.       
  781.       if (curClass == compiledMethodClass) {
  782.     /* Compiled methods have to be dealt with specially since they
  783.      * have a structure that's unlike a regular Smalltalk object:
  784.      * it has two fixed instance variables (description and 
  785.      * methodHeader), a variable number of literals, and then
  786.      * a bunch of bytecodes, which must be skipped over */
  787.     stepSize = object->objSize * sizeof(OOP);
  788.     method = (Method)object;
  789.     maybeMoveOOP(method->descriptor);
  790.     if (method->header.headerFlag == 0 || method->header.headerFlag == 3) {
  791.       for (i = 0; i < method->header.numLiterals; i++) {
  792.         maybeMoveOOP(method->literals[i]);
  793.       }
  794.     }
  795.  
  796.     curSpace->scanPtr += stepSize;
  797.     copyQuota -= stepSize;
  798.       } else if (!classIsPointers(curClass)) {
  799.     /* nothing to scan, just skip over it */
  800.     stepSize = object->objSize * sizeof(OOP);
  801.     curSpace->scanPtr += stepSize;
  802.     copyQuota -= stepSize;
  803.       } else {
  804.     /* we've got an object with sub structure, so we set the object
  805.      * size pointer to 2 words less than the object size (ignore
  806.      * the header; we've already copied the class) and set the
  807.      * scan pointer to the first word of the object.  We then continue
  808.      * to go through the normal scanning procedure (fall out the
  809.      * bottom of the if and go back to the top of the loop again)
  810.      */
  811.     curObject = object;
  812.     curObjectSize = numOOPs(curObject) * sizeof(OOP);
  813.     curSpace->scanPtr = (char *)curObject->data;
  814.       }
  815.  
  816.     } else {
  817.       /* we're part way through scanning an object, continue to scan... */
  818.       if (curObjectSize <= 0) {
  819.     curObject = nil;
  820.       } else {
  821.     maybeMoveOOP(*(OOP *)curSpace->scanPtr);
  822.     stepSize = sizeof(OOP);
  823.     curSpace->scanPtr += stepSize;
  824.     curObjectSize -= stepSize;
  825.     copyQuota -= stepSize;
  826.       }
  827.     }
  828.   }
  829.  
  830.   if (copyQuota < 0) {
  831.     copyQuota = 0;
  832.   }
  833. }
  834.  
  835. /*
  836.  *    Boolean gcOff()
  837.  *
  838.  * Description
  839.  *
  840.  *    Turns off the garbage collector.  Returns the previous on/off state.
  841.  *
  842.  * Outputs
  843.  *
  844.  *    Previous state of the garbage collector (on or off).
  845.  */
  846. Boolean gcOff()
  847. {
  848.   Boolean    oldGCState;
  849.  
  850.   oldGCState = gcState;
  851.   gcState = false;
  852.   return (oldGCState);
  853. }
  854.  
  855. /*
  856.  *    void gcOn()
  857.  *
  858.  * Description
  859.  *
  860.  *    Turns on the garbage collector.
  861.  *
  862.  */
  863. void gcOn()
  864. {
  865.   gcState = true;
  866. }
  867.  
  868. /*
  869.  *    void setGCState(state)
  870.  *
  871.  * Description
  872.  *
  873.  *    Set the garbage collector flag to the specified state (either on or
  874.  *    off).
  875.  *
  876.  * Inputs
  877.  *
  878.  *    state : Boolean, true => gc on.
  879.  *
  880.  */
  881. void setGCState(state)
  882. Boolean    state;
  883. {
  884.   gcState = state;
  885. }
  886.  
  887.  
  888. /*
  889.  *    void fullGC()
  890.  *
  891.  * Description
  892.  *
  893.  *    Perform a complete garbage collection of the system.  This basically
  894.  *    copies all the remaining referenced objects to new space, flips old and
  895.  *    new space, copies the root set to the now new space, and then copies
  896.  *    all the referenced objects to the now new space.
  897.  *
  898.  */
  899. void fullGC()
  900. {
  901.   if (!gcState) {
  902.     /* can't do a full GC with gc turned off! */
  903.     return;
  904.   }
  905.  
  906.  
  907.   copyReferencedObjects(0x7FFFFFFF); /* copy what we can */
  908.   gcFlip();
  909.   copyReferencedObjects(0x7FFFFFFF);
  910.   clearOldOOPs();
  911. }
  912.  
  913.  
  914.  
  915.  
  916.  
  917. /*
  918.  *    static void finishOOPScan()
  919.  *
  920.  * Description
  921.  *
  922.  *    Scans through the OOP table, finishing the incremental OOP table
  923.  *    scanning that goes on as OOPs are allocated.
  924.  *
  925.  */
  926. static void finishOOPScan()
  927. {
  928.   OOP        oop;
  929.   int        i;
  930.  
  931.   for (i = oopTableIndex; i < OOP_TABLE_SIZE; i++) {
  932.     oop = &oopTable[i];
  933.     if (!oop->isFree) {
  934.       if (!oop->evenMark && !oop->oddMark) {
  935.     /* we've found a dead one...add it to the free list */
  936.     numFreeOOPs++;
  937.     oop->object = (Object)freeOOPs;
  938.     freeOOPs = oop;
  939.     freeOOPs->isFree = true;
  940. /*    printf("Freed %d\n", i); */
  941.       } else if (toSpace) {
  942.     oop->evenMark = 0;
  943.       } else {
  944.     oop->oddMark = 0;
  945.       }
  946.     }
  947.   }
  948. }
  949.  
  950. /*
  951.  *    static void clearOldOOPs()
  952.  *
  953.  * Description
  954.  *
  955.  *    Scans through the OOP table, removing OOPS that have died.  Only
  956.  *    called at the end of a full GC to remove any stragglers.
  957.  *
  958.  */
  959. static void clearOldOOPs()
  960. {
  961.   OOP        oop;
  962.   int        i;
  963.  
  964.   for (i = oopTableIndex; i < OOP_TABLE_SIZE; i++) {
  965.     oop = &oopTable[i];
  966.     if (!oop->isFree) {
  967.       if ((toSpace && !oop->oddMark) || (!toSpace && !oop->evenMark)) {
  968.     /* we've found a dead one...add it to the free list */
  969.     numFreeOOPs++;
  970.     oop->object = (Object)freeOOPs;
  971.     freeOOPs = oop;
  972.     freeOOPs->isFree = true;
  973. /*    printf("Freed %d\n", i); */
  974.       } else if (toSpace) {
  975.     oop->evenMark = 0;
  976.       } else {
  977.     oop->oddMark = 0;
  978.       }
  979.     }
  980.   }
  981. }
  982.  
  983. /*
  984.  *    void gcFlip()
  985.  *
  986.  * Description
  987.  *
  988.  *    Switches the garbage collector's notion of which space is "new" space
  989.  *    and which is "old" space.  Readjusts the garbage collection parameters
  990.  *    based on things like the allocation to copying ratio.  Copies the root
  991.  *    set to new space.
  992.  *
  993.  */
  994. void gcFlip()
  995. {
  996.   long        oldCopySize, oldNewSize;
  997.  
  998.   if (!gcState) {
  999.     errorf("Attempted to do a gcFlip with garbage collector off!");
  1000.     exit(1);
  1001.   }
  1002.  
  1003.   if (gcFlipCounter >= 1) {
  1004.     errorf("Attempted to do a gcFlip too soon after a gcFlip!");
  1005.     exit(1);
  1006.   }
  1007.  
  1008.  
  1009. #ifdef OOP_DEBUGGING
  1010.   printf("%d free oops = %.2f%%, scanner was at %d/%d\n", numFreeOOPs,
  1011.        100.0 * numFreeOOPs / OOP_TABLE_SIZE, oopTableIndex, OOP_TABLE_SIZE);
  1012. #endif
  1013.  
  1014.   if (gcMessage && !regressionTesting) {
  1015.     /* print the first part of this message before we finish scanning 
  1016.      * oop table for live ones, so that the delay caused by this scanning
  1017.      * is apparent.
  1018.      */
  1019.     printf("\"GC flipping "); fflush(stdout);
  1020.   }
  1021.  
  1022.   finishOOPScan();        /* make sure we're done */
  1023.  
  1024.   oldCopySize = curSpace->copyPtr - curSpace->space;
  1025.   oldNewSize = curSpace->space + MEM_SPACE_SIZE - curSpace->allocPtr;
  1026.  
  1027. if (oldCopySize == 0) {  /* ### Experimental */
  1028.   oldCopySize = oldNewSize;
  1029. }
  1030.  
  1031.  
  1032.   copyRate = ((double)oldCopySize) / oldNewSize;
  1033.   copyRate *= copyRateAdjustment;
  1034.  
  1035.   toSpace = !toSpace;
  1036.   fromSpace = !fromSpace;
  1037.   curSpace = &spaces[toSpace];
  1038.   curObject = nil;
  1039.   copyQuota = 0;
  1040.   oopTableIndex = 0;
  1041.   initSpace(curSpace);
  1042.  
  1043. #ifdef remove_soon /* Mon May 14 23:41:55 1990 */
  1044. /**/zeroMarks();
  1045. #endif /* remove_soon Mon May 14 23:41:55 1990 */
  1046.  
  1047.   /* note the use of quotation marks around the printed message.  The
  1048.      idea here was to make them appear as Smalltalk comments, so that 
  1049.      generated output could be fed to another Smalltalk without harm. */
  1050.   if (gcMessage && !regressionTesting) {
  1051.     printf("to space %d...", toSpace); fflush(stdout);
  1052.     printf("copied space = %.1f%%...", oldCopySize * 100.0 / MEM_SPACE_SIZE);
  1053.   }
  1054.   moveRootOOPs();
  1055.   if (gcMessage && !regressionTesting) {
  1056.     printf("done\"\n");
  1057.   }
  1058.   gcFlipped = true;
  1059. }
  1060.  
  1061. /*
  1062.  *    static void moveRootOOPs()
  1063.  *
  1064.  * Description
  1065.  *
  1066.  *    Copies the root objects from old space to new space.  All of the root
  1067.  *    objects are those that are mentioned in the set of objects that are
  1068.  *    known specially by the interpreter, those that are being used by the
  1069.  *    interpreter, and some information about compilation state.  Also, the
  1070.  *    built-in oops (Characters, nil, true, false) are marked as being in new
  1071.  *    space so that they won't ever be moved.
  1072.  *
  1073.  */
  1074. static void moveRootOOPs()
  1075. {
  1076.   OOP        **oopPtr, oop;
  1077.   int        i;
  1078.  
  1079.   markBuiltinOOPs();
  1080.  
  1081.   /* copy objects that have global pointers */
  1082.   for (oopPtr = globalOOPs; *oopPtr; oopPtr++) {
  1083.     oop = **oopPtr;
  1084.     maybeMoveOOP(oop);        /* use the maybe form here so that we don't
  1085.                  * accidentally move builtins, which have
  1086.                  * already been marked as being in the new
  1087.                  * space
  1088.                  */
  1089.   }
  1090.  
  1091.   moveProcessorRegisters();
  1092.   copyCompileContext();
  1093. }
  1094.  
  1095. /*
  1096.  *    static void markBuiltinOOPs()
  1097.  *
  1098.  * Description
  1099.  *
  1100.  *    Marks all of the builtin OOPS (nil, true, false, and the Characters) as
  1101.  *    being in the current new space.
  1102.  *
  1103.  */
  1104. static void markBuiltinOOPs()
  1105. {
  1106.   int        i;
  1107.  
  1108.   for (i = OOP_TABLE_SIZE; i < TOTAL_OOP_TABLE_SLOTS; i++) {
  1109.     oopTable[i].inSpace = toSpace;
  1110.     oopTable[i].evenMark = oopTable[i].oddMark = 1;
  1111.   }
  1112. }
  1113.  
  1114. /*
  1115.  *    static void initSpace(space)
  1116.  *
  1117.  * Description
  1118.  *
  1119.  *    Initializes the allocation and copying pointers for semispace SPACE.
  1120.  *
  1121.  * Inputs
  1122.  *
  1123.  *    space : Semispace index number.
  1124.  *
  1125.  */
  1126. static void initSpace(space)
  1127. struct memorySpaceStruct *space;
  1128. {
  1129.   space->copyPtr = space->scanPtr = space->space;
  1130.   space->size = MEM_SPACE_SIZE;
  1131.   space->allocPtr = space->space + space->size;
  1132. }
  1133.  
  1134.  
  1135. #ifndef INLINE_MACROS
  1136.  
  1137. /*
  1138.  *    void maybeMoveOOP(oop)
  1139.  *
  1140.  * Description
  1141.  *
  1142.  *    Move OOP to new space if it's not already there.
  1143.  *
  1144.  * Inputs
  1145.  *
  1146.  *    oop   : OOP to be examined, and, if it's in old space, moved to new
  1147.  *        space.
  1148.  *
  1149.  */
  1150. void maybeMoveOOP(oop)
  1151. OOP    oop;
  1152. {
  1153.   maybeMoveOOPMac(oop);
  1154. }
  1155.  
  1156. #endif /* INLINE_MACROS */
  1157.  
  1158.  
  1159. /*
  1160.  *    void moveOOP(oop)
  1161.  *
  1162.  * Description
  1163.  *
  1164.  *    Moves an OOP from old space to new space unconditionally.  Basically
  1165.  *    marks the OOP as being in the current new space, copies the object that
  1166.  *    the oop points to to new space, and sets the even/odd flags to keep the
  1167.  *    OOP table garbage collector from reaping this OOP.
  1168.  *
  1169.  * Inputs
  1170.  *
  1171.  *    oop   : OOP to be moved.  Should always be in OLD space.
  1172.  *
  1173.  */
  1174. void moveOOP(oop)
  1175. OOP    oop;
  1176. {
  1177.   Object    object;
  1178.  
  1179.   object = oopToObj(oop);
  1180.   oop->inSpace = toSpace;
  1181.   oop->object = moveObject(object);
  1182. #ifdef remove_soon /* Mon May 14 23:42:39 1990 */
  1183. /**/if (traceOOPStuff) 
  1184. /**/{ int i;
  1185. /**/
  1186. /**/  i = oop - oopTable;
  1187. /**/if (marks[i] != 0) {
  1188. /**/  printf("moveOOP: oop %d has a mark value of %d\n", i, marks[i]);
  1189. /**/}
  1190. /**/marks[i] = 1;
  1191. /**/}
  1192. #endif /* remove_soon Mon May 14 23:42:39 1990 */
  1193.   if (toSpace) {
  1194.     oop->oddMark = 1;
  1195.   } else {
  1196.     oop->evenMark = 1;
  1197.   }
  1198. }
  1199.  
  1200. /*
  1201.  *    static Object moveObject(object)
  1202.  *
  1203.  * Description
  1204.  *
  1205.  *    Copies OBJECT from old space to new space.  Adjusts the garbage
  1206.  *    collectors pointers to indicate that the object has been added to new
  1207.  *    space so that the scanner will see it.
  1208.  *
  1209.  * Inputs
  1210.  *
  1211.  *    object: Object to be moved to new space.
  1212.  *
  1213.  */
  1214. static Object moveObject(object)
  1215. Object    object;
  1216. {
  1217.   int        size;
  1218.  
  1219.   size = object->objSize * sizeof(OOP);
  1220.   memcpy(curSpace->copyPtr, object, size);
  1221.   object = (Object)curSpace->copyPtr;
  1222.   curSpace->copyPtr += size;
  1223.   curSpace->size -= size;
  1224.   if (curSpace->copyPtr >= curSpace->allocPtr) {
  1225.     errorf("Garbage collector failed...ran out of room while copying!!!");
  1226.     exit(0);
  1227.   }
  1228.  
  1229.   return (object);
  1230. }
  1231.  
  1232. /*
  1233.  *    void printFreeList()
  1234.  *
  1235.  * Description
  1236.  *
  1237.  *    Debugging support routine.  Prints the free list.  Meant only to be
  1238.  *    called from a debugger.
  1239.  *
  1240.  */
  1241. void printFreeList()
  1242. {
  1243.   OOP        oop;
  1244.   for (oop = freeOOPs; oop != nil; oop = (OOP)oop->object) {
  1245.     printf("oop %x\n", oop);
  1246.     printf("oop isfree %d\n", oop->isFree);
  1247.   }
  1248. }
  1249.  
  1250. /*
  1251.  *    debug()
  1252.  *
  1253.  * Description
  1254.  *
  1255.  *    Used for debugging.  You set a breakpoint in the debug routine in the
  1256.  *    debugger, and have code call it when you want it to stop.  Performs no
  1257.  *    action normally.
  1258.  *
  1259.  */
  1260. debug()
  1261. {
  1262. }
  1263.  
  1264.  
  1265. #ifdef remove_soon /* Mon May 14 23:42:01 1990 */
  1266. /**/static void zeroMarks()
  1267. /**/{
  1268. /**/  char    *p;
  1269. /**/
  1270. /**/  for (p = marks; p < &marks[TOTAL_OOP_TABLE_SLOTS]; ) {
  1271. /**/    *p++ = 0;
  1272. /**/  }
  1273. /**/}
  1274. #endif /* remove_soon Mon May 14 23:42:01 1990 */
  1275.