Writing Our Own Memory Manager In C/C++

Requirements

• GNU/Linux Operating System (Any Distribution)
• GCC (GNU Compiler Collection with C compiler)
• Any Editor (Vi/Emacs/Gedit etc.)

This article is divided into two sections, the first is to write our own simple memory allocator (malloc) function and the second is to implement memory management schemes such as Paging & Segmentation.

To allocate memory we will use kernel system call sbrk(). 

 

Introduction

The memory management function keeps track of the status of each memory location, either allocated or free. It determines how memory is allocated among competing processes, deciding which gets memory, when they receive it, and how much they are allowed.

The work of memory manager is to allocate memory, manage memory by providing memory addresses to a Loader, a program that loads another program into main memory using memory addresses provided by memory manager.

 

So how to allocate memory ?

We are using sbrk() system call which takes an positive integer value and increases the size of the heap on main memory.

For more information view main page for it. "main sbrk"

 

Well you have studied data structures at some point in programming, but where and how actually is it used in developing OS?

 

Consider we have many processes for which we need to allocate memory; if we allocate memory for one process and move to second process for allocation,  how will you keep track of last allocated memory block? For this we need to store some metadata with allocated memory block such as pointer points to a next block, memory address, isfree etc.

So it will form a Linked List data structure the same as the following image.

 

So where does our memory block get stored using sbrk() call?

In the following image the break point is the point pointed by "sbrk(0)", if we increases the size by calling sbrk() then the break point increases.

  

Ok now let's start by writing our simple memory allocator program.

  

Remember our program is only the small part of the memory manager implemented by the kernel itself, so whatever the

memory address you see through this; and other programs are Virtual addresses not physical addresses.

This is just an understanding of an implementation of memory manager and their algorithms.

 

You see above linked list image, let's define structure for it to use it as a metadata.

typedef struct __s_block{
    struct __s_block *next;
    bool isfree;
    size_t size;
    void *memoryAddress;
}_SBLOCK;


#define BLOCK_SIZE sizeof(_SBLOCK)

next   :   Pointer that points to a next memory block.

isfree :   To check whether memory block is free or not.

size   :   Size which is allocated in the memory.

memoryAddress  :  Starting memory address from where the memory is allocated.

BLOCK_SIZE  :  Size of the structure. 

 

Ok now let's write a function that allocates memory block(allocateMemBlock).

_SBLOCK *allocateMemBlock(size_t size)
{
    _SBLOCK *block = (_SBLOCK*)sbrk(0);
    void *memadr = (void*)sbrk(0);
    void *allocate_mem = (void*)sbrk(BLOCK_SIZE + size);

    if(allocate_mem == (void*)-1){
        return NULL;
    }else{
        block->next = NULL;
        block->isfree = false;
        block->size = size;
        block->memoryAddress = memadr+BLOCK_SIZE;
        return block;
    }
}

This function takes an argument of how much size it wants to allocate.  This function is nothing but to add a new node to a linked list.

 

_SBLOCK *block = (_SBLOCK*)sbrk(0);

             First store sbrk(0) means store break point memory address to block so that we can starts our memory allocation from break point.

 

void *memadr = (void*)sbrk(0);

             Store memory address to memadr.

 

void *allocate_mem = (void*)sbrk(BLOCK_SIZE + size);

            Change the location of program break by calling sbrk() call with increment of our metadata block size and how much memory needs to allocate. 

 

Check allocate_mem is equal to (void*)-1 means error then it returns NULL. If not then it stores approriate data into structure variables and returns an allocated block.

 

Ok now we added a new node to our linked list. So we need to add more blocks(nodes) to our linked list.  As you know we are allocating memory for our linked list data structure, so we cannot add a node to the beginning of the list, we need to add it to the end of the list. Here i used singly linked list to manage memory blocks but you can use doubly linked list for both sides.

Here's the function that allocates the next new block and sets the pointers to form a complete linked list.

void allocateNextMemBlock(size_t size, _SBLOCK **head)
{
    _SBLOCK *current = *head;
    void *allocate_mem = NULL;
    void *memadr = (void*)sbrk(0);

    if(current==NULL){
        *head = allocateMemBlock(size);
    }else{
        while(current->next != NULL){
            current = current->next;
        }
        _SBLOCK *newblock = sbrk(0);

        allocate_mem = (void*)sbrk(BLOCK_SIZE + size);
        if(allocate_mem == (void*) - 1){ }
        else{
            newblock->next = NULL;
            newblock->isfree = false;
            newblock->size = size;
            newblock->memoryAddress = memadr+BLOCK_SIZE;
            current->next = newblock;
      }
    }
}

First get the last memory block by traversing, add a new node to the next node of the current last node.

 

You can see that we are using isfree variable to check whether current memory block is free or not. Freeing memory means to just overwrite the contents. So for freeing the memory we will set isfree variable value to true. When another block wants to allocate some memory it will check only this variable value for true.

void freeMemBlock(_SBLOCK **head)
{
    if(*head == NULL){}
    else{
        (*head)->isfree = true;
    }
}

Here's the complete program for simple memory allocator.

#include<stdio.h>
#include<stdbool.h>

typedef struct __s_block{
    struct __s_block *next;
    bool isfree;
    size_t size;
    void *memoryAddress;
}_SBLOCK;

#define BLOCK_SIZE sizeof(_SBLOCK)

_SBLOCK *allocateMemBlock(size_t size)
{
    _SBLOCK *block = (_SBLOCK*)sbrk(0);
    void *memadr = (void*)sbrk(0);
    void *allocate_mem = (void*)sbrk(BLOCK_SIZE + size);

    if(allocate_mem == (void*)-1){
        return NULL;
    }else{
        block->next = NULL;
        block->isfree = false;
        block->size = size;
        block->memoryAddress = memadr+BLOCK_SIZE;
        return block;
    }
}


//allocate next memory block
void allocateNextMemBlock(size_t size, _SBLOCK **head)
{
    _SBLOCK *current = *head;
    void *allocate_mem = NULL;
    void *memadr = (void*)sbrk(0);

    if(current==NULL){
        *head = allocateMemBlock(size);
    }else{
        while(current->next != NULL){
            current = current->next;
        }
        _SBLOCK *newblock = sbrk(0);

        allocate_mem = (void*)sbrk(BLOCK_SIZE + size);
        if(allocate_mem == (void*) - 1){ }
        else{
            newblock->next = NULL;
            newblock->isfree = false;
            newblock->size = size;
            newblock->memoryAddress = memadr+BLOCK_SIZE;
            current->next = newblock;
      }
    }
}


void freeMemBlock(_SBLOCK **head)
{
    if(*head == NULL){}
    else{
        (*head)->isfree = true;
    }
}


void printMemBlocks(_SBLOCK *current)
{
    while(current != NULL){
        printf("isfree = %d, size = %d, memoryAddress = %p, current = %p, next-node = %p\n",
                current->isfree, current->size, current->memoryAddress, current, current->next);
        current = current->next;
    }
}


int main()
{
    _SBLOCK *sMemBlock = NULL;
    allocateNextMemBlock(10,&sMemBlock);
    allocateNextMemBlock(35,&sMemBlock);
    allocateNextMemBlock(62,&sMemBlock);
    printMemBlocks(sMemBlock);

    printf("\nAfter freeing second node\n");
    freeMemBlock(&(sMemBlock->next));
    printMemBlocks(sMemBlock);

    return 0;
}

Compile this program using gcc -w <file_name>.c command and then execute it(./a.out). 

 

For the rest of the programs I am reading their input from a file which contains a number of processes and how much memory they need. To read data from a file I am using linked lists by reading each character from a file, and forming real data from it. I  know we can directly read integers from a file, but if we want to read some specific data labeled by a string then you cannot do that by just reading an integer, you may lose that specific data.

I have written a simple parser for reading data from a file(getDataFromFile.c).

 

Allocate All Memory

 

If a given process's size is enough to satisfy the memory then allocate all the memory to all processes. This is good for embeded systems which have finite memory and processes but not in general. In allocating all memory we just need to add nodes in the linked list and print their memory addresses. where : _PROCINTNODE is the linked list that contains process id & required size. It is a structure defined like this.

typedef struct __procintnode {
    int process;
    int size;
    struct __procintnode *next;
}_PROCINTNODE;

void allocate_allMemory(_SBLOCK **blockHead,_PROCINTNODE *procinthead)
{
    _PROCINTNODE *current = procinthead;

    printf("\n\t\t[ All Memory allocated to processes]\n");
    printf("-------------------------------------------------------------------------");
    printf("\n|  Process   |   Start Address   |   End Address    |      Size       |\n");
    printf("-------------------------------------------------------------------------\n");

    while(current != NULL){
        void *start_address = sbrk(0) + 1;
        allocateNextMemBlock(current->size + 1, &(*blockHead));
        void *end_address = sbrk(0);
        float size_kb = (current->size)/1024.0;

        printf("|     P%d     |     %p     |    %p     |     %.3fKB     |\n",
                current->process, start_address, end_address, size_kb);

        current = current->next;
    }
    printf("-------------------------------------------------------------------------\n");
    printf("\n\n");
    printf("\n\tCurrent brk pointer is here (sbrk(0)) = %p\n", sbrk(0));


    //release the allocated memory
    printf("\n\t\t\t[ Memory released ]\n\n");
    _SBLOCK *lastblock, *blockcurrent = *blockHead;
    while(blockcurrent != NULL){
        blockcurrent->isfree = true;
        if(blockcurrent->next == NULL){
                lastblock = blockcurrent;
        }
        blockcurrent = blockcurrent->next;
    }

    blockcurrent = lastblock;
    int proc_length = _countPROCINTNodes(procinthead);

    while(blockcurrent->prev != NULL){
        if(blockcurrent->isfree){
            (blockcurrent->prev)->next = NULL;
            if(blockcurrent->prev == NULL){
                sbrk(0-(BLOCK_SIZE + blockcurrent->size + 1));
                printf("\nProcess P%d : sbrk(0) is %p\n", proc_length, sbrk(0));
            }
            sbrk(0-(BLOCK_SIZE + blockcurrent->size + 1));
            printf("\nProcess P%d : sbrk(0) is %p\n", proc_length, sbrk(0));
        }
        blockcurrent = blockcurrent->prev;
        proc_length--;
    }

    sbrk(0 - (BLOCK_SIZE + blockcurrent->size + 1));
    printf("\nProcess P%d : sbrk(0) is %p\n",proc_length,sbrk(0));
    *blockHead=NULL;

}

Paging

 

Paging is the memory management scheme in which each process is divided into equal size of pages. Then the memory is allocated for each page for its processing.

Paging gives the idea of Virtual memory. Virtual memory is the memory whose smallest part is of the physical memory address. Virtual memory addresses could be infinite. Then the mapping is done to calculate the actual physical memory address. 

  

But the size of all the memory is fixed, we need to reuse those page blocks which have done their jobs. For this you can use many algorithms such as Most Recently Used(MRU), Least Recently Used(LRU), Most Frequently Used(MFU) etc.

  

As far as our memory management program, we dont know what is the physical address, so we cannot do mapping. We will just use the virtual addresses provided by the kernel for our program.

 

For our implementation of paging, we need two tables, Virtual & Physical table.

 

Download the source code to view code for implementation of paging.

See the following image.

  

#define MAX_MEM_SIZE (1024*1024)

#define PAGE_SIZE 4096
#define MAX_PAGES 256
#define PAGE_MEM_SIZE 0x256


//structure for store virtual memory data using paging
typedef struct __memvirtpageblocks{
    struct __memvirtpageblocks *next;
    size_t size;
    int process;
    int pagenumber;
    void *memoryaddress;
}_VIRTMEMPAGEBLOCKS;


//structure for allocate memory using paging
typedef struct __mempageblocks{
    struct __mempageblocks *next;
    bool isfree;
    void *memoryaddress;
}_MEMPAGEBLOCKS;

#define MEM_PAGE_BLOCK_SIZE sizeof(_MEMPAGEBLOCKS)

MAX_MEM_SIZE   :  Which is our maximum whole memory(main memory) size which is 1MB.

MAX_PAGES   :   Maximum number of pages.

PAGE_MEM_SIZE   :  Size of each page.

I used three functions to implement paging,

void divideProc_Mem_IntoPageBlocks(_PROCINTNODE *procinthead,
                                                             _VIRTMEMPAGEBLOCKS **virtmempageblockshead,
                                                             _MEMPAGEBLOCKS **mempageblocksHead)

void mapVirtPhyAddressPageTable(_VIRTMEMPAGEBLOCKS **virtmempageblockshead,
                                                         _MEMPAGEBLOCKS **mempageblocksHead)

void AllocatePAGING(_SBLOCK *s_blockHead,
                                   _VIRTMEMPAGEBLOCKS *virtmempageBlocks,
                                   _MEMPAGEBLOCKS *mempageBlocks,
                                   const char *inputFile)

In the first function I am dividing our process & memory into equal sized  page blocks and forming a linked list of them(_VIRTMEMPAGEBLOCKS & _MEMPAGEBLOCKS).

In the second function I am mapping a virtual to physical address, as you know we dont know the actual physical address, so we will just print the address provided by sbrk() sys call.

In the third function I am calling all paging functions, and reading data from inputFile etc.
 

Segmentation

 

This is another memory management scheme which is like paging but it uses segments whose size is variable rather than fixed. Segmentation also provides a virtual memory. Also in this scheme memory mapping is done to find the actual physical memory address.

 

As I said the size of each segment is variable, but how much ?

You know memory is fixed in size, so you cannot allocate whole memory to only one process. So the size of the segment is also fixed but this fixed size is used only when it's needed. If some process requires a lesser size than the fixed segment then allocate memory only for that process otherwise allocate fixed segment size. Segmentation consists of ansegment table which contains segment number, size, process id, physical address, virtual address etc.

 

Download the source code to view code for implementation of segmentation.

See following image.

    

#define MAX_SEGMENT_SIZE 256000

typedef struct __memsegmentblocks{
    struct __memsegmentblocks *next;
    bool isfree;
    size_t size;
    void *memoryaddress;
}_MEMSEGMENTBLOCKS;


#define MEM_SEGMENT_BLOCK_SIZE sizeof(_MEMSEGMENTBLOCKS)

I used four functions to implement segmentation

void allocateMemory_using_Segmentation(_PROCINTNODE **procinthead,
                                                                     _MEMSEGMENTBLOCKS **memSegBlockshead)

void getFreeMemoryAddress(_MEMSEGMENTBLOCKS *memSegBlockshead,
                                                unsigned int size,
                                                void **start_address)

void allocateMemory_using_Segment_remain(_PROCINTNODE **procinthead,
                                                                           _MEMSEGMENTBLOCKS **memSegBlockshead)

void AllocateSEGMENTATION(_SBLOCK *s_blockHead,
                                               _MEMSEGMENTBLOCKS *memSegBlocksHead,
                                               const char *inputFile)

In the first function i am allocating memory to each process according to their size. Once memory is allocated to some processes memory gets full, so we will just free the memory. Using second & third functions i am allocating memory to those processes whose task is still not completed. In the fourth function I am calling all segmentation functions by reading data from inputFile. 

 

Alright you might be wondering what this program does; well, it allocates a memory in the form of a linked list, and generates the memory addresses. These memory addresses are then used by the program loader & processes to complete its task in the allocated memory addresses.

This is just an abstract implementation of memory manager which is used in operating systems using standard C libraries.