Trace and Analyze Memory Allocators in FreeRTOS

吳彥廷

Mission

First, in the Posix demo simulation environment, switch between heap_3, heap_4, and heap_5, and write test code to simulate memory allocation behaviors with varying sizes and frequencies. Then, compare the memory allocation speed, fragmentation levels, and resource overhead of heap_3, heap_4, and heap_5 to identify the strengths, limitations, and appropriate use cases for each allocator. Additionally, integrate the mallocvis tool to observe the dynamic behavior of memory allocation and deallocation. Finally, propose improvement suggestions for heap_5 and implement the optimized solution.

Different betwen Heap 3,4,5

Feature	heap_3	heap_4	heap_5
Allocation Strategy	Uses C standard library malloc() and free()	First-Fit algorithm	Multi-region First-Fit algorithm
Multi-Memory Region Support	Not supported	Not supported	Supported
Fragmentation Control	Cannot control	Uses best-fit strategy to reduce internal fragmentation	Provides flexibility to reduce fragmentation
Memory Efficiency	Efficiency depends on the underlying C standard library	Highly efficient for small embedded systems	Supports dynamic memory regions, more effective for large embedded systems
Overhead	Minimal (determined by the C standard library)	Moderate (additional metadata for the built-in allocator)	Moderate (additional data structures for region management)
Configuration Complexity	Simple (just link the standard library)	Relatively simple (requires memory block size setup)	Relatively complex (requires configuration of multiple memory regions)
Debugging and Tracking Support	Relies on the implementation of the C standard library	Provides detailed memory management data	Provides multi-region memory management data
Use Case	Small systems or scenarios requiring integration with the standard library	General use cases, suitable for most embedded applications	Highly flexible, suitable for scenarios requiring multi-region memory allocation

1. Environment Setup

1.1 Install Required Software

On an Ubuntu system, execute the following commands to install the necessary tools and libraries:

Update packages and install basic tools :

$ sudo apt update && sudo apt upgrade
$ sudo apt install -y build-essential git cmake gdb qemu gcc-multilib libstdc++-8-dev

Install RISC-V toolchain :

$ sudo apt install -y gcc-riscv64-unknown-elf gdb-multiarch

Install mallocvis (for visualization tools)

$ sudo apt install -y libgl-dev python3 python3-pip
$ pip install mallocvis

1.2 Clone FreeRTOS Repository

Clone the source code from the official FreeRTOS repository :

$ git clone https://github.com/FreeRTOS/FreeRTOS.git
$ cd FreeRTOS

2.Setup and Compilation

2.1 Select and Configure Demo Project

Select the Posix_GCC demo project for testing :

$ cd FreeRTOS/Demo/Posix_GCC

Modify the FreeRTOSConfig.h file to select the heap management scheme :

# define configUSE_HEAP_SCHEME_3    1  // Use heap_3

2.2 Compile the Project

Use the following command to compile the project:

$ make

3.Heap Testing Logic :

3.1 Modify Heap Testing Logic

In heap_3.c, add the following code to log allocation and deallocation behaviors :

// Global variable to track the number of operations
static int operationCount = 0;
#define MAX_OPERATIONS 1000 // Maximum number of operations

void memoryFragmentationTest()
{
    const int blockSizes[] = {32, 64, 128, 256, 512}; // Simulate various allocation sizes
    void *allocatedBlocks[MAX_OPERATIONS];

    // Simulate allocation
    for (int i = 0; i < MAX_OPERATIONS; i++)
    {
        int sizeIndex = rand() % 5; // Randomly select a size
        allocatedBlocks[i] = pvPortMalloc(blockSizes[sizeIndex]);

        // Release some memory periodically to simulate fragmentation
        if (i % 10 == 0 && i > 0)
        {
            for (int j = i - 10; j < i; j += 2) // Randomly free some blocks
            {
                vPortFree(allocatedBlocks[j]);
                allocatedBlocks[j] = NULL;
            }
        }
    }

    // Clean up all allocated memory
    for (int i = 0; i < MAX_OPERATIONS; i++)
    {
        if (allocatedBlocks[i] != NULL)
        {
            vPortFree(allocatedBlocks[i]);
        }
    }
}

void *pvPortMalloc(size_t xWantedSize)
{
    // Start timing
    struct timespec startTime, endTime;
    clock_gettime(CLOCK_MONOTONIC, &startTime);

    // Perform the original allocation logic
    void *ptr = malloc(xWantedSize);

    // Record operation
    if (ptr != NULL)
    {
        operationCount++;
        clock_gettime(CLOCK_MONOTONIC, &endTime);

        long elapsedTime = (endTime.tv_sec - startTime.tv_sec) * 1000000L +
                           (endTime.tv_nsec - startTime.tv_nsec) / 1000;
        printf("Allocated %zu bytes (Operation #%d) in %ld µs\n", xWantedSize, operationCount, elapsedTime);
    }
    return ptr;
}

void vPortFree(void *pv)
{
    // Start timing
    struct timespec startTime, endTime;
    clock_gettime(CLOCK_MONOTONIC, &startTime);

    // Perform the original free logic
    if (pv != NULL)
    {
        free(pv);
        clock_gettime(CLOCK_MONOTONIC, &endTime);

        long elapsedTime = (endTime.tv_sec - startTime.tv_sec) * 1000000L +
                           (endTime.tv_nsec - startTime.tv_nsec) / 1000;
        printf("Freed memory (Operation #%d) in %ld µs\n", operationCount, elapsedTime);
    }
}

Idea was as follows : I planned to modify the source code of heap3, heap4, and heap5 to include custom malloc and free functions, then test these using the Posix_gcc demo. Additionally, I intended to use mallocvis to observe memory management behavior in these heaps, particularly focusing on fragmentation analysis. However, I’ve encountered some issues that I’m currently trying to resolve:

1. Mallocvis cannot generate the expected complete visualization
   My expectation was to see a clear graphical representation of memory allocation and deallocation behavior, but the actual output is incomplete and does not meet the intended requirements.

2. The allocated memory block sizes do not match the original settings
   Initially, I configured the memory allocation to randomly select sizes from {32, 64, 128, 256, 512}. However, during execution, the allocated sizes were inconsistent, showing results like:

Allocated 90 bytes (Operation #555) in 0 µs
Allocated 111 bytes (Operation #556) in 0 µs
Freed memory (Operation #556) in 0 µs
Allocated 82 bytes (Operation #557) in 0 µs
Freed memory (Operation #557) in 0 µs
Freed memory (Operation #557) in 0 µs
Allocated 131 bytes (Operation #558) in 0 µs
Freed memory (Operation #558) in 0 µs
Allocated 131 bytes (Operation #559) in 0 µs
Freed memory (Operation #559) in 0 µs
Allocated 111 bytes (Operation #560) in 0 µs

Allocations such as 82, 90, and 111 bytes deviate from the predefined sizes.

3. The memoryFragmentationTest function does not stop correctly
   I configured the memoryFragmentationTest function to perform 1000 memory allocation and deallocation operations. However, during execution, I observed that the output keeps running indefinitely, suggesting an infinite loop or other issue.

These problems are preventing me from completing the tests and observations as planned. I am currently working on troubleshooting and resolving these issues.

4. Improve Heap_5

4.1 pvPortMalloc change to Best-Fit Allocation

The modified pvPortMalloc function implements a Best-Fit Allocation strategy to reduce memory fragmentation by selecting the smallest free block that is large enough to fulfill the allocation request.

Key Changes for Best-Fit Allocation:

1. Tracking the Best-Fit Block:
   Two new variables are introduced:
   • pxBestFitBlock: Pointer to the block that best fits the requested size.
   • xBestFitSize: Tracks the size of the smallest block found that satisfies the allocation request.

Both are initialized to NULL and SIZE_MAX respectively.

BlockLink_t *pxBestFitBlock = NULL; // Best-fit block pointer
size_t xBestFitSize = SIZE_MAX;     // Minimum size found so far

2. Iterating Through Free Blocks:

• The free block list is traversed using a loop, checking each block's size against the requested size (xWantedSize).
• If the current block’s size is sufficient (>= xWantedSize) and smaller than the current xBestFitSize, it becomes the new candidate for allocation.
• This ensures that the smallest possible block is chosen.

while (pxBlock != pxEnd){
    if ((pxBlock->xBlockSize >= xWantedSize) && (pxBlock->xBlockSize < xBestFitSize))
    {
        pxBestFitBlock = pxBlock;
        xBestFitSize = pxBlock->xBlockSize;
    }
    pxPreviousBlock = pxBlock;
    pxBlock = heapPROTECT_BLOCK_POINTER(pxBlock->pxNextFreeBlock);
}

3. Allocating the Best-Fit Block:

• After finding the best-fit block, it is used for the allocation.
• If the block’s size is larger than required, it is split into two blocks:
  • One block for the exact requested size.
  • The remaining portion is inserted back into the free list.

if ((pxBlock->xBlockSize - xWantedSize) > heapMINIMUM_BLOCK_SIZE){
    pxNewBlockLink = (void *)(((uint8_t *)pxBlock) + xWantedSize);
    pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
    pxBlock->xBlockSize = xWantedSize;
    pxNewBlockLink->pxNextFreeBlock = pxPreviousBlock->pxNextFreeBlock;
    pxPreviousBlock->pxNextFreeBlock = heapPROTECT_BLOCK_POINTER(pxNewBlockLink);
}

4.2 Add Block Coalescing into function (vPortFree)

The modified vPortFree function incorporates Block Coalescing to merge adjacent free blocks when a block is released. This reduces fragmentation and makes larger contiguous memory blocks available for future allocations.

Key Changes for Block Coalescing:

1. Locating the Next Block:

• After freeing the current block, the function calculates the memory address of the next block.
• This is done by adding the size of the current block to its address.

BlockLink_t *pxNextBlock = (BlockLink_t *)((uint8_t *)pxLink + pxLink->xBlockSize);

2. Checking If the Next Block Is Free:

• The function verifies if the next block lies within the valid memory range (< pxEnd) and is free (heapBLOCK_IS_FREE).

if ((uint8_t *)pxNextBlock < (uint8_t *)pxEnd && heapBLOCK_IS_FREE(pxNextBlock))

3. Merging Blocks:

• If the next block is free, its size is added to the current block's size, effectively merging the two blocks into one.
• The pxNextFreeBlock pointer of the current block is updated to skip over the merged block.

pxLink->xBlockSize += pxNextBlock->xBlockSize;
pxLink->pxNextFreeBlock = pxNextBlock->pxNextFreeBlock;

4. Inserting the Merged Block:

• The coalesced block is inserted back into the free list using the prvInsertBlockIntoFreeList function, making it available for future allocations.

prvInsertBlockIntoFreeList(pxLink);