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

annotate vmalloc.c @ 116:35547e66b971

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