Kea 2.6.0
flq_allocator.cc
Go to the documentation of this file.
1// Copyright (C) 2023-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
10#include <dhcpsrv/dhcpsrv_log.h>
14#include <dhcpsrv/subnet.h>
15#include <util/stopwatch.h>
16#include <unordered_set>
17
18using namespace isc::asiolink;
19using namespace isc::util;
20using namespace std;
21
22namespace {
25const string FLQ_OWNER = "flq";
26}
27
28namespace isc {
29namespace dhcp {
30
32 : Allocator(type, subnet), generator_() {
33 random_device rd;
34 generator_.seed(rd());
35}
36
38FreeLeaseQueueAllocator::pickAddressInternal(const ClientClasses& client_classes,
40 const IOAddress&) {
41 auto subnet = subnet_.lock();
42 auto const& pools = subnet->getPools(pool_type_);
43 if (pools.empty()) {
44 // No pools, no allocation.
46 }
47 // Let's first iterate over the pools and identify the ones that
48 // meet client class criteria and are not exhausted.
49 std::vector<uint64_t> available;
50 for (auto i = 0; i < pools.size(); ++i) {
51 // Check if the pool is allowed for the client's classes.
52 if (pools[i]->clientSupported(client_classes)) {
53 // Get or create the pool state.
54 auto pool_state = getPoolState(pools[i]);
55 if (!pool_state->exhausted()) {
56 // There are still available addresses in this pool.
57 available.push_back(i);
58 }
59 }
60 }
61 if (available.empty()) {
62 // No pool meets the client class criteria or all are exhausted.
64 }
65 // Get a random pool from the available ones.
66 auto const& pool = pools[available[getRandomNumber(available.size() - 1)]];
67
68 // Get or create the pool state.
69 auto pool_state = getPoolState(pool);
70
71 // The pool should still offer some leases.
72 auto free_lease = pool_state->offerFreeLease();
73 // It shouldn't happen, but let's be safe.
74 if (!free_lease.isV4Zero() && !free_lease.isV6Zero()) {
75 return (free_lease);
76 }
77 // No address available.
79}
80
82FreeLeaseQueueAllocator::pickPrefixInternal(const ClientClasses& client_classes,
83 Pool6Ptr& pool6,
85 PrefixLenMatchType prefix_length_match,
86 const IOAddress&,
87 uint8_t hint_prefix_length) {
88 auto subnet = subnet_.lock();
89 auto const& pools = subnet->getPools(pool_type_);
90 if (pools.empty()) {
91 // No pool, no allocation.
93 }
94 // Let's first iterate over the pools and identify the ones that
95 // meet client class criteria and are not exhausted.
96 std::vector<uint64_t> available;
97 for (auto i = 0; i < pools.size(); ++i) {
98 // Check if the pool is allowed for the client's classes.
99 if (pools[i]->clientSupported(client_classes)) {
100 if (!Allocator::isValidPrefixPool(prefix_length_match, pools[i],
101 hint_prefix_length)) {
102 continue;
103 }
104 // Get or create the pool state.
105 auto pool_state = getPoolState(pools[i]);
106 if (!pool_state->exhausted()) {
107 // There are still available prefixes in this pool.
108 available.push_back(i);
109 }
110 }
111 }
112 if (available.empty()) {
113 // No pool meets the client class criteria or all are exhausted.
115 }
116 // Get a random pool from the available ones.
117 auto const& pool = pools[available[getRandomNumber(available.size() - 1)]];
118 pool6 = boost::dynamic_pointer_cast<Pool6>(pool);
119 if (!pool6) {
120 // Something is gravely wrong here
121 isc_throw(Unexpected, "Wrong type of pool: "
122 << (pool)->toText()
123 << " is not Pool6");
124 }
125 // Get or create the pool state.
126 auto pool_state = getPoolState(pool);
127 // The pool should still offer some leases.
128 auto free_lease = pool_state->offerFreeLease();
129 // It shouldn't happen, but let's be safe.
130 if (!free_lease.isV6Zero()) {
131 return (free_lease);
132 }
133 // No prefix available.
135}
136
137void
138FreeLeaseQueueAllocator::initAfterConfigureInternal() {
139 auto subnet = subnet_.lock();
140 auto const& pools = subnet->getPools(pool_type_);
141 if (pools.empty()) {
142 // If there are no pools there is nothing to do.
143 return;
144 }
145 Lease4Collection leases4;
146 Lease6Collection leases6;
147 switch (pool_type_) {
148 case Lease::TYPE_V4:
149 leases4 = LeaseMgrFactory::instance().getLeases4(subnet->getID());
150 populateFreeAddressLeases(leases4, pools);
151 break;
152 case Lease::TYPE_NA:
153 case Lease::TYPE_TA:
154 leases6 = LeaseMgrFactory::instance().getLeases6(subnet->getID());
155 populateFreeAddressLeases(leases6, pools);
156 break;
157 case Lease::TYPE_PD:
158 leases6 = LeaseMgrFactory::instance().getLeases6(subnet->getID());
159 populateFreePrefixDelegationLeases(leases6, pools);
160 break;
161 default:
162 ;
163 }
164 // Install the callbacks for lease add, update and delete in the interface manager.
165 // These callbacks will ensure that we have up-to-date free lease queue.
166 auto& lease_mgr = LeaseMgrFactory::instance();
167 lease_mgr.registerCallback(TrackingLeaseMgr::TRACK_ADD_LEASE, FLQ_OWNER, subnet->getID(), pool_type_,
168 std::bind(&FreeLeaseQueueAllocator::addLeaseCallback, this,
169 std::placeholders::_1));
170 lease_mgr.registerCallback(TrackingLeaseMgr::TRACK_UPDATE_LEASE, FLQ_OWNER, subnet->getID(), pool_type_,
171 std::bind(&FreeLeaseQueueAllocator::updateLeaseCallback, this,
172 std::placeholders::_1));
173 lease_mgr.registerCallback(TrackingLeaseMgr::TRACK_DELETE_LEASE, FLQ_OWNER, subnet->getID(), pool_type_,
174 std::bind(&FreeLeaseQueueAllocator::deleteLeaseCallback, this,
175 std::placeholders::_1));
176}
177
178template<typename LeaseCollectionType>
179void
180FreeLeaseQueueAllocator::populateFreeAddressLeases(const LeaseCollectionType& leases,
181 const PoolCollection& pools) {
182 auto subnet = subnet_.lock();
184 .arg(subnet->toText());
185
186 Stopwatch stopwatch;
187
188 // Let's iterate over the lease queue and index them with the
189 // unordered_set. Also, elminate the expired leases and those
190 // in the expired-reclaimed state.
191 unordered_set<IOAddress, IOAddress::Hash> leased_addresses;
192 for (auto const& lease : leases) {
193 if ((lease->getType() == pool_type_) && (!lease->expired()) && (!lease->stateExpiredReclaimed())) {
194 leased_addresses.insert(lease->addr_);
195 }
196 }
197 // For each pool, check if the address is in the leases list.
198 size_t free_lease_count = 0;
199 for (auto const& pool : pools) {
200 // Create the pool permutation so the resulting lease queue is no
201 // particular order.
202 IPRangePermutation perm(AddressRange(pool->getFirstAddress(), pool->getLastAddress()));
203 auto pool_state = getPoolState(pool);
204 auto done = false;
205 while (!done) {
206 auto address = perm.next(done);
207 if (address.isV4Zero() || address.isV6Zero()) {
208 continue;
209 }
210 if (leased_addresses.count(address) == 0) {
211 // No lease for this address, so add it to the free leases queue.
212 pool_state->addFreeLease(address);
213 }
214 }
215 free_lease_count += pool_state->getFreeLeaseCount();
216 }
217
218 stopwatch.stop();
219
221 .arg(free_lease_count)
222 .arg(subnet->toText())
223 .arg(stopwatch.logFormatLastDuration());
224}
225
226void
227FreeLeaseQueueAllocator::populateFreePrefixDelegationLeases(const Lease6Collection& leases,
228 const PoolCollection& pools) {
229 auto subnet = subnet_.lock();
231 .arg(subnet->toText());
232
233 Stopwatch stopwatch;
234
235 // Let's iterate over the lease queue and index them with the
236 // unordered_set. Also, elminate the expired leases and those
237 // in the expired-reclaimed state.
238 unordered_set<IOAddress, IOAddress::Hash> leased_prefixes;
239 for (auto const& lease : leases) {
240 if ((lease->getType() == Lease::TYPE_PD) && (!lease->expired()) && (!lease->stateExpiredReclaimed())) {
241 leased_prefixes.insert(lease->addr_);
242 }
243 }
244 // For each pool, check if the prefix is in the leases list.
245 size_t free_lease_count = 0;
246 for (auto const& pool : pools) {
247 auto pool6 = boost::dynamic_pointer_cast<Pool6>(pool);
248 if (!pool6) {
249 continue;
250 }
251 // Create the pool permutation so the resulting lease queue is no
252 // particular order.
253 IPRangePermutation perm(PrefixRange(pool->getFirstAddress(),
254 pool->getLastAddress(),
255 pool6->getLength()));
256 auto pool_state = getPoolState(pool);
257 auto done = false;
258 while (!done) {
259 auto prefix = perm.next(done);
260 if (prefix.isV4Zero() || prefix.isV6Zero()) {
261 continue;
262 }
263 if (leased_prefixes.count(prefix) == 0) {
264 // No lease for this prefix, so add it to the free leases queue.
265 pool_state->addFreeLease(prefix);
266 }
267 }
268 free_lease_count += pool_state->getFreeLeaseCount();
269 }
270
271 stopwatch.stop();
272
274 .arg(free_lease_count)
275 .arg(subnet->toText())
276 .arg(stopwatch.logFormatLastDuration());
277}
278
280FreeLeaseQueueAllocator::getPoolState(const PoolPtr& pool) const {
281 if (!pool->getAllocationState()) {
282 pool->setAllocationState(PoolFreeLeaseQueueAllocationState::create(pool));
283 }
284 return (boost::dynamic_pointer_cast<PoolFreeLeaseQueueAllocationState>(pool->getAllocationState()));
285}
286
288FreeLeaseQueueAllocator::getLeasePool(const LeasePtr& lease) const {
289 auto subnet = subnet_.lock();
290 if (!subnet) {
291 return (PoolPtr());
292 }
293 auto pool = subnet->getPool(pool_type_, lease->addr_, false);
294 return (pool);
295}
296
297void
298FreeLeaseQueueAllocator::addLeaseCallback(LeasePtr lease) {
300 addLeaseCallbackInternal(lease);
301}
302
303void
304FreeLeaseQueueAllocator::addLeaseCallbackInternal(LeasePtr lease) {
305 if (lease->expired()) {
306 return;
307 }
308 auto pool = getLeasePool(lease);
309 if (!pool) {
310 return;
311 }
312 getPoolState(pool)->deleteFreeLease(lease->addr_);
313}
314
315void
316FreeLeaseQueueAllocator::updateLeaseCallback(LeasePtr lease) {
318 updateLeaseCallbackInternal(lease);
319}
320
321void
322FreeLeaseQueueAllocator::updateLeaseCallbackInternal(LeasePtr lease) {
323 auto pool = getLeasePool(lease);
324 if (!pool) {
325 return;
326 }
327 auto pool_state = getPoolState(pool);
328 if (lease->stateExpiredReclaimed() || (lease->expired())) {
329 pool_state->addFreeLease(lease->addr_);
330 } else {
331 pool_state->deleteFreeLease(lease->addr_);
332 }
333}
334
335void
336FreeLeaseQueueAllocator::deleteLeaseCallback(LeasePtr lease) {
338 deleteLeaseCallbackInternal(lease);
339}
340
341void
342FreeLeaseQueueAllocator::deleteLeaseCallbackInternal(LeasePtr lease) {
343 auto pool = getLeasePool(lease);
344 if (!pool) {
345 return;
346 }
347 getPoolState(pool)->addFreeLease(lease->addr_);
348}
349
350uint64_t
351FreeLeaseQueueAllocator::getRandomNumber(uint64_t limit) {
352 // Take the short path if there is only one number to randomize from.
353 if (limit == 0) {
354 return (0);
355 }
356 std::uniform_int_distribution<uint64_t> dist(0, limit);
357 return (dist(generator_));
358}
359
360} // end of namespace isc::dhcp
361} // end of namespace isc
A generic exception that is thrown when an unexpected error condition occurs.
Base class for all address/prefix allocation algorithms.
Definition: allocator.h:57
Lease::Type pool_type_
Defines pool type allocation.
Definition: allocator.h:226
std::mutex mutex_
The mutex to protect the allocated lease.
Definition: allocator.h:235
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
FreeLeaseQueueAllocator(Lease::Type type, const WeakSubnetPtr &subnet)
Constructor.
static TrackingLeaseMgr & instance()
Return current lease manager.
virtual Lease6Collection getLeases6(Lease::Type type, const DUID &duid, uint32_t iaid) const =0
Returns existing IPv6 leases for a given DUID+IA combination.
virtual Lease4Collection getLeases4(SubnetID subnet_id) const =0
Returns all IPv4 leases for the particular subnet identifier.
static PoolFreeLeaseQueueAllocationStatePtr create(const PoolPtr &pool)
Factory function creating the state instance from a pool.
Utility class to measure code execution times.
Definition: stopwatch.h:35
void stop()
Stops the stopwatch.
Definition: stopwatch.cc:34
std::string logFormatLastDuration() const
Returns the last measured duration in the format directly usable in log messages.
Definition: stopwatch.cc:74
#define isc_throw(type, stream)
A shortcut macro to insert known values into exception arguments.
#define LOG_INFO(LOGGER, MESSAGE)
Macro to conveniently test info output and log it.
Definition: macros.h:20
isc::log::Logger dhcpsrv_logger("dhcpsrv")
DHCP server library Logger.
Definition: dhcpsrv_log.h:56
boost::shared_ptr< PoolFreeLeaseQueueAllocationState > PoolFreeLeaseQueueAllocationStatePtr
Type of the pointer to the PoolFreeLeaseQueueAllocationState.
const isc::log::MessageID DHCPSRV_CFGMGR_FLQ_POPULATE_FREE_PREFIX_LEASES
boost::weak_ptr< Subnet > WeakSubnetPtr
Weak pointer to the Subnet.
Definition: allocator.h:32
const isc::log::MessageID DHCPSRV_CFGMGR_FLQ_POPULATE_FREE_ADDRESS_LEASES_DONE
std::vector< Lease6Ptr > Lease6Collection
A collection of IPv6 leases.
Definition: lease.h:670
const isc::log::MessageID DHCPSRV_CFGMGR_FLQ_POPULATE_FREE_PREFIX_LEASES_DONE
std::vector< PoolPtr > PoolCollection
a container for either IPv4 or IPv6 Pools
Definition: pool.h:486
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< Lease > LeasePtr
Pointer to the lease object.
Definition: lease.h:25
std::vector< Lease4Ptr > Lease4Collection
A collection of IPv4 leases.
Definition: lease.h:497
const isc::log::MessageID DHCPSRV_CFGMGR_FLQ_POPULATE_FREE_ADDRESS_LEASES
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
@ TYPE_TA
the lease contains temporary IPv6 address
Definition: lease.h:48
@ TYPE_PD
the lease contains IPv6 prefix (for prefix delegation)
Definition: lease.h:49
@ TYPE_V4
IPv4 lease.
Definition: lease.h:50
@ TYPE_NA
the lease contains non-temporary IPv6 address
Definition: lease.h:47
RAII lock object to protect the code in the same scope with a mutex.