Branch data Line data Source code
1 : : // Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
2 : : //
3 : : // Permission to use, copy, modify, and/or distribute this software for any
4 : : // purpose with or without fee is hereby granted, provided that the above
5 : : // copyright notice and this permission notice appear in all copies.
6 : : //
7 : : // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
8 : : // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
9 : : // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
10 : : // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
11 : : // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
12 : : // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
13 : : // PERFORMANCE OF THIS SOFTWARE.
14 : :
15 : : #include <stdint.h>
16 : :
17 : : #include <map>
18 : :
19 : : #include <dns/question.h>
20 : : #include <dns/rrclass.h>
21 : : #include <dns/rrset.h>
22 : : #include <dns/rrtype.h>
23 : :
24 : : #include <list>
25 : :
26 : : #include <datasrc/cache.h>
27 : : #include <datasrc/logger.h>
28 : :
29 : : using namespace std;
30 : : using namespace isc::dns;
31 : :
32 : : namespace isc {
33 : : namespace datasrc {
34 : :
35 : : /// \brief A \c CacheEntry object contains the data stored with
36 : : /// each \c CacheNode: a pointer to the cached RRset (empty in
37 : : /// the case of a negative cache entry), and a copy of the
38 : : /// query-response flags that were returned when the RRset
39 : : /// was originally looked up in the low-level data source.
40 : 420 : class CacheEntry {
41 : : private:
42 : : /// The copy constructor and the assignment operator are intentionally
43 : : /// defined as private.
44 : : CacheEntry(const CacheEntry& source);
45 : : CacheEntry& operator=(const CacheEntry& source);
46 : :
47 : : public:
48 : 840 : CacheEntry(RRsetPtr r, uint32_t f) : rrset(r), flags(f) {};
49 : :
50 : : RRsetPtr rrset;
51 : : uint32_t flags;
52 : : };
53 : :
54 : : typedef boost::shared_ptr<CacheEntry> CacheEntryPtr;
55 : :
56 : : /// \brief A \c CacheNode is a node in the \c HotCache LRU queue. It
57 : : /// contains a pointer to a \c CacheEntry, a reference to the \c Question
58 : : /// that we are answering, a lifespan during which this entry remains
59 : : /// valid, and pointers to the next and previous entries in the list.
60 : 420 : class CacheNode {
61 : : private:
62 : : /// \name Constructors and Assignment Operator
63 : : ///
64 : : /// Note: The copy constructor and the assignment operator are intentionally
65 : : /// defined as private.
66 : : //@{
67 : : CacheNode(const CacheNode& source);
68 : : CacheNode& operator=(const CacheNode& source);
69 : :
70 : : public:
71 : : /// \brief Constructor for positive cache entry.
72 : : ///
73 : : /// \param rrset The \c RRset to cache.
74 : : /// \param flags The query response flags returned from the low-level
75 : : /// data source when this \c RRset was looked up.
76 : : /// \param lifespan How long the cache node is to be considered valid.
77 : : CacheNode(const RRsetPtr rrset, uint32_t flags, time_t lifespan);
78 : :
79 : : /// \brief Constructor for negative cache entry.
80 : : ///
81 : : /// \param name Query name
82 : : /// \param rrclass Query class
83 : : /// \param rrtype Query type
84 : : /// \param flags Query response flags returned from the low-level
85 : : /// data source, indicating why this lookup failed (name not found,
86 : : /// type not found, etc).
87 : : /// \param lifespan How long the cache node is to be considered valid.
88 : : CacheNode(const Name& name,
89 : : const RRClass& rrclass,
90 : : const RRType& rrtype,
91 : : uint32_t flags,
92 : : time_t lifespan);
93 : : //@}
94 : :
95 : : /// \name Getter and Setter Methods
96 : : //@{
97 : : /// \brief Returns a pointer to the cached RRset (or an empty
98 : : /// RRsetPtr for negative cache entries).
99 : :
100 : : /// \return \c RRsetPtr
101 : 718 : RRsetPtr getRRset() const { return (entry->rrset); }
102 : :
103 : : /// \brief Returns name associated with cached node
104 : : ///
105 : : /// This is the name associated with the RRset if it is a positive
106 : : /// entry, and the associated question name if the RRSet is NULL
107 : : /// and this is a negative entry (together with an indication that
108 : : /// this is a negative entry).
109 : 441 : string getNodeName() const {
110 [ + + ]: 882 : if (getRRset()) {
111 [ + - ][ + - ]: 204 : return (getRRset()->getName().toText());
112 : : }
113 [ + - ]: 678 : return (std::string("negative entry for ") + question.toText());
114 : : }
115 : :
116 : : /// \brief Returns the query response flags associated with the data.
117 : : ///
118 : : /// \return \c uint32_t
119 : 73 : uint32_t getFlags() const { return (entry->flags); }
120 : :
121 : : /// \brief Is this record still valid?
122 : : ///
123 : : /// \return True if the expiration time has not yet passed,
124 : : /// or false if it has.
125 : : bool isValid() const;
126 : : //@}
127 : :
128 : : // An iterator referencing this entry in the LRU list. This
129 : : // permits unit-time removal using list::erase().
130 : : list<CacheNodePtr>::iterator lru_entry_;
131 : :
132 : : /// The \c Question (name/rrclass/rrtype) answered by this cache node
133 : : const isc::dns::Question question;
134 : :
135 : : private:
136 : : // The cached RRset data
137 : : CacheEntryPtr entry;
138 : :
139 : : // When this record should be discarded
140 : : time_t expiry;
141 : : };
142 : :
143 : : // CacheNode constructor for a positive cache entry
144 : 186 : CacheNode::CacheNode(const RRsetPtr rrset, const uint32_t flags,
145 : : const time_t lifespan) :
146 : 186 : question(Question(rrset->getName(), rrset->getClass(), rrset->getType()))
147 : : {
148 : 186 : const time_t now = time(NULL);
149 : 186 : expiry = now + lifespan;
150 : :
151 [ + - ][ + - ]: 372 : entry = CacheEntryPtr(new CacheEntry(rrset, flags));
[ + - ]
152 : 186 : }
153 : :
154 : : // CacheNode constructor for a negative cache entry
155 : 234 : CacheNode::CacheNode(const Name& name,
156 : : const RRClass& rrclass,
157 : : const RRType& rrtype,
158 : : const uint32_t flags,
159 : : const time_t lifespan) :
160 : 0 : question(Question(name, rrclass, rrtype))
161 : : {
162 : 234 : const time_t now = time(NULL);
163 : 234 : expiry = now + lifespan;
164 : :
165 [ + - ][ + - ]: 468 : entry = CacheEntryPtr(new CacheEntry(RRsetPtr(), flags));
[ + - ]
166 : 234 : }
167 : : // Returns true if the node has not yet expired.
168 : : bool
169 : 82 : CacheNode::isValid() const {
170 : 82 : const time_t now = time(NULL);
171 : 82 : return (now < expiry);
172 : : }
173 : :
174 : : /// This class abstracts the implementation details for \c HotCache.
175 : : ///
176 : : /// Each node inserted into the cache is placed at the head of a
177 : : /// doubly-linked list. Whenever that node is retrieved from the cache,
178 : : /// it is again moved to the head of the list. When the configured
179 : : /// number of slots in the cache has been exceeded, the least recently
180 : : /// used nodes will be removed from the tail of the list.
181 : : ///
182 : : /// A pointer to each cache node is also placed in a \c std::map object,
183 : : /// keyed by \c isc::dns::Question. This allows retrieval of data in
184 : : /// (usually) logarithmic time. (Possible TODO item: replace this with a
185 : : /// hash table instead.)
186 : 154 : class HotCacheImpl {
187 : : public:
188 : : HotCacheImpl(int slots, bool enabled);
189 : :
190 : : // The LRU list
191 : : list<CacheNodePtr> lru_;
192 : :
193 : : // Flag to indicate whether the cache is enabled
194 : : bool enabled_;
195 : :
196 : : // The number of available slots in the LRU list. (If zero,
197 : : // then the list is unbounded; otherwise, items are removed
198 : : // from the tail of the list whenever it grows past slots_.)
199 : : int slots_;
200 : :
201 : : // The number of items currently in the list.
202 : : int count_;
203 : :
204 : : // Map from query tuple to cache node pointer, allowing fast retrieval
205 : : // of data without a linear search of the LRU list
206 : : std::map<Question, CacheNodePtr> map_;
207 : :
208 : : // Move a node to the front of the LRU list.
209 : : void promote(CacheNodePtr node);
210 : :
211 : : // Remove a node from the cache.
212 : : void remove(ConstCacheNodePtr node);
213 : :
214 : : // Insert a node into the cache (called by both cache() and ncache())
215 : : void insert(CacheNodePtr node);
216 : : };
217 : :
218 : : // HotCacheImpl constructor
219 : 154 : HotCacheImpl::HotCacheImpl(int slots, bool enabled) :
220 : 0 : enabled_(enabled), slots_(slots), count_(0)
221 : : {
222 [ + - ][ + - ]: 154 : LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_CACHE_CREATE);
[ + - ][ + - ]
223 : 154 : }
224 : :
225 : : // Insert a cache node into the cache
226 : : inline void
227 : 420 : HotCacheImpl::insert(const CacheNodePtr node) {
228 [ + - ][ + - ]: 840 : LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_CACHE_INSERT).
229 [ + - ][ + - ]: 840 : arg(node->getNodeName());
230 : : std::map<Question, CacheNodePtr>::const_iterator iter;
231 : 420 : iter = map_.find(node->question);
232 [ + + ]: 420 : if (iter != map_.end()) {
233 : 8 : CacheNodePtr old = iter->second;
234 [ + - ][ + - ]: 8 : if (old && old->isValid()) {
[ - + ][ + - ]
235 [ + - ][ + - ]: 16 : LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_CACHE_OLD_FOUND)
[ + - ]
236 [ + - ][ + - ]: 16 : .arg(node->getNodeName());
[ + - ]
237 [ + - ]: 8 : remove(old);
238 : : }
239 : : }
240 : :
241 : 420 : lru_.push_front(node);
242 : 420 : node->lru_entry_ = lru_.begin();
243 : :
244 : 420 : map_[node->question] = node;
245 : 420 : ++count_;
246 : :
247 [ + - ][ + + ]: 420 : if (slots_ != 0 && count_ > slots_) {
248 [ + - ]: 2 : LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_CACHE_FULL);
249 [ + - ]: 2 : remove(lru_.back());
250 : : }
251 : 420 : }
252 : :
253 : : // Promote a node to the head of the LRU list
254 : : void
255 : 73 : HotCacheImpl::promote(CacheNodePtr node) {
256 [ + - ]: 73 : if (!node) {
257 : : return;
258 : : }
259 [ + + ]: 73 : if (node->lru_entry_ == lru_.begin()) {
260 : : return;
261 : : }
262 : 66 : lru_.splice(lru_.begin(), lru_, node->lru_entry_); // move node to front
263 : 73 : node->lru_entry_ = lru_.begin();
264 : : }
265 : :
266 : : // Remove a node from the LRU list and the map
267 : : void
268 : 13 : HotCacheImpl::remove(ConstCacheNodePtr node) {
269 [ + - ][ + - ]: 26 : LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_CACHE_REMOVE).
270 [ + - ][ + - ]: 26 : arg(node->getNodeName());
271 : 13 : lru_.erase(node->lru_entry_);
272 : 13 : map_.erase(node->question);
273 : 13 : --count_;
274 : 13 : }
275 : :
276 : : // HotCache constructor
277 : 154 : HotCache::HotCache(const int slots) {
278 [ + - ]: 154 : impl_ = new HotCacheImpl(slots, true);
279 : 154 : }
280 : :
281 : : // HotCache destructor
282 : 154 : HotCache::~HotCache() {
283 [ + - ]: 154 : LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_CACHE_DESTROY);
284 [ + - ]: 308 : delete impl_;
285 : 154 : }
286 : :
287 : : // Add a positive entry to the cache
288 : : void
289 : 194 : HotCache::addPositive(RRsetPtr rrset, const uint32_t flags,
290 : : const time_t lifespan)
291 : : {
292 [ + + ]: 194 : if (!impl_->enabled_) {
293 : 194 : return;
294 : : }
295 : :
296 [ + - ][ + - ]: 186 : impl_->insert(CacheNodePtr(new CacheNode(rrset, flags, lifespan)));
[ + - ][ + - ]
297 : : }
298 : :
299 : : // Add a negative entry to the cache
300 : : void
301 : 243 : HotCache::addNegative(const Name& name, const RRClass &rrclass,
302 : : const RRType& rrtype, const uint32_t flags,
303 : : const time_t lifespan)
304 : : {
305 [ + + ]: 243 : if (!impl_->enabled_) {
306 : : return;
307 : : }
308 : :
309 [ + - ][ - + ]: 468 : if (rrtype == RRType::ANY() || rrclass == RRClass::ANY()) {
[ + - ]
310 : : return;
311 : : }
312 : :
313 : : impl_->insert(CacheNodePtr(new CacheNode(name, rrclass, rrtype,
314 [ + - ][ + - ]: 234 : flags, lifespan)));
315 : : }
316 : :
317 : : // Try to retrieve an entry from the cache, returning true if
318 : : // it was found and valid.
319 : : bool
320 : 527 : HotCache::retrieve(const Name& n, const RRClass& c, const RRType& t,
321 : : RRsetPtr& rrset, uint32_t& flags)
322 : : {
323 [ + + ]: 527 : if (!impl_->enabled_) {
324 : : return (false);
325 : : }
326 : :
327 : : std::map<Question, CacheNodePtr>::const_iterator iter;
328 [ + - ]: 507 : iter = impl_->map_.find(Question(n, c, t));
329 [ + + ]: 507 : if (iter == impl_->map_.end()) {
330 [ + - ][ + - ]: 433 : LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_CACHE_NOT_FOUND).arg(n);
331 : : return (false);
332 : : }
333 : :
334 : 74 : CacheNodePtr node = iter->second;
335 : :
336 [ + - ][ + + ]: 74 : if (node->isValid()) {
337 [ + - ][ + - ]: 73 : LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_CACHE_FOUND).arg(n);
[ + - ][ + - ]
[ + - ]
338 [ + - ]: 73 : impl_->promote(node);
339 [ + - ]: 73 : rrset = node->getRRset();
340 : 146 : flags = node->getFlags();
341 : : return (true);
342 : : }
343 : :
344 [ + - ][ + - ]: 1 : LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_CACHE_EXPIRED).arg(n);
[ + - ][ + - ]
[ + - ]
345 [ + - ]: 1 : impl_->remove(node);
346 : : return (false);
347 : : }
348 : :
349 : : // Set the number of slots in the cache.
350 : : void
351 : 18 : HotCache::setSlots(const int slots) {
352 : 18 : impl_->slots_ = slots;
353 : :
354 [ + - ]: 18 : if (!impl_->enabled_) {
355 : 18 : return;
356 : : }
357 : :
358 [ + - ]: 36 : logger.info(DATASRC_CACHE_SLOTS).arg(slots).arg(max(0, impl_->count_ -
359 [ + - ]: 18 : slots));
360 : :
361 [ + + ][ + + ]: 20 : while (impl_->slots_ != 0 && impl_->count_ > impl_->slots_) {
[ + + ]
362 [ + - ]: 2 : impl_->remove(impl_->lru_.back());
363 : : }
364 : : }
365 : :
366 : : // Return the number of slots in the cache
367 : : int
368 : 3 : HotCache::getSlots() const {
369 : 3 : return (impl_->slots_);
370 : : }
371 : :
372 : : /// Enable or disable the cache
373 : : void
374 : 101 : HotCache::setEnabled(const bool e) {
375 : 101 : impl_->enabled_ = e;
376 [ + + ]: 101 : if (e) {
377 : 85 : logger.info(DATASRC_CACHE_ENABLE);
378 : : } else {
379 : 16 : logger.info(DATASRC_CACHE_DISABLE);
380 : : }
381 : 101 : }
382 : :
383 : : /// Indicate whether the cache is enabled
384 : : bool
385 : 2 : HotCache::getEnabled() const {
386 : 2 : return (impl_->enabled_);
387 : : }
388 : :
389 : : // Return the number of entries in the cache
390 : : int
391 : 14 : HotCache::getCount() const {
392 : 14 : return (impl_->count_);
393 : : }
394 : :
395 : : }
396 : 107 : }
|
