Я хочу сделать свой собственный Malloc

Существует довольно много хорошей литературы по реализации malloc и подобных вещей. но я заметил, что вы включаете сюда C ++ - знаете ли вы, что вы можете написать свою собственную реализацию new и delete в C ++? Это может быть полезно как способ сделать это легко.

В любом случае, характеристики, которые вы хотите, будут в значительной степени зависеть от вашей рабочей нагрузки, то есть от модели использования во времени. Если у вас есть только malloc и новые освобождения, это легко, очевидно. Если у вас есть только malloc с одним или несколькими разными размерами блоков, это также просто.

В других языках вы получаете некоторые рычаги, обладая способностью объединять память в одну цепочку, но C не настолько умен.

] Базовая реализация malloc просто выделяет заголовок, который содержит длину данных, «используемый флаг» и недопустимая память. Затем Malloc создает новый заголовок в конце своего пространства, выделяет память и возвращает указатель. Когда вы освобождаетесь, он просто сбрасывает флаг использования.

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

Вы могли бы сделать более сложный gc, но помните, что это требует времени; Вы не хотите, чтобы бесплатная занимала много времени.

Есть хорошая статья о реализации malloc в Solaris, которая может показаться вам интересной. Вот еще один по созданию альтернативного malloc , опять же в Solaris, но основы те же. И вы должны прочитать статью Википедии о сборке мусора, и следуйте за ним к некоторым более формальным статьям.

Обновление

Вы знаете, вы действительно должны взглянуть на сборщиков мусора поколений. Основная идея заключается в том, что чем дольше что-то остается выделенным, тем больше вероятность того, что останется выделенным . Это расширение "копирующего" GC, о котором вы упоминаете. По сути, вы размещаете новые вещи в одной части вашего пула памяти, называя это g0. Когда вы достигаете максимальной отметки, вы просматриваете выделенные блоки и копируете те, которые все еще используются, в другой раздел памяти, называете его g1. Затем вы можете просто очистить пространство g0 и начать выделять его. В конце концов g1 достигает своей верхней отметки, и вы исправляете это, очищая g0, и очищаете g1, перемещая вещи в g0, и когда вы закончите, вы переименовываете старый g1 в g0, и наоборот, и продолжаете.

Хитрость в том, что в C, в частности, дескрипторы, которые вы раздаете памяти в malloc, являются прямыми необработанными указателями; Вы не можете по-настоящему перемещать вещи без какого-либо большого лекарства.

Второе обновление

В комментариях @unknown спрашивает: «Не будет ли перемещение вещей просто быть memcpy ()». И это действительно так. но учтите эту временную шкалу:

предупреждение: это не полный и непроверенный, только для иллюстрации, только для развлечения, без гарантий, явных или подразумеваемых

/* basic environment for illustration*/
void * myMemoryHdl ;
unsigned char lotsOfMemory[LOTS]; /* this will be your memory pool*/ 

Вы неправильно выделяете память

/* if we get past this, it succeded */
if((myMemoryHdl = newMalloc(SIZE)) == NULL)
    exit(-1);

В своей реализации malloc вы создаете памяти и верните указатель на буфер.

unsigned char * nextUnusued = &lotsOfMemory[0];
int partitionSize = (int)(LOTS/2);
int hwm = (int) (partition/2);
/* So g0 will be the bottom half and g1 the top half to start */
unsigned char * g0 = &lotsOfMemory[0];
unsigned char * g1 = &lotsOfMemory[partitionSize];


void * newMalloc(size_t size){
   void * rtn ;
   if( /* memory COMPLETELY exhausted */)
      return NULL;
   /* otherwise */
   /* add header at nextUnused */
   newHeader(nextUnused);     /* includes some pointers for chaining
                               * and a field with values USED or FREE, 
                               * set to USED */
   nextUnused += HEADERLEN ;  /* this could be niftier */
   rtn = nextUnused ;
   nextUnused += size ;
}

Некоторые вещи освобождены

  newFree(void * aHandle){
     *(aHandle-offset) = FREE ; /* set the flag in the header, 
                                 * using an offset. */
  }

Итак, теперь вы делаете все, и вы достигаете своей максимальной отметки.

 for( /* each block in your memory pool */ )
    if( /* block header is still marked USED */ ) {
        memcpy(/* block into other partition */);
    }
 /* clear the partition */
 bzero(g0, partitionSize);

Теперь вернемся к исходному дескриптору, который вы сохранили. в myMemHdl. На что это указывает? (Ответ, вы просто установите его на 0x00 с помощью bzero (3). )

В этом и заключается магия. По крайней мере, в C указатель, который вы вернули из своего malloc, больше не находится под вашим контролем - вы не можете переместить его после свершившегося факта. В C ++ с помощью пользовательских типов, подобных указателю, вы можете это исправить.