[#2348] Moved allocators outside the engine

11 files changed, 1182 insertions, 665 deletions

diff --git a/src/lib/dhcpsrv/Makefile.am b/src/lib/dhcpsrv/Makefile.am
index 21e6dfb548..da0622c726 100644
--- a/src/lib/dhcpsrv/Makefile.am
+++ b/src/lib/dhcpsrv/Makefile.am
@@ -64,6 +64,7 @@ libkea_dhcpsrv_la_SOURCES  =
 libkea_dhcpsrv_la_SOURCES += alloc_engine.cc alloc_engine.h
 libkea_dhcpsrv_la_SOURCES += alloc_engine_log.cc alloc_engine_log.h
 libkea_dhcpsrv_la_SOURCES += alloc_engine_messages.h alloc_engine_messages.cc
+libkea_dhcpsrv_la_SOURCES += allocator.h
 libkea_dhcpsrv_la_SOURCES += base_host_data_source.h
 libkea_dhcpsrv_la_SOURCES += cache_host_data_source.h
 libkea_dhcpsrv_la_SOURCES += callout_handle_store.h
@@ -114,6 +115,7 @@ libkea_dhcpsrv_la_SOURCES += hosts_log.cc hosts_log.h
 libkea_dhcpsrv_la_SOURCES += hosts_messages.h hosts_messages.cc
 libkea_dhcpsrv_la_SOURCES += ip_range.h ip_range.cc
 libkea_dhcpsrv_la_SOURCES += ip_range_permutation.h ip_range_permutation.cc
+libkea_dhcpsrv_la_SOURCES += iterative_allocator.cc iterative_allocator.h
 libkea_dhcpsrv_la_SOURCES += key_from_key.h
 libkea_dhcpsrv_la_SOURCES += lease.cc lease.h
 libkea_dhcpsrv_la_SOURCES += lease_file_loader.h
@@ -292,6 +294,7 @@ libkea_dhcpsrv_include_HEADERS = \
 	alloc_engine.h \
 	alloc_engine_log.h \
 	alloc_engine_messages.h \
+	allocator.h \
 	base_host_data_source.h \
 	cache_host_data_source.h \
 	callout_handle_store.h \
@@ -341,6 +344,7 @@ libkea_dhcpsrv_include_HEADERS = \
 	hosts_log.h \
 	ip_range.h \
 	ip_range_permutation.h \
+	iterative_allocator.h \
 	key_from_key.h \
 	lease.h \
 	lease_file_loader.h \
diff --git a/src/lib/dhcpsrv/alloc_engine.cc b/src/lib/dhcpsrv/alloc_engine.cc
index 1da842187d..327345e38e 100644
--- a/src/lib/dhcpsrv/alloc_engine.cc
+++ b/src/lib/dhcpsrv/alloc_engine.cc
@@ -17,6 +17,7 @@
 #include <dhcpsrv/dhcpsrv_log.h>
 #include <dhcpsrv/host_mgr.h>
 #include <dhcpsrv/host.h>
+#include <dhcpsrv/iterative_allocator.h>
 #include <dhcpsrv/lease_mgr_factory.h>
 #include <dhcpsrv/ncr_generator.h>
 #include <dhcpsrv/network.h>
@@ -34,7 +35,6 @@
 #include <boost/make_shared.hpp>
 
 #include <algorithm>
-#include <cstring>
 #include <limits>
 #include <sstream>
 #include <stdint.h>
@@ -90,230 +90,7 @@ AllocEngineHooks Hooks;
 namespace isc {
 namespace dhcp {
 
-AllocEngine::IterativeAllocator::IterativeAllocator(Lease::Type lease_type)
-    : Allocator(lease_type) {
-}
-
-isc::asiolink::IOAddress
-AllocEngine::IterativeAllocator::increasePrefix(const isc::asiolink::IOAddress& prefix,
-                                                const uint8_t prefix_len) {
-    if (!prefix.isV6()) {
-        isc_throw(BadValue, "Prefix operations are for IPv6 only (attempted to "
-                  "increase prefix " << prefix << ")");
-    }
-
-    // Get a buffer holding an address.
-    const std::vector<uint8_t>& vec = prefix.toBytes();
-
-    if (prefix_len < 1 || prefix_len > 128) {
-        isc_throw(BadValue, "Cannot increase prefix: invalid prefix length: "
-                  << prefix_len);
-    }
-
-    uint8_t n_bytes = (prefix_len - 1)/8;
-    uint8_t n_bits = 8 - (prefix_len - n_bytes*8);
-    uint8_t mask = 1 << n_bits;
-
-    // Explanation: n_bytes specifies number of full bytes that are in-prefix.
-    // They can also be used as an offset for the first byte that is not in
-    // prefix. n_bits specifies number of bits on the last byte that is
-    // (often partially) in prefix. For example for a /125 prefix, the values
-    // are 15 and 3, respectively. Mask is a bitmask that has the least
-    // significant bit from the prefix set.
-
-    uint8_t packed[V6ADDRESS_LEN];
-
-    // Copy the address. It must be V6, but we already checked that.
-    std::memcpy(packed, &vec[0], V6ADDRESS_LEN);
-
-    // Can we safely increase only the last byte in prefix without overflow?
-    if (packed[n_bytes] + uint16_t(mask) < 256u) {
-        packed[n_bytes] += mask;
-        return (IOAddress::fromBytes(AF_INET6, packed));
-    }
-
-    // Overflow (done on uint8_t, but the sum is greater than 255)
-    packed[n_bytes] += mask;
-
-    // Deal with the overflow. Start increasing the least significant byte
-    for (int i = n_bytes - 1; i >= 0; --i) {
-        ++packed[i];
-        // If we haven't overflowed (0xff->0x0) the next byte, then we are done
-        if (packed[i] != 0) {
-            break;
-        }
-    }
-
-    return (IOAddress::fromBytes(AF_INET6, packed));
-}
-
-isc::asiolink::IOAddress
-AllocEngine::IterativeAllocator::increaseAddress(const isc::asiolink::IOAddress& address,
-                                                 bool prefix,
-                                                 const uint8_t prefix_len) {
-    if (!prefix) {
-        return (IOAddress::increase(address));
-    } else {
-        return (increasePrefix(address, prefix_len));
-    }
-}
-
-isc::asiolink::IOAddress
-AllocEngine::IterativeAllocator::pickAddressInternal(const SubnetPtr& subnet,
-                                                     const ClientClasses& client_classes,
-                                                     const DuidPtr&,
-                                                     const IOAddress&) {
-    // Is this prefix allocation?
-    bool prefix = pool_type_ == Lease::TYPE_PD;
-    uint8_t prefix_len = 0;
-
-    // Let's get the last allocated address. It is usually set correctly,
-    // but there are times when it won't be (like after removing a pool or
-    // perhaps restarting the server).
-    IOAddress last = subnet->getLastAllocated(pool_type_);
-    bool valid = true;
-    bool retrying = false;
-
-    const PoolCollection& pools = subnet->getPools(pool_type_);
-
-    if (pools.empty()) {
-        isc_throw(AllocFailed, "No pools defined in selected subnet");
-    }
-
-    // first we need to find a pool the last address belongs to.
-    PoolCollection::const_iterator it;
-    PoolCollection::const_iterator first = pools.end();
-    PoolPtr first_pool;
-    for (it = pools.begin(); it != pools.end(); ++it) {
-        if (!(*it)->clientSupported(client_classes)) {
-            continue;
-        }
-        if (first == pools.end()) {
-            first = it;
-        }
-        if ((*it)->inRange(last)) {
-            break;
-        }
-    }
-
-    // Caller checked this cannot happen
-    if (first == pools.end()) {
-        isc_throw(AllocFailed, "No allowed pools defined in selected subnet");
-    }
-
-    // last one was bogus for one of several reasons:
-    // - we just booted up and that's the first address we're allocating
-    // - a subnet was removed or other reconfiguration just completed
-    // - perhaps allocation algorithm was changed
-    // - last pool does not allow this client
-    if (it == pools.end()) {
-        it = first;
-    }
-
-    for (;;) {
-        // Trying next pool
-        if (retrying) {
-            for (; it != pools.end(); ++it) {
-                if ((*it)->clientSupported(client_classes)) {
-                    break;
-                }
-            }
-            if (it == pools.end()) {
-                // Really out of luck today. That was the last pool.
-                break;
-            }
-        }
-
-        last = (*it)->getLastAllocated();
-        valid = (*it)->isLastAllocatedValid();
-        if (!valid && (last == (*it)->getFirstAddress())) {
-            // Pool was (re)initialized
-            (*it)->setLastAllocated(last);
-            subnet->setLastAllocated(pool_type_, last);
-            return (last);
-        }
-        // still can be bogus
-        if (valid && !(*it)->inRange(last)) {
-            valid = false;
-            (*it)->resetLastAllocated();
-            (*it)->setLastAllocated((*it)->getFirstAddress());
-        }
-
-        if (valid) {
-            // Ok, we have a pool that the last address belonged to, let's use it.
-            if (prefix) {
-                Pool6Ptr pool6 = boost::dynamic_pointer_cast<Pool6>(*it);
-
-                if (!pool6) {
-                    // Something is gravely wrong here
-                    isc_throw(Unexpected, "Wrong type of pool: "
-                              << (*it)->toText()
-                              << " is not Pool6");
-                }
-                // Get the prefix length
-                prefix_len = pool6->getLength();
-            }
-
-            IOAddress next = increaseAddress(last, prefix, prefix_len);
-            if ((*it)->inRange(next)) {
-                // the next one is in the pool as well, so we haven't hit
-                // pool boundary yet
-                (*it)->setLastAllocated(next);
-                subnet->setLastAllocated(pool_type_, next);
-                return (next);
-            }
-
-            valid = false;
-            (*it)->resetLastAllocated();
-        }
-        // We hit pool boundary, let's try to jump to the next pool and try again
-        ++it;
-        retrying = true;
-    }
-
-    // Let's rewind to the beginning.
-    for (it = first; it != pools.end(); ++it) {
-        if ((*it)->clientSupported(client_classes)) {
-            (*it)->setLastAllocated((*it)->getFirstAddress());
-            (*it)->resetLastAllocated();
-        }
-    }
-
-    // ok to access first element directly. We checked that pools is non-empty
-    last = (*first)->getLastAllocated();
-    (*first)->setLastAllocated(last);
-    subnet->setLastAllocated(pool_type_, last);
-    return (last);
-}
-
-AllocEngine::HashedAllocator::HashedAllocator(Lease::Type lease_type)
-    : Allocator(lease_type) {
-    isc_throw(NotImplemented, "Hashed allocator is not implemented");
-}
-
-isc::asiolink::IOAddress
-AllocEngine::HashedAllocator::pickAddressInternal(const SubnetPtr&,
-                                                  const ClientClasses&,
-                                                  const DuidPtr&,
-                                                  const IOAddress&) {
-    isc_throw(NotImplemented, "Hashed allocator is not implemented");
-}
-
-AllocEngine::RandomAllocator::RandomAllocator(Lease::Type lease_type)
-    : Allocator(lease_type) {
-    isc_throw(NotImplemented, "Random allocator is not implemented");
-}
-
-isc::asiolink::IOAddress
-AllocEngine::RandomAllocator::pickAddressInternal(const SubnetPtr&,
-                                                  const ClientClasses&,
-                                                  const DuidPtr&,
-                                                  const IOAddress&) {
-    isc_throw(NotImplemented, "Random allocator is not implemented");
-}
-
-AllocEngine::AllocEngine(AllocType engine_type, uint64_t attempts,
-                         bool ipv6)
+AllocEngine::AllocEngine(AllocType, uint64_t attempts, bool ipv6)
     : attempts_(attempts), incomplete_v4_reclamations_(0),
       incomplete_v6_reclamations_(0) {
 
@@ -321,39 +98,13 @@ AllocEngine::AllocEngine(AllocType engine_type, uint64_t attempts,
     Lease::Type basic_type = ipv6 ? Lease::TYPE_NA : Lease::TYPE_V4;
 
     // Initialize normal address allocators
-    switch (engine_type) {
-    case ALLOC_ITERATIVE:
-        allocators_[basic_type] = AllocatorPtr(new IterativeAllocator(basic_type));
-        break;
-    case ALLOC_HASHED:
-        allocators_[basic_type] = AllocatorPtr(new HashedAllocator(basic_type));
-        break;
-    case ALLOC_RANDOM:
-        allocators_[basic_type] = AllocatorPtr(new RandomAllocator(basic_type));
-        break;
-    default:
-        isc_throw(BadValue, "Invalid/unsupported allocation algorithm");
-    }
+    allocators_[basic_type] = AllocatorPtr(new IterativeAllocator(basic_type));
 
     // If this is IPv6 allocation engine, initialize also temporary addrs
     // and prefixes
     if (ipv6) {
-        switch (engine_type) {
-        case ALLOC_ITERATIVE:
-            allocators_[Lease::TYPE_TA] = AllocatorPtr(new IterativeAllocator(Lease::TYPE_TA));
-            allocators_[Lease::TYPE_PD] = AllocatorPtr(new IterativeAllocator(Lease::TYPE_PD));
-            break;
-        case ALLOC_HASHED:
-            allocators_[Lease::TYPE_TA] = AllocatorPtr(new HashedAllocator(Lease::TYPE_TA));
-            allocators_[Lease::TYPE_PD] = AllocatorPtr(new HashedAllocator(Lease::TYPE_PD));
-            break;
-        case ALLOC_RANDOM:
-            allocators_[Lease::TYPE_TA] = AllocatorPtr(new RandomAllocator(Lease::TYPE_TA));
-            allocators_[Lease::TYPE_PD] = AllocatorPtr(new RandomAllocator(Lease::TYPE_PD));
-            break;
-        default:
-            isc_throw(BadValue, "Invalid/unsupported allocation algorithm");
-        }
+        allocators_[Lease::TYPE_TA] = AllocatorPtr(new IterativeAllocator(Lease::TYPE_TA));
+        allocators_[Lease::TYPE_PD] = AllocatorPtr(new IterativeAllocator(Lease::TYPE_PD));
     }
 
     // Register hook points
@@ -361,7 +112,8 @@ AllocEngine::AllocEngine(AllocType engine_type, uint64_t attempts,
     hook_index_lease6_select_ = Hooks.hook_index_lease6_select_;
 }
 
-AllocEngine::AllocatorPtr AllocEngine::getAllocator(Lease::Type type) {
+AllocatorPtr
+AllocEngine::getAllocator(Lease::Type type) {
     std::map<Lease::Type, AllocatorPtr>::const_iterator alloc = allocators_.find(type);
 
     if (alloc == allocators_.end()) {
diff --git a/src/lib/dhcpsrv/alloc_engine.h b/src/lib/dhcpsrv/alloc_engine.h
index 07257145a1..c1ac2c53e0 100644
--- a/src/lib/dhcpsrv/alloc_engine.h
+++ b/src/lib/dhcpsrv/alloc_engine.h
@@ -16,6 +16,7 @@
 #include <dhcp/option6_ia.h>
 #include <dhcp/option6_iaaddr.h>
 #include <dhcp/option6_iaprefix.h>
+#include <dhcpsrv/allocator.h>
 #include <dhcpsrv/d2_client_cfg.h>
 #include <dhcpsrv/host.h>
 #include <dhcpsrv/subnet.h>
@@ -38,20 +39,6 @@
 namespace isc {
 namespace dhcp {
 
-/// An exception that is thrown when allocation module fails (e.g. due to
-/// lack of available addresses)
-class AllocFailed : public isc::Exception {
-public:
-
-    /// @brief Constructor
-    ///
-    /// @param file name of the file, where exception occurred
-    /// @param line line of the file, where exception occurred
-    /// @param what text description of the issue that caused exception
-    AllocFailed(const char* file, size_t line, const char* what)
-        : isc::Exception(file, line, what) {}
-};
-
 /// @brief DHCPv4 and DHCPv6 allocation engine
 ///
 /// This class represents a DHCP allocation engine. It is responsible
@@ -61,207 +48,6 @@ public:
 /// @todo: Does not handle out of leases well
 /// @todo: Does not handle out of allocation attempts well
 class AllocEngine : public boost::noncopyable {
-protected:
-
-    /// @brief Base class for all address/prefix allocation algorithms
-    ///
-    /// This is an abstract class that should not be used directly, but rather
-    /// specialized implementations should be used instead.
-    class Allocator {
-    public:
-
-        /// @brief Picks one address out of available pools in a given subnet
-        ///
-        /// This method returns one address from the available pools in the
-        /// specified subnet. It should not check if the address is used or
-        /// reserved - AllocEngine will check that and will call pickAddress
-        /// again if necessary. The number of times this method is called will
-        /// increase as the number of available leases will decrease.
-        ///
-        /// This method can also be used to pick a prefix. We should not rename
-        /// it to pickLease(), because at this early stage there is no concept
-        /// of a lease yet. Here it is a matter of selecting one address or
-        /// prefix from the defined pool, without going into details who it is
-        /// for or who uses it. I thought that pickAddress() is less confusing
-        /// than pickResource(), because nobody would immediately know what the
-        /// resource means in this context.
-        ///
-        /// Pools which are not allowed for client classes are skipped.
-        ///
-        /// @param subnet next address will be returned from pool of that subnet
-        /// @param client_classes list of classes client belongs to
-        /// @param duid Client's DUID
-        /// @param hint Client's hint
-        ///
-        /// @return the next address
-        virtual isc::asiolink::IOAddress
-        pickAddress(const SubnetPtr& subnet,
-                    const ClientClasses& client_classes,
-                    const DuidPtr& duid,
-                    const isc::asiolink::IOAddress& hint) {
-            if (isc::util::MultiThreadingMgr::instance().getMode()) {
-                std::lock_guard<std::mutex> lock(mutex_);
-                return pickAddressInternal(subnet, client_classes, duid, hint);
-            } else {
-                return pickAddressInternal(subnet, client_classes, duid, hint);
-            }
-        }
-
-        /// @brief Default constructor
-        ///
-        /// Specifies which type of leases this allocator will assign
-        /// @param pool_type specifies pool type (addresses, temp. addr or prefixes)
-        Allocator(Lease::Type pool_type) : pool_type_(pool_type) {
-        }
-
-        /// @brief Virtual destructor
-        virtual ~Allocator() {
-        }
-
-    private:
-        virtual isc::asiolink::IOAddress
-        pickAddressInternal(const SubnetPtr& subnet,
-                            const ClientClasses& client_classes,
-                            const DuidPtr& duid,
-                            const isc::asiolink::IOAddress& hint) = 0;
-
-    protected:
-
-        /// @brief Defines pool type allocation
-        Lease::Type pool_type_;
-
-    private:
-
-        /// @brief The mutex to protect the allocated lease
-        std::mutex mutex_;
-    };
-
-    /// defines a pointer to allocator
-    typedef boost::shared_ptr<Allocator> AllocatorPtr;
-
-    /// @brief Address/prefix allocator that iterates over all addresses
-    ///
-    /// This class implements an iterative algorithm that returns all addresses in
-    /// a pool iteratively, one after another. Once the last address is reached,
-    /// it starts allocating from the beginning of the first pool (i.e. it loops
-    /// over).
-    class IterativeAllocator : public Allocator {
-    public:
-
-        /// @brief Default constructor
-        ///
-        /// Does not do anything
-        /// @param type - specifies allocation type
-        IterativeAllocator(Lease::Type type);
-
-    private:
-
-        /// @brief Returns the next address from pools in a subnet
-        ///
-        /// @param subnet next address will be returned from pool of that subnet
-        /// @param client_classes list of classes client belongs to
-        /// @param duid Client's DUID (ignored)
-        /// @param hint Client's hint (ignored)
-        ///
-        /// @return the next address
-        virtual isc::asiolink::IOAddress
-        pickAddressInternal(const SubnetPtr& subnet,
-                            const ClientClasses& client_classes,
-                            const DuidPtr& duid,
-                            const isc::asiolink::IOAddress& hint);
-
-    protected:
-
-        /// @brief Returns the next prefix
-        ///
-        /// This method works for IPv6 addresses only. It increases the
-        /// specified prefix by a given prefix_len. For example, 2001:db8::
-        /// increased by prefix length /32 will become 2001:db9::. This method
-        /// is used to iterate over IPv6 prefix pools
-        ///
-        /// @param prefix prefix to be increased
-        /// @param prefix_len length of the prefix to be increased
-        ///
-        /// @return result prefix
-        static isc::asiolink::IOAddress
-        increasePrefix(const isc::asiolink::IOAddress& prefix,
-                       const uint8_t prefix_len);
-
-        /// @brief Returns the next address or prefix
-        ///
-        /// This method works for IPv4 addresses, IPv6 addresses and
-        /// IPv6 prefixes.
-        ///
-        /// @param address address or prefix to be increased
-        /// @param prefix true when the previous argument is a prefix
-        /// @param prefix_len length of the prefix
-        ///
-        /// @return result address or prefix
-        static isc::asiolink::IOAddress
-        increaseAddress(const isc::asiolink::IOAddress& address,
-                        bool prefix, const uint8_t prefix_len);
-    };
-
-    /// @brief Address/prefix allocator that gets an address based on a hash
-    ///
-    /// @todo: This is a skeleton class for now and is missing an implementation.
-    class HashedAllocator : public Allocator {
-    public:
-
-        /// @brief Default constructor (does nothing)
-        ///
-        /// @param type - specifies allocation type
-        HashedAllocator(Lease::Type type);
-
-    private:
-
-        /// @brief Returns an address based on hash calculated from client's DUID.
-        ///
-        /// @todo: Implement this method
-        ///
-        /// @param subnet an address will be picked from pool of that subnet
-        /// @param client_classes list of classes client belongs to
-        /// @param duid Client's DUID
-        /// @param hint a hint (last address that was picked)
-        ///
-        /// @return selected address
-        virtual isc::asiolink::IOAddress
-        pickAddressInternal(const SubnetPtr& subnet,
-                            const ClientClasses& client_classes,
-                            const DuidPtr& duid,
-                            const isc::asiolink::IOAddress& hint);
-    };
-
-    /// @brief Random allocator that picks address randomly
-    ///
-    /// @todo: This is a skeleton class for now and is missing an implementation.
-    class RandomAllocator : public Allocator {
-    public:
-
-        /// @brief Default constructor (does nothing)
-        ///
-        /// @param type - specifies allocation type
-        RandomAllocator(Lease::Type type);
-
-    private:
-
-        /// @brief Returns a random address from pool of specified subnet
-        ///
-        /// @todo: Implement this method
-        ///
-        /// @param subnet an address will be picked from pool of that subnet
-        /// @param client_classes list of classes client belongs to
-        /// @param duid Client's DUID (ignored)
-        /// @param hint the last address that was picked (ignored)
-        ///
-        /// @return a random address from the pool
-        virtual isc::asiolink::IOAddress
-        pickAddressInternal(const SubnetPtr& subnet,
-                            const ClientClasses& client_classes,
-                            const DuidPtr& duid,
-                            const isc::asiolink::IOAddress& hint);
-    };
-
 public:
 
     /// @brief Specifies allocation type
diff --git a/src/lib/dhcpsrv/allocator.h b/src/lib/dhcpsrv/allocator.h
new file mode 100644
index 0000000000..c073a849db
--- /dev/null
+++ b/src/lib/dhcpsrv/allocator.h
@@ -0,0 +1,115 @@
+// 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 ALLOCATOR_H
+#define ALLOCATOR_H
+
+#include <asiolink/io_address.h>
+#include <dhcp/classify.h>
+#include <dhcp/duid.h>
+#include <dhcpsrv/subnet.h>
+#include <exceptions/exceptions.h>
+#include <util/multi_threading_mgr.h>
+#include <boost/shared_ptr.hpp>
+#include <mutex>
+
+namespace isc {
+namespace dhcp {
+
+/// An exception that is thrown when allocation module fails (e.g. due to
+/// lack of available addresses)
+class AllocFailed : public Exception {
+public:
+
+    /// @brief Constructor
+    ///
+    /// @param file name of the file, where exception occurred
+    /// @param line line of the file, where exception occurred
+    /// @param what text description of the issue that caused exception
+    AllocFailed(const char* file, size_t line, const char* what)
+        : Exception(file, line, what) {}
+};
+
+/// @brief Base class for all address/prefix allocation algorithms.
+///
+/// This is an abstract class that should not be used directly, but rather
+/// specialized implementations should be used instead.
+class Allocator {
+public:
+
+    /// @brief Picks a address or a delegated prefix
+    ///
+    /// This method returns one address from the available pools in the
+    /// specified subnet. It should not check if the address is used or
+    /// reserved - AllocEngine will check that and will call pickAddress
+    /// again if necessary. The number of times this method is called will
+    /// increase as the number of available leases will decrease.
+    ///
+    /// This method can also be used to pick a prefix. We should not rename
+    /// it to pickLease(), because at this early stage there is no concept
+    /// of a lease yet. Here it is a matter of selecting one address or
+    /// prefix from the defined pool, without going into details who it is
+    /// for or who uses it. I thought that pickAddress() is less confusing
+    /// than pickResource(), because nobody would immediately know what the
+    /// resource means in this context.
+    ///
+    /// Pools which are not allowed for client classes are skipped.
+    ///
+    /// @param subnet next address will be returned from pool of that subnet
+    /// @param client_classes list of classes client belongs to
+    /// @param duid Client's DUID
+    /// @param hint Client's hint
+    ///
+    /// @return the next address.
+    virtual isc::asiolink::IOAddress
+    pickAddress(const SubnetPtr& subnet,
+                const ClientClasses& client_classes,
+                const DuidPtr& duid,
+                const asiolink::IOAddress& hint) {
+        if (util::MultiThreadingMgr::instance().getMode()) {
+            std::lock_guard<std::mutex> lock(mutex_);
+            return pickAddressInternal(subnet, client_classes, duid, hint);
+        } else {
+            return pickAddressInternal(subnet, client_classes, duid, hint);
+        }
+    }
+
+        /// @brief Default constructor
+        ///
+        /// Specifies which type of leases this allocator will assign
+        /// @param pool_type specifies pool type (addresses, temp. addr or prefixes)
+        Allocator(Lease::Type pool_type) : pool_type_(pool_type) {
+        }
+
+        /// @brief Virtual destructor
+        virtual ~Allocator() {
+        }
+
+    private:
+        virtual isc::asiolink::IOAddress
+        pickAddressInternal(const SubnetPtr& subnet,
+                            const ClientClasses& client_classes,
+                            const DuidPtr& duid,
+                            const isc::asiolink::IOAddress& hint) = 0;
+
+    protected:
+
+        /// @brief Defines pool type allocation
+        Lease::Type pool_type_;
+
+    private:
+
+        /// @brief The mutex to protect the allocated lease
+        std::mutex mutex_;
+};
+
+/// defines a pointer to allocator
+typedef boost::shared_ptr<Allocator> AllocatorPtr;
+
+} // end of namespace isc::dhcp
+} // end of namespace isc
+
+#endif // ALLOCATOR_H
\ No newline at end of file
diff --git a/src/lib/dhcpsrv/iterative_allocator.cc b/src/lib/dhcpsrv/iterative_allocator.cc
new file mode 100644
index 0000000000..52cf8cbc4d
--- /dev/null
+++ b/src/lib/dhcpsrv/iterative_allocator.cc
@@ -0,0 +1,216 @@
+// 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/iterative_allocator.h>
+#include <exceptions/exceptions.h>
+#include <cstring>
+
+using namespace isc::asiolink;
+using namespace std;
+
+namespace isc {
+namespace dhcp {
+
+IterativeAllocator::IterativeAllocator(Lease::Type lease_type)
+    : Allocator(lease_type) {
+}
+
+isc::asiolink::IOAddress
+IterativeAllocator::increasePrefix(const IOAddress& prefix,
+                                   const uint8_t prefix_len) {
+    if (!prefix.isV6()) {
+        isc_throw(BadValue, "Prefix operations are for IPv6 only (attempted to "
+                  "increase prefix " << prefix << ")");
+    }
+
+    // Get a buffer holding an address.
+    const std::vector<uint8_t>& vec = prefix.toBytes();
+
+    if (prefix_len < 1 || prefix_len > 128) {
+        isc_throw(BadValue, "Cannot increase prefix: invalid prefix length: "
+                  << prefix_len);
+    }
+
+    uint8_t n_bytes = (prefix_len - 1)/8;
+    uint8_t n_bits = 8 - (prefix_len - n_bytes*8);
+    uint8_t mask = 1 << n_bits;
+
+    // Explanation: n_bytes specifies number of full bytes that are in-prefix.
+    // They can also be used as an offset for the first byte that is not in
+    // prefix. n_bits specifies number of bits on the last byte that is
+    // (often partially) in prefix. For example for a /125 prefix, the values
+    // are 15 and 3, respectively. Mask is a bitmask that has the least
+    // significant bit from the prefix set.
+
+    uint8_t packed[V6ADDRESS_LEN];
+
+    // Copy the address. It must be V6, but we already checked that.
+    memcpy(packed, &vec[0], V6ADDRESS_LEN);
+
+    // Can we safely increase only the last byte in prefix without overflow?
+    if (packed[n_bytes] + uint16_t(mask) < 256u) {
+        packed[n_bytes] += mask;
+        return (IOAddress::fromBytes(AF_INET6, packed));
+    }
+
+    // Overflow (done on uint8_t, but the sum is greater than 255)
+    packed[n_bytes] += mask;
+
+    // Deal with the overflow. Start increasing the least significant byte
+    for (int i = n_bytes - 1; i >= 0; --i) {
+        ++packed[i];
+        // If we haven't overflowed (0xff->0x0) the next byte, then we are done
+        if (packed[i] != 0) {
+            break;
+        }
+    }
+
+    return (IOAddress::fromBytes(AF_INET6, packed));
+}
+
+IOAddress
+IterativeAllocator::increaseAddress(const IOAddress& address,
+                                    bool prefix,
+                                    const uint8_t prefix_len) {
+    if (!prefix) {
+        return (IOAddress::increase(address));
+    } else {
+        return (increasePrefix(address, prefix_len));
+    }
+}
+
+IOAddress
+IterativeAllocator::pickAddressInternal(const SubnetPtr& subnet,
+                                        const ClientClasses& client_classes,
+                                        const DuidPtr&,
+                                        const IOAddress&) {
+    // Is this prefix allocation?
+    bool prefix = pool_type_ == Lease::TYPE_PD;
+    uint8_t prefix_len = 0;
+
+    // Let's get the last allocated address. It is usually set correctly,
+    // but there are times when it won't be (like after removing a pool or
+    // perhaps restarting the server).
+    IOAddress last = subnet->getLastAllocated(pool_type_);
+    bool valid = true;
+    bool retrying = false;
+
+    const PoolCollection& pools = subnet->getPools(pool_type_);
+
+    if (pools.empty()) {
+        isc_throw(AllocFailed, "No pools defined in selected subnet");
+    }
+
+    // first we need to find a pool the last address belongs to.
+    PoolCollection::const_iterator it;
+    PoolCollection::const_iterator first = pools.end();
+    PoolPtr first_pool;
+    for (it = pools.begin(); it != pools.end(); ++it) {
+        if (!(*it)->clientSupported(client_classes)) {
+            continue;
+        }
+        if (first == pools.end()) {
+            first = it;
+        }
+        if ((*it)->inRange(last)) {
+            break;
+        }
+    }
+
+    // Caller checked this cannot happen
+    if (first == pools.end()) {
+        isc_throw(AllocFailed, "No allowed pools defined in selected subnet");
+    }
+
+    // last one was bogus for one of several reasons:
+    // - we just booted up and that's the first address we're allocating
+    // - a subnet was removed or other reconfiguration just completed
+    // - perhaps allocation algorithm was changed
+    // - last pool does not allow this client
+    if (it == pools.end()) {
+        it = first;
+    }
+
+    for (;;) {
+        // Trying next pool
+        if (retrying) {
+            for (; it != pools.end(); ++it) {
+                if ((*it)->clientSupported(client_classes)) {
+                    break;
+                }
+            }
+            if (it == pools.end()) {
+                // Really out of luck today. That was the last pool.
+                break;
+            }
+        }
+
+        last = (*it)->getLastAllocated();
+        valid = (*it)->isLastAllocatedValid();
+        if (!valid && (last == (*it)->getFirstAddress())) {
+            // Pool was (re)initialized
+            (*it)->setLastAllocated(last);
+            subnet->setLastAllocated(pool_type_, last);
+            return (last);
+        }
+        // still can be bogus
+        if (valid && !(*it)->inRange(last)) {
+            valid = false;
+            (*it)->resetLastAllocated();
+            (*it)->setLastAllocated((*it)->getFirstAddress());
+        }
+
+        if (valid) {
+            // Ok, we have a pool that the last address belonged to, let's use it.
+            if (prefix) {
+                Pool6Ptr pool6 = boost::dynamic_pointer_cast<Pool6>(*it);
+
+                if (!pool6) {
+                    // Something is gravely wrong here
+                    isc_throw(Unexpected, "Wrong type of pool: "
+                              << (*it)->toText()
+                              << " is not Pool6");
+                }
+                // Get the prefix length
+                prefix_len = pool6->getLength();
+            }
+
+            IOAddress next = increaseAddress(last, prefix, prefix_len);
+            if ((*it)->inRange(next)) {
+                // the next one is in the pool as well, so we haven't hit
+                // pool boundary yet
+                (*it)->setLastAllocated(next);
+                subnet->setLastAllocated(pool_type_, next);
+                return (next);
+            }
+
+            valid = false;
+            (*it)->resetLastAllocated();
+        }
+        // We hit pool boundary, let's try to jump to the next pool and try again
+        ++it;
+        retrying = true;
+    }
+
+    // Let's rewind to the beginning.
+    for (it = first; it != pools.end(); ++it) {
+        if ((*it)->clientSupported(client_classes)) {
+            (*it)->setLastAllocated((*it)->getFirstAddress());
+            (*it)->resetLastAllocated();
+        }
+    }
+
+    // ok to access first element directly. We checked that pools is non-empty
+    last = (*first)->getLastAllocated();
+    (*first)->setLastAllocated(last);
+    subnet->setLastAllocated(pool_type_, last);
+    return (last);
+}
+
+} // end of namespace isc::dhcp
+} // end of namespace isc
\ No newline at end of file
diff --git a/src/lib/dhcpsrv/iterative_allocator.h b/src/lib/dhcpsrv/iterative_allocator.h
new file mode 100644
index 0000000000..1450fe7edc
--- /dev/null
+++ b/src/lib/dhcpsrv/iterative_allocator.h
@@ -0,0 +1,79 @@
+// 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 ITERATIVE_ALLOCATOR_H
+#define ITERATIVE_ALLOCATOR_H
+
+#include <dhcpsrv/allocator.h>
+#include <dhcpsrv/lease.h>
+
+#include <cstdint>
+
+namespace isc {
+namespace dhcp {
+
+/// @brief Address/prefix allocator that iterates over all addresses
+///
+/// This class implements an iterative algorithm that returns all addresses in
+/// a pool iteratively, one after another. Once the last address is reached,
+/// it starts allocating from the beginning of the first pool (i.e. it loops
+/// over).
+class IterativeAllocator : public Allocator {
+public:
+    /// @brief Default constructor
+    ///
+    /// Does not do anything
+    /// @param type - specifies allocation type
+    IterativeAllocator(Lease::Type type);
+
+private:
+    /// @brief Returns the next address from pools in a subnet
+    ///
+    /// @param subnet next address will be returned from pool of that subnet
+    /// @param client_classes list of classes client belongs to
+    /// @param duid Client's DUID (ignored)
+    /// @param hint Client's hint (ignored)
+    ///
+    /// @return the next address
+    virtual asiolink::IOAddress pickAddressInternal(const SubnetPtr& subnet,
+                                                    const ClientClasses& client_classes,
+                                                    const DuidPtr& duid,
+                                                    const asiolink::IOAddress& hint);
+
+protected:
+    /// @brief Returns the next prefix
+    ///
+    /// This method works for IPv6 addresses only. It increases the
+    /// specified prefix by a given prefix_len. For example, 2001:db8::
+    /// increased by prefix length /32 will become 2001:db9::. This method
+    /// is used to iterate over IPv6 prefix pools
+    ///
+    /// @param prefix prefix to be increased
+    /// @param prefix_len length of the prefix to be increased
+    ///
+    /// @return result prefix
+    static asiolink::IOAddress increasePrefix(const asiolink::IOAddress& prefix,
+                                              const uint8_t prefix_len);
+
+    /// @brief Returns the next address or prefix
+    ///
+    /// This method works for IPv4 addresses, IPv6 addresses and
+    /// IPv6 prefixes.
+    ///
+    /// @param address address or prefix to be increased
+    /// @param prefix true when the previous argument is a prefix
+    /// @param prefix_len length of the prefix
+    ///
+    /// @return result address or prefix
+    static asiolink::IOAddress increaseAddress(const asiolink::IOAddress& address,
+                                               bool prefix,
+                                               const uint8_t prefix_len);
+};
+
+}  // namespace dhcp
+}  // end of namespace isc
+
+#endif  // ITERATIVE_ALLOCATOR_H
\ No newline at end of file
diff --git a/src/lib/dhcpsrv/tests/Makefile.am b/src/lib/dhcpsrv/tests/Makefile.am
index c9523eb9b8..17d8ba2a49 100644
--- a/src/lib/dhcpsrv/tests/Makefile.am
+++ b/src/lib/dhcpsrv/tests/Makefile.am
@@ -99,6 +99,7 @@ libdhcpsrv_unittests_SOURCES += host_reservations_list_parser_unittest.cc
 libdhcpsrv_unittests_SOURCES += ifaces_config_parser_unittest.cc
 libdhcpsrv_unittests_SOURCES += ip_range_unittest.cc
 libdhcpsrv_unittests_SOURCES += ip_range_permutation_unittest.cc
+libdhcpsrv_unittests_SOURCES += iterative_allocator_unittest.cc
 libdhcpsrv_unittests_SOURCES += lease_file_loader_unittest.cc
 libdhcpsrv_unittests_SOURCES += lease_unittest.cc
 libdhcpsrv_unittests_SOURCES += lease_mgr_factory_unittest.cc
diff --git a/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc b/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc
index 83235a9f9f..31e38bf66e 100644
--- a/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc
+++ b/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc
@@ -44,12 +44,6 @@ namespace test {
 TEST_F(AllocEngine4Test, constructor) {
     boost::scoped_ptr<AllocEngine> x;
 
-    // Hashed and random allocators are not supported yet
-    ASSERT_THROW(x.reset(new AllocEngine(AllocEngine::ALLOC_HASHED, 5, false)),
-                 NotImplemented);
-    ASSERT_THROW(x.reset(new AllocEngine(AllocEngine::ALLOC_RANDOM, 5, false)),
-                 NotImplemented);
-
     // Create V4 (ipv6=false) Allocation Engine that will try at most
     // 100 attempts to pick up a lease
     ASSERT_NO_THROW(x.reset(new AllocEngine(AllocEngine::ALLOC_ITERATIVE, 100,
@@ -851,98 +845,6 @@ TEST_F(AllocEngine4Test, bootpRenew4) {
     EXPECT_EQ(infinity_lft, lease2->valid_lft_);
 }
 
-// This test verifies that the allocator picks addresses that belong to the
-// pool
-TEST_F(AllocEngine4Test, IterativeAllocator) {
-    boost::scoped_ptr<NakedAllocEngine::Allocator>
-        alloc(new NakedAllocEngine::IterativeAllocator(Lease::TYPE_V4));
-
-    for (int i = 0; i < 1000; ++i) {
-        IOAddress candidate = alloc->pickAddress(subnet_, cc_, clientid_,
-                                                 IOAddress("0.0.0.0"));
-        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
-    }
-}
-
-// This test verifies that the allocator picks addresses that belong to the
-// pool using classification
-TEST_F(AllocEngine4Test, IterativeAllocator_class) {
-    boost::scoped_ptr<NakedAllocEngine::Allocator>
-        alloc(new NakedAllocEngine::IterativeAllocator(Lease::TYPE_V4));
-
-    // Restrict pool_ to the foo class. Add a second pool with bar class.
-    pool_->allowClientClass("foo");
-    Pool4Ptr pool(new Pool4(IOAddress("192.0.2.200"),
-                            IOAddress("192.0.2.209")));
-    pool->allowClientClass("bar");
-    subnet_->addPool(pool);
-
-    // Clients are in bar
-    cc_.insert("bar");
-
-    for (int i = 0; i < 1000; ++i) {
-        IOAddress candidate = alloc->pickAddress(subnet_, cc_, clientid_,
-                                                 IOAddress("0.0.0.0"));
-        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
-        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate, cc_));
-    }
-}
-
-// This test verifies that the iterative allocator really walks over all addresses
-// in all pools in specified subnet. It also must not pick the same address twice
-// unless it runs out of pool space and must start over.
-TEST_F(AllocEngine4Test, IterativeAllocator_manyPools4) {
-    NakedAllocEngine::IterativeAllocator alloc(Lease::TYPE_V4);
-
-    // Let's start from 2, as there is 2001:db8:1::10 - 2001:db8:1::20 pool already.
-    for (int i = 2; i < 10; ++i) {
-        stringstream min, max;
-
-        min << "192.0.2." << i * 10 + 1;
-        max << "192.0.2." << i * 10 + 9;
-
-        Pool4Ptr pool(new Pool4(IOAddress(min.str()),
-                                IOAddress(max.str())));
-        // cout << "Adding pool: " << min.str() << "-" << max.str() << endl;
-        subnet_->addPool(pool);
-    }
-
-    int total = 10 + 8 * 9; // first pool (.100 - .109) has 10 addresses in it,
-                            // there are 8 extra pools with 9 addresses in each.
-
-    // Let's keep picked addresses here and check their uniqueness.
-    std::set<IOAddress> generated_addrs;
-    int cnt = 0;
-    while (++cnt) {
-        IOAddress candidate = alloc.pickAddress(subnet_, cc_, clientid_, IOAddress("0.0.0.0"));
-        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
-
-        // One way to easily verify that the iterative allocator really works is
-        // to uncomment the following line and observe its output that it
-        // covers all defined subnets.
-        // cout << candidate.toText() << endl;
-
-        if (generated_addrs.find(candidate) == generated_addrs.end()) {
-            // We haven't had this
-            generated_addrs.insert(candidate);
-        } else {
-            // We have seen this address before. That should mean that we
-            // iterated over all addresses.
-            if (generated_addrs.size() == total) {
-                // We have exactly the number of address in all pools
-                break;
-            }
-            ADD_FAILURE() << "Too many or not enough unique addresses generated.";
-            break;
-        }
-
-        if ( cnt>total ) {
-            ADD_FAILURE() << "Too many unique addresses generated.";
-            break;
-        }
-    }
-}
-
 // This test checks if really small pools are working
 TEST_F(AllocEngine4Test, smallPool4) {
     boost::scoped_ptr<AllocEngine> engine;
diff --git a/src/lib/dhcpsrv/tests/alloc_engine6_unittest.cc b/src/lib/dhcpsrv/tests/alloc_engine6_unittest.cc
index e07193bc15..f381c4fc12 100644
--- a/src/lib/dhcpsrv/tests/alloc_engine6_unittest.cc
+++ b/src/lib/dhcpsrv/tests/alloc_engine6_unittest.cc
@@ -10,6 +10,7 @@
 #include <dhcpsrv/host_mgr.h>
 #include <dhcpsrv/parsers/client_class_def_parser.h>
 #include <dhcpsrv/tests/alloc_engine_utils.h>
+#include <dhcpsrv/allocator.h>
 #include <dhcpsrv/testutils/test_utils.h>
 #include <eval/eval_context.h>
 #include <stats/stats_mgr.h>
@@ -58,10 +59,6 @@ TEST(ClientContext6Test, addAllocatedResource) {
 TEST_F(AllocEngine6Test, constructor) {
     boost::scoped_ptr<AllocEngine> x;
 
-    // Hashed and random allocators are not supported yet
-    ASSERT_THROW(x.reset(new AllocEngine(AllocEngine::ALLOC_HASHED, 5)), NotImplemented);
-    ASSERT_THROW(x.reset(new AllocEngine(AllocEngine::ALLOC_RANDOM, 5)), NotImplemented);
-
     ASSERT_NO_THROW(x.reset(new AllocEngine(AllocEngine::ALLOC_ITERATIVE, 100, true)));
 
     // Check that allocator for normal addresses is created
@@ -301,8 +298,7 @@ TEST_F(AllocEngine6Test, allocateAddress6Nulls) {
 // This test verifies that the allocator picks addresses that belong to the
 // pool
 TEST_F(AllocEngine6Test, IterativeAllocator) {
-    boost::scoped_ptr<NakedAllocEngine::Allocator>
-        alloc(new NakedAllocEngine::IterativeAllocator(Lease::TYPE_NA));
+    boost::scoped_ptr<Allocator> alloc(new NakedIterativeAllocator(Lease::TYPE_NA));
 
     for (int i = 0; i < 1000; ++i) {
         IOAddress candidate = alloc->pickAddress(subnet_, cc_,
@@ -314,8 +310,7 @@ TEST_F(AllocEngine6Test, IterativeAllocator) {
 // This test verifies that the allocator picks addresses that belong to the
 // pool using classification
 TEST_F(AllocEngine6Test, IterativeAllocator_class) {
-    boost::scoped_ptr<NakedAllocEngine::Allocator>
-        alloc(new NakedAllocEngine::IterativeAllocator(Lease::TYPE_NA));
+    boost::scoped_ptr<Allocator> alloc(new NakedIterativeAllocator(Lease::TYPE_NA));
 
     // Restrict pool_ to the foo class. Add a second pool with bar class.
     pool_->allowClientClass("foo");
@@ -336,7 +331,7 @@ TEST_F(AllocEngine6Test, IterativeAllocator_class) {
 }
 
 TEST_F(AllocEngine6Test, IterativeAllocatorAddrStep) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_NA);
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
 
     subnet_->delPools(Lease::TYPE_NA); // Get rid of default pool
 
@@ -381,7 +376,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorAddrStep) {
 }
 
 TEST_F(AllocEngine6Test, IterativeAllocatorAddrStepInClass) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_NA);
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
 
     subnet_->delPools(Lease::TYPE_NA); // Get rid of default pool
 
@@ -432,7 +427,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorAddrStepInClass) {
 }
 
 TEST_F(AllocEngine6Test, IterativeAllocatorAddrStepOutClass) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_NA);
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
 
     subnet_->delPools(Lease::TYPE_NA); // Get rid of default pool
 
@@ -477,7 +472,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorAddrStepOutClass) {
 }
 
 TEST_F(AllocEngine6Test, IterativeAllocatorPrefixStep) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_PD);
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
 
     subnet_.reset(new Subnet6(IOAddress("2001:db8::"), 32, 1, 2, 3, 4));
 
@@ -554,7 +549,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorPrefixStep) {
 }
 
 TEST_F(AllocEngine6Test, IterativeAllocatorPrefixStepInClass) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_PD);
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
 
     subnet_.reset(new Subnet6(IOAddress("2001:db8::"), 32, 1, 2, 3, 4));
 
@@ -637,7 +632,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorPrefixStepInClass) {
 }
 
 TEST_F(AllocEngine6Test, IterativeAllocatorPrefixStepOutClass) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_PD);
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
 
     subnet_.reset(new Subnet6(IOAddress("2001:db8::"), 32, 1, 2, 3, 4));
 
@@ -715,7 +710,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorPrefixStepOutClass) {
 
 // This test verifies that the iterative allocator can step over addresses
 TEST_F(AllocEngine6Test, IterativeAllocatorAddressIncrease) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_NA);
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
 
     // Let's pick the first address
     IOAddress addr1 = alloc.pickAddress(subnet_, cc_, duid_, IOAddress("2001:db8:1::10"));
@@ -735,7 +730,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorAddressIncrease) {
 
 // This test verifies that the allocator can step over prefixes
 TEST_F(AllocEngine6Test, IterativeAllocatorPrefixIncrease) {
-    NakedAllocEngine::NakedIterativeAllocator alloc(Lease::TYPE_PD);
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
 
     // For /128 prefix, increasePrefix should work the same as addressIncrease
     checkPrefixIncrease(alloc, "2001:db8::9", 128, "2001:db8::a");
@@ -787,7 +782,7 @@ TEST_F(AllocEngine6Test, IterativeAllocatorPrefixIncrease) {
 // in all pools in specified subnet. It also must not pick the same address twice
 // unless it runs out of pool space and must start over.
 TEST_F(AllocEngine6Test, IterativeAllocator_manyPools6) {
-    NakedAllocEngine::IterativeAllocator alloc(Lease::TYPE_NA);
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
 
     // let's start from 2, as there is 2001:db8:1::10 - 2001:db8:1::20 pool already.
     for (int i = 2; i < 10; ++i) {
diff --git a/src/lib/dhcpsrv/tests/alloc_engine_utils.h b/src/lib/dhcpsrv/tests/alloc_engine_utils.h
index be8152419e..b94e1cf183 100644
--- a/src/lib/dhcpsrv/tests/alloc_engine_utils.h
+++ b/src/lib/dhcpsrv/tests/alloc_engine_utils.h
@@ -1,4 +1,4 @@
-// Copyright (C) 2015-2021 Internet Systems Consortium, Inc. ("ISC")
+// Copyright (C) 2015-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
@@ -7,11 +7,13 @@
 #ifndef LIBDHCPSRV_ALLOC_ENGINE_UTILS_H
 #define LIBDHCPSRV_ALLOC_ENGINE_UTILS_H
 
-#include <dhcpsrv/lease_mgr.h>
-#include <dhcpsrv/lease_mgr_factory.h>
+#include <asiolink/io_address.h>
 #include <dhcpsrv/alloc_engine.h>
 #include <dhcpsrv/cfgmgr.h>
-#include <asiolink/io_address.h>
+#include <dhcpsrv/iterative_allocator.h>
+#include <dhcpsrv/lease_mgr.h>
+#include <dhcpsrv/lease_mgr_factory.h>
+
 #include <gtest/gtest.h>
 #include <vector>
 
@@ -31,7 +33,6 @@ namespace test {
 /// alloc_engine6_unittest.cc - all unit-tests dedicated to IPv6
 /// alloc_engine_hooks_unittest.cc - all unit-tests dedicated to hooks
 
-
 /// @brief Test that statistic manager holds a given value.
 ///
 /// This function may be used in many allocation tests and there's no
@@ -43,7 +44,8 @@ namespace test {
 ///
 /// @return true if the statistic manager holds a particular value,
 /// false otherwise.
-bool testStatistics(const std::string& stat_name, const int64_t exp_value,
+bool testStatistics(const std::string& stat_name,
+                    const int64_t exp_value,
                     const SubnetID subnet_id = SUBNET_ID_UNUSED);
 
 /// @brief Get a value held by statistic manager.
@@ -54,42 +56,35 @@ bool testStatistics(const std::string& stat_name, const int64_t exp_value,
 /// @param stat_name Statistic name.
 /// @param subnet_id subnet_id of the desired subnet, if not zero.
 /// @return the value held by the statistic manager or zero.
-int64_t getStatistics(const std::string& stat_name,
-                      const SubnetID subnet_id = SUBNET_ID_UNUSED);
+int64_t getStatistics(const std::string& stat_name, const SubnetID subnet_id = SUBNET_ID_UNUSED);
+
+/// @brief IterativeAllocator with internal methods exposed
+class NakedIterativeAllocator : public IterativeAllocator {
+public:
+    /// @brief constructor
+    /// @param type pool types that will be iterated through
+    NakedIterativeAllocator(Lease::Type type) : IterativeAllocator(type) {
+    }
+
+    using IterativeAllocator::increaseAddress;
+    using IterativeAllocator::increasePrefix;
+};
 
 /// @brief Allocation engine with some internal methods exposed
 class NakedAllocEngine : public AllocEngine {
 public:
-
     /// @brief the sole constructor
     /// @param engine_type specifies engine type (e.g. iterative)
     /// @param attempts number of lease selection attempts before giving up
     /// @param ipv6 specifies if the engine is IPv6 or IPv4
-    NakedAllocEngine(AllocEngine::AllocType engine_type,
-                     unsigned int attempts, bool ipv6 = true)
-        :AllocEngine(engine_type, attempts, ipv6) {
+    NakedAllocEngine(AllocEngine::AllocType engine_type, unsigned int attempts, bool ipv6 = true)
+        : AllocEngine(engine_type, attempts, ipv6) {
     }
 
     // Expose internal classes for testing purposes
-    using AllocEngine::Allocator;
-    using AllocEngine::IterativeAllocator;
     using AllocEngine::getAllocator;
     using AllocEngine::updateLease4ExtendedInfo;
 
-    /// @brief IterativeAllocator with internal methods exposed
-    class NakedIterativeAllocator: public AllocEngine::IterativeAllocator {
-    public:
-
-        /// @brief constructor
-        /// @param type pool types that will be iterated through
-        NakedIterativeAllocator(Lease::Type type)
-            :IterativeAllocator(type) {
-        }
-
-        using AllocEngine::IterativeAllocator::increaseAddress;
-        using AllocEngine::IterativeAllocator::increasePrefix;
-    };
-
     /// @brief Wrapper method for invoking AllocEngine4::updateLease4ExtendedInfo().
     /// @param lease lease to update
     /// @param ctx current packet processing context
@@ -141,11 +136,10 @@ public:
                     const asiolink::IOAddress& pool_start,
                     const asiolink::IOAddress& pool_end,
                     const asiolink::IOAddress& pd_pool_prefix =
-                    asiolink::IOAddress::IPV6_ZERO_ADDRESS(),
+                     asiolink::IOAddress::IPV6_ZERO_ADDRESS(),
                     const uint8_t pd_pool_length = 0,
                     const uint8_t pd_delegated_length = 0);
 
-
     /// @brief Initializes FQDN data for a test.
     ///
     /// The initialized values are used by the test fixture class members to
@@ -198,8 +192,10 @@ public:
     /// @param exp_pd_len expected prefix length
     /// @param expected_in_subnet whether the lease is expected to be in subnet
     /// @param expected_in_pool whether the lease is expected to be in dynamic
-    void checkLease6(const DuidPtr& duid, const Lease6Ptr& lease,
-                     Lease::Type exp_type, uint8_t exp_pd_len = 128,
+    void checkLease6(const DuidPtr& duid,
+                     const Lease6Ptr& lease,
+                     Lease::Type exp_type,
+                     uint8_t exp_pd_len = 128,
                      bool expected_in_subnet = true,
                      bool expected_in_pool = true) {
 
@@ -263,9 +259,9 @@ public:
     /// @param alloc IterativeAllocator that is tested
     /// @param input address to be increased
     /// @param exp_output expected address after increase
-    void
-    checkAddrIncrease(NakedAllocEngine::NakedIterativeAllocator& alloc,
-                      std::string input, std::string exp_output) {
+    void checkAddrIncrease(NakedIterativeAllocator& alloc,
+                           std::string input,
+                           std::string exp_output) {
         EXPECT_EQ(exp_output, alloc.increaseAddress(asiolink::IOAddress(input),
                                                     false, 0).toText());
     }
@@ -278,12 +274,13 @@ public:
     /// @param input IPv6 prefix (as a string)
     /// @param prefix_len prefix len
     /// @param exp_output expected output (string)
-    void
-    checkPrefixIncrease(NakedAllocEngine::NakedIterativeAllocator& alloc,
-                        std::string input, uint8_t prefix_len,
-                        std::string exp_output) {
-        EXPECT_EQ(exp_output, alloc.increasePrefix(asiolink::IOAddress(input),
-                                                   prefix_len).toText());
+    void checkPrefixIncrease(NakedIterativeAllocator& alloc,
+                             std::string input,
+                             uint8_t prefix_len,
+                             std::string exp_output) {
+        EXPECT_EQ(exp_output,
+                  alloc.increasePrefix(asiolink::IOAddress(input),
+                                       prefix_len).toText());
     }
 
     /// @brief Checks if the simple allocation can succeed
@@ -297,7 +294,8 @@ public:
     /// @return allocated lease (or NULL)
     Lease6Ptr simpleAlloc6Test(const Pool6Ptr& pool,
                                const asiolink::IOAddress& hint,
-                               bool fake, bool in_pool = true);
+                               bool fake,
+                               bool in_pool = true);
 
     /// @brief Checks if the simple allocation can succeed with lifetimes.
     ///
@@ -312,8 +310,10 @@ public:
     /// @return allocated lease (or NULL)
     Lease6Ptr simpleAlloc6Test(const Pool6Ptr& pool,
                                const asiolink::IOAddress& hint,
-                               uint32_t preferred, uint32_t valid,
-                               uint32_t exp_preferred, uint32_t exp_valid);
+                               uint32_t preferred,
+                               uint32_t valid,
+                               uint32_t exp_preferred,
+                               uint32_t exp_valid);
 
     /// @brief Checks if the simple allocation can succeed for custom DUID.
     ///
@@ -325,10 +325,11 @@ public:
     /// @param fake true - this is fake allocation (SOLICIT)
     /// @param in_pool specifies whether the lease is expected to be in pool
     /// @return allocated lease (or NULL)
-    Lease6Ptr simpleAlloc6Test(const Pool6Ptr& pool, const DuidPtr& duid,
+    Lease6Ptr simpleAlloc6Test(const Pool6Ptr& pool,
+                               const DuidPtr& duid,
                                const asiolink::IOAddress& hint,
-                               bool fake, bool in_pool = true);
-
+                               bool fake,
+                               bool in_pool = true);
 
     /// @brief Checks if the allocation can succeed.
     ///
@@ -341,8 +342,10 @@ public:
     /// @param fake true - this is fake allocation (SOLICIT)
     /// @param in_pool specifies whether the lease is expected to be in pool
     /// @return allocated lease(s) (may be empty)
-    Lease6Collection allocateTest(AllocEngine& engine, const Pool6Ptr& pool,
-                                  const asiolink::IOAddress& hint, bool fake,
+    Lease6Collection allocateTest(AllocEngine& engine,
+                                  const Pool6Ptr& pool,
+                                  const asiolink::IOAddress& hint,
+                                  bool fake,
                                   bool in_pool = true);
 
     /// @brief Checks if the allocation can be renewed.
@@ -355,7 +358,8 @@ public:
     /// @param hints address to be used as a hint
     /// @param in_pool specifies whether the lease is expected to be in pool
     /// @return allocated lease(s) (may be empty)
-    Lease6Collection renewTest(AllocEngine& engine, const Pool6Ptr& pool,
+    Lease6Collection renewTest(AllocEngine& engine,
+                               const Pool6Ptr& pool,
                                AllocEngine::HintContainer& hints,
                                bool in_pool = true);
 
@@ -369,7 +373,8 @@ public:
     ///        allocation by some other user)
     /// @param requested address requested by the client
     /// @param expected_pd_len expected PD len (128 for addresses)
-    void allocWithUsedHintTest(Lease::Type type, asiolink::IOAddress used_addr,
+    void allocWithUsedHintTest(Lease::Type type,
+                               asiolink::IOAddress used_addr,
                                asiolink::IOAddress requested,
                                uint8_t expected_pd_len);
 
@@ -426,12 +431,12 @@ public:
     /// @param addr specifies reserved address or prefix
     /// @param prefix_len prefix length (should be 128 for addresses)
     /// @return created Host object.
-    HostPtr
-    createHost6(bool add_to_host_mgr, IPv6Resrv::Type type,
-                const asiolink::IOAddress& addr, uint8_t prefix_len) {
-        HostPtr host(new Host(&duid_->getDuid()[0], duid_->getDuid().size(),
-                              Host::IDENT_DUID, SUBNET_ID_UNUSED, subnet_->getID(),
-                              asiolink::IOAddress("0.0.0.0")));
+    HostPtr createHost6(bool add_to_host_mgr,
+                        IPv6Resrv::Type type,
+                        const asiolink::IOAddress& addr,
+                        uint8_t prefix_len) {
+        HostPtr host(new Host(&duid_->getDuid()[0], duid_->getDuid().size(), Host::IDENT_DUID,
+                              SUBNET_ID_UNUSED, subnet_->getID(), asiolink::IOAddress("0.0.0.0")));
         IPv6Resrv resv(type, addr, prefix_len);
         host->addReservation(resv);
 
@@ -450,8 +455,7 @@ public:
     /// such as subnets.
     ///
     /// @param host host reservation to add
-    void
-    addHost(HostPtr& host) {
+    void addHost(HostPtr& host) {
         SrvConfigPtr cfg = boost::const_pointer_cast<SrvConfig>(CfgMgr::instance().getCurrentCfg());
         cfg->getCfgHosts()->add(host);
     }
@@ -464,10 +468,11 @@ public:
     /// @param addr specifies reserved address or prefix
     /// @param prefix_len prefix length (should be 128 for addresses)
     /// @return created Host object.
-    HostPtr
-    createHost6HWAddr(bool add_to_host_mgr, IPv6Resrv::Type type,
-                      HWAddrPtr& hwaddr, const asiolink::IOAddress& addr,
-                      uint8_t prefix_len);
+    HostPtr createHost6HWAddr(bool add_to_host_mgr,
+                              IPv6Resrv::Type type,
+                              HWAddrPtr& hwaddr,
+                              const asiolink::IOAddress& addr,
+                              uint8_t prefix_len);
 
     /// @brief Utility function that decrements cltt of a persisted lease
     ///
@@ -478,13 +483,11 @@ public:
     ///
     /// @param[in][out] lease pointer reference to the lease to modify.  Upon
     /// return it will point to the newly updated lease.
-    void
-    rollbackPersistedCltt(Lease6Ptr& lease) {
+    void rollbackPersistedCltt(Lease6Ptr& lease) {
         ASSERT_TRUE(lease) << "rollbackPersistedCltt lease is empty";
 
         // Fetch it, so we can update it.
-        Lease6Ptr from_mgr = LeaseMgrFactory::instance().getLease6(lease->type_,
-                                                                   lease->addr_);
+        Lease6Ptr from_mgr = LeaseMgrFactory::instance().getLease6(lease->type_, lease->addr_);
         ASSERT_TRUE(from_mgr) << "rollbackPersistedCltt: lease not found?";
 
         // Decrement cltt then update it in the manager.
@@ -552,11 +555,9 @@ public:
         }
         if (lease->client_id_ && !clientid_) {
             ADD_FAILURE() << "Lease4 has a client-id, while it should have none.";
-        } else
-        if (!lease->client_id_ && clientid_) {
+        } else if (!lease->client_id_ && clientid_) {
             ADD_FAILURE() << "Lease4 has no client-id, but it was expected to have one.";
-        } else
-        if (lease->client_id_ && clientid_) {
+        } else if (lease->client_id_ && clientid_) {
             EXPECT_TRUE(*lease->client_id_ == *clientid_);
         }
         EXPECT_TRUE(*lease->hwaddr_ == *hwaddr_);
@@ -610,16 +611,16 @@ public:
         factory_.destroy();
     }
 
-    ClientIdPtr clientid_;      ///< Client-identifier (value used in tests)
-    ClientIdPtr clientid2_;     ///< Alternative client-identifier.
-    HWAddrPtr hwaddr_;          ///< Hardware address (value used in tests)
-    HWAddrPtr hwaddr2_;         ///< Alternative hardware address.
-    Subnet4Ptr subnet_;         ///< Subnet4 (used in tests)
-    Pool4Ptr pool_;             ///< Pool belonging to subnet_
-    LeaseMgrFactory factory_;   ///< Pointer to LeaseMgr factory
+    ClientIdPtr clientid_;            ///< Client-identifier (value used in tests)
+    ClientIdPtr clientid2_;           ///< Alternative client-identifier.
+    HWAddrPtr hwaddr_;                ///< Hardware address (value used in tests)
+    HWAddrPtr hwaddr2_;               ///< Alternative hardware address.
+    Subnet4Ptr subnet_;               ///< Subnet4 (used in tests)
+    Pool4Ptr pool_;                   ///< Pool belonging to subnet_
+    LeaseMgrFactory factory_;         ///< Pointer to LeaseMgr factory
     AllocEngine::ClientContext4 ctx_; ///< Context information passed to various
-    ClientClasses cc_;          ///< Client classes
-                                     ///< allocation engine functions.
+    ClientClasses cc_;                ///< Client classes
+                                      ///< allocation engine functions.
 };
 
 } // namespace test
diff --git a/src/lib/dhcpsrv/tests/iterative_allocator_unittest.cc b/src/lib/dhcpsrv/tests/iterative_allocator_unittest.cc
new file mode 100644
index 0000000000..1dda363fcc
--- /dev/null
+++ b/src/lib/dhcpsrv/tests/iterative_allocator_unittest.cc
@@ -0,0 +1,666 @@
+// 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/iterative_allocator.h>
+#include <dhcpsrv/tests/alloc_engine_utils.h>
+#include <gtest/gtest.h>
+#include <sstream>
+
+using namespace isc::asiolink;
+using namespace isc::dhcp;
+using namespace std;
+
+namespace isc {
+namespace dhcp {
+namespace test {
+
+using IterativeAllocatorTest4 = AllocEngine4Test;
+
+// This test verifies that the allocator picks addresses that belong to the
+// pool
+TEST_F(IterativeAllocatorTest4, basic) {
+    boost::scoped_ptr<Allocator> alloc(new IterativeAllocator(Lease::TYPE_V4));
+
+    for (int i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc->pickAddress(subnet_, cc_, clientid_,
+                                                 IOAddress("0.0.0.0"));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
+    }
+}
+
+// This test verifies that the allocator picks addresses that belong to the
+// pool using classification
+TEST_F(IterativeAllocatorTest4, clientClass) {
+    boost::scoped_ptr<Allocator> alloc(new IterativeAllocator(Lease::TYPE_V4));
+
+    // Restrict pool_ to the foo class. Add a second pool with bar class.
+    pool_->allowClientClass("foo");
+    Pool4Ptr pool(new Pool4(IOAddress("192.0.2.200"),
+                            IOAddress("192.0.2.209")));
+    pool->allowClientClass("bar");
+    subnet_->addPool(pool);
+
+    // Clients are in bar
+    cc_.insert("bar");
+
+    for (int i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc->pickAddress(subnet_, cc_, clientid_,
+                                                 IOAddress("0.0.0.0"));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate, cc_));
+    }
+}
+
+// This test verifies that the iterative allocator really walks over all addresses
+// in all pools in specified subnet. It also must not pick the same address twice
+// unless it runs out of pool space and must start over.
+TEST_F(IterativeAllocatorTest4, manyPools) {
+    IterativeAllocator alloc(Lease::TYPE_V4);
+
+    // Let's start from 2, as there is 2001:db8:1::10 - 2001:db8:1::20 pool already.
+    for (int i = 2; i < 10; ++i) {
+        stringstream min, max;
+
+        min << "192.0.2." << i * 10 + 1;
+        max << "192.0.2." << i * 10 + 9;
+
+        Pool4Ptr pool(new Pool4(IOAddress(min.str()),
+                                IOAddress(max.str())));
+        // cout << "Adding pool: " << min.str() << "-" << max.str() << endl;
+        subnet_->addPool(pool);
+    }
+
+    int total = 10 + 8 * 9; // first pool (.100 - .109) has 10 addresses in it,
+                            // there are 8 extra pools with 9 addresses in each.
+
+    // Let's keep picked addresses here and check their uniqueness.
+    std::set<IOAddress> generated_addrs;
+    int cnt = 0;
+    while (++cnt) {
+        IOAddress candidate = alloc.pickAddress(subnet_, cc_, clientid_, IOAddress("0.0.0.0"));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
+
+        // One way to easily verify that the iterative allocator really works is
+        // to uncomment the following line and observe its output that it
+        // covers all defined subnets.
+        // cout << candidate.toText() << endl;
+
+        if (generated_addrs.find(candidate) == generated_addrs.end()) {
+            // We haven't had this
+            generated_addrs.insert(candidate);
+        } else {
+            // We have seen this address before. That should mean that we
+            // iterated over all addresses.
+            if (generated_addrs.size() == total) {
+                // We have exactly the number of address in all pools
+                break;
+            }
+            ADD_FAILURE() << "Too many or not enough unique addresses generated.";
+            break;
+        }
+
+        if ( cnt>total ) {
+            ADD_FAILURE() << "Too many unique addresses generated.";
+            break;
+        }
+    }
+}
+
+using IterativeAllocatorTest6 = AllocEngine6Test;
+
+// This test verifies that the allocator picks addresses that belong to the
+// pool
+TEST_F(IterativeAllocatorTest6, basic) {
+    boost::scoped_ptr<Allocator> alloc(new NakedIterativeAllocator(Lease::TYPE_NA));
+
+    for (int i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc->pickAddress(subnet_, cc_,
+                                                 duid_, IOAddress("::"));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate));
+    }
+}
+
+// This test verifies that the allocator picks addresses that belong to the
+// pool using classification
+TEST_F(IterativeAllocatorTest6, clientClass) {
+    boost::scoped_ptr<Allocator> alloc(new NakedIterativeAllocator(Lease::TYPE_NA));
+
+    // Restrict pool_ to the foo class. Add a second pool with bar class.
+    pool_->allowClientClass("foo");
+    Pool6Ptr pool(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::100"),
+                            IOAddress("2001:db8:1::109")));
+    pool->allowClientClass("bar");
+    subnet_->addPool(pool);
+
+    // Clients are in bar
+    cc_.insert("bar");
+
+    for (int i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc->pickAddress(subnet_, cc_,
+                                                 duid_, IOAddress("::"));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate, cc_));
+    }
+}
+
+// This test verifies that the allocator walks over the addresses in the
+// non-contiguous pools.
+TEST_F(IterativeAllocatorTest6, addrStep) {
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
+
+    subnet_->delPools(Lease::TYPE_NA); // Get rid of default pool
+
+    Pool6Ptr pool1(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::1"),
+                             IOAddress("2001:db8:1::5")));
+    Pool6Ptr pool2(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::100"),
+                             IOAddress("2001:db8:1::100")));
+    Pool6Ptr pool3(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::105"),
+                             IOAddress("2001:db8:1::106")));
+    subnet_->addPool(pool1);
+    subnet_->addPool(pool2);
+    subnet_->addPool(pool3);
+
+    // Let's check the first pool (5 addresses here)
+    EXPECT_EQ("2001:db8:1::1",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::2",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::3",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::4",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::5",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // The second pool is easy - only one address here
+    EXPECT_EQ("2001:db8:1::100",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // This is the third and last pool, with 2 addresses in it
+    EXPECT_EQ("2001:db8:1::105",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::106",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // We iterated over all addresses and reached to the end of the last pool.
+    // Let's wrap around and start from the beginning
+    EXPECT_EQ("2001:db8:1::1",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::2",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+}
+
+// This test verifies that the allocator walks over the addresses in the
+// non-contiguous pools when pools contain class guards.
+TEST_F(IterativeAllocatorTest6, addrStepInClass) {
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
+
+    subnet_->delPools(Lease::TYPE_NA); // Get rid of default pool
+
+    Pool6Ptr pool1(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::1"),
+                             IOAddress("2001:db8:1::5")));
+    Pool6Ptr pool2(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::100"),
+                             IOAddress("2001:db8:1::100")));
+    Pool6Ptr pool3(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::105"),
+                             IOAddress("2001:db8:1::106")));
+    // Set pool1 and pool3 but not pool2 in foo class
+    pool1->allowClientClass("foo");
+    pool3->allowClientClass("foo");
+    subnet_->addPool(pool1);
+    subnet_->addPool(pool2);
+    subnet_->addPool(pool3);
+
+    // Clients are in foo
+    cc_.insert("foo");
+
+    // Let's check the first pool (5 addresses here)
+    EXPECT_EQ("2001:db8:1::1",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::2",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::3",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::4",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::5",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // The second pool is easy - only one address here
+    EXPECT_EQ("2001:db8:1::100",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // This is the third and last pool, with 2 addresses in it
+    EXPECT_EQ("2001:db8:1::105",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::106",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // We iterated over all addresses and reached to the end of the last pool.
+    // Let's wrap around and start from the beginning
+    EXPECT_EQ("2001:db8:1::1",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::2",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+}
+
+// This test verifies that the allocator omits pools with non-matching class guards.
+TEST_F(IterativeAllocatorTest6, addrStepOutClass) {
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
+
+    subnet_->delPools(Lease::TYPE_NA); // Get rid of default pool
+
+    Pool6Ptr pool1(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::1"),
+                             IOAddress("2001:db8:1::5")));
+    Pool6Ptr pool2(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::100"),
+                             IOAddress("2001:db8:1::100")));
+    Pool6Ptr pool3(new Pool6(Lease::TYPE_NA, IOAddress("2001:db8:1::105"),
+                             IOAddress("2001:db8:1::106")));
+    // Set pool2 in foo
+    pool2->allowClientClass("foo");
+    subnet_->addPool(pool1);
+    subnet_->addPool(pool2);
+    subnet_->addPool(pool3);
+
+    // Let's check the first pool (5 addresses here)
+    EXPECT_EQ("2001:db8:1::1",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::2",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::3",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::4",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::5",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // The second pool is skipped
+
+    // This is the third and last pool, with 2 addresses in it
+    EXPECT_EQ("2001:db8:1::105",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::106",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // We iterated over all addresses and reached to the end of the last pool.
+    // Let's wrap around and start from the beginning
+    EXPECT_EQ("2001:db8:1::1",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:1::2",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+}
+
+// This test verifies that the allocator picks delegated prefixes from several
+// pools.
+TEST_F(IterativeAllocatorTest6, prefixStep) {
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
+
+    subnet_.reset(new Subnet6(IOAddress("2001:db8::"), 32, 1, 2, 3, 4));
+
+    Pool6Ptr pool1(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8::"), 56, 60));
+    Pool6Ptr pool2(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8:1::"), 48, 48));
+    Pool6Ptr pool3(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8:2::"), 56, 64));
+    subnet_->addPool(pool1);
+    subnet_->addPool(pool2);
+    subnet_->addPool(pool3);
+
+    // We have a 2001:db8::/48 subnet that has 3 pools defined in it:
+    // 2001:db8::/56 split into /60 prefixes (16 leases) (or 2001:db8:0:X0::)
+    // 2001:db8:1::/48 split into a single /48 prefix (just 1 lease)
+    // 2001:db8:2::/56 split into /64 prefixes (256 leases) (or 2001:db8:2:XX::)
+
+    // First pool check (Let's check over all 16 leases)
+    EXPECT_EQ("2001:db8::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:10::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:20::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:30::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:40::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:50::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:60::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:70::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:80::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:90::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:a0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:b0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:c0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:d0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:e0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:f0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // Second pool (just one lease here)
+    EXPECT_EQ("2001:db8:1::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // Third pool (256 leases, let's check first and last explicitly and the
+    // rest over in a pool
+    EXPECT_EQ("2001:db8:2::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    for (int i = 1; i < 255; i++) {
+        stringstream exp;
+        exp << "2001:db8:2:" << hex << i << dec << "::";
+        EXPECT_EQ(exp.str(),
+                  alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    }
+    EXPECT_EQ("2001:db8:2:ff::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // Ok, we've iterated over all prefixes in all pools. We now wrap around.
+    // We're looping over now (iterating over first pool again)
+    EXPECT_EQ("2001:db8::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:10::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+}
+
+// This test verifies that the allocator picks delegated prefixes from the pools
+// with class guards.
+TEST_F(IterativeAllocatorTest6, prefixStepInClass) {
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
+
+    subnet_.reset(new Subnet6(IOAddress("2001:db8::"), 32, 1, 2, 3, 4));
+
+    Pool6Ptr pool1(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8::"), 56, 60));
+    Pool6Ptr pool2(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8:1::"), 48, 48));
+    Pool6Ptr pool3(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8:2::"), 56, 64));
+    // Set pool1 and pool3 but not pool2 in foo class
+    pool1->allowClientClass("foo");
+    pool3->allowClientClass("foo");
+    subnet_->addPool(pool1);
+    subnet_->addPool(pool2);
+    subnet_->addPool(pool3);
+
+    // Clients are in foo
+    cc_.insert("foo");
+
+    // We have a 2001:db8::/48 subnet that has 3 pools defined in it:
+    // 2001:db8::/56 split into /60 prefixes (16 leases) (or 2001:db8:0:X0::)
+    // 2001:db8:1::/48 split into a single /48 prefix (just 1 lease)
+    // 2001:db8:2::/56 split into /64 prefixes (256 leases) (or 2001:db8:2:XX::)
+
+    // First pool check (Let's check over all 16 leases)
+    EXPECT_EQ("2001:db8::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:10::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:20::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:30::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:40::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:50::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:60::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:70::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:80::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:90::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:a0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:b0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:c0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:d0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:e0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:f0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // Second pool (just one lease here)
+    EXPECT_EQ("2001:db8:1::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // Third pool (256 leases, let's check first and last explicitly and the
+    // rest over in a pool
+    EXPECT_EQ("2001:db8:2::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    for (int i = 1; i < 255; i++) {
+        stringstream exp;
+        exp << "2001:db8:2:" << hex << i << dec << "::";
+        EXPECT_EQ(exp.str(),
+                  alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    }
+    EXPECT_EQ("2001:db8:2:ff::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // Ok, we've iterated over all prefixes in all pools. We now wrap around.
+    // We're looping over now (iterating over first pool again)
+    EXPECT_EQ("2001:db8::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:10::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+}
+
+// This test verifies that the allocator omits pools with non-matching client classes.
+TEST_F(IterativeAllocatorTest6, prefixStepOutClass) {
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
+
+    subnet_.reset(new Subnet6(IOAddress("2001:db8::"), 32, 1, 2, 3, 4));
+
+    Pool6Ptr pool1(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8::"), 56, 60));
+    Pool6Ptr pool2(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8:1::"), 48, 48));
+    Pool6Ptr pool3(new Pool6(Lease::TYPE_PD, IOAddress("2001:db8:2::"), 56, 64));
+    // Set pool2 in foo
+    pool2->allowClientClass("foo");
+    subnet_->addPool(pool1);
+    subnet_->addPool(pool2);
+    subnet_->addPool(pool3);
+
+    // We have a 2001:db8::/48 subnet that has 3 pools defined in it:
+    // 2001:db8::/56 split into /60 prefixes (16 leases) (or 2001:db8:0:X0::)
+    // 2001:db8:1::/48 split into a single /48 prefix (just 1 lease)
+    // 2001:db8:2::/56 split into /64 prefixes (256 leases) (or 2001:db8:2:XX::)
+
+    // First pool check (Let's check over all 16 leases)
+    EXPECT_EQ("2001:db8::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:10::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:20::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:30::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:40::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:50::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:60::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:70::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:80::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:90::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:a0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:b0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:c0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:d0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:e0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:f0::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // The second pool is skipped
+
+    // Third pool (256 leases, let's check first and last explicitly and the
+    // rest over in a pool
+    EXPECT_EQ("2001:db8:2::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    for (int i = 1; i < 255; i++) {
+        stringstream exp;
+        exp << "2001:db8:2:" << hex << i << dec << "::";
+        EXPECT_EQ(exp.str(),
+                  alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    }
+    EXPECT_EQ("2001:db8:2:ff::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+
+    // Ok, we've iterated over all prefixes in all pools. We now wrap around.
+    // We're looping over now (iterating over first pool again)
+    EXPECT_EQ("2001:db8::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+    EXPECT_EQ("2001:db8:0:10::",
+              alloc.pickAddress(subnet_, cc_, duid_, IOAddress("::")).toText());
+}
+
+// This test verifies that the iterative allocator can step over addresses.
+TEST_F(IterativeAllocatorTest6, addressIncrease) {
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
+
+    // Let's pick the first address
+    IOAddress addr1 = alloc.pickAddress(subnet_, cc_, duid_, IOAddress("2001:db8:1::10"));
+
+    // Check that we can indeed pick the first address from the pool
+    EXPECT_EQ("2001:db8:1::10", addr1.toText());
+
+    // Check that addresses can be increased properly
+    checkAddrIncrease(alloc, "2001:db8::9", "2001:db8::a");
+    checkAddrIncrease(alloc, "2001:db8::f", "2001:db8::10");
+    checkAddrIncrease(alloc, "2001:db8::10", "2001:db8::11");
+    checkAddrIncrease(alloc, "2001:db8::ff", "2001:db8::100");
+    checkAddrIncrease(alloc, "2001:db8::ffff", "2001:db8::1:0");
+    checkAddrIncrease(alloc, "::", "::1");
+    checkAddrIncrease(alloc, "ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff", "::");
+}
+
+// This test verifies that the allocator can step over prefixes.
+TEST_F(IterativeAllocatorTest6, prefixIncrease) {
+    NakedIterativeAllocator alloc(Lease::TYPE_PD);
+
+    // For /128 prefix, increasePrefix should work the same as addressIncrease
+    checkPrefixIncrease(alloc, "2001:db8::9", 128, "2001:db8::a");
+    checkPrefixIncrease(alloc, "2001:db8::f", 128, "2001:db8::10");
+    checkPrefixIncrease(alloc, "2001:db8::10", 128, "2001:db8::11");
+    checkPrefixIncrease(alloc, "2001:db8::ff", 128, "2001:db8::100");
+    checkPrefixIncrease(alloc, "2001:db8::ffff", 128, "2001:db8::1:0");
+    checkPrefixIncrease(alloc, "::", 128, "::1");
+    checkPrefixIncrease(alloc, "ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff", 128, "::");
+
+    // Check that /64 prefixes can be generated
+    checkPrefixIncrease(alloc, "2001:db8::", 64, "2001:db8:0:1::");
+
+    // Check that prefix length not divisible by 8 are working
+    checkPrefixIncrease(alloc, "2001:db8::", 128, "2001:db8::1");
+    checkPrefixIncrease(alloc, "2001:db8::", 127, "2001:db8::2");
+    checkPrefixIncrease(alloc, "2001:db8::", 126, "2001:db8::4");
+    checkPrefixIncrease(alloc, "2001:db8::", 125, "2001:db8::8");
+    checkPrefixIncrease(alloc, "2001:db8::", 124, "2001:db8::10");
+    checkPrefixIncrease(alloc, "2001:db8::", 123, "2001:db8::20");
+    checkPrefixIncrease(alloc, "2001:db8::", 122, "2001:db8::40");
+    checkPrefixIncrease(alloc, "2001:db8::", 121, "2001:db8::80");
+    checkPrefixIncrease(alloc, "2001:db8::", 120, "2001:db8::100");
+
+    // These are not really useful cases, because there are bits set
+    // int the last (128 - prefix_len) bits. Nevertheless, it shows
+    // that the algorithm is working even in such cases
+    checkPrefixIncrease(alloc, "2001:db8::1", 128, "2001:db8::2");
+    checkPrefixIncrease(alloc, "2001:db8::1", 127, "2001:db8::3");
+    checkPrefixIncrease(alloc, "2001:db8::1", 126, "2001:db8::5");
+    checkPrefixIncrease(alloc, "2001:db8::1", 125, "2001:db8::9");
+    checkPrefixIncrease(alloc, "2001:db8::1", 124, "2001:db8::11");
+    checkPrefixIncrease(alloc, "2001:db8::1", 123, "2001:db8::21");
+    checkPrefixIncrease(alloc, "2001:db8::1", 122, "2001:db8::41");
+    checkPrefixIncrease(alloc, "2001:db8::1", 121, "2001:db8::81");
+    checkPrefixIncrease(alloc, "2001:db8::1", 120, "2001:db8::101");
+
+    // Let's try out couple real life scenarios
+    checkPrefixIncrease(alloc, "2001:db8:1:abcd::", 64, "2001:db8:1:abce::");
+    checkPrefixIncrease(alloc, "2001:db8:1:abcd::", 60, "2001:db8:1:abdd::");
+    checkPrefixIncrease(alloc, "2001:db8:1:abcd::", 56, "2001:db8:1:accd::");
+    checkPrefixIncrease(alloc, "2001:db8:1:abcd::", 52, "2001:db8:1:bbcd::");
+
+    // And now let's try something over the top
+    checkPrefixIncrease(alloc, "::", 1, "8000::");
+}
+
+// This test verifies that the iterative allocator really walks over all addresses
+// in all pools in specified subnet. It also must not pick the same address twice
+// unless it runs out of pool space and must start over.
+TEST_F(IterativeAllocatorTest6, manyPools) {
+    NakedIterativeAllocator alloc(Lease::TYPE_NA);
+
+    // let's start from 2, as there is 2001:db8:1::10 - 2001:db8:1::20 pool already.
+    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;
+
+        Pool6Ptr pool(new Pool6(Lease::TYPE_NA, IOAddress(min.str()),
+                                IOAddress(max.str())));
+        subnet_->addPool(pool);
+    }
+
+    int total = 17 + 8 * 9; // First pool (::10 - ::20) has 17 addresses in it,
+                            // there are 8 extra pools with 9 addresses in each.
+
+    // Let's keep picked addresses here and check their uniqueness.
+    std::set<IOAddress> generated_addrs;
+    int cnt = 0;
+    while (++cnt) {
+        IOAddress candidate = alloc.pickAddress(subnet_, cc_,
+                                                duid_, IOAddress("::"));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate));
+
+        // One way to easily verify that the iterative allocator really works is
+        // to uncomment the following line and observe its output that it
+        // covers all defined pools.
+        // cout << candidate.toText() << endl;
+
+        if (generated_addrs.find(candidate) == generated_addrs.end()) {
+            // We haven't had this.
+            generated_addrs.insert(candidate);
+        } else {
+            // We have seen this address before. That should mean that we
+            // iterated over all addresses.
+            if (generated_addrs.size() == total) {
+                // We have exactly the number of address in all pools.
+                break;
+            }
+            ADD_FAILURE() << "Too many or not enough unique addresses generated.";
+            break;
+        }
+
+        if ( cnt>total ) {
+            ADD_FAILURE() << "Too many unique addresses generated.";
+            break;
+        }
+    }
+}
+
+} // end of namespace isc::dhcp::test
+} // end of namespace isc::dhcp
+} // end of namespace isc
\ No newline at end of file