NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: 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; -*- */
22 #include "in-memory-storage.hpp"
24 #include "util/backports.hpp"
25 
26 #include "crypto.hpp"
27 
28 #include "../security/signature-sha256-with-rsa.hpp"
29 
30 namespace ndn {
31 namespace util {
32 
33 const time::milliseconds InMemoryStorage::INFINITE_WINDOW(-1);
34 const time::milliseconds InMemoryStorage::ZERO_WINDOW(0);
35 
38  : m_ptr(ptr)
39  , m_cache(cache)
40  , m_it(it)
41 {
42 }
43 
46 {
47  m_it++;
48  if (m_it != m_cache->get<byFullName>().end()) {
49  m_ptr = &((*m_it)->getData());
50  }
51  else {
52  m_ptr = 0;
53  }
54 
55  return *this;
56 }
57 
60 {
62  this->operator++();
63  return i;
64 }
65 
66 const Data&
68 {
69  return *m_ptr;
70 }
71 
72 const Data*
74 {
75  return m_ptr;
76 }
77 
78 bool
80 {
81  return m_it == rhs.m_it;
82 }
83 
84 bool
86 {
87  return m_it != rhs.m_it;
88 }
89 
91  : m_limit(limit)
92  , m_nPackets(0)
93 {
94  init();
95 }
96 
97 InMemoryStorage::InMemoryStorage(boost::asio::io_service& ioService, size_t limit)
98  : m_limit(limit)
99  , m_nPackets(0)
100 {
101  m_scheduler = make_unique<Scheduler>(ioService);
102  init();
103 }
104 
105 void
106 InMemoryStorage::init()
107 {
108  // TODO consider a more suitable initial value
109  m_capacity = 10;
110 
111  if (m_limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
112  m_capacity = m_limit;
113  }
114 
115  for (size_t i = 0; i < m_capacity; i++) {
116  m_freeEntries.push(new InMemoryStorageEntry());
117  }
118 }
119 
121 {
122  // evict all items from cache
123  Cache::iterator it = m_cache.begin();
124  while (it != m_cache.end()) {
125  it = freeEntry(it);
126  }
127 
128  BOOST_ASSERT(m_freeEntries.size() == m_capacity);
129 
130  while (!m_freeEntries.empty()) {
131  delete m_freeEntries.top();
132  m_freeEntries.pop();
133  }
134 }
135 
136 void
137 InMemoryStorage::setCapacity(size_t capacity)
138 {
139  size_t oldCapacity = m_capacity;
140  m_capacity = capacity;
141 
142  if (size() > m_capacity) {
143  ssize_t nAllowedFailures = size() - m_capacity;
144  while (size() > m_capacity) {
145  if (!evictItem() && --nAllowedFailures < 0) {
146  BOOST_THROW_EXCEPTION(Error());
147  }
148  }
149  }
150 
151  if (m_capacity >= oldCapacity) {
152  for (size_t i = oldCapacity; i < m_capacity; i++) {
153  m_freeEntries.push(new InMemoryStorageEntry());
154  }
155  }
156  else {
157  for (size_t i = oldCapacity; i > m_capacity; i--) {
158  delete m_freeEntries.top();
159  m_freeEntries.pop();
160  }
161  }
162 
163  BOOST_ASSERT(size() + m_freeEntries.size() == m_capacity);
164 }
165 
166 void
167 InMemoryStorage::insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow)
168 {
169  //check if identical Data/Name already exists
170  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(data.getFullName());
171  if (it != m_cache.get<byFullName>().end())
172  return;
173 
174  //if full, double the capacity
175  bool doesReachLimit = (getLimit() == getCapacity());
176  if (isFull() && !doesReachLimit) {
177  // note: This is incorrect if 2*capacity overflows, but memory should run out before that
178  size_t newCapacity = std::min(2 * getCapacity(), getLimit());
179  setCapacity(newCapacity);
180  }
181 
182  //if full and reach limitation of the capacity, employ replacement policy
183  if (isFull() && doesReachLimit) {
184  evictItem();
185  }
186 
187  //insert to cache
188  BOOST_ASSERT(m_freeEntries.size() > 0);
189  // take entry for the memory pool
190  InMemoryStorageEntry* entry = m_freeEntries.top();
191  m_freeEntries.pop();
192  m_nPackets++;
193  entry->setData(data);
194  if (m_scheduler != nullptr && mustBeFreshProcessingWindow > ZERO_WINDOW) {
195  auto eventId = make_unique<scheduler::ScopedEventId>(*m_scheduler);
196  *eventId = m_scheduler->scheduleEvent(mustBeFreshProcessingWindow,
197  bind(&InMemoryStorageEntry::markStale, entry));
198  entry->setMarkStaleEventId(std::move(eventId));
199  }
200  m_cache.insert(entry);
201 
202  //let derived class do something with the entry
203  afterInsert(entry);
204 }
205 
206 shared_ptr<const Data>
208 {
209  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(name);
210 
211  //if not found, return null
212  if (it == m_cache.get<byFullName>().end()) {
213  return shared_ptr<const Data>();
214  }
215 
216  //if the given name is not the prefix of the lower_bound, return null
217  if (!name.isPrefixOf((*it)->getFullName())) {
218  return shared_ptr<const Data>();
219  }
220 
221  afterAccess(*it);
222  return ((*it)->getData()).shared_from_this();
223 }
224 
225 shared_ptr<const Data>
227 {
228  //if the interest contains implicit digest, it is possible to directly locate a packet.
229  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>()
230  .find(interest.getName());
231 
232  //if a packet is located by its full name, it must be the packet to return.
233  if (it != m_cache.get<byFullName>().end()) {
234  return ((*it)->getData()).shared_from_this();
235  }
236 
237  //if the packet is not discovered by last step, either the packet is not in the storage or
238  //the interest doesn't contains implicit digest.
239  it = m_cache.get<byFullName>().lower_bound(interest.getName());
240 
241  if (it == m_cache.get<byFullName>().end()) {
242  return shared_ptr<const Data>();
243  }
244 
245  //to locate the element that has a just smaller name than the interest's
246  if (it != m_cache.get<byFullName>().begin())
247  it--;
248 
249  InMemoryStorageEntry* ret = selectChild(interest, it);
250  if (ret != 0) {
251  //let derived class do something with the entry
252  afterAccess(ret);
253  return ret->getData().shared_from_this();
254  }
255  else {
256  return shared_ptr<const Data>();
257  }
258 }
259 
262 {
263  for (; it != m_cache.get<byFullName>().end(); it++) {
264  if ((*it)->isFresh())
265  return it;
266  }
267 
268  return it;
269 }
270 
273  Cache::index<byFullName>::type::iterator startingPoint) const
274 {
275  BOOST_ASSERT(startingPoint != m_cache.get<byFullName>().end());
276 
277  if (startingPoint != m_cache.get<byFullName>().begin())
278  {
279  BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
280  }
281 
282  bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
283  bool hasRightmostSelector = !hasLeftmostSelector;
284 
285  // filter out "stale" data
286  if (interest.getMustBeFresh())
287  startingPoint = findNextFresh(startingPoint);
288 
289  if (startingPoint == m_cache.get<byFullName>().end()) {
290  return nullptr;
291  }
292 
293  if (hasLeftmostSelector)
294  {
295  if (interest.matchesData((*startingPoint)->getData()))
296  {
297  return *startingPoint;
298  }
299  }
300 
301  //iterate to the right
302  Cache::index<byFullName>::type::iterator rightmost = startingPoint;
303  if (startingPoint != m_cache.get<byFullName>().end())
304  {
305  Cache::index<byFullName>::type::iterator rightmostCandidate = startingPoint;
306  Name currentChildPrefix("");
307 
308  while (true)
309  {
310  ++rightmostCandidate;
311  // filter out "stale" data
312  if (interest.getMustBeFresh())
313  rightmostCandidate = findNextFresh(rightmostCandidate);
314 
315  bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
316  bool isInPrefix = false;
317  if (isInBoundaries)
318  {
319  isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
320  }
321 
322  if (isInPrefix)
323  {
324  if (interest.matchesData((*rightmostCandidate)->getData()))
325  {
326  if (hasLeftmostSelector)
327  {
328  return *rightmostCandidate;
329  }
330 
331  if (hasRightmostSelector)
332  {
333  // get prefix which is one component longer than Interest name
334  const Name& childPrefix = (*rightmostCandidate)->getFullName()
335  .getPrefix(interest.getName().size() + 1);
336 
337  if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
338  {
339  currentChildPrefix = childPrefix;
340  rightmost = rightmostCandidate;
341  }
342  }
343  }
344  }
345  else
346  break;
347  }
348  }
349 
350  if (rightmost != startingPoint)
351  {
352  return *rightmost;
353  }
354 
355  if (hasRightmostSelector) // if rightmost was not found, try starting point
356  {
357  if (interest.matchesData((*startingPoint)->getData()))
358  {
359  return *startingPoint;
360  }
361  }
362 
363  return 0;
364 }
365 
367 InMemoryStorage::freeEntry(Cache::iterator it)
368 {
369  //push the *empty* entry into mem pool
370  (*it)->release();
371  m_freeEntries.push(*it);
372  m_nPackets--;
373  return m_cache.erase(it);
374 }
375 
376 void
377 InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
378 {
379  if (isPrefix) {
380  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(prefix);
381 
382  while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
383  //let derived class do something with the entry
384  beforeErase(*it);
385  it = freeEntry(it);
386  }
387  }
388  else {
389  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(prefix);
390 
391  if (it == m_cache.get<byFullName>().end())
392  return;
393 
394  //let derived class do something with the entry
395  beforeErase(*it);
396  freeEntry(it);
397  }
398 
399  if (m_freeEntries.size() > (2 * size()))
400  setCapacity(getCapacity() / 2);
401 }
402 
403 void
405 {
406  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(name);
407 
408  if (it == m_cache.get<byFullName>().end())
409  return;
410 
411  freeEntry(it);
412 }
413 
416 {
417  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().begin();
418 
419  return const_iterator(&((*it)->getData()), &m_cache, it);
420 }
421 
424 {
425  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().end();
426 
427  const Data* ptr = NULL;
428 
429  return const_iterator(ptr, &m_cache, it);
430 }
431 
432 void
434 {
435 }
436 
437 void
439 {
440 }
441 
442 void
443 InMemoryStorage::afterAccess(InMemoryStorageEntry* entry)
444 {
445 }
446 
447 void
448 InMemoryStorage::printCache(std::ostream& os) const
449 {
450  //start from the upper layer towards bottom
451  const Cache::index<byFullName>::type& cacheIndex = m_cache.get<byFullName>();
452  for (Cache::index<byFullName>::type::iterator it = cacheIndex.begin();
453  it != cacheIndex.end(); it++)
454  os << (*it)->getFullName() << std::endl;
455 }
456 
457 } // namespace util
458 } // namespace ndn
const Data & getData() const
Returns the Data packet stored in the in-memory storage entry.
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix (PartialName) of the name, containing first nComponents components.
Definition: name.hpp:249
bool isFull() const
returns true if the in-memory storage uses up the current capacity, false otherwise ...
Copyright (c) 2011-2015 Regents of the University of California.
int getChildSelector() const
Definition: interest.hpp:398
int getMustBeFresh() const
Definition: interest.hpp:412
void markStale()
Disable the data from satisfying interest with MustBeFresh.
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.
Represents a self-defined const_iterator for the in-memory storage.
represents an Interest packet
Definition: interest.hpp:45
bool operator!=(const const_iterator &rhs)
virtual bool evictItem()=0
Removes one Data packet from in-memory storage based on derived class implemented replacement policy...
virtual void beforeErase(InMemoryStorageEntry *entry)
Update the entry or other data structures before a entry is successfully erased according to derived ...
void eraseImpl(const Name &name)
deletes in-memory storage entries by the Name with implicit digest.
Table::const_iterator iterator
Definition: cs-internal.hpp:41
InMemoryStorage::const_iterator begin() const
Returns begin iterator of the in-memory storage ordering by name with digest.
InMemoryStorage::const_iterator end() const
Returns end iterator of the in-memory storage ordering by name with digest.
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
size_t getCapacity() const
returns current capacity of in-memory storage (in packets)
Cache::index< byFullName >::type::iterator findNextFresh(Cache::index< byFullName >::type::iterator startingPoint) const
Get the next iterator (include startingPoint) that satisfies MustBeFresh requirement.
bool matchesData(const Data &data) const
Check if Interest can be satisfied by data.
Definition: interest.cpp:132
Represents an in-memory storage entry.
Name abstraction to represent an absolute name.
Definition: name.hpp:46
bool isPrefixOf(const Name &name) const
Check if the N components of this name are the same as the first N components of the given name...
Definition: name.cpp:320
const_iterator(const Data *ptr, const Cache *cache, Cache::index< byFullName >::type::iterator it)
const Name & getFullName() const
Get full name of Data packet, including the implicit digest.
Definition: data.cpp:179
size_t size() const
Get the number of components.
Definition: name.hpp:408
void printCache(std::ostream &os) const
Prints contents of the in-memory storage.
bool operator==(const const_iterator &rhs)
virtual void afterInsert(InMemoryStorageEntry *entry)
Update the entry or other data structures after a entry is successfully inserted according to derived...
void insert(const Data &data, const time::milliseconds &mustBeFreshProcessingWindow=INFINITE_WINDOW)
Inserts a Data packet.
bool empty() const
Check if name is emtpy.
Definition: name.hpp:398
static const time::milliseconds INFINITE_WINDOW
InMemoryStorageEntry * selectChild(const Interest &interest, Cache::index< byFullName >::type::iterator startingPoint) const
Implements child selector (leftmost, rightmost, undeclared).
Represents an error might be thrown during reduce the current capacity of the in-memory storage throu...
represents a Data packet
Definition: data.hpp:39
const Name & getName() const
Definition: interest.hpp:218
void erase(const Name &prefix, const bool isPrefix=true)
Deletes in-memory storage entry by prefix by default.