MemoryManager.cpp

#include "MemoryManager.h"
#include <fcntl.h>
#include <iostream>
#include <string>
#include <sys/mman.h>
#include <unistd.h>

using namespace std;

MemoryManager::MemoryManager(unsigned wordSize, std::function<int(int, void*)> allocator){
	this->wordSize = wordSize;
	this->allocatorFunc = allocator;
	this->memory_block = nullptr;
	this->head_ptr = nullptr;
	this->limitInWords =0;
}

MemoryManager::~MemoryManager(){ shutdown();}

void MemoryManager::cleanUpList(){
	BlockNode* temp = head_ptr;
	while (temp){
		BlockNode* nextNode = temp->next;
		delete temp;
		temp = nextNode;
	}
	head_ptr = nullptr;
}
void MemoryManager::initialize(size_t sizeInWords){
	if (sizeInWords > 65535 || sizeInWords == 0){
		return;
}
	if (memory_block != nullptr){
 		shutdown(); 
}

	limitInWords = sizeInWords;
	size_t totalBytes = sizeInWords *wordSize;
	// Request a private, anonymous block directly from the operating system.
	memory_block = static_cast<uint8_t*>(mmap(nullptr, totalBytes, PROT_READ | PROT_WRITE,
		MAP_PRIVATE | MAP_ANONYMOUS, -1, 0));

	if (memory_block == MAP_FAILED){
		memory_block = nullptr;
		return;
	}
	head_ptr = new BlockNode(0, static_cast<int>(sizeInWords), true);
}

void MemoryManager::shutdown(){
	if (memory_block != nullptr){
		munmap(memory_block, limitInWords * wordSize);
		memory_block = nullptr;
	}
	cleanUpList();
	limitInWords = 0;
}

void *MemoryManager::allocate(size_t sizeInBytes){
	if (memory_block == nullptr || sizeInBytes ==0) return nullptr;
	// Convert bytes to words, rounding up for alignment.
	int wordsNeeded = sizeInBytes / wordSize;
	if (sizeInBytes % wordSize != 0) { wordsNeeded++;}
	if (!allocatorFunc) return nullptr;

	void *listData = getList();
	int target_offset = allocatorFunc(wordsNeeded, listData);
	//clean up array
	uint16_t* listArray = (uint16_t*)listData;
	delete[] listArray;

	if (target_offset == -1){
	return nullptr;
	}


	BlockNode* curr = head_ptr;
	while (curr != nullptr)
	{
		// Find the free block selected by the active allocation strategy.
		if (curr->is_free && curr->start_offset == target_offset){
			if (curr->chunk_size > wordsNeeded){
				BlockNode* leftover = new BlockNode(curr->start_offset + wordsNeeded, curr->chunk_size - wordsNeeded, true);
			leftover->next = curr->next;
			leftover->prev = curr;
			// Keep both directions of the linked list connected.
                        if (curr->next != nullptr) {
                        	curr->next->prev = leftover;
                        }

                        curr->next = leftover;
                        curr->chunk_size = wordsNeeded;
                        }
                        curr->is_free = false;

					// memory_block is byte-addressable, while offsets are measured in words.
                        return (void*)(memory_block + (curr->start_offset * wordSize));
                }
                curr = curr->next;
        }

        return nullptr;
}

void MemoryManager::free(void *address){
	if (address == nullptr || memory_block == nullptr) return;

	uintptr_t base = reinterpret_cast<uintptr_t>(memory_block);
	uintptr_t target = reinterpret_cast<uintptr_t>(address);
	size_t memorySize = limitInWords * wordSize;
	if (target < base || target >= base + memorySize || (target - base) % wordSize != 0) {
		return;
	}

	int target_offset = static_cast<int>((target - base) / wordSize);

	BlockNode* temp = head_ptr;
	while (temp != nullptr){
		if (temp->start_offset == target_offset && !temp->is_free){
			temp->is_free = true;
			mergeBlocks(temp);
			return;
		}
		temp = temp->next;
	}
}

void MemoryManager::mergeBlocks(BlockNode* node){
	if (node == nullptr) return;
	// Merge with the previous hole first, then consume all adjacent holes.
	if (node->prev != nullptr && node->prev->is_free){
		node = node->prev;}
	while(node->next != nullptr && node->next->is_free){
		BlockNode* right = node ->next;
		node->chunk_size += right->chunk_size;

		node ->next = right-> next;
		if (right->next != nullptr){
			right->next->prev = node;
		}
		delete right;
	}
}

void MemoryManager::setAllocator(function<int(int, void *)> allocator){
	this->allocatorFunc=allocator;}
// Write the current hole map using POSIX file operations.
int MemoryManager::dumpMemoryMap(char *filename){
	int fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0666);
	if ( fd == -1) return -1;
	
	string mapStr = "";
	BlockNode* curr = head_ptr;
	bool firstHole = true;

	while (curr != nullptr){
		if (curr->is_free){
			if(!firstHole) mapStr += " - ";
			mapStr += "[" + to_string(curr->start_offset) + ", " + to_string(curr->chunk_size) + "]";
			firstHole = false;
		}
		curr = curr->next;
	}
	ssize_t bytesWritten = write(fd, mapStr.c_str(), mapStr.length());
	close(fd);

        if (bytesWritten == -1) return -1;
		return 0;
}

void *MemoryManager::getList(){
	if (memory_block == nullptr) return nullptr;
	//count how many holes we have first 
	int count = 0;
	BlockNode* temp = head_ptr;
	while (temp != nullptr){
		if (temp->is_free) count ++;
		temp = temp->next;
	}
	// Format: [hole count, offset 1, length 1, offset 2, length 2, ...]
	uint16_t* holeArray = new uint16_t[1 + (count *2)];
	holeArray[0] = (uint16_t)count;
	//second pass fills the array with the data
	int idx = 1;
        temp = head_ptr;
        while (temp != nullptr) {
                if (temp->is_free) {
                        holeArray[idx++] = (uint16_t)temp->start_offset;
                        holeArray[idx++] = (uint16_t)temp->chunk_size;
                }
                temp = temp->next;
        }
        return (void*)holeArray;
}

// A set bit represents an allocated word; a cleared bit represents a hole.
void *MemoryManager::getBitmap() {
	if (memory_block == nullptr) return nullptr;

	// Divide by eight and round up to hold any partial byte.
        int bytes_for_bits = (limitInWords + 7) / 8;
        
	// Two little-endian length bytes precede the bitstream.
        uint8_t* bitmap = new uint8_t[2 + bytes_for_bits];

		bitmap[0] = (uint8_t)(bytes_for_bits & 0xFF);
        bitmap[1] = (uint8_t)((bytes_for_bits >> 8) & 0xFF);

	// Initialize every word as free.
        for (int i = 0; i < bytes_for_bits; i++) {
                bitmap[i + 2] = 0;
        }
        BlockNode* curr = head_ptr;
        while (curr != nullptr) {
                if (!curr->is_free) {
                        for (int i = 0; i < curr->chunk_size; i++) {
                                int word_pos = curr->start_offset + i;
                                int byte_index = 2 + (word_pos / 8);
                                int bit_in_byte = word_pos % 8;
                                // Bitwise OR to flip the specific bit to 1
                                bitmap[byte_index] |= (1 << bit_in_byte);
                        }
                }
                curr = curr->next;
        }

        return (void*)bitmap;
}

unsigned MemoryManager::getWordSize(){
	return wordSize;}
void *MemoryManager::getMemoryStart(){
	return (void*)memory_block;}
unsigned MemoryManager::getMemoryLimit(){
	return limitInWords * wordSize;
}

int bestFit(int sizeInWords, void *list){
	if (list == nullptr) return -1;
	uint16_t* arr = (uint16_t*)list;
	int numHoles = arr[0];
	int best_offset = -1;
	int smallest_gap = 1000000;
	// Choose the fitting hole that leaves the least unused space.
        for (int i = 0; i < numHoles; i++) {
                int offset = arr[1 + (i * 2)];
                int length = arr[2 + (i * 2)];

                if (length >= sizeInWords) {
                        int gap = length - sizeInWords;
                        if (gap < smallest_gap) {
                                smallest_gap = gap;
                                best_offset = offset;
                        }
                }
        }
        return best_offset;
}
int worstFit(int sizeInWords, void *list) {
        if (list == nullptr) return -1;

        uint16_t* arr = (uint16_t*)list;
        int numHoles = arr[0];
        int worst_offset = -1;
        int largest_gap = -1;

	// Choose the largest available hole.
        int i = 0;
        while (i < numHoles) {
                int off = arr[1 + (i * 2)];
                int len = arr[2 + (i * 2)];

                if (len >= sizeInWords && len > largest_gap) {
                        largest_gap = len;
                        worst_offset = off;
                }
                i++;
        }
        return worst_offset;
}