[PATCH guest-common v6 07/18] 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>
---
Hope I didn't overdo it with the comments here, but I felt that some
explanatory comments were warranted. I also considered aggressively
merging ranges until the file sizes is at $SIZE_WARN again. That would
mean that even more guest IDs would be marked as used even though not
strictly necessary. Feedback here would be much appreciated. I think it
can be argued that repeated warnings if the file size if between
$SIZE_WARN and $SIZE_MAX are annoying, but I'm not sure if the "lost"
guest IDs would be worth it.

 src/PVE/GuestID.pm | 104 ++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 93 insertions(+), 11 deletions(-)

diff --git a/src/PVE/GuestID.pm b/src/PVE/GuestID.pm
index 862d92b..4ab6f2d 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 = [];

@@ -54,24 +58,102 @@ 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 $last = $merged->[-1];

-        if (!defined($start)) {
-            ($start, $last) = ($curr_start, $curr_end);
-        } elsif ($curr_start <= $last + 1) {
-            $last = $curr_end if $curr_end > $last;
+        if ($last && $start <= $last->[1] + 1) {
+            $last->[1] = $end if $end > $last->[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 $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, $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 joining the ranges at indices 1-3 and at 4 5, this would be:
+    #   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 $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
+        $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