#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <sys/mman.h>
#include <time.h>
#include <pthread.h>
#include <numaif.h>

static inline uint64_t read_tscp(void) {
  uint64_t rax, rcx, rdx;
  asm volatile("rdtscp" : "=a" (rax), "=d" (rdx), "=c" (rcx));
  return rax | (rdx << 32);
}

/*
 *
 *    Latences :
 *    N = 16 (cache L1) :    ~ 4 cycles
 *    N = 256 (cache L2) :   ~ 15 cycles
 *    N = 2048 (cache L3) :  ~ 47 cycles
 *    N = 32768 (mémoire) :
 *      locale :             ~ 148 cycles 
 *      distante un saut:    ~ 264 cycles 
 *      distante deux sauts: ~ 365 cycles
 *
 */

#define NB_LOOPS        10

/*
 *  Cache line, just a structure of 64 bytes
 */
struct cache_line {
	uint64_t val[8];
};

/*
 *  Allocate n bytes
 */
struct cache_line* allocate(uint64_t n) {
	struct cache_line* buf = mmap(0, n, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, 0, 0);

  printf("allocate %lu byte\n", n);
	if(buf == MAP_FAILED) {
		perror("mmap");
		exit(1);
	}

	return buf;
}

/*
 *  Prepare the buffer to perform a randomized access
 */
void randomize(struct cache_line* buf, uint64_t n) {
	uint64_t c = 0, r;

	srand(time(NULL));
	
	for(uint64_t i=0; i<(n-1); i++) {
		buf[c].val[0] = 1;

		do {
			r = rand() % n;
		} while(buf[r].val[0]);

		buf[c].val[0] = r;

		c = r;
	}

	buf[c].val[0] = 0;
}

void randomize_other_soluce(struct cache_line* buf, uint64_t n) {
  uint64_t elements[n-1];

  for(uint64_t i=0; i<(n-1); i++)
    elements[i] = i + 1;
  
  uint64_t cur = 0;
  for(uint64_t i=n-1; i>0; i--) {
    uint64_t k = rand() % i;
    buf[cur].val[0] = elements[k];
    elements[k] = elements[i-1];
    cur = buf[cur].val[0];
  }

  buf[cur].val[0] = 0;
}

/*
 *  Access all the nbc cache lines of the buffer buf
 */
uint64_t access(struct cache_line* buf, uint64_t nbc) {
	uint64_t r = 0;
	for(uint64_t i=0; i<nbc; i++) {
		r = buf[r].val[0];
	}
	return r;
}

/*
 *  Pine the current thread to the core core_id
 */
void pine_thread(int core_id) {
	cpu_set_t cpuset;

	CPU_ZERO(&cpuset);
	CPU_SET(core_id, &cpuset);

	if(pthread_setaffinity_np(pthread_self(), sizeof(cpu_set_t), &cpuset) == -1) {
		perror("pthread_setaffinity_np");
		exit(1);
	}
}

/*
 *  Bind the nbc cache lines of the buffer the numa domain node_id
 */
void bind_memory(struct cache_line* buf, uint64_t nbc, uint32_t node_id) {
	uint64_t nodemask = (1 << node_id);

	if(mbind(buf, nbc*sizeof(struct cache_line),  MPOL_BIND, &nodemask, 64, MPOL_MF_MOVE) == -1) {
		perror("mbind");
		exit(1);
	}
}

int main(int argc, char** argv) {
	if(argc != 4) {
		fprintf(stderr, "Usage: %s k p n\n", argv[0]);
		fprintf(stderr, "    k: number of KiB in the buffer\n");
		fprintf(stderr, "    p: processor number of the thread\n");
		fprintf(stderr, "    n: numa node of the memory\n");
		return 1;
	}

	uint64_t nbb = atol(argv[1]) * 1024L;    /* number of bytes to allocate */
	uint64_t core_id = atol(argv[2]);        /* core id on which we pine the thread */
	uint64_t numa_id = atol(argv[3]);        /* numa domain on which we bind the memory */
	struct cache_line* buf = allocate(nbb);  /* allocate the buffer of nbb bytes */
	uint64_t nbc = nbb/sizeof(struct cache_line);      /* compute the number of cache lines */
	uint64_t r = 0;                          /* just a number, see TP */

	pine_thread(core_id);                    /* pine the thread */
	bind_memory(buf, nbc, numa_id);          /* bind the memory */
	randomize(buf, nbc);                     /* randomize the access to buffer */

	r = access(buf, nbc);                    /* access the buffer */

	uint64_t start = read_tscp();    /* start of experiment */

	for(uint64_t i=0; i<NB_LOOPS; i++) {     /* perform NB_LOOPS */
		r += access(buf, nbc);                 /*   full access the buffer */
	}

	uint64_t end = read_tscp();      /* end of experiment */

	printf("%lu cycles to access a cache line (total: %lu cycles)\n", (end - start)/(NB_LOOPS*nbc), end - start);

	return r;
}