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