Why does this code sample produce a memory leak?

Question

In the university we were given the following code sample and we were being told, that there is a memory leak when running this code. The sample should demonstrate that this is a situation where the garbage collector can't work.

As far as my object oriented programming goes, the only codeline able to create a memory leak would be

items=Arrays.copyOf(items,2 * size+1); 

The documentation says, that the elements are copied. Does that mean the reference is copied (and therefore another entry on the heap is created) or the object itself is being copied? As far as I know, Object and therefore Object[] are implemented as a reference type. So assigning a new value to 'items' would allow the garbage collector to find that the old 'item' is no longer referenced and can therefore be collected.

In my eyes, this the codesample does not produce a memory leak. Could somebody prove me wrong? =)

import java.util.Arrays;
public class Foo  
{  
private Object[] items;  
private int size=0;  
private static final int ISIZE=10;

public Foo()  
{  
  items= new Object[ISIZE];  
}  

public void push(final Object o){  
  checkSize();  
  items[size++]=o;  
}  

public Object pop(){  
  if (size==0)  
    throw new ///...  
  return items[--size];  
}  
private void checkSize(){  
  if (items.length==size){  
    items=Arrays.copyOf(items,2 * size+1);  
  }  
}  
}

Answer 1

Hint: the leak is in the pop method. Consider what happens to the references to a popped object ...

Answer 2

This example is discussed in Effective Java by Joshua Bloch. The leak is when popping elements. The references keep pointing to objects you don't use.

Answer 3

It's not a priori true that there's a memory leak here.

I think the prof has in mind that you're not nulling out popped items (in other words, after you return items[--size], you probably ought to set items[size] = null). But when the Foo instance goes out of scope, then everything will get collected. So it's a pretty weak exercise.

Answer 4

Hint: Imagine what happens if you use a Foo object, insert into it 10000 "heavy" items, and then remove all of them using pop() because you don't need them anymore in your program.

Answer 5

I'm not going to flat out give you the answer, but look at what push(Object o) does that pop() doesn't do.

Answer 6

In the pop() method, the item on the size (i.e, items[size-1]) is not set to NULL. As a result, there still exists reference from objects items to items[size-1], although size has been reduced by one. During GC, items[size-1] won't be collected even if there is no other object pointing to it, which leads to memory leak.

Answer 7

Consider this demo:

Foo f = new Foo();
{
    Object o1 = new Object();
    Object o2 = new Object();
    f.push(o1);
    f.push(o2);
}

f.pop();
f.pop();

// #1. o1 and o2 still are refered in f.items, thus not deleted

f = null;

// #2. o1 and o2 will be deleted now

Several things should be improved in Foo which will fix this:

1. In pop, you should set the items entry to null.
2. You should introduce the opposite to checkSize, something like shrinkSize, which will make the array smaller (maybe in a similar way to checkSize).

Answer 8

The pop method produces the memory leak.

The reason is that you only reduce the number of items that are in the queue, but you don't actually remove them from the queue.The references remain in the array. If you don't remove them, the garbage collector, won't destruct the objects, even if the code that produced the object is executed.

Imagine this:

{
    Object o = new Object();
    myQueue.add(o);
}

Now you have only one reference for this object - the one in the array.

Later you do:

{
    myQueue.pop();
}

This pop doesn't delete the reference. If you don't remove the reference the Garbage collector will think that you are still thinking of using this reference and that this object is useful.

So if you fill the Queue with n number of objects then you will hold reference for these n objects.

This is a the memory leak your teachers told you about.

Answer 9

Memory leaks are defined as unbounded growth in allocation caused by ongoing execution.

The explanations provided explain how objects could continue to be held active through references in the stack after popping, and can certainly result in all kinds of misbehaviour (for example when the caller releases what they think is the last reference and expects finalisation and memory recovery), but can hardly be called leaks.

As the stack is used to store other object references the previous orphaned objects will become truly inaccessible and be returned to the memory pool.

Your initial skepticism is valid. The code presented would provide bounded memory use growth with convergence to a long-term state.

Answer 10

The code sample doesn't produce a leak. It's true that when you call pop(), the memory isn't freed for the appropriate object - but it will be when you next call push().

It's true that the sample never releases memory. However, the unreleased memory is always re-used. In this case, it doesn't really fit the definition of memory leak.

for(int i = 0; i < 1000; i++)
    foo.push(new Object());
for(int i = 0; i < 1000; i++)
    foo.pop();

This will produce memory that isn't freed. However, if you ran the loop again, or a hundred thousand million times, you wouldn't produce more memory that isn't freed. Therefore, memory is never leaked.

You can actually see this behaviour in many malloc and free (C) implementations- when you free memory, it isn't actually returned to the OS, but added to a list to be given back next time you call malloc. But we still don't suggest that free leaks memory.