NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
cs-policy-priority-fifo.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2018, 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,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
27 #include "cs.hpp"
28 
29 namespace nfd {
30 namespace cs {
31 namespace priority_fifo {
32 
33 const std::string PriorityFifoPolicy::POLICY_NAME = "priority_fifo";
35 
37  : Policy(POLICY_NAME)
38 {
39 }
40 
42 {
43  for (auto entryInfoMapPair : m_entryInfoMap) {
44  delete entryInfoMapPair.second;
45  }
46 }
47 
48 void
49 PriorityFifoPolicy::doAfterInsert(iterator i)
50 {
51  this->attachQueue(i);
52  this->evictEntries();
53 }
54 
55 void
56 PriorityFifoPolicy::doAfterRefresh(iterator i)
57 {
58  this->detachQueue(i);
59  this->attachQueue(i);
60 }
61 
62 void
63 PriorityFifoPolicy::doBeforeErase(iterator i)
64 {
65  this->detachQueue(i);
66 }
67 
68 void
69 PriorityFifoPolicy::doBeforeUse(iterator i)
70 {
71  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
72 }
73 
74 void
75 PriorityFifoPolicy::evictEntries()
76 {
77  BOOST_ASSERT(this->getCs() != nullptr);
78 
79  while (this->getCs()->size() > this->getLimit()) {
80  this->evictOne();
81  }
82 }
83 
84 void
85 PriorityFifoPolicy::evictOne()
86 {
87  BOOST_ASSERT(!m_queues[QUEUE_UNSOLICITED].empty() ||
88  !m_queues[QUEUE_STALE].empty() ||
89  !m_queues[QUEUE_FIFO].empty());
90 
91  iterator i;
92  if (!m_queues[QUEUE_UNSOLICITED].empty()) {
93  i = m_queues[QUEUE_UNSOLICITED].front();
94  }
95  else if (!m_queues[QUEUE_STALE].empty()) {
96  i = m_queues[QUEUE_STALE].front();
97  }
98  else if (!m_queues[QUEUE_FIFO].empty()) {
99  i = m_queues[QUEUE_FIFO].front();
100  }
101 
102  this->detachQueue(i);
103  this->emitSignal(beforeEvict, i);
104 }
105 
106 void
107 PriorityFifoPolicy::attachQueue(iterator i)
108 {
109  BOOST_ASSERT(m_entryInfoMap.find(i) == m_entryInfoMap.end());
110 
111  EntryInfo* entryInfo = new EntryInfo();
112  if (i->isUnsolicited()) {
113  entryInfo->queueType = QUEUE_UNSOLICITED;
114  }
115  else if (i->isStale()) {
116  entryInfo->queueType = QUEUE_STALE;
117  }
118  else {
119  entryInfo->queueType = QUEUE_FIFO;
120  entryInfo->moveStaleEventId = scheduler::schedule(i->getData().getFreshnessPeriod(),
121  [=] { moveToStaleQueue(i); });
122  }
123 
124  Queue& queue = m_queues[entryInfo->queueType];
125  entryInfo->queueIt = queue.insert(queue.end(), i);
126  m_entryInfoMap[i] = entryInfo;
127 }
128 
129 void
130 PriorityFifoPolicy::detachQueue(iterator i)
131 {
132  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
133 
134  EntryInfo* entryInfo = m_entryInfoMap[i];
135  if (entryInfo->queueType == QUEUE_FIFO) {
136  scheduler::cancel(entryInfo->moveStaleEventId);
137  }
138 
139  m_queues[entryInfo->queueType].erase(entryInfo->queueIt);
140  m_entryInfoMap.erase(i);
141  delete entryInfo;
142 }
143 
144 void
145 PriorityFifoPolicy::moveToStaleQueue(iterator i)
146 {
147  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
148 
149  EntryInfo* entryInfo = m_entryInfoMap[i];
150  BOOST_ASSERT(entryInfo->queueType == QUEUE_FIFO);
151 
152  m_queues[QUEUE_FIFO].erase(entryInfo->queueIt);
153 
154  entryInfo->queueType = QUEUE_STALE;
155  Queue& queue = m_queues[QUEUE_STALE];
156  entryInfo->queueIt = queue.insert(queue.end(), i);
157  m_entryInfoMap[i] = entryInfo;
158 }
159 
160 } // namespace priority_fifo
161 } // namespace cs
162 } // namespace nfd
Cs * getCs() const
gets cs
Definition: cs-policy.hpp:199
signal::Signal< Policy, iterator > beforeEvict
emits when an entry is being evicted
Definition: cs-policy.hpp:102
NFD_REGISTER_CS_POLICY(PriorityFifoPolicy)
#define emitSignal(...)
(implementation detail)
Definition: emit.hpp:76
Table::const_iterator iterator
Definition: cs-internal.hpp:41
represents a CS replacement policy
Definition: cs-policy.hpp:39
void cancel(EventId eventId)
Cancel a scheduled event.
Definition: scheduler.hpp:49
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
EventId schedule(time::nanoseconds after, const EventCallback &event)
Schedule an event.
Definition: scheduler.cpp:48
size_t getLimit() const
gets hard limit (in number of entries)
Definition: cs-policy.hpp:211