Markov Chain BT Allocator

A small boundary tag (first-fit) memory allocator written in C++ with Markov Chains (implemented using the Eigen3 library) to defer coalescion when possible.

Idea: rather than traversing the entire heap to find the first-fit for a requested allocation size, a call to mbt_free will use a Markov Chain to predict the next allocation size and then potentially defer coalescion and cache/prepare the freed block to be allocated if the request matches the prediction. This will result in constant-time allocations in the ideal case.

To compile:

g++ *.cpp Allocator/*.cpp -std=c++20 -O0 -g -o main
./main

The declarations for mbt_alloc and mbt_free are:

void *mbt_alloc(int num_bytes); 
void mbt_free(uint8_t *ptr);

To test and call the allocator:

/*
 *   INCLUDE ALLOCATOR FILES 
 */

#include "Allocator/Alloc.h"
#include "Allocator/Free.h"


/*
 * CONFIG VARIABLES FOR ALLOCATOR AND SIMULATION
 */
uint8_t *heap_start = (uint8_t *)sbrk(0);
uint8_t *block = (uint8_t *)sbrk(65);
uint8_t *heap_end = (uint8_t *)sbrk(0);

uint8_t *cache_ptr = nullptr;
uint8_t cache_guess = 0;
uint8_t prev_guess = 0;
uint8_t prev_alloc = 0;

Markov markov;


int main() {
        initialize_heap(); 

        /* Insert calls to mbt_free() and mbt_alloc() */

        print_heap();
}