home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / amiga / os / kludge03.tz / kludge03 / mk74 / user / threads / malloc.c < prev    next >
C/C++ Source or Header  |  1991-05-15  |  8KB  |  350 lines
  1. /* 
  2.  * Mach Operating System
  3.  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
  4.  * All Rights Reserved.
  5.  * 
  6.  * Permission to use, copy, modify and distribute this software and its
  7.  * documentation is hereby granted, provided that both the copyright
  8.  * notice and this permission notice appear in all copies of the
  9.  * software, derivative works or modified versions, and any portions
  10.  * thereof, and that both notices appear in supporting documentation.
  11.  * 
  12.  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  13.  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  14.  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  15.  * 
  16.  * Carnegie Mellon requests users of this software to return to
  17.  * 
  18.  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  19.  *  School of Computer Science
  20.  *  Carnegie Mellon University
  21.  *  Pittsburgh PA 15213-3890
  22.  * 
  23.  * any improvements or extensions that they make and grant Carnegie Mellon
  24.  * the rights to redistribute these changes.
  25.  */
  26. /*
  27.  * HISTORY
  28.  * $Log:    malloc.c,v $
  29.  * Revision 2.7  91/05/14  17:57:34  mrt
  30.  *     Correcting copyright
  31.  * 
  32.  * Revision 2.6  91/02/14  14:20:26  mrt
  33.  *     Added new Mach copyright
  34.  *     [91/02/13  12:41:21  mrt]
  35.  * 
  36.  * Revision 2.5  90/11/05  14:37:33  rpd
  37.  *     Added malloc_fork* code.
  38.  *     [90/11/02            rwd]
  39.  * 
  40.  *     Add spin_lock_t.
  41.  *     [90/10/31            rwd]
  42.  * 
  43.  * Revision 2.4  90/08/07  14:31:28  rpd
  44.  *     Removed RCS keyword nonsense.
  45.  * 
  46.  * Revision 2.3  90/06/02  15:14:00  rpd
  47.  *     Converted to new IPC.
  48.  *     [90/03/20  20:56:57  rpd]
  49.  * 
  50.  * Revision 2.2  89/12/08  19:53:59  rwd
  51.  *     Removed conditionals.
  52.  *     [89/10/23            rwd]
  53.  * 
  54.  * Revision 2.1  89/08/03  17:09:46  rwd
  55.  * Created.
  56.  * 
  57.  *
  58.  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
  59.  *    Changed realloc() to copy min(old size, new size) bytes.
  60.  *    Bug found by Mike Kupfer at Olivetti.
  61.  */
  62. /*
  63.  *     File:     malloc.c
  64.  *    Author: Eric Cooper, Carnegie Mellon University
  65.  *    Date:    July, 1988
  66.  *
  67.  *     Memory allocator for use with multiple threads.
  68.  */
  69.  
  70.  
  71. #include <cthreads.h>
  72. #include "cthread_internals.h"
  73.  
  74. /*
  75.  * C library imports:
  76.  */
  77. extern bcopy();
  78.  
  79. /*
  80.  * Structure of memory block header.
  81.  * When free, next points to next block on free list.
  82.  * When allocated, fl points to free list.
  83.  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
  84.  */
  85. typedef union header {
  86.     union header *next;
  87.     struct free_list *fl;
  88. } *header_t;
  89.  
  90. #define MIN_SIZE    8    /* minimum block size */
  91.  
  92. typedef struct free_list {
  93.     spin_lock_t lock;    /* spin lock for mutual exclusion */
  94.     header_t head;        /* head of free list for this size */
  95. #ifdef    DEBUG
  96.     int in_use;        /* # mallocs - # frees */
  97. #endif    DEBUG
  98. } *free_list_t;
  99.  
  100. /*
  101.  * Free list with index i contains blocks of size 2^(i+3) including header.
  102.  * Smallest block size is 8, with 4 bytes available to user.
  103.  * Size argument to malloc is a signed integer for sanity checking,
  104.  * so largest block size is 2^31.
  105.  */
  106. #define NBUCKETS    29
  107.  
  108. static struct free_list malloc_free_list[NBUCKETS];
  109.  
  110. static void
  111. more_memory(size, fl)
  112.     int size;
  113.     register free_list_t fl;
  114. {
  115.     register int amount;
  116.     register int n;
  117.     vm_address_t where;
  118.     register header_t h;
  119.     kern_return_t r;
  120.  
  121.     if (size <= vm_page_size) {
  122.         amount = vm_page_size;
  123.         n = vm_page_size / size;
  124.         /*
  125.          * We lose vm_page_size - n*size bytes here.
  126.          */
  127.     } else {
  128.         amount = size;
  129.         n = 1;
  130.     }
  131.     MACH_CALL(vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE), r);
  132.     h = (header_t) where;
  133.     do {
  134.         h->next = fl->head;
  135.         fl->head = h;
  136.         h = (header_t) ((char *) h + size);
  137.     } while (--n != 0);
  138. }
  139.  
  140. char *
  141. malloc(size)
  142.     register unsigned int size;
  143. {
  144.     register int i, n;
  145.     register free_list_t fl;
  146.     register header_t h;
  147.  
  148.     if ((int) size <= 0)        /* sanity check */
  149.         return 0;
  150.     size += sizeof(union header);
  151.     /*
  152.      * Find smallest power-of-two block size
  153.      * big enough to hold requested size plus header.
  154.      */
  155.     i = 0;
  156.     n = MIN_SIZE;
  157.     while (n < size) {
  158.         i += 1;
  159.         n <<= 1;
  160.     }
  161.     ASSERT(i < NBUCKETS);
  162.     fl = &malloc_free_list[i];
  163.     spin_lock(&fl->lock);
  164.     h = fl->head;
  165.     if (h == 0) {
  166.         /*
  167.          * Free list is empty;
  168.          * allocate more blocks.
  169.          */
  170.         more_memory(n, fl);
  171.         h = fl->head;
  172.         if (h == 0) {
  173.             /*
  174.              * Allocation failed.
  175.              */
  176.             spin_unlock(&fl->lock);
  177.             return 0;
  178.         }
  179.     }
  180.     /*
  181.      * Pop block from free list.
  182.      */
  183.     fl->head = h->next;
  184. #ifdef    DEBUG
  185.     fl->in_use += 1;
  186. #endif    DEBUG
  187.     spin_unlock(&fl->lock);
  188.     /*
  189.      * Store free list pointer in block header
  190.      * so we can figure out where it goes
  191.      * at free() time.
  192.      */
  193.     h->fl = fl;
  194.     /*
  195.      * Return pointer past the block header.
  196.      */
  197.     return ((char *) h) + sizeof(union header);
  198. }
  199.  
  200. free(base)
  201.     char *base;
  202. {
  203.     register header_t h;
  204.     register free_list_t fl;
  205.     register int i;
  206.  
  207.     if (base == 0)
  208.         return;
  209.     /*
  210.      * Find free list for block.
  211.      */
  212.     h = (header_t) (base - sizeof(union header));
  213.     fl = h->fl;
  214.     i = fl - malloc_free_list;
  215.     /*
  216.      * Sanity checks.
  217.      */
  218.     if (i < 0 || i >= NBUCKETS) {
  219.         ASSERT(0 <= i && i < NBUCKETS);
  220.         return;
  221.     }
  222.     if (fl != &malloc_free_list[i]) {
  223.         ASSERT(fl == &malloc_free_list[i]);
  224.         return;
  225.     }
  226.     /*
  227.      * Push block on free list.
  228.      */
  229.     spin_lock(&fl->lock);
  230.     h->next = fl->head;
  231.     fl->head = h;
  232. #ifdef    DEBUG
  233.     fl->in_use -= 1;
  234. #endif    DEBUG
  235.     spin_unlock(&fl->lock);
  236.     return;
  237. }
  238.  
  239. char *
  240. realloc(old_base, new_size)
  241.     char *old_base;
  242.     unsigned int new_size;
  243. {
  244.     register header_t h;
  245.     register free_list_t fl;
  246.     register int i;
  247.     unsigned int old_size;
  248.     char *new_base;
  249.  
  250.     if (old_base == 0)
  251.         return 0;
  252.     /*
  253.      * Find size of old block.
  254.      */
  255.     h = (header_t) (old_base - sizeof(union header));
  256.     fl = h->fl;
  257.     i = fl - malloc_free_list;
  258.     /*
  259.      * Sanity checks.
  260.      */
  261.     if (i < 0 || i >= NBUCKETS) {
  262.         ASSERT(0 <= i && i < NBUCKETS);
  263.         return 0;
  264.     }
  265.     if (fl != &malloc_free_list[i]) {
  266.         ASSERT(fl == &malloc_free_list[i]);
  267.         return 0;
  268.     }
  269.     /*
  270.      * Free list with index i contains blocks of size 2^(i+3) including header.
  271.      */
  272.     old_size = (1 << (i+3)) - sizeof(union header);
  273.     /*
  274.      * Allocate new block, copy old bytes, and free old block.
  275.      */
  276.     new_base = malloc(new_size);
  277.     if (new_base != 0)
  278.         bcopy(old_base, new_base, (int) (old_size < new_size ? old_size : new_size));
  279.     free(old_base);
  280.     return new_base;
  281. }
  282.  
  283. #ifdef    DEBUG
  284. void
  285. print_malloc_free_list()
  286. {
  287.       register int i, size;
  288.     register free_list_t fl;
  289.     register int n;
  290.       register header_t h;
  291.     int total_used = 0;
  292.     int total_free = 0;
  293.  
  294.     fprintf(stderr, "      Size     In Use       Free      Total\n");
  295.       for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
  296.          i < NBUCKETS;
  297.          i += 1, size <<= 1, fl += 1) {
  298.         spin_lock(&fl->lock);
  299.         if (fl->in_use != 0 || fl->head != 0) {
  300.             total_used += fl->in_use * size;
  301.             for (n = 0, h = fl->head; h != 0; h = h->next, n += 1)
  302.                 ;
  303.             total_free += n * size;
  304.             fprintf(stderr, "%10d %10d %10d %10d\n",
  305.                 size, fl->in_use, n, fl->in_use + n);
  306.         }
  307.         spin_unlock(&fl->lock);
  308.       }
  309.       fprintf(stderr, " all sizes %10d %10d %10d\n",
  310.         total_used, total_free, total_used + total_free);
  311. }
  312. #endif    DEBUG
  313.  
  314. void malloc_fork_prepare()
  315. /*
  316.  * Prepare the malloc module for a fork by insuring that no thread is in a
  317.  * malloc critical section.
  318.  */
  319. {
  320.     register int i;
  321.     
  322.     for (i = 0; i < NBUCKETS; i++) {
  323.     spin_lock(&malloc_free_list[i].lock);
  324.     }
  325. }
  326.  
  327. void malloc_fork_parent()
  328. /*
  329.  * Called in the parent process after a fork() to resume normal operation.
  330.  */
  331. {
  332.     register int i;
  333.  
  334.     for (i = NBUCKETS-1; i >= 0; i--) {
  335.     spin_unlock(&malloc_free_list[i].lock);
  336.     }
  337. }
  338.  
  339. void malloc_fork_child()
  340. /*
  341.  * Called in the child process after a fork() to resume normal operation.
  342.  */
  343. {
  344.     register int i;
  345.  
  346.     for (i = NBUCKETS-1; i >= 0; i--) {
  347.     spin_unlock(&malloc_free_list[i].lock);
  348.     }
  349. }
  350.