heap.c

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 */