My BobFS

bobfs.cc

#include "bobfs.h"
#include "libk.h"
#include "debug.h"
#include "machine.h"

uint8_t zero_1024[BobFS::BLOCK_SIZE];

Semaphore BobFS::lock{0};
BobFS* BobFS::cache[4];
void bobFSInit() {
    BobFS::lock.up();
    for (int i = 0; i < 4; i++) {
        BobFS::cache[i] = nullptr;
    }
}

//////////
// Node //
//////////

Node::Node(BobFS* fs, uint32_t inumber) : fs(fs), inumber(inumber) {
}

uint16_t Node::getType(void) {
    Locker l{};
    iNode inode{};
    fs->readINode(inumber, &inode);
    return inode.type;
}

bool Node::isDirectory(void) {
    return getType() == DIR_TYPE;
}

bool Node::isFile(void) {
    return getType() == FILE_TYPE;
}

static bool streq(const char* a, const char* b, uint32_t n) {
    for (uint32_t i = 0; i < n; i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

static uint32_t strlen(const char* str) {
    uint32_t i = 0;
    while (*str++ != 0) i++;
    return i;
}

Node* Node::findNode(const char* name) {
    Locker l{};
    uint32_t nameLen = strlen(name);
    iNode inode{};
    fs->readINode(inumber, &inode);
    if (inode.type != DIR_TYPE) {
        return nullptr;
    }
    uint8_t buf[inode.size];
    readAll(0, buf, inode.size, false);
    uint8_t* entries = buf;
    uint32_t i = 0;
    while (i < inode.size) {
        uint32_t entryINumber;
        memcpy(&entryINumber, entries, sizeof(uint32_t));
        entries += sizeof(uint32_t);
        uint32_t entryNameLen;
        memcpy(&entryNameLen, entries, sizeof(uint32_t));
        entries += sizeof(uint32_t);
        char entryName[entryNameLen];
        memcpy(entryName, entries, entryNameLen);
        entries += entryNameLen;
        if (nameLen == entryNameLen && streq(name, entryName, nameLen)) {
            return new Node(fs, entryINumber);
        }
        i += 2 * sizeof(uint32_t) + entryNameLen;
    }
    return nullptr;
}
    
uint16_t Node::getLinks(void) {
    Locker l{};
    iNode inode{};
    fs->readINode(inumber, &inode);
    return inode.nlinks;
}

uint32_t Node::getSize(void) {
    Locker l{};
    iNode inode{};
    fs->readINode(inumber, &inode);
    return inode.size;
}

uint32_t Node::getDataBlock(uint32_t block, iNode& inode) {
    uint32_t dataBlock;
    bool flushINode = false;
    if (block == 0) {
        if (!inode.direct) {
            inode.direct = fs->dalloc();
            flushINode = true;
        }
        dataBlock = inode.direct;
    } else {
        if (inode.indirect == 0) {
            inode.indirect = fs->dalloc();
            flushINode = true;
            dataBlock = 0;
        } else {
            fs->device->readAll(inode.indirect * BobFS::BLOCK_SIZE + (block - 1) * sizeof(uint32_t), &dataBlock, sizeof(uint32_t));
        }
        
        if (!dataBlock) {
            dataBlock = fs->dalloc();
            fs->device->writeAll(inode.indirect * BobFS::BLOCK_SIZE + (block - 1) * sizeof(uint32_t), &dataBlock, sizeof(uint32_t));
        }
    }

    if (flushINode) {
        fs->writeINode(inumber, &inode);
    }

    return dataBlock;
}

int32_t Node::read(uint32_t offset, void* buffer, uint32_t n, bool lock) {
    Locker l{lock};
    if (n == 0) return 0;

    iNode inode{};
    fs->readINode(inumber, &inode);
    if (offset > inode.size) return -1;
    if (offset == inode.size) return 0;
    if (offset + n > inode.size) n = inode.size - offset;

    uint32_t block = offset / BobFS::BLOCK_SIZE;
    uint32_t start = offset % BobFS::BLOCK_SIZE;
    uint32_t end = start + n;
    if (end > BobFS::BLOCK_SIZE) end = BobFS::BLOCK_SIZE;
    uint32_t count = end - start;

    uint32_t dataBlock = getDataBlock(block, inode);
    fs->device->readAll(dataBlock * BobFS::BLOCK_SIZE + start, buffer, count);
    return count;
}

int32_t Node::write(uint32_t offset, const void* buffer, uint32_t n, bool lock) {
    Locker l{lock};
    if (n == 0) return 0;
    if (offset >= BobFS::MAX_FILE_SIZE) return -1;
    if (offset + n > BobFS::MAX_FILE_SIZE) n = BobFS::MAX_FILE_SIZE - offset;
    iNode inode{};
    fs->readINode(inumber, &inode);

    uint32_t block = offset / BobFS::BLOCK_SIZE;
    uint32_t start = offset % BobFS::BLOCK_SIZE;

    uint32_t end = start + n;
    if (end > BobFS::BLOCK_SIZE) end = BobFS::BLOCK_SIZE;
    uint32_t count = end - start;

    uint32_t dataBlock = getDataBlock(block, inode);

    if (offset + count > inode.size) {
        inode.size = offset + count;
        fs->writeINode(inumber, &inode);
    }

    fs->device->writeAll(dataBlock * BobFS::BLOCK_SIZE + start, buffer, count);
    return count;
}

int32_t Node::readAll(uint32_t offset, void* buffer_, uint32_t n, bool lock) {
    Locker l{lock};
    int32_t total = 0;
    uint8_t* buffer = (uint8_t*) buffer_;

    while (n > 0) {
        int32_t cnt = read(offset, buffer, n, false);
        if (cnt < 0) return cnt;
        if (cnt == 0) return total;
        total += cnt;
        n -= cnt;
        offset += cnt;
        buffer += cnt;
    }
    return total;
}

int32_t Node::writeAll(uint32_t offset, const void* buffer_, uint32_t n, bool lock) {
    Locker l{lock};
    if (offset >= BobFS::MAX_FILE_SIZE) return -1;
    if (offset + n > BobFS::MAX_FILE_SIZE) n = BobFS::MAX_FILE_SIZE - offset;
    int32_t total = 0;
    uint8_t* buffer = (uint8_t*) buffer_;

    while (n > 0) {
        int32_t cnt = write(offset, buffer, n, false);
        if (cnt < 0) return cnt;
        if (cnt == 0) return total;
        total += cnt;
        n -= cnt;
        offset += cnt;
        buffer += cnt;
    }
    return total;
}

void Node::linkNode(const char* name, Node* node) {
    Locker l{};
    iNode inode{};
    fs->readINode(inumber, &inode);
    if (inode.type != DIR_TYPE) {
        return;
    }
    uint32_t nameLen = strlen(name);
    uint8_t entry[2 * sizeof(uint32_t) + nameLen];
    memcpy(&entry[0], &node->inumber, sizeof(uint32_t));
    memcpy(&entry[sizeof(uint32_t)], &nameLen, sizeof(uint32_t));
    memcpy(&entry[2 * sizeof(uint32_t)], name, nameLen);
    writeAll(inode.size, entry, sizeof(entry), false);

    iNode other{};
    fs->readINode(node->inumber, &other);
    other.nlinks++;
    fs->writeINode(node->inumber, &other);
}

Node* Node::newNode(const char* name, uint16_t type) {
    Locker l{};
    iNode inode{};
    fs->readINode(inumber, &inode);
    if (inode.type != DIR_TYPE) {
        return nullptr;
    }
    uint32_t newINumber = fs->ialloc();
    uint32_t nameLen = strlen(name);
    uint8_t entry[2 * sizeof(uint32_t) + nameLen];
    memcpy(&entry[0], &newINumber, sizeof(uint32_t));
    memcpy(&entry[sizeof(uint32_t)], &nameLen, sizeof(uint32_t));
    memcpy(&entry[2 * sizeof(uint32_t)], name, nameLen);
    writeAll(inode.size, entry, sizeof(entry), false);

    iNode newInode{
        .type = type,
        .nlinks = 1,
        .size = 0,
        .direct = 0,
        .indirect = 0
    };
    fs->writeINode(newINumber, &newInode);
    return new Node(fs, newINumber);
}

Node* Node::newFile(const char* name) {
    return newNode(name, FILE_TYPE);
}

Node* Node::newDirectory(const char* name) {
    return newNode(name, DIR_TYPE);
}

void Node::dump(const char* name, bool* visited) {
    bool top = false;
    if (!visited) {
        visited = new bool[BobFS::INODE_BITMAP_SIZE * 8];
        for (uint32_t i = 0; i < BobFS::INODE_BITMAP_SIZE * 8; i++) visited[i] = 0;
        top = true;
    }
    bool was = visited[inumber];
    visited[inumber] = 1;
    uint32_t type = getType();
    switch (type) {
    case DIR_TYPE:
        Debug::printf("*** 0 directory:%s(%d)\n",name,getLinks());
        {
            uint32_t sz = getSize();
            uint32_t offset = 0;

            while (offset < sz) {
                uint32_t ichild;
                readAll(offset,&ichild,4);
                offset += 4;
                uint32_t len;
                readAll(offset,&len,4);
                offset += 4;
                char* ptr = (char*) malloc(len+1);
                readAll(offset,ptr,len);
                offset += len;
                ptr[len] = 0;              
                
                Node* child = Node::get(fs,ichild);
                if (!was)
                    child->dump(ptr, visited);
                free(ptr);
            }
        }
        break;
    case FILE_TYPE:
        Debug::printf("*** 0 file:%s(%d,%d)\n",name,getLinks(),getSize());
        break;
    default:
         Debug::panic("unknown i-node type %d\n",type);
    }
    if (top) delete[] visited;
}

Bitmap::Bitmap(Ide* device, uint32_t bitmapStart, uint32_t bitmapSize, uint32_t blockSize):
    device(device), bitmapStart(bitmapStart), bitmapSize(bitmapSize), blockSize(blockSize), availableBlocks(bitmapSize * 8)
{
    bitmap = new uint8_t[bitmapSize];
    device->readAll(bitmapStart, bitmap, bitmapSize);
}

Bitmap::~Bitmap() {
    device->writeAll(bitmapStart, bitmap, bitmapSize);
    delete[] bitmap;
}

inline bool Bitmap::get(uint32_t index) {
    return bitmap[index / 8] & (1 << (index % 8));
}

inline void Bitmap::set(uint32_t index, bool value) {
    uint32_t byteNum = index / 8;
    uint32_t bitNum = index % 8;
    bitmap[byteNum] |= value << bitNum;
    bitmap[byteNum] &= ~(!value << bitNum);
}

uint32_t Bitmap::map(uint32_t sz) {
    uint32_t size = (sz / blockSize) + ((bool) (sz % blockSize));
    uint32_t i = 0;
    while (true) {
        if (i + size > availableBlocks) {
            return 0;
        }
        bool clear = true;
        uint32_t next = 0;
        for (uint32_t j = 0; j < size; j++) {
            if (get(i + size - 1 - j)) {
                next = i + size - j;
                clear = false;
                break;
            }
        }

        if (clear) {
            for (uint32_t j = i; j < i + size; j++) {
                set(j, true);
            }
            return i * blockSize;
        }

        i = next;
    }
}

/*void Bitmap::unmap(uint32_t start, uint32_t size) {
}*/

///////////
// BobFS //
///////////

BobFS::BobFS(Ide* device): device(device) {
}

BobFS::~BobFS() {
    cache[device->drive] = nullptr;
}

uint32_t BobFS::dalloc() {
    uint32_t block =  (dbitmap.map(BLOCK_SIZE) + DATA_SEGMENT_START) / BLOCK_SIZE;
    device->writeAll(block * BLOCK_SIZE, zero_1024, BLOCK_SIZE);
    return block;
}

uint32_t BobFS::ialloc() {
    return ibitmap.map(INODE_SIZE) / INODE_SIZE;
}

void BobFS::readINode(uint32_t inumber, iNode* inode) {
    device->readAll(INODE_SEGMENT_START + inumber * INODE_SIZE, inode, INODE_SIZE);
}

void BobFS::writeINode(uint32_t inumber, iNode* inode) {
    device->writeAll(INODE_SEGMENT_START + inumber * INODE_SIZE, inode, INODE_SIZE);
}

Node* BobFS::root(BobFS* fs) {
    Locker l{};
    Superblock superblock{};
    fs->device->readAll(0, &superblock, sizeof(Superblock));
    if (!streq(superblock.magic, Superblock::MAGIC, 8)) {
        Debug::panic("Invalid BOBFS");
    }
    return new Node(fs, superblock.root);
}

BobFS* BobFS::mount(Ide* device) {
    if (cache[device->drive] == nullptr) {
        cache[device->drive] = new BobFS(device);
    }
    return cache[device->drive];
}

BobFS* BobFS::mkfs(Ide* device) {
    Locker l{};
    Superblock superblock{.magic = MAGIC_STRING, .root = 0};
    device->writeAll(0, &superblock, sizeof(Superblock));
    // zero the bitmaps
    device->writeAll(DATA_BITMAP_START, zero_1024, BLOCK_SIZE);
    device->writeAll(INODE_BITMAP_START, zero_1024, BLOCK_SIZE);

    BobFS* fs = new BobFS(device);
    cache[device->drive] = fs;
    uint32_t rootINumber = fs->ialloc();
    iNode rootInode = iNode{
        .type = Node::DIR_TYPE,
        .nlinks = 1,
        .size = 0,
        .direct = 0,
        .indirect = 0
    };
    device->writeAll(INODE_SEGMENT_START + rootINumber * INODE_SIZE, &rootInode, INODE_SIZE);
    return fs;
}

bobfs.h

#ifndef _BOBFS_H_
#define _BOBFS_H_

#include "ide.h"
#include "semaphore.h"
#include "debug.h"
#include "heap.h"
#include "threads.h"

#define MAGIC_STRING {'B', 'O', 'B', 'F', 'S', '4', '3', '9'}

void bobFSInit();

class BobFS;

struct Superblock {
    static constexpr const char MAGIC[] = MAGIC_STRING;
    const char magic[8];
    uint32_t root;
} __attribute__((packed));

struct iNode {
    uint16_t type;
    uint16_t nlinks;
    uint32_t size;
    uint32_t direct;
    uint32_t indirect;
} __attribute__((packed));

/* In-memory representation of an i-node */
class Node {
    BobFS* fs;

    uint32_t getDataBlock(uint32_t block, iNode& inode);
public:
    static constexpr uint32_t SIZE = 16;
    static constexpr uint16_t DIR_TYPE = 1;
    static constexpr uint16_t FILE_TYPE = 2;

    uint32_t inumber;
    /* Create a Node object representing the given i-node
       in the given file system */
    Node(BobFS* fs, uint32_t inumber);

    /* node type */
    uint16_t getType(void);

    /* number of links to this node */
    uint16_t getLinks(void);

    /* size of the data represented by this node */
    uint32_t getSize(void);

    /* read up to "n" bytes and store them in the given "buffer"
       starting at the given "offset" in the file

       returns: number of bytes actually read
                x = 0      ==> end of file
                x < 0      ==> error
                0 < x <= n ==> number of bytes actually read
     */ 
    int32_t read(uint32_t offset, void* buffer, uint32_t n, bool lock = true);


    /* like read but promises to read as many bytes as it can */
    int32_t readAll(uint32_t offset, void* buffer, uint32_t n, bool lock = true);

    /* writes up to "n" bytes from the given "buffer"
       starting at the given "offset" in the file

       returns: number of bytes actually written
                x = 0      ==> end of file
                x < 0      ==> error
                0 < x <= n ==> number of bytes actually written
     */ 
    int32_t write(uint32_t offset, const void* buffer, uint32_t n, bool lock = true);

    /* like write but promises to write as many bytes as it can */
    int32_t writeAll(uint32_t offset, const void* buffer, uint32_t n, bool lock = true);

    /* If the current node is a directory, create an entry
       with the given information and return a pointer to the
       Node representing the new entry

       returns null if the current Node is not a directory

     */
    Node* newNode(const char* name, uint16_t type);

    /* calls newNode to create a file */
    Node* newFile(const char* name);

    /* calls newNode to create a directory */
    Node* newDirectory(const char* name);

    /* if the current node is a directory, returns a pointer
       the entry with the given name */
    Node* findNode(const char* name);

    bool isFile(void);
    bool isDirectory(void);

    /* Creates a new link to the given node in this directory */
    /* does nothing of the current node is not a directory */
    void linkNode(const char* name, Node* file);

    void dump(const char* name, bool* visited = nullptr);

    static Node* get(BobFS* fs, uint32_t index) {
        Node* n = new Node(fs,index);
        return n;
    }
};

/* A helper class that represents a generic Bitmap (for the data and inode bitmaps).
 * Has the ability to map and unmap blocks from each segment.
 * Loads the bitmap into memory when constructed, and flushes any changes back out to disk
 * when deleted.
 */
class Bitmap {
    Ide* device;
    uint32_t bitmapStart;
    uint32_t bitmapSize;
    uint32_t blockSize;
    uint32_t availableBlocks;
    uint8_t* bitmap;

    // gets a bit by index
    inline bool get(uint32_t index);
    // sets a bit to a value
    inline void set(uint32_t index, bool value);

public:
    // creates a bitmap read in from a region on the device. All values are in bytes.
    Bitmap(Ide* device, uint32_t bitmapStart, uint32_t bitmapSize, uint32_t blockSize);
    // writes any changes back to disk
    ~Bitmap();

    // finds an available region and maps it. size, in bytes, is rounded up to the nearest multiple of itemSize.
    uint32_t map(uint32_t size);
    // unmaps the region from start to start + size. start is truncated to itemSize, and size is rounded up to itemSize.
    // void unmap(uint32_t start, uint32_t size);  // looks like we might not have to delete files, so uneccessary for now?
};


/* In-memory representation of a BobFS file system */
class BobFS {
public:
    static constexpr uint32_t BLOCK_SIZE = 1024;
    static constexpr uint32_t INODE_SIZE = 16;

    static constexpr uint32_t DATA_BITMAP_START = 0x400;
    static constexpr uint32_t DATA_BITMAP_SIZE = BLOCK_SIZE;
    static constexpr uint32_t INODE_BITMAP_START = 0x800;
    static constexpr uint32_t INODE_BITMAP_SIZE = BLOCK_SIZE;

    static constexpr uint32_t INODE_SEGMENT_START = 0xc00;
    static constexpr uint32_t INODE_SEGMENT_SIZE = INODE_BITMAP_SIZE * 8 * INODE_SIZE;
    static constexpr uint32_t DATA_SEGMENT_START = INODE_SEGMENT_START + INODE_SEGMENT_SIZE;

    static constexpr uint32_t MAX_FILE_SIZE = (BLOCK_SIZE / sizeof(uint32_t) + 1) * BLOCK_SIZE;

    static Semaphore lock;
    static BobFS* cache[4];
    Ide* device;
    Bitmap dbitmap{device, DATA_BITMAP_START, DATA_BITMAP_SIZE, BLOCK_SIZE};
    Bitmap ibitmap{device, INODE_BITMAP_START, INODE_BITMAP_SIZE, INODE_SIZE};

    BobFS(Ide* device);
    virtual ~BobFS();

    // alloc a data block and return its block number (relative to beginning of drive)
    uint32_t dalloc();
    //void dunmap(uint32_t start, uint32_t size);

    // alloc an inode and return its inumber
    uint32_t ialloc();
    //void ifree();
    
    void readINode(uint32_t inumber, iNode* inode);
    void writeINode(uint32_t inumber, iNode* inode);

    /* make a new BobFS file system on the given device */
    static BobFS* mkfs(Ide* device);

    /* mount an existing BobFS file system from the given device */
    static BobFS* mount(Ide* device);

    /* Return a pointer to the root node of the given file system */
    static Node* root(BobFS* fs);

};

class Locker {
public:
    bool doIt;
    Locker(bool doIt = true) : doIt(doIt) {
        if (doIt) {
            BobFS::lock.down();
        }
    }

    ~Locker() {
        if (doIt) {
            BobFS::lock.up();
        }
    }
};

#endif