Don't install sys/xattr.h
[kopensolaris-gnu/glibc.git] / hurd / hurdmalloc.c
1 #include <stdlib.h>
2 #include <string.h>
3
4 #include "hurdmalloc.h"         /* XXX see that file */
5
6 #include <mach.h>
7 #define vm_allocate __vm_allocate
8 #define vm_page_size __vm_page_size
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  * (pre-GNU) HISTORY
37  *
38  * Revision 2.7  91/05/14  17:57:34  mrt
39  *      Correcting copyright
40  *
41  * Revision 2.6  91/02/14  14:20:26  mrt
42  *      Added new Mach copyright
43  *      [91/02/13  12:41:21  mrt]
44  *
45  * Revision 2.5  90/11/05  14:37:33  rpd
46  *      Added malloc_fork* code.
47  *      [90/11/02            rwd]
48  *
49  *      Add spin_lock_t.
50  *      [90/10/31            rwd]
51  *
52  * Revision 2.4  90/08/07  14:31:28  rpd
53  *      Removed RCS keyword nonsense.
54  *
55  * Revision 2.3  90/06/02  15:14:00  rpd
56  *      Converted to new IPC.
57  *      [90/03/20  20:56:57  rpd]
58  *
59  * Revision 2.2  89/12/08  19:53:59  rwd
60  *      Removed conditionals.
61  *      [89/10/23            rwd]
62  *
63  * Revision 2.1  89/08/03  17:09:46  rwd
64  * Created.
65  *
66  *
67  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
68  *      Changed realloc() to copy min(old size, new size) bytes.
69  *      Bug found by Mike Kupfer at Olivetti.
70  */
71 /*
72  *      File:   malloc.c
73  *      Author: Eric Cooper, Carnegie Mellon University
74  *      Date:   July, 1988
75  *
76  *      Memory allocator for use with multiple threads.
77  */
78
79 \f
80 #include <assert.h>
81
82 #include <cthreads.h>
83
84 #define MCHECK
85
86 /*
87  * Structure of memory block header.
88  * When free, next points to next block on free list.
89  * When allocated, fl points to free list.
90  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
91  */
92
93 #define CHECK_BUSY  0x8a3c743e
94 #define CHECK_FREE  0x66688b92
95
96 #ifdef MCHECK
97
98 typedef struct header {
99   long check;
100   union {
101     struct header *next;
102     struct free_list *fl;
103   } u;
104 } *header_t;
105
106 #define HEADER_SIZE sizeof (struct header)
107 #define HEADER_NEXT(h) ((h)->u.next)
108 #define HEADER_FREE(h) ((h)->u.fl)
109 #define HEADER_CHECK(h) ((h)->check)
110 #define MIN_SIZE        16
111 #define LOG2_MIN_SIZE   4
112
113 #else /* ! MCHECK */
114
115 typedef union header {
116         union header *next;
117         struct free_list *fl;
118 } *header_t;
119
120 #define HEADER_SIZE sizeof (union header)
121 #define HEADER_NEXT(h) ((h)->next)
122 #define HEADER_FREE(h) ((h)->fl)
123 #define MIN_SIZE        8       /* minimum block size */
124 #define LOG2_MIN_SIZE   3
125
126 #endif /* MCHECK */
127
128 typedef struct free_list {
129         spin_lock_t lock;       /* spin lock for mutual exclusion */
130         header_t head;          /* head of free list for this size */
131 #ifdef  DEBUG
132         int in_use;             /* # mallocs - # frees */
133 #endif  /* DEBUG */
134 } *free_list_t;
135
136 /*
137  * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
138  * including header.  Smallest block size is MIN_SIZE, with MIN_SIZE -
139  * HEADER_SIZE bytes available to user.  Size argument to malloc is a signed
140  * integer for sanity checking, so largest block size is 2^31.
141  */
142 #define NBUCKETS        29
143
144 static struct free_list malloc_free_list[NBUCKETS];
145
146 /* Initialization just sets everything to zero, but might be necessary on a
147    machine where spin_lock_init does otherwise, and is necessary when
148    running an executable that was written by something like Emacs's unexec.
149    It preserves the values of data variables like malloc_free_list, but
150    does not save the vm_allocate'd space allocated by this malloc.  */
151
152 static void
153 malloc_init (void)
154 {
155   int i;
156   for (i = 0; i < NBUCKETS; ++i)
157     {
158       spin_lock_init (&malloc_free_list[i].lock);
159       malloc_free_list[i].head = NULL;
160 #ifdef DEBUG
161       malloc_free_list[i].in_use = 0;
162 #endif
163     }
164
165   /* This not only suppresses a `defined but not used' warning,
166      but it is ABSOLUTELY NECESSARY to avoid the hyperclever
167      compiler from "optimizing out" the entire function!  */
168   (void) &malloc_init;
169 }
170
171 static void
172 more_memory(int size, free_list_t fl)
173 {
174         register int amount;
175         register int n;
176         vm_address_t where;
177         register header_t h;
178         kern_return_t r;
179
180         if (size <= vm_page_size) {
181                 amount = vm_page_size;
182                 n = vm_page_size / size;
183                 /* We lose vm_page_size - n*size bytes here.  */
184         } else {
185                 amount = size;
186                 n = 1;
187         }
188
189         r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
190         assert_perror (r);
191
192         h = (header_t) where;
193         do {
194                 HEADER_NEXT (h) = fl->head;
195 #ifdef MCHECK
196                 HEADER_CHECK (h) = CHECK_FREE;
197 #endif
198                 fl->head = h;
199                 h = (header_t) ((char *) h + size);
200         } while (--n != 0);
201 }
202
203 /* Declaration changed to standard one for GNU.  */
204 void *
205 malloc(size)
206         register size_t size;
207 {
208         register int i, n;
209         register free_list_t fl;
210         register header_t h;
211
212         if ((int) size < 0)             /* sanity check */
213                 return 0;
214         size += HEADER_SIZE;
215         /*
216          * Find smallest power-of-two block size
217          * big enough to hold requested size plus header.
218          */
219         i = 0;
220         n = MIN_SIZE;
221         while (n < size) {
222                 i += 1;
223                 n <<= 1;
224         }
225         ASSERT(i < NBUCKETS);
226         fl = &malloc_free_list[i];
227         spin_lock(&fl->lock);
228         h = fl->head;
229         if (h == 0) {
230                 /*
231                  * Free list is empty;
232                  * allocate more blocks.
233                  */
234                 more_memory(n, fl);
235                 h = fl->head;
236                 if (h == 0) {
237                         /*
238                          * Allocation failed.
239                          */
240                         spin_unlock(&fl->lock);
241                         return 0;
242                 }
243         }
244         /*
245          * Pop block from free list.
246          */
247         fl->head = HEADER_NEXT (h);
248
249 #ifdef MCHECK
250         assert (HEADER_CHECK (h) == CHECK_FREE);
251         HEADER_CHECK (h) = CHECK_BUSY;
252 #endif
253
254 #ifdef  DEBUG
255         fl->in_use += 1;
256 #endif  /* DEBUG */
257         spin_unlock(&fl->lock);
258         /*
259          * Store free list pointer in block header
260          * so we can figure out where it goes
261          * at free() time.
262          */
263         HEADER_FREE (h) = fl;
264         /*
265          * Return pointer past the block header.
266          */
267         return ((char *) h) + HEADER_SIZE;
268 }
269
270 /* Declaration changed to standard one for GNU.  */
271 void
272 free(base)
273         void *base;
274 {
275         register header_t h;
276         register free_list_t fl;
277         register int i;
278
279         if (base == 0)
280                 return;
281         /*
282          * Find free list for block.
283          */
284         h = (header_t) (base - HEADER_SIZE);
285
286 #ifdef MCHECK
287         assert (HEADER_CHECK (h) == CHECK_BUSY);
288 #endif
289
290         fl = HEADER_FREE (h);
291         i = fl - malloc_free_list;
292         /*
293          * Sanity checks.
294          */
295         if (i < 0 || i >= NBUCKETS) {
296                 ASSERT(0 <= i && i < NBUCKETS);
297                 return;
298         }
299         if (fl != &malloc_free_list[i]) {
300                 ASSERT(fl == &malloc_free_list[i]);
301                 return;
302         }
303         /*
304          * Push block on free list.
305          */
306         spin_lock(&fl->lock);
307         HEADER_NEXT (h) = fl->head;
308 #ifdef MCHECK
309         HEADER_CHECK (h) = CHECK_FREE;
310 #endif
311         fl->head = h;
312 #ifdef  DEBUG
313         fl->in_use -= 1;
314 #endif  /* DEBUG */
315         spin_unlock(&fl->lock);
316         return;
317 }
318
319 /* Declaration changed to standard one for GNU.  */
320 void *
321 realloc(old_base, new_size)
322         void *old_base;
323         size_t new_size;
324 {
325         register header_t h;
326         register free_list_t fl;
327         register int i;
328         unsigned int old_size;
329         char *new_base;
330
331         if (old_base == 0)
332           return malloc (new_size);
333
334         /*
335          * Find size of old block.
336          */
337         h = (header_t) (old_base - HEADER_SIZE);
338 #ifdef MCHECK
339         assert (HEADER_CHECK (h) == CHECK_BUSY);
340 #endif
341         fl = HEADER_FREE (h);
342         i = fl - malloc_free_list;
343         /*
344          * Sanity checks.
345          */
346         if (i < 0 || i >= NBUCKETS) {
347                 ASSERT(0 <= i && i < NBUCKETS);
348                 return 0;
349         }
350         if (fl != &malloc_free_list[i]) {
351                 ASSERT(fl == &malloc_free_list[i]);
352                 return 0;
353         }
354         /*
355          * Free list with index i contains blocks of size
356          * 2 ^ (i + * LOG2_MIN_SIZE) including header.
357          */
358         old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
359
360         if (new_size <= old_size
361             && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
362           /* The new size still fits in the same block, and wouldn't fit in
363              the next smaller block!  */
364           return old_base;
365
366         /*
367          * Allocate new block, copy old bytes, and free old block.
368          */
369         new_base = malloc(new_size);
370         if (new_base)
371           memcpy (new_base, old_base,
372                   (int) (old_size < new_size ? old_size : new_size));
373
374         if (new_base || new_size == 0)
375           /* Free OLD_BASE, but only if the malloc didn't fail.  */
376           free (old_base);
377
378         return new_base;
379 }
380
381 #ifdef  DEBUG
382 void
383 print_malloc_free_list()
384 {
385         register int i, size;
386         register free_list_t fl;
387         register int n;
388         register header_t h;
389         int total_used = 0;
390         int total_free = 0;
391
392         fprintf(stderr, "      Size     In Use       Free      Total\n");
393         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
394              i < NBUCKETS;
395              i += 1, size <<= 1, fl += 1) {
396                 spin_lock(&fl->lock);
397                 if (fl->in_use != 0 || fl->head != 0) {
398                         total_used += fl->in_use * size;
399                         for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
400                                 ;
401                         total_free += n * size;
402                         fprintf(stderr, "%10d %10d %10d %10d\n",
403                                 size, fl->in_use, n, fl->in_use + n);
404                 }
405                 spin_unlock(&fl->lock);
406         }
407         fprintf(stderr, " all sizes %10d %10d %10d\n",
408                 total_used, total_free, total_used + total_free);
409 }
410 #endif  /* DEBUG */
411
412 static void
413 malloc_fork_prepare(void)
414 /*
415  * Prepare the malloc module for a fork by insuring that no thread is in a
416  * malloc critical section.
417  */
418 {
419     register int i;
420
421     for (i = 0; i < NBUCKETS; i++) {
422         spin_lock(&malloc_free_list[i].lock);
423     }
424 }
425
426 static void
427 malloc_fork_parent(void)
428 /*
429  * Called in the parent process after a fork() to resume normal operation.
430  */
431 {
432     register int i;
433
434     for (i = NBUCKETS-1; i >= 0; i--) {
435         spin_unlock(&malloc_free_list[i].lock);
436     }
437 }
438
439 static void
440 malloc_fork_child(void)
441 /*
442  * Called in the child process after a fork() to resume normal operation.
443  */
444 {
445     register int i;
446
447     for (i = NBUCKETS-1; i >= 0; i--) {
448         spin_unlock(&malloc_free_list[i].lock);
449     }
450 }
451 \f
452
453 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
454 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
455 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
456 text_set_element (_hurd_preinit_hook, malloc_init);