blob: 4a196609af838874d487f686b0d492d50795c4e2 [file] [log] [blame]
Jiewen Tan99135962014-09-20 02:18:53 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev73e30042015-09-17 17:09:51 -07003 * Copyright (c) 2013-2015 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
25#include "crypto.hpp"
26
27#include "../security/signature-sha256-with-rsa.hpp"
28
29namespace ndn {
30namespace util {
31
32InMemoryStorage::const_iterator::const_iterator(const Data* ptr, const Cache* cache,
33 Cache::index<byFullName>::type::iterator it)
34 : m_ptr(ptr)
35 , m_cache(cache)
36 , m_it(it)
37{
38}
39
40InMemoryStorage::const_iterator&
41InMemoryStorage::const_iterator::operator++()
42{
43 m_it++;
44 if (m_it != m_cache->get<byFullName>().end()) {
45 m_ptr = &((*m_it)->getData());
46 }
47 else {
48 m_ptr = 0;
49 }
50
51 return *this;
52}
53
54InMemoryStorage::const_iterator
55InMemoryStorage::const_iterator::operator++(int)
56{
57 InMemoryStorage::const_iterator i(*this);
58 this->operator++();
59 return i;
60}
61
62const Data&
63InMemoryStorage::const_iterator::operator*()
64{
65 return *m_ptr;
66}
67
68const Data*
69InMemoryStorage::const_iterator::operator->()
70{
71 return m_ptr;
72}
73
74bool
75InMemoryStorage::const_iterator::operator==(const const_iterator& rhs)
76{
77 return m_it == rhs.m_it;
78}
79
80bool
81InMemoryStorage::const_iterator::operator!=(const const_iterator& rhs)
82{
83 return m_it != rhs.m_it;
84}
85
86InMemoryStorage::InMemoryStorage(size_t limit)
87 : m_limit(limit)
88 , m_nPackets(0)
89{
90 // TODO consider a more suitable initial value
91 m_capacity = 10;
92
93 if (limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
94 m_capacity = m_limit;
95 }
96
97 for (size_t i = 0; i < m_capacity; i++) {
98 m_freeEntries.push(new InMemoryStorageEntry());
99 }
100}
101
102InMemoryStorage::~InMemoryStorage()
103{
104 // evict all items from cache
105 Cache::iterator it = m_cache.begin();
106 while (it != m_cache.end()) {
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800107 it = freeEntry(it);
Jiewen Tan99135962014-09-20 02:18:53 -0700108 }
109
110 BOOST_ASSERT(m_freeEntries.size() == m_capacity);
111
112 while (!m_freeEntries.empty()) {
113 delete m_freeEntries.top();
114 m_freeEntries.pop();
115 }
116}
117
118void
119InMemoryStorage::setCapacity(size_t capacity)
120{
121 size_t oldCapacity = m_capacity;
122 m_capacity = capacity;
123
124 if (size() > m_capacity) {
125 ssize_t nAllowedFailures = size() - m_capacity;
126 while (size() > m_capacity) {
127 if (!evictItem() && --nAllowedFailures < 0) {
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700128 BOOST_THROW_EXCEPTION(Error());
Jiewen Tan99135962014-09-20 02:18:53 -0700129 }
130 }
131 }
132
133 if (m_capacity >= oldCapacity) {
134 for (size_t i = oldCapacity; i < m_capacity; i++) {
135 m_freeEntries.push(new InMemoryStorageEntry());
136 }
137 }
138 else {
139 for (size_t i = oldCapacity; i > m_capacity; i--) {
140 delete m_freeEntries.top();
141 m_freeEntries.pop();
142 }
143 }
144
145 BOOST_ASSERT(size() + m_freeEntries.size() == m_capacity);
146}
147
148void
149InMemoryStorage::insert(const Data& data)
150{
151 //check if identical Data/Name already exists
152 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(data.getFullName());
153 if (it != m_cache.get<byFullName>().end())
154 return;
155
156 //if full, double the capacity
157 bool doesReachLimit = (getLimit() == getCapacity());
158 if (isFull() && !doesReachLimit) {
159 // note: This is incorrect if 2*capacity overflows, but memory should run out before that
160 size_t newCapacity = std::min(2 * getCapacity(), getLimit());
161 setCapacity(newCapacity);
162 }
163
164 //if full and reach limitation of the capacity, employ replacement policy
165 if (isFull() && doesReachLimit) {
166 evictItem();
167 }
168
169 //insert to cache
170 BOOST_ASSERT(m_freeEntries.size() > 0);
171 // take entry for the memory pool
172 InMemoryStorageEntry* entry = m_freeEntries.top();
173 m_freeEntries.pop();
174 m_nPackets++;
175 entry->setData(data);
176 m_cache.insert(entry);
177
178 //let derived class do something with the entry
179 afterInsert(entry);
180}
181
182shared_ptr<const Data>
183InMemoryStorage::find(const Name& name)
184{
185 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(name);
186
187 //if not found, return null
188 if (it == m_cache.get<byFullName>().end()) {
189 return shared_ptr<const Data>();
190 }
191
192 //if the given name is not the prefix of the lower_bound, return null
193 if (!name.isPrefixOf((*it)->getFullName())) {
194 return shared_ptr<const Data>();
195 }
196
197 afterAccess(*it);
198 return ((*it)->getData()).shared_from_this();
199}
200
201shared_ptr<const Data>
202InMemoryStorage::find(const Interest& interest)
203{
204 //if the interest contains implicit digest, it is possible to directly locate a packet.
205 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>()
206 .find(interest.getName());
207
208 //if a packet is located by its full name, it must be the packet to return.
209 if (it != m_cache.get<byFullName>().end()) {
210 return ((*it)->getData()).shared_from_this();
211 }
212
213 //if the packet is not discovered by last step, either the packet is not in the storage or
214 //the interest doesn't contains implicit digest.
215 it = m_cache.get<byFullName>().lower_bound(interest.getName());
216
217 if (it == m_cache.get<byFullName>().end()) {
218 return shared_ptr<const Data>();
219 }
220
221
222 //to locate the element that has a just smaller name than the interest's
223 if (it != m_cache.get<byFullName>().begin())
224 it--;
225
226 InMemoryStorageEntry* ret = selectChild(interest, it);
227 if (ret != 0) {
228 //let derived class do something with the entry
229 afterAccess(ret);
230 return ret->getData().shared_from_this();
231 }
232 else {
233 return shared_ptr<const Data>();
234 }
235}
236
237InMemoryStorageEntry*
238InMemoryStorage::selectChild(const Interest& interest,
239 Cache::index<byFullName>::type::iterator startingPoint) const
240{
241 BOOST_ASSERT(startingPoint != m_cache.get<byFullName>().end());
242
243 if (startingPoint != m_cache.get<byFullName>().begin())
244 {
245 BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
246 }
247
248 bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
249 bool hasRightmostSelector = !hasLeftmostSelector;
250
251 if (hasLeftmostSelector)
252 {
253 if (interest.matchesData((*startingPoint)->getData()))
254 {
255 return *startingPoint;
256 }
257 }
258
259 //iterate to the right
260 Cache::index<byFullName>::type::iterator rightmost = startingPoint;
261 if (startingPoint != m_cache.get<byFullName>().end())
262 {
263 Cache::index<byFullName>::type::iterator rightmostCandidate = startingPoint;
264 Name currentChildPrefix("");
265
266 while (true)
267 {
268 ++rightmostCandidate;
269
270 bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
271 bool isInPrefix = false;
272 if (isInBoundaries)
273 {
274 isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
275 }
276
277 if (isInPrefix)
278 {
279 if (interest.matchesData((*rightmostCandidate)->getData()))
280 {
281 if (hasLeftmostSelector)
282 {
283 return *rightmostCandidate;
284 }
285
286 if (hasRightmostSelector)
287 {
288 // get prefix which is one component longer than Interest name
289 const Name& childPrefix = (*rightmostCandidate)->getFullName()
290 .getPrefix(interest.getName().size() + 1);
291
292 if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
293 {
294 currentChildPrefix = childPrefix;
295 rightmost = rightmostCandidate;
296 }
297 }
298 }
299 }
300 else
301 break;
302 }
303 }
304
305 if (rightmost != startingPoint)
306 {
307 return *rightmost;
308 }
309
310 if (hasRightmostSelector) // if rightmost was not found, try starting point
311 {
312 if (interest.matchesData((*startingPoint)->getData()))
313 {
314 return *startingPoint;
315 }
316 }
317
318 return 0;
319}
320
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800321InMemoryStorage::Cache::iterator
322InMemoryStorage::freeEntry(Cache::iterator it)
323{
Jiewen Tan99135962014-09-20 02:18:53 -0700324 //push the *empty* entry into mem pool
325 (*it)->release();
326 m_freeEntries.push(*it);
327 m_nPackets--;
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800328 return m_cache.erase(it);
Jiewen Tan99135962014-09-20 02:18:53 -0700329}
330
331void
332InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
333{
334 if (isPrefix) {
335 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(prefix);
336
Jiewen Tan99135962014-09-20 02:18:53 -0700337 while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
338 //let derived class do something with the entry
339 beforeErase(*it);
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800340 it = freeEntry(it);
Jiewen Tan99135962014-09-20 02:18:53 -0700341 }
342 }
343 else {
344 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(prefix);
345
346 if (it == m_cache.get<byFullName>().end())
347 return;
348
349 //let derived class do something with the entry
350 beforeErase(*it);
351 freeEntry(it);
352 }
353
354 if (m_freeEntries.size() > (2 * size()))
355 setCapacity(getCapacity() / 2);
356}
357
358void
359InMemoryStorage::eraseImpl(const Name& name)
360{
361 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(name);
362
363 if (it == m_cache.get<byFullName>().end())
364 return;
365
366 freeEntry(it);
367}
368
369InMemoryStorage::const_iterator
370InMemoryStorage::begin() const
371{
372 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().begin();
373
374 return const_iterator(&((*it)->getData()), &m_cache, it);
375}
376
377InMemoryStorage::const_iterator
378InMemoryStorage::end() const
379{
380 Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().end();
381
382 const Data* ptr = NULL;
383
384 return const_iterator(ptr, &m_cache, it);
385}
386
387void
388InMemoryStorage::afterInsert(InMemoryStorageEntry* entry)
389{
390}
391
392void
393InMemoryStorage::beforeErase(InMemoryStorageEntry* entry)
394{
395}
396
397void
398InMemoryStorage::afterAccess(InMemoryStorageEntry* entry)
399{
400}
401
402void
403InMemoryStorage::printCache(std::ostream& os) const
404{
405 //start from the upper layer towards bottom
406 const Cache::index<byFullName>::type& cacheIndex = m_cache.get<byFullName>();
407 for (Cache::index<byFullName>::type::iterator it = cacheIndex.begin();
408 it != cacheIndex.end(); it++)
409 os << (*it)->getFullName() << std::endl;
410}
411
412} // namespace util
413} // namespace ndn