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