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