Coverage Report

Created: 2026-08-14 08:07

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/kea/src/lib/dhcpsrv/ip_range_permutation.h
Line
Count
Source
1
// Copyright (C) 2020-2024 Internet Systems Consortium, Inc. ("ISC")
2
//
3
// This Source Code Form is subject to the terms of the Mozilla Public
4
// License, v. 2.0. If a copy of the MPL was not distributed with this
5
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
6
7
#ifndef IP_RANGE_PERMUTATION_H
8
#define IP_RANGE_PERMUTATION_H
9
10
#include <asiolink/io_address.h>
11
#include <dhcpsrv/ip_range.h>
12
#include <util/bigints.h>
13
14
#include <boost/shared_ptr.hpp>
15
16
#include <map>
17
#include <random>
18
19
namespace isc {
20
namespace dhcp {
21
22
/// @brief Random IP address/prefix permutation based on Fisher-Yates shuffle.
23
///
24
/// This class is used to shuffle IP addresses or delegated prefixes within
25
/// the specified range. It is following the Fisher-Yates shuffle algorithm
26
/// described in https://en.wikipedia.org/wiki/Fisher-Yates_shuffle.
27
///
28
/// The original algorithm is modified to keep the minimal information about
29
/// the current state of the permutation and relies on the caller to collect
30
/// and store the next available value. In other words, the generated and
31
/// already returned random values are not stored by this class.
32
///
33
/// The class assumes that initially the IP addresses or delegated prefixes
34
/// in the specified range are in increasing order. Suppose we're dealing with
35
/// the following address range: 192.0.2.1-192.0.2.5. Therefore our addresses
36
/// are initially ordered like this: a[0]=192.0.2.1, a[1]=192.0.2.2 ...,
37
/// a[4]=192.0.2.5. The algorithm starts from the end of that range, i.e. i=4,
38
/// so a[i]=192.0.2.5. A random value from the range of [0..i-1] is picked,
39
/// i.e. a value from the range of [0..3]. Let's say it is 1. This value initially
40
/// corresponds to the address a[1]=192.0.2.2. In the original algorithm the
41
/// value of a[1] is swapped with a[4], yelding the following partial permutation:
42
/// 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
43
/// return the value of 192.0.2.2 to the caller and remember that
44
/// a[1]=192.0.2.5. At this point we don't store the values of a[0], a[2] and
45
/// a[3] because the corresponding IP addresses can be calculated from the
46
/// range start and their index in the permutation. The value of a[1] must be
47
/// stored because it has been swapped with a[4] and can't be calculated from
48
/// the position index.
49
///
50
/// In the next step, the current index i (cursor value) is decreased by one.
51
/// It now has the value of 3. Again, a random index is picked from the range
52
/// of [0..3]. Note that it can be the same or different index than selected
53
/// in the previous step. Let's assume it is 0. This corresponds to the address
54
/// of 192.0.2.1. This address will be returned to the caller. The value of
55
/// a[3]=192.0.2.4 is moved to a[0]. This yelds the following permutation:
56
/// 192.0.2.4, 192.0.2.5, 192.0.2.3, 192.0.2.1, 192.0.2.2. However, we only
57
/// remember a[0] and a[1]. The a[3] can be still computed from the range
58
/// start and the position. The other two have been already returned to the
59
/// caller so we forget them.
60
///
61
/// This algorithm guarantees that all IP addresses or delegated prefixes
62
/// belonging to the given range are returned and no duplicates are returned.
63
/// The addresses or delegated prefixes are returned in a random order.
64
///
65
/// @todo Methods of this class should be called in thread safe context. Otherwise
66
/// they should be made thread safe.
67
class IPRangePermutation {
68
public:
69
70
    /// @brief Constructor for address ranges.
71
    ///
72
    /// @param range address range for which the permutation will be generated.
73
    IPRangePermutation(const AddressRange& range);
74
75
    /// @brief Constructor for prefix ranges.
76
    ///
77
    /// @param range range of delegated prefixes for which the permutation will
78
    /// be generated.
79
    IPRangePermutation(const PrefixRange& range);
80
81
    /// @brief Checks if the range has been exhausted.
82
    ///
83
    /// @return false if the algorithm went over all addresses or prefixes in
84
    /// the range, true otherwise.
85
0
    bool exhausted() const {
86
0
        return (done_);
87
0
    }
88
89
    /// @brief Returns next random address or prefix from the permutation.
90
    ///
91
    /// This method returns all addresses or prefixes belonging to the specified
92
    /// range in random order. For the first number of calls equal to the size of
93
    /// the range it guarantees to return a non-zero IP address from that range
94
    /// without duplicates.
95
    ///
96
    /// @param [out] done this parameter is set to true if no more addresses
97
    /// or prefixes can be returned for this permutation.
98
    /// @return next available IP address or prefix. It returns IPv4 zero or IPv6
99
    /// zero address after this method walked over all available IP addresses or
100
    /// prefixes in the range.
101
    asiolink::IOAddress next(bool& done);
102
103
    /// @brief Resets the permutation state.
104
    ///
105
    /// It effectively causes the permutation to start over the process of
106
    /// serving addresses. Any previously returned addresses can be returned
107
    /// again after calling this function.
108
    void reset();
109
110
private:
111
112
    /// Beginning of the range.
113
    asiolink::IOAddress range_start_;
114
115
    /// Distance between two neighboring addresses or delegated prefixes,
116
    /// i.e. 1 for address range and delegated prefix size for delegated
117
    /// prefixes.
118
    isc::util::uint128_t step_;
119
120
    /// Keeps the position of the next address or prefix to be swapped with
121
    /// a randomly picked address or prefix from the range of 0..cursor-1. The
122
    /// cursor value is decreased every time a new IP address or prefix
123
    /// is returned.
124
    isc::util::uint128_t cursor_;
125
126
    /// Keeps the initial cursor position for @c reset function.
127
    isc::util::uint128_t initial_cursor_;
128
129
    /// Keeps the current permutation state. The state associates the
130
    /// swapped IP addresses or delegated prefixes with their positions in
131
    /// the permutation.
132
    std::map<isc::util::uint128_t, asiolink::IOAddress> state_;
133
134
    /// Indicates if the addresses or delegated prefixes are exhausted.
135
    bool done_;
136
137
    /// Random generator.
138
    std::mt19937 generator_;
139
};
140
141
/// @brief Pointer to the @c IPRangePermutation.
142
typedef boost::shared_ptr<IPRangePermutation> IPRangePermutationPtr;
143
144
} // end of namespace isc::dhcp
145
} // end of namespace isc
146
147
#endif // IP_RANGE_PERMUTATION_H