summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Anderson2018-07-31 18:43:26 -0500
committerDavid Anderson2018-08-02 11:14:47 -0500
commitde1daa72aaa25de8b61f004457a60b8f4527dec6 (patch)
tree7e2859ae3b6d522f4850dcdfb26263f0ba9ddb65
parentddcee93c0138fc68dbc6320962a53cd4761ab94b (diff)
downloadplatform-system-core-de1daa72aaa25de8b61f004457a60b8f4527dec6.tar.gz
platform-system-core-de1daa72aaa25de8b61f004457a60b8f4527dec6.tar.xz
platform-system-core-de1daa72aaa25de8b61f004457a60b8f4527dec6.zip
liblp: Simplify GrowPartition().
The partition resize algorithm duplicates a lot of logic because it handles the final free interval separately from other free intervals. This is unnecessary and makes it harder to change the actual algorithm. This change makes GrowPartition() treat the final free space region the same as free gaps in between partitions. It does this by converting the extent list into a gap list, and then adds a final gap for the remainder of the free space. The resize function no longer has to treat the end of the disk separately. This patch does not change the way partitions are allocated, it is purely a refactoring. Bug: 79173901 Test: liblp_test gtest Change-Id: I4780f20b23fe021eac62de874b061857712c04fe
-rw-r--r--fs_mgr/liblp/builder.cpp86
1 files changed, 38 insertions, 48 deletions
diff --git a/fs_mgr/liblp/builder.cpp b/fs_mgr/liblp/builder.cpp
index d6eee6b32..d3c785d33 100644
--- a/fs_mgr/liblp/builder.cpp
+++ b/fs_mgr/liblp/builder.cpp
@@ -299,49 +299,59 @@ bool MetadataBuilder::GrowPartition(Partition* partition, uint64_t aligned_size)
299 Interval(uint64_t start, uint64_t end) : start(start), end(end) {} 299 Interval(uint64_t start, uint64_t end) : start(start), end(end) {}
300 bool operator<(const Interval& other) const { return start < other.start; } 300 bool operator<(const Interval& other) const { return start < other.start; }
301 }; 301 };
302 std::vector<Interval> intervals;
303 302
304 // Collect all extents in the partition table. 303 // Collect all extents in the partition table, then sort them by starting
304 // sector.
305 std::vector<Interval> extents;
305 for (const auto& partition : partitions_) { 306 for (const auto& partition : partitions_) {
306 for (const auto& extent : partition->extents()) { 307 for (const auto& extent : partition->extents()) {
307 LinearExtent* linear = extent->AsLinearExtent(); 308 LinearExtent* linear = extent->AsLinearExtent();
308 if (!linear) { 309 if (!linear) {
309 continue; 310 continue;
310 } 311 }
311 intervals.emplace_back(linear->physical_sector(), 312 extents.emplace_back(linear->physical_sector(),
312 linear->physical_sector() + extent->num_sectors()); 313 linear->physical_sector() + extent->num_sectors());
313 } 314 }
314 } 315 }
316 std::sort(extents.begin(), extents.end());
315 317
316 // Sort extents by starting sector. 318 // Convert the extent list into a list of gaps between the extents; i.e.,
317 std::sort(intervals.begin(), intervals.end()); 319 // the list of ranges that are free on the disk.
318 320 std::vector<Interval> free_regions;
319 // Find gaps that we can use for new extents. Note we store new extents in a 321 for (size_t i = 1; i < extents.size(); i++) {
320 // temporary vector, and only commit them if we are guaranteed enough free 322 const Interval& previous = extents[i - 1];
321 // space. 323 const Interval& current = extents[i];
322 std::vector<std::unique_ptr<LinearExtent>> new_extents;
323 for (size_t i = 1; i < intervals.size(); i++) {
324 const Interval& previous = intervals[i - 1];
325 const Interval& current = intervals[i];
326
327 if (previous.end >= current.start) {
328 // There is no gap between these two extents, try the next one. Note that
329 // extents may never overlap, but just for safety, we ignore them if they
330 // do.
331 DCHECK(previous.end == current.start);
332 continue;
333 }
334 324
335 uint64_t aligned = AlignSector(previous.end); 325 uint64_t aligned = AlignSector(previous.end);
336 if (aligned >= current.start) { 326 if (aligned >= current.start) {
337 // After alignment, this extent is not usable. 327 // There is no gap between these two extents, try the next one.
328 // Note that we check with >= instead of >, since alignment may
329 // bump the ending sector past the beginning of the next extent.
338 continue; 330 continue;
339 } 331 }
340 332
333 // The new interval represents the free space starting at the end of
334 // the previous interval, and ending at the start of the next interval.
335 free_regions.emplace_back(aligned, current.start);
336 }
337
338 // Add a final interval representing the remainder of the free space.
339 uint64_t last_free_extent_start =
340 extents.empty() ? geometry_.first_logical_sector : extents.back().end;
341 last_free_extent_start = AlignSector(last_free_extent_start);
342 if (last_free_extent_start <= geometry_.last_logical_sector) {
343 free_regions.emplace_back(last_free_extent_start, geometry_.last_logical_sector + 1);
344 }
345
346 // Find gaps that we can use for new extents. Note we store new extents in a
347 // temporary vector, and only commit them if we are guaranteed enough free
348 // space.
349 std::vector<std::unique_ptr<LinearExtent>> new_extents;
350 for (const auto& region : free_regions) {
341 // This gap is enough to hold the remainder of the space requested, so we 351 // This gap is enough to hold the remainder of the space requested, so we
342 // can allocate what we need and return. 352 // can allocate what we need and return.
343 if (current.start - aligned >= sectors_needed) { 353 if (region.end - region.start >= sectors_needed) {
344 auto extent = std::make_unique<LinearExtent>(sectors_needed, aligned); 354 auto extent = std::make_unique<LinearExtent>(sectors_needed, region.start);
345 sectors_needed -= extent->num_sectors(); 355 sectors_needed -= extent->num_sectors();
346 new_extents.push_back(std::move(extent)); 356 new_extents.push_back(std::move(extent));
347 break; 357 break;
@@ -349,33 +359,13 @@ bool MetadataBuilder::GrowPartition(Partition* partition, uint64_t aligned_size)
349 359
350 // This gap is not big enough to fit the remainder of the space requested, 360 // This gap is not big enough to fit the remainder of the space requested,
351 // so consume the whole thing and keep looking for more. 361 // so consume the whole thing and keep looking for more.
352 auto extent = std::make_unique<LinearExtent>(current.start - aligned, aligned); 362 auto extent = std::make_unique<LinearExtent>(region.end - region.start, region.start);
353 sectors_needed -= extent->num_sectors(); 363 sectors_needed -= extent->num_sectors();
354 new_extents.push_back(std::move(extent)); 364 new_extents.push_back(std::move(extent));
355 } 365 }
356
357 // If we still have more to allocate, take it from the remaining free space
358 // in the allocatable region.
359 if (sectors_needed) { 366 if (sectors_needed) {
360 uint64_t first_sector; 367 LERROR << "Not enough free space to expand partition: " << partition->name();
361 if (intervals.empty()) { 368 return false;
362 first_sector = geometry_.first_logical_sector;
363 } else {
364 first_sector = intervals.back().end;
365 }
366 DCHECK(first_sector <= geometry_.last_logical_sector);
367
368 // Note: After alignment, |first_sector| may be > the last usable sector.
369 first_sector = AlignSector(first_sector);
370
371 // Note: the last usable sector is inclusive.
372 if (first_sector > geometry_.last_logical_sector ||
373 geometry_.last_logical_sector + 1 - first_sector < sectors_needed) {
374 LERROR << "Not enough free space to expand partition: " << partition->name();
375 return false;
376 }
377 auto extent = std::make_unique<LinearExtent>(sectors_needed, first_sector);
378 new_extents.push_back(std::move(extent));
379 } 369 }
380 370
381 for (auto& extent : new_extents) { 371 for (auto& extent : new_extents) {