/* malloc.c -- malloc and free implementations and a test program */

/* Author:  Douglas W. Jones, University of Iowa Department of Computer Science
 * Date:    Aug. 7, 2019
 * Copyleft: This is free code, make of it what you will at your own risk,
 *           at no cost, but please retain the attribution to the above-
 *           mentioned author when you pass this to others or derive other
 *           code from it.
 *
 * Purpose:  To produce a small heap manager with the following properties:
 *           -- the simplest possible data structure
 *           -- first-fit allocation
 *           -- blocks aligned to the sizeof( void * ), whatever that may be
 *           -- a heap that grows naturally from high memory toward low memory
 *              (therefore suitable for machines where the stack grows up)
 *           -- lazy merger of free blocks
 *           -- try to keep the heap compact, so searches for free space
 *              always begin at the top of the heap
 *           -- speed is not an issue
 *           -- to produce a prototype for translation to assembly language
 *
 *           A consequence of the above is that the heap will tend to sort
 *           itself over time, with small blocks and free-space fragments
 *           accumulating at the top of the heap and large ones accumulate
 *           at the bottom (toward the stack).
 */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

/* roundup(x) increases x (an integer) to the next aligned address
 * unless it is already aligned
 */
#define roundup(x) (((x) + (sizeof( void * ) - 1)) & -sizeof( void * ))

/* each block on the heap is described by the tag at its lower end.
 * There is no separate free list.
 */
struct tag {
	struct tag * below; /* always points down or NULL */
	int state;          /* 0 = free, 1 = in use */
};
/* note -- because the pointer in each tag is aligned, its least-significant
	bit is available to store the state.  The code given here does not
	apply this optimization, but can as much as halve the effective tag
	size, so this optimization is particularly desirable if there will
	be many small objects on the heap */

/* The heap, which could as easily pulled from sbrk or mmap, but a statically
 * allocated array suffices for demo and testing purposes.
 */
struct tag heap[1000];
struct tag * const heaptop = &heap[999]; /* the address of the topmost tag */
struct tag * const heapbase = &heap[0];  /* the address of the bottommost tag */
/* note -- Here, we assume that the compiler will guarantee that heap[999] is
	aligned; heapbase is used only to detect the heap-full condition,
	while heaptop is the start of every search for a free block.
	The default zeroing of newly allocated global memory sets
	heaptop->below = NULL ad heaptop->state to free. */

/* milloc implements the spec for malloc, renamed because malloc is a builtin
 */
void * milloc( unsigned int size ) {
	struct tag * high = heaptop; /* tag at top of heap */
	struct tag * low;   /* block below high */
	struct tag * lower; /* block below low */
	struct tag * new;   /* new block */

	size = roundup(size + sizeof( struct tag ));
	/* size rounded up to word with space for tag */

	for (;;) { /* all exits from this loop are by break or return */
		low = high->below;

		if (low == NULL) { /* end of heap */
			/* extend heap in order to allocate */
			new = (struct tag *)((uintptr_t)high - size);
			if (new < heapbase) return NULL;
			high->below = new;
			new->below = NULL;
			break; /* go tag new as used then return it */
		}

		if (low->state) { /* this block is in use */
			high = low; /* walk onward */
			continue;
		}
		lower = low->below;

		/* low refers to a free block, lower is below it
		   new is candidate address of a new block */
		new = (struct tag *)((uintptr_t)high - size);

		/* try to merge free blocks until allocate is possible */
		while (new < low) {
			lower = low->below;
			if (lower == NULL) { /* end of heap */
				break; /* merger not possible */
			}
			if (lower->state) { /* block is in use */
				break; /* merger not possible */
			}
			/* lower is free block, merge low and lower */
			high->below = lower;
			low = lower;
		}

		/* try to split oversized free block */
		struct tag * limit; /* used only in following it statement */
		limit = (struct tag *)((uintptr_t)low + sizeof( struct tag ));
		if (new >= limit) { /* split the block */
			high->below = new;
			new->below = low;
			break; /* go tag new as used then return it */
		}
		if (new >= low) { /* no split possible */
			new = low;
			break; /* go tag new as used then return it */
		}

		/* block not big enough */
		high = low; /* walk onward */
	} /* end of loop walking down list */

	/* we only get here with new defined! */
	new->state = 1; /* mark as in use */

	/* the user's pointer refers to the address just after the tag */
	return (void *)((uintptr_t)new + sizeof( struct tag ));
}

/* frie implements the spec for free, renamed because free is a builtin
 */
void frie( void * p ) {
	/* the tag is just before the user's pointer */
	struct tag * old = (struct tag *)((uintptr_t)p - sizeof( struct tag ));

	old->state = 0; /* mark as free */

	/* job done because this is lazy, with mergers done in allocate */
}

/* main program:  Test the heap by repeatedly and randomly allocating and
 * deallocating memory, scribbling on each allocated block and then checking
 * that the scribbles have not been defaced by the heap manager immedately 
 * before each deallocation.  It halts when it detects an error, so it should
 * run forever with a correct heap implementation.  On each iteration, it
 * prints the current load (number of bytes allocated) and the allocate or
 * deallocate action it takes.
 */
int main() {
	int * a[100]; /* the set of pointers to blocks
			 on average, half of them will be NULL */
	int i;
	int load = 0;

	/* initialization */
	for (i = 0; i < 100; i++) a[i] = NULL;

	/* the main test loop */
	for (;;) { /* forever until failure */

		i = random() % 100; /* pick a block to allocate or deallocate */

		printf( "i =%3d ", i );
		if (a[i] == NULL) { /* try to allocate it */
			int j = (random() % 90) + 1;
			int * k = milloc( j * sizeof( int ) );
			a[i] = k;
			if (k != NULL) { /* allocate sucessful */
				load = load + (j * sizeof( int ));
				printf( " load =%5d ", load );

				while (j > 0) { /* scribble on it */
					*k = j;
					k++;
					j = j - 1;
				}
				puts( "Allocated successfully" );

			} else { /* allocate unsuccessful */
				printf( " load =%5d ", load );
				puts( "Allocate returned NULL *************" );
			}

		} else { /* deallocate the block */
			int * k = a[i];
			int j = *k;
			load = load - (j * sizeof( int ));
			printf( " load =%5d ", load );

			while (j > 0) { /* first, check for intact scribble */
				if (*k != j) {
					puts( "ERROR! Garbled block!" );
					return 1;
				}
				k++;
				j = j - 1;
			}
			frie( a[i] );
			puts( "Deallocated" );
			a[i] = NULL;
		}
	}
	return 0; /* this never happens */
}