Initial Revision

1 files changed, 274 insertions, 0 deletions

diff --git a/serverboot/kalloc.c b/serverboot/kalloc.c
new file mode 100644
index 00000000..80438738
--- /dev/null
+++ b/serverboot/kalloc.c
@@ -0,0 +1,274 @@
+/*
+ * Mach Operating System
+ * Copyright (c) 1993-1987 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.
+ */
+/*
+ *	File:	kern/kalloc.c
+ *	Author:	Avadis Tevanian, Jr.
+ *	Date:	1985
+ *
+ *	General kernel memory allocator.  This allocator is designed
+ *	to be used by the kernel to manage dynamic memory fast.
+ */
+
+#include <mach.h>
+#include <cthreads.h>		/* for spin locks */
+
+#define	DEBUG
+
+/*
+ *	All allocations of size less than kalloc_max are rounded to the
+ *	next highest power of 2.
+ */
+vm_size_t	kalloc_max;		/* max before we use vm_allocate */
+#define		MINSIZE	4		/* minimum allocation size */
+
+struct free_list {
+	spin_lock_t	lock;
+	vm_offset_t	head;		/* head of free list */
+#ifdef	DEBUG
+	int		count;
+#endif	/*DEBUG*/
+};
+
+#define	KLIST_MAX	13
+					/* sizes: 4, 8, 16, 32, 64,
+						128, 256, 512, 1024,
+						2048, 4096, 8192, 16384 */
+struct free_list	kfree_list[KLIST_MAX];
+
+spin_lock_t		kget_space_lock;
+vm_offset_t		kalloc_next_space = 0;
+vm_offset_t		kalloc_end_of_space = 0;
+
+vm_size_t		kalloc_wasted_space = 0;
+
+boolean_t		kalloc_initialized = FALSE;
+
+/*
+ *	Initialize the memory allocator.  This should be called only
+ *	once on a system wide basis (i.e. first processor to get here
+ *	does the initialization).
+ *
+ *	This initializes all of the zones.
+ */
+
+void kalloc_init(void)
+{
+	vm_offset_t min, max;
+	vm_size_t size;
+	register int i;
+
+	/*
+	 * Support free lists for items up to vm_page_size or
+	 * 16Kbytes, whichever is less.
+	 */
+
+	if (vm_page_size > 16*1024)
+		kalloc_max = 16*1024;
+	else
+		kalloc_max = vm_page_size;
+
+	for (i = 0; i < KLIST_MAX; i++) {
+	    spin_lock_init(&kfree_list[i].lock);
+	    kfree_list[i].head = 0;
+	}
+	spin_lock_init(&kget_space_lock);
+
+	/*
+	 * Do not allocate memory at address 0.
+	 */
+	kalloc_next_space = vm_page_size;
+	kalloc_end_of_space = vm_page_size;
+}
+
+/*
+ * Contiguous space allocator for items of less than a page size.
+ */
+vm_offset_t kget_space(vm_offset_t size)
+{
+	vm_size_t	space_to_add;
+	vm_offset_t	new_space = 0;
+	vm_offset_t	addr;
+
+	spin_lock(&kget_space_lock);
+	while (kalloc_next_space + size > kalloc_end_of_space) {
+	    /*
+	     * Add at least one page to allocation area.
+	     */
+	    space_to_add = round_page(size);
+
+	    if (new_space == 0) {
+		/*
+		 * Unlock and allocate memory.
+		 * Try to make it contiguous with the last
+		 * allocation area.
+		 */
+		spin_unlock(&kget_space_lock);
+
+		new_space = kalloc_end_of_space;
+		if (vm_map(mach_task_self(),
+			   &new_space, space_to_add, (vm_offset_t) 0, TRUE,
+			   MEMORY_OBJECT_NULL, (vm_offset_t) 0, FALSE,
+			   VM_PROT_DEFAULT, VM_PROT_ALL, VM_INHERIT_DEFAULT)
+			!= KERN_SUCCESS)
+		    return 0;
+		wire_memory(new_space, space_to_add,
+			    VM_PROT_READ|VM_PROT_WRITE);
+		spin_lock(&kget_space_lock);
+		continue;
+	    }
+
+	    /*
+	     * Memory was allocated in a previous iteration.
+	     * Check whether the new region is contiguous with the
+	     * old one.
+	     */
+	    if (new_space != kalloc_end_of_space) {
+		/*
+		 * Throw away the remainder of the old space,
+		 * and start a new one.
+		 */
+		kalloc_wasted_space +=
+			kalloc_end_of_space - kalloc_next_space;
+		kalloc_next_space = new_space;
+	    }
+	    kalloc_end_of_space = new_space + space_to_add;
+
+	    new_space = 0;
+	}
+
+	addr = kalloc_next_space;
+	kalloc_next_space += size;
+	spin_unlock(&kget_space_lock);
+
+	if (new_space != 0)
+	    (void) vm_deallocate(mach_task_self(), new_space, space_to_add);
+
+	return addr;
+}
+
+void *kalloc(vm_size_t size)
+{
+	register vm_size_t allocsize;
+	vm_offset_t addr;
+	register struct free_list *fl;
+
+	if (!kalloc_initialized) {
+	    kalloc_init();
+	    kalloc_initialized = TRUE;
+	}
+
+	/* compute the size of the block that we will actually allocate */
+
+	allocsize = size;
+	if (size < kalloc_max) {
+	    allocsize = MINSIZE;
+	    fl = kfree_list;
+	    while (allocsize < size) {
+		allocsize <<= 1;
+		fl++;
+	    }
+	}
+
+	/*
+	 * If our size is still small enough, check the queue for that size
+	 * and allocate.
+	 */
+
+	if (allocsize < kalloc_max) {
+	    spin_lock(&fl->lock);
+	    if ((addr = fl->head) != 0) {
+		fl->head = *(vm_offset_t *)addr;
+#ifdef	DEBUG
+		fl->count--;
+#endif
+		spin_unlock(&fl->lock);
+	    }
+	    else {
+		spin_unlock(&fl->lock);
+		addr = kget_space(allocsize);
+	    }
+	}
+	else {
+	    if (vm_allocate(mach_task_self(), &addr, allocsize, TRUE)
+			!= KERN_SUCCESS)
+		addr = 0;
+	}
+	return (void *) addr;
+}
+
+void
+kfree(	void *data,
+	vm_size_t size)
+{
+	register vm_size_t freesize;
+	register struct free_list *fl;
+
+	freesize = size;
+	if (size < kalloc_max) {
+	    freesize = MINSIZE;
+	    fl = kfree_list;
+	    while (freesize < size) {
+		freesize <<= 1;
+		fl++;
+	    }
+	}
+
+	if (freesize < kalloc_max) {
+	    spin_lock(&fl->lock);
+	    *(vm_offset_t *)data = fl->head;
+	    fl->head = (vm_offset_t) data;
+#ifdef	DEBUG
+	    fl->count++;
+#endif
+	    spin_unlock(&fl->lock);
+	}
+	else {
+	    (void) vm_deallocate(mach_task_self(), (vm_offset_t)data, freesize);
+	}
+}
+
+void *malloc(vm_size_t size)
+{
+	return (void *)kalloc(size);
+}
+
+void free(void *addr)
+{
+  /* Just ignore harmless attempts at cleanliness.  */
+  /*	panic("free not implemented"); */
+}
+
+void malloc_fork_prepare()
+{
+}
+
+void malloc_fork_parent()
+{
+}
+
+void malloc_fork_child()
+{
+}