aligned_alloc.c

pebble

/* 
 * Copyright 1999, 2000, 2001, 2002 Lucent Technologies Inc.
 * All Rights Reserved.
 * Information Sciences Research Center, Bell Labs.
 *
 * LUCENT TECHNOLOGIES DOES NOT CLAIM MERCHANTABILITY OF THIS SOFTWARE 
 * OR THE SUITABILITY OF THIS SOFTWARE FOR ANY PARTICULAR PURPOSE. The
 * software is provided "as is" without expressed or implied warranty 
 * of any kind.
 *
 * These notices must be retained in any copies of any part of this
 * software.
 *
 */

/*
 *	Aligned memory management.
 *	All allocated memory segments are contained within a single
 *	page.
 *
 *	Size of allocated area must be less or equal to MAX_FRAG_WORDS
 *	words (slightly less than a page).
 *
 *	This code is NOT thread safe.
 *
 *	Memory allocation uses separate lists, one for each fragment size.
 *	The routine tries first to find a fragement of the right size,
 *	and if it fails, it tries to split the largest available fragment.
 *
 *	Assumption:
 *	This routine is used to allocate only a few sizes of memory
 *	areas. Thus it makes a lot of sense to keep separate free lists,
 *	one for each size.
 *
 *	Caveat: memory reclamation is primitive.
 *	The routine does NOT combine free fragments to a larger one!
 */

#include <string.h>
#include <unistd.h>		/* for sbrk(), etc. */
#include "diag.h"
#include "pebble.h"
#include "mem.h"
#include "portal.h"

typedef	struct mem_frag {	/* memory fragment head */
	uint magic;	/* magic constant for detecting memory corruption */
	int nwords;	/* fragement size in words (integers) */
	int nref;	/* number of references to this area */
	struct mem_frag *next;	/* next fragment in free list */
} MemFrag;

#define	MIN_FRAG_WORDS	(sizeof(MemFrag)/sizeof(int))
#define	MAX_FRAG_WORDS	(PAGESIZE / sizeof(int))
#define	MAGIC		0xdeadbeef

/* free list; one list for each fragment size */
static MemFrag *free_list[MAX_FRAG_WORDS+1];
static int largest_flist = -1;
static int smallest_fragment = MIN_FRAG_WORDS;

void *
aligned_malloc(int size)
{
	int nwords, nbytes;
	MemFrag *p, *start, *new_frag, *split_frag;
	int alloc_bytes, split_nwords;

	DIAG(ALLOC_DIAG, ("aligned_malloc(%d)\n", size));

	if (size == 0)
		return NULL;

	ASSERT((size > 0), ("negative input to aligned_malloc: %d", size));
	nbytes = (size + sizeof(MemFrag) + sizeof(int) - 1) & ~(sizeof(int));
	nwords = nbytes / sizeof(int);
	ASSERT((nwords <= MAX_FRAG_WORDS),
		("input too big for aligned_malloc. nwords=%d", nwords));

	if (nwords < smallest_fragment || smallest_fragment == MIN_FRAG_WORDS)
		smallest_fragment = nwords;

	do {
		/* try to see if we have an exact match */
		if ((p = free_list[nwords]) != NULL) {
			ASSERT((p->magic == MAGIC && p->nwords == nwords),\
				("invalid fragment in free list %p", p));

			/* remove fragment from list */
			free_list[nwords] = p->next;
		} else if (largest_flist > nwords &&
			   (p = free_list[largest_flist]) != NULL) {

			ASSERT((p->magic == MAGIC &&\
				p->nwords == largest_flist),\
				("invalid fragment in free list %p", p));

			/* remove fragment from list */
			free_list[largest_flist] = p->next;
		}

		/* we may have to adjust the largest free list index */
		while (largest_flist >= 0 &&
		       free_list[largest_flist] == NULL)
			largest_flist--;

		if (p == NULL) {
			/* we must allocate a new virtual memory page */
			start = (MemFrag *)sbrk(0);
			alloc_bytes = PAGESIZE - ((int)start & PAGEMASK);
			new_frag = (MemFrag *)sbrk(alloc_bytes);
			
			if ((int)new_frag < 0 || new_frag != start)
				return(NULL);

			/* initialize new fragment */
			new_frag->magic = MAGIC;
			new_frag->nwords = alloc_bytes / sizeof(int);

			/* insert fragment into free list */
			new_frag->next = free_list[new_frag->nwords];
			free_list[new_frag->nwords] = new_frag;
			if (new_frag->nwords > largest_flist)
				largest_flist = new_frag->nwords;
		}
	} while (p == NULL);


	/* found a memory fragment! */
	ASSERT((p->magic == MAGIC && p->nwords >= nwords),\
		 ("invalid fragment in free list %p", p));

	/* should we split it? */
	split_nwords = p->nwords - nwords;
	if (split_nwords >= smallest_fragment) {
		/* truncate fragment */
		p->nwords = nwords;

		/* create a split fragment */
		split_frag = (MemFrag *)((char *)p + nwords * sizeof(int));
		split_frag->magic = MAGIC;
		split_frag->nwords = split_nwords;

		/* insert new fragment into the free list */
		split_frag->next = free_list[split_nwords];
		free_list[split_nwords] = split_frag;
		if (split_nwords > largest_flist)
			largest_flist = split_nwords;
	}

	p->nref = 1;

	DIAG(ALLOC_DIAG, ("aligned_malloc(%d) returns %08x\n", size, (uint)(p+1)));

	return (void *)(p+1);
}


void
aligned_incref(void *p)
{
	MemFrag *frag;

	ASSERT((p != NULL), ("invalid input to aligned_incref"));
	frag = (MemFrag *)((char *)p - sizeof(MemFrag));
	ASSERT((frag->magic == MAGIC && frag->nref >= 0),\
		("invalid memory fragment %p", p));
	frag->nref++;
}

void
aligned_decref(void *p)
{
	MemFrag *frag;

	ASSERT((p != NULL), ("invalid input to aligned_decref"));
	frag = (MemFrag *)((char *)p - sizeof(MemFrag));
	ASSERT((frag->magic == MAGIC && frag->nref > 0),\
		("invalid memory fragment %p", p));
	frag->nref--;

	if (frag->nref > 0)
		return;

	/* reclaim memory fragment */
	ASSERT((frag->nwords > 0 && frag->nwords <= MAX_FRAG_WORDS),\
		("invalid memory fragment for reclamation %p", frag));

	DIAG(ALLOC_DIAG,
		("aligned_decref reclaiming fragment %p\n", frag));
	frag->next = free_list[frag->nwords];
	free_list[frag->nwords] = frag;
	if (frag->nwords > largest_flist)
		largest_flist = frag->nwords;
}