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.11 1996/06/06 15:13:47 miles
41 * Changes to bring in line with the hurd libthreads/malloc.c:
42 * (more_memory): Use assert_perror instead of MACH_CALL.
43 * "cthread_internals.h": Include removed.
44 * (realloc): Use LOG2_MIN_SIZE.
45 * (LOG2_MIN_SIZE): New macro.
46 * (realloc): Don't bother allocating a new block if the
47 * new size request fits in the old one and doesn't waste any space.
48 * Only free the old block if we successfully got a new one.
49 * [MCHECK] (struct header): New type.
50 * (union header): Only define if !MCHECK.
51 * (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
52 * [MCHECK] (MIN_SIZE): Add correct definition for this case.
53 * (more_memory, malloc, free, realloc): Use above macros, and add appropiate
54 * checks & frobs in MCHECK case.
56 * Revision 1.6 1996/03/07 21:13:08 miles
59 * Don't bother allocating a new block if the new size request fits in the old
60 * one and doesn't waste any space.
61 * Only free the old block if we successfully got a new one.
62 * (LOG2_MIN_SIZE): New macro.
64 * Revision 1.5 1996/03/06 23:51:04 miles
65 * [MCHECK] (struct header): New type.
66 * (union header): Only define if !MCHECK.
67 * (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
68 * [MCHECK] (MIN_SIZE): Add correct definition for this case.
69 * (more_memory, malloc, free, realloc):
70 * Use above macros, and add appropiate checks & frobs in MCHECK case.
72 * Revision 1.4 1994/05/05 11:21:42 roland
75 * Revision 2.7 91/05/14 17:57:34 mrt
76 * Correcting copyright
78 * Revision 2.6 91/02/14 14:20:26 mrt
79 * Added new Mach copyright
80 * [91/02/13 12:41:21 mrt]
82 * Revision 2.5 90/11/05 14:37:33 rpd
83 * Added malloc_fork* code.
89 * Revision 2.4 90/08/07 14:31:28 rpd
90 * Removed RCS keyword nonsense.
92 * Revision 2.3 90/06/02 15:14:00 rpd
93 * Converted to new IPC.
94 * [90/03/20 20:56:57 rpd]
96 * Revision 2.2 89/12/08 19:53:59 rwd
97 * Removed conditionals.
100 * Revision 2.1 89/08/03 17:09:46 rwd
104 * 13-Sep-88 Eric Cooper (ecc) at Carnegie Mellon University
105 * Changed realloc() to copy min(old size, new size) bytes.
106 * Bug found by Mike Kupfer at Olivetti.
110 * Author: Eric Cooper, Carnegie Mellon University
113 * Memory allocator for use with multiple threads.
119 #include <cthreads.h>
124 * Structure of memory block header.
125 * When free, next points to next block on free list.
126 * When allocated, fl points to free list.
127 * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
130 #define CHECK_BUSY 0x8a3c743e
131 #define CHECK_FREE 0x66688b92
135 typedef struct header
{
139 struct free_list
*fl
;
143 #define HEADER_SIZE sizeof (struct header)
144 #define HEADER_NEXT(h) ((h)->u.next)
145 #define HEADER_FREE(h) ((h)->u.fl)
146 #define HEADER_CHECK(h) ((h)->check)
148 #define LOG2_MIN_SIZE 4
152 typedef union header
{
154 struct free_list
*fl
;
157 #define HEADER_SIZE sizeof (union header)
158 #define HEADER_NEXT(h) ((h)->next)
159 #define HEADER_FREE(h) ((h)->fl)
160 #define MIN_SIZE 8 /* minimum block size */
161 #define LOG2_MIN_SIZE 3
165 typedef struct free_list
{
166 spin_lock_t lock
; /* spin lock for mutual exclusion */
167 header_t head
; /* head of free list for this size */
169 int in_use
; /* # mallocs - # frees */
174 * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
175 * including header. Smallest block size is MIN_SIZE, with MIN_SIZE -
176 * HEADER_SIZE bytes available to user. Size argument to malloc is a signed
177 * integer for sanity checking, so largest block size is 2^31.
181 static struct free_list malloc_free_list
[NBUCKETS
];
183 /* Initialization just sets everything to zero, but might be necessary on a
184 machine where spin_lock_init does otherwise, and is necessary when
185 running an executable that was written by something like Emacs's unexec.
186 It preserves the values of data variables like malloc_free_list, but
187 does not save the vm_allocate'd space allocated by this malloc. */
193 for (i
= 0; i
< NBUCKETS
; ++i
)
195 spin_lock_init (&malloc_free_list
[i
].lock
);
196 malloc_free_list
[i
].head
= NULL
;
198 malloc_free_list
[i
].in_use
= 0;
202 /* This not only suppresses a `defined but not used' warning,
203 but it is ABSOLUTELY NECESSARY to avoid the hyperclever
204 compiler from "optimizing out" the entire function! */
209 more_memory(size
, fl
)
211 register free_list_t fl
;
219 if (size
<= vm_page_size
) {
220 amount
= vm_page_size
;
221 n
= vm_page_size
/ size
;
222 /* We lose vm_page_size - n*size bytes here. */
228 r
= vm_allocate(mach_task_self(), &where
, (vm_size_t
) amount
, TRUE
);
231 h
= (header_t
) where
;
233 HEADER_NEXT (h
) = fl
->head
;
235 HEADER_CHECK (h
) = CHECK_FREE
;
238 h
= (header_t
) ((char *) h
+ size
);
242 /* Declaration changed to standard one for GNU. */
245 register size_t size
;
248 register free_list_t fl
;
251 if ((int) size
< 0) /* sanity check */
255 * Find smallest power-of-two block size
256 * big enough to hold requested size plus header.
264 ASSERT(i
< NBUCKETS
);
265 fl
= &malloc_free_list
[i
];
266 spin_lock(&fl
->lock
);
270 * Free list is empty;
271 * allocate more blocks.
279 spin_unlock(&fl
->lock
);
284 * Pop block from free list.
286 fl
->head
= HEADER_NEXT (h
);
289 assert (HEADER_CHECK (h
) == CHECK_FREE
);
290 HEADER_CHECK (h
) = CHECK_BUSY
;
296 spin_unlock(&fl
->lock
);
298 * Store free list pointer in block header
299 * so we can figure out where it goes
302 HEADER_FREE (h
) = fl
;
304 * Return pointer past the block header.
306 return ((char *) h
) + HEADER_SIZE
;
309 /* Declaration changed to standard one for GNU. */
315 register free_list_t fl
;
321 * Find free list for block.
323 h
= (header_t
) (base
- HEADER_SIZE
);
326 assert (HEADER_CHECK (h
) == CHECK_BUSY
);
329 fl
= HEADER_FREE (h
);
330 i
= fl
- malloc_free_list
;
334 if (i
< 0 || i
>= NBUCKETS
) {
335 ASSERT(0 <= i
&& i
< NBUCKETS
);
338 if (fl
!= &malloc_free_list
[i
]) {
339 ASSERT(fl
== &malloc_free_list
[i
]);
343 * Push block on free list.
345 spin_lock(&fl
->lock
);
346 HEADER_NEXT (h
) = fl
->head
;
348 HEADER_CHECK (h
) = CHECK_FREE
;
354 spin_unlock(&fl
->lock
);
358 /* Declaration changed to standard one for GNU. */
360 realloc(old_base
, new_size
)
365 register free_list_t fl
;
367 unsigned int old_size
;
371 return malloc (new_size
);
374 * Find size of old block.
376 h
= (header_t
) (old_base
- HEADER_SIZE
);
378 assert (HEADER_CHECK (h
) == CHECK_BUSY
);
380 fl
= HEADER_FREE (h
);
381 i
= fl
- malloc_free_list
;
385 if (i
< 0 || i
>= NBUCKETS
) {
386 ASSERT(0 <= i
&& i
< NBUCKETS
);
389 if (fl
!= &malloc_free_list
[i
]) {
390 ASSERT(fl
== &malloc_free_list
[i
]);
394 * Free list with index i contains blocks of size
395 * 2 ^ (i + * LOG2_MIN_SIZE) including header.
397 old_size
= (1 << (i
+ LOG2_MIN_SIZE
)) - HEADER_SIZE
;
399 if (new_size
<= old_size
400 && new_size
> (((old_size
+ HEADER_SIZE
) >> 1) - HEADER_SIZE
))
401 /* The new size still fits in the same block, and wouldn't fit in
402 the next smaller block! */
406 * Allocate new block, copy old bytes, and free old block.
408 new_base
= malloc(new_size
);
410 bcopy(old_base
, new_base
,
411 (int) (old_size
< new_size
? old_size
: new_size
));
413 if (new_base
|| new_size
== 0)
414 /* Free OLD_BASE, but only if the malloc didn't fail. */
422 print_malloc_free_list()
424 register int i
, size
;
425 register free_list_t fl
;
431 fprintf(stderr
, " Size In Use Free Total\n");
432 for (i
= 0, size
= MIN_SIZE
, fl
= malloc_free_list
;
434 i
+= 1, size
<<= 1, fl
+= 1) {
435 spin_lock(&fl
->lock
);
436 if (fl
->in_use
!= 0 || fl
->head
!= 0) {
437 total_used
+= fl
->in_use
* size
;
438 for (n
= 0, h
= fl
->head
; h
!= 0; h
= HEADER_NEXT (h
), n
+= 1)
440 total_free
+= n
* size
;
441 fprintf(stderr
, "%10d %10d %10d %10d\n",
442 size
, fl
->in_use
, n
, fl
->in_use
+ n
);
444 spin_unlock(&fl
->lock
);
446 fprintf(stderr
, " all sizes %10d %10d %10d\n",
447 total_used
, total_free
, total_used
+ total_free
);
451 static void malloc_fork_prepare()
453 * Prepare the malloc module for a fork by insuring that no thread is in a
454 * malloc critical section.
459 for (i
= 0; i
< NBUCKETS
; i
++) {
460 spin_lock(&malloc_free_list
[i
].lock
);
464 static void malloc_fork_parent()
466 * Called in the parent process after a fork() to resume normal operation.
471 for (i
= NBUCKETS
-1; i
>= 0; i
--) {
472 spin_unlock(&malloc_free_list
[i
].lock
);
476 static void malloc_fork_child()
478 * Called in the child process after a fork() to resume normal operation.
483 for (i
= NBUCKETS
-1; i
>= 0; i
--) {
484 spin_unlock(&malloc_free_list
[i
].lock
);
489 text_set_element (_hurd_fork_prepare_hook
, malloc_fork_prepare
);
490 text_set_element (_hurd_fork_parent_hook
, malloc_fork_parent
);
491 text_set_element (_hurd_fork_child_hook
, malloc_fork_child
);
492 text_set_element (_hurd_preinit_hook
, malloc_init
);