diff options
Diffstat (limited to '')
| -rwxr-xr-x | scripts/sql/generate_pool_addresses.pl | 456 |
1 files changed, 456 insertions, 0 deletions
diff --git a/scripts/sql/generate_pool_addresses.pl b/scripts/sql/generate_pool_addresses.pl new file mode 100755 index 0000000..85fe030 --- /dev/null +++ b/scripts/sql/generate_pool_addresses.pl @@ -0,0 +1,456 @@ +#!/usr/bin/perl -Tw + +###################################################################### +# +# Copyright (C) 2020 Network RADIUS +# +# $Id$ +# +###################################################################### +# +# Helper script for populating IP pools with address entries. +# +# This script generates output that is useful for populating an IP pool for +# use with FreeRADIUS (and possibly other purposes). The pool may be +# implemented as an SQL IP Pool (rlm_sqlippool) or any other backing store +# that has one entry per IP address. +# +# This script output a list of address to add, retain and remove in order to +# align a pool to a specification. It is likely that you will want to +# process the output to generate the actual commands (e.g. SQL statements) +# that make changes to the datastore. For example: +# +# generate_pool_addresses.pl ... | align_sql_pools.pl postgresql +# +# +# Use with a single address range +# ------------------------------- +# +# For basic use, arguments can be provided to this script that denote the ends +# of a single IP (v4 or v6) address range together with the pool_name. +# +# Optionally the number of IPs to sparsely populate the range with can be +# provided. If the range is wider than a /16 then the population of the range +# is capped at 65536 IPs, unless otherwise specified. +# +# In the case that a sparse range is defined, a file containing pre-existing +# IP entries can be provided. The range will be populated with entries from +# this file that fall within the range, prior to the remainder of the range +# being populated with random address in the range. +# +# generate_pool_addresses.pl <pool_name> <range_start> <range_end> \ +# [ <capacity> [ <existing_ips_file> ] ] +# +# Note: Sparse ranges are populated using a deterministic, pseudo-random +# function. This allows pools to be trivially extended without having to +# supply the existing contents using a file. If you require +# less-predictable randomness or a different random sequence then remove +# or modify the line calling srand(), below. +# +# +# Use with multiple pools and address ranges +# ------------------------------------------ +# +# For more complex us, the script allows a set of pool definitions to be +# provided in a YAML file which describes a set of one or more pools, each +# containing a set of one or more ranges. The first argument in this case is +# always "yaml": +# +# generate_pool_addresses.pl yaml <pool_defs_yaml_file> [ <existing_ips_file> ] +# +# The format for the YAML file is demonstrated by the following example: +# +# pool_with_a_single_contiguous_range: +# - start: 192.0.2.3 +# end: 192.0.2.250 +# +# pool_with_a_single_sparse_range: +# - start: 10.10.10.0 +# end: 10.10.20.255 +# capacity: 200 +# +# pool_with_multiple_ranges: +# - start: 10.10.10.1 +# end: 10.10.10.253 +# - start: 10.10.100.0 +# end: 10.10.199.255 +# capacity: 1000 +# +# v6_pool_with_contiguous_range: +# - start: '2001:db8:1:2:3:4:5:10' +# end: '2001:db8:1:2:3:4:5:7f' +# +# v6_pool_with_sparse_range: +# - start: '2001:db8:1:2::' +# end: '2001:db8:1:2:ffff:ffff:ffff:ffff' +# capacity: 200 +# +# As with the basic use case, a file containing pre-existing IP entries can be +# provided with which any sparse ranges will be populated ahead of any random +# addresses. +# +# +# Output +# ------ +# +# The script returns line-based output beginning with "+", "=" or "-", and +# includes the pool_name and an IP address. +# +# + pool_name 192.0.2.10 +# +# A new address to be added to the corresponding range in the pool. +# +# = pool_name 192.0.2.20 +# +# A pre-existing address that is to be retained in the pool. (Only if a +# pre-existing pool entries file is given.) +# +# - pool_name 192.0.2.30 +# +# A pre-existing address that is to be removed from the corresponding +# range in the pool. (Only if a pre-existing pool entries file is given.) +# +# # main_pool: 192.0.10.3 - 192.0.12.250 (500) +# +# Lines beginning with "#" are comments +# +# +# Examples +# -------- +# +# generate_pool_addresses.pl main_pool 192.0.2.3 192.0.2.249 +# +# Will create a pool from a full populated IPv4 range, i.e. all IPs in the +# range available for allocation). +# +# generate_pool_addresses.pl main_pool 10.66.0.0 10.66.255.255 10000 +# +# Will create a pool from a sparsely populated IPv4 range for a /16 +# network (maximum of 65.536 addresses), populating the range with 10,000 +# addreses. The effective size of the pool can be increased in future by +# increasing the capacity of the range with: +# +# generate_pool_addresses.pl main_pool 10.66.0.0 10.66.255.255 20000 +# +# This generates the same initial set of 10,000 addresses as the previous +# example but will create 20,000 addresses overall, unless the random seed +# has been amended since the initial run. +# +# generate_pool_addresses.pl main_pool 2001:db8:1:2:: \ +# 2001:db8:1:2:ffff:ffff:ffff:ffff +# +# Will create a pool from the IPv6 range 2001:db8:1:2::/64, initially +# populating the range with 65536 (by default) addresses. +# +# generate_pool_addresses.pl main_pool 2001:db8:1:2:: \ +# 2001:db8:1:2:ffff:ffff:ffff:ffff \ +# 10000 existing_ips.txt +# +# Will create a pool using the same range as the previous example, but +# this time the range will be populated with 10,000 addresses. The range +# will be populated using lines extracted from the `existing_ips.txt` file +# that represent IPs which fall within range. +# +# generate_pool_addresses.pl yaml pool_defs.yml existing_ips.txt +# +# Will create one of more pools using the definitions found in the +# pool_defs.yml YAML file. The pools will contain one or more ranges with +# each of the ranges first being populated with entries from the +# existing_ips.txt file that fall within the range, before being filled +# with random addresses to the defined capacity. +# + +use strict; +use Net::IP qw/ip_bintoip ip_iptobin ip_bincomp ip_binadd ip_is_ipv4 ip_is_ipv6/; + +my $yaml_available = 0; + +eval { + require YAML::XS; + YAML::XS->import('LoadFile'); + $yaml_available = 1; +}; + +if ($#ARGV < 2 || $#ARGV > 4) { + usage(); + exit 1; +} + +if ($ARGV[0] eq 'yaml') { + + if ($#ARGV > 3) { + usage(); + exit 1; + } + + unless ($yaml_available) { + die "ERROR: YAML is not available. Install the YAML::XS Perl module."; + } + process_yaml_file(); + + goto done; + +} + +process_commandline(); + +done: + +exit 0; + + +sub usage { + print STDERR <<'EOF' +Usage: + generate_pool_addresses.pl <pool_name> <range_start> <range_end> [ <capacity> [ <existing_ips_file> ] ] +or: + generate_pool_addresses.pl yaml <pool_defs_yaml_file> [ <existing_ips_file> ] + +EOF +} + + +sub process_commandline { + + $SIG{__DIE__} = sub { usage(); die(@_); }; + + my $pool_name = $ARGV[0]; + my $range_start = $ARGV[1]; + my $range_end = $ARGV[2]; + my $capacity = $ARGV[3]; + + my @entries = (); + @entries = load_entries($ARGV[4]) if ($#ARGV >= 4); + + handle_range($pool_name, $range_start, $range_end, $capacity, @entries); + +} + + +sub process_yaml_file { + + my $yaml_file = $ARGV[1]; + + unless (-r $yaml_file) { + die "ERROR: Cannot open <pool_defs_yaml_file> for reading: $yaml_file"; + } + + my %pool_defs = %{LoadFile($yaml_file)}; + + my @entries = (); + @entries = load_entries($ARGV[2]) if ($#ARGV >= 2); + + foreach my $pool_name (sort keys %pool_defs) { + foreach my $range (@{$pool_defs{$pool_name}}) { + my $range_start = $range->{start}; + my $range_end = $range->{end}; + my $capacity = $range->{capacity}; + handle_range($pool_name, $range_start, $range_end, $capacity, @entries); + } + } + +} + + +sub load_entries { + + my $entries_file = shift; + + my @entries = (); + unless (-r $entries_file) { + die "ERROR: Cannot open <existing_ips_file> for reading: $entries_file" + } + open(my $fh, "<", $entries_file) || die "Failed to open $entries_file"; + while(<$fh>) { + chomp; + push @entries, $_; + } + + return @entries; + +} + + +sub handle_range { + + my $pool_name = shift; + my $range_start = shift; + my $range_end = shift; + my $capacity = shift; + my @entries = @_; + + unless (ip_is_ipv4($range_start) || ip_is_ipv6($range_start)) { + die "ERROR: Incorrectly formatted IPv4/IPv6 address for range_start: $range_start"; + } + + unless (ip_is_ipv4($range_end) || ip_is_ipv6($range_end)) { + die "ERROR: Incorrectly formatted IPv4/IPv6 address for range_end: $range_end"; + } + + my $ip_start = new Net::IP($range_start); + my $ip_end = new Net::IP($range_end); + my $ip_range = new Net::IP("$range_start - $range_end"); + + unless (defined $ip_range) { + die "ERROR: The range defined by <range_start> - <range_end> is invalid: $range_start - $range_end"; + } + + my $range_size = $ip_range->size; + $capacity = $range_size < 65536 ? "$range_size" : 65536 unless defined $capacity; + + if ($range_size < $capacity) { + $capacity = "$range_size"; + warn "WARNING: Insufficent IPs in the range. Will create $capacity entries."; + } + + # Prune the entries to only those within the specified range + for (my $i = 0; $i <= $#entries; $i++) { + my $version = ip_is_ipv4($entries[$i]) ? 4 : 6; + my $binip = ip_iptobin($entries[$i],$version); + if ($ip_start->version != $version || + ip_bincomp($binip, 'lt', $ip_start->binip) == 1 || + ip_bincomp($binip, 'gt', $ip_end->binip) == 1) { + $entries[$i]=''; + } + } + + # + # We use the sparse method if the number of entries available occupies < 80% of + # the network range, otherwise we use a method that involves walking the + # entire range. + # + + srand(42); # Set the seed for the PRNG + + if (length($range_size) > 9 || $capacity / "$range_size" < 0.8) { # From "BigInt" to FP + @entries = sparse_fill($pool_name, $ip_start, $ip_end, $capacity, @entries); + } else { + @entries = dense_fill($pool_name, $ip_start, $ip_end, $ip_range, $capacity, @entries); + } + + print "# $pool_name: $range_start - $range_end ($capacity)\n"; + print "$_\n" foreach @entries; + print "\n"; + +} + + +# +# With this sparse fill method we randomly allocate within the scope of the +# smallest enclosing network prefix, checking that we are within the given +# range, retrying if we are outside or we hit a duplicate. +# +# This method can efficiently choose a small number of addresses relative to +# the size of the range. It becomes slower as the population of a range nears +# the range's limit since it is harder to choose a free address at random. +# +# It is useful for selecting a handful of addresses from an enourmous IPv6 /64 +# network for example. +# +sub sparse_fill { + + my $pool_name = shift; + my $ip_start = shift; + my $ip_end = shift; + my $capacity = shift; + my @entries = @_; + + # Find the smallest network that encloses the given range + my $version = $ip_start->version; + ( $ip_start->binip ^ $ip_end->binip ) =~ /^\0*/; + my $net_prefix = $+[0]; + my $net_bits = substr($ip_start->binip, 0, $net_prefix); + my $host_length = length($ip_start->binip) - $net_prefix; + + my %ips = (); + my $i = 0; + while ($i < $capacity) { + + # Use the given entries first + my $rand_ip; + my $given_lease = 0; + shift @entries while $#entries >= 0 && $entries[0] eq ''; + if ($#entries >= 0) { + $rand_ip = ip_iptobin(shift @entries, $version); + $given_lease = 1; + } else { + $rand_ip = $net_bits; + $rand_ip .= [0..1]->[rand 2] for 1..$host_length; + # Check that we are inside the given range + next if ip_bincomp($rand_ip, 'lt', $ip_start->binip) == 1 || + ip_bincomp($rand_ip, 'gt', $ip_end->binip) == 1; + } + + next if defined $ips{$rand_ip}; + + $ips{$rand_ip} = $given_lease ? '=' : '+'; + $i++; + + } + + # Allow the pool to be shrunk + $ips{ip_iptobin($_, $version)} = '-' foreach @entries; + + return map { $ips{$_}." ".$pool_name." ".ip_bintoip($_, $version) } sort keys %ips; + +} + + +# +# With this dense fill method, after first selecting the given entries we walk +# the network range picking IPs with evenly distributed probability. +# +# This method can efficiently choose a large number of addresses relative to +# the size of a range, provided that the range isn't massive. It becomes +# slower as the range size increases. +# +sub dense_fill { + + my $pool_name = shift; + my $ip_start = shift; + my $ip_end = shift; + my $ip_range = shift; + my $capacity = shift; + my @entries = @_; + + my $version = $ip_start->version; + + my $one = ("0"x($version == 4 ? 31 : 127)) . '1'; + + my %ips = (); + my $remaining_entries = $capacity; + my $remaining_ips = $ip_range->size; + my $ipbin = $ip_start->binip; + + while ($remaining_entries > 0 && (ip_bincomp($ipbin, 'le', $ip_end->binip) == 1)) { + + # Use the given entries first + shift @entries while $#entries >= 0 && $entries[0] eq ''; + if ($#entries >= 0) { + $ips{ip_iptobin(shift @entries, $version)} = '='; + $remaining_entries--; + $remaining_ips--; + next; + } + + goto next_ip if defined $ips{$ipbin}; + + # Skip the IP that we have already selected by given entries, otherwise + # randomly pick it + if (!defined $ips{$ipbin} && + (rand) <= $remaining_entries / "$remaining_ips") { # From "BigInt" to FP + $ips{$ipbin} = '+'; + $remaining_entries--; + } + + $remaining_ips--; + $ipbin = ip_binadd($ipbin,$one); + + } + + # Allow the pool to be shrunk + $ips{ip_iptobin($_, $version)} = '-' foreach @entries; + + return map { $ips{$_}." ".$pool_name." ".ip_bintoip($_, $version) } sort keys %ips; + +} |