gistfile1.cpp

#include <iostream>
#include <cstdlib>
#include <cfloat>
#include <cmath>

#include "simpletest.h"

#include "allocator.h"

using namespace std;

SIMPLETEST_DECL

uint64_t memspace[4096];
uint64_t expectedMemspace[4096];

auto format_hex = [](const uint64_t & x){clog << boost::format("%16X")%x;};
auto format_hexaddr = [](const void * & x){clog << boost::format("%16X")%x;};

int main(int argc, const char * argv[])
{
    StartTestGroup("Allocator");
    
    auto heap = (Allocator *)nullptr;
    memset(memspace, 0x5A, sizeof(uint64_t)*4096);
    memcpy(expectedMemspace, memspace, sizeof(uint64_t)*4096);
    
    auto emPool = expectedMemspace + 1024;
    for(int j = 0; j < 128; ++j)
        emPool[j] = 0;
    emPool[1] = 2048;
    emPool[2] = 1;
    emPool[64+13] = 128;// Free list
    emPool[128] = (2048-2-128) | 0x8000000000000000ll;// free block size and status
    emPool[129] = 0;// free block next ptr
    emPool[2047] = 2048-2-128;// free block size
    
    //------------------------------------------------------------------------
    ShouldNotThrow("construction", [&]{heap = new Allocator;});
    ShouldNotThrow("Init()", [&]{heap->Init(memspace + 1024, 2048);});
    
    //------------------------------------------------------------------------
    // Test pool creation
    
    Should("pool underflow after construction", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after construction", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after construction", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test allocation #1
    auto alloc1 = (uint8_t *)nullptr;
    ShouldNotThrow("Alloc<uint8_t>(16)", [&]{alloc1 = heap->Alloc<uint8_t>(16);});
    
    Should("alloc1 location", alloc1, memspace + 1024 + 129);
    memset(alloc1, 0, 16);
    
    emPool[64+13] = 132;// Free list
    
    emPool[128] = 2;// allocated block size and status
    memset(emPool + 129, 0, 16);
    emPool[131] = 2;// allocated block size
    
    emPool[132] = (2048-2-128-4) | 0x8000000000000000ll;// free block size and status
    emPool[133] = 0;// free block next ptr
    emPool[2047] = 2048-2-128-4;// free block size
    
    Should("pool underflow after Alloc()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Alloc()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test allocation #2
    auto alloc2 = (uint8_t *)nullptr;
    ShouldNotThrow("Alloc<uint8_t>(16) 2", [&]{alloc2 = heap->Alloc<uint8_t>(16);});
    
    Should("alloc2 location", alloc2, memspace + 1024 + 133);
    memset(alloc2, 0, 16);
    
    emPool[64+13] = 136;// Free list
    
    emPool[132] = 2;// allocated block 2 size and status
    memset(emPool + 133, 0, 16);
    emPool[135] = 2;// allocated block 2 size
    
    emPool[136] = (2048-2-128-8) | 0x8000000000000000ll;// free block size and status
    emPool[137] = 0;// free block next ptr
    emPool[2047] = 2048-2-128-8;// free block size
    
    Should("pool underflow after Alloc()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Alloc()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Do two more allocations and sanity check
    auto alloc3 = (uint8_t *)nullptr;
    auto alloc4 = (uint8_t *)nullptr;
    ShouldNotThrow("Alloc<uint8_t>(16) 3", [&]{alloc3 = heap->Alloc<uint8_t>(16);});
    ShouldNotThrow("Alloc<uint8_t>(16) 4", [&]{alloc4 = heap->Alloc<uint8_t>(16);});
    
    Should("alloc3 location", alloc3, memspace + 1024 + 137);
    Should("alloc4 location", alloc4, memspace + 1024 + 141);
    memset(alloc3, 0, 16);
    memset(alloc4, 0, 16);
    
    emPool[64+13] = 144;// Free list
    
    emPool[136] = 2;// allocated block 3 size and status
    memset(emPool + 137, 0, 16);
    emPool[139] = 2;// allocated block 3 size
    
    emPool[140] = 2;// allocated block 4 size and status
    memset(emPool + 141, 0, 16);
    emPool[143] = 2;// allocated block 4 size
    
    emPool[144] = (2048-2-144) | 0x8000000000000000ll;// free block size and status
    emPool[145] = 0;// free block next ptr
    emPool[2047] = 2048-2-144;// free block size
    
    Should("pool underflow after Alloc()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Alloc()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test deallocation of single block, no merging
    ShouldNotThrow("Free(alloc3)", [&]{heap->Free(alloc3);});
    
    emPool[64+4] = 136;// Free list
    
    emPool[136] = 2 | 0x8000000000000000ll;// freed block 3 size and status
    emPool[139] = 2;// freed block 3 size
    
    Should("pool underflow after Free()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Free()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test exact size allocation, re-allocates previously freed block
    ShouldNotThrow("Alloc<uint8_t>(16) 3_2", [&]{alloc3 = heap->Alloc<uint8_t>(16);});
    
    Should("alloc3_2 location", alloc3, memspace + 1024 + 137);
    
    emPool[64+4] = 0;// Free list
    
    emPool[136] = 2;// allocated block 3 size and status
    emPool[139] = 2;// allocated block 3 size
    
    Should("pool underflow after Alloc()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Alloc()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test deallocation of lowest block
    ShouldNotThrow("Free(alloc1)", [&]{heap->Free(alloc1);});
    
    emPool[64+4] = 128;// Free list
    
    emPool[128] = 2 | 0x8000000000000000ll;// freed block 1 size and status
    emPool[131] = 2;// freed block 1 size
    
    Should("pool underflow after Free()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Free()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test deallocation of single block, merging with lower block
    ShouldNotThrow("Free(alloc2)", [&]{heap->Free(alloc2);});
    
    emPool[64+4] = 0;// Free lists
    emPool[64+5] = 128;
    
    emPool[128] = 6 | 0x8000000000000000ll;// freed block 1 & 2 size and status
    emPool[135] = 6;
    
    Should("pool underflow after Free()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Free()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test deallocation of single block, merging with higher block
    ShouldNotThrow("Free(alloc4)", [&]{heap->Free(alloc4);});
    
    emPool[64+13] = 140;// Free list
    
    emPool[140] = 2048-2-140 | 0x8000000000000000ll;// freed block 1 & 2 size and status
    emPool[2047] = 2048-2-140;// free block size
    
    Should("pool underflow after Free()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Free()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    //------------------------------------------------------------------------
    // Test deallocation of single block, merging with higher and lower block
    ShouldNotThrow("Free(alloc3)", [&]{heap->Free(alloc3);});
    
    emPool[64+13] = 128;// Free list
    emPool[64+5] = 0;
    
    emPool[139] = 10;// temporary freed block 1, 2, and 3 size
    
    emPool[128] = 2048-2-128 | 0x8000000000000000ll;// freed block 1 & 2 size and status
    emPool[2047] = 2048-2-128;// free block size
    
    Should("pool underflow after Free()", memspace, expectedMemspace, 1024, format_hex);
    Should("pool overflow after Free()", memspace + 1024*3, expectedMemspace + 1024*3, 1024, format_hex);
    Should("memory map after Alloc()", memspace + 1024, expectedMemspace + 1024, 2048, format_hex);
    
    EndTestGroup("Allocator");
    
    return EXIT_SUCCESS;
}