Automatic removal of array memory leaks

Details Automatic removal of array memory leaks Automatic removal of array memory leaks

2000-06-30

2004-01-06

Nguyen-Ba, Hoang-Vu Antony (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S118000, C717S130000, C712S002000, C712S227000, C712S244000

Reexamination Certificate

active

06675379

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to efficient use of computer memory in carrying out program instructions, and specifically to methods and apparatus for garbage collection, i.e., for automatic reclamation of unused memory.
BACKGROUND OF THE INVENTION
Programming languages such as Java relieve the programmer of the burden of explicit memory management through the use of automatic garbage collection (GC) techniques that are applied “behind the scenes.” Unused data objects, which are not reachable by the running program via any path of pointer traversals, are considered “garbage.” GC automatically reclaims computer storage assigned to such objects, in order to free the storage for reuse. This makes programming in garbage-collected languages significantly easier than in C or C++, for example, in which the programmer must include an explicit “free” statement in order to reclaim memory. It allows many run-time errors to be avoided and naturally supports modular programming. A survey of basic GC techniques is presented in an article by Wilson, entitled “Uniprocessor Garbage Collections Techniques,” in the proceedings of the 1992
International Workshop on Memory Management
(Springer-Verlag Lecture Notes in Computer Science), which is incorporated herein by reference.
Run-time GC, as is performed by a Java Virtual Machine (JVM), does not (and in general cannot) collect all the garbage that a program produces. GC typically collects objects that are no longer reachable from a set of root references. However, there are some objects that the program never accesses again, even though they are reachable. Failure to reclaim memory at the proper point may lead to memory “leaks,” with unreclaimed memory accumulating until the program terminates or memory space is exhausted. Such leaks may lead to performance slowdown and to the program running out of memory space. Some Java programmers try to circumvent these memory leaks by rewriting their source code, i.e., explicitly assigning “null” to object references that are known not to be used again. Such solutions may lead to erroneous (or even slower) programs and may even be eliminated by optimizing compilers.
For example, a standard Java implementation of a stack data structure is shown in Table I below. (Certain lines in the program are marked “s”, “S′” and “s″” for later reference.) After a successful “pop,” the current value of “stack[top]” is not subsequently used. Current garbage collection techniques fail to identify memory leaks of this sort; thus, storage allocated for elements popped from the stack may not be freed in a timely manner.
TABLE I
public Class Stack {
private Object stack[];
private int top;
public Stack(int len) {
stack = new Object[len];
top = 0;
}
public synchronized Object pop() {
top --;
s:
return stack[top]; +
}
public synchronized void push(Object o) {
s′:
stack[top]=o;
top++;
}
public synchronized void print() {
for (int i=0; i<top; i++) {
s″:
System.out.println(stack[i]);
}
}
}
A typical solution to avoid these memory leaks is to explicitly assign “null” to array elements that are no longer needed. For example, a stack implementation, which avoids these leaks, is shown in Table II below, wherein “null” is explicitly assigned to “stack[top].”
TABLE II
public Class Stack {
private Object stack[];
private int top;
public Stack(int len) {
stack = new Object[len];
top = 0;
}
public synchronized Object pop() {
Object tmp;
top --;
tmp = stack[top];
stack[top]=null;
return tmp;
}
public synchronized void push(Object o) {
stack[top]=o;
top++;
}
public synchronized void print() {
for (int i=0; i<top; i++) {
System.out.println(stack[i]);
}
}
}
Explicit solutions of the type shown in Table II have the following drawbacks:
Explicit memory management complicates program logic and may lead to bugs; by trying to avoid memory leaks, a programmer may inadvertently free an object prematurely.
GC considerations are not part of the program logic; thus, they are surely not a good programming practice. In fact, the whole idea of GC-aware programs defeats some of the purposes of automatic GC.
Aiding the memory management task may require knowledge of the GC algorithm, which is implementation-dependent. This may lead to programs that depend on a particular GC algorithm.
The solution of explicitly assigning “null” may slow the program, since such “null” assignments are performed as part of the program flow. For example, consider the method “removeAllElements” of class “java.util.Vector,” taken from a Java utilities package called “java.util,” offered by Sun Microsystems and shown in Table III below. The only reason for the loop in the method is to allow GC to free the array elements.
An optimizing compiler may deduce that “null” assignment statements have no effect, thus eliminating them.
TABLE III
synchronized void removeAllElements() {
for (int i=0; i < elementCount; i++) {
elementData[i]= null;
}
elementCount=0;
}
The above limitations lead to the conclusion that programmers should be freed from dealing with these memory management considerations and that the leaks should be detected by automatic means, such as by compiler analyses.
“Liveness analysis” is a method of data flow analysis that has been developed for use in software optimization and validation. It is described, for example, by Nielson et al., in
Principles of Program Analysis
(Schloss Dagstuhl, Germany, 1998), which is incorporated herein by reference. The analysis is typically performed by tracing the program flow backwards, from end to beginning. A variable is considered “live” before a program point if there exist an execution sequence in the program including the program point and a use of the current value of the variable, such that the program point occurs before the use of the current value of the variable, and the variable is not reassigned before the use.
The use of liveness analysis for garbage collection in Java is proposed by Agesen et al., in an article entitled “Garbage Collection and Local Variable Type-Precision and Liveness in Java™ Virtual Machines,” in the proceedings of the
ACM SIGPLAN Conference on Programming Language Design and Implementation
(Montreal, June, 1998), which is incorporated herein by reference. This liveness analysis is applied to references held by local variables and leads to a reduced root set, enabling more memory to be reclaimed. The main benefit found by the authors in using liveness analysis for GC was in “preventing bad surprises.” There is no suggestion in the article as to how liveness analysis might be applied to arrays of objects.
Analysis of relationships between variables has been used to analyze array accesses, generally for purposes of parallelizing software compilers and array reference analyses. A precise method for this purpose is described by Cousot et al., in an article entitled “Automatic Discovery of Linear Restraints among Variables of a Program,” in the
Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages
(Tucson, Ariz., January, 1978), which is incorporated herein by reference. Cousot's method automatically identifies linear relationships between variables by scanning the data flow graph of a program in a forward direction. Analysis of relationships between variables can be extended to detect the minimal and maximal values used as array indices, thus allowing the removal of checks for array bounds violations.
For similar purposes, certain programming languages, such as CLU, provide built-in dynamic arrays that can be used to implement stacks and vectors. The number of element

Affiliated with

Also associated with

Rating

Automatic removal of array memory leaks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Automatic removal of array memory leaks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic removal of array memory leaks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3245705