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/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 ++++---- 5 files changed, 134 insertions(+), 168 deletions(-) (limited to 'dev/kernel') 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; } } -- cgit v1.2.3