Kea  2.3.9
addr_utilities.cc
Go to the documentation of this file.
1 // Copyright (C) 2012-2023 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 <exceptions/exceptions.h>
11 
12 #include <vector>
13 #include <limits>
14 #include <string.h>
15 
16 using namespace isc;
17 using namespace isc::asiolink;
18 using namespace isc::util;
19 
20 namespace {
21 
25 const uint32_t bitMask4[] = { 0xffffffff, 0x7fffffff, 0x3fffffff, 0x1fffffff,
26  0x0fffffff, 0x07ffffff, 0x03ffffff, 0x01ffffff,
27  0x00ffffff, 0x007fffff, 0x003fffff, 0x001fffff,
28  0x000fffff, 0x0007ffff, 0x0003ffff, 0x0001ffff,
29  0x0000ffff, 0x00007fff, 0x00003fff, 0x00001fff,
30  0x00000fff, 0x000007ff, 0x000003ff, 0x000001ff,
31  0x000000ff, 0x0000007f, 0x0000003f, 0x0000001f,
32  0x0000000f, 0x00000007, 0x00000003, 0x00000001,
33  0x00000000 };
34 
36 const uint8_t bitMask6[]= { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
37 
39 const uint8_t revMask6[]= { 0xff, 0x7f, 0x3f, 0x1f, 0xf, 0x7, 0x3, 0x1 };
40 
41 
49 IOAddress firstAddrInPrefix6(const IOAddress& prefix, uint8_t len) {
50  if (len > 128) {
52  "Too large netmask. 0..128 is allowed in IPv6");
53  }
54 
55  // First we copy the whole address as 16 bytes.
56  // We don't check that it is a valid IPv6 address and thus has
57  // the required length because it is already checked by
58  // the calling function.
59  uint8_t packed[V6ADDRESS_LEN];
60  memcpy(packed, &prefix.toBytes()[0], V6ADDRESS_LEN);
61 
62  // If the length is divisible by 8, it is simple. We just zero out the host
63  // part. Otherwise we need to handle the byte that has to be partially
64  // zeroed.
65  if (len % 8 != 0) {
66 
67  // Get the appropriate mask. It has relevant bits (those that should
68  // stay) set and irrelevant (those that should be wiped) cleared.
69  uint8_t mask = bitMask6[len % 8];
70 
71  // Let's leave only whatever the mask says should not be cleared.
72  packed[len / 8] = packed[len / 8] & mask;
73 
74  // Since we have just dealt with this byte, let's move the prefix length
75  // to the beginning of the next byte (len is expressed in bits).
76  len = (len / 8 + 1) * 8;
77  }
78 
79  // Clear out the remaining bits.
80  for (int i = len / 8; i < sizeof(packed); ++i) {
81  packed[i] = 0x0;
82  }
83 
84  // Finally, let's wrap this into nice and easy IOAddress object.
85  return (IOAddress::fromBytes(AF_INET6, packed));
86 }
87 
95 IOAddress firstAddrInPrefix4(const IOAddress& prefix, uint8_t len) {
96  if (len > 32) {
97  isc_throw(isc::BadValue, "Too large netmask. 0..32 is allowed in IPv4");
98  }
99 
100  // We don't check that it is a valid IPv4 address and thus has
101  // a required length of 4 bytes because it has been already
102  // checked by the calling function.
103  uint32_t addr = prefix.toUint32();
104  return (IOAddress(addr & (~bitMask4[len])));
105 }
106 
114 IOAddress lastAddrInPrefix4(const IOAddress& prefix, uint8_t len) {
115  if (len > 32) {
116  isc_throw(isc::BadValue, "Too large netmask. 0..32 is allowed in IPv4");
117  }
118 
119  uint32_t addr = prefix.toUint32();
120  return (IOAddress(addr | bitMask4[len]));
121 }
122 
130 IOAddress lastAddrInPrefix6(const IOAddress& prefix, uint8_t len) {
131  if (len > 128) {
133  "Too large netmask. 0..128 is allowed in IPv6");
134  }
135 
136  // First we copy the whole address as 16 bytes.
137  uint8_t packed[V6ADDRESS_LEN];
138  memcpy(packed, &prefix.toBytes()[0], 16);
139 
140  // if the length is divisible by 8, it is simple. We just fill the host part
141  // with ones. Otherwise we need to handle the byte that has to be partially
142  // zeroed.
143  if (len % 8 != 0) {
144  // Get the appropriate mask. It has relevant bits (those that should
145  // stay) set and irrelevant (those that should be set to 1) cleared.
146  uint8_t mask = bitMask6[len % 8];
147 
148  // Let's set those irrelevant bits with 1. It would be perhaps
149  // easier to not use negation here and invert bitMask6 content. However,
150  // with this approach, we can use the same mask in first and last
151  // address calculations.
152  packed[len / 8] = packed[len / 8] | ~mask;
153 
154  // Since we have just dealt with this byte, let's move the prefix length
155  // to the beginning of the next byte (len is expressed in bits).
156  len = (len / 8 + 1) * 8;
157  }
158 
159  // Finally set remaining bits to 1.
160  for (int i = len / 8; i < sizeof(packed); ++i) {
161  packed[i] = 0xff;
162  }
163 
164  // Finally, let's wrap this into nice and easy IOAddress object.
165  return (IOAddress::fromBytes(AF_INET6, packed));
166 }
167 
168 }; // end of anonymous namespace
169 
170 namespace isc {
171 namespace asiolink {
172 
173 IOAddress firstAddrInPrefix(const IOAddress& prefix, uint8_t len) {
174  if (prefix.isV4()) {
175  return (firstAddrInPrefix4(prefix, len));
176 
177  } else {
178  return (firstAddrInPrefix6(prefix, len));
179 
180  }
181 }
182 
183 IOAddress lastAddrInPrefix(const IOAddress& prefix, uint8_t len) {
184  if (prefix.isV4()) {
185  return (lastAddrInPrefix4(prefix, len));
186 
187  } else {
188  return (lastAddrInPrefix6(prefix, len));
189 
190  }
191 }
192 
193 IOAddress getNetmask4(uint8_t len) {
194  if (len > 32) {
195  isc_throw(BadValue, "Invalid netmask size "
196  << static_cast<unsigned>(len) << ", allowed range is 0..32");
197  }
198  uint32_t x = ~bitMask4[len];
199 
200  return (IOAddress(x));
201 }
202 
203 uint128_t
204 addrsInRange(const IOAddress& min, const IOAddress& max) {
205  if (min.getFamily() != max.getFamily()) {
206  isc_throw(BadValue, "Both addresses have to be the same family");
207  }
208 
209  if (max < min) {
210  isc_throw(BadValue, min.toText() << " must not be greater than "
211  << max.toText());
212  }
213 
214  if (min.isV4()) {
215  // Let's explicitly cast last_ and first_ (IOAddress). This conversion is
216  // automatic, but let's explicitly cast it show that we moved to integer
217  // domain and addresses are now substractable.
218  uint64_t max_numeric = static_cast<uint64_t>(max.toUint32());
219  uint64_t min_numeric = static_cast<uint64_t>(min.toUint32());
220 
221  // We can simply subtract the values. We need to increase the result
222  // by one, as both min and max are included in the range. So even if
223  // min == max, there's one address.
224  return (max_numeric - min_numeric + 1);
225  } else {
226 
227  // Calculating the difference in v6 is more involved. Let's subtract
228  // one from the other. By subtracting min from max, we move the
229  // [a, b] range to the [0, (b-a)] range. We don't care about the beginning
230  // of the new range (it's always zero). The upper bound now specifies
231  // the number of addresses minus one.
232  IOAddress count = IOAddress::subtract(max, min);
233 
234  // There's one very special case. Someone is trying to check how many
235  // IPv6 addresses are in IPv6 address space. He called this method
236  // with ::, ffff:ffff:ffff:fffff:ffff:ffff:ffff:ffff. The diff is also
237  // all 1s. Had we increased it by one, the address would flip to all 0s.
238  // This will not happen in a real world. Apparently, unit-tests are
239  // sometimes nastier then a real world.
240  static IOAddress max6("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff");
241  if (count == max6) {
242  return (std::numeric_limits<uint64_t>::max());
243  }
244 
245  // Increase it by one (a..a range still contains one address, even though
246  // a subtracted from a is zero).
247  count = IOAddress::increase(count);
248 
249  // We don't have uint128, so for anything greater than 2^64, we'll just
250  // assume numeric_limits<uint64_t>::max. Let's do it the manual way.
251  const std::vector<uint8_t>& bin(count.toBytes());
252 
253  // If any of the most significant 64 bits is set, we have more than
254  // 2^64 addresses and can't represent it even on uint64_t.
255  for (int i = 0 ; i < 8; i++) {
256  if (bin[i]) {
257  return (std::numeric_limits<uint64_t>::max());
258  }
259  }
260 
261  // Ok, we're good. The pool is sanely sized. It may be huge, but at least
262  // that's something we can represent on uint64_t.
263  uint64_t numeric = 0;
264  for (int i = 8; i < 16; i++) {
265  numeric <<= 8;
266  numeric += bin[i];
267  }
268 
269  return (numeric);
270  }
271 }
272 
273 int
274 prefixLengthFromRange(const IOAddress& min, const IOAddress& max) {
275  if (min.getFamily() != max.getFamily()) {
276  isc_throw(BadValue, "Both addresses have to be the same family");
277  }
278 
279  if (max < min) {
280  isc_throw(BadValue, min.toText() << " must not be greater than "
281  << max.toText());
282  }
283 
284  if (min.isV4()) {
285  // Get addresses as integers
286  uint32_t max_numeric = max.toUint32();
287  uint32_t min_numeric = min.toUint32();
288 
289  // Get the exclusive or which must be one of the bit masks
290  // and the min must be at the beginning of the prefix
291  // so it does not contribute to trailing ones.
292  uint32_t xor_numeric = max_numeric ^ min_numeric;
293  if ((min_numeric & ~xor_numeric) != min_numeric) {
294  return (-1);
295  }
296  for (uint8_t prefix_len = 0; prefix_len <= 32; ++prefix_len) {
297  if (xor_numeric == bitMask4[prefix_len]) {
298  // Got it: the wanted value is also the index
299  return (static_cast<int>(prefix_len));
300  }
301  }
302 
303  // If it was not found the range is not from a prefix / prefix_len
304  return (-1);
305  } else {
306  // Get addresses as 16 bytes
307  uint8_t min_packed[V6ADDRESS_LEN];
308  memcpy(min_packed, &min.toBytes()[0], 16);
309  uint8_t max_packed[V6ADDRESS_LEN];
310  memcpy(max_packed, &max.toBytes()[0], 16);
311 
312  // Scan the exclusive or of addresses to find a difference
313  int candidate = 128;
314  bool zeroes = true;
315  for (uint8_t i = 0; i < 16; ++i) {
316  uint8_t xor_byte = min_packed[i] ^ max_packed[i];
317  // The min must be at the beginning of the prefix
318  // so it does not contribute to trailing ones.
319  if ((min_packed[i] & ~xor_byte) != min_packed[i]) {
320  return (-1);
321  }
322  if (zeroes) {
323  // Skipping zero bits searching for one bits
324  if (xor_byte == 0) {
325  continue;
326  }
327  // Found a one bit: note the fact
328  zeroes = false;
329  // Compare the exclusive or to masks
330  for (uint8_t j = 0; j < 8; ++j) {
331  if (xor_byte == revMask6[j]) {
332  // Got it the prefix length: note it
333  candidate = static_cast<int>((i * 8) + j);
334  }
335  }
336  if (candidate == 128) {
337  // Not found? The range is not from a prefix / prefix_len
338  return (-1);
339  }
340  } else {
341  // Checking that trailing bits are on bits
342  if (xor_byte == 0xff) {
343  continue;
344  }
345  // Not all ones is bad
346  return (-1);
347  }
348  }
349  return (candidate);
350  }
351 }
352 
353 uint128_t prefixesInRange(const uint8_t pool_len, const uint8_t delegated_len) {
354  if (delegated_len < pool_len) {
355  return (0);
356  }
357 
358  uint8_t const count(delegated_len - pool_len);
359 
360  if (count == 128) {
361  // One off is the best we can do, unless we promote to uint256_t.
362  return uint128_t(-1);
363  }
364 
365  return (uint128_t(1) << count);
366 }
367 
368 IOAddress offsetAddress(const IOAddress& addr, uint64_t offset) {
369  // There is nothing to do if the offset is 0.
370  if (offset == 0) {
371  return (addr);
372  }
373 
374  // If this is an IPv4 address, then we utilize the conversion to uint32_t.
375  if (addr.isV4()) {
376  auto addr_uint32 = static_cast<uint64_t>(addr.toUint32());
377  // If the result would exceed the maximum possible IPv4 address, let's return
378  // the maximum IPv4 address.
379  if (static_cast<uint64_t>(std::numeric_limits<uint32_t>::max() - addr_uint32) < offset) {
380  return (IOAddress(std::numeric_limits<uint32_t>::max()));
381  }
382  return (IOAddress(static_cast<uint32_t>(addr_uint32 + offset)));
383  }
384 
385  // This is IPv6 address. Let's first convert the offset value to network
386  // byte order and store within the vector.
387  std::vector<uint8_t> offset_bytes(8);
388  for (int offset_idx = offset_bytes.size() - 1; offset_idx >= 0; --offset_idx) {
389  offset_bytes[offset_idx] = static_cast<uint8_t>(offset & 0x00000000000000ff);
390  offset = offset >> 8;
391  }
392 
393  // Convert the IPv6 address to vector.
394  auto addr_bytes = addr.toBytes();
395 
396  // Sum up the bytes.
397 
398  uint16_t carry = 0;
399  for (int i = offset_bytes.size() - 1; (i >= 0) || (carry > 0); --i) {
400  // Sum the bytes of the address, offset and the carry.
401  uint16_t sum = static_cast<uint16_t>(addr_bytes[i+8]) + carry;
402 
403  // Protect against the case when we went beyond the offset vector and
404  // we have only carry to add.
405  if (i >= 0 ) {
406  sum += static_cast<uint16_t>(offset_bytes[i]);
407  }
408 
409  // Update the address byte.
410  addr_bytes[i+8] = sum % 256;
411 
412  // Calculate the carry value.
413  carry = sum / 256;
414  }
415 
416  // Reconstruct IPv6 address from the vector.
417  return (IOAddress::fromBytes(AF_INET6, &addr_bytes[0]));
418 }
419 
420 
421 };
422 };
A generic exception that is thrown if a parameter given to a method is considered invalid in that con...
#define isc_throw(type, stream)
A shortcut macro to insert known values into exception arguments.
Definition: edns.h:19
boost::multiprecision::uint128_t uint128_t
Definition: bigints.h:21
Defines the logger used by the top-level component of kea-lfc.