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-2019, 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 #include "common/global.hpp"
29 
30 namespace nfd {
31 namespace cs {
32 namespace priority_fifo {
33 
34 const std::string PriorityFifoPolicy::POLICY_NAME = "priority_fifo";
36 
38  : Policy(POLICY_NAME)
39 {
40 }
41 
43 {
44  for (auto entryInfoMapPair : m_entryInfoMap) {
45  delete entryInfoMapPair.second;
46  }
47 }
48 
49 void
50 PriorityFifoPolicy::doAfterInsert(EntryRef i)
51 {
52  this->attachQueue(i);
53  this->evictEntries();
54 }
55 
56 void
57 PriorityFifoPolicy::doAfterRefresh(EntryRef i)
58 {
59  this->detachQueue(i);
60  this->attachQueue(i);
61 }
62 
63 void
64 PriorityFifoPolicy::doBeforeErase(EntryRef i)
65 {
66  this->detachQueue(i);
67 }
68 
69 void
70 PriorityFifoPolicy::doBeforeUse(EntryRef i)
71 {
72  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
73 }
74 
75 void
76 PriorityFifoPolicy::evictEntries()
77 {
78  BOOST_ASSERT(this->getCs() != nullptr);
79 
80  while (this->getCs()->size() > this->getLimit()) {
81  this->evictOne();
82  }
83 }
84 
85 void
86 PriorityFifoPolicy::evictOne()
87 {
88  BOOST_ASSERT(!m_queues[QUEUE_UNSOLICITED].empty() ||
89  !m_queues[QUEUE_STALE].empty() ||
90  !m_queues[QUEUE_FIFO].empty());
91 
92  EntryRef i;
93  if (!m_queues[QUEUE_UNSOLICITED].empty()) {
94  i = m_queues[QUEUE_UNSOLICITED].front();
95  }
96  else if (!m_queues[QUEUE_STALE].empty()) {
97  i = m_queues[QUEUE_STALE].front();
98  }
99  else if (!m_queues[QUEUE_FIFO].empty()) {
100  i = m_queues[QUEUE_FIFO].front();
101  }
102 
103  this->detachQueue(i);
104  this->emitSignal(beforeEvict, i);
105 }
106 
107 void
108 PriorityFifoPolicy::attachQueue(EntryRef i)
109 {
110  BOOST_ASSERT(m_entryInfoMap.find(i) == m_entryInfoMap.end());
111 
112  EntryInfo* entryInfo = new EntryInfo();
113  if (i->isUnsolicited()) {
114  entryInfo->queueType = QUEUE_UNSOLICITED;
115  }
116  else if (!i->isFresh()) {
117  entryInfo->queueType = QUEUE_STALE;
118  }
119  else {
120  entryInfo->queueType = QUEUE_FIFO;
121  entryInfo->moveStaleEventId = getScheduler().schedule(i->getData().getFreshnessPeriod(),
122  [=] { moveToStaleQueue(i); });
123  }
124 
125  Queue& queue = m_queues[entryInfo->queueType];
126  entryInfo->queueIt = queue.insert(queue.end(), i);
127  m_entryInfoMap[i] = entryInfo;
128 }
129 
130 void
131 PriorityFifoPolicy::detachQueue(EntryRef i)
132 {
133  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
134 
135  EntryInfo* entryInfo = m_entryInfoMap[i];
136  if (entryInfo->queueType == QUEUE_FIFO) {
137  entryInfo->moveStaleEventId.cancel();
138  }
139 
140  m_queues[entryInfo->queueType].erase(entryInfo->queueIt);
141  m_entryInfoMap.erase(i);
142  delete entryInfo;
143 }
144 
145 void
146 PriorityFifoPolicy::moveToStaleQueue(EntryRef i)
147 {
148  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
149 
150  EntryInfo* entryInfo = m_entryInfoMap[i];
151  BOOST_ASSERT(entryInfo->queueType == QUEUE_FIFO);
152 
153  m_queues[QUEUE_FIFO].erase(entryInfo->queueIt);
154 
155  entryInfo->queueType = QUEUE_STALE;
156  Queue& queue = m_queues[QUEUE_STALE];
157  entryInfo->queueIt = queue.insert(queue.end(), i);
158  m_entryInfoMap[i] = entryInfo;
159 }
160 
161 } // namespace priority_fifo
162 } // namespace cs
163 } // namespace nfd
Cs * getCs() const
gets cs
Definition: cs-policy.hpp:77
size_t getLimit() const
gets hard limit (in number of entries)
Definition: cs-policy.hpp:93
#define NFD_REGISTER_CS_POLICY(P)
registers a CS policy
Definition: cs-policy.hpp:214
Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.
Definition: global.cpp:45
std::list< Policy::EntryRef > Queue
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
represents a CS replacement policy
Definition: cs-policy.hpp:38
Table::const_iterator EntryRef
a reference to an CS entry
Definition: cs-policy.hpp:111
signal::Signal< Policy, EntryRef > beforeEvict
emits when an entry is being evicted
Definition: cs-policy.hpp:118