Changes to bring in line with the hurd libthreads/malloc.c:
[kopensolaris-gnu/glibc.git] / hurd / hurdmalloc.c
1 #include <stdlib.h>
2 #include <string.h>
3
4 #define bcopy(s,d,n)    memcpy ((d), (s), (n)) /* No overlap handling.  */
5
6 #include "hurdmalloc.h"         /* XXX see that file */
7
8 #include <mach.h>
9 #define vm_allocate __vm_allocate
10 #define vm_page_size __vm_page_size
11
12 /* 
13  * Mach Operating System
14  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
15  * All Rights Reserved.
16  * 
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.
22  * 
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.
26  * 
27  * Carnegie Mellon requests users of this software to return to
28  * 
29  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
30  *  School of Computer Science
31  *  Carnegie Mellon University
32  *  Pittsburgh PA 15213-3890
33  * 
34  * any improvements or extensions that they make and grant Carnegie Mellon
35  * the rights to redistribute these changes.
36  */
37 /*
38  * HISTORY
39  * $Log$
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.
55  *
56  * Revision 1.6  1996/03/07 21:13:08  miles
57  * (realloc):
58  *   Use LOG2_MIN_SIZE.
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.
63  *
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.
71  *
72  * Revision 1.4  1994/05/05 11:21:42  roland
73  * entered into RCS
74  *
75  * Revision 2.7  91/05/14  17:57:34  mrt
76  *      Correcting copyright
77  * 
78  * Revision 2.6  91/02/14  14:20:26  mrt
79  *      Added new Mach copyright
80  *      [91/02/13  12:41:21  mrt]
81  * 
82  * Revision 2.5  90/11/05  14:37:33  rpd
83  *      Added malloc_fork* code.
84  *      [90/11/02            rwd]
85  * 
86  *      Add spin_lock_t.
87  *      [90/10/31            rwd]
88  * 
89  * Revision 2.4  90/08/07  14:31:28  rpd
90  *      Removed RCS keyword nonsense.
91  * 
92  * Revision 2.3  90/06/02  15:14:00  rpd
93  *      Converted to new IPC.
94  *      [90/03/20  20:56:57  rpd]
95  * 
96  * Revision 2.2  89/12/08  19:53:59  rwd
97  *      Removed conditionals.
98  *      [89/10/23            rwd]
99  * 
100  * Revision 2.1  89/08/03  17:09:46  rwd
101  * Created.
102  * 
103  *
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.
107  */
108 /*
109  *      File:   malloc.c
110  *      Author: Eric Cooper, Carnegie Mellon University
111  *      Date:   July, 1988
112  *
113  *      Memory allocator for use with multiple threads.
114  */
115
116 \f
117 #include <assert.h>
118
119 #include <cthreads.h>
120
121 #define MCHECK
122
123 /*
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.
128  */
129
130 #define CHECK_BUSY  0x8a3c743e
131 #define CHECK_FREE  0x66688b92
132
133 #ifdef MCHECK
134
135 typedef struct header {
136   long check;
137   union {
138     struct header *next;
139     struct free_list *fl;
140   } u;
141 } *header_t;
142
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)
147 #define MIN_SIZE        16
148 #define LOG2_MIN_SIZE   4
149
150 #else /* ! MCHECK */
151
152 typedef union header {
153         union header *next;
154         struct free_list *fl;
155 } *header_t;
156
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
162
163 #endif /* MCHECK */
164
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 */
168 #ifdef  DEBUG
169         int in_use;             /* # mallocs - # frees */
170 #endif  DEBUG
171 } *free_list_t;
172
173 /*
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.
178  */
179 #define NBUCKETS        29
180
181 static struct free_list malloc_free_list[NBUCKETS];
182
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.  */
188
189 static void
190 malloc_init (void)
191 {
192   int i;
193   for (i = 0; i < NBUCKETS; ++i)
194     {
195       spin_lock_init (&malloc_free_list[i].lock);
196       malloc_free_list[i].head = NULL;
197 #ifdef DEBUG
198       malloc_free_list[i].in_use = 0;
199 #endif
200     }
201
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!  */
205   (void) &malloc_init;
206 }
207
208 static void
209 more_memory(size, fl)
210         int size;
211         register free_list_t fl;
212 {
213         register int amount;
214         register int n;
215         vm_address_t where;
216         register header_t h;
217         kern_return_t r;
218
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.  */
223         } else {
224                 amount = size;
225                 n = 1;
226         }
227
228         r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
229         assert_perror (r);
230
231         h = (header_t) where;
232         do {
233                 HEADER_NEXT (h) = fl->head;
234 #ifdef MCHECK
235                 HEADER_CHECK (h) = CHECK_FREE;
236 #endif
237                 fl->head = h;
238                 h = (header_t) ((char *) h + size);
239         } while (--n != 0);
240 }
241
242 /* Declaration changed to standard one for GNU.  */
243 void *
244 malloc(size)
245         register size_t size;
246 {
247         register int i, n;
248         register free_list_t fl;
249         register header_t h;
250
251         if ((int) size < 0)             /* sanity check */
252                 return 0;
253         size += HEADER_SIZE;
254         /*
255          * Find smallest power-of-two block size
256          * big enough to hold requested size plus header.
257          */
258         i = 0;
259         n = MIN_SIZE;
260         while (n < size) {
261                 i += 1;
262                 n <<= 1;
263         }
264         ASSERT(i < NBUCKETS);
265         fl = &malloc_free_list[i];
266         spin_lock(&fl->lock);
267         h = fl->head;
268         if (h == 0) {
269                 /*
270                  * Free list is empty;
271                  * allocate more blocks.
272                  */
273                 more_memory(n, fl);
274                 h = fl->head;
275                 if (h == 0) {
276                         /*
277                          * Allocation failed.
278                          */
279                         spin_unlock(&fl->lock);
280                         return 0;
281                 }
282         }
283         /*
284          * Pop block from free list.
285          */
286         fl->head = HEADER_NEXT (h);
287
288 #ifdef MCHECK
289         assert (HEADER_CHECK (h) == CHECK_FREE);
290         HEADER_CHECK (h) = CHECK_BUSY;
291 #endif
292
293 #ifdef  DEBUG
294         fl->in_use += 1;
295 #endif  DEBUG
296         spin_unlock(&fl->lock);
297         /*
298          * Store free list pointer in block header
299          * so we can figure out where it goes
300          * at free() time.
301          */
302         HEADER_FREE (h) = fl;
303         /*
304          * Return pointer past the block header.
305          */
306         return ((char *) h) + HEADER_SIZE;
307 }
308
309 /* Declaration changed to standard one for GNU.  */
310 void
311 free(base)
312         void *base;
313 {
314         register header_t h;
315         register free_list_t fl;
316         register int i;
317
318         if (base == 0)
319                 return;
320         /*
321          * Find free list for block.
322          */
323         h = (header_t) (base - HEADER_SIZE);
324
325 #ifdef MCHECK
326         assert (HEADER_CHECK (h) == CHECK_BUSY);
327 #endif  
328
329         fl = HEADER_FREE (h);
330         i = fl - malloc_free_list;
331         /*
332          * Sanity checks.
333          */
334         if (i < 0 || i >= NBUCKETS) {
335                 ASSERT(0 <= i && i < NBUCKETS);
336                 return;
337         }
338         if (fl != &malloc_free_list[i]) {
339                 ASSERT(fl == &malloc_free_list[i]);
340                 return;
341         }
342         /*
343          * Push block on free list.
344          */
345         spin_lock(&fl->lock);
346         HEADER_NEXT (h) = fl->head;
347 #ifdef MCHECK
348         HEADER_CHECK (h) = CHECK_FREE;
349 #endif  
350         fl->head = h;
351 #ifdef  DEBUG
352         fl->in_use -= 1;
353 #endif  DEBUG
354         spin_unlock(&fl->lock);
355         return;
356 }
357
358 /* Declaration changed to standard one for GNU.  */
359 void *
360 realloc(old_base, new_size)
361         void *old_base;
362         size_t new_size;
363 {
364         register header_t h;
365         register free_list_t fl;
366         register int i;
367         unsigned int old_size;
368         char *new_base;
369
370         if (old_base == 0)
371           return malloc (new_size);
372
373         /*
374          * Find size of old block.
375          */
376         h = (header_t) (old_base - HEADER_SIZE);
377 #ifdef MCHECK
378         assert (HEADER_CHECK (h) == CHECK_BUSY);
379 #endif
380         fl = HEADER_FREE (h);
381         i = fl - malloc_free_list;
382         /*
383          * Sanity checks.
384          */
385         if (i < 0 || i >= NBUCKETS) {
386                 ASSERT(0 <= i && i < NBUCKETS);
387                 return 0;
388         }
389         if (fl != &malloc_free_list[i]) {
390                 ASSERT(fl == &malloc_free_list[i]);
391                 return 0;
392         }
393         /*
394          * Free list with index i contains blocks of size
395          * 2 ^ (i + * LOG2_MIN_SIZE) including header.
396          */
397         old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
398
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!  */
403           return old_base;
404
405         /*
406          * Allocate new block, copy old bytes, and free old block.
407          */
408         new_base = malloc(new_size);
409         if (new_base)
410           bcopy(old_base, new_base,
411                 (int) (old_size < new_size ? old_size : new_size));
412
413         if (new_base || new_size == 0)
414           /* Free OLD_BASE, but only if the malloc didn't fail.  */
415           free (old_base);
416
417         return new_base;
418 }
419
420 #ifdef  DEBUG
421 void
422 print_malloc_free_list()
423 {
424         register int i, size;
425         register free_list_t fl;
426         register int n;
427         register header_t h;
428         int total_used = 0;
429         int total_free = 0;
430
431         fprintf(stderr, "      Size     In Use       Free      Total\n");
432         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
433              i < NBUCKETS;
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)
439                                 ;
440                         total_free += n * size;
441                         fprintf(stderr, "%10d %10d %10d %10d\n",
442                                 size, fl->in_use, n, fl->in_use + n);
443                 }
444                 spin_unlock(&fl->lock);
445         }
446         fprintf(stderr, " all sizes %10d %10d %10d\n",
447                 total_used, total_free, total_used + total_free);
448 }
449 #endif  DEBUG
450
451 static void malloc_fork_prepare()
452 /*
453  * Prepare the malloc module for a fork by insuring that no thread is in a
454  * malloc critical section.
455  */
456 {
457     register int i;
458     
459     for (i = 0; i < NBUCKETS; i++) {
460         spin_lock(&malloc_free_list[i].lock);
461     }
462 }
463
464 static void malloc_fork_parent()
465 /*
466  * Called in the parent process after a fork() to resume normal operation.
467  */
468 {
469     register int i;
470
471     for (i = NBUCKETS-1; i >= 0; i--) {
472         spin_unlock(&malloc_free_list[i].lock);
473     }
474 }
475
476 static void malloc_fork_child()
477 /*
478  * Called in the child process after a fork() to resume normal operation.
479  */
480 {
481     register int i;
482
483     for (i = NBUCKETS-1; i >= 0; i--) {
484         spin_unlock(&malloc_free_list[i].lock);
485     }
486 }
487 \f
488
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);