diff options
Diffstat (limited to 'storage/ndb/src/common/transporter/buddy.cpp')
| -rw-r--r-- | storage/ndb/src/common/transporter/buddy.cpp | 325 |
1 files changed, 325 insertions, 0 deletions
diff --git a/storage/ndb/src/common/transporter/buddy.cpp b/storage/ndb/src/common/transporter/buddy.cpp new file mode 100644 index 00000000000..dc25e2dc66c --- /dev/null +++ b/storage/ndb/src/common/transporter/buddy.cpp @@ -0,0 +1,325 @@ +/* Copyright (C) 2003 MySQL AB + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +#include "buddy.hpp" + +void Chunk256::setFree(bool free){ + // Bit 0 of allocationTimeStamp represents if the segment is free or not + Uint32 offMask = 0x0; // A mask to set the 0 bit to 0 + allocationTimeStamp = 0x0; + if(free) + // Set this bit to 0, if segment should be free + allocationTimeStamp = allocationTimeStamp & offMask; +} + +bool Chunk256::getFree(){ + Uint32 offMask = 0x0; + return ((allocationTimeStamp | offMask) == offMask ? true : false); +} + +void Chunk256::setAllocationTimeStamp(Uint32 cTime){ + // Bits 1-31 of allocationTimeStamp represent the allocation time for segment + + // printf("\nSet allocation time. Current time %d", cTime); + Uint32 onMask = 0x80000000; // A mask to set the 0 bit to 1 + allocationTimeStamp = 0x0; + allocationTimeStamp = onMask | cTime; +} + +Uint32 Chunk256::getAllocationTimeStamp(){ + Uint32 onMask = 0x80000000; + allocationTimeStamp = allocationTimeStamp ^ onMask; + printf("\nGet allocation time. Time is %d", allocationTimeStamp); + return allocationTimeStamp; +}; + +bool BuddyMemory::allocate(int nChunksToAllocate) { + + // Allocate the memory block needed. This memory is deallocated in the + // destructor of TransporterRegistry. + + printf("\nAllocating %d chunks...", nChunksToAllocate); + + startOfMemoryBlock = (Uint32*) malloc(256 * nChunksToAllocate); + + if (startOfMemoryBlock == NULL) + return false; + + // Allocate the array of 256-byte chunks + chunk = new Chunk256[nChunksToAllocate]; + + // Initialize the chunk-array. Every 8 kB segment consists of 32 chunks. + // Set all chunks to free and set the prev and next pointer + for (int i=0; i < nChunksToAllocate; i++) { + chunk[i].setFree(true); + if (i%32 == 0) { + // The first chunk in every segment will point to the prev and next segment + chunk[i].prevSegmentOfSameSize = i-32; + chunk[i].nextSegmentOfSameSize = i + 32; + chunk[0].prevSegmentOfSameSize = END_OF_CHUNK_LIST; + chunk[totalNoOfChunks-32].nextSegmentOfSameSize = END_OF_CHUNK_LIST; + } else { + // The rest of the chunks in the segments have undefined prev and next pointers + chunk[i].prevSegmentOfSameSize = UNDEFINED_CHUNK; + chunk[i].nextSegmentOfSameSize = UNDEFINED_CHUNK; + } + } + + // Initialize the freeSegment-pointers + for (int i=0; i<sz_MAX; i++) + freeSegment[i] = UNDEFINED_CHUNK; + + // There are only 8 kB segments at startup + freeSegment[sz_8192] = 0; + + for (int i=0; i<sz_MAX; i++) + printf("\nPointers: %d", freeSegment[i]); + + return true; +} + + +bool BuddyMemory::getSegment(Uint32 size, Segment * dst) { + + // The no of chunks the user asked for + Uint32 nChunksAskedFor = ceil((double(size)/double(256))); + int segm; + + printf("\n%d chunks asked for", nChunksAskedFor); + + // It may be that the closest segment size above + // nChunksAskedFor*256 is not a size that is available in + // the freeSegment-list, i.e. it may not be of FreeSegmentSize. + int nChunksToAllocate = nChunksAskedFor; + + // Find the FreeSegmentSize closest above nChunksAskedFor + if ((nChunksToAllocate != 1) && (nChunksToAllocate % 2 != 0)) + nChunksToAllocate++; + + printf("\n%d chunks to allocate", nChunksToAllocate); + int segmSize = logTwoPlus(nChunksToAllocate) - 1; + if (size-pow(2,segmSize) > 256) + segmSize ++; + printf("\nSegment size: %f", pow(2,int(8+segmSize))); + + while ((segmSize <= sz_GET_MAX) && (freeSegment[segmSize] == UNDEFINED_CHUNK)) + segmSize++; + + segm = freeSegment[segmSize]; + if (segm != UNDEFINED_CHUNK){ + // Free segment of asked size or larger is found + + // Remove the found segment from the freeSegment-list + removeFromFreeSegmentList(segmSize, segm); + + // Set all chunks to allocated (not free) and set the allocation time + // for the segment we are about to allocate + for (int i = segm; i <= segm+nChunksToAllocate; i++) { + chunk[i].setFree(false); + chunk[i].setAllocationTimeStamp(currentTime); + } + + // Before returning the segment, check if it is larger than the segment asked for + if (nChunksAskedFor < nChunksToAllocate) + release(nChunksAskedFor, nChunksToAllocate - nChunksAskedFor - 1); + + Segment segment; + segment.segmentAddress = startOfMemoryBlock+(segm * 256); + segment.segmentSize = 256 * nChunksAskedFor; + segment.releaseId = segm; + + printf("\nSegment: segment address = %d, segment size = %d, release Id = %d", + segment.segmentAddress, segment.segmentSize, segment.releaseId); + + return true; + } + printf("\nNo segments of asked size or larger are found"); + return false; +} + +void BuddyMemory::removeFromFreeSegmentList(int sz, int index) { + // Remove the segment from the freeSegment list + + printf("\nRemoving segment from list..."); + if (index != UNDEFINED_CHUNK) { + Chunk256 prevChunk; + Chunk256 nextChunk; + int prevChunkIndex = chunk[index].prevSegmentOfSameSize; + int nextChunkIndex = chunk[index].nextSegmentOfSameSize; + + if (prevChunkIndex == END_OF_CHUNK_LIST) { + if (nextChunkIndex == END_OF_CHUNK_LIST) + // We are about to remove the only element in the list + freeSegment[sz] = UNDEFINED_CHUNK; + else { + // We are about to remove the first element in the list + nextChunk = chunk[nextChunkIndex]; + nextChunk.prevSegmentOfSameSize = END_OF_CHUNK_LIST; + freeSegment[sz] = nextChunkIndex; + } + } else { + if (nextChunkIndex == END_OF_CHUNK_LIST) { + // We are about to remove the last element in the list + prevChunk = chunk[prevChunkIndex]; + prevChunk.nextSegmentOfSameSize = END_OF_CHUNK_LIST; + } else { + // We are about to remove an element in the middle of the list + prevChunk = chunk[prevChunkIndex]; + nextChunk = chunk[nextChunkIndex]; + prevChunk.nextSegmentOfSameSize = nextChunkIndex; + nextChunk.prevSegmentOfSameSize = prevChunkIndex; + } + } + } + for (int i=0; i<sz_MAX; i++) + printf("\nPointers: %d", freeSegment[i]); +} + +void BuddyMemory::release(int releaseId, int size) { + + int nChunksToRelease = (size == 0 ? 1 : ceil(double(size)/double(256))); + //nChunksToRelease = ceil(double(size)/double(256)); + int startChunk = releaseId; + int endChunk = releaseId + nChunksToRelease - 1; + + printf("\n%d chunks to release (initially)", nChunksToRelease); + + // Set the chunks we are about to release to free + for (int i = startChunk; i <= endChunk; i++){ + chunk[i].setFree(true); + } + + // Look at the chunks before the segment we are about to release + for (int i = releaseId-1; i >= 0; i--) { + if (!chunk[i].getFree()) + break; + else { + startChunk = i; + nChunksToRelease++; + // Look at the next-pointer. If it is valid, we have a + // chunk that is the start of a free segment. Remove it + // from the freeSegment-list. + if (chunk[i].nextSegmentOfSameSize != UNDEFINED_CHUNK) + removeFromFreeSegmentList(size, i); + } + } + + // Look at the chunks after the segment we are about to release + for (int i = endChunk+1; i <= totalNoOfChunks; i++) { + if (!chunk[i].getFree()) + break; + else { + endChunk = i; + nChunksToRelease++; + // Look at the next-pointer. If it is valid, we have a + // chunk that is the start of a free segment. Remove it + // from the free segment list + if (chunk[i].nextSegmentOfSameSize != UNDEFINED_CHUNK) + removeFromFreeSegmentList(size, i); + } + } + + // We have the start and end indexes and total no of free chunks. + // Separate the chunks into segments that can be added to the + // freeSegments-list. + int restChunk = 0; + int segmSize; + + printf("\n%d chunks to release (finally)", nChunksToRelease); + + segmSize = logTwoPlus(nChunksToRelease) - 1; + if (segmSize > sz_MAX) { + segmSize = sz_MAX; + } + + nChunksToRelease = pow(2,segmSize); + addToFreeSegmentList(nChunksToRelease*256, startChunk); +} + +void BuddyMemory::addToFreeSegmentList(int sz, int index) { + // Add a segment to the freeSegment list + + printf("\nAsked to add segment of size %d", sz); + + // Get an index in freeSegment list corresponding to sz size + int segmSize = logTwoPlus(sz) - 1; + if (sz - pow(2,segmSize) >= 256) + segmSize ++; + sz = segmSize - 8; + + int nextSegm = freeSegment[sz]; + + printf("\nAdding a segment of size %f", pow(2,(8 + sz))); + + freeSegment[sz] = index; + if (nextSegm == UNDEFINED_CHUNK) { + // We are about to add a segment to an empty list + chunk[index].prevSegmentOfSameSize = END_OF_CHUNK_LIST; + chunk[index].nextSegmentOfSameSize = END_OF_CHUNK_LIST; + } + else { + // Add the segment first in the list + chunk[index].prevSegmentOfSameSize = END_OF_CHUNK_LIST; + chunk[index].nextSegmentOfSameSize = nextSegm; + chunk[nextSegm].prevSegmentOfSameSize = index; + } + + for (int i=0; i<sz_MAX; i++) + printf("\nPointers: %d", freeSegment[i]); + +} + +Uint32 BuddyMemory::logTwoPlus(Uint32 arg) { + // Calculate log2(arg) + 1 + + Uint32 resValue; + + arg = arg | (arg >> 8); + arg = arg | (arg >> 4); + arg = arg | (arg >> 2); + arg = arg | (arg >> 1); + resValue = (arg & 0x5555) + ((arg >> 1) & 0x5555); + resValue = (resValue & 0x3333) + ((resValue >> 2) & 0x3333); + resValue = resValue + (resValue >> 4); + resValue = (resValue & 0xf) + ((resValue >> 8) & 0xf); + + return resValue; +} + +bool BuddyMemory::memoryAvailable() { + // Return true if there is at least 8 kB memory available + for (int i = sz_8192; i < sz_MAX; i++) + if (freeSegment[i] != UNDEFINED_CHUNK) + return true; + return false; +} + + +void BuddyMemory::refreshTime(Uint32 time) { + if (time - currentTime > 1000) { + // Update current time + currentTime = time; + // Go through the chunk-list every second and release + // any chunks that have been allocated for too long + for (int i=0; i<totalNoOfChunks; i++) { + if ((!chunk[i].getFree()) && + (currentTime-chunk[i].getAllocationTimeStamp() > ALLOCATION_TIMEOUT)) { + release(i, 256); + printf("\nChunks hve been allocated for too long"); + } + } + } +} |