Formerly ../hurd/hurdkill.c.~5~
[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.5  1994/06/04 01:48:44  roland
40  * entered into RCS
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 = 0; 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           h->next = fl->head;
167           fl->head = h;
168           h = (header_t) ((char *) h + size);
169         } while (--n != 0);
170 }
171
172 /* Declaration changed to standard one for GNU.  */
173 void *
174 malloc(size)
175         register size_t size;
176 {
177         register int i, n;
178         register free_list_t fl;
179         register header_t h;
180
181         if ((int) size < 0)             /* sanity check */
182                 return 0;
183         size += sizeof(union header);
184         /*
185          * Find smallest power-of-two block size
186          * big enough to hold requested size plus header.
187          */
188         i = 0;
189         n = MIN_SIZE;
190         while (n < size) {
191                 i += 1;
192                 n <<= 1;
193         }
194         ASSERT(i < NBUCKETS);
195         fl = &malloc_free_list[i];
196         spin_lock(&fl->lock);
197         h = fl->head;
198         if (h == 0) {
199                 /*
200                  * Free list is empty;
201                  * allocate more blocks.
202                  */
203                 more_memory(n, fl);
204                 h = fl->head;
205                 if (h == 0) {
206                         /*
207                          * Allocation failed.
208                          */
209                         spin_unlock(&fl->lock);
210                         return 0;
211                 }
212         }
213         /*
214          * Pop block from free list.
215          */
216         fl->head = h->next;
217 #ifdef  DEBUG
218         fl->in_use += 1;
219 #endif  DEBUG
220         spin_unlock(&fl->lock);
221         /*
222          * Store free list pointer in block header
223          * so we can figure out where it goes
224          * at free() time.
225          */
226         h->fl = fl;
227         /*
228          * Return pointer past the block header.
229          */
230         return ((char *) h) + sizeof(union header);
231 }
232
233 /* Declaration changed to standard one for GNU.  */
234 void
235 free(base)
236         void *base;
237 {
238         register header_t h;
239         register free_list_t fl;
240         register int i;
241
242         if (base == 0)
243                 return;
244         /*
245          * Find free list for block.
246          */
247         h = (header_t) (base - sizeof(union header));
248         fl = h->fl;
249         i = fl - malloc_free_list;
250         /*
251          * Sanity checks.
252          */
253         if (i < 0 || i >= NBUCKETS) {
254                 ASSERT(0 <= i && i < NBUCKETS);
255                 return;
256         }
257         if (fl != &malloc_free_list[i]) {
258                 ASSERT(fl == &malloc_free_list[i]);
259                 return;
260         }
261         /*
262          * Push block on free list.
263          */
264         spin_lock(&fl->lock);
265         h->next = fl->head;
266         fl->head = h;
267 #ifdef  DEBUG
268         fl->in_use -= 1;
269 #endif  DEBUG
270         spin_unlock(&fl->lock);
271         return;
272 }
273
274 /* Declaration changed to standard one for GNU.  */
275 void *
276 realloc(old_base, new_size)
277         void *old_base;
278         size_t new_size;
279 {
280         register header_t h;
281         register free_list_t fl;
282         register int i;
283         unsigned int old_size;
284         char *new_base;
285
286         if (old_base == 0)
287           return malloc (new_size);
288
289         /*
290          * Find size of old block.
291          */
292         h = (header_t) (old_base - sizeof(union header));
293         fl = h->fl;
294         i = fl - malloc_free_list;
295         /*
296          * Sanity checks.
297          */
298         if (i < 0 || i >= NBUCKETS) {
299                 ASSERT(0 <= i && i < NBUCKETS);
300                 return 0;
301         }
302         if (fl != &malloc_free_list[i]) {
303                 ASSERT(fl == &malloc_free_list[i]);
304                 return 0;
305         }
306         /*
307          * Free list with index i contains blocks of size 2^(i+3) including header.
308          */
309         old_size = (1 << (i+3)) - sizeof(union header);
310         /*
311          * Allocate new block, copy old bytes, and free old block.
312          */
313         new_base = malloc(new_size);
314         if (new_base != 0)
315                 bcopy(old_base, new_base, (int) (old_size < new_size ? old_size : new_size));
316         free(old_base);
317         return new_base;
318 }
319
320 #ifdef  DEBUG
321 void
322 print_malloc_free_list()
323 {
324         register int i, size;
325         register free_list_t fl;
326         register int n;
327         register header_t h;
328         int total_used = 0;
329         int total_free = 0;
330
331         fprintf(stderr, "      Size     In Use       Free      Total\n");
332         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
333              i < NBUCKETS;
334              i += 1, size <<= 1, fl += 1) {
335                 spin_lock(&fl->lock);
336                 if (fl->in_use != 0 || fl->head != 0) {
337                         total_used += fl->in_use * size;
338                         for (n = 0, h = fl->head; h != 0; h = h->next, n += 1)
339                                 ;
340                         total_free += n * size;
341                         fprintf(stderr, "%10d %10d %10d %10d\n",
342                                 size, fl->in_use, n, fl->in_use + n);
343                 }
344                 spin_unlock(&fl->lock);
345         }
346         fprintf(stderr, " all sizes %10d %10d %10d\n",
347                 total_used, total_free, total_used + total_free);
348 }
349 #endif  DEBUG
350
351 static void malloc_fork_prepare()
352 /*
353  * Prepare the malloc module for a fork by insuring that no thread is in a
354  * malloc critical section.
355  */
356 {
357     register int i;
358     
359     for (i = 0; i < NBUCKETS; i++) {
360         spin_lock(&malloc_free_list[i].lock);
361     }
362 }
363
364 static void malloc_fork_parent()
365 /*
366  * Called in the parent process after a fork() to resume normal operation.
367  */
368 {
369     register int i;
370
371     for (i = NBUCKETS-1; i >= 0; i--) {
372         spin_unlock(&malloc_free_list[i].lock);
373     }
374 }
375
376 static void malloc_fork_child()
377 /*
378  * Called in the child process after a fork() to resume normal operation.
379  */
380 {
381     register int i;
382
383     for (i = NBUCKETS-1; i >= 0; i--) {
384         spin_unlock(&malloc_free_list[i].lock);
385     }
386 }