Memory-aligned malloc

This article is inspired by this In-pyjama video: Mock Interview: Implement Custom Malloc | Embedded systems podcast, in Pyjama (youtube.com)

Problem statement:

Implement a custom malloc API that

1. Takes two integers, size and alignment as inputs.
2. Return the starting address of buffer aligned to alignment.

void* custom_malloc(int size,int alignment)
{

}
int custom_free(void *ptr)
{

}

Assumption: You can use malloc and free internally.

Solution:

What is aligned memory?

Aligned memory refers to a memory address that is a multiple of a specific value, known as the alignment boundary. This means that the memory address satisfies certain alignment constraints, ensuring that it starts at a particular boundary that is a power of two (e.g., 4 bytes, 8 bytes, 16 bytes, 64 bytes, etc.).

Why Aligned Memory is Important:

1. Performance:

• CPU Efficiency: Many CPUs are optimized to handle data that is aligned on natural boundaries. Accessing unaligned data can cause the CPU to perform additional operations, slowing down memory access.
• Cache Performance: Properly aligned data can improve cache performance because cache lines are often aligned to specific boundaries. Misaligned data can span multiple cache lines, causing additional cache misses and reduced performance.

2. Hardware Requirements:

• Some hardware devices and instructions require data to be aligned. For example, SIMD (Single Instruction, Multiple Data) instructions on modern processors often require data to be aligned to specific boundaries.

3. Consistency and Portability:

• Ensuring that data is aligned makes code more portable and consistent across different architectures and systems, which may have varying alignment requirements.

Example of Aligned Memory:

Suppose you have a 64-byte alignment requirement. This means any memory address you allocate should be a multiple of 64 (e.g., 0x10000, 0x10040, 0x10080, etc.). If the memory address meets this requirement, it is considered aligned.

Visual Example of Aligned Memory Allocation:

Let’s allocate a memory block and align it to a 64-byte boundary:

1. Memory Allocation:

• Assume malloc returns an address, say 0x10000.

2. Alignment Adjustment:

• To align this address to a 64-byte boundary, we need to adjust it to the nearest multiple of 64.

3. Calculate the Aligned Address:

• Adding 64–1 (63) to ensure there’s enough space:
• 0x10000 + 0x3F = 0x10047

4. Aligning the address by masking out the lower bits:

• 0x10047 & ~(0x3F) = 0x10040
• The final aligned address is 0x10040, which is a multiple of 64.

Memory Address        Content
0x10000               [Original pointer allocation start (0x10000)]
0x10001               [Unused]
0x10002               [Unused]
0x10003               [Unused]
0x10004               [Unused]
0x10005               [Unused]
0x10006               [Unused]
0x10007               [Unused]
-----------------------------------------
0x10008 - 0x1000F     [Intermediate pointer after moving sizeof(void*) bytes]
-----------------------------------------
0x10010 - 0x10046     [Unused space after adding alignment - 1 (0x10047)]
-----------------------------------------
0x10038               [Stored original pointer (0x10000)]
0x10039               [Unused]
0x1003A               [Unused]
0x1003B               [Unused]
0x1003C               [Unused]
0x1003D               [Unused]
0x1003E               [Unused]
0x1003F               [Unused]
-----------------------------------------
0x10040               [Aligned memory address (start of aligned block)]
0x10041               [ ]
0x10042               [ ]
...
0x1043F               [Last byte of user data]
-----------------------------------------
Total Allocated Size: 1095 bytes

#include <stdio.h>
#include <stdlib.h>

void* custom_malloc(int size,int alignment)
{
 if(alignment<=0 || size<=0){
 return NULL;
 }
 int total_allocated_size=size+alignment-1+sizeof(void*);
 void *original=malloc(total_allocated_size);
 if(!original){
 return NULL;
 }

 //step 1: Move past the space kept for original pointer 8bytes in 64 bit machine
 char *aligned=(char*)original+sizeof(void*);
 
 //step2: Add alignment -1 to handle potential misalignment
 aligned+=alignment-1;
 
 //step 3: Align the address
 aligned= (char*)((unsigned long) aligned & ~(alignment-1)); //finds the start of alignment boundary
 
 //step4: store the original pointer just before aligned adress
 void **store_original=(void**)(aligned - sizeof(void*));
 *store_original=original;

 //debugging info
 printf("Original address: %p\n",original);
     printf("Aligned address before masking: %p\n",(void*)((unsigned long)aligned | (alignment - 1)));
     printf("Aligned address after masking: %p\n",aligned);
     printf("Stored original pointer at: %p\n",store_original);
     printf("Total allocated size: %d bytes\n",total_allocated_size);

 return aligned;
}
int custom_free(void *ptr)
{
 if(ptr){
 //void *original= *((void**)((char*)ptr - sizeof(void*)));
 //step1: convert ptr to char* for pointer arithmetic
 char *char_ptr=(char*)ptr;
 //step2: move back by sizeof(void*) bytes to reach the original pointer
 char *original_location = char_ptr-sizeof(void*);
 //step3: retrieve original pointer
 void *original=*((void**)original_location);
 
  if (original != NULL) {
            printf("Freeing original memory at address: %p\n", original);
            free(original); // Free the original memory

            // Nullify the pointer to prevent double freeing
            *((void**)((char*)ptr - sizeof(void*))) = NULL;
            return 0; // Success
         }
 }
    
    return -1; // Failure 
}

int main() {
    int size=1024;
    int alignment=64;
    void *aligned_memory= custom_malloc(size,alignment);
    if(aligned_memory==NULL){
  printf("Memory allocation failed\n");
  return 1;
 } 
    printf("Aligned memory address: %p\n",aligned_memory);
    printf("Aligned memory address (decimal): %lu\n",(unsigned long)aligned_memory);

    //check alignment 
    if((unsigned long)aligned_memory % alignment==0){
 printf("Memory is aligned to %d bytes \n",alignment);
 
    }else{
 printf("Memory is not aligned\n");
 }
 
      // Free aligned memory and verify
    if (custom_free(aligned_memory)==0) {
        printf("Memory successfully freed.\n");
    } else {
        printf("Failed to free memory.\n");
    }

    // Verify the memory has been freed by attempting to free it again
    printf("Attempting to free the same memory again to check if it has been freed:\n");
    if (custom_free(aligned_memory)==0) {
        printf("Memory successfully freed again.\n");
    } else {
        printf("No errors occurred during the second free attempt.\n");
    }

    return 0;
}

1.Input Validation

• if (alignment <= 0 || size <= 0) { return NULL; // Invalid alignment or size }
• This checks if the alignment and size are positive values. If not, it returns NULL indicating an error.

2.Calculate Total Allocated Size:

• int total_allocated_size = size + alignment - 1 + sizeof(void*);
• This calculates the total size needed to ensure proper alignment and space to store the original pointer.
• alignment - 1 ensures we have enough space to adjust the address to the next alignment boundary.
• sizeof(void*) ensures space to store the original pointer for later use during freeing.

3.Allocate Memory:

• void *original = malloc(total_allocated_size); if (!original) { return NULL; // Memory allocation failed }
• This allocates the calculated total size. If allocation fails, it returns NULL.

4.Move Past Space for Original Pointer:

• char *aligned = (char*)original + sizeof(void*);
• This moves the pointer forward by sizeof(void*) bytes to leave space to store the original pointer.

5.Add Alignment — 1:

• aligned += alignment - 1;
• This adds alignment - 1 to ensure the address can be adjusted to the nearest aligned boundary.

6.Align the Address:

• aligned = (char*)((unsigned long)aligned & ~(alignment - 1));
• This masks out the lower bits of the address to align it to the nearest multiple of the alignment value.

7.Store Original Pointer:

• void **store_original = (void**)(aligned - sizeof(void*)); *store_original = original;
• This stores the original pointer just before the aligned address for use during freeing.

Output in Cmd Line in windows

The custom_free function is self explanatory i will leave it to the reader to understand it.

What is double freeing?

Double freeing refers to a situation where a memory block that has already been deallocated (freed) is attempted to be freed again. This can lead to memory corruption, crashes, or unpredictable behavior. So we are doing this to prevent it.

// Nullify the pointer to prevent double freeing
            *((void**)((char*)ptr - sizeof(void*))) = NULL;

Why do we see warnings?:

The warnings are occurring because of casting a pointer to an unsigned long, which might not be the same size on your platform (for example, on a 64-bit system). To avoid these warnings, you should use the uintptr_t type from <stdint.h>, which is designed to hold pointer values in a way that is safe for casting to and from integer types on different machines.

Using uintptr_t ensures that the pointer arithmetic is performed correctly regardless of the platform, and it eliminates the warnings about casting between different pointer and integer sizes.

Thank you for reading. Please clap if this post was informative and leave a comment if you feel there can be any improvement in this article your feedback is appreciated. Thank you again.