Менеджер памяти для встроенных систем

Как известно стандартные функции динамического  выделения памяти calloc , malloc не являются детерминированными по времени. При написании программ под микроконтроллер это вряд ли подходит. То есть в условиях с ограниченной памятью наступает момент когда выделение свободного блока памяти резко замедляется, что в большинстве случаев  недопустимо в системе реального времени. Это замедление происходит из-за поиска блока памяти  нужного размера. Кроме того реализация этих функций может вообще отличаться от компилятора к компилятору.  Из за этого возникает идея написать свой менеджер памяти.

Есть разные алгоритмы аллокации , но они приводят к фрагментации. Поэтому , например,  операционные  системы реального времени содержат свои менеджеры памяти ( memory manager). И это как правило менеджер памяти для выделения блоков фиксированной длинны.

Ниже представлена реализация такого кода.
Сначала объявим структуру memory partion для того можно было работать с несколькими менеджерами памяти.

typedef struct 
{
    void *pMemFree;		// Free block pointer
    unsigned char BlkSize;  // Size block of the partition
    unsigned int  BlkNum;	// Number blocks in the partition
    unsigned int  BlkFree;  // Number free blocks in the partiotion

}MEM_PART;

Практически нам понадобятся три функции:
1. Инициализации
2. Получить блок памяти
3. Вернуть блок обратно

Функция инициализации строит список из свободных блоков памяти.Далее работа всегда будет идти через голову списка.

void InitMem(MEM_PART * pMem,void *addr,unsigned char size,unsigned int  num)
{
  unsigned int i;
  void** pLink;
  unsigned char * pBlk;

  pLink = (void**)addr;
  pBlk  = (unsigned char *)addr+size;

	// The first two bytes is pointer to the next block.
	// Create free memory block list 
   for(i=0;i<num-1;i++)
   {

		*pLink = (void*)pBlk; // same link list : pBlock->next = pBlk;
 	    pLink = (void **)pBlk; // same link list : pBlock = pBlk;
		pBlk+=size;

	
   }
	
   *pLink = 0; // last block pointer =0
	
   pMem->pMemFree = addr;
   pMem->BlkSize = size;
   pMem->BlkNum  = num;
   pMem->BlkFree = num;
}

Далее функция которая возвращает указатель на блок памяти , если он есть, и ноль, если блоки закончились.

void *GetMemBlock(MEM_PART *pMem)
{
  void **pBlk;
  if(pMem->BlkFree >0) // Check if thare are free blocks
  {
	pBlk = (void **)pMem->pMemFree;
 	pMem->pMemFree = *pBlk;
	pMem->BlkFree--; 
	return pBlk;
 }
 else
   return 0;		
}

И ,наконец , функция высвобождения блока памяти. Опять же нужен указатель на структуру MEM_PART и блок памяти который нужно вернуть.

void PutMemBlock(MEM_PART *pMem,void *pBlk)
{
     unsigned char **pLink;
     if(pMem->BlkFree < pMem->BlkNum)
     {
        pLink = (unsigned char **)pBlk;
        *pLink = pMem->pMemFree;
        pMem->pMemFree = pBlk;
        pMem->BlkFree++;
     }
}

Хочу обратить внимание этот менеджер памяти работает через список свободных блоков, поэтому нет тут дополнительных затрат памяти. То есть указатели списка находятся в начале свободных блоков,а когда блок взят, то они уже ненужны. Именно поэтому вопросы подобного рода любят задавать на собеседованиях при приеме на работу. Конечно вряд ли кто-нибудь обяжет вас написать такой код на бумаге без багов, но такие приемы нужно знать.

Допустим нужно 10 блоков по 10 байт,то вызов инициализации должен быть таким

...
MEM_PART MemPart;
unsigned char  MemPool[100];
...
InitMem(&MemPart,MemPool,10,10);
...

Этот простой аллокатор был использован в проекте написанном на FreeRTOS, так как его собственный не подошел.