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