summaryrefslogtreecommitdiff
path: root/serverboot/kalloc.c
diff options
context:
space:
mode:
authorThomas Bushnell <thomas@gnu.org>1997-04-03 23:28:32 +0000
committerThomas Bushnell <thomas@gnu.org>1997-04-03 23:28:32 +0000
commit3dd031e1f1571f5b60409c17efe90cc51d51a25c (patch)
tree3491c55317bb9976413ca314a11d35d2808753f2 /serverboot/kalloc.c
parent6812102eb13b3c58c79f42f6a6f5c5081f8dfcad (diff)
Initial Revision
Diffstat (limited to 'serverboot/kalloc.c')
-rw-r--r--serverboot/kalloc.c274
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()
+{
+}