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;