Lines Matching +full:linear +full:- +full:mapping +full:- +full:mode
1 .. SPDX-License-Identifier: GPL-2.0-only
4 Design of dm-vdo
7 The dm-vdo (virtual data optimizer) target provides inline deduplication,
8 compression, zero-block elimination, and thin provisioning. A dm-vdo target
12 production environments ever since. It was made open-source in 2017 after
14 dm-vdo. For usage, see vdo.rst in the same directory as this file.
25 The design of dm-vdo is based on the idea that deduplication is a two-part
27 storing multiple copies of those duplicates. Therefore, dm-vdo has two main
34 -------------------
41 design attempts to be lock-free.
59 reflected in the on-disk representation of each data structure. Therefore,
64 -----------------------
79 trade-off between the storage saved and the resources expended to achieve
83 Each block of data is hashed to produce a 16-byte block name. An index
87 because it is too costly to update the index when a block is over-written
89 with the blocks, which is difficult to do efficiently in block-based
116 chapters are read-only structures and their contents are never altered in
127 mapping each block name to the chapter containing its newest record. This
128 mapping is updated as records for the block name are copied or updated,
149 memory-efficient structure called a delta index. Instead of storing the
160 splitting its key space into many sub-lists, each starting at a fixed key
190 indexing, the memory requirements do not increase. The trade-off is
193 duplicate data, sparse indexing will detect 97-99% of the deduplication
197 -------------------------------
200 fields and data to track vdo-specific information. A struct vio maintains a
221 --------------
231 three sections. Most of a slab consists of a linear sequence of 4K blocks.
243 memory and are written out, a block at a time in oldest-dirtied-order, only
249 zones" in round-robin fashion. If there are P physical zones, then slab n
260 available, the target can resume normal operation in a degraded mode. Read
266 The block map contains the logical to physical mapping. It can be thought
270 of the mapping. Of the 16 possible states, one represents a logical address
276 In practice, the array of mapping entries is divided into "block map
278 consists of a header and 812 mapping entries. Each mapping page is actually
283 0-811 belong to tree 0, logical addresses 812-1623 belong to tree 1, and so
289 need to pre-allocate space for the entire set of logical mappings and also
296 time, and is large enough to hold all the non-leaf pages of the entire
307 pages are never reclaimed or repurposed, so the old mapping is always 0.
372 a. If any page-node in the tree has not yet been allocated, it must be
374 data_vio to lock the page-node that needs to be allocated. This
383 the tree using a similar process to adding a new data block mapping.
387 new mapping to the parent tree node (step 12). Once the tree is
391 b. In the steady-state case, the block map tree nodes will already be
393 the required leaf node. The location of the mapping (the "block map
416 sub-component of the slab and are thus also covered by the implicit
474 to record their new mapping. If there are more data_vios in the hash
527 new mapping.
533 9. The data_vio determines the previous mapping of the logical address.
540 physical mapping"), if any, and records it. This step requires a lock
545 logical block address, the old physical mapping, and the new physical
546 mapping. Making this journal entry requires holding the implicit
552 journal entries: an increment entry for the new mapping, and a
553 decrement entry for the old mapping. These two operations each require
565 logical-to-physical mapping in the block map to point to the new
589 logical-to-physical mapping by traversing the block map tree as in step 3,
602 a read-modify-write operation that reads the relevant 4K block, copies the
611 recovery journal. During the pre-resume phase of the next start, the
620 *Read-only Rebuild*
622 If a vdo encounters an unrecoverable error, it will enter read-only mode.
623 This mode indicates that some previously acknowledged data may have been
626 to the possibility that data has been lost. During a read-only rebuild, the