14.1 The Block Store

The notion of external memory includes a large number of possible different devices, each of which has its own block size and is accessed with its 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 BlockStore. A BlockStore stores a collection of memory blocks, each of size $B$. Each block is uniquely identified by its integer index. A BlockStore supports these operations:

1. $\ensuremath{\mathrm{read\_block}(\ensuremath{\mathit{i}})}$: Return the contents of the block whose index is $\ensuremath{\ensuremath{\mathit{i}}}$.

2. $\ensuremath{\mathrm{write\_block}(\ensuremath{\mathit{i}},\ensuremath{\mathit{b}})}$: Write contents of $\ensuremath{\ensuremath{\mathit{b}}}$ to the block whose index is $\ensuremath{\ensuremath{\mathit{i}}}$.

3. $\ensuremath{\mathrm{place\_block}(\ensuremath{\mathit{b}})}$: Return a new index and store the contents of $\ensuremath{\ensuremath{\mathit{b}}}$ at this index.

4. $\ensuremath{\mathrm{free\_block}(\ensuremath{\mathit{i}})}$: Free the block whose index is $\ensuremath{\ensuremath{\mathit{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 BlockStore is to imagine it as storing a file on disk that is partitioned into blocks, each containing $B$ bytes. In this way, $\ensuremath{\mathrm{read\_block}(\ensuremath{\mathit{i}})}$ and $\ensuremath{\mathrm{write\_block}(\ensuremath{\mathit{i}},\ensuremath{\mathit{b}})}$ simply read and write bytes $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}B,\ldots,(\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}+1)B-1$ of this file. In addition, a simple BlockStore could keep a free list of blocks that are available for use. Blocks freed with $\ensuremath{\mathrm{free\_block}(\ensuremath{\mathit{i}})}$ are added to the free list. In this way, $\ensuremath{\mathrm{place\_block}(\ensuremath{\mathit{b}})}$ can use a block from the free list or, if none is available, append a new block to the end of the file.