1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
// Copyright (C) 2020-2021 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 <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);
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.
uint64_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.
uint64_t cursor_;
/// Keeps the current permutation state. The state associates the
/// swapped IP addresses or delegated prefixes with their positions in
/// the permutation.
std::map<uint64_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
|
