ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

memorypool.cpp

Go to the documentation of this file.
00001 /* ScummVM - Graphic Adventure Engine
00002  *
00003  * ScummVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the COPYRIGHT
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #include "common/memorypool.h"
00024 #include "common/util.h"
00025 
00026 namespace Common {
00027 
00028 enum {
00029     INITIAL_CHUNKS_PER_PAGE = 8
00030 };
00031 
00032 static size_t adjustChunkSize(size_t chunkSize) {
00033     // You must at least fit the pointer in the node (technically unneeded considering the next rounding statement)
00034     chunkSize = MAX(chunkSize, sizeof(void *));
00035     // There might be an alignment problem on some platforms when trying to load a void* on a non natural boundary
00036     // so we round to the next sizeof(void *)
00037     chunkSize = (chunkSize + sizeof(void *) - 1) & (~(sizeof(void *) - 1));
00038 
00039     return chunkSize;
00040 }
00041 
00042 
00043 MemoryPool::MemoryPool(size_t chunkSize)
00044     : _chunkSize(adjustChunkSize(chunkSize)) {
00045 
00046     _next = nullptr;
00047 
00048     _chunksPerPage = INITIAL_CHUNKS_PER_PAGE;
00049 }
00050 
00051 MemoryPool::~MemoryPool() {
00052 #if 0
00053     freeUnusedPages();
00054     if (!_pages.empty())
00055         warning("Memory leak found in pool");
00056 #endif
00057 
00058     for (size_t i = 0; i < _pages.size(); ++i)
00059         ::free(_pages[i].start);
00060 }
00061 
00062 void MemoryPool::allocPage() {
00063     Page page;
00064 
00065     // Allocate a new page
00066     page.numChunks = _chunksPerPage;
00067     assert(page.numChunks * _chunkSize < 16*1024*1024); // Refuse to allocate pages bigger than 16 MB
00068 
00069     page.start = ::malloc(page.numChunks * _chunkSize);
00070     assert(page.start);
00071     _pages.push_back(page);
00072 
00073 
00074     // Next time, we'll allocate a page twice as big as this one.
00075     _chunksPerPage *= 2;
00076 
00077     // Add the page to the pool of free chunk
00078     addPageToPool(page);
00079 }
00080 
00081 void MemoryPool::addPageToPool(const Page &page) {
00082     // Add all chunks of the new page to the linked list (pool) of free chunks
00083     void *current = page.start;
00084     for (size_t i = 1; i < page.numChunks; ++i) {
00085         void *next = (byte *)current + _chunkSize;
00086         *(void **)current = next;
00087 
00088         current = next;
00089     }
00090 
00091     // Last chunk points to the old _next
00092     *(void **)current = _next;
00093 
00094     // From now on, the first free chunk is the first chunk of the new page
00095     _next = page.start;
00096 }
00097 
00098 void *MemoryPool::allocChunk() {
00099     // No free chunks left? Allocate a new page
00100     if (!_next)
00101         allocPage();
00102 
00103     assert(_next);
00104     void *result = _next;
00105     _next = *(void **)result;
00106     return result;
00107 }
00108 
00109 void MemoryPool::freeChunk(void *ptr) {
00110     // Add the chunk back to (the start of) the list of free chunks
00111     *(void **)ptr = _next;
00112     _next = ptr;
00113 }
00114 
00115 // Technically not compliant C++ to compare unrelated pointers. In practice...
00116 bool MemoryPool::isPointerInPage(void *ptr, const Page &page) {
00117     return (ptr >= page.start) && (ptr < (char *)page.start + page.numChunks * _chunkSize);
00118 }
00119 
00120 void MemoryPool::freeUnusedPages() {
00121     //std::sort(_pages.begin(), _pages.end());
00122     Array<size_t> numberOfFreeChunksPerPage;
00123     numberOfFreeChunksPerPage.resize(_pages.size());
00124     for (size_t i = 0; i < numberOfFreeChunksPerPage.size(); ++i) {
00125         numberOfFreeChunksPerPage[i] = 0;
00126     }
00127 
00128     // Compute for each page how many chunks in it are still in use.
00129     void *iterator = _next;
00130     while (iterator) {
00131         // TODO: This should be a binary search (requiring us to keep _pages sorted)
00132         for (size_t i = 0; i < _pages.size(); ++i) {
00133             if (isPointerInPage(iterator, _pages[i])) {
00134                 ++numberOfFreeChunksPerPage[i];
00135                 break;
00136             }
00137         }
00138 
00139         iterator = *(void **)iterator;
00140     }
00141 
00142     // Free all pages which are not in use.
00143     size_t freedPagesCount = 0;
00144     for (size_t i = 0; i < _pages.size(); ++i)  {
00145         if (numberOfFreeChunksPerPage[i] == _pages[i].numChunks) {
00146             // Remove all chunks of this page from the list of free chunks
00147             void **iter2 = &_next;
00148             while (*iter2) {
00149                 if (isPointerInPage(*iter2, _pages[i]))
00150                     *iter2 = **(void ***)iter2;
00151                 else
00152                     iter2 = *(void ***)iter2;
00153             }
00154 
00155             ::free(_pages[i].start);
00156             ++freedPagesCount;
00157             _pages[i].start = nullptr;
00158         }
00159     }
00160 
00161 //  debug("freed %d pages out of %d", (int)freedPagesCount, (int)_pages.size());
00162 
00163     // Remove all now unused pages
00164     size_t newSize = 0;
00165     for (size_t i = 0; i < _pages.size(); ++i) {
00166         if (_pages[i].start != nullptr) {
00167             if (newSize != i)
00168                 _pages[newSize] = _pages[i];
00169             ++newSize;
00170         }
00171     }
00172     _pages.resize(newSize);
00173 
00174     // Reset _chunksPerPage
00175     _chunksPerPage = INITIAL_CHUNKS_PER_PAGE;
00176     for (size_t i = 0; i < _pages.size(); ++i) {
00177         if (_chunksPerPage < _pages[i].numChunks)
00178             _chunksPerPage = _pages[i].numChunks;
00179     }
00180 }
00181 
00182 } // End of namespace Common


Generated on Sat Feb 16 2019 05:00:57 for ResidualVM by doxygen 1.7.1
curved edge   curved edge