Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 134:a9b72021f053
Distributed memory management w/o free requests working
| author | Merten Sach <msach@mailbox.tu-berlin.de> |
|---|---|
| date | Fri, 16 Sep 2011 16:19:24 +0200 |
| parents | dbfc8382d546 |
| children | 0b49fd35afc1 |
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>
15 #include "VMS.h"
16 #include "Histogram/Histogram.h"
18 /*Helper function
19 *Insert a newly generated free chunk into the first spot on the free list.
20 * The chunk is cast as a MallocProlog, so the various pointers in it are
21 * accessed with C's help -- and the size of the prolog is easily added to
22 * the pointer when a chunk is returned to the app -- so C handles changes
23 * in pointer sizes among machines.
24 *
25 *The list head is a normal MallocProlog struct -- identified by its
26 * prevChunkInFreeList being NULL -- the only one.
27 *
28 *The end of the list is identified by next chunk being NULL, as usual.
29 */
30 void inline
31 add_chunk_to_free_list( MallocProlog *chunk, MallocProlog *listHead )
32 {
33 chunk->nextChunkInFreeList = listHead->nextChunkInFreeList;
34 if( chunk->nextChunkInFreeList != NULL ) //if not last in free list
35 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk;
36 chunk->prevChunkInFreeList = listHead;
37 listHead->nextChunkInFreeList = chunk;
38 }
40 /*
41 * This function is called by code which is part of the master loop.
42 * This reads the animating coreID from the MasterEnv and calls the normal malloc
43 * in VMS__malloc_on_core
44 */
45 void *
46 VMS__malloc( size_t sizeRequested)
47 {
48 return VMS__malloc_on_core(sizeRequested, _VMSMasterEnv->currentMasterProcrID);
49 }
51 /*
52 * This is called by the plugin. This call to VMS_malloc_on_core is run on the
53 * slave VPs stack so there is no switch to the VMS runtime.
54 */
55 void *
56 VMS__malloc_in_lib(size_t sizeRequested, VirtProcr *VProcr)
57 {
58 return VMS__malloc_on_core(sizeRequested, VProcr->coreAnimatedBy);
59 }
61 /*
62 *Search down list, checking size by the nextHigherInMem pointer, to find
63 * first chunk bigger than size needed.
64 *Shave off the extra and make it into a new free-list element, hook it in
65 * then return the address of the found element plus size of prolog.
66 */
67 void *
68 VMS__malloc_on_core( size_t sizeRequested, int procrID)
69 { MallocProlog *foundElem = NULL, *currElem, *newElem;
70 MallocPrologAllocated *returnElem;
71 ssize_t amountExtra, sizeConsumed,sizeOfFound;
72 uint32 foundElemIsTopOfHeap;
74 printf("Malloc on core %d\n", procrID);
76 //============================= MEASUREMENT STUFF ========================
77 #ifdef MEAS__TIME_MALLOC
78 int32 startStamp, endStamp;
79 saveLowTimeStampCountInto( startStamp );
80 #endif
81 //========================================================================
83 //step up the size to be aligned at 16-byte boundary, prob better ways
84 sizeRequested = (sizeRequested + 16) & ~15;
85 currElem = (_VMSMasterEnv->freeListHead[procrID])
86 ->nextChunkInFreeList;
88 while( currElem != NULL )
89 { //check if size of currElem is big enough
90 sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem);
91 amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
92 if( amountExtra > 0 )
93 { //found it, get out of loop
94 foundElem = currElem;
95 currElem = NULL;
96 }
97 else
98 currElem = currElem->nextChunkInFreeList;
99 }
101 if( foundElem == NULL )
102 { ERROR("\nmalloc failed\n")
103 return (void *)NULL; //indicates malloc failed
104 }
105 //Using a kludge to identify the element that is the top chunk in the
106 // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
107 // save addr of start of heap in head's nextLowerInMem
108 //Will handle top of Heap specially
109 foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
110 _VMSMasterEnv->freeListHead[procrID]->nextHigherInMem;
112 //before shave off and try to insert new elem, remove found elem
113 //note, foundElem will never be the head, so always has valid prevChunk
114 foundElem->prevChunkInFreeList->nextChunkInFreeList =
115 foundElem->nextChunkInFreeList;
116 if( foundElem->nextChunkInFreeList != NULL )
117 { foundElem->nextChunkInFreeList->prevChunkInFreeList =
118 foundElem->prevChunkInFreeList;
119 }
120 returnElem = (MallocPrologAllocated*)foundElem;
121 returnElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
122 returnElem->procrID = procrID;
124 //if enough, turn extra into new elem & insert it
125 if( amountExtra > 64 )
126 { //make new elem by adding to addr of curr elem then casting
127 sizeConsumed = sizeof(MallocProlog) + sizeRequested;
128 newElem = (MallocProlog *)( (uintptr_t)returnElem + sizeConsumed );
129 newElem->nextLowerInMem = (MallocProlog*)returnElem;
130 newElem->nextHigherInMem = returnElem->nextHigherInMem;
131 returnElem->nextHigherInMem = newElem;
132 if( ! foundElemIsTopOfHeap )
133 { //there is no next higher for top of heap, so can't write to it
134 newElem->nextHigherInMem->nextLowerInMem = newElem;
135 }
136 add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead[procrID] );
137 }
138 else
139 {
140 sizeConsumed = sizeOfFound;
141 }
142 _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
144 //============================= MEASUREMENT STUFF ========================
145 #ifdef MEAS__TIME_MALLOC
146 saveLowTimeStampCountInto( endStamp );
147 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
148 #endif
149 //========================================================================
151 //skip over the prolog by adding its size to the pointer return
152 return (void*)((uintptr_t)returnElem + sizeof(MallocProlog));
153 }
155 /*
156 * This free is called for a master loop. It decides whether the allocation of
157 * chunk was done on the same core. If it was it calls VMS__free_on_core
158 * otherwise it sends a message to the responsible core.
159 */
160 void
161 VMS__free(void *ptrToFree)
162 {
163 MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1;
164 if(chunk->procrID == _VMSMasterEnv->currentMasterProcrID)
165 {
166 VMS__free_on_core(ptrToFree, _VMSMasterEnv->currentMasterProcrID);
167 }
168 else
169 {
170 //Request from other Core
171 }
172 }
174 /*
175 * This free is called for the plugins. It decides whether the allocation of
176 * chunk was done on the same core. If it was it calls VMS__free_on_core
177 * otherwise it sends a message to the responsible core.
178 */
179 void
180 VMS__free_in_lib(void *ptrToFree, VirtProcr *VProc)
181 {
182 MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1;
183 printf("Free from core %d for core %d\n", VProc->coreAnimatedBy, chunk->procrID);
184 if(chunk->procrID == VProc->coreAnimatedBy)
185 {
186 VMS__free_on_core(ptrToFree, VProc->coreAnimatedBy);
187 }
188 else
189 {
190 //Request from other Core
191 }
192 }
194 /*This is sequential code -- only to be called from the Master
195 * When free, subtract the size of prolog from pointer, then cast it to a
196 * MallocProlog. Then check the nextLower and nextHigher chunks to see if
197 * one or both are also free, and coalesce if so, and if neither free, then
198 * add this one to free-list.
199 */
200 void
201 VMS__free_on_core( void *ptrToFree, int procrID)
202 { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem;
203 size_t sizeOfElem;
204 uint32 lowerExistsAndIsFree, higherExistsAndIsFree;
206 //============================= MEASUREMENT STUFF ========================
207 #ifdef MEAS__TIME_MALLOC
208 int32 startStamp, endStamp;
209 saveLowTimeStampCountInto( startStamp );
210 #endif
211 //========================================================================
213 MallocProlog* masterListHead = _VMSMasterEnv->freeListHead[procrID];
215 if( ptrToFree < (void*)masterListHead->nextLowerInMem ||
216 ptrToFree > (void*)masterListHead->nextHigherInMem )
217 { //outside the range of data owned by VMS's malloc, so do nothing
218 return;
219 }
220 //subtract size of prolog to get pointer to prolog, then cast
221 elemToFree = (MallocProlog *)((uintptr_t)ptrToFree - sizeof(MallocProlog));
222 sizeOfElem =(size_t)((uintptr_t)elemToFree->nextHigherInMem-(uintptr_t)elemToFree);
224 if( elemToFree->prevChunkInFreeList != NULL )
225 { printf( "error: freeing same element twice!" ); exit(1);
226 }
228 _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem;
230 nextLowerElem = elemToFree->nextLowerInMem;
231 nextHigherElem = elemToFree->nextHigherInMem;
233 if( nextHigherElem == NULL )
234 higherExistsAndIsFree = FALSE;
235 else //okay exists, now check if in the free-list by checking back ptr
236 higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL);
238 if( nextLowerElem == NULL )
239 lowerExistsAndIsFree = FALSE;
240 else //okay, it exists, now check if it's free
241 lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL);
244 //now, know what exists and what's free
245 if( lowerExistsAndIsFree )
246 { if( higherExistsAndIsFree )
247 { //both exist and are free, so coalesce all three
248 //First, remove higher from free-list
249 nextHigherElem->prevChunkInFreeList->nextChunkInFreeList =
250 nextHigherElem->nextChunkInFreeList;
251 if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list?
252 nextHigherElem->nextChunkInFreeList->prevChunkInFreeList =
253 nextHigherElem->prevChunkInFreeList;
254 //Now, fix-up sequence-in-mem list -- by side-effect, this also
255 // changes size of the lower elem, which is still in free-list
256 nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem;
257 if( nextHigherElem->nextHigherInMem !=
258 masterListHead->nextHigherInMem )
259 nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem;
260 //notice didn't do anything to elemToFree -- it simply is no
261 // longer reachable from any of the lists. Wonder if could be a
262 // security leak because left valid addresses in it,
263 // but don't care for now.
264 }
265 else
266 { //lower is the only of the two that exists and is free,
267 //In this case, no adjustment to free-list, just change mem-list.
268 // By side-effect, changes size of the lower elem
269 nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem;
270 if( elemToFree->nextHigherInMem !=
271 masterListHead->nextHigherInMem )
272 elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem;
273 }
274 }
275 else
276 { //lower either doesn't exist or isn't free, so check higher
277 if( higherExistsAndIsFree )
278 { //higher exists and is the only of the two free
279 //First, in free-list, replace higher elem with the one to free
280 elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList;
281 elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList;
282 elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree;
283 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
284 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
285 //Now chg mem-list. By side-effect, changes size of elemToFree
286 elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem;
287 if( elemToFree->nextHigherInMem !=
288 masterListHead->nextHigherInMem )
289 elemToFree->nextHigherInMem->nextLowerInMem = elemToFree;
290 }
291 else
292 { //neither lower nor higher is availabe to coalesce so add to list
293 // this makes prev chunk ptr non-null, which indicates it's free
294 elemToFree->nextChunkInFreeList =
295 masterListHead->nextChunkInFreeList;
296 masterListHead->nextChunkInFreeList = elemToFree;
297 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
298 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
299 elemToFree->prevChunkInFreeList = masterListHead;
300 }
301 }
302 //============================= MEASUREMENT STUFF ========================
303 #ifdef MEAS__TIME_MALLOC
304 saveLowTimeStampCountInto( endStamp );
305 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
306 #endif
307 //========================================================================
309 }
312 /*Allocates memory from the external system -- higher overhead
313 *
314 *Because of Linux's malloc throwing bizarre random faults when malloc is
315 * used inside a VMS virtual processor, have to pass this as a request and
316 * have the core loop do it when it gets around to it -- will look for these
317 * chores leftover from the previous animation of masterVP the next time it
318 * goes to animate the masterVP -- so it takes two separate masterVP
319 * animations, separated by work, to complete an external malloc or
320 * external free request.
321 *
322 *Thinking core loop accepts signals -- just looks if signal-location is
323 * empty or not --
324 */
325 void *
326 VMS__malloc_in_ext( size_t sizeRequested )
327 {
328 /*
329 //This is running in the master, so no chance for multiple cores to be
330 // competing for the core's flag.
331 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
332 { //something has already signalled to core loop, so save the signal
333 // and look, next time master animated, to see if can send it.
334 //Note, the addr to put a signal is in the coreloop's frame, so just
335 // checks it each time through -- make it volatile to avoid GCC
336 // optimizations -- it's a coreloop local var that only changes
337 // after jumping away. The signal includes the addr to send the
338 //return to -- even if just empty return completion-signal
339 //
340 //save the signal in some queue that the master looks at each time
341 // it starts up -- one loc says if empty for fast common case --
342 //something like that -- want to hide this inside this call -- but
343 // think this has to come as a request -- req handler gives procr
344 // back to master loop, which gives it back to req handler at point
345 // it sees that core loop has sent return signal. Something like
346 // that.
347 saveTheSignal
349 }
350 coreSigData->type = malloc;
351 coreSigData->sizeToMalloc = sizeRequested;
352 coreSigData->locToSignalCompletion = &figureOut;
353 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
354 */
355 //just risk system-stack faults until get this figured out
356 return malloc( sizeRequested );
357 }
360 /*Frees memory that was allocated in the external system -- higher overhead
361 *
362 *As noted in external malloc comment, this is clunky 'cause the free has
363 * to be called in the core loop.
364 */
365 void
366 VMS__free_in_ext( void *ptrToFree )
367 {
368 //just risk system-stack faults until get this figured out
369 free( ptrToFree );
371 //TODO: fix this -- so
372 }
375 /*Designed to be called from the main thread outside of VMS, during init
376 */
377 MallocProlog *
378 VMS_ext__create_free_list()
379 { MallocProlog *freeListHead, *firstChunk;
381 //Note, this is running in the main thread -- all increases in malloc
382 // mem and all frees of it must be done in this thread, with the
383 // thread's original stack available
385 freeListHead = malloc( sizeof(MallocProlog) );
386 firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
387 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
389 //Touch memory to avoid page faults
390 void *ptr,*endPtr;
391 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
392 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
393 {
394 *(char*)ptr = 0;
395 }
397 freeListHead->prevChunkInFreeList = NULL;
398 //Use this addr to free the heap when cleanup
399 freeListHead->nextLowerInMem = firstChunk;
400 //to identify top-of-heap elem, compare this addr to elem's next higher
401 freeListHead->nextHigherInMem = (void*)( (uintptr_t)firstChunk +
402 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
403 freeListHead->nextChunkInFreeList = firstChunk;
405 firstChunk->nextChunkInFreeList = NULL;
406 firstChunk->prevChunkInFreeList = freeListHead;
407 //next Higher has to be set to top of chunk, so can calc size in malloc
408 firstChunk->nextHigherInMem = (void*)( (uintptr_t)firstChunk +
409 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
410 firstChunk->nextLowerInMem = NULL; //identifies as bott of heap
412 _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet
414 return freeListHead;
415 }
418 /*Designed to be called from the main thread outside of VMS, during cleanup
419 */
420 void
421 VMS_ext__free_free_list( MallocProlog* freeListHeads[] )
422 {
423 //stashed a ptr to the one and only bug chunk malloc'd from OS in the
424 // free list head's next lower in mem pointer
425 int i;
426 for(i=0; i<NUM_CORES; i++)
427 {
428 free( freeListHeads[i]->nextLowerInMem );
429 }
430 //don't free the head -- it'll be in an array eventually -- free whole
431 // array when all the free lists linked from it have already been freed
432 }