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