/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
* 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 <list>
#include "ns3/abort.h"
#include "ns3/assert.h"
#include "ns3/log.h"
#include "ns3/simulation-singleton.h"
#include "ipv4-address-generator.h"
namespace ns3 {
NS_LOG_COMPONENT_DEFINE ("Ipv4AddressGenerator");
/**
* \internal
* \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 ();
/**
* \internal
* \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);
/**
* \internal
* \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;
/**
* \internal
* \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);
/**
* \internal
* \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);
/**
* \internal
* \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);
/**
* \internal
* \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;
/**
* \internal
* \brief Reset the networks and Ipv4Address to zero
*/
void Reset (void);
/**
* \internal
* \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);
/**
* \internal
* \brief Used to turn off fatal errors and assertions, for testing
*/
void TestMode (void);
private:
static const uint32_t N_BITS = 32; //!< /internal the number of bits in the address
static const uint32_t MOST_SIGNIFICANT_BIT = 0x80000000; //!< /internal MSB set to 1
/**
* \internal
* \brief Create an index number for the network mask
* \param mask the mask to index
* \returns an index
*/
uint32_t MaskToIndex (Ipv4Mask mask) const;
/**
* \internal
* \brief This class holds the state for a given network
*/
class NetworkState
{
public:
uint32_t mask; //!< /internal the network mask
uint32_t shift; //!< /internal a shift
uint32_t network; //!< /internal the network
uint32_t addr; //!< /internal the address
uint32_t addrMax; //!< /internal the maximum address
};
NetworkState m_netTable[N_BITS]; //!< /internal the available networks
/**
* \internal
* \brief This class holds the allocated addresses
*/
class Entry
{
public:
uint32_t addrLow; //!< /internal the lowest allocated address
uint32_t addrHigh; //!< /internal the highest allocated address
};
std::list<Entry> m_entries; //!< /internal contained of allocated addresses
bool m_test; //!< /internal test mode (if true)
};
Ipv4AddressGeneratorImpl::Ipv4AddressGeneratorImpl ()
: m_entries (), m_test (false)
{
NS_LOG_FUNCTION (this);
Reset ();
}
void
Ipv4AddressGeneratorImpl::Reset (void)
{
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 = ~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;
return;
}
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 includ 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;
}
void
Ipv4AddressGeneratorImpl::TestMode (void)
{
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_NOARGS ();
SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->Init (net, mask, addr);
}
Ipv4Address
Ipv4AddressGenerator::NextNetwork (const Ipv4Mask mask)
{
NS_LOG_FUNCTION_NOARGS ();
return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->NextNetwork (mask);
}
Ipv4Address
Ipv4AddressGenerator::GetNetwork (const Ipv4Mask mask)
{
NS_LOG_FUNCTION_NOARGS ();
return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->GetNetwork (mask);
}
void
Ipv4AddressGenerator::InitAddress (
const Ipv4Address addr,
const Ipv4Mask mask)
{
NS_LOG_FUNCTION_NOARGS ();
SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->InitAddress (addr, mask);
}
Ipv4Address
Ipv4AddressGenerator::GetAddress (const Ipv4Mask mask)
{
NS_LOG_FUNCTION_NOARGS ();
return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->GetAddress (mask);
}
Ipv4Address
Ipv4AddressGenerator::NextAddress (const Ipv4Mask mask)
{
NS_LOG_FUNCTION_NOARGS ();
return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->NextAddress (mask);
}
void
Ipv4AddressGenerator::Reset (void)
{
NS_LOG_FUNCTION_NOARGS ();
return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->Reset ();
}
bool
Ipv4AddressGenerator::AddAllocated (const Ipv4Address addr)
{
NS_LOG_FUNCTION_NOARGS ();
return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->AddAllocated (addr);
}
void
Ipv4AddressGenerator::TestMode (void)
{
NS_LOG_FUNCTION_NOARGS ();
SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()
->TestMode ();
}
} // namespace ns3