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