Formerly ../hurd/hurdmalloc.c.~4~
[kopensolaris-gnu/glibc.git] / hurd / hurdmalloc.c
1 #include <stdlib.h>
2 #include "hurdmalloc.h"         /* XXX see that file */
3
4 #include <gnu-stabs.h>
5 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
6 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
7 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
8 text_set_element (_hurd_preinit_hook, malloc_init);
9
10
11 /* 
12  * Mach Operating System
13  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
14  * All Rights Reserved.
15  * 
16  * Permission to use, copy, modify and distribute this software and its
17  * documentation is hereby granted, provided that both the copyright
18  * notice and this permission notice appear in all copies of the
19  * software, derivative works or modified versions, and any portions
20  * thereof, and that both notices appear in supporting documentation.
21  * 
22  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
23  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
24  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
25  * 
26  * Carnegie Mellon requests users of this software to return to
27  * 
28  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
29  *  School of Computer Science
30  *  Carnegie Mellon University
31  *  Pittsburgh PA 15213-3890
32  * 
33  * any improvements or extensions that they make and grant Carnegie Mellon
34  * the rights to redistribute these changes.
35  */
36 /*
37  * HISTORY
38  * $Log$
39  * Revision 1.4  1994/06/01 01:10:11  roland
40  * Formerly ../hurd/hurdmalloc.c.~4~
41  *
42  * Revision 2.7  91/05/14  17:57:34  mrt
43  *      Correcting copyright
44  * 
45  * Revision 2.6  91/02/14  14:20:26  mrt
46  *      Added new Mach copyright
47  *      [91/02/13  12:41:21  mrt]
48  * 
49  * Revision 2.5  90/11/05  14:37:33  rpd
50  *      Added malloc_fork* code.
51  *      [90/11/02            rwd]
52  * 
53  *      Add spin_lock_t.
54  *      [90/10/31            rwd]
55  * 
56  * Revision 2.4  90/08/07  14:31:28  rpd
57  *      Removed RCS keyword nonsense.
58  * 
59  * Revision 2.3  90/06/02  15:14:00  rpd
60  *      Converted to new IPC.
61  *      [90/03/20  20:56:57  rpd]
62  * 
63  * Revision 2.2  89/12/08  19:53:59  rwd
64  *      Removed conditionals.
65  *      [89/10/23            rwd]
66  * 
67  * Revision 2.1  89/08/03  17:09:46  rwd
68  * Created.
69  * 
70  *
71  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
72  *      Changed realloc() to copy min(old size, new size) bytes.
73  *      Bug found by Mike Kupfer at Olivetti.
74  */
75 /*
76  *      File:   malloc.c
77  *      Author: Eric Cooper, Carnegie Mellon University
78  *      Date:   July, 1988
79  *
80  *      Memory allocator for use with multiple threads.
81  */
82
83 \f
84 #include <cthreads.h>
85 #include "cthread_internals.h"
86
87 /*
88  * C library imports:
89  */
90 extern bcopy();
91
92 /*
93  * Structure of memory block header.
94  * When free, next points to next block on free list.
95  * When allocated, fl points to free list.
96  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
97  */
98 typedef union header {
99         union header *next;
100         struct free_list *fl;
101 } *header_t;
102
103 #define MIN_SIZE        8       /* minimum block size */
104
105 typedef struct free_list {
106         spin_lock_t lock;       /* spin lock for mutual exclusion */
107         header_t head;          /* head of free list for this size */
108 #ifdef  DEBUG
109         int in_use;             /* # mallocs - # frees */
110 #endif  DEBUG
111 } *free_list_t;
112
113 /*
114  * Free list with index i contains blocks of size 2^(i+3) including header.
115  * Smallest block size is 8, with 4 bytes available to user.
116  * Size argument to malloc is a signed integer for sanity checking,
117  * so largest block size is 2^31.
118  */
119 #define NBUCKETS        29
120
121 static struct free_list malloc_free_list[NBUCKETS];
122
123 /* Initialization just sets everything to zero, but might be necessary on a
124    machine where spin_lock_init does otherwise, and is necessary when
125    running an executable that was written by something like Emacs's unexec.
126    It preserves the values of data variables like malloc_free_list, but
127    does not save the vm_allocate'd space allocated by this malloc.  */
128
129 static void
130 malloc_init (void)
131 {
132   int i;
133   for (i = i; i < NBUCKETS; ++i)
134     {
135       spin_lock_init (&malloc_free_list[i].lock);
136       malloc_free_list[i].head = NULL;
137 #ifdef DEBUG
138       malloc_free_list[i].in_use = 0;
139 #endif
140     }
141 }
142
143 static void
144 more_memory(size, fl)
145         int size;
146         register free_list_t fl;
147 {
148         register int amount;
149         register int n;
150         vm_address_t where;
151         register header_t h;
152         kern_return_t r;
153
154         if (size <= vm_page_size) {
155                 amount = vm_page_size;
156                 n = vm_page_size / size;
157                 /*
158                  * We lose vm_page_size - n*size bytes here.  */
159         } else {
160                 amount = size;
161                 n = 1;
162         }
163         MACH_CALL(vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE), r);
164         h = (header_t) where;
165         do {
166           spin_lock_init (&h->lock);
167           h->next = fl->head;
168           fl->head = h;
169           h = (header_t) ((char *) h + size);
170         } while (--n != 0);
171 }
172
173 /* Declaration changed to standard one for GNU.  */
174 void *
175 malloc(size)
176         register size_t size;
177 {
178         register int i, n;
179         register free_list_t fl;
180         register header_t h;
181
182         if ((int) size < 0)             /* sanity check */
183                 return 0;
184         size += sizeof(union header);
185         /*
186          * Find smallest power-of-two block size
187          * big enough to hold requested size plus header.
188          */
189         i = 0;
190         n = MIN_SIZE;
191         while (n < size) {
192                 i += 1;
193                 n <<= 1;
194         }
195         ASSERT(i < NBUCKETS);
196         fl = &malloc_free_list[i];
197         spin_lock(&fl->lock);
198         h = fl->head;
199         if (h == 0) {
200                 /*
201                  * Free list is empty;
202                  * allocate more blocks.
203                  */
204                 more_memory(n, fl);
205                 h = fl->head;
206                 if (h == 0) {
207                         /*
208                          * Allocation failed.
209                          */
210                         spin_unlock(&fl->lock);
211                         return 0;
212                 }
213         }
214         /*
215          * Pop block from free list.
216          */
217         fl->head = h->next;
218 #ifdef  DEBUG
219         fl->in_use += 1;
220 #endif  DEBUG
221         spin_unlock(&fl->lock);
222         /*
223          * Store free list pointer in block header
224          * so we can figure out where it goes
225          * at free() time.
226          */
227         h->fl = fl;
228         /*
229          * Return pointer past the block header.
230          */
231         return ((char *) h) + sizeof(union header);
232 }
233
234 /* Declaration changed to standard one for GNU.  */
235 void
236 free(base)
237         void *base;
238 {
239         register header_t h;
240         register free_list_t fl;
241         register int i;
242
243         if (base == 0)
244                 return;
245         /*
246          * Find free list for block.
247          */
248         h = (header_t) (base - sizeof(union header));
249         fl = h->fl;
250         i = fl - malloc_free_list;
251         /*
252          * Sanity checks.
253          */
254         if (i < 0 || i >= NBUCKETS) {
255                 ASSERT(0 <= i && i < NBUCKETS);
256                 return;
257         }
258         if (fl != &malloc_free_list[i]) {
259                 ASSERT(fl == &malloc_free_list[i]);
260                 return;
261         }
262         /*
263          * Push block on free list.
264          */
265         spin_lock(&fl->lock);
266         h->next = fl->head;
267         fl->head = h;
268 #ifdef  DEBUG
269         fl->in_use -= 1;
270 #endif  DEBUG
271         spin_unlock(&fl->lock);
272         return;
273 }
274
275 /* Declaration changed to standard one for GNU.  */
276 void *
277 realloc(old_base, new_size)
278         void *old_base;
279         size_t new_size;
280 {
281         register header_t h;
282         register free_list_t fl;
283         register int i;
284         unsigned int old_size;
285         char *new_base;
286
287         if (old_base == 0)
288           return malloc (new_size);
289
290         /*
291          * Find size of old block.
292          */
293         h = (header_t) (old_base - sizeof(union header));
294         fl = h->fl;
295         i = fl - malloc_free_list;
296         /*
297          * Sanity checks.
298          */
299         if (i < 0 || i >= NBUCKETS) {
300                 ASSERT(0 <= i && i < NBUCKETS);
301                 return 0;
302         }
303         if (fl != &malloc_free_list[i]) {
304                 ASSERT(fl == &malloc_free_list[i]);
305                 return 0;
306         }
307         /*
308          * Free list with index i contains blocks of size 2^(i+3) including header.
309          */
310         old_size = (1 << (i+3)) - sizeof(union header);
311         /*
312          * Allocate new block, copy old bytes, and free old block.
313          */
314         new_base = malloc(new_size);
315         if (new_base != 0)
316                 bcopy(old_base, new_base, (int) (old_size < new_size ? old_size : new_size));
317         free(old_base);
318         return new_base;
319 }
320
321 #ifdef  DEBUG
322 void
323 print_malloc_free_list()
324 {
325         register int i, size;
326         register free_list_t fl;
327         register int n;
328         register header_t h;
329         int total_used = 0;
330         int total_free = 0;
331
332         fprintf(stderr, "      Size     In Use       Free      Total\n");
333         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
334              i < NBUCKETS;
335              i += 1, size <<= 1, fl += 1) {
336                 spin_lock(&fl->lock);
337                 if (fl->in_use != 0 || fl->head != 0) {
338                         total_used += fl->in_use * size;
339                         for (n = 0, h = fl->head; h != 0; h = h->next, n += 1)
340                                 ;
341                         total_free += n * size;
342                         fprintf(stderr, "%10d %10d %10d %10d\n",
343                                 size, fl->in_use, n, fl->in_use + n);
344                 }
345                 spin_unlock(&fl->lock);
346         }
347         fprintf(stderr, " all sizes %10d %10d %10d\n",
348                 total_used, total_free, total_used + total_free);
349 }
350 #endif  DEBUG
351
352 static void malloc_fork_prepare()
353 /*
354  * Prepare the malloc module for a fork by insuring that no thread is in a
355  * malloc critical section.
356  */
357 {
358     register int i;
359     
360     for (i = 0; i < NBUCKETS; i++) {
361         spin_lock(&malloc_free_list[i].lock);
362     }
363 }
364
365 static void malloc_fork_parent()
366 /*
367  * Called in the parent process after a fork() to resume normal operation.
368  */
369 {
370     register int i;
371
372     for (i = NBUCKETS-1; i >= 0; i--) {
373         spin_unlock(&malloc_free_list[i].lock);
374     }
375 }
376
377 static void malloc_fork_child()
378 /*
379  * Called in the child process after a fork() to resume normal operation.
380  */
381 {
382     register int i;
383
384     for (i = NBUCKETS-1; i >= 0; i--) {
385         spin_unlock(&malloc_free_list[i].lock);
386     }
387 }