memory_management.c

#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
  sbrk(-size_of_movment);
  // Make the new block
  block *new_block    = (block*) sbrk(0);
  //Move the sbrk back to the top
  sbrk(size_of_movment);

  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)
    return;

  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)
    return;

  // 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;
    return;
  }

  // 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;
    else
      return;
  }
}

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]);

  _free(b);
  show_heap();
  
  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]);

  show_heap();

  exit(0);
}

memory_management.h

#ifndef MEM_MANAGER
#define MEM_MANAGER

#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);

#endif

My malloc and free.md

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 https://github.com/mit-pdos/xv6-riscv 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.

Explanations

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

Disclaimer

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;