#include <stdlib.h>
#include <sys/mman.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#define ACCESSES 100000000

size_t cyclelength(void *mem)
{
  size_t r=0;
  void *p=mem;
  do {
    r++;
    p = *(void **)p;
  } while (p!=mem);
  return r;
}

void init(void *mem, size_t elements, size_t stride, int randomize, int silent)
{
    size_t offsets[elements];
    size_t i;

    for (i=0; i<elements; i++) {
        offsets[i] = i;
    }
    if (!silent && elements>3)
        printf("size: %ld, offsets at 0x%lx 0x%lx 0x%lx 0x%lx ...%s\n",
               (elements-1)*stride+sizeof(void *),
               offsets[0]*stride,offsets[1]*stride,
               offsets[2]*stride,offsets[3]*stride,
               randomize?", randomized":"");
    if (randomize) {
      /* Sattolo's algorithm */
      for (i=elements-1; i>0; i--) {
        size_t j=random()%i;
        // printf("%ld,%ld\n",i,j);
        size_t tmp=offsets[i]; offsets[i]=offsets[j]; offsets[j]=tmp;
      }
      // for (i=0; i<elements; i++)
      //   printf("%ld->%ld\n",i,offsets[i]);
    } else {
      for (i=0; i<elements-1; i++)
        offsets[i] = offsets[i+1];
      offsets[elements-1] = 0;
    }
    for (i=0; i<elements; i++)
      *(void **)(mem+offsets[i]*stride)=(mem+i*stride);
    // printf("%ld\n",cyclelength(mem));
    // assert(cyclelength(mem)==elements);
}

void smallpages(void *mem, size_t size)
/* eliminate huge pages by making every other page read-only */
{
  size_t i;
  size_t pagesize = 4096;
  for (i=pagesize; i<size; i+=pagesize*2)
    mprotect(mem+i,pagesize,PROT_READ);
}

void **run(void *mem)
{
    size_t i;
    void **p = (void **)mem;
    for (i=0; i<ACCESSES; i++) {
        p = (void **)*p;
    }
    return p;
}

int main(int argc, char *argv[])
{
    size_t elements;
    size_t stride;
    size_t size;
    int randomize;
    int silent=0;
    void *mem;
    if (argc<4) {
    usage:
      fprintf(stderr,"Usage: %s linear|random <elements> <stride> [silent]\n",
              argv[0]);
        return 1;
    }
    if (strcmp(argv[1],"linear")==0)
        randomize = 0;
    else if (strcmp(argv[1],"random")==0)
        randomize = 1;
    else
        goto usage;
    elements = strtoul(argv[2], NULL, 10);
    if (elements<1)
        goto usage;
    if (elements>1000000) {
      fprintf(stderr,"use elements in [1,1000000]\n");
      goto usage;
    }
    stride = strtoul(argv[3], NULL, 10);
    if (stride<sizeof(void *)) {
      fprintf(stderr,"use stride>=%ld\n",sizeof(void *));
        goto usage;
    }
    if (argc>4 && strcmp(argv[4],"silent")==0)
        silent = 1;
    size = (elements-1)*stride+sizeof(void*);
    mem = mmap(NULL,size,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0);
    if (mem==MAP_FAILED) {
        perror("mmap failed");
        return 1;
    }
    init(mem,elements,stride,randomize,silent);
    smallpages(mem,size);
    if (run(mem)==(void **)mem) /* the result of run should not be dead */
        return 0;
    else
        /*should also be 0, but in a way that the compiler hopefully does not know it */
        return ACCESSES%elements;
}