[PATCH guest-common v8 08/22] guest id: keep used ID list below the pmxcfs file size limit

["Michael Köppl" <m.koeppl@proxmox.com>]

The used-guest-ids file can grow to more than 1 MiB if many
non-adjacent ID ranges or individual guest IDs are stored. While
unlikely to happen with regular operation, exceeding this limit on a
file in pmxcfs will cause every operation to fail, regardless of
whether the feature is turned on or not. To avoid this, add 2
thresholds: the first at 512 KiB, at which users are warned that their
ranges might be aggressively merged in the future, and the second at
768 KiB, at which this aggressive merging happens.

Once the second threshold is exceeded, the smallest gaps between ranges
will be merged until the file size is below the threshold again. This
will cause previously unused IDs to be recorded as used, resulting in
fewer available IDs overall.

Signed-off-by: Michael Köppl <m.koeppl@proxmox.com>
Reviewed-by: Fiona Ebner <f.ebner@proxmox.com>
Tested-by: Fiona Ebner <f.ebner@proxmox.com>
---
 src/PVE/GuestID.pm | 112 ++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 101 insertions(+), 11 deletions(-)

diff --git a/src/PVE/GuestID.pm b/src/PVE/GuestID.pm
index 89219c8..0494913 100644
--- a/src/PVE/GuestID.pm
+++ b/src/PVE/GuestID.pm
@@ -11,6 +11,10 @@ use PVE::Cluster qw(
 
 my $FILENAME = 'virtual-guest/used-guest-ids';
 
+# keep well below the 1 MiB file size limit of pmxcfs, writes fail beyond it
+my $SIZE_WARN = 512 * 1024;
+my $SIZE_MAX = 768 * 1024;
+
 my sub parse_id_list($filename, $raw) {
     my $ranges = [];
 
@@ -43,24 +47,110 @@ my sub format_entry($start, $last) {
     return $start == $last ? "$start\n" : "$start-$last\n";
 }
 
-my sub write_id_list($filename, $ranges) {
-    my $output = '';
-    my ($start, $last);
+my sub merge_ranges($ranges) {
+    my $merged = [];
 
     for my $range ($ranges->@*) {
-        my ($curr_start, $curr_end) = $range->@*;
+        my ($start, $end) = $range->@*;
+        my $current_merge = $merged->[-1];
 
-        if (!defined($start)) {
-            ($start, $last) = ($curr_start, $curr_end);
-        } elsif ($curr_start <= $last + 1) {
-            $last = $curr_end if $curr_end > $last;
+        if ($current_merge && $start <= $current_merge->[1] + 1) {
+            $current_merge->[1] = $end if $end > $current_merge->[1];
         } else {
-            $output .= format_entry($start, $last);
-            ($start, $last) = ($curr_start, $curr_end);
+            push $merged->@*, [$start, $end];
         }
     }
 
-    $output .= format_entry($start, $last) if defined($start);
+    return $merged;
+}
+
+my sub format_ranges($ranges) {
+    return join('', map { format_entry($_->@*) } $ranges->@*);
+}
+
+# Closes the smallest gaps between ranges in $merged until the
+# formatted list of $output_size bytes fits into $SIZE_MAX. The unused
+# IDs in a closed gap count as used from then on. Returns the resulting
+# ranges and the number of unused IDs that got marked as used.
+my sub close_smallest_gaps($merged, $output_size) {
+    my @gap_sizes;
+    for my $i (1 .. $#$merged) {
+        my $prev_end = $merged->[$i - 1]->[1];
+        my $curr_start = $merged->[$i]->[0];
+
+        $gap_sizes[$i] = $curr_start - $prev_end - 1;
+    }
+
+    my @gap_order = sort { $gap_sizes[$a] <=> $gap_sizes[$b] || $a <=> $b } 1 .. $#$merged;
+
+    # Record start and end of each group. Initially, with e.g. 6 ranges,
+    # this would be:
+    #   start: (0, 1, 2, 3, 4, 5)
+    #   end:   (0, 1, 2, 3, 4, 5)
+    # After closing the gap between 1 and 2:
+    #   start: (0, 1, 1, 3, 4, 5)
+    #   end:   (0, 2, 2, 3, 4, 5)
+    # After closing the gap between 2 and 3 (note that range 2 is now fully
+    # merged into adjacent ranges, so its group indices won't be accessed
+    # anymore):
+    #   start: (0, 1, 1, 1, 4, 5)
+    #   end:   (0, 3, 2, 3, 4, 5)
+    # After closing the gap between 4 and 5:
+    #   start: (0, 1, 1, 1, 4, 4)
+    #   end:   (0, 3, 2, 3, 5, 5)
+    my @group_start = (0 .. $#$merged);
+    my @group_end = (0 .. $#$merged);
+
+    my $closed_id_count = 0;
+
+    for my $i (@gap_order) {
+        last if $output_size <= $SIZE_MAX;
+
+        my ($first_index, $last_index) = ($group_start[$i - 1], $group_end[$i]);
+        my ($new_range_start, $new_range_end) =
+            ($merged->[$first_index]->[0], $merged->[$last_index]->[1]);
+        # used IDs directly before and after gap $i
+        my ($before_gap, $after_gap) = ($merged->[$i - 1]->[1], $merged->[$i]->[0]);
+
+        # the lines of both groups are replaced by a single line
+        # spanning them
+        $output_size +=
+            length(format_entry($new_range_start, $new_range_end)) -
+            length(format_entry($new_range_start, $before_gap)) -
+            length(format_entry($after_gap, $new_range_end));
+
+        $group_end[$first_index] = $last_index;
+        $group_start[$last_index] = $first_index;
+        $closed_id_count += $gap_sizes[$i];
+    }
+
+    my $closed = [];
+    for (my $i = 0; $i <= $#$merged; $i = $group_end[$i] + 1) {
+        push $closed->@*, [$merged->[$i]->[0], $merged->[$group_end[$i]]->[1]];
+    }
+
+    return ($closed, $closed_id_count);
+}
+
+my sub write_id_list($filename, $ranges) {
+    my $merged = merge_ranges($ranges);
+    my $output = format_ranges($merged);
+
+    if (length($output) > $SIZE_MAX) {
+        my ($closed, $closed_ids) = close_smallest_gaps($merged, length($output));
+        $output = format_ranges($closed);
+        warn "$filename would exceed "
+            . ($SIZE_MAX / 1024) . " KiB"
+            . ", recorded $closed_ids unused guest IDs in the smallest"
+            . " gaps as used\n";
+    } elsif (length($output) > $SIZE_WARN) {
+        warn "$filename is "
+            . int(length($output) / 1024) . " KiB"
+            . ", the smallest gaps between used guest IDs will be"
+            . " closed beyond "
+            . ($SIZE_MAX / 1024)
+            . " KiB\n";
+    }
 
     return $output;
 }
-- 
2.47.3