1 /*
2 * Copyright (C) 2021 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "snapuserd.h"
18
19 #include <csignal>
20 #include <optional>
21 #include <set>
22
23 #include <libsnapshot/snapuserd_client.h>
24
25 namespace android {
26 namespace snapshot {
27
28 using namespace android;
29 using namespace android::dm;
30 using android::base::unique_fd;
31
32 #define SNAP_LOG(level) LOG(level) << misc_name_ << ": "
33 #define SNAP_PLOG(level) PLOG(level) << misc_name_ << ": "
34
35 /*
36 * Merging a copy operation involves the following flow:
37 *
38 * 1: dm-snapshot layer requests merge for a 4k block. dm-user sends the request
39 * to the daemon
40 * 2: daemon reads the source block
41 * 3: daemon copies the source data
42 * 4: IO completion sent back to dm-user (a switch from user space to kernel)
43 * 5: dm-snapshot merges the data to base device
44 * 6: dm-snapshot sends the merge-completion IO to dm-user
45 * 7: dm-user re-directs the merge completion IO to daemon (one more switch)
46 * 8: daemon updates the COW file about the completed merge request (a write syscall) and followed
47 * by a fysnc. 9: Send the IO completion back to dm-user
48 *
49 * The above sequence is a significant overhead especially when merging one 4k
50 * block at a time.
51 *
52 * Read-ahead layer will optimize the above path by reading the data from base
53 * device in the background so that merging thread can retrieve the data from
54 * the read-ahead cache. Additionally, syncing of merged data is deferred to
55 * read-ahead thread threadby the IO path is not bottlenecked.
56 *
57 * We create a scratch space of 2MB to store the read-ahead data in the COW
58 * device.
59 *
60 * +-----------------------+
61 * | Header (fixed) |
62 * +-----------------------+
63 * | Scratch space | <-- 2MB
64 * +-----------------------+
65 *
66 * Scratch space is as follows:
67 *
68 * +-----------------------+
69 * | Metadata | <- 4k page
70 * +-----------------------+
71 * | Metadata | <- 4k page
72 * +-----------------------+
73 * | |
74 * | Read-ahead data |
75 * | |
76 * +-----------------------+
77 *
78 * State transitions and communication between read-ahead thread and worker
79 * thread during merge:
80 * =====================================================================
81 *
82 * Worker Threads Read-Ahead thread
83 * ------------------------------------------------------------------
84 *
85 * |
86 * |
87 * --> -----------------READ_AHEAD_BEGIN------------->|
88 * | | | READ_AHEAD_IN_PROGRESS
89 * | WAIT |
90 * | | |
91 * | |<-----------------IO_IN_PROGRESS---------------
92 * | | |
93 * | | IO_IN_PRGRESS WAIT
94 * | | |
95 * |<--| |
96 * | |
97 * ------------------IO_TERMINATED--------------->|
98 * END
99 *
100 *
101 * ===================================================================
102 *
103 * Example:
104 *
105 * We have 6 copy operations to be executed in OTA and there is a overlap. Update-engine
106 * will write to COW file as follows:
107 *
108 * Op-1: 20 -> 23
109 * Op-2: 19 -> 22
110 * Op-3: 18 -> 21
111 * Op-4: 17 -> 20
112 * Op-5: 16 -> 19
113 * Op-6: 15 -> 18
114 *
115 * Read-ahead thread will read all the 6 source blocks and store the data in the
116 * scratch space. Metadata will contain the destination block numbers. Thus,
117 * scratch space will look something like this:
118 *
119 * +--------------+
120 * | Block 23 |
121 * | offset - 1 |
122 * +--------------+
123 * | Block 22 |
124 * | offset - 2 |
125 * +--------------+
126 * | Block 21 |
127 * | offset - 3 |
128 * +--------------+
129 * ...
130 * ...
131 * +--------------+
132 * | Data-Block 20| <-- offset - 1
133 * +--------------+
134 * | Data-Block 19| <-- offset - 2
135 * +--------------+
136 * | Data-Block 18| <-- offset - 3
137 * +--------------+
138 * ...
139 * ...
140 *
141 * ====================================================================
142 * IO Path:
143 *
144 * Read-ahead will serve the data to worker threads during merge only
145 * after metadata and data are persisted to the scratch space. Worker
146 * threads during merge will always retrieve the data from cache; if the
147 * cache is not populated, it will wait for the read-ahead thread to finish.
148 * Furthermore, the number of operations merged will by synced to the header
149 * only when all the blocks in the read-ahead cache are merged. In the above
150 * case, when all 6 operations are merged, COW Header is updated with
151 * num_merge_ops = 6.
152 *
153 * Merge resume after crash:
154 *
155 * Let's say we have a crash after 5 operations are merged. i.e. after
156 * Op-5: 16->19 is completed but before the Op-6 is merged. Thus, COW Header
157 * num_merge_ops will be 0 as the all the ops were not merged yet. During next
158 * reboot, read-ahead thread will re-construct the data in-memory from the
159 * scratch space; when merge resumes, Op-1 will be re-exectued. However,
160 * data will be served from read-ahead cache safely even though, block 20
161 * was over-written by Op-4.
162 *
163 */
164
ReadAheadThread(const std::string & cow_device,const std::string & backing_device,const std::string & misc_name,std::shared_ptr<Snapuserd> snapuserd)165 ReadAheadThread::ReadAheadThread(const std::string& cow_device, const std::string& backing_device,
166 const std::string& misc_name,
167 std::shared_ptr<Snapuserd> snapuserd) {
168 cow_device_ = cow_device;
169 backing_store_device_ = backing_device;
170 misc_name_ = misc_name;
171 snapuserd_ = snapuserd;
172 }
173
CheckOverlap(const CowOperation * cow_op)174 void ReadAheadThread::CheckOverlap(const CowOperation* cow_op) {
175 if (dest_blocks_.count(cow_op->new_block) || source_blocks_.count(cow_op->source)) {
176 overlap_ = true;
177 }
178
179 dest_blocks_.insert(cow_op->source);
180 source_blocks_.insert(cow_op->new_block);
181 }
182
PrepareReadAhead(uint64_t * source_block,int * pending_ops,std::vector<uint64_t> & blocks)183 void ReadAheadThread::PrepareReadAhead(uint64_t* source_block, int* pending_ops,
184 std::vector<uint64_t>& blocks) {
185 int num_ops = *pending_ops;
186 int nr_consecutive = 0;
187
188 if (!IterDone() && num_ops) {
189 // Get the first block
190 const CowOperation* cow_op = GetIterOp();
191 *source_block = cow_op->source;
192 IterNext();
193 num_ops -= 1;
194 nr_consecutive = 1;
195 blocks.push_back(cow_op->new_block);
196
197 if (!overlap_) {
198 CheckOverlap(cow_op);
199 }
200
201 /*
202 * Find number of consecutive blocks working backwards.
203 */
204 while (!IterDone() && num_ops) {
205 const CowOperation* op = GetIterOp();
206 if (op->source != (*source_block - nr_consecutive)) {
207 break;
208 }
209 nr_consecutive += 1;
210 num_ops -= 1;
211 blocks.push_back(op->new_block);
212 IterNext();
213
214 if (!overlap_) {
215 CheckOverlap(op);
216 }
217 }
218 }
219 }
220
ReconstructDataFromCow()221 bool ReadAheadThread::ReconstructDataFromCow() {
222 std::unordered_map<uint64_t, void*>& read_ahead_buffer_map = snapuserd_->GetReadAheadMap();
223 read_ahead_buffer_map.clear();
224 loff_t metadata_offset = 0;
225 loff_t start_data_offset = snapuserd_->GetBufferDataOffset();
226 int num_ops = 0;
227 int total_blocks_merged = 0;
228
229 // This memcpy is important as metadata_buffer_ will be an unaligned address and will fault
230 // on 32-bit systems
231 std::unique_ptr<uint8_t[]> metadata_buffer =
232 std::make_unique<uint8_t[]>(snapuserd_->GetBufferMetadataSize());
233 memcpy(metadata_buffer.get(), metadata_buffer_, snapuserd_->GetBufferMetadataSize());
234
235 while (true) {
236 struct ScratchMetadata* bm = reinterpret_cast<struct ScratchMetadata*>(
237 (char*)metadata_buffer.get() + metadata_offset);
238
239 // Done reading metadata
240 if (bm->new_block == 0 && bm->file_offset == 0) {
241 break;
242 }
243
244 loff_t buffer_offset = bm->file_offset - start_data_offset;
245 void* bufptr = static_cast<void*>((char*)read_ahead_buffer_ + buffer_offset);
246 read_ahead_buffer_map[bm->new_block] = bufptr;
247 num_ops += 1;
248 total_blocks_merged += 1;
249
250 metadata_offset += sizeof(struct ScratchMetadata);
251 }
252
253 // We are done re-constructing the mapping; however, we need to make sure
254 // all the COW operations to-be merged are present in the re-constructed
255 // mapping.
256 while (!IterDone()) {
257 const CowOperation* op = GetIterOp();
258 if (read_ahead_buffer_map.find(op->new_block) != read_ahead_buffer_map.end()) {
259 num_ops -= 1;
260 snapuserd_->SetFinalBlockMerged(op->new_block);
261 IterNext();
262 } else {
263 // Verify that we have covered all the ops which were re-constructed
264 // from COW device - These are the ops which are being
265 // re-constructed after crash.
266 if (!(num_ops == 0)) {
267 SNAP_LOG(ERROR) << "ReconstructDataFromCow failed. Not all ops recoverd "
268 << " Pending ops: " << num_ops;
269 snapuserd_->ReadAheadIOFailed();
270 return false;
271 }
272 break;
273 }
274 }
275
276 snapuserd_->SetTotalRaBlocksMerged(total_blocks_merged);
277
278 snapuserd_->ReconstructDataFromCowFinish();
279
280 if (!snapuserd_->ReadAheadIOCompleted(true)) {
281 SNAP_LOG(ERROR) << "ReadAheadIOCompleted failed...";
282 snapuserd_->ReadAheadIOFailed();
283 return false;
284 }
285
286 SNAP_LOG(INFO) << "ReconstructDataFromCow success";
287 return true;
288 }
289
ReadAheadIOStart()290 bool ReadAheadThread::ReadAheadIOStart() {
291 // Check if the data has to be constructed from the COW file.
292 // This will be true only once during boot up after a crash
293 // during merge.
294 if (snapuserd_->ReconstructDataFromCow()) {
295 return ReconstructDataFromCow();
296 }
297
298 std::unordered_map<uint64_t, void*>& read_ahead_buffer_map = snapuserd_->GetReadAheadMap();
299 read_ahead_buffer_map.clear();
300
301 int num_ops = (snapuserd_->GetBufferDataSize()) / BLOCK_SZ;
302 loff_t metadata_offset = 0;
303
304 struct ScratchMetadata* bm =
305 reinterpret_cast<struct ScratchMetadata*>((char*)metadata_buffer_ + metadata_offset);
306
307 bm->new_block = 0;
308 bm->file_offset = 0;
309
310 std::vector<uint64_t> blocks;
311
312 loff_t buffer_offset = 0;
313 loff_t offset = 0;
314 loff_t file_offset = snapuserd_->GetBufferDataOffset();
315 int total_blocks_merged = 0;
316 overlap_ = false;
317 dest_blocks_.clear();
318 source_blocks_.clear();
319
320 while (true) {
321 uint64_t source_block;
322 int linear_blocks;
323
324 PrepareReadAhead(&source_block, &num_ops, blocks);
325 linear_blocks = blocks.size();
326 if (linear_blocks == 0) {
327 // No more blocks to read
328 SNAP_LOG(DEBUG) << " Read-ahead completed....";
329 break;
330 }
331
332 // Get the first block in the consecutive set of blocks
333 source_block = source_block + 1 - linear_blocks;
334 size_t io_size = (linear_blocks * BLOCK_SZ);
335 num_ops -= linear_blocks;
336 total_blocks_merged += linear_blocks;
337
338 // Mark the block number as the one which will
339 // be the final block to be merged in this entire region.
340 // Read-ahead thread will get
341 // notified when this block is merged to make
342 // forward progress
343 snapuserd_->SetFinalBlockMerged(blocks.back());
344
345 while (linear_blocks) {
346 uint64_t new_block = blocks.back();
347 blocks.pop_back();
348 // Assign the mapping
349 void* bufptr = static_cast<void*>((char*)read_ahead_buffer_ + offset);
350 read_ahead_buffer_map[new_block] = bufptr;
351 offset += BLOCK_SZ;
352
353 bm = reinterpret_cast<struct ScratchMetadata*>((char*)metadata_buffer_ +
354 metadata_offset);
355 bm->new_block = new_block;
356 bm->file_offset = file_offset;
357
358 metadata_offset += sizeof(struct ScratchMetadata);
359 file_offset += BLOCK_SZ;
360
361 linear_blocks -= 1;
362 }
363
364 // Read from the base device consecutive set of blocks in one shot
365 if (!android::base::ReadFullyAtOffset(backing_store_fd_,
366 (char*)read_ahead_buffer_ + buffer_offset, io_size,
367 source_block * BLOCK_SZ)) {
368 SNAP_PLOG(ERROR) << "Copy-op failed. Read from backing store: " << backing_store_device_
369 << "at block :" << source_block << " buffer_offset : " << buffer_offset
370 << " io_size : " << io_size << " buf-addr : " << read_ahead_buffer_;
371
372 snapuserd_->ReadAheadIOFailed();
373 return false;
374 }
375
376 // This is important - explicitly set the contents to zero. This is used
377 // when re-constructing the data after crash. This indicates end of
378 // reading metadata contents when re-constructing the data
379 bm = reinterpret_cast<struct ScratchMetadata*>((char*)metadata_buffer_ + metadata_offset);
380 bm->new_block = 0;
381 bm->file_offset = 0;
382
383 buffer_offset += io_size;
384 }
385
386 snapuserd_->SetTotalRaBlocksMerged(total_blocks_merged);
387
388 // Flush the data only if we have a overlapping blocks in the region
389 if (!snapuserd_->ReadAheadIOCompleted(overlap_)) {
390 SNAP_LOG(ERROR) << "ReadAheadIOCompleted failed...";
391 snapuserd_->ReadAheadIOFailed();
392 return false;
393 }
394
395 return true;
396 }
397
RunThread()398 bool ReadAheadThread::RunThread() {
399 if (!InitializeFds()) {
400 return false;
401 }
402
403 InitializeIter();
404 InitializeBuffer();
405
406 while (!IterDone()) {
407 if (!ReadAheadIOStart()) {
408 return false;
409 }
410
411 bool status = snapuserd_->WaitForMergeToComplete();
412
413 if (status && !snapuserd_->CommitMerge(snapuserd_->GetTotalRaBlocksMerged())) {
414 return false;
415 }
416
417 if (!status) break;
418 }
419
420 CloseFds();
421 SNAP_LOG(INFO) << " ReadAhead thread terminating....";
422 return true;
423 }
424
425 // Initialization
InitializeFds()426 bool ReadAheadThread::InitializeFds() {
427 backing_store_fd_.reset(open(backing_store_device_.c_str(), O_RDONLY));
428 if (backing_store_fd_ < 0) {
429 SNAP_PLOG(ERROR) << "Open Failed: " << backing_store_device_;
430 return false;
431 }
432
433 cow_fd_.reset(open(cow_device_.c_str(), O_RDWR));
434 if (cow_fd_ < 0) {
435 SNAP_PLOG(ERROR) << "Open Failed: " << cow_device_;
436 return false;
437 }
438
439 return true;
440 }
441
InitializeIter()442 void ReadAheadThread::InitializeIter() {
443 std::vector<const CowOperation*>& read_ahead_ops = snapuserd_->GetReadAheadOpsVec();
444 read_ahead_iter_ = read_ahead_ops.rbegin();
445 }
446
IterDone()447 bool ReadAheadThread::IterDone() {
448 std::vector<const CowOperation*>& read_ahead_ops = snapuserd_->GetReadAheadOpsVec();
449 return read_ahead_iter_ == read_ahead_ops.rend();
450 }
451
IterNext()452 void ReadAheadThread::IterNext() {
453 read_ahead_iter_++;
454 }
455
GetIterOp()456 const CowOperation* ReadAheadThread::GetIterOp() {
457 return *read_ahead_iter_;
458 }
459
InitializeBuffer()460 void ReadAheadThread::InitializeBuffer() {
461 void* mapped_addr = snapuserd_->GetMappedAddr();
462 // Map the scratch space region into memory
463 metadata_buffer_ =
464 static_cast<void*>((char*)mapped_addr + snapuserd_->GetBufferMetadataOffset());
465 read_ahead_buffer_ = static_cast<void*>((char*)mapped_addr + snapuserd_->GetBufferDataOffset());
466 }
467
468 } // namespace snapshot
469 } // namespace android
470