dead-nonce-list.hpp
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 #ifndef NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
27 #define NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
28 
29 #include "core/common.hpp"
30 
31 #include <ndn-cxx/util/scheduler.hpp>
32 
33 #include <boost/multi_index_container.hpp>
34 #include <boost/multi_index/hashed_index.hpp>
35 #include <boost/multi_index/sequenced_index.hpp>
36 
37 namespace nfd {
38 
56 class DeadNonceList : noncopyable
57 {
58 public:
66  explicit
67  DeadNonceList(time::nanoseconds lifetime = DEFAULT_LIFETIME);
68 
73  bool
74  has(const Name& name, Interest::Nonce nonce) const;
75 
79  void
80  add(const Name& name, Interest::Nonce nonce);
81 
86  size_t
87  size() const;
88 
92  time::nanoseconds
93  getLifetime() const
94  {
95  return m_lifetime;
96  }
97 
98 private:
99  using Entry = uint64_t;
100 
101  static Entry
102  makeEntry(const Name& name, Interest::Nonce nonce);
103 
106  size_t
107  countMarks() const;
108 
111  void
112  mark();
113 
119  void
120  adjustCapacity();
121 
124  void
125  evictEntries();
126 
127 public:
129  static constexpr time::nanoseconds DEFAULT_LIFETIME = 6_s;
131  static constexpr time::nanoseconds MIN_LIFETIME = 50_ms;
132 
133 private:
134  const time::nanoseconds m_lifetime;
135 
136  struct Queue {};
137  struct Hashtable {};
138  using Container = boost::multi_index_container<
139  Entry,
140  boost::multi_index::indexed_by<
141  boost::multi_index::sequenced<boost::multi_index::tag<Queue>>,
142  boost::multi_index::hashed_non_unique<boost::multi_index::tag<Hashtable>,
143  boost::multi_index::identity<Entry>>
144  >
145  >;
146 
147  Container m_index;
148  Container::index<Queue>::type& m_queue = m_index.get<Queue>();
149  Container::index<Hashtable>::type& m_ht = m_index.get<Hashtable>();
150 
152 
153  // ---- current capacity and hard limits
154 
162  size_t m_capacity;
163 
164  static constexpr size_t INITIAL_CAPACITY = 1 << 14;
165 
170  static constexpr size_t MIN_CAPACITY = 1 << 10;
171 
176  static constexpr size_t MAX_CAPACITY = 1 << 24;
177 
178  // ---- actual entry lifetime estimation
179 
186  static constexpr Entry MARK = 0;
187 
189  static constexpr size_t EXPECTED_MARK_COUNT = 5;
190 
196  std::multiset<size_t> m_actualMarkCounts;
197 
198  const time::nanoseconds m_markInterval;
199  ndn::scheduler::ScopedEventId m_markEvent;
200 
201  // ---- capacity adjustments
202 
203  static constexpr double CAPACITY_UP = 1.2;
204  static constexpr double CAPACITY_DOWN = 0.9;
205  const time::nanoseconds m_adjustCapacityInterval;
206  ndn::scheduler::ScopedEventId m_adjustCapacityEvent;
207 
209  static constexpr size_t EVICT_LIMIT = 64;
210 };
211 
212 } // namespace nfd
213 
214 #endif // NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
Represents the Dead Nonce List.
time::nanoseconds getLifetime() const
Returns the expected nonce lifetime.
static constexpr time::nanoseconds MIN_LIFETIME
Minimum entry lifetime.
static constexpr time::nanoseconds DEFAULT_LIFETIME
Default entry lifetime.
DeadNonceList(time::nanoseconds lifetime=DEFAULT_LIFETIME)
Constructs the Dead Nonce List.
size_t size() const
Returns the number of stored nonces.
void add(const Name &name, Interest::Nonce nonce)
Adds name+nonce to the list.
bool has(const Name &name, Interest::Nonce nonce) const
Determines if name+nonce is in the list.
#define NFD_PUBLIC_WITH_TESTS_ELSE_PRIVATE
Definition: common.hpp:41
boost::multi_index_container< Policy::EntryRef, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::ordered_unique< boost::multi_index::identity< Policy::EntryRef > > > > Queue
-status-http-server
Definition: common.hpp:71