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