1 files changed, 123 insertions, 108 deletions

diff --git a/arm9/source/devices/memory.c b/arm9/source/devices/memory.c
index 915aec2..c9e86d7 100644
--- a/arm9/source/devices/memory.c
+++ b/arm9/source/devices/memory.c
@@ -1,143 +1,158 @@
-#include "nds.h"
 #include "memory.h"
 
-static u8 heap[HEAP_SIZE][256];  // the page heap.
-static u8 unallocated[256];      // page to use for all unallocated reads and writes.
-static u8 heap_index[HEAP_SIZE];
 
-u8 mem_read1(MemoryDevice *mem) {
-    u8 output = mem->point1[mem->byte1++];
-    if (mem->byte1 == 0) {
-        mem->page1++;
-        mem_get_page1(mem);
-    }
-    return output;
+/*
+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;
 }
 
-u8 mem_read2(MemoryDevice *mem) {
-    u8 output = mem->point2[mem->byte2++];
-    if (mem->byte2 == 0) {
-        mem->page2++;
-        mem_get_page2(mem);
-    }
-    return output;
+// 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);
 }
 
-void mem_write1(MemoryDevice *mem, u8 value) {
-    mem->point1[mem->byte1++] = value;
-    if (mem->byte1 == 0) {
-        mem->page1++;
-        mem_get_page1(mem);
+// 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;
 }
 
-void mem_write2(MemoryDevice *mem, u8 value) {
-    mem->point2[mem->byte2++] = value;
-    if (mem->byte2 == 0) {
-        mem->page2++;
-        mem_get_page2(mem);
+// 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 mem_load_cache1(MemoryDevice *mem) {
-    // Set all cached pointers to unallocated.
-    for (int i=0; i<256; i++) {
-        mem->cache1[i] = (u8*) &unallocated;
-    }
-    // Iterate over all heap pages, gather our ones.
-    int count = 0;
-    int cached = 0;
-    for (int i=0; i<HEAP_SIZE; i++) {
-        if (heap_index[i] == mem->id) {
-            if (count >= mem->offset1) {
-                mem->cache1[cached] = (u8*) &heap[i];
-                cached++;
-            }
-            count++;
-            if (cached == 256) break;
-        }
-    }
+void memory_refresh_page(MemoryHead *head) {
+    head->point = head->cache[head->page];
 }
 
-void mem_load_cache2(MemoryDevice *mem) {
-    // Set all cached pointers to unallocated.
-    for (int i=0; i<256; i++) {
-        mem->cache2[i] = (u8*) &unallocated;
-    }
-    // Iterate over all heap pages, gather our ones.
-    int count = 0;
-    int cached = 0;
-    for (int i=0; i<HEAP_SIZE; i++) {
-        if (heap_index[i] == mem->id) {
-            if (count >= mem->offset2) {
-                mem->cache2[cached] = (u8*) &heap[i];
-                cached++;
+// 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;
             }
-            count++;
-            if (cached == 256) break;
         }
     }
 }
 
-// Fetch the page1 pointer from cache1.
-void mem_get_page1(MemoryDevice *mem) {
-    mem->point1 = mem->cache1[mem->page1];
-}
-
-// Fetch the page2 pointer from cache2.
-void mem_get_page2(MemoryDevice *mem) {
-    mem->point2 = mem->cache2[mem->page2];
-}
-
-void mem_allocate(MemoryDevice *mem) {
-    int count = 0;
-
-    // ALLOCATING
-    if (mem->count_write > mem->count) {
-        int to_allocate = mem->count_write - mem->count;
-        for (int i=0; i<HEAP_SIZE; i++) {
+// 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;
-                count++;
-                if (count == to_allocate) {
-                    break;
-                }
+                if (++n == to_allocate) break;
             }
         }
-    // DEALLOCATING
-    } else if (mem->count_write < mem->count) {
-        for (int i=0; i<HEAP_SIZE; i++) {
+    // Deallocate memory.
+    } else if (mem->count < mem->allocated) {
+        for (int i=0; i<MAX_PAGES; i++) {
             if (heap_index[i] == mem->id) {
-                count++;
-                if (count > mem->count_write) {
-                    heap_index[i] = 0;
+                if (++n > mem->count) {
+                    // Clear the page when it's deallocated.
                     memset(heap[i], 0, 256);
+                    heap_index[i] = 0;
                 }
             }
         }
     }
-
-    // Count the number of pages allocated to us.
-    mem->count = 0;
-    for (int i=0; i<HEAP_SIZE; i++) {
-        if (heap_index[i]==mem->id) mem->count++;
+    // 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++;
     }
-    // Reload the pointer caches for each head.
-    mem_load_cache1(mem);
-    mem_load_cache2(mem);
+    // Refresh the page caches for both heads.
+    memory_refresh_cache(mem, &mem->head1);
+    memory_refresh_cache(mem, &mem->head2);
 }
 
-
-void mem_do_copy(MemoryDevice *mem) {
-    int src = mem->offset2;
-    int dest = mem->offset1;
-    if (src == dest) return;
-    for (int i=0; i<mem->copy_write; i++) {
-        if (src>=mem->count || dest>=mem->count) {
-            return;
-        }
-        memcpy(&heap[dest++], &heap[src++], 256);
+// 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);
     }
 }
-