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 
41 {
42 public:
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 
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 
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;
191  bool m_test;
192 };
193 
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 
244 {
245  NS_LOG_FUNCTION (this);
246 }
247 
248 void
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 
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 
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
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 
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 
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
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
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
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
635 {
636  NS_LOG_FUNCTION (this);
637  m_test = true;
638 }
639 
640 uint32_t
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 {
680  NS_LOG_FUNCTION (net << prefix << interfaceId);
681 
683  ->Init (net, prefix, interfaceId);
684 }
685 
688 {
689  NS_LOG_FUNCTION (prefix);
690 
692  ->NextNetwork (prefix);
693 }
694 
697 {
698  NS_LOG_FUNCTION (prefix);
699 
701  ->GetNetwork (prefix);
702 }
703 
704 void
706  const Ipv6Address interfaceId,
707  const Ipv6Prefix prefix)
708 {
709  NS_LOG_FUNCTION (interfaceId << prefix);
710 
712  ->InitAddress (interfaceId, prefix);
713 }
714 
717 {
718  NS_LOG_FUNCTION (prefix);
719 
721  ->GetAddress (prefix);
722 }
723 
726 {
727  NS_LOG_FUNCTION (prefix);
728 
730  ->NextAddress (prefix);
731 }
732 
733 void
735 {
737 
739  ->Reset ();
740 }
741 
742 bool
744 {
745  NS_LOG_FUNCTION (addr);
746 
748  ->AddAllocated (addr);
749 }
750 
751 bool
753 {
754  NS_LOG_FUNCTION (addr);
755 
757  ->IsAddressAllocated (addr);
758 }
759 
760 bool
762 {
763  NS_LOG_FUNCTION (addr << prefix);
764 
766  ->IsNetworkAllocated (addr, prefix);
767 }
768 
769 void
771 {
773 
775  ->TestMode ();
776 }
777 
778 } // namespace ns3
779 
This class holds the state for a given network.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
This class holds the allocated addresses.
void GetBytes(uint8_t buf[16]) const
Get the bytes corresponding to the address.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
static Ipv6Address NextNetwork(const Ipv6Prefix prefix)
Get the next network according to the given Ipv6Prefix.
void GetBytes(uint8_t buf[16]) const
Get the bytes corresponding to the prefix.
#define NS_FATAL_ERROR(msg)
Report a fatal error with a message and terminate.
Definition: fatal-error.h:165
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
static T * Get(void)
Get a pointer to the singleton instance.
bool IsNetworkAllocated(const Ipv6Address addr, const Ipv6Prefix prefix)
Check if a network has already allocated addresses.
void Reset(void)
Reset the networks and Ipv6Address to zero.
static void InitAddress(const Ipv6Address interfaceId, const Ipv6Prefix prefix)
Set the interfaceId for the given Ipv6Prefix.
bool IsAddressAllocated(const Ipv6Address addr)
Check the Ipv6Address allocation in the list of IPv6 entries.
Ipv6Address GetNetwork(const Ipv6Prefix prefix) const
Get the current network of 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.
Ipv6Address GetAddress(const Ipv6Prefix prefix) const
Get the Ipv6Address that will be allocated upon NextAddress ()
void InitAddress(const Ipv6Address interfaceId, const Ipv6Prefix prefix)
Set the interfaceId for the given Ipv6Prefix.
Ipv6Address CombinePrefix(Ipv6Prefix const &prefix) const
Combine this address with a prefix.
NetworkState m_netTable[N_BITS]
the available networks
std::list< Entry > m_entries
contained of allocated addresses
static const uint32_t N_BITS
the number of bits in the address
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
static bool IsAddressAllocated(const Ipv6Address addr)
Check the Ipv6Address allocation in the list of IPv6 entries.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
address
Definition: first.py:44
static const uint32_t MOST_SIGNIFICANT_BIT
MSB set to 1.
Implementation class of Ipv6AddressGenerator This generator assigns addresses sequentially from a pro...
static void TestMode(void)
Used to turn off fatal errors and assertions, for testing.
void TestMode(void)
Used to turn off fatal errors and assertions, for testing.
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition: assert.h:88
Describes an IPv6 address.
Definition: ipv6-address.h:49
static void Reset(void)
Reset the networks and Ipv6Address to zero.
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if a condition is false, with a message.
Definition: abort.h:144
uint32_t PrefixToIndex(Ipv6Prefix prefix) const
Create an index number for the prefix.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
Ipv6Address NextNetwork(const Ipv6Prefix prefix)
Get the next network according to the given Ipv6Prefix.
static Ipv6Address GetAddress(const Ipv6Prefix prefix)
Get the Ipv6Address that will be allocated upon NextAddress ()
Describes an IPv6 prefix.
Definition: ipv6-address.h:467
static bool AddAllocated(const Ipv6Address addr)
Add the Ipv6Address to the list of IPv6 entries.
uint8_t addrLow[16]
the lowest allocated address
Ipv6Address NextAddress(const Ipv6Prefix prefix)
Allocate the next Ipv6Address for the configured network and prefix.
void Init(const Ipv6Address net, const Ipv6Prefix prefix, const Ipv6Address interfaceId)
Initialise the base network and interfaceId for the generator.
static bool IsNetworkAllocated(const Ipv6Address addr, const Ipv6Prefix prefix)
Check if a network has already allocated addresses.
static Ipv6Address NextAddress(const Ipv6Prefix prefix)
Allocate the next Ipv6Address for the configured network and prefix.
uint8_t addrHigh[16]
the highest allocated address
bool AddAllocated(const Ipv6Address addr)
Add the Ipv6Address to the list of IPv6 entries.
static Ipv6Address GetNetwork(const Ipv6Prefix prefix)
Get the current network of the given Ipv6Prefix.