A Discrete-Event Network Simulator
API
ipv6-address-generator.cc
Go to the documentation of this file.
1 /* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2008 University of Washington
4  * Copyright (c) 2011 Atishay Jain
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License version 2 as
8  * published by the Free Software Foundation;
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */
19 
20 #include <list>
21 #include "ns3/abort.h"
22 #include "ns3/assert.h"
23 #include "ns3/log.h"
24 #include "ns3/simulation-singleton.h"
25 #include "ipv6-address-generator.h"
26 
27 namespace ns3 {
28 
29 NS_LOG_COMPONENT_DEFINE ("Ipv6AddressGenerator");
30 
40 class Ipv6AddressGeneratorImpl
41 {
42 public:
43  Ipv6AddressGeneratorImpl ();
44  virtual ~Ipv6AddressGeneratorImpl ();
45 
56  void Init (const Ipv6Address net, const Ipv6Prefix prefix,
57  const Ipv6Address interfaceId);
58 
71  Ipv6Address NextNetwork (const Ipv6Prefix prefix);
72 
82  Ipv6Address GetNetwork (const Ipv6Prefix prefix) const;
83 
90  void InitAddress (const Ipv6Address interfaceId, const Ipv6Prefix prefix);
91 
101  Ipv6Address GetAddress (const Ipv6Prefix prefix) const;
102 
112  Ipv6Address NextAddress (const Ipv6Prefix prefix);
113 
117  void Reset (void);
118 
129  bool AddAllocated (const Ipv6Address addr);
130 
137  bool IsAddressAllocated (const Ipv6Address addr);
138 
146  bool IsNetworkAllocated (const Ipv6Address addr, const Ipv6Prefix prefix);
147 
151  void TestMode (void);
152 
153 private:
154  static const uint32_t N_BITS = 128;
155  static const uint32_t MOST_SIGNIFICANT_BIT = 0x80;
156 
162  uint32_t PrefixToIndex (Ipv6Prefix prefix) const;
163 
167  class NetworkState
168  {
169 public:
170  uint8_t prefix[16];
171  uint32_t shift;
172  uint8_t network[16];
173  uint8_t addr[16];
174  uint8_t addrMax[16];
175  };
176 
177  NetworkState m_netTable[N_BITS];
178 
182  class Entry
183  {
184 public:
185  uint8_t addrLow[16];
186  uint8_t addrHigh[16];
187  };
188 
189  std::list<Entry> m_entries;
190  Ipv6Address m_base;
191  bool m_test;
192 };
193 
194 Ipv6AddressGeneratorImpl::Ipv6AddressGeneratorImpl ()
195  : m_entries (),
196  m_base ("::1"),
197  m_test (false)
198 {
199  NS_LOG_FUNCTION (this);
200  Reset ();
201 }
202 
203 void
205 {
206  NS_LOG_FUNCTION (this);
207 
208  uint8_t prefix[16] = { 0};
209 
210  for (uint32_t i = 0; i < N_BITS; ++i)
211  {
212  for (uint32_t j = 0; j < 16; ++j)
213  {
214  m_netTable[i].prefix[j] = prefix[j];
215  }
216  for (uint32_t j = 0; j < 15; ++j)
217  {
218  prefix[15 - j] >>= 1;
219  prefix[15 - j] |= (prefix[15 - j - 1] & 1);
220  }
221  prefix[0] |= MOST_SIGNIFICANT_BIT;
222  for (uint32_t j = 0; j < 15; ++j)
223  {
224  m_netTable[i].network[j] = 0;
225  }
226  m_netTable[i].network[15] = 1;
227  for (uint32_t j = 0; j < 15; ++j)
228  {
229  m_netTable[i].addr[j] = 0;
230  }
231  m_netTable[i].addr[15] = 1;
232  for (uint32_t j = 0; j < 16; ++j)
233  {
234  m_netTable[i].addrMax[j] = ~prefix[j];
235  }
236  m_netTable[i].shift = N_BITS - i;
237  }
238  m_entries.clear ();
239  m_base = Ipv6Address ("::1");
240  m_test = false;
241 }
242 
243 Ipv6AddressGeneratorImpl::~Ipv6AddressGeneratorImpl ()
244 {
245  NS_LOG_FUNCTION (this);
246 }
247 
248 void
249 Ipv6AddressGeneratorImpl::Init (
250  const Ipv6Address net,
251  const Ipv6Prefix prefix,
252  const Ipv6Address interfaceId)
253 {
254  NS_LOG_FUNCTION (this << net << prefix << interfaceId);
255 
256  m_base = interfaceId;
257  //
258  // We're going to be playing with the actual bits in the network and prefix so
259  // pull them out into ints.
260  //
261  uint8_t prefixBits[16];
262  prefix.GetBytes (prefixBits);
263  uint8_t netBits[16];
264  net.GetBytes (netBits);
265  uint8_t interfaceIdBits[16];
266  interfaceId.GetBytes (interfaceIdBits);
267  //
268  // Some quick reasonableness testing.
269  //
270  // Convert the network prefix into an index into the network number table.
271  // The network number comes in to us properly aligned for the prefix and so
272  // needs to be shifted right into the normalized position (lowest bit of the
273  // network number at bit zero of the int that holds it).
274  //
275  uint32_t index = PrefixToIndex (prefix);
276  NS_LOG_DEBUG ("Index " << index);
277  uint32_t a = m_netTable[index].shift / 8;
278  uint32_t b = m_netTable[index].shift % 8;
279  for (int32_t j = 15 - a; j >= 0; j--)
280  {
281  m_netTable[index].network[j + a] = netBits[j];
282  }
283  for (uint32_t j = 0; j < a; j++)
284  {
285  m_netTable[index].network[j] = 0;
286  }
287  for (uint32_t j = 15; j >= a; j--)
288  {
289  m_netTable[index].network[j] = m_netTable[index].network[j] >> b;
290  m_netTable[index].network[j] |= m_netTable[index].network[j - 1] << (8 - b);
291  }
292  for (int32_t j = 0; j < 16; j++)
293  {
294  m_netTable[index].addr[j] = interfaceIdBits[j];
295  }
296  return;
297 }
298 
299 Ipv6Address
300 Ipv6AddressGeneratorImpl::GetNetwork (
301  const Ipv6Prefix prefix) const
302 {
303  NS_LOG_FUNCTION (this);
304  uint8_t nw[16] = { 0 };
305  uint32_t index = PrefixToIndex (prefix);
306  uint32_t a = m_netTable[index].shift / 8;
307  uint32_t b = m_netTable[index].shift % 8;
308  for (uint32_t j = 0; j < 16 - a; ++j)
309  {
310  nw[j] = m_netTable[index].network[j + a];
311  }
312  for (uint32_t j = 0; j < 15; j++)
313  {
314  nw[j] = nw[j] << b;
315  nw[j] |= nw[j + 1] >> (8 - b);
316  }
317  nw[15] = nw[15] << b;
318 
319  return Ipv6Address (nw);
320 }
321 
322 Ipv6Address
323 Ipv6AddressGeneratorImpl::NextNetwork (
324  const Ipv6Prefix prefix)
325 {
326  NS_LOG_FUNCTION (this);
327 
328  uint32_t index = PrefixToIndex (prefix);
329  // Reset the base to what was initialized
330  uint8_t interfaceIdBits[16];
331  m_base.GetBytes (interfaceIdBits);
332  for (int32_t j = 0; j < 16; j++)
333  {
334  m_netTable[index].addr[j] = interfaceIdBits[j];
335  }
336 
337  for (int32_t j = 15; j >= 0; j--)
338  {
339  if (m_netTable[index].network[j] < 0xff)
340  {
341  ++m_netTable[index].network[j];
342  break;
343  }
344  else
345  {
346  ++m_netTable[index].network[j];
347  }
348  }
349 
350  uint8_t nw[16];
351  uint32_t a = m_netTable[index].shift / 8;
352  uint32_t b = m_netTable[index].shift % 8;
353  for (uint32_t j = 0; j < 16 - a; ++j)
354  {
355  nw[j] = m_netTable[index].network[j + a];
356  }
357  for (uint32_t j = 16 - a; j < 16; ++j)
358  {
359  nw[j] = 0;
360  }
361  for (uint32_t j = 0; j < 15; j++)
362  {
363  nw[j] = nw[j] << b;
364  nw[j] |= nw[j + 1] >> (8 - b);
365  }
366  nw[15] = nw[15] << b;
367 
368  return Ipv6Address (nw);
369 
370 }
371 
372 void
373 Ipv6AddressGeneratorImpl::InitAddress (
374  const Ipv6Address interfaceId,
375  const Ipv6Prefix prefix)
376 {
377  NS_LOG_FUNCTION (this);
378 
379  uint32_t index = PrefixToIndex (prefix);
380  uint8_t interfaceIdBits[16];
381  interfaceId.GetBytes (interfaceIdBits);
382 
383  for (uint32_t j = 0; j < 16; ++j)
384  {
385  m_netTable[index].addr[j] = interfaceIdBits[j];
386  }
387 }
388 
389 Ipv6Address
390 Ipv6AddressGeneratorImpl::GetAddress (const Ipv6Prefix prefix) const
391 {
392  NS_LOG_FUNCTION (this);
393 
394  uint32_t index = PrefixToIndex (prefix);
395 
396  uint8_t nw[16] = { 0 };
397  uint32_t a = m_netTable[index].shift / 8;
398  uint32_t b = m_netTable[index].shift % 8;
399  for (uint32_t j = 0; j < 16 - a; ++j)
400  {
401  nw[j] = m_netTable[index].network[j + a];
402  }
403  for (uint32_t j = 0; j < 15; j++)
404  {
405  nw[j] = nw[j] << b;
406  nw[j] |= nw[j + 1] >> (8 - b);
407  }
408  nw[15] = nw[15] << b;
409  for (uint32_t j = 0; j < 16; j++)
410  {
411  nw[j] |= m_netTable[index].addr[j];
412  }
413 
414  return Ipv6Address (nw);
415 }
416 
417 Ipv6Address
418 Ipv6AddressGeneratorImpl::NextAddress (const Ipv6Prefix prefix)
419 {
420  NS_LOG_FUNCTION (this);
421 
422  uint32_t index = PrefixToIndex (prefix);
423 
424  uint8_t ad[16] = { 0 };
425  uint32_t a = m_netTable[index].shift / 8;
426  uint32_t b = m_netTable[index].shift % 8;
427  for (uint32_t j = 0; j < 16 - a; ++j)
428  {
429  ad[j] = m_netTable[index].network[j + a];
430  }
431  for (uint32_t j = 0; j < 15; j++)
432  {
433  ad[j] = ad[j] << b;
434  ad[j] |= ad[j + 1] >> (8 - b);
435  }
436  ad[15] = ad[15] << b;
437  for (uint32_t j = 0; j < 16; j++)
438  {
439  ad[j] |= m_netTable[index].addr[j];
440  }
441  Ipv6Address addr = Ipv6Address (ad);
442 
443  for (int32_t j = 15; j >= 0; j--)
444  {
445  if (m_netTable[index].addr[j] < 0xff)
446  {
447  ++m_netTable[index].addr[j];
448  break;
449  }
450  else
451  {
452  ++m_netTable[index].addr[j];
453  }
454  }
455 
456  //
457  // Make a note that we've allocated this address -- used for address collision
458  // detection.
459  //
460  AddAllocated (addr);
461  return addr;
462 }
463 
464 bool
465 Ipv6AddressGeneratorImpl::AddAllocated (const Ipv6Address address)
466 {
467  NS_LOG_FUNCTION (this << address);
468 
469  uint8_t addr[16];
470  address.GetBytes (addr);
471 
472  std::list<Entry>::iterator i;
473 
474  for (i = m_entries.begin (); i != m_entries.end (); ++i)
475  {
476  NS_LOG_LOGIC ("examine entry: " << Ipv6Address ((*i).addrLow) <<
477  " to " << Ipv6Address ((*i).addrHigh));
478  //
479  // First things first. Is there an address collision -- that is, does the
480  // new address fall in a previously allocated block of addresses.
481  //
482  if (!(Ipv6Address (addr) < Ipv6Address ((*i).addrLow))
483  && ((Ipv6Address (addr) < Ipv6Address ((*i).addrHigh))
484  || (Ipv6Address (addr) == Ipv6Address ((*i).addrHigh))))
485  {
486  NS_LOG_LOGIC ("Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address (addr));
487  if (!m_test)
488  {
489  NS_FATAL_ERROR ("Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address (addr));
490  }
491  return false;
492  }
493  //
494  // If the new address is less than the lowest address in the current
495  // block and can't be merged into to the current block, then insert it
496  // as a new block before the current block.
497  //
498  uint8_t taddr[16];
499  for (uint32_t j = 0; j < 16; j++)
500  {
501  taddr[j] = (*i).addrLow[j];
502  }
503  taddr[15] -= 1;
504  if (Ipv6Address (addr) < Ipv6Address (taddr))
505  {
506  break;
507  }
508  //
509  // If the new address fits at the end of the block, look ahead to the next
510  // block and make sure it's not a collision there. If we won't overlap,
511  // then just extend the current block by one address. We expect that
512  // completely filled network ranges will be a fairly rare occurrence,
513  // so we don't worry about collapsing address range blocks.
514  //
515  for (uint32_t j = 0; j < 16; j++)
516  {
517  taddr[j] = (*i).addrLow[j];
518  }
519  taddr[15] += 1;
520  if (Ipv6Address (addr) == Ipv6Address (taddr))
521  {
522  std::list<Entry>::iterator j = i;
523  ++j;
524 
525  if (j != m_entries.end ())
526  {
527  if (Ipv6Address (addr) == Ipv6Address ((*j).addrLow))
528  {
529  NS_LOG_LOGIC ("Ipv6AddressGeneratorImpl::Add(): "
530  "Address Collision: " << Ipv6Address (addr));
531  if (!m_test)
532  {
533  NS_FATAL_ERROR ("Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address (addr));
534  }
535  return false;
536  }
537  }
538 
539  NS_LOG_LOGIC ("New addrHigh = " << Ipv6Address (addr));
540  for (uint32_t j = 0; j < 16; j++)
541  {
542  (*i).addrHigh[j] = addr[j];
543  }
544  return true;
545  }
546  //
547  // If we get here, we know that the next lower block of addresses
548  // couldn't have been extended to include this new address since the
549  // code immediately above would have been executed and that next lower
550  // block extended upward. So we know it's safe to extend the current
551  // block down to include the new address.
552  //
553  for (uint32_t j = 0; j < 16; j++)
554  {
555  taddr[j] = (*i).addrLow[j];
556  }
557  taddr[15] -= 1;
558  if ((Ipv6Address (addr) == Ipv6Address (taddr)))
559  {
560  NS_LOG_LOGIC ("New addrLow = " << Ipv6Address (addr));
561  for (uint32_t j = 0; j < 16; j++)
562  {
563  (*i).addrLow[j] = addr[j];
564  }
565  return true;
566  }
567  }
568 
569  Entry entry;
570  for (uint32_t j = 0; j < 16; j++)
571  {
572  entry.addrLow[j] = entry.addrHigh[j] = addr[j];
573  }
574  m_entries.insert (i, entry);
575  return true;
576 }
577 
578 bool
579 Ipv6AddressGeneratorImpl::IsAddressAllocated (const Ipv6Address address)
580 {
581  NS_LOG_FUNCTION (this << address);
582 
583  uint8_t addr[16];
584  address.GetBytes (addr);
585 
586  std::list<Entry>::iterator i;
587 
588  for (i = m_entries.begin (); i != m_entries.end (); ++i)
589  {
590  NS_LOG_LOGIC ("examine entry: " << Ipv6Address ((*i).addrLow) <<
591  " to " << Ipv6Address ((*i).addrHigh));
592 
593  if (!(Ipv6Address (addr) < Ipv6Address ((*i).addrLow))
594  && ((Ipv6Address (addr) < Ipv6Address ((*i).addrHigh))
595  || (Ipv6Address (addr) == Ipv6Address ((*i).addrHigh))))
596  {
597  NS_LOG_LOGIC ("Ipv6AddressGeneratorImpl::IsAddressAllocated(): Address Collision: " << Ipv6Address (addr));
598  return false;
599  }
600  }
601  return true;
602 }
603 
604 bool
605 Ipv6AddressGeneratorImpl::IsNetworkAllocated (const Ipv6Address address, const Ipv6Prefix prefix)
606 {
607  NS_LOG_FUNCTION (this << address << prefix);
608 
609  Ipv6Address addr = address;
610  NS_ABORT_MSG_UNLESS (address == addr.CombinePrefix (prefix),
611  "Ipv6AddressGeneratorImpl::IsNetworkAllocated(): network address and mask don't match " << address << " " << prefix);
612 
613  std::list<Entry>::iterator i;
614 
615  for (i = m_entries.begin (); i != m_entries.end (); ++i)
616  {
617  NS_LOG_LOGIC ("examine entry: " << Ipv6Address ((*i).addrLow) << " to " << Ipv6Address ((*i).addrHigh));
618  Ipv6Address low = Ipv6Address ((*i).addrLow);
619  Ipv6Address high = Ipv6Address ((*i).addrHigh);
620 
621  if (address == low.CombinePrefix (prefix) || address == high.CombinePrefix (prefix))
622  {
623  NS_LOG_LOGIC ("Ipv6AddressGeneratorImpl::IsNetworkAllocated(): Network already allocated: " <<
624  address << " " << low << "-" << high);
625  return false;
626  }
627 
628  }
629  return true;
630 }
631 
632 
633 void
634 Ipv6AddressGeneratorImpl::TestMode (void)
635 {
636  NS_LOG_FUNCTION (this);
637  m_test = true;
638 }
639 
640 uint32_t
641 Ipv6AddressGeneratorImpl::PrefixToIndex (Ipv6Prefix prefix) const
642 {
643  //
644  // We've been given a prefix that has a higher order bit set for each bit of
645  // the network number. In order to translate this prefix into an index,
646  // we just need to count the number of zero bits in the prefix. We do this
647  // in a loop in which we shift the prefix right until we find the first
648  // nonzero bit. This tells us the number of zero bits, and from this we
649  // infer the number of nonzero bits which is the number of bits in the prefix.
650  //
651  // We use the number of bits in the prefix as the number of bits in the
652  // network number and as the index into the network number state table.
653  //
654  uint8_t prefixBits[16];
655  prefix.GetBytes (prefixBits);
656 
657  for (int32_t i = 15; i >= 0; --i)
658  {
659  for (uint32_t j = 0; j < 8; ++j)
660  {
661  if (prefixBits[i] & 1)
662  {
663  uint32_t index = N_BITS - (15 - i) * 8 - j;
664  NS_ABORT_MSG_UNLESS (index > 0 && index < N_BITS, "Ip64AddressGenerator::PrefixToIndex(): Illegal Prefix");
665  return index;
666  }
667  prefixBits[i] >>= 1;
668  }
669  }
670  NS_ASSERT_MSG (false, "Ipv6AddressGenerator::PrefixToIndex(): Impossible");
671  return 0;
672 }
673 
674 void
676  const Ipv6Address net,
677  const Ipv6Prefix prefix,
678  const Ipv6Address interfaceId)
679 {
681 
683  ->Init (net, prefix, interfaceId);
684 }
685 
686 Ipv6Address
687 Ipv6AddressGenerator::NextNetwork (const Ipv6Prefix prefix)
688 {
690 
692  ->NextNetwork (prefix);
693 }
694 
695 Ipv6Address
696 Ipv6AddressGenerator::GetNetwork (const Ipv6Prefix prefix)
697 {
699 
701  ->GetNetwork (prefix);
702 }
703 
704 void
706  const Ipv6Address interfaceId,
707  const Ipv6Prefix prefix)
708 {
710 
712  ->InitAddress (interfaceId, prefix);
713 }
714 
715 Ipv6Address
716 Ipv6AddressGenerator::GetAddress (const Ipv6Prefix prefix)
717 {
719 
721  ->GetAddress (prefix);
722 }
723 
724 Ipv6Address
725 Ipv6AddressGenerator::NextAddress (const Ipv6Prefix prefix)
726 {
728 
730  ->NextAddress (prefix);
731 }
732 
733 void
735 {
737 
739  ->Reset ();
740 }
741 
742 bool
743 Ipv6AddressGenerator::AddAllocated (const Ipv6Address addr)
744 {
746 
748  ->AddAllocated (addr);
749 }
750 
751 bool
752 Ipv6AddressGenerator::IsAddressAllocated (const Ipv6Address addr)
753 {
755 
757  ->IsAddressAllocated (addr);
758 }
759 
760 bool
761 Ipv6AddressGenerator::IsNetworkAllocated (const Ipv6Address addr, const Ipv6Prefix prefix)
762 {
764 
766  ->IsNetworkAllocated (addr, prefix);
767 }
768 
769 void
771 {
773 
775  ->TestMode ();
776 }
777 
778 } // namespace ns3
779 
static Ipv6Address NextAddress(const Ipv6Prefix prefix)
Allocate the next Ipv6Address for the configured network and prefix.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
NS_ASSERT_MSG(false, "Ipv4AddressGenerator::MaskToIndex(): Impossible")
static void TestMode(void)
Used to turn off fatal errors and assertions, for testing.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:204
static void Reset(void)
Reset the networks and Ipv6Address to zero.
static bool IsNetworkAllocated(const Ipv6Address addr, const Ipv6Prefix prefix)
Check if a network has already allocated addresses.
#define NS_FATAL_ERROR(msg)
Report a fatal error with a message and terminate.
Definition: fatal-error.h:162
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
static T * Get(void)
Get a pointer to the singleton instance.
static bool IsAddressAllocated(const Ipv6Address addr)
Check the Ipv6Address allocation in the list of IPv6 entries.
const uint32_t N_BITS
number of bits in a IPv4 address
static Ipv6Address GetAddress(const Ipv6Prefix prefix)
Get the Ipv6Address that will be allocated upon NextAddress ()
Every class exported by the ns3 library is enclosed in the ns3 namespace.
address
Definition: first.py:37
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
void Reset(void)
Reset the initial value of every attribute as well as the value of every global to what they were bef...
Definition: config.cc:785
static Ipv6Address NextNetwork(const Ipv6Prefix prefix)
Get the next network according to the given Ipv6Prefix.
static void Init(const Ipv6Address net, const Ipv6Prefix prefix, const Ipv6Address interfaceId="::1")
Initialise the base network and interfaceId for the generator.
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if a condition is false, with a message.
Definition: abort.h:144
static bool AddAllocated(const Ipv6Address addr)
Add the Ipv6Address to the list of IPv6 entries.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:272
static Ipv6Address GetNetwork(const Ipv6Prefix prefix)
Get the current network of the given Ipv6Prefix.
static void InitAddress(const Ipv6Address interfaceId, const Ipv6Prefix prefix)
Set the interfaceId for the given Ipv6Prefix.