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
|
#include "memory.h"
/*
The 'heap' array is the global pool of memory from which pages are allocated
and deallocated, used by every Bedrock instance. The 'heap_index' array tracks
the owner of each page of memory: the value of each entry is the ID of the
instance that owns / has allocated the corresponding page in the heap. An ID
of zero indicates that the page is free / hasn't been allocated yet.
If multiple instances are repeatedly allocating and deallocating pages, it's
expected that the allocations will become very fragmented, with pages owned
by each instance interleaving with one another. To find the heap address that
corresponds with an allocated page address, the heap will need to be traversed,
which makes random access very expensive. To mitigate this, the heap address
of every page accessible from the current offset value (which determines the
base page to address from) is cached in an array of 256 pointers, and the
pointer corresponding with the current page is further cached as a pointer.
The 'unallocated' array acts as a sort of null page, with every access of an
unallocated page being routed instead to that page. This allows the read and
write methods to omit a test to check whether a page is allocated or not;
effectively, every page is always allocated. This is allowed because the
Bedrock specification says that an unallocated read or write causes undefined
behaviour, allowing us to optimise away the test.
TODO: If one instance allocates memory, then a second instance allocates memory,
then the first instance deallocates, then the second instance allocates some
more, the pages allocated to the second instance will be out of order, but the
code so far assumes that all pages are in the correct order (with gaps or not).
There needs to be either a page reordering pass (time expensive) or an array to
track the allocation order of pages for each instance (space expensive). The
former approach would be the best, because it's unlikely that this would be a
frequent occurrence. I'll need to shuffle pages around using memcpy and the null
page. Only touch the pages of the current instance, to avoid having to recalculate
the page caches of every instance. We can determine if pages will need to be
shuffled / defragmented by checking if an unallocated page is traversed before
the final allocated page is found.
*/
// Size of the heap in pages. The value was chosen by steadily increasing it
// until the emulator refused to compile, and then easing back a bit.
#define MAX_PAGES (12000)
// The heap.
static u8 heap[MAX_PAGES][256]; // the page heap.
// Null page to use for unallocated reads and writes.
static u8 unallocated[256];
// Map heap pages to instances. An ID of zero represents an unallocated page.
static u8 heap_index[MAX_PAGES];
// Reset a read-write head on the memory device.
void memory_head_reset(MemoryHead *head) {
head->offset = 0;
head->byte = 0;
head->point = (u8*) &unallocated;
head->page = 0;
for (int i=0; i<256; i++) head->cache[i] = (u8*) &unallocated;
}
// Reset the memory device.
void memory_reset(MemoryDevice *mem) {
mem->count = 0;
mem->copy = 0;
memory_allocate(mem);
memory_head_reset(&mem->head1);
memory_head_reset(&mem->head2);
}
// Read a byte from a memory head.
u8 memory_read(MemoryHead *head) {
u8 output = head->point[head->byte++];
if (head->byte == 0) {
head->page++;
memory_refresh_page(head);
}
return output;
}
// Write a byte to a memory head.
void memory_write(MemoryHead *head, u8 value) {
head->point[head->byte++] = value;
if (head->byte == 0) {
head->page++;
memory_refresh_page(head);
}
}
void memory_refresh_page(MemoryHead *head) {
head->point = head->cache[head->page];
}
// Recalculate the pointers stored in the page cache.
void memory_refresh_cache(MemoryDevice *mem, MemoryHead *head) {
// Point every page in the cache to the unallocated page.
for (int i=0; i<256; i++) head->cache[i] = (u8*) &unallocated;
// Iterate over every page in the heap, gather all pages allocated to
// this instance that belong to the current offset.
int n = 0;
int cache_i = 0;
for (int heap_i=0; heap_i<MAX_PAGES; heap_i++) {
if (heap_index[heap_i] == mem->id) {
if (n++ >= head->offset) {
head->cache[cache_i++] = (u8*) &heap[heap_i];
if (cache_i == 256) break;
}
}
}
}
// Allocate mem->count pages of memory.
void memory_allocate(MemoryDevice *mem) {
// Track how many pages have been allocated/deallocated so far.
int n = 0;
// Allocate memory.
if (mem->count > mem->allocated) {
int to_allocate = mem->count - mem->allocated;
for (int i=0; i<MAX_PAGES; i++) {
if (heap_index[i] == 0) {
heap_index[i] = mem->id;
if (++n == to_allocate) break;
}
}
// Deallocate memory.
} else if (mem->count < mem->allocated) {
for (int i=0; i<MAX_PAGES; i++) {
if (heap_index[i] == mem->id) {
if (++n > mem->count) {
// Clear the page when it's deallocated.
memset(heap[i], 0, 256);
heap_index[i] = 0;
}
}
}
}
// Re-count the number of pages allocated to this instance.
mem->allocated = 0;
for (int i=0; i<MAX_PAGES; i++) {
if (heap_index[i]==mem->id) mem->allocated++;
}
// Refresh the page caches for both heads.
memory_refresh_cache(mem, &mem->head1);
memory_refresh_cache(mem, &mem->head2);
}
// Copy mem->count pages from head 2 to head 1.
void memory_copy(MemoryDevice *mem) {
if (mem->head1.offset == mem->head2.offset) return;
for (int n=0; n<mem->copy; n++) {
if (mem->head1.cache[n] == (u8*) &unallocated) return;
if (mem->head2.cache[n] == (u8*) &unallocated) return;
memcpy(mem->head1.cache[n], mem->head2.cache[n], 256);
}
}
|
