dead-nonce-list.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "dead-nonce-list.hpp"
27 #include "core/city-hash.hpp"
28 #include "core/logger.hpp"
29 
30 NFD_LOG_INIT("DeadNonceList");
31 
32 namespace nfd {
33 
34 const time::nanoseconds DeadNonceList::DEFAULT_LIFETIME = time::seconds(6);
35 const time::nanoseconds DeadNonceList::MIN_LIFETIME = time::milliseconds(1);
36 const size_t DeadNonceList::INITIAL_CAPACITY = (1 << 7);
37 const size_t DeadNonceList::MIN_CAPACITY = (1 << 3);
38 const size_t DeadNonceList::MAX_CAPACITY = (1 << 24);
39 const DeadNonceList::Entry DeadNonceList::MARK = 0;
40 const size_t DeadNonceList::EXPECTED_MARK_COUNT = 5;
41 const double DeadNonceList::CAPACITY_UP = 1.2;
42 const double DeadNonceList::CAPACITY_DOWN = 0.9;
43 const size_t DeadNonceList::EVICT_LIMIT = (1 << 6);
44 
45 DeadNonceList::DeadNonceList(const time::nanoseconds& lifetime)
46  : m_lifetime(lifetime)
47  , m_queue(m_index.get<0>())
48  , m_ht(m_index.get<1>())
49  , m_capacity(INITIAL_CAPACITY)
50  , m_markInterval(m_lifetime / EXPECTED_MARK_COUNT)
51  , m_adjustCapacityInterval(m_lifetime)
52 {
53  if (m_lifetime < MIN_LIFETIME) {
54  BOOST_THROW_EXCEPTION(std::invalid_argument("lifetime is less than MIN_LIFETIME"));
55  }
56 
57  for (size_t i = 0; i < EXPECTED_MARK_COUNT; ++i) {
58  m_queue.push_back(MARK);
59  }
60 
61  m_markEvent = scheduler::schedule(m_markInterval, bind(&DeadNonceList::mark, this));
62  m_adjustCapacityEvent = scheduler::schedule(m_adjustCapacityInterval,
63  bind(&DeadNonceList::adjustCapacity, this));
64 }
65 
67 {
68  scheduler::cancel(m_markEvent);
69  scheduler::cancel(m_adjustCapacityEvent);
70 
71  BOOST_ASSERT_MSG(DEFAULT_LIFETIME >= MIN_LIFETIME, "DEFAULT_LIFETIME is too small");
72  static_assert(INITIAL_CAPACITY >= MIN_CAPACITY, "INITIAL_CAPACITY is too small");
73  static_assert(INITIAL_CAPACITY <= MAX_CAPACITY, "INITIAL_CAPACITY is too large");
74  BOOST_ASSERT_MSG(static_cast<size_t>(MIN_CAPACITY * CAPACITY_UP) > MIN_CAPACITY,
75  "CAPACITY_UP must be able to increase from MIN_CAPACITY");
76  BOOST_ASSERT_MSG(static_cast<size_t>(MAX_CAPACITY * CAPACITY_DOWN) < MAX_CAPACITY,
77  "CAPACITY_DOWN must be able to decrease from MAX_CAPACITY");
78  BOOST_ASSERT_MSG(CAPACITY_UP > 1.0, "CAPACITY_UP must adjust up");
79  BOOST_ASSERT_MSG(CAPACITY_DOWN < 1.0, "CAPACITY_DOWN must adjust down");
80  static_assert(EVICT_LIMIT >= 1, "EVICT_LIMIT must be at least 1");
81 }
82 
83 size_t
85 {
86  return m_queue.size() - this->countMarks();
87 }
88 
89 bool
90 DeadNonceList::has(const Name& name, uint32_t nonce) const
91 {
92  Entry entry = DeadNonceList::makeEntry(name, nonce);
93  return m_ht.find(entry) != m_ht.end();
94 }
95 
96 void
97 DeadNonceList::add(const Name& name, uint32_t nonce)
98 {
99  Entry entry = DeadNonceList::makeEntry(name, nonce);
100  m_queue.push_back(entry);
101 
102  this->evictEntries();
103 }
104 
105 DeadNonceList::Entry
106 DeadNonceList::makeEntry(const Name& name, uint32_t nonce)
107 {
108  Block nameWire = name.wireEncode();
109  return CityHash64WithSeed(reinterpret_cast<const char*>(nameWire.wire()), nameWire.size(),
110  static_cast<uint64_t>(nonce));
111 }
112 
113 size_t
114 DeadNonceList::countMarks() const
115 {
116  return m_ht.count(MARK);
117 }
118 
119 void
120 DeadNonceList::mark()
121 {
122  m_queue.push_back(MARK);
123  size_t nMarks = this->countMarks();
124  m_actualMarkCounts.insert(nMarks);
125 
126  NFD_LOG_TRACE("mark nMarks=" << nMarks);
127 
128  scheduler::schedule(m_markInterval, bind(&DeadNonceList::mark, this));
129 }
130 
131 void
132 DeadNonceList::adjustCapacity()
133 {
135  m_actualMarkCounts.equal_range(EXPECTED_MARK_COUNT);
136 
137  if (equalRange.second == m_actualMarkCounts.begin()) {
138  // all counts are above expected count, adjust down
139  m_capacity = std::max(MIN_CAPACITY,
140  static_cast<size_t>(m_capacity * CAPACITY_DOWN));
141  NFD_LOG_TRACE("adjustCapacity DOWN capacity=" << m_capacity);
142  }
143  else if (equalRange.first == m_actualMarkCounts.end()) {
144  // all counts are below expected count, adjust up
145  m_capacity = std::min(MAX_CAPACITY,
146  static_cast<size_t>(m_capacity * CAPACITY_UP));
147  NFD_LOG_TRACE("adjustCapacity UP capacity=" << m_capacity);
148  }
149 
150  m_actualMarkCounts.clear();
151 
152  this->evictEntries();
153 
154  m_adjustCapacityEvent = scheduler::schedule(m_adjustCapacityInterval,
155  bind(&DeadNonceList::adjustCapacity, this));
156 }
157 
158 void
159 DeadNonceList::evictEntries()
160 {
161  ssize_t nOverCapacity = m_queue.size() - m_capacity;
162  if (nOverCapacity <= 0) // not over capacity
163  return;
164 
165  for (ssize_t nEvict = std::min<ssize_t>(nOverCapacity, EVICT_LIMIT); nEvict > 0; --nEvict) {
166  m_queue.erase(m_queue.begin());
167  }
168  BOOST_ASSERT(m_queue.size() >= m_capacity);
169 }
170 
171 } // namespace nfd
void cancel(const EventId &eventId)
cancel a scheduled event
Definition: scheduler.cpp:53
size_t size() const
void add(const Name &name, uint32_t nonce)
records name+nonce
bool has(const Name &name, uint32_t nonce) const
determines if name+nonce exists
Table::const_iterator iterator
Definition: cs-internal.hpp:41
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed)
Definition: city-hash.cpp:397
DeadNonceList(const time::nanoseconds &lifetime=DEFAULT_LIFETIME)
constructs the Dead Nonce List
#define NFD_LOG_INIT(name)
Definition: logger.hpp:122
static const time::nanoseconds MIN_LIFETIME
minimum entry lifetime
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:160
EventId schedule(time::nanoseconds after, const EventCallback &event)
schedule an event
Definition: scheduler.cpp:47
static const time::nanoseconds DEFAULT_LIFETIME
default entry lifetime