commit 597c5213fe05ec840f864a44136419dee8a1d2d8
parent 1a7bf04b9f89d2168241b57c6ce7fda87053a7f5
Author: fundamental <mark.d.mccurry@gmail.com>
Date: Fri, 17 Oct 2014 11:30:01 -0400
Add Multi-Pool Info To Allocator
Diffstat:
4 files changed, 299 insertions(+), 18 deletions(-)
diff --git a/src/Misc/Allocator.cpp b/src/Misc/Allocator.cpp
@@ -5,22 +5,178 @@
#include "../../tlsf/tlsf.h"
#include "Allocator.h"
+//recursive type class to avoid void *v = *(void**)v style casting
+struct next_t
+{
+ next_t *next;
+ size_t pool_size;
+};
+
+void *data(next_t *n)
+{
+ return n+sizeof(next_t);
+}
+
+
+struct AllocatorImpl
+{
+ void *tlsf = 0;;
+
+ //singly linked list of memory pools
+ //XXX this may violate alignment on some platforms if malloc doesn't return
+ //nice values
+ next_t *pools = 0;
+};
+
Allocator::Allocator(void)
{
- void *buf = malloc(1024*1024);
- impl = tlsf_create_with_pool(buf, 1024*1024);
+ impl = new AllocatorImpl;
+ size_t default_size = 5*1024*1024;
+ impl->pools = (next_t*)malloc(default_size);
+ impl->pools->next = 0x0;
+ impl->pools->pool_size = default_size;
+ size_t off = tlsf_size() + tlsf_pool_overhead() + sizeof(next_t);
+ //printf("Generated Memory Pool with '%p'\n", impl->pools);
+ impl->tlsf = tlsf_create_with_pool(((char*)impl->pools)+off, default_size-2*off);
+ //printf("Allocator(%p)\n", impl);
+}
+
+Allocator::~Allocator(void)
+{
+ next_t *n = impl->pools;
+ while(n) {
+ next_t *nn = n->next;
+ free(n);
+ n = nn;
+ }
+ delete impl;
}
void *Allocator::alloc_mem(size_t mem_size)
{
- void *mem = tlsf_malloc(impl, mem_size);
- //fprintf(stderr, "Allocating memory (%p)\n", mem);
+ void *mem = tlsf_malloc(impl->tlsf, mem_size);
+ //printf("Allocator.malloc(%p, %d) = %p\n", impl, mem_size, mem);
+ //void *mem = malloc(mem_size);
+ //printf("Allocator result = %p\n", mem);
return mem;
- //return malloc(mem_size);
}
void Allocator::dealloc_mem(void *memory)
{
//fprintf(stderr, "Freeing memory (%p)\n", memory);
- tlsf_free(impl, memory);
+ tlsf_free(impl->tlsf, memory);
//free(memory);
}
+
+bool Allocator::lowMemory(unsigned n, size_t chunk_size)
+{
+ //This should stay on the stack
+ void *buf[n];
+ for(unsigned i=0; i<n; ++i)
+ buf[i] = tlsf_malloc(impl->tlsf, chunk_size);
+ bool outOfMem = false;
+ for(unsigned i=0; i<n; ++i)
+ outOfMem |= (buf[i] == nullptr);
+ for(unsigned i=0; i<n; ++i)
+ if(buf[i])
+ tlsf_free(impl->tlsf, buf[i]);
+
+ return outOfMem;
+}
+
+
+void Allocator::addMemory(void *v, size_t mem_size)
+{
+ next_t *n = impl->pools;
+ while(n->next) n = n->next;
+ n->next = (next_t*)v;
+ n->next->next = 0x0;
+ n->next->pool_size = mem_size;
+ //printf("Inserting '%p'\n", v);
+ off_t off = sizeof(next_t) + tlsf_pool_overhead();
+ void *result =
+ tlsf_add_pool(impl->tlsf, ((char*)n->next)+off,
+ //0x0eadbeef);
+ mem_size-off-sizeof(size_t));
+ if(!result)
+ printf("FAILED TO INSERT MEMORY POOL\n");
+};//{(void)mem_size;};
+
+//From tlsf internals
+typedef struct block_header_t
+{
+ /* Points to the previous physical block. */
+ struct block_header_t* prev_phys_block;
+
+ /* The size of this block, excluding the block header. */
+ size_t size;
+
+ /* Next and previous free blocks. */
+ struct block_header_t* next_free;
+ struct block_header_t* prev_free;
+} block_header_t;
+static const size_t block_header_free_bit = 1 << 0;
+
+bool Allocator::memFree(void *pool)
+{
+ size_t bh_shift = sizeof(next_t)+sizeof(size_t);
+ //printf("memFree(%p)\n", pool);
+ bool isFree = true;
+ block_header_t &bh = *(block_header_t*)((char*)pool+bh_shift);
+ //printf("size_test = %x\n", 50*1024*1024);
+ //printf("size1 = %x\n", bh.size);
+ if((bh.size&block_header_free_bit) == 0)
+ isFree = false;
+ //printf("Step 1 = %d\n", isFree);
+ block_header_t &bhn = *(block_header_t*)
+ (((char*)&bh)+((bh.size&~0x3)+bh_shift-2*sizeof(size_t)));
+ //printf("size2 = %x\n", bhn.size);
+ if((bhn.size&block_header_free_bit) != 0)
+ isFree = false;
+ //printf("Step 2 = %d\n", isFree);
+ if((bhn.size&~0x3) != 0)
+ isFree = false;
+ //printf("Step 3 = %d\n", isFree);
+ //printf("Result = %d\n\n", isFree);
+
+ return isFree;
+}
+
+int Allocator::memPools()
+{
+ int i = 1;
+ next_t *n = impl->pools;
+ while(n->next) {
+ i++;
+ n = n->next;
+ }
+ return i;
+}
+
+int Allocator::freePools()
+{
+ int i = 0;
+ next_t *n = impl->pools->next;
+ while(n) {
+ if(memFree(n))
+ i++;
+ n = n->next;
+ }
+ return i;
+}
+
+/*
+ * Notes on tlsf internals
+ * - TLSF consists of blocks linked by block headers and these form a doubly
+ * linked list of free segments
+ * - Original memory is [control_t pool]
+ * base sentinal
+ * Pools are [block_t block_t blocks ...]
+ * Blocks are [memory block_t](??)
+ * - These are stored in the control_t structure in an order dependent on the
+ * size that they are
+ * it's a bit unclear how collisions are handled here, but the basic premise
+ * makes sense
+ * - Additional structure is added before the start of each pool to define the
+ * pool size and the next pool in the list as this information is not
+ * accessible in O(good) time
+ */
diff --git a/src/Misc/Allocator.h b/src/Misc/Allocator.h
@@ -4,8 +4,9 @@ class Allocator
{
public:
Allocator(void);
- virtual void *alloc_mem(size_t mem_size);
- virtual void dealloc_mem(void *memory);
+ ~Allocator(void);
+ void *alloc_mem(size_t mem_size);
+ void dealloc_mem(void *memory);
template <typename T, typename... Ts>
T *alloc(Ts... ts)
@@ -64,28 +65,34 @@ class Allocator
//Return true if the current pool cannot allocate n chunks of chunk_size
bool lowMemory(unsigned n, size_t chunk_size);//{(void)n;(void)chunk_size; return false;};
+ bool memFree(void *pool);
- void *impl;
+ //returns number of pools
+ int memPools();
+
+ int freePools();
+
+ struct AllocatorImpl *impl;
};
//Memory that could either be from the heap or from the realtime allocator
//This should be avoided when possible, but it's not clear if it can be avoided
//in all cases
-template<class T>
-class HeapRtMem
-{
-};
+//template<class T>
+//class HeapRtMem
+//{
+//};
//A helper class used to perform a series of allocations speculatively to verify
//that there is enough memory for a set transation to occur.
//Stuff will get weird if this ends up failing, but it will be able to at least
//detect where there is an issue
-class StaticAllocFreeVerifyier
-{
- void *scratch_buf[4096];
- unsigned alloc_count;
-};
+//class StaticAllocFreeVerifyier
+//{
+// void *scratch_buf[4096];
+// unsigned alloc_count;
+//};
/**
diff --git a/src/Tests/AllocatorTest.h b/src/Tests/AllocatorTest.h
@@ -0,0 +1,115 @@
+/*
+ ZynAddSubFX - a software synthesizer
+
+ AllocatorTest.h - CxxTest for RT Memory Allocator
+ Copyright (C) 2014-2014 Mark McCurry
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of version 2 of the GNU General Public License
+ as published by the Free Software Foundation.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License (version 2 or later) for more details.
+
+ You should have received a copy of the GNU General Public License (version 2)
+ along with this program; if not, write to the Free Software Foundation,
+ Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+*/
+
+
+#include <cxxtest/TestSuite.h>
+#include <iostream>
+#include <fstream>
+#include <ctime>
+#include <cstring>
+#include <string>
+#include <vector>
+#include "../Misc/Allocator.h"
+//using namespace std;
+using std::vector;
+class AllocatorTest:public CxxTest::TestSuite
+{
+ public:
+ Allocator *memory_;
+ vector<void*> data;
+
+ void setUp() {
+ memory_ = new Allocator();
+ }
+
+ void tearDown() {
+ delete memory_;
+ }
+
+ void testBasic() {
+ Allocator &memory = *memory_;
+ char *d = (char*)memory.alloc_mem(128);
+ TS_ASSERT(d);
+ d[0] = 0;
+ d[127] = 0;
+ memory.dealloc_mem(d);
+ }
+
+ void testTooBig() {
+ Allocator &memory = *memory_;
+ //Try to allocate a gig
+ char *d = (char*)memory.alloc_mem(1024*1024*1024);
+ TS_ASSERT(d==nullptr);
+ }
+
+ void testEnlarge()
+ {
+ Allocator &memory = *memory_;
+ //Additional Buffers
+ size_t N = 50*1024*1024;
+ char *bufA = (char*)malloc(N);
+ char *bufB = (char*)malloc(N);
+ memset(bufA,0xff, N);
+ memset(bufB,0xff, N);
+
+
+ //By default 25MBi is too large
+ //Therefore this allocation should fail
+ bool low = memory.lowMemory(5,5*1024*1024);
+ TS_ASSERT(low);
+ TS_ASSERT(memory.memPools() == 1);
+
+
+ //Try to add a buffer
+ //This provides enough for the low memory check to pass
+ memory.addMemory(bufA, N);
+ TS_ASSERT(memory.memPools() == 2);
+ TS_ASSERT(memory.memFree(bufA));
+ bool low2 = memory.lowMemory(5,5*1024*1024);
+ TS_ASSERT(!low2);
+ TS_ASSERT(memory.memFree(bufA));
+
+ //We should be able to see that a chunk enters and exits the free
+ //state
+ char *mem2 = (char*)memory.alloc_mem(10*1024*1024);
+ TS_ASSERT(mem2);
+ TS_ASSERT(!memory.memFree(bufA));
+ memory.dealloc_mem(mem2);
+ TS_ASSERT(memory.memFree(bufA));
+ mem2 = (char*)memory.alloc_mem(10*1024*1024);
+ char *mem3 = (char*)memory.alloc_mem(10*1024*1024);
+ TS_ASSERT(mem3);
+ memory.dealloc_mem(mem2);
+ TS_ASSERT(!memory.memFree(bufA));
+ TS_ASSERT(memory.freePools() == 0);
+ memory.dealloc_mem(mem3);
+ TS_ASSERT(memory.memFree(bufA));
+ TS_ASSERT(memory.freePools() == 1);
+
+ //Observe that adding another pool superficially works
+ memory.addMemory(bufB, N);
+ TS_ASSERT(memory.freePools() == 2);
+
+ //delete [] bufA;
+ //delete [] bufB;
+ }
+
+};
diff --git a/src/Tests/CMakeLists.txt b/src/Tests/CMakeLists.txt
@@ -15,6 +15,8 @@ CXXTEST_ADD_TEST(PADnoteTest PadNoteTest.cpp ${CMAKE_CURRENT_SOURCE_DIR}/PadNote
CXXTEST_ADD_TEST(PluginTest PluginTest.cpp ${CMAKE_CURRENT_SOURCE_DIR}/PluginTest.h)
CXXTEST_ADD_TEST(UnisonTest UnisonTest.cpp ${CMAKE_CURRENT_SOURCE_DIR}/UnisonTest.h)
#CXXTEST_ADD_TEST(RtAllocTest RtAllocTest.cpp ${CMAKE_CURRENT_SOURCE_DIR}/RtAllocTest.h)
+CXXTEST_ADD_TEST(AllocatorTest AllocatorTest.cpp
+ ${CMAKE_CURRENT_SOURCE_DIR}/AllocatorTest.h)
#Extra libraries added to make test and full compilation use the same library
#links for quirky compilers
@@ -34,6 +36,7 @@ target_link_libraries(PluginTest zynaddsubfx_core zynaddsubfx_nio
${GUI_LIBRARIES} ${NIO_LIBRARIES} ${AUDIO_LIBRARIES})
target_link_libraries(UnisonTest ${test_lib})
#target_link_libraries(RtAllocTest ${test_lib})
+target_link_libraries(AllocatorTest ${test_lib})
#message(STATUS "Plugin Test ${GUI_LIBRARIES} ${NIO_LIBRARIES} ${AUDIO_LIBRARIES}")
