#include <backend.h>
#include <limits.h>
#include "ti-gc.h"
#include "regions.h"

/* Page allocator for region-based memory management */
/* TBD: special free list for size == K ?? */
/* TBD: best maximum size for single page list ? (should it be
   nPROCS dependent ?) */

struct page
{
  /* Next page in region or in free list */
  struct page *next;

  /* Doubly linked list of pages sorted by address */
  struct page *next_address, *prev_address;

  PageId _flags;
  #define PAGE_PAGECOUNT(ppage)        ((ppage)->_flags >> 1)
  #define PAGE_ISFREE(ppage)           ((ppage)->_flags & 0x1)
  #define PAGE_SETPAGECOUNT(ppage,val) (((ppage)->_flags = (((val) << 1) | PAGE_ISFREE(ppage))), (void)0)
  #define PAGE_SETFREE(ppage,val)      (((ppage)->_flags = \
                                        (((ppage)->_flags & (~(PageId)1)) | ((val) & 0x1))), (void)0)

  /* Only in free pages not in the single_pages list */
  struct page *previous;
};

/* The pages are kept in a single list sorted by address via the
   next_address and prev_address fields. The first page's prev_address and
   the last page's next_address fields points to pages_byaddress.
   page_byaddress.next_address is the first page
   page_byaddress.prev_address is the last page

   This list is used for coalescing operations.
*/
static struct page pages_byaddress;

struct page *alloc_single_page(struct page *next);
void free_single_page(Region r, struct page *p);

struct page *alloc_pages(int n, struct page *next);
void free_pages(Region r, struct page *p);


/* a list of free individual pages */
static struct page *single_pages;
static int single_page_count;

/* all free pages */
static struct page *unused_pages;

static int nocoalesce;
static int page_alloc_count;
static int clobberfreed = -1;
static int leakfreed = -1;

static get_page_stats(jlong *pfreecount, jlong *punused) {
  struct page *p;
  jlong freecount = 0, unused = 0;
  assert(pfreecount && punused);

  for (p = pages_byaddress.next_address;
       p != &pages_byaddress; p = p->next_address)
    {
#if 0
      fprintf(stderr, "p %08x %d (%08x) %s\n",
	      p, PAGE_PAGECOUNT(p), (char *)p + (PAGE_PAGECOUNT(p) << RPAGELOG),
	      PAGE_ISFREE(p) ? "F" : "");
#endif
      if (PAGE_ISFREE(p))
	freecount += PAGE_PAGECOUNT(p);
    }
  for (p = unused_pages; p; p = p->next)
    unused += PAGE_PAGECOUNT(p);

  *pfreecount = freecount;
  *punused = unused;
}

void ti_get_region_stats(jlong *regionTotalHeapSize, jlong *regionHeapInUse) {
  if (regionTotalHeapSize) {
    *regionTotalHeapSize = ((jlong)page_alloc_count)*RPAGESIZE;
  }
  if (regionHeapInUse) {
    jlong freecount = 0, unused = 0;
    get_page_stats(&freecount, &unused); /* this op is expensive, so avoid when possible */
    *regionHeapInUse = ((jlong)(page_alloc_count - (unused+single_page_count)))*RPAGESIZE;
    /* DOB: freecount and unused count seem to reference the same pages? */
  }
}

/* modify buf, inserting commas in large numbers to enhance readability */
extern char *beautify_numbers(char *buf) {
  char *pos = buf;
  while ((pos = strpbrk(pos,"0123456789")) != NULL) {
    char num[255];
    char *end = pos + strspn(pos, "0123456789");
    int len = end-pos;
    int extras = 0;
    if (len > 3 && len < 100) {
      char *p = num+len;
      strncpy(num, pos, len);
      *p = '\0';
      while ((p -= 3) > num) {
        char tmp[255];
        strcpy(tmp, p);
        *p = ',';
        strcpy(p+1,tmp);
        extras++;
      }
      while (extras && ((pos > buf+1 && *(pos-1) == ' ' && *(pos-2) == ' ') ||
                        (pos == buf+1 && *(pos-1) == ' '))) { /* eat prior spaces */
        extras--;
        pos--;
      }
      if (extras) {
        int taillen = strlen(end);
        memmove(end+extras, end, taillen);
        end += extras;
        end[taillen] = '\0';
      }
      memcpy(pos, num, strlen(num));
    }
    pos = end;
    if (*pos == '.') { /* skip numbers after decimal pt */
      pos++;
      pos += strspn(pos, "0123456789");
    }
  }
  return buf;
}

void print_page_stats(char *header)
{
  jlong freecount = 0, unused = 0;
  char buf[1024];
  get_page_stats(&freecount, &unused);

  sprintf(buf,    "%s: Region pages total        %7lu (%llu bytes)\n"
                  "%s: Region single free pages  %7lu (%llu bytes)\n"
                  "%s: Region free pages         %7lu (%llu bytes)\n"
                  "%s: Region unused free pages  %7lu (%llu bytes)\n", 
  header, (unsigned long)page_alloc_count, ((unsigned long long)page_alloc_count)*RPAGESIZE,
  header, (unsigned long)single_page_count, ((unsigned long long)single_page_count)*RPAGESIZE,
  header, (unsigned long)freecount, ((unsigned long long)freecount)*RPAGESIZE,
  header, (unsigned long)unused, ((unsigned long long)unused)*RPAGESIZE);

  beautify_numbers(buf);
  fprintf(stderr, buf);
}

static void init_pages(void)
{
  const char *tmp;
  int quiet = !!getenvMaster("TI_BACKEND_SILENT") || MYBOX != 0;
  pages_byaddress.next_address = &pages_byaddress;
  pages_byaddress.prev_address = &pages_byaddress;

  nocoalesce = !!getenvMaster("TI_NOCOALESCE");
  if (nocoalesce && !quiet) printf("Warning: Disabling region coalescing, which can hurt region memory performance.\n");
  tmp = getenvMaster("TI_REGION_CLOBBER");
  if (tmp) clobberfreed = atoi(tmp);
  if (clobberfreed >= 0 && !quiet) 
     printf("Clobbering all freed space for deleted regions with 0x%02x\n", clobberfreed);
  leakfreed = !!getenvMaster("TI_REGION_LEAK");
  if (leakfreed && !quiet) 
     printf("Warning: Leaking all freed space for deleted regions, which can hurt region memory performance.\n");
  fflush(NULL);
}

static void insertbefore_address(struct page *p, struct page *before)
{
  p->prev_address = before->prev_address;
  p->next_address = before;
  before->prev_address = p;
  p->prev_address->next_address = p;
}

static void unlink_address(struct page *p)
{
  p->prev_address->next_address = p->next_address;
  p->next_address->prev_address = p->prev_address;
}

static void addbyaddress(struct page *p)
{
  struct page *address_scan, *last;

  /* Warning: this is slow. Calls to it should not be frequent (once app
     reaches a steady state of memory usage). */

  for (address_scan = pages_byaddress.next_address; ;
       address_scan = address_scan->next_address)
    if (p < address_scan || address_scan == &pages_byaddress)
      {
	insertbefore_address(p, address_scan);
	return;
      }
}

/* Doubly linked page list management */
void addfront(struct page **list, struct page *p)
/* Effects: Adds p to the front of doubly-linked list list */
{
  p->previous = NULL;
  p->next = *list;
  if (*list) (*list)->previous = p;
  *list = p;
}

void unlink_page(struct page **list, struct page *p)
/* Effects: Remove p from its doubly linked list */
{
  if (p->previous)
    p->previous->next = p->next;
  else
    *list = p->next;
  if (p->next)
    p->next->previous = p->previous;
}

/* Some memory allocation routines */

#ifdef USE_GC_NONE
#define MINIMUM_MEM_REQUEST (RPAGESIZE * K * K * K)
/* Get memory and align it. */

void *nogc_region_get_mem(size_t s)
{
  size_t request_bytes;
  void *mem;

  /* Don't get less than K * RPAGESIZE extra memory (K * RPAGESIZE
     is the minimum size for something on unused_pages) */
  if (s + K * RPAGESIZE < MINIMUM_MEM_REQUEST) 
    request_bytes = MINIMUM_MEM_REQUEST;
  else
    request_bytes = s;

  mem = malloc(request_bytes + RPAGESIZE - 1);
  ti_alloccheck_notrace(mem, request_bytes + RPAGESIZE - 1);
  mem = (void *)ALIGN((IntPtr)mem, RPAGESIZE);

  /* Add the extra memory to unused_pages */
  if (request_bytes > s)
    {
      struct page *extra = (struct page *)((char *)mem + s);
      PageId cnt;
#ifndef NMEMDEBUG
      set_region_range(extra, (char *)mem + request_bytes, FREEPAGE);
#endif
      cnt = (request_bytes - s) >> RPAGELOG;
      PAGE_SETPAGECOUNT(extra, cnt);
      page_alloc_count += cnt;
      PAGE_SETFREE(extra, 1);
      addfront(&unused_pages, extra);
      addbyaddress(extra);
    }

  return mem;
}
#endif /* USE_GC_NONE */

#ifdef MEMORY_DISTRIBUTED
void *ti_dist_malloc(size_t n)
{
  void *x = ti_malloc_atomic(n);

  if (x) {
    memset(x, 0, n);
  }

  return x;
}
#endif /* MEMORY_DISTRIBUTED */

/* Page to region map management */
/* ----------------------------- */

void set_region(struct page *p, int npages, Region r)
{
  PageId pnb = PAGENB(p);
  RegionId rid = Region2RegionId(r);

  while (npages-- > 0) 
    SetRegionId(pnb++, rid);
}

/* Mark the memory range from 'from' (inclusive) to 'to' (exclusive)
   as belonging to region with id 'rid' */
void set_region_range(void *from, void *to, RegionId rid)
{
  PageId first = PAGENB(from), last = PAGENB((PageId)to - 1);

  while (first <= last)
    SetRegionId(first++, rid);
}

#ifndef LARGE_ADDRESSES
/* This is a page table implemented as a simple table. */
RegionId __regionmap[MAXPAGE];
#else
/* This is a page table implemented as a table of indirect tables. */
RegionId *__regiontable[1 << MEMSLICE2];
PageId large_page_top_bits = 0;
int large_page_top_bits_set = 0;

void SetRegionId(PageId pagenb, RegionId rid)
{
  IntPtr offset2 = (pagenb >> MEMSLICE3) & ((1 << MEMSLICE2) - 1);
  IntPtr offset3 = pagenb & ((1 << MEMSLICE3) - 1);
  RegionId *rmap;

#ifndef NMEMDEBUG
  if (pagenb != 0) {
    if (large_page_top_bits_set) assert(large_page_top_bits == ((pagenb) >> (MEMSLICE2+MEMSLICE3)));
    else {
      large_page_top_bits = ((pagenb) >> (MEMSLICE2+MEMSLICE3));
      large_page_top_bits_set = 1;
    }
  }
#endif

  CHECK_VALID_PAGE(pagenb);

  rmap = __regiontable[offset2];
  if (!rmap)
    {
      unsigned long size = sizeof(RegionId) * (1 << MEMSLICE3);
      int i;

#ifndef USE_GC_NONE
      if (size < GC_page_size) size = GC_page_size;
#endif
      /* assert(!(size & (GC_page_size - 1))); */

      rmap = (RegionId *) ti_alloccheck_notrace(malloc(size), size);
      __regiontable[offset2] = rmap;
      for (i = 0; i < (1 << MEMSLICE3); i++) {
	rmap[i] = UNK_REGIONID;
      }
    }
  rmap[offset3] = rid;
}
#endif

/* Multi-page allocation management */
/* -------------------------------- */

struct page *alloc_new(int n, struct page *next)
/* Assumes PAGEALLOC lock held */
{
  struct page *newp = (struct page *)ti_region_get_mem(n << RPAGELOG);

  if (!newp)
    abort();
  assert(!((long)newp & (RPAGESIZE - 1)));

  page_alloc_count += n;

  newp->next = next;
  PAGE_SETPAGECOUNT(newp, n);
  PAGE_SETFREE(newp, 0);
  addbyaddress(newp);
#ifndef NMEMDEBUG
  {
    PageId i, pnb = PAGENB(newp);

    for (i = pnb; i < pnb + n; i++)
      SetRegionId(i, FREEPAGE);
  }
#endif

  return newp;
}

struct page *alloc_split(struct page *split, int n, struct page *next)
/* Assumes PAGEALLOC lock held */
{
  PageId cnt = PAGE_PAGECOUNT(split);
#ifndef NMEMDEBUG
  /* These pages had better be free */
  PageId i, pnb = PAGENB(split);

  assert(cnt >= n);
  for (i = pnb; i < pnb + cnt; i++)
    assert(Page2RegionId(i) == FREEPAGE);
#endif
  if (cnt > n) {
      struct page *splitoff;

      /* Keep first part of block */
      cnt -= n;
      PAGE_SETPAGECOUNT(split, cnt);
      /* Return latter part of block */
      splitoff = split;
      split = (struct page *)((char *)split + (cnt << RPAGELOG));

      /* Update the by adress list */
      insertbefore_address(split, splitoff->next_address);
    }
  else
    {
      /* remove split from list */
      unlink_page(&unused_pages, split);
    }
  split->next = next;
  PAGE_SETPAGECOUNT(split, n);
  PAGE_SETFREE(split, 0);

  return split;
}

struct page *alloc_pages(int n, struct page *next)
{
  struct page *best;
  jIntPointer bestn;
  struct page *scan;

  assert(n >= K);

  LOCK_PAGEALLOC();

  scan = unused_pages;
  /* Find first fit */
  for (;;)
    {
      if (!scan)
	{
	  struct page *newp = alloc_new(n, next);
          UNLOCK_PAGEALLOC();
	  return newp;
	}

      if (PAGE_PAGECOUNT(scan) >= n) break;
      scan = scan->next;
    }

  /* Now find best fit */
  best = scan;
  bestn = PAGE_PAGECOUNT(scan);
  for (;;) {
      PageId cnt;
      scan = scan->next;
      if (!scan || bestn == n)
	{
	  struct page *newp = alloc_split(best, n, next);

          UNLOCK_PAGEALLOC();
  	  return newp;
	}
      cnt = PAGE_PAGECOUNT(scan);
      if (cnt >= n && cnt < bestn)
	{
	  best = scan;
	  bestn = cnt;
	}
    }
}

static void coalesce(struct page *p)
{
  struct page *prev = p->prev_address, *next;

  PAGE_SETFREE(p, 1);

  if (clobberfreed >= 0) {
    size_t headersz = offsetof(struct page, previous);
    size_t datasz = (PAGE_PAGECOUNT(p) << RPAGELOG) - headersz;
    memset(((char*)p)+headersz, clobberfreed, datasz);
  }

  if (leakfreed) return;

  if (nocoalesce)
    {
      addfront(&unused_pages, p);
      return;
    }

  /* Coalesce with predecessor ? */
  if (PAGE_ISFREE(prev) && (char *)prev + (PAGE_PAGECOUNT(prev) << RPAGELOG) == (char *)p)
    {
      PAGE_SETPAGECOUNT(prev, PAGE_PAGECOUNT(prev) + PAGE_PAGECOUNT(p));
      unlink_address(p);
      p = prev;
    }
  else /* No, add to free pages list */
    addfront(&unused_pages, p);

  next = p->next_address;
  /* Coalesce with successor ? */
  if (PAGE_ISFREE(next) && (char *)p + (PAGE_PAGECOUNT(p) << RPAGELOG) == (char *)next)
    {
      unlink_page(&unused_pages, next);
      PAGE_SETPAGECOUNT(p, PAGE_PAGECOUNT(p) + PAGE_PAGECOUNT(next));
      unlink_address(next);
    }
}

void free_pages(Region r, struct page *p)
/* Assumes PAGEALLOC lock held */
{
#ifndef NMEMDEBUG
  PageId i, pnb = PAGENB(p);
  RegionId rid = Region2RegionId(r);
  PageId cnt = PAGE_PAGECOUNT(p);
  for (i = pnb; i < pnb + cnt; i++)
    {
      assert(Page2RegionId(i) == rid);
      SetRegionId(i, FREEPAGE);
    }
#endif

  coalesce(p);
}


/* Single page management */
/* ---------------------- */

static void add_single_pages(struct page *base)
/* Effects: Adds pages at base to the single_pages list */
{
  PageId n = PAGE_PAGECOUNT(base);
  struct page *prev = base->prev_address, *basenext = base->next_address,
    *next;

  single_page_count += n;

  for (;;)
    {
      ASSERT_FREE(base);
      PAGE_SETFREE(base, 0); /* Not free so that coalesce won't steal these back */
      PAGE_SETPAGECOUNT(base, 1);
      base->prev_address = prev;
      prev = base;
      base->next = single_pages;
      single_pages = base;
      if (--n == 0)
	break;
      next = (struct page *)((char *)base + RPAGESIZE);
      base->next_address = next;
      base = next;
    }
  base->next_address = basenext;
  basenext->prev_address = base;
}

void scavenge_single_pages(int n)
{
  /* Add n pages to the single_pages list */
  struct page *scan, *best;
  jIntPointer bestn;

  /* Take any group in unused_pages that is <= n or < K.
     Remember smallest entry > n too. This is sortof equivalent to
     a best fit where we allow partial allocations to make up a whole */
  best = NULL;
  /* will be big enough with -2, no real need to get the "largest possible"
     value for bestn */
  bestn = (jIntPointer)1 << (sizeof(jIntPointer) * CHAR_BIT - 2);
  scan = unused_pages;
  while (scan)
    {
      /* The pages < K can't be used for anything but single pages so we
	 might as well grab them even if they are a little too big */
      PageId cnt = PAGE_PAGECOUNT(scan);
      if (cnt <= n || cnt < K)
	{
	  struct page *adding = scan;

	  scan = scan->next;
	  n -= cnt;
	  unlink_page(&unused_pages, adding);
	  add_single_pages(adding);
	  if (n <= 0) return;
	}
      else
	{
	  if (cnt < bestn)
	    {
	      bestn = cnt;
	      best = scan;
	    }
	  scan = scan->next;
	}
    }
  /* Still not enough. Split the best block if there is one, allocate
     new pages otherwise */
  if (!best)
    add_single_pages(alloc_new(n, NULL));
  else if (PAGE_PAGECOUNT(best) - n < K)
    {
      unlink_page(&unused_pages, best);
      add_single_pages(best);
    }
  else
    add_single_pages(alloc_split(best, n, NULL));
}

struct page *alloc_single_page(struct page *next)
{
  struct page *p;

  LOCK_PAGEALLOC();

  if (!single_pages)
    scavenge_single_pages(PAGE_GROUP_SIZE);

  ASSERT_FREE(single_pages);
  p = single_pages;
  single_pages = p->next;
  p->next = next;

  single_page_count--;
  assert(PAGE_PAGECOUNT(p) == 1 && !PAGE_ISFREE(p));

  UNLOCK_PAGEALLOC();

  return p;
}

void free_single_page(Region r, struct page *p)
/* Assumes PAGEALLOC lock held */
{
#ifndef NMEMDEBUG
  ASSERT_INUSE(p, r);
  SetRegionId(PAGENB(p), FREEPAGE);
#endif

  assert(PAGE_PAGECOUNT(p) == 1 && !PAGE_ISFREE(p));

  /* Once free list is big enough just coalesce the pages.
     The actual threshold to use might merit further study (something
     adaptive ? e.g., proportional to allocated single pages) */
  if (single_page_count > PAGE_GROUP_SIZE * 2)
    coalesce(p);
  else {
    if (clobberfreed >= 0) {
      size_t headersz = offsetof(struct page, previous);
      size_t datasz = (PAGE_PAGECOUNT(p) << RPAGELOG) - headersz;
      memset(((char*)p)+headersz, clobberfreed, datasz);
    }

    if (!leakfreed) {
      p->next = single_pages;
      single_pages = p;
      single_page_count++;
    }
  }
}