diff options
Diffstat (limited to '')
| -rw-r--r-- | otautil/Android.bp | 9 | ||||
| -rw-r--r-- | otautil/Android.mk | 2 | ||||
| -rw-r--r-- | otautil/DirUtil.cpp | 115 | ||||
| -rw-r--r-- | otautil/SysUtil.cpp | 9 | ||||
| -rw-r--r-- | otautil/ThermalUtil.cpp | 4 | ||||
| -rw-r--r-- | otautil/ZipUtil.cpp | 2 | ||||
| -rw-r--r-- | otautil/cache_location.cpp | 31 | ||||
| -rw-r--r-- | otautil/include/otautil/DirUtil.h (renamed from otautil/DirUtil.h) | 30 | ||||
| -rw-r--r-- | otautil/include/otautil/SysUtil.h (renamed from otautil/SysUtil.h) | 0 | ||||
| -rw-r--r-- | otautil/include/otautil/ThermalUtil.h (renamed from otautil/ThermalUtil.h) | 0 | ||||
| -rw-r--r-- | otautil/include/otautil/cache_location.h | 69 | ||||
| -rw-r--r-- | otautil/include/otautil/error_code.h (renamed from error_code.h) | 13 | ||||
| -rw-r--r-- | otautil/include/otautil/print_sha1.h (renamed from print_sha1.h) | 26 | ||||
| -rw-r--r-- | otautil/include/otautil/rangeset.h | 170 | ||||
| -rw-r--r-- | otautil/rangeset.cpp | 267 |
15 files changed, 695 insertions, 52 deletions
diff --git a/otautil/Android.bp b/otautil/Android.bp index 0b2314374..a109d39b6 100644 --- a/otautil/Android.bp +++ b/otautil/Android.bp @@ -15,11 +15,15 @@ cc_library_static { name: "libotautil", + host_supported: true, + srcs: [ "SysUtil.cpp", "DirUtil.cpp", "ZipUtil.cpp", "ThermalUtil.cpp", + "cache_location.cpp", + "rangeset.cpp", ], static_libs: [ @@ -28,7 +32,12 @@ cc_library_static { ], cflags: [ + "-D_FILE_OFFSET_BITS=64", "-Werror", "-Wall", ], + + export_include_dirs: [ + "include", + ], } diff --git a/otautil/Android.mk b/otautil/Android.mk index 45e0f765d..feb468de5 100644 --- a/otautil/Android.mk +++ b/otautil/Android.mk @@ -36,4 +36,6 @@ LOCAL_CFLAGS := \ -Werror \ -Wall +LOCAL_C_INCLUDES := include + include $(BUILD_STATIC_LIBRARY) diff --git a/otautil/DirUtil.cpp b/otautil/DirUtil.cpp index e08e360c0..8d364b74f 100644 --- a/otautil/DirUtil.cpp +++ b/otautil/DirUtil.cpp @@ -14,24 +14,107 @@ * limitations under the License. */ -#include "DirUtil.h" +#include "otautil/DirUtil.h" +#include <dirent.h> +#include <errno.h> #include <stdlib.h> -#include <string.h> -#include <stdio.h> -#include <sys/types.h> #include <sys/stat.h> +#include <sys/types.h> #include <unistd.h> -#include <errno.h> -#include <dirent.h> -#include <limits.h> +#include <utime.h> #include <string> #include <selinux/label.h> #include <selinux/selinux.h> -typedef enum { DMISSING, DDIR, DILLEGAL } DirStatus; +enum class DirStatus { DMISSING, DDIR, DILLEGAL }; + +static DirStatus dir_status(const std::string& path) { + struct stat sb; + if (stat(path.c_str(), &sb) == 0) { + // Something's there; make sure it's a directory. + if (S_ISDIR(sb.st_mode)) { + return DirStatus::DDIR; + } + errno = ENOTDIR; + return DirStatus::DILLEGAL; + } else if (errno != ENOENT) { + // Something went wrong, or something in the path is bad. Can't do anything in this situation. + return DirStatus::DILLEGAL; + } + return DirStatus::DMISSING; +} + +int mkdir_recursively(const std::string& input_path, mode_t mode, bool strip_filename, + const selabel_handle* sehnd) { + // Check for an empty string before we bother making any syscalls. + if (input_path.empty()) { + errno = ENOENT; + return -1; + } + + // Allocate a path that we can modify; stick a slash on the end to make things easier. + std::string path = input_path; + if (strip_filename) { + // Strip everything after the last slash. + size_t pos = path.rfind('/'); + if (pos == std::string::npos) { + errno = ENOENT; + return -1; + } + path.resize(pos + 1); + } else { + // Make sure that the path ends in a slash. + path.push_back('/'); + } + + // See if it already exists. + DirStatus ds = dir_status(path); + if (ds == DirStatus::DDIR) { + return 0; + } else if (ds == DirStatus::DILLEGAL) { + return -1; + } + + // Walk up the path from the root and make each level. + size_t prev_end = 0; + while (prev_end < path.size()) { + size_t next_end = path.find('/', prev_end + 1); + if (next_end == std::string::npos) { + break; + } + std::string dir_path = path.substr(0, next_end); + // Check this part of the path and make a new directory if necessary. + switch (dir_status(dir_path)) { + case DirStatus::DILLEGAL: + // Could happen if some other process/thread is messing with the filesystem. + return -1; + case DirStatus::DMISSING: { + char* secontext = nullptr; + if (sehnd) { + selabel_lookup(const_cast<selabel_handle*>(sehnd), &secontext, dir_path.c_str(), mode); + setfscreatecon(secontext); + } + int err = mkdir(dir_path.c_str(), mode); + if (secontext) { + freecon(secontext); + setfscreatecon(nullptr); + } + if (err != 0) { + return -1; + } + break; + } + default: + // Already exists. + break; + } + prev_end = next_end; + } + return 0; +} static DirStatus getPathDirStatus(const char *path) @@ -44,17 +127,17 @@ getPathDirStatus(const char *path) /* Something's there; make sure it's a directory. */ if (S_ISDIR(st.st_mode)) { - return DDIR; + return DirStatus::DDIR; } errno = ENOTDIR; - return DILLEGAL; + return DirStatus::DILLEGAL; } else if (errno != ENOENT) { /* Something went wrong, or something in the path * is bad. Can't do anything in this situation. */ - return DILLEGAL; + return DirStatus::DILLEGAL; } - return DMISSING; + return DirStatus::DMISSING; } int @@ -90,9 +173,9 @@ dirCreateHierarchy(const char *path, int mode, /* See if it already exists. */ ds = getPathDirStatus(cpath.c_str()); - if (ds == DDIR) { + if (ds == DirStatus::DDIR) { return 0; - } else if (ds == DILLEGAL) { + } else if (ds == DirStatus::DILLEGAL) { return -1; } @@ -124,12 +207,12 @@ dirCreateHierarchy(const char *path, int mode, * if necessary. */ ds = getPathDirStatus(path_start); - if (ds == DILLEGAL) { + if (ds == DirStatus::DILLEGAL) { /* Could happen if some other process/thread is * messing with the filesystem. */ return -1; - } else if (ds == DMISSING) { + } else if (ds == DirStatus::DMISSING) { int err; char *secontext = NULL; diff --git a/otautil/SysUtil.cpp b/otautil/SysUtil.cpp index dfa215073..48336ad07 100644 --- a/otautil/SysUtil.cpp +++ b/otautil/SysUtil.cpp @@ -14,8 +14,9 @@ * limitations under the License. */ -#include "SysUtil.h" +#include "otautil/SysUtil.h" +#include <errno.h> // TEMP_FAILURE_RETRY #include <fcntl.h> #include <stdint.h> // SIZE_MAX #include <sys/mman.h> @@ -100,7 +101,7 @@ bool MemMapping::MapBlockFile(const std::string& filename) { } // Reserve enough contiguous address space for the whole file. - void* reserve = mmap64(nullptr, blocks * blksize, PROT_NONE, MAP_PRIVATE | MAP_ANON, -1, 0); + void* reserve = mmap(nullptr, blocks * blksize, PROT_NONE, MAP_PRIVATE | MAP_ANON, -1, 0); if (reserve == MAP_FAILED) { PLOG(ERROR) << "failed to reserve address space"; return false; @@ -135,8 +136,8 @@ bool MemMapping::MapBlockFile(const std::string& filename) { break; } - void* range_start = mmap64(next, range_size, PROT_READ, MAP_PRIVATE | MAP_FIXED, fd, - static_cast<off64_t>(start) * blksize); + void* range_start = mmap(next, range_size, PROT_READ, MAP_PRIVATE | MAP_FIXED, fd, + static_cast<off_t>(start) * blksize); if (range_start == MAP_FAILED) { PLOG(ERROR) << "failed to map range " << i << ": " << line; success = false; diff --git a/otautil/ThermalUtil.cpp b/otautil/ThermalUtil.cpp index 13d36432a..5d9bd45c0 100644 --- a/otautil/ThermalUtil.cpp +++ b/otautil/ThermalUtil.cpp @@ -14,7 +14,7 @@ * limitations under the License. */ -#include "ThermalUtil.h" +#include "otautil/ThermalUtil.h" #include <dirent.h> #include <stdio.h> @@ -77,4 +77,4 @@ int GetMaxValueFromThermalZone() { } LOG(INFO) << "current maximum temperature: " << max_temperature; return max_temperature; -}
\ No newline at end of file +} diff --git a/otautil/ZipUtil.cpp b/otautil/ZipUtil.cpp index 714c956ed..a2d0cbac5 100644 --- a/otautil/ZipUtil.cpp +++ b/otautil/ZipUtil.cpp @@ -28,7 +28,7 @@ #include <selinux/selinux.h> #include <ziparchive/zip_archive.h> -#include "DirUtil.h" +#include "otautil/DirUtil.h" static constexpr mode_t UNZIP_DIRMODE = 0755; static constexpr mode_t UNZIP_FILEMODE = 0644; diff --git a/otautil/cache_location.cpp b/otautil/cache_location.cpp new file mode 100644 index 000000000..8ddefec5e --- /dev/null +++ b/otautil/cache_location.cpp @@ -0,0 +1,31 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "otautil/cache_location.h" + +constexpr const char kDefaultCacheTempSource[] = "/cache/saved.file"; +constexpr const char kDefaultLastCommandFile[] = "/cache/recovery/last_command"; +constexpr const char kDefaultStashDirectoryBase[] = "/cache/recovery"; + +CacheLocation& CacheLocation::location() { + static CacheLocation cache_location; + return cache_location; +} + +CacheLocation::CacheLocation() + : cache_temp_source_(kDefaultCacheTempSource), + last_command_file_(kDefaultLastCommandFile), + stash_directory_base_(kDefaultStashDirectoryBase) {} diff --git a/otautil/DirUtil.h b/otautil/include/otautil/DirUtil.h index 85b83c387..e3d021971 100644 --- a/otautil/DirUtil.h +++ b/otautil/include/otautil/DirUtil.h @@ -14,18 +14,28 @@ * limitations under the License. */ -#ifndef MINZIP_DIRUTIL_H_ -#define MINZIP_DIRUTIL_H_ +#ifndef OTAUTIL_DIRUTIL_H_ +#define OTAUTIL_DIRUTIL_H_ -#include <stdbool.h> -#include <utime.h> +#include <sys/stat.h> // mode_t -#ifdef __cplusplus -extern "C" { -#endif +#include <string> struct selabel_handle; +// Like "mkdir -p", try to guarantee that all directories specified in path are present, creating as +// many directories as necessary. The specified mode is passed to all mkdir calls; no modifications +// are made to umask. +// +// If strip_filename is set, everything after the final '/' is stripped before creating the +// directory +// hierarchy. +// +// Returns 0 on success; returns -1 (and sets errno) on failure (usually if some element of path is +// not a directory). +int mkdir_recursively(const std::string& path, mode_t mode, bool strip_filename, + const struct selabel_handle* sehnd); + /* Like "mkdir -p", try to guarantee that all directories * specified in path are present, creating as many directories * as necessary. The specified mode is passed to all mkdir @@ -47,8 +57,4 @@ int dirCreateHierarchy(const char *path, int mode, */ int dirUnlinkHierarchy(const char *path); -#ifdef __cplusplus -} -#endif - -#endif // MINZIP_DIRUTIL_H_ +#endif // OTAUTIL_DIRUTIL_H_ diff --git a/otautil/SysUtil.h b/otautil/include/otautil/SysUtil.h index 52f6d20a7..52f6d20a7 100644 --- a/otautil/SysUtil.h +++ b/otautil/include/otautil/SysUtil.h diff --git a/otautil/ThermalUtil.h b/otautil/include/otautil/ThermalUtil.h index 43ab55940..43ab55940 100644 --- a/otautil/ThermalUtil.h +++ b/otautil/include/otautil/ThermalUtil.h diff --git a/otautil/include/otautil/cache_location.h b/otautil/include/otautil/cache_location.h new file mode 100644 index 000000000..f2f663816 --- /dev/null +++ b/otautil/include/otautil/cache_location.h @@ -0,0 +1,69 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _OTAUTIL_OTAUTIL_CACHE_LOCATION_H_ +#define _OTAUTIL_OTAUTIL_CACHE_LOCATION_H_ + +#include <string> + +#include "android-base/macros.h" + +// A singleton class to maintain the update related locations. The locations should be only set +// once at the start of the program. +class CacheLocation { + public: + static CacheLocation& location(); + + // getter and setter functions. + std::string cache_temp_source() const { + return cache_temp_source_; + } + void set_cache_temp_source(const std::string& temp_source) { + cache_temp_source_ = temp_source; + } + + std::string last_command_file() const { + return last_command_file_; + } + void set_last_command_file(const std::string& last_command) { + last_command_file_ = last_command; + } + + std::string stash_directory_base() const { + return stash_directory_base_; + } + void set_stash_directory_base(const std::string& base) { + stash_directory_base_ = base; + } + + private: + CacheLocation(); + DISALLOW_COPY_AND_ASSIGN(CacheLocation); + + // When there isn't enough room on the target filesystem to hold the patched version of the file, + // we copy the original here and delete it to free up space. If the expected source file doesn't + // exist, or is corrupted, we look to see if the cached file contains the bits we want and use it + // as the source instead. The default location for the cached source is "/cache/saved.file". + std::string cache_temp_source_; + + // Location to save the last command that stashes blocks. + std::string last_command_file_; + + // The base directory to write stashes during update. + std::string stash_directory_base_; +}; + +#endif // _OTAUTIL_OTAUTIL_CACHE_LOCATION_H_ diff --git a/error_code.h b/otautil/include/otautil/error_code.h index 9fe047c91..b0ff42d8d 100644 --- a/error_code.h +++ b/otautil/include/otautil/error_code.h @@ -17,7 +17,7 @@ #ifndef _ERROR_CODE_H_ #define _ERROR_CODE_H_ -enum ErrorCode { +enum ErrorCode : int { kNoError = -1, kLowBattery = 20, kZipVerificationFailure, @@ -25,9 +25,12 @@ enum ErrorCode { kBootreasonInBlacklist, kPackageCompatibilityFailure, kScriptExecutionFailure, + kMapFileFailure, + kForkUpdateBinaryFailure, + kUpdateBinaryCommandFailure, }; -enum CauseCode { +enum CauseCode : int { kNoCause = -1, kArgsParsingFailure = 100, kStashCreationFailure, @@ -48,7 +51,7 @@ enum CauseCode { kVendorFailure = 200 }; -enum UncryptErrorCode { +enum UncryptErrorCode : int { kUncryptNoError = -1, kUncryptErrorPlaceholder = 50, kUncryptTimeoutError = 100, @@ -68,6 +71,8 @@ enum UncryptErrorCode { kUncryptFileCloseError, kUncryptFileRenameError, kUncryptPackageMissingError, + kUncryptRealpathFindError, + kUncryptBlockDeviceFindError, }; -#endif // _ERROR_CODE_H_ +#endif // _ERROR_CODE_H_ diff --git a/print_sha1.h b/otautil/include/otautil/print_sha1.h index 1f8589519..03a8d292a 100644 --- a/print_sha1.h +++ b/otautil/include/otautil/print_sha1.h @@ -23,25 +23,25 @@ #include <openssl/sha.h> static std::string print_sha1(const uint8_t* sha1, size_t len) { - const char* hex = "0123456789abcdef"; - std::string result = ""; - for (size_t i = 0; i < len; ++i) { - result.push_back(hex[(sha1[i]>>4) & 0xf]); - result.push_back(hex[sha1[i] & 0xf]); - } - return result; + const char* hex = "0123456789abcdef"; + std::string result = ""; + for (size_t i = 0; i < len; ++i) { + result.push_back(hex[(sha1[i] >> 4) & 0xf]); + result.push_back(hex[sha1[i] & 0xf]); + } + return result; } -static std::string print_sha1(const uint8_t sha1[SHA_DIGEST_LENGTH]) { - return print_sha1(sha1, SHA_DIGEST_LENGTH); +[[maybe_unused]] static std::string print_sha1(const uint8_t sha1[SHA_DIGEST_LENGTH]) { + return print_sha1(sha1, SHA_DIGEST_LENGTH); } -static std::string short_sha1(const uint8_t sha1[SHA_DIGEST_LENGTH]) { - return print_sha1(sha1, 4); +[[maybe_unused]] static std::string short_sha1(const uint8_t sha1[SHA_DIGEST_LENGTH]) { + return print_sha1(sha1, 4); } -static std::string print_hex(const uint8_t* bytes, size_t len) { - return print_sha1(bytes, len); +[[maybe_unused]] static std::string print_hex(const uint8_t* bytes, size_t len) { + return print_sha1(bytes, len); } #endif // RECOVERY_PRINT_SHA1_H diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h new file mode 100644 index 000000000..e91d02ca6 --- /dev/null +++ b/otautil/include/otautil/rangeset.h @@ -0,0 +1,170 @@ +/* + * Copyright (C) 2017 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include <stddef.h> + +#include <string> +#include <utility> +#include <vector> + +using Range = std::pair<size_t, size_t>; + +class RangeSet { + public: + RangeSet() : blocks_(0) {} + + explicit RangeSet(std::vector<Range>&& pairs); + + // Parses the given string into a RangeSet. Returns the parsed RangeSet, or an empty RangeSet on + // errors. + static RangeSet Parse(const std::string& range_text); + + // Appends the given Range to the current RangeSet. + bool PushBack(Range range); + + // Clears all the ranges from the RangeSet. + void Clear(); + + std::string ToString() const; + + // Gets the block number for the i-th (starting from 0) block in the RangeSet. + size_t GetBlockNumber(size_t idx) const; + + // Returns whether the current RangeSet overlaps with other. RangeSet has half-closed half-open + // bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" and "5,7" are not overlapped. + bool Overlaps(const RangeSet& other) const; + + // Returns a vector of RangeSets that contain the same set of blocks represented by the current + // RangeSet. The RangeSets in the vector contain similar number of blocks, with a maximum delta + // of 1-block between any two of them. For example, 14 blocks would be split into 4 + 4 + 3 + 3, + // as opposed to 4 + 4 + 4 + 2. If the total number of blocks (T) is less than groups, it + // returns a vector of T 1-block RangeSets. Otherwise the number of the returned RangeSets must + // equal to groups. The current RangeSet remains intact after the split. + std::vector<RangeSet> Split(size_t groups) const; + + // Returns the number of Range's in this RangeSet. + size_t size() const { + return ranges_.size(); + } + + // Returns the total number of blocks in this RangeSet. + size_t blocks() const { + return blocks_; + } + + std::vector<Range>::const_iterator cbegin() const { + return ranges_.cbegin(); + } + + std::vector<Range>::const_iterator cend() const { + return ranges_.cend(); + } + + std::vector<Range>::iterator begin() { + return ranges_.begin(); + } + + std::vector<Range>::iterator end() { + return ranges_.end(); + } + + std::vector<Range>::const_iterator begin() const { + return ranges_.begin(); + } + + std::vector<Range>::const_iterator end() const { + return ranges_.end(); + } + + // Reverse const iterators for MoveRange(). + std::vector<Range>::const_reverse_iterator crbegin() const { + return ranges_.crbegin(); + } + + std::vector<Range>::const_reverse_iterator crend() const { + return ranges_.crend(); + } + + // Returns whether the RangeSet is valid (i.e. non-empty). + explicit operator bool() const { + return !ranges_.empty(); + } + + const Range& operator[](size_t i) const { + return ranges_[i]; + } + + bool operator==(const RangeSet& other) const { + // The orders of Range's matter. "4,1,5,8,10" != "4,8,10,1,5". + return (ranges_ == other.ranges_); + } + + bool operator!=(const RangeSet& other) const { + return ranges_ != other.ranges_; + } + + protected: + // Actual limit for each value and the total number are both INT_MAX. + std::vector<Range> ranges_; + size_t blocks_; +}; + +// The class is a sorted version of a RangeSet; and it's useful in imgdiff to split the input +// files when we're handling large zip files. Specifically, we can treat the input file as a +// continuous RangeSet (i.e. RangeSet("0-99") for a 100 blocks file); and break it down into +// several smaller chunks based on the zip entries. + +// For example, [source: 0-99] can be split into +// [split_src1: 10-29]; [split_src2: 40-49, 60-69]; [split_src3: 70-89] +// Here "10-29" simply means block 10th to block 29th with respect to the original input file. +// Also, note that the split sources should be mutual exclusive, but they don't need to cover +// every block in the original source. +class SortedRangeSet : public RangeSet { + public: + // The block size when working with offset and file length. + static constexpr size_t kBlockSize = 4096; + + SortedRangeSet() {} + + // Ranges in the the set should be mutually exclusive; and they're sorted by the start block. + explicit SortedRangeSet(std::vector<Range>&& pairs); + + void Insert(const Range& to_insert); + + // Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges. + void Insert(const SortedRangeSet& rs); + + // Compute the block range the file occupies, and insert that range. + void Insert(size_t start, size_t len); + + using RangeSet::Overlaps; + + bool Overlaps(size_t start, size_t len) const; + + // Given an offset of the file, checks if the corresponding block (by considering the file as + // 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset + // within this SortedRangeSet. + // + // For example, the 4106-th byte of a file is from block 1, assuming a block size of 4096-byte. + // The mapped offset within a SortedRangeSet("1-9 15-19") is 10. + // + // An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th + // item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10 + // + 10) in a range represented by this SortedRangeSet. + size_t GetOffsetInRangeSet(size_t old_offset) const; +}; diff --git a/otautil/rangeset.cpp b/otautil/rangeset.cpp new file mode 100644 index 000000000..96955b9d0 --- /dev/null +++ b/otautil/rangeset.cpp @@ -0,0 +1,267 @@ +/* + * Copyright (C) 2017 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "otautil/rangeset.h" + +#include <limits.h> +#include <stddef.h> + +#include <algorithm> +#include <string> +#include <utility> +#include <vector> + +#include <android-base/logging.h> +#include <android-base/parseint.h> +#include <android-base/stringprintf.h> +#include <android-base/strings.h> + +RangeSet::RangeSet(std::vector<Range>&& pairs) { + blocks_ = 0; + if (pairs.empty()) { + LOG(ERROR) << "Invalid number of tokens"; + return; + } + + for (const auto& range : pairs) { + if (!PushBack(range)) { + Clear(); + return; + } + } +} + +RangeSet RangeSet::Parse(const std::string& range_text) { + std::vector<std::string> pieces = android::base::Split(range_text, ","); + if (pieces.size() < 3) { + LOG(ERROR) << "Invalid range text: " << range_text; + return {}; + } + + size_t num; + if (!android::base::ParseUint(pieces[0], &num, static_cast<size_t>(INT_MAX))) { + LOG(ERROR) << "Failed to parse the number of tokens: " << range_text; + return {}; + } + if (num == 0) { + LOG(ERROR) << "Invalid number of tokens: " << range_text; + return {}; + } + if (num % 2 != 0) { + LOG(ERROR) << "Number of tokens must be even: " << range_text; + return {}; + } + if (num != pieces.size() - 1) { + LOG(ERROR) << "Mismatching number of tokens: " << range_text; + return {}; + } + + std::vector<Range> pairs; + for (size_t i = 0; i < num; i += 2) { + size_t first; + size_t second; + if (!android::base::ParseUint(pieces[i + 1], &first, static_cast<size_t>(INT_MAX)) || + !android::base::ParseUint(pieces[i + 2], &second, static_cast<size_t>(INT_MAX))) { + return {}; + } + pairs.emplace_back(first, second); + } + return RangeSet(std::move(pairs)); +} + +bool RangeSet::PushBack(Range range) { + if (range.first >= range.second) { + LOG(ERROR) << "Empty or negative range: " << range.first << ", " << range.second; + return false; + } + size_t sz = range.second - range.first; + if (blocks_ >= SIZE_MAX - sz) { + LOG(ERROR) << "RangeSet size overflow"; + return false; + } + + ranges_.push_back(std::move(range)); + blocks_ += sz; + return true; +} + +void RangeSet::Clear() { + ranges_.clear(); + blocks_ = 0; +} + +std::vector<RangeSet> RangeSet::Split(size_t groups) const { + if (ranges_.empty() || groups == 0) return {}; + + if (blocks_ < groups) { + groups = blocks_; + } + + // Evenly distribute blocks, with the first few groups possibly containing one more. + size_t mean = blocks_ / groups; + std::vector<size_t> blocks_per_group(groups, mean); + std::fill_n(blocks_per_group.begin(), blocks_ % groups, mean + 1); + + std::vector<RangeSet> result; + + // Forward iterate Ranges and fill up each group with the desired number of blocks. + auto it = ranges_.cbegin(); + Range range = *it; + for (const auto& blocks : blocks_per_group) { + RangeSet buffer; + size_t needed = blocks; + while (needed > 0) { + size_t range_blocks = range.second - range.first; + if (range_blocks > needed) { + // Split the current range and don't advance the iterator. + buffer.PushBack({ range.first, range.first + needed }); + range.first = range.first + needed; + break; + } + buffer.PushBack(range); + it++; + if (it != ranges_.cend()) { + range = *it; + } + needed -= range_blocks; + } + result.push_back(std::move(buffer)); + } + return result; +} + +std::string RangeSet::ToString() const { + if (ranges_.empty()) { + return ""; + } + std::string result = std::to_string(ranges_.size() * 2); + for (const auto& r : ranges_) { + result += android::base::StringPrintf(",%zu,%zu", r.first, r.second); + } + + return result; +} + +// Get the block number for the i-th (starting from 0) block in the RangeSet. +size_t RangeSet::GetBlockNumber(size_t idx) const { + CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")"; + + for (const auto& range : ranges_) { + if (idx < range.second - range.first) { + return range.first + idx; + } + idx -= (range.second - range.first); + } + + CHECK(false) << "Failed to find block number for index " << idx; + return 0; // Unreachable, but to make compiler happy. +} + +// RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" +// and "5,7" are not overlapped. +bool RangeSet::Overlaps(const RangeSet& other) const { + for (const auto& range : ranges_) { + size_t start = range.first; + size_t end = range.second; + for (const auto& other_range : other.ranges_) { + size_t other_start = other_range.first; + size_t other_end = other_range.second; + // [start, end) vs [other_start, other_end) + if (!(other_start >= end || start >= other_end)) { + return true; + } + } + } + return false; +} + +// Ranges in the the set should be mutually exclusive; and they're sorted by the start block. +SortedRangeSet::SortedRangeSet(std::vector<Range>&& pairs) : RangeSet(std::move(pairs)) { + std::sort(ranges_.begin(), ranges_.end()); +} + +void SortedRangeSet::Insert(const Range& to_insert) { + SortedRangeSet rs({ to_insert }); + Insert(rs); +} + +// Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges. +void SortedRangeSet::Insert(const SortedRangeSet& rs) { + if (rs.size() == 0) { + return; + } + // Merge and sort the two RangeSets. + std::vector<Range> temp = std::move(ranges_); + std::copy(rs.begin(), rs.end(), std::back_inserter(temp)); + std::sort(temp.begin(), temp.end()); + + Clear(); + // Trim overlaps and insert the result back to ranges_. + Range to_insert = temp.front(); + for (auto it = temp.cbegin() + 1; it != temp.cend(); it++) { + if (it->first <= to_insert.second) { + to_insert.second = std::max(to_insert.second, it->second); + } else { + ranges_.push_back(to_insert); + blocks_ += (to_insert.second - to_insert.first); + to_insert = *it; + } + } + ranges_.push_back(to_insert); + blocks_ += (to_insert.second - to_insert.first); +} + +// Compute the block range the file occupies, and insert that range. +void SortedRangeSet::Insert(size_t start, size_t len) { + Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 }; + Insert(to_insert); +} + +bool SortedRangeSet::Overlaps(size_t start, size_t len) const { + RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } }); + return Overlaps(rs); +} + +// Given an offset of the file, checks if the corresponding block (by considering the file as +// 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset +// within this SortedRangeSet. +// +// For example, the 4106-th byte of a file is from block 1, assuming a block size of 4096-byte. +// The mapped offset within a SortedRangeSet("1-9 15-19") is 10. +// +// An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th +// item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10 +// + 10) in a range represented by this SortedRangeSet. +size_t SortedRangeSet::GetOffsetInRangeSet(size_t old_offset) const { + size_t old_block_start = old_offset / kBlockSize; + size_t new_block_start = 0; + for (const auto& range : ranges_) { + // Find the index of old_block_start. + if (old_block_start >= range.second) { + new_block_start += (range.second - range.first); + } else if (old_block_start >= range.first) { + new_block_start += (old_block_start - range.first); + return (new_block_start * kBlockSize + old_offset % kBlockSize); + } else { + CHECK(false) << "block_start " << old_block_start + << " is missing between two ranges: " << this->ToString(); + return 0; + } + } + CHECK(false) << "block_start " << old_block_start + << " exceeds the limit of current RangeSet: " << this->ToString(); + return 0; +} |