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 
134  void TestMode (void);
135 
136 private:
137  static const uint32_t N_BITS = 128;
138  static const uint32_t MOST_SIGNIFICANT_BIT = 0x80;
139 
145  uint32_t PrefixToIndex (Ipv6Prefix prefix) const;
146 
150  class NetworkState
151  {
152 public:
153  uint8_t prefix[16];
154  uint32_t shift;
155  uint8_t network[16];
156  uint8_t addr[16];
157  uint8_t addrMax[16];
158  };
159 
160  NetworkState m_netTable[N_BITS];
161 
165  class Entry
166  {
167 public:
168  uint8_t addrLow[16];
169  uint8_t addrHigh[16];
170  };
171 
172  std::list<Entry> m_entries;
173  Ipv6Address m_base;
174  bool m_test;
175 };
176 
177 Ipv6AddressGeneratorImpl::Ipv6AddressGeneratorImpl ()
178  : m_entries (),
179  m_base ("::1"),
180  m_test (false)
181 {
182  NS_LOG_FUNCTION (this);
183  Reset ();
184 }
185 
186 void
188 {
189  NS_LOG_FUNCTION (this);
190 
191  uint8_t prefix[16] = { 0};
192 
193  for (uint32_t i = 0; i < N_BITS; ++i)
194  {
195  for (uint32_t j = 0; j < 16; ++j)
196  {
197  m_netTable[i].prefix[j] = prefix[j];
198  }
199  for (uint32_t j = 0; j < 15; ++j)
200  {
201  prefix[15 - j] >>= 1;
202  prefix[15 - j] |= (prefix[15 - j - 1] & 1);
203  }
204  prefix[0] |= MOST_SIGNIFICANT_BIT;
205  for (uint32_t j = 0; j < 15; ++j)
206  {
207  m_netTable[i].network[j] = 0;
208  }
209  m_netTable[i].network[15] = 1;
210  for (uint32_t j = 0; j < 15; ++j)
211  {
212  m_netTable[i].addr[j] = 0;
213  }
214  m_netTable[i].addr[15] = 1;
215  for (uint32_t j = 0; j < 16; ++j)
216  {
217  m_netTable[i].addrMax[j] = ~prefix[j];
218  }
219  m_netTable[i].shift = N_BITS - i;
220  }
221  m_entries.clear ();
222  m_base = Ipv6Address ("::1");
223  m_test = false;
224 }
225 
226 Ipv6AddressGeneratorImpl::~Ipv6AddressGeneratorImpl ()
227 {
228  NS_LOG_FUNCTION (this);
229 }
230 
231 void
232 Ipv6AddressGeneratorImpl::Init (
233  const Ipv6Address net,
234  const Ipv6Prefix prefix,
235  const Ipv6Address interfaceId)
236 {
237  NS_LOG_FUNCTION (this << net << prefix << interfaceId);
238 
239  m_base = interfaceId;
240  //
241  // We're going to be playing with the actual bits in the network and prefix so
242  // pull them out into ints.
243  //
244  uint8_t prefixBits[16];
245  prefix.GetBytes (prefixBits);
246  uint8_t netBits[16];
247  net.GetBytes (netBits);
248  uint8_t interfaceIdBits[16];
249  interfaceId.GetBytes (interfaceIdBits);
250  //
251  // Some quick reasonableness testing.
252  //
253  // Convert the network prefix into an index into the network number table.
254  // The network number comes in to us properly aligned for the prefix and so
255  // needs to be shifted right into the normalized position (lowest bit of the
256  // network number at bit zero of the int that holds it).
257  //
258  uint32_t index = PrefixToIndex (prefix);
259  NS_LOG_DEBUG ("Index " << index);
260  uint32_t a = m_netTable[index].shift / 8;
261  uint32_t b = m_netTable[index].shift % 8;
262  for (int32_t j = 15 - a; j >= 0; j--)
263  {
264  m_netTable[index].network[j + a] = netBits[j];
265  }
266  for (uint32_t j = 0; j < a; j++)
267  {
268  m_netTable[index].network[j] = 0;
269  }
270  for (uint32_t j = 15; j >= a; j--)
271  {
272  m_netTable[index].network[j] = m_netTable[index].network[j] >> b;
273  m_netTable[index].network[j] |= m_netTable[index].network[j - 1] << (8 - b);
274  }
275  for (int32_t j = 0; j < 16; j++)
276  {
277  m_netTable[index].addr[j] = interfaceIdBits[j];
278  }
279  return;
280 }
281 
282 Ipv6Address
283 Ipv6AddressGeneratorImpl::GetNetwork (
284  const Ipv6Prefix prefix) const
285 {
286  NS_LOG_FUNCTION (this);
287  uint8_t nw[16] = { 0 };
288  uint32_t index = PrefixToIndex (prefix);
289  uint32_t a = m_netTable[index].shift / 8;
290  uint32_t b = m_netTable[index].shift % 8;
291  for (uint32_t j = 0; j < 16 - a; ++j)
292  {
293  nw[j] = m_netTable[index].network[j + a];
294  }
295  for (uint32_t j = 0; j < 15; j++)
296  {
297  nw[j] = nw[j] << b;
298  nw[j] |= nw[j + 1] >> (8 - b);
299  }
300  nw[15] = nw[15] << b;
301 
302  return Ipv6Address (nw);
303 }
304 
305 Ipv6Address
306 Ipv6AddressGeneratorImpl::NextNetwork (
307  const Ipv6Prefix prefix)
308 {
309  NS_LOG_FUNCTION (this);
310 
311  uint32_t index = PrefixToIndex (prefix);
312  // Reset the base to what was initialized
313  uint8_t interfaceIdBits[16];
314  m_base.GetBytes (interfaceIdBits);
315  for (int32_t j = 0; j < 16; j++)
316  {
317  m_netTable[index].addr[j] = interfaceIdBits[j];
318  }
319 
320  for (int32_t j = 15; j >= 0; j--)
321  {
322  if (m_netTable[index].network[j] < 0xff)
323  {
324  ++m_netTable[index].network[j];
325  break;
326  }
327  else
328  {
329  ++m_netTable[index].network[j];
330  }
331  }
332 
333  uint8_t nw[16];
334  uint32_t a = m_netTable[index].shift / 8;
335  uint32_t b = m_netTable[index].shift % 8;
336  for (uint32_t j = 0; j < 16 - a; ++j)
337  {
338  nw[j] = m_netTable[index].network[j + a];
339  }
340  for (uint32_t j = 16 - a; j < 16; ++j)
341  {
342  nw[j] = 0;
343  }
344  for (uint32_t j = 0; j < 15; j++)
345  {
346  nw[j] = nw[j] << b;
347  nw[j] |= nw[j + 1] >> (8 - b);
348  }
349  nw[15] = nw[15] << b;
350 
351  return Ipv6Address (nw);
352 
353 }
354 
355 void
356 Ipv6AddressGeneratorImpl::InitAddress (
357  const Ipv6Address interfaceId,
358  const Ipv6Prefix prefix)
359 {
360  NS_LOG_FUNCTION (this);
361 
362  uint32_t index = PrefixToIndex (prefix);
363  uint8_t interfaceIdBits[16];
364  interfaceId.GetBytes (interfaceIdBits);
365 
366  for (uint32_t j = 0; j < 16; ++j)
367  {
368  m_netTable[index].addr[j] = interfaceIdBits[j];
369  }
370 }
371 
372 Ipv6Address
373 Ipv6AddressGeneratorImpl::GetAddress (const Ipv6Prefix prefix) const
374 {
375  NS_LOG_FUNCTION (this);
376 
377  uint32_t index = PrefixToIndex (prefix);
378 
379  uint8_t nw[16] = { 0 };
380  uint32_t a = m_netTable[index].shift / 8;
381  uint32_t b = m_netTable[index].shift % 8;
382  for (uint32_t j = 0; j < 16 - a; ++j)
383  {
384  nw[j] = m_netTable[index].network[j + a];
385  }
386  for (uint32_t j = 0; j < 15; j++)
387  {
388  nw[j] = nw[j] << b;
389  nw[j] |= nw[j + 1] >> (8 - b);
390  }
391  nw[15] = nw[15] << b;
392  for (uint32_t j = 0; j < 16; j++)
393  {
394  nw[j] |= m_netTable[index].addr[j];
395  }
396 
397  return Ipv6Address (nw);
398 }
399 
400 Ipv6Address
401 Ipv6AddressGeneratorImpl::NextAddress (const Ipv6Prefix prefix)
402 {
403  NS_LOG_FUNCTION (this);
404 
405  uint32_t index = PrefixToIndex (prefix);
406 
407  uint8_t ad[16] = { 0 };
408  uint32_t a = m_netTable[index].shift / 8;
409  uint32_t b = m_netTable[index].shift % 8;
410  for (uint32_t j = 0; j < 16 - a; ++j)
411  {
412  ad[j] = m_netTable[index].network[j + a];
413  }
414  for (uint32_t j = 0; j < 15; j++)
415  {
416  ad[j] = ad[j] << b;
417  ad[j] |= ad[j + 1] >> (8 - b);
418  }
419  ad[15] = ad[15] << b;
420  for (uint32_t j = 0; j < 16; j++)
421  {
422  ad[j] |= m_netTable[index].addr[j];
423  }
424  Ipv6Address addr = Ipv6Address (ad);
425 
426  for (int32_t j = 15; j >= 0; j--)
427  {
428  if (m_netTable[index].addr[j] < 0xff)
429  {
430  ++m_netTable[index].addr[j];
431  break;
432  }
433  else
434  {
435  ++m_netTable[index].addr[j];
436  }
437  }
438 
439  //
440  // Make a note that we've allocated this address -- used for address collision
441  // detection.
442  //
443  AddAllocated (addr);
444  return addr;
445 }
446 
447 bool
448 Ipv6AddressGeneratorImpl::AddAllocated (const Ipv6Address address)
449 {
450  NS_LOG_FUNCTION (this << address);
451 
452  uint8_t addr[16];
453  address.GetBytes (addr);
454 
455  std::list<Entry>::iterator i;
456 
457  for (i = m_entries.begin (); i != m_entries.end (); ++i)
458  {
459  NS_LOG_LOGIC ("examine entry: " << Ipv6Address ((*i).addrLow) <<
460  " to " << Ipv6Address ((*i).addrHigh));
461  //
462  // First things first. Is there an address collision -- that is, does the
463  // new address fall in a previously allocated block of addresses.
464  //
465  if (!(Ipv6Address (addr) < Ipv6Address ((*i).addrLow))
466  && ((Ipv6Address (addr) < Ipv6Address ((*i).addrHigh))
467  || (Ipv6Address (addr) == Ipv6Address ((*i).addrHigh))))
468  {
469  NS_LOG_LOGIC ("Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address (addr));
470  if (!m_test)
471  {
472  NS_FATAL_ERROR ("Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address (addr));
473  }
474  return false;
475  }
476  //
477  // If the new address is less than the lowest address in the current
478  // block and can't be merged into to the current block, then insert it
479  // as a new block before the current block.
480  //
481  uint8_t taddr[16];
482  for (uint32_t j = 0; j < 16; j++)
483  {
484  taddr[j] = (*i).addrLow[j];
485  }
486  taddr[15] -= 1;
487  if (Ipv6Address (addr) < Ipv6Address (taddr))
488  {
489  break;
490  }
491  //
492  // If the new address fits at the end of the block, look ahead to the next
493  // block and make sure it's not a collision there. If we won't overlap,
494  // then just extend the current block by one address. We expect that
495  // completely filled network ranges will be a fairly rare occurrence,
496  // so we don't worry about collapsing address range blocks.
497  //
498  for (uint32_t j = 0; j < 16; j++)
499  {
500  taddr[j] = (*i).addrLow[j];
501  }
502  taddr[15] += 1;
503  if (Ipv6Address (addr) == Ipv6Address (taddr))
504  {
505  std::list<Entry>::iterator j = i;
506  ++j;
507 
508  if (j != m_entries.end ())
509  {
510  if (Ipv6Address (addr) == Ipv6Address ((*j).addrLow))
511  {
512  NS_LOG_LOGIC ("Ipv6AddressGeneratorImpl::Add(): "
513  "Address Collision: " << Ipv6Address (addr));
514  if (!m_test)
515  {
516  NS_FATAL_ERROR ("Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address (addr));
517  }
518  return false;
519  }
520  }
521 
522  NS_LOG_LOGIC ("New addrHigh = " << Ipv6Address (addr));
523  for (uint32_t j = 0; j < 16; j++)
524  {
525  (*i).addrHigh[j] = addr[j];
526  }
527  return true;
528  }
529  //
530  // If we get here, we know that the next lower block of addresses
531  // couldn't have been extended to include this new address since the
532  // code immediately above would have been executed and that next lower
533  // block extended upward. So we know it's safe to extend the current
534  // block down to includ the new address.
535  //
536  for (uint32_t j = 0; j < 16; j++)
537  {
538  taddr[j] = (*i).addrLow[j];
539  }
540  taddr[15] -= 1;
541  if ((Ipv6Address (addr) == Ipv6Address (taddr)))
542  {
543  NS_LOG_LOGIC ("New addrLow = " << Ipv6Address (addr));
544  for (uint32_t j = 0; j < 16; j++)
545  {
546  (*i).addrLow[j] = addr[j];
547  }
548  return true;
549  }
550  }
551 
552  Entry entry;
553  for (uint32_t j = 0; j < 16; j++)
554  {
555  entry.addrLow[j] = entry.addrHigh[j] = addr[j];
556  }
557  m_entries.insert (i, entry);
558  return true;
559 }
560 
561 void
562 Ipv6AddressGeneratorImpl::TestMode (void)
563 {
564  NS_LOG_FUNCTION (this);
565  m_test = true;
566 }
567 
568 uint32_t
569 Ipv6AddressGeneratorImpl::PrefixToIndex (Ipv6Prefix prefix) const
570 {
571  //
572  // We've been given a prefix that has a higher order bit set for each bit of
573  // the network number. In order to translate this prefix into an index,
574  // we just need to count the number of zero bits in the prefix. We do this
575  // in a loop in which we shift the prefix right until we find the first
576  // nonzero bit. This tells us the number of zero bits, and from this we
577  // infer the number of nonzero bits which is the number of bits in the prefix.
578  //
579  // We use the number of bits in the prefix as the number of bits in the
580  // network number and as the index into the network number state table.
581  //
582  uint8_t prefixBits[16];
583  prefix.GetBytes (prefixBits);
584 
585  for (int32_t i = 15; i >= 0; --i)
586  {
587  for (uint32_t j = 0; j < 8; ++j)
588  {
589  if (prefixBits[i] & 1)
590  {
591  uint32_t index = N_BITS - (15 - i) * 8 - j;
592  NS_ABORT_MSG_UNLESS (index > 0 && index < N_BITS, "Ip64AddressGenerator::PrefixToIndex(): Illegal Prefix");
593  return index;
594  }
595  prefixBits[i] >>= 1;
596  }
597  }
598  NS_ASSERT_MSG (false, "Ipv6AddressGenerator::PrefixToIndex(): Impossible");
599  return 0;
600 }
601 
602 void
604  const Ipv6Address net,
605  const Ipv6Prefix prefix,
606  const Ipv6Address interfaceId)
607 {
609 
611  ->Init (net, prefix, interfaceId);
612 }
613 
614 Ipv6Address
615 Ipv6AddressGenerator::NextNetwork (const Ipv6Prefix prefix)
616 {
618 
620  ->NextNetwork (prefix);
621 }
622 
623 Ipv6Address
624 Ipv6AddressGenerator::GetNetwork (const Ipv6Prefix prefix)
625 {
627 
629  ->GetNetwork (prefix);
630 }
631 
632 void
634  const Ipv6Address interfaceId,
635  const Ipv6Prefix prefix)
636 {
638 
640  ->InitAddress (interfaceId, prefix);
641 }
642 
643 Ipv6Address
644 Ipv6AddressGenerator::GetAddress (const Ipv6Prefix prefix)
645 {
647 
649  ->GetAddress (prefix);
650 }
651 
652 Ipv6Address
653 Ipv6AddressGenerator::NextAddress (const Ipv6Prefix prefix)
654 {
656 
658  ->NextAddress (prefix);
659 }
660 
661 void
663 {
665 
667  ->Reset ();
668 }
669 
670 bool
671 Ipv6AddressGenerator::AddAllocated (const Ipv6Address addr)
672 {
674 
676  ->AddAllocated (addr);
677 }
678 
679 void
681 {
683 
685  ->TestMode ();
686 }
687 
688 } // namespace ns3
689 
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 "...
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:201
static void Reset(void)
Reset the networks and Ipv6Address to zero.
#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.
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.
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:757
#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:90
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:269
tuple address
Definition: first.py:37
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.