把 vfs 实现好了
极尽简洁，然过犹不及(As simple as possible, but not simpler.)——爱因斯坦
这段时间的工作是把上次提到的 VFS 系统实现了。而写这篇 Blog 的促因是 twitter 上有同学想让我谈谈对 Linus 最近的一篇老生常谈的看法。哦，看似既然是语言之争。C 好，还是 C++ 好。但这次他平和了许多。Linus 惯有风格依旧，但少了些须三年前的争论 中的刻薄。
我想说，C 的三个特质(见引用文最后一段) 哪一点都不可忽略。Linus 这次强调的大约是第三点，也是 C++ 程序员们不屑一顾的一点。可对于多人协作构建的项目，这一点实在是太重要了。这并不是人人都聪明就能回避的问题。如果程序员们都足够睿智，反而更能意识到沟通之成本。其实即使是你一个人在做整个项目，从前的你和现在的你以及将来的你，同样有沟通（记忆）的成本。人不可能两次踏进同一条河流。
我的观点在于，如非必要，勿增概念。这是我这次翻新资源管理系统的初衷。在项目组内，这种大的修改是反对多过赞同的。我尚无能力像说服自己那样说服每个人。虽然我及其主张项目演化中的民主，但这一次稍显独断，实在是不得已。因为我觉得这是个不明显的重大缺陷。虽然老的设计它精巧，且可以很好的工作，但它不适合长期保留。
理想的大项目，应该是每个人专心做自己的一块东西，它涉及的外部部分用极少的文档或易于表达的概念定义清楚：无论是程序接口、对资源的占用、适用的范围等等。尤其是弱化 framework 这种联系方方面面的巨无霸。
说回这次实现的 VFS 模块。实现还是比较简单的。但是设计很困难。难点在于，虽无可避免的有一些 framework 的倾向（比原来的系统要弱化许多），但怎样让后面具体的文件系统跟这个小型 framework 交流最少。架子主要解决的是内存资源管理问题和用 cache 提升索引性能的问题。
我定义了两个内部数据结构，借用 linux 的 vfs 中的概念表达。一种叫 dentry 描述目录项，一种叫 inode 描述文件项。但没有暴露这两个数据结构的内部布局。用户扩充的时候，需要给出各一个额外的数据指针来扩展自己的结构。这种手法，我曾经描述过。实际应用的时候，没有定法。
所有函数都应该是可重入的，但暂不要求线程安全。以此实现文件系统的嵌套 mount 。起初，我认为实现一个 zipfs 会很容易。可以 mount 上通用的 zip 文件使用。实际实现时，发现无论是通用的 zlib 还是另一个使用执照稍微麻烦一点的 zziplib ，都不提供高效的 seek 接口。我花了一整个晚上研究 zip 的文件格式和解码算法。发现对于这种流式数据压缩，很难做到特别高效的 seek 算法。
利用 zlib 的底层 api ，我想了个办法来提高 zlib 中带的 minizip 库的 seek 效率（目前必须通过假读来实现），不过也不可能达到 O ( LogN ) 的水平。所以我放弃了这个打算。没有高效的 seek 接口，坏处在于嵌套的 mount zip 文件中被打包的 zip 文件性能会很差。当然，可以选择在 zip 被打包进 zip 时不压缩，这样稍微改造一下 minizip ，就能把 seek 提高到 O(1) 的水平。我权衡了一下，还是把此类需求留到以后自己设计一个新的包格式为佳。（采用分块压缩即可）
最终我实现了一个基本的 rootfs ，一个 memfs 用于在内存中创建文件和目录（主要用于创建出最初的 mount 点），一个 nativefs 用于把本地文件系统上的目录树以只读方式映射给引擎，一个 zipfs 实现开发期基本的打包方案。未来可能会增加一个可写的文件系统，用于保存一些本地设置。一个自定义的包方案。
同时在同事的协助上，把 engine 中老的资源操作的接口迁移到新系统上。
btw, 我还考察了一个修改过的 unrar 的库。不过由于繁杂的执照问题，暂时没有采纳。如果人力充足的话，日后倒可以找人来加上。
Comments
有支持seek的gzip： razf
Posted by: zhanxw | (17) September 1, 2010 01:33 PM
用lzo吧, 这个压缩库解压速度非常快, 可以和memcpy benchmark
Posted by: Siney | (16) July 19, 2010 07:51 PM
经常看你的博客，写得不错。
但有个疑问一直萦绕－－为什么你的开发如此自在？可以不断重复造轮子？没有开发进度的要求？
Posted by: hi | (15) July 7, 2010 10:56 AM
wow 的MPQ文件是如何实现的？
Posted by: lbaby | (14) June 26, 2010 09:22 AM
是否可把blog加上可回复回复的功能？
Posted by: lichking | (13) June 25, 2010 12:28 AM
期待你的可写vfs，
并期望你能分享你的经验。
Posted by: littlebug | (12) June 24, 2010 01:33 PM
文章很好啊.有些地方有待请教!www.input9.info
Posted by: 126bt | (11) June 21, 2010 08:26 AM
文章写得很好,只是有些地方不太明白!
Posted by: zes | (10) June 21, 2010 08:25 AM
我先声明，我没很认真看这个vfs，我只是想，干嘛不把所有的资源直接塞到BDB里面了事呢？
Posted by: 小x | (9) June 19, 2010 10:12 AM
是否可以用C++的关键特性，比如继承，重载等，但是不使用C++的库，尽量使用C来实现，这样的组合也许是个合适的选择。C++有时候感觉比较复杂。
Posted by: youngs | (8) June 18, 2010 04:01 PM
linus说道重载，我想起C宏里写MIN里也要考虑是否会重复求值，不知道这是否也算上下文相关。宏也可以undef后重define，如果把这个过程写在头文件里那么包含这种头文件也会导致宏的使用变成上下文相关的。甚至调用库函数也可能是上下文相关的，因为可能你不知道实际运行时调用的是哪个版本的库。
我觉得这些问题不是重载或宏所必然导致的问题，换句话说并非任何一次使用都一定会产生这些问题。所以也不应怪罪在这些语言特性上。
如果要怪罪重载的话，只能说它没有限制使用者，使得使用者写出的重载函数的调用既可以是含义非常明显直接的，也可以是非常晦涩的。不过反过来也可以看作一种优点，语言并不会轻易抹杀使用者的选择权，相对于某些语言强迫使用者使用GC来说，我更喜欢让我自己选择。
另外，“不想用GC就可以不用XXX语言”这种逻辑和“有选择”不一样，这就像我如果进了一家餐馆，我要么必须吃指定的菜要么就不能在这家吃，这样就无论如何都不存在“点菜”这种选择行为。如果库的API导致我必须选择特定的语言，那就会像旅行团指定了餐馆一样，不会存在任何有选择的余地了。
Posted by: sjinny | (7) June 14, 2010 11:05 AM
简单就是不要有特殊情况
Posted by: cc | (6) June 13, 2010 09:09 PM
我还是我的观点，在大项目中，C的“足够简洁”并不能本质上节省沟通和记忆成本。
本质的复杂性是项目本身引入的，C只不过是把复杂的东西移出了语言而已。C倒是足够简洁了，但在项目的层面上复杂性仍然存在且没有减少。C++等较为复杂的语言则是把项目的部分复杂性由语言承担，当然C++做的并不是很好就是了。
Posted by: sandy_zc_1 | (5) June 13, 2010 07:57 PM
"所有函数都应该是可重入的，但暂不要求线程安全。"可重入的函数线程不是安全的？
Posted by: Stabber | (4) June 13, 2010 06:18 PM
As simple as possible 还有后半句 but not simpler 。就是说不要因简化而去掉了某些本质的东西。
如果这里定义出来的 vfs 的作用是把一块以某种方式组织起来的数据，以统一的接口来组织和访问。那么数据来源就该允许是其自身。
这样的模块接口定义对外是最简，约束最小的。可以和别的部分充分隔离开。
Posted by: cloud | (3) June 13, 2010 04:36 PM
嵌套是个自然的产物，不是特别的需求。如果你把任何一个设备抽象成定义好的若干控制接口，那么嵌套不嵌套只是性能问题，而不是实现问题。
如果有性能问题，有如 zip 嵌套，那么我们不用即可。
如果实现不了，那说明前面的接口设计出了问题。或是说不够简单。很可能是加了一些特例，或是隐藏了一些未被定义出来却没能满足的条件。
Posted by: cloud | (2) June 13, 2010 04:27 PM
zip里面还要嵌套zip，这也能算As simple as possible么？明显是把事情往复杂方向搞。
Posted by: analyst | (1) June 13, 2010 04:04 PM