Add experimental block based filesystem

3 files changed, 322 insertions, 85 deletions

diff --git a/src/common.h b/src/common.h
index 39f3ada..bfa3903 100644
--- a/src/common.h
+++ b/src/common.h
@@ -716,10 +716,13 @@ wait_vsync(void) {
 #define CLAMP(X, MIN, MAX) ((X) <= (MIN) ? (MIN) : (X) > (MAX) ? (MAX): (X))
 #define LEN(ARR) (sizeof(ARR) / sizeof((ARR)[0]))
 
-// IWRAM allocation macros for devkitARM.
-#define IWRAM_CODE __attribute__((section(".iwram"), long_call, target("arm")))
+//
+// Memory section macros for devkitARM.
+//
 #define IWRAM_DATA __attribute__((section(".iwram")))
+#define IWRAM_CODE __attribute__((section(".iwram"), long_call, target("arm")))
 #define EWRAM_DATA __attribute__((section(".ewram")))
+#define EWRAM_CODE __attribute__((section(".ewram"), long_call))
 #define EWRAM_BSS __attribute__((section(".sbss")))
 
 #endif // GBAEXP_COMMON_H
diff --git a/src/filesystem.c b/src/filesystem.c
index 6737386..4a55818 100644
--- a/src/filesystem.c
+++ b/src/filesystem.c
@@ -1,29 +1,68 @@
-// We need 64 * 32 bytes (2K) of SRAM for file indexes. To avoid corruption
-// issues we ignore the first file (32 bytes).
-// Note that the filename should include the null terminator if we want to use
-// strcmp.
-#define FILE_NAME_SIZE     27
-#define FILE_CAPACITY      4
-#define FILE_HEADER_OFFSET 2
-#define FILE_INDEX_OFFSET  32
-#define FILE_DATA_OFFSET   KB(2)
-#define FILE_MAX_SIZE      KB(16)
-#define SRAM               ((vu8*)(MEM_CART))
+// This file implements a filesystem with a minimum block size of 256 bytes. The
+// maximum number of files depends on the block size. The default 1KB block size
+// will give us 32-64 files depending on the size of MEM_CART. In case we want
+// to use a block size of 512 bytes, we will have up to 128 file available.
+// Blocks of 256 bytes will give us the maximum of 255 files available, since
+// a block index of 0xFF will be considered as a null block.
 
-typedef struct File {
-    char name[FILE_NAME_SIZE + 1];
+// A fileblock of 1KB give us a maximum of 64 files.
+#define FILE_BLOCK_SIZE KB(1)
+#define FILE_MAX_FILES  64
+#define FILE_N_BLOCKS   62
+
+// With this file name size sizeof(FileIndex) will be 32 bytes. 32 * 64 files
+// give us 2KB spent on file index that we can't use for data (so maximum of 62
+// files without accounting for the block index).
+#define FILE_NAME_SIZE  30
+#define FILE_INDEX_NUM  62
+
+// Since we are reserving the first 2K bytes for the filesystem, we have 60
+// blocks available for writing data. If you were to change the previous
+// parameters, you *must* recalculate the initial block start location.
+#define FILE_DATA_START KB(2)
+
+// We must write to the SRAM using the 8bit bus.
+#define SRAM ((vu8*)(MEM_CART))
+
+// Special filesystem constants.
+enum { FS_INIT_PATTERN = 0xBA, FS_NULL = 0xFF };
+
+typedef struct FileBlock {
+    // Size used in the current block (in bytes). Should be smaller than:
+    //     FILE_BLOCK_SIZE - sizeof(FileBlock)
     u16 size;
-    u16 mem_offset; // NOTE: Unused...
-} File;
+    // The index for the next block. Set to FS_NULL if there is none.
+    u8 next_block;
+    u8 prev_block;
+} FileBlock;
+
+typedef struct FileIndex {
+    // File name.
+    char name[FILE_NAME_SIZE + 1];
+    // Index to the first block of this file. If set to FS_NULL this file
+    // has not yet been written to.
+    u8 first_block;
+} FileIndex;
 
 // The filesystem header.
 typedef struct FileSystem {
-    u16 num_files;
-    u16 data_size; // NOTE: Unused...
-    u16 data_capacity; // NOTE: Unused...
-    File files[FILE_CAPACITY];
+    // The first byte of the SRAM can become corrupted in some situations, like
+    // changing cartridges for example.
+    u8 blank;
+    // If the filesystem exists, this will be set to FS_INIT_PATTERN.
+    u8 initialized;
+    // Number of blocks in use.
+    u8 busy_blocks;
+    // Number of files currently existing in the filesystem.
+    u8 num_files;
+    // This stores a bitmap pattern to keep track of the blocks in use by the
+    // filesystem. The first byte maps the first 8 blocks and so on.
+    u8 used_blocks[FILE_MAX_FILES / 8];
+    // The list of possible file indexes.
+    FileIndex files[FILE_INDEX_NUM];
 } FileSystem;
 
+EWRAM_BSS
 static FileSystem filesystem;
 
 void
@@ -41,114 +80,278 @@ _fs_write(u8 *src, size_t pos, size_t n_bytes) {
 }
 
 void
-fs_init() {
-    // Load header if existing.
-    _fs_read(&filesystem, FILE_HEADER_OFFSET, offsetof(FileSystem, files));
-    if (filesystem.num_files == 0xFFFF
-            && filesystem.data_capacity == 0xFFFF
-            && filesystem.data_size == 0xFFFF) {
+fs_init(void) {
+    // Load filesystem if existing.
+    _fs_read(&filesystem, 0, sizeof(FileSystem));
+    if (filesystem.initialized != FS_INIT_PATTERN) {
         // Clear SRAM.
-        for (size_t i = 0; i < KB(64); ++i) {
-            SRAM[i] = 0;
+        for (size_t i = 0; i < KB(64) / 8; ++i) {
+            SRAM[i] = 0x00;
+        }
+
+        // Initialize block headers.
+        FileBlock block = {
+            .size = 0,
+            .next_block = FS_NULL,
+            .prev_block = FS_NULL,
+        };
+        for (size_t i = 0; i < FILE_INDEX_NUM; ++i) {
+            size_t block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * i;
+            _fs_write(&block, block_pos, sizeof(FileBlock));
         }
 
         // Initialize filesystem.
-        filesystem.num_files = 0;
-        filesystem.data_size = 0;
-        filesystem.data_capacity = (u16)(FILE_CAPACITY * FILE_MAX_SIZE);
-        memset(&filesystem.files, 0, FILE_CAPACITY * sizeof(File));
-        _fs_write(&filesystem, FILE_HEADER_OFFSET, offsetof(FileSystem, files));
-    } else {
-        _fs_read(&filesystem.files, FILE_INDEX_OFFSET, sizeof(File) * filesystem.num_files);
+        memset(&filesystem, 0, sizeof(FileSystem));
+        filesystem.initialized = FS_INIT_PATTERN;
+        for (size_t i = 0; i < FILE_INDEX_NUM; ++i) {
+            filesystem.files[i].first_block = FS_NULL;
+        }
+
+        // Write the FS to disk.
+        _fs_write(&filesystem, 0, sizeof(FileSystem));
     }
 }
 
+void inline
+_fs_update_filesystem_header(void) {
+    _fs_write(&filesystem, 0, offsetof(FileSystem, files));
+};
+
+void inline
+_fs_update_file_index(u16 index) {
+    _fs_write(&filesystem.files[index],
+            offsetof(FileSystem, files) + index * sizeof(FileIndex),
+            sizeof(FileIndex));
+}
+
 typedef enum {
-    OPEN_READ,
-    OPEN_WRITE,
+    FS_OPEN_READ,
+    FS_OPEN_WRITE,
+    FS_OPEN_APPEND,
 } OpenMode;
 
-int
+typedef struct File {
+    u8 index;
+    u16 cur;
+    OpenMode mode;
+} File;
+
+File
 fs_open_file(char *name, OpenMode mode) {
     // Try to find an existing file.
     for (size_t i = 0; i < filesystem.num_files; ++i) {
         // TODO: Replace strcmp with vectorized fixed size char comparison.
         if (strcmp(name, filesystem.files[i].name) == 0) {
-            return i;
+            return (File){i, 0, mode};
         }
     }
 
-    if (mode == OPEN_READ) {
-        return -1;
+    if (mode == FS_OPEN_READ) {
+        return (File){FS_NULL, 0, mode};
     }
 
     // Create a new file if there is space.
-    if (filesystem.num_files < FILE_CAPACITY) {
+    if (filesystem.num_files < FILE_INDEX_NUM) {
         size_t index = filesystem.num_files++;
         size_t k = 0;
         while(*name) {
             filesystem.files[index].name[k++] = *name++;
         }
-        filesystem.files[index].size = 0;
-        filesystem.files[index].mem_offset = 0;
 
-        // Update file index.
-        _fs_write(&filesystem.files[index],
-                FILE_INDEX_OFFSET + index * sizeof(File),
-                sizeof(File));
+        // Update file index and filesystem on SRAM.
+        _fs_update_file_index(index);
+        _fs_update_filesystem_header();
 
-        // Update header.
-        _fs_write(&filesystem, FILE_HEADER_OFFSET, offsetof(FileSystem, files));
+        return (File){index, 0, mode};
+    }
+    return (File){FS_NULL, 0, mode};
+}
 
-        return index;
+u8
+_fs_init_new_block(void) {
+    // Find free block.
+    u8 block_index = 0;
+    for (size_t j = 0; j < LEN(filesystem.used_blocks); ++j) {
+        for (size_t i = 0; i < 8; ++i, block_index++) {
+            u8 blk = (filesystem.used_blocks[j] >> i) & 0x1;
+            if (blk == 0) {
+                // Initialize the block.
+                filesystem.busy_blocks++;
+                filesystem.used_blocks[j] |= (1 << i);
+                _fs_update_filesystem_header();
+                return block_index;
+            }
+        }
     }
-    return -1;
+    return FS_NULL;
 }
 
-size_t
-fs_write(u8 *src, size_t n_bytes, u16 file_index, u16 offset, bool append) {
-    File *file = &filesystem.files[file_index];
+#include "text.h"
 
-    // Check if there is enough capacity for this write operation.
-    if (offset + n_bytes >= FILE_MAX_SIZE) {
-        return 0;
+// Recursively free blocks starting at block_id. To improve performance, the
+// filesystem header is updated in memory but not written to disk. It is
+// responsability of the caller to perform the filesystem update.
+void
+_fs_free_blocks(u8 block_id) {
+    if (block_id == FS_NULL) {
+        return;
     }
 
-    // Write data to file block.
-    _fs_write(src, FILE_DATA_OFFSET + FILE_MAX_SIZE * file_index + offset, n_bytes);
+    // Read block.
+    FileBlock block;
+    size_t block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * block_id;
+    _fs_read(&block, block_pos, sizeof(FileBlock));
+
+    // Update block.
+    u8 next_block = block.next_block;
+    block = (FileBlock){
+        .size = 0,
+        .next_block =  FS_NULL,
+        .prev_block = FS_NULL,
+    };
+    _fs_write(&block, block_pos, sizeof(FileBlock));
+
+    // Update dirty and busy blocks.
+    filesystem.busy_blocks--;
+    filesystem.used_blocks[block_id / 8] &= ~(1 << (block_id % 8));
+
+    _fs_free_blocks(next_block);
+}
+
+// Write to block as a new file.
+void
+_fs_write_to_block(u8 *src, size_t n_bytes, u8 block_id, u8 prev_block) {
+    // Read initial block.
+    FileBlock block;
+    size_t block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * block_id;
+    _fs_read(&block, block_pos, sizeof(FileBlock));
+    u16 block_capacity = (FILE_BLOCK_SIZE - sizeof(FileBlock));
 
-    // Update file index.
-    if (append) {
-        if (offset + n_bytes > file->size) {
-            file->size = offset + n_bytes;
+    // Write capacity.
+    u16 block_bytes = MIN(block_capacity, n_bytes);
+    _fs_write(src, block_pos + sizeof(FileBlock), block_bytes);
+
+    if (n_bytes > block_capacity) {
+        if (block.next_block == FS_NULL) {
+            // Find new available block and initialize it.
+            block.next_block = _fs_init_new_block();
         }
+        _fs_write_to_block(
+                src + block_capacity,
+                n_bytes - block_capacity,
+                block.next_block,
+                block_id);
+    } else if (block.next_block != FS_NULL){
+        // Recursively free unused blocks.
+        _fs_free_blocks(block.next_block);
+        _fs_update_filesystem_header();
+        block.next_block = FS_NULL;
+    }
+
+    // Update block header.
+    if (prev_block != FS_NULL) {
+        block.prev_block = prev_block;
+    }
+    block.size = block_bytes;
+    _fs_write(&block, block_pos, sizeof(FileBlock));
+}
+
+// void
+// _fs_append_to_block(u8 *src, size_t n_bytes, u8 block_id, u8 prev_block) {
+//     // Read initial block.
+//     FileBlock block;
+//     size_t block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * block_id;
+//     _fs_read(&block, block_pos, sizeof(FileBlock));
+//     u16 block_capacity = (FILE_BLOCK_SIZE - sizeof(FileBlock)) - block.size;
+
+//     // Write capacity.
+//     u16 block_bytes = MIN(block_capacity, n_bytes);
+//     _fs_write(src, block_pos + sizeof(FileBlock), block_bytes);
+
+//     // txt_printf("cap: %d\n", block_capacity);
+//     // txt_printf("bytes: %d\n", n_bytes);
+//     // txt_printf("id: %d\n", block_id);
+//     if (n_bytes > block_capacity) {
+//         if (block.next_block == FS_NULL) {
+//             // Find new available block and initialize it.
+//             block.next_block = _fs_init_new_block();
+//             // TODO: Don't forget to set the block_prev of the next block as
+//             // this one.
+//         }
+//         _fs_write_to_block(
+//                 src + block_capacity,
+//                 n_bytes - block_capacity,
+//                 block.next_block,
+//                 block_id);
+//     }
+
+//     // Update block header.
+//     if (prev_block != FS_NULL) {
+//         block.prev_block = prev_block;
+//     }
+//     block.size += block_bytes;
+//     _fs_write(&block, block_pos, sizeof(FileBlock));
+// }
+
+size_t
+fs_write(u8 *src, size_t n_bytes, u16 offset, bool append, File *file) {
+    FileIndex *file_idx = &filesystem.files[file->index];
+    // TODO: Account for offset.
+
+    // If this is a new file.
+    if (file_idx->first_block == FS_NULL) {
+        // Check how many blocks will this write require and if we have enough
+        // available.
+        u16 blocks_required = n_bytes / (FILE_BLOCK_SIZE - sizeof(FileBlock));
+        u16 blocks_available = FILE_N_BLOCKS - filesystem.busy_blocks;
+        if (blocks_required > blocks_available) {
+            return 0;
+        }
+
+        // Find the first available block.
+        u8 block_id = _fs_init_new_block();
+        file_idx->first_block = block_id;
+
+        // Update file index on SRAM.
+        _fs_update_file_index(file->index);
     } else {
-        file->size = offset + n_bytes;
+        // TODO: Check how many blocks will this write require and if we have
+        // enough available.
     }
-    _fs_write(file, FILE_INDEX_OFFSET + file_index * sizeof(File), sizeof(File));
+    // txt_printf("id: %d", file_idx->first_block);
 
-    // Update header.
-    _fs_write(&filesystem, FILE_HEADER_OFFSET, offsetof(FileSystem, files));
+    // Write to block.
+    _fs_write_to_block(src, n_bytes, file_idx->first_block, FS_NULL);
+
+    // // Update file index.
+    // if (append) {
+    //     if (offset + n_bytes > file->size) {
+    //         file->size = offset + n_bytes;
+    //     }
+    // } else {
+    //     file->size = offset + n_bytes;
+    // }
+    // _fs_write(file, FILE_INDEX_OFFSET + file_index * sizeof(File), sizeof(File));
 
     return n_bytes;
 }
 
 size_t
-fs_read(u8 *dst, size_t n_bytes, u16 file_index, u16 offset) {
-    File *file = &filesystem.files[file_index];
+fs_read(u8 *dst, size_t n_bytes, u16 offset, File *file) {
+    // File *file = &filesystem.files[file_index];
 
-    // Check if the offset is within limits.
-    if (file->size == 0 || offset >= file->size - 1) {
-        return 0;
-    }
+    // // Check if the offset is within limits.
+    // if (file->size == 0 || offset >= file->size - 1) {
+    //     return 0;
+    // }
 
-    // Read as much as we can.
-    if (offset + n_bytes > file->size) {
-        n_bytes = file->size - offset;
-    }
+    // // Read as much as we can.
+    // if (offset + n_bytes > file->size) {
+    //     n_bytes = file->size - offset;
+    // }
 
-    // Copy n_bytes to destination.
-    _fs_read(dst, FILE_DATA_OFFSET + FILE_MAX_SIZE * file_index + offset, n_bytes);
+    // // Copy n_bytes to destination.
+    // _fs_read(dst, FILE_DATA_OFFSET + FILE_MAX_SIZE * file_index + offset, n_bytes);
 
     return n_bytes;
 }
diff --git a/src/main.c b/src/main.c
index e30035a..62030e5 100644
--- a/src/main.c
+++ b/src/main.c
@@ -124,13 +124,20 @@ file_talk(Device *d, u8 b0, u8 w) {
         u16 result = 0, length = mempeek16(d->dat, 0xa);
         u16 offset = mempeek16(d->dat, 0x4);
         u16 addr = mempeek16(d->dat, b0 - 1);
-        int file_idx = fs_open_file(name, read ? OPEN_READ : OPEN_WRITE);
-        if (file_idx >= 0) {
+        File file = fs_open_file(name, read ? FS_OPEN_READ : FS_OPEN_WRITE);
+        if (file.index != FS_NULL) {
+            txt_position(9, 9);
+            // TODO: Use file.cur pointer and fs_seek instead of offset.
+            // TODO: Remove append, that should be a write mode.
             if (read) {
-                result = fs_read(&d->mem[addr], length, file_idx, offset);
+                result = fs_read(&d->mem[addr], length, offset, &file);
             } else {
-                result = fs_write(&d->mem[addr], length, file_idx, offset, offset > 0);
+                result = fs_write(&d->mem[addr], length, offset, offset > 0, &file);
+                txt_printf("WROTE: %d\n", result);
             }
+        } else {
+            // txt_position(9, 9);
+            // txt_printf("NOT FOUND");
         }
                 mempoke16(d->dat, 0x2, result);
         }
@@ -353,14 +360,38 @@ int main(void) {
     txt_init(1, TEXT_LAYER);
     txt_position(0,0);
 
+    u8 test_data_a[1020];
+    u8 test_data_b[2038];
+    memset(&test_data_a, 0xAA, sizeof(test_data_a));
+    memset(&test_data_b, 0xbb, sizeof(test_data_b));
+
+    txt_position(0, 8);
+    File file_a = fs_open_file("file_a", FS_OPEN_WRITE);
+    File file_b = fs_open_file("file_b", FS_OPEN_WRITE);
+    fs_write(&test_data_b, sizeof(test_data_b), 0, 0, &file_a);
+    fs_write(&test_data_a, sizeof(test_data_a), 0, 0, &file_a);
+    // fs_write(&test_data_a, sizeof(test_data_a), 0, 0, &file_a);
+    // fs_write(&test_data_b, sizeof(test_data_b), 0, 0, &file_b);
+
     // Main loop.
     int frame_counter = 0;
     evaluxn(&u, 0x0100);
+    u32 flip_cycles = 0;
     while(true) {
         bios_vblank_wait();
+        profile_start();
         handle_input(&u);
+        u32 input_cycles = profile_stop();
+        profile_start();
         evaluxn(&u, mempeek16(devscreen->dat, 0));
+        u32 eval_cycles = profile_stop();
+        txt_position(0, 8);
+        // txt_printf("INPUT: %lu  \n", input_cycles);
+        // txt_printf("EVAL:  %lu  \n", eval_cycles);
+        // txt_printf("FLIP:  %lu  \n", flip_cycles);
+        profile_start();
         flipbuf(&ppu);
+        flip_cycles = profile_stop();
         frame_counter++;
     }