Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
view vmalloc.c @ 208:eaf7e4c58c9e
Create common_ancestor brch -- all branches will be closed, then new ones
created with this as the common ancestor of all branches -- it is incomplete!
only code that is common to all HW and Feat and FeatDev branches is in here
| author | Some Random Person <seanhalle@yahoo.com> |
|---|---|
| date | Wed, 22 Feb 2012 11:39:12 -0800 |
| parents | |
| children | 0c83ea8adefc |
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 "C_Libraries/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 }
41 /*This is sequential code, meant to only be called from the Master, not from
42 * any slave VPs.
43 *Search down list, checking size by the nextHigherInMem pointer, to find
44 * first chunk bigger than size needed.
45 *Shave off the extra and make it into a new free-list element, hook it in
46 * then return the address of the found element plus size of prolog.
47 *
48 */
49 void *VMS_int__malloc( size_t sizeRequested )
50 { MallocProlog *foundElem = NULL, *currElem, *newElem;
51 ssize_t amountExtra, sizeConsumed,sizeOfFound;
52 uint32 foundElemIsTopOfHeap;
54 //============================= MEASUREMENT STUFF ========================
55 #ifdef MEAS__TIME_MALLOC
56 int32 startStamp, endStamp;
57 saveLowTimeStampCountInto( startStamp );
58 #endif
59 //========================================================================
61 //step up the size to be aligned at 16-byte boundary, prob better ways
62 sizeRequested = (sizeRequested + 16) & ~15;
63 currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
65 while( currElem != NULL )
66 { //check if size of currElem is big enough
67 sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem);
68 amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
69 if( amountExtra > 0 )
70 { //found it, get out of loop
71 foundElem = currElem;
72 currElem = NULL;
73 }
74 else
75 currElem = currElem->nextChunkInFreeList;
76 }
78 if( foundElem == NULL )
79 { ERROR("\nmalloc failed\n")
80 return (void *)NULL; //indicates malloc failed
81 }
82 //Using a kludge to identify the element that is the top chunk in the
83 // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
84 // save addr of start of heap in head's nextLowerInMem
85 //Will handle top of Heap specially
86 foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
87 _VMSMasterEnv->freeListHead->nextHigherInMem;
89 //before shave off and try to insert new elem, remove found elem
90 //note, foundElem will never be the head, so always has valid prevChunk
91 foundElem->prevChunkInFreeList->nextChunkInFreeList =
92 foundElem->nextChunkInFreeList;
93 if( foundElem->nextChunkInFreeList != NULL )
94 { foundElem->nextChunkInFreeList->prevChunkInFreeList =
95 foundElem->prevChunkInFreeList;
96 }
97 foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
99 //if enough, turn extra into new elem & insert it
100 if( amountExtra > 64 )
101 { //make new elem by adding to addr of curr elem then casting
102 sizeConsumed = sizeof(MallocProlog) + sizeRequested;
103 newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed );
104 newElem->nextLowerInMem = foundElem; //This is evil (but why?)
105 newElem->nextHigherInMem = foundElem->nextHigherInMem; //This is evil (but why?)
106 foundElem->nextHigherInMem = newElem;
107 if( ! foundElemIsTopOfHeap )
108 { //there is no next higher for top of heap, so can't write to it
109 newElem->nextHigherInMem->nextLowerInMem = newElem;
110 }
111 add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
112 }
113 else
114 {
115 sizeConsumed = sizeOfFound;
116 }
117 _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
119 //============================= MEASUREMENT STUFF ========================
120 #ifdef MEAS__TIME_MALLOC
121 saveLowTimeStampCountInto( endStamp );
122 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
123 #endif
124 //========================================================================
126 //skip over the prolog by adding its size to the pointer return
127 return (void*)((uintptr_t)foundElem + sizeof(MallocProlog));
128 }
130 /*This is sequential code, meant to only be called from the Master, not from
131 * any slave VPs.
132 *Search down list, checking size by the nextHigherInMem pointer, to find
133 * first chunk bigger than size needed.
134 *Shave off the extra and make it into a new free-list element, hook it in
135 * then return the address of the found element plus size of prolog.
136 *
137 * The difference to the regular malloc is, that all the allocated chunks are
138 * aligned and padded to the size of a CACHE_LINE_SZ. Thus creating a new chunk
139 * before the aligned chunk.
140 */
141 void *VMS_int__malloc_aligned( size_t sizeRequested )
142 { MallocProlog *foundElem = NULL, *currElem, *newElem;
143 ssize_t amountExtra, sizeConsumed,sizeOfFound,prevAmount;
144 uint32 foundElemIsTopOfHeap;
146 //============================= MEASUREMENT STUFF ========================
147 #ifdef MEAS__TIME_MALLOC
148 uint32 startStamp, endStamp;
149 saveLowTimeStampCountInto( startStamp );
150 #endif
151 //========================================================================
153 //step up the size to be multiple of the cache line size
154 sizeRequested = (sizeRequested + CACHE_LINE_SZ) & ~(CACHE_LINE_SZ-1);
155 currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
157 while( currElem != NULL )
158 { //check if size of currElem is big enough
159 sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem);
160 amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
161 if( amountExtra > 0 )
162 {
163 //look if the found element is already aligned
164 if((((uintptr_t)currElem+sizeof(MallocProlog)) & (uintptr_t)(CACHE_LINE_SZ-1)) == 0){
165 //found it, get out of loop
166 foundElem = currElem;
167 break;
168 }else{
169 //find first aligned address and check if it's still big enough
170 //check also if the space before the aligned address is big enough
171 //for a new element
172 void *firstAlignedAddr = (void*)(((uintptr_t)currElem + 2*CACHE_LINE_SZ) & ~((uintptr_t)(CACHE_LINE_SZ-1)));
173 prevAmount = (uintptr_t)firstAlignedAddr - (uintptr_t)currElem;
174 sizeOfFound=(uintptr_t)currElem->nextHigherInMem -(uintptr_t)firstAlignedAddr + sizeof(MallocProlog);
175 amountExtra= sizeOfFound - sizeRequested - sizeof(MallocProlog);
176 if(prevAmount > 2*sizeof(MallocProlog) && amountExtra > 0 ){
177 //found suitable element
178 //create new previous element and exit loop
179 MallocProlog *newAlignedElem = (MallocProlog*)firstAlignedAddr - 1;
181 //insert new element into free list
182 if(currElem->nextChunkInFreeList != NULL)
183 currElem->nextChunkInFreeList->prevChunkInFreeList = newAlignedElem;
184 newAlignedElem->prevChunkInFreeList = currElem;
185 newAlignedElem->nextChunkInFreeList = currElem->nextChunkInFreeList;
186 currElem->nextChunkInFreeList = newAlignedElem;
188 //set higherInMem and lowerInMem
189 newAlignedElem->nextHigherInMem = currElem->nextHigherInMem;
190 foundElemIsTopOfHeap = currElem->nextHigherInMem ==
191 _VMSMasterEnv->freeListHead->nextHigherInMem;
192 if(!foundElemIsTopOfHeap)
193 currElem->nextHigherInMem->nextLowerInMem = newAlignedElem;
194 currElem->nextHigherInMem = newAlignedElem;
195 newAlignedElem->nextLowerInMem = currElem;
197 //Found new element leaving loop
198 foundElem = newAlignedElem;
199 break;
200 }
201 }
203 }
204 currElem = currElem->nextChunkInFreeList;
205 }
207 if( foundElem == NULL )
208 { ERROR("\nmalloc failed\n")
209 return (void *)NULL; //indicates malloc failed
210 }
211 //Using a kludge to identify the element that is the top chunk in the
212 // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
213 // save addr of start of heap in head's nextLowerInMem
214 //Will handle top of Heap specially
215 foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
216 _VMSMasterEnv->freeListHead->nextHigherInMem;
218 //before shave off and try to insert new elem, remove found elem
219 //note, foundElem will never be the head, so always has valid prevChunk
220 foundElem->prevChunkInFreeList->nextChunkInFreeList =
221 foundElem->nextChunkInFreeList;
222 if( foundElem->nextChunkInFreeList != NULL )
223 { foundElem->nextChunkInFreeList->prevChunkInFreeList =
224 foundElem->prevChunkInFreeList;
225 }
226 foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
228 //if enough, turn extra into new elem & insert it
229 if( amountExtra > 64 )
230 { //make new elem by adding to addr of curr elem then casting
231 sizeConsumed = sizeof(MallocProlog) + sizeRequested;
232 newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed );
233 newElem->nextHigherInMem = foundElem->nextHigherInMem;
234 newElem->nextLowerInMem = foundElem;
235 foundElem->nextHigherInMem = newElem;
237 if( ! foundElemIsTopOfHeap )
238 { //there is no next higher for top of heap, so can't write to it
239 newElem->nextHigherInMem->nextLowerInMem = newElem;
240 }
241 add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
242 }
243 else
244 {
245 sizeConsumed = sizeOfFound;
246 }
247 _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
249 //============================= MEASUREMENT STUFF ========================
250 #ifdef MEAS__TIME_MALLOC
251 saveLowTimeStampCountInto( endStamp );
252 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
253 #endif
254 //========================================================================
256 //skip over the prolog by adding its size to the pointer return
257 return (void*)((uintptr_t)foundElem + sizeof(MallocProlog));
258 }
261 /*This is sequential code -- only to be called from the Master
262 * When free, subtract the size of prolog from pointer, then cast it to a
263 * MallocProlog. Then check the nextLower and nextHigher chunks to see if
264 * one or both are also free, and coalesce if so, and if neither free, then
265 * add this one to free-list.
266 */
267 void
268 VMS_int__free( void *ptrToFree )
269 { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem;
270 size_t sizeOfElem;
271 uint32 lowerExistsAndIsFree, higherExistsAndIsFree;
273 //============================= MEASUREMENT STUFF ========================
274 #ifdef MEAS__TIME_MALLOC
275 int32 startStamp, endStamp;
276 saveLowTimeStampCountInto( startStamp );
277 #endif
278 //========================================================================
280 if( ptrToFree < (void*)_VMSMasterEnv->freeListHead->nextLowerInMem ||
281 ptrToFree > (void*)_VMSMasterEnv->freeListHead->nextHigherInMem )
282 { //outside the range of data owned by VMS's malloc, so do nothing
283 return;
284 }
285 //subtract size of prolog to get pointer to prolog, then cast
286 elemToFree = (MallocProlog *)((uintptr_t)ptrToFree - sizeof(MallocProlog));
287 sizeOfElem =(size_t)((uintptr_t)elemToFree->nextHigherInMem-(uintptr_t)elemToFree);
289 if( elemToFree->prevChunkInFreeList != NULL )
290 { printf( "error: freeing same element twice!" ); exit(1);
291 }
293 _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem;
295 nextLowerElem = elemToFree->nextLowerInMem;
296 nextHigherElem = elemToFree->nextHigherInMem;
298 if( nextHigherElem == NULL )
299 higherExistsAndIsFree = FALSE;
300 else //okay exists, now check if in the free-list by checking back ptr
301 higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL);
303 if( nextLowerElem == NULL )
304 lowerExistsAndIsFree = FALSE;
305 else //okay, it exists, now check if it's free
306 lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL);
309 //now, know what exists and what's free
310 if( lowerExistsAndIsFree )
311 { if( higherExistsAndIsFree )
312 { //both exist and are free, so coalesce all three
313 //First, remove higher from free-list
314 nextHigherElem->prevChunkInFreeList->nextChunkInFreeList =
315 nextHigherElem->nextChunkInFreeList;
316 if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list?
317 nextHigherElem->nextChunkInFreeList->prevChunkInFreeList =
318 nextHigherElem->prevChunkInFreeList;
319 //Now, fix-up sequence-in-mem list -- by side-effect, this also
320 // changes size of the lower elem, which is still in free-list
321 nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem;
322 if( nextHigherElem->nextHigherInMem !=
323 _VMSMasterEnv->freeListHead->nextHigherInMem )
324 nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem;
325 //notice didn't do anything to elemToFree -- it simply is no
326 // longer reachable from any of the lists. Wonder if could be a
327 // security leak because left valid addresses in it,
328 // but don't care for now.
329 }
330 else
331 { //lower is the only of the two that exists and is free,
332 //In this case, no adjustment to free-list, just change mem-list.
333 // By side-effect, changes size of the lower elem
334 nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem;
335 if( elemToFree->nextHigherInMem !=
336 _VMSMasterEnv->freeListHead->nextHigherInMem )
337 elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem;
338 }
339 }
340 else
341 { //lower either doesn't exist or isn't free, so check higher
342 if( higherExistsAndIsFree )
343 { //higher exists and is the only of the two free
344 //First, in free-list, replace higher elem with the one to free
345 elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList;
346 elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList;
347 elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree;
348 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
349 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
350 //Now chg mem-list. By side-effect, changes size of elemToFree
351 elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem;
352 if( elemToFree->nextHigherInMem !=
353 _VMSMasterEnv->freeListHead->nextHigherInMem )
354 elemToFree->nextHigherInMem->nextLowerInMem = elemToFree;
355 }
356 else
357 { //neither lower nor higher is availabe to coalesce so add to list
358 // this makes prev chunk ptr non-null, which indicates it's free
359 elemToFree->nextChunkInFreeList =
360 _VMSMasterEnv->freeListHead->nextChunkInFreeList;
361 _VMSMasterEnv->freeListHead->nextChunkInFreeList = elemToFree;
362 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
363 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
364 elemToFree->prevChunkInFreeList = _VMSMasterEnv->freeListHead;
365 }
366 }
367 //============================= MEASUREMENT STUFF ========================
368 #ifdef MEAS__TIME_MALLOC
369 saveLowTimeStampCountInto( endStamp );
370 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
371 #endif
372 //========================================================================
374 }
377 /*Allocates memory from the external system -- higher overhead
378 *
379 *Because of Linux's malloc throwing bizarre random faults when malloc is
380 * used inside a VMS virtual processor, have to pass this as a request and
381 * have the core loop do it when it gets around to it -- will look for these
382 * chores leftover from the previous animation of masterVP the next time it
383 * goes to animate the masterVP -- so it takes two separate masterVP
384 * animations, separated by work, to complete an external malloc or
385 * external free request.
386 *
387 *Thinking core loop accepts signals -- just looks if signal-location is
388 * empty or not --
389 */
390 void *
391 VMS__malloc_in_ext( size_t sizeRequested )
392 {
393 /*
394 //This is running in the master, so no chance for multiple cores to be
395 // competing for the core's flag.
396 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
397 { //something has already signalled to core loop, so save the signal
398 // and look, next time master animated, to see if can send it.
399 //Note, the addr to put a signal is in the coreloop's frame, so just
400 // checks it each time through -- make it volatile to avoid GCC
401 // optimizations -- it's a coreloop local var that only changes
402 // after jumping away. The signal includes the addr to send the
403 //return to -- even if just empty return completion-signal
404 //
405 //save the signal in some queue that the master looks at each time
406 // it starts up -- one loc says if empty for fast common case --
407 //something like that -- want to hide this inside this call -- but
408 // think this has to come as a request -- req handler gives procr
409 // back to master loop, which gives it back to req handler at point
410 // it sees that core loop has sent return signal. Something like
411 // that.
412 saveTheSignal
414 }
415 coreSigData->type = malloc;
416 coreSigData->sizeToMalloc = sizeRequested;
417 coreSigData->locToSignalCompletion = &figureOut;
418 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
419 */
420 //just risk system-stack faults until get this figured out
421 return malloc( sizeRequested );
422 }
425 /*Frees memory that was allocated in the external system -- higher overhead
426 *
427 *As noted in external malloc comment, this is clunky 'cause the free has
428 * to be called in the core loop.
429 */
430 void
431 VMS__free_in_ext( void *ptrToFree )
432 {
433 //just risk system-stack faults until get this figured out
434 free( ptrToFree );
436 //TODO: fix this -- so
437 }
440 /*Designed to be called from the main thread outside of VMS, during init
441 */
442 MallocProlog *
443 VMS_ext__create_free_list()
444 { MallocProlog *freeListHead, *firstChunk;
446 //Note, this is running in the main thread -- all increases in malloc
447 // mem and all frees of it must be done in this thread, with the
448 // thread's original stack available
449 freeListHead = malloc( sizeof(MallocProlog) );
450 firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
451 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
453 //Touch memory to avoid page faults
454 void *ptr,*endPtr;
455 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
456 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
457 {
458 *(char*)ptr = 0;
459 }
461 freeListHead->prevChunkInFreeList = NULL;
462 //Use this addr to free the heap when cleanup
463 freeListHead->nextLowerInMem = firstChunk;
464 //to identify top-of-heap elem, compare this addr to elem's next higher
465 freeListHead->nextHigherInMem = (void*)( (uintptr_t)firstChunk +
466 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
467 freeListHead->nextChunkInFreeList = firstChunk;
469 firstChunk->nextChunkInFreeList = NULL;
470 firstChunk->prevChunkInFreeList = freeListHead;
471 //next Higher has to be set to top of chunk, so can calc size in malloc
472 firstChunk->nextHigherInMem = (void*)( (uintptr_t)firstChunk +
473 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
474 firstChunk->nextLowerInMem = NULL; //identifies as bott of heap
476 _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet
478 return freeListHead;
479 }
482 /*Designed to be called from the main thread outside of VMS, during cleanup
483 */
484 void
485 VMS_ext__free_free_list( MallocProlog *freeListHead )
486 {
487 //stashed a ptr to the one and only bug chunk malloc'd from OS in the
488 // free list head's next lower in mem pointer
489 free( freeListHead->nextLowerInMem );
491 //don't free the head -- it'll be in an array eventually -- free whole
492 // array when all the free lists linked from it have already been freed
493 }