Database Systems

Due Date

Complete lab: Due by 11:59 p.m., Tuesday, Feb. 11, 2025.. Full implementation. Passes all tests in all unit test programs provided.

Checkpoint: Tuesday, Feb. 4. Pass all tests in checkpt.

Your lab partner for Lab 2 is listed here: Lab 2 lab partners

Our guidelines for working with partners: working with partners, etiquette and expectations

This is a large programming assignment that requiress reading and understanding code from an even larger code base. We strongly encourage you to plan to work on this early and often, and to have this lab assignment page up, and refer to it often, as you work.

Overview

In this lab you will implement the Buffer Manager layer of the SwatDB database management system. You will implement all Buffer Manager interface functionality with a version of the Clock page replacement algorithm described in the Lab Details section. The SwatDB Buffer Manager interacts with the Disk Manager to read, write, allocate, and deallocate Pages of file data from disk in response to requests from the File Manager for Pages of relation and index files.

The primary goal of the SwatDB lab assignments is to gain an understanding of the details of how a relational DBMS works by implementing and testing parts of a relational DBMS.

The SwatDB code base is quite extensive and will require significant reading of its documentation (see SwatDB).

Lab Goals

The main goals of the SwatDB Buffer Manager Lab are:

Understanding the functionality of the Buffer Management layer of a database.
Simulating the management of Main Memory and implementing and testing a page replacement policy.
Navigating provided documentation to utilize a provided interface for the SwatDB Disk Manager Layer.
Developing a testing strategy for a large, complex system; making use of a provided unit testing framework, testing sandbox, and debugging tools.
Practice working with part of a large code base, much of which you have access to only through its interface definition (i.e., .h files and generated documentation).

Starting Point Code

If you have not already done so, first create a course directory for this course, and add a lab subdirectory for your lab repos:

mkdir -p cs44
mkdir -p cs44/labs
cd cs44/labs

We will be using git repos hosted on the college’s GitHub server for labs in this class. If you have not used git or the college’s GitHub server before, here are some detailed instructions on using git for CS44 labs.

Next find your git repo for this lab assignment off the GitHub server for our class: CS44-s25

Clone your git repo (Lab2-userID1-userID2) containing starting point files into your labs directory:

cd ~/cs44/labs
git clone [the ssh url to your your repo]
cd Lab2-userID1-userID2

If all was successful, you should see the following files (highlighted files require modification):

Lab 2 Files

Makefile - pre-defined. You may edit this file to add extra source files or execution commands.
README.md - some directions about how to compile and run test programs for the Buffer Manager.

Buffer Manager layer Header Files:

bufmgr.h, bm_buffermap.h, bm_policies.h - the SwatDB BufferManager class, BufferMap class, and Clock class.

You should not add any new data members to these classes or public methods. You can add private helper methods for good modular code design.
bm_frame.h: the Frame class definition. Do not modify this file, it is provided just for reference as it is used extensively by buffer manager classes you will implement.
bm_replacement.h: defines the ReplacementPolicy base class of which the Clock class is derived. Do not modify this file, it is provided just for reference.

Buffer Manager layer Source Files:

bufmgr.cpp - the SwatDB BufferManager class implementation.

You will implement most of the functions in the BufferManager interface in this file. You may add private helper functions for good modular design.
bm_policies.cpp - full implementation of the Random policy.

You will implement the Clock replacement policy methods in the file.. You may add private helper functions for good modular design.
bm_buffermap.cpp - the BufferMap class implementation.

You will implenet the BufferMap methods in this file.. You may add private helper functions for good modular design.
bm_replacement.cpp: the methods of the ReplacementPolicy base class. Do not modify this file. This is here for your reference.
bm_frame.cpp: the methods of the Frame class. Do not modify this file. This is here for your reference. The Frame class is used by lots of the methods you will implement.

For all methods that you define and/or implement, make sure to include good function comments in both the .h and .cpp files (function comments in .h files alone are not sufficient). For new methods, follow the conventions of existing comments in the .h file. To start comments in .cpp, copy and paste function comments from the .h file into the .cpp. Remember .cpp comments are for someone reading your code, vs. using your interface, so you may have additional comments in the .cpp that explain algorithms used or tricky code sequences.

Buffer Manager layer Test Files:

We are giving you a lot of unit tests for this assignment. You are not required to add more tests as part of this assignment. However, you still may want to add some more for further stress testing your solution. Each of the unit test files has a placeholder for StudentTests into which you can add your own. You can also add to the sandbox.cpp test file (testing in a different way that doesn’t use the unit test infrastructure). This is often useful for debugging specific methods/functionality.

There are debug print methods that you can call to see buffer manager state as you debug and test.

Unit tests files:

checkpt.cpp - unit testing code for the checkpoint.
unittest.cpp - unit testing code for Buffer Manager interface.
replaementtests.cpp - tests specifically for page replacement.
clocktests.cpp - tests specifically the clock replacement policy.
performancetests.cpp - performs performance tests comparing Random to Clock. NOTE: all tests will complete successfully regardless of if you have implemented Clock or not (there are no tests for correctness). Instead of focusing on successfully passing, uses these tests to help you debug your statistics setting methods.

Sandbox test program:

sandbox.cpp - another way to test your code. This is a more application code style vs. using the unit-test infrastructure. Note the examples of how to print out BufferManager state. You can use this to add your own testing code. This is meant to complement the unit tests to help with implementation, debugging, or designing new tests.

Deliverables

The following will be evaluated for your lab grade:

The BufferManager (in bufmgr.cpp), Clock (in bm_policies.cpp), and BufferMap (in bm_buffermap.cpp) classes. These classes implement the Buffer Manager layer of SwatDB with the Clock replacement algorithm. Their class implementations should be completed in each of their .cpp files listed above.
The class definitions in .h files. Only add private helper methods to class definitions to support good modular design of your solution. Do not add public methods to any classes defined in these file. Also note where you can and cannot add private data members to classes (look for comments in .h files and in lab write-up).
Your Lab 2 Questionnaire to be completed individually (This will open on the due date and close after 3 days)

Checkpoint

Before the checkpoint due date, you should complete Buffer Manager functionality to pass all the unit tests in the checkpt program. While we recommend dealing with exceptions as you implement the methods, we will not require that exceptions are implemented for the checkpoint.

The checkpoint functionality includes:

A complete implementation of the BufferMap.
A partial implementation of _allocateFrame - enough to handle the case where the buffer pool is mostly empty. It should be able to increment the clock hand and return the next Frame to the caller since it will be empty.
allocatePage without triggering Page replacement (the case when there are free Frames of Buffer Pool space to allocate), and without complete error handling or exceptions.
getPage without triggering Page replacement (the case when there are free Frames in the buffer pool), and without complete error handling or exceptions.
releasePage
setDirty
flushPage

Read the Lab Details section for a description of each (also, refer to SwatDB documention and comments in .h and .cpp files), and follow the Suggested Order for impelmenting the Buffer Manager.

SwatDB

This is the first lab assignment of several that involve implementing parts of the SwatDB Database Management System. In this assignment you will implement the Buffer Manager layer of SwatDB, which interacts with DiskManager’s interface when Page data need to be de/allocated, or read/written between Memory and Disk.

For information about SwatDB, including a link to its on-line code documentation, see this page:

About SwatDB

In addition to the .h files distributed with this lab, the SwatDB documentation that will be particularly helpful for this lab includes:

The DiskManager interface
Type and constant definitions in swatdb_types.h
The Exceptions classes defined at the BufferManager and DiskManger layers in swatdb_exceptions.h that you may need to catch or throw. For some Disk Manager layer excpetion, the Buffer Manager may catch them or just pass them through to a higher level layer (not catch them). Check the BufferManager method function comments in bufmgr.h to see if a particular method needs to throw a BufferManager layer exception(s) or not.

Lab Details

The BufferManger class is declared in the bufmgr.h header file that is part of the starting point code with this lab. Open this file in an editor to read its contents:

vim bufmgr.h

You may also look at the SwatDB on-line documentation of the bufmgr.h for this file (Note: there are some extra features in the online documentation that you are not responsible for implementing, e.g., concurrency. Your local bufmgr.h is the version you are responsible for implementing.).

What to implement

The buffer manager is defined in four main modules: bufmgr.[h,cpp], bm_frame.[h,cpp], bm_buffermap.[h,cpp], bm_policies.[h,cpp]:

You need to complete the BufferMap, Clock, and BufferManager classes to implement the Buffer Manger layer. The Frame class is fully implemented for you.

The code for each should be written in its associated .cpp file. Each starting point file includes stub functions for all the methods you need to implement, with TODO comments for the parts you need to do. You may also add additional private methods for good modular design (make sure to add them in the .h class definitions as well, but they must be private).

In addition, you may add some code to test your BufferManger implementation to one or more of the test program, that use different testing frameworks:

unit tests programs: checkpt.cpp, unittest.cpp, clocktests.cpp and performancetests.cpp
programatic interface: sandbox.cpp

Testing is described in more detail in the Testing your code section.

Below we describe the main functionality you need to implement. However, make sure to read the more detailed comments about each method in the .h and .cpp files for complete information about what these methods should do. In particular look closely at their parameter descriptions, return values, and any exceptions they may throw.

Frame

The Frame class, defined in bm_frame.[h,cpp], stores meta data about the Page stored in a Frame of the Buffer Pool.

We give you full implementation of the Frame class methods, but take a look at them to see what they do since you will need to use these methods and the Frame data members in your BufferManager code.

BufferMap

The BufferMap class, defined in bm_buffermap.[h,cpp], implements a mapping of PageId to FrameId in the Buffer Pool. This allows you to quickly identify whether a requested page is in the buffer pool already, and where to find it. The implementation is a simplified dictionary (or hash table implementation) from CS35 and uses the C++ standard library unordered_map to implement the map data structure. We provide a hash function for it to use BufHash in bm_buffermap.h, and you can see how its data member is defined:

private:
   std::unordered_map<PageId,FrameId,BufHash> buf_map;

Your implementation should use std::unordered_map methods to find, insert, erase, etc. items to the BufferMap. Here is some unordered_map documentation. The implementation is not complicated, but you will need to first understand how to use unordered_map before proceeding.

You will implement the following BufferMap class methods:

get: takes a PageId and returns the FrameId (i.e., index into the buffer pool) in which the Page is stored. It throws a PageNotFoundBufMgr exception if the page is not in the buffer pool.
contains: takes a PageId and returns true if the Page with this PageId is in the Buffer Pool, and false if not.
insert: takes a PageId and FrameId and inserts a new <PageId,FrameId> mapping for it into the BufferMap. It throws a PageAlreadyLoadedBufMgr exception if the PageID is already in the map (i.e., it is already in the buffer pool).
remove: takes a PageId and removes its mapping from the BufferMap. It throws a PageNotFoundBufMgr exception if the page is not in the map.

Read the method comments in bm_buffermap.h or bm_buffermap.cpp to see what specific parameter values are, what the return values are, and if the method may throw exceptions for certain cases. Your implementation must match these more detailed criteria described in the method comments.

BufferManager

The BufferManger class defines the Buffer Manager interface to the higher layer of SwatDB.

Note: For this lab, you will implement the slightly simplified version declared in bufmgr.h. The implementation in the full SwatDB includes some synchronization that you do not need to implement, so you should ignore the mutex data members.

Data Members:

buf_pool an array of Page objects. These are the Pages of Main Memory that make up the Buffer Pool.
frame_table an array of Frame objects, one for each frame in the Buffer Pool. Each entry contains meta-data about the Page stored in the corresponding Frame of the Buffer Pool.
replacement_pol a pointer to a ReplacementPolicy object. You will implement the Clock class that is derived from ReplacementPolicy to implement the Clock replacement algorithm.
buf_map a BufferMap object that is used to map a PageId to a FrameId that stores the Page.
disk_mgr is a pointer to the SwatDB DiskManager. The Buffer Manager uses this to request Page I/O operations to the Disk Manager layer.

Figure 1. The buf_pool, frame_table, and replacement_pol data members of the BufferManager store file page data in frames of buffer pool memory, store meta-data for each frame of buffer pool memory, and store state for the clock replacement algorithm. NOTE: the Clock object has many other data members that we are not showing that are inherited from the ReplacementPolicy class, including the free list of pages.

Methods you need to implement

Below is a brief description of the methods you need to implement. You will also need to read the function comments for key implementation details.

~BufferManager destructor needs to ensure that any dirty Pages in the Buffer Pool are written back to disk. The destructor would be called when the DBMS system is being shut down or rebooted, and needs to ensure that DB data are persistent.
allocatePage adds a new page to a File and allocates an empty Page for it in the Buffer Pool. It takes a FileId specifying in which DB File to allocate a new page and returns the address of the Page of Buffer Pool allocated for the new page, and the PageId of the new Page.

The method should first find a frame in the Buffer Pool to allocate to store this new empty page. This is handled by the _allocateFrame method (see below). If there is no space an InsufficientSpaceBufMgr exception should be thrown from _allocateFrame. If successful, this method can then call the Disk Manager allocatePage method to allocate a new Page in the underlying file and get its unique PageId. However, the DiskManager could potential throw an exception if the FileId is invalid or there is no space on disk; you should let this pass through. The Buffer Manger state needs to be updated to reflect that this new PageId is in the allocated Frame of the Buffer Pool. The frame should have a pin count of 1, and it should call the pin method of the Clock replacement algorithm to notify it that a frame’s pin count went from 0 to 1 (the clock algorithm doesn’t care, but some replacement algorithms may). The address of the Page of Buffer Pool memory and the newly allocated PageId value are returned to the caller (see here for a refresher on using the C++ pair objects).

There are several cases to handle in implementing this method, but you can (and should) implement it in parts, starting with just the easiest case assuming there is a free frame of Buffer Pool, and the replacement algorithm does not need to be called to find one. Test this case, and then add more page allocation functionality incrementally.

On a successful allocatePage, the replacement object’s incrementGetAllocCount method should be called. This updates a count of the number of successful calls to getPage and allocatePage, which is used to compute statistics about buffer manager replacement policies. If allocatePage fails, or throws an exeption, it should not call the incrementGetAllocCount method (this was not a successful call to allocatePage).
deallocatePage removes a Page with a given PageId from the underlying file on disk. If the Page is in the buffer pool, it also needs to be removed from the pool and associated Frame cleared (this frame no longer stores a valid page). This method throws an exception if either the provided PageId is not valid (see the Diskmanager interface for methods that can detect this) or the page is still pinned in the buffer pool. As for all exceptions, it is important to not leave the database in an inconsistent state if the method is aborted (due to a thrown an exception). For example, deallocating a page on disk but then aborting because the page is pinned will result in a Page in the buffer pool staying valid even though it no longer exists on disk. The replacement object’s freeFrame method should be called.
getPage takes a PageId, pins the page, and returns a pointer to the Page of Buffer Pool storing the Page data. Your implementation will need to handle two cases: the page is already in the pool, or the page is not in the pool. The latter scenario will require allocating a frame in the buffer pool and retrieving the page from disk. getPage throws exceptions if the PageId is invalid (does not exist on disk) or if there is not sufficient space in the Buffer Pool to store the requested page. getPage increments the pin count associated with the page. If getPage causes the pin count to go from 0 to 1, the pin method of the replacement object should be called to notify the replacement algorithm.

On a successful getPage, the replacement object’s incrementGetAllocCount method should be called. This updates a count of the number of successful calls to getPage and allocatePage, which is used to compute statistics about buffer manager replacement policies. If getPage fails, or throws an exeption, it should not call the incrementGetAllocCount method (this was not a successful call to getPage).

This method has several cases to handle so you may want to implement one functionality at a time and test as you go. If this method throws an exception, be sure that any partial changes it has made to Buffer Manager state are cleaned-up before it is thrown. It may call _allocateFrame if the requested page is not in the Buffer Pool.
releasePage is the complement to getPage. It unpins a page in the buffer pool (but does not remove it). It may also need to update other metadata - the dirty parameter indicates if the page was modified by the upper layer. If the pin count for the page goes to 0, the unpin method of the replacement object should be called to notify the replacment algorithm (in clock replacement, the Page’s refbit should be set when the pin count reaches 0). This method may throw exceptions.
setDirty takes a PageId and sets the dirty bit of the Frame associated with this page. This method throws an exception if there is no page with a matching PageId in the Buffer Pool.
flushPage takes a PageId and if it is dirty, writes its contents to disk using the DiskManager interface. The Page should no longer be dirty after the write. This method may result in exceptions, some of which are thrown by calls to the DiskManager and need to pass through.
_allocateFrame is a private helper function that may be called by getPage and allocatePage to find a frame in the Buffer to store a Page not currently in the buffer pool using the Clock Page Replacement algorithm. The clock algorithm is implemented through the replacement_pol defined in the bm_policies.[h,cpp] This method returns the FrameId value of the frame in the Buffer Pool that it allocates. The returned FrameId value is the index into the Buffer Pool of the specific frame it allocates. You may add more private helper methods for good modular design.

The Buffer Manager also has two interface functions for higher-level layers to create and delete files on disk (these also show examples of how the BufferManger invokes methods of the DiskManager).

createFile: is called by a higher level to create a new file in the DB (this method is implemented for you).
removeFile: is called by a higher level to remove a file from the DB. This method is partially implemented for you, but you need to complete its implementation to remove all state associated with pages of the deleted file from the Buffer Pool. All of the file’s pages must be unpinned for this operation to succeed, and it throws a PagePinnedBufMgr exception if this is not the case.

You may add additional private helper methods or functions for good modular design but you may not modify the existing public interface (do not add new public methods or alter parameters/return values of existing methods).

There are a several BufferManager methods that are helpful for debugging that have been implemented for you. You should read all of these before beginning so that you can make good use of them when your program is not working.

Clock

The BufferManager has a data member, replacement_pol, whose type is derived from the ReplacementPolicy class. These derived classes (defined in bm_policies.cpp) implement different buffer manager replacement algorithms. With the starting point code you are given an implementation of the Random class that implements a random replacement policy.

The BufferManager makes calls to the replacement object:

When a page of Buffer Pool memory needs to be allocated as part of a getPage or allocatePage request to the buffer manager.
When a page of Buffer Pool memory is deallocated on a deallocatePage request to the buffer manager.
When a page’s pin count goes from 0 to 1, or from 1 to 0, the buffer manager notifies the replacement policy. Some replacement policies may do something when pages go from being unpinned to pinned (0 to 1) or from pinned to unpined (1 to 0), while others may not.

You will implement the Clock class in bm_policies.[h,cpp] that implements the clock replacement algorithm (see Clock Replacement Algorithm for details about the algorithm to implement).

All classes derived from Replacement Policy have a data field that points to the BufferManager’s frame table, and some fields that keep track of statistics about the replacement policy. These should be updated in class specific Clock method functions.

The Clock algorithm needs two pieces of additional buffer pool state: a reference bit associated with each page of buffer pool memory; and the current value of the clock hand.

The methods to implement include:

Clock: constructor initializes data members:
- clock_hand: initialize to 0
- ref_table: initialize all to 0
~Clock: cleans up any allocated state.

replace: implements the Clock replacement algorithm to find a frame an available Frame for the buffer manager (part of handling a getPage or allocatePage request). If no replacement frames are available, this method throws a InsufficientSpaceBufMgr exception if all pages in the buffer pool are pinned.

The replace method just finds the Frame to replace returns its FrameId to the BufferManager method that called it. The calling method in the BufferManager is responsible for preparing the frame to be replaced and replacinging it. This includes checking if the Frame currently stores a valid and dirty Page and if so handling this case approriately before replacing it with a different Page (BufferManager code performs the steps in with the dotted box around them in Fig. 2 ).

This method needs to update some of the replacement-specific statistics (defined in the struct ReplacementStats in bufmgr.h): rep_calls: number of times the replace function has been called. avg_frames_checked: the average number of frames checked before finding a replacement. This is an approximation of a true average keeping only a single value. The first average computed is the number of frames checked. Subsequent average values should be computing using the following formula:

    ((current avg) x (current num replace calls)) + num checked this call
 = ---------------------------------------------------------------------
                     (current num replace calls + 1)

Make sure you are using double aritmetic for multiplication and division operations, and don’t worry about loss of precision for the numerator, but make sure to check that you are not dividing by 0 (if rep_calls + 1 is 0, you are wrapping around the number of values, then start the running average all over from scratch).

_advanceClock: a private helper function for replace
pin: called by higher-level BufferManager functions when a page’s pin count goes from 0 to 1. The Clock algorithm doesn’t need to do anything in this case (but some replacement policies may).
unpin: called by higher-level BufferManager functions when a page’s pin count goes from 1 to 0. The Clock algorithm should set the reference bit on the associated page.
freeFrame: called when a frame is invalidated by the buffer manager. Add (push) this frame to the free list. Invalid frames should be selected for replacement before any valid pages with cleared ref bits are.

printFrame: for debugging: print only clock-specific meta-data associated with the frame (the ref_bit value)
printStats: prints out statistics about the clock algorithm (this is implemented for you, but some of the other Clock methods need to update some of the stats field values (defined in the struct ReplacementStats in bufmgr.h).

Clock Replacement Algorithm

You should implement the Clock algorithm exactly as we described in class, with one optimization, which is that if there are any invalid frames, those should be chosen to replace before any valid frame is selected for replacement.

To implement this optimization, your Clock impelmentation should make use of the free frame list in the ReplacementObject base class for storing invalid Frames (push Frames when they become invalid, and pop off Frames to handle replace calls). Figure Figure 2 shows the control flow of the optimized Clock algorithm

Figure 2. Optimized Clock Page Replacement Algorithm: showing the main steps taken to find a replacement Page (note: the stopping condition on a failure is not shown).

If there are no invalid Frames available for replacement on the free list, then the algorithm behaves exactly how it was described in class. Briefly, the clock algorithm logically organizes the Buffer Pool pages in a circular list. The clock hand "points" to the current frame (it is the value of the FrameId of the current frame) under consideration for replacement. The clock hand is incremented in a clockwise, circular, fashion around the Frames in the circular list as the algorithm proceeds in its search for either a page to replace or a free frame to use.

Buffer Pool frame organized as a circular array

clock circular array

The main clock part of the algorithm should be invoked whenever there are no invalid frames that can be used to satisfy a request for a Frame from the buffer manager (may be part of it handling a getPage or allocatePage requests).

If the page being evicted is dirty (i.e., it has been modified), the page needs to first be written to disk.

If a replacement is found, the Frame’s metadata needs to be reset before it is returned to the caller for use. If a replacement is not found, an exception is thrown.

Exceptions

In some methods your calls to methods in the DiskManager may result in exceptions being thrown by that layer (these have the suffice DskMgr). In some cases, you need to catch and handle these exceptions; in other cases, you may need to let the exception pass through to the caller (i.e., do nothing) to handle. In certain situations you may need to throw a new SwatDB Exception from the Buffer Manger (suffix BufMgr) layer in response to error handling.

For information about how to throw and catch different SwatDB exception objects, look at the Exceptions Section of the SwatDB information page. You will need to think carefully about the cause of these exceptions in order to know how to handle them. It is helpful to answer the question: who is responsible for the exception? For example, if the PageId provided in the function call is not on disk, the exception thrown by a call to the DiskManager is not the responsibility of the buffer manager and should instead be passed on to the calling layer of the DBMS. However, in some cases when a lower-level exception should be passed on up, your code may need to catch the exception, clean-up some partial internal state changes it made, and then re-throw it. See the documentation above for an example of how to do this.

Lab Requirements

In addition to correctly implementing parts of the BufferManager, Clock, and BufferMap classes listed above, and adding code to test your implementation, you should also:

Declare and use variables of the types defined in swatdb_types.h as opposed to their underlying type definition. Also use constants and enum types defined in this file - they help make the code more readable. For example, if a method returns a FrameId, declare a variable of type FrameId rather than std:uint32_t or int to store its return value:
```
FrameId frame_num;
PageId  pg_id;
// some code that give pg_pid a value
frame_num = buf_map->get(pg_id);
```
Use good C++ code design, and use good modular design in your solution. This includes using defined constants and types.
Ensure you code is robust to errors, in particular, be sure to test for error handling for exceptions that should be thrown and caught by the buffer manager.
Ensure your code is free of valgrind errors.
Make sure your code is well-commented, and there is no line wrapping. (See our C++ Style guide link from the Handy Links section.
Your submitted code should have all of our TODO comments removed. As you implement a TODO, remove it. These are also helpful to find parts of the given code that you need to implement.

Testing your code

There are several test files in the starting point code, most use the same unit tests framework you used in CS35, and test various buffer manager functionality:

checkpt.cpp
unittest.cpp
replacementtests.cpp
clocktests.cpp
performancetests.cpp

There is aso a programatic interface for testing buffer manager. This is similar to the way in which SwatDB would be deployed to run:

sandbox.cpp: this one is a programtic interface for testing buffer manager.

You will want to use all of them to verify you program is working correctly. sandbox.cpp and checkpt.cpp are useful in the early parts of your implementation.

unit tests

The unittest.cpp and checkpt.cpp implement the main Buffer Manager layer test code using the unit tests framework from CS35. The replacementtests.cpp, and clocktests.cpp unit tests test the replacement algorithm part of the Buffer manager, and performancetests.cpp runs tests to compare your Clock implementation to the Random replacement algorithm that we give you with the starting point code.

You can add additional tests to unittest.cpp by following the examples in that file (see the studentTests SUITE near the bottom of unittest.cpp).

checkpt.cpp has fewer tests, and tests partial functionality of some methods (allocatePage, for example), and is likely a better first start for running unit tests to test your code.
unittest.cpp contains a fairly complete set of test functions for core buffer manager functionality, and you may want to use it later in your testing as most tests will fail until you have implemented a fair amount of functionality.
replacementtests.cpp contains some tests for basic functionality of replacement algorithm interface functions.
clock.cpp contains some tests to specifically test for correct clock algorithm implemenation.

performancetests.cpp contains some performance tests of Clock and the Random replacement algorithms (Random is given to you with the starting point code). In addition to seeing some performance comparisions of two replacement algorithms, this is a good way to see if you are correctly updating buffer manager statistics in your solution.

All tests of performancetests.cpp will complete successfully regardless of if you have implemented Clock or full buffer manager functionality (there are no tests for correctness in the performance unit tests). Use this test program to test your statistics methods (do the results make sense? do any of the values seem really wrong?…). Look at the comments with the test suites to get a sense of what you might expect.

To run unit test programs:

# run all of the unittest test suites
./unittests
Success: 16 tests passed.
Test time: 0.40 seconds.

# run all of the checkpt test suites
./checkpt

# or you can run individual test suites alone using -s testSuiteName
./unittests -s allocatePage   # run just allocatePage test suite
Success: 1 tests passed.
Test time: 0.02 seconds.

./checkpt -s allocatePageCkPt

# to list the test suites names run with -h
./unittests -h
 Usage: ./unittests -s <suite_name> -h help
 Available Suites: allocatePage, deallocatePage, releasePage,
  setDirtyAndFlushPage, getPage, clockReplacement, removeFile, studentTests

./checkpt -h
 Usage: ./checkpt -s <suite_name> -h help
 Available Suites: allocatePageCkPt, releasePageCkPt, setDirtyAndFlushPageCkPt,
 getPageCkPt

In unittest.cpp there is an empty test suite into which you can add more test code to test your solution:

/*
 * An empty SUITE for students to add additional tests. Students may add tests
 * to other existing SUITE as well.
 */
SUITE(studentTests){
  //TODO: add tests

}

sandbox test program

sandbox.cpp is a more programatic way of designing test code. It includes an example of calling some of the BufferManager debugging functions that are already implemented for you in the starting point of bufmgr.cpp.

It also includes two commented out test functions that are implementations of two tests from unittests.cpp — one test for allocating pages and another for testing the clock replacement algorithm. As you add functionality to the Buffer Manager, you can uncomment the code in main that calls these tests to try them out. You can also add any other test functions you would like to this program to test your code. Follow the design of the tests functions in this program to add more test code.

Read the code in this file to understand what it is doing, and add your own tests that follow this model to test a sequence of operations on your buffer manager.

cleaning up corrupted files

SwatDB maintains several files to allow for persistent storage of data. While that is not a central feature of this lab, a consequence of a program crash is that temporary files do not get properly cleaned up since the DBMS did not shutdown cleanly. This can cause problems when you try to rerun the program, so you will need to clean this up. Use the two options below:

./cleanup.sh

make clean     # or make clean also runs cleanup.sh then just re-build
make

Tips and Hints

General Tips

The following are some tips to help you implement the Buffer Manager:

We suggest starting out with the sandbox.cpp test program and testing some very simple starting functionality. After that, use whichever testing framework is easier. It may require less code writing to add tests to unittests.cpp than to sandbox.cpp, so we recommend eventually moving to use the unittests.cpp framework.
If your tests fail with a crash, run the cleanup.sh script to clean-up any SwatDB files that may be left around (they did not get correctly deleted because your test program crashed):
```
./cleanup.sh
```
If this doesn’t run, make sure it is executable by running ls -l to list file permissions:
```
ls -l cleanup.sh
  -rwx------ 1 you users  DATE cleanup.sh*
```
If it doesn’t list rwx as the permissions, you can change them with the chmod command:
```
chmod 700 cleanup.sh
ls -l cleanup.sh
  -rwx------ 1 you users  DATE cleanup.sh*
```
Make use of some of the BufferManager, and ReplacementPolicy print methods to see Buffer Manager state in either the test program sandbox.cpp (see the printTutorial function for an example), or you can call functions from within gdb using the call command:

  # assume there is a variable buf_mgr that points to the BufferManager obj:
  (gdb) call  buf_mgr->printBufferState();

  # or from a breakpoint inside a method, you can use this:
  (gdb) call  this->printBufferState();

Run unittests often to see which you are passing and which fail. This will help you find missing functionality in your code, and some missing cases. NOTE: these tests are not necessarily complete, so you will want to add some more tests here to really stress test your solution (our grading tests will do this).
Implement and test incrementally.

Suggested Order

Here is a suggestion for an order in which to implement Buffer Manger functionality:

Implement BufferMap functionality first
Implement BufferManger::allocatePage, but just for the case that the buffer pool has space (without the full clock replacement policy yet). You can call and test from sandbox.cpp by uncommenting the call to the allocatePageTest() in the main function. You will need to implement Clock methods with a very simple replace implementation that just handles the case when there are invalid Frames to allocate (returns a Frame from the free list). You will go back later and fully implement the clock replacement algorithm in the replace method, but do not do that right now. Also, note that the BufferManager data field replacement_pol is initialized to point to a Clock object in the BufferManager constructor (see Fig. 1 illustrating the BufferManager data fields). Note that the Clock object has many other data members that are not shown in that figure that are inherited from the ReplacementPolicy class, including the free list of pages.

Use the code in the the allocatePageTest function to add and test more functionality to allocatePage.
Implement setDirty.
Implement just some getPage functionality, without triggering the full clock replacement algorithm yet. You can use the unit tests or add some test functions to sandbox.cpp to test it. Try calling allocatePage followed by getPage on the same PageId and check its pin count, for example.
Implement flushPage, with and without dirty set.
Implement releasePage, with and without dirty set.
Implement the BufferManager destructor.
Implement deallocatePage.
Implement the clock replacement algorithm, and add more functionality to allocatePage and getPage to make use of it.
Implement removeFile and all remaining functionality and error handling.
Implement any remaining functionality, methods, error handling, etc.
Go back and implement exceptions you skipped along the way. Be sure that you stress test these to ensure your code is using them properly.
- Refer to Wednesday in-lab code examples for C++, gdb, and valgrind reminders.
- Remember the & operator returns the address of its argument (this is C-style operator, not & used to specify reference parameter types in C++). Its argument must be an lvalue (a storage location, such as the name of a variable or an array bucket). For example, to get the address of the 3rd bucket in and array of ints:
  int array[20];
  you would use the & operator like this (in this example I’m assigning its value to an int * variable):
  int *ptr; ptr = &array[3]

Submitting your lab

Review the lab deliverables to ensure you have completed all of your work. Before the due date, push your solution to github from one of your local repos to the GitHub remote repo.

From your local repo (in your ~/cs44/labs/Lab2-userID1-userID2 subdirectory)

make clean
git add *.h *.cpp
git commit -m "my correct and well commented solution for grading"
git push

Never do git add * or git add ./: this is terrible practice!

Verify that the results appear (e.g., by viewing the the repository on CS44-s25). You will receive deductions for submitting code that does not run or repos with merge conflicts. Also note that the time stamp of your final submission is used to verify late days, so please do not update your repo until after the late period has ended.

If that doesn’t work, take a look at the "Troubleshooting" section of the Using git for CS44 labs and the Using git pages. At this point, you should submit the required Lab 2 Questionnaire (each lab partner must do this).

Handy References

Examples

Look at C++ examples from in-lab week 1 and week 2

SwatDB

Information about SwatDB
SwatDB Code Documentation

C++ programming

Some C++ Programming Resources and Links including the C++ Style Guide
C++ programming tools compiling, linking, debugging C++
gdb and valgrind from Dive into Systems, and my (very similar) gdb and valgrind guides.
C references in Dive into Systems (some useful for C++ programming too) Chapter 2: C pointers, command line arguments, C debugging tools (valgrind, gdb for C)

Unix

Appendix 2: Using Unix from Dive into Systems
my CS help pages (Unix tools, programming links)
CS Department help pages

Git

Using git for CS44 labs
Using Git detailed Git guide

CS44 Lab 2: SwatDB Buffer Manager

Due Date

Overview

Lab Goals

Starting Point Code

Lab 2 Files

Deliverables

Checkpoint

SwatDB

Lab Details

What to implement

Frame

BufferMap

BufferManager

Clock

Clock Replacement Algorithm

Exceptions

Lab Requirements

Testing your code

unit tests

To run unit test programs:

sandbox test program

cleaning up corrupted files

Tips and Hints

General Tips

Suggested Order

Submitting your lab

Handy References

Examples

SwatDB

C++ programming

Unix

Git