Своя реализация malloc и free

[Sazary]

Дали мне тут одно задание - реализовать свои malloc и free. Естественно, не пользуясь стандартными.
Мне дано 10 метров памяти (статический массив).

Собственно, программа уже сделана и работает. Но показать преподавателю могу только на следующей неделе, поэтому пока есть время порассуждать.

Итак, описываю, как сделал я.

Есть массив ALLBUF размером в 10 Мб.
static char ALLBUF[BUF_SIZE];
Это и будет моя виртуальная память.

Есть две пары массивов:
static char* pools[MAX_POOLS] - массив адресов свободных пулов, то есть свободных участков памяти.
static unsigned int pools_size[MAX_POOLS] - массив, который хранит размеры этих пулов.
static char* blocks[MAX_POOLS] - массив адресов блоков (занятых участков).
static unsigned int block_size[MAX_POOLS] - их размеры.
И есть еще переменная RIGHT_BLOCK, которая указывает (хранит номер) на самый правый блок.

MAX_POOLS - максимальное количество блоков или пулов (сделал 1000).

Функции (описываю не все, а основные):
void ars_alloc_init(void) - присваивает первому элементу массива пулов адрес начала массива ALLBUF, а также заносит его размер (10 Мб) в соответствующий элемент массива размеров.
Эта функция вызывается первой в тестовой программе.

char* ars_malloc(unsigned long Size)
Функция выделения.
Если требуют больше, чем есть - возвращает 0.
Если нет пула достаточного размера - возвращаем 0.
Если все ок, то добавляем в массив блоков адрес первого подошедшего пула. Увеличиваем количество блоков (BLOCKS_COUNT) и RIGHT_BLOCK.
Пул, в котором разместили блок, теперь начинается в конце этого блока.
Возвращаем указатель на блок.

int ars_free(char* block)
Функция освобождения.
Ищем блок по адресу в массиве blocks. Если не нашли - выходим.
Если нашли, то зануляем блок, уменьшаем количество блоков (при этом RIGHT_BLOCK не меняется), добавляем в массив пулов адрес бывшего блока.

Такой подход очень неэффективен, т.к. память быстро фрагментируется. После нескольких выделений/освобождений появляются смежные пулы, которые хорошо бы объединить.
Поэтому я добавил функцию дефрагментации, которая смещает все блоки влево, вплотную друг к другу.
Была идея при освобождении искать адрес ближайшего левого пула, и если он ближе, чем ближайший левый блок, объединять новый пул с найденным (ну и с правой стороной также). Но как-то мне она не очень понравилась.
-------------------
Собственно, программу написал за вечер, взял первую идею, что пришла в голову.

Мне не нравится, что помимо основной памяти (виртуальной - ALLBUF) приходится использовать еще достаточное количество для массивов адресов и размеров. Притом они еще и статические, поэтому приходится также ограничивать количество элементов.

----------
Интересно будет послушать другие идеи.

Код не выкладываю, т.к. врядли кому-нибудь интересно его читать. А его словесное описание - выше.

[MaTBeu]

Все пулы одинакового размера или каждый пул имеет такой размер, какой занимает в нем информация?

[Luke]

Сделано грамотно, есть схожесть в менеджером памяти WinXP=)

А теперь - зачем при вызове int ars_free(char* block) занулять память?
Уж лучше тогда при выделении обнулять... Да и то, если юзеру надо сам обнулит... И еще, зачем хранить длину блока памяти, не лешче ли хранить кол-во блоков?

[Sazary]

Сообщение от MaTBeu

Все пулы одинакового размера или каждый пул имеет такой размер, какой занимает в нем информация?

Изначально пул один - вся свободная память. По мере выделения/освобождения их количество увеличивается.
То есть, например, выделили память под блок - размер пула уменьшился, а адрес его начала сместился. Потом выделили второй блок, а первый освободили. В итоге имеем 2 пула - один в начале (до второго блока), второй - в конце.

Сообщение от Luke

А теперь - зачем при вызове int ars_free(char* block) занулять память?

Память я не зануляю. Я зануляю элемент массива blocks, чтобы показать, что блока с указанным индексом не существует.

Сообщение от Luke

И еще, зачем хранить длину блока памяти, не лешче ли хранить кол-во блоков?

У меня есть переменная BLOCKS_COUNT, которая хранит количество блоков. Но т.к. каждый блок имеет свой размер, то также есть массив с размерами.

[pu4koff]

я так понимаю информация между массивами pools, pools_size перекочевывает в blocks, block_size при malloc и наоборот при free? Это же долго будет массив "сдвигаться", чтобы удалить центральный элемент из него.
Я бы пожалуй реализовал примерно таким образом:
структура "блок памяти", хранящий начальный адрес и размер.
Соответственно, массив этих самых блоков памяти.
Свободные участки реализовал бы по типу односвязного списка (хотя может и на массиве оставил, тут думать надо и взвешивать все за и против ) и упорядочил по размеру блока (потому что достаточно важно использовать наиболее подходящий по размеру блок, чтобы не "резать" первый попавшийся, что в итоге окажется куча мелких блоков, в которые ничего не влезет). Размер и адрес для участка отдельно хранить бы не стал, а тупо ссылался на элемент общего массива блоков.
Выделенную память по тому же образу бы пожалуй хранил, но упорядочил уже по адресу, т.к. освобождается она именно по адресу.
Поддержание списка в отсортированном виде достаточно "дешево", но зато поиск потом будет шустрее работать. На массивах конечно это будет слишком дорого.
Вообще тут можно много чего напридумывать и лично мне очень сложно сделать выбор между занимаемой памятью и скоростью работы. Так и хочется хранить массив занятых блоков памяти, где индексом является адрес блока. Удаление будет моментальным, но на 10 метров "полезной" памяти будет в N-цать раз больше служебных данных храниться

[Sazary]

Сообщение от pu4koff

я так понимаю информация между массивами pools, pools_size перекочевывает в blocks, block_size при malloc и наоборот при free? Это же долго будет массив "сдвигаться", чтобы удалить центральный элемент из него.

Не совсем так. Информация всегда остается на месте. Она сдвигается только при вызове функции дефрагментации.

Т.к. мне нужно вернуть указатель на выделенную память, то просто как-то не вижу смысла создавать отдельную структуру. Проще, по-моему, использовать память как единый блок. Ведь блоки все равно нельзя держать в разных местах.

Сделать сортировку пулов по размеру, конечно, хорошо, но ведь как-то не очень эффективно с точки зрения скорости.

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

#include <string.h>

const int MAX_POOLS = 1000;
const long BUF_SIZE = 104888320;
 
static char ALLBUF[BUF_SIZE];             // доступная память
static unsigned long AVAIBLE = BUF_SIZE;  // свободно
static char* pools[MAX_POOLS];              // пулы
static unsigned int POOLS_COUNT = 1;        // количество пулов
static unsigned int pools_size[MAX_POOLS]; // размеры пулов

static char* blocks[MAX_POOLS];  // блоки
static unsigned int BLOCKS_COUNT = 0;  // количетсво существующих блоков
static unsigned int block_size[MAX_POOLS]; // размеры блоков
static unsigned int RIGHT_BLOCK;  // номер самого правого блока

// ---- обработка ошибок ----
static int ARS_ALLOC_ERR=0;   // флаг для ошибок

#define NO_MEMORY 1
#define BLOCK_NOT_FOUND 2


void ars_alloc_init(void);   // инициализация
char* ars_malloc(unsigned long Size);  // выделение
int ars_free(char*);                  // освобождение
int ars_defrag(void);               // дефрагментация
void ars_alloc_stat(char *str);   // статистика
int GetArsAllocError(void);       // возврат кода последней ошибки

//=========================================
void ars_alloc_init(void)
{
 pools[0] = ALLBUF; // начало первого пула
 pools_size[0] = AVAIBLE;
}
//=========================================

char* ars_malloc(unsigned long Size)
{
 unsigned long int i,k;
 char *p;
 
 // если требуют больше, чем есть
 if(Size > AVAIBLE)
  {
   ARS_ALLOC_ERR = NO_MEMORY;
   return 0;     
  }
 //----   
 p = 0;
 // ищем первый подходящий пул
 for(i=0; i<POOLS_COUNT; ++i)
   if(Size<=pools_size[i])
    {
     p = pools[i]; // запоминаем адрес
     k = i;      // ...и номер
     break;
    }
 
 if(!p)  // если подходящий пул не найден
  {
   ARS_ALLOC_ERR = NO_MEMORY;
   return 0;
  }   
 
 blocks[BLOCKS_COUNT] = p;  // здесь будет новый блок
 block_size[BLOCKS_COUNT] = Size;
 ++BLOCKS_COUNT;
 ++RIGHT_BLOCK;
 pools[k] = (char*)(p+Size+1);  // смещаем адрес начала пула на конец блока
 pools_size[k] = pools_size[k]-Size;  // и исправляем размер

 AVAIBLE -= Size;  // места стало меньше
 return p;  
}
//==========================================
 
int ars_free(char* block)
{
 unsigned int i,k;
 char* p = 0;
 // ищем блок по адресу
 for(i=0; i<RIGHT_BLOCK; ++i)
   if(block == blocks[i])
    {
     p = blocks[i];
     k = i;
     break;
    }
 if(!p) 
  {
   ARS_ALLOC_ERR = BLOCK_NOT_FOUND;
   return BLOCK_NOT_FOUND;  // блок не найден
  }
 
  blocks[k] = 0;  
  --BLOCKS_COUNT;
  pools[POOLS_COUNT] = block; // превращаем блок в пул
  pools_size[POOLS_COUNT] = block_size[k];
  ++POOLS_COUNT;
  AVAIBLE += block_size[k]; // места стало больше
  
 return 0;
}
//==========================================

// функция дефрагментирования. Смещает все блоки влево и оставляет
//  единственный пул

int ars_defrag(void)
{
unsigned int i,k;
char* p = ALLBUF;
char* t,*tmp;

for(i=0; i<RIGHT_BLOCK; ++i)
 {
  t = blocks[i];
  if(t == ALLBUF)
   {
    p = (char*)(blocks[i]+block_size[i]+1);
    continue;
   }
  tmp = p;
  for(k=0,t=blocks[i]; k<block_size[i]; ++k)
   *p++ = *t++; 
  blocks[i] = tmp; 
 }

 POOLS_COUNT = 1;
 pools[0] = p;
 AVAIBLE = BUF_SIZE - (unsigned long)(p-ALLBUF);
 pools_size[0] = AVAIBLE;
 RIGHT_BLOCK = 0; 
 return 0;
}
//==========================

// вывод статистики
void ars_alloc_stat(char *str)
{
 sprintf(str,"Statistic:\nAvaible: %ld of %ld bytes\nCount of blocks: %d\n", \
  AVAIBLE,BUF_SIZE,BLOCKS_COUNT); 
}
//====================

int GetArsAllocError(void)
{
 return ARS_ALLOC_ERR;
}

При этом, если верить диспетчеру задач, программа кушает около 100 метров вирт. памяти о_О.

[pu4koff]

Сообщение от Sazary

Сделать сортировку пулов по размеру, конечно, хорошо, но ведь как-то не очень эффективно с точки зрения скорости.

Если на массиве, то да. А если что-то среднее между списком и массивом попытаться собрать, чтобы был и список и никакого динамического выделения памяти не было... поддерживать список отсортированным ничего не стоит. Нужно всего-лишь в нужное место элемент воткнуть
Зато поиск по отсортированной последовательности в разы быстрее, чем простой линейный перебор.
Такую штуку конечно тестить нужно в идеале по взрослому. С профайлерами всякими. Занять всю память маленькими элементами, потом всё освободить и попытаться выделить под большие блоки, т.е. нужно делать поддержку "склеивания" свободных блоков.
Блин. Аж интересно стало как оно на практике это всё будет, что хоть тоже реализовывай
Ну а в целом, идея вроде неплохая и как учебный проект сойдёт. В реале еще и многопоточность появится в списке проблем

[Sazary]

Нечто среднее между списком и массивом? )
Но тогда нужно будет для единичного блока какой-то размер выбрать (>1), ведь если взять 1 байт, то это будет как-то расточительно (в структуре будет один элемент в 1 байт (для информации) и как минимум еще 4б под указатель на след. элемент). Но тогда такая проблема будет: а если юзер захочет выделить несколько участков по 1 байту? Ведь тогда все равно придется отдавать по целому блоку.

Значит, как я понял, склеивание лучше все-таки добавить? Лучше смотреться будет?

Всякие профайлеры я, конечно, использовать не буду
Да это и не проект скорее, а так.. Что-то поменьше. Все должны сделать 3 лабы на ввод-вывод-ветвления, а мне вот это дали

[pu4koff]

Сообщение от Sazary

Нечто среднее между списком и массивом? )
Но тогда нужно будет для единичного блока какой-то размер выбрать (>1), ведь если взять 1 байт, то это будет как-то расточительно (в структуре будет один элемент в 1 байт (для информации) и как минимум еще 4б под указатель на след. элемент).

Ага. Это минус, но зато оптимальный по размеру блок быстро будет искаться. Я же говорю, что мне сложно выбрать между объемом служебной информации и скоростью работы

Сообщение от Sazary

Но тогда такая проблема будет: а если юзер захочет выделить несколько участков по 1 байту? Ведь тогда все равно придется отдавать по целому блоку.

Ну для мелких кусков можно сделать что-то вроде частного случая. Осталось только придумать как это всё реализовать

Сообщение от Sazary

Значит, как я понял, склеивание лучше все-таки добавить? Лучше смотреться будет?

Ну как бы без склеивания просто рано или поздно получится, что имеется куча мелких пулов, что ни один из них не подойдет по размеру. Но для этого функция дефрагментации есть. Так что наверно и не стоит особо мучиться по этому поводу.
Так вот "на глаз" и не определишь просто что будет оптимальнее: дефрагментация по мере необходимости или же частичная дефрагментация "на лету", путём склеивания соседних свободных блоков памяти.

Сообщение от Sazary

Всякие профайлеры я, конечно, использовать не буду
Да это и не проект скорее, а так.. Что-то поменьше. Все должны сделать 3 лабы на ввод-вывод-ветвления, а мне вот это дали

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

[Sazary]

Все ясно.. Тогда свой вариант пока оставлю как есть.

Но задача, вообще, заинтересовала ) Хотя бы потому, что раньше с таким не сталкивался. А что-то "более интересное" (и не очень) у меня по другим предметам ) Поэтому, когда захочется передохнуть, буду думать над этой задачей.

И вот что непонятно: функция должна возвращать указатель на чар, но как тогда можно организовать память в виде единичных блоков с указателями на следующий?
Вот никак не придумать, как избавиться от изначально заданного количества блоков. Вдруг юзер захочет выделить память под массив из 10 мегабайт char'ов.. В моем варианте, например, можно выделить только 1000 (ну или сколько укажешь).

Мне кажется, или без этого ограничения никак не обойтись?