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