Click here to Skip to main content
13,260,383 members (44,443 online)
Click here to Skip to main content
Add your own
alternative version

Stats

9.1K views
235 downloads
14 bookmarked
Posted 6 Apr 2017

Writing Our Own Simple Memory Manager In C/C++

, 6 Apr 2017
Rate this:
Please Sign up or sign in to vote.
In this article we will write our own memory manager by implementing our malloc function and memory management schemes such as FCFS, Paging, Segmentation etc using linked list in C/C++

 

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 man page for it. "man sbrk"

or see following article

                       Special Features of Linux Memory Management Mechanism

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,first is to write our own simple memory allocator(malloc) function and second is to implement memory management schemes such as Paging & Segmentation.
To allocate memory we will use kernel system call sbrk().
 

Using the code

Well you have studied data structures at some point in programming.but where and how actually it is 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, so how will you keep track of last allocated memory block, for this we need to store some metadata with allocated memory block such as poiter points to a next block, memory address, isfree etc.
So it will form a Linked List data structure same as following image.

So where does our memory block is stored using sbrk() call.
In following image break point is the point pointed by "sbrk(0)", if we increases the size by calling sbrk() then break point is increases.

Ok now lets 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 throuout 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, lets 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 lets write a function that allocate 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 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 in increasing then return NULL.
If not then store approriate data into structure variables and return a 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 traversing.

If you 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 rest of the programs i am reading their input data from a file.
A file which contain a number of processes and how much memory they require.
To reading a data from a file i am using linked list by reading each character from file, and forming a real integer data from it.
well 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 lost that specific data.
I have written a simple parser for reading data from a file(getDataFromFile.c).

 

Allocate All Memory

If given processes size are enough to satisfy the memory then allocate whole memory to all processes.
This is good for embeded systems who have finite memory and processes but not for general.
In allocating all memory we just need to add nodes in the linked list and printing their memory addresses.

where : _PROCINTNODE is the linked list that contains process id & required size.

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 didvided 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 little bit part is of the physical memory address.
Virtual memory addresses could be infinite. Then the mapping is done to calculate actual physical memory address.

But the size of whole memory is fixed, we need to reuse those page blocks who has 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 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 first function i am dividing our process & memory into equal size of page blocks and forming a linked list of them(_VIRTMEMPAGEBLOCKS & _MEMPAGEBLOCKS).
In second function i am mapping a virtual to physical address, as you know we dont know actual physical address,so we will just print the address provided by sbrk() sys call.
In third function i am calling all paging functions,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 size in paging. 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 segment is also fixed but this fixed size is used only when its needed.
if some process requires lesser size than fixed segment then allocate memory only for that process otherwise allocate fixed segment size.

Segmentation consists of an segment table which contain 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 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 or allocating memory to remaining processes segments.
In fourth function i am calling all segmentation functions by reading data from inputFile. 
 

 

Alright you might be thinking that what does this program do, well it allocates a memory in the form of 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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Pritam Zope
Software Developer
India India
Hi, I am a programmer/developer. I code in several programming languages such as C, C++, C#, Java, Win32, Linux shell, OpenGL, HTML/CSS etc. My favorites are C/C++, C# and Java

You may also be interested in...

Pro
Pro

Comments and Discussions

 
QuestionMissing snippet Pin
Nelek7-Apr-17 0:52
protectorNelek7-Apr-17 0:52 
AnswerRe: Missing snippet Pin
Pritam Zope7-Apr-17 4:15
memberPritam Zope7-Apr-17 4:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.171114.1 | Last Updated 6 Apr 2017
Article Copyright 2017 by Pritam Zope
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid