From 3410761714c70480c063112e5a184c93cae39bb3 Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Mon, 24 May 2021 17:02:29 +0200 Subject: Add experimental block based filesystem --- src/common.h | 7 +- src/filesystem.c | 361 +++++++++++++++++++++++++++++++++++++++++++------------ src/main.c | 39 +++++- 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++; } -- cgit v1.2.1