Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 141:79bb48d7d93b
changed free back to request to master and bugfixes
| author | Merten Sach <msach@mailbox.tu-berlin.de> |
|---|---|
| date | Wed, 21 Sep 2011 11:51:29 +0200 |
| parents | 2c8f3cf6c058 |
| children | 98fc8f3761a2 |
line source
1 /*
2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org
3 * Licensed under GNU General Public License version 2
4 *
5 * Author: seanhalle@yahoo.com
6 *
7 * Created on November 14, 2009, 9:07 PM
8 */
10 #include <malloc.h>
11 #include <inttypes.h>
12 #include <stdlib.h>
13 #include <stdio.h>
14 #include <string.h>
15 #include <math.h>
17 #define NDEBUG
18 #include <assert.h>
20 #include "VMS.h"
21 #include "vmalloc.h"
22 #include "Histogram/Histogram.h"
24 #define MAX_UINT64 0xFFFFFFFFFFFFFFFF
28 inline void
29 sendFreeReqst_lib(int receiverID, void *ptrToFree, VirtProcr *animPr);
31 inline void
32 sendFreeReqst_master(int receiverID, void *ptrToFree);
34 void VMS__check_free_list(MallocArrays *freeLists);
36 //A MallocProlog is a head element if the HigherInMem variable is NULL
37 //A Chunk is free if the prevChunkInFreeList variable is NULL
39 /*
40 * This calculates the container which fits the given size.
41 */
42 inline
43 uint32 getContainer(size_t size)
44 {
45 return (log2(size)-LOG128)/LOG54;
46 }
48 /*
49 * Removes the first chunk of a freeList
50 * The chunk is removed but not set as free. There is no check if
51 * the free list is empty, so make sure this is not the case.
52 */
53 inline
54 MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
55 {
56 MallocProlog** container = &freeLists->bigChunks[containerIdx];
57 MallocProlog* removedChunk = *container;
58 *container = removedChunk->nextChunkInFreeList;
60 if(removedChunk->nextChunkInFreeList)
61 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
62 (MallocProlog*)container;
64 assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0);
66 if(*container == NULL)
67 {
68 if(containerIdx < 64)
69 {
70 assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0);
71 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
72 }
73 else
74 {
75 assert((freeLists->bigChunksSearchVector[1] & ((uint64)1 << (containerIdx-64))) != 0);
76 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
77 }
78 }
79 return removedChunk;
80 }
82 /*
83 * Removes the first chunk of a freeList
84 * The chunk is removed but not set as free. There is no check if
85 * the free list is empty, so make sure this is not the case.
86 */
87 inline
88 MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)
89 {
90 MallocProlog** container = &freeLists->smallChunks[containerIdx];
91 MallocProlog* removedChunk = *container;
92 *container = removedChunk->nextChunkInFreeList;
94 if(removedChunk->nextChunkInFreeList)
95 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
96 (MallocProlog*)container;
98 return removedChunk;
99 }
101 inline
102 size_t getChunkSize(MallocProlog* chunk)
103 {
104 return (uintptr_t)chunk->nextHigherInMem -
105 (uintptr_t)chunk - sizeof(MallocProlog);
106 }
108 /*
109 * Removes a chunk from a free list.
110 */
111 inline
112 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
113 {
114 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
115 if(chunk->nextChunkInFreeList)
116 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
118 //The last element in the list points to the container. If the container points
119 //to NULL the container is empty
120 if(((*((void**)(chunk->prevChunkInFreeList))) == NULL) && (getChunkSize(chunk) >= BIG_LOWER_BOUND))
121 {
122 assert((*((void**)(chunk->prevChunkInFreeList))) == NULL);
123 //Find the approppiate container because we do not know it
124 uint64 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 3;
125 if(containerIdx < (uint64)64)
126 {
127 assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0);
128 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
129 }
130 if(containerIdx < 128 && containerIdx >=64)
131 {
132 assert((freeLists->bigChunksSearchVector[1] & ((uint64)1 << (containerIdx-64))) != 0);
133 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
134 }
136 }
137 }
139 /*
140 * Merges two chunks.
141 * Chunk A has to be before chunk B in memory. Both have to be removed from
142 * a free list
143 */
144 inline
145 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
146 {
147 chunkA->nextHigherInMem = chunkB->nextHigherInMem;
148 chunkB->nextHigherInMem->nextLowerInMem = chunkA;
149 return chunkA;
150 }
151 /*
152 * Inserts a chunk into a free list.
153 */
154 inline
155 void insertChunk(MallocProlog* chunk, MallocProlog** container)
156 {
157 chunk->nextChunkInFreeList = *container;
158 chunk->prevChunkInFreeList = (MallocProlog*)container;
159 if(*container)
160 (*container)->prevChunkInFreeList = chunk;
161 *container = chunk;
162 }
164 /*
165 * Divides the chunk that a new chunk of newSize is created.
166 * There is no size check, so make sure the size value is valid.
167 */
168 inline
169 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
170 {
171 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
172 newSize - sizeof(MallocProlog));
174 newChunk->nextLowerInMem = chunk;
175 newChunk->nextHigherInMem = chunk->nextHigherInMem;
177 chunk->nextHigherInMem->nextLowerInMem = newChunk;
178 chunk->nextHigherInMem = newChunk;
180 return newChunk;
181 }
183 /*
184 * Search for chunk in the list of big chunks. Split the block if it's too big
185 */
186 inline
187 MallocProlog *searchChunk(MallocArrays *freeLists, size_t sizeRequested, uint32 containerIdx)
188 {
189 MallocProlog* foundChunk;
191 uint64 searchVector = freeLists->bigChunksSearchVector[0];
192 //set small chunk bits to zero
193 searchVector &= MAX_UINT64 << containerIdx;
194 containerIdx = __builtin_ffsl(searchVector);
196 if(containerIdx == 0)
197 {
198 searchVector = freeLists->bigChunksSearchVector[1];
199 containerIdx = __builtin_ffsl(searchVector);
200 if(containerIdx == 0)
201 {
202 printf("VMS malloc failed: low memory");
203 exit(1);
204 }
205 containerIdx += 64;
206 }
207 containerIdx--; // ffsl index starts at 1
210 foundChunk = removeChunk(freeLists, containerIdx);
211 size_t chunkSize = getChunkSize(foundChunk);
213 //If the new chunk is larger than the requested size: split
214 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + BIG_LOWER_BOUND)
215 {
216 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
217 containerIdx = getContainer(getChunkSize(foundChunk)) - 1;
218 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
219 if(containerIdx < 64)
220 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
221 else
222 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
223 assert(freeLists->bigChunks[containerIdx] == foundChunk);
224 assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0);
225 foundChunk = newChunk;
226 }
228 return foundChunk;
229 }
231 /*
232 * This function is called by code which is part of the master loop.
233 * This reads the animating coreID from the MasterEnv and calls the normal malloc
234 * in VMS__malloc_on_core
235 */
236 void *
237 VMS__malloc( size_t sizeRequested)
238 {
239 return VMS__malloc_on_core(sizeRequested, _VMSMasterEnv->currentMasterProcrID);
240 }
242 /*
243 * This is called by the plugin. This call to VMS_malloc_on_core is run on the
244 * slave VPs stack so there is no switch to the VMS runtime.
245 */
246 void *
247 VMS__malloc_in_lib(size_t sizeRequested, VirtProcr *VProcr)
248 {
249 return VMS__malloc_on_core(sizeRequested, VProcr->coreAnimatedBy);
250 }
252 /*
253 * This is sequential code, meant to only be called from the Master, not from
254 * any slave VPs.
255 */
256 void *VMS__malloc_on_core( size_t sizeRequested, int procrID )
257 {
258 //============================= MEASUREMENT STUFF ========================
259 #ifdef MEAS__TIME_MALLOC
260 int32 startStamp, endStamp;
261 saveLowTimeStampCountInto( startStamp );
262 #endif
263 //========================================================================
265 MallocArrays* freeLists = _VMSMasterEnv->freeLists[procrID];
266 MallocProlog* foundChunk;
267 MallocPrologAllocated* returnChunk;
269 //Return a small chunk if the requested size is smaller than 128B
270 if(sizeRequested <= LOWER_BOUND)
271 {
272 uint32 freeListIdx = (sizeRequested-1)/SMALL_CHUNK_SIZE;
273 if(freeLists->smallChunks[freeListIdx] == NULL)
274 foundChunk = searchChunk(freeLists, SMALL_CHUNK_SIZE*(freeListIdx+1), 0);
275 else
276 foundChunk = removeSmallChunk(freeLists, freeListIdx);
278 _VMSMasterEnv->amtOfOutstandingMem -= getChunkSize(foundChunk) + sizeof(MallocProlog);
279 returnChunk = (MallocPrologAllocated*)foundChunk;
280 returnChunk->prevChunkInFreeList = NULL;//indicates elem currently allocated
281 returnChunk->procrID = procrID;
282 return returnChunk + 1;
283 }
285 //Calculate the expected container. Start one higher to have a Chunk that's
286 //always big enough.
287 uint32 containerIdx = getContainer(sizeRequested);
289 if(freeLists->bigChunks[containerIdx] == NULL)
290 foundChunk = searchChunk(freeLists, sizeRequested, containerIdx);
291 else
292 foundChunk = removeChunk(freeLists, containerIdx);
294 //Mark as allocated
295 _VMSMasterEnv->amtOfOutstandingMem -= getChunkSize(foundChunk) + sizeof(MallocProlog);
296 returnChunk = (MallocPrologAllocated*)foundChunk;
297 returnChunk->prevChunkInFreeList = NULL;//indicates elem currently allocated
298 returnChunk->procrID = procrID;
300 //============================= MEASUREMENT STUFF ========================
301 #ifdef MEAS__TIME_MALLOC
302 saveLowTimeStampCountInto( endStamp );
303 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
304 #endif
305 //========================================================================
306 assert(getChunkSize((MallocProlog*)returnChunk)>=sizeRequested);
308 //skip over the prolog by adding its size to the pointer return
309 return returnChunk + 1;
310 }
312 /*
313 * This free is called for a master loop. It decides whether the allocation of
314 * chunk was done on the same core. If it was it calls VMS__free_on_core
315 * otherwise it sends a message to the responsible core.
316 */
317 void
318 VMS__free(void *ptrToFree)
319 {
320 MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1;
321 if(chunk->procrID == _VMSMasterEnv->currentMasterProcrID)
322 {
323 VMS__free_on_core(ptrToFree, _VMSMasterEnv->currentMasterProcrID);
324 }
325 else
326 {
327 sendFreeReqst_master(chunk->procrID, ptrToFree);
329 }
330 }
332 /*
333 * This free is called for the plugins. It decides whether the allocation of
334 * chunk was done on the same core. If it was it calls VMS__free_on_core
335 * otherwise it sends a message to the responsible core.
336 */
337 void
338 VMS__free_in_lib(void *ptrToFree, VirtProcr *VProc)
339 {
340 MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1;
341 if(chunk->procrID == VProc->coreAnimatedBy)
342 {
343 VMS__free_on_core(ptrToFree, VProc->coreAnimatedBy);
344 }
345 else
346 {
347 sendFreeReqst_lib(chunk->procrID, ptrToFree, VProc);
348 }
349 }
351 /*
352 * This is called form a masterVP and request an free from a different masterVP.
353 * The free of the request structure is done after the request is handled.
354 */
355 inline void
356 sendFreeReqst_master(int receiverID, void *ptrToFree)
357 {
358 InterVMSCoreReqst *freeReqst = VMS__malloc(sizeof(InterVMSCoreReqst));
359 freeReqst->freePtr = ptrToFree;
360 freeReqst->secondReqType = transfer_free_ptr;
362 VMS__sendInterMasterReqst(receiverID, (InterMasterReqst*)freeReqst);
363 }
365 /*
366 * This is called if the free is called from the plugin. This requests an inter
367 * master request from his master.
368 */
369 inline void
370 sendFreeReqst_lib(int receiverID, void *ptrToFree, VirtProcr *animPr )
371 {
372 VMSSemReq reqData;
373 InterVMSCoreReqst *freeReqst = VMS__malloc(sizeof(InterVMSCoreReqst));
374 freeReqst->freePtr = ptrToFree;
375 freeReqst->secondReqType = transfer_free_ptr;
377 reqData.reqType = interMasterReqst;
378 reqData.receiverID = receiverID;
379 reqData.data = (void*)freeReqst;
381 VMS__send_VMSSem_request( (void*)&reqData, animPr );
382 }
384 void VMS__check_free_list(MallocArrays *freeLists)
385 {
386 int idx;
387 for(idx=0; idx< freeLists->containerCount; idx++)
388 {
389 if(freeLists->bigChunks[idx])
390 assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << idx)) != 0);
391 if((freeLists->bigChunksSearchVector[0] & ((uint64)1 << idx)))
392 assert(freeLists->bigChunks[idx] != NULL);
393 }
394 }
396 /*
397 * This is sequential code, meant to only be called from the Master, not from
398 * any slave VPs.
399 */
400 void
401 VMS__free_on_core( void *ptrToFree, int procrID )
402 {
404 //============================= MEASUREMENT STUFF ========================
405 #ifdef MEAS__TIME_MALLOC
406 int32 startStamp, endStamp;
407 saveLowTimeStampCountInto( startStamp );
408 #endif
409 //========================================================================
411 MallocArrays* freeLists = _VMSMasterEnv->freeLists[procrID];
412 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
413 uint32 containerIdx;
414 _VMSMasterEnv->amtOfOutstandingMem += getChunkSize(chunkToFree) + sizeof(MallocProlog);
416 //Check for free neighbors
417 if(chunkToFree->nextLowerInMem)
418 {
419 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
420 {//Chunk is not allocated
421 extractChunk(chunkToFree->nextLowerInMem, freeLists);
422 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
423 }
424 }
425 if(chunkToFree->nextHigherInMem)
426 {
427 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
428 {//Chunk is not allocated
429 extractChunk(chunkToFree->nextHigherInMem, freeLists);
430 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
431 }
432 }
434 size_t chunkSize = getChunkSize(chunkToFree);
435 if(chunkSize < BIG_LOWER_BOUND)
436 {
437 containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1;
438 if(containerIdx > SMALL_CHUNK_COUNT-1)
439 containerIdx = SMALL_CHUNK_COUNT-1;
440 insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]);
441 }
442 else
443 {
444 containerIdx = getContainer(getChunkSize(chunkToFree)) - 1;
445 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
446 if(containerIdx < 64)
447 freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
448 else
449 freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
450 assert((freeLists->bigChunksSearchVector[0] & (uint64)1 << containerIdx) != 0);
451 }
453 //============================= MEASUREMENT STUFF ========================
454 #ifdef MEAS__TIME_MALLOC
455 saveLowTimeStampCountInto( endStamp );
456 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
457 #endif
458 //========================================================================
460 }
462 /*
463 * Designed to be called from the main thread outside of VMS, during init
464 */
465 MallocArrays *
466 VMS_ext__create_free_list()
467 {
468 //Initialize containers for small chunks and fill with zeros
469 MallocArrays *freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
471 freeLists->smallChunks =
472 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
473 memset((void*)freeLists->smallChunks,
474 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
476 //Calculate number of containers for big chunks
477 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
478 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
479 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
480 freeLists->containerCount = container;
482 //Create first element in lastContainer
483 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
484 if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);}
485 freeLists->memSpace = firstChunk;
487 //Touch memory to avoid page faults
488 void *ptr,*endPtr;
489 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
490 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
491 {
492 *(char*)ptr = 0;
493 }
495 firstChunk->nextLowerInMem = NULL;
496 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
497 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog));
498 firstChunk->nextChunkInFreeList = NULL;
499 //previous element in the queue is the container
500 firstChunk->prevChunkInFreeList = (MallocProlog*)&freeLists->bigChunks[container-2];
502 freeLists->bigChunks[container-2] = firstChunk;
503 //Insert into bit search list
504 if(container <= 65)
505 {
506 freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2));
507 freeLists->bigChunksSearchVector[1] = 0;
508 }
509 else
510 {
511 freeLists->bigChunksSearchVector[0] = 0;
512 freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66));
513 }
515 //Create dummy chunk to mark the top of stack this is of course
516 //never freed
517 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
518 dummyChunk->nextHigherInMem = dummyChunk+1;
519 dummyChunk->nextLowerInMem = NULL;
520 dummyChunk->nextChunkInFreeList = NULL;
521 dummyChunk->prevChunkInFreeList = NULL;
523 return freeLists;
524 }
527 /*Designed to be called from the main thread outside of VMS, during cleanup
528 */
529 void
530 VMS_ext__free_free_list( MallocArrays *freeLists )
531 {
532 free(freeLists->memSpace);
533 free(freeLists->bigChunks);
534 free(freeLists->smallChunks);
535 free(freeLists);
536 }