浮云闲笔— Windows Live

浮云闲笔 — Windows Live

2010-07-02 12:17:36 阅读7 评论0 字号:

关于de-duplication的一点想法(待补充)
最近看了几款de-duplication(重复数据删除)的软件,NoClone、Duplicate Files Finder等,感觉有些地方需要改进。其中比较重要的一点是,这些软件似乎将文件作为比较的基本单位。由此导致的一个问题是:如果两个软件的文件夹中都包含有同一个库文件,其中一个库文件作为“重复数据”被删除了,显然对应的软件将没办法运行。另外,如果作用在两个不同版本的项目源代码,也将出现某个,甚至是两个版本都不完整的情况。
为此,为“重复数据删除”建立一个模型是非常必要的。首先必须解决的关键问题是:什么是重复数据?
重复数据,应该是内容xx相同的多份独立数据(待完善)...


从Filemon看Windows文件系统过滤驱动的实现
FileMon 是一个系统文件监视工具,可以监视应用程序进行的文件读写操作。它将所有与文件一切相关操作(如读取、修改、出错信息等)全部记录下来以供用户参考,并允许用户对记录的信息进行保存、过滤、查找等处理,这就为用户对系统的维护提供了极大的便利。
FileMon实现包含设备驱动程序和GUI部分。首先取到要监控卷的设备句柄,然后在设备上挂接自己的过滤设备,系统访问卷的所有操作都会经过过滤设备,然后再有此设备发给真正的文件设备对象完成文件的访问。
GUI
Save和Save As命令将List View中的所有信息保存在选定的日志文件中。
Copy命令将ListView中选中的行拷贝到剪贴板。
History Depth设置在ListView显示的历史信息的数目。0表示无限制,即所有输出都将显示在ListView中。点击该按钮后,将弹出对话框,让用户输入一个数值。该数值将在本次GUI关闭时,透过调用SavePositionSettings保存到注册表的Setting表项,以便下次重启GUI时使用。
Highlight Colors用于设置背景和前景颜色,似乎没有用到。
Font…用于设置ListView中显示的字体。该数值将在本次GUI关闭时,透过调用SavePositionSettings保存到注册表的Setting表项,以便下次重启GUI时使用。
Find…用于在ListView中查找给定的字符串。这纯粹是GUI的行为。
Explorer Jump:该项打开Explorer,并navigate到给定的文件/文件夹。这纯粹是GUI的行为,调用ShellExecute。
Filter/Highlight:向驱动程序发送IOCTL_FILEMON_SETFILTER。
Clear Display:向驱动程序发送IOCTL_FILEMON_ZEROSTATS清零信息,同时根据驱动程序的内容更新GUI的ListView的内容,即清空之。
Always On Top表明GUI是否应该总在顶层。该数值将在本次GUI关闭时,透过调用SavePositionSettings保存到注册表的Setting表项,以便下次重启GUI时使用。
Auto Scroll表明是否ListView应该自动滚行。这是GUI的行为。
Time Duration:表明是否在ListView中显示请求的持续时间,而不是xx时间。该数值将在本次GUI关闭时,透过调用SavePositionSettings保存到注册表的Setting表项,以便下次重启GUI时使用。
Show MS:表明在ListView中显示请求的时间时,是否显示毫秒信息。如果选中,则表示显示毫秒信息,显示格式为hh:mm:ss.mmm;如果未选中,则表示不选中毫秒信息,显示格式为hh:mm:ss。注意,当选中以Time Duration形式显示请求时间时,这一项不起作用,应该被禁止。该数值将在本次GUI关闭时,透过调用SavePositionSettings保存到注册表的Setting表项,以便下次重启GUI时使用。
Capture Events:当选中该项时,表明要启动过滤;当未选中该项时,表明要停止过滤。分别向驱动程序发送IOCTL_FILEMON_STARTFILTER和IOCTL_FILEMON_STOPFILTER。
Named Pipes:当选中该项时,表明是否要过滤特殊文件系统。分别向驱动程序发送IOCTL_FILEMON_HOOKSPECIAL和IOCTL_FILEMON_UNHOOKSPECIAL。
Mail Slots:当选中该项时,表明是否要过滤特殊文件系统。分别向驱动程序发送IOCTL_FILEMON_HOOKSPECIAL和IOCTL_FILEMON_UNHOOKSPECIAL。
Drives C: (Fixed):当选中该项时,表明要过滤驱动器C。考虑到系统可以有26个驱动器。用一个32位整数表示这些驱动器是否需要被过滤的位图。构造该位图,设置与驱动器C对应的位,透过HookDrives向驱动程序发送IOCTL_FILEMON_SETDRIVES,根据返回的位图判断各个驱动器是否被成功过滤,从而修改GUI。
Drives D: (Fixed):当选中该项时,表明要过滤驱动器D。
Drives E: (CD):当选中该项时,表明要过滤驱动器C。
All Drives:当选中该项时,表明要过滤所有驱动器。同上处理,传递参数MaxDriveSet,调用GetLogicalDrives的返回结果。
No Drives:当选中该项时,表明要不过滤任何驱动器。同上处理,传递参数0。
注册表项
Filemon的注册表项位于HKEY_CURRENT_USER中,路径为Software\\Sysinternals\\Filemon。包括以下内容:Settings、InFilters、ExFilters和HiFilters。
Setting包含:
posversion;
left/top/width/height:保存GUI窗口的位置。
column[NUMCOLUMNS]:ListView的各列宽度。
curdriveset:当前挂钩的驱动器集合,以位图的形式表示各个驱动器是否当前被挂钩。
historydepth:ListView显示的列数。
maximized:GUI窗口显示是否{zd0}化。
timeduration:是否在ListView中显示请求的持续时间,而不是时间。
showms:是否显示毫秒级信息。
logreads:
logwrites:
ontop:是否将GUI保持在顶层。
hookpipes:是否要挂钩Named Pipes。
hookslots:是否要挂钩Mail Slots。
showtoolbar:是否显示工具条。当前设置为显示,且不能更改。
font:ListView的显示字体。
highlightfg;
highlightbg;
内核驱动
Filemon内核的设备驱动对象保存在全局变量FilemonDriver中。从其中创建了多个设备对象:
GUI设备对象:创建用于GUI通信的设备,它只是被保存为一个局部变量,将该设备对象的设备扩展的Type域设置为GUIINTERFACE。根据该类型域判断请求是否来自GUI。
每个驱动器符号(从A到Z)的挂钩设备表。保存在长度为26的DriveHookDevices全局数组中。查找每个驱动器符号的文件句柄,获得和文件对象相关的设备对象,找出它关联到什么设备。之后创建一个挂钩设备对象,设置挂钩对象的Hooked标志,并挂接到上述驱动器设备对象。以后有请求到达驱动器设备时,将被我们挂接到该驱动器设备上的挂钩设备对象截获。
为特殊文件系统创建的挂钩设备对象。包括NamedPipeHookDevice和MailSlotHookDevice,原理同上。
{yj}性快照和非{yj}性快照

在{dy}次修改快照源的数据时,需要将快照源的数据拷贝到COW设备上。假定快照源的数据所在的位置称为旧chunk,完成上述需要三个步骤:

每个快照都有一种例外信息管理机制,叫做例外仓库,通过快照结构的store域指向。例外仓库结构exception_store给出了管理例外的方法:

struct exception_store {
void (*destroy) (struct exception_store *store);        //在使用完之后销毁例外仓库
 int (*read_metadata) (struct exception_store *store);       //目标器在调用这个函数之后才能读取COW设备
 int (*prepare_exception) (struct exception_store *store, struct exception *e); //查找保存下一个例外的位置
void (*commit_exception) (struct exception_store *store, struct exception *e, void (*callback) (void *, int success), void *callback_context);                //用这个例外更新元数据
 void (*drop_snapshot) (struct exception_store *store);       //快照无效,在元数据中记录下来
void (*fraction_full) (struct exception_store *store, sector_t *numerator, sector_t *denominator); //返回快照有多满
 struct dm_snapshot *snap;             //回指到所属快照
 void *context;                //例外仓库的上下文
};

在这些方法中,prepare_exception相当于第1个步骤,可以理解为例外信息准备;而commit_exception相当于第3个步骤,即例外信息提交。

当前的快照实现支持两种方式的例外仓库,一种称为{yj}性例外仓库,一种为非{yj}性例外仓库。

非{yj}性例外仓库是一种简单的例外信息管理机制。元数据只存在内存,即快照结构的例外表。在COW设备上只保留快照数据,并且是根据例外发生的先后顺序存放的。一旦关机,非{yj}性例外仓库的元数据便丢失了,快照即失效了。

按照这一机制,非{yj}性例外仓库只需要一个变量,记录在COW设备上保存(快照源的)下一个数据的起始扇区编号。

struct transient_c {
 sector_t next_free;
};

计算这个编号的方法非常简单。只需要确保这个位置开始的一个chunk没有超出COW设备的长度,即可以将它作为快照源的数据的存放位置。同时修改这个编号,往前推进一个chunk。当然如果这个位置的chunk已经超出COW设备的长度,则返回一个错误值,由上层调用负责来将这个快照置为无效状态。

对于非{yj}性例外仓库,前面描述的三个步骤的第3步是不必要的。因为例外信息已经记录在快照结构的例外表中。因此commit_exception不需要做特定的元数据记录,直接调用上层设定的例外提交回调函数即可。

非{yj}性例外仓库不在COW设备上保存元数据,因此也无所谓读取。故read_metadata函数也直接返回0。

与此相对应,除了保存快照源的数据外,{yj}性例外仓库还将元数据保存在COW设备上。{yj}性例外仓库的上下文结构如下:

struct pstore {
 struct dm_snapshot  *snap;     //回指到快照
 int      version;
 int      valid;
 uint32_t    exceptions_per_area; //每个区域含有的例外个数
/* Now that we have an asynchronous kcopyd there is no need for large chunk sizes, so it wont hurt to have a whole chunks worth of metadata in memory at once. */
 void     *area;     //保存一个chunk的元数据
 uint32_t    current_area;   // Used to keep track of which metadata area the data in 'chunk' refers to
 uint32_t    next_free;    //用于例外的下一个空闲chunk
 uint32_t    current_committed; //The index of next free exception in the current metadata area
 atomic_t    pending_count;
 uint32_t    callback_count;
 struct commit_callback *callbacks;
 struct dm_io_client  *io_client;
};

COW设备的布局如图所示。COW设备空间以chunk为单位,{dy}个chunk保存了标识该快照的一些基本信息:包括魔术(0x70416e53)、有效标志、版本号以及以扇区为单位的chunk长度。之后的空间被分成多个区,每个区(area)由一个chunk的元数据和相应chunk数目的数据组成,形成交隔的布局。区的{dy}个chunk用来保存多个例外,其数目可以计算出来,保存于exceptions_per_area域。这样,元数据后是exceptions_per_area个chunk数据。因此一个区总共的chunk数是exceptions_per_area+1。

在这样的设计下,空闲chunk编号next_free分配算法如下:初始从第2个开始,即跳过头信息chunk和{dy}个源数据区域。之后不断增1,但是需要中间的元数据区。即当next_free在增加后,如果模一个区的chunk数为1,表明此时,next_free指向元数据区,因此再将其加1。

注意到,元数据也是以chunk为单位写入磁盘的。在pstore结构中,area保存了一个chunk的元数据,current_area记录了它的区号,current_committed记录了在当前区中的下一个空闲例外的编号。提交的例外信息会首先保存在area中,一旦所有发起的数据均已经写入了COW设备,或者说一个区的所有chunk的数据都已经写入COW设备,则会将area中的元数据也写入(提交)到COW设备中。并根据需要确定是否要转到下一个区,转之前会先将下一个区在磁盘上的信息清零。

由于元数据也保存在COW设备上,{yj}性例外仓库可以使得快照在系统重启之后依然有效。read_metadata负责在快照启动时重建例外表。这个过程是:从COW设备读取头信息,确保魔数、有效性及版本号等信息正确。然后循环读取每个area的元数据,并根据其中的映射信息构造快照结构的例外表,直到映射信息中new_chunk为0,这表明到达了空闲的chunk。

device mapper的“kcopyd内核拷贝进程”

在device mapper中,需要执行某些异步拷贝。例如,在{dy}次写快照源前,需要将快照源的数据拷贝到COW设备上;又如,在镜像模块进行恢复时,需要将某个设备的数据拷贝到其他镜像设备上。这些异步拷贝都由“内核拷贝进程”进行。

“内核拷贝进程”提供了一些所谓的“客户端”API函数,由要进行异步拷贝的内核模块使用。其中

int kcopyd_client_create(unsigned int num_pages, struct kcopyd_client **result);

void kcopyd_client_destroy(struct kcopyd_client *kc);

分配和释放“kcopyd客户端”结构。而

int kcopyd_copy(struct kcopyd_client *kc, struct io_region *from, unsigned int num_dests, struct io_region *dests, unsigned int flags, kcopyd_notify_fn fn, void *context);

用于向“kcopyd内核拷贝进程”提交一个拷贝任务。其中kc为提交拷贝任务的“kcopyd客户端”,from为拷贝源,num_dests和dests为拷贝目标数目以及拷贝目标数组。在拷贝完成之后,作为“客户端”的内核模块通常要执行某些善后工作,这是在参数中指定了回调函数和回调上下文。

每个提交上来的拷贝任务都会被“内核拷贝进程”添加到任务链表中。根据任务所处的阶段不同,有三个这样的链表:i)等待页面的任务链表_pages_jobs;ii)有页面、等待发起I/O的任务_io_jobs;iii)已经完成的任务_complete_jobs。“内核拷贝进程”的主要任务是循环处理这三个任务链表。

任务刚提交时,被加入到_pages_jobs链表,在从“kcopyd客户端”的页面池中分配所需个数的页面后,这个任务会转移到_ios_jobs链表。

任务刚开始加入到_ios_jobs链表时,rw标志为读,一旦调度,将从拷贝源读取数据到任务的页面,然后通过设定的回调函数将rw标志改为写,并重新插入到_ios_jobs链表。再次调度时,会将任务的页面中的数据拷贝到所有的拷贝目标,在完成之后,回调函数把这个任务又转移到_complete_jobs链表。

_complete_job链表中的任务是需要进行善后处理的,包括将使用的页面重新回收到“kcopyd客户端”的页面池中,并将kcopyd任务从链表中取出,并释放,最终调用“客户端”内核模块指定的回调函数,即kcopyd_copy函数的fn参数。




引文来源  
<#--{zx1}日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--相关文章--> <#--历史上的今天--> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构-->
郑重声明:资讯 【浮云闲笔— Windows Live】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——