liblp: Indicate usable regions in ResizePartition
- Open up GetFreeRegions() API.
- Add a new argument, free_region_hint, to ResizePartitions(). It
indicates the regions that extents can be allocated to.
- Expose Interval::Intersect functions. libsnapshot needs the algorithm
to intersect extents to find out the free regions for COW partitions.
Test: liblp_test
Change-Id: I0c079c0e919aa7b0627eb76a071a7cc2a281d692
diff --git a/fs_mgr/liblp/builder.cpp b/fs_mgr/liblp/builder.cpp
index f8c492d..c5d6a3b 100644
--- a/fs_mgr/liblp/builder.cpp
+++ b/fs_mgr/liblp/builder.cpp
@@ -579,12 +579,38 @@
return true;
}
-bool MetadataBuilder::GrowPartition(Partition* partition, uint64_t aligned_size) {
+Interval Interval::Intersect(const Interval& a, const Interval& b) {
+ Interval ret = a;
+ if (a.device_index != b.device_index) {
+ ret.start = ret.end = a.start; // set length to 0 to indicate no intersection.
+ return ret;
+ }
+ ret.start = std::max(a.start, b.start);
+ ret.end = std::max(ret.start, std::min(a.end, b.end));
+ return ret;
+}
+
+std::vector<Interval> Interval::Intersect(const std::vector<Interval>& a,
+ const std::vector<Interval>& b) {
+ std::vector<Interval> ret;
+ for (const Interval& a_interval : a) {
+ for (const Interval& b_interval : b) {
+ auto intersect = Intersect(a_interval, b_interval);
+ if (intersect.length() > 0) ret.emplace_back(std::move(intersect));
+ }
+ }
+ return ret;
+}
+
+bool MetadataBuilder::GrowPartition(Partition* partition, uint64_t aligned_size,
+ const std::vector<Interval>& free_region_hint) {
uint64_t space_needed = aligned_size - partition->size();
uint64_t sectors_needed = space_needed / LP_SECTOR_SIZE;
DCHECK(sectors_needed * LP_SECTOR_SIZE == space_needed);
std::vector<Interval> free_regions = GetFreeRegions();
+ if (!free_region_hint.empty())
+ free_regions = Interval::Intersect(free_regions, free_region_hint);
const uint64_t sectors_per_block = geometry_.logical_block_size / LP_SECTOR_SIZE;
CHECK_NE(sectors_per_block, 0);
@@ -650,7 +676,7 @@
return true;
}
-std::vector<MetadataBuilder::Interval> MetadataBuilder::PrioritizeSecondHalfOfSuper(
+std::vector<Interval> MetadataBuilder::PrioritizeSecondHalfOfSuper(
const std::vector<Interval>& free_list) {
const auto& super = block_devices_[0];
uint64_t first_sector = super.first_logical_sector;
@@ -926,7 +952,8 @@
return true;
}
-bool MetadataBuilder::ResizePartition(Partition* partition, uint64_t requested_size) {
+bool MetadataBuilder::ResizePartition(Partition* partition, uint64_t requested_size,
+ const std::vector<Interval>& free_region_hint) {
// Align the space needed up to the nearest sector.
uint64_t aligned_size = AlignTo(requested_size, geometry_.logical_block_size);
uint64_t old_size = partition->size();
@@ -936,7 +963,7 @@
}
if (aligned_size > old_size) {
- if (!GrowPartition(partition, aligned_size)) {
+ if (!GrowPartition(partition, aligned_size, free_region_hint)) {
return false;
}
} else if (aligned_size < partition->size()) {
diff --git a/fs_mgr/liblp/builder_test.cpp b/fs_mgr/liblp/builder_test.cpp
index c5b4047..bd41f59 100644
--- a/fs_mgr/liblp/builder_test.cpp
+++ b/fs_mgr/liblp/builder_test.cpp
@@ -887,3 +887,38 @@
std::set<std::string> partitions_to_keep{"system_a", "vendor_a", "product_a"};
ASSERT_TRUE(builder->ImportPartitions(*on_disk.get(), partitions_to_keep));
}
+
+// Interval has operator< defined; it is not appropriate to re-define Interval::operator== that
+// compares device index.
+namespace android {
+namespace fs_mgr {
+bool operator==(const Interval& a, const Interval& b) {
+ return a.device_index == b.device_index && a.start == b.start && a.end == b.end;
+}
+} // namespace fs_mgr
+} // namespace android
+
+TEST_F(BuilderTest, Interval) {
+ EXPECT_EQ(0u, Interval::Intersect(Interval(0, 100, 200), Interval(0, 50, 100)).length());
+ EXPECT_EQ(Interval(0, 100, 150),
+ Interval::Intersect(Interval(0, 100, 200), Interval(0, 50, 150)));
+ EXPECT_EQ(Interval(0, 100, 200),
+ Interval::Intersect(Interval(0, 100, 200), Interval(0, 50, 200)));
+ EXPECT_EQ(Interval(0, 100, 200),
+ Interval::Intersect(Interval(0, 100, 200), Interval(0, 50, 250)));
+ EXPECT_EQ(Interval(0, 100, 200),
+ Interval::Intersect(Interval(0, 100, 200), Interval(0, 100, 200)));
+ EXPECT_EQ(Interval(0, 150, 200),
+ Interval::Intersect(Interval(0, 100, 200), Interval(0, 150, 250)));
+ EXPECT_EQ(0u, Interval::Intersect(Interval(0, 100, 200), Interval(0, 200, 250)).length());
+
+ auto v = Interval::Intersect(std::vector<Interval>{Interval(0, 0, 50), Interval(0, 100, 150)},
+ std::vector<Interval>{Interval(0, 25, 125)});
+ ASSERT_EQ(2, v.size());
+ EXPECT_EQ(Interval(0, 25, 50), v[0]);
+ EXPECT_EQ(Interval(0, 100, 125), v[1]);
+
+ EXPECT_EQ(0u, Interval::Intersect(std::vector<Interval>{Interval(0, 0, 50)},
+ std::vector<Interval>{Interval(0, 100, 150)})
+ .size());
+}
diff --git a/fs_mgr/liblp/include/liblp/builder.h b/fs_mgr/liblp/include/liblp/builder.h
index 5ab42f5..6f2ab75 100644
--- a/fs_mgr/liblp/include/liblp/builder.h
+++ b/fs_mgr/liblp/include/liblp/builder.h
@@ -138,6 +138,33 @@
uint64_t size_;
};
+// An interval in the metadata. This is similar to a LinearExtent with one difference.
+// LinearExtent represents a "used" region in the metadata, while Interval can also represent
+// an "unused" region.
+struct Interval {
+ uint32_t device_index;
+ uint64_t start;
+ uint64_t end;
+
+ Interval(uint32_t device_index, uint64_t start, uint64_t end)
+ : device_index(device_index), start(start), end(end) {}
+ uint64_t length() const { return end - start; }
+
+ // Note: the device index is not included in sorting (intervals are
+ // sorted in per-device lists).
+ bool operator<(const Interval& other) const {
+ return (start == other.start) ? end < other.end : start < other.start;
+ }
+
+ // Intersect |a| with |b|.
+ // If no intersection, result has 0 length().
+ static Interval Intersect(const Interval& a, const Interval& b);
+
+ // Intersect two lists of intervals, and store result to |a|.
+ static std::vector<Interval> Intersect(const std::vector<Interval>& a,
+ const std::vector<Interval>& b);
+};
+
class MetadataBuilder {
public:
// Construct an empty logical partition table builder given the specified
@@ -244,7 +271,11 @@
//
// Note, this is an in-memory operation, and it does not alter the
// underlying filesystem or contents of the partition on disk.
- bool ResizePartition(Partition* partition, uint64_t requested_size);
+ //
+ // If |free_region_hint| is not empty, it will only try to allocate extents
+ // in regions within the list.
+ bool ResizePartition(Partition* partition, uint64_t requested_size,
+ const std::vector<Interval>& free_region_hint = {});
// Return the list of partitions belonging to a group.
std::vector<Partition*> ListPartitionsInGroup(const std::string& group_name);
@@ -291,6 +322,9 @@
// Return the name of the block device at |index|.
std::string GetBlockDevicePartitionName(uint64_t index) const;
+ // Return the list of free regions not occupied by extents in the metadata.
+ std::vector<Interval> GetFreeRegions() const;
+
private:
MetadataBuilder();
MetadataBuilder(const MetadataBuilder&) = delete;
@@ -300,7 +334,8 @@
bool Init(const std::vector<BlockDeviceInfo>& block_devices, const std::string& super_partition,
uint32_t metadata_max_size, uint32_t metadata_slot_count);
bool Init(const LpMetadata& metadata);
- bool GrowPartition(Partition* partition, uint64_t aligned_size);
+ bool GrowPartition(Partition* partition, uint64_t aligned_size,
+ const std::vector<Interval>& free_region_hint);
void ShrinkPartition(Partition* partition, uint64_t aligned_size);
uint64_t AlignSector(const LpMetadataBlockDevice& device, uint64_t sector) const;
uint64_t TotalSizeOfGroup(PartitionGroup* group) const;
@@ -323,22 +358,6 @@
bool ValidatePartitionGroups() const;
- struct Interval {
- uint32_t device_index;
- uint64_t start;
- uint64_t end;
-
- Interval(uint32_t device_index, uint64_t start, uint64_t end)
- : device_index(device_index), start(start), end(end) {}
- uint64_t length() const { return end - start; }
-
- // Note: the device index is not included in sorting (intervals are
- // sorted in per-device lists).
- bool operator<(const Interval& other) const {
- return (start == other.start) ? end < other.end : start < other.start;
- }
- };
- std::vector<Interval> GetFreeRegions() const;
bool IsAnyRegionCovered(const std::vector<Interval>& regions,
const LinearExtent& candidate) const;
bool IsAnyRegionAllocated(const LinearExtent& candidate) const;