// vim: set sw=4 ts=4 sts=4 expandtab cindent:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/param.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <time.h>

#include <immintrin.h>

#define BUFFER_SIZE (1ULL<<30)
#define MMAP_FLAGS (MAP_ANONYMOUS|MAP_PRIVATE|MAP_POPULATE|MAP_HUGETLB|(30<<MAP_HUGE_SHIFT))
#define HUGETLBFS "/mnt/lab1/buff"
#define TASK_NOT_IMPLEMENTED -9

#define NSAMPLES (16 * 1024)
#define NROUNDS (48 * 1024)
#define CONFLICT_RATIO (1 / 64.0)

static inline uint64_t rdtscp()
{
    uint32_t eax, edx;
    __asm__ volatile("rdtscp" : "=a"(eax), "=d"(edx) :: "ecx");
    return ((uint64_t)edx << 32 | eax);
}

static inline void clflush(volatile void* p)
{
    __asm__ volatile("clflush (%0)" :: "r"(p));
}

int compare_ints(const void* a, const void* b)
{
    return *(const int*)a - *(const int*)b;
}

//-----------------------------------------------------------------
/*
*   Implement the timing in the following function.
*   (It makes it easier for us when grading and debugging)
*/
size_t time_accesses(volatile char* base, volatile char* probe, size_t rounds) {
    int* deltas = malloc(rounds * sizeof(int));

    for (int i = 0; i < rounds; ++i)
    {
        /* Make sure the data at probe is in the row buffer. */
        clflush(probe);
        *probe;

        clflush(probe);

        /* Then load the data at base into the row buffer, evicting
         * the data at probe if they are in the same bank but in a
         * different row */
        clflush(base);
        *base;

        // see how long it takes to access probe
        // if it takes long, base and probe share
        // a row buffer (so are in the same bank)
        uint64_t start = rdtscp();
        *probe;
        uint64_t end = rdtscp();

        deltas[i] = end - start;
    }

    /* Return the median access time. */
    qsort(deltas, rounds, sizeof(int), compare_ints);
    int val = deltas[rounds / 2];
    free(deltas);

    return val;
}

//-----------------------------------------------------------------
/*  TASK 1:
 *  You need to perform timing of the different memory accesses and
 *  export them to stdout. Please implement the timing in the
 *  time_accesses function above.
 * */
void export_times(char* buff) {
    srand(time(NULL));

    if (RAND_MAX < BUFFER_SIZE)
    {
        fprintf(stderr, "RAND_MAX too low!\n");
        exit(-1);
    }

    void* base = buff;

    for (int i = 0; i < NSAMPLES; ++i)
    {
        void* addr = buff + (rand() % BUFFER_SIZE);

        size_t time = time_accesses(base, addr, NROUNDS);
        fprintf(stdout, "%p,%p,%ld\n", base, addr, time);

        fprintf(stderr, "%d/%d\r", i, NSAMPLES);
    }
    fprintf(stderr, "\n");
}


//-----------------------------------------------------------------
/*  TASK 2:
 *  In this function you need to figure out the bank bits as explained
 *  in the manual.
 *  param: cutoff_val = cutoff value to distinguish between bank
 *  hit or conflict.
 * */
void find_bank_bits(char* buff, size_t cutoff_val) {
    char* base = buff;
    void* addr;

    uintptr_t bitmask = 0;

    srand(time(NULL));

    while (1)
    {
        addr = buff + (rand() % BUFFER_SIZE);
        size_t time = time_accesses(base, addr, NROUNDS);
        if (time > cutoff_val) break;
    }

    // at this point, addr is an address which conflicts with base.
    for (int i = 0; i < 30; ++i)
    {
        fprintf(stderr, "bit %d/30\r", i+1);
        void* modified_addr = (void*)((uintptr_t)addr ^ (1 << i));
        size_t time = time_accesses(base, modified_addr, NROUNDS);

        if (time < cutoff_val)
        {
            // it now no longer conflicts. therefore, the i'th bit
            // (partially) determines the bank.
            bitmask |= (1 << i);
        }
    }

    // export the bitmask of all the BANK bits in the following format:
    fprintf(stdout, "\n0x%lx\n",bitmask);
}

/* Returns the ratio of elements which are above the cutoff. */
float cutoff_ratio(int* times, int cutoff)
{
    // to avoid division by zero
    int above = 1, under = 1;

    for (int i = 0; i < NSAMPLES; ++i)
    {
        if (times[i] > cutoff)
            above++;
        else
            under++;
    }
    return ((float)above / (above + under));
}

//-----------------------------------------------------------------
/*  TASK 3:
 *  You can reuse the same code as the one for task 1 to collect
 *  measurements. On top of that after collecting the times you need
 *  to figure out a cutoff value to detect bank hits from bank
 *  conflicts.
 * */
size_t detect_cutoff(char* buff) {
    int* times = malloc(NSAMPLES * sizeof(int));

    srand(time(NULL));

    if (RAND_MAX < BUFFER_SIZE)
    {
        fprintf(stderr, "RAND_MAX too low!\n");
        exit(-1);
    }

    void* base = buff;

    for (int i = 0; i < NSAMPLES; ++i)
    {
        void* addr = buff + (rand() % BUFFER_SIZE);

        times[i] = time_accesses(base, addr, NROUNDS);
        fprintf(stderr, "%d/%d\r", i, NSAMPLES);
    }
    fprintf(stderr, "\n");

    int cutoff = 0;

    do
    {
        float r = cutoff_ratio(times, cutoff);
        if (r < CONFLICT_RATIO) break;
    } while (cutoff += 1);

    fprintf(stderr, "using cutoff: %d\n", cutoff);

    return cutoff;
}




//-----------------------------------------------------------------
/*
 * You should not touch the main function. Everything can be
 * implemented in the different functions stubs we provide.
 * */
int main(int argc, char** argv) {
	unsigned char* buff;
	int fd_hugepage;

    // allocating a 1GB hugepage
	fd_hugepage = open(HUGETLBFS, O_CREAT|O_RDWR);
	assert(fd_hugepage != -1);
	buff = (unsigned char*) mmap(NULL, BUFFER_SIZE, PROT_READ|PROT_WRITE, MMAP_FLAGS, fd_hugepage, 0 );
	assert(buff != (void*)-1);


#ifdef TASK_1
    export_times(buff);
#endif // TASK_1


#ifdef TASK_2
    // checking if we passed the cutoff value as argv[1] and extract it
    assert(argc == 2);
    size_t cutoff_val = strtoul(argv[1],NULL,10);
    fprintf(stderr, "cutoff_val: %ld\n", cutoff_val);

    find_bank_bits(buff, cutoff_val);
#endif // TASK_2


#ifdef TASK_3
    // automatically detect the cutoff val
    size_t cutoff_val = detect_cutoff(buff);
    assert(cutoff_val != TASK_NOT_IMPLEMENTED);

    // same as TASK_2
    find_bank_bits(buff, cutoff_val);
#endif // TASK_3



    assert (munmap(buff, BUFFER_SIZE) == 0);
    close(fd_hugepage);
    return 0;
}