/*
 *  lwk/mm/bootmem.c
 *
 *  Copyright (C) 1999 Ingo Molnar
 *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
 *
 *  simple boot-time physical memory area allocator and
 *  free memory collector. It's used to deal with reserved
 *  system memory and memory holes as well.
 */

#include <lwk/init.h>
#include <lwk/pfn.h>
#include <lwk/bootmem.h>
#include <lwk/params.h>
#include <lwk/log2.h>
#include <lwk/pmem.h>
#include <lwk/kmem.h>
#include <lwk/bitops.h>
#include <arch/io.h>

/**
 * Set to true once bootmem allocator has been destroyed.
 */
static bool bootmem_destoyed = false;

/**
 * Access to this subsystem has to be serialized externally.
 * (this is true for the boot process anyway)
 */


/**
 * Amount of system memory to reserve for use by the kernel. The first
 * kmem_size bytes of system memory [0, kmem_size) will be added to the
 * kernel memory pool. The remainder of system memory is left untouched by
 * the kernel and is available for use by applications.
 */
static unsigned long kmem_size = (1024 * 1024 * 8);  /* default is first 8 MB */
param(kmem_size, ulong);


/**
 *
 */
static bootmem_data_t __initdata bootmem_data;

/**
 * List of bootmem_data structures, each describing a section of
 * physical memory.
 */
static LIST_HEAD(bdata_list);

/**
 * Returns the number of _pages_ that will be allocated for the boot bitmap.
 */
unsigned long __init
bootmem_bootmap_pages(unsigned long pages)
{
	unsigned long mapsize;

	mapsize = (pages+7)/8;
	mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK;
	mapsize >>= PAGE_SHIFT;

	return mapsize;
}

/**
 * Links a newly created bootmem_data structure to the bdata_list.
 */
static void __init
link_bootmem(bootmem_data_t *bdata)
{
	bootmem_data_t *ent;
	if (list_empty(&bdata_list)) {
		list_add(&bdata->list, &bdata_list);
		return;
	}
	/* insert in order */
	list_for_each_entry(ent, &bdata_list, list) {
		if (bdata->node_boot_start < ent->node_boot_start) {
			list_add_tail(&bdata->list, &ent->list);
			return;
		}
	}
	list_add_tail(&bdata->list, &bdata_list);
	return;
}

/**
 * Called once to set up the allocator itself.
 */
static unsigned long __init
init_bootmem_core(
	bootmem_data_t	*bdata,
	unsigned long	mapstart,
	unsigned long	start,
	unsigned long	end
)
{
	unsigned long mapsize = ((end - start)+7)/8;

	mapsize = ALIGN(mapsize, sizeof(long));
	bdata->node_bootmem_map = phys_to_virt(mapstart << PAGE_SHIFT);
	bdata->node_boot_start = (start << PAGE_SHIFT);
	bdata->node_low_pfn = end;
	link_bootmem(bdata);

	/*
	 * Initially all pages are reserved - setup_arch() has to
	 * register free RAM areas explicitly.
	 */
	memset(bdata->node_bootmem_map, 0xff, mapsize);

	return mapsize;
}

/**
 * Marks a particular physical memory range as unallocatable. Usable RAM
 * might be used for boot-time allocations - or it might get added
 * to the free page pool later on.
 */
static void __init
reserve_bootmem_core(
	bootmem_data_t	*bdata,
	unsigned long	addr,
	unsigned long	size
)
{
	unsigned long sidx, eidx;
	unsigned long i;

	/*
	 * round up, partially reserved pages are considered
	 * fully reserved.
	 */
	BUG_ON(!size);
	BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn);
	BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn);

	sidx = PFN_DOWN(addr - bdata->node_boot_start);
	eidx = PFN_UP(addr + size - bdata->node_boot_start);

	for (i = sidx; i < eidx; i++) {
		if (test_and_set_bit(i, bdata->node_bootmem_map)) {
#ifdef CONFIG_DEBUG_BOOTMEM
			printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
#endif
		}
	}
}

/**
 * Frees a section of bootmemory.
 */
static void __init
free_bootmem_core(
	bootmem_data_t	*bdata,
	unsigned long	addr,
	unsigned long	size
)
{
	unsigned long i;
	unsigned long start;
	/*
	 * round down end of usable mem, partially free pages are
	 * considered reserved.
	 */
	unsigned long sidx;
	unsigned long eidx = (addr + size - bdata->node_boot_start)/PAGE_SIZE;
	unsigned long end = (addr + size)/PAGE_SIZE;

	BUG_ON(!size);
	BUG_ON(end > bdata->node_low_pfn);

	if (addr < bdata->last_success)
		bdata->last_success = addr;

	/*
	 * Round up the beginning of the address.
	 */
	start = (addr + PAGE_SIZE-1) / PAGE_SIZE;
	sidx = start - (bdata->node_boot_start/PAGE_SIZE);

	for (i = sidx; i < eidx; i++) {
		if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map)))
			BUG();
	}
}

/**
 * We 'merge' subsequent allocations to save space. We might 'lose'
 * some fraction of a page if allocations cannot be satisfied due to
 * size constraints on boxes where there is physical RAM space
 * fragmentation - in these cases (mostly large memory boxes) this
 * is not a problem.
 *
 * On low memory boxes we get it right in 100% of the cases.
 *
 * alignment has to be a power of 2 value.
 *
 * NOTE:  This function is _not_ reentrant.
 */
void * __init
__alloc_bootmem_core(
	struct bootmem_data	*bdata,
	unsigned long		size,
	unsigned long		align,
	unsigned long		goal,
	unsigned long		limit
)
{
	unsigned long offset, remaining_size, areasize, preferred;
	unsigned long i, start = 0, incr, eidx, end_pfn = bdata->node_low_pfn;
	void *ret;

	if (bootmem_destoyed)
		panic("The bootmem allocator has been destroyed.");

	if(!size) {
		printk("__alloc_bootmem_core(): zero-sized request\n");
		BUG();
	}
	BUG_ON(align & (align-1));

	if (limit && bdata->node_boot_start >= limit)
		return NULL;

        limit >>=PAGE_SHIFT;
	if (limit && end_pfn > limit)
		end_pfn = limit;

	eidx = end_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
	offset = 0;
	if (align &&
	    (bdata->node_boot_start & (align - 1UL)) != 0)
		offset = (align - (bdata->node_boot_start & (align - 1UL)));
	offset >>= PAGE_SHIFT;

	/*
	 * We try to allocate bootmem pages above 'goal'
	 * first, then we try to allocate lower pages.
	 */
	if (goal && (goal >= bdata->node_boot_start) && 
	    ((goal >> PAGE_SHIFT) < end_pfn)) {
		preferred = goal - bdata->node_boot_start;

		if (bdata->last_success >= preferred)
			if (!limit || (limit && limit > bdata->last_success))
				preferred = bdata->last_success;
	} else
		preferred = 0;

	preferred = ALIGN(preferred, align) >> PAGE_SHIFT;
	preferred += offset;
	areasize = (size+PAGE_SIZE-1)/PAGE_SIZE;
	incr = align >> PAGE_SHIFT ? : 1;

restart_scan:
	for (i = preferred; i < eidx; i += incr) {
		unsigned long j;
		i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i);
		i = ALIGN(i, incr);
		if (i >= eidx)
			break;
		if (test_bit(i, bdata->node_bootmem_map))
			continue;
		for (j = i + 1; j < i + areasize; ++j) {
			if (j >= eidx)
				goto fail_block;
			if (test_bit (j, bdata->node_bootmem_map))
				goto fail_block;
		}
		start = i;
		goto found;
	fail_block:
		i = ALIGN(j, incr);
	}

	if (preferred > offset) {
		preferred = offset;
		goto restart_scan;
	}
	return NULL;

found:
	bdata->last_success = start << PAGE_SHIFT;
	BUG_ON(start >= eidx);

	/*
	 * Is the next page of the previous allocation-end the start
	 * of this allocation's buffer? If yes then we can 'merge'
	 * the previous partial page with this allocation.
	 */
	if (align < PAGE_SIZE &&
	    bdata->last_offset && bdata->last_pos+1 == start) {
		offset = ALIGN(bdata->last_offset, align);
		BUG_ON(offset > PAGE_SIZE);
		remaining_size = PAGE_SIZE-offset;
		if (size < remaining_size) {
			areasize = 0;
			/* last_pos unchanged */
			bdata->last_offset = offset+size;
			ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
						bdata->node_boot_start);
		} else {
			remaining_size = size - remaining_size;
			areasize = (remaining_size+PAGE_SIZE-1)/PAGE_SIZE;
			ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
						bdata->node_boot_start);
			bdata->last_pos = start+areasize-1;
			bdata->last_offset = remaining_size;
		}
		bdata->last_offset &= ~PAGE_MASK;
	} else {
		bdata->last_pos = start + areasize - 1;
		bdata->last_offset = size & ~PAGE_MASK;
		ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
	}

	/*
	 * Reserve the area now:
	 */
	for (i = start; i < start+areasize; i++)
		if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map)))
			BUG();
	memset(ret, 0, size);
	return ret;
}

static void __init
free_all_bootmem_core(struct bootmem_data *bdata)
{
	unsigned long pfn;
	unsigned long vaddr;
	unsigned long i, m, count;
	unsigned long bootmem_total=0, kmem_total=0, umem_total=0;
	unsigned long kmem_max_idx, max_idx;
	unsigned long *map; 
	struct pmem_region rgn;

	BUG_ON(!bdata->node_bootmem_map);

	kmem_max_idx = (kmem_size >> PAGE_SHIFT) - (bdata->node_boot_start >> PAGE_SHIFT);
	max_idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
	BUG_ON(kmem_max_idx > max_idx);

	/* Create the initial kernel managed memory pool (kmem) */
	count = 0;
	pfn = bdata->node_boot_start >> PAGE_SHIFT;  /* first extant page of node */
	map = bdata->node_bootmem_map;
	for (i = 0; i < kmem_max_idx; ) {
		unsigned long v = ~map[i / BITS_PER_LONG];

		if (v) {
			vaddr = (unsigned long) __va(pfn << PAGE_SHIFT);
			for (m = 1; m && i < kmem_max_idx; m<<=1, vaddr+=PAGE_SIZE, i++) {
				if (v & m) {
					count++;
					kmem_add_memory(vaddr, PAGE_SIZE);
				}
			}
		} else {
			i+=BITS_PER_LONG;
		}
		pfn += BITS_PER_LONG;
	}
	BUG_ON(count == 0);

	/*
	 * At this point, kmem_alloc() will work. The physical memory tracking
	 * code relies on kmem_alloc(), so it cannot be initialized until now.
	 *
	 * Tell the physical memory tracking subsystem about the kernel-managed
	 * pool and the remaining memory that will be managed by user-space.
	 */
	pfn = bdata->node_boot_start >> PAGE_SHIFT;  /* first extant page of node */
	map = bdata->node_bootmem_map;
	pmem_region_unset_all(&rgn);
	rgn.type_is_set = true;
	rgn.allocated_is_set = true;
	rgn.lgroup_is_set = true;
	for (i = 0; i < max_idx; ) {
		unsigned long v = ~map[i / BITS_PER_LONG];
		unsigned long paddr = (unsigned long) pfn << PAGE_SHIFT;

		for (m = 1; m && i < max_idx; m<<=1, paddr+=PAGE_SIZE, i++) {
			rgn.start = paddr;
			rgn.end   = paddr + PAGE_SIZE;

			if (v & m) {
				if (i < kmem_max_idx) {
					rgn.type = PMEM_TYPE_KMEM;
					rgn.allocated = true;
					rgn.lgroup = 0;
					++kmem_total;
				} else {
					rgn.type = PMEM_TYPE_UMEM;
					rgn.allocated = false;
					rgn.lgroup = 0;
					++umem_total;
				}
			} else {
				rgn.type = PMEM_TYPE_BOOTMEM;
				rgn.allocated = true;
				rgn.lgroup = 0;
				++bootmem_total;
			}

			if (pmem_add(&rgn))
				BUG();
		}

		pfn += BITS_PER_LONG;
	}

	/*
	 * Now free the allocator bitmap itself, it's not
	 * needed anymore:
	 */
	vaddr = (unsigned long)bdata->node_bootmem_map;
	count = 0;
	pmem_region_unset_all(&rgn);
	rgn.type_is_set = true;
	rgn.allocated_is_set = true;
	rgn.lgroup_is_set = true;
	for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,vaddr+=PAGE_SIZE) {
		count++;

		rgn.start = __pa(vaddr);
		rgn.end   = rgn.start + PAGE_SIZE;

		if (i < kmem_max_idx) {
			kmem_add_memory(vaddr, PAGE_SIZE);
			rgn.type = PMEM_TYPE_KMEM;
			rgn.allocated = true;
			rgn.lgroup = 0;
		} else {
			rgn.type = PMEM_TYPE_UMEM;
			rgn.allocated = false;
			rgn.lgroup = 0;
		}

		pmem_add(&rgn);
	}
	BUG_ON(count == 0);

	/* Mark the bootmem allocator as dead */
	bdata->node_bootmem_map = NULL;

	printk(KERN_DEBUG
	       "The boot-strap bootmem allocator has been destroyed:\n");
	printk(KERN_DEBUG
	       "  %lu bytes released to the kernel-managed memory pool (kmem)\n",
	       kmem_total << PAGE_SHIFT);
	printk(KERN_DEBUG
	       "  %lu bytes released to the user-managed memory pool (umem)\n",
	       umem_total << PAGE_SHIFT);
}

/**
 * Initialize boot memory allocator.
 */
unsigned long __init
init_bootmem(unsigned long start, unsigned long pages)
{
	return init_bootmem_core(&bootmem_data, start, 0, pages);
}

/**
 * Reserve a portion of the boot memory.
 * This prevents the reserved memory from being allocated.
 */
void __init
reserve_bootmem(unsigned long addr, unsigned long size)
{
	reserve_bootmem_core(&bootmem_data, addr, size);
}

/**
 * Return a portion of boot memory to the free pool.
 * Note that the region freed is the set of pages covering
 * the byte range [addr, addr+size).
 */
void __init
free_bootmem(unsigned long addr, unsigned long size)
{
	free_bootmem_core(&bootmem_data, addr, size);
}

void __init
free_all_bootmem(void)
{
	free_all_bootmem_core(&bootmem_data);
	bootmem_destoyed = true;
}

static void * __init
__alloc_bootmem_nopanic(unsigned long size, unsigned long align, unsigned long goal)
{
	bootmem_data_t *bdata;
	void *ptr;

	list_for_each_entry(bdata, &bdata_list, list)
		if ((ptr = __alloc_bootmem_core(bdata, size, align, goal, 0)))
			return(ptr);
	return NULL;
}

/**
 * Allocate a chunk of memory from the boot memory allocator.
 *
 *     size  = number of bytes requested
 *     align = required alignment
 *     goal  = hint specifying address to start search.
 */
void * __init
__alloc_bootmem(unsigned long size, unsigned long align, unsigned long goal)
{
	void *mem = __alloc_bootmem_nopanic(size,align,goal);
	if (mem)
		return mem;
	/*
	 * Whoops, we cannot satisfy the allocation request.
	 */
	printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
	panic("Out of memory");
	return NULL;
}

/**
 * Allocates a block of memory of the specified size.
 */
void * __init
alloc_bootmem(unsigned long size)
{
	return __alloc_bootmem(size, SMP_CACHE_BYTES, 0);
}

/**
 * Allocates a block of memory of the specified size and alignment.
 */
void * __init
alloc_bootmem_aligned(unsigned long size, unsigned long align)
{
	return __alloc_bootmem(size, align, 0);
}

/**
 * Initializes the kernel memory subsystem.
 */
void __init
mem_subsys_init(void)
{
	/* We like powers of two */
	if (!is_power_of_2(kmem_size)) {
		printk(KERN_WARNING "kmem_size must be a power of two.");
		kmem_size = roundup_pow_of_two(kmem_size);
	}

	printk(KERN_DEBUG
	       "First %lu bytes of system memory reserved for the kernel.\n",
	       kmem_size);

	/* Initialize the kernel memory pool */
	kmem_create_zone(PAGE_OFFSET, kmem_size);
	free_all_bootmem();
	arch_memsys_init(kmem_size);
}