/*
 * This module derived from code donated to the FreeBSD Project by
 * Matthew Dillon <dillon@backplane.com>
 *
 * Copyright (c) 1998 The FreeBSD Project
 * 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
 */

#include <sys/cdefs.h>
#include <sys/param.h>

/*
 * LIB/MEMORY/ZALLOC.C	- self contained low-overhead memory pool/allocation
 *			  subsystem
 *
 *	This subsystem implements memory pools and memory allocation
 *	routines.
 *
 *	Pools are managed via a linked list of 'free' areas.  Allocating
 *	memory creates holes in the freelist, freeing memory fills them.
 *	Since the freelist consists only of free memory areas, it is possible
 *	to allocate the entire pool without incuring any structural overhead.
 *
 *	The system works best when allocating similarly-sized chunks of
 *	memory.  Care must be taken to avoid fragmentation when
 *	allocating/deallocating dissimilar chunks.
 *
 *	When a memory pool is first allocated, the entire pool is marked as
 *	allocated.  This is done mainly because we do not want to modify any
 *	portion of a pool's data area until we are given permission.  The
 *	caller must explicitly deallocate portions of the pool to make them
 *	available.
 *
 *	z[n]xalloc() works like z[n]alloc() but the allocation is made from
 *	within the specified address range.  If the segment could not be
 *	allocated, NULL is returned.  WARNING!  The address range will be
 *	aligned to an 8 or 16 byte boundry depending on the cpu so if you
 *	give an unaligned address range, unexpected results may occur.
 *
 *	If a standard allocation fails, the reclaim function will be called
 *	to recover some space.  This usually causes other portions of the
 *	same pool to be released.  Memory allocations at this low level
 *	should not block but you can do that too in your reclaim function
 *	if you want.  Reclaim does not function when z[n]xalloc() is used,
 *	only for z[n]alloc().
 *
 *	Allocation and frees of 0 bytes are valid operations.
 */

#include "zalloc_defs.h"

/*
 * Objects in the pool must be aligned to at least the size of struct MemNode.
 * They must also be aligned to MALLOCALIGN, which should normally be larger
 * than the struct, so assert that to be so at compile time.
 */
typedef char assert_align[(sizeof (struct MemNode) <= MALLOCALIGN) ? 1 : -1];

#define	MEMNODE_SIZE_MASK	MALLOCALIGN_MASK

/*
 * znalloc() -	allocate memory (without zeroing) from pool.  Call reclaim
 *		and retry if appropriate, return NULL if unable to allocate
 *		memory.
 */

void *
znalloc(MemPool *mp, uintptr_t bytes, size_t align)
{
	MemNode **pmn;
	MemNode *mn;

	/*
	 * align according to pool object size (can be 0).  This is
	 * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
	 *
	 */
	bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;

	if (bytes == 0)
		return ((void *)-1);

	/*
	 * locate freelist entry big enough to hold the object.  If all objects
	 * are the same size, this is a constant-time function.
	 */

	if (bytes > mp->mp_Size - mp->mp_Used)
		return (NULL);

	for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
		char *ptr = (char *)mn;
		uintptr_t dptr;
		char *aligned;
		size_t extra;

		dptr = (uintptr_t)(ptr + MALLOCALIGN);	/* pointer to data */
		aligned = (char *)(roundup2(dptr, align) - MALLOCALIGN);
		extra = aligned - ptr;

		if (bytes + extra > mn->mr_Bytes)
			continue;

		/*
		 * Cut extra from head and create new memory node from
		 * remainder.
		 */

		if (extra != 0) {
			MemNode *new;

			new = (MemNode *)aligned;
			new->mr_Next = mn->mr_Next;
			new->mr_Bytes = mn->mr_Bytes - extra;

			/* And update current memory node */
			mn->mr_Bytes = extra;
			mn->mr_Next = new;
			/* In next iteration, we will get our aligned address */
			continue;
		}

		/*
		 *  Cut a chunk of memory out of the beginning of this
		 *  block and fixup the link appropriately.
		 */

		if (mn->mr_Bytes == bytes) {
			*pmn = mn->mr_Next;
		} else {
			mn = (MemNode *)((char *)mn + bytes);
			mn->mr_Next  = ((MemNode *)ptr)->mr_Next;
			mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes;
			*pmn = mn;
		}
		mp->mp_Used += bytes;
		return (ptr);
	}

	/*
	 * Memory pool is full, return NULL.
	 */

	return (NULL);
}

/*
 * zfree() - free previously allocated memory
 */

void
zfree(MemPool *mp, void *ptr, uintptr_t bytes)
{
	MemNode **pmn;
	MemNode *mn;

	/*
	 * align according to pool object size (can be 0).  This is
	 * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
	 */
	bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;

	if (bytes == 0)
		return;

	/*
	 * panic if illegal pointer
	 */

	if ((char *)ptr < (char *)mp->mp_Base ||
	    (char *)ptr + bytes > (char *)mp->mp_End ||
	    ((uintptr_t)ptr & MEMNODE_SIZE_MASK) != 0)
		panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes);

	/*
	 * free the segment
	 */
	mp->mp_Used -= bytes;

	for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
		/*
		 * If area between last node and current node
		 *  - check range
		 *  - check merge with next area
		 *  - check merge with previous area
		 */
		if ((char *)ptr <= (char *)mn) {
			/*
			 * range check
			 */
			if ((char *)ptr + bytes > (char *)mn) {
				panic("zfree(%p,%ju): corrupt memlist1", ptr,
				    (uintmax_t)bytes);
			}

			/*
			 * merge against next area or create independant area
			 */

			if ((char *)ptr + bytes == (char *)mn) {
				((MemNode *)ptr)->mr_Next = mn->mr_Next;
				((MemNode *)ptr)->mr_Bytes =
				    bytes + mn->mr_Bytes;
			} else {
				((MemNode *)ptr)->mr_Next = mn;
				((MemNode *)ptr)->mr_Bytes = bytes;
			}
			*pmn = mn = (MemNode *)ptr;

			/*
			 * merge against previous area (if there is a previous
			 * area).
			 */

			if (pmn != &mp->mp_First) {
				if ((char *)pmn + ((MemNode*)pmn)->mr_Bytes ==
				    (char *)ptr) {
					((MemNode *)pmn)->mr_Next = mn->mr_Next;
					((MemNode *)pmn)->mr_Bytes +=
					    mn->mr_Bytes;
					mn = (MemNode *)pmn;
				}
			}
			return;
		}
		if ((char *)ptr < (char *)mn + mn->mr_Bytes) {
			panic("zfree(%p,%ju): corrupt memlist2", ptr,
			    (uintmax_t)bytes);
		}
	}
	/*
	 * We are beyond the last MemNode, append new MemNode.  Merge against
	 * previous area if possible.
	 */
	if (pmn == &mp->mp_First ||
	    (char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr) {
		((MemNode *)ptr)->mr_Next = NULL;
		((MemNode *)ptr)->mr_Bytes = bytes;
		*pmn = (MemNode *)ptr;
		mn = (MemNode *)ptr;
	} else {
		((MemNode *)pmn)->mr_Bytes += bytes;
		mn = (MemNode *)pmn;
	}
}

/*
 * zextendPool() - extend memory pool to cover additional space.
 *
 *		   Note: the added memory starts out as allocated, you
 *		   must free it to make it available to the memory subsystem.
 *
 *		   Note: mp_Size may not reflect (mp_End - mp_Base) range
 *		   due to other parts of the system doing their own sbrk()
 *		   calls.
 */

void
zextendPool(MemPool *mp, void *base, uintptr_t bytes)
{
	if (mp->mp_Size == 0) {
		mp->mp_Base = base;
		mp->mp_Used = bytes;
		mp->mp_End = (char *)base + bytes;
		mp->mp_Size = bytes;
	} else {
		void *pend = (char *)mp->mp_Base + mp->mp_Size;

		if (base < mp->mp_Base) {
			mp->mp_Size += (char *)mp->mp_Base - (char *)base;
			mp->mp_Used += (char *)mp->mp_Base - (char *)base;
			mp->mp_Base = base;
		}
		base = (char *)base + bytes;
		if (base > pend) {
			mp->mp_Size += (char *)base - (char *)pend;
			mp->mp_Used += (char *)base - (char *)pend;
			mp->mp_End = (char *)base;
		}
	}
}

#ifdef ZALLOCDEBUG

void
zallocstats(MemPool *mp)
{
	int abytes = 0;
	int hbytes = 0;
	int fcount = 0;
	MemNode *mn;

	printf("%d bytes reserved", (int)mp->mp_Size);

	mn = mp->mp_First;

	if ((void *)mn != (void *)mp->mp_Base) {
		abytes += (char *)mn - (char *)mp->mp_Base;
	}

	while (mn != NULL) {
		if ((char *)mn + mn->mr_Bytes != mp->mp_End) {
			hbytes += mn->mr_Bytes;
			++fcount;
		}
		if (mn->mr_Next != NULL) {
			abytes += (char *)mn->mr_Next -
			    ((char *)mn + mn->mr_Bytes);
		}
		mn = mn->mr_Next;
	}
	printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n",
	    abytes, fcount, hbytes);
}

#endif