Feature/memory arena (#631)

* First pass at MemoryArena.

* First pass at RandomGenerator.

* Extract TestContext into external source file.

* Fix warning on printf.

* Use enum classes for Test enums.
OutputMode -> TestOutputMode.

* First pass at FreeList unit test.

* Auto registering tests.
Improvements to RandomGenerator.

* Remove the need for unitTest headers - cos can use registering.

* Added unitTest for MemoryArena.

* Do unit tests.

* Fix typo.

1 files changed, 393 insertions, 0 deletions

diff --git a/source/core/slang-memory-arena.h b/source/core/slang-memory-arena.h
new file mode 100644
index 000000000..acbac51dd
--- /dev/null
+++ b/source/core/slang-memory-arena.h
@@ -0,0 +1,393 @@
+#ifndef SLANG_MEMORY_ARENA_H
+#define SLANG_MEMORY_ARENA_H
+
+#include "../../slang.h"
+
+#include <assert.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "slang-free-list.h"
+
+namespace Slang { 
+
+/** Defines arena allocator where allocations are made very quickly, but that deallocations
+can only be performed in reverse order, or with the client code knowing a previous deallocation (say with
+ deallocateAllFrom), automatically deallocates everything after it.
+
+It works by allocating large blocks and then cutting out smaller pieces as requested. If a piece of memory is
+deallocated, it either MUST be in reverse allocation order OR the subsequent allocations are implicitly 
+deallocated too, and therefore accessing their memory is now undefined behavior. Allocations are made 
+contiguously from the current block. If there is no space in the current block, the 
+next block (which is unused) if available is checked. If that works, an allocation is made from the next block. 
+If not a new block is allocated that can hold at least the allocation with required alignment.
+ 
+All memory allocated can be deallocated very quickly and without a client having to track any memory. 
+All memory allocated will be freed on destruction - or with reset.
+
+A memory arena can have requests larger than the block size. When that happens they will just be allocated
+from the heap. As such 'oversized blocks' are seen as unusual and potentially wasteful they are deallocated
+when deallocateAll is called, whereas regular size blocks will remain allocated for fast subsequent allocation.
+
+It is intentional that blocks information is stored separately from the allocations that store the
+user data. This is so that alignment permitting, block allocations sizes can be passed directly to underlying allocator.
+For large power of 2 backing allocations this might mean a page/pages directly allocated by the OS for example.
+Also means better cache coherency when traversing blocks -> as generally they will be contiguous in memory.
+
+Also note that allocateUnaligned can be used for slightly faster aligned allocations. All blocks allocated internally
+are aligned to the blockAlignment passed to the constructor. If subsequent allocations (of any type) sizes are of that
+alignment or larger then no alignment fixing is required (because allocations are contiguous) and so 'allocateUnaligned'
+will return allocations of blockAlignment alignment.
+*/
+class MemoryArena
+{
+public:
+    typedef MemoryArena ThisType;
+
+    static const size_t kMinAlignment = sizeof(void*);  ///< The minimum alignment of the backing memory allocator.
+
+        /** Determines if an allocation is consistent with an allocation from this arena.
+
+        The test cannot say definitively if this was such an allocation, because the exact details
+        of each allocation is not kept.
+        @param alloc The start of the allocation
+        @param sizeInBytes The size of the allocation
+        @return true if allocation could have been from this Arena */
+    bool isValid(const void* alloc, size_t sizeInBytes) const;
+
+        /** Initialize the arena with specified block size and alignment 
+        If the arena has been previously initialized will free and deallocate all memory */
+    void init(size_t blockSize, size_t blockAlignment = kMinAlignment);
+
+        /** Allocate some memory of at least size bytes without having any specific alignment.
+
+         Can be used for slightly faster *aligned* allocations if caveats in class description are met. The
+         Unaligned, means the method will not enforce alignment - but a client call to allocateUnaligned can control
+         subsequent allocations alignments via it's size.
+
+         @param size The size of the allocation requested (in bytes and must be > 0).
+         @return The allocation. Can be nullptr if backing allocator was not able to request required memory */
+    void* allocate(size_t sizeInBytes);
+
+        /** Allocate some aligned memory of at least size bytes 
+         @param size Size of allocation wanted (must be > 0).
+         @param alignment Alignment of allocation - must be a power of 2.
+         @return The allocation (or nullptr if unable to allocate). Will be at least 'alignment' alignment or better. */
+    void* allocateAligned(size_t sizeInBytes, size_t alignment);
+
+        /** Allocate some aligned memory of at least size bytes 
+        @param size Size of allocation wanted (must be > 0).
+        @param alignment Alignment of allocation - must be a power of 2.
+        @return The allocation (or nullptr if unable to allocate). Will be at least 'alignment' alignment or better. */
+    void* allocateUnaligned(size_t sizeInBytes);
+
+        /** Allocates a null terminated string.
+        @param str A null-terminated string
+        @return A copy of the string held on the arena */
+    const char* allocateString(const char* str);
+
+        /** Allocates a null terminated string.     
+         @param chars Pointer to first character
+         @param charCount The amount of characters NOT including terminating 0.
+         @return A copy of the string held on the arena. */
+    const char* allocateString(const char* chars, size_t numChars);
+
+        /// Allocate an element of the specified type. Note: Constructor for type is not executed.
+    template <typename T>
+    T* allocate();
+
+        /// Allocate an array of a specified type. NOTE Constructor of T is NOT executed.
+    template <typename T>
+    T* allocateArray(size_t size);
+
+        /// Allocate an array of a specified type, and copy array passed into it.
+    template <typename T>
+    T* allocateAndCopyArray(const T* src, size_t size);  
+
+        /// Allocate an array of a specified type, and zero it.
+    template <typename T>
+    T* allocateAndZeroArray(size_t size);
+
+        /// Deallocate the last allocation. If data is not from the last allocation then the behavior is undefined.
+    void deallocateLast(void* data);
+
+        /// Deallocate this allocation and all remaining after it.
+    void deallocateAllFrom(void* dataStart);
+
+        /** Deallocates all allocated memory. That backing memory will generally not be released so
+         subsequent allocation will be fast, and from the same memory. Note though that 'oversize' blocks
+         will be deallocated. */
+    void deallocateAll();
+
+        /// Resets to the initial state when constructed (and all backing memory will be deallocated)  
+    void reset();
+        /// Adjusts such that the next allocate will be at least to the block alignment.
+    void adjustToBlockAlignment();
+ 
+        /// Gets the block alignment that is passed at initialization otherwise 0 an invalid block alignment.
+    size_t getBlockAlignment() const { return m_blockAlignment; }
+
+        /// Default Ctor
+    MemoryArena();
+        /// Construct with block size and alignment. Block alignment must be a power of 2.
+    MemoryArena(size_t blockSize, size_t blockAlignment = kMinAlignment);
+
+        /// Dtor
+    ~MemoryArena();
+
+protected:
+    struct Block
+    {
+        Block* m_next;
+        uint8_t* m_alloc;
+        uint8_t* m_start;
+        uint8_t* m_end;
+    };
+
+    void _initialize(size_t blockSize, size_t blockAlignment);
+
+    void* _allocateAligned(size_t size, size_t alignment);
+    void _deallocateBlocks();
+
+    void _setCurrentBlock(Block* block);
+
+    Block* _newCurrentBlock(size_t size, size_t alignment);
+    Block* _findBlock(const void* alloc, Block* endBlock = nullptr) const;
+    Block* _findPreviousBlock(Block* block);
+
+    uint8_t* m_start;
+    uint8_t* m_end;
+    uint8_t* m_current;
+    size_t m_blockSize; 
+    size_t m_blockAlignment;
+    Block* m_blocks;
+    Block* m_currentBlock;
+
+    FreeList m_blockFreeList;
+
+    private:
+    // Disable
+    MemoryArena(const ThisType& rhs) = delete;
+    void operator=(const ThisType& rhs) = delete;
+};
+
+// --------------------------------------------------------------------------
+inline bool MemoryArena::isValid(const void* data, size_t size) const
+{
+    assert(size);
+
+    uint8_t* ptr = (uint8_t*)data;
+    // Is it in current
+    if (ptr >= m_start && ptr + size <= m_current)
+    {
+        return true;
+    }
+    // Is it in a previous block?
+    Block* block = _findBlock(data, m_currentBlock);
+    return block && (ptr >= block->m_start && (ptr + size) <= block->m_end);
+}
+
+// --------------------------------------------------------------------------
+SLANG_FORCE_INLINE void* MemoryArena::allocateUnaligned(size_t size)
+{
+    // Align with the minimum alignment
+    uint8_t* mem = m_current;
+    uint8_t* end = mem + size;
+    if (end <= m_end)
+    {
+        m_current = end;
+        return mem;
+    }
+    else
+    {
+        return _allocateAligned(size, m_blockAlignment);
+    }
+}
+
+// --------------------------------------------------------------------------
+SLANG_FORCE_INLINE void* MemoryArena::allocate(size_t size)
+{
+    // Align with the minimum alignment
+    const size_t alignMask = kMinAlignment - 1;
+    uint8_t* mem = (uint8_t*)((size_t(m_current) + alignMask) & ~alignMask);
+
+    if (mem + size <= m_end)
+    {
+        m_current = mem + size;
+        return mem;
+    }
+    else
+    {
+        return _allocateAligned(size, kMinAlignment);
+    }
+}
+
+// --------------------------------------------------------------------------
+inline void* MemoryArena::allocateAligned(size_t size, size_t alignment)
+{
+    // Alignment must be a power of 2
+    assert(((alignment - 1) & alignment) == 0);
+
+    // Align the pointer
+    const size_t alignMask = alignment - 1;
+    uint8_t* memory = (uint8_t*)((size_t(m_current) + alignMask) & ~alignMask);
+
+    if (memory + size <= m_end)
+    {
+        m_current = memory + size;
+        return memory;
+    }
+    else
+    {
+        return _allocateAligned(size, alignment);
+    }
+}
+
+// --------------------------------------------------------------------------
+inline const char* MemoryArena::allocateString(const char* str)
+{
+    size_t size = ::strlen(str);
+    if (size == 0)
+    {
+        return "";
+    }
+    char* dst = (char*)allocateUnaligned(size + 1);
+    ::memcpy(dst, str, size + 1);
+    return dst;
+}
+
+// --------------------------------------------------------------------------
+inline const char* MemoryArena::allocateString(const char* chars, size_t charsCount)
+{
+    if (charsCount == 0)
+    {
+        return "";
+    }
+    char* dst = (char*)allocateUnaligned(charsCount + 1);
+    ::memcpy(dst, chars, charsCount);
+
+    // Add null-terminating zero
+    dst[charsCount] = 0;
+    return dst;
+} 
+
+// --------------------------------------------------------------------------
+template <typename T>
+inline T* MemoryArena::allocate()
+{
+    return reinterpret_cast<T*>(allocateAligned(sizeof(T), SLANG_ALIGN_OF(T)));
+}
+
+// --------------------------------------------------------------------------
+template <typename T>
+inline T* MemoryArena::allocateArray(size_t count)
+{
+    return (count > 0) ? reinterpret_cast<T*>(allocateAligned(sizeof(T) * count, SLANG_ALIGN_OF(T))) : nullptr;
+}
+
+// --------------------------------------------------------------------------
+template <typename T>
+inline T* MemoryArena::allocateAndCopyArray(const T* arr, size_t size)
+{
+    if (size > 0)
+    {
+        const size_t totalSize = sizeof(T) * size;
+        void* ptr = allocateAligned(totalSize, SLANG_ALIGN_OF(T));
+        ::memcpy(ptr, arr, totalSize);
+        return reinterpret_cast<T*>(ptr);
+    }
+    return nullptr;
+}
+
+// ---------------------------------------------------------------------------
+template <typename T>
+inline T* MemoryArena::allocateAndZeroArray(size_t size)
+{
+    if (size > 0)
+    {
+        const size_t totalSize = sizeof(T) * size;
+        void* ptr = allocateAligned(totalSize, SLANG_ALIGN_OF(T));
+        ::memset(ptr, 0, totalSize);
+        return reinterpret_cast<T*>(ptr);
+    }
+    return nullptr;
+}
+
+// --------------------------------------------------------------------------
+inline void MemoryArena::deallocateLast(void* data)
+{
+    // See if it's in current block
+    uint8_t* ptr = (uint8_t*)data;
+    if (ptr >= m_start && ptr < m_current)
+    {
+        // Then just go back
+        m_current = ptr;
+    }
+    else
+    {
+        // Only called if not in the current block. Therefore can only be in previous
+        Block* prevBlock = _findPreviousBlock(m_currentBlock);
+        if (prevBlock == nullptr || (!(ptr >= prevBlock->m_start && ptr < prevBlock->m_end)))
+        {
+            assert(!"Allocation not found");
+            return;
+        }
+
+        // Make the previous block the current
+        _setCurrentBlock(prevBlock);
+        // Make the current the alloc freed
+        m_current = ptr;
+    }
+}
+
+// --------------------------------------------------------------------------
+inline void MemoryArena::deallocateAllFrom(void* data)
+{
+    // See if it's in current block, and is allocated (ie < m_current)
+    uint8_t* ptr = (uint8_t*)data;
+    if (ptr >= m_start && ptr < m_current)
+    {
+        // If it's in current block, then just go back
+        m_current = ptr;
+        return;
+    }
+
+    // Search all blocks prior to current block
+    Block* block = _findBlock(data, m_currentBlock);
+    assert(block);
+    if (!block)
+    {
+        return;
+    }
+    // Make this current block
+    _setCurrentBlock(block);
+
+    // Move the pointer to the allocations position
+    m_current = ptr;
+}
+
+// --------------------------------------------------------------------------
+inline void MemoryArena::adjustToBlockAlignment()
+{
+    const size_t alignMask = m_blockAlignment - 1;
+    uint8_t* ptr = (uint8_t*)((size_t(m_current) + alignMask) & ~alignMask);
+
+    // Alignment might push beyond end of block... if so allocate a new block
+    // This test could be avoided if we aligned m_end, but depending on block alignment that might waste some space
+    if (ptr > m_end)
+    {
+        // We'll need a new block to make this alignment
+        _newCurrentBlock(0, m_blockAlignment);
+    }
+    else
+    {
+        // Set the position
+        m_current = ptr;
+    }
+    assert(size_t(m_current) & alignMask);
+}
+
+} // namespace Slang
+
+#endif // SLANG_MEMORY_ARENA_H
\ No newline at end of file