davide carboni
Embed:
(wiki syntax)
Show/hide line numbers
heap.c
Go to the documentation of this file.
00001 /* 00002 # This file is Copyright 2003, 2006, 2007, 2009 Dean Hall. 00003 # 00004 # This file is part of the PyMite VM. 00005 # The PyMite VM is free software: you can redistribute it and/or modify 00006 # it under the terms of the GNU GENERAL PUBLIC LICENSE Version 2. 00007 # 00008 # The PyMite VM is distributed in the hope that it will be useful, 00009 # but WITHOUT ANY WARRANTY; without even the implied warranty of 00010 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00011 # A copy of the GNU GENERAL PUBLIC LICENSE Version 2 00012 # is seen in the file COPYING in this directory. 00013 */ 00014 00015 00016 #undef __FILE_ID__ 00017 #define __FILE_ID__ 0x06 00018 00019 00020 /** 00021 * \file 00022 * \brief VM Heap 00023 * 00024 * VM heap operations. 00025 * All of PyMite's dynamic memory is obtained from this heap. 00026 * The heap provides dynamic memory on demand. 00027 */ 00028 00029 00030 #include "pm.h" 00031 00032 00033 /** Checks for heap size definition. */ 00034 #ifndef PM_HEAP_SIZE 00035 #warning PM_HEAP_SIZE not defined in src/platform/<yourplatform>/pmfeatures.h 00036 #elif PM_HEAP_SIZE & 3 00037 #error PM_HEAP_SIZE is not a multiple of four 00038 #endif 00039 00040 00041 /** 00042 * The maximum size a live chunk can be (a live chunk is one that is in use). 00043 * The live chunk size is limited by the size field in the *object* descriptor. 00044 * That field is nine bits with two assumed least significant bits (zeros): 00045 * (0x1FF << 2) == 2044 00046 */ 00047 #define HEAP_MAX_LIVE_CHUNK_SIZE 2044 00048 00049 /** 00050 * The maximum size a free chunk can be (a free chunk is one that is not in use). 00051 * The free chunk size is limited by the size field in the *heap* descriptor. 00052 * That field is fourteen bits with two assumed least significant bits (zeros): 00053 * (0x3FFF << 2) == 65532 00054 */ 00055 #define HEAP_MAX_FREE_CHUNK_SIZE 65532 00056 00057 /** The minimum size a chunk can be (rounded up to a multiple of 4) */ 00058 #define HEAP_MIN_CHUNK_SIZE ((sizeof(PmHeapDesc_t) + 3) & ~3) 00059 00060 00061 /** 00062 * Gets the GC's mark bit for the object. 00063 * This MUST NOT be called on objects that are free. 00064 */ 00065 #define OBJ_GET_GCVAL(pobj) ((((pPmObj_t)pobj)->od >> OD_MARK_SHIFT) & 1) 00066 00067 /** 00068 * Sets the GC's mark bit for the object 00069 * This MUST NOT be called on objects that are free. 00070 */ 00071 #ifdef HAVE_GC 00072 #define OBJ_SET_GCVAL(pobj, gcval) \ 00073 do \ 00074 { \ 00075 ((pPmObj_t)pobj)->od = (gcval) ? ((pPmObj_t)pobj)->od | OD_MARK_BIT \ 00076 : ((pPmObj_t)pobj)->od & ~OD_MARK_BIT;\ 00077 } \ 00078 while (0) 00079 #else 00080 #define OBJ_SET_GCVAL(pobj, gcval) 00081 #endif /* HAVE_GC */ 00082 00083 00084 /** 00085 * The following is a diagram of the heap descriptor at the head of the chunk: 00086 * 00087 * MSb LSb 00088 * 7 6 5 4 3 2 1 0 00089 * pchunk-> +-+-+-+-+-+-+-+-+ 00090 * | S[9:2] | S := Size of the chunk (2 LSbs dropped) 00091 * +-+-+-----------+ F := Chunk free bit (not in use) 00092 * |F|R| S[15:10] | R := Bit reserved for future use 00093 * +-+-+-----------+ 00094 * | P(L) | P := hd_prev: Pointer to previous node 00095 * | P(H) | N := hd_next: Pointer to next node 00096 * | N(L) | 00097 * | N(H) | Theoretical min size == 6 00098 * +---------------+ Effective min size == 8 00099 * | unused space | (12 on 32-bit MCUs) 00100 * ... ... 00101 * | end chunk | 00102 * +---------------+ 00103 */ 00104 typedef struct PmHeapDesc_s 00105 { 00106 /** Heap descriptor */ 00107 uint16_t hd; 00108 00109 /** Ptr to prev heap chunk */ 00110 struct PmHeapDesc_s *prev; 00111 00112 /** Ptr to next heap chunk */ 00113 struct PmHeapDesc_s *next; 00114 } PmHeapDesc_t, 00115 *pPmHeapDesc_t; 00116 00117 typedef struct PmHeap_s 00118 { 00119 /* 00120 * WARNING: Leave 'base' field at the top of struct to increase chance 00121 * of alignment when compiler doesn't recognize the aligned attribute 00122 * which is specific to GCC 00123 */ 00124 /** Global declaration of heap. */ 00125 uint8_t base[PM_HEAP_SIZE]; 00126 00127 /** Ptr to list of free chunks; sorted smallest to largest. */ 00128 pPmHeapDesc_t pfreelist; 00129 00130 /** The amount of heap space available in free list */ 00131 #if PM_HEAP_SIZE > 65535 00132 uint32_t avail; 00133 #else 00134 uint16_t avail; 00135 #endif 00136 00137 #ifdef HAVE_GC 00138 /** Garbage collection mark value */ 00139 uint8_t gcval; 00140 00141 /** Boolean to indicate if GC should run automatically */ 00142 uint8_t auto_gc; 00143 #endif /* HAVE_GC */ 00144 00145 } PmHeap_t, 00146 *pPmHeap_t; 00147 00148 00149 /** The PyMite heap */ 00150 static PmHeap_t pmHeap; 00151 00152 00153 #if 0 00154 static void 00155 heap_gcPrintFreelist(void) 00156 { 00157 pPmHeapDesc_t pchunk = pmHeap.pfreelist; 00158 00159 printf("DEBUG: pmHeap.avail = %d\n", pmHeap.avail); 00160 printf("DEBUG: freelist:\n"); 00161 while (pchunk != C_NULL) 00162 { 00163 printf("DEBUG: free chunk (%d bytes) @ 0x%0x\n", 00164 OBJ_GET_SIZE(pchunk), (int)pchunk); 00165 pchunk = pchunk->next; 00166 } 00167 } 00168 #endif 00169 00170 00171 #if 0 00172 /** DEBUG: dumps the heap and roots list to a file */ 00173 static void 00174 heap_dump(void) 00175 { 00176 static int n = 0; 00177 int i; 00178 char filename[32]; 00179 FILE *fp; 00180 00181 snprintf(filename, 32, "pmheapdump%02d.bin", n++); 00182 fp = fopen(filename, "wb"); 00183 00184 /* Write size of heap */ 00185 i = PM_HEAP_SIZE; 00186 fwrite(&i, sizeof(int), 1, fp); 00187 00188 /* Write base address of heap */ 00189 i = (int)&pmHeap.base; 00190 fwrite(&i, sizeof(int *), 1, fp); 00191 00192 /* Write contents of heap */ 00193 fwrite(&pmHeap.base, 1, PM_HEAP_SIZE, fp); 00194 00195 /* Write num roots*/ 00196 i = 10; 00197 fwrite(&i, sizeof(int), 1, fp); 00198 00199 /* Write heap root ptrs */ 00200 fwrite((void *)&gVmGlobal.pnone, sizeof(intptr_t), 1, fp); 00201 fwrite((void *)&gVmGlobal.pfalse, sizeof(intptr_t), 1, fp); 00202 fwrite((void *)&gVmGlobal.ptrue, sizeof(intptr_t), 1, fp); 00203 fwrite((void *)&gVmGlobal.pzero, sizeof(intptr_t), 1, fp); 00204 fwrite((void *)&gVmGlobal.pone, sizeof(intptr_t), 1, fp); 00205 fwrite((void *)&gVmGlobal.pnegone, sizeof(intptr_t), 1, fp); 00206 fwrite((void *)&gVmGlobal.pcodeStr, sizeof(intptr_t), 1, fp); 00207 fwrite((void *)&gVmGlobal.builtins, sizeof(intptr_t), 1, fp); 00208 fwrite((void *)&gVmGlobal.nativeframe, sizeof(intptr_t), 1, fp); 00209 fwrite((void *)&gVmGlobal.threadList, sizeof(intptr_t), 1, fp); 00210 fclose(fp); 00211 } 00212 #endif 00213 00214 00215 /* Removes the given chunk from the free list; leaves list in sorted order */ 00216 static PmReturn_t 00217 heap_unlinkFromFreelist(pPmHeapDesc_t pchunk) 00218 { 00219 C_ASSERT(pchunk != C_NULL); 00220 00221 pmHeap.avail -= OBJ_GET_SIZE(pchunk); 00222 00223 if (pchunk->next != C_NULL) 00224 { 00225 pchunk->next->prev = pchunk->prev; 00226 } 00227 00228 /* If pchunk was the first chunk in the free list, update the heap ptr */ 00229 if (pchunk->prev == C_NULL) 00230 { 00231 pmHeap.pfreelist = pchunk->next; 00232 } 00233 else 00234 { 00235 pchunk->prev->next = pchunk->next; 00236 } 00237 00238 return PM_RET_OK; 00239 } 00240 00241 00242 /* Inserts in order a chunk into the free list. Caller adjusts heap state */ 00243 static PmReturn_t 00244 heap_linkToFreelist(pPmHeapDesc_t pchunk) 00245 { 00246 uint16_t size; 00247 pPmHeapDesc_t pscan; 00248 00249 /* Ensure the object is already free */ 00250 C_ASSERT(OBJ_GET_FREE(pchunk) != 0); 00251 00252 pmHeap.avail += OBJ_GET_SIZE(pchunk); 00253 00254 /* If free list is empty, add to head of list */ 00255 if (pmHeap.pfreelist == C_NULL) 00256 { 00257 pmHeap.pfreelist = pchunk; 00258 pchunk->next = C_NULL; 00259 pchunk->prev = C_NULL; 00260 00261 return PM_RET_OK; 00262 } 00263 00264 /* Scan free list for insertion point */ 00265 pscan = pmHeap.pfreelist; 00266 size = OBJ_GET_SIZE(pchunk); 00267 while ((OBJ_GET_SIZE(pscan) < size) && (pscan->next != C_NULL)) 00268 { 00269 pscan = pscan->next; 00270 } 00271 00272 /* 00273 * Insert chunk after the scan chunk (next is NULL). 00274 * This is a slightly rare case where the last chunk in the free list 00275 * is smaller than the chunk being freed. 00276 */ 00277 if (size > OBJ_GET_SIZE(pscan)) 00278 { 00279 pchunk->next = pscan->next; 00280 pscan->next = pchunk; 00281 pchunk->prev = pscan; 00282 } 00283 00284 /* Insert chunk before the scan chunk */ 00285 else 00286 { 00287 pchunk->next = pscan; 00288 pchunk->prev = pscan->prev; 00289 00290 /* If chunk will be first item in free list */ 00291 if (pscan->prev == C_NULL) 00292 { 00293 pmHeap.pfreelist = pchunk; 00294 } 00295 else 00296 { 00297 pscan->prev->next = pchunk; 00298 } 00299 pscan->prev = pchunk; 00300 } 00301 00302 return PM_RET_OK; 00303 } 00304 00305 00306 /* 00307 * Initializes the heap state variables 00308 */ 00309 PmReturn_t 00310 heap_init(void) 00311 { 00312 pPmHeapDesc_t pchunk; 00313 00314 #if PM_HEAP_SIZE > 65535 00315 uint32_t hs; 00316 #else 00317 uint16_t hs; 00318 #endif 00319 00320 /* Init heap globals */ 00321 pmHeap.pfreelist = C_NULL; 00322 pmHeap.avail = 0; 00323 #ifdef HAVE_GC 00324 pmHeap.gcval = (uint8_t)0; 00325 heap_gcSetAuto(C_TRUE); 00326 #endif /* HAVE_GC */ 00327 00328 /* Create as many max-sized chunks as possible in the freelist */ 00329 for (pchunk = (pPmHeapDesc_t)pmHeap.base, hs = PM_HEAP_SIZE; 00330 hs >= HEAP_MAX_FREE_CHUNK_SIZE; hs -= HEAP_MAX_FREE_CHUNK_SIZE) 00331 { 00332 OBJ_SET_FREE(pchunk, 1); 00333 OBJ_SET_SIZE(pchunk, HEAP_MAX_FREE_CHUNK_SIZE); 00334 heap_linkToFreelist(pchunk); 00335 pchunk = 00336 (pPmHeapDesc_t)((uint8_t *)pchunk + HEAP_MAX_FREE_CHUNK_SIZE); 00337 } 00338 00339 /* Add any leftover memory to the freelist */ 00340 if (hs >= HEAP_MIN_CHUNK_SIZE) 00341 { 00342 /* Round down to a multiple of four */ 00343 hs = hs & ~3; 00344 OBJ_SET_FREE(pchunk, 1); 00345 OBJ_SET_SIZE(pchunk, hs); 00346 heap_linkToFreelist(pchunk); 00347 } 00348 00349 C_DEBUG_PRINT(VERBOSITY_LOW, "heap_init(), id=%p, s=%d\n", 00350 pmHeap.base, pmHeap.avail); 00351 00352 string_cacheInit(); 00353 00354 return PM_RET_OK; 00355 } 00356 00357 00358 /** 00359 * Obtains a chunk of memory from the free list 00360 * 00361 * Performs the Best Fit algorithm. 00362 * Iterates through the freelist to see if a chunk of suitable size exists. 00363 * Shaves a chunk to perfect size iff the remainder is greater than 00364 * the minimum chunk size. 00365 * 00366 * @param size Requested chunk size 00367 * @param r_pchunk Return ptr to chunk 00368 * @return Return status 00369 */ 00370 static PmReturn_t 00371 heap_getChunkImpl(uint16_t size, uint8_t **r_pchunk) 00372 { 00373 PmReturn_t retval; 00374 pPmHeapDesc_t pchunk; 00375 pPmHeapDesc_t premainderChunk; 00376 00377 C_ASSERT(r_pchunk != C_NULL); 00378 00379 /* Skip to the first chunk that can hold the requested size */ 00380 pchunk = pmHeap.pfreelist; 00381 while ((pchunk != C_NULL) && (OBJ_GET_SIZE(pchunk) < size)) 00382 { 00383 pchunk = pchunk->next; 00384 } 00385 00386 /* No chunk of appropriate size was found, raise OutOfMemory exception */ 00387 if (pchunk == C_NULL) 00388 { 00389 *r_pchunk = C_NULL; 00390 PM_RAISE(retval, PM_RET_EX_MEM); 00391 return retval; 00392 } 00393 00394 /* Remove the chunk from the free list */ 00395 retval = heap_unlinkFromFreelist(pchunk); 00396 PM_RETURN_IF_ERROR(retval); 00397 00398 /* Check if a chunk should be carved from what is available */ 00399 if (OBJ_GET_SIZE(pchunk) - size >= HEAP_MIN_CHUNK_SIZE) 00400 { 00401 /* Create the heap descriptor for the remainder chunk */ 00402 premainderChunk = (pPmHeapDesc_t)((uint8_t *)pchunk + size); 00403 OBJ_SET_FREE(premainderChunk, 1); 00404 OBJ_SET_SIZE(premainderChunk, OBJ_GET_SIZE(pchunk) - size); 00405 00406 /* Put the remainder chunk back in the free list */ 00407 retval = heap_linkToFreelist(premainderChunk); 00408 PM_RETURN_IF_ERROR(retval); 00409 00410 /* Convert the chunk from a heap descriptor to an object descriptor */ 00411 OBJ_SET_SIZE(pchunk, 0); 00412 OBJ_SET_FREE(pchunk, 0); 00413 OBJ_SET_SIZE(pchunk, size); 00414 00415 C_DEBUG_PRINT(VERBOSITY_HIGH, 00416 "heap_getChunkImpl()carved, id=%p, s=%d\n", pchunk, 00417 size); 00418 } 00419 else 00420 { 00421 /* Set chunk's type to none (overwrites size field's high byte) */ 00422 OBJ_SET_TYPE((pPmObj_t)pchunk, OBJ_TYPE_NON); 00423 OBJ_SET_FREE(pchunk, 0); 00424 00425 C_DEBUG_PRINT(VERBOSITY_HIGH, 00426 "heap_getChunkImpl()exact, id=%p, s=%d\n", pchunk, 00427 OBJ_GET_SIZE(pchunk)); 00428 } 00429 00430 /* 00431 * Set the chunk's GC mark so it will be collected during the next GC cycle 00432 * if it is not reachable 00433 */ 00434 OBJ_SET_GCVAL(pchunk, pmHeap.gcval); 00435 00436 /* Return the chunk */ 00437 *r_pchunk = (uint8_t *)pchunk; 00438 00439 return retval; 00440 } 00441 00442 00443 /* 00444 * Allocates chunk of memory. 00445 * Filters out invalid sizes. 00446 * Rounds the size up to the next multiple of 4. 00447 * Obtains a chunk of at least the desired size. 00448 */ 00449 PmReturn_t 00450 heap_getChunk(uint16_t requestedsize, uint8_t **r_pchunk) 00451 { 00452 PmReturn_t retval; 00453 uint16_t adjustedsize; 00454 00455 /* Ensure size request is valid */ 00456 if (requestedsize > HEAP_MAX_LIVE_CHUNK_SIZE) 00457 { 00458 PM_RAISE(retval, PM_RET_EX_MEM); 00459 return retval; 00460 } 00461 00462 else if (requestedsize < HEAP_MIN_CHUNK_SIZE) 00463 { 00464 requestedsize = HEAP_MIN_CHUNK_SIZE; 00465 } 00466 00467 /* 00468 * Round up the size to a multiple of 4 bytes. 00469 * This maintains alignment on 32-bit platforms (required). 00470 */ 00471 adjustedsize = ((requestedsize + 3) & ~3); 00472 00473 /* Attempt to get a chunk */ 00474 retval = heap_getChunkImpl(adjustedsize, r_pchunk); 00475 00476 #ifdef HAVE_GC 00477 /* Perform GC if out of memory, gc is enabled and not in native session */ 00478 if ((retval == PM_RET_EX_MEM) && (pmHeap.auto_gc == C_TRUE) 00479 && (gVmGlobal.nativeframe.nf_active == C_FALSE)) 00480 { 00481 retval = heap_gcRun(); 00482 PM_RETURN_IF_ERROR(retval); 00483 00484 /* Attempt to get a chunk */ 00485 retval = heap_getChunkImpl(adjustedsize, r_pchunk); 00486 } 00487 #endif /* HAVE_GC */ 00488 00489 /* Ensure that the pointer is 4-byte aligned */ 00490 if (retval == PM_RET_OK) 00491 { 00492 C_ASSERT(((intptr_t)*r_pchunk & 3) == 0); 00493 } 00494 00495 return retval; 00496 } 00497 00498 00499 /* Releases chunk to the free list */ 00500 PmReturn_t 00501 heap_freeChunk(pPmObj_t ptr) 00502 { 00503 PmReturn_t retval; 00504 00505 C_DEBUG_PRINT(VERBOSITY_HIGH, "heap_freeChunk(), id=%p, s=%d\n", 00506 ptr, OBJ_GET_SIZE(ptr)); 00507 00508 /* Ensure the chunk falls within the heap */ 00509 C_ASSERT(((uint8_t *)ptr >= pmHeap.base) 00510 && ((uint8_t *)ptr < pmHeap.base + PM_HEAP_SIZE)); 00511 00512 /* Insert the chunk into the freelist */ 00513 OBJ_SET_FREE(ptr, 1); 00514 00515 /* Clear type so that heap descriptor's size's upper byte is zero */ 00516 OBJ_SET_TYPE(ptr, 0); 00517 retval = heap_linkToFreelist((pPmHeapDesc_t)ptr); 00518 PM_RETURN_IF_ERROR(retval); 00519 00520 return retval; 00521 } 00522 00523 00524 /* Returns, by reference, the number of bytes available in the heap */ 00525 #if PM_HEAP_SIZE > 65535 00526 uint32_t 00527 #else 00528 uint16_t 00529 #endif 00530 heap_getAvail (void) 00531 { 00532 return pmHeap.avail; 00533 } 00534 00535 00536 #ifdef HAVE_GC 00537 /* 00538 * Marks the given object and the objects it references. 00539 * 00540 * @param pobj Any non-free heap object 00541 * @return Return code 00542 */ 00543 static PmReturn_t 00544 heap_gcMarkObj(pPmObj_t pobj) 00545 { 00546 PmReturn_t retval = PM_RET_OK; 00547 int16_t i = 0; 00548 PmType_t type; 00549 00550 /* Return if ptr is null or object is already marked */ 00551 if ((pobj == C_NULL) || (OBJ_GET_GCVAL(pobj) == pmHeap.gcval)) 00552 { 00553 return retval; 00554 } 00555 00556 /* The pointer must be within the heap (native frame is special case) */ 00557 C_ASSERT((((uint8_t *)pobj >= &pmHeap.base[0]) 00558 && ((uint8_t *)pobj <= &pmHeap.base[PM_HEAP_SIZE])) 00559 || ((uint8_t *)pobj == (uint8_t *)&gVmGlobal.nativeframe)); 00560 00561 /* The object must not already be free */ 00562 C_ASSERT(OBJ_GET_FREE(pobj) == 0); 00563 00564 type = (PmType_t)OBJ_GET_TYPE(pobj); 00565 switch (type) 00566 { 00567 /* Objects with no references to other objects */ 00568 case OBJ_TYPE_NON: 00569 case OBJ_TYPE_INT: 00570 case OBJ_TYPE_FLT: 00571 case OBJ_TYPE_STR: 00572 case OBJ_TYPE_NOB: 00573 case OBJ_TYPE_BOOL: 00574 case OBJ_TYPE_CIO: 00575 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00576 break; 00577 00578 case OBJ_TYPE_TUP: 00579 i = ((pPmTuple_t)pobj)->length; 00580 00581 /* Mark tuple head */ 00582 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00583 00584 /* Mark each obj in tuple */ 00585 while (--i >= 0) 00586 { 00587 retval = heap_gcMarkObj(((pPmTuple_t)pobj)->val[i]); 00588 PM_RETURN_IF_ERROR(retval); 00589 } 00590 break; 00591 00592 case OBJ_TYPE_LST: 00593 00594 /* Mark the list */ 00595 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00596 00597 /* Mark the seglist */ 00598 retval = heap_gcMarkObj((pPmObj_t)((pPmList_t)pobj)->val); 00599 break; 00600 00601 case OBJ_TYPE_DIC: 00602 /* Mark the dict head */ 00603 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00604 00605 /* Mark the keys seglist */ 00606 retval = heap_gcMarkObj((pPmObj_t)((pPmDict_t)pobj)->d_keys); 00607 PM_RETURN_IF_ERROR(retval); 00608 00609 /* Mark the vals seglist */ 00610 retval = heap_gcMarkObj((pPmObj_t)((pPmDict_t)pobj)->d_vals); 00611 break; 00612 00613 case OBJ_TYPE_COB: 00614 /* Mark the code obj head */ 00615 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00616 00617 /* Mark the names tuple */ 00618 retval = heap_gcMarkObj((pPmObj_t)((pPmCo_t)pobj)->co_names); 00619 PM_RETURN_IF_ERROR(retval); 00620 00621 /* Mark the consts tuple */ 00622 retval = heap_gcMarkObj((pPmObj_t)((pPmCo_t)pobj)->co_consts); 00623 PM_RETURN_IF_ERROR(retval); 00624 00625 /* #122: Mark the code image if it is in RAM */ 00626 if (((pPmCo_t)pobj)->co_memspace == MEMSPACE_RAM) 00627 { 00628 retval = heap_gcMarkObj((pPmObj_t) 00629 (((pPmCo_t)pobj)->co_codeimgaddr)); 00630 } 00631 00632 #ifdef HAVE_CLOSURES 00633 /* #256: Add support for closures */ 00634 /* Mark the cellvars tuple */ 00635 retval = heap_gcMarkObj((pPmObj_t)((pPmCo_t)pobj)->co_cellvars); 00636 #endif /* HAVE_CLOSURES */ 00637 break; 00638 00639 case OBJ_TYPE_MOD: 00640 case OBJ_TYPE_FXN: 00641 /* Module and Func objs are implemented via the PmFunc_t */ 00642 /* Mark the func obj head */ 00643 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00644 00645 /* Mark the code obj */ 00646 retval = heap_gcMarkObj((pPmObj_t)((pPmFunc_t)pobj)->f_co); 00647 PM_RETURN_IF_ERROR(retval); 00648 00649 /* Mark the attr dict */ 00650 retval = heap_gcMarkObj((pPmObj_t)((pPmFunc_t)pobj)->f_attrs); 00651 PM_RETURN_IF_ERROR(retval); 00652 00653 #ifdef HAVE_DEFAULTARGS 00654 /* Mark the default args tuple */ 00655 retval = heap_gcMarkObj((pPmObj_t)((pPmFunc_t)pobj)->f_defaultargs); 00656 #endif /* HAVE_DEFAULTARGS */ 00657 00658 #ifdef HAVE_CLOSURES 00659 /* #256: Mark the closure tuple */ 00660 retval = heap_gcMarkObj((pPmObj_t)((pPmFunc_t)pobj)->f_closure); 00661 #endif /* HAVE_CLOSURES */ 00662 break; 00663 00664 #ifdef HAVE_CLASSES 00665 case OBJ_TYPE_CLI: 00666 /* Mark the obj head */ 00667 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00668 00669 /* Mark the class */ 00670 retval = heap_gcMarkObj((pPmObj_t)((pPmInstance_t)pobj)->cli_class); 00671 PM_RETURN_IF_ERROR(retval); 00672 00673 /* Mark the attrs dict */ 00674 retval = heap_gcMarkObj((pPmObj_t)((pPmInstance_t)pobj)->cli_attrs); 00675 PM_RETURN_IF_ERROR(retval); 00676 break; 00677 00678 case OBJ_TYPE_MTH: 00679 /* Mark the obj head */ 00680 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00681 00682 /* Mark the instance */ 00683 retval = heap_gcMarkObj((pPmObj_t)((pPmMethod_t)pobj)->m_instance); 00684 PM_RETURN_IF_ERROR(retval); 00685 00686 /* Mark the func */ 00687 retval = heap_gcMarkObj((pPmObj_t)((pPmMethod_t)pobj)->m_func); 00688 PM_RETURN_IF_ERROR(retval); 00689 00690 /* Mark the attrs dict */ 00691 retval = heap_gcMarkObj((pPmObj_t)((pPmMethod_t)pobj)->m_attrs); 00692 PM_RETURN_IF_ERROR(retval); 00693 break; 00694 00695 case OBJ_TYPE_CLO: 00696 /* Mark the obj head */ 00697 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00698 00699 /* Mark the attrs dict */ 00700 retval = heap_gcMarkObj((pPmObj_t)((pPmClass_t)pobj)->cl_attrs); 00701 PM_RETURN_IF_ERROR(retval); 00702 00703 /* Mark the base tuple */ 00704 retval = heap_gcMarkObj((pPmObj_t)((pPmClass_t)pobj)->cl_bases); 00705 break; 00706 #endif /* HAVE_CLASSES */ 00707 00708 /* 00709 * An obj in ram should not be of these types. 00710 * Images arrive in RAM as string objects (image is array of bytes) 00711 */ 00712 case OBJ_TYPE_CIM: 00713 case OBJ_TYPE_NIM: 00714 PM_RAISE(retval, PM_RET_EX_SYS); 00715 return retval; 00716 00717 case OBJ_TYPE_FRM: 00718 { 00719 pPmObj_t *ppobj2 = C_NULL; 00720 00721 /* Mark the frame obj head */ 00722 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00723 00724 /* Mark the previous frame */ 00725 retval = heap_gcMarkObj((pPmObj_t)((pPmFrame_t)pobj)->fo_back); 00726 PM_RETURN_IF_ERROR(retval); 00727 00728 /* Mark the fxn obj */ 00729 retval = heap_gcMarkObj((pPmObj_t)((pPmFrame_t)pobj)->fo_func); 00730 PM_RETURN_IF_ERROR(retval); 00731 00732 /* Mark the blockstack */ 00733 retval = heap_gcMarkObj((pPmObj_t) 00734 ((pPmFrame_t)pobj)->fo_blockstack); 00735 PM_RETURN_IF_ERROR(retval); 00736 00737 /* Mark the attrs dict */ 00738 retval = heap_gcMarkObj((pPmObj_t)((pPmFrame_t)pobj)->fo_attrs); 00739 PM_RETURN_IF_ERROR(retval); 00740 00741 /* Mark the globals dict */ 00742 retval = heap_gcMarkObj((pPmObj_t)((pPmFrame_t)pobj)->fo_globals); 00743 PM_RETURN_IF_ERROR(retval); 00744 00745 /* Mark each obj in the locals list and the stack */ 00746 ppobj2 = ((pPmFrame_t)pobj)->fo_locals; 00747 while (ppobj2 < ((pPmFrame_t)pobj)->fo_sp) 00748 { 00749 retval = heap_gcMarkObj(*ppobj2); 00750 PM_RETURN_IF_ERROR(retval); 00751 ppobj2++; 00752 } 00753 break; 00754 } 00755 00756 case OBJ_TYPE_BLK: 00757 /* Mark the block obj head */ 00758 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00759 00760 /* Mark the next block in the stack */ 00761 retval = heap_gcMarkObj((pPmObj_t)((pPmBlock_t)pobj)->next); 00762 break; 00763 00764 case OBJ_TYPE_SEG: 00765 /* Mark the segment obj head */ 00766 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00767 00768 /* Mark each obj in the segment */ 00769 for (i = 0; i < SEGLIST_OBJS_PER_SEG; i++) 00770 { 00771 retval = heap_gcMarkObj(((pSegment_t)pobj)->s_val[i]); 00772 PM_RETURN_IF_ERROR(retval); 00773 } 00774 00775 /* Mark the next segment */ 00776 retval = heap_gcMarkObj((pPmObj_t)((pSegment_t)pobj)->next); 00777 break; 00778 00779 case OBJ_TYPE_SGL: 00780 /* Mark the seglist obj head */ 00781 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00782 00783 /* Mark the root segment */ 00784 retval = heap_gcMarkObj((pPmObj_t)((pSeglist_t)pobj)->sl_rootseg); 00785 break; 00786 00787 case OBJ_TYPE_SQI: 00788 /* Mark the sequence iterator obj head */ 00789 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00790 00791 /* Mark the sequence */ 00792 retval = heap_gcMarkObj(((pPmSeqIter_t)pobj)->si_sequence); 00793 break; 00794 00795 case OBJ_TYPE_THR: 00796 /* Mark the thread obj head */ 00797 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00798 00799 /* Mark the current frame */ 00800 retval = heap_gcMarkObj((pPmObj_t)((pPmThread_t)pobj)->pframe); 00801 break; 00802 00803 case OBJ_TYPE_NFM: 00804 /* 00805 * Mark the obj desc. This doesn't really do much since the 00806 * native frame is declared static (not from the heap), but this 00807 * is here in case that ever changes 00808 */ 00809 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00810 00811 /* Mark the native frame's remaining fields if active */ 00812 if (gVmGlobal.nativeframe.nf_active) 00813 { 00814 /* Mark the frame stack */ 00815 retval = heap_gcMarkObj((pPmObj_t) 00816 gVmGlobal.nativeframe.nf_back); 00817 PM_RETURN_IF_ERROR(retval); 00818 00819 /* Mark the function object */ 00820 retval = heap_gcMarkObj((pPmObj_t) 00821 gVmGlobal.nativeframe.nf_func); 00822 PM_RETURN_IF_ERROR(retval); 00823 00824 /* Mark the stack object */ 00825 retval = heap_gcMarkObj(gVmGlobal.nativeframe.nf_stack); 00826 PM_RETURN_IF_ERROR(retval); 00827 00828 /* Mark the args to the native func */ 00829 for (i = 0; i < NATIVE_GET_NUM_ARGS(); i++) 00830 { 00831 retval = 00832 heap_gcMarkObj(gVmGlobal.nativeframe.nf_locals[i]); 00833 PM_RETURN_IF_ERROR(retval); 00834 } 00835 } 00836 break; 00837 00838 #ifdef HAVE_BYTEARRAY 00839 case OBJ_TYPE_BYA: 00840 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00841 00842 retval = heap_gcMarkObj((pPmObj_t)((pPmBytearray_t)pobj)->val); 00843 break; 00844 00845 case OBJ_TYPE_BYS: 00846 OBJ_SET_GCVAL(pobj, pmHeap.gcval); 00847 break; 00848 #endif /* HAVE_BYTEARRAY */ 00849 00850 default: 00851 /* There should be no invalid types */ 00852 PM_RAISE(retval, PM_RET_EX_SYS); 00853 break; 00854 } 00855 return retval; 00856 } 00857 00858 00859 /* 00860 * Marks the root objects so they won't be collected during the sweep phase. 00861 * Recursively marks all objects reachable from the roots. 00862 */ 00863 static PmReturn_t 00864 heap_gcMarkRoots(void) 00865 { 00866 PmReturn_t retval; 00867 00868 /* Toggle the GC marking value so it differs from the last run */ 00869 pmHeap.gcval ^= 1; 00870 00871 /* Mark the constant objects */ 00872 retval = heap_gcMarkObj(PM_NONE); 00873 PM_RETURN_IF_ERROR(retval); 00874 retval = heap_gcMarkObj(PM_FALSE); 00875 PM_RETURN_IF_ERROR(retval); 00876 retval = heap_gcMarkObj(PM_TRUE); 00877 PM_RETURN_IF_ERROR(retval); 00878 retval = heap_gcMarkObj(PM_ZERO); 00879 PM_RETURN_IF_ERROR(retval); 00880 retval = heap_gcMarkObj(PM_ONE); 00881 PM_RETURN_IF_ERROR(retval); 00882 retval = heap_gcMarkObj(PM_NEGONE); 00883 PM_RETURN_IF_ERROR(retval); 00884 retval = heap_gcMarkObj(PM_CODE_STR); 00885 PM_RETURN_IF_ERROR(retval); 00886 00887 /* Mark the builtins dict */ 00888 retval = heap_gcMarkObj(PM_PBUILTINS); 00889 PM_RETURN_IF_ERROR(retval); 00890 00891 /* Mark the native frame if it is active */ 00892 retval = heap_gcMarkObj((pPmObj_t)&gVmGlobal.nativeframe); 00893 PM_RETURN_IF_ERROR(retval); 00894 00895 /* Mark the thread list */ 00896 retval = heap_gcMarkObj((pPmObj_t)gVmGlobal.threadList); 00897 00898 return retval; 00899 } 00900 00901 00902 #if USE_STRING_CACHE 00903 /** 00904 * Unlinks free objects from the string cache. 00905 * This function must only be called by the GC after the heap has been marked 00906 * and before the heap has been swept. 00907 * 00908 * This solves the problem where a string object would be collected 00909 * but its chunk was still linked into the free list 00910 * 00911 * @param gcval The current value for chunks marked by the GC 00912 */ 00913 static PmReturn_t 00914 heap_purgeStringCache(uint8_t gcval) 00915 { 00916 PmReturn_t retval; 00917 pPmString_t *ppstrcache; 00918 pPmString_t pstr; 00919 00920 /* Update string cache pointer if the first string objs are not marked */ 00921 retval = string_getCache(&ppstrcache); 00922 if (ppstrcache == C_NULL) 00923 { 00924 return retval; 00925 } 00926 while ((*ppstrcache != C_NULL) && (OBJ_GET_GCVAL(*ppstrcache) != gcval)) 00927 { 00928 *ppstrcache = (*ppstrcache)->next; 00929 } 00930 if (*ppstrcache == C_NULL) 00931 { 00932 return retval; 00933 } 00934 00935 /* Unlink remaining strings that are not marked */ 00936 for (pstr = *ppstrcache; pstr->next != C_NULL;) 00937 { 00938 /* Unlink consecutive non-marked strings */ 00939 while ((pstr->next != C_NULL) && (OBJ_GET_GCVAL(pstr->next) != gcval)) 00940 { 00941 pstr->next = pstr->next->next; 00942 } 00943 00944 /* If not at end of cache, string must be marked, skip it */ 00945 if (pstr->next != C_NULL) 00946 { 00947 pstr = pstr->next; 00948 } 00949 } 00950 00951 return retval; 00952 } 00953 #endif 00954 00955 00956 /* 00957 * Reclaims any object that does not have a current mark. 00958 * Puts it in the free list. Coalesces all contiguous free chunks. 00959 */ 00960 static PmReturn_t 00961 heap_gcSweep(void) 00962 { 00963 PmReturn_t retval; 00964 pPmObj_t pobj; 00965 pPmHeapDesc_t pchunk; 00966 uint16_t totalchunksize; 00967 00968 #if USE_STRING_CACHE 00969 retval = heap_purgeStringCache(pmHeap.gcval); 00970 #endif 00971 00972 /* Start at the base of the heap */ 00973 pobj = (pPmObj_t)pmHeap.base; 00974 while ((uint8_t *)pobj < &pmHeap.base[PM_HEAP_SIZE]) 00975 { 00976 /* Skip to the next unmarked or free chunk within the heap */ 00977 while (!OBJ_GET_FREE(pobj) 00978 && (OBJ_GET_GCVAL(pobj) == pmHeap.gcval) 00979 && ((uint8_t *)pobj < &pmHeap.base[PM_HEAP_SIZE])) 00980 { 00981 pobj = (pPmObj_t)((uint8_t *)pobj + OBJ_GET_SIZE(pobj)); 00982 } 00983 00984 /* Stop if reached the end of the heap */ 00985 if ((uint8_t *)pobj >= &pmHeap.base[PM_HEAP_SIZE]) 00986 { 00987 break; 00988 } 00989 00990 /* Accumulate the sizes of all consecutive unmarked or free chunks */ 00991 totalchunksize = 0; 00992 00993 /* Coalesce all contiguous free chunks */ 00994 pchunk = (pPmHeapDesc_t)pobj; 00995 while (OBJ_GET_FREE(pchunk) 00996 || (!OBJ_GET_FREE(pchunk) 00997 && (OBJ_GET_GCVAL(pchunk) != pmHeap.gcval))) 00998 { 00999 if ((totalchunksize + OBJ_GET_SIZE(pchunk)) 01000 > HEAP_MAX_FREE_CHUNK_SIZE) 01001 { 01002 break; 01003 } 01004 totalchunksize = totalchunksize + OBJ_GET_SIZE(pchunk); 01005 01006 /* 01007 * If the chunk is already free, unlink it because its size 01008 * is about to change 01009 */ 01010 if (OBJ_GET_FREE(pchunk)) 01011 { 01012 retval = heap_unlinkFromFreelist(pchunk); 01013 PM_RETURN_IF_ERROR(retval); 01014 } 01015 01016 /* Otherwise free and reclaim the unmarked chunk */ 01017 else 01018 { 01019 OBJ_SET_TYPE(pchunk, 0); 01020 OBJ_SET_FREE(pchunk, 1); 01021 } 01022 01023 C_DEBUG_PRINT(VERBOSITY_HIGH, "heap_gcSweep(), id=%p, s=%d\n", 01024 pchunk, OBJ_GET_SIZE(pchunk)); 01025 01026 /* Proceed to the next chunk */ 01027 pchunk = (pPmHeapDesc_t) 01028 ((uint8_t *)pchunk + OBJ_GET_SIZE(pchunk)); 01029 01030 /* Stop if it's past the end of the heap */ 01031 if ((uint8_t *)pchunk >= &pmHeap.base[PM_HEAP_SIZE]) 01032 { 01033 break; 01034 } 01035 } 01036 01037 /* Set the heap descriptor data */ 01038 OBJ_SET_FREE(pobj, 1); 01039 OBJ_SET_SIZE(pobj, totalchunksize); 01040 01041 /* Insert chunk into free list */ 01042 retval = heap_linkToFreelist((pPmHeapDesc_t)pobj); 01043 PM_RETURN_IF_ERROR(retval); 01044 01045 /* Continue to the next chunk */ 01046 pobj = (pPmObj_t)pchunk; 01047 } 01048 01049 return PM_RET_OK; 01050 } 01051 01052 01053 /* Runs the mark-sweep garbage collector */ 01054 PmReturn_t 01055 heap_gcRun(void) 01056 { 01057 PmReturn_t retval; 01058 01059 C_DEBUG_PRINT(VERBOSITY_LOW, "heap_gcRun()\n"); 01060 /*heap_dump();*/ 01061 01062 retval = heap_gcMarkRoots(); 01063 PM_RETURN_IF_ERROR(retval); 01064 01065 retval = heap_gcSweep(); 01066 /*heap_dump();*/ 01067 return retval; 01068 } 01069 01070 01071 /* Enables or disables automatic garbage collection */ 01072 PmReturn_t 01073 heap_gcSetAuto(uint8_t auto_gc) 01074 { 01075 pmHeap.auto_gc = auto_gc; 01076 return PM_RET_OK; 01077 } 01078 #endif /* HAVE_GC */
Generated on Tue Jul 12 2022 17:07:01 by
1.7.2