blob: 3db250d91e89b3b60da86dc6263073ffbe24b1df [file] [log] [blame]
Jiewen Tan99135962014-09-20 02:18:53 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Davide Pesavento10b24be2017-07-12 23:23:46 -04002/*
Davide Pesaventodb4da5e2018-06-15 11:37:52 -04003 * Copyright (c) 2013-2018 Regents of the University of California.
Jiewen Tan99135962014-09-20 02:18:53 -07004 *
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"
23#include "in-memory-storage-entry.hpp"
24
Jiewen Tan99135962014-09-20 02:18:53 -070025namespace ndn {
Jiewen Tan99135962014-09-20 02:18:53 -070026
Yingdi Yu404eafd2016-03-06 14:54:25 -080027const time::milliseconds InMemoryStorage::INFINITE_WINDOW(-1);
28const time::milliseconds InMemoryStorage::ZERO_WINDOW(0);
29
Jiewen Tan99135962014-09-20 02:18:53 -070030InMemoryStorage::const_iterator::const_iterator(const Data* ptr, const Cache* cache,
31 Cache::index<byFullName>::type::iterator it)
32 : m_ptr(ptr)
33 , m_cache(cache)
34 , m_it(it)
35{
36}
37
38InMemoryStorage::const_iterator&
39InMemoryStorage::const_iterator::operator++()
40{
41 m_it++;
42 if (m_it != m_cache->get<byFullName>().end()) {
43 m_ptr = &((*m_it)->getData());
44 }
45 else {
Davide Pesaventodb4da5e2018-06-15 11:37:52 -040046 m_ptr = nullptr;
Jiewen Tan99135962014-09-20 02:18:53 -070047 }
48
49 return *this;
50}
51
52InMemoryStorage::const_iterator
53InMemoryStorage::const_iterator::operator++(int)
54{
55 InMemoryStorage::const_iterator i(*this);
56 this->operator++();
57 return i;
58}
59
Davide Pesaventodb4da5e2018-06-15 11:37:52 -040060InMemoryStorage::const_iterator::reference
Jiewen Tan99135962014-09-20 02:18:53 -070061InMemoryStorage::const_iterator::operator*()
62{
63 return *m_ptr;
64}
65
Davide Pesaventodb4da5e2018-06-15 11:37:52 -040066InMemoryStorage::const_iterator::pointer
Jiewen Tan99135962014-09-20 02:18:53 -070067InMemoryStorage::const_iterator::operator->()
68{
69 return m_ptr;
70}
71
72bool
73InMemoryStorage::const_iterator::operator==(const const_iterator& rhs)
74{
75 return m_it == rhs.m_it;
76}
77
78bool
79InMemoryStorage::const_iterator::operator!=(const const_iterator& rhs)
80{
81 return m_it != rhs.m_it;
82}
83
84InMemoryStorage::InMemoryStorage(size_t limit)
85 : m_limit(limit)
86 , m_nPackets(0)
87{
Yingdi Yu404eafd2016-03-06 14:54:25 -080088 init();
89}
90
91InMemoryStorage::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
99void
100InMemoryStorage::init()
101{
Jiewen Tan99135962014-09-20 02:18:53 -0700102 // TODO consider a more suitable initial value
103 m_capacity = 10;
104
Yingdi Yu404eafd2016-03-06 14:54:25 -0800105 if (m_limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
Jiewen Tan99135962014-09-20 02:18:53 -0700106 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
114InMemoryStorage::~InMemoryStorage()
115{
116 // evict all items from cache
117 Cache::iterator it = m_cache.begin();
118 while (it != m_cache.end()) {
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800119 it = freeEntry(it);
Jiewen Tan99135962014-09-20 02:18:53 -0700120 }
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
130void
131InMemoryStorage::setCapacity(size_t capacity)
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) {
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700140 BOOST_THROW_EXCEPTION(Error());
Jiewen Tan99135962014-09-20 02:18:53 -0700141 }
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
160void
Yingdi Yu404eafd2016-03-06 14:54:25 -0800161InMemoryStorage::insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow)
Jiewen Tan99135962014-09-20 02:18:53 -0700162{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400163 // check if identical Data/Name already exists
164 auto it = m_cache.get<byFullName>().find(data.getFullName());
Jiewen Tan99135962014-09-20 02:18:53 -0700165 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);
Yingdi Yu404eafd2016-03-06 14:54:25 -0800188 if (m_scheduler != nullptr && mustBeFreshProcessingWindow > ZERO_WINDOW) {
Junxiao Shic542f632017-07-18 14:20:32 +0000189 auto eventId = make_unique<util::scheduler::ScopedEventId>(*m_scheduler);
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400190 *eventId = m_scheduler->scheduleEvent(mustBeFreshProcessingWindow, [entry] { entry->markStale(); });
Yingdi Yu404eafd2016-03-06 14:54:25 -0800191 entry->setMarkStaleEventId(std::move(eventId));
192 }
Jiewen Tan99135962014-09-20 02:18:53 -0700193 m_cache.insert(entry);
194
195 //let derived class do something with the entry
196 afterInsert(entry);
197}
198
199shared_ptr<const Data>
200InMemoryStorage::find(const Name& name)
201{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400202 auto it = m_cache.get<byFullName>().lower_bound(name);
Jiewen Tan99135962014-09-20 02:18:53 -0700203
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400204 // if not found, return null
Jiewen Tan99135962014-09-20 02:18:53 -0700205 if (it == m_cache.get<byFullName>().end()) {
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400206 return nullptr;
Jiewen Tan99135962014-09-20 02:18:53 -0700207 }
208
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400209 // if the given name is not the prefix of the lower_bound, return null
Jiewen Tan99135962014-09-20 02:18:53 -0700210 if (!name.isPrefixOf((*it)->getFullName())) {
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400211 return nullptr;
Jiewen Tan99135962014-09-20 02:18:53 -0700212 }
213
214 afterAccess(*it);
215 return ((*it)->getData()).shared_from_this();
216}
217
218shared_ptr<const Data>
219InMemoryStorage::find(const Interest& interest)
220{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400221 // if the interest contains implicit digest, it is possible to directly locate a packet.
222 auto it = m_cache.get<byFullName>().find(interest.getName());
Jiewen Tan99135962014-09-20 02:18:53 -0700223
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400224 // if a packet is located by its full name, it must be the packet to return.
Jiewen Tan99135962014-09-20 02:18:53 -0700225 if (it != m_cache.get<byFullName>().end()) {
226 return ((*it)->getData()).shared_from_this();
227 }
228
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400229 // if the packet is not discovered by last step, either the packet is not in the storage or
230 // the interest doesn't contains implicit digest.
Jiewen Tan99135962014-09-20 02:18:53 -0700231 it = m_cache.get<byFullName>().lower_bound(interest.getName());
232
233 if (it == m_cache.get<byFullName>().end()) {
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400234 return nullptr;
Jiewen Tan99135962014-09-20 02:18:53 -0700235 }
236
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400237 // to locate the element that has a just smaller name than the interest's
238 if (it != m_cache.get<byFullName>().begin()) {
Jiewen Tan99135962014-09-20 02:18:53 -0700239 it--;
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400240 }
Jiewen Tan99135962014-09-20 02:18:53 -0700241
242 InMemoryStorageEntry* ret = selectChild(interest, it);
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400243 if (ret == nullptr) {
244 return nullptr;
Jiewen Tan99135962014-09-20 02:18:53 -0700245 }
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400246
247 // let derived class do something with the entry
248 afterAccess(ret);
249 return ret->getData().shared_from_this();
Jiewen Tan99135962014-09-20 02:18:53 -0700250}
251
Yingdi Yu404eafd2016-03-06 14:54:25 -0800252InMemoryStorage::Cache::index<InMemoryStorage::byFullName>::type::iterator
253InMemoryStorage::findNextFresh(Cache::index<byFullName>::type::iterator it) const
254{
255 for (; it != m_cache.get<byFullName>().end(); it++) {
256 if ((*it)->isFresh())
257 return it;
258 }
259
260 return it;
261}
262
Jiewen Tan99135962014-09-20 02:18:53 -0700263InMemoryStorageEntry*
264InMemoryStorage::selectChild(const Interest& interest,
265 Cache::index<byFullName>::type::iterator startingPoint) const
266{
267 BOOST_ASSERT(startingPoint != m_cache.get<byFullName>().end());
268
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400269 if (startingPoint != m_cache.get<byFullName>().begin()) {
270 BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
271 }
Jiewen Tan99135962014-09-20 02:18:53 -0700272
273 bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
274 bool hasRightmostSelector = !hasLeftmostSelector;
275
Yingdi Yu404eafd2016-03-06 14:54:25 -0800276 // filter out "stale" data
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400277 if (interest.getMustBeFresh()) {
Yingdi Yu404eafd2016-03-06 14:54:25 -0800278 startingPoint = findNextFresh(startingPoint);
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400279 }
Yingdi Yu404eafd2016-03-06 14:54:25 -0800280
281 if (startingPoint == m_cache.get<byFullName>().end()) {
282 return nullptr;
283 }
284
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400285 if (hasLeftmostSelector) {
286 if (interest.matchesData((*startingPoint)->getData())) {
287 return *startingPoint;
Jiewen Tan99135962014-09-20 02:18:53 -0700288 }
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400289 }
Jiewen Tan99135962014-09-20 02:18:53 -0700290
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400291 // iterate to the right
292 auto rightmost = startingPoint;
293 if (startingPoint != m_cache.get<byFullName>().end()) {
294 auto rightmostCandidate = startingPoint;
295 Name currentChildPrefix("");
Jiewen Tan99135962014-09-20 02:18:53 -0700296
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400297 while (true) {
298 ++rightmostCandidate;
299 // filter out "stale" data
300 if (interest.getMustBeFresh()) {
301 rightmostCandidate = findNextFresh(rightmostCandidate);
302 }
Jiewen Tan99135962014-09-20 02:18:53 -0700303
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400304 bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
305 bool isInPrefix = false;
306 if (isInBoundaries) {
307 isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
308 }
309
310 if (isInPrefix) {
311 if (interest.matchesData((*rightmostCandidate)->getData())) {
312 if (hasLeftmostSelector) {
313 return *rightmostCandidate;
314 }
315
316 if (hasRightmostSelector) {
317 // get prefix which is one component longer than Interest name
318 const Name& childPrefix = (*rightmostCandidate)->getFullName().getPrefix(interest.getName().size() + 1);
319 if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix)) {
320 currentChildPrefix = childPrefix;
321 rightmost = rightmostCandidate;
Jiewen Tan99135962014-09-20 02:18:53 -0700322 }
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400323 }
Jiewen Tan99135962014-09-20 02:18:53 -0700324 }
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400325 }
326 else {
327 break;
328 }
Jiewen Tan99135962014-09-20 02:18:53 -0700329 }
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400330 }
Jiewen Tan99135962014-09-20 02:18:53 -0700331
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400332 if (rightmost != startingPoint) {
333 return *rightmost;
334 }
335
336 if (hasRightmostSelector) { // if rightmost was not found, try starting point
337 if (interest.matchesData((*startingPoint)->getData())) {
338 return *startingPoint;
Jiewen Tan99135962014-09-20 02:18:53 -0700339 }
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400340 }
Jiewen Tan99135962014-09-20 02:18:53 -0700341
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400342 return nullptr;
Jiewen Tan99135962014-09-20 02:18:53 -0700343}
344
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800345InMemoryStorage::Cache::iterator
346InMemoryStorage::freeEntry(Cache::iterator it)
347{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400348 // push the *empty* entry into mem pool
Jiewen Tan99135962014-09-20 02:18:53 -0700349 (*it)->release();
350 m_freeEntries.push(*it);
351 m_nPackets--;
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800352 return m_cache.erase(it);
Jiewen Tan99135962014-09-20 02:18:53 -0700353}
354
355void
356InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
357{
358 if (isPrefix) {
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400359 auto it = m_cache.get<byFullName>().lower_bound(prefix);
Jiewen Tan99135962014-09-20 02:18:53 -0700360 while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400361 // let derived class do something with the entry
Jiewen Tan99135962014-09-20 02:18:53 -0700362 beforeErase(*it);
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800363 it = freeEntry(it);
Jiewen Tan99135962014-09-20 02:18:53 -0700364 }
365 }
366 else {
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400367 auto it = m_cache.get<byFullName>().find(prefix);
Jiewen Tan99135962014-09-20 02:18:53 -0700368 if (it == m_cache.get<byFullName>().end())
369 return;
370
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400371 // let derived class do something with the entry
Jiewen Tan99135962014-09-20 02:18:53 -0700372 beforeErase(*it);
373 freeEntry(it);
374 }
375
376 if (m_freeEntries.size() > (2 * size()))
377 setCapacity(getCapacity() / 2);
378}
379
380void
381InMemoryStorage::eraseImpl(const Name& name)
382{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400383 auto it = m_cache.get<byFullName>().find(name);
Jiewen Tan99135962014-09-20 02:18:53 -0700384 if (it == m_cache.get<byFullName>().end())
385 return;
386
387 freeEntry(it);
388}
389
390InMemoryStorage::const_iterator
391InMemoryStorage::begin() const
392{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400393 auto it = m_cache.get<byFullName>().begin();
Jiewen Tan99135962014-09-20 02:18:53 -0700394 return const_iterator(&((*it)->getData()), &m_cache, it);
395}
396
397InMemoryStorage::const_iterator
398InMemoryStorage::end() const
399{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400400 auto it = m_cache.get<byFullName>().end();
Davide Pesavento10b24be2017-07-12 23:23:46 -0400401 return const_iterator(nullptr, &m_cache, it);
Jiewen Tan99135962014-09-20 02:18:53 -0700402}
403
404void
405InMemoryStorage::afterInsert(InMemoryStorageEntry* entry)
406{
407}
408
409void
410InMemoryStorage::beforeErase(InMemoryStorageEntry* entry)
411{
412}
413
414void
415InMemoryStorage::afterAccess(InMemoryStorageEntry* entry)
416{
417}
418
419void
420InMemoryStorage::printCache(std::ostream& os) const
421{
Davide Pesaventodb4da5e2018-06-15 11:37:52 -0400422 // start from the upper layer towards bottom
423 for (const auto& elem : m_cache.get<byFullName>())
424 os << elem->getFullName() << std::endl;
Jiewen Tan99135962014-09-20 02:18:53 -0700425}
426
Jiewen Tan99135962014-09-20 02:18:53 -0700427} // namespace ndn