table: add CS policy interface
Change-Id: I1946fe03ca00150b1ff9f08acae48c01bc569904
Refs: #1207
diff --git a/daemon/table/cs-entry-impl.cpp b/daemon/table/cs-entry-impl.cpp
index 9e1c1cd..c8bd357 100644
--- a/daemon/table/cs-entry-impl.cpp
+++ b/daemon/table/cs-entry-impl.cpp
@@ -35,7 +35,6 @@
}
EntryImpl::EntryImpl(shared_ptr<const Data> data, bool isUnsolicited)
- : queueType(QUEUE_NONE)
{
this->setData(data, isUnsolicited);
BOOST_ASSERT(!this->isQuery());
diff --git a/daemon/table/cs-entry-impl.hpp b/daemon/table/cs-entry-impl.hpp
index 0732047..d061f88 100644
--- a/daemon/table/cs-entry-impl.hpp
+++ b/daemon/table/cs-entry-impl.hpp
@@ -26,9 +26,7 @@
#ifndef NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
#define NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
-#include "cs-internal.hpp"
#include "cs-entry.hpp"
-#include "core/scheduler.hpp"
namespace nfd {
namespace cs {
@@ -69,11 +67,6 @@
bool
isQuery() const;
-public:
- QueueType queueType;
- QueueIt queueIt;
- scheduler::EventId moveStaleEvent;
-
private:
Name m_queryName;
};
diff --git a/daemon/table/cs-internal.hpp b/daemon/table/cs-internal.hpp
index 7df3d06..3f22bcd 100644
--- a/daemon/table/cs-internal.hpp
+++ b/daemon/table/cs-internal.hpp
@@ -38,18 +38,7 @@
class EntryImpl;
typedef std::set<EntryImpl> Table;
-typedef Table::const_iterator TableIt;
-
-typedef std::list<TableIt> Queue;
-typedef Queue::iterator QueueIt;
-
-enum QueueType {
- QUEUE_UNSOLICITED,
- QUEUE_STALE,
- QUEUE_FIFO,
- QUEUE_MAX,
- QUEUE_NONE = QUEUE_MAX
-};
+typedef Table::const_iterator iterator;
} // namespace cs
} // namespace nfd
diff --git a/daemon/table/cs-policy-priority-fifo.cpp b/daemon/table/cs-policy-priority-fifo.cpp
new file mode 100644
index 0000000..e7231a9
--- /dev/null
+++ b/daemon/table/cs-policy-priority-fifo.cpp
@@ -0,0 +1,157 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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,
+ * The University of Memphis.
+ *
+ * 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/>.
+ */
+
+#include "cs-policy-priority-fifo.hpp"
+#include "cs.hpp"
+#include <ndn-cxx/util/signal.hpp>
+
+namespace nfd {
+namespace cs {
+namespace priority_fifo {
+
+const std::string PriorityFifoPolicy::POLICY_NAME = "fifo";
+
+PriorityFifoPolicy::PriorityFifoPolicy()
+ : Policy(POLICY_NAME)
+{
+}
+
+void
+PriorityFifoPolicy::doAfterInsert(iterator i)
+{
+ this->attachQueue(i);
+ this->evictEntries();
+}
+
+void
+PriorityFifoPolicy::doAfterRefresh(iterator i)
+{
+ this->detachQueue(i);
+ this->attachQueue(i);
+}
+
+void
+PriorityFifoPolicy::doBeforeErase(iterator i)
+{
+ this->detachQueue(i);
+}
+
+void
+PriorityFifoPolicy::doBeforeUse(iterator i)
+{
+ BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
+}
+
+void
+PriorityFifoPolicy::evictEntries()
+{
+ BOOST_ASSERT(this->getCs() != nullptr);
+
+ while (this->getCs()->size() > this->getLimit()) {
+ this->evictOne();
+ }
+}
+
+void
+PriorityFifoPolicy::evictOne()
+{
+ BOOST_ASSERT(!m_queues[QUEUE_UNSOLICITED].empty() ||
+ !m_queues[QUEUE_STALE].empty() ||
+ !m_queues[QUEUE_FIFO].empty());
+
+ iterator i;
+ if (!m_queues[QUEUE_UNSOLICITED].empty()) {
+ i = m_queues[QUEUE_UNSOLICITED].front();
+ }
+ else if (!m_queues[QUEUE_STALE].empty()) {
+ i = m_queues[QUEUE_STALE].front();
+ }
+ else if (!m_queues[QUEUE_FIFO].empty()) {
+ i = m_queues[QUEUE_FIFO].front();
+ }
+
+ this->detachQueue(i);
+ this->emitSignal(beforeEvict, i);
+}
+
+void
+PriorityFifoPolicy::attachQueue(iterator i)
+{
+ BOOST_ASSERT(m_entryInfoMap.find(i) == m_entryInfoMap.end());
+
+ EntryInfo* entryInfo = new EntryInfo();
+ if (i->isUnsolicited()) {
+ entryInfo->queueType = QUEUE_UNSOLICITED;
+ }
+ else if (i->isStale()) {
+ entryInfo->queueType = QUEUE_STALE;
+ }
+ else {
+ entryInfo->queueType = QUEUE_FIFO;
+
+ if (i->canStale()) {
+ entryInfo->moveStaleEventId = scheduler::schedule(i->getData().getFreshnessPeriod(),
+ bind(&PriorityFifoPolicy::moveToStaleQueue, this, i));
+ }
+ }
+
+ Queue& queue = m_queues[entryInfo->queueType];
+ entryInfo->queueIt = queue.insert(queue.end(), i);
+ m_entryInfoMap[i] = entryInfo;
+}
+
+void
+PriorityFifoPolicy::detachQueue(iterator i)
+{
+ BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
+
+ EntryInfo* entryInfo = m_entryInfoMap[i];
+ if (entryInfo->queueType == QUEUE_FIFO) {
+ scheduler::cancel(entryInfo->moveStaleEventId);
+ }
+
+ m_queues[entryInfo->queueType].erase(entryInfo->queueIt);
+ m_entryInfoMap.erase(i);
+}
+
+void
+PriorityFifoPolicy::moveToStaleQueue(iterator i)
+{
+ BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
+
+ EntryInfo* entryInfo = m_entryInfoMap[i];
+ BOOST_ASSERT(entryInfo->queueType == QUEUE_FIFO);
+
+ m_queues[QUEUE_FIFO].erase(entryInfo->queueIt);
+
+ entryInfo->queueType = QUEUE_STALE;
+ Queue& queue = m_queues[QUEUE_STALE];
+ entryInfo->queueIt = queue.insert(queue.end(), i);
+ m_entryInfoMap[i] = entryInfo;
+}
+
+} // namespace priorityfifo
+} // namespace cs
+} // namespace nfd
diff --git a/daemon/table/cs-policy-priority-fifo.hpp b/daemon/table/cs-policy-priority-fifo.hpp
new file mode 100644
index 0000000..93ae884
--- /dev/null
+++ b/daemon/table/cs-policy-priority-fifo.hpp
@@ -0,0 +1,133 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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,
+ * The University of Memphis.
+ *
+ * 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/>.
+ */
+
+#ifndef NFD_DAEMON_TABLE_CS_POLICY_FIFO_HPP
+#define NFD_DAEMON_TABLE_CS_POLICY_FIFO_HPP
+
+#include "cs-policy.hpp"
+#include "common.hpp"
+#include "core/scheduler.hpp"
+
+namespace nfd {
+namespace cs {
+namespace priority_fifo {
+
+typedef std::list<iterator> Queue;
+typedef Queue::iterator QueueIt;
+
+enum QueueType {
+ QUEUE_UNSOLICITED,
+ QUEUE_STALE,
+ QUEUE_FIFO,
+ QUEUE_MAX
+};
+
+struct EntryInfo
+{
+ QueueType queueType;
+ QueueIt queueIt;
+ scheduler::EventId moveStaleEventId;
+};
+
+struct EntryItComparator
+{
+ bool
+ operator()(const iterator& a, const iterator& b) const
+ {
+ return *a < *b;
+ }
+};
+
+typedef std::map<iterator, EntryInfo*, EntryItComparator> EntryInfoMapFifo;
+
+/** \brief Priority Fifo cs replacement policy
+ *
+ * The entries that get removed first are unsolicited Data packets,
+ * which are the Data packets that got cached opportunistically without preceding
+ * forwarding of the corresponding Interest packet.
+ * Next, the Data packets with expired freshness are removed.
+ * Last, the Data packets are removed from the Content Store on a pure FIFO basis.
+ */
+class PriorityFifoPolicy : public Policy
+{
+public:
+ PriorityFifoPolicy();
+
+public:
+ static const std::string POLICY_NAME;
+
+private:
+ virtual void
+ doAfterInsert(iterator i) DECL_OVERRIDE;
+
+ virtual void
+ doAfterRefresh(iterator i) DECL_OVERRIDE;
+
+ virtual void
+ doBeforeErase(iterator i) DECL_OVERRIDE;
+
+ virtual void
+ doBeforeUse(iterator i) DECL_OVERRIDE;
+
+ virtual void
+ evictEntries() DECL_OVERRIDE;
+
+private:
+ /** \brief evicts one entry
+ * \pre CS is not empty
+ */
+ void
+ evictOne();
+
+ /** \brief attaches the entry to an appropriate queue
+ * \pre the entry is not in any queue
+ */
+ void
+ attachQueue(iterator i);
+
+ /** \brief detaches the entry from its current queue
+ * \post the entry is not in any queue
+ */
+ void
+ detachQueue(iterator i);
+
+ /** \brief moves an entry from FIFO queue to STALE queue
+ */
+ void
+ moveToStaleQueue(iterator i);
+
+private:
+ Queue m_queues[QUEUE_MAX];
+ EntryInfoMapFifo m_entryInfoMap;
+};
+
+} // namespace priorityfifo
+
+using priority_fifo::PriorityFifoPolicy;
+
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_POLICY_FIFO_HPP
\ No newline at end of file
diff --git a/daemon/table/cs-policy.cpp b/daemon/table/cs-policy.cpp
new file mode 100644
index 0000000..9726269
--- /dev/null
+++ b/daemon/table/cs-policy.cpp
@@ -0,0 +1,79 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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,
+ * The University of Memphis.
+ *
+ * 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/>.
+ */
+
+#include "cs-policy.hpp"
+#include "cs.hpp"
+
+namespace nfd {
+namespace cs {
+
+Policy::Policy(const std::string& policyName)
+ : m_policyName(policyName)
+{
+}
+
+Policy::~Policy()
+{
+}
+
+void
+Policy::setLimit(size_t nMaxEntries)
+{
+ BOOST_ASSERT(nMaxEntries > 0);
+ m_limit = nMaxEntries;
+
+ this->evictEntries();
+}
+
+void
+Policy::afterInsert(iterator i)
+{
+ BOOST_ASSERT(m_cs != nullptr);
+ this->doAfterInsert(i);
+}
+
+void
+Policy::afterRefresh(iterator i)
+{
+ BOOST_ASSERT(m_cs != nullptr);
+ this->doAfterRefresh(i);
+}
+
+void
+Policy::beforeErase(iterator i)
+{
+ BOOST_ASSERT(m_cs != nullptr);
+ this->doBeforeErase(i);
+}
+
+void
+Policy::beforeUse(iterator i)
+{
+ BOOST_ASSERT(m_cs != nullptr);
+ this->doBeforeUse(i);
+}
+
+} // namespace cs
+} // namespace nfd
diff --git a/daemon/table/cs-policy.hpp b/daemon/table/cs-policy.hpp
new file mode 100644
index 0000000..4beb114
--- /dev/null
+++ b/daemon/table/cs-policy.hpp
@@ -0,0 +1,191 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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,
+ * The University of Memphis.
+ *
+ * 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/>.
+ */
+
+#ifndef NFD_DAEMON_TABLE_CS_POLICY_HPP
+#define NFD_DAEMON_TABLE_CS_POLICY_HPP
+
+#include "cs-internal.hpp"
+#include "cs-entry-impl.hpp"
+
+namespace nfd {
+namespace cs {
+
+class Cs;
+
+/** \brief represents a CS replacement policy
+ */
+class Policy : noncopyable
+{
+public:
+ explicit
+ Policy(const std::string& policyName);
+
+ virtual
+ ~Policy();
+
+ const std::string&
+ getName() const;
+
+public:
+ /** \brief gets cs
+ */
+ Cs*
+ getCs() const;
+
+ /** \brief sets cs
+ */
+ void
+ setCs(Cs *cs);
+
+ /** \brief gets hard limit (in number of entries)
+ */
+ size_t
+ getLimit() const;
+
+ /** \brief sets hard limit (in number of entries)
+ * \post getLimit() == nMaxEntries
+ * \post cs.size() <= getLimit()
+ *
+ * The policy may evict entries if necessary.
+ */
+ void
+ setLimit(size_t nMaxEntries);
+
+ /** \brief emits when an entry is being evicted
+ *
+ * A policy implementation should emit this signal to cause CS to erase the entry from its index.
+ * CS should connect to this signal and erase the entry upon signal emission.
+ */
+ signal::Signal<Policy, iterator> beforeEvict;
+
+ /** \brief invoked by CS after a new entry is inserted
+ * \post cs.size() <= getLimit()
+ *
+ * The policy may evict entries if necessary.
+ * During this process, \p i might be evicted.
+ */
+ void
+ afterInsert(iterator i);
+
+ /** \brief invoked by CS after an existing entry is refreshed by same Data
+ *
+ * The policy may witness this refresh to make better eviction decisions in the future.
+ */
+ void
+ afterRefresh(iterator i);
+
+ /** \brief invoked by CS before an entry is erased due to management command
+ * \warning CS must not invoke this method if an entry is erased due to eviction.
+ */
+ void
+ beforeErase(iterator i);
+
+ /** \brief invoked by CS before an entry is used to match a lookup
+ *
+ * The policy may witness this usage to make better eviction decisions in the future.
+ */
+ void
+ beforeUse(iterator i);
+
+protected:
+ /** \brief invoked after a new entry is created in CS
+ *
+ * When overridden in a subclass, a policy implementation should decide whether to accept \p i.
+ * If \p i is accepted, it should be inserted into a cleanup index.
+ * Otherwise, \p beforeEvict signal should be emitted with \p i to inform CS to erase the entry.
+ * A policy implementation may decide to evict other entries by emitting \p beforeEvict signal,
+ * in order to keep CS size under limit.
+ */
+ virtual void
+ doAfterInsert(iterator i) = 0;
+
+ /** \brief invoked after an existing entry is refreshed by same Data
+ *
+ * When overridden in a subclass, a policy implementation may witness this operation
+ * and adjust its cleanup index.
+ */
+ virtual void
+ doAfterRefresh(iterator i) = 0;
+
+ /** \brief invoked before an entry is erased due to management command
+ * \note This will not be invoked for an entry being evicted by policy.
+ *
+ * When overridden in a subclass, a policy implementation should erase \p i
+ * from its cleanup index without emitted \p afterErase signal.
+ */
+ virtual void
+ doBeforeErase(iterator i) = 0;
+
+ /** \brief invoked before an entry is used to match a lookup
+ *
+ * When overridden in a subclass, a policy implementation may witness this operation
+ * and adjust its cleanup index.
+ */
+ virtual void
+ doBeforeUse(iterator i) = 0;
+
+ /** \brief evicts zero or more entries
+ * \post CS size does not exceed hard limit
+ */
+ virtual void
+ evictEntries() = 0;
+
+protected:
+ DECLARE_SIGNAL_EMIT(beforeEvict)
+
+private:
+ std::string m_policyName;
+ size_t m_limit;
+ Cs* m_cs;
+};
+
+inline const std::string&
+Policy::getName() const
+{
+ return m_policyName;
+}
+
+inline Cs*
+Policy::getCs() const
+{
+ return m_cs;
+}
+
+inline void
+Policy::setCs(Cs *cs)
+{
+ m_cs = cs;
+}
+
+inline size_t
+Policy::getLimit() const
+{
+ return m_limit;
+}
+
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_POLICY_HPP
\ No newline at end of file
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index a63d33e..9ea3d8b 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -24,9 +24,9 @@
*/
#include "cs.hpp"
+#include "cs-policy-priority-fifo.hpp"
#include "core/logger.hpp"
#include "core/algorithm.hpp"
-#include <numeric>
NFD_LOG_INIT("ContentStore");
@@ -44,18 +44,38 @@
BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Cs::const_iterator>));
#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
-Cs::Cs(size_t nMaxPackets)
- : m_limit(nMaxPackets)
+unique_ptr<Policy>
+makeDefaultPolicy()
{
- BOOST_ASSERT(nMaxPackets > 0);
+ return unique_ptr<Policy>(new PriorityFifoPolicy());
+}
+
+Cs::Cs(size_t nMaxPackets, unique_ptr<Policy> policy)
+{
+ this->setPolicyImpl(policy);
+ m_policy->setLimit(nMaxPackets);
}
void
Cs::setLimit(size_t nMaxPackets)
{
- BOOST_ASSERT(nMaxPackets > 0);
- m_limit = nMaxPackets;
- this->evict();
+ m_policy->setLimit(nMaxPackets);
+}
+
+size_t
+Cs::getLimit() const
+{
+ return m_policy->getLimit();
+}
+
+void
+Cs::setPolicy(unique_ptr<Policy> policy)
+{
+ BOOST_ASSERT(policy != nullptr);
+ BOOST_ASSERT(m_policy != nullptr);
+ size_t limit = m_policy->getLimit();
+ this->setPolicyImpl(policy);
+ m_policy->setLimit(limit);
}
bool
@@ -73,26 +93,25 @@
}
}
- bool isNewEntry = false; TableIt it;
+ bool isNewEntry = false;
+ iterator it;
// use .insert because gcc46 does not support .emplace
std::tie(it, isNewEntry) = m_table.insert(EntryImpl(data.shared_from_this(), isUnsolicited));
EntryImpl& entry = const_cast<EntryImpl&>(*it);
+ entry.updateStaleTime();
+
if (!isNewEntry) { // existing entry
- this->detachQueue(it);
// XXX This doesn't forbid unsolicited Data from refreshing a solicited entry.
if (entry.isUnsolicited() && !isUnsolicited) {
entry.unsetUnsolicited();
}
+
+ m_policy->afterRefresh(it);
}
- entry.updateStaleTime();
- this->attachQueue(it);
-
- // check there are same amount of entries in the table and in queues
- BOOST_ASSERT(m_table.size() == std::accumulate(m_queues, m_queues + QUEUE_MAX, 0U,
- [] (size_t sum, const Queue queue) { return sum + queue.size(); }));
-
- this->evict(); // XXX The new entry could be evicted, but it shouldn't matter.
+ else {
+ m_policy->afterInsert(it);
+ }
return true;
}
@@ -109,13 +128,13 @@
bool isRightmost = interest.getChildSelector() == 1;
NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
- TableIt first = m_table.lower_bound(prefix);
- TableIt last = m_table.end();
+ iterator first = m_table.lower_bound(prefix);
+ iterator last = m_table.end();
if (prefix.size() > 0) {
last = m_table.lower_bound(prefix.getSuccessor());
}
- TableIt match = last;
+ iterator match = last;
if (isRightmost) {
match = this->findRightmost(interest, first, last);
}
@@ -129,39 +148,40 @@
return;
}
NFD_LOG_DEBUG(" matching " << match->getName());
+ m_policy->beforeUse(match);
hitCallback(interest, match->getData());
}
-TableIt
-Cs::findLeftmost(const Interest& interest, TableIt first, TableIt last) const
+iterator
+Cs::findLeftmost(const Interest& interest, iterator first, iterator last) const
{
return std::find_if(first, last, bind(&cs::EntryImpl::canSatisfy, _1, interest));
}
-TableIt
-Cs::findRightmost(const Interest& interest, TableIt first, TableIt last) const
+iterator
+Cs::findRightmost(const Interest& interest, iterator first, iterator last) const
{
// Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
// If there is a match in that sub-namespace, the leftmost match is returned;
// otherwise, loop continues.
size_t interestNameLength = interest.getName().size();
- for (TableIt right = last; right != first;) {
- TableIt prev = std::prev(right);
+ for (iterator right = last; right != first;) {
+ iterator prev = std::prev(right);
// special case: [first,prev] have exact Names
if (prev->getName().size() == interestNameLength) {
NFD_LOG_TRACE(" find-among-exact " << prev->getName());
- TableIt matchExact = this->findRightmostAmongExact(interest, first, right);
+ iterator matchExact = this->findRightmostAmongExact(interest, first, right);
return matchExact == right ? last : matchExact;
}
Name prefix = prev->getName().getPrefix(interestNameLength + 1);
- TableIt left = m_table.lower_bound(prefix);
+ iterator left = m_table.lower_bound(prefix);
// normal case: [left,right) are under one-component-longer prefix
NFD_LOG_TRACE(" find-under-prefix " << prefix);
- TableIt match = this->findLeftmost(interest, left, right);
+ iterator match = this->findLeftmost(interest, left, right);
if (match != right) {
return match;
}
@@ -170,97 +190,22 @@
return last;
}
-TableIt
-Cs::findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const
+iterator
+Cs::findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const
{
return find_last_if(first, last, bind(&EntryImpl::canSatisfy, _1, interest));
}
void
-Cs::attachQueue(TableIt it)
+Cs::setPolicyImpl(unique_ptr<Policy>& policy)
{
- EntryImpl& entry = const_cast<EntryImpl&>(*it);
+ m_policy = std::move(policy);
+ m_beforeEvictConnection = m_policy->beforeEvict.connect([this] (iterator it) {
+ m_table.erase(it);
+ });
- if (entry.queueType != QUEUE_NONE) {
- this->detachQueue(it);
- }
-
- if (entry.isUnsolicited()) {
- entry.queueType = QUEUE_UNSOLICITED;
- }
- else if (entry.isStale()) {
- entry.queueType = QUEUE_STALE;
- }
- else {
- entry.queueType = QUEUE_FIFO;
-
- if (entry.canStale()) {
- entry.moveStaleEvent = scheduler::schedule(entry.getData().getFreshnessPeriod(),
- bind(&Cs::moveToStaleQueue, this, it));
- }
- }
-
- Queue& queue = m_queues[entry.queueType];
- entry.queueIt = queue.insert(queue.end(), it);
-}
-
-void
-Cs::detachQueue(TableIt it)
-{
- EntryImpl& entry = const_cast<EntryImpl&>(*it);
-
- BOOST_ASSERT(entry.queueType != QUEUE_NONE);
-
- if (entry.queueType == QUEUE_FIFO) {
- scheduler::cancel(entry.moveStaleEvent);
- }
-
- m_queues[entry.queueType].erase(entry.queueIt);
- entry.queueType = QUEUE_NONE;
-}
-
-void
-Cs::moveToStaleQueue(TableIt it)
-{
- EntryImpl& entry = const_cast<EntryImpl&>(*it);
-
- BOOST_ASSERT(entry.queueType == QUEUE_FIFO);
- m_queues[QUEUE_FIFO].erase(entry.queueIt);
-
- entry.queueType = QUEUE_STALE;
- Queue& queue = m_queues[QUEUE_STALE];
- entry.queueIt = queue.insert(queue.end(), it);
-}
-
-std::tuple<TableIt, std::string>
-Cs::evictPick()
-{
- if (!m_queues[QUEUE_UNSOLICITED].empty()) {
- return std::make_tuple(m_queues[QUEUE_UNSOLICITED].front(), "unsolicited");
- }
- if (!m_queues[QUEUE_STALE].empty()) {
- return std::make_tuple(m_queues[QUEUE_STALE].front(), "stale");
- }
- if (!m_queues[QUEUE_FIFO].empty()) {
- return std::make_tuple(m_queues[QUEUE_FIFO].front(), "fifo");
- }
-
- BOOST_ASSERT(false);
- return std::make_tuple(m_table.end(), "error");
-}
-
-
-void
-Cs::evict()
-{
- while (this->size() > m_limit) {
- TableIt it; std::string reason;
- std::tie(it, reason) = this->evictPick();
-
- NFD_LOG_DEBUG("evict " << it->getName() << " " << reason);
- this->detachQueue(it);
- m_table.erase(it);
- }
+ m_policy->setCs(this);
+ BOOST_ASSERT(m_policy->getCs() == this);
}
void
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 5e3bfbe..5a24bde 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -48,19 +48,25 @@
#ifndef NFD_DAEMON_TABLE_CS_HPP
#define NFD_DAEMON_TABLE_CS_HPP
+#include "cs-policy.hpp"
+#include "cs-internal.hpp"
#include "cs-entry-impl.hpp"
+#include <ndn-cxx/util/signal.hpp>
#include <boost/iterator/transform_iterator.hpp>
namespace nfd {
namespace cs {
+unique_ptr<Policy>
+makeDefaultPolicy();
+
/** \brief represents the ContentStore
*/
class Cs : noncopyable
{
public:
explicit
- Cs(size_t nMaxPackets = 10);
+ Cs(size_t nMaxPackets = 10, unique_ptr<Policy> policy = makeDefaultPolicy());
/** \brief inserts a Data packet
* \return true
@@ -97,9 +103,20 @@
/** \return capacity (in number of packets)
*/
size_t
- getLimit() const
+ getLimit() const;
+
+ /** \brief changes cs replacement policy
+ * \pre size() == 0
+ */
+ void
+ setPolicy(unique_ptr<Policy> policy);
+
+ /** \return cs replacement policy
+ */
+ Policy*
+ getPolicy() const
{
- return m_limit;
+ return m_policy.get();
}
/** \return number of stored packets
@@ -128,7 +145,7 @@
/** \brief ContentStore iterator (public API)
*/
- typedef boost::transform_iterator<EntryFromEntryImpl, TableIt, const Entry&> const_iterator;
+ typedef boost::transform_iterator<EntryFromEntryImpl, iterator, const Entry&> const_iterator;
const_iterator
begin() const
@@ -146,54 +163,28 @@
/** \brief find leftmost match in [first,last)
* \return the leftmost match, or last if not found
*/
- TableIt
- findLeftmost(const Interest& interest, TableIt left, TableIt right) const;
+ iterator
+ findLeftmost(const Interest& interest, iterator left, iterator right) const;
/** \brief find rightmost match in [first,last)
* \return the rightmost match, or last if not found
*/
- TableIt
- findRightmost(const Interest& interest, TableIt first, TableIt last) const;
+ iterator
+ findRightmost(const Interest& interest, iterator first, iterator last) const;
/** \brief find rightmost match among entries with exact Names in [first,last)
* \return the rightmost match, or last if not found
*/
- TableIt
- findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const;
+ iterator
+ findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const;
-private: // cleanup
- /** \brief attaches an entry to a suitable cleanup queue
- * \note if the entry is already attached to a queue, it's automatically detached
- */
void
- attachQueue(TableIt it);
-
- /** \brief detaches an entry from its current cleanup queue
- * \warning if the entry is unattached, this will cause undefined behavior
- */
- void
- detachQueue(TableIt it);
-
- /** \brief moves an entry from FIFO queue to STALE queue
- */
- void
- moveToStaleQueue(TableIt it);
-
- /** \brief picks an entry for eviction
- */
- std::tuple<TableIt, std::string/*reason*/>
- evictPick();
-
- /** \brief evicts zero or more entries so that number of stored entries
- * is not greater than capacity
- */
- void
- evict();
+ setPolicyImpl(unique_ptr<Policy>& policy);
private:
- size_t m_limit;
Table m_table;
- Queue m_queues[QUEUE_MAX];
+ unique_ptr<Policy> m_policy;
+ ndn::util::signal::ScopedConnection m_beforeEvictConnection;
};
} // namespace cs
diff --git a/tests/daemon/table/cs-policy-priority-fifo.t.cpp b/tests/daemon/table/cs-policy-priority-fifo.t.cpp
new file mode 100644
index 0000000..e88f8d5
--- /dev/null
+++ b/tests/daemon/table/cs-policy-priority-fifo.t.cpp
@@ -0,0 +1,148 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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,
+ * The University of Memphis.
+ *
+ * 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/>.
+ */
+
+#include "table/cs.hpp"
+#include "table/cs-policy-priority-fifo.hpp"
+#include <ndn-cxx/util/crypto.hpp>
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace cs {
+namespace tests {
+
+using namespace nfd::tests;
+using ndn::nfd::LocalControlHeader;
+
+BOOST_AUTO_TEST_SUITE(CsPriorityFifo)
+
+BOOST_FIXTURE_TEST_CASE(EvictOne, UnitTestTimeFixture)
+{
+ Cs cs(3);
+ cs.setPolicy(unique_ptr<Policy>(new PriorityFifoPolicy()));
+
+ shared_ptr<Data> dataA = makeData("ndn:/A");
+ dataA->setFreshnessPeriod(time::milliseconds(99999));
+ dataA->wireEncode();
+ cs.insert(*dataA);
+
+ shared_ptr<Data> dataB = makeData("ndn:/B");
+ dataB->setFreshnessPeriod(time::milliseconds(10));
+ dataB->wireEncode();
+ cs.insert(*dataB);
+
+ shared_ptr<Data> dataC = makeData("ndn:/C");
+ dataC->setFreshnessPeriod(time::milliseconds(99999));
+ dataC->wireEncode();
+ cs.insert(*dataC, true);
+
+ this->advanceClocks(time::milliseconds(11));
+
+ // evict unsolicited
+ shared_ptr<Data> dataD = makeData("ndn:/D");
+ dataD->setFreshnessPeriod(time::milliseconds(99999));
+ dataD->wireEncode();
+ cs.insert(*dataD);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ cs.find(Interest("ndn:/C"),
+ bind([] { BOOST_CHECK(false); }),
+ bind([] { BOOST_CHECK(true); }));
+
+ // evict stale
+ shared_ptr<Data> dataE = makeData("ndn:/E");
+ dataE->setFreshnessPeriod(time::milliseconds(99999));
+ dataE->wireEncode();
+ cs.insert(*dataE);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ cs.find(Interest("ndn:/B"),
+ bind([] { BOOST_CHECK(false); }),
+ bind([] { BOOST_CHECK(true); }));
+
+ // evict fifo
+ shared_ptr<Data> dataF = makeData("ndn:/F");
+ dataF->setFreshnessPeriod(time::milliseconds(99999));
+ dataF->wireEncode();
+ cs.insert(*dataF);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ cs.find(Interest("ndn:/A"),
+ bind([] { BOOST_CHECK(false); }),
+ bind([] { BOOST_CHECK(true); }));
+}
+
+BOOST_FIXTURE_TEST_CASE(Refresh, UnitTestTimeFixture)
+{
+ Cs cs(3);
+ cs.setPolicy(unique_ptr<Policy>(new PriorityFifoPolicy()));
+
+ shared_ptr<Data> dataA = makeData("ndn:/A");
+ dataA->setFreshnessPeriod(time::milliseconds(99999));
+ dataA->wireEncode();
+ cs.insert(*dataA);
+
+ shared_ptr<Data> dataB = makeData("ndn:/B");
+ dataB->setFreshnessPeriod(time::milliseconds(10));
+ dataB->wireEncode();
+ cs.insert(*dataB);
+
+ shared_ptr<Data> dataC = makeData("ndn:/C");
+ dataC->setFreshnessPeriod(time::milliseconds(10));
+ dataC->wireEncode();
+ cs.insert(*dataC);
+
+ this->advanceClocks(time::milliseconds(11));
+
+ // refresh dataB
+ shared_ptr<Data> dataB2 = make_shared<Data>(*dataB);
+ dataB2->wireEncode();
+ cs.insert(*dataB2);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ cs.find(Interest("ndn:/A"),
+ bind([] { BOOST_CHECK(true); }),
+ bind([] { BOOST_CHECK(false); }));
+
+ cs.find(Interest("ndn:/B"),
+ bind([] { BOOST_CHECK(true); }),
+ bind([] { BOOST_CHECK(false); }));
+
+ cs.find(Interest("ndn:/C"),
+ bind([] { BOOST_CHECK(true); }),
+ bind([] { BOOST_CHECK(false); }));
+
+ // evict dataC stale
+ shared_ptr<Data> dataD = makeData("ndn:/D");
+ dataD->setFreshnessPeriod(time::milliseconds(99999));
+ dataD->wireEncode();
+ cs.insert(*dataD);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ cs.find(Interest("ndn:/C"),
+ bind([] { BOOST_CHECK(false); }),
+ bind([] { BOOST_CHECK(true); }));
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace cs
+} // namespace nfd
diff --git a/tests/daemon/table/cs.t.cpp b/tests/daemon/table/cs.t.cpp
index 521df2d..0b3bebb 100644
--- a/tests/daemon/table/cs.t.cpp
+++ b/tests/daemon/table/cs.t.cpp
@@ -330,107 +330,6 @@
bind([] { BOOST_CHECK(true); }));
}
-BOOST_FIXTURE_TEST_CASE(Evict, UnitTestTimeFixture)
-{
- Cs cs(3);
-
- shared_ptr<Data> dataA = makeData("ndn:/A");
- dataA->setFreshnessPeriod(time::milliseconds(99999));
- dataA->wireEncode();
- cs.insert(*dataA);
-
- shared_ptr<Data> dataB = makeData("ndn:/B");
- dataB->setFreshnessPeriod(time::milliseconds(10));
- dataB->wireEncode();
- cs.insert(*dataB);
-
- shared_ptr<Data> dataC = makeData("ndn:/C");
- dataC->setFreshnessPeriod(time::milliseconds(99999));
- dataC->wireEncode();
- cs.insert(*dataC, true);
-
- this->advanceClocks(time::milliseconds(11));
-
- // evict unsolicited
- shared_ptr<Data> dataD = makeData("ndn:/D");
- dataD->setFreshnessPeriod(time::milliseconds(99999));
- dataD->wireEncode();
- cs.insert(*dataD);
- BOOST_CHECK_EQUAL(cs.size(), 3);
- cs.find(Interest("ndn:/C"),
- bind([] { BOOST_CHECK(false); }),
- bind([] { BOOST_CHECK(true); }));
-
- // evict stale
- shared_ptr<Data> dataE = makeData("ndn:/E");
- dataE->setFreshnessPeriod(time::milliseconds(99999));
- dataE->wireEncode();
- cs.insert(*dataE);
- BOOST_CHECK_EQUAL(cs.size(), 3);
- cs.find(Interest("ndn:/B"),
- bind([] { BOOST_CHECK(false); }),
- bind([] { BOOST_CHECK(true); }));
-
- // evict fifo
- shared_ptr<Data> dataF = makeData("ndn:/F");
- dataF->setFreshnessPeriod(time::milliseconds(99999));
- dataF->wireEncode();
- cs.insert(*dataF);
- BOOST_CHECK_EQUAL(cs.size(), 3);
- cs.find(Interest("ndn:/A"),
- bind([] { BOOST_CHECK(false); }),
- bind([] { BOOST_CHECK(true); }));
-}
-
-BOOST_FIXTURE_TEST_CASE(Refresh, UnitTestTimeFixture)
-{
- Cs cs(3);
-
- shared_ptr<Data> dataA = makeData("ndn:/A");
- dataA->setFreshnessPeriod(time::milliseconds(99999));
- dataA->wireEncode();
- cs.insert(*dataA);
-
- shared_ptr<Data> dataB = makeData("ndn:/B");
- dataB->setFreshnessPeriod(time::milliseconds(10));
- dataB->wireEncode();
- cs.insert(*dataB);
-
- shared_ptr<Data> dataC = makeData("ndn:/C");
- dataC->setFreshnessPeriod(time::milliseconds(10));
- dataC->wireEncode();
- cs.insert(*dataC);
-
- this->advanceClocks(time::milliseconds(11));
-
- // refresh dataB
- shared_ptr<Data> dataB2 = make_shared<Data>(*dataB);
- dataB2->wireEncode();
- cs.insert(*dataB2);
- BOOST_CHECK_EQUAL(cs.size(), 3);
- cs.find(Interest("ndn:/A"),
- bind([] { BOOST_CHECK(true); }),
- bind([] { BOOST_CHECK(false); }));
-
- cs.find(Interest("ndn:/B"),
- bind([] { BOOST_CHECK(true); }),
- bind([] { BOOST_CHECK(false); }));
-
- cs.find(Interest("ndn:/C"),
- bind([] { BOOST_CHECK(true); }),
- bind([] { BOOST_CHECK(false); }));
-
- // evict dataC stale
- shared_ptr<Data> dataD = makeData("ndn:/D");
- dataD->setFreshnessPeriod(time::milliseconds(99999));
- dataD->wireEncode();
- cs.insert(*dataD);
- BOOST_CHECK_EQUAL(cs.size(), 3);
- cs.find(Interest("ndn:/C"),
- bind([] { BOOST_CHECK(false); }),
- bind([] { BOOST_CHECK(true); }));
-}
-
BOOST_AUTO_TEST_CASE(Enumeration)
{
Cs cs;