aboutsummaryrefslogtreecommitdiff
path: root/sword2/memory.cpp
blob: 5b01e0336445255394acd9b3eee4fd29631c1070 (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
/* Copyright (C) 1994-2004 Revolution Software Ltd
 *
 * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * $Header$
 */

// memory manager
//   - "remember, it's not good to leave memory locked for a moment longer
//      than necessary" Tony
//   - "actually, in a sequential system theoretically you never need to lock
//      any memory!" Chris ;)
//
// This is a very simple implementation but I see little advantage to being
// any cleverer with the coding - i could have put the mem blocks before the
// defined blocks instead of in an array and then used pointers to
// child/parent blocks. But why bother? I've Kept it simple. When it needs
// updating or customising it will be accessable to anyone who looks at it.
//
// Doesn't have a purgeable/age consituant yet - if anyone wants this then
// I'll add it in.

// MemMan v1.1

#include "common/stdafx.h"
#include "sword2/sword2.h"
#include "sword2/resman.h"

namespace Sword2 {

#define MEMORY_POOL (1024 * 12000)

// #define MEMDEBUG 1

MemoryManager::MemoryManager(Sword2Engine *vm) : _vm(vm) {
	uint32 j;
	uint8 *memory_base;

	_suggestedStart = 0;

	_totalFreeMemory = MEMORY_POOL;

	memory_base = (uint8 *) malloc(_totalFreeMemory);

	if (!memory_base)
		error("MemoryManager: couldn't malloc %d bytes", _totalFreeMemory);

	// the original malloc address
	_freeMemman = memory_base;

	// set all but first handle to unused
	for (j = 1; j < MAX_mem_blocks; j++)
		_memList[j].state = MEM_null;

	// total used (free, locked or floating)
	_totalBlocks = 1;

	_memList[0].ad = memory_base;
	_memList[0].state = MEM_free;
	_memList[0].age = 0;
	_memList[0].size = _totalFreeMemory;
	_memList[0].parent = -1;		// we are base - for now
	_memList[0].child = -1;			// we are the end as well
	_memList[0].uid = (uint32) UID_memman;		// init id

	_baseMemBlock = 0;			// for now
}

MemoryManager::~MemoryManager(void) {
	free(_freeMemman);
}

// I don't know about C++, but here's what "C: A Reference Manual" (Harbison &
// Steele) has to say:
//
// "There is no requirement in C that any of the integral types be large enough
// to represent a pointer, although C programmers often assume that type long
// is large enough, which it is on most computers. In C99, header inttypes.h
// may define integer types intptr_t and uintptr_t, which are guaranteed large
// enough to hold a pointer as an integer."
//
// The script engine frequently needs to pass around pointers to various
// structures etc. and, and used to do so by casting them to int32 and back
// again. Since those pointers always point to memory that belongs to the
// memory manager, we can easily represent them as offsets instead.

int32 MemoryManager::ptrToInt(const uint8 *p) {
	debug(9, "ptrToInt: %p -> %d", p, p - _freeMemman);

	if (p < _freeMemman || p >= &_freeMemman[MEMORY_POOL])
		warning("ptrToInt: Converting bad pointer: %p", p);

	return p - _freeMemman;
}

uint8 *MemoryManager::intToPtr(int32 n) {
	debug(9, "intToPtr: %d -> %p", n, &_freeMemman[n]);

	if (n < 0 || n >= MEMORY_POOL)
		warning("intToPtr: Converting bad integer: %d", n);

	return &_freeMemman[n];
}

Memory *MemoryManager::lowLevelAlloc(uint32 size, uint32 type, uint32 unique_id) {
	// allocate a block of memory - locked or float

	// returns 0 if fails to allocate the memory
	// or a pointer to a mem structure

	int32 nu_block;
	uint32 spawn = 0;
	uint32 slack;

	// we must first round the size UP to a dword, so subsequent blocks
	// will start dword alligned

	size += 3;		// move up
	size &= 0xfffffffc;	// and back down to boundary

	// find a free block large enough

	// the defragger returns when its made a big enough block. This is
	// a good time to defrag as we're probably not doing anything super
	// time-critical at the moment

	if ((nu_block = defragMemory(size)) == -1) {
		// error - couldn't find a big enough space
		return 0;
	}

	// an exact fit?
	if (_memList[nu_block].size == size) {
		// no new block is required as the fit is perfect
		_memList[nu_block].state = type;    // locked or float
		_memList[nu_block].size = size;	    // set to the required size
		_memList[nu_block].uid = unique_id; // an identifier

#ifdef	MEMDEBUG
		debugMemory();
#endif

		return &_memList[nu_block];
	}

	// nu_block is the free block to split, forming our locked/float block
	// with a new free block in any remaining space

	// If our child is free then is can expand downwards to eat up our
	// chopped space this is good because it doesn't create an extra block
	// so keeping the block count down.
	//
	// Why? Imagine you Talloc 1000k, then free it. Now keep allocating 10
	// bytes less and freeing again you end up with thousands of new free
	// mini blocks. This way avoids that as the free child keeps growing
	// downwards.

	if (_memList[nu_block].child != -1 && _memList[_memList[nu_block].child].state == MEM_free) {
		// our child is free
		// the spare memory is the blocks current size minus the
		// amount we're taking

		slack = _memList[nu_block].size - size;

		_memList[nu_block].state = type;    // locked or float
		_memList[nu_block].size = size;	    // set to the required size
		_memList[nu_block].uid = unique_id; // an identifier

		// child starts after us
		_memList[_memList[nu_block].child].ad = _memList[nu_block].ad + size;
		// child's size increases
		_memList[_memList[nu_block].child].size += slack;

		return &_memList[nu_block];
	}

	// otherwise we spawn a new block after us and before our child - our
	// child being a proper block that we cannot change

	// we remain a child of our parent
	// we spawn a new child and it inherits our current child

	// find a NULL slot for a new block

	while (_memList[spawn].state != MEM_null && spawn!=MAX_mem_blocks)
		spawn++;

	if (spawn == MAX_mem_blocks) {
		// run out of blocks - stop the program. this is a major blow
		// up and we need to alert the developer
		// Lets get a printout of this
		debugMemory();
		error("Out of mem blocks in Talloc()");
	}

	_memList[spawn].state = MEM_free;	// new block is free
	_memList[spawn].uid = (uint32) UID_memman;	// a memman created bloc

	// size of the existing parent free block minus the size of the new
	// space Talloc'ed.

	_memList[spawn].size = _memList[nu_block].size - size;

	// IOW the remaining memory is given to the new free block

	// we start 1 byte after the newly allocated block
	_memList[spawn].ad = _memList[nu_block].ad + size;

	// the spawned child gets it parent - the newly allocated block
	_memList[spawn].parent = nu_block;

	// the new child inherits the parents old child (we are its new
	// child "Waaaa")
	_memList[spawn].child = _memList[nu_block].child;

	// is the spawn the end block?
	if (_memList[spawn].child != -1) {
		// the child of the new free-spawn needs to know its new parent
		_memList[_memList[spawn].child].parent = spawn;
	}

	_memList[nu_block].state = type;	// locked or float
	_memList[nu_block].size = size;		// set to the required size
	_memList[nu_block].uid = unique_id;	// an identifier

	// the new blocks new child is the newly formed free block
	_memList[nu_block].child = spawn;

	//we've brought a new block into the world. Ahhh!
	_totalBlocks++;

#ifdef	MEMDEBUG
	debugMemory();
#endif

	return &_memList[nu_block];
}

void MemoryManager::freeMemory(Memory *block) {
	// kill a block of memory - which was presumably floating or locked
	// once you've done this the memory may be recycled

	block->state = MEM_free;
	block->uid = (uint32) UID_memman;	// belongs to the memory manager again

#ifdef	MEMDEBUG
	debugMemory();
#endif
}

void MemoryManager::floatMemory(Memory *block) {
	// set a block to float
	// wont be trashed but will move around in memory

	block->state = MEM_float;

#ifdef	MEMDEBUG
	debugMemory();
#endif
}

void MemoryManager::lockMemory(Memory *block) {
	// set a block to lock
	// wont be moved - don't lock memory for any longer than necessary
	// unless you know the locked memory is at the bottom of the heap

	// can't move now - this block is now crying out to be floated or
	// free'd again

	block->state = MEM_locked;

#ifdef	MEMDEBUG
	debugMemory();
#endif
}

int32 MemoryManager::defragMemory(uint32 req_size) {
	// moves floating blocks down and/or merges free blocks until a large
	// enough space is found or there is nothing left to do and a big
	// enough block cannot be found we stop when we find/create a large
	// enough block - this is enough defragging.

	int32 cur_block;	// block 0 remains the parent block
	int32 original_parent,child, end_child;
	uint32 j;
	uint32 *a;
	uint32 *b;

	// cur_block = _baseMemBlock;	//the mother of all parents
	cur_block = _suggestedStart;

	do {
		// is current block a free block?
		if (_memList[cur_block].state == MEM_free) {
			if (_memList[cur_block].size >= req_size) {
				// this block is big enough - return its id
				return cur_block;
			}

			// the child is the end block - stop if the next block
			// along is the end block
			if (_memList[cur_block].child == -1) {
				// no luck, couldn't find a big enough block
				return -1;
			}

			// current free block is too small, but if its child
			// is *also* free then merge the two together

			if (_memList[_memList[cur_block].child].state == MEM_free) {
				// ok, we nuke the child and inherit its child
				child = _memList[cur_block].child;

				// our size grows by the size of our child
				_memList[cur_block].size += _memList[child].size;

				// our new child is our old childs, child
				_memList[cur_block].child = _memList[child].child;

				// not if the chld we're nuking is the end
				// child (it has no child)

				if (_memList[child].child != -1) {
					// the (nuked) old childs childs
					// parent is now us
					_memList[_memList[child].child].parent = cur_block;
				}

				// clean up the nuked child, so it can be used
				// again
				_memList[child].state = MEM_null;

				_totalBlocks--;
			} else if (_memList[_memList[cur_block].child].state == MEM_float) {
				// current free block is too small, but if its
				// child is a float then we move the floating
				// memory block down and the free up but,
				// parent/child relationships must be such
				// that the memory is all continuous between
				// blocks. ie. a childs memory always begins 1
				// byte after its parent finishes. However, the
				// positions in the memory list may become
				// truly random, but, any particular block of
				// locked or floating memory must retain its
				// position within the _memList - the float
				// stays a float because the handle/pointer
				// has been passed back
				//
				// what this means is that when the physical
				// memory of the foat moves down (and the free
				// up) the child becomes the parent and the
				// parent the child but, remember, the parent
				// had a parent and the child another child -
				// these swap over too as the parent/child swap
				// takes place - phew.

				// our child is currently floating
				child = _memList[cur_block].child;

				// move the higher float down over the free
				// block
				// memcpy(_memList[cur_block].ad, _memList[child].ad, _memList[child].size);

				a = (uint32 *) _memList[cur_block].ad;
				b = (uint32 *) _memList[child].ad;

				for (j = 0; j < _memList[child].size / 4; j++)
					*(a++) = *(b++);

				// both *ad's change
				// the float is now where the free was and the
				// free goes up by the size of the float
				// (which has come down)

				_memList[child].ad = _memList[cur_block].ad;
				_memList[cur_block].ad += _memList[child].size;

				// the status of the _memList blocks must
				// remain the same, so...

				// our child gets this when we become its
				// child and it our parent
				original_parent = _memList[cur_block].parent;

				// the free's child becomes its parent
				_memList[cur_block].parent = child;

				// the new child inherits its previous childs
				// child
				_memList[cur_block].child = _memList[child].child;

				// save this - see next line
				end_child = _memList[child].child;

				// the floats parent becomes its child
				_memList[child].child = cur_block;
				_memList[child].parent = original_parent;

				// if the child had a child
				if (end_child != -1) {
					// then its parent is now the new child
					_memList[end_child].parent = cur_block;
				}

				// if the base block was the true base parent
				if (original_parent == -1) {
					// then the child that has moved down
					// becomes the base block as it sits
					// at the lowest possible memory
					// location
					_baseMemBlock = child;
				} else {
					// otherwise the parent of the current
					// free block - that is now the child
					// - gets a new child, that child
					// being previously the child of the
					// child of the original parent
					_memList[original_parent].child = child;
				}
			} else { // if (_memList[_memList[cur_block].child].state == MEM_lock)
				// the child of current is locked - move to it
				// move to next one along - either locked or
				// END
				cur_block=_memList[cur_block].child;
			}
		} else {
			// move to next one along, the current must be
			// floating, locked, or a NULL slot
			cur_block = _memList[cur_block].child;
		}
	} while (cur_block != -1);	// while the block we've just done is not the final block

	return -1;	//no luck, couldn't find a big enough block
}

void MemoryManager::debugMemory(void) {
	// gets called with lowLevelAlloc, Mem_free, Mem_lock & Mem_float if
	// MEMDEBUG has been #defined otherwise can be called at any time
	// anywhere else

	int j;
	char inf[][20] = {
		{ "MEM_null" },
		{ "MEM_free" },
		{ "MEM_locked" },
		{ "MEM_float" }
	};

	debug(5, "base %d total %d", _baseMemBlock, _totalBlocks);

	// first in mem list order
	for (j = 0; j < MAX_mem_blocks; j++) {
		if (_memList[j].state == MEM_null)
			debug(5, "%d- NULL", j);
		else
			debug(5, "%d- state %s, ad %p, size %d, p %d, c %d, id %d",
				j, inf[_memList[j].state], _memList[j].ad,
				_memList[j].size, _memList[j].parent,
				_memList[j].child, _memList[j].uid);
	}

	// now in child/parent order
	j = _baseMemBlock;
	do {
		debug(5, " %d- state %s, ad %p, size %d, p %d, c %d, id %d",
			j, inf[_memList[j].state], _memList[j].ad,
			_memList[j].size, _memList[j].parent,
			_memList[j].child, _memList[j].uid);

		j = _memList[j].child;
	} while (j != -1);
}

Memory *MemoryManager::allocMemory(uint32 size, uint32 type, uint32 unique_id) {
	// the high level allocator

	// can ask the resman to remove old resources to make space - will
	// either do it or halt the system

	Memory *membloc;
	int j;
	uint32 free = 0;

	while (virtualDefrag(size)) {
		// trash the oldest closed resource
		if (!_vm->_resman->helpTheAgedOut()) {
			error("alloc ran out of memory: size=%d type=%d unique_id=%d", size, type, unique_id);
		}
	}

	membloc = lowLevelAlloc(size, type, unique_id);

	if (membloc == 0) {
		error("lowLevelAlloc failed to get memory virtualDefrag said was there");
	}

	j = _baseMemBlock;
	do {

		if (_memList[j].state == MEM_free)
			free += _memList[j].size;

		j = _memList[j].child;
	} while (j != -1);

	// return the pointer to the memory
	return membloc;
}

// Maximum allowed wasted memory.
#define MAX_WASTAGE 51200

int32 MemoryManager::virtualDefrag(uint32 size) {
	// Virutually defrags memory...
	//
	// Used to determine if there is potentially are large enough free
	// block available is the real defragger was allowed to run.
	//
	// The idea being that alloc will call this and help_the_aged_out
	// until we indicate that it is possible to obtain a large enough
	// free block. This way the defragger need only run once to yield the
	// required block size.
	//
	// The reason for its current slowness is that the defragger is
	// potentially called several times, each time shifting upto 20Megs
	// around, to obtain the required free block.

	int32 cur_block;	
	uint32 currentBubbleSize = 0;

	cur_block = _baseMemBlock;
	_suggestedStart = _baseMemBlock;

	do {
		if (_memList[cur_block].state == MEM_free) {
			// Add a little intelligence. At the start the oldest
			// resources are at the bottom of the tube. However
			// there will be some air at the top. Thus bubbles
			// will be created at the bottom and float to the
			// top. If we ignore the top gap then a large enough
			// bubble will form lower down the tube. Thus less
			// memory will need to be shifted.

			if (_memList[cur_block].child != -1)
				currentBubbleSize += _memList[cur_block].size;
			else if (_memList[cur_block].size > MAX_WASTAGE)
				currentBubbleSize += _memList[cur_block].size;

			if (currentBubbleSize >= size)
				return 0;
		} else if (_memList[cur_block].state == MEM_locked) {
			currentBubbleSize = 0;
			// Any free block of the correct size will be above
			// this locked block.
			_suggestedStart = _memList[cur_block].child;
		}

		cur_block = _memList[cur_block].child;
	} while (cur_block != -1);	

	return 1;
}

} // End of namespace Sword2