From 2bc33f1a7ac94e534c266ac1473e89e0f4268225 Mon Sep 17 00:00:00 2001 From: Amlal Date: Sat, 3 May 2025 10:55:00 +0200 Subject: kernel: HeFS: breaking changes — major refactor of Index Node Directory layout MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Why: - Enables efficient allocation of nested paths like '/boot/pagefile.sys' without pre-creating parent paths manually. - Reduces disk space waste by avoiding placeholder or stub directories. - Faster and cleaner: avoids expensive Utf8Char* traversal and comparison at runtime. - Prepares the filesystem for structural hashing and future journaling. Signed-off-by: Amlal --- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 1141 ++++++++++++++++++++++++++++ 1 file changed, 1141 insertions(+) create mode 100644 dev/kernel/src/FS/HeFS+FileSystemParser.cc (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc new file mode 100644 index 00000000..2e9e77b7 --- /dev/null +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -0,0 +1,1141 @@ +/* ------------------------------------------- + + Copyright (C) 2024-2025, Amlal El Mahrouss, all rights reserved. + +------------------------------------------- */ + +#ifdef __FSKIT_INCLUDES_HEFS__ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace Kernel { +namespace Detail { + /// @brief Forward declarations of internal functions. + + /// @brief Traverse the RB-Tree of the filesystem. + /// @param dir The directory to traverse. + /// @param start The starting point of the traversal. + /// @note This function is used to traverse the RB-Tree of the filesystem. + /// @internal Internal filesystem use only. + STATIC ATTRIBUTE(unused) _Output Void + hefsi_traverse_tree(HEFS_INDEX_NODE_DIRECTORY* dir, DriveTrait* mnt, const Lba& start_ind, + Lba& start, const BOOL try_new = NO); + + /// @brief Get the index node of a file or directory. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read from. + /// @param dir_name The name of the directory. + /// @param file_name The name of the file. + /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic + /// link, unknown). + STATIC ATTRIBUTE(unused) _Output HEFS_INDEX_NODE* hefsi_fetch_index_node( + HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, const Utf8Char* file_name, + UInt8 kind, SizeT* cnt); + + /// @brief Get the index node size. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read from. + /// @param dir_name The name of the directory. + /// @param file_name The name of the file. + /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic + /// link, unknown). + STATIC ATTRIBUTE(unused) _Output SizeT + hefsi_fetch_index_node_size(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, + const Utf8Char* file_name, UInt8 kind); + + /// @brief Allocate a new index node-> + /// @param root The root node of the filesystem. + /// @param mnt The drive to read/write from. + /// @param dir_name The name of the parent directory. + /// @return Status, see err_global_get(). + STATIC ATTRIBUTE(unused) _Output BOOL + hefsi_update_in_status(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, + HEFS_INDEX_NODE* node, const BOOL create_or_delete); + + /// @brief Balance RB-Tree of the filesystem. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read/write from. + /// @return Status, see err_global_get(). + STATIC ATTRIBUTE(unused) _Output BOOL hefsi_balance_ind(HEFS_BOOT_NODE* root, DriveTrait* mnt); + + /// @brief Alllocate IND from boot node. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read from. + /// @param dir_name The name of the directory. + /// @param dir_name The parent of the directory. + /// @param flags Directory flags. + /// @param delete_or_create Delete or create directory. + STATIC _Output BOOL hefsi_update_ind_status(HEFS_BOOT_NODE* root, DriveTrait* mnt, + const Utf8Char* dir_name, UInt16 flags, + const BOOL delete_or_create); + + UInt64 hefsi_hash_64(const Utf8Char* name) { + const UInt64 FNV_OFFSET_BASIS = 0x811C9DC5; + const UInt64 FNV_PRIME = 0x01000193; + + UInt64 hash = FNV_OFFSET_BASIS; + + while (*name) { + hash ^= (Utf8Char) (*name++); + hash *= FNV_PRIME; + } + + return hash; + } + + /// @brief Traverse the RB-Tree of the filesystem. + /// @param dir The directory to traverse. + /// @param start The starting point of the traversal. + /// @note This function is used to traverse the RB-Tree of the filesystem. + /// @internal Internal filesystem use only. + STATIC ATTRIBUTE(unused) Void + hefsi_traverse_tree(HEFS_INDEX_NODE_DIRECTORY* dir, DriveTrait* mnt, const Lba& ind_start, + Lba& start, const BOOL try_new) { + if (!mnt || !dir) return; + + BOOL check_is_good = NO; + + while (YES) { + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + mnt->fInput(mnt->fPacket); + + if (!mnt->fPacket.fPacketGood) break; + + if (dir->fNext != 0) { + if (check_is_good) break; + + start = dir->fNext; + + check_is_good = YES; + continue; + } else if (dir->fPrev != 0) { + if (check_is_good) break; + + start = dir->fPrev; + check_is_good = YES; + continue; + } else { + if (dir->fParent != 0) { + if (check_is_good) break; + + start = dir->fParent; + check_is_good = YES; + continue; + } else if (dir->fPrev != 0) { + if (check_is_good) break; + + start = dir->fPrev; + check_is_good = YES; + continue; + } else { + if (!try_new) break; + + if (start == 0) { + start = ind_start; + continue; + } + + start += kHeFSINDStartOffset; + break; + } + } + } + + if (try_new) start += sizeof(HEFS_INDEX_NODE_DIRECTORY); + if (start == 0) start = ind_start; + + (Void)(kout << "LBA_" << number(start) << kendl); + } + + /***********************************************************************************/ + /// @brief Rotate the RB-Tree to the left. + /// @internal + /***********************************************************************************/ + STATIC ATTRIBUTE(unused) _Output Void hefsi_rotate_tree(Lba& start, DriveTrait* mnt, Bool left) { + if (!start || !mnt) return; + + HEFS_INDEX_NODE_DIRECTORY* parent = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = parent; + + mnt->fInput(mnt->fPacket); + + HEFS_INDEX_NODE_DIRECTORY* grand_parent = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = parent->fParent; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = grand_parent; + + mnt->fInput(mnt->fPacket); + + if (parent->fParent == 0) return; + + HEFS_INDEX_NODE_DIRECTORY* cousin = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = left ? grand_parent->fPrev : grand_parent->fNext; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = cousin; + + mnt->fInput(mnt->fPacket); + + HEFS_INDEX_NODE_DIRECTORY* cousin_child = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = cousin->fChild; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = cousin; + + mnt->fInput(mnt->fPacket); + + grand_parent->fChild = cousin->fChild; + cousin_child->fParent = parent->fParent; + + parent->fParent = cousin->fParent; + cousin->fChild = start; + + cousin_child->fChecksum = + ke_calculate_crc32((Char*) cousin_child, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + grand_parent->fChecksum = + ke_calculate_crc32((Char*) grand_parent, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + parent->fChecksum = ke_calculate_crc32((Char*) parent, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + cousin->fChecksum = ke_calculate_crc32((Char*) cousin, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = parent->fParent; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = grand_parent; + + mnt->fOutput(mnt->fPacket); + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = parent; + + mnt->fOutput(mnt->fPacket); + + kout << "Rotate tree has been done.\r"; + } + + /// @brief Get the index node size. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read from. + /// @param dir_name The name of the directory. + /// @param file_name The name of the file. + /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic + /// link, unknown). + STATIC ATTRIBUTE(unused) _Output SizeT + hefsi_fetch_index_node_size(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, + const Utf8Char* file_name, UInt8 kind) { + if (mnt) { + HEFS_INDEX_NODE* node = (HEFS_INDEX_NODE*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE)); + HEFS_INDEX_NODE_DIRECTORY* dir = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + SizeT sz = 0UL; + + auto start = root->fStartIND; + + while (YES) { + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fInput(mnt->fPacket); + + if (!mnt->fPacket.fPacketGood) { + err_global_get() = kErrorFileNotFound; + + return 0; + } + + if (dir->fKind == kHeFSFileKindDirectory) { + if (hefsi_hash_64(dir_name) == dir->fHashName || + KStringBuilder::Equals(dir_name, kHeFSSearchAllStr)) { + for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; inode_index += 2) { + mnt->fPacket.fPacketLba = dir->fIndexNode[inode_index]; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE); + mnt->fPacket.fPacketContent = node; + mnt->fInput(mnt->fPacket); + + if (KStringBuilder::Equals(file_name, node->fName) && node->fKind == kind) { + if (node->fKind == kHeFSFileKindDirectory) { + sz += hefsi_fetch_index_node_size(root, mnt, dir_name, file_name, kind); + } else { + sz = node->fSize; + } + + return sz; + } + } + } + } + } + + err_global_get() = kErrorSuccess; + return sz; + } + + err_global_get() = kErrorFileNotFound; + return 0; + } + + /// @brief Alllocate IND from boot node. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read from. + /// @param dir_name The name of the directory. + /// @param dir_name The parent of the directory. + /// @param flags Directory flags. + /// @param delete_or_create Delete or create directory. + STATIC _Output BOOL hefsi_update_ind_status(HEFS_BOOT_NODE* root, DriveTrait* mnt, + const Utf8Char* dir_name, UInt16 flags, + const BOOL delete_or_create) { + if (urt_string_len(dir_name) >= kHeFSFileNameLen) { + err_global_get() = kErrorDisk; + return NO; + } + + if (mnt) { + HEFS_INDEX_NODE_DIRECTORY* tmpdir = + (HEFS_INDEX_NODE_DIRECTORY*) mm_new_heap(sizeof(HEFS_INDEX_NODE_DIRECTORY), Yes, No); + + auto start = root->fStartIND; + auto prev_location = start; + auto parent_location = 0UL; + + MUST_PASS(root->fStartIND > mnt->fLbaStart); + + while (YES) { + auto prev_start = start; + + if (start) + mnt->fPacket.fPacketLba = start; + else + mnt->fPacket.fPacketLba = prev_location + sizeof(HEFS_INDEX_NODE_DIRECTORY); + + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = tmpdir; + + mnt->fInput(mnt->fPacket); + + BOOL expr = NO; + + if (!delete_or_create) { + expr = (!tmpdir->fCreated && tmpdir->fDeleted) || tmpdir->fHashName == 0; + } else { + expr = tmpdir->fCreated && !tmpdir->fDeleted && hefsi_hash_64(dir_name) == tmpdir->fHashName; + } + + if (expr) { + HEFS_INDEX_NODE_DIRECTORY* dirent = + (HEFS_INDEX_NODE_DIRECTORY*) mm_new_heap(sizeof(HEFS_INDEX_NODE_DIRECTORY), Yes, No); + + rt_set_memory(dirent, 0, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + dirent->fHashName = delete_or_create ? 0UL : hefsi_hash_64(dir_name); + dirent->fAccessed = 0UL; + dirent->fCreated = delete_or_create ? 0UL : 1UL; + dirent->fDeleted = delete_or_create ? 1UL : 0UL; + dirent->fModified = 0UL; + dirent->fEntryCount = 0UL; + + dirent->fKind = kHeFSFileKindDirectory; + dirent->fFlags = flags; + dirent->fChecksum = 0; + + dirent->fEntryCount = 0; + + if (parent_location) { + HEFS_INDEX_NODE_DIRECTORY* tmpend = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = parent_location; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = tmpend; + + mnt->fInput(mnt->fPacket); + + if (tmpend->fChecksum != + ke_calculate_crc32((Char*) tmpend, sizeof(HEFS_INDEX_NODE_DIRECTORY))) + ke_panic(RUNTIME_CHECK_FILESYSTEM, "Bad CRC32"); + + if (delete_or_create) + --tmpend->fEntryCount; + else + ++tmpend->fEntryCount; + + tmpend->fChecksum = + ke_calculate_crc32((Char*) tmpend, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fOutput(mnt->fPacket); + + auto child_first = tmpend->fChild; + + while (YES) { + mnt->fPacket.fPacketLba = child_first; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = tmpend; + + mnt->fInput(mnt->fPacket); + + if ((!tmpend->fCreated && tmpend->fDeleted) || tmpend->fHashName == 0) { + start = child_first; + break; + } + + hefsi_traverse_tree(tmpend, mnt, root->fStartIND, child_first, YES); + } + } + + dirent->fNext = tmpdir->fNext; + dirent->fPrev = tmpdir->fPrev; + dirent->fParent = tmpdir->fParent; + dirent->fChild = tmpdir->fChild; + dirent->fColor = tmpdir->fColor; + + if (dirent->fColor < kHeFSRed) { + dirent->fColor = kHeFSBlack; + } + + if (dirent->fPrev == 0) { + dirent->fPrev = root->fStartIND; + } + + if (dirent->fNext == 0) { + dirent->fNext = prev_start + sizeof(HEFS_INDEX_NODE_DIRECTORY); + } + + if (dirent->fParent == 0) { + dirent->fParent = root->fStartIND; + } + + if (tmpdir->fChild == 0) { + auto child = dirent->fNext + sizeof(HEFS_INDEX_NODE_DIRECTORY); + + HEFS_INDEX_NODE_DIRECTORY* tmpend = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + while (YES) { + mnt->fPacket.fPacketLba = child; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = tmpend; + + mnt->fInput(mnt->fPacket); + + if ((!tmpend->fCreated && tmpend->fDeleted) || tmpdir->fHashName == 0) { + break; + } + + child += sizeof(HEFS_INDEX_NODE_DIRECTORY); + if (child > root->fEndIND) break; + } + + dirent->fColor = kHeFSRed; + dirent->fChild = child; + + if (child > root->fEndIND) dirent->fChild = root->fStartIND; + } + + for (SizeT index = 0UL; index < kHeFSSliceCount; ++index) { + dirent->fIndexNode[index] = 0; + } + + dirent->fChecksum = ke_calculate_crc32((Char*) dirent, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = prev_start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dirent; + + mnt->fOutput(mnt->fPacket); + + err_global_get() = kErrorSuccess; + + mm_delete_heap(dirent); + mm_delete_heap(tmpdir); + + if (!delete_or_create) + ++root->fINDCount; + else + --root->fINDCount; + + mnt->fPacket.fPacketLba = mnt->fLbaStart; + mnt->fPacket.fPacketSize = sizeof(HEFS_BOOT_NODE); + mnt->fPacket.fPacketContent = root; + + mnt->fOutput(mnt->fPacket); + + return YES; + } + + prev_location = start; + + hefsi_traverse_tree(tmpdir, mnt, root->fStartIND, start, YES); + if (start > root->fEndIND) break; + } + + err_global_get() = kErrorDisk; + mm_delete_heap(tmpdir); + + return NO; + } + + err_global_get() = kErrorDiskIsFull; + return NO; + } + + /// @brief Get the index node of a file or directory. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read from. + /// @param dir_name The name of the directory. + /// @param file_name The name of the file. + /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic + /// link, unknown). + STATIC ATTRIBUTE(unused) _Output HEFS_INDEX_NODE* hefsi_fetch_index_node( + HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, const Utf8Char* file_name, + UInt8 kind, SizeT* cnt) { + if (mnt) { + HEFS_INDEX_NODE* node_arr = new HEFS_INDEX_NODE[*cnt]; + + if (!node_arr) { + return nullptr; + } + + HEFS_INDEX_NODE* node = (HEFS_INDEX_NODE*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE)); + HEFS_INDEX_NODE_DIRECTORY* dir = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + auto start = root->fStartIND; + + auto start_cnt = 0UL; + + while (YES) { + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fInput(mnt->fPacket); + + if (!mnt->fPacket.fPacketGood) { + err_global_get() = kErrorFileNotFound; + + delete[] node_arr; + return nullptr; + } + + if (dir->fKind == kHeFSFileKindDirectory) { + if (hefsi_hash_64(dir_name) == dir->fHashName || + KStringBuilder::Equals(dir_name, kHeFSSearchAllStr)) { + if (ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)) != + dir->fChecksum) + ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 failure on HeFS IND!"); + + for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; ++inode_index) { + if (dir->fIndexNode[inode_index] != 0) { + if (mnt->fPacket.fPacketGood) { + if (ke_calculate_crc32((Char*) node, sizeof(HEFS_INDEX_NODE)) != node->fChecksum) + ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 failure on HeFS IND!"); + + if (KStringBuilder::Equals(file_name, node->fName) && node->fKind == kind) { + node_arr[start_cnt] = *node; + ++start_cnt; + + if (start_cnt > *cnt) { + return node_arr; + } + } + } else { + err_global_get() = kErrorDiskIsCorrupted; + + delete[] node_arr; + + node_arr = nullptr; + + return nullptr; + } + } + } + } + } + + hefsi_traverse_tree(dir, mnt, root->fStartIND, start, YES); + if (start > root->fEndIND || start == 0) break; + } + } + + kout << "Error: Failed to find index node->\r"; + + err_global_get() = kErrorFileNotFound; + + return nullptr; + } + + STATIC ATTRIBUTE(unused) _Output BOOL + hefsi_update_in_status(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, + HEFS_INDEX_NODE* node, BOOL delete_or_create) { + if (!root) return NO; + + auto start = root->fStartIND; + + if (start >= root->fEndIND) return NO; + if (root->fStartIN > root->fEndIN) return NO; + + if (mnt) { + HEFS_INDEX_NODE_DIRECTORY* dir = + (HEFS_INDEX_NODE_DIRECTORY*) mm_new_heap(sizeof(HEFS_INDEX_NODE_DIRECTORY), Yes, No); + + Utf8Char file_name[kHeFSFileNameLen] = {0}; + + urt_copy_memory(node->fName, file_name, urt_string_len(node->fName) + 1); + + while (YES) { + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fInput(mnt->fPacket); + + (Void)(kout << hex_number(hefsi_hash_64(dir_name)) << kendl); + (Void)(kout << hex_number(dir->fHashName) << kendl); + + if (hefsi_hash_64(dir_name) == dir->fHashName) { + for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; ++inode_index) { + if (dir->fIndexNode[inode_index] == 0 && !delete_or_create) { + dir->fIndexNode[inode_index] = root->fStartIN; + + root->fStartIN += sizeof(HEFS_INDEX_NODE); + + mnt->fPacket.fPacketLba = mnt->fLbaStart; + mnt->fPacket.fPacketSize = sizeof(HEFS_BOOT_NODE); + mnt->fPacket.fPacketContent = root; + + mnt->fOutput(mnt->fPacket); + + ++dir->fEntryCount; + dir->fChecksum = ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fOutput(mnt->fPacket); + + auto lba = dir->fIndexNode[inode_index]; + + mnt->fPacket.fPacketLba = lba; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE); + mnt->fPacket.fPacketContent = node; + + mnt->fOutput(mnt->fPacket); + + mm_delete_heap(dir); + + if (mnt->fPacket.fPacketGood) { + return YES; + } + + return NO; + } else if (dir->fIndexNode[inode_index] != 0 && delete_or_create) { + auto lba = dir->fIndexNode[inode_index]; + + HEFS_INDEX_NODE tmp_node{}; + + mnt->fPacket.fPacketLba = lba; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE); + mnt->fPacket.fPacketContent = &tmp_node; + + mnt->fInput(mnt->fPacket); + + if (!KStringBuilder::Equals(tmp_node.fName, file_name)) { + continue; + } + + root->fStartIN -= sizeof(HEFS_INDEX_NODE); + + mnt->fPacket.fPacketLba = mnt->fLbaStart; + mnt->fPacket.fPacketSize = sizeof(HEFS_BOOT_NODE); + mnt->fPacket.fPacketContent = root; + + mnt->fOutput(mnt->fPacket); + + mnt->fPacket.fPacketLba = lba; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE); + mnt->fPacket.fPacketContent = node; + + mnt->fOutput(mnt->fPacket); + + dir->fIndexNode[inode_index] = 0; + + if (dir->fEntryCount) --dir->fEntryCount; + + dir->fChecksum = ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fOutput(mnt->fPacket); + + mm_delete_heap(dir); + + if (mnt->fPacket.fPacketGood) { + return YES; + } + + return NO; + } + } + } + + hefsi_traverse_tree(dir, mnt, root->fStartIND, start, YES); + if (start > root->fEndIND || start == 0) break; + } + + mm_delete_heap(dir); + err_global_get() = kErrorFileNotFound; + return NO; + } + + err_global_get() = kErrorDiskIsFull; + return NO; + } + + /// @brief Balance RB-Tree of the filesystem. + /// @param root The root node of the filesystem. + /// @param mnt The drive to read/write from. + /// @return Status, see err_global_get(). + STATIC ATTRIBUTE(unused) _Output BOOL hefsi_balance_ind(HEFS_BOOT_NODE* root, DriveTrait* mnt) { + if (mnt) { + HEFS_INDEX_NODE_DIRECTORY* dir = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + HEFS_INDEX_NODE_DIRECTORY* parent_dir = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + auto start = root->fStartIND; + + while (YES) { + if (start == 0) break; + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fInput(mnt->fPacket); + + if (!mnt->fPacket.fPacketGood) { + err_global_get() = kErrorDiskIsCorrupted; + + return NO; + } + + if (ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)) != dir->fChecksum) { + dir->fChecksum = ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fOutput(mnt->fPacket); + } + + if (start == root->fStartIND) { + dir->fColor = kHeFSBlack; + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fOutput(mnt->fPacket); + } + + mnt->fPacket.fPacketLba = dir->fParent; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = parent_dir; + + mnt->fInput(mnt->fPacket); + + if (!mnt->fPacket.fPacketGood) { + err_global_get() = kErrorDiskIsCorrupted; + + return NO; + } + + HEFS_INDEX_NODE_DIRECTORY* dir_uncle = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = parent_dir->fNext; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir_uncle; + + mnt->fInput(mnt->fPacket); + + if (!mnt->fPacket.fPacketGood) { + err_global_get() = kErrorDiskIsCorrupted; + + return NO; + } + + if (parent_dir->fNext == start) { + hefsi_rotate_tree(start, mnt, YES); + hefsi_traverse_tree(parent_dir, mnt, root->fStartIND, start); + + if (start > root->fEndIND || start == 0) break; + + continue; + } + + parent_dir->fColor = kHeFSBlack; + + parent_dir->fChecksum = + ke_calculate_crc32((Char*) parent_dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + if (dir->fParent == 0) { + hefsi_traverse_tree(dir, mnt, root->fStartIND, start, YES); + continue; + } + + mnt->fPacket.fPacketLba = dir->fParent; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = parent_dir; + + mnt->fOutput(mnt->fPacket); + + if (!mnt->fPacket.fPacketGood) { + err_global_get() = kErrorDiskIsCorrupted; + + return NO; + } + + hefsi_rotate_tree(start, mnt, NO); + + hefsi_traverse_tree(dir, mnt, root->fStartIND, start, YES); + if (start > root->fEndIND || start == 0) break; + } + + return YES; + } + + return NO; + } +} // namespace Detail +} // namespace Kernel + +/// @note HeFS will allocate inodes and ind in advance, to avoid having to allocate them in +/// real-time. +/// @note This is certainly take longer to format a disk with it, but worth-it in the long run. + +namespace Kernel::HeFS { +/// @brief Make a EPM+HeFS drive out of the disk. +/// @param drive The drive to write on. +/// @return If it was sucessful, see err_local_get(). +_Output Bool HeFileSystemParser::Format(_Input _Output DriveTrait* drive, _Input const Int32 flags, + _Input const Utf8Char* part_name) { + NE_UNUSED(drive); + NE_UNUSED(flags); + NE_UNUSED(part_name); + + // Verify Disk. + drive->fVerify(drive->fPacket); + + // if disk isn't good, then error out. + if (false == drive->fPacket.fPacketGood) { + err_global_get() = kErrorDiskIsCorrupted; + return false; + } + + if (drv_std_get_size() < kHeFSMinimumDiskSize) { + err_global_get() = kErrorDiskIsTooTiny; + kout << "Error: Failed to allocate memory for boot node->\r"; + return NO; + } + + HEFS_BOOT_NODE* root = (HEFS_BOOT_NODE*) RTL_ALLOCA(sizeof(HEFS_BOOT_NODE)); + + drive->fPacket.fPacketLba = drive->fLbaStart; + drive->fPacket.fPacketSize = sizeof(HEFS_BOOT_NODE); + drive->fPacket.fPacketContent = root; + + drive->fInput(drive->fPacket); + + if (!drive->fPacket.fPacketGood) { + err_global_get() = kErrorDiskIsCorrupted; + + return NO; + } + + // Check if the disk is already formatted. + + if (KStringBuilder::Equals(root->fMagic, kHeFSMagic) && root->fVersion == kHeFSVersion) { + err_global_get() = kErrorSuccess; + return YES; + } + + if (ke_calculate_crc32((Char*) root, sizeof(HEFS_BOOT_NODE)) != root->fChecksum && + root->fChecksum > 0) { + err_global_get() = kErrorDiskIsCorrupted; + return NO; + } + + rt_copy_memory((VoidPtr) "fs/hefs-packet", drive->fPacket.fPacketMime, + rt_string_len("fs/hefs-packet")); + + urt_copy_memory((VoidPtr) part_name, root->fVolName, urt_string_len(part_name) + 1); + rt_copy_memory((VoidPtr) kHeFSMagic, root->fMagic, kHeFSMagicLen - 1); + + if (drive->fLbaStart > drive->fLbaEnd) { + err_global_get() = kErrorDiskIsCorrupted; + + return NO; + } + + root->fBadSectors = 0; + + root->fSectorCount = drv_std_get_sector_count(); + root->fSectorSize = drive->fSectorSz; + + MUST_PASS(root->fSectorSize); + + const SizeT max_lba = drive->fLbaEnd / root->fSectorSize; + + const SizeT dir_max = max_lba / 20; // 20% for directory metadata + const SizeT inode_max = max_lba / 20; // 10% for inodes + + root->fStartIND = drive->fLbaStart + kHeFSINDStartOffset; + root->fEndIND = root->fStartIND + dir_max; + + root->fStartIN = root->fEndIND + sizeof(HEFS_INDEX_NODE_DIRECTORY); + root->fEndIN = root->fStartIN + inode_max; + + constexpr SizeT kHeFSPreallocateCount = 0x6UL; + + root->fINDCount = 0; + + // let's lie here. + root->fDiskSize = drive->fLbaEnd; + root->fDiskStatus = kHeFSStatusUnlocked; + + root->fDiskFlags = flags; + + if (drive->fKind & kMassStorageDrive) { + } else if (drive->fKind & kHeFSOpticalDrive) { + root->fDiskKind = kHeFSOpticalDrive; + } else { + root->fDiskKind = kHeFSUnknown; + } + + root->fReserved = 0; + root->fReserved1 = 0; + + root->fVersion = kHeFSVersion; + + root->fVID = kHeFSInvalidVID; + + root->fChecksum = ke_calculate_crc32((Char*) root, sizeof(HEFS_BOOT_NODE)); + + drive->fPacket.fPacketLba = drive->fLbaStart; + drive->fPacket.fPacketSize = sizeof(HEFS_BOOT_NODE); + drive->fPacket.fPacketContent = root; + + drive->fOutput(drive->fPacket); + + (Void)(kout << "Drive kind: " << drive->fProtocol() << kendl); + (Void)(kout8 << u8"Volume name: " << root->fVolName << kendl8); + (Void)(kout << "Start IND: " << hex_number(root->fStartIND) << kendl); + (Void)(kout << "Number of IND: " << hex_number(root->fINDCount) << kendl); + (Void)(kout << "Sector size: " << hex_number(root->fSectorSize) << kendl); + + if (!drive->fPacket.fPacketGood) { + err_global_get() = kErrorDiskIsCorrupted; + + return NO; + } + + const Utf8Char* kFileMap[kHeFSPreallocateCount] = {u8"/", u8"/boot", u8"/system", + u8"/network", u8"/devices", u8"/media"}; + + for (SizeT i = 0; i < kHeFSPreallocateCount; ++i) { + this->CreateINodeDirectory(drive, kHeFSEncodingUTF8, kFileMap[i]); + } + + err_global_get() = kErrorSuccess; + + return YES; +} + +/// @brief Create a new directory on the disk. +/// @param drive The drive to write on. +/// @param flags The flags to use. +/// @param dir The directory to create the file in. +/// @return If it was sucessful, see err_local_get(). +_Output Bool HeFileSystemParser::INodeDirectoryCtl_(_Input DriveTrait* drive, + _Input const Int32 flags, const Utf8Char* dir, + const BOOL delete_or_create) { + HEFS_BOOT_NODE* root = (HEFS_BOOT_NODE*) mm_new_heap(sizeof(HEFS_BOOT_NODE), Yes, No); + + rt_copy_memory((VoidPtr) "fs/hefs-packet", drive->fPacket.fPacketMime, + rt_string_len("fs/hefs-packet")); + + drive->fPacket.fPacketLba = drive->fLbaStart; + drive->fPacket.fPacketSize = sizeof(HEFS_BOOT_NODE); + drive->fPacket.fPacketContent = root; + + drive->fInput(drive->fPacket); + + if (!KStringBuilder::Equals(root->fMagic, kHeFSMagic) || root->fVersion != kHeFSVersion) { + err_global_get() = kErrorDiskIsCorrupted; + + kout << "Invalid Boot Node, this can't continue!\r"; + + return NO; + } + + if (KStringBuilder::Equals(dir, kHeFSSearchAllStr)) { + kout << "Error: Invalid directory name.\r"; + + err_global_get() = kErrorInvalidData; + + return NO; + } + + if (Detail::hefsi_update_ind_status(root, drive, dir, flags, delete_or_create)) { + // todo: make it smarter for high-throughput. + Detail::hefsi_balance_ind(root, drive); + + mm_delete_heap((VoidPtr) root); + return YES; + } + + mm_delete_heap((VoidPtr) root); + return NO; +} + +_Output Bool HeFileSystemParser::RemoveINodeDirectory(_Input DriveTrait* drive, + _Input const Int32 flags, + const Utf8Char* dir) { + return this->INodeDirectoryCtl_(drive, flags, dir, YES); +} + +_Output Bool HeFileSystemParser::CreateINodeDirectory(_Input DriveTrait* drive, + _Input const Int32 flags, + const Utf8Char* dir) { + return this->INodeDirectoryCtl_(drive, flags, dir, NO); +} + +_Output Bool HeFileSystemParser::DeleteINode(_Input DriveTrait* drive, _Input const Int32 flags, + const Utf8Char* dir, const Utf8Char* name) { + return this->INodeCtl_(drive, flags, dir, name, YES); +} + +_Output Bool HeFileSystemParser::CreateINode(_Input DriveTrait* drive, _Input const Int32 flags, + const Utf8Char* dir, const Utf8Char* name) { + return this->INodeCtl_(drive, flags, dir, name, NO); +} + +/// @brief Create a new file on the disk. +/// @param drive The drive to write on. +/// @param flags The flags to use. +/// @param dir The directory to create the file in. +/// @param name The name of the file. +/// @return If it was sucessful, see err_local_get(). +_Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input const Int32 flags, + const Utf8Char* dir, const Utf8Char* name, + const BOOL delete_or_create) { + HEFS_INDEX_NODE* node = (HEFS_INDEX_NODE*) mm_new_heap(sizeof(HEFS_INDEX_NODE), Yes, No); + + rt_set_memory(node, 0, sizeof(HEFS_INDEX_NODE)); + + HEFS_BOOT_NODE* root = (HEFS_BOOT_NODE*) RTL_ALLOCA(sizeof(HEFS_BOOT_NODE)); + + MUST_PASS(root && node); + + rt_copy_memory((VoidPtr) "fs/hefs-packet", drive->fPacket.fPacketMime, + rt_string_len("fs/hefs-packet")); + + drive->fPacket.fPacketLba = drive->fLbaStart; + drive->fPacket.fPacketSize = sizeof(HEFS_BOOT_NODE); + drive->fPacket.fPacketContent = root; + + drive->fInput(drive->fPacket); + + if (KStringBuilder::Equals(name, kHeFSSearchAllStr)) { + kout << "Error: Invalid file name.\r"; + + err_global_get() = kErrorInvalidData; + return NO; + } + + if (KStringBuilder::Equals(dir, kHeFSSearchAllStr)) { + kout << "Error: Invalid directory name.\r"; + + err_global_get() = kErrorInvalidData; + return NO; + } + + node->fAccessed = 0; + node->fCreated = delete_or_create ? 0UL : 1UL; + node->fDeleted = delete_or_create ? 1UL : 0UL; + node->fModified = 0; + node->fSize = 0; + node->fKind = kHeFSFileKindRegular; + node->fFlags = flags; + node->fChecksum = 0; + node->fChecksum = ke_calculate_crc32((Char*) node, sizeof(HEFS_INDEX_NODE)); + node->fGID = 0; + node->fUID = 0; + + urt_copy_memory((VoidPtr) name, node->fName, urt_string_len(name) + 1); + + if (Detail::hefsi_update_in_status(root, drive, dir, node, delete_or_create)) { + mm_delete_heap((VoidPtr) node); + + Detail::hefsi_balance_ind(root, drive); + err_global_get() = kErrorSuccess; + return YES; + } + + mm_delete_heap((VoidPtr) node); + err_global_get() = kErrorDirectoryNotFound; + return NO; +} + +STATIC DriveTrait kMountPoint; + +/// @brief Initialize the HeFS filesystem. +/// @return To check its status, see err_local_get(). +Boolean fs_init_hefs(Void) { + kout << "Creating HeFS disk...\r"; + + kMountPoint = io_construct_main_drive(); + + if (kMountPoint.fPacket.fPacketReadOnly == YES) + ke_panic(RUNTIME_CHECK_FILESYSTEM, "Main disk cannot be mounted (read-only media)."); + + HeFileSystemParser parser; + + parser.Format(&kMountPoint, kHeFSEncodingUTF8, kHeFSDefaultVoluneName); + + parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8"pagefile.sys"); + + return YES; +} +} // namespace Kernel::HeFS + +#endif // ifdef __FSKIT_INCLUDES_HEFS__ -- cgit v1.2.3 From d4d4944362d433146e052c3530e364b7ac6bed05 Mon Sep 17 00:00:00 2001 From: Amlal Date: Sat, 3 May 2025 11:04:41 +0200 Subject: FS:HeFS: document hefsi_hash_64. Signed-off-by: Amlal --- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index 2e9e77b7..a262fab0 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -80,14 +80,17 @@ namespace Detail { const Utf8Char* dir_name, UInt16 flags, const BOOL delete_or_create); - UInt64 hefsi_hash_64(const Utf8Char* name) { + /// @brief Simple algorithm to hash directory entries for INDs. + /// @param path the directory path. + /// @return The hashed path. + STATIC UInt64 hefsi_hash_64(const Utf8Char* path) { const UInt64 FNV_OFFSET_BASIS = 0x811C9DC5; const UInt64 FNV_PRIME = 0x01000193; UInt64 hash = FNV_OFFSET_BASIS; - while (*name) { - hash ^= (Utf8Char) (*name++); + while (*path) { + hash ^= (Utf8Char) (*path++); hash *= FNV_PRIME; } @@ -342,7 +345,8 @@ namespace Detail { if (!delete_or_create) { expr = (!tmpdir->fCreated && tmpdir->fDeleted) || tmpdir->fHashName == 0; } else { - expr = tmpdir->fCreated && !tmpdir->fDeleted && hefsi_hash_64(dir_name) == tmpdir->fHashName; + expr = + tmpdir->fCreated && !tmpdir->fDeleted && hefsi_hash_64(dir_name) == tmpdir->fHashName; } if (expr) { @@ -351,7 +355,7 @@ namespace Detail { rt_set_memory(dirent, 0, sizeof(HEFS_INDEX_NODE_DIRECTORY)); - dirent->fHashName = delete_or_create ? 0UL : hefsi_hash_64(dir_name); + dirent->fHashName = delete_or_create ? 0UL : hefsi_hash_64(dir_name); dirent->fAccessed = 0UL; dirent->fCreated = delete_or_create ? 0UL : 1UL; dirent->fDeleted = delete_or_create ? 1UL : 0UL; -- cgit v1.2.3 From a2df3cdb17330addd117938df71696ffbb2f1aae Mon Sep 17 00:00:00 2001 From: Amlal Date: Sun, 4 May 2025 09:09:49 +0200 Subject: feat(filesystem): Update HeFS implementation and specifications. Signed-off-by: Amlal --- dev/kernel/FSKit/HeFS.h | 17 ++++--- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 77 +++++++++++++++++------------- docs/tex/hefs.tex | 14 +++--- 3 files changed, 58 insertions(+), 50 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/FSKit/HeFS.h b/dev/kernel/FSKit/HeFS.h index 83d93f8c..7d84c2e7 100644 --- a/dev/kernel/FSKit/HeFS.h +++ b/dev/kernel/FSKit/HeFS.h @@ -132,7 +132,7 @@ inline constexpr Kernel::ATime kHeFSTimeMax = 0xFFFFFFFFFFFFFFFF - 1; /// @note The index node is a special type of INode that contains the file information. /// @note The index node is used to store the file information of a file. struct PACKED HEFS_INDEX_NODE final { - Kernel::Utf8Char fName[kHeFSFileNameLen]; /// @brief File name. + Kernel::UInt64 fHashPath; /// @brief File name. Kernel::UInt32 fFlags; /// @brief File flags. Kernel::UInt16 fKind; /// @brief File kind. (Regular, Directory, Block, Character, FIFO, Socket, /// Symbolic Link, Unknown). @@ -146,9 +146,9 @@ struct PACKED HEFS_INDEX_NODE final { Kernel::UInt32 fUID, fGID; /// @brief User ID and Group ID of the file. Kernel::UInt32 fMode; /// @brief File mode. (read, write, execute, etc). - Kernel::UInt64 fBlock[kHeFSSliceCount]; /// @brief block slice. + Kernel::UInt64 fSlices[kHeFSSliceCount]; /// @brief block slice. - Kernel::Char fPad[69]; + Kernel::Char fPad[317]; }; enum { @@ -162,14 +162,13 @@ enum { /// @details This structure is used to store the directory information of a file. /// @note The directory node is a special type of INode that contains the directory entries. struct PACKED HEFS_INDEX_NODE_DIRECTORY final { - Kernel::UInt64 fHashName; /// @brief Directory name. + Kernel::UInt64 fHashPath; /// @brief Directory name. Kernel::UInt32 fFlags; /// @brief File flags. Kernel::UInt16 fKind; /// @brief File kind. (Regular, Directory, Block, Character, FIFO, Socket, /// Symbolic Link, Unknown). Kernel::UInt32 fEntryCount; /// @brief Entry Count of this directory inode. - Kernel::UInt32 fChecksum, - fIndexNodeChecksum; /// @brief Checksum of the file, index node checksum. + Kernel::UInt32 fChecksum; /// @brief Checksum of the file, index node checksum. Kernel::ATime fCreated, fAccessed, fModified, fDeleted; /// @brief File timestamps and allocation status. @@ -180,12 +179,12 @@ struct PACKED HEFS_INDEX_NODE_DIRECTORY final { /// [0] = OFFSET /// [1] = SIZE /// @note Thus the += 2 when iterating over them. - Kernel::UInt64 fIndexNode[kHeFSSliceCount]; /// @brief Start of the index node. + Kernel::UInt64 fINSlices[kHeFSSliceCount]; /// @brief Start of the index node. Kernel::UInt8 fColor; /// @brief Color of the node. (Red or Black). Kernel::Lba fNext, fPrev, fChild, fParent; /// @brief Red-black tree pointers. - Kernel::Char fPad[281]; + Kernel::Char fPad[285]; }; namespace Kernel::Detail { @@ -392,4 +391,4 @@ class HeFileSystemParser final { /// @brief Initialize HeFS inside the main disk. /// @return Whether it successfuly formated it or not. Boolean fs_init_hefs(Void); -} // namespace Kernel::HeFS \ No newline at end of file +} // namespace Kernel::HeFS diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index a262fab0..b73de87e 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -80,6 +80,12 @@ namespace Detail { const Utf8Char* dir_name, UInt16 flags, const BOOL delete_or_create); + STATIC UInt64 hefsi_to_big_endian_64(UInt64 val) { + return ((val >> 56) & 0x00000000000000FFULL) | ((val >> 40) & 0x000000000000FF00ULL) | + ((val >> 24) & 0x0000000000FF0000ULL) | ((val >> 8) & 0x00000000FF000000ULL) | + ((val << 8) & 0x000000FF00000000ULL) | ((val << 24) & 0x0000FF0000000000ULL) | + ((val << 40) & 0x00FF000000000000ULL) | ((val << 56) & 0xFF00000000000000ULL); + } /// @brief Simple algorithm to hash directory entries for INDs. /// @param path the directory path. /// @return The hashed path. @@ -94,7 +100,7 @@ namespace Detail { hash *= FNV_PRIME; } - return hash; + return hefsi_to_big_endian_64(hash); } /// @brief Traverse the RB-Tree of the filesystem. @@ -272,15 +278,15 @@ namespace Detail { } if (dir->fKind == kHeFSFileKindDirectory) { - if (hefsi_hash_64(dir_name) == dir->fHashName || + if (hefsi_hash_64(dir_name) == dir->fHashPath || KStringBuilder::Equals(dir_name, kHeFSSearchAllStr)) { for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; inode_index += 2) { - mnt->fPacket.fPacketLba = dir->fIndexNode[inode_index]; + mnt->fPacket.fPacketLba = dir->fINSlices[inode_index]; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE); mnt->fPacket.fPacketContent = node; mnt->fInput(mnt->fPacket); - if (KStringBuilder::Equals(file_name, node->fName) && node->fKind == kind) { + if (hefsi_hash_64(file_name) == node->fHashPath && node->fKind == kind) { if (node->fKind == kHeFSFileKindDirectory) { sz += hefsi_fetch_index_node_size(root, mnt, dir_name, file_name, kind); } else { @@ -290,6 +296,8 @@ namespace Detail { return sz; } } + } else if (dir->fHashPath == 0) { + break; } } } @@ -343,10 +351,10 @@ namespace Detail { BOOL expr = NO; if (!delete_or_create) { - expr = (!tmpdir->fCreated && tmpdir->fDeleted) || tmpdir->fHashName == 0; + expr = (!tmpdir->fCreated && tmpdir->fDeleted) || tmpdir->fHashPath == 0; } else { expr = - tmpdir->fCreated && !tmpdir->fDeleted && hefsi_hash_64(dir_name) == tmpdir->fHashName; + tmpdir->fCreated && !tmpdir->fDeleted && hefsi_hash_64(dir_name) == tmpdir->fHashPath; } if (expr) { @@ -355,7 +363,7 @@ namespace Detail { rt_set_memory(dirent, 0, sizeof(HEFS_INDEX_NODE_DIRECTORY)); - dirent->fHashName = delete_or_create ? 0UL : hefsi_hash_64(dir_name); + dirent->fHashPath = delete_or_create ? 0UL : hefsi_hash_64(dir_name); dirent->fAccessed = 0UL; dirent->fCreated = delete_or_create ? 0UL : 1UL; dirent->fDeleted = delete_or_create ? 1UL : 0UL; @@ -401,7 +409,7 @@ namespace Detail { mnt->fInput(mnt->fPacket); - if ((!tmpend->fCreated && tmpend->fDeleted) || tmpend->fHashName == 0) { + if ((!tmpend->fCreated && tmpend->fDeleted) || tmpend->fHashPath == 0) { start = child_first; break; } @@ -445,7 +453,7 @@ namespace Detail { mnt->fInput(mnt->fPacket); - if ((!tmpend->fCreated && tmpend->fDeleted) || tmpdir->fHashName == 0) { + if ((!tmpend->fCreated && tmpend->fDeleted) || tmpdir->fHashPath == 0) { break; } @@ -460,7 +468,7 @@ namespace Detail { } for (SizeT index = 0UL; index < kHeFSSliceCount; ++index) { - dirent->fIndexNode[index] = 0; + dirent->fINSlices[index] = 0; } dirent->fChecksum = ke_calculate_crc32((Char*) dirent, sizeof(HEFS_INDEX_NODE_DIRECTORY)); @@ -546,19 +554,19 @@ namespace Detail { } if (dir->fKind == kHeFSFileKindDirectory) { - if (hefsi_hash_64(dir_name) == dir->fHashName || + if (hefsi_hash_64(dir_name) == dir->fHashPath || KStringBuilder::Equals(dir_name, kHeFSSearchAllStr)) { if (ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)) != dir->fChecksum) ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 failure on HeFS IND!"); for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; ++inode_index) { - if (dir->fIndexNode[inode_index] != 0) { + if (dir->fINSlices[inode_index] != 0) { if (mnt->fPacket.fPacketGood) { if (ke_calculate_crc32((Char*) node, sizeof(HEFS_INDEX_NODE)) != node->fChecksum) ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 failure on HeFS IND!"); - if (KStringBuilder::Equals(file_name, node->fName) && node->fKind == kind) { + if (hefsi_hash_64(file_name) == node->fHashPath && node->fKind == kind) { node_arr[start_cnt] = *node; ++start_cnt; @@ -577,6 +585,8 @@ namespace Detail { } } } + } else if (dir->fHashPath == 0) { + break; } } @@ -606,10 +616,7 @@ namespace Detail { HEFS_INDEX_NODE_DIRECTORY* dir = (HEFS_INDEX_NODE_DIRECTORY*) mm_new_heap(sizeof(HEFS_INDEX_NODE_DIRECTORY), Yes, No); - Utf8Char file_name[kHeFSFileNameLen] = {0}; - - urt_copy_memory(node->fName, file_name, urt_string_len(node->fName) + 1); - + auto hash_file = node->fHashPath; while (YES) { mnt->fPacket.fPacketLba = start; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); @@ -618,12 +625,12 @@ namespace Detail { mnt->fInput(mnt->fPacket); (Void)(kout << hex_number(hefsi_hash_64(dir_name)) << kendl); - (Void)(kout << hex_number(dir->fHashName) << kendl); + (Void)(kout << hex_number(dir->fHashPath) << kendl); - if (hefsi_hash_64(dir_name) == dir->fHashName) { + if (hefsi_hash_64(dir_name) == dir->fHashPath) { for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; ++inode_index) { - if (dir->fIndexNode[inode_index] == 0 && !delete_or_create) { - dir->fIndexNode[inode_index] = root->fStartIN; + if (dir->fINSlices[inode_index] == 0 && !delete_or_create) { + dir->fINSlices[inode_index] = root->fStartIN; root->fStartIN += sizeof(HEFS_INDEX_NODE); @@ -642,7 +649,7 @@ namespace Detail { mnt->fOutput(mnt->fPacket); - auto lba = dir->fIndexNode[inode_index]; + auto lba = dir->fINSlices[inode_index]; mnt->fPacket.fPacketLba = lba; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE); @@ -657,8 +664,8 @@ namespace Detail { } return NO; - } else if (dir->fIndexNode[inode_index] != 0 && delete_or_create) { - auto lba = dir->fIndexNode[inode_index]; + } else if (dir->fINSlices[inode_index] != 0 && delete_or_create) { + auto lba = dir->fINSlices[inode_index]; HEFS_INDEX_NODE tmp_node{}; @@ -668,7 +675,7 @@ namespace Detail { mnt->fInput(mnt->fPacket); - if (!KStringBuilder::Equals(tmp_node.fName, file_name)) { + if (tmp_node.fHashPath != hash_file) { continue; } @@ -686,7 +693,7 @@ namespace Detail { mnt->fOutput(mnt->fPacket); - dir->fIndexNode[inode_index] = 0; + dir->fINSlices[inode_index] = 0; if (dir->fEntryCount) --dir->fEntryCount; @@ -851,11 +858,7 @@ namespace Kernel::HeFS { /// @param drive The drive to write on. /// @return If it was sucessful, see err_local_get(). _Output Bool HeFileSystemParser::Format(_Input _Output DriveTrait* drive, _Input const Int32 flags, - _Input const Utf8Char* part_name) { - NE_UNUSED(drive); - NE_UNUSED(flags); - NE_UNUSED(part_name); - + _Input const Utf8Char* vol_name) { // Verify Disk. drive->fVerify(drive->fPacket); @@ -888,6 +891,12 @@ _Output Bool HeFileSystemParser::Format(_Input _Output DriveTrait* drive, _Input // Check if the disk is already formatted. if (KStringBuilder::Equals(root->fMagic, kHeFSMagic) && root->fVersion == kHeFSVersion) { + if (ke_calculate_crc32((Char*) root, sizeof(HEFS_BOOT_NODE)) != root->fChecksum && + root->fChecksum > 0) { + err_global_get() = kErrorDiskIsCorrupted; + return NO; + } + err_global_get() = kErrorSuccess; return YES; } @@ -901,7 +910,7 @@ _Output Bool HeFileSystemParser::Format(_Input _Output DriveTrait* drive, _Input rt_copy_memory((VoidPtr) "fs/hefs-packet", drive->fPacket.fPacketMime, rt_string_len("fs/hefs-packet")); - urt_copy_memory((VoidPtr) part_name, root->fVolName, urt_string_len(part_name) + 1); + urt_copy_memory((VoidPtr) vol_name, root->fVolName, urt_string_len(vol_name) + 1); rt_copy_memory((VoidPtr) kHeFSMagic, root->fMagic, kHeFSMagicLen - 1); if (drive->fLbaStart > drive->fLbaEnd) { @@ -1104,8 +1113,7 @@ _Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input cons node->fChecksum = ke_calculate_crc32((Char*) node, sizeof(HEFS_INDEX_NODE)); node->fGID = 0; node->fUID = 0; - - urt_copy_memory((VoidPtr) name, node->fName, urt_string_len(name) + 1); + node->fHashPath = Detail::hefsi_hash_64(name); if (Detail::hefsi_update_in_status(root, drive, dir, node, delete_or_create)) { mm_delete_heap((VoidPtr) node); @@ -1137,6 +1145,7 @@ Boolean fs_init_hefs(Void) { parser.Format(&kMountPoint, kHeFSEncodingUTF8, kHeFSDefaultVoluneName); parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8"pagefile.sys"); + parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8"pagefile.sys-2"); return YES; } diff --git a/docs/tex/hefs.tex b/docs/tex/hefs.tex index fe0d681b..5a9c5abf 100644 --- a/docs/tex/hefs.tex +++ b/docs/tex/hefs.tex @@ -87,7 +87,7 @@ The `HEFS\_INDEX\_NODE` represents a file and is constrained to 512 bytes to mat \begin{lstlisting}[style=cstyle, caption={HEFS\_INDEX\_NODE (Fits 512B)}] struct HEFS_INDEX_NODE { - Utf8Char fName[256]; // Local file name + UInt64fHashPath; // Local file name UInt32 fFlags; UInt16 fKind; UInt32 fSize; @@ -98,8 +98,8 @@ struct HEFS_INDEX_NODE { UInt32 fUID, fGID; UInt32 fMode; - UInt64 fBlock[16]; // Data block slices (start-only) - Char fPad[69]; // Padding to reach 512B + UInt64 fSlices[16]; // Data block slices (start-only) + Char fPad[317]; // Padding to reach 512B }; \end{lstlisting} @@ -108,22 +108,22 @@ Directories form a red-black tree. Each node (IND) can hold up to 16 index node \begin{lstlisting}[style=cstyle, caption={HEFS\_INDEX\_NODE\_DIRECTORY}] struct HEFS_INDEX_NODE_DIRECTORY { - UInt64 fHashName; // Directory name as hash + UInt64 fHashPath; // Directory name as hash UInt32 fFlags; UInt16 fKind; UInt32 fEntryCount; - UInt32 fChecksum, fIndexNodeChecksum; + UInt32 fChecksum; ATime fCreated, fAccessed, fModified, fDeleted; UInt32 fUID, fGID; UInt32 fMode; - UInt64 fIndexNode[16]; // Inode LBA references + UInt64 fINSlices[16]; // Inode LBA references UInt8 fColor; // Red/Black tree color Lba fNext, fPrev, fChild, fParent; - Char fPad[281]; + Char fPad[285]; }; \end{lstlisting} -- cgit v1.2.3 From 8c6138652733b4beda082ca2393170c14d5feb06 Mon Sep 17 00:00:00 2001 From: Amlal Date: Sun, 4 May 2025 09:15:24 +0200 Subject: feat(kernel/filesystem): update HeFS's FNV algorithm to 64-bit. Signed-off-by: Amlal --- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index b73de87e..1e2cf873 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -90,8 +90,8 @@ namespace Detail { /// @param path the directory path. /// @return The hashed path. STATIC UInt64 hefsi_hash_64(const Utf8Char* path) { - const UInt64 FNV_OFFSET_BASIS = 0x811C9DC5; - const UInt64 FNV_PRIME = 0x01000193; + const UInt64 FNV_OFFSET_BASIS = 0xcbf29ce484222325ULL; + const UInt64 FNV_PRIME = 0x100000001b3ULL; UInt64 hash = FNV_OFFSET_BASIS; -- cgit v1.2.3 From 7b8460f92cbf53342fc35f1956f91c3ca190147e Mon Sep 17 00:00:00 2001 From: Amlal Date: Mon, 5 May 2025 02:46:33 +0200 Subject: kernel(feat): fix compilation error casued by the previous commit being too 'clever' Signed-off-by: Amlal --- dev/ddk/DDKKit/ifs.h | 1 - dev/kernel/FirmwareKit/EFI/API.h | 3 +++ dev/kernel/src/FS/HeFS+FileSystemParser.cc | 40 +++++++++++++++++++++++++++--- 3 files changed, 39 insertions(+), 5 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/ddk/DDKKit/ifs.h b/dev/ddk/DDKKit/ifs.h index 8232499a..46c13be4 100644 --- a/dev/ddk/DDKKit/ifs.h +++ b/dev/ddk/DDKKit/ifs.h @@ -15,4 +15,3 @@ struct DDK_IFS_MANIFEST; /// @brief IFS hooks to plug into the FileMgr. /// why? because we don't need to implement filesystem on the kernel directly. - diff --git a/dev/kernel/FirmwareKit/EFI/API.h b/dev/kernel/FirmwareKit/EFI/API.h index 50964bb8..7c9ad93d 100644 --- a/dev/kernel/FirmwareKit/EFI/API.h +++ b/dev/kernel/FirmwareKit/EFI/API.h @@ -25,6 +25,9 @@ class BootTextWriter; inline EfiSystemTable* ST = nullptr; inline EfiBootServices* BS = nullptr; +EXTERN_C void rt_cli(); +EXTERN_C void rt_halt(); + namespace Boot { /// @brief Halt and clear interrut flag on x86. /// @return diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index 1e2cf873..1b674344 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -210,7 +210,7 @@ namespace Detail { mnt->fPacket.fPacketLba = cousin->fChild; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = cousin; + mnt->fPacket.fPacketContent = cousin_child; mnt->fInput(mnt->fPacket); @@ -236,13 +236,26 @@ namespace Detail { mnt->fOutput(mnt->fPacket); + + mnt->fPacket.fPacketLba = left ? grand_parent->fPrev : grand_parent->fNext; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = cousin; + + mnt->fOutput(mnt->fPacket); + + mnt->fPacket.fPacketLba = cousin->fChild; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = cousin_child; + + mnt->fOutput(mnt->fPacket); + mnt->fPacket.fPacketLba = start; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); mnt->fPacket.fPacketContent = parent; mnt->fOutput(mnt->fPacket); - kout << "Rotate tree has been done.\r"; + kout << "RB-Tree has been rotated.\r"; } /// @brief Get the index node size. @@ -624,6 +637,8 @@ namespace Detail { mnt->fInput(mnt->fPacket); + kout8 << dir_name << u8"\r"; + (Void)(kout << hex_number(hefsi_hash_64(dir_name)) << kendl); (Void)(kout << hex_number(dir->fHashPath) << kendl); @@ -1073,11 +1088,21 @@ _Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input cons const BOOL delete_or_create) { HEFS_INDEX_NODE* node = (HEFS_INDEX_NODE*) mm_new_heap(sizeof(HEFS_INDEX_NODE), Yes, No); + if (!node) { + err_global_get() = kErrorInvalidData; + return NO; + } + rt_set_memory(node, 0, sizeof(HEFS_INDEX_NODE)); HEFS_BOOT_NODE* root = (HEFS_BOOT_NODE*) RTL_ALLOCA(sizeof(HEFS_BOOT_NODE)); - MUST_PASS(root && node); + if (!root) { + mm_delete_heap((VoidPtr) node); + err_global_get() = kErrorInvalidData; + + return NO; + } rt_copy_memory((VoidPtr) "fs/hefs-packet", drive->fPacket.fPacketMime, rt_string_len("fs/hefs-packet")); @@ -1088,13 +1113,20 @@ _Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input cons drive->fInput(drive->fPacket); - if (KStringBuilder::Equals(name, kHeFSSearchAllStr)) { + if (KStringBuilder::Equals(dir, kHeFSSearchAllStr)) { kout << "Error: Invalid file name.\r"; err_global_get() = kErrorInvalidData; return NO; } + for (SizeT i_name = 0UL; i_name < urt_string_len(name); ++i_name) { + if (name[i_name] == u'/') { + err_global_get() = kErrorInvalidData; + return NO; + } + } + if (KStringBuilder::Equals(dir, kHeFSSearchAllStr)) { kout << "Error: Invalid directory name.\r"; -- cgit v1.2.3 From fbda565b63e33aabf0ce3493a7cd3a801d8a9bfa Mon Sep 17 00:00:00 2001 From: Amlal Date: Mon, 5 May 2025 02:56:56 +0200 Subject: feat(HeFS): Improving implementation and its quirks. Signed-off-by: Amlal --- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 89 +++++++----------------------- 1 file changed, 20 insertions(+), 69 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index 1b674344..971c6eaf 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -236,7 +236,6 @@ namespace Detail { mnt->fOutput(mnt->fPacket); - mnt->fPacket.fPacketLba = left ? grand_parent->fPrev : grand_parent->fNext; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); mnt->fPacket.fPacketContent = cousin; @@ -333,11 +332,6 @@ namespace Detail { STATIC _Output BOOL hefsi_update_ind_status(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, UInt16 flags, const BOOL delete_or_create) { - if (urt_string_len(dir_name) >= kHeFSFileNameLen) { - err_global_get() = kErrorDisk; - return NO; - } - if (mnt) { HEFS_INDEX_NODE_DIRECTORY* tmpdir = (HEFS_INDEX_NODE_DIRECTORY*) mm_new_heap(sizeof(HEFS_INDEX_NODE_DIRECTORY), Yes, No); @@ -752,13 +746,11 @@ namespace Detail { if (mnt) { HEFS_INDEX_NODE_DIRECTORY* dir = (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); - HEFS_INDEX_NODE_DIRECTORY* parent_dir = - (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); auto start = root->fStartIND; while (YES) { - if (start == 0) break; + if (start == 0 || start > root->fEndIND) break; mnt->fPacket.fPacketLba = start; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); @@ -792,73 +784,16 @@ namespace Detail { mnt->fOutput(mnt->fPacket); } - mnt->fPacket.fPacketLba = dir->fParent; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = parent_dir; - - mnt->fInput(mnt->fPacket); - - if (!mnt->fPacket.fPacketGood) { - err_global_get() = kErrorDiskIsCorrupted; - - return NO; - } - - HEFS_INDEX_NODE_DIRECTORY* dir_uncle = - (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); - - mnt->fPacket.fPacketLba = parent_dir->fNext; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = dir_uncle; - - mnt->fInput(mnt->fPacket); - - if (!mnt->fPacket.fPacketGood) { - err_global_get() = kErrorDiskIsCorrupted; - - return NO; - } - - if (parent_dir->fNext == start) { - hefsi_rotate_tree(start, mnt, YES); - hefsi_traverse_tree(parent_dir, mnt, root->fStartIND, start); - - if (start > root->fEndIND || start == 0) break; - - continue; - } - - parent_dir->fColor = kHeFSBlack; - - parent_dir->fChecksum = - ke_calculate_crc32((Char*) parent_dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)); - - if (dir->fParent == 0) { - hefsi_traverse_tree(dir, mnt, root->fStartIND, start, YES); - continue; - } - - mnt->fPacket.fPacketLba = dir->fParent; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = parent_dir; - - mnt->fOutput(mnt->fPacket); - - if (!mnt->fPacket.fPacketGood) { - err_global_get() = kErrorDiskIsCorrupted; - - return NO; - } - hefsi_rotate_tree(start, mnt, NO); - hefsi_traverse_tree(dir, mnt, root->fStartIND, start, YES); - if (start > root->fEndIND || start == 0) break; + hefsi_traverse_tree(dir, mnt, root->fStartIND, start, NO); } + err_global_get() = kErrorSuccess; return YES; } + err_global_get() = kErrorDisk; return NO; } } // namespace Detail @@ -1016,6 +951,11 @@ _Output Bool HeFileSystemParser::Format(_Input _Output DriveTrait* drive, _Input _Output Bool HeFileSystemParser::INodeDirectoryCtl_(_Input DriveTrait* drive, _Input const Int32 flags, const Utf8Char* dir, const BOOL delete_or_create) { + if (urt_string_len(dir) > kHeFSFileNameLen) { + err_global_get() = kErrorDisk; + return NO; + } + HEFS_BOOT_NODE* root = (HEFS_BOOT_NODE*) mm_new_heap(sizeof(HEFS_BOOT_NODE), Yes, No); rt_copy_memory((VoidPtr) "fs/hefs-packet", drive->fPacket.fPacketMime, @@ -1086,6 +1026,16 @@ _Output Bool HeFileSystemParser::CreateINode(_Input DriveTrait* drive, _Input co _Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input const Int32 flags, const Utf8Char* dir, const Utf8Char* name, const BOOL delete_or_create) { + if (urt_string_len(name) > kHeFSFileNameLen) { + err_global_get() = kErrorDisk; + return NO; + } + + if (urt_string_len(dir) >= kHeFSFileNameLen) { + err_global_get() = kErrorDisk; + return NO; + } + HEFS_INDEX_NODE* node = (HEFS_INDEX_NODE*) mm_new_heap(sizeof(HEFS_INDEX_NODE), Yes, No); if (!node) { @@ -1151,6 +1101,7 @@ _Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input cons mm_delete_heap((VoidPtr) node); Detail::hefsi_balance_ind(root, drive); + err_global_get() = kErrorSuccess; return YES; } -- cgit v1.2.3 From aa3efdeee647ac5200075f9c84d07a34bc9d7fcb Mon Sep 17 00:00:00 2001 From: Amlal Date: Mon, 5 May 2025 03:11:35 +0200 Subject: fs:HeFS: Filesystem fixes. Signed-off-by: Amlal --- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 109 +++++++++++++++-------------- 1 file changed, 56 insertions(+), 53 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index 971c6eaf..16d464fc 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -170,87 +170,83 @@ namespace Detail { } /***********************************************************************************/ - /// @brief Rotate the RB-Tree to the left. + /// @brief Rotate the RB-Tree to the left or right. /// @internal /***********************************************************************************/ STATIC ATTRIBUTE(unused) _Output Void hefsi_rotate_tree(Lba& start, DriveTrait* mnt, Bool left) { if (!start || !mnt) return; - HEFS_INDEX_NODE_DIRECTORY* parent = + HEFS_INDEX_NODE_DIRECTORY* cur = (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); mnt->fPacket.fPacketLba = start; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = parent; + mnt->fPacket.fPacketContent = cur; mnt->fInput(mnt->fPacket); - HEFS_INDEX_NODE_DIRECTORY* grand_parent = + if (cur->fHashPath == 0) return; + + HEFS_INDEX_NODE_DIRECTORY* sibling = (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); - mnt->fPacket.fPacketLba = parent->fParent; + mnt->fPacket.fPacketLba = cur->fPrev; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = grand_parent; + mnt->fPacket.fPacketContent = sibling; mnt->fInput(mnt->fPacket); - if (parent->fParent == 0) return; + if (sibling->fHashPath == 0) return; - HEFS_INDEX_NODE_DIRECTORY* cousin = - (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + auto child_sibling = sibling->fChild; + auto child_cur = cur->fChild; - mnt->fPacket.fPacketLba = left ? grand_parent->fPrev : grand_parent->fNext; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = cousin; - - mnt->fInput(mnt->fPacket); + cur->fChild = child_sibling; + sibling->fChild = child_cur; - HEFS_INDEX_NODE_DIRECTORY* cousin_child = - (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); + sibling->fChecksum = ke_calculate_crc32((Char*) sibling, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + cur->fChecksum = ke_calculate_crc32((Char*) cur, sizeof(HEFS_INDEX_NODE_DIRECTORY)); - mnt->fPacket.fPacketLba = cousin->fChild; + mnt->fPacket.fPacketLba = cur->fParent; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = cousin_child; + mnt->fPacket.fPacketContent = sibling; - mnt->fInput(mnt->fPacket); + mnt->fOutput(mnt->fPacket); - grand_parent->fChild = cousin->fChild; - cousin_child->fParent = parent->fParent; + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = cur; - parent->fParent = cousin->fParent; - cousin->fChild = start; + mnt->fOutput(mnt->fPacket); - cousin_child->fChecksum = - ke_calculate_crc32((Char*) cousin_child, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + HEFS_INDEX_NODE_DIRECTORY* sibling_child = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); - grand_parent->fChecksum = - ke_calculate_crc32((Char*) grand_parent, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + mnt->fPacket.fPacketLba = child_sibling; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = sibling_child; - parent->fChecksum = ke_calculate_crc32((Char*) parent, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + mnt->fInput(mnt->fPacket); - cousin->fChecksum = ke_calculate_crc32((Char*) cousin, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + sibling_child->fParent = cur->fParent; - mnt->fPacket.fPacketLba = parent->fParent; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = grand_parent; + sibling_child->fChecksum = + ke_calculate_crc32((Char*) sibling, sizeof(HEFS_INDEX_NODE_DIRECTORY)); mnt->fOutput(mnt->fPacket); - mnt->fPacket.fPacketLba = left ? grand_parent->fPrev : grand_parent->fNext; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = cousin; - - mnt->fOutput(mnt->fPacket); + HEFS_INDEX_NODE_DIRECTORY* cur_child = + (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); - mnt->fPacket.fPacketLba = cousin->fChild; + mnt->fPacket.fPacketLba = child_cur; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = cousin_child; + mnt->fPacket.fPacketContent = cur_child; - mnt->fOutput(mnt->fPacket); + mnt->fInput(mnt->fPacket); - mnt->fPacket.fPacketLba = start; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = parent; + cur_child->fParent = start; + + cur_child->fChecksum = ke_calculate_crc32((Char*) sibling, sizeof(HEFS_INDEX_NODE_DIRECTORY)); mnt->fOutput(mnt->fPacket); @@ -431,18 +427,14 @@ namespace Detail { dirent->fChild = tmpdir->fChild; dirent->fColor = tmpdir->fColor; - if (dirent->fColor < kHeFSRed) { - dirent->fColor = kHeFSBlack; + if (dirent->fColor == 0) { + dirent->fColor = dirent->fNext ? kHeFSRed : kHeFSBlack; } if (dirent->fPrev == 0) { dirent->fPrev = root->fStartIND; } - if (dirent->fNext == 0) { - dirent->fNext = prev_start + sizeof(HEFS_INDEX_NODE_DIRECTORY); - } - if (dirent->fParent == 0) { dirent->fParent = root->fStartIND; } @@ -764,8 +756,8 @@ namespace Detail { return NO; } - if (ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)) != dir->fChecksum) { - dir->fChecksum = ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + if (start == root->fStartIND) { + dir->fColor = kHeFSBlack; mnt->fPacket.fPacketLba = start; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); @@ -774,7 +766,10 @@ namespace Detail { mnt->fOutput(mnt->fPacket); } - if (start == root->fStartIND) { + if (dir->fColor == kHeFSBlack && dir->fChild != 0) { + dir->fColor = kHeFSRed; + hefsi_rotate_tree(start, mnt, NO); + } else if (dir->fColor == kHeFSBlack && dir->fChild == 0) { dir->fColor = kHeFSBlack; mnt->fPacket.fPacketLba = start; @@ -784,7 +779,15 @@ namespace Detail { mnt->fOutput(mnt->fPacket); } - hefsi_rotate_tree(start, mnt, NO); + if (ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)) != dir->fChecksum) { + dir->fChecksum = ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)); + + mnt->fPacket.fPacketLba = start; + mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); + mnt->fPacket.fPacketContent = dir; + + mnt->fOutput(mnt->fPacket); + } hefsi_traverse_tree(dir, mnt, root->fStartIND, start, NO); } -- cgit v1.2.3 From b26b54d1f1eb7568eb47e5a99d653f17b6920ccb Mon Sep 17 00:00:00 2001 From: Amlal Date: Mon, 5 May 2025 03:16:55 +0200 Subject: feat(kernel): remove usage of `left` inside `hefsi_rotate_tree` Signed-off-by: Amlal --- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index 16d464fc..078079f7 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -173,7 +173,7 @@ namespace Detail { /// @brief Rotate the RB-Tree to the left or right. /// @internal /***********************************************************************************/ - STATIC ATTRIBUTE(unused) _Output Void hefsi_rotate_tree(Lba& start, DriveTrait* mnt, Bool left) { + STATIC ATTRIBUTE(unused) _Output Void hefsi_rotate_tree(Lba& start, DriveTrait* mnt) { if (!start || !mnt) return; HEFS_INDEX_NODE_DIRECTORY* cur = @@ -768,7 +768,7 @@ namespace Detail { if (dir->fColor == kHeFSBlack && dir->fChild != 0) { dir->fColor = kHeFSRed; - hefsi_rotate_tree(start, mnt, NO); + hefsi_rotate_tree(start, mnt); } else if (dir->fColor == kHeFSBlack && dir->fChild == 0) { dir->fColor = kHeFSBlack; @@ -1132,6 +1132,7 @@ Boolean fs_init_hefs(Void) { parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8"pagefile.sys"); parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8"pagefile.sys-2"); + parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/network", u8".socket"); return YES; } -- cgit v1.2.3 From eaf96ff18d9bc516d4b1da84bc3585ff20c06c63 Mon Sep 17 00:00:00 2001 From: Amlal Date: Mon, 5 May 2025 03:21:27 +0200 Subject: feat(kernel): add .filetest to check if filesystem works correctly. Signed-off-by: Amlal --- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 35 +++++++++++++++--------------- 1 file changed, 18 insertions(+), 17 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index 078079f7..e8ffd02a 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -467,7 +467,7 @@ namespace Detail { } for (SizeT index = 0UL; index < kHeFSSliceCount; ++index) { - dirent->fINSlices[index] = 0; + dirent->fINSlices[index] = 0UL; } dirent->fChecksum = ke_calculate_crc32((Char*) dirent, sizeof(HEFS_INDEX_NODE_DIRECTORY)); @@ -608,7 +608,7 @@ namespace Detail { auto start = root->fStartIND; - if (start >= root->fEndIND) return NO; + if (start > root->fEndIND) return NO; if (root->fStartIN > root->fEndIN) return NO; if (mnt) { @@ -616,6 +616,7 @@ namespace Detail { (HEFS_INDEX_NODE_DIRECTORY*) mm_new_heap(sizeof(HEFS_INDEX_NODE_DIRECTORY), Yes, No); auto hash_file = node->fHashPath; + while (YES) { mnt->fPacket.fPacketLba = start; mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); @@ -660,11 +661,7 @@ namespace Detail { mm_delete_heap(dir); - if (mnt->fPacket.fPacketGood) { - return YES; - } - - return NO; + return YES; } else if (dir->fINSlices[inode_index] != 0 && delete_or_create) { auto lba = dir->fINSlices[inode_index]; @@ -676,6 +673,12 @@ namespace Detail { mnt->fInput(mnt->fPacket); + kout8 << u8"HashPath: "; + (Void)(kout << hex_number(tmp_node.fHashPath) << kendl); + + kout8 << u8"HashPath: "; + (Void)(kout << hex_number(hash_file) << kendl); + if (tmp_node.fHashPath != hash_file) { continue; } @@ -707,12 +710,8 @@ namespace Detail { mnt->fOutput(mnt->fPacket); mm_delete_heap(dir); - - if (mnt->fPacket.fPacketGood) { - return YES; - } - - return NO; + + return YES; } } } @@ -1034,7 +1033,7 @@ _Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input cons return NO; } - if (urt_string_len(dir) >= kHeFSFileNameLen) { + if (urt_string_len(dir) > kHeFSFileNameLen) { err_global_get() = kErrorDisk; return NO; } @@ -1111,6 +1110,7 @@ _Output Bool HeFileSystemParser::INodeCtl_(_Input DriveTrait* drive, _Input cons mm_delete_heap((VoidPtr) node); err_global_get() = kErrorDirectoryNotFound; + return NO; } @@ -1130,9 +1130,10 @@ Boolean fs_init_hefs(Void) { parser.Format(&kMountPoint, kHeFSEncodingUTF8, kHeFSDefaultVoluneName); - parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8"pagefile.sys"); - parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8"pagefile.sys-2"); - parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/network", u8".socket"); + MUST_PASS(parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8".filetest")); + MUST_PASS(parser.DeleteINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8".filetest")); + MUST_PASS(parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/network", u8".filetest")); + MUST_PASS(parser.DeleteINode(&kMountPoint, kHeFSEncodingBinary, u8"/network", u8".filetest")); return YES; } -- cgit v1.2.3 From 0c54169b6517fc7acbe4281399fa8146219a8e2c Mon Sep 17 00:00:00 2001 From: Amlal Date: Mon, 5 May 2025 09:56:40 +0200 Subject: feat(kernel): new HeFS version, scheduler allocation tree improvements and reintroduce VEPM. why? - The extents structure on HeFS has to be clearer. - The allocation tracker group has to be organized according to pointer size. - VEPM was scraped because HeFS took time, so now I can focus on it now. Signed-off-by: Amlal --- dev/boot/modules/SysChk/amd64-ahci-epm.json | 1 + dev/boot/modules/SysChk/amd64-pio-epm.json | 1 + dev/kernel/FSKit/HeFS.h | 90 ++++++----- dev/kernel/src/FS/HeFS+FileSystemParser.cc | 158 ++++++------------- dev/kernel/src/MemoryMgr.cc | 2 +- dev/kernel/src/Network/IPCMsg.cc | 8 + dev/kernel/src/UserProcessScheduler.cc | 44 +++--- docs/tex/hefs.tex | 226 ++++++++++++++-------------- tooling/hefs.h | 22 +-- tooling/mkfs.hefs.cc | 2 +- 10 files changed, 258 insertions(+), 296 deletions(-) (limited to 'dev/kernel/src/FS/HeFS+FileSystemParser.cc') diff --git a/dev/boot/modules/SysChk/amd64-ahci-epm.json b/dev/boot/modules/SysChk/amd64-ahci-epm.json index 3c56cfe8..91c95941 100644 --- a/dev/boot/modules/SysChk/amd64-ahci-epm.json +++ b/dev/boot/modules/SysChk/amd64-ahci-epm.json @@ -32,6 +32,7 @@ "__AHCI__", "__SYSCHK__", "BOOTZ_EPM_SUPPORT", + "__NE_VEPM__", "__NE_MODULAR_KERNEL_COMPONENTS__", "kChkVersionHighest=0x0100", "kChkVersionLowest=0x0100", diff --git a/dev/boot/modules/SysChk/amd64-pio-epm.json b/dev/boot/modules/SysChk/amd64-pio-epm.json index 14a804d0..b1b95d8d 100644 --- a/dev/boot/modules/SysChk/amd64-pio-epm.json +++ b/dev/boot/modules/SysChk/amd64-pio-epm.json @@ -33,6 +33,7 @@ "__NE_AMD64__", "__ATA_PIO__", "BOOTZ_EPM_SUPPORT", + "__NE_VEPM__", "kChkVersionHighest=0x0100", "kChkVersionLowest=0x0100", "kChkVersion=0x0100" diff --git a/dev/kernel/FSKit/HeFS.h b/dev/kernel/FSKit/HeFS.h index 255a5381..27fe2838 100644 --- a/dev/kernel/FSKit/HeFS.h +++ b/dev/kernel/FSKit/HeFS.h @@ -17,7 +17,7 @@ /// @file HeFS.h /// @brief HeFS filesystem support. -#define kHeFSVersion (0x0102) +#define kHeFSVersion (0x0103) #define kHeFSMagic " HeFS" #define kHeFSMagicLen (8) @@ -37,7 +37,7 @@ struct HEFS_INDEX_NODE; struct HEFS_INDEX_NODE_DIRECTORY; struct HEFS_JOURNAL_NODE; -enum { +enum : UInt8 { kHeFSHardDrive = 0xC0, // Hard Drive kHeFSSolidStateDrive = 0xC1, // Solid State Drive kHeFSOpticalDrive = 0x0C, // Blu-Ray/DVD @@ -48,7 +48,7 @@ enum { kHeFSDriveCount = 7, }; -enum { +enum : UInt8 { kHeFSStatusUnlocked = 0x18, kHeFSStatusLocked, kHeFSStatusError, @@ -56,18 +56,25 @@ enum { kHeFSStatusCount, }; -enum { - kHeFSEncodingUTF8 = 0x00, - kHeFSEncodingUTF16, - kHeFSEncodingUTF32, - kHeFSEncodingUTF16BE, - kHeFSEncodingUTF16LE, - kHeFSEncodingUTF32BE, - kHeFSEncodingUTF32LE, - kHeFSEncodingUTF8BE, - kHeFSEncodingUTF8LE, - kHeFSEncodingBinary, - kHeFSEncodingCount, +enum : UInt16 { + kHeFSEncodingFlagsUTF8 = 0x50, + kHeFSEncodingFlagsUTF16, + kHeFSEncodingFlagsUTF32, + kHeFSEncodingFlagsUTF16BE, + kHeFSEncodingFlagsUTF16LE, + kHeFSEncodingFlagsUTF32BE, + kHeFSEncodingFlagsUTF32LE, + kHeFSEncodingFlagsUTF8BE, + kHeFSEncodingFlagsUTF8LE, + kHeFSEncodingFlagsBinary, + kHeFSEncodingFlagsCount = 11, + kHeFSFlagsNone = 0, + kHeFSFlagsReadOnly = 0x100, + kHeFSFlagsHidden, + kHeFSFlagsSystem, + kHeFSFlagsArchive, + kHeFSFlagsDevice, + kHeFSFlagsCount = 5 }; inline constexpr UInt16 kHeFSFileKindRegular = 0x00; @@ -107,10 +114,9 @@ struct PACKED HEFS_BOOT_NODE final { Kernel::UInt8 fDiskKind; /// @brief Kind of the drive. (Hard Drive, Solid State Drive, Optical /// Drive, etc). Kernel::UInt8 fEncoding; /// @brief Encoding of the filesystem. (UTF-8, UTF-16, etc). - Kernel::UInt64 fStartIND; /// @brief Start of the INode tree. - Kernel::UInt64 - fEndIND; /// @brief End of the INode tree. it is used to track down the last ind offset. - Kernel::UInt64 fINDCount; /// @brief Number of leafs in the INode tree. + Kernel::UInt64 fStartIND; /// @brief Start of the INode directory tree. + Kernel::UInt64 fEndIND; /// @brief End of the INode directory tree. + Kernel::UInt64 fINDCount; /// @brief Number of leafs in the INode tree. Kernel::UInt64 fDiskSize; /// @brief Size of the disk. (Could be a virtual size, that is not the /// real size of the disk.) Kernel::UInt16 fDiskStatus; /// @brief Status of the disk. (locked, unlocked, error, invalid). @@ -146,9 +152,16 @@ struct PACKED HEFS_INDEX_NODE final { Kernel::UInt32 fUID, fGID; /// @brief User ID and Group ID of the file. Kernel::UInt32 fMode; /// @brief File mode. (read, write, execute, etc). - Kernel::UInt64 fSlices[kHeFSSliceCount]; /// @brief block slice. + /// @brief Extents system by using blocks + /// @details Using an offset to ask fBase, and fLength to compute each slice's length. + Kernel::UInt64 fOffsetSlices; - Kernel::Char fPad[317]; + struct { + Kernel::UInt32 fBase; + Kernel::UInt32 fLength; + } fSlices[kHeFSSliceCount]; /// @brief block slice + + Kernel::Char fPad[309]; }; enum { @@ -162,7 +175,7 @@ enum { /// @details This structure is used to store the directory information of a file. /// @note The directory node is a special type of INode that contains the directory entries. struct PACKED HEFS_INDEX_NODE_DIRECTORY final { - Kernel::UInt64 fHashPath; /// @brief Directory name. + Kernel::UInt64 fHashPath; /// @brief Directory path as FNV hash. Kernel::UInt32 fFlags; /// @brief File flags. Kernel::UInt16 fKind; /// @brief File kind. (Regular, Directory, Block, Character, FIFO, Socket, @@ -271,23 +284,23 @@ inline const Char* hefs_drive_kind_to_string(UInt8 kind) noexcept { inline const Char* hefs_encoding_to_string(UInt8 encoding) noexcept { switch (encoding) { - case kHeFSEncodingUTF8: + case kHeFSEncodingFlagsUTF8: return "UTF-8"; - case kHeFSEncodingUTF16: + case kHeFSEncodingFlagsUTF16: return "UTF-16"; - case kHeFSEncodingUTF32: + case kHeFSEncodingFlagsUTF32: return "UTF-32"; - case kHeFSEncodingUTF16BE: + case kHeFSEncodingFlagsUTF16BE: return "UTF-16BE"; - case kHeFSEncodingUTF16LE: + case kHeFSEncodingFlagsUTF16LE: return "UTF-16LE"; - case kHeFSEncodingUTF32BE: + case kHeFSEncodingFlagsUTF32BE: return "UTF-32BE"; - case kHeFSEncodingUTF32LE: + case kHeFSEncodingFlagsUTF32LE: return "UTF-32LE"; - case kHeFSEncodingUTF8BE: + case kHeFSEncodingFlagsUTF8BE: return "UTF-8BE"; - case kHeFSEncodingUTF8LE: + case kHeFSEncodingFlagsUTF8LE: return "UTF-8LE"; default: return "Unknown"; @@ -318,17 +331,17 @@ inline const Char* hefs_file_kind_to_string(UInt16 kind) noexcept { inline const Char* hefs_file_flags_to_string(UInt32 flags) noexcept { switch (flags) { - case 0x00: + case kHeFSFlagsNone: return "No Flags"; - case 0x01: + case kHeFSFlagsReadOnly: return "Read Only"; - case 0x02: + case kHeFSFlagsHidden: return "Hidden"; - case 0x04: + case kHeFSFlagsSystem: return "System"; - case 0x08: + case kHeFSFlagsArchive: return "Archive"; - case 0x10: + case kHeFSFlagsDevice: return "Device"; default: return "Unknown"; @@ -382,9 +395,6 @@ class HeFileSystemParser final { _Output Bool INodeDirectoryCtl_(_Input DriveTrait* drive, _Input const Int32 flags, const Utf8Char* dir, const BOOL delete_or_create); - - UInt32 mDriveIndex{MountpointInterface::kDriveIndexA}; /// @brief The drive index which this - /// filesystem is mounted on. }; /// @brief Initialize HeFS inside the main disk. diff --git a/dev/kernel/src/FS/HeFS+FileSystemParser.cc b/dev/kernel/src/FS/HeFS+FileSystemParser.cc index e8ffd02a..b3e1d4d0 100644 --- a/dev/kernel/src/FS/HeFS+FileSystemParser.cc +++ b/dev/kernel/src/FS/HeFS+FileSystemParser.cc @@ -23,15 +23,18 @@ namespace Kernel { namespace Detail { /// @brief Forward declarations of internal functions. + /***********************************************************************************/ /// @brief Traverse the RB-Tree of the filesystem. /// @param dir The directory to traverse. /// @param start The starting point of the traversal. /// @note This function is used to traverse the RB-Tree of the filesystem. /// @internal Internal filesystem use only. + /***********************************************************************************/ STATIC ATTRIBUTE(unused) _Output Void hefsi_traverse_tree(HEFS_INDEX_NODE_DIRECTORY* dir, DriveTrait* mnt, const Lba& start_ind, Lba& start, const BOOL try_new = NO); + /***********************************************************************************/ /// @brief Get the index node of a file or directory. /// @param root The root node of the filesystem. /// @param mnt The drive to read from. @@ -39,34 +42,30 @@ namespace Detail { /// @param file_name The name of the file. /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic /// link, unknown). - STATIC ATTRIBUTE(unused) _Output HEFS_INDEX_NODE* hefsi_fetch_index_node( - HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, const Utf8Char* file_name, - UInt8 kind, SizeT* cnt); - - /// @brief Get the index node size. - /// @param root The root node of the filesystem. - /// @param mnt The drive to read from. - /// @param dir_name The name of the directory. - /// @param file_name The name of the file. - /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic - /// link, unknown). - STATIC ATTRIBUTE(unused) _Output SizeT - hefsi_fetch_index_node_size(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, - const Utf8Char* file_name, UInt8 kind); + /***********************************************************************************/ + STATIC ATTRIBUTE(unused) _Output HEFS_INDEX_NODE* hefsi_fetch_in(HEFS_BOOT_NODE* root, + DriveTrait* mnt, + const Utf8Char* dir_name, + const Utf8Char* file_name, + UInt8 kind, SizeT* cnt); + /***********************************************************************************/ /// @brief Allocate a new index node-> /// @param root The root node of the filesystem. /// @param mnt The drive to read/write from. /// @param dir_name The name of the parent directory. /// @return Status, see err_global_get(). + /***********************************************************************************/ STATIC ATTRIBUTE(unused) _Output BOOL hefsi_update_in_status(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, HEFS_INDEX_NODE* node, const BOOL create_or_delete); + /***********************************************************************************/ /// @brief Balance RB-Tree of the filesystem. /// @param root The root node of the filesystem. /// @param mnt The drive to read/write from. /// @return Status, see err_global_get(). + /***********************************************************************************/ STATIC ATTRIBUTE(unused) _Output BOOL hefsi_balance_ind(HEFS_BOOT_NODE* root, DriveTrait* mnt); /// @brief Alllocate IND from boot node. @@ -253,71 +252,6 @@ namespace Detail { kout << "RB-Tree has been rotated.\r"; } - /// @brief Get the index node size. - /// @param root The root node of the filesystem. - /// @param mnt The drive to read from. - /// @param dir_name The name of the directory. - /// @param file_name The name of the file. - /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic - /// link, unknown). - STATIC ATTRIBUTE(unused) _Output SizeT - hefsi_fetch_index_node_size(HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, - const Utf8Char* file_name, UInt8 kind) { - if (mnt) { - HEFS_INDEX_NODE* node = (HEFS_INDEX_NODE*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE)); - HEFS_INDEX_NODE_DIRECTORY* dir = - (HEFS_INDEX_NODE_DIRECTORY*) RTL_ALLOCA(sizeof(HEFS_INDEX_NODE_DIRECTORY)); - - SizeT sz = 0UL; - - auto start = root->fStartIND; - - while (YES) { - mnt->fPacket.fPacketLba = start; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE_DIRECTORY); - mnt->fPacket.fPacketContent = dir; - - mnt->fInput(mnt->fPacket); - - if (!mnt->fPacket.fPacketGood) { - err_global_get() = kErrorFileNotFound; - - return 0; - } - - if (dir->fKind == kHeFSFileKindDirectory) { - if (hefsi_hash_64(dir_name) == dir->fHashPath || - KStringBuilder::Equals(dir_name, kHeFSSearchAllStr)) { - for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; inode_index += 2) { - mnt->fPacket.fPacketLba = dir->fINSlices[inode_index]; - mnt->fPacket.fPacketSize = sizeof(HEFS_INDEX_NODE); - mnt->fPacket.fPacketContent = node; - mnt->fInput(mnt->fPacket); - - if (hefsi_hash_64(file_name) == node->fHashPath && node->fKind == kind) { - if (node->fKind == kHeFSFileKindDirectory) { - sz += hefsi_fetch_index_node_size(root, mnt, dir_name, file_name, kind); - } else { - sz = node->fSize; - } - - return sz; - } - } - } else if (dir->fHashPath == 0) { - break; - } - } - } - - err_global_get() = kErrorSuccess; - return sz; - } - - err_global_get() = kErrorFileNotFound; - return 0; - } - /// @brief Alllocate IND from boot node. /// @param root The root node of the filesystem. /// @param mnt The drive to read from. @@ -520,9 +454,11 @@ namespace Detail { /// @param file_name The name of the file. /// @param kind The kind of the file (regular, directory, block, character, FIFO, socket, symbolic /// link, unknown). - STATIC ATTRIBUTE(unused) _Output HEFS_INDEX_NODE* hefsi_fetch_index_node( - HEFS_BOOT_NODE* root, DriveTrait* mnt, const Utf8Char* dir_name, const Utf8Char* file_name, - UInt8 kind, SizeT* cnt) { + STATIC ATTRIBUTE(unused) _Output HEFS_INDEX_NODE* hefsi_fetch_in(HEFS_BOOT_NODE* root, + DriveTrait* mnt, + const Utf8Char* dir_name, + const Utf8Char* file_name, + UInt8 kind, SizeT* cnt) { if (mnt) { HEFS_INDEX_NODE* node_arr = new HEFS_INDEX_NODE[*cnt]; @@ -536,6 +472,9 @@ namespace Detail { auto start = root->fStartIND; + if (start > root->fEndIND) return nullptr; + if (root->fStartIN > root->fEndIN) return nullptr; + auto start_cnt = 0UL; while (YES) { @@ -557,30 +496,21 @@ namespace Detail { KStringBuilder::Equals(dir_name, kHeFSSearchAllStr)) { if (ke_calculate_crc32((Char*) dir, sizeof(HEFS_INDEX_NODE_DIRECTORY)) != dir->fChecksum) - ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 failure on HeFS IND!"); + ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 checksum failed on HeFS IND!"); for (SizeT inode_index = 0UL; inode_index < kHeFSSliceCount; ++inode_index) { if (dir->fINSlices[inode_index] != 0) { - if (mnt->fPacket.fPacketGood) { - if (ke_calculate_crc32((Char*) node, sizeof(HEFS_INDEX_NODE)) != node->fChecksum) - ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 failure on HeFS IND!"); + if (ke_calculate_crc32((Char*) node, sizeof(HEFS_INDEX_NODE)) != node->fChecksum) + ke_panic(RUNTIME_CHECK_FILESYSTEM, "CRC32 failure on HeFS IND!"); - if (hefsi_hash_64(file_name) == node->fHashPath && node->fKind == kind) { - node_arr[start_cnt] = *node; - ++start_cnt; + if (hefsi_hash_64(file_name) == node->fHashPath && node->fKind == kind) { + node_arr[start_cnt] = *node; + ++start_cnt; - if (start_cnt > *cnt) { - return node_arr; - } + if (start_cnt > *cnt) { + err_global_get() = kErrorSuccess; + return node_arr; } - } else { - err_global_get() = kErrorDiskIsCorrupted; - - delete[] node_arr; - - node_arr = nullptr; - - return nullptr; } } } @@ -592,6 +522,9 @@ namespace Detail { hefsi_traverse_tree(dir, mnt, root->fStartIND, start, YES); if (start > root->fEndIND || start == 0) break; } + + err_global_get() = kErrorSuccess; + return node_arr; } kout << "Error: Failed to find index node->\r"; @@ -710,7 +643,7 @@ namespace Detail { mnt->fOutput(mnt->fPacket); mm_delete_heap(dir); - + return YES; } } @@ -921,11 +854,12 @@ _Output Bool HeFileSystemParser::Format(_Input _Output DriveTrait* drive, _Input drive->fOutput(drive->fPacket); - (Void)(kout << "Drive kind: " << drive->fProtocol() << kendl); - (Void)(kout8 << u8"Volume name: " << root->fVolName << kendl8); + (Void)(kout << "Protocol: " << drive->fProtocol() << kendl); + (Void)(kout8 << u8"Volume Name: " << root->fVolName << kendl8); (Void)(kout << "Start IND: " << hex_number(root->fStartIND) << kendl); (Void)(kout << "Number of IND: " << hex_number(root->fINDCount) << kendl); - (Void)(kout << "Sector size: " << hex_number(root->fSectorSize) << kendl); + (Void)(kout << "Sector Size: " << hex_number(root->fSectorSize) << kendl); + (Void)(kout << "Drive Kind:" << Detail::hefs_drive_kind_to_string(root->fDiskKind) << kendl); if (!drive->fPacket.fPacketGood) { err_global_get() = kErrorDiskIsCorrupted; @@ -937,7 +871,7 @@ _Output Bool HeFileSystemParser::Format(_Input _Output DriveTrait* drive, _Input u8"/network", u8"/devices", u8"/media"}; for (SizeT i = 0; i < kHeFSPreallocateCount; ++i) { - this->CreateINodeDirectory(drive, kHeFSEncodingUTF8, kFileMap[i]); + this->CreateINodeDirectory(drive, kHeFSEncodingFlagsUTF8, kFileMap[i]); } err_global_get() = kErrorSuccess; @@ -1128,12 +1062,16 @@ Boolean fs_init_hefs(Void) { HeFileSystemParser parser; - parser.Format(&kMountPoint, kHeFSEncodingUTF8, kHeFSDefaultVoluneName); + parser.Format(&kMountPoint, kHeFSEncodingFlagsUTF8, kHeFSDefaultVoluneName); - MUST_PASS(parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8".filetest")); - MUST_PASS(parser.DeleteINode(&kMountPoint, kHeFSEncodingBinary, u8"/boot", u8".filetest")); - MUST_PASS(parser.CreateINode(&kMountPoint, kHeFSEncodingBinary, u8"/network", u8".filetest")); - MUST_PASS(parser.DeleteINode(&kMountPoint, kHeFSEncodingBinary, u8"/network", u8".filetest")); + MUST_PASS(parser.CreateINode(&kMountPoint, kHeFSEncodingFlagsBinary | kHeFSFlagsReadOnly, + u8"/boot", u8".filetest")); + MUST_PASS(parser.DeleteINode(&kMountPoint, kHeFSEncodingFlagsBinary | kHeFSFlagsReadOnly, + u8"/boot", u8".filetest")); + MUST_PASS(parser.CreateINode(&kMountPoint, kHeFSEncodingFlagsBinary | kHeFSFlagsReadOnly, + u8"/network", u8".filetest")); + MUST_PASS(parser.DeleteINode(&kMountPoint, kHeFSEncodingFlagsBinary | kHeFSFlagsReadOnly, + u8"/network", u8".filetest")); return YES; } diff --git a/dev/kernel/src/MemoryMgr.cc b/dev/kernel/src/MemoryMgr.cc index cb33753d..001f970a 100644 --- a/dev/kernel/src/MemoryMgr.cc +++ b/dev/kernel/src/MemoryMgr.cc @@ -26,7 +26,7 @@ //! @brief Heap algorithm that serves as the main memory manager. #define kMemoryMgrMagic (0xD4D75) -#define kMemoryMgrAlignSz (4) +#define kMemoryMgrAlignSz (4U) namespace Kernel { /// @brief Implementation details. diff --git a/dev/kernel/src/Network/IPCMsg.cc b/dev/kernel/src/Network/IPCMsg.cc index b3c9d9fd..e89e7c1b 100644 --- a/dev/kernel/src/Network/IPCMsg.cc +++ b/dev/kernel/src/Network/IPCMsg.cc @@ -9,8 +9,10 @@ #include namespace Kernel { +/***********************************************************************************/ /// @internal internal use for IPC system only. /// @brief The internal sanitize function. +/***********************************************************************************/ Bool ipc_int_sanitize_packet(IPC_MSG* pckt) { auto endian = RTL_ENDIAN(pckt, ((Char*) pckt)[0]); @@ -45,9 +47,11 @@ ipc_check_failed: return false; } +/***********************************************************************************/ /// @brief Sanitize packet function /// @retval true packet is correct. /// @retval false packet is incorrect and process has crashed. +/***********************************************************************************/ Bool ipc_sanitize_packet(IPC_MSG* pckt) { if (!pckt || !ipc_int_sanitize_packet(pckt)) { return false; @@ -56,9 +60,11 @@ Bool ipc_sanitize_packet(IPC_MSG* pckt) { return true; } +/***********************************************************************************/ /// @brief Construct packet function /// @retval true packet is correct. /// @retval false packet is incorrect and process has crashed. +/***********************************************************************************/ Bool ipc_construct_packet(_Output IPC_MSG** pckt_in) { // don't act if it's not even valid. if (!pckt_in) return false; @@ -87,9 +93,11 @@ Bool ipc_construct_packet(_Output IPC_MSG** pckt_in) { return No; } +/***********************************************************************************/ /// @brief Pass message from **src** to **target** /// @param src Source message. /// @param target Target message. +/***********************************************************************************/ Bool IPC_MSG::Pass(IPC_MSG* src, IPC_MSG* target) noexcept { if (src && target && (target != src)) { if (src->IpcMsgSz > target->IpcMsgSz) return No; diff --git a/dev/kernel/src/UserProcessScheduler.cc b/dev/kernel/src/UserProcessScheduler.cc index 45a95b5b..dbe3882f 100644 --- a/dev/kernel/src/UserProcessScheduler.cc +++ b/dev/kernel/src/UserProcessScheduler.cc @@ -97,6 +97,7 @@ Void USER_PROCESS::Wake(Bool should_wakeup) { /***********************************************************************************/ /** @brief Allocate pointer to heap tree. */ +/** @param tree The tree to calibrate */ /***********************************************************************************/ STATIC USER_PROCESS::USER_HEAP_TREE* sched_try_go_upper_heap_tree( @@ -141,13 +142,13 @@ ErrorOr USER_PROCESS::New(SizeT sz, SizeT pad_amount) { if (!this->HeapTree) { this->HeapTree = new USER_HEAP_TREE(); - this->HeapTree->MemoryColor = USER_HEAP_TREE::kBlackMemory; - this->HeapTree->MemoryEntryPad = pad_amount; this->HeapTree->MemoryEntrySize = sz; this->HeapTree->MemoryEntry = ptr; + this->HeapTree->MemoryColor = USER_HEAP_TREE::kBlackMemory; + this->HeapTree->MemoryPrev = nullptr; this->HeapTree->MemoryNext = nullptr; this->HeapTree->MemoryParent = nullptr; @@ -163,32 +164,41 @@ ErrorOr USER_PROCESS::New(SizeT sz, SizeT pad_amount) { prev_entry = entry; - if (entry->MemoryNext) { - is_parent = NO; - entry = entry->MemoryNext; - } else if (entry->MemoryChild) { + if (entry->MemoryColor == USER_HEAP_TREE::kBlackMemory) break; + + if (entry->MemoryChild && entry->MemoryChild->MemoryEntrySize > 0 && + entry->MemoryChild->MemoryEntrySize == sz) { entry = entry->MemoryChild; is_parent = YES; + } else if (entry->MemoryNext && entry->MemoryChild->MemoryEntrySize > 0 && + entry->MemoryNext->MemoryEntrySize == sz) { + is_parent = NO; + entry = entry->MemoryNext; } else { entry = sched_try_go_upper_heap_tree(entry); + if (entry && entry->MemoryColor == USER_HEAP_TREE::kBlackMemory) break; } } - if (!entry) entry = new USER_HEAP_TREE(); + auto new_entry = new USER_HEAP_TREE(); - entry->MemoryEntry = ptr; - entry->MemoryEntrySize = sz; - entry->MemoryEntryPad = pad_amount; + new_entry->MemoryEntry = ptr; + new_entry->MemoryEntrySize = sz; + new_entry->MemoryEntryPad = pad_amount; + new_entry->MemoryParent = entry; + new_entry->MemoryChild = nullptr; + new_entry->MemoryNext = nullptr; + new_entry->MemoryPrev = nullptr; - if (is_parent) { - entry->MemoryParent = prev_entry; - prev_entry->MemoryChild = entry; + new_entry->MemoryColor = USER_HEAP_TREE::kBlackMemory; + prev_entry->MemoryColor = USER_HEAP_TREE::kRedMemory; - prev_entry->MemoryColor = USER_HEAP_TREE::kBlackMemory; - entry->MemoryColor = USER_HEAP_TREE::kRedMemory; + if (is_parent) { + prev_entry->MemoryChild = new_entry; + new_entry->MemoryParent = prev_entry; } else { - prev_entry->MemoryNext = entry; - entry->MemoryPrev = prev_entry; + prev_entry->MemoryNext = new_entry; + new_entry->MemoryPrev = prev_entry; } } diff --git a/docs/tex/hefs.tex b/docs/tex/hefs.tex index 5aa9c59b..afafc472 100644 --- a/docs/tex/hefs.tex +++ b/docs/tex/hefs.tex @@ -1,157 +1,151 @@ \documentclass{article} -\usepackage[a4paper, margin=1in]{geometry} -\usepackage{amsmath, amssymb} -\usepackage{listings} -\usepackage{xcolor} -\usepackage{graphicx} -\usepackage{enumitem} -\usepackage{caption} +\usepackage[utf8]{inputenc} +\usepackage{geometry} \usepackage{longtable} - -\definecolor{lightgray}{gray}{0.95} - -\lstdefinestyle{cstyle}{ - language=C++, - backgroundcolor=\color{lightgray}, - basicstyle=\ttfamily\small, - keywordstyle=\color{blue}, - commentstyle=\color{green!60!black}, - stringstyle=\color{orange}, - numbers=left, - numberstyle=\tiny, - breaklines=true, - frame=single, - showstringspaces=false -} - -\title{HeFS (High-Throughput Extended File System) Specification} +\usepackage{listings} +\geometry{margin=1in} +\title{HeFS Filesystem Specification (v0x0103)} \author{Amlal El Mahrouss} -\date{2024-2025} +\date{2025} \begin{document} \maketitle \section{Overview} -HeFS is a high-throughput filesystem designed for NeKernel. It implements a robust directory structure based on red-black trees, uses slice-linked blocks for file storage, and includes CRC32-based integrity checks. Designed for desktop, server, and embedded contexts, it prioritizes performance, corruption recovery, and extensibility. +The High-throughput Extended File System (HeFS) is a custom filesystem tailored for performance, structure, and compact representation. It uses red-black trees for directory indexing, sparse block slicing for file layout, and fixed-size metadata structures optimized for 512-byte sector alignment. -\section{Boot Node Structure} -\begin{longtable}{|l|l|p{8cm}|} +\section{Constants and Macros} +\begin{longtable}{|l|l|} \hline -\textbf{Field} & \textbf{Type} & \textbf{Description} \\ +\textbf{Name} & \textbf{Value / Description} \\ \hline -\verb|fMagic| & \verb|char[8]| & Filesystem magic (" HeFS") \\ -\verb|fVolName| & \verb|Utf8Char[128]| & Volume name \\ -\verb|fVersion| & \verb|UInt32| & Filesystem version (e.g., 0x0102) \\ -\verb|fBadSectors| & \verb|UInt64| & Number of bad sectors detected \\ -\verb|fSectorCount| & \verb|UInt64| & Total sector count \\ -\verb|fSectorSize| & \verb|UInt64| & Size of each sector \\ -\verb|fChecksum| & \verb|UInt32| & CRC32 checksum of the boot node \\ -\verb|fDiskKind| & \verb|UInt8| & Type of drive (e.g., HDD, SSD, USB) \\ -\verb|fEncoding| & \verb|UInt8| & Encoding mode (UTF-8, UTF-16, etc.) \\ -\verb|fStartIND| & \verb|UInt64| & Starting LBA of inode directory region \\ -\verb|fEndIND| & \verb|UInt64| & Ending LBA of inode directory region \\ -\verb|fINDCount| & \verb|UInt64| & Number of directory nodes allocated \\ -\verb|fDiskSize| & \verb|UInt64| & Logical size of the disk \\ -\verb|fDiskStatus| & \verb|UInt16| & Status of the disk (e.g., unlocked, locked) \\ -\verb|fDiskFlags| & \verb|UInt16| & Disk flags (e.g., read-only) \\ -\verb|fVID| & \verb|UInt16| & Virtual ID (for EPM integration) \\ +\texttt{kHeFSVersion} & 0x0103 \\ +\texttt{kHeFSMagic} & " HeFS" (8-byte magic identifier) \\ +\texttt{kHeFSFileNameLen} & 256 characters \\ +\texttt{kHeFSPartNameLen} & 128 characters \\ +\texttt{kHeFSMinimumDiskSize} & 16 MiB \\ +\texttt{kHeFSDefaultVoluneName} & "HeFS Volume" \\ +\texttt{kHeFSINDStartOffset} & Offset after boot + dir nodes \\ +\texttt{kHeFSSearchAllStr} & "\*" (wildcard string) \\ \hline \end{longtable} -\section{File Types and Flags} -\subsection*{File Kinds} -\begin{itemize}[label=--] - \item \verb|0x00| --- Regular File - \item \verb|0x01| --- Directory - \item \verb|0x02| --- Block Device - \item \verb|0x03| --- Character Device - \item \verb|0x04| --- FIFO - \item \verb|0x05| --- Socket - \item \verb|0x06| --- Symbolic Link - \item \verb|0x07| --- Unknown +\section{Disk and File Metadata Enums} + +\subsection{Drive Kind (\texttt{UInt8})} +\begin{itemize} +\item 0xC0: Hard Drive +\item 0xC1: Solid State Drive +\item 0x0C: Optical Drive +\item 0xCC: USB Mass Storage +\item 0xC4: SCSI Drive +\item 0xC6: Flash Drive +\item 0xFF: Unknown +\end{itemize} + +\subsection{Disk Status (\texttt{UInt8})} +\begin{itemize} +\item 0x18: Unlocked +\item 0x19: Locked +\item 0x1A: Error +\item 0x1B: Invalid +\end{itemize} + +\subsection{Encoding Flags (\texttt{UInt16})} +\begin{itemize} +\item UTF-8, UTF-16, UTF-32, Binary (with endianness variants) \end{itemize} -\subsection*{Drive Types} -\begin{itemize}[label=--] - \item \verb|0xC0| --- Hard Drive - \item \verb|0xC1| --- Solid State Drive - \item \verb|0x0C| --- Optical Drive - \item \verb|0xCC| --- USB Mass Storage - \item \verb|0xC4| --- SCSI/SAS Drive - \item \verb|0xC6| --- Flash Drive +\subsection{File Kinds (\texttt{UInt16})} +\begin{itemize} +\item 0x00: Regular File +\item 0x01: Directory +\item 0x02: Block Device +\item 0x03: Character Device +\item 0x04: FIFO +\item 0x05: Socket +\item 0x06: Symbolic Link +\item 0x07: Unknown \end{itemize} -\section{Index Node Structure} -The `HEFS\_INDEX\_NODE` represents a file and is constrained to 512 bytes to match hardware sector boundaries. It uses a fixed set of block pointers (slices) and CRC32 checks for data integrity. Only the local file name is stored in `fName`. +\subsection{File Flags (\texttt{UInt32})} +\begin{itemize} +\item ReadOnly, Hidden, System, Archive, Device +\end{itemize} -\begin{lstlisting}[style=cstyle, caption={HEFS\_INDEX\_NODE (Fits 512B)}] -struct HEFS_INDEX_NODE { - UInt64 fHashPath; // Local file name, hashed. - UInt32 fFlags; - UInt16 fKind; - UInt32 fSize; - UInt32 fChecksum; +\section{Structures} - Boolean fSymLink; - ATime fCreated, fAccessed, fModified, fDeleted; - UInt32 fUID, fGID; - UInt32 fMode; +\subsection{HEFS\_BOOT\_NODE} +Acts as the superblock. - UInt64 fSlices[16]; // Data block slices (start-only) - Char fPad[317]; // Padding to reach 512B -}; -\end{lstlisting} +\begin{itemize} + \item \texttt{fMagic}, \texttt{fVolName}, \texttt{fVersion}, \texttt{fChecksum} + \item Sector and disk geometry: \texttt{fSectorCount}, \texttt{fSectorSize}, \texttt{fBadSectors} + \item Drive info: \texttt{fDiskKind}, \texttt{fEncoding}, \texttt{fDiskStatus}, \texttt{fDiskFlags}, \texttt{fVID} + \item Tree layout: \texttt{fStartIND}, \texttt{fEndIND}, \texttt{fINDCount} + \item Reserved: \texttt{fStartIN}, \texttt{fEndIN}, \texttt{fReserved}, \texttt{fReserved1} +\end{itemize} -\section{Directory Node Structure} -Directories form a red-black tree. Each node (IND) can hold up to 16 index node references and links to its parent, siblings, and children via LBAs. +\subsection{HEFS\_INDEX\_NODE} +Contains file metadata and block layout. -\begin{lstlisting}[style=cstyle, caption={HEFS\_INDEX\_NODE\_DIRECTORY}] -struct HEFS_INDEX_NODE_DIRECTORY { - UInt64 fHashPath; // Directory path as hash - UInt32 fFlags; - UInt16 fKind; - UInt32 fEntryCount; - UInt32 fChecksum; +\begin{itemize} + \item \texttt{fHashPath}, \texttt{fFlags}, \texttt{fKind}, \texttt{fSize}, \texttt{fChecksum} + \item Symbolic link: \texttt{fSymLink} + \item Time: \texttt{fCreated}, \texttt{fAccessed}, \texttt{fModified}, \texttt{fDeleted} + \item Ownership: \texttt{fUID}, \texttt{fGID}, \texttt{fMode} + \item Block data: \texttt{fOffsetSlices}, \texttt{fSlices[kHeFSSliceCount]} as (base, length) pairs +\end{itemize} - ATime fCreated, fAccessed, fModified, fDeleted; - UInt32 fUID, fGID; - UInt32 fMode; +\subsection{HEFS\_INDEX\_NODE\_DIRECTORY} +Red-black tree based directory node. - UInt64 fINSlices[16]; // Inode LBA references +\begin{itemize} + \item \texttt{fHashPath}, \texttt{fFlags}, \texttt{fKind}, \texttt{fEntryCount}, \texttt{fChecksum} + \item Time and ownership same as inode + \item \texttt{fINSlices[kHeFSSliceCount]} for storing child inodes + \item Tree links: \texttt{fColor}, \texttt{fNext}, \texttt{fPrev}, \texttt{fChild}, \texttt{fParent} +\end{itemize} - UInt8 fColor; // Red/Black tree color - Lba fNext, fPrev, fChild, fParent; +\section{Timestamp Layout (ATime)} - Char fPad[285]; -}; -\end{lstlisting} +\texttt{ATime} is a 64-bit timestamp with the following structure: -\section{Design Characteristics} +\begin{itemize} + \item Bits 63-32: Year + \item Bits 31-24: Month + \item Bits 23-16: Day + \item Bits 15-8: Hour + \item Bits 7-0: Minute +\end{itemize} +Constants: \begin{itemize} - \item Red-black tree traversal for directory balancing - \item One-sector (512B) inode design for efficient I/O - \item Slice-linked file storage (fixed 16 slots) - \item CRC32 for boot node, inode, and directory integrity - \item Preallocated directory inodes to avoid runtime fragmentation + \item \texttt{kHeFSTimeInvalid = 0x0} + \item \texttt{kHeFSTimeMax = 0xFFFFFFFFFFFFFFFF - 1} \end{itemize} -\section{Minimum Requirements} +\section{Filesystem API} + +Provided by \texttt{Kernel::HeFS::HeFileSystemParser}. \begin{itemize} - \item Minimum disk size: 16MB - \item Recommended size: 8GB or more - \item Supported media: HDD, SSD, USB, SCSI, Flash, Optical + \item \texttt{Format(drive, flags, name)} - Format drive with HeFS + \item \texttt{CreateINodeDirectory(drive, flags, dir)} + \item \texttt{RemoveINodeDirectory(drive, flags, dir)} + \item \texttt{CreateINode(drive, flags, dir, name)} + \item \texttt{DeleteINode(drive, flags, dir, name)} + \item \texttt{WriteINode(drive, block, size, dir, name)} + \item \texttt{ReadINode(drive, block, size, dir, name)} \end{itemize} -\section{Future Work} +Internal helpers: \begin{itemize} - \item Journaling layer for recovery - \item Extended access control and ACL support - \item Logical Volume Management (LVM) - \item Dual boot node layout for redundancy - \item Self-healing and online fsck tools + \item \texttt{INodeCtl\_}, \texttt{INodeDirectoryCtl\_} \end{itemize} +\section{Conclusion} +HeFS provides a modern and compact approach to high-performance file storage. Its use of red-black trees, fixed-size metadata, slice-based sparse files, and minimal overhead makes it a strong candidate for embedded and performance-sensitive use cases. + \end{document} diff --git a/tooling/hefs.h b/tooling/hefs.h index 99d04768..ded6cbef 100644 --- a/tooling/hefs.h +++ b/tooling/hefs.h @@ -43,17 +43,17 @@ enum { // Encodings enum { - kHeFSEncodingUTF8 = 0x00, - kHeFSEncodingUTF16, - kHeFSEncodingUTF32, - kHeFSEncodingUTF16BE, - kHeFSEncodingUTF16LE, - kHeFSEncodingUTF32BE, - kHeFSEncodingUTF32LE, - kHeFSEncodingUTF8BE, - kHeFSEncodingUTF8LE, - kHeFSEncodingBinary, - kHeFSEncodingCount, + kHeFSEncodingFlagsUTF8 = 0x00, + kHeFSEncodingFlagsUTF16, + kHeFSEncodingFlagsUTF32, + kHeFSEncodingFlagsUTF16BE, + kHeFSEncodingFlagsUTF16LE, + kHeFSEncodingFlagsUTF32BE, + kHeFSEncodingFlagsUTF32LE, + kHeFSEncodingFlagsUTF8BE, + kHeFSEncodingFlagsUTF8LE, + kHeFSEncodingFlagsBinary, + kHeFSEncodingFlagsCount, }; // Time type diff --git a/tooling/mkfs.hefs.cc b/tooling/mkfs.hefs.cc index 23772023..bc1f3d3c 100644 --- a/tooling/mkfs.hefs.cc +++ b/tooling/mkfs.hefs.cc @@ -74,7 +74,7 @@ int main(int argc, char** argv) { bootNode.version = kVersion; bootNode.diskKind = mkfs::hefs::kHeFSHardDrive; - bootNode.encoding = mkfs::hefs::kHeFSEncodingUTF8; + bootNode.encoding = mkfs::hefs::kHeFSEncodingFlagsUTF8; bootNode.diskSize = kDiskSize; bootNode.sectorSize = kSectorSize; bootNode.startIND = start_ind; -- cgit v1.2.3