[svn] commit: r1988 - in /branches/trac192/src/lib/datasrc: TODO cache.cc cache.h data_source.h query.h
BIND 10 source code commits
bind10-changes at lists.isc.org
Sun May 30 02:53:57 UTC 2010
Author: each
Date: Sun May 30 02:53:57 2010
New Revision: 1988
Log:
Doc, doc, doc.
Modified:
branches/trac192/src/lib/datasrc/TODO
branches/trac192/src/lib/datasrc/cache.cc
branches/trac192/src/lib/datasrc/cache.h
branches/trac192/src/lib/datasrc/data_source.h
branches/trac192/src/lib/datasrc/query.h
Modified: branches/trac192/src/lib/datasrc/TODO
==============================================================================
--- branches/trac192/src/lib/datasrc/TODO (original)
+++ branches/trac192/src/lib/datasrc/TODO Sun May 30 02:53:57 2010
@@ -1,5 +1,1 @@
- store rdata in the database as binary blobs instead of text
-
-hot cache:
-- restore query_unittest.cc, which is currently disabled because of
- the change in QueryTask construction.
Modified: branches/trac192/src/lib/datasrc/cache.cc
==============================================================================
--- branches/trac192/src/lib/datasrc/cache.cc (original)
+++ branches/trac192/src/lib/datasrc/cache.cc Sun May 30 02:53:57 2010
@@ -74,14 +74,14 @@
HotCache::~HotCache() {
CacheNodePtr node;
- for (node = head; node = node->next; node != CacheNodePtr()) {
- head = node->next;
- if (head) {
- head->prev = CacheNodePtr();
+ for (node = lru_head_; node = node->next; node != CacheNodePtr()) {
+ lru_head_ = node->next;
+ if (lru_head_) {
+ lru_head_->prev = CacheNodePtr();
}
}
- head = tail = CacheNodePtr();
+ lru_head_ = lru_tail_ = CacheNodePtr();
}
@@ -103,21 +103,21 @@
inline void
HotCache::insert(const CacheNodePtr node) {
- if (head) {
- node->next = head;
- head->prev = node;
- head = node;
+ if (lru_head_) {
+ node->next = lru_head_;
+ lru_head_->prev = node;
+ lru_head_ = node;
} else {
- node->next = head;
- head = node;
- tail = node;
+ node->next = lru_head_;
+ lru_head_ = node;
+ lru_tail_ = node;
}
map_[QTuple(node->qname, node->qclass, node->qtype)] = node;
++count_;
- while (slots_ != 0 && count_ > slots_ && tail) {
- remove(tail);
+ while (slots_ != 0 && count_ > slots_ && lru_tail_) {
+ remove(lru_tail_);
}
}
@@ -155,8 +155,8 @@
HotCache::setSlots(int slots) {
slots_ = slots;
- while (slots_ != 0 && count_ > slots_ && tail) {
- remove(tail);
+ while (slots_ != 0 && count_ > slots_ && lru_tail_) {
+ remove(lru_tail_);
}
}
@@ -174,7 +174,7 @@
void
HotCache::promote(CacheNodePtr node) {
- if (!node || node == head) {
+ if (!node || node == lru_head_) {
return;
}
@@ -186,15 +186,15 @@
node->next->prev = node->prev;
}
- if (node == tail) {
- tail = node->prev;
- tail->next = CacheNodePtr();
- }
-
- head->prev = node;
+ if (node == lru_tail_) {
+ lru_tail_ = node->prev;
+ lru_tail_->next = CacheNodePtr();
+ }
+
+ lru_head_->prev = node;
node->prev = CacheNodePtr();
- node->next = head;
- head = node;
+ node->next = lru_head_;
+ lru_head_ = node;
}
void
@@ -203,12 +203,12 @@
return;
}
- if (node == head) {
- head = node->next;
- }
-
- if (node == tail) {
- tail = node->prev;
+ if (node == lru_head_) {
+ lru_head_ = node->next;
+ }
+
+ if (node == lru_tail_) {
+ lru_tail_ = node->prev;
}
if (node->next) {
Modified: branches/trac192/src/lib/datasrc/cache.h
==============================================================================
--- branches/trac192/src/lib/datasrc/cache.h (original)
+++ branches/trac192/src/lib/datasrc/cache.h Sun May 30 02:53:57 2010
@@ -36,34 +36,70 @@
class CacheEntry;
typedef boost::shared_ptr<CacheEntry> CacheEntryPtr;
+/// \brief A \c CacheEntry object contains a pointer to an RRset,
+/// and the query-response flags that were returned when the RRset
+/// was originally looked up in the low-level data source.
class CacheEntry {
public:
isc::dns::RRsetPtr rrset;
uint32_t flags;
};
-// A node in the data cache; keyed by qname/qclass/qtype, contains a
-// pointer to a single RRset.
+/// \brief A \c CacheNode is a node in the \c HotCache.
class CacheNode {
public:
- // Constructors
+ /// \name Constructors and Destructor
+ //@{
+ /// \brief Constructor for positive cache entry.
+ ///
+ /// \param rrset The \c RRset to cache.
+ /// \param flags The query response flags returned from the low-level
+ /// data source when this \c RRset was looked up.
+ /// \param interval How long the cache node is to be considered valid.
CacheNode(const isc::dns::RRsetPtr rrset,
const uint32_t flags,
time_t interval);
+
+ /// \brief Constructor for negative cache entry.
+ ///
+ /// \param name Query name
+ /// \param rrclass Query class
+ /// \param rrtype Query type
+ /// \param flags Query response flags returned from the low-level
+ /// data source, indicating why this lookup failed (name not found,
+ /// type not found, etc).
+ /// \param interval How long the cache node is to be considered valid.
CacheNode(const isc::dns::Name& name,
const isc::dns::RRClass& rrclass,
const isc::dns::RRType& rrtype,
const uint32_t flags,
const time_t interval);
- // Destructor
+ // \brief Destructor
~CacheNode();
-
+ //@}
+
+ /// \name Getter and Setter Methods
+ //@{
+ /// \brief Returns a pointer to the cached RRset (or an empty
+ /// RRsetPtr for negative cache entries).
+
+ /// \return \c RRsetPtr
isc::dns::RRsetPtr getRRset() const { return (entry_->rrset); }
+
+ /// \brief Returns the query response flags associated with the data.
+ ///
+ /// \return \c uint32_t
uint32_t getFlags() const { return (entry_->flags); }
+
+ /// \brief Is this record still valid?
+ ///
+ /// \return True if the expiration time has not yet passed,
+ /// or false if it has.
bool isValid() const;
-
- // List pointers
+ //@}
+
+ // Links to next and previous nodes in the LRU list.
CacheNodePtr prev;
CacheNodePtr next;
@@ -81,6 +117,13 @@
time_t expiry_;
};
+/// \brief A \c QTuple is a simple object containing the standard query
+/// tuple: {name, class, type}.
+///
+/// Its purpose is to act as the key data format for the \c std::map
+/// in the \c HotCache class.
+///
+/// (Possible TODO item: using this in other parts of libdatasrc as well.)
class QTuple {
public:
QTuple(isc::dns::Name n, isc::dns::RRClass c, isc::dns::RRType t);
@@ -96,51 +139,131 @@
isc::dns::RRType qtype;
};
+/// \brief A \c HotCache is a hot-spot cache for one or more data sources.
+///
+/// A \c HotCache is instantiated as a static member of class \c Query, so
+/// that all instances of \c Query can use the same cache.
+///
+/// Each time <code>DataSrc::doQueryTask()</code> is called, it will
+/// search the hot-spot cache for records matching the query. If a
+/// matching entry is found, and is still within its lifespan, it will
+/// be returned to the calling function.
+///
+/// When the requested data is not found in the cache, or is found but
+/// has expired, it will be looked up in the underlying data source.
+/// If found there, it will be cached with a lifespan currently defaulting
+/// to 30 seconds.
+///
+/// Each node inserted into the cache is placed at the head of a
+/// doubly-linked list; whenever that node is retrieved from the cache,
+/// it is again moved to the head of the list. When the configured
+/// number of slots in the cache has been exceeded, the least recently
+/// used nodes will be removed from the tail of the list.
+///
+/// A pointer to each cache node is also placed in a \c std::map object,
+/// keyed by \c QTuple. This allows retrieval of data in (usually)
+/// logarithmic time. (Possible TODO item: replace this with a hash
+/// table instead.)
class HotCache {
public:
- // Constructor
- // If slots is zero, we don't limit the size of the LRU queue.
+ /// \name Constructor and Destructor
+ //@{
+ /// \brief Constructor
+ ///
+ /// \param slots The number of slots. If zero, the cache is unlimited.
HotCache(int slots = 0) : slots_(slots), count_(0) {}
- // Destructor
+ // \brief Destructor
~HotCache();
-
- // Retrieve a record from the cache
- CacheNodePtr retrieve(isc::dns::Name qname,
- isc::dns::RRClass qclass,
- isc::dns::RRType qtype);
-
- // Positively cache an RRset
+ //@}
+
+ /// \name Cache Manipulation Methods
+ //@{
+ /// \brief Enter a positive cache entry.
+ ///
+ /// \param rrset The \c RRset to cache.
+ /// \param flags The query response flags returned from the low-level
+ /// data source when this \c RRset was looked up.
+ /// \param interval How long the cache node is to be considered valid;
+ /// defaulting to 30 seconds.
void cache(isc::dns::RRsetPtr rrset,
const uint32_t flags,
const time_t interval = 30);
- // Negatively cache a name/class/type tuple
+ /// \brief Enter a negative cache entry.
+ ///
+ /// In the case of a negative cache entry there is no \c RRset to
+ /// cache, so instead a null \c RRsetPtr will be stored. Since the
+ /// name, class, and type cannot be retrieved from an \c RRset, they
+ /// must be specified in the parameters.
+ ///
+ /// \param name Query name
+ /// \param rrclass Query class
+ /// \param rrtype Query type
+ /// \param flags Query response flags returned from the low-level
+ /// data source, indicating why this lookup failed (name not found,
+ /// type not found, etc).
+ /// \param interval How long the cache node is to be considered valid;
+ /// defaulting to 30 seconds.
void ncache(const isc::dns::Name& name,
const isc::dns::RRClass& rrclass,
const isc::dns::RRType& rrtype,
const uint32_t flags,
const time_t interval = 30);
+ /// \brief Retrieve a record from the cache
+ ///
+ /// \param name The query name
+ /// \param rrclass The query class
+ /// \param rrtype The query type
+ ///
+ /// \return \c CacheNodePtr, empty if no data was found in the cache.
+ CacheNodePtr retrieve(isc::dns::Name qname,
+ isc::dns::RRClass qclass,
+ isc::dns::RRType qtype);
+ //@}
+
+
+ /// \name Getter and Setter Methods
+ //@{
+ /// \brief Sets the number of slots in the cache.
+ ///
+ /// If slots is set to zero, the cache can grow without any imposed
+ /// limit, up to the number of RRsets in the data source. If slots
+ /// is set to a lower number than previous (but not to zero), and
+ /// the number of nodes currently in the cache exceeds the new
+ /// value of slots, then the oldest records in the LRU queue will
+ /// be removed immediately.
void setSlots(int slots);
+
+ /// \brief Returns the number of slots in the cache.
int getSlots() const;
+
+ /// \brief Returns the number of nodes currently stored in the cache.
+ ///
+ /// Note that this doesn't indicate how many nodes are still valid;
+ /// some may have expired.
int getCount() const;
-
- // Pointers to the doubly-linked list of cache nodes
- CacheNodePtr head;
- CacheNodePtr tail;
+ //@}
private:
+ // Pointers to the head and tail of the LRU list.
+ CacheNodePtr lru_head_;
+ CacheNodePtr lru_tail_;
+
int slots_;
int count_;
+ // Map from query tuple to cache node pointer, allowing faster retrieval
std::map<QTuple, CacheNodePtr> map_;
// Move a node to the front of the LRU queue.
void promote(CacheNodePtr node);
+
+ // Remove a node from the cache.
void remove(CacheNodePtr node);
- // Insert a node (used by both cache() and ncache())
+ // Insert a node into the cache (called by both cache() and ncache())
inline void insert(const CacheNodePtr node);
};
Modified: branches/trac192/src/lib/datasrc/data_source.h
==============================================================================
--- branches/trac192/src/lib/datasrc/data_source.h (original)
+++ branches/trac192/src/lib/datasrc/data_source.h Sun May 30 02:53:57 2010
@@ -297,21 +297,48 @@
std::vector<ConstDataSrcPtr> data_sources;
};
+/// \brief Information about the zone for a given query
+///
+/// The \c NameMatch object is created with the query name and query
+/// class (and optionally, query type) for an ongoing query, and the
+/// top-level data source. When it becomes necessary to find the
+/// closest enclosing zone matching the query and the concrete data
+/// source which is authoritative for that zone, then the \c NameMatch
+/// object will search through data sources to make that determination.
+/// (This is done only when needed, so that the search can be avoided
+/// when the query can be answered from the cache.)
class NameMatch {
///
/// \name Constructors, Assignment Operator and Destructor.
///
/// Note: The copy constructor and the assignment operator are intentionally
/// defined as private.
+ //@{
private:
NameMatch(const NameMatch& source);
NameMatch& operator=(const NameMatch& source);
public:
+ /// \brief Constructor suitable for most typical queries
+ ///
+ /// \param ds Pointer to the top-level data source
+ /// \param qname Query name
+ /// \param qclass Query class
NameMatch(const DataSrc* ds, const isc::dns::Name& qname,
const isc::dns::RRClass& qclass) :
top_source_(ds), closest_name_(NULL), best_source_(NULL),
- qname_(qname), qclass_(qclass), qtype_(isc::dns::RRType::ANY())
- {}
+ qname_(qname), qclass_(qclass), qtype_(isc::dns::RRType::ANY()) {}
+
+ /// \brief Constructor for queries that specify RRtype
+ ///
+ /// Queries for the DS rrtype must be sent to the parent zone, not
+ /// to the zone matching the query name. Therefore, if a query type of
+ /// DS is specified here, the query name is altered, so that when
+ /// we search for the closest enclosing zone, we'll find the right one.
+ ///
+ /// \param ds Pointer to the top-level data source
+ /// \param qname Query name
+ /// \param qclass Query class
+ /// \param qtype Query type
NameMatch(const DataSrc* ds, const isc::dns::Name& qname,
const isc::dns::RRClass& qclass, const isc::dns::RRType& qtype) :
top_source_(ds), closest_name_(NULL), best_source_(NULL),
@@ -323,12 +350,20 @@
~NameMatch();
//@}
- void update(const DataSrc& new_source, const isc::dns::Name& container);
-
+ /// \name Getter and Setter Methods
+ //@{
+ /// \brief Returns the query name.
const isc::dns::Name& qname() const { return (qname_); }
+
+ /// \brief Returns the query class.
const isc::dns::RRClass& qclass() const { return (qclass_); }
- const isc::dns::RRType& qtype() const { return (qtype_); }
-
+
+ /// \brief Returns the enclosing zone name for the query.
+ ///
+ /// If the enclosing zone has not yet been found, search the
+ /// data source for it.
+ ///
+ /// \return A pointer to the zone apex \c Name
isc::dns::Name* name() {
if (!closest_name_) {
top_source_->findClosestEnclosure(*this);
@@ -336,12 +371,24 @@
return (closest_name_);
}
+ /// \brief Returns the concrete data source serving the zone.
+ ///
+ /// If the concrete data source has not yet been found, search
+ /// down from the top-level data source for it.
+ ///
+ /// \return A pointer to the concrete data source.
const DataSrc* datasrc() {
if (!best_source_) {
top_source_->findClosestEnclosure(*this);
}
return (best_source_);
}
+ //@}
+
+ /// \brief Called by a concrete data source's
+ /// <code>findClosestEnclosure()</code> routine to store the
+ /// best match for the query that has found so far.
+ void update(const DataSrc& new_source, const isc::dns::Name& container);
private:
const DataSrc* top_source_;
Modified: branches/trac192/src/lib/datasrc/query.h
==============================================================================
--- branches/trac192/src/lib/datasrc/query.h (original)
+++ branches/trac192/src/lib/datasrc/query.h Sun May 30 02:53:57 2010
@@ -46,7 +46,7 @@
// XXX: Members are currently public, but should probably be
// moved to private and wrapped in get() functions later.
- // The Query that this task is part of.
+ // The \c Query that this \c QueryTask was created to service.
const Query& q;
// The standard query tuple: qname/qclass/qtype.
@@ -218,8 +218,8 @@
void setDatasrc(DataSrc* ds) { datasrc_ = ds; }
DataSrc* datasrc() const { return datasrc_; }
- // Query cache. This is static; the same cache will be
- // used by all instances of Query.
+ // \brief The query cache. This is a static member of class \c Query;
+ // the same cache will be used by all instances.
static HotCache cache;
private:
More information about the bind10-changes
mailing list