← Back to branch summary

~vadim-tk/percona-server/flushing-algo

« back to all changes in this revision

Viewing changes to storage/ndb/src/common/transporter/buddy.cpp

  • Committer: root
  • Date: 2011-10-29 01:34:40 UTC
  • Revision ID: root@hppro1.office.percona.com-20111029013440-qhnf4jk8kdjcf4e0
Initial import

Show diffs side-by-side

added added

removed removed

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