Updated to fedora-glibc-20081028T1533
[glibc.git] / hurd / hurdmalloc.c
blob12da1f2abc50ef0a1c2e107166331cc28ea0703a
1 #include <stdlib.h>
2 #include <string.h>
4 #include "hurdmalloc.h" /* XXX see that file */
6 #include <mach.h>
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.
36 * (pre-GNU) HISTORY
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.
47 * [90/11/02 rwd]
49 * Add spin_lock_t.
50 * [90/10/31 rwd]
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.
61 * [89/10/23 rwd]
63 * Revision 2.1 89/08/03 17:09:46 rwd
64 * Created.
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.
72 * File: malloc.c
73 * Author: Eric Cooper, Carnegie Mellon University
74 * Date: July, 1988
76 * Memory allocator for use with multiple threads.
80 #include <assert.h>
82 #include <cthreads.h>
84 #define MCHECK
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
96 #ifdef MCHECK
98 typedef struct header {
99 long check;
100 union {
101 struct header *next;
102 struct free_list *fl;
103 } u;
104 } *header_t;
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)
110 #define MIN_SIZE 16
111 #define LOG2_MIN_SIZE 4
113 #else /* ! MCHECK */
115 typedef union header {
116 union header *next;
117 struct free_list *fl;
118 } *header_t;
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
126 #endif /* MCHECK */
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 */
131 #ifdef DEBUG
132 int in_use; /* # mallocs - # frees */
133 #endif /* DEBUG */
134 } *free_list_t;
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.
142 #define NBUCKETS 29
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. */
152 static void
153 malloc_init (void)
155 int i;
156 for (i = 0; i < NBUCKETS; ++i)
158 spin_lock_init (&malloc_free_list[i].lock);
159 malloc_free_list[i].head = NULL;
160 #ifdef DEBUG
161 malloc_free_list[i].in_use = 0;
162 #endif
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! */
168 (void) &malloc_init;
171 static void
172 more_memory(int size, free_list_t fl)
174 register int amount;
175 register int n;
176 vm_address_t where;
177 register header_t h;
178 kern_return_t r;
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. */
184 } else {
185 amount = size;
186 n = 1;
189 r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
190 assert_perror (r);
192 h = (header_t) where;
193 do {
194 HEADER_NEXT (h) = fl->head;
195 #ifdef MCHECK
196 HEADER_CHECK (h) = CHECK_FREE;
197 #endif
198 fl->head = h;
199 h = (header_t) ((char *) h + size);
200 } while (--n != 0);
203 /* Declaration changed to standard one for GNU. */
204 void *
205 malloc(size)
206 register size_t size;
208 register int i, n;
209 register free_list_t fl;
210 register header_t h;
212 if ((int) size < 0) /* sanity check */
213 return 0;
214 size += HEADER_SIZE;
216 * Find smallest power-of-two block size
217 * big enough to hold requested size plus header.
219 i = 0;
220 n = MIN_SIZE;
221 while (n < size) {
222 i += 1;
223 n <<= 1;
225 ASSERT(i < NBUCKETS);
226 fl = &malloc_free_list[i];
227 spin_lock(&fl->lock);
228 h = fl->head;
229 if (h == 0) {
231 * Free list is empty;
232 * allocate more blocks.
234 more_memory(n, fl);
235 h = fl->head;
236 if (h == 0) {
238 * Allocation failed.
240 spin_unlock(&fl->lock);
241 return 0;
245 * Pop block from free list.
247 fl->head = HEADER_NEXT (h);
249 #ifdef MCHECK
250 assert (HEADER_CHECK (h) == CHECK_FREE);
251 HEADER_CHECK (h) = CHECK_BUSY;
252 #endif
254 #ifdef DEBUG
255 fl->in_use += 1;
256 #endif /* DEBUG */
257 spin_unlock(&fl->lock);
259 * Store free list pointer in block header
260 * so we can figure out where it goes
261 * at free() time.
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. */
271 void
272 free(base)
273 void *base;
275 register header_t h;
276 register free_list_t fl;
277 register int i;
279 if (base == 0)
280 return;
282 * Find free list for block.
284 h = (header_t) (base - HEADER_SIZE);
286 #ifdef MCHECK
287 assert (HEADER_CHECK (h) == CHECK_BUSY);
288 #endif
290 fl = HEADER_FREE (h);
291 i = fl - malloc_free_list;
293 * Sanity checks.
295 if (i < 0 || i >= NBUCKETS) {
296 ASSERT(0 <= i && i < NBUCKETS);
297 return;
299 if (fl != &malloc_free_list[i]) {
300 ASSERT(fl == &malloc_free_list[i]);
301 return;
304 * Push block on free list.
306 spin_lock(&fl->lock);
307 HEADER_NEXT (h) = fl->head;
308 #ifdef MCHECK
309 HEADER_CHECK (h) = CHECK_FREE;
310 #endif
311 fl->head = h;
312 #ifdef DEBUG
313 fl->in_use -= 1;
314 #endif /* DEBUG */
315 spin_unlock(&fl->lock);
316 return;
319 /* Declaration changed to standard one for GNU. */
320 void *
321 realloc(old_base, new_size)
322 void *old_base;
323 size_t new_size;
325 register header_t h;
326 register free_list_t fl;
327 register int i;
328 unsigned int old_size;
329 char *new_base;
331 if (old_base == 0)
332 return malloc (new_size);
335 * Find size of old block.
337 h = (header_t) (old_base - HEADER_SIZE);
338 #ifdef MCHECK
339 assert (HEADER_CHECK (h) == CHECK_BUSY);
340 #endif
341 fl = HEADER_FREE (h);
342 i = fl - malloc_free_list;
344 * Sanity checks.
346 if (i < 0 || i >= NBUCKETS) {
347 ASSERT(0 <= i && i < NBUCKETS);
348 return 0;
350 if (fl != &malloc_free_list[i]) {
351 ASSERT(fl == &malloc_free_list[i]);
352 return 0;
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! */
364 return old_base;
367 * Allocate new block, copy old bytes, and free old block.
369 new_base = malloc(new_size);
370 if (new_base)
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. */
376 free (old_base);
378 return new_base;
381 #ifdef DEBUG
382 void
383 print_malloc_free_list()
385 register int i, size;
386 register free_list_t fl;
387 register int n;
388 register header_t h;
389 int total_used = 0;
390 int total_free = 0;
392 fprintf(stderr, " Size In Use Free Total\n");
393 for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
394 i < NBUCKETS;
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);
410 #endif /* DEBUG */
412 static void
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.
419 register int i;
421 for (i = 0; i < NBUCKETS; i++) {
422 spin_lock(&malloc_free_list[i].lock);
426 static void
427 malloc_fork_parent(void)
429 * Called in the parent process after a fork() to resume normal operation.
432 register int i;
434 for (i = NBUCKETS-1; i >= 0; i--) {
435 spin_unlock(&malloc_free_list[i].lock);
439 static void
440 malloc_fork_child(void)
442 * Called in the child process after a fork() to resume normal operation.
445 register int i;
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);