// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// See malloc.h for overview.
//
// TODO(rsc): double-check stats.
// TODO(rsc): solve "stack overflow during malloc" problem.

#include "runtime.h"
#include "malloc.h"
#include "defs.h"

MHeap mheap;
MStats mstats;

// Allocate an object of at least size bytes.
// Small objects are allocated from the per-thread cache's free lists.
// Large objects (> 32 kB) are allocated straight from the heap.
void*
malloc(uintptr size)
{
	int32 sizeclass;
	MCache *c;
	uintptr npages;
	MSpan *s;
	void *v;
	uint32 *ref;

	if(m->mallocing)
		throw("malloc/free - deadlock");
	m->mallocing = 1;

	if(size == 0)
		size = 1;

	if(size <= MaxSmallSize) {
		// Allocate from mcache free lists.
		sizeclass = SizeToClass(size);
		size = class_to_size[sizeclass];
		c = m->mcache;
		v = MCache_Alloc(c, sizeclass, size);
		if(v == nil)
			throw("out of memory");
		mstats.alloc += size;
	} else {
		// TODO(rsc): Report tracebacks for very large allocations.

		// Allocate directly from heap.
		npages = size >> PageShift;
		if((size & PageMask) != 0)
			npages++;
		s = MHeap_Alloc(&mheap, npages, 0);
		if(s == nil)
			throw("out of memory");
		mstats.alloc += npages<<PageShift;
		v = (void*)(s->start << PageShift);
	}

	// setup for mark sweep
	if(!mlookup(v, nil, nil, &ref)) {
		printf("malloc %D; mlookup failed\n", (uint64)size);
		throw("malloc mlookup");
	}
	*ref = RefNone;

	m->mallocing = 0;
	return v;
}

void*
mallocgc(uintptr size)
{
	void *v;

	v = malloc(size);
	if(mstats.inuse_pages > mstats.next_gc)
		gc(0);
	return v;
}

// Free the object whose base pointer is v.
void
free(void *v)
{
	int32 sizeclass, size;
	uintptr page, tmp;
	MSpan *s;
	MCache *c;
	uint32 *ref;

	if(v == nil)
		return;

	if(m->mallocing)
		throw("malloc/free - deadlock");
	m->mallocing = 1;

	if(!mlookup(v, nil, nil, &ref))
		throw("free mlookup");
	*ref = RefFree;

	// Find size class for v.
	page = (uintptr)v >> PageShift;
	sizeclass = MHeapMapCache_GET(&mheap.mapcache, page, tmp);
	if(sizeclass == 0) {
		// Missed in cache.
		s = MHeap_Lookup(&mheap, page);
		if(s == nil)
			throw("free - invalid pointer");
		sizeclass = s->sizeclass;
		if(sizeclass == 0) {
			// Large object.
			mstats.alloc -= s->npages<<PageShift;
			sys_memclr(v, s->npages<<PageShift);
			MHeap_Free(&mheap, s);
			goto out;
		}
		MHeapMapCache_SET(&mheap.mapcache, page, sizeclass);
	}

	// Small object.
	c = m->mcache;
	size = class_to_size[sizeclass];
	sys_memclr(v, size);
	mstats.alloc -= size;
	MCache_Free(c, v, sizeclass, size);

out:
	m->mallocing = 0;
}

int32
mlookup(void *v, byte **base, uintptr *size, uint32 **ref)
{
	uintptr n, nobj, i;
	byte *p;
	MSpan *s;

	s = MHeap_LookupMaybe(&mheap, (uintptr)v>>PageShift);
	if(s == nil) {
		if(base)
			*base = nil;
		if(size)
			*size = 0;
		if(ref)
			*ref = 0;
		return 0;
	}

	p = (byte*)((uintptr)s->start<<PageShift);
	if(s->sizeclass == 0) {
		// Large object.
		if(base)
			*base = p;
		if(size)
			*size = s->npages<<PageShift;
		if(ref)
			*ref = &s->gcref0;
		return 1;
	}

	if((byte*)v >= (byte*)s->gcref) {
		// pointers into the gc ref counts
		// do not count as pointers.
		return 0;
	}

	n = class_to_size[s->sizeclass];
	i = ((byte*)v - p)/n;
	if(base)
		*base = p + i*n;
	if(size)
		*size = n;
	nobj = (s->npages << PageShift) / (n + RefcountOverhead);
	if((byte*)s->gcref < p || (byte*)(s->gcref+nobj) > p+(s->npages<<PageShift)) {
		printf("odd span state=%d span=%p base=%p sizeclass=%d n=%D size=%D npages=%D\n",
			s->state, s, p, s->sizeclass, (uint64)nobj, (uint64)n, (uint64)s->npages);
		printf("s->base sizeclass %d v=%p base=%p gcref=%p blocksize=%D nobj=%D size=%D end=%p end=%p\n",
			s->sizeclass, v, p, s->gcref, (uint64)s->npages<<PageShift,
			(uint64)nobj, (uint64)n, s->gcref + nobj, p+(s->npages<<PageShift));
		throw("bad gcref");
	}
	if(ref)
		*ref = &s->gcref[i];

	return 1;
}

MCache*
allocmcache(void)
{
	return FixAlloc_Alloc(&mheap.cachealloc);
}

void
mallocinit(void)
{
	InitSizes();
	MHeap_Init(&mheap, SysAlloc);
	m->mcache = allocmcache();

	// See if it works.
	free(malloc(1));
}

void*
SysAlloc(uintptr n)
{
	mstats.sys += n;
	return sys_mmap(nil, n, PROT_READ|PROT_WRITE|PROT_EXEC, MAP_ANON|MAP_PRIVATE, -1, 0);
}

void
SysUnused(void *v, uintptr n)
{
	USED(v);
	USED(n);
	// TODO(rsc): call madvise MADV_DONTNEED
}

void
SysFree(void *v, uintptr n)
{
	USED(v);
	USED(n);
	// TODO(rsc): call munmap
}

// Runtime stubs.

extern void *oldmal(uint32);

void*
mal(uint32 n)
{
//return oldmal(n);
	void *v;

	v = mallocgc(n);

	if(0) {
		byte *p;
		uint32 i;
		p = v;
		for(i=0; i<n; i++) {
			if(p[i] != 0) {
				printf("mal %d => %p: byte %d is non-zero\n", n, v, i);
				throw("mal");
			}
		}
	}

//printf("mal %d %p\n", n, v);  // |checkmal to check for overlapping returns.
	return v;
}

// Stack allocator uses malloc/free most of the time,
// but if we're in the middle of malloc and need stack,
// we have to do something else to avoid deadlock.
// In that case, we fall back on a fixed-size free-list
// allocator, assuming that inside malloc all the stack
// frames are small, so that all the stack allocations
// will be a single size, the minimum (right now, 5k).
struct {
	Lock;
	FixAlloc;
} stacks;

void*
stackalloc(uint32 n)
{
	void *v;
	uint32 *ref;

//return oldmal(n);
	if(m->mallocing || m->gcing) {
		lock(&stacks);
		if(stacks.size == 0)
			FixAlloc_Init(&stacks, n, SysAlloc, nil, nil);
		if(stacks.size != n) {
			printf("stackalloc: in malloc, size=%D want %d", (uint64)stacks.size, n);
			throw("stackalloc");
		}
		v = FixAlloc_Alloc(&stacks);
		unlock(&stacks);
		return v;
	}
	v = malloc(n);
	if(!mlookup(v, nil, nil, &ref))
		throw("stackalloc mlookup");
	*ref = RefStack;
	return v;
}

void
stackfree(void *v)
{
//return;

	if(m->mallocing || m->gcing) {
		lock(&stacks);
		FixAlloc_Free(&stacks, v);
		unlock(&stacks);
		return;
	}
	free(v);
}