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