/* EXERCISE 02 — REPAIRED.
 *
 * A map tile cache. Tiles arrive, are decoded into 32 KiB buffers, and are
 * evicted when the viewport moves. Eviction is interleaved: the tiles that
 * leave the viewport are scattered through the allocation order, not grouped
 * at the end of it.
 *
 * The repair: a tile is a whole number of pages with an independent lifetime,
 * so it does not belong on the general-purpose heap at all. Each tile gets its
 * own anonymous mapping, and munmap(2) returns those pages to the OS the
 * moment the tile is evicted — in any order, with no neighbours to strand.
 *
 * Build and run:
 *   clang -O2 -g -Wall -Wextra tilecache.c -o /tmp/tiles_fixed
 *   /tmp/tiles_fixed
 *
 * The decoded bytes and the checksum are unchanged. Only who owns the pages
 * is different. Every measurement is printed as key=value.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <malloc/malloc.h>
#include <mach/mach.h>
#include <sys/mman.h>

#define TILES      20000
#define TILE_BYTES (32 * 1024)
#define WATCHDOG_S 60

/* ------------------------------------------------------------------ safety */
/* A watchdog thread bounds this fixture even if it is run on a machine where
 * the allocation pattern behaves very differently. It reports through write(2)
 * and leaves through _exit(2) deliberately: a wedged process may hold a lock
 * that stdio or an atexit handler would need. */
static void *watchdog(void *unused) {
    (void)unused;
    sleep(WATCHDOG_S);
    const char m[] = "WATCHDOG: no progress within budget - forcing _exit(75).\n";
    ssize_t ignored = write(2, m, sizeof m - 1); (void)ignored;
    _exit(75);
}

/* --------------------------------------------------------------- footprint */
/* phys_footprint is the number macOS itself uses for per-process memory
 * limits. It is neither virtual size nor resident size. */
static double footprint_mb(void) {
    struct task_vm_info info;
    mach_msg_type_number_t count = TASK_VM_INFO_COUNT;
    if (task_info(mach_task_self(), TASK_VM_INFO,
                  (task_info_t)&info, &count) != KERN_SUCCESS) return -1.0;
    return info.phys_footprint / 1048576.0;
}

static char *tiles[TILES];

static unsigned long long checksum(void) {
    unsigned long long sum = 0;
    for (int i = 0; i < TILES; i++)
        if (tiles[i]) sum += (unsigned char)tiles[i][0];
    return sum;
}

int main(void) {
    pthread_t wd;
    pthread_create(&wd, NULL, watchdog, NULL);
    pthread_detach(wd);

    double base = footprint_mb();
    printf("phase=start footprintMB=%.1f\n", base);

    /* Fill the cache. Every tile is touched, so every page is real.
     * TILE_BYTES is a multiple of the page size, so one mapping per tile
     * wastes nothing to rounding. */
    for (int i = 0; i < TILES; i++) {
        tiles[i] = mmap(NULL, TILE_BYTES, PROT_READ | PROT_WRITE,
                        MAP_PRIVATE | MAP_ANON, -1, 0);
        if (tiles[i] == MAP_FAILED) { perror("mmap"); return 1; }
        memset(tiles[i], (i & 0x7f) + 1, TILE_BYTES);
    }
    double full = footprint_mb();
    unsigned long long sum = checksum();
    printf("phase=full footprintMB=%.1f requestedMB=%.1f\n",
           full, (double)TILES * TILE_BYTES / 1048576.0);

    /* Evict half the cache — interleaved, the way a moving viewport does it.
     * Every odd-indexed tile survives — which no longer matters, because a
     * tile's pages are not shared with its neighbours. */
    for (int i = 0; i < TILES; i += 2) { munmap(tiles[i], TILE_BYTES); tiles[i] = NULL; }
    double half = footprint_mb();
    printf("phase=evicted-half footprintMB=%.1f\n", half);

    /* Still asked, so the two runs print the same fields. With the tiles out
     * of the heap there is nothing here for it to reclaim. */
    size_t relieved = malloc_zone_pressure_relief(NULL, 0);
    double relief = footprint_mb();
    printf("phase=after-pressure-relief footprintMB=%.1f reliefBytes=%zu\n",
           relief, relieved);

    /* Free the rest. */
    for (int i = 1; i < TILES; i += 2) { munmap(tiles[i], TILE_BYTES); tiles[i] = NULL; }
    double empty = footprint_mb();
    printf("phase=empty footprintMB=%.1f\n", empty);

    double grewMB      = full  - base;
    double releasedMB  = full  - half;
    double retainedMB  = half  - base;

    printf("checksum=%llu\n", sum);
    printf("peakMB=%.1f\n", full);
    printf("grewMB=%.1f\n", grewMB);
    printf("releasedByHalfEvictionMB=%.1f\n", releasedMB);
    printf("stillHeldAfterHalfEvictionMB=%.1f\n", retainedMB);
    printf("finalMB=%.1f\n", empty);
    printf("recoveredFractionAtHalf=%.3f\n", grewMB > 0 ? releasedMB / grewMB : 0.0);
    return 0;
}