liblp: Reclaim wasted space from unaligned partitions, v2.

When allocating a partition with a size that is unaligned (to the
optimal alignment), the remaining sectors are wasted since they are
never reallocated. This is because the free list is guaranteed to only
contain optimally-aligned regions. Unfortunately this means when a
partition is resized, we are wasting a small amount of space each time.
On a non-A/B device, this could wind up being significant.

For example, with an alignment of 512KiB, a 4KiB partition at offset 0
will waste 508KiB of space. The next extent to be allocated by any
partition will start at the next 512KiB.

To address this, we check if the last extent for a partition can be
extended to cover the difference between its last sector and the next
optimally aligned sector. We also verify that this region was not
allocated to any other partition, and does not appear in the free list,
to make sure we're not stealing space that will be used somewhere else.

Bug: 120434950
Test: liblp_test gtest
Change-Id: I88689889d44a4d2c51e659241918aaf2c064e049

3 files changed, 120 insertions, 17 deletions

diff --git a/fs_mgr/liblp/builder.cpp b/fs_mgr/liblp/builder.cpp
index 5e1bb2364..27222af8e 100644
--- a/fs_mgr/liblp/builder.cpp
+++ b/fs_mgr/liblp/builder.cpp
@@ -591,11 +591,25 @@ bool MetadataBuilder::GrowPartition(Partition* partition, uint64_t aligned_size)
         free_regions = PrioritizeSecondHalfOfSuper(free_regions);
     }
 
-    // Find gaps that we can use for new extents. Note we store new extents in a
-    // temporary vector, and only commit them if we are guaranteed enough free
-    // space.
+    // Note we store new extents in a temporary vector, and only commit them
+    // if we are guaranteed enough free space.
     std::vector<std::unique_ptr<LinearExtent>> new_extents;
+
+    // If the last extent in the partition has a size < alignment, then the
+    // difference is unallocatable due to being misaligned. We peek for that
+    // case here to avoid wasting space.
+    if (auto extent = ExtendFinalExtent(partition, free_regions, sectors_needed)) {
+        sectors_needed -= extent->num_sectors();
+        new_extents.emplace_back(std::move(extent));
+    }
+
     for (auto& region : free_regions) {
+        // Note: this comes first, since we may enter the loop not needing any
+        // more sectors.
+        if (!sectors_needed) {
+            break;
+        }
+
         if (region.length() % sectors_per_block != 0) {
             // This should never happen, because it would imply that we
             // once allocated an extent that was not a multiple of the
@@ -618,9 +632,6 @@ bool MetadataBuilder::GrowPartition(Partition* partition, uint64_t aligned_size)
         auto extent = std::make_unique<LinearExtent>(sectors, region.device_index, region.start);
         new_extents.push_back(std::move(extent));
         sectors_needed -= sectors;
-        if (!sectors_needed) {
-            break;
-        }
     }
     if (sectors_needed) {
         LERROR << "Not enough free space to expand partition: " << partition->name();
@@ -668,6 +679,64 @@ std::vector<MetadataBuilder::Interval> MetadataBuilder::PrioritizeSecondHalfOfSu
     return second_half;
 }
 
+std::unique_ptr<LinearExtent> MetadataBuilder::ExtendFinalExtent(
+        Partition* partition, const std::vector<Interval>& free_list,
+        uint64_t sectors_needed) const {
+    if (partition->extents().empty()) {
+        return nullptr;
+    }
+    LinearExtent* extent = partition->extents().back()->AsLinearExtent();
+    if (!extent) {
+        return nullptr;
+    }
+
+    // If the sector ends where the next aligned chunk begins, then there's
+    // no missing gap to try and allocate.
+    const auto& block_device = block_devices_[extent->device_index()];
+    uint64_t next_aligned_sector = AlignSector(block_device, extent->end_sector());
+    if (extent->end_sector() == next_aligned_sector) {
+        return nullptr;
+    }
+
+    uint64_t num_sectors = std::min(next_aligned_sector - extent->end_sector(), sectors_needed);
+    auto new_extent = std::make_unique<LinearExtent>(num_sectors, extent->device_index(),
+                                                     extent->end_sector());
+    if (IsAnyRegionAllocated(*new_extent.get()) ||
+        IsAnyRegionCovered(free_list, *new_extent.get())) {
+        LERROR << "Misaligned region " << new_extent->physical_sector() << ".."
+               << new_extent->end_sector() << " was allocated or marked allocatable.";
+        return nullptr;
+    }
+    return new_extent;
+}
+
+bool MetadataBuilder::IsAnyRegionCovered(const std::vector<Interval>& regions,
+                                         const LinearExtent& candidate) const {
+    for (const auto& region : regions) {
+        if (region.device_index == candidate.device_index() &&
+            (candidate.OwnsSector(region.start) || candidate.OwnsSector(region.end))) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool MetadataBuilder::IsAnyRegionAllocated(const LinearExtent& candidate) const {
+    for (const auto& partition : partitions_) {
+        for (const auto& extent : partition->extents()) {
+            LinearExtent* linear = extent->AsLinearExtent();
+            if (!linear || linear->device_index() != candidate.device_index()) {
+                continue;
+            }
+            if (linear->OwnsSector(candidate.physical_sector()) ||
+                linear->OwnsSector(candidate.end_sector() - 1)) {
+                return true;
+            }
+        }
+    }
+    return false;
+}
+
 void MetadataBuilder::ShrinkPartition(Partition* partition, uint64_t aligned_size) {
     partition->ShrinkTo(aligned_size);
 }
diff --git a/fs_mgr/liblp/builder_test.cpp b/fs_mgr/liblp/builder_test.cpp
index 88c303527..46bfe9238 100644
--- a/fs_mgr/liblp/builder_test.cpp
+++ b/fs_mgr/liblp/builder_test.cpp
@@ -218,7 +218,7 @@ TEST_F(BuilderTest, InternalPartitionAlignment) {
     // Check that each starting sector is aligned.
     for (const auto& extent : exported->extents) {
         ASSERT_EQ(extent.target_type, LP_TARGET_TYPE_LINEAR);
-        EXPECT_EQ(extent.num_sectors, 8);
+        EXPECT_EQ(extent.num_sectors, 80);
 
         uint64_t lba = extent.target_data * LP_SECTOR_SIZE;
         uint64_t aligned_lba = AlignTo(lba, device_info.alignment, device_info.alignment_offset);
@@ -226,7 +226,7 @@ TEST_F(BuilderTest, InternalPartitionAlignment) {
     }
 
     // Sanity check one extent.
-    EXPECT_EQ(exported->extents.back().target_data, 30656);
+    EXPECT_EQ(exported->extents.back().target_data, 3008);
 }
 
 TEST_F(BuilderTest, UseAllDiskSpace) {
@@ -797,19 +797,43 @@ TEST_F(BuilderTest, ABExtents) {
     EXPECT_EQ(system_a->extents().size(), static_cast<size_t>(1));
     EXPECT_EQ(system_b->extents().size(), static_cast<size_t>(1));
     ASSERT_TRUE(builder->ResizePartition(system_b, 6_GiB));
-    EXPECT_EQ(system_b->extents().size(), static_cast<size_t>(3));
+    EXPECT_EQ(system_b->extents().size(), static_cast<size_t>(2));
 
     unique_ptr<LpMetadata> exported = builder->Export();
     ASSERT_NE(exported, nullptr);
-    ASSERT_EQ(exported->extents.size(), static_cast<size_t>(4));
+    ASSERT_EQ(exported->extents.size(), static_cast<size_t>(3));
     EXPECT_EQ(exported->extents[0].target_data, 10487808);
-    EXPECT_EQ(exported->extents[0].num_sectors, 4194304);
-    EXPECT_EQ(exported->extents[1].target_data, 14682624);
-    EXPECT_EQ(exported->extents[1].num_sectors, 6288896);
-    EXPECT_EQ(exported->extents[2].target_data, 6292992);
-    EXPECT_EQ(exported->extents[2].num_sectors, 2099712);
-    EXPECT_EQ(exported->extents[3].target_data, 1536);
-    EXPECT_EQ(exported->extents[3].num_sectors, 6291456);
+    EXPECT_EQ(exported->extents[0].num_sectors, 10483712);
+    EXPECT_EQ(exported->extents[1].target_data, 6292992);
+    EXPECT_EQ(exported->extents[1].num_sectors, 2099200);
+    EXPECT_EQ(exported->extents[2].target_data, 1536);
+    EXPECT_EQ(exported->extents[2].num_sectors, 6291456);
+}
+
+TEST_F(BuilderTest, PartialExtents) {
+    // super has a minimum extent size of 768KiB.
+    BlockDeviceInfo device_info("super", 1_GiB, 768 * 1024, 0, 4096);
+    auto builder = MetadataBuilder::New(device_info, 65536, 1);
+    ASSERT_NE(builder, nullptr);
+    Partition* system = builder->AddPartition("system", 0);
+    ASSERT_NE(system, nullptr);
+    Partition* vendor = builder->AddPartition("vendor", 0);
+    ASSERT_NE(vendor, nullptr);
+    ASSERT_TRUE(builder->ResizePartition(system, device_info.alignment + 4096));
+    ASSERT_TRUE(builder->ResizePartition(vendor, device_info.alignment));
+    ASSERT_EQ(system->size(), device_info.alignment + 4096);
+    ASSERT_EQ(vendor->size(), device_info.alignment);
+
+    ASSERT_TRUE(builder->ResizePartition(system, device_info.alignment * 2));
+    ASSERT_EQ(system->extents().size(), static_cast<size_t>(1));
+
+    unique_ptr<LpMetadata> exported = builder->Export();
+    ASSERT_NE(exported, nullptr);
+    ASSERT_EQ(exported->extents.size(), static_cast<size_t>(2));
+    EXPECT_EQ(exported->extents[0].target_data, 1536);
+    EXPECT_EQ(exported->extents[0].num_sectors, 3072);
+    EXPECT_EQ(exported->extents[1].target_data, 4608);
+    EXPECT_EQ(exported->extents[1].num_sectors, 1536);
 }
 
 TEST_F(BuilderTest, UpdateSuper) {
diff --git a/fs_mgr/liblp/include/liblp/builder.h b/fs_mgr/liblp/include/liblp/builder.h
index 486a71f75..c706f2a73 100644
--- a/fs_mgr/liblp/include/liblp/builder.h
+++ b/fs_mgr/liblp/include/liblp/builder.h
@@ -66,6 +66,10 @@ class LinearExtent final : public Extent {
     uint64_t end_sector() const { return physical_sector_ + num_sectors_; }
     uint32_t device_index() const { return device_index_; }
 
+    bool OwnsSector(uint64_t sector) const {
+        return sector >= physical_sector_ && sector < end_sector();
+    }
+
   private:
     uint32_t device_index_;
     uint64_t physical_sector_;
@@ -322,9 +326,15 @@ class MetadataBuilder {
         }
     };
     std::vector<Interval> GetFreeRegions() const;
+    bool IsAnyRegionCovered(const std::vector<Interval>& regions,
+                            const LinearExtent& candidate) const;
+    bool IsAnyRegionAllocated(const LinearExtent& candidate) const;
     void ExtentsToFreeList(const std::vector<Interval>& extents,
                            std::vector<Interval>* free_regions) const;
     std::vector<Interval> PrioritizeSecondHalfOfSuper(const std::vector<Interval>& free_list);
+    std::unique_ptr<LinearExtent> ExtendFinalExtent(Partition* partition,
+                                                    const std::vector<Interval>& free_list,
+                                                    uint64_t sectors_needed) const;
 
     static bool sABOverrideValue;
     static bool sABOverrideSet;