/*
 * Copyright (c) 2007, 2008 University of Tsukuba
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 3. Neither the name of the University of Tsukuba nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * Copyright (c) 2010-2012 Yuichi Watanabe
 */

#include <common/list.h>
#include <core/assert.h>
#include <core/spinlock.h>
#include <core/string.h>
#include "mm.h"
#include "panic.h"
#include <core/types.h>

#define NUM_OF_ALLOCSIZE	13
#define NUM_OF_ALLOCLIST	7
#define ALLOCLIST_SIZE(n)	((1 << (n)) * 16)
#define ALLOCLIST_DATABIT(n)	(PAGESIZE / ALLOCLIST_SIZE (n))
#define ALLOCLIST_DATASIZE(n)	((ALLOCLIST_DATABIT (n) + 7) / 8)
#define ALLOCLIST_HEADERSIZE(n)	(sizeof (struct allocdata) + \
				 ALLOCLIST_DATASIZE(n) - 1)

struct allocdata {
	LIST1_DEFINE (struct allocdata);
	u8 n, data[1];
};

static LIST1_DEFINE_HEAD (struct page, freepage_list[NUM_OF_ALLOCSIZE]);
static LIST1_DEFINE_HEAD (struct allocdata, alloclist[NUM_OF_ALLOCLIST]);
static int allocsize[NUM_OF_ALLOCSIZE];
static spinlock_t mm_lock, mm_lock2;


/*
 *
 * Page Allocator
 *
 */
struct page *
mm_page_alloc_internal(int n)
{
	int s;
	virt_t virt;
	struct page *p, *q;

	if (n >= NUM_OF_ALLOCSIZE) {
		return NULL;
	}
	s = allocsize[n];
	while ((p = LIST1_POP (freepage_list[n])) == NULL) {
		p = mm_page_alloc_internal (n + 1);
		if (p == NULL) {
			return NULL;
		}
		virt = page_to_virt (p);
		q = virt_to_page (virt ^ s);
		p->allocsize = n;
		p->type = PAGE_TYPE_FREE;
		q->type = PAGE_TYPE_FREE;
		LIST1_ADD (freepage_list[n], p);
		LIST1_ADD (freepage_list[n], q);
	}
	p->type = PAGE_TYPE_ALLOCATED;
	return p;
}

struct page *
mm_page_alloc(int n)
{
	struct page *page;

	spinlock_lock (&mm_lock);
	page = mm_page_alloc_internal(n);
	spinlock_unlock (&mm_lock);

	return page;
}

void
mm_page_free (struct page *p)
{
	int s, n;
	struct page *q, *tmp;
	virt_t virt;

	spinlock_lock (&mm_lock);
	n = p->allocsize;
	p->type = PAGE_TYPE_FREE;
	LIST1_ADD (freepage_list[n], p);
	s = allocsize[n];
	virt = page_to_virt (p);
	while (n < (NUM_OF_ALLOCSIZE - 1) &&
	       (q = virt_to_page (virt ^ s))->type == PAGE_TYPE_FREE &&
		q->allocsize == n) {
		if (virt & s) {
			tmp = p;
			p = q;
			q = tmp;
		}
		LIST1_DEL (freepage_list[n], p);
		LIST1_DEL (freepage_list[n], q);
		q->type = PAGE_TYPE_NOT_HEAD;
		n = ++p->allocsize;
		LIST1_ADD (freepage_list[n], p);
		s = allocsize[n];
		virt = page_to_virt (p);
	}
	spinlock_unlock (&mm_lock);
}

/* returns number of available pages */
int
num_of_available_pages (void)
{
	int i, r, n;
	struct page *p;

	spinlock_lock (&mm_lock);
	r = 0;
	for (i = 0; i < NUM_OF_ALLOCSIZE; i++) {
		n = 0;
		LIST1_FOREACH (freepage_list[i], p)
			n++;
		r += n * (allocsize[i] >> PAGESIZE_SHIFT);
	}
	spinlock_unlock (&mm_lock);
	return r;
}


/* allocate n or more pages */
vmmerr_t
alloc_pages (void **virt, phys_t *phys, int n)
{
	struct page *p;
	int i, s;

	s = n * PAGESIZE;
	for (i = 0; i < NUM_OF_ALLOCSIZE; i++)
		if (allocsize[i] >= s)
			goto found;
/* 	panic ("alloc_pages (%d) failed.", n); */
	return VMMERR_NOMEM;
found:
	p = mm_page_alloc (i);
	if (p == NULL) {
		return VMMERR_NOMEM;
	}
	if (virt)
		*virt = (void *)page_to_virt (p);
	if (phys)
		*phys = page_to_phys (p);
	return 0;
}

/* allocate a page */
vmmerr_t
alloc_page (void **virt, u64 *phys)
{
	return alloc_pages (virt, phys, 1);
}

/* free pages */
void
free_page (void *virt)
{
	mm_page_free (virt_to_page ((virt_t)virt));
}

/* free pages addressed by physical address */
void
free_page_phys (phys_t phys)
{
	mm_page_free (phys_to_page (phys));
}


/*
 *
 * Memory Allocator
 *
 */
static struct allocdata *
alloclist_new (int n)
{
	struct allocdata *r;
	uint i, headlen;
	void *tmp;
	vmmerr_t err;

	err = alloc_page (&tmp, NULL);
	if (err) {
		return NULL;
	}
	r = tmp;
	headlen = ALLOCLIST_HEADERSIZE (n);
	memset (r, 0, headlen);
	r->n = n;
	for (i = 0; i * ALLOCLIST_SIZE (n) < headlen; i++)
		r->data[i / 8] |= 1 << (i % 8);
	return r;
}

static bool
alloclist_alloc (struct allocdata *p, int n, void **r)
{
	uint i, j, datalen, offset;

	datalen = ALLOCLIST_DATASIZE (n);
	for (i = 0; i < datalen; i++) {
		if (p->data[i] != 0xFF)
			goto found;
	}
	return false;
found:
	for (j = 0; j < 8; j++) {
		if ((p->data[i] & (1 << j)) == 0)
			break;
	}
	if (i * 8 + j >= ALLOCLIST_DATABIT (n))
		return false;
	p->data[i] |= (1 << j);
	offset = (i * 8 + j) * ALLOCLIST_SIZE (n);
	ASSERT (offset != 0);
	ASSERT (offset < PAGESIZE);
	*r = (u8 *)p + offset;
	return true;
}

static void
alloclist_free (struct allocdata *p, int n, uint offset)
{
	uint bit, i, j;

	bit = offset / ALLOCLIST_SIZE (n);
	i = bit / 8;
	j = bit % 8;
	ASSERT (p->data[i] & (1 << j));	/* double free check */
	p->data[i] &= ~(1 << j);
}

/* allocate n bytes */
/* FIXME: bad implementation */
void *
alloc (size_t len)
{
	void *r;
	int i;
	struct allocdata *p;
	vmmerr_t err;

	for (i = 0; i < NUM_OF_ALLOCLIST; i++) {
		if (len <= ALLOCLIST_SIZE (i))
			goto found;
	}
	/* allocate pages if len is larger than 1024 */
	err = alloc_pages (&r, NULL, (len + 4095) / 4096);
	if (err) {
		return NULL;
	}
	return r;
found:
	spinlock_lock (&mm_lock2);
	for (;;) {
		p = LIST1_POP (alloclist[i]);
		if (p == NULL)
			p = alloclist_new (i);
		if (p == NULL) {
			spinlock_unlock (&mm_lock2);
			return NULL;
		}
		if (alloclist_alloc (p, i, &r))
			break;
		p->n |= 0x80;
	}
	LIST1_PUSH (alloclist[i], p);
	spinlock_unlock (&mm_lock2);
	return r;
}

/* free */
void
free (void *virt)
{
	struct allocdata *p;
	uint offset;

	offset = (virt_t)virt & PAGESIZE_MASK;
	if (offset == 0) {
		mm_page_free (virt_to_page ((virt_t)virt));
		return;
	}
	spinlock_lock (&mm_lock2);
	p = (struct allocdata *)((virt_t)virt & ~PAGESIZE_MASK);
	if (p->n & 0x80) {
		p->n &= ~0x80;
		LIST1_PUSH (alloclist[p->n], p);
	}
	alloclist_free (p, p->n, offset);
	spinlock_unlock (&mm_lock2);
}

void
mm_alloc_init (void)
{
	int i;

	spinlock_init (&mm_lock);
	spinlock_init (&mm_lock2);

	for (i = 0; i < NUM_OF_ALLOCLIST; i++)
		LIST1_HEAD_INIT (alloclist[i]);
	for (i = 0; i < NUM_OF_ALLOCSIZE; i++) {
		allocsize[i] = 4096 << i;
		LIST1_HEAD_INIT (freepage_list[i]);
	}
}
