编程技术-Apple HFS+文件系统可视化分析

起因

因需要编译调试XNU内核, 需要更改安装镜像BaseSystem.img, 但是OpenCore在HFS+的支持有问题, 在修改镜像后读取不到BootKernelExtensions.kc. 所要了解HFS+才能修改OpenCore.
HFS+也是比较老的文件系统, 现在macos默认都是APFS, 但应该是HFS+因为比较轻巧简单,所以苹果才保留在系统安装盘上.
HFS+有官方开源项目, 不过是内核模块, 而且比较杂乱, 直接从源码分析不容易理解,最好编写demo进行辅助.
!! HFS+好像是历史PowerPC的原因使用的是大端序（Big-endian）, 文件名也是大端序的unicode!!

环境

• macOS
• 010 Editor + Drive Template
• HFS源码
• ChatGPT/GitHub Copilot/阿里云通义

GPT分区和HFS分区头结构

GPT分区非常简单, 可以找到HFS+的FirstLBA即可,使用ChatGPT可以直接给出解析代码.

HFS+分区头,源码

以上结构可以先不用太详细了解, 先了解大概结构和思路, 才能方便理解, 不然只是通过文字和代码还是很难理解.

BTree索引结构

需要理解的专业名词

• Tree和BTree
• 二分查找 (Binary Search)
• 复合索引(Composite Index)

结构简介

首先要大概了解BTree的索引结构, 所有的文件和目录的查找都需要通BTree进行查找, BTree树的高度是动态调整的, 如果整个分区的文件越多,BTree树就会越高.同一层高度的节点(Node)也是相互前后链接的.

文件检索

检索是通过文件和目录父层ID和文件名进行检索的(复合索引), , Index Node都有子层的最开开始的目录ID和最小的文件名(子层可以是末端树吐(Leaf), 也可以是子Index).(目录ID要从小到大存放, 文件名也要排列进行从小到大存放)

index Node下如果还是index Node, 那它包含的是它的子Index最小的父母目录ID和最小的文件名.如果目录比较大,子Index可能会有多个相同的父母目录ID,所以一定要有文件名,且是排序后最小的, 这样只要从一层的index node最确定要找的文件所在子节点, 直到末端树叶(高度为1).Node下的记录使用二分查找.

Node结构

Inex和Leaf Node的结构都是同一的, HFS+都是尽量复用和统一结构, Record的结构是由Descriptor中的Kind确定的.(注意,Node因为文件名长度不一, 它每个Record的大小不是固定的, 如果固定最大长度255, 那浪费比较多的空间)

Inex和Leaf Node使用时不是使用完一个Node再使用下一下, 而且是只先使用大概20%的容量, 这样添加和删除记录时,尽量不需要修改多个Node. 本文章只大概介绍结构, 修改的逻辑涉及到更多更深的算法.这里只略微带过.

文件结构

每个文件都有一个ForkData, 一个ForkData有8个Extent, 每个Extent有指向具体的块startBlock和多个块blockCount, 但如果分区碎片化比较严重, 那会超过8个Extent,那要到Extents BTree再检索相应的ForkData

文件系统的碎片化问题都是所有文件系统都无法避免的, HFS+碎片化越严重需要越多个扩展ForkData.会导致读取文件时效率下降越严重. HFS+它的设计理念似乎不是优先使用空白的大的区域, 而是先把前面能用的空白的块先用上, 这个设计不太合理.这个有了解的可以评论交流一下.

OpenCore OpenHfsPlus模块问题

解决最开始的Opencore的OpenHfsPlus模块的问题, 其实也不是问题,而是作者没有实现读超过默认8个Extent(作者叫它分片fragments), 作者有写注释没有实现.相关代码:

深入

需要完整的读完HFS源码, 并了解XNU系统才能真正了解HFS, 因为它只是内核驱动的一部分, 它需要内核系统的缓存系统, 线程锁系统等. HFS的管理逻辑还有很多, 插入删除时索引的重建,调整BTree的高度等. 创建文件ID确保多线程下的唯一性等
~
黑苹果, XNU内核交流可QQ: 3=1=0=4=1=9=0=6=2 (倒序)
~