ipv4-address-generator.cc

Go to the documentation of this file.

/*
 * Copyright (c) 2008 University of Washington
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
 
#include "ipv4-address-generator.h"
 
#include "ns3/abort.h"
#include "ns3/assert.h"
#include "ns3/log.h"
#include "ns3/simulation-singleton.h"
 
#include <list>
 
namespace ns3
{
 
NS_LOG_COMPONENT_DEFINE("Ipv4AddressGenerator");
 
/**
 * \ingroup address
 *
 * \brief Implementation class of Ipv4AddressGenerator
 * This generator assigns addresses sequentially from a provided
 * network address; used in topology code. It also keeps track of all
 * addresses assigned to perform duplicate detection.
 */
class Ipv4AddressGeneratorImpl
{
  public:
    Ipv4AddressGeneratorImpl();
    virtual ~Ipv4AddressGeneratorImpl();
 
    /**
     * \brief Initialise the base network, mask and address for the generator
     *
     * The first call to NextAddress() or GetAddress() will return the
     * value passed in.
     *
     * \param net The network for the base Ipv4Address
     * \param mask The network mask of the base Ipv4Address
     * \param addr The base address used for initialization
     */
    void Init(const Ipv4Address net, const Ipv4Mask mask, const Ipv4Address addr);
 
    /**
     * \brief Get the current network of the given Ipv4Mask
     *
     * Does not change the internal state; this just peeks at the current
     * network
     *
     * \param mask The Ipv4Mask for the current network
     * \returns the IPv4 address of the current network
     */
    Ipv4Address GetNetwork(const Ipv4Mask mask) const;
 
    /**
     * \brief Get the next network according to the given Ipv4Mask
     *
     * This operation is a pre-increment, meaning that the internal state
     * is changed before returning the new network address.
     *
     * This also resets the address to the base address that was
     * used for initialization.
     *
     * \param mask The Ipv4Mask used to set the next network
     * \returns the IPv4 address of the next network
     */
    Ipv4Address NextNetwork(const Ipv4Mask mask);
 
    /**
     * \brief Set the address for the given mask
     *
     * \param addr The address to set for the current mask
     * \param mask The Ipv4Mask whose address is to be set
     */
    void InitAddress(const Ipv4Address addr, const Ipv4Mask mask);
 
    /**
     * \brief Allocate the next Ipv4Address for the configured network and mask
     *
     * This operation is a post-increment, meaning that the first address
     * allocated will be the one that was initially configured.
     *
     * \param mask The Ipv4Mask for the current network
     * \returns the IPv4 address
     */
    Ipv4Address NextAddress(const Ipv4Mask mask);
 
    /**
     * \brief Get the Ipv4Address that will be allocated upon NextAddress ()
     *
     * Does not change the internal state; just is used to peek the next
     * address that will be allocated upon NextAddress ()
     *
     * \param mask The Ipv4Mask for the current network
     * \returns the IPv4 address
     */
    Ipv4Address GetAddress(const Ipv4Mask mask) const;
 
    /**
     * \brief Reset the networks and Ipv4Address to zero
     */
    void Reset();
 
    /**
     * \brief Add the Ipv4Address to the list of IPv4 entries
     *
     * Typically, this is used by external address allocators that want
     * to make use of this class's ability to track duplicates.  AddAllocated
     * is always called internally for any address generated by NextAddress ()
     *
     * \param addr The Ipv4Address to be added to the list of Ipv4 entries
     * \returns true on success
     */
    bool AddAllocated(const Ipv4Address addr);
 
    /**
     * \brief Check the Ipv4Address allocation in the list of IPv4 entries
     *
     * \param addr The Ipv4Address to be checked in the list of Ipv4 entries
     * \returns true if the address is already allocated
     */
    bool IsAddressAllocated(const Ipv4Address addr);
 
    /**
     * \brief Check if a network has already allocated addresses
     *
     * \param addr The Ipv4 network to be checked
     * \param mask The Ipv4 network mask
     * \returns true if the network is already allocated
     */
    bool IsNetworkAllocated(const Ipv4Address addr, const Ipv4Mask mask);
 
    /**
     * \brief Used to turn off fatal errors and assertions, for testing
     */
    void TestMode();
 
  private:
    static const uint32_t N_BITS = 32;                       //!< the number of bits in the address
    static const uint32_t MOST_SIGNIFICANT_BIT = 0x80000000; //!< MSB set to 1
 
    /**
     * \brief Create an index number for the network mask
     * \param mask the mask to index
     * \returns an index
     */
    uint32_t MaskToIndex(Ipv4Mask mask) const;
 
    /**
     * \brief This class holds the state for a given network
     */
    class NetworkState
    {
      public:
        uint32_t mask;    //!< the network mask
        uint32_t shift;   //!< a shift
        uint32_t network; //!< the network
        uint32_t addr;    //!< the address
        uint32_t addrMax; //!< the maximum address
    };
 
    NetworkState m_netTable[N_BITS]; //!< the available networks
 
    /**
     * \brief This class holds the allocated addresses
     */
    class Entry
    {
      public:
        uint32_t addrLow;  //!< the lowest allocated address
        uint32_t addrHigh; //!< the highest allocated address
    };
 
    std::list<Entry> m_entries; //!< contained of allocated addresses
    bool m_test;                //!< test mode (if true)
};
 
Ipv4AddressGeneratorImpl::Ipv4AddressGeneratorImpl()
    : m_entries(),
      m_test(false)
{
    NS_LOG_FUNCTION(this);
    Reset();
}
 
void
Ipv4AddressGeneratorImpl::Reset()
{
    NS_LOG_FUNCTION(this);
 
    uint32_t mask = 0;
    //
    // There are 32 possible masks in a 32-bit integer.  Two of these are illegal
    // for a network mask (0x00000000 and 0xffffffff).  Valid network masks
    // correspond to some nonzero number of high order bits set to one followed by
    // some nonzero number of lower order bits set to zero.
    //
    // We look at a network number as an n-bit number where n is defined as the
    // number of bits in each mask.  Allocating a new network number is simply
    // incrementing this number.
    //
    // In order to combine an allocated network number with an IP address, we have
    // to shift the network into the correct alignment with respect to its mask.
    // For example, a network mask of 0xff000000 admits the possibility of 256
    // different network numbers since there are eight bits available.  To create
    // IP addresses, we need to shift the network number counter left by 24 bits
    // to put it in correct alignment.  This leaves 24 bits left for addresses.
    // We make sure we don't overflow by saving a maximum address number which is
    // just the inverse of the mask (~mask).
    //
    for (uint32_t i = 0; i < N_BITS; ++i)
    {
        m_netTable[i].mask = mask;
        mask >>= 1;
        mask |= MOST_SIGNIFICANT_BIT;
        m_netTable[i].network = 1;
        m_netTable[i].addr = 1;
        m_netTable[i].addrMax = ~m_netTable[i].mask;
        m_netTable[i].shift = N_BITS - i;
    }
    m_entries.clear();
    m_test = false;
}
 
Ipv4AddressGeneratorImpl::~Ipv4AddressGeneratorImpl()
{
    NS_LOG_FUNCTION(this);
}
 
void
Ipv4AddressGeneratorImpl::Init(const Ipv4Address net, const Ipv4Mask mask, const Ipv4Address addr)
{
    NS_LOG_FUNCTION(this << net << mask << addr);
    //
    // We're going to be playing with the actual bits in the network and mask so
    // pull them out into ints.
    //
    uint32_t maskBits = mask.Get();
    uint32_t netBits = net.Get();
    uint32_t addrBits = addr.Get();
    //
    // Some quick reasonableness testing.
    //
    NS_ABORT_MSG_UNLESS((netBits & ~maskBits) == 0,
                        "Ipv4AddressGeneratorImpl::Init (): Inconsistent network and mask");
    NS_ABORT_MSG_UNLESS((addrBits & maskBits) == 0,
                        "Ipv4AddressGeneratorImpl::Init (): Inconsistent address and mask");
 
    //
    // Convert the network mask into an index into the network number table.
    // The network number comes in to us properly aligned for the mask and so
    // needs to be shifted right into the normalized position (lowest bit of the
    // network number at bit zero of the int that holds it).
    //
    uint32_t index = MaskToIndex(mask);
 
    m_netTable[index].network = netBits >> m_netTable[index].shift;
 
    NS_ABORT_MSG_UNLESS(addrBits <= m_netTable[index].addrMax,
                        "Ipv4AddressGeneratorImpl::Init(): Address overflow");
    m_netTable[index].addr = addrBits;
}
 
Ipv4Address
Ipv4AddressGeneratorImpl::GetNetwork(const Ipv4Mask mask) const
{
    NS_LOG_FUNCTION(this << mask);
 
    uint32_t index = MaskToIndex(mask);
    return Ipv4Address(m_netTable[index].network << m_netTable[index].shift);
}
 
Ipv4Address
Ipv4AddressGeneratorImpl::NextNetwork(const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(this << mask);
    //
    // The way this is expected to be used is that an address and network prefix
    // are initialized, and then NextAddress() is called repeatedly to set the
    // addresses on a given subnet.  The client will expect that the first
    // addresses will use the network prefix she used to initialize the generator
    // with.  After a subnet is assigned, the client will call NextNetwork to
    // get the network number of the next subnet.  This implies that that this
    // operation is a pre-increment.
    //
    uint32_t index = MaskToIndex(mask);
    ++m_netTable[index].network;
    return Ipv4Address(m_netTable[index].network << m_netTable[index].shift);
}
 
void
Ipv4AddressGeneratorImpl::InitAddress(const Ipv4Address addr, const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(this << addr << mask);
 
    uint32_t index = MaskToIndex(mask);
    uint32_t addrBits = addr.Get();
 
    NS_ABORT_MSG_UNLESS(addrBits <= m_netTable[index].addrMax,
                        "Ipv4AddressGeneratorImpl::InitAddress(): Address overflow");
    m_netTable[index].addr = addrBits;
}
 
Ipv4Address
Ipv4AddressGeneratorImpl::GetAddress(const Ipv4Mask mask) const
{
    NS_LOG_FUNCTION(this << mask);
 
    uint32_t index = MaskToIndex(mask);
 
    return Ipv4Address((m_netTable[index].network << m_netTable[index].shift) |
                       m_netTable[index].addr);
}
 
Ipv4Address
Ipv4AddressGeneratorImpl::NextAddress(const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(this << mask);
    //
    // The way this is expected to be used is that an address and network prefix
    // are initialized, and then NextAddress() is called repeatedly to set the
    // addresses on a given subnet.  The client will expect that the first address
    // she gets back is the one she used to initialize the generator with.  This
    // implies that this operation is a post-increment.
    //
    uint32_t index = MaskToIndex(mask);
 
    NS_ABORT_MSG_UNLESS(m_netTable[index].addr <= m_netTable[index].addrMax,
                        "Ipv4AddressGeneratorImpl::NextAddress(): Address overflow");
 
    Ipv4Address addr((m_netTable[index].network << m_netTable[index].shift) |
                     m_netTable[index].addr);
 
    ++m_netTable[index].addr;
    //
    // Make a note that we've allocated this address -- used for address collision
    // detection.
    //
    AddAllocated(addr);
    return addr;
}
 
bool
Ipv4AddressGeneratorImpl::AddAllocated(const Ipv4Address address)
{
    NS_LOG_FUNCTION(this << address);
 
    uint32_t addr = address.Get();
 
    NS_ABORT_MSG_UNLESS(
        addr,
        "Ipv4AddressGeneratorImpl::Add(): Allocating the broadcast address is not a good idea");
 
    std::list<Entry>::iterator i;
 
    for (i = m_entries.begin(); i != m_entries.end(); ++i)
    {
        NS_LOG_LOGIC("examine entry: " << Ipv4Address((*i).addrLow) << " to "
                                       << Ipv4Address((*i).addrHigh));
        //
        // First things first.  Is there an address collision -- that is, does the
        // new address fall in a previously allocated block of addresses.
        //
        if (addr >= (*i).addrLow && addr <= (*i).addrHigh)
        {
            NS_LOG_LOGIC(
                "Ipv4AddressGeneratorImpl::Add(): Address Collision: " << Ipv4Address(addr));
            if (!m_test)
            {
                NS_FATAL_ERROR(
                    "Ipv4AddressGeneratorImpl::Add(): Address Collision: " << Ipv4Address(addr));
            }
            return false;
        }
        //
        // If the new address is less than the lowest address in the current block,
        // and can't be merged into to the current block, then insert it as a new
        // block before the current block.
        //
        if (addr < (*i).addrLow - 1)
        {
            break;
        }
        //
        // If the new address fits at the end of the block, look ahead to the next
        // block and make sure it's not a collision there.  If we won't overlap, then
        // just extend the current block by one address.  We expect that completely
        // filled network ranges will be a fairly rare occurrence, so we don't worry
        // about collapsing address range blocks.
        //
        if (addr == (*i).addrHigh + 1)
        {
            auto j = i;
            ++j;
 
            if (j != m_entries.end())
            {
                if (addr == (*j).addrLow)
                {
                    NS_LOG_LOGIC("Ipv4AddressGeneratorImpl::Add(): "
                                 "Address Collision: "
                                 << Ipv4Address(addr));
                    if (!m_test)
                    {
                        NS_FATAL_ERROR("Ipv4AddressGeneratorImpl::Add(): Address Collision: "
                                       << Ipv4Address(addr));
                    }
                    return false;
                }
            }
 
            NS_LOG_LOGIC("New addrHigh = " << Ipv4Address(addr));
            (*i).addrHigh = addr;
            return true;
        }
        //
        // If we get here, we know that the next lower block of addresses couldn't
        // have been extended to include this new address since the code immediately
        // above would have been executed and that next lower block extended upward.
        // So we know it's safe to extend the current block down to include the new
        // address.
        //
        if (addr == (*i).addrLow - 1)
        {
            NS_LOG_LOGIC("New addrLow = " << Ipv4Address(addr));
            (*i).addrLow = addr;
            return true;
        }
    }
 
    Entry entry;
    entry.addrLow = entry.addrHigh = addr;
    m_entries.insert(i, entry);
    return true;
}
 
bool
Ipv4AddressGeneratorImpl::IsAddressAllocated(const Ipv4Address address)
{
    NS_LOG_FUNCTION(this << address);
 
    uint32_t addr = address.Get();
 
    NS_ABORT_MSG_UNLESS(
        addr,
        "Ipv4AddressGeneratorImpl::IsAddressAllocated(): Don't check for the broadcast address...");
 
    for (auto i = m_entries.begin(); i != m_entries.end(); ++i)
    {
        NS_LOG_LOGIC("examine entry: " << Ipv4Address((*i).addrLow) << " to "
                                       << Ipv4Address((*i).addrHigh));
        if (addr >= (*i).addrLow && addr <= (*i).addrHigh)
        {
            NS_LOG_LOGIC("Ipv4AddressGeneratorImpl::IsAddressAllocated(): Address Collision: "
                         << Ipv4Address(addr));
            return true;
        }
    }
    return false;
}
 
bool
Ipv4AddressGeneratorImpl::IsNetworkAllocated(const Ipv4Address address, const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(this << address << mask);
 
    NS_ABORT_MSG_UNLESS(
        address == address.CombineMask(mask),
        "Ipv4AddressGeneratorImpl::IsNetworkAllocated(): network address and mask don't match "
            << address << " " << mask);
 
    for (auto i = m_entries.begin(); i != m_entries.end(); ++i)
    {
        NS_LOG_LOGIC("examine entry: " << Ipv4Address((*i).addrLow) << " to "
                                       << Ipv4Address((*i).addrHigh));
        Ipv4Address low((*i).addrLow);
        Ipv4Address high((*i).addrHigh);
 
        if (address == low.CombineMask(mask) || address == high.CombineMask(mask))
        {
            NS_LOG_LOGIC(
                "Ipv4AddressGeneratorImpl::IsNetworkAllocated(): Network already allocated: "
                << address << " " << low << "-" << high);
            return false;
        }
    }
    return true;
}
 
void
Ipv4AddressGeneratorImpl::TestMode()
{
    NS_LOG_FUNCTION(this);
    m_test = true;
}
 
uint32_t
Ipv4AddressGeneratorImpl::MaskToIndex(Ipv4Mask mask) const
{
    NS_LOG_FUNCTION(this << mask);
 
    //
    // We've been given a mask that has a higher order bit set for each bit of the
    // network number.  In order to translate this mask into an index, we just need
    // to count the number of zero bits in the mask.  We do this in a loop in which
    // we shift the mask right until we find the first nonzero bit.  This tells us
    // the number of zero bits, and from this we infer the number of nonzero bits
    // which is the number of bits in the mask.
    //
    // We use the number of bits in the mask as the number of bits in the network
    // number and as the index into the network number state table.
    //
    uint32_t maskBits = mask.Get();
 
    for (uint32_t i = 0; i < N_BITS; ++i)
    {
        if (maskBits & 1)
        {
            uint32_t index = N_BITS - i;
            NS_ABORT_MSG_UNLESS(index > 0 && index < N_BITS,
                                "Ipv4AddressGenerator::MaskToIndex(): Illegal Mask");
            return index;
        }
        maskBits >>= 1;
    }
    NS_ASSERT_MSG(false, "Ipv4AddressGenerator::MaskToIndex(): Impossible");
    return 0;
}
 
void
Ipv4AddressGenerator::Init(const Ipv4Address net, const Ipv4Mask mask, const Ipv4Address addr)
{
    NS_LOG_FUNCTION(net << mask << addr);
 
    SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->Init(net, mask, addr);
}
 
Ipv4Address
Ipv4AddressGenerator::NextNetwork(const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(mask);
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->NextNetwork(mask);
}
 
Ipv4Address
Ipv4AddressGenerator::GetNetwork(const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(mask);
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->GetNetwork(mask);
}
 
void
Ipv4AddressGenerator::InitAddress(const Ipv4Address addr, const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(addr << mask);
 
    SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->InitAddress(addr, mask);
}
 
Ipv4Address
Ipv4AddressGenerator::GetAddress(const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(mask);
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->GetAddress(mask);
}
 
Ipv4Address
Ipv4AddressGenerator::NextAddress(const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(mask);
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->NextAddress(mask);
}
 
void
Ipv4AddressGenerator::Reset()
{
    NS_LOG_FUNCTION_NOARGS();
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->Reset();
}
 
bool
Ipv4AddressGenerator::AddAllocated(const Ipv4Address addr)
{
    NS_LOG_FUNCTION(addr);
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->AddAllocated(addr);
}
 
bool
Ipv4AddressGenerator::IsAddressAllocated(const Ipv4Address addr)
{
    NS_LOG_FUNCTION(addr);
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->IsAddressAllocated(addr);
}
 
bool
Ipv4AddressGenerator::IsNetworkAllocated(const Ipv4Address addr, const Ipv4Mask mask)
{
    NS_LOG_FUNCTION(addr << mask);
 
    return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->IsNetworkAllocated(addr, mask);
}
 
void
Ipv4AddressGenerator::TestMode()
{
    NS_LOG_FUNCTION_NOARGS();
 
    SimulationSingleton<Ipv4AddressGeneratorImpl>::Get()->TestMode();
}
 
} // namespace ns3