Skip to content

Instantly share code, notes, and snippets.

Last active November 17, 2021 11:20
Show Gist options
  • Save Bogdan-Ciurea/2ab1277de2c931925b9990203679c053 to your computer and use it in GitHub Desktop.
Save Bogdan-Ciurea/2ab1277de2c931925b9990203679c053 to your computer and use it in GitHub Desktop.
#include "memory_management.h"
// The start of the linked list of blocks
block *global_head = NULL;
* @brief We will find a possible place to allocate the needed memory
* If we have a bigger free space than we need, we will then divide the space
* that we have.
* @param last a double pointer to the place we want the memory to allocate
* @param size the size that we want to allocate
* @return A block pointer to the place that we found to be suitable.
block *find_free_block(block **last, int size) {
block *current = global_head;
// Find a block that has a >= size than we need and it's free
while (current && !(current->free && current->size >= size)) {
*last = current;
current = current->next;
// Return the current pointer as it is if the size is the same
// or we didn't get a suitable pointer
if( current == NULL || current->size - size <= sizeof(block) + sizeof(int))
return current;
// If we have more available space than needed
// we can use just the needed size to allocate the needed memory
// Find out the distance to the top of the heap
block *looper = current->next;
int size_of_movment = current->size - size;
while(looper) {
size_of_movment += looper->size + sizeof(block);
looper = looper->next;
// Move the sbrk down
// Make the new block
block *new_block = (block*) sbrk(0);
//Move the sbrk back to the top
new_block->size = current->size - size - sizeof(block);
if (current->next)
current->next->previous = new_block;
new_block->free = true;
new_block->next = current->next;
new_block->previous = current;
current->size -= new_block->size + sizeof(block);
current->next = new_block;
return current;
* @brief Will make space for a new memory and add it to the new list.
* @param last the block that we want to split
* @param size the size of the new space that we want to allocate
* @return A pointer to the new block.
block *add_new_block(block *last, int size) {
block *new;
new = (block*) sbrk(0);
void *request = sbrk(size + sizeof(block));
if (request == (void*) - 1)
return NULL; // sbrk failed.
if (last) // NULL on first request.
last->next = new;
new->size = size;
new->free = false;
new->next = NULL;
new->previous = last;
return new;
* @brief My malloc function. A block of memory will be freed.
* If the block is at the end of the heap, the sbrk function will be called
* and move the pointer down by the size of the heap + sizeof(block).
* In case a block has another free adjacent block, the two blocks
* will be merged.
* @param size the size of the block we want to allocate
* @return The pointer to the location that we allocated
void *_malloc(int size) {
block *current;
if (size <= 0)
return NULL;
// The first usage of the global_head
if (!global_head) {
current = add_new_block(NULL, size);
if (!current)
return NULL;
global_head = current;
return ++current;
block *last = global_head;
current = find_free_block(&last, size);
// If we do not find a free block, then we allocate one
// to the end of the heap
if (!current) { // Failed to find free block.
current = add_new_block(last, size);
if (!current)
return NULL;
} else {
// If we find a suitable space we put the data in there
current->free = false;
return ++current;
* @brief Will merge all neighboring blocks of a block to make room
* for bigger spaces to be allocated.
* @param current The block that we want to merge
* @return The location of the new block
block *merge(block *current) {
if (current->free == false)
return NULL;
if (current->next && current->next->free) {
current->size += current->next->size + sizeof(block);
current->next->next->previous = current;
current->next = current->next->next;
if (current->previous && current->previous->free) {
current->previous->size += current->size + sizeof(block);
current->next->previous = current->previous;
current->previous->next = current->next;
return current->previous;
return current;
* @brief The free function frees the memory space pointed to by the parameter
* which must have been returned by a previous call to malloc().
* Otherwise, or if free has already been called on the pointer before,
* undefined behavior occurs. If the pointer is NULL, no operation is performed.
* @param ptr The pointer to the space that we want to free
void _free(void *ptr) {
if (!ptr)
block* block_ptr = ptr - sizeof(block);
// Merge the blocks around the current current block
block_ptr->free = true;
block_ptr = merge(block_ptr);
if (block_ptr == NULL)
// If the only block that is left is the first block
if (block_ptr->previous == NULL && block_ptr->next == NULL) {
sbrk (- (block_ptr->size + sizeof(block) ));
global_head = NULL;
// Check if the given block is the last block in the list
if (block_ptr->next == NULL) {
block_ptr->previous->next = NULL;
sbrk (- (block_ptr->size + sizeof(block) ));
void show_heap() {
block *current = global_head;
while (current) {
printf("Free:%d Size:%d Current:%p Next:%p Prev:%p\n", current->free, current->size, current, current->next, current->previous);
if(current->next != NULL)
current = current->next;
int main(int argc, char *argv[]) {
struct test{
int a;
char b;
unsigned int x;
} *structure = _malloc(5 * sizeof(struct test));
int *a = _malloc(10 * sizeof(int));
int *b = _malloc(10 * sizeof(int));
int *c = _malloc(10 * sizeof(int));
int *d = _malloc(10 * sizeof(int));
printf("%d %d %d %d\n\n", a[0], b[0], c[0], d[0]);
structure[3].a = 5;
structure[3].b = 'c';
printf("%d %c\n", structure[3].a, structure[3].b);
int *f = _malloc(30 * sizeof(char));
int *e = _malloc(100 * sizeof(char));
printf("%c %c %p\n", e[0], f[0], &a[11]);
#include "kernel/types.h"
#include "user/user.h"
#define false 0
#define true 1
#define NULL (void*) 0
typedef struct block{
int size; // Will be the size of the block
int free; // Will tell if the block is fried or not
struct block *next; // Will point to the next block
struct block *previous; // Will point to the previoust block
} block;
void *_malloc(int size);
void _free(void *ptr);

My Malloc and Free

The next program is intended to simulate a malloc and a free in the XV6 Operating System. This program was written for a coursework from University.

How to use

In order to use the code you will have to git clone on your local machine. In the Makefile add the following code on line 130: $U/_memory_management\ . Then run make, make qemu. After the files have been compiled the terminal should display the next text: hart 2 starting hart 1 starting init: starting sh $ After this just type memory_management and the program will run. This should show some of the testing that has been done.


In the next files you can see a type of implementation of the malloc and free function that the C programming language uses. These functions will allocate memory in the heap of the program. The program will keep track of all of the blocks of memory using a linked list of structs presented in the memory_management.h.

How the program will work

  1. When allocation memory for the first time, the program will use the sbrk() to see where is the top of the heap and allocate memory there.
  2. If we already freed some memory and the block that we want to allocate can be placed in that free space, we can spit that freed space into two parts.

When trying to free the memory we will have three cases:

  1. If the memory is at the top of the heap, we will just move the top of the heap down by calling sbrk() with a negative value;
  2. If the memory has a neighboring free blocks the two/three blocks will be merged
  3. If none of the above cases happened, the block will just be considered free


The following code is only usable in a XV6 machine although the code is written in a simple type of C. To use the code on another machine, you should change the headers in the memory_management.h file to #include <stdio.h> but also to delete the #define NULL (void*) 0 line (in XV6 there is no definition of NULL). You can also change the exit (0); to return 0; on the last line of the main function but this will not change the way _malloc() and _free() will work;

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment