NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
in-memory-storage.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2013-2019 Regents of the University of California.
4  *
5  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
6  *
7  * ndn-cxx library is free software: you can redistribute it and/or modify it under the
8  * terms of the GNU Lesser General Public License as published by the Free Software
9  * Foundation, either version 3 of the License, or (at your option) any later version.
10  *
11  * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
12  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
13  * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
14  *
15  * You should have received copies of the GNU General Public License and GNU Lesser
16  * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
17  * <http://www.gnu.org/licenses/>.
18  *
19  * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
20  */
21 
24 
25 namespace ndn {
26 
27 const time::milliseconds InMemoryStorage::INFINITE_WINDOW(-1);
28 const time::milliseconds InMemoryStorage::ZERO_WINDOW(0);
29 
32  : m_ptr(ptr)
33  , m_cache(cache)
34  , m_it(it)
35 {
36 }
37 
40 {
41  m_it++;
42  if (m_it != m_cache->get<byFullName>().end()) {
43  m_ptr = &((*m_it)->getData());
44  }
45  else {
46  m_ptr = nullptr;
47  }
48 
49  return *this;
50 }
51 
54 {
56  this->operator++();
57  return i;
58 }
59 
62 {
63  return *m_ptr;
64 }
65 
68 {
69  return m_ptr;
70 }
71 
72 bool
74 {
75  return m_it == rhs.m_it;
76 }
77 
78 bool
80 {
81  return m_it != rhs.m_it;
82 }
83 
85  : m_limit(limit)
86  , m_nPackets(0)
87 {
88  init();
89 }
90 
92  : m_limit(limit)
93  , m_nPackets(0)
94 {
95  m_scheduler = make_unique<Scheduler>(ioService);
96  init();
97 }
98 
99 void
100 InMemoryStorage::init()
101 {
102  // TODO consider a more suitable initial value
103  m_capacity = m_initCapacity;
104 
105  if (m_limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
106  m_capacity = m_limit;
107  }
108 
109  for (size_t i = 0; i < m_capacity; i++) {
110  m_freeEntries.push(new InMemoryStorageEntry());
111  }
112 }
113 
115 {
116  // evict all items from cache
117  Cache::iterator it = m_cache.begin();
118  while (it != m_cache.end()) {
119  it = freeEntry(it);
120  }
121 
122  BOOST_ASSERT(m_freeEntries.size() == m_capacity);
123 
124  while (!m_freeEntries.empty()) {
125  delete m_freeEntries.top();
126  m_freeEntries.pop();
127  }
128 }
129 
130 void
131 InMemoryStorage::setCapacity(size_t capacity)
132 {
133  size_t oldCapacity = m_capacity;
134  m_capacity = std::max(capacity, m_initCapacity);
135 
136  if (size() > m_capacity) {
137  ssize_t nAllowedFailures = size() - m_capacity;
138  while (size() > m_capacity) {
139  if (!evictItem() && --nAllowedFailures < 0) {
140  BOOST_THROW_EXCEPTION(Error());
141  }
142  }
143  }
144 
145  if (m_capacity >= oldCapacity) {
146  for (size_t i = oldCapacity; i < m_capacity; i++) {
147  m_freeEntries.push(new InMemoryStorageEntry());
148  }
149  }
150  else {
151  for (size_t i = oldCapacity; i > m_capacity; i--) {
152  delete m_freeEntries.top();
153  m_freeEntries.pop();
154  }
155  }
156 
157  BOOST_ASSERT(size() + m_freeEntries.size() == m_capacity);
158 }
159 
160 void
161 InMemoryStorage::insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow)
162 {
163  // check if identical Data/Name already exists
164  auto it = m_cache.get<byFullName>().find(data.getFullName());
165  if (it != m_cache.get<byFullName>().end())
166  return;
167 
168  //if full, double the capacity
169  bool doesReachLimit = (getLimit() == getCapacity());
170  if (isFull() && !doesReachLimit) {
171  // note: This is incorrect if 2*capacity overflows, but memory should run out before that
172  size_t newCapacity = std::min(2 * getCapacity(), getLimit());
173  setCapacity(newCapacity);
174  }
175 
176  //if full and reach limitation of the capacity, employ replacement policy
177  if (isFull() && doesReachLimit) {
178  evictItem();
179  }
180 
181  //insert to cache
182  BOOST_ASSERT(m_freeEntries.size() > 0);
183  // take entry for the memory pool
184  InMemoryStorageEntry* entry = m_freeEntries.top();
185  m_freeEntries.pop();
186  m_nPackets++;
187  entry->setData(data);
188  if (m_scheduler != nullptr && mustBeFreshProcessingWindow > ZERO_WINDOW) {
189  entry->scheduleMarkStale(*m_scheduler, mustBeFreshProcessingWindow);
190  }
191  m_cache.insert(entry);
192 
193  //let derived class do something with the entry
194  afterInsert(entry);
195 }
196 
197 shared_ptr<const Data>
199 {
200  auto it = m_cache.get<byFullName>().lower_bound(name);
201 
202  // if not found, return null
203  if (it == m_cache.get<byFullName>().end()) {
204  return nullptr;
205  }
206 
207  // if the given name is not the prefix of the lower_bound, return null
208  if (!name.isPrefixOf((*it)->getFullName())) {
209  return nullptr;
210  }
211 
212  afterAccess(*it);
213  return ((*it)->getData()).shared_from_this();
214 }
215 
216 shared_ptr<const Data>
218 {
219  // if the interest contains implicit digest, it is possible to directly locate a packet.
220  auto it = m_cache.get<byFullName>().find(interest.getName());
221 
222  // if a packet is located by its full name, it must be the packet to return.
223  if (it != m_cache.get<byFullName>().end()) {
224  return ((*it)->getData()).shared_from_this();
225  }
226 
227  // if the packet is not discovered by last step, either the packet is not in the storage or
228  // the interest doesn't contains implicit digest.
229  it = m_cache.get<byFullName>().lower_bound(interest.getName());
230 
231  if (it == m_cache.get<byFullName>().end()) {
232  return nullptr;
233  }
234 
235  // to locate the element that has a just smaller name than the interest's
236  if (it != m_cache.get<byFullName>().begin()) {
237  it--;
238  }
239 
240  InMemoryStorageEntry* ret = selectChild(interest, it);
241  if (ret == nullptr) {
242  return nullptr;
243  }
244 
245  // let derived class do something with the entry
246  afterAccess(ret);
247  return ret->getData().shared_from_this();
248 }
249 
252 {
253  for (; it != m_cache.get<byFullName>().end(); it++) {
254  if ((*it)->isFresh())
255  return it;
256  }
257 
258  return it;
259 }
260 
263  Cache::index<byFullName>::type::iterator startingPoint) const
264 {
265  BOOST_ASSERT(startingPoint != m_cache.get<byFullName>().end());
266 
267  if (startingPoint != m_cache.get<byFullName>().begin()) {
268  BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
269  }
270 
271  bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
272  bool hasRightmostSelector = !hasLeftmostSelector;
273 
274  // filter out "stale" data
275  if (interest.getMustBeFresh()) {
276  startingPoint = findNextFresh(startingPoint);
277  }
278 
279  if (startingPoint == m_cache.get<byFullName>().end()) {
280  return nullptr;
281  }
282 
283  if (hasLeftmostSelector) {
284  if (interest.matchesData((*startingPoint)->getData())) {
285  return *startingPoint;
286  }
287  }
288 
289  // iterate to the right
290  auto rightmost = startingPoint;
291  if (startingPoint != m_cache.get<byFullName>().end()) {
292  auto rightmostCandidate = startingPoint;
293  Name currentChildPrefix("");
294 
295  while (true) {
296  ++rightmostCandidate;
297  // filter out "stale" data
298  if (interest.getMustBeFresh()) {
299  rightmostCandidate = findNextFresh(rightmostCandidate);
300  }
301 
302  bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
303  bool isInPrefix = false;
304  if (isInBoundaries) {
305  isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
306  }
307 
308  if (isInPrefix) {
309  if (interest.matchesData((*rightmostCandidate)->getData())) {
310  if (hasLeftmostSelector) {
311  return *rightmostCandidate;
312  }
313 
314  if (hasRightmostSelector) {
315  // get prefix which is one component longer than Interest name
316  const Name& childPrefix = (*rightmostCandidate)->getFullName().getPrefix(interest.getName().size() + 1);
317  if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix)) {
318  currentChildPrefix = childPrefix;
319  rightmost = rightmostCandidate;
320  }
321  }
322  }
323  }
324  else {
325  break;
326  }
327  }
328  }
329 
330  if (rightmost != startingPoint) {
331  return *rightmost;
332  }
333 
334  if (hasRightmostSelector) { // if rightmost was not found, try starting point
335  if (interest.matchesData((*startingPoint)->getData())) {
336  return *startingPoint;
337  }
338  }
339 
340  return nullptr;
341 }
342 
344 InMemoryStorage::freeEntry(Cache::iterator it)
345 {
346  // push the *empty* entry into mem pool
347  (*it)->release();
348  m_freeEntries.push(*it);
349  m_nPackets--;
350  return m_cache.erase(it);
351 }
352 
353 void
354 InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
355 {
356  if (isPrefix) {
357  auto it = m_cache.get<byFullName>().lower_bound(prefix);
358  while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
359  // let derived class do something with the entry
360  beforeErase(*it);
361  it = freeEntry(it);
362  }
363  }
364  else {
365  auto it = m_cache.get<byFullName>().find(prefix);
366  if (it == m_cache.get<byFullName>().end())
367  return;
368 
369  // let derived class do something with the entry
370  beforeErase(*it);
371  freeEntry(it);
372  }
373 
374  if (m_freeEntries.size() > (2 * size()))
375  setCapacity(getCapacity() / 2);
376 }
377 
378 void
380 {
381  auto it = m_cache.get<byFullName>().find(name);
382  if (it == m_cache.get<byFullName>().end())
383  return;
384 
385  freeEntry(it);
386 }
387 
390 {
391  auto it = m_cache.get<byFullName>().begin();
392  return const_iterator(&((*it)->getData()), &m_cache, it);
393 }
394 
397 {
398  auto it = m_cache.get<byFullName>().end();
399  return const_iterator(nullptr, &m_cache, it);
400 }
401 
402 void
404 {
405 }
406 
407 void
409 {
410 }
411 
412 void
413 InMemoryStorage::afterAccess(InMemoryStorageEntry* entry)
414 {
415 }
416 
417 void
418 InMemoryStorage::printCache(std::ostream& os) const
419 {
420  // start from the upper layer towards bottom
421  for (const auto& elem : m_cache.get<byFullName>())
422  os << elem->getFullName() << std::endl;
423 }
424 
425 } // namespace ndn
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix of the name.
Definition: name.hpp:203
Copyright (c) 2011-2015 Regents of the University of California.
void erase(const Name &prefix, const bool isPrefix=true)
Deletes in-memory storage entry by prefix by default.
int getChildSelector() const
Definition: interest.hpp:427
Cache::index< byFullName >::type::iterator findNextFresh(Cache::index< byFullName >::type::iterator startingPoint) const
Get the next iterator (include startingPoint) that satisfies MustBeFresh requirement.
virtual bool evictItem()=0
Removes one Data packet from in-memory storage based on derived class implemented replacement policy.
void printCache(std::ostream &os) const
Prints contents of the in-memory storage.
bool isPrefixOf(const Name &other) const
Check if this name is a prefix of another name.
Definition: name.cpp:251
Represents an Interest packet.
Definition: interest.hpp:44
bool operator==(const const_iterator &rhs)
boost::multi_index_container< InMemoryStorageEntry *, boost::multi_index::indexed_by< boost::multi_index::ordered_unique< boost::multi_index::tag< byFullName >, boost::multi_index::const_mem_fun< InMemoryStorageEntry, const Name &, &InMemoryStorageEntry::getFullName >, std::less< Name > > > > Cache
bool operator!=(const const_iterator &rhs)
InMemoryStorage::const_iterator end() const
Returns end iterator of the in-memory storage ordering by name with digest.
Table::const_iterator iterator
Definition: cs-internal.hpp:41
virtual void beforeErase(InMemoryStorageEntry *entry)
Update the entry or other data structures before a entry is successfully erased according to derived ...
InMemoryStorage(size_t limit=std::numeric_limits< size_t >::max())
Create a InMemoryStorage with up to limit entries The InMemoryStorage created through this method wil...
shared_ptr< const Data > find(const Interest &interest)
Finds the best match Data for an Interest.
const Data & getData() const
Returns the Data packet stored in the in-memory storage entry.
virtual void afterInsert(InMemoryStorageEntry *entry)
Update the entry or other data structures after a entry is successfully inserted according to derived...
InMemoryStorageEntry * selectChild(const Interest &interest, Cache::index< byFullName >::type::iterator startingPoint) const
Implements child selector (leftmost, rightmost, undeclared).
Represents a self-defined const_iterator for the in-memory storage.
bool matchesData(const Data &data) const
Check if Interest can be satisfied by data.
Definition: interest.cpp:445
Represents an absolute name.
Definition: name.hpp:43
Represents an in-memory storage entry.
const Name & getFullName() const
Get full name including implicit digest.
Definition: data.cpp:196
size_t size() const
Get number of components.
Definition: name.hpp:147
const_iterator(const Data *ptr, const Cache *cache, Cache::index< byFullName >::type::iterator it)
bool isFull() const
returns true if the in-memory storage uses up the current capacity, false otherwise
bool empty() const
Check if name is empty.
Definition: name.hpp:139
void insert(const Data &data, const time::milliseconds &mustBeFreshProcessingWindow=INFINITE_WINDOW)
Inserts a Data packet.
bool getMustBeFresh() const
Check whether the MustBeFresh element is present.
Definition: interest.hpp:202
InMemoryStorage::const_iterator begin() const
Returns begin iterator of the in-memory storage ordering by name with digest.
Represents a Data packet.
Definition: data.hpp:35
void eraseImpl(const Name &name)
deletes in-memory storage entries by the Name with implicit digest.
static const time::milliseconds INFINITE_WINDOW
size_t getCapacity() const
returns current capacity of in-memory storage (in packets)
const Name & getName() const
Definition: interest.hpp:134