Kea  2.1.7-git
free_lease_queue.cc
Go to the documentation of this file.
1 // Copyright (C) 2020-2021 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>
10 
11 #include <boost/make_shared.hpp>
12 
13 #include <iostream>
14 #include <tuple>
15 #include <utility>
16 
17 using namespace isc::asiolink;
18 
19 namespace isc {
20 namespace dhcp {
21 
22 FreeLeaseQueue::FreeLeaseQueue()
23  : ranges_() {
24 }
25 
26 void
28  // If the container with ranges is empty, there are is no need for
29  // doing any checks. Let's just add the new range.
30  if (!ranges_.empty()) {
31  checkRangeOverlaps(range.start_, range.end_);
32  }
33  ranges_.insert(RangeDescriptor{range.start_, range.end_, 128, boost::make_shared<Leases>()});
34 }
35 
36 void
37 FreeLeaseQueue::addRange(const IOAddress& start, const IOAddress& end) {
38  addRange(AddressRange(start, end));
39 }
40 
41 void
43  if (!ranges_.empty()) {
44  auto last_addr = offsetAddress(range.end_, range.delegated_length_ - 1);
45  checkRangeOverlaps(range.start_, last_addr);
46  }
47  ranges_.insert(RangeDescriptor{range.start_, range.end_, range.delegated_length_,
48  boost::make_shared<Leases>()});
49 }
50 
51 void
52 FreeLeaseQueue::addRange(const asiolink::IOAddress& prefix, const uint8_t prefix_length,
53  const uint8_t delegated_length) {
54  addRange(PrefixRange(prefix, prefix_length, delegated_length));
55 }
56 
57 bool
59  // If there are no ranges defined, there is nothing to do.
60  if (ranges_.empty()) {
61  return (false);
62  }
63  // Find the beginning of the range which has the start address
64  // greater than the address we're appending.
65  auto lb = ranges_.upper_bound(address);
66  // If the range we found is the first one in the container
67  // there is no range matching our address because all existing
68  // ranges include higher addresses.
69  if (lb == ranges_.begin()) {
70  return (false);
71  }
72  --lb;
73  // Go one range back and see if our address is within its boundaries.
74  if ((lb->range_end_ < address) || (address < lb->range_start_)) {
75  return (false);
76  }
77  // Use the range we found and append the address to it.
78  AddressRange range(lb->range_start_, lb->range_end_);
79  append(range, address);
80 
81  // Everything is fine.
82  return (true);
83 }
84 
85 bool
86 FreeLeaseQueue::append(const IOAddress& prefix, const uint8_t delegated_length) {
87  // If there are no ranges defined, there is nothing to do.
88  if (ranges_.empty()) {
89  return (false);
90  }
91  // Find the beginning of the range which has the start address
92  // greater than the address we're appending.
93  auto lb = ranges_.upper_bound(prefix);
94  // If the range we found is the first one in the container
95  // there is no range matching our prefix because all existing
96  // ranges include higher addresses.
97  if (lb == ranges_.begin()) {
98  return (false);
99  }
100  --lb;
101  // Go one range back and see if our prefix is within its boundaries.
102  if ((lb->range_end_ < prefix) || (prefix < lb->range_start_) ||
103  (delegated_length != lb->delegated_length_)) {
104  return (false);
105  }
106  // Use the range we found and append the prefix to it.
107  PrefixRange range(lb->range_start_, lb->range_end_, lb->delegated_length_);
108  append(range, prefix);
109 
110  // Everything is fine.
111  return (true);
112 }
113 
114 void
115 FreeLeaseQueue::append(const AddressRange& range, const IOAddress& address) {
116  // Make sure the address is within the range boundaries.
117  checkRangeBoundaries(range, address);
118  auto cont = getLeases(range);
119  cont->insert(address);
120 }
121 
122 void
123 FreeLeaseQueue::append(const uint64_t range_index, const IOAddress& ip) {
124  auto desc = getRangeDescriptor(range_index);
125  if ((ip < desc.range_start_) || (desc.range_end_ < ip)) {
126  isc_throw(BadValue, ip << " is not within the range of " << desc.range_start_
127  << ":" << desc.range_end_);
128  }
129  desc.leases_->insert(ip);
130 }
131 
132 void
134  checkRangeBoundaries(range, prefix, true);
135  auto cont = getLeases(range);
136  cont->insert(prefix);
137 }
138 
139 bool
140 FreeLeaseQueue::use(const AddressRange& range, const IOAddress& address) {
141  checkRangeBoundaries(range, address);
142  auto cont = getLeases(range);
143  auto found = cont->find(address);
144  if (found != cont->end()) {
145  static_cast<void>(cont->erase(found));
146  return (true);
147  }
148  return (false);
149 }
150 
151 bool
152 FreeLeaseQueue::use(const PrefixRange& range, const IOAddress& prefix) {
153  checkRangeBoundaries(range, prefix, true);
154  auto cont = getLeases(range);
155  auto found = cont->find(prefix);
156  if (found != cont->end()) {
157  static_cast<void>(cont->erase(found));
158  return (true);
159  }
160  return (false);
161 }
162 
163 template<typename RangeType>
164 void
165 FreeLeaseQueue::checkRangeBoundaries(const RangeType& range, const IOAddress& ip,
166  const bool prefix) const {
167  if ((ip < range.start_) || (range.end_ < ip)) {
168  isc_throw(BadValue, (prefix ? "prefix " : "address ") << ip << " is not within the range of "
169  << range.start_ << ":" << range.end_);
170  }
171 }
172 
173 void
174 FreeLeaseQueue::checkRangeOverlaps(const IOAddress& start, const IOAddress& end) const {
175  // Get the next range in the container relative to the start of the new
176  // range. The upper_bound returns the range which starts after the start
177  // of the new range.
178  auto next_range = ranges_.lower_bound(start);
179  // Get the range the range that is before that one. It is also possible that
180  // there is no previous range in which case we default to end().
181  auto previous_range = ranges_.end();
182  // If the next range is at the beginning of the container there is no
183  // previous range.
184  if (next_range != ranges_.begin()) {
185  // This should work fine even if the next range is set to end(). We
186  // will get the range that is one position before end() and that
187  // should be the range that goes before the new one.
188  auto it = next_range;
189  --it;
190  previous_range = it;
191  }
192 
193  // Now that we have next and previous ranges set we should check that the
194  // new range we're adding does not overlap with them.
195 
196  // If the previous range exists, let's check that the start of the new
197  // range is neither within that range nor lower. Assuming that the ranges
198  // are constructed such that the end must be greater or equal the start
199  // it is sufficient to check that the start of the new range is not lower
200  // or equal the end of the previous range.
201  if ((previous_range != ranges_.end()) &&
202  (start <= previous_range->range_end_)) {
203  isc_throw(BadValue, "new address range " << start << ":" << end
204  << " overlaps with the existing range");
205  }
206 
207  // If the next range exists, let's check that the end of the new range
208  // is neither within that range nor higher.
209  if ((next_range != ranges_.end()) &&
210  (next_range->range_start_ <= end)) {
211  isc_throw(BadValue, "new address range " << start << ":" << end
212  << " overlaps with the existing range");
213  }
214 }
215 
216 
217 FreeLeaseQueue::LeasesPtr
218 FreeLeaseQueue::getLeases(const AddressRange& range) const {
219  auto cont = ranges_.find(range.start_);
220  if (cont == ranges_.end()) {
221  isc_throw(BadValue, "container for the specified address range " << range.start_
222  << ":" << range.end_ << " does not exist");
223  }
224  return (cont->leases_);
225 }
226 
227 FreeLeaseQueue::LeasesPtr
228 FreeLeaseQueue::getLeases(const PrefixRange& range) const {
229  auto cont = ranges_.find(range.start_);
230  if (cont == ranges_.end()) {
231  isc_throw(BadValue, "container for the specified prefix " << range.start_
232  << " and delegated length of " << static_cast<int>(range.delegated_length_)
233  << " does not exist");
234  }
235  return (cont->leases_);
236 }
237 
238 FreeLeaseQueue::RangeDescriptor
239 FreeLeaseQueue::getRangeDescriptor(const uint64_t range_index) const {
240  if (ranges_.get<2>().size() <= range_index) {
241  isc_throw(BadValue, "container for the specified range index " << range_index
242  << " does not exist");
243  }
244  auto cont = ranges_.get<2>().at(range_index);
245  return (cont);
246 }
247 
248 } // end of namespace isc::dhcp
249 } // end of namespace isc
Structure representing delegated prefix range.
Definition: ip_range.h:32
asiolink::IOAddress end_
IP address denoting the end of the address range.
Definition: ip_range.h:20
void addRange(const AddressRange &range)
Adds new address range to the queue.
bool use(const AddressRange &range, const asiolink::IOAddress &address)
Removes the specified address from the free addresses.
#define isc_throw(type, stream)
A shortcut macro to insert known values into exception arguments.
A generic exception that is thrown if a parameter given to a method is considered invalid in that con...
Defines the logger used by the top-level component of kea-lfc.
bool append(const asiolink::IOAddress &address)
Appends an address to the end of the queue for a range.
asiolink::IOAddress end_
IP address denoting the first address within the last prefix in the prefix range. ...
Definition: ip_range.h:37
Structure representing IP address range.
Definition: ip_range.h:16
asiolink::IOAddress start_
IP address denoting the start of the address range.
Definition: ip_range.h:18
asiolink::IOAddress start_
IP address denoting the start of the prefix range.
Definition: ip_range.h:34
uint8_t delegated_length_
Delegated prefix length.
Definition: ip_range.h:41