diff --git a/libpolyml/exporter.cpp b/libpolyml/exporter.cpp index 1a4f25e0..4e0ee44b 100644 --- a/libpolyml/exporter.cpp +++ b/libpolyml/exporter.cpp @@ -1,936 +1,936 @@ /* Title: exporter.cpp - Export a function as an object or C file Copyright (c) 2006-7, 2015, 2016-20 David C.J. Matthews This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifdef HAVE_CONFIG_H #include "config.h" #elif defined(_WIN32) #include "winconfig.h" #else #error "No configuration file" #endif #ifdef HAVE_ASSERT_H #include #define ASSERT(x) assert(x) #else #define ASSERT(x) #endif #ifdef HAVE_STRING_H #include #endif #ifdef HAVE_ERRNO_H #include #endif #ifdef HAVE_SYS_PARAM_H #include #endif #ifdef HAVE_STDLIB_H #include #endif #if (defined(_WIN32)) #include #else #define _T(x) x #define _tcslen strlen #define _tcscmp strcmp #define _tcscat strcat #endif #include "exporter.h" #include "save_vec.h" #include "polystring.h" #include "run_time.h" #include "osmem.h" #include "scanaddrs.h" #include "gc.h" #include "machine_dep.h" #include "diagnostics.h" #include "memmgr.h" #include "processes.h" // For IO_SPACING #include "sys.h" // For EXC_Fail #include "rtsentry.h" #include "pexport.h" #ifdef HAVE_PECOFF #include "pecoffexport.h" #elif defined(HAVE_ELF_H) || defined(HAVE_ELF_ABI_H) #include "elfexport.h" #elif defined(HAVE_MACH_O_RELOC_H) #include "machoexport.h" #endif #if (defined(_WIN32)) #define NOMEMORY ERROR_NOT_ENOUGH_MEMORY #define ERRORNUMBER _doserrno #else #define NOMEMORY ENOMEM #define ERRORNUMBER errno #endif extern "C" { POLYEXTERNALSYMBOL POLYUNSIGNED PolyExport(FirstArgument threadId, PolyWord fileName, PolyWord root); POLYEXTERNALSYMBOL POLYUNSIGNED PolyExportPortable(FirstArgument threadId, PolyWord fileName, PolyWord root); } /* To export the function and everything reachable from it we need to copy all the objects into a new area. We leave tombstones in the original objects by overwriting the length word. That prevents us from copying an object twice and breaks loops. Once we've copied the objects we then have to go back over the memory and turn the tombstones back into length words. */ GraveYard::~GraveYard() { free(graves); } // Used to calculate the space required for the ordinary mutables // and the no-overwrite mutables. They are interspersed in local space. class MutSizes : public ScanAddress { public: MutSizes() : mutSize(0), noOverSize(0) {} virtual PolyObject *ScanObjectAddress(PolyObject *base) { return base; }// No Actually used virtual void ScanAddressesInObject(PolyObject *base, POLYUNSIGNED lengthWord) { const POLYUNSIGNED words = OBJ_OBJECT_LENGTH(lengthWord) + 1; // Include length word if (OBJ_IS_NO_OVERWRITE(lengthWord)) noOverSize += words; else mutSize += words; } POLYUNSIGNED mutSize, noOverSize; }; CopyScan::CopyScan(unsigned h/*=0*/): hierarchy(h) { defaultImmSize = defaultMutSize = defaultCodeSize = defaultNoOverSize = 0; tombs = 0; graveYard = 0; } void CopyScan::initialise(bool isExport/*=true*/) { ASSERT(gMem.eSpaces.size() == 0); // Set the space sizes to a proportion of the space currently in use. // Computing these sizes is not obvious because CopyScan is used both // for export and for saved states. For saved states in particular we // want to use a smaller size because they are retained after we save // the state and if we have many child saved states it's important not // to waste memory. if (hierarchy == 0) { graveYard = new GraveYard[gMem.pSpaces.size()]; if (graveYard == 0) { if (debugOptions & DEBUG_SAVING) Log("SAVE: Unable to allocate graveyard, size: %lu.\n", gMem.pSpaces.size()); throw MemoryException(); } } for (std::vector::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) { PermanentMemSpace *space = *i; if (space->hierarchy >= hierarchy) { // Include this if we're exporting (hierarchy=0) or if we're saving a state // and will include this in the new state. size_t size = (space->top-space->bottom)/4; if (space->noOverwrite) defaultNoOverSize += size; else if (space->isMutable) defaultMutSize += size; else if (space->isCode) defaultCodeSize += size; else defaultImmSize += size; if (space->hierarchy == 0 && ! space->isMutable) { // We need a separate area for the tombstones because this is read-only graveYard[tombs].graves = (PolyWord*)calloc(space->spaceSize(), sizeof(PolyWord)); if (graveYard[tombs].graves == 0) { if (debugOptions & DEBUG_SAVING) Log("SAVE: Unable to allocate graveyard for permanent space, size: %lu.\n", space->spaceSize() * sizeof(PolyWord)); throw MemoryException(); } if (debugOptions & DEBUG_SAVING) Log("SAVE: Allocated graveyard for permanent space, %p size: %lu.\n", graveYard[tombs].graves, space->spaceSize() * sizeof(PolyWord)); graveYard[tombs].startAddr = space->bottom; graveYard[tombs].endAddr = space->top; tombs++; } } } for (std::vector::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) { LocalMemSpace *space = *i; uintptr_t size = space->allocatedSpace(); // It looks as though the mutable size generally gets // overestimated while the immutable size is correct. if (space->isMutable) { MutSizes sizeMut; sizeMut.ScanAddressesInRegion(space->bottom, space->lowerAllocPtr); sizeMut.ScanAddressesInRegion(space->upperAllocPtr, space->top); defaultNoOverSize += sizeMut.noOverSize / 4; defaultMutSize += sizeMut.mutSize / 4; } else defaultImmSize += size/2; } for (std::vector::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) { CodeSpace *space = *i; uintptr_t size = space->spaceSize(); defaultCodeSize += size/2; } if (isExport) { // Minimum 1M words. if (defaultMutSize < 1024*1024) defaultMutSize = 1024*1024; if (defaultImmSize < 1024*1024) defaultImmSize = 1024*1024; if (defaultCodeSize < 1024*1024) defaultCodeSize = 1024*1024; #ifdef MACOSX // Limit the segment size for Mac OS X. The linker has a limit of 2^24 relocations // in a segment so this is a crude way of ensuring the limit isn't exceeded. // It's unlikely to be exceeded by the code itself. // Actually, from trial-and-error, the limit seems to be around 6M. if (defaultMutSize > 6 * 1024 * 1024) defaultMutSize = 6 * 1024 * 1024; if (defaultImmSize > 6 * 1024 * 1024) defaultImmSize = 6 * 1024 * 1024; #endif if (defaultNoOverSize < 4096) defaultNoOverSize = 4096; // Except for the no-overwrite area } else { // Much smaller minimum sizes for saved states. if (defaultMutSize < 1024) defaultMutSize = 1024; if (defaultImmSize < 4096) defaultImmSize = 4096; if (defaultCodeSize < 4096) defaultCodeSize = 4096; if (defaultNoOverSize < 4096) defaultNoOverSize = 4096; // Set maximum sizes as well. We may have insufficient contiguous space for // very large areas. if (defaultMutSize > 1024 * 1024) defaultMutSize = 1024 * 1024; if (defaultImmSize > 1024 * 1024) defaultImmSize = 1024 * 1024; if (defaultCodeSize > 1024 * 1024) defaultCodeSize = 1024 * 1024; if (defaultNoOverSize > 1024 * 1024) defaultNoOverSize = 1024 * 1024; } if (debugOptions & DEBUG_SAVING) Log("SAVE: Copyscan default sizes: Immutable: %" POLYUFMT ", Mutable: %" POLYUFMT ", Code: %" POLYUFMT ", No-overwrite %" POLYUFMT ".\n", defaultImmSize, defaultMutSize, defaultCodeSize, defaultNoOverSize); } CopyScan::~CopyScan() { gMem.DeleteExportSpaces(); if (graveYard) delete[](graveYard); } // This function is called for each address in an object // once it has been copied to its new location. We copy first // then scan to update the addresses. POLYUNSIGNED CopyScan::ScanAddressAt(PolyWord *pt) { PolyWord val = *pt; // Ignore integers. if (IS_INT(val) || val == PolyWord::FromUnsigned(0)) return 0; PolyObject *obj = val.AsObjPtr(); POLYUNSIGNED l = ScanAddress(&obj); *pt = obj; return l; } // This function is called for each address in an object // once it has been copied to its new location. We copy first // then scan to update the addresses. POLYUNSIGNED CopyScan::ScanAddress(PolyObject **pt) { PolyObject *obj = *pt; MemSpace *space = gMem.SpaceForAddress((PolyWord*)obj - 1); ASSERT(space != 0); // We may sometimes get addresses that have already been updated // to point to the new area. e.g. (only?) in the case of constants // that have been updated in ScanConstantsWithinCode. if (space->spaceType == ST_EXPORT) return 0; // If this is at a lower level than the hierarchy we are saving // then leave it untouched. if (space->spaceType == ST_PERMANENT) { PermanentMemSpace *pmSpace = (PermanentMemSpace*)space; if (pmSpace->hierarchy < hierarchy) return 0; } // Have we already scanned this? if (obj->ContainsForwardingPtr()) { // Update the address to the new value. #ifdef POLYML32IN64 PolyObject *newAddr; if (space->isCode) newAddr = (PolyObject*)(globalCodeBase + ((obj->LengthWord() & ~_OBJ_TOMBSTONE_BIT) << 1)); else newAddr = obj->GetForwardingPtr(); #else PolyObject *newAddr = obj->GetForwardingPtr(); #endif *pt = newAddr; return 0; // No need to scan it again. } else if (space->spaceType == ST_PERMANENT) { // See if we have this in the grave-yard. for (unsigned i = 0; i < tombs; i++) { GraveYard *g = &graveYard[i]; if ((PolyWord*)obj >= g->startAddr && (PolyWord*)obj < g->endAddr) { PolyWord *tombAddr = g->graves + ((PolyWord*)obj - g->startAddr); PolyObject *tombObject = (PolyObject*)tombAddr; if (tombObject->ContainsForwardingPtr()) { #ifdef POLYML32IN64 PolyObject *newAddr; if (space->isCode) newAddr = (PolyObject*)(globalCodeBase + ((tombObject->LengthWord() & ~_OBJ_TOMBSTONE_BIT) << 1)); else newAddr = tombObject->GetForwardingPtr(); #else PolyObject *newAddr = tombObject->GetForwardingPtr(); #endif *pt = newAddr; return 0; } break; // No need to look further } } } // No, we need to copy it. ASSERT(space->spaceType == ST_LOCAL || space->spaceType == ST_PERMANENT || space->spaceType == ST_CODE); POLYUNSIGNED lengthWord = obj->LengthWord(); POLYUNSIGNED words = OBJ_OBJECT_LENGTH(lengthWord); PolyObject *newObj = 0; PolyObject* writeAble = 0; bool isMutableObj = obj->IsMutable(); bool isNoOverwrite = false; bool isByteObj = false; bool isCodeObj = false; if (isMutableObj) { isNoOverwrite = obj->IsNoOverwriteObject(); isByteObj = obj->IsByteObject(); } else isCodeObj = obj->IsCodeObject(); // Allocate a new address for the object. for (std::vector::iterator i = gMem.eSpaces.begin(); i < gMem.eSpaces.end(); i++) { PermanentMemSpace *space = *i; if (isMutableObj == space->isMutable && isNoOverwrite == space->noOverwrite && isByteObj == space->byteOnly && isCodeObj == space->isCode) { ASSERT(space->topPointer <= space->top && space->topPointer >= space->bottom); size_t spaceLeft = space->top - space->topPointer; if (spaceLeft > words) { newObj = (PolyObject*)(space->topPointer + 1); writeAble = space->writeAble(newObj); space->topPointer += words + 1; #ifdef POLYML32IN64 // Maintain the odd-word alignment of topPointer if ((words & 1) == 0 && space->topPointer < space->top) { *space->writeAble(space->topPointer) = PolyWord::FromUnsigned(0); space->topPointer++; } #endif break; } } } if (newObj == 0) { // Didn't find room in the existing spaces. Create a new space. uintptr_t spaceWords; if (isMutableObj) { if (isNoOverwrite) spaceWords = defaultNoOverSize; else spaceWords = defaultMutSize; } else { if (isCodeObj) spaceWords = defaultCodeSize; else spaceWords = defaultImmSize; } if (spaceWords <= words) spaceWords = words + 1; // Make sure there's space for this object. PermanentMemSpace *space = gMem.NewExportSpace(spaceWords, isMutableObj, isNoOverwrite, isCodeObj); if (isByteObj) space->byteOnly = true; if (space == 0) { if (debugOptions & DEBUG_SAVING) Log("SAVE: Unable to allocate export space, size: %lu.\n", spaceWords); // Unable to allocate this. throw MemoryException(); } newObj = (PolyObject*)(space->topPointer + 1); writeAble = space->writeAble(newObj); space->topPointer += words + 1; #ifdef POLYML32IN64 // Maintain the odd-word alignment of topPointer if ((words & 1) == 0 && space->topPointer < space->top) { *space->writeAble(space->topPointer) = PolyWord::FromUnsigned(0); space->topPointer++; } #endif ASSERT(space->topPointer <= space->top && space->topPointer >= space->bottom); } writeAble->SetLengthWord(lengthWord); // copy length word if (hierarchy == 0 /* Exporting object module */ && isNoOverwrite && isMutableObj && !isByteObj) { // These are not exported. They are used for special values e.g. mutexes // that should be set to 0/nil/NONE at start-up. // Weak+No-overwrite byte objects are used for entry points and volatiles // in the foreign-function interface and have to be treated specially. // Note: this must not be done when exporting a saved state because the // copied version is used as the local data for the rest of the session. for (POLYUNSIGNED i = 0; i < words; i++) writeAble->Set(i, TAGGED(0)); } else memcpy(writeAble, obj, words * sizeof(PolyWord)); if (space->spaceType == ST_PERMANENT && !space->isMutable && ((PermanentMemSpace*)space)->hierarchy == 0) { // The immutable permanent areas are read-only. unsigned m; for (m = 0; m < tombs; m++) { GraveYard *g = &graveYard[m]; if ((PolyWord*)obj >= g->startAddr && (PolyWord*)obj < g->endAddr) { PolyWord *tombAddr = g->graves + ((PolyWord*)obj - g->startAddr); PolyObject *tombObject = (PolyObject*)tombAddr; #ifdef POLYML32IN64 if (isCodeObj) { POLYUNSIGNED ll = (POLYUNSIGNED)(((PolyWord*)newObj - globalCodeBase) >> 1 | _OBJ_TOMBSTONE_BIT); tombObject->SetLengthWord(ll); } else tombObject->SetForwardingPtr(newObj); #else tombObject->SetForwardingPtr(newObj); #endif break; // No need to look further } } ASSERT(m < tombs); // Should be there. } else if (isCodeObj) #ifdef POLYML32IN64 // If this is a code address we can't use the usual forwarding pointer format. // Instead we have to compute the offset relative to the base of the code. { POLYUNSIGNED ll = (POLYUNSIGNED)(((PolyWord*)newObj-globalCodeBase) >> 1 | _OBJ_TOMBSTONE_BIT); gMem.SpaceForAddress(obj)->writeAble(obj)->SetLengthWord(ll); } #else - gMem.SpaceForAddress(obj)->writeAble(obj)->SetForwardingPtr(newObj); + gMem.SpaceForObjectAddress(obj)->writeAble(obj)->SetForwardingPtr(newObj); #endif else obj->SetForwardingPtr(newObj); // Put forwarding pointer in old object. if (OBJ_IS_CODE_OBJECT(lengthWord)) { // We don't need to worry about flushing the instruction cache // since we're not going to execute this code here. // We do have to update any relative addresses within the code // to take account of its new position. We have to do that now // even though ScanAddressesInObject will do it again because this // is the only point where we have both the old and the new addresses. machineDependent->ScanConstantsWithinCode(newObj, obj, words, this); } *pt = newObj; // Update it to the newly copied object. return lengthWord; // This new object needs to be scanned. } // The address of code in the code area. We treat this as a normal heap cell. // We will probably need to copy this and to process addresses within it. POLYUNSIGNED CopyScan::ScanCodeAddressAt(PolyObject **pt) { POLYUNSIGNED lengthWord = ScanAddress(pt); if (lengthWord) ScanAddressesInObject(*pt, lengthWord); return 0; } PolyObject *CopyScan::ScanObjectAddress(PolyObject *base) { PolyWord val = base; // Scan this as an address. POLYUNSIGNED lengthWord = CopyScan::ScanAddressAt(&val); if (lengthWord) ScanAddressesInObject(val.AsObjPtr(), lengthWord); return val.AsObjPtr(); } #define MAX_EXTENSION 4 // The longest extension we may need to add is ".obj" // Convert the forwarding pointers in a region back into length words. // Generally if this object has a forwarding pointer that's // because we've moved it into the export region. We can, // though, get multiple levels of forwarding if there is an object // that has been shifted up by a garbage collection, leaving a forwarding // pointer and then that object has been moved to the export region. // We mustn't turn locally forwarded values back into ordinary objects // because they could contain addresses that are no longer valid. static POLYUNSIGNED GetObjLength(PolyObject *obj) { if (obj->ContainsForwardingPtr()) { PolyObject *forwardedTo; #ifdef POLYML32IN64 { MemSpace *space = gMem.SpaceForAddress((PolyWord*)obj - 1); if (space->isCode) forwardedTo = (PolyObject*)(globalCodeBase + ((obj->LengthWord() & ~_OBJ_TOMBSTONE_BIT) << 1)); else forwardedTo = obj->GetForwardingPtr(); } #else forwardedTo = obj->GetForwardingPtr(); #endif POLYUNSIGNED length = GetObjLength(forwardedTo); MemSpace *space = gMem.SpaceForAddress((PolyWord*)forwardedTo-1); if (space->spaceType == ST_EXPORT) - gMem.SpaceForAddress(obj)->writeAble(obj)->SetLengthWord(length); + gMem.SpaceForObjectAddress(obj)->writeAble(obj)->SetLengthWord(length); return length; } else { ASSERT(obj->ContainsNormalLengthWord()); return obj->LengthWord(); } } static void FixForwarding(PolyWord *pt, size_t space) { while (space) { pt++; PolyObject *obj = (PolyObject*)pt; #ifdef POLYML32IN64 if ((uintptr_t)obj & 4) { // Skip filler words needed to align to an even word space--; continue; // We've added 1 to pt so just loop. } #endif size_t length = OBJ_OBJECT_LENGTH(GetObjLength(obj)); pt += length; ASSERT(space > length); space -= length+1; } } class ExportRequest: public MainThreadRequest { public: ExportRequest(Handle root, Exporter *exp): MainThreadRequest(MTP_EXPORTING), exportRoot(root), exporter(exp) {} virtual void Perform() { exporter->RunExport(exportRoot->WordP()); } Handle exportRoot; Exporter *exporter; }; static void exporter(TaskData *taskData, Handle fileName, Handle root, const TCHAR *extension, Exporter *exports) { size_t extLen = _tcslen(extension); TempString fileNameBuff(Poly_string_to_T_alloc(fileName->Word(), extLen)); if (fileNameBuff == NULL) raise_syscall(taskData, "Insufficient memory", NOMEMORY); size_t length = _tcslen(fileNameBuff); // Does it already have the extension? If not add it on. if (length < extLen || _tcscmp(fileNameBuff + length - extLen, extension) != 0) _tcscat(fileNameBuff, extension); #if (defined(_WIN32) && defined(UNICODE)) exports->exportFile = _wfopen(fileNameBuff, L"wb"); #else exports->exportFile = fopen(fileNameBuff, "wb"); #endif if (exports->exportFile == NULL) raise_syscall(taskData, "Cannot open export file", ERRORNUMBER); // Request a full GC to reduce the size of fix-ups. FullGC(taskData); // Request the main thread to do the export. ExportRequest request(root, exports); processes->MakeRootRequest(taskData, &request); if (exports->errorMessage) raise_fail(taskData, exports->errorMessage); } // This is called by the initial thread to actually do the export. void Exporter::RunExport(PolyObject *rootFunction) { Exporter *exports = this; PolyObject *copiedRoot = 0; CopyScan copyScan(hierarchy); try { copyScan.initialise(); // Copy the root and everything reachable from it into the temporary area. copiedRoot = copyScan.ScanObjectAddress(rootFunction); } catch (MemoryException &) { // If we ran out of memory. copiedRoot = 0; } // Fix the forwarding pointers. for (std::vector::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) { LocalMemSpace *space = *i; // Local areas only have objects from the allocation pointer to the top. FixForwarding(space->bottom, space->lowerAllocPtr - space->bottom); FixForwarding(space->upperAllocPtr, space->top - space->upperAllocPtr); } for (std::vector::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) { MemSpace *space = *i; // Permanent areas are filled with objects from the bottom. FixForwarding(space->bottom, space->top - space->bottom); } for (std::vector::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) { MemSpace *space = *i; // Code areas are filled with objects from the bottom. FixForwarding(space->bottom, space->top - space->bottom); } // Reraise the exception after cleaning up the forwarding pointers. if (copiedRoot == 0) { exports->errorMessage = "Insufficient Memory"; return; } // Copy the areas into the export object. size_t tableEntries = gMem.eSpaces.size(); unsigned memEntry = 0; if (hierarchy != 0) tableEntries += gMem.pSpaces.size(); exports->memTable = new memoryTableEntry[tableEntries]; // If we're constructing a module we need to include the global spaces. if (hierarchy != 0) { // Permanent spaces from the executable. for (std::vector::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) { PermanentMemSpace *space = *i; if (space->hierarchy < hierarchy) { memoryTableEntry *entry = &exports->memTable[memEntry++]; entry->mtOriginalAddr = entry->mtCurrentAddr = space->bottom; entry->mtLength = (space->topPointer-space->bottom)*sizeof(PolyWord); entry->mtIndex = space->index; entry->mtFlags = 0; if (space->isMutable) entry->mtFlags |= MTF_WRITEABLE; if (space->isCode) entry->mtFlags |= MTF_EXECUTABLE; } } newAreas = memEntry; } for (std::vector::iterator i = gMem.eSpaces.begin(); i < gMem.eSpaces.end(); i++) { memoryTableEntry *entry = &exports->memTable[memEntry++]; PermanentMemSpace *space = *i; entry->mtOriginalAddr = entry->mtCurrentAddr = space->bottom; entry->mtLength = (space->topPointer-space->bottom)*sizeof(PolyWord); entry->mtIndex = hierarchy == 0 ? memEntry-1 : space->index; entry->mtFlags = 0; if (space->isMutable) { entry->mtFlags = MTF_WRITEABLE; if (space->noOverwrite) entry->mtFlags |= MTF_NO_OVERWRITE; } if (space->isCode) entry->mtFlags |= MTF_EXECUTABLE; if (space->byteOnly) entry->mtFlags |= MTF_BYTES; } ASSERT(memEntry == tableEntries); exports->memTableEntries = memEntry; exports->rootFunction = copiedRoot; try { // This can raise MemoryException at least in PExport::exportStore. exports->exportStore(); } catch (MemoryException &) { exports->errorMessage = "Insufficient Memory"; } } // Functions called via the RTS call. Handle exportNative(TaskData *taskData, Handle args) { #ifdef HAVE_PECOFF // Windows including Cygwin #if (defined(_WIN32)) const TCHAR *extension = _T(".obj"); // Windows #else const char *extension = ".o"; // Cygwin #endif PECOFFExport exports; exporter(taskData, taskData->saveVec.push(args->WordP()->Get(0)), taskData->saveVec.push(args->WordP()->Get(1)), extension, &exports); #elif defined(HAVE_ELF_H) || defined(HAVE_ELF_ABI_H) // Most Unix including Linux, FreeBSD and Solaris. const char *extension = ".o"; ELFExport exports; exporter(taskData, taskData->saveVec.push(args->WordP()->Get(0)), taskData->saveVec.push(args->WordP()->Get(1)), extension, &exports); #elif defined(HAVE_MACH_O_RELOC_H) // Mac OS-X const char *extension = ".o"; MachoExport exports; exporter(taskData, taskData->saveVec.push(args->WordP()->Get(0)), taskData->saveVec.push(args->WordP()->Get(1)), extension, &exports); #else raise_exception_string (taskData, EXC_Fail, "Native export not available for this platform"); #endif return taskData->saveVec.push(TAGGED(0)); } Handle exportPortable(TaskData *taskData, Handle args) { PExport exports; exporter(taskData, taskData->saveVec.push(args->WordP()->Get(0)), taskData->saveVec.push(args->WordP()->Get(1)), _T(".txt"), &exports); return taskData->saveVec.push(TAGGED(0)); } POLYUNSIGNED PolyExport(FirstArgument threadId, PolyWord fileName, PolyWord root) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); Handle pushedName = taskData->saveVec.push(fileName); Handle pushedRoot = taskData->saveVec.push(root); try { #ifdef HAVE_PECOFF // Windows including Cygwin #if (defined(_WIN32)) const TCHAR *extension = _T(".obj"); // Windows #else const char *extension = ".o"; // Cygwin #endif PECOFFExport exports; exporter(taskData, pushedName, pushedRoot, extension, &exports); #elif defined(HAVE_ELF_H) || defined(HAVE_ELF_ABI_H) // Most Unix including Linux, FreeBSD and Solaris. const char *extension = ".o"; ELFExport exports; exporter(taskData, pushedName, pushedRoot, extension, &exports); #elif defined(HAVE_MACH_O_RELOC_H) // Mac OS-X const char *extension = ".o"; MachoExport exports; exporter(taskData, pushedName, pushedRoot, extension, &exports); #else raise_exception_string (taskData, EXC_Fail, "Native export not available for this platform"); #endif } catch (...) { } // If an ML exception is raised taskData->saveVec.reset(reset); taskData->PostRTSCall(); return TAGGED(0).AsUnsigned(); // Returns unit } POLYUNSIGNED PolyExportPortable(FirstArgument threadId, PolyWord fileName, PolyWord root) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); Handle pushedName = taskData->saveVec.push(fileName); Handle pushedRoot = taskData->saveVec.push(root); try { PExport exports; exporter(taskData, pushedName, pushedRoot, _T(".txt"), &exports); } catch (...) { } // If an ML exception is raised taskData->saveVec.reset(reset); taskData->PostRTSCall(); return TAGGED(0).AsUnsigned(); // Returns unit } // Helper functions for exporting. We need to produce relocation information // and this code is common to every method. Exporter::Exporter(unsigned int h): exportFile(NULL), errorMessage(0), hierarchy(h), memTable(0), newAreas(0) { } Exporter::~Exporter() { delete[](memTable); if (exportFile) fclose(exportFile); } void Exporter::relocateValue(PolyWord *pt) { #ifndef POLYML32IN64 PolyWord q = *pt; if (IS_INT(q) || q == PolyWord::FromUnsigned(0)) {} else createRelocation(pt); #endif } void Exporter::createRelocation(PolyWord* pt) { *gMem.SpaceForAddress(pt)->writeAble(pt) = createRelocation(*pt, pt); } // Check through the areas to see where the address is. It must be // in one of them. unsigned Exporter::findArea(void *p) { for (unsigned i = 0; i < memTableEntries; i++) { if (p > memTable[i].mtOriginalAddr && p <= (char*)memTable[i].mtOriginalAddr + memTable[i].mtLength) return i; } { ASSERT(0); } return 0; } void Exporter::relocateObject(PolyObject *p) { if (p->IsByteObject()) { if (p->IsMutable() && p->IsWeakRefObject()) { // Weak mutable byte refs are used for external references and // also in the FFI for non-persistent values. bool isFuncPtr = true; const char *entryName = getEntryPointName(p, &isFuncPtr); if (entryName != 0) addExternalReference(p, entryName, isFuncPtr); // Clear the first word of the data. ASSERT(p->Length() >= sizeof(uintptr_t)/sizeof(PolyWord)); *(uintptr_t*)p = 0; } } else if (p->IsCodeObject()) { POLYUNSIGNED constCount; PolyWord *cp; ASSERT(! p->IsMutable() ); p->GetConstSegmentForCode(cp, constCount); /* Now the constants. */ for (POLYUNSIGNED i = 0; i < constCount; i++) relocateValue(&(cp[i])); } else if (p->IsClosureObject()) { #ifndef POLYML32IN64 ASSERT(0); #endif // This should only be used in 32-in-64 where we don't use relocations. } else /* Ordinary objects, essentially tuples. */ { POLYUNSIGNED length = p->Length(); for (POLYUNSIGNED i = 0; i < length; i++) relocateValue(p->Offset(i)); } } ExportStringTable::ExportStringTable(): strings(0), stringSize(0), stringAvailable(0) { } ExportStringTable::~ExportStringTable() { free(strings); } // Add a string to the string table, growing it if necessary. unsigned long ExportStringTable::makeEntry(const char *str) { unsigned len = (unsigned)strlen(str); unsigned long entry = stringSize; if (stringSize + len + 1 > stringAvailable) { stringAvailable = stringAvailable+stringAvailable/2; if (stringAvailable < stringSize + len + 1) stringAvailable = stringSize + len + 1 + 500; char* newStrings = (char*)realloc(strings, stringAvailable); if (newStrings == 0) { if (debugOptions & DEBUG_SAVING) Log("SAVE: Unable to realloc string table, size: %lu.\n", stringAvailable); throw MemoryException(); } else strings = newStrings; } strcpy(strings + stringSize, str); stringSize += len + 1; return entry; } struct _entrypts exporterEPT[] = { { "PolyExport", (polyRTSFunction)&PolyExport}, { "PolyExportPortable", (polyRTSFunction)&PolyExportPortable}, { NULL, NULL} // End of list. }; diff --git a/libpolyml/gc_mark_phase.cpp b/libpolyml/gc_mark_phase.cpp index a18dc413..87633796 100644 --- a/libpolyml/gc_mark_phase.cpp +++ b/libpolyml/gc_mark_phase.cpp @@ -1,888 +1,888 @@ /* Title: Multi-Threaded Garbage Collector - Mark phase Copyright (c) 2010-12, 2015-16, 2019 David C. J. Matthews Based on the original garbage collector code Copyright 2000-2008 Cambridge University Technical Services Limited This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ /* This is the first, mark, phase of the garbage collector. It detects all reachable cells in the area being collected. At the end of the phase the bit-maps associated with the areas will have ones for words belonging to cells that must be retained and zeros for words that can be reused. This is now multi-threaded. The mark phase involves setting a bit in the header of each live cell and then a pass over the memory building the bitmaps and clearing this bit. It is unfortunate that we cannot use the GC-bit that is used in forwarding pointers but we may well have forwarded pointers left over from a partially completed minor GC. Using a bit in the header avoids the need for locking since at worst it may involve two threads duplicating some marking. The code ensures that each reachable cell is marked at least once but with multiple threads a cell may be marked by more than once cell if the memory is not fully up to date. Each thread has a stack on which it remembers cells that have been marked but not fully scanned. If a thread runs out of cells of its own to scan it can pick a pointer off the stack of another thread and scan that. The original thread will still scan it some time later but it should find that the addresses in it have all been marked and it can simply pop this off. This is all done without locking. Stacks are only modified by the owning thread and when they pop anything they write zero in its place. Other threads only need to search for a zero to find if they are at the top and if they get a pointer that has already been scanned then this is safe. The only assumption made about the memory is that all the bits of a word are updated together so that a thread will always read a value that is a valid pointer. Many of the ideas are drawn from Flood, Detlefs, Shavit and Zhang 2001 "Parallel Garbage Collection for Shared Memory Multiprocessors". */ #ifdef HAVE_CONFIG_H #include "config.h" #elif defined(_WIN32) #include "winconfig.h" #else #error "No configuration file" #endif #ifdef HAVE_ASSERT_H #include #define ASSERT(x) assert(x) #else #define ASSERT(x) #endif #include "globals.h" #include "processes.h" #include "gc.h" #include "scanaddrs.h" #include "check_objects.h" #include "bitmap.h" #include "memmgr.h" #include "diagnostics.h" #include "gctaskfarm.h" #include "profiling.h" #include "heapsizing.h" #define MARK_STACK_SIZE 3000 #define LARGECACHE_SIZE 20 class MTGCProcessMarkPointers: public ScanAddress { public: MTGCProcessMarkPointers(); virtual void ScanRuntimeAddress(PolyObject **pt, RtsStrength weak); virtual PolyObject *ScanObjectAddress(PolyObject *base); virtual void ScanAddressesInObject(PolyObject *base, POLYUNSIGNED lengthWord); // Have to redefine this for some reason. void ScanAddressesInObject(PolyObject *base) { ScanAddressesInObject(base, base->LengthWord()); } virtual void ScanConstant(PolyObject *base, byte *addressOfConstant, ScanRelocationKind code); // ScanCodeAddressAt should never be called. POLYUNSIGNED ScanCodeAddressAt(PolyObject **pt) { ASSERT(0); return 0; } static void MarkPointersTask(GCTaskId *, void *arg1, void *arg2); static void InitStatics(unsigned threads) { markStacks = new MTGCProcessMarkPointers[threads]; nInUse = 0; nThreads = threads; } static void MarkRoots(void); static bool RescanForStackOverflow(); private: bool TestForScan(PolyWord *pt); void MarkAndTestForScan(PolyWord *pt); void Reset(); void PushToStack(PolyObject *obj, PolyWord *currentPtr = 0) { // If we don't have all the threads running we start a new one but // only once we have several items on the stack. Otherwise we // can end up creating a task that terminates almost immediately. if (nInUse >= nThreads || msp < 2 || ! ForkNew(obj)) { if (msp < MARK_STACK_SIZE) { markStack[msp++] = obj; if (currentPtr != 0) { locPtr++; if (locPtr == LARGECACHE_SIZE) locPtr = 0; largeObjectCache[locPtr].base = obj; largeObjectCache[locPtr].current = currentPtr; } } else StackOverflow(obj); } // else the new task is processing it. } static void StackOverflow(PolyObject *obj); static bool ForkNew(PolyObject *obj); PolyObject *markStack[MARK_STACK_SIZE]; unsigned msp; bool active; // For the typical small cell it's easier just to rescan from the start // but that can be expensive for large cells. This caches the offset for // large cells. static const POLYUNSIGNED largeObjectSize = 50; struct { PolyObject *base; PolyWord *current; } largeObjectCache[LARGECACHE_SIZE]; unsigned locPtr; static MTGCProcessMarkPointers *markStacks; protected: static unsigned nThreads, nInUse; static PLock stackLock; }; // There is one mark-stack for each GC thread. markStacks[0] is used by the // main thread when marking the roots and rescanning after mark-stack overflow. // Once that work is done markStacks[0] is released and is available for a // worker thread. MTGCProcessMarkPointers *MTGCProcessMarkPointers::markStacks; unsigned MTGCProcessMarkPointers::nThreads, MTGCProcessMarkPointers::nInUse; PLock MTGCProcessMarkPointers::stackLock("GC mark stack"); // It is possible to have two levels of forwarding because // we could have a cell in the allocation area that has been moved // to the immutable area and then shared with another cell. inline PolyObject *FollowForwarding(PolyObject *obj) { while (obj->ContainsForwardingPtr()) obj = obj->GetForwardingPtr(); return obj; } MTGCProcessMarkPointers::MTGCProcessMarkPointers(): msp(0), active(false), locPtr(0) { // Clear the mark stack for (unsigned i = 0; i < MARK_STACK_SIZE; i++) markStack[i] = 0; // Clear the large object cache just to be sure. for (unsigned j = 0; j < LARGECACHE_SIZE; j++) { largeObjectCache[j].base = 0; largeObjectCache[j].current = 0; } } // Clear the state at the beginning of a new GC pass. void MTGCProcessMarkPointers::Reset() { locPtr = 0; //largeObjectCache[locPtr].base = 0; // Clear the cache completely just to be safe for (unsigned j = 0; j < LARGECACHE_SIZE; j++) { largeObjectCache[j].base = 0; largeObjectCache[j].current = 0; } } // Called when the stack has overflowed. We need to include this // in the range to be rescanned. void MTGCProcessMarkPointers::StackOverflow(PolyObject *obj) { MarkableSpace *space = (MarkableSpace*)gMem.SpaceForAddress((PolyWord*)obj-1); ASSERT(space != 0 && (space->spaceType == ST_LOCAL || space->spaceType == ST_CODE)); PLocker lock(&space->spaceLock); // Have to include this in the range to rescan. if (space->fullGCRescanStart > ((PolyWord*)obj) - 1) space->fullGCRescanStart = ((PolyWord*)obj) - 1; POLYUNSIGNED n = obj->Length(); if (space->fullGCRescanEnd < ((PolyWord*)obj) + n) space->fullGCRescanEnd = ((PolyWord*)obj) + n; ASSERT(obj->LengthWord() & _OBJ_GC_MARK); // Should have been marked. if (debugOptions & DEBUG_GC_ENHANCED) Log("GC: Mark: Stack overflow. Rescan for %p\n", obj); } // Fork a new task. Because we've checked nInUse without taking the lock // we may find that we can no longer create a new task. bool MTGCProcessMarkPointers::ForkNew(PolyObject *obj) { MTGCProcessMarkPointers *marker = 0; { PLocker lock(&stackLock); if (nInUse == nThreads) return false; for (unsigned i = 0; i < nThreads; i++) { if (! markStacks[i].active) { marker = &markStacks[i]; break; } } ASSERT(marker != 0); marker->active = true; nInUse++; } bool test = gpTaskFarm->AddWork(&MTGCProcessMarkPointers::MarkPointersTask, marker, obj); ASSERT(test); return true; } // Main marking task. This is forked off initially to scan a specific object and // anything reachable from it but once that has finished it tries to find objects // on other stacks to scan. void MTGCProcessMarkPointers::MarkPointersTask(GCTaskId *, void *arg1, void *arg2) { MTGCProcessMarkPointers *marker = (MTGCProcessMarkPointers*)arg1; marker->Reset(); marker->ScanAddressesInObject((PolyObject*)arg2); while (true) { // Look for a stack that has at least one item on it. MTGCProcessMarkPointers *steal = 0; for (unsigned i = 0; i < nThreads && steal == 0; i++) { if (markStacks[i].markStack[0] != 0) steal = &markStacks[i]; } // We're finished if they're all done. if (steal == 0) break; // Look for items on this stack for (unsigned j = 0; j < MARK_STACK_SIZE; j++) { // Pick the item off the stack. // N.B. The owning thread may update this to zero // at any time. PolyObject *toSteal = steal->markStack[j]; if (toSteal == 0) break; // Nothing more on the stack // The idea here is that the original thread pushed this // because there were at least two addresses it needed to // process. It started down one branch but left the other. // Since it will have marked cells in the branch it has // followed this thread will start on the unprocessed // address(es). marker->ScanAddressesInObject(toSteal); } } PLocker lock(&stackLock); marker->active = false; // It's finished nInUse--; ASSERT(marker->markStack[0] == 0); } // Tests if this needs to be scanned. It marks it if it has not been marked // unless it has to be scanned. bool MTGCProcessMarkPointers::TestForScan(PolyWord *pt) { if ((*pt).IsTagged()) return false; // This could contain a forwarding pointer if it points into an // allocation area and has been moved by the minor GC. // We have to be a little careful. Another thread could also // be following any forwarding pointers here. However it's safe // because they will update it with the same value. PolyObject *obj = (*pt).AsObjPtr(); if (obj->ContainsForwardingPtr()) { obj = FollowForwarding(obj); *pt = obj; } MemSpace *sp = gMem.SpaceForAddress((PolyWord*)obj-1); if (sp == 0 || (sp->spaceType != ST_LOCAL && sp->spaceType != ST_CODE)) return false; // Ignore it if it points to a permanent area POLYUNSIGNED L = obj->LengthWord(); if (L & _OBJ_GC_MARK) return false; // Already marked if (debugOptions & DEBUG_GC_DETAIL) Log("GC: Mark: %p %" POLYUFMT " %u\n", obj, OBJ_OBJECT_LENGTH(L), GetTypeBits(L)); if (OBJ_IS_BYTE_OBJECT(L)) { obj->SetLengthWord(L | _OBJ_GC_MARK); // Mark it return false; // We've done as much as we need } return true; } void MTGCProcessMarkPointers::MarkAndTestForScan(PolyWord *pt) { if (TestForScan(pt)) { PolyObject *obj = (*pt).AsObjPtr(); obj->SetLengthWord(obj->LengthWord() | _OBJ_GC_MARK); } } // The initial entry to process the roots. These may be RTS addresses or addresses in // a thread stack. Also called recursively to process the addresses of constants in // code segments. This is used in situations where a scanner may return the // updated address of an object. PolyObject *MTGCProcessMarkPointers::ScanObjectAddress(PolyObject *obj) { MemSpace *sp = gMem.SpaceForAddress((PolyWord*)obj-1); if (!(sp->spaceType == ST_LOCAL || sp->spaceType == ST_CODE)) return obj; // Ignore it if it points to a permanent area // We may have a forwarding pointer if this has been moved by the // minor GC. if (obj->ContainsForwardingPtr()) { obj = FollowForwarding(obj); sp = gMem.SpaceForAddress((PolyWord*)obj - 1); } ASSERT(obj->ContainsNormalLengthWord()); POLYUNSIGNED L = obj->LengthWord(); if (L & _OBJ_GC_MARK) return obj; // Already marked sp->writeAble(obj)->SetLengthWord(L | _OBJ_GC_MARK); // Mark it if (profileMode == kProfileLiveData || (profileMode == kProfileLiveMutables && obj->IsMutable())) AddObjectProfile(obj); POLYUNSIGNED n = OBJ_OBJECT_LENGTH(L); if (debugOptions & DEBUG_GC_DETAIL) Log("GC: Mark: %p %" POLYUFMT " %u\n", obj, n, GetTypeBits(L)); if (OBJ_IS_BYTE_OBJECT(L)) return obj; // If we already have something on the stack we must being called // recursively to process a constant in a code segment. Just push // it on the stack and let the caller deal with it. if (msp != 0) PushToStack(obj); // Can't check this because it may have forwarding ptrs. else { // Normally a root but this can happen if we're following constants in code. // In that case we want to make sure that we don't recurse too deeply and // overflow the C stack. Push the address to the stack before calling // ScanAddressesInObject so that if we come back here msp will be non-zero. // ScanAddressesInObject will empty the stack. PushToStack(obj); MTGCProcessMarkPointers::ScanAddressesInObject(obj, L); // We can only check after we've processed it because if we // have addresses left over from an incomplete partial GC they // may need to forwarded. CheckObject (obj); } return obj; } // These functions are only called with pointers held by the runtime system. // Weak references can occur in the runtime system, eg. streams and windows. // Weak references are not marked and so unreferenced streams and windows // can be detected and closed. void MTGCProcessMarkPointers::ScanRuntimeAddress(PolyObject **pt, RtsStrength weak) { if (weak == STRENGTH_WEAK) return; *pt = ScanObjectAddress(*pt); CheckPointer (*pt); // Check it after any forwarding pointers have been followed. } // This is called via ScanAddressesInRegion to process the permanent mutables. It is // also called from ScanObjectAddress to process root addresses. // It processes all the addresses reachable from the object. // This is almost the same as RecursiveScan::ScanAddressesInObject. void MTGCProcessMarkPointers::ScanAddressesInObject(PolyObject *obj, POLYUNSIGNED lengthWord) { if (OBJ_IS_BYTE_OBJECT(lengthWord)) return; while (true) { ASSERT (OBJ_IS_LENGTH(lengthWord)); POLYUNSIGNED length = OBJ_OBJECT_LENGTH(lengthWord); PolyWord *baseAddr = (PolyWord*)obj; PolyWord *endWord = baseAddr + length; if (OBJ_IS_WEAKREF_OBJECT(lengthWord)) { // Special case. ASSERT(OBJ_IS_MUTABLE_OBJECT(lengthWord)); // Should be a mutable. ASSERT(OBJ_IS_WORD_OBJECT(lengthWord)); // Should be a plain object. // We need to mark the "SOME" values in this object but we don't mark // the references contained within the "SOME". // Mark every word but ignore the result. for (POLYUNSIGNED i = 0; i < length; i++) (void)MarkAndTestForScan(baseAddr+i); // We've finished with this. endWord = baseAddr; } else if (OBJ_IS_CODE_OBJECT(lengthWord)) { // Code addresses in the native code versions. // Closure cells are normal (word) objects and code addresses are normal addresses. // It's better to process the whole code object in one go. ScanAddress::ScanAddressesInObject(obj, lengthWord); endWord = baseAddr; // Finished } else if (OBJ_IS_CLOSURE_OBJECT(lengthWord)) { // Closure cells in 32-in-64. // The first word is the absolute address of the code ... PolyObject *codeAddr = *(PolyObject**)obj; // except that it is possible we haven't yet set it. if (((uintptr_t)codeAddr & 1) == 0) ScanObjectAddress(codeAddr); // The rest is a normal tuple. baseAddr += sizeof(PolyObject*) / sizeof(PolyWord); } // If there are only two addresses in this cell that need to be // followed we follow them immediately and treat this cell as done. // If there are more than two we push the address of this cell on // the stack, follow the first address and then rescan it. That way // list cells are processed once only but we don't overflow the // stack by pushing all the addresses in a very large vector. PolyObject *firstWord = 0; PolyObject *secondWord = 0; PolyWord *restartAddr = 0; if (obj == largeObjectCache[locPtr].base) { baseAddr = largeObjectCache[locPtr].current; ASSERT(baseAddr > (PolyWord*)obj && baseAddr < endWord); if (locPtr == 0) locPtr = LARGECACHE_SIZE - 1; else locPtr--; } while (baseAddr != endWord) { PolyWord wordAt = *baseAddr; if (wordAt.IsDataPtr() && wordAt != PolyWord::FromUnsigned(0)) { // Normal address. We can have words of all zeros at least in the // situation where we have a partially constructed code segment where // the constants at the end of the code have not yet been filled in. if (TestForScan(baseAddr)) { if (firstWord == 0) firstWord = baseAddr->AsObjPtr(); else if (secondWord == 0) { // If we need to rescan because there are three or more words to do // this is the place we need to restart (or the start of the cell if it's // small). restartAddr = baseAddr; secondWord = baseAddr->AsObjPtr(); } else break; // More than two words. } } baseAddr++; } if (baseAddr != endWord) // Put this back on the stack while we process the first word PushToStack(obj, length < largeObjectSize ? 0 : restartAddr); else if (secondWord != 0) { // Mark it now because we will process it. PolyObject* writeAble = secondWord; if (secondWord->IsCodeObject()) - writeAble = gMem.SpaceForAddress(secondWord)->writeAble(secondWord); + writeAble = gMem.SpaceForObjectAddress(secondWord)->writeAble(secondWord); writeAble->SetLengthWord(secondWord->LengthWord() | _OBJ_GC_MARK); // Put this on the stack. If this is a list node we will be // pushing the tail. PushToStack(secondWord); } if (firstWord != 0) { // Mark it and process it immediately. PolyObject* writeAble = firstWord; if (firstWord->IsCodeObject()) - writeAble = gMem.SpaceForAddress(firstWord)->writeAble(firstWord); + writeAble = gMem.SpaceForObjectAddress(firstWord)->writeAble(firstWord); writeAble->SetLengthWord(firstWord->LengthWord() | _OBJ_GC_MARK); obj = firstWord; } else if (msp == 0) { markStack[msp] = 0; // Really finished return; } else { // Clear the item above the top. This really is finished. if (msp < MARK_STACK_SIZE) markStack[msp] = 0; // Pop the item from the stack but don't overwrite it yet. // This allows another thread to steal it if there really // is nothing else to do. This is only really important // for large objects. obj = markStack[--msp]; // Pop something. } lengthWord = obj->LengthWord(); } } // Process a constant within the code. This is a direct copy of ScanAddress::ScanConstant // with the addition of the locking. void MTGCProcessMarkPointers::ScanConstant(PolyObject *base, byte *addressOfConstant, ScanRelocationKind code) { // If we have newly compiled code the constants may be in the // local heap. MTGCProcessMarkPointers::ScanObjectAddress can // return an updated address for a local address if there is a // forwarding pointer. // Constants can be aligned on any byte offset so another thread // scanning the same code could see an invalid address if it read // the constant while it was being updated. We put a lock round // this just in case. MemSpace *space = gMem.SpaceForAddress(addressOfConstant); PLock *lock = 0; if (space->spaceType == ST_CODE) lock = &((CodeSpace*)space)->spaceLock; if (lock != 0) lock->Lock(); PolyObject *p = GetConstantValue(addressOfConstant, code); if (lock != 0) lock->Unlock(); if (p != 0) { PolyObject *newVal = ScanObjectAddress(p); if (newVal != p) // Update it if it has changed. { if (lock != 0) lock->Lock(); SetConstantValue(addressOfConstant, newVal, code); if (lock != 0) lock->Unlock(); } } } // Mark all the roots. This is run in the main thread and has the effect // of starting new tasks as the scanning runs. void MTGCProcessMarkPointers::MarkRoots(void) { ASSERT(nThreads >= 1); ASSERT(nInUse == 0); MTGCProcessMarkPointers *marker = &markStacks[0]; marker->Reset(); marker->active = true; nInUse = 1; // Scan the permanent mutable areas. for (std::vector::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) { PermanentMemSpace *space = *i; if (space->isMutable && ! space->byteOnly) marker->ScanAddressesInRegion(space->bottom, space->top); } // Scan the RTS roots. GCModules(marker); ASSERT(marker->markStack[0] == 0); // When this has finished there may well be other tasks running. PLocker lock(&stackLock); marker->active = false; nInUse--; } // This class just allows us to use ScanAddress::ScanAddressesInRegion to call // ScanAddressesInObject for each object in the region. class Rescanner: public ScanAddress { public: Rescanner(MTGCProcessMarkPointers *marker): m_marker(marker) {} virtual void ScanAddressesInObject(PolyObject *obj, POLYUNSIGNED lengthWord) { // If it has previously been marked it is known to be reachable but // the contents may not have been scanned if the stack overflowed. if (lengthWord &_OBJ_GC_MARK) m_marker->ScanAddressesInObject(obj, lengthWord); } // Have to define this. virtual PolyObject *ScanObjectAddress(PolyObject *base) { ASSERT(false); return 0; } virtual POLYUNSIGNED ScanCodeAddressAt(PolyObject **pt) { ASSERT(false); return 0; } bool ScanSpace(MarkableSpace *space); private: MTGCProcessMarkPointers *m_marker; }; // Rescan any marked objects in the area between fullGCRescanStart and fullGCRescanEnd. // N.B. We may have threads already processing other areas and they could overflow // their stacks and change fullGCRescanStart or fullGCRescanEnd. bool Rescanner::ScanSpace(MarkableSpace *space) { PolyWord *start, *end; { PLocker lock(&space->spaceLock); start = space->fullGCRescanStart; end = space->fullGCRescanEnd; space->fullGCRescanStart = space->top; space->fullGCRescanEnd = space->bottom; } if (start < end) { if (debugOptions & DEBUG_GC_ENHANCED) Log("GC: Mark: Rescanning from %p to %p\n", start, end); ScanAddressesInRegion(start, end); return true; // Require rescan } else return false; } // When the threads created by marking the roots have completed we need to check that // the mark stack has not overflowed. If it has we need to rescan. This rescanning // pass may result in a further overflow so if we find we have to rescan we repeat. bool MTGCProcessMarkPointers::RescanForStackOverflow() { ASSERT(nThreads >= 1); ASSERT(nInUse == 0); MTGCProcessMarkPointers *marker = &markStacks[0]; marker->Reset(); marker->active = true; nInUse = 1; bool rescan = false; Rescanner rescanner(marker); for (std::vector::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) { if (rescanner.ScanSpace(*i)) rescan = true; } for (std::vector::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) { if (rescanner.ScanSpace(*i)) rescan = true; } { PLocker lock(&stackLock); nInUse--; marker->active = false; } return rescan; } static void SetBitmaps(LocalMemSpace *space, PolyWord *pt, PolyWord *top) { while (pt < top) { #ifdef POLYML32IN64 if ((((uintptr_t)pt) & 4) == 0) { pt++; continue; } #endif PolyObject *obj = (PolyObject*)++pt; // If it has been copied by a minor collection skip it if (obj->ContainsForwardingPtr()) { obj = FollowForwarding(obj); ASSERT(obj->ContainsNormalLengthWord()); pt += obj->Length(); } else { POLYUNSIGNED L = obj->LengthWord(); POLYUNSIGNED n = OBJ_OBJECT_LENGTH(L); if (L & _OBJ_GC_MARK) { obj->SetLengthWord(L & ~(_OBJ_GC_MARK)); uintptr_t bitno = space->wordNo(pt); space->bitmap.SetBits(bitno - 1, n + 1); if (OBJ_IS_MUTABLE_OBJECT(L)) space->m_marked += n + 1; else space->i_marked += n + 1; if ((PolyWord*)obj <= space->fullGCLowerLimit) space->fullGCLowerLimit = (PolyWord*)obj-1; if (OBJ_IS_WEAKREF_OBJECT(L)) { // Add this to the limits for the containing area. PolyWord *baseAddr = (PolyWord*)obj; PolyWord *startAddr = baseAddr-1; // Must point AT length word. PolyWord *endObject = baseAddr + n; if (startAddr < space->lowestWeak) space->lowestWeak = startAddr; if (endObject > space->highestWeak) space->highestWeak = endObject; } } pt += n; } } } static void CreateBitmapsTask(GCTaskId *, void *arg1, void *arg2) { LocalMemSpace *lSpace = (LocalMemSpace *)arg1; lSpace->bitmap.ClearBits(0, lSpace->spaceSize()); SetBitmaps(lSpace, lSpace->bottom, lSpace->top); } // Parallel task to check the marks on cells in the code area and // turn them into byte areas if they are free. static void CheckMarksOnCodeTask(GCTaskId *, void *arg1, void *arg2) { CodeSpace *space = (CodeSpace*)arg1; #ifdef POLYML32IN64 PolyWord *pt = space->bottom+1; #else PolyWord *pt = space->bottom; #endif PolyWord *lastFree = 0; POLYUNSIGNED lastFreeSpace = 0; space->largestFree = 0; space->firstFree = 0; while (pt < space->top) { PolyObject *obj = (PolyObject*)(pt+1); // There should not be forwarding pointers ASSERT(obj->ContainsNormalLengthWord()); POLYUNSIGNED L = obj->LengthWord(); POLYUNSIGNED length = OBJ_OBJECT_LENGTH(L); if (L & _OBJ_GC_MARK) { // It's marked - retain it. ASSERT(L & _OBJ_CODE_OBJ); space->writeAble(obj)->SetLengthWord(L & ~(_OBJ_GC_MARK)); // Clear the mark bit lastFree = 0; lastFreeSpace = 0; } #ifdef POLYML32IN64 else if (length == 0) { // We may have zero filler words to set the correct alignment. // Merge them into a previously free area otherwise leave // them if they're after something allocated. if (lastFree + lastFreeSpace == pt) { lastFreeSpace += length + 1; PolyObject *freeSpace = (PolyObject*)(lastFree + 1); space->writeAble(freeSpace)->SetLengthWord(lastFreeSpace - 1, F_BYTE_OBJ); } } #endif else { // Turn it into a byte area i.e. free. It may already be free. if (space->firstFree == 0) space->firstFree = pt; space->headerMap.ClearBit(pt-space->bottom); // Remove the "header" bit if (lastFree + lastFreeSpace == pt) // Merge free spaces. Speeds up subsequent scans. lastFreeSpace += length + 1; else { lastFree = pt; lastFreeSpace = length + 1; } PolyObject *freeSpace = (PolyObject*)(lastFree+1); space->writeAble(freeSpace)->SetLengthWord(lastFreeSpace-1, F_BYTE_OBJ); if (lastFreeSpace > space->largestFree) space->largestFree = lastFreeSpace; } pt += length+1; } } void GCMarkPhase(void) { mainThreadPhase = MTP_GCPHASEMARK; // Clear the mark counters and set the rescan limits. for(std::vector::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) { LocalMemSpace *lSpace = *i; lSpace->i_marked = lSpace->m_marked = 0; lSpace->fullGCRescanStart = lSpace->top; lSpace->fullGCRescanEnd = lSpace->bottom; } for (std::vector::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) { CodeSpace *space = *i; space->fullGCRescanStart = space->top; space->fullGCRescanEnd = space->bottom; } MTGCProcessMarkPointers::MarkRoots(); gpTaskFarm->WaitForCompletion(); // Do we have to rescan because the mark stack overflowed? bool rescan; do { rescan = MTGCProcessMarkPointers::RescanForStackOverflow(); gpTaskFarm->WaitForCompletion(); } while(rescan); gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeIntermediate, "Mark"); // Turn the marks into bitmap entries. for (std::vector::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) gpTaskFarm->AddWorkOrRunNow(&CreateBitmapsTask, *i, 0); // Process the code areas. for (std::vector::iterator i = gMem.cSpaces.begin(); i < gMem.cSpaces.end(); i++) gpTaskFarm->AddWorkOrRunNow(&CheckMarksOnCodeTask, *i, 0); gpTaskFarm->WaitForCompletion(); // Wait for completion of the bitmaps gMem.RemoveEmptyCodeAreas(); gHeapSizeParameters.RecordGCTime(HeapSizeParameters::GCTimeIntermediate, "Bitmap"); uintptr_t totalLive = 0; for(std::vector::iterator i = gMem.lSpaces.begin(); i < gMem.lSpaces.end(); i++) { LocalMemSpace *lSpace = *i; if (! lSpace->isMutable) ASSERT(lSpace->m_marked == 0); totalLive += lSpace->m_marked + lSpace->i_marked; if (debugOptions & DEBUG_GC_ENHANCED) Log("GC: Mark: %s space %p: %" POLYUFMT " immutable words marked, %" POLYUFMT " mutable words marked\n", lSpace->spaceTypeString(), lSpace, lSpace->i_marked, lSpace->m_marked); } if (debugOptions & DEBUG_GC) Log("GC: Mark: Total live data %" POLYUFMT " words\n", totalLive); } // Set up the stacks. void initialiseMarkerTables() { unsigned threads = gpTaskFarm->ThreadCount(); if (threads == 0) threads = 1; MTGCProcessMarkPointers::InitStatics(threads); } diff --git a/libpolyml/memmgr.h b/libpolyml/memmgr.h index 2bcc968e..9b1bdb3a 100644 --- a/libpolyml/memmgr.h +++ b/libpolyml/memmgr.h @@ -1,423 +1,440 @@ /* Title: memmgr.h Memory segment manager - Copyright (c) 2006-8, 2010-12, 2016-18 David C. J. Matthews + Copyright (c) 2006-8, 2010-12, 2016-18, 2020 David C. J. Matthews This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef MEMMGR_H #define MEMMGR_H #include "bitmap.h" #include "locking.h" #include "osmem.h" #include // utility conversion macros #define Words_to_K(w) (w*sizeof(PolyWord))/1024 #define Words_to_M(w) (w*sizeof(PolyWord))/(1<<20) #define B_to_M(b) (b/(1<<20)) class ScanAddress; class GCTaskId; class TaskData; typedef enum { ST_PERMANENT, // Permanent areas are part of the object code // Also loaded saved state. ST_LOCAL, // Local heaps contain volatile data ST_EXPORT, // Temporary export area ST_STACK, // ML Stack for a thread ST_CODE // Code created in the current run } SpaceType; // B-tree used in SpaceForAddress. Leaves are MemSpaces. class SpaceTree { public: SpaceTree(bool is): isSpace(is) { } virtual ~SpaceTree() {} bool isSpace; }; // A non-leaf node in the B-tree class SpaceTreeTree: public SpaceTree { public: SpaceTreeTree(); virtual ~SpaceTreeTree(); SpaceTree *tree[256]; }; // Base class for the various memory spaces. class MemSpace: public SpaceTree { protected: MemSpace(OSMem *alloc); virtual ~MemSpace(); public: SpaceType spaceType; bool isMutable; bool isCode; PolyWord *bottom; // Bottom of area PolyWord *top; // Top of area. OSMem *allocator; // Used to free the area. May be null. PolyWord *shadowSpace; // Extra writable area for code if necessary uintptr_t spaceSize(void)const { return top-bottom; } // No of words // These next two are used in the GC to limit scanning for // weak refs. PolyWord *lowestWeak, *highestWeak; // Used when printing debugging info virtual const char *spaceTypeString() { return isMutable ? "mutable" : "immutable"; } // Return the writeable address if this is in read-only code. byte* writeAble(byte* p) { if (shadowSpace != 0) return (p - (byte*)bottom + (byte*)shadowSpace); else return p; } PolyWord* writeAble(PolyWord* p) { if (shadowSpace != 0) return (p - bottom + shadowSpace); else return p; } PolyObject* writeAble(PolyObject* p) { return (PolyObject*)writeAble((PolyWord *) p); } friend class MemMgr; }; // Permanent memory space. Either linked into the executable program or // loaded from a saved state file. class PermanentMemSpace: public MemSpace { protected: PermanentMemSpace(OSMem *alloc): MemSpace(alloc), index(0), hierarchy(0), noOverwrite(false), byteOnly(false), topPointer(0) {} public: unsigned index; // An identifier for the space. Used when saving and loading. unsigned hierarchy; // The hierarchy number: 0=from executable, 1=top level saved state, ... bool noOverwrite; // Don't save this in deeper hierarchies. bool byteOnly; // Only contains byte data - no need to scan for addresses. // When exporting or saving state we copy data into a new area. // This area grows upwards unlike the local areas that grow down. PolyWord *topPointer; Bitmap shareBitmap; // Used in sharedata Bitmap profileCode; // Used when profiling friend class MemMgr; }; #define NSTARTS 10 // Markable spaces are used as the base class for local heap // spaces and code spaces. class MarkableSpace: public MemSpace { protected: MarkableSpace(OSMem *alloc); virtual ~MarkableSpace() {} public: PolyWord *fullGCRescanStart; // Upper and lower limits for rescan during mark phase. PolyWord *fullGCRescanEnd; PLock spaceLock; // Lock used to protect forwarding pointers }; // Local areas can be garbage collected. class LocalMemSpace: public MarkableSpace { protected: LocalMemSpace(OSMem *alloc); virtual ~LocalMemSpace() {} bool InitSpace(PolyWord *heapPtr, uintptr_t size, bool mut); public: // Allocation. The minor GC allocates at the bottom of the areas while the // major GC and initial allocations are made at the top. The reason for this // is that it's only possible to scan objects from the bottom up and the minor // GC combines scanning with allocation whereas the major GC compacts from the // bottom into the top of an area. PolyWord *upperAllocPtr; // Allocation pointer. Objects are allocated AFTER this. PolyWord *lowerAllocPtr; // Allocation pointer. Objects are allocated BEFORE this. PolyWord *fullGCLowerLimit;// Lowest object in area before copying. PolyWord *partialGCTop; // Value of upperAllocPtr before the current partial GC. PolyWord *partialGCScan; // Scan pointer used in minor GC PolyWord *partialGCRootBase; // Start of the root objects. PolyWord *partialGCRootTop;// Value of lowerAllocPtr after the roots have been copied. GCTaskId *spaceOwner; // The thread that "owns" this space during a GC. Bitmap bitmap; /* bitmap with one bit for each word in the GC area. */ PLock bitmapLock; // Lock used in GC sharing pass. bool allocationSpace; // True if this is (mutable) space for initial allocation uintptr_t start[NSTARTS]; /* starting points for bit searches. */ unsigned start_index; /* last index used to index start array */ uintptr_t i_marked; /* count of immutable words marked. */ uintptr_t m_marked; /* count of mutable words marked. */ uintptr_t updated; /* count of words updated. */ uintptr_t allocatedSpace(void)const // Words allocated { return (top-upperAllocPtr) + (lowerAllocPtr-bottom); } uintptr_t freeSpace(void)const // Words free { return upperAllocPtr-lowerAllocPtr; } #ifdef POLYML32IN64 // We will generally set a zero cell for alignment. bool isEmpty(void)const { return allocatedSpace() <= 1; } #else bool isEmpty(void)const { return allocatedSpace() == 0; } #endif virtual const char *spaceTypeString() { return allocationSpace ? "allocation" : MemSpace::spaceTypeString(); } // Used when converting to and from bit positions in the bitmap uintptr_t wordNo(PolyWord *pt) { return pt - bottom; } PolyWord *wordAddr(uintptr_t bitno) { return bottom + bitno; } friend class MemMgr; }; class StackObject; // Abstract - Architecture specific // Stack spaces. These are managed by the thread module class StackSpace: public MemSpace { public: StackSpace(OSMem *alloc): MemSpace(alloc) { } StackObject *stack()const { return (StackObject *)bottom; } }; // Code Space. These contain local code created by the compiler. class CodeSpace: public MarkableSpace { public: CodeSpace(PolyWord *start, PolyWord *shadow, uintptr_t spaceSize, OSMem *alloc); Bitmap headerMap; // Map to find the headers during GC or profiling. uintptr_t largestFree; // The largest free space in the area PolyWord *firstFree; // The start of the first free space in the area. }; class MemMgr { public: MemMgr(); ~MemMgr(); bool Initialise(); // Create a local space for initial allocation. LocalMemSpace *CreateAllocationSpace(uintptr_t size); // Create and initialise a new local space and add it to the table. LocalMemSpace *NewLocalSpace(uintptr_t size, bool mut); // Create an entry for a permanent space. PermanentMemSpace *NewPermanentSpace(PolyWord *base, uintptr_t words, unsigned flags, unsigned index, unsigned hierarchy = 0); // Create a permanent space but allocate memory for it. // Sets bottom and top to the actual memory size. PermanentMemSpace *AllocateNewPermanentSpace(uintptr_t byteSize, unsigned flags, unsigned index, unsigned hierarchy = 0); // Called after an allocated permanent area has been filled in. bool CompletePermanentSpaceAllocation(PermanentMemSpace *space); // Delete a local space. Takes the iterator position in lSpaces and returns the // iterator after deletion. void DeleteLocalSpace(std::vector::iterator &iter); // Allocate an area of the heap of at least minWords and at most maxWords. // This is used both when allocating single objects (when minWords and maxWords // are the same) and when allocating heap segments. If there is insufficient // space to satisfy the minimum it will return 0. Updates "maxWords" with // the space actually allocated PolyWord *AllocHeapSpace(uintptr_t minWords, uintptr_t &maxWords, bool doAllocation = true); PolyWord *AllocHeapSpace(uintptr_t words) { uintptr_t allocated = words; return AllocHeapSpace(words, allocated); } CodeSpace *NewCodeSpace(uintptr_t size); // Allocate space for code. This is initially mutable to allow the code to be built. PolyObject *AllocCodeSpace(POLYUNSIGNED size); // Check that a subsequent allocation will succeed. Called from the GC to ensure bool CheckForAllocation(uintptr_t words); // If an allocation space has a lot of data left in it, particularly a single // large object we should turn it into a local area. void ConvertAllocationSpaceToLocal(LocalMemSpace *space); // Allocate space for the initial stack for a thread. The caller must // initialise the new stack. Returns 0 if allocation fails. StackSpace *NewStackSpace(uintptr_t size); // Adjust the space for a stack. Returns true if it succeeded. If it failed // it leaves the stack untouched. bool GrowOrShrinkStack(TaskData *taskData, uintptr_t newSize); // Delete a stack when a thread has finished. bool DeleteStackSpace(StackSpace *space); // Create and delete export spaces PermanentMemSpace *NewExportSpace(uintptr_t size, bool mut, bool noOv, bool code); void DeleteExportSpaces(void); bool PromoteExportSpaces(unsigned hierarchy); // Turn export spaces into permanent spaces. bool DemoteImportSpaces(void); // Turn previously imported spaces into local. PermanentMemSpace *SpaceForIndex(unsigned index); // Return the space for a given index // As a debugging check, write protect the immutable areas apart from during the GC. void ProtectImmutable(bool on); // Find a space that contains a given address. This is called for every cell // during a GC so needs to be fast., // N.B. This must be called on an address at the beginning or within the cell. // Generally that means with a pointer to the length word. Pointing at the // first "data" word may give the wrong result if the length is zero. MemSpace *SpaceForAddress(const void *pt) const { uintptr_t t = (uintptr_t)pt; SpaceTree *tr = spaceTree; // Each level of the tree is either a leaf or a vector of trees. unsigned j = sizeof(void *)*8; for (;;) { if (tr == 0 || tr->isSpace) return (MemSpace*)tr; j -= 8; tr = ((SpaceTreeTree*)tr)->tree[(t >> j) & 0xff]; } return 0; } + // SpaceForAddress must NOT be applied to a PolyObject *. That's because + // it works nearly all the time except when a zero-sized object is placed + // at the end of page. Then the base address will be the start of the + // next page. + void SpaceForAddress(PolyObject *pt) {} + + // Use this instead. + MemSpace* SpaceForObjectAddress(PolyObject* pt) + { return SpaceForAddress(((PolyWord*)pt) - 1); } + // Find a local address for a space. // N.B. The argument should generally be the length word. See // comment on SpaceForAddress. LocalMemSpace *LocalSpaceForAddress(const void *pt) const { MemSpace *s = SpaceForAddress(pt); if (s != 0 && s->spaceType == ST_LOCAL) return (LocalMemSpace*)s; else return 0; } + // LocalSpaceForAddress must NOT be applied to PolyObject*. + // See comment on SpaceForAddress above. + void LocalSpaceForAddress(PolyObject* pt) {} + + LocalMemSpace* LocalSpaceForObjectAddress(PolyObject* pt) + { return LocalSpaceForAddress(((PolyWord*)pt) - 1); } + void SetReservation(uintptr_t words) { reservedSpace = words; } // In several places we assume that segments are filled with valid // objects. This fills unused memory with one or more "byte" objects. void FillUnusedSpace(PolyWord *base, uintptr_t words); // Return number of words of free space for stats. uintptr_t GetFreeAllocSpace(); // Remove unused local areas. void RemoveEmptyLocals(); // Remove unused code areas. void RemoveEmptyCodeAreas(); // Remove unused allocation areas to reduce the space below the limit. void RemoveExcessAllocation(uintptr_t words); void RemoveExcessAllocation() { RemoveExcessAllocation(spaceBeforeMinorGC); } // Table for permanent spaces std::vector pSpaces; // Table for local spaces std::vector lSpaces; // Table for export spaces std::vector eSpaces; // Table for stack spaces std::vector sSpaces; PLock stackSpaceLock; // Table for code spaces std::vector cSpaces; PLock codeSpaceLock; // Storage manager lock. PLock allocLock; // Lock for creating new bitmaps for code profiling PLock codeBitmapLock; unsigned nextIndex; // Used when allocating new permanent spaces. uintptr_t SpaceBeforeMinorGC() const { return spaceBeforeMinorGC; } uintptr_t SpaceForHeap() const { return spaceForHeap; } void SetSpaceBeforeMinorGC(uintptr_t minorSize) { spaceBeforeMinorGC = minorSize; } void SetSpaceForHeap(uintptr_t heapSize) { spaceForHeap = heapSize; } uintptr_t CurrentAllocSpace() { return currentAllocSpace; } uintptr_t AllocatedInAlloc(); uintptr_t CurrentHeapSize() { return currentHeapSize; } uintptr_t DefaultSpaceSize() const { return defaultSpaceSize; } void ReportHeapSizes(const char *phase); // Profiling - Find a code object or return zero if not found. PolyObject *FindCodeObject(const byte *addr); // Profiling - Free bitmaps to indicate start of an object. void RemoveProfilingBitmaps(); private: bool AddLocalSpace(LocalMemSpace *space); bool AddCodeSpace(CodeSpace *space); uintptr_t reservedSpace; unsigned nextAllocator; // The default size in words when creating new segments. uintptr_t defaultSpaceSize; // The number of words that can be used for initial allocation. uintptr_t spaceBeforeMinorGC; // The number of words that can be used for the heap uintptr_t spaceForHeap; // The current sizes of the allocation space and the total heap size. uintptr_t currentAllocSpace, currentHeapSize; // LocalSpaceForAddress is a hot-spot so we use a B-tree to convert addresses; SpaceTree *spaceTree; PLock spaceTreeLock; void AddTree(MemSpace *space) { AddTree(space, space->bottom, space->top); } void RemoveTree(MemSpace *space) { RemoveTree(space, space->bottom, space->top); } void AddTree(MemSpace *space, PolyWord *startS, PolyWord *endS); void RemoveTree(MemSpace *space, PolyWord *startS, PolyWord *endS); void AddTreeRange(SpaceTree **t, MemSpace *space, uintptr_t startS, uintptr_t endS); void RemoveTreeRange(SpaceTree **t, MemSpace *space, uintptr_t startS, uintptr_t endS); OSMem osHeapAlloc, osStackAlloc, osCodeAlloc; }; extern MemMgr gMem; #endif diff --git a/libpolyml/pexport.cpp b/libpolyml/pexport.cpp index fb705d9a..cf11b4d2 100644 --- a/libpolyml/pexport.cpp +++ b/libpolyml/pexport.cpp @@ -1,873 +1,873 @@ /* Title: Export and import memory in a portable format Author: David C. J. Matthews. Copyright (c) 2006-7, 2015-8, 2020 David C. J. Matthews This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR H PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifdef HAVE_CONFIG_H #include "config.h" #elif defined(_WIN32) #include "winconfig.h" #else #error "No configuration file" #endif #ifdef HAVE_STDIO_H #include #endif #ifdef HAVE_ERRNO_H #include #endif #ifdef HAVE_ASSERT_H #include #define ASSERT(x) assert(x) #else #define ASSERT(x) #endif #include "globals.h" #include "pexport.h" #include "machine_dep.h" #include "scanaddrs.h" #include "run_time.h" #include "../polyexports.h" #include "version.h" #include "sys.h" #include "polystring.h" #include "memmgr.h" #include "rtsentry.h" #include "mpoly.h" // For polyStderr /* This file contains the code both to export the file and to import it in a new session. */ PExport::PExport() { } PExport::~PExport() { } // Get the index corresponding to an address. size_t PExport::getIndex(PolyObject *p) { // Binary chop to find the index from the address. size_t lower = 0, upper = pMap.size(); while (1) { ASSERT(lower < upper); size_t middle = (lower+upper)/2; ASSERT(middle < pMap.size()); if (p < pMap[middle]) { // Use lower to middle upper = middle; } else if (p > pMap[middle]) { // Use middle+1 to upper lower = middle+1; } else // Found it return middle; } } /* Get the index corresponding to an address. */ void PExport::printAddress(void *p) { fprintf(exportFile, "@%" PRI_SIZET "", getIndex((PolyObject*)p)); } void PExport::printValue(PolyWord q) { if (IS_INT(q) || q == PolyWord::FromUnsigned(0)) fprintf(exportFile, "%" POLYSFMT, UNTAGGED(q)); else printAddress(q.AsAddress()); } void PExport::printObject(PolyObject *p) { POLYUNSIGNED length = p->Length(); POLYUNSIGNED i; size_t myIndex = getIndex(p); fprintf(exportFile, "%" PRI_SIZET ":", myIndex); if (p->IsMutable()) putc('M', exportFile); if (OBJ_IS_NEGATIVE(p->LengthWord())) putc('N', exportFile); if (OBJ_IS_WEAKREF_OBJECT(p->LengthWord())) putc('W', exportFile); if (OBJ_IS_NO_OVERWRITE(p->LengthWord())) putc('V', exportFile); if (p->IsByteObject()) { if (p->IsMutable() && p->IsWeakRefObject() && p->Length() >= sizeof(uintptr_t) / sizeof(PolyWord)) { // This is either an entry point or a weak ref used in the FFI. // Clear the first word if (p->Length() == sizeof(uintptr_t)/sizeof(PolyWord)) putc('K', exportFile); // Weak ref else if (p->Length() > sizeof(uintptr_t) / sizeof(PolyWord)) { // Entry point - C null-terminated string. putc('E', exportFile); const char* name = (char*)p + sizeof(uintptr_t); fprintf(exportFile, "%" PRI_SIZET "|%s", strlen(name), name); *(uintptr_t*)p = 0; // Entry point } } else { /* May be a string, a long format arbitrary precision number or a real number. */ PolyStringObject* ps = (PolyStringObject*)p; /* This is not infallible but it seems to be good enough to detect the strings. */ POLYUNSIGNED bytes = length * sizeof(PolyWord); if (length >= 2 && ps->length <= bytes - sizeof(POLYUNSIGNED) && ps->length > bytes - 2 * sizeof(POLYUNSIGNED)) { /* Looks like a string. */ fprintf(exportFile, "S%" POLYUFMT "|", ps->length); for (unsigned i = 0; i < ps->length; i++) { char ch = ps->chars[i]; fprintf(exportFile, "%02x", ch & 0xff); } } else { /* Not a string. May be an arbitrary precision integer. If the source and destination word lengths differ we could find that some long-format arbitrary precision numbers could be represented in the tagged short form or vice-versa. The former case might give rise to errors because when comparing two arbitrary precision numbers for equality we assume that they are not equal if they have different representation. The latter case could be a problem because we wouldn't know whether to convert the tagged form to long form, which would be correct if the value has type "int" or to truncate it which would be correct for "word". It could also be a real number but that doesn't matter if we recompile everything on the new machine. */ byte* u = (byte*)p; putc('B', exportFile); fprintf(exportFile, "%" PRI_SIZET "|", length * sizeof(PolyWord)); for (unsigned i = 0; i < (unsigned)(length * sizeof(PolyWord)); i++) { fprintf(exportFile, "%02x", u[i]); } } } } else if (p->IsCodeObject()) { POLYUNSIGNED constCount, i; PolyWord *cp; ASSERT(! p->IsMutable() ); /* Work out the number of bytes in the code and the number of constants. */ p->GetConstSegmentForCode(cp, constCount); /* The byte count is the length of the segment minus the number of constants minus one for the constant count. It includes the marker word, byte count, profile count and, on the X86/64 at least, any non-address constants. These are actually word values. */ POLYUNSIGNED byteCount = (length - constCount - 1) * sizeof(PolyWord); fprintf(exportFile, "D%" POLYUFMT ",%" POLYUFMT "|", constCount, byteCount); // First the code. byte *u = (byte*)p; for (i = 0; i < byteCount; i++) fprintf(exportFile, "%02x", u[i]); putc('|', exportFile); // Now the constants. for (i = 0; i < constCount; i++) { printValue(cp[i]); if (i < constCount-1) putc(',', exportFile); } putc('|', exportFile); // Finally any constants in the code object. machineDependent->ScanConstantsWithinCode(p, this); } else // Ordinary objects, essentially tuples, or closures. { fprintf(exportFile, "%c%" POLYUFMT "|", p->IsClosureObject() ? 'L' : 'O', length); if (p->IsClosureObject()) { // The first word is always a code address. printAddress(*(PolyObject**)p); i = sizeof(PolyObject*)/sizeof(PolyWord); if (i < length) putc(',', exportFile); } else i = 0; while (i < length) { printValue(p->Get(i)); if (i < length-1) putc(',', exportFile); i++; } } fprintf(exportFile, "\n"); } /* This is called for each constant within the code. Print a relocation entry for the word and return a value that means that the offset is saved in original word. */ void PExport::ScanConstant(PolyObject *base, byte *addr, ScanRelocationKind code) { PolyObject *p = GetConstantValue(addr, code); if (p == 0) return; // Don't put in tagged constants // Put in the byte offset and the relocation type code. POLYUNSIGNED offset = (POLYUNSIGNED)(addr - (byte*)base); ASSERT (offset < base->Length() * sizeof(POLYUNSIGNED)); fprintf(exportFile, "%" POLYUFMT ",%d,", (POLYUNSIGNED)(addr - (byte*)base), code); printAddress(p); // The value to plug in. fprintf(exportFile, " "); } void PExport::exportStore(void) { // We want the entries in pMap to be in ascending // order of address to make searching easy so we need to process the areas // in order of increasing address, which may not be the order in memTable. std::vector indexOrder; indexOrder.reserve(memTableEntries); for (size_t i = 0; i < memTableEntries; i++) { std::vector::iterator it; for (it = indexOrder.begin(); it != indexOrder.end(); it++) { if (memTable[*it].mtOriginalAddr >= memTable[i].mtOriginalAddr) break; } indexOrder.insert(it, i); } // Process the area in order of ascending address. for (std::vector::iterator i = indexOrder.begin(); i != indexOrder.end(); i++) { size_t index = *i; char *start = (char*)memTable[index].mtOriginalAddr; char *end = start + memTable[index].mtLength; for (PolyWord *p = (PolyWord*)start; p < (PolyWord*)end; ) { p++; PolyObject *obj = (PolyObject*)p; POLYUNSIGNED length = obj->Length(); pMap.push_back(obj); p += length; } } /* Start writing the information. */ fprintf(exportFile, "Objects\t%" PRI_SIZET "\n", pMap.size()); fprintf(exportFile, "Root\t%" PRI_SIZET "\n", getIndex(rootFunction)); // Generate each of the areas. for (size_t i = 0; i < memTableEntries; i++) { char *start = (char*)memTable[i].mtOriginalAddr; char *end = start + memTable[i].mtLength; for (PolyWord *p = (PolyWord*)start; p < (PolyWord*)end; ) { p++; PolyObject *obj = (PolyObject*)p; POLYUNSIGNED length = obj->Length(); #ifdef POLYML32IN64 // We may have filler cells to get the alignment right. // We mustn't try to print them. if (((uintptr_t)obj & 4) != 0 && length == 0) continue; #endif printObject(obj); p += length; } } fclose(exportFile); exportFile = NULL; } /* Import a portable export file and load it into memory. Creates "permanent" address entries in the global memory table. */ class SpaceAlloc { public: SpaceAlloc(unsigned *indexCtr, unsigned perms, POLYUNSIGNED def); PolyObject *NewObj(POLYUNSIGNED objWords); size_t defaultSize; PermanentMemSpace *memSpace; size_t used; unsigned permissions; unsigned *spaceIndexCtr; }; SpaceAlloc::SpaceAlloc(unsigned *indexCtr, unsigned perms, POLYUNSIGNED def) { permissions = perms; defaultSize = def; memSpace = 0; used = 0; spaceIndexCtr = indexCtr; } // Allocate a new object. May create a new space and add the old one to the permanent // memory table if this is exhausted. #ifndef POLYML32IN64 PolyObject *SpaceAlloc::NewObj(POLYUNSIGNED objWords) { if (memSpace == 0 || memSpace->spaceSize() - used <= objWords) { // Need some more space. size_t size = defaultSize; if (size <= objWords) size = objWords+1; memSpace = gMem.AllocateNewPermanentSpace(size * sizeof(PolyWord), permissions, *spaceIndexCtr); (*spaceIndexCtr)++; // The memory is writable until CompletePermanentSpaceAllocation is called if (memSpace == 0) { fprintf(polyStderr, "Unable to allocate memory\n"); return 0; } used = 0; } ASSERT(memSpace->spaceSize() - used > objWords); PolyObject *newObj = (PolyObject*)(memSpace->bottom + used+1); used += objWords+1; return newObj; } #else // With 32in64 we need to allocate on 8-byte boundaries. PolyObject *SpaceAlloc::NewObj(POLYUNSIGNED objWords) { size_t rounded = objWords; if ((objWords & 1) == 0) rounded++; if (memSpace == 0 || memSpace->spaceSize() - used <= rounded) { // Need some more space. size_t size = defaultSize; if (size <= rounded) size = rounded + 1; memSpace = gMem.AllocateNewPermanentSpace(size * sizeof(PolyWord), permissions, *spaceIndexCtr); (*spaceIndexCtr)++; // The memory is writable until CompletePermanentSpaceAllocation is called if (memSpace == 0) { fprintf(stderr, "Unable to allocate memory\n"); return 0; } memSpace->writeAble(memSpace->bottom)[0] = PolyWord::FromUnsigned(0); used = 1; } PolyObject *newObj = (PolyObject*)(memSpace->bottom + used + 1); if (rounded != objWords) memSpace->writeAble(newObj)->Set(objWords, PolyWord::FromUnsigned(0)); used += rounded + 1; ASSERT(((uintptr_t)newObj & 0x7) == 0); return newObj; } #endif class PImport { public: PImport(); ~PImport(); bool DoImport(void); FILE *f; PolyObject *Root(void) { return objMap[nRoot]; } private: bool ReadValue(PolyObject *p, POLYUNSIGNED i); bool GetValue(PolyWord *result); POLYUNSIGNED nObjects, nRoot; PolyObject **objMap; unsigned spaceIndex; SpaceAlloc mutSpace, immutSpace, codeSpace; }; PImport::PImport(): mutSpace(&spaceIndex, MTF_WRITEABLE, 1024*1024), immutSpace(&spaceIndex, 0, 1024*1024), codeSpace(&spaceIndex, MTF_EXECUTABLE, 1024 * 1024) { f = NULL; objMap = 0; spaceIndex = 1; } PImport::~PImport() { if (f) fclose(f); free(objMap); } bool PImport::GetValue(PolyWord *result) { int ch = getc(f); if (ch == '@') { /* Address of an object. */ POLYUNSIGNED obj; fscanf(f, "%" POLYUFMT, &obj); ASSERT(obj < nObjects); *result = objMap[obj]; } else if ((ch >= '0' && ch <= '9') || ch == '-') { /* Tagged integer. */ POLYSIGNED j; ungetc(ch, f); fscanf(f, "%" POLYSFMT, &j); /* The assertion may be false if we are porting to a machine with a shorter tagged representation. */ ASSERT(j >= -MAXTAGGED-1 && j <= MAXTAGGED); *result = TAGGED(j); } else { fprintf(polyStderr, "Unexpected character in stream"); return false; } return true; } /* Read a value and store it at the specified word. */ bool PImport::ReadValue(PolyObject *p, POLYUNSIGNED i) { PolyWord result = TAGGED(0); if (GetValue(&result)) { p->Set(i, result); return true; } else return false; } bool PImport::DoImport() { int ch; POLYUNSIGNED objNo; ASSERT(gMem.pSpaces.size() == 0); ASSERT(gMem.eSpaces.size() == 0); ch = getc(f); ASSERT(ch == 'O'); /* Number of objects. */ while (getc(f) != '\t') ; fscanf(f, "%" POLYUFMT, &nObjects); /* Create a mapping table. */ objMap = (PolyObject**)calloc(nObjects, sizeof(PolyObject*)); if (objMap == 0) { fprintf(polyStderr, "Unable to allocate memory\n"); return false; } do { ch = getc(f); } while (ch == '\n'); ASSERT(ch == 'R'); /* Root object number. */ while (getc(f) != '\t') ; fscanf(f, "%" POLYUFMT, &nRoot); /* Now the objects themselves. */ while (1) { unsigned objBits = 0; POLYUNSIGNED nWords, nBytes; do { ch = getc(f); } while (ch == '\r' || ch == '\n'); if (ch == EOF) break; ungetc(ch, f); fscanf(f, "%" POLYUFMT, &objNo); ch = getc(f); ASSERT(ch == ':'); ASSERT(objNo < nObjects); /* Modifiers, MNVW. */ do { ch = getc(f); if (ch == 'M') objBits |= F_MUTABLE_BIT; else if (ch == 'N') objBits |= F_NEGATIVE_BIT; if (ch == 'V') objBits |= F_NO_OVERWRITE; if (ch == 'W') objBits |= F_WEAK_BIT; } while (ch == 'M' || ch == 'N' || ch == 'V' || ch == 'W'); /* Object type. */ switch (ch) { case 'O': /* Simple object. */ fscanf(f, "%" POLYUFMT, &nWords); break; case 'B': /* Byte segment. */ objBits |= F_BYTE_OBJ; fscanf(f, "%" POLYUFMT, &nBytes); /* Round up to appropriate number of words. */ nWords = (nBytes + sizeof(PolyWord) -1) / sizeof(PolyWord); break; case 'S': /* String. */ objBits |= F_BYTE_OBJ; /* The length is the number of characters. */ fscanf(f, "%" POLYUFMT, &nBytes); /* Round up to appropriate number of words. Need to add one PolyWord for the length PolyWord. */ nWords = (nBytes + sizeof(PolyWord) -1) / sizeof(PolyWord) + 1; break; case 'C': /* Code segment (old form). */ case 'D': /* Code segment (new form). */ objBits |= F_CODE_OBJ; /* Read the number of bytes of code and the number of words for constants. */ fscanf(f, "%" POLYUFMT ",%" POLYUFMT, &nWords, &nBytes); nWords += ch == 'C' ? 4 : 1; /* Add words for extras. */ /* Add in the size of the code itself. */ nWords += (nBytes + sizeof(PolyWord) -1) / sizeof(PolyWord); break; case 'L': // Closure objBits |= F_CLOSURE_OBJ; fscanf(f, "%" POLYUFMT, &nWords); break; case 'K': // Single weak reference nWords = sizeof(uintptr_t)/sizeof(PolyWord); objBits |= F_BYTE_OBJ; break; case 'E': // Entry point - address followed by string objBits |= F_BYTE_OBJ; // The length is the length of the string but it must be null-terminated fscanf(f, "%" POLYUFMT, &nBytes); // Add one uintptr_t plus one plus padding to an integral number of words. nWords = (nBytes + sizeof(uintptr_t) + sizeof(PolyWord)) / sizeof(PolyWord); break; default: fprintf(polyStderr, "Invalid object type\n"); return false; } SpaceAlloc* alloc; if (objBits & F_MUTABLE_BIT) alloc = &mutSpace; else if ((objBits & 3) == F_CODE_OBJ) alloc = &codeSpace; else alloc = &immutSpace; PolyObject* p = alloc->NewObj(nWords); if (p == 0) return false; objMap[objNo] = p; /* Put in length PolyWord and flag bits. */ alloc->memSpace->writeAble(p)->SetLengthWord(nWords, objBits); /* Skip the object contents. */ while (getc(f) != '\n') ; } /* Second pass - fill in the contents. */ fseek(f, 0, SEEK_SET); /* Skip the information at the start. */ ch = getc(f); ASSERT(ch == 'O'); /* Number of objects. */ while (getc(f) != '\n'); ch = getc(f); ASSERT(ch == 'R'); /* Root object number. */ while (getc(f) != '\n') ; while (1) { if (feof(f)) break; fscanf(f, "%" POLYUFMT, &objNo); if (feof(f)) break; ch = getc(f); ASSERT(ch == ':'); ASSERT(objNo < nObjects); PolyObject * p = objMap[objNo]; /* Modifiers, M or N. */ do { ch = getc(f); } while (ch == 'M' || ch == 'N' || ch == 'V' || ch == 'W'); /* Object type. */ switch (ch) { case 'O': /* Simple object. */ case 'L': // Closure { POLYUNSIGNED nWords; bool isClosure = ch == 'L'; fscanf(f, "%" POLYUFMT, &nWords); ch = getc(f); ASSERT(ch == '|'); ASSERT(nWords == p->Length()); POLYUNSIGNED i = 0; if (isClosure) { int ch = getc(f); // This should be an address if (ch != '@') return false; POLYUNSIGNED obj; fscanf(f, "%" POLYUFMT, &obj); ASSERT(obj < nObjects); *(PolyObject**)p = objMap[obj]; ch = getc(f); i = sizeof(PolyObject*) / sizeof(PolyWord); } while (i < nWords) { if (!ReadValue(p, i)) return false; ch = getc(f); ASSERT((ch == ',' && i < nWords - 1) || (ch == '\n' && i == nWords - 1)); i++; } break; } case 'B': /* Byte segment. */ { byte *u = (byte*)p; POLYUNSIGNED nBytes; fscanf(f, "%" POLYUFMT, &nBytes); ch = getc(f); ASSERT(ch == '|'); for (POLYUNSIGNED i = 0; i < nBytes; i++) { int n; fscanf(f, "%02x", &n); u[i] = n; } ch = getc(f); ASSERT(ch == '\n'); // Legacy: If this is an entry point object set its value. if (p->IsMutable() && p->IsWeakRefObject() && p->Length() > sizeof(uintptr_t)/sizeof(PolyWord)) { bool loadEntryPt = setEntryPoint(p); ASSERT(loadEntryPt); } break; } case 'S': /* String. */ { PolyStringObject * ps = (PolyStringObject *)p; /* The length is the number of characters. */ POLYUNSIGNED nBytes; fscanf(f, "%" POLYUFMT, &nBytes); ch = getc(f); ASSERT(ch == '|'); ps->length = nBytes; for (POLYUNSIGNED i = 0; i < nBytes; i++) { int n; fscanf(f, "%02x", &n); ps->chars[i] = n; } ch = getc(f); ASSERT(ch == '\n'); break; } case 'C': /* Code segment. */ case 'D': { bool oldForm = ch == 'C'; POLYUNSIGNED length = p->Length(); POLYUNSIGNED nWords, nBytes; - MemSpace* space = gMem.SpaceForAddress(p); + MemSpace* space = gMem.SpaceForObjectAddress(p); PolyObject *wr = space->writeAble(p); byte* u = (byte*)wr; /* Read the number of bytes of code and the number of words for constants. */ fscanf(f, "%" POLYUFMT ",%" POLYUFMT, &nWords, &nBytes); /* Read the code. */ ch = getc(f); ASSERT(ch == '|'); for (POLYUNSIGNED i = 0; i < nBytes; i++) { int n; fscanf(f, "%02x", &n); u[i] = n; } ch = getc(f); ASSERT(ch == '|'); /* Set the constant count. */ wr->Set(length-1, PolyWord::FromUnsigned(nWords)); if (oldForm) { wr->Set(length-1-nWords-1, PolyWord::FromUnsigned(0)); /* Profile count. */ wr->Set(length-1-nWords-3, PolyWord::FromUnsigned(0)); /* Marker word. */ wr->Set(length-1-nWords-2, PolyWord::FromUnsigned((length-1-nWords-2)*sizeof(PolyWord))); /* Check - the code should end at the marker word. */ ASSERT(nBytes == ((length-1-nWords-3)*sizeof(PolyWord))); } /* Read in the constants. */ for (POLYUNSIGNED i = 0; i < nWords; i++) { if (! ReadValue(wr, i+length-nWords-1)) return false; ch = getc(f); ASSERT((ch == ',' && i < nWords-1) || ((ch == '\n' || ch == '|') && i == nWords-1)); } // Read in any constants in the code. if (ch == '|') { ch = getc(f); while (ch != '\n') { ungetc(ch, f); POLYUNSIGNED offset; int code; fscanf(f, "%" POLYUFMT ",%d", &offset, &code); ch = getc(f); ASSERT(ch == ','); // This should be an address. ch = getc(f); if (ch == '@') { POLYUNSIGNED obj; fscanf(f, "%" POLYUFMT, &obj); ASSERT(obj < nObjects); PolyObject *addr = objMap[obj]; byte *toPatch = (byte*)p + offset; // Pass the execute address here. ScanAddress::SetConstantValue(toPatch, addr, (ScanRelocationKind)code); } else { // Previously we also included tagged constants but they are // already in the code. ungetc(ch, f); PolyWord w; if (!GetValue(&w)) return false; } do ch = getc(f); while (ch == ' '); } } // Clear the mutable bit wr->SetLengthWord(p->Length(), F_CODE_OBJ); break; } case 'K': // Weak reference - must be zeroed *(uintptr_t*)p = 0; break; case 'E': // Entry point - address followed by string { // The length is the number of characters. *(uintptr_t*)p = 0; char* b = (char*)p + sizeof(uintptr_t); POLYUNSIGNED nBytes; fscanf(f, "%" POLYUFMT, &nBytes); ch = getc(f); ASSERT(ch == '|'); for (POLYUNSIGNED i = 0; i < nBytes; i++) { ch = getc(f); *b++ = ch; } *b = 0; ch = getc(f); ASSERT(ch == '\n'); bool loadEntryPt = setEntryPoint(p); ASSERT(loadEntryPt); break; } default: fprintf(polyStderr, "Invalid object type\n"); return false; } } // Now remove write access from immutable spaces. for (std::vector::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) gMem.CompletePermanentSpaceAllocation(*i); return true; } // Import a file in the portable format and return a pointer to the root object. PolyObject *ImportPortable(const TCHAR *fileName) { PImport pImport; #if (defined(_WIN32) && defined(UNICODE)) pImport.f = _wfopen(fileName, L"r"); if (pImport.f == 0) { fprintf(polyStderr, "Unable to open file: %S\n", fileName); return 0; } #else pImport.f = fopen(fileName, "r"); if (pImport.f == 0) { fprintf(polyStderr, "Unable to open file: %s\n", fileName); return 0; } #endif if (pImport.DoImport()) return pImport.Root(); else return 0; } diff --git a/libpolyml/poly_specific.cpp b/libpolyml/poly_specific.cpp index 4a68fd22..0e43de16 100644 --- a/libpolyml/poly_specific.cpp +++ b/libpolyml/poly_specific.cpp @@ -1,463 +1,463 @@ /* Title: poly_specific.cpp - Poly/ML specific RTS calls. Copyright (c) 2006, 2015-17, 2019 David C. J. Matthews This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ /* This module is used for various run-time calls that are either in the PolyML structure or otherwise specific to Poly/ML. */ #ifdef HAVE_CONFIG_H #include "config.h" #elif defined(_WIN32) #include "winconfig.h" #else #error "No configuration file" #endif #ifdef HAVE_ASSERT_H #include #define ASSERT(x) assert(x) #else #define ASSERT(x) 0 #endif #ifdef HAVE_STRING_H #include #endif #include "globals.h" #include "poly_specific.h" #include "arb.h" #include "mpoly.h" #include "sys.h" #include "machine_dep.h" #include "polystring.h" #include "run_time.h" #include "version.h" #include "save_vec.h" #include "version.h" #include "memmgr.h" #include "processes.h" #include "gc.h" #include "rtsentry.h" extern "C" { POLYEXTERNALSYMBOL POLYUNSIGNED PolySpecificGeneral(FirstArgument threadId, PolyWord code, PolyWord arg); POLYEXTERNALSYMBOL POLYUNSIGNED PolyGetABI(); POLYEXTERNALSYMBOL POLYUNSIGNED PolyLockMutableCode(FirstArgument threadId, PolyWord byteSeg); POLYEXTERNALSYMBOL POLYUNSIGNED PolyLockMutableClosure(FirstArgument threadId, PolyWord closure); POLYEXTERNALSYMBOL POLYUNSIGNED PolyCopyByteVecToCode(FirstArgument threadId, PolyWord byteVec); POLYEXTERNALSYMBOL POLYUNSIGNED PolyCopyByteVecToClosure(FirstArgument threadId, PolyWord byteVec, PolyWord closure); POLYEXTERNALSYMBOL POLYUNSIGNED PolySetCodeConstant(PolyWord closure, PolyWord offset, PolyWord c, PolyWord flags); POLYEXTERNALSYMBOL POLYUNSIGNED PolySetCodeByte(PolyWord closure, PolyWord offset, PolyWord c); POLYEXTERNALSYMBOL POLYUNSIGNED PolyGetCodeByte(PolyWord closure, PolyWord offset); POLYEXTERNALSYMBOL POLYUNSIGNED PolySortArrayOfAddresses(PolyWord array); POLYEXTERNALSYMBOL POLYUNSIGNED PolyTest4(FirstArgument threadId, PolyWord arg1, PolyWord arg2, PolyWord arg3, PolyWord arg4); POLYEXTERNALSYMBOL POLYUNSIGNED PolyTest5(FirstArgument threadId, PolyWord arg1, PolyWord arg2, PolyWord arg3, PolyWord arg4, PolyWord arg5); } #define SAVE(x) taskData->saveVec.push(x) #ifndef GIT_VERSION #define GIT_VERSION "" #endif Handle poly_dispatch_c(TaskData *taskData, Handle args, Handle code) { unsigned c = get_C_unsigned(taskData, DEREFWORD(code)); switch (c) { case 9: // Return the GIT version if appropriate { return SAVE(C_string_to_Poly(taskData, GIT_VERSION)); } case 10: // Return the RTS version string. { const char *version; switch (machineDependent->MachineArchitecture()) { case MA_Interpreted: version = "Portable-" TextVersion; break; case MA_I386: version = "I386-" TextVersion; break; case MA_X86_64: version = "X86_64-" TextVersion; break; default: version = "Unknown-" TextVersion; break; } return SAVE(C_string_to_Poly(taskData, version)); } case 12: // Return the architecture // Used in InitialPolyML.ML for PolyML.architecture { const char *arch; switch (machineDependent->MachineArchitecture()) { case MA_Interpreted: arch = "Interpreted"; break; case MA_I386: arch = "I386"; break; case MA_X86_64: arch = "X86_64"; break; case MA_X86_64_32: arch = "X86_64_32"; break; default: arch = "Unknown"; break; } return SAVE(C_string_to_Poly(taskData, arch)); } case 19: // Return the RTS argument help string. return SAVE(C_string_to_Poly(taskData, RTSArgHelp())); default: { char msg[100]; sprintf(msg, "Unknown poly-specific function: %d", c); raise_exception_string(taskData, EXC_Fail, msg); return 0; } } } // General interface to poly-specific. Ideally the various cases will be made into // separate functions. POLYUNSIGNED PolySpecificGeneral(FirstArgument threadId, PolyWord code, PolyWord arg) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); Handle pushedCode = taskData->saveVec.push(code); Handle pushedArg = taskData->saveVec.push(arg); Handle result = 0; try { result = poly_dispatch_c(taskData, pushedArg, pushedCode); } catch (...) { } // If an ML exception is raised taskData->saveVec.reset(reset); taskData->PostRTSCall(); if (result == 0) return TAGGED(0).AsUnsigned(); else return result->Word().AsUnsigned(); } // Return the ABI - i.e. the calling conventions used when calling external functions. POLYEXTERNALSYMBOL POLYUNSIGNED PolyGetABI() { // Return the ABI. For 64-bit we need to know if this is Windows. #if (SIZEOF_VOIDP == 8) #if (defined(_WIN32) || defined(__CYGWIN__)) return TAGGED(2).AsUnsigned(); // 64-bit Windows #else return TAGGED(1).AsUnsigned(); // 64-bit Unix #endif #else return TAGGED(0).AsUnsigned(); // 32-bit Unix and Windows #endif } // Code generation - Code is initially allocated in a byte segment. When all the // values have been set apart from any addresses the byte segment is copied into // a mutable code segment. // PolyCopyByteVecToCode is now replaced by PolyCopyByteVecToClosure POLYEXTERNALSYMBOL POLYUNSIGNED PolyCopyByteVecToCode(FirstArgument threadId, PolyWord byteVec) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); Handle pushedArg = taskData->saveVec.push(byteVec); PolyObject *result = 0; try { if (!pushedArg->WordP()->IsByteObject()) raise_fail(taskData, "Not byte data area"); do { PolyObject *initCell = pushedArg->WordP(); POLYUNSIGNED requiredSize = initCell->Length(); result = gMem.AllocCodeSpace(requiredSize); if (result == 0) { // Could not allocate - must GC. if (!QuickGC(taskData, pushedArg->WordP()->Length())) raise_fail(taskData, "Insufficient memory"); } else memcpy(result, initCell, requiredSize * sizeof(PolyWord)); } while (result == 0); } catch (...) {} // If an ML exception is raised taskData->saveVec.reset(reset); taskData->PostRTSCall(); return ((PolyWord)result).AsUnsigned(); } // Copy the byte vector into code space. POLYUNSIGNED PolyCopyByteVecToClosure(FirstArgument threadId, PolyWord byteVec, PolyWord closure) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); Handle pushedByteVec = taskData->saveVec.push(byteVec); Handle pushedClosure = taskData->saveVec.push(closure); PolyObject *result = 0; try { if (!pushedByteVec->WordP()->IsByteObject()) raise_fail(taskData, "Not byte data area"); if (pushedClosure->WordP()->Length() != sizeof(PolyObject*)/sizeof(PolyWord)) raise_fail(taskData, "Invalid closure size"); if (!pushedClosure->WordP()->IsMutable()) raise_fail(taskData, "Closure is not mutable"); do { PolyObject *initCell = pushedByteVec->WordP(); POLYUNSIGNED requiredSize = initCell->Length(); result = gMem.AllocCodeSpace(requiredSize); if (result == 0) { // Could not allocate - must GC. if (!QuickGC(taskData, pushedByteVec->WordP()->Length())) raise_fail(taskData, "Insufficient memory"); } - else memcpy(gMem.SpaceForAddress(result)->writeAble((byte*)result), initCell, requiredSize * sizeof(PolyWord)); + else memcpy(gMem.SpaceForObjectAddress(result)->writeAble((byte*)result), initCell, requiredSize * sizeof(PolyWord)); } while (result == 0); } catch (...) {} // If an ML exception is raised // Store the code address in the closure. *((PolyObject**)pushedClosure->WordP()) = result; // Lock the closure. pushedClosure->WordP()->SetLengthWord(pushedClosure->WordP()->LengthWord() & ~_OBJ_MUTABLE_BIT); taskData->saveVec.reset(reset); taskData->PostRTSCall(); return TAGGED(0).AsUnsigned(); } // Code generation - Lock a mutable code segment and return the original address. // Currently this does not allocate so other than the exception it could // be a fast call. POLYEXTERNALSYMBOL POLYUNSIGNED PolyLockMutableCode(FirstArgument threadId, PolyWord byteSeg) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); Handle pushedArg = taskData->saveVec.push(byteSeg); Handle result = 0; try { PolyObject *codeObj = pushedArg->WordP(); if (!codeObj->IsCodeObject() || !codeObj->IsMutable()) raise_fail(taskData, "Not mutable code area"); POLYUNSIGNED segLength = codeObj->Length(); codeObj->SetLengthWord(segLength, F_CODE_OBJ); // This is really a legacy of the PPC code-generator. machineDependent->FlushInstructionCache(codeObj, segLength * sizeof(PolyWord)); // In the future it may be necessary to return a different address here. // N.B. The code area should only have execute permission in the native // code version, not the interpreted version. result = pushedArg; // Return the original address. } catch (...) {} // If an ML exception is raised taskData->saveVec.reset(reset); taskData->PostRTSCall(); if (result == 0) return TAGGED(0).AsUnsigned(); else return result->Word().AsUnsigned(); } // Replacement for above POLYEXTERNALSYMBOL POLYUNSIGNED PolyLockMutableClosure(FirstArgument threadId, PolyWord closure) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); PolyObject *codeObj = *(PolyObject**)(closure.AsObjPtr()); try { if (!codeObj->IsCodeObject() || !codeObj->IsMutable()) raise_fail(taskData, "Not mutable code area"); POLYUNSIGNED segLength = codeObj->Length(); - gMem.SpaceForAddress(codeObj)->writeAble(codeObj)->SetLengthWord(segLength, F_CODE_OBJ); + gMem.SpaceForObjectAddress(codeObj)->writeAble(codeObj)->SetLengthWord(segLength, F_CODE_OBJ); // In the future it may be necessary to return a different address here. // N.B. The code area should only have execute permission in the native // code version, not the interpreted version. } catch (...) {} // If an ML exception is raised taskData->saveVec.reset(reset); taskData->PostRTSCall(); return TAGGED(0).AsUnsigned(); } // Set code constant. This can be a fast call. // This is in the RTS both because we pass a closure in here and cannot have // code addresses in 32-in-64 and also because we need to ensure there is no // possibility of a GC while the code is an inconsistent state. POLYUNSIGNED PolySetCodeConstant(PolyWord closure, PolyWord offset, PolyWord cWord, PolyWord flags) { byte *pointer; // Previously we passed the code address in here and we need to // retain that for legacy code. This is now the closure. if (closure.AsObjPtr()->IsCodeObject()) pointer = closure.AsCodePtr(); else pointer = *(POLYCODEPTR*)(closure.AsObjPtr()); // pointer is the start of the code segment. // c will usually be an address. // offset is a byte offset pointer += offset.UnTaggedUnsigned(); byte* writeable = gMem.SpaceForAddress(pointer)->writeAble(pointer); switch (UNTAGGED(flags)) { case 0: // Absolute constant - size PolyWord { POLYUNSIGNED c = cWord.AsUnsigned(); #ifdef WORDS_BIGENDIAN // This is used to store constants in the constant area // on the interpreted version. for (unsigned i = sizeof(PolyWord); i > 0; i--) { writeable[i-1] = (byte)(c & 255); c >>= 8; } #else for (unsigned i = 0; i < sizeof(PolyWord); i++) { writeable[i] = (byte)(c & 255); c >>= 8; } #endif break; } case 1: // Relative constant - X86 - size 4 bytes { // The offset is relative to the END of the constant. byte *target; // In 32-in-64 we pass in the closure address here // rather than the code address. if (cWord.AsObjPtr()->IsCodeObject()) target = cWord.AsCodePtr(); else target = *(POLYCODEPTR*)(cWord.AsObjPtr()); size_t c = target - pointer - 4; for (unsigned i = 0; i < sizeof(PolyWord); i++) { writeable[i] = (byte)(c & 255); c >>= 8; } break; } case 2: // Absolute constant - size uintptr_t // This is the same as case 0 except in 32-in-64 when // it is an absolute address rather than an object pointer. { uintptr_t c = (uintptr_t)(cWord.AsObjPtr()); for (unsigned i = 0; i < sizeof(uintptr_t); i++) { pointer[i] = (byte)(c & 255); c >>= 8; } break; } } return TAGGED(0).AsUnsigned(); } // Set a code byte. This needs to be in the RTS because it uses the closure POLYEXTERNALSYMBOL POLYUNSIGNED PolySetCodeByte(PolyWord closure, PolyWord offset, PolyWord cWord) { byte *pointer = *(POLYCODEPTR*)(closure.AsObjPtr()); byte* writable = gMem.SpaceForAddress(pointer)->writeAble(pointer); writable[UNTAGGED_UNSIGNED(offset)] = (byte)UNTAGGED_UNSIGNED(cWord); return TAGGED(0).AsUnsigned(); } POLYEXTERNALSYMBOL POLYUNSIGNED PolyGetCodeByte(PolyWord closure, PolyWord offset) { byte *pointer = *(POLYCODEPTR*)(closure.AsObjPtr()); return TAGGED(pointer[UNTAGGED_UNSIGNED(offset)]).AsUnsigned(); } static int compare(const void *a, const void *b) { PolyWord *av = (PolyWord*)a; PolyWord *bv = (PolyWord*)b; if ((*av).IsTagged() || (*bv).IsTagged()) return 0; // Shouldn't happen PolyObject *ao = (*av).AsObjPtr(), *bo = (*bv).AsObjPtr(); if (ao->Length() < 1 || bo->Length() < 1) return 0; // Shouldn't happen if (ao->Get(0).AsUnsigned() < bo->Get(0).AsUnsigned()) return -1; if (ao->Get(0).AsUnsigned() > bo->Get(0).AsUnsigned()) return 1; return 0; } // Sort an array of addresses. This is used in the code-generator to search for // duplicates in the address area. The argument is an array of pairs. The first // item of each pair is an address, the second is an identifier of some kind. POLYEXTERNALSYMBOL POLYUNSIGNED PolySortArrayOfAddresses(PolyWord array) { if (!array.IsDataPtr()) return(TAGGED(0)).AsUnsigned(); PolyObject *arrayP = array.AsObjPtr(); POLYUNSIGNED numberOfItems = arrayP->Length(); if (!arrayP->IsMutable()) return(TAGGED(0)).AsUnsigned(); qsort(arrayP, numberOfItems, sizeof(PolyWord), compare); return (TAGGED(1)).AsUnsigned(); } POLYEXTERNALSYMBOL POLYUNSIGNED PolyTest4(FirstArgument threadId, PolyWord arg1, PolyWord arg2, PolyWord arg3, PolyWord arg4) { switch (arg1.UnTaggedUnsigned()) { case 1: return arg1.AsUnsigned(); case 2: return arg2.AsUnsigned(); case 3: return arg3.AsUnsigned(); case 4: return arg4.AsUnsigned(); default: return TAGGED(0).AsUnsigned(); } } POLYEXTERNALSYMBOL POLYUNSIGNED PolyTest5(FirstArgument threadId, PolyWord arg1, PolyWord arg2, PolyWord arg3, PolyWord arg4, PolyWord arg5) { switch (arg1.UnTaggedUnsigned()) { case 1: return arg1.AsUnsigned(); case 2: return arg2.AsUnsigned(); case 3: return arg3.AsUnsigned(); case 4: return arg4.AsUnsigned(); case 5: return arg5.AsUnsigned(); default: return TAGGED(0).AsUnsigned(); } } struct _entrypts polySpecificEPT[] = { { "PolySpecificGeneral", (polyRTSFunction)&PolySpecificGeneral}, { "PolyGetABI", (polyRTSFunction)&PolyGetABI }, { "PolyCopyByteVecToCode", (polyRTSFunction)&PolyCopyByteVecToCode }, { "PolyCopyByteVecToClosure", (polyRTSFunction)&PolyCopyByteVecToClosure }, { "PolyLockMutableCode", (polyRTSFunction)&PolyLockMutableCode }, { "PolyLockMutableClosure", (polyRTSFunction)&PolyLockMutableClosure }, { "PolySetCodeConstant", (polyRTSFunction)&PolySetCodeConstant }, { "PolySetCodeByte", (polyRTSFunction)&PolySetCodeByte }, { "PolyGetCodeByte", (polyRTSFunction)&PolyGetCodeByte }, { "PolySortArrayOfAddresses", (polyRTSFunction)&PolySortArrayOfAddresses }, { "PolyTest4", (polyRTSFunction)&PolyTest4 }, { "PolyTest5", (polyRTSFunction)&PolyTest5 }, { NULL, NULL} // End of list. }; diff --git a/libpolyml/sharedata.cpp b/libpolyml/sharedata.cpp index fbea3d20..2a3b6f9c 100644 --- a/libpolyml/sharedata.cpp +++ b/libpolyml/sharedata.cpp @@ -1,1123 +1,1123 @@ /* Title: Share common immutable data Copyright (c) 2000 Cambridge University Technical Services Limited and David C. J. Matthews 2006, 2010-13, 2016-17, 2019 This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifdef HAVE_CONFIG_H #include "config.h" #elif defined(_WIN32) #include "winconfig.h" #else #error "No configuration file" #endif #ifdef HAVE_STDLIB_H #include #endif #ifdef HAVE_ASSERT_H #include #define ASSERT(x) assert(x) #else #define ASSERT(x) #endif #ifdef HAVE_STRING_H #include #endif #include #include "globals.h" #include "save_vec.h" #include "machine_dep.h" #include "scanaddrs.h" #include "run_time.h" #include "sys.h" #include "gc.h" #include "rtsentry.h" #include "memmgr.h" #include "processes.h" #include "gctaskfarm.h" #include "diagnostics.h" #include "sharedata.h" #include "gc_progress.h" /* This code was largely written by Simon Finn as a database improver for the memory-mapped persistent store version. The aim is that where two immutable objects (cells) contain the same data (i.e. where ML equality would say they were equal) they should be merged so that only a single object is retained. The basic algorithm works like this: 1. From the root, recursively process all objects and calculate a "depth" for each object. Mutable data and code segments have depth 0 and cannot be merged. Byte segments (e.g. strings and long-format arbitrary precision values) have depth 1. Other cells have depths of 1 or greater, the depth being the maximum recursion depth until a byte segment or an object with depth 0 is reached. Cycles of immutable data don't arise normally in ML but could be produced as a result of locking mutable objects. To avoid infinite recursion cycles are broken by setting the depth of an object to zero before processing it. The depth of each object is stored in the length word of the object. This ensures each object is processed once only. 2. Vectors are created containing objects of the same depth, from 1 to the maximum depth found. 3. We begin a loop starting at depth 1. 4. The length words are restored, replacing the depth count in the header. 5. The objects are sorted by their contents so bringing together objects with the same contents. The contents are considered simply as uninterpreted bits. 6. The sorted vector is processed to find those objects that are actually bitwise equal. One object is selected to be retained and other objects have their length words turned into tombstones pointing at the retained object. 7. Objects at the next depth are first processed to find pointers to objects that moved in the previous step (or that step with a lower depth). The addresses are updated to point to the retained object. The effect of this step is to ensure that now two objects that are equal in ML terms have identical contents. e.g. If we have val a = ("abc", "def") and b = ("abc", "def") then we will have merged the two occurrences of "abc" and "def" in the previous pass of level 1 objects. This step ensures that the two cells containing the pairs both hold pointers to the same objects and so are bitwise equal. 8. Repeat with 4, 5 and 6 until all the levels have been processed. Each object is processed once and at the end most of the objects have been updated with the shared addresses. We have to scan all the mutable and code objects to update the addresses but also have to scan the immutables because of the possibility of missing an update as a result of breaking a loop (see SPF's comment below). DCJM 3/8/06 This has been substantially updated while retaining the basic algorithm. Sorting is now done in parallel by the GC task farm and the stack is now in dynamic memory. That avoids a possible segfault if the normal C stack overflows. A further problem is that the vectors can get very large and this can cause problems if there is insufficient contiguous space. The code has been modified to reduce the size of the vectors at the cost of increasing the total memory requirement. */ extern "C" { POLYEXTERNALSYMBOL POLYUNSIGNED PolyShareCommonData(FirstArgument threadId, PolyWord root); } // The depth is stored in the length field. If the Weak bit is set but the Mutable bit // is clear the value in the length word is a depth rather than a real length. // The tombstone bit is zero. // Previously "depth" values were encoded with the tombstone bit set but that isn't // possible in 32-in-64 because we need 31 bits in a forwarding pointer. inline bool OBJ_IS_DEPTH(POLYUNSIGNED L) { return (L & (_OBJ_WEAK_BIT| _OBJ_MUTABLE_BIT)) == _OBJ_WEAK_BIT; } inline POLYUNSIGNED OBJ_GET_DEPTH(POLYUNSIGNED L) { return OBJ_OBJECT_LENGTH(L); } inline POLYUNSIGNED OBJ_SET_DEPTH(POLYUNSIGNED n) { return n | _OBJ_WEAK_BIT; } // The DepthVector type contains all the items of a particular depth. // This is the abstract class. There are variants for the case where all // the cells have the same size and where they may vary. class DepthVector { public: DepthVector() : nitems(0), vsize(0), ptrVector(0) {} virtual ~DepthVector() { free(ptrVector); } virtual POLYUNSIGNED MergeSameItems(void); virtual void Sort(void); virtual POLYUNSIGNED ItemCount(void) { return nitems; } virtual void AddToVector(POLYUNSIGNED L, PolyObject *pt) = 0; void FixLengthAndAddresses(ScanAddress *scan); virtual void RestoreForwardingPointers() = 0; protected: POLYUNSIGNED nitems; POLYUNSIGNED vsize; PolyObject **ptrVector; // This must only be called BEFORE sorting. The pointer vector will be // modified by sorting but the length vector is not. virtual void RestoreLengthWords(void) = 0; static void SortRange(PolyObject * *first, PolyObject * *last); static int CompareItems(const PolyObject * const *a, const PolyObject * const *b); static int qsCompare(const void *a, const void *b) { return CompareItems((const PolyObject * const*)a, (const PolyObject *const *)b); } static void sortTask(GCTaskId*, void *s, void *l) { SortRange((PolyObject **)s, (PolyObject **)l); } }; // DepthVector where the size needs to be held for each item. class DepthVectorWithVariableLength: public DepthVector { public: DepthVectorWithVariableLength() : lengthVector(0) {} virtual ~DepthVectorWithVariableLength() { free(lengthVector); } virtual void RestoreLengthWords(void); virtual void AddToVector(POLYUNSIGNED L, PolyObject *pt); virtual void RestoreForwardingPointers(); protected: POLYUNSIGNED *lengthVector; // Same size as the ptrVector }; class DepthVectorWithFixedLength : public DepthVector { public: DepthVectorWithFixedLength(POLYUNSIGNED l) : length(l) {} virtual void RestoreLengthWords(void); virtual void AddToVector(POLYUNSIGNED L, PolyObject *pt); // It's safe to run this again for the fixed length vectors. virtual void RestoreForwardingPointers() { RestoreLengthWords(); } protected: POLYUNSIGNED length; }; // We have special vectors for the sizes from 1 to FIXEDLENGTHSIZE-1. // Zero-sized and large objects go in depthVectorArray[0]. #define FIXEDLENGTHSIZE 10 class ShareDataClass { public: ShareDataClass(); ~ShareDataClass(); bool RunShareData(PolyObject *root); void AddToVector(POLYUNSIGNED depth, POLYUNSIGNED length, PolyObject *pt); private: std::vector depthVectorArray[FIXEDLENGTHSIZE]; POLYUNSIGNED maxVectorSize; }; ShareDataClass::ShareDataClass() { maxVectorSize = 0; } ShareDataClass::~ShareDataClass() { // Free the bitmaps associated with the permanent spaces. for (std::vector::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) (*i)->shareBitmap.Destroy(); // Free the depth vectors. for (unsigned i = 0; i < FIXEDLENGTHSIZE; i++) { for (std::vector ::iterator j = depthVectorArray[i].begin(); j < depthVectorArray[i].end(); j++) delete(*j); } } // Grow the appropriate depth vector if necessary and add the item to it. void ShareDataClass::AddToVector(POLYUNSIGNED depth, POLYUNSIGNED length, PolyObject *pt) { // Select the appropriate vector. Element zero is the variable length vector and is // also used for the, rare, zero length objects. std::vector *vectorToUse = &(depthVectorArray[length < FIXEDLENGTHSIZE ? length : 0]); if (depth >= maxVectorSize) maxVectorSize = depth+1; while (vectorToUse->size() <= depth) { try { if (length != 0 && length < FIXEDLENGTHSIZE) vectorToUse->push_back(new DepthVectorWithFixedLength(length)); else vectorToUse->push_back(new DepthVectorWithVariableLength); } catch (std::bad_alloc&) { throw MemoryException(); } } (*vectorToUse)[depth]->AddToVector(length, pt); } // Add an object to a depth vector void DepthVectorWithVariableLength::AddToVector(POLYUNSIGNED L, PolyObject *pt) { ASSERT (this->nitems <= this->vsize); if (this->nitems == this->vsize) { // The vector is full or has not yet been allocated. Grow it by 50%. POLYUNSIGNED new_vsize = this->vsize + this->vsize / 2 + 1; if (new_vsize < 15) new_vsize = 15; // First the length vector. POLYUNSIGNED *newLength = (POLYUNSIGNED *)realloc(this->lengthVector, new_vsize * sizeof(POLYUNSIGNED)); if (newLength == 0) { // The vectors can get large and we may not be able to grow them // particularly if the address space is limited in 32-bit mode. // Try again with just a small increase. new_vsize = this->vsize + 15; newLength = (POLYUNSIGNED *)realloc(this->lengthVector, new_vsize * sizeof(POLYUNSIGNED)); // If that failed give up. if (newLength == 0) throw MemoryException(); } PolyObject **newPtrVector = (PolyObject * *)realloc (this->ptrVector, new_vsize*sizeof(PolyObject *)); if (newPtrVector == 0) { new_vsize = this->vsize + 15; newPtrVector = (PolyObject **)realloc (this->ptrVector, new_vsize*sizeof(PolyObject *)); // If that failed give up. if (newPtrVector == 0) throw MemoryException(); } this->lengthVector = newLength; this->ptrVector = newPtrVector; this->vsize = new_vsize; } ASSERT (this->nitems < this->vsize); this->lengthVector[this->nitems] = L; this->ptrVector[this->nitems] = pt; this->nitems++; ASSERT (this->nitems <= this->vsize); } // Add an object to a depth vector void DepthVectorWithFixedLength::AddToVector(POLYUNSIGNED L, PolyObject *pt) { ASSERT(this->nitems <= this->vsize); ASSERT(L == length); if (this->nitems == this->vsize) { // The vector is full or has not yet been allocated. Grow it by 50%. POLYUNSIGNED new_vsize = this->vsize + this->vsize / 2 + 1; if (new_vsize < 15) new_vsize = 15; PolyObject **newPtrVector = (PolyObject * *)realloc(this->ptrVector, new_vsize * sizeof(PolyObject *)); if (newPtrVector == 0) { new_vsize = this->vsize + 15; newPtrVector = (PolyObject **)realloc(this->ptrVector, new_vsize * sizeof(PolyObject *)); // If that failed give up. if (newPtrVector == 0) throw MemoryException(); } this->ptrVector = newPtrVector; this->vsize = new_vsize; } ASSERT(this->nitems < this->vsize); this->ptrVector[this->nitems] = pt; this->nitems++; ASSERT(this->nitems <= this->vsize); } // Comparison function used for sorting and also to test whether // two cells can be merged. int DepthVector::CompareItems(const PolyObject *const *a, const PolyObject *const *b) { const PolyObject *x = *a; const PolyObject *y = *b; POLYUNSIGNED lX = x->LengthWord(); POLYUNSIGNED lY = y->LengthWord(); // ASSERT (OBJ_IS_LENGTH(lX)); // ASSERT (OBJ_IS_LENGTH(lY)); if (lX > lY) return 1; // These tests include the flag bits if (lX < lY) return -1; // Return simple bitwise equality. return memcmp(x, y, OBJ_OBJECT_LENGTH(lX)*sizeof(PolyWord)); } // Merge cells with the same contents. POLYUNSIGNED DepthVector::MergeSameItems() { POLYUNSIGNED N = this->nitems; POLYUNSIGNED n = 0; POLYUNSIGNED i = 0; while (i < N) { PolyObject *bestShare = 0; // Candidate to share. MemSpace *bestSpace = 0; POLYUNSIGNED j; for (j = i; j < N; j++) { ASSERT (OBJ_IS_LENGTH(ptrVector[i]->LengthWord())); // Search for identical objects. Don't bother to compare it with itself. if (i != j && CompareItems (&ptrVector[i], &ptrVector[j]) != 0) break; // The order of sharing is significant. // Choose an object in the permanent memory if that is available. // This is necessary to retain the invariant that no object in // the permanent memory points to an object in the temporary heap. // (There may well be pointers to this object elsewhere in the permanent // heap). // Choose the lowest hierarchy value for preference since that // may reduce the size of saved state when resaving already saved // data. // If we can't find a permanent space choose a space that isn't // an allocation space. Otherwise we could break the invariant // that immutable areas never point into the allocation area. MemSpace *space = gMem.SpaceForAddress((PolyWord*)ptrVector[j]-1); if (bestSpace == 0) { bestShare = ptrVector[j]; bestSpace = space; } else if (bestSpace->spaceType == ST_PERMANENT) { // Only update if the current space is also permanent and a lower hierarchy if (space->spaceType == ST_PERMANENT && ((PermanentMemSpace *)space)->hierarchy < ((PermanentMemSpace *)bestSpace)->hierarchy) { bestShare = ptrVector[j]; bestSpace = space; } } else if (bestSpace->spaceType == ST_LOCAL) { // Update if the current space is not an allocation space if (space->spaceType != ST_LOCAL || ! ((LocalMemSpace*)space)->allocationSpace) { bestShare = ptrVector[j]; bestSpace = space; } } } POLYUNSIGNED k = j; // Remember the first object that didn't match. // For each identical object set all but the one we want to point to // the shared object. for (j = i; j < k; j++) { ASSERT (OBJ_IS_LENGTH(ptrVector[j]->LengthWord())); if (ptrVector[j] != bestShare) { ptrVector[j]->SetForwardingPtr(bestShare); /* an indirection */ n++; } } i = k; } return n; } // Sort this vector void DepthVector::Sort() { if (nitems > 1) { SortRange(ptrVector, ptrVector + (nitems - 1)); gpTaskFarm->WaitForCompletion(); } // Check // for (POLYUNSIGNED i = 0; i < nitems-1; i++) // ASSERT(CompareItems(vector+i, vector+i+1) <= 0); } inline void swapItems(PolyObject * *i, PolyObject * *j) { PolyObject * t = *i; *i = *j; *j = t; } // Simple parallel quick-sort. "first" and "last" are the first // and last items (inclusive) in the vector. void DepthVector::SortRange(PolyObject * *first, PolyObject * *last) { while (first < last) { if (last-first <= 100) { // Use the standard library function for small ranges. qsort(first, last-first+1, sizeof(PolyObject *), qsCompare); return; } // Select the best pivot from the first, last and middle item // by sorting these three items. We use the middle item as // the pivot and since the first and last items are sorted // by this we can skip them when we start the partitioning. PolyObject * *middle = first + (last-first)/2; if (CompareItems(first, middle) > 0) swapItems(first, middle); if (CompareItems(middle, last) > 0) { swapItems(middle, last); if (CompareItems(first, middle) > 0) swapItems(first, middle); } // Partition the data about the pivot. This divides the // vector into two partitions with all items <= pivot to // the left and all items >= pivot to the right. // Note: items equal to the pivot could be in either partition. PolyObject * *f = first+1; PolyObject * *l = last-1; do { // Find an item we have to move. These loops will always // terminate because testing the middle with itself // will return == 0. while (CompareItems(f, middle/* pivot*/) < 0) f++; while (CompareItems(middle/* pivot*/, l) < 0) l--; // If we haven't finished we need to swap the items. if (f < l) { swapItems(f, l); // If one of these was the pivot item it will have moved to // the other position. if (middle == f) middle = l; else if (middle == l) middle = f; f++; l--; } else if (f == l) { f++; l--; break; } } while (f <= l); // Process the larger partition as a separate task or // by recursion and do the smaller partition by tail // recursion. if (l-first > last-f) { // Lower part is larger gpTaskFarm->AddWorkOrRunNow(sortTask, first, l); first = f; } else { // Upper part is larger gpTaskFarm->AddWorkOrRunNow(sortTask, f, last); last = l; } } } // Set the genuine length word. This overwrites both depth words and forwarding pointers. void DepthVectorWithVariableLength::RestoreLengthWords() { for (POLYUNSIGNED i = 0; i < this->nitems; i++) { PolyObject* obj = ptrVector[i]; - obj = gMem.SpaceForAddress(obj)->writeAble(obj); // This could be code. + obj = gMem.SpaceForObjectAddress(obj)->writeAble(obj); // This could be code. obj->SetLengthWord(lengthVector[i]); // restore genuine length word } } void DepthVectorWithFixedLength::RestoreLengthWords() { for (POLYUNSIGNED i = 0; i < this->nitems; i++) ptrVector[i]->SetLengthWord(length); // restore genuine length word } // Fix up the length word. Then update all addresses to their new location if // we have shared the original destination of the address with something else. void DepthVector::FixLengthAndAddresses(ScanAddress *scan) { RestoreLengthWords(); for (POLYUNSIGNED i = 0; i < this->nitems; i++) { // Fix up all addresses. scan->ScanAddressesInObject(ptrVector[i]); } } // Restore the original length words on forwarding pointers. // After sorting the pointer vector and length vector are no longer // matched so we have to follow the pointers. void DepthVectorWithVariableLength::RestoreForwardingPointers() { for (POLYUNSIGNED i = 0; i < this->nitems; i++) { PolyObject *obj = ptrVector[i]; if (obj->ContainsForwardingPtr()) obj->SetLengthWord(obj->GetForwardingPtr()->LengthWord()); } } // This class is used in two places and is called to ensure that all // object length words have been restored. // Before we actually try to share the immutable objects at a particular depth it // is called to update addresses in those objects to take account of // sharing at lower depths. // When all sharing is complete it is called to update the addresses in // level zero objects, i.e. mutables and code. class ProcessFixupAddress: public ScanAddress { protected: virtual POLYUNSIGNED ScanAddressAt(PolyWord *pt); virtual POLYUNSIGNED ScanCodeAddressAt(PolyObject **pt); virtual PolyObject *ScanObjectAddress(PolyObject *base) { return GetNewAddress(base).AsObjPtr(); } PolyWord GetNewAddress(PolyWord old); }; POLYUNSIGNED ProcessFixupAddress::ScanAddressAt(PolyWord *pt) { *pt = GetNewAddress(*pt); return 0; } // Don't have to do anything for code since it isn't moved. POLYUNSIGNED ProcessFixupAddress::ScanCodeAddressAt(PolyObject **pt) { return 0; } // Returns the new address if the argument is the address of an object that // has moved, otherwise returns the original. PolyWord ProcessFixupAddress::GetNewAddress(PolyWord old) { if (old.IsTagged() || old == PolyWord::FromUnsigned(0)) return old; // Nothing to do. ASSERT(old.IsDataPtr()); PolyObject *obj = old.AsObjPtr(); POLYUNSIGNED L = obj->LengthWord(); if (obj->ContainsForwardingPtr()) // tombstone is a pointer to a shared object { PolyObject *newp = obj->GetForwardingPtr(); // ASSERT (newp->ContainsNormalLengthWord()); return newp; } // Generally each address will point to an object processed at a lower depth. // The exception is if we have a cycle and have assigned the rest of the // structure to a higher depth. // N.B. We return the original address here but this could actually share // with something else and not be retained. if (OBJ_IS_DEPTH(L)) return old; ASSERT (obj->ContainsNormalLengthWord()); // object is not shared return old; } // This class is used to set up the depth vectors for sorting. It subclasses ScanAddress // in order to be able to use that for code objects since they are complicated but it // handles all the other object types itself. It scans them depth-first using an explicit stack. class ProcessAddToVector: public ScanAddress { public: ProcessAddToVector(ShareDataClass *p): m_parent(p), addStack(0), stackSize(0), asp(0) {} ~ProcessAddToVector(); // These are used when scanning code areas. They return either // a length or a possibly updated address. virtual POLYUNSIGNED ScanAddressAt(PolyWord *pt) { (void)AddPolyWordToDepthVectors(*pt); return 0; } virtual PolyObject *ScanObjectAddress(PolyObject *base) { (void)AddObjectToDepthVector(base); return base; } void ProcessRoot(PolyObject *root); protected: // Process an address and return the "depth". POLYUNSIGNED AddPolyWordToDepthVectors(PolyWord old); POLYUNSIGNED AddObjectToDepthVector(PolyObject *obj); void PushToStack(PolyObject *obj); ShareDataClass *m_parent; PolyObject **addStack; unsigned stackSize; unsigned asp; }; ProcessAddToVector::~ProcessAddToVector() { // Normally the stack will be empty. However if we have run out of // memory and thrown an exception we may well have items left. // We have to remove the mark bits otherwise it will mess up any // subsequent GC. for (unsigned i = 0; i < asp; i++) { PolyObject *obj = addStack[i]; if (obj->LengthWord() & _OBJ_GC_MARK) obj->SetLengthWord(obj->LengthWord() & (~_OBJ_GC_MARK)); } free(addStack); // Now free the stack } POLYUNSIGNED ProcessAddToVector::AddPolyWordToDepthVectors(PolyWord old) { // If this is a tagged integer or an IO pointer that's simply a constant. if (old.IsTagged() || old == PolyWord::FromUnsigned(0)) return 0; return AddObjectToDepthVector(old.AsObjPtr()); } // Either adds an object to the stack or, if its depth is known, adds it // to the depth vector and returns the depth. // We use _OBJ_GC_MARK to detect when we have visited a cell but not yet // computed the depth. We have to be careful that this bit is removed // before we finish in the case that we run out of memory and throw an // exception. PushToStack may throw the exception if the stack needs to // grow. POLYUNSIGNED ProcessAddToVector::AddObjectToDepthVector(PolyObject *obj) { MemSpace *space = gMem.SpaceForAddress(((PolyWord*)obj)-1); if (space == 0) return 0; POLYUNSIGNED L = obj->LengthWord(); if (OBJ_IS_DEPTH(L)) // tombstone contains genuine depth or 0. return OBJ_GET_DEPTH(L); if (obj->LengthWord() & _OBJ_GC_MARK) return 0; // Marked but not yet scanned. Circular structure. ASSERT (OBJ_IS_LENGTH(L)); if (obj->IsMutable()) { // Mutable data in the local or permanent areas. Ignore byte objects or // word objects containing only ints. if (obj->IsWordObject()) { bool containsAddress = false; for (POLYUNSIGNED j = 0; j < OBJ_OBJECT_LENGTH(L) && !containsAddress; j++) containsAddress = ! obj->Get(j).IsTagged(); if (containsAddress) { // Add it to the vector so we will update any addresses it contains. m_parent->AddToVector(0, L, obj); // and follow any addresses to try to merge those. PushToStack(obj); obj->SetLengthWord(L | _OBJ_GC_MARK); // To prevent rescan } // If we don't add it to the vector we mustn't set _OBJ_GC_MARK. } return 0; // Level is zero } if (space->spaceType == ST_PERMANENT && ((PermanentMemSpace*)space)->hierarchy == 0) { // Immutable data in the permanent area can't be merged // because it's read only. We need to follow the addresses // because they may point to mutable areas containing data // that can be. A typical case is the root function pointing // at the global name table containing new declarations. Bitmap *bm = &((PermanentMemSpace*)space)->shareBitmap; if (! bm->TestBit((PolyWord*)obj - space->bottom)) { bm->SetBit((PolyWord*)obj - space->bottom); if (! obj->IsByteObject()) PushToStack(obj); } return 0; } /* There's a problem sharing code objects if they have relative calls/jumps in them to other code. The code of two functions may be identical (e.g. they both call functions 100 bytes ahead) and so they will appear the same but if the functions they jump to are different they are actually different. For that reason we don't share code segments. DCJM 4/1/01 */ if (obj->IsCodeObject()) { // We want to update addresses in the code segment. m_parent->AddToVector(0, L, obj); PushToStack(obj); - gMem.SpaceForAddress(obj)->writeAble(obj)->SetLengthWord(L | _OBJ_GC_MARK); // To prevent rescan + gMem.SpaceForObjectAddress(obj)->writeAble(obj)->SetLengthWord(L | _OBJ_GC_MARK); // To prevent rescan return 0; } // Byte objects always have depth 1 and can't contain addresses. if (obj->IsByteObject()) { m_parent->AddToVector (1, L, obj);// add to vector at correct depth obj->SetLengthWord(OBJ_SET_DEPTH(1)); return 1; } ASSERT(OBJ_IS_WORD_OBJECT(L) || OBJ_IS_CLOSURE_OBJECT(L)); // That leaves immutable data objects. PushToStack(obj); obj->SetLengthWord(L | _OBJ_GC_MARK); // To prevent rescan return 0; } // Adds an object to the stack. void ProcessAddToVector::PushToStack(PolyObject *obj) { if (asp == stackSize) { if (addStack == 0) { addStack = (PolyObject**)malloc(sizeof(PolyObject*) * 100); if (addStack == 0) throw MemoryException(); stackSize = 100; } else { unsigned newSize = stackSize+100; PolyObject** newStack = (PolyObject**)realloc(addStack, sizeof(PolyObject*) * newSize); if (newStack == 0) throw MemoryException(); stackSize = newSize; addStack = newStack; } } ASSERT(asp < stackSize); addStack[asp++] = obj; } // Processes the root and anything reachable from it. Addresses are added to the // explicit stack if an object has not yet been processed. Most of this function // is about processing the stack. void ProcessAddToVector::ProcessRoot(PolyObject *root) { // Mark the initial object AddObjectToDepthVector(root); // Process the stack until it's empty. while (asp != 0) { // Pop it from the stack. PolyObject *obj = addStack[asp-1]; if (obj->IsCodeObject()) { // Code cells are now only found in the code area. /* There's a problem sharing code objects if they have relative calls/jumps in them to other code. The code of two functions may be identical (e.g. they both call functions 100 bytes ahead) and so they will appear the same but if the functions they jump to are different they are actually different. For that reason we don't share code segments. DCJM 4/1/01 */ asp--; // Pop it because we'll process it completely ScanAddressesInObject(obj); // If it's local set the depth with the value zero. It has already been // added to the zero depth vector. if (obj->LengthWord() & _OBJ_GC_MARK) - gMem.SpaceForAddress(obj)->writeAble(obj)->SetLengthWord(OBJ_SET_DEPTH(0)); // Now scanned + gMem.SpaceForObjectAddress(obj)->writeAble(obj)->SetLengthWord(OBJ_SET_DEPTH(0)); // Now scanned } else { POLYUNSIGNED length = obj->Length(); PolyWord *pt = (PolyWord*)obj; unsigned osp = asp; if (obj->IsClosureObject()) { // The first word of a closure is a code pointer. We don't share code but // we do want to share anything reachable from the constants. AddObjectToDepthVector(*(PolyObject**)pt); pt += sizeof(PolyObject*) / sizeof(PolyWord); length -= sizeof(PolyObject*) / sizeof(PolyWord); } if (((obj->LengthWord() & _OBJ_GC_MARK) && !obj->IsMutable())) { // Immutable local objects. These can be shared. We need to compute the // depth by computing the maximum of the depth of all the addresses in it. POLYUNSIGNED depth = 0; while (length != 0 && osp == asp) { POLYUNSIGNED d = AddPolyWordToDepthVectors(*pt); if (d > depth) depth = d; pt++; length--; } if (osp == asp) { // We've finished it asp--; // Pop this item. depth++; // One more for this object obj->SetLengthWord(obj->LengthWord() & (~_OBJ_GC_MARK)); m_parent->AddToVector(depth, obj->LengthWord() & (~_OBJ_GC_MARK), obj); obj->SetLengthWord(OBJ_SET_DEPTH(depth)); } } else { // Mutable or non-local objects. These have depth zero. Local objects have // _OBJ_GC_MARK in their header. Immutable permanent objects cannot be // modified so we don't set the depth. Mutable objects are added to the // depth vectors even though they aren't shared so that they will be // updated if they point to immutables that have been shared. while (length != 0) { if (!(*pt).IsTagged()) { // If we've already pushed an address break now if (osp != asp) break; // Process the address and possibly push it AddPolyWordToDepthVectors(*pt); } pt++; length--; } if (length == 0) { // We've finished it if (osp != asp) { ASSERT(osp == asp - 1); addStack[osp - 1] = addStack[osp]; } asp--; // Pop this item. if (obj->LengthWord() & _OBJ_GC_MARK) obj->SetLengthWord(OBJ_SET_DEPTH(0)); } } } } } // This is called by the root thread to do the work. bool ShareDataClass::RunShareData(PolyObject *root) { // We use a bitmap to indicate when we've visited an object to avoid // infinite recursion in cycles in the data. for (std::vector::iterator i = gMem.pSpaces.begin(); i < gMem.pSpaces.end(); i++) { PermanentMemSpace *space = *i; if (!space->isMutable && space->hierarchy == 0) { if (! space->shareBitmap.Create(space->spaceSize())) return false; } } POLYUNSIGNED totalObjects = 0; POLYUNSIGNED totalShared = 0; // Build the vectors from the immutable objects. bool success = true; try { ProcessAddToVector addToVector(this); addToVector.ProcessRoot(root); } catch (MemoryException &) { // If we ran out of memory we may still be able to process what we have. // That will also do any clean-up. success = false; } ProcessFixupAddress fixup; for (POLYUNSIGNED depth = 1; depth < maxVectorSize; depth++) { for (unsigned j = 0; j < FIXEDLENGTHSIZE; j++) { if (depth < depthVectorArray[j].size()) { DepthVector *vec = depthVectorArray[j][depth]; // Set the length word and update all addresses. vec->FixLengthAndAddresses(&fixup); vec->Sort(); POLYUNSIGNED n = vec->MergeSameItems(); if ((debugOptions & DEBUG_SHARING) && n > 0) Log("Sharing: Level %4" POLYUFMT ", size %3u, Objects %6" POLYUFMT ", Shared %6" POLYUFMT " (%1.0f%%)\n", depth, j, vec->ItemCount(), n, (float)n / (float)vec->ItemCount() * 100.0); totalObjects += vec->ItemCount(); totalShared += n; } } } if (debugOptions & DEBUG_SHARING) Log("Sharing: Maximum level %4" POLYUFMT ",\n", maxVectorSize); /* At this stage, we have fixed up most but not all of the forwarding pointers. The ones that we haven't fixed up arise from situations such as the following: X -> Y <-> Z i.e. Y and Z form a loop, and X is isomorphic to Z. When we assigned the depths, we have to arbitrarily break the loop between Y and Z. Suppose Y is assigned to level 1, and Z is assigned to level 2. When we process level 1 and fixup Y, there's nothing to do, since Z is still an ordinary object. However when we process level 2, we find that X and Z are isomorphic so we arbitrarily choose one of them and turn it into a "tombstone" pointing at the other. If we change Z into the tombstone, then Y now contains a pointer that needs fixing up. That's why we need the second fixup pass. Note also that if we had broken the loop the other way, we would have assigned Z to level 1, Y to level 2 and X to level 3, so we would have missed the chance to share Z and X. Perhaps that's why running the program repeatedly sometimes finds extra things to share? SPF 26/1/95 */ /* We have updated the addresses in objects with non-zero level so they point to the single occurrence but we need to do the same with level 0 objects (mutables and code). */ for (unsigned j = 0; j < FIXEDLENGTHSIZE; j++) { if (! depthVectorArray[j].empty()) { DepthVector *v = depthVectorArray[j][0]; // Log this because it could be very large. if (debugOptions & DEBUG_SHARING) Log("Sharing: Level %4" POLYUFMT ", size %3u, Objects %6" POLYUFMT "\n", 0ul, j, v->ItemCount()); v->FixLengthAndAddresses(&fixup); } } /* Previously we made a complete scan over the memory updating any addresses so that if we have shared two substructures within our root we would also share any external pointers. This has been removed but we have to reinstate the length words we've overwritten with forwarding pointers because there may be references to unshared objects from outside. */ for (POLYUNSIGNED d = 1; d < maxVectorSize; d++) { for (unsigned j = 0; j < FIXEDLENGTHSIZE; j++) { if (d < depthVectorArray[j].size()) { DepthVector *v = depthVectorArray[j][d]; v->RestoreForwardingPointers(); } } } if (debugOptions & DEBUG_SHARING) Log ("Sharing: Total Objects %6" POLYUFMT ", Total Shared %6" POLYUFMT " (%1.0f%%)\n", totalObjects, totalShared, (float)totalShared / (float)totalObjects * 100.0); return success; // Succeeded. } class ShareRequest: public MainThreadRequest { public: ShareRequest(Handle root): MainThreadRequest(MTP_SHARING), shareRoot(root), result(false) {} virtual void Perform() { ShareDataClass s; // Do a full GC. If we have a large heap the allocation of the vectors // can cause paging. Doing this now reduces the heap and discards the // allocation spaces. It may be overkill if we are applying the sharing // to a small root but generally it seems to be applied to the whole heap. FullGCForShareCommonData(); gcProgressBeginOtherGC(); // Set the phase to "other" now the GC is complete. // Now do the sharing. result = s.RunShareData(shareRoot->WordP()); } Handle shareRoot; bool result; }; // ShareData. This is the main entry point. // Because this can recurse deeply it needs to be run by the main thread. // Also it manipulates the heap in ways that could mess up other threads // so we need to stop them before executing this. void ShareData(TaskData *taskData, Handle root) { if (! root->Word().IsDataPtr()) return; // Nothing to do. We could do handle a code pointer but it shouldn't occur. // Request the main thread to do the sharing. ShareRequest request(root); processes->MakeRootRequest(taskData, &request); // Raise an exception if it failed. if (! request.result) raise_exception_string(taskData, EXC_Fail, "Insufficient memory"); } // RTS call entry. POLYUNSIGNED PolyShareCommonData(FirstArgument threadId, PolyWord root) { TaskData *taskData = TaskData::FindTaskForId(threadId); ASSERT(taskData != 0); taskData->PreRTSCall(); Handle reset = taskData->saveVec.mark(); try { if (! root.IsDataPtr()) return TAGGED(0).AsUnsigned(); // Nothing to do. // Request the main thread to do the sharing. ShareRequest request(taskData->saveVec.push(root)); processes->MakeRootRequest(taskData, &request); // Raise an exception if it failed. if (! request.result) raise_exception_string(taskData, EXC_Fail, "Insufficient memory"); } catch (...) { } // If an ML exception is raised taskData->saveVec.reset(reset); taskData->PostRTSCall(); return TAGGED(0).AsUnsigned(); } struct _entrypts shareDataEPT[] = { { "PolyShareCommonData", (polyRTSFunction)&PolyShareCommonData}, { NULL, NULL} // End of list. };