aboutsummaryrefslogtreecommitdiff
path: root/engines/tinsel/heapmem.cpp
blob: aff085d00355f65f571074d205841a7e4aeb0d84 (plain)
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
/* 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

namespace Tinsel {

// minimum memory required for MS-DOS version of game
#define	MIN_MEM 2506752L

// 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;

	// allocatea big chunk of memory
	const uint32 size = 2*MIN_MEM+655360L;
	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);

	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(int) - 1) & ~(sizeof(int) - 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