NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
cs.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2018, Regents of the University of California,
4  * Arizona Board of Regents,
5  * Colorado State University,
6  * University Pierre & Marie Curie, Sorbonne University,
7  * Washington University in St. Louis,
8  * Beijing Institute of Technology,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #include "cs.hpp"
27 #include "core/algorithm.hpp"
28 #include "core/logger.hpp"
29 
30 #include <ndn-cxx/lp/tags.hpp>
32 
33 namespace nfd {
34 namespace cs {
35 
37 
39 
40 static unique_ptr<Policy>
42 {
43  return Policy::create("lru");
44 }
45 
46 Cs::Cs(size_t nMaxPackets)
47  : m_shouldAdmit(true)
48  , m_shouldServe(true)
49 {
50  this->setPolicyImpl(makeDefaultPolicy());
51  m_policy->setLimit(nMaxPackets);
52 }
53 
54 void
55 Cs::insert(const Data& data, bool isUnsolicited)
56 {
57  if (!m_shouldAdmit || m_policy->getLimit() == 0) {
58  return;
59  }
60  NFD_LOG_DEBUG("insert " << data.getName());
61 
62  // recognize CachePolicy
63  shared_ptr<lp::CachePolicyTag> tag = data.getTag<lp::CachePolicyTag>();
64  if (tag != nullptr) {
65  lp::CachePolicyType policy = tag->get().getPolicy();
66  if (policy == lp::CachePolicyType::NO_CACHE) {
67  return;
68  }
69  }
70 
71  iterator it;
72  bool isNewEntry = false;
73  std::tie(it, isNewEntry) = m_table.emplace(data.shared_from_this(), isUnsolicited);
74  EntryImpl& entry = const_cast<EntryImpl&>(*it);
75 
76  entry.updateStaleTime();
77 
78  if (!isNewEntry) { // existing entry
79  // XXX This doesn't forbid unsolicited Data from refreshing a solicited entry.
80  if (entry.isUnsolicited() && !isUnsolicited) {
81  entry.unsetUnsolicited();
82  }
83 
84  m_policy->afterRefresh(it);
85  }
86  else {
87  m_policy->afterInsert(it);
88  }
89 }
90 
91 void
92 Cs::erase(const Name& prefix, size_t limit, const AfterEraseCallback& cb)
93 {
94  BOOST_ASSERT(static_cast<bool>(cb));
95 
96  iterator first = m_table.lower_bound(prefix);
97  iterator last = m_table.end();
98  if (prefix.size() > 0) {
99  last = m_table.lower_bound(prefix.getSuccessor());
100  }
101 
102  size_t nErased = 0;
103  while (first != last && nErased < limit) {
104  m_policy->beforeErase(first);
105  first = m_table.erase(first);
106  ++nErased;
107  }
108 
109  if (cb) {
110  cb(nErased);
111  }
112 }
113 
114 void
115 Cs::find(const Interest& interest,
116  const HitCallback& hitCallback,
117  const MissCallback& missCallback) const
118 {
119  BOOST_ASSERT(static_cast<bool>(hitCallback));
120  BOOST_ASSERT(static_cast<bool>(missCallback));
121 
122  if (!m_shouldServe || m_policy->getLimit() == 0) {
123  missCallback(interest);
124  return;
125  }
126  const Name& prefix = interest.getName();
127  bool isRightmost = interest.getChildSelector() == 1;
128  NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
129 
130  iterator first = m_table.lower_bound(prefix);
131  iterator last = m_table.end();
132  if (prefix.size() > 0) {
133  last = m_table.lower_bound(prefix.getSuccessor());
134  }
135 
136  iterator match = last;
137  if (isRightmost) {
138  match = this->findRightmost(interest, first, last);
139  }
140  else {
141  match = this->findLeftmost(interest, first, last);
142  }
143 
144  if (match == last) {
145  NFD_LOG_DEBUG(" no-match");
146  missCallback(interest);
147  return;
148  }
149  NFD_LOG_DEBUG(" matching " << match->getName());
150  m_policy->beforeUse(match);
151  hitCallback(interest, match->getData());
152 }
153 
154 iterator
155 Cs::findLeftmost(const Interest& interest, iterator first, iterator last) const
156 {
157  return std::find_if(first, last, [&interest] (const auto& entry) { return entry.canSatisfy(interest); });
158 }
159 
160 iterator
161 Cs::findRightmost(const Interest& interest, iterator first, iterator last) const
162 {
163  // Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
164  // If there is a match in that sub-namespace, the leftmost match is returned;
165  // otherwise, loop continues.
166 
167  size_t interestNameLength = interest.getName().size();
168  for (iterator right = last; right != first;) {
169  iterator prev = std::prev(right);
170 
171  // special case: [first,prev] have exact Names
172  if (prev->getName().size() == interestNameLength) {
173  NFD_LOG_TRACE(" find-among-exact " << prev->getName());
174  iterator matchExact = this->findRightmostAmongExact(interest, first, right);
175  return matchExact == right ? last : matchExact;
176  }
177 
178  Name prefix = prev->getName().getPrefix(interestNameLength + 1);
179  iterator left = m_table.lower_bound(prefix);
180 
181  // normal case: [left,right) are under one-component-longer prefix
182  NFD_LOG_TRACE(" find-under-prefix " << prefix);
183  iterator match = this->findLeftmost(interest, left, right);
184  if (match != right) {
185  return match;
186  }
187  right = left;
188  }
189  return last;
190 }
191 
192 iterator
193 Cs::findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const
194 {
195  return find_last_if(first, last, [&interest] (const auto& entry) { return entry.canSatisfy(interest); });
196 }
197 
198 void
199 Cs::dump()
200 {
201  NFD_LOG_DEBUG("dump table");
202  for (const EntryImpl& entry : m_table) {
203  NFD_LOG_TRACE(entry.getFullName());
204  }
205 }
206 
207 void
208 Cs::setPolicy(unique_ptr<Policy> policy)
209 {
210  BOOST_ASSERT(policy != nullptr);
211  BOOST_ASSERT(m_policy != nullptr);
212  size_t limit = m_policy->getLimit();
213  this->setPolicyImpl(std::move(policy));
214  m_policy->setLimit(limit);
215 }
216 
217 void
218 Cs::setPolicyImpl(unique_ptr<Policy> policy)
219 {
220  NFD_LOG_DEBUG("set-policy " << policy->getName());
221  m_policy = std::move(policy);
222  m_beforeEvictConnection = m_policy->beforeEvict.connect([this] (iterator it) {
223  m_table.erase(it);
224  });
225 
226  m_policy->setCs(this);
227  BOOST_ASSERT(m_policy->getCs() == this);
228 }
229 
230 void
231 Cs::enableAdmit(bool shouldAdmit)
232 {
233  if (m_shouldAdmit == shouldAdmit) {
234  return;
235  }
236  m_shouldAdmit = shouldAdmit;
237  NFD_LOG_INFO((shouldAdmit ? "Enabling" : "Disabling") << " Data admittance");
238 }
239 
240 void
241 Cs::enableServe(bool shouldServe)
242 {
243  if (m_shouldServe == shouldServe) {
244  return;
245  }
246  m_shouldServe = shouldServe;
247  NFD_LOG_INFO((shouldServe ? "Enabling" : "Disabling") << " Data serving");
248 }
249 
250 } // namespace cs
251 } // namespace nfd
std::function< void(size_t nErased)> AfterEraseCallback
Definition: cs.hpp:59
shared_ptr< T > getTag() const
get a tag item
Definition: tag-host.hpp:66
const Name & getName() const
Get name.
Definition: data.hpp:124
int getChildSelector() const
Definition: interest.hpp:427
static unique_ptr< Policy > makeDefaultPolicy()
Definition: cs.cpp:41
bool isUnsolicited() const
Definition: cs-entry.hpp:73
static unique_ptr< Policy > create(const std::string &policyName)
Definition: cs-policy.cpp:46
Name getSuccessor() const
Get the successor of a name.
Definition: name.cpp:241
bool shouldAdmit() const
get CS_ENABLE_ADMIT flag
Definition: cs.hpp:128
#define NFD_LOG_INFO
Definition: logger.hpp:39
It find_last_if(It first, It last, Pred p)
Definition: algorithm.hpp:49
Represents an Interest packet.
Definition: interest.hpp:44
bool shouldServe() const
get CS_ENABLE_SERVE flag
Definition: cs.hpp:143
void enableAdmit(bool shouldAdmit)
set CS_ENABLE_ADMIT flag
Definition: cs.cpp:231
NDN_CXX_ASSERT_FORWARD_ITERATOR(Cs::const_iterator)
an Entry in ContentStore implementation
provides a tag type for simple types
Definition: tag.hpp:58
Table::const_iterator iterator
Definition: cs-internal.hpp:41
void insert(const Data &data, bool isUnsolicited=false)
inserts a Data packet
Definition: cs.cpp:55
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
#define NFD_LOG_TRACE
Definition: logger.hpp:37
constexpr const T & get() const noexcept
Definition: tag.hpp:86
void erase(const Name &prefix, size_t limit, const AfterEraseCallback &cb)
asynchronously erases entries under prefix
Definition: cs.cpp:92
ContentStore
Definition: cs.cpp:38
boost::transform_iterator< EntryFromEntryImpl, iterator, const Entry & > const_iterator
ContentStore iterator (public API)
Definition: cs.hpp:168
void setPolicy(unique_ptr< Policy > policy)
change replacement policy
Definition: cs.cpp:208
Cs(size_t nMaxPackets=10)
Definition: cs.cpp:46
CachePolicyType
indicates the cache policy applied to a Data packet
Represents an absolute name.
Definition: name.hpp:43
void find(const Interest &interest, const HitCallback &hitCallback, const MissCallback &missCallback) const
finds the best matching Data packet
Definition: cs.cpp:115
size_t size() const
Get number of components.
Definition: name.hpp:147
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
void updateStaleTime()
refreshes stale time relative to current time
Definition: cs-entry.cpp:48
std::function< void(const Interest &, const Data &)> HitCallback
Definition: cs.hpp:70
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
Represents a Data packet.
Definition: data.hpp:35
std::function< void(const Interest &)> MissCallback
Definition: cs.hpp:71
void enableServe(bool shouldServe)
set CS_ENABLE_SERVE flag
Definition: cs.cpp:241
const Name & getName() const
Definition: interest.hpp:134