The world's most popular open source database

MySQL 5.1: BuddyMemory Class Reference

BuddyMemory Class Reference

#include <buddy.hpp>

Collaboration diagram for BuddyMemory:


Public Member Functions
bool	memoryAvailable ()
bool	allocate (int nChunksToAllocate)
void	removeFromFreeSegmentList (int sz, int index)
void	release (int releaseId, int size)
void	addToFreeSegmentList (int sz, int index)
bool	getSegment (Uint32 size, Segment *dst)
void	refreshTime (Uint32 time)
Uint32	logTwoPlus (Uint32 arg)
Public Attributes
Uint32	currentTime
Uint32	freeSegment [sz_MAX]
Uint32 *	startOfMemoryBlock
Uint32	totalNoOfChunks
Chunk256 *	chunk

Detailed Description

Definition at line 56 of file buddy.hpp.

Member Function Documentation

void BuddyMemory::addToFreeSegmentList	(	int	sz,
		int	index
	)

Definition at line 252 of file buddy.cpp.

References chunk, END_OF_CHUNK_LIST, freeSegment, logTwoPlus(), Chunk256::nextSegmentOfSameSize, Chunk256::prevSegmentOfSameSize, sz_MAX, and UNDEFINED_CHUNK.

Referenced by release().

00252                                                         {
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 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool BuddyMemory::allocate ( int nChunksToAllocate )

Definition at line 49 of file buddy.cpp.

References chunk, END_OF_CHUNK_LIST, freeSegment, malloc, Chunk256::nextSegmentOfSameSize, NULL, Chunk256::prevSegmentOfSameSize, startOfMemoryBlock, sz_8192, sz_MAX, totalNoOfChunks, and UNDEFINED_CHUNK.

00049                                                 {
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 }

bool BuddyMemory::getSegment	(	Uint32	size,
		Segment *	dst
	)

Definition at line 95 of file buddy.cpp.

References chunk, currentTime, freeSegment, logTwoPlus(), release(), Segment::releaseId, removeFromFreeSegmentList(), Segment::segmentAddress, Segment::segmentSize, Chunk256::setAllocationTimeStamp(), startOfMemoryBlock, sz_GET_MAX, and UNDEFINED_CHUNK.

00095                                                        {
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 }

Here is the call graph for this function:

Uint32 BuddyMemory::logTwoPlus ( Uint32 arg )

Definition at line 285 of file buddy.cpp.

Referenced by addToFreeSegmentList(), getSegment(), and release().

00285                                          {
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 }

Here is the caller graph for this function:

bool BuddyMemory::memoryAvailable ( )

Definition at line 302 of file buddy.cpp.

References freeSegment, sz_8192, sz_MAX, and UNDEFINED_CHUNK.

00302                                   {
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 }

void BuddyMemory::refreshTime ( Uint32 time )

Definition at line 311 of file buddy.cpp.

References ALLOCATION_TIMEOUT, chunk, currentTime, release(), and totalNoOfChunks.

00311                                          {
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 }

Here is the call graph for this function:

void BuddyMemory::release	(	int	releaseId,
		int	size
	)

Definition at line 191 of file buddy.cpp.

References addToFreeSegmentList(), chunk, logTwoPlus(), removeFromFreeSegmentList(), sz_MAX, totalNoOfChunks, and UNDEFINED_CHUNK.

Referenced by getSegment(), and refreshTime().

00191                                                  {
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 }

Here is the call graph for this function:

Here is the caller graph for this function:

void BuddyMemory::removeFromFreeSegmentList	(	int	sz,
		int	index
	)

Definition at line 153 of file buddy.cpp.

References chunk, END_OF_CHUNK_LIST, freeSegment, Chunk256::nextSegmentOfSameSize, Chunk256::prevSegmentOfSameSize, sz_MAX, and UNDEFINED_CHUNK.

Referenced by getSegment(), and release().

00153                                                              {
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 }