C Linked List Memory Usage (Possible memory leak)

Question

Hi, I'm having trouble with what should be a simple program.

I've written a single linked list implementation in C using void* pointers. However, I have a problem, as there is a possible memory leak somewhere, however I checked the code using valgrind and it detected no such errors.

But when all the memory is free'd there is still some memory un-freed (see comments)... I tried passing everything to the add function by reference too, but this didn't fix the issue either.

I just wondered if anyone here had any comments from looking at the code. (This should be simple!, right?)

/*
 Wrapping up singley linked list inside a struct
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* Needed for: memcpy */

void waitKey(){
 printf("Press any key to continue...");
 getchar();
}

/* Define a structure for a list entry */
struct ListEntry {
 void* data;
 struct ListEntry* pNext;
};

/* Struct for list properties */
struct ListProperties {
 struct ListEntry* g_pLast;
 struct ListEntry* g_pHead;
 struct ListEntry* pCurrent;
 unsigned int size;
 int getHead;
};

/* Add:
 args: list, data, dyn (0 if not, else size of dynamic data)
*/
void add(struct ListProperties* l, void* d, unsigned long dyn) {
 struct ListEntry* pNew = malloc(sizeof(struct ListEntry));

 /* Set the data */
 if (dyn > 0){
  /* Allocate and copy array */
  pNew->data = malloc(dyn);
  pNew->data = memcpy(pNew->data,d,dyn);
 } else {
  pNew->data = d;
 }

 /* Set last element to point to new element */
 if (l->g_pLast != NULL){
  l->g_pLast->pNext = pNew;

  /* Get head of list */
  if (l->g_pHead == NULL && l->getHead == 0){
   l->g_pHead = l->g_pLast;
   l->getHead = 1;
  }
 } else {
  /* 1 elem case */
  l->g_pHead = pNew;
  l->pCurrent = pNew;
 }

 /* New element points to NULL */
 pNew->pNext = NULL;

 /* Save last element for setting 
    pointer to next element */
 l->g_pLast = pNew;

 /* Inc size */
 l->size++;
}

/* Create new list and return a pointer to it */
struct ListProperties* newList(){
 struct ListProperties* nList = malloc (sizeof(struct ListProperties));
 nList->g_pHead = NULL;
 nList->g_pLast = NULL;
 nList->getHead = 0;
 nList->size = 0;
 return nList;
}

/* Reset pointer */
int reset(struct ListProperties *l){
 if (l->g_pHead != NULL){
  l->pCurrent = l->g_pHead;
  return 0;
 }
 return -1;
}

/* Get element at pointer */
void* get(struct ListProperties *l) {
 if (l->size > 0){
  if (l->pCurrent != NULL){
   return l->pCurrent->data;
  }
 }
 return NULL;
}

/* Increment pointer */
int next(struct ListProperties *l){
 if (l->pCurrent->pNext != NULL){
  l->pCurrent = l->pCurrent->pNext;
  return 1;
 }
 return 0;
}

/* Get element at n */
void* getatn(struct ListProperties *l, int n) {
 if (l->size > 0){
  int count = 0;
  reset(l);
  while (count <= n){
   if (count == n){
    return l->pCurrent->data;
    break;
   }
   next(l);
   count++; 
  }
 }
 return NULL;
}

/* Free list contents */
void freeList(struct ListProperties *l){
 struct ListEntry* tmp;

 /* Reset pointer */
 if (l->size > 0){
  if (reset(l) == 0){
   /* Free list if elements remain */
   while (l->pCurrent != NULL){
    if (l->pCurrent->data != NULL)
     free(l->pCurrent->data);
    tmp = l->pCurrent->pNext;
    free(l->pCurrent);
    l->pCurrent = tmp;
   }
  }
 }

 l->g_pHead = NULL;
 l->g_pLast = NULL;

 l->size = 0;
 l->getHead = 0;

 free(l);
}

void deleteElem(struct ListProperties *l, int index){
 struct ListEntry* tmp;
 int count = 0;
 if (index != 0)
  index--;
 reset(l);
 while (count <= index){
  if (count == index){ // Prev element
   if (l->pCurrent != NULL){
    if (l->pCurrent->pNext != NULL){
     free(l->pCurrent->pNext->data); // Free payload
     tmp = l->pCurrent->pNext;
     l->pCurrent->pNext = l->pCurrent->pNext->pNext;
     free(tmp);
     if (l->size > 0)
      l->size--;
    } else {
     // Last element
     free(l->pCurrent->data);
     free(l->pCurrent);
     l->g_pHead = NULL;
     l->g_pLast = NULL;
     l->getHead = 0;
     l->size = 0;
    }
   }
   break;
  }
  if (next(l) != 1)
   break;
  count++;
 }
}

int size(struct ListProperties *l){
 return l->size;
}

int main( int argc, char* argv )
{
 int j = 0;
 unsigned long sz = 0;

 /*=====| Test 1: Dynamic strings |=====*/

 /* Create new list */
 struct ListProperties* list = newList();

 if (list == NULL)
  return 1;

 char *str;
 str = malloc(2);
 str = strncat(str,"A",1);
 sz = 2;

 printf("Dynamic Strings\n===============\n");

 /* Check memory usage here (pre-allocation) */
 waitKey();

 /* Add to list */
 for (j = 0; j < 10000; j++){
  add(list,(char*)str, sz);
  str = realloc(str, sz+2);

  if (str != NULL){
   str = strncat(str,"a",1);
   sz++;
  }
 }

 /* Allocated strings */
 waitKey();

 /* TESTING */
 freeList(list);
 free(str);

 /* Check memory usage here (Not original size!?) */
 waitKey();
 return 0;
}

Thanks!

Answer 1

You don't say how you are checking memory usage, but I'm going to guess that you are using ps or something similar to see how much memory the OS has given the process.

Depending no your memory allocator, calling free may or may not return the memory to the OS. So even though you are calling free, you will not see the memory footprint decrease from the OS's point of view.

The allocator may keep a cache of memory that is given to it by the OS. A call to malloc will first look in this cache to see if it can find a big enough block and if so, malloc can return without asking the OS for more memory. If it can't find a big enough block, malloc will ask the OS for more memory and add it to it's cache.

But free may simply add the memory back to the cache and never return it to the OS.

So, what you may be doing is seeing the allocators cache and not any memory leak.

Answer 2

As was mentioned, I would not trust the memory usage reported by the task manager as there are other factors beyond your control that impact it (how malloc/free are implemented, etc).

One way you can test for memory leaks is by writing your own wrapper functions around the existing malloc and free functions similar to:

void* my_malloc(size_t len) {
    void* ptr = malloc(len);
    printf("Allocated %u bytes at %p\n", len, ptr);
    return ptr;
}

void my_free(void* ptr) {
    printf("Freeing memory at %p\n", ptr);
    free(ptr);
}

Now, you will get a log of all memory that is dynamically allocated or freed. From here, it should be fairly obvious if you leak a block of memory (the more complex your program is, the longer your log will be and the more difficult this task will be).

Answer 3

Your program contains incorrect argv in main, incorrect usage of strncat, and strange memory allocation. Some of these should of shown up as warnings. The argv is a non-issue, but if the others showed up as warning, you needed to heed them. Don't ignore warnings.

These changes clean it up. The biggest thing was that you don't seem to have a good grasp on the NUL ('\0') character (different than NULL pointer) used to terminate C strings, and how that effects str(n)cat.

The mixed usage of str* functions with memory functions (*alloc/free) was likely part of the confusion. Be careful.

 #include <assert.h>
 ...
 int main( int argc, char* argv[] )       /* or int main(void) */
 ...
 sz = 2;
 str = (char*) malloc(sz);       /* allocate 2 bytes, shortest non-trivial C string */
 assert(str != NULL);
 strncpy(str, "A", sz);          /* copy 'A' and '\0' into the memory that str points to */
 ...
/* Add to list */
 for (j = 0; j < 10000; j++){
  add(list, str, sz);
  str = realloc(str, ++sz);      /* realloc str to be one (1) byte larger */
  assert(str != NULL);

  strncat(str, "a", sz - strlen(str));    /* now insert an 'a' between last 'A' or 'a' and '\0' */
  assert(str != NULL);
 }