Freeing memory in C

[ipha]

I've been writing a linked list in C and everything works as expected except for freeing memory after removing a node.

In my test I added 10 000 000 entries to the list and removed them twice. However, instead of seeing the memory usage go down after removing them, it stayed at ~300mb even after adding and removing the next set.

Am I doing something wrong, or is this how it's supposed to work?

#include <stdio.h>
#include <stdlib.h>


typedef struct node{
	int data;
	struct node *previous;
	struct node *next;
} item;

item *current, *first, *last;
int count = 0;

void add(int data){
	current = (item *)malloc(sizeof(item));
	current->data = data;
	if(count == 0){
		current->next = current;
		current->previous = current;
		first = current;
		last = current;
		count++;
	}
	else{
		current->next = NULL;
		current->previous = last;
		last->next = current;
		last = current;
		count++;
	}
}
int pullLast(){
	if(count > 1){
		int ret;
		current = last;
		ret = current->data;
		last = last->previous;
		last->next = NULL;
		free(current);
		current = NULL;
		count--;
		return(ret);
	}
	else if(count == 1){
		int ret;
		current = last;
		ret = current->data;
		last = NULL;
		first = NULL;
		free(current);
		current = NULL;
		count--;
		return(ret);
	}
	else{
		return(0);
	}
}
int pullFirst(){
	if(count > 1){
		int ret;
		current = first;
		ret = current->data;
		first = first->next;
		first->previous = NULL;
		free(current);
		current = NULL;
		count--;
		return(ret);
	}
	else if(count == 1){
		int ret;
		current = last;
		ret = current->data;
		last = NULL;
		first = NULL;
		free(current);
		current = NULL;
		count--;
		return(ret);
	}
	else{
		return(0);
	}
}
	

int main (int argc, char *argv[])
{
	int i;
	printf("Empty list");
	getchar();
	for(i=0;i<10000000;i++){
		add(i);
	}
	printf("Done filling list"); //memory jumps to ~300mb
	getchar();
	for(i=0;i<10000000;i++){
		pullLast();
	}
	printf("List should be empty now"); //still at 300mb
	getchar();
	for(i=0;i<10000000;i++){
		add(i);
	}
	printf("Done filling list"); //still at 300mb
	getchar();
	for(i=0;i<10000000;i++){
		pullLast();
	}
	printf("List should be empty now"); //still at 300mb
	getchar();
	return(0);
}

[jA_cOp]

What are you using to determine the memory usage?

[ipha]

System monitor.

[jA_cOp]

That's not going to work. At first, your program requests a lot of memory and thus the OS increases your heap size to ~300MB, then when you free it, you just return it to the process heap. The heap size isn't decreased because the OS has enough memory to do without it at the moment, so it assumes that leaving the memory with you is the best option as you might use it again (and indeed you do allocate all that memory twice).

edit:

There's a lot of duplication going on in your code though, spotting bugs is going to require some effort. You should really clean it up.

[ipha]

Ok, is there anyway to return the memory to the OS?

[jA_cOp]

[QUOTE=IpHa;21190261]Ok, is there anyway to return the memory to the OS?[/QUOTE]

The OS will reclaim your unused heap memory when necessary. You don't have to worry about it.

And even if your platform API does support manually messing with the heap, the OS knows better than you how to handle that memory anyway.

[ipha]

Ok, I just started 5 instances and the memory did start to go down on the ones with empty lists. It's still kind of annoying though that it prefered using swap rather than freeing memory, but I guess it's working how it's supposed to.

[Pepin]

I think your problem is resolved, but if you're still concerned about your memory usage then try using chars where you don't need ints.

[Wyzard]

I don't think the OS has control of reclaiming heap memory from a process; the process has to voluntarily give it back. (I know this is true in Linux; I'm less sure about Windows.)

The memory allocator should return memory back to the OS when possible, but sometimes its hands are tied. The heap can only grow or shrink by moving the "top" end of it (known as the "program break") up or down, somewhat like a stack. If you do something like this:
[list]
[*]Allocate 300MB worth of objects
[*]Allocate another object, which gets placed just above the others in memory, at the top of the heap
[*]Free all the objects allocated in step 1
[/list]
you end up with 300MB of memory that's available for re-use [i]within[/i] your program, but can't be returned to the OS because that object from step 2 is still sitting there preventing the heap from shrinking back down.

[jA_cOp]

Your post is a bit contradictory. You assert that the OS has no control over reclaiming heap memory, yet you also mention that it can return memory back to the pool unless its hands are tied. Of course this is platform specific, but I'm fairly sure Windows will reduce heap sizes (although not below the default size, only if it has grown) when the "top" heap regions aren't used and it wants more memory.

[Wyzard]

It's the memory allocator within a process (e.g. free(), operator delete, etc.) that returns memory back to the kernel when it can. The kernel can't barge in and shrink the heap on its own initiative because it doesn't know what parts of the heap contain data that the process needs.

[Sakarias88]

Put this at the top of main to check for memory leaks.
"_CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);"

As Wyzard said you have to return manually allocated memory meaning that you have to delete the pointers after using them.

If you need any example I could send you my linked lists (queue, priority queue and stack).

[jA_cOp]

[QUOTE=Wyzard;21202879]It's the memory allocator within a process (e.g. free(), operator delete, etc.) that returns memory back to the kernel when it can. The kernel can't barge in and shrink the heap on its own initiative because it doesn't know what parts of the heap contain data that the process needs.[/QUOTE]

Of course; but that doesn't return memory back to the kernel, that returns memory back to the process heap. The process heap grows when you allocate memory beyond the default heap size, and shrinks whenever there are unused heap regions and the OS wants more memory.

edit:

I am talking about Windows, though, but I wouldn't be surprised if Linux did the same.

[Wyzard]

In Linux, the interface for both requesting memory from the OS and giving memory back to the OS is the [url=http://www.kernel.org/doc/man-pages/online/pages/man2/brk.2.html]brk()[/url] system call, which manipulates the size of the process's data segment.

When malloc() finds that the heap doesn't contain a large enough contiguous chunk of available memory to hold what it's being asked to allocate, it uses brk() to enlarge the data segment by an appropriate amount, asking the kernel to give the process more memory. Assuming that succeeds, it now has memory with which to satisfy the allocation request.

When free() finds that the heap is larger than it needs to be, it can use brk() again to shrink the data segment back down to a smaller size, releasing some memory back to the kernel so that it can be given to other processes. In other words, free() releases memory back to the process heap, and it [i]may[/i] also shrink the heap, releasing memory back to the OS. That's the only way the OS gets memory back. But the positions of allocated regions within the heap can limit how much it can shrink.

It's actually a little more complicated than this, because the mmap() system call can be used to create multiple heaps (more or less) that can each be returned the OS when it becomes empty. But the bookkeeping for that is more complicated, so it's not typically used for "normal" allocations.

I know less about Windows memory management, but in the documentation for [url=http://msdn.microsoft.com/en-us/library/aa366599(v=VS.85).aspx]HeapCreate()[/url] I don't see any mention of heaps ever shrinking. The existence of HeapCreate(), together with its sibling [url=http://msdn.microsoft.com/en-us/library/aa366700(v=VS.85).aspx]HeapDestroy()[/url], indicates that Windows supports multiple heaps (similar to the mmap() approach in Linux), though the implementation of malloc() probably just uses the default heap provided by [url=http://msdn.microsoft.com/en-us/library/aa366569(v=VS.85).aspx]GetProcessHeap()[/url].