Kea 2.7.0
iterative_allocator.cc
Go to the documentation of this file.
1// Copyright (C) 2022-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#include <config.h>
8
11#include <boost/pointer_cast.hpp>
12#include <cstring>
13
14using namespace isc::asiolink;
15using namespace std;
16
17namespace isc {
18namespace dhcp {
19
21 const WeakSubnetPtr& subnet)
22 : Allocator(type, subnet) {
23}
24
27 const uint8_t prefix_len) {
28 if (!prefix.isV6()) {
29 isc_throw(BadValue, "Prefix operations are for IPv6 only (attempted to "
30 "increase prefix " << prefix << ")");
31 }
32
33 // Get a buffer holding an address.
34 const std::vector<uint8_t>& vec = prefix.toBytes();
35
36 if (prefix_len < 1 || prefix_len > 128) {
37 isc_throw(BadValue, "Cannot increase prefix: invalid prefix length: "
38 << prefix_len);
39 }
40
41 uint8_t n_bytes = (prefix_len - 1)/8;
42 uint8_t n_bits = 8 - (prefix_len - n_bytes*8);
43 uint8_t mask = 1 << n_bits;
44
45 // Explanation: n_bytes specifies number of full bytes that are in-prefix.
46 // They can also be used as an offset for the first byte that is not in
47 // prefix. n_bits specifies number of bits on the last byte that is
48 // (often partially) in prefix. For example for a /125 prefix, the values
49 // are 15 and 3, respectively. Mask is a bitmask that has the least
50 // significant bit from the prefix set.
51
52 uint8_t packed[V6ADDRESS_LEN];
53
54 // Copy the address. It must be V6, but we already checked that.
55 memcpy(packed, &vec[0], V6ADDRESS_LEN);
56
57 // Can we safely increase only the last byte in prefix without overflow?
58 if (packed[n_bytes] + uint16_t(mask) < 256u) {
59 packed[n_bytes] += mask;
60 return (IOAddress::fromBytes(AF_INET6, packed));
61 }
62
63 // Overflow (done on uint8_t, but the sum is greater than 255)
64 packed[n_bytes] += mask;
65
66 // Deal with the overflow. Start increasing the least significant byte
67 for (int i = n_bytes - 1; i >= 0; --i) {
68 ++packed[i];
69 // If we haven't overflowed (0xff->0x0) the next byte, then we are done
70 if (packed[i] != 0) {
71 break;
72 }
73 }
74
75 return (IOAddress::fromBytes(AF_INET6, packed));
76}
77
80 bool prefix,
81 const uint8_t prefix_len) {
82 if (!prefix) {
83 return (IOAddress::increase(address));
84 } else {
85 return (increasePrefix(address, prefix_len));
86 }
87}
88
90IterativeAllocator::pickAddressInternal(const ClientClasses& client_classes,
92 const IOAddress&) {
93 // Let's get the last allocated address. It is usually set correctly,
94 // but there are times when it won't be (like after removing a pool or
95 // perhaps restarting the server).
96 IOAddress last = getSubnetState()->getLastAllocated();
97 bool valid = true;
98 bool retrying = false;
99
100 auto const& pools = subnet_.lock()->getPools(pool_type_);
101
102 if (pools.empty()) {
103 isc_throw(AllocFailed, "No pools defined in selected subnet");
104 }
105
106 // first we need to find a pool the last address belongs to.
107 PoolCollection::const_iterator it;
108 PoolCollection::const_iterator first = pools.end();
109 PoolPtr first_pool;
110 for (it = pools.begin(); it != pools.end(); ++it) {
111 if (!(*it)->clientSupported(client_classes)) {
112 continue;
113 }
114 if (first == pools.end()) {
115 first = it;
116 }
117 if ((*it)->inRange(last)) {
118 break;
119 }
120 }
121
122 // Caller checked this cannot happen
123 if (first == pools.end()) {
124 isc_throw(AllocFailed, "No allowed pools defined in selected subnet");
125 }
126
127 // last one was bogus for one of several reasons:
128 // - we just booted up and that's the first address we're allocating
129 // - a subnet was removed or other reconfiguration just completed
130 // - perhaps allocation algorithm was changed
131 // - last pool does not allow this client
132 if (it == pools.end()) {
133 it = first;
134 }
135
136 for (;;) {
137 // Trying next pool
138 if (retrying) {
139 for (; it != pools.end(); ++it) {
140 if ((*it)->clientSupported(client_classes)) {
141 break;
142 }
143 }
144 if (it == pools.end()) {
145 // Really out of luck today. That was the last pool.
146 break;
147 }
148 }
149
150 last = getPoolState(*it)->getLastAllocated();
151 valid = getPoolState(*it)->isLastAllocatedValid();
152 if (!valid && (last == (*it)->getFirstAddress())) {
153 // Pool was (re)initialized
154 getPoolState(*it)->setLastAllocated(last);
155 getSubnetState()->setLastAllocated(last);
156 return (last);
157 }
158 // still can be bogus
159 if (valid && !(*it)->inRange(last)) {
160 valid = false;
161 getPoolState(*it)->resetLastAllocated();
162 getPoolState(*it)->setLastAllocated((*it)->getFirstAddress());
163 }
164
165 if (valid) {
166 IOAddress next = increaseAddress(last, false, 0);
167 if ((*it)->inRange(next)) {
168 // the next one is in the pool as well, so we haven't hit
169 // pool boundary yet
170 getPoolState(*it)->setLastAllocated(next);
171 getSubnetState()->setLastAllocated(next);
172 return (next);
173 }
174
175 getPoolState(*it)->resetLastAllocated();
176 }
177 // We hit pool boundary, let's try to jump to the next pool and try again
178 ++it;
179 retrying = true;
180 }
181
182 // Let's rewind to the beginning.
183 for (it = first; it != pools.end(); ++it) {
184 if ((*it)->clientSupported(client_classes)) {
185 getPoolState(*it)->setLastAllocated((*it)->getFirstAddress());
186 getPoolState(*it)->resetLastAllocated();
187 }
188 }
189
190 // ok to access first element directly. We checked that pools is non-empty
191 last = getPoolState(*first)->getLastAllocated();
192 getPoolState(*first)->setLastAllocated(last);
193 getSubnetState()->setLastAllocated(last);
194 return (last);
195}
196
198IterativeAllocator::pickPrefixInternal(const ClientClasses& client_classes,
199 Pool6Ptr& pool6,
201 PrefixLenMatchType prefix_length_match,
202 const IOAddress&,
203 uint8_t hint_prefix_length) {
204 uint8_t prefix_len = 0;
205
206 // Let's get the last allocated prefix. It is usually set correctly,
207 // but there are times when it won't be (like after removing a pool or
208 // perhaps restarting the server).
209 IOAddress last = getSubnetState()->getLastAllocated();
210 bool valid = true;
211 bool retrying = false;
212
213 auto const& pools = subnet_.lock()->getPools(pool_type_);
214
215 if (pools.empty()) {
216 isc_throw(AllocFailed, "No pools defined in selected subnet");
217 }
218
219 // first we need to find a pool the last prefix belongs to.
220 PoolCollection::const_iterator it;
221 PoolCollection::const_iterator first = pools.end();
222 PoolPtr first_pool;
223 for (it = pools.begin(); it != pools.end(); ++it) {
224 if (!(*it)->clientSupported(client_classes)) {
225 continue;
226 }
227 if (!Allocator::isValidPrefixPool(prefix_length_match, *it,
228 hint_prefix_length)) {
229 continue;
230 }
231 if (first == pools.end()) {
232 first = it;
233 }
234 if ((*it)->inRange(last)) {
235 break;
236 }
237 }
238
239 // Caller checked this cannot happen
240 if (first == pools.end()) {
241 isc_throw(AllocFailed, "No allowed pools defined in selected subnet");
242 }
243
244 // last one was bogus for one of several reasons:
245 // - we just booted up and that's the first prefix we're allocating
246 // - a subnet was removed or other reconfiguration just completed
247 // - perhaps allocation algorithm was changed
248 // - last pool does not allow this client
249 if (it == pools.end()) {
250 it = first;
251 }
252
253 for (;;) {
254 // Trying next pool
255 if (retrying) {
256 for (; it != pools.end(); ++it) {
257 if ((*it)->clientSupported(client_classes)) {
258 if (!Allocator::isValidPrefixPool(prefix_length_match, *it,
259 hint_prefix_length)) {
260 continue;
261 }
262 break;
263 }
264 }
265 if (it == pools.end()) {
266 // Really out of luck today. That was the last pool.
267 break;
268 }
269 }
270
271 last = getPoolState(*it)->getLastAllocated();
272 valid = getPoolState(*it)->isLastAllocatedValid();
273 if (!valid && (last == (*it)->getFirstAddress())) {
274 // Pool was (re)initialized
275 getPoolState(*it)->setLastAllocated(last);
276 getSubnetState()->setLastAllocated(last);
277
278 pool6 = boost::dynamic_pointer_cast<Pool6>(*it);
279
280 if (!pool6) {
281 // Something is gravely wrong here
282 isc_throw(Unexpected, "Wrong type of pool: "
283 << (*it)->toText()
284 << " is not Pool6");
285 }
286
287 return (last);
288 }
289 // still can be bogus
290 if (valid && !(*it)->inRange(last)) {
291 valid = false;
292 getPoolState(*it)->resetLastAllocated();
293 getPoolState(*it)->setLastAllocated((*it)->getFirstAddress());
294 }
295
296 if (valid) {
297 // Ok, we have a pool that the last prefix belonged to, let's use it.
298 pool6 = boost::dynamic_pointer_cast<Pool6>(*it);
299 if (!pool6) {
300 // Something is gravely wrong here
301 isc_throw(Unexpected, "Wrong type of pool: "
302 << (*it)->toText()
303 << " is not Pool6");
304 }
305
306 // Get the prefix length
307 prefix_len = pool6->getLength();
308
309 IOAddress next = increaseAddress(last, true, prefix_len);
310 if ((*it)->inRange(next)) {
311 // the next one is in the pool as well, so we haven't hit
312 // pool boundary yet
313 getPoolState(*it)->setLastAllocated(next);
314 getSubnetState()->setLastAllocated(next);
315 return (next);
316 }
317
318 getPoolState(*it)->resetLastAllocated();
319 }
320 // We hit pool boundary, let's try to jump to the next pool and try again
321 ++it;
322 retrying = true;
323 }
324
325 // Let's rewind to the beginning.
326 for (it = first; it != pools.end(); ++it) {
327 if ((*it)->clientSupported(client_classes)) {
328 if (!Allocator::isValidPrefixPool(prefix_length_match, *it,
329 hint_prefix_length)) {
330 continue;
331 }
332 getPoolState(*it)->setLastAllocated((*it)->getFirstAddress());
333 getPoolState(*it)->resetLastAllocated();
334 }
335 }
336
337 // ok to access first element directly. We checked that pools is non-empty
338 last = getPoolState(*first)->getLastAllocated();
339 getPoolState(*first)->setLastAllocated(last);
340 getSubnetState()->setLastAllocated(last);
341
342 pool6 = boost::dynamic_pointer_cast<Pool6>(*first);
343 if (!pool6) {
344 // Something is gravely wrong here
345 isc_throw(Unexpected, "Wrong type of pool: "
346 << (*it)->toText()
347 << " is not Pool6");
348 }
349 return (last);
350}
351
353IterativeAllocator::getSubnetState() const {
354 auto subnet = subnet_.lock();
355 if (!subnet->getAllocationState(pool_type_)) {
356 subnet->setAllocationState(pool_type_, SubnetIterativeAllocationState::create(subnet));
357 }
358 return (boost::dynamic_pointer_cast<SubnetIterativeAllocationState>(subnet->getAllocationState(pool_type_)));
359}
360
362IterativeAllocator::getPoolState(const PoolPtr& pool) const {
363 if (!pool->getAllocationState()) {
364 pool->setAllocationState(PoolIterativeAllocationState::create(pool));
365 }
366 return (boost::dynamic_pointer_cast<PoolIterativeAllocationState>(pool->getAllocationState()));
367}
368
369} // end of namespace isc::dhcp
370} // end of namespace isc
A generic exception that is thrown if a parameter given to a method is considered invalid in that con...
A generic exception that is thrown when an unexpected error condition occurs.
An exception that is thrown when allocation module fails (e.g.
Definition allocator.h:36
Base class for all address/prefix allocation algorithms.
Definition allocator.h:57
Lease::Type pool_type_
Defines pool type allocation.
Definition allocator.h:226
WeakSubnetPtr subnet_
Weak pointer to the subnet owning the allocator.
Definition allocator.h:232
static bool isValidPrefixPool(Allocator::PrefixLenMatchType prefix_length_match, PoolPtr pool, uint8_t hint_prefix_length)
Check if the pool matches the selection criteria relative to the provided hint prefix length.
Definition allocator.cc:39
Container for storing client class names.
Definition classify.h:108
static asiolink::IOAddress increasePrefix(const asiolink::IOAddress &prefix, const uint8_t prefix_len)
Returns the next prefix.
static asiolink::IOAddress increaseAddress(const asiolink::IOAddress &address, bool prefix, const uint8_t prefix_len)
Returns the next address or prefix.
IterativeAllocator(Lease::Type type, const WeakSubnetPtr &subnet)
Constructor.
static PoolIterativeAllocationStatePtr create(const PoolPtr &pool)
Factory function creating the state instance from pool.
static SubnetIterativeAllocationStatePtr create(const SubnetPtr &subnet)
Factory function creating the state instance from subnet.
#define isc_throw(type, stream)
A shortcut macro to insert known values into exception arguments.
boost::weak_ptr< Subnet > WeakSubnetPtr
Weak pointer to the Subnet.
Definition allocator.h:32
boost::shared_ptr< IdentifierBaseType > IdentifierBaseTypePtr
Shared pointer to a IdentifierType.
Definition duid.h:34
boost::shared_ptr< Pool > PoolPtr
a pointer to either IPv4 or IPv6 Pool
Definition pool.h:483
boost::shared_ptr< PoolIterativeAllocationState > PoolIterativeAllocationStatePtr
Type of the pointer to the PoolIterativeAllocationState.
boost::shared_ptr< SubnetIterativeAllocationState > SubnetIterativeAllocationStatePtr
Type of the pointer to the SubnetIterativeAllocationState.
boost::shared_ptr< Pool6 > Pool6Ptr
a pointer an IPv6 Pool
Definition pool.h:293
Defines the logger used by the top-level component of kea-lfc.
Type
Type of lease or pool.
Definition lease.h:46