1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
|
/* 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$
*
* This file contains the handle based Memory Manager code.
*/
#include "tinsel/heapmem.h"
#include "tinsel/timers.h" // For DwGetCurrentTime
#include "tinsel/tinsel.h"
namespace Tinsel {
// Specifies the total amount of memory required for DW1 demo, DW1, or DW2 respectively.
// Currently this is set at 5MB for the DW1 demo and DW1 and 10MB for DW2
// This could probably be reduced somewhat
// If the memory is not enough, the engine throws an "Out of memory" error in handle.cpp inside LockMem()
static const uint32 MemoryPoolSize[3] = {5 * 1024 * 1024, 5 * 1024 * 1024, 10 * 1024 * 1024};
// list of all memory nodes
MEM_NODE mnodeList[NUM_MNODES];
// pointer to the linked list of free mnodes
static MEM_NODE *pFreeMemNodes;
#ifdef DEBUG
// diagnostic mnode counters
static int numNodes;
static int maxNodes;
#endif
// the mnode heap sentinel
static MEM_NODE heapSentinel;
//
static MEM_NODE *AllocMemNode(void);
/**
* Initialises the memory manager.
*/
void MemoryInit(void) {
MEM_NODE *pNode;
#ifdef DEBUG
// clear number of nodes in use
numNodes = 0;
#endif
// place first node on free list
pFreeMemNodes = mnodeList;
// link all other objects after first
for (int i = 1; i < NUM_MNODES; i++) {
mnodeList[i - 1].pNext = mnodeList + i;
}
// null the last mnode
mnodeList[NUM_MNODES - 1].pNext = NULL;
// allocates a big chunk of memory
uint32 size = MemoryPoolSize[0];
if (TinselVersion == TINSEL_V1) size = MemoryPoolSize[1];
else if (TinselVersion == TINSEL_V2) size = MemoryPoolSize[2];
uint8 *mem = (uint8 *)malloc(size);
assert(mem);
// allocate a mnode for this memory
pNode = AllocMemNode();
// make sure mnode was allocated
assert(pNode);
// convert segment to memory address
pNode->pBaseAddr = mem;
// set size of the memory heap
pNode->size = size;
// clear the memory
memset(pNode->pBaseAddr, 0, size);
// set cyclic links to the sentinel
heapSentinel.pPrev = pNode;
heapSentinel.pNext = pNode;
pNode->pPrev = &heapSentinel;
pNode->pNext = &heapSentinel;
// flag sentinel as locked
heapSentinel.flags = DWM_LOCKED | DWM_SENTINEL;
}
#ifdef DEBUG
/**
* Shows the maximum number of mnodes used at once.
*/
void MemoryStats(void) {
printf("%i mnodes of %i used.\n", maxNodes, NUM_MNODES);
}
#endif
/**
* Allocate a mnode from the free list.
*/
static MEM_NODE *AllocMemNode(void) {
// get the first free mnode
MEM_NODE *pMemNode = pFreeMemNodes;
// make sure a mnode is available
assert(pMemNode); // Out of memory nodes
// the next free mnode
pFreeMemNodes = pMemNode->pNext;
// wipe out the mnode
memset(pMemNode, 0, sizeof(MEM_NODE));
#ifdef DEBUG
// one more mnode in use
if (++numNodes > maxNodes)
maxNodes = numNodes;
#endif
// return new mnode
return pMemNode;
}
/**
* Return a mnode back to the free list.
* @param pMemNode Node of the memory object
*/
void FreeMemNode(MEM_NODE *pMemNode) {
// validate mnode pointer
assert(pMemNode >= mnodeList && pMemNode <= mnodeList + NUM_MNODES - 1);
#ifdef DEBUG
// one less mnode in use
--numNodes;
assert(numNodes >= 0);
#endif
// place free list in mnode next
pMemNode->pNext = pFreeMemNodes;
// add mnode to top of free list
pFreeMemNodes = pMemNode;
}
/**
* Tries to make space for the specified number of bytes on the specified heap.
* @param size Number of bytes to free up
* @param bDiscard When set - will discard blocks to fullfill the request
*/
bool HeapCompact(long size, bool bDiscard) {
MEM_NODE *pHeap = &heapSentinel;
MEM_NODE *pPrev, *pCur, *pOldest;
long largest; // size of largest free block
uint32 oldest; // time of the oldest discardable block
while (true) {
bool bChanged;
do {
bChanged = false;
for (pPrev = pHeap->pNext, pCur = pPrev->pNext;
pCur != pHeap; pPrev = pCur, pCur = pCur->pNext) {
if (pPrev->flags == 0 && pCur->flags == 0) {
// set the changed flag
bChanged = true;
// both blocks are free - merge them
pPrev->size += pCur->size;
// unlink the current mnode
pPrev->pNext = pCur->pNext;
pCur->pNext->pPrev = pPrev;
// free the current mnode
FreeMemNode(pCur);
// leave the loop
break;
} else if ((pPrev->flags & (DWM_MOVEABLE | DWM_LOCKED | DWM_DISCARDED)) == DWM_MOVEABLE
&& pCur->flags == 0) {
// a free block after a moveable block - swap them
// set the changed flag
bChanged = true;
// move the unlocked blocks data up (can overlap)
memmove(pPrev->pBaseAddr + pCur->size,
pPrev->pBaseAddr, pPrev->size);
// swap the order in the linked list
pPrev->pPrev->pNext = pCur;
pCur->pNext->pPrev = pPrev;
pCur->pPrev = pPrev->pPrev;
pPrev->pPrev = pCur;
pPrev->pNext = pCur->pNext;
pCur->pNext = pPrev;
pCur->pBaseAddr = pPrev->pBaseAddr;
pPrev->pBaseAddr += pCur->size;
// leave the loop
break;
}
}
} while (bChanged);
// find the largest free block
for (largest = 0, pCur = pHeap->pNext; pCur != pHeap; pCur = pCur->pNext) {
if (pCur->flags == 0 && pCur->size > largest)
largest = pCur->size;
}
if (largest >= size)
// we have freed enough memory
return true;
if (!bDiscard)
// we cannot free enough without discarding blocks
return false;
// find the oldest discardable block
oldest = DwGetCurrentTime();
pOldest = NULL;
for (pCur = pHeap->pNext; pCur != pHeap; pCur = pCur->pNext) {
if ((pCur->flags & (DWM_DISCARDABLE | DWM_DISCARDED | DWM_LOCKED))
== DWM_DISCARDABLE) {
// found a non-discarded discardable block
if (pCur->lruTime < oldest) {
oldest = pCur->lruTime;
pOldest = pCur;
}
}
}
if (pOldest)
// discard the oldest block
MemoryDiscard(pOldest);
else
// cannot discard any blocks
return false;
}
}
/**
* Allocates the specified number of bytes from the heap.
* @param flags Allocation attributes
* @param size Number of bytes to allocate
*/
MEM_NODE *MemoryAlloc(int flags, long size) {
MEM_NODE *pHeap = &heapSentinel;
MEM_NODE *pNode;
bool bCompacted = true; // set when heap has been compacted
// compact the heap if we are allocating fixed memory
if (flags & DWM_FIXED) {
HeapCompact(MAX_INT, false);
}
#ifdef SCUMM_NEED_ALIGNMENT
const int alignPadding = sizeof(void*) - 1;
size = (size + alignPadding) & ~alignPadding; //round up to nearest multiple of sizeof(void*), this ensures the addresses that are returned are alignment-safe.
#endif
while ((flags & DWM_NOALLOC) == 0 && bCompacted) {
// search the heap for a free block
for (pNode = pHeap->pNext; pNode != pHeap; pNode = pNode->pNext) {
if (pNode->flags == 0 && pNode->size >= size) {
// a free block of the required size
pNode->flags = flags;
// update the LRU time
pNode->lruTime = DwGetCurrentTime() + 1;
if (pNode->size == size) {
// an exact fit
// check for zeroing the block
if (flags & DWM_ZEROINIT)
memset(pNode->pBaseAddr, 0, size);
if (flags & DWM_FIXED)
// lock the memory
return (MEM_NODE *)MemoryLock(pNode);
else
// just return the node
return pNode;
} else {
// allocate a node for the remainder of the free block
MEM_NODE *pTemp = AllocMemNode();
// calc size of the free block
long freeSize = pNode->size - size;
// set size of free block
pTemp->size = freeSize;
// set size of node
pNode->size = size;
if (flags & DWM_FIXED) {
// place the free node after pNode
pTemp->pBaseAddr = pNode->pBaseAddr + size;
pTemp->pNext = pNode->pNext;
pTemp->pPrev = pNode;
pNode->pNext->pPrev = pTemp;
pNode->pNext = pTemp;
// check for zeroing the block
if (flags & DWM_ZEROINIT)
memset(pNode->pBaseAddr, 0, size);
return (MEM_NODE *)MemoryLock(pNode);
} else {
// place the free node before pNode
pTemp->pBaseAddr = pNode->pBaseAddr;
pNode->pBaseAddr += freeSize;
pTemp->pNext = pNode;
pTemp->pPrev = pNode->pPrev;
pNode->pPrev->pNext = pTemp;
pNode->pPrev = pTemp;
// check for zeroing the block
if (flags & DWM_ZEROINIT)
memset(pNode->pBaseAddr, 0, size);
return pNode;
}
}
}
}
// compact the heap if we get to here
bCompacted = HeapCompact(size, (flags & DWM_NOCOMPACT) ? false : true);
}
// not allocated a block if we get to here
if (flags & DWM_DISCARDABLE) {
// chain a discarded node onto the end of the heap
pNode = AllocMemNode();
pNode->flags = flags | DWM_DISCARDED;
// set mnode at the end of the list
pNode->pPrev = pHeap->pPrev;
pNode->pNext = pHeap;
// fix links to this mnode
pHeap->pPrev->pNext = pNode;
pHeap->pPrev = pNode;
// return the discarded node
return pNode;
}
// could not allocate a block
return NULL;
}
/**
* Discards the specified memory object.
* @param pMemNode Node of the memory object
*/
void MemoryDiscard(MEM_NODE *pMemNode) {
// validate mnode pointer
assert(pMemNode >= mnodeList && pMemNode <= mnodeList + NUM_MNODES - 1);
// object must be discardable
assert(pMemNode->flags & DWM_DISCARDABLE);
// object cannot be locked
assert((pMemNode->flags & DWM_LOCKED) == 0);
if ((pMemNode->flags & DWM_DISCARDED) == 0) {
// allocate a free node to replace this node
MEM_NODE *pTemp = AllocMemNode();
// copy node data
memcpy(pTemp, pMemNode, sizeof(MEM_NODE));
// flag as a free block
pTemp->flags = 0;
// link in the free node
pTemp->pPrev->pNext = pTemp;
pTemp->pNext->pPrev = pTemp;
// discard the node
pMemNode->flags |= DWM_DISCARDED;
pMemNode->pBaseAddr = NULL;
pMemNode->size = 0;
// and place it at the end of the heap
while ((pTemp->flags & DWM_SENTINEL) != DWM_SENTINEL)
pTemp = pTemp->pNext;
// pTemp now points to the heap sentinel
// set mnode at the end of the list
pMemNode->pPrev = pTemp->pPrev;
pMemNode->pNext = pTemp;
// fix links to this mnode
pTemp->pPrev->pNext = pMemNode;
pTemp->pPrev = pMemNode;
}
}
/**
* Frees the specified memory object and invalidates its node.
* @param pMemNode Node of the memory object
*/
void MemoryFree(MEM_NODE *pMemNode) {
MEM_NODE *pPrev, *pNext;
// validate mnode pointer
assert(pMemNode >= mnodeList && pMemNode <= mnodeList + NUM_MNODES - 1);
// get pointer to the next mnode
pNext = pMemNode->pNext;
// get pointer to the previous mnode
pPrev = pMemNode->pPrev;
if (pPrev->flags == 0) {
// there is a previous free mnode
pPrev->size += pMemNode->size;
// unlink this mnode
pPrev->pNext = pNext; // previous to next
pNext->pPrev = pPrev; // next to previous
// free this mnode
FreeMemNode(pMemNode);
pMemNode = pPrev;
}
if (pNext->flags == 0) {
// the next mnode is free
pMemNode->size += pNext->size;
// flag as a free block
pMemNode->flags = 0;
// unlink the next mnode
pMemNode->pNext = pNext->pNext;
pNext->pNext->pPrev = pMemNode;
// free the next mnode
FreeMemNode(pNext);
}
}
/**
* Locks a memory object and returns a pointer to the first byte
* of the objects memory block.
* @param pMemNode Node of the memory object
*/
void *MemoryLock(MEM_NODE *pMemNode) {
// validate mnode pointer
assert(pMemNode >= mnodeList && pMemNode <= mnodeList + NUM_MNODES - 1);
// make sure memory object is not already locked
assert((pMemNode->flags & DWM_LOCKED) == 0);
// check for a discarded or null memory object
if ((pMemNode->flags & DWM_DISCARDED) || pMemNode->size == 0)
return NULL;
// set the lock flag
pMemNode->flags |= DWM_LOCKED;
// return memory objects base address
return pMemNode->pBaseAddr;
}
/**
* Changes the size or attributes of a specified memory object.
* @param pMemNode Node of the memory object
* @param size New size of block
* @param flags How to reallocate the object
*/
MEM_NODE *MemoryReAlloc(MEM_NODE *pMemNode, long size, int flags) {
MEM_NODE *pNew;
// validate mnode pointer
assert(pMemNode >= mnodeList && pMemNode <= mnodeList + NUM_MNODES - 1);
// validate the flags
// cannot be fixed and moveable
assert((flags & (DWM_FIXED | DWM_MOVEABLE)) != (DWM_FIXED | DWM_MOVEABLE));
// cannot be fixed and discardable
assert((flags & (DWM_FIXED | DWM_DISCARDABLE)) != (DWM_FIXED | DWM_DISCARDABLE));
// must be fixed or moveable
assert(flags & (DWM_FIXED | DWM_MOVEABLE));
// align the size to machine boundary requirements
size = (size + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
// validate the size
assert(size);
// make sure we want the node on the same heap
assert((flags & (DWM_SOUND | DWM_GRAPHIC)) == (pMemNode->flags & (DWM_SOUND | DWM_GRAPHIC)));
if (size == pMemNode->size) {
// must be just a change in flags
// update the nodes flags
pMemNode->flags = flags;
} else {
// unlink the mnode from the current heap
pMemNode->pNext->pPrev = pMemNode->pPrev;
pMemNode->pPrev->pNext = pMemNode->pNext;
// allocate a new node
pNew = MemoryAlloc((flags & ~DWM_FIXED) | DWM_MOVEABLE, size);
// make sure memory allocated
assert(pNew != NULL);
// update the nodes flags
pNew->flags = flags;
// copy the node to the current node
memcpy(pMemNode, pNew, sizeof(MEM_NODE));
// relink the mnode into the list
pMemNode->pPrev->pNext = pMemNode;
pMemNode->pNext->pPrev = pMemNode;
// free the new node
FreeMemNode(pNew);
}
if (flags & DWM_FIXED)
// lock the memory
return (MEM_NODE *)MemoryLock(pMemNode);
else
// just return the node
return pMemNode;
}
/**
* Unlocks a memory object.
* @param pMemNode Node of the memory object
*/
void MemoryUnlock(MEM_NODE *pMemNode) {
// validate mnode pointer
assert(pMemNode >= mnodeList && pMemNode <= mnodeList + NUM_MNODES - 1);
// make sure memory object is already locked
assert(pMemNode->flags & DWM_LOCKED);
// clear the lock flag
pMemNode->flags &= ~DWM_LOCKED;
// update the LRU time
pMemNode->lruTime = DwGetCurrentTime();
}
/**
* Retrieves the mnode associated with the specified pointer to a memory object.
* @param pMem Address of memory object
*/
MEM_NODE *MemoryHandle(void *pMem) {
MEM_NODE *pNode;
// search the DOS heap
for (pNode = heapSentinel.pNext; pNode != &heapSentinel; pNode = pNode->pNext) {
if (pNode->pBaseAddr == pMem)
// found it
return pNode;
}
// not found if we get to here
return NULL;
}
} // End of namespace Tinsel
|