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
|
// 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/.
#include <config.h>
#include <asiolink/addr_utilities.h>
#include <dhcpsrv/ip_range_permutation.h>
#include <iostream>
using namespace isc::asiolink;
namespace isc {
namespace dhcp {
IPRangePermutation::IPRangePermutation(const AddressRange& range)
: range_start_(range.start_), step_(1), cursor_(addrsInRange(range_start_, range.end_) - 1),
initial_cursor_(cursor_), state_(), done_(false), generator_() {
std::random_device rd;
generator_.seed(rd());
}
IPRangePermutation::IPRangePermutation(const PrefixRange& range)
: range_start_(range.start_), step_(isc::util::uint128_t(1) << (128 - range.delegated_length_)),
cursor_(prefixesInRange(range.prefix_length_, range.delegated_length_) - 1),
initial_cursor_(cursor_), state_(), done_(false), generator_() {
std::random_device rd;
generator_.seed(rd());
}
IOAddress
IPRangePermutation::next(bool& done) {
// If we're done iterating over the pool let's return zero address and
// set the user supplied done flag to true.
if (done_) {
done = true;
return (range_start_.isV4() ? IOAddress::IPV4_ZERO_ADDRESS() : IOAddress::IPV6_ZERO_ADDRESS());
}
// If there is one address left, return this address.
if (cursor_ == 0) {
done = done_ = true;
return (state_.at(0));
}
// We're not done.
done = false;
// The cursor indicates where we're in the range starting from its end. The
// addresses between the cursor and the end of the range have been already
// returned by this function. Therefore we focus on the remaining cursor-1
// addresses. Let's get random address from this sub-range.
uint64_t max_limit = std::numeric_limits<uint64_t>::max();
if ((cursor_ - 1) < isc::util::int128_t(max_limit)) {
max_limit = static_cast<uint64_t>(cursor_ - 1);
}
std::uniform_int_distribution<uint64_t> dist(0, max_limit);
auto next_loc = dist(generator_);
IOAddress next_loc_address = IOAddress::IPV4_ZERO_ADDRESS();
// Check whether this address exists in our map or not. If it exists
// it means it was swapped with some other address in previous calls to
// this function.
auto next_loc_existing = state_.find(next_loc);
if (next_loc_existing != state_.end()) {
// Address exists, so let's record it.
next_loc_address = next_loc_existing->second;
} else {
// Address does not exist on this position. We infer this address from
// its position by advancing the range start by position. For example,
// if the range is 192.0.2.1-192.0.2.10 and the picked random position is
// 5, the address we get is 192.0.2.6. This random address will be later
// returned to the caller.
next_loc_address = offsetAddress(range_start_, next_loc * step_);
}
// Let's get the address at cursor position in the same way.
IOAddress cursor_address = IOAddress::IPV4_ZERO_ADDRESS();
auto cursor_existing = state_.find(cursor_);
if (cursor_existing != state_.end()) {
cursor_address = cursor_existing->second;
} else {
cursor_address = offsetAddress(range_start_, cursor_ * step_);
}
// Now we swap them.... in fact we don't swap because as an optimization
// we don't record the addresses we returned by this function. We merely
// replace the address at random position with the address from cursor
// position. This address will be returned in the future if we get back
// to this position as a result of randomization.
if (next_loc_existing == state_.end()) {
state_.insert(std::make_pair(next_loc, cursor_address));
} else {
state_.at(next_loc) = cursor_address;
}
// Move the cursor one position backwards.
--cursor_;
// Return the address from the random position.
return (next_loc_address);
}
void
IPRangePermutation::reset() {
state_.clear();
cursor_ = initial_cursor_;
done_ = false;
}
} // end of namespace isc::dhcp
} // end of namespace isc
|
