| /* -*- 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 |