CMU 15-445: TASK #2 - BUFFER POOL MANAGER

buffer_pool_manager.cpp

//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// buffer_pool_manager.cpp
//
// Identification: src/buffer/buffer_pool_manager.cpp
//
// Copyright (c) 2015-2019, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/buffer_pool_manager.h"

#include <list>
#include <unordered_map>

namespace bustub {

BufferPoolManager::BufferPoolManager(size_t pool_size, DiskManager *disk_manager, LogManager *log_manager)
    : pool_size_(pool_size), disk_manager_(disk_manager), log_manager_(log_manager) {
  // We allocate a consecutive memory space for the buffer pool.
  pages_ = new Page[pool_size_];
  replacer_ = new LRUReplacer(pool_size);

  // Initially, every page is in the free list.
  for (size_t i = 0; i < pool_size_; ++i) {
    free_list_.emplace_back(static_cast<int>(i));
  }
}

BufferPoolManager::~BufferPoolManager() {
  delete[] pages_;
  delete replacer_;
}

Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
  // 1.     Search the page table for the requested page (P).
  // 1.1    If P exists, pin it and return it immediately.
  // 1.2    If P does not exist, find a replacement page (R) from either the free list or the replacer.
  //        Note that pages are always found from the free list first.
  // 2.     If R is dirty, write it back to the disk.
  // 3.     Delete R from the page table and insert P.
  // 4.     Update P's metadata, read in the page content from disk, and then return a pointer to P.
  std::lock_guard<std::mutex> lock(latch_);
  auto iter = page_table_.find(page_id);
  if (iter != page_table_.end()) {
    replacer_->Pin(iter->second);
    Page *page = pages_ + iter->second;
    page->pin_count_++;
    return page;
  }

  if (!free_list_.empty()) {
    frame_id_t frame_id = free_list_.front();
    free_list_.pop_front();
    Page* page = pages_ + frame_id;
    page->page_id_ = page_id;
    page->pin_count_ = 1;
    page->is_dirty_ = false;
    disk_manager_->ReadPage(page_id, page->GetData());
    replacer_->Pin(frame_id);
    page_table_[page_id] = frame_id;
    return page;
  }

  frame_id_t victim_frame_id;
  if(!replacer_->Victim(&victim_frame_id)) {
    return nullptr;
  }
  Page *victim_page = pages_ + victim_frame_id;
  if (victim_page->IsDirty()) {
    disk_manager_->WritePage(victim_page->GetPageId(), victim_page->GetData());
  }
  page_table_.erase(victim_page->page_id_);
  victim_page->page_id_ = page_id;
  victim_page->pin_count_ = 1;
  victim_page->is_dirty_ = false;
  disk_manager_->ReadPage(page_id, victim_page->GetData());
  page_table_[page_id] = victim_frame_id;
  return victim_page;
}

bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty) {
  std::lock_guard<std::mutex> lock(latch_);
  auto iter = page_table_.find(page_id);
  if (iter == page_table_.end()) {
    return false;
  }
  Page *page = pages_ + iter->second;
  page->is_dirty_ = is_dirty;
  replacer_->Unpin(iter->second);
  return true;
}

bool BufferPoolManager::FlushPageImpl(page_id_t page_id) {
  // Make sure you call DiskManager::WritePage!
  std::lock_guard<std::mutex> lock(latch_);
  auto iter = page_table_.find(page_id);
  if (iter == page_table_.end()) {
    return false;
  }
  Page *page = pages_ + iter->second;
  disk_manager_->WritePage(page->GetPageId(), page->GetData());
  return true;
}

Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
  std::lock_guard<std::mutex> lock(latch_);
  // bool all_pinned = true;
  // for (int i = 0; i < pool_size_; i++) {
  //   if (pages_[i].GetPinCount() == 0) {
  //     all_pinned = false;
  //     break;
  //   }
  // }
  // if (all_pinned) {
  //   return nullptr;
  // }

  if (!free_list_.empty()) {
    frame_id_t frame_id = free_list_.front();
    free_list_.pop_front();
    *page_id = disk_manager_->AllocatePage();
    page_table_[*page_id] = frame_id;
    Page *page = pages_ + frame_id;
    page->page_id_ = *page_id;
    page->pin_count_ = 0;
    page->is_dirty_ = false;
    return page;
  }

  frame_id_t victim_frame_id;
  if(!replacer_->Victim(&victim_frame_id)) {
    return nullptr;
  }

  // page_id_t victim_page_id = INVALID_PAGE_ID;
  // for (auto iter = page_table_.cbegin(); iter != page_table_.cend(); ++iter) {
  //   if (iter->second == victim_page_id) {
  //     victim_page_id = iter->second;
  //     break;
  //   }
  // }
  // if (victim_page_id == INVALID_PAGE_ID) {
  //   return nullptr;
  // }

  Page *victim_page = pages_ + victim_frame_id;
  if (victim_page->IsDirty()) {
    disk_manager_->WritePage(victim_page->GetPageId(), victim_page->GetData());
  }
  page_table_.erase(victim_page->page_id_);

  *page_id = disk_manager_->AllocatePage();
  page_table_[*page_id] = victim_frame_id;
  victim_page->ResetMemory();
  victim_page->page_id_ = *page_id;
  victim_page->pin_count_ = 0;
  victim_page->is_dirty_ = false;
  return victim_page;

  // 0.   Make sure you call DiskManager::AllocatePage!
  // 1.   If all the pages in the buffer pool are pinned, return nullptr.
  // 2.   Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
  // 3.   Update P's metadata, zero out memory and add P to the page table.
  // 4.   Set the page ID output parameter. Return a pointer to P.
}

bool BufferPoolManager::DeletePageImpl(page_id_t page_id) {
  // 0.   Make sure you call DiskManager::DeallocatePage!
  // 1.   Search the page table for the requested page (P).
  // 1.   If P does not exist, return true.
  // 2.   If P exists, but has a non-zero pin-count, return false. Someone is using the page.
  // 3.   Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.
  std::lock_guard<std::mutex> lock(latch_);
  auto iter = page_table_.find(page_id);
  if (iter == page_table_.end()) {
    return true;
  }

  Page *page = pages_ + iter->second;
  if (page->GetPinCount() != 0) {
    return false;
  }

  page_table_.erase(page_id);
  page->page_id_ = INVALID_PAGE_ID;
  free_list_.push_back(iter->second);
  disk_manager_->DeallocatePage(page_id);
  return true;
}

void BufferPoolManager::FlushAllPagesImpl() {
  // You can do it!
}

}  // namespace bustub