addr_utilities.cc

Go to the documentation of this file.

// Copyright (C) 2012-2021 Internet Systems Consortium, Inc. ("ISC")
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

#include <config.h>

#include <asiolink/addr_utilities.h>
#include <exceptions/exceptions.h>

#include <vector>
#include <limits>
#include <string.h>

using namespace isc;
using namespace isc::asiolink;

namespace {

const uint32_t bitMask4[] = { 0xffffffff, 0x7fffffff, 0x3fffffff, 0x1fffffff,
                              0x0fffffff, 0x07ffffff, 0x03ffffff, 0x01ffffff,
                              0x00ffffff, 0x007fffff, 0x003fffff, 0x001fffff,
                              0x000fffff, 0x0007ffff, 0x0003ffff, 0x0001ffff,
                              0x0000ffff, 0x00007fff, 0x00003fff, 0x00001fff,
                              0x00000fff, 0x000007ff, 0x000003ff, 0x000001ff,
                              0x000000ff, 0x0000007f, 0x0000003f, 0x0000001f,
                              0x0000000f, 0x00000007, 0x00000003, 0x00000001,
                              0x00000000 };

const uint8_t bitMask6[]= { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };

const uint8_t revMask6[]= { 0xff, 0x7f, 0x3f, 0x1f, 0xf, 0x7, 0x3, 0x1 };


IOAddress firstAddrInPrefix6(const IOAddress& prefix, uint8_t len) {
    if (len > 128) {
        isc_throw(isc::BadValue,
                  "Too large netmask. 0..128 is allowed in IPv6");
    }

    // First we copy the whole address as 16 bytes.
    // We don't check that it is a valid IPv6 address and thus has
    // the required length because it is already checked by
    // the calling function.
    uint8_t packed[V6ADDRESS_LEN];
    memcpy(packed, &prefix.toBytes()[0], V6ADDRESS_LEN);

    // If the length is divisible by 8, it is simple. We just zero out the host
    // part. Otherwise we need to handle the byte that has to be partially
    // zeroed.
    if (len % 8 != 0) {

        // Get the appropriate mask. It has relevant bits (those that should
        // stay) set and irrelevant (those that should be wiped) cleared.
        uint8_t mask = bitMask6[len % 8];

        // Let's leave only whatever the mask says should not be cleared.
        packed[len / 8] = packed[len / 8] & mask;

        // Since we have just dealt with this byte, let's move the prefix length
        // to the beginning of the next byte (len is expressed in bits).
        len = (len / 8 + 1) * 8;
    }

    // Clear out the remaining bits.
    for (int i = len / 8; i < sizeof(packed); ++i) {
        packed[i] = 0x0;
    }

    // Finally, let's wrap this into nice and easy IOAddress object.
    return (IOAddress::fromBytes(AF_INET6, packed));
}

IOAddress firstAddrInPrefix4(const IOAddress& prefix, uint8_t len) {
    if (len > 32) {
        isc_throw(isc::BadValue, "Too large netmask. 0..32 is allowed in IPv4");
    }

    // We don't check that it is a valid IPv4 address and thus has
    // a required length of 4 bytes because it has been already
    // checked by the calling function.
    uint32_t addr = prefix.toUint32();
    return (IOAddress(addr & (~bitMask4[len])));
}

IOAddress lastAddrInPrefix4(const IOAddress& prefix, uint8_t len) {
    if (len > 32) {
        isc_throw(isc::BadValue, "Too large netmask. 0..32 is allowed in IPv4");
    }

    uint32_t addr = prefix.toUint32();
    return (IOAddress(addr | bitMask4[len]));
}

IOAddress lastAddrInPrefix6(const IOAddress& prefix, uint8_t len) {
    if (len > 128) {
        isc_throw(isc::BadValue,
                  "Too large netmask. 0..128 is allowed in IPv6");
    }

    // First we copy the whole address as 16 bytes.
    uint8_t packed[V6ADDRESS_LEN];
    memcpy(packed, &prefix.toBytes()[0], 16);

    // if the length is divisible by 8, it is simple. We just fill the host part
    // with ones. Otherwise we need to handle the byte that has to be partially
    // zeroed.
    if (len % 8 != 0) {
        // Get the appropriate mask. It has relevant bits (those that should
        // stay) set and irrelevant (those that should be set to 1) cleared.
        uint8_t mask = bitMask6[len % 8];

        // Let's set those irrelevant bits with 1. It would be perhaps
        // easier to not use negation here and invert bitMask6 content. However,
        // with this approach, we can use the same mask in first and last
        // address calculations.
        packed[len / 8] = packed[len / 8] | ~mask;

        // Since we have just dealt with this byte, let's move the prefix length
        // to the beginning of the next byte (len is expressed in bits).
        len = (len / 8 + 1) * 8;
    }

    // Finally set remaining bits to 1.
    for (int i = len / 8; i < sizeof(packed); ++i) {
        packed[i] = 0xff;
    }

    // Finally, let's wrap this into nice and easy IOAddress object.
    return (IOAddress::fromBytes(AF_INET6, packed));
}

}; // end of anonymous namespace

namespace isc {
namespace asiolink {

IOAddress firstAddrInPrefix(const IOAddress& prefix, uint8_t len) {
    if (prefix.isV4()) {
        return (firstAddrInPrefix4(prefix, len));

    } else {
        return (firstAddrInPrefix6(prefix, len));

    }
}

IOAddress lastAddrInPrefix(const IOAddress& prefix, uint8_t len) {
    if (prefix.isV4()) {
        return (lastAddrInPrefix4(prefix, len));

    } else {
        return (lastAddrInPrefix6(prefix, len));

    }
}

IOAddress getNetmask4(uint8_t len) {
    if (len > 32) {
        isc_throw(BadValue, "Invalid netmask size "
                  << static_cast<unsigned>(len) << ", allowed range is 0..32");
    }
    uint32_t x = ~bitMask4[len];

    return (IOAddress(x));
}

uint64_t
addrsInRange(const IOAddress& min, const IOAddress& max) {
    if (min.getFamily() != max.getFamily()) {
        isc_throw(BadValue, "Both addresses have to be the same family");
    }

    if (max < min) {
        isc_throw(BadValue, min.toText() << " must not be greater than "
                  << max.toText());
    }

    if (min.isV4()) {
        // Let's explicitly cast last_ and first_ (IOAddress). This conversion is
        // automatic, but let's explicitly cast it show that we moved to integer
        // domain and addresses are now substractable.
        uint64_t max_numeric = static_cast<uint64_t>(max.toUint32());
        uint64_t min_numeric = static_cast<uint64_t>(min.toUint32());

        // We can simply subtract the values. We need to increase the result
        // by one, as both min and max are included in the range. So even if
        // min == max, there's one address.
        return (max_numeric - min_numeric + 1);
    } else {

        // Calculating the difference in v6 is more involved. Let's subtract
        // one from the other. By subtracting min from max, we move the
        // [a, b] range to the [0, (b-a)] range. We don't care about the beginning
        // of the new range (it's always zero). The upper bound now specifies
        // the number of addresses minus one.
        IOAddress count = IOAddress::subtract(max, min);

        // There's one very special case. Someone is trying to check how many
        // IPv6 addresses are in IPv6 address space. He called this method
        // with ::, ffff:ffff:ffff:fffff:ffff:ffff:ffff:ffff. The diff is also
        // all 1s. Had we increased it by one, the address would flip to all 0s.
        // This will not happen in a real world. Apparently, unit-tests are
        // sometimes nastier then a real world.
        static IOAddress max6("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff");
        if (count == max6) {
            return (std::numeric_limits<uint64_t>::max());
        }

        // Increase it by one (a..a range still contains one address, even though
        // a subtracted from a is zero).
        count = IOAddress::increase(count);

        // We don't have uint128, so for anything greater than 2^64, we'll just
        // assume numeric_limits<uint64_t>::max. Let's do it the manual way.
        const std::vector<uint8_t>& bin(count.toBytes());

        // If any of the most significant 64 bits is set, we have more than
        // 2^64 addresses and can't represent it even on uint64_t.
        for (int i = 0 ; i < 8; i++) {
            if (bin[i]) {
                return (std::numeric_limits<uint64_t>::max());
            }
        }

        // Ok, we're good. The pool is sanely sized. It may be huge, but at least
        // that's something we can represent on uint64_t.
        uint64_t numeric = 0;
        for (int i = 8; i < 16; i++) {
            numeric <<= 8;
            numeric += bin[i];
        }

        return (numeric);
    }
}

int
prefixLengthFromRange(const IOAddress& min, const IOAddress& max) {
    if (min.getFamily() != max.getFamily()) {
        isc_throw(BadValue, "Both addresses have to be the same family");
    }

    if (max < min) {
        isc_throw(BadValue, min.toText() << " must not be greater than "
                  << max.toText());
    }

    if (min.isV4()) {
        // Get addresses as integers
        uint32_t max_numeric = max.toUint32();
        uint32_t min_numeric = min.toUint32();

        // Get the exclusive or which must be one of the bit masks
        // and the min must be at the beginning of the prefix
        // so it does not contribute to trailing ones.
        uint32_t xor_numeric = max_numeric ^ min_numeric;
        if ((min_numeric & ~xor_numeric) != min_numeric) {
            return (-1);
        }
        for (uint8_t prefix_len = 0; prefix_len <= 32; ++prefix_len) {
            if (xor_numeric == bitMask4[prefix_len]) {
                // Got it: the wanted value is also the index
                return (static_cast<int>(prefix_len));
            }
        }

        // If it was not found the range is not from a prefix / prefix_len
        return (-1);
    } else {
        // Get addresses as 16 bytes
        uint8_t min_packed[V6ADDRESS_LEN];
        memcpy(min_packed, &min.toBytes()[0], 16);
        uint8_t max_packed[V6ADDRESS_LEN];
        memcpy(max_packed, &max.toBytes()[0], 16);

        // Scan the exclusive or of addresses to find a difference
        int candidate = 128;
        bool zeroes = true;
        for (uint8_t i = 0; i < 16; ++i) {
            uint8_t xor_byte = min_packed[i] ^ max_packed[i];
            // The min must be at the beginning of the prefix
            // so it does not contribute to trailing ones.
            if ((min_packed[i] & ~xor_byte) != min_packed[i]) {
                return (-1);
            }
            if (zeroes) {
                // Skipping zero bits searching for one bits
                if (xor_byte == 0) {
                    continue;
                }
                // Found a one bit: note the fact
                zeroes = false;
                // Compare the exclusive or to masks
                for (uint8_t j = 0; j < 8; ++j) {
                    if (xor_byte == revMask6[j]) {
                        // Got it the prefix length: note it
                        candidate = static_cast<int>((i * 8) + j);
                    }
                }
                if (candidate == 128) {
                    // Not found? The range is not from a prefix / prefix_len
                    return (-1);
                }
            } else {
                // Checking that trailing bits are on bits
                if (xor_byte == 0xff) {
                    continue;
                }
                // Not all ones is bad
                return (-1);
            }
        }
        return (candidate);
    }
}

uint64_t prefixesInRange(const uint8_t pool_len, const uint8_t delegated_len) {
    if (delegated_len < pool_len) {
        return (0);
    }

    uint64_t count = delegated_len - pool_len;

    if (count == 0) {
        // If we want to delegate /64 out of /64 pool, we have only
        // one prefix.
        return (1);
    } else if (count >= 64) {
        // If the difference is greater than or equal 64, e.g. we want to
        // delegate /96 out of /16 pool, the number is bigger than we can
        // express, so we'll stick with maximum value of uint64_t.
        return (std::numeric_limits<uint64_t>::max());
    } else {
        // Now count specifies the exponent (e.g. if the difference between the
        // delegated and pool length is 4, we have 16 prefixes), so we need
        // to calculate 2^(count - 1)
        return ((static_cast<uint64_t>(2)) << (count - 1));
    }
}

IOAddress offsetAddress(const IOAddress& addr, uint64_t offset) {
    // There is nothing to do if the offset is 0.
    if (offset == 0) {
        return (addr);
    }

    // If this is an IPv4 address, then we utilize the conversion to uint32_t.
    if (addr.isV4()) {
        auto addr_uint32 = static_cast<uint64_t>(addr.toUint32());
        // If the result would exceed the maximum possible IPv4 address, let's return
        // the maximum IPv4 address.
        if (static_cast<uint64_t>(std::numeric_limits<uint32_t>::max() - addr_uint32) < offset) {
            return (IOAddress(std::numeric_limits<uint32_t>::max()));
        }
        return (IOAddress(static_cast<uint32_t>(addr_uint32 + offset)));
    }

    // This is IPv6 address. Let's first convert the offset value to network
    // byte order and store within the vector.
    std::vector<uint8_t> offset_bytes(8);
    for (int offset_idx = offset_bytes.size() - 1; offset_idx >= 0; --offset_idx) {
        offset_bytes[offset_idx] = static_cast<uint8_t>(offset & 0x00000000000000ff);
        offset = offset >> 8;
    }

    // Convert the IPv6 address to vector.
    auto addr_bytes = addr.toBytes();

    // Sum up the bytes.

    uint16_t carry = 0;
    for (int i = offset_bytes.size() - 1; (i >= 0) || (carry > 0); --i) {
        // Sum the bytes of the address, offset and the carry.
        uint16_t sum = static_cast<uint16_t>(addr_bytes[i+8]) + carry;

        // Protect against the case when we went beyond the offset vector and
        // we have only carry to add.
        if (i >= 0 ) {
            sum += static_cast<uint16_t>(offset_bytes[i]);
        }

        // Update the address byte.
        addr_bytes[i+8] = sum % 256;

        // Calculate the carry value.
        carry = sum / 256;
    }

    // Reconstruct IPv6 address from the vector.
    return (IOAddress::fromBytes(AF_INET6, &addr_bytes[0]));
}


};
};