[PATCH guest-common v6 04/18] add module to track previously used guest IDs

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

The /cluster/nextid API endpoint always suggests the lowest free
guest ID, so IDs of destroyed guests get handed out again. Offering
an opt-out requires recording every ID that has ever been in use
somewhere both the endpoint and the guest create and destroy paths
can reach.

Store them in /etc/pve/virtual-guest/used-guest-ids and register it as
a cfs file, so the list is kept in sync cluster-wide. IDs are stored as
"<start>-<end>" ranges and are not expanded per ID since cfs_read_file()
hands out a deep copy of the parsed data on every call, which gets
expensive on clusters that churn through many guests. Adjacent ranges
are merged on write to keep the file small. Entries that do not parse,
ranges with reversed bounds included, are skipped with a warning instead
of failing the whole read.

get_next_unused_id() returns the lowest ID at or above a given one that
is neither in use nor recorded as having been used previously.

Recording failures are non-critical and will only warn while 'unique' is
off.

Originally-by: Daniel Krambrock <krambrock@hrz.uni-marburg.de>
Originally-by: Severen Redwood <severen.redwood@sitehost.co.nz>
Signed-off-by: Michael Köppl <m.koeppl@proxmox.com>
---
 src/Makefile       |   1 +
 src/PVE/GuestID.pm | 132 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 133 insertions(+)
 create mode 100644 src/PVE/GuestID.pm

diff --git a/src/Makefile b/src/Makefile
index 030e7f7..ceba738 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -14,6 +14,7 @@ install: PVE
 	install -m 0644 PVE/Replication.pm ${PERL5DIR}/PVE/
 	install -m 0644 PVE/StorageTunnel.pm ${PERL5DIR}/PVE/
 	install -m 0644 PVE/Tunnel.pm ${PERL5DIR}/PVE/
+	install -m 0644 PVE/GuestID.pm ${PERL5DIR}/PVE/
 	install -d ${PERL5DIR}/PVE/Mapping
 	install -m 0644 PVE/Mapping/Dir.pm ${PERL5DIR}/PVE/Mapping/
 	install -m 0644 PVE/Mapping/PCI.pm ${PERL5DIR}/PVE/Mapping/
diff --git a/src/PVE/GuestID.pm b/src/PVE/GuestID.pm
new file mode 100644
index 0000000..862d92b
--- /dev/null
+++ b/src/PVE/GuestID.pm
@@ -0,0 +1,132 @@
+package PVE::GuestID;
+
+use v5.36;
+
+use PVE::Cluster qw(
+    cfs_lock_file
+    cfs_read_file
+    cfs_register_file
+    cfs_write_file
+);
+
+my $FILENAME = 'virtual-guest/used-guest-ids';
+
+my sub parse_id_list($filename, $raw) {
+    my $ranges = [];
+
+    return $ranges if !defined($raw);
+
+    for my $line (split(/\n/, $raw)) {
+        next if $line =~ m/^\s*$/;
+
+        if ($line =~ m/^(\d+)$/) {
+            push $ranges->@*, [$1, $1];
+        } elsif ($line =~ m/^(\d+)-(\d+)$/) {
+            my ($start, $end) = ($1, $2);
+            if ($start > $end) {
+                warn "skipping reversed range in $filename: $line\n";
+                next;
+            }
+            push $ranges->@*, [$start, $end];
+        } else {
+            warn "skipping invalid entry in $filename: $line\n";
+        }
+    }
+
+    # lookup and insertion rely on the ranges being ordered by start,
+    # merging adjacent and overlapping ones is done when writing the
+    # id list.
+    return [sort { $a->[0] <=> $b->[0] } $ranges->@*];
+}
+
+my sub next_unused($ranges, $id) {
+    my $next = $id;
+    for my $range ($ranges->@*) {
+        my ($start, $end) = $range->@*;
+        next if $end < $next;
+        last if $next < $start;
+        $next = $end + 1;
+    }
+    return $next;
+}
+
+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);
+
+    for my $range ($ranges->@*) {
+        my ($curr_start, $curr_end) = $range->@*;
+
+        if (!defined($start)) {
+            ($start, $last) = ($curr_start, $curr_end);
+        } elsif ($curr_start <= $last + 1) {
+            $last = $curr_end if $curr_end > $last;
+        } else {
+            $output .= format_entry($start, $last);
+            ($start, $last) = ($curr_start, $curr_end);
+        }
+    }
+
+    $output .= format_entry($start, $last) if defined($start);
+
+    return $output;
+}
+
+# Returns the lowest ID at or above $id that is neither taken by an
+# existing guest nor recorded as used before.
+sub get_next_unused_id($id) {
+    my $ranges = cfs_read_file($FILENAME);
+    my $vmlist = PVE::Cluster::get_vmlist() // {};
+    my $existing = $vmlist->{ids} // {};
+
+    $id = next_unused($ranges, $id);
+    while (defined($existing->{$id})) {
+        $id = next_unused($ranges, $id + 1);
+    }
+
+    return $id;
+}
+
+my sub insert_id($ranges, $id) {
+    my $i = 0;
+
+    while ($i < @$ranges && $ranges->[$i]->[1] < $id) {
+        $i++;
+    }
+
+    return 0 if $i < @$ranges && $ranges->[$i]->[0] <= $id;
+
+    splice(@$ranges, $i, 0, [$id, $id]);
+
+    return 1;
+}
+
+sub register_used_id($id) {
+    cfs_lock_file(
+        $FILENAME,
+        10,
+        sub {
+            my $ranges = cfs_read_file($FILENAME);
+
+            return if !insert_id($ranges, $id);
+
+            cfs_write_file($FILENAME, $ranges);
+        },
+    );
+
+    if (my $err = $@) {
+        my $dc_conf = cfs_read_file('datacenter.cfg');
+
+        my $emsg = "unable to record guest ID $id as used";
+        die "$emsg - $err" if $dc_conf->{'next-id'}->{unique};
+        warn "$emsg - $err";
+    }
+}
+
+cfs_register_file($FILENAME, \&parse_id_list, \&write_id_list);
+
+1;
-- 
2.47.3