(get_myaddress): Avoid loopback interfaces, return loopback address
[kopensolaris-gnu/glibc.git] / hurd / hurdmalloc.c
1 #include <stdlib.h>
2 #include <string.h>
3
4 #define bcopy(s,d,n)    memcpy ((d), (s), (n)) /* No overlap handling.  */
5
6 #include "hurdmalloc.h"         /* XXX see that file */
7
8 #include <mach.h>
9 #define vm_allocate __vm_allocate
10 #define vm_page_size __vm_page_size
11
12 /* 
13  * Mach Operating System
14  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
15  * All Rights Reserved.
16  * 
17  * Permission to use, copy, modify and distribute this software and its
18  * documentation is hereby granted, provided that both the copyright
19  * notice and this permission notice appear in all copies of the
20  * software, derivative works or modified versions, and any portions
21  * thereof, and that both notices appear in supporting documentation.
22  * 
23  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
24  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
25  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
26  * 
27  * Carnegie Mellon requests users of this software to return to
28  * 
29  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
30  *  School of Computer Science
31  *  Carnegie Mellon University
32  *  Pittsburgh PA 15213-3890
33  * 
34  * any improvements or extensions that they make and grant Carnegie Mellon
35  * the rights to redistribute these changes.
36  */
37 /*
38  * HISTORY
39  * $Log$
40  * Revision 1.13  1996/12/20 01:32:01  drepper
41  * Update from main archive 961219
42  *
43  * Revision 1.12  1996/11/15 19:44:13  thomas
44  * Tue Nov 12 16:58:41 1996  Thomas Bushnell, n/BSG  <thomas@gnu.ai.mit.edu>
45  *
46  *      * mach/msg-destroy.c (mach_msg_destroy_port,
47  *      mach_msg_destroy_memory): Use prototype syntax.
48  *      * hurd/hurdmalloc.c (more_memory, malloc_fork_prepare,
49  *      malloc_fork_parent, malloc_fork_child): Likewise.
50  *
51  * Revision 1.11  1996/06/06 15:13:47  miles
52  * Changes to bring in line with the hurd libthreads/malloc.c:
53  *   (more_memory): Use assert_perror instead of MACH_CALL.
54  *   "cthread_internals.h": Include removed.
55  *   (realloc): Use LOG2_MIN_SIZE.
56  *   (LOG2_MIN_SIZE): New macro.
57  *   (realloc): Don't bother allocating a new block if the
58  *     new size request fits in the old one and doesn't waste any space.
59  *     Only free the old block if we successfully got a new one.
60  *   [MCHECK] (struct header): New type.
61  *   (union header): Only define if !MCHECK.
62  *   (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
63  *   [MCHECK] (MIN_SIZE): Add correct definition for this case.
64  *   (more_memory, malloc, free, realloc): Use above macros, and add
65  *     appropriate checks & frobs in MCHECK case.
66  *
67  * Revision 1.6  1996/03/07 21:13:08  miles
68  * (realloc):
69  *   Use LOG2_MIN_SIZE.
70  *   Don't bother allocating a new block if the new size request fits in the old
71  *     one and doesn't waste any space.
72  *   Only free the old block if we successfully got a new one.
73  * (LOG2_MIN_SIZE): New macro.
74  *
75  * Revision 1.5  1996/03/06 23:51:04  miles
76  * [MCHECK] (struct header): New type.
77  * (union header): Only define if !MCHECK.
78  * (HEADER_SIZE, HEADER_NEXT, HEADER_FREE, HEADER_CHECK): New macros.
79  * [MCHECK] (MIN_SIZE): Add correct definition for this case.
80  * (more_memory, malloc, free, realloc):
81  *   Use above macros, and add appropriate checks & frobs in MCHECK case.
82  *
83  * Revision 1.4  1994/05/05 11:21:42  roland
84  * entered into RCS
85  *
86  * Revision 2.7  91/05/14  17:57:34  mrt
87  *      Correcting copyright
88  *
89  * Revision 2.6  91/02/14  14:20:26  mrt
90  *      Added new Mach copyright
91  *      [91/02/13  12:41:21  mrt]
92  *
93  * Revision 2.5  90/11/05  14:37:33  rpd
94  *      Added malloc_fork* code.
95  *      [90/11/02            rwd]
96  *
97  *      Add spin_lock_t.
98  *      [90/10/31            rwd]
99  *
100  * Revision 2.4  90/08/07  14:31:28  rpd
101  *      Removed RCS keyword nonsense.
102  *
103  * Revision 2.3  90/06/02  15:14:00  rpd
104  *      Converted to new IPC.
105  *      [90/03/20  20:56:57  rpd]
106  *
107  * Revision 2.2  89/12/08  19:53:59  rwd
108  *      Removed conditionals.
109  *      [89/10/23            rwd]
110  *
111  * Revision 2.1  89/08/03  17:09:46  rwd
112  * Created.
113  *
114  *
115  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
116  *      Changed realloc() to copy min(old size, new size) bytes.
117  *      Bug found by Mike Kupfer at Olivetti.
118  */
119 /*
120  *      File:   malloc.c
121  *      Author: Eric Cooper, Carnegie Mellon University
122  *      Date:   July, 1988
123  *
124  *      Memory allocator for use with multiple threads.
125  */
126
127 \f
128 #include <assert.h>
129
130 #include <cthreads.h>
131
132 #define MCHECK
133
134 /*
135  * Structure of memory block header.
136  * When free, next points to next block on free list.
137  * When allocated, fl points to free list.
138  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
139  */
140
141 #define CHECK_BUSY  0x8a3c743e
142 #define CHECK_FREE  0x66688b92
143
144 #ifdef MCHECK
145
146 typedef struct header {
147   long check;
148   union {
149     struct header *next;
150     struct free_list *fl;
151   } u;
152 } *header_t;
153
154 #define HEADER_SIZE sizeof (struct header)
155 #define HEADER_NEXT(h) ((h)->u.next)
156 #define HEADER_FREE(h) ((h)->u.fl)
157 #define HEADER_CHECK(h) ((h)->check)
158 #define MIN_SIZE        16
159 #define LOG2_MIN_SIZE   4
160
161 #else /* ! MCHECK */
162
163 typedef union header {
164         union header *next;
165         struct free_list *fl;
166 } *header_t;
167
168 #define HEADER_SIZE sizeof (union header)
169 #define HEADER_NEXT(h) ((h)->next)
170 #define HEADER_FREE(h) ((h)->fl)
171 #define MIN_SIZE        8       /* minimum block size */
172 #define LOG2_MIN_SIZE   3
173
174 #endif /* MCHECK */
175
176 typedef struct free_list {
177         spin_lock_t lock;       /* spin lock for mutual exclusion */
178         header_t head;          /* head of free list for this size */
179 #ifdef  DEBUG
180         int in_use;             /* # mallocs - # frees */
181 #endif  DEBUG
182 } *free_list_t;
183
184 /*
185  * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
186  * including header.  Smallest block size is MIN_SIZE, with MIN_SIZE -
187  * HEADER_SIZE bytes available to user.  Size argument to malloc is a signed
188  * integer for sanity checking, so largest block size is 2^31.
189  */
190 #define NBUCKETS        29
191
192 static struct free_list malloc_free_list[NBUCKETS];
193
194 /* Initialization just sets everything to zero, but might be necessary on a
195    machine where spin_lock_init does otherwise, and is necessary when
196    running an executable that was written by something like Emacs's unexec.
197    It preserves the values of data variables like malloc_free_list, but
198    does not save the vm_allocate'd space allocated by this malloc.  */
199
200 static void
201 malloc_init (void)
202 {
203   int i;
204   for (i = 0; i < NBUCKETS; ++i)
205     {
206       spin_lock_init (&malloc_free_list[i].lock);
207       malloc_free_list[i].head = NULL;
208 #ifdef DEBUG
209       malloc_free_list[i].in_use = 0;
210 #endif
211     }
212
213   /* This not only suppresses a `defined but not used' warning,
214      but it is ABSOLUTELY NECESSARY to avoid the hyperclever
215      compiler from "optimizing out" the entire function!  */
216   (void) &malloc_init;
217 }
218
219 static void
220 more_memory(int size, free_list_t fl)
221 {
222         register int amount;
223         register int n;
224         vm_address_t where;
225         register header_t h;
226         kern_return_t r;
227
228         if (size <= vm_page_size) {
229                 amount = vm_page_size;
230                 n = vm_page_size / size;
231                 /* We lose vm_page_size - n*size bytes here.  */
232         } else {
233                 amount = size;
234                 n = 1;
235         }
236
237         r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
238         assert_perror (r);
239
240         h = (header_t) where;
241         do {
242                 HEADER_NEXT (h) = fl->head;
243 #ifdef MCHECK
244                 HEADER_CHECK (h) = CHECK_FREE;
245 #endif
246                 fl->head = h;
247                 h = (header_t) ((char *) h + size);
248         } while (--n != 0);
249 }
250
251 /* Declaration changed to standard one for GNU.  */
252 void *
253 malloc(size)
254         register size_t size;
255 {
256         register int i, n;
257         register free_list_t fl;
258         register header_t h;
259
260         if ((int) size < 0)             /* sanity check */
261                 return 0;
262         size += HEADER_SIZE;
263         /*
264          * Find smallest power-of-two block size
265          * big enough to hold requested size plus header.
266          */
267         i = 0;
268         n = MIN_SIZE;
269         while (n < size) {
270                 i += 1;
271                 n <<= 1;
272         }
273         ASSERT(i < NBUCKETS);
274         fl = &malloc_free_list[i];
275         spin_lock(&fl->lock);
276         h = fl->head;
277         if (h == 0) {
278                 /*
279                  * Free list is empty;
280                  * allocate more blocks.
281                  */
282                 more_memory(n, fl);
283                 h = fl->head;
284                 if (h == 0) {
285                         /*
286                          * Allocation failed.
287                          */
288                         spin_unlock(&fl->lock);
289                         return 0;
290                 }
291         }
292         /*
293          * Pop block from free list.
294          */
295         fl->head = HEADER_NEXT (h);
296
297 #ifdef MCHECK
298         assert (HEADER_CHECK (h) == CHECK_FREE);
299         HEADER_CHECK (h) = CHECK_BUSY;
300 #endif
301
302 #ifdef  DEBUG
303         fl->in_use += 1;
304 #endif  DEBUG
305         spin_unlock(&fl->lock);
306         /*
307          * Store free list pointer in block header
308          * so we can figure out where it goes
309          * at free() time.
310          */
311         HEADER_FREE (h) = fl;
312         /*
313          * Return pointer past the block header.
314          */
315         return ((char *) h) + HEADER_SIZE;
316 }
317
318 /* Declaration changed to standard one for GNU.  */
319 void
320 free(base)
321         void *base;
322 {
323         register header_t h;
324         register free_list_t fl;
325         register int i;
326
327         if (base == 0)
328                 return;
329         /*
330          * Find free list for block.
331          */
332         h = (header_t) (base - HEADER_SIZE);
333
334 #ifdef MCHECK
335         assert (HEADER_CHECK (h) == CHECK_BUSY);
336 #endif
337
338         fl = HEADER_FREE (h);
339         i = fl - malloc_free_list;
340         /*
341          * Sanity checks.
342          */
343         if (i < 0 || i >= NBUCKETS) {
344                 ASSERT(0 <= i && i < NBUCKETS);
345                 return;
346         }
347         if (fl != &malloc_free_list[i]) {
348                 ASSERT(fl == &malloc_free_list[i]);
349                 return;
350         }
351         /*
352          * Push block on free list.
353          */
354         spin_lock(&fl->lock);
355         HEADER_NEXT (h) = fl->head;
356 #ifdef MCHECK
357         HEADER_CHECK (h) = CHECK_FREE;
358 #endif
359         fl->head = h;
360 #ifdef  DEBUG
361         fl->in_use -= 1;
362 #endif  DEBUG
363         spin_unlock(&fl->lock);
364         return;
365 }
366
367 /* Declaration changed to standard one for GNU.  */
368 void *
369 realloc(old_base, new_size)
370         void *old_base;
371         size_t new_size;
372 {
373         register header_t h;
374         register free_list_t fl;
375         register int i;
376         unsigned int old_size;
377         char *new_base;
378
379         if (old_base == 0)
380           return malloc (new_size);
381
382         /*
383          * Find size of old block.
384          */
385         h = (header_t) (old_base - HEADER_SIZE);
386 #ifdef MCHECK
387         assert (HEADER_CHECK (h) == CHECK_BUSY);
388 #endif
389         fl = HEADER_FREE (h);
390         i = fl - malloc_free_list;
391         /*
392          * Sanity checks.
393          */
394         if (i < 0 || i >= NBUCKETS) {
395                 ASSERT(0 <= i && i < NBUCKETS);
396                 return 0;
397         }
398         if (fl != &malloc_free_list[i]) {
399                 ASSERT(fl == &malloc_free_list[i]);
400                 return 0;
401         }
402         /*
403          * Free list with index i contains blocks of size
404          * 2 ^ (i + * LOG2_MIN_SIZE) including header.
405          */
406         old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
407
408         if (new_size <= old_size
409             && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
410           /* The new size still fits in the same block, and wouldn't fit in
411              the next smaller block!  */
412           return old_base;
413
414         /*
415          * Allocate new block, copy old bytes, and free old block.
416          */
417         new_base = malloc(new_size);
418         if (new_base)
419           bcopy(old_base, new_base,
420                 (int) (old_size < new_size ? old_size : new_size));
421
422         if (new_base || new_size == 0)
423           /* Free OLD_BASE, but only if the malloc didn't fail.  */
424           free (old_base);
425
426         return new_base;
427 }
428
429 #ifdef  DEBUG
430 void
431 print_malloc_free_list()
432 {
433         register int i, size;
434         register free_list_t fl;
435         register int n;
436         register header_t h;
437         int total_used = 0;
438         int total_free = 0;
439
440         fprintf(stderr, "      Size     In Use       Free      Total\n");
441         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
442              i < NBUCKETS;
443              i += 1, size <<= 1, fl += 1) {
444                 spin_lock(&fl->lock);
445                 if (fl->in_use != 0 || fl->head != 0) {
446                         total_used += fl->in_use * size;
447                         for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
448                                 ;
449                         total_free += n * size;
450                         fprintf(stderr, "%10d %10d %10d %10d\n",
451                                 size, fl->in_use, n, fl->in_use + n);
452                 }
453                 spin_unlock(&fl->lock);
454         }
455         fprintf(stderr, " all sizes %10d %10d %10d\n",
456                 total_used, total_free, total_used + total_free);
457 }
458 #endif  DEBUG
459
460 static void
461 malloc_fork_prepare(void)
462 /*
463  * Prepare the malloc module for a fork by insuring that no thread is in a
464  * malloc critical section.
465  */
466 {
467     register int i;
468
469     for (i = 0; i < NBUCKETS; i++) {
470         spin_lock(&malloc_free_list[i].lock);
471     }
472 }
473
474 static void
475 malloc_fork_parent(void)
476 /*
477  * Called in the parent process after a fork() to resume normal operation.
478  */
479 {
480     register int i;
481
482     for (i = NBUCKETS-1; i >= 0; i--) {
483         spin_unlock(&malloc_free_list[i].lock);
484     }
485 }
486
487 static void
488 malloc_fork_child(void)
489 /*
490  * Called in the child process after a fork() to resume normal operation.
491  */
492 {
493     register int i;
494
495     for (i = NBUCKETS-1; i >= 0; i--) {
496         spin_unlock(&malloc_free_list[i].lock);
497     }
498 }
499 \f
500
501 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
502 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
503 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
504 text_set_element (_hurd_preinit_hook, malloc_init);