Managing Realeyes Memory

I have been at work on a new project that I hope to announce soon. But at the moment I need a break to let the algorithm for a particularly tricky function to germinate. So I am going to describe how I do memory management in the Realeyes IDS.

First, I have to say that this is not a generic memory manager. It is specific to my application. It may be possible to adapt it to other applications, but the key word here is 'adapt'. However, it will hopefully give anyone who is considering doing their own memory management some food for thought.

The reason I do my own memory management is to avoid fragmentation. The Realeyes IDS manages a lot of sessions simultaneously, so memory has to be used efficiently as possible. If a buffer were allocated for exactly the size of a packet's data, the overall buffer space would develop lots of pockets of unusable space. But to set the size of data buffers to the largest allowed by the Internet Protocol would also be inefficient, because there are a huge number of tinygrams in network traffic.

The solution is a compromise. I allocate fixed size buffers in sizes that are designed to waste as little space as possible. The smallest is 64 bytes. The next is 105 bytes, and the next, 128 bytes. So if 56 bytes are needed, the first size buffer is allocated. If 65 bytes are needed, the second. And if 108 bytes are needed, the third.

If you did a double take on the 105 byte buffer size, there is a method to my madness. These buffers are kept in pools of 8 Kilobytes. A 64 byte buffer pool will hold 256 buffers, and a 128 byte buffer pool will hold 64 buffers. Both of these will fit exactly into the 8K pool with no wasted space. To fine tune this a bit, I found the buffer size between them that wastes the least space. Allocating 78 buffers of 105 bytes each uses 8190 bytes, which wastes 2 bytes of space in an 8K pool.

Here is the complete list of buffer sizes: 64, 105, 128, 195, 256, 390, 512, 744, 1024, 2048, 4096, 8192. If larger sizes are needed, multiple adjacent pools are allocated, up to 64K. Again, this is specific to the Realeyes IDS application, which can guarantee that no buffer larger than 64K will ever be requested.

When the application is initialized, a huge buffer (many megabytes) is allocated and it is divided into 8K pools. Then, when a buffer is requested, if there is no pool for the appropriate buffer size already selected, the next available pool is assigned to provide buffers of that size only, and the first buffer in the pool is returned to the requester. If a pool already exists for the buffer size and has free buffers, a buffer from that pool is returned.

To handle the requests, each allocated pool is kept on one of three queues for that buffer size. The reason there are three is that the entire queue must be locked while buffers are being allocated or freed. The Realeyes IDS functions to handle semaphores allow for a caller to request an immediate return if a lock is already held. This means that if one of the pool queues is in use, the caller can try the next one. The rae_mem_mgmt.c module keeps track of the last queue accessed and uses a simple round robin method to check the next queue.

So far, so good. But there are still some loose ends. What if all of the buffers in a pool are in use, and that pool is at the head of the pool queue? For that matter, what if the first 1,000 pools in a queue have no available buffers? This is where the manager comes in.

For each pool size there are Full and Free queues. The manager periodically (about 500 times a second) checks each of the available queues, removes all pools that have no available buffers, and puts them on the Full queue for that buffer size. Pools on the Full queue that have available buffers are put on the Free queue. And pools that are on the Free queue are divvied up so that each available queue has approximately the same number of pools.

There are a few other steps in managing the queues, which is done in rae_mem_ctl.c. If an allocated pool has all of its buffers freed, it is put on a general available queue to be reused for possibly a different buffer size. Also, there is a queue at each buffer size for full pools that have not had available buffers for a period of time. This is only checked once a second to see if buffers have been freed.

So does it work? In the pilot project I have been running for over a year, the statistics I have collected show that the average number of sessions being managed simultaneously is around 20,000. Assuming an average size of 16K per session, that is 325M of data, plus the application data about each session. And that is just a snapshot. There are many Gigabytes of data being examined over the course of an hour. When the IDS does run out of buffers (I'm working on it, OK?!?), it is because the application hasn't released them when it should, not because the memory management is bogging down.

So that's the essence of how memory management is handled in the Realeyes IDS. However, because the application uses multiple processes instead of threads, the memory must be shared. I will cover that in a future post.

Later . . . Jim