4 #include "hurdmalloc.h" /* XXX see that file */
7 #define vm_allocate __vm_allocate
8 #define vm_page_size __vm_page_size
11 * Mach Operating System
12 * Copyright (c) 1991,1990,1989 Carnegie Mellon University
13 * All Rights Reserved.
15 * Permission to use, copy, modify and distribute this software and its
16 * documentation is hereby granted, provided that both the copyright
17 * notice and this permission notice appear in all copies of the
18 * software, derivative works or modified versions, and any portions
19 * thereof, and that both notices appear in supporting documentation.
21 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
22 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
23 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
25 * Carnegie Mellon requests users of this software to return to
27 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
28 * School of Computer Science
29 * Carnegie Mellon University
30 * Pittsburgh PA 15213-3890
32 * any improvements or extensions that they make and grant Carnegie Mellon
33 * the rights to redistribute these changes.
38 * Revision 2.7 91/05/14 17:57:34 mrt
39 * Correcting copyright
41 * Revision 2.6 91/02/14 14:20:26 mrt
42 * Added new Mach copyright
43 * [91/02/13 12:41:21 mrt]
45 * Revision 2.5 90/11/05 14:37:33 rpd
46 * Added malloc_fork* code.
52 * Revision 2.4 90/08/07 14:31:28 rpd
53 * Removed RCS keyword nonsense.
55 * Revision 2.3 90/06/02 15:14:00 rpd
56 * Converted to new IPC.
57 * [90/03/20 20:56:57 rpd]
59 * Revision 2.2 89/12/08 19:53:59 rwd
60 * Removed conditionals.
63 * Revision 2.1 89/08/03 17:09:46 rwd
67 * 13-Sep-88 Eric Cooper (ecc) at Carnegie Mellon University
68 * Changed realloc() to copy min(old size, new size) bytes.
69 * Bug found by Mike Kupfer at Olivetti.
73 * Author: Eric Cooper, Carnegie Mellon University
76 * Memory allocator for use with multiple threads.
87 * Structure of memory block header.
88 * When free, next points to next block on free list.
89 * When allocated, fl points to free list.
90 * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
93 #define CHECK_BUSY 0x8a3c743e
94 #define CHECK_FREE 0x66688b92
98 typedef struct header {
102 struct free_list *fl;
106 #define HEADER_SIZE sizeof (struct header)
107 #define HEADER_NEXT(h) ((h)->u.next)
108 #define HEADER_FREE(h) ((h)->u.fl)
109 #define HEADER_CHECK(h) ((h)->check)
111 #define LOG2_MIN_SIZE 4
115 typedef union header {
117 struct free_list *fl;
120 #define HEADER_SIZE sizeof (union header)
121 #define HEADER_NEXT(h) ((h)->next)
122 #define HEADER_FREE(h) ((h)->fl)
123 #define MIN_SIZE 8 /* minimum block size */
124 #define LOG2_MIN_SIZE 3
128 typedef struct free_list {
129 spin_lock_t lock; /* spin lock for mutual exclusion */
130 header_t head; /* head of free list for this size */
132 int in_use; /* # mallocs - # frees */
137 * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
138 * including header. Smallest block size is MIN_SIZE, with MIN_SIZE -
139 * HEADER_SIZE bytes available to user. Size argument to malloc is a signed
140 * integer for sanity checking, so largest block size is 2^31.
144 static struct free_list malloc_free_list[NBUCKETS];
146 /* Initialization just sets everything to zero, but might be necessary on a
147 machine where spin_lock_init does otherwise, and is necessary when
148 running an executable that was written by something like Emacs's unexec.
149 It preserves the values of data variables like malloc_free_list, but
150 does not save the vm_allocate'd space allocated by this malloc. */
156 for (i = 0; i < NBUCKETS; ++i)
158 spin_lock_init (&malloc_free_list[i].lock);
159 malloc_free_list[i].head = NULL;
161 malloc_free_list[i].in_use = 0;
165 /* This not only suppresses a `defined but not used' warning,
166 but it is ABSOLUTELY NECESSARY to avoid the hyperclever
167 compiler from "optimizing out" the entire function! */
172 more_memory(int size, free_list_t fl)
180 if (size <= vm_page_size) {
181 amount = vm_page_size;
182 n = vm_page_size / size;
183 /* We lose vm_page_size - n*size bytes here. */
189 r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
192 h = (header_t) where;
194 HEADER_NEXT (h) = fl->head;
196 HEADER_CHECK (h) = CHECK_FREE;
199 h = (header_t) ((char *) h + size);
203 /* Declaration changed to standard one for GNU. */
206 register size_t size;
209 register free_list_t fl;
212 if ((int) size < 0) /* sanity check */
216 * Find smallest power-of-two block size
217 * big enough to hold requested size plus header.
225 ASSERT(i < NBUCKETS);
226 fl = &malloc_free_list[i];
227 spin_lock(&fl->lock);
231 * Free list is empty;
232 * allocate more blocks.
240 spin_unlock(&fl->lock);
245 * Pop block from free list.
247 fl->head = HEADER_NEXT (h);
250 assert (HEADER_CHECK (h) == CHECK_FREE);
251 HEADER_CHECK (h) = CHECK_BUSY;
257 spin_unlock(&fl->lock);
259 * Store free list pointer in block header
260 * so we can figure out where it goes
263 HEADER_FREE (h) = fl;
265 * Return pointer past the block header.
267 return ((char *) h) + HEADER_SIZE;
270 /* Declaration changed to standard one for GNU. */
276 register free_list_t fl;
282 * Find free list for block.
284 h = (header_t) (base - HEADER_SIZE);
287 assert (HEADER_CHECK (h) == CHECK_BUSY);
290 fl = HEADER_FREE (h);
291 i = fl - malloc_free_list;
295 if (i < 0 || i >= NBUCKETS) {
296 ASSERT(0 <= i && i < NBUCKETS);
299 if (fl != &malloc_free_list[i]) {
300 ASSERT(fl == &malloc_free_list[i]);
304 * Push block on free list.
306 spin_lock(&fl->lock);
307 HEADER_NEXT (h) = fl->head;
309 HEADER_CHECK (h) = CHECK_FREE;
315 spin_unlock(&fl->lock);
319 /* Declaration changed to standard one for GNU. */
321 realloc(old_base, new_size)
326 register free_list_t fl;
328 unsigned int old_size;
332 return malloc (new_size);
335 * Find size of old block.
337 h = (header_t) (old_base - HEADER_SIZE);
339 assert (HEADER_CHECK (h) == CHECK_BUSY);
341 fl = HEADER_FREE (h);
342 i = fl - malloc_free_list;
346 if (i < 0 || i >= NBUCKETS) {
347 ASSERT(0 <= i && i < NBUCKETS);
350 if (fl != &malloc_free_list[i]) {
351 ASSERT(fl == &malloc_free_list[i]);
355 * Free list with index i contains blocks of size
356 * 2 ^ (i + * LOG2_MIN_SIZE) including header.
358 old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
360 if (new_size <= old_size
361 && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
362 /* The new size still fits in the same block, and wouldn't fit in
363 the next smaller block! */
367 * Allocate new block, copy old bytes, and free old block.
369 new_base = malloc(new_size);
371 memcpy (new_base, old_base,
372 (int) (old_size < new_size ? old_size : new_size));
374 if (new_base || new_size == 0)
375 /* Free OLD_BASE, but only if the malloc didn't fail. */
383 print_malloc_free_list()
385 register int i, size;
386 register free_list_t fl;
392 fprintf(stderr, " Size In Use Free Total\n");
393 for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
395 i += 1, size <<= 1, fl += 1) {
396 spin_lock(&fl->lock);
397 if (fl->in_use != 0 || fl->head != 0) {
398 total_used += fl->in_use * size;
399 for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
401 total_free += n * size;
402 fprintf(stderr, "%10d %10d %10d %10d\n",
403 size, fl->in_use, n, fl->in_use + n);
405 spin_unlock(&fl->lock);
407 fprintf(stderr, " all sizes %10d %10d %10d\n",
408 total_used, total_free, total_used + total_free);
413 malloc_fork_prepare(void)
415 * Prepare the malloc module for a fork by insuring that no thread is in a
416 * malloc critical section.
421 for (i = 0; i < NBUCKETS; i++) {
422 spin_lock(&malloc_free_list[i].lock);
427 malloc_fork_parent(void)
429 * Called in the parent process after a fork() to resume normal operation.
434 for (i = NBUCKETS-1; i >= 0; i--) {
435 spin_unlock(&malloc_free_list[i].lock);
440 malloc_fork_child(void)
442 * Called in the child process after a fork() to resume normal operation.
447 for (i = NBUCKETS-1; i >= 0; i--) {
448 spin_unlock(&malloc_free_list[i].lock);
453 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
454 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
455 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
456 text_set_element (_hurd_preinit_hook, malloc_init);