blob: 85aade6102d867c8b926a853aa6ba994a710b891 [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
Junxiao Shi838c4f12014-11-03 18:55:24 -070063 if (this->hasStrategy(strategyName, true)) {
Junxiao Shibb5105f2014-03-03 12:06:45 -070064 NFD_LOG_ERROR("install(" << strategyName << ") duplicate strategyName");
65 return false;
66 }
67
68 m_strategyInstances[strategyName] = strategy;
69 return true;
70}
71
Junxiao Shi838c4f12014-11-03 18:55:24 -070072fw::Strategy*
Junxiao Shie93d6a32014-09-07 16:13:22 -070073StrategyChoice::getStrategy(const Name& strategyName) const
74{
Junxiao Shi838c4f12014-11-03 18:55:24 -070075 fw::Strategy* candidate = nullptr;
76 for (auto it = m_strategyInstances.lower_bound(strategyName);
Junxiao Shie93d6a32014-09-07 16:13:22 -070077 it != m_strategyInstances.end() && strategyName.isPrefixOf(it->first); ++it) {
78 switch (it->first.size() - strategyName.size()) {
79 case 0: // exact match
Junxiao Shi838c4f12014-11-03 18:55:24 -070080 return it->second.get();
Junxiao Shie93d6a32014-09-07 16:13:22 -070081 case 1: // unversioned strategyName matches versioned strategy
Junxiao Shi838c4f12014-11-03 18:55:24 -070082 candidate = it->second.get();
Junxiao Shie93d6a32014-09-07 16:13:22 -070083 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 Shi838c4f12014-11-03 18:55:24 -070092 Strategy* strategy = this->getStrategy(strategyName);
93 if (strategy == nullptr) {
Junxiao Shibb5105f2014-03-03 12:06:45 -070094 NFD_LOG_ERROR("insert(" << prefix << "," << strategyName << ") strategy not installed");
95 return false;
96 }
97
Junxiao Shi838c4f12014-11-03 18:55:24 -070098 shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(prefix);
99 shared_ptr<Entry> entry = nte->getStrategyChoiceEntry();
100 Strategy* oldStrategy = nullptr;
Junxiao Shie93d6a32014-09-07 16:13:22 -0700101 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 }
Junxiao Shi838c4f12014-11-03 18:55:24 -0700106 oldStrategy = &entry->getStrategy();
Junxiao Shie93d6a32014-09-07 16:13:22 -0700107 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)) {
Junxiao Shi838c4f12014-11-03 18:55:24 -0700112 oldStrategy = &this->findEffectiveStrategy(prefix);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700113 entry = make_shared<Entry>(prefix);
Junxiao Shi838c4f12014-11-03 18:55:24 -0700114 nte->setStrategyChoiceEntry(entry);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700115 ++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
Junxiao Shi838c4f12014-11-03 18:55:24 -0700119 this->changeStrategy(*entry, *oldStrategy, *strategy);
120 entry->setStrategy(*strategy);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700121 return true;
122}
123
124void
125StrategyChoice::erase(const Name& prefix)
126{
127 BOOST_ASSERT(prefix.size() > 0);
128
Junxiao Shi838c4f12014-11-03 18:55:24 -0700129 shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
130 if (!static_cast<bool>(nte)) {
Junxiao Shibb5105f2014-03-03 12:06:45 -0700131 return;
132 }
133
Junxiao Shi838c4f12014-11-03 18:55:24 -0700134 shared_ptr<Entry> entry = nte->getStrategyChoiceEntry();
Junxiao Shibb5105f2014-03-03 12:06:45 -0700135 if (!static_cast<bool>(entry)) {
136 return;
137 }
138
139 Strategy& oldStrategy = entry->getStrategy();
Junxiao Shie349ea12014-03-12 01:32:42 -0700140
141 Strategy& parentStrategy = this->findEffectiveStrategy(prefix.getPrefix(-1));
Junxiao Shi838c4f12014-11-03 18:55:24 -0700142 this->changeStrategy(*entry, oldStrategy, parentStrategy);
Junxiao Shie349ea12014-03-12 01:32:42 -0700143
Junxiao Shi838c4f12014-11-03 18:55:24 -0700144 nte->setStrategyChoiceEntry(shared_ptr<Entry>());
145 m_nameTree.eraseEntryIfEmpty(nte);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700146 --m_nItems;
Junxiao Shibb5105f2014-03-03 12:06:45 -0700147}
148
Junxiao Shi838c4f12014-11-03 18:55:24 -0700149std::pair<bool, Name>
Junxiao Shibb5105f2014-03-03 12:06:45 -0700150StrategyChoice::get(const Name& prefix) const
151{
Junxiao Shi838c4f12014-11-03 18:55:24 -0700152 shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
153 if (!static_cast<bool>(nte)) {
154 return { false, Name() };
Junxiao Shibb5105f2014-03-03 12:06:45 -0700155 }
156
Junxiao Shi838c4f12014-11-03 18:55:24 -0700157 shared_ptr<Entry> entry = nte->getStrategyChoiceEntry();
Junxiao Shibb5105f2014-03-03 12:06:45 -0700158 if (!static_cast<bool>(entry)) {
Junxiao Shi838c4f12014-11-03 18:55:24 -0700159 return { false, Name() };
Junxiao Shibb5105f2014-03-03 12:06:45 -0700160 }
161
Junxiao Shi838c4f12014-11-03 18:55:24 -0700162 return { true, entry->getStrategy().getName() };
Junxiao Shibb5105f2014-03-03 12:06:45 -0700163}
164
165Strategy&
166StrategyChoice::findEffectiveStrategy(const Name& prefix) const
167{
Junxiao Shi838c4f12014-11-03 18:55:24 -0700168 shared_ptr<name_tree::Entry> nte = m_nameTree.findLongestPrefixMatch(prefix,
169 [] (const name_tree::Entry& entry) {
170 return static_cast<bool>(entry.getStrategyChoiceEntry());
171 });
172
173 BOOST_ASSERT(static_cast<bool>(nte));
174 return nte->getStrategyChoiceEntry()->getStrategy();
Junxiao Shibb5105f2014-03-03 12:06:45 -0700175}
176
177Strategy&
Junxiao Shi838c4f12014-11-03 18:55:24 -0700178StrategyChoice::findEffectiveStrategy(shared_ptr<name_tree::Entry> nte) const
HangZhangcb4fc832014-03-11 16:57:11 +0800179{
Junxiao Shi838c4f12014-11-03 18:55:24 -0700180 shared_ptr<strategy_choice::Entry> entry = nte->getStrategyChoiceEntry();
HangZhangcb4fc832014-03-11 16:57:11 +0800181 if (static_cast<bool>(entry))
182 return entry->getStrategy();
Junxiao Shi838c4f12014-11-03 18:55:24 -0700183
184 nte = m_nameTree.findLongestPrefixMatch(nte,
185 [] (const name_tree::Entry& entry) {
186 return static_cast<bool>(entry.getStrategyChoiceEntry());
187 });
188
189 BOOST_ASSERT(static_cast<bool>(nte));
190 return nte->getStrategyChoiceEntry()->getStrategy();
HangZhangcb4fc832014-03-11 16:57:11 +0800191}
192
193Strategy&
Junxiao Shibb5105f2014-03-03 12:06:45 -0700194StrategyChoice::findEffectiveStrategy(const pit::Entry& pitEntry) const
195{
Junxiao Shi838c4f12014-11-03 18:55:24 -0700196 shared_ptr<name_tree::Entry> nte = m_nameTree.get(pitEntry);
HangZhangcb4fc832014-03-11 16:57:11 +0800197
Junxiao Shi838c4f12014-11-03 18:55:24 -0700198 BOOST_ASSERT(static_cast<bool>(nte));
199 return this->findEffectiveStrategy(nte);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700200}
201
Junxiao Shi7bb01512014-03-05 21:34:09 -0700202Strategy&
203StrategyChoice::findEffectiveStrategy(const measurements::Entry& measurementsEntry) const
204{
Junxiao Shi838c4f12014-11-03 18:55:24 -0700205 shared_ptr<name_tree::Entry> nte = m_nameTree.get(measurementsEntry);
HangZhangcb4fc832014-03-11 16:57:11 +0800206
Junxiao Shi838c4f12014-11-03 18:55:24 -0700207 BOOST_ASSERT(static_cast<bool>(nte));
208 return this->findEffectiveStrategy(nte);
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
Junxiao Shi838c4f12014-11-03 18:55:24 -0700218 shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(Name());
Junxiao Shibb5105f2014-03-03 12:06:45 -0700219 shared_ptr<Entry> entry = make_shared<Entry>(Name());
Junxiao Shi838c4f12014-11-03 18:55:24 -0700220 nte->setStrategyChoiceEntry(entry);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700221 ++m_nItems;
Junxiao Shi838c4f12014-11-03 18:55:24 -0700222 NFD_LOG_INFO("setDefaultStrategy " << strategy->getName());
Junxiao Shibb5105f2014-03-03 12:06:45 -0700223
Junxiao Shi838c4f12014-11-03 18:55:24 -0700224 entry->setStrategy(*strategy);
Junxiao Shibb5105f2014-03-03 12:06:45 -0700225}
226
Junxiao Shi838c4f12014-11-03 18:55:24 -0700227static inline void
228clearStrategyInfo(const name_tree::Entry& nte)
Junxiao Shie349ea12014-03-12 01:32:42 -0700229{
Junxiao Shi838c4f12014-11-03 18:55:24 -0700230 NFD_LOG_TRACE("clearStrategyInfo " << nte.getPrefix());
231
232 for (const shared_ptr<pit::Entry>& pitEntry : nte.getPitEntries()) {
233 pitEntry->clearStrategyInfo();
234 for (const pit::InRecord& inRecord : pitEntry->getInRecords()) {
235 const_cast<pit::InRecord&>(inRecord).clearStrategyInfo();
236 }
237 for (const pit::OutRecord& outRecord : pitEntry->getOutRecords()) {
238 const_cast<pit::OutRecord&>(outRecord).clearStrategyInfo();
239 }
Junxiao Shie349ea12014-03-12 01:32:42 -0700240 }
Junxiao Shi838c4f12014-11-03 18:55:24 -0700241 if (static_cast<bool>(nte.getMeasurementsEntry())) {
242 nte.getMeasurementsEntry()->clearStrategyInfo();
Junxiao Shie349ea12014-03-12 01:32:42 -0700243 }
244}
245
Junxiao Shibb5105f2014-03-03 12:06:45 -0700246void
Junxiao Shi838c4f12014-11-03 18:55:24 -0700247StrategyChoice::changeStrategy(strategy_choice::Entry& entry,
248 fw::Strategy& oldStrategy,
249 fw::Strategy& newStrategy)
Junxiao Shibb5105f2014-03-03 12:06:45 -0700250{
Junxiao Shi838c4f12014-11-03 18:55:24 -0700251 if (&oldStrategy == &newStrategy) {
Junxiao Shibb5105f2014-03-03 12:06:45 -0700252 return;
253 }
254
Junxiao Shi838c4f12014-11-03 18:55:24 -0700255 NFD_LOG_INFO("changeStrategy(" << entry.getPrefix() << ")"
256 << " from " << oldStrategy.getName()
257 << " to " << newStrategy.getName());
258
259 // reset StrategyInfo on a portion of NameTree,
260 // where entry's effective strategy is covered by the changing StrategyChoice entry
261 const name_tree::Entry* rootNte = m_nameTree.get(entry).get();
Junxiao Shi60607c72014-11-26 22:40:36 -0700262 auto&& ntChanged = m_nameTree.partialEnumerate(entry.getPrefix(),
Junxiao Shi838c4f12014-11-03 18:55:24 -0700263 [&rootNte] (const name_tree::Entry& nte) -> std::pair<bool, bool> {
264 if (&nte == rootNte) {
Junxiao Shi60607c72014-11-26 22:40:36 -0700265 return {true, true};
Junxiao Shi838c4f12014-11-03 18:55:24 -0700266 }
267 if (static_cast<bool>(nte.getStrategyChoiceEntry())) {
Junxiao Shi60607c72014-11-26 22:40:36 -0700268 return {false, false};
Junxiao Shi838c4f12014-11-03 18:55:24 -0700269 }
Junxiao Shi60607c72014-11-26 22:40:36 -0700270 return {true, true};
Junxiao Shi838c4f12014-11-03 18:55:24 -0700271 });
Junxiao Shi60607c72014-11-26 22:40:36 -0700272 for (const name_tree::Entry& nte : ntChanged) {
273 clearStrategyInfo(nte);
274 }
Junxiao Shibb5105f2014-03-03 12:06:45 -0700275}
276
Junxiao Shib5888d22014-05-26 07:35:22 -0700277StrategyChoice::const_iterator
278StrategyChoice::begin() const
279{
Junxiao Shi60607c72014-11-26 22:40:36 -0700280 auto&& enumerable = m_nameTree.fullEnumerate(
Junxiao Shi838c4f12014-11-03 18:55:24 -0700281 [] (const name_tree::Entry& entry) {
282 return static_cast<bool>(entry.getStrategyChoiceEntry());
Junxiao Shi60607c72014-11-26 22:40:36 -0700283 });
284 return const_iterator(enumerable.begin());
Junxiao Shib5888d22014-05-26 07:35:22 -0700285}
286
Junxiao Shibb5105f2014-03-03 12:06:45 -0700287} // namespace nfd