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