feat(file-system): implement read and write FAT32 File System and basic shell

3 files changed, 656 insertions, 8 deletions

diff --git a/src/fs/fat32.cc b/src/fs/fat32.cc
index 7ef829a..5c70f5a 100644
--- a/src/fs/fat32.cc
+++ b/src/fs/fat32.cc
@@ -6,6 +6,35 @@
 
 FAT32FileSystem fat32_fs;
 
+// Helper function
+static void generate_short_name(char *dst, const char *src)
+{
+    memset(dst, ' ', 11);
+
+    int i = 0;
+    for (; *src && *src != '.' && i < 8; src++)
+    {
+        char c = *src;
+        if (c >= 'a' && c <= 'z')
+            c -= 32;
+        dst[i++] = c;
+    }
+
+    while (*src && *src != '.')
+        src++;
+    if (*src == '.')
+        src++;
+
+    i = 8;
+    for (; *src && i < 11; src++)
+    {
+        char c = *src;
+        if (c >= 'a' && c <= 'z')
+            c -= 32;
+        dst[i++] = c;
+    }
+}
+
 // FAT32 FileSystem Implementation
 
 void FAT32FileSystem::init()
@@ -59,6 +88,7 @@ void FAT32FileSystem::init()
     }
 
     uint32 fat_sz = bpb->FATSz32;
+    this->fat_sz = fat_sz;
     uint32 reserved_sec = bpb->reservedSecCnt;
     uint8 num_fats = bpb->numFATs;
 
@@ -69,10 +99,12 @@ void FAT32FileSystem::init()
     fat_start_sector = partition_lba + reserved_sec;
     data_start_sector = partition_lba + reserved_sec + (fat_sz * num_fats);
 
+    Drivers::uart_puts(ANSI_GREEN);
     Drivers::uart_puts("[FAT32] Init Success: RootClus=");
     Drivers::uart_put_int(root_cluster);
     Drivers::uart_puts(", DataStart=");
     Drivers::uart_put_int(data_start_sector);
+    Drivers::uart_puts(ANSI_RESET);
     Drivers::uart_puts("\n");
 
     BufferCache::brelse(b);
@@ -216,7 +248,7 @@ Inode *FAT32Inode::lookup(const char *name)
     {
         uint32 sec = fs->cluster_to_sector(clus);
 
-        for (int i = 0; i < fs->sectors_per_cluster; i++)
+        for (uint32 i = 0; i < fs->sectors_per_cluster; i++)
         {
             uint32 current_sec = sec + i;
             struct Buf *b = BufferCache::bread(dev, current_sec / 2);
@@ -248,6 +280,8 @@ Inode *FAT32Inode::lookup(const char *name)
                     ip->nlink = 1;
                     ip->ref_cnt = 1;
                     ip->valid = 1;
+                    ip->ent_sec = current_sec; // Log Sector
+                    ip->ent_off = off;         // Log Setoff
 
                     BufferCache::brelse(b);
                     return ip;
@@ -261,11 +295,440 @@ Inode *FAT32Inode::lookup(const char *name)
 }
 
 // Placeholder
-void FAT32Inode::update() {}
-int FAT32Inode::write(const char *src, uint32 off, uint32 n, int isUser) { return -1; }
-Inode *FAT32Inode::create(const char *name, short type, short major, short minor) { return nullptr; }
-void FAT32Inode::truncate() {}
-uint32 FAT32FileSystem::alloc_cluster() { return 0; }
+uint32 FAT32FileSystem::alloc_cluster()
+{
+    uint32 fat_entries_per_sector = 512 / 4;
+    for (uint32 i = 0; i < fat_sz; i++)
+    {
+        uint32 current_fat_sec = fat_start_sector + i;
+        struct Buf *b = BufferCache::bread(0, current_fat_sec / 2);
+        uint32 *table = (uint32 *)(b->data + (current_fat_sec % 2) * 512);
+        for(uint32 j = 0; j <  fat_entries_per_sector; j++)
+        {
+            if (i == 0 && j < 2)
+                continue;
+
+            if ((table[j] & 0x0FFFFFFF) == 0)
+            {
+                // Find the free cluster and mark it as EOF (0x0FFFFFFF)
+                table[j] = 0x0FFFFFFF;
+                BufferCache::bwrite(b); // Write back to disk
+                BufferCache::brelse(b);
+
+                uint32 cluster_idx = i * fat_entries_per_sector + j;
+
+                // Clear the data content of the new cluster
+                uint32 data_sec = cluster_to_sector(cluster_idx);
+                for (uint32 k = 0; k < sectors_per_cluster; k++)
+                {
+                    struct Buf *db = BufferCache::bread(0, (data_sec + k) / 2);
+                    memset(db->data + ((data_sec + k) % 2) * 512, 0, 512);
+                    BufferCache::bwrite(db);
+                    BufferCache::brelse(db);
+                }
+
+                return cluster_idx;
+            }
+        }
+        BufferCache::brelse(b);
+    }
+    Drivers::uart_puts("[FAT32] Out of space!\n");
+    return 0;
+}
+
+void FAT32FileSystem::free_cluster_chain(uint32 cluster)
+{
+    while (cluster >= 2 && cluster < 0x0FFFFFF8)
+    {
+        uint32 next = next_cluster(cluster);
+
+        // Calculate the current cluster's position in the FAT table
+        uint32 fat_offset = cluster * 4;
+        uint32 fat_sector = fat_start_sector + (fat_offset / 512);
+        uint32 ent_offset = fat_offset % 512;
+
+        // Read FAT sector
+        struct Buf *b = BufferCache::bread(0, fat_sector / 2);
+
+        // Marked as idle (0x00000000)
+        uint32 *entry = (uint32 *)(b->data + (fat_sector % 2) * 512 + ent_offset);
+        *entry = 0;
+
+        BufferCache::bwrite(b);
+        BufferCache::brelse(b);
+
+        cluster = next;
+    }
+    
+}
+
+void FAT32Inode::update()
+{
+    struct Buf *b = BufferCache::bread(dev, ent_sec / 2);
+    uint32 offset = (ent_sec % 2) * 512 + ent_off;
+
+    struct FAT32_DirEnt *de = (struct FAT32_DirEnt *)(b->data + offset);
+
+    // Update file size and starting cluster
+    de->fileSize = size;
+    de->fstClusHI = (uint16)((first_clus >> 16) & 0xFFFF);
+    de->fstClusLO = (uint16)(first_clus & 0xFFFF);
+
+    BufferCache::bwrite(b);
+    BufferCache::brelse(b);
+}
+
+int FAT32Inode::write(const char *src, uint32 off, uint32 n, int isUser)
+{
+    if (off > size)
+    {
+        return -1;
+    }
+
+    uint32 tot = 0;
+    uint32 clus = first_clus;
+    uint32 clus_sz = fs->bytes_per_cluster;
+    uint32 prev_clus = 0;
+
+    if (clus == 0)
+    {
+        clus = fs->alloc_cluster();
+        if (clus == 0)
+            return -1;
+        first_clus = clus;
+        // Update the metadata immediately to prevent data loss in case of a power outage.
+        update();
+    }
+
+    uint32 skip = off / clus_sz;
+    uint32 current_off = off % clus_sz;
+
+    while (skip > 0)
+    {
+        prev_clus = clus;
+        clus = fs->next_cluster(clus);
+        if (clus >= 0x0FFFFFF8)
+        {
+            return -1;
+        }
+        skip--;
+    }
+    while (tot < n)
+    {
+        if (current_off == clus_sz)
+        {
+            uint32 next = fs->next_cluster(clus);
+            if (next >= 0x0FFFFFF8)
+            {
+                uint32 new_clus = fs->alloc_cluster();
+                if (new_clus == 0)
+                    break;
+
+                // Point the current cluster to the new cluster (update the FAT table)
+                uint32 fat_offset = clus * 4;
+                uint32 fat_sec = fs->fat_start_sector + (fat_offset / 512);
+                struct Buf *fat_b = BufferCache::bread(dev, fat_sec / 2);
+                uint32 *entry = (uint32 *)(fat_b->data + (fat_sec % 2) * 512 + (fat_offset % 512));
+                *entry = new_clus; // Link
+                BufferCache::bwrite(fat_b);
+                BufferCache::brelse(fat_b);
+
+                clus = new_clus;
+            }
+            else
+            {
+                clus = next;
+            }
+            current_off = 0;
+        }
+
+        // Calculate the physical sector to write
+        uint32 sec_in_clus = current_off / 512;
+        uint32 sec = fs->cluster_to_sector(clus) + sec_in_clus;
+        uint32 off_in_sec = current_off % 512;
+
+        // Calculate how many bytes can be written this time
+        uint32 m = 512 - off_in_sec;
+        if (n - tot < m)
+            m = n - tot;
+
+        struct Buf *b = BufferCache::bread(dev, sec / 2);
+        uint32 block_offset = (sec % 2) * 512 + off_in_sec;
+
+        if (isUser)
+        {
+            if (VM::copyin(myproc()->pagetable, (char *)(b->data + block_offset), (uint64)src, m) < 0)
+            {
+                BufferCache::brelse(b);
+                return -1;
+            }
+        }
+        else
+        {
+            memmove(b->data + block_offset, src, m);
+        }
+
+        BufferCache::bwrite(b);
+        BufferCache::brelse(b);
+
+        tot += m;
+        src += m;
+        current_off += m;
+    }
+    if (off + n > size)
+    {
+        size = off + n;
+        update();
+    }
+
+    return tot;
+}
+
+Inode *FAT32Inode::create(const char *name, short type, short major, short minor)
+{
+    Inode *exist = lookup(name);
+    if (exist)
+    {
+        return exist;
+    }
+
+    struct FAT32_DirEnt de;
+    memset(&de, 0, sizeof(de));
+    generate_short_name(de.name, name);
+    de.attr = (type == T_DIR) ? ATTR_DIRECTORY : ATTR_ARCHIVE;
+
+    uint32 new_dir_clus = 0;
+    if (type == T_DIR)
+    {
+        new_dir_clus = fs->alloc_cluster();
+        if (new_dir_clus == 0)
+            return nullptr;
+
+        de.fstClusHI = (uint16)((new_dir_clus >> 16) & 0xFFFF);
+        de.fstClusLO = (uint16)(new_dir_clus & 0xFFFF);
+    }
+    else
+    {
+        de.fileSize = 0;
+    }
+
+    uint32 clus = first_clus;
+    bool written = false;
+
+    while (true)
+    {
+        uint32 sec = fs->cluster_to_sector(clus);
+
+        for (uint32 i = 0; i < fs->sectors_per_cluster; i++)
+        {
+            struct Buf *b = BufferCache::bread(dev, (sec + i) / 2);
+            uint8 *data = (uint8 *)b->data + ((sec + i) % 2) * 512;
+
+            for (int off = 0; off < 512; off += 32)
+            {
+                if (data[off] == 0x00 || data[off] == 0xE5)
+                {
+                    memmove(data + off, &de, 32);
+                    BufferCache::bwrite(b);
+                    BufferCache::brelse(b);
+                    written = true;
+                    break;
+                }
+            }
+
+            if (written)
+                break;
+            BufferCache::brelse(b);
+        }
+
+        if (written)
+            break;
+
+        uint32 next = fs->next_cluster(clus);
+        if (next >= 0x0FFFFFF8)
+        {
+            uint32 new_parent_clus = fs->alloc_cluster();
+            if (new_parent_clus == 0)
+                return nullptr;
+
+            uint32 fat_off = clus * 4;
+            uint32 fat_sec = fs->fat_start_sector + (fat_off / 512);
+            struct Buf *fb = BufferCache::bread(dev, fat_sec / 2);
+            *(uint32 *)(fb->data + (fat_sec % 2) * 512 + (fat_off % 512)) = new_parent_clus;
+            BufferCache::bwrite(fb);
+            BufferCache::brelse(fb);
+
+            uint32 s = fs->cluster_to_sector(new_parent_clus);
+            for (uint32 k = 0; k < fs->sectors_per_cluster; k++)
+            {
+                struct Buf *zb = BufferCache::bread(dev, (s + k) / 2);
+                uint8 *zdata = (uint8 *)zb->data + ((s + k) % 2) * 512;
+                memset(zdata, 0, 512);
+
+                if (k == 0)
+                {
+                    memmove(zdata, &de, 32);
+                }
+
+                BufferCache::bwrite(zb);
+                BufferCache::brelse(zb);
+            }
+
+            written = true;
+            break;
+        }
+        clus = next;
+    }
+
+    if (written && type == T_DIR)
+    {
+        struct FAT32_DirEnt dot;
+        memset(&dot, 0, 32);
+        memset(dot.name, ' ', 11);
+        dot.name[0] = '.';
+        dot.attr = ATTR_DIRECTORY;
+        dot.fstClusHI = (uint16)((new_dir_clus >> 16) & 0xFFFF);
+        dot.fstClusLO = (uint16)(new_dir_clus & 0xFFFF);
+
+        struct FAT32_DirEnt dotdot;
+        memset(&dotdot, 0, 32);
+        memset(dotdot.name, ' ', 11);
+        dotdot.name[0] = '.';
+        dotdot.name[1] = '.';
+        dotdot.attr = ATTR_DIRECTORY;
+
+        uint32 parent_clus_num = this->first_clus;
+        if (parent_clus_num == fs->root_cluster)
+        {
+            parent_clus_num = 0;
+        }
+        dotdot.fstClusHI = (uint16)((parent_clus_num >> 16) & 0xFFFF);
+        dotdot.fstClusLO = (uint16)(parent_clus_num & 0xFFFF);
+
+        uint32 s = fs->cluster_to_sector(new_dir_clus);
+
+        struct Buf *zb = BufferCache::bread(dev, s / 2);
+        uint8 *zdata = (uint8 *)zb->data + (s % 2) * 512;
+
+        memmove(zdata, &dot, 32);         // Offset 0
+        memmove(zdata + 32, &dotdot, 32); // Offset 32
+
+        BufferCache::bwrite(zb);
+        BufferCache::brelse(zb);
+    }
+
+    if (written)
+    {
+        return lookup(name);
+    }
+
+    return nullptr;
+}
+
+void FAT32Inode::truncate()
+{
+    if (first_clus == 0)
+    {
+        if (size != 0)
+        {
+            size = 0;
+            update();
+        }
+        return;
+    }
+
+    fs->free_cluster_chain(first_clus);
+
+    size = 0;
+    first_clus = 0;
+
+    update();
+}
+
+int FAT32Inode::unlink(const char *name)
+{
+    if (type != T_DIR)
+        return -1;
+    if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0)
+        return -1;
+
+    uint32_t clus = first_clus;
+    bool found = false;
+    struct Buf *target_buf = nullptr;
+    uint32_t target_offset = 0;
+    struct FAT32_DirEnt de;
+
+    while (true)
+    {
+        uint32_t sec = fs->cluster_to_sector(clus);
+        for (uint32 i = 0; i < fs->sectors_per_cluster; ++i)
+        {
+            struct Buf *b = BufferCache::bread(dev, (sec + i) / 2);
+            uint8_t *data = (uint8_t *)b->data + ((sec + i) % 2) * 512;
+
+            for (int off = 0; off < 512; off += 32)
+            {
+                memmove(&de, data + off, 32);
+                if (de.name[0] == 0x00) // end of dir
+                {
+                    BufferCache::brelse(b);
+                    return -1; // Not found
+                }
+                if (de.name[0] == 0xE5)
+                    continue; // have been unlink
+                if (de.attr & ATTR_LONG_NAME)
+                    continue;
+
+                if (match_name(de.name, name))
+                {
+                    target_buf = b;
+                    target_offset = ((sec + i) % 2) * 512 + off;
+                    found = true;
+                    break;
+                }
+            }
+
+            if (found)
+                break;
+            BufferCache::brelse(b);
+        }
+
+        if (found)
+            break;
+
+        clus = fs->next_cluster(clus);
+        if (clus >= 0x0FFFFFF8)
+            return -1;
+    }
+
+    if (found && target_buf)
+    {
+        Inode *target_ip = lookup(name);
+        if (target_ip)
+        {
+            VFS::ilock(target_ip);
+            if (target_ip->type == T_DIR)
+            {
+                VFS::iunlockput(target_ip);
+                BufferCache::brelse(target_buf);
+                return -1;
+            }
+
+            target_ip->nlink--;
+            target_ip->update();
+            VFS::iunlockput(target_ip);
+        }
+
+        uint8_t *ptr = (uint8_t *)target_buf->data + target_offset;
+        *ptr = 0xE5;
+
+        BufferCache::bwrite(target_buf);
+        BufferCache::brelse(target_buf);
+        return 0;
+    }
+
+    return -1;
+}
 
 // Test Function
 void fat32_test()
diff --git a/src/fs/file.cc b/src/fs/file.cc
index 99bb65d..623b535 100644
--- a/src/fs/file.cc
+++ b/src/fs/file.cc
@@ -3,12 +3,135 @@
 #include "kernel/mm.h"
 #include "drivers/uart.h"
 #include "kernel/proc.h"
+#include "kernel/slab.h"
 
 #define NFILE 100
 #define SEEK_SET 0
 #define SEEK_CUR 1
 #define SEEK_END 2
 
+extern void *operator new(unsigned long, void *p);
+
+int Pipe::create_pair(file** f0, file** f1)
+{
+    void *mem = Slab::kmalloc(sizeof(Pipe));
+    if (!mem)
+        return -1;
+    Pipe *pi = new (mem) Pipe();
+
+    *f0 = FileTable::alloc();
+    *f1 = FileTable::alloc();
+
+    if (*f0 == nullptr || *f1 == nullptr)
+    {
+        if (*f0)
+            FileTable::close(*f0);
+        if (*f1)
+            FileTable::close(*f1);
+        pi->~Pipe();
+        Slab::kfree(pi);
+        return -1;
+    }
+
+    (*f0)->type = FD_PIPE;
+    (*f0)->readable = 1;
+    (*f0)->writable = 0;
+    (*f0)->pipe = pi;
+
+    (*f1)->type = FD_PIPE;
+    (*f1)->readable = 0;
+    (*f1)->writable = 1;
+    (*f1)->pipe = pi;
+
+    return 0;
+}
+
+void Pipe::close(bool is_writer)
+{
+    lock.acquire();
+    if (is_writer)
+    {
+        write_open = false;
+        ProcManager::wakeup(&nread); // Wake up the process that is currently reading
+    }
+    else
+    {
+        read_open = false;
+        ProcManager::wakeup(&nwrite); // Wake up the process that is writing
+    }
+
+    bool empty = !read_open && !write_open;
+    lock.release();
+
+    if (empty)
+    {
+        this->~Pipe();
+        Slab::kfree(this);
+    }
+}
+
+int Pipe::write(uint64_t addr, int n)
+{
+    int i = 0;
+    struct Proc *p = myproc();
+
+    lock.acquire();
+    while (i < n)
+    {
+        if (!read_open || p->xstate) // The read end is closed or the process is abnormal
+        {
+            lock.release();
+            return -1;
+        }
+
+        if (nwrite == nread + SIZE) // buffer is full
+        {
+            ProcManager::wakeup(&nread);
+            ProcManager::sleep(&nwrite, &lock);
+        }
+        else
+        {
+            char ch;
+            if (VM::copyin(p->pagetable, &ch, addr + i, 1) < 0)
+                break;
+            data[nwrite++ % SIZE] = ch;
+            i++;
+        }
+    }
+    ProcManager::wakeup(&nread);
+    lock.release();
+    return i;
+}
+
+int Pipe::read(uint64_t addr, int n)
+{
+    int i = 0;
+    struct Proc *p = myproc();
+
+    lock.acquire();
+    while (nread == nwrite && write_open) // The buffer is empty and the write end is not closed
+    {
+        if (p->xstate)
+        {
+            lock.release();
+            return -1;
+        }
+        ProcManager::sleep(&nread, &lock);
+    }
+
+    for (i = 0; i < n; ++i)
+    {
+        if (nread == nwrite)
+            break;
+        char ch = data[nread++ % SIZE];
+        if (VM::copyout(p->pagetable, addr + i, &ch, 1) < 0)
+            break;
+    }
+    ProcManager::wakeup(&nwrite);
+    lock.release();
+    return i;
+}
+
 namespace FileTable
 {
     struct
@@ -82,7 +205,8 @@ namespace FileTable
         }
         else if (ff.type == FD_PIPE)
         {
-            // pipeclose(ff.pipe, ff.writable);
+            if (ff.pipe)
+                ff.pipe->close(ff.writable);
         }
     }
 
@@ -101,6 +225,11 @@ namespace FileTable
             VFS::iunlock(f->ip);
             return r;
         }
+        else if (f->type == FD_PIPE)
+        {
+            if (f->pipe)
+                return f->pipe->read(addr, n);
+        }
         return -1;
     }
     
@@ -119,7 +248,11 @@ namespace FileTable
             VFS::iunlock(f->ip);
             return r;
         }
-        // else if (f->type == FD_PIPE) ...
+        else if (f->type == FD_PIPE)
+        {
+            if (f->pipe)
+                return f->pipe->write(addr, n);
+        }
 
         return -1;
     }
diff --git a/src/fs/fs.cc b/src/fs/fs.cc
index c5a34ee..9e3d50e 100644
--- a/src/fs/fs.cc
+++ b/src/fs/fs.cc
@@ -149,6 +149,7 @@ namespace VFS
         Inode *ip, *next;
         struct Proc *p = myproc();
 
+        // 1. 确定起点
         if (*path == '/')
         {
             ip = get_root();
@@ -170,6 +171,23 @@ namespace VFS
 
         while ((path = skipelem(path, name)) != nullptr)
         {
+            if (strcmp(name, ".") == 0)
+            {
+                continue;
+            }
+
+            if (strcmp(name, "..") == 0)
+            {
+                Inode *root = get_root();
+                bool is_root = (ip->inum == root->inum);
+                iput(root);
+
+                if (is_root)
+                {
+                    continue;
+                }
+            }
+
             ilock(ip);
 
             if (ip->type != T_DIR)
@@ -189,4 +207,38 @@ namespace VFS
         return ip;
     }
 
+    Inode *nameiparent(const char* path, char* name)
+    {
+        Inode* ip;
+        Inode* next;
+
+        if (*path == '/')
+            ip = get_root();
+        else
+            ip = idup(myproc()->cwd ? myproc()->cwd : get_root());
+
+        while ((path = skipelem(path, name)) != nullptr)
+        {
+            if (*path == 0)
+            {
+                return ip;
+            }
+
+            ilock(ip);
+            if (ip->type != T_DIR)
+            {
+                iunlockput(ip);
+                return nullptr;
+            }
+
+            next = ip->lookup(name);
+            iunlockput(ip);
+
+            ip = next;
+            if (!ip)
+                return nullptr;
+        }
+        iput(ip);
+        return nullptr;
+    }
 } // namespace VFS