Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 147:98fc8f3761a2
Small changes to make SSR & SSR Sequential work
| author | Merten Sach <msach@mailbox.tu-berlin.de> |
|---|---|
| date | Tue, 27 Sep 2011 14:37:59 +0200 |
| parents | 79bb48d7d93b |
| children |
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 assert(chunkToFree->prevChunkInFreeList == NULL);
414 uint32 containerIdx;
415 _VMSMasterEnv->amtOfOutstandingMem += getChunkSize(chunkToFree) + sizeof(MallocProlog);
417 //Check for free neighbors
418 if(chunkToFree->nextLowerInMem)
419 {
420 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
421 {//Chunk is not allocated
422 extractChunk(chunkToFree->nextLowerInMem, freeLists);
423 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
424 }
425 }
426 if(chunkToFree->nextHigherInMem)
427 {
428 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
429 {//Chunk is not allocated
430 extractChunk(chunkToFree->nextHigherInMem, freeLists);
431 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
432 }
433 }
435 size_t chunkSize = getChunkSize(chunkToFree);
436 if(chunkSize < BIG_LOWER_BOUND)
437 {
438 containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1;
439 if(containerIdx > SMALL_CHUNK_COUNT-1)
440 containerIdx = SMALL_CHUNK_COUNT-1;
441 insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]);
442 }
443 else
444 {
445 containerIdx = getContainer(getChunkSize(chunkToFree)) - 1;
446 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
447 if(containerIdx < 64)
448 freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
449 else
450 freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
451 assert((freeLists->bigChunksSearchVector[0] & (uint64)1 << containerIdx) != 0);
452 }
454 //============================= MEASUREMENT STUFF ========================
455 #ifdef MEAS__TIME_MALLOC
456 saveLowTimeStampCountInto( endStamp );
457 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
458 #endif
459 //========================================================================
461 }
463 /*
464 * Designed to be called from the main thread outside of VMS, during init
465 */
466 MallocArrays *
467 VMS_ext__create_free_list()
468 {
469 //Initialize containers for small chunks and fill with zeros
470 MallocArrays *freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
472 freeLists->smallChunks =
473 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
474 memset((void*)freeLists->smallChunks,
475 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
477 //Calculate number of containers for big chunks
478 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
479 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
480 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
481 freeLists->containerCount = container;
483 //Create first element in lastContainer
484 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
485 if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);}
486 freeLists->memSpace = firstChunk;
488 //Touch memory to avoid page faults
489 void *ptr,*endPtr;
490 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
491 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
492 {
493 *(char*)ptr = 0;
494 }
496 firstChunk->nextLowerInMem = NULL;
497 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
498 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog));
499 firstChunk->nextChunkInFreeList = NULL;
500 //previous element in the queue is the container
501 firstChunk->prevChunkInFreeList = (MallocProlog*)&freeLists->bigChunks[container-2];
503 freeLists->bigChunks[container-2] = firstChunk;
504 //Insert into bit search list
505 if(container <= 65)
506 {
507 freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2));
508 freeLists->bigChunksSearchVector[1] = 0;
509 }
510 else
511 {
512 freeLists->bigChunksSearchVector[0] = 0;
513 freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66));
514 }
516 //Create dummy chunk to mark the top of stack this is of course
517 //never freed
518 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
519 dummyChunk->nextHigherInMem = dummyChunk+1;
520 dummyChunk->nextLowerInMem = NULL;
521 dummyChunk->nextChunkInFreeList = NULL;
522 dummyChunk->prevChunkInFreeList = NULL;
524 return freeLists;
525 }
528 /*Designed to be called from the main thread outside of VMS, during cleanup
529 */
530 void
531 VMS_ext__free_free_list( MallocArrays *freeLists )
532 {
533 free(freeLists->memSpace);
534 free(freeLists->bigChunks);
535 free(freeLists->smallChunks);
536 free(freeLists);
537 }