New file.
[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.10  1995/02/13 22:04:34  roland
41  * (malloc_init): Add self reference to avoid not only the `defined but not
42  * used' warning, but also to avoid GCC optimizing out the entire function
43  * (!).
44  *
45  * Revision 1.9  1995/02/13  16:36:08  roland
46  * Include string.h; #define bcopy using memcpy.
47  *
48  * Revision 1.8  1995/02/03  01:54:21  roland
49  * Remove bogus bcopy decl.
50  *
51  * Revision 1.7  1995/01/26  04:22:02  roland
52  * Don't include gnu-stabs.h.
53  *
54  * Revision 1.6  1994/12/07  19:41:26  roland
55  * (vm_allocate, vm_page_size): #define these to __ names at top.
56  *
57  * Revision 1.5  1994/06/04  01:48:44  roland
58  * entered into RCS
59  *
60  * Revision 2.7  91/05/14  17:57:34  mrt
61  *      Correcting copyright
62  * 
63  * Revision 2.6  91/02/14  14:20:26  mrt
64  *      Added new Mach copyright
65  *      [91/02/13  12:41:21  mrt]
66  * 
67  * Revision 2.5  90/11/05  14:37:33  rpd
68  *      Added malloc_fork* code.
69  *      [90/11/02            rwd]
70  * 
71  *      Add spin_lock_t.
72  *      [90/10/31            rwd]
73  * 
74  * Revision 2.4  90/08/07  14:31:28  rpd
75  *      Removed RCS keyword nonsense.
76  * 
77  * Revision 2.3  90/06/02  15:14:00  rpd
78  *      Converted to new IPC.
79  *      [90/03/20  20:56:57  rpd]
80  * 
81  * Revision 2.2  89/12/08  19:53:59  rwd
82  *      Removed conditionals.
83  *      [89/10/23            rwd]
84  * 
85  * Revision 2.1  89/08/03  17:09:46  rwd
86  * Created.
87  * 
88  *
89  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
90  *      Changed realloc() to copy min(old size, new size) bytes.
91  *      Bug found by Mike Kupfer at Olivetti.
92  */
93 /*
94  *      File:   malloc.c
95  *      Author: Eric Cooper, Carnegie Mellon University
96  *      Date:   July, 1988
97  *
98  *      Memory allocator for use with multiple threads.
99  */
100
101 \f
102 #include <cthreads.h>
103 #include "cthread_internals.h"
104
105
106 /*
107  * Structure of memory block header.
108  * When free, next points to next block on free list.
109  * When allocated, fl points to free list.
110  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
111  */
112 typedef union header {
113         union header *next;
114         struct free_list *fl;
115 } *header_t;
116
117 #define MIN_SIZE        8       /* minimum block size */
118
119 typedef struct free_list {
120         spin_lock_t lock;       /* spin lock for mutual exclusion */
121         header_t head;          /* head of free list for this size */
122 #ifdef  DEBUG
123         int in_use;             /* # mallocs - # frees */
124 #endif  DEBUG
125 } *free_list_t;
126
127 /*
128  * Free list with index i contains blocks of size 2^(i+3) including header.
129  * Smallest block size is 8, with 4 bytes available to user.
130  * Size argument to malloc is a signed integer for sanity checking,
131  * so largest block size is 2^31.
132  */
133 #define NBUCKETS        29
134
135 static struct free_list malloc_free_list[NBUCKETS];
136
137 /* Initialization just sets everything to zero, but might be necessary on a
138    machine where spin_lock_init does otherwise, and is necessary when
139    running an executable that was written by something like Emacs's unexec.
140    It preserves the values of data variables like malloc_free_list, but
141    does not save the vm_allocate'd space allocated by this malloc.  */
142
143 static void
144 malloc_init (void)
145 {
146   int i;
147   for (i = 0; i < NBUCKETS; ++i)
148     {
149       spin_lock_init (&malloc_free_list[i].lock);
150       malloc_free_list[i].head = NULL;
151 #ifdef DEBUG
152       malloc_free_list[i].in_use = 0;
153 #endif
154     }
155
156   /* This not only suppresses a `defined but not used' warning,
157      but it is ABSOLUTELY NECESSARY to avoid the hyperclever
158      compiler from "optimizing out" the entire function!  */
159   (void) &malloc_init;
160 }
161
162 static void
163 more_memory(size, fl)
164         int size;
165         register free_list_t fl;
166 {
167         register int amount;
168         register int n;
169         vm_address_t where;
170         register header_t h;
171         kern_return_t r;
172
173         if (size <= vm_page_size) {
174                 amount = vm_page_size;
175                 n = vm_page_size / size;
176                 /*
177                  * We lose vm_page_size - n*size bytes here.  */
178         } else {
179                 amount = size;
180                 n = 1;
181         }
182         MACH_CALL(vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE), r);
183         h = (header_t) where;
184         do {
185           h->next = fl->head;
186           fl->head = h;
187           h = (header_t) ((char *) h + size);
188         } while (--n != 0);
189 }
190
191 /* Declaration changed to standard one for GNU.  */
192 void *
193 malloc(size)
194         register size_t size;
195 {
196         register int i, n;
197         register free_list_t fl;
198         register header_t h;
199
200         if ((int) size < 0)             /* sanity check */
201                 return 0;
202         size += sizeof(union header);
203         /*
204          * Find smallest power-of-two block size
205          * big enough to hold requested size plus header.
206          */
207         i = 0;
208         n = MIN_SIZE;
209         while (n < size) {
210                 i += 1;
211                 n <<= 1;
212         }
213         ASSERT(i < NBUCKETS);
214         fl = &malloc_free_list[i];
215         spin_lock(&fl->lock);
216         h = fl->head;
217         if (h == 0) {
218                 /*
219                  * Free list is empty;
220                  * allocate more blocks.
221                  */
222                 more_memory(n, fl);
223                 h = fl->head;
224                 if (h == 0) {
225                         /*
226                          * Allocation failed.
227                          */
228                         spin_unlock(&fl->lock);
229                         return 0;
230                 }
231         }
232         /*
233          * Pop block from free list.
234          */
235         fl->head = h->next;
236 #ifdef  DEBUG
237         fl->in_use += 1;
238 #endif  DEBUG
239         spin_unlock(&fl->lock);
240         /*
241          * Store free list pointer in block header
242          * so we can figure out where it goes
243          * at free() time.
244          */
245         h->fl = fl;
246         /*
247          * Return pointer past the block header.
248          */
249         return ((char *) h) + sizeof(union header);
250 }
251
252 /* Declaration changed to standard one for GNU.  */
253 void
254 free(base)
255         void *base;
256 {
257         register header_t h;
258         register free_list_t fl;
259         register int i;
260
261         if (base == 0)
262                 return;
263         /*
264          * Find free list for block.
265          */
266         h = (header_t) (base - sizeof(union header));
267         fl = h->fl;
268         i = fl - malloc_free_list;
269         /*
270          * Sanity checks.
271          */
272         if (i < 0 || i >= NBUCKETS) {
273                 ASSERT(0 <= i && i < NBUCKETS);
274                 return;
275         }
276         if (fl != &malloc_free_list[i]) {
277                 ASSERT(fl == &malloc_free_list[i]);
278                 return;
279         }
280         /*
281          * Push block on free list.
282          */
283         spin_lock(&fl->lock);
284         h->next = fl->head;
285         fl->head = h;
286 #ifdef  DEBUG
287         fl->in_use -= 1;
288 #endif  DEBUG
289         spin_unlock(&fl->lock);
290         return;
291 }
292
293 /* Declaration changed to standard one for GNU.  */
294 void *
295 realloc(old_base, new_size)
296         void *old_base;
297         size_t new_size;
298 {
299         register header_t h;
300         register free_list_t fl;
301         register int i;
302         unsigned int old_size;
303         char *new_base;
304
305         if (old_base == 0)
306           return malloc (new_size);
307
308         /*
309          * Find size of old block.
310          */
311         h = (header_t) (old_base - sizeof(union header));
312         fl = h->fl;
313         i = fl - malloc_free_list;
314         /*
315          * Sanity checks.
316          */
317         if (i < 0 || i >= NBUCKETS) {
318                 ASSERT(0 <= i && i < NBUCKETS);
319                 return 0;
320         }
321         if (fl != &malloc_free_list[i]) {
322                 ASSERT(fl == &malloc_free_list[i]);
323                 return 0;
324         }
325         /*
326          * Free list with index i contains blocks of size 2^(i+3) including header.
327          */
328         old_size = (1 << (i+3)) - sizeof(union header);
329         /*
330          * Allocate new block, copy old bytes, and free old block.
331          */
332         new_base = malloc(new_size);
333         if (new_base != 0)
334                 bcopy(old_base, new_base, (int) (old_size < new_size ? old_size : new_size));
335         free(old_base);
336         return new_base;
337 }
338
339 #ifdef  DEBUG
340 void
341 print_malloc_free_list()
342 {
343         register int i, size;
344         register free_list_t fl;
345         register int n;
346         register header_t h;
347         int total_used = 0;
348         int total_free = 0;
349
350         fprintf(stderr, "      Size     In Use       Free      Total\n");
351         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
352              i < NBUCKETS;
353              i += 1, size <<= 1, fl += 1) {
354                 spin_lock(&fl->lock);
355                 if (fl->in_use != 0 || fl->head != 0) {
356                         total_used += fl->in_use * size;
357                         for (n = 0, h = fl->head; h != 0; h = h->next, n += 1)
358                                 ;
359                         total_free += n * size;
360                         fprintf(stderr, "%10d %10d %10d %10d\n",
361                                 size, fl->in_use, n, fl->in_use + n);
362                 }
363                 spin_unlock(&fl->lock);
364         }
365         fprintf(stderr, " all sizes %10d %10d %10d\n",
366                 total_used, total_free, total_used + total_free);
367 }
368 #endif  DEBUG
369
370 static void malloc_fork_prepare()
371 /*
372  * Prepare the malloc module for a fork by insuring that no thread is in a
373  * malloc critical section.
374  */
375 {
376     register int i;
377     
378     for (i = 0; i < NBUCKETS; i++) {
379         spin_lock(&malloc_free_list[i].lock);
380     }
381 }
382
383 static void malloc_fork_parent()
384 /*
385  * Called in the parent process after a fork() to resume normal operation.
386  */
387 {
388     register int i;
389
390     for (i = NBUCKETS-1; i >= 0; i--) {
391         spin_unlock(&malloc_free_list[i].lock);
392     }
393 }
394
395 static void malloc_fork_child()
396 /*
397  * Called in the child process after a fork() to resume normal operation.
398  */
399 {
400     register int i;
401
402     for (i = NBUCKETS-1; i >= 0; i--) {
403         spin_unlock(&malloc_free_list[i].lock);
404     }
405 }
406 \f
407
408 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
409 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
410 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
411 text_set_element (_hurd_preinit_hook, malloc_init);