Remove bogus bcopy decl.
[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.8  1995/02/03 01:54:21  roland
37  * Remove bogus bcopy decl.
38  *
39  * Revision 1.7  1995/01/26  04:22:02  roland
40  * Don't include gnu-stabs.h.
41  *
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 /*
95  * Structure of memory block header.
96  * When free, next points to next block on free list.
97  * When allocated, fl points to free list.
98  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
99  */
100 typedef union header {
101         union header *next;
102         struct free_list *fl;
103 } *header_t;
104
105 #define MIN_SIZE        8       /* minimum block size */
106
107 typedef struct free_list {
108         spin_lock_t lock;       /* spin lock for mutual exclusion */
109         header_t head;          /* head of free list for this size */
110 #ifdef  DEBUG
111         int in_use;             /* # mallocs - # frees */
112 #endif  DEBUG
113 } *free_list_t;
114
115 /*
116  * Free list with index i contains blocks of size 2^(i+3) including header.
117  * Smallest block size is 8, with 4 bytes available to user.
118  * Size argument to malloc is a signed integer for sanity checking,
119  * so largest block size is 2^31.
120  */
121 #define NBUCKETS        29
122
123 static struct free_list malloc_free_list[NBUCKETS];
124
125 /* Initialization just sets everything to zero, but might be necessary on a
126    machine where spin_lock_init does otherwise, and is necessary when
127    running an executable that was written by something like Emacs's unexec.
128    It preserves the values of data variables like malloc_free_list, but
129    does not save the vm_allocate'd space allocated by this malloc.  */
130
131 static void
132 malloc_init (void)
133 {
134   int i;
135   for (i = 0; i < NBUCKETS; ++i)
136     {
137       spin_lock_init (&malloc_free_list[i].lock);
138       malloc_free_list[i].head = NULL;
139 #ifdef DEBUG
140       malloc_free_list[i].in_use = 0;
141 #endif
142     }
143 }
144
145 static void
146 more_memory(size, fl)
147         int size;
148         register free_list_t fl;
149 {
150         register int amount;
151         register int n;
152         vm_address_t where;
153         register header_t h;
154         kern_return_t r;
155
156         if (size <= vm_page_size) {
157                 amount = vm_page_size;
158                 n = vm_page_size / size;
159                 /*
160                  * We lose vm_page_size - n*size bytes here.  */
161         } else {
162                 amount = size;
163                 n = 1;
164         }
165         MACH_CALL(vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE), r);
166         h = (header_t) where;
167         do {
168           h->next = fl->head;
169           fl->head = h;
170           h = (header_t) ((char *) h + size);
171         } while (--n != 0);
172 }
173
174 /* Declaration changed to standard one for GNU.  */
175 void *
176 malloc(size)
177         register size_t size;
178 {
179         register int i, n;
180         register free_list_t fl;
181         register header_t h;
182
183         if ((int) size < 0)             /* sanity check */
184                 return 0;
185         size += sizeof(union header);
186         /*
187          * Find smallest power-of-two block size
188          * big enough to hold requested size plus header.
189          */
190         i = 0;
191         n = MIN_SIZE;
192         while (n < size) {
193                 i += 1;
194                 n <<= 1;
195         }
196         ASSERT(i < NBUCKETS);
197         fl = &malloc_free_list[i];
198         spin_lock(&fl->lock);
199         h = fl->head;
200         if (h == 0) {
201                 /*
202                  * Free list is empty;
203                  * allocate more blocks.
204                  */
205                 more_memory(n, fl);
206                 h = fl->head;
207                 if (h == 0) {
208                         /*
209                          * Allocation failed.
210                          */
211                         spin_unlock(&fl->lock);
212                         return 0;
213                 }
214         }
215         /*
216          * Pop block from free list.
217          */
218         fl->head = h->next;
219 #ifdef  DEBUG
220         fl->in_use += 1;
221 #endif  DEBUG
222         spin_unlock(&fl->lock);
223         /*
224          * Store free list pointer in block header
225          * so we can figure out where it goes
226          * at free() time.
227          */
228         h->fl = fl;
229         /*
230          * Return pointer past the block header.
231          */
232         return ((char *) h) + sizeof(union header);
233 }
234
235 /* Declaration changed to standard one for GNU.  */
236 void
237 free(base)
238         void *base;
239 {
240         register header_t h;
241         register free_list_t fl;
242         register int i;
243
244         if (base == 0)
245                 return;
246         /*
247          * Find free list for block.
248          */
249         h = (header_t) (base - sizeof(union header));
250         fl = h->fl;
251         i = fl - malloc_free_list;
252         /*
253          * Sanity checks.
254          */
255         if (i < 0 || i >= NBUCKETS) {
256                 ASSERT(0 <= i && i < NBUCKETS);
257                 return;
258         }
259         if (fl != &malloc_free_list[i]) {
260                 ASSERT(fl == &malloc_free_list[i]);
261                 return;
262         }
263         /*
264          * Push block on free list.
265          */
266         spin_lock(&fl->lock);
267         h->next = fl->head;
268         fl->head = h;
269 #ifdef  DEBUG
270         fl->in_use -= 1;
271 #endif  DEBUG
272         spin_unlock(&fl->lock);
273         return;
274 }
275
276 /* Declaration changed to standard one for GNU.  */
277 void *
278 realloc(old_base, new_size)
279         void *old_base;
280         size_t new_size;
281 {
282         register header_t h;
283         register free_list_t fl;
284         register int i;
285         unsigned int old_size;
286         char *new_base;
287
288         if (old_base == 0)
289           return malloc (new_size);
290
291         /*
292          * Find size of old block.
293          */
294         h = (header_t) (old_base - sizeof(union header));
295         fl = h->fl;
296         i = fl - malloc_free_list;
297         /*
298          * Sanity checks.
299          */
300         if (i < 0 || i >= NBUCKETS) {
301                 ASSERT(0 <= i && i < NBUCKETS);
302                 return 0;
303         }
304         if (fl != &malloc_free_list[i]) {
305                 ASSERT(fl == &malloc_free_list[i]);
306                 return 0;
307         }
308         /*
309          * Free list with index i contains blocks of size 2^(i+3) including header.
310          */
311         old_size = (1 << (i+3)) - sizeof(union header);
312         /*
313          * Allocate new block, copy old bytes, and free old block.
314          */
315         new_base = malloc(new_size);
316         if (new_base != 0)
317                 bcopy(old_base, new_base, (int) (old_size < new_size ? old_size : new_size));
318         free(old_base);
319         return new_base;
320 }
321
322 #ifdef  DEBUG
323 void
324 print_malloc_free_list()
325 {
326         register int i, size;
327         register free_list_t fl;
328         register int n;
329         register header_t h;
330         int total_used = 0;
331         int total_free = 0;
332
333         fprintf(stderr, "      Size     In Use       Free      Total\n");
334         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
335              i < NBUCKETS;
336              i += 1, size <<= 1, fl += 1) {
337                 spin_lock(&fl->lock);
338                 if (fl->in_use != 0 || fl->head != 0) {
339                         total_used += fl->in_use * size;
340                         for (n = 0, h = fl->head; h != 0; h = h->next, n += 1)
341                                 ;
342                         total_free += n * size;
343                         fprintf(stderr, "%10d %10d %10d %10d\n",
344                                 size, fl->in_use, n, fl->in_use + n);
345                 }
346                 spin_unlock(&fl->lock);
347         }
348         fprintf(stderr, " all sizes %10d %10d %10d\n",
349                 total_used, total_free, total_used + total_free);
350 }
351 #endif  DEBUG
352
353 static void malloc_fork_prepare()
354 /*
355  * Prepare the malloc module for a fork by insuring that no thread is in a
356  * malloc critical section.
357  */
358 {
359     register int i;
360     
361     for (i = 0; i < NBUCKETS; i++) {
362         spin_lock(&malloc_free_list[i].lock);
363     }
364 }
365
366 static void malloc_fork_parent()
367 /*
368  * Called in the parent process after a fork() to resume normal operation.
369  */
370 {
371     register int i;
372
373     for (i = NBUCKETS-1; i >= 0; i--) {
374         spin_unlock(&malloc_free_list[i].lock);
375     }
376 }
377
378 static void malloc_fork_child()
379 /*
380  * Called in the child process after a fork() to resume normal operation.
381  */
382 {
383     register int i;
384
385     for (i = NBUCKETS-1; i >= 0; i--) {
386         spin_unlock(&malloc_free_list[i].lock);
387     }
388 }
389 \f
390
391 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
392 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
393 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
394 text_set_element (_hurd_preinit_hook, malloc_init);