Dalvik Heap

Dalvik 的堆空间分为 Zygote Heap 和 Active Heap

Android 系统的第一个 Dalvik 虚拟机是由 Zygote 进程创建的。应用程序进程是由 Zygote 进程 fork 出来的。也就是说应用程序进程使用了一种 写时拷贝技术（COW）来复制了 Zygote 进程的地址空间。这意味着一开始的时候，应用程序进程和 Zygote 进程共享了同一个用来分配对象的堆。然而，当 Zygote 进程或者应用程序进程对该堆进行写操作时，内核就会执行真正的拷贝操作，使得 Zygote 进程和应用程序进程分别拥有自己的一份拷贝。

拷贝是一件费时费力的事情。因此，为了尽量地避免拷贝，Dalvik 虚拟机将自己的堆划分为两部分。事实上，Dalvik 虚拟机的堆最初是只有一个的。也就是 Zygote 进程在启动过程中创建 Dalvik 虚拟机的时候，只有一个堆。但是当 Zygote 进程在 fork 第一个应用程序进程之前，会将已经使用了的那部分堆内存划分为一部分，还没有使用的堆内存划分为另外一部分。前者就称为 Zygote 堆，后者就称为 Active 堆。以后无论是 Zygote 进程，还是应用程序进程，当它们需要分配对象的时候，都在 Active 堆 上进行。这样就可以使得 Zygote 堆 尽可能少地被执行写操作，因而就可以减少执行写时拷贝的操作。在 Zygote 堆 里面分配的对象其实主要就是 Zygote 进程在启动过程中预加载的类、资源和对象了。这意味着这些预加载的类、资源和对象可以在 Zygote 进程和应用程序进程中做到长期共享。这样既能减少拷贝操作，还能减少对内存的需求。

堆的一些重要参数

堆 起始大小 指定了 Davlik 虚拟机在启动的时候向系统申请的物理内存的大小。后面再根据需要逐渐向系统申请更多的物理内存，直到达到 最大值 为止。这是一种按需要分配策略，可以避免内存浪费，厂商会通过 dalvik.vm.heapstartsize 和 dalvik.vm.heapsize 这两个属性将它们设置为合适设备的值的

注意，虽然堆使用的 物理内存 是按需要分配的，但是它使用的 虚拟内存 的总大小却是需要在 Dalvik 启动的时候就确定的。这个虚拟内存的大小就等于堆的最大值

想象一下，如果不这样做的话，会出现什么情况。假设开始时创建的虚拟内存小于堆的最大值，由于实际情况是允许虚拟内存达到堆的最大值的，因此当开始时创建的虚拟内存无法满足需求时，那么就需要重新创建另外一块更大的虚拟内存。这样就需要将之前的虚拟内存的内容拷贝到新创建的更大的虚拟内存去，并且还要相应地修改各种辅助数据结构。这样太麻烦了，而且效率也太低了。因此就在一开始的时候，就创建一块与堆的最大值相等的虚拟内存

但是 Dalvik 虚拟机又希望能够动态地调整堆的可用最大值，于是就出现了一个称为 增长上限 的值，我们可以认为它是堆大小的 软限制，而前面所描述的最大值是堆大小的 硬限制。它主要是用来限制 Active Heap 无节制地增长到最大值的，而是要根据预先设定的 堆目标利用率 来控制 Active Heap 有节奏地增长到最大值。这样可以更有效地使用堆内存。想象一下，如果我们一开始 Active Heap 的大小设置为最大值，那么就很有可能造成已分配的内存分布在一个很大的范围。这样随着 Dalvik 虚拟机不断地运行，Active Heap 的内存碎片就会越来越来重。相反，如果我们施加一个 Soft Limit，那可以尽量地控制已分配的内存都位于较紧凑的范围内，可以有效地减少碎片

后三个用来确保每次 GC 之后，堆已用内存和空闲内存有一个合适的比例，这样可以尽量地减少 GC 的次数。举个例子说，堆的利用率为 U，最小空闲值为 MinFree 字节，最大空闲值为 MaxFree 字节。假设在某一次 GC 之后，存活对象占用内存的大小为 LiveSize。那么这时候堆的理想大小应该为 (LiveSize / U)，且 (LiveSize + MinFree) <= (LiveSize / U) <= (LiveSize + MaxFree)

4 Type Of GC

Davlik 虚拟机定义了四种类型的 GC

/* Not enough space for an "ordinary" Object to be allocated. */
/* 在堆上分配对象时内存不足 */
extern const GcSpec *GC_FOR_MALLOC;

/* Automatic GC triggered by exceeding a heap occupancy threshold. */
/* 在已分配内存达到一定量之后触发 */
extern const GcSpec *GC_CONCURRENT;

/* Explicit GC via Runtime.gc(), VMRuntime.gc(), or SIGUSR1. */
/* 应用程序调用 System.gc、VMRuntime.gc接口或者收到 SIGUSR1 信号时触发 */
extern const GcSpec *GC_EXPLICIT;

/* Final attempt to reclaim memory before throwing an OOM. */
/* 在准备抛 OOM 异常之前进行的最后努力而触发的 GC */
extern const GcSpec *GC_BEFORE_OOM;

每种 GC 通过成员属性控制 GC 细节

struct GcSpec {
  /* If true, only the application heap is threatened. */
  /* true - 仅仅回收 Active Heap，false - 同时回收 Active Heap 和 Zygote Heap */
  bool isPartial;
  /* If true, the trace is run concurrently with the mutator. */
  /* true - 执行并行 GC，false - 执行非并行 GC */
  bool isConcurrent;
  /* Toggles for the soft reference clearing policy. */
  /* true - 不回收软引用，false - 回收软引用引 */
  bool doPreserve;
  /* A name for this garbage collection mode. */
  const char *reason;
};

GC_FOR_MALLOC、GC_CONCURRENT 和 GC_BEFORE_OOM 三种类型的 GC 都是在分配对象的过程触发的：

1. Dalvik 虚拟机在堆上分配对象的时候，如果分配失败会首先尝试 GC_FOR_MALLOC
2. GC 后再次进行对象的分配，如果失败这时候就得考虑先将堆的当前大小设置为 Dalvik 虚拟机启动时指定的堆最大值，再进行内存分配了（不应该是逐步增长？）
3. 如果上一步内存分配还是失败，这时候就得出狠招 GC_BEFORE_OOM 将 软引用 也回收掉
4. 这是最后一次努力了，如果还是分配失败就抛出 OOM
5. 成功地在堆上分配到一个对象之后，就会检查 Active Heap 当前已经分配的内存，如果大于阀值就会唤醒 GC 线程进行 GC_CONCURRENT。这个阀值是一个比指定的 堆最小空闲内存 小 128K 的数值，也就是说当堆的 空闲内不足 时就会触发 GC_CONCURRENT

Mark-Sweep（标记-清理 GC 算法）

顾名思义，Mark-Sweep （标记-回收）算法就是分为 Mark 和 Sweep两个阶段进行垃圾回收：

1. Mark 阶段从 GC ROOT开始递归地标记出当前所有被引用的对象
2. Sweep 阶段负责回收那些没有被引用的对象

挂起其他线程

函数 lockThreadSuspend 尝试获取 gDvm._threadSuspendLock 锁。如果获取失败，就表明有其它线程也正在请求挂起 Dalvik 虚拟机中的线程，包括当前线程。每一个 Dalvik 虚拟机线程都有一个 Suspend Count 计数，每当它们都挂起的时候，对应的 Suspend Count 计数就会加 1，而当被唤醒时，对应的 Suspend Count 计数就会减 1。在获取 gDvm._threadSuspendLock 锁失败的情况下，当前线程按照一定的时间间隔检查自己的 Suspend Count，直到自己的 Suspend Count 等于 0，并且能成功获取 gDvm._threadSuspendLock 锁为止。这样就可以保证每一个挂起 Dalvik 虚拟机线程的请求都能够得到顺序执行。

从函数 lockThreadSuspend 返回之后，就表明当前线程可以执行挂起其它线程的操作了。它首先要做的第一件事情是遍历 Dalvik 虚拟机线程列表，并且调用函数 dvmAddToSuspendCounts 将列表里面的每一个线程对应的 Suspend Count 都增加1，但是除了当前线程之外。注意，在增加被挂起线程的 Suspend Count 计数之前，必须要获取 gDvm.threadSuspendCountLock 锁。这个锁的获取和释放可以通过函数 lockThreadSuspendCount 和 unlockThreadSuspendCount 完成

将被挂起线程的 Suspend Count 计数都增加 1 之后，接下来就是等待被挂起线程自愿将自己挂起来了。这是通过函数 waitForThreadSuspend 来实现。当一个线程自愿将自己挂起来的时候，会将自己的状态设置为非运行状态（THREAD_RUNNING），这样函数 waitForThreadSuspend 通过不断地检查一个线程的状态是否处于非运行状态就可以知道它是否已经挂起来了

那么，一个线程在什么情况才会自愿将自己挂起来呢？一个线程在执行的过程中，会在合适的时候检查自己的 Suspend Count 计数。一旦该计数值不等于 0，那么它就知道有线程请求挂起自己，因此它就会很配合地将自己的状态设置为非运行的，并且将自己挂起来。例如，当一个线程通过解释器执行代码时，就会周期性地检查自己的 Suspend Count 是否等于 0。这里说的周期性，实际上就是碰到 IF 指令、GOTO 指令、SWITCH 指令、RETURN 指令和 THROW 指令等时。

Heap Bitmap

堆的起始地址为 base，大小为 maxSize，由此我们就知道在堆上创建的对象的地址范围为 [base, maxSize)。 但是通过 C 库提供的 mspace_malloc 在堆分配内存时，得到的内存地址是以 8 bits 对齐的。这意味着我们只需要 (maxSize / 8) bits 来描述堆对象。结构体 HeapBitmap 的成员变量 bits 是一个类型为 unsigned long 的数组，也就是说数组中的每一个元素都可以描述 sizeof(unsigned long) 个对象的存活。在 32 位设备上，一个 unsigned long 占用 32 bits，这意味着需要一个大小为 (maxSize / 8 / 32) 的 unsigned long 数组来描述堆对象的存活。如果换成字节数来描述的话，就是说我们需要一块大小为 (maxSize / 8 / 32) × 4 的内存块来描述一个大小为 maxSize 的堆对象。

Live Bitmap 用来标记上一次 GC 时被引用的对象（也就是没有被回收的对象），Mark Bitmap 用来标记当前 GC Mark 阶段发现的被引用对象，那么在 Live Bitmap 标记为 1，但是在 Mark Bitmap 中标记为 0 的即为需要回收的对象