Method and system for incremental stack scanning

[0001] This application for U.S. patent is a non-provisional conversion of U.S. provisional application for patent Serial No. 60/200,142 filed Apr. 27, 2000.

[0003] This invention relates to a method for automatic memory management known as garbage collection. More specifically, this invention relates to improvements in incremental garbage collection most useful for object-oriented program-controlled systems with real-time constraints.

[0004] Briefly, garbage collection, the automatic recycling of dynamically allocated memory, is a tried and tested memory management technique that has been in use since its invention by John McCarthy in 1958 as part of the implementation of Lisp. Garbage collection avoids the need for the programmer to deallocate memory blocks explicitly, thus avoiding a number of problems, including memory leaks, double frees, and premature frees. The burden on the programmer is reduced by not having to investigate such problems, thereby increasing productivity, and dramatically simplifying programs by allowing modules to present cleaner interfaces to each other. The use of garbage collectors in automatic memory management is well known in the prior art, and detailed descriptions of the art appear in U.S. Pat. No. 6,055,612 and other sources cited in this disclosure, and incorporated by reference herein. The reader is assumed to be one of skill in the art and familiar with the terms common to the art.

[0005] Nevertheless, many garbage collectors stop all other activity in the system for a significant, unpredictable duration of time while the garbage collector is running, which makes these systems unsuitable for systems with real-time constraints. In response to such limitations in standard garbage collectors, a number of incremental garbage collectors have been proposed and developed which avoid the stop-and-collect procedure of traditional garbage collectors. However, the incremental garbage collections developed to date have not fully met the needs of a hard real-time system.

[0006] Many existing incremental garbage collectors require some unpredictable and possibly large atomic operation either at the start of a collection cycle or as part of the completion of the mark phase. For example, the garbage collector described in Taiichi Yuasa, Real-Time Garbage Collection on General Purpose Machines, Journal of Software & Systems, 11(3):181-198 (1990), copies the entire program stack at the start of a collection cycle, and incrementally scans that copy. The garbage collector disclosed in Mark Stuart Johnstone, Non-Compacting Memory Allocation and Real-Time Garbage Collection, Ph.D. thesis, U. of Texas at Austin (December 1997), treats all stacks as part of the root set to be scanned in an atomic operation at the start of each collection cycle. While these solutions lead to some efficiency gains, both suffer from an unpredictable and possibly large startup pause.

[0007] Likewise, the garbage collector disclosed in Tian F. Lim et al., A Memory-Efficient Real-Time Non-Copying Garbage Collector, Conference Proceedings of the International Symposium on Memory Management, Vancouver, Canada (October 1998), scans stacks at the end of a collection cycle, scanning all stacks and then reinitiating the mark phase for objects shaded grey during the stack scan. (For purposes of additional clarity in this disclosure, the tri-color marking scheme is used in which during the mark phase of the collector, objects are partitioned into three sets. Black objects have been noted as reachable and have had their contained references scanned. Grey objects have also been noted as reachable but their contents have not yet been scanned. White objects have not yet been noted as reachable and might be reclaimed. To mark an object, the method of system examines its color, and if it is white, transfer it to the grey set. Grey objects are transferred to the black set when they are scanned.) Lim et al. make this process incremental by limiting the amount of stack scanning that will be performed and rescanning those stacks that were reactivated after an preempted increment of stack scanning. This solution presents two limitations: first, the granularity of this operation is relatively coarse, and second, a high rate of stack reactivation could significantly delay the completion of this process, possibly indefinitely.

[0008] Finally, Thierry Le Sargent & Bernard Barthomieu, Incremental Multi-Threaded Garbage Collection on Virtually Shared Memory Architectures, in Proceedings of International Workshop on Memory Management, St. Malo, France (September 1992), propose the use of virtual memory support to perform incremental stack scanning. In their proposed collector, the top page of each stack is treated as part of the root set and scanned at the start of the collection cycle, while other pages of the stack are made inaccessible. An attempt to access an inaccessible stack page is trapped by the virtual memory system, and the page is scanned at that time. The incremental scanner then scans stack pages that have not otherwise been scanned. This approach requires that essentially arbitrary chunks of the stack (or individual pages) can be scanned with little or no information available about their content, which imposes possibly significant restrictions on what the mutator can store on the stack and in what format.

[0009] Therefore, while many incremental garbage collectorsincluding those discussed aboveare described as real-time, for the reasons discussed their performance cannot meet the needs of certain real-time applications. For these systems, results must be on time, and a late result is as useless as an incorrectly calculated one. Therefore, there remains the need for an improved garbage collector able to satisfactorily meet the needs of a system requiring real-time operation.

[0010] The object of the invention is attained by modifying an incremental garbage collector so that the stack scan can be performed incrementally in units of individual stack locations without having to rescan any stack when the garbage collector is preempted by the system to perform real-time operations.

[0011] In the present invention, the stack is scanned by dividing it into call frames, and by using continuation replacement to notify the collector that the mutator has modified a frame being processed by the collector. In one embodiment, a stack is scanned in push order, from the base of the stack toward the top of the stack.

[0012] In the preferred embodiment, when starting the scan of a call frame, the continuation for reactivating that call frame is replaced with an unwind routine which is used to detect reactivation of that frame. The scan of the stack is made incremental by recording at each step the call frame being processed and the progress made so far in processing it. This allows the stack scanner to perform some small increment of work and then return, resuming where it left off when next invoked. An increment of work in this process can be as little as scanning one stack location.

[0013] It is a further object of the preferred embodiment of the present invention that when the stack scanner reaches the last call frame for a stack, there are two cases to be considered. If the stack being scanned is not the current stack, then proceed as for any other call frame. Otherwise, when the stack being scanned is the current stack, the call frame should be treated as if it were partially scanned and then reactivated; that is, it should be processed in the same manner as would be done by the unwind routine.

[0014] It is also an object of the invention to integrate the incremental scan of the stacks into the mark phase of a collector.

[0015] Finally, although the method and system described herein were developed as part of a Treadmill collector, it does not rely on details of that collector. This method can be applied to, for example, a Mark and Sweep collector, an indirection-based collector, or a replicating collector known to one of skill in the art.

[0016] FIG. 1 is a flow diagram depicting an overview of the incremental garbage collector;

[0017] FIG. 2 is a flow diagram of the outer-loop of the preferred embodiment of the present invention;

[0018] FIGS. 3A and 3B are flow diagrams of the inner-loop of the preferred embodiment of the present invention;

[0019] FIG. 4 is a flow diagram of the unwind routine used in the preferred embodiment of the present invention; and

[0020] FIG. 5 contains exemplary code for implementing the unwind routine.

[0021] In addition, the exemplary code for implementing the preferred embodiment of the present invention is attached in Appendix A. Page and line numbers have been added to the code for reference purposes and are referred to within this disclosure.

[0022] For purposes of providing a detailed description of a preferred embodiment, this discussion focuses on an implementation of the present invention as an improvement on a prior art treadmill collector for use with an implementation of L, a Common Lisp dialect designed for embedded real-time robot control systems. One of skill in the art will recognize that the invention is not limited to just this particular type of garbage collector or programming language. Additional details on the treadmill collector of the preferred embodiment can be found in Henry Baker, The Treadmill, Real-Time Garbage Collection Without Motion Sickness, ACM SIGPLAN Notices, 27(3), March 1992. Additional details on the specific implementation of L can be found in Rodney A. Brooks & Charles Rosenberg, LA Common Lisp for Embedded Systems, Association of Lisp Users Meeting and Workshop LUV '95, August 1995.

[0023] The treadmill collector used in the preferred embodiment is broadly similar to those described in: (a) Paul R. Wilson & Mark S. Johnstone, Truly Real-Time Non-Copying Garbage Collection, which is discussed in Elliot Moss, Paul R. Wilson & Benjamin Zorn, editors. OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, October 1993; (b) Mark Stuart Johnstone, Non-Compacting Memory Allocation and Real-Time Garbage Collection Ph.D. thesis, University of Texas at Austin, December 1997; and (c) Tian F. Lim, Przemyslaw Pardyak, and Brian N. Bershad, A Memory-Efficient Real-Time Non-Copying Garbage Collector, Conference Proceedings of the International Symposium on Memory Management, Vancouver, Canada, October 1998 (ACM Press) pp. 118-129. While these references are not necessary for the understanding of the present invention, each is hereby incorporated by reference herein.

[0024] The treadmill of the preferred embodiment uses a segregated storage strategy, having multiple treadmills for different sizes of objects. It uses tri-color marking with a write barrier to maintain coherence between the collector and the mutator. While various embodiments of the present invention can be configured to use various write barriers, including either an incremental update or a snapshot at the beginning write barrier, the preferred embodiment uses a snapshot at the beginning write barrier and is discussed in detail below.

[0025] As depicted in FIG. 1, the incremental collector of the present invention proceeds in stages (steps 110-150), with each stage being incremental. Certain stages are performed exactly once per collection cycle, while others might be transitioned back to by a later stage.

[0026] In the preferred embodiment, the current stage is encoded in the value of a variable containing a pointer to the routine for performing whatever processing is to be done during the current stage. This routine is called with one argument, which is a step request count. The step request count is the number of work units the current incremental step is to perform before allowing the caller to resume. In a preferred embodiment, the amount of work units to perform is based on the system's allocation needs and therefore maintains an appropriate level of garbage collection with each allocation. Each stage has some auxiliary variables used to maintain state from one invocation of the stepper routine to the next, as necessary to record the incremental progress of that stage of the collector. This allows the method and system of the present invention to resume the collection without duplicating effort.

[0027] As shown in FIG. 1, the stages are: (1) scan initialization 110, (2) scan stacks 120, (3) scan permanent objects and global variables 130, (4) scan objects in the mark chain until mark chain is empty 140, and (5) flip the collector 150 (garbage reclamation), preparing for the next collection cycle. In the specific implementation attached in Appendix A, the scan of permanent objects and global variables occurs in sub-stages: scanning the sysquant area, scanning the permanent scanned cons cells and scanning the permanent scanned headered objects. Each stage will be discussed sequentially in the order it appears in the preferred embodiment. Because the improvements in the garbage collector are within the stack scan 120, only a brief description of the other stages, along with exemplary code, is provided as needed to practice the preferred embodiment of the invention.

[0028] As an initial matter, in the implementation disclosed in Appendix A, the transition from one incremental step routine to the next is table driven, so that any individual step routine need not be aware of the routine or routines to which it can transition. (Appendix A, from page 1, line 18 to page 2, line 56, includes exemplary code used in the preferred embodiment for controlling the transitions between the various stages.) The particular order in which the stages are called may depend on the particulars of the implementation of the present invention, including the choice of write barriers, discussed below. In other embodiments, the stages can be coded directly (as opposed to table driven) for the sake of additional efficiency.

[0029] Stage 1Scan Initialization

[0030] The scan initialization 110 is performed at system startup and at the end of each collection cycle in preparation for starting the next cycle. The initialization stage ensures that while stack scanning in Stage 2 (step 120) is in progress, all new allocations are colored grey (115). Once the stack scan (step 120) is complete, all new allocations are set to black (125).

[0031] Stage 2Stack Scan

[0032] The stack scan is herein first discussed with reference to the incremental stack scan algorithm itself, then discussed with reference to particulars of the preferred embodiment. The stack scan 120 of the preferred embodiment is presented in more detail in the flow diagrams in FIGS. 2, 3A, 3B and 4.

[0033] In the present invention, a stack is scanned by dividing it into call frames and by using continuation replacement to notify the collector that the mutator has modified a frame being processed by the collector. A stack is scanned in push order, from the base of the stack toward the top of the stack. While scanning a stack in the other direction, from the top toward the base, is possible, doing so is more complex and may result in significant wasted effort if the mutator happens to frequently reactivate call frames as the collector is processing them.

[0034] The stack scanner of the preferred embodiment must be able to parse the stack into call frames. In particular, the scanner must be able to determine the boundaries of call frames, the locations within each call frame that must be scanned, and the location of the continuation that will be invoked to reactivate the call frame.

[0035] When starting the scan of a call frame, the continuation for reactivating that call frame is saved, then replaced with an unwind routine, as described below, which is used to detect reactivation of that frame. The scan of the stack is made incremental by recording at each step the call frame being processed and the progress made so far in processing it. This allows the stack scanner to perform some small increment of work and then return, resuming where it left off when next invoked. Importantly, an increment of work in this process could be as little as scanning one stack location.

[0036] FIG. 2 depicts an outer-loop 200 for the preferred embodiment of the incremental stack scan. The purpose of the outer-loop is to cycle through each stack, and if the stack is live, scan the stack. Therefore, the system keeps track of whether the stacks have been completed (in a completed stack list) or remain pending (in a pending stack list). Stacks created during a cycle are placed on the completed list. The first step 210 of the preferred method looks to whether the pending stack list is empty. If the pending stack list is empty, then the list of completed stacks is copied to the pending stack list (step 220) and the completed stack list is erased (step 230) in preparation for the next cycle, the garbage collector can then proceed to Stage 3 (step 130). With the use of an incremental write barrier, after all stacks have been completely scanned, the collector determines whether any of stacks need to be rescanned during the current collection cycle.

[0037] If the pending stack list is not empty (step 210), a stack is selected to scan (step 240), and the stack is removed from the pending stack list (step 240). The system then determines whether the selected stack has any contents, i.e. whether that particular stack is in active use (step 250). If the stack does not have any contents, the system goes back to the pending stack list (step 210) to look for any remaining stacks for scanning. If the stack has contents, the stack is added to the completed stack list (step 260) and the stack is scanned (step 270). Once a stack has been completely scanned, the stack scanner can proceed on to the next stack, until all stacks have been processed. The process of scanning the selected stack is detailed in an inner-loop, shown in FIGS. 3A and 3B. Appendix A, from page 7, line 33 to page 8, line 36, includes exemplary code for implementing the outer-loop of the preferred embodiment.

[0038] The inner-loop 300 of the stack scan is shown in FIGS. 3A and 3B. The first step (step 310) looks to see if the scan pointer for the particular stack selected for scanning in step 240 has been changed. A change in the scan pointer could represent either that the stack was deleted or that the frame being scanned had been reactivated. If the frame had been reactivated, the scan of that stack would have already been completed. If the stack is no longer in use, the deletion operation alters the stack pointer so that the collector will avoid an unnecessary scan. In either case, the scan pointer has been changed and the system in step 320 returns to the outer-loop 200 to select another stack, if any, for processing.

[0039] If it is determined that the scan point has not been changed (step 310), the system will continue to scan the current frame (step 330) until one of three events occur: (a) the scan request is complete (step 340), (b) the frame is completely scanned (step 350) or (c) the system receives a preemption request (step 360). The results from each of these events is discussed below.

[0040] Once the scan request is complete (step 340), by having completed the work request by the incremental scan request (i.e. the step request count, as discussed above), the scan pointer representing the progress for the particular scan is recorded (step 344) and the stage 120 is exited (step 348) sending the system to exit this incremental step of the garbage collector.

[0041] If a preemption request is received (step 360), the system is being called away from its current garbage collection activity to perform a specific task. The ability of the system to accept a preemption request (step 360) allows this incremental stack scanner to perform garbage collection in systems requiring real-time operations. Where a preemption request has been received (step 360), the current scan pointer is recorded (step 364) and the system is released to perform the requested task. When the task is complete, the system will invoke the current incremental step routine, which may have changed during the preemption, with the request residuethe remainder of the request at the point of preemption.

[0042] The last condition for the cessation for the scanning of the frame (step 330) is if the frame has been completely scanned (step 350). If the frame has been completely scanned, the system must then determine whether there are additional frames in the current stack (step 354). If there are not additional frames in the current stack, the continuation which was previously stored is restored (step 355) and the system returns to the outer-loop 200 to select another stack, if any, for processing.

[0043] FIG. 3B contains a detailed flow diagram 400 of the method of the preferred embodiment where the system in step 354 determines that there are additional frames in the current stack. Where there are additional frames in the current stack, the system first sets the scan pointer to the start of the next frame (step 410), where the next frame is the frame pushed immediately after the current frame. That next frame becomes the current frame. Unless the frame is the first frame (special case for start of scan), the continuation that was previously saved is restored (step 430). The first frame has no continuation.

[0044] The system then determines if the current frame is the last frame (step 440) and/or whether the stack being scanned is the currently executing stack (step 450). There are three possibilities for the current frame: (a) the current frame is not the last frame (steps 442, 444 & 446), (b) the current frame is the last frame but not the currently executing stack (steps 452, 454 & 456), or (c) the current frame is the last frame of the currently executing stack (step 460). The steps necessary for handling each of these cases are discussed below.

[0045] If the current frame is not the last frame, the system gets the size of the frame (step 442), saves the continuation of the next frame (step 444), then sets the continuation of the next frame to the unwind routine (step 446). In the preferred embodiment, the size of the frame is obtained from the header created when the frame is initialized. The system, in this case, then loops back to continue scanning the frame (step 330).

[0046] When the stack scanner reaches the last call frame for a stack, there are two cases to be considered. If the stack being scanned is not the currently executing stack, then proceed as for any other call frame, except that the continuation to save is found in the stack header, along with the stack pointer which is used to determine the size of the framethere is no next frame in this case. Otherwise, when the stack being scanned is the currently executing stack, the call frame should be treated as if it were partially scanned and then reactivated. That is, it should be processed in the same manner as would be done by the unwind routine.

[0047] With reference to FIG. 3B, if the current frame is the last frame but not the currently executing stack, the system records the continuation found in the stack header (step 452), sets the continuation to the unwind routine (step 454), gets the size of the frame from the stack pointer (step 456), which was saved in the stack header, and then loops back to continue scanning the frame (step 330).

[0048] If the current frame is the last frame of the currently executing stack, the step 460 implemented in the system or method can take one of the following paths. As optimization incorporated into the preferred embodiment, the system simply ignores this frame because it is known that there are no values in the frame of interest to the collector and nothing need be marked. In that case, the scan pointer need not be modified and system returns to the outer-loop 200 to select another stack, if any, for processing. In the alternative, if the system requires scanning of the final frame, it is treated in the same manner as the unwind routine.

[0049] The unwind routine which replaces a call frame's continuation serves multiple purposes. First, by completing the scan of the frame being reentered, the unwind routine ensures that the stack has passed through the completely scanned state. The unwind routine by changing the scan pointer informs the stack scanner (step 310) that the scan of the frame has been completed. Second, with an incremental write barrier, the unwind routine informs the stack scanner that some of the scanner's forward progress has been undone by function call return by backing up the scan pointer to exclude the call frame being reentered. The unwind routine then resumes execution in the reentered frame by invoking the saved continuation it replaced. Non-local exits must perform similar processing if the resumption point is within a call frame that the scanner has at least started to process.

[0050] FIG. 4 shows a flow diagram of the preferred embodiment of the unwind routine 500. The unwinding routine 500 is executed in the context of the call frame being continued (returned to), which has become the current call frame. Therefore, first, the unwind routine gets the scan pointer for the current stack (step 510). The unwinding routine 500 then scans any unscanned portion of the current call frame and marks any values returned to the current call frame (step 520). In the preferred embodiment, this completes the scanning of the current stack. Subsequent to the completion of the scan (step 520), the unwind routine updates the scan pointer for the stack to indicate that the frame has been activated (step 540). This will trip the condition in the inner-loop (step 310) to inform the system that the scan of the stack had been completed. Finally, the unwind routine 500 recovers the real continuation for the current call frame and goes to that location (step 550). Exemplary code implementing the unwind routine is shown in FIG. 5.

[0051] The process of completing the scan (step 520) of the reentered call frame involves marking values in the unscanned part of the stack and additionally marking any related state, such as machine registers and values returned to the reentered frame by the callee. Performing this scan could make the mutator latency introduced by the unwind routine fairly large, particularly if the scan is performed in place. However, this mutator latency can be substantially reduced by instead copying all of the values to be marked to a separate scan buffer, for later processing by the stack scanner.

[0052] The mutator latency introduced by this scan completion (step 520) is bounded by the maximum call frame size for the application. In other embodiments, a compiler could report call frame sizes greater than some threshold, or could automatically split functions that exceeded that threshold, in order to keep this latency within some application-specific limit.

[0053] In still other embodiments, it is also possible to elide the scan of the reentered call frame entirely, with the idea being to leave the completion of the scan to the normal operation of the stack scanner or to defer it to some other call frame earlier in the stack. However, care must be taken to ensure that doing so does not prevent the stack scanner from making forward progress and reaching eventual termination. Such a failure can occur if the collector repeatedly begins the scan of a frame, only to have that frame reactivated by the mutator. This approach is probably only appropriate when performing short duration, high priority tasks that have tight real-time performance requirements. To use this technique, the mutator must be guaranteed to exit such a deferred scan completion context before too much allocation is performed.

[0054] Irrespective of the techniques selected for optimizing the scan completion of the frame, in the preferred embodiment, the scan (step 520) itself can be preempted by recording its state and installing an appropriate unwind routine for use upon reactivation of the frame.

[0055] As described above, the incremental scan of the stacks is integrated into the mark phase of the collector. How this should be done depends on the choice of write barrier used by the mutator. The choice of write barrier (which in the preferred embodiment is a snapshot at the beginning write barrier), in combination with incremental stack scanning, leads to interactions with the compiler and runtime model for the system. In order to minimize the performance impact of incremental stack scanning on the mutator while ensuring correct behavior of the collector, the compiler must selectively insert barrier operations when generating memory accesses.

[0056] For the purposes of this disclosure, the mutator memory access is divided into the following categories with the associated interactions: first, when reading from or writing into the current call frame, no additional action is needed; second, when reading from a stack location not in the current stack, the value read should be marked; third, when writing to a stack location not in the current call frame, the value written should be marked; fourth, when performing an object initialization write, the value written should be marked when using an incremental write barrier; fifth, when writing into a scanned location, apply the specified write barrier; and finally, for all other memory accesses, no additional action is needed. The key point is the collector imposes no additional overhead on the mutator's access to the current call frame.

[0057] The fundamental problem for combining a snapshot at the beginning write barrier with incremental stack scanning is that the implicit elimination of references by stack unwinding can lead to violations of the weak tri-color invariant that the write barrier is attempting to maintain. In the present invention, when the scan of a stack completes, all objects directly referenced by the stack have been marked. Further, any additional objects to which the stack later gains reference must either be non-white or be accessible from some not yet scanned location, and in the latter case the write barrier will ensure that the object will eventually be marked. Thus, once a stack has been completely scanned, no further processing of the stack is needed during the current collection cycle.

[0058] For example, consider the possible sources of values on a stack after it has been scanned. First, if an object was already present on the stack when the scan started, then it has been marked by the process of scanning the stack. In fact, during the incremental scan of a stack, the scanned part of the stack is protected from becoming the sole reference to a white object by the barrier for storing into a stack location not in the current call frame. Second, if an object is read from some other stack, the barrier for reading from a stack location not in the current call frame will have ensured that it was marked when read. Third, if an object is newly created, it will have been allocated grey or black. Fourth, if an object was written from some other stack, the barrier for storing into a stack location not in the current call frame will have ensured that it was marked when written. Fifth, and finally, if an object was read from some scanned location not previously mentioned, the scanner and the write barrier conspire to ensure that it will be marked.

[0059] As a result, in the preferred embodiment when using a snapshot at the beginning write barrier, the mark phase should proceeds as follows:

[0060] Mark Phase

[0061] Ensure Allocation Color is Grey

[0062] Scan Stacks

[0063] Ensure Allocation Color is Black

[0064] Scan Roots

[0065] Scan Grey

[0066] end Mark Phase

[0067] As shown in FIG. 4, the unwind routine must complete the partial scan of the call frame being reentered. It then records the stack as completely scanned, recovers the real continuation, and invokes it. As the stack scanner completes the scan of a call frame, it recovers the continuation for the just completed frame and reinstalls the continuation (step 550) over the unwind routine before saving the continuation for the next frame and replacing that next continuation with the unwind routine.

[0068] One final consideration is necessary in implementing the incremental stack scanner of the present invention. Incremental stack scanning leads to a requirement that whenever a value is read from or written to a stack location outside the current call frame, the value read or written must be marked. This leads to two problematic situations when allocating on the stack an object having fields that can contain collectable objects.

[0069] 1. Suppose stack S₁ contains a stack allocated object O, O has not yet been scanned, and O contains the sole reference to a heap allocated object W. Now suppose stack S₂, which has been scanned, is active, and the mutator reads W from O into the mutator's current call frame. If the reference to W from O is then deleted before the scan of S₁ reaches O, by unwinding S₁ sufficiently to deallocate O, then W is now live because it is referenced from S₂, but might not get marked because S₂ has already been scanned.

[0070] 2. When using a snapshot at the beginning write barrier, suppose stack S contains a stack allocated object O, and the scan of S has passed through O. Further, suppose that the unscanned part of S contains the sole reference to a heap allocated object W. Now suppose that the original reference to W is in the mutator's current call frame, and that the mutator writes W into O. If the original reference to W is eliminated (either by an unwind of S or by overwriting the reference by the mutator while it is in the mutator's current call frame), then W is now live because it is referenced from O, but might not get marked because O has already been scanned.

[0071] These problems have significant implications for stack allocated objects, since the barriers needed to avoid them would not normally be present when performing a read from or write to an object.

[0072] The simplest solution to these problems is to simply disallow stack allocation of objects having fields that can contain collectable objects. Similarly, the first problem can be evaded by simply disallowing a stack allocated object to be referenced from some other stack. However, this latter solution may be an unacceptable solution in some languages or implementations.

[0073] An alternative solution is to allow stack allocation of such objects when the compiler can identify all accesses to the object and treat them specially, inserting the appropriate barriers. This is in fact a subset of the escape analysis performed by some implementations in order to perform compiler-directed stack allocation. However, this is a stronger limitation than might be imposed by such implementations, and this solution also requires such analysis, which might not already be present for other reasons in some language implementations, and might not be trivial to add.

[0074] When using a snapshot at the beginning write barrier, the first problem, above, can be solved by ensuring that a stack allocated object has been scanned before deleting the object by unwinding the stack. However, this solution may introduce a large and difficult to predict mutator overhead when unwinding the stack.

[0075] The second problem can be solved by deferring the scanning of stack allocated objects until after the stacks themselves have been scanned; that is, exclude the space used for stack allocated objects from the containing call frames when performing the stack scan and instead scan stack allocated objects in an additional later phase. Yet another. .

[0076] Stage 3Scan of Permanent Objects

[0077] In the preferred embodiment, the step of scanning the permanent objects 130 is performed in three sub-stages: scanning the sysquant area, scanning the permanent scanned cons cells and scanning the permanent scanned headered objects. Exemplary code for performing each of the three sub-stages is shown in Appendix A, from page 2, line 58 to page 5, line 26. These stages are known in the art and are included solely to illustrate the preferred embodiment of the present invention.

[0078] Stage 4Scan Marked Objects

[0079] The processing performed by Stage 4scan marked objects (step 140)is also known in the art. Appendix A, from page 5, line 33 to page 6, line 55, includes exemplary code used in the preferred embodiment for scanning objects in the mark chain.

[0080] Stage 5Flip the Collector

[0081] In the final stageflipping the collector 150the garbage collector reclaims all objects that were not reachable by returning them to free memory. This process is well-known in the art and is not discussed in detail herein. Appendix A, from page 12 to page 16 contains exemplary code for this stage.

[0082] It will be appreciated by those skilled in the art that the present invention may be practiced in connection with details that differ from the specific examples of implementation set forth herein, and can be implemented in devices, systems and methods differing from those shown. Thus, the details set forth herein are provided by way of illustration rather than limitation, and the invention is limited only by the scope of the appended claims. each of the three sub-stages is shown in Appendix A, from page 2, line 58 to page 5, line 26. These stages are known in the art and are included solely to illustrate the preferred embodiment of the present invention.

[0083] Stage 4Scan Marked Objects

[0084] The processing performed by Stage 4scan marked objects (step 140)is also known in the art. Appendix A, from page 5, line 33 to page 6, line 55, includes exemplary code used in the preferred embodiment for scanning objects in the mark chain.

[0085] Stage 5Flip the Collector

[0086] In the final stageflipping the collector 150the garbage collector reclaims all objects that were not reachable by returning them to free memory. This process is well-known in the art and is not discussed in detail herein. Appendix A, from page 12 to page 16 contains exemplary code for this stage.

[0087] It will be appreciated by those skilled in the art that the present invention may be practiced in connection with details that differ from the specific examples of implementation set forth herein, and can be implemented in devices, systems and methods differing from those shown. Thus, the details set forth herein are provided by way of illustration rather than limitation, and the invention is limited only by the scope of the appended claims.