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

annotate vmalloc.c @ 101:ca154ebe2b6c

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