Back to index

glibc  2.9
hurdmalloc.c
Go to the documentation of this file.
00001 #include <stdlib.h>
00002 #include <string.h>
00003 
00004 #include "hurdmalloc.h"            /* XXX see that file */
00005 
00006 #include <mach.h>
00007 #define vm_allocate __vm_allocate
00008 #define vm_page_size __vm_page_size
00009 
00010 /*
00011  * Mach Operating System
00012  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
00013  * All Rights Reserved.
00014  *
00015  * Permission to use, copy, modify and distribute this software and its
00016  * documentation is hereby granted, provided that both the copyright
00017  * notice and this permission notice appear in all copies of the
00018  * software, derivative works or modified versions, and any portions
00019  * thereof, and that both notices appear in supporting documentation.
00020  *
00021  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
00022  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
00023  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
00024  *
00025  * Carnegie Mellon requests users of this software to return to
00026  *
00027  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
00028  *  School of Computer Science
00029  *  Carnegie Mellon University
00030  *  Pittsburgh PA 15213-3890
00031  *
00032  * any improvements or extensions that they make and grant Carnegie Mellon
00033  * the rights to redistribute these changes.
00034  */
00035 /*
00036  * (pre-GNU) HISTORY
00037  *
00038  * Revision 2.7  91/05/14  17:57:34  mrt
00039  *     Correcting copyright
00040  *
00041  * Revision 2.6  91/02/14  14:20:26  mrt
00042  *     Added new Mach copyright
00043  *     [91/02/13  12:41:21  mrt]
00044  *
00045  * Revision 2.5  90/11/05  14:37:33  rpd
00046  *     Added malloc_fork* code.
00047  *     [90/11/02            rwd]
00048  *
00049  *     Add spin_lock_t.
00050  *     [90/10/31            rwd]
00051  *
00052  * Revision 2.4  90/08/07  14:31:28  rpd
00053  *     Removed RCS keyword nonsense.
00054  *
00055  * Revision 2.3  90/06/02  15:14:00  rpd
00056  *     Converted to new IPC.
00057  *     [90/03/20  20:56:57  rpd]
00058  *
00059  * Revision 2.2  89/12/08  19:53:59  rwd
00060  *     Removed conditionals.
00061  *     [89/10/23            rwd]
00062  *
00063  * Revision 2.1  89/08/03  17:09:46  rwd
00064  * Created.
00065  *
00066  *
00067  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
00068  *     Changed realloc() to copy min(old size, new size) bytes.
00069  *     Bug found by Mike Kupfer at Olivetti.
00070  */
00071 /*
00072  *     File:  malloc.c
00073  *     Author: Eric Cooper, Carnegie Mellon University
00074  *     Date:  July, 1988
00075  *
00076  *     Memory allocator for use with multiple threads.
00077  */
00078 
00079 
00080 #include <assert.h>
00081 
00082 #include <cthreads.h>
00083 
00084 #define MCHECK
00085 
00086 /*
00087  * Structure of memory block header.
00088  * When free, next points to next block on free list.
00089  * When allocated, fl points to free list.
00090  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
00091  */
00092 
00093 #define CHECK_BUSY  0x8a3c743e
00094 #define CHECK_FREE  0x66688b92
00095 
00096 #ifdef MCHECK
00097 
00098 typedef struct header {
00099   long check;
00100   union {
00101     struct header *next;
00102     struct free_list *fl;
00103   } u;
00104 } *header_t;
00105 
00106 #define HEADER_SIZE sizeof (struct header)
00107 #define HEADER_NEXT(h) ((h)->u.next)
00108 #define HEADER_FREE(h) ((h)->u.fl)
00109 #define HEADER_CHECK(h) ((h)->check)
00110 #define MIN_SIZE     16
00111 #define LOG2_MIN_SIZE       4
00112 
00113 #else /* ! MCHECK */
00114 
00115 typedef union header {
00116        union header *next;
00117        struct free_list *fl;
00118 } *header_t;
00119 
00120 #define HEADER_SIZE sizeof (union header)
00121 #define HEADER_NEXT(h) ((h)->next)
00122 #define HEADER_FREE(h) ((h)->fl)
00123 #define MIN_SIZE     8      /* minimum block size */
00124 #define LOG2_MIN_SIZE       3
00125 
00126 #endif /* MCHECK */
00127 
00128 typedef struct free_list {
00129        spin_lock_t lock;    /* spin lock for mutual exclusion */
00130        header_t head;              /* head of free list for this size */
00131 #ifdef DEBUG
00132        int in_use;          /* # mallocs - # frees */
00133 #endif /* DEBUG */
00134 } *free_list_t;
00135 
00136 /*
00137  * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
00138  * including header.  Smallest block size is MIN_SIZE, with MIN_SIZE -
00139  * HEADER_SIZE bytes available to user.  Size argument to malloc is a signed
00140  * integer for sanity checking, so largest block size is 2^31.
00141  */
00142 #define NBUCKETS     29
00143 
00144 static struct free_list malloc_free_list[NBUCKETS];
00145 
00146 /* Initialization just sets everything to zero, but might be necessary on a
00147    machine where spin_lock_init does otherwise, and is necessary when
00148    running an executable that was written by something like Emacs's unexec.
00149    It preserves the values of data variables like malloc_free_list, but
00150    does not save the vm_allocate'd space allocated by this malloc.  */
00151 
00152 static void
00153 malloc_init (void)
00154 {
00155   int i;
00156   for (i = 0; i < NBUCKETS; ++i)
00157     {
00158       spin_lock_init (&malloc_free_list[i].lock);
00159       malloc_free_list[i].head = NULL;
00160 #ifdef DEBUG
00161       malloc_free_list[i].in_use = 0;
00162 #endif
00163     }
00164 
00165   /* This not only suppresses a `defined but not used' warning,
00166      but it is ABSOLUTELY NECESSARY to avoid the hyperclever
00167      compiler from "optimizing out" the entire function!  */
00168   (void) &malloc_init;
00169 }
00170 
00171 static void
00172 more_memory(int size, free_list_t fl)
00173 {
00174        register int amount;
00175        register int n;
00176        vm_address_t where;
00177        register header_t h;
00178        kern_return_t r;
00179 
00180        if (size <= vm_page_size) {
00181               amount = vm_page_size;
00182               n = vm_page_size / size;
00183               /* We lose vm_page_size - n*size bytes here.  */
00184        } else {
00185               amount = size;
00186               n = 1;
00187        }
00188 
00189        r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
00190        assert_perror (r);
00191 
00192        h = (header_t) where;
00193        do {
00194               HEADER_NEXT (h) = fl->head;
00195 #ifdef MCHECK
00196               HEADER_CHECK (h) = CHECK_FREE;
00197 #endif
00198               fl->head = h;
00199               h = (header_t) ((char *) h + size);
00200        } while (--n != 0);
00201 }
00202 
00203 /* Declaration changed to standard one for GNU.  */
00204 void *
00205 malloc(size)
00206        register size_t size;
00207 {
00208        register int i, n;
00209        register free_list_t fl;
00210        register header_t h;
00211 
00212        if ((int) size < 0)         /* sanity check */
00213               return 0;
00214        size += HEADER_SIZE;
00215        /*
00216         * Find smallest power-of-two block size
00217         * big enough to hold requested size plus header.
00218         */
00219        i = 0;
00220        n = MIN_SIZE;
00221        while (n < size) {
00222               i += 1;
00223               n <<= 1;
00224        }
00225        ASSERT(i < NBUCKETS);
00226        fl = &malloc_free_list[i];
00227        spin_lock(&fl->lock);
00228        h = fl->head;
00229        if (h == 0) {
00230               /*
00231                * Free list is empty;
00232                * allocate more blocks.
00233                */
00234               more_memory(n, fl);
00235               h = fl->head;
00236               if (h == 0) {
00237                      /*
00238                       * Allocation failed.
00239                       */
00240                      spin_unlock(&fl->lock);
00241                      return 0;
00242               }
00243        }
00244        /*
00245         * Pop block from free list.
00246         */
00247        fl->head = HEADER_NEXT (h);
00248 
00249 #ifdef MCHECK
00250        assert (HEADER_CHECK (h) == CHECK_FREE);
00251        HEADER_CHECK (h) = CHECK_BUSY;
00252 #endif
00253 
00254 #ifdef DEBUG
00255        fl->in_use += 1;
00256 #endif /* DEBUG */
00257        spin_unlock(&fl->lock);
00258        /*
00259         * Store free list pointer in block header
00260         * so we can figure out where it goes
00261         * at free() time.
00262         */
00263        HEADER_FREE (h) = fl;
00264        /*
00265         * Return pointer past the block header.
00266         */
00267        return ((char *) h) + HEADER_SIZE;
00268 }
00269 
00270 /* Declaration changed to standard one for GNU.  */
00271 void
00272 free(base)
00273        void *base;
00274 {
00275        register header_t h;
00276        register free_list_t fl;
00277        register int i;
00278 
00279        if (base == 0)
00280               return;
00281        /*
00282         * Find free list for block.
00283         */
00284        h = (header_t) (base - HEADER_SIZE);
00285 
00286 #ifdef MCHECK
00287        assert (HEADER_CHECK (h) == CHECK_BUSY);
00288 #endif
00289 
00290        fl = HEADER_FREE (h);
00291        i = fl - malloc_free_list;
00292        /*
00293         * Sanity checks.
00294         */
00295        if (i < 0 || i >= NBUCKETS) {
00296               ASSERT(0 <= i && i < NBUCKETS);
00297               return;
00298        }
00299        if (fl != &malloc_free_list[i]) {
00300               ASSERT(fl == &malloc_free_list[i]);
00301               return;
00302        }
00303        /*
00304         * Push block on free list.
00305         */
00306        spin_lock(&fl->lock);
00307        HEADER_NEXT (h) = fl->head;
00308 #ifdef MCHECK
00309        HEADER_CHECK (h) = CHECK_FREE;
00310 #endif
00311        fl->head = h;
00312 #ifdef DEBUG
00313        fl->in_use -= 1;
00314 #endif /* DEBUG */
00315        spin_unlock(&fl->lock);
00316        return;
00317 }
00318 
00319 /* Declaration changed to standard one for GNU.  */
00320 void *
00321 realloc(old_base, new_size)
00322         void *old_base;
00323         size_t new_size;
00324 {
00325        register header_t h;
00326        register free_list_t fl;
00327        register int i;
00328        unsigned int old_size;
00329        char *new_base;
00330 
00331        if (old_base == 0)
00332          return malloc (new_size);
00333 
00334        /*
00335         * Find size of old block.
00336         */
00337        h = (header_t) (old_base - HEADER_SIZE);
00338 #ifdef MCHECK
00339        assert (HEADER_CHECK (h) == CHECK_BUSY);
00340 #endif
00341        fl = HEADER_FREE (h);
00342        i = fl - malloc_free_list;
00343        /*
00344         * Sanity checks.
00345         */
00346        if (i < 0 || i >= NBUCKETS) {
00347               ASSERT(0 <= i && i < NBUCKETS);
00348               return 0;
00349        }
00350        if (fl != &malloc_free_list[i]) {
00351               ASSERT(fl == &malloc_free_list[i]);
00352               return 0;
00353        }
00354        /*
00355         * Free list with index i contains blocks of size
00356         * 2 ^ (i + * LOG2_MIN_SIZE) including header.
00357         */
00358        old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
00359 
00360        if (new_size <= old_size
00361            && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
00362          /* The new size still fits in the same block, and wouldn't fit in
00363             the next smaller block!  */
00364          return old_base;
00365 
00366        /*
00367         * Allocate new block, copy old bytes, and free old block.
00368         */
00369        new_base = malloc(new_size);
00370        if (new_base)
00371          memcpy (new_base, old_base,
00372                 (int) (old_size < new_size ? old_size : new_size));
00373 
00374        if (new_base || new_size == 0)
00375          /* Free OLD_BASE, but only if the malloc didn't fail.  */
00376          free (old_base);
00377 
00378        return new_base;
00379 }
00380 
00381 #ifdef DEBUG
00382 void
00383 print_malloc_free_list()
00384 {
00385        register int i, size;
00386        register free_list_t fl;
00387        register int n;
00388        register header_t h;
00389        int total_used = 0;
00390        int total_free = 0;
00391 
00392        fprintf(stderr, "      Size     In Use       Free      Total\n");
00393        for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
00394             i < NBUCKETS;
00395             i += 1, size <<= 1, fl += 1) {
00396               spin_lock(&fl->lock);
00397               if (fl->in_use != 0 || fl->head != 0) {
00398                      total_used += fl->in_use * size;
00399                      for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
00400                             ;
00401                      total_free += n * size;
00402                      fprintf(stderr, "%10d %10d %10d %10d\n",
00403                             size, fl->in_use, n, fl->in_use + n);
00404               }
00405               spin_unlock(&fl->lock);
00406        }
00407        fprintf(stderr, " all sizes %10d %10d %10d\n",
00408               total_used, total_free, total_used + total_free);
00409 }
00410 #endif /* DEBUG */
00411 
00412 static void
00413 malloc_fork_prepare(void)
00414 /*
00415  * Prepare the malloc module for a fork by insuring that no thread is in a
00416  * malloc critical section.
00417  */
00418 {
00419     register int i;
00420 
00421     for (i = 0; i < NBUCKETS; i++) {
00422        spin_lock(&malloc_free_list[i].lock);
00423     }
00424 }
00425 
00426 static void
00427 malloc_fork_parent(void)
00428 /*
00429  * Called in the parent process after a fork() to resume normal operation.
00430  */
00431 {
00432     register int i;
00433 
00434     for (i = NBUCKETS-1; i >= 0; i--) {
00435        spin_unlock(&malloc_free_list[i].lock);
00436     }
00437 }
00438 
00439 static void
00440 malloc_fork_child(void)
00441 /*
00442  * Called in the child process after a fork() to resume normal operation.
00443  */
00444 {
00445     register int i;
00446 
00447     for (i = NBUCKETS-1; i >= 0; i--) {
00448        spin_unlock(&malloc_free_list[i].lock);
00449     }
00450 }
00451 
00452 
00453 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
00454 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
00455 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
00456 text_set_element (_hurd_preinit_hook, malloc_init);