Fleurer.Lee

翻译：ssword
原文：http://www.iecc.com/gclist/GC-faq.html

这是GC邮件列表的FAQ草稿，欢迎评论、标注或贡献内容。它暂时分为三(?)部分，大约是一般问题，技巧及算法，语言接口和高级论题。以后内容要是多了，这些内容可以重新组织便于查阅。

我们也提供了这些内容的文本文件，即GC-algorithms.txt, GC-lang.txt, and GC-harder.txt。

这里一些内容的学术气可能要差些，而更偏重于传道（或者更确切地说，是在没技术成分有减少的前提下增加点传道的因素）。关于垃圾收集多好多好之类，言辞越简洁越好。

Common questions
常见问题

What is garbage collection?
什么是垃圾收集？
垃圾收集可以是语言运行时的一部分，也可以是个附加库。它们能够与编译器、硬件或操作系统打交道，自动检查出程序中不再使用的内存，并将其回收利用。这也称作“自动存储（内存）回收”。

Why is it good?
它好在哪？

手工内存管理既浪费程序员的生命，也容易引入错误。相当多的程序都难免于内存泄漏，使用了错误处理或线程的程序尤其如此。

未使用过垃圾收集的朋友可能难以察觉它的第二大好处，那就是不必纠结于内存管理的细节（“谁来回收这块内存”），从而简化了程序组件（子程序、库、模块、类）间的接口。

你可以在 Object-Orientation FAQ — 3.9) Why is Garbage Collection A Good Thing?了解更多内容

Is garbage collection slow?
垃圾收集会不会很慢？

并非如此，现代的垃圾收集器的速度几乎可与手工内存管理(malloc/free或new/delete)相媲美。垃圾收集可能不如特定程序中相应的allocator快，不过为保证手工allocator正常工作而添加的额外代码（如引用计数）往往会使得程序比垃圾收集更慢，共享资源的多线程程序中尤其如此。

正如开始所说，内存已经足够便宜，垃圾收集可以应用到非常大的堆上（比如1GB）。活动内存如果足够的大，暂停时间依然是个问题。不过对于现代的垃圾收集器而言，其暂停时间通常也就0.1秒，对人类的交互几乎可以不计。要是小块活动内存，暂停时间就更少了：0.01秒以下。

Can I use garbage collection with C or C++?
我可以在C\C++中使用垃圾收集吗？

应该可以。对于存在遗留代码的C和C++可能还差些，不过现代的垃圾收集器（测试良好，高效，无暂停）几乎已经支持了一切。了解更多请看GC, C, and C++ 。

Does garbage collection cause my program’s execution to pause?
垃圾收集会不会让我的程序暂停？

不必。有不一的算法允许垃圾收集并行化、增量化甚至“实时化”。比如C\C++下边就有增量式的垃圾收集。

Where can I get a C or C++ garbage collector?
怎样搞到C\C++的垃圾收集？

Boehm-Weiser collector
http://www.hpl.hp.com/personal/Hans_Boehm/gc/ or
ftp://parcftp.xerox.com/pub/gc/gc.html
Great Circle from Geodesic Systems or 800-360-8388 or http://www.geodesic.com
Kevin Warne or 800-707-7171

Folk myths
坊间传闻

• GC一定不如手工内存管理快
• GC一定会让程序暂停
• 手工内存管理就不暂停
• GC与C\C++水火不容

Folk truths
其实…

• 大部分动态创建的对象其实少有与其它对象的关联，通常其引用数就是1。
• 大部分对象的生存期都很短。
• 对象大小、生存期呈爆炸式分布，而不是正态分布。
• VM很重要
• 缓存很重要
• 不成熟的优化乃万恶之源。

Tradeoffs
权衡

• 严格式 vs. 保守式
• 移动/压缩 vs. 无移动
• 暂停 vs. 增量 vs. 并行
• 分代 vs. 无分代

GC, C, and C++

What do you mean, garbage collection and C?
你说什么，C语言的垃圾收集？

可以引入一个垃圾收集器自动管理内存，从而代替malloc和free的手工申请或释放。通常的做法是将malloc替换为垃圾收集器的allocator，而free则替换为一个空函数。比如X11就是如此。

也可以令free依然生效，不过垃圾收集器就弱化为一个防弹衣的存在，堵住潜在的内存泄漏。这一做法也是有了很多应用，并且工作良好。好处是方便程序员手工管理内存，而程序员顾不到的地方，就交给垃圾收集。这不一定比空free风格的快，不过可能让堆变得小点。

How is this possible?
如何做到的？

C兼容的垃圾收集可以知道指针在什么地方（例如”bss”,”data”和堆栈里面），保留在堆中的数据结构可以让它们很方便就能找出哪段数据是可能的指针。来个搜索遍历所有可以访问的指针，剩下没被访问的就是垃圾。

This doesn’t sound very portable. What if I need to port my code and there’s no garbage collector on the target platform?
这个听起来移植性好像不怎么样。我需要将代码移植到没有垃圾收集器的平台上该怎么办？

有些代码一定是平台相关的，但是大多操作系统都有足够的功能，所以C的垃圾收集其几乎可以在所有平台移植。一般而言，只要有垃圾收集的实现，移植性就不是问题。在Boehm-Weiser的移植还不多的时候，我曾经自己移植过两次，其时我对操作系统的底层接口还不甚熟悉。

Won’t this leave bugs in my program?
这不会给我程序引入bug吧？

这看你怎么想了。垃圾收集器可以解决程序员的很多问题，从而可以把精力放在其他地方，使得工作完成的更轻松。某种意义上讲，这跟浮点算法和虚拟内存的初衷是一致的。它们被发明出来都是为了解决些折腾程序员的乏味问题（如比例运算、换出页到硬盘）。没有FP和VM支持也可以写代码来实现相应的功能，不过只要有这功能可用，人们就不会自己写。一样的道理。

如果程序中用了垃圾收集风格的代码再扔掉垃圾收集器，内存泄漏的bug是肯定的。同样，如果一个程序用了FP（或VM）相关的代码，再卸掉浮点单元和MMU，bug也是一定的。

实际上，许多使用malloc和free的程序里都有内存泄漏，使用个垃圾收集器反而可以减少程序的bug。这可比手工跟踪内存再手工修复利索多了，要是跟踪发现内存泄漏出在三方库，还根本没办法修复。

Can’t a devious C programmer break the collector?
程序员可不可以把这收集器玩崩溃?

当然可以。不过大多数人应该更喜欢研究些正事，而不是整天想着把自己的工具玩坏掉。收集器需要正在内存空间中的指针，所以想玩坏就有办法。例如双向链表中的翻转指针技巧就不能用——这指针长得不像指针。如果程序把指针写到文件中，呆会再读出来，没准就崩了，因为这些指针指向的内存很可能已经被回收了。没大有程序会这么玩，所以对大多数程序而言，这不是问题。C中一般的（合法的）指针运算都是没问题的。

某技术团队在考虑使用GC时想到一个问题，那就是使用pointer mangling技巧可能会搞出“不透明”的指针。所谓pointer mangling，就是三方库中的指针与一固定的随机数异或下，这一来三方库中的数据只有按照特定的接口才可以访问。这个不兼容保守式GC，也不兼容Ansi C标准的严格编译…甚至会迷惑内存泄漏的跟踪器（跟保守式GC用的技术一样）。不过即便如此，它们依然是合法的程序。

Insert more questions here — send them to

What does a garbage collector do about destructors?
垃圾收集器如何对待析构函数？

析构函数就是对象被释放时候执行的代码，它的用途之一就是来手工回收内存，比如递归地回收对其它对象的引用。垃圾收集器里本没有析构函数的必要：如果一个对象是垃圾，它引用的所有对象就都是垃圾，自然会被收集到。

利用析构函数还可以做点其他事情。有两个应用比较典型：

与外部环境相关的对象的状态。比如文件相关的对象：当一个文件对象被回收时，垃圾收集器应该能保证能够刷新缓冲区、关闭文件，并将文件相关的资源返还给操作系统。

再就是程序需要保留一组在别处引用的对象。程序可能需要知道对象的功能，而不阻止它被收集。

解决这问题有很多方法：

有些系统是“built in”的垃圾收集，它就可以对外部引用的资源有所了解，处理起来也就心里有数
有不少垃圾收集系统有个“弱引用(weak pointer)”的概念，就是不被垃圾收集器认作引用的指针。如果一对象是个弱引用，那么就可以被GC收集。弱引用可以用来实现对象的list之类的数据结构。
再就是，java里可能会这样保护外部资源R：

class ClientR {
   CRWeak wr;
   // delegate all methods to wr;
   ClientR() {
     wr = new CRWeak(this);
   }
}
 
class CRWeak extends WeakReference {
  static ReferenceQueue rq = new ReferenceQueue();
  static {
         Thread th = new CRCleaner(rq);
         th.setDaemon(true);
         th.start();
  }
 
  CRWeak(Object x) {
     super(x, rq);
  }
  ExternalResource r;
  // delegated methods from ClientR
}
 
class CRCleaner extends Thread {
  ReferenceQueue rq;
  CRCleaner(ReferenceQueue rq) { this.rq = rq; }
  public void run() {
         while (true) {
           CRWeak x = (CRWeak) rq.remove();
           // Release x.r
         }
  }
}

当没有对象引用ClientR时候，这块内存就回收了，而对它的弱引用则移动到了各自的引用队列。清扫线程可以保证这些外部资源的回收。

许多GC系统都有“析构函数”的概念。垃圾收集器在回收一对象的时候，会执行该对象的一个函数来执行必要的清理操作。这会比较复杂，因为有些问题需要考虑：

• 对象是在什么时候才会被收集？它并不像看起来这么简单，这对一些资源吃紧的应用尤为棘手。
• 析构函数该在哪个线程、资源或者上下文下边执行？
• 对象的交叉引用该怎么办？
• 如果一个析构函数使得对象不再是垃圾，又该怎么办？

For more information

Contributors (so far)
贡献者（目前）

David Gadbois
Charles Fiterman
David Chase
Marc Shapiro
Kelvin Nilsen
Paul Haahr
Nick Barnes
Pekka P. Pirinen
GC FAQ table of contents
Techniques and algorithms
Language interfaces
Difficult topics
Silly stuff

作者：Gustavo Duarte
翻译：ssword
原文：http://duartes.org/gustavo/blog/post/how-the-kernel-manages-your-memory

我们已经对类型的虚拟地址空间布局有了一定了解，接下来我们进入内核，了解其内存管理机制。再拿gonzo的图示出来：

Linux内核使用进程描述符task_struct的实例来表示进程。task_struct中的mm字段指向内存描述符mm_struct，它储存了内存中各个段的起始位置（如上图）、进程中使用物理页的数量（rss是Resident Set Size的缩写）、虚拟地址区域的大小以及其他一点细节。在内存描述符中，我们还可以发现其两大心腹：虚拟内存区域和页表。Gonzo的内存区域表示起来如下：

每块虚拟内存区域（VMA）都是一段连续的虚拟地址，其间没有重叠。vm_area_struct的实例就是对一段内存区域的描述，其中包含了内存区域的起始地址、描述行为和访问控制的标志以及表示文件映射的vm_field字段，没有文件映射的VMA就是匿名的（anoymous）。除去内存映射段，如上的每个段（如堆、栈）都单独与一个VMA相关联。x86的机器大都如此组织内存，不过并非如此不可–VMA本身不关心自己位于哪个段。

对程序员而言，VMA在其内存描述符，既有mmap字段里顺序的一段链表，又有mm_rb字段的一棵红黑树。这棵红黑树使得内核得以快速按照给出的虚拟地址来找出相应的内存区域。像读取文件/proc/pid_of_process/maps的内容，内核就只是简单遍历这个VMA的链表再将其输出。Windows下的EPROCESS差不多就是task_struct和mm_struct的混合体，而其相对于VMA的等价物就是虚拟地址描述符（Virtual Address Descriptor），简称VAD，储存在一颗AVL树中。你说Windows和Linux最有趣的东西是啥？就是那点小差异。

4GB的虚拟地址空间被划分为页。32位的x86处理器允许将页划分为三种大小：4kb、2mb或4mb。Linux和Windows的用户虚拟地址空间的页大小都是4kb。地址中0-4085字节是第一页，4096-8191是第二页，以此类推。VMA的大小必为页大小的整数倍。如下就是按4kb分页的3gb用户空间：

处理器依据页表将虚拟地址转换为物理地址，不同进程的页表各不相同。因此在进程切换时，用户空间的页表也随之切换。Linux将指向进程页表的指针储存于内存描述符的pgd字段中。每个虚页都与一个页表入口（PTE）相关联，在一般的x86分页机制下，它就是一个4字节长的记录：

Linux有专门的函数来读写PTE的属性标志。P位表示次页表是否位于物理内存。若清零，读取这块内存就会触发一个页异常。牢记，就算该位清零，内核依然可以修改其他属性域。R/W表示读/写(read/write)；若清零，该页只读。U/S表示用户/超级用户(user/supervisor)，若清零，该页只允许内核访问。有了这些标志，才可以实现我们前面所见的只读内存和内核空间保护。

D位与A位分别表示dirty和accessed。若一个页曾被写过，它就被标记为dirty；若曾有过读或写，它就会被标记为accessed。这两个标志都挺难搞：进程只管设置它们，清零却只允许内核来做。PTE保存与此页相关联的起始地址，以4kb对齐。这个貌似简单的属性域有一点不足，那就是限制了物理内存最大只能是4GB。物理地址扩展相关的PTE属性域改天再讲。

虚拟页是内存保护的基本单元，其中的所有字节共享同一U/S和R/W标志。不同的虚拟页可能映射自同一物理页，但其保护标志并不一定相同。注意下，PTE中并没有包含执行权的标志。这带来的后果就是，早期的x86系列CPU可能将堆栈段上的代码执行，因而易于遭到堆栈缓冲区溢出的攻击（如今使用return-to-libc或其他技巧，依然可以对堆栈中不可执行的代码搞溢出）。更深一层，PTE中执行权限标志的缺失使得VMA中的保护标志不一定能够应用到硬件的保护机制。内核已尽其全力，然而体系结构的限制尤在。

虚拟内存也不是什么都存。它只是将一个程序的地址空间映射到实在的物理内存，即物理地址空间。虽然在某种意义上有些内存操作也需要经过总线，但我们在此大可忽略之，从而将物理地址看作是从0开头，以字节为单位递增的一段地址。内核将物理地址空间划分为n个页框。处理器对页框的存在并不关心，不过对内核而言页框至关重要，因为页框就是管理物理内存的基本单元。32位的Linux和Windows都是用4kb的页框，如下是个2GB内存机器的例子：

Linux的每个页框都带有一个描述符以及n个属性标志。这些描述符管理了电脑的所有物理内存，使得每个页框的状态都可以明确。物理内存通过伙伴内存分配机制进行管理，对伙伴系统而言，一个页框若可以分配，那它就是free的。分配来的页框可以是匿名，以储存程序数据；也可以是页缓存，以包含来自文件或设备的数据。也有其他类型的页框，在这里先略过就是。Windows下有个类似的页框号（Page Frame Number,PFN）数据库来跟踪物理内存。

现在把虚拟内存区域、页表、页框放到一起，看看其整体是如何工作。如下是个用户堆的例子：

蓝色方形表示了VMA中包含的页，箭头表示页经页表与页框形成的映射关系。某些虚拟页上并没有箭头，因为它们PTE中Present标志都是清零的。这些页可能是从未使用，也可能是已被换出。不过无论怎样，访问这些页都会导致页异常，即便这些页在VMA中也是如此。VMA和页表不能一一对应，可能难以理解，不过确实是经常发生的事情。

VMA就像是程序与内核间的通信员。你先下个什么请求（内存分配，文件映射等等），内核说“行”，它就创建或更新一个合适的VMA。但它并不会马上将其一步到位，而是等到有了页异常再来。内核是个懒惰且狡诈的混蛋，这就是虚拟内存的基本作风。熟悉与否，这一思想随处可见。VMA保存上面分配来的内容，而PTE决定其具体的行为。这两个数据结构共同管理着程序的内存，遇到页异常、释放内存、换页等操作的时候，都有它俩的份。看个这个内存分配的简单例子：

程序使用brk()系统调用来申请更多内存，内核就简单更新下堆的VMA，说“行了”。不过这时并没有页框真正分配出来，页也不在物理内存中。程序一旦要访问这些页，处理器就会触发页异常，并执行do_page_fault()。它使用find_vma()找出异常发生地址对应的VMA，若找到，检查VMA的权限标志以防恶意访问（读或写）；如果没有合适的VMA，就不再管这个内存访问而交给处理器触发一个段异常。

找到相应VMA之后，内核必须检查PTE的内容以及VMA的类型，以处理这个异常。在我们的例子里，PTE显示出这个页不在物理内存中。这里我们PTE为空（全为零），Linux中就表示这段虚拟页从未被映射过。这是个匿名的VMA，因此只能用do_anoymous_page()处理。它会分配一个页框，修改PTE将那发生异常的虚拟页映射到新分配的页框上。

也有例外。例如页已经换出，那它PTE中Present标志就是0，里面则保存了页内容在硬盘上的地址，它使用do_swap_page()读取硬盘并将其装载置页框。

我们内核内存管理之旅大约已行至一半。在下篇post里，我们会讨论上文件及性能的因素，以了解内存管理的整体。

囧，译到四分之三的时候发现已经有人译过了：http://blog.csdn.net/drshenlei/archive/2009/07/15/4350928.aspx