2002-01-02 Roland McGrath <roland@frob.com>
[kopensolaris-gnu/glibc.git] / hurd / hurdmalloc.c
1 #include <stdlib.h>
2 #include <string.h>
3
4 #include "hurdmalloc.h"         /* XXX see that file */
5
6 #include <mach.h>
7 #define vm_allocate __vm_allocate
8 #define vm_page_size __vm_page_size
9
10 /*
11  * Mach Operating System
12  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
13  * All Rights Reserved.
14  *
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.
20  *
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.
24  *
25  * Carnegie Mellon requests users of this software to return to
26  *
27  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
28  *  School of Computer Science
29  *  Carnegie Mellon University
30  *  Pittsburgh PA 15213-3890
31  *
32  * any improvements or extensions that they make and grant Carnegie Mellon
33  * the rights to redistribute these changes.
34  */
35 /*
36  * HISTORY
37  * $Log$
38  * Revision 1.15  2001/09/19 03:04:09  drepper
39  * (bcopy): Removed.
40  * (realloc): Replace bcopy with memcpy.
41  *
42  * Revision 1.14  2001/04/01 05:03:14  roland
43  * 2001-03-11  Roland McGrath  <roland@frob.com>
44  *
45  *      * mach/mach_error.h: Fix ancient #endif syntax.
46  *      * hurd/hurdmalloc.c: Likewise.
47  *
48  * Revision 1.13  1996/12/20 01:32:01  drepper
49  * Update from main archive 961219
50  *
51  * Revision 1.12  1996/11/15 19:44:13  thomas
52  * Tue Nov 12 16:58:41 1996  Thomas Bushnell, n/BSG  <thomas@gnu.ai.mit.edu>
53  *
54  *      * mach/msg-destroy.c (mach_msg_destroy_port,
55  *      mach_msg_destroy_memory): Use prototype syntax.
56  *      * hurd/hurdmalloc.c (more_memory, malloc_fork_prepare,
57  *      malloc_fork_parent, malloc_fork_child): Likewise.
58  *
59  * Revision 1.11  1996/06/06 15:13:47  miles
60  * Changes to bring in line with the hurd libthreads/malloc.c:
61  *   (more_memory): Use assert_perror instead of MACH_CALL.
62  *   "cthread_internals.h": Include removed.
63  *   (realloc): Use LOG2_MIN_SIZE.
64  *   (LOG2_MIN_SIZE): New macro.
65  *   (realloc): Don't bother allocating a new block if the
66  *     new size request fits in the old one and doesn't waste any space.
67  *     Only free the old block if we successfully got a new one.
68  *   [MCHECK] (struct header): New type.
69  *   (union header): Only define if !MCHECK.
70  *   (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
71  *   [MCHECK] (MIN_SIZE): Add correct definition for this case.
72  *   (more_memory, malloc, free, realloc): Use above macros, and add
73  *     appropriate checks & frobs in MCHECK case.
74  *
75  * Revision 1.6  1996/03/07 21:13:08  miles
76  * (realloc):
77  *   Use LOG2_MIN_SIZE.
78  *   Don't bother allocating a new block if the new size request fits in the old
79  *     one and doesn't waste any space.
80  *   Only free the old block if we successfully got a new one.
81  * (LOG2_MIN_SIZE): New macro.
82  *
83  * Revision 1.5  1996/03/06 23:51:04  miles
84  * [MCHECK] (struct header): New type.
85  * (union header): Only define if !MCHECK.
86  * (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
87  * [MCHECK] (MIN_SIZE): Add correct definition for this case.
88  * (more_memory, malloc, free, realloc):
89  *   Use above macros, and add appropriate checks & frobs in MCHECK case.
90  *
91  * Revision 1.4  1994/05/05 11:21:42  roland
92  * entered into RCS
93  *
94  * Revision 2.7  91/05/14  17:57:34  mrt
95  *      Correcting copyright
96  *
97  * Revision 2.6  91/02/14  14:20:26  mrt
98  *      Added new Mach copyright
99  *      [91/02/13  12:41:21  mrt]
100  *
101  * Revision 2.5  90/11/05  14:37:33  rpd
102  *      Added malloc_fork* code.
103  *      [90/11/02            rwd]
104  *
105  *      Add spin_lock_t.
106  *      [90/10/31            rwd]
107  *
108  * Revision 2.4  90/08/07  14:31:28  rpd
109  *      Removed RCS keyword nonsense.
110  *
111  * Revision 2.3  90/06/02  15:14:00  rpd
112  *      Converted to new IPC.
113  *      [90/03/20  20:56:57  rpd]
114  *
115  * Revision 2.2  89/12/08  19:53:59  rwd
116  *      Removed conditionals.
117  *      [89/10/23            rwd]
118  *
119  * Revision 2.1  89/08/03  17:09:46  rwd
120  * Created.
121  *
122  *
123  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
124  *      Changed realloc() to copy min(old size, new size) bytes.
125  *      Bug found by Mike Kupfer at Olivetti.
126  */
127 /*
128  *      File:   malloc.c
129  *      Author: Eric Cooper, Carnegie Mellon University
130  *      Date:   July, 1988
131  *
132  *      Memory allocator for use with multiple threads.
133  */
134
135 \f
136 #include <assert.h>
137
138 #include <cthreads.h>
139
140 #define MCHECK
141
142 /*
143  * Structure of memory block header.
144  * When free, next points to next block on free list.
145  * When allocated, fl points to free list.
146  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
147  */
148
149 #define CHECK_BUSY  0x8a3c743e
150 #define CHECK_FREE  0x66688b92
151
152 #ifdef MCHECK
153
154 typedef struct header {
155   long check;
156   union {
157     struct header *next;
158     struct free_list *fl;
159   } u;
160 } *header_t;
161
162 #define HEADER_SIZE sizeof (struct header)
163 #define HEADER_NEXT(h) ((h)->u.next)
164 #define HEADER_FREE(h) ((h)->u.fl)
165 #define HEADER_CHECK(h) ((h)->check)
166 #define MIN_SIZE        16
167 #define LOG2_MIN_SIZE   4
168
169 #else /* ! MCHECK */
170
171 typedef union header {
172         union header *next;
173         struct free_list *fl;
174 } *header_t;
175
176 #define HEADER_SIZE sizeof (union header)
177 #define HEADER_NEXT(h) ((h)->next)
178 #define HEADER_FREE(h) ((h)->fl)
179 #define MIN_SIZE        8       /* minimum block size */
180 #define LOG2_MIN_SIZE   3
181
182 #endif /* MCHECK */
183
184 typedef struct free_list {
185         spin_lock_t lock;       /* spin lock for mutual exclusion */
186         header_t head;          /* head of free list for this size */
187 #ifdef  DEBUG
188         int in_use;             /* # mallocs - # frees */
189 #endif  /* DEBUG */
190 } *free_list_t;
191
192 /*
193  * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
194  * including header.  Smallest block size is MIN_SIZE, with MIN_SIZE -
195  * HEADER_SIZE bytes available to user.  Size argument to malloc is a signed
196  * integer for sanity checking, so largest block size is 2^31.
197  */
198 #define NBUCKETS        29
199
200 static struct free_list malloc_free_list[NBUCKETS];
201
202 /* Initialization just sets everything to zero, but might be necessary on a
203    machine where spin_lock_init does otherwise, and is necessary when
204    running an executable that was written by something like Emacs's unexec.
205    It preserves the values of data variables like malloc_free_list, but
206    does not save the vm_allocate'd space allocated by this malloc.  */
207
208 static void
209 malloc_init (void)
210 {
211   int i;
212   for (i = 0; i < NBUCKETS; ++i)
213     {
214       spin_lock_init (&malloc_free_list[i].lock);
215       malloc_free_list[i].head = NULL;
216 #ifdef DEBUG
217       malloc_free_list[i].in_use = 0;
218 #endif
219     }
220
221   /* This not only suppresses a `defined but not used' warning,
222      but it is ABSOLUTELY NECESSARY to avoid the hyperclever
223      compiler from "optimizing out" the entire function!  */
224   (void) &malloc_init;
225 }
226
227 static void
228 more_memory(int size, free_list_t fl)
229 {
230         register int amount;
231         register int n;
232         vm_address_t where;
233         register header_t h;
234         kern_return_t r;
235
236         if (size <= vm_page_size) {
237                 amount = vm_page_size;
238                 n = vm_page_size / size;
239                 /* We lose vm_page_size - n*size bytes here.  */
240         } else {
241                 amount = size;
242                 n = 1;
243         }
244
245         r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
246         assert_perror (r);
247
248         h = (header_t) where;
249         do {
250                 HEADER_NEXT (h) = fl->head;
251 #ifdef MCHECK
252                 HEADER_CHECK (h) = CHECK_FREE;
253 #endif
254                 fl->head = h;
255                 h = (header_t) ((char *) h + size);
256         } while (--n != 0);
257 }
258
259 /* Declaration changed to standard one for GNU.  */
260 void *
261 malloc(size)
262         register size_t size;
263 {
264         register int i, n;
265         register free_list_t fl;
266         register header_t h;
267
268         if ((int) size < 0)             /* sanity check */
269                 return 0;
270         size += HEADER_SIZE;
271         /*
272          * Find smallest power-of-two block size
273          * big enough to hold requested size plus header.
274          */
275         i = 0;
276         n = MIN_SIZE;
277         while (n < size) {
278                 i += 1;
279                 n <<= 1;
280         }
281         ASSERT(i < NBUCKETS);
282         fl = &malloc_free_list[i];
283         spin_lock(&fl->lock);
284         h = fl->head;
285         if (h == 0) {
286                 /*
287                  * Free list is empty;
288                  * allocate more blocks.
289                  */
290                 more_memory(n, fl);
291                 h = fl->head;
292                 if (h == 0) {
293                         /*
294                          * Allocation failed.
295                          */
296                         spin_unlock(&fl->lock);
297                         return 0;
298                 }
299         }
300         /*
301          * Pop block from free list.
302          */
303         fl->head = HEADER_NEXT (h);
304
305 #ifdef MCHECK
306         assert (HEADER_CHECK (h) == CHECK_FREE);
307         HEADER_CHECK (h) = CHECK_BUSY;
308 #endif
309
310 #ifdef  DEBUG
311         fl->in_use += 1;
312 #endif  /* DEBUG */
313         spin_unlock(&fl->lock);
314         /*
315          * Store free list pointer in block header
316          * so we can figure out where it goes
317          * at free() time.
318          */
319         HEADER_FREE (h) = fl;
320         /*
321          * Return pointer past the block header.
322          */
323         return ((char *) h) + HEADER_SIZE;
324 }
325
326 /* Declaration changed to standard one for GNU.  */
327 void
328 free(base)
329         void *base;
330 {
331         register header_t h;
332         register free_list_t fl;
333         register int i;
334
335         if (base == 0)
336                 return;
337         /*
338          * Find free list for block.
339          */
340         h = (header_t) (base - HEADER_SIZE);
341
342 #ifdef MCHECK
343         assert (HEADER_CHECK (h) == CHECK_BUSY);
344 #endif
345
346         fl = HEADER_FREE (h);
347         i = fl - malloc_free_list;
348         /*
349          * Sanity checks.
350          */
351         if (i < 0 || i >= NBUCKETS) {
352                 ASSERT(0 <= i && i < NBUCKETS);
353                 return;
354         }
355         if (fl != &malloc_free_list[i]) {
356                 ASSERT(fl == &malloc_free_list[i]);
357                 return;
358         }
359         /*
360          * Push block on free list.
361          */
362         spin_lock(&fl->lock);
363         HEADER_NEXT (h) = fl->head;
364 #ifdef MCHECK
365         HEADER_CHECK (h) = CHECK_FREE;
366 #endif
367         fl->head = h;
368 #ifdef  DEBUG
369         fl->in_use -= 1;
370 #endif  /* DEBUG */
371         spin_unlock(&fl->lock);
372         return;
373 }
374
375 /* Declaration changed to standard one for GNU.  */
376 void *
377 realloc(old_base, new_size)
378         void *old_base;
379         size_t new_size;
380 {
381         register header_t h;
382         register free_list_t fl;
383         register int i;
384         unsigned int old_size;
385         char *new_base;
386
387         if (old_base == 0)
388           return malloc (new_size);
389
390         /*
391          * Find size of old block.
392          */
393         h = (header_t) (old_base - HEADER_SIZE);
394 #ifdef MCHECK
395         assert (HEADER_CHECK (h) == CHECK_BUSY);
396 #endif
397         fl = HEADER_FREE (h);
398         i = fl - malloc_free_list;
399         /*
400          * Sanity checks.
401          */
402         if (i < 0 || i >= NBUCKETS) {
403                 ASSERT(0 <= i && i < NBUCKETS);
404                 return 0;
405         }
406         if (fl != &malloc_free_list[i]) {
407                 ASSERT(fl == &malloc_free_list[i]);
408                 return 0;
409         }
410         /*
411          * Free list with index i contains blocks of size
412          * 2 ^ (i + * LOG2_MIN_SIZE) including header.
413          */
414         old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
415
416         if (new_size <= old_size
417             && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
418           /* The new size still fits in the same block, and wouldn't fit in
419              the next smaller block!  */
420           return old_base;
421
422         /*
423          * Allocate new block, copy old bytes, and free old block.
424          */
425         new_base = malloc(new_size);
426         if (new_base)
427           memcpy (new_base, old_base,
428                   (int) (old_size < new_size ? old_size : new_size));
429
430         if (new_base || new_size == 0)
431           /* Free OLD_BASE, but only if the malloc didn't fail.  */
432           free (old_base);
433
434         return new_base;
435 }
436
437 #ifdef  DEBUG
438 void
439 print_malloc_free_list()
440 {
441         register int i, size;
442         register free_list_t fl;
443         register int n;
444         register header_t h;
445         int total_used = 0;
446         int total_free = 0;
447
448         fprintf(stderr, "      Size     In Use       Free      Total\n");
449         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
450              i < NBUCKETS;
451              i += 1, size <<= 1, fl += 1) {
452                 spin_lock(&fl->lock);
453                 if (fl->in_use != 0 || fl->head != 0) {
454                         total_used += fl->in_use * size;
455                         for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
456                                 ;
457                         total_free += n * size;
458                         fprintf(stderr, "%10d %10d %10d %10d\n",
459                                 size, fl->in_use, n, fl->in_use + n);
460                 }
461                 spin_unlock(&fl->lock);
462         }
463         fprintf(stderr, " all sizes %10d %10d %10d\n",
464                 total_used, total_free, total_used + total_free);
465 }
466 #endif  /* DEBUG */
467
468 static void
469 malloc_fork_prepare(void)
470 /*
471  * Prepare the malloc module for a fork by insuring that no thread is in a
472  * malloc critical section.
473  */
474 {
475     register int i;
476
477     for (i = 0; i < NBUCKETS; i++) {
478         spin_lock(&malloc_free_list[i].lock);
479     }
480 }
481
482 static void
483 malloc_fork_parent(void)
484 /*
485  * Called in the parent process after a fork() to resume normal operation.
486  */
487 {
488     register int i;
489
490     for (i = NBUCKETS-1; i >= 0; i--) {
491         spin_unlock(&malloc_free_list[i].lock);
492     }
493 }
494
495 static void
496 malloc_fork_child(void)
497 /*
498  * Called in the child process after a fork() to resume normal operation.
499  */
500 {
501     register int i;
502
503     for (i = NBUCKETS-1; i >= 0; i--) {
504         spin_unlock(&malloc_free_list[i].lock);
505     }
506 }
507 \f
508
509 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
510 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
511 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
512 text_set_element (_hurd_preinit_hook, malloc_init);