home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / stdlib / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-12  |  6.7 KB  |  258 lines
  1. /* 
  2.  * malloc.c --
  3.  *
  4.  *    Source code for the "malloc" library procedure.  See memInt.h
  5.  *    for overall information about how the allocator works.
  6.  *
  7.  * Copyright 1985, 1988 Regents of the University of California
  8.  * Permission to use, copy, modify, and distribute this
  9.  * software and its documentation for any purpose and without
  10.  * fee is hereby granted, provided that the above copyright
  11.  * notice appear in all copies.  The University of California
  12.  * makes no representations about the suitability of this
  13.  * software for any purpose.  It is provided "as is" without
  14.  * express or implied warranty.
  15.  */
  16.  
  17. #ifndef lint
  18. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/malloc.c,v 1.6 88/08/20 21:09:18 ouster Exp $ SPRITE (Berkeley)";
  19. #endif not lint
  20.  
  21. #include "stdlib.h"
  22. #include "memInt.h"
  23.  
  24.  
  25. /*
  26.  * ----------------------------------------------------------------------------
  27.  *
  28.  * malloc --
  29.  *
  30.  *    This procedure allocates a chunk of memory.
  31.  *
  32.  * Results:
  33.  *    The return value is a pointer to an area of at least bytesNeeded
  34.  *    bytes of free storage.  If no memory is available, then this
  35.  *    procedure will never return:  the MemChunkAlloc procedure 
  36.  *    determines what will happen.
  37.  *
  38.  * Side effects:
  39.  *    The returned block is marked as allocated and will not be
  40.  *    allocated to anyone else until it is returned with a call
  41.  *    to free.
  42.  *
  43.  * ----------------------------------------------------------------------------
  44.  */
  45.  
  46. ENTRY Address
  47. malloc(bytesNeeded)
  48.     register unsigned bytesNeeded;    /* How many bytes to allocate. */
  49. {
  50.     int            thisBlockSize, admin;
  51.     register Address    result;
  52.     Address        newRegion;
  53.     int            regionSize;
  54.     int            origSize;
  55.     register int    index;
  56.  
  57.     LOCK_MONITOR;
  58.  
  59. #ifdef MEM_TRACE
  60.     mem_NumAllocs++;
  61. #endif
  62.  
  63.     if (!memInitialized) {
  64.     MemInit();
  65.     }
  66.  
  67.     origSize = bytesNeeded;
  68.  
  69.     /* 
  70.      * Handle binned objects quickly, if possible.
  71.      */
  72.  
  73.     bytesNeeded = BYTES_TO_BLOCKSIZE(bytesNeeded);
  74.     index = BLOCKSIZE_TO_INDEX(bytesNeeded);
  75.     if (bytesNeeded <= BIN_SIZE) {
  76.     result = memFreeLists[index];
  77.     if (result == NOBIN) {
  78.         goto largeBlockAllocator;
  79.     }
  80.     if (result == (Address) NULL) {
  81.  
  82.         /*
  83.          * There aren't currently any free objects of this size.
  84.          * Call the client's function to obtain another region
  85.          * from the system.  While we're at it, get a whole bunch
  86.          * of objects of this size once and put all but one back
  87.          * on the free list.
  88.          */
  89.  
  90.         regionSize = BLOCKS_AT_ONCE * bytesNeeded;
  91.         newRegion = MemChunkAlloc(regionSize);
  92.  
  93.         while (regionSize >= bytesNeeded) {
  94.         SET_ADMIN(newRegion, memFreeLists[index]);
  95.         memFreeLists[index] = newRegion;
  96.         mem_NumBlocks[index] += 1;
  97.         newRegion += bytesNeeded;
  98.         regionSize -= bytesNeeded;
  99.         }
  100.         result = memFreeLists[index];
  101.     }
  102.  
  103.     memFreeLists[index] = (Address) GET_ADMIN(result);
  104.     SET_ADMIN(result, MARK_DUMMY(bytesNeeded));
  105.  
  106. #ifdef MEM_TRACE
  107.     mem_NumBinnedAllocs[index] += 1;
  108.     SET_PC(result);
  109.     SET_ORIG_SIZE(result, origSize);
  110.     MemDoTrace(TRUE, result, (Address)NULL, bytesNeeded);
  111. #endif MEM_TRACE
  112.  
  113.     UNLOCK_MONITOR;
  114.     return(result+sizeof(AdminInfo));
  115.     }
  116.  
  117.     /*
  118.      * This is a large object.  Step circularly through the blocks
  119.      * in the list, looking for one that's large enough to hold
  120.      * what's needed.
  121.      */
  122.  
  123. largeBlockAllocator:
  124.     if (origSize == 0) {
  125.     return (Address) NULL;
  126.     }
  127. #ifdef MEM_TRACE
  128.     mem_NumLargeAllocs += 1;
  129. #endif
  130.     result = memCurrentPtr;
  131.     while (TRUE) {
  132.     Address nextPtr;
  133.  
  134. #ifdef MEM_TRACE
  135.     mem_NumLargeLoops += 1;
  136. #endif
  137.     admin = GET_ADMIN(result);
  138.     thisBlockSize = SIZE(admin);
  139.     nextPtr = result+thisBlockSize;
  140.     if (!IS_IN_USE(admin)) {
  141.     
  142.         /*
  143.          * Several blocks in a row could have been freed since the last
  144.          * time we were here.  If so, merge them together.
  145.          */
  146.  
  147.         while (!IS_IN_USE(GET_ADMIN(nextPtr))) {
  148.         thisBlockSize += SIZE(GET_ADMIN(nextPtr));
  149.         admin = MARK_FREE(thisBlockSize);
  150.         SET_ADMIN(result, admin);
  151.         nextPtr = result+thisBlockSize;
  152.         }
  153.         if (thisBlockSize >= bytesNeeded) {
  154.         break;
  155.         }
  156.         if (thisBlockSize > memLargestFree) {
  157.         memLargestFree = thisBlockSize;
  158.         }
  159.     }
  160.  
  161.     /*
  162.      * This block won't do the job.  Go on to the next block.
  163.      */
  164.  
  165.     if (nextPtr != memLast) {
  166.         result = nextPtr;
  167.         continue;
  168.     }
  169.  
  170.     /*
  171.      * End of the list.  If there's any chance that there's
  172.      * enough free storage in the list to satisfy the request,
  173.      * then go back to the beginning of the list and start
  174.      * again.
  175.      */
  176.  
  177.     if ((memLargestFree + memBytesFreed) > bytesNeeded) {
  178.         memLargestFree = 0;
  179.         memBytesFreed = 0;
  180.         result = memFirst;
  181.         continue;
  182.     }
  183.  
  184.     /*
  185.      * Not enough free space in the list.  Allocate a new region
  186.      * of memory and add it to the list.
  187.      */
  188.  
  189.     if (bytesNeeded < MIN_REGION_SIZE) {
  190.         regionSize = MIN_REGION_SIZE;
  191.     } else {
  192.         regionSize = bytesNeeded + sizeof(AdminInfo);
  193.     }
  194.     newRegion = MemChunkAlloc(regionSize);
  195.     mem_NumLargeBytes += regionSize;
  196.  
  197.     /*
  198.      * If the new region immediately follows the end of the previous
  199.      * region, merge them together.  At this point result always
  200.      * points to a block of memory adjacent to and preceding the block
  201.      * of memory pointed to by memLast (memLast == nextPtr).  Thus it
  202.      * may be possible to merge the new region with both the region
  203.      * at result and the one at nextPtr.
  204.      */
  205.  
  206.     if (newRegion == (nextPtr+sizeof(AdminInfo))) {
  207.         newRegion = nextPtr;
  208.         regionSize += sizeof(AdminInfo);
  209.         if (!IS_IN_USE(admin)) {
  210.         newRegion = result;
  211.         regionSize += SIZE(admin);
  212.         }
  213.     } else {
  214.         SET_ADMIN(nextPtr, MARK_DUMMY(newRegion - nextPtr));
  215.     }
  216.  
  217.     /*
  218.      * Create a dummy block at the end of the new region, which links
  219.      * to "last".
  220.      */
  221.     
  222.     SET_ADMIN(newRegion, MARK_FREE(regionSize - sizeof(AdminInfo)));
  223.     memLast = newRegion + regionSize - sizeof(AdminInfo);
  224.     SET_ADMIN(memLast, MARK_DUMMY(0));
  225.  
  226.     /*
  227.      * Continue scanning the list (try result again in case it
  228.      * merged with the new region).
  229.      */
  230.     }
  231.  
  232.     /*
  233.      * At this point we've got a block that's large enough.  If it's
  234.      * larger than needed for the object, put the rest back on the
  235.      * free list (note: even if the remnant is smaller than the smallest
  236.      * large object, which means it'll be used by itself, we put it back
  237.      * on the list so it can merge with either this block or the next,
  238.      * whichever gets freed first).
  239.      */
  240.  
  241.     if (thisBlockSize < (bytesNeeded + sizeof(AdminInfo))) {
  242.     SET_ADMIN(result, MARK_IN_USE(admin));
  243.     } else {
  244.     SET_ADMIN(result+bytesNeeded, MARK_FREE(thisBlockSize-bytesNeeded));
  245.     SET_ADMIN(result, MARK_IN_USE(bytesNeeded));
  246.     }
  247.  
  248. #ifdef MEM_TRACE
  249.     SET_PC(result);
  250.     SET_ORIG_SIZE(result, origSize);
  251.     MemDoTrace(TRUE, result, (Address) NULL, bytesNeeded);
  252. #endif MEM_TRACE
  253.     memCurrentPtr = result;
  254.  
  255.     UNLOCK_MONITOR;
  256.     return(result+sizeof(AdminInfo));
  257. }
  258.