Merge changes I88689889,Ibfd66734

* changes:
  liblp: Reclaim wasted space from unaligned partitions, v2.
  Revert "liblp: Reclaim wasted space from unaligned partitions."

3 files changed, 92 insertions, 22 deletions

diff --git a/fs_mgr/liblp/builder.cpp b/fs_mgr/liblp/builder.cpp
index ebd699717..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
@@ -613,22 +627,10 @@ bool MetadataBuilder::GrowPartition(Partition* partition, uint64_t aligned_size)
         }
 
         uint64_t sectors = std::min(sectors_needed, region.length());
-        if (sectors < region.length()) {
-            const auto& block_device = block_devices_[region.device_index];
-            if (block_device.alignment) {
-                const uint64_t alignment = block_device.alignment / LP_SECTOR_SIZE;
-                sectors = AlignTo(sectors, alignment);
-                sectors = std::min(sectors, region.length());
-            }
-        }
         CHECK(sectors % sectors_per_block == 0);
 
         auto extent = std::make_unique<LinearExtent>(sectors, region.device_index, region.start);
         new_extents.push_back(std::move(extent));
-        if (sectors >= sectors_needed) {
-            sectors_needed = 0;
-            break;
-        }
         sectors_needed -= sectors;
     }
     if (sectors_needed) {
@@ -677,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 81305b3a0..46bfe9238 100644
--- a/fs_mgr/liblp/builder_test.cpp
+++ b/fs_mgr/liblp/builder_test.cpp
@@ -209,8 +209,8 @@ TEST_F(BuilderTest, InternalPartitionAlignment) {
         ASSERT_TRUE(builder->ResizePartition(a, a->size() + 4096));
         ASSERT_TRUE(builder->ResizePartition(b, b->size() + 4096));
     }
-    EXPECT_EQ(a->size(), 7864320);
-    EXPECT_EQ(b->size(), 7864320);
+    EXPECT_EQ(a->size(), 40960);
+    EXPECT_EQ(b->size(), 40960);
 
     unique_ptr<LpMetadata> exported = builder->Export();
     ASSERT_NE(exported, nullptr);
@@ -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, 1536);
+        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) {
@@ -698,7 +698,7 @@ TEST_F(BuilderTest, MultipleBlockDevices) {
     EXPECT_EQ(metadata->extents[1].target_type, LP_TARGET_TYPE_LINEAR);
     EXPECT_EQ(metadata->extents[1].target_data, 1472);
     EXPECT_EQ(metadata->extents[1].target_source, 1);
-    EXPECT_EQ(metadata->extents[2].num_sectors, 129600);
+    EXPECT_EQ(metadata->extents[2].num_sectors, 129088);
     EXPECT_EQ(metadata->extents[2].target_type, LP_TARGET_TYPE_LINEAR);
     EXPECT_EQ(metadata->extents[2].target_data, 1472);
     EXPECT_EQ(metadata->extents[2].target_source, 2);
@@ -805,7 +805,7 @@ TEST_F(BuilderTest, ABExtents) {
     EXPECT_EQ(exported->extents[0].target_data, 10487808);
     EXPECT_EQ(exported->extents[0].num_sectors, 10483712);
     EXPECT_EQ(exported->extents[1].target_data, 6292992);
-    EXPECT_EQ(exported->extents[1].num_sectors, 2099712);
+    EXPECT_EQ(exported->extents[1].num_sectors, 2099200);
     EXPECT_EQ(exported->extents[2].target_data, 1536);
     EXPECT_EQ(exported->extents[2].num_sectors, 6291456);
 }
@@ -821,7 +821,7 @@ TEST_F(BuilderTest, PartialExtents) {
     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 * 2);
+    ASSERT_EQ(system->size(), device_info.alignment + 4096);
     ASSERT_EQ(vendor->size(), device_info.alignment);
 
     ASSERT_TRUE(builder->ResizePartition(system, device_info.alignment * 2));
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;