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