pvPortMalloc and vPortFree in FreeRTOS - Time & Space Complexity

Time Complexity: pvPortMalloc and vPortFree

O(n)

Understanding Time Complexity

When using pvPortMalloc and vPortFree in FreeRTOS, it's important to understand how the time to allocate and free memory changes as the program runs.

We want to know how the cost of these operations grows when the system manages more memory blocks.

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS memory allocation and freeing code.

void *ptr = pvPortMalloc(size);
if(ptr != NULL) {
    // Use the allocated memory
    vPortFree(ptr);
}
    

This code allocates a block of memory of given size and then frees it after use.

Identify Repeating Operations

Look for loops or repeated steps inside the allocation and free functions.

• Primary operation: Searching through the free memory blocks to find a suitable block for allocation or to merge freed blocks.
• How many times: The search may check multiple blocks depending on how fragmented the memory is.

How Execution Grows With Input

As the number of free memory blocks increases, the time to find a suitable block or merge blocks grows.

Input Size (number of free blocks)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows roughly in direct proportion to the number of free blocks.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate or free memory grows linearly with the number of free memory blocks.

Common Mistake

[X] Wrong: "Memory allocation and freeing always take the same fixed time no matter what."

[OK] Correct: The time depends on how many free blocks exist and how fragmented the memory is, so it can take longer if there are many blocks to check.

Interview Connect

Understanding how memory allocation time grows helps you reason about system performance and resource management in embedded systems.

Self-Check

"What if the memory allocator used a different data structure like a balanced tree? How would the time complexity change?"

Practice

1. What is the primary purpose of pvPortMalloc in FreeRTOS?

easy

A. To suspend a running task temporarily

B. To free allocated memory back to the system

C. To create a new task in FreeRTOS

D. To allocate memory safely for tasks and resources

Solution

1. Step 1: Understand the role of pvPortMalloc

   pvPortMalloc is designed to allocate memory safely in FreeRTOS, especially in multitasking environments.

2. Step 2: Differentiate from other functions

   Functions like vPortFree free memory, and task creation or suspension are unrelated to memory allocation.

3. Final Answer:

   To allocate memory safely for tasks and resources -> Option D

4. Quick Check:

   pvPortMalloc = allocate memory [OK]

Hint: pvPortMalloc always allocates memory safely [OK]

Common Mistakes:

• Confusing pvPortMalloc with vPortFree
• Thinking pvPortMalloc creates tasks
• Assuming it suspends tasks

2. Which of the following is the correct syntax to free memory allocated by pvPortMalloc?

easy

A. vPortFree(pointer);

B. pvPortMalloc(pointer);

C. free(pointer);

D. vPortMalloc(pointer);

Solution

1. Step 1: Identify the function to free memory

   Memory allocated by pvPortMalloc must be freed using vPortFree to avoid memory leaks.

2. Step 2: Check syntax correctness

   The correct syntax is vPortFree(pointer);. Other options either allocate memory or use standard C free, which is not recommended in FreeRTOS.

3. Final Answer:

   vPortFree(pointer); -> Option A

4. Quick Check:

   Free memory with vPortFree [OK]

Hint: Use vPortFree to release memory allocated by pvPortMalloc [OK]

Common Mistakes:

• Using free() instead of vPortFree()
• Calling pvPortMalloc to free memory
• Incorrect function names like vPortMalloc

3. Consider the following FreeRTOS code snippet:

void *ptr = pvPortMalloc(100);
if(ptr != NULL) {
    vPortFree(ptr);
    ptr = NULL;
}
printf("%p", ptr);

What will be the output of the printf statement?

medium

A. A memory address (non-NULL pointer)

B. Compilation error

C. NULL (0x0 or equivalent)

D. Random garbage value

Solution

1. Step 1: Analyze memory allocation and freeing

   pvPortMalloc(100) allocates memory and returns a pointer. Then vPortFree(ptr) frees it, and ptr is set to NULL.

2. Step 2: Understand the printf output

   Since ptr is explicitly set to NULL, printf will print 0x0 or equivalent NULL pointer representation.

3. Final Answer:

   NULL (0x0 or equivalent) -> Option C

4. Quick Check:

   Pointer set to NULL after free = NULL output [OK]

Hint: Pointer set to NULL after free prints NULL [OK]

Common Mistakes:

• Assuming pointer still holds address after free
• Expecting compilation error due to free
• Thinking printf prints garbage

4. Identify the error in the following FreeRTOS code snippet:

void *ptr = pvPortMalloc(50);
// Some code using ptr
vPortFree(ptr);
vPortFree(ptr);

medium

A. Double free of the same pointer

B. Missing check if pvPortMalloc returned NULL

C. Incorrect function name vPortFree

D. Memory leak due to not freeing ptr

Solution

1. Step 1: Review memory allocation and freeing

   pvPortMalloc(50) allocates memory and returns a pointer stored in ptr. The first vPortFree(ptr) frees this memory.

2. Step 2: Identify the problem with second free

   The second vPortFree(ptr) attempts to free the same memory again, causing a double free error which can crash or corrupt memory.

3. Final Answer:

   Double free of the same pointer -> Option A

4. Quick Check:

   Freeing pointer twice causes error [OK]

Hint: Never free the same pointer twice without resetting it [OK]

Common Mistakes:

• Ignoring double free risks
• Not checking for NULL after malloc
• Confusing function names

5. You want to allocate memory for an array of 10 integers using FreeRTOS memory management. Which code snippet correctly allocates and frees this memory?

hard

A. int *arr = (int *)pvPortMalloc(sizeof(int));
if(arr != NULL) {
// use arr
vPortFree(arr);
}

B. int *arr = (int *)pvPortMalloc(10 * sizeof(int));
if(arr != NULL) {
// use arr
vPortFree(arr);
}

C. int *arr = (int *)malloc(10 * sizeof(int));
if(arr != NULL) {
// use arr
free(arr);
}

D. int *arr = (int *)vPortFree(10 * sizeof(int));
if(arr != NULL) {
// use arr
pvPortMalloc(arr);
}

Solution

1. Step 1: Allocate correct memory size with pvPortMalloc

   To store 10 integers, allocate 10 times the size of int using pvPortMalloc(10 * sizeof(int)). This ensures enough space.

2. Step 2: Free memory properly with vPortFree

   After using the array, free the memory with vPortFree(arr). Also, check if allocation succeeded by verifying arr != NULL.

3. Final Answer:

   Correct allocation and freeing using pvPortMalloc and vPortFree -> Option B

4. Quick Check:

   Allocate 10 ints with pvPortMalloc, free with vPortFree [OK]

Hint: Multiply size by count in pvPortMalloc, free with vPortFree [OK]

Common Mistakes:

• Allocating only size of one int instead of 10
• Using standard malloc/free instead of pvPortMalloc/vPortFree
• Confusing allocation and free function calls