Memory Fragmentation with Dynamic FIFO Queue

I have recently witten the code for a dynamic FIFO queue that has nodes that can have variable size. I have thoroughly tested the code and the init/add/remove operations work flawlessly. I have even run it agains valgrind to verify that there are no memory leaks when allocating and freeing nodes. I am currently running the program I have written on Debian 5.0 kernel 2.6.26 with the default OS settings. I have not performed any memory tweaks to tune for performance etc. All of the allocations for each node in the queue are handled using the default malloc() and free().

The problem I have with my queue occurs when I add a large number of small items to the queue. I have been watching my memory usage via the System Monitor in Debian and after adding 4000 items of size 1518 each to the queue my memory usage jumps just as expected. However, when I move through my queue and remove each item the memory usage does not appear to go down. When I run this test again without restarting my program the system does not allocate any further memory than was allocated in the first run. It appears as though it reuses memory that was allocated previously. I ran a second test and instead of adding a large number of small nodes to the queue I just added 30 items containing 10MB each and then emptied my queue again. This time the memory went up as expected and came back down as expected. I have been researching this problem for a few days now and I believe I have discovered the problem but have been unable to decide on reasonable solution.

Basically what I have determined is that when i call free() to free my nodes the memory is not being returned to the operating system. I found a good explaination at the link below.

When Linux Runs Out of Memory - O'Reilly Media

It states:

"The decision on whether to use brk() or mmap() requires one simple check. If the request is equal or larger than M_MMAP_THRESHOLD, the allocator uses mmap(). If it is smaller, the allocator calls brk(). By default, M_MMAP_THRESHOLD is 128KB, but you may freely change it by using mallopt().

In the OOM context, how ptmalloc frees memory blocks is interesting. Blocks allocated via mmap() get freed via an unmap() call, and thus become completely released. Freeing blocks allocated via brk() means marking them as free, but they remain under the allocator's control."

Because the small blocks I am allocating are smaller than the mmap threshold they are being allocated by brk() and brk does not release freed memory back to the OS right away. I am assuming it does this mostly for performance gains. Apparently it reuses the allocated memory for future requests.

This is a big problem for me because in my software that uses my queue I also report on the amount of free memory the system currently has. Anomalies such as what I have just described above cause the memory usage updates sent from my program to give a completely inaccurate representaion of the amount of memory currently being used. In addition, what I have also noticed is that as I continue to add/remove more and more items I begin to notice a fairly large and rapid performance degredation with my software. I don't know if what I described above is actual "memory fragmentation". I have always thought that memory fragmentation occured as a result of blocks of allocated memory not being used at all by the software. I am using all of the blocks I allocate, they just dont appear to be freeing in the manner I would like them to. Furthermore, my queue is only a small portion of my software that will be performing these types of small memory allocations. I have other modules that will be performing very similar allocations and I expect to take even larger memory reporting inaccuracies and performance hits.

I have thought of various solutions:

1. Use a different memory allocator
2. Allocate large chunks of memory ahead of time and manage the memory myself. (This is very difficult because my queue could become very large)
3. Adjust the management parameters for malloc so that it does not use brk (have had no success with this)

Any help or suggestions would be greatly appreciated.

So you don't like the default implementation of malloc(). Big deal. Implement your own allocator and move on.

That was less than helpful.

You are working with a general-purpose operating system with many layers of complexity. If you want precise control over the allocation/deallocation of pages, you need to use mmap() and throw your own allocator on the top of it.

You might be able to fix these "anomalies" for your own software, but every other program on the system is also affected. Trying to produce an accurate number by adding up a bunch of inaccurate numbers is a losing proposition.

The very concept of how much memory is "free" isn't well-defined in a virtual memory environment. You're trying to measure something that can't be measured.

This is pretty much the same conclusion I have come to after all the research I have done. However, it blows my mind that a user of the linux operating system has no way of knowing when their system is actually low on memory. The statistics returned by the System Monitor are completely inaccurate. You would think that at some point they would try to remedy this whole situation.

Nope, Linux users just know how to interpret that data.

So, assuming you are a "Linux user", how would you interpret the exact (or as close as possible) amount of memory that your Linux system is currently using? Because your response above seems to negate what you have just posted. First you said that it is a losing battle to make this calculation and now you say that linux users know how to do it.

didnt realize the last post was from diff person.. sorry

I am getting conflicting answers here.. can it be done or not?

Basically what I need to know now is how do i know when my system is going to be critically low on memory when the calculations I am performing are inaccurate. What calculation should I be performing because the System Monitor calculation is not correct for % mem free?

By looking at it with the naked eye -- using the human brain to gather the data and interpret it? YES. Using a computer program to figure it out -- probably not. There are way too many variables at play. The brain can look at all the data and go -- Hmm, I'm outta memory here. A program, however, can only see things as 1 or 0 -- SO, no, there is no way to do it in code.

Just be consistent on whatever numbers you do report. See "ps", "top", and "vmstat" commands.

As for getting malloc() to behave a certain way, I would consult the manual - The GNU C Library - GNU Project - Free Software Foundation (FSF) (also where mallopt is documented).

>> Basically what I need to know now is how do i know when my system is going to be critically low on memory
Why does your app "need" to know this? What does"critically low" actually means to you and your app?

gg

Quote:

---

Originally Posted by Codeplug

Why does your app "need" to know this? What does"critically low" actually means to you and your app?

---

I agree. Let the operating system manage it. Maybe you add up a bunch of numbers and come to the conclusion that you're "out of memory" so you bail. But how do you know the kernel doesn't have some trick up its sleeve that will make everything a-okay? You just gave up for nothing.

Besides, the fact that you have tons of memory right now doesn't mean you'll still have tons of memory 100 milliseconds from now. Some other program could suddenly allocate a huge chunk. It's like trying to measure the location of an electron.

The application I have written allocates a very large amount of memory, and it is entirely possible that it will eventually consume it all. If I can deallocate this memory or stop allocating more when it reaches a certain threshold I can prevent this situation from occuring. The problem is that I have no way of actually determining when the system is low because Linux works so much magic behind the scenes.

This software I am writing is the only major application on the machine so it essentially has all of the memory available to it and does not have to worry about other programs allocating a lot of memory. Because of this I may just begin managing blocks of free memory within my code using a ring buffer or something similar. Then I would not have to deal with the numerous amounts of malloc() and free() pairs that are causing me problems. However, this approach will involve more overhead on my cpu's which I am not too fond of given the performance I am trying to squeeze out of the machine.

>> If I can ... I can prevent this situation from occurring.
What "situation" are you trying to prevent?

>> Then I would not have to deal with the numerous amounts of malloc() and free() pairs that are causing me problems.
I'm not clear on what the "problems" are.

Why not just check for a 0 return from malloc and react then? Zero from malloc is a good indicator that things are getting tight :)

The malloc/free implementation in glibc has been optimized by a lot of smart folks. Adding "variable-sized chunk management" code on top of large blocks returned by malloc doesn't make much sense in my mind.

gg

OK. I have run tests and what I have found out is that the 128KB threshold mentioned in the above quote is either inaccurate or outdated. The allocator only holds onto a chunk of allocated memory when it is has a total size that is less than or equal to 32672 bytes. This is essentially 4 pages worth of memory with a 96 byte gap which I am assuming is tied up in some sort of overhead with the allocator. I have tried this across two different platforms and versions of Linux and it seems to hold true. Based upon this I think I will just write a mask for my malloc() and free() methods that will keep track of the amount of memory my program has allocated. In these methods I can make a decision based upon the size of the chunk of data that is being allocated as to how it will be represented within the total memory used for my program ( i.e. whether or not the allocator will hold onto it or hand it directly back to the OS). I would rather not go through the trouble of managing my own allocator due to some current time constraints. Furthermore, it is not absolutely imperative that I know the exact memory usage but I would like to be within approximately 1%-5% accuracy and I think this method will achieve that goal. What are you thoughts on this approach?

By the way, I ran into an interesting scenario when attempting to determine the 32672 threshold I mentioned above. My test involved storing 50,000 items of 32673 bytes each into a queue. Each item was allocated using malloc() of course. What I noticed is that this scenario brings one of my cpu cores to 100% usage and takes approximately 5-10 times longer to allocate all of the items than the same scenario with 50,000 items of 32672 bytes each. I am assuming this has to do with the fact that each item that is allocated is forced to use 2 pages rather than one in this scenario with only one byte of data being allocated in each of the second pages, but I don't know why that would slow it down. I also tried this scenario at 32674 and received the same results so I guess there is a tremendous amount of overhead when the allocator is forced to put a very few number of bytes in the last page required to fill the allocation. Any thoughts on this scenario?

Thanks for all of your replies.

I'm not sure I understood the problem here, because I didn't read all the post, but, from what I read on the first post, did you think about using __libc_freeres?