/*
 * 管理共享内存的分配与释放
 */
#include "mm.h"
#include "sem_util.h"
#include "hashtable.h"
#include "key_def.h"
#include "logger_factory.h"
#include "bh_api.h"
#include <sys/sem.h>
#include <sys/shm.h>


/* $begin mallocmacros */
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 16

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size_t)(size) + (ALIGNMENT-1)) & ~(ALIGNMENT - 1))

/* Returns true if p is ALIGNMENT-byte aligned */
#define IS_ALIGNED(p)  ((((size_t)(p)) & (ALIGNMENT - 1)) == 0)

/*
 * If NEXT_FIT defined use next fit search, else use first-fit search
 */
//#define NEXT_FITx

/* Basic constants and macros */
#define SIZE_T_SIZE (sizeof(size_t))

#define PTR_SIZE (sizeof(char *))

#define MIN_BLOCK_SIZE (ALIGN( (SIZE_T_SIZE << 1) + SIZE_T_SIZE + (PTR_SIZE << 1) ))


//#define MAX(x, y) ((x) > (y)? (x) : (y))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc)  ((size) | (alloc)) //line:vm:mm:pack

/* Read and write a word at address p */
#define GET(p)       (*(size_t *)(p))
#define PUT(p, val)  (*(size_t *)(p) = (val))
#define GET_PTR(p)       (*(char **)(p))
#define PUT_PTR(p, val)  (*(char **)(p) = (char*)(val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~(ALIGNMENT-1))                   //line:vm:mm:getsize
#define GET_ALLOC(p) (GET(p) & 0x1)                    //line:vm:mm:getalloc

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)       ((char *)(bp) - SIZE_T_SIZE)                      //line:vm:mm:hdrp
#define FTRP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)) - 2 * SIZE_T_SIZE) //line:vm:mm:ftrp
#define SUCCRP(bp)       ((char **)(bp) + 1)                      //line:vm:mm:hdrp
#define PREDRP(bp)       ((char **)(bp))                      //line:vm:mm:hdrp
//#define FIRSTER(heap_listp)       ((char **)(heap_listp))
//#define LASTER(heap_listp)       ((char **)(heap_listp) + 1)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - SIZE_T_SIZE))) //line:vm:mm:nextblkp
#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - 2 * SIZE_T_SIZE))) //line:vm:mm:prevblkp
#define NEXT_FBLKP(bp) (*SUCCRP(bp))
#define PREV_FBLKP(bp) (*PREDRP(bp))

/* $end mallocmacros */

// #define MAX_HEAP (512*(1<<20))  /* 20 MB */
#define MAX_HEAP (512)  /* 20 MB */
/* Hard-coded keys for IPC objects */
#define SHM_KEY 0x1234          /* Key for shared memory segment */
#define SHM_MUTEX_KEY 0x8800
#define OBJ_PERMS (S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP)


/* Global variables */
static void *key_addr = (void *)0x400d0000;
static void * heap_listp = 0;  /* Pointer to first block */

/* Function prototypes for internal helper routines */
static void * extend_heap(size_t words);
static void *place(void *bp, size_t size);
static void *find_fit(size_t size);
static void *coalesce(void *bp);
static inline void rm_fblock(void *bp);
static void insert_fblock (void *bp);

static void *mem_sbrk(int incr);
static int is_allocated(void *ptr);

static int shmid = -1;
static void *shmp;
static int mutex = SemUtil::get(SHM_MUTEX_KEY, 1);
//static int mutex = SemUtil::get(IPC_PRIVATE, 1);

static void *mem_start_brk;  /* points to first byte of heap */
static void *mem_brk;        /* points to last byte of heap */
static void *mem_max_addr;   /* largest legal heap address */
static size_t mem_max_size;



/*
 * mm_malloc - Allocate a block with at least size bytes of payload
 */
void *mm_malloc(size_t size)
{
  size_t newsize;      /* Adjusted block size */
  void *ptr, *aptr;

  /* Ignore spurious requests */
  if (size == 0)
    return NULL;

  newsize = ALIGN(size +  (SIZE_T_SIZE << 1) +  (PTR_SIZE << 1) );

  /* Search the free list for a fit */
  SemUtil::dec(mutex);
  if ((ptr = find_fit(newsize)) != NULL)
  {
    aptr = place(ptr, newsize);
    SemUtil::inc(mutex);
    return aptr;
  } else {
    SemUtil::inc(mutex);
    err_msg(0, "mm_malloc : out of memery\n");
    LoggerFactory::getLogger()->fatal("mm_malloc : out of memery\n");
    // abort();
    exit(1);
    
    return NULL;
  }

}

/*
 * mm_free - Free a block
 */
void mm_free(void *ptr, int enable)
{
  if (ptr == 0) 
    return;

  if (check_mm_valid(ptr) == false)
    return;

  /*
   *if (!is_allocated(ptr) ) {
   *  printf("Free error: %p is not a allocated block\n", ptr);
   *  return;
   *}
   */

  if (enable == true) {
    SemUtil::dec_uni(mutex);
  }
  ptr -= SIZE_T_SIZE;
  size_t size = GET_SIZE(HDRP(ptr));
  PUT(HDRP(ptr), PACK(size, 0));
  PUT(FTRP(ptr), PACK(size, 0));
  *(size_t *)ptr = 0x00;
  coalesce(ptr);
  if (enable == true) {
    SemUtil::inc(mutex);
  }
}

/*
 * mm_realloc - Naive implementation of realloc
 */
void *mm_realloc(void *ptr, size_t size)
{
  size_t oldsize;
  void *newptr;

  /* If size == 0 then this is just free, and we return NULL. */
  if (size == 0)
  {
    mm_free(ptr);
    return 0;
  }

  /* If oldptr is NULL, then this is just malloc. */
  if (ptr == NULL)
  {
    return mm_malloc(size);
  }

  /*if (!is_allocated(ptr) ) {*/
  /*printf("realloc error: %p is not a allocated block\n", ptr);*/
  /*return 0;*/
  /*}*/

  newptr = mm_malloc(size);

  /* If realloc() fails the original block is left untouched  */
  if (!newptr)
  {
    return 0;
  }

  /* Copy the old data. */
  oldsize = GET_SIZE(HDRP(ptr));
  if (size < oldsize) oldsize = size;
  memcpy(newptr, ptr, oldsize);

  /* Free the old block. */
  mm_free(ptr);

  return newptr;
}
/*
 * The remaining routines are internal helper routines
 */

void *mem_sbrk(int incr)
{
  void *old_brk = mem_brk;

  if ( (incr < 0) || (((char *)mem_brk + incr) > (char*)mem_max_addr))
  {
    errno = ENOMEM;
    fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
    return (void *) - 1;
  }
  mem_brk =(void*)((char *)mem_brk + incr);
  return (void *)old_brk;
}

// void *get_mm_start_brk() {
//   return mem_start_brk;
// }

// size_t get_mm_max_size() {
//   return mem_max_size;
// }

static hashtable_t *hashtable = NULL;

/*
 * mm_init - Initialize the memory manager, M unit
 * @return 是否第一次创建
 */
bool mm_init(size_t heap_size)
{
  
  //同一进程内已经初始化过了
  SemUtil::dec_uni(mutex);
  if (shmid != -1){
    hashtable = (hashtable_t *)shmp;
    SemUtil::inc(mutex);
    return false;
  }

  bool first = true;
  int offset = sizeof(hashtable_t);
  if(heap_size <= 0) {
    heap_size = MAX_HEAP;
  }
  heap_size = (heap_size*(1<<20));

  shmid = shmget(SHM_KEY, heap_size, IPC_CREAT | IPC_EXCL | OBJ_PERMS);
  if (shmid == -1 && errno == EEXIST) {
    first = false;
    shmid  = shmget(SHM_KEY, 0, 0);
  }

  if (shmid == -1)
    err_exit(errno, "mm_init shmget");
  shmp = shmat(shmid, key_addr, 0);
  if ((long)shmp == -1)
    err_exit(errno, "mm_init shmat");

  mem_start_brk = (void*)ALIGN((size_t)((char *)shmp + offset + ALIGNMENT));
  mem_max_addr = (void *)((char *)shmp+ heap_size);
  mem_max_size = (char *)mem_max_addr - (char*)mem_start_brk;
  mem_brk = mem_start_brk;
  void *free_listp;
  /* Create the initial empty heap */
  int initsize = ALIGN(3 * SIZE_T_SIZE + 2 * PTR_SIZE);
  heap_listp = (char *)mem_start_brk + initsize - 2 * SIZE_T_SIZE - 2 * PTR_SIZE;

  if(!first) {
    //其他进程已经创建过了共享内存
    hashtable = (hashtable_t *)shmp;
    SemUtil::inc(mutex);
    return first;
  }

 
  if ((mem_sbrk(initsize)) == (void *) - 1)
    err_exit(errno, "mm_init mem_sbrk");
  
  PUT((char *)mem_start_brk + initsize - SIZE_T_SIZE, PACK(0, 1));   /* Epilogue header */
  /*PUT(HDRP(heap_listp), PACK(initsize - SIZE_T_SIZE, 1));
  PUT(FTRP(heap_listp), PACK(initsize - SIZE_T_SIZE, 1));*/

  PUT(HDRP(heap_listp), PACK(initsize - SIZE_T_SIZE, 1));
  PUT(FTRP(heap_listp), PACK(initsize - SIZE_T_SIZE, 1));
  
  /**
   * here the heap_listp can be look as a ancher which concat the header and tail of free-list to form a ring, and the heap_list itself will never be used as a free block
  */
  PUT_PTR(SUCCRP(heap_listp), heap_listp);
  PUT_PTR(PREDRP(heap_listp), heap_listp);
  /* Extend the empty heap with a free block of CHUNKSIZE bytes */
  if ((free_listp = extend_heap(mem_max_size - initsize - ALIGNMENT)) == NULL)
    err_exit(errno, "mm_init extend_heap");

  hashtable = (hashtable_t *)shmp;
  hashtable_init(hashtable);
  SemUtil::inc(mutex);
  return first;
}

/**
 * @return 是否真正销毁成功
 */
bool mm_destroy(void) {
  struct shmid_ds shmid_ds;
  
  SemUtil::dec_uni(mutex);
  
  if(shmctl(shmid, IPC_STAT, &shmid_ds) == 0) {
    //LoggerFactory::getLogger()->debug("shm_nattch=%d\n", shmid_ds.shm_nattch);
    // 多个进程attach在共享内存上
    if (shmid_ds.shm_nattch > 1) {
      //detache
      if (shmdt(shmp) == -1) {
        LoggerFactory::getLogger()->error(errno, "mm_destroy shmdt");
      }
      SemUtil::inc(mutex);
      return false;
    } else  {
      // 只有当前一个进程attach到共享内存上
      hashtable_destroy(hashtable);
      //detache
      if (shmdt(shmp) == -1) {
        LoggerFactory::getLogger()->error(errno, "mm_destroy shmdt");
        SemUtil::inc(mutex);
        return false;
      }

      //remove shared memery
      if (shmctl(shmid, IPC_RMID, 0) == -1)
        err_exit(errno, "mm_destroy shmctl IPC_RMID");

      SemUtil::inc(mutex);
      SemUtil::remove(mutex);
      return true;

    } 
    
  } else {
    err_msg(errno, "mm_destroy shmctl IPC_STAT");
    SemUtil::inc(mutex);
    return false;
  }
}

hashtable_t * mm_get_hashtable() {
  return hashtable;
}

void * mm_get_by_key(int key) {
  return hashtable_get(hashtable, key);
}

void mm_free_by_key(int key) {
  void *ptr;

  ptr = hashtable_get(hashtable, key);
  if(ptr != NULL) {
    mm_free(ptr);
    hashtable_remove(hashtable, key);
  }
}


int mm_alloc_key() {
  return hashtable_alloc_key(hashtable);
}

/*
 * extend_heap - Extend heap with free block and return its block pointer
 */
/* $begin mmextendheap */
static void *extend_heap(size_t size)
{
  void *bp;
  size = ALIGN(size);

  if ((long)(bp = mem_sbrk(size)) == -1)
    return NULL;                                        //line:vm:mm:endextend

  /* Initialize free block header/footer and the epilogue header */
  PUT(HDRP(bp), PACK(size, 0));         /* Free block header */   //line:vm:mm:freeblockhdr
  PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */   //line:vm:mm:freeblockftr
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */ //line:vm:mm:newepihdr
  
  /* Coalesce if the previous block was free */
  return coalesce(bp);                                          //line:vm:mm:returnblock
}

static void insert_fblock (void *bp)
{
  // insert into the header of the free list
  PUT_PTR(SUCCRP(bp), NEXT_FBLKP(heap_listp)); //the successor of bp point to the old first free block
  PUT_PTR(PREDRP(NEXT_FBLKP(heap_listp)), bp); //the predecessor of the old first free block point to bp
  PUT_PTR(SUCCRP(heap_listp), bp); // successor of the ancher(锚点) point to bp
  PUT_PTR(PREDRP(bp), heap_listp); //the predecessor of bp point to heap_listp

}
/**
 * remove a block form free list
 */
static inline void rm_fblock(void *rbp)
{
  // the successor of the previous block of rbp point to next block of rbp

  PUT_PTR(SUCCRP(PREV_FBLKP(rbp)), NEXT_FBLKP(rbp));
  // the predecessor of then next block of rbp point to previous block of rbp
  PUT_PTR(PREDRP(NEXT_FBLKP(rbp)), PREV_FBLKP(rbp));
}
/*
 * coalesce - Boundary tag coalescing. Return ptr to coalesced block
 */
static void *coalesce(void *bp)
{
  void *nbp = NEXT_BLKP(bp);
  void *pbp = PREV_BLKP(bp);
  size_t prev_alloc = GET_ALLOC(FTRP(pbp));
  size_t next_alloc = GET_ALLOC(HDRP(nbp));
  size_t size = GET_SIZE(HDRP(bp));


  if (prev_alloc && next_alloc)              /* Case 1 */
  {
    insert_fblock(bp);
    return bp;
  }

  else if (prev_alloc && !next_alloc)        /* Case 2 */
  {
    size += GET_SIZE(HDRP(nbp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));

    rm_fblock(nbp);
    insert_fblock(bp);
  }

  else if (!prev_alloc && next_alloc)        /* Case 3 */
  {
    size += GET_SIZE(HDRP(pbp));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(pbp), PACK(size, 0));
    bp = pbp;
  }

  else                                       /* Case 4 */
  {
    nbp = nbp;
    size += GET_SIZE(HDRP(pbp)) + GET_SIZE(FTRP(nbp));
    PUT(HDRP(pbp), PACK(size, 0));
    PUT(FTRP(nbp), PACK(size, 0));
    bp = pbp;
    rm_fblock(nbp);
  }

  return bp;
}

/*
 * place - Place block of size bytes at start of free block bp
 *         and split if remainder would be at least minimum block size
 */
static void * place(void *bp, size_t size)
{
  size_t csize = GET_SIZE(HDRP(bp));

  if ((csize - size) >= MIN_BLOCK_SIZE)
  {
    //free list keep no change
    PUT(HDRP(bp), PACK(csize - size, 0));
    PUT(FTRP(bp), PACK(csize - size, 0));
    bp = NEXT_BLKP(bp);
    PUT(HDRP(bp), PACK(size, 1));
    PUT(FTRP(bp), PACK(size, 1));
  }
  else
  {
    // mark allocateed
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
    rm_fblock(bp);
  }

  *(size_t *)bp = inter_key_get();

  return (bp + SIZE_T_SIZE);
}

static int is_allocated(void *ptr)
{
  if (ptr == NULL)
    return 0;
  int is_alloced = 0;
  void *bp;
  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
  {
    if ((ptr == bp) && GET_ALLOC(HDRP(bp)) )
    {
      is_alloced = 1;
      break;
    }
  }
  if (!is_alloced)
  {
    return 0;
  }
  return 1;

}

void find_mm_data(int val)
{
  void *bp = heap_listp;

  unsigned int diff;
  struct timeval start, end;

  gettimeofday(&start, NULL);
  SemUtil::dec(mutex);
  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
  {
    if (GET_ALLOC(HDRP(bp))) {
      if ((*(size_t *)bp) == val) {
        mm_free(bp + SIZE_T_SIZE, false);
      }
    }

    gettimeofday(&end, NULL);

    diff = end.tv_sec - start.tv_sec;
    if (diff >= TIME_DUR)
      break;
  }
  SemUtil::inc(mutex);

  return;
}

int check_mm_valid(void *bp)
{
  int val;

  if ((bp >= mem_start_brk) && (bp <= mem_max_addr) && (GET_ALLOC(HDRP(bp - SIZE_T_SIZE)))) {

    val = *(size_t *)(bp - SIZE_T_SIZE);
    if ((val >= START_KEY) || (val == SHM_BUS_KEY)) {
      return true;
    }

    return false;
  }

  return false;
}

/*
 * find_fit - Find a fit for a block with size bytes
 */
static void *find_fit(size_t size)
{
  void *bp;
  unsigned int diff;
  struct timeval start, end;

  gettimeofday(&start, NULL);  
  for (bp = NEXT_FBLKP(heap_listp); bp != heap_listp; bp = NEXT_FBLKP(bp))
  {
    if (!GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp))))
    {
      return bp;
    } else if (GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) == 0)) 
    {
      break;
    }

    gettimeofday(&end, NULL);
    
    diff = end.tv_sec - start.tv_sec;
    if (diff >= TIME_DUR)
      break;
  }
  
  return NULL; /* No fit */
}

// =============================check heap========================
static void printblock(void *bp)
{
  size_t hsize, halloc, fsize, falloc;

  hsize = GET_SIZE(HDRP(bp));
  halloc = GET_ALLOC(HDRP(bp));
  fsize = GET_SIZE(FTRP(bp));
  falloc = GET_ALLOC(FTRP(bp));

  if (hsize == 0)
  {
    printf("%p: EOL\n", bp);
    return;
  }

  printf("%p: header: [%lx:%c] footer: [%lx:%c]\n",
         bp, hsize, (halloc ? 'a' : 'f'), fsize, (falloc ? 'a' : 'f'));
}

static int checkblock(void *bp)
{
  if (!IS_ALIGNED(bp))
  {
    printf("Error: %p is not doubleword aligned\n", bp);
    return 0;
  }
  if (GET(HDRP(bp)) != GET(FTRP(bp)))
  {
    printf("Error: header does not match footer\n");
    return 0;
  }
  return 1;
}

static int checkblocklist(int verbose)
{
  int valid = 1;
  void *bp = heap_listp;

  if (verbose > 1)
    printf("Heap (%p):\n", heap_listp);

  /*if ((GET_SIZE(HDRP(heap_listp)) != 2 * SIZE_T_SIZE) || !GET_ALLOC(HDRP(heap_listp)))*/
  /*printf("Bad prologue header\n");*/

  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
  {
    if (verbose > 1)
      printblock(bp);

    if (!checkblock(bp))
    {
      valid = 0;
    }
  }

  if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
  {
    printf("Bad epilogue header\n");
    valid = 0;
  }
  if (verbose > 1)
    printblock(bp);
  return valid;
}

void printfreeblock(void *bp)
{

}

void check_freelist()
{
  void *bp;

  for (bp = NEXT_FBLKP(heap_listp); bp != heap_listp; bp = NEXT_FBLKP(bp))
  {
    printfreeblock(bp);
  }

}
/*
 * mm_check - Minimal check of the heap for consistency
 */
int mm_checkheap(int verbose)
{
  return checkblocklist(verbose);
}