table: Content Store performance fix
Change-Id: I7f6752ec279e64e81c90c0b3e8d756da34194965
Refs: #1432
diff --git a/daemon/common.hpp b/daemon/common.hpp
index 974fa57..e60dbc7 100644
--- a/daemon/common.hpp
+++ b/daemon/common.hpp
@@ -79,6 +79,7 @@
using ndn::Interest;
using ndn::Data;
using ndn::Name;
+namespace name = ndn::name;
using ndn::Exclude;
using ndn::Block;
namespace tlv {
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index 0708de4..447c710 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -32,42 +32,22 @@
NFD_LOG_INIT("CsEntry");
-Entry::Entry(const Data& data, bool isUnsolicited)
- : m_dataPacket(data.shared_from_this())
- , m_isUnsolicited(isUnsolicited)
- , m_wasRefreshedByDuplicate(false)
- , m_nameWithDigest(data.getName())
+void
+Entry::release()
{
- updateStaleTime();
- m_nameWithDigest.append(ndn::name::Component(getDigest()));
-}
+ BOOST_ASSERT(m_layerIterators.empty());
-
-Entry::~Entry()
-{
-}
-
-const Name&
-Entry::getName() const
-{
- return m_nameWithDigest;
-}
-
-const Data&
-Entry::getData() const
-{
- return *m_dataPacket;
+ m_dataPacket.reset();
+ m_digest.reset();
+ m_nameWithDigest.clear();
}
void
-Entry::setData(const Data& data)
+Entry::setData(const Data& data, bool isUnsolicited)
{
- /// \todo This method may not be necessary (if it is real duplicate,
- /// there is no reason to recalculate the same digest
-
+ m_isUnsolicited = isUnsolicited;
m_dataPacket = data.shared_from_this();
m_digest.reset();
- m_wasRefreshedByDuplicate = true;
updateStaleTime();
@@ -76,14 +56,10 @@
}
void
-Entry::setData(const Data& data, const ndn::ConstBufferPtr& digest)
+Entry::setData(const Data& data, bool isUnsolicited, const ndn::ConstBufferPtr& digest)
{
- /// \todo This method may not be necessary (if it is real duplicate,
- /// there is no reason to recalculate the same digest
-
m_dataPacket = data.shared_from_this();
m_digest = digest;
- m_wasRefreshedByDuplicate = true;
updateStaleTime();
@@ -91,30 +67,12 @@
m_nameWithDigest.append(ndn::name::Component(getDigest()));
}
-bool
-Entry::isUnsolicited() const
-{
- return m_isUnsolicited;
-}
-
-const time::steady_clock::TimePoint&
-Entry::getStaleTime() const
-{
- return m_staleAt;
-}
-
void
Entry::updateStaleTime()
{
m_staleAt = time::steady_clock::now() + m_dataPacket->getFreshnessPeriod();
}
-bool
-Entry::wasRefreshedByDuplicate() const
-{
- return m_wasRefreshedByDuplicate;
-}
-
const ndn::ConstBufferPtr&
Entry::getDigest() const
{
@@ -139,12 +97,6 @@
m_layerIterators.erase(layer);
}
-const Entry::LayerIterators&
-Entry::getIterators() const
-{
- return m_layerIterators;
-}
-
void
Entry::printIterators() const
{
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index be26645..ce3d538 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -41,11 +41,14 @@
class Entry : noncopyable
{
public:
- typedef std::map<int, std::list< shared_ptr<Entry> >::iterator> LayerIterators;
+ typedef std::map<int, std::list<Entry*>::iterator > LayerIterators;
- Entry(const Data& data, bool isUnsolicited = false);
+ Entry();
- ~Entry();
+ /** \brief releases reference counts on shared objects
+ */
+ void
+ release();
/** \brief returns the name of the Data packet stored in the CS entry
* \return{ NDN name }
@@ -60,11 +63,6 @@
bool
isUnsolicited() const;
- /** \brief Returns True if CS entry was refreshed by a duplicate Data packet
- */
- bool
- wasRefreshedByDuplicate() const;
-
/** \brief returns the absolute time when Data becomes expired
* \return{ Time (resolution up to time::milliseconds) }
*/
@@ -79,12 +77,12 @@
/** \brief changes the content of CS entry and recomputes digest
*/
void
- setData(const Data& data);
+ setData(const Data& data, bool isUnsolicited);
/** \brief changes the content of CS entry and modifies digest
*/
void
- setData(const Data& data, const ndn::ConstBufferPtr& digest);
+ setData(const Data& data, bool isUnsolicited, const ndn::ConstBufferPtr& digest);
/** \brief refreshes the time when Data becomes expired
* according to the current absolute time.
@@ -123,8 +121,6 @@
shared_ptr<const Data> m_dataPacket;
bool m_isUnsolicited;
- bool m_wasRefreshedByDuplicate;
-
Name m_nameWithDigest;
mutable ndn::ConstBufferPtr m_digest;
@@ -132,6 +128,41 @@
LayerIterators m_layerIterators;
};
+inline
+Entry::Entry()
+{
+}
+
+inline const Name&
+Entry::getName() const
+{
+ return m_nameWithDigest;
+}
+
+inline const Data&
+Entry::getData() const
+{
+ return *m_dataPacket;
+}
+
+inline bool
+Entry::isUnsolicited() const
+{
+ return m_isUnsolicited;
+}
+
+inline const time::steady_clock::TimePoint&
+Entry::getStaleTime() const
+{
+ return m_staleAt;
+}
+
+inline const Entry::LayerIterators&
+Entry::getIterators() const
+{
+ return m_layerIterators;
+}
+
} // namespace cs
} // namespace nfd
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 3add035..c86ba54 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -26,11 +26,10 @@
#include "cs.hpp"
#include "core/logger.hpp"
-
#include <ndn-cpp-dev/util/crypto.hpp>
#define SKIPLIST_MAX_LAYERS 32
-#define SKIPLIST_PROBABILITY 50 // 50% ( p = 1/2 )
+#define SKIPLIST_PROBABILITY 25 // 25% (p = 1/4)
NFD_LOG_INIT("ContentStore");
@@ -38,21 +37,34 @@
Cs::Cs(int nMaxPackets)
: m_nMaxPackets(nMaxPackets)
+ , m_nPackets(0)
{
- srand (time::toUnixTimestamp(time::system_clock::now()).count());
SkipListLayer* zeroLayer = new SkipListLayer();
m_skipList.push_back(zeroLayer);
+
+ for (size_t i = 0; i < m_nMaxPackets; i++)
+ m_freeCsEntries.push(new cs::Entry());
}
Cs::~Cs()
{
- /// \todo Fix memory leak
+ // evict all items from CS
+ while (evictItem())
+ ;
+
+ BOOST_ASSERT(m_freeCsEntries.size() == m_nMaxPackets);
+
+ while (!m_freeCsEntries.empty())
+ {
+ delete m_freeCsEntries.front();
+ m_freeCsEntries.pop();
+ }
}
size_t
Cs::size() const
{
- return (*m_skipList.begin())->size(); // size of the first layer in a skip list
+ return m_nPackets; // size of the first layer in a skip list
}
void
@@ -62,7 +74,8 @@
while (isFull())
{
- evictItem();
+ if (!evictItem())
+ break;
}
}
@@ -73,13 +86,20 @@
}
//Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
-std::pair< shared_ptr<cs::Entry>, bool>
+std::pair<cs::Entry*, bool>
Cs::insertToSkipList(const Data& data, bool isUnsolicited)
{
NFD_LOG_TRACE("insertToSkipList() " << data.getName() << ", "
<< "skipList size " << size());
- shared_ptr<cs::Entry> entry = make_shared<cs::Entry>(data, isUnsolicited);
+ BOOST_ASSERT(m_cleanupIndex.size() <= size());
+ BOOST_ASSERT(m_freeCsEntries.size() > 0);
+
+ // take entry for the memory pool
+ cs::Entry* entry = m_freeCsEntries.front();
+ m_freeCsEntries.pop();
+ m_nPackets++;
+ entry->setData(data, isUnsolicited);
bool insertInFront = false;
bool isIterated = false;
@@ -87,14 +107,14 @@
SkipListLayer::iterator updateTable[SKIPLIST_MAX_LAYERS];
SkipListLayer::iterator head = (*topLayer)->begin();
- if ( !(*topLayer)->empty() )
+ if (!(*topLayer)->empty())
{
//start from the upper layer towards bottom
int layer = m_skipList.size() - 1;
for (SkipList::reverse_iterator rit = topLayer; rit != m_skipList.rend(); ++rit)
{
//if we didn't do any iterations on the higher layers, start from the begin() again
- if ( !isIterated )
+ if (!isIterated)
head = (*rit)->begin();
updateTable[layer] = head;
@@ -102,7 +122,7 @@
if (head != (*rit)->end())
{
// it can happen when begin() contains the element in front of which we need to insert
- if ( !isIterated && ((*head)->getName() >= entry->getName()) )
+ if (!isIterated && ((*head)->getName() >= entry->getName()))
{
--updateTable[layer];
insertInFront = true;
@@ -153,6 +173,11 @@
(*head)->setData(data, entry->getDigest()); //updates stale time
+ // new entry not needed, returning to the pool
+ entry->release();
+ m_freeCsEntries.push(entry);
+ m_nPackets--;
+
return std::make_pair(*head, false);
}
@@ -160,7 +185,7 @@
size_t randomLayer = pickRandomLayer();
- while ( m_skipList.size() < randomLayer + 1)
+ while (m_skipList.size() < randomLayer + 1)
{
SkipListLayer* newLayer = new SkipListLayer();
m_skipList.push_back(newLayer);
@@ -198,8 +223,6 @@
layer++;
}
- printSkipList();
-
return std::make_pair(entry, true);
}
@@ -214,17 +237,12 @@
}
//pointer and insertion status
- std::pair< shared_ptr<cs::Entry>, bool> entry = insertToSkipList(data, isUnsolicited);
+ std::pair<cs::Entry*, bool> entry = insertToSkipList(data, isUnsolicited);
//new entry
- if (entry.first && (entry.second == true))
+ if (static_cast<bool>(entry.first) && (entry.second == true))
{
- m_contentByArrival.push(entry.first);
- m_contentByStaleness.push(entry.first);
-
- if (entry.first->isUnsolicited())
- m_unsolicitedContent.push(entry.first);
-
+ m_cleanupIndex.push_back(entry.first);
return true;
}
@@ -242,7 +260,7 @@
layer++;
randomValue = rand() % 100 + 1;
}
- while ( (randomValue < SKIPLIST_PROBABILITY) && (layer < SKIPLIST_MAX_LAYERS) );
+ while ((randomValue < SKIPLIST_PROBABILITY) && (layer < SKIPLIST_MAX_LAYERS));
return static_cast<size_t>(layer);
}
@@ -257,40 +275,52 @@
}
bool
-Cs::eraseFromSkipList(shared_ptr<cs::Entry> entry)
+Cs::eraseFromSkipList(cs::Entry* entry)
{
NFD_LOG_TRACE("eraseFromSkipList() " << entry->getName());
NFD_LOG_TRACE("SkipList size " << size());
bool isErased = false;
- int layer = m_skipList.size() - 1;
- for (SkipList::reverse_iterator rit = m_skipList.rbegin(); rit != m_skipList.rend(); ++rit)
- {
- const std::map<int, std::list< shared_ptr<cs::Entry> >::iterator>& iterators = entry->getIterators();
- std::map<int, std::list< shared_ptr<cs::Entry> >::iterator>::const_iterator it = iterators.find(layer);
- if (it != iterators.end())
- {
- (*rit)->erase(it->second);
- entry->removeIterator(layer);
- isErased = true;
- }
+ const std::map<int, std::list<cs::Entry*>::iterator>& iterators = entry->getIterators();
- layer--;
+ if (!iterators.empty())
+ {
+ int layer = 0;
+
+ for (SkipList::iterator it = m_skipList.begin(); it != m_skipList.end(); )
+ {
+ std::map<int, std::list<cs::Entry*>::iterator>::const_iterator i = iterators.find(layer);
+
+ if (i != iterators.end())
+ {
+ (*it)->erase(i->second);
+ entry->removeIterator(layer);
+ isErased = true;
+
+ //remove layers that do not contain any elements (starting from the second layer)
+ if ((layer != 0) && (*it)->empty())
+ {
+ delete *it;
+ it = m_skipList.erase(it);
+ }
+ else
+ ++it;
+
+ layer++;
+ }
+ else
+ break;
+ }
}
- printSkipList();
-
- //remove layers that do not contain any elements (starting from the second layer)
- for (SkipList::iterator it = (++m_skipList.begin()); it != m_skipList.end();)
- {
- if ((*it)->empty())
- {
- it = m_skipList.erase(it);
- }
- else
- ++it;
- }
+ //delete entry;
+ if (isErased)
+ {
+ entry->release();
+ m_freeCsEntries.push(entry);
+ m_nPackets--;
+ }
return isErased;
}
@@ -300,65 +330,34 @@
{
NFD_LOG_TRACE("evictItem()");
- //because there is a possibility that this item is in a queue, but no longer in skiplist
- while ( !m_unsolicitedContent.empty() )
- {
- NFD_LOG_TRACE("Evict from unsolicited queue");
+ if (!m_cleanupIndex.get<unsolicited>().empty() &&
+ (*m_cleanupIndex.get<unsolicited>().begin())->isUnsolicited())
+ {
+ NFD_LOG_TRACE("Evict from unsolicited queue");
- shared_ptr<cs::Entry> entry = m_unsolicitedContent.front();
- m_unsolicitedContent.pop();
- bool isErased = eraseFromSkipList(entry);
+ eraseFromSkipList(*m_cleanupIndex.get<unsolicited>().begin());
+ m_cleanupIndex.get<unsolicited>().erase(m_cleanupIndex.get<unsolicited>().begin());
+ return true;
+ }
- if (isErased)
- return true;
- }
+ if (!m_cleanupIndex.get<byStaleness>().empty() &&
+ (*m_cleanupIndex.get<byStaleness>().begin())->getStaleTime() < time::steady_clock::now())
+ {
+ NFD_LOG_TRACE("Evict from staleness queue");
- //because there is a possibility that this item is in a queue, but no longer in skiplist
- int nIterations = size() * 0.01; // 1% of the Content Store
- while ( !m_contentByStaleness.empty() )
- {
- NFD_LOG_TRACE("Evict from staleness queue");
+ eraseFromSkipList(*m_cleanupIndex.get<byStaleness>().begin());
+ m_cleanupIndex.get<byStaleness>().erase(m_cleanupIndex.get<byStaleness>().begin());
+ return true;
+ }
- shared_ptr<cs::Entry> entry = m_contentByStaleness.top();
+ if (!m_cleanupIndex.get<byArrival>().empty())
+ {
+ NFD_LOG_TRACE("Evict from arrival queue");
- //because stale time could be updated by the duplicate packet
- if (entry->getStaleTime() < time::steady_clock::now())
- {
- m_contentByStaleness.pop();
- bool isErased = eraseFromSkipList(entry);
-
- if (isErased)
- return true;
- }
- else if ( (entry->getStaleTime() > time::steady_clock::now()) && entry->wasRefreshedByDuplicate() )
- {
- m_contentByStaleness.pop();
- m_contentByStaleness.push(entry); // place in a right order
-
- nIterations--;
- // if 1% of the CS are non-expired refreshed CS entries (allocated sequentially),
- // then stop to prevent too many iterations
- if ( nIterations <= 0 )
- break;
- }
- else //no further item will be expired, stop
- {
- break;
- }
- }
-
- //because there is a possibility that this item is in a queue, but no longer in skiplist
- while ( !m_contentByArrival.empty() )
- {
- NFD_LOG_TRACE("Evict from arrival queue");
-
- shared_ptr<cs::Entry> entry = m_contentByArrival.front();
- m_contentByArrival.pop();
- bool isErased = eraseFromSkipList(entry);
-
- if (isErased)
- return true;
- }
+ eraseFromSkipList(*m_cleanupIndex.get<byArrival>().begin());
+ m_cleanupIndex.get<byArrival>().erase(m_cleanupIndex.get<byArrival>().begin());
+ return true;
+ }
return false;
}
@@ -372,7 +371,7 @@
SkipList::const_reverse_iterator topLayer = m_skipList.rbegin();
SkipListLayer::iterator head = (*topLayer)->begin();
- if ( !(*topLayer)->empty() )
+ if (!(*topLayer)->empty())
{
//start from the upper layer towards bottom
int layer = m_skipList.size() - 1;
@@ -385,7 +384,7 @@
if (head != (*rit)->end())
{
// it happens when begin() contains the element we want to find
- if ( !isIterated && (interest.getName().isPrefixOf((*head)->getName())) )
+ if (!isIterated && (interest.getName().isPrefixOf((*head)->getName())))
{
if (layer > 0)
{
@@ -401,7 +400,7 @@
{
SkipListLayer::iterator it = head;
- while ( (*it)->getName() < interest.getName() )
+ while ((*it)->getName() < interest.getName())
{
NFD_LOG_TRACE((*it)->getName() << " < " << interest.getName());
head = it;
@@ -420,7 +419,7 @@
}
else //if we reached the first layer
{
- if ( isIterated )
+ if (isIterated)
return selectChild(interest, head);
}
@@ -431,19 +430,18 @@
return 0;
}
-// because skip list is a probabilistic data structure and the way it is traversed,
-// there is no guarantee that startingPoint is an element preceding the leftmost child
const Data*
Cs::selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const
{
- BOOST_ASSERT( startingPoint != (*m_skipList.begin())->end() );
+ BOOST_ASSERT(startingPoint != (*m_skipList.begin())->end());
if (startingPoint != (*m_skipList.begin())->begin())
{
- BOOST_ASSERT( (*startingPoint)->getName() < interest.getName() );
+ BOOST_ASSERT((*startingPoint)->getName() < interest.getName());
}
- NFD_LOG_TRACE("selectChild() " << interest.getChildSelector() << " " << (*startingPoint)->getName());
+ NFD_LOG_TRACE("selectChild() " << interest.getChildSelector() << " "
+ << (*startingPoint)->getName());
bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
bool hasRightmostSelector = !hasLeftmostSelector;
@@ -464,7 +462,7 @@
if (isInPrefix)
{
- if (doesComplyWithSelectors(interest, *startingPoint))
+ if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
{
return &(*startingPoint)->getData();
}
@@ -487,11 +485,13 @@
bool doesInterestContainDigest = false;
if (isInBoundaries)
{
- doesInterestContainDigest = recognizeInterestWithDigest(interest, *rightmostCandidate);
+ doesInterestContainDigest = recognizeInterestWithDigest(interest,
+ *rightmostCandidate);
if (doesInterestContainDigest)
{
- isInPrefix = interest.getName().getPrefix(-1).isPrefixOf((*rightmostCandidate)->getName());
+ isInPrefix = interest.getName().getPrefix(-1)
+ .isPrefixOf((*rightmostCandidate)->getName());
}
else
{
@@ -501,7 +501,7 @@
if (isInPrefix)
{
- if (doesComplyWithSelectors(interest, *rightmostCandidate))
+ if (doesComplyWithSelectors(interest, *rightmostCandidate, doesInterestContainDigest))
{
if (hasLeftmostSelector)
{
@@ -512,11 +512,13 @@
{
if (doesInterestContainDigest)
{
- // get prefix which is one component longer than Interest name (without digest)
- const Name& childPrefix = (*rightmostCandidate)->getName().getPrefix(interest.getName().size());
+ // get prefix which is one component longer than Interest name
+ // (without digest)
+ const Name& childPrefix = (*rightmostCandidate)->getName()
+ .getPrefix(interest.getName().size());
NFD_LOG_TRACE("Child prefix" << childPrefix);
- if ( currentChildPrefix.empty() || (childPrefix != currentChildPrefix) )
+ if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
{
currentChildPrefix = childPrefix;
rightmost = rightmostCandidate;
@@ -525,10 +527,11 @@
else
{
// get prefix which is one component longer than Interest name
- const Name& childPrefix = (*rightmostCandidate)->getName().getPrefix(interest.getName().size() + 1);
+ const Name& childPrefix = (*rightmostCandidate)->getName()
+ .getPrefix(interest.getName().size() + 1);
NFD_LOG_TRACE("Child prefix" << childPrefix);
- if ( currentChildPrefix.empty() || (childPrefix != currentChildPrefix) )
+ if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
{
currentChildPrefix = childPrefix;
rightmost = rightmostCandidate;
@@ -563,7 +566,7 @@
if (isInPrefix)
{
- if (doesComplyWithSelectors(interest, *startingPoint))
+ if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
{
return &(*startingPoint)->getData();
}
@@ -574,16 +577,18 @@
}
bool
-Cs::doesComplyWithSelectors(const Interest& interest, shared_ptr<cs::Entry> entry) const
+Cs::doesComplyWithSelectors(const Interest& interest,
+ cs::Entry* entry,
+ bool doesInterestContainDigest) const
{
NFD_LOG_TRACE("doesComplyWithSelectors()");
/// \todo The following detection is not correct
/// 1. If data name ends with 32-octet component doesn't mean that this component is digest
- /// 2. Only min/max selectors (both 0) can be specified, all other selectors do not make sense
- /// for interests with digest (though not sure if we need to enforce this)
- bool doesInterestContainDigest = recognizeInterestWithDigest(interest, entry);
- if ( doesInterestContainDigest )
+ /// 2. Only min/max selectors (both 0) can be specified, all other selectors do not
+ /// make sense for interests with digest (though not sure if we need to enforce this)
+
+ if (doesInterestContainDigest)
{
const ndn::name::Component& last = interest.getName().get(-1);
const ndn::ConstBufferPtr& digest = entry->getDigest();
@@ -598,14 +603,14 @@
}
}
- if ( !doesInterestContainDigest )
+ if (!doesInterestContainDigest)
{
if (interest.getMinSuffixComponents() >= 0)
{
size_t minDataNameLength = interest.getName().size() + interest.getMinSuffixComponents();
bool isSatisfied = (minDataNameLength <= entry->getName().size());
- if ( !isSatisfied )
+ if (!isSatisfied)
{
NFD_LOG_TRACE("violates minComponents");
return false;
@@ -617,7 +622,7 @@
size_t maxDataNameLength = interest.getName().size() + interest.getMaxSuffixComponents();
bool isSatisfied = (maxDataNameLength >= entry->getName().size());
- if ( !isSatisfied )
+ if (!isSatisfied)
{
NFD_LOG_TRACE("violates maxComponents");
return false;
@@ -631,11 +636,11 @@
return false;
}
- if ( doesInterestContainDigest )
+ if (doesInterestContainDigest)
{
const ndn::name::Component& lastComponent = entry->getName().get(-1);
- if ( !lastComponent.empty() )
+ if (!lastComponent.empty())
{
if (interest.getExclude().isExcluded(lastComponent))
{
@@ -648,9 +653,9 @@
{
if (entry->getName().size() >= interest.getName().size() + 1)
{
- const ndn::name::Component& nextComponent = entry->getName().get(interest.getName().size());
-
- if ( !nextComponent.empty() )
+ const ndn::name::Component& nextComponent = entry->getName()
+ .get(interest.getName().size());
+ if (!nextComponent.empty())
{
if (interest.getExclude().isExcluded(nextComponent))
{
@@ -666,7 +671,7 @@
}
bool
-Cs::recognizeInterestWithDigest(const Interest& interest, shared_ptr<cs::Entry> entry) const
+Cs::recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const
{
// only when min selector is not specified or specified with value of 0
// and Interest's name length is exactly the length of the name of CS entry
@@ -695,14 +700,14 @@
SkipList::reverse_iterator topLayer = m_skipList.rbegin();
SkipListLayer::iterator head = (*topLayer)->begin();
- if ( !(*topLayer)->empty() )
+ if (!(*topLayer)->empty())
{
//start from the upper layer towards bottom
int layer = m_skipList.size() - 1;
for (SkipList::reverse_iterator rit = topLayer; rit != m_skipList.rend(); ++rit)
{
//if we didn't do any iterations on the higher layers, start from the begin() again
- if ( !isIterated )
+ if (!isIterated)
head = (*rit)->begin();
updateTable[layer] = head;
@@ -710,7 +715,7 @@
if (head != (*rit)->end())
{
// it can happen when begin() contains the element we want to remove
- if ( !isIterated && ((*head)->getName() == exactName) )
+ if (!isIterated && ((*head)->getName() == exactName))
{
eraseFromSkipList(*head);
return;
@@ -726,7 +731,7 @@
isIterated = true;
++it;
- if ( it == (*rit)->end() )
+ if (it == (*rit)->end())
break;
}
}
@@ -760,8 +765,6 @@
NFD_LOG_TRACE("Found target " << (*head)->getName());
eraseFromSkipList(*head);
}
-
- printSkipList();
}
void
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 56783ef..a1769ea 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -30,11 +30,71 @@
#include "common.hpp"
#include "cs-entry.hpp"
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/multi_index/identity.hpp>
+
+using namespace ::boost;
+using namespace ::boost::multi_index;
+
namespace nfd {
-typedef std::list< shared_ptr<cs::Entry> > SkipListLayer;
+typedef std::list<cs::Entry*> SkipListLayer;
typedef std::list<SkipListLayer*> SkipList;
+class StalenessComparator
+{
+public:
+ bool
+ operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
+ {
+ return entry1->getStaleTime() < entry2->getStaleTime();
+ }
+};
+
+class UnsolicitedComparator
+{
+public:
+ bool
+ operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
+ {
+ return entry1->isUnsolicited();
+ }
+};
+
+// tags
+class unsolicited;
+class byStaleness;
+class byArrival;
+
+typedef multi_index_container<
+ cs::Entry*,
+ indexed_by<
+
+ // by arrival (FIFO)
+ sequenced<
+ tag<byArrival>
+ >,
+
+ // index by staleness time
+ ordered_non_unique<
+ tag<byStaleness>,
+ identity<cs::Entry*>,
+ StalenessComparator
+ >,
+
+ // unsolicited Data is in the front
+ ordered_non_unique<
+ tag<unsolicited>,
+ identity<cs::Entry*>,
+ UnsolicitedComparator
+ >
+
+ >
+> CleanupIndex;
+
/** \brief represents Content Store
*/
class Cs : noncopyable
@@ -110,14 +170,14 @@
* \return{ returns a pair containing a pointer to the CS Entry,
* and a flag indicating if the entry was newly created (True) or refreshed (False) }
*/
- std::pair< shared_ptr<cs::Entry>, bool>
+ std::pair<cs::Entry*, bool>
insertToSkipList(const Data& data, bool isUnsolicited = false);
/** \brief Removes a specific CS Entry from all layers of a skip list
* \return{ returns True if CS Entry was succesfully removed and False if CS Entry was not found}
*/
bool
- eraseFromSkipList(shared_ptr<cs::Entry> entry);
+ eraseFromSkipList(cs::Entry* entry);
/** \brief Prints contents of the skip list, starting from the top layer
*/
@@ -144,32 +204,23 @@
* \return{ true if satisfies all selectors; false otherwise }
*/
bool
- doesComplyWithSelectors(const Interest& interest, shared_ptr<cs::Entry> entry) const;
+ doesComplyWithSelectors(const Interest& interest,
+ cs::Entry* entry,
+ bool doesInterestContainDigest) const;
/** \brief interprets minSuffixComponent and name lengths to understand if Interest contains
* implicit digest of the data
* \return{ True if Interest name contains digest; False otherwise }
*/
bool
- recognizeInterestWithDigest(const Interest& interest, shared_ptr<cs::Entry> entry) const;
+ recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const;
private:
- class StalenessComparator
- {
- public:
- bool
- operator() (shared_ptr<cs::Entry> entry1, shared_ptr<cs::Entry> entry2)
- {
- return entry1->getStaleTime() > entry2->getStaleTime();
- }
- };
-
SkipList m_skipList;
- size_t m_nMaxPackets; //user defined maximum size of the Content Store in packets
-
- std::queue< shared_ptr<cs::Entry> > m_unsolicitedContent; //FIFO for unsolicited Data
- std::queue< shared_ptr<cs::Entry> > m_contentByArrival; //FIFO index
- std::priority_queue< shared_ptr<cs::Entry>, std::vector< shared_ptr<cs::Entry> >, StalenessComparator> m_contentByStaleness; //index by staleness time
+ CleanupIndex m_cleanupIndex;
+ size_t m_nMaxPackets; // user defined maximum size of the Content Store in packets
+ size_t m_nPackets; // current number of packets in Content Store
+ std::queue<cs::Entry*> m_freeCsEntries; // memory pool
};
} // namespace nfd
diff --git a/tests-other/cs-smoketest.cpp b/tests-other/cs-smoketest.cpp
new file mode 100644
index 0000000..be8973f
--- /dev/null
+++ b/tests-other/cs-smoketest.cpp
@@ -0,0 +1,110 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD 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.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * \author Ilya Moiseenko <iliamo@ucla.edu>
+ **/
+
+#include "table/cs.hpp"
+#include "table/cs-entry.hpp"
+#include <ndn-cpp-dev/security/key-chain.hpp>
+
+namespace nfd {
+
+static void
+runStressTest()
+{
+ shared_ptr<Data> dataWorkload[70000];
+ shared_ptr<Interest> interestWorkload[70000];
+
+ ndn::SignatureSha256WithRsa fakeSignature;
+ fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue,
+ reinterpret_cast<const uint8_t*>(0), 0));
+
+ // 182 MB in memory
+ for (int i = 0; i < 70000; i++)
+ {
+ Name name("/stress/test");
+ name.appendNumber(i % 4);
+ name.appendNumber(i);
+
+ shared_ptr<Interest> interest = make_shared<Interest>(name);
+ interestWorkload[i] = interest;
+
+ shared_ptr<Data> data = make_shared<Data>(name);
+ data->setSignature(fakeSignature);
+ dataWorkload[i] = data;
+ }
+
+ time::duration<double, boost::nano> previousResult(0);
+
+ for (size_t nInsertions = 1000; nInsertions < 10000000; nInsertions *= 2)
+ {
+ Cs cs;
+ srand(time::toUnixTimestamp(time::system_clock::now()).count());
+
+ time::steady_clock::TimePoint startTime = time::steady_clock::now();
+
+ int workloadCounter = 0;
+ for (int i = 0; i < nInsertions; i++)
+ {
+ if (workloadCounter > 69999)
+ workloadCounter = 0;
+
+ cs.find(*interestWorkload[workloadCounter]);
+ cs.insert(*dataWorkload[workloadCounter]);
+
+ workloadCounter++;
+ }
+
+ time::steady_clock::TimePoint endTime = time::steady_clock::now();
+
+ time::duration<double, boost::nano> runDuration = endTime - startTime;
+ time::duration<double, boost::nano> perOperationTime = runDuration / nInsertions;
+
+ std::cout << "nItem = " << nInsertions << std::endl;
+ std::cout << "Total running time = "
+ << time::duration_cast<time::duration<double> >(runDuration)
+ << std::endl;
+ std::cout << "Average per-operation time = "
+ << time::duration_cast<time::duration<double, boost::micro> >(perOperationTime)
+ << std::endl;
+
+ if (previousResult > time::nanoseconds(1))
+ std::cout << "Change compared to the previous: "
+ << (100.0 * perOperationTime / previousResult) << "%" << std::endl;
+
+ std::cout << "\n=================================\n" << std::endl;
+
+ previousResult = perOperationTime;
+ }
+}
+
+} // namespace nfd
+
+int
+main(int argc, char** argv)
+{
+ nfd::runStressTest();
+
+ return 0;
+}
diff --git a/tests-other/wscript b/tests-other/wscript
new file mode 100644
index 0000000..88dab1c
--- /dev/null
+++ b/tests-other/wscript
@@ -0,0 +1,33 @@
+# -*- Mode: python; py-indent-offset: 4; indent-tabs-mode: nil; coding: utf-8; -*-
+
+"""
+Copyright (c) 2014 Regents of the University of California,
+ Arizona Board of Regents,
+ Colorado State University,
+ University Pierre & Marie Curie, Sorbonne University,
+ Washington University in St. Louis,
+ Beijing Institute of Technology
+
+This file is part of NFD (Named Data Networking Forwarding Daemon).
+See AUTHORS.md for complete list of NFD authors and contributors.
+
+NFD 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.
+
+NFD 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
+NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+"""
+
+top = '..'
+
+def build(bld):
+ bld.program(target="cs-smoketest",
+ source="cs-smoketest.cpp",
+ use='nfd-objects',
+ includes='.. ../daemon',
+ install_path=None)
diff --git a/tests/table/cs.cpp b/tests/table/cs.cpp
index f236d77..e8e5377 100644
--- a/tests/table/cs.cpp
+++ b/tests/table/cs.cpp
@@ -29,15 +29,12 @@
#include "tests/test-common.hpp"
-#include <ndn-cpp-dev/security/key-chain.hpp>
-
namespace nfd {
namespace tests {
class CsAccessor : public Cs
{
public:
-
bool
evictItem_accessor()
{
@@ -51,37 +48,17 @@
{
Cs cs;
- shared_ptr<Data> data = make_shared<Data>("/insertion");
-
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
- data->setSignature(fakeSignature);
-
- BOOST_CHECK_EQUAL(cs.insert(*data), true);
+ BOOST_CHECK_EQUAL(cs.insert(*makeData("/insertion")), true);
}
BOOST_AUTO_TEST_CASE(Insertion2)
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
- cs.insert(*data);
-
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = make_shared<Data>("/c");
- data3->setSignature(fakeSignature);
- cs.insert(*data3);
-
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
- cs.insert(*data4);
+ cs.insert(*makeData("/a"));
+ cs.insert(*makeData("/b"));
+ cs.insert(*makeData("/c"));
+ cs.insert(*makeData("/d"));
BOOST_CHECK_EQUAL(cs.size(), 4);
}
@@ -91,15 +68,10 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data0 = make_shared<Data>("/insert/smth");
- data0->setSignature(fakeSignature);
+ shared_ptr<Data> data0 = makeData("/insert/smth");
BOOST_CHECK_EQUAL(cs.insert(*data0), true);
- shared_ptr<Data> data = make_shared<Data>("/insert/duplicate");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/insert/duplicate");
BOOST_CHECK_EQUAL(cs.insert(*data), true);
cs.insert(*data);
@@ -111,18 +83,13 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/insert/duplicate");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/insert/duplicate");
BOOST_CHECK_EQUAL(cs.insert(*data), true);
cs.insert(*data);
BOOST_CHECK_EQUAL(cs.size(), 1);
- shared_ptr<Data> data2 = make_shared<Data>("/insert/original");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/insert/original");
BOOST_CHECK_EQUAL(cs.insert(*data2), true);
BOOST_CHECK_EQUAL(cs.size(), 2);
}
@@ -131,13 +98,9 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
Name name("/insert/and/find");
- shared_ptr<Data> data = make_shared<Data>(name);
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData(name);
BOOST_CHECK_EQUAL(cs.insert(*data), true);
shared_ptr<Interest> interest = make_shared<Interest>(name);
@@ -152,12 +115,8 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
Name name("/insert/and/find");
- shared_ptr<Data> data = make_shared<Data>(name);
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData(name);
BOOST_CHECK_EQUAL(cs.insert(*data), true);
Name name2("/not/find");
@@ -173,11 +132,7 @@
{
CsAccessor cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/insertandelete");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/insertandelete");
cs.insert(*data);
BOOST_CHECK_EQUAL(cs.size(), 1);
@@ -189,24 +144,19 @@
{
CsAccessor cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
Name name2("/insert/fresh");
- shared_ptr<Data> data2 = make_shared<Data>(name2);
+ shared_ptr<Data> data2 = makeData(name2);
data2->setFreshnessPeriod(time::milliseconds(5000));
- data2->setSignature(fakeSignature);
cs.insert(*data2);
Name name("/insert/expire");
- shared_ptr<Data> data = make_shared<Data>(name);
+ shared_ptr<Data> data = makeData(name);
data->setFreshnessPeriod(time::milliseconds(500));
- data->setSignature(fakeSignature);
cs.insert(*data);
BOOST_CHECK_EQUAL(cs.size(), 2);
- sleep(1);
+ sleep(3);
cs.evictItem_accessor();
BOOST_CHECK_EQUAL(cs.size(), 1);
@@ -222,27 +172,19 @@
{
Cs cs(4);
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/b");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/c");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/c");
cs.insert(*data3);
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/d");
cs.insert(*data4);
- shared_ptr<Data> data5 = make_shared<Data>("/e");
- data5->setSignature(fakeSignature);
+ shared_ptr<Data> data5 = makeData("/e");
cs.insert(*data5);
BOOST_CHECK_EQUAL(cs.size(), 4);
@@ -253,23 +195,16 @@
{
Cs cs(3);
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/b");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/c");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/c");
cs.insert(*data3);
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/d");
cs.insert(*data4);
BOOST_CHECK_EQUAL(cs.size(), 3);
@@ -279,82 +214,64 @@
{
CsAccessor cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
Name name("/insertandremovebyname");
- shared_ptr<Data> data = make_shared<Data>(name);
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData(name);
cs.insert(*data);
- uint8_t digest1[32];
- ndn::ndn_digestSha256(data->wireEncode().wire(), data->wireEncode().size(), digest1);
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
- shared_ptr<Data> data2 = make_shared<Data>("/a");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/a");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/z");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/z");
cs.insert(*data3);
BOOST_CHECK_EQUAL(cs.size(), 3);
- name.append(digest1, 32);
+ name.append(digest1->buf(), digest1->size());
cs.erase(name);
BOOST_CHECK_EQUAL(cs.size(), 2);
}
BOOST_AUTO_TEST_CASE(DigestCalculation)
{
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
+ shared_ptr<Data> data = makeData("/digest/compute");
- shared_ptr<Data> data = make_shared<Data>("/digest/compute");
- data->setSignature(fakeSignature);
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
+ BOOST_CHECK_EQUAL(digest1->size(), 32);
- uint8_t digest1[32];
- ndn::ndn_digestSha256(data->wireEncode().wire(), data->wireEncode().size(), digest1);
+ cs::Entry* entry = new cs::Entry();
+ entry->setData(*data, false);
- cs::Entry* entry = new cs::Entry(*data, false);
-
- BOOST_CHECK_EQUAL_COLLECTIONS(digest1, digest1+32,
- entry->getDigest()->buf(), entry->getDigest()->buf()+32);
+ BOOST_CHECK_EQUAL_COLLECTIONS(digest1->begin(), digest1->end(),
+ entry->getDigest()->begin(), entry->getDigest()->end());
}
BOOST_AUTO_TEST_CASE(InsertCanonical)
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/b");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/c");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/c");
cs.insert(*data3);
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/d");
cs.insert(*data4);
- shared_ptr<Data> data5 = make_shared<Data>("/c/c/1/2/3/4/5/6");
- data5->setSignature(fakeSignature);
+ shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
cs.insert(*data5);
- shared_ptr<Data> data6 = make_shared<Data>("/c/c/1/2/3");
- data6->setSignature(fakeSignature);
+ shared_ptr<Data> data6 = makeData("/c/c/1/2/3");
cs.insert(*data6);
- shared_ptr<Data> data7 = make_shared<Data>("/c/c/1");
- data7->setSignature(fakeSignature);
+ shared_ptr<Data> data7 = makeData("/c/c/1");
cs.insert(*data7);
}
@@ -362,42 +279,32 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/b");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/c");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/c");
cs.insert(*data3);
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/d");
cs.insert(*data4);
- uint8_t digest1[32];
- ndn::ndn_digestSha256(data->wireEncode().wire(), data->wireEncode().size(), digest1);
-
- shared_ptr<Data> data5 = make_shared<Data>("/c/c/1/2/3/4/5/6");
- data5->setSignature(fakeSignature);
+ shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
cs.insert(*data5);
- shared_ptr<Data> data6 = make_shared<Data>("/c/c/1/2/3");
- data6->setSignature(fakeSignature);
+ shared_ptr<Data> data6 = makeData("/c/c/1/2/3");
cs.insert(*data6);
- shared_ptr<Data> data7 = make_shared<Data>("/c/c/1");
- data7->setSignature(fakeSignature);
+ shared_ptr<Data> data7 = makeData("/c/c/1");
cs.insert(*data7);
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
+
Name name("/a");
- name.append(digest1,32);
+ name.append(digest1->buf(), digest1->size());
cs.erase(name);
BOOST_CHECK_EQUAL(cs.size(), 6);
}
@@ -406,28 +313,23 @@
{
CsAccessor cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
Name name("/digest/works");
- shared_ptr<Data> data = make_shared<Data>(name);
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData(name);
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/a");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/a");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/z/z/z");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/z/z/z");
cs.insert(*data3);
- uint8_t digest1[32];
- ndn::ndn_digestSha256(data->wireEncode().wire(), data->wireEncode().size(), digest1);
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
+ uint8_t digest2[32] = {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
- uint8_t digest2[32] = {0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1};
-
- shared_ptr<Interest> interest = make_shared<Interest>(boost::cref(Name(name).append(digest1, 32)));
+ shared_ptr<Interest> interest = make_shared<Interest>();
+ interest->setName(Name(name).append(digest1->buf(), digest1->size()));
interest->setMinSuffixComponents(0);
interest->setMaxSuffixComponents(0);
@@ -435,7 +337,8 @@
BOOST_CHECK_NE(found, static_cast<const Data*>(0));
BOOST_CHECK_EQUAL(found->getName(), name);
- shared_ptr<Interest> interest2 = make_shared<Interest>(boost::cref(Name(name).append(digest2, 32)));
+ shared_ptr<Interest> interest2 = make_shared<Interest>();
+ interest2->setName(Name(name).append(digest2, 32));
interest2->setMinSuffixComponents(0);
interest2->setMaxSuffixComponents(0);
@@ -447,31 +350,22 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/b");
cs.insert(*data2);
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/d");
cs.insert(*data4);
- shared_ptr<Data> data5 = make_shared<Data>("/c/c");
- data5->setSignature(fakeSignature);
+ shared_ptr<Data> data5 = makeData("/c/c");
cs.insert(*data5);
- shared_ptr<Data> data6 = make_shared<Data>("/c/f");
- data6->setSignature(fakeSignature);
+ shared_ptr<Data> data6 = makeData("/c/f");
cs.insert(*data6);
- shared_ptr<Data> data7 = make_shared<Data>("/c/n");
- data7->setSignature(fakeSignature);
+ shared_ptr<Data> data7 = makeData("/c/n");
cs.insert(*data7);
shared_ptr<Interest> interest = make_shared<Interest>("/c");
@@ -491,23 +385,16 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a/b/1");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a/b/1");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/a/b/2");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/a/b/2");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/a/z/1");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/a/z/1");
cs.insert(*data3);
- shared_ptr<Data> data4 = make_shared<Data>("/a/z/2");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/a/z/2");
cs.insert(*data4);
shared_ptr<Interest> interest = make_shared<Interest>("/a");
@@ -521,13 +408,9 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
Name name("/insert/nonfresh");
- shared_ptr<Data> data = make_shared<Data>(name);
+ shared_ptr<Data> data = makeData(name);
data->setFreshnessPeriod(time::milliseconds(500));
- data->setSignature(fakeSignature);
cs.insert(*data);
sleep(1);
@@ -543,35 +426,25 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/b");
cs.insert(*data2);
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/d");
cs.insert(*data4);
- shared_ptr<Data> data5 = make_shared<Data>("/c/c/1/2/3/4/5/6");
- data5->setSignature(fakeSignature);
+ shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
cs.insert(*data5);
- shared_ptr<Data> data6 = make_shared<Data>("/c/c/6/7/8/9");
- data6->setSignature(fakeSignature);
+ shared_ptr<Data> data6 = makeData("/c/c/6/7/8/9");
cs.insert(*data6);
- shared_ptr<Data> data7 = make_shared<Data>("/c/c/1/2/3");
- data7->setSignature(fakeSignature);
+ shared_ptr<Data> data7 = makeData("/c/c/1/2/3");
cs.insert(*data7);
- shared_ptr<Data> data8 = make_shared<Data>("/c/c/1");
- data8->setSignature(fakeSignature);
+ shared_ptr<Data> data8 = makeData("/c/c/1");
cs.insert(*data8);
shared_ptr<Interest> interest = make_shared<Interest>("/c/c");
@@ -600,35 +473,25 @@
{
Cs cs;
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
-
- shared_ptr<Data> data = make_shared<Data>("/a");
- data->setSignature(fakeSignature);
+ shared_ptr<Data> data = makeData("/a");
cs.insert(*data);
- shared_ptr<Data> data2 = make_shared<Data>("/b");
- data2->setSignature(fakeSignature);
+ shared_ptr<Data> data2 = makeData("/b");
cs.insert(*data2);
- shared_ptr<Data> data3 = make_shared<Data>("/c/a");
- data3->setSignature(fakeSignature);
+ shared_ptr<Data> data3 = makeData("/c/a");
cs.insert(*data3);
- shared_ptr<Data> data4 = make_shared<Data>("/d");
- data4->setSignature(fakeSignature);
+ shared_ptr<Data> data4 = makeData("/d");
cs.insert(*data4);
- shared_ptr<Data> data5 = make_shared<Data>("/c/c");
- data5->setSignature(fakeSignature);
+ shared_ptr<Data> data5 = makeData("/c/c");
cs.insert(*data5);
- shared_ptr<Data> data6 = make_shared<Data>("/c/f");
- data6->setSignature(fakeSignature);
+ shared_ptr<Data> data6 = makeData("/c/f");
cs.insert(*data6);
- shared_ptr<Data> data7 = make_shared<Data>("/c/n");
- data7->setSignature(fakeSignature);
+ shared_ptr<Data> data7 = makeData("/c/n");
cs.insert(*data7);
shared_ptr<Interest> interest = make_shared<Interest>("/c");
@@ -669,14 +532,10 @@
void
insert(uint32_t id, const Name& name)
{
- shared_ptr<Data> data = make_shared<Data>(name);
+ shared_ptr<Data> data = makeData(name);
data->setFreshnessPeriod(time::milliseconds(99999));
data->setContent(reinterpret_cast<const uint8_t*>(&id), sizeof(id));
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
- data->setSignature(fakeSignature);
-
m_cs.insert(*data);
}
@@ -891,23 +750,121 @@
insert(3, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 33 'C's
startInterest("ndn:/A")
- .setExclude(Exclude().excludeBefore(ndn::name::Component(reinterpret_cast<const uint8_t*>(
+ .setExclude(Exclude().excludeBefore(name::Component(reinterpret_cast<const uint8_t*>(
"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"
"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"), 31))); // 31 0xFF's
BOOST_CHECK_EQUAL(find(), 2);
startInterest("ndn:/A")
.setChildSelector(1)
- .setExclude(Exclude().excludeAfter(ndn::name::Component(reinterpret_cast<const uint8_t*>(
+ .setExclude(Exclude().excludeAfter(name::Component(reinterpret_cast<const uint8_t*>(
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
"\x00"), 33))); // 33 0x00's
BOOST_CHECK_EQUAL(find(), 2);
}
-BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_CASE(ExactName32)
+{
+ insert(1, "ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"); // 32 'B's
+ insert(2, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 32 'C's
-BOOST_AUTO_TEST_SUITE_END()
+ startInterest("ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB");
+ BOOST_CHECK_EQUAL(find(), 1);
+}
+
+BOOST_AUTO_TEST_CASE(MinSuffixComponents32)
+{
+ insert(1, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/1/2/3/4"); // 32 'x's
+ insert(2, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/B/1/2/3");
+ insert(3, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/C/1/2");
+ insert(4, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/D/1");
+ insert(5, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/E");
+ insert(6, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(0);
+ BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(1);
+ BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(2);
+ BOOST_CHECK_EQUAL(find(), 5);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(3);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(4);
+ BOOST_CHECK_EQUAL(find(), 3);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(5);
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(6);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(7);
+ BOOST_CHECK_EQUAL(find(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(MaxSuffixComponents32)
+{
+ insert(1, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/"); // 32 'x's
+ insert(2, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A");
+ insert(3, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B");
+ insert(4, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C");
+ insert(5, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C/D");
+ insert(6, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C/D/E");
+ // Order is 6,5,4,3,2,1, because <32-octet hash> is greater than a 1-octet component.
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(0);
+ BOOST_CHECK_EQUAL(find(), 0);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(1);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(2);
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(3);
+ BOOST_CHECK_EQUAL(find(), 3);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(4);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(5);
+ BOOST_CHECK_EQUAL(find(), 5);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(6);
+ BOOST_CHECK_EQUAL(find(), 6);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // Find
+
+BOOST_AUTO_TEST_SUITE_END() // TableCs
} // namespace tests
} // namespace nfd
diff --git a/tests/test-common.hpp b/tests/test-common.hpp
index e9402b2..2e555b4 100644
--- a/tests/test-common.hpp
+++ b/tests/test-common.hpp
@@ -69,7 +69,8 @@
shared_ptr<Data> data = make_shared<Data>(name);
ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue, reinterpret_cast<const uint8_t*>(0), 0));
+ fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue,
+ reinterpret_cast<const uint8_t*>(0), 0));
data->setSignature(fakeSignature);
return data;
diff --git a/wscript b/wscript
index 7003118..d57a36d 100644
--- a/wscript
+++ b/wscript
@@ -39,6 +39,8 @@
nfdopt = opt.add_option_group('NFD Options')
nfdopt.add_option('--with-tests', action='store_true', default=False,
dest='with_tests', help='''Build unit tests''')
+ nfdopt.add_option('--with-other-tests', action='store_true', default=False,
+ dest='with_other_tests', help='''Build other tests''')
def configure(conf):
conf.load("compiler_cxx boost gnu_dirs")
@@ -57,6 +59,9 @@
conf.define('WITH_TESTS', 1);
boost_libs += ' unit_test_framework'
+ if conf.options.with_other_tests:
+ conf.env['WITH_OTHER_TESTS'] = 1
+
conf.check_boost(lib=boost_libs)
if conf.env.BOOST_VERSION_NUMBER < 104800:
@@ -85,6 +90,7 @@
def build(bld):
nfd_objects = bld(
target='nfd-objects',
+ name='nfd-objects',
features='cxx',
source=bld.path.ant_glob(['daemon/**/*.cpp'],
excl=['daemon/face/ethernet-*.cpp',
@@ -135,6 +141,9 @@
if bld.env['HAVE_UNIX_SOCKETS']:
unit_tests.source += bld.path.ant_glob('tests/face/unix-*.cpp')
+ if bld.env['WITH_OTHER_TESTS']:
+ bld.recurse("tests-other")
+
bld(features="subst",
source='nfd.conf.sample.in',
target='nfd.conf.sample',