唐福林 博客雨

 传统的文件同步方案有rsync(单向) 和 unison(双向)等，它们需要扫描所有文件后进行比对，差量传输。如果文件数量达到了百万甚至千万量级，扫描所有文件将非常耗时。而且正在发生变化的往往是其中很少的一部分，这是非常低效的方式。

之前看了Amazon的Dynamo的设计文档， 它们每个节点的数据是通过Hash Tree来实现同步，既有通过日志来同步的软实时特点(msyql, bdb等)，也可以保证最终数据的一致性(rsync, unison等)。Hash Tree的大体思路是将所有数据存储成树状结构，每个节点的Hash是其所有子节点的Hash的Hash，叶子节点的Hash是其内容的Hash。这样一 旦某个节点发生变化，其Hash的变化会迅速传播到根节点。需要同步的系统只需要不断查询跟节点的hash，一旦有变化，顺着树状结构就能够在logN级 别的时间找到发生变化的内容，马上同步。

文件系统天然的是树状结构，尽管不是平衡的数。如果文件的修改时间是可靠的，可以表征文件的变化，那就可以用它作为文件的Hash值。另一方面，文 件的修改通常是按顺序执行的，后修改的文件比早修改的文件具有更大的修改时间，这样就可以把一个目录内的最大修改时间作为它的修改时间，以实现Hash Tree。这样，一旦某个文件被修改，修改时间的信息就会迅速传播到根目录。

一般的文件系统都不是这样做的，目录的修改时间表示的是目录结构最后发生变化的时间，不包括子目录，否则会不堪重负。因为我们需要自己实现这个功 能，利用Linux 2.6内核的新特性inotify获得某个目录内文件发生变化的信息，并把其修改时间传播到它的上级目录(以及再上级目录)。Python 有 pyinotify，watch.py的代码如下：

1. #!/usr/bin/python  
2.   
3. from pyinotify import *  
4. import os, os.path  
5.   
6. flags = IN_CLOSE_WRITE|IN_CREATE|IN_Q_OVERFLOW  
7. dirs = {}  
8. base = ’/log/lighttpd/cache/images/icon/u241′  
9. base = ’tmp’  
10.   
11. class UpdateParentDir(ProcessEvent):  
12.     def process_IN_CLOSE_WRITE(self, event):  
13.         print ’modify’, event.pathname  
14.         mtime = os.path.getmtime(event.pathname)  
15.         p = event.path  
16.         while p.startswith(base):  
17.             m = os.path.getmtime(p)  
18.             if m < mtime:  
19.                 print ’update‘, p  
20.                 os.utime(p, (mtime,mtime))  
21.             elif m > mtime:  
22.                 mtime = m  
23.             p = os.path.dirname(p)  
24.       
25.     process_IN_MODIFY = process_IN_CLOSE_WRITE  
26.   
27.     def process_IN_Q_OVERFLOW(self, event):  
28.         print ’over flow’  
29.         max_queued_events.value *= 2  
30.   
31.     def process_default(self, event):  
32.         pass  
33.   
34. wm = WatchManager()  
35. notifier = Notifier(wm, UpdateParentDir())  
36. dirs.update(wm.add_watch(base, flags, rec=True, auto_add=True))  
37.   
38. notifier.loop()  

#!/usr/bin/python from pyinotify import * import os, os.path flags = IN_CLOSE_WRITE|IN_CREATE|IN_Q_OVERFLOW dirs = {} base = ‘/log/lighttpd/cache/images/icon/u241′ base = ‘tmp’ class UpdateParentDir(ProcessEvent): def process_IN_CLOSE_WRITE(self, event): print ‘modify’, event.pathname mtime = os.path.getmtime(event.pathname) p = event.path while p.startswith(base): m = os.path.getmtime(p) if m < mtime: print ‘update’, p os.utime(p, (mtime,mtime)) elif m > mtime: mtime = m p = os.path.dirname(p) process_IN_MODIFY = process_IN_CLOSE_WRITE def process_IN_Q_OVERFLOW(self, event): print ‘over flow’ max_queued_events.value *= 2 def process_default(self, event): pass wm = WatchManager() notifier = Notifier(wm, UpdateParentDir()) dirs.update(wm.add_watch(base, flags, rec=True, auto_add=True)) notifier.loop() 在已经有Hash Tree的时候，同步就比较简单了，不停地获取根目录的修改时间并顺着目录结构往下找即可。需要注意的是，在更新完文件后，需要设置修改时间为原文件的修改时间，目录也是，保证Hash Tree的一致性，否则没法同步。mirror.py的代码如下

#!/usr/bin/python  

1.   
2. import sys,time,re,urllib  
3. import os,os.path  
4. from os.path import exists, isdir, getmtime  
5.   
6. src = sys.argv[1]  
7. dst = sys.argv[2]  
8.   
9. def local_mirror(src, dst):  
10.     if exists(dst) and mtime == getmtime(dst):  
11.         return  
12.     if not isdir(src):  
13.         print ’update:’, dst  
14.         open(dst,’wb’).write(open(src).read())  
15.     else:  
16.         if not exists(dst):  
17.             os.makedirs(dst)  
18.         for filename in os.listdir(src):  
19.             local_mirror(os.path.join(src,filename), os.path.join(dst,filename))  
20.     os.utime(dst, (mtime,mtime))  
21.   
22. def get_info(path):  
23.     f = urllib.urlopen(path)  
24.     mtime = f.headers.get(‘Last-Modified’)  
25.     if mtime:  
26.         mtime = time.mktime(time.strptime(mtime, ’%a, %d %b %Y %H:%M:%S %Z’))  
27.     content = f.read()  
28.     f.close()  
29.     return int(mtime), content  
30.   
31. p = re.compile(r’([\d.]+?) +([\w/]+)’)  
32.   
33. def remote_mirror(src, dst):  
34.     mtime, content = get_info(src)  
35.     if exists(dst) and mtime == int(getmtime(dst)):  
36.         return  
37.     print ’update:’, dst, src  
38.     if not src.endswith(‘/’):  
39.         open(dst,’wb’).write(content)  
40.     else:  
41.         if not exists(dst):  
42.             os.makedirs(dst)  
43.         for mt,filename in p.findall(content):  
44.             mt = int(float(mt))  
45.             lpath = dst+filename  
46.             if not exists(lpath) or int(getmtime(lpath)) != mt:  
47.                 remote_mirror(src+filename, lpath)  
48.     os.utime(dst, (mtime,mtime))  
49.   
50. if src.startswith(‘http://’):  
51.     mirror = remote_mirror  
52. else:  
53.     mirror = local_mirror  
54.   
55. while True:  
56.     mirror(src, dst)  
57.     time.sleep(1)  

#!/usr/bin/python import sys,time,re,urllib import os,os.path from os.path import exists, isdir, getmtime src = sys.argv[1] dst = sys.argv[2] def local_mirror(src, dst): if exists(dst) and mtime == getmtime(dst): return if not isdir(src): print ‘update:’, dst open(dst,’wb’).write(open(src).read()) else: if not exists(dst): os.makedirs(dst) for filename in os.listdir(src): local_mirror(os.path.join(src,filename), os.path.join(dst,filename)) os.utime(dst, (mtime,mtime)) def get_info(path): f = urllib.urlopen(path) mtime = f.headers.get(‘Last-Modified’) if mtime: mtime = time.mktime(time.strptime(mtime, ‘%a, %d %b %Y %H:%M:%S %Z’)) content = f.read() f.close() return int(mtime), content p = re.compile(r’([\d.]+?) +([\w/]+)’) def remote_mirror(src, dst): mtime, content = get_info(src) if exists(dst) and mtime == int(getmtime(dst)): return print ‘update:’, dst, src if not src.endswith(‘/’): open(dst,’wb’).write(content) else: if not exists(dst): os.makedirs(dst) for mt,filename in p.findall(content): mt = int(float(mt)) lpath = dst+filename if not exists(lpath) or int(getmtime(lpath)) != mt: remote_mirror(src+filename, lpath) os.utime(dst, (mtime,mtime)) if src.startswith(‘http://’): mirror = remote_mirror else: mirror = local_mirror while True: mirror(src, dst) time.sleep(1) 如果源文件不在同一台机器上，可以通过NFS等共享过来。或者可以通过支持列目录的HTTP服务器来访问远程目录，mirror.py 已经支持这种访问方式。server.py 是用webpy做的一个简单的只是列目录的文件服务器。由于瓶颈在IO上，它的性能不是关键。server.py的代码如下：

#!/usr/bin/python  

1.   
2. import os,os.path  
3. import web  
4. import time  
5.   
6. root = ’tmp’  
7.   
8. HTTP_HEADER_TIME = ’%a, %d %b %Y %H:%M:%S %Z’  
9.   
10. class FileServer:  
11.     def GET(self, path):  
12.         path = root + path  
13.         if not os.path.exists(path):  
14.             return 404  
15.         mtime = time.localtime(os.path.getmtime(path))  
16.         web.header(‘Last-Modified’, time.strftime(HTTP_HEADER_TIME, mtime))  
17.         if os.path.isdir(path):  
18.             for file in os.listdir(path):  
19.                 if file.startswith(‘.’): continue  
20.                 p = os.path.join(path,file)  
21.                 m = os.path.getmtime(p)  
22.                 if os.path.isdir(p):  
23.                     file += ’/'  
24.                 print m, file  
25.         else:  
26.             print open(path,’rb’).read()  
27.   
28. urls = (  
29.    ”(/.*)”, ”FileServer”,  
30. )  
31.   
32. if __name__ == ’__main__‘:  
33.     web.run(urls, globals())  

#!/usr/bin/python import os,os.path import web import time root = ‘tmp’ HTTP_HEADER_TIME = ‘%a, %d %b %Y %H:%M:%S %Z’ class FileServer: def GET(self, path): path = root + path if not os.path.exists(path): return 404 mtime = time.localtime(os.path.getmtime(path)) web.header(‘Last-Modified’, time.strftime(HTTP_HEADER_TIME, mtime)) if os.path.isdir(path): for file in os.listdir(path): if file.startswith(‘.’): continue p = os.path.join(path,file) m = os.path.getmtime(p) if os.path.isdir(p): file += ‘/’ print m, file else: print open(path,’rb’).read() urls = ( “(/.*)”, “FileServer”, ) if __name__ == ‘__main__’: web.run(urls, globals())
为了获得更好性能，以达到更好的实时性，Hash Tree最好是平衡的，比如BTree。如果一个文件发生变化，同步它需要进行的IO操作为N*M，其中N为数的层数，M为每层的文件数目。现在我们N为 2，M最大为10000，适当减少它可以获得更好的性能，比如N为4，M为100。在以后创建目录结构时，最好能够考虑这方面的因素。

参考：灵感点滴 （http://blog.daviesliu.net/）

在unix痛恨者手册中, indent 被当作一个臭名昭著的反面例子给出.不过,从客观角度讲,目前的indent,还是挺讨人喜欢的.
对于indent的参数,建议使用:

-bad -bap -bbb -bbo -nbc -bl -bli0 -bls -c33 -cd33 -ncdb -ncdw -nce -cli0 -cp33 -cs -d0 -nbfda -di2 -nfc1 -nfca -hnl -ip5 -l75 -lp -pcs -nprs -psl -saf -sai -saw -nsc -nsob -nss -i4 -ts4 -ut

这些参数可写入用户目录下的文件,作为运行indent的缺省参数：

echo “-bad -bap -bbb -bbo -nbc -bl -bli0 -bls -c33 -cd33 -ncdb -ncdw -nce -cli0 -cp33 -cs -d0 -nbfda -di2 -nfc1 -nfca -hnl -ip5 -l75 -lp -pcs -nprs -psl -saf -sai -saw -nsc -nsob -nss -i4 -ts4 -ut”
> ~/.indent.pro

indent参数详细说明：
使用的indent长参数                             值         含义
–blank-lines-after-declarations               bad   变量声明后加空行
–blank-lines-after-procedures                bap   函数结束后加空行
–blank-lines-before-block-comments   bbb   块注释前加空行
–break-before-boolean-operator           bbo   较长的行，在逻辑运算符前分行
–blank-lines-after-commas                    nbc   变量声明中，逗号分隔的变量不分行
–braces-after-if-line                                bl   “if”和”{“分做两行
–brace-indent 0                                       bli0   “{“不继续缩进
–braces-after-struct-decl-line              bls   定义结构，”struct”和”{“分行
–comment-indentationn                        c33   语句后注释开始于行33
–declaration-comment-columnn          cd33   变量声明后注释开始于行33
–comment-delimiters-on-blank-lines   ncdb   不将单行注释变为块注释
–cuddle-do-while                             ncdw   “do — while”的”while”和其前面的”}”另起一行
–cuddle-else                                     nce   “else”和其前面的”}”另起一行
–case-indentation 0                       cli0   switch中的case语句所进0个空格
–else-endif-columnn                     cp33   #else, #endif后面的注释开始于行33
–space-after-cast                          cs   在类型转换后面加空格
–line-comments-indentation n   d0   单行注释（不从1列开始的），不向左缩进
–break-function-decl-args          nbfda   关闭：函数的参数一个一行
–declaration-indentationn          di2   变量声明，变量开始于2行，即不必对齐
–format-first-column-comments   nfc1   不格式化起于第一行的注释
–format-all-comments              nfca   不开启全部格式化注释的开关
–honour-newlines             hnl   Prefer to break long lines at the position of newlines in the input.
–indent-leveln          i4   设置缩进多少字符，如果为tab的整数倍，用tab来缩进，否则用空格填充。
–parameter-indentationn   ip5   旧风格的函数定义中参数说明缩进5个空格
–line-length                                   75   l75   非注释行最长75
–continue-at-parentheses          lp   续行从上一行出现的括号开始
–space-after-procedure-calls    pcs   函数和”(“之间插入一个空格
–space-after-parentheses         nprs   在”（”后”）”前不插入空格
–procnames-start-lines             psl   将函数名和返回类型放在两行定义
–space-after-for                         saf   for后面有空格
–space-after-if                            sai   if后面有空格
–space-after-while                     saw   while后面有空格
–start-left-side-of-comments   nsc   不在生成的块注释中加*
–swallow-optional-blank-lines   nsob   不去掉可添加的空行
–space-special-semicolon            nss   一行的for或while语句，在”;”前不加空。
–tab-size                                      ts4   一个tab为4个空格（要能整除”-in”）
–use-tabs                                    ut   使用tab来缩进

对于不同编码风格,如GNU风格,KR风格和BSD风格,不同的使用者可能会需要做不同的参数配置.

一.内存泄漏的介绍：

• 内存泄漏以发生的方式来分类，内存泄漏可以分为4类：

• 1.常发性内存泄漏。发生内存泄漏的代码会被多次执行到，每次被执行的时候都会导致一块内存泄漏。
• 2.偶发性内存泄漏。发生内存泄漏的代码只有在某些特定环境或操作过程下才会发生。常发性和偶发性是相对的。对于特定的环境，偶发性的也许就变成了常发性的。所以测试环境和测试方法对检测内存泄漏至关重要。
• 3.一次性内存泄漏。发生内存泄漏的代码只会被执行一次，或者由于算法上的缺陷，导致总会有一块仅且一块内存发生泄漏。

二.C程序内存泄漏和其它内存常见错误及例子

• 1.malloc之后没有free引起的内存泄漏
• 2.指针访问越界
• ##############Explame1###########################
  • p = (char *)malloc(10);
    • p[24] = ’0′; free(p);
      #################################################

• 3.两次对同一个地址使用free() ##############Explame2###########################
  char *p = NULL;
  char *q = NULL;
  p = (char *)malloc( 2 );
  free(p);
  free(p); 可以检测出这一行
  free(p+2)这样写也可以检测出
  free(q); 不能检测出
  #################################################
• 4.让未初始化数据作为赋值量
• ##############Explame1###########################
  • int n,m;
    m = n;
    #################################################
• 5.将未初始化值作为判断条件 ##############Explame1###########################
  int n;
  if(n){
  n++;
  }
  #################################################
  6.memcpy引起的内存重叠 ##############Explame1###########################
  char szStr[10];
  memcpy(szStr,szStr+3,6);
  #################################################

• 7.栈溢出
  ##############Explame1###########################
  fun(){
  fun();
  }
  main(){
  fun();
  }
  #################################################
  8.new , delete , malloc free 搭配错误 ##############Explame1###########################
  char *p = (char *)malloc(2);
  delete p;
  #################################################

三.Linux下内存检测方法介绍

• 1.确定要检查的范围。
  • 确定要对哪些内存错误进行检测。基本上都是上面提到的内存错误。

  2.使用内存检测工具对程序进行检测

  • 目前我们使用了Linux下的开源工具Valgrind 进行内存泄漏和各种工具的检测，类似的工具，都是要求再程序在GCC编译时加入-g参数，然后可以动态分析程序的内存分配情况，和各种内存错误。使用一般得到得结果为。(1)错误类型(2)错误所在文件(3)错误所在行。

  3.深入源代码进行错误得分析和猜测。

  • 根据工具得到得错误提示深入源代码进行错误得分析。找到程序自身代码的最底一层调用。

四.Valgrind 工具介绍

        Valgrind是一个GPL的软件，用于Linux（For x86, amd64 and ppc32）程序的内存调试和代码剖析。你可以在它的环境中运行你的程序来监视内存的使用情况，比如C 语言中的malloc和free或者 C++中的new和 delete。使用Valgrind的工具包，你可以自动的检测许多内存管理和线程的bug，避免花费太多的时间在bug寻找上，使得你的程序更加稳固。

Valgrind的主要功能

Valgrind工具包包含多个工具，如Memcheck,Cachegrind,Helgrind, Callgrind，Massif。下面分别介绍个工具的作用：

Memcheck 工具主要检查下面的程序错误：

• 使用未初始化的内存 (Use of uninitialised memory)

• 使用已经释放了的内存 (Reading/writing memory after it has been free’d)

• 使用超过 malloc分配的内存空间(Reading/writing off the end of malloc’d blocks)

• 对堆栈的非法访问 (Reading/writing inappropriate areas on the stack)

• 申请的空间是否有释放 (Memory leaks – where pointers to malloc’d blocks are lost forever)

• malloc/free/new/delete申请和释放内存的匹配(Mismatched use of malloc/new/new [] vs free/delete/delete [])

• src和dst的重叠(Overlapping src and dst pointers in memcpy() and related functions)

Callgrind

Callgrind收集程序运行时的一些数据，函数调用关系等信息，还可以有选择地进行cache 模拟。在运行结束时，它会把分析数据写入一个文件。callgrind_annotate可以把这个文件的内容转化成可读的形式。

Cachegrind

它模拟 CPU中的一级缓存I1,D1和L2二级缓存，能够精确地指出程序中 cache的丢失和命中。如果需要，它还能够为我们提供cache丢失次数，内存引用次数，以及每行代码，每个函数，每个模块，整个程序产生的指令数。这对优化程序有很大的帮助。

Helgrind

它主要用来检查多线程程序中出现的竞争问题。Helgrind 寻找内存中被多个线程访问，而又没有一贯加锁的区域，这些区域往往是线程之间失去同步的地方，而且会导致难以发掘的错误。Helgrind实现了名为” Eraser” 的竞争检测算法，并做了进一步改进，减少了报告错误的次数。

Massif

堆栈分析器，它能测量程序在堆栈中使用了多少内存，告诉我们堆块，堆管理块和栈的大小。Massif能帮助我们减少内存的使用，在带有虚拟内存的现代系统中，它还能够加速我们程序的运行，减少程序停留在交换区中的几率。

Valgrind 安装

1、 到www.valgrind.org下载最新版 http://www.valgrind.org/downloads/current.html2、 解压安装包：tar –jxvf valgrind-3.2.3.tar.bz23、 解压后生成目录valgrind-3.2.34、 cd valgrind-3.2.35、 ./configure6、 Make;make install

Valgrind 使用

用法: valgrind [options] prog-and-args [options]: 常用选项，适用于所有Valgrind工具

1. -tool=<name> 最常用的选项。运行 valgrind中名为toolname的工具。默认memcheck。

2. h –help 显示帮助信息。

3. -version 显示valgrind内核的版本，每个工具都有各自的版本。

4. q –quiet 安静地运行，只打印错误信息。

5. v –verbose 更详细的信息, 增加错误数统计。

6. -trace-children=no|yes 跟踪子线程? [no]

7. -track-fds=no|yes 跟踪打开的文件描述？[no]

8. -time-stamp=no|yes 增加时间戳到LOG信息? [no]

9. -log-fd=<number> 输出LOG到描述符文件 [2=stderr]

10. -log-file=<file> 将输出的信息写入到filename.PID的文件里，PID是运行程序的进行ID

11. -log-file-exactly=<file> 输出LOG信息到 file

12. -log-file-qualifier=<VAR> 取得环境变量的值来做为输出信息的文件名。 [none]

13. -log-socket=ipaddr:port 输出LOG到socket ，ipaddr:port

LOG信息输出

1. -xml=yes 将信息以xml格式输出，只有memcheck可用

2. -num-callers=<number> show <number> callers in stack traces [12]

3. -error-limit=no|yes 如果太多错误，则停止显示新错误? [yes]

4. -error-exitcode=<number> 如果发现错误则返回错误代码 [0=disable]

5. -db-attach=no|yes 当出现错误，valgrind会自动启动调试器gdb。[no]

6. -db-command=<command> 启动调试器的命令行选项[gdb -nw %f %p]

适用于Memcheck工具的相关选项：

1. -leak-check=no|summary|full 要求对leak给出详细信息? [summary]

2. -leak-resolution=low|med|high how much bt merging in leak check [low]

3. -show-reachable=no|yes show reachable blocks in leak check? [no]

使用Valgrind

• 对被测程序的要求

1. 要求用GCC编译时使用-g选项
2. 例如对test.c程序进行编译：gcc -o test -g test.c

• 基本用法：

1. valgrind [option] exefile arg…
2. [option]:参数选项
3. exefile：可执行程序
4. arg…：程序参数

• 使用内存检测

1. option参数必须加上–leak-check=yes
2. 举例：以程序test为例
3. 检查test程序的内存错误：valgrind –leak-check=yes ./test

• 详细参数说明见valgrind在线帮助手册 http://www.valgrind.org/docs/manual/mc-manual.html

• Valgrind可以识别的错误及错误提示

thanks to http://blog.sina.com.cn/u/1195316944 : http://blog.sina.com.cn/s/blog_473f16d00100044w.html