Memory Allocator

This question is asked in one of my phone interview. The question is "To  implement a memory allocator that allows multiple clients to allocate and free memory from a buffer". My initial thought is the maintain a front and rear pointer and make the buffer as a ring. However, such design doesn't satisfy the requirement because there are multiple users for example, user1 has requested buffer[0-3], user2 has requested buffer[4-6] and user3 has requested buffer[7]. When user2 releases his buffer before user3, you'll get a problem because of memory fragmentation. You can't simply move the front pointer back to 4 because it'll release user3's buffer which is being used currently. So I thought of the way how Linux kernel maintains the memory.  I'll need a pointer that maintains a list of free memory chunk. Yes, it is a linked list because of the memory fragmentation. When you request a piece of memory, you'll check the list to see if there is any memory fragment that has enough space for the request. If so, update the offset pointer for that node. Otherwise, return NULL pointer.

 #include <stdio.h>  
 #include <stdlib.h>  
 // To execute C, please define "int main()"  
 static char buffer[256];  
 struct LinkNode {  
  int start;  
  int end;  
  struct LinkNode *next;  
 };  
 static struct LinkNode *free_header = NULL;  
 void initFreeMemory();  
 void *allocate(int size);  
 int main() {  
  initFreeMemory();  
  printf("%p\n", buffer);  
  void *addr1 = allocate(3);  
  printf("%p\n", addr1);  
  void *addr2 = allocate(128);  
  printf("%p\n", addr2);  
  printf("%p\n", buffer+free_header->start);  
  return 0;  
 }  
 void initFreeMemory() {  
  free_header = (struct LinkNode *)malloc(sizeof(struct LinkNode));  
  free_header->start = 0;  
  free_header->end = 256;  
  free_header->next = NULL;  
 }  
 void *allocate(int size) {  
  struct LinkNode *p = free_header;  
  while (p) {  
   if (p->end - p->start >= size) break;  
   p = p->next;  
  }  
  if (p == NULL) return NULL;  
  void *ret = buffer+p->start;  
  p->start += size;  
  return ret;  
 }  
 /*void free(void *object) {  
  int size = sizeof(object);  
  struct LinkNode *node = malloc(sizeof(struct LinkNode));  
  node->start = object;  
  node->end = node->start + size;  
  free_header->next = node;  
 }*/  

Memory Configuration on STM32F407

1. Stack Overflow

The process maintains its stack and the stack size is configured as following:

1:   ;*******************************************************************************   
2:   ; Amount of memory (in bytes) allocated for Stack   
3:   ; Tailor this value to your application needs   
4:   ; <h> Stack Configuration   
5:   ; <o> Stack Size (in Bytes) <0x0-0xFFFFFFFF:8>   
6:   ; </h>   
7:   Stack_Size  EQU  0x00008000   
8:       AREA STACK, NOINIT, READWRITE, ALIGN=3   
9:   Stack_Mem  SPACE Stack_Size   
10:   __initial_sp   
11:  </code></pre>  

So the code above defines the default stack size as 0x8000 (32Kb). If you have a buffer larger than 32Kb or you have a very deep recursive call, the stack will overflow. Once the overflow happens, the processor will generate an interrupt and jump to the interrupt handler which is HardFault_Handler.
I created a very simple test code shown as below to verify this behavior.

1:  #define BUF_SIZE (32*1024L)
2:  int main( void )  
3:  {  
4:       char buf[BUF_SIZE];  
5:       buf[0] = 'a';  
6:       buf[BUF_SIZE-1] = 'x';  
7:       printf("buf allocated on STACK, buf[%d]=%c, buf[%ld]=%c\r\n",  
8:            0, buf[0], BUF_SIZE, buf[BUF_SIZE-1]);  
9:  }  

If you run this code, nothing will output. If you run the JTAG debugger,  and set a break point in HardFault_Handler, you'll see the code flow reaches the break point.

Note, the reason the printf is not working in HardFault_Handler is the main stack is corrupted.
On the other hand, if you increase the Stack_Size beyond BUF_SIZE or reduce the BUF_SIZE below 32Kb, you'll see the output.

2. STM32F407 on-chip SRAM

By roughly looking at the STM32F407 datasheet, you are aware that you can use up to 192Kb SRAM. And you probably want to allocate the entire SRAM as stack to the processor and thus no heap. So you just increase the Stack_Size to 0x0002ffff and then you compile the code. However, you'll see following errors during the link stage:

1:  assembling startup_stm32f40xx.s...  
2:  linking...  
3:  .\Obj\STM32F407VET.axf: Error: L6406E: No space in execution regions with .ANY selector matching startup_stm32f40xx.o(STACK).  
4:  .\Obj\STM32F407VET.axf: Error: L6407E: Sections of aggregate size 0x30000 bytes could not fit into .ANY selector(s).  
5:  Not enough information to list image symbols.  
6:  Not enough information to list the image map.  
7:  Finished: 2 information, 0 warning and 2 error messages.  

Weird, right? Does it mean that we can't use the entire memory for stack? The answer is "YES we CAN" but we need to do a little bit more configuration. Looking at the STM32F407 datasheet again, you'll realize that the 192Kb SRAM actually consists of two on-chip SRAM, one of which is 128Kb while the other is 64Kb. By default, the Keil project doesn't include the second 64Kb into memory so you have to opt in that chip.

Now, try to compile the code again and you'll see the errors gone!