interest.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2013-2018 Regents of the University of California.
4  *
5  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
6  *
7  * ndn-cxx library is free software: you can redistribute it and/or modify it under the
8  * terms of the GNU Lesser General Public License as published by the Free Software
9  * Foundation, either version 3 of the License, or (at your option) any later version.
10  *
11  * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
12  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
13  * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
14  *
15  * You should have received copies of the GNU General Public License and GNU Lesser
16  * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
17  * <http://www.gnu.org/licenses/>.
18  *
19  * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
20  */
21 
22 #include "interest.hpp"
23 #include "util/random.hpp"
24 #include "data.hpp"
25 
26 #include <cstring>
27 #include <sstream>
28 
29 namespace ndn {
30 
31 BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Interest>));
32 BOOST_CONCEPT_ASSERT((WireEncodable<Interest>));
33 BOOST_CONCEPT_ASSERT((WireEncodableWithEncodingBuffer<Interest>));
34 BOOST_CONCEPT_ASSERT((WireDecodable<Interest>));
35 static_assert(std::is_base_of<tlv::Error, Interest::Error>::value,
36  "Interest::Error must inherit from tlv::Error");
37 
38 Interest::Interest(const Name& name, time::milliseconds lifetime)
39  : m_name(name)
40  , m_interestLifetime(lifetime)
41 {
42  if (lifetime < time::milliseconds::zero()) {
43  BOOST_THROW_EXCEPTION(std::invalid_argument("InterestLifetime must be >= 0"));
44  }
45 }
46 
48 {
49  wireDecode(wire);
50 }
51 
52 // ---- encode and decode ----
53 
54 template<encoding::Tag TAG>
55 size_t
56 Interest::wireEncode(EncodingImpl<TAG>& encoder) const
57 {
58  size_t totalLength = 0;
59 
60  // Interest ::= INTEREST-TYPE TLV-LENGTH
61  // Name
62  // Selectors?
63  // Nonce
64  // InterestLifetime?
65  // ForwardingHint?
66 
67  // (reverse encoding)
68 
69  // ForwardingHint
70  if (m_forwardingHint.size() > 0) {
71  totalLength += m_forwardingHint.wireEncode(encoder);
72  }
73 
74  // InterestLifetime
76  totalLength += prependNonNegativeIntegerBlock(encoder,
78  getInterestLifetime().count());
79  }
80 
81  // Nonce
82  uint32_t nonce = this->getNonce(); // assigns random Nonce if needed
83  totalLength += encoder.prependByteArray(reinterpret_cast<uint8_t*>(&nonce), sizeof(nonce));
84  totalLength += encoder.prependVarNumber(sizeof(nonce));
85  totalLength += encoder.prependVarNumber(tlv::Nonce);
86 
87  // Selectors
88  if (hasSelectors()) {
89  totalLength += getSelectors().wireEncode(encoder);
90  }
91 
92  // Name
93  totalLength += getName().wireEncode(encoder);
94 
95  totalLength += encoder.prependVarNumber(totalLength);
96  totalLength += encoder.prependVarNumber(tlv::Interest);
97  return totalLength;
98 }
99 
101 
102 const Block&
104 {
105  if (m_wire.hasWire())
106  return m_wire;
107 
108  EncodingEstimator estimator;
109  size_t estimatedSize = wireEncode(estimator);
110 
111  EncodingBuffer buffer(estimatedSize, 0);
112  wireEncode(buffer);
113 
114  const_cast<Interest*>(this)->wireDecode(buffer.block());
115  return m_wire;
116 }
117 
118 void
120 {
121  m_wire = wire;
122  m_wire.parse();
123 
124  if (m_wire.type() != tlv::Interest) {
125  BOOST_THROW_EXCEPTION(Error("expecting Interest element, got " + to_string(m_wire.type())));
126  }
127 
128  if (!decode02()) {
129  decode03();
130  if (!hasNonce()) {
131  setNonce(getNonce());
132  }
133  }
134 }
135 
136 bool
137 Interest::decode02()
138 {
139  auto ele = m_wire.elements_begin();
140 
141  // Name
142  if (ele != m_wire.elements_end() && ele->type() == tlv::Name) {
143  m_name.wireDecode(*ele);
144  ++ele;
145  }
146  else {
147  return false;
148  }
149 
150  // Selectors?
151  if (ele != m_wire.elements_end() && ele->type() == tlv::Selectors) {
152  m_selectors.wireDecode(*ele);
153  ++ele;
154  }
155  else {
156  m_selectors = Selectors();
157  }
158 
159  // Nonce
160  if (ele != m_wire.elements_end() && ele->type() == tlv::Nonce) {
161  uint32_t nonce = 0;
162  if (ele->value_size() != sizeof(nonce)) {
163  BOOST_THROW_EXCEPTION(Error("Nonce element is malformed"));
164  }
165  std::memcpy(&nonce, ele->value(), sizeof(nonce));
166  m_nonce = nonce;
167  ++ele;
168  }
169  else {
170  return false;
171  }
172 
173  // InterestLifetime?
174  if (ele != m_wire.elements_end() && ele->type() == tlv::InterestLifetime) {
175  m_interestLifetime = time::milliseconds(readNonNegativeInteger(*ele));
176  ++ele;
177  }
178  else {
179  m_interestLifetime = DEFAULT_INTEREST_LIFETIME;
180  }
181 
182  // ForwardingHint?
183  if (ele != m_wire.elements_end() && ele->type() == tlv::ForwardingHint) {
184  m_forwardingHint.wireDecode(*ele, false);
185  ++ele;
186  }
187  else {
188  m_forwardingHint = DelegationList();
189  }
190 
191  return ele == m_wire.elements_end();
192 }
193 
194 void
195 Interest::decode03()
196 {
197  // Interest ::= INTEREST-TYPE TLV-LENGTH
198  // Name
199  // CanBePrefix?
200  // MustBeFresh?
201  // ForwardingHint?
202  // Nonce?
203  // InterestLifetime?
204  // HopLimit?
205  // Parameters?
206 
207  bool hasName = false;
208  m_selectors = Selectors().setMaxSuffixComponents(1); // CanBePrefix=0
209  m_nonce.reset();
210  m_interestLifetime = DEFAULT_INTEREST_LIFETIME;
211  m_forwardingHint = DelegationList();
212 
213  int lastEle = 0; // last recognized element index, in spec order
214  for (const Block& ele : m_wire.elements()) {
215  switch (ele.type()) {
216  case tlv::Name: {
217  if (lastEle >= 1) {
218  BOOST_THROW_EXCEPTION(Error("Name element is out of order"));
219  }
220  hasName = true;
221  m_name.wireDecode(ele);
222  if (m_name.empty()) {
223  BOOST_THROW_EXCEPTION(Error("Name has zero name components"));
224  }
225  lastEle = 1;
226  break;
227  }
228  case tlv::CanBePrefix: {
229  if (lastEle >= 2) {
230  BOOST_THROW_EXCEPTION(Error("CanBePrefix element is out of order"));
231  }
232  if (ele.value_size() != 0) {
233  BOOST_THROW_EXCEPTION(Error("CanBePrefix element has non-zero TLV-LENGTH"));
234  }
235  m_selectors.setMaxSuffixComponents(-1);
236  lastEle = 2;
237  break;
238  }
239  case tlv::MustBeFresh: {
240  if (lastEle >= 3) {
241  BOOST_THROW_EXCEPTION(Error("MustBeFresh element is out of order"));
242  }
243  if (ele.value_size() != 0) {
244  BOOST_THROW_EXCEPTION(Error("MustBeFresh element has non-zero TLV-LENGTH"));
245  }
246  m_selectors.setMustBeFresh(true);
247  lastEle = 3;
248  break;
249  }
250  case tlv::ForwardingHint: {
251  if (lastEle >= 4) {
252  BOOST_THROW_EXCEPTION(Error("ForwardingHint element is out of order"));
253  }
254  m_forwardingHint.wireDecode(ele);
255  lastEle = 4;
256  break;
257  }
258  case tlv::Nonce: {
259  if (lastEle >= 5) {
260  BOOST_THROW_EXCEPTION(Error("Nonce element is out of order"));
261  }
262  uint32_t nonce = 0;
263  if (ele.value_size() != sizeof(nonce)) {
264  BOOST_THROW_EXCEPTION(Error("Nonce element is malformed"));
265  }
266  std::memcpy(&nonce, ele.value(), sizeof(nonce));
267  m_nonce = nonce;
268  lastEle = 5;
269  break;
270  }
271  case tlv::InterestLifetime: {
272  if (lastEle >= 6) {
273  BOOST_THROW_EXCEPTION(Error("InterestLifetime element is out of order"));
274  }
275  m_interestLifetime = time::milliseconds(readNonNegativeInteger(ele));
276  lastEle = 6;
277  break;
278  }
279  case tlv::HopLimit: {
280  if (lastEle >= 7) {
281  break; // HopLimit is non-critical, ignore out-of-order appearance
282  }
283  if (ele.value_size() != 1) {
284  BOOST_THROW_EXCEPTION(Error("HopLimit element is malformed"));
285  }
286  // TLV-VALUE is ignored
287  lastEle = 7;
288  break;
289  }
290  case tlv::Parameters: {
291  if (lastEle >= 8) {
292  BOOST_THROW_EXCEPTION(Error("Parameters element is out of order"));
293  }
294  // TLV-VALUE is ignored
295  lastEle = 8;
296  break;
297  }
298  default: {
299  if (tlv::isCriticalType(ele.type())) {
300  BOOST_THROW_EXCEPTION(Error("unrecognized element of critical type " +
301  to_string(ele.type())));
302  }
303  break;
304  }
305  }
306  }
307 
308  if (!hasName) {
309  BOOST_THROW_EXCEPTION(Error("Name element is missing"));
310  }
311 }
312 
313 std::string
315 {
316  std::ostringstream os;
317  os << *this;
318  return os.str();
319 }
320 
321 // ---- matching ----
322 
323 bool
324 Interest::matchesName(const Name& name) const
325 {
326  if (name.size() < m_name.size())
327  return false;
328 
329  if (!m_name.isPrefixOf(name))
330  return false;
331 
332  if (getMinSuffixComponents() >= 0 &&
333  // name must include implicit digest
334  !(name.size() - m_name.size() >= static_cast<size_t>(getMinSuffixComponents())))
335  return false;
336 
337  if (getMaxSuffixComponents() >= 0 &&
338  // name must include implicit digest
339  !(name.size() - m_name.size() <= static_cast<size_t>(getMaxSuffixComponents())))
340  return false;
341 
342  if (!getExclude().empty() &&
343  name.size() > m_name.size() &&
344  getExclude().isExcluded(name[m_name.size()]))
345  return false;
346 
347  return true;
348 }
349 
350 bool
351 Interest::matchesData(const Data& data) const
352 {
353  size_t interestNameLength = m_name.size();
354  const Name& dataName = data.getName();
355  size_t fullNameLength = dataName.size() + 1;
356 
357  // check MinSuffixComponents
358  bool hasMinSuffixComponents = getMinSuffixComponents() >= 0;
359  size_t minSuffixComponents = hasMinSuffixComponents ?
360  static_cast<size_t>(getMinSuffixComponents()) : 0;
361  if (!(interestNameLength + minSuffixComponents <= fullNameLength))
362  return false;
363 
364  // check MaxSuffixComponents
365  bool hasMaxSuffixComponents = getMaxSuffixComponents() >= 0;
366  if (hasMaxSuffixComponents &&
367  !(interestNameLength + getMaxSuffixComponents() >= fullNameLength))
368  return false;
369 
370  // check prefix
371  if (interestNameLength == fullNameLength) {
372  if (m_name.get(-1).isImplicitSha256Digest()) {
373  if (m_name != data.getFullName())
374  return false;
375  }
376  else {
377  // Interest Name is same length as Data full Name, but last component isn't digest
378  // so there's no possibility of matching
379  return false;
380  }
381  }
382  else {
383  // Interest Name is a strict prefix of Data full Name
384  if (!m_name.isPrefixOf(dataName))
385  return false;
386  }
387 
388  // check Exclude
389  // Exclude won't be violated if Interest Name is same as Data full Name
390  if (!getExclude().empty() && fullNameLength > interestNameLength) {
391  if (interestNameLength == fullNameLength - 1) {
392  // component to exclude is the digest
393  if (getExclude().isExcluded(data.getFullName().get(interestNameLength)))
394  return false;
395  // There's opportunity to inspect the Exclude filter and determine whether
396  // the digest would make a difference.
397  // eg. "<GenericNameComponent>AA</GenericNameComponent><Any/>" doesn't exclude
398  // any digest - fullName not needed;
399  // "<Any/><GenericNameComponent>AA</GenericNameComponent>" and
400  // "<Any/><ImplicitSha256DigestComponent>ffffffffffffffffffffffffffffffff
401  // </ImplicitSha256DigestComponent>"
402  // excludes all digests - fullName not needed;
403  // "<Any/><ImplicitSha256DigestComponent>80000000000000000000000000000000
404  // </ImplicitSha256DigestComponent>"
405  // excludes some digests - fullName required
406  // But Interests that contain the exact Data Name before digest and also
407  // contain Exclude filter is too rare to optimize for, so we request
408  // fullName no matter what's in the Exclude filter.
409  }
410  else {
411  // component to exclude is not the digest
412  if (getExclude().isExcluded(dataName.get(interestNameLength)))
413  return false;
414  }
415  }
416 
417  // check PublisherPublicKeyLocator
418  const KeyLocator& publisherPublicKeyLocator = this->getPublisherPublicKeyLocator();
419  if (!publisherPublicKeyLocator.empty()) {
420  const Signature& signature = data.getSignature();
421  const Block& signatureInfo = signature.getInfo();
423  if (it == signatureInfo.elements_end()) {
424  return false;
425  }
426  if (publisherPublicKeyLocator.wireEncode() != *it) {
427  return false;
428  }
429  }
430 
431  return true;
432 }
433 
434 bool
436 {
438  return (this->getName() == other.getName() &&
439  this->getSelectors() == other.getSelectors());
440 }
441 
442 // ---- field accessors ----
443 
444 uint32_t
446 {
447  if (!m_nonce) {
448  m_nonce = random::generateWord32();
449  }
450  return *m_nonce;
451 }
452 
453 Interest&
454 Interest::setNonce(uint32_t nonce)
455 {
456  m_nonce = nonce;
457  m_wire.reset();
458  return *this;
459 }
460 
461 void
463 {
464  if (!hasNonce())
465  return;
466 
467  uint32_t oldNonce = getNonce();
468  uint32_t newNonce = oldNonce;
469  while (newNonce == oldNonce)
470  newNonce = random::generateWord32();
471 
472  setNonce(newNonce);
473 }
474 
475 Interest&
476 Interest::setInterestLifetime(time::milliseconds lifetime)
477 {
478  if (lifetime < time::milliseconds::zero()) {
479  BOOST_THROW_EXCEPTION(std::invalid_argument("InterestLifetime must be >= 0"));
480  }
481  m_interestLifetime = lifetime;
482  m_wire.reset();
483  return *this;
484 }
485 
486 Interest&
488 {
489  m_forwardingHint = value;
490  m_wire.reset();
491  return *this;
492 }
493 
494 // ---- operators ----
495 
496 std::ostream&
497 operator<<(std::ostream& os, const Interest& interest)
498 {
499  os << interest.getName();
500 
501  char delim = '?';
502 
503  if (interest.getMinSuffixComponents() >= 0) {
504  os << delim << "ndn.MinSuffixComponents=" << interest.getMinSuffixComponents();
505  delim = '&';
506  }
507  if (interest.getMaxSuffixComponents() >= 0) {
508  os << delim << "ndn.MaxSuffixComponents=" << interest.getMaxSuffixComponents();
509  delim = '&';
510  }
511  if (interest.getChildSelector() != DEFAULT_CHILD_SELECTOR) {
512  os << delim << "ndn.ChildSelector=" << interest.getChildSelector();
513  delim = '&';
514  }
515  if (interest.getMustBeFresh()) {
516  os << delim << "ndn.MustBeFresh=" << interest.getMustBeFresh();
517  delim = '&';
518  }
520  os << delim << "ndn.InterestLifetime=" << interest.getInterestLifetime().count();
521  delim = '&';
522  }
523 
524  if (interest.hasNonce()) {
525  os << delim << "ndn.Nonce=" << interest.getNonce();
526  delim = '&';
527  }
528  if (!interest.getExclude().empty()) {
529  os << delim << "ndn.Exclude=" << interest.getExclude();
530  delim = '&';
531  }
532 
533  return os;
534 }
535 
536 } // namespace ndn
void wireDecode(const Block &wire)
Decode the input from wire format.
Definition: selectors.cpp:131
size_t wireEncode(EncodingImpl< TAG > &encoder) const
prepend wire encoding
Definition: key-locator.cpp:52
int getMinSuffixComponents() const
Definition: interest.hpp:300
int getMaxSuffixComponents() const
Definition: interest.hpp:316
const Name & getName() const
Definition: interest.hpp:137
Copyright (c) 2013-2017 Regents of the University of California.
Definition: common.hpp:66
const element_container & elements() const
Get container of sub elements.
Definition: block.hpp:347
bool matchesName(const Name &name) const
Check if Interest, including selectors, matches the given name.
Definition: interest.cpp:324
size_t prependNonNegativeIntegerBlock(EncodingImpl< TAG > &encoder, uint32_t type, uint64_t value)
Prepend a TLV element containing a non-negative integer.
Selectors & setMustBeFresh(bool mustBeFresh)
Definition: selectors.cpp:225
size_t wireEncode(EncodingImpl< TAG > &encoder) const
Fast encoding or block size estimation.
Definition: selectors.cpp:61
constexpr bool isCriticalType(uint32_t type)
Determine whether a TLV-TYPE is "critical" for evolvability purpose.
element_const_iterator find(uint32_t type) const
Find the first sub element of specified TLV-TYPE.
Definition: block.cpp:437
void refreshNonce()
Change nonce value.
Definition: interest.cpp:462
std::ostream & operator<<(std::ostream &os, const Data &data)
Definition: data.cpp:337
Interest(const Name &name=Name(), time::milliseconds lifetime=DEFAULT_INTEREST_LIFETIME)
Construct an Interest with given name and lifetime.
Definition: interest.cpp:38
element_container::const_iterator element_const_iterator
Definition: block.hpp:47
bool hasSelectors() const
Check if Interest has any selector present.
Definition: interest.hpp:277
const Signature & getSignature() const
Get Signature.
Definition: data.hpp:189
const int DEFAULT_CHILD_SELECTOR
Definition: selectors.hpp:31
const Block & wireEncode() const
Encode to a Block.
Definition: interest.cpp:103
size_t wireEncode(EncodingImpl< TAG > &encoder) const
Fast encoding or block size estimation.
Definition: name.cpp:126
Represents a TLV element of NDN packet format.
Definition: block.hpp:42
Represents an Interest packet.
Definition: interest.hpp:42
std::string toUri() const
Return a URI-like string that represents the Interest.
Definition: interest.cpp:314
int getChildSelector() const
Definition: interest.hpp:364
uint64_t readNonNegativeInteger(const Block &block)
Read a non-negative integer from a TLV element.
uint32_t getNonce() const
Get nonce value.
Definition: interest.cpp:445
Selectors & setMaxSuffixComponents(int maxSuffixComponents)
Definition: selectors.cpp:190
uint32_t generateWord32()
Generate a non-cryptographically-secure random integer in the range [0, 2^32)
Definition: random.cpp:63
bool isExcluded(const name::Component &comp) const
Check if name component is excluded.
Definition: exclude.cpp:231
void wireDecode(const Block &block, bool wantSort=true)
decode a DelegationList
const Selectors & getSelectors() const
Definition: interest.hpp:284
bool empty() const
Definition: key-locator.hpp:95
Interest & setNonce(uint32_t nonce)
Set nonce value.
Definition: interest.cpp:454
const Exclude & getExclude() const
Definition: interest.hpp:348
#define NDN_CXX_DEFINE_WIRE_ENCODE_INSTANTIATIONS(ClassName)
size_t size() const
Get number of components.
Definition: name.hpp:154
size_t size() const noexcept
void reset()
Reset wire buffer of the element.
Definition: block.cpp:258
Represents an absolute name.
Definition: name.hpp:42
bool isPrefixOf(const Name &other) const
Check if this name is a prefix of another name.
Definition: name.cpp:255
bool matchesData(const Data &data) const
Check if Interest can be satisfied by data.
Definition: interest.cpp:351
void parse() const
Parse TLV-VALUE into sub elements.
Definition: block.cpp:336
uint32_t type() const
Get TLV-TYPE.
Definition: block.hpp:235
void wireDecode(const Block &wire)
Decode from wire in NDN Packet Format v0.2 or v0.3.
Definition: interest.cpp:119
bool matchesInterest(const Interest &other) const
Check if Interest matches other interest.
Definition: interest.cpp:435
const Name & getName() const
Get name.
Definition: data.hpp:128
bool empty() const
Definition: exclude.hpp:327
const Block & getInfo() const
Get SignatureInfo as wire format.
Definition: signature.hpp:77
bool empty() const
Check if name is empty.
Definition: name.hpp:146
bool hasWire() const
Check if the Block has fully encoded wire.
Definition: block.cpp:252
represents a list of Delegations
Interest & setForwardingHint(const DelegationList &value)
Definition: interest.cpp:487
Interest & setInterestLifetime(time::milliseconds lifetime)
Set Interest&#39;s lifetime.
Definition: interest.cpp:476
const KeyLocator & getPublisherPublicKeyLocator() const
Definition: interest.hpp:332
const time::milliseconds DEFAULT_INTEREST_LIFETIME
default value for InterestLifetime
Definition: interest.hpp:38
std::string to_string(const V &v)
Definition: backports.hpp:107
element_const_iterator elements_end() const
Equivalent to elements().end()
Definition: block.hpp:363
time::milliseconds getInterestLifetime() const
Definition: interest.hpp:261
void reset() noexcept
const Name & getFullName() const
Get full name including implicit digest.
Definition: data.cpp:197
element_const_iterator elements_begin() const
Equivalent to elements().begin()
Definition: block.hpp:355
void wireDecode(const Block &wire)
Decode name from wire encoding.
Definition: name.cpp:159
Represents a Data packet.
Definition: data.hpp:35
bool getMustBeFresh() const
Check whether the MustBeFresh element is present.
Definition: interest.hpp:184
const Component & get(ssize_t i) const
Get the component at the given index.
Definition: name.hpp:164
EncodingImpl< EncoderTag > EncodingBuffer
size_t wireEncode(EncodingImpl< TAG > &encoder, uint32_t type=tlv::ForwardingHint) const
encode into wire format
EncodingImpl< EstimatorTag > EncodingEstimator
bool isImplicitSha256Digest() const
Check if the component is ImplicitSha256DigestComponent.
Holds SignatureInfo and SignatureValue in a Data packet.
Definition: signature.hpp:37
bool hasNonce() const
Check if the Nonce element is present.
Definition: interest.hpp:235