#include <vector>
#include <string>
#include <list>
#include <cstdlib>
#include "xxhash32.h"
#include "buffer.h"
#include <iostream>
ExtendibleHashDirectory::ExtendibleHashDirectory(int initialDepth, int maxDepth)
: globalDepth(initialDepth), maxDepth(maxDepth), max_chaining(5) {
directoryVec.resize(1 << globalDepth); // 2^globalDepth entries
}
int ExtendibleHashDirectory::addPage(int pageId, PageFrame* pageFrame) {
uint32_t hash = XXHash32::hash(&pageId, sizeof(int), 0);
int index = 0;
if (globalDepth > 0) {
index = hash >> (32 - globalDepth); // Use the first globalDepth bits as the index
}
if (globalDepth < maxDepth && directoryVec[index].size() >= max_chaining) {
// Overflow when the chain is length 5, can be tuned.
// Increase the size will add overhead for remove (and all functions in general)
directoryVec[index].push_back(pageFrame);
globalDepth++;
std::vector<std::list<PageFrame*>> newDirectory(1 << globalDepth);
for (int i = 0; i < (1 << (globalDepth - 1)); i++) {
for (PageFrame* frame : directoryVec[i]) {
int framePageId = frame->pageId;
uint32_t frameHash = XXHash32::hash(&framePageId, sizeof(int), 0); // Rehash the exisiting pages
int newIndex = 0;
if (globalDepth > 0){
newIndex = frameHash >> (32 - globalDepth);
}
newDirectory[newIndex].push_back(frame);
}
}
directoryVec = std::move(newDirectory);
return 1;
}
else if (directoryVec[index].size() >= max_chaining) { // max size reached but overflowed again, need evict
return 0;
}
else {
directoryVec[index].push_back(pageFrame);
return 1;
}
}
int ExtendibleHashDirectory::getGlobalDepth() {
return globalDepth;
}
std::list<PageFrame*>& ExtendibleHashDirectory::getPageFrames(int index) {
return directoryVec[index];
}
BufferPool::BufferPool(int initialDepth, int maxDepth)
: directory(initialDepth, maxDepth), curSize(0), head(-1), tail(-1) {}
void BufferPool::insertPage(int pageId, char* data) {
// std::cout << "Page " << pageId <<" is being inserted.\n";
// Check if the page is already in the buffer pool
if (getPage(pageId) != nullptr) {
return; // Page is already in the buffer pool
}
PageFrame *pg = new PageFrame(pageId, data);
// Set up info for LRU algorithm. Inserted page is at head of queue, pointing to old head.
if(head == -1){ // Special case: buffer pool is empty
head = pageId;
tail = pageId;
pg->next = -1;
pg->previous = -1;
}
else{ // buffer pool is non-empty
getPageFrame(head)->previous = pageId; // old head points to new
pg->next = head; // new head points to old
pg->previous = -1; // new head has no prev element
head = pageId; // head global variable now points to new head
}
// Add the page to the buffer pool and directory
int result = directory.addPage(pageId, pg);
// If the page is unable to be successfully inserted, keep removing pages until it can be.
while (result == 0) {
evictPage(evictPolicy());
result = directory.addPage(pageId, pg);
}
// std::cout << "Page " << pageId <<" has been inserted.\n";
curSize++;
}
// Could have getPageFrame integrated. Do this later?
char* BufferPool::getPage(int pageId) {
uint32_t hash = XXHash32::hash(&pageId, sizeof(int), 0);
uint32_t hashPrefix = 0;
if (directory.getGlobalDepth() > 0){
hashPrefix = hash >> (32 - directory.getGlobalDepth());
}
if (hashPrefix < 0 || hashPrefix >= directory.directoryVec.size()){
return nullptr;
}
std::list<PageFrame*> pageList = directory.getPageFrames(hashPrefix);
for (PageFrame* frame : pageList) {
if (frame->pageId == pageId) { // we have found the desired pageframe.
// Update LRU queue info (if this page is the head, no updates are needed).
if(pageId != head){
if(pageId == tail){ // There is a new tail for the queue. Update it.
tail = frame->previous;
getPageFrame(frame->previous)->next = -1;
}
else{ // current page is not head or tail, is a middle element.
PageFrame* previous_page = getPageFrame(frame->previous);
PageFrame* next_page = getPageFrame(frame->next);
previous_page->next = next_page->pageId;
next_page->previous = previous_page->pageId;
}
// Now, move page to front of queue.
frame->next = head; // current frame points to old head.
frame->previous = -1; // current frame has no prior element.
getPageFrame(head)->previous = pageId; // old head points to current frame as previous element.
head = pageId; // now we can make the new frame the head safely.
}
return frame->getData();
}
}
return nullptr; // Page not found in the buffer pool
}
// Helper function, only for use by the page replacement algorithm.
// This function assumes the page corresponding to pageId exists. Nullptr is not meant to be returned, if it is there is a flaw in the code.
PageFrame* BufferPool::getPageFrame(int pageId) {
uint32_t hash = XXHash32::hash(&pageId, sizeof(int), 0);
uint32_t hashPrefix = 0;
if (directory.getGlobalDepth() > 0){
hashPrefix = hash >> (32 - directory.getGlobalDepth());
}
if (hashPrefix < 0 || hashPrefix >= directory.directoryVec.size()){
std::cerr << "Page replacement error: Buffer page with pageId " << pageId << " queried for, but does not exist.\n";
return nullptr;
}
std::list<PageFrame*> pageList = directory.getPageFrames(hashPrefix);
for (PageFrame* frame : pageList) {
if (frame->pageId == pageId) {
return frame;
}
}
std::cerr << "Page replacement error: Buffer page with pageId " << pageId << " queried for, but does not exist.\n";
return nullptr; // Page not found in the buffer pool
}
void BufferPool::setMaxDirectoryDepth(int depth) {
if(depth == 0){no_buffer = true;}
else{no_buffer = false;}
if (depth > directory.globalDepth) {
directory.maxDepth = depth;
return;
}
else{
std::vector<std::list<PageFrame*>> newDirectory(1 << depth);
for (int i = 0; i < (1 << directory.globalDepth); i++) {
for (PageFrame* frame : directory.directoryVec[i]) {
int framePageId = frame->pageId;
uint32_t frameHash = XXHash32::hash(&framePageId, sizeof(int), 0); // Rehash the exisiting pages
int newIndex = 0;
if (depth > 0) {
newIndex = frameHash >> (32 - depth);
}
newDirectory[newIndex].push_back(frame);
}
}
directory.directoryVec = std::move(newDirectory);
directory.maxDepth = depth;
directory.globalDepth = depth;
for (int i = 0; i < (1 << directory.globalDepth); i++) {
while (directory.directoryVec[i].size() >= directory.max_chaining){
evictPage(evictPolicy());
}
}
}
}
void BufferPool::evictPage(PageFrame* pageFrame) {
// std::cout << "Page " << pageFrame->pageId <<" is being evicted.\n";
uint32_t hash = XXHash32::hash(&pageFrame->pageId, sizeof(int), 0);
uint32_t hashPrefix = 0;
if (directory.getGlobalDepth() > 0){
hashPrefix = hash >> (32 - directory.getGlobalDepth());
}
// Remove is O(N) in nature, but pageList length <= 5 here. Constant time.
// A handmade Linked list can be created for this but in sacrific of the clean,
// safe code of std::list
free(pageFrame->data);
directory.directoryVec[hashPrefix].remove(pageFrame);
delete(pageFrame);
curSize -= 1;
}
PageFrame* BufferPool::evictPolicy(){
// LRU eviction policy: evict the least recently used page. We then need to update our linked list.
// Edge case: empty linked list, buffer pool has been exhausted
if(tail == -1) return nullptr;
// std::cerr << "Page replacement error: eviction called on empty buffer pool.\n";
// Edge case: only one element in linked list.
if(head == tail){
int frameNum = head;
head = -1;
tail = -1;
return getPageFrame(frameNum);
}
// Can safely assume linked list size >= 2 (oldTail->previous exists)
PageFrame* oldTail = getPageFrame(tail); // Page to be evicted
PageFrame* newTail = getPageFrame(oldTail->previous); // new page to be set as tail.
newTail->next = -1; //new tail has no next element.
tail = newTail->pageId; // set global tail variable to new tail.
return oldTail;
}
// Policy that is used after compaction. Empties the buffer pool to remove invalid pages.
void BufferPool::emptyBuffer(){
PageFrame* currPage = evictPolicy();
while (currPage != nullptr){
evictPage(currPage);
currPage = evictPolicy();
}
}
// Potential alternate policy that can be used after compaction. Removes ALL pages that correspond to a given SST.
// for baseline_size, pass in LSM_level0_pagecount_upperbound().
void BufferPool::evictFromSST(int baseline_size, int SST_num){
int start_index = (((1 << SST_num) - 1) * baseline_size); // start of pages for current SST
int end_index = (((1 << (SST_num + 1)) - 1) * baseline_size); // start of pages for next SST
evict_in_range(start_index, end_index);
}
// Evicts all pages with start_index <= PageID < end_index.
void BufferPool::evict_in_range(int start_index, int end_index){
int curr = head;
PageFrame* currPage;
int nextPage;
// Iterate through linked list of buffer pages
while(curr != 1){ // curr will be -1 if the buffer is empty, or if we have tried to iterate past the tail.
currPage = getPageFrame(curr); // get page frame for current page. Should always exist.
if(currPage == nullptr){ // error checking- should never be nullputr
std::cerr << "Error in evict_in_range: Buffer page with pageId " << currPage << " queried for, but does not exist.\n";
return;
}
nextPage = currPage->next; // set next page.
if((currPage->pageId >= start_index) && (currPage->pageId < end_index)){ // if curr belongs to SST we want to evict from
if(head == tail){ // one element in list, indicate buffer is now empty
head = -1;
tail = -1;
}
else if(currPage->pageId == head){ // front of list, update head
head = currPage->next;
}
else if(currPage->pageId == tail){ // end of list, update tail
tail = currPage->previous;
}
else{ // middle of list, update next and previous pointers
PageFrame* previous_page = getPageFrame(currPage->previous);
PageFrame* next_page = getPageFrame(currPage->next);
previous_page->next = next_page->pageId;
next_page->previous = previous_page->pageId;
}
evictPage(currPage);
}
curr = nextPage; // move to next page
}
}
void BufferPool::destroyBuffer(){
for (int i = 0; i < (1 << directory.globalDepth); i++) {
for (PageFrame* frame : directory.directoryVec[i]) {
free(frame->data);
delete(frame);
}
}
delete(this);
}