সরল মেমোরি ম্যানেজার

μnix এর জন্য খুব সাধারণ একটা মেমোরি ম্যানেজার বানিয়েছিলাম কিছুদিন আগে। বর্তমানে এটার স্লথগতির জন্য এটাকে আর ব্যবহার করছি না। তবে মেমোরি ম্যানেজার কিভাবে বানানো যায় সেটার একটা উদাহরণ হতে পারে। এটা একটা লিংকড লিস্ট ব্যবহার করে বানানো। অপারেটিং সিস্টেমের জন্য এর চেয়ে ভাল ডাটা স্ট্রাকচার ব্যবহার করতে হবে। বর্তমানে আমি Splay Tree ব্যবহার করছি। অনেকে বলেন AVL Tree ব্যবহার করার কথা। ডেমো এর সুবিধার জন্য এটাকে একটা ইউজার মোড অ্যাপ্লিকেশন হিসাবে দিলাম (টেস্ট করার জন্য অপারেটিং সিস্টেম বানাতে হলে বিপদ!)।

#include "stdio.h"
#include "memory"

#define SIZE 1024*1024
#define MEMORY_USED 0x1
#define DEAD_SIGN 0xEFBEADDE

#define SIGN 0xABCD08EF

#define panic(message)

#define assert(cond) if(!cond){panic("ASSERTION FAILED")}

#define INCLIDE_SANITY_CHECK_CODE

struct memblk{
#ifdef INCLIDE_SANITY_CHECK_CODE
    int signature;
#endif

    memblk *prev,*next;
    unsigned int managed_data, size;
    void *memory;
};

#define MEM_BLK_STRUCT_SIZE (sizeof(memblk) - sizeof(void*))

void *block = NULL;
memblk *head = NULL;

memblk* find_free_block(unsigned int size)
{
    assert(size);

    memblk *cur_blk = head, *free_blk = NULL;

    while(!free_blk)
    {
        if(!(cur_blk->managed_data & MEMORY_USED) && cur_blk->size >=size)
        {
            free_blk = cur_blk;
            break;
        }

        if(cur_blk->next == NULL)
        {
            break;
        }

        cur_blk=cur_blk->next;
    }

    return free_blk;
}

void split_block(memblk *free_blk, unsigned int size)
{
 assert(free_blk->size > (size + MEM_BLK_STRUCT_SIZE));

    //create a new block as next block
    void *address = &(free_blk->memory);
    memblk *next = (memblk *)((int)address + size);
    memset(next, 0, MEM_BLK_STRUCT_SIZE);
#ifdef INCLIDE_SANITY_CHECK_CODE
    next->signature = SIGN;
#endif
    next->prev = free_blk;
    next->next = free_blk->next;
    next->size = free_blk->size - (size + MEM_BLK_STRUCT_SIZE);

    free_blk->next = next;
    free_blk->size = size;
}


void * mem_alloc(unsigned int size)
{
    assert(size);

    if(size<1)
    {
        return NULL;
    }

    memblk* free_blk = find_free_block(size);

    if(free_blk == NULL)
    {    
        return NULL;
    }    
    
    if(free_blk->size > (size + MEM_BLK_STRUCT_SIZE))
    {
        split_block(free_blk, size);
    }
    
    free_blk->managed_data |= MEMORY_USED;
    return &(free_blk->memory);
}

void merge_blocks(memblk *left_blk, memblk *right_blk)
{
    assert(left_blk);
    assert(right_blk);
    assert(!(left_blk->managed_data & MEMORY_USED));
    assert(!(right_blk->managed_data & MEMORY_USED));

    left_blk->next = right_blk->next;
    left_blk->size += (right_blk->size + MEM_BLK_STRUCT_SIZE);

    if(right_blk->next)
    {
        right_blk->next->prev = left_blk;
    }

#ifdef INCLIDE_SANITY_CHECK_CODE
    memset(right_blk, 0xC3, MEM_BLK_STRUCT_SIZE);
#endif
}

void mem_free(void *address)
{
    assert(address);

    memblk *block = (memblk *)((int)address - MEM_BLK_STRUCT_SIZE);

#ifdef INCLIDE_SANITY_CHECK_CODE
    memset(address, 0xAC, block->size);
#endif

    block->managed_data &= ~MEMORY_USED;

    memblk *left_blk = block->prev;
    memblk *right_blk = block->next;
    memblk *cur_blk=block;
    if(left_blk && !(left_blk->managed_data & MEMORY_USED))
    {        
        merge_blocks(left_blk, cur_blk);
        cur_blk = left_blk;
    }

    if(right_blk && !(right_blk->managed_data & MEMORY_USED))
    {
        merge_blocks(cur_blk, right_blk);
    }
}

void print_heap()
{
    memblk *cur_blk=head;
    int count = 0;

    while(cur_blk)
    {
        printf("Block %d: Address: %d Next %d Prev %d Size: %d Used=%s\n", count, cur_blk, cur_blk->next, cur_blk->prev, cur_blk->size, (cur_blk->managed_data & MEMORY_USED)?"Yes":"No");
        count++;
        cur_blk=cur_blk->next;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    block = malloc(SIZE);
    memset(block, 0, SIZE);

    head = (memblk*)block;
#ifdef INCLIDE_SANITY_CHECK_CODE
    head->signature = SIGN;
#endif
    head->prev = NULL;
    head->next = NULL;
    head->managed_data = 0;
    head->size = SIZE - MEM_BLK_STRUCT_SIZE;

    print_heap();
    printf("-------------------------------------------\n");
    void *mem=mem_alloc(16);
    memset(mem, 0xD1, 16);

    print_heap();
    printf("-------------------------------------------\n");

    void *mem2=mem_alloc(32);
    memset(mem2, 0xD2, 32);

    print_heap();
    printf("-------------------------------------------\n");


    void *mem3=mem_alloc(64);
    memset(mem3, 0xD3, 64);

    print_heap();
    printf("-------------------------------------------\n");

    mem_free(mem2);

    print_heap();
    printf("-------------------------------------------\n");


    mem_free(mem);

    print_heap();
    printf("-------------------------------------------\n");

    mem_free(mem3);

    print_heap();
    printf("-------------------------------------------\n");

    return 0;
}