Happy Tuesday! Hope you had a nice long weekend. Labor Day in Minnesota marks the official summer season. The Minnesota State Fair ended yesterday. It flags the start of public schools and public universities in our state. In general, private schools and universities start a few weeks earlier.
My wife and I did not have too many things to do over the long weekend. Pretty much we did some grocery shopping, walking, and cook meals. We did watch on Amazon Prime an interesting and somewhat older movie. Trumbo was released on DVD in September 15, 2009. The movie provides interesting facts about the Hollywood Blacklist. It describes interesting and dark moments for liberty and freedom in the USA. Hopefully we have learned something and it will not repeat. The black list has nothing to do with African Americans. These events are associated with white people that disagreed with the main stream ideas of the time. The movie starts in 1947, a few years after the WWII ended. When you get a chance spend a couple hours watching this movie.
On a separate note, this post has as of right now 9,037 subscribers. Thank you very much!!!
Now let’s take a look at the main subject for this post.
In the post Memory Pools – Revisited we covered an implementation of a memory pool that operated using storage O(n), where `n` stands for the number of blocks in the memory heap. Note that one of the constraints for the problem is that all memory blocks are of the same size. If interested in this problem, I suggest you take a quick look at the previous post here mentioned and then continue reading. I will wait for you…
… Welcome back.
In the previous implementation we used an array of pointers per memory heap to hold the addresses of the free memory blocks. In this post we will replace the array in order to use O(1) storage. This will be possible by building a linked list using the free memory blocks.
09/07/21 09:56:47 0x00001390 - MemoryPool <<< initializing all memory heaps line: 59420 ... 09/07/21 09:56:47 0x00001390 - MemoryPool <<< next: 0x00aa90f0 line: 59447 09/07/21 09:56:47 0x00001390 - MemoryPool <<< next: 0x00aa8fe8 line: 59447 09/07/21 09:56:47 0x00001390 - MemoryPool <<< next: 0x00a89cd8 line: 59447 09/07/21 09:56:47 0x00001390 - MemoryPool <<< next: 0x00a89bd0 line: 59447 09/07/21 09:56:47 0x00001390 - MemoryPool <<< next: 0x00000000 line: 59447 09/07/21 09:56:47 0x00001390 - MemoryPool <<< allocate and free memory from the heaps line: 59460 ... 09/07/21 09:56:47 0x00001390 - MemoryPool <<< memory: 0x00aa90f0 memory ==>memPoolID: 0 i: 0<== line: 59523 09/07/21 09:56:47 0x00001390 - MemoryPool <<< memory: 0x00aa90f0 memory ==>memPoolID: 0 i: 1<== line: 59523 09/07/21 09:56:47 0x00001390 - MemoryPool <<< memory: 0x00aa8fe8 memory ==>memPoolID: 0 i: 2<== line: 59523 09/07/21 09:56:47 0x00001390 - MemoryPool <<< memory: 0x00a89cd8 memory ==>memPoolID: 0 i: 3<== line: 59523 09/07/21 09:56:47 0x00001390 - MemoryPool <<< memory: 0x00a89cd8 memory ==>memPoolID: 0 i: 4<== line: 59523 09/07/21 09:56:47 0x00001390 - MemoryPool <<< memory: 0x00a89bd0 memory ==>memPoolID: 0 i: 5<== line: 59523 09/07/21 09:56:47 0x00001390 - MPAlloc <<< UNEXPECTED mpHeap[0]: 0x00000000 line: 59342 file ==>C:\SencorSource\source\testlib.c<== 09/07/21 09:56:47 0x00001390 - MPAlloc <<< retVal: -1052 line: 59382 file ==>C:\SencorSource\source\testlib.c<== 09/07/21 09:56:47 0x00001390 - MemoryPool <<< MPAlloc WAR_NO_MORE_MEMORY memory: 0x00000000 i: 6 line: 59492 file ==>C:\SencorSource\source\testlib.c<== 09/07/21 09:56:47 0x00001390 - MPAlloc <<< UNEXPECTED mpHeap[0]: 0x00000000 line: 59342 file ==>C:\SencorSource\source\testlib.c<== 09/07/21 09:56:47 0x00001390 - MPAlloc <<< retVal: -1052 line: 59382 file ==>C:\SencorSource\source\testlib.c<== 09/07/21 09:56:47 0x00001390 - MemoryPool <<< MPAlloc WAR_NO_MORE_MEMORY memory: 0x00000000 i: 7 line: 59492 file ==>C:\SencorSource\source\testlib.c<==
Before we look at some code, let’s take a look at the output of the test program.
The code is quite similar (if not the same) as in the previous implementation. We start by initializing our memory pools / heaps. For each pool, the address of each associated memory block is displayed. Note that for simplicity, our example uses a single memory pool. If interested, copy the code to your system and change some definition that we will cover shortly.
In this example we will have in a single heap four memory blocks.
On each pass of a loop, we allocate and use a block of memory. The block may or may not be release. This is the reason the same memory block is reused.
Our program attempts to get memory from the heap while it is empty. This is the reason we see the last two sets of messages.
// **** Memory Pool related ****
#define MAX_MEMORY_POOLS 1 // was: 1, 8
#define MAX_POOL_CAPACITY 1024
#define ALLOCATION_SIZE 256 // was: 127, 128, 256
// **** memory block ****
typedef union {
unsigned char data[ALLOCATION_SIZE];
unsigned long *next;
} MP_MEM_BLOCK;
We have a set of definitions for the number of memory pools, the total initial capacity of each memory pool, and the size of each allocation. Not much has changed from previous implementations.
The MP_MEM_BLOCK union is new. It is used to implement a free memory block and the necessary pointer to implement a linked list. The linked list replaces the array we used in the previous implementation.
A union is just a way to refer to the same piece of memory using different variables. In our case we can refer to it as a block of bytes or as a pointer to the next free memory block. You can read more about unions in Union Types (https://en.wikipedia.org/wiki/Union_type#C/C++).
// **** **** HANDLE mpMutex[MAX_MEMORY_POOLS]; void *mpHeap[MAX_MEMORY_POOLS];
We have two arrays in our implementation. Note that the first one could be replaced by a single definition. I left it as an array to further experiment with the problem using different sizes per memory partition / heap. The second array contains the pointer to the head of the linked list holding all the free blocks for each memory partition / heap.
In general, in a queue /list we have a head and a tail. In this case our queue has a single pointer because we are actually implementing a stack. We pull free blocks when memory is allocated and push memory when blocks are freed / released. Note that the name of the second array does not use the words queue or stack in its name.
int __stdcall MemoryPool (
)
// ***************************************************************@@
// - Exercise the memory pool(s).
// *****************************************************************
{
int memPoolID, // memory pool ID
retVal, // returned by this function
status; // returned by function calls
unsigned long *next; // next memory block in a heap
unsigned char *memory; // memory to be allocated
#ifdef CAKE
int traceExecution = 1; // for testing only
#endif
// **** initialization ****
retVal = 0; // hope all goes well
memory = (unsigned char *)NULL; // for starters
next = (unsigned long*)NULL; // for starters
// **** inform the user what is going on ****
EventLog(EVENT_INFO,
"MemoryPool <<< initializing all memory heaps line: %d ...\n\n",
__LINE__);
// **** initialize ALL the memory heaps ****
for (memPoolID = 0; memPoolID < MAX_MEMORY_POOLS; memPoolID++)
{
status = MPInit(memPoolID);
if (status != 0)
{
EventLog(EVENT_ERROR,
"MemoryPool <<< MPInit status: %d memPoolID: %d line: %d file ==>%s<==\n",
status, memPoolID, __LINE__, __FILE__);
retVal = status;
goto done;
}
}
// **** display free memory blocks in ALL heaps ****
for (memPoolID = 0; memPoolID < MAX_MEMORY_POOLS; memPoolID++)
{
// **** display the free memory blocks in this heap ****
next = mpHeap[memPoolID];
do {
// **** inform the user what is going on ****
EventLog(EVENT_INFO,
"MemoryPool <<< next: 0x%08lx line: %d\n",
(unsigned long)next, __LINE__);
// **** point to next free memory block OR exit loop ****
if (next != NULL)
next = *next;
else
break;
} while ((BOOL)(1 == 1));
}
// **** inform the user what is going on ****
EventLog(EVENT_INFO,
"MemoryPool <<< allocate and free memory from the heaps line: %d ...\n\n",
__LINE__);
// **** allocate and free memory from all pools ****
for (int memPoolID = 0; memPoolID < MAX_MEMORY_POOLS; memPoolID++)
{
// **** allocate memory from the specified pool ****
for (int i = 0; i < 8; i++) // 5, 8, 9, 13, 17
{
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MemoryPool <<< i: %d memory: 0x%08lx line: %d\n",
i, (unsigned long)memory, __LINE__);
// **** allocate memory from this pool ****
status = MPAlloc( memPoolID,
(void*)&memory);
// **** proceed based on the returned status ****
switch (status)
{
case 0:
// **** all is well so far ****
break;
case WAR_NO_MORE_MEMORY:
EventLog(EVENT_ERROR,
"MemoryPool <<< MPAlloc WAR_NO_MORE_MEMORY memory: 0x%08lx i: %d line: %d file ==>%s<==\n",
(unsigned long)memory, i, __LINE__, __FILE__);
// **** ignore this condition ****
continue;
break;
default:
EventLog(EVENT_ERROR,
"MemoryPool <<< MPAlloc status: %d i: %d line: %d file ==>%s<==\n",
status, i, __LINE__, __FILE__);
retVal = status;
goto done;
break;
}
// **** use the memory block ****
status = sprintf( (char*)memory,
"memPoolID: %d i: %d",
memPoolID, i);
if (status <= 0)
{
EventLog(EVENT_ERROR,
"MemoryPool <<< sprintf status: %d line: %d file ==>%s<==\n",
status, __LINE__, __FILE__);
retVal = WAR_INTERNAL_ERROR;
goto done;
}
// **** inform the user what is going on ****
EventLog(EVENT_INFO,
"MemoryPool <<< memory: 0x%08lx memory ==>%s<== line: %d\n",
(unsigned long)&memory[0], memory, __LINE__);
// **** free this memory block (if needed) ****
if (i % 3 == 0)
{
status = MPFree(memPoolID,
(void*)memory);
if (status != 0)
{
EventLog(EVENT_ERROR,
"MemoryPool <<< MPFree status: %d memory: 0x%08lx line: %d file ==>%s<==\n",
status, (unsigned long)memory, __LINE__, __FILE__);
retVal = status;
goto done;
}
}
// **** display free blocks in this memory pool ****
if (traceExecution != 0)
{
// **** display the free blocks in this heap ****
next = mpHeap[memPoolID];
do {
// **** inform the user what is going on ****
EventLog(EVENT_INFO,
"MemoryPool <<< next: 0x%08lx line: %d\n",
(unsigned long)next, __LINE__);
// **** point to next free memory block OR exit loop ****
if (next != NULL)
next = *next;
else
break;
} while ((BOOL)(1 == 1));
}
}
}
// **** clean up ****
done:
// **** inform the user what is going on ****
if ((retVal != 0) || (traceExecution != 0))
EventLog(EVENT_INFO,
"MemoryPool <<< retVal: %d line: %d file ==>%s<==\n",
retVal, __LINE__, __FILE__);
// **** inform the caller what went on ****
return retVal;
}
This code implements the test program.
The symbol CAKE is not defined.
As before, you can / should replace the EventLog() function with a printf() and remove the first argument.
We start by entering a loop to initialize each of the memory partitions. In our example we have a single partition.
After initialization, we display the address of each memory block in all the partitions. The way we do it is by traversing the stack from top to bottom.
We then enter a new loop in which we allocate a memory block from a memory partition. If the partition is empty, a message is displayed and the test program continues. This is why we see two error messages when we run the test code.
If all is well and we get a memory block, we use it and then display it.
We then decide if we wish to free the memory block or not. One way or the other, if we enable tracing, we will display the contents of the specified memory pool. Note that in our example, CAKE is not defined. You can specify a different symbol that is defined.
int __stdcall MPInit (
int mpName
)
// ***************************************************************@@
// - Initialize the specified memory pool.
// *****************************************************************
{
int retVal, // returned by this function
status; // returned by function calls
#ifdef CAKE
int traceExecution = 1; // for testing only
#endif
MP_MEM_BLOCK *memoryBlock; // memory block
// **** initialization ****
retVal = 0; // hope all goes well
memoryBlock = (MP_MEM_BLOCK*)NULL; // for starters
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPInit <<< mpName: %d line: %d\n",
mpName, __LINE__);
// **** perform sanity checks ****
if (MAX_POOL_CAPACITY % ALLOCATION_SIZE != 0)
{
EventLog(EVENT_ERROR,
"MPInit <<< UNEXPECTED MAX_POOL_CAPACITY: %d ALLOCATION_SIZE: %d line: %d file ==>%s<==\n",
MAX_POOL_CAPACITY, ALLOCATION_SIZE, __LINE__, __FILE__);
retVal = WAR_SYSTEM_CONFIGURATION_ERROR;
goto done;
}
if ((mpName < 0) ||
(mpName > MAX_MEMORY_POOLS))
{
EventLog(EVENT_ERROR,
"MPInit <<< UNEXPECTED mpName: %d line: %d file ==>%s<==\n",
mpName, __LINE__, __FILE__);
retVal = WAR_INVALID_ARGUMENT_VALUE;
goto done;
}
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPInit <<< sizeof(MP_MEM_BLOCK): %d line: %d\n",
sizeof(MP_MEM_BLOCK), __LINE__);
// **** loop allocating memory blocks for this heap ****
for (int i = 0; i < MAX_POOL_CAPACITY / ALLOCATION_SIZE; i++)
{
// **** allocate a memory block ****
memoryBlock = (unsigned long*)calloc( (size_t)1,
(size_t)sizeof(MP_MEM_BLOCK));
if (memoryBlock == (MP_MEM_BLOCK*)NULL)
{
EventLog(EVENT_ERROR,
"MPInit <<< UNEXPECTED calloc == NULL mpName: %d i: %d line: %d file ==>%s<==\n",
mpName, i, __LINE__, __FILE__);
retVal = WAR_NO_MORE_MEMORY;
goto done;
}
// **** point to next memory block ****
memoryBlock[0].next = mpHeap[mpName];
// **** heap points to first memory block ****
mpHeap[mpName] = memoryBlock;
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPInit <<< mpHeap[%d]: 0x%08lx line: %d\n",
mpName, mpHeap[mpName], __LINE__);
}
// **** initialize the mutex used to allocate memory for this pool ****
status = MutexInit( &mpMutex[mpName],
(BOOL)(0 == 1));
if (status != 0)
{
EventLog(EVENT_ERROR,
"MPInit <<< MutexInit status: %d mpName: %d line: %d file ==>%s<==\n",
status, mpName, __LINE__, __FILE__);
retVal = status;
goto done;
}
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPInit <<< mpMutex[%d]: 0x%08lx line: %d\n",
mpName, (unsigned long)mpMutex[mpName], __LINE__);
// **** clean up ****
done:
// **** inform the user what is going on ****
if ((retVal != 0) || (traceExecution != 0))
EventLog(EVENT_INFO,
"MPInit <<< retVal: %d line: %d file ==>%s<==\n",
retVal, __LINE__, __FILE__);
// **** inform the caller what went on ****
return retVal;
}
This function is used to initialize a memory partition. We just need to specify the name of the partition which has to be within a range.
Note that we define and set to NULL the memoryBlock variable.
We check that all the memory that will be allocated from the system will be used by checking the amount of memory allocated and the size of the free blocks.
We then enter a loop in which we allocate each memory block.
After allocating a memory block, we point to the next memory block which should be stored in the mpHeap array for this memory partition. We then update the value in the array to point to the block we allocated. As you can see, we are pushing into our stack free memory blocks, one at a time.
We then initialize a mutex. The reason for this is that in most real world situations, a memory heap could server different programs or threads. In this case we can ignore the mutex if you desire. The simplest way is to delete or comment out the mutex initialization.
int __stdcall MPAlloc (
int mpName,
void **memory
)
// ***************************************************************@@
// - Allocate memory from the specified memory pool.
// *****************************************************************
{
BOOL gotMutex; // got mutex flag
int retVal, // returned by this function
status; // returned by function calls
MP_MEM_BLOCK *memoryBlock; // memory block
#ifdef CAKE
int traceExecution = 1; // for testing only
#endif
// **** initialization ****
retVal = 0; // hope all goes well
gotMutex = (BOOL)(0 == 1); // for starters
memoryBlock = (MP_MEM_BLOCK*)NULL; // for starters
// **** perform sanity checks ****
if ((mpName < 0) ||
(mpName >= MAX_MEMORY_POOLS))
{
EventLog(EVENT_ERROR,
"MPAlloc <<< UNEXPECTED mpName: %d line: %d file ==>%s<==\n",
mpName, __LINE__, __FILE__);
retVal = WAR_INVALID_ARGUMENT_VALUE;
goto done;
}
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPAlloc <<< mpName: %d line: %d\n",
mpName, __LINE__);
// **** check the memory pointer ****
if (memory == (void *)NULL)
{
EventLog(EVENT_ERROR,
"MPAlloc <<< UNEXPECTED memory: 0x%08lx line: %d file ==>%s<==\n",
memory, __LINE__, __FILE__);
retVal = WAR_INVALID_ARGUMENT_VALUE;
goto done;
}
// **** set the associated memory block to NULL ****
*memory = (void *)NULL;
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPAlloc <<< mpMutex[%d]: 0x%08lx line: %d\n",
mpName, (unsigned long)mpMutex[mpName], __LINE__);
// **** get access to the mutex ****
status = MutexLock(&mpMutex[mpName]);
CDP_CHECK_STATUS("MPAlloc <<< MutexLock", status);
// **** flag that we have the mutex ****
gotMutex = (BOOL)(1 == 1);
// **** check if we are out of free memory in this heap ****
if (mpHeap[mpName] == NULL)
{
EventLog(EVENT_ERROR,
"MPAlloc <<< UNEXPECTED mpHeap[%d]: 0x%08lx line: %d file ==>%s<==\n",
mpName, mpHeap[mpName], __LINE__, __FILE__);
retVal = WAR_NO_MORE_MEMORY;
goto done;
}
// **** get the first memory block from the heap ****
memoryBlock = (MP_MEM_BLOCK*)mpHeap[mpName];
// **** update heap pointer ****
mpHeap[mpName] = memoryBlock->next;
// **** clear the memory block ****
memset((void*)memoryBlock->data, (int)0x00, (size_t)ALLOCATION_SIZE);
// **** point to the memory block ****
*memory = (void*)memoryBlock;
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPAlloc <<< *memory: 0x%08lx *memory ==>%s<== line: %d\n",
(unsigned long)*memory, *memory, __LINE__);
// **** clean up ****
done:
// **** release the mutex (if needed) ****
if (gotMutex)
{
status = MutexUnLock(&mpMutex[mpName]);
if (status != 0)
EventLog(EVENT_ERROR,
"MPAlloc <<< MutexUnLock status: %d mpMutex[%d]: 0x%08lx line: %d file ==>%s<==\n",
status, mpName, (unsigned long)mpMutex[mpName], __LINE__, __FILE__);
}
// **** inform the user what is going on ****
if ((retVal != 0) || (traceExecution != 0))
EventLog(EVENT_INFO,
"MPAlloc <<< retVal: %d line: %d file ==>%s<==\n",
retVal, __LINE__, __FILE__);
// **** inform the caller what went on ****
return retVal;
}
This function is called when allocating memory from our test program. Since all the heaps use the same size, we do not need to be concerned at this point with the memory size. If each pool would use a different memory size, then we would have to pass the desired memory size to this call. In addition we would have to make some changes to the function that initializes each memory partition.
After a few checks and initialization, we check if the specified memory partition by partition name is empty. If so we display a message and return an error.
If not empty, we point to the first free memory block.
We then set the top of our stack to the address of the next free memory block. This implements the stack.
After some housekeeping operations, we return from the function.
int __stdcall MPFree (
int mpName,
void *memory
)
// ***************************************************************@@
// - Free (return to heap) the specified memory block into the
// specified memory pool.
// *****************************************************************
{
BOOL gotMutex; // got mutex flag
int retVal, // returned by this function
status; // returned by function calls
MP_MEM_BLOCK *memoryBlock; // memory block
#ifdef CAKE
int traceExecution = 1; // for testing only
#endif
// **** initialization ****
retVal = 0; // hope all goes well
gotMutex = (BOOL)(0 == 1); // for starters
memoryBlock = (MP_MEM_BLOCK*)memory; // for ease of use
// **** perform sanity checks ****
if ((mpName < 0) ||
(mpName >= MAX_MEMORY_POOLS))
{
EventLog(EVENT_ERROR,
"MPFree <<< UNEXPECTED mpName: %d line: %d file ==>%s<==\n",
mpName, __LINE__, __FILE__);
retVal = WAR_INVALID_ARGUMENT_VALUE;
goto done;
}
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPFree <<< memoryBlock ==>%s<== &memoryBlock[0]: 0x%08lx line: %d\n",
(char*)memoryBlock, (unsigned long)&memoryBlock[0], __LINE__);
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPFree <<< mpMutex[%d]: 0x%08lx line: %d\n",
mpName, (unsigned long)mpMutex[mpName], __LINE__);
// **** get access to the mutex ****
status = MutexLock(&mpMutex[mpName]);
CDP_CHECK_STATUS("MPFree <<< MutexLock", status);
// **** flag we have the mutex ****
gotMutex = (BOOL)(1 == 1);
// **** point to first block in the specified heap ****
memoryBlock->next = mpHeap[mpName];
// **** point to first memory block ****
mpHeap[mpName] = (void*)memory;
// **** inform the user what is going on ****
if (traceExecution != 0)
EventLog(EVENT_INFO,
"MPFree <<< mpHeap[%d]: 0x%08lx line: %d\n",
mpName, mpHeap[mpName], __LINE__);
// **** clean up ****
done:
// **** release the mutex (if needed) ****
if (gotMutex)
{
status = MutexUnLock(&mpMutex[mpName]);
if (status != 0)
EventLog(EVENT_ERROR,
"MPFree <<< MutexUnLock status: %d mpMutex[%d]: 0x%08lx line: %d file ==>%s<==\n",
status, mpName, (unsigned long)mpMutex[mpName], __LINE__, __FILE__);
}
// **** inform the user what is going on ****
if ((retVal != 0) || (traceExecution != 0))
EventLog(EVENT_INFO,
"MPFree <<< retVal: %d line: %d file ==>%s<==\n",
retVal, __LINE__, __FILE__);
// **** inform the caller what went on ****
return retVal;
}
This function is used to return to the specified memory heap memory that is no longer in use.
The function performs some initialization and checks.
The block to be freed is set to point to the first memory block in the stack. The mpHeap entry for the specified heap is then set to point to the block being freed. This puts the block on the top of the stack. In the next allocation operation, this block will be returned.
As you can see our memory blocks stay in a stack and the only additional variable is the pointer to the top of our stack which is represented by a single entry in the mpHeap array. For each memory partition we require O(1) storage.
Hope you enjoyed solving this problem as much as I did. The code for this project is not in GitHub. Please copy and paste the code from this post into your IDE.
Please note that the code here presented might not be the best possible solution.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Starting on the next post, I will continue to solve problems from HackerRank and LeetCode, but will be using the Python programming language. Based on a few different polls, it seems that Python is more popular than Java. Also keep in mind, that a lot of Python libraries are implemented using the C programming language. This is done in order to obtain better / faster performance.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John