The world's most popular open source database

MySQL 5.1: mysql/src/5.1-dbg/storage/ndb/src/common/transporter/buddy.cpp Source File
mysql/src/5.1-dbg/storage/ndb/src/common/transporter/buddy.cpp

00001 /* Copyright (C) 2003 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; either version 2 of the License, or
00006    (at your option) any later version.
00007 
00008    This program is distributed in the hope that it will be useful,
00009    but WITHOUT ANY WARRANTY; without even the implied warranty of
00010    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00011    GNU General Public License for more details.
00012 
00013    You should have received a copy of the GNU General Public License
00014    along with this program; if not, write to the Free Software
00015    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
00016 
00017 #include "buddy.hpp"
00018 
00019 void Chunk256::setFree(bool free){
00020   // Bit 0 of allocationTimeStamp represents if the segment is free or not
00021   Uint32 offMask = 0x0; // A mask to set the 0 bit to 0
00022   allocationTimeStamp = 0x0;
00023   if(free) 
00024     // Set this bit to 0, if segment should be free
00025     allocationTimeStamp = allocationTimeStamp & offMask;
00026 }
00027 
00028 bool Chunk256::getFree(){
00029   Uint32 offMask = 0x0; 
00030   return ((allocationTimeStamp | offMask) == offMask ? true : false);
00031 }
00032 
00033 void Chunk256::setAllocationTimeStamp(Uint32 cTime){
00034   // Bits 1-31 of allocationTimeStamp represent the allocation time for segment
00035   
00036   // printf("\nSet allocation time. Current time %d", cTime);
00037   Uint32 onMask = 0x80000000; // A mask to set the 0 bit to 1
00038   allocationTimeStamp = 0x0;
00039   allocationTimeStamp = onMask | cTime;
00040 }
00041 
00042 Uint32 Chunk256::getAllocationTimeStamp(){
00043   Uint32 onMask = 0x80000000;
00044   allocationTimeStamp = allocationTimeStamp ^ onMask;
00045   printf("\nGet allocation time. Time is %d", allocationTimeStamp);
00046   return allocationTimeStamp;
00047 };
00048 
00049 bool BuddyMemory::allocate(int nChunksToAllocate) {
00050   
00051   // Allocate the memory block needed. This memory is deallocated in the
00052   // destructor of TransporterRegistry.
00053 
00054   printf("\nAllocating %d chunks...", nChunksToAllocate);
00055 
00056   startOfMemoryBlock = (Uint32*) malloc(256 * nChunksToAllocate);
00057 
00058   if (startOfMemoryBlock == NULL)
00059     return false;
00060   
00061   // Allocate the array of 256-byte chunks
00062   chunk = new Chunk256[nChunksToAllocate];
00063   
00064   // Initialize the chunk-array. Every 8 kB segment consists of 32 chunks.
00065   // Set all chunks to free and set the prev and next pointer 
00066   for (int i=0; i < nChunksToAllocate; i++) {
00067     chunk[i].setFree(true);
00068     if (i%32 == 0) {  
00069       // The first chunk in every segment will point to the prev and next segment
00070       chunk[i].prevSegmentOfSameSize = i-32;
00071       chunk[i].nextSegmentOfSameSize = i + 32;
00072       chunk[0].prevSegmentOfSameSize = END_OF_CHUNK_LIST;
00073       chunk[totalNoOfChunks-32].nextSegmentOfSameSize = END_OF_CHUNK_LIST;
00074     } else {
00075       // The rest of the chunks in the segments have undefined prev and next pointers
00076       chunk[i].prevSegmentOfSameSize = UNDEFINED_CHUNK;
00077       chunk[i].nextSegmentOfSameSize = UNDEFINED_CHUNK;
00078     }
00079   }
00080   
00081   // Initialize the freeSegment-pointers
00082   for (int i=0; i<sz_MAX; i++)
00083     freeSegment[i] = UNDEFINED_CHUNK;
00084      
00085   // There are only 8 kB segments at startup
00086   freeSegment[sz_8192] = 0;
00087 
00088   for (int i=0; i<sz_MAX; i++)
00089     printf("\nPointers: %d", freeSegment[i]);
00090 
00091   return true;
00092 }
00093 
00094 
00095 bool BuddyMemory::getSegment(Uint32 size, Segment * dst) {
00096   
00097   // The no of chunks the user asked for
00098   Uint32 nChunksAskedFor = ceil((double(size)/double(256)));
00099   int segm;
00100 
00101   printf("\n%d chunks asked for", nChunksAskedFor);
00102 
00103   // It may be that the closest segment size above 
00104   // nChunksAskedFor*256 is not a size that is available in 
00105   // the freeSegment-list, i.e. it may not be of FreeSegmentSize.
00106   int nChunksToAllocate = nChunksAskedFor;
00107 
00108   // Find the FreeSegmentSize closest above nChunksAskedFor
00109   if ((nChunksToAllocate != 1) && (nChunksToAllocate % 2 != 0))
00110     nChunksToAllocate++;
00111 
00112   printf("\n%d chunks to allocate", nChunksToAllocate);
00113   int segmSize = logTwoPlus(nChunksToAllocate) - 1;
00114   if (size-pow(2,segmSize) > 256) 
00115     segmSize ++;
00116   printf("\nSegment size: %f", pow(2,int(8+segmSize)));
00117 
00118   while ((segmSize <= sz_GET_MAX) && (freeSegment[segmSize] == UNDEFINED_CHUNK))
00119     segmSize++;
00120 
00121   segm = freeSegment[segmSize];
00122   if (segm != UNDEFINED_CHUNK){
00123     // Free segment of asked size or larger is found
00124     
00125     // Remove the found segment from the freeSegment-list
00126     removeFromFreeSegmentList(segmSize, segm);
00127 
00128     // Set all chunks to allocated (not free) and set the allocation time
00129     // for the segment we are about to allocate
00130     for (int i = segm; i <= segm+nChunksToAllocate; i++) {
00131       chunk[i].setFree(false);
00132       chunk[i].setAllocationTimeStamp(currentTime);
00133     }
00134 
00135     // Before returning the segment, check if it is larger than the segment asked for
00136     if (nChunksAskedFor < nChunksToAllocate) 
00137       release(nChunksAskedFor, nChunksToAllocate - nChunksAskedFor - 1);
00138     
00139     Segment segment;
00140     segment.segmentAddress = startOfMemoryBlock+(segm * 256);
00141     segment.segmentSize = 256 * nChunksAskedFor;
00142     segment.releaseId = segm;
00143 
00144     printf("\nSegment: segment address = %d, segment size = %d, release Id = %d", 
00145            segment.segmentAddress, segment.segmentSize, segment.releaseId);  
00146 
00147     return true;
00148   }
00149   printf("\nNo segments of asked size or larger are found");
00150   return false;
00151 }
00152 
00153 void BuddyMemory::removeFromFreeSegmentList(int sz, int index) {
00154   // Remove the segment from the freeSegment list
00155 
00156   printf("\nRemoving segment from list...");
00157   if (index != UNDEFINED_CHUNK) {
00158     Chunk256 prevChunk;
00159     Chunk256 nextChunk;
00160     int prevChunkIndex = chunk[index].prevSegmentOfSameSize;
00161     int nextChunkIndex = chunk[index].nextSegmentOfSameSize;
00162   
00163     if (prevChunkIndex == END_OF_CHUNK_LIST) {
00164       if (nextChunkIndex == END_OF_CHUNK_LIST)
00165         // We are about to remove the only element in the list
00166         freeSegment[sz] = UNDEFINED_CHUNK;
00167       else {
00168         // We are about to remove the first element in the list
00169         nextChunk = chunk[nextChunkIndex];
00170         nextChunk.prevSegmentOfSameSize = END_OF_CHUNK_LIST;
00171         freeSegment[sz] = nextChunkIndex;
00172       }
00173     } else {
00174       if (nextChunkIndex == END_OF_CHUNK_LIST) {
00175         // We are about to remove the last element in the list
00176         prevChunk = chunk[prevChunkIndex];
00177         prevChunk.nextSegmentOfSameSize = END_OF_CHUNK_LIST;
00178       } else {
00179         // We are about to remove an element in the middle of the list
00180         prevChunk = chunk[prevChunkIndex];
00181         nextChunk = chunk[nextChunkIndex];
00182         prevChunk.nextSegmentOfSameSize = nextChunkIndex;
00183         nextChunk.prevSegmentOfSameSize = prevChunkIndex;
00184       }
00185     }
00186   }
00187   for (int i=0; i<sz_MAX; i++)
00188     printf("\nPointers: %d", freeSegment[i]);
00189 }
00190 
00191 void BuddyMemory::release(int releaseId, int size) {
00192 
00193   int nChunksToRelease = (size == 0 ? 1 : ceil(double(size)/double(256)));
00194   //nChunksToRelease = ceil(double(size)/double(256));
00195   int startChunk = releaseId;
00196   int endChunk = releaseId + nChunksToRelease - 1;
00197 
00198   printf("\n%d chunks to release (initially)", nChunksToRelease);
00199  
00200   // Set the chunks we are about to release to free
00201   for (int i = startChunk; i <= endChunk; i++){
00202     chunk[i].setFree(true);
00203   }
00204 
00205   // Look at the chunks before the segment we are about to release
00206   for (int i = releaseId-1; i >= 0; i--) {
00207     if (!chunk[i].getFree())
00208       break;
00209     else {
00210       startChunk = i;
00211       nChunksToRelease++;
00212       // Look at the next-pointer. If it is valid, we have a 
00213       // chunk that is the start of a free segment. Remove it 
00214       // from the freeSegment-list.
00215       if (chunk[i].nextSegmentOfSameSize != UNDEFINED_CHUNK)
00216         removeFromFreeSegmentList(size, i);
00217     }
00218   }
00219   
00220   // Look at the chunks after the segment we are about to release
00221   for (int i = endChunk+1; i <= totalNoOfChunks; i++) {
00222     if (!chunk[i].getFree())
00223       break;
00224     else {
00225       endChunk = i;
00226       nChunksToRelease++;
00227       // Look at the next-pointer. If it is valid, we have a 
00228       // chunk that is the start of a free segment. Remove it
00229       // from the free segment list
00230       if (chunk[i].nextSegmentOfSameSize != UNDEFINED_CHUNK)
00231         removeFromFreeSegmentList(size, i);
00232     }
00233   }
00234  
00235   // We have the start and end indexes and total no of free chunks. 
00236   // Separate the chunks into segments that can be added to the
00237   // freeSegments-list.
00238   int restChunk = 0;
00239   int segmSize; 
00240   
00241    printf("\n%d chunks to release (finally)", nChunksToRelease);
00242   
00243   segmSize = logTwoPlus(nChunksToRelease) - 1;
00244   if (segmSize > sz_MAX) {
00245     segmSize = sz_MAX;
00246   }
00247    
00248   nChunksToRelease = pow(2,segmSize);
00249   addToFreeSegmentList(nChunksToRelease*256, startChunk);
00250 }
00251 
00252 void BuddyMemory::addToFreeSegmentList(int sz, int index) {
00253   // Add a segment to the freeSegment list
00254  
00255   printf("\nAsked to add segment of size %d", sz);
00256 
00257   // Get an index in freeSegment list corresponding to sz size
00258   int segmSize = logTwoPlus(sz) - 1;
00259   if (sz - pow(2,segmSize) >= 256) 
00260     segmSize ++;
00261   sz = segmSize - 8; 
00262  
00263   int nextSegm = freeSegment[sz];
00264 
00265   printf("\nAdding a segment of size %f", pow(2,(8 + sz)));
00266 
00267   freeSegment[sz] = index;
00268   if (nextSegm == UNDEFINED_CHUNK) {
00269     // We are about to add a segment to an empty list
00270     chunk[index].prevSegmentOfSameSize = END_OF_CHUNK_LIST;
00271     chunk[index].nextSegmentOfSameSize = END_OF_CHUNK_LIST;
00272   }
00273   else {
00274     // Add the segment first in the list
00275     chunk[index].prevSegmentOfSameSize = END_OF_CHUNK_LIST;
00276     chunk[index].nextSegmentOfSameSize = nextSegm;
00277     chunk[nextSegm].prevSegmentOfSameSize = index;
00278   }
00279 
00280  for (int i=0; i<sz_MAX; i++)
00281     printf("\nPointers: %d", freeSegment[i]);
00282 
00283 }
00284 
00285 Uint32 BuddyMemory::logTwoPlus(Uint32 arg) {
00286   // Calculate log2(arg) + 1
00287             
00288   Uint32 resValue;
00289 
00290   arg = arg | (arg >> 8);
00291   arg = arg | (arg >> 4);
00292   arg = arg | (arg >> 2);
00293   arg = arg | (arg >> 1);
00294   resValue = (arg & 0x5555) + ((arg >> 1) & 0x5555);
00295   resValue = (resValue & 0x3333) + ((resValue >> 2) & 0x3333);
00296   resValue = resValue + (resValue >> 4);
00297   resValue = (resValue & 0xf) + ((resValue >> 8) & 0xf);
00298 
00299   return resValue;
00300 }
00301 
00302 bool BuddyMemory::memoryAvailable() {
00303   // Return true if there is at least 8 kB memory available
00304   for (int i = sz_8192; i < sz_MAX; i++)
00305     if (freeSegment[i] != UNDEFINED_CHUNK)
00306       return true;
00307   return false;   
00308 }
00309 
00310 
00311 void BuddyMemory::refreshTime(Uint32 time) {
00312   if (time - currentTime > 1000) { 
00313     // Update current time
00314     currentTime = time;
00315     // Go through the chunk-list every second and release 
00316     // any chunks that have been allocated for too long
00317     for (int i=0; i<totalNoOfChunks; i++) {
00318       if ((!chunk[i].getFree()) && 
00319           (currentTime-chunk[i].getAllocationTimeStamp() > ALLOCATION_TIMEOUT)) {
00320         release(i, 256);
00321         printf("\nChunks hve been allocated for too long");
00322       }
00323     } 
00324   }
00325 }
Generated on Sat Sep 9 00:50:39 2006 for MySQL 5.1 by
1.4.7