#include <stdlib.h>

#include <string.h>

#include "hurdmalloc.h"		/* XXX see that file */

#include <mach.h>

#define vm_allocate __vm_allocate

#define vm_page_size __vm_page_size

/*

 * Mach Operating System

 * Copyright (c) 1991,1990,1989 Carnegie Mellon University

 * All Rights Reserved.

 *

 * Permission to use, copy, modify and distribute this software and its

 * documentation is hereby granted, provided that both the copyright

 * notice and this permission notice appear in all copies of the

 * software, derivative works or modified versions, and any portions

 * thereof, and that both notices appear in supporting documentation.

 *

 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"

 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR

 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.

 *

 * Carnegie Mellon requests users of this software to return to

 *

 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU

 *  School of Computer Science

 *  Carnegie Mellon University

 *  Pittsburgh PA 15213-3890

 *

 * any improvements or extensions that they make and grant Carnegie Mellon

 * the rights to redistribute these changes.

 */

/*

 * (pre-GNU) HISTORY

 *

 * Revision 2.7  91/05/14  17:57:34  mrt

 * 	Correcting copyright

 *

 * Revision 2.6  91/02/14  14:20:26  mrt

 * 	Added new Mach copyright

 * 	[91/02/13  12:41:21  mrt]

 *

 * Revision 2.5  90/11/05  14:37:33  rpd

 * 	Added malloc_fork* code.

 * 	[90/11/02            rwd]

 *

 * 	Add spin_lock_t.

 * 	[90/10/31            rwd]

 *

 * Revision 2.4  90/08/07  14:31:28  rpd

 * 	Removed RCS keyword nonsense.

 *

 * Revision 2.3  90/06/02  15:14:00  rpd

 * 	Converted to new IPC.

 * 	[90/03/20  20:56:57  rpd]

 *

 * Revision 2.2  89/12/08  19:53:59  rwd

 * 	Removed conditionals.

 * 	[89/10/23            rwd]

 *

 * Revision 2.1  89/08/03  17:09:46  rwd

 * Created.

 *

 *

 * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University

 *	Changed realloc() to copy min(old size, new size) bytes.

 *	Bug found by Mike Kupfer at Olivetti.

 */

/*

 * 	File: 	malloc.c

 *	Author: Eric Cooper, Carnegie Mellon University

 *	Date:	July, 1988

 *

 * 	Memory allocator for use with multiple threads.

 */

#include <assert.h>

#include <cthreads.h>

#define MCHECK

/*

 * Structure of memory block header.

 * When free, next points to next block on free list.

 * When allocated, fl points to free list.

 * Size of header is 4 bytes, so minimum usable block size is 8 bytes.

 */

#define CHECK_BUSY  0x8a3c743e

#define CHECK_FREE  0x66688b92

#ifdef MCHECK

typedef struct header {

  long check;

  union {

    struct header *next;

    struct free_list *fl;

  } u;

} *header_t;

#define HEADER_SIZE sizeof (struct header)

#define HEADER_NEXT(h) ((h)->u.next)

#define HEADER_FREE(h) ((h)->u.fl)

#define HEADER_CHECK(h) ((h)->check)

#define MIN_SIZE	16

#define LOG2_MIN_SIZE	4

#else /* ! MCHECK */

typedef union header {

	union header *next;

	struct free_list *fl;

} *header_t;

#define HEADER_SIZE sizeof (union header)

#define HEADER_NEXT(h) ((h)->next)

#define HEADER_FREE(h) ((h)->fl)

#define MIN_SIZE	8	/* minimum block size */

#define LOG2_MIN_SIZE	3

#endif /* MCHECK */

typedef struct free_list {

	spin_lock_t lock;	/* spin lock for mutual exclusion */

	header_t head;		/* head of free list for this size */

#ifdef	DEBUG

	int in_use;		/* # mallocs - # frees */

#endif	/* DEBUG */

} *free_list_t;

/*

 * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)

 * including header.  Smallest block size is MIN_SIZE, with MIN_SIZE -

 * HEADER_SIZE bytes available to user.  Size argument to malloc is a signed

 * integer for sanity checking, so largest block size is 2^31.

 */

#define NBUCKETS	29

static struct free_list malloc_free_list[NBUCKETS];

/* Initialization just sets everything to zero, but might be necessary on a

   machine where spin_lock_init does otherwise, and is necessary when

   running an executable that was written by something like Emacs's unexec.

   It preserves the values of data variables like malloc_free_list, but

   does not save the vm_allocate'd space allocated by this malloc.  */

static void

malloc_init (void)

{

  int i;

  for (i = 0; i < NBUCKETS; ++i)

    {

      spin_lock_init (&malloc_free_list[i].lock);

      malloc_free_list[i].head = NULL;

#ifdef DEBUG

      malloc_free_list[i].in_use = 0;

#endif

    }

  /* This not only suppresses a `defined but not used' warning,

     but it is ABSOLUTELY NECESSARY to avoid the hyperclever

     compiler from "optimizing out" the entire function!  */

  (void) &malloc_init;

}

static void

more_memory(int size, free_list_t fl)

{

	int amount;

	int n;

	vm_address_t where;

	header_t h;

	kern_return_t r;

	if (size <= vm_page_size) {

		amount = vm_page_size;

		n = vm_page_size / size;

		/* We lose vm_page_size - n*size bytes here.  */

	} else {

		amount = size;

		n = 1;

	}

	r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);

	assert_perror (r);

	h = (header_t) where;

	do {

		HEADER_NEXT (h) = fl->head;

#ifdef MCHECK

		HEADER_CHECK (h) = CHECK_FREE;

#endif

		fl->head = h;

		h = (header_t) ((char *) h + size);

	} while (--n != 0);

}

/* Declaration changed to standard one for GNU.  */

void *

malloc (size_t size)

{

	int i, n;

	free_list_t fl;

	header_t h;

	if ((int) size < 0)		/* sanity check */

		return 0;

	size += HEADER_SIZE;

	/*

	 * Find smallest power-of-two block size

	 * big enough to hold requested size plus header.

	 */

	i = 0;

	n = MIN_SIZE;

	while (n < size) {

		i += 1;

		n <<= 1;

	}

	ASSERT(i < NBUCKETS);

	fl = &malloc_free_list[i];

	spin_lock(&fl->lock);

	h = fl->head;

	if (h == 0) {

		/*

		 * Free list is empty;

		 * allocate more blocks.

		 */

		more_memory(n, fl);

		h = fl->head;

		if (h == 0) {

			/*

			 * Allocation failed.

			 */

			spin_unlock(&fl->lock);

			return 0;

		}

	}

	/*

	 * Pop block from free list.

	 */

	fl->head = HEADER_NEXT (h);

#ifdef MCHECK

	assert (HEADER_CHECK (h) == CHECK_FREE);

	HEADER_CHECK (h) = CHECK_BUSY;

#endif

#ifdef	DEBUG

	fl->in_use += 1;

#endif	/* DEBUG */

	spin_unlock(&fl->lock);

	/*

	 * Store free list pointer in block header

	 * so we can figure out where it goes

	 * at free() time.

	 */

	HEADER_FREE (h) = fl;

	/*

	 * Return pointer past the block header.

	 */

	return ((char *) h) + HEADER_SIZE;

}

/* Declaration changed to standard one for GNU.  */

void

free (void *base)

{

	header_t h;

	free_list_t fl;

	int i;

	if (base == 0)

		return;

	/*

	 * Find free list for block.

	 */

	h = (header_t) (base - HEADER_SIZE);

#ifdef MCHECK

	assert (HEADER_CHECK (h) == CHECK_BUSY);

#endif

	fl = HEADER_FREE (h);

	i = fl - malloc_free_list;

	/*

	 * Sanity checks.

	 */

	if (i < 0 || i >= NBUCKETS) {

		ASSERT(0 <= i && i < NBUCKETS);

		return;

	}

	if (fl != &malloc_free_list[i]) {

		ASSERT(fl == &malloc_free_list[i]);

		return;

	}

	/*

	 * Push block on free list.

	 */

	spin_lock(&fl->lock);

	HEADER_NEXT (h) = fl->head;

#ifdef MCHECK

	HEADER_CHECK (h) = CHECK_FREE;

#endif

	fl->head = h;

#ifdef	DEBUG

	fl->in_use -= 1;

#endif	/* DEBUG */

	spin_unlock(&fl->lock);

	return;

}

/* Declaration changed to standard one for GNU.  */

void *

realloc (void *old_base, size_t new_size)

{

	header_t h;

	free_list_t fl;

	int i;

	unsigned int old_size;

	char *new_base;

	if (old_base == 0)

	  return malloc (new_size);

	/*

	 * Find size of old block.

	 */

	h = (header_t) (old_base - HEADER_SIZE);

#ifdef MCHECK

	assert (HEADER_CHECK (h) == CHECK_BUSY);

#endif

	fl = HEADER_FREE (h);

	i = fl - malloc_free_list;

	/*

	 * Sanity checks.

	 */

	if (i < 0 || i >= NBUCKETS) {

		ASSERT(0 <= i && i < NBUCKETS);

		return 0;

	}

	if (fl != &malloc_free_list[i]) {

		ASSERT(fl == &malloc_free_list[i]);

		return 0;

	}

	/*

	 * Free list with index i contains blocks of size

	 * 2 ^ (i + * LOG2_MIN_SIZE) including header.

	 */

	old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;

	if (new_size <= old_size

	    && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))

	  /* The new size still fits in the same block, and wouldn't fit in

	     the next smaller block!  */

	  return old_base;

	/*

	 * Allocate new block, copy old bytes, and free old block.

	 */

	new_base = malloc(new_size);

	if (new_base)

	  memcpy (new_base, old_base,

		  (int) (old_size < new_size ? old_size : new_size));

	if (new_base || new_size == 0)

	  /* Free OLD_BASE, but only if the malloc didn't fail.  */

	  free (old_base);

	return new_base;

}

#ifdef	DEBUG

void

print_malloc_free_list (void)

{

	int i, size;

	free_list_t fl;

	int n;

	header_t h;

	int total_used = 0;

	int total_free = 0;

	fprintf(stderr, "      Size     In Use       Free      Total\n");

	for (i = 0, size = MIN_SIZE, fl = malloc_free_list;

	     i < NBUCKETS;

	     i += 1, size <<= 1, fl += 1) {

		spin_lock(&fl->lock);

		if (fl->in_use != 0 || fl->head != 0) {

			total_used += fl->in_use * size;

			for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)

				;

			total_free += n * size;

			fprintf(stderr, "%10d %10d %10d %10d\n",

				size, fl->in_use, n, fl->in_use + n);

		}

		spin_unlock(&fl->lock);

	}

	fprintf(stderr, " all sizes %10d %10d %10d\n",

		total_used, total_free, total_used + total_free);

}

#endif	/* DEBUG */

void

_hurd_malloc_fork_prepare(void)

/*

 * Prepare the malloc module for a fork by insuring that no thread is in a

 * malloc critical section.

 */

{

    int i;

    for (i = 0; i < NBUCKETS; i++) {

	spin_lock(&malloc_free_list[i].lock);

    }

}

void

_hurd_malloc_fork_parent(void)

/*

 * Called in the parent process after a fork() to resume normal operation.

 */

{

    int i;

    for (i = NBUCKETS-1; i >= 0; i--) {

	spin_unlock(&malloc_free_list[i].lock);

    }

}

void

_hurd_malloc_fork_child(void)

/*

 * Called in the child process after a fork() to resume normal operation.

 */

{

    int i;

    for (i = NBUCKETS-1; i >= 0; i--) {

	spin_unlock(&malloc_free_list[i].lock);

    }

}

text_set_element (_hurd_preinit_hook, malloc_init);