SLAB allocator

slab_alloc.c

#include <stdio.h>
#define ORDER 10
#define POWER 1024 /* 2^ORDER */

/**
 * Эти две функции вы должны использовать для аллокации
 * и освобождения памяти в этом задании. Считайте, что
 * внутри они используют buddy аллокатор с размером
 * страницы равным 4096 байтам.
 **/

/**
 * Аллоцирует участок размером 4096 * 2^order байт,
 * выровненный на границу 4096 * 2^order байт. order
 * должен быть в интервале [0; 10] (обе границы
 * включительно), т. е. вы не можете аллоцировать больше
 * 4Mb за раз.
 **/
void *alloc_slab(int order);
/**
 * Освобождает участок ранее аллоцированный с помощью
 * функции alloc_slab.
 **/
void free_slab(void *slab);

struct object {
    struct object* next;
};

struct slab {
    size_t count; // кол-во свободных эл-ов в этом SLAB
    struct object* free; // укзатель на первый элемент списка объектов
    struct slab* prev; // указатель на предыдущий SLAB
    struct slab* next;
};

/**
 * Эта структура представляет аллокатор, вы можете менять
 * ее как вам удобно. Приведенные в ней поля и комментарии
 * просто дают общую идею того, что вам может понадобится
 * сохранить в этой структуре.
 **/
struct cache {
    struct slab* empty_slab; /* список пустых SLAB-ов для поддержки cache_shrink */
    struct slab* work_slab; /* список частично занятых SLAB-ов */
    struct slab* busy_slab; /* список заполненых SLAB-ов */
    struct slab** slabs[3]; // сохраним указатели на SLAB-ы для простого обхода

    size_t object_size; /* размер аллоцируемого объекта */
    size_t slab_order; /* используемый размер SLAB-а */
    size_t slab_objects; /* количество объектов в одном SLAB-е */

    cache()
        : empty_slab(NULL)
        , work_slab(NULL)
        , busy_slab(NULL)
    {
        slabs[0] = &empty_slab;
        slabs[1] = &work_slab;
        slabs[2] = &busy_slab;
    }
};

/**
 * Функция создает пустой SLAB и добавляет в cache, в список
 * пустых SLAB-ов. Функцию следует вызывать, _только_
 * если список пустых SLAB-ов пуст.
 * cache->object_size должен быть проинициализирован.
 *
 * retval - число свободных объектов в SLAB.
 **/
int mkslab(struct cache * const cache)
{
    void* memchunk = alloc_slab(ORDER);
    cache->empty_slab = (struct slab*) memchunk;

    struct slab freeslab;
    freeslab.count = (4096*POWER - sizeof(struct slab))
                   / (cache->object_size + sizeof(struct object*));
    freeslab.free = (struct object*) ((char*) memchunk + sizeof(struct slab));
    freeslab.prev = NULL;
    freeslab.next = NULL;

    struct object* ptr = freeslab.free;
    for(size_t i = 0; i < freeslab.count - 1; ++i){
        ptr->next = (object*) (((char*) (ptr + 1)) + cache->object_size);
        ptr = ptr->next;
    }
    ptr->next = NULL;

    *(cache->empty_slab) = freeslab;

    return freeslab.count;
}

/**
 * Функция инициализации будет вызвана перед тем, как
 * использовать этот кеширующий аллокатор для аллокации.
 * Параметры:
 *  - cache - структура, которую вы должны инициализировать
 *  - object_size - размер объектов, которые должен
 *    аллоцировать этот кеширующий аллокатор 
 **/
void cache_setup(struct cache *cache, size_t object_size)
{
    cache->object_size = object_size;
    size_t cnt = mkslab(cache);
    cache->slab_order = 4096*POWER;
    cache->slab_objects = cnt;
}

/**
 * Функция освобождения будет вызвана когда работа с
 * аллокатором будет закончена. Она должна освободить
 * всю память занятую аллокатором. Проверяющая система
 * будет считать ошибкой, если не вся память будет
 * освбождена.
 **/
void cache_release(struct cache *cache)
{
    struct slab* pslab = NULL;
    struct slab* pslab_next = NULL;
    for(size_t i = 0; i < 3; ++i)
    {
        pslab = *(cache->slabs[i]);
        while(NULL != pslab)
        {
            pslab_next = pslab->next;
            free_slab((void*) pslab);
            pslab = pslab_next;
        }
    }
}

/**
 * Добавление SLAB-а в голову списка to из списка from.
 **/
struct slab* mvslab(struct slab** from, struct slab** to)
{
    struct slab* pslab = *to; // сохранить указатель на to
    *to = *from; // теперь to то же, что и from
    // убрать SLAB из списка from, пока поле next не поменяли
    (*from) = (*from)->next;
    (*to)->prev = NULL;
    (*to)->next = pslab; // next указывает на старый список to
    if(NULL != pslab)
    {
        pslab->prev = *to;
    }
    return *to;
}

/**
 * Функция аллокации памяти из кеширующего аллокатора.
 * Должна возвращать указатель на участок памяти размера
 * как минимум object_size байт (см cache_setup).
 * Гарантируется, что cache указывает на корректный
 * инициализированный аллокатор.
 **/
void *cache_alloc(struct cache *cache)
{
    struct slab* source = cache->work_slab;
    if(NULL != source)
    { // список рабочих SLAB-ов
        if(NULL == cache->work_slab->free->next)
        { // если элемент в SLAB-е единственный свободный
            // добавить в голову списка busy_slab
            source = mvslab(&cache->work_slab, &cache->busy_slab);
        }
    }
    else
    { // взять объект из empty_slab
        if(NULL == cache->empty_slab)
        { // создать в cache еще один пустой slab
            mkslab(cache);
        }
        // добавить пустой SLAB в голову списка work_slab
        source = mvslab(&cache->empty_slab, &cache->work_slab);
    }
    void* allocated = (void*) source->free;
    source->free = source->free->next;
    --(source->count);

    return allocated;
}

/**
 * Функция освобождения памяти назад в кеширующий аллокатор.
 * Гарантируется, что ptr - указатель ранее возвращенный из
 * cache_alloc.
 **/
void cache_free(struct cache* cache, void* ptr)
{
    // из адреса объекта получить адрес slab
    struct slab* p = (struct slab*) ((size_t) ptr & ~(cache->slab_order - 1));
    // вставить в голову списка новый свободный объект
    struct object* temp_free = p->free;
    p->free = (struct object*) ptr;
    p->free->next = temp_free;
    ++(p->count);
    if(cache->slab_objects == p->count)
    { // если объект из work_slab и у него был аллоцирован только 1 объект
        // вставить в голову списка empty_slab

            mvslab(&cache->work_slab, &cache->empty_slab);
 
    }
    else if(1 == p->count)
    { // этот объект был из busy_slab
        // вставить в голову списка work_slab
            mvslab(&cache->busy_slab, &cache->work_slab);
  
    }
}


/**
 * Функция должна освободить все SLAB, которые не содержат
 * занятых объектов. Если SLAB не использовался для аллокации
 * объектов (например, если вы выделяли с помощью alloc_slab
 * память для внутренних нужд вашего алгоритма), то освбождать
 * его не обязательно.
 **/
void cache_shrink(struct cache *cache)
{
    struct slab* ptr = cache->empty_slab;
    struct slab* temp_ptr;
    while(NULL != ptr){
        temp_ptr = ptr->next;
        free_slab((void*) ptr);
        ptr = temp_ptr;
    }
    cache->empty_slab = NULL;
}