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