/*
 * Allocate thread stacks
 *
 * The Plan 9 virtual address allocator works from the highest address below
 * the bottom of the user stack downwards. That is:
 * 	(0x0) | TTTT             ...SSSUUU | KKKKKK | (~0x0)
 *
 * Each thread stack is flanked by two red zones, each one page, immediately
 * above and below. We bypass the virtual address allocator by requesting 
 * stacks and redzones at specific addresses.
 *
 * To allocate the first thread stack, we call segattach(SG_NONE...) and use
 * the address returned by the VM as a 'base' for the red zones. We then
 * allocate a red zone prior to the start of the thread stack, followed by 
 * the stack itself:
 *	(0x0) | TTTT		....RSRUUU | KKKKKK | (~0x0)
 *
 * Subsequent thread stack allocations are at lower addresses, reusing the 
 * lower redzone of an adjacent thread stack if possible.
 *
 * We keep an address-ordered list of redzones; on stack allocation, we scan
 * the space between unused redzones for a hole, before attempting to allocate
 * a new one.
 *
 * Stack frees release the pages backing the stack but not the redzones, unless
 * we free the lowest stack. 
 */

#include <u.h>
#include <libc.h>
#include <thread.h>
#include "threadimpl.h"

#define BY2PG (4096)

struct redzone {
	struct redzone *next;
	char *addr; /* Redzone address */
	int right;
};

static Lock stklock;
static struct redzone *low;

void *_stackmalloc(unsigned long size) {
	int pgssize;
	char *base, *rztop, *rzbottom, *p, *bp;
	struct redzone *rzt;

	pgssize = (size) + (BY2PG - 1) & ~(BY2PG - 1);

	lock(&stklock);

	if (low == nil) {
		low = mallocz(sizeof(struct redzone), 1);
		if (low == nil) {
			unlock(&stklock);
			return nil;
		}

		rztop = segattach(SG_NONE | SG_SAS | SG_CEXEC, "memory", nil, BY2PG);
		if (rztop == (void *) -1) {
			free(low);
			low = nil;
			unlock(&stklock);
			return nil;
		}

		low->addr = rztop;
	}

	if(low->next == nil) {
		rztop = low->addr;
		p = rztop - pgssize - BY2PG;
		rzbottom = segattach(SG_NONE | SG_SAS | SG_CEXEC, "memory", p, BY2PG);
		if (rzbottom == (void *) -1) {
			unlock(&stklock);
			return nil;
		}

		rzt = mallocz(sizeof(struct redzone), 1);
		if (rzt == nil) {
			segdetach(rzbottom);
			unlock(&stklock);
			return nil;
		}

		rzt->addr = rzbottom;
		rzt->next = low;
		low = rzt;
	}

	for(rzt = low; rzt->next != nil;) {
		if (((rzt->next->addr - rzt->addr + BY2PG) >= pgssize) && !rzt->right) {
			break;
		}
		rzt = rzt->next;
	}

	if (rzt->next == nil) {
		/* We could not find a hole; we must allocate below 'low' */
		bp = low->addr - pgssize;
		base = segattach(SG_COMMIT | SG_SAS | SG_CEXEC, "memory", bp, pgssize);
		if (base == (void *) -1) {
			unlock(&stklock);
			return nil;
		}

		p = base - BY2PG;
		rzbottom = segattach(SG_NONE | SG_SAS | SG_CEXEC, "memory", p, BY2PG);
		if (rzbottom == (void *) -1) {
			segdetach(base);
			unlock(&stklock);
			return nil;
		}

		rzt = mallocz(sizeof(struct redzone), 1);
		if (rzt == nil) {
			segdetach(rzbottom);
			segdetach(base);
			unlock(&stklock);
			return nil;
		}

		rzt->next = low;
		rzt->addr = rzbottom;
		low = rzt;
		low->right = 1;

		unlock(&stklock);
		return base;

	} else {
		/* We found a hole */
		bp = rzt->addr + BY2PG;
		base = segattach(SG_COMMIT | SG_SAS | SG_CEXEC, "memory", bp, pgssize);
		if (base == (void *) -1) {
			unlock(&stklock);
			return nil;
		}
		rzt->right = 1;

		unlock(&stklock);
		return base;
	}

	/* NOTREACHED */
}

void _stackfree(void *stack, unsigned long size) {
	char *stk;
	struct redzone *nz;
	int found;

	stk = stack;

	if (stack == nil)
		return;

	/* Freeing the lowest stack segment */
	if ((stk - BY2PG) == low->addr) {
		nz = low->next;

		segdetach(low->addr);
		segdetach(stk);

		free(low);
		low = nz;
	} else {
		segdetach(stk);

		found = 0;
		for (nz = low; nz->next != nil; nz = nz->next) 
			if (nz->addr == (stk - BY2PG)) {
				if (found == 1) {
					found = 0;
					break;
				}
				found = 1;
				nz->right = 0;
			}
		if (found == 0)
			print("Redzone list error \n");
	}
}