seanhalle@208: /*
seanhalle@208:  *  Copyright 2009 OpenSourceCodeStewardshipFoundation.org
seanhalle@208:  *  Licensed under GNU General Public License version 2
seanhalle@208:  *
seanhalle@208:  * Author: seanhalle@yahoo.com
seanhalle@208:  *
seanhalle@208:  * Created on November 14, 2009, 9:07 PM
seanhalle@208:  */
seanhalle@208: 
seanhalle@208: #include <malloc.h>
seanhalle@208: #include <inttypes.h>
seanhalle@208: #include <stdlib.h>
seanhalle@208: #include <stdio.h>
seanhalle@209: #include <string.h>
seanhalle@209: #include <math.h>
seanhalle@208: 
seanhalle@208: #include "VMS.h"
seanhalle@222: #include "Histogram/Histogram.h"
seanhalle@208: 
seanhalle@209: #define MAX_UINT64 0xFFFFFFFFFFFFFFFF
seanhalle@209: 
seanhalle@209: //A MallocProlog is a head element if the HigherInMem variable is NULL
seanhalle@209: //A Chunk is free if the prevChunkInFreeList variable is NULL
seanhalle@209: 
seanhalle@209: /*
seanhalle@209:  * This calculates the container which fits the given size.
seanhalle@208:  */
seanhalle@209: inline
seanhalle@209: uint32 getContainer(size_t size)
seanhalle@209: {
seanhalle@209:     return (log2(size)-LOG128)/LOG54;
seanhalle@209: }
seanhalle@208: 
seanhalle@209: /*
seanhalle@209:  * Removes the first chunk of a freeList
seanhalle@209:  * The chunk is removed but not set as free. There is no check if
seanhalle@209:  * the free list is empty, so make sure this is not the case.
seanhalle@209:  */
seanhalle@209: inline
seanhalle@209: MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
seanhalle@209: {
seanhalle@209:     MallocProlog** container = &freeLists->bigChunks[containerIdx];
seanhalle@209:     MallocProlog*  removedChunk = *container;
seanhalle@209:     *container = removedChunk->nextChunkInFreeList;
seanhalle@209:     
seanhalle@209:     if(removedChunk->nextChunkInFreeList)
seanhalle@209:         removedChunk->nextChunkInFreeList->prevChunkInFreeList = 
seanhalle@209:                 (MallocProlog*)container;
seanhalle@209:     
seanhalle@209:     if(*container == NULL)
seanhalle@209:     {
seanhalle@209:        if(containerIdx < 64)
seanhalle@209:            freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); 
seanhalle@209:        else
seanhalle@209:            freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
seanhalle@209:     }
seanhalle@209:     
seanhalle@209:     return removedChunk;
seanhalle@209: }
seanhalle@208: 
seanhalle@209: /*
seanhalle@209:  * Removes the first chunk of a freeList
seanhalle@209:  * The chunk is removed but not set as free. There is no check if
seanhalle@209:  * the free list is empty, so make sure this is not the case.
seanhalle@209:  */
seanhalle@209: inline
seanhalle@209: MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)
seanhalle@209: {
seanhalle@209:     MallocProlog** container = &freeLists->smallChunks[containerIdx];
seanhalle@209:     MallocProlog*  removedChunk = *container;
seanhalle@209:     *container = removedChunk->nextChunkInFreeList;
seanhalle@209:     
seanhalle@209:     if(removedChunk->nextChunkInFreeList)
seanhalle@209:         removedChunk->nextChunkInFreeList->prevChunkInFreeList = 
seanhalle@209:                 (MallocProlog*)container;
seanhalle@209:     
seanhalle@209:     return removedChunk;
seanhalle@209: }
seanhalle@209: 
seanhalle@209: inline
seanhalle@209: size_t getChunkSize(MallocProlog* chunk)
seanhalle@209: {
seanhalle@209:     return (uintptr_t)chunk->nextHigherInMem -
seanhalle@209:             (uintptr_t)chunk - sizeof(MallocProlog);
seanhalle@209: }
seanhalle@209: 
seanhalle@209: /*
seanhalle@209:  * Removes a chunk from a free list.
seanhalle@209:  */
seanhalle@209: inline
seanhalle@209: void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
seanhalle@209: {
seanhalle@209:    chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
seanhalle@209:    if(chunk->nextChunkInFreeList)
seanhalle@209:        chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
seanhalle@209:    
seanhalle@209:    //The last element in the list points to the container. If the container points
seanhalle@209:    //to NULL the container is empty
seanhalle@209:    if(*((void**)(chunk->prevChunkInFreeList)) == NULL && getChunkSize(chunk) >= BIG_LOWER_BOUND)
seanhalle@209:    {
seanhalle@209:        //Find the approppiate container because we do not know it
seanhalle@209:        uint64 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 3;
seanhalle@209:        if(containerIdx < (uint32)64)
seanhalle@209:            freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); 
seanhalle@209:        if(containerIdx < 128 && containerIdx >=64)
seanhalle@209:            freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64)); 
seanhalle@209:        
seanhalle@209:    }
seanhalle@209: }
seanhalle@209: 
seanhalle@209: /*
seanhalle@209:  * Merges two chunks.
seanhalle@209:  * Chunk A has to be before chunk B in memory. Both have to be removed from
seanhalle@209:  * a free list
seanhalle@209:  */
seanhalle@209: inline
seanhalle@209: MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
seanhalle@209: {
seanhalle@209:     chunkA->nextHigherInMem = chunkB->nextHigherInMem;
seanhalle@209:     chunkB->nextHigherInMem->nextLowerInMem = chunkA;
seanhalle@209:     return chunkA;
seanhalle@209: }
seanhalle@209: /*
seanhalle@209:  * Inserts a chunk into a free list.
seanhalle@209:  */
seanhalle@209: inline
seanhalle@209: void insertChunk(MallocProlog* chunk, MallocProlog** container)
seanhalle@209: {
seanhalle@209:     chunk->nextChunkInFreeList = *container;
seanhalle@209:     chunk->prevChunkInFreeList = (MallocProlog*)container;
seanhalle@209:     if(*container)
seanhalle@209:         (*container)->prevChunkInFreeList = chunk;
seanhalle@209:     *container = chunk;
seanhalle@209: }
seanhalle@209: 
seanhalle@209: /*
seanhalle@209:  * Divides the chunk that a new chunk of newSize is created.
seanhalle@209:  * There is no size check, so make sure the size value is valid.
seanhalle@209:  */
seanhalle@209: inline
seanhalle@209: MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
seanhalle@209: {
seanhalle@209:     MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
seanhalle@209:             newSize - sizeof(MallocProlog));
seanhalle@209:     
seanhalle@209:     newChunk->nextLowerInMem  = chunk;
seanhalle@209:     newChunk->nextHigherInMem = chunk->nextHigherInMem;
seanhalle@209:     
seanhalle@209:     chunk->nextHigherInMem->nextLowerInMem = newChunk;
seanhalle@209:     chunk->nextHigherInMem = newChunk;
seanhalle@209:     
seanhalle@209:     return newChunk;
seanhalle@209: }
seanhalle@209: 
seanhalle@209: /* 
seanhalle@209:  * Search for chunk in the list of big chunks. Split the block if it's too big
seanhalle@209:  */
seanhalle@209: inline
seanhalle@209: MallocProlog *searchChunk(MallocArrays *freeLists, size_t sizeRequested, uint32 containerIdx)
seanhalle@209: {
seanhalle@209:     MallocProlog* foundChunk;
seanhalle@209:     
seanhalle@209:     uint64 searchVector = freeLists->bigChunksSearchVector[0];
seanhalle@209:     //set small chunk bits to zero
seanhalle@209:     searchVector &= MAX_UINT64 << containerIdx;
seanhalle@209:     containerIdx = __builtin_ffsl(searchVector);
seanhalle@209: 
seanhalle@209:     if(containerIdx == 0)
seanhalle@209:     {
seanhalle@209:        searchVector = freeLists->bigChunksSearchVector[1];
seanhalle@209:        containerIdx = __builtin_ffsl(searchVector);
seanhalle@209:        if(containerIdx == 0)
seanhalle@209:        {
seanhalle@209:            printf("VMS malloc failed: low memory");
seanhalle@209:            exit(1);   
seanhalle@209:        }
seanhalle@209:        containerIdx += 64;
seanhalle@209:     }
seanhalle@209:     containerIdx--;
seanhalle@209:     
seanhalle@209: 
seanhalle@209:     foundChunk = removeChunk(freeLists, containerIdx);
seanhalle@209:     size_t chunkSize     = getChunkSize(foundChunk);
seanhalle@209: 
seanhalle@209:     //If the new chunk is larger than the requested size: split
seanhalle@209:     if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + BIG_LOWER_BOUND)
seanhalle@209:     {
seanhalle@209:        MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
seanhalle@209:        containerIdx = getContainer(getChunkSize(foundChunk)) - 1;
seanhalle@209:        insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
seanhalle@209:        if(containerIdx < 64)
seanhalle@209:            freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
seanhalle@209:        else
seanhalle@209:            freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
seanhalle@209:        foundChunk = newChunk;
seanhalle@209:     } 
seanhalle@209:     
seanhalle@209:     return foundChunk;
seanhalle@209: }
seanhalle@209: 
seanhalle@209: 
seanhalle@209: /*
seanhalle@209:  * This is sequential code, meant to only be called from the Master, not from
seanhalle@209:  * any slave Slvs.
seanhalle@208:  */
seanhalle@208: void *VMS_int__malloc( size_t sizeRequested )
seanhalle@209:  {     
seanhalle@208:    //============================= MEASUREMENT STUFF ========================
seanhalle@208:    #ifdef MEAS__TIME_MALLOC
seanhalle@208:    int32 startStamp, endStamp;
seanhalle@208:    saveLowTimeStampCountInto( startStamp );
seanhalle@208:    #endif
seanhalle@208:    //========================================================================
seanhalle@208:    
seanhalle@209:    MallocArrays* freeLists = _VMSMasterEnv->freeLists;
seanhalle@209:    MallocProlog* foundChunk;
seanhalle@208:    
seanhalle@209:    //Return a small chunk if the requested size is smaller than 128B
seanhalle@209:    if(sizeRequested <= LOWER_BOUND)
seanhalle@209:    {
seanhalle@209:        uint32 freeListIdx = (sizeRequested-1)/SMALL_CHUNK_SIZE;
seanhalle@209:        if(freeLists->smallChunks[freeListIdx] == NULL)
seanhalle@209:            foundChunk = searchChunk(freeLists, SMALL_CHUNK_SIZE*(freeListIdx+1), 0);
seanhalle@209:        else
seanhalle@209:            foundChunk = removeSmallChunk(freeLists, freeListIdx);
seanhalle@209:        
seanhalle@209:        //Mark as allocated
seanhalle@209:        foundChunk->prevChunkInFreeList = NULL;      
seanhalle@209:        return foundChunk + 1;
seanhalle@209:    }
seanhalle@208:    
seanhalle@209:    //Calculate the expected container. Start one higher to have a Chunk that's
seanhalle@209:    //always big enough.
seanhalle@209:    uint32 containerIdx = getContainer(sizeRequested);
seanhalle@208:    
seanhalle@209:    if(freeLists->bigChunks[containerIdx] == NULL)
seanhalle@209:        foundChunk = searchChunk(freeLists, sizeRequested, containerIdx); 
seanhalle@208:    else
seanhalle@209:        foundChunk = removeChunk(freeLists, containerIdx); 
seanhalle@209:    
seanhalle@209:    //Mark as allocated
seanhalle@209:    foundChunk->prevChunkInFreeList = NULL;      
seanhalle@209:    
seanhalle@208:    //============================= MEASUREMENT STUFF ========================
seanhalle@208:    #ifdef MEAS__TIME_MALLOC
seanhalle@208:    saveLowTimeStampCountInto( endStamp );
seanhalle@208:    addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
seanhalle@208:    #endif
seanhalle@208:    //========================================================================
seanhalle@209:    
seanhalle@209:    //skip over the prolog by adding its size to the pointer return
seanhalle@209:    return foundChunk + 1;
seanhalle@208:  }
seanhalle@208: 
seanhalle@209: /*
seanhalle@209:  * This is sequential code, meant to only be called from the Master, not from
seanhalle@209:  * any slave Slvs.
seanhalle@208:  */
seanhalle@208: void
seanhalle@208: VMS_int__free( void *ptrToFree )
seanhalle@209:  {
seanhalle@209:     
seanhalle@210:          MEAS__Capture_Pre_Free_Point;
seanhalle@210:          
seanhalle@209:    MallocArrays* freeLists = _VMSMasterEnv->freeLists;
seanhalle@209:    MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
seanhalle@209:    uint32 containerIdx;
seanhalle@209:    
seanhalle@209:    //Check for free neighbors
seanhalle@209:    if(chunkToFree->nextLowerInMem)
seanhalle@209:    {
seanhalle@209:        if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
seanhalle@209:        {//Chunk is not allocated
seanhalle@209:            extractChunk(chunkToFree->nextLowerInMem, freeLists);
seanhalle@209:            chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
seanhalle@208:        }
seanhalle@209:    }
seanhalle@209:    if(chunkToFree->nextHigherInMem)
seanhalle@209:    {
seanhalle@209:        if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
seanhalle@209:        {//Chunk is not allocated
seanhalle@209:            extractChunk(chunkToFree->nextHigherInMem, freeLists);
seanhalle@209:            chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
seanhalle@208:        }
seanhalle@209:    }
seanhalle@209:    
seanhalle@209:    size_t chunkSize = getChunkSize(chunkToFree);
seanhalle@209:    if(chunkSize < BIG_LOWER_BOUND)
seanhalle@209:    {
seanhalle@209:        containerIdx =  (chunkSize/SMALL_CHUNK_SIZE)-1;
seanhalle@209:        if(containerIdx > SMALL_CHUNK_COUNT-1)
seanhalle@209:            containerIdx = SMALL_CHUNK_COUNT-1;
seanhalle@209:        insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]);
seanhalle@209:    }
seanhalle@208:    else
seanhalle@209:    {
seanhalle@209:        containerIdx = getContainer(getChunkSize(chunkToFree)) - 1;
seanhalle@209:        insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
seanhalle@209:        if(containerIdx < 64)
seanhalle@209:            freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
seanhalle@209:        else
seanhalle@209:            freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
seanhalle@209:    }   
seanhalle@209:    
seanhalle@210:          MEAS__Capture_Post_Free_Point;
seanhalle@208:  }
seanhalle@208: 
seanhalle@209: /*
seanhalle@209:  * Designed to be called from the main thread outside of VMS, during init
seanhalle@208:  */
seanhalle@209: MallocArrays *
seanhalle@208: VMS_ext__create_free_list()
seanhalle@209: {     
seanhalle@209:    //Initialize containers for small chunks and fill with zeros
seanhalle@209:    _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
seanhalle@209:    MallocArrays *freeLists = _VMSMasterEnv->freeLists;
seanhalle@209:    
seanhalle@209:    freeLists->smallChunks = 
seanhalle@209:            (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
seanhalle@209:    memset((void*)freeLists->smallChunks,
seanhalle@209:            0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
seanhalle@209:    
seanhalle@209:    //Calculate number of containers for big chunks
seanhalle@209:    uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
seanhalle@209:    freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
seanhalle@209:    memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
seanhalle@209:    freeLists->containerCount = container;
seanhalle@209:    
seanhalle@209:    //Create first element in lastContainer 
seanhalle@209:    MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
seanhalle@209:    if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);}
seanhalle@209:    freeLists->memSpace = firstChunk;
seanhalle@208:    
seanhalle@208:    //Touch memory to avoid page faults
seanhalle@208:    void *ptr,*endPtr; 
seanhalle@208:    endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
seanhalle@208:    for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
seanhalle@208:    {
seanhalle@208:        *(char*)ptr = 0;
seanhalle@208:    }
seanhalle@208:    
seanhalle@209:    firstChunk->nextLowerInMem = NULL;
seanhalle@209:    firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
seanhalle@209:                         MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog));
seanhalle@209:    firstChunk->nextChunkInFreeList = NULL;
seanhalle@209:    //previous element in the queue is the container
seanhalle@209:    firstChunk->prevChunkInFreeList = &freeLists->bigChunks[container-2];
seanhalle@209:    
seanhalle@209:    freeLists->bigChunks[container-2] = firstChunk;
seanhalle@209:    //Insert into bit search list
seanhalle@209:    if(container <= 65)
seanhalle@209:    {
seanhalle@209:        freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2));
seanhalle@209:        freeLists->bigChunksSearchVector[1] = 0;
seanhalle@209:    }   
seanhalle@209:    else
seanhalle@209:    {
seanhalle@209:        freeLists->bigChunksSearchVector[0] = 0;
seanhalle@209:        freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66));
seanhalle@209:    }
seanhalle@209:    
seanhalle@209:    //Create dummy chunk to mark the top of stack this is of course
seanhalle@209:    //never freed
seanhalle@209:    MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
seanhalle@209:    dummyChunk->nextHigherInMem = dummyChunk+1;
seanhalle@209:    dummyChunk->nextLowerInMem  = NULL;
seanhalle@209:    dummyChunk->nextChunkInFreeList = NULL;
seanhalle@209:    dummyChunk->prevChunkInFreeList = NULL;
seanhalle@209:    
seanhalle@209:    return freeLists;
seanhalle@208:  }
seanhalle@208: 
seanhalle@208: 
seanhalle@208: /*Designed to be called from the main thread outside of VMS, during cleanup
seanhalle@208:  */
seanhalle@208: void
seanhalle@209: VMS_ext__free_free_list( MallocArrays *freeLists )
seanhalle@208:  {    
seanhalle@209:    free(freeLists->memSpace);
seanhalle@209:    free(freeLists->bigChunks);
seanhalle@209:    free(freeLists->smallChunks);
seanhalle@209:    
seanhalle@208:  }
seanhalle@208: