Abstract:
An invention is provided for managing memory that includes a heap memory and scoped memory. The scoped memory is managed separately from the heap memory, and includes defining a scope tree structure having a root node and a plurality of child nodes. The child nodes are capable of having respective child nodes, however each child node has only one parent node. Each child node corresponds to a scoped memory space that forms a logical memory pool corresponding to a particular scoped memory. During memory management, a thread is allowed to enter a particular child node only through the parent node of the particular child node. In this manner, a thread executing in a particular scooped memory space allocates memory from the scoped memory corresponding to the particular scoped memory space.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
         [0001]    This application claims the benefit of U.S. Provisional Patent Application No. 60/343,793, filed Oct. 23, 2001, entitled “Method and Apparatus for Scoped Memory,” which is incorporated herein by reference.  
         BACKGROUND OF THE INVENTION  
         [0002]    1. Field of the Invention  
           [0003]    This invention relates generally to computer memory, and more particularly to heap memory spaces with limited lifetimes.  
           [0004]    2. Description of the Related Art  
           [0005]    In computer programming, the free memory available for a program to utilize is known as the heap. When data objects such as arrays, records, and other data structures are created, space for the object is allocated in the heap. The term “object” is used herein to denote generally any piece of memory. For example, FIG. 1A is a diagram showing a portion of heap memory  100 . Generally, a pointer  102  can be used to reference an object  104  in the heap memory  100 . Specifically, when a computer program needs to access the heap memory  100 , the program can allocate a portion of the heap memory  100  using an allocation function provided in the language or memory management library. The allocation function often returns a reference or pointer  102  that can be used to access the allocated portion of the heap  100 .  
           [0006]    When the object  104  is no longer needed, its space is freed in order that the heap  100  does not become saturated with objects  104  that are no longer required for the computation. Some computer programming languages, such as Pascal or C, typically require the programmer to attend to the reclamation of heap  100  manually using a free function. This is known as manual memory management. In manual memory management, the programmer keeps track of when an object can be safely discarded. This manual heap maintenance is feasible, although prone to errors because too many allocations or too few deallocations can corrupt the memory.  
           [0007]    The continuing need to avoid such errors has rendered systems and languages supporting garbage collected heaps very attractive. Developing software in such environments is much faster because garbage collection eliminates a large class of programmer errors, both in the design and implementation stages. FIG. 1B is a diagram showing an automatic memory management heap  150 . As above, pointers  102   a - 102   c  can be used to access objects  104   a - 104   c  in the heap  150 . Also, as above, these pointers  102   a - 102   c  are generally created using an allocation function. However, instead of manual free operations being performed by the programmer, a garbage collector is used to manage the memory.  
           [0008]    During operation the garbage collector examines the heap  150  and determines which areas of the heap  150  no longer have pointers  102   a - 102   c  referencing them, and are thus available for reclaimation. The garbage collector then reclaims these heap areas, which are then available to be reallocated. Although automatic memory management provides a safe and stable operating environment that is less error prone, the non-deterministic nature of automatic memory management makes it unfavorable for use in some applications, such as real-time programming.  
           [0009]    Real-time programs often need direct access to the heap to perform certain operations. Unfortunately an automatic memory management system generally does not allow the programmer to access the heap when the garbage collector is in operation. This ensures the memory does not get corrupted as a result of heap alterations during garbage collection.  
           [0010]    For example, FIG. 1B shows pointer  3   102   c  referencing object  104   c  in the heap  150 . Suppose, during a garbage collection operation, the garbage collector examines the heap  150  and determines that heap area  150  is no longer referenced by a pointer and is thus available for reclaimation. If the programmer were then allowed to alter pointer  3   102   c  to point to an object in heap area  105  before the garbage collector could return the heap memory  105  to a consistent state, the heap memory  150  could be corrupted. In particular, since the garbage collector had previously determined that heap area  150  was available for reclaimation, the garbage collector would free heap area  150 , thus eliminating the object pointer  3   102   c  references. Later, when the application attempts to utilize the eliminated object, problems will occur.  
           [0011]    The time period in which an automatic memory management system locks out an application from the heap  150  is known as the minimum preemption interval. During the minimum preemption interval the garbage collector has exclusive access to the heap  150 . However, the minimum preemption interval is actually the minimum time the garbage collector needs to safely exit after beginning operation. More importantly, the minimum preemption interval does not guarantee any cleanup work is done on the heap  150 . Thus, in certain situations, an application can continuously access the heap in intervals close to the minimum preemption interval. In these situations, unreferenced objects in the heap may not be reclaimed, thus eventually depleting the heap  150  of memory.  
           [0012]    In view of the foregoing, there is a need for a method that provides the deterministic nature of manual memory management and the stability of automatic memory management. The method should reduce or eliminate the minimum preemption interval needed for garbage collection, and provide safe access to heap memory.  
         SUMMARY OF THE INVENTION  
         [0013]    Broadly speaking, the present invention fills these needs by providing memory management that includes the deterministic nature of manual memory management and the stability of automatic memory management. In one embodiment, a method for managing memory that includes a heap memory and scoped memory is disclosed. The scoped memory is managed separately from the heap memory, and includes defining a scope tree structure having a root node and a plurality of child nodes. The child nodes are capable of having respective child nodes; however, each child node has only one parent node. In addition, during memory management, a thread is allowed to enter a particular child node only through the parent node of the particular child node.  
           [0014]    A further method for managing memory that includes a heap memory and scoped memory is disclosed in a further embodiment of the present invention. As above, the scoped memory is managed separately from the heap memory, and includes defining a scope tree structure having a root node and a plurality of child nodes. Also, the child nodes are capable of having respective child nodes; however, each child node has only one parent node. Each child node corresponds to a scoped memory space that forms a logical memory pool corresponding to a particular scoped memory. In addition, during memory management, a thread is allowed to enter a particular child node only through the parent node of the particular child node. In this manner, a thread executing in a particular scooped memory space allocates memory from the scoped memory corresponding to the particular scoped memory space.  
           [0015]    In a further embodiment, a computer program embodied on a computer readable medium for managing memory that includes a heap memory and scoped memory is disclosed. The computer program includes a code segment that defines a scope tree structure having a root node and a plurality of child nodes, where the child nodes are capable of having respective child nodes, and each child node has only one parent node. In addition, the computer program includes a code segment that allows a thread to enter a particular child node only through the parent node of the particular child node. Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]    The invention, together with further advantages thereof, may best be understood by reference to the following description taken in conjunction with the accompanying drawings in which:  
         [0017]    [0017]FIG. 1A is a diagram showing a portion of heap memory;  
         [0018]    [0018]FIG. 1B is a diagram showing an automatic memory management heap;  
         [0019]    [0019]FIG. 2A is a diagram showing a heap providing scoped memory, in accordance with an embodiment of the present invention;  
         [0020]    [0020]FIG. 2B is a logical diagram illustrating a thread having an independent scoped memory, in accordance with an embodiment of the present invention;  
         [0021]    [0021]FIG. 3A is a diagram showing a scoped memory object, in accordance with an embodiment of the present invention;  
         [0022]    [0022]FIG. 3B is a diagram showing two threads and having nested references to scoped memory areas;  
         [0023]    [0023]FIG. 4 is graph showing a scope tree, in accordance with an embodiment of the present invention; and  
         [0024]    [0024]FIG. 5 is a diagram showing an exemplary scope stack, in accordance with an embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0025]    An invention is disclosed for scoped memory that provides heap memory spaces with limited lifetimes. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some or all of these specific details. In other instances, well known process steps have not been described in detail in order not to unnecessarily obscure the present invention.  
         [0026]    Embodiments of the present invention provide memory management that includes the deterministic nature of manual memory management and the stability of automatic memory management. As such, embodiments of the present invention are particularly useful for real-time programming using an object-oriented computer programming language, such as Java.  
         [0027]    However, it should be noted that other programming languages in addition to Java may be used to implement the embodiments of the present invention, including both procedural and object oriented programming languages. Object-oriented programming is a method of creating computer programs by combining certain fundamental building blocks, and creating relationships among and between the building blocks. The building blocks in object-oriented programming systems are called “objects.” An object is a programming unit that groups together a data structure (instance variables) and the operations (methods) that can use or affect that data. Thus, an object consists of data and one or more operations or procedures that can be performed on that data. The joining of data and operations into a unitary building block is called “encapsulation.” 
         [0028]    An object can be instructed to perform one of its methods when it receives a “message.”A message is a command or instruction to the object to execute a certain method. It comprises a method selection (name) and a plurality of arguments that are sent to the object. A message tells the receiving object what operations to perform.  
         [0029]    One advantage of object-oriented programming is the way in which methods are invoked. When a message is sent to an object, it is not necessary for the message to instruct the object how to perform a certain method. It is only necessary to request that the object execute the method. This greatly simplifies program development.  
         [0030]    Object-oriented programming languages are predominantly based on a “class” scheme. A class defines a type of object that typically includes both instance variables and methods for the class. An object class is used to create a particular instance of an object. An instance of an object class includes the variables and methods defined for the class. Multiple instances of the same class can be created from an object class. Each instance that is created from the object class is said to be of the same type or class.  
         [0031]    A hierarchy of classes can be defined such that an object class definition has one or more subclasses. A subclass inherits its parent&#39;s (and grandparent&#39;s etc.) definition. Each subclass in the hierarchy may add to or modify the behavior specified by its parent class.  
         [0032]    With the above in mind, FIG. 2A is a diagram showing a heap  200  providing scoped memory, in accordance with an embodiment of the present invention. Within the heap  200  is a scoped memory  204 , which is referenced by a scoped memory object Sm  202 . The scoped memory  204  performs as an independent heap having a-limited lifetime, as described in greater detail next with reference to FIG. 2B.  
         [0033]    [0033]FIG. 2B is a logical diagram illustrating a thread  206  having an independent scoped memory  204 , in accordance with an embodiment of the present invention. When the thread  206  is passed the scoped memory reference  202  and started, the thread  206  runs with the scoped memory  204  “attached.” In particular, the thread  206  operates as though the scoped memory  204  is the heap. The thread  206  can create new objects within the scoped memory  204  using normal allocation functions. For example, in FIG. 2B the thread  206  includes an allocation function  208  to create a new object T 1  of type T. As a result, the object Ti is placed in the scoped memory  204  at scoped memory area  210  and can be referenced by the thread  206  thereafter as a normal object.  
         [0034]    No garbage collection is performed on scoped memory  204 . Thus, there is no minimum preemption interval in which the application is excluded from the scoped memory  204 . Thus, the thread  206  can operate with objects in the scoped memory  204  independently and without fear of being collected. In addition, the scoped memory  204  can be shared with other threads using predetermined rules, as described in greater detail below with reference to FIG. 4. Briefly, a thread can access the scoped memory  204  by entering the scope of the scoped memory  204  using a enter( ) method. As a result, multiple threads can utilize a single scoped memory  204 , which will remain valid as long as there are threads with access to it. The number of threads with access to objects within a scoped memory is indicated using a reference counter.  
         [0035]    [0035]FIG. 3A is a diagram showing a scoped memory object  202 , in accordance with an embodiment of the present invention. Among other components, the scoped memory object  202  includes a reference counter  300 . The reference counter indicates the number of threads having access to objects within the scoped memory space referenced by the scoped memory object  202 . When the scoped memory object  202  is entered by a thread using an enter( ) method, the reference counter  300  is increased. Conversely, when a thread exits the scoped memory space referenced by scoped memory object  202 , the reference counter  300  is decreased. When the reference counter  300  reaches zero, no objects are being referenced within the scoped memory space referenced by the scoped memory object  202 . After the last reference to objects within the scoped memory space referenced by the scoped memory object  202  is removed by exiting the thread or exiting the enter( ) method, and before the scoped memory is reused, finalizers are run for all objects in the scoped memory area, and the scoped memory area is emptied. Thus, objects allocated from a scoped memory area have a defined lifetime. In particular, the objects cease to exist after the reference counter  300  for the scoped memory object  202  goes to zero.  
         [0036]    However, unrestricted access to scoped memories can lead to memory corruption, in particular, when nested references to scoped memories are executed. FIG. 3B is a diagram showing two threads  206   a  and  206   b  having nested references to scoped memory areas. In particular, thread  206   a  first enters scoped memory SmA 1   202   a , and then enters scoped memory SmA 2   202   b  from SmA 1   202   a . Thread  206   b  first enters scoped memory SmA 2   202   b , and then enters scoped memory SmA 1   202   a  from SmA 2   202   b . This type of nested referencing to scoped memory areas can cause the reference counters of the scoped memory objects  202   a  and  202   b  to increment and decrement incorrectly, thus making the reference counters no longer consistent with the scoped memory. To avoid this situation embodiments of the present invention utilize a scope tree, as discussed next with reference to FIG. 4.  
         [0037]    [0037]FIG. 4 is a graph showing a scope tree  400 , in accordance with an embodiment of the present invention. The scope tree  400  includes a plurality of nodes  406   a - 406   e , each representing a scoped memory scope. The scope tree  400  further includes a plurality of edges  408  connecting the scoped memory spaces  406   a - 406   e . The scope tree  400  is an undirected acyclic graph with a single root node  404 , which represents the global system heap. Further, the scope tree  400  is global and thus accessible by all threads on the system.  
         [0038]    During operation, a new scoped memory space can be created in a manner similar to allocating general objects. In particular, a modified allocation function, such as “new,” can be used to create a scoped memory object  202 , which is placed in the current memory space. For example, if the current memory space is scoped memory space  406   a , a newly created scoped memory object  202  would be placed within the scoped memory space  406   a . The newly created scoped memory object  202  can then be used to reference a new scoped memory space. For example, a thread executing in scoped memory space  406   a  can utilize the scoped memory object  202  to enter a new scoped memory space  406   b  referenced by the scoped memory object  202 . The current scoped memory space from which the new scoped memory space is first entered becomes the “parent” of the new scoped memory space. For example, since the thread was executing in scoped memory space  406   a  when it entered new scoped memory space  406   b , scoped memory space  406   a  becomes the “parent” scoped memory space  406   b.    
         [0039]    As mentioned above, a modified allocation function, such as “new,” can be used to create a scoped memory object  202 , which is placed in the current memory space. Upon creation of the scoped memory object  202 , the scoped memory space  406   b  referenced by the scoped memory object  202  can be entered using a scoped memory space entry method, referred to hereafter as a “.enter( ) method.” The enter( ) method draws an edge  408  between the parent memory space and the new memory space, which becomes the “child” memory space. For example, a thread executing in scoped memory space  406   a  can call a enter( ) method for the scoped memory object  202  to enter scoped memory space  406   b . In this case, scoped memory space  406   b  is the child of scoped memory space  406   a , because scoped memory space  406   b  was entered from scoped memory space  406   a . It should be born in mind that a new scoped memory space can be entered from a scoped memory space other than the scoped memory space in which the related scoped memory object is located. For example, the scoped memory object  202  can be created in scoped memory space  406   a  and not utilized for a period of time. Thereafter, a thread executing in scoped memory space  406   c  can call a enter( ) method for the scoped memory object  202  to enter a new scoped memory space  406   f , which is referenced by scoped memory object  202  in this example. In this case, scoped memory space  406   c  is the parent of scoped memory space  406   f , even though the scoped memory object  202  is located in scoped memory space  406   a.    
         [0040]    To reduce or eliminate the above mentioned nested referencing errors, which can cause the reference counters to increment and decrement incorrectly, embodiments of the present invention utilize a single parent rule. Specifically, the scope tree  400  requires each memory space node  406   a - 406   e  to have either zero or one parent node. That is, a single memory space node  406   a - 406   e  cannot have more than one parent node. For example, once scoped memory space  406   a  is established as the parent of scoped memory space  406   b , scoped memory space  406   b  can only be entered via scoped memory space  406   a.    
         [0041]    To do otherwise would result in scoped memory space  406   b  having more than one parent, thus violating the single parent rule. For example, a thread operating within scoped memory space  406   d  cannot perform a enter( ) to directly enter scoped memory space  406   b  from scoped memory space  406   d . To do so would result in scoped memory space  406   b  having both scoped memory space  406   a  and scoped memory space  406   d  as parents, which is a situation prohibit under the single parent rule.  
         [0042]    The embodiments of the present invention further utilize an access rule that allows referencing “down” the scope tree  400  from the root  404 , but prohibits referencing “up” the scope tree  400  towards the root  404 . For example, a thread operating within scoped memory space  406   b  can reference objects in scoped memory space  406   a , but a thread operating within scoped memory space  406   a  cannot reference objects in scoped memory space  406   b . To access objects in scoped memory space  406   b , a thread operating in scoped memory space  406   a  should first enter scoped memory space  406   b  via a enter( ) method.  
         [0043]    The access rule ensures that referenced objects will be in existence whenever referenced. Objects within memory spaces “above” the current memory space in the scope tree  400  (where “above” means closer to the root  404 ) have longer lifetimes than objects lower in the scope tree  400  because scoped memory spaces lower on the scope tree  400  must be exited and cleaned up before the scoped memory spaces above them. As a result, if a thread is allowed to reference down the scope tree  400  a dangling pointer can occur if the lower scoped memory space is completely exited and cleaned up. For example, if a thread operating in scoped memory space  406   a  referenced an object in scoped memory space  406   b , finalizers could be run for all objects in the scoped memory area  406   b  and the scoped memory area emptied when the reference counter reached zero. As a result, the object referenced from scoped memory space  406   a  could be eliminated even though it is being referenced, resulting in a dangling pointer.  
         [0044]    To allow easy traversing of the scope tree  400  and allow threads to examine histories of memory spaces, embodiments of the present invention utilize scope stacks. FIG. 5 is a diagram showing an exemplary scope stack  500 , in accordance with an embodiment of the present invention. A scope stack  500  is provided local to each thread, and allows the thread to examine the sequence of memory areas that have been entered or used as arguments for the thread constructor up to the current point in the thread execution. Specifically, as each memory space is entered, or used as an argument to a constructor, a reference to the memory space is pushed onto the local scope stack  500  for the thread. For example, FIG. 5 shows an exemplary scope stack  500  for a thread that has entered scoped memory area SmA 1   506 , the heap  502 , scoped memory area SmA 2   504 , and is currently back in the heap  502  memory space.  
         [0045]    In addition to utilizing scoped memory having limited lifetimes, embodiments of the present invention further allow applications to enter and reference objects in non-scoped memory spaces, such as the system heap. Such non-scoped memory spaces generally do not have the same entry and referencing restrictions applied to scoped memory spaces. As a result, non-scoped memory areas can be entered and referenced from any memory space, generally without restriction.  
         [0046]    Hence, the scope tree  400  alone cannot be utilized to determine the memory spaces entered or utilized by a particular thread because non-scoped memory spaces are not represented in the scope tree  400 . The scope stack  500  allows the non-scoped memory spaces, as well as the scoped memory spaces, to be accounted for when examining a history of entered memory spaces. As a result, a thread can utilize its local scope stack  500  to, for example, look back three memory spaces and reference something in that memory space.  
         [0047]    Although the foregoing invention has been described in some detail for purposes of clarity of understanding, it will be apparent that certain changes and modifications may be practiced within the scope of the appended claims. Accordingly, the present embodiments are to be considered as illustrative and not restrictive, and the invention is not to be limited to the details given herein, but may be modified within the scope and equivalents of the appended claims.