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-2017 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 
22 #include "in-memory-storage.hpp"
24 
25 namespace ndn {
26 
27 const time::milliseconds InMemoryStorage::INFINITE_WINDOW(-1);
28 const time::milliseconds InMemoryStorage::ZERO_WINDOW(0);
29 
31  Cache::index<byFullName>::type::iterator it)
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 = 0;
47  }
48 
49  return *this;
50 }
51 
54 {
56  this->operator++();
57  return i;
58 }
59 
60 const Data&
62 {
63  return *m_ptr;
64 }
65 
66 const Data*
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 
91 InMemoryStorage::InMemoryStorage(boost::asio::io_service& ioService, size_t limit)
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 = 10;
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
132 {
133  size_t oldCapacity = m_capacity;
134  m_capacity = capacity;
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  Cache::index<byFullName>::type::iterator 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  auto eventId = make_unique<util::scheduler::ScopedEventId>(*m_scheduler);
190  *eventId = m_scheduler->scheduleEvent(mustBeFreshProcessingWindow,
191  bind(&InMemoryStorageEntry::markStale, entry));
192  entry->setMarkStaleEventId(std::move(eventId));
193  }
194  m_cache.insert(entry);
195 
196  //let derived class do something with the entry
197  afterInsert(entry);
198 }
199 
200 shared_ptr<const Data>
202 {
203  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(name);
204 
205  //if not found, return null
206  if (it == m_cache.get<byFullName>().end()) {
207  return shared_ptr<const Data>();
208  }
209 
210  //if the given name is not the prefix of the lower_bound, return null
211  if (!name.isPrefixOf((*it)->getFullName())) {
212  return shared_ptr<const Data>();
213  }
214 
215  afterAccess(*it);
216  return ((*it)->getData()).shared_from_this();
217 }
218 
219 shared_ptr<const Data>
221 {
222  //if the interest contains implicit digest, it is possible to directly locate a packet.
223  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>()
224  .find(interest.getName());
225 
226  //if a packet is located by its full name, it must be the packet to return.
227  if (it != m_cache.get<byFullName>().end()) {
228  return ((*it)->getData()).shared_from_this();
229  }
230 
231  //if the packet is not discovered by last step, either the packet is not in the storage or
232  //the interest doesn't contains implicit digest.
233  it = m_cache.get<byFullName>().lower_bound(interest.getName());
234 
235  if (it == m_cache.get<byFullName>().end()) {
236  return shared_ptr<const Data>();
237  }
238 
239  //to locate the element that has a just smaller name than the interest's
240  if (it != m_cache.get<byFullName>().begin())
241  it--;
242 
243  InMemoryStorageEntry* ret = selectChild(interest, it);
244  if (ret != 0) {
245  //let derived class do something with the entry
246  afterAccess(ret);
247  return ret->getData().shared_from_this();
248  }
249  else {
250  return shared_ptr<const Data>();
251  }
252 }
253 
254 InMemoryStorage::Cache::index<InMemoryStorage::byFullName>::type::iterator
255 InMemoryStorage::findNextFresh(Cache::index<byFullName>::type::iterator it) const
256 {
257  for (; it != m_cache.get<byFullName>().end(); it++) {
258  if ((*it)->isFresh())
259  return it;
260  }
261 
262  return it;
263 }
264 
266 InMemoryStorage::selectChild(const Interest& interest,
267  Cache::index<byFullName>::type::iterator startingPoint) const
268 {
269  BOOST_ASSERT(startingPoint != m_cache.get<byFullName>().end());
270 
271  if (startingPoint != m_cache.get<byFullName>().begin())
272  {
273  BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
274  }
275 
276  bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
277  bool hasRightmostSelector = !hasLeftmostSelector;
278 
279  // filter out "stale" data
280  if (interest.getMustBeFresh())
281  startingPoint = findNextFresh(startingPoint);
282 
283  if (startingPoint == m_cache.get<byFullName>().end()) {
284  return nullptr;
285  }
286 
287  if (hasLeftmostSelector)
288  {
289  if (interest.matchesData((*startingPoint)->getData()))
290  {
291  return *startingPoint;
292  }
293  }
294 
295  //iterate to the right
296  Cache::index<byFullName>::type::iterator rightmost = startingPoint;
297  if (startingPoint != m_cache.get<byFullName>().end())
298  {
299  Cache::index<byFullName>::type::iterator rightmostCandidate = startingPoint;
300  Name currentChildPrefix("");
301 
302  while (true)
303  {
304  ++rightmostCandidate;
305  // filter out "stale" data
306  if (interest.getMustBeFresh())
307  rightmostCandidate = findNextFresh(rightmostCandidate);
308 
309  bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
310  bool isInPrefix = false;
311  if (isInBoundaries)
312  {
313  isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
314  }
315 
316  if (isInPrefix)
317  {
318  if (interest.matchesData((*rightmostCandidate)->getData()))
319  {
320  if (hasLeftmostSelector)
321  {
322  return *rightmostCandidate;
323  }
324 
325  if (hasRightmostSelector)
326  {
327  // get prefix which is one component longer than Interest name
328  const Name& childPrefix = (*rightmostCandidate)->getFullName()
329  .getPrefix(interest.getName().size() + 1);
330 
331  if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
332  {
333  currentChildPrefix = childPrefix;
334  rightmost = rightmostCandidate;
335  }
336  }
337  }
338  }
339  else
340  break;
341  }
342  }
343 
344  if (rightmost != startingPoint)
345  {
346  return *rightmost;
347  }
348 
349  if (hasRightmostSelector) // if rightmost was not found, try starting point
350  {
351  if (interest.matchesData((*startingPoint)->getData()))
352  {
353  return *startingPoint;
354  }
355  }
356 
357  return 0;
358 }
359 
360 InMemoryStorage::Cache::iterator
361 InMemoryStorage::freeEntry(Cache::iterator it)
362 {
363  //push the *empty* entry into mem pool
364  (*it)->release();
365  m_freeEntries.push(*it);
366  m_nPackets--;
367  return m_cache.erase(it);
368 }
369 
370 void
371 InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
372 {
373  if (isPrefix) {
374  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(prefix);
375 
376  while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
377  //let derived class do something with the entry
378  beforeErase(*it);
379  it = freeEntry(it);
380  }
381  }
382  else {
383  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(prefix);
384 
385  if (it == m_cache.get<byFullName>().end())
386  return;
387 
388  //let derived class do something with the entry
389  beforeErase(*it);
390  freeEntry(it);
391  }
392 
393  if (m_freeEntries.size() > (2 * size()))
394  setCapacity(getCapacity() / 2);
395 }
396 
397 void
399 {
400  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(name);
401 
402  if (it == m_cache.get<byFullName>().end())
403  return;
404 
405  freeEntry(it);
406 }
407 
410 {
411  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().begin();
412 
413  return const_iterator(&((*it)->getData()), &m_cache, it);
414 }
415 
418 {
419  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().end();
420 
421  return const_iterator(nullptr, &m_cache, it);
422 }
423 
424 void
426 {
427 }
428 
429 void
431 {
432 }
433 
434 void
436 {
437 }
438 
439 void
440 InMemoryStorage::printCache(std::ostream& os) const
441 {
442  //start from the upper layer towards bottom
443  const Cache::index<byFullName>::type& cacheIndex = m_cache.get<byFullName>();
444  for (Cache::index<byFullName>::type::iterator it = cacheIndex.begin();
445  it != cacheIndex.end(); it++)
446  os << (*it)->getFullName() << std::endl;
447 }
448 
449 } // namespace ndn
const Name & getName() const
Definition: interest.hpp:139
Copyright (c) 2013-2017 Regents of the University of California.
Definition: common.hpp:66
void erase(const Name &prefix, const bool isPrefix=true)
Deletes in-memory storage entry by prefix by default.
void setCapacity(size_t nMaxPackets)
sets current capacity of in-memory storage (in packets)
virtual bool evictItem()=0
Removes one Data packet from in-memory storage based on derived class implemented replacement policy...
bool isFull() const
returns true if the in-memory storage uses up the current capacity, false otherwise ...
void markStale()
Disable the data from satisfying interest with MustBeFresh.
represents an Interest packet
Definition: interest.hpp:42
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)
size_t getCapacity() const
returns current capacity of in-memory storage (in packets)
int getChildSelector() const
Definition: interest.hpp:304
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...
Represents an error might be thrown during reduce the current capacity of the in-memory storage throu...
shared_ptr< const Data > find(const Interest &interest)
Finds the best match Data for an Interest.
int getMustBeFresh() const
Definition: interest.hpp:318
virtual void afterAccess(InMemoryStorageEntry *entry)
Update the entry when the entry is returned by the find() function according to derived class impleme...
virtual void afterInsert(InMemoryStorageEntry *entry)
Update the entry or other data structures after a entry is successfully inserted according to derived...
Represents a self-defined const_iterator for the in-memory storage.
size_t size() const
Get number of components.
Definition: name.hpp:154
Represents an absolute name.
Definition: name.hpp:42
bool isPrefixOf(const Name &other) const
Check if this name is a prefix of another name.
Definition: name.cpp:260
bool matchesData(const Data &data) const
Check if Interest can be satisfied by data.
Definition: interest.cpp:207
Represents an in-memory storage entry.
InMemoryStorage::const_iterator begin() const
Returns begin iterator of the in-memory storage ordering by name with digest.
const_iterator(const Data *ptr, const Cache *cache, Cache::index< byFullName >::type::iterator it)
const Data & getData() const
Returns the Data packet stored in the in-memory storage entry.
InMemoryStorage::const_iterator end() const
Returns end iterator of the in-memory storage ordering by name with digest.
void printCache(std::ostream &os) const
Prints contents of the in-memory storage.
bool empty() const
Check if name is empty.
Definition: name.hpp:146
void insert(const Data &data, const time::milliseconds &mustBeFreshProcessingWindow=INFINITE_WINDOW)
Inserts a Data packet.
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix of the name.
Definition: name.hpp:210
const Name & getFullName() const
Get full name including implicit digest.
Definition: data.cpp:148
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