Everything原理探究以及Ｃ＃实现

前言

    这篇博文发布后，有人问我为什么和别人写的很相似。我说：原理能不相似吗。

    但其实，Everything的原理并不是我钻研出来的，我只是看懂了别人的解析，别人的代码。所以称不上是原创文章，我深深的认识到了自己的错误。

起因

阅读本文时可以参照官方文档 https://docs.microsoft.com/en-us/windows/win32/api/

    我写这个程序是用来当作《操作系统原理》这门课的课程设计的, 从今年三月份开始做, 前前后后花了一个多月的时间。原本收集了许多资料，可惜保存在了本地文件夹，一换固态就找不到了，不然可以分享给大家。

    本打算做一个电脑上的文件管理工具，类似于安卓的文件管理一样，后来发现，想要管理磁盘上的文件, 首先得全部找出磁盘上的文件。 于是计划着计划着就做成了变异的Everything。程序介绍以及源码我会在下一篇博文中发布。这篇主要介绍 Everything 查询的原理，以及所用到的Windows编程接口，以及程序展示。

NTFS文件系统

    NTFS文件系统伴随NT操作系统而诞生。文件系统都有文件分配表，它记录了磁盘上文件的位置，名称等等一系列信息。 在NFTS文件系统当中，它被称为MFT——主文件表。该文件系统也应用于U盘等设备。
    主文件表体积十分庞大。你如果下载一个WinHex可以查看它的具体内容， 当然是16进制形式。其中一条记录是1024个字节，如果一个文件比较复杂，那么它可能占好几条记录。里面包含着大量的文件属性，十分详尽，我们可以通过它来做数据恢复，但你必须熟悉它的格式规范，才有可能看得懂里面的内容。Windows也提供了一些编程接口来对它进行操作。当然，主文件表与Everything并没有什么关系。 说这些呢，只是为了告诉大家我走了很长一段弯路。

Everythin原理

    Everything获取磁盘上的文件靠的是读取NTFS文件系统的USN日志。因此，使用NTFS的磁盘都可以通过读取USN日志的方式来实现文件的快速查找。

    USN日志称为更改日志。每个NTFS磁盘分区都有一个USN日志用于记录该磁盘上的文件更改情况，更改日志中的每条记录都包含USN（即记录编号）、文件的名称，文件引用号，父文件引用号等信息。但并不记录具体的更改操作，因此体积相对于主文件表来说要小很多。

    我们可以通过调用 system３２文件夹下动态链接库中的API编程接口，来读取USN日志的内容，并对其内容进行解析，从中得到文件名和文件路径，进而实现快速查找磁盘上任意文件的功能。

USN日志的结构

    public struct USN_RECORD
    {
        public int RecordLength;
        public short MajorVersion;
        public short MinorVersion;
        public long FileReferenceNumber;
        public long ParentFileReferenceNumber;
        public long Usn;
        public long TimeStamp;
        public int Reason;
        public int SourceInfo;
        public int SecurityId;
        public FileAttributes FileAttributes;
        public short FileNameLength;
        public short FileNameOffset;
    }

我来简单解释一下USN日志记录结构体。

RecordLength：  记录长度，单位字节。
MajorVersion; MinorVersion   主次版本号。版本不同,USN日志的格式也会有差异。但我并没有区分它们，目前版本大多是一致的。
FileReferenceNumber   文件引用号 ，可以看作文件的ID
ParentFileReferenceNumber   父文件引用号，父目录的ID
Usn   更新日志号，递增，不规律
FileNameLength   文件名长度
FileNameOffset   相对于该记录起始位置，文件名起始位置的偏移量

  我们需要通过文件名长度和文件名偏移量，来读出文件名，根据父文件引用号，找到父文件名，并拼接出文件的完整路径。这些操作都在内存中，且会用到指针，所以速度是很快的。

如何读取到USN日志

    我们可以通过一个叫做DeviceIoControl的系统函数来读取USN日志，从它的名字可以猜出，这是一个非常强大的函数.

BOOL DeviceIoControl(
    HANDLE       hDevice,
    DWORD        dwIoControlCode,
    LPVOID       lpInBuffer,
    DWORD        nInBufferSize,
    LPVOID       lpOutBuffer,
    DWORD        nOutBufferSize,
    LPDWORD      lpBytesReturned,
    LPOVERLAPPED lpOverlapped
);

第一个参数是一个句柄指针，它指向你要操作的Device对象。
第二个参数是控制码，它是一个常量，决定了这个函数的作用，当我们读取USN日志是，该值为：0x900b3;
lpInBuffer 代表输入条件，它是一个指向特定结构体的指针。这个结构体的格式根据你的用法而定，也就是第二个参数dwIoControlCode。
nInBufferSize     lpInBuffer的大小
lpOutBuffer     是一个指向输出缓存区的指针，用于接收返回的数据
nOutBufferSize     输出缓冲区的大小
lpBytesReturned     返回的数据字节数

具体的用法我会在下一篇博文讲述，这里只讲述实现思路，你也可以通过查阅MSDN来了解更多信息。

    我们从USN日志中读取到的内容保存在了lpOutBuffer所指向的字节数组中，该数组的前八个字节代表着下一条USN日志号（因为接收缓存区大小限制，USN日志并不一定能一次读取完成。下一条USN日志号是将要读取到的那条记录号）。输出缓冲区里可能会包含多条记录，它们并没有明确的长度，边界。因此必须按照上面提到的结构规则对其进行解析。
    需要注意，我们需要通过lpBytesReturned ：返回的数据字节数，来判断USN日志是否读取完成。而且在解析接收缓冲区的时候，同样需要用到。

    下面这段代码讲的就是上面这个过程啦！事实上仅仅需要读取出文件名并获取文件路径的话，使用Ｃ＃只需要一百来行代码。

在Ｃ＃编程中，我们并不需要考虑指针和内存分配，但是C#仍然给我们提供了丰富的操作非托管资源的方法。我们可以使用unsafe代码，也可以使用更高级的Inptr和Marshal类。

do
    {           
        if (WinApi.DeviceIoControl(
            rootHandle,
            WinApi.FSCTL_ENUM_USN_DATA，
            mftPtr, 
            Marshal.SizeOf(mftData),
            receiveBuffer, 
            receiveBufferSize,
            out retBytes, 
            IntPtr.Zero))
        {
        　　cb = retBytes;
            IntPtr recPtr = new IntPtr(receiveBuffer.ToInt64() + 8);
            while (retBytes > 64)
            {                   
                record = (WinApi.USN_RECORD)Marshal.PtrToStructure(recPtr,typeof(WinApi.USN_RECORD));
                FileName =Marshal.PtrToStringUni(new IntPtr(recPtr.ToInt64() + record.FileNameOffset), record.FileNameLength / 2);
                bool IsFile = !record.FileAttributes.HasFlag(FileAttributes.Directory);
                FSNodes.Add(record.FileReferenceNumber, new FSNode(record.FileReferenceNumber, record.ParentFileReferenceNumber, FileName, IsFile));
                recPtr = new IntPtr(recPtr.ToInt64() + record.RecordLength);
                retBytes-=record.RecordLength;
            }
            Marshal.WriteInt64(mftPtr, Marshal.ReadInt64(receiveBuffer, 0));
        }
        else
        {
            break;
        }                

    } while (cb > 8);　　   

导入WindowsＡＰＩ到项目中,　CreateFile函数用于获取磁盘句柄。

    其实不能说是导入,因为动态链接库是程序运行时才加载的,这里只是一个声明.程序会从system32,bin文件夹下等查找该dll . 能够在c#中使用其他语言编写的链接库, 得益于.NET遵循的ＣＴＳ通用类型系统，它制定了中间语言所能转化的基本数据类型。

[DllImport("kernel32.dll", SetLastError = true)]
public static extern IntPtr CreateFile(
    string lpFileName, 
    uint dwDesiredAccess, 
    int dwShareMode, 
    IntPtr lpSecurityAttributes, 
    int dwCreationDisposition, 
    int dwFlagsAndAttributes, 
    IntPtr hTemplateFile);

[DllImport("kernel32.dll", SetLastError = true)]
public static extern bool DeviceIoControl(
    IntPtr hDevice, 
    uint dwIoControlCode, 
    IntPtr lpInBuffer, 
    int nInBufferSize, 
    IntPtr lpOutBuffer, 
    int nOutBufferSize, 
    out int lpBytesReturned, 
    IntPtr lpOverlapped);

最后，将你解析到的日志条目保存到Dictionary或是List或是任意你希望的地方。通过父文件引用号，找到父文件名，把父文件名和自己的名字串起来，一直串下去，就可以得到文件路径啦！

效果图

（毕竟是课程设计，做起来是一个蛮复杂的过程，源码和具体实现下次再讲）

    检索系统是集文件搜索、复合条件组合查询、文件管理、文件分析等功能于一体的实时文件定位与检索应用软件。系统支持极速搜索、正则表达式、多模块组合查询、右键菜单、文件数据可视化、磁盘结构可视化、各磁盘文件类型实时分析、系统文件总数分析等功能。系统采用Task任务并行、UI异步线程、虚模式、Highchart可视化控件实现界面无卡顿以及数据动态实时显示；基于Windows Shell编程实现文件复制、粘贴、发送、属性等功能。

（要不是字数限制，我们可以写更多。）