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");
 
class Ipv4AddressGeneratorImpl
{
  public:
    Ipv4AddressGeneratorImpl();
    virtual ~Ipv4AddressGeneratorImpl();
 
    void Init(const Ipv4Address net, const Ipv4Mask mask, const Ipv4Address addr);
 
    Ipv4Address GetNetwork(const Ipv4Mask mask) const;
 
    Ipv4Address NextNetwork(const Ipv4Mask mask);
 
    void InitAddress(const Ipv4Address addr, const Ipv4Mask mask);
 
    Ipv4Address NextAddress(const Ipv4Mask mask);
 
    Ipv4Address GetAddress(const Ipv4Mask mask) const;
 
    void Reset();
 
    bool AddAllocated(const Ipv4Address addr);
 
    bool IsAddressAllocated(const Ipv4Address addr);
 
    bool IsNetworkAllocated(const Ipv4Address addr, const Ipv4Mask mask);
 
    void TestMode();
 
  private:
    static const uint32_t N_BITS = 32;                       
    static const uint32_t MOST_SIGNIFICANT_BIT = 0x80000000; 
 
    uint32_t MaskToIndex(Ipv4Mask mask) const;
 
    class NetworkState
    {
      public:
        uint32_t mask;    
        uint32_t shift;   
        uint32_t network; 
        uint32_t addr;    
        uint32_t addrMax; 
    };
 
    NetworkState m_netTable[N_BITS]; 
 
    class Entry
    {
      public:
        uint32_t addrLow;  
        uint32_t addrHigh; 
    };
 
    std::list<Entry> m_entries; 
    bool m_test;                
};
 
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 = Ipv4Address((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)
        {
            std::list<Entry>::iterator 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...");
 
    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));
        if (addr >= (*i).addrLow && addr <= (*i).addrHigh)
        {
            NS_LOG_LOGIC("Ipv4AddressGeneratorImpl::IsAddressAllocated(): Address Collision: "
                         << Ipv4Address(addr));
            return false;
        }
    }
    return true;
}
 
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);
 
    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));
        Ipv4Address low = Ipv4Address((*i).addrLow);
        Ipv4Address high = Ipv4Address((*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