Re: [PATCH guest-common v6 07/18] guest id: keep used ID list below the pmxcfs file size limit

[Fiona Ebner <f.ebner@proxmox.com>]

Am 24.09.26 um 6:15 PM schrieb Michael Köppl:
> 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

Yes, please! Comments are very nice to have if they describe context,
intention, rationale, pitfalls etc. (i.e. if they don't just repeat the
code 1:1 in words).

> 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.

In practice, this should be very rare. Essentially only with very
specific ID usage patterns like only using even numbers. And if using
such patterns, closing the gaps only gets rids of IDs they didn't use in
their patterns anyways. If somebody really complains about too many
warnings, we can still adapt later, but I think the current approach is
fine.

> 
>  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];

I'd suggest s/$last/$current_range/ or s/$last/$current_merge/

IMHO, $last is too similar to $end.

> 
> -        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) {

Since there are different sizes handled below, I'd be more precise with
something like $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 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)

Since it was not immediately obvious to me why it would be 3, 2, 3
instead of 3, 3, 3, I suggest expanding the comment:

>     # 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 the 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)

Hope I didn't get it wrong ^^

> +    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