支持含有碎片的文件仿真

mdyblog

chenall 发表于 2014-12-24 10:59
修改了一下上面的代码(复杂度还是不变,只是尽量减少了一些循环内部的计算),目前时间应该和0227差不多.

...

测试结果 10G的分区， 10秒。
和120322查不多(11秒)。
120227 是 3秒

刚才网络突然好慢啊。 图一直传不上来。
如图：

chenall

和我的测试结果相差太多了,我用前面的版本时间减小了一半...

再试试这个版本,应该可以瞬间完成了.

原理,考虑到目前GRUB4DOS的sector_size值只有两种512和2048,所以针对这两种情况优化了一下算法,其它情况使用原来的方案,慢慢计算.

这个版本一般情况下都可以瞬间完成.

我是按照我对这一段代码的理解来改写的,就是不知会不会产生其它问题,需要更多的时间测试一下.

mdyblog

chenall 发表于 2014-12-24 11:42
和我的测试结果相差太多了,我用前面的版本时间减小了一半...

再试试这个版本,应该可以瞬间完成了.

这个算法牛！！ 瞬间完成。

麻烦加到 最新的0.46a上， 我再试试。

chenall

mdyblog 发表于 2014-12-24 12:29
这个算法牛！！ 瞬间完成。

麻烦加到 最新的0.46a上， 我再试试。

把这个补丁应用到0.4.6a上,效果不是很明显,

因为0.4.6a需要读取所有扇区的,一个一个读过去的,这个要看yaya是不是能优化一下了.

mdyblog

chenall 发表于 2014-12-24 14:35
把这个补丁应用到0.4.6a上,效果不是很明显,

因为0.4.6a需要读取所有扇区的,一个一个读过去的,这个要看 ...

新版0.46a问题最多最严重，
现在解决的部分，对 新版0.46a， 反倒只是小头。
最耗时的那个 “需要读取所有扇区的,一个一个读过去的”。
测试还要52秒。

目前这个版本是最新的0.46a(20141206)吗

麻烦你先用上面的成果， 将0.46a20120334和0.46a20141206改正。 后面yaya再接着改。免得yaya有重复你的工作。

chenall

上面就是基于最新版本的0.4.6a代码.测试没有问题之后我再更新一下源码,yaya可以接着继续优化.

mdyblog

热切期盼 yaya大 赶快 解决 0.46a 山区序列 map巨慢的问题。
测试最新grub4dos-0.4.6a-2014-12-25.7z, 10G分区， 要52秒。

2011yaya2007777

几种方案：
1.  判断是否属于扇区序列。即便是，也不能简单跳过块列表函数。因为不连续的扇区序列也可以映射，此时需要建立映射表。要增加不少代码。
另外，对于大的文件映射，连续时，也白白浪费时间。
2.  执行块列表函数时，不真正读磁盘。效果不理想。仍然有延时，且对于不连续文件，只返回 1 组参数。没有仔细研究错在哪里。
3.  从文件分配表判断连续性。这是快捷的方法。但是文件系统类型太多，增加代码过多。

权衡利弊，觉得增加一个参数较妥。当用户确认文件连续时，可以使用该参数，加快执行速度。
参数是    --continuou

chenall

对于0.4.6a的这个map检测流程我看得不是很明白.

请问一下0.4.6a执行blocklist_func,返回的主要信息是什么?有没有具体的流程也许可以再优化下,

个人认为使用一个额外的参数来解决不太好,对于用户来说能够不用参数就尽量不要使用.越简单越好.

mdyblog

2011yaya2007777 发表于 2014-12-25 20:39
几种方案：
1.  判断是否属于扇区序列。即便是，也不能简单跳过块列表函数。因为不连续的扇区序列也可以映 ...

1：
这个效果好啊！ 瞬间完成。
佩服！佩服！
终于看到了希望——就在眼前。


看来问题接近完美了。

2：
可以直接通词法分析， 就能判断扇区序列是否连续。
这样相对扇区序列空间大小的时间复杂度为 O(0).

(hd0,0)2+20,33+5,87+300
这个肯定是不连续的。

(hd0,0)2+2000
这个肯定是连续的。

下面也是连续的，map其实不考虑， map只能扇区对齐
(hd0)800+100,51100     //不能map

1） 最简单的方法， 就数逗号。没有逗号就是直接当连续的。有逗号走原来的流程。
对我们中国人来说，这个完全够用了。（代价也最小）。
if (逗号数=0) 就是连续的。(走--continuou流程)
else               就是不连续的。 (走原来的流程)

2）复杂点(完善点——完美主义者)。
执行一次排序，合并，
再:
if (分片数=1) 就是连续的。(走--continuou流程)
else               就是不连续的。  (走原来的流程)
//适用的角度，意义不大。但是作为程序员，感觉心里舒服点。

yaya好样的，加油哦！

2011yaya2007777

对于0.4.6a的这个map检测流程我看得不是很明白.

其实我也不太明白，尤其是扇区序列。
在 map 中执行 blocklist_func，原来 0.4.5c 是读文件的首扇区及末扇区，用来确定文件的首扇区（start_sector）和扇区数（sector_count）。
但是后面紧接着 disk_read_start_sector_func() 将重新设置start_sector和sector_count。因此，对于 0.4.5c，
if (mem == -1ULL)
{
......
}
可以删除。

对于 0.4.6a，此处是用来确定文件的连续性，获得各段文件起始及扇区数。
前面描述的不对，确定连续性也不是 1 扇区 1 扇区地读。fat，iso9660 是最大 4 扇区，ntfs 是最大 8 扇区。

个人认为使用一个额外的参数来解决不太好,对于用户来说能够不用参数就尽量不要使用.越简单越好.

那就采用：如果是连续的扇区序列，则跳过连续性检查。
我已经上传了一个补丁，打在我的分支，不知这么没有进入你的主干。如果可能的话，请帮忙撤销，或者告诉我如何撤销。

chenall

发现没有同步到过来,比较奇怪,

不过这样也好,省得麻烦.

一般原则上不建议撤销,特别是已经上传同步的代码.

不过目前看来没有同步过来,你自己可以撤销

撤销的话就是强制更新

具体操作方法
首先在本地分支恢复到上一个版本(下面的dabcf1d就是版本ID).
git reset dabcf1d

注: 以上只是恢复log,会保留代码的改动.如果不需要保留可以加参数--hard即
git reset --hard dabcf1d
然后修改重新更新
git commit xxxxx

最后要更新源码时需要加-f进行强制覆盖更新.
git push -f

chenall

另外好像原来的blocklist_func就是可以直接返回块列表的吧?

只不过0.4.5c的map只是简单检测是否连续,这样速度很快.

0.4.6a应该只需要稍微修改一下就行了,我看你增加了一个query_block_entries=4的类型.

我觉得可以继续使用0.4.5的方式,只需要修改blocklist_func让它检测所有块就行了.

mdyblog

chenall 发表于 2014-12-26 16:54
另外好像原来的blocklist_func就是可以直接返回块列表的吧?

只不过0.4.5c的map只是简单检测是否连续,这 ...

大哥们啊， 能先放出个版本吗？ 能自动判读的。（不要--continuou，这个开关迟早会被淘汰）
等米下锅啊！

chenall

抽了一些时间改了一个版本,先试试看有没有什么问题...

yaya也可以检查一下,看看我逻辑是否有问题.

PS: 可以尽量测试看看能发现多少问题(尽可能的多测试,比如单文件块,多文件块,还有扇区块之类的),我要等明天10点之后才有时间继续处理.

mdyblog

chenall 发表于 2014-12-26 17:50
抽了一些时间改了一个版本,先试试看有没有什么问题...

yaya也可以检查一下,看看我逻辑是否有问题.

这个还是慢。 10G需要50秒。


--continuou不支持了。


盼啊---盼啊---

chenall

可以先测试一下目前这样子会不会有问题.

上面的修改主要是让0.4.6a的这些代码和0.4.5c保持大体一致.

明天再针对块文件(block file)优化一下,,也就是(hdx,y)aaaa+bbbb这类的块文件.

1. 首先用0.4.5c的方法判断文件是否连续的,如果是的话就直接返回了.(对于blockfile和普通文件都很快)
2. 如果不是连续的文件的话就分两种情况处理
   对于block文件,根据块列表来处理,这样很快.
   对于普通文件,目前没有什么很好的方案还是使用老方案,一扇区一扇区读过去.

chenall

发现几乎所有的文件系统最终都是调用rawread函数来读的..

也许可以在rawread函数上动些手脚,这样子不用管什么文件系统应该都可以通用.

具体的明天再试验一下.

mdyblog

chenall 发表于 2014-12-26 20:44
可以先测试一下目前这样子会不会有问题.

上面的修改主要是让0.4.6a的这些代码和0.4.5c保持大体一致.

>>对于普通文件,目前没有什么很好的方案还是使用老方案,一扇区一扇区读过去.
不是有文件分配表吗。
一般是分析分配表，就知道文件布局，也就知道连续性，也获得扇区列表。
这些算法都是或接近O(0)的算法。
如果文件和少碎片，就是O(0)。
如果全是碎片，那就是O(n).

用来map的文件，一般是连续的，（或基本是连续的，就几个分段）。
对巨大的文件， 这种算法实际也是O(n)，但是极大缩小了比例因子。
文件分配表的1扇区，对应许多个节点信息。1个节点信息对应许多个文件扇区。
如果磁盘整理好了，由于比例因子极小， 一般也是不到1秒。

----
我想，目前的设计，本来就是分析 文件分配表吧。
否则， block命令没那么快。读完一个巨大的文件， 时间那可老长了！！！

chenall

使用上面的方案实验了一下,大家可以对比测试一下新旧版本的使用情况,如果我的逻辑和算法正确的话应该是不会有什么问题.

可能会影响到map的准确性,先上传上来测试一段时间.

这个改动对于blocklist命令进行了优化,特别是对于大文件效果更明显.

使用这个版本map一个大文件,一般情况下都可以瞬间完成.使用blocklist命令查看文件的块列表同样的速度飞快.

chenall

mdyblog 发表于 2014-12-27 09:31
>>对于普通文件,目前没有什么很好的方案还是使用老方案,一扇区一扇区读过去.
不是有文件分配表吗。
...

之前的设计不是分析文件分配表的,就像前面yaya所说的一样,如果按照文件分配表那当然快了,但是需要针对每个文件系统,很麻烦.

0.4.5c的情况
执行blocklist会一个扇区块一个扇区块读(没有真的读),然后最终得到块列表.
map命令调用的blocklist命令只读首尾扇区,然后进行判断是不是一整个块,这样速度很快.

0.4.6a完全是一个扇区一个扇区读的,如果文件很大的话需要很大的循环才能完成,所以就造成了上面的10G分区需要50秒.

mdyblog

chenall 发表于 2014-12-27 09:34
使用上面的方案实验了一下,大家可以对比测试一下新旧版本的使用情况,如果我的逻辑和算法正确的话应该是不会 ...

1：瞬间完成，牛！



2：
》》可能会影响到map的准确性,先上传上来测试一段时间.
难道 获得是扇区序列可能不准吗？ 那可要命啊。

chenall

mdyblog 发表于 2014-12-27 10:25
1：瞬间完成，牛！

因为改变了blocklist的计算方法,理论上是没有什么问题,需要多多测试而已

这个不只是针对(hd0)xx+y的,而是针对所有类型文件的,包括(hd0,1)/100G.VHD这种情况.

测试的话主要是看blocklist命令返回的信息和旧版的是否一致.一样的话就没有什么问题了.

我自己测试了一下都是一样的.

可以用blocklist命令对比一下新旧版本,看有没有什么区别.

mdyblog

chenall 发表于 2014-12-27 10:33
因为改变了blocklist的计算方法,理论上是没有什么问题,需要多多测试而已

这个不只是针对(hd0)xx+y的 ...

》》因为改变了blocklist的计算方法,理论上是没有什么问题,需要多多测试而已
哦。
不是原理上的漏洞，那就好。——不是"明知有问题，装作没看见。"

即使有问题，那也只能算作BUG——慢慢改吧——BUG是改不完的。
---------
这么说，这基本上是个发行版本了？！

chenall

没什么问题的话就是差不多这样子了

mdyblog

chenall 发表于 2014-12-27 11:04
没什么问题的话就是差不多这样子了

网上版本1227，正常，瞬间，如图：

chenall

这个版本和前面的代码是一样的,没有修改..

0.4.5c的暂时还没有修改,0.4.5c只影响blocklist命令,map命令影响不是很大,以后再看情况打是否要打这个补丁进去.

2011yaya2007777

关于变量 long query_block_entries（查询块项） 的探讨：

0.4.5c：初始化=0; 外部3处测试连续性设置=-1；函数返回1=连续，2=不连续，3=压缩文件认为不连续，0=程序失败（撤销请求‘-1’，回归0）。
0.4.6a：初始化=0; 外部3处测试连续性并且获取分段参数设置=-1；函数返回 blklst_num_entries（块列表项数=0～n），3=压缩文件，-1=程序失败。

disk_read_blocklist_func 函数是根据 query_block_entries 变量判断：
0.4.5c： >=0，是命令行调用，需测试文件全部长度，并打印信息； <0，是 G4D 内部调用，仅判断连续性，只测试文件首扇区及末扇区，不打印信息。
0.4.6a： >=0，是命令行调用，需测试文件全部长度，并打印信息； <0，是 G4D 内部调用，获取分段参数，需测试文件全部长度，不打印信息。
因此，程序失败时返回 ‘-1’ 不妥，应当撤销请求 ‘-1’，回归0。否则紧接命令行调用时，会出错。
另外返回 3 也没有意义，并且会被错误认为 blklst_num_entries=3。

发现 1 个 bug：
执行    blocklist (hd0)+0x20000000
返回    (hd0)
错误定位在

1. blocklist_func (char *arg, int flags)
   
2. {
   
3.   char *dummy = NULL;
   
4.   int err, i;

复制代码

应当是

1. blocklist_func (char *arg, int flags)
   
2. {
   
3.    char *dummy = NULL;
   
4.   int i;
   
5.   unsigned long long err = 0;

复制代码

不点

你们做这个工作很有效率，很棒，我不再参与了。究竟该怎么做，你们研究着办。

贯通 DOS 与 grub4dos，可能是我做的最后一个工作了。今后我不再参与 grub4dos 的开发了。

通报一下，让大家知道我的情况。

sunsea

mdyblog 发表于 2014-12-27 09:31
>>对于普通文件,目前没有什么很好的方案还是使用老方案,一扇区一扇区读过去.
不是有文件分配表吗。
...

常数时间复杂度是O(1)吧。。。

查文件分配表是个好方法。但是以后每添加一个文件系统就得多写一段代码了。

纠正以上:可以从读文件的算法里抄一下代码，稍微改动一下就行。（读文件貌似已经解决碎片问题了）