基于B树的HFS+文件系统

尽管如今的操作系统在驱动程序的帮助下支持任何的文件系统，但是每一个操作系统都会有一个自己“原生”的文件系统，DOS的原生文件系统是FAT。Windows的原生文件系统是NTFS。Linux的是Ext2/3/4。OS X 也不例外，HFS+ 是OS X 的原生文件系统。

HFS+文件系统概念

时间戳

HFS+采用一个无符号整数记录自格林治时间1904年1月1日零点到现在的秒数表示的时间。

访问控制表

传统UNIX 在inode层就提供了权限机制，然而这些权限局限性非常大，仅仅是遵循了用户/组/其他的简单模型。通过访问控制表(ACL)可以精确地设置系统上任何用户和任何组的具体权限，这种方式类似Windows 的权限系统，要注意的是，ACL实际上是一项VFS的特性，而不是HFS+的特性，然而为了能支持ACL，底层文件系统必须支持扩展属性(HFS+就支持)

扩展属性

文件除了由包含实际数据和权限信息的块组成之外，还有额外的属性信息。这些属性信息通常称为扩展属性(extended attribute)。扩展属性一般是透明的，任何人都可以设置扩展属性，OS X 采用了逆DNS的命名约定以确保属性名称的唯一性。

fork

fork 最初是由苹果发明的一项概念(在最早的HFS中)，后来被微软用在NTFS中(在NTFS中称为“交替数据流(alternate data stream)”)。一个fork很像一个扩展属性，因为都可以用于表示额外的元数据，但是更适合于单独放在另一个相关文件中的数据。扩展属性有大小限制，而fork则没有这样的限制。OS X 中大量使用资源fork的一个地方是别名(alias)。别名很好地利用了资源fork。别名被创建(甚至重命名)时，会有一个Finder 扩展属性(com.apple.FinderInfo)指定alisMACS，还有一个资源fork指定原始文件的一些特性，还包括图标。有趣的是，别名文件往往比原文件占用的磁盘空间多。

压缩

文件压缩是HFS+最强大的特性之一。压缩的方式是将数据fork留空，然后将压缩后的数据放在资源fork中，并且通过一个扩展属性com.apple.decmpfs将文件标记为压缩。OS X的程序默默地对系统文件进行实时解压缩操作，而且扩展属性工具xattr(1)会自动忽略用于压缩的扩展属性com.apple.defcmpfs。内核通过特殊的AppleFSCompressionTypeZlib.kext扩展支持实时压缩功能。HFS+压缩的过程如下：

• 文件被当成是64K大小数据块的数组
• 小文件通过Typel 压缩，数据以未压缩的形式保存在扩展属性中
• 较大的文件如果仍然在一个块内可以放进com.apple.decmpfs扩展属性，则保存在扩展属性中
• 所有其他较大的文件都被压缩，并保存在文件的资源fork中。注意在这种情况下，文件自己本身可能没有资源fork
• 扩展属性和资源fork被添加到文件中
• 实际的文件大小重编码为0，然后通过chflags(2)将文件标记为压缩

Unicode 支持

HFS+ 通过Unicode解决了国际化的问题。Unicode有很多变体，HFS+采用的是UTF-16编码：双字节Unicode。文件名的长度最长可达255个字符(510个字节)。HFS+内部使用的数据结构为HFSUniStr255。

Finder 集成

HFS+ 和 OS X Finder结合很紧密。宗卷头和单个的编录条目中都有一个特殊的Finder信息字段，其中包含了由Finder使用的标志位。具体的内容取决于是文件还是文件夹。

大小写敏感(HFSX)

文件系统可以定义为大小写不敏感或大小写敏感，区别在于比较文件名时是否考虑字母的大小写。此外，尽管文件系统可以是大小写不敏感的，但是仍然可以保留大小写：即文件名保存时按照传入的大小写原样保存，而且在后续操作中依然保存原始的大小写状态。HFS+是大小写不敏感，但是保留大小写的文件系统。OS X 还支持一种新的变种 HFSX，可以设置为大小写敏感。OS X 默认使用 HFS+。iOS 使用启用了大小写敏感的HFSX。大小写保留(HFS+)和大小写敏感(HFSX)的决定只能在分区时进行一次(通过Disk Utility 应用程序或命令行程序diskutil(8)进行分区操作)。因为这个决定会影响编录树种的顺序

日志

文件事务可以异常复杂，特别是写操作可能会跨越多个数据块。在断电或其他崩溃的情况下，如果一个写操作事务中只有部分数据写入了底层媒体，那么这种写操作会导致数据损坏。日志(journaling)是一项试图解决这个问题的技术。日记是磁盘中一块特殊的区域，用户看不见这个区域，文件系统在向磁盘提交事务之前会将事务记录在这个区域中。如果修改事务被成功提交，那么这些事务就会在日志中删除。但是如果发生了崩溃，文件系统可以快速恢复到一致的状态：要么重放日志(即提交所有记录的事务)，要么回滚日志(如果包含未完成的事务)。日志并不能完美解决数据丢失，但是可以显著地减少系统崩溃导致文件系统无法使用的情况。现代的文件系统，例如Linux 的Ext3 和微软的NTFS都是支持日志的。HFS+挂载时可以选中支持或不支持日志，记录日志是默认选项，不过基于SSD的Mac可能会通过禁用日志获得一些好处(因为擦除日志的操作会缩短底层闪存芯片的寿命)

动态大小调节

HFS+宗卷的大小可以动态调整，即使是在宗卷处于挂载的状态。这是一项高级功能，有一些文件系统不支持这项功能(例如XFS只支持增大但是不支持缩小)。HFS+的大小调整是通过hfs_extendfs( )完成的，在用户态可以通过ioctl(2)传入HFS_RESIZE_VOLUME操作、sysctl(2)传入HFS_EXTEND_FS操作以及在Disk Unility图形界面中调整HFS+分区右下角的把手对HFS+分区大小进行调节

元数据区域

元数据区域(metadata zone)是OS X 10.3引入的。元数据区域在系统卷后面，包含了文件系统的内部结构(靠着热文件区域)。这个区域故意安排在宗卷开头处，这样可以减少定位时间。在满足以下条件时，hfs_metadatazone_init( )函数会开启元数据区域：

• 宗卷大小至少为10GB
• 宗卷开启了日志
• 调用者没有显式地要求禁用这个区域(通过fsctl)

元数据区域内禁止分配普通的文件(除非系统中数据块异常短缺)。这个区域包含了文件系统使用的文件和数据结构。其中hfs_virturalmetafile( )函数的作用是查找一个文件是否属于元数据区域。

热文件

HFS+有一项很有意思很特别的特性是能够动态适应频繁访问的文件。HFS+为每一个文件维护一个热度值(temperature)。热度值是通过文件被读取的字节数除以文件大小得到(向下转换为unit32_t值)。这个计算得到的值和文件大小成反比，因此热度更倾向于小文件，小文件的内容经常被频繁访问。热度值超过了HFC_MINIMUM_TEMPERATURE的文件成为“热文件”，会被添加到元数据区域中的一个特殊B树中，这个B树维护了最多HFC_MAXIMUM_FILE_COUNT个条目，这些热文件的数据块也被转移到了元数据区域。热文件B树是一个普通的文件，由hfc_create( )创建，这个文件设置FndrFileInfo标志位(kIsInvisible+kNameLocked)，因此这个文件的文件名无法被修改，而且在Finder中看不见。

动态碎片整理

文件碎片化是所有文件系统的噩梦：随着系统不断创建、修改和删除文件，文件被删除的位置开始出现“空洞”，当文件需要扩大而没有连续的空间时，就会产生文件碎片。尽管文件系统中存在足够的空间，但是如果这些空间都被分割为零散小空间，那么文件分配就不会特别高效。HFS+能够在工作时进行碎片整理工作。hfs_relocate( )函数会处理这些情况。hfs_vnop( )尝试重新安置被认为是严重碎片化的文件。将热文件移入或移出元数据区域也能够帮助碎片整理，因为文件的移动是通过调用hfs_relocate( )完成的。

HFS+的设计概念

HFS+中的“+”意味着HFS+是前一代(层次文件系统(HFS))的增强版。HFS的设计在HFS+中并没有重大改变。这两个文件系统底层的思想是一致的。HFS+的主要改进是增加了字段和记录的大小，从而支持更多的文件，支持的文件大小也更大。

B树基础知识

B树(B-Tree)是一些文件系统构建的基础。例如NTFS(Windows)、Ext4(Linux)以及苹果的NFS以及NFS+。

采用B树的动机

任何文件系统中最基本的概念就是用于保存和取得文件的机制。文件系统需要提供一种机制能够满足一下运行时的需求：

• 搜索
• 插入
• 更新
• 随机访问

尽管有一些文件系统依然采用基于分配表的方式(例如FAT、FAT32以及最近的ExFat都是采用“文件分配表”的文件系统)，但是大部分文件系统都 采用了基于树的方案。
B树可以看出是二叉树的扩展，相似的地方在于都采用树形结构，而不同的地方在于B书的节点可以有任意数据的子节点。这种结构可以帮助限制树的深度。

B树节点

B树由节点(node)组成，B树的节点可以有具体的子类型或称为kind。不同的节点类型可以保存不同的数据，但是所有类型的节点都来源于一个基本类型(基类)，所有节点类型都采用同一套基本结构：一个节点描述符，后面在跟着0个或多个其他记录。所有节点类型的描述符都是完全相同的。记录本身的内容取决于包含它们的节点类型。内部节点包含索引记录，索引记录指向子节点，而叶子节点包含实际的数据，然而这两种节点的记录都是键值记录，采用了相同的一般性记录格式：首先是一个键，然后紧跟着数据。键必须以递增的顺序保存，而且必须唯一。

B树头节点

HFS+的B树起点并不是根节点，而是一个特殊的节点：头节点(header node)，这个节点的节点类型为kBTHeaderNode(1)。头节点一直存在，即使树本身为空。头节点刚好包含了3条记录，这些记录是不通过键索引的记录。头记录(header record)包含了整个树的元数据。由于头记录紧跟在描述符后面，因此其第一个字段(treeDepth，表示树种的层次树)是一个16位的值。HFS+的B树总是有一个固定的深度。也就是说，所有的叶子节点都在同一层上。深度由treeDepth字段定义的，通过ID可以快速查询节点。头记录之后是用户数据记录(User Data Record)：也是128字节长，目前这个记录是预留的记录，唯一用到这个记录的B树是热文件B树。头节点中最后一条记录是映射记录(Map Record)。映射记录占用了节点剩下的所有空间。

组件

HFS+使用了6个特殊的文件来维护自己的数据。其中有四个文件是B树：

• 编录(catalog)B树：包含文件系统中的所有文件
• 属性B树：HFS+中新增的，用于支持文件扩展属性
• extent 溢出(overflow)B树：用于超过8个碎片(或extent)的文件(一个extent表示一组连续的分配块)
• 热文件B树：用于频繁访问的小文件
• 分配文件：包含一个记录文件系统中所有数据块使用情况的位图
• 启动文件：一个简单的可执行文件，用于引导操作系统。OS X 基本忽略这个文件，但是其他操作系统可以使用。

当HFS+挂载时启用了日志功能，那么还会启用一个日志文件。所有这些组件(包括日志文件，但除去启动文件)都保存在元数据区域中。如果在宗卷上启用了磁盘配额，那么还会在元数据区域中保存用于支持磁盘配额的文件。

HFS+宗卷头

系统在开始对各种B树操作之前，必须能够找到这些B树在什么位置，并且还要识别HFS+文件系统本身的身份。为此，在一个固定的位置(从分区(即“宗卷”))开头器1024字节的位置有一个巨大的数据结构(512字节),这个数据结构(即宗卷头)包含了操作系统加载操作初始化所需要的所有必要的细节信息。
这个宗卷头目前也是HFS+和HFSX的主要区别所在：两个系统的宗卷头就一致，只有一下3点不同：

• HFSX使用签名HX，而HFS+使用的是H+
• HFSX将版本号设置为5，而HFS+的版本号设置为4
• HFSX的B树提供了一个选项用于选中比较键的方法：二进制比较或大写转换后比较

HFS+宗卷头编录非常重要，因此在宗卷头尾部的替补宗卷头(Alternate Volume Header)中也有备份，替补宗卷头在最尾部向前1024字节处，刚好占用了512字节，因此宗卷的最后512字节是没有使用且保存预留的。

编录文件

HFS+文件系统中最主要的B树就是编录文件了。编录文件包含文件系统中所有的文件和文件夹的条目。系统的所有文件操作都会使用这个B树：列出文件、搜索文件、读取文件、写入文件以及删除文件。
由于编录文件是一个B树，因此编录文件集成了HFS+ B树的结构和所有属性。编录文件还有一些新的属性：

• Catalog Node ID(编录节点ID，即CNID)：是文件或文件夹唯一的32位标识符
• 编录文件键定义一个结构体
• 编录文件中可能包含的4种不同的记录类别：
  • kHFSPlusFileRecord类型以HFSPlusCatalogFolder的形式保存文件夹数据
  • kHFSPlusFileRecord类型以HFSPlusCatalogFile的形式保存文件数据
  • kHFSPlusFolderThreadRecord以及kHFSPlusFileThreadRecored用于保存“thread(线索)”这两种请求下，线索是类型都为HFSPlusCatalogThread

编录查找

编录查找分为两种类型：

• 根据文件或文件夹名查找
• 根据CNID查找

硬连接和软连接

与其他任何UNIX文件系统一样，HFS+支持硬连接和软连接。然而其底层实现却很特别。
硬连接和软连接是通过userInfo字段中的fdType字段区分的。对于硬连接，这个字段的值是一个魔数0x686c6e6b(hlnk)，对于软连接，这个字段的值是另一个魔数0x736c6e6b(slnk)。在这两个情况下，fdCreator代码都是hfs+。
对于软连接，特殊处理到此为止：软连接也不过是普通文件，只是文件内容中包含了文件系统中另一个文件的名字。
对于硬连接，系统则需要特殊处理。创建硬连接时，底层文件的fork被重新安置了(甚至可以说是隐藏在文件系统中，某个私有隐秘的位置中。HFS+努力保持这个文件夹的隐藏和不可访问状态。通过UNIX工具无法看到这个文件夹(因为这个文件夹名字以NULL开头，NULL终止了C字符串))，Finder 也无法看到这个文件夹(Finder 要遵循kIsInvisible和kNameLocked标志位的约束)
硬连接的dentry和普通文件一样保存在对应的位置，但是这些文件的资源fork被设置为0。相反，bsdInfo中有一个“special”字段被设置为文件的inode编号，而这个编号可以从\0\0\0\0HFS+ Priviate Data 文件夹中获得。

fork分配

文件记录提供了两个HFSPlusForData结构体：一个用于资源fork; 另一个用于数据fork。根据前文的描述，HFS+可以支持任意数目的fork(通过后文要描述的属性树)，不过如果真的使用了fork，一般只有数据fork被使用了。

extent 溢出文件

大部分文件都刚好适合不超过8个extent。超过8个extent的文件被认为是严重碎片化，但是文件系统依然应该为这种文件提供服务。为此，文件系统维护了另外一个B树：extent溢出B树。extent 溢出B树比编录文件的B树要简单得多。和编录文件的不同之处在于，extent 溢出B树不含多个索引的记录：只包含叶子节点。

属性B树

属性B树是HFS+使用的另一个B树。HFS+通过属性B树保存各种扩展属性。大部分情况下，用户态应用程序都不需要关系这个B树，因为通过系统调用listattr(2)、getattr(2)和setattr(2)可以分别列出、获得和设置属性。hfsleuth工具可以直接读取属性B树所有的属性

热文件B树

热文件B树的记录是通过temperature 和 fileID(即目标热文件的CNID)索引的。由于temperature值是系统需要非常频繁查询的值，因此系统可以将搜索键的temperature设置为HFC_LOOKUPTAG。

分配文件

分配文件是一个非常大，而且无法访问的文件，负责跟踪卷中所有块的分配情况。由于分配文件本身也是一个文件，因此可能会碎片化。如果宗卷被扩大了，那么分配文件也会增长，因此实现了非常可扩展的方案。分配文件通常是连续的，而且包含在单独一个extern中，因为分配文件是在创建文件系统时通过mkfs呈现创建的。此外文件系统分配块大小的动态变化也是比较容易实现的。

HFS 日志

在HFS+ 中，日志是一项可以随意开关的特性，不过默认情况下是开启的。在加载一个文件系统时，HFS+检查宗卷头中lastMountedVersion 字段的值。