Method and system for shadow heap memory leak detection and other heap analysis in an object-oriented environment during real-time trace processing

• US 6,658,652 B1
• Filed: 06/08/2000
• Issued: 12/02/2003
• Est. Priority Date: 06/08/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Levine, Frank Eliot, Alexander, William Preston III, Urquhart, Robert J., Reynolds, William Robert
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): STEELMAN, MARY J
• Application Number:
  US09/589,798
• Time in Patent Office: 1,272 Days
• Field of Search: 717/128, 714/42, 714/47, 711/1, 711/6, 711/100, 711/152, 711/173, 707/206
• US Class Current: 717/128
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/366 using diagnostics G06F11/0703 takes precedence
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and system for detecting memory leaks in an object-oriented environment during real-time trace processing is provided. During the profiling of a program executing in a data processing system, a profiler processes events caused by the execution of the program, and the profiler maintains a profile data structure containing execution-related metrics for the program. The execution-related metrics may include object allocation and deallocation metrics that are associated with object processing initiated on behalf of an executing method. An object allocator allocates objects during the execution of the program and modifies object allocation metrics in the profile data structure. Object metrics are stored in a particular location and a pointer to that location is stored in a hash table associated with the object'"'"'s ID. In another embodiment the pointer to the location is stored in a shadow heap in the same relative position as the position of the object in the heap. The object allocation metrics and the object deallocation metrics may be compared to identify memory leaks.

Claims

1. A method for profiling a program in a data processing system, the method comprising the computer-implemented steps of:

allocating a first object during execution of a function;

obtaining a reference to a profile data area associated with the function;

storing the reference in a shadow heap, wherein the shadow heap is a data structure in which references to profile data areas are stored at positions in the shadow heap that correspond to positions of corresponding objects in a memory heap; and

updating object allocation metrics in the profile data area associated with the function.

2. The method of claim 1 further comprising:

placing the reference in a corresponding position in the shadow heap as the position of the first object in the heap.

3. The method of claim 1 further comprising:

incrementing an object allocation count in the profile data area associated with the function.

4. The method of claim 1 further comprising:

incrementing a byte allocation count in the profile data area associated with the function.

5. The method of claim 1 further comprising:

allocating a second object during execution of the function;

obtaining the reference to the profile data area associated with the function; and

updating the object allocation metrics in the profile data area associated with the function.

6. The method of claim 1 further comprising:

receiving an object allocation event during execution of a current function;

determining whether the current function'"'"'s node has been allocated profile data area; and

returning a reference to the profile data area for the current function.

7. The method of claim 6 further comprising:

in response to a determination that a profile data area has not been allocated for the function, allocating a profile data area for the function.

8. The method of claim 7 further comprising:

storing the reference to the profile data area for the function in a call stack tree data structure.

9. The method of claim 1 further comprising:

obtaining, from the shadow heap, the reference to the profile data area associated with the function; and

updating object allocation metrics in the profile data area associated with the function.

10. The method of claim 1 further comprising:

accessing the profile data area associated with the function; and

comparing object allocation metrics and object deallocation metrics to identify memory leaks.

11. The method of claim 1 wherein the profile data area comprises execution context information for the function.

12. The method of claim 1 further comprising:

comparing object allocation metrics and object deallocation metrics to identify memory leaks;

ascertaining a memory leak, based on the comparison;

identifying a class of object being leaked, based on the comparison; and

identifying a function and call stack responsible for the leak is a unique advantage of the present invention.

13. The method of claim 1, wherein updating object allocation metrics in the profile data area associated with the function further comprises;

incrementing a live object metric in the profile data area.

14. The method of claim 13 further comprising:

marking all live objects in a heap;

identifying at least one unmarked object in the heap;

deallocating the unmarked object;

retrieving a reference from the shadow heap, wherein the reference has the same relative position in the shadow heap as the unmarked object'"'"'s position in the heap;

accessing the profile data area using the reference; and

decrementing the live object metric in response to identifying the unmarked object.

15. The method of claim 1, wherein updating object allocation metrics in the profile data area associated with the function further comprises:

incrementing a total object metric in the profile data area.

16. The method of claim 15 further comprising:

marking a live object in a heap;

retrieving a reference from the shadow heap, wherein the reference has the same relative position in the shadow heap as the live object'"'"'s position in the heap;

accessing the profile data area using the reference; and

incrementing a live object metric in response to identifying the live object.

17. A method for profiling a program in a data processing system, the method comprising the computer-implemented steps of:

allocating a first object during execution of a function;

obtaining a reference to a profile data area associated with the function;

storing the reference in a hash table; and

updating object allocation metrics in the profile data area associated with the function.

18. The method of claim 17, wherein storing the reference in a hash table further comprises:

hashing a first object identifier, wherein a first object identifier key is hashed;

comparing the first object identifier key with at least one slot index for the hash table; and

storing the reference as a slot in the hash table, wherein the slot index and the first object identifier are identical.

19. The method of claim 17, wherein updating object allocation metrics in the profile data area associated with the function further comprises:

incrementing a live object metric in the profile data area.

20. The method of claim 19 further comprising:

marking all live objects in a heap;

identifying at least one unmarked object in the heap;

deallocating the unmarked object;

retrieving a reference from the hash table based on the identity of the unmarked object;

accessing the profile data area using the reference; and

decrementing the live object metric in response to identifying the unmarked object.

21. The method of claim 17, wherein updating object allocation metrics in the profile data area associated with the function further comprises:

incrementing a total object metric in the profile data area.

22. The method of claim 21 further comprising:

marking a live object in a heap;

retrieving a reference from the hash table based on the identity of the marked object;

accessing the profile data area using the reference; and

incrementing a live object metric in response to identifying the live object.

25. The method of claim 21 further comprising:

identifying a live object in the heap;

accessing the reference stored external to the object; and

updating the object allocation metrics in the profile data area associated with the function based on identifying a live object.

26. The method of claim 25 further comprising:

accessing the profile data area associated with the function; and

comparing object allocation metrics and object deallocation metrics to identify memory leaks.

27. The method of claim 25 wherein the profile data area comprises at least one of live object count metric, live object bytes metric, total allocated object count metric and total allocated object bytes metric.

28. The method of claim 25 further comprising:

comparing object allocation metrics and object deallocation metrics to identify memory leaks;

ascertaining a memory leak, based on the comparison;

identifying a class of object being leaked, based on the comparison; and

identifying a function and call stack responsible for the leak is a unique advantage of the present invention.

23. A method for profiling a program in a data processing system, the method comprising the computer-implemented steps of:

allocating a first object in a heap during execution of a function;

determining whether a profile data area associated with the function has been allocated;

obtaining a reference to a profile data area associated with the function in response to a profile data area associated with the function having been allocated;

storing the reference external to the object in a data structure wherein a position of the reference in the data structure corresponds to a position of the object in the heap; and

updating object allocation metrics in the profile data area associated with the function.

24. The method of claim 23, wherein the reference is stored in one of a hash table and a shadow heap.

29. The method of claim 23, wherein storing the reference external to the object further comprises:

generating a key by hashing the object'"'"'s identifier;

checking a slot in a hash table for an object entry, wherein the slot is indexed by the key; and

storing the reference in the hash table.

30. The method of claim 23, wherein checking a slot in a hash table for an object entry, wherein the slot is indexed by the key further comprises:

generating another key by rehashing the object'"'"'s identifier in response to the slot containing object entry.

31. A data processing system for profiling a program in a data processing system, the data processing system comprising:

allocating means for allocating a first object during execution of a function;

obtaining means for obtaining a reference to a profile data area associated with the function;

storing means for storing the reference in a shadow heap, wherein the shadow heap is a data structure in which references to profile data areas are stored at positions in the shadow heap that correspond to positions of corresponding objects in a memory heap; and

updating means for updating object allocation metrics in the profile data area associated with the function.

32. The data processing system of claim 31 further comprising:

placing means for placing the reference in a corresponding position in the shadow heap as the position of the first object in the heap.

33. The data processing system of claim 31 further comprising:

incrementing means for incrementing an object allocation count in the profile data area associated with the function.

34. The data processing system of claim 31 further comprising:

incrementing means for incrementing a byte allocation count in the profile data area associated with the function.

35. The data processing system of claim 31 further comprising:

allocating means for allocating a second object during execution of the function;

obtaining means for obtaining the reference to the profile data area associated with the function; and

updating means for updating the object allocation metrics in the profile data area associated with the function.

36. The data processing system of claim 31 further comprising:

receiving means for receiving an object allocation event during execution of a current function;

determining means for determining whether the current function'"'"'s node has been allocated profile data area; and

returning means for returning a reference to the profile data area for the current function.

37. The data processing system of claim 36 further comprising:

allocating means for allocating a profile data area for the function in response to a determination that a profile data area has not been allocated for the function.

38. The data processing system of claim 37 further comprising:

storing means for storing the reference to the profile data area for the function in a call stack tree data structure.

39. The data processing system of claim 31 further comprising:

obtaining means for obtaining, from the shadow heap, the reference to the profile data area associated with the function; and

updating means for updating object allocation metrics in the profile data area associated with the function.

40. The data processing system of claim 31 further comprising:

accessing means for accessing the profile data area associated with the function; and

comparing means for comparing object allocation metrics and object deallocation metrics to identify memory leaks.

41. The data processing system of claim 31 wherein the profile data area comprises execution context information for the function.

42. The data processing system of claim 31 further comprising:

comparing means for comparing object allocation metrics and object deallocation metrics to identify memory leaks;

ascertaining means for ascertaining a memory leak, based on the comparison;

identifying means for identifying a class of object being leaked, based on the comparison; and

identifying means for identifying a function and call stack responsible for the leak is a unique advantage of the present invention.

43. The data processing system of claim 31, wherein the updating means for updating object allocation metrics in the profile data area associated with the function further comprises:

incrementing means for incrementing a live object metric in the profile data area.

44. The data processing system of claim 43 further comprising:

marking means for marking all live objects in a heap;

identifying means for identifying at least one unmarked object in the heap;

deallocating means for deallocating the unmarked object;

retrieving means for retrieving a reference from the shadow heap, wherein the reference has the same relative positioned in the shadow heap as the unmarked object'"'"'s position in the heap;

accessing means for accessing the profile data area using the reference; and

decrementing means for decrementing the live object metric in response to identifying the unmarked object.

45. The data processing system of claim 31, wherein the updating means for updating object allocation metrics in the profile data area associated with the system further comprises:

incrementing means for incrementing a total object metric in the profile data area.

46. The data processing system of claim 45 further comprising:

marking means for marking a live object in a heap;

retrieving means for retrieving a reference from the shadow heap, wherein the reference has the same relative positioned in the shadow heap as the live object'"'"'s position in the heap;

accessing means for accessing the profile data area using the reference; and

incrementing means for incrementing a live object metric in response to identifying the live object.

47. A computer program product for profiling a program in a data processing system, the product comprising the computer-implemented instructions of:

allocating instructions for allocating a first object during execution of a function;

obtaining instructions for obtaining;

a reference to a profile data area associated with the function;

storing instructions for storing the reference in a shadow heap, wherein the shadow heap is a data structure in which references to profile data areas are stored at positions in the shadow heap that correspond to positions of corresponding objects in a memory heap; and

updating instructions for updating object allocation metrics in the profile data area associated with the function.

48. The computer program product of claim 47 further comprising:

placing instructions for placing the reference in a corresponding position in the shadow heap as the position of the first object in the heap.