Memory Leaks...Explained (hopefully)

Question

Could someone please help me understand the concept of memory leaking and how specific data structures promote/prevent it (e.g. linked lists, arrays etc). I've been taught it twice by 2 different people a while ago - which has confused me slightly because of the differences in teaching methods.

Answer 1

Wikipedia has a good description on memory leaks. The defintion given there is:

A memory leak, in computer science (or leakage, in this context), occurs 
when a computer program consumes memory but is unable to release it back 
to the operating system.

For example, the following C function leaks memory:

void leaky(int n)
{
    char* a = malloc(n);
    char* b = malloc(n);
    // Do something with a
    // Do something with b
    free(a);
}

The above function leaks n bytes of memory as the programmer forgot to call free(b). What that means is that the operating system has n bytes less memory to satisfy further calls to malloc. If the program calls leaky many times, the OS may eventually run out of memory that it could allocate for other tasks.

As for the second part of your question, there is nothing intrinsic to data structures that makes them leak memory, but a careless implementation of a data structure could leak memory. As an example, consider the following function that deletes an element from a linked list:

// I guess you could figure out where memory is leaking and fix it.

void delete_element(ListNode* node, int key)
{
    if (node != NULL)
    {
        if (node->key == key)
        {
            if (node->prev != NULL) {
                // Unlink the node from the list.
                node->prev->next = node->next;
            }
        }
        else
        {
            delete_element(node->next, key);
        }  
    }
}

Answer 2

I agree with Vijay's answer for the most part, but it is important to note that leaks occur when references to heap blocks (pointers) are lost. The two common causes are:

1 - Losing scope of the pointer

void foo(void)
{
    char *s;
    s = strdup("U N I C O R N S ! ! !");
    return;
}

In the above, we've lost scope of the pointer s, so we have absolutely no way to free it. That memory is now lost in (address) space until the program exits and the virtual memory subsystem reclaims everything the process had.

However, if we just changed the function to return strdup("U N I C O R N S ! ! !");, we'd still have reference to the block that strdup() allocated.

2 - Re-assigning pointers without saving the original

 void foo(void)
 {
      unsigned int i;
      char *s;

      for (i=0; i<100; i++)
         s = strdup("U N I C O R N S ! ! !");

      free(s);
  }

In this example, we've lost 99 references to blocks that s once pointed to, so we're only actually freeing one block at the end. Again, this memory is now lost until the OS reclaims it after the program exits.

Another typical misconception is that memory that is still reachable at program exit is leaked if the program does not free it prior to exiting. This has not been true for a very long time. A leak only happens when there is no way to dereference a previously allocated block in order to free it.

It should also be noted that dealing with the static storage type is a little different, as discussed in this answer.