BufferPool.java

package simpledb;

import java.io.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * BufferPool manages the reading and writing of pages into memory from disk.
 * Access methods call into it to retrieve pages, and it fetches pages from the
 * appropriate location.
 * <p>
 * The BufferPool is also responsible for locking; when a transaction fetches a
 * page, BufferPool checks that the transaction has the appropriate locks to
 * read/write the page.
 * 
 * @Threadsafe, all fields are final
 */
public class BufferPool {

	/** Bytes per page, including header. */
	private static final int DEFAULT_PAGE_SIZE = 4096;

	private static int pageSize = DEFAULT_PAGE_SIZE;

	/**
	 * Default number of pages passed to the constructor. This is used by other
	 * classes. BufferPool should use the numPages argument to the constructor
	 * instead.
	 */
	public static final int DEFAULT_PAGES = 50;

	private Page[] pool;
	private Map<PageId, Integer> pidToPoolIdx;
	private Stack<Integer> freePoolIdxStack;
	private Map<PageId, Integer> pidToLastAccessCounter;

	private int accessCounter;

	/**
	 * Creates a BufferPool that caches up to numPages pages.
	 *
	 * @param numPages
	 *            maximum number of pages in this buffer pool.
	 */
	public BufferPool(int numPages) {
		this.accessCounter = 0;
		this.pool = new Page[numPages];
		this.pidToPoolIdx = new HashMap<>();
		this.pidToLastAccessCounter = new HashMap<>();
		this.freePoolIdxStack = new Stack<>();
		for (int i = this.pool.length - 1; i > -1; i--) {
			this.freePoolIdxStack.push(i);
		}
	}

	public static int getPageSize() {
		return pageSize;
	}

	// THIS FUNCTION SHOULD ONLY BE USED FOR TESTING!!
	public static void setPageSize(int pageSize) {
		BufferPool.pageSize = pageSize;
	}

	// THIS FUNCTION SHOULD ONLY BE USED FOR TESTING!!
	public static void resetPageSize() {
		BufferPool.pageSize = DEFAULT_PAGE_SIZE;
	}

	/**
	 * Retrieve the specified page with the associated permissions. Will acquire a
	 * lock and may block if that lock is held by another transaction.
	 * <p>
	 * The retrieved page should be looked up in the buffer pool. If it is present,
	 * it should be returned. If it is not present, it should be added to the buffer
	 * pool and returned. If there is insufficient space in the buffer pool, a page
	 * should be evicted and the new page should be added in its place.
	 *
	 * @param tid
	 *            the ID of the transaction requesting the page
	 * @param pid
	 *            the ID of the requested page
	 * @param perm
	 *            the requested permissions on the page
	 */
	public Page getPage(TransactionId tid, PageId pid, Permissions perm)
			throws TransactionAbortedException, DbException {
		while (!Database.getLockManager().hasLock(tid, pid, perm)) {
			Database.getLockManager().lock(tid, pid, perm);
		}
		if (this.pidToPoolIdx.containsKey(pid)) {
			this.pidToLastAccessCounter.put(pid, ++this.accessCounter);
			return this.pool[this.pidToPoolIdx.get(pid)];
		}
		if (this.freePoolIdxStack.isEmpty()) {
			this.evictPage();
		}
		int idx = this.freePoolIdxStack.pop();
		DbFile file = Database.getCatalog().getDatabaseFile(pid.getTableId());
		
		this.pool[idx] = file.readPage(pid);
		this.pidToPoolIdx.put(pid, idx);
		this.pidToLastAccessCounter.put(pid, ++this.accessCounter);
		return this.pool[idx];
	}

	/**
	 * Releases the lock on a page. Calling this is very risky, and may result in
	 * wrong behavior. Think hard about who needs to call this and why, and why they
	 * can run the risk of calling it.
	 *
	 * @param tid
	 *            the ID of the transaction requesting the unlock
	 * @param pid
	 *            the ID of the page to unlock
	 */
	public void releasePage(TransactionId tid, PageId pid) {
		Database.getLockManager().unlock(tid, pid);
	}

	/**
	 * Release all locks associated with a given transaction.
	 *
	 * @param tid
	 *            the ID of the transaction requesting the unlock
	 */
	public void transactionComplete(TransactionId tid) throws IOException {
		this.transactionComplete(tid, true);
	}

	/** Return true if the specified transaction has a lock on the specified page */
	public boolean holdsLock(TransactionId tid, PageId pid) {
		return Database.getLockManager().hasLock(tid, pid, Permissions.READ_ONLY);
	}

	/**
	 * Commit or abort a given transaction; release all locks associated to the
	 * transaction.
	 *
	 * @param tid
	 *            the ID of the transaction requesting the unlock
	 * @param commit
	 *            a flag indicating whether we should commit or abort
	 */
	public void transactionComplete(TransactionId tid, boolean commit) throws IOException {
		if (commit) {
			this.flushPages(tid);
		} else
			this.abortTransaction(tid);
		Database.getLockManager().unlock(tid);
	}

	/*
	 * Aborts transaction tid
	 */
	public synchronized void abortTransaction(TransactionId tid) {
		for (int i = 0; i < this.pool.length; i++) {
			Page page = this.pool[i];
			if (page == null)
				continue;
			if (tid.equals(page.isDirty()))
				this.discardPage(page.getId());
		}
	}

	/**
	 * Add a tuple to the specified table on behalf of transaction tid. Will acquire
	 * a write lock on the page the tuple is added to and any other pages that are
	 * updated (Lock acquisition is not needed for lab2). May block if the lock(s)
	 * cannot be acquired.
	 * 
	 * Marks any pages that were dirtied by the operation as dirty by calling their
	 * markDirty bit, and adds versions of any pages that have been dirtied to the
	 * cache (replacing any existing versions of those pages) so that future
	 * requests see up-to-date pages.
	 *
	 * @param tid
	 *            the transaction adding the tuple
	 * @param tableId
	 *            the table to add the tuple to
	 * @param t
	 *            the tuple to add
	 */
	public void insertTuple(TransactionId tid, int tableId, Tuple t)
			throws DbException, IOException, TransactionAbortedException {
		DbFile file = Database.getCatalog().getDatabaseFile(tableId);
		List<Page> affectedPages = file.insertTuple(tid, t);
		for (Page page : affectedPages) {
			page.markDirty(true, tid);
			PageId pid = page.getId();
			if (!this.pidToPoolIdx.containsKey(pid) && this.freePoolIdxStack.isEmpty()) {
				this.evictPage();
			}
			int idx = this.pidToPoolIdx.containsKey(pid) ? this.pidToPoolIdx.get(pid) : this.freePoolIdxStack.pop();
			this.pool[idx] = page;
			this.pidToPoolIdx.put(pid, idx);
			this.pidToLastAccessCounter.put(pid, ++this.accessCounter);
		}
	}

	/**
	 * Remove the specified tuple from the buffer pool. Will acquire a write lock on
	 * the page the tuple is removed from and any other pages that are updated. May
	 * block if the lock(s) cannot be acquired.
	 *
	 * Marks any pages that were dirtied by the operation as dirty by calling their
	 * markDirty bit, and adds versions of any pages that have been dirtied to the
	 * cache (replacing any existing versions of those pages) so that future
	 * requests see up-to-date pages.
	 *
	 * @param tid
	 *            the transaction deleting the tuple.
	 * @param t
	 *            the tuple to delete
	 */
	public void deleteTuple(TransactionId tid, Tuple t) throws DbException, IOException, TransactionAbortedException {
		RecordId rid = t.getRecordId();
		assert (rid != null);
		PageId pid = rid.getPageId();
		DbFile file = Database.getCatalog().getDatabaseFile(pid.getTableId());
		List<Page> affectedPages = file.deleteTuple(tid, t);
		for (Page page : affectedPages)
			page.markDirty(true, tid);
	}

	/**
	 * Flush all dirty pages to disk. NB: Be careful using this routine -- it writes
	 * dirty data to disk so will break simpledb if running in NO STEAL mode.
	 */
	public synchronized void flushAllPages() throws IOException {
		for (int i = 0; i < this.pool.length; i++) {
			Page page = this.pool[i];
			if (page != null)
				this.flushPage(page.getId());
		}
	}

	/**
	 * Remove the specific page id from the buffer pool. Needed by the recovery
	 * manager to ensure that the buffer pool doesn't keep a rolled back page in its
	 * cache.
	 * 
	 * Also used by B+ tree files to ensure that deleted pages are removed from the
	 * cache so they can be reused safely
	 */
	public synchronized void discardPage(PageId pid) {
		int poolIdx = this.pidToPoolIdx.get(pid);
		pool[poolIdx] = null;
		this.pidToPoolIdx.remove(pid);
		this.pidToLastAccessCounter.remove(pid);
		this.freePoolIdxStack.add(poolIdx);
	}

	/**
	 * Flushes a certain page to disk
	 * 
	 * @param pid
	 *            an ID indicating the page to flush
	 */
	private synchronized void flushPage(PageId pid) throws IOException {
		DbFile file = Database.getCatalog().getDatabaseFile(pid.getTableId());
		Page page = pool[this.pidToPoolIdx.get(pid)];
		TransactionId tid = page.isDirty();
		if (tid != null) {
//			while (!Database.getLockManager().hasFileLock(tid, pid.getTableId()))
//				 Database.getLockManager().lockFile(tid, pid.getTableId());
			file.writePage(page);
//				Database.getLockManager().unlockFile(tid, pid.getTableId());
			page.markDirty(false, null);
		}
	}

	/**
	 * Write all pages of the specified transaction to disk.
	 */
	public synchronized void flushPages(TransactionId tid) throws IOException {
		for (int i = 0; i < this.pool.length; i++) {
			Page page = this.pool[i];
			if (page == null)
				continue;
			if (tid.equals(page.isDirty()))
				flushPage(page.getId());
		}
	}

	/**
	 * Discards a page from the buffer pool. Flushes the page to disk to ensure
	 * dirty pages are updated on disk.
	 */
	private synchronized void evictPage() throws DbException {
		assert (this.freePoolIdxStack.isEmpty());
		PageId oldestPid = null;
		int oldestAccessCount = this.accessCounter;
		for (int i = 0; i < this.pool.length; i++) {
			Page page = this.pool[i];
			if (page == null || page.isDirty() != null)
				continue;
			PageId pid = page.getId();
			if (this.pidToLastAccessCounter.get(pid) <= oldestAccessCount) {
				oldestAccessCount = this.pidToLastAccessCounter.get(pid);
				oldestPid = pid;
			}
		}
		if (oldestPid == null) {
			throw new DbException("Couldn't evict page because all pages in bufferpool are dirty");
		}
		try {
			this.flushPage(oldestPid);
		} catch (IOException e) {
			throw new DbException("Couldn't flushPage");
		}
		this.discardPage(oldestPid);
	}

}