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