buddy.cpp
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:10k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2003 MySQL AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. #include "buddy.hpp"
  14. void Chunk256::setFree(bool free){
  15.   // Bit 0 of allocationTimeStamp represents if the segment is free or not
  16.   Uint32 offMask = 0x0; // A mask to set the 0 bit to 0
  17.   allocationTimeStamp = 0x0;
  18.   if(free) 
  19.     // Set this bit to 0, if segment should be free
  20.     allocationTimeStamp = allocationTimeStamp & offMask;
  21. }
  22. bool Chunk256::getFree(){
  23.   Uint32 offMask = 0x0; 
  24.   return ((allocationTimeStamp | offMask) == offMask ? true : false);
  25. }
  26. void Chunk256::setAllocationTimeStamp(Uint32 cTime){
  27.   // Bits 1-31 of allocationTimeStamp represent the allocation time for segment
  28.   
  29.   // printf("nSet allocation time. Current time %d", cTime);
  30.   Uint32 onMask = 0x80000000; // A mask to set the 0 bit to 1
  31.   allocationTimeStamp = 0x0;
  32.   allocationTimeStamp = onMask | cTime;
  33. }
  34. Uint32 Chunk256::getAllocationTimeStamp(){
  35.   Uint32 onMask = 0x80000000;
  36.   allocationTimeStamp = allocationTimeStamp ^ onMask;
  37.   printf("nGet allocation time. Time is %d", allocationTimeStamp);
  38.   return allocationTimeStamp;
  39. };
  40. bool BuddyMemory::allocate(int nChunksToAllocate) {
  41.   
  42.   // Allocate the memory block needed. This memory is deallocated in the
  43.   // destructor of TransporterRegistry.
  44.   printf("nAllocating %d chunks...", nChunksToAllocate);
  45.   startOfMemoryBlock = (Uint32*) malloc(256 * nChunksToAllocate);
  46.   if (startOfMemoryBlock == NULL)
  47.     return false;
  48.   
  49.   // Allocate the array of 256-byte chunks
  50.   chunk = new Chunk256[nChunksToAllocate];
  51.   
  52.   // Initialize the chunk-array. Every 8 kB segment consists of 32 chunks.
  53.   // Set all chunks to free and set the prev and next pointer 
  54.   for (int i=0; i < nChunksToAllocate; i++) {
  55.     chunk[i].setFree(true);
  56.     if (i%32 == 0) {  
  57.       // The first chunk in every segment will point to the prev and next segment
  58.       chunk[i].prevSegmentOfSameSize = i-32;
  59.       chunk[i].nextSegmentOfSameSize = i + 32;
  60.       chunk[0].prevSegmentOfSameSize = END_OF_CHUNK_LIST;
  61.       chunk[totalNoOfChunks-32].nextSegmentOfSameSize = END_OF_CHUNK_LIST;
  62.     } else {
  63.       // The rest of the chunks in the segments have undefined prev and next pointers
  64.       chunk[i].prevSegmentOfSameSize = UNDEFINED_CHUNK;
  65.       chunk[i].nextSegmentOfSameSize = UNDEFINED_CHUNK;
  66.     }
  67.   }
  68.   
  69.   // Initialize the freeSegment-pointers
  70.   for (int i=0; i<sz_MAX; i++)
  71.     freeSegment[i] = UNDEFINED_CHUNK;
  72.      
  73.   // There are only 8 kB segments at startup
  74.   freeSegment[sz_8192] = 0;
  75.   for (int i=0; i<sz_MAX; i++)
  76.     printf("nPointers: %d", freeSegment[i]);
  77.   return true;
  78. }
  79. bool BuddyMemory::getSegment(Uint32 size, Segment * dst) {
  80.   
  81.   // The no of chunks the user asked for
  82.   Uint32 nChunksAskedFor = ceil((double(size)/double(256)));
  83.   int segm;
  84.   printf("n%d chunks asked for", nChunksAskedFor);
  85.   // It may be that the closest segment size above 
  86.   // nChunksAskedFor*256 is not a size that is available in 
  87.   // the freeSegment-list, i.e. it may not be of FreeSegmentSize.
  88.   int nChunksToAllocate = nChunksAskedFor;
  89.   // Find the FreeSegmentSize closest above nChunksAskedFor
  90.   if ((nChunksToAllocate != 1) && (nChunksToAllocate % 2 != 0))
  91.     nChunksToAllocate++;
  92.   printf("n%d chunks to allocate", nChunksToAllocate);
  93.   int segmSize = logTwoPlus(nChunksToAllocate) - 1;
  94.   if (size-pow(2,segmSize) > 256) 
  95.     segmSize ++;
  96.   printf("nSegment size: %f", pow(2,int(8+segmSize)));
  97.   while ((segmSize <= sz_GET_MAX) && (freeSegment[segmSize] == UNDEFINED_CHUNK))
  98.     segmSize++;
  99.   segm = freeSegment[segmSize];
  100.   if (segm != UNDEFINED_CHUNK){
  101.     // Free segment of asked size or larger is found
  102.     
  103.     // Remove the found segment from the freeSegment-list
  104.     removeFromFreeSegmentList(segmSize, segm);
  105.     // Set all chunks to allocated (not free) and set the allocation time
  106.     // for the segment we are about to allocate
  107.     for (int i = segm; i <= segm+nChunksToAllocate; i++) {
  108.       chunk[i].setFree(false);
  109.       chunk[i].setAllocationTimeStamp(currentTime);
  110.     }
  111.     // Before returning the segment, check if it is larger than the segment asked for
  112.     if (nChunksAskedFor < nChunksToAllocate) 
  113.       release(nChunksAskedFor, nChunksToAllocate - nChunksAskedFor - 1);
  114.     
  115.     Segment segment;
  116.     segment.segmentAddress = startOfMemoryBlock+(segm * 256);
  117.     segment.segmentSize = 256 * nChunksAskedFor;
  118.     segment.releaseId = segm;
  119.     printf("nSegment: segment address = %d, segment size = %d, release Id = %d", 
  120.    segment.segmentAddress, segment.segmentSize, segment.releaseId);  
  121.     return true;
  122.   }
  123.   printf("nNo segments of asked size or larger are found");
  124.   return false;
  125. }
  126. void BuddyMemory::removeFromFreeSegmentList(int sz, int index) {
  127.   // Remove the segment from the freeSegment list
  128.   printf("nRemoving segment from list...");
  129.   if (index != UNDEFINED_CHUNK) {
  130.     Chunk256 prevChunk;
  131.     Chunk256 nextChunk;
  132.     int prevChunkIndex = chunk[index].prevSegmentOfSameSize;
  133.     int nextChunkIndex = chunk[index].nextSegmentOfSameSize;
  134.   
  135.     if (prevChunkIndex == END_OF_CHUNK_LIST) {
  136.       if (nextChunkIndex == END_OF_CHUNK_LIST)
  137. // We are about to remove the only element in the list
  138. freeSegment[sz] = UNDEFINED_CHUNK;
  139.       else {
  140. // We are about to remove the first element in the list
  141. nextChunk = chunk[nextChunkIndex];
  142. nextChunk.prevSegmentOfSameSize = END_OF_CHUNK_LIST;
  143. freeSegment[sz] = nextChunkIndex;
  144.       }
  145.     } else {
  146.       if (nextChunkIndex == END_OF_CHUNK_LIST) {
  147. // We are about to remove the last element in the list
  148. prevChunk = chunk[prevChunkIndex];
  149. prevChunk.nextSegmentOfSameSize = END_OF_CHUNK_LIST;
  150.       } else {
  151. // We are about to remove an element in the middle of the list
  152. prevChunk = chunk[prevChunkIndex];
  153. nextChunk = chunk[nextChunkIndex];
  154. prevChunk.nextSegmentOfSameSize = nextChunkIndex;
  155. nextChunk.prevSegmentOfSameSize = prevChunkIndex;
  156.       }
  157.     }
  158.   }
  159.   for (int i=0; i<sz_MAX; i++)
  160.     printf("nPointers: %d", freeSegment[i]);
  161. }
  162. void BuddyMemory::release(int releaseId, int size) {
  163.   int nChunksToRelease = (size == 0 ? 1 : ceil(double(size)/double(256)));
  164.   //nChunksToRelease = ceil(double(size)/double(256));
  165.   int startChunk = releaseId;
  166.   int endChunk = releaseId + nChunksToRelease - 1;
  167.   printf("n%d chunks to release (initially)", nChunksToRelease);
  168.  
  169.   // Set the chunks we are about to release to free
  170.   for (int i = startChunk; i <= endChunk; i++){
  171.     chunk[i].setFree(true);
  172.   }
  173.   // Look at the chunks before the segment we are about to release
  174.   for (int i = releaseId-1; i >= 0; i--) {
  175.     if (!chunk[i].getFree())
  176.       break;
  177.     else {
  178.       startChunk = i;
  179.       nChunksToRelease++;
  180.       // Look at the next-pointer. If it is valid, we have a 
  181.       // chunk that is the start of a free segment. Remove it 
  182.       // from the freeSegment-list.
  183.       if (chunk[i].nextSegmentOfSameSize != UNDEFINED_CHUNK)
  184. removeFromFreeSegmentList(size, i);
  185.     }
  186.   }
  187.   
  188.   // Look at the chunks after the segment we are about to release
  189.   for (int i = endChunk+1; i <= totalNoOfChunks; i++) {
  190.     if (!chunk[i].getFree())
  191.       break;
  192.     else {
  193.       endChunk = i;
  194.       nChunksToRelease++;
  195.       // Look at the next-pointer. If it is valid, we have a 
  196.       // chunk that is the start of a free segment. Remove it
  197.       // from the free segment list
  198.       if (chunk[i].nextSegmentOfSameSize != UNDEFINED_CHUNK)
  199. removeFromFreeSegmentList(size, i);
  200.     }
  201.   }
  202.  
  203.   // We have the start and end indexes and total no of free chunks. 
  204.   // Separate the chunks into segments that can be added to the
  205.   // freeSegments-list.
  206.   int restChunk = 0;
  207.   int segmSize; 
  208.   
  209.    printf("n%d chunks to release (finally)", nChunksToRelease);
  210.   
  211.   segmSize = logTwoPlus(nChunksToRelease) - 1;
  212.   if (segmSize > sz_MAX) {
  213.     segmSize = sz_MAX;
  214.   }
  215.    
  216.   nChunksToRelease = pow(2,segmSize);
  217.   addToFreeSegmentList(nChunksToRelease*256, startChunk);
  218. }
  219. void BuddyMemory::addToFreeSegmentList(int sz, int index) {
  220.   // Add a segment to the freeSegment list
  221.  
  222.   printf("nAsked to add segment of size %d", sz);
  223.   // Get an index in freeSegment list corresponding to sz size
  224.   int segmSize = logTwoPlus(sz) - 1;
  225.   if (sz - pow(2,segmSize) >= 256) 
  226.     segmSize ++;
  227.   sz = segmSize - 8; 
  228.  
  229.   int nextSegm = freeSegment[sz];
  230.   printf("nAdding a segment of size %f", pow(2,(8 + sz)));
  231.   freeSegment[sz] = index;
  232.   if (nextSegm == UNDEFINED_CHUNK) {
  233.     // We are about to add a segment to an empty list
  234.     chunk[index].prevSegmentOfSameSize = END_OF_CHUNK_LIST;
  235.     chunk[index].nextSegmentOfSameSize = END_OF_CHUNK_LIST;
  236.   }
  237.   else {
  238.     // Add the segment first in the list
  239.     chunk[index].prevSegmentOfSameSize = END_OF_CHUNK_LIST;
  240.     chunk[index].nextSegmentOfSameSize = nextSegm;
  241.     chunk[nextSegm].prevSegmentOfSameSize = index;
  242.   }
  243.  for (int i=0; i<sz_MAX; i++)
  244.     printf("nPointers: %d", freeSegment[i]);
  245. }
  246. Uint32 BuddyMemory::logTwoPlus(Uint32 arg) {
  247.   // Calculate log2(arg) + 1
  248.             
  249.   Uint32 resValue;
  250.   arg = arg | (arg >> 8);
  251.   arg = arg | (arg >> 4);
  252.   arg = arg | (arg >> 2);
  253.   arg = arg | (arg >> 1);
  254.   resValue = (arg & 0x5555) + ((arg >> 1) & 0x5555);
  255.   resValue = (resValue & 0x3333) + ((resValue >> 2) & 0x3333);
  256.   resValue = resValue + (resValue >> 4);
  257.   resValue = (resValue & 0xf) + ((resValue >> 8) & 0xf);
  258.   return resValue;
  259. }
  260. bool BuddyMemory::memoryAvailable() {
  261.   // Return true if there is at least 8 kB memory available
  262.   for (int i = sz_8192; i < sz_MAX; i++)
  263.     if (freeSegment[i] != UNDEFINED_CHUNK)
  264.       return true;
  265.   return false;   
  266. }
  267. void BuddyMemory::refreshTime(Uint32 time) {
  268.   if (time - currentTime > 1000) { 
  269.     // Update current time
  270.     currentTime = time;
  271.     // Go through the chunk-list every second and release 
  272.     // any chunks that have been allocated for too long
  273.     for (int i=0; i<totalNoOfChunks; i++) {
  274.       if ((!chunk[i].getFree()) && 
  275.   (currentTime-chunk[i].getAllocationTimeStamp() > ALLOCATION_TIMEOUT)) {
  276. release(i, 256);
  277. printf("nChunks hve been allocated for too long");
  278.       }
  279.     } 
  280.   }
  281. }