Checkpoint.cpp

   1 /*
   2  * Copyright (C) 2018 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 #define LOG_TAG "Checkpoint"
  18 #include "Checkpoint.h"
  19 #include "VoldUtil.h"
  20 #include "VolumeManager.h"
  21
  22 #include <fstream>
  23 #include <list>
  24 #include <memory>
  25 #include <string>
  26 #include <thread>
  27 #include <vector>
  28
  29 #include <android-base/file.h>
  30 #include <android-base/logging.h>
  31 #include <android-base/parseint.h>
  32 #include <android-base/properties.h>
  33 #include <android-base/unique_fd.h>
  34 #include <android/hardware/boot/1.0/IBootControl.h>
  35 #include <cutils/android_reboot.h>
  36 #include <fcntl.h>
  37 #include <fs_mgr.h>
  38 #include <linux/fs.h>
  39 #include <mntent.h>
  40 #include <sys/mount.h>
  41 #include <sys/stat.h>
  42 #include <sys/statvfs.h>
  43 #include <unistd.h>
  44
  45 using android::base::GetBoolProperty;
  46 using android::base::GetUintProperty;
  47 using android::base::SetProperty;
  48 using android::binder::Status;
  49 using android::fs_mgr::Fstab;
  50 using android::fs_mgr::ReadFstabFromFile;
  51 using android::hardware::hidl_string;
  52 using android::hardware::boot::V1_0::BoolResult;
  53 using android::hardware::boot::V1_0::CommandResult;
  54 using android::hardware::boot::V1_0::IBootControl;
  55 using android::hardware::boot::V1_0::Slot;
  56
  57 namespace android {
  58 namespace vold {
  59
  60 namespace {
  61 const std::string kMetadataCPFile = "/metadata/vold/checkpoint";
  62
  63 binder::Status error(const std::string& msg) {
  64     PLOG(ERROR) << msg;
  65     return binder::Status::fromServiceSpecificError(errno, String8(msg.c_str()));
  66 }
  67
  68 binder::Status error(int error, const std::string& msg) {
  69     LOG(ERROR) << msg;
  70     return binder::Status::fromServiceSpecificError(error, String8(msg.c_str()));
  71 }
  72
  73 bool setBowState(std::string const& block_device, std::string const& state) {
  74     std::string bow_device = fs_mgr_find_bow_device(block_device);
  75     if (bow_device.empty()) return false;
  76
  77     if (!android::base::WriteStringToFile(state, bow_device + "/bow/state")) {
  78         PLOG(ERROR) << "Failed to write to file " << bow_device + "/bow/state";
  79         return false;
  80     }
  81
  82     return true;
  83 }
  84
  85 }  // namespace
  86
  87 Status cp_supportsCheckpoint(bool& result) {
  88     result = false;
  89
  90     for (const auto& entry : fstab_default) {
  91         if (entry.fs_mgr_flags.checkpoint_blk || entry.fs_mgr_flags.checkpoint_fs) {
  92             result = true;
  93             return Status::ok();
  94         }
  95     }
  96     return Status::ok();
  97 }
  98
  99 Status cp_supportsBlockCheckpoint(bool& result) {
 100     result = false;
 101
 102     for (const auto& entry : fstab_default) {
 103         if (entry.fs_mgr_flags.checkpoint_blk) {
 104             result = true;
 105             return Status::ok();
 106         }
 107     }
 108     return Status::ok();
 109 }
 110
 111 Status cp_supportsFileCheckpoint(bool& result) {
 112     result = false;
 113
 114     for (const auto& entry : fstab_default) {
 115         if (entry.fs_mgr_flags.checkpoint_fs) {
 116             result = true;
 117             return Status::ok();
 118         }
 119     }
 120     return Status::ok();
 121 }
 122
 123 Status cp_startCheckpoint(int retry) {
 124     bool result;
 125     if (!cp_supportsCheckpoint(result).isOk() || !result)
 126         return error(ENOTSUP, "Checkpoints not supported");
 127
 128     if (retry < -1) return error(EINVAL, "Retry count must be more than -1");
 129     std::string content = std::to_string(retry + 1);
 130     if (retry == -1) {
 131         sp<IBootControl> module = IBootControl::getService();
 132         if (module) {
 133             std::string suffix;
 134             auto cb = [&suffix](hidl_string s) { suffix = s; };
 135             if (module->getSuffix(module->getCurrentSlot(), cb).isOk()) content += " " + suffix;
 136         }
 137     }
 138     if (!android::base::WriteStringToFile(content, kMetadataCPFile))
 139         return error("Failed to write checkpoint file");
 140     return Status::ok();
 141 }
 142
 143 namespace {
 144
 145 volatile bool isCheckpointing = false;
 146
 147 volatile bool needsCheckpointWasCalled = false;
 148
 149 // Protects isCheckpointing, needsCheckpointWasCalled and code that makes decisions based on status
 150 // of isCheckpointing
 151 std::mutex isCheckpointingLock;
 152 }
 153
 154 Status cp_commitChanges() {
 155     std::lock_guard<std::mutex> lock(isCheckpointingLock);
 156
 157     if (!isCheckpointing) {
 158         return Status::ok();
 159     }
 160     if (android::base::GetProperty("persist.vold.dont_commit_checkpoint", "0") == "1") {
 161         LOG(WARNING)
 162             << "NOT COMMITTING CHECKPOINT BECAUSE persist.vold.dont_commit_checkpoint IS 1";
 163         return Status::ok();
 164     }
 165     sp<IBootControl> module = IBootControl::getService();
 166     if (module) {
 167         CommandResult cr;
 168         module->markBootSuccessful([&cr](CommandResult result) { cr = result; });
 169         if (!cr.success)
 170             return error(EINVAL, "Error marking booted successfully: " + std::string(cr.errMsg));
 171         LOG(INFO) << "Marked slot as booted successfully.";
 172         // Clears the warm reset flag for next reboot.
 173         if (!SetProperty("ota.warm_reset", "0")) {
 174             LOG(WARNING) << "Failed to reset the warm reset flag";
 175         }
 176     }
 177     // Must take action for list of mounted checkpointed things here
 178     // To do this, we walk the list of mounted file systems.
 179     // But we also need to get the matching fstab entries to see
 180     // the original flags
 181     std::string err_str;
 182
 183     Fstab mounts;
 184     if (!ReadFstabFromFile("/proc/mounts", &mounts)) {
 185         return error(EINVAL, "Failed to get /proc/mounts");
 186     }
 187
 188     // Walk mounted file systems
 189     for (const auto& mount_rec : mounts) {
 190         const auto fstab_rec = GetEntryForMountPoint(&fstab_default, mount_rec.mount_point);
 191         if (!fstab_rec) continue;
 192
 193         if (fstab_rec->fs_mgr_flags.checkpoint_fs) {
 194             if (fstab_rec->fs_type == "f2fs") {
 195                 std::string options = mount_rec.fs_options + ",checkpoint=enable";
 196                 if (mount(mount_rec.blk_device.c_str(), mount_rec.mount_point.c_str(), "none",
 197                           MS_REMOUNT | fstab_rec->flags, options.c_str())) {
 198                     return error(EINVAL, "Failed to remount");
 199                 }
 200             }
 201         } else if (fstab_rec->fs_mgr_flags.checkpoint_blk) {
 202             if (!setBowState(mount_rec.blk_device, "2"))
 203                 return error(EINVAL, "Failed to set bow state");
 204         }
 205     }
 206     SetProperty("vold.checkpoint_committed", "1");
 207     LOG(INFO) << "Checkpoint has been committed.";
 208     isCheckpointing = false;
 209     if (!android::base::RemoveFileIfExists(kMetadataCPFile, &err_str))
 210         return error(err_str.c_str());
 211
 212     return Status::ok();
 213 }
 214
 215 namespace {
 216 void abort_metadata_file() {
 217     std::string oldContent, newContent;
 218     int retry = 0;
 219     struct stat st;
 220     int result = stat(kMetadataCPFile.c_str(), &st);
 221
 222     // If the file doesn't exist, we aren't managing a checkpoint retry counter
 223     if (result != 0) return;
 224     if (!android::base::ReadFileToString(kMetadataCPFile, &oldContent)) {
 225         PLOG(ERROR) << "Failed to read checkpoint file";
 226         return;
 227     }
 228     std::string retryContent = oldContent.substr(0, oldContent.find_first_of(" "));
 229
 230     if (!android::base::ParseInt(retryContent, &retry)) {
 231         PLOG(ERROR) << "Could not parse retry count";
 232         return;
 233     }
 234     if (retry > 0) {
 235         newContent = "0";
 236         if (!android::base::WriteStringToFile(newContent, kMetadataCPFile))
 237             PLOG(ERROR) << "Could not write checkpoint file";
 238     }
 239 }
 240 }  // namespace
 241
 242 void cp_abortChanges(const std::string& message, bool retry) {
 243     if (!cp_needsCheckpoint()) return;
 244     if (!retry) abort_metadata_file();
 245     android_reboot(ANDROID_RB_RESTART2, 0, message.c_str());
 246 }
 247
 248 bool cp_needsRollback() {
 249     std::string content;
 250     bool ret;
 251
 252     ret = android::base::ReadFileToString(kMetadataCPFile, &content);
 253     if (ret) {
 254         if (content == "0") return true;
 255         if (content.substr(0, 3) == "-1 ") {
 256             std::string oldSuffix = content.substr(3);
 257             sp<IBootControl> module = IBootControl::getService();
 258             std::string newSuffix;
 259
 260             if (module) {
 261                 auto cb = [&newSuffix](hidl_string s) { newSuffix = s; };
 262                 module->getSuffix(module->getCurrentSlot(), cb);
 263                 if (oldSuffix == newSuffix) return true;
 264             }
 265         }
 266     }
 267     return false;
 268 }
 269
 270 bool cp_needsCheckpoint() {
 271     std::lock_guard<std::mutex> lock(isCheckpointingLock);
 272
 273     // Make sure we only return true during boot. See b/138952436 for discussion
 274     if (needsCheckpointWasCalled) return isCheckpointing;
 275     needsCheckpointWasCalled = true;
 276
 277     bool ret;
 278     std::string content;
 279     sp<IBootControl> module = IBootControl::getService();
 280
 281     if (isCheckpointing) return isCheckpointing;
 282
 283     if (module && module->isSlotMarkedSuccessful(module->getCurrentSlot()) == BoolResult::FALSE) {
 284         isCheckpointing = true;
 285         return true;
 286     }
 287     ret = android::base::ReadFileToString(kMetadataCPFile, &content);
 288     if (ret) {
 289         ret = content != "0";
 290         isCheckpointing = ret;
 291         return ret;
 292     }
 293     return false;
 294 }
 295
 296 bool cp_isCheckpointing() {
 297     return isCheckpointing;
 298 }
 299
 300 namespace {
 301 const std::string kSleepTimeProp = "ro.sys.cp_msleeptime";
 302 const uint32_t msleeptime_default = 1000;  // 1 s
 303 const uint32_t max_msleeptime = 3600000;   // 1 h
 304
 305 const std::string kMinFreeBytesProp = "ro.sys.cp_min_free_bytes";
 306 const uint64_t min_free_bytes_default = 100 * (1 << 20);  // 100 MiB
 307
 308 const std::string kCommitOnFullProp = "ro.sys.cp_commit_on_full";
 309 const bool commit_on_full_default = true;
 310
 311 static void cp_healthDaemon(std::string mnt_pnt, std::string blk_device, bool is_fs_cp) {
 312     struct statvfs data;
 313     uint32_t msleeptime = GetUintProperty(kSleepTimeProp, msleeptime_default, max_msleeptime);
 314     uint64_t min_free_bytes =
 315         GetUintProperty(kMinFreeBytesProp, min_free_bytes_default, (uint64_t)-1);
 316     bool commit_on_full = GetBoolProperty(kCommitOnFullProp, commit_on_full_default);
 317
 318     struct timespec req;
 319     req.tv_sec = msleeptime / 1000;
 320     msleeptime %= 1000;
 321     req.tv_nsec = msleeptime * 1000000;
 322     while (isCheckpointing) {
 323         uint64_t free_bytes = 0;
 324         if (is_fs_cp) {
 325             statvfs(mnt_pnt.c_str(), &data);
 326             free_bytes = ((uint64_t) data.f_bavail) * data.f_frsize;
 327         } else {
 328             std::string bow_device = fs_mgr_find_bow_device(blk_device);
 329             if (!bow_device.empty()) {
 330                 std::string content;
 331                 if (android::base::ReadFileToString(bow_device + "/bow/free", &content)) {
 332                     free_bytes = std::strtoull(content.c_str(), NULL, 10);
 333                 }
 334             }
 335         }
 336         if (free_bytes < min_free_bytes) {
 337             if (commit_on_full) {
 338                 LOG(INFO) << "Low space for checkpointing. Commiting changes";
 339                 cp_commitChanges();
 340                 break;
 341             } else {
 342                 LOG(INFO) << "Low space for checkpointing. Rebooting";
 343                 cp_abortChanges("checkpoint,low_space", false);
 344                 break;
 345             }
 346         }
 347         nanosleep(&req, NULL);
 348     }
 349 }
 350
 351 }  // namespace
 352
 353 Status cp_prepareCheckpoint() {
 354     // Log to notify CTS - see b/137924328 for context
 355     LOG(INFO) << "cp_prepareCheckpoint called";
 356     std::lock_guard<std::mutex> lock(isCheckpointingLock);
 357     if (!isCheckpointing) {
 358         return Status::ok();
 359     }
 360
 361     Fstab mounts;
 362     if (!ReadFstabFromFile("/proc/mounts", &mounts)) {
 363         return error(EINVAL, "Failed to get /proc/mounts");
 364     }
 365
 366     for (const auto& mount_rec : mounts) {
 367         const auto fstab_rec = GetEntryForMountPoint(&fstab_default, mount_rec.mount_point);
 368         if (!fstab_rec) continue;
 369
 370         if (fstab_rec->fs_mgr_flags.checkpoint_blk) {
 371             android::base::unique_fd fd(
 372                 TEMP_FAILURE_RETRY(open(mount_rec.mount_point.c_str(), O_RDONLY | O_CLOEXEC)));
 373             if (fd == -1) {
 374                 PLOG(ERROR) << "Failed to open mount point" << mount_rec.mount_point;
 375                 continue;
 376             }
 377
 378             struct fstrim_range range = {};
 379             range.len = ULLONG_MAX;
 380             nsecs_t start = systemTime(SYSTEM_TIME_BOOTTIME);
 381             if (ioctl(fd, FITRIM, &range)) {
 382                 PLOG(ERROR) << "Failed to trim " << mount_rec.mount_point;
 383                 continue;
 384             }
 385             nsecs_t time = systemTime(SYSTEM_TIME_BOOTTIME) - start;
 386             LOG(INFO) << "Trimmed " << range.len << " bytes on " << mount_rec.mount_point << " in "
 387                       << nanoseconds_to_milliseconds(time) << "ms for checkpoint";
 388
 389             setBowState(mount_rec.blk_device, "1");
 390         }
 391         if (fstab_rec->fs_mgr_flags.checkpoint_blk || fstab_rec->fs_mgr_flags.checkpoint_fs) {
 392             std::thread(cp_healthDaemon, std::string(mount_rec.mount_point),
 393                         std::string(mount_rec.blk_device),
 394                         fstab_rec->fs_mgr_flags.checkpoint_fs == 1)
 395                 .detach();
 396         }
 397     }
 398     return Status::ok();
 399 }
 400
 401 namespace {
 402 const int kSectorSize = 512;
 403
 404 typedef uint64_t sector_t;
 405
 406 struct log_entry {
 407     sector_t source;  // in sectors of size kSectorSize
 408     sector_t dest;    // in sectors of size kSectorSize
 409     uint32_t size;    // in bytes
 410     uint32_t checksum;
 411 } __attribute__((packed));
 412
 413 struct log_sector_v1_0 {
 414     uint32_t magic;
 415     uint16_t header_version;
 416     uint16_t header_size;
 417     uint32_t block_size;
 418     uint32_t count;
 419     uint32_t sequence;
 420     uint64_t sector0;
 421 } __attribute__((packed));
 422
 423 // MAGIC is BOW in ascii
 424 const int kMagic = 0x00574f42;
 425 // Partially restored MAGIC is WOB in ascii
 426 const int kPartialRestoreMagic = 0x00424f57;
 427
 428 void crc32(const void* data, size_t n_bytes, uint32_t* crc) {
 429     static uint32_t table[0x100] = {
 430         0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535,
 431         0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD,
 432         0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D,
 433         0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
 434         0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
 435         0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
 436         0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC,
 437         0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
 438         0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB,
 439         0xB6662D3D,
 440
 441         0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5,
 442         0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
 443         0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED,
 444         0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
 445         0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074,
 446         0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC,
 447         0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C,
 448         0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
 449         0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B,
 450         0xC0BA6CAD,
 451
 452         0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615,
 453         0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D,
 454         0x0A00AE27, 0x7D079EB1, 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D,
 455         0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
 456         0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4,
 457         0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C,
 458         0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, 0xCB61B38C,
 459         0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
 460         0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B,
 461         0x5BDEAE1D,
 462
 463         0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785,
 464         0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D,
 465         0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD,
 466         0xF6B9265B, 0x6FB077E1, 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
 467         0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354,
 468         0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
 469         0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, 0xBDBDF21C,
 470         0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
 471         0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B,
 472         0x2D02EF8D};
 473
 474     for (size_t i = 0; i < n_bytes; ++i) {
 475         *crc ^= ((uint8_t*)data)[i];
 476         *crc = table[(uint8_t)*crc] ^ *crc >> 8;
 477     }
 478 }
 479
 480 // A map of relocations.
 481 // The map must be initialized so that relocations[0] = 0
 482 // During restore, we replay the log records in reverse, copying from dest to
 483 // source
 484 // To validate, we must be able to read the 'dest' sectors as though they had
 485 // been copied but without actually copying. This map represents how the sectors
 486 // would have been moved. To read a sector s, find the index <= s and read
 487 // relocations[index] + s - index
 488 typedef std::map<sector_t, sector_t> Relocations;
 489
 490 void relocate(Relocations& relocations, sector_t dest, sector_t source, int count) {
 491     // Find first one we're equal to or greater than
 492     auto s = --relocations.upper_bound(source);
 493
 494     // Take slice
 495     Relocations slice;
 496     slice[dest] = source - s->first + s->second;
 497     ++s;
 498
 499     // Add rest of elements
 500     for (; s != relocations.end() && s->first < source + count; ++s)
 501         slice[dest - source + s->first] = s->second;
 502
 503     // Split range at end of dest
 504     auto dest_end = --relocations.upper_bound(dest + count);
 505     relocations[dest + count] = dest + count - dest_end->first + dest_end->second;
 506
 507     // Remove all elements in [dest, dest + count)
 508     relocations.erase(relocations.lower_bound(dest), relocations.lower_bound(dest + count));
 509
 510     // Add new elements
 511     relocations.insert(slice.begin(), slice.end());
 512 }
 513
 514 // A map of sectors that have been written to.
 515 // The final entry must always be False.
 516 // When we restart the restore after an interruption, we must take care that
 517 // when we copy from dest to source, that the block we copy to was not
 518 // previously copied from.
 519 // i e. A->B C->A; If we replay this sequence, we end up copying C->B
 520 // We must save our partial result whenever we finish a page, or when we copy
 521 // to a location that was copied from earlier (our source is an earlier dest)
 522 typedef std::map<sector_t, bool> Used_Sectors;
 523
 524 bool checkCollision(Used_Sectors& used_sectors, sector_t start, sector_t end) {
 525     auto second_overlap = used_sectors.upper_bound(start);
 526     auto first_overlap = --second_overlap;
 527
 528     if (first_overlap->second) {
 529         return true;
 530     } else if (second_overlap != used_sectors.end() && second_overlap->first < end) {
 531         return true;
 532     }
 533     return false;
 534 }
 535
 536 void markUsed(Used_Sectors& used_sectors, sector_t start, sector_t end) {
 537     auto start_pos = used_sectors.insert_or_assign(start, true).first;
 538     auto end_pos = used_sectors.insert_or_assign(end, false).first;
 539
 540     if (start_pos == used_sectors.begin() || !std::prev(start_pos)->second) {
 541         start_pos++;
 542     }
 543     if (std::next(end_pos) != used_sectors.end() && !std::next(end_pos)->second) {
 544         end_pos++;
 545     }
 546     if (start_pos->first < end_pos->first) {
 547         used_sectors.erase(start_pos, end_pos);
 548     }
 549 }
 550
 551 // Restores the given log_entry's data from dest -> source
 552 // If that entry is a log sector, set the magic to kPartialRestoreMagic and flush.
 553 void restoreSector(int device_fd, Used_Sectors& used_sectors, std::vector<char>& ls_buffer,
 554                    log_entry* le, std::vector<char>& buffer) {
 555     log_sector_v1_0& ls = *reinterpret_cast<log_sector_v1_0*>(&ls_buffer[0]);
 556     uint32_t index = le - ((log_entry*)&ls_buffer[ls.header_size]);
 557     int count = (le->size - 1) / kSectorSize + 1;
 558
 559     if (checkCollision(used_sectors, le->source, le->source + count)) {
 560         fsync(device_fd);
 561         lseek64(device_fd, 0, SEEK_SET);
 562         ls.count = index + 1;
 563         ls.magic = kPartialRestoreMagic;
 564         write(device_fd, &ls_buffer[0], ls.block_size);
 565         fsync(device_fd);
 566         used_sectors.clear();
 567         used_sectors[0] = false;
 568     }
 569
 570     markUsed(used_sectors, le->dest, le->dest + count);
 571
 572     if (index == 0 && ls.sequence != 0) {
 573         log_sector_v1_0* next = reinterpret_cast<log_sector_v1_0*>(&buffer[0]);
 574         if (next->magic == kMagic) {
 575             next->magic = kPartialRestoreMagic;
 576         }
 577     }
 578
 579     lseek64(device_fd, le->source * kSectorSize, SEEK_SET);
 580     write(device_fd, &buffer[0], le->size);
 581
 582     if (index == 0) {
 583         fsync(device_fd);
 584     }
 585 }
 586
 587 // Read from the device
 588 // If we are validating, the read occurs as though the relocations had happened
 589 std::vector<char> relocatedRead(int device_fd, Relocations const& relocations, bool validating,
 590                                 sector_t sector, uint32_t size, uint32_t block_size) {
 591     if (!validating) {
 592         std::vector<char> buffer(size);
 593         lseek64(device_fd, sector * kSectorSize, SEEK_SET);
 594         read(device_fd, &buffer[0], size);
 595         return buffer;
 596     }
 597
 598     std::vector<char> buffer(size);
 599     for (uint32_t i = 0; i < size; i += block_size, sector += block_size / kSectorSize) {
 600         auto relocation = --relocations.upper_bound(sector);
 601         lseek64(device_fd, (sector + relocation->second - relocation->first) * kSectorSize,
 602                 SEEK_SET);
 603         read(device_fd, &buffer[i], block_size);
 604     }
 605
 606     return buffer;
 607 }
 608
 609 }  // namespace
 610
 611 Status cp_restoreCheckpoint(const std::string& blockDevice, int restore_limit) {
 612     bool validating = true;
 613     std::string action = "Validating";
 614     int restore_count = 0;
 615
 616     for (;;) {
 617         Relocations relocations;
 618         relocations[0] = 0;
 619         Status status = Status::ok();
 620
 621         LOG(INFO) << action << " checkpoint on " << blockDevice;
 622         base::unique_fd device_fd(open(blockDevice.c_str(), O_RDWR | O_CLOEXEC));
 623         if (device_fd < 0) return error("Cannot open " + blockDevice);
 624
 625         log_sector_v1_0 original_ls;
 626         read(device_fd, reinterpret_cast<char*>(&original_ls), sizeof(original_ls));
 627         if (original_ls.magic == kPartialRestoreMagic) {
 628             validating = false;
 629             action = "Restoring";
 630         } else if (original_ls.magic != kMagic) {
 631             return error(EINVAL, "No magic");
 632         }
 633
 634         LOG(INFO) << action << " " << original_ls.sequence << " log sectors";
 635
 636         for (int sequence = original_ls.sequence; sequence >= 0 && status.isOk(); sequence--) {
 637             auto ls_buffer = relocatedRead(device_fd, relocations, validating, 0,
 638                                            original_ls.block_size, original_ls.block_size);
 639             log_sector_v1_0& ls = *reinterpret_cast<log_sector_v1_0*>(&ls_buffer[0]);
 640
 641             Used_Sectors used_sectors;
 642             used_sectors[0] = false;
 643
 644             if (ls.magic != kMagic && (ls.magic != kPartialRestoreMagic || validating)) {
 645                 status = error(EINVAL, "No magic");
 646                 break;
 647             }
 648
 649             if (ls.block_size != original_ls.block_size) {
 650                 status = error(EINVAL, "Block size mismatch");
 651                 break;
 652             }
 653
 654             if ((int)ls.sequence != sequence) {
 655                 status = error(EINVAL, "Expecting log sector " + std::to_string(sequence) +
 656                                            " but got " + std::to_string(ls.sequence));
 657                 break;
 658             }
 659
 660             LOG(INFO) << action << " from log sector " << ls.sequence;
 661             for (log_entry* le =
 662                      reinterpret_cast<log_entry*>(&ls_buffer[ls.header_size]) + ls.count - 1;
 663                  le >= reinterpret_cast<log_entry*>(&ls_buffer[ls.header_size]); --le) {
 664                 // This is very noisy - limit to DEBUG only
 665                 LOG(VERBOSE) << action << " " << le->size << " bytes from sector " << le->dest
 666                              << " to " << le->source << " with checksum " << std::hex
 667                              << le->checksum;
 668
 669                 auto buffer = relocatedRead(device_fd, relocations, validating, le->dest, le->size,
 670                                             ls.block_size);
 671                 uint32_t checksum = le->source / (ls.block_size / kSectorSize);
 672                 for (size_t i = 0; i < le->size; i += ls.block_size) {
 673                     crc32(&buffer[i], ls.block_size, &checksum);
 674                 }
 675
 676                 if (le->checksum && checksum != le->checksum) {
 677                     status = error(EINVAL, "Checksums don't match");
 678                     break;
 679                 }
 680
 681                 if (validating) {
 682                     relocate(relocations, le->source, le->dest, (le->size - 1) / kSectorSize + 1);
 683                 } else {
 684                     restoreSector(device_fd, used_sectors, ls_buffer, le, buffer);
 685                     restore_count++;
 686                     if (restore_limit && restore_count >= restore_limit) {
 687                         status = error(EAGAIN, "Hit the test limit");
 688                         break;
 689                     }
 690                 }
 691             }
 692         }
 693
 694         if (!status.isOk()) {
 695             if (!validating) {
 696                 LOG(ERROR) << "Checkpoint restore failed even though checkpoint validation passed";
 697                 return status;
 698             }
 699
 700             LOG(WARNING) << "Checkpoint validation failed - attempting to roll forward";
 701             auto buffer = relocatedRead(device_fd, relocations, false, original_ls.sector0,
 702                                         original_ls.block_size, original_ls.block_size);
 703             lseek64(device_fd, 0, SEEK_SET);
 704             write(device_fd, &buffer[0], original_ls.block_size);
 705             return Status::ok();
 706         }
 707
 708         if (!validating) break;
 709
 710         validating = false;
 711         action = "Restoring";
 712     }
 713
 714     return Status::ok();
 715 }
 716
 717 Status cp_markBootAttempt() {
 718     std::string oldContent, newContent;
 719     int retry = 0;
 720     struct stat st;
 721     int result = stat(kMetadataCPFile.c_str(), &st);
 722
 723     // If the file doesn't exist, we aren't managing a checkpoint retry counter
 724     if (result != 0) return Status::ok();
 725     if (!android::base::ReadFileToString(kMetadataCPFile, &oldContent))
 726         return error("Failed to read checkpoint file");
 727     std::string retryContent = oldContent.substr(0, oldContent.find_first_of(" "));
 728
 729     if (!android::base::ParseInt(retryContent, &retry))
 730         return error(EINVAL, "Could not parse retry count");
 731     if (retry > 0) {
 732         retry--;
 733
 734         newContent = std::to_string(retry);
 735         if (!android::base::WriteStringToFile(newContent, kMetadataCPFile))
 736             return error("Could not write checkpoint file");
 737     }
 738     return Status::ok();
 739 }
 740
 741 void cp_resetCheckpoint() {
 742     std::lock_guard<std::mutex> lock(isCheckpointingLock);
 743     needsCheckpointWasCalled = false;
 744 }
 745
 746 }  // namespace vold
 747 }  // namespace android