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