Merge branch 'adamierymenko-dev' into netcon

4 files changed, 301 insertions, 0 deletions

diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp
index bcc111e3..d2b85c15 100644
--- a/node/Hashtable.hpp
+++ b/node/Hashtable.hpp
@@ -380,6 +380,11 @@ private:
 		 * hash an integer key index in a hash table. */
 		return (unsigned long)i;
 	}
+	static inline unsigned long _hc(const uint32_t i)
+	{
+		// In the uint32_t case we use a simple multiplier for hashing to ensure coverage
+		return ((unsigned long)i * (unsigned long)2654435761);
+	}
 
 	inline void _grow()
 	{
diff --git a/node/MAC.hpp b/node/MAC.hpp
index 619b7195..a9cd43cf 100644
--- a/node/MAC.hpp
+++ b/node/MAC.hpp
@@ -250,6 +250,12 @@ public:
 		_m = m._m;
 		return *this;
 	}
+	inline MAC &operator=(const uint64_t m)
+		throw()
+	{
+		_m = m;
+		return *this;
+	}
 
 	inline bool operator==(const MAC &m) const throw() { return (_m == m._m); }
 	inline bool operator!=(const MAC &m) const throw() { return (_m != m._m); }
diff --git a/osdep/Arp.cpp b/osdep/Arp.cpp
new file mode 100644
index 00000000..f71dfb54
--- /dev/null
+++ b/osdep/Arp.cpp
@@ -0,0 +1,134 @@
+/*
+ * ZeroTier One - Network Virtualization Everywhere
+ * Copyright (C) 2011-2015  ZeroTier, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * --
+ *
+ * ZeroTier may be used and distributed under the terms of the GPLv3, which
+ * are available at: http://www.gnu.org/licenses/gpl-3.0.html
+ *
+ * If you would like to embed ZeroTier into a commercial application or
+ * redistribute it in a modified binary form, please contact ZeroTier Networks
+ * LLC. Start here: http://www.zerotier.com/
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "Arp.hpp"
+#include "OSUtils.hpp"
+
+namespace ZeroTier {
+
+static const uint8_t ARP_REQUEST_HEADER[8] = { 0x00,0x01,0x08,0x00,0x06,0x04,0x00,0x01 };
+static const uint8_t ARP_RESPONSE_HEADER[8] = { 0x00,0x01,0x08,0x00,0x06,0x04,0x00,0x02 };
+
+Arp::Arp() :
+	_cache(256),
+	_lastCleaned(OSUtils::now())
+{
+}
+
+void Arp::addLocal(uint32_t ip,const MAC &mac)
+{
+	_ArpEntry &e = _cache[ip];
+	e.lastQuerySent = 0; // local IP
+	e.lastResponseReceived = 0; // local IP
+	e.mac = mac;
+	e.local = true;
+}
+
+void Arp::remove(uint32_t ip)
+{
+	_cache.erase(ip);
+}
+
+uint32_t Arp::processIncomingArp(const void *arp,unsigned int len,void *response,unsigned int &responseLen,MAC &responseDest)
+{
+	const uint64_t now = OSUtils::now();
+	uint32_t ip = 0;
+
+	responseLen = 0;
+	responseDest.zero();
+
+	if (len > 28) {
+		if (!memcmp(arp,ARP_REQUEST_HEADER,8)) {
+			// Respond to ARP requests for locally-known IPs
+			_ArpEntry *targetEntry = _cache.get(reinterpret_cast<const uint32_t *>(arp)[6]);
+			if ((targetEntry)&&(targetEntry->local)) {
+				memcpy(response,ARP_RESPONSE_HEADER,8);
+				targetEntry->mac.copyTo(reinterpret_cast<uint8_t *>(response) + 8,6);
+				memcpy(reinterpret_cast<uint8_t *>(response) + 14,reinterpret_cast<const uint8_t *>(arp) + 24,4);
+				memcpy(reinterpret_cast<uint8_t *>(response) + 18,reinterpret_cast<const uint8_t *>(arp) + 8,10);
+				responseLen = 28;
+				responseDest.setTo(reinterpret_cast<const uint8_t *>(arp) + 8,6);
+			}
+		} else if (!memcmp(arp,ARP_RESPONSE_HEADER,8)) {
+			// Learn cache entries for remote IPs from relevant ARP replies
+			uint32_t responseIp = 0;
+			memcpy(&responseIp,reinterpret_cast<const uint8_t *>(arp) + 14,4);
+			_ArpEntry *queryEntry = _cache.get(responseIp);
+			if ((queryEntry)&&(!queryEntry->local)&&((now - queryEntry->lastQuerySent) <= ZT_ARP_QUERY_MAX_TTL)) {
+				queryEntry->lastResponseReceived = now;
+				queryEntry->mac.setTo(reinterpret_cast<const uint8_t *>(arp) + 8,6);
+				ip = responseIp;
+			}
+		}
+	}
+
+	if ((now - _lastCleaned) >= ZT_ARP_EXPIRE) {
+		_lastCleaned = now;
+		Hashtable< uint32_t,_ArpEntry >::Iterator i(_cache);
+		uint32_t *k = (uint32_t *)0;
+		_ArpEntry *v = (_ArpEntry *)0;
+		while (i.next(k,v)) {
+			if ((!v->local)&&((now - v->lastResponseReceived) >= ZT_ARP_EXPIRE))
+				_cache.erase(*k);
+		}
+	}
+
+	return ip;
+}
+
+MAC Arp::query(const MAC &localMac,uint32_t ip,void *query,unsigned int &queryLen,MAC &queryDest)
+{
+	const uint64_t now = OSUtils::now();
+
+	_ArpEntry &e = _cache[ip];
+
+	if ( ((e.mac)&&((now - e.lastResponseReceived) >= (ZT_ARP_EXPIRE / 3))) ||
+	     ((!e.mac)&&((now - e.lastQuerySent) >= ZT_ARP_QUERY_INTERVAL)) ) {
+		e.lastQuerySent = now;
+
+		uint8_t *q = reinterpret_cast<uint8_t *>(query);
+		memcpy(q,ARP_REQUEST_HEADER,8); q += 8; // ARP request header information, always the same
+		localMac.copyTo(q,6); q += 6; // sending host address
+		memset(q,0,10); q += 10; // sending IP and target media address are ignored in requests
+		memcpy(q,&ip,4); // target IP address for resolution (IP already in big-endian byte order)
+		queryLen = 28;
+		if (e.mac)
+			queryDest = e.mac; // confirmation query, send directly to address holder
+		else queryDest = (uint64_t)0xffffffffffffULL; // broadcast query
+	} else {
+		queryLen = 0;
+		queryDest.zero();
+	}
+
+	return e.mac;
+}
+
+} // namespace ZeroTier
diff --git a/osdep/Arp.hpp b/osdep/Arp.hpp
new file mode 100644
index 00000000..b747cf85
--- /dev/null
+++ b/osdep/Arp.hpp
@@ -0,0 +1,156 @@
+/*
+ * ZeroTier One - Network Virtualization Everywhere
+ * Copyright (C) 2011-2015  ZeroTier, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * --
+ *
+ * ZeroTier may be used and distributed under the terms of the GPLv3, which
+ * are available at: http://www.gnu.org/licenses/gpl-3.0.html
+ *
+ * If you would like to embed ZeroTier into a commercial application or
+ * redistribute it in a modified binary form, please contact ZeroTier Networks
+ * LLC. Start here: http://www.zerotier.com/
+ */
+
+#ifndef ZT_ARP_HPP
+#define ZT_ARP_HPP
+
+#include <stdint.h>
+
+#include <utility>
+
+#include "../node/Constants.hpp"
+#include "../node/Hashtable.hpp"
+#include "../node/MAC.hpp"
+
+/**
+ * Maximum possible ARP length
+ *
+ * ARPs are 28 bytes in length, but specify a 128 byte buffer since
+ * some weird extensions we may support in the future can pad them
+ * out to as long as 72 bytes.
+ */
+#define ZT_ARP_BUF_LENGTH 128
+
+/**
+ * Minimum permitted interval between sending ARP queries for a given IP
+ */
+#define ZT_ARP_QUERY_INTERVAL 2000
+
+/**
+ * Maximum time between query and response, otherwise responses are discarded to prevent poisoning
+ */
+#define ZT_ARP_QUERY_MAX_TTL 5000
+
+/**
+ * ARP expiration time
+ */
+#define ZT_ARP_EXPIRE 600000
+
+namespace ZeroTier {
+
+/**
+ * ARP cache and resolver
+ *
+ * To implement ARP:
+ *
+ * (1) Call processIncomingArp() on all ARP packets received and then always
+ * check responseLen after calling. If it is non-zero, send the contents
+ * of response to responseDest.
+ *
+ * (2) Call query() to look up IP addresses, and then check queryLen. If it
+ * is non-zero, send the contents of query to queryDest (usually broadcast).
+ *
+ * Note that either of these functions can technically generate a response or
+ * a query at any time, so their result parameters for sending ARPs should
+ * always be checked.
+ *
+ * This class is not thread-safe and must be guarded if used in multi-threaded
+ * code.
+ */
+class Arp
+{
+public:
+	Arp();
+
+	/**
+	 * Set a local IP entry that we should respond to ARPs for
+	 *
+	 * @param mac Our local MAC address
+	 * @param ip IP in big-endian byte order (sin_addr.s_addr)
+	 */
+	void addLocal(uint32_t ip,const MAC &mac);
+
+	/**
+	 * Delete a local IP entry or a cached ARP entry
+	 *
+	 * @param ip IP in big-endian byte order (sin_addr.s_addr)
+	 */
+	void remove(uint32_t ip);
+
+	/**
+	 * Process ARP packets
+	 *
+	 * For ARP queries, a response is generated and responseLen is set to its
+	 * frame payload length in bytes.
+	 *
+	 * For ARP responses, the cache is populated and the IP address entry that
+	 * was learned is returned.
+	 *
+	 * @param arp ARP frame data
+	 * @param len Length of ARP frame (usually 28)
+	 * @param response Response buffer -- MUST be a minimum of ZT_ARP_BUF_LENGTH in size
+	 * @param responseLen Response length, or set to 0 if no response
+	 * @param responseDest Destination of response, or set to null if no response
+	 * @return IP address learned or 0 if no new IPs in cache
+	 */
+	uint32_t processIncomingArp(const void *arp,unsigned int len,void *response,unsigned int &responseLen,MAC &responseDest);
+
+	/**
+	 * Get the MAC corresponding to an IP, generating a query if needed
+	 *
+	 * This returns a MAC for a remote IP. The local MAC is returned for local
+	 * IPs as well. It may also generate a query if the IP is not known or the
+	 * entry needs to be refreshed. In this case queryLen will be set to a
+	 * non-zero value, so this should always be checked on return even if the
+	 * MAC returned is non-null.
+	 *
+	 * @param localMac Local MAC address of host interface
+	 * @param ip IP to look up
+	 * @param query Buffer for generated query -- MUST be a minimum of ZT_ARP_BUF_LENGTH in size
+	 * @param queryLen Length of generated query, or set to 0 if no query generated
+	 * @param queryDest Destination of query, or set to null if no query generated
+	 * @return MAC or 0 if no cached entry for this IP
+	 */
+	MAC query(const MAC &localMac,uint32_t ip,void *query,unsigned int &queryLen,MAC &queryDest);
+
+private:
+	struct _ArpEntry
+	{
+		_ArpEntry() : lastQuerySent(0),lastResponseReceived(0),mac(),local(false) {}
+		uint64_t lastQuerySent; // Time last query was sent or 0 for local IP
+		uint64_t lastResponseReceived; // Time of last ARP response or 0 for local IP
+		MAC mac; // MAC address of device responsible for IP or null if not known yet
+		bool local; // True if this is a local ARP entry
+	};
+
+	Hashtable< uint32_t,_ArpEntry > _cache;
+	uint64_t _lastCleaned;
+};
+
+} // namespace ZeroTier
+
+#endif