#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 ?) */

#define PAGECOUNTBITS (CHAR_BIT * sizeof(PageId) - 1)

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;

  /* number of pages in this allocation unit. Negative for free pages. */
  #ifdef __xlC__
    uintptr_t pagecount : PAGECOUNTBITS;
  #else  
    PageId pagecount : PAGECOUNTBITS;
  #endif

  unsigned int free : 1;

  /* 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 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, p->pagecount, (char *)p + (p->pagecount << RPAGELOG),
	      p->free ? "F" : "");
#endif
      if (p->free)
	freecount += p->pagecount;
    }
  for (p = unused_pages; p; p = p->next)
    unused += p->pagecount;

  *pfreecount = freecount;
  *punused = unused;
}

void get_region_stats(jlong *regionTotalHeapSize, jlong *regionHeapInUse) {
  jlong freecount = 0, unused = 0;
  assert(regionTotalHeapSize && regionHeapInUse);
  get_page_stats(&freecount, &unused);
  *regionTotalHeapSize = ((jlong)page_alloc_count)*RPAGESIZE;
  *regionHeapInUse = *regionTotalHeapSize - 
                     ((jlong)(freecount+unused+single_page_count))*RPAGESIZE;
}

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

  fprintf(stderr, "%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);
}

static void init_pages(void)
{
  pages_byaddress.next_address = &pages_byaddress;
  pages_byaddress.prev_address = &pages_byaddress;

  if (getenvMaster("TI_NOCOALESCE")) nocoalesce = 1;
}

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(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);

#ifndef NMEMDEBUG
      set_region_range(extra, (char *)mem + request_bytes, FREEPAGE);
#endif
      extra->pagecount = (request_bytes - s) >> RPAGELOG;
      page_alloc_count += extra->pagecount;
      extra->free = 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(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;
  newp->pagecount = n;
  newp->free = 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 */
{
#ifndef NMEMDEBUG
  /* These pages had better be free */
  PageId i, pnb = PAGENB(split);

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

      /* Keep first part of block */
      split->pagecount -= n;
      /* Return latter part of block */
      splitoff = split;
      split = (struct page *)((char *)split + (split->pagecount << 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;
  split->pagecount = n;
  split->free = 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 (scan->pagecount >= n) break;
      scan = scan->next;
    }

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

          UNLOCK_PAGEALLOC();
  	  return newp;
	}

      if (scan->pagecount >=n && scan->pagecount < bestn)
	{
	  best = scan;
	  bestn = scan->pagecount;
	}
    }
}

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

  p->free = 1;

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

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

  next = p->next_address;
  /* Coalesce with successor ? */
  if (next->free && (char *)p + (p->pagecount << RPAGELOG) == (char *)next)
    {
      unlink_page(&unused_pages, next);
      p->pagecount += next->pagecount;
      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);

  for (i = pnb; i < pnb + p->pagecount; 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 = base->pagecount;
  struct page *prev = base->prev_address, *basenext = base->next_address,
    *next;

  single_page_count += n;

  for (;;)
    {
      ASSERT_FREE(base);
      base->free = 0; /* Not free so that coalesce won't steal these back */
      base->pagecount = 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 */
      if (scan->pagecount <= n || scan->pagecount < K)
	{
	  struct page *adding = scan;

	  scan = scan->next;
	  n -= adding->pagecount;
	  unlink_page(&unused_pages, adding);
	  add_single_pages(adding);
	  if (n <= 0) return;
	}
      else
	{
	  if (scan->pagecount < bestn)
	    {
	      bestn = scan->pagecount;
	      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 (best->pagecount - 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(p->pagecount == 1 && !p->free);

  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(p->pagecount == 1 && !p->free);

  /* 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
    {
      p->next = single_pages;
      single_pages = p;
      single_page_count++;
    }
}