Leveraging garbage collection to dynamically infer heap invariants

• US 7,912,877 B2
• Filed: 05/20/2005
• Issued: 03/22/2011
• Est. Priority Date: 05/20/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chilimbi, Trishul, Shankar, Ajeet
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Bromell; Alexandria Y
• Application Number:
  US11/134,796
• Publication Number:
  US 20060265438A1
• Time in Patent Office: 2,132 Days
• Field of Search: None
• US Class Current: 707/813
• CPC Class Codes: G06F 11/0718 in an object-oriented system
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

A program analysis tool leverages the garbage collection process to dynamically infer invariants of objects or data structures created by a program on the heap during execution. During execution of the program in a garbage-collected execution environment, the program analysis tool tracks object allocations made by the program, and records some meta data relating to invariants tracked for the type of the object, which are initially assumed satisfied by the object. Whenever a garbage collection pass visits the object, the tool checks whether the object still satisfies the invariants, and updates the meta data accordingly. The tool finally reports the invariants reflected by the meta data upon the object'"'"'s death or at termination of the program. The invariants can then be used to annotate the program source code and/or detect bugs that violate the invariants.

Claims

1. A method of inferring heap invariants for program objects maintained by a program in heap memory, comprising:

causing the program to execute over a period in an execution environment having a heap memory managed using garbage collection;

creating meta data to track a set of invariants to be inferred about the program objects created by the program in the heap memory, wherein the invariants are properties of the program objects which do not vary during execution of the program;

upon a vitality check of the program objects in a garbage collection pass and during the garbage collection pass;

traversing objects in the heap memory to determine, for each object which is traversed, whether the object is reachable;

for each object in the heap memory that is traversed, as the object is traversed to determine if it is reachable, checking whether the set of invariants to be inferred about the object remain satisfied, and updating the meta data based on results of the checking;

producing data reporting the invariants satisfied by the program objects in the heap memory during the period of execution of the program;

generating an annotated program, wherein generating the annotated program comprises writing static annotations to the source code for the program specifying the invariants reported to be satisfied by at least some of the program objects in the heap memory;

compiling the annotated program with edits to the source code into an edited program; and

reporting occurrences of anomalies in which the invariants are violated by the edited program in a period of execution of the edited program at least by comparing the invariants specified by the static annotations in the source code and invariants reported in the period of execution of the edited program.

2. The method of claim 1, further comprising:

when creating the meta data, initializing the meta data of the program objects to indicate the invariants are satisfied by the program objects; and

when the checking determines that an invariant is not satisfied by a program object, updating the meta data to indicate the invariant was not satisfied by said program object.

3. The method of claim 1 further comprising tracking a set of invariants that are generic to all the program objects.

4. The method of claim 1 further comprising tracking a set of type-specific invariants of the program objects according to their respective types.

5. The method of claim 1 further comprising tracking a set of invariants of the program objects based on allocation site.

6. The method of claim 1 further comprising tracking a set of type-wide invariants applicable across all program objects of a same type.

7. The method of claim 1 wherein the period of execution of the edited program is a separate debugging run after the program has been edited.

8. The method of claim 1 further comprising identifying code in the program that produced an occurrence of an anomaly as a bug.

9. The method of claim 1 further comprising identifying code in the program associated with a program object having an invariant indicative of likely inefficient behavior for possible optimization.

10. The computer-readable computer program-carrying physical storage of claim 1 wherein the program analysis tool further comprises:

identifying code in said program under test that produced an occurrence of an anomaly as a bug.

11. Computer-readable computer program-carrying physical storage having instructions which, when executed by a computer, cause the computer to perform the actions of a program analysis tool by performing analysis of a program under test to infer heap invariants of program objects maintained by said program under test in heap memory, the performing analysis of a program under test comprising:

performing the actions of a heap executive by providing a heap allocator application programming interface service to allocate memory space in heap memory upon request from said program under test;

performing the actions of a garbage collector by;

periodically performing a garbage collection pass over program objects created by said program under test in heap memory; and

testing liveness of the program objects; and

performing the actions of an invariant inference service operating across and outside of an execution of said program under test by;

maintaining meta data tracking a set of invariant inferences per program object, wherein the invariant inferences are inferences that an invariant property of the respective object does not vary during execution of the program;

at the time the garbage collector tests liveness of a program object, checking that the program object continues to satisfy the invariant inferences tracked for the respective object; and

producing a report indicating the invariant properties satisfied by the program objects across the execution of said program under test; and

reporting occurrences of anomalies in which the invariants are violated by the program with edited source code in a subsequent execution of the edited program at least by comparing the reported invariant properties satisfied by the program objects and invariant properties reported in the subsequent period of execution of the edited program.

12. The computer-readable computer program-carrying physical storage of claim 11 wherein performing the actions of the invariant inference service further comprises:

when creating the meta data, initializing the meta data of the program objects to indicate the invariant inferences are satisfied by the program objects; and

when its check determines that an invariant inference is not satisfied by a program object, updating the meta data to indicate the invariant inference was not satisfied by said object.

13. The computer-readable computer program-carrying physical storage of claim 11 wherein performing the actions of the invariant inference service further comprises tracking a set of invariant inferences that include inferences that at least some of generic invariants, type-specific invariants, allocation-site based invariants, type-wide invariants, and behavioral invariants are satisfied for the respective object.

14. The computer-readable computer program-carrying physical storage of claim 11 wherein performing the actions of the program analysis tool further comprises:

adding annotations to source code of said program under test based on the invariant properties reported to be satisfied by at least some of the program objects.

15. A computer implementing a dynamic program analysis system for inferring heap invariants of program objects maintained by a program in heap memory, the system comprising:

one or more physical computer processors; and

computer memory containing computer-executable instructions executing on the one or more computer processors causing the computer to perform a method, the method comprising;

causing the program to execute over a period in an execution environment having a heap memory managed using garbage collection;

creating meta data to track a set of invariants to be inferred about the program objects created by the executing program in the heap memory, wherein the meta data is created based on the types of the program objects;

holding the metadata in an area of memory that is not managed by the garbage collection;

when creating the meta data, initializing the meta data of the program objects to indicate the invariants are satisfied by the program objects;

responsive to a vitality check of the program objects during a garbage collection pass;

traversing objects in the heap memory to determine, for each object which is traversed, whether the object is reachable;

for each object that is traversed, as the object is traversed to determine if it is reachable, checking whether the set of invariants to be inferred about the program object remain satisfied and updating the meta data based on results of the checking;

updating the meta data to indicate the invariant was not satisfied by a program object, when the checking determines that an invariant is not satisfied by the program object; and

if the object is no longer reachable, as the object is reclaimed, performing a final update of the meta data based on results of said checking;

responsive to termination of the program execution;

updating the meta data of the objects that remain on the heap;

logging the final state of the invariant inferences for each object remaining on the heap;

producing data, based on the logging, reporting the invariants satisfied by the program objects over the period of execution of the program; and

adding static annotations to the source code of the program specifying the invariants reported to be satisfied by at least some of the program objects in the heap memory of the executing program;

compiling an annotated program with edits to the source code into an edited program; and

reporting occurrences of anomalies in which invariants are violated by the edited program in a period of execution of the compiled edited program, by comparing the invariants specified by the static annotations in the source code and the invariants reported in the period of execution of the compiled edited program.