From 4769a870917b98723690aa336d12d0656769528b Mon Sep 17 00:00:00 2001 From: Minep Date: Wed, 20 Jul 2022 13:31:57 +0100 Subject: [PATCH] feat: vfs - path walking and dnode caching. feat: vfs - file system manager for extensible file system implementation. feat: simple hash table implementation based on hash list. --- lunaix-os/includes/klibc/string.h | 3 + lunaix-os/includes/lib/crc.h | 6 + lunaix-os/includes/lib/hash.h | 26 +++ lunaix-os/includes/lunaix/ds/hashtable.h | 49 +++++ lunaix-os/includes/lunaix/ds/hstr.h | 25 +++ lunaix-os/includes/lunaix/ds/llist.h | 23 +++ lunaix-os/includes/lunaix/fs.h | 97 ++++++++++ lunaix-os/kernel/fs/fsm.c | 48 +++++ lunaix-os/kernel/fs/vfs.c | 221 +++++++++++++++++++++++ lunaix-os/libs/hash.c | 21 +++ lunaix-os/libs/klibc/string/strcmp.c | 14 ++ 11 files changed, 533 insertions(+) create mode 100644 lunaix-os/includes/lib/crc.h create mode 100644 lunaix-os/includes/lib/hash.h create mode 100644 lunaix-os/includes/lunaix/ds/hashtable.h create mode 100644 lunaix-os/includes/lunaix/ds/hstr.h create mode 100644 lunaix-os/includes/lunaix/fs.h create mode 100644 lunaix-os/kernel/fs/fsm.c create mode 100644 lunaix-os/kernel/fs/vfs.c create mode 100644 lunaix-os/libs/hash.c create mode 100644 lunaix-os/libs/klibc/string/strcmp.c diff --git a/lunaix-os/includes/klibc/string.h b/lunaix-os/includes/klibc/string.h index 8337ef1..35fd53e 100644 --- a/lunaix-os/includes/klibc/string.h +++ b/lunaix-os/includes/klibc/string.h @@ -30,4 +30,7 @@ strncpy(char* dest, const char* src, size_t n); const char* strchr(const char* str, int character); +int +streq(const char* a, const char* b); + #endif /* __LUNAIX_STRING_H */ diff --git a/lunaix-os/includes/lib/crc.h b/lunaix-os/includes/lib/crc.h new file mode 100644 index 0000000..4e9c4db --- /dev/null +++ b/lunaix-os/includes/lib/crc.h @@ -0,0 +1,6 @@ +#ifndef __LUNAIX_CRC_H +#define __LUNAIX_CRC_H +unsigned int +crc32b(unsigned char* data, unsigned int size); + +#endif /* __LUNAIX_CRC_H */ diff --git a/lunaix-os/includes/lib/hash.h b/lunaix-os/includes/lib/hash.h new file mode 100644 index 0000000..ad5e98b --- /dev/null +++ b/lunaix-os/includes/lib/hash.h @@ -0,0 +1,26 @@ +#ifndef __LUNAIX_HASH_H +#define __LUNAIX_HASH_H + +#include + +#define HASH_SIZE_BITS 32 + +uint32_t +strhash_32(unsigned char* str, uint32_t truncate_to); + +/** + * @brief Simple generic hash function + * + * ref: + * https://elixir.bootlin.com/linux/v5.18.12/source/include/linux/hash.h#L60 + * + * @param val + * @return uint32_t + */ +inline uint32_t +hash_32(uint32_t val, uint32_t truncate_to) +{ + return (val * 0x61C88647u) >> (HASH_SIZE_BITS - truncate_to); +} + +#endif /* __LUNAIX_HASH_H */ diff --git a/lunaix-os/includes/lunaix/ds/hashtable.h b/lunaix-os/includes/lunaix/ds/hashtable.h new file mode 100644 index 0000000..0e8c691 --- /dev/null +++ b/lunaix-os/includes/lunaix/ds/hashtable.h @@ -0,0 +1,49 @@ +/** + * @file hashtable.h Simple hash table implementation. + * Based on + * https://elixir.bootlin.com/linux/v5.18.12/source/include/linux/hashtable.h + * @author Lunaixsky (zelong56@gmail.com) + * @brief + * @version 0.1 + * @date 2022-07-20 + * + * @copyright Copyright (c) 2022 + * + */ +#ifndef __LUNAIX_HASHTABLE_H +#define __LUNAIX_HASHTABLE_H + +#include +#include + +struct hbucket +{ + struct hlist_node* head; +}; + +#define __hashkey(table, hash) (hash % (sizeof(table) / sizeof(table[0]))) + +#define DECLARE_HASHTABLE(name, bucket_num) struct hbucket name[bucket_num]; + +#define hashtable_bucket_foreach(bucket, pos, n, member) \ + for (pos = list_entry((bucket)->head, typeof(*pos), member); \ + pos && ({ \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + 1; \ + }); \ + pos = n) + +#define hashtable_hash_foreach(table, hash, pos, n, member) \ + hashtable_bucket_foreach(&table[__hashkey(table, hash)], pos, n, member) + +#define hashtable_init(table) \ + { \ + for (int i = 0; i < (sizeof(table) / sizeof(table[0])); i++) { \ + table[i].head = 0; \ + } \ + } + +#define hashtable_hash_in(table, list_node, hash) \ + hlist_add(&table[__hashkey(table, hash)].head, list_node) + +#endif /* __LUNAIX_HASHTABLE_H */ diff --git a/lunaix-os/includes/lunaix/ds/hstr.h b/lunaix-os/includes/lunaix/ds/hstr.h new file mode 100644 index 0000000..4864052 --- /dev/null +++ b/lunaix-os/includes/lunaix/ds/hstr.h @@ -0,0 +1,25 @@ +#ifndef __LUNAIX_HSTR_H +#define __LUNAIX_HSTR_H + +#include + +struct hstr +{ + unsigned int hash; + unsigned int len; + char* value; +}; + +#define HSTR(str, length) \ + (struct hstr) \ + { \ + .len = length, .value = str \ + } + +inline void +hstr_rehash(struct hstr* hash_str, unsigned int truncate_to) +{ + hash_str->hash = strhash_32(hash_str->value, truncate_to); +} + +#endif /* __LUNAIX_HSTR_H */ diff --git a/lunaix-os/includes/lunaix/ds/llist.h b/lunaix-os/includes/lunaix/ds/llist.h index 5afc36a..9af9dd1 100644 --- a/lunaix-os/includes/lunaix/ds/llist.h +++ b/lunaix-os/includes/lunaix/ds/llist.h @@ -87,4 +87,27 @@ llist_empty(struct llist_header* elem) &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member)) +struct hlist_node +{ + struct hlist_node *next, **pprev; +}; + +static inline void +hlist_del(struct hlist_node* node) +{ + *node->pprev = node->next; + node->next = 0; + node->pprev = 0; +} + +static inline void +hlist_add(struct hlist_node** head, struct hlist_node* node) +{ + node->next = *head; + if (*head) { + (*head)->pprev = &node->next; + } + node->pprev = head; + *head = node; +} #endif /* __LUNAIX_LLIST_H */ diff --git a/lunaix-os/includes/lunaix/fs.h b/lunaix-os/includes/lunaix/fs.h new file mode 100644 index 0000000..8e34d81 --- /dev/null +++ b/lunaix-os/includes/lunaix/fs.h @@ -0,0 +1,97 @@ +#ifndef __LUNAIX_VFS_H +#define __LUNAIX_VFS_H + +#include +#include +#include +#include +#include + +#define VFS_NAME_MAXLEN 128 + +struct v_dnode; + +struct filesystem +{ + struct hlist_node fs_list; + struct hstr fs_name; + int (*mount)(struct v_superblock* vsb, struct v_dnode* mount_point); + int (*unmount)(struct v_superblock* vsb); +}; + +struct v_superblock +{ + struct llist_header sb_list; + int fs_id; + bdev_t dev; + struct v_dnode* root; + struct filesystem* fs; + struct + { + uint32_t (*read_capacity)(struct v_superblock* vsb); + uint32_t (*read_usage)(struct v_superblock* vsb); + } ops; +}; + +struct v_file +{ + struct v_inode* inode; + struct + { + void* data; + uint32_t size; + uint64_t lb_addr; + uint32_t offset; + int dirty; + } buffer; + struct + { + int (*write)(struct v_file* file, void* data_in, uint32_t size); + int (*read)(struct v_file* file, void* data_out, uint32_t size); + int (*readdir)(struct v_file* file, int dir_index); + int (*seek)(struct v_file* file, size_t offset); + int (*rename)(struct v_file* file, char* new_name); + int (*close)(struct v_file* file); + int (*sync)(struct v_file* file); + } ops; +}; + +struct v_inode +{ + uint32_t itype; + uint32_t ctime; + uint32_t mtime; + uint64_t lb_addr; + uint32_t ref_count; + uint32_t lb_usage; + struct + { + int (*open)(struct v_inode* inode, struct v_file* file); + int (*sync)(struct v_inode* inode); + int (*mkdir)(struct v_inode* inode, struct v_dnode* dnode); + int (*dir_lookup)(struct v_inode* inode, struct v_dnode* dnode); + } ops; +}; + +struct v_dnode +{ + struct hstr name; + struct v_inode* inode; + struct v_dnode* parent; + struct hlist_node hash_list; + struct llist_header children; + struct llist_header siblings; + struct v_superblock* super_block; +}; + +/* --- file system manager --- */ +void +fsm_init(); + +void +fsm_register(struct filesystem* fs); + +struct filesystem* +fsm_get(const char* fs_name); + +#endif /* __LUNAIX_VFS_H */ diff --git a/lunaix-os/kernel/fs/fsm.c b/lunaix-os/kernel/fs/fsm.c new file mode 100644 index 0000000..95e12e3 --- /dev/null +++ b/lunaix-os/kernel/fs/fsm.c @@ -0,0 +1,48 @@ +/** + * @file fsm.c File system manager + * @author Lunaixsky (zelong56@gmail.com) + * @brief + * @version 0.1 + * @date 2022-07-19 + * + * @copyright Copyright (c) 2022 + * + */ +#include +#include +#include + +#define HASH_BUCKET_BITS 4 +#define HASH_BUCKET_NUM (1 << HASH_BUCKET_BITS) + +DECLARE_HASHTABLE(fs_registry, HASH_BUCKET_NUM); + +void +fsm_init() +{ + hashtable_init(fs_registry); +} + +void +fsm_register(struct filesystem* fs) +{ + hstr_rehash(&fs->fs_name, HASH_BUCKET_BITS); + hashtable_hash_in(fs_registry, &fs->fs_list, fs->fs_name.hash); +} + +struct filesystem* +fsm_get(const char* fs_name) +{ + struct filesystem *pos, *next; + struct hstr str = HSTR(fs_name, 0); + hstr_rehash(&str, HASH_BUCKET_BITS); + + hashtable_hash_foreach(fs_registry, str.hash, pos, next, fs_list) + { + if (pos->fs_name.hash == str.hash) { + return pos; + } + } + + return NULL; +} \ No newline at end of file diff --git a/lunaix-os/kernel/fs/vfs.c b/lunaix-os/kernel/fs/vfs.c new file mode 100644 index 0000000..09539c9 --- /dev/null +++ b/lunaix-os/kernel/fs/vfs.c @@ -0,0 +1,221 @@ +#include +#include +#include +#include + +#define PATH_DELIM '/' +#define DNODE_HASHTABLE_BITS 10 +#define DNODE_HASHTABLE_SIZE (1 << DNODE_HASHTABLE_BITS) +#define DNODE_HASH_MASK (DNODE_HASHTABLE_SIZE - 1) +#define DNODE_HASHBITS (32 - DNODE_HASHTABLE_BITS) + +#define VFS_ETOOLONG -1 +#define VFS_ENOFS -2 + +static struct cake_pile* dnode_pile; +static struct cake_pile* inode_pile; +static struct cake_pile* superblock_pile; +static struct cake_pile* name_pile; + +static struct v_superblock* root_sb; +static struct hbucket* dnode_cache; + +static int fs_id = 0; + +struct v_dnode* +__new_dnode(); + +void +__free_dnode(struct v_dnode* dnode); + +struct v_superblock* +__new_superblock(); + +void +__free_superblock(struct v_superblock* sb); + +void +vfs_init() +{ + // 为他们专门创建一个蛋糕堆，而不使用valloc，这样我们可以最小化内部碎片的产生 + dnode_pile = cake_new_pile("dnode", sizeof(struct v_dnode), 1, 0); + inode_pile = cake_new_pile("inode", sizeof(struct v_inode), 1, 0); + name_pile = cake_new_pile("dname", VFS_NAME_MAXLEN, 1, 0); + superblock_pile = + cake_new_pile("superblock", sizeof(struct v_superblock), 1, 0); + + dnode_cache = valloc(DNODE_HASHTABLE_SIZE * sizeof(struct hbucket)); + + // 挂载Lunaix的根文件系统，TwiFS！ + struct filesystem* rootfs = fsm_get("twifs"); + root_sb = __new_superblock(); + rootfs->mount(root_sb, NULL); +} + +inline struct hbucket* +__dcache_get_bucket(struct v_dnode* parent, unsigned int hash) +{ + // 与parent的指针值做加法，来减小碰撞的可能性。 + hash += (uint32_t)parent; + // 确保低位更加随机 + hash = hash ^ (hash >> DNODE_HASHBITS); + return &dnode_cache[hash & DNODE_HASH_MASK]; +} + +struct v_dnode* +vfs_dcache_lookup(struct v_dnode* parent, struct hstr* str) +{ + struct hbucket* slot = __dcache_get_bucket(parent, str->hash); + + struct v_dnode *pos, *n; + hashtable_bucket_foreach(slot, pos, n, hash_list) + { + if (pos->name.hash == str->hash) { + return pos; + } + } + return NULL; +} + +void +vfs_dcache_add(struct v_dnode* parent, struct v_dnode* dnode) +{ + struct hbucket* bucket = __dcache_get_bucket(parent, dnode->name.hash); + hlist_add(&bucket->head, &dnode->hash_list); +} + +int +vfs_walk(struct v_dnode* start, const char* path, struct v_dnode** dentry) +{ + int errno = 0; + int i = 0, j = 0; + + if (path[0] == PATH_DELIM) { + start = start->super_block->root; + i++; + } + + struct v_dnode* dnode; + struct v_dnode* current_level = start; + + char name_content[VFS_NAME_MAXLEN]; + struct hstr name = HSTR(name_content, 0); + + char current, lookahead; + do { + current = path[i++]; + lookahead = path[i++]; + if (current != PATH_DELIM) { + if (j >= VFS_NAME_MAXLEN - 1) { + errno = VFS_ETOOLONG; + goto error; + } + name_content[j++] = current; + if (lookahead) { + continue; + } + } + + name_content[j] = 0; + hstr_rehash(&name, 32); + + dnode = vfs_dcache_lookup(current_level, &name); + + if (!dnode) { + dnode = __new_dnode(); + strcpy(dnode->name.value, name_content); + dnode->name.hash = name.hash; + dnode->name.len = j; + + if ((errno = + dnode->inode->ops.dir_lookup(current_level->inode, dnode))) { + goto error; + } + + vfs_dcache_add(current_level, dnode); + + dnode->parent = current_level; + llist_append(¤t_level->children, &dnode->siblings); + } + + j = 0; + current_level = dnode; + } while (lookahead); + + *dentry = dnode; + return 0; + +error: + __free_dnode(dnode); + return errno; +} + +int +vfs_mount(const char* fs_name, bdev_t device, struct v_dnode* mnt_point) +{ + struct filesystem* fs = fsm_get(fs_name); + if (!fs) + return VFS_ENOFS; + struct v_superblock* sb = __new_superblock(); + sb->dev = device; + sb->fs_id = fs_id++; + + int errno = 0; + if (!(errno = fs->mount(sb, mnt_point))) { + sb->fs = fs; + llist_append(&root_sb->sb_list, &sb->sb_list); + } + + return errno; +} + +int +vfs_unmount(const int fs_id) +{ + int errno = 0; + struct v_superblock *pos, *n; + llist_for_each(pos, n, &root_sb->sb_list, sb_list) + { + if (pos->fs_id != fs_id) { + continue; + } + if (!(errno = pos->fs->unmount(pos))) { + llist_delete(&pos->sb_list); + __free_superblock(pos); + } + break; + } + return errno; +} + +struct v_superblock* +__new_superblock() +{ + struct v_superblock* sb = cake_grab(superblock_pile); + memset(sb, 0, sizeof(*sb)); + llist_init_head(&sb->sb_list); + sb->root = __new_dnode(); +} + +void +__free_superblock(struct v_superblock* sb) +{ + __free_dnode(sb->root); + cake_release(superblock_pile, sb); +} + +struct v_dnode* +__new_dnode() +{ + struct v_dnode* dnode = cake_grab(dnode_pile); + dnode->inode = cake_grab(inode_pile); + dnode->name.value = cake_grab(name_pile); +} + +void +__free_dnode(struct v_dnode* dnode) +{ + cake_release(inode_pile, dnode->inode); + cake_release(name_pile, dnode->name.value); + cake_release(dnode_pile, dnode); +} \ No newline at end of file diff --git a/lunaix-os/libs/hash.c b/lunaix-os/libs/hash.c new file mode 100644 index 0000000..293ec67 --- /dev/null +++ b/lunaix-os/libs/hash.c @@ -0,0 +1,21 @@ +#include + +/** + * @brief Simple string hash function + * + * ref: https://stackoverflow.com/a/7666577 + * + * @param str + * @return unsigned int + */ +uint32_t +strhash_32(unsigned char* str, uint32_t truncate_to) +{ + uint32_t hash = 5381; + int c; + + while (c = *str++) + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + + return hash >> (HASH_SIZE_BITS - truncate_to); +} \ No newline at end of file diff --git a/lunaix-os/libs/klibc/string/strcmp.c b/lunaix-os/libs/klibc/string/strcmp.c new file mode 100644 index 0000000..736bb91 --- /dev/null +++ b/lunaix-os/libs/klibc/string/strcmp.c @@ -0,0 +1,14 @@ +#include + +int +streq(const char* a, const char* b) +{ + while (*a == *b) { + if (!(*a)) { + return 1; + } + a++; + b++; + } + return 0; +} \ No newline at end of file -- 2.27.0