New super-packed dictionary -- we are going back to a backward compatibile format with the old netconf but in an embedded-friendly way. This is simpler.

2 files changed, 230 insertions, 426 deletions

diff --git a/node/Dictionary.cpp b/node/Dictionary.cpp
deleted file mode 100644
index b334066c..00000000
--- a/node/Dictionary.cpp
+++ /dev/null
@@ -1,245 +0,0 @@
-/*
- * ZeroTier One - Network Virtualization Everywhere
- * Copyright (C) 2011-2016  ZeroTier, Inc.  https://www.zerotier.com/
- *
- * 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/>.
- */
-
-#include "Dictionary.hpp"
-
-#ifdef ZT_SUPPORT_OLD_STYLE_NETCONF
-
-#include "C25519.hpp"
-#include "Identity.hpp"
-#include "Utils.hpp"
-
-namespace ZeroTier {
-
-Dictionary::iterator Dictionary::find(const std::string &key)
-{
-	for(iterator i(begin());i!=end();++i) {
-		if (i->first == key)
-			return i;
-	}
-	return end();
-}
-Dictionary::const_iterator Dictionary::find(const std::string &key) const
-{
-	for(const_iterator i(begin());i!=end();++i) {
-		if (i->first == key)
-			return i;
-	}
-	return end();
-}
-
-bool Dictionary::getBoolean(const std::string &key,bool dfl) const
-{
-	const_iterator e(find(key));
-	if (e == end())
-		return dfl;
-	if (e->second.length() < 1)
-		return dfl;
-	switch(e->second[0]) {
-		case '1':
-		case 't':
-		case 'T':
-		case 'y':
-		case 'Y':
-			return true;
-	}
-	return false;
-}
-
-std::string &Dictionary::operator[](const std::string &key)
-{
-	for(iterator i(begin());i!=end();++i) {
-		if (i->first == key)
-			return i->second;
-	}
-	push_back(std::pair<std::string,std::string>(key,std::string()));
-	std::sort(begin(),end());
-	for(iterator i(begin());i!=end();++i) {
-		if (i->first == key)
-			return i->second;
-	}
-	return front().second; // should be unreachable!
-}
-
-std::string Dictionary::toString() const
-{
-	std::string s;
-	for(const_iterator kv(begin());kv!=end();++kv) {
-		_appendEsc(kv->first.data(),(unsigned int)kv->first.length(),s);
-		s.push_back('=');
-		_appendEsc(kv->second.data(),(unsigned int)kv->second.length(),s);
-		s.append(ZT_EOL_S);
-	}
-	return s;
-}
-
-void Dictionary::updateFromString(const char *s,unsigned int maxlen)
-{
-	bool escapeState = false;
-	std::string keyBuf;
-	std::string *element = &keyBuf;
-	const char *end = s + maxlen;
-	while ((*s)&&(s < end)) {
-		if (escapeState) {
-			escapeState = false;
-			switch(*s) {
-				case '0':
-					element->push_back((char)0);
-					break;
-				case 'r':
-					element->push_back('\r');
-					break;
-				case 'n':
-					element->push_back('\n');
-					break;
-				default:
-					element->push_back(*s);
-					break;
-			}
-		} else {
-			if (*s == '\\') {
-				escapeState = true;
-			} else if (*s == '=') {
-				if (element == &keyBuf)
-					element = &((*this)[keyBuf]);
-			} else if ((*s == '\r')||(*s == '\n')) {
-				if ((element == &keyBuf)&&(keyBuf.length() > 0))
-					(*this)[keyBuf];
-				keyBuf = "";
-				element = &keyBuf;
-			} else element->push_back(*s);
-		}
-		++s;
-	}
-	if ((element == &keyBuf)&&(keyBuf.length() > 0))
-		(*this)[keyBuf];
-}
-
-void Dictionary::fromString(const char *s,unsigned int maxlen)
-{
-	clear();
-	updateFromString(s,maxlen);
-}
-
-void Dictionary::eraseKey(const std::string &key)
-{
-	for(iterator i(begin());i!=end();++i) {
-		if (i->first == key) {
-			this->erase(i);
-			return;
-		}
-	}
-}
-
-bool Dictionary::sign(const Identity &id,uint64_t now)
-{
-	try {
-		// Sign identity and timestamp fields too. If there's an existing
-		// signature, _mkSigBuf() ignores it.
-		char nows[32];
-		Utils::snprintf(nows,sizeof(nows),"%llx",(unsigned long long)now);
-		(*this)[ZT_DICTIONARY_SIGNATURE_IDENTITY] = id.toString(false);
-		(*this)[ZT_DICTIONARY_SIGNATURE_TIMESTAMP] = nows;
-
-		// Create a blob to hash and sign from fields in sorted order
-		std::string buf;
-		_mkSigBuf(buf);
-
-		// Add signature field
-		C25519::Signature sig(id.sign(buf.data(),(unsigned int)buf.length()));
-		(*this)[ZT_DICTIONARY_SIGNATURE] = Utils::hex(sig.data,(unsigned int)sig.size());
-
-		return true;
-	} catch ( ... ) {
-		// Probably means identity has no secret key field
-		removeSignature();
-		return false;
-	}
-}
-
-bool Dictionary::verify(const Identity &id) const
-{
-	try {
-		std::string buf;
-		_mkSigBuf(buf);
-		const_iterator sig(find(ZT_DICTIONARY_SIGNATURE));
-		if (sig == end())
-			return false;
-		std::string sigbin(Utils::unhex(sig->second));
-		return id.verify(buf.data(),(unsigned int)buf.length(),sigbin.data(),(unsigned int)sigbin.length());
-	} catch ( ... ) {
-		return false;
-	}
-}
-
-uint64_t Dictionary::signatureTimestamp() const
-{
-	const_iterator ts(find(ZT_DICTIONARY_SIGNATURE_TIMESTAMP));
-	if (ts == end())
-		return 0;
-	return Utils::hexStrToU64(ts->second.c_str());
-}
-
-void Dictionary::_mkSigBuf(std::string &buf) const
-{
-	unsigned long pairs = 0;
-	for(const_iterator i(begin());i!=end();++i) {
-		if (i->first != ZT_DICTIONARY_SIGNATURE) {
-			buf.append(i->first);
-			buf.push_back('=');
-			buf.append(i->second);
-			buf.push_back('\0');
-			++pairs;
-		}
-	}
-	buf.push_back((char)0xff);
-	buf.push_back((char)((pairs >> 24) & 0xff)); // pad with number of key/value pairs at end
-	buf.push_back((char)((pairs >> 16) & 0xff));
-	buf.push_back((char)((pairs >> 8) & 0xff));
-	buf.push_back((char)(pairs & 0xff));
-}
-
-void Dictionary::_appendEsc(const char *data,unsigned int len,std::string &to)
-{
-	for(unsigned int i=0;i<len;++i) {
-		switch(data[i]) {
-			case 0:
-				to.append("\\0");
-				break;
-			case '\r':
-				to.append("\\r");
-				break;
-			case '\n':
-				to.append("\\n");
-				break;
-			case '\\':
-				to.append("\\\\");
-				break;
-			case '=':
-				to.append("\\=");
-				break;
-			default:
-				to.push_back(data[i]);
-				break;
-		}
-	}
-}
-
-} // namespace ZeroTier
-
-#endif // ZT_SUPPORT_OLD_STYLE_NETCONF
diff --git a/node/Dictionary.hpp b/node/Dictionary.hpp
index d4cdd230..66072952 100644
--- a/node/Dictionary.hpp
+++ b/node/Dictionary.hpp
@@ -20,261 +20,310 @@
 #define ZT_DICTIONARY_HPP
 
 #include "Constants.hpp"
-
-#ifdef ZT_SUPPORT_OLD_STYLE_NETCONF
+#include "Utils.hpp"
 
 #include <stdint.h>
 
 #include <string>
-#include <vector>
-#include <stdexcept>
-#include <algorithm>
-
-#include "Utils.hpp"
 
-// Three fields are added/updated by sign()
-#define ZT_DICTIONARY_SIGNATURE "~!ed25519"
-#define ZT_DICTIONARY_SIGNATURE_IDENTITY "~!sigid"
-#define ZT_DICTIONARY_SIGNATURE_TIMESTAMP "~!sigts"
+#define ZT_DICTIONARY_MAX_SIZE 16384
 
 namespace ZeroTier {
 
-class Identity;
-
 /**
- * Simple key/value dictionary with string serialization
+ * A small key=value store
+ *
+ * This stores data in the form of a blob of max size ZT_DICTIONARY_MAX_SIZE.
+ * It's *technically* human-readable to be backward compatible with old format
+ * netconfs, but it can store binary data and doing this will negatively impact
+ * its human-readability.
  *
- * The serialization format is a flat key=value with backslash escape.
- * It does not support comments or other syntactic complexities. It is
- * human-readable if the keys and values in the dictionary are also
- * human-readable. Otherwise it might contain unprintable characters.
+ * In any case nulls are always escaped, making the serialized form of this
+ * object a valid null-terminated C-string. Appending it to a buffer appends
+ * it as such.
  *
- * Keys beginning with "~!" are reserved for signature data fields.
+ * Keys cannot contain binary data, CR/LF, nulls, or the equals (=) sign.
+ * Adding such a key will result in an invalid entry (but isn't dangerous).
  *
- * It's stored as a simple vector and can be linearly scanned or
- * binary searched. Dictionaries are only used for very small things
- * outside the core loop, so this is not a significant performance
- * issue and it reduces memory use and code footprint.
+ * There is code to test and fuzz this in selftest.cpp.
  */
-class Dictionary : public std::vector< std::pair<std::string,std::string> >
+class Dictionary
 {
 public:
-	Dictionary() {}
-
-	/**
-	 * @param s String-serialized dictionary
-	 * @param maxlen Maximum length of buffer
-	 */
-	Dictionary(const char *s,unsigned int maxlen) { fromString(s,maxlen); }
-
-	/**
-	 * @param s String-serialized dictionary
-	 */
-	Dictionary(const std::string &s) { fromString(s.c_str(),(unsigned int)s.length()); }
-
-	iterator find(const std::string &key);
-	const_iterator find(const std::string &key) const;
-
-	/**
-	 * Get a key, returning a default if not present
-	 *
-	 * @param key Key to look up
-	 * @param dfl Default if not present
-	 * @return Value or default
-	 */
-	inline const std::string &get(const std::string &key,const std::string &dfl) const
+	Dictionary()
 	{
-		const_iterator e(find(key));
-		if (e == end())
-			return dfl;
-		return e->second;
+		_d[0] = (char)0;
 	}
 
-	/**
-	 * @param key Key to get
-	 * @param dfl Default boolean result if key not found or empty (default: false)
-	 * @return Boolean value of key
-	 */
-	bool getBoolean(const std::string &key,bool dfl = false) const;
+	Dictionary(const char *s)
+	{
+		Utils::scopy(_d,sizeof(_d),s);
+	}
 
-	/**
-	 * @param key Key to get
-	 * @param dfl Default value if not present (default: 0)
-	 * @return Value converted to unsigned 64-bit int or 0 if not found
-	 */
-	inline uint64_t getUInt(const std::string &key,uint64_t dfl = 0) const
+	inline void load(const char *s)
 	{
-		const_iterator e(find(key));
-		if (e == end())
-			return dfl;
-		return Utils::strToU64(e->second.c_str());
+		Utils::scopy(_d,sizeof(_d),s);
 	}
 
 	/**
-	 * @param key Key to get
-	 * @param dfl Default value if not present (default: 0)
-	 * @return Value converted to unsigned 64-bit int or 0 if not found
+	 * Delete all entries
 	 */
-	inline uint64_t getHexUInt(const std::string &key,uint64_t dfl = 0) const
+	inline void clear()
 	{
-		const_iterator e(find(key));
-		if (e == end())
-			return dfl;
-		return Utils::hexStrToU64(e->second.c_str());
+		_d[0] = (char)0;
 	}
 
 	/**
-	 * @param key Key to get
-	 * @param dfl Default value if not present (default: 0)
-	 * @return Value converted to signed 64-bit int or 0 if not found
+	 * @return Size of dictionary in bytes not including terminating NULL
 	 */
-	inline int64_t getInt(const std::string &key,int64_t dfl = 0) const
+	inline unsigned int sizeBytes() const
 	{
-		const_iterator e(find(key));
-		if (e == end())
-			return dfl;
-		return Utils::strTo64(e->second.c_str());
+		for(unsigned int i=0;i<ZT_DICTIONARY_MAX_SIZE;++i) {
+			if (!_d[i])
+				return i;
+		}
+		return ZT_DICTIONARY_MAX_SIZE;
 	}
 
-	std::string &operator[](const std::string &key);
-
 	/**
-	 * @param key Key to set
-	 * @param value String value
+	 * Get an entry
+	 *
+	 * Note that to get binary values, dest[] should be at least one more than
+	 * the maximum size of the value being retrieved. That's because even if
+	 * the data is binary a terminating 0 is appended to dest[].
+	 *
+	 * If the key is not found, dest[0] is set to 0 to make dest[] an empty
+	 * C string in that case. The dest[] array will *never* be unterminated.
+	 *
+	 * @param key Key to look up
+	 * @param dest Destination buffer
+	 * @param destlen Size of destination buffer
+	 * @return -1 if not found, or actual number of bytes stored in dest[] minus trailing 0
 	 */
-	inline void set(const std::string &key,const char *value)
+	inline int get(const char *key,char *dest,unsigned int destlen) const
 	{
-		(*this)[key] = value;
+		const char *p = _d;
+		const char *const eof = p + ZT_DICTIONARY_MAX_SIZE;
+		const char *k,*s;
+		unsigned int dptr = 0;
+		bool esc;
+		int j;
+
+		for(;;) {
+			s = p;
+			for(;;) {
+				if ((*p == '\r')||(*p == '\n')||(*p == '=')||(!*p)) {
+					k = key;
+					while ((*k)&&(s != p)) {
+						if (*(k++) != *(s++))
+							break;
+					}
+					if (*k) {
+						esc = false;
+						for(;;) {
+							if (!*p) {
+								dest[0] = (char)0;
+								return -1;
+							} else if (esc) {
+								esc = false;
+							} else if (*p == '\\') {
+								esc = true;
+							} else if ((*p == '\r')||(*p == '\n')) {
+								++p;
+								break;
+							}
+							++p;
+						}
+						break;
+					} else {
+						if (*p == '=') ++p;
+						esc = false;
+						j = 0;
+						for(;;) {
+							if (esc) {
+								esc = false;
+								if (j >= destlen) {
+									dest[destlen-1] = (char)0;
+									return (int)(destlen-1);
+								}
+								switch(*p) {
+									case 'r':
+										dest[j++] = '\r';
+										break;
+									case 'n':
+										dest[j++] = '\n';
+										break;
+									case 't':
+										dest[j++] = '\t';
+										break;
+									case '0':
+										dest[j++] = (char)0;
+										break;
+									default:
+										dest[j++] = *p;
+								}
+							} else if (*p == '\\') {
+								esc = true;
+							} else if ((*p == '\r')||(*p == '\n')||(!*p)) {
+								dest[j] = (char)0;
+								return j;
+							} else {
+								if (j >= destlen) {
+									dest[destlen-1] = (char)0;
+									return (int)(destlen-1);
+								}
+								dest[j++] = *p;
+							}
+							++p;
+						}
+					}
+				} else {
+					++p;
+				}
+			}
+		}
 	}
 
 	/**
-	 * @param key Key to set
-	 * @param value String value
+	 * @param key Key to look up
+	 * @param dfl Default value if not found in dictionary (a key with an empty value is considered not found)
+	 * @return Boolean value of key or 'dfl' if not found
 	 */
-	inline void set(const std::string &key,const std::string &value)
+	bool getBoolean(const char *key,bool dfl = false) const
 	{
-		(*this)[key] = value;
+		char tmp[128];
+		if (this->get(key,tmp,sizeof(tmp)) >= 1) {
+			switch(tmp[0]) {
+				case '1':
+				case 't':
+				case 'T':
+				case 'y':
+				case 'Y':
+					return true;
+				default:
+					return false;
+			}
+		}
+		return dfl;
 	}
 
 	/**
-	 * @param key Key to set
-	 * @param value Boolean value
+	 * @param key Key to look up
+	 * @param dfl Default value or 0 if unspecified
+	 * @return Decoded hex UInt value or 'dfl' if not found
 	 */
-	inline void set(const std::string &key,bool value)
+	inline uint64_t getHexUInt(const char *key,uint64_t dfl = 0) const
 	{
-		(*this)[key] = ((value) ? "1" : "0");
+		char tmp[128];
+		if (this->get(key,tmp,sizeof(tmp)) >= 1)
+			return Utils::hexStrToU64(tmp);
+		return dfl;
 	}
 
 	/**
-	 * @param key Key to set
-	 * @param value Integer value
+	 * Add a new key=value pair
+	 *
+	 * If the key is already present this will append another, but the first
+	 * will always be returned by get(). There is no erase(). This is designed
+	 * to be generated and shipped, not as an editable data structure.
+	 *
+	 * @param key Key -- nulls, CR/LF, and equals (=) are illegal characters
+	 * @param value Value to set
+	 * @param vlen Length of value in bytes or -1 to treat value[] as a C-string and look for terminating 0
+	 * @return True if there was enough room to add this key=value pair
 	 */
-	inline void set(const std::string &key,uint64_t value)
+	inline bool add(const char *key,const char *value,int vlen = -1)
 	{
-		char tmp[24];
-		Utils::snprintf(tmp,sizeof(tmp),"%llu",(unsigned long long)value);
-		(*this)[key] = tmp;
+		for(unsigned int i=0;i<ZT_DICTIONARY_MAX_SIZE;++i) {
+			if (!_d[i]) {
+				unsigned int j = i;
+				const char *p = key;
+				while (*p) {
+					_d[j++] = *(p++);
+					if (j == ZT_DICTIONARY_MAX_SIZE) {
+						_d[i] = (char)0;
+						return false;
+					}
+				}
+				p = value;
+				int k = 0;
+				while ((*p)&&((vlen < 0)||(k < vlen))) {
+					switch(*p) {
+						case '\r':
+						case '\n':
+						case '\0':
+						case '\t':
+							_d[j++] = '\\';
+							if (j == ZT_DICTIONARY_MAX_SIZE) {
+								_d[i] = (char)0;
+								return false;
+							}
+							switch(*p) {
+								case '\r': _d[j++] = 'r'; break;
+								case '\n': _d[j++] = 'n'; break;
+								case '\0': _d[j++] = '0'; break;
+								case '\t': _d[j++] = 't'; break;
+							}
+							if (j == ZT_DICTIONARY_MAX_SIZE) {
+								_d[i] = (char)0;
+								return false;
+							}
+							break;
+						default:
+							_d[j++] = *p;
+							if (j == ZT_DICTIONARY_MAX_SIZE) {
+								_d[i] = (char)0;
+								return false;
+							}
+							break;
+					}
+					++p;
+					++k;
+				}
+				_d[j++] = (char)0;
+				return true;
+			}
+		}
+		return false;
 	}
 
 	/**
-	 * @param key Key to set
-	 * @param value Integer value
+	 * Add a boolean as a '1' or a '0'
 	 */
-	inline void set(const std::string &key,int64_t value)
+	inline void add(const char *key,bool value)
 	{
-		char tmp[24];
-		Utils::snprintf(tmp,sizeof(tmp),"%lld",(long long)value);
-		(*this)[key] = tmp;
+		this->add(key,(value) ? "1" : "0",1);
 	}
 
-	/**
-	 * @param key Key to set
-	 * @param value Integer value
+	/** 
+	 * Add a 64-bit integer (unsigned) as a hex value
 	 */
-	inline void setHex(const std::string &key,uint64_t value)
+	inline void add(const char *key,uint64_t value)
 	{
-		char tmp[24];
+		char tmp[128];
 		Utils::snprintf(tmp,sizeof(tmp),"%llx",(unsigned long long)value);
-		(*this)[key] = tmp;
+		this->add(key,tmp,-1);
 	}
 
 	/**
 	 * @param key Key to check
-	 * @return True if dictionary contains key
-	 */
-	inline bool contains(const std::string &key) const { return (find(key) != end()); }
-
-	/**
-	 * @return String-serialized dictionary
-	 */
-	std::string toString() const;
-
-	/**
-	 * Clear and initialize from a string
-	 *
-	 * @param s String-serialized dictionary
-	 * @param maxlen Maximum length of string buffer
-	 */
-	void fromString(const char *s,unsigned int maxlen);
-	inline void fromString(const std::string &s) { fromString(s.c_str(),(unsigned int)s.length()); }
-	void updateFromString(const char *s,unsigned int maxlen);
-	inline void update(const char *s,unsigned int maxlen) { updateFromString(s, maxlen); }
-	inline void update(const std::string &s) { updateFromString(s.c_str(),(unsigned int)s.length()); }
-
-	/**
-	 * @return True if this dictionary is cryptographically signed
-	 */
-	inline bool hasSignature() const { return (find(ZT_DICTIONARY_SIGNATURE) != end()); }
-
-	/**
-	 * @return Signing identity in string-serialized format or empty string if none
+	 * @return True if key is present
 	 */
-	inline std::string signingIdentity() const { return get(ZT_DICTIONARY_SIGNATURE_IDENTITY,std::string()); }
-
-	/**
-	 * @return Signature timestamp in milliseconds since epoch or 0 if none
-	 */
-	uint64_t signatureTimestamp() const;
-
-	/**
-	 * @param key Key to erase
-	 */
-	void eraseKey(const std::string &key);
-
-	/**
-	 * Remove any signature from this dictionary
-	 */
-	inline void removeSignature()
+	inline bool contains(const char *key) const
 	{
-		eraseKey(ZT_DICTIONARY_SIGNATURE);
-		eraseKey(ZT_DICTIONARY_SIGNATURE_IDENTITY);
-		eraseKey(ZT_DICTIONARY_SIGNATURE_TIMESTAMP);
+		char tmp[2];
+		return (this->get(key,tmp,2) >= 0);
 	}
 
 	/**
-	 * Add or update signature fields with a signature of all other keys and values
-	 *
-	 * @param with Identity to sign with (must have secret key)
-	 * @param now Current time
-	 * @return True on success
+	 * @return Dictionary data as a 0-terminated C-string
 	 */
-	bool sign(const Identity &id,uint64_t now);
-
-	/**
-	 * Verify signature against an identity
-	 *
-	 * @param id Identity to verify against
-	 * @return True if signature verification OK
-	 */
-	bool verify(const Identity &id) const;
+	inline const char *data() const { return _d; }
 
 private:
-	void _mkSigBuf(std::string &buf) const;
-	static void _appendEsc(const char *data,unsigned int len,std::string &to);
+	char _d[ZT_DICTIONARY_MAX_SIZE];
 };
 
 } // namespace ZeroTier
 
-#endif // ZT_SUPPORT_OLD_STYLE_NETCONF
-
 #endif