[#969] Random allocator

3 files changed, 407 insertions, 1 deletions

diff --git a/src/lib/dhcpsrv/tests/Makefile.am b/src/lib/dhcpsrv/tests/Makefile.am
index 8ef2476920..ea2d29b5f9 100644
--- a/src/lib/dhcpsrv/tests/Makefile.am
+++ b/src/lib/dhcpsrv/tests/Makefile.am
@@ -123,6 +123,7 @@ libdhcpsrv_unittests_SOURCES += pgsql_host_data_source_unittest.cc
 endif
 libdhcpsrv_unittests_SOURCES += pool_unittest.cc
 libdhcpsrv_unittests_SOURCES += random_allocation_state_unittest.cc
+libdhcpsrv_unittests_SOURCES += random_allocator_unittest.cc
 libdhcpsrv_unittests_SOURCES += resource_handler_unittest.cc
 libdhcpsrv_unittests_SOURCES += sanity_checks_unittest.cc
 libdhcpsrv_unittests_SOURCES += shared_network_parser_unittest.cc
diff --git a/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc b/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc
index 339f53e3a6..bae361aa21 100644
--- a/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc
+++ b/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (C) 2020 Internet Systems Consortium, Inc. ("ISC")
+// Copyright (C) 2020-2022 Internet Systems Consortium, Inc. ("ISC")
 //
 // This Source Code Form is subject to the terms of the Mozilla Public
 // License, v. 2.0. If a copy of the MPL was not distributed with this
@@ -137,6 +137,41 @@ TEST(IPRangePermutationTest, pd) {
     EXPECT_TRUE(addrs.begin()->isV6Zero());
 }
 
+// This test verifies that a permutation of delegated prefixes is
+// generated from the prefix range specified using first and last
+// address.
+TEST(IPRangePermutationTest, pdStartEnd) {
+    PrefixRange range(IOAddress("3000::"), IOAddress("3000::ffff"), 120);
+    IPRangePermutation perm(range);
+
+    std::set<IOAddress> addrs;
+    bool done = false;
+    for (auto i = 0; i < 257; ++i) {
+        auto next = perm.next(done);
+        if (!next.isV6Zero()) {
+            // Make sure the prefix is within the range.
+            EXPECT_LE(range.start_, next);
+            EXPECT_LE(next, range.end_);
+        }
+        // If we went over all delegated prefixes in the range, the flags indicating
+        // that the permutation is exhausted should be set to true.
+        if (i >= 255) {
+            EXPECT_TRUE(done);
+            EXPECT_TRUE(perm.exhausted());
+        } else {
+            // We're not done yet, so these flag should still be false.
+            EXPECT_FALSE(done);
+            EXPECT_FALSE(perm.exhausted());
+        }
+        // Insert the prefix returned to the set.
+        addrs.insert(next);
+    }
+
+    // We should have recorded 257 unique addresses, including the zero address.
+    EXPECT_EQ(257, addrs.size());
+    EXPECT_TRUE(addrs.begin()->isV6Zero());
+}
+
 // This test verifies that it is possible to reset the permutation state.
 TEST(IPRangePermutationTest, reset) {
     // Create address range with 11 addresses.
diff --git a/src/lib/dhcpsrv/tests/random_allocator_unittest.cc b/src/lib/dhcpsrv/tests/random_allocator_unittest.cc
new file mode 100644
index 0000000000..79dbfa5d6f
--- /dev/null
+++ b/src/lib/dhcpsrv/tests/random_allocator_unittest.cc
@@ -0,0 +1,370 @@
+// Copyright (C) 2022 Internet Systems Consortium, Inc. ("ISC")
+//
+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+#include <config.h>
+#include <asiolink/io_address.h>
+#include <dhcpsrv/random_allocator.h>
+#include <dhcpsrv/tests/alloc_engine_utils.h>
+#include <boost/make_shared.hpp>
+#include <gtest/gtest.h>
+#include <set>
+#include <vector>
+#include <sstream>
+
+using namespace isc::asiolink;
+using namespace std;
+
+namespace isc {
+namespace dhcp {
+namespace test {
+
+using RandomAllocatorTest4 = AllocEngine4Test;
+
+// Test allocating IPv4 addresses when a subnet has a single pool.
+TEST_F(RandomAllocatorTest4, singlePool) {
+    RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+    // Remember returned addresses, so we can verify that unique addresses
+    // are returned.
+    std::set<IOAddress> addresses;
+    for (auto i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+        addresses.insert(candidate);
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate, cc_));
+    }
+    // The pool comprises 10 addresses. All should be returned.
+    EXPECT_EQ(10, addresses.size());
+}
+
+// Test allocating IPv4 addresses from multiple pools.
+TEST_F(RandomAllocatorTest4, manyPools) {
+    RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+    // Add several more pools.
+    for (int i = 2; i < 10; ++i) {
+        stringstream min, max;
+        min << "192.0.2." << i * 10 + 1;
+        max << "192.0.2." << i * 10 + 9;
+        auto pool = boost::make_shared<Pool4>(IOAddress(min.str()),
+                                              IOAddress(max.str()));
+        subnet_->addPool(pool);
+    }
+
+    // First pool (.100 - .109) has 10 addresses.
+    // There are 8 extra pools with 9 addresses in each.
+    int total = 10 + 8 * 9;
+
+    // Repeat allocation of all addresses several times. Make sure that
+    // the same addresses are returned when all pools are exhausted.
+    for (auto j = 0; j < 6; ++j) {
+        std::set<IOAddress> addresses_set;
+        std::vector<IOAddress> addresses_vector;
+        std::vector<PoolPtr> pools_vector;
+
+        // Pick random addresses the number of times equal to the
+        // subnet capacity to ensure that all addresses are returned.
+        for (auto i = 0; i < total; ++i) {
+            IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+            addresses_set.insert(candidate);
+            addresses_vector.push_back(candidate);
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate, cc_));
+            pools_vector.push_back(subnet_->getPool(Lease::TYPE_V4, candidate));
+        }
+        // Make sure that unique addresses have been returned.
+        EXPECT_EQ(total, addresses_set.size());
+
+        // Verify that the addresses are returned in the random order.
+        // Count how many times we found consecutive addresses. It should
+        // be 0 or close to 0.
+        int consecutives = 0;
+        for (auto k = 0; k < addresses_vector.size()-1; ++k) {
+            if (addresses_vector[k].toUint32() == addresses_vector[k+1].toUint32()-1) {
+                ++consecutives;
+            }
+        }
+        // Ideally, the number of consecutive occurences should be 0 but we
+        // allow some to make sure the test doesn't fall over sporadically.
+        EXPECT_LT(consecutives, addresses_vector.size()/4);
+
+        // Repeat similar check for pools. The pools should be picked in the
+        // random order too.
+        int pool_matches = 0;
+        for (auto k = 0; k < pools_vector.size()-1; ++k) {
+            if (pools_vector[k] == subnet_->getPools(Lease::TYPE_V4)[k]) {
+                ++pool_matches;
+            }
+        }
+        EXPECT_LT(pool_matches, pools_vector.size()/2);
+    }
+}
+
+// Test that the allocator returns a zero address when there are no
+// pools.
+TEST_F(RandomAllocatorTest4, noPools) {
+   RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+   subnet_->delPools(Lease::TYPE_V4);
+
+   IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+   EXPECT_TRUE(candidate.isV4Zero());
+}
+
+// Test that the allocator respects client classes while it picks
+// pools and addresses.
+TEST_F(RandomAllocatorTest4, clientClasses) {
+   RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+   // First pool only allows the client class foo.
+   pool_->allowClientClass("foo");
+
+   // Second pool. It only allows client class bar.
+   auto pool1 = boost::make_shared<Pool4>(IOAddress("192.0.2.120"),
+                                         IOAddress("192.0.2.129"));
+   pool1->allowClientClass("bar");
+   subnet_->addPool(pool1);
+
+   // Third pool. It only allows client class foo.
+   auto pool2 = boost::make_shared<Pool4>(IOAddress("192.0.2.140"),
+                                          IOAddress("192.0.2.149"));
+   pool2->allowClientClass("foo");
+   subnet_->addPool(pool2);
+
+   // Forth pool. It only allows client class bar.
+   auto pool3 = boost::make_shared<Pool4>(IOAddress("192.0.2.160"),
+                                          IOAddress("192.0.2.169"));
+   pool3->allowClientClass("bar");
+   subnet_->addPool(pool3);
+
+   // Remember offered addresses.
+   std::set<IOAddress> addresses_set;
+
+   // Simulate client's request belonging to the class bar.
+   cc_.insert("bar");
+   for (auto i = 0; i < 40; ++i) {
+       // Allocate random addresses and make sure they belong to the
+       // pools associated with the class bar.
+       IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(pool1->inRange(candidate) || pool3->inRange(candidate));
+   }
+   EXPECT_EQ(20, addresses_set.size());
+
+   addresses_set.clear();
+
+   // Simulate the case that the client also belongs to the class foo.
+   // All pools should now be available.
+   cc_.insert("foo");
+   for (auto i = 0; i < 60; ++i) {
+       IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(subnet_->inRange(candidate));
+   }
+   EXPECT_EQ(40, addresses_set.size());
+
+   // When the client does not belong to any client class the allocator
+   // can't offer any address to the client.
+   cc_.clear();
+   IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+   EXPECT_TRUE(candidate.isV4Zero());
+}
+
+using RandomAllocatorTest6 = AllocEngine6Test;
+
+// Test allocating IPv6 addresses when a subnet has a single pool.
+TEST_F(RandomAllocatorTest6, singlePool) {
+    RandomAllocator alloc(Lease::TYPE_NA, subnet_);
+
+    // Remember returned addresses, so we can verify that unique addresses
+    // are returned.
+    std::set<IOAddress> addresses;
+    for (auto i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+        addresses.insert(candidate);
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate, cc_));
+    }
+    // The pool comprises 17 addresses. All should be returned.
+    EXPECT_EQ(17, addresses.size());
+}
+
+// Test allocating IPv6 addresses from multiple pools.
+TEST_F(RandomAllocatorTest6, manyPools) {
+    RandomAllocator alloc(Lease::TYPE_NA, subnet_);
+
+    // Add several more pools.
+    for (int i = 2; i < 10; ++i) {
+        stringstream min, max;
+        min << "2001:db8:1::" << hex << i * 16 + 1;
+        max << "2001:db8:1::" << hex << i * 16 + 9;
+        auto pool = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                              IOAddress(min.str()),
+                                              IOAddress(max.str()));
+        subnet_->addPool(pool);
+    }
+
+    // First pool (::10 - ::20) has 17 addresses.
+    // There are 8 extra pools with 9 addresses in each.
+    int total = 17 + 8 * 9;
+
+    // Repeat allocation of all addresses several times. Make sure that
+    // the same addresses are returned when all pools are exhausted.
+    for (auto j = 0; j < 6; ++j) {
+        std::set<IOAddress> addresses_set;
+        std::vector<IOAddress> addresses_vector;
+        std::vector<PoolPtr> pools_vector;
+
+        // Pick random addresses the number of times equal to the
+        // subnet capacity to ensure that all addresses are returned.
+        for (auto i = 0; i < total; ++i) {
+            IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+            addresses_set.insert(candidate);
+            addresses_vector.push_back(candidate);
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate));
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate, cc_));
+            pools_vector.push_back(subnet_->getPool(Lease::TYPE_NA, candidate));
+        }
+        // Make sure that unique addresses have been returned.
+        EXPECT_EQ(total, addresses_set.size());
+
+        // Verify that the addresses are returned in the random order.
+        // Count how many times we found consecutive addresses. It should
+        // be 0 or close to 0.
+        int consecutives = 0;
+        for (auto k = 0; k < addresses_vector.size()-1; ++k) {
+            
+            if (IOAddress::increase(addresses_vector[k]) == addresses_vector[k+1]) {
+                ++consecutives;
+            }
+        }
+        // Ideally, the number of consecutive occurences should be 0 but we
+        // allow some to make sure the test doesn't fall over sporadically.
+        EXPECT_LT(consecutives, addresses_vector.size()/4);
+
+        // Repeat similar check for pools. The pools should be picked in the
+        // random order too.
+        int pool_matches = 0;
+        for (auto k = 0; k < pools_vector.size()-1; ++k) {
+            if (pools_vector[k] == subnet_->getPools(Lease::TYPE_NA)[k]) {
+                ++pool_matches;
+            }
+        }
+        EXPECT_LT(pool_matches, pools_vector.size()/2);
+    }
+}
+
+// Test that the allocator respects client classes while it picks
+// pools and addresses.
+TEST_F(RandomAllocatorTest6, clientClasses) {
+   RandomAllocator alloc(Lease::TYPE_NA, subnet_);
+
+   // First pool only allows the client class foo.
+   pool_->allowClientClass("foo");
+
+   // Second pool. It only allows client class bar.
+   auto pool1 = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                          IOAddress("2001:db8:1::120"),
+                                          IOAddress("2001:db8:1::129"));
+   pool1->allowClientClass("bar");
+   subnet_->addPool(pool1);
+
+   // Third pool. It only allows client class foo.
+   auto pool2 = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                          IOAddress("2001:db8:1::140"),
+                                          IOAddress("2001:db8:1::149"));
+   pool2->allowClientClass("foo");
+   subnet_->addPool(pool2);
+
+   // Forth pool. It only allows client class bar.
+   auto pool3 = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                          IOAddress("2001:db8:1::160"),
+                                          IOAddress("2001:db8:1::169"));
+   pool3->allowClientClass("bar");
+   subnet_->addPool(pool3);
+
+   // Remember offered addresses.
+   std::set<IOAddress> addresses_set;
+
+   // Simulate client's request belonging to the class bar.
+   cc_.insert("bar");
+   for (auto i = 0; i < 60; ++i) {
+       // Allocate random addresses and make sure they belong to the
+       // pools associated with the class bar.
+       IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(pool1->inRange(candidate) || pool3->inRange(candidate));
+   }
+   EXPECT_EQ(20, addresses_set.size());
+
+   addresses_set.clear();
+
+   // Simulate the case that the client also belongs to the class foo.
+   // All pools should now be available.
+   cc_.insert("foo");
+   for (auto i = 0; i < 100; ++i) {
+       IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(subnet_->inRange(candidate));
+   }
+   EXPECT_EQ(47, addresses_set.size());
+
+   // When the client does not belong to any client class the allocator
+   // can't offer any address to the client.
+   cc_.clear();
+   IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("0.0.0.0"));
+   EXPECT_TRUE(candidate.isV4Zero());
+}
+
+// Test allocating delegated prefixes when a subnet has a single pool.
+TEST_F(RandomAllocatorTest6, singlePdPool) {
+    RandomAllocator alloc(Lease::TYPE_PD, subnet_);
+
+    // Remember returned prefixes, so we can verify that unique addresses
+    // are returned.
+    std::set<IOAddress> prefixes;
+    for (auto i = 0; i < 66000; ++i) {
+        IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+        prefixes.insert(candidate);
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate, cc_));
+    }
+    // The pool comprises 65536 prefixes. All should be returned.
+    EXPECT_EQ(65536, prefixes.size());
+}
+
+// Test allocating delegated prefixes from multiple pools.
+TEST_F(RandomAllocatorTest6, manyPdPools) {
+    RandomAllocator alloc(Lease::TYPE_PD, subnet_);
+
+    for (auto i = 0; i < 10; ++i) {
+        ostringstream s;
+        s << "300" << hex << i+1 << "::";
+        auto pool = boost::make_shared<Pool6>(Lease::TYPE_PD,
+                                              IOAddress(s.str()),
+                                              120,
+                                              128);
+        subnet_->addPool(pool);
+    }
+
+    size_t total = 65536 + 10*256;
+
+    for (auto j = 0; j < 2; ++j) {
+        std::set<IOAddress> prefixes;
+        for (auto i = 0; i < total; ++i) {
+            IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+            prefixes.insert(candidate);
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate));
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate, cc_));
+        }
+        // Make sure that unique prefixes have been returned.
+        EXPECT_EQ(total, prefixes.size());
+    }
+}
+
+} // end of isc::dhcp::test namespace
+} // end of isc::dhcp namespace
+} // end of isc namespace