feat: vfs - file system manager for extensible file system implementation.
feat: simple hash table implementation based on hash list.
const char*
strchr(const char* str, int character);
+int
+streq(const char* a, const char* b);
+
#endif /* __LUNAIX_STRING_H */
--- /dev/null
+#ifndef __LUNAIX_CRC_H
+#define __LUNAIX_CRC_H
+unsigned int
+crc32b(unsigned char* data, unsigned int size);
+
+#endif /* __LUNAIX_CRC_H */
--- /dev/null
+#ifndef __LUNAIX_HASH_H
+#define __LUNAIX_HASH_H
+
+#include <stdint.h>
+
+#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 */
--- /dev/null
+/**
+ * @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 <lib/hash.h>
+#include <lunaix/ds/llist.h>
+
+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 */
--- /dev/null
+#ifndef __LUNAIX_HSTR_H
+#define __LUNAIX_HSTR_H
+
+#include <lib/hash.h>
+
+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 */
&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 */
--- /dev/null
+#ifndef __LUNAIX_VFS_H
+#define __LUNAIX_VFS_H
+
+#include <hal/ahci/hba.h>
+#include <lunaix/block.h>
+#include <lunaix/ds/hashtable.h>
+#include <lunaix/ds/hstr.h>
+#include <lunaix/ds/llist.h>
+
+#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 */
--- /dev/null
+/**
+ * @file fsm.c File system manager
+ * @author Lunaixsky (zelong56@gmail.com)
+ * @brief
+ * @version 0.1
+ * @date 2022-07-19
+ *
+ * @copyright Copyright (c) 2022
+ *
+ */
+#include <klibc/string.h>
+#include <lunaix/ds/hashtable.h>
+#include <lunaix/fs.h>
+
+#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
--- /dev/null
+#include <klibc/string.h>
+#include <lunaix/fs.h>
+#include <lunaix/mm/cake.h>
+#include <lunaix/mm/valloc.h>
+
+#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
--- /dev/null
+#include <lib/hash.h>
+
+/**
+ * @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
--- /dev/null
+#include <klibc/string.h>
+
+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
git://scm.lunaixsky.com / lunaix-os.git / commitdiff