annotate vmalloc.c @ 76:9ddbb071142d

make hardware independent and port to 64bit
author Merten Sach <msach@mailbox.tu-berlin.de>
date Thu, 16 Jun 2011 14:41:15 +0200
parents 9c3107044f86
children 521c75d64cef
rev   line source
Me@50 1 /*
Me@50 2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org
Me@50 3 * Licensed under GNU General Public License version 2
Me@50 4 *
Me@50 5 * Author: seanhalle@yahoo.com
Me@50 6 *
Me@50 7 * Created on November 14, 2009, 9:07 PM
Me@50 8 */
Me@50 9
Me@50 10 #include <malloc.h>
msach@76 11 #include <inttypes.h>
Me@53 12 #include <stdlib.h>
msach@76 13 #include <stdio.h>
Me@50 14
Me@50 15 #include "VMS.h"
Me@68 16 #include "Histogram/Histogram.h"
Me@50 17
Me@50 18 /*Helper function
Me@50 19 *Insert a newly generated free chunk into the first spot on the free list.
Me@50 20 * The chunk is cast as a MallocProlog, so the various pointers in it are
Me@50 21 * accessed with C's help -- and the size of the prolog is easily added to
Me@50 22 * the pointer when a chunk is returned to the app -- so C handles changes
Me@50 23 * in pointer sizes among machines.
Me@50 24 *
Me@50 25 *The list head is a normal MallocProlog struct -- identified by its
Me@50 26 * prevChunkInFreeList being NULL -- the only one.
Me@50 27 *
Me@50 28 *The end of the list is identified by next chunk being NULL, as usual.
Me@50 29 */
Me@50 30 void inline
Me@50 31 add_chunk_to_free_list( MallocProlog *chunk, MallocProlog *listHead )
Me@50 32 {
Me@50 33 chunk->nextChunkInFreeList = listHead->nextChunkInFreeList;
Me@50 34 if( chunk->nextChunkInFreeList != NULL ) //if not last in free list
Me@50 35 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk;
Me@50 36 chunk->prevChunkInFreeList = listHead;
Me@50 37 listHead->nextChunkInFreeList = chunk;
Me@50 38 }
Me@50 39
Me@50 40
Me@50 41 /*This is sequential code, meant to only be called from the Master, not from
Me@50 42 * any slave VPs.
Me@50 43 *Search down list, checking size by the nextHigherInMem pointer, to find
Me@50 44 * first chunk bigger than size needed.
Me@50 45 *Shave off the extra and make it into a new free-list element, hook it in
Me@50 46 * then return the address of the found element plus size of prolog.
Me@50 47 *
Me@50 48 *Will find a
Me@50 49 */
msach@76 50 void *VMS__malloc( size_t sizeRequested )
Me@50 51 { MallocProlog *foundElem = NULL, *currElem, *newElem;
msach@76 52 ssize_t amountExtra, sizeConsumed,sizeOfFound;
msach@76 53 uint32 foundElemIsTopOfHeap;
Me@50 54
Me@65 55 //============================= MEASUREMENT STUFF ========================
Me@65 56 #ifdef MEAS__TIME_MALLOC
Me@65 57 int32 startStamp, endStamp;
Me@65 58 saveLowTimeStampCountInto( startStamp );
Me@65 59 #endif
Me@65 60 //========================================================================
Me@65 61
Me@50 62 //step up the size to be aligned at 16-byte boundary, prob better ways
Me@50 63 sizeRequested = ((sizeRequested + 16) >> 4) << 4;
Me@50 64 currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
Me@50 65
Me@50 66 while( currElem != NULL )
Me@50 67 { //check if size of currElem is big enough
msach@76 68 sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem);
Me@50 69 amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
Me@50 70 if( amountExtra > 0 )
Me@50 71 { //found it, get out of loop
Me@50 72 foundElem = currElem;
Me@50 73 currElem = NULL;
Me@50 74 }
Me@50 75 else
Me@50 76 currElem = currElem->nextChunkInFreeList;
Me@50 77 }
Me@50 78
Me@50 79 if( foundElem == NULL )
Me@55 80 { ERROR("\nmalloc failed\n")
Me@60 81 return (void *)NULL; //indicates malloc failed
Me@50 82 }
Me@50 83 //Using a kludge to identify the element that is the top chunk in the
Me@50 84 // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
Me@50 85 // save addr of start of heap in head's nextLowerInMem
Me@50 86 //Will handle top of Heap specially
Me@50 87 foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
Me@50 88 _VMSMasterEnv->freeListHead->nextHigherInMem;
Me@50 89
Me@50 90 //before shave off and try to insert new elem, remove found elem
Me@50 91 //note, foundElem will never be the head, so always has valid prevChunk
Me@50 92 foundElem->prevChunkInFreeList->nextChunkInFreeList =
Me@50 93 foundElem->nextChunkInFreeList;
Me@50 94 if( foundElem->nextChunkInFreeList != NULL )
Me@50 95 { foundElem->nextChunkInFreeList->prevChunkInFreeList =
Me@50 96 foundElem->prevChunkInFreeList;
Me@50 97 }
Me@50 98 foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
Me@50 99
Me@50 100 //if enough, turn extra into new elem & insert it
Me@50 101 if( amountExtra > 64 )
Me@50 102 { //make new elem by adding to addr of curr elem then casting
Me@50 103 sizeConsumed = sizeof(MallocProlog) + sizeRequested;
msach@76 104 newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed );
Me@50 105 newElem->nextHigherInMem = foundElem->nextHigherInMem;
Me@50 106 newElem->nextLowerInMem = foundElem;
Me@50 107 foundElem->nextHigherInMem = newElem;
Me@50 108
Me@50 109 if( ! foundElemIsTopOfHeap )
Me@50 110 { //there is no next higher for top of heap, so can't write to it
Me@50 111 newElem->nextHigherInMem->nextLowerInMem = newElem;
Me@50 112 }
Me@50 113 add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
Me@50 114 }
Me@50 115 else
Me@50 116 {
Me@50 117 sizeConsumed = sizeOfFound;
Me@50 118 }
Me@50 119 _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
Me@50 120
Me@65 121 //============================= MEASUREMENT STUFF ========================
Me@65 122 #ifdef MEAS__TIME_MALLOC
Me@65 123 saveLowTimeStampCountInto( endStamp );
Me@65 124 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
Me@65 125 #endif
Me@65 126 //========================================================================
Me@65 127
Me@50 128 //skip over the prolog by adding its size to the pointer return
msach@76 129 return (void*)((uintptr_t)foundElem + sizeof(MallocProlog));
Me@50 130 }
Me@50 131
Me@50 132
Me@50 133 /*This is sequential code -- only to be called from the Master
Me@50 134 * When free, subtract the size of prolog from pointer, then cast it to a
Me@50 135 * MallocProlog. Then check the nextLower and nextHigher chunks to see if
Me@50 136 * one or both are also free, and coalesce if so, and if neither free, then
Me@50 137 * add this one to free-list.
Me@50 138 */
Me@50 139 void
Me@50 140 VMS__free( void *ptrToFree )
Me@50 141 { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem;
msach@76 142 size_t sizeOfElem;
msach@76 143 uint32 lowerExistsAndIsFree, higherExistsAndIsFree;
Me@50 144
Me@65 145 //============================= MEASUREMENT STUFF ========================
Me@65 146 #ifdef MEAS__TIME_MALLOC
Me@65 147 int32 startStamp, endStamp;
Me@65 148 saveLowTimeStampCountInto( startStamp );
Me@65 149 #endif
Me@65 150 //========================================================================
Me@65 151
Me@53 152 if( ptrToFree < (void*)_VMSMasterEnv->freeListHead->nextLowerInMem ||
Me@53 153 ptrToFree > (void*)_VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50 154 { //outside the range of data owned by VMS's malloc, so do nothing
Me@50 155 return;
Me@50 156 }
Me@50 157 //subtract size of prolog to get pointer to prolog, then cast
msach@76 158 elemToFree = (MallocProlog *)((uintptr_t)ptrToFree - sizeof(MallocProlog));
msach@76 159 sizeOfElem =(size_t)((uintptr_t)elemToFree->nextHigherInMem-(uintptr_t)elemToFree);
Me@53 160
Me@53 161 if( elemToFree->prevChunkInFreeList != NULL )
Me@53 162 { printf( "error: freeing same element twice!" ); exit(1);
Me@53 163 }
Me@53 164
Me@50 165 _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem;
Me@50 166
Me@50 167 nextLowerElem = elemToFree->nextLowerInMem;
Me@50 168 nextHigherElem = elemToFree->nextHigherInMem;
Me@50 169
Me@50 170 if( nextHigherElem == NULL )
Me@50 171 higherExistsAndIsFree = FALSE;
Me@50 172 else //okay exists, now check if in the free-list by checking back ptr
Me@50 173 higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL);
Me@50 174
Me@50 175 if( nextLowerElem == NULL )
Me@50 176 lowerExistsAndIsFree = FALSE;
Me@50 177 else //okay, it exists, now check if it's free
Me@50 178 lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL);
Me@50 179
Me@50 180
Me@50 181 //now, know what exists and what's free
Me@50 182 if( lowerExistsAndIsFree )
Me@50 183 { if( higherExistsAndIsFree )
Me@50 184 { //both exist and are free, so coalesce all three
Me@50 185 //First, remove higher from free-list
Me@50 186 nextHigherElem->prevChunkInFreeList->nextChunkInFreeList =
Me@50 187 nextHigherElem->nextChunkInFreeList;
Me@50 188 if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list?
Me@50 189 nextHigherElem->nextChunkInFreeList->prevChunkInFreeList =
Me@50 190 nextHigherElem->prevChunkInFreeList;
Me@50 191 //Now, fix-up sequence-in-mem list -- by side-effect, this also
Me@50 192 // changes size of the lower elem, which is still in free-list
Me@50 193 nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem;
Me@50 194 if( nextHigherElem->nextHigherInMem !=
Me@50 195 _VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50 196 nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem;
Me@50 197 //notice didn't do anything to elemToFree -- it simply is no
Me@50 198 // longer reachable from any of the lists. Wonder if could be a
Me@50 199 // security leak because left valid addresses in it,
Me@50 200 // but don't care for now.
Me@50 201 }
Me@50 202 else
Me@50 203 { //lower is the only of the two that exists and is free,
Me@50 204 //In this case, no adjustment to free-list, just change mem-list.
Me@50 205 // By side-effect, changes size of the lower elem
Me@50 206 nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem;
Me@50 207 if( elemToFree->nextHigherInMem !=
Me@50 208 _VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50 209 elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem;
Me@50 210 }
Me@50 211 }
Me@50 212 else
Me@50 213 { //lower either doesn't exist or isn't free, so check higher
Me@50 214 if( higherExistsAndIsFree )
Me@50 215 { //higher exists and is the only of the two free
Me@50 216 //First, in free-list, replace higher elem with the one to free
Me@50 217 elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList;
Me@50 218 elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList;
Me@50 219 elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree;
Me@50 220 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
Me@50 221 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
Me@50 222 //Now chg mem-list. By side-effect, changes size of elemToFree
Me@50 223 elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem;
Me@50 224 if( elemToFree->nextHigherInMem !=
Me@50 225 _VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50 226 elemToFree->nextHigherInMem->nextLowerInMem = elemToFree;
Me@50 227 }
Me@50 228 else
Me@50 229 { //neither lower nor higher is availabe to coalesce so add to list
Me@50 230 // this makes prev chunk ptr non-null, which indicates it's free
Me@50 231 elemToFree->nextChunkInFreeList =
Me@50 232 _VMSMasterEnv->freeListHead->nextChunkInFreeList;
Me@50 233 _VMSMasterEnv->freeListHead->nextChunkInFreeList = elemToFree;
Me@50 234 if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
Me@50 235 elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
Me@50 236 elemToFree->prevChunkInFreeList = _VMSMasterEnv->freeListHead;
Me@50 237 }
Me@50 238 }
Me@65 239 //============================= MEASUREMENT STUFF ========================
Me@65 240 #ifdef MEAS__TIME_MALLOC
Me@65 241 saveLowTimeStampCountInto( endStamp );
Me@65 242 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
Me@65 243 #endif
Me@65 244 //========================================================================
Me@50 245
Me@50 246 }
Me@50 247
Me@50 248
Me@53 249 /*Allocates memory from the external system -- higher overhead
Me@53 250 *
Me@53 251 *Because of Linux's malloc throwing bizarre random faults when malloc is
Me@53 252 * used inside a VMS virtual processor, have to pass this as a request and
Me@53 253 * have the core loop do it when it gets around to it -- will look for these
Me@53 254 * chores leftover from the previous animation of masterVP the next time it
Me@53 255 * goes to animate the masterVP -- so it takes two separate masterVP
Me@53 256 * animations, separated by work, to complete an external malloc or
Me@53 257 * external free request.
Me@53 258 *
Me@53 259 *Thinking core loop accepts signals -- just looks if signal-location is
Me@53 260 * empty or not --
Me@53 261 */
Me@53 262 void *
msach@76 263 VMS__malloc_in_ext( size_t sizeRequested )
Me@53 264 {
Me@53 265 /*
Me@53 266 //This is running in the master, so no chance for multiple cores to be
Me@53 267 // competing for the core's flag.
Me@53 268 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
Me@53 269 { //something has already signalled to core loop, so save the signal
Me@53 270 // and look, next time master animated, to see if can send it.
Me@53 271 //Note, the addr to put a signal is in the coreloop's frame, so just
Me@53 272 // checks it each time through -- make it volatile to avoid GCC
Me@53 273 // optimizations -- it's a coreloop local var that only changes
Me@53 274 // after jumping away. The signal includes the addr to send the
Me@53 275 //return to -- even if just empty return completion-signal
Me@53 276 //
Me@53 277 //save the signal in some queue that the master looks at each time
Me@53 278 // it starts up -- one loc says if empty for fast common case --
Me@53 279 //something like that -- want to hide this inside this call -- but
Me@53 280 // think this has to come as a request -- req handler gives procr
Me@53 281 // back to master loop, which gives it back to req handler at point
Me@53 282 // it sees that core loop has sent return signal. Something like
Me@53 283 // that.
Me@53 284 saveTheSignal
Me@53 285
Me@53 286 }
Me@53 287 coreSigData->type = malloc;
Me@53 288 coreSigData->sizeToMalloc = sizeRequested;
Me@53 289 coreSigData->locToSignalCompletion = &figureOut;
Me@53 290 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
Me@53 291 */
Me@53 292 //just risk system-stack faults until get this figured out
Me@53 293 return malloc( sizeRequested );
Me@53 294 }
Me@53 295
Me@53 296
Me@53 297 /*Frees memory that was allocated in the external system -- higher overhead
Me@53 298 *
Me@53 299 *As noted in external malloc comment, this is clunky 'cause the free has
Me@53 300 * to be called in the core loop.
Me@53 301 */
Me@53 302 void
Me@53 303 VMS__free_in_ext( void *ptrToFree )
Me@53 304 {
Me@53 305 //just risk system-stack faults until get this figured out
Me@53 306 free( ptrToFree );
Me@53 307
Me@53 308 //TODO: fix this -- so
Me@53 309 }
Me@53 310
Me@53 311
Me@50 312 /*Designed to be called from the main thread outside of VMS, during init
Me@50 313 */
Me@50 314 MallocProlog *
Me@53 315 VMS_ext__create_free_list()
Me@50 316 { MallocProlog *freeListHead, *firstChunk;
Me@50 317
Me@50 318 //Note, this is running in the main thread -- all increases in malloc
Me@50 319 // mem and all frees of it must be done in this thread, with the
Me@50 320 // thread's original stack available
Me@50 321 freeListHead = malloc( sizeof(MallocProlog) );
Me@50 322 firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
Me@50 323 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
Me@50 324
Me@50 325 freeListHead->prevChunkInFreeList = NULL;
Me@50 326 //Use this addr to free the heap when cleanup
Me@50 327 freeListHead->nextLowerInMem = firstChunk;
Me@50 328 //to identify top-of-heap elem, compare this addr to elem's next higher
msach@76 329 freeListHead->nextHigherInMem = (void*)( (uintptr_t)firstChunk +
Me@53 330 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
Me@50 331 freeListHead->nextChunkInFreeList = firstChunk;
Me@50 332
Me@50 333 firstChunk->nextChunkInFreeList = NULL;
Me@50 334 firstChunk->prevChunkInFreeList = freeListHead;
Me@50 335 //next Higher has to be set to top of chunk, so can calc size in malloc
msach@76 336 firstChunk->nextHigherInMem = (void*)( (uintptr_t)firstChunk +
Me@53 337 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
Me@50 338 firstChunk->nextLowerInMem = NULL; //identifies as bott of heap
Me@53 339
Me@53 340 _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet
Me@50 341
Me@50 342 return freeListHead;
Me@50 343 }
Me@50 344
Me@50 345
Me@50 346 /*Designed to be called from the main thread outside of VMS, during cleanup
Me@50 347 */
Me@50 348 void
Me@50 349 VMS_ext__free_free_list( MallocProlog *freeListHead )
Me@50 350 {
Me@50 351 //stashed a ptr to the one and only bug chunk malloc'd from OS in the
Me@50 352 // free list head's next lower in mem pointer
Me@50 353 free( freeListHead->nextLowerInMem );
Me@50 354
Me@50 355 //don't free the head -- it'll be in an array eventually -- free whole
Me@50 356 // array when all the free lists linked from it have already been freed
Me@50 357 }
Me@50 358