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         register int amount;
 175         register int n;
 176         vm_address_t where;
 177         register 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)
 206         register size_t size;
 207 {
 208         register int i, n;
 209         register free_list_t fl;
 210         register header_t h;
 211
 212         if ((int) size < 0)             /* sanity check */
 213                 return 0;
 214         size += HEADER_SIZE;
 215         /*
 216          * Find smallest power-of-two block size
 217          * big enough to hold requested size plus header.
 218          */
 219         i = 0;
 220         n = MIN_SIZE;
 221         while (n < size) {
 222                 i += 1;
 223                 n <<= 1;
 224         }
 225         ASSERT(i < NBUCKETS);
 226         fl = &malloc_free_list[i];
 227         spin_lock(&fl->lock);
 228         h = fl->head;
 229         if (h == 0) {
 230                 /*
 231                  * Free list is empty;
 232                  * allocate more blocks.
 233                  */
 234                 more_memory(n, fl);
 235                 h = fl->head;
 236                 if (h == 0) {
 237                         /*
 238                          * Allocation failed.
 239                          */
 240                         spin_unlock(&fl->lock);
 241                         return 0;
 242                 }
 243         }
 244         /*
 245          * Pop block from free list.
 246          */
 247         fl->head = HEADER_NEXT (h);
 248
 249 #ifdef MCHECK
 250         assert (HEADER_CHECK (h) == CHECK_FREE);
 251         HEADER_CHECK (h) = CHECK_BUSY;
 252 #endif
 253
 254 #ifdef  DEBUG
 255         fl->in_use += 1;
 256 #endif  /* DEBUG */
 257         spin_unlock(&fl->lock);
 258         /*
 259          * Store free list pointer in block header
 260          * so we can figure out where it goes
 261          * at free() time.
 262          */
 263         HEADER_FREE (h) = fl;
 264         /*
 265          * Return pointer past the block header.
 266          */
 267         return ((char *) h) + HEADER_SIZE;
 268 }
 269
 270 /* Declaration changed to standard one for GNU.  */
 271 void
 272 free(base)
 273         void *base;
 274 {
 275         register header_t h;
 276         register free_list_t fl;
 277         register int i;
 278
 279         if (base == 0)
 280                 return;
 281         /*
 282          * Find free list for block.
 283          */
 284         h = (header_t) (base - HEADER_SIZE);
 285
 286 #ifdef MCHECK
 287         assert (HEADER_CHECK (h) == CHECK_BUSY);
 288 #endif
 289
 290         fl = HEADER_FREE (h);
 291         i = fl - malloc_free_list;
 292         /*
 293          * Sanity checks.
 294          */
 295         if (i < 0 || i >= NBUCKETS) {
 296                 ASSERT(0 <= i && i < NBUCKETS);
 297                 return;
 298         }
 299         if (fl != &malloc_free_list[i]) {
 300                 ASSERT(fl == &malloc_free_list[i]);
 301                 return;
 302         }
 303         /*
 304          * Push block on free list.
 305          */
 306         spin_lock(&fl->lock);
 307         HEADER_NEXT (h) = fl->head;
 308 #ifdef MCHECK
 309         HEADER_CHECK (h) = CHECK_FREE;
 310 #endif
 311         fl->head = h;
 312 #ifdef  DEBUG
 313         fl->in_use -= 1;
 314 #endif  /* DEBUG */
 315         spin_unlock(&fl->lock);
 316         return;
 317 }
 318
 319 /* Declaration changed to standard one for GNU.  */
 320 void *
 321 realloc(old_base, new_size)
 322         void *old_base;
 323         size_t new_size;
 324 {
 325         register header_t h;
 326         register free_list_t fl;
 327         register int i;
 328         unsigned int old_size;
 329         char *new_base;
 330
 331         if (old_base == 0)
 332           return malloc (new_size);
 333
 334         /*
 335          * Find size of old block.
 336          */
 337         h = (header_t) (old_base - HEADER_SIZE);
 338 #ifdef MCHECK
 339         assert (HEADER_CHECK (h) == CHECK_BUSY);
 340 #endif
 341         fl = HEADER_FREE (h);
 342         i = fl - malloc_free_list;
 343         /*
 344          * Sanity checks.
 345          */
 346         if (i < 0 || i >= NBUCKETS) {
 347                 ASSERT(0 <= i && i < NBUCKETS);
 348                 return 0;
 349         }
 350         if (fl != &malloc_free_list[i]) {
 351                 ASSERT(fl == &malloc_free_list[i]);
 352                 return 0;
 353         }
 354         /*
 355          * Free list with index i contains blocks of size
 356          * 2 ^ (i + * LOG2_MIN_SIZE) including header.
 357          */
 358         old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
 359
 360         if (new_size <= old_size
 361             && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
 362           /* The new size still fits in the same block, and wouldn't fit in
 363              the next smaller block!  */
 364           return old_base;
 365
 366         /*
 367          * Allocate new block, copy old bytes, and free old block.
 368          */
 369         new_base = malloc(new_size);
 370         if (new_base)
 371           memcpy (new_base, old_base,
 372                   (int) (old_size < new_size ? old_size : new_size));
 373
 374         if (new_base || new_size == 0)
 375           /* Free OLD_BASE, but only if the malloc didn't fail.  */
 376           free (old_base);
 377
 378         return new_base;
 379 }
 380
 381 #ifdef  DEBUG
 382 void
 383 print_malloc_free_list()
 384 {
 385         register int i, size;
 386         register free_list_t fl;
 387         register int n;
 388         register header_t h;
 389         int total_used = 0;
 390         int total_free = 0;
 391
 392         fprintf(stderr, "      Size     In Use       Free      Total\n");
 393         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
 394              i < NBUCKETS;
 395              i += 1, size <<= 1, fl += 1) {
 396                 spin_lock(&fl->lock);
 397                 if (fl->in_use != 0 || fl->head != 0) {
 398                         total_used += fl->in_use * size;
 399                         for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
 400                                 ;
 401                         total_free += n * size;
 402                         fprintf(stderr, "%10d %10d %10d %10d\n",
 403                                 size, fl->in_use, n, fl->in_use + n);
 404                 }
 405                 spin_unlock(&fl->lock);
 406         }
 407         fprintf(stderr, " all sizes %10d %10d %10d\n",
 408                 total_used, total_free, total_used + total_free);
 409 }
 410 #endif  /* DEBUG */
 411
 412 static void
 413 malloc_fork_prepare(void)
 414 /*
 415  * Prepare the malloc module for a fork by insuring that no thread is in a
 416  * malloc critical section.
 417  */
 418 {
 419     register int i;
 420
 421     for (i = 0; i < NBUCKETS; i++) {
 422         spin_lock(&malloc_free_list[i].lock);
 423     }
 424 }
 425
 426 static void
 427 malloc_fork_parent(void)
 428 /*
 429  * Called in the parent process after a fork() to resume normal operation.
 430  */
 431 {
 432     register int i;
 433
 434     for (i = NBUCKETS-1; i >= 0; i--) {
 435         spin_unlock(&malloc_free_list[i].lock);
 436     }
 437 }
 438
 439 static void
 440 malloc_fork_child(void)
 441 /*
 442  * Called in the child process after a fork() to resume normal operation.
 443  */
 444 {
 445     register int i;
 446
 447     for (i = NBUCKETS-1; i >= 0; i--) {
 448         spin_unlock(&malloc_free_list[i].lock);
 449     }
 450 }
 451 \f
 452
 453 text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
 454 text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
 455 text_set_element (_hurd_fork_child_hook, malloc_fork_child);
 456 text_set_element (_hurd_preinit_hook, malloc_init);