diff options
Diffstat (limited to 'src/lib/dhcpsrv/ip_range_permutation.h')
| -rw-r--r-- | src/lib/dhcpsrv/ip_range_permutation.h | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/src/lib/dhcpsrv/ip_range_permutation.h b/src/lib/dhcpsrv/ip_range_permutation.h new file mode 100644 index 0000000..ca7a5ae --- /dev/null +++ b/src/lib/dhcpsrv/ip_range_permutation.h @@ -0,0 +1,147 @@ +// Copyright (C) 2020-2023 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 IP_RANGE_PERMUTATION_H +#define IP_RANGE_PERMUTATION_H + +#include <asiolink/io_address.h> +#include <dhcpsrv/ip_range.h> +#include <util/bigints.h> + +#include <boost/shared_ptr.hpp> + +#include <map> +#include <random> + +namespace isc { +namespace dhcp { + +/// @brief Random IP address/prefix permutation based on Fisher-Yates shuffle. +/// +/// This class is used to shuffle IP addresses or delegated prefixes within +/// the specified range. It is following the Fisher-Yates shuffle algorithm +/// described in https://en.wikipedia.org/wiki/Fisher–Yates_shuffle. +/// +/// The original algorithm is modified to keep the minimal information about +/// the current state of the permutation and relies on the caller to collect +/// and store the next available value. In other words, the generated and +/// already returned random values are not stored by this class. +/// +/// The class assumes that initially the IP addresses or delegated prefixes +/// in the specified range are in increasing order. Suppose we're dealing with +/// the following address range: 192.0.2.1-192.0.2.5. Therefore our addresses +/// are initially ordered like this: a[0]=192.0.2.1, a[1]=192.0.2.2 ..., +/// a[4]=192.0.2.5. The algorithm starts from the end of that range, i.e. i=4, +/// so a[i]=192.0.2.5. A random value from the range of [0..i-1] is picked, +/// i.e. a value from the range of [0..3]. Let's say it is 1. This value initially +/// corresponds to the address a[1]=192.0.2.2. In the original algorithm the +/// value of a[1] is swapped with a[4], yelding the following partial permutation: +/// 192.0.2.1, 192.0.2.5, 192.0.2.3, 192.0.2.4, 192.0.2.2. In our case, we simply +/// return the value of 192.0.2.2 to the caller and remember that +/// a[1]=192.0.2.5. At this point we don't store the values of a[0], a[2] and +/// a[3] because the corresponding IP addresses can be calculated from the +/// range start and their index in the permutation. The value of a[1] must be +/// stored because it has been swapped with a[4] and can't be calculated from +/// the position index. +/// +/// In the next step, the current index i (cursor value) is decreased by one. +/// It now has the value of 3. Again, a random index is picked from the range +/// of [0..3]. Note that it can be the same or different index than selected +/// in the previous step. Let's assume it is 0. This corresponds to the address +/// of 192.0.2.1. This address will be returned to the caller. The value of +/// a[3]=192.0.2.4 is moved to a[0]. This yelds the following permutation: +/// 192.0.2.4, 192.0.2.5, 192.0.2.3, 192.0.2.1, 192.0.2.2. However, we only +/// remember a[0] and a[1]. The a[3] can be still computed from the range +/// start and the position. The other two have been already returned to the +/// caller so we forget them. +/// +/// This algorithm guarantees that all IP addresses or delegated prefixes +/// belonging to the given range are returned and no duplicates are returned. +/// The addresses or delegated prefixes are returned in a random order. +/// +/// @todo Methods of this class should be called in thread safe context. Otherwise +/// they should be made thread safe. +class IPRangePermutation { +public: + + /// @brief Constructor for address ranges. + /// + /// @param range address range for which the permutation will be generated. + IPRangePermutation(const AddressRange& range); + + /// @brief Constructor for prefix ranges. + /// + /// @param range range of delegated prefixes for which the permutation will + /// be generated. + IPRangePermutation(const PrefixRange& range); + + /// @brief Checks if the range has been exhausted. + /// + /// @return false if the algorithm went over all addresses or prefixes in + /// the range, true otherwise. + bool exhausted() const { + return (done_); + } + + /// @brief Returns next random address or prefix from the permutation. + /// + /// This method returns all addresses or prefixes belonging to the specified + /// range in random order. For the first number of calls equal to the size of + /// the range it guarantees to return a non-zero IP address from that range + /// without duplicates. + /// + /// @param [out] done this parameter is set to true if no more addresses + /// or prefixes can be returned for this permutation. + /// @return next available IP address or prefix. It returns IPv4 zero or IPv6 + /// zero address after this method walked over all available IP addresses or + /// prefixes in the range. + asiolink::IOAddress next(bool& done); + + /// @brief Resets the permutation state. + /// + /// It effectively causes the permutation to start over the process of + /// serving addresses. Any previously returned addresses can be returned + /// again after calling this function. + void reset(); + +private: + + /// Beginning of the range. + asiolink::IOAddress range_start_; + + /// Distance between two neighboring addresses or delegated prefixes, + /// i.e. 1 for address range and delegated prefix size for delegated + /// prefixes. + isc::util::uint128_t step_; + + /// Keeps the position of the next address or prefix to be swapped with + /// a randomly picked address or prefix from the range of 0..cursor-1. The + /// cursor value is decreased every time a new IP address or prefix + /// is returned. + isc::util::uint128_t cursor_; + + /// Keeps the initial cursor position for @c reset function. + isc::util::uint128_t initial_cursor_; + + /// Keeps the current permutation state. The state associates the + /// swapped IP addresses or delegated prefixes with their positions in + /// the permutation. + std::map<isc::util::uint128_t, asiolink::IOAddress> state_; + + /// Indicates if the addresses or delegated prefixes are exhausted. + bool done_; + + /// Random generator. + std::mt19937 generator_; +}; + +/// @brief Pointer to the @c IPRangePermutation. +typedef boost::shared_ptr<IPRangePermutation> IPRangePermutationPtr; + +} // end of namespace isc::dhcp +} // end of namespace isc + +#endif // IP_RANGE_PERMUTATION_H |