[#969] Random allocation state added

5 files changed, 223 insertions, 0 deletions

diff --git a/src/lib/dhcpsrv/Makefile.am b/src/lib/dhcpsrv/Makefile.am
index 740749607b..6a952c8b6f 100644
--- a/src/lib/dhcpsrv/Makefile.am
+++ b/src/lib/dhcpsrv/Makefile.am
@@ -143,6 +143,7 @@ libkea_dhcpsrv_la_SOURCES += pgsql_lease_mgr.cc pgsql_lease_mgr.h
 endif
 
 libkea_dhcpsrv_la_SOURCES += pool.cc pool.h
+libkea_dhcpsrv_la_SOURCES += random_allocation_state.cc random_allocation_state.h
 libkea_dhcpsrv_la_SOURCES += resource_handler.cc resource_handler.h
 libkea_dhcpsrv_la_SOURCES += sanity_checker.cc sanity_checker.h
 libkea_dhcpsrv_la_SOURCES += shared_network.cc shared_network.h
@@ -362,6 +363,7 @@ libkea_dhcpsrv_include_HEADERS = \
 	network.h \
 	network_state.h \
 	pool.h \
+	random_allocation_state.h \
 	resource_handler.h \
 	sanity_checker.h \
 	shared_network.h \
diff --git a/src/lib/dhcpsrv/random_allocation_state.cc b/src/lib/dhcpsrv/random_allocation_state.cc
new file mode 100644
index 0000000000..0a8fcb5d4d
--- /dev/null
+++ b/src/lib/dhcpsrv/random_allocation_state.cc
@@ -0,0 +1,40 @@
+// 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 <dhcpsrv/random_allocation_state.h>
+#include <boost/make_shared.hpp>
+
+using namespace isc::asiolink;
+
+namespace isc {
+namespace dhcp {
+
+PoolRandomAllocationStatePtr
+PoolRandomAllocationState::create(const PoolPtr& pool) {
+    if (pool->getType() == Lease::TYPE_PD) {
+        // Pool classes ensure that the proper type is used for
+        // the IPv6 specific lease types, so we can just cast
+        // to the Pool6 pointer.
+        auto pd_pool = boost::dynamic_pointer_cast<Pool6>(pool);
+        return (boost::make_shared<PoolRandomAllocationState>(pd_pool->getFirstAddress(),
+                                                              pd_pool->getLastAddress(),
+                                                              pd_pool->getLength()));
+    }
+    return (boost::make_shared<PoolRandomAllocationState>(pool->getFirstAddress(), pool->getLastAddress()));
+}
+
+PoolRandomAllocationState::PoolRandomAllocationState(const IOAddress& first, const IOAddress& last)
+    : permutation_(new IPRangePermutation(AddressRange(first, last))) {
+}
+
+PoolRandomAllocationState::PoolRandomAllocationState(const IOAddress& first, const IOAddress& last,
+                                                     const uint8_t delegated)
+    : permutation_(new IPRangePermutation(PrefixRange(first, last, delegated))) {
+}
+
+} // end of namespace isc::dhcp
+} // end of namespace isc
diff --git a/src/lib/dhcpsrv/random_allocation_state.h b/src/lib/dhcpsrv/random_allocation_state.h
new file mode 100644
index 0000000000..610d38bdf8
--- /dev/null
+++ b/src/lib/dhcpsrv/random_allocation_state.h
@@ -0,0 +1,74 @@
+// 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/.
+
+#ifndef RANDOM_ALLOCATION_STATE_H
+#define RANDOM_ALLOCATION_STATE_H
+
+#include <dhcpsrv/allocation_state.h>
+#include <dhcpsrv/ip_range_permutation.h>
+#include <dhcpsrv/pool.h>
+#include <boost/shared_ptr.hpp>
+#include <cstdint>
+
+namespace isc {
+namespace dhcp {
+
+/// @brief Forward declaration of the @c PoolRandomAllocationState.
+class PoolRandomAllocationState;
+
+/// @brief Type of the pointer to the @c PoolRandomAllocationState.
+typedef boost::shared_ptr<PoolRandomAllocationState> PoolRandomAllocationStatePtr;
+
+/// @brief Pool allocation state used by the random allocator.
+///
+/// It extends the base class with the mechanism that maintains
+/// an address or delegated prefix pool permutation. The
+/// permutation serves random, non-repeating leases.
+class PoolRandomAllocationState : public AllocationState {
+public:
+
+    /// @brief Factory function creating the state instance from pool.
+    ///
+    /// @param pool instance of the pool for which the allocation state
+    /// should be instantiated.
+    /// @return new allocation state instance.
+    static PoolRandomAllocationStatePtr create(const PoolPtr& pool);
+
+    /// @brief Constructor from an IP address pool.
+    ///
+    /// @param first first address in the pool.
+    /// @param last last address in the pool.
+    PoolRandomAllocationState(const asiolink::IOAddress& first,
+                              const asiolink::IOAddress& last);
+
+    /// @brief Constructor from a delegated prefix pool.
+    ///
+    /// @param first first address in the pool.
+    /// @param last last prefix in the pool.
+    /// @param delegated delegated prefix length.
+    PoolRandomAllocationState(const asiolink::IOAddress& first,
+                              const asiolink::IOAddress& last,
+                              const uint8_t delegated);
+
+    /// @brief Returns a pointer to the permutation of addresses
+    /// or delegated prefixes.
+    ///
+    /// @return permutation instance.
+    IPRangePermutationPtr getPermutation() const {
+        return (permutation_);
+    }
+
+private:
+
+    /// @brief Permutation instance for the pool.
+    IPRangePermutationPtr permutation_;
+};
+
+
+} // end of isc::dhcp namespace
+} // end of isc namespace
+
+#endif // RANDOM_ALLOCATION_STATE_H
diff --git a/src/lib/dhcpsrv/tests/Makefile.am b/src/lib/dhcpsrv/tests/Makefile.am
index c8a0c9d4ac..8ef2476920 100644
--- a/src/lib/dhcpsrv/tests/Makefile.am
+++ b/src/lib/dhcpsrv/tests/Makefile.am
@@ -122,6 +122,7 @@ libdhcpsrv_unittests_SOURCES += pgsql_lease_mgr_unittest.cc
 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 += 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/random_allocation_state_unittest.cc b/src/lib/dhcpsrv/tests/random_allocation_state_unittest.cc
new file mode 100644
index 0000000000..17f4ad96d8
--- /dev/null
+++ b/src/lib/dhcpsrv/tests/random_allocation_state_unittest.cc
@@ -0,0 +1,106 @@
+// 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/lease.h>
+#include <dhcpsrv/pool.h>
+#include <dhcpsrv/random_allocation_state.h>
+#include <testutils/multi_threading_utils.h>
+#include <boost/make_shared.hpp>
+#include <gtest/gtest.h>
+#include <set>
+
+using namespace isc;
+using namespace isc::asiolink;
+using namespace isc::dhcp;
+using namespace isc::test;
+
+namespace {
+
+// Test creating the random allocation state for an IPv4 pool.
+TEST(PoolRandomAllocationStateTest, ipv4Pool) {
+    // Create the pool and state.
+    IOAddress first("192.0.2.1");
+    IOAddress last("192.0.2.255");
+    auto pool = boost::make_shared<Pool4>(first, last);
+    auto state = PoolRandomAllocationState::create(pool);
+    ASSERT_TRUE(state);
+
+    // Make sure that the permutation has been initialized.
+    auto permutation = state->getPermutation();
+    ASSERT_TRUE(permutation);
+
+    // Keep the record of the addresses returned by the permutation
+    // to ensure it returns unique addresses.
+    std::set<IOAddress> addresses;
+    for (auto i = 0; i < 10; ++i) {
+        auto done = true;
+        auto next = permutation->next(done);
+        // Returned address must belong to the pool.
+        EXPECT_TRUE(pool->inRange(next));
+        EXPECT_FALSE(done);
+        addresses.insert(next);
+    }
+    // Make sure that unique addresses were returned.
+    EXPECT_EQ(10, addresses.size());
+}
+
+// Test creating the random allocation state for an IPv6 pool.
+TEST(PoolRandomAllocationStateTest, ipv6AddressPool) {
+    // Create the pool and state.
+    IOAddress first("2001:db8::1");
+    IOAddress last("2001:db8::1:0");
+    auto pool = boost::make_shared<Pool6>(Lease::TYPE_NA, first, last);
+    auto state = PoolRandomAllocationState::create(pool);
+    ASSERT_TRUE(state);
+
+    // Make sure that the permutation has been initialized.
+    auto permutation = state->getPermutation();
+    ASSERT_TRUE(permutation);
+
+    // Keep the record of the addresses returned by the permutation
+    // to ensure it returns unique addresses.
+    std::set<IOAddress> addresses;
+    for (auto i = 0; i < 10; ++i) {
+        auto done = true;
+        auto next = permutation->next(done);
+        // Returned address must belong to the pool.
+        EXPECT_TRUE(pool->inRange(next));
+        EXPECT_FALSE(done);
+        addresses.insert(next);
+    }
+    // Make sure that unique addresses were returned.
+    EXPECT_EQ(10, addresses.size());
+}
+
+// Test creating the random allocation state for an IPv6 prefix pool.
+TEST(PoolRandomAllocationStateTest, ipv6PrefixPool) {
+    // Create the pool and state.  
+    auto pool = boost::make_shared<Pool6>(Lease::TYPE_PD, IOAddress("2001:db8::"), 64, 96);
+    auto state = PoolRandomAllocationState::create(pool);
+    ASSERT_TRUE(state);
+
+    // Make sure that the permutation has been initialized.
+    auto permutation = state->getPermutation();
+    ASSERT_TRUE(permutation);
+
+    // Keep the record of the addresses returned by the permutation
+    // to ensure it returns unique prefixes.
+    std::set<IOAddress> prefixes;
+    for (auto i = 0; i < 10; ++i) {
+        auto done = true;
+        auto next = permutation->next(done);
+        // Returned prefix must belong to the pool.
+        EXPECT_TRUE(pool->inRange(next));
+        EXPECT_FALSE(done);
+        prefixes.insert(next);
+    }
+    // Make sure that unique prefixes were returned.
+    EXPECT_EQ(10, prefixes.size());
+}
+
+} // end of anonymous namespace