================================================================================
PART 1: PROJECT OVERVIEW
================================================================================

This project successfully implements a robust, fault-tolerant dynamic memory allocator for a theoretical Mars rover.
Which is able to allocate/free/quarantine memory blocks, and then read/write data to these block payloads.
The runme.c test environment then simulates survival of the memory allocator when corrupted.

The solution meets the following requirements to survive the harsh environment on Mars:

1.  **Resilient Memory Structure**:
    - Custom `mm_malloc`/`mm_free` functions allocate and free memory blocks (header, payload, footer) on a single contiguous block of memory provided by the OS.
    - An implicit free list structure is used to link these memory blocks together, with immediate coalescing to minimize fragmentation.
    - 40-byte alignment is enforced for all payloads, ensuring compatibility with hardware requirements.

2.  **Corruption Detection**:
    - **Metadata Checksum**: Each block's metadata is protected from corruption by an XOR-based checksum.
    - **Payload Checksum**: Each block's payload is protected from corruption by an XOR-based checksum.
    - **Redundancy**: Critical metadata fields like `size` are mirrored (`size_mirror`) to double-check integrity.
    - **Magic Numbers**: A signature `0xCAFEBABE` is used to validate block headers and footers.
    - **Corruption Recovery**: When a corrupt block is enounterered, the allocator skips 40 byte increments, and isolates the damaged region instead of crashing.
    - **Header/Footer Matching**: Ensures that the header and footer of a block are consistent with each other.
    - **Alignment Enforcement**: Strictly checks that all block addresses are 40-byte aligned, catching pointer corruption.

3.  **Further Security**:
    - **Bounds Checking**: Extensive checks ensure pointers refer to blocks within the valid heap range.
    - **Authorized Access**: `mm_read` and `mm_write` functions access memory safely, verifying block integrity and preventing out-of-bounds access or writes to free blocks.
    - **Double-Free Detection**: Prevents freeing an already free block, preserving the integrity of the free list.
    - **Pattern Management**: A specified 5-byte pattern is used to indicate "unused memory" in free memory blocks.

4.  **Operational Scenarios**:
    - Sucessfully operates under "Clear Skies" (normal operation) efficiently.
    - Sucessfully operates under "Radiation Storms" by detecting and rejecting corrupted blocks.
    - Sucessfully operates under "Brownout" inconsistencies via payload checksums and logical size tracking.

5.  **Submission Output**:
    - Successfully compiles into a shared library (`liballocator.so`) and test environment (`runme`) using the Makefile.

================================================================================
PART 2: CODE FUNCTIONALITY BREAKDOWN
================================================================================
--------------------------------------------------------------------------------
1. allocator.h
--------------------------------------------------------------------------------
This header file contains the list of available functions (API), so other programs (like `runme.c`) can use the allocator.

-   **mm_init**: Initializes the heap. Must be called before any other function.
-   **mm_malloc**: Used to allocate a memory block aligned to 40 bytes, before read/write is possible.
-   **mm_read / mm_write**: Safe access functions that verify that also verify the block is not corrupt.
-   **mm_free**: Frees a block and merges it with adjacent free blocks.
-   **mm_realloc**: Resizes an existing block.
-   **mm_heap_stats**: Prints the state of the heap for debugging.

--------------------------------------------------------------------------------
2. allocator.c
--------------------------------------------------------------------------------
This is the core implementation file.

**A. Block Structure**
-   ALIGNMENT: Defined as 40 bytes.
-   MAGIC: A constant `0xCAFEBABE` used to identify valid headers/footers.
-   BlockHeader and BlockFooter:
    -   `size`: The total size of the payload.
    -   `size_mirror`: A copy of `size` to detect bit-flips in the size field.
    -   `magic`: Must match `0xCAFEBABE`.
    -   `flags`: 1 for allocated, 0 for free.
    -   `checksum`: An XOR sum of the other fields. If any field changes (due to radiation), the checksum will no longer match.
    -   `payload_checksum`: A checksum of the actual user data. Used to detect if the data itself has been corrupted.
    -   `logical_size`: Tracks the exact size the user asked for (e.g., 100 bytes) vs the aligned size (e.g., 120 bytes).

**B. Helpers for Other Functions**
-   calculate_checksum: Computes the XOR sum of the metadata (header/footer).
-   calculate_payload_checksum: Computes the XOR sum of the payload.
-   detect_pattern: Scans the initial heap to find the provided 5-byte pattern (indicates "unused" memory).
-   create_header / create_footer: Populates the structs and calculates the initial checksums.
-   verify_block: The most critical all-round security function that checks:
    -   Is the pointer within heap bounds?
    -   Is it 40-byte aligned?
    -   Does the magic number match?
    -   Do `size` and `size_mirror` match?
    -   Do calculated checksums match their stored checksums?
    -   Does the header match the footer for a memory block?

**C. Available Functions (API)**
-   **mm_init**:
    -   This function is first used to receive and initalise the memory block from the OS.
    -   It initialises one large "free" block with 5 byte pattern payload that indicates "unused memory".
    -   This one large free block covers the entire heap (header, payload and footer).

-   **mm_malloc**:
    -   This function calculates the actual size needed for a requested block allocation (requested payload + alignment + metadata).
    -   The program then uses a First-Fit Algorithm, looping through all blocks from `heap_start` until a suitable free block is found.
    -   If a corrupted block is encountered where `verify_block` fails, it scans forward in 40 byte increments to find the next `MAGIC` number, rather than crashing.
    -   When a large enough free block is found, it is split into the allocated block and a smaller free block (if the remainder is large enough).
    -   The function then updates the payload and metadata checksums of the blocks that have been modified.

-   **mm_free**:
    -   This function is used to free a unrequired memory block, first checking the pointer to the block is valid.
    -   It then checks that the block has not been asked to be freed twice ie no double-free (`flags == 0`).
    -   To free the block, it fills the payload with the 5-byte pattern to mark it as "unused memory".
    -   The function then checks and merges neighbour blocks if they are also free, to reduce fragmentation.

-   **mm_read / mm_write**:
    -   These functions read/write data (eg stone weights) to payloads after memory blocks have been allocated.
    -   They first verify the block payload and metadata is uncorrupted before allowing read/write access.
    -   Clear Skies: Normal read/write access without corruption.
    -   Radiation Storms: The functions prevent data loss during "Radiation Storms" by first checking that the block is not corrupt.
    -   Brownouts: The functions are able to detect inconsistencies that might happen during power failures.
    -   'mm_write` makes sure to update the `payload_checksum` after writing, so future checks will pass.

-   **mm_realloc**:
    -   This function is used to resize an existing memory block.
    -   To make the block smaller, it shrinks the block in the same location.
    -   To make the block larger, it mallocs a new block in a different location.
    -   It copies the data from the old block to the new block, and then frees the old block.

--------------------------------------------------------------------------------
3. runme.c
--------------------------------------------------------------------------------
This is the file used to test and demonstrate the allocators functionality.

-   **Command Line Arguments**: parsed to set heap size, seed, and "storm" mode (sets up the structure).
-   **Initialisation**: Allocates a chunk of system memory to simulate the "Mars Rover Heap" and passes it to `mm_init`.
-   **Basic Test**: Allocates payloads p1 and p2, writes data to them, then reads it back.
-   **Brownout Test**: Allocates a 100 byte logical (120 byte physical) block, then tries to write 120 bytes to it. The allocator's `mm_write` should reject this because it exceeds the *logical* size (100), even if it fits in the physical block. This proves the allocator tracks exact usage.
-   **Cleanup**: Frees memory and exits.

--------------------------------------------------------------------------------
4. Makefile
--------------------------------------------------------------------------------
Makefile compiles files to a shared library (`liballocator.so`) and test environment (`runme`)

-   `CFLAGS`: Flags for the compiler (Warnings, C99 standard, Position Independent Code for libraries).
-   `liballocator.so`: Compiles `allocator.c` into a shared library object.
-   `runme`: Compiles `runme.c` and links it against the `allocator.o` object.
-   `clean`: Removes generated files.
-   `test`: A shortcut to run the `runme` executable with default arguments.