14.1 The Block Store

The notion of external memory includes a large number of possible different devices, each of which has their own block size and is accessed with their own collection of system calls. To simplify the exposition of this chapter so that we can focus on the common ideas, we encapsulate external memory devices with an object called a $\mathtt{BlockStore}$. A $\mathtt{BlockStore}$ stores a collection of memory blocks, each of size $B$. Each block is uniquely identified by its integer index. A $\mathtt{BlockStore}$ supports these operations:

1. $\mathtt{readBlock(i)}$: Return the contents of the block whose index is $\mathtt{i}$.

2. $\mathtt{writeBlock(i,b)}$: Write contents of $\mathtt{b}$ to the block whose index is $\mathtt{i}$.

3. $\mathtt{placeBlock(b)}$: Return a new index and store the contents of $\mathtt{b}$ at this index.

4. $\mathtt{freeBlock(i)}$: Free the block whose index is $\mathtt{i}$. This indicates that the contents of this block are no longer used so the external memory allocated by this block may be reused.

The easiest way to imagine a $\mathtt{BlockStore}$ is to think of it as storing a file on disk that is partitioned into blocks, each containing $B$ bytes. Then $\mathtt{readBlock(i)}$ and $\mathtt{writeBlock(i,b)}$ simply read and write bytes $\ensuremath{\mathtt{i}}B,\ldots,(\ensuremath{\mathtt{i}}+1)B-1$ of this file. In addition, a simple $\mathtt{BlockStore}$ could keep a free list of blocks that are available for use. Blocks freed with $\mathtt{freeBlock(i)}$ are added to the free list. In this way, $\mathtt{placeBlock(b)}$ can use a block from the free list or, if none is available, can append a new block to the end of the file.