/*********************************************************************** * * Object Table maintenance module. * ***********************************************************************/ /*********************************************************************** * * Copyright (C) 1990, 1991, 1992 Free Software Foundation, Inc. * Written by Steve Byrne. * * This file is part of GNU Smalltalk. * * GNU Smalltalk is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the Free * Software Foundation; either version 1, or (at your option) any later * version. * * GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for * more details. * * You should have received a copy of the GNU General Public License along with * GNU Smalltalk; see the file COPYING. If not, write to the Free Software * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. * ***********************************************************************/ /* * Change Log * ============================================================================ * Author Date Change * sbb 31 Dec 91 Added registered oops to root set. * * sbb 31 Dec 91 oopTable now allocated from memory instead of being * stored as part of the executable. * * sbb 8 Dec 91 Changed oopValid to only check the FREE bit, instead * of worrying about the even odd flags, which may not * be valid. * * sbb 20 Oct 91 Support for growing now fully operational (and no, it * hasn't taken me over a month to track down the * problems; free time has been nil). Also removed more * vestiges of the incremental GC. * * sbb 15 Sep 91 Added support for loading larger semispaces from * saved images. * * sbb 4 Aug 91 Removed more vestiges of the incremental GC, began * switchover to automatically growing semi-spaces. * * sbb 13 Oct 90 Converted to use bit masks instead of bit fields, * hoping to improve performance somewhat. * * sbyrne 8 Apr 90 Changed oopFree to oopValid to fix the bug with * someInstance losing after GC's due to objects that * have non-free OOP table entries, but point to freed * objects. * * sbyrne 7 Apr 90 Increased mem space size to 4M. This can be * decreased as necessary. * * sbyrne 24 Feb 90 Update to change log: there are no longer any * explicitly allocated OOPs due to the new symbol table * structure; the comment below is now a noop. * * sbyrne 20 Sep 89 Added oop table slot GC'ing. I'm not dealing with * oop table slots that are explictly allocated; I * believe that most OOP slots are not explicitly chosen * and so not running the incremental reclaimer for that * case shouldn't hurt us. * * sbyrne 12 Sep 89 Much of the garbage collector's operation depends on * the fact that only 1 flip will occur between any two * operations (such as a compilation, or a byte-code). * The code would be much more complex if this were not * the case, and I'm not sure that things would even be * possible if this were not the case. Anyway, there is * code in this routine to check for that eventuality * and to halt the system if it occurs. * * sbyrne 6 Sep 89 started implementing the garbage collector (YAY!!!) * * sbyrne 13 Jan 89 Created. * */ #include #include "mst.h" #include "mstoop.h" #include "mstdict.h" #include "mstsave.h" #include "mstcomp.h" #include "mstcallin.h" /* Size of the object semi spaces, in bytes */ #define K 1024 #ifndef atarist /* Min for Kernel = 512K, Kernel+STIX min is 1M */ /* you can increase this value if you need more space, and it won't hurt * performance *if* your machine has enough physical memory (otherwise, you * thrash the pager) */ #ifdef AMIGA #define INIT_MEM_SPACE_SIZE /*(512 * K) */ (1500 * K) #else #define INIT_MEM_SPACE_SIZE /*(512 * K) */ (2 * K * K) #else #endif #define INIT_MEM_SPACE_SIZE (1152 * K) #endif #ifdef pre_full_gc /* Sun Aug 4 19:00:10 1991 */ /**/#define oopReclaimFactor 4 /* how many oops to reclaim per oop alloc */ #endif /* pre_full_gc Sun Aug 4 19:00:10 1991 */ /* Define this flag to turn on debugging code for OOP table management */ /* #define OOP_DEBUGGING */ #define alignSize(size) \ ( ((size) + DOUBLE_ALIGNMENT - 1) & ~(DOUBLE_ALIGNMENT - 1) ) #define objSpace(obj) \ ( (((char *)(obj) >= spaces[1].space) \ && ((char *)(obj) < spaces[1].space + spaces[1].totalSize)) \ ? F_SPACE : 0 ) /* Returns 1 if space flag represents the ODD space, 0 for the EVEN space */ #define boolSpace(spaceFlag) \ ((spaceFlag) == F_SPACE) #define EVEN_ODD_MASK (F_EVEN | F_ODD) typedef struct CompiledMethodStruct *Method; extern Boolean regressionTesting; /* These are the real OOPS for nil, true, and false */ OOP nilOOP, trueOOP, falseOOP; /* The OOP table. This contains a pointer to the object, and some flag bits indicating which semispace the pointed-to object lives in. Some of the bits indicate the difference between the allocated length (stored in the object itself, and the real length, for things like byte strings that may not be an even multiple of 4 (== sizeof(void *)). */ struct OOPStruct *oopTable; #ifdef pre_full_gc /* Sun Aug 4 19:00:44 1991 */ /**//* This is the head of the free list. The free list is maintained in the /**/ oop table. Each OOP on the free list has a bit indicating that it''s free, /**/ a pointer to the next free OOP, and a pointer to the previous free OOP. /**/ when this points at NIL, we''re out of space */ /**/OOP freeOOPs; #endif /* pre_full_gc Sun Aug 4 19:00:44 1991 */ int numFreeOOPs; /* The indices of which is the current new space (toSpace) and which is the current old space (fromSpace). At GC flip time, these two are interchanged. */ unsigned long fromSpace, toSpace; Boolean gcFlipped, gcState, gcMessage; int gcFlipCounter; /* If there is this much space used after a gcFlip, we need to grow the other * semi space by spaceGrowRate next time we gcFlip, so that the storage gets * copied into the new, larger area. */ double growThresholdPercent = 80.0; /* Grow the semi spaces by this percentage when the amount of space used * exceeds growThresholdPercent. */ double spaceGrowRate = 30.0; /* This vector holds the storage for all the Character objects in the system. Since all character objects are unique, we pre-allocate space for 256 of them, and treat them as special built-ins when doing garbage collection.*/ CharObject charObjectTable[NUM_CHAR_OBJECTS]; /* This is "nil" object in the system. That is, the single instance of the UndefinedObject class, which is called "nil". */ struct NilObjectStruct nilObject; /* These represent the two boolean objects in the system, true and false. This is the object storage for those two objects. false == &booleanObjects[0], true == &booleanObjects[1] */ struct BooleanObjectStruct booleanObjects[2]; struct memorySpaceStruct { char *space; /* base of allocated storage */ char *allocPtr; /* new space ptr, starts hi, goes down */ char *copyPtr; /* used by GC, points to highest copied space */ char *scanPtr; /* used by GC, points to highest scanned addr */ unsigned long size; /* current remaining size */ unsigned long totalSize; /* current allocated size */ double percentUsed; /* amount used at just after copyReferences */ }; /* This contains the maximum size of a semi space. It is checked before a * semi space gets used at gcflip time; if the space is too small, it is * brought up to spec before being used */ unsigned long maxSpaceSize; /* These two variables represent information about the semispaces. spaces holds the information for each semispace (basically the pointer to the base of the space, and the pointers into it for allocation, copying, and scanning. curSpace holds the address of one of the two semispace data structures, and is used by the garbage collector */ static struct memorySpaceStruct spaces[2]; static struct memorySpaceStruct *curSpace; /* This contains the bit mask of the current toSpace: it's F_EVEN when toSpace is 0, and F_ODD when toSpace is not zero */ static unsigned long evenOddFlag; #ifdef pre_full_gc /* Sun Aug 4 19:22:24 1991 */ /**/static Object curObject; /**/static long curObjectSize/* , copyQuota*/; #endif /* pre_full_gc Sun Aug 4 19:22:24 1991 */ #ifdef preserved /* Sat Aug 3 18:47:58 1991 */ /**/static double copyRate; /**/static double copyRateAdjustment = 1.50; /* copy 50% more than last time */ #endif /* preserved Sat Aug 3 18:47:58 1991 */ static long oopTableIndex; static Object moveObject(); static Boolean isOOPAddr(), isObjAddr(); static void initCharObject(), moveRootOOPs(), initSpace(), markBuiltinOOPs(), copyReferencedObjects(), clearOldOOPs(), displayOOP(), displayObject(); /* * void initOOPTable() * * Description * * Initialize the OOP table. Initially, all the OOPs are on the OOP free * list so that's just how we initialize them. We do as much * initialization as we can, but we're called before classses are * defined, so things that have definite classes must wait until * the classes are defined. * */ void initOOPTable() { int i; allocOOPTable(); numFreeOOPs = OOP_TABLE_SIZE; for (i = 0; i < OOP_TABLE_SIZE; i++) { /* forward chain free list of oops */ oopTable[i].flags = F_FREE; #ifdef pre_sc_gc /* Sat Jul 27 22:02:13 1991 */ /**/ oopTable[i].object = (Object)&oopTable[i+1]; /**/ oopTable[i].flags |= F_FREE; #endif /* pre_sc_gc Sat Jul 27 22:02:13 1991 */ } #ifdef pre_sc_gc /* Sat Jul 27 22:03:03 1991 */ /**/ oopTable[i-1].object = nil; /**/ /**/ freeOOPs = oopTable; #endif /* pre_sc_gc Sat Jul 27 22:03:03 1991 */ nilOOP = &oopTable[nilOOPIndex]; trueOOP = &oopTable[trueOOPIndex]; falseOOP = &oopTable[falseOOPIndex]; nilOOP->flags = trueOOP->flags = falseOOP->flags = 0; nilOOP->object = (Object)&nilObject; nilObject.objSize = ROUNDED_WORDS(sizeof(struct NilObjectStruct)); trueOOP->object = (Object)&booleanObjects[0]; falseOOP->object = (Object)&booleanObjects[1]; booleanObjects[0].objSize = ROUNDED_WORDS(sizeof(struct BooleanObjectStruct)); booleanObjects[1].objSize = ROUNDED_WORDS(sizeof(struct BooleanObjectStruct)); booleanObjects[0].booleanValue= trueOOP; booleanObjects[1].booleanValue= falseOOP; dictInit(); /* ### TEMP HACK ### */ } void allocOOPTable() { oopTable = (struct OOPStruct *)malloc(sizeof(struct OOPStruct) *TOTAL_OOP_TABLE_SLOTS); if (oopTable == NULL) { errorf("Failed to allocate oopTable!!!"); exit(1); } } /* * void initNil() * * Description * * Initialize the "nil" object. * */ void initNil() { nilObject.objClass = undefinedObjectClass; } /* * void initBooleans() * * Description * * Initialize the two boolean objects, after their respective classes have * been created. * */ void initBooleans() { booleanObjects[0].objClass = trueClass; booleanObjects[1].objClass = falseClass; } /* * void initCharTable() * * Description * * Initialize the instances of the class Character, after that class has * been created. * */ void initCharTable() { int i; for (i = 0; i < NUM_CHAR_OBJECTS; i++) { initCharObject(i); oopTable[i + CHAR_OBJECT_BASE].object = (Object)&charObjectTable[i]; oopTable[i + CHAR_OBJECT_BASE].flags = 0; } } /* * static void initCharObject(i) * * Description * * Initialize a single character object. * * Inputs * * i : The index of the character object, in the range 0..255. * */ static void initCharObject(i) int i; { charObjectTable[i].objSize = ROUNDED_WORDS(sizeof(CharObject)); charObjectTable[i].objClass = charClass; charObjectTable[i].charVal = i; } /* * void fixupMetaclassObjects() * * Description * * Called after the fundamental class hierarchy has been defined, this * function goes through and fixes up all the objects in the oop table * that don't have a objClass (objClass == nilOOP). It's a * chicken-and-egg problem: the metaclassClass doesn't yet exist when the * hierarchy is put together, so after it's created, we have to go back * and fix all the metaclasses that we created. * */ void fixupMetaclassObjects() { int i; for (i = 0; i < OOP_TABLE_SIZE; i++) { if (!(oopTable[i].flags & F_FREE) && isNil(oopTable[i].object->objClass)) { oopTable[i].object->objClass = metaclassClass; } } } /* * OOP findAnInstance(classOOP) * * Description * * Finds and returns an instance of the class CLASSOOP. Returns "nil" if * there are no instances present. * * Inputs * * classOOP: * OOP for a class for which to find an instance * * Outputs * * The first instance of the given class in the OOP table. */ OOP findAnInstance(classOOP) OOP classOOP; { register OOP oop; for (oop = oopTable; oop < &oopTable[OOP_TABLE_SIZE]; oop++) { if (!(oop->flags & F_FREE) && oop->object->objClass == classOOP) { return (oop); } } return (nilOOP); } #ifndef INLINE_MACROS /* * long oopIndex(oop) * * Description * * Returns the index within the OOP table of the given OOP. * * Inputs * * oop : OOP to return index of * * Outputs * * Returned index in the OOP table, in range 0..TOTAL_OOP_TABLE_SLOTS. */ long oopIndex(oop) OOP oop; { return (oopIndexMac(oop)); } #endif /* INLINE_MACROS */ /* * Boolean oopIndexValid(index) * * Description * * Checks to see if index represents a valid OOP. * * Inputs * * index : a long index into the OOP table, apparently 1 based due to * being called from Smalltalk via a primitive. * * Outputs * * True if the index represents a valid OOP table element, false * otherwise. */ Boolean oopIndexValid(index) long index; { return (index >= 1 && index <= TOTAL_OOP_TABLE_SLOTS); } #ifndef INLINE_MACROS OOP oopAt(index) long index; { return (oopAtMac(index)); } void prepareToStore(destOOP, srcOOP) OOP destOOP, srcOOP; { prepareToStoreMac(destOOP, srcOOP); } #endif /* INLINE_MACROS */ void swapObjects(oop1, oop2) OOP oop1, oop2; { struct OOPStruct tempOOP; tempOOP = *oop2; *oop2 = *oop1; *oop1 = tempOOP; } OOP charOOPAt(c) Byte c; { return (&oopTable[c + CHAR_OBJECT_BASE]); } Byte charOOPValue(charOOP) OOP charOOP; { return (charOOP - &oopTable[CHAR_OBJECT_BASE]); } void printObject(oop) OOP oop; { if (isInt(oop)) { printf("%d", toInt(oop)); } else if (isNil(oop)) { printf("nil"); } else if (oop == trueOOP) { printf("true"); } else if (oop == falseOOP) { printf("false"); } else if (oopClass(oop) == charClass) { printf("$%c", charOOPValue(oop)); } else if (oopClass(oop) == floatClass) { printf("%#g", floatOOPValue(oop)); } else if (oopClass(oop) == symbolClass) { printf("#"); printSymbol(oop); } else if (oopClass(oop) == stringClass) { /* ### have to quote embedded quote chars */ printf("'"); printString(oop); printf("'"); } else { printOOPConstructor(oop); } } void classifyAddr(addr) void *addr; { if (isOOPAddr(addr)) { displayOOP(addr); } else if (isObjAddr(addr)) { displayObject(addr); } else if isInt(addr) { printf("Smalltalk Integer %d\n", toInt(addr)); } else { printf("Address %#x is not a Smalltalk entity\n", addr); } } static Boolean isOOPAddr(addr) OOP addr; { if (addr >= oopTable && addr < &oopTable[TOTAL_OOP_TABLE_SLOTS]) { if ((long)addr % 4 == 0) { return (true); } } return (false); } static Boolean isObjAddr(addr) char *addr; { if ((addr >= spaces[0].space && addr < spaces[0].space + spaces[0].totalSize) || (addr >= spaces[1].space && addr < spaces[1].space + spaces[1].totalSize)) { if ((long)addr % 4 == 0) { return (true); } } return (false); } static void displayOOP(oop) OOP oop; { Boolean isBuiltin; if (!isOOPAddr(oop)) { printf("Parameter %#x does not appear to be an OOP!\n", oop); return; } isBuiltin = (oop >= &oopTable[OOP_TABLE_SIZE]) ? true : false; if (!isBuiltin) { printf ("OOP %#x [%d]\n", oop, oop - oopTable); } if (oop->flags & F_FREE) { printf("Free "); } printf("Space=%d ", (oop->flags & F_SPACE) ? 1 : 0); if (oop->flags & F_EVEN) { printf("Even "); } if (oop->flags & F_ODD) { printf("Odd "); } if (oop->flags & F_FAKE) { printf("Fake "); } printf(" Empty bytes = %d\n", oop->flags & EMPTY_BYTES); if (!(oop->flags & F_FREE)) { printObject(oop); } printf("\n"); } static void displayObject(obj) Object obj; { int space; if (!isObjAddr(obj)) { printf("Parameter %#x does not appear to be an object!\n", obj); return; } space = objSpace(obj) != 0; printf("Object at %#x, in space %d (curSpace is %d), ", obj, space, curSpace == &spaces[1]); if ((char *)obj >= spaces[space].allocPtr) { printf("allocated this GC pass\n"); } else if ((char *)obj >= spaces[space].scanPtr) { printf("copied in this GC pass, not scanned\n"); } else { printf("copied in this GC pass, scanned\n"); } printf("Size %d\n", numOOPs(obj)); printf("Class "); printObject(obj->objClass); printf("\n"); } Boolean oopValid(oop) OOP oop; { /* In the non-incremental GC world, being FREE is all that matters for * validity. */ return (!(oop->flags & F_FREE)); #ifdef old_code /* Sun Dec 8 16:01:28 1991 */ /**/ return (!(oop->flags & F_FREE) && (oop->flags & (F_EVEN|F_ODD)) ); #endif /* old_code Sun Dec 8 16:01:28 1991 */ } #ifndef INLINE_MACROS Boolean oopAvailable(index) long index; { return (oopAvailableMac(index)); } #endif /* INLINE_MACROS */ /* * OOP allocOOP(obj) * * Description * * Given an object OBJ, this routine allocates an OOP table slot for it * and returns it. It marks the OOP so that it indicates the object is in * new space, and that the oop has been referenced on this pass (to keep * the OOP table reaper from reclaiming this OOP). * * Inputs * * obj : Object that the new OOP should point to. * * Outputs * * An OOP, which is the address of an element in the OOP table. */ OOP allocOOP(obj) Object obj; { register OOP oop; for (oop = &oopTable[oopTableIndex]; oop < &oopTable[OOP_TABLE_SIZE]; oop++) { if (oop->flags & F_FREE) { oopTableIndex = oop - oopTable + 1; numFreeOOPs--; /* !!! not sure if this is needed */ if (objSpace(obj) != toSpace) { /* dprintf("doing move for oldspace object in allocOOP\n"); */ obj = moveObject(obj); } oop->object = obj; oop->flags = toSpace | evenOddFlag; return (oop); } } errorf("Ran out of OOP Table slots!!!"); exit(1); } #ifdef preserved /* Sat Jul 27 16:48:12 1991 */ /**/OOP allocOOP(obj) /**/Object obj; /**/{ /**/#ifndef NORMAL_ALLOC_OOP /**/ register OOP oop; /**/ register int i; /**/ /**/ for (i = 0, oop = &oopTable[oopTableIndex]; /**/ i < oopReclaimFactor && oop < &oopTable[OOP_TABLE_SIZE]; i++, oop++) { /**/ if (!(oop->flags & F_FREE)) { /**/ if (!(oop->flags & (F_EVEN|F_ODD))) { /**/ /* we've found a dead one...add it to the free list */ /**/ numFreeOOPs++; /**/ oop->object = (Object)freeOOPs; /**/ freeOOPs = oop; /**/ freeOOPs->flags |= F_FREE; /**/ } else { /**/ /* turn off the bit for the space we're not in */ /**/ oop->flags &= ~(evenOddFlag ^ EVEN_ODD_MASK); /**/ } /**/ } /**/ } /**/ /**/ oopTableIndex = oop - oopTable; /**/ /**/#else /**/ OOP oop; /**/ register int i; /**/ /**/ for (i = 0; i < oopReclaimFactor; i++) { /**/ if (oopTableIndex >= OOP_TABLE_SIZE) { /**/ break; /**/ } /**/ oop = &oopTable[oopTableIndex++]; /**/ if (!oop->isFree) { /**/ if (!oop->evenMark && !oop->oddMark) { /**/ /* we've found a dead one...add it to the free list */ /**/ numFreeOOPs++; /**/ oop->object = (Object)freeOOPs; /**/ freeOOPs = oop; /**/ freeOOPs->isFree = true; /**/ } else if (toSpace) { /**/ oop->evenMark = 0; /**/ } else { /**/ oop->oddMark = 0; /**/ } /**/ } /**/ } /**/#endif /**/ /**/ oop = freeOOPs; /**/ /**/ numFreeOOPs--; /**/ /**/ if (oop == nil) { /**/ errorf("Ran out of OOP Table slots!!!"); /**/ exit(1); /**/ /* ### this needs to be fixed */ /**/ } /**/ /**/ if (!(oop->flags & F_FREE)) { /**/ errorf("Allocating allocated OOP!!!"); /**/ exit(0); /**/ } /**/ /**/ freeOOPs = (OOP)oop->object; /**/ /**/ if (objSpace(obj) != toSpace) { /**/ obj = moveObject(obj); /**/ } /**/ /**/ /**/ oop->object = obj; /**/ oop->flags = toSpace | evenOddFlag; /**/ /**/ return (oop); /**/} #endif /* preserved Sat Jul 27 16:48:12 1991 */ /* * void setOOPObject(oop, object) * * Description * * Sets the object of OOP to be OBJECT. Makes sure that the object is in * new space before it assigns it to OOP. * * Inputs * * oop : an OOP table entry to be assigned into * object: an object that the OOP should point to. * */ void setOOPObject(oop, object) OOP oop; Object object; { #ifndef OPTIMIZE if (isFake(oop)) { printf("found a fake oop %x\n", oop); debug(); } #endif /* !OPTIMIZE */ if (objSpace(object) != toSpace) { /* dprintf("doing move for oldspace object in setOOPObject\n"); */ object = moveObject(object); } oop->object = object; oop->flags = (oop->flags & ~F_SPACE) | toSpace; } /* * void initMem() * * Description * * Initialize the memory allocator. Both semispaces are allocated, and * the various garbage collection flags are set to their initial values. * */ void initMem() { int i; maxSpaceSize = INIT_MEM_SPACE_SIZE; for (i = 0; i < 2; i++) { spaces[i].space = (char *)malloc(maxSpaceSize); spaces[i].totalSize = maxSpaceSize; spaces[i].percentUsed = 0.0; if (spaces[i].space == NULL) { printf("Malloc failure; you're out of paging/swapping space\n"); exit(1); } initSpace(&spaces[i]); } curSpace = &spaces[0]; toSpace = 0; #ifdef bogus_old_code /* Sat Oct 13 15:37:50 1990 */ /**/ fromSpace = !toSpace; #endif /* bogus_old_code Sat Oct 13 15:37:50 1990 */ fromSpace = F_SPACE; evenOddFlag = F_EVEN; gcFlipped = false; gcState = false; gcMessage = true; #ifdef preserved /* Sat Aug 3 18:48:45 1991 */ /**/ copyRate = 0.0; /* don't copy anything until first flip */ /**/ copyQuota = 0; #endif /* preserved Sat Aug 3 18:48:45 1991 */ oopTableIndex = 0; #ifdef testing_out /* Sat Feb 29 10:55:51 1992 */ /**/ markBuiltinOOPs(); #endif /* testing_out Sat Feb 29 10:55:51 1992 */ clearGCFlipFlags(); } Object curSpaceAddr() { return ((Object)curSpace->space); } void setSpaceInfo(size) long size; { curSpace->copyPtr = curSpace->scanPtr = curSpace->space + size; curSpace->size -= size; } #ifndef INLINE_MACROS void clearGCFlipFlags() { clearGCFlipFlagsMac(); } #endif /* INLINE_MACROS */ /* * Object allocObj(size) * * Description * * Allocate and return space for an object of SIZE bytes. This basically * means moving the allocation pointer for the current space down by SIZE * bytes, and, if there isn't enough space left, flipping the garbage * collector to switch semispaces. The space is merely allocated; it is * not initialized. * * Inputs * * size : size in bytes of the object to allocate. This will be rounded * by this routine up to a suitable boundary, typically to a 4 * byte boundary. * * Outputs * * Address of the newly allocated object. */ Object allocObj(size) long size; { size = alignSize(size); #ifdef preserved /* Sat Jul 27 16:43:00 1991 */ /**/ copyReferencedObjects((long)(size * copyRate)); #endif /* preserved Sat Jul 27 16:43:00 1991 */ curSpace->allocPtr -= size; while (curSpace->allocPtr <= curSpace->copyPtr) { gcFlip(); curSpace->allocPtr -= size; } #ifdef preserved /* Fri Oct 18 21:46:22 1991 */ /**/ if (curSpace->allocPtr <= curSpace->copyPtr) { /**/ gcFlip(); /**/ curSpace->allocPtr -= size; /**/ } #endif /* preserved Fri Oct 18 21:46:22 1991 */ return ((Object)curSpace->allocPtr); } /* * static void copyReferencedObjects() * * Description * * This is the heart of the garbage collector. It fully scans all objects * in new space, copying object that it finds that are still in old space * to new space and adding them to the set of objects to be scanned. * It has to special case * CompiledMethod objects due to their unusual structure. * */ static void copyReferencedObjects() { Object object; register OOP curClass, *oop; int stepSize, count; Method method; register int i; while (curSpace->scanPtr < curSpace->copyPtr) { /* there's more to scan */ /* if there is no current object, start off with the object's class */ object = (Object)curSpace->scanPtr; curClass = object->objClass; #ifdef debugging /* Mon Oct 28 12:29:31 1991 */ /**/ if (curClass == stringClass) { /**/ fwrite(object->data, sizeof(Byte), numOOPs(object) * sizeof(OOP), stdout); /**/ fflush(stdout); /**/ printf("\n----------------------------------------\n"); /**/ } #endif /* debugging Mon Oct 28 12:29:31 1991 */ /* { extern Boolean gcDebug; if (gcDebug) { dprintf("copying at %#8x, size %d\n", curSpace->scanPtr, object->objSize); } } */ /* don't need to do the isInt test for this case */ localMaybeMoveOOP(curClass); stepSize = object->objSize * sizeof(OOP); if (curClass == compiledMethodClass) { /* Compiled methods have to be dealt with specially since they * have a structure that's unlike a regular Smalltalk object: * it has two fixed instance variables (description and * methodHeader), a variable number of literals, and then * a bunch of bytecodes, which must be skipped over */ method = (Method)object; localMaybeMoveOOP(method->descriptor); if (method->header.headerFlag == 0 || method->header.headerFlag == 3) { count = method->header.numLiterals; for (i = 0; i < count; i++) { localMaybeMoveOOP(method->literals[i]); } } } else if (!classIsPointers(curClass)) { /* nothing to scan, just skip over it */ } else { /* we've got an object with sub structure, so we set the object * size pointer to 2 words less than the object size (ignore * the header; we've already copied the class) and set the * scan pointer to the first word of the object. We then continue * to go through the normal scanning procedure (fall out the * bottom of the if and go back to the top of the loop again) */ count = numOOPs(object); for (i = 0, oop = object->data; i < count; i++, oop++) { localMaybeMoveOOP(*oop); } } curSpace->scanPtr += stepSize; } } #ifdef preserved /* Sat Jul 27 17:06:09 1991 */ /**/static void copyReferencedObjects(numBytes) /**/long numBytes; /**/{ /**/ Object object; /**/ OOP curClass; /**/ int stepSize, i; /**/ Method method; /**/ /**/ copyQuota += numBytes; /**/ while (curSpace->scanPtr < curSpace->copyPtr /**/ && copyQuota > 0) { /* there's more to scan */ /**/ if (curObject == nil) { /**/ /* if there is no current object, start off with the object's class */ /**/ object = (Object)curSpace->scanPtr; /**/ curClass = object->objClass; /**/ maybeMoveOOP(curClass); /**/ /**/ if (curClass == compiledMethodClass) { /**/ /* Compiled methods have to be dealt with specially since they /**/ * have a structure that''s unlike a regular Smalltalk object: /**/ * it has two fixed instance variables (description and /**/ * methodHeader), a variable number of literals, and then /**/ * a bunch of bytecodes, which must be skipped over */ /**/ stepSize = object->objSize * sizeof(OOP); /**/ method = (Method)object; /**/ maybeMoveOOP(method->descriptor); /**/ if (method->header.headerFlag == 0 || method->header.headerFlag == 3) { /**/ for (i = 0; i < method->header.numLiterals; i++) { /**/ maybeMoveOOP(method->literals[i]); /**/ } /**/ } /**/ /**/ curSpace->scanPtr += stepSize; /**/ copyQuota -= stepSize; /**/ } else if (!classIsPointers(curClass)) { /**/ /* nothing to scan, just skip over it */ /**/ stepSize = object->objSize * sizeof(OOP); /**/ curSpace->scanPtr += stepSize; /**/ copyQuota -= stepSize; /**/ } else { /**/ /* we've got an object with sub structure, so we set the object /**/ * size pointer to 2 words less than the object size (ignore /**/ * the header; we''ve already copied the class) and set the /**/ * scan pointer to the first word of the object. We then continue /**/ * to go through the normal scanning procedure (fall out the /**/ * bottom of the if and go back to the top of the loop again) /**/ */ /**/ curObject = object; /**/ curObjectSize = numOOPs(curObject) * sizeof(OOP); /**/ curSpace->scanPtr = (char *)curObject->data; /**/ } /**/ /**/ } else { /**/ /* we're part way through scanning an object, continue to scan... */ /**/ if (curObjectSize <= 0) { /**/ curObject = nil; /**/ } else { /**/ maybeMoveOOP(*(OOP *)curSpace->scanPtr); /**/ stepSize = sizeof(OOP); /**/ curSpace->scanPtr += stepSize; /**/ curObjectSize -= stepSize; /**/ copyQuota -= stepSize; /**/ } /**/ } /**/ } /**/ /**/ if (copyQuota < 0) { /**/ copyQuota = 0; /**/ } /**/} /**/ #endif /* preserved Sat Jul 27 17:06:09 1991 */ /* * Boolean gcOff() * * Description * * Turns off the garbage collector. Returns the previous on/off state. * * Outputs * * Previous state of the garbage collector (on or off). */ Boolean gcOff() { Boolean oldGCState; oldGCState = gcState; gcState = false; return (oldGCState); } /* * void gcOn() * * Description * * Turns on the garbage collector. * */ void gcOn() { gcState = true; } /* * void setGCState(state) * * Description * * Set the garbage collector flag to the specified state (either on or * off). * * Inputs * * state : Boolean, true => gc on. * */ void setGCState(state) Boolean state; { gcState = state; } /* * static void clearOldOOPs() * * Description * * Scans through the OOP table, removing OOPS that have died. Only * called at the end of a full GC to remove any stragglers. * */ static void clearOldOOPs() { register OOP oop; for (oop = oopTable; oop<&oopTable[OOP_TABLE_SIZE]; oop++) { if (!(oop->flags & F_FREE)) { if (!(oop->flags & evenOddFlag)) { /* we've found a dead one...add it to the free list */ numFreeOOPs++; oop->flags = F_FREE; } else { /* !!! may not want to clear completey to 0? */ oop->flags &= ~EVEN_ODD_MASK; } } #ifdef pre_sc_gc /* Sat Jul 27 17:33:01 1991 */ /**/ for (oop = &oopTable[oopTableIndex]; oop<&oopTable[OOP_TABLE_SIZE]; oop++) { /**/ if (!(oop->flags & F_FREE)) { /**/ if (!(oop->flags & evenOddFlag)) { /**/ /* we've found a dead one...add it to the free list */ /**/ numFreeOOPs++; /**/ oop->object = (Object)freeOOPs; /**/ freeOOPs = oop; /**/ freeOOPs->flags |= F_FREE; /**/ } else { /**/ /* turn off the bit for the space we're not in */ /**/ oop->flags &= ~(evenOddFlag ^ EVEN_ODD_MASK); /**/ } /**/ } /**/ #endif /* pre_sc_gc Sat Jul 27 17:33:01 1991 */ } } /* * void gcFlip() * * Description * * Switches the garbage collector's notion of which space is "new" space * and which is "old" space. Readjusts the garbage collection parameters * based on things like the allocation to copying ratio. Copies the root * set to new space. * */ void gcFlip() { long oldCopySize, oldNewSize; double lastPercent; if (!gcState) { errorf("Attempted to do a gcFlip with garbage collector off!"); exit(1); } #ifndef OPTIMIZE if (gcFlipCounter >= 1) { errorf("Attempted to do a gcFlip too soon after a gcFlip!"); exit(1); } #endif #ifdef OOP_DEBUGGING printf("%d free oops = %.2f%%, scanner was at %d/%d\n", numFreeOOPs, 100.0 * numFreeOOPs / OOP_TABLE_SIZE, oopTableIndex, OOP_TABLE_SIZE); #endif if (gcMessage && !regressionTesting) { /* print the first part of this message before we finish scanning * oop table for live ones, so that the delay caused by this scanning * is apparent. */ printf("\"GC flipping "); fflush(stdout); } oldCopySize = curSpace->copyPtr - curSpace->space; oldNewSize = curSpace->space + curSpace->totalSize - curSpace->allocPtr; if (oldCopySize == 0) { /* ### Experimental */ oldCopySize = oldNewSize; } lastPercent = curSpace->percentUsed; #ifdef preserved /* Sat Jul 27 17:30:33 1991 */ /**/ copyRate = ((double)oldCopySize) / oldNewSize; /**/ copyRate *= copyRateAdjustment; #endif /* preserved Sat Jul 27 17:30:33 1991 */ toSpace ^= F_SPACE; fromSpace ^= F_SPACE; evenOddFlag ^= EVEN_ODD_MASK; /* switch which bit is in use */ curSpace = &spaces[boolSpace(toSpace)]; #ifdef pre_full_gc /* Sun Aug 4 19:24:21 1991 */ /**/ curObject = nil; #endif /* pre_full_gc Sun Aug 4 19:24:21 1991 */ #ifdef preserved /* Sat Aug 3 18:49:00 1991 */ /**/ copyQuota = 0; #endif /* preserved Sat Aug 3 18:49:00 1991 */ oopTableIndex = 0; if (lastPercent > growThresholdPercent) { maxSpaceSize *= 1.0 + spaceGrowRate/100.0; maxSpaceSize &= ~3; /* round to word boundary */ } initSpace(curSpace); moveRootOOPs(); copyReferencedObjects(); /* copy what we can */ clearOldOOPs(); curSpace->percentUsed = (curSpace->scanPtr - curSpace->space) * 100.0 / curSpace->totalSize; /* if oldCopySize / size of space > threshold allocate new old space */ /* note the use of quotation marks around the printed message. The idea here was to make them appear as Smalltalk comments, so that generated output could be fed to another Smalltalk without harm. */ if (gcMessage && !regressionTesting) { printf("to space %d...", boolSpace(toSpace)); fflush(stdout); printf("copied space = %.1f%%...", curSpace->percentUsed); #ifdef pre_full_gc /* Sun Aug 4 20:09:15 1991 */ /**/ printf("copied space = %.1f%%...", oldCopySize * 100.0 / MEM_SPACE_SIZE); #endif /* pre_full_gc Sun Aug 4 20:09:15 1991 */ } if (gcMessage && !regressionTesting) { printf("done\"\n"); } gcFlipped = true; } #ifdef preserved /* Sat Jul 27 16:37:34 1991 */ /**/void gcFlip() /**/{ /**/ long oldCopySize, oldNewSize; /**/ /**/ if (!gcState) { /**/ errorf("Attempted to do a gcFlip with garbage collector off!"); /**/ exit(1); /**/ } /**/ /**/ if (gcFlipCounter >= 1) { /**/ errorf("Attempted to do a gcFlip too soon after a gcFlip!"); /**/ exit(1); /**/ } /**/ /**/ /**/#ifdef OOP_DEBUGGING /**/ printf("%d free oops = %.2f%%, scanner was at %d/%d\n", numFreeOOPs, /**/ 100.0 * numFreeOOPs / OOP_TABLE_SIZE, oopTableIndex, OOP_TABLE_SIZE); /**/#endif /**/ /**/ if (gcMessage && !regressionTesting) { /**/ /* print the first part of this message before we finish scanning /**/ * oop table for live ones, so that the delay caused by this scanning /**/ * is apparent. /**/ */ /**/ printf("\"GC flipping "); fflush(stdout); /**/ } /**/ /**/ finishOOPScan(); /* make sure we're done */ /**/ /**/ oldCopySize = curSpace->copyPtr - curSpace->space; /**/ oldNewSize = curSpace->space + MEM_SPACE_SIZE - curSpace->allocPtr; /**/ /**/if (oldCopySize == 0) { /* ### Experimental */ /**/ oldCopySize = oldNewSize; /**/} /**/ /**/ /**/ copyRate = ((double)oldCopySize) / oldNewSize; /**/ copyRate *= copyRateAdjustment; /**/ /**/ toSpace ^= F_SPACE; /**/ fromSpace ^= F_SPACE; /**/ evenOddFlag ^= EVEN_ODD_MASK; /* switch which bit is in use */ /**/#ifdef bogus /* Sat Oct 13 15:38:55 1990 */ /**//**/ toSpace = !toSpace; /**//**/ fromSpace = !fromSpace; /**/#endif /* bogus Sat Oct 13 15:38:55 1990 */ /**/ curSpace = &spaces[boolSpace(toSpace)]; /**/ curObject = nil; /**/ copyQuota = 0; /**/ oopTableIndex = 0; /**/ initSpace(curSpace); /**/ /**/#ifdef remove_soon /* Mon May 14 23:41:55 1990 */ /**//**/zeroMarks(); /**/#endif /* remove_soon Mon May 14 23:41:55 1990 */ /**/ /**/ /* note the use of quotation marks around the printed message. The /**/ idea here was to make them appear as Smalltalk comments, so that /**/ generated output could be fed to another Smalltalk without harm. */ /**/ if (gcMessage && !regressionTesting) { /**/ printf("to space %d...", boolSpace(toSpace)); fflush(stdout); /**/ printf("copied space = %.1f%%...", oldCopySize * 100.0 / MEM_SPACE_SIZE); /**/ } /**/ moveRootOOPs(); /**/ if (gcMessage && !regressionTesting) { /**/ printf("done\"\n"); /**/ } /**/ gcFlipped = true; /**/} #endif /* preserved Sat Jul 27 16:37:34 1991 */ /* * static void moveRootOOPs() * * Description * * Copies the root objects from old space to new space. All of the root * objects are those that are mentioned in the set of objects that are * known specially by the interpreter, those that are being used by the * interpreter, and some information about compilation state. Also, the * built-in oops (Characters, nil, true, false) are marked as being in new * space so that they won't ever be moved. * */ static void moveRootOOPs() { OOP **oopPtr, oop; markBuiltinOOPs(); /* copy objects that have global pointers */ for (oopPtr = globalOOPs; *oopPtr; oopPtr++) { oop = **oopPtr; localMaybeMoveOOP(oop); /* use the maybe form here so that we don't * accidentally move builtins, which have * already been marked as being in the new * space */ } moveProcessorRegisters(); copyRegisteredOOPs(); copyCompileContext(); } /* * static void markBuiltinOOPs() * * Description * * Marks all of the builtin OOPS (nil, true, false, and the Characters) as * being in the current new space. * */ static void markBuiltinOOPs() { register OOP oop; for (oop = &oopTable[OOP_TABLE_SIZE]; oop < &oopTable[TOTAL_OOP_TABLE_SLOTS]; oop++) { oop->flags = (oop->flags & ~F_SPACE) | toSpace | F_EVEN | F_ODD; } } /* * static void initSpace(space) * * Description * * Initializes the allocation and copying pointers for semispace SPACE. * * Inputs * * space : Semispace index number. * */ static void initSpace(space) struct memorySpaceStruct *space; { char *oldSpace; if (space->totalSize < maxSpaceSize) { oldSpace = space->space; space->space = (char *)realloc(oldSpace, maxSpaceSize); if (space->space == NULL) { space->space = oldSpace; errorf("Could not grow space to %d", maxSpaceSize); /* ??? Should print some kind of warning here, like we can't reallocate * more space */ } else { space->totalSize = maxSpaceSize; } } space->copyPtr = space->scanPtr = space->space; space->size = space->totalSize; space->allocPtr = space->space + space->size; } void growBothSpaces(newSize) unsigned long newSize; { int i; maxSpaceSize = newSize; for (i = 0; i < 2; i++) { initSpace(&spaces[i]); } } #ifndef INLINE_MACROS /* * void maybeMoveOOP(oop) * * Description * * Move OOP to new space if it's not already there. * * Inputs * * oop : OOP to be examined, and, if it's in old space, moved to new * space. * */ void maybeMoveOOP(oop) OOP oop; { maybeMoveOOPMac(oop); } #endif /* INLINE_MACROS */ /* * void moveOOP(oop) * * Description * * Moves an OOP from old space to new space unconditionally. Basically * marks the OOP as being in the current new space, copies the object that * the oop points to to new space, and sets the even/odd flags to keep the * OOP table garbage collector from reaping this OOP. * * Inputs * * oop : OOP to be moved. Should always be in OLD space. * */ void moveOOP(oop) OOP oop; { Object object; #ifndef OPTIMIZE if (isFake(oop)) { printf("moving fake object!!! %x\n", oop); debug(); } #endif /* !OPTIMIZE */ object = oopToObj(oop); /* !!! this F_SPACE and TO_SPACE stuff should go */ oop->flags = (oop->flags & ~F_SPACE) | toSpace | evenOddFlag; oop->object = moveObject(object); } /* * static Object moveObject(object) * * Description * * Copies OBJECT from old space to new space. Adjusts the garbage * collectors pointers to indicate that the object has been added to new * space so that the scanner will see it. * * Inputs * * object: Object to be moved to new space. * */ static Object moveObject(object) Object object; { long size; /* dprintf("moving %8x, size %d\n", curSpace->copyPtr, object->objSize); */ if ((long) object->objSize >= 1000) { debug(); } size = object->objSize * sizeof(OOP); memcpy(curSpace->copyPtr, object, size); object = (Object)curSpace->copyPtr; curSpace->copyPtr += size; curSpace->size -= size; if (curSpace->copyPtr >= curSpace->allocPtr) { errorf("Garbage collector failed...ran out of room while copying!!!"); exit(0); } return (object); } #ifdef pre_full_gc /* Sun Aug 4 19:31:08 1991 */ /**//* /**/ * void printFreeList() /**/ * /**/ * Description /**/ * /**/ * Debugging support routine. Prints the free list. Meant only to be /**/ * called from a debugger. /**/ * /**/ */ /**/void printFreeList() /**/{ /**/ OOP oop; /**/ for (oop = freeOOPs; oop != nil; oop = (OOP)oop->object) { /**/ printf("oop %x\n", oop); /**/ printf("oop isfree %d\n", (oop->flags & F_FREE) != 0); /**/ } /**/} #endif /* pre_full_gc Sun Aug 4 19:31:08 1991 */ /* * debug() * * Description * * Used for debugging. You set a breakpoint in the debug routine in the * debugger, and have code call it when you want it to stop. Performs no * action normally. * */ debug() { } #ifdef remove_soon /* Mon May 14 23:42:01 1990 */ /**/static void zeroMarks() /**/{ /**/ char *p; /**/ /**/ for (p = marks; p < &marks[TOTAL_OOP_TABLE_SLOTS]; ) { /**/ *p++ = 0; /**/ } /**/} #endif /* remove_soon Mon May 14 23:42:01 1990 */