Abstract:
A method, computer system and program product operable to calculate a life span of an object by determining when an object is created and becomes collectable. A garbage collection trace algorithm conducted on a method boundary reveals when the object becomes unreachable. Trace data pertaining to the collection status of the object is stored and displayed within a record file. Other data stored by the invention relates to object creation, as well as to method entry and exit.

Description:
FIELD OF THE INVENTION  
         [0001]    The invention is generally relates to computers and computer software. More specifically, the invention relates to the management of data structures and functions in an object oriented programming system.  
         BACKGROUND OF THE INVENTION  
         [0002]    Managing available memory is critically important to the performance and reliability of a computer system. Such systems must store vast quantities of data within limited memory address space. Such data is commonly stored in the form of “objects.” Memory space allocated for an object is known as an object heap. Typically each computer program has its own object heap.  
           [0003]    Objects comprise both data structures and operations, known collectively as methods. Methods access and manipulate data structures. Objects having identical data structures and common behavior can be grouped together into classes. Each object inherits the data structure and methods of the particular class from which it was instantiated. Further, a hierarchical inheritance relationship exists between multiple classes. For example, one class may be considered a parent of another, child class. The child class is said to be derived from the parent class and thus, inherits all of the attributes and methods of the parent class.  
           [0004]    Object structure includes data and pointer fields. Pointers contain the addresses of other memory locations; data fields embody information or other objects. The object  10  of FIG. 1 has an identifier field  12 , data field  14  and pointers  16 ,  18 . The identifier field  12  contains processing instructions used only when the object  10  is compiled, so it is not necessarily stored with the object  10 . A dashes distinguish the identifier field  12  from information stored at run time.  
           [0005]    In the figure, pointers  16  are represented as arrows pointing to other objects  20 . A nil value of pointer  18  is represented by an “X” within the corresponding pointer field. Items  14  are contained by the object and are referred to as internal objects, while objects  20  referenced by the object&#39;s  10  pointers are known as external objects.  
           [0006]    The exemplary object  10  also has names  22  associated with it. Each name is a labeled pointer to the object. Since names are only used by the compiler at compile time, they do not require any storage at run time. This fact is represented by the use of dashed boxes to enclose the name pointers. Note that external objects can also contain pointers to other objects recursively, creating an object with arbitrary “depth.” 
           [0007]    The depth of an object is determined by counting the number of pointers that must be followed to reach it, starting from a name. Thus in the figure, names  22  are at depth  0 , the object  10  is at depth  1 , and the external objects  20  are at depth  2 . For consistency, the depth attributed to the manipulation of a pointer corresponds to the depth at which the pointer is stored. Thus, manipulations of pointers  16  as shown in FIG. 1 are considered to be at depth  1 .  
           [0008]    Whenever a program creates a new object, available memory is reserved using a process known as memory allocation. The Java programming environment developed by Sun Microsystems is one example of a programming framework that utilizes memory allocation. Given the limited amount of memory available in such an environment, it is important to deallocate memory reserved for data no longer in use. Otherwise, system performance will suffer as available memory is consumed.  
           [0009]    A computer program known as a garbage collector empties unused memory that has been allocated by other programs. Generally, a garbage collection algorithm carries out storage management by automatically reclaiming storage. Garbage collectors are typically activated when an object heap becomes full. A key functionality of a garbage collection algorithm involves determining if an object is no longer reachable by an executing program. A properly collectable object must be unreachable either directly or through a chain of pointers.  
           [0010]    Thus, the garbage collector must identify pointers directly accessible to the executing program. Further, the collector must identify references contained within that object, allowing the garbage collector to transitively trace chains of pointers. When the data structure of an object is deemed unreachable, the garbage collector reclaims memory. The memory is deallocated even if it has not been explicitly designated by the program.  
           [0011]    Specific methods for memory reclamation include reference counting, mark-scan and the copying garbage collection. In reference counting collection, as diagramed in FIG. 2, each external object  20  is associated with a count  24  reflecting the number of objects that point to it. Every time a new pointer implicates an external object  20 , the count  24  is incremented. Conversely, the count  24  is decremented every time an existing reference is destroyed. When the count  24  goes to zero, the object  20  and its associated count  24  are deallocated.  
           [0012]    A variation of the reference counting scheme known as weighted reference counting removes the requirement of referencing shared memory, but some bookkeeping is still required at run time. Another variation known as lazy reference counting reduces the run-time CPU requirements by deferring deallocation operations and then combining them with allocations, but does not eliminate them entirely.  
           [0013]    An alternative method, called mark-scan garbage collection, never explicitly deallocates external objects. Periodically, the garbage collection process marks all data blocks that can be accessed by any object. Unreachable memory is reclaimed by scanning the entire memory and deallocating unmarked elements.  
           [0014]    Each cycle of the mark-scan algorithm sequentially operates in mark and sweep stages. In the mark stage, the collector scans through an object heap beginning at its roots, and attempts to mark objects that are still reachable from a root. Objects deemed reachable if it is referenced directly by a root or by a chain of objects reachable from a root. In the sweep stage, the collector scans through the objects and deallocates any memory reserved for objects that are unmarked as of completion of the mark stage. Some variations of mark-scan require that active program threads be halted during collection, while others operate concurrently.  
           [0015]    Copying garbage collectors are similar to those of the mark-scan variety. However, instead of marking those items that can be reached by reference, all reachable data structures are periodically copied from one memory space into another. The first memory space can then be reclaimed in its entirety. A specific implementation of a copying garbage collector is a generational garbage collector, which partitions an object heap into new and old partitions. A generational garbage collector relies on a tendency for newer objects to cease to be used more frequently than older objects. Put another way, as an object is used over time, it becomes less and less likely that the object will cease being used.  
           [0016]    A generational garbage collector manages an object heap by scanning through newer objects in a new partition of the heap. The collector deallocates memory for objects that are no longer in use, and move objects that live beyond a predetermined period into an old partition. Given that older objects tend to be more stable, typically no scanning of the old partition of the object heap is required.  
           [0017]    Despite the progresses afforded by the above garbage collection techniques, obstacles to memory management remain. One particular area of concern relates to “short lived” objects. Although such objects may be used only briefly, they tend to linger and take up space in the object heap between garbage collection cycles. Further, the overhead associated with allocating and deallocating short lived objects is disproportionally high relative to “longer lived” objects.  
           [0018]    Deallocating processes require the computer to perform certain operations that are outside of normal productive operations. These additional processes burden the overall operation of the computer. Therefore, for both performance and storage concerns, it is desirable to minimize the occurrence of short lived objects. For instance, a programmer conducting a debugging operation could consolidate the functionality of a located short lived object into a long lived one. However, this task is complicated by the absence of an accurate method of calculating the life span of an object. Currently, a programmer is relegated to estimating life spans as a function of the time that the object is collected. Since the initiation of a garbage collection cycle does not necessarily coincide with when an object becomes unreachable, conventional life span measurements include periods where the object is actually defunct. Therefore a significant need exists for a manner of accurately calculating the lifetime of an object.  
         SUMMARY OF THE INVENTION  
         [0019]    The present invention involves a method, computer system and program product operable to calculate a life span of an object. The invention determines when an object is created and when it becomes collectable. A processor conducts a garbage collection trace algorithm on a method boundary to determine when the object becomes unreachable. In one embodiment, the frequency with which the trace algorithm is performed is modified via a user interface. In another application consistent with the invention, the processor conducts the trace algorithm at every method exit.  
           [0020]    Trace data pertaining to the algorithm is stored along with other data relating to method entry and exit, as well as to object creation. A visualizer program displays the trace data to the user. In one embodiment, the user locates an object within an object oriented programing environment based on the life span of the object. Another embodiment allows the user to determine what method was running at the time that the object became collectable.  
           [0021]    The above and other objects and advantages of the present invention shall be made apparent from the accompanying drawings and the description thereof.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0022]    [0022]FIG. 1 represents an object in accordance with the principles of the present invention.  
         [0023]    [0023]FIG. 2 represents a reference count attached to an external object in a manner consistent with the prior art.  
         [0024]    [0024]FIG. 3 is a block diagram of a networked computer system consistent with the present invention.  
         [0025]    [0025]FIG. 4 is a block diagram of an exemplary hardware and software environment for a computer from the networked computer system of FIG. 3.  
         [0026]    [0026]FIG. 5 is a flow chart illustrating computer processing steps that are in accordance with the principles of the present invention.  
         [0027]    [0027]FIG. 6 is a table populated with exemplary trace data generated in accordance with the principles of the present invention. 
     
    
       [0028]    The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and, together with a general description of the invention given above, and the detailed description of the embodiments given below, serve to explain the principles of the invention.  
       DETAILED DESCRIPTION  
     Hardware Environment  
       [0029]    Turning to the Drawings, wherein like numbers denote like parts throughout the several views, FIG. 3 illustrates a computer system  25  consistent with the invention. Computer system  25  is illustrated as a networked computer system including one or more client computer systems  36 ,  27  and  30  (e.g., desktop or personal computers, workstations, etc.) coupled to server system  28  through a network  29 .  
         [0030]    Network  29  may represent practically any type of networked interconnection, including but not limited to local-area, wide-area, wireless, and public networks (e.g., the Internet). Moreover, any number of computers and other devices may be networked through network  29 , e.g., multiple servers. Furthermore, it should be appreciated that the principles of the invention may be utilized as well by stand-alone computers and associated devices consistent with the invention.  
         [0031]    Computer system  30 , which may be similar to computer systems  26 ,  27 , may include one or more processors such as a microprocessor  321 ; a number of peripheral components such as a computer display  32  (e.g., a CRT, an LCD display or other display device); storage devices  33  such as hard, floppy, and/or CD-ROM disk drives; a printer  34 ; and various input devices (e.g., a mouse  36  and keyboard  37 ), among others. Computer system  30  operates under the control of an operating system, and executes various computer software applications, programs, objects, modules, etc. Moreover, various applications, programs, objects, modules, etc. may also execute on one or more processors in server  28  or other computer systems  26 ,  27 , e.g., in a distributed computing environment.  
         [0032]    In general, the routines executed to implement the illustrated embodiments of the invention, whether implemented as part of an operating system or a specific application, program, object, module or sequence of instructions will be referred to herein as computer programs. The computer programs typically comprise instructions that, when read and executed by one or more processors in the devices or systems in computer system  30 , cause those devices or systems to perform the steps necessary to execute steps or elements embodying the various aspects of the invention.  
         [0033]    Moreover, while the invention has and hereinafter will be described in the context of fully functioning computer systems, those skilled in the art will appreciate that the various embodiments of the invention are capable of being distributed as a program product in a variety of forms, and that the invention applies equally regardless of the particular type of signal bearing media used to actually carry out the distribution. Examples of signal bearing media include but are not limited to recordable type media such as volatile and non-volatile memory devices, floppy disks, hard disk drives, CD-ROM&#39;s, and DVD&#39;s, among others and transmission type media such as digital and analog communications links.  
         [0034]    Those skilled in the art will recognize that the exemplary environment illustrated in FIG. 3 is not intended to limit the present invention. Indeed, those skilled in the art will recognize that other alternative hardware environments may be used without departing from the scope of the invention.  
       Software Environment  
       [0035]    [0035]FIG. 4 illustrates one suitable software environment for computer system  30  consistent with the invention. A processor  31  is illustrated as coupled to a memory  38  as well as to several inputs and outputs. For example, user input is received by processor  31 , e.g., by mouse  36  and keyboard  37 , among others. Additional information may be passed between computer system  30  and other computer systems in networked computer system  25  via network  29 . Additional information may be stored to and/or received from mass storage  33 . Processor  31  also outputs display data to display  32 . It should be appreciated that computer system  30  includes suitable interfaces between processor  31  and each of components  29 ,  32 ,  33 ,  36 ,  37  and  38  as is well known in the art.  
         [0036]    A Java Virtual Machine (JVM) execution module  40  is illustrated as resident in memory  38 , and is configured to execute program code on processor  31 , e.g., one or more program threads  42 , as well as a collector thread  44  that is used to deallocate unused data stored in an object heap  46 . Collector thread  44 , which is described in greater detail below, also utilizes a plurality of data structures  48  during its operation.  
         [0037]    Execution module  40  may be resident as a component of the operating system of computer system  30 , or in the alternative, may be implemented as a separate application that executes on top of an operating system. Furthermore, any of execution module  40 , program thread  42 , collector thread  44 , object heap  46  and collector data structures  48  may, at different times, be resident in whole or in part in any of memory  38 , mass storage  33 , network  29 , or within registers and/or caches in processor  3   1 .  
         [0038]    In one embodiment of the invention, JVM  40  is specially configured to operate in a developmental environment. Since such environments are geared towards debugging, as opposed to performance, JVM  40  may be configured for flexibility and optimized code correction. More specifically, the developmental emphasis means that processing delays associated with memory management techniques are better tolerated than with conventional machines.  
         [0039]    It should be appreciated that the various software components may also be resident on, and may execute on, other computers coupled to computer system  25 . Specifically, one particularly useful implementation of an execution module consistent with the invention is executed in a server such as an AS/400 midrange computer system from International Business Machines Corporation. It should be appreciated that other software environments may be utilized in the alternative.  
       Life Span Determination  
       [0040]    The invention calls for the JVM  40  of FIG. 4 to cycle through an instruction sequence represented by the flowchart of FIG. 5. The sequence determines the life span of an object by executing a trace collection algorithm on a method boundary. Other data gleaned from the invention relates to object creation, as well as to method entries and exits. A program of the exemplary embodiment additionally stores and initiates the display of trace data relating to each instruction.  
         [0041]    Turning to the figure, the JVM begins the program cycle at block  50 . While the invention can operate concurrently with other programs, the instruction sequence is preferably conducted while other programs are halted. This precaution ensures that concurrent processes do not affect objects while they are under evaluation. At block  52 , the JVM retrieves the first instruction. Of note, the sequence of the exemplary instructions  54 ,  56 ,  58  may be altered or augmented with other processes without straying from the principles of the invention.  
         [0042]    Instructions in a Java environment include byte codes, or functions, that are each operable to perform a simple processing operation. Examples of such operations include loading a value from out of a particular location or calling a subroutine. The exemplary instructions of FIG. 5 may each invoke multiple methods to achieve their purpose. In the flowchart, the first occurring instruction option relates to object creation. Assuming that an object creation requirement is indicated at block  54 , the JVM executes code operable to create an object. For instance, the program could create an object configured to maintain employee records at block  60 . Trace data that relates to the creation instruction is written to a trace record at block  62 .  
         [0043]    A trace record that is consistent with the principles of the present invention is shown in FIG. 6. Diagnostic and other statistical data relevant to the creation instruction include event and thread identification numbers  64 ,  66 , as shown in row  68 . A time stamp value  70  is also recorded. Other relevant data includes an event type  72 , or method description, as well as an information column  74 , which designates the name of the object manipulated by the method. While the enumerated record categories are shown in FIG. 6, a record table consistent with the invention is not limited to these data points.  
         [0044]    Furthermore, a post-processor may be used to visualize the trace data for the programmer, allowing for a more focused and tailored display. For instance, a graphical interface summarizes information of particular interest to the programmer. For example, a display could list the life span of a select object by calculating the difference between associated creation and collection time stamps. Another list could reveal the final method that manipulated the object. A variation of such a list can signal the unanticipated persistence of an object meant to be collected by a programmer&#39;s method, a scenario known as object leakage. Still another display lists all objects having a life span within a particular range. Such a display would assist a debugger in locating short lived objects.  
         [0045]    Returning to the flowchart of FIG. 5, the program searches for a next occurring instruction  52  after writing to the trace record  62 . If the next instruction calls for a method entry, as opposed to a second object creation instruction, then processing required to initiate a method is conducted at block  56 . For instance, the program of FIG. 5 requires a particular subroutine to sort through employee zip codes. At block  80 , a method, zip_start, operable to initiate the subroutine is executed. Trace data relating to the entry of start zip is written to the trace record  82 , and the program sequence is begun again at block  52 .  
         [0046]    Assuming the next instruction at block  58  is a method exit, then the objects required to end the function are conjured and executed by the JVM. For instance, get_ssn is a method that retrieves and loads a social security value from a database into an employee benefits field. The application of get_ssn ends at time stamp 00:01:07. Accordingly, processing required to end get_ssn is accomplished at block  84 . As with the above instructions, the program relates trace data relevant to the exit of method get_ssn to the record of FIG. 6.  
         [0047]    Prior to repeating the writing the method exit to the trace record  96 , a garbage collector algorithm is invoked at block  86 . Any of the deallocation methods discussed herein are compatible with the present invention, including copying, mark-scan and reference counting collectors. Further, such algorithms may be optimized for the instrumented JVM environment. For example, a generational-type collector can be modified to only track and mark changed objects, obviating the need to evaluate all objects. Similarly, an object heap can be apportioned to selectively optimize a collector&#39;s evaluation. A mark-scan collector can be configured so that it merely locates unreachable objects without actually sweeping them.  
         [0048]    The process of FIG. 5 call for such a modified mark-scan collector at block  86 . By way of review, a mark-scan collector cycles through multiple collection stages to reclaim unused data in an object heap. A first stage initiates the collection cycle. Next, a mark stage is executed that marks any used, or reachable, objects.  
         [0049]    Typically, the mark stage is divided into several distinct stages, e.g., a “mark roots” stage and a “trace” stage. The mark roots stage marks the global and local roots in the object heap—that is, any variables that are defined as global or static or that are stored in various stacks and registers within the computer system. The trace stage then marks the objects reachable from other marked objects. The trace stage is complete when all objects that reference marked objects are also marked.  
         [0050]    When marking objects in a concurrent collection cycle, a four-color marking scheme is typically utilized. A white color indicates that an object is unmarked. A gray color indicates that an object is marked, but that its direct descendants may not yet be marked (i.e., some may be white). A black color indicates that an object is marked and all of its direct descendants are marked (either gray or black). Finally, a blue color indicates that the object is on the free list. With this scheme, gray or black objects are also referred to as “shaded” objects.  
         [0051]    Depending upon the language being supported, additional stages may be present in a collector thread. For example, Java may require a “finalize trace” stage between the mark and sweep stages to identify and trace objects ready for finalization. A finalizer ensures that all files and resources used by object are closed prior to deallocation. The present invention can account for finalization by writing traces to a separate record, or even by using a separate deallocation algorithm to monitor the finalizer.  
         [0052]    Once the collector locates an unreachable object at block  88 , the object is identified and trace record data relating to the unreachable object is stored a block  90 . For example, the invention determines that all pointers cease to reference object ins_dat at time stamp 00:02:23. The name  92  of the object is reflected in the trace record of FIG. 6, along with the collection event  94  precipitating its identification.  
         [0053]    The JVM determines the method that was running at the time the object became collectable by associating creation and exit time stamps for respective objects and methods. The mark-scan collector continues to locate collectable objects at block  88  until all are recorded in the trace record. Then at block  96 , the trace data relating to the method&#39;s exit are related to the record of FIG. 6.  
         [0054]    The sequence begins again at block  52 , and the JVM searches for instructions to create an object  54  or method entry  56 /exit  58 . If an instruction for exiting the JVM is encountered at block  98 , then the program is ended at block  100 . Otherwise, the program sequence repeats at block  52 . Of note, while the illustrated embodiment is configured to run a deallocation program after every method exit, another embodiment incorporates a user interface that allows a programmer to interactively select the collection frequency.  
         [0055]    While the present invention has been illustrated by a description of various embodiments and while these embodiments have been described in considerable detail, it is not the intention of the applicants to restrict or in any way limit the scope of the appended claims to such detail. Additional advantages and modifications will readily appear to those skilled in the art. The invention in its broader aspects is therefore not limited to the specific details, representative apparatus and method, and illustrative example shown and described. Accordingly, departures may be made from such details without departing from the spirit or scope of applicant&#39;s general inventive concept.