4 #define bcopy(s,d,n) memcpy ((d), (s), (n)) /* No overlap handling. */
6 #include "hurdmalloc.h" /* XXX see that file */
9 #define vm_allocate __vm_allocate
10 #define vm_page_size __vm_page_size
13 * Mach Operating System
14 * Copyright (c) 1991,1990,1989 Carnegie Mellon University
15 * All Rights Reserved.
17 * Permission to use, copy, modify and distribute this software and its
18 * documentation is hereby granted, provided that both the copyright
19 * notice and this permission notice appear in all copies of the
20 * software, derivative works or modified versions, and any portions
21 * thereof, and that both notices appear in supporting documentation.
23 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
24 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
25 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
27 * Carnegie Mellon requests users of this software to return to
29 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
30 * School of Computer Science
31 * Carnegie Mellon University
32 * Pittsburgh PA 15213-3890
34 * any improvements or extensions that they make and grant Carnegie Mellon
35 * the rights to redistribute these changes.
40 * Revision 1.14 2001/04/01 05:03:14 roland
41 * 2001-03-11 Roland McGrath <roland@frob.com>
43 * * mach/mach_error.h: Fix ancient #endif syntax.
44 * * hurd/hurdmalloc.c: Likewise.
46 * Revision 1.13 1996/12/20 01:32:01 drepper
47 * Update from main archive 961219
49 * Revision 1.12 1996/11/15 19:44:13 thomas
50 * Tue Nov 12 16:58:41 1996 Thomas Bushnell, n/BSG <thomas@gnu.ai.mit.edu>
52 * * mach/msg-destroy.c (mach_msg_destroy_port,
53 * mach_msg_destroy_memory): Use prototype syntax.
54 * * hurd/hurdmalloc.c (more_memory, malloc_fork_prepare,
55 * malloc_fork_parent, malloc_fork_child): Likewise.
57 * Revision 1.11 1996/06/06 15:13:47 miles
58 * Changes to bring in line with the hurd libthreads/malloc.c:
59 * (more_memory): Use assert_perror instead of MACH_CALL.
60 * "cthread_internals.h": Include removed.
61 * (realloc): Use LOG2_MIN_SIZE.
62 * (LOG2_MIN_SIZE): New macro.
63 * (realloc): Don't bother allocating a new block if the
64 * new size request fits in the old one and doesn't waste any space.
65 * Only free the old block if we successfully got a new one.
66 * [MCHECK] (struct header): New type.
67 * (union header): Only define if !MCHECK.
68 * (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
69 * [MCHECK] (MIN_SIZE): Add correct definition for this case.
70 * (more_memory, malloc, free, realloc): Use above macros, and add
71 * appropriate checks & frobs in MCHECK case.
73 * Revision 1.6 1996/03/07 21:13:08 miles
76 * Don't bother allocating a new block if the new size request fits in the old
77 * one and doesn't waste any space.
78 * Only free the old block if we successfully got a new one.
79 * (LOG2_MIN_SIZE): New macro.
81 * Revision 1.5 1996/03/06 23:51:04 miles
82 * [MCHECK] (struct header): New type.
83 * (union header): Only define if !MCHECK.
84 * (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
85 * [MCHECK] (MIN_SIZE): Add correct definition for this case.
86 * (more_memory, malloc, free, realloc):
87 * Use above macros, and add appropriate checks & frobs in MCHECK case.
89 * Revision 1.4 1994/05/05 11:21:42 roland
92 * Revision 2.7 91/05/14 17:57:34 mrt
93 * Correcting copyright
95 * Revision 2.6 91/02/14 14:20:26 mrt
96 * Added new Mach copyright
97 * [91/02/13 12:41:21 mrt]
99 * Revision 2.5 90/11/05 14:37:33 rpd
100 * Added malloc_fork* code.
106 * Revision 2.4 90/08/07 14:31:28 rpd
107 * Removed RCS keyword nonsense.
109 * Revision 2.3 90/06/02 15:14:00 rpd
110 * Converted to new IPC.
111 * [90/03/20 20:56:57 rpd]
113 * Revision 2.2 89/12/08 19:53:59 rwd
114 * Removed conditionals.
117 * Revision 2.1 89/08/03 17:09:46 rwd
121 * 13-Sep-88 Eric Cooper (ecc) at Carnegie Mellon University
122 * Changed realloc() to copy min(old size, new size) bytes.
123 * Bug found by Mike Kupfer at Olivetti.
127 * Author: Eric Cooper, Carnegie Mellon University
130 * Memory allocator for use with multiple threads.
136 #include <cthreads.h>
141 * Structure of memory block header.
142 * When free, next points to next block on free list.
143 * When allocated, fl points to free list.
144 * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
147 #define CHECK_BUSY 0x8a3c743e
148 #define CHECK_FREE 0x66688b92
152 typedef struct header {
156 struct free_list *fl;
160 #define HEADER_SIZE sizeof (struct header)
161 #define HEADER_NEXT(h) ((h)->u.next)
162 #define HEADER_FREE(h) ((h)->u.fl)
163 #define HEADER_CHECK(h) ((h)->check)
165 #define LOG2_MIN_SIZE 4
169 typedef union header {
171 struct free_list *fl;
174 #define HEADER_SIZE sizeof (union header)
175 #define HEADER_NEXT(h) ((h)->next)
176 #define HEADER_FREE(h) ((h)->fl)
177 #define MIN_SIZE 8 /* minimum block size */
178 #define LOG2_MIN_SIZE 3
182 typedef struct free_list {
183 spin_lock_t lock; /* spin lock for mutual exclusion */
184 header_t head; /* head of free list for this size */
186 int in_use; /* # mallocs - # frees */
191 * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
192 * including header. Smallest block size is MIN_SIZE, with MIN_SIZE -
193 * HEADER_SIZE bytes available to user. Size argument to malloc is a signed
194 * integer for sanity checking, so largest block size is 2^31.
198 static struct free_list malloc_free_list[NBUCKETS];
200 /* Initialization just sets everything to zero, but might be necessary on a
201 machine where spin_lock_init does otherwise, and is necessary when
202 running an executable that was written by something like Emacs's unexec.
203 It preserves the values of data variables like malloc_free_list, but
204 does not save the vm_allocate'd space allocated by this malloc. */
210 for (i = 0; i < NBUCKETS; ++i)
212 spin_lock_init (&malloc_free_list[i].lock);
213 malloc_free_list[i].head = NULL;
215 malloc_free_list[i].in_use = 0;
219 /* This not only suppresses a `defined but not used' warning,
220 but it is ABSOLUTELY NECESSARY to avoid the hyperclever
221 compiler from "optimizing out" the entire function! */
226 more_memory(int size, free_list_t fl)
234 if (size <= vm_page_size) {
235 amount = vm_page_size;
236 n = vm_page_size / size;
237 /* We lose vm_page_size - n*size bytes here. */
243 r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
246 h = (header_t) where;
248 HEADER_NEXT (h) = fl->head;
250 HEADER_CHECK (h) = CHECK_FREE;
253 h = (header_t) ((char *) h + size);
257 /* Declaration changed to standard one for GNU. */
260 register size_t size;
263 register free_list_t fl;
266 if ((int) size < 0) /* sanity check */
270 * Find smallest power-of-two block size
271 * big enough to hold requested size plus header.
279 ASSERT(i < NBUCKETS);
280 fl = &malloc_free_list[i];
281 spin_lock(&fl->lock);
285 * Free list is empty;
286 * allocate more blocks.
294 spin_unlock(&fl->lock);
299 * Pop block from free list.
301 fl->head = HEADER_NEXT (h);
304 assert (HEADER_CHECK (h) == CHECK_FREE);
305 HEADER_CHECK (h) = CHECK_BUSY;
311 spin_unlock(&fl->lock);
313 * Store free list pointer in block header
314 * so we can figure out where it goes
317 HEADER_FREE (h) = fl;
319 * Return pointer past the block header.
321 return ((char *) h) + HEADER_SIZE;
324 /* Declaration changed to standard one for GNU. */
330 register free_list_t fl;
336 * Find free list for block.
338 h = (header_t) (base - HEADER_SIZE);
341 assert (HEADER_CHECK (h) == CHECK_BUSY);
344 fl = HEADER_FREE (h);
345 i = fl - malloc_free_list;
349 if (i < 0 || i >= NBUCKETS) {
350 ASSERT(0 <= i && i < NBUCKETS);
353 if (fl != &malloc_free_list[i]) {
354 ASSERT(fl == &malloc_free_list[i]);
358 * Push block on free list.
360 spin_lock(&fl->lock);
361 HEADER_NEXT (h) = fl->head;
363 HEADER_CHECK (h) = CHECK_FREE;
369 spin_unlock(&fl->lock);
373 /* Declaration changed to standard one for GNU. */
375 realloc(old_base, new_size)
380 register free_list_t fl;
382 unsigned int old_size;
386 return malloc (new_size);
389 * Find size of old block.
391 h = (header_t) (old_base - HEADER_SIZE);
393 assert (HEADER_CHECK (h) == CHECK_BUSY);
395 fl = HEADER_FREE (h);
396 i = fl - malloc_free_list;
400 if (i < 0 || i >= NBUCKETS) {
401 ASSERT(0 <= i && i < NBUCKETS);
404 if (fl != &malloc_free_list[i]) {
405 ASSERT(fl == &malloc_free_list[i]);
409 * Free list with index i contains blocks of size
410 * 2 ^ (i + * LOG2_MIN_SIZE) including header.
412 old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
414 if (new_size <= old_size
415 && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
416 /* The new size still fits in the same block, and wouldn't fit in
417 the next smaller block! */
421 * Allocate new block, copy old bytes, and free old block.
423 new_base = malloc(new_size);
425 bcopy(old_base, new_base,
426 (int) (old_size < new_size ? old_size : new_size));
428 if (new_base || new_size == 0)
429 /* Free OLD_BASE, but only if the malloc didn't fail. */
437 print_malloc_free_list()
439 register int i, size;
440 register free_list_t fl;
446 fprintf(stderr, " Size In Use Free Total\n");
447 for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
449 i += 1, size <<= 1, fl += 1) {
450 spin_lock(&fl->lock);
451 if (fl->in_use != 0 || fl->head != 0) {
452 total_used += fl->in_use * size;
453 for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
455 total_free += n * size;
456 fprintf(stderr, "%10d %10d %10d %10d\n",
457 size, fl->in_use, n, fl->in_use + n);
459 spin_unlock(&fl->lock);
461 fprintf(stderr, " all sizes %10d %10d %10d\n",
462 total_used, total_free, total_used + total_free);
467 malloc_fork_prepare(void)
469 * Prepare the malloc module for a fork by insuring that no thread is in a
470 * malloc critical section.
475 for (i = 0; i < NBUCKETS; i++) {
476 spin_lock(&malloc_free_list[i].lock);
481 malloc_fork_parent(void)
483 * Called in the parent process after a fork() to resume normal operation.
488 for (i = NBUCKETS-1; i >= 0; i--) {
489 spin_unlock(&malloc_free_list[i].lock);
494 malloc_fork_child(void)
496 * Called in the child process after a fork() to resume normal operation.
501 for (i = NBUCKETS-1; i >= 0; i--) {
502 spin_unlock(&malloc_free_list[i].lock);
507 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
508 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
509 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
510 text_set_element (_hurd_preinit_hook, malloc_init);