strategy-choice.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2024, 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 
26 #include "strategy-choice.hpp"
27 #include "measurements-entry.hpp"
28 #include "pit-entry.hpp"
29 
30 #include "common/logger.hpp"
31 #include "fw/strategy.hpp"
32 
33 namespace nfd::strategy_choice {
34 
35 NFD_LOG_INIT(StrategyChoice);
36 
37 using fw::Strategy;
38 
39 static inline bool
41 {
42  return nte.getStrategyChoiceEntry() != nullptr;
43 }
44 
46  : m_forwarder(forwarder)
47  , m_nameTree(m_forwarder.getNameTree())
48 {
49 }
50 
51 void
52 StrategyChoice::setDefaultStrategy(const Name& strategyName)
53 {
54  auto entry = make_unique<Entry>(Name());
55  entry->setStrategy(Strategy::create(strategyName, m_forwarder));
56  NFD_LOG_INFO("setDefaultStrategy " << entry->getStrategyInstanceName());
57 
58  // don't use .insert here, because it will invoke findEffectiveStrategy
59  // which expects an existing root entry
60  name_tree::Entry& nte = m_nameTree.lookup(Name());
61  nte.setStrategyChoiceEntry(std::move(entry));
62  ++m_nItems;
63 }
64 
66 StrategyChoice::insert(const Name& prefix, const Name& strategyName)
67 {
68  if (prefix.size() > NameTree::getMaxDepth()) {
69  return InsertResult::DEPTH_EXCEEDED;
70  }
71 
72  unique_ptr<Strategy> strategy;
73  try {
74  strategy = Strategy::create(strategyName, m_forwarder);
75  }
76  catch (const std::invalid_argument& e) {
77  NFD_LOG_ERROR("insert(" << prefix << "," << strategyName << ") cannot create strategy: " << e.what());
78  return InsertResult(InsertResult::EXCEPTION, e.what());
79  }
80 
81  if (strategy == nullptr) {
82  NFD_LOG_ERROR("insert(" << prefix << "," << strategyName << ") strategy not registered");
83  return InsertResult::NOT_REGISTERED;
84  }
85 
86  name_tree::Entry& nte = m_nameTree.lookup(prefix);
87  Entry* entry = nte.getStrategyChoiceEntry();
88  Strategy* oldStrategy = nullptr;
89  if (entry != nullptr) {
90  if (entry->getStrategyInstanceName() == strategy->getInstanceName()) {
91  NFD_LOG_TRACE("insert(" << prefix << ") not changing " << strategy->getInstanceName());
92  return InsertResult::OK;
93  }
94  oldStrategy = &entry->getStrategy();
95  NFD_LOG_TRACE("insert(" << prefix << ") changing from " << oldStrategy->getInstanceName() <<
96  " to " << strategy->getInstanceName());
97  }
98  else {
99  oldStrategy = &this->findEffectiveStrategy(prefix);
100  auto newEntry = make_unique<Entry>(prefix);
101  entry = newEntry.get();
102  nte.setStrategyChoiceEntry(std::move(newEntry));
103  ++m_nItems;
104  NFD_LOG_TRACE("insert(" << prefix << ") new entry " << strategy->getInstanceName());
105  }
106 
107  this->changeStrategy(*entry, *oldStrategy, *strategy);
108  entry->setStrategy(std::move(strategy));
109  return InsertResult::OK;
110 }
111 
112 StrategyChoice::InsertResult::InsertResult(Status status, const std::string& exceptionMessage)
113  : m_status(status)
114  , m_exceptionMessage(exceptionMessage)
115 {
116 }
117 
118 std::ostream&
119 operator<<(std::ostream& os, const StrategyChoice::InsertResult& res)
120 {
121  switch (res.m_status) {
122  case StrategyChoice::InsertResult::OK:
123  return os << "OK";
124  case StrategyChoice::InsertResult::NOT_REGISTERED:
125  return os << "Strategy not registered";
126  case StrategyChoice::InsertResult::EXCEPTION:
127  return os << "Error instantiating strategy: " << res.m_exceptionMessage;
128  case StrategyChoice::InsertResult::DEPTH_EXCEEDED:
129  return os << "Prefix has too many components (limit is "
130  << std::to_string(NameTree::getMaxDepth()) << ")";
131  }
132  return os;
133 }
134 
135 void
136 StrategyChoice::erase(const Name& prefix)
137 {
138  BOOST_ASSERT(prefix.size() > 0);
139 
140  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
141  if (nte == nullptr) {
142  return;
143  }
144 
145  Entry* entry = nte->getStrategyChoiceEntry();
146  if (entry == nullptr) {
147  return;
148  }
149 
150  Strategy& oldStrategy = entry->getStrategy();
151 
152  Strategy& parentStrategy = this->findEffectiveStrategy(prefix.getPrefix(-1));
153  this->changeStrategy(*entry, oldStrategy, parentStrategy);
154 
155  nte->setStrategyChoiceEntry(nullptr);
156  m_nameTree.eraseIfEmpty(nte);
157  --m_nItems;
158 }
159 
160 std::pair<bool, Name>
161 StrategyChoice::get(const Name& prefix) const
162 {
163  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
164  if (nte == nullptr) {
165  return {false, {}};
166  }
167 
168  Entry* entry = nte->getStrategyChoiceEntry();
169  if (entry == nullptr) {
170  return {false, {}};
171  }
172 
173  return {true, entry->getStrategyInstanceName()};
174 }
175 
176 template<typename K>
177 Strategy&
178 StrategyChoice::findEffectiveStrategyImpl(const K& key) const
179 {
181  BOOST_ASSERT(nte != nullptr);
182  return nte->getStrategyChoiceEntry()->getStrategy();
183 }
184 
185 Strategy&
186 StrategyChoice::findEffectiveStrategy(const Name& prefix) const
187 {
188  return this->findEffectiveStrategyImpl(prefix);
189 }
190 
191 Strategy&
193 {
194  return this->findEffectiveStrategyImpl(pitEntry);
195 }
196 
197 Strategy&
199 {
200  return this->findEffectiveStrategyImpl(measurementsEntry);
201 }
202 
203 static inline void
205 {
206  NFD_LOG_TRACE("clearStrategyInfo " << nte.getName());
207 
208  for (const auto& pitEntry : nte.getPitEntries()) {
209  pitEntry->clearStrategyInfo();
210  for (const auto& inRecord : pitEntry->getInRecords()) {
211  const_cast<pit::InRecord&>(inRecord).clearStrategyInfo();
212  }
213  for (const auto& outRecord : pitEntry->getOutRecords()) {
214  const_cast<pit::OutRecord&>(outRecord).clearStrategyInfo();
215  }
216  }
217  if (nte.getMeasurementsEntry() != nullptr) {
219  }
220 }
221 
222 void
223 StrategyChoice::changeStrategy(Entry& entry, Strategy& oldStrategy, Strategy& newStrategy)
224 {
225  const Name& oldInstanceName = oldStrategy.getInstanceName();
226  const Name& newInstanceName = newStrategy.getInstanceName();
227  if (Strategy::areSameType(oldInstanceName, newInstanceName)) {
228  // same Strategy subclass type: no need to clear StrategyInfo
229  NFD_LOG_INFO("changeStrategy(" << entry.getPrefix() << ") "
230  << oldInstanceName << " -> " << newInstanceName << " same-type");
231  return;
232  }
233 
234  NFD_LOG_INFO("changeStrategy(" << entry.getPrefix() << ") "
235  << oldInstanceName << " -> " << newInstanceName);
236 
237  // reset StrategyInfo on a portion of NameTree,
238  // where entry's effective strategy is covered by the changing StrategyChoice entry
239  const name_tree::Entry* rootNte = m_nameTree.getEntry(entry);
240  BOOST_ASSERT(rootNte != nullptr);
241  const auto& ntChanged = m_nameTree.partialEnumerate(entry.getPrefix(),
242  [&rootNte] (const name_tree::Entry& nte) -> std::pair<bool, bool> {
243  if (&nte == rootNte) {
244  return {true, true};
245  }
246  if (nte.getStrategyChoiceEntry() != nullptr) {
247  return {false, false};
248  }
249  return {true, true};
250  });
251  for (const auto& nte : ntChanged) {
252  clearStrategyInfo(nte);
253  }
254 }
255 
257 StrategyChoice::getRange() const
258 {
259  return m_nameTree.fullEnumerate(&nteHasStrategyChoiceEntry) |
260  boost::adaptors::transformed(name_tree::GetTableEntry<Entry>(
262 }
263 
264 } // namespace nfd::strategy_choice
Main class of NFD's forwarding engine.
Definition: forwarder.hpp:54
void clearStrategyInfo()
Clear all StrategyInfo items.
Base class of all forwarding strategies.
Definition: strategy.hpp:46
const Name & getInstanceName() const noexcept
Returns the strategy's instance name.
Definition: strategy.hpp:126
static unique_ptr< Strategy > create(const Name &instanceName, Forwarder &forwarder)
Returns a strategy instance created from instanceName.
Definition: strategy.cpp:92
static bool areSameType(const Name &instanceNameA, const Name &instanceNameB)
Returns whether two names will instantiate the same strategy type.
Definition: strategy.cpp:108
Represents an entry in the Measurements table.
An entry in the name tree.
measurements::Entry * getMeasurementsEntry() const
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
void setStrategyChoiceEntry(unique_ptr< strategy_choice::Entry > strategyChoiceEntry)
const Name & getName() const noexcept
strategy_choice::Entry * getStrategyChoiceEntry() const
Range partialEnumerate(const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
Enumerate all entries under a prefix.
Definition: name-tree.cpp:231
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
Delete the entry if it is empty.
Definition: name-tree.cpp:122
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
Definition: name-tree.cpp:225
static constexpr size_t getMaxDepth()
Maximum depth of the name tree.
Definition: name-tree.hpp:51
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
Definition: name-tree.cpp:43
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:77
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Definition: name-tree.cpp:149
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
Longest prefix matching.
Definition: name-tree.cpp:161
Represents an entry in the Interest table (PIT).
Definition: pit-entry.hpp:197
Contains information about an Interest from an incoming face.
Definition: pit-entry.hpp:107
Contains information about an Interest toward an outgoing face.
Definition: pit-entry.hpp:129
Represents an entry in the Strategy Choice table.
const Name & getStrategyInstanceName() const
fw::Strategy & getStrategy() const
void setStrategy(unique_ptr< fw::Strategy > strategy)
void erase(const Name &prefix)
Make prefix to inherit strategy from its parent.
boost::transformed_range< name_tree::GetTableEntry< Entry >, const name_tree::Range > Range
InsertResult insert(const Name &prefix, const Name &strategyName)
Set strategy of prefix to be strategyName.
void setDefaultStrategy(const Name &strategyName)
Set the default strategy.
fw::Strategy & findEffectiveStrategy(const Name &prefix) const
Get effective strategy for prefix.
std::pair< bool, Name > get(const Name &prefix) const
Get strategy Name of prefix.
#define NFD_LOG_ERROR
Definition: logger.hpp:41
#define NFD_LOG_INFO
Definition: logger.hpp:39
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
#define NFD_LOG_TRACE
Definition: logger.hpp:37
static void clearStrategyInfo(const name_tree::Entry &nte)
static bool nteHasStrategyChoiceEntry(const name_tree::Entry &nte)
std::ostream & operator<<(std::ostream &os, const StrategyChoice::InsertResult &res)