Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl

annotate vmalloc.c @ 115:62c59f2ac9f1

find changesets by author, revision, files, or words in the commit message
first changes malloc
author Merten Sach <msach@mailbox.tu-berlin.de>
date Thu, 25 Aug 2011 16:32:13 +0200
parents def70e32cf2c
children 35547e66b971
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>
msach@101 14 #include <string.h>
msach@101 15 #include <math.h>
Me@50 16
Me@50 17 #include "VMS.h"
Me@68 18 #include "Histogram/Histogram.h"
Me@50 19
msach@115 20 #define MAX_UINT64 0xFFFFFFFFFFFFFFFF
msach@115 21
msach@102 22 //A MallocProlog is a head element if the HigherInMem variable is NULL
msach@102 23 //A Chunk is free if the prevChunkInFreeList variable is NULL
msach@102 24
msach@101 25 /*
msach@101 26 * This calculates the container which fits the given size.
Me@50 27 */
msach@101 28 inline
msach@101 29 uint32 getContainer(size_t size)
msach@101 30 {
msach@102 31 return (log10(size)-LOG128)/LOG54;
msach@101 32 }
msach@101 33
msach@101 34 /*
msach@101 35 * This calculates the size of a given container
msach@101 36 */
msach@101 37 inline
msach@101 38 size_t getContainerSize(uint32 idx)
msach@101 39 {
msach@101 40 return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND;
msach@101 41 }
msach@101 42
msach@101 43 /*
msach@101 44 * Removes the first chunk of a freeList
msach@101 45 * The chunk is removed but not set as free. There is no check if
msach@101 46 * the free list is empty, so make sure this is not the case.
msach@101 47 */
msach@101 48 inline
msach@101 49 MallocProlog *removeChunk(MallocProlog** container)
msach@101 50 {
msach@101 51 MallocProlog *removedChunk = *container;
msach@101 52 *container = removedChunk->nextChunkInFreeList;
msach@101 53
msach@101 54 if(removedChunk->nextChunkInFreeList)
msach@101 55 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
msach@101 56 (MallocProlog*)container;
msach@101 57
msach@101 58 return removedChunk;
msach@101 59 }
msach@101 60
msach@102 61 inline
msach@102 62 void recycleSmallChunks(MallocProlog** container)
msach@102 63 {
msach@102 64 //TODO recycle small chunks
msach@102 65 }
msach@102 66
msach@101 67 /*
msach@101 68 * Removes a chunk from a free list.
msach@101 69 */
msach@101 70 inline
msach@115 71 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
msach@101 72 {
msach@102 73 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
msach@102 74 if(chunk->nextChunkInFreeList)
msach@102 75 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
msach@115 76 if(*(chunk->prevChunkInFreeList) == NULL)
msach@115 77 {
msach@115 78 uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*);
msach@115 79 freeLists->bigChunksSearchVector &= ~(1 << containerIdx);
msach@115 80 }
msach@101 81 }
msach@101 82
msach@101 83 /*
msach@101 84 * Merges two chunks.
msach@102 85 * Chunk A has to be before chunk B in memory. Both have to be removed from
msach@102 86 * a free list
msach@101 87 */
msach@101 88 inline
msach@101 89 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
msach@101 90 {
msach@102 91 chunkA->nextHigherInMem = chunkB->nextHigherInMem;
msach@102 92 return chunkA;
msach@101 93 }
msach@101 94 /*
msach@101 95 * Inserts a chunk into a free list.
msach@101 96 */
msach@101 97 inline
msach@101 98 void insertChunk(MallocProlog* chunk, MallocProlog** container)
msach@101 99 {
msach@101 100 chunk->nextChunkInFreeList = *container;
msach@101 101 chunk->prevChunkInFreeList = (MallocProlog*)container;
msach@101 102 if(*container)
msach@101 103 (*container)->prevChunkInFreeList = chunk;
msach@101 104 *container = chunk;
msach@101 105 }
msach@101 106
msach@101 107 /*
msach@101 108 * Divides the chunk that a new chunk of newSize is created.
msach@101 109 * There is no size check, so make sure the size value is valid.
msach@101 110 */
msach@101 111 inline
msach@101 112 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
msach@101 113 {
msach@101 114 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
msach@101 115 newSize - sizeof(MallocProlog));
msach@101 116
msach@101 117 newChunk->nextLowerInMem = chunk;
msach@101 118 newChunk->nextHigherInMem = chunk->nextHigherInMem;
msach@101 119
msach@101 120 chunk->nextHigherInMem = newChunk;
msach@101 121 chunk->nextHigherInMem->nextLowerInMem = newChunk;
msach@101 122
msach@101 123 return newChunk;
msach@101 124 }
msach@101 125
msach@101 126 inline
msach@101 127 size_t getChunkSize(MallocProlog* chunk)
msach@101 128 {
msach@101 129 return (uintptr_t)chunk->nextHigherInMem -
msach@101 130 (uintptr_t)chunk - sizeof(MallocProlog);
msach@101 131 }
msach@101 132
msach@102 133
msach@102 134 /*
msach@102 135 * This makes 5 Chunks of the requested size.
msach@102 136 */
msach@102 137 inline
msach@102 138 void makeChunks(size_t size, MallocProlog **container)
msach@102 139 {
msach@102 140 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
msach@102 141 size_t addedSize = 5*(size + sizeof(MallocProlog));
msach@102 142
msach@102 143 uint32 containerIdx = getContainer(addedSize)+4;
msach@102 144 while(freeLists->bigChunks[containerIdx] == NULL )
msach@102 145 containerIdx++;
msach@102 146
msach@102 147 MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
msach@102 148
msach@102 149 int i;
msach@102 150 for(i=0; i<5; i++)
msach@102 151 {
msach@102 152 insertChunk(divideChunk(foundChunk,size), container);
msach@102 153 }
msach@102 154 containerIdx = getContainer(getChunkSize(foundChunk));
msach@102 155 insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
msach@102 156 }
msach@102 157
msach@101 158 /*
msach@101 159 * This is sequential code, meant to only be called from the Master, not from
msach@101 160 * any slave VPs.
msach@101 161 */
msach@101 162 void *VMS__malloc( size_t sizeRequested )
msach@101 163 {
msach@101 164 //============================= MEASUREMENT STUFF ========================
msach@101 165 #ifdef MEAS__TIME_MALLOC
msach@101 166 int32 startStamp, endStamp;
msach@101 167 saveLowTimeStampCountInto( startStamp );
msach@101 168 #endif
msach@101 169 //========================================================================
msach@101 170
msach@102 171
msach@115 172 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
msach@101 173
msach@101 174 //Return a small chunk if the requested size is smaller than 128B
msach@102 175 if(sizeRequested <= LOWER_BOUND)
msach@102 176 {
msach@102 177 uint32 freeListIdx = (sizeRequested-1)/32;
msach@115 178 if(freeLists->smallChunkCount[freeListIdx] == 0)
msach@102 179 {
msach@115 180 makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]);
msach@115 181 freeLists->smallChunkCount[freeListIdx] += 5;
msach@102 182 }
msach@102 183
msach@115 184 freeLists->smallChunkCount[freeListIdx]--;
msach@115 185 return removeChunk(&freeLists->smallChunks[freeListIdx]) + 1;
msach@102 186 }
msach@102 187
msach@101 188 //Calculate the expected container. Start one higher to have a Chunk that's
msach@101 189 //always big enough.
msach@101 190 uint32 targetContainerIdx = getContainer(sizeRequested);
msach@101 191 uint32 containerIdx = targetContainerIdx + 1;
msach@101 192
msach@101 193 MallocProlog* foundChunk;
msach@115 194 if(freeLists->bigChunks[containerIdx] == NULL)
msach@101 195 {
msach@115 196 uint64 searchVector = freeLists->bigChunksSearchVector;
msach@115 197 //set small chunk bits to zero
msach@115 198 searchVector &= MAX_UINT64 << containerIdx;
msach@115 199 containerIdx = __builtin_ffsl(searchVector);
msach@115 200
msach@115 201 if(containerIdx == 0)
msach@115 202 {
msach@115 203 printf("VMS malloc failed: low memory");
msach@115 204 exit(1);
msach@115 205 }
msach@115 206 /*
msach@101 207 while(freeList->bigChunks[containerIdx] == NULL)
msach@101 208 {
msach@101 209 containerIdx++;
msach@102 210 if(containerIdx >= freeList->containerCount)
msach@101 211 {
msach@101 212 printf("VMS malloc failed: low memory");
msach@101 213 exit(1);
msach@101 214 }
msach@115 215 }*/
msach@101 216
msach@115 217 foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
msach@101 218 size_t chunkSize = getChunkSize(foundChunk);
msach@101 219
msach@115 220 //If the new chunk is larger than the requested size: split
msach@115 221 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND)
msach@101 222 {
msach@102 223 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
msach@115 224 containerIdx = getContainer(getChunkSize(newChunk));
msach@115 225 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
msach@115 226 freeLists->bigChunksSearchVector |= 1 << containerIdx;
msach@102 227 foundChunk = newChunk;
msach@102 228 }
msach@101 229 }
msach@101 230 else
msach@101 231 {
msach@115 232 foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
msach@101 233 }
msach@101 234
msach@101 235 //Mark as allocated
msach@101 236 foundChunk->prevChunkInFreeList = NULL;
msach@101 237
msach@101 238 //============================= MEASUREMENT STUFF ========================
msach@101 239 #ifdef MEAS__TIME_MALLOC
msach@101 240 saveLowTimeStampCountInto( endStamp );
msach@101 241 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
msach@101 242 #endif
msach@101 243 //========================================================================
msach@102 244
msach@101 245 //skip over the prolog by adding its size to the pointer return
msach@102 246 return foundChunk + 1;
Me@50 247 }
Me@50 248
msach@101 249 /*
msach@101 250 * This is sequential code, meant to only be called from the Master, not from
Me@50 251 * any slave VPs.
Me@50 252 */
msach@101 253 void
msach@101 254 VMS__free( void *ptrToFree )
msach@101 255 {
Me@50 256
Me@65 257 //============================= MEASUREMENT STUFF ========================
Me@65 258 #ifdef MEAS__TIME_MALLOC
Me@65 259 int32 startStamp, endStamp;
Me@65 260 saveLowTimeStampCountInto( startStamp );
Me@65 261 #endif
Me@65 262 //========================================================================
Me@65 263
msach@102 264 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
msach@101 265 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
msach@102 266 uint32 containerIdx;
msach@102 267
msach@102 268 size_t chunkSize = getChunkSize(chunkToFree);
msach@102 269 if(chunkSize <= LOWER_BOUND)
msach@102 270 {
msach@102 271 containerIdx = (chunkSize-1)/32;
msach@102 272 insertChunk(chunkToFree,&freeLists->smallChunks[containerIdx]);
msach@102 273 freeLists->smallChunkCount[containerIdx]++;
msach@102 274
msach@102 275 if(freeLists->smallChunkCount[containerIdx] > 20)
msach@102 276 recycleSmallChunks(&freeLists->smallChunks[containerIdx]);
msach@102 277
msach@102 278 return;
msach@102 279 }
msach@101 280
msach@101 281 //Check for free neighbors
msach@101 282 if(chunkToFree->nextLowerInMem)
msach@101 283 {
msach@101 284 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
msach@101 285 {//Chunk is not allocated
msach@102 286 if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
msach@102 287 {
msach@102 288 extractChunk(chunkToFree->nextLowerInMem);
msach@102 289 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
msach@102 290 }
Me@50 291 }
msach@101 292 }
msach@102 293 if(chunkToFree->nextHigherInMem)
msach@102 294 {
msach@102 295 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
msach@102 296 {//Chunk is not allocated
msach@102 297 if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
msach@102 298 {
msach@102 299 extractChunk(chunkToFree->nextHigherInMem);
msach@102 300 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
msach@102 301 }
msach@102 302 }
msach@102 303 }
msach@102 304
msach@102 305 containerIdx = getContainer(chunkSize);
msach@102 306 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
msach@102 307
Me@65 308 //============================= MEASUREMENT STUFF ========================
Me@65 309 #ifdef MEAS__TIME_MALLOC
Me@65 310 saveLowTimeStampCountInto( endStamp );
Me@65 311 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
Me@65 312 #endif
Me@65 313 //========================================================================
Me@50 314
Me@50 315 }
Me@50 316
Me@50 317
Me@53 318 /*Allocates memory from the external system -- higher overhead
Me@53 319 *
Me@53 320 *Because of Linux's malloc throwing bizarre random faults when malloc is
Me@53 321 * used inside a VMS virtual processor, have to pass this as a request and
Me@53 322 * have the core loop do it when it gets around to it -- will look for these
Me@53 323 * chores leftover from the previous animation of masterVP the next time it
Me@53 324 * goes to animate the masterVP -- so it takes two separate masterVP
Me@53 325 * animations, separated by work, to complete an external malloc or
Me@53 326 * external free request.
Me@53 327 *
Me@53 328 *Thinking core loop accepts signals -- just looks if signal-location is
Me@53 329 * empty or not --
Me@53 330 */
Me@53 331 void *
msach@76 332 VMS__malloc_in_ext( size_t sizeRequested )
Me@53 333 {
Me@53 334 /*
Me@53 335 //This is running in the master, so no chance for multiple cores to be
Me@53 336 // competing for the core's flag.
Me@53 337 if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
Me@53 338 { //something has already signalled to core loop, so save the signal
Me@53 339 // and look, next time master animated, to see if can send it.
Me@53 340 //Note, the addr to put a signal is in the coreloop's frame, so just
Me@53 341 // checks it each time through -- make it volatile to avoid GCC
Me@53 342 // optimizations -- it's a coreloop local var that only changes
Me@53 343 // after jumping away. The signal includes the addr to send the
Me@53 344 //return to -- even if just empty return completion-signal
Me@53 345 //
Me@53 346 //save the signal in some queue that the master looks at each time
Me@53 347 // it starts up -- one loc says if empty for fast common case --
Me@53 348 //something like that -- want to hide this inside this call -- but
Me@53 349 // think this has to come as a request -- req handler gives procr
Me@53 350 // back to master loop, which gives it back to req handler at point
Me@53 351 // it sees that core loop has sent return signal. Something like
Me@53 352 // that.
Me@53 353 saveTheSignal
Me@53 354
Me@53 355 }
Me@53 356 coreSigData->type = malloc;
Me@53 357 coreSigData->sizeToMalloc = sizeRequested;
Me@53 358 coreSigData->locToSignalCompletion = &figureOut;
Me@53 359 _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
Me@53 360 */
Me@53 361 //just risk system-stack faults until get this figured out
Me@53 362 return malloc( sizeRequested );
Me@53 363 }
Me@53 364
Me@53 365
Me@53 366 /*Frees memory that was allocated in the external system -- higher overhead
Me@53 367 *
Me@53 368 *As noted in external malloc comment, this is clunky 'cause the free has
Me@53 369 * to be called in the core loop.
Me@53 370 */
Me@53 371 void
Me@53 372 VMS__free_in_ext( void *ptrToFree )
Me@53 373 {
Me@53 374 //just risk system-stack faults until get this figured out
Me@53 375 free( ptrToFree );
Me@53 376
Me@53 377 //TODO: fix this -- so
Me@53 378 }
Me@53 379
Me@53 380
Me@50 381 /*Designed to be called from the main thread outside of VMS, during init
Me@50 382 */
msach@101 383 MallocArrays *
Me@53 384 VMS_ext__create_free_list()
msach@101 385 {
msach@101 386 //Initialize containers for small chunks and fill with zeros
msach@101 387 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
msach@101 388 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
msach@101 389
msach@101 390 freeLists->smallChunks =
msach@101 391 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
msach@101 392 memset((void*)freeLists->smallChunks,
msach@101 393 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
msach@102 394 memset((void*)freeLists->smallChunkCount,
msach@102 395 0,SMALL_CHUNK_COUNT*sizeof(uint32));
msach@101 396
msach@101 397 //Calculate number of containers for big chunks
msach@101 398 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
msach@101 399 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
msach@101 400 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
msach@101 401 freeLists->containerCount = container;
msach@101 402
msach@101 403 //Create first element in lastContainer
msach@101 404 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
Me@50 405 if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
msach@102 406 freeLists->memSpace = firstChunk;
msach@79 407
msach@101 408 firstChunk->nextLowerInMem = NULL;
msach@101 409 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
msach@101 410 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));
msach@101 411 firstChunk->nextChunkInFreeList = NULL;
msach@101 412 //previous element in the queue is the container
msach@101 413 firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
Me@53 414
msach@101 415 freeLists->bigChunks[container-1] = firstChunk;
msach@115 416 //Insert into bit search list
msach@115 417 freeLists->bigChunksSearchVector |= (1 << (container-1));
msach@101 418
msach@101 419 //Create dummy chunk to mark the top of stack this is of course
msach@101 420 //never freed
msach@101 421 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
msach@101 422 dummyChunk->nextHigherInMem = dummyChunk+1;
msach@101 423 dummyChunk->nextLowerInMem = NULL;
msach@101 424 dummyChunk->nextChunkInFreeList = NULL;
msach@101 425 dummyChunk->prevChunkInFreeList = NULL;
msach@101 426
msach@101 427 return freeLists;
Me@50 428 }
Me@50 429
Me@50 430
Me@50 431 /*Designed to be called from the main thread outside of VMS, during cleanup
Me@50 432 */
Me@50 433 void
msach@102 434 VMS_ext__free_free_list( MallocArrays *freeLists )
Me@50 435 {
msach@102 436 free(freeLists->memSpace);
msach@102 437 free(freeLists->bigChunks);
msach@102 438 free(freeLists->smallChunks);
msach@102 439
Me@50 440 }
Me@50 441