FCES - 一种全新的分区文件系统结构 二

Hzj_jie

3、UUIT的保存和获取
定义索引编号为0x00000000，父目录为0x80000000的文件为未使用索引编号列表保存文件。和其他文件一样，保存在文件系统中。
1、整理与保存
每次结束分区操作时，需要将已有的UUIT进行整理与保存。具体的整理工作是将全数据表依照由小到大的顺序重新排列，并将可以合并的UUIT区域合并，如在由小到大的排序后存在Index=n的UUIT区域中End=m，而Index=n+1的UUIT区域中Start=m+1。将可以遗弃的区域遗弃，如Index=n的UUIT区域中Start=0x00000000。
保存时的工作与保存一般文件相同，将文件和目录的UUIT完全写入索引编号为0x00000000，父目录为0x80000000的文件中，以便下一次启动分区时获取。
2、获取与初始化
每次启动分区时，需要将已存在的UUIT由文件系统读取入内存区域，以方便文件系统的操作。读取时的工作与读取一般文件相同，由索引编号为0x00000000的文件获得。如果0x00000000的索引记录区域的检查使用标记为0x00，则说明UUIT需要被初始化，此时初始化文件UUIT的第一个记录区域的Start=0x00000001，End=0x7FFFFFFF，目录UUIT的第一个记录区样的Start=0x80000001,End=0xFFFFFFFF。此工作也可以由格式化程序进行处理，并保存。
9、文件系统操作
1、目录和文件建立处理
1、获取未使用的索引编号，并检查索引编号区域的使用标记。
2、查找未被使用的自由簇[仅对于文件]
由数据区的起始扇区开始，检查第一扇区的自由簇使用标记，如为0xFF，则读取自由簇长度，并跳转至下一自由簇。如为0x00，则将新建立文件的起始扇区编号标记为此扇区。并将此自由簇的使用标记标记为0xFF，长度标记为1扇区，文件结尾标记标记为0xFF。
2、文件的追加处理
本段包含对文件结尾进行追加的处理方式。
1、获取现有文件的结尾，即包含文件结尾的自由簇。
2、获取可用的下一自由簇
由当前文件结尾自由簇最后一个扇区的后一扇区开始检索，如果自由簇使用标记为0xFF，则读取自由簇长度，并跳转至下一自由簇。直至发现使用标记为0x00的自由簇，将原文件结尾的自由簇的随后簇扇区编号标记为此自由簇的起始扇区编号，并将文件结尾标记标值为0x00。同时将此自由簇的使用标记标记为0xFF。如果需要，比如尚不存在已经建立的自由簇，则同时写入自由簇的长度等其它自由簇信息。
如果选择的自由簇可记录数据长度小于需要追加的数据，则在完成当前自由簇数据区域写入后，再检索下一可用的自由簇。并同样标记当前自由簇的结尾标记和随后簇扇区编号，以及标记下一自由簇的使用标记和写入数据。
如果出现下一可用的自由簇紧接于当前的自由簇的情况，则将两个自由簇合并。需要进行的操作包括，将前一自由簇的长度标记为两个自由簇长度之和，并删除后一自由簇的自由簇信息[即自由簇第一个扇区中的信息]。
如果选择的自由簇可记录数据长度大于需要追加的数据，则修改此自由簇长度记录[包括自由簇长度记录和最后扇区长度记录]至合适于需要追加数据的长度，并在下一扇区建立新的自由簇，将检查使用标记修改为0x00，自由簇长度为原自由簇长度减去之前一个自由簇长度，以便以后用于其它文件的记录。
3、文件的非追加修改处理
本段包含对文件已有数据进行修改的处理方式，要求所修改的数据的位置均在已存在的文件长度内。
1、获取现有文件的起始扇区，并开始记录已被检索文件的长度。
2、通过若干次跳转，将需要修改的数据位置定位于一个自由簇中。
3、准确定位所需修改的数据在自由簇中的位置，并进行修改。
文件的追加和非追加修改处理可能在文件操作中被同时使用。因此可以将追加的功能添加入非追加修改处理中，即在文件达到结尾时，自动追加下一可用自由簇为隶属此文件的自由簇。
4、目录和文件删除处理
1、临时删除[可恢复删除]
此类删除的文件或目录并不被从存储空间中物理擦除，而只是在文件系统中无法被检索到。
具体操作为修改目录或文件的索引记录中的使用标记由0xFF至0x00。如果是目录，还需同时修改隶属于此目录的文件和目录的索引记录中的使用标记。
2、非可恢复删除
此类删除的文件或目录将有可能在一定时间内被恢复，但对分区的重新写入将破坏被删除文件的数据，所以此类删除将被认为是不可安全恢复的。
具体操作包括修改目录或文件的索引记录中的使用标记由0xFF至0x00，和修改UITT中的相应索引记录为未使用。如果是文件，还需修改所有隶属自由簇的使用标记为0x00。如果是目录，还需要同时非可恢复的删除隶属的所有文件和目录。
5、目录和文件恢复处理
1、对临时删除的恢复处理
具体操作包括检索所有索引记录，若满足下列三点要求，则修改使用记录为0xFF。
1、使用标记为0x00
2、索引记录位置与索引编号对应
3、在UITT中未标记此索引编号为可用
同时可以对其父目录或字符名称进行控制，以达到恢复相应目录中被临时删除的文件和目录，或恢复指定文件或目录的功能。
2、对非可恢复删除的试图恢复处理
根据非可恢复删除的处理过程，此类删除的恢复被认为是不一定总能恢复有效的数据。
具体操作包括检索所有索引记录，如果同时满足下列两点要求，则修改使用记录为0xFF。
1、使用标记为0x00
2、索引记录位置与索引编号对应
然后根据起始扇区编号检索所有隶属自由簇[包括可能的自由簇]，如果同时满足下列三点要求，则修改使用标记为0xFF。
1、使用标记为0x00
2、对应扇区满足自由簇结构定义，如检查使用标记和文件结尾标记为0x00和0xFF中的一个，随后簇起始扇区编号以后的部分全部为0x00等。如果任何一点不满足，则说明此文件的这个部分及以后内容已被修改，无法继续恢复剩余内容。
3、随后簇起始扇区指向的区域仍然为一个可能的自由簇
虽然可能同时满足以上三点要求的扇区可能并不会很多，但是仍然可能有某个以后写入的文件内容恰好符合以上要求，而被错误修改为自由簇的信息。所以此类恢复将有可能破坏其它的文件，而被认为是不安全的。
6、目录和文件的移动处理
对于FCES分区，移动处理只需要修改父目录的索引编号就可以实现。具体操作为，获取需要移入的目录的索引编号，修改需要移动的目录或文件的父目录索引编号为移入目录的索引编号。
7、目录和文件的复制处理
FCES分区中不允许多个文件指向同一数据区域，所以复制目录或文件需要重新建立新的目录或文件，在新建立的目录或文件的索引记录中复制原目录或文件的索引记录信息，修改父目录索引编号为复制入目录的索引编号。
对于文件，还需要完全写入原文件中的所有数据，并修改起始扇区编号为新写入数据的起始扇区编号。对于目录，还需要同时检索隶属的所有文件或目录并加以复制，同时修改父目录索引编号为新建的目录的索引编号。
10、分区检查和处理
1、分区剩余空间检测
根据以上章节中对FCES分区的定义和实现方式，FCES分区中基本不存在需要预留的区域。可用空间被定义为由数据记录区起，至已经使用的最后一个索引编号所在索引记录区域为止，之间的所有未被使用的自由簇或尚未包含自由簇信息的区域。
检查分区剩余空间时的操作包括，
1、确认已经使用的最后一个索引编号，及其所占用的索引记录区域的物理位置。
2、由数据记录区起始位置起，检查每一个已存在的自由簇，如果使用标记为0x00，则获取此自由簇的长度信息，将其大小累加进寄存器中，并且跳转至下一自由簇。
3、当发现某一位置不再存在自由簇完整信息时，则停止检查，将此位置至最后一个索引记录区域之间的磁盘空间累加进寄存器。
2、检查与逻辑数据损坏处理
因为对于已经加密的文件或目录，在没有密码的情况下无法获取其几乎任何的信息，所以一般要求需要确认密码的前提下进行分区的检查工作。或者当在没有密码的情况下强制检查，则跳过所有已经加密的文件和目录。
检查主要包括三个阶段，
1、索引记录区完整校验 [基础检查]
检查所有索引记录是否有效。
1、检查使用标记是否正确。即是否为0x00和0xFF中的一个。同时检查使用标记是否与未使用索引编号表对应。
2、检查用户编号是否存在。即用户编号记录是否指向一个已经存在的用户。
3、检查索引记录区中各索引编号与其所在位置是否一一对应。
4、检查父目录索引编号是否指向一个有效的目录。即是否文件和目录区分位为1。若为1，则再检查对应的目录是否已经存在。
5、检查类型编号是否标记的为已存在的文件类型。即不存在的类型位是否全部为0。
6、检查创建/修改时间是否有效。即年月日的对应值是否为有效值。
7、检查起始扇区编号是否指向一个有效的自由簇起始位置。包括是否在当前分区内，以及指向扇区是否包含一个有效的自由簇信息。
8、对于加密并且已经提供密码的文件或目录，则首先必须检查密码是否正确。
2、数据区记录检查 [扩展检查]
检查所有的自由簇信息是否有效。
1、检查使用标记是否正确。即是否为0x00和0xFF中的一个。
2、检查自由簇长度记录。即当前自由簇之后是否为一个有效的自由簇，或尚未标注为自由簇的空白区域。
3、检查自由簇隶属文件编号信息是否与之前自由簇及索引记录区的记录是否相符合。
4、检查最后扇区长度记录和随后簇起始扇区编号记录与文件结尾标记是否对应。即当文件结尾标记为0xFF时，最后扇区长度是否大于0x0000。以及当文件结尾标记为0x00时，随后簇起始扇区编号记录是否指向一个有效的自由簇。
3、分区基础属性区检查 [高级检查]
这种检查独立于其它检查，因为分区基础属性区的错误将可能导致分区读取错误，从而无法进行任何读取和检查。
检查分区基础属性区信息是否有效。
1、BPB长度
统计各种属性[基础以及扩展]所占用的总长度与BPB长度记录信息是否一致。
2、检查相关的扩展属性设置是否有效，此功能将依赖于支持的操作系统。
3、分区数据整理和优化
对于FCES分区，分区的数据整理和优化主要是将包含多个自由簇的文件尽量合并到一个自由簇。所以整理和优化数据可能要花费较长的时间。
1、分区整理策略
1、对于FCES分区，最优的状况是每一个文件都只包含一个自由簇，但通常这是不可能，也不算最为合理的优化。特别是对于文件较大，且占用率较高的分区。将所有文件如此优化在某些情况下几乎是不可能的，而且所花费的时间和操作中占用的额外寻址时间相比明显不够划算。
2、介于前一条中的说明，数据整理和优化应该在分析了整个分区自由簇和文件数目的比值，以及自由簇的平均大小的前提下进行合理的整理。
2、分区整理步骤
1、分析整个分区，并统计零碎文件信息。包括文件总数[亦可由UUIT中获取。]、文件的平均大小、自由簇总数、自由簇平均大小等。
2、根据统计结果以及用户问讯选择合适的优化策略，包括允许的最大文件自由簇数目；单文件包含多自由簇情况下，每个自由簇的最小空间等。
3、生成需要进行整理的文件的列表。
4、对于需要进行整理的文件，在有限次的隶属自由簇的移动以后，将文件的某些自由簇进行合并，以满足对自由簇数目和大小的要求。具体合并方法同[9、文件系统操作 -> 2、文件的追加处理 -> 2、获取可用的下一自由簇]中的说明。此过程中，可以利用未被使用的数据记录区域进行文件的移动中介。
4、格式化与物理结构损坏处理
1、格式化处理
1、概述
基础格式化分区操作主要是将索引记录区[IRB]中的检查使用标记和数据记录区[DRB]中自由簇记录信息的检查使用标记清为0x00，同时将未使用索引编号表[UUIT]重置。这样所有的文件信息将全部丢失，同时分区将初始化为空状态，以便于再次写入新信息。与文件不可恢复删除一样，基础格式化分区操作被认为是不可安全恢复的。
扩展格式化分区操作包括索引记录区和数据记录区的清空，同时选择性修改除扩展标识以外的扩展属性表。在清空过程中检查分区的盘面物理错误，同时在相应位置加以标记[详见物理结构损坏处理中的说明]。这样的格式化操作是不可恢复的。
2、格式化处理步骤
1、基础格式化操作
1、清除索引记录区[IRB]中的检查使用标记
由索引记录区起始位置起，依单一索引记录长度[由基础属性表中的索引长度获得]跳转，同时修改第一位置的检查使用标记为0x00。
2、清除数据记录区[DRB]中自由簇记录信息的检查使用标记
由数据记录区起始位置起，依单一自由簇长度[由自由簇记录信息中的自由簇长度获得]跳转，同时修改第一位置的检查使用标记为0x00。
3、重置未使用索引编号表[UUIT]
见未使用索引编号标的获取与初始化部分。
2、扩展格式化操作
在基础格式化操作的基础上，附加清空索引记录区和数据记录区及分区物理检查。
2、分区物理检查
1、概述
分区物理检查是检查分区所在的硬盘区域的物理错误。此操作可以独立于扩展格式化之外进行。
2、检查方式
对分区包含的所有扇区进行写操作，包括全[0]写入和全[1]写入，再读取判断正误。如果不是在扩展格式化后进行检查，则还需要记录原扇区内容，并在检查后重新写入。
3、错误处理方式
1、索引记录区物理错误
将所在位置的索引编号使用记录标记为已使用，同时将此索引记录的使用标记标为0xFF。如果不是在扩展格式化后进行检查，则还需要将原有的索引信息[依照发现损坏前数据]重新存入另一空索引记录区，修改其索引记录编号，并将其在未使用索引编号表中标记为使用。如果发现数据存在严重损害，如起始扇区编号的信息存在错误[包括超界及与自由簇隶属文件信息不符。]，则可能需要搜索整个数据记录区以查找到隶属的自由簇并修改对应的起始扇区编号。
一般认为文件的隶属自由簇在分区中的排列是顺序的，除非此某些自由簇中存在物理错误而被修复过。在此类修复时，同时检查所有的隶属自由簇的之前自由簇和随后自由簇的起始扇区编号，以查找到起始扇区。
2、数据记录区物理错误
在所在位置建立一个自由簇，长度视连续的物理错误扇区而定。将存在物理错误的扇区包括在此自由簇中。如果不是在扩展格式化后进行检查，则还需要将所属扇区[依照发现损坏前数据]及之前和之后各一个扇区的信息重新组成自由簇，寻找未被使用的数据记录区保存，再在前后位置重新组成自由簇，并与新的自由簇链接。
11、可被附加的功能
由于FCES分区未破坏或改变文件的块存储方式，所以如数据的压缩和加密功能仍然可以在文件系统上被附加。具体视支持的文件系统控制软件。
加密功能应以流加密方式为基础，即要求任何一位的处理均与之前或之后位的信息无关，而只与其在文件中的位置相关。以下提供加密的一种解决方案，即流插入检查加密方式[FIC]的说明。

Flow Insert & Check（流插入检查）
特点概述
将传统的单纯计算机程序检查数据流准确性的方式改为了计算机和用户同时检查。在保证程序能较高比率的检查出密码错误造成的数据流错误的前提下，通过单纯程序检查结果的不唯一性提高安全性能。

实现方法
流插入检查（FIC）是通过在数据流中插入固定位置的检查码并将密码嵌入实现的。整个加密处理过程将分为插入校验码（Flow Insert Part）和密码嵌入（Code Inset Part）两个部分。解密处理过程将包括同时处理的密码提取（Code Extract Part）和校验码检验及去除（Flow Check Part）两个部分。

加密处理过程
加密处理过程需要4个参数：
Flow        字符串，表示需加密的数据流
Code        字符串，表示加密时使用的密码
Bits                整型，用于确定插入校验码的间隔
Mode        整型，用于确定校验码ASCII码二进制数位的来源
1．插入校验码（Flow Insert Part）
每8*Bits位插入一个校验码，校验码将依靠前8*Bits位的数据产生。其ASCII码的二进制数为其中的固定8位的ASCII码二进制数的Mode位的顺序排列，固定位的选取由Bits的设定控制。选取方式为第1位，第Bits+1位，第2*Bits+1位，直至第7*Bits+1位。
2．密码嵌入（Code Inset Part）
在生成新的数据流之后，依次把密码的各个位加入流中，方法是进行位异或运算。
设数据流为a0,a1,a2,a3,a4,a5,a6,a7,a8
密码为b0,b1,b2
则经过密码嵌入处理的新的流为
a0 xor b0,a1 xor b1,a2 xor b2,a3 xor b0,a4 xor b1,a5 xor b2,a6 xor b0,a7 xor b1,a8 xor b2

解密处理过程
解密处理过程需要4个参数：
Flow        字符串，表示需解密的数据流
Code        字符串，表示解密时使用的密码
Bits                整型，用于确定提取校验码检验的间隔
Mode        整型，用于确定校验码ASCII码二进制数位的来源
3．密码提取（Code Extract Part）
在数据流中为每一位数据与所获得密码对应位再进行一次位异或运算。如果密码正确即得到了未加密时的数据流。
4．校验码检验及去除（Flow Check Part）
在提取密码的同时，将进行校验码检验及去除的工作。每当提取了8*Bits+1位的密码之后就自动进行。方法是检验第8*Bits+1位数据的ASCII码的二进制数是否是前8*Bits位中固定8位的ASCII码二进制数的Mode位的顺序排列。

加密的可行性
对于一个给定的数据流和密码，当使用了上述的加密方法，流的数据不再保持原有的状态，无法直接读取。并且因为是流和密码混合的运算，在不知道其中任何一个的情况下，都无法通过数学方法得到另一个。此运算对于任意一位，都可表示为函数z=f(x,y)，x为明文，y为密码，z为暗文。由函数性质可知，在x、y、z中任意两个未知的情况下，无法用数学方法同时求得。因此如果被得知某一组明文、暗文和密码，甚至在知道了整个加密方法（包括可以调节的两个参数Mode和Bits）的情况下，要想通过暗文在没有密码的情况下得到明文都是很困难的。在下文的优越性讨论中有关于提高的安全性能及防止相关的传统破解方式的介绍。

解密的可行性
如果需要解密后的数据保持原状，则需要两点条件：
1、        对数据流中一位与同一个数进行两次异或运算，所得结果与原数相同。
2、        在加密过程中插入的校验码能够在解密过程中被正确识别。
先证明第一点
因为在加密和解密过程中使用的是数据流对应的Ascii码，所以不妨设数据流中某一位的Ascii码值为X（1<=X<=255）。
由于加密和解密中只有插入的校验码与数据流的排列有关，而在此的第一点中不讨论校验码的问题，所以对于任意位，可以认为其实独立的。上面的假设不失一般性。
又对于一位二进制数的异或运算，其结果只与本位相关，不存在进位和退位的情况。所以对于固定二进制数的X，只要对应的每位二进制数在与另一个二进制数K对应位进行两次异或运算后，结果与原数X一致，就可以认为第一点条件满足。
问题归结为某个二进制数A与另一个二进制数B（A、B取值无必然联系）进行两次异或运算后，仍然为A。
因为A、B的取值无必然联系，所以存在A=B和A<>B两种情况。根据异或运算的定义
当A=B时，A xor B=0。而0 xor B，当B=1时，其值等于1，由A=B得，A=1=0 xor B。同理，当B=0时，0 xor B=0=A。
当A<>B时，A xor B=1。当B=1时，1 xor B=0，又A<>B，所以A=0=1 xor B。同理，当B=0时，0 xor B=1=A。

再证明第二点
由加密时插入校验码和嵌入密码的顺序可知，校验码是由原数据流产生。而解密是正好相反，先进行密码提取，再检查校验码。所以当密码正确时，校验码也同样保持在嵌入密码前的状态。所以利用同样的方法生成的对比码和校验码应该是相同的。

3、开发组成员资料集
资料集填写要求：
1、资料集中每人只允许填写和修改一组信息，如果发现存在重复的信息[特指可以识别身份的项目，包括联系方式、证件号码、修改内容等的信息。]，则只有第一条有效。填写时请在之后添加一张表格。
2、需填写信息中加入*的为必添内容，如果存在遗漏，则对应的一组信息视为无效。
3、请真实填写联系方式，并及时关注联系方式是否畅通，以便在将来能维护您作为开发组成员的权利。
1、核心开发组成员资料集
称谓*        Hzj_jie
年龄       
性别       
联系方式*        [email protected]

证件类型       
证件号码       
开发内容*        FCES最初版本的所有内容，包括自由簇思想、分区基础属性区、自由簇管理方式、文件索引记录管理方式、简单的文件系统实现。以及流插入检查加密方式的加密解决方案。
添加日期*       

2、修改组成员资料集
称谓*       
年龄       
性别       
联系方式*       
证件类型       
证件号码       
修改内容*       
添加日期*