blob: e5da3fa360bce124df3d359436b13facfa2f6889 [file] [log] [blame]
Junxiao Shi0fcb41e2014-01-24 10:29:43 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -07003 * Copyright (c) 2014 Regents of the University of California,
4 * Arizona Board of Regents,
5 * Colorado State University,
6 * University Pierre & Marie Curie, Sorbonne University,
7 * Washington University in St. Louis,
8 * Beijing Institute of Technology
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -08009 *
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 * This file is part of NFD (Named Data Networking Forwarding Daemon).
11 * See AUTHORS.md for complete list of NFD authors and contributors.
12 *
13 * NFD is free software: you can redistribute it and/or modify it under the terms
14 * of the GNU General Public License as published by the Free Software Foundation,
15 * either version 3 of the License, or (at your option) any later version.
16 *
17 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
18 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
19 * PURPOSE. See the GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License along with
22 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
23 *
24 * \author Ilya Moiseenko <iliamo@ucla.edu>
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070025 */
26
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070027#include "cs.hpp"
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -060028#include "core/logger.hpp"
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080029#include <ndn-cpp-dev/util/crypto.hpp>
Ilya Moiseenko9c9231b2014-04-10 11:05:12 -040030#include "ndn-cpp-dev/security/signature-sha256-with-rsa.hpp"
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080031
32#define SKIPLIST_MAX_LAYERS 32
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040033#define SKIPLIST_PROBABILITY 25 // 25% (p = 1/4)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080034
35NFD_LOG_INIT("ContentStore");
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -080036
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080037namespace nfd {
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070038
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080039Cs::Cs(int nMaxPackets)
40 : m_nMaxPackets(nMaxPackets)
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040041 , m_nPackets(0)
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070042{
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080043 SkipListLayer* zeroLayer = new SkipListLayer();
44 m_skipList.push_back(zeroLayer);
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040045
46 for (size_t i = 0; i < m_nMaxPackets; i++)
47 m_freeCsEntries.push(new cs::Entry());
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070048}
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080049
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070050Cs::~Cs()
51{
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040052 // evict all items from CS
53 while (evictItem())
54 ;
55
56 BOOST_ASSERT(m_freeCsEntries.size() == m_nMaxPackets);
57
58 while (!m_freeCsEntries.empty())
59 {
60 delete m_freeCsEntries.front();
61 m_freeCsEntries.pop();
62 }
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080063}
64
65size_t
66Cs::size() const
67{
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040068 return m_nPackets; // size of the first layer in a skip list
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080069}
70
71void
72Cs::setLimit(size_t nMaxPackets)
73{
74 m_nMaxPackets = nMaxPackets;
75
76 while (isFull())
77 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040078 if (!evictItem())
79 break;
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080080 }
81}
82
83size_t
84Cs::getLimit() const
85{
86 return m_nMaxPackets;
87}
88
89//Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040090std::pair<cs::Entry*, bool>
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080091Cs::insertToSkipList(const Data& data, bool isUnsolicited)
92{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -070093 NFD_LOG_TRACE("insertToSkipList() " << data.getName() << ", "
94 << "skipList size " << size());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080095
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -040096 BOOST_ASSERT(m_cleanupIndex.size() <= size());
97 BOOST_ASSERT(m_freeCsEntries.size() > 0);
98
99 // take entry for the memory pool
100 cs::Entry* entry = m_freeCsEntries.front();
101 m_freeCsEntries.pop();
102 m_nPackets++;
103 entry->setData(data, isUnsolicited);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800104
105 bool insertInFront = false;
106 bool isIterated = false;
107 SkipList::reverse_iterator topLayer = m_skipList.rbegin();
108 SkipListLayer::iterator updateTable[SKIPLIST_MAX_LAYERS];
109 SkipListLayer::iterator head = (*topLayer)->begin();
110
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400111 if (!(*topLayer)->empty())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800112 {
113 //start from the upper layer towards bottom
114 int layer = m_skipList.size() - 1;
115 for (SkipList::reverse_iterator rit = topLayer; rit != m_skipList.rend(); ++rit)
116 {
117 //if we didn't do any iterations on the higher layers, start from the begin() again
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400118 if (!isIterated)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800119 head = (*rit)->begin();
120
121 updateTable[layer] = head;
122
123 if (head != (*rit)->end())
124 {
125 // it can happen when begin() contains the element in front of which we need to insert
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400126 if (!isIterated && ((*head)->getName() >= entry->getName()))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800127 {
128 --updateTable[layer];
129 insertInFront = true;
130 }
131 else
132 {
133 SkipListLayer::iterator it = head;
134
135 while ((*it)->getName() < entry->getName())
136 {
137 head = it;
138 updateTable[layer] = it;
139 isIterated = true;
140
141 ++it;
142 if (it == (*rit)->end())
143 break;
144 }
145 }
146 }
147
148 if (layer > 0)
149 head = (*head)->getIterators().find(layer - 1)->second; // move HEAD to the lower layer
150
151 layer--;
152 }
153 }
154 else
155 {
156 updateTable[0] = (*topLayer)->begin(); //initialization
157 }
158
159 head = updateTable[0];
160 ++head; // look at the next slot to check if it contains a duplicate
161
162 bool isCsEmpty = (size() == 0);
163 bool isInBoundaries = (head != (*m_skipList.begin())->end());
164 bool isNameIdentical = false;
165 if (!isCsEmpty && isInBoundaries)
166 {
167 isNameIdentical = (*head)->getName() == entry->getName();
168 }
169
170 //check if this is a duplicate packet
171 if (isNameIdentical)
172 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700173 NFD_LOG_TRACE("Duplicate name (with digest)");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800174
Alexander Afanasyev88811622014-04-10 00:00:15 -0700175 (*head)->setData(data, isUnsolicited, entry->getDigest()); //updates stale time
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800176
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400177 // new entry not needed, returning to the pool
178 entry->release();
179 m_freeCsEntries.push(entry);
180 m_nPackets--;
181
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800182 return std::make_pair(*head, false);
183 }
184
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700185 NFD_LOG_TRACE("Not a duplicate");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800186
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700187 size_t randomLayer = pickRandomLayer();
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800188
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400189 while (m_skipList.size() < randomLayer + 1)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800190 {
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700191 SkipListLayer* newLayer = new SkipListLayer();
192 m_skipList.push_back(newLayer);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800193
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700194 updateTable[(m_skipList.size() - 1)] = newLayer->begin();
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800195 }
196
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700197 size_t layer = 0;
198 for (SkipList::iterator i = m_skipList.begin();
199 i != m_skipList.end() && layer <= randomLayer; ++i)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800200 {
201 if (updateTable[layer] == (*i)->end() && !insertInFront)
202 {
203 (*i)->push_back(entry);
204 SkipListLayer::iterator last = (*i)->end();
205 --last;
206 entry->setIterator(layer, last);
207
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700208 NFD_LOG_TRACE("pushback " << &(*last));
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800209 }
210 else if (updateTable[layer] == (*i)->end() && insertInFront)
211 {
212 (*i)->push_front(entry);
213 entry->setIterator(layer, (*i)->begin());
214
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700215 NFD_LOG_TRACE("pushfront ");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800216 }
217 else
218 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700219 NFD_LOG_TRACE("insertafter");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800220 ++updateTable[layer]; // insert after
221 SkipListLayer::iterator position = (*i)->insert(updateTable[layer], entry);
222 entry->setIterator(layer, position); // save iterator where item was inserted
223 }
224 layer++;
225 }
226
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800227 return std::make_pair(entry, true);
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700228}
229
230bool
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800231Cs::insert(const Data& data, bool isUnsolicited)
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700232{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700233 NFD_LOG_TRACE("insert() " << data.getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800234
235 if (isFull())
236 {
237 evictItem();
238 }
239
240 //pointer and insertion status
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400241 std::pair<cs::Entry*, bool> entry = insertToSkipList(data, isUnsolicited);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800242
243 //new entry
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400244 if (static_cast<bool>(entry.first) && (entry.second == true))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800245 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400246 m_cleanupIndex.push_back(entry.first);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800247 return true;
248 }
249
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700250 return false;
251}
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800252
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700253size_t
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800254Cs::pickRandomLayer() const
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700255{
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800256 int layer = -1;
257 int randomValue;
258
259 do
260 {
261 layer++;
262 randomValue = rand() % 100 + 1;
263 }
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400264 while ((randomValue < SKIPLIST_PROBABILITY) && (layer < SKIPLIST_MAX_LAYERS));
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800265
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700266 return static_cast<size_t>(layer);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800267}
268
269bool
270Cs::isFull() const
271{
272 if (size() >= m_nMaxPackets) //size of the first layer vs. max size
273 return true;
274
275 return false;
276}
277
278bool
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400279Cs::eraseFromSkipList(cs::Entry* entry)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800280{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700281 NFD_LOG_TRACE("eraseFromSkipList() " << entry->getName());
282 NFD_LOG_TRACE("SkipList size " << size());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800283
284 bool isErased = false;
285
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400286 const std::map<int, std::list<cs::Entry*>::iterator>& iterators = entry->getIterators();
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800287
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400288 if (!iterators.empty())
289 {
290 int layer = 0;
291
292 for (SkipList::iterator it = m_skipList.begin(); it != m_skipList.end(); )
293 {
294 std::map<int, std::list<cs::Entry*>::iterator>::const_iterator i = iterators.find(layer);
295
296 if (i != iterators.end())
297 {
298 (*it)->erase(i->second);
299 entry->removeIterator(layer);
300 isErased = true;
301
302 //remove layers that do not contain any elements (starting from the second layer)
303 if ((layer != 0) && (*it)->empty())
304 {
305 delete *it;
306 it = m_skipList.erase(it);
307 }
308 else
309 ++it;
310
311 layer++;
312 }
313 else
314 break;
315 }
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800316 }
317
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400318 //delete entry;
319 if (isErased)
320 {
321 entry->release();
322 m_freeCsEntries.push(entry);
323 m_nPackets--;
324 }
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800325
326 return isErased;
327}
328
329bool
330Cs::evictItem()
331{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700332 NFD_LOG_TRACE("evictItem()");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800333
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400334 if (!m_cleanupIndex.get<unsolicited>().empty() &&
335 (*m_cleanupIndex.get<unsolicited>().begin())->isUnsolicited())
336 {
337 NFD_LOG_TRACE("Evict from unsolicited queue");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800338
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400339 eraseFromSkipList(*m_cleanupIndex.get<unsolicited>().begin());
340 m_cleanupIndex.get<unsolicited>().erase(m_cleanupIndex.get<unsolicited>().begin());
341 return true;
342 }
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800343
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400344 if (!m_cleanupIndex.get<byStaleness>().empty() &&
345 (*m_cleanupIndex.get<byStaleness>().begin())->getStaleTime() < time::steady_clock::now())
346 {
347 NFD_LOG_TRACE("Evict from staleness queue");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800348
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400349 eraseFromSkipList(*m_cleanupIndex.get<byStaleness>().begin());
350 m_cleanupIndex.get<byStaleness>().erase(m_cleanupIndex.get<byStaleness>().begin());
351 return true;
352 }
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800353
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400354 if (!m_cleanupIndex.get<byArrival>().empty())
355 {
356 NFD_LOG_TRACE("Evict from arrival queue");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800357
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400358 eraseFromSkipList(*m_cleanupIndex.get<byArrival>().begin());
359 m_cleanupIndex.get<byArrival>().erase(m_cleanupIndex.get<byArrival>().begin());
360 return true;
361 }
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800362
363 return false;
364}
365
366const Data*
367Cs::find(const Interest& interest) const
368{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700369 NFD_LOG_TRACE("find() " << interest.getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800370
371 bool isIterated = false;
372 SkipList::const_reverse_iterator topLayer = m_skipList.rbegin();
373 SkipListLayer::iterator head = (*topLayer)->begin();
374
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400375 if (!(*topLayer)->empty())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800376 {
377 //start from the upper layer towards bottom
378 int layer = m_skipList.size() - 1;
379 for (SkipList::const_reverse_iterator rit = topLayer; rit != m_skipList.rend(); ++rit)
380 {
381 //if we didn't do any iterations on the higher layers, start from the begin() again
382 if (!isIterated)
383 head = (*rit)->begin();
384
385 if (head != (*rit)->end())
386 {
387 // it happens when begin() contains the element we want to find
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400388 if (!isIterated && (interest.getName().isPrefixOf((*head)->getName())))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800389 {
390 if (layer > 0)
391 {
392 layer--;
393 continue; // try lower layer
394 }
395 else
396 {
397 isIterated = true;
398 }
399 }
400 else
401 {
402 SkipListLayer::iterator it = head;
403
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400404 while ((*it)->getName() < interest.getName())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800405 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700406 NFD_LOG_TRACE((*it)->getName() << " < " << interest.getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800407 head = it;
408 isIterated = true;
409
410 ++it;
411 if (it == (*rit)->end())
412 break;
413 }
414 }
415 }
416
417 if (layer > 0)
418 {
419 head = (*head)->getIterators().find(layer - 1)->second; // move HEAD to the lower layer
420 }
421 else //if we reached the first layer
422 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400423 if (isIterated)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800424 return selectChild(interest, head);
425 }
426
427 layer--;
428 }
429 }
430
Alexander Afanasyevc9765df2014-01-25 19:24:27 -0800431 return 0;
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700432}
433
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800434const Data*
435Cs::selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const
436{
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400437 BOOST_ASSERT(startingPoint != (*m_skipList.begin())->end());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800438
439 if (startingPoint != (*m_skipList.begin())->begin())
440 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400441 BOOST_ASSERT((*startingPoint)->getName() < interest.getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800442 }
443
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400444 NFD_LOG_TRACE("selectChild() " << interest.getChildSelector() << " "
445 << (*startingPoint)->getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800446
447 bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
448 bool hasRightmostSelector = !hasLeftmostSelector;
449
450 if (hasLeftmostSelector)
451 {
452 bool doesInterestContainDigest = recognizeInterestWithDigest(interest, *startingPoint);
453 bool isInPrefix = false;
454
455 if (doesInterestContainDigest)
456 {
457 isInPrefix = interest.getName().getPrefix(-1).isPrefixOf((*startingPoint)->getName());
458 }
459 else
460 {
461 isInPrefix = interest.getName().isPrefixOf((*startingPoint)->getName());
462 }
463
464 if (isInPrefix)
465 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400466 if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800467 {
468 return &(*startingPoint)->getData();
469 }
470 }
471 }
472
473 //iterate to the right
474 SkipListLayer::iterator rightmost = startingPoint;
475 if (startingPoint != (*m_skipList.begin())->end())
476 {
477 SkipListLayer::iterator rightmostCandidate = startingPoint;
478 Name currentChildPrefix("");
479
480 while (true)
481 {
482 ++rightmostCandidate;
483
484 bool isInBoundaries = (rightmostCandidate != (*m_skipList.begin())->end());
485 bool isInPrefix = false;
486 bool doesInterestContainDigest = false;
487 if (isInBoundaries)
488 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400489 doesInterestContainDigest = recognizeInterestWithDigest(interest,
490 *rightmostCandidate);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800491
492 if (doesInterestContainDigest)
493 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400494 isInPrefix = interest.getName().getPrefix(-1)
495 .isPrefixOf((*rightmostCandidate)->getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800496 }
497 else
498 {
499 isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getName());
500 }
501 }
502
503 if (isInPrefix)
504 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400505 if (doesComplyWithSelectors(interest, *rightmostCandidate, doesInterestContainDigest))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800506 {
507 if (hasLeftmostSelector)
508 {
509 return &(*rightmostCandidate)->getData();
510 }
511
512 if (hasRightmostSelector)
513 {
514 if (doesInterestContainDigest)
515 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400516 // get prefix which is one component longer than Interest name
517 // (without digest)
518 const Name& childPrefix = (*rightmostCandidate)->getName()
519 .getPrefix(interest.getName().size());
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700520 NFD_LOG_TRACE("Child prefix" << childPrefix);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800521
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400522 if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800523 {
524 currentChildPrefix = childPrefix;
525 rightmost = rightmostCandidate;
526 }
527 }
528 else
529 {
530 // get prefix which is one component longer than Interest name
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400531 const Name& childPrefix = (*rightmostCandidate)->getName()
532 .getPrefix(interest.getName().size() + 1);
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700533 NFD_LOG_TRACE("Child prefix" << childPrefix);
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800534
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400535 if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800536 {
537 currentChildPrefix = childPrefix;
538 rightmost = rightmostCandidate;
539 }
540 }
541 }
542 }
543 }
544 else
545 break;
546 }
547 }
548
549 if (rightmost != startingPoint)
550 {
551 return &(*rightmost)->getData();
552 }
553
554 if (hasRightmostSelector) // if rightmost was not found, try starting point
555 {
556 bool doesInterestContainDigest = recognizeInterestWithDigest(interest, *startingPoint);
557 bool isInPrefix = false;
558
559 if (doesInterestContainDigest)
560 {
561 isInPrefix = interest.getName().getPrefix(-1).isPrefixOf((*startingPoint)->getName());
562 }
563 else
564 {
565 isInPrefix = interest.getName().isPrefixOf((*startingPoint)->getName());
566 }
567
568 if (isInPrefix)
569 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400570 if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800571 {
572 return &(*startingPoint)->getData();
573 }
574 }
575 }
576
577 return 0;
578}
579
580bool
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400581Cs::doesComplyWithSelectors(const Interest& interest,
582 cs::Entry* entry,
583 bool doesInterestContainDigest) const
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800584{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700585 NFD_LOG_TRACE("doesComplyWithSelectors()");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800586
587 /// \todo The following detection is not correct
588 /// 1. If data name ends with 32-octet component doesn't mean that this component is digest
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400589 /// 2. Only min/max selectors (both 0) can be specified, all other selectors do not
590 /// make sense for interests with digest (though not sure if we need to enforce this)
591
592 if (doesInterestContainDigest)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800593 {
594 const ndn::name::Component& last = interest.getName().get(-1);
595 const ndn::ConstBufferPtr& digest = entry->getDigest();
596
597 BOOST_ASSERT(digest->size() == last.value_size());
598 BOOST_ASSERT(digest->size() == ndn::crypto::SHA256_DIGEST_SIZE);
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700599
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800600 if (std::memcmp(digest->buf(), last.value(), ndn::crypto::SHA256_DIGEST_SIZE) != 0)
601 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700602 NFD_LOG_TRACE("violates implicit digest");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800603 return false;
604 }
605 }
606
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400607 if (!doesInterestContainDigest)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800608 {
609 if (interest.getMinSuffixComponents() >= 0)
610 {
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700611 size_t minDataNameLength = interest.getName().size() + interest.getMinSuffixComponents();
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800612
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700613 bool isSatisfied = (minDataNameLength <= entry->getName().size());
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400614 if (!isSatisfied)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800615 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700616 NFD_LOG_TRACE("violates minComponents");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800617 return false;
618 }
619 }
620
621 if (interest.getMaxSuffixComponents() >= 0)
622 {
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700623 size_t maxDataNameLength = interest.getName().size() + interest.getMaxSuffixComponents();
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800624
Alexander Afanasyevefea8fe2014-03-23 00:00:35 -0700625 bool isSatisfied = (maxDataNameLength >= entry->getName().size());
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400626 if (!isSatisfied)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800627 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700628 NFD_LOG_TRACE("violates maxComponents");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800629 return false;
630 }
631 }
632 }
633
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700634 if (interest.getMustBeFresh() && entry->getStaleTime() < time::steady_clock::now())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800635 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700636 NFD_LOG_TRACE("violates mustBeFresh");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800637 return false;
638 }
639
Ilya Moiseenko9c9231b2014-04-10 11:05:12 -0400640 if (!interest.getPublisherPublicKeyLocator().empty())
641 {
642 if (entry->getData().getSignature().getType() == ndn::Signature::Sha256WithRsa)
643 {
644 ndn::SignatureSha256WithRsa rsaSignature(entry->getData().getSignature());
645 if (rsaSignature.getKeyLocator() != interest.getPublisherPublicKeyLocator())
646 {
647 NFD_LOG_TRACE("violates publisher key selector");
648 return false;
649 }
650 }
651 else
652 {
653 NFD_LOG_TRACE("violates publisher key selector");
654 return false;
655 }
656 }
657
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400658 if (doesInterestContainDigest)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800659 {
660 const ndn::name::Component& lastComponent = entry->getName().get(-1);
661
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400662 if (!lastComponent.empty())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800663 {
664 if (interest.getExclude().isExcluded(lastComponent))
665 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700666 NFD_LOG_TRACE("violates exclusion");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800667 return false;
668 }
669 }
670 }
671 else
672 {
673 if (entry->getName().size() >= interest.getName().size() + 1)
674 {
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400675 const ndn::name::Component& nextComponent = entry->getName()
676 .get(interest.getName().size());
677 if (!nextComponent.empty())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800678 {
679 if (interest.getExclude().isExcluded(nextComponent))
680 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700681 NFD_LOG_TRACE("violates exclusion");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800682 return false;
683 }
684 }
685 }
686 }
687
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700688 NFD_LOG_TRACE("complies");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800689 return true;
690}
691
692bool
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400693Cs::recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800694{
695 // only when min selector is not specified or specified with value of 0
696 // and Interest's name length is exactly the length of the name of CS entry
697 if (interest.getMinSuffixComponents() <= 0 &&
698 interest.getName().size() == (entry->getName().size()))
699 {
700 const ndn::name::Component& last = interest.getName().get(-1);
701 if (last.value_size() == ndn::crypto::SHA256_DIGEST_SIZE)
702 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700703 NFD_LOG_TRACE("digest recognized");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800704 return true;
705 }
706 }
707
708 return false;
709}
710
711void
712Cs::erase(const Name& exactName)
713{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700714 NFD_LOG_TRACE("insert() " << exactName << ", "
715 << "skipList size " << size());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800716
717 bool isIterated = false;
718 SkipListLayer::iterator updateTable[SKIPLIST_MAX_LAYERS];
719 SkipList::reverse_iterator topLayer = m_skipList.rbegin();
720 SkipListLayer::iterator head = (*topLayer)->begin();
721
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400722 if (!(*topLayer)->empty())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800723 {
724 //start from the upper layer towards bottom
725 int layer = m_skipList.size() - 1;
726 for (SkipList::reverse_iterator rit = topLayer; rit != m_skipList.rend(); ++rit)
727 {
728 //if we didn't do any iterations on the higher layers, start from the begin() again
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400729 if (!isIterated)
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800730 head = (*rit)->begin();
731
732 updateTable[layer] = head;
733
734 if (head != (*rit)->end())
735 {
736 // it can happen when begin() contains the element we want to remove
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400737 if (!isIterated && ((*head)->getName() == exactName))
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800738 {
739 eraseFromSkipList(*head);
740 return;
741 }
742 else
743 {
744 SkipListLayer::iterator it = head;
745
746 while ((*it)->getName() < exactName)
747 {
748 head = it;
749 updateTable[layer] = it;
750 isIterated = true;
751
752 ++it;
Ilya Moiseenko96b80bb2014-04-05 20:53:27 -0400753 if (it == (*rit)->end())
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800754 break;
755 }
756 }
757 }
758
759 if (layer > 0)
760 head = (*head)->getIterators().find(layer - 1)->second; // move HEAD to the lower layer
761
762 layer--;
763 }
764 }
765 else
766 {
767 return;
768 }
769
770 head = updateTable[0];
771 ++head; // look at the next slot to check if it contains the item we want to remove
772
773 bool isCsEmpty = (size() == 0);
774 bool isInBoundaries = (head != (*m_skipList.begin())->end());
775 bool isNameIdentical = false;
776 if (!isCsEmpty && isInBoundaries)
777 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700778 NFD_LOG_TRACE("Identical? " << (*head)->getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800779 isNameIdentical = (*head)->getName() == exactName;
780 }
781
782 if (isNameIdentical)
783 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700784 NFD_LOG_TRACE("Found target " << (*head)->getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800785 eraseFromSkipList(*head);
786 }
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800787}
788
789void
790Cs::printSkipList() const
791{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700792 NFD_LOG_TRACE("print()");
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800793 //start from the upper layer towards bottom
794 int layer = m_skipList.size() - 1;
795 for (SkipList::const_reverse_iterator rit = m_skipList.rbegin(); rit != m_skipList.rend(); ++rit)
796 {
797 for (SkipListLayer::iterator it = (*rit)->begin(); it != (*rit)->end(); ++it)
798 {
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700799 NFD_LOG_TRACE("Layer " << layer << " " << (*it)->getName());
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -0800800 }
801 layer--;
802 }
803}
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700804
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800805} //namespace nfd