Lines Matching refs:chunk
42 A compressed block device compresses and decompresses data in units of chunks, where a chunk is a
43 multiple of at least two 4KB backing IO units. The number of backing IO units per chunk determines
44 the chunk size and is specified when the compressed block device is created. A chunk
45 consumes a number of 4KB backing IO units between 1 and the number of 4KB units in the chunk. For
46 example, a 16KB chunk consumes 1, 2, 3 or 4 backing IO units. The number of backing IO units depen…
47 much the chunk was able to be compressed. The blocks on disk associated with a chunk are stored in…
48 "chunk map" in persistent memory. Each chunk map consists of N 64-bit values, where N is the maxim…
49 number of backing IO units in the chunk. Each 64-bit value corresponds to a backing IO unit index.…
51 number of chunk maps allocated is equal to the size of the compressed block device divided by its c…
52 size, plus some number of extra chunk maps. These extra chunk maps are used to ensure atomicity on
53 writes and will be explained later in this document. At start, all of the chunk maps represent the
54 "free chunk map list".
57 logical map is a mapping of chunk offsets into the compressed block device to the corresponding
58 chunk map. Each entry in the logical map is a 64-bit value, denoting the associated chunk map.
59 A special value (UINT64_MAX) is used if there is no associated chunk map. The mapping is
60 determined by dividing the byte offset by the chunk size to get an index, which is used as an
61 array index into the array of chunk map entries. At start, all entries in the logical map have no
62 associated chunk map. Note that while access to the backing storage device is in 4KB units, the
69 The size of the compressed block device is 64KB, with a chunk size of 16KB. This will
77 * A "chunk map" will be 32 bytes in size. This corresponds to 4 backing IO units per chunk
79 * 5 chunk maps will be allocated in 160B of persistent memory. This corresponds to 4 chunk maps
80 for the 4 chunks in the compressed block device (64KB / 16KB), plus an extra chunk map for use
81 when overwriting an existing chunk.
82 * "Free chunk map list" will consist of indices 0 through 4 (inclusive). These represent the
83 5 allocated chunk maps.
111 * Find the corresponding index into the logical map. Offset 32KB divided by the chunk size
121 * Allocate a chunk map (0) from the free chunk map list.
122 * Write (0, 1, X, X) to the chunk map. This represents that only 2 backing IO units were used to
124 * Write the chunk map index to entry 2 in the logical map.
146 * Find the corresponding index into the logical map. Offset 8KB divided by the chunk size is 0.
148 * The write is not for the entire 16KB chunk, so we must allocate a 16KB chunk-sized buffer for
156 * Allocate a chunk map (1) from the free chunk map list.
157 * Write (2, X, X, X) to the chunk map.
158 * Write the chunk map index to entry 0 in the logical map.
182 * Since no data has been written to this chunk, return all 0's to satisfy the read I/O.
187 * Entry 0 in the logical map is "1". Since we are not overwriting the entire chunk, we must
193 * Allocate a 16KB buffer for the uncompressed data for this chunk. Decompress the data from
200 * Allocate chunk map 2 from the free chunk map list.
201 * Write (3, 4, X, X) to chunk map 2. Note that at this point, the chunk map is not referenced
202 by the logical map. If there was a power fail at this point, the previous data for this chunk
204 * Write chunk map 2 to entry 0 in the logical map.
205 * Free chunk map 1 back to the free chunk map list.
228 Operations that span a chunk boundary are logically split into multiple operations, each of
229 which is associated with a single chunk.
234 chunk 0 in the logical map) and a 8KB write at offset 16KB (affecting only chunk 1 in the
240 Unmap operations on an entire chunk are achieved by removing the chunk map entry (if any) from
241 the logical map. The chunk map is returned to the free chunk map list, and any backing IO units
242 associated with the chunk map are returned to the free backing IO unit list.
244 Unmap operations that affect only part of a chunk can be treated as writing zeroes to that
245 region of the chunk. If the entire chunk is unmapped via several operations, it can be
246 detected via the uncompressed data equaling all zeroes. When this occurs, the chunk map entry
249 After an entire chunk has been unmapped, subsequent reads to the chunk will return all zeroes.
255 operation covers an entire chunk, we can remove the chunk's entry in the logical map
256 completely. Then subsequent reads to that chunk will return all zeroes.
264 When the compressed volume is reloaded, the free chunk map list and free backing IO unit list
266 chunk maps, and the valid chunk maps will only point to valid backing IO units. Any chunk maps
270 after a chunk map is updated, but before it is written to the logical map - that everything
273 ### Overlapping operations on same chunk
275 Implementations must take care to handle overlapping operations on the same chunk. For example,
276 operation 1 writes some data to chunk A, and while this is in progress, operation 2 also writes
277 some data to chunk A. In this case, operation 2 should not start until operation 1 has