diff options
Diffstat (limited to 'REORG.TODO/hurd/hurdmalloc.c')
| -rw-r--r-- | REORG.TODO/hurd/hurdmalloc.c | 449 |
1 files changed, 449 insertions, 0 deletions
diff --git a/REORG.TODO/hurd/hurdmalloc.c b/REORG.TODO/hurd/hurdmalloc.c new file mode 100644 index 0000000000..65fb959d84 --- /dev/null +++ b/REORG.TODO/hurd/hurdmalloc.c @@ -0,0 +1,449 @@ +#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); |