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 * This file contains the handle based Memory Manager code.
22 */
23
24 #include "tinsel/heapmem.h"
25 #include "tinsel/timers.h" // For DwGetCurrentTime
26 #include "tinsel/tinsel.h"
27
28 namespace Tinsel {
29
30
31 #define NUM_MNODES 192 // the number of memory management nodes (was 128, then 192)
32
33
34 // internal allocation flags
35 #define DWM_USED 0x0001 ///< the objects memory block is in use
36 #define DWM_DISCARDED 0x0002 ///< the objects memory block has been discarded
37 #define DWM_LOCKED 0x0004 ///< the objects memory block is locked
38 #define DWM_SENTINEL 0x0008 ///< the objects memory block is a sentinel
39
40
41 struct MEM_NODE {
42 MEM_NODE *pNext; // link to the next node in the list
43 MEM_NODE *pPrev; // link to the previous node in the list
44 uint8 *pBaseAddr; // base address of the memory object
45 long size; // size of the memory object
46 uint32 lruTime; // time when memory object was last accessed
47 int flags; // allocation attributes
48 };
49
50
51 // Specifies the total amount of memory required for DW1 demo, DW1, or DW2 respectively.
52 // Currently this is set at 5MB for the DW1 demo and DW1 and 10MB for DW2
53 // This could probably be reduced somewhat
54 // If the memory is not enough, the engine throws an "Out of memory" error in handle.cpp inside LockMem()
55 static const uint32 MemoryPoolSize[4] = {5 * 1024 * 1024, 5 * 1024 * 1024, 10 * 1024 * 1024, 512 * 1024 * 1024};
56
57 // These vars are reset upon engine destruction
58
59 // list of all memory nodes
60 MEM_NODE g_mnodeList[NUM_MNODES];
61
62 // pointer to the linked list of free mnodes
63 static MEM_NODE *g_pFreeMemNodes;
64
65 // list of all fixed memory nodes
66 MEM_NODE g_s_fixedMnodesList[5];
67
68 // the mnode heap sentinel
69 static MEM_NODE g_heapSentinel;
70
71 //
72 static MEM_NODE *AllocMemNode();
73
74 #ifdef DEBUG
MemoryStats()75 static void MemoryStats() {
76 int usedNodes = 0;
77 int allocedNodes = 0;
78 int lockedNodes = 0;
79 int lockedSize = 0;
80 int totalSize = 0;
81
82 const MEM_NODE *pHeap = &g_heapSentinel;
83 MEM_NODE *pCur;
84
85 for (pCur = pHeap->pNext; pCur != pHeap; pCur = pCur->pNext) {
86 usedNodes++;
87 totalSize += pCur->size;
88 if (pCur->flags)
89 allocedNodes++;
90 if (pCur->flags & DWM_LOCKED) {
91 lockedNodes++;
92 lockedSize += pCur->size;
93 }
94 }
95
96 debug("%d nodes used, %d alloced, %d locked; %d bytes locked, %d used",
97 usedNodes, allocedNodes, lockedNodes, lockedSize, totalSize);
98 }
99 #endif
100
101 /**
102 * Initializes the memory manager.
103 */
MemoryInit()104 void MemoryInit() {
105 // place first node on free list
106 g_pFreeMemNodes = g_mnodeList;
107
108 // link all other objects after first
109 memset(g_mnodeList, 0, sizeof(g_mnodeList));
110 for (int i = 1; i < NUM_MNODES; i++) {
111 g_mnodeList[i - 1].pNext = g_mnodeList + i;
112 }
113
114 // null the last mnode
115 g_mnodeList[NUM_MNODES - 1].pNext = nullptr;
116
117 // clear list of fixed memory nodes
118 memset(g_s_fixedMnodesList, 0, sizeof(g_s_fixedMnodesList));
119
120 // set cyclic links to the sentinel
121 g_heapSentinel.pPrev = &g_heapSentinel;
122 g_heapSentinel.pNext = &g_heapSentinel;
123
124 // flag sentinel as locked
125 g_heapSentinel.flags = DWM_LOCKED | DWM_SENTINEL;
126
127 // store the current heap size in the sentinel
128 uint32 size = MemoryPoolSize[0];
129 if (TinselVersion == TINSEL_V1) size = MemoryPoolSize[1];
130 else if (TinselVersion == TINSEL_V2) size = MemoryPoolSize[2];
131 else if (TinselVersion == TINSEL_V3) {
132 warning("TODO: Find the correct memory pool size for Noir, using 512 MiB for now");
133 size = MemoryPoolSize[3];
134 }
135 g_heapSentinel.size = size;
136 }
137
138 /**
139 * Deinitializes the memory manager.
140 */
MemoryDeinit()141 void MemoryDeinit() {
142 const MEM_NODE *pHeap = &g_heapSentinel;
143 MEM_NODE *pCur;
144
145 pCur = g_s_fixedMnodesList;
146 for (int i = 0; i < ARRAYSIZE(g_s_fixedMnodesList); ++i, ++pCur) {
147 free(pCur->pBaseAddr);
148 pCur->pBaseAddr = 0;
149 }
150
151 for (pCur = pHeap->pNext; pCur != pHeap; pCur = pCur->pNext) {
152 free(pCur->pBaseAddr);
153 pCur->pBaseAddr = 0;
154 }
155
156 memset(g_mnodeList, 0, sizeof(g_mnodeList));
157 memset(g_s_fixedMnodesList, 0, sizeof(g_s_fixedMnodesList));
158 g_pFreeMemNodes = nullptr;
159 }
160
161
162 /**
163 * Allocate a mnode from the free list.
164 */
AllocMemNode()165 static MEM_NODE *AllocMemNode() {
166 // get the first free mnode
167 MEM_NODE *pMemNode = g_pFreeMemNodes;
168
169 // make sure a mnode is available
170 assert(pMemNode); // Out of memory nodes
171
172 // the next free mnode
173 g_pFreeMemNodes = pMemNode->pNext;
174
175 // wipe out the mnode
176 memset(pMemNode, 0, sizeof(MEM_NODE));
177
178 // return new mnode
179 return pMemNode;
180 }
181
182 /**
183 * Return a mnode back to the free list.
184 * @param pMemNode Node of the memory object
185 */
FreeMemNode(MEM_NODE * pMemNode)186 void FreeMemNode(MEM_NODE *pMemNode) {
187 // validate mnode pointer
188 assert(pMemNode >= g_mnodeList && pMemNode <= g_mnodeList + NUM_MNODES - 1);
189
190 // place free list in mnode next
191 pMemNode->pNext = g_pFreeMemNodes;
192
193 // add mnode to top of free list
194 g_pFreeMemNodes = pMemNode;
195 }
196
197
198 /**
199 * Tries to make space for the specified number of bytes on the specified heap.
200 * @param size Number of bytes to free up
201 * @return true if any blocks were discarded, false otherwise
202 */
HeapCompact(long size)203 static bool HeapCompact(long size) {
204 const MEM_NODE *pHeap = &g_heapSentinel;
205 MEM_NODE *pCur, *pOldest;
206 uint32 oldest; // time of the oldest discardable block
207
208 while (g_heapSentinel.size < size) {
209
210 // find the oldest discardable block
211 oldest = DwGetCurrentTime();
212 pOldest = nullptr;
213 for (pCur = pHeap->pNext; pCur != pHeap; pCur = pCur->pNext) {
214 if (pCur->flags == DWM_USED) {
215 // found a non-discarded discardable block
216 if (pCur->lruTime < oldest) {
217 oldest = pCur->lruTime;
218 pOldest = pCur;
219 }
220 }
221 }
222
223 if (pOldest)
224 // discard the oldest block
225 MemoryDiscard(pOldest);
226 else
227 // cannot discard any blocks
228 return false;
229 }
230
231 // we have freed enough memory
232 return true;
233 }
234
235 /**
236 * Allocates the specified number of bytes from the heap.
237 * @param flags Allocation attributes
238 * @param size Number of bytes to allocate
239 */
MemoryAlloc(long size)240 static MEM_NODE *MemoryAlloc(long size) {
241 MEM_NODE *pHeap = &g_heapSentinel;
242
243 #ifdef SCUMM_NEED_ALIGNMENT
244 const int alignPadding = sizeof(void *) - 1;
245 size = (size + alignPadding) & ~alignPadding; //round up to nearest multiple of sizeof(void *), this ensures the addresses that are returned are alignment-safe.
246 #endif
247
248 // compact the heap to make up room for 'size' bytes, if necessary
249 if (!HeapCompact(size))
250 return 0;
251
252 // success! we may allocate a new node of the right size
253
254 // Allocate a node.
255 MEM_NODE *pNode = AllocMemNode();
256
257 // Allocate memory for the node.
258 pNode->pBaseAddr = (byte *)malloc(size);
259
260 // Verify that we got the memory.
261 // TODO: If this fails, we should first try to compact the heap some further.
262 assert(pNode->pBaseAddr);
263
264 // Subtract size of new block from total
265 g_heapSentinel.size -= size;
266
267 #ifdef DEBUG
268 MemoryStats();
269 #endif
270
271 // Set flags, LRU time and size
272 pNode->flags = DWM_USED;
273 pNode->lruTime = DwGetCurrentTime() + 1;
274 pNode->size = size;
275
276 // set mnode at the end of the list
277 pNode->pPrev = pHeap->pPrev;
278 pNode->pNext = pHeap;
279
280 // fix links to this mnode
281 pHeap->pPrev->pNext = pNode;
282 pHeap->pPrev = pNode;
283
284 return pNode;
285 }
286
287 /**
288 * Allocate a discarded MEM_NODE. Actual memory can be assigned to it
289 * by using MemoryReAlloc().
290 */
MemoryNoAlloc()291 MEM_NODE *MemoryNoAlloc() {
292 MEM_NODE *pHeap = &g_heapSentinel;
293
294 // chain a discarded node onto the end of the heap
295 MEM_NODE *pNode = AllocMemNode();
296 pNode->flags = DWM_USED | DWM_DISCARDED;
297 pNode->lruTime = DwGetCurrentTime();
298 pNode->size = 0;
299
300 // set mnode at the end of the list
301 pNode->pPrev = pHeap->pPrev;
302 pNode->pNext = pHeap;
303
304 // fix links to this mnode
305 pHeap->pPrev->pNext = pNode;
306 pHeap->pPrev = pNode;
307
308 // return the discarded node
309 return pNode;
310 }
311
312 /**
313 * Allocate a fixed block of data.
314 * @todo We really should keep track of the allocated pointers,
315 * so that we can discard them later on, when the engine quits.
316 */
MemoryAllocFixed(long size)317 MEM_NODE *MemoryAllocFixed(long size) {
318
319 #ifdef SCUMM_NEED_ALIGNMENT
320 const int alignPadding = sizeof(void *) - 1;
321 size = (size + alignPadding) & ~alignPadding; //round up to nearest multiple of sizeof(void *), this ensures the addresses that are returned are alignment-safe.
322 #endif
323
324 // Search for a free entry in s_fixedMnodesList
325 MEM_NODE *pNode = g_s_fixedMnodesList;
326 for (int i = 0; i < ARRAYSIZE(g_s_fixedMnodesList); ++i, ++pNode) {
327 if (!pNode->pBaseAddr) {
328 pNode->pNext = 0;
329 pNode->pPrev = 0;
330 pNode->pBaseAddr = (byte *)malloc(size);
331 pNode->size = size;
332 pNode->lruTime = DwGetCurrentTime() + 1;
333 pNode->flags = DWM_USED;
334
335 // Subtract size of new block from total
336 g_heapSentinel.size -= size;
337
338 return pNode;
339 }
340 }
341
342 return 0;
343 }
344
345
346 /**
347 * Discards the specified memory object.
348 * @param pMemNode Node of the memory object
349 */
MemoryDiscard(MEM_NODE * pMemNode)350 void MemoryDiscard(MEM_NODE *pMemNode) {
351 // validate mnode pointer
352 assert(pMemNode >= g_mnodeList && pMemNode <= g_mnodeList + NUM_MNODES - 1);
353
354 // object must be in use and locked
355 assert((pMemNode->flags & (DWM_USED | DWM_LOCKED)) == DWM_USED);
356
357 // discard it if it isn't already
358 if ((pMemNode->flags & DWM_DISCARDED) == 0) {
359 // free memory
360 free(pMemNode->pBaseAddr);
361 g_heapSentinel.size += pMemNode->size;
362
363 #ifdef DEBUG
364 MemoryStats();
365 #endif
366
367 // mark the node as discarded
368 pMemNode->flags |= DWM_DISCARDED;
369 pMemNode->pBaseAddr = nullptr;
370 pMemNode->size = 0;
371 }
372 }
373
374 /**
375 * Locks a memory object and returns a pointer to the first byte
376 * of the objects memory block.
377 * @param pMemNode Node of the memory object
378 */
MemoryLock(MEM_NODE * pMemNode)379 void *MemoryLock(MEM_NODE *pMemNode) {
380 // make sure memory object is not already locked
381 assert((pMemNode->flags & DWM_LOCKED) == 0);
382
383 // check for a discarded or null memory object
384 if ((pMemNode->flags & DWM_DISCARDED) || pMemNode->size == 0)
385 return NULL;
386
387 // set the lock flag
388 pMemNode->flags |= DWM_LOCKED;
389
390 #ifdef DEBUG
391 MemoryStats();
392 #endif
393
394 // return memory objects base address
395 return pMemNode->pBaseAddr;
396 }
397
398 /**
399 * Unlocks a memory object.
400 * @param pMemNode Node of the memory object
401 */
MemoryUnlock(MEM_NODE * pMemNode)402 void MemoryUnlock(MEM_NODE *pMemNode) {
403 // make sure memory object is already locked
404 assert(pMemNode->flags & DWM_LOCKED);
405
406 // clear the lock flag
407 pMemNode->flags &= ~DWM_LOCKED;
408
409 #ifdef DEBUG
410 MemoryStats();
411 #endif
412
413 // update the LRU time
414 pMemNode->lruTime = DwGetCurrentTime();
415 }
416
417 /**
418 * Changes the size of a specified memory object and re-allocate it if necessary.
419 * @param pMemNode Node of the memory object
420 * @param size New size of block
421 */
MemoryReAlloc(MEM_NODE * pMemNode,long size)422 void MemoryReAlloc(MEM_NODE *pMemNode, long size) {
423 MEM_NODE *pNew;
424
425 // validate mnode pointer
426 assert(pMemNode >= g_mnodeList && pMemNode <= g_mnodeList + NUM_MNODES - 1);
427
428 // align the size to machine boundary requirements
429 size = (size + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
430
431 // validate the size
432 assert(size);
433
434 if (size != pMemNode->size) {
435 // make sure memory object is discarded and not locked
436 assert(pMemNode->flags == (DWM_USED | DWM_DISCARDED));
437 assert(pMemNode->size == 0);
438
439 // unlink the mnode from the current heap
440 pMemNode->pNext->pPrev = pMemNode->pPrev;
441 pMemNode->pPrev->pNext = pMemNode->pNext;
442
443 // allocate a new node
444 pNew = MemoryAlloc(size);
445
446 // make sure memory allocated
447 assert(pNew != NULL);
448
449 // copy the node to the current node
450 memcpy(pMemNode, pNew, sizeof(MEM_NODE));
451
452 // relink the mnode into the list
453 pMemNode->pPrev->pNext = pMemNode;
454 pMemNode->pNext->pPrev = pMemNode;
455
456 // free the new node
457 FreeMemNode(pNew);
458 }
459
460 assert(pMemNode->pBaseAddr);
461 }
462
463 /**
464 * Touch a memory object by updating its LRU time.
465 * @param pMemNode Node of the memory object
466 */
MemoryTouch(MEM_NODE * pMemNode)467 void MemoryTouch(MEM_NODE *pMemNode) {
468 // update the LRU time
469 pMemNode->lruTime = DwGetCurrentTime();
470 }
471
MemoryDeref(MEM_NODE * pMemNode)472 uint8 *MemoryDeref(MEM_NODE *pMemNode) {
473 return pMemNode->pBaseAddr;
474 }
475
476
477 } // End of namespace Tinsel
478