js引擎v8源码分析之MemoryAllocator（基于v8 0.1.5）

class MemoryAllocator : public AllStatic {
 public:

  static bool Setup(int max_capacity);

  static void TearDown();

  static void* ReserveInitialChunk(const size_t requested);

  static Page* CommitPages(Address start, size_t size, PagedSpace* owner, int* num_pages);

  static bool CommitBlock(Address start, size_t size);

  static Page* AllocatePages(int requested_pages, int* allocated_pages,
                             PagedSpace* owner);
  static Page* FreePages(Page* p);

  static void* AllocateRawMemory(const size_t requested, size_t* allocated);
  static void FreeRawMemory(void* buf, size_t length);

  static int Available() { return capacity_ < size_ ? 0 : capacity_ - size_; }

  static inline void SetNextPage(Page* prev, Page* next);

  static inline Page* GetNextPage(Page* p);

  static inline bool IsPageInSpace(Page* p, PagedSpace* space);

  static inline PagedSpace* PageOwner(Page* page);
  static Page* FindFirstPageInSameChunk(Page* p);
  static Page* FindLastPageInSameChunk(Page* p);

  static const int kMaxNofChunks = 1 << Page::kPageSizeBits;
  static const int kPagesPerChunk = 64;
  static const int kChunkSize = kPagesPerChunk * Page::kPageSize;

 private:
  static int capacity_;
  static int size_;
  static VirtualMemory* initial_chunk_;

  class ChunkInfo BASE_EMBEDDED {
   public:
    ChunkInfo() : address_(NULL), size_(0), owner_(NULL) {}
    void init(Address a, size_t s, PagedSpace* o) {
      address_ = a;
      size_ = s;
      owner_ = o;
    }
    Address address() { return address_; }
    size_t size() { return size_; }
    PagedSpace* owner() { return owner_; }

   private:
    Address address_;
    size_t size_;
    PagedSpace* owner_;
  };

  static List<ChunkInfo> chunks_;
  static List<int> free_chunk_ids_;
  static int max_nof_chunks_;
  static int top_;

  static void Push(int free_chunk_id);
  static int Pop();
  static bool OutOfChunkIds() { return top_ == 0; }

  static void DeleteChunk(int chunk_id);

  static inline bool IsValidChunkId(int chunk_id);

  static inline bool IsValidChunk(int chunk_id);

  static inline int GetChunkId(Page* p);

  static Page* InitializePagesInChunk(int chunk_id, int pages_in_chunk, PagedSpace* owner);
};

int MemoryAllocator::capacity_   = 0;
int MemoryAllocator::size_       = 0;

VirtualMemory* MemoryAllocator::initial_chunk_ = NULL;

// 270 is an estimate based on the static default heap size of a pair of 256K
// semispaces and a 64M old generation.
// list的元素个数
const int kEstimatedNumberOfChunks = 270;
List<MemoryAllocator::ChunkInfo> MemoryAllocator::chunks_(kEstimatedNumberOfChunks);
List<int> MemoryAllocator::free_chunk_ids_(kEstimatedNumberOfChunks);
int MemoryAllocator::max_nof_chunks_ = 0;
int MemoryAllocator::top_ = 0;

// chunnkId管理
void MemoryAllocator::Push(int free_chunk_id) {
  ASSERT(max_nof_chunks_ > 0);
  ASSERT(top_ < max_nof_chunks_);
  free_chunk_ids_[top_++] = free_chunk_id;
}


int MemoryAllocator::Pop() {
  ASSERT(top_ > 0);
  return free_chunk_ids_[--top_];
}

// 初始化属性
bool MemoryAllocator::Setup(int capacity) {
  // 页的整数倍
  capacity_ = RoundUp(capacity, Page::kPageSize);

  // 最大的chunk数,
  max_nof_chunks_ = (capacity_ / (kChunkSize - Page::kPageSize)) + 4;
  if (max_nof_chunks_ > kMaxNofChunks) return false;

  size_ = 0;
  ChunkInfo info;  // uninitialized element.
  // 初始化chunks列表和id,max_nof_chunks_大于list的长度的话list会自动扩容,ChunkId大的在后面，小的id先被Pop出来使用
  for (int i = max_nof_chunks_ - 1; i >= 0; i--) {
    chunks_.Add(info);
    free_chunk_ids_.Add(i);
  }
  top_ = max_nof_chunks_;
  return true;
}


void MemoryAllocator::TearDown() {
  // chunk非空则释放对应的内存
  for (int i = 0; i < max_nof_chunks_; i++) {
    if (chunks_[i].address() != NULL) DeleteChunk(i);
  }
  // 清空list
  chunks_.Clear();
  free_chunk_ids_.Clear();
  // 释放initial_chunk_对应的内存
  if (initial_chunk_ != NULL) {
    LOG(DeleteEvent("InitialChunk", initial_chunk_->address()));
    delete initial_chunk_;
    initial_chunk_ = NULL;
  }

  ASSERT(top_ == max_nof_chunks_);  // all chunks are free
  // 重置属性
  top_ = 0;
  capacity_ = 0;
  size_ = 0;
  max_nof_chunks_ = 0;
}


// 分配虚拟内存
void* MemoryAllocator::AllocateRawMemory(const size_t requested,
                                         size_t* allocated) {
  // 当前大小 + 请求大小不能大于最大容量
  if (size_ + static_cast<int>(requested) > capacity_) return NULL;
  // 请求分配的大小和实际分配的大小，成功的话返回首地址
  void* mem = OS::Allocate(requested, allocated);
  // 实际分配的大小
  int alloced = *allocated;
  // 记录当前已经分配的内存大小
  size_ += alloced;
  Counters::memory_allocated.Increment(alloced);
  return mem;
}

// 释放虚拟内容
void MemoryAllocator::FreeRawMemory(void* mem, size_t length) {
  OS::Free(mem, length);
  Counters::memory_allocated.Decrement(length);
  size_ -= length;
  ASSERT(size_ >= 0);
}

// v8初始化的时候分配的堆内存
void* MemoryAllocator::ReserveInitialChunk(const size_t requested) {
  ASSERT(initial_chunk_ == NULL);
  // 新建一个VM对象，分配size的虚拟内存，记录在VM对象
  initial_chunk_ = new VirtualMemory(requested);
  CHECK(initial_chunk_ != NULL);
  //是否已经分配了虚拟地址
  if (!initial_chunk_->IsReserved()) {
    // 失败了，释放VM对象
    delete initial_chunk_;
    initial_chunk_ = NULL;
    return NULL;
  }

  // We are sure that we have mapped a block of requested addresses.
  ASSERT(initial_chunk_->size() == requested);
  LOG(NewEvent("InitialChunk", initial_chunk_->address(), requested));
  size_ += requested;
  // 返回分配内存的首地址
  return initial_chunk_->address();
}

// 算出有效的大小，在start到start + size中有效的内存大小，等于页数*每页大小
static int PagesInChunk(Address start, size_t size) {
  return (RoundDown(start + size, Page::kPageSize)
          - RoundUp(start, Page::kPageSize)) >> Page::kPageSizeBits;
}

// 之前分配的内存不够用，再分配
Page* MemoryAllocator::AllocatePages(int requested_pages, int* allocated_pages,
                                     PagedSpace* owner) {
  if (requested_pages <= 0) return Page::FromAddress(NULL);
  // 页数 * 每页大小
  size_t chunk_size = requested_pages * Page::kPageSize;

  // 空间不够，只能申请小于请求页数的内存了
  if (size_ + static_cast<int>(chunk_size) > capacity_) {
    // Request as many pages as we can.
    // 还能申请的字节数
    chunk_size = capacity_ - size_;
    // 还能申请多少页
    requested_pages = chunk_size >> Page::kPageSizeBits;
    // 不够一页了，直接返回申请失败
    if (requested_pages <= 0) return Page::FromAddress(NULL);
  }
  // 分配虚拟内存,chunk_size是申请分配的大小和实际分配的大小
  void* chunk = AllocateRawMemory(chunk_size, &chunk_size);
  if (chunk == NULL) return Page::FromAddress(NULL);
  LOG(NewEvent("PagedChunk", chunk, chunk_size));
  // 算出实际分配的页数
  *allocated_pages = PagesInChunk(static_cast<Address>(chunk), chunk_size);
  if (*allocated_pages == 0) {
    FreeRawMemory(chunk, chunk_size);
    LOG(DeleteEvent("PagedChunk", chunk));
    return Page::FromAddress(NULL);
  }
  // 取出一个id
  int chunk_id = Pop();
  // 记录在ChunkInfo中
  chunks_[chunk_id].init(static_cast<Address>(chunk), chunk_size, owner);

  return InitializePagesInChunk(chunk_id, *allocated_pages, owner);
}

// 保存和管理虚拟地址start到start+size的空间，
Page* MemoryAllocator::CommitPages(Address start, size_t size,
                                   PagedSpace* owner, int* num_pages) {
  ASSERT(start != NULL);
  // chunk中的页数
  *num_pages = PagesInChunk(start, size);
  ASSERT(*num_pages > 0);
  ASSERT(initial_chunk_ != NULL);
  ASSERT(initial_chunk_->address() <= start);
  ASSERT(start + size <= reinterpret_cast<Address>(initial_chunk_->address())
                             + initial_chunk_->size());
  // commit，修改内存的属性，使得可用，见platform-linux.ccd的mmap
  if (!initial_chunk_->Commit(start, size)) {
    return Page::FromAddress(NULL);
  }
  Counters::memory_allocated.Increment(size);

  // So long as we correctly overestimated the number of chunks we should not
  // run out of chunk ids.
  CHECK(!OutOfChunkIds());
  // 保存信息到chunkInfo，初始化chunk里的page
  int chunk_id = Pop();
  chunks_[chunk_id].init(start, size, owner);
  return InitializePagesInChunk(chunk_id, *num_pages, owner);
}


bool MemoryAllocator::CommitBlock(Address start, size_t size) {
  ASSERT(start != NULL);
  ASSERT(size > 0);
  ASSERT(initial_chunk_ != NULL);
  ASSERT(initial_chunk_->address() <= start);
  ASSERT(start + size <= reinterpret_cast<Address>(initial_chunk_->address())
                             + initial_chunk_->size());
  // commit，修改内存的属性，使得可用，见platform-linux.ccd的mmap
  if (!initial_chunk_->Commit(start, size)) return false;
  Counters::memory_allocated.Increment(size);
  return true;
}

// 初始化某块内存为page管理的结构
Page* MemoryAllocator::InitializePagesInChunk(int chunk_id, int pages_in_chunk,
                                              PagedSpace* owner) {
  ASSERT(IsValidChunk(chunk_id));
  ASSERT(pages_in_chunk > 0);

  Address chunk_start = chunks_[chunk_id].address();
  // 算出有效的开始地址，即要对齐
  Address low = RoundUp(chunk_start, Page::kPageSize);

#ifdef DEBUG
  size_t chunk_size = chunks_[chunk_id].size();
  Address high = RoundDown(chunk_start + chunk_size, Page::kPageSize);
  ASSERT(pages_in_chunk <=
        ((OffsetFrom(high) - OffsetFrom(low)) / Page::kPageSize));
#endif

  Address page_addr = low;
  for (int i = 0; i < pages_in_chunk; i++) {
    Page* p = Page::FromAddress(page_addr);
    // 保存下一页的地址和当前所属的chunk_id
    p->opaque_header = OffsetFrom(page_addr + Page::kPageSize) | chunk_id;
    // 不是large object
    p->is_normal_page = 1;
    // 指向下一页地址
    page_addr += Page::kPageSize;
  }

  // Set the next page of the last page to 0.
  // page_addr此时执行最后一页的末尾，减去一页大小得到最后一页的起始地址
  Page* last_page = Page::FromAddress(page_addr - Page::kPageSize);
  // 下一页地址为0
  last_page->opaque_header = OffsetFrom(0) | chunk_id;

  return Page::FromAddress(low);
}

// 释放多个chunk的内存
Page* MemoryAllocator::FreePages(Page* p) {
  if (!p->is_valid()) return p;

  // Find the first page in the same chunk as 'p'
  // 找出同chunk中的第一个page
  Page* first_page = FindFirstPageInSameChunk(p);
  Page* page_to_return = Page::FromAddress(NULL);
  // 不是第一个page
  if (p != first_page) {
    // Find the last page in the same chunk as 'prev'.
    Page* last_page = FindLastPageInSameChunk(p);
    // 执行p所在chunk的下一个chunk
    first_page = GetNextPage(last_page);  // first page in next chunk

    // set the next_page of last_page to NULL
    SetNextPage(last_page, Page::FromAddress(NULL));
    // p所在的chunk没有被删除
    page_to_return = p;  // return 'p' when exiting
  }
  // 删除多个chunk
  while (first_page->is_valid()) {
    int chunk_id = GetChunkId(first_page);
    ASSERT(IsValidChunk(chunk_id));

    // Find the first page of the next chunk before deleting this chunk.
    first_page = GetNextPage(FindLastPageInSameChunk(first_page));

    // Free the current chunk.
    DeleteChunk(chunk_id);
  }

  return page_to_return;
}

// 删除一个chunk
void MemoryAllocator::DeleteChunk(int chunk_id) {
  ASSERT(IsValidChunk(chunk_id));

  ChunkInfo& c = chunks_[chunk_id];

  bool in_initial_chunk = false;
  // initial_chunk_非空说明之前通过ReserveInitialChunk申请了内存 
  if (initial_chunk_ != NULL) {
    Address start = static_cast<Address>(initial_chunk_->address());
    Address end = start + initial_chunk_->size();
    // 判断当前删除的chunk管理的内存范围是不是在初始化时申请的内存里
    in_initial_chunk = (start <= c.address()) && (c.address() < end);
  }
  // 释放的是初始化申请的内存的一部分，否则是通过malloc额外申请的
  if (in_initial_chunk) {
    // TODO(1240712): VirtualMemory::Uncommit has a return value which
    // is ignored here.
    // 撤销chunk对应的内存，可能导致把之前申请的一大块内存切开。由操作系统完成
    initial_chunk_->Uncommit(c.address(), c.size());
    Counters::memory_allocated.Decrement(c.size());
  } else {
    LOG(DeleteEvent("PagedChunk", c.address()));
    // malloc申请的直接释放就行
    FreeRawMemory(c.address(), c.size());
  }
  // 重置
  c.init(NULL, 0, NULL);
  // 回收chunkId
  Push(chunk_id);
}

// 找出p对应的chunk中的第一个page的地址
Page* MemoryAllocator::FindFirstPageInSameChunk(Page* p) {
  int chunk_id = GetChunkId(p);
  ASSERT(IsValidChunk(chunk_id));

  Address low = RoundUp(chunks_[chunk_id].address(), Page::kPageSize);
  return Page::FromAddress(low);
}

// 找出chunk中的最后一个page的地址
Page* MemoryAllocator::FindLastPageInSameChunk(Page* p) {
  // 根据page获取所在chunk的id
  int chunk_id = GetChunkId(p);
  ASSERT(IsValidChunk(chunk_id));
  // chunk管理的内存的首地址和大小
  Address chunk_start = chunks_[chunk_id].address();
  size_t chunk_size = chunks_[chunk_id].size();
  // chunk管理的内存有效的末地址，即满足对齐的
  Address high = RoundDown(chunk_start + chunk_size, Page::kPageSize);
  ASSERT(chunk_start <= p->address() && p->address() < high);
  // 末地址减一页即最后一页的地址
  return Page::FromAddress(high - Page::kPageSize);
}

// 检查chunk是否管理着有效内存
bool MemoryAllocator::IsValidChunk(int chunk_id) {
  if (!IsValidChunkId(chunk_id)) return false;

  ChunkInfo& c = chunks_[chunk_id];
  return (c.address() != NULL) && (c.size() != 0) && (c.owner() != NULL);
}

// 检查chunkid的有效性
bool MemoryAllocator::IsValidChunkId(int chunk_id) {
  return (0 <= chunk_id) && (chunk_id < max_nof_chunks_);
}

// 检查给定page的地址是否在chunk管理的内存中
bool MemoryAllocator::IsPageInSpace(Page* p, PagedSpace* space) {
  ASSERT(p->is_valid());

  int chunk_id = GetChunkId(p);
  if (!IsValidChunkId(chunk_id)) return false;

  ChunkInfo& c = chunks_[chunk_id];
  return (c.address() <= p->address()) &&
         (p->address() < c.address() + c.size()) &&
         (space == c.owner());
}

// 获取下一页的地址
Page* MemoryAllocator::GetNextPage(Page* p) {
  ASSERT(p->is_valid());
  // 取出在opaque_header中的有效地址，取高位的值
  int raw_addr = p->opaque_header & ~Page::kPageAlignmentMask; // 2 ^ 13 - 1 
  return Page::FromAddress(AddressFrom<Address>(raw_addr));
}

// 取opaque_header的低n位，是ChunkId
int MemoryAllocator::GetChunkId(Page* p) {
  ASSERT(p->is_valid());
  return p->opaque_header & Page::kPageAlignmentMask;
}

// 在prev后插入next
void MemoryAllocator::SetNextPage(Page* prev, Page* next) {
  ASSERT(prev->is_valid());
  int chunk_id = prev->opaque_header & Page::kPageAlignmentMask;
  ASSERT_PAGE_ALIGNED(next->address());
  prev->opaque_header = OffsetFrom(next->address()) | chunk_id;
}

// 获取page所属的Space
PagedSpace* MemoryAllocator::PageOwner(Page* page) {
  int chunk_id = GetChunkId(page);
  ASSERT(IsValidChunk(chunk_id));
  return chunks_[chunk_id].owner();
}