1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #include "common/memorypool.h"
24 #include "common/util.h"
25
26 namespace Common {
27
28 enum {
29 INITIAL_CHUNKS_PER_PAGE = 8
30 };
31
adjustChunkSize(size_t chunkSize)32 static size_t adjustChunkSize(size_t chunkSize) {
33 // You must at least fit the pointer in the node (technically unneeded considering the next rounding statement)
34 chunkSize = MAX(chunkSize, sizeof(void *));
35 // There might be an alignment problem on some platforms when trying to load a void* on a non natural boundary
36 // so we round to the next sizeof(void *)
37 chunkSize = (chunkSize + sizeof(void *) - 1) & (~(sizeof(void *) - 1));
38
39 return chunkSize;
40 }
41
42
MemoryPool(size_t chunkSize)43 MemoryPool::MemoryPool(size_t chunkSize)
44 : _chunkSize(adjustChunkSize(chunkSize)) {
45
46 _next = nullptr;
47
48 _chunksPerPage = INITIAL_CHUNKS_PER_PAGE;
49 }
50
~MemoryPool()51 MemoryPool::~MemoryPool() {
52 #if 0
53 freeUnusedPages();
54 if (!_pages.empty())
55 warning("Memory leak found in pool");
56 #endif
57
58 for (size_t i = 0; i < _pages.size(); ++i)
59 ::free(_pages[i].start);
60 }
61
allocPage()62 void MemoryPool::allocPage() {
63 Page page;
64
65 // Allocate a new page
66 page.numChunks = _chunksPerPage;
67 assert(page.numChunks * _chunkSize < 16*1024*1024); // Refuse to allocate pages bigger than 16 MB
68
69 page.start = ::malloc(page.numChunks * _chunkSize);
70 assert(page.start);
71 _pages.push_back(page);
72
73
74 // Next time, we'll allocate a page twice as big as this one.
75 _chunksPerPage *= 2;
76
77 // Add the page to the pool of free chunk
78 addPageToPool(page);
79 }
80
addPageToPool(const Page & page)81 void MemoryPool::addPageToPool(const Page &page) {
82 // Add all chunks of the new page to the linked list (pool) of free chunks
83 void *current = page.start;
84 for (size_t i = 1; i < page.numChunks; ++i) {
85 void *next = (byte *)current + _chunkSize;
86 *(void **)current = next;
87
88 current = next;
89 }
90
91 // Last chunk points to the old _next
92 *(void **)current = _next;
93
94 // From now on, the first free chunk is the first chunk of the new page
95 _next = page.start;
96 }
97
allocChunk()98 void *MemoryPool::allocChunk() {
99 // No free chunks left? Allocate a new page
100 if (!_next)
101 allocPage();
102
103 assert(_next);
104 void *result = _next;
105 _next = *(void **)result;
106 return result;
107 }
108
freeChunk(void * ptr)109 void MemoryPool::freeChunk(void *ptr) {
110 // Add the chunk back to (the start of) the list of free chunks
111 *(void **)ptr = _next;
112 _next = ptr;
113 }
114
115 // Technically not compliant C++ to compare unrelated pointers. In practice...
isPointerInPage(void * ptr,const Page & page)116 bool MemoryPool::isPointerInPage(void *ptr, const Page &page) {
117 return (ptr >= page.start) && (ptr < (char *)page.start + page.numChunks * _chunkSize);
118 }
119
freeUnusedPages()120 void MemoryPool::freeUnusedPages() {
121 //std::sort(_pages.begin(), _pages.end());
122 Array<size_t> numberOfFreeChunksPerPage;
123 numberOfFreeChunksPerPage.resize(_pages.size());
124 for (size_t i = 0; i < numberOfFreeChunksPerPage.size(); ++i) {
125 numberOfFreeChunksPerPage[i] = 0;
126 }
127
128 // Compute for each page how many chunks in it are still in use.
129 void *iterator = _next;
130 while (iterator) {
131 // TODO: This should be a binary search (requiring us to keep _pages sorted)
132 for (size_t i = 0; i < _pages.size(); ++i) {
133 if (isPointerInPage(iterator, _pages[i])) {
134 ++numberOfFreeChunksPerPage[i];
135 break;
136 }
137 }
138
139 iterator = *(void **)iterator;
140 }
141
142 // Free all pages which are not in use.
143 size_t freedPagesCount = 0;
144 for (size_t i = 0; i < _pages.size(); ++i) {
145 if (numberOfFreeChunksPerPage[i] == _pages[i].numChunks) {
146 // Remove all chunks of this page from the list of free chunks
147 void **iter2 = &_next;
148 while (*iter2) {
149 if (isPointerInPage(*iter2, _pages[i]))
150 *iter2 = **(void ***)iter2;
151 else
152 iter2 = *(void ***)iter2;
153 }
154
155 ::free(_pages[i].start);
156 ++freedPagesCount;
157 _pages[i].start = nullptr;
158 }
159 }
160
161 // debug("freed %d pages out of %d", (int)freedPagesCount, (int)_pages.size());
162
163 // Remove all now unused pages
164 size_t newSize = 0;
165 for (size_t i = 0; i < _pages.size(); ++i) {
166 if (_pages[i].start != nullptr) {
167 if (newSize != i)
168 _pages[newSize] = _pages[i];
169 ++newSize;
170 }
171 }
172 _pages.resize(newSize);
173
174 // Reset _chunksPerPage
175 _chunksPerPage = INITIAL_CHUNKS_PER_PAGE;
176 for (size_t i = 0; i < _pages.size(); ++i) {
177 if (_chunksPerPage < _pages[i].numChunks)
178 _chunksPerPage = _pages[i].numChunks;
179 }
180 }
181
182 } // End of namespace Common
183