写在前面

一个设计良好的组件总是让人忘了它的存在。文件系统就是这样，由于其设计精良、运行高效，让我们在日常的复制、粘贴、格式化中都感觉不到它的存在。但作为技术人员我们有必要了解背后的基本原理，这是我的导师给我的第一个题目，也是我用C++写的第一个小工具：根据磁盘偏移量（LBA地址）定位文件、根据输入的文件路径确定物理偏移量。工具制作完成，正好整理总结一下制作过程，发出来跟大家分享。

原理分析

传统的硬盘是在盘片上存储文件的，硬件上采用C（柱面）H（磁头）S（扇区）的方式进行寻址，在硬盘容量一再扩增、CHS方式不足以寻址全部扇区时提出了LBA（逻辑区块地址）寻址的方式，LBA地址与PBA（物理区块地址）一一对应，通过基于首地址的偏移量可以直接读取某一物理位置上的扇区内容；虽然固态硬盘的存储原理与机械硬盘大不相同，也已经没有了盘片和磁头的概念，但仍然支持通过LBA地址访问扇区，通过FTL（闪存转换层）将LBA地址转换成物理上的PBA地址，并维护一份LBA和PBA的映射表。但两种硬盘都可以通过LBA地址访问硬盘中每一个有效扇区。

要想实现根据LBA地址定位文件，需要知道两个东西：

  • 硬盘是如何索引分区的
  • 文件系统是如何索引文件的

第一点，我们大多数电脑采用DOS分区体系，即使用MBR（主引导记录）来记录硬盘上的分区信息，并完成计算机通电自检后的第一步引导任务，部分新电脑已经支持EFI引导+GPT分区体系，苹果电脑在此之前采用的是Apple分区体系。本次任务主要针对DOS分区体系。MBR位于硬盘的第一扇区，使用WinHex可以直接打开并查看这个扇区的内容：

MBR的详细结构如下表：

可以看到，标准MBR的分区表可以描述四个分区，每项占据16字节，起始LBA地址总为0x1BE。每个分区项中的详细结构如下表：

如此一来，我们有了每个主分区的起始LBA地址，接下来就要弄清楚分区上是如何组织文件的。根据已经得到的信息，我们使用WinHex定位到第一个分区的起始扇区：

其中的关键信息如下图：

现在需要说明第二点，NTFS文件系统是如何索引分区上的文件的。

文件系统使用簇（Cluster）来分配文件，而刚才我们是通过扇区（Sector）来完成MBR、PBR的定位的。簇的大小在格式化分区时可以手动指定，一般默认为8个扇区为1簇，由于每个扇区容量为512字节，则每簇实际大小为4KB。

而NTFS又使用VCN（虚拟簇号）和LCN（逻辑簇号）来进行簇的定位，LCN是对整个卷中所有的簇从头到尾所进行的简单编号。卷因子乘以LCN，NTFS就能够得到卷上的物理字节偏移量，从而得到物理磁盘地址。VCN则是对属于特定文件的簇从头到尾进行编号，以便于引用文件中的数据。VCN可以映射成LCN，而不必要求在物理上连续。

NTFS的目录只是一个简单的文件名和文件引用号的索引，如果目录的属性列表小于一个记录的长度，那么该目录的所有信息都存储在主文件表的记录中，对于大于记录的目录则使用B+树进行管理。

主文件表中的基本文件记录中有一个指针指向一个存储非常驻索引缓冲--包括该目录下所有下一级子目录和文件的外部簇，而B+树结构便于大型目录中文件和子目录的快速查找。在NTFS中，所有存储在卷上的数据都包含在文件中，包括用来定位和获取文件的数据结构，引导程序和记录这个卷的记录（NTFS元数据）的位图（$BITMAP），这体现了NTFS的原则：磁盘上的任何事物都为文件。在文件中存储一切使得文件系统很容易定位和维护数据，而在NTFS中，卷中所有存放的数据均在一个叫做MFT的文件记录数组中，称为主文件表(Master File Table)，MFT是由高级格式化产生的。而MFT则由文件记录(File Record)数组构成。File Record的大小一般是固定的，不管簇的大小是多少，均为1KB，这个概念相当于Linux中的inode（i节点）。File Record在MFT文件记录数组中物理上是连续的，且从0开始编号。MFT仅供系统本身组织、架构文件系统使用，这在NTFS中称为元数据（metadata）。其中最基本的前16个记录是操作系统使用的非常重要的元数据文件。这些NTFS主文件表的重要的元数据文件都是以$开始的名字，所以是隐藏文件。实际上File System Driver(ntfs.sys)维护了一个系统变量NTFS Protect System Files用于隐藏这些元数据，但这并不妨碍我们基于LBA地址直接读取这些扇区上的字节内容。

包括我们刚才看到的NTFS引导区、还有MFT表，都是以文件的形式存储在分区上的。而知道了第一个MFT项的地址，也就能索引所有的MFT项了。通过上图我们知道，这块分区的MFT表起始簇号为786,432。我们把786,432转换成LBA地址，然后打开这块扇区，可以看到如下内容：

那么MFT项中的信息是如何组织的呢？继续使用WinHex提供的模板来查看：

一个MFT项包含MFT头、属性列表，属性列表中包含标准信息属性、文件名属性、数据属性、索引根属性等，上面我们提到过，小于1KB的文件，其内容会直接作为常驻属性存储在MFT项内以节省空间。属性列表由属性组成，每个属性又包含属性头和属性内容。常用的属性如下表：

其中数据属性决定了这个MFT项所代表的文件在硬盘上的存储位置，同样的，根据各字节偏移处所代表的信息，可以将其解构出来：

非常驻的数据属性描述了簇流列表（包含簇流长度和簇流起始位置）和起始与结束的VCN地址。根据这些信息，我们就能计算出每个MFT代表的文件在硬盘上对应的LBA地址和长度了。

由于我们直接面对的是Raw Bytes，所以实际编程还需要查阅哪个字节处的数据代表什么意思。

编程实现

实现这个程序主要需要以下几个Windows API：

1
2
3
4
5
6
7
8
9
10
HANDLE WINAPI **CreateFile**(

LPCTSTR lpFileName, // 文件名
DWORD dwDesiredAccess, // 访问模式
DWORD dwShareMode, // 共享模式
LPSECURITY\_ATTRIBUTES lpSecurityAttributes, // 安全属性(也即销毁方式)
DWORD dwCreationDisposition, // 创建方式
DWORD dwFlagsAndAttributes, // 文件属性
HANDLE hTemplateFile // 模板文件句柄
);

这个API会返回要打开的对象句柄，lpFileName可以填写要打开的文件的完整路径，这样就能得到文件的句柄，也快成填写\\.\PHYSICALDRIVE0，这样就能得到已挂载的第一块硬盘的句柄，或者\\.\C，可以打开C盘的句柄。

需要注意的是，第三个参数需要填成FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE，来保证在你打开该文件/分区/硬盘并读取的时候，别人仍然可以访问它，不然在打开硬盘句柄时系统会拒绝访问。

1
2
3
4
5
6
DWORD WINAPI **SetFilePointer**(
HANDLE hFile, //要打开的句柄
LONG lDistanceToMove, //指针偏移的字节数的低32位
PLONG lpDistanceToMoveHigh,  //指针偏移的字节数的高32位，如果文件小于4GB此项为NULL
DWORD dwMoveMethod //设置成基于起始位置还是结束位置
);

这个API可以设置读文件的指针的起点，也引出了下一个需要介绍的API：

1
2
3
4
5
6
7
BOOL WINAPI **ReadFile**(
HANDLE hFile, //要读取的文件句柄
LPVOID lpBuffer, //接收数据的buffer指针
DWORD nNumberOfBytesToRead, //要读取多少字节的数据
LPDWORD lpNumberOfBytesRead, //实际读了多少字节的数据
LPOVERLAPPED lpOverlapped //异步读取的开关
);

使用这个API来读取一定字节数量的数据，而上一个可以设置读取的起点位置。

既然我们要根据基于硬盘起点的LBA地址定位文件，那么我们就需要物理硬盘的句柄，首先定位MBR，然后读取分区表，得到每个分区的起始LBA地址，并读取分区头部的PBR，得到$MFT项的起始地址，由于MFT线性排布，这样就知道了每个MFT项的LBA地址。然后根据MFT项中每种属性的字节偏移，就能解析MFT项了。这就是定位过程的实现思路。

1
2
3
4
5
6
7
8
9
10
BOOL WINAPI **DeviceIoControl**(
\_In\_ HANDLE hDevice,
\_In\_ DWORD dwIoControlCode,
\_In\_opt\_ LPVOID lpInBuffer,
\_In\_ DWORD nInBufferSize,
\_Out\_opt\_ LPVOID lpOutBuffer,
\_In\_ DWORD nOutBufferSize,
\_Out\_opt\_ LPDWORD lpBytesReturned,
\_Inout\_opt\_ LPOVERLAPPED lpOverlapped
);

这个API可以对输入输出设备发送预设的控制码，使用FSCTL_GET_RETRIEVAL_POINTERS控制码，可以根据文件句柄，获得文件每个碎片的VCN、LCN地址和占用簇的数量。使用这个API可以根据文件名定位其LBA地址。

使用这些API可以完成基本的 LBA<--双向-->文件名 查询流程，但还需要考虑以下问题：

  1. 如何知道一共有多少个有效的MFT项？对于这个信息可以读取$MFT元文件的$BITMAP属性，来获得MFT项的分配情况；
  2. 如何处理大目录？对于碎片很多的文件，或是子文件很多的大目录，会占据多个MFT项来存储所有的常驻属性，这时候需要手动解析索引根属性（0x90）和属性列表属性（0x20）；
  3. 在MBR之后、PBR之前，是一块预留空间，PBR之后、MFT起始之前存有分区引导代码，剩余空间填零，要预先判断输入的LBA地址是否落在这些保留空间里；
  4. 如何处理权限问题？不难推断，直接对MFT项进行解析、对指定扇区进行读取，会破坏Windows原本的ACL访问保护机制，所以程序需要以管理员权限运行，对于较老版本的Visual Studio，需要添加一个资源文件，说明程序所需的权限，从而被链接到可执行文件中；
  5. 如何处置访问过的MFT项？如果对读取的MFT项仅仅索引几个关键属性，然后就将其放过、进入下次循环，那么宝贵的信息就都流失了。可以建立自己的数据结构，将NTFS分区上的文件索引起来，对NTFS日志做增量索引，做成文件搜索工具，搜索速度比Windows自带的搜索工具快很多；
  6. 如何解析以UTF-16保存成Raw bytes的文件名？Windows提供了名为MultiByteToWideChar的函数可以转换widechar，如果你觉得这个函数用起来太麻烦不妨手写代码将Raw bytes按照little-endian的方式转换成widechar；
  7. 对应的，由于并没有将Raw bytes转换成整型数的API，你需要手写一个以little-endian的方式将Raw bytes解析成整型数的函数；
  8. …………继续考虑下去，假以一定时间，以强迫症作为驱动力，大概就能写出像Everything那样强大的搜索工具了：）

完成感悟

我去我了个大去，写到现在突然发现这一点都不像我的文风啊喂，怎么好像一篇又臭又长的实验报告啊喂，一点都不愉快的文字写地都快吐血了。其实做完这个小工具，最大的感悟就是：NTFS是个如此靠谱的文件系统！！！在大分区上还在用FAT32的都什么心态。。。

那么为什么说NTFS是一个靠谱的文件系统呢？FAT文件系统的文件分配表只能列出了每个文件的名称及起始簇，并没有说明这个文件是否存在，而需要通过其所在文件夹的记录来判断，而文件夹入口又包含在文件分配表的索引中。因此在访问文件时，首先要读取文件分配表来确定文件已经存在，然后再次读取文件分配表找到文件的首簇，接着通过链式的检索找到文件所有的存放簇，最终确定后才可以访问。

而NTFS继续将文件组织成目录，目录也像在 HPFS 中一样被排序。NTFS 在磁盘上没有“特殊”对象，而且对诸如 512 字节扇区之类的基础硬件也没有依赖性。NTFS 是一个可恢复的文件系统，因为它能跟踪针对文件系统的事务。在 FAT 或 HPFS 上执行 CHKDSK 时，系统会检查目录、分配和文件表中指针的一致性。在 NTFS 下，系统会维护针对这些组件的事务日志，因此，CHKDSK 只需将事务回滚到上一个提交点就可以恢复文件系统中的一致性。 每次读写时，它都会检查扇区正确与否。当读取时发现错误，NTFS会报告这个错误;当向磁盘写文件时发现错误，NTFS将会十分智能地换一个完好位置存储数据，操作不会受到任何影响。在这两种情况下，NTFS都会在坏扇区上作标记，以防今后被使用。这种工作模式可以使磁盘错误可以较早地被发现，避免灾难性的事故发生。

——以上两段引用自MSDN。

如果我们使用的网盘，在同步本地文件的时候，通过读取NTFS日志来检测文件更改（比如坚果云），就能做到实时响应更改，不再需要以每1min或者每5min的周期间隔来扫描整个目录确定更改情况了（比如百度云）。这些都是NTFS带来的方便啊啊喂。

另外作为从C#转过来的C++开发者，以前我认为C#的语法是C系最佳，在用C++做了两周的开发工作后——越来越觉得C#的语法很优美了……各种LINQ快速查询、装箱拆箱、await简单异步执行……C#在桌面开发中可怜的份额实在对不起这么好的语言啊……嗯，吐槽结束，作为一名合格的开发人员，手动管理内存、使用底层函数都是必备的技能，熟练使用C++还有很长的路要走。

文章第一张图片是我制作的小工具的使用方法，需要使用管理员权限运行，

1
2
3
4
5
LocateFile \-f 文件路径  //给出该文件的LBA地址

LocateFile \-l LBA地址  //给出该LBA对应的文件

LocateFile \-d         //DEMO，列出前250个标记为FILE的MFT项

最后，感谢我的导师，以前常用各种工具给人修电脑，这还是第一次亲手制作一个小工具：）