// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*- // Copyright (c) 2001-2006 International Computer Science Institute // // Permission is hereby granted, free of charge, to any person obtaining a // copy of this software and associated documentation files (the "Software") // to deal in the Software without restriction, subject to the conditions // listed in the XORP LICENSE file. These conditions include: you must // preserve this copyright notice, and you cannot mention the copyright // holders in advertising related to the Software without their permission. // The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This // notice is a summary of the XORP LICENSE file; the license in that file is // legally binding. // $XORP: xorp/libxorp/ipnet.hh,v 1.24 2006/08/01 22:21:39 mjh Exp $ #ifndef __LIBXORP_IPNET_HH__ #define __LIBXORP_IPNET_HH__ #include "xorp.h" #include "exceptions.hh" #include "c_format.hh" #include "range.hh" #include "utils.hh" /** * @short A template class for subnets * * A "subnet" is specified by a base "address" and a "prefix length". */ template <class A> class IPNet { public: /** * Default constructor taking no parameters. * * Default value has INADDR_ANY/0. */ IPNet() : _prefix_len(0) {} /** * Constructor from a given base address and a prefix length. * * @param a base address for the subnet. * @param prefix_len length of subnet mask (e.g., class C nets would have * prefix_len=24). */ IPNet(const A& a, uint32_t prefix_len) throw (InvalidNetmaskLength) : _masked_addr(a), _prefix_len(prefix_len) { if (prefix_len > A::addr_bitlen()) xorp_throw(InvalidNetmaskLength, prefix_len); _masked_addr = a.mask_by_prefix_len(prefix_len); } /** * Constructor from a string. * * @param from_cstring C-style string with slash separated address * and prefix length. */ IPNet(const char *from_cstring) throw (InvalidString, InvalidNetmaskLength) { initialize_from_string(from_cstring); } /** * Copy constructor * * @param n the subnet to copy from. */ IPNet(const IPNet& n) { _masked_addr = n.masked_addr(); _prefix_len = n.prefix_len(); } /** * Assignment operator * * @param n the subnet to assign from. * @return the subnet after the assignment. */ IPNet& operator=(const IPNet& n) { _masked_addr = n.masked_addr(); _prefix_len = n.prefix_len(); return *this; } /** * Equality Operator * * @param other the right-hand operand to compare against. * @return true if the left-hand operand is numerically same as the * right-hand operand. */ bool operator==(const IPNet& other) const { return ((prefix_len() == other.prefix_len()) && (masked_addr() == other.masked_addr())); } /** * Less-than comparison for subnets (see body for description). * * @param other the right-hand side of the comparison. * @return true if the left-hand side is "smaller" than the right-hand * side according to the chosen order. */ inline bool operator<(const IPNet& other) const; /** * Decrement Operator * * The numerical value of the prefix address is decrement by one. * Example: decrementing 128.2.0.0/16 results in 128.1.0.0/16. * * @return a reference to this subnet after the decrement */ IPNet& operator--(); /** * Increment Operator * * The numerical value of the prefix address is incremented by one. * Example: incrementing 128.2.0.0/16 results in 128.3.0.0/16. * * @return a reference to this subnet after the increment */ IPNet& operator++(); /** * Equality Operator for @ref U32Range operand. * * @param range the right-hand operand to compare against. * @return true if the prefix length falls inside the range defined * by the right-hand operand. */ inline bool operator==(const U32Range& range) const { return (prefix_len() == range); } /** * Non-equality Operator for @ref U32Range operand. * * @param range the right-hand operand to compare against. * @return true if the prefix length falls outside the range defined * by the right-hand operand. */ inline bool operator!=(const U32Range& range) const { return (prefix_len() != range); } /** * Less-than comparison for prefix lengths for @ref U32Range operand. * * @param range the right-hand side of the comparison. * @return true if the prefix length is bellow the range defined * by the right-hand operand. */ inline bool operator<(const U32Range& range) const { return (prefix_len() < range); }; /** * Less-than or equal comparison for prefix lengths for @ref U32Range * operand. * * @param range the right-hand side of the comparison. * @return true if the prefix length is bellow or within the range * defined by the right-hand operand. */ inline bool operator<=(const U32Range& range) const { return (prefix_len() <= range); }; /** * Greater-than comparison for prefix lengths for @ref U32Range operand. * * @param range the right-hand side of the comparison. * @return true if the prefix length is above the range defined * by the right-hand operand. */ inline bool operator>(const U32Range& range) const { return (prefix_len() > range); }; /** * Greater-than or equal comparison for prefix lengths for @ref U32Range * operand. * * @param range the right-hand side of the comparison. * @return true if the prefix length is above or within the range * defined by the right-hand operand. */ inline bool operator>=(const U32Range& range) const { return (prefix_len() >= range); }; /** * Convert this address from binary form to presentation format. * * @return C++ string with the human-readable ASCII representation * of the address. */ inline string str() const { return _masked_addr.str() + c_format("/%u", XORP_UINT_CAST(_prefix_len)); } /** * Test if the object contains a real (non-default) value. * * @return true if the object stores a real (non-default) value. */ bool is_valid() const { return _prefix_len != 0; } /** * Test if subnets overlap. * * @param other the subnet to compare against. * @return true if there is some overlap between the two subnets. */ inline bool is_overlap(const IPNet& other) const; /** * Test if a subnet contains (or is equal to) another subnet. * * in LaTeX, x.contains(y) would be $x \superseteq y$ * * @param other the subnet to test against. * @return true if this subnet contains or is equal to @ref other. */ inline bool contains(const IPNet& other) const; /** * Test if an address is within a subnet. * * @param addr the address to test against. * @return true if @ref addr is within this subnet. */ inline bool contains(const A& addr) const { return addr.mask_by_prefix_len(_prefix_len) == _masked_addr; } /** * Determine the number of the most significant bits overlapping with * another subnet. * * @param other the subnet to test against. * @return the number of bits overlapping between @ref other and * this subnet. */ inline uint32_t overlap(const IPNet& other) const; /** * Get the address family. * * @return the address family of this address. */ static const int af() { return A::af(); } /** * Get the base address. * * @return the base address for this subnet. */ inline const A& masked_addr() const { return _masked_addr; } /** * Get the prefix length. * * @return the prefix length for this subnet. */ inline uint32_t prefix_len() const { return _prefix_len; } /** * Get the network mask. * * @return the netmask associated with this subnet. */ inline A netmask() const { return _masked_addr.make_prefix(_prefix_len); } /** * Return the subnet containing all multicast addresses. * * Note that this is a static function and can be used without * a particular object. Example: * IPv4Net my_prefix = IPv4Net::ip_multicast_base_prefix(); OK * IPv4Net my_prefix = ipv4net.ip_multicast_base_prefix(); OK * * @return the subnet containing multicast addresses. */ static const IPNet<A> ip_multicast_base_prefix() { return IPNet(A::MULTICAST_BASE(), A::ip_multicast_base_address_mask_len()); } /** * Test if this subnet is within the multicast address range. * * @return true if this subnet is within the multicast address range. */ bool is_multicast() const { return (ip_multicast_base_prefix().contains(*this)); } /** * Test if this subnet is a unicast prefix. Note that unicast * prefixes include the default route such as 0.0.0.0/0 in IPv4 or * the v6 equivalent. * * @return true if this subnet is a unicast prefix. */ bool is_unicast() const { // Some corner cases: // 0.0.0.0/0 - this is the default route, and should return true. // // 0.0.0.0/1 - this is a valid unicast route and should return true // // 128.0.0.0/1 - this overlaps the multicast range, and // technically should return false. We return true here, // because we don't want to accidentally reject routes that // mind be thought of as valid, but the behaviour could // probably be changed to be more strictly correct if needed. // // 224.0.0.0/8 - this is a multicast route, and returns false. if (masked_addr().is_zero()) { // it's the default route, or a valid unicast route return true; } return masked_addr().is_unicast(); } /** * Get the highest address within this subnet. * * @return the highest address within this subnet. */ inline A top_addr() const { return _masked_addr | ~netmask(); } /** * Get the smallest subnet containing both subnets. * * @return the smallest subnet containing both subnets passed * as arguments. */ static IPNet<A> common_subnet(const IPNet<A> x, const IPNet<A> y) { return IPNet<A>(x.masked_addr(), x.overlap(y)); } protected: inline void initialize_from_string(const char *s) throw (InvalidString, InvalidNetmaskLength); A _masked_addr; uint32_t _prefix_len; }; /* ------------------------------------------------------------------------- */ /* Deferred method definitions */ template <class A> bool IPNet<A>::operator<(const IPNet& other) const { #if 1 /* * say x = A/B and y = C/D, then * * x < y : * * if x.contains(y) // equal is fine * return false * else if y.strictly_contains(x) // equal already taken care of * return true * else * return A < C * * |---x---| * x=y |---y---| * x>y |-y-| * x<y |------y-------| * x<y |-----y---------| * x<y |--y-| */ if (masked_addr().af() != other.masked_addr().af()) return (masked_addr().af() < other.masked_addr().af()); if (this->contains(other)) return false; else if (other.contains(*this)) return true; else return this->masked_addr() < other.masked_addr(); #else // old code const A& maddr_him = other.masked_addr(); uint32_t his_prefix_len = other.prefix_len(); //the ordering is important because we want the longest match to //be first. For example, we want the following: // 128.16.0.0/24 < 128.16.64.0/24 < 128.16.0.0/16 < 128.17.0.0/24 if (_prefix_len == his_prefix_len) return _masked_addr < maddr_him; // we need to check the case when one subnet is a subset of // the other if (_prefix_len < his_prefix_len) { A test_addr(maddr_him.mask_by_prefix_len(_prefix_len)); if (_masked_addr == test_addr) { //his subnet is a subset of mine, so he goes first. return (false); } } else if (_prefix_len > his_prefix_len) { A test_addr(_masked_addr.mask_by_prefix_len(his_prefix_len)); if (maddr_him == test_addr) { //my subnet is a subset of his, so I go first. return (true); } } //the subnets don't overlap (or are identical), so just order by address if (_masked_addr < maddr_him) { return (true); } return (false); #endif } template <class A> bool IPNet<A>::is_overlap(const IPNet<A>& other) const { if (masked_addr().af() != other.masked_addr().af()) return (false); if (prefix_len() > other.prefix_len()) { // I have smaller prefix size IPNet other_masked(masked_addr(), other.prefix_len()); return (other_masked.masked_addr() == other.masked_addr()); } if (prefix_len() < other.prefix_len()) { // I have bigger prefix size IPNet other_masked(other.masked_addr(), prefix_len()); return (other_masked.masked_addr() == masked_addr()); } // Same prefix size return (other.masked_addr() == masked_addr()); } template <class A> bool IPNet<A>::contains(const IPNet<A>& other) const { if (masked_addr().af() != other.masked_addr().af()) return (false); if (prefix_len() > other.prefix_len()) { // I have smaller prefix size, hence I don't contain other. return (false); } if (prefix_len() < other.prefix_len()) { // I have bigger prefix size IPNet other_masked(other.masked_addr(), prefix_len()); return (other_masked.masked_addr() == masked_addr()); } // Same prefix size return (other.masked_addr() == masked_addr()); } template <class A> void IPNet<A>::initialize_from_string(const char *cp) throw (InvalidString, InvalidNetmaskLength) { char *slash = strrchr(cp, '/'); if (slash == 0) xorp_throw(InvalidString, "Missing slash"); if (*(slash + 1) == 0) xorp_throw(InvalidString, "Missing prefix length"); char *n = slash + 1; while (*n != 0) { if (*n < '0' || *n > '9') { xorp_throw(InvalidString, "Bad prefix length"); } n++; } _prefix_len = atoi(slash + 1); string addr = string(cp, slash - cp); _masked_addr = A(addr.c_str()).mask_by_prefix_len(_prefix_len); } template <class A> IPNet<A>& IPNet<A>::operator--() { _masked_addr = _masked_addr >> (_masked_addr.addr_bitlen() - _prefix_len); --_masked_addr; _masked_addr = _masked_addr << (_masked_addr.addr_bitlen() - _prefix_len); return (*this); } template <class A> IPNet<A>& IPNet<A>::operator++() { _masked_addr = _masked_addr >> (_masked_addr.addr_bitlen() - _prefix_len); ++_masked_addr; _masked_addr = _masked_addr << (_masked_addr.addr_bitlen() - _prefix_len); return (*this); } template <class A> inline uint32_t IPNet<A>::overlap(const IPNet<A>& other) const { if (masked_addr().af() != other.masked_addr().af()) return 0; A xor_addr = masked_addr() ^ other.masked_addr(); uint32_t done = xor_addr.leading_zero_count(); uint32_t p = (prefix_len() < other.prefix_len()) ? prefix_len() : other.prefix_len(); if (done > p) done = p; return done; } /** * Determine the number of the most significant bits overlapping * between two subnets. * * @param a1 the first subnet. * @param a2 the subnet. * @return the number of bits overlapping between @ref a1 and @ref a2. */ template <class A> uint32_t overlap(const IPNet<A>& a1, const IPNet<A>& a2) { return a1.overlap(a2); } #endif // __LIBXORP_IPNET_HH__