Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl

comparison vmalloc.c @ 116:35547e66b971

find changesets by author, revision, files, or words in the commit message
malloc: multiple small chunk allocation
author Merten Sach <msach@mailbox.tu-berlin.de>
date Mon, 29 Aug 2011 17:09:00 +0200
parents 62c59f2ac9f1
children 07e679ee2095
comparison
equal deleted inserted replaced
15:5f703d658f90 16:f60c85476efd
44 * Removes the first chunk of a freeList 44 * Removes the first chunk of a freeList
45 * The chunk is removed but not set as free. There is no check if 45 * The chunk is removed but not set as free. There is no check if
46 * the free list is empty, so make sure this is not the case. 46 * the free list is empty, so make sure this is not the case.
47 */ 47 */
48 inline 48 inline
49 MallocProlog *removeChunk(MallocProlog** container) 49 MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
50 { 50 {
51 MallocProlog *removedChunk = *container; 51 MallocProlog** container = &freeLists->bigChunks[containerIdx];
52 MallocProlog* removedChunk = *container;
52 *container = removedChunk->nextChunkInFreeList; 53 *container = removedChunk->nextChunkInFreeList;
53 54
54 if(removedChunk->nextChunkInFreeList) 55 if(removedChunk->nextChunkInFreeList)
55 removedChunk->nextChunkInFreeList->prevChunkInFreeList = 56 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
56 (MallocProlog*)container; 57 (MallocProlog*)container;
57 58
59 if(*container == NULL)
60 {
61 if(containerIdx < 64)
62 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
63 else
64 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
65 }
66
67 return removedChunk;
68 }
69
70 /*
71 * Removes the first chunk of a freeList
72 * The chunk is removed but not set as free. There is no check if
73 * the free list is empty, so make sure this is not the case.
74 */
75 inline
76 MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)
77 {
78 MallocProlog** container = &freeLists->smallChunks[containerIdx];
79 MallocProlog* removedChunk = *container;
80 *container = removedChunk->nextChunkInFreeList;
81
82 if(removedChunk->nextChunkInFreeList)
83 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
84 (MallocProlog*)container;
85
58 return removedChunk; 86 return removedChunk;
59 } 87 }
60 88
61 inline 89 inline
62 void recycleSmallChunks(MallocProlog** container) 90 void recycleSmallChunks(MallocProlog** container)
71 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists) 99 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
72 { 100 {
73 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList; 101 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
74 if(chunk->nextChunkInFreeList) 102 if(chunk->nextChunkInFreeList)
75 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList; 103 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
76 if(*(chunk->prevChunkInFreeList) == NULL) 104
77 { 105 //The last element in the list points to the container. If the container points
78 uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*); 106 //to NULL the container is empty
79 freeLists->bigChunksSearchVector &= ~(1 << containerIdx); 107 if(*((void**)(chunk->prevChunkInFreeList)) == NULL)
108 {
109 uint32 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 6;
110 if(containerIdx < (uint32)64)
111 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
112 if(containerIdx < 128 && containerIdx >=64)
113 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
80 } 114 }
81 } 115 }
82 116
83 /* 117 /*
84 * Merges two chunks. 118 * Merges two chunks.
142 176
143 uint32 containerIdx = getContainer(addedSize)+4; 177 uint32 containerIdx = getContainer(addedSize)+4;
144 while(freeLists->bigChunks[containerIdx] == NULL ) 178 while(freeLists->bigChunks[containerIdx] == NULL )
145 containerIdx++; 179 containerIdx++;
146 180
147 MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); 181 MallocProlog *foundChunk = removeChunk(freeLists, containerIdx);
148 182
149 int i; 183 int i;
150 for(i=0; i<5; i++) 184 for(i=0; i<5; i++)
151 { 185 {
152 insertChunk(divideChunk(foundChunk,size), container); 186 insertChunk(divideChunk(foundChunk,size), container);
153 } 187 }
154 containerIdx = getContainer(getChunkSize(foundChunk)); 188 containerIdx = getContainer(getChunkSize(foundChunk));
155 insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]); 189 insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
190 if(containerIdx < 64)
191 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
192 else
193 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
156 } 194 }
157 195
158 /* 196 /*
159 * This is sequential code, meant to only be called from the Master, not from 197 * This is sequential code, meant to only be called from the Master, not from
160 * any slave VPs. 198 * any slave VPs.
166 int32 startStamp, endStamp; 204 int32 startStamp, endStamp;
167 saveLowTimeStampCountInto( startStamp ); 205 saveLowTimeStampCountInto( startStamp );
168 #endif 206 #endif
169 //======================================================================== 207 //========================================================================
170 208
171
172 MallocArrays* freeLists = _VMSMasterEnv->freeLists; 209 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
173 210
174 //Return a small chunk if the requested size is smaller than 128B 211 //Return a small chunk if the requested size is smaller than 128B
175 if(sizeRequested <= LOWER_BOUND) 212 if(sizeRequested <= LOWER_BOUND)
176 { 213 {
180 makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]); 217 makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]);
181 freeLists->smallChunkCount[freeListIdx] += 5; 218 freeLists->smallChunkCount[freeListIdx] += 5;
182 } 219 }
183 220
184 freeLists->smallChunkCount[freeListIdx]--; 221 freeLists->smallChunkCount[freeListIdx]--;
185 return removeChunk(&freeLists->smallChunks[freeListIdx]) + 1; 222 return removeSmallChunk(freeLists, freeListIdx) + 1;
186 } 223 }
187 224
188 //Calculate the expected container. Start one higher to have a Chunk that's 225 //Calculate the expected container. Start one higher to have a Chunk that's
189 //always big enough. 226 //always big enough.
190 uint32 targetContainerIdx = getContainer(sizeRequested); 227 uint32 containerIdx = getContainer(sizeRequested) + 1;
191 uint32 containerIdx = targetContainerIdx + 1;
192 228
193 MallocProlog* foundChunk; 229 MallocProlog* foundChunk;
194 if(freeLists->bigChunks[containerIdx] == NULL) 230 if(freeLists->bigChunks[containerIdx] == NULL)
195 { 231 {
196 uint64 searchVector = freeLists->bigChunksSearchVector; 232 uint64 searchVector = freeLists->bigChunksSearchVector[0];
197 //set small chunk bits to zero 233 //set small chunk bits to zero
198 searchVector &= MAX_UINT64 << containerIdx; 234 searchVector &= MAX_UINT64 << containerIdx;
199 containerIdx = __builtin_ffsl(searchVector); 235 containerIdx = __builtin_ffsl(searchVector);
200 236
201 if(containerIdx == 0) 237 if(containerIdx == 0)
202 { 238 {
203 printf("VMS malloc failed: low memory"); 239 searchVector = freeLists->bigChunksSearchVector[1];
204 exit(1); 240 containerIdx = __builtin_ffsl(searchVector);
205 } 241 if(containerIdx == 0)
206 /*
207 while(freeList->bigChunks[containerIdx] == NULL)
208 {
209 containerIdx++;
210 if(containerIdx >= freeList->containerCount)
211 { 242 {
212 printf("VMS malloc failed: low memory"); 243 printf("VMS malloc failed: low memory");
213 exit(1); 244 exit(1);
214 } 245 }
215 }*/ 246 containerIdx += 64;
216 247 }
217 foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); 248 containerIdx--;
249
250
251 foundChunk = removeChunk(freeLists, containerIdx);
218 size_t chunkSize = getChunkSize(foundChunk); 252 size_t chunkSize = getChunkSize(foundChunk);
219 253
220 //If the new chunk is larger than the requested size: split 254 //If the new chunk is larger than the requested size: split
221 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND) 255 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND)
222 { 256 {
223 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested); 257 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
224 containerIdx = getContainer(getChunkSize(newChunk)); 258 containerIdx = getContainer(getChunkSize(foundChunk));
225 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]); 259 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
226 freeLists->bigChunksSearchVector |= 1 << containerIdx; 260 if(containerIdx < 64)
261 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
262 else
263 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
227 foundChunk = newChunk; 264 foundChunk = newChunk;
228 } 265 }
229 } 266 }
230 else 267 else
231 { 268 {
232 foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); 269 foundChunk = removeChunk(freeLists, containerIdx);
233 } 270 }
234 271
235 //Mark as allocated 272 //Mark as allocated
236 foundChunk->prevChunkInFreeList = NULL; 273 foundChunk->prevChunkInFreeList = NULL;
237 274
283 { 320 {
284 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL) 321 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
285 {//Chunk is not allocated 322 {//Chunk is not allocated
286 if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND) 323 if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
287 { 324 {
288 extractChunk(chunkToFree->nextLowerInMem); 325 extractChunk(chunkToFree->nextLowerInMem, freeLists);
289 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree); 326 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
290 } 327 }
291 } 328 }
292 } 329 }
293 if(chunkToFree->nextHigherInMem) 330 if(chunkToFree->nextHigherInMem)
294 { 331 {
295 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL) 332 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
296 {//Chunk is not allocated 333 {//Chunk is not allocated
297 if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND) 334 if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
298 { 335 {
299 extractChunk(chunkToFree->nextHigherInMem); 336 extractChunk(chunkToFree->nextHigherInMem, freeLists);
300 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem); 337 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
301 } 338 }
302 } 339 }
303 } 340 }
304 341
305 containerIdx = getContainer(chunkSize); 342 containerIdx = getContainer(getChunkSize(chunkToFree));
306 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]); 343 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
344 if(containerIdx < 64)
345 freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
346 else
347 freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
307 348
308 //============================= MEASUREMENT STUFF ======================== 349 //============================= MEASUREMENT STUFF ========================
309 #ifdef MEAS__TIME_MALLOC 350 #ifdef MEAS__TIME_MALLOC
310 saveLowTimeStampCountInto( endStamp ); 351 saveLowTimeStampCountInto( endStamp );
311 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist ); 352 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
412 //previous element in the queue is the container 453 //previous element in the queue is the container
413 firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1]; 454 firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
414 455
415 freeLists->bigChunks[container-1] = firstChunk; 456 freeLists->bigChunks[container-1] = firstChunk;
416 //Insert into bit search list 457 //Insert into bit search list
417 freeLists->bigChunksSearchVector |= (1 << (container-1)); 458 if(container <= 64)
459 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << (container-1));
460 else
461 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (container-65));
418 462
419 //Create dummy chunk to mark the top of stack this is of course 463 //Create dummy chunk to mark the top of stack this is of course
420 //never freed 464 //never freed
421 MallocProlog *dummyChunk = firstChunk->nextHigherInMem; 465 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
422 dummyChunk->nextHigherInMem = dummyChunk+1; 466 dummyChunk->nextHigherInMem = dummyChunk+1;