卡曼妮耶美肯男友:V8系列——内存管理(2)

可见在对象分配失败时，会尝试以两种不同方法回收内存，并重复尝试分配对象空间（最多三次）。

2、 回收算法

(2.1)scavenge，用于NewSpace，使用Cheney’s Alogorithm，大致思想为：

a) Heap被平分为两个semispace，任何时候只有一个semispace处于使用状态；

b) 垃圾回收时把处于使用状态的semispace(from_space_)中包含的live ojbects拷贝到另一个semispace(to_space_)，具体逻辑为：

I) 检查stack上所有对象引用；如果被引用的对象(live objects)还没有被拷贝到to_space_，则在to_space_建立一个完全相同的新对象，然后把所有引用到该原对象指向新的对象，并用forwarding pointer替代该对象原来在from_space_位置；如果被引用的对象(live objects)已经被拷贝到to_space_，则简单地更新引用，通过forwarding pointer指向新的to_space_中的新对象。

II) 检查to_space_上所有新建对象是否有引用其它对象，操作同i。

算法流程（入口Heap::Scavenge）：

a) 为了避免newspace由于空间过小儿引起频繁地scavenge，于是在每次scavenge之前检查次数，如果超过限制次数（初始为8）且newspace能满足空间翻倍（初始为256KB，最大为2MB），则double空间以及该次数限制。这里的策略调整可以根据实际优化；

遗留问题：在double空间时，需要使用事务机制来确保to_space成功翻倍扩展而from_space失败的情况。 To review the latest version。

b) 两个semispace的信息互换，SemiSpace tmp = from_space_; from_space_ = to_space_; to_space_ = tmp; 即把正在使用的to_space_变成from_space_，而原来的from_space_变成空的to_space_；

c) 把from_space_中alive的对象逐个拷贝至to_space_，最先从拷贝root对象开始（包括strong_root_list、struct_map、symbol、bootstrapper、top、debug、compilation cache、handlescope、builtins、globalhandles、threadmanager等）；拷贝完毕后再检查新拷贝对象是否存在引用其它对象；最后再对global handle list中处于weak或pengding状态的对象进行拷贝。

由于to_space_最高限制只有2MB，所以一些生命周期长的对象，需要在scavenge中被置换(promoted)到OldSpace，为了跟踪这些promoted对象对其它对象的引用，利用to_space_的尾端开始反向记录promotd对象的新地址；该做法不会造成空间不足的原因在于：每个HeapObject最少为一个指针大小。

举例，假设情景如下：

对象被置换(promoted)到OldSpace的时机：

(i) 当前处于使用状态的to_space可用空间少于75%时；

(ii) 当对象地址小于age_mark时，to_space的age_mark在每次scavenge后被置成新的可用起始地址，即如果对象在上一次scavenge中survive，那么在下次的scavenge中将会被置换到OldSpace（根据对象类型拷贝至Old_Pointer_Space or Old_Data_Space，见Heap::TargetSpaceId，Heap numbers and sequential strings are promoted to old data space, all other object types are promoted to old pointer space）;

(iii) 如果OldSpace分配对象空间失败，那么对象依旧分配在NewSpace(to_space)。

(2.2)Mark-Compact，用于所有space的内存垃圾回收

(2.2.1) Definition：The mark-and-compact algorithm consists of two phases: In the first phase, it finds and marks all live objects. The first phase is called the mark phase. In the second phase, the garbage collection algorithm compacts the heap by moving all the live objects into contiguous memory locations. The second phase is called the compaction phase. The algorithm can be expressed as follows:       for each root variable r {mark (r);} compact ();

由于Mark-Compact涉及对象的内存拷贝，比较耗时；于是再把该算法划分为Mark-Sweep和Mark-Compact，当OldSpaces（CodeSpace、Old_Data_Space、Old_Pointer_Space）总的利用率低于2/3时，才会使用Mark-Compact。

(2.2.2) 流程（入口Heap::MarkCompact）

a) MarkCompactCollector::Prepare，一些准备工作，决定使用Mark-Sweep(后续简写为MS)或Mark-Compact(后续简写为MC)，并清除各个PagedSpace的free_list、一些数据记录，这些信息在后续流程中会重建，具体见OldSpace&PagedSpace的PrepareForMarkCompact方法；

b) Heap:: MarkCompactPrologue，预处理工作，①清CompliationCache，避免cached的编译代码存在时间过长；目前是全部删除省事，但可以考虑其它的清理策略，例如LRU算法；②选择MC时，通知stack上所有frames的对应线程，设置标记位（暂停执行？）；MS不会对live objects处理，内存地址不变，所以不需线程调度；

c) MarkCompactCollector::CollectGarbage，实际内存回收，大致工作流程如下：

d) Heap:: MarkCompactEpilogue，线程标记位处理，与b)对应；

e) Heap::shrink，PagedSpace的内存空闲页回收，

具体代码如下：

(2.3) 两种算法的结合

       涉及内存结构的设计思想，NewSpace是最常用的Heap空间，所以内存垃圾回收需要快速，使用Scavenge需要JS引擎停止执行~2ms；而OldSpace是生命时间较长的对象所在地，所以内存垃圾回收速度没那么快，一般是Mark-Sweep（~50ms），如果使用到Mark-Compace，速度会更慢，约耗时100ms，估算数据来自

http://dl.google.com/io/2009/pres/W_1230_V8BuildingaHighPerformanceJavaScriptEngine.pdf。

       Heap::SelectGarbageCollector在不同情况下对这两种算法进行选择：

在一个特殊场景下内存回收会同时使用到该两种算法：

A) 请求在NewSpace分配内存；

B) 选择使用Mark-Sweep，其中NewSpace中的废弃对象只是被标志，没有被回收；

C) 再次使用Scavenge对NewSpace进行对象回收。

关于内存管理的可用资料：

http://www.ednasia.com/article-182-handlingmemoryfragmentation-Asia.html 内存碎片概述

http://www.ibm.com/developerworks/cn/linux/l-memory   内存管理内幕

http://www.memorymanagement.org/

http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbibG.html   论文

http://g.oswego.edu/   Doug Lea's malloc

Dynamic Storage：Allocation A Survey and Critical Review.pdf  
http://www.cs.northwestern.edu/~pdinda/ics-s05/doc/dsa.pdf

个人认为内存管理的要点：
1、减少内存碎片的产生，涉及分配算法和回收合并算法
2、分配速度不比标准接口慢，涉及内存块组织结构，如何快速定位合适的块
3、多线程支持
4、辅助信息结构尽可能简单，避免内存的占用
5、使用状况的记录（调试信息）