core: Add Mtree
Change-Id: I80205fb0d1f4ee5bcbc6c73651bb697fe854bf53
diff --git a/core/merkle-tree-cache.cpp b/core/merkle-tree-cache.cpp
new file mode 100644
index 0000000..a7f2dc0
--- /dev/null
+++ b/core/merkle-tree-cache.cpp
@@ -0,0 +1,353 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL 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.
+ *
+ * NSL 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
+ * NSL, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * @author Peizhen Guo <patrick.guopz@gmail.com>
+ */
+
+#include "merkle-tree-cache.hpp"
+
+
+
+namespace nsl {
+
+typedef std::map<Index, int>::iterator tree_iter;
+typedef std::map<uint64_t, ndn::ConstBufferPtr>::iterator leaf_iter;
+
+Index
+MerkleTreeCache::findSubTree(Index nodeIndex)
+{
+ if(nodeIndex.level % 6 == 0 && nodeIndex.level != 0)
+ {
+ return nodeIndex;
+ }
+ else
+ {
+ uint8_t step = (uint64_t(nodeIndex.level / 6) + 1) * 6 - nodeIndex.level;
+ for (int i = 0; i < step; i++)
+ {
+ nodeIndex.number -= nodeIndex.number % int(pow(2, nodeIndex.level + 1));
+ nodeIndex.level += 1;
+ }
+ return nodeIndex;
+ }
+}
+
+Index
+MerkleTreeCache::getParentRootIndex(Index thisRootIndex)
+{
+ Index parentIndex;
+ parentIndex.number = thisRootIndex.number;
+ parentIndex.level = thisRootIndex.level;
+ for (int i = 0; i < 6; i++)
+ {
+ parentIndex.number -= parentIndex.number%int(pow(2, parentIndex.level + 1));
+ parentIndex.level += 1;
+ }
+ return parentIndex;
+}
+
+
+void
+MerkleTreeCache::removeSubTree()
+{
+ if (doesCacheFull() > 1)
+ {
+ // find out the least recent used subtree
+ tree_iter _i = m_timeFromLastUse.begin();
+ int idle_time_max = -1;
+ Index rm_index_max = _i->first;
+ int idle_time_min = _i->second;
+ Index rm_index_min = _i->first;
+ for (_i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
+ {
+ if (_i->second > idle_time_max && m_cachedTree[_i->first]->getRemainPosition() == 0)
+ {
+ idle_time_max = _i->second;
+ rm_index_max = _i->first;
+ }
+ if (_i->second < idle_time_min)
+ {
+ idle_time_min = _i->second;
+ rm_index_min = _i->first;
+ }
+ }
+
+ // refresh the timer
+ for (_i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
+ {
+ _i->second -= idle_time_min;
+ }
+ // update to database and remove subtree from cache and timer,only when there is full subtree
+ if (m_cachedTree[rm_index_max]->getRemainPosition() == 0 && idle_time_max >= 0)
+ {
+ m_database.addSubTree(m_cachedTree[rm_index_max]);
+ m_cachedTree.erase(rm_index_max);
+ m_timeFromLastUse.erase(rm_index_max);
+ }
+ }
+}
+
+void
+MerkleTreeCache::removeLeaf()
+{
+ if (doesCacheFull() % 2 != 0)
+ {
+ // randomly pick a old leaf to remove
+ leaf_iter _i = m_leavesData.begin();
+ while (_i->first == m_nLeaves - 1)
+ {
+ _i++;
+ }
+ m_database.addLeafInfo(_i->first, _i->second);
+ m_leavesData.erase(_i->first);
+ }
+}
+
+
+
+
+
+// Do not have to deal with NOT-IN-MEMORY issue because not full tree will not in database
+void
+MerkleTreeCache::addLeaf(Leaf newLeaf)
+{
+ ndn::ConstBufferPtr data = newLeaf.getData();
+ removeLeaf(); // test whether is full, if so, delete an old item
+ m_leavesData[newLeaf.getIndex().number] = data;
+ Index leafIndex = newLeaf.getIndex();
+ ndn::ConstBufferPtr hash = newLeaf.getHash();
+
+ Index subTreeRoot = findSubTree(leafIndex);
+ if (m_nLeaves > 0)
+ {
+ // Not full so that always in memory
+ m_cachedTree[subTreeRoot]->addNode(hash);
+ m_nLeaves += 1;
+ }
+ else
+ {
+ SubTreePtr newTree(new SubTree(subTreeRoot,
+ ndn::bind(&MerkleTreeCache::update, this,
+ subTreeRoot, _1, _2)));
+ newTree->addNode(hash);
+ removeSubTree();
+ m_cachedTree[subTreeRoot] = newTree;
+ m_nLeaves = 1;
+ m_nLevels = 1;
+ }
+
+ for (tree_iter _i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
+ {
+ _i->second += 1;
+ }
+ m_timeFromLastUse[subTreeRoot] = 0; // if not exist, automatically create one and set to 0
+}
+
+
+// Deal with loading from database
+// database update
+// consider add to database when a subtree is full
+void
+MerkleTreeCache::update(Index subRootIndex, uint8_t subRemainNum, ndn::ConstBufferPtr subRootHash)
+{
+ if ((subRootIndex.level / 6) < m_nLevels)
+ {
+ Index parentRoot = getParentRootIndex(subRootIndex);
+
+ // bring in memory if parentRoot not in
+ if (m_cachedTree.count(parentRoot) <= 0)
+ {
+ loadSubTreeFromDatabase(parentRoot);
+ }
+ m_cachedTree[parentRoot]->updateLeafHash(subRootIndex, subRootHash);
+ m_timeFromLastUse[parentRoot] = 0;
+ }
+
+ if (subRemainNum == 0) // add the current full subtree into the database
+ {
+ Index parentRoot = getParentRootIndex(subRootIndex);
+ if ((subRootIndex.level / 6) >= m_nLevels) // if it is the top subtree
+ {
+ SubTreePtr newTree(new SubTree(parentRoot,
+ ndn::bind(&MerkleTreeCache::update, this,
+ parentRoot, _1, _2)));
+ removeSubTree();
+ m_cachedTree[parentRoot] = newTree;
+ m_nLevels += 1;
+ m_timeFromLastUse[parentRoot] = 0;
+ m_cachedTree[parentRoot]->updateLeafHash(subRootIndex, subRootHash);
+ }
+ Index newRoot;
+ newRoot.level = subRootIndex.level;
+ newRoot.number = subRootIndex.number + int(pow(2, subRootIndex.level));
+ // whether the updated subtree is already full,
+ // but its child subtree is not full.
+ // To avoid create multiple sibling new subtree
+ if (m_cachedTree.count(newRoot) == 0)
+ {
+ SubTreePtr newTree(new SubTree(newRoot,
+ ndn::bind(&MerkleTreeCache::update, this,
+ newRoot, _1, _2)));
+ removeSubTree();
+ m_cachedTree[newRoot] = newTree;
+ m_timeFromLastUse[newRoot] = 0;
+ }
+ }
+}
+
+
+NodePtr
+MerkleTreeCache::queryNode(Index nodeIndex)
+{
+ // update timer
+ for (tree_iter _i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
+ {
+ _i->second += 1;
+ }
+
+ Index rootIndex = findSubTree(nodeIndex);
+ ndn::ConstBufferPtr hash;
+ if (m_cachedTree.count(rootIndex) == 0)
+ {
+ loadSubTreeFromDatabase(rootIndex);
+ }
+ hash = m_cachedTree[rootIndex]->getHash(nodeIndex);
+
+ if (nodeIndex.level == 0)
+ {
+ if (m_leavesData.count(nodeIndex.number) == 0)
+ {
+ loadLeafFromDatabase(nodeIndex.number);
+ }
+ NodePtr node_ptr(new Leaf(m_leavesData[nodeIndex.number],
+ nodeIndex.number, nodeIndex.level, 0));
+ node_ptr->setHash(hash);
+ return node_ptr;
+ }
+ else
+ {
+ NodePtr node_ptr(new IntermediateNode(nodeIndex.number, nodeIndex.level, 0));
+ node_ptr->setHash(hash);
+ ((IntermediateNode*)node_ptr.get())->setIsFull(m_nLeaves);
+ return node_ptr;
+ }
+}
+
+
+bool
+MerkleTreeCache::doesNodeExist(Index nodeIndex)
+{
+ Index rootIndex = findSubTree(nodeIndex);
+ if (m_cachedTree.count(rootIndex) > 0)
+ {
+ return true;
+ }
+ else
+ {
+ bool result = m_database.doesSubTreeExist(rootIndex);
+ return result;
+ }
+}
+
+
+
+SubTreePtr
+MerkleTreeCache::decoding(std::string subTreeInfo)
+{
+ uint64_t seq = 0;
+ unsigned char tmp = 0;
+ for (int i = 7; i >= 0; i--)
+ {
+ tmp = subTreeInfo[i];
+ seq += tmp;
+ seq = seq << 8;
+ }
+ seq = seq >> 8;
+ uint64_t lev = 0;
+ for (int i = 15; i >= 8; i--)
+ {
+ tmp = subTreeInfo[i];
+ lev += tmp;
+ lev = lev << 8;
+ }
+ lev = lev >> 8;
+ Index rootIndex;
+ rootIndex.number = seq;
+ rootIndex.level = lev;
+ SubTreePtr newTree(new SubTree(rootIndex,
+ ndn::bind(&MerkleTreeCache::update, this,
+ rootIndex, _1, _2)));
+ uint8_t remain = subTreeInfo[16]; // not useful
+ if (remain == 0)
+ {
+ std::vector<ndn::BufferPtr> hashes;
+ for (int i = 0; i < 127; i++)
+ {
+ ndn::Buffer buf;
+ for(int j = 17 + 32 * i; j < 49 + 32 * i; j++)
+ {
+ buf.push_back(subTreeInfo[j]);
+ }
+ ndn::BufferPtr thisBuf = ndn::make_shared<ndn::Buffer>(buf);
+ hashes.push_back(thisBuf);
+ }
+ newTree->resumeFromString(remain, hashes);
+ return newTree;
+ }
+ else
+ {
+ std::vector<ndn::BufferPtr> hashes;
+ uint8_t lastNo = 126 - remain;
+ for (int i = 63; i <= lastNo; i++)
+ {
+ ndn::Buffer buf;
+ for(int j = 17 + 32 * i; j < 49 + 32 * i; j++)
+ {
+ buf.push_back(subTreeInfo[j]);
+ }
+ ndn::BufferPtr thisBuf = ndn::make_shared<ndn::Buffer>(buf);
+ hashes.push_back(thisBuf);
+ }
+ newTree->resumeFromString(remain, hashes);
+ return newTree;
+ }
+}
+
+
+void
+MerkleTreeCache::loadSubTreeFromDatabase(Index rootIndex)
+{
+ // Detect the cache limitation
+ removeSubTree();
+ std::string tmp_str = m_database.getSubTree(rootIndex);
+ SubTreePtr newtree = decoding(tmp_str);
+ m_cachedTree[rootIndex] = newtree;
+ m_timeFromLastUse[rootIndex] = 0;
+}
+
+void
+MerkleTreeCache::loadLeafFromDatabase(uint64_t sequence)
+{
+ // Detect the cache limitation
+ removeLeaf();
+ ndn::ConstBufferPtr newleaf = m_database.getLeafInfo(sequence);
+ m_leavesData[sequence] = newleaf;
+}
+
+
+} // namespace nsl