menios
menios copied to clipboard
pbalduino
Implement ext2 filesystem support
Goal
Implement ext2 (Second Extended Filesystem) read and write support for meniOS, providing a more robust and feature-rich filesystem option alongside FAT32.
Context
ext2 is a widely-used Linux filesystem that offers better features than FAT32, including:
- POSIX permissions (user/group/other, rwx)
- Symbolic and hard links
- File ownership (UID/GID)
- Better metadata support
- Improved reliability with journaling preparation (ext3/ext4 path)
ext2 support will enable meniOS to:
- Mount and use Linux-formatted partitions
- Support proper UNIX file permissions
- Enable future ext3/ext4 upgrades
- Provide a native Linux filesystem experience
Dependencies
Required (Blocking)
- #65 - VFS layer ✅ COMPLETE
- #62 - Block device driver ✅ COMPLETE
- #63 - Block cache ✅ COMPLETE
- #96 - File descriptor management (for file operations)
Optional (Performance/Features)
- #60 - Filesystem syscalls (open, read, write, etc.)
- User/Group management (UID/GID support) - future
Blocks (Downstream)
- #154 - ext2 read-only support (subset of this issue)
- #228 - Dual partition mount (FAT32 /boot + ext2 /)
- #229 - Migrate /bin utilities to ext2
Priority
Medium - Important for proper UNIX filesystem support, but not blocking critical milestones
Justification
- Provides POSIX permissions, ownership, and symbolic links
- Enables proper Linux filesystem layout
- Not blocking Doom or GCC milestones immediately
- FAT32 is functional for current needs
- Nice upgrade path for future features
Implementation Phases
Phase 1: Read-Only Core (2-3 weeks) → Issue #154
- Superblock reading and validation
- Block group descriptor parsing
- Inode reading
- Direct block support
- Basic directory traversal
- File reading (small files)
Phase 2: Indirect Blocks (1 week)
- Single indirect block support
- Double indirect block support
- Triple indirect block support
- Large file reading (>48KB, up to 4GB)
Phase 3: Write Support (2-3 weeks)
- Block allocation (bitmap management)
- Inode allocation
- File creation and writing
- Directory creation
- Basic metadata updates
Phase 4: Full Operations (2 weeks)
- File/directory deletion
- Hard link support
- Symbolic link support
- Permission management
- Truncation and resize
Phase 5: Reliability (1-2 weeks)
- Error handling and recovery
- Sync operations
- Consistency checks
- Stress testing
Total Estimated: 8-11 weeks
Definition of Done
- ext2 detection: Recognize ext2 superblock and validate filesystem
- Read support: Read files, directories, inodes, block groups
- Write support: Create, modify, delete files and directories
- Directory operations: Create, list, remove directories
- Inode management: Allocate, free, update inodes
- Block allocation: Bitmap-based block allocation and freeing
- Metadata: Support permissions, ownership, timestamps
- Links: Hard links and symbolic links
- Integration: VFS layer integration with mount/umount
ext2 Filesystem Structure
Superblock
// ext2 superblock (located at offset 1024)
struct ext2_superblock {
uint32_t s_inodes_count; // Total inodes count
uint32_t s_blocks_count; // Total blocks count
uint32_t s_r_blocks_count; // Reserved blocks count
uint32_t s_free_blocks_count; // Free blocks count
uint32_t s_free_inodes_count; // Free inodes count
uint32_t s_first_data_block; // First data block
uint32_t s_log_block_size; // Block size (1024 << s_log_block_size)
uint32_t s_log_frag_size; // Fragment size
uint32_t s_blocks_per_group; // Blocks per group
uint32_t s_frags_per_group; // Fragments per group
uint32_t s_inodes_per_group; // Inodes per group
uint32_t s_mtime; // Mount time
uint32_t s_wtime; // Write time
uint16_t s_mnt_count; // Mount count
uint16_t s_max_mnt_count; // Maximal mount count
uint16_t s_magic; // Magic signature (0xEF53)
uint16_t s_state; // Filesystem state
uint16_t s_errors; // Behavior on errors
uint16_t s_minor_rev_level; // Minor revision level
uint32_t s_lastcheck; // Time of last check
uint32_t s_checkinterval; // Max time between checks
uint32_t s_creator_os; // OS
uint32_t s_rev_level; // Revision level
uint16_t s_def_resuid; // Default reserved UID
uint16_t s_def_resgid; // Default reserved GID
// Extended fields for revision 1+
uint32_t s_first_ino; // First non-reserved inode
uint16_t s_inode_size; // Inode size
// ... additional fields
};
#define EXT2_SUPER_MAGIC 0xEF53
#define EXT2_VALID_FS 1
#define EXT2_ERROR_FS 2
Block Group Descriptor
// Block group descriptor
struct ext2_group_desc {
uint32_t bg_block_bitmap; // Block bitmap block
uint32_t bg_inode_bitmap; // Inode bitmap block
uint32_t bg_inode_table; // Inode table block
uint16_t bg_free_blocks_count; // Free blocks count
uint16_t bg_free_inodes_count; // Free inodes count
uint16_t bg_used_dirs_count; // Directories count
uint16_t bg_pad; // Padding
uint32_t bg_reserved[3]; // Reserved
};
// Calculate number of block groups
uint32_t block_groups = (sb->s_blocks_count + sb->s_blocks_per_group - 1)
/ sb->s_blocks_per_group;
Inode Structure
// ext2 inode structure
struct ext2_inode {
uint16_t i_mode; // File mode
uint16_t i_uid; // Owner UID
uint32_t i_size; // Size in bytes
uint32_t i_atime; // Access time
uint32_t i_ctime; // Creation time
uint32_t i_mtime; // Modification time
uint32_t i_dtime; // Deletion time
uint16_t i_gid; // Group GID
uint16_t i_links_count; // Hard links count
uint32_t i_blocks; // Blocks count (512-byte blocks)
uint32_t i_flags; // File flags
uint32_t i_osd1; // OS dependent 1
uint32_t i_block[15]; // Block pointers
uint32_t i_generation; // File version (for NFS)
uint32_t i_file_acl; // File ACL
uint32_t i_dir_acl; // Directory ACL / file size high
uint32_t i_faddr; // Fragment address
uint8_t i_osd2[12]; // OS dependent 2
};
// i_mode flags
#define EXT2_S_IFSOCK 0xC000 // Socket
#define EXT2_S_IFLNK 0xA000 // Symbolic link
#define EXT2_S_IFREG 0x8000 // Regular file
#define EXT2_S_IFBLK 0x6000 // Block device
#define EXT2_S_IFDIR 0x4000 // Directory
#define EXT2_S_IFCHR 0x2000 // Character device
#define EXT2_S_IFIFO 0x1000 // FIFO
// Permission bits
#define EXT2_S_IRUSR 0x0100 // User read
#define EXT2_S_IWUSR 0x0080 // User write
#define EXT2_S_IXUSR 0x0040 // User execute
#define EXT2_S_IRGRP 0x0020 // Group read
#define EXT2_S_IWGRP 0x0010 // Group write
#define EXT2_S_IXGRP 0x0008 // Group execute
#define EXT2_S_IROTH 0x0004 // Others read
#define EXT2_S_IWOTH 0x0002 // Others write
#define EXT2_S_IXOTH 0x0001 // Others execute
Directory Entry
// Directory entry structure
struct ext2_dir_entry {
uint32_t inode; // Inode number
uint16_t rec_len; // Directory entry length
uint8_t name_len; // Name length
uint8_t file_type; // File type
char name[]; // File name (variable length)
};
// File types
#define EXT2_FT_UNKNOWN 0 // Unknown
#define EXT2_FT_REG_FILE 1 // Regular file
#define EXT2_FT_DIR 2 // Directory
#define EXT2_FT_CHRDEV 3 // Character device
#define EXT2_FT_BLKDEV 4 // Block device
#define EXT2_FT_FIFO 5 // FIFO
#define EXT2_FT_SOCK 6 // Socket
#define EXT2_FT_SYMLINK 7 // Symbolic link
Core Implementation
Filesystem Operations
// ext2 filesystem driver
struct filesystem_type ext2_fs_type = {
.name = "ext2",
.mount = ext2_mount,
.unmount = ext2_unmount,
};
// Mount ext2 filesystem
struct superblock *ext2_mount(struct block_device *bdev, uint32_t flags);
int ext2_unmount(struct superblock *sb);
int ext2_read_super(struct block_device *bdev, struct ext2_superblock *sb);
int ext2_validate_super(struct ext2_superblock *sb);
Inode Operations
// Inode operations
struct inode *ext2_inode_get(struct superblock *sb, uint32_t ino);
int ext2_inode_read(struct superblock *sb, uint32_t ino, struct ext2_inode *inode);
int ext2_inode_write(struct superblock *sb, uint32_t ino, struct ext2_inode *inode);
int ext2_inode_alloc(struct superblock *sb, uint32_t *ino);
int ext2_inode_free(struct superblock *sb, uint32_t ino);
int ext2_inode_update_times(struct inode *inode);
// Calculate inode location
uint32_t get_inode_block_group(struct ext2_superblock *sb, uint32_t ino);
uint32_t get_inode_index(struct ext2_superblock *sb, uint32_t ino);
uint32_t get_inode_block(struct ext2_superblock *sb,
struct ext2_group_desc *gd, uint32_t index);
Block Operations
// Block allocation and management
int ext2_block_alloc(struct superblock *sb, uint32_t *block);
int ext2_block_free(struct superblock *sb, uint32_t block);
int ext2_block_read(struct superblock *sb, uint32_t block, void *buffer);
int ext2_block_write(struct superblock *sb, uint32_t block, const void *buffer);
// Block bitmap operations
int ext2_test_bit(const uint8_t *bitmap, uint32_t bit);
void ext2_set_bit(uint8_t *bitmap, uint32_t bit);
void ext2_clear_bit(uint8_t *bitmap, uint32_t bit);
int ext2_find_first_zero_bit(const uint8_t *bitmap, uint32_t size);
File Operations
// File I/O operations
ssize_t ext2_file_read(struct file *file, char *buffer, size_t count, loff_t *offset);
ssize_t ext2_file_write(struct file *file, const char *buffer, size_t count, loff_t *offset);
int ext2_file_open(struct inode *inode, struct file *file);
int ext2_file_release(struct inode *inode, struct file *file);
// Block mapping
int ext2_get_block(struct inode *inode, uint32_t block, uint32_t *phys_block);
int ext2_map_block(struct inode *inode, uint32_t logical_block, int create);
// Handle indirect blocks
int ext2_get_indirect_block(struct superblock *sb, uint32_t indirect_block,
uint32_t index, uint32_t *phys_block);
int ext2_get_double_indirect_block(struct superblock *sb, uint32_t double_indirect,
uint32_t index, uint32_t *phys_block);
int ext2_get_triple_indirect_block(struct superblock *sb, uint32_t triple_indirect,
uint32_t index, uint32_t *phys_block);
Directory Operations
// Directory operations
struct ext2_dir_entry *ext2_dir_lookup(struct inode *dir, const char *name, size_t len);
int ext2_dir_add_entry(struct inode *dir, const char *name, size_t len, uint32_t ino, uint8_t type);
int ext2_dir_remove_entry(struct inode *dir, const char *name, size_t len);
int ext2_dir_is_empty(struct inode *dir);
// Directory iteration
int ext2_readdir(struct file *file, void *dirent, filldir_t filldir);
int ext2_create(struct inode *dir, struct dentry *dentry, int mode);
int ext2_mkdir(struct inode *dir, struct dentry *dentry, int mode);
int ext2_rmdir(struct inode *dir, struct dentry *dentry);
int ext2_unlink(struct inode *dir, struct dentry *dentry);
Link Operations
// Link support
int ext2_link(struct dentry *old_dentry, struct inode *dir, struct dentry *dentry);
int ext2_symlink(struct inode *dir, struct dentry *dentry, const char *symname);
int ext2_readlink(struct dentry *dentry, char *buffer, int buflen);
int ext2_follow_link(struct dentry *dentry, struct nameidata *nd);
Block Pointer Management
Direct/Indirect Block Handling
// ext2 uses 15 block pointers in inode:
// - i_block[0-11]: Direct blocks (12 blocks)
// - i_block[12]: Single indirect (points to block of block numbers)
// - i_block[13]: Double indirect (points to block of indirect blocks)
// - i_block[14]: Triple indirect (points to block of double indirect blocks)
#define EXT2_NDIR_BLOCKS 12
#define EXT2_IND_BLOCK 12
#define EXT2_DIND_BLOCK 13
#define EXT2_TIND_BLOCK 14
// Calculate maximum file size
// With 4KB blocks and 4-byte block numbers:
// - Direct: 12 * 4KB = 48KB
// - Indirect: 1024 * 4KB = 4MB
// - Double: 1024 * 1024 * 4KB = 4GB
// - Triple: 1024 * 1024 * 1024 * 4KB = 4TB
uint32_t ext2_max_file_size(struct ext2_superblock *sb);
int ext2_truncate(struct inode *inode, loff_t new_size);
VFS Integration
Superblock Operations
struct super_operations ext2_super_ops = {
.read_inode = ext2_read_inode,
.write_inode = ext2_write_inode,
.delete_inode = ext2_delete_inode,
.put_super = ext2_put_super,
.sync_fs = ext2_sync_fs,
.statfs = ext2_statfs,
};
Inode Operations
struct inode_operations ext2_file_inode_ops = {
.truncate = ext2_truncate,
.getattr = ext2_getattr,
.setattr = ext2_setattr,
};
struct inode_operations ext2_dir_inode_ops = {
.create = ext2_create,
.lookup = ext2_lookup,
.link = ext2_link,
.unlink = ext2_unlink,
.symlink = ext2_symlink,
.mkdir = ext2_mkdir,
.rmdir = ext2_rmdir,
.rename = ext2_rename,
};
struct inode_operations ext2_symlink_inode_ops = {
.readlink = ext2_readlink,
.follow_link = ext2_follow_link,
};
File Operations
struct file_operations ext2_file_ops = {
.read = ext2_file_read,
.write = ext2_file_write,
.open = ext2_file_open,
.release = ext2_file_release,
.lseek = generic_file_lseek,
.fsync = ext2_fsync,
};
struct file_operations ext2_dir_ops = {
.read = generic_read_dir,
.readdir = ext2_readdir,
};
Testing Strategy
- Read tests: Mount ext2 image, read files
- Write tests: Create files, write data, verify
- Directory tests: Create, list, delete directories
- Large file tests: Test indirect block handling
- Permission tests: Verify mode bits work correctly
- Link tests: Hard links and symbolic links
- Stress tests: Many files, deep directories
- Concurrent access tests
- Power-loss simulation tests
Performance Considerations
- Block caching for frequently accessed blocks
- Inode caching
- Directory entry caching
- Read-ahead for sequential access
- Delayed write for metadata updates
- Batch allocation for efficiency
Security Considerations
- Validate all filesystem structures
- Check bounds on all array accesses
- Prevent directory loops in traversal
- Validate inode numbers
- Check permissions before access
- Prevent integer overflows in calculations
- Sanitize symlink targets
Standards Compliance
- ext2 specification compatibility
- Linux ext2 filesystem structure
- POSIX file semantics
- Standard permission model
Usage Examples
Mount ext2 filesystem
// Mount ext2 partition
int fd = open("/dev/sda1", O_RDWR);
struct superblock *sb = mount(fd, "ext2", 0);
// Create file
int file_fd = open("/mnt/test.txt", O_CREAT | O_WRONLY, 0644);
write(file_fd, "Hello ext2!\n", 12);
close(file_fd);
// Read file
file_fd = open("/mnt/test.txt", O_RDONLY);
char buffer[128];
ssize_t bytes = read(file_fd, buffer, sizeof(buffer));
close(file_fd);
// Create directory
mkdir("/mnt/mydir", 0755);
// Unmount
umount(sb);
Related Issues
- #65 - VFS layer (required) ✅
- #63 - Block cache (performance) ✅
- #96 - File descriptor management
- #189 - FAT32 write support (similar filesystem work) ✅
- #60 - Filesystem syscalls
- #154 - ext2 read-only support (first phase)
- #228 - Dual partition mount
- #229 - Binary migration to ext2
Files to Create/Modify
- src/kernel/fs/ext2/super.c - Superblock operations
- src/kernel/fs/ext2/inode.c - Inode operations
- src/kernel/fs/ext2/file.c - File operations
- src/kernel/fs/ext2/dir.c - Directory operations
- src/kernel/fs/ext2/balloc.c - Block allocation
- src/kernel/fs/ext2/ialloc.c - Inode allocation
- src/kernel/fs/ext2/symlink.c - Symbolic link support
- include/fs/ext2.h - ext2 structures and definitions
- test/test_ext2.c - ext2 test suite
Deliverables
- Working ext2 read support
- ext2 write support
- Directory operations
- Permission management
- Link support (hard and symbolic)
- Test suite
- Documentation
Performance Goals
- File read speed comparable to FAT32
- Directory lookup < 1ms for cached entries
- Block allocation < 100μs
- Support files up to 4GB
- Handle 100,000+ files per directory
- Minimal memory overhead per mounted filesystem
Error Handling
- Detect corrupted superblock (EINVAL)
- Handle out-of-space conditions (ENOSPC)
- Detect invalid inode numbers (EINVAL)
- Handle read/write errors (EIO)
- Validate block numbers
- Check for circular directory structures
- Proper cleanup on mount failures
Current Status
Not Started - Dependencies satisfied (#65, #62, #63 complete), ready to begin Phase 1
Recommend starting with #154 (read-only support) as the first milestone.
