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: ^L
   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: ^L
  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);