PLUGINS: add ELF memory manager to solve fragmentation

Following lordhoto's suggestion, I implemented a simple allocator that grabs the size of the biggest available plugin in memory. This is an elegant solution to the fragmentation problem, with the caveat that memory is wasted. As such, it's not suited for the DS, so I added a #define to disable it there.

svn-id: r55009

7 files changed, 357 insertions, 14 deletions

diff --git a/backends/plugins/elf/elf-loader.cpp b/backends/plugins/elf/elf-loader.cpp
index f7b151ecee..43477e06e2 100644
--- a/backends/plugins/elf/elf-loader.cpp
+++ b/backends/plugins/elf/elf-loader.cpp
@@ -28,6 +28,7 @@
 #if defined(DYNAMIC_MODULES) && defined(USE_ELF_LOADER)
 
 #include "backends/plugins/elf/elf-loader.h"
+#include "backends/plugins/elf/memory-manager.h"
 
 #include "common/debug.h"
 #include "common/file.h"
@@ -52,7 +53,7 @@ DLObject::DLObject() :
 
 DLObject::~DLObject() {
 	discardSymtab();
-	free(_segment);
+	ELFMemMan.pluginDeallocate(_segment);
 	_segment = 0;
 }
 
@@ -71,7 +72,7 @@ void DLObject::discardSymtab() {
 void DLObject::unload() {
 	discardSymtab();
 
-	free(_segment);
+	ELFMemMan.pluginDeallocate(_segment);
 
 	_segment = 0;
 	_segmentSize = 0;
@@ -165,7 +166,7 @@ bool DLObject::readProgramHeaders(Elf32_Ehdr *ehdr, Elf32_Phdr *phdr, Elf32_Half
 }
 
 bool DLObject::loadSegment(Elf32_Phdr *phdr) {
-	_segment = (byte *)memalign(phdr->p_align, phdr->p_memsz);
+	_segment = (byte *)ELFMemMan.pluginAllocate(phdr->p_align, phdr->p_memsz);
 
 	if (!_segment) {
 		warning("elfloader: Out of memory.");
@@ -222,19 +223,27 @@ Elf32_Shdr * DLObject::loadSectionHeaders(Elf32_Ehdr *ehdr) {
 	return shdr;
 }
 
-int DLObject::loadSymbolTable(Elf32_Ehdr *ehdr, Elf32_Shdr *shdr) {
-	assert(_file);
-
+int DLObject::findSymbolTableSection(Elf32_Ehdr *ehdr, Elf32_Shdr *shdr) {
+	int SymbolTableSection = -1;
+	
 	// Loop over sections, looking for symbol table linked to a string table
 	for (uint32 i = 0; i < ehdr->e_shnum; i++) {
 		if (shdr[i].sh_type == SHT_SYMTAB &&
 				shdr[i].sh_entsize == sizeof(Elf32_Sym) &&
 				shdr[i].sh_link < ehdr->e_shnum &&
-				shdr[shdr[i].sh_link].sh_type == SHT_STRTAB &&
-				_symtab_sect < 0) {
-			_symtab_sect = i;
+				shdr[shdr[i].sh_link].sh_type == SHT_STRTAB) {
+			SymbolTableSection = i;
+			break;
 		}
 	}
+	
+	return SymbolTableSection;
+}
+
+int DLObject::loadSymbolTable(Elf32_Ehdr *ehdr, Elf32_Shdr *shdr) {
+	assert(_file);
+
+	_symtab_sect = findSymbolTableSection(ehdr, shdr);
 
 	// Check for no symbol table
 	if (_symtab_sect < 0) {
@@ -308,6 +317,43 @@ void DLObject::relocateSymbols(ptrdiff_t offset) {
 	}
 }
 
+// Track the size of the plugin through memory manager without loading
+// the plugin into memory. 
+//
+void DLObject::trackSize(const char *path) {
+	
+	_file = Common::FSNode(path).createReadStream();
+	
+	if (!_file) {
+		warning("elfloader: File %s not found.", path);
+		return;
+	}
+
+	Elf32_Ehdr ehdr;
+	Elf32_Phdr phdr;
+
+	if (!readElfHeader(&ehdr))
+		return;
+	
+	ELFMemMan.trackPlugin(true);	// begin tracking the plugin size
+	
+	// Load the segments
+	for (uint32 i = 0; i < ehdr.e_phnum; i++) {	
+		debug(2, "elfloader: Loading segment %d", i);
+
+		if (!readProgramHeaders(&ehdr, &phdr, i))
+			return;
+
+		if (phdr.p_flags & PF_X) {	// check for executable, allocated segment
+			ELFMemMan.trackAlloc(phdr.p_align, phdr.p_memsz);
+		}
+	}
+	
+	ELFMemMan.trackPlugin(false);	// we're done tracking the plugin size
+
+	// No need to track the symbol table sizes -- they get discarded
+}
+
 bool DLObject::load() {
 	Elf32_Ehdr ehdr;
 	Elf32_Phdr phdr;
@@ -315,7 +361,8 @@ bool DLObject::load() {
 	if (readElfHeader(&ehdr) == false)
 		return false;
 
-	for (uint32 i = 0; i < ehdr.e_phnum; i++) {	//Load our segments
+	//Load the segments
+	for (uint32 i = 0; i < ehdr.e_phnum; i++) {	
 		debug(2, "elfloader: Loading segment %d", i);
 
 		if (readProgramHeaders(&ehdr, &phdr, i) == false)
diff --git a/backends/plugins/elf/elf-loader.h b/backends/plugins/elf/elf-loader.h
index 2825cc9d8d..e11aaf1ad0 100644
--- a/backends/plugins/elf/elf-loader.h
+++ b/backends/plugins/elf/elf-loader.h
@@ -67,6 +67,7 @@ protected:
 	bool readProgramHeaders(Elf32_Ehdr *ehdr, Elf32_Phdr *phdr, Elf32_Half num);
 	virtual bool loadSegment(Elf32_Phdr *phdr);
 	Elf32_Shdr *loadSectionHeaders(Elf32_Ehdr *ehdr);
+	int findSymbolTableSection(Elf32_Ehdr *ehdr, Elf32_Shdr *shdr);
 	int loadSymbolTable(Elf32_Ehdr *ehdr, Elf32_Shdr *shdr);
 	bool loadStringTable(Elf32_Shdr *shdr);
 	virtual void relocateSymbols(ptrdiff_t offset);
@@ -90,6 +91,11 @@ public:
 	DLObject();
 	virtual ~DLObject();
 
+	/**
+	 * Test the size of the plugin in memory using the memory manager.
+	 * @param path			Path of file
+	 */
+	void trackSize(const char *path);
 	bool open(const char *path);
 	bool close();
 	void *symbol(const char *name);
diff --git a/backends/plugins/elf/elf-provider.cpp b/backends/plugins/elf/elf-provider.cpp
index b241379934..393010fd6f 100644
--- a/backends/plugins/elf/elf-provider.cpp
+++ b/backends/plugins/elf/elf-provider.cpp
@@ -33,6 +33,7 @@
 
 #include "backends/plugins/elf/elf-provider.h"
 #include "backends/plugins/dynamic-plugin.h"
+#include "backends/plugins/elf/memory-manager.h"
 
 #include "common/debug.h"
 #include "common/fs.h"
@@ -96,6 +97,17 @@ DynamicPlugin::VoidFunc ELFPlugin::findSymbol(const char *symbol) {
 	return tmp;
 }
 
+ /**
+  * Test the size of the plugin.
+  */
+void ELFPlugin::trackSize() {
+	// All we need to do is create our object, track its size, then delete it
+	DLObject *obj = makeDLObject();
+	
+	obj->trackSize(_filename.c_str());
+	delete obj;
+}
+
 bool ELFPlugin::loadPlugin() {
 	assert(!_dlHandle);
 
@@ -162,6 +174,30 @@ void ELFPlugin::unloadPlugin() {
 	}
 }
 
+ /**
+  * We override this function in FilePluginProvider to allow the single
+  * plugin method to create a non-fragmenting memory allocation. We take
+  * the plugins found and tell the memory manager to allocate space for
+  * them.
+  */
+PluginList ELFPluginProvider::getPlugins() {
+	PluginList pl = FilePluginProvider::getPlugins();
+
+#if defined(ONE_PLUGIN_AT_A_TIME) && !defined(ELF_NO_MEM_MANAGER) 	
+	// This static downcast is safe because all of the plugins must
+	// be ELF plugins
+	for (PluginList::iterator p = pl.begin(); p != pl.end(); ++p) {
+		(static_cast<ELFPlugin *>(*p))->trackSize();
+	}
+
+	// The Memory Manager should now allocate space based on the information
+	// it collected
+	ELFMemMan.allocateHeap();
+#endif	
+	
+	return pl;
+}
+
 bool ELFPluginProvider::isPluginFilename(const Common::FSNode &node) const {
 	// Check the plugin suffix
 	Common::String filename = node.getName();
diff --git a/backends/plugins/elf/elf-provider.h b/backends/plugins/elf/elf-provider.h
index 4d05c0956b..fe8346f95e 100644
--- a/backends/plugins/elf/elf-provider.h
+++ b/backends/plugins/elf/elf-provider.h
@@ -67,8 +67,9 @@ public:
 
 	virtual DLObject *makeDLObject() = 0;
 
-	bool loadPlugin();
-	void unloadPlugin();
+	virtual bool loadPlugin();
+	virtual void unloadPlugin();
+	void trackSize();
 };
 
 template<class T>
@@ -87,6 +88,7 @@ public:
 class ELFPluginProvider : public FilePluginProvider {
 protected:
 	virtual Plugin *createPlugin(const Common::FSNode &node) const = 0;
+	virtual PluginList getPlugins();
 
 	bool isPluginFilename(const Common::FSNode &node) const;
 };
diff --git a/backends/plugins/elf/memory-manager.cpp b/backends/plugins/elf/memory-manager.cpp
new file mode 100644
index 0000000000..6e573088e2
--- /dev/null
+++ b/backends/plugins/elf/memory-manager.cpp
@@ -0,0 +1,168 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * 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 for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ *
+ */
+
+#include "common/scummsys.h" 
+#include "common/util.h"
+#include "backends/plugins/elf/memory-manager.h"
+ 
+DECLARE_SINGLETON(ELFMemoryManager); 
+
+ELFMemoryManager::ELFMemoryManager() : 
+	_heap(0), _heapSize(0), _heapAlign(0), 
+	_trackAllocs(false), _measuredSize(0), _measuredAlign(0), 
+	_bytesAllocated(0) {}
+
+ELFMemoryManager::~ELFMemoryManager() {
+	free(_heap);
+	_heap = 0;
+}
+
+void ELFMemoryManager::trackPlugin(bool value) {
+	assert(!_heap);
+
+	if (value == _trackAllocs)
+		return;
+	
+	_trackAllocs = value;
+	
+	if (_trackAllocs) {	// start measuring
+		// start tracking allocations
+		_measuredAlign = 0;
+		
+	} else {	// we're done measuring
+		// get the total allocated size
+		size_t measuredSize = _allocList.back().end() - _allocList.front().start;
+
+		_heapSize = MAX(_heapSize, measuredSize);
+		_heapAlign = MAX(_heapAlign, _measuredAlign);
+		
+		_allocList.clear();
+		_bytesAllocated = 0;	// reset
+		
+		debug(2, "measured a plugin of size %d. Max size %d. Max align %d", measuredSize, _heapSize, _heapAlign);
+	}
+}
+
+void ELFMemoryManager::trackAlloc(size_t align, size_t size) {
+	if (!_measuredAlign)
+		_measuredAlign = align;
+		
+	// use the allocate function to simulate allocation
+	allocateOnHeap(align, size);
+}
+
+void ELFMemoryManager::allocateHeap() {
+	// The memory manager should only allocate once
+	assert (!_heap);
+	assert (_heapSize);
+	
+	// clear the list
+	_allocList.clear();
+	_bytesAllocated = 0;
+	
+	debug(2, "ELFMemoryManager: allocating %d bytes aligned at %d as the \
+			plugin heap", _heapSize, _heapAlign);
+	
+	// prepare the heap
+	if (_heapAlign) 
+		_heap = ::memalign(_heapAlign, _heapSize);
+	else
+		_heap = ::malloc(_heapSize);
+		
+	assert(_heap);
+}
+
+void *ELFMemoryManager::pluginAllocate(size_t size) {
+	if (_heap) {
+		return pluginAllocate(sizeof(void *), size);
+	}
+	return ::malloc(size);
+}
+
+void *ELFMemoryManager::pluginAllocate(size_t align, size_t size) {
+	if (_heap) {
+		return allocateOnHeap(align, size);
+	} 
+	return ::memalign(align, size);
+}
+
+void ELFMemoryManager::pluginDeallocate(void *ptr) {
+	if (_heap) {
+		return deallocateFromHeap(ptr);
+	}
+	return ::free(ptr);
+}
+
+// Allocate space for the request in our heap
+void *ELFMemoryManager::allocateOnHeap(size_t align, size_t size) {
+	byte *lastAddress = (byte *)_heap;
+	
+	// We can't allow allocations smaller than sizeof(Allocation). This could
+	// only be from non-plugin allocations and would cause infinite recursion 
+	// when allocating our Allocation in the list.
+	if (size <= sizeof(Allocation))
+		return 0;
+	
+	Common::List<Allocation>::iterator i;
+	for (i = _allocList.begin(); i != _allocList.end(); i++) {
+		if (i->start - lastAddress > (int)size) 
+			break;
+		lastAddress = i->end();
+		// align to desired alignment
+		if (align) {
+			lastAddress = (byte *)( ((size_t)lastAddress + align - 1) & ~(align - 1) );
+		}
+	}
+	
+	// Check if we exceeded our heap limit
+	// We skip this case if we're only tracking allocations
+	if (!_trackAllocs && ((size_t)lastAddress + size > (size_t)_heap + _heapSize)) {
+		debug(2, "failed to find space to allocate %d bytes", size);
+		return 0;
+	}
+	
+	_allocList.insert(i, Allocation(lastAddress, size));
+	_bytesAllocated += size;
+	
+	debug(7, "ELFMemoryManager: allocated %d bytes at %p. Total %d bytes", 
+		size, lastAddress, _bytesAllocated);
+	
+	return lastAddress;
+}
+
+void ELFMemoryManager::deallocateFromHeap(void *ptr) {
+	Common::List<Allocation>::iterator i;
+	for (i = _allocList.begin(); i != _allocList.end(); i++) {
+		if (i->start == ptr) {
+			_bytesAllocated -= (*i).size;
+			
+			debug(7, "ELFMemoryManager: freed %d bytes at %p. Total %d bytes", 
+				(*i).size, (*i).start, _bytesAllocated);
+			
+			_allocList.erase(i);
+			break;
+		}
+	}	
+}
diff --git a/backends/plugins/elf/memory-manager.h b/backends/plugins/elf/memory-manager.h
new file mode 100644
index 0000000000..5121ed163d
--- /dev/null
+++ b/backends/plugins/elf/memory-manager.h
@@ -0,0 +1,83 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * 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 for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ *
+ */
+
+#ifndef ELF_MEMORY_MANAGER_H
+#define ELF_MEMORY_MANAGER_H
+
+#include "common/singleton.h"
+#include "common/list.h"
+#include "common/mutex.h"
+ 
+/**
+ * A 'foolproof' way to prevent memory fragmentation. This class is used to 
+ * serve as a permanent allocation to prevent the process of loading and 
+ * unloading plugins from causing heavy fragmentation.
+ **/
+ 
+#define ELFMemMan		ELFMemoryManager::instance()
+ 
+class ELFMemoryManager : public Common::Singleton<ELFMemoryManager> {
+public:	
+	void trackPlugin(bool value);
+	void trackAlloc(size_t align, size_t size);
+
+	void allocateHeap();
+
+	void *pluginAllocate(size_t size);
+	void *pluginAllocate(uint32 align, uint32 size);
+	void pluginDeallocate(void *ptr);
+	
+private:
+   friend class Common::Singleton<ELFMemoryManager>;
+
+	ELFMemoryManager();
+	~ELFMemoryManager();
+
+	void *allocateOnHeap(size_t align, size_t size);
+	void deallocateFromHeap(void *ptr);
+	
+	struct Allocation {
+		byte *start;
+		size_t size;
+		byte *end() { return start + size; }
+		Allocation(byte *a, size_t b) : start(a), size(b) {}
+	};
+
+	// heap
+	void *_heap;
+	size_t _heapAlign;			// alignment of the heap
+	size_t _heapSize;			// size of the heap
+	
+	// tracking allocations
+	bool _trackAllocs;		// whether we are currently tracking
+	size_t _measuredSize; 
+	size_t _measuredAlign;	
+	
+	// real allocations
+	Common::List<Allocation> _allocList;
+	uint32 _bytesAllocated;
+};
+ 
+#endif /* ELF_MEMORY_MANAGER_H */
diff --git a/backends/plugins/elf/mips-loader.cpp b/backends/plugins/elf/mips-loader.cpp
index b25017af98..42af831ef4 100644
--- a/backends/plugins/elf/mips-loader.cpp
+++ b/backends/plugins/elf/mips-loader.cpp
@@ -28,6 +28,7 @@
 #if defined(DYNAMIC_MODULES) && defined(USE_ELF_LOADER) && defined(MIPS_TARGET)
 
 #include "backends/plugins/elf/mips-loader.h"
+#include "backends/plugins/elf/memory-manager.h"
 
 #include "common/debug.h"
 
@@ -281,7 +282,7 @@ bool MIPSDLObject::loadSegment(Elf32_Phdr *phdr) {
 	// We need to take account of non-allocated segment for shorts
 	if (phdr->p_flags & PF_X) {	// This is a relocated segment
 		// Attempt to allocate memory for segment
-		_segment = (byte *)memalign(phdr->p_align, phdr->p_memsz);
+		_segment = (byte *)ELFMemMan.pluginAllocate(phdr->p_align, phdr->p_memsz);
 
 		if (!_segment) {
 			warning("elfloader: Out of memory.");
@@ -289,7 +290,7 @@ bool MIPSDLObject::loadSegment(Elf32_Phdr *phdr) {
 		}
 
 		debug(2, "elfloader: Allocated segment @ %p", _segment);
-
+		
 		// Get offset to load segment into
 		baseAddress = _segment;
 		_segmentSize = phdr->p_memsz;