Untitled

#include "VirtualMemory.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) {
    if ((virtualAddress >= VIRTUAL_MEMORY_SIZE) || (TABLES_DEPTH > NUM_FRAMES)) {
        return false;
    }
    return true;
}

void dfs(uint64_t parent_address, uint64_t base_address, int &max_frame, word_t &empty_frame, word_t &frame_to_evict) {
    for (uint64_t i = 0; i < PAGE_SIZE; i++) {
        word_t value;
        PMread(base_address + i, &value);
        if (value != 0) {
            max_frame = std::max(max_frame, static_cast<int>(value));
            dfs(base_address, value * PAGE_SIZE, max_frame, empty_frame, frame_to_evict);
        } else if (empty_frame == -1) {
            empty_frame = base_address / PAGE_SIZE;
        }
    }

    // If all entries in the frame are zero, it is an empty frame
    bool is_empty = true;
    for (uint64_t i = 0; i < PAGE_SIZE; i++) {
        word_t value;
        PMread(base_address + i, &value);
        if (value != 0) {
            is_empty = false;
            break;
        }
    }

    if (is_empty && empty_frame == -1) {
        empty_frame = base_address / PAGE_SIZE;
    }

    // Update the parent to point to zero
    if (empty_frame != -1 && parent_address != base_address) {
        uint64_t parent_index = base_address / PAGE_SIZE % PAGE_SIZE;
        PMwrite(parent_address + parent_index, 0);
    }

    // If no empty frame is found, choose the frame to evict
    if (empty_frame == -1 && frame_to_evict == -1) {
        frame_to_evict = base_address / PAGE_SIZE;
    }
}

uint64_t find_frame() {
    int max_frame = 0;
    word_t empty_frame = -1;
    word_t frame_to_evict = -1;

    dfs(0, 0, max_frame, empty_frame, frame_to_evict);

    if (empty_frame != -1) {
        return empty_frame;
    }

    if (frame_to_evict != -1) {
        clearFrame(frame_to_evict);
        return frame_to_evict;
    }

    return max_frame + 1;
}

uint64_t translate_address(uint64_t virtualAddress) {
    word_t cur_address = 0;

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

        if (next_address == 0) {
            uint64_t new_frame = find_frame();
            PMwrite(cur_address * PAGE_SIZE + trans_level, new_frame);
            clearFrame(new_frame);
            next_address = new_frame;
        }

        cur_address = next_address;
    }

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

/* reads a word from the given virtual address
 * and puts its content in *value.
 *
 * returns 1 on success.
 * returns 0 on failure (if the address cannot be mapped to a physical
 * address for any reason)
 */
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;
}

/* writes a word to the given virtual address
 *
 * returns 1 on success.
 * returns 0 on failure (if the address cannot be mapped to a physical
 * address for any reason)
 */
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;
}