.

2 files changed, 153 insertions, 52 deletions

diff --git a/node/RoutingTable.hpp b/node/RoutingTable.hpp
index 2f8965b5..1750a510 100644
--- a/node/RoutingTable.hpp
+++ b/node/RoutingTable.hpp
@@ -25,79 +25,118 @@
  * LLC. Start here: http://www.zerotier.com/
  */
 
-#ifndef ZT_SYSTEMNETWORKSTACK_HPP
-#define ZT_SYSTEMNETWORKSTACK_HPP
+#ifndef ZT_ROUTINGTABLE_HPP
+#define ZT_ROUTINGTABLE_HPP
 
 #include <stdint.h>
+#include <string.h>
+#include <stdlib.h>
 
 #include <vector>
 #include <string>
-#include <set>
 
 #include "InetAddress.hpp"
 #include "NonCopyable.hpp"
+#include "Utils.hpp"
 
 namespace ZeroTier {
 
 /**
- * Base class for OS-dependent interfaces to the system network configuration
+ * Base class for OS routing table interfaces
  */
-class SystemNetworkStack : NonCopyable
+class RoutingTable : NonCopyable
 {
 public:
-  struct RoutingTableEntry
-  {
-    char device[128];
-    InetAddress destination;
-    InetAddress gateway;
-    unsigned int deviceMetric;
-  };
+	class Entry
+	{
+	public:
+		Entry() { device[0] = (char)0; }
 
-  SystemNetworkStack() {}
-  virtual ~SystemNetworkStack() {}
+		InetAddress destination;
+		InetAddress gateway;
+		char device[128];
+		int metric;
 
-  /**
-   * @return All routing table entries sorted in order of destination
-   */
-  virtual std::vector<RoutingTableEntry> routingTable() const = 0;
+		inline bool operator==(const Entry &re) const { return ((destination == re.destination)&&(gateway == re.gateway)&&(strcmp(device == re.device) == 0)&&(metric == re.metric)); }
+		inline bool operator!=(const Entry &re) const { return (!(*this == re)); }
+		inline bool operator<(const Entry &re) const
+		{
+			if (destination < re.destination)
+				return true;
+			if (destination == re.destination) {
+				if (gateway < re.gateway)
+					return true;
+				if (gateway == re.gateway) {
+					int tmp = (int)::strcmp(device,re.device);
+					if (tmp < 0)
+						return true;
+					if (tmp == 0)
+						return (metric < re.metric);
+				}
+			}
+			return false;
+		}
+		inline bool operator>(const Entry &re) const { return (re < *this); }
+		inline bool operator<=(const Entry &re) const { return (!(re < *this)); }
+		inline bool operator>=(const Entry &re) const { return (!(*this < re)); }
+	};
 
-  /**
-   * Add or update a routing table entry
-   *
-   * Note that metrics may only be changed at the device level,
-   * so changes to deviceMetric are ignored.
-   *
-   * @param re Entry to add/update
-   * @return True if successful
-   */
-  virtual bool addUpdateRoute(const RoutingTableEntry &re) = 0;
+	SystemNetworkStack() {}
+	virtual ~SystemNetworkStack() {}
 
-  /**
-   * @param ifname Name of interface (Unix-style device or Windows device name)
-   * @return Interface metric (higher = lower priority)
-   */
-  virtual unsigned int interfaceMetric(const char *ifname) const = 0;
+	/**
+	 * @return All routing table entries sorted in order of destination address / netmask
+	 */
+	virtual std::vector<Entry> routingTable() const = 0;
 
-  /**
-   * @param ifname Name of interface (Unix-style device or Windows device name)
-   * @param metric New metric (higher = lower priority)
-   * @return True if successful
-   */
-  virtual bool setInterfaceMetric(const char *ifname,unsigned int metric) = 0;
+	/**
+	 * Add or update a routing table entry
+	 *
+	 * @param re Entry to add/update
+	 * @return True if successful
+	 */
+	virtual bool addUpdateRoute(const Entry &re) = 0;
 
-  /**
-   * @return Interface names sorted in ascending order
-   */
-  virtual std::vector<std::string> interfaces() const = 0;
-
-  /**
-   * @param ignoreInterfaces List of interfaces to exclude from fingerprint
-   * @return Integer CRC-type fingerprint of current network environment
-   */
-  inline uint64_t networkEnvironmentFingerprint(const std::set<std::string> &ignoreInterfaces) const
-  {
-    std::vector<RoutingTableEntry> rtab(routingTable());
-  };
+	/**
+	 * Compute a 64-bit value that hashes the current state of the network environment
+	 *
+	 * @param ignoreInterfaces Names of interfaces to exclude from fingerprint (e.g. my own)
+	 * @return Integer CRC-type fingerprint of current network environment
+	 */
+	inline uint64_t networkEnvironmentFingerprint(const std::vector<std::string> &ignoreInterfaces) const
+	{
+		uint64_t fp = 0;
+		std::vector<Entry> rtab(routingTable());
+		for(std::vector<Entry>::const_iterator re(rtab.begin());re!=rtab.end();++re) {
+			bool skip = false;
+			for(std::vector<std::string>::const_iterator ii(ignoreInterfaces.begin());ii!=ignoreInterfaces.end();++ii) {
+				if (*ii == re->interface.device) {
+					skip = true;
+					break;
+				}
+			}
+			if (skip)
+				continue;
+			++fp;
+			if (re->destination.isV4()) {
+				fp = Utils::sdbmHash(re->destination.rawIpData(),4,fp);
+				fp = Utils::sdbmHash((uint16_t)re->destination.netmaskBits(),fp);
+			} else if (re->destination.isV6()) {
+				fp = Utils::sdbmHash(re->destination.rawIpData(),16,fp);
+				fp = Utils::sdbmHash((uint16_t)re->destination.netmaskBits(),fp);
+			}
+			if (re->gateway.isV4()) {
+				fp = Utils::sdbmHash(re->gateway.rawIpData(),4,fp);
+				fp = Utils::sdbmHash((uint16_t)re->gateway.netmaskBits(),fp);
+			} else if (re->gateway.isV6()) {
+				fp = Utils::sdbmHash(re->gateway.rawIpData(),16,fp);
+				fp = Utils::sdbmHash((uint16_t)re->gateway.netmaskBits(),fp);
+			}
+			fp = Utils::sdbmHash(re->device,fp);
+			fp = Utils::sdbmHash((uint32_t)re->metric,fp);
+		}
+		return fp;
+	}
 };
 
 } // namespace ZeroTier
diff --git a/node/Utils.hpp b/node/Utils.hpp
index fdec54d1..82837286 100644
--- a/node/Utils.hpp
+++ b/node/Utils.hpp
@@ -518,6 +518,68 @@ public:
 		return ((*aptr & mask) == (*aptr & mask));
 	}
 
+	/**
+	 * Compute SDBM hash of a binary string
+	 *
+	 * See: http://www.cse.yorku.ca/~oz/hash.html
+	 *
+	 * @param s Data to hash
+	 * @param l Length in bytes
+	 * @param h Previous hash value (use 0 initially)
+	 * @tparam H Hash integer type -- should be unsigned
+	 * @return New hash value
+	 */
+	template<typename H>
+	static inline H sdbmHash(const void *s,unsigned int l,H h)
+		throw()
+	{
+		for(unsigned int i=0;i<l;++i)
+			h = ((H)(((const unsigned char *)s)[i])) + (h << 6) + (h << 16) - h;
+		return h;
+	}
+
+	/**
+	 * Compute SDBM hash of a 0-terminated C string
+	 *
+	 * See: http://www.cse.yorku.ca/~oz/hash.html
+	 *
+	 * @param s C-string to hash
+	 * @param h Previous hash value (use 0 initially)
+	 * @tparam H Hash integer type -- should be unsigned
+	 * @return New hash value
+	 */
+	template<typename H>
+	static inline H sdbmHash(const char *s,H h)
+		throw()
+	{
+		char c;
+		while ((c = *(s++)))
+			h = ((H)c) + (h << 6) + (h << 16) - h;
+		return h;
+	}
+
+	/**
+	 * Compute SDBM hash of an integer's bytes in little-endian byte order
+	 *
+	 * See: http://www.cse.yorku.ca/~oz/hash.html
+	 *
+	 * @param n Integer to hash in LE byte order
+	 * @param h Previous hash value (use 0 initially)
+	 * @tparam I Integer type -- should be unsigned
+	 * @tparam H Hash integer type -- should be unsigned
+	 * @return New hash value
+	 */
+	template<typename I,typename H>
+	static inline H sdbmHash(I n,H h)
+		throw()
+	{
+		for(unsigned int i=0;i<(unsigned int)sizeof(n);++i) {
+			h = ((H)(n & 0xff)) + (h << 6) + (h << 16) - h;
+			n >>= 8;
+		}
+		return h;
+	}
+
 	// Byte swappers for big/little endian conversion
 	static inline uint8_t hton(uint8_t n) throw() { return n; }
 	static inline int8_t hton(int8_t n) throw() { return n; }