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

annotate vmalloc.c @ 209:0c83ea8adefc

find changesets by author, revision, files, or words in the commit message
Close to compilable version of common_ancestor -- still includes HW dep stuff
author Some Random Person <seanhalle@yahoo.com>
date Sun, 04 Mar 2012 14:26:35 -0800
parents eaf7e4c58c9e
children a18539c0bc37
rev   line source
seanhalle@208 1 /*
seanhalle@208 2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org
seanhalle@208 3 * Licensed under GNU General Public License version 2
seanhalle@208 4 *
seanhalle@208 5 * Author: seanhalle@yahoo.com
seanhalle@208 6 *
seanhalle@208 7 * Created on November 14, 2009, 9:07 PM
seanhalle@208 8 */
seanhalle@208 9
seanhalle@208 10 #include <malloc.h>
seanhalle@208 11 #include <inttypes.h>
seanhalle@208 12 #include <stdlib.h>
seanhalle@208 13 #include <stdio.h>
seanhalle@209 14 #include <string.h>
seanhalle@209 15 #include <math.h>
seanhalle@208 16
seanhalle@208 17 #include "VMS.h"
seanhalle@208 18 #include "C_Libraries/Histogram/Histogram.h"
seanhalle@208 19
seanhalle@209 20 #define MAX_UINT64 0xFFFFFFFFFFFFFFFF
seanhalle@209 21
seanhalle@209 22 //A MallocProlog is a head element if the HigherInMem variable is NULL
seanhalle@209 23 //A Chunk is free if the prevChunkInFreeList variable is NULL
seanhalle@209 24
seanhalle@209 25 /*
seanhalle@209 26 * This calculates the container which fits the given size.
seanhalle@208 27 */
seanhalle@209 28 inline
seanhalle@209 29 uint32 getContainer(size_t size)
seanhalle@209 30 {
seanhalle@209 31 return (log2(size)-LOG128)/LOG54;
seanhalle@209 32 }
seanhalle@208 33
seanhalle@209 34 /*
seanhalle@209 35 * Removes the first chunk of a freeList
seanhalle@209 36 * The chunk is removed but not set as free. There is no check if
seanhalle@209 37 * the free list is empty, so make sure this is not the case.
seanhalle@209 38 */
seanhalle@209 39 inline
seanhalle@209 40 MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
seanhalle@209 41 {
seanhalle@209 42 MallocProlog** container = &freeLists->bigChunks[containerIdx];
seanhalle@209 43 MallocProlog* removedChunk = *container;
seanhalle@209 44 *container = removedChunk->nextChunkInFreeList;
seanhalle@209 45
seanhalle@209 46 if(removedChunk->nextChunkInFreeList)
seanhalle@209 47 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
seanhalle@209 48 (MallocProlog*)container;
seanhalle@209 49
seanhalle@209 50 if(*container == NULL)
seanhalle@209 51 {
seanhalle@209 52 if(containerIdx < 64)
seanhalle@209 53 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
seanhalle@209 54 else
seanhalle@209 55 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
seanhalle@209 56 }
seanhalle@209 57
seanhalle@209 58 return removedChunk;
seanhalle@209 59 }
seanhalle@208 60
seanhalle@209 61 /*
seanhalle@209 62 * Removes the first chunk of a freeList
seanhalle@209 63 * The chunk is removed but not set as free. There is no check if
seanhalle@209 64 * the free list is empty, so make sure this is not the case.
seanhalle@209 65 */
seanhalle@209 66 inline
seanhalle@209 67 MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)
seanhalle@209 68 {
seanhalle@209 69 MallocProlog** container = &freeLists->smallChunks[containerIdx];
seanhalle@209 70 MallocProlog* removedChunk = *container;
seanhalle@209 71 *container = removedChunk->nextChunkInFreeList;
seanhalle@209 72
seanhalle@209 73 if(removedChunk->nextChunkInFreeList)
seanhalle@209 74 removedChunk->nextChunkInFreeList->prevChunkInFreeList =
seanhalle@209 75 (MallocProlog*)container;
seanhalle@209 76
seanhalle@209 77 return removedChunk;
seanhalle@209 78 }
seanhalle@209 79
seanhalle@209 80 inline
seanhalle@209 81 size_t getChunkSize(MallocProlog* chunk)
seanhalle@209 82 {
seanhalle@209 83 return (uintptr_t)chunk->nextHigherInMem -
seanhalle@209 84 (uintptr_t)chunk - sizeof(MallocProlog);
seanhalle@209 85 }
seanhalle@209 86
seanhalle@209 87 /*
seanhalle@209 88 * Removes a chunk from a free list.
seanhalle@209 89 */
seanhalle@209 90 inline
seanhalle@209 91 void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
seanhalle@209 92 {
seanhalle@209 93 chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
seanhalle@209 94 if(chunk->nextChunkInFreeList)
seanhalle@209 95 chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
seanhalle@209 96
seanhalle@209 97 //The last element in the list points to the container. If the container points
seanhalle@209 98 //to NULL the container is empty
seanhalle@209 99 if(*((void**)(chunk->prevChunkInFreeList)) == NULL && getChunkSize(chunk) >= BIG_LOWER_BOUND)
seanhalle@209 100 {
seanhalle@209 101 //Find the approppiate container because we do not know it
seanhalle@209 102 uint64 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 3;
seanhalle@209 103 if(containerIdx < (uint32)64)
seanhalle@209 104 freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx);
seanhalle@209 105 if(containerIdx < 128 && containerIdx >=64)
seanhalle@209 106 freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
seanhalle@209 107
seanhalle@209 108 }
seanhalle@209 109 }
seanhalle@209 110
seanhalle@209 111 /*
seanhalle@209 112 * Merges two chunks.
seanhalle@209 113 * Chunk A has to be before chunk B in memory. Both have to be removed from
seanhalle@209 114 * a free list
seanhalle@209 115 */
seanhalle@209 116 inline
seanhalle@209 117 MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
seanhalle@209 118 {
seanhalle@209 119 chunkA->nextHigherInMem = chunkB->nextHigherInMem;
seanhalle@209 120 chunkB->nextHigherInMem->nextLowerInMem = chunkA;
seanhalle@209 121 return chunkA;
seanhalle@209 122 }
seanhalle@209 123 /*
seanhalle@209 124 * Inserts a chunk into a free list.
seanhalle@209 125 */
seanhalle@209 126 inline
seanhalle@209 127 void insertChunk(MallocProlog* chunk, MallocProlog** container)
seanhalle@209 128 {
seanhalle@209 129 chunk->nextChunkInFreeList = *container;
seanhalle@209 130 chunk->prevChunkInFreeList = (MallocProlog*)container;
seanhalle@209 131 if(*container)
seanhalle@209 132 (*container)->prevChunkInFreeList = chunk;
seanhalle@209 133 *container = chunk;
seanhalle@209 134 }
seanhalle@209 135
seanhalle@209 136 /*
seanhalle@209 137 * Divides the chunk that a new chunk of newSize is created.
seanhalle@209 138 * There is no size check, so make sure the size value is valid.
seanhalle@209 139 */
seanhalle@209 140 inline
seanhalle@209 141 MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
seanhalle@209 142 {
seanhalle@209 143 MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
seanhalle@209 144 newSize - sizeof(MallocProlog));
seanhalle@209 145
seanhalle@209 146 newChunk->nextLowerInMem = chunk;
seanhalle@209 147 newChunk->nextHigherInMem = chunk->nextHigherInMem;
seanhalle@209 148
seanhalle@209 149 chunk->nextHigherInMem->nextLowerInMem = newChunk;
seanhalle@209 150 chunk->nextHigherInMem = newChunk;
seanhalle@209 151
seanhalle@209 152 return newChunk;
seanhalle@209 153 }
seanhalle@209 154
seanhalle@209 155 /*
seanhalle@209 156 * Search for chunk in the list of big chunks. Split the block if it's too big
seanhalle@209 157 */
seanhalle@209 158 inline
seanhalle@209 159 MallocProlog *searchChunk(MallocArrays *freeLists, size_t sizeRequested, uint32 containerIdx)
seanhalle@209 160 {
seanhalle@209 161 MallocProlog* foundChunk;
seanhalle@209 162
seanhalle@209 163 uint64 searchVector = freeLists->bigChunksSearchVector[0];
seanhalle@209 164 //set small chunk bits to zero
seanhalle@209 165 searchVector &= MAX_UINT64 << containerIdx;
seanhalle@209 166 containerIdx = __builtin_ffsl(searchVector);
seanhalle@209 167
seanhalle@209 168 if(containerIdx == 0)
seanhalle@209 169 {
seanhalle@209 170 searchVector = freeLists->bigChunksSearchVector[1];
seanhalle@209 171 containerIdx = __builtin_ffsl(searchVector);
seanhalle@209 172 if(containerIdx == 0)
seanhalle@209 173 {
seanhalle@209 174 printf("VMS malloc failed: low memory");
seanhalle@209 175 exit(1);
seanhalle@209 176 }
seanhalle@209 177 containerIdx += 64;
seanhalle@209 178 }
seanhalle@209 179 containerIdx--;
seanhalle@209 180
seanhalle@209 181
seanhalle@209 182 foundChunk = removeChunk(freeLists, containerIdx);
seanhalle@209 183 size_t chunkSize = getChunkSize(foundChunk);
seanhalle@209 184
seanhalle@209 185 //If the new chunk is larger than the requested size: split
seanhalle@209 186 if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + BIG_LOWER_BOUND)
seanhalle@209 187 {
seanhalle@209 188 MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
seanhalle@209 189 containerIdx = getContainer(getChunkSize(foundChunk)) - 1;
seanhalle@209 190 insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
seanhalle@209 191 if(containerIdx < 64)
seanhalle@209 192 freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
seanhalle@209 193 else
seanhalle@209 194 freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
seanhalle@209 195 foundChunk = newChunk;
seanhalle@209 196 }
seanhalle@209 197
seanhalle@209 198 return foundChunk;
seanhalle@209 199 }
seanhalle@209 200
seanhalle@209 201
seanhalle@209 202 /*
seanhalle@209 203 * This is sequential code, meant to only be called from the Master, not from
seanhalle@209 204 * any slave Slvs.
seanhalle@208 205 */
seanhalle@208 206 void *VMS_int__malloc( size_t sizeRequested )
seanhalle@209 207 {
seanhalle@208 208 //============================= MEASUREMENT STUFF ========================
seanhalle@208 209 #ifdef MEAS__TIME_MALLOC
seanhalle@208 210 int32 startStamp, endStamp;
seanhalle@208 211 saveLowTimeStampCountInto( startStamp );
seanhalle@208 212 #endif
seanhalle@208 213 //========================================================================
seanhalle@208 214
seanhalle@209 215 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
seanhalle@209 216 MallocProlog* foundChunk;
seanhalle@208 217
seanhalle@209 218 //Return a small chunk if the requested size is smaller than 128B
seanhalle@209 219 if(sizeRequested <= LOWER_BOUND)
seanhalle@209 220 {
seanhalle@209 221 uint32 freeListIdx = (sizeRequested-1)/SMALL_CHUNK_SIZE;
seanhalle@209 222 if(freeLists->smallChunks[freeListIdx] == NULL)
seanhalle@209 223 foundChunk = searchChunk(freeLists, SMALL_CHUNK_SIZE*(freeListIdx+1), 0);
seanhalle@209 224 else
seanhalle@209 225 foundChunk = removeSmallChunk(freeLists, freeListIdx);
seanhalle@209 226
seanhalle@209 227 //Mark as allocated
seanhalle@209 228 foundChunk->prevChunkInFreeList = NULL;
seanhalle@209 229 return foundChunk + 1;
seanhalle@209 230 }
seanhalle@208 231
seanhalle@209 232 //Calculate the expected container. Start one higher to have a Chunk that's
seanhalle@209 233 //always big enough.
seanhalle@209 234 uint32 containerIdx = getContainer(sizeRequested);
seanhalle@208 235
seanhalle@209 236 if(freeLists->bigChunks[containerIdx] == NULL)
seanhalle@209 237 foundChunk = searchChunk(freeLists, sizeRequested, containerIdx);
seanhalle@208 238 else
seanhalle@209 239 foundChunk = removeChunk(freeLists, containerIdx);
seanhalle@209 240
seanhalle@209 241 //Mark as allocated
seanhalle@209 242 foundChunk->prevChunkInFreeList = NULL;
seanhalle@209 243
seanhalle@208 244 //============================= MEASUREMENT STUFF ========================
seanhalle@208 245 #ifdef MEAS__TIME_MALLOC
seanhalle@208 246 saveLowTimeStampCountInto( endStamp );
seanhalle@208 247 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
seanhalle@208 248 #endif
seanhalle@208 249 //========================================================================
seanhalle@209 250
seanhalle@209 251 //skip over the prolog by adding its size to the pointer return
seanhalle@209 252 return foundChunk + 1;
seanhalle@208 253 }
seanhalle@208 254
seanhalle@209 255 /*
seanhalle@209 256 * This is sequential code, meant to only be called from the Master, not from
seanhalle@209 257 * any slave Slvs.
seanhalle@208 258 */
seanhalle@208 259 void
seanhalle@208 260 VMS_int__free( void *ptrToFree )
seanhalle@209 261 {
seanhalle@209 262
seanhalle@208 263 //============================= MEASUREMENT STUFF ========================
seanhalle@208 264 #ifdef MEAS__TIME_MALLOC
seanhalle@208 265 int32 startStamp, endStamp;
seanhalle@208 266 saveLowTimeStampCountInto( startStamp );
seanhalle@208 267 #endif
seanhalle@208 268 //========================================================================
seanhalle@209 269
seanhalle@209 270 MallocArrays* freeLists = _VMSMasterEnv->freeLists;
seanhalle@209 271 MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
seanhalle@209 272 uint32 containerIdx;
seanhalle@209 273
seanhalle@209 274 //Check for free neighbors
seanhalle@209 275 if(chunkToFree->nextLowerInMem)
seanhalle@209 276 {
seanhalle@209 277 if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
seanhalle@209 278 {//Chunk is not allocated
seanhalle@209 279 extractChunk(chunkToFree->nextLowerInMem, freeLists);
seanhalle@209 280 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
seanhalle@208 281 }
seanhalle@209 282 }
seanhalle@209 283 if(chunkToFree->nextHigherInMem)
seanhalle@209 284 {
seanhalle@209 285 if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
seanhalle@209 286 {//Chunk is not allocated
seanhalle@209 287 extractChunk(chunkToFree->nextHigherInMem, freeLists);
seanhalle@209 288 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
seanhalle@208 289 }
seanhalle@209 290 }
seanhalle@209 291
seanhalle@209 292 size_t chunkSize = getChunkSize(chunkToFree);
seanhalle@209 293 if(chunkSize < BIG_LOWER_BOUND)
seanhalle@209 294 {
seanhalle@209 295 containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1;
seanhalle@209 296 if(containerIdx > SMALL_CHUNK_COUNT-1)
seanhalle@209 297 containerIdx = SMALL_CHUNK_COUNT-1;
seanhalle@209 298 insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]);
seanhalle@209 299 }
seanhalle@208 300 else
seanhalle@209 301 {
seanhalle@209 302 containerIdx = getContainer(getChunkSize(chunkToFree)) - 1;
seanhalle@209 303 insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
seanhalle@209 304 if(containerIdx < 64)
seanhalle@209 305 freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
seanhalle@209 306 else
seanhalle@209 307 freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
seanhalle@209 308 }
seanhalle@209 309
seanhalle@208 310 //============================= MEASUREMENT STUFF ========================
seanhalle@208 311 #ifdef MEAS__TIME_MALLOC
seanhalle@208 312 saveLowTimeStampCountInto( endStamp );
seanhalle@208 313 addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist );
seanhalle@208 314 #endif
seanhalle@208 315 //========================================================================
seanhalle@208 316
seanhalle@208 317 }
seanhalle@208 318
seanhalle@209 319 /*
seanhalle@209 320 * Designed to be called from the main thread outside of VMS, during init
seanhalle@208 321 */
seanhalle@209 322 MallocArrays *
seanhalle@208 323 VMS_ext__create_free_list()
seanhalle@209 324 {
seanhalle@209 325 //Initialize containers for small chunks and fill with zeros
seanhalle@209 326 _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
seanhalle@209 327 MallocArrays *freeLists = _VMSMasterEnv->freeLists;
seanhalle@209 328
seanhalle@209 329 freeLists->smallChunks =
seanhalle@209 330 (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
seanhalle@209 331 memset((void*)freeLists->smallChunks,
seanhalle@209 332 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
seanhalle@209 333
seanhalle@209 334 //Calculate number of containers for big chunks
seanhalle@209 335 uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
seanhalle@209 336 freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
seanhalle@209 337 memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
seanhalle@209 338 freeLists->containerCount = container;
seanhalle@209 339
seanhalle@209 340 //Create first element in lastContainer
seanhalle@209 341 MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
seanhalle@209 342 if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);}
seanhalle@209 343 freeLists->memSpace = firstChunk;
seanhalle@208 344
seanhalle@208 345 //Touch memory to avoid page faults
seanhalle@208 346 void *ptr,*endPtr;
seanhalle@208 347 endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
seanhalle@208 348 for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
seanhalle@208 349 {
seanhalle@208 350 *(char*)ptr = 0;
seanhalle@208 351 }
seanhalle@208 352
seanhalle@209 353 firstChunk->nextLowerInMem = NULL;
seanhalle@209 354 firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
seanhalle@209 355 MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog));
seanhalle@209 356 firstChunk->nextChunkInFreeList = NULL;
seanhalle@209 357 //previous element in the queue is the container
seanhalle@209 358 firstChunk->prevChunkInFreeList = &freeLists->bigChunks[container-2];
seanhalle@209 359
seanhalle@209 360 freeLists->bigChunks[container-2] = firstChunk;
seanhalle@209 361 //Insert into bit search list
seanhalle@209 362 if(container <= 65)
seanhalle@209 363 {
seanhalle@209 364 freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2));
seanhalle@209 365 freeLists->bigChunksSearchVector[1] = 0;
seanhalle@209 366 }
seanhalle@209 367 else
seanhalle@209 368 {
seanhalle@209 369 freeLists->bigChunksSearchVector[0] = 0;
seanhalle@209 370 freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66));
seanhalle@209 371 }
seanhalle@209 372
seanhalle@209 373 //Create dummy chunk to mark the top of stack this is of course
seanhalle@209 374 //never freed
seanhalle@209 375 MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
seanhalle@209 376 dummyChunk->nextHigherInMem = dummyChunk+1;
seanhalle@209 377 dummyChunk->nextLowerInMem = NULL;
seanhalle@209 378 dummyChunk->nextChunkInFreeList = NULL;
seanhalle@209 379 dummyChunk->prevChunkInFreeList = NULL;
seanhalle@209 380
seanhalle@209 381 return freeLists;
seanhalle@208 382 }
seanhalle@208 383
seanhalle@208 384
seanhalle@208 385 /*Designed to be called from the main thread outside of VMS, during cleanup
seanhalle@208 386 */
seanhalle@208 387 void
seanhalle@209 388 VMS_ext__free_free_list( MallocArrays *freeLists )
seanhalle@208 389 {
seanhalle@209 390 free(freeLists->memSpace);
seanhalle@209 391 free(freeLists->bigChunks);
seanhalle@209 392 free(freeLists->smallChunks);
seanhalle@209 393
seanhalle@208 394 }
seanhalle@208 395