/*
* Copyright (C) 2011 Red Hat, Inc.
*
* This file is released under the GPL.
*/
#include "dm-thin-metadata.h"
#include "persistent-data/dm-btree.h"
#include "persistent-data/dm-space-map.h"
#include "persistent-data/dm-space-map-disk.h"
#include "persistent-data/dm-transaction-manager.h"
#include <linux/list.h>
#include <linux/device-mapper.h>
#include <linux/workqueue.h>
/*--------------------------------------------------------------------------
* As far as the metadata goes, there is:
*
* - A superblock in block zero, taking up fewer than 512 bytes for
* atomic writes.
*
* - A space map managing the metadata blocks.
*
* - A space map managing the data blocks.
*
* - A btree mapping our internal thin dev ids onto struct disk_device_details.
*
* - A hierarchical btree, with 2 levels which effectively maps (thin
* dev id, virtual block) -> block_time. Block time is a 64-bit
* field holding the time in the low 24 bits, and block in the top 48
* bits.
*
* BTrees consist solely of btree_nodes, that fill a block. Some are
* internal nodes, as such their values are a __le64 pointing to other
* nodes. Leaf nodes can store data of any reasonable size (ie. much
* smaller than the block size). The nodes consist of the header,
* followed by an array of keys, followed by an array of values. We have
* to binary search on the keys so they're all held together to help the
* cpu cache.
*
* Space maps have 2 btrees:
*
* - One maps a uint64_t onto a struct index_entry. Which points to a
* bitmap block, and has some details about how many free entries there
* are etc.
*
* - The bitmap blocks have a header (for the checksum). Then the rest