本文介绍在kvm中垃圾收集的实际实现,其方法名为garbageCollectForReal.其代码如下:
void garbageCollectForReal(int realSize) { CHUNK firstFreeChunk; long maximumFreeSize; /* The actual high-level GC algorithm is here */ // 1. 标记root markRootObjects(); // 2. 从root对象出发,进行扫描 markNonRootObjects(); // 3. 处理WeakPointer markWeakPointerLists(); // 4.处理WeakReferences markWeakReferences(); // 5. sweep firstFreeChunk = sweepTheHeap(&maximumFreeSize); #if ENABLE_HEAP_COMPACTION if (realSize > maximumFreeSize) {// 当heap 内最大的可用内存不满足要求时,需要进行压缩处理 /* We need to compact the heap. */ breakTableStruct currentTable; // 压缩 cell* freeStart = compactTheHeap(¤tTable, firstFreeChunk); if (currentTable.length > 0) { // 修改指针 updateRootObjects(¤tTable); updateHeapObjects(¤tTable, freeStart); } if (freeStart < CurrentHeapEnd - 1) { firstFreeChunk = (CHUNK)freeStart; firstFreeChunk->size = (CurrentHeapEnd - freeStart - HEADERSIZE) << TYPEBITS; firstFreeChunk->next = NULL; } else { /* We are so utterly hosed. * Memory is completely full, and there is no free space whatsoever. * 没有空闲内存 */ firstFreeChunk = NULL; } } #endif FirstFreeChunk = firstFreeChunk; }其中,我们来看第一步: markRootObjects.其代码如下:
static void markRootObjects(void) { cell *heapSpace = CurrentHeap; cell *heapSpaceEnd = CurrentHeapEnd; cellOrPointer *ptr, *endptr; HASHTABLE stringTable; THREAD thread; // 1. 标记GlobalRoots ptr = &GlobalRoots[0]; endptr = ptr + GlobalRootsLength; for ( ; ptr < endptr; ptr++) { MARK_OBJECT_IF_NON_NULL(*(ptr->cellpp)); } // 2. 标记TemporaryRoots ptr = &TemporaryRoots[0]; endptr = ptr + TemporaryRootsLength; for ( ; ptr < endptr; ptr++) { cellOrPointer location = *ptr; if (location.cell == -1) {// 占双字节 /* 此处的TemporaryRoot是使用DECLARE_TEMPORARY_ROOT_FROM_BASE声明的 */ MARK_OBJECT_IF_NON_NULL(ptr[2].cellpp); ptr += 2; } else { MARK_OBJECT_IF_NON_NULL(*(location.cellpp)); } } #if ASYNCHRONOUS_NATIVE_FUNCTIONS { // 3. 处理ASYNCIOCB int i; for (i = 0 ; i < ASYNC_IOCB_COUNT ; i++) { ASYNCIOCB *aiocb = &IocbRoots[i]; MARK_OBJECT_IF_NON_NULL(aiocb->thread); MARK_OBJECT_IF_NON_NULL(aiocb->instance); MARK_OBJECT_IF_NON_NULL(aiocb->array); } } #endif #if ROMIZING { /* In RELOCATABLE_ROM builds, we have a pointer to the static data. * In !RELOCATABLE_ROM builds, we have the actual array. */ #if RELOCATABLE_ROM long *staticPtr = KVM_staticDataPtr; #else long *staticPtr = KVM_staticData; #endif // 4. 处理静态区域 int refCount = staticPtr[0]; for( ; refCount > 0; refCount--) { MARK_OBJECT_IF_NON_NULL((cell *)staticPtr[refCount]); } } #endif // 5. 处理InternStringTable stringTable = InternStringTable; if (ROMIZING || stringTable != NULL) { int count = stringTable->bucketCount; while (--count >= 0) { INTERNED_STRING_INSTANCE instance = (INTERNED_STRING_INSTANCE)stringTable->bucket[count]; for ( ; instance != NULL; instance = instance->next) { checkMonitorAndMark((OBJECT)instance); } } } // 6. 处理ClassTable if (ROMIZING || ClassTable != NULL) { FOR_ALL_CLASSES(clazz) checkMonitorAndMark((OBJECT)clazz);// 1. 标记该对象所对应的Monitor if (!IS_ARRAY_CLASS(clazz)) { INSTANCE_CLASS iclazz = (INSTANCE_CLASS)clazz; POINTERLIST statics = iclazz->staticFields; METHODTABLE methodTable = iclazz->methodTable; MARK_OBJECT_IF_NON_NULL(iclazz->initThread); if (clazz->accessFlags & ACC_ROM_CLASS) {// 2. 如果该对象是rom中的class,则不出来 continue; } if (USESTATIC) {// 3. 如果使用"static memory" (storage RAM on Palm)的话,则依次标记constPool,ifaceTable,fieldTable,methodTable MARK_OBJECT_IF_NON_NULL(iclazz->constPool); MARK_OBJECT_IF_NON_NULL(iclazz->ifaceTable); MARK_OBJECT_IF_NON_NULL(iclazz->fieldTable); MARK_OBJECT_IF_NON_NULL(iclazz->methodTable); } // 4. 依次标记该类的静态字段所引用的对象 if (statics != NULL) { int count = statics->length; while (--count >= 0) { MARK_OBJECT_IF_NON_NULL(statics->data[count].cellp); } } if (iclazz->status == CLASS_VERIFIED) { continue; } // 5. 依次标记该对象非本地方法的verifierMap FOR_EACH_METHOD(thisMethod, methodTable) /* Mark the bytecode object alive for non-native methods */ if (!(thisMethod->accessFlags & ACC_NATIVE)) { checkValidHeapPointer((cell *) thisMethod->u.java.stackMaps.verifierMap); MARK_OBJECT_IF_NON_NULL(thisMethod->u.java.stackMaps.verifierMap); } END_FOR_EACH_METHOD } END_FOR_ALL_CLASSES } // 7. 处理活动线程 for (thread = AllThreads; thread != NULL; thread = thread->nextAliveThread){ MARK_OBJECT(thread); // 标记该活动线程 if (thread->javaThread != NULL) {// 如果该线程是对应的java线程,则也标记java线程 MARK_OBJECT(thread->javaThread); } if (thread->stack != NULL) { markThreadStack(thread); // 标记线程的执行栈 } } }其中的步骤为:
标记GlobalRoots,遍历GlobalRoot,如果GlobalRoot所对应的对象存活,则标记为存活(将对象头中的标记为设为1). 此处使用到了MARK_OBJECT_IF_NON_NULL.其定义如下:
#define MARKBIT 0x00000001 #define STATICBIT 0x00000002 #define TYPEMASK 0x000000FC #define MARK_OBJECT_IF_NON_NULL(object) \ if (inHeapSpaceFast((object))) { OBJECT_HEADER((object)) |= MARKBIT; } #define inHeapSpaceFast(ptr) \ (((cell *)(ptr) >= heapSpace) && ((cell *)(ptr) < heapSpaceEnd)) #define OBJECT_HEADER(object) ((cell *)(object))[-HEADERSIZE]在kvm内部,标记为GlobalRoot的有: OutOfMemoryObject,StackOverflowObject,waitingThread,MainThread,CurrentThread,RunnableThreads,TimerQueue,debugRoot,bucketMap,ClassPathTable,filePointerRoot.这些都在之前的文章介绍过,这里就不再介绍了.
标记TemporaryRoots.关于TemporaryRoot是结合START_TEMPORARY_ROOTS,END_TEMPORARY_ROOTS,DECLARE_TEMPORARY_ROOT等宏使用的.定义如下:
#define START_TEMPORARY_ROOTS { int _tmp_roots_ = TemporaryRootsLength; #define END_TEMPORARY_ROOTS TemporaryRootsLength = _tmp_roots_; } #define IS_TEMPORARY_ROOT(_var_, _value_) \ _var_ = (VERIFY_INSIDE_TEMPORARY_ROOTS \ _var_ = _value_, \ VERIFY_TEMPORARY_ROOT_SPACE(1) \ TemporaryRoots[TemporaryRootsLength++].cellp = (cell *)&_var_, \ _var_) #define IS_TEMPORARY_ROOT_FROM_BASE(_var_, _value_, _base_) \ _var_ = (VERIFY_INSIDE_TEMPORARY_ROOTS \ VERIFY_TEMPORARY_ROOT_SPACE(3) \ _var_ = _value_, \ TemporaryRoots[TemporaryRootsLength].cell = -1, \ TemporaryRoots[TemporaryRootsLength+1].cellpp = (cell **)&_var_, \ TemporaryRoots[TemporaryRootsLength+2].cellp = (cell *)_base_, \ TemporaryRootsLength = TemporaryRootsLength + 3, \ _var_) #define DECLARE_TEMPORARY_ROOT(_type_, _var_, _value_) \ _type_ IS_TEMPORARY_ROOT(_var_, _value_) #define DECLARE_TEMPORARY_ROOT_FROM_BASE(_type_, _var_, _value_, _base_) \ _type_ IS_TEMPORARY_ROOT_FROM_BASE(_var_, _value_, _base_)因此,关于此处标记TemporaryRoots就很清楚了.如果location.cell == -1 则说明该TemporaryRoot是使用DECLARE_TEMPORARY_ROOT_FROM_BASE 声明的,因此,在标记时,使用ptr[2].cellpp来访问对象指针。
处理ASYNCIOCB.ASYNCIOCB定义如下:
typedef struct asynciocb { struct asynciocb *nextFree; THREAD thread; INSTANCE instance; BYTEARRAY array; char *exception; } ASYNCIOCB; typedef struct threadQueue* THREAD; typedef struct instanceStruct* INSTANCE; typedef struct byteArrayStruct* BYTEARRAY;其中的指针有nextFree, thread，instance，array.这里只需要处理thread，instance，array即可.因为此处是通过遍历整个ASYNCIOCB实现标记的,因此就不需要nextFree指针了.
处理静态区域.此处涉及到ROM,就不展开了.
处理InternStringTable. InternStringTable是一个数组加链表的结构,这点在之前的文章中有介绍.这里就展开了.此处介绍一下checkMonitorAndMark.其代码如下:
static void checkMonitorAndMark(OBJECT object) { /* We only need to mark real monitors. We don't need to mark threads' * in the monitor/hashcode slot since they will be marked elsewhere */ if (OBJECT_HAS_REAL_MONITOR(object)) {// 如果该对象存在monitor cell *heapSpace = CurrentHeap; cell *heapSpaceEnd = CurrentHeapEnd; MONITOR monitor = OBJECT_MHC_MONITOR(object);// 获得该对象的monitor /* A monitor doesn't contain any subobjects that won't be marked * elsewhere */ MARK_OBJECT(monitor);// 将monitor 标记为存活 } }处理ClassTable.在注释中有详细介绍.
处理活动线程.此处重点介绍markThreadStack,该方法的功能是标记方法中的局部变量,操作数栈所引用的对象.其代码为:
static void markThreadStack(THREAD thisThread) { /* Perform a complete stack trace, looking for pointers */ /* inside the stack and marking the corresponding objects. */ cell *heapSpace = CurrentHeap; cell *heapSpaceEnd = CurrentHeapEnd; FRAME thisFP = thisThread->fpStore; cell* thisSP = thisThread->spStore; BYTE* thisIP = thisThread->ipStore; char map[(MAXIMUM_STACK_AND_LOCALS + 7) >> 3]; long i; STACK stack = thisThread->stack; // 1. 如果该线程没有所对应的栈帧,则在标记stack后直接return if (thisFP == NULL) { MARK_OBJECT_IF_NON_NULL(stack); return; } thisFP->stack->next = NULL; /* we're the end of the stack chain. */ while (thisFP != NULL) { /* Get a pointer to the method of the current frame */ METHOD method = thisFP->thisMethod; // #define FRAMELOCALS(fp) ((cell*)(fp) - fp->thisMethod->frameSize) cell* localVars = FRAMELOCALS(thisFP); // 获得局部变量的指针 cell *operandStack = (cell*)thisFP + SIZEOF_FRAME; // 获得操作栈 int localsCount = method->frameSize; long realStackSize = thisSP - (cell*)thisFP - SIZEOF_FRAME + 1; // 获得操作数栈的大小 unsigned int totalSize = realStackSize + localsCount; /* 标记syncObject和该栈帧所对应的stack*/ MARK_OBJECT_IF_NON_NULL(thisFP->syncObject); MARK_OBJECT_IF_NON_NULL(thisFP->stack); if (method == RunCustomCodeMethod) { memset(map, -1, (realStackSize + 7) >> 3); } else { unsigned int expectedStackSize = getGCRegisterMask(method, thisIP, map); // 获得stack的实际大小,通过模拟字节码执行 if ((unsigned int)realStackSize > expectedStackSize) { // 如果gc是在KNI中调用的,则执行栈可能含有比stack map 更多的元素. totalSize = expectedStackSize + localsCount; } } // 标记方法中的局部变量,操作数栈所引用的对象 for (i = 0; i < totalSize; i++) { if (map[i >> 3] & (1 << (i & 7))) { cell *arg; if (i < localsCount) { arg = *(cell **)&localVars[i]; } else { arg = *(cell **)&operandStack[i - localsCount]; } if (INCLUDEDEBUGCODE && method != RunCustomCodeMethod) { checkValidHeapPointer(arg); } // 进行标记 MARK_OBJECT_IF_NON_NULL(arg); } } /* This frame is now done. Go to the previous one */ /* using the same algorithm as in 'popFrame()'. 进行递归处理 */ thisSP = thisFP->previousSp; thisIP = thisFP->previousIp; thisFP = thisFP->previousFp; } }注意,此时是从后往前遍历栈帧来进行标记的
