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 
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 = 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 
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 = 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  auto 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 = 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  NDN_THROW(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 
250 InMemoryStorage::Cache::index<InMemoryStorage::byFullName>::type::iterator
251 InMemoryStorage::findNextFresh(Cache::index<byFullName>::type::iterator it) const
252 {
253  for (; it != m_cache.get<byFullName>().end(); it++) {
254  if ((*it)->isFresh())
255  return it;
256  }
257 
258  return it;
259 }
260 
262 InMemoryStorage::selectChild(const Interest& interest,
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  // filter out non-fresh data
272  if (interest.getMustBeFresh()) {
273  startingPoint = findNextFresh(startingPoint);
274  }
275 
276  if (startingPoint == m_cache.get<byFullName>().end()) {
277  return nullptr;
278  }
279 
280  if (interest.matchesData((*startingPoint)->getData())) {
281  return *startingPoint;
282  }
283 
284  // iterate to the right
285  auto rightmostCandidate = startingPoint;
286  while (true) {
287  ++rightmostCandidate;
288  // filter out non-fresh data
289  if (interest.getMustBeFresh()) {
290  rightmostCandidate = findNextFresh(rightmostCandidate);
291  }
292 
293  bool isInPrefix = false;
294  if (rightmostCandidate != m_cache.get<byFullName>().end()) {
295  isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
296  }
297  if (isInPrefix) {
298  if (interest.matchesData((*rightmostCandidate)->getData())) {
299  return *rightmostCandidate;
300  }
301  }
302  else {
303  break;
304  }
305  }
306 
307  return nullptr;
308 }
309 
310 InMemoryStorage::Cache::iterator
311 InMemoryStorage::freeEntry(Cache::iterator it)
312 {
313  // push the *empty* entry into mem pool
314  (*it)->release();
315  m_freeEntries.push(*it);
316  m_nPackets--;
317  return m_cache.erase(it);
318 }
319 
320 void
321 InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
322 {
323  if (isPrefix) {
324  auto it = m_cache.get<byFullName>().lower_bound(prefix);
325  while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
326  // let derived class do something with the entry
327  beforeErase(*it);
328  it = freeEntry(it);
329  }
330  }
331  else {
332  auto it = m_cache.get<byFullName>().find(prefix);
333  if (it == m_cache.get<byFullName>().end())
334  return;
335 
336  // let derived class do something with the entry
337  beforeErase(*it);
338  freeEntry(it);
339  }
340 
341  if (m_freeEntries.size() > (2 * size()))
342  setCapacity(getCapacity() / 2);
343 }
344 
345 void
347 {
348  auto it = m_cache.get<byFullName>().find(name);
349  if (it == m_cache.get<byFullName>().end())
350  return;
351 
352  freeEntry(it);
353 }
354 
357 {
358  auto it = m_cache.get<byFullName>().begin();
359  return const_iterator(&((*it)->getData()), &m_cache, it);
360 }
361 
364 {
365  auto it = m_cache.get<byFullName>().end();
366  return const_iterator(nullptr, &m_cache, it);
367 }
368 
369 void
371 {
372 }
373 
374 void
376 {
377 }
378 
379 void
381 {
382 }
383 
384 void
385 InMemoryStorage::printCache(std::ostream& os) const
386 {
387  // start from the upper layer towards bottom
388  for (const auto& elem : m_cache.get<byFullName>())
389  os << elem->getFullName() << std::endl;
390 }
391 
392 } // namespace ndn
bool getMustBeFresh() const noexcept
Check whether the MustBeFresh element is present.
Definition: interest.hpp:228
Definition: data.cpp:26
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...
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:299
Represents an Interest packet.
Definition: interest.hpp:50
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.
#define NDN_THROW(e)
Definition: exception.hpp:61
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.
virtual void afterAccess(InMemoryStorageEntry *entry)
Update the entry when the entry is returned by the find() function according to derived class impleme...
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...
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:333
Represents an absolute name.
Definition: name.hpp:44
Represents an in-memory storage entry.
const Name & getFullName() const
Get full name including implicit digest.
Definition: data.cpp:206
const_iterator(const Data *ptr, const Cache *cache, Cache::index< byFullName >::type::iterator it)
const Name & getName() const noexcept
Definition: interest.hpp:174
bool isFull() const
returns true if the in-memory storage uses up the current capacity, false otherwise ...
void insert(const Data &data, const time::milliseconds &mustBeFreshProcessingWindow=INFINITE_WINDOW)
Inserts a Data packet.
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:39
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)