blob: eedbc914201f913fd719c08668ccc96df45b4767 [file] [log] [blame]
Junxiao Shibb5105f2014-03-03 12:06:45 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Junxiao Shib5888d22014-05-26 07:35:22 -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,
9 * The University of Memphis
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 *
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/>.
Junxiao Shiee5a4442014-07-27 17:13:43 -070024 */
Junxiao Shibb5105f2014-03-03 12:06:45 -070025
26#include "strategy-choice.hpp"
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -060027#include "core/logger.hpp"
Junxiao Shibb5105f2014-03-03 12:06:45 -070028#include "fw/strategy.hpp"
29#include "pit-entry.hpp"
Junxiao Shi7bb01512014-03-05 21:34:09 -070030#include "measurements-entry.hpp"
Junxiao Shibb5105f2014-03-03 12:06:45 -070031
32namespace nfd {
33
34using strategy_choice::Entry;
35using fw::Strategy;
36
37NFD_LOG_INIT("StrategyChoice");
38
39StrategyChoice::StrategyChoice(NameTree& nameTree, shared_ptr<Strategy> defaultStrategy)
40 : m_nameTree(nameTree)
Junxiao Shib5888d22014-05-26 07:35:22 -070041 , m_nItems(0)
Junxiao Shibb5105f2014-03-03 12:06:45 -070042{
43 this->setDefaultStrategy(defaultStrategy);
44}
45
46bool
Junxiao Shie93d6a32014-09-07 16:13:22 -070047StrategyChoice::hasStrategy(const Name& strategyName, bool isExact) const
Junxiao Shibb5105f2014-03-03 12:06:45 -070048{
Junxiao Shie93d6a32014-09-07 16:13:22 -070049 if (isExact) {
50 return m_strategyInstances.count(strategyName) > 0;
51 }
52 else {
53 return static_cast<bool>(this->getStrategy(strategyName));
54 }
Junxiao Shibb5105f2014-03-03 12:06:45 -070055}
56
57bool
58StrategyChoice::install(shared_ptr<Strategy> strategy)
59{
60 BOOST_ASSERT(static_cast<bool>(strategy));
61 const Name& strategyName = strategy->getName();
62
63 if (this->hasStrategy(strategyName)) {
64 NFD_LOG_ERROR("install(" << strategyName << ") duplicate strategyName");
65 return false;
66 }
67
68 m_strategyInstances[strategyName] = strategy;
69 return true;
70}
71
Junxiao Shie93d6a32014-09-07 16:13:22 -070072shared_ptr<fw::Strategy>
73StrategyChoice::getStrategy(const Name& strategyName) const
74{
75 shared_ptr<fw::Strategy> candidate;
76 for (StrategyInstanceTable::const_iterator it = m_strategyInstances.lower_bound(strategyName);
77 it != m_strategyInstances.end() && strategyName.isPrefixOf(it->first); ++it) {
78 switch (it->first.size() - strategyName.size()) {
79 case 0: // exact match
80 return it->second;
81 case 1: // unversioned strategyName matches versioned strategy
82 candidate = it->second;
83 break;
84 }
85 }
86 return candidate;
87}
88
Junxiao Shibb5105f2014-03-03 12:06:45 -070089bool
90StrategyChoice::insert(const Name& prefix, const Name& strategyName)
91{
Junxiao Shibb5105f2014-03-03 12:06:45 -070092 shared_ptr<Strategy> strategy = this->getStrategy(strategyName);
93 if (!static_cast<bool>(strategy)) {
94 NFD_LOG_ERROR("insert(" << prefix << "," << strategyName << ") strategy not installed");
95 return false;
96 }
97
Junxiao Shie93d6a32014-09-07 16:13:22 -070098 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(prefix);
99 shared_ptr<Entry> entry = nameTreeEntry->getStrategyChoiceEntry();
100 shared_ptr<Strategy> oldStrategy;
101 if (static_cast<bool>(entry)) {
102 if (entry->getStrategy().getName() == strategy->getName()) {
103 NFD_LOG_TRACE("insert(" << prefix << ") not changing " << strategy->getName());
104 return true;
105 }
106 oldStrategy = entry->getStrategy().shared_from_this();
107 NFD_LOG_TRACE("insert(" << prefix << ") changing from " << oldStrategy->getName() <<
108 " to " << strategy->getName());
109 }
110
Junxiao Shibb5105f2014-03-03 12:06:45 -0700111 if (!static_cast<bool>(entry)) {
112 oldStrategy = this->findEffectiveStrategy(prefix).shared_from_this();
113 entry = make_shared<Entry>(prefix);
114 nameTreeEntry->setStrategyChoiceEntry(entry);
115 ++m_nItems;
Junxiao Shie93d6a32014-09-07 16:13:22 -0700116 NFD_LOG_TRACE("insert(" << prefix << ") new entry " << strategy->getName());
Junxiao Shibb5105f2014-03-03 12:06:45 -0700117 }
118
119 this->changeStrategy(entry, oldStrategy, strategy);
120 return true;
121}
122
123void
124StrategyChoice::erase(const Name& prefix)
125{
126 BOOST_ASSERT(prefix.size() > 0);
127
128 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
129 if (!static_cast<bool>(nameTreeEntry)) {
130 return;
131 }
132
133 shared_ptr<Entry> entry = nameTreeEntry->getStrategyChoiceEntry();
134 if (!static_cast<bool>(entry)) {
135 return;
136 }
137
138 Strategy& oldStrategy = entry->getStrategy();
Junxiao Shie349ea12014-03-12 01:32:42 -0700139
140 Strategy& parentStrategy = this->findEffectiveStrategy(prefix.getPrefix(-1));
141 this->changeStrategy(entry, oldStrategy.shared_from_this(), parentStrategy.shared_from_this());
142
Junxiao Shibb5105f2014-03-03 12:06:45 -0700143 nameTreeEntry->setStrategyChoiceEntry(shared_ptr<Entry>());
Junxiao Shiee5a4442014-07-27 17:13:43 -0700144 m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700145 --m_nItems;
Junxiao Shibb5105f2014-03-03 12:06:45 -0700146}
147
148shared_ptr<const Name>
149StrategyChoice::get(const Name& prefix) const
150{
151 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
152 if (!static_cast<bool>(nameTreeEntry)) {
153 return shared_ptr<const Name>();
154 }
155
156 shared_ptr<Entry> entry = nameTreeEntry->getStrategyChoiceEntry();
157 if (!static_cast<bool>(entry)) {
158 return shared_ptr<const Name>();
159 }
160
Steve DiBenedetto77c87512014-10-06 14:18:22 -0600161 return make_shared<const Name>(entry->getStrategy().getName());
Junxiao Shibb5105f2014-03-03 12:06:45 -0700162}
163
164static inline bool
165predicate_NameTreeEntry_hasStrategyChoiceEntry(const name_tree::Entry& entry)
166{
167 return static_cast<bool>(entry.getStrategyChoiceEntry());
168}
169
170Strategy&
171StrategyChoice::findEffectiveStrategy(const Name& prefix) const
172{
173 shared_ptr<name_tree::Entry> nameTreeEntry =
174 m_nameTree.findLongestPrefixMatch(prefix, &predicate_NameTreeEntry_hasStrategyChoiceEntry);
175 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
176 return nameTreeEntry->getStrategyChoiceEntry()->getStrategy();
177}
178
179Strategy&
HangZhangcb4fc832014-03-11 16:57:11 +0800180StrategyChoice::findEffectiveStrategy(shared_ptr<name_tree::Entry> nameTreeEntry) const
181{
182 shared_ptr<strategy_choice::Entry> entry = nameTreeEntry->getStrategyChoiceEntry();
183 if (static_cast<bool>(entry))
184 return entry->getStrategy();
Junxiao Shie349ea12014-03-12 01:32:42 -0700185 nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry,
HangZhangcb4fc832014-03-11 16:57:11 +0800186 &predicate_NameTreeEntry_hasStrategyChoiceEntry);
187 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
188 return nameTreeEntry->getStrategyChoiceEntry()->getStrategy();
189}
190
191Strategy&
Junxiao Shibb5105f2014-03-03 12:06:45 -0700192StrategyChoice::findEffectiveStrategy(const pit::Entry& pitEntry) const
193{
HangZhangcb4fc832014-03-11 16:57:11 +0800194 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
195
196 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
197
198 return findEffectiveStrategy(nameTreeEntry);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700199}
200
Junxiao Shi7bb01512014-03-05 21:34:09 -0700201Strategy&
202StrategyChoice::findEffectiveStrategy(const measurements::Entry& measurementsEntry) const
203{
HangZhangcb4fc832014-03-11 16:57:11 +0800204 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(measurementsEntry);
205
206 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
207
208 return findEffectiveStrategy(nameTreeEntry);
Junxiao Shi7bb01512014-03-05 21:34:09 -0700209}
210
Junxiao Shibb5105f2014-03-03 12:06:45 -0700211void
212StrategyChoice::setDefaultStrategy(shared_ptr<Strategy> strategy)
213{
214 this->install(strategy);
215
216 // don't use .insert here, because it will invoke findEffectiveStrategy
217 // which expects an existing root entry
218 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(Name());
219 shared_ptr<Entry> entry = make_shared<Entry>(Name());
220 nameTreeEntry->setStrategyChoiceEntry(entry);
221 ++m_nItems;
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700222 NFD_LOG_INFO("Set default strategy " << strategy->getName());
Junxiao Shibb5105f2014-03-03 12:06:45 -0700223
224 entry->setStrategy(strategy);
225}
226
Junxiao Shie349ea12014-03-12 01:32:42 -0700227/** \brief a predicate that decides whether StrategyInfo should be reset
228 *
229 * StrategyInfo on a NameTree entry needs to be reset,
230 * if its effective strategy is covered by the changing StrategyChoice entry.
231 */
232static inline std::pair<bool,bool>
233predicate_nameTreeEntry_needResetStrategyChoice(const name_tree::Entry& nameTreeEntry,
234 const name_tree::Entry& rootEntry)
235{
236 if (&nameTreeEntry == &rootEntry) {
237 return std::make_pair(true, true);
238 }
239 if (static_cast<bool>(nameTreeEntry.getStrategyChoiceEntry())) {
240 return std::make_pair(false, false);
241 }
242 return std::make_pair(true, true);
243}
244
245static inline void
246clearStrategyInfo_pitFaceRecord(const pit::FaceRecord& pitFaceRecord)
247{
248 const_cast<pit::FaceRecord&>(pitFaceRecord).clearStrategyInfo();
249}
250
251static inline void
252clearStrategyInfo_pitEntry(shared_ptr<pit::Entry> pitEntry)
253{
254 pitEntry->clearStrategyInfo();
255 std::for_each(pitEntry->getInRecords().begin(), pitEntry->getInRecords().end(),
256 &clearStrategyInfo_pitFaceRecord);
257 std::for_each(pitEntry->getOutRecords().begin(), pitEntry->getOutRecords().end(),
258 &clearStrategyInfo_pitFaceRecord);
259}
260
261static inline void
262clearStrategyInfo(const name_tree::Entry& nameTreeEntry)
263{
264 NFD_LOG_TRACE("clearStrategyInfo " << nameTreeEntry.getPrefix());
265
266 std::for_each(nameTreeEntry.getPitEntries().begin(), nameTreeEntry.getPitEntries().end(),
267 &clearStrategyInfo_pitEntry);
268 if (static_cast<bool>(nameTreeEntry.getMeasurementsEntry())) {
269 nameTreeEntry.getMeasurementsEntry()->clearStrategyInfo();
270 }
271}
272
Junxiao Shibb5105f2014-03-03 12:06:45 -0700273void
274StrategyChoice::changeStrategy(shared_ptr<strategy_choice::Entry> entry,
275 shared_ptr<fw::Strategy> oldStrategy,
276 shared_ptr<fw::Strategy> newStrategy)
277{
278 entry->setStrategy(newStrategy);
279 if (oldStrategy == newStrategy) {
280 return;
281 }
282
Junxiao Shie349ea12014-03-12 01:32:42 -0700283 std::for_each(m_nameTree.partialEnumerate(entry->getPrefix(),
284 bind(&predicate_nameTreeEntry_needResetStrategyChoice,
Alexander Afanasyevf6980282014-05-13 18:28:40 -0700285 _1, cref(*m_nameTree.get(*entry)))),
Junxiao Shie349ea12014-03-12 01:32:42 -0700286 m_nameTree.end(),
287 &clearStrategyInfo);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700288}
289
Junxiao Shib5888d22014-05-26 07:35:22 -0700290StrategyChoice::const_iterator
291StrategyChoice::begin() const
292{
293 return const_iterator(m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasStrategyChoiceEntry));
294}
295
Junxiao Shibb5105f2014-03-03 12:06:45 -0700296} // namespace nfd