Selective self-healing of memory errors using allocation location information Number:7,434,105 from the United States Patent and Trademark Office (PTO) owispatent

Title: Selective self-healing of memory errors using allocation location information

Abstract: A system for selective self-healing of memory errors comprises a processor coupled to a memory, where the memory stores instructions executable by the processor to store an error record for each memory management error detected during an execution of the application. The error record identifies an allocation location (e.g., a portion of a stack trace corresponding to the invocation of a memory allocation function such as malloc( )) of an object associated with the memory management error. The instructions are executable to use the error record to identify, during subsequent execution, memory operations performed on objects allocated from the allocation location, and to perform corresponding memory protection operations (e.g., operations to prevent re-occurrences of the memory errors) for the memory operations identified using the error record.

Patent Number: 7,434,105 Issued on 10/07/2008 to Rodriguez-Rivera,   et al.

---

Inventors:	Rodriguez-Rivera; Gustavo (West Lafayette, IN), Spertus; Michael P. (Chicago, IL)
Assignee:	Symantec Operating Corporation (Cupertino, CA)
Appl. No.:	11/268,360
Filed:	November 7, 2005

---

Current U.S. Class:	714/38 ; 714/42
Current International Class:	G06F 11/00 (20060101)
Field of Search:	714/38

---

References Cited [Referenced By]

---

U.S. Patent Documents

5355483	October 1994	Serlet
5687368	November 1997	Nilsen
5909580	June 1999	Crelier et al.
6035426	March 2000	Applegate
6349312	February 2002	Fresko et al.
6496850	December 2002	Bowman-Amuah
6546477	April 2003	Russo et al.
6874074	March 2005	Burton et al.
7024535	April 2006	Fougeroux et al.
7051056	May 2006	Rodriguez-Rivera et al.
7096339	August 2006	Nelson
7174354	February 2007	Andreasson
7181585	February 2007	Abrashkevich et al.
7234080	June 2007	Cirne et al.
7293201	November 2007	Ansari
7296130	November 2007	Dimpsey et al.
7299384	November 2007	Rodriguez-Rivera et al.
2002/0035676	March 2002	Weeks
2004/0015642	January 2004	Moir et al.
2004/0078540	April 2004	Cirne et al.
2004/0117771	June 2004	Venkatapathy
2004/0158589	August 2004	Liang et al.
2004/0172513	September 2004	Nelson
2004/0225925	November 2004	Chen
2005/0022063	January 2005	Grebenev
2005/0235124	October 2005	Pomaranski et al.
2005/0235127	October 2005	Muthiah et al.
2006/0294433	December 2006	Thelen
2007/0011415	January 2007	Kaakani et al.

Other References

Van Der Wal, Ron; "Testing testers: Error detection tools for Win32"; Review; Jul. 1996; Internet; Tarma Software research; http://www.tarma.com/index.htm#/articles/1996jul.htm. cited by other . "Develop Fast, Reliable Code with IBM Rational PurifyPlus"; Paper; 2003; Internet; Rational Software Corporation; ftp://ftp.software.ibm.com/software/rational/web/whitepapers/2003/PurifyP- lusPDF.pdf. cited by other . "VERITAS (tm) Application Saver 1.2--User's Guide--Windows"; Manual; 2004; Internet; VERITAS Software Corporation; http://ftp.support.veritas.com/pub/support/products/Application.sub.--Sav- er/266719.pdf. cited by other . Best, Steve; "Linux Debugging and Performance Tuning: Tips and Techniques"; Article; Oct. 10, 2005; Pearson PTR. cited by other . "Managing Application Reliability with VERITAS (tm) Application Saver"; White Paper; 2004; Internet; VERITAS Software Corporation; http://eval.symantec.com/mktginfo/enterprise/white.sub.--papers/veritas.s- ub.--application.sub.--saver.sub.--2.sub.--1.sub.--wp.pdf. cited by other . Grunwald, Dirk and Benjamin Zorn; "CustoMalloc: Efficient Synthesized Memory Allocators"; Technical Report; Jul. 1992; University of Colorado at Boulder. cited by other.

Primary Examiner: Maskulinski; Michael C
Assistant Examiner: Miles; Neil D
Attorney, Agent or Firm: Meyertons Hood Kivlin Kowert & Goetzel, P.C. Kivlin; B. Noel

---

Claims

---

What is claimed is:

1. A system, comprising: a processor; and memory coupled to the processor; wherein the memory stores program instructions executable by the processor to: store an error record in a database corresponding to a memory management error detected during an execution of an application, wherein the memory management error is associated with an object allocated during the execution, wherein the error record identifies an allocation location within the application at which the object was allocated; identify, using the error record, at least one memory operation in the application performed on an other object allocated from the allocation location identified in the error record; and perform at least one memory protection operation corresponding to the at least one memory operation identified using the error record.

2. The system as recited in claim 1, wherein the instructions are further executable to: examine the database to determine whether a memory protection operation is to be performed for a given memory operation during an execution of the program; in response to determining that a memory protection operation is to be performed for the given memory operation, perform the memory protection operation; and in response to determining that a memory protection operation is not to be performed for the given memory operation, perform the given memory operation without performing a corresponding memory protection operation.

3. The system as recited in claim 1, wherein the error record indicates a type of memory protection operation to be performed for memory operations on objects allocated from the identified allocation location.

4. The system as recited in claim 1, wherein the instructions are further executable to: store a respective identification of an allocation location corresponding to each object allocated during the execution; and prior to storing the error record, generate the error record using a stored identification of an allocation location corresponding to the object.

5. The system as recited in claim 1, wherein the allocation location is specified in the error record as one or more program counter values.

6. The system as recited in claim 1, wherein the allocation location is specified in the error record as a portion of an execution stack.

7. The system as recited in claim 1, wherein the memory management error comprises at least one of: a memory smash operation, a premature free operation, a duplicate free operation, a premature garbage collection operation, and a memory leak.

8. The system as recited in claim 7, wherein: if the memory management error comprises a memory smash operation, a corresponding memory protection operation comprises allocating a number of extra bytes for the other object; if the memory management error comprises a premature free operation or a duplicate free operation, a corresponding memory protection operation comprises designating the other object as an object to be collected via garbage collection instead of being explicitly freed; if the memory management error comprises a premature garbage collection operation, a corresponding memory protection operation comprises designating the other object as an object to be explicitly freed instead of being collected via garbage collection; and if the memory management error comprises a memory leak, a corresponding memory protection operation comprises generating a report of a stack trace of the application when the other object is allocated.

9. The system as recited in claim 1, wherein the instructions are further executable to: provide an interface configured to display a representation of one or more memory management errors detected during the execution, wherein the representation comprises an identification of the type of each memory management error of the one or more memory errors.

10. The system as recited in claim 9, wherein the interface comprises a mechanism enabling a user to selectively enable and disable a use of memory protection operations corresponding to one or more types of memory management errors.

11. The system as recited in claim 1, wherein the at least one memory protection operation is performed during the same execution of the application in which the memory management error is detected.

12. The system as recited in claim 1, wherein the at least one memory protection operation is performed during a different execution of the application than the execution in which the memory management error is detected, wherein the instructions are further executable to: generate a persistent data structure comprising the error record; wherein the at least one memory operation is identified during the different execution using the persistent data structure.

13. The system as recited in claim 1, wherein the execution of the application comprises an invocation of one or more functions of a shared library, wherein the allocation location is within a function of the shared library.

14. A computer-implemented method, comprising: storing an error record in a database corresponding to a memory management error detected during an execution of an application, wherein the memory management error is associated with an object allocated during the execution, wherein the error record identifies an allocation location within the application at which the object was allocated; identifying, using the error record, at least one memory operation in the application performed on an other object allocated from the allocation location identified in the error record; and performing at least one memory protection operation corresponding to the at least one memory operation identified using the error record.

15. The method as recited in claim 14, further comprising: examining the database to determine whether a memory protection operation is to be performed for a given memory operation during an execution of the program; in response to determining that a memory protection operation is to be performed for the given memory operation, performing the memory protection operation; and in response to determining that a memory protection operation is not to be performed for the given memory operation, performing the given memory operation without performing a corresponding memory protection operation.

16. The method as recited in claim 14, further comprising: storing a respective identification of an allocation location corresponding to each object allocated during the execution; and prior to storing the error record, generating the error record using a stored identification of an allocation location corresponding to the object.

17. The method as recited in claim 14, wherein the allocation location is specified in the error record as one or more program counter values.

18. The method as recited in claim 14, wherein the memory management error comprises at least one of: a memory smash operation, a premature free operation, a duplicate free operation, a premature garbage collection operation, and a memory leak.

19. The method as recited in claim 18, wherein, if the memory management error comprises a memory smash operation, a corresponding memory protection operation comprises allocating a number of extra bytes for the other object; if the memory management error comprises a premature free operation or a duplicate free operation, a corresponding memory protection operation comprises designating the other object as an object to be collected via garbage collection instead of being explicitly freed; if the memory management error comprises a premature garbage collection operation, a corresponding memory protection operation comprises designating the other object as an object to be explicitly freed instead of being collected via garbage collection; and if the memory management error comprises a memory leak, a corresponding memory protection operation comprises generating a report of a stack trace of the application when the other object is allocated.

20. A tangible computer readable medium comprising program instructions, wherein the instructions are computer-executable to: store an error record in a database corresponding to a memory management error detected during an execution of an application, wherein the memory management error is associated with an object allocated during the execution, wherein the error record identifies an allocation location within the application at which the object was allocated; identify, using the error record, at least one memory operation in the application performed on an other object allocated from the allocation location identified in the error record; and perform at least one memory protection operation corresponding to the at least one memory operation identified using the error record.

21. The computer readable medium as recited in claim 20, wherein the instructions are further computer executable to: examine the database to determine whether a memory protection operation is to be performed for a given memory operation during an execution of the program; in response to determining that a memory protection operation is to be performed for the given memory operation, perform the memory protection operation; and in response to determining that a memory protection operation is not to be performed for the given memory operation, perform the given memory operation without performing a corresponding memory protection operation.

22. The computer readable medium as recited in claim 20, wherein the instructions are further computer executable to: store a respective identification of an allocation location corresponding to each object allocated during the execution; and prior to storing the error record, generate the error record using a stored identification of an allocation location corresponding to the object.

23. The computer readable medium as recited in claim 20, wherein the allocation location is specified in the error record as a portion of a stack trace.

24. The computer readable medium as recited in claim 20, wherein the memory management error comprises at least one of: a memory smash operation, a premature free operation, a duplicate free operation, a premature garbage collection operation, and a memory leak.

25. The computer readable medium as recited in claim 24, wherein, if the memory management error comprises a memory smash operation, a corresponding memory protection operation comprises allocating a number of extra bytes for the other object; if the memory management error comprises a premature free operation or a duplicate free operation, a corresponding memory protection operation comprises designating the other object as an object to be collected via garbage collection instead of being explicitly freed; if the memory management error comprises a premature garbage collection operation, a corresponding memory protection operation comprises designating the other object as an object to be explicitly freed instead of being collected via garbage collection; and if the memory management error comprises a memory leak, a corresponding memory protection operation comprises generating a report of a stack trace of the application when the other object is allocated.

---

Description

---

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to computer systems and, more particularly, to handling memory management errors within computer systems.

2. Description of the Related Art

Memory management has long been known as a source of errors or "bugs" in computer applications. Often applications, e.g., those applications written at least partly using programming languages such as C and C++ that allow programmers to manage memory, are introduced into production environments even though they may contain memory management bugs. Even programs that may be considered relatively bug-free, e.g., as a result of thorough testing prior to release, may rely on third-party libraries that may contain memory management bugs. As a result, the executable code of a production application may often result in various types of memory management errors such as memory leaks, premature frees, duplicate frees, memory smashes etc.

Various techniques have been developed to identify such memory management errors, e.g., by instrumenting the application code to track object creations and deletions. Several such techniques support the elimination of certain types of memory management errors by implementing global error correction or prevention. For example, in one such global technique, all explicit programmer-initiated memory de-allocation functions (e.g., "free( )") may be eliminated from the application via code substitution or code modification, and a conservative garbage collection mechanism may instead be used to release memory. In another such global scheme, memory smashes (where a program modifies memory beyond the end of an allocated object, thus potentially modifying neighboring objects or data structures) may be largely or completely avoided by extending the size of each allocated object by additional bytes.

However, many of these global techniques may be accompanied by negative side effects. For example, a global replacement of programmer-initiated memory de-allocation by conservative garbage collection may result in a substantial increase in both execution time (e.g., because of the extra processing required for the garbage collection) and memory used (e.g., because the aggregate amount of memory used by the application may grow relatively large between successive garbage collection events). Adding extra bytes to each allocated object to avoid memory smashes may also lead to excessive use of memory. The frequency of occurrence of memory management bugs within a program relative to the frequency of occurrence of "correct" (i.e., error-free) memory operations may often be relatively low, so that the overhead of global memory error handling schemes may not always be justifiable in some cases. In fact, in practice, the overhead of the global techniques has sometimes been found to be so high that administrators have deliberately disabled global memory error handling mechanisms; that is, administrators have sometimes been willing to accept the risks of memory management errors in preference to the overhead of global memory error handling. A more flexible approach towards memory error handling may provide application administrators and application users with a better tradeoff between the risk of memory management errors and the overhead of error prevention or correction.

SUMMARY

Various embodiments of systems and methods for selective self-healing of memory errors using allocation location information are disclosed. According to one embodiment, a system comprises a processor coupled to a memory, where the memory stores instructions executable by the processor to store an error record for each memory management error detected during an execution of the application. The instructions may, for example, implement a memory management tool configured to detect errors and selectively perform memory protection operations in response to the detection of the errors. The error record may identify an allocation location (e.g., a portion of a stack trace corresponding to the invocation of a memory allocation function such as malloc( )) of an object associated with the memory management error, such as an object that is freed prematurely or an object that is freed multiple times. The allocation location may be within one or more shared libraries used by the application in some embodiments, and may be in the main program of the application itself in other embodiments. The error record may thus indicate that some portions of code may be "unsafe" allocation locations, e.g., indicating that objects allocated from those unsafe locations during subsequent execution of the application may be more likely to be involved in memory management errors than objects allocated from other allocation locations. Using the error records, one or more memory operations performed on objects allocated from unsafe allocation locations may be identified by the memory management tool during subsequent execution, and corresponding memory protection operations (e.g., operations to prevent re-occurrences of the memory errors, or to counteract negative effects of the memory errors) may be performed.

The memory management tool may be configured in one embodiment to examine the database of error records to determine, for a given memory operation during an execution of the application, whether a memory protection operation is needed, and to only perform memory protection operations for those objects that were allocated from unsafe allocation locations, allowing operations on other objects to be performed without corresponding memory protection operations. In this way, the memory management tool may reduce the overhead of memory protection operations in comparison to other global techniques where memory protection operations may be performed for each memory operation. In some embodiments, the memory management tool may generate an allocation location record corresponding to each allocation event in the application, and use the allocation location records to generate the error records (e.g., for any object involved in a given memory management error, the tool may look up the allocation location of the object in an allocation location database, and designate that allocation location as an unsafe allocation location in an error record).

In some embodiments, the error may be detected in the same execution in which a corresponding memory protection operation is performed: e.g., an unsafe allocation location may be identified in a particular function, and a memory protection operation may be performed if and when a memory operation is performed on another object allocated from that same function while the application is still executing. In other embodiments, a persistent version (e.g., a "profile" or "unsafe allocation location list") of error records may be generated for use across multiple executions of the application. In one such embodiment, protective memory operations may be performed proactively using the persistent version, i.e., memory management errors that were detected in an earlier execution may be entirely eliminated during a later execution of the application using memory protection operations.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram illustrating one embodiment of a system.

FIG. 2 is a flow diagram illustrating aspects of the operation of a memory management tool, according to one embodiment.

FIG. 3 is a table listing exemplary memory protection operations and reporting actions that may be performed by a memory management tool, according to one embodiment.

FIG. 4 is a block diagram illustrating various subcomponents of a distributed version of memory management tool, according to one embodiment.

FIG. 5 is a flow diagram illustrating aspects of the operation of a memory management tool in an embodiment where an instrumented version of an application is executed in a test environment to detect unsafe allocation locations prior to deployment of the application in a production environment.

FIG. 6 is a block diagram illustrating constituent elements of a computer host, according to one embodiment.

While the invention is susceptible to various modifications and alternative forms, specific embodiments are shown by way of example in the drawings and are herein described in detail. It should be understood, however, that drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the invention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION

FIG. 1 is a block diagram illustrating a system 100 according to one embodiment. As shown, system 100 includes a memory management tool 120, an allocation location database 140 and an error database 150. The memory management tool 120 may be configured to detect memory management errors in an executing application 102 and to perform or initiate memory protection operations in response to at least some of the detected memory management errors. The allocation location database 140 and the error database 150 may be implemented as a single database in some embodiments, and may share at least some components in other embodiments. In one embodiment memory management tool 120 may be configured to store, corresponding to each object for which memory is allocated in executing application 102, an allocation location (e.g., a portion of an application stack trace, or a program counter value corresponding to a caller of a function such as malloc( ) that is invoked to allocate the object) in the allocation database 140. When a memory management error is detected during the execution of application 102, the memory management tool 120 may be configured to store an error record 170 (e.g., error record 170A or 170B of FIG. 1) in error database 150. The error record 170 may include an allocation location corresponding to the allocation of an object associated with the memory error--e.g., if an error occurs when an object "A" is freed, the allocation location for "A" may be stored in a corresponding error record 170. The allocation locations and the occurrences of memory management errors may be detected by memory management tool 120 using a variety of techniques in different embodiments, such as dynamic substitution of existing memory management functions by customized versions of the functions.

The memory management tool 120 may be configured to use the error records 170 to identify potentially problematic allocation locations. For example, if a memory management error occurs during an operation associated with an object allocated from a particular location within a particular function of a shared library, the memory management tool 120 may determine that it is likely that other objects allocated from that location, that function, and/or that shared library may also eventually be involved in memory management errors. The potentially problematic allocation location may be termed an "unsafe" allocation location herein. The memory management tool 120 may be configured to use the error records 170 to identify other memory management operations that are performed on objects allocated from such unsafe allocation locations, and to perform memory protection operations corresponding to the identified memory management operations. Other objects may be allocated from the unsafe allocation locations, for example, during the same execution in which the errors are detected (e.g., if a function in which the unsafe allocation is performed is called multiple times in the application), or in a different execution of the application. The term "memory protection operation" as used herein, generally refers to an operation that may be performed in response to a memory management error, e.g., to prevent a re-occurrence of the error, to alleviate effects of the error, etc. Various types of memory protection operations may be performed for different types of memory operations, e.g., extra memory may be allocated to prevent data corruption due to memory smashes on objects allocated from the unsafe allocation locations, or the manner in which objects allocated from the unsafe allocation location in the future are freed may be modified. For some kinds of memory management errors, a memory protection operation may include a notification of detailed information about the error (such as a report of a full stack trace corresponding to a memory leak). Further details on how memory management errors of various types may be detected in various embodiments, and the specific types of memory protection operations performed for errors of different types are provided below.

Using error records 170, memory management tool 120 may be operable to determine, for a given memory operation performed on an object during the execution of application 102, whether a memory protection operation is to be performed or not, and may only perform memory protection operations for those objects identified as having been allocated from a potentially problematic allocation location. Other memory operations performed on objects that have not yet been identified as unsafe may be allowed to proceed without any change, e.g., without performing any corresponding memory protection operations. By restricting the use of memory protection operations to operations on objects allocated only from "unsafe" locations, memory management tool 120 may avoid the excessive overhead associated with some traditional global memory error handling mechanisms that may, for example, perform memory protection operations for all objects allocated from all locations. The level of protection provided by the memory management tool 120 may be similar or equivalent to that provided by traditional global memory error handling mechanisms, potentially with much lower resource costs, especially for applications in which the majority of errors are located in a relatively small subset of the code (e.g., in a third-party shared library or in a few subcomponents of the code). It is noted that not all memory operations performed on objects allocated from unsafe allocation locations may actually lead to errors if memory protection operations are not performed; thus, even some of the limited memory protection operations performed by memory management tool 120 may not be strictly necessary. However, the reduction of the number of memory protection operations performed using the selective techniques employed by memory management tool 120, compared to the number that would be performed using some conventional global memory error handling techniques, may be substantial and may result in a much lower impact on application performance and resource consumption.

Several exemplary memory related operations 130 (e.g., operations 130A-130K) of executing application 102 are illustrated in FIG. 1. For example, operation 130A allocates an object "A". FIG. 1 illustrates exemplary allocation locations 110 in the form of hexadecimal program counter values of the calling function for each allocation operation shown--e.g., the allocation location of operation 130A is "0x1abd32" (the "0x" suffix indicates that the remaining portion of the value is to be treated as a hexadecimal number). Memory management tool 120 may enter the allocation location for object "A" into allocation location database 140, as shown. It is noted that in some embodiments, allocation location database 140 and/or error database 150 may be maintained in volatile memory only, while in other embodiments, portions or all of one or both databases may be saved in persistent storage as well. The exact format and/or content of allocation locations stored in the allocation location database 140 may vary in different embodiments. E.g., in some embodiments, instead of simply storing one program counter value corresponding to a function that invoked the allocation function such as malloc( ), additional information such as function names and/or program counter values of two or three levels of the stack frame at the time of the allocation may be included in the allocation location database. If a malloc( ) function to allocate "A" was invoked from a first function F1, which was called from a second function F2, which was called by a third function F3, for example, the names and/or program counter values for each of F1, F2 and F3 may be stored in allocation location database 140 in some implementations, and each of the program counter values and/or functions may thereby be designated as an "unsafe" allocation location in such implementations. The format and order of the records in the allocation location database 140 may differ in different embodiments. For example, in some embodiments, the database 140 may be stored in a sort order based on the allocation location, and in other embodiments one or more indexes may be created corresponding to the columns of the database such as allocation location, object name, object address, etc. The columns included in the allocation location database 140 in some embodiments may differ from those shown in FIG. 1, e.g., in embodiments where more detailed allocation location information is stored than a single program counter value, multiple columns may be used for various elements of the allocation location information.

In some embodiments, memory management tool 120 may be configured to create a new entry in allocation location database 140 for each allocation operation of application 102 for which an entry does not already exist. E.g., on encountering allocation operation 130B for object "B", a new entry may be created, and on encountering allocation operation 130C for object "C", another new entry may be created in the allocation location database 140. In some embodiments, when an allocation occurs from a location for which an entry already exists in allocation database 140 (e.g., when object "K" is allocated from location "0x1abd32" in operation 130G), the memory management tool 120 may simply add an identification of the newly allocated object to the existing entry; in other embodiments, multiple separate entries for the same allocation location may be created if multiple objects are allocated from that location.

Memory management tool 120 may be configured to detect a variety of different types of memory management errors, of which two types are illustrated in FIG. 1. A first type of memory management error, which may be termed a "duplicate free", occurs when an object that has already been freed is freed again. At some point after "A" is allocated in the execution, "A" may be freed, e.g., in operation 130D. If "A" is subsequently freed again, e.g., at operation 130F, the memory management tool 120 may be configured to detect the repeated or duplicated free as a memory management error. In FIG. 1, for example, memory management tool 120 detects an error "E1" when operation 130F is attempted, and stores a corresponding error record 170A in the error database 150. Since the error is associated with object "A" (i.e., memory allocated for "A" is being freed a second time), the error record 170A indicates that the allocation location "0x1abd32" at which "A" was allocated is an "unsafe" allocation location. Another type of memory management error, termed a "memory smash", may be detected if application 102 attempts to modify memory beyond the end of an object, as shown in operation 130H where a write beyond the allocated memory of object "B" is attempted and memory management tool 120 detects the error E2. Memory management tool 120 may generate another error record 170B in error database 150 corresponding to error E2, indicating that the allocation location "0x5c2d65" of object "B" is another potentially problematic or "unsafe" allocation location. In addition to storing the unsafe allocation locations in the error records 170, memory management tool 120 may be configured to store additional information in each error record in some embodiments, such as the type of error (e.g., "Duplicate Free", "Memory Smash" etc.), an identifier for the error (e.g., "E1" or "E2"), the memory protection operation to be performed, statistics on how often memory protection operations have already been performed for the unsafe allocation location, etc. Other types of memory errors that may be detected by memory management tool 120 in various embodiments may include, for example, premature frees, premature garbage collection operations, memory leaks, etc.; further details about these error types are provided below.

Memory management tool 120 may be configured to use error database 140 to check, when a given allocation operation is performed during the execution of application 102, whether the allocation is performed from a location previously designated as an unsafe allocation location. If an object is allocated from an unsafe allocation location, memory management tool 120 may designate the object as a memory protection candidate (MPC) 160 in some embodiments. When another operation (such as an invocation of a free( ) function or a garbage collection operation) is later performed on the MPC object, memory protection tool 120 may perform a memory protection operation to avoid or prevent potentially unsafe behavior. For example, in FIG. 1, memory protection tool 120 may be configured to designate object "K" as an MPC 160A, since "K" is allocated in operation 130G from allocation location "0x1bd32", which was earlier identified as an "unsafe" allocation location in error record 170A. Similarly, object "P" may be designated as an MPC 160B because it is allocated (in operation 130J) from allocation location "0x5c2d65", which was also earlier designated as an unsafe allocation location in error record 170B. When an operation is attempted on "K" (e.g., a free( ) operation 130K) or on "P", the memory management tool may intervene and perform one or more protection operations, e.g., by replacing a free( ) operation with the logical equivalent of a "no-operation" or no-op and designating the object as a candidate for eventual garbage collection. In one embodiment, in addition to recognizing that an object is a candidate for a future memory protection operation when the object is allocated from an unsafe allocation location, memory management tool 120 may perform a memory protection operation associated with the allocation itself (e.g., additional memory may be allocated for the object beyond the requested amount, or the object may be allocated from a special region in memory, etc.). In some embodiments, object names or address ranges of memory protection candidates 160 may be stored in an additional database or data structure. It is noted that the word "object" is used generically for entities (e.g., "A", "B", "K", "P" in FIG. 1) for which memory is dynamically allocated, and that the use of the word "object" is not meant to restrict the use of the techniques described above to applications written in object-oriented languages--for example, the techniques may be used for applications written in non-object-oriented languages such as C, Pascal, etc. as well as for applications written in object-oriented languages such as C++. It is also noted that in some embodiments, a plurality of memory protection operations may be performed corresponding to each object identified as being allocated from an unsafe allocation location: e.g., a first memory protection operation may be performed when the object is allocated, and another memory protection operation may be performed when it is freed.

In some embodiments, e.g., in order to detect memory allocations and memory management errors, memory management tool 120 may be configured to dynamically replace one or more memory management libraries or functions invoked by the application 102 with customized or instrumented versions, or to modify the binary code of the application with instrumentation instructions. For example, in some operating environments (such as various Linux or UNIX.TM.-based operating systems), an application may have an associated environment variable such as "LD_PRELOAD" that supports the ability to modify the order in which various shared libraries are loaded or searched for a given function to be executed. By placing a substitute memory management library that includes modified/instrumented versions of various memory management functions at an appropriate location within the set of libraries identified by the environment variable, memory management tool 120 may arrange for application 102 to execute the modified or instrumented versions instead of the original, unmodified versions. The modified versions may include code to maintain metadata on dynamically created objects in the application; e.g., in one implementation, a separate instrumentation record or header may be created for the memory allocated in each malloc( ) call, and stored in an independent heap location (e.g., in a location that is not adjacent or near to the object that is allocated, and is therefore less likely to be overwritten or damaged by a memory management error associated with the allocated memory). The instrumentation record may be used to store various types of information on the allocated memory, such as checksums calculated from the allocated memory, etc., that may be used to detect errors such as premature frees and/or to perform various memory protection operations. Similar techniques of code substitution may be used in other operating environments, e.g., using other environment variables in other operating systems. In some embodiments, a memory management library supplied by an operating system may be modified, e.g., a few additional instructions may be added at the start of memory allocation functions like malloc( ) and free( ) supplied by the operating system to redirect memory management function calls to custom versions of the functions. Memory management tool 120 may instrument an application 102 using such techniques without, for example, having access to source code for the application, thus allowing the memory protection mechanisms described above to be applied in production environments where source code is often unavailable.

In one embodiments, the support for selective memory error correction/protection based on the designation of allocation locations as "unsafe" may be provided as an optional feature of an existing memory error handling mechanism. For example, in one embodiment, memory management tool 120 may be configured to operate in one of two modes: a first mode in which the tool performs memory protection operations globally, e.g., for all allocation locations in a given program, and a second mode in which the memory protection operations are performed selectively based on error record entries 170 identifying unsafe allocation locations as described above. Such a tool may be implemented for a variety of reasons, e.g., to maintain compatibility with existing system management scripts while optionally providing improved performance. In some implementations, memory management tool 120 may be configured to provide an estimate or measurement of resources used by the tool itself (e.g., how much memory and/or CPU is used for error database 150 and allocation location database 140), allowing users to easily quantify the benefits of selective memory error correction.

Memory management tool 120 may be used to detect and prevent memory management errors in production environments in some embodiments. For example, the initial detection of an error and the protective operations performed for other objects allocated at the unsafe allocation location corresponding to the error may all occur during the same execution of a production application in such embodiments. In other embodiments, memory management tool 120 may also be used in a test environment prior to deployment of an application to a production environment. For example, the techniques described above of storing allocation location information for all allocations, and designating a subset of the allocation locations as being potentially unsafe based on detected errors, may be applied during a test run or runs, where for example an application is subjected to various expected workload levels. Having identified the unsafe allocation locations in the test runs, the application may then be instrumented to eliminate or avoid each of the errors detected, before being deployed to the production environment. Thus, one or more errors may be initially detected during a first execution of the application 102 in a test environment, and protective actions corresponding to the designated unsafe allocation locations may be performed during subsequent executions. In this way, proactive memory protection operations may be performed in the production environment prior to an occurrence of any actual error in the production environment. E.g., if the application 102 of FIG. 1 were instrumented and modified in a test environment, "0x1abd32" would have been designated as an unsafe allocation location even before operation 130A is executed at the production environment, and protective memory operations may be performed for object "A" to preclude the occurrence of any error such as the duplicate free of operation 130F.

In some embodiments, a list or "profile" of unsafe allocation locations (e.g., part or all of error database 150) may be maintained in a persistent form for an application based on one or more executions. If the application is moved or redeployed from its original operating environment to a different operating environment, or another instance of the application is set up in an new operating environment, the list of unsafe allocation locations may be provided for use in the different or new operating environment. For example, a banking application may first be deployed at one bank data center, and after the initial deployment is successful, the application may be replicated (i.e., additional instances may be deployed) at other data centers of the same banking company. A compact disk or other media including the list of unsafe allocation operations identified in the first deployment (or in a test environment prior to the first deployment) may be provided for the new deployments. The list may be used to perform memory protection operations in the new operating environment without requiring re-instrumentation or re-detection of errors in the new environment, thus potentially saving substantial time and computing resources. Since the unsafe allocation location list was obtained in a particular operating environment, for example using a particular version of shared libraries, device drivers, etc., the unsafe allocation location list may potentially be invalid or stale in a new operating environment where different versions of shared libraries, drivers etc. are used. For example, if a particular function F1 was a source of many memory management errors in version 5.0 of a shared library in which errors and unsafe allocation locations were detected, the function F1 may have been modified in version 6.0, so that the program counter values or stack information identified in the allocation locations may have changed. In some implementations, in order to avoid inadvertent use of stale unsafe allocation location lists, a unique identification of the set of components (shared library versions, application code versions, etc.) may be maintained along with the unsafe allocation location list. The identification may be implemented using a variety of different techniques, such as checksums for each of the various components and/or a text file containing version numbers, executable file sizes, creation dates, timestamps, etc.

Part or all of the allocation location information (e.g., the hexadecimal program counter values such as "0x5c2d65" shown in FIG. 1) may be stored as absolute numerical quantities in some embodiments. In other embodiments, program counter values included within the allocation location information may be stored as offsets with respect to a starting address of a program or shared library. If the order in which libraries or programs are loaded changes from one execution environment to another, or if the memory address at which a library or program is loaded changes from one execution environment to another, the use of relative program counter values in such embodiments may ensure that the memory protection operations are still performed for the appropriate memory operations. It is noted that in embodiments where program counter values are stored as offsets, a recompilation or an upgrade to a new version of a shared library or another portion of the application may potentially result in the offsets becoming invalid. In some embodiments, memory management tool 120 may be configured to store in persistent storage a list of shared libraries used in the application, along with corresponding checksums or digest values (e.g., calculated using the MD5 Message Digest algorithm) and the unsafe allocation location information. Whenever the application 102 is started, the checksums/digests may be recalculated for the shared libraries, and if any of the checksum values differ from those stored earlier, unsafe allocation locations corresponding to the libraries whose checksums have changed may be discarded as being invalid (and in some implementations, administrators may be informed). The unsafe allocation locations for the changed libraries may then be recomputed during execution using the techniques described above.

FIG. 2 is a flow diagram illustrating aspects of the operation of memory management tool 120, according to one embodiment. The memory management tool 120 may be configured to record allocation location information in allocation location database 140 for each allocation operation encountered during the execution of an application 102 (block 205 of FIG. 2). The specific content of the allocation location information may vary in different embodiments: e.g., in one embodiment, a single numerical quantity such as a hexadecimal program counter of a function that invokes a malloc( ) function may be saved in an allocation location record, while in other embodiments more detailed information such as multiple levels of stack information (function names and associated absolute or relative program counter values) may be saved.

As shown in block 210 of FIG. 2, memory management tool 120 may be configured to detect memory management errors dynamically during the execution of the application 102 (block 210). A number of different types of memory management errors may be detected in different embodiments using a variety of error detection techniques, as described below. In one implementation, memory management tool 120 may redirect calls made from the application 102 to memory management functions such as malloc( ) and free( ) to customized or instrumentation versions of the memory management functions (such as "CustoMalloc( )" and "CustomFree( )"). A customized version of an allocation function such as malloc( ) may generate a data structure called a "header" for each allocation, and store information in the header that may be needed for detection and/or correction of various types of errors. The header may be stored in a portion of memory that is relatively distant from the allocated object itself, e.g., to prevent any memory management errors associated with the object from corrupting the header.

Using the header, a premature free operation, i.e., a freeing or de-allocation of an object that is still in use, may be detected using the following technique in one embodiment where malloc( ) and free( ) are used to allocate and deallocate objects respectively. A checksum of the object being freed may be computed in the call to free( ) (e.g., in the custom version of free( )), and the checksum may be stored in the header for the object. When malloc( ) is subsequently called and the memory freed earlier is chosen for allocation, the checksum is computed again and compared with the checksum stored in the header. If the two checksums differ, the object was modified after it was freed, indicating that the call to free( ) was premature. Duplicated frees of an object may be detected by storing a status of the object within the header for the object. The status may indicate, for example, whether the object is currently allocated (in-use) or free. If, when free( ) is called for an object, the object already has a free status, a duplicated free may be detected by memory management tool 120. In environments where conservative garbage collection is used for one or more objects, a premature garbage collection error may be detected if an object is collected while the program is still using the object. Conservative garbage collection is a technique that relies on identifying potential pointers within an application's address space (e.g., potential pointers within "root" objects as well as heap objects) based on the value of data (e.g., if a data value "looks like" a heap address or falls within a numerical range that is within heap address boundaries, the data value is assumed to be a pointer) to identify memory regions to be collected. Conservative garbage collection may be employed as an error correction/prevention mechanism, e.g., to respond to memory leaks in programs that use explicit rather than automatic memory management, in some embodiments. A premature garbage collection may occur, for example, if pointers are hidden from the garbage collector by scrambling or writing the pointers to disk, making the garbage collector erroneously conclude that an object is no longer in use. Memory management tool 120 may use the header for an object to store garbage collection status for the object: e.g., to indicate whether the object has already been collected. When free( ) is invoked for the object, a premature collection may be detected if the status of the object indicates that it has already been collected. A memory smash error may be detected using the following technique in one embodiment: at allocation, a "guard word" may be added to the end of the object with a value (which may be called a "magic number") that is unlikely to occur in the object. If, during a free( ) for the object, or in a heap check, the value is found to have been changed, a memory smash associated with the object is detected. Another type of memory management error, a memory leak (i.e., when an allocated object is never explicitly freed in the application) may be detected if unreachable objects are found in the heap. Other types of memory management errors may also be detected in some embodiments, such as late writes (writes to an object after the object has already been freed) and/or wild frees (attempts to free memory that was not dynamically allocated).

As shown in block 215 of FIG. 2, for each instance of a memory management error detected, memory management tool 120 may be configured to store an error record 170, e.g., in error database 150, indicating an allocation location of an object associated with or affected by the error. E.g., if object "A" allocated from allocation location "0x1abd32" is freed multiple times, or is involved in a memory smash, its allocation location may be identified as a potentially unsafe allocation location in an error record 170. The memory management tool 120 may, for example, look up an object (e.g., "A", "B", etc.) in allocation location database 140 corresponding to a memory address specified in the memory operation that results in an error, and store the allocation location of that object in the error record 170. That is, to generate an error record 170 for a memory management error, in some embodiments memory management tool 120 may search for an allocation location corresponding to an object involved in the error, or identified as an operand of the memory operation that resulted in the error. Various types of additional information may also be stored in the error record 170 in different embodiments, such as an error identifier, the type of the error, memory protection actions to be taken on objects allocated from the unsafe allocation location, etc.

In one embodiment, whenever an object is allocated (e.g., using malloc( )) during the application execution, memory management tool 120 may be configured to check whether the corresponding allocation location has previously been identified as an unsafe allocation location in error database 150. If the corresponding allocation location has been designated as an unsafe allocation location, the newly allocated object may be marked (e.g., using a header object of the type described above) as a memory protection candidate object 160. Memory management tool 120 may be configured to identify one or more memory operations performed on the memory protection candidate object (including, for example, the malloc( ) call itself, as well as free( ), realloc( ) and other memory management functions), as shown in b