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