/*
 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009, 2014
 *	The President and Fellows of Harvard College.
 *
 * 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 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 UNIVERSITY 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 UNIVERSITY 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.
 */

/*
 * User-level malloc and free implementation.
 *
 * This is a basic first-fit allocator. It's intended to be simple and
 * easy to follow. It performs abysmally if the heap becomes larger than
 * physical memory. To get (much) better out-of-core performance, port
 * the kernel's malloc. :-)
 */

#include <stdlib.h>
#include <stdint.h>  // for uintptr_t on non-OS/161 platforms
#include <unistd.h>
#include <err.h>
#include <assert.h>

#undef MALLOCDEBUG

#if defined(__mips__) || defined(__i386__)
#define MALLOC32
#elif defined(__alpha__) || defined(__x86_64__)
#define MALLOC64
#else
#error "please fix me"
#endif

/*
 * malloc block header.
 *
 * mh_prevblock is the downwards offset to the previous header, 0 if this
 * is the bottom of the heap.
 *
 * mh_nextblock is the upwards offset to the next header.
 *
 * mh_pad is unused.
 * mh_inuse is 1 if the block is in use, 0 if it is free.
 * mh_magic* should always be a fixed value.
 *
 * MBLOCKSIZE should equal sizeof(struct mheader) and be a power of 2.
 * MBLOCKSHIFT is the log base 2 of MBLOCKSIZE.
 * MMAGIC is the value for mh_magic*.
 */
struct mheader {

#if defined(MALLOC32)
#define MBLOCKSIZE 8
#define MBLOCKSHIFT 3
#define MMAGIC 2
	/*
	 * 32-bit platform. size_t is 32 bits (4 bytes).
	 * Block size is 8 bytes.
	 */
	unsigned mh_prevblock:29;
	unsigned mh_pad:1;
	unsigned mh_magic1:2;

	unsigned mh_nextblock:29;
	unsigned mh_inuse:1;
	unsigned mh_magic2:2;

#elif defined(MALLOC64)
#define MBLOCKSIZE 16
#define MBLOCKSHIFT 4
#define MMAGIC 6
	/*
	 * 64-bit platform. size_t is 64 bits (8 bytes)
	 * Block size is 16 bytes.
	 */
	unsigned mh_prevblock:60;
	unsigned mh_pad:1;
	unsigned mh_magic1:3;

	unsigned mh_nextblock:60;
	unsigned mh_inuse:1;
	unsigned mh_magic2:3;

#else
#error "please fix me"
#endif
};

/*
 * Operator macros on struct mheader.
 *
 * M_NEXT/PREVOFF:	return offset to next/previous header
 * M_NEXT/PREV:		return next/previous header
 *
 * M_DATA:		return data pointer of a header
 * M_SIZE:		return data size of a header
 *
 * M_OK:		true if the magic values are correct
 *
 * M_MKFIELD:		prepare a value for mh_next/prevblock.
 * 			(value should include the header size)
 */

#define M_NEXTOFF(mh)	((size_t)(((size_t)((mh)->mh_nextblock))<<MBLOCKSHIFT))
#define M_PREVOFF(mh)	((size_t)(((size_t)((mh)->mh_prevblock))<<MBLOCKSHIFT))
#define M_NEXT(mh)	((struct mheader *)(((char*)(mh))+M_NEXTOFF(mh)))
#define M_PREV(mh)	((struct mheader *)(((char*)(mh))-M_PREVOFF(mh)))

#define M_DATA(mh)	((void *)((mh)+1))
#define M_SIZE(mh)	(M_NEXTOFF(mh)-MBLOCKSIZE)

#define M_OK(mh)	((mh)->mh_magic1==MMAGIC && (mh)->mh_magic2==MMAGIC)

#define M_MKFIELD(off)	((off)>>MBLOCKSHIFT)

/*
 * System page size. In POSIX you're supposed to call
 * sysconf(_SC_PAGESIZE). If _SC_PAGESIZE isn't defined, as on OS/161,
 * assume 4K.
 */

#ifdef _SC_PAGESIZE
static size_t __malloc_pagesize;
#define PAGE_SIZE __malloc_pagesize
#else
#define PAGE_SIZE 4096
#endif

////////////////////////////////////////////////////////////

/*
 * Static variables - the bottom and top addresses of the heap.
 */
static uintptr_t __heapbase, __heaptop;

/*
 * Setup function.
 */
static
void
__malloc_init(void)
{
	void *x;

	/*
	 * Check various assumed properties of the sizes.
	 */
	if (sizeof(struct mheader) != MBLOCKSIZE) {
		errx(1, "malloc: Internal error - MBLOCKSIZE wrong");
	}
	if ((MBLOCKSIZE & (MBLOCKSIZE-1))!=0) {
		errx(1, "malloc: Internal error - MBLOCKSIZE not power of 2");
	}
	if (1<<MBLOCKSHIFT != MBLOCKSIZE) {
		errx(1, "malloc: Internal error - MBLOCKSHIFT wrong");
	}

	/* init should only be called once. */
	if (__heapbase!=0 || __heaptop!=0) {
		errx(1, "malloc: Internal error - bad init call");
	}

	/* Get the page size, if needed. */
#ifdef _SC_PAGESIZE
	__malloc_pagesize = sysconf(_SC_PAGESIZE);
#endif

	/* Use sbrk to find the base of the heap. */
	x = sbrk(0);
	if (x==(void *)-1) {
		err(1, "malloc: initial sbrk failed");
	}
	if (x==(void *) 0) {
		errx(1, "malloc: Internal error - heap began at 0");
	}
	__heapbase = __heaptop = (uintptr_t)x;

	/*
	 * Make sure the heap base is aligned the way we want it.
	 * (On OS/161, it will begin on a page boundary. But on
	 * an arbitrary Unix, it may not be, as traditionally it
	 * begins at _end.)
	 */

	if (__heapbase % MBLOCKSIZE != 0) {
		size_t adjust = MBLOCKSIZE - (__heapbase % MBLOCKSIZE);
		x = sbrk(adjust);
		if (x==(void *)-1) {
			err(1, "malloc: sbrk failed aligning heap base");
		}
		if ((uintptr_t)x != __heapbase) {
			err(1, "malloc: heap base moved during init");
		}
#ifdef MALLOCDEBUG
		warnx("malloc: adjusted heap base upwards by %lu bytes",
		      (unsigned long) adjust);
#endif
		__heapbase += adjust;
		__heaptop = __heapbase;
	}
}

////////////////////////////////////////////////////////////

#ifdef MALLOCDEBUG

/*
 * Debugging print function to iterate and dump the entire heap.
 */
static
void
__malloc_dump(void)
{
	struct mheader *mh;
	uintptr_t i;
	size_t rightprevblock;

	warnx("heap: ************************************************");

	rightprevblock = 0;
	for (i=__heapbase; i<__heaptop; i += M_NEXTOFF(mh)) {
		mh = (struct mheader *) i;
		if (!M_OK(mh)) {
			errx(1, "malloc: Heap corrupt; header at 0x%lx"
			     " has bad magic bits",
			     (unsigned long) i);
		}
		if (mh->mh_prevblock != rightprevblock) {
			errx(1, "malloc: Heap corrupt; header at 0x%lx"
			     " has bad previous-block size %lu "
			     "(should be %lu)",
			     (unsigned long) i,
			     (unsigned long) mh->mh_prevblock << MBLOCKSHIFT,
			     (unsigned long) rightprevblock << MBLOCKSHIFT);
		}
		rightprevblock = mh->mh_nextblock;

		warnx("heap: 0x%lx 0x%-6lx (next: 0x%lx) %s",
		      (unsigned long) i + MBLOCKSIZE,
		      (unsigned long) M_SIZE(mh),
		      (unsigned long) (i+M_NEXTOFF(mh)),
		      mh->mh_inuse ? "INUSE" : "FREE");
	}
	if (i!=__heaptop) {
		errx(1, "malloc: Heap corrupt; ran off end");
	}

	warnx("heap: ************************************************");
}

#endif /* MALLOCDEBUG */

////////////////////////////////////////////////////////////

/*
 * Get more memory (at the top of the heap) using sbrk, and
 * return a pointer to it.
 */
static
void *
__malloc_sbrk(size_t size)
{
	void *x;

	x = sbrk(size);
	if (x == (void *)-1) {
		return NULL;
	}

	if ((uintptr_t)x != __heaptop) {
		errx(1, "malloc: Internal error - "
		     "heap top moved itself from 0x%lx to 0x%lx",
		     (unsigned long) __heaptop,
		     (unsigned long) (uintptr_t) x);
	}
	__heaptop += size;
	return x;
}

/*
 * Make a new (free) block from the block passed in, leaving size
 * bytes for data in the current block. size must be a multiple of
 * MBLOCKSIZE.
 *
 * Only split if the excess space is at least twice the blocksize -
 * one blocksize to hold a header and one for data.
 */
static
void
__malloc_split(struct mheader *mh, size_t size)
{
	struct mheader *mhnext, *mhnew;
	size_t oldsize;

	if (size % MBLOCKSIZE != 0) {
		errx(1, "malloc: Internal error (size %lu passed to split)",
		     (unsigned long) size);
	}

	if (M_SIZE(mh) - size < 2*MBLOCKSIZE) {
		/* no room */
		return;
	}

	mhnext = M_NEXT(mh);

	oldsize = M_SIZE(mh);
	mh->mh_nextblock = M_MKFIELD(size + MBLOCKSIZE);

	mhnew = M_NEXT(mh);
	if (mhnew==mhnext) {
		errx(1, "malloc: Internal error (split screwed up?)");
	}

	mhnew->mh_prevblock = M_MKFIELD(size + MBLOCKSIZE);
	mhnew->mh_pad = 0;
	mhnew->mh_magic1 = MMAGIC;
	mhnew->mh_nextblock = M_MKFIELD(oldsize - size);
	mhnew->mh_inuse = 0;
	mhnew->mh_magic2 = MMAGIC;

	if (mhnext != (struct mheader *) __heaptop) {
		mhnext->mh_prevblock = mhnew->mh_nextblock;
	}
}

/*
 * malloc itself.
 */
void *
malloc(size_t size)
{
	struct mheader *mh;
	uintptr_t i;
	size_t rightprevblock;
	size_t morespace;
	void *p;

	if (__heapbase==0) {
		__malloc_init();
	}
	if (__heapbase==0 || __heaptop==0 || __heapbase > __heaptop) {
		warnx("malloc: Internal error - local data corrupt");
		errx(1, "malloc: heapbase 0x%lx; heaptop 0x%lx",
		     (unsigned long) __heapbase, (unsigned long) __heaptop);
	}

#ifdef MALLOCDEBUG
	warnx("malloc: about to allocate %lu (0x%lx) bytes",
	      (unsigned long) size, (unsigned long) size);
	__malloc_dump();
#endif

	/* Round size up to an integral number of blocks. */
	size = ((size + MBLOCKSIZE - 1) & ~(size_t)(MBLOCKSIZE-1));

	/*
	 * First-fit search algorithm for available blocks.
	 * Check to make sure the next/previous sizes all agree.
	 */
	rightprevblock = 0;
	mh = NULL;
	for (i=__heapbase; i<__heaptop; i += M_NEXTOFF(mh)) {
		mh = (struct mheader *) i;
		if (!M_OK(mh)) {
			errx(1, "malloc: Heap corrupt; header at 0x%lx"
			     " has bad magic bits",
			     (unsigned long) i);
		}
		if (mh->mh_prevblock != rightprevblock) {
			errx(1, "malloc: Heap corrupt; header at 0x%lx"
			     " has bad previous-block size %lu "
			     "(should be %lu)",
			     (unsigned long) i,
			     (unsigned long) mh->mh_prevblock << MBLOCKSHIFT,
			     (unsigned long) rightprevblock << MBLOCKSHIFT);
		}
		rightprevblock = mh->mh_nextblock;

		/* Can't allocate a block that's in use. */
		if (mh->mh_inuse) {
			continue;
		}

		/* Can't allocate a block that isn't big enough. */
		if (M_SIZE(mh) < size) {
			continue;
		}

		/* Try splitting block. */
		__malloc_split(mh, size);

		/*
		 * Now, allocate.
		 */
		mh->mh_inuse = 1;

#ifdef MALLOCDEBUG
		warnx("malloc: allocating at %p", M_DATA(mh));
		__malloc_dump();
#endif
		return M_DATA(mh);
	}
	if (i!=__heaptop) {
		errx(1, "malloc: Heap corrupt; ran off end");
	}

	/*
	 * Didn't find anything. Expand the heap.
	 *
	 * If the heap is nonempty and the top block (the one mh is
	 * left pointing to after the above loop) is free, we can
	 * expand it. Otherwise we need a new block.
	 */
	if (mh != NULL && !mh->mh_inuse) {
		assert(size > M_SIZE(mh));
		morespace = size - M_SIZE(mh);
	}
	else {
		morespace = MBLOCKSIZE + size;
	}

	/* Round the amount of space we ask for up to a whole page. */
	morespace = PAGE_SIZE * ((morespace + PAGE_SIZE - 1) / PAGE_SIZE);

	p = __malloc_sbrk(morespace);
	if (p == NULL) {
		return NULL;
	}

	if (mh != NULL && !mh->mh_inuse) {
		/* update old header */
		mh->mh_nextblock = M_MKFIELD(M_NEXTOFF(mh) + morespace);
		mh->mh_inuse = 1;
	}
	else {
		/* fill out new header */
		mh = p;
		mh->mh_prevblock = rightprevblock;
		mh->mh_magic1 = MMAGIC;
		mh->mh_magic2 = MMAGIC;
		mh->mh_pad = 0;
		mh->mh_inuse = 1;
		mh->mh_nextblock = M_MKFIELD(morespace);
	}

	/*
	 * Either way, try splitting the block we got as because of
	 * the page rounding it might be quite a bit bigger than we
	 * needed.
	 */
	__malloc_split(mh, size);

#ifdef MALLOCDEBUG
	warnx("malloc: allocating at %p", M_DATA(mh));
	__malloc_dump();
#endif
	return M_DATA(mh);
}

////////////////////////////////////////////////////////////

/*
 * Clear a range of memory with 0xdeadbeef.
 * ptr must be suitably aligned.
 */
static
void
__malloc_deadbeef(void *ptr, size_t size)
{
	uint32_t *x = ptr;
	size_t i, n = size/sizeof(uint32_t);
	for (i=0; i<n; i++) {
		x[i] = 0xdeadbeef;
	}
}

/*
 * Attempt to merge two adjacent blocks (mh below mhnext).
 */
static
void
__malloc_trymerge(struct mheader *mh, struct mheader *mhnext)
{
	struct mheader *mhnextnext;

	if (mh->mh_nextblock != mhnext->mh_prevblock) {
		errx(1, "free: Heap corrupt (%p and %p inconsistent)",
		     mh, mhnext);
	}
	if (mh->mh_inuse || mhnext->mh_inuse) {
		/* can't merge */
		return;
	}

	mhnextnext = M_NEXT(mhnext);

	mh->mh_nextblock = M_MKFIELD(MBLOCKSIZE + M_SIZE(mh) +
				     MBLOCKSIZE + M_SIZE(mhnext));

	if (mhnextnext != (struct mheader *)__heaptop) {
		mhnextnext->mh_prevblock = mh->mh_nextblock;
	}

	/* Deadbeef out the memory used by the now-obsolete header */
	__malloc_deadbeef(mhnext, sizeof(struct mheader));
}

/*
 * The actual free() implementation.
 */
void
free(void *x)
{
	struct mheader *mh, *mhnext, *mhprev;

	if (x==NULL) {
		/* safest practice */
		return;
	}

	/* Consistency check. */
	if (__heapbase==0 || __heaptop==0 || __heapbase > __heaptop) {
		warnx("free: Internal error - local data corrupt");
		errx(1, "free: heapbase 0x%lx; heaptop 0x%lx",
		     (unsigned long) __heapbase, (unsigned long) __heaptop);
	}

	/* Don't allow freeing pointers that aren't on the heap. */
	if ((uintptr_t)x < __heapbase || (uintptr_t)x >= __heaptop) {
		errx(1, "free: Invalid pointer %p freed (out of range)", x);
	}

#ifdef MALLOCDEBUG
	warnx("free: about to free %p", x);
	__malloc_dump();
#endif

	mh = ((struct mheader *)x)-1;
	if (!M_OK(mh)) {
		errx(1, "free: Invalid pointer %p freed (corrupt header)", x);
	}

	if (!mh->mh_inuse) {
		errx(1, "free: Invalid pointer %p freed (already free)", x);
	}

	/* mark it free */
	mh->mh_inuse = 0;

	/* wipe it */
	__malloc_deadbeef(M_DATA(mh), M_SIZE(mh));

	/* Try merging with the block above (but not if we're at the top) */
	mhnext = M_NEXT(mh);
	if (mhnext != (struct mheader *)__heaptop) {
		__malloc_trymerge(mh, mhnext);
	}

	/* Try merging with the block below (but not if we're at the bottom) */
	if (mh != (struct mheader *)__heapbase) {
		mhprev = M_PREV(mh);
		__malloc_trymerge(mhprev, mh);
	}

#ifdef MALLOCDEBUG
	warnx("free: freed %p", x);
	__malloc_dump();
#endif
}