1 // Copyright (C) 2019 The Android Open Source Project
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #pragma once
16 
17 #include <android-base/logging.h>
18 #include <stdint.h>
19 
20 #include <limits>
21 #include <optional>
22 #include <unordered_set>
23 
24 namespace android {
25 namespace snapshot {
26 
27 class DmSnapCowSizeCalculator {
28   public:
DmSnapCowSizeCalculator(unsigned int sector_bytes,unsigned int chunk_sectors)29     DmSnapCowSizeCalculator(unsigned int sector_bytes, unsigned int chunk_sectors)
30         : sector_bytes_(sector_bytes),
31           chunk_sectors_(chunk_sectors),
32           exceptions_per_chunk(chunk_sectors_ * sector_bytes_ / exception_size_bytes) {}
33 
WriteByte(uint64_t address)34     void WriteByte(uint64_t address) { WriteSector(address / sector_bytes_); }
WriteSector(uint64_t sector)35     void WriteSector(uint64_t sector) { WriteChunk(sector / chunk_sectors_); }
WriteChunk(uint64_t chunk_id)36     void WriteChunk(uint64_t chunk_id) {
37         if (!valid_) {
38             return;
39         }
40 
41         if (chunk_id > std::numeric_limits<uint32_t>::max()) {
42             LOG(ERROR) << "Chunk exceeds maximum size: " << chunk_id;
43             valid_ = false;
44             return;
45         }
46         if (modified_chunks_.count(chunk_id) > 0) {
47             return;
48         }
49 
50         modified_chunks_.emplace(chunk_id);
51     }
52 
cow_size_bytes()53     std::optional<uint64_t> cow_size_bytes() const {
54         auto sectors = cow_size_sectors();
55         if (!sectors) {
56             return std::nullopt;
57         }
58         return sectors.value() * sector_bytes_;
59     }
cow_size_sectors()60     std::optional<uint64_t> cow_size_sectors() const {
61         auto chunks = cow_size_chunks();
62         if (!chunks) {
63             return std::nullopt;
64         }
65         return chunks.value() * chunk_sectors_;
66     }
67 
68     /*
69      * The COW device has a precise internal structure as follows:
70      *
71      * - header (1 chunk)
72      * - #0 map and chunks
73      *   - map (1 chunk)
74      *   - chunks addressable by previous map (exceptions_per_chunk)
75      * - #1 map and chunks
76      *   - map (1 chunk)
77      *   - chunks addressable by previous map (exceptions_per_chunk)
78      * ...
79      * - #n: map and chunks
80      *   - map (1 chunk)
81      *   - chunks addressable by previous map (exceptions_per_chunk)
82      * - 1 extra chunk
83      */
cow_size_chunks()84     std::optional<uint64_t> cow_size_chunks() const {
85         if (!valid_) {
86             LOG(ERROR) << "Invalid COW size.";
87             return std::nullopt;
88         }
89 
90         uint64_t cow_chunks = 0;
91 
92         /* disk header + padding = 1 chunk */
93         cow_chunks += 1;
94 
95         /* snapshot modified chunks */
96         cow_chunks += modified_chunks_.size();
97 
98         /* snapshot chunks index metadata */
99         cow_chunks += 1 + modified_chunks_.size() / exceptions_per_chunk;
100 
101         return cow_chunks;
102     }
103 
104   private:
105     /*
106      * Size of each sector in bytes.
107      */
108     const uint64_t sector_bytes_;
109 
110     /*
111      * Size of each chunk in sectors.
112      */
113     const uint64_t chunk_sectors_;
114 
115     /*
116      * The COW device stores tables to map the modified chunks. Each table has
117      * the size of exactly 1 chunk.
118      * Each entry of the table is called exception and the number of exceptions
119      * that each table can contain determines the number of data chunks that
120      * separate two consecutive tables. This value is then fundamental to
121      * compute the space overhead introduced by the tables in COW devices.
122      */
123     const uint64_t exceptions_per_chunk;
124 
125     /*
126      * Each row of the table (called exception in the kernel) contains two
127      * 64 bit indices to identify the corresponding chunk, and this 128 bit
128      * pair is constant in size.
129      */
130     static constexpr unsigned int exception_size_bytes = 64 * 2 / 8;
131 
132     /*
133      * Validity check for the container.
134      * It may happen that the caller attempts the write of an invalid chunk
135      * identifier, and this misbehavior is accounted and stored in this value.
136      */
137     bool valid_ = true;
138 
139     /*
140      * |modified_chunks_| is a container that keeps trace of the modified
141      * chunks.
142      */
143     std::unordered_set<uint32_t> modified_chunks_;
144 };
145 
146 }  // namespace snapshot
147 }  // namespace android
148