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 #ifndef LIBLP_METADATA_BUILDER_H 18 #define LIBLP_METADATA_BUILDER_H 19 20 #include <stddef.h> 21 #include <stdint.h> 22 23 #include <map> 24 #include <memory> 25 #include <optional> 26 #include <set> 27 #include <string_view> 28 29 #include "liblp.h" 30 #include "partition_opener.h" 31 32 namespace android { 33 namespace fs_mgr { 34 35 class LinearExtent; 36 struct Interval; 37 38 // By default, partitions are aligned on a 1MiB boundary. 39 static constexpr uint32_t kDefaultPartitionAlignment = 1024 * 1024; 40 static constexpr uint32_t kDefaultBlockSize = 4096; 41 42 // Name of the default group in a metadata. 43 static constexpr std::string_view kDefaultGroup = "default"; 44 45 // Abstraction around dm-targets that can be encoded into logical partition tables. 46 class Extent { 47 public: Extent(uint64_t num_sectors)48 explicit Extent(uint64_t num_sectors) : num_sectors_(num_sectors) {} ~Extent()49 virtual ~Extent() {} 50 51 virtual bool AddTo(LpMetadata* out) const = 0; AsLinearExtent()52 virtual LinearExtent* AsLinearExtent() { return nullptr; } 53 num_sectors()54 uint64_t num_sectors() const { return num_sectors_; } set_num_sectors(uint64_t num_sectors)55 void set_num_sectors(uint64_t num_sectors) { num_sectors_ = num_sectors; } 56 57 protected: 58 uint64_t num_sectors_; 59 }; 60 61 // This corresponds to a dm-linear target. 62 class LinearExtent final : public Extent { 63 public: LinearExtent(uint64_t num_sectors,uint32_t device_index,uint64_t physical_sector)64 LinearExtent(uint64_t num_sectors, uint32_t device_index, uint64_t physical_sector) 65 : Extent(num_sectors), device_index_(device_index), physical_sector_(physical_sector) {} 66 67 bool AddTo(LpMetadata* metadata) const override; AsLinearExtent()68 LinearExtent* AsLinearExtent() override { return this; } 69 physical_sector()70 uint64_t physical_sector() const { return physical_sector_; } end_sector()71 uint64_t end_sector() const { return physical_sector_ + num_sectors_; } device_index()72 uint32_t device_index() const { return device_index_; } 73 74 bool OverlapsWith(const LinearExtent& other) const; 75 bool OverlapsWith(const Interval& interval) const; 76 77 Interval AsInterval() const; 78 79 private: 80 uint32_t device_index_; 81 uint64_t physical_sector_; 82 }; 83 84 // This corresponds to a dm-zero target. 85 class ZeroExtent final : public Extent { 86 public: ZeroExtent(uint64_t num_sectors)87 explicit ZeroExtent(uint64_t num_sectors) : Extent(num_sectors) {} 88 89 bool AddTo(LpMetadata* out) const override; 90 }; 91 92 class PartitionGroup final { 93 friend class MetadataBuilder; 94 95 public: PartitionGroup(std::string_view name,uint64_t maximum_size)96 explicit PartitionGroup(std::string_view name, uint64_t maximum_size) 97 : name_(name), maximum_size_(maximum_size) {} 98 name()99 const std::string& name() const { return name_; } maximum_size()100 uint64_t maximum_size() const { return maximum_size_; } 101 102 private: set_maximum_size(uint64_t maximum_size)103 void set_maximum_size(uint64_t maximum_size) { maximum_size_ = maximum_size; } 104 105 std::string name_; 106 uint64_t maximum_size_; 107 }; 108 109 class Partition final { 110 friend class MetadataBuilder; 111 112 public: 113 Partition(std::string_view name, std::string_view group_name, uint32_t attributes); 114 115 // Add a raw extent. 116 void AddExtent(std::unique_ptr<Extent>&& extent); 117 118 // Remove all extents from this partition. 119 void RemoveExtents(); 120 121 // Compute the size used by linear extents. This is the same as size(), 122 // but does not factor in extents which do not take up space. 123 uint64_t BytesOnDisk() const; 124 name()125 const std::string& name() const { return name_; } group_name()126 const std::string& group_name() const { return group_name_; } attributes()127 uint32_t attributes() const { return attributes_; } set_attributes(uint32_t attributes)128 void set_attributes(uint32_t attributes) { attributes_ = attributes; } extents()129 const std::vector<std::unique_ptr<Extent>>& extents() const { return extents_; } size()130 uint64_t size() const { return size_; } 131 132 // Return a copy of *this, but with extents that includes only the first 133 // |aligned_size| bytes. |aligned_size| should be aligned to 134 // logical_block_size() of the MetadataBuilder that this partition belongs 135 // to. 136 Partition GetBeginningExtents(uint64_t aligned_size) const; 137 138 private: 139 void ShrinkTo(uint64_t aligned_size); set_group_name(std::string_view group_name)140 void set_group_name(std::string_view group_name) { group_name_ = group_name; } 141 142 std::string name_; 143 std::string group_name_; 144 std::vector<std::unique_ptr<Extent>> extents_; 145 uint32_t attributes_; 146 uint64_t size_; 147 bool disabled_; 148 }; 149 150 // An interval in the metadata. This is similar to a LinearExtent with one difference. 151 // LinearExtent represents a "used" region in the metadata, while Interval can also represent 152 // an "unused" region. 153 struct Interval { 154 uint32_t device_index; 155 uint64_t start; 156 uint64_t end; 157 IntervalInterval158 Interval(uint32_t device_index, uint64_t start, uint64_t end) 159 : device_index(device_index), start(start), end(end) {} lengthInterval160 uint64_t length() const { return end - start; } 161 162 // Note: the device index is not included in sorting (intervals are 163 // sorted in per-device lists). 164 bool operator<(const Interval& other) const { 165 return (start == other.start) ? end < other.end : start < other.start; 166 } 167 168 std::unique_ptr<Extent> AsExtent() const; 169 170 // Intersect |a| with |b|. 171 // If no intersection, result has 0 length(). 172 static Interval Intersect(const Interval& a, const Interval& b); 173 174 // Intersect two lists of intervals, and store result to |a|. 175 static std::vector<Interval> Intersect(const std::vector<Interval>& a, 176 const std::vector<Interval>& b); 177 }; 178 179 class MetadataBuilder { 180 public: 181 // Construct an empty logical partition table builder given the specified 182 // map of partitions that are available for storing logical partitions. 183 // 184 // At least one partition in the list must be the "super" device, where 185 // metadata will be stored. 186 // 187 // If the parameters would yield invalid metadata, nullptr is returned. This 188 // could happen if the super device is too small to store all required 189 // metadata. 190 static std::unique_ptr<MetadataBuilder> New(const std::vector<BlockDeviceInfo>& block_devices, 191 const std::string& super_partition, 192 uint32_t metadata_max_size, 193 uint32_t metadata_slot_count); 194 195 // Import an existing table for modification. This reads metadata off the 196 // given block device and imports it. It also adjusts alignment information 197 // based on run-time values in the operating system. 198 static std::unique_ptr<MetadataBuilder> New(const IPartitionOpener& opener, 199 const std::string& super_partition, 200 uint32_t slot_number); 201 202 // Same as above, but use the default PartitionOpener. 203 static std::unique_ptr<MetadataBuilder> New(const std::string& super_partition, 204 uint32_t slot_number); 205 206 // This is when performing an A/B update. The source partition must be a 207 // super partition. On a normal device, the metadata for the source slot 208 // is imported and the target slot is ignored. On a retrofit device, the 209 // metadata may not have the target slot's devices listed yet, in which 210 // case, it is automatically upgraded to include all available block 211 // devices. 212 // If |always_keep_source_slot| is set, on a Virtual A/B device 213 // - source slot partitions are kept. 214 // - UPDATED flag is cleared. 215 // This is useful when applying a downgrade package. 216 static std::unique_ptr<MetadataBuilder> NewForUpdate(const IPartitionOpener& opener, 217 const std::string& source_partition, 218 uint32_t source_slot_number, 219 uint32_t target_slot_number, 220 bool always_keep_source_slot = false); 221 222 // Import an existing table for modification. If the table is not valid, for 223 // example it contains duplicate partition names, then nullptr is returned. 224 // 225 // If an IPartitionOpener is specified, then block device informatiom will 226 // be updated. 227 static std::unique_ptr<MetadataBuilder> New(const LpMetadata& metadata, 228 const IPartitionOpener* opener = nullptr); 229 230 // Helper function for a single super partition, for tests. New(const BlockDeviceInfo & device_info,uint32_t metadata_max_size,uint32_t metadata_slot_count)231 static std::unique_ptr<MetadataBuilder> New(const BlockDeviceInfo& device_info, 232 uint32_t metadata_max_size, 233 uint32_t metadata_slot_count) { 234 return New({device_info}, device_info.partition_name, metadata_max_size, 235 metadata_slot_count); 236 } 237 238 // Wrapper around New() with a BlockDeviceInfo that only specifies a device 239 // size. This is a convenience method for tests. New(uint64_t blockdev_size,uint32_t metadata_max_size,uint32_t metadata_slot_count)240 static std::unique_ptr<MetadataBuilder> New(uint64_t blockdev_size, uint32_t metadata_max_size, 241 uint32_t metadata_slot_count) { 242 BlockDeviceInfo device_info(LP_METADATA_DEFAULT_PARTITION_NAME, blockdev_size, 0, 0, 243 kDefaultBlockSize); 244 return New(device_info, metadata_max_size, metadata_slot_count); 245 } 246 247 // Define a new partition group. By default there is one group called 248 // "default", with an unrestricted size. A non-zero size will restrict the 249 // total space used by all partitions in the group. 250 // 251 // This can fail and return false if the group already exists. 252 bool AddGroup(std::string_view group_name, uint64_t maximum_size); 253 254 // Export metadata so it can be serialized to an image, to disk, or mounted 255 // via device-mapper. 256 std::unique_ptr<LpMetadata> Export(); 257 258 // Add a partition, returning a handle so it can be sized as needed. If a 259 // partition with the given name already exists, nullptr is returned. 260 Partition* AddPartition(std::string_view name, std::string_view group_name, 261 uint32_t attributes); 262 263 // Same as AddPartition above, but uses the default partition group which 264 // has no size restrictions. 265 Partition* AddPartition(const std::string& name, uint32_t attributes); 266 267 // Delete a partition by name if it exists. 268 void RemovePartition(std::string_view name); 269 270 // Find a partition by name. If no partition is found, nullptr is returned. 271 Partition* FindPartition(std::string_view name); 272 273 // Find a group by name. If no group is found, nullptr is returned. 274 PartitionGroup* FindGroup(std::string_view name); 275 276 // Add a predetermined extent to a partition. 277 bool AddLinearExtent(Partition* partition, const std::string& block_device, 278 uint64_t num_sectors, uint64_t physical_sector); 279 280 // Grow or shrink a partition to the requested size. This size will be 281 // rounded UP to the nearest block (512 bytes). 282 // 283 // When growing a partition, a greedy algorithm is used to find free gaps 284 // in the partition table and allocate them. If not enough space can be 285 // allocated, false is returned, and the parition table will not be 286 // modified. 287 // 288 // Note, this is an in-memory operation, and it does not alter the 289 // underlying filesystem or contents of the partition on disk. 290 // 291 // If |free_region_hint| is not empty, it will only try to allocate extents 292 // in regions within the list. 293 bool ResizePartition(Partition* partition, uint64_t requested_size, 294 const std::vector<Interval>& free_region_hint = {}); 295 296 // Return the list of partitions belonging to a group. 297 std::vector<Partition*> ListPartitionsInGroup(std::string_view group_name); 298 299 // Changes a partition's group. Size constraints will not be checked until 300 // the metadata is exported, to avoid errors during potential group and 301 // size shuffling operations. This will return false if the new group does 302 // not exist. 303 bool ChangePartitionGroup(Partition* partition, std::string_view group_name); 304 305 // Changes the size of a partition group. Size constraints will not be 306 // checked until metadata is exported, to avoid errors during group 307 // reshuffling. This will return false if the group does not exist, or if 308 // the group name is "default". 309 bool ChangeGroupSize(const std::string& group_name, uint64_t maximum_size); 310 311 // Amount of space that can be allocated to logical partitions. 312 uint64_t AllocatableSpace() const; 313 uint64_t UsedSpace() const; 314 315 // Return a list of all group names. 316 std::vector<std::string> ListGroups() const; 317 318 // Remove all partitions belonging to a group, then remove the group. 319 void RemoveGroupAndPartitions(std::string_view group_name); 320 321 // Set the LP_METADATA_AUTO_SLOT_SUFFIXING flag. 322 void SetAutoSlotSuffixing(); 323 // Set the LP_HEADER_FLAG_VIRTUAL_AB_DEVICE flag. 324 void SetVirtualABDeviceFlag(); 325 326 // If set, checks for slot suffixes will be ignored internally. 327 void IgnoreSlotSuffixing(); 328 329 bool GetBlockDeviceInfo(const std::string& partition_name, BlockDeviceInfo* info) const; 330 bool UpdateBlockDeviceInfo(const std::string& partition_name, const BlockDeviceInfo& info); 331 332 // Require the expanded metadata header. This is exposed for testing, and 333 // is normally only called as needed by other methods. 334 void RequireExpandedMetadataHeader(); 335 336 // Attempt to preserve the named partitions from an older metadata. If this 337 // is not possible (for example, the block device list has changed) then 338 // false is returned. 339 bool ImportPartitions(const LpMetadata& metadata, const std::set<std::string>& partition_names); 340 341 // Return true if a block device is found, else false. 342 bool HasBlockDevice(const std::string& partition_name) const; 343 344 // Return the name of the block device at |index|. 345 std::string GetBlockDevicePartitionName(uint64_t index) const; 346 347 // Return the list of free regions not occupied by extents in the metadata. 348 std::vector<Interval> GetFreeRegions() const; 349 350 uint64_t logical_block_size() const; 351 352 private: 353 MetadataBuilder(); 354 MetadataBuilder(const MetadataBuilder&) = delete; 355 MetadataBuilder(MetadataBuilder&&) = delete; 356 MetadataBuilder& operator=(const MetadataBuilder&) = delete; 357 MetadataBuilder& operator=(MetadataBuilder&&) = delete; 358 bool Init(const std::vector<BlockDeviceInfo>& block_devices, const std::string& super_partition, 359 uint32_t metadata_max_size, uint32_t metadata_slot_count); 360 bool Init(const LpMetadata& metadata); 361 bool GrowPartition(Partition* partition, uint64_t aligned_size, 362 const std::vector<Interval>& free_region_hint); 363 void ShrinkPartition(Partition* partition, uint64_t aligned_size); 364 uint64_t AlignSector(const LpMetadataBlockDevice& device, uint64_t sector) const; 365 uint64_t TotalSizeOfGroup(PartitionGroup* group) const; 366 bool UpdateBlockDeviceInfo(size_t index, const BlockDeviceInfo& info); 367 bool FindBlockDeviceByName(const std::string& partition_name, uint32_t* index) const; 368 bool ValidatePartitionSizeChange(Partition* partition, uint64_t old_size, uint64_t new_size, 369 bool force_check); 370 void ImportExtents(Partition* dest, const LpMetadata& metadata, 371 const LpMetadataPartition& source); 372 bool ImportPartition(const LpMetadata& metadata, const LpMetadataPartition& source); 373 374 // Return true if the device is an AB device. 375 static bool IsABDevice(); 376 377 // Return true if the device is retrofitting dynamic partitions. 378 static bool IsRetrofitDynamicPartitionsDevice(); 379 380 // Return true if _b partitions should be prioritized at the second half of the device. 381 bool ShouldHalveSuper() const; 382 383 bool ValidatePartitionGroups() const; 384 385 bool IsAnyRegionCovered(const std::vector<Interval>& regions, 386 const LinearExtent& candidate) const; 387 bool IsAnyRegionAllocated(const LinearExtent& candidate) const; 388 void ExtentsToFreeList(const std::vector<Interval>& extents, 389 std::vector<Interval>* free_regions) const; 390 std::vector<Interval> PrioritizeSecondHalfOfSuper(const std::vector<Interval>& free_list); 391 std::unique_ptr<LinearExtent> ExtendFinalExtent(Partition* partition, 392 const std::vector<Interval>& free_list, 393 uint64_t sectors_needed) const; 394 395 static bool UpdateMetadataForOtherSuper(LpMetadata* metadata, uint32_t source_slot_number, 396 uint32_t target_slot_number); 397 398 LpMetadataGeometry geometry_; 399 LpMetadataHeader header_; 400 std::vector<std::unique_ptr<Partition>> partitions_; 401 std::vector<std::unique_ptr<PartitionGroup>> groups_; 402 std::vector<LpMetadataBlockDevice> block_devices_; 403 bool auto_slot_suffixing_; 404 }; 405 406 // Read BlockDeviceInfo for a given block device. This always returns false 407 // for non-Linux operating systems. 408 bool GetBlockDeviceInfo(const std::string& block_device, BlockDeviceInfo* device_info); 409 410 } // namespace fs_mgr 411 } // namespace android 412 413 #endif /* LIBLP_METADATA_BUILDER_H */ 414