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