Adaptive instrumentation runtime monitoring and analysis

• US 7,587,709 B2
• Filed: 10/24/2003
• Issued: 09/08/2009
• Est. Priority Date: 10/24/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hauswirth, Matthias, Chilimbi, Trishul
• Primary Examiner(s): Dam; Tuan Q
• Assistant Examiner(s): Wei; Zheng
• Application Number:
  US10/693,834
• Publication Number:
  US 20050091645A1
• Time in Patent Office: 2,146 Days
• Field of Search: None
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime
• CPC Class Codes: G06F 11/366 using diagnostics G06F11/0703 takes precedence

Abstract

Techniques described herein provide low-overhead adaptive instrumentation runtime monitoring and analysis of software. A method of instrumenting a program to provide instrumentation data creates instrumentation versions comprising duplicate versions of original procedures in the program with instrumentation code for capturing instrumentation data, and adaptively decreases the sampling rate of the instrumented version of a procedure as the frequency of execution of the procedure increases. Additionally, the instrumentation methods can be used to build runtime tools that monitor the correctness of a program with very little overhead.

Claims

1. A method of instrumenting a program to provide instrumentation data for detecting memory leaks in the program, the method comprising:

creating an instrumented version of the program comprising duplicate versions of at least some code paths in the program, such that a duplicate code path has an original version code path and an instrumented version code path with instrumentation code for capturing instrumentation data;

tracking a frequency of execution of the code paths;

when a code path is to be executed, determining to dispatch execution into the instrumented version code path at a sampling rate for the respective code path and otherwise into the original version code path such that, for a given sampling rate, a ratio of a number of executions of the instrumented version code path to a total number of executions of both the instrumented version code path and the original version code path is equivalent to the given sampling rate;

adapting the sampling rate for the code paths according to the frequency of execution of the code paths, such that, after adapting, the ratio of a number of executions of the instrumented version code path to a total number of executions of the code path is equivalent to the adapted sampling rate, wherein the sampling rate for executing the code paths is adapted such that the adapted sampling rate is inversely related to the frequency of execution of the code paths;

storing instrumentation data obtained by execution of the instrumented version of the software; and

reporting all objects that, according to the instrumentation data, satisfy a predefined staleness condition as memory leaks, wherein the predefined staleness condition comprises determining whether an object in the heap has been accessed within a predetermined length of time.

2. The method of claim 1 wherein instrumentation data comprises data relating to runtime data references, branch executions, memory allocations, synchronization events, data loads, data stores, or branches.

3. The method of claim 1 wherein instrumentation data comprises heap allocation, heap free, and heap access information.

4. The method of claim 1 wherein reporting all objects comprises reporting the heap object, responsible allocation, heap frees that deallocated objects created at that allocation site, and the last access to the leaked object.

5. The method of claim 4 wherein a source code browser highlights the last access to a leaked object.

6. A method for bursty tracing to detect memory leaks in software by adapting a sampling rate of executing instrumented procedures in the software during runtime, the method comprising:

creating an instrumented version of the software containing an original version and an instrumented copy version of each procedure in the software, wherein only one version of the each procedure will be executed each time when the each procedure is required to execute during the runtime;

executing the instrumented version of the software;

tracking frequency of execution of the procedures, wherein the instrumented copy version of the procedures are sampled at rates adjusted to be inversely related to the frequency of execution of the procedures, including;

sampling at higher rates for the procedures whose total number of executions of both the original versions and the copy versions are executed less frequently, and sampling at lower rates for procedures whose total number of execution of both the original versions and the copy versions are executed more frequently, wherein the sampling rate for a given procedure comprises a number of executions of the instrumented version of the procedure taken as percentage of total number of executions of both versions of the procedure;

storing instrumentation data obtained by execution of the instrumented version of the software; and

reporting all objects that satisfy a predefined staleness condition as memory leaks, wherein the predefined staleness condition comprises determining whether an object in the heap has been accessed within a predetermined length of time.

7. The method of claim 6 wherein instrumentation data comprises heap allocation, heap free and heap access information.

8. The method of claim 6 wherein reporting all objects comprises reporting the heap object, responsible allocation, heap frees that deallocated objects created at that allocation site, and the last access to the leaked object.

9. The method of claim 8 wherein a source code browser highlights the last access to a leaked object.

10. A method of instrumenting a program to provide instrumentation data for detecting data races in the program, the method comprising:

creating an instrumented version of the program comprising duplicate versions of at least some code paths in the program, such that a duplicate code path has an original version code path and an instrumented version code path with instrumentation code for capturing instrumentation data;

tracking a frequency of execution of the code paths;

when a code path is to be executed, determining to dispatch execution into the instrumented version code path at a sampling rate for the respective code path and otherwise into the original version code path such that, for a given sampling rate, a ratio of a number of executions of the instrumented version code path to a total number of executions of both the instrumented version code path and the original version code path is equivalent to the given sampling rate; and

adapting the sampling rate for the code paths according to the frequency of execution of the code paths, such that, after adapting, the ratio of a number of executions of the instrumented version code path to a total number of executions of the code path is equivalent to the adapted sampling rate, wherein the sampling rate for executing the code paths are adapted at a rate inversely related to the frequency of execution of the code paths;

storing instrumentation data obtained by execution of the instrumented version of the software; and

reporting variables, that, according to the instrumentation data, satisfy a predefined data race condition based on lock acquisitions and releases for the variables.

11. The method of claim 10, wherein instrumentation data comprises sets of locks for variables in the software and sets of locks held by threads which access shared variables.

12. The method of claim 11, wherein storing instrumentation data comprises, when a thread accesses a shared variable, refining a set of locks for the variable by intersecting it with a set of locks for the thread.

13. The method of claim 12, wherein the predefined data race condition comprises determining, when an intersection is made between a set of locks for a variable and a set of locks for a thread, whether the intersection is null.

14. The method of claim 12, wherein the predefined data race condition comprises determining, when an intersection is made between a set of locks for a variable and a set of locks for a thread, whether the intersection is null.

15. The method of claim 11, wherein storing instrumentation data comprises, when a thread accesses a shared variable, refining a set of locks for the variable by intersecting it with a set of locks for the thread.

16. The method of claim 10, wherein instrumentation data comprises sets of locks for variables in the software and sets of locks held by threads which access shared variables.

17. A method for bursty tracing to detect data races in software by adapting a sampling rate of executing instrumented procedures in the software during runtime, the method comprising:

creating an instrumented version of the software containing an original version and an instrumented copy version of each procedure in the software, wherein only one version of the each procedure will be executed each time when the each procedure is required to execute during the runtime;

executing the instrumented version of the software;

tracking frequency of execution of the procedures, wherein the instrumented copy version of the procedures are sampled at rates adjusted to be inversely related to the frequency of execution of the procedures, including;

sampling at higher rates for the procedures whose total number of executions of both the original versions and the copy versions are executed less frequently, and sampling at lower rates for procedures whose total number of execution of both the original versions and the copy versions are executed more frequently, wherein the sampling rate for a given procedure comprises a number of executions of the instrumented version of the procedure taken as percentage of total number of executions of both versions of the procedure;

storing instrumentation data obtained by execution of the instrumented version of the software; and

reporting variables that, according to the instrumentation data, satisfy a predefined data race condition based on lock acquisitions and releases for the variables.

18. A method of instrumenting a program to provide instrumentation data for checking correctness of memory accesses in the program, the method comprising:

creating an instrumented version of the program comprising duplicate versions of at least some code paths in the program, such that a duplicate code path has an original version code path and an instrumented version code path with instrumentation code for capturing instrumentation data;

tracking a frequency of execution of the code paths;

when a code path is to be executed, determining to dispatch execution into the instrumented version code path at a sampling rate for the respective code path and otherwise into the original version code path such that, for a given sampling rate, a ratio of a number of executions of the instrumented version code path to a total number of executions of both the instrumented version code path and the original version code path is equivalent to the given sampling rate; and

adapting the sampling rate for the code paths according to the frequency of execution of the code paths, such that, after adapting, the ratio of a number of executions of the instrumented version code path to a total number of executions of the code path is equivalent to the adapted sampling rate, wherein the sampling rate for executing the code paths are adapted at a rate inversely related to the frequency of execution of the code paths;

storing instrumentation data obtained by execution of the instrumented version of the software; and

reporting memory accesses, that, according to the instrumentation data, access memory locations incorrectly.

19. The method of claim 18, wherein reporting memory accesses comprises reporting checking invariance in the software.

20. The method of claim 19, wherein the instrumentation data comprises array accesses.

21. The method of claim 20, wherein checking invariance comprises checking the array accesses against array bounds.

22. A method for bursty tracing to detect incorrect memory accesses in software by adapting a sampling rate of executing instrumented procedures in the software during runtime, the method comprising:

creating an instrumented version of the software containing an original version and an instrumented copy version of each procedure in the software, wherein only one version of the each procedure will be executed each time when the each procedure is required to execute during the runtime;

executing the instrumented version of the software;

tracking frequency of execution of the procedures, wherein the instrumented copy version of the procedures are sampled at rates adjusted to be inversely related to the frequency of execution of the procedures, including;

sampling at higher rates for the procedures whose total number of executions of both the original versions and the copy versions are executed less frequently, and sampling at lower rates for procedures whose total number of execution of both the original versions and the copy versions are executed more frequently, wherein the sampling rate for a given procedure comprises a number of executions of the instrumented version of the procedure taken as percentage of total number of executions of both versions of the procedure;

storing instrumentation data obtained by execution of the instrumented version of the software; and

reporting memory accesses, that, according to the instrumentation data, access memory locations incorrectly.

23. The method of claim 22, wherein reporting memory accesses comprises reporting checking invariance in the software.

24. The method of claim 23, wherein the instrumentation data comprises array accesses.

25. The method of claim 24, wherein checking invariance comprises checking the array accesses against array bounds.