[SOLVED] cache file system algorithm README

README

README

Logistics

Deadlines Part 1: Tuesday, May 1st 11:59 PM Part 2: Wednesday, May 9th 11:59 PM (Last
day of classes)

WARNING: Even though Part 1 is due Tuesday, May 1, you will likely not finish Part 2
unless you start before before May 1st.

Project Overview

Treedisk may be unlike any filesystem you have learned about in class, so we have provided
slides on the course webpage (found in the Schedule section, but a quick link to the slides is
this: http://www.cs.cornell.edu/courses/cs4410/2018sp/schedule/slides/block-stores.pdf). We
HIGHLY RECOMMEND that you look at these slides ASAP. These slides go over the details of
treedisk, layered filesystems, and A4.

This directory contains an implementation of a layered block store. A block store is much like a
file, except that the unit of access is a block, not a byte. Each block store has the following
simple interface:

#include block_store.h

Defines BLOCK_SIZE, the size of a block.Also has typedefs

for:

block_store_t: a block store interface

block_t:a block of size BLOCK_SIZE

block_no: an offset into a block store

int nblocks = (*block_store->nblocks)(block_store_t *block_store);

Returns the size of the block store in #blocks, or -1 if error.

int (*block_store->read)(block_store, block_no offset, OUT block_t *block);

Reads the block at the given offset.Return 0 upon success,

-1 upon error.

int (*block_store->write)(block_store, block_no offset, IN block_t *block);

Writes the block at the given offset.Some block stores support

automatically growing.Returns -1 upon error.

int (*block_store->setsize)(block_store, block_no size);

Set the size of the block store to size blocks.May either

truncate or grow the underlying block store.Not all sizes

may be supported.Returns the old size, or -1 upon error.

void (*block_store->destroy)(block_store);

http://www.cs.cornell.edu/courses/cs4410/2018sp/schedule/slides/block-stores.pdf

To create a block store, you need the block stores init function. The simplest two block stores
are the following:

For example, if you want caching, you can invoke (once you implement cachedisk):

This adds a caching layer to below with nblocks of cache, pointed to by blocks, but they use
different algorithms. So if you run:

then higher is a block store that stores its blocks in file and caches its blocks in the given
(write-through) cache. One can still read and write lower, by-passing the cache (but particularly
writing would be dangerousthe cache would not reflect the latest content). If you like, you can
dump caching statistics:

Theres a disk layer that does nothing but count operations:

You can dump the stats using:

A handy debugging tool is:

Clean up the block store.In case of a low-level storage (an

actual disk), will typically leave the blocks intact so it can

be reloaded again.

block_store_t *disk_init(char *file_name, block_no nblocks);

Implements a block store with nblocks blocks in the POSIX

file file_name.The file simply stores the list of blocks.

block_store_t *ramdisk_init(block_t *blocks, block_no nblocks);

Implements a block store with nblocks blocks in the provided

memory, pointed to by blocks.

block_store_t *cachedisk_init(block_store_t *below, block_t *blocks,

block_no nblocks);

block_store_t *lower = disk_init(file, 100);

block_t cache[10];

block_store_t *higher = cachedisk_init(lower, cache, 10);

void cachedisk_dump_stats(block_store_t *this_bs);

block_store_t *higher = statdisk_init(lower);

void statdisk_dump_stats(block_store_t *this_bs);

Another useful layer is the check disk that checks if whats read is what has been written:

One can also virtualize the underlying block store, creating multiple virtual block stores on a
single underlying block store. Currently, there is one such module available:

For example:

This creates two virtual block stores file0 (associated with inode 0) and file1 (associated with
inode 1) on top of a single cached block store stored in filesystem.

A trace disk is a top-level block store (does not support layers on top of it) that generates a
load on the underlying layers. It is supposed to run over a treedisk-virtualized block store. The
load is read from a file that is given as the first argument. The file contains entries of the
following form:

There are 4 supported commands:

block_store_t *debugdisk_init(block_store_t *below, char *descr);

This prints any invocation to and result from nblocks(), read(),

and write() along with the string descr.

block_store_t *checkdisk_init(block_store_t *below, char *descr);

void treedisk_create(block_store_t *below, unsigned int n_inodes)

Create a file system on the block store below.The number of inodes

(virtual block stores) is n_inodes.Each such virtual block store is

initially empty (0 blocks), but grows dynamically as blocks are

written.

int treedisk_check(block_store_t *below)

Checks the integrity of a tree virtual block store.Returns

0 if the block store is broken, and 1 if its in good shape.

Useful for testing.

block_store_t *treedisk_init(block_store_t *below, unsigned int inode_no)

Return a block store interface to the virtual block store identified

by the inode number.

block_t cache[10];

block_store_t *disk = disk_init(filesystem, 100);

block_store_t *cdisk = cachedisk_init(disk, cache, 10);

treedisk_create(cdisk, 2);

block_store_t *file0 = treedisk_init(cdisk, 0);

block_store_t *file1 = treedisk_init(cdisk, 1);

command:inode-number:block-number

To use a tracedisk, run

A tracedisk automatically adds treedisk layers as needed for each inode, and also adds a
checkdisk layer for each to check that the content read is the same as the last content written.

TODO

Your project to-do list consists of the following:

1) read README to learn about the available layers. stay up to date with the a4 FAQ on piazza.

2) run make in order to compile the sources. This should generate an executable called trace
that can be used for testing your software. The syntax of trace is as follows:

./trace [trace-file [cache-size]]

The default trace-file is trace.txt, and we have included an example. The optional cache-size
lets you set the size of the cache.

3) run ./trace. The output will likely look like this:

4) look in treedisk.c and look for the function treedisk_setsize(). It is currently incomplete and
causes the error that you saw in the previous step. Implement the missing code. You only need
to support setting the size to 0. If you run ./trace again, the output should look more like:

R: read a block of the given inode

W: write a block of the given inode

S: set the size of the given inode

N: check the size of the given inode

block_store_t *tracedisk_init(block_store_t *below, char *trace, unsigned

int n_inodes);

trace specifies the name of the trace file

n_inodes specifies the number of inodes in the underlying file

blocksize:512

refs/block: 128

!!TDERR: setsize not yet supported

!!ERROR: tracedisk_run: setsize(1, 0) failed

!!CHKSIZE 10: nblocks 1: 0 != 2

!$STAT: #nnblocks:0

!$STAT: #nsetsize:0

!$STAT: #nread: 32

!$STAT: #nwrite:20

5) look in cachedisk.c. It is supposed to cache blocks, but currently it simply forwards read and
write operations to the layer below. You are to implement a caching algorithm. You can use any
algorithm that appeared in the literature (LRU, LFU, MRU, ) or design your own. Note that it is
supposed to be a write-through cache: the write operation cannot buffer writes until a later
time.

6) we are going to run a contest! You are to provide your own version of the file trace.txt. We
will run everybodys trace against everybodys cache layer. In particular, we will run ./trace with
your treedisk and caching layer (configured with 16 blocks) against everybodys trace, and count
up the total number of read operations that your caching layer performs. We will rank
contestants by this total.

Note that you will get disqualified if your treedisk layer or caching layer does not work. You will
also get disqualified if you cache any user data in a place other than the memory that is passed
to the caching layer, or if you change the layout of the treedisk file system. The outcome of this
contest does not count toward your Project gradehowever, there will be prizes.

Your trace.txt file has the following limitations:

it can have at most 10,000 lines/commands

inode numbers must range between 0 and 127 inclusive

block numbers must range between 0 and (1<<27)-1 inclusiveTo win, you can use the following strategies or a combination: Things to submit Submit the following files on CMS, but be sure you use your git repository wisely so as toprotect your self against any unexpected life or scholastic events.Part 1 1. trace.txt– A valid trace file. Just overwrite the original trace.txt2. alias.txt — the name by which you shall be known for the contestblocksize:512refs/block: 128!$STAT: #nnblocks:0!$STAT: #nsetsize:0!$STAT: #nread: 36!$STAT: #nwrite:24- defensive approach: modify treedisk and/or cachedisk so asto minimize the number of read operations below.- offensive approach: create a trace.txt that makes it veryhard for the underlying layers (except yours of course) tocache anything.Part 2 1. treedisk.c2. cachedisk.c3. trace.txt4. alias.txtREADMELogisticsProject OverviewTODOThings to submitPart 1Part 2