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

annotate vmalloc.c @ 102:def70e32cf2c

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