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