Untitled

#include "VirtualMemory.h"

#include <sys/types.h>

#include "PhysicalMemory.h"

void clearFrame(uint64_t base_address) {
    for (uint64_t i = 0; i < PAGE_SIZE; i++) {
        PMwrite(base_address * PAGE_SIZE + i, 0);
    }
}

bool is_valid_address(uint64_t virtualAddress) {
    return virtualAddress < VIRTUAL_MEMORY_SIZE;
}

uint64_t cyclic_distance(uint64_t page1, uint64_t page2) {
    return std::min(NUM_PAGES - std::abs(page1 - page2), std::abs(page1 - page2));
}

void dfs(uint64_t parent_address, word_t &max_frame, uint64_t &max_distance_frame, uint64_t current_distance, int level, uint64_t virtual_page, uint64_t protected_frame, uint64_t &empty_frame, bool &found_empty) {
    if (level == TABLES_DEPTH) {
        return;
    }

    for (uint64_t i = 0; i < PAGE_SIZE; i++) {
        word_t next_address;
        PMread(parent_address * PAGE_SIZE + i, &next_address);

        if (next_address != 0) {
            uint64_t new_distance = cyclic_distance(next_address, virtual_page);
            if (new_distance > current_distance) {
                current_distance = new_distance;
                max_distance_frame = next_address;
            }

            if (next_address > max_frame) {
                max_frame = next_address;
            }

            dfs(next_address, max_frame, max_distance_frame, current_distance, level + 1, virtual_page, protected_frame, empty_frame, found_empty);
        } else if (!found_empty && next_address != protected_frame) {
            empty_frame = parent_address * PAGE_SIZE + i;
            found_empty = true;
        }
    }
}

uint64_t find_unused_frame(uint64_t virtual_page, uint64_t protected_frame) {
    word_t max_frame = 0;
    uint64_t max_distance_frame = 0;
    uint64_t empty_frame = 0;
    bool found_empty = false;

    dfs(0, max_frame, max_distance_frame, 0, 0, virtual_page, protected_frame, empty_frame, found_empty);

    if (found_empty) {
        PMwrite(empty_frame, 0);
        return empty_frame;
    }

    if (max_frame + 1 < NUM_FRAMES) {
        return max_frame + 1;
    }

    PMevict(max_distance_frame, virtual_page);
    return max_distance_frame;
}

uint64_t handle_page_fault(int level, uint64_t &cur_address, uint64_t &fault_address, uint64_t protected_frame, uint64_t virtual_address) {
    uint64_t new_frame = find_unused_frame(virtual_address / PAGE_SIZE, protected_frame);

    if (level < TABLES_DEPTH - 1) {
        clearFrame(new_frame);
    } else {
        PMrestore(new_frame, virtual_address / PAGE_SIZE);
    }

    PMwrite(fault_address, new_frame);
    return new_frame;
}

void VMinitialize() {
    clearFrame(0);
}

uint64_t translate_address(uint64_t virtualAddress) {
    uint64_t cur_address = 0;
    for (word_t level = 0; level < TABLES_DEPTH; level++) {
        uint64_t trans_level = (virtualAddress >> ((TABLES_DEPTH - level - 1) * OFFSET_WIDTH)) & (PAGE_SIZE - 1);
        word_t next_address;
        PMread(cur_address * PAGE_SIZE + trans_level, &next_address);

        if (next_address == 0) {
            uint64_t base_address = cur_address * PAGE_SIZE + trans_level;
            next_address = handle_page_fault(level, cur_address, base_address, cur_address, virtualAddress);
        }
        cur_address = next_address;
    }

    return cur_address * PAGE_SIZE + (virtualAddress % PAGE_SIZE);
}

int VMread(uint64_t virtualAddress, word_t *value) {
    if (!is_valid_address(virtualAddress)) {
        return 0;
    }
    uint64_t address = translate_address(virtualAddress);
    PMread(address, value);
    return 1;
}

int VMwrite(uint64_t virtualAddress, word_t value) {
    if (!is_valid_address(virtualAddress)) {
        return 0;
    }
    uint64_t address = translate_address(virtualAddress);
    PMwrite(address, value);
    return 1;
}