hurd/hurdmalloc.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "set-hooks.h"
   4
   5 #include "hurdmalloc.h"         /* XXX see that file */
   6
   7 #include <mach.h>
   8 #include <mach/spin-lock.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  * (pre-GNU) HISTORY
  39  *
  40  * Revision 2.7  91/05/14  17:57:34  mrt
  41  *      Correcting copyright
  42  *
  43  * Revision 2.6  91/02/14  14:20:26  mrt
  44  *      Added new Mach copyright
  45  *      [91/02/13  12:41:21  mrt]
  46  *
  47  * Revision 2.5  90/11/05  14:37:33  rpd
  48  *      Added malloc_fork* code.
  49  *      [90/11/02            rwd]
  50  *
  51  *      Add spin_lock_t.
  52  *      [90/10/31            rwd]
  53  *
  54  * Revision 2.4  90/08/07  14:31:28  rpd
  55  *      Removed RCS keyword nonsense.
  56  *
  57  * Revision 2.3  90/06/02  15:14:00  rpd
  58  *      Converted to new IPC.
  59  *      [90/03/20  20:56:57  rpd]
  60  *
  61  * Revision 2.2  89/12/08  19:53:59  rwd
  62  *      Removed conditionals.
  63  *      [89/10/23            rwd]
  64  *
  65  * Revision 2.1  89/08/03  17:09:46  rwd
  66  * Created.
  67  *
  68  *
  69  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
  70  *      Changed realloc() to copy min(old size, new size) bytes.
  71  *      Bug found by Mike Kupfer at Olivetti.
  72  */
  73 /*
  74  *      File:   malloc.c
  75  *      Author: Eric Cooper, Carnegie Mellon University
  76  *      Date:   July, 1988
  77  *
  78  *      Memory allocator for use with multiple threads.
  79  */
  80
  81 \f
  82 #include <assert.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 attribute_used_retain
 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
 166 static void
 167 more_memory(int size, free_list_t fl)
 168 {
 169         int amount;
 170         int n;
 171         vm_address_t where;
 172         header_t h;
 173         kern_return_t r;
 174
 175         if (size <= vm_page_size) {
 176                 amount = vm_page_size;
 177                 n = vm_page_size / size;
 178                 /* We lose vm_page_size - n*size bytes here.  */
 179         } else {
 180                 amount = size;
 181                 n = 1;
 182         }
 183
 184         r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
 185         assert_perror (r);
 186
 187         h = (header_t) where;
 188         do {
 189                 HEADER_NEXT (h) = fl->head;
 190 #ifdef MCHECK
 191                 HEADER_CHECK (h) = CHECK_FREE;
 192 #endif
 193                 fl->head = h;
 194                 h = (header_t) ((char *) h + size);
 195         } while (--n != 0);
 196 }
 197
 198 /* Declaration changed to standard one for GNU.  */
 199 void *
 200 malloc (size_t size)
 201 {
 202         int i, n;
 203         free_list_t fl;
 204         header_t h;
 205
 206         if ((int) size < 0)             /* sanity check */
 207                 return 0;
 208         size += HEADER_SIZE;
 209         /*
 210          * Find smallest power-of-two block size
 211          * big enough to hold requested size plus header.
 212          */
 213         i = 0;
 214         n = MIN_SIZE;
 215         while (n < size) {
 216                 i += 1;
 217                 n <<= 1;
 218         }
 219         assert(i < NBUCKETS);
 220         fl = &malloc_free_list[i];
 221         spin_lock(&fl->lock);
 222         h = fl->head;
 223         if (h == 0) {
 224                 /*
 225                  * Free list is empty;
 226                  * allocate more blocks.
 227                  */
 228                 more_memory(n, fl);
 229                 h = fl->head;
 230                 if (h == 0) {
 231                         /*
 232                          * Allocation failed.
 233                          */
 234                         spin_unlock(&fl->lock);
 235                         return 0;
 236                 }
 237         }
 238         /*
 239          * Pop block from free list.
 240          */
 241         fl->head = HEADER_NEXT (h);
 242
 243 #ifdef MCHECK
 244         assert (HEADER_CHECK (h) == CHECK_FREE);
 245         HEADER_CHECK (h) = CHECK_BUSY;
 246 #endif
 247
 248 #ifdef  DEBUG
 249         fl->in_use += 1;
 250 #endif  /* DEBUG */
 251         spin_unlock(&fl->lock);
 252         /*
 253          * Store free list pointer in block header
 254          * so we can figure out where it goes
 255          * at free() time.
 256          */
 257         HEADER_FREE (h) = fl;
 258         /*
 259          * Return pointer past the block header.
 260          */
 261         return ((char *) h) + HEADER_SIZE;
 262 }
 263
 264 /* Declaration changed to standard one for GNU.  */
 265 void
 266 free (void *base)
 267 {
 268         header_t h;
 269         free_list_t fl;
 270         int i;
 271
 272         if (base == 0)
 273                 return;
 274         /*
 275          * Find free list for block.
 276          */
 277         h = (header_t) (base - HEADER_SIZE);
 278
 279 #ifdef MCHECK
 280         assert (HEADER_CHECK (h) == CHECK_BUSY);
 281 #endif
 282
 283         fl = HEADER_FREE (h);
 284         i = fl - malloc_free_list;
 285         /*
 286          * Sanity checks.
 287          */
 288         if (i < 0 || i >= NBUCKETS) {
 289                 assert(0 <= i && i < NBUCKETS);
 290                 return;
 291         }
 292         if (fl != &malloc_free_list[i]) {
 293                 assert(fl == &malloc_free_list[i]);
 294                 return;
 295         }
 296         /*
 297          * Push block on free list.
 298          */
 299         spin_lock(&fl->lock);
 300         HEADER_NEXT (h) = fl->head;
 301 #ifdef MCHECK
 302         HEADER_CHECK (h) = CHECK_FREE;
 303 #endif
 304         fl->head = h;
 305 #ifdef  DEBUG
 306         fl->in_use -= 1;
 307 #endif  /* DEBUG */
 308         spin_unlock(&fl->lock);
 309         return;
 310 }
 311
 312 /* Declaration changed to standard one for GNU.  */
 313 void *
 314 realloc (void *old_base, size_t new_size)
 315 {
 316         header_t h;
 317         free_list_t fl;
 318         int i;
 319         unsigned int old_size;
 320         char *new_base;
 321
 322         if (old_base == 0)
 323           return malloc (new_size);
 324
 325         /*
 326          * Find size of old block.
 327          */
 328         h = (header_t) (old_base - HEADER_SIZE);
 329 #ifdef MCHECK
 330         assert (HEADER_CHECK (h) == CHECK_BUSY);
 331 #endif
 332         fl = HEADER_FREE (h);
 333         i = fl - malloc_free_list;
 334         /*
 335          * Sanity checks.
 336          */
 337         if (i < 0 || i >= NBUCKETS) {
 338                 assert(0 <= i && i < NBUCKETS);
 339                 return 0;
 340         }
 341         if (fl != &malloc_free_list[i]) {
 342                 assert(fl == &malloc_free_list[i]);
 343                 return 0;
 344         }
 345         /*
 346          * Free list with index i contains blocks of size
 347          * 2 ^ (i + * LOG2_MIN_SIZE) including header.
 348          */
 349         old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
 350
 351         if (new_size <= old_size
 352             && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
 353           /* The new size still fits in the same block, and wouldn't fit in
 354              the next smaller block!  */
 355           return old_base;
 356
 357         /*
 358          * Allocate new block, copy old bytes, and free old block.
 359          */
 360         new_base = malloc(new_size);
 361         if (new_base)
 362           memcpy (new_base, old_base,
 363                   (int) (old_size < new_size ? old_size : new_size));
 364
 365         if (new_base || new_size == 0)
 366           /* Free OLD_BASE, but only if the malloc didn't fail.  */
 367           free (old_base);
 368
 369         return new_base;
 370 }
 371
 372 #ifdef  DEBUG
 373 void
 374 print_malloc_free_list (void)
 375 {
 376         int i, size;
 377         free_list_t fl;
 378         int n;
 379         header_t h;
 380         int total_used = 0;
 381         int total_free = 0;
 382
 383         fprintf(stderr, "      Size     In Use       Free      Total\n");
 384         for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
 385              i < NBUCKETS;
 386              i += 1, size <<= 1, fl += 1) {
 387                 spin_lock(&fl->lock);
 388                 if (fl->in_use != 0 || fl->head != 0) {
 389                         total_used += fl->in_use * size;
 390                         for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
 391                                 ;
 392                         total_free += n * size;
 393                         fprintf(stderr, "%10d %10d %10d %10d\n",
 394                                 size, fl->in_use, n, fl->in_use + n);
 395                 }
 396                 spin_unlock(&fl->lock);
 397         }
 398         fprintf(stderr, " all sizes %10d %10d %10d\n",
 399                 total_used, total_free, total_used + total_free);
 400 }
 401 #endif  /* DEBUG */
 402
 403 void
 404 _hurd_malloc_fork_prepare(void)
 405 /*
 406  * Prepare the malloc module for a fork by insuring that no thread is in a
 407  * malloc critical section.
 408  */
 409 {
 410     int i;
 411
 412     for (i = 0; i < NBUCKETS; i++) {
 413         spin_lock(&malloc_free_list[i].lock);
 414     }
 415 }
 416
 417 void
 418 _hurd_malloc_fork_parent(void)
 419 /*
 420  * Called in the parent process after a fork() to resume normal operation.
 421  */
 422 {
 423     int i;
 424
 425     for (i = NBUCKETS-1; i >= 0; i--) {
 426         spin_unlock(&malloc_free_list[i].lock);
 427     }
 428 }
 429
 430 void
 431 _hurd_malloc_fork_child(void)
 432 /*
 433  * Called in the child process after a fork() to resume normal operation.
 434  */
 435 {
 436     int i;
 437
 438     for (i = NBUCKETS-1; i >= 0; i--) {
 439         spin_unlock(&malloc_free_list[i].lock);
 440     }
 441 }
 442 \f
 443
 444 SET_RELHOOK (_hurd_preinit_hook, malloc_init);