Improve explanation of fifos.

[aple.git] / LVM.m4

TITLE(«

        Who the heck is General Failure, and why is he reading my disk? -- Unknown

», __file__)

OVERVIEW(«

The idea of Logical Volume Management is to decouple data and
storage. This offers great flexibility in managing storage and reduces
server downtimes because the storage may be replaced while file
systems are mounted read-write and applications are actively using
them. This chapter provides an introduction to the Linux block layer
and LVM. Subsequent sections cover selected device mapper targets.

»)

SECTION(«The Linux Block Layer»)

<p> The main task of LVM is the management of block devices, so it is
natural to start an introduction to LVM with a section on the Linux
block layer, which is the central component in the Linux kernel
for the handling of persistent storage devices. The mission of the
block layer is to provide a uniform interface to different types
of storage devices. The obvious in-kernel users of this interface
are the file systems and the swap subsystem. But also <em> stacking
device drivers </em> like LVM, Bcache and MD access block devices
through this interface to create virtual block devices from other block
devices. Some user space programs (<code>fdisk, dd, mkfs, ...</code>)
also need to access block devices. The block layer allows them to
perform their task in a well-defined and uniform manner through
block-special device files. </p>

<p> The userspace programs and the in-kernel users interact with the block
layer by sending read or write requests. A <em>bio</em> is the central
data structure that carries such requests within the kernel. Bios
may contain an arbitrary amount of data. They are given to the block
layer to be queued for subsequent handling. Often a bio has to travel
through a stack of block device drivers where each driver modifies
the bio and sends it on to the next driver. Typically, only the last
driver in the stack corresponds to a hardware device. </p>

<p> Besides requests to read or write data blocks, there are various other
bio requests that carry SCSI commands like FLUSH, FUA (Force Unit
Access), TRIM and UNMAP. FLUSH and FUA ensure that certain data hits
stable storage. FLUSH asks the the device to write out the contents of
its volatile write cache while a FUA request carries data that should
be written directly to the device, bypassing all caches. UNMAP/TRIM is
a SCSI/ATA command which is only relevant to SSDs. It is a promise of
the OS to not read the given range of blocks any more, so the device
is free to discard the contents and return arbitrary data on the
next read. This helps the device to level out the number of times
the flash storage cells are overwritten (<em>wear-leveling</em>),
which improves the durability of the device. </p>

<p> The first task of the block layer is to split incoming bios if
necessary to make them conform to the size limit or the alignment
requirements of the target device, and to batch and merge bios so that
they can be submitted as a unit for performance reasons. The thusly
processed bios then form an I/O request which is handed to an <em>
I/O scheduler </em> (also known as <em> elevator</em>). </p>

<p> Traditionally, the schedulers were designed for rotating disks.
They implemented a single request queue and reordered the queued
I/O requests with the aim to minimize disk seek times. The newer
multi-queue schedulers mq-deadline, kyber, and bfq (budget fair
queueing) aim to max out even the fastest devices. As implied by
the name "multi-queue", they implement several request queues,
the number of which depends on the hardware in use. This has become
necessary because modern storage hardware allows multiple requests
to be submitted in parallel from different CPUs. Moreover, with many
CPUs the locking overhead required to put a request into a queue
increases. Per-CPU queues allow for per-CPU locks, which decreases
queue lock contention. </p>

<p> We will take a look at some aspects of the Linux block layer and on
the various I/O schedulers. An exercise on loop devices enables the
reader to create block devices for testing. This will be handy in
the subsequent sections on LVM specific topics. </p>

EXERCISES()

<ul>

        <li> Run <code>find /dev -type b</code> to get the list of all block
        devices on your system. Explain which is which. </li>

        <li> Examine the files in <code>/sys/block/sda</code>, in
        particular <code>/sys/block/sda/stat</code>. Search the web for
        <code>Documentation/block/stat.txt</code> for the meaning of the
        numbers shown. Then run <code>iostat -xdh sda 1</code>. </li>

        <li> Examine the files in <code>/sys/block/sda/queue</code>. </li>

        <li> Find out how to determine the size of a block device. </li>

        <li> Figure out a way to identify the name of all block devices which
        correspond to SSDs (i.e., excluding any rotating disks). </li>

        <li> Run <code>lsblk</code> and discuss
        the output. Too easy? Run <code>lsblk -o
        KNAME,PHY-SEC,MIN-IO,OPT-IO,PHY-SEC,LOG-SEC,RQ-SIZE,ROTA,SCHED</code>
        </li>

        <li> What's the difference between a task scheduler and an I/O
        scheduler? </li>

        <li> Why are I/O schedulers also called elevators? </li>

        <li> How can one find out which I/O schedulers are supported on a
        system and which scheduler is active for a given block device? </li>

        <li> Is it possible (and safe) to change the I/O scheduler for a
        block device while it is in use? If so, how can this be done? </li>

        <li> The loop device driver of the Linux kernel allows privileged
        users to create a block device from a regular file stored on a file
        system.  The resulting block device is called a <em>loop</em> device.
        Create a 1G large temporary file containing only zeroes. Run a suitable
        <code>losetup(8)</code> command to create a loop device from the
        file. Create an XFS file system on the loop device and mount it. </li>

</ul>

HOMEWORK(«

<ul>
        <li> Come up with three different use cases for loop devices. </li>

        <li> Given a block device node in <code> /dev</code>, how can one
        tell that it is a loop device? </li>

        <li> Describe the connection between loop devices created by
        <code>losetup(8)</code> and the loopback device used for network
        connections from the machine to itself. </li>

</ul>
»)

define(«svg_disk», «
        <g
                fill="$5"
                stroke="black"
                stroke-width="1"
        >
        <ellipse
                cx="eval($1 + $3 / 2)"
                cy="eval($2 + $4)"
                rx="eval($3 / 2)"
                ry="eval($3 / 4)"
        />
        <rect
                x="$1"
                y="$2"
                width="$3"
                height="$4"
        />
        <rect
                x="eval($1 + 1)"
                y="eval($2 + $4 - 1)"
                width="eval($3 - 2)"
                height="2"
                stroke="$5"
        />
        <ellipse
                cx="eval($1 + $3 / 2)"
                cy="$2"
                rx="eval($3 / 2)"
                ry="eval($3 / 4)"
        />
        </g>
»)

SECTION(«Physical and Logical Volumes, Volume Groups»)

<p> Getting started with the Logical Volume Manager (LVM) requires to
get used to a minimal set of vocabulary. This section introduces
the words named in the title of the section, and a couple more.
The basic concepts of LVM are then described in terms of these words. </p>

<div>
define(lvm_width», «300»)
define(«lvm_height», «183»)
define(«lvm_margin», «10»)
define(«lvm_extent_size», «10»)
define(«lvm_extent», «
        <rect
                fill="$1"
                x="$2"
                y="$3"
                width="lvm_extent_size()"
                height="lvm_extent_size()"
                stroke="black"
                stroke-width="1"
        />
»)
dnl $1: color, $2: x, $3: y, $4: number of extents
define(«lvm_extents», «
        ifelse(«$4», «0», «», «
                lvm_extent(«$1», «$2», «$3»)
                lvm_extents(«$1», eval($2 + lvm_extent_size() + lvm_margin()),
                        «$3», eval($4 - 1))
        »)
»)
dnl $1: x, $2: y, $3: number of extents, $4: disk color, $5: extent color
define(«lvm_disk», «
        ifelse(eval(«$3» > 3), «1», «
                pushdef(«h», «eval(7 * lvm_extent_size())»)
                pushdef(«w», «eval(($3 + 1) * lvm_extent_size())»)
        », «
                pushdef(«h», «eval(3 * lvm_extent_size() + lvm_margin())»)
                pushdef(«w», «eval($3 * lvm_extent_size() * 2)»)
        »)
        svg_disk(«$1», «$2», «w()», «h()», «$4»)
        ifelse(eval(«$3» > 3), «1», «
                pushdef(«n1», eval(«$3» / 2))
                pushdef(«n2», eval(«$3» - n1()))
                lvm_extents(«$5»,
                        eval(«$1» + (w() - (2 * n1() - 1) * lvm_extent_size()) / 2),
                        eval(«$2» + h() / 2 - lvm_extent_size()), «n1()»)
                lvm_extents(«$5»,
                        eval(«$1» + (w() - (2 * n2() - 1) * lvm_extent_size()) / 2),
                        eval(«$2» + h() / 2 + 2 * lvm_extent_size()), «n2()»)
                popdef(«n1»)
                popdef(«n2»)
        », «
                lvm_extents(«$5»,
                        eval(«$1» + (w() - (2 * «$3» - 1) * lvm_extent_size()) / 2),
                        eval(«$2» + h() / 2), «$3»)
        »)
        popdef(«w»)
        popdef(«h»)
»)
<svg
        width="lvm_width()" height="lvm_height()"
        xmlns="http://www.w3.org/2000/svg"
        xmlns:xlink="http://www.w3.org/1999/xlink"
>
        <rect
                x=1
                y=1
                width="140"
                height="180"
                fill="green"
                rx="10"
                stroke-width="1"
                stroke="black"
        />
        lvm_disk(«20», «20», «2», «#666», «yellow»)
        lvm_disk(«10», «90», «4», «#666», «yellow»)
        lvm_disk(«70», «55», «5», «#666», «yellow»)
        <path
                d="
                        M 155 91
                        l 20 0
                        m 0 0
                        l -4 -3
                        l 0 6
                        l 4 -3
                        z
                "
                stroke-width="4"
                stroke="black"
                fill="black"
        />
        lvm_disk(«190», «22», «7», «#66f», «orange»)
        lvm_disk(«220», «130», «1», «#66f», «orange»)
</svg>
</div>

<p> A <em> Physical Volume</em> (PV, grey) is an arbitrary block device which
contains a certain metadata header (also known as <em>superblock</em>)
at the start. PVs can be partitions on a local hard disk or a SSD,
a soft- or hardware raid, or a loop device. LVM does not care.
The storage space on a physical volume is managed in units called <em>
Physical Extents </em> (PEs, yellow). The default PE size is 4M. </p>

<p> A <em>Volume Group</em> (VG, green) is a non-empty set of PVs with
a name and a unique ID assigned to it. A PV can but doesn't need to
be assigned to a VG. If it is, the ID of the associated VG is stored
in the metadata header of the PV. </p>

<p> A <em> Logical Volume</em> (LV, blue) is a named block device which is
provided by LVM. LVs are always associated with a VG and are stored
on that VG's PVs. Since LVs are normal block devices, file systems
of any type can be created on them, they can be used as swap storage,
etc. The chunks of a LV are managed as <em>Logical Extents</em> (LEs,
orange). Often the LE size equals the PE size.  For each LV there is
a mapping between the LEs of the LV and the PEs of the underlying
PVs. The PEs can spread multiple PVs. </p>

<p> VGs can be extended by adding additional PVs to it, or reduced by
removing unused devices, i.e., those with no PEs allocated on them. PEs
may be moved from one PV to another while the LVs are active. LVs
may be grown or shrunk. To grow a LV, there must be enough space
left in the VG. Growing a LV does not magically grow the file system
stored on it, however. To make use of the additional space, a second,
file system specific step is needed to tell the file system that it's
underlying block device (the LV) has grown. </p>

<p> The exercises of this section illustrate the basic LVM concepts
and the essential LVM commands. They ask the reader to create a VG
whose PVs are loop devices. This VG is used as a starting point in
subsequent chapters. </p>

EXERCISES()

<ul>

        <li> Create two 5G large loop devices <code>/dev/loop1</code>
        and <code>/dev/loop2</code>. Make them PVs by running
        <code>pvcreate</code>. Create a VG <code>tvg</code> (test volume group)
        from the two loop devices and two 3G large LVs named <code>tlv1</code>
        and <code>tlv2</code> on it. Run the <code>pvcreate, vgcreate</code>,
        and <code>lvcreate</code> commands with <code>-v</code> to activate
        verbose output and try to understand each output line. </li>

        <li> Run <code>pvs, vgs, lvs, lvdisplay, pvdisplay</code> and examine
        the output. </li>

        <li> Run <code>lvdisplay -m</code> to examine the mapping of logical
        extents to PVs and physical extents. </li>

        <li> Run <code>pvs --segments -o+lv_name,seg_start_pe,segtype</code>
        to see the map between physical extents and logical extents. </li>

</ul>

HOMEWORK(«

In the above scenario (two LVs in a VG consisting of two PVs), how
can you tell whether both PVs are actually used? Remove the LVs
with <code>lvremove</code>. Recreate them, but this time use the
<code>--stripes 2</code> option to <code>lvcreate</code>. Explain
what this option does and confirm with a suitable command.

»)

SECTION(«Device Mapper and Device Mapper Targets»)

<p> The kernel part of the Logical Volume Manager (LVM) is called
<em>device mapper</em> (DM), which is a generic framework to map
one block device to another. Applications talk to the Device Mapper
via the <em>libdevmapper</em> library, which issues requests
to the <code>/dev/mapper/control</code> character device using the
<code>ioctl(2)</code> system call. The device mapper is also accessible
from scripts via the <code>dmsetup(8)</code> tool. </p>

<p> A DM target represents one particular mapping type for ranges
of LEs. Several DM targets exist, each of which which creates and
maintains block devices with certain characteristics. In this section
we take a look at the <code>dmsetup</code> tool and the relatively
simple <em>mirror</em> target. Subsequent sections cover other targets
in more detail. </p>

EXERCISES()

<ul>

        <li> Run <code>dmsetup targets</code> to list all targets supported
        by the currently running kernel. Explain their purpose and typical
        use cases. </li>

        <li> Starting with the <code>tvg</code> VG, remove <code>tlv2</code>.
        Convince yourself by running <code>vgs</code> that <code>tvg</code>
        is 10G large, with 3G being in use. Run <code>pvmove
        /dev/loop1</code> to move the used PEs of <code>/dev/loop1</code>
        to <code>/dev/loop2</code>. After the command completes, run
        <code>pvs</code> again to see that <code>/dev/loop1</code> has no
        more PEs in use. </li>

        <li> Create a third 5G loop device <code>/dev/loop3</code>, make it a
        PV and extend the VG with <code>vgextend tvg /dev/loop3</code>. Remove
        <code>tlv1</code>. Now the LEs of <code>tlv2</code> fit on any
        of the three PVs.  Come up with a command which moves them to
        <code>/dev/loop3</code>. </li>

        <li> The first two loop devices are both unused. Remove them from
        the VG with <code>vgreduce -a</code>. Why are they still listed in
        the <code>pvs</code> output? What can be done about that? </li>

</ul>

HOMEWORK(«

As advertised in the introduction, LVM allows the administrator to
replace the underlying storage of a file system online. This is done
by running a suitable <code>pvmove(8)</code> command to move all PEs of
one PV to different PVs in the same VG.

<ul>

        <li> Explain the mapping type of dm-mirror. </li>

        <li> The traditional way to mirror the contents of two or more block
        devices is software raid 1, also known as <em>md raid1</em> ("md"
        is short for multi-disk). Explain the difference between md raid1,
        the dm-raid target which supports raid1 and other raid levels, and
        the dm-mirror target. </li>

        <li> Guess how <code>pvmove</code> is implemented on top of
        dm-mirror. Verify your guess by reading the "NOTES" section of the
        <code>pvmove(8)</code> man page. </li>

</ul>
»)

SECTION(«LVM Snapshots»)

<p> LVM snapshots are based on the CoW optimization strategy described
earlier in the chapter on <a href="./Unix_Concepts.html#processes">Unix
Concepts</a>. Creating a snapshot means to create a CoW table of the
given size. Just before a LE of a snapshotted LV is about to be written
to, its contents are copied to a free slot in the CoW table. This
preserves an old version of the LV, the snapshot, which can later be
reconstructed by overlaying the CoW table atop the LV. </p>

<p> Snapshots can be taken from a LV which contains a mounted file system,
while applications are actively modifying files. Without coordination
between the file system and LVM, the file system most likely has memory
buffers scheduled for writeback. These outstanding writes did not make
it to the snapshot, so one can not expect the snapshot to contain a
consistent file system image. Instead, it is in a similar state as a
regular device after an unclean shutdown. This is not a problem for
XFS and EXT4, as both are <em>journalling</em> file systems, which
were designed with crash recovery in mind. At the next mount after a
crash, journalling file systems replay their journal, which results
in a consistent state. Note that this implies that even a read-only
mount of the snapshot device has to write to the device. </p>

EXERCISES()

<ul>

        <li> In the test VG, create a 1G large snapshot named
        <code>snap_tlv1</code> of the <code>tlv1</code> VG by using the
        <code>-s</code> option to <code>lvcreate(8)</code>. Predict how much
        free space is left in the VG. Confirm with <code>vgs tvg</code>. </li>

        <li> Create an EXT4 file system on <code>tlv1</code> by running
        <code>mkfs.ext4 /dev/tvg/lv1</code>. Guess how much of the snapshot
        space has been allocated by this operation. Check with <code>lvs
        tvg1/snap_lv1</code>. </li>

        <li> Remove the snapshot with <code>lvremove</code> and recreate
        it. Repeat the previous step, but this time run <code>mkfs.xfs</code>
        to create an XFS file system. Run <code>lvs tvg/snap_lv1</code>
        again and compare the used snapshot space to the EXT4 case. Explain
        the difference. </li>

        <li> Remove the snapshot and recreate it so that both <code>tlv1</code>
        and <code>snap_tlv1</code> contain a valid XFS file system. Mount
        the file systems on <code>/mnt/1</code> and <code>/mnt/2</code>. </li>

        <li> Run <code>dd if=/dev/zero of=/mnt/1/zero count=$((2 * 100 *
        1024))</code> to create a 100M large file on <code>tlv1</code>. Check
        that <code>/mnt/2</code> is still empty. Estimate how much of the
        snapshot space is used and check again. </li>

        <li> Repeat the above <code>dd</code> command 5 times and run
        <code>lvs</code> again. Explain why the used snapshot space did not
        increase. </li>

        <li> It is possible to create snapshots of snapshots. This is
        implemented by chaining together CoW tables. Describe the impact on
        performance. </li>

        <li> Suppose a snapshot was created before significant modifications
        were made to the contents of the LV, for example an upgrade of a large
        software package. Assume that the user wishes to permanently return to
        the old version because the upgrade did not work out. In this scenario
        it is the snapshot which needs to be retained, rather than the original
        LV.  In view of this scenario, guess what happens on the attempt to
        remove a LV which is being snapshotted. Unmount <code>/mnt/1</code>
        and confirm by running <code>lvremove tvg/lv1</code>. </li>

        <li> Come up with a suitable <code>lvconvert</code> command which
        replaces the role of the LV and its snapshot. Explain why this solves
        the "bad upgrade" problem outlined above. </li>

        <li> Explain what happens if the CoW table fills up. Confirm by
        writing a file larger than the snapshot size. </li>

</ul>

SECTION(«Thin Provisioning»)

<p> The term "thin provisioning" is just a modern buzzword for
over-subscription. Both terms mean to give the appearance of having
more resources than are actually available. This is achieved by
on-demand allocation. The thin provisioning implementation of Linux
is implemented as a DM target called <em>dm-thin</em>. This code
first made its appearance in 2011 and was declared as stable two
years later. These days it should be safe for production use. </p>

<p> The general problem with thin provisioning is of course that bad
things happen when the resources are exhausted because the demand has
increased before new resources were added. For dm-thin this can happen
when users write to their allotted space, causing dm-thin to attempt
allocating a data block from a volume which is already full. This
usually leads to severe data corruption because file systems are
not really prepared to handle this error case and treat it as if the
underlying block device had failed. dm-thin does nothing to prevent
this, but one can configure a <em>low watermark</em>.  When the
number of free data blocks drops below the watermark, a so-called
<em>dm-event</em> will be generated to notice the administrator. </p>

<p> One highlight of dm-thin is its efficient support for an arbitrary
depth of recursive snapshots, called <em>dm-thin snapshots</em>
in this document. With the traditional snapshot implementation,
recursive snapshots quickly become a performance issue as the depth
increases. With dm-thin one can have an arbitrary subset of all
snapshots active at any point in time, and there is no ordering
requirement on activating or removing them. </p>

<p> The block devices created by dm-thin always belong to a <em>thin
pool</em> which ties together two LVs called the <em>metadata LV</em>
and the <em>data LV</em>. The combined LV is called the <em>thin pool
LV</em>. Setting up a VG for thin provisioning is done in two steps:
First the standard LVs for data and the metatdata are created. Second,
the two LVs are combined into a thin pool LV. The second step hides
the two underlying LVs so that only the combined thin pool LV is
visible afterwards. Thin provisioned LVs and dm-thin snapshots can
then be created from the thin pool LV with a single command. </p>

<p> Another nice feature of dm-thin are <em>external snapshots</em>.
An external snapshot is one where the origin for a thinly provisioned
device is not a device of the pool. Arbitrary read-only block
devices can be turned into writable devices by creating an external
snapshot. Reads to an unprovisioned area of the snapshot will be passed
through to the origin. Writes trigger the allocation of new blocks as
usual with CoW. One use case for this is VM hosts which run their VMs
on thinly-provisioned volumes but have the base image on some "master"
device which is read-only and can hence be shared between all VMs. </p>

EXERCISES()

<p> Starting with the <code>tvg</code> VG, create and test a thin pool LV
by performing the following steps.  The "Thin Usage" section of
<code>lvmthin(7)</code> will be helpful.

<ul>

        <li> Remove the <code>tlv1</code> and <code>tlv2</code> LVs. </li>

        <li> Create a 5G data LV named <code>tdlv</code> (thin data LV)
        and a 500M LV named <code>tmdlv</code> (thin metada LV). </li>

        <li> Combine the two LVs into a thin pool with
        <code>lvconvert</code>. Run <code>lvs -a</code> and explain the flags
        listed below <code>Attr</code>. </li>

        <li> Create a 10G thin LV named <code>oslv</code> (over-subscribed
        LV). </li>

        <li> Create an XFS file system on <code>oslv</code> and mount it on
        <code>/mnt</code>. </li>

        <li> Run a loop of the form <code>for ((i = 0; i &lt; 50; i++)): do
        ... ; done</code> so that each iteration creates a 50M file named
        <code>file-$i</code> and a snapshot named <code>snap_oslv-$i</code>
        of <code>oslv</code>. </li>

        <li> Activate an arbitrary snapshot with <code>lvchange -K</code> and
        try to mount it. Explain what the error message means. Then read the
        "XFS on snapshots" section of <code>lvmthin(7)</code>. </li>

        <li> Check the available space of the data LV with <code>lvs
        -a</code>. Mount one snapshot (specifying <code>-o nouuid</code>)
        and run <code>lvs -a</code> again.  Why did the free space decrease
        although no new files were written? </li>

        <li> Mount four different snapshots and check that they contain the
        expected files. </li>

        <li> Remove all snapshots. Guess what <code>lvs -a</code> and <code>dh
        -h /mnt</code> report. Then run the commands to confirm. Guess
        what happens if you try to create another 3G file? Confirm
        your guess, then read the section on "Data space exhaustion" of
        <code>lvmthin(7)</code>. </li>

</ul>

HOMEWORK(«

When a thin pool provisions a new data block for a thin LV, the new
block is first overwritten with zeros by default. Discuss why this
is done, its impact on performance and security, and conclude whether
or not it is a good idea to turn off the zeroing.

»)

SECTION(«Bcache, dm-cache and dm-writecache»)

<p> All three implementations named in the title of this chapter are <em>
Linux block layer caches</em>. They combine two different block
devices to form a hybrid block device which dynamically caches
and migrates data between the two devices with the aim to improve
performance. One device, the <em> backing device</em>, is expected
to be large and slow while the other one, the <em>cache device</em>,
is expected to be small and fast. </p>

<div>
define(«bch_width», «300»)
define(«bch_height», «130»)
define(«bch_margin», «10»)
define(«bch_rraid_width», «eval((bch_width() - 4 * bch_margin()) * 4 / 5)»)
define(«bch_raidbox_height», «eval(bch_height() - 2 * bch_margin())»)
define(«bch_nraid_width», «eval(bch_rraid_width() / 4)»)
define(«bch_rdisk_width», «eval((bch_width() - 3 * bch_margin()) * 18 / 100)»)
define(«bch_rdisk_height», «eval((bch_height() - 4 * bch_margin()) / 3)»)
define(«bch_ndisk_width», «eval(bch_rdisk_width() / 2)»)
define(«bch_ndisk_height», «eval(bch_raidbox_height() - 5 * bch_margin())»)
define(«bch_rdisk», «svg_disk(«$1», «$2»,
        «bch_rdisk_width()», «bch_rdisk_height()», «#666»)»)
define(«bch_ndisk», «svg_disk(«$1», «$2»,
        «bch_ndisk_width()», «bch_ndisk_height()», «#66f»)»)
define(«bch_5rdisk», «
        bch_rdisk(«$1», «$2»)
        bch_rdisk(«eval($1 + bch_margin())»,
                «eval($2 + bch_margin())»)
        bch_rdisk(«eval($1 + 2 * bch_margin())»,
                «eval($2 + 2 * bch_margin())»)
        bch_rdisk(«eval($1 + 3 * bch_margin())»,
                «eval($2 + 3 * bch_margin())»)
        bch_rdisk(«eval($1 + 4 * bch_margin())»,
                «eval($2 + 4 * bch_margin())»)

»)
define(«bch_rraid», «
        <rect
                fill="#3b3"
                stroke="black"
                x="$1"
                y="$2"
                width="bch_rraid_width()"
                height="bch_raidbox_height()"
                rx=10
        />
        bch_5rdisk(«eval($1 + bch_margin())»,
                «eval($2 + 2 * bch_margin())»)
        bch_5rdisk(«eval($1 + 2 * bch_rdisk_width() + bch_margin())»,
                «eval($2 + 2 * bch_margin())»)
»)
define(«bch_nraid», «
        <rect
                fill="orange"
                stroke="black"
                x="$1"
                y="$2"
                width="bch_nraid_width()"
                height="bch_raidbox_height()"
                rx=10
        />
        bch_ndisk(eval($1 + bch_margin()),
                eval($2 + 2 * bch_margin()))
        bch_ndisk(eval($1 + 2 * bch_margin()),
                eval($2 + 3 * bch_margin()))
»)

<svg
        width="bch_width()" height="bch_height()"
        xmlns="http://www.w3.org/2000/svg"
        xmlns:xlink="http://www.w3.org/1999/xlink"
>
        <rect
                fill="#cc2"
                stroke="black"
                stroke-width="1"
                x="1"
                y="1"
                width="eval(bch_rraid_width() + bch_nraid_width()
                        + 3 * bch_margin() - 2)"
                height="eval(bch_raidbox_height() + 2 * bch_margin() - 2)"
                rx="10"
        />
        bch_nraid(«bch_margin()», «bch_margin()»)
        bch_rraid(«eval(2 * bch_margin() + bch_nraid_width())», «bch_margin()»)
</svg>
</div>

<p> The most simple setup consists of a single rotating disk and one SSD.
The setup shown in the diagram at the left is realistic for a large
server with redundant storage.  In this setup the hybrid device
(yellow) combines a raid6 array (green) consisting of many rotating
disks (grey) with a two-disk raid1 array (orange) stored on fast
NVMe devices (blue). In the simple setup it is always a win when
I/O is performed from/to the SSD instead of the rotating disk. In
the server setup, however, it depends on the workload which device
is faster. Given enough rotating disks and a streaming I/O workload,
the raid6 outperforms the raid1 because all disks can read or write
at full speed. </p>

<p> Since block layer caches hook into the Linux block API described <a
href="«#»the_linux_block_layer">earlier</a>, the hybrid block devices
they provide can be used like any other block device. In particular,
the hybrid devices are <em> file system agnostic</em>, meaning that
any file system can be created on them. In what follows we briefly
describe the differences between the three block layer caches and
conclude with the pros and cons of each. </p>

<p> Bcache is a stand-alone stacking device driver which was
included in the Linux kernel in 2013. According to the <a
href="https://bcache.evilpiepirate.org/">bcache home page</a>, it
is "done and stable". dm-cache and dm-writecache are device mapper
targets included in 2013 and 2018, respectively, which are both marked
as experimental. In contrast to dm-cache, dm-writecache only caches
writes while reads are supposed to be cached in RAM. It has been
designed for programs like databases which need low commit latency.
Both bcache and dm-cache can operate in writeback or writethrough
mode while dm-writecache always operates in writeback mode. </p>

<p> The DM-based caches are designed to leave the decision as to what
data to migrate (and when) to user space while bcache has this policy
built-in. However, at this point only the <em> Stochastic Multiqueue
</em> (smq) policy for dm-cache exists, plus a second policy which
is only useful for decommissioning the cache device. There are no
tunables for dm-cache while all the bells and whistles of bcache can
be configured through sysfs files.  Another difference is that bcache
detects sequential I/O and separates it from random I/O so that large
streaming reads and writes bypass the cache and don't push cached
randomly accessed data out of the cache. </p>

<p> bcache is the clear  winner of this comparison because it is stable,
configurable and performs better at least on the server setup
described above because it separate random and sequential I/O. The
only advantage of dm-cache is its flexibility because cache policies
can be switched. But even this remains a theoretical advantage as
long as only a single policy for dm-cache exists. </p>

EXERCISES()

<ul>

        <li> Recall the concepts of writeback and writethrough and explain
        why writeback is faster and writethrough is safer. </li>

        <li> Explain how the <em>writearound</em> mode of bcache works and
        when it should be used. </li>

        <li> Setup a bcache device from two loop devices. </li>

        <li> Create a file system of a bcache device and mount it. Detach
        the cache device while the file system is mounted. </li>

        <li> Setup a dm-cache device from two loop devices. </li>

        <li> Setup a thin pool where the data LV is a dm-cache device.</li>

        <li> Explain the point of dm-cache's <em>passthrough</em> mode.</li>

</ul>

HOMEWORK(«

Explain why small writes to a file system which is stored on a
parity raid result in read-modify-write (RMW) updates. Explain why
RMW updates are particularly expensive and how raid implementations
and block layer caches try to avoid them.

»)

HOMEWORK(«

Recall the concepts of writeback and writethrough. Describe what
each mode means for a hardware device and for a bcache/dm-cache
device. Explain why writeback is faster and writethrough is safer.

»)

HOMEWORK(«

TRIM and UNMAP are special commands in the ATA/SCSI command sets
which inform an SSD that certain data blocks are no longer in use,
allowing the SSD to re-use these blocks to increase performance and
to reduce wear. Subsequent reads from the trimmed data blocks will
not return any meaningful data. For example, the <code> mkfs </code>
commands sends this command to discard all blocks of the device.
Discuss the implications when <code> mkfs. </code> is run on a device
provided by bcache or dm-cache.

»)

SECTION(«The dm-crypt Target»)

<p> This device mapper target provides encryption of arbitrary block
devices by employing the primitives of the crypto API of the Linux
kernel. This API provides a uniform interface to a large number of
cipher algorithms which have been implemented with performance and
security in mind. </p>

<p> The cipher algorithm of choice for the encryption of block devices
is the <em> Advanced Encryption Standard </em> (AES), also known
as <em> Rijndael</em>, named after the two Belgian cryptographers
Rijmen and Daemen who proposed the algorithm in 1999. AES is a <em>
symmetric block cipher</em>. That is, a transformation which operates
on fixed-length blocks and which is determined by a single key for both
encryption and decryption. The underlying algorithm is fairly simple,
which makes AES perform well in both hardware and software. Also
the key setup time and the memory requirements are excellent. Modern
processors of all manufacturers include instructions to perform AES
operations in hardware, improving speed and security. </p>

<p> According to the Snowden documents, the NSA has been doing research
on breaking AES for a long time without being able to come up with
a practical attack for 256 bit keys. Successful attacks invariably
target the key management software instead, which is often implemented
poorly, trading security for user-friendliness, for example by
storing passwords weakly encrypted, or by providing a "feature"
which can decrypt the device without knowing the password. </p>

<p> The exercises of this section ask the reader to encrypt a loop device
with AES without relying on any third party key management software </p>.

EXERCISES()
<ul>
        <li> Discuss the message of this <a
        href="https://xkcd.com/538/">xkcd</a> comic. </li>

        <li> How can a hardware implementation of an algorithm like AES
        improve security? After all, it is the same algorithm that is
        implemented. </li>

        <li> What's the point of the <a href="#random_stream">rstream.c</a>
        program below which writes random data to stdout? Doesn't <code>
        cat /dev/urandom </code> do the same? </li>

        <li> Compile and run <a href="#random_stream">rstream.c</a> to create
        a 10G local file and create the loop device <code> /dev/loop0 </code>
        from the file. </li>

        <li> A <em> table </em> for the <code> dmsetup(8) </code> command is
        a single line of the form <code> start_sector num_sectors target_type
        target_args</code>. Determine the correct values for the first three
        arguments to encrypt <code> /dev/loop0</code>. </li>

        <li> The <code>target_args</code> for the dm-crypt target are
        of the form <code>cipher key iv_offset device offset</code>. To
        encrypt <code>/dev/loop0</code> with AES-256, <code>cipher</code>
        is <code>aes</code>, <code>device</code> is <code>/dev/loop0</code>
        and both offsets are zero. Come up with an idea to create a 256 bit
        key from a passphrase. </li>

        <li> The <code> create </code> subcommand of <code> dmsetup(8)
        </code> creates a device from the given table. Run a command of
        the form <code> echo "$table" | dmsetup create cryptdev </code>
        to create the encrypted device <code> /dev/mapper/cryptdev </code>
        from the loop device. </li>

        <li> Create a file system on <code> /dev/mapper/cryptdev</code>,
        mount it and create the file <code> passphrase </code> containing
        the string "super-secret" on this file system. </li>

        <li> Unmount the <code> cryptdev </code> device and run <code> dmsetup
        remove cryptdev</code>. Run <code> strings </code> on the loop device
        and on the underlying file to see if it contains the string <code>
        super-secret" </code> or <code> passphrase</code>. </li>

        <li> Re-create the <code> cryptdev </code> device, but this time use
        a different (hence invalid) key. Guess what happens and confirm. </li>

        <li> Write a script which disables echoing (<code>stty -echo</code>),
        reads a passphrase from stdin and combines the above steps to create
        and mount an encrypted device. </li>

</ul>

HOMEWORK(«

Why is it a good idea to overwrite a block device with random data
before it is encrypted?

»)

HOMEWORK(«

The dm-crypt target encrypts whole block devices. An alternative is
to encrypt on the file system level. That is, each file is encrypted
separately. Discuss the pros and cons of both approaches.

»)

SUPPLEMENTS()

SUBSECTION(«Random stream»)

<pre>
        <code>
                /* Link with -lcrypto */
                #include &lt;openssl/rand.h&gt;
                #include &lt;stdio.h&gt;
                #include &lt;unistd.h&gt;
                #include &lt;stdio.h&gt;

                int main(int argc, char **argv)
                {
                        unsigned char buf[1024 * 1024];

                        for (;;) {
                                int ret = RAND_bytes(buf, sizeof(buf));

                                if (ret &lt;= 0) {
                                        fprintf(stderr, "RAND_bytes() error\n");
                                        exit(EXIT_FAILURE);
                                }
                                ret = write(STDOUT_FILENO, buf, sizeof(buf));
                                if (ret &lt; 0) {
                                        perror("write");
                                        exit(EXIT_FAILURE);
                                }
                        }
                        return 0;
                }
        </code>
</pre>