[svn] commit: r3764 - in /branches/trac408: ./ src/lib/nsas/
BIND 10 source code commits
bind10-changes at lists.isc.org
Wed Dec 8 11:34:53 UTC 2010
Author: vorner
Date: Wed Dec 8 11:34:52 2010
New Revision: 3764
Log:
Hmm, subversion works locally to subdir. Commit the rest of the tree as well
Added:
branches/trac408/src/lib/nsas/random_number_generator.h
- copied unchanged from r3761, branches/trac356/src/lib/nsas/random_number_generator.h
Modified:
branches/trac408/ (props changed)
branches/trac408/src/lib/nsas/address_entry.h
branches/trac408/src/lib/nsas/hash_deleter.h
branches/trac408/src/lib/nsas/hash_table.h
branches/trac408/src/lib/nsas/lru_list.h
branches/trac408/src/lib/nsas/nameserver_address.h
branches/trac408/src/lib/nsas/nameserver_entry.cc
branches/trac408/src/lib/nsas/nameserver_entry.h
branches/trac408/src/lib/nsas/nsas_entry.h
branches/trac408/src/lib/nsas/zone_entry.h
Modified: branches/trac408/src/lib/nsas/address_entry.h
==============================================================================
--- branches/trac408/src/lib/nsas/address_entry.h (original)
+++ branches/trac408/src/lib/nsas/address_entry.h Wed Dec 8 11:34:52 2010
@@ -37,7 +37,7 @@
/// \param address Address object representing this address
/// \param rtt Initial round-trip time
AddressEntry(const asiolink::IOAddress& address, uint32_t rtt = 0) :
- address_(address), rtt_(rtt)
+ address_(address), rtt_(rtt), dead_until_(0)
{}
/// \return Address object
@@ -46,7 +46,12 @@
}
/// \return Current round-trip time
- uint32_t getRTT() const {
+ uint32_t getRTT() {
+ if(dead_until_ != 0 && time(NULL) >= dead_until_){
+ dead_until_ = 0;
+ rtt_ = 1; //reset the rtt to a small value so it has an opportunity to be updated
+ }
+
return rtt_;
}
@@ -54,7 +59,11 @@
///
/// \param rtt New RTT to be associated with this address
void setRTT(uint32_t rtt) {
- rtt_ = rtt; // TODO: Modify to use weighting formula
+ if(rtt == UNREACHABLE){
+ dead_until_ = time(NULL) + 5*60;//Cache the unreachable server for 5 minutes (RFC2308 sec7.2)
+ }
+
+ rtt_ = rtt;
}
/// Mark address as unreachable.
@@ -65,8 +74,8 @@
/// Check if address is unreachable
///
/// \return true if the address is unreachable, false if not
- bool isUnreachable() const {
- return (rtt_ == UNREACHABLE);
+ bool isUnreachable() {
+ return (getRTT() == UNREACHABLE); // The getRTT() will check the cache time for unreachable server
}
/// \return true if the object is a V4 address
@@ -85,6 +94,7 @@
private:
asiolink::IOAddress address_; ///< Address
uint32_t rtt_; ///< Round-trip time
+ time_t dead_until_; ///< Dead time for unreachable server
};
} // namespace dns
Modified: branches/trac408/src/lib/nsas/hash_deleter.h
==============================================================================
--- branches/trac408/src/lib/nsas/hash_deleter.h (original)
+++ branches/trac408/src/lib/nsas/hash_deleter.h Wed Dec 8 11:34:52 2010
@@ -46,6 +46,10 @@
HashDeleter(HashTable<T>& hashtable) : hashtable_(hashtable)
{}
+ /// \brief Destructor
+ ///
+ virtual ~HashDeleter(){}
+
// The default copy constructor and assignment operator are correct for
// this object.
Modified: branches/trac408/src/lib/nsas/hash_table.h
==============================================================================
--- branches/trac408/src/lib/nsas/hash_table.h (original)
+++ branches/trac408/src/lib/nsas/hash_table.h Wed Dec 8 11:34:52 2010
@@ -89,6 +89,11 @@
template <typename T>
class HashTableCompare {
public:
+ /// \brief Constructor
+ HashTableCompare(){}
+
+ /// \brief virtual Destructor
+ virtual ~HashTableCompare() {}
/// \brief Comparison Function
///
@@ -100,8 +105,6 @@
///
/// \return bool true of the name of the object is equal to the name given.
virtual bool operator()(T* object, const HashKey& key) const = 0;
- /// \brief Virtual destructor
- virtual ~ HashTableCompare() { }
};
@@ -145,6 +148,10 @@
/// prime although that is not checked. The default value is the size used
/// in BIND-9 for its address database.
HashTable(HashTableCompare<T>* cmp, uint32_t size = 1009);
+
+ /// \brief Destructor
+ ///
+ virtual ~HashTable(){}
/// \brief Get Entry
///
Modified: branches/trac408/src/lib/nsas/lru_list.h
==============================================================================
--- branches/trac408/src/lib/nsas/lru_list.h (original)
+++ branches/trac408/src/lib/nsas/lru_list.h Wed Dec 8 11:34:52 2010
@@ -58,6 +58,11 @@
/// will handle any additional operations needed.
class Dropped {
public:
+ /// \brief Constructor
+ Dropped(){}
+
+ /// \brief Virtual Destructor
+ virtual ~Dropped(){}
/// \brief Dropped Object Handler
///
@@ -66,8 +71,6 @@
///
/// \param drop Object being dropped.
virtual void operator()(T* drop) const = 0;
- /// \brief Virtual destructor
- virtual ~ Dropped() { }
};
/// \brief Constructor
Modified: branches/trac408/src/lib/nsas/nameserver_address.h
==============================================================================
--- branches/trac408/src/lib/nsas/nameserver_address.h (original)
+++ branches/trac408/src/lib/nsas/nameserver_address.h Wed Dec 8 11:34:52 2010
@@ -25,6 +25,17 @@
namespace isc {
namespace nsas {
+/// \brief Empty \c NameserverEntry pointer exception
+///
+/// Thrown if the the \c NameservrEntry pointer in the \c boost::shared_ptr that passed
+/// into \c NameserverAddress' constructor is NULL
+class NullNameserverEntryPointer : public isc::Exception {
+public:
+ NullNameserverEntryPointer(const char* file, size_t line, const char* what) :
+ isc::Exception(file, line, what)
+ {}
+};
+
/// \brief Nameserver Address
///
/// This class implements the object that returned from NSAS when the resolver
@@ -45,8 +56,18 @@
/// the shared_ptr can avoid the NameserverEntry object being dropped while the
/// request is processing.
/// \param index The address's index in NameserverEntry's addresses vector
- NameserverAddress(boost::shared_ptr<NameserverEntry>& nameserver, uint32_t index):
- ns_(nameserver), index_(index)
+ /// \param family Address family, AF_INET or AF_INET6
+ NameserverAddress(boost::shared_ptr<NameserverEntry>& nameserver, uint32_t index, short family):
+ ns_(nameserver), index_(index), family_(family)
+ {
+ if(!ns_.get()) {
+ isc_throw(NullNameserverEntryPointer, "NULL NameserverEntry pointer.");
+ }
+ }
+
+ /// \brief Default Constructor
+ ///
+ NameserverAddress(): index_(0), family_(AF_INET)
{
}
@@ -54,14 +75,13 @@
///
/// Empty destructor.
~NameserverAddress()
- {}
+ {
+ }
/// \brief Return address
///
asiolink::IOAddress getAddress() const {
- NameserverEntry *ne = ns_.get();
- assert(ne != NULL);
- return ne->getAddressAtIndex(index_);
+ return ns_.get()->getAddressAtIndex(index_, family_);
}
/// \brief Update Round-trip Time
@@ -70,17 +90,13 @@
/// update the address's RTT.
/// \param rtt The new Round-Trip Time
void updateRTT(uint32_t rtt) {
- NameserverEntry* ne = ns_.get();
- if(ne) ne->updateAddressRTTAtIndex(rtt, index_);
+ ns_.get()->updateAddressRTTAtIndex(rtt, index_, family_);
}
private:
- /// \brief Default Constructor
- ///
- /// A private default constructor to avoid creating an empty object.
- NameserverAddress();
boost::shared_ptr<NameserverEntry> ns_; ///< Shared-pointer to NameserverEntry object
uint32_t index_; ///< The address index in NameserverEntry
+ short family_; ///< Address family AF_INET or AF_INET6
};
} // namespace nsas
Modified: branches/trac408/src/lib/nsas/nameserver_entry.cc
==============================================================================
--- branches/trac408/src/lib/nsas/nameserver_entry.cc (original)
+++ branches/trac408/src/lib/nsas/nameserver_entry.cc Wed Dec 8 11:34:52 2010
@@ -33,6 +33,7 @@
#include <dns/question.h>
#include "address_entry.h"
+#include "nameserver_address.h"
#include "nameserver_entry.h"
#include "resolver_interface.h"
@@ -78,6 +79,9 @@
if (getState() == EXPIRED && !expired_ok) {
return EXPIRED;
+
+ // Update the address selector
+ updateAddressSelector(v4_addresses_, v4_address_selector_);
}
switch (getState()) {
@@ -116,6 +120,9 @@
remove_copy_if(address_.begin(), address_.end(),
back_inserter(addresses), boost::bind(addressSelection, s_family,
_1));
+
+ // Update the address selector
+ updateAddressSelector(v6_addresses_, v6_address_selector_);
}
if (getState() == EXPIRED && expired_ok) {
return READY;
@@ -123,13 +130,41 @@
return getState();
}
-asiolink::IOAddress
-NameserverEntry::getAddressAtIndex(uint32_t index) const {
- Lock lock(mutex_);
-
- assert(index < address_.size());
-
- return address_[index].getAddress();
+// Return one address matching the given family
+bool NameserverEntry::getAddress(NameserverAddress& address, short family)
+{
+ Lock lock(mutex_);
+
+// TODO Change to AddressFamily
+ // Get the shared_ptr object that point to "this" object
+ shared_ptr<NameserverEntry> shared_ptr_to_this = shared_from_this();
+
+ if(family == AF_INET){
+ if(v4_addresses_.size() == 0) return false;
+
+ address = NameserverAddress(shared_ptr_to_this, v4_address_selector_(), AF_INET);
+ return true;
+ } else if(family == AF_INET6){
+ if(v6_addresses_.size() == 0) return false;
+
+ //address = NameserverAddress(shared_from_this(), v6_address_selector_(), AF_INET6);
+ return true;
+ }
+ return false;
+}
+
+// Return the address corresponding to the family
+asiolink::IOAddress NameserverEntry::getAddressAtIndex(uint32_t index, short family) const
+{
+ Lock lock(mutex_);
+
+ const vector<AddressEntry> *addresses = &v4_addresses_;
+ if(family == AF_INET6){
+ addresses = &v6_addresses_;
+ }
+ assert(index < addresses->size());
+
+ return (*addresses)[index].getAddress();
}
// Set the address RTT to a specific value
@@ -138,23 +173,55 @@
Lock lock(mutex_);
// Search through the list of addresses for a match
- for (AddressVectorIterator i = address_.begin(); i != address_.end(); ++i) {
+ for (AddressVectorIterator i = v4_addresses_.begin(); i != v4_addresses_.end(); ++i) {
if (i->getAddress().equal(address)) {
i->setRTT(rtt);
+
+ // Update the selector
+ updateAddressSelector(v4_addresses_, v4_address_selector_);
+ return;
+ }
+ }
+
+ // Search the v6 list
+ for (AddressVectorIterator i = v6_addresses_.begin(); i != v6_addresses_.end(); ++i) {
+ if (i->getAddress().equal(address)) {
+ i->setRTT(rtt);
+
+ // Update the selector
+ updateAddressSelector(v6_addresses_, v6_address_selector_);
+ return;
}
}
}
// Update the address's rtt
-void
-NameserverEntry::updateAddressRTTAtIndex(uint32_t rtt, uint32_t index) {
- Lock lock(mutex_);
+#define UPDATE_RTT_ALPHA 0.7
+void NameserverEntry::updateAddressRTTAtIndex(uint32_t rtt, uint32_t index, short family) {
+ Lock lock(mutex_);
+
+ vector<AddressEntry>* addresses = &v4_addresses_;
+ if(family == AF_INET6){
+ addresses = &v6_addresses_;
+ }
//make sure it is a valid index
- if(index >= address_.size()) return;
-
- //update the rtt
- address_[index].setRTT(rtt);
+ if(index >= addresses->size()) return;
+
+ // Smoothly update the rtt
+ // The algorithm is as the same as bind8/bind9:
+ // new_rtt = old_rtt * alpha + new_rtt * (1 - alpha), where alpha is a float number in [0, 1.0]
+ // The default value for alpha is 0.7
+ uint32_t old_rtt = (*addresses)[index].getRTT();
+ uint32_t new_rtt = (int)(old_rtt * UPDATE_RTT_ALPHA + rtt * (1 - UPDATE_RTT_ALPHA));
+ (*addresses)[index].setRTT(new_rtt);
+
+ // Update the selector
+ if(family == AF_INET) {
+ updateAddressSelector(v4_addresses_, v4_address_selector_);
+ } else if(family == AF_INET6) {
+ updateAddressSelector(v6_addresses_, v6_address_selector_);
+ }
}
// Sets the address to be unreachable
@@ -169,6 +236,7 @@
* pointer to the entry so it is not destroyed too soon.
*/
class NameserverEntry::ResolverCallback : public ResolverInterface::Callback {
+ // TODO This needs to bring in some changes from the constructor
public:
ResolverCallback(shared_ptr<NameserverEntry> entry,
AddressFamily family, const RRType& type) :
@@ -199,8 +267,7 @@
// Try to find the original value and reuse its rtt
string address(i->getCurrent().toText());
int curr_rtt(-1);
- BOOST_FOREACH(const AddressEntry& entry,
- entry_->previous_addresses_)
+ BOOST_FOREACH(AddressEntry& entry, entry_->previous_addresses_)
{
if (entry.getAddress().toText() == address) {
curr_rtt = entry.getRTT();
@@ -372,5 +439,50 @@
}
}
+// Update the address selector according to the RTTs
+//
+// Each address has a probability to be selected if multiple addresses are available
+// The weight factor is equal to 1/(rtt*rtt), then all the weight factors are normalized
+// to make the sum equal to 1.0
+void NameserverEntry::updateAddressSelector(std::vector<AddressEntry>& addresses,
+ WeightedRandomIntegerGenerator& selector)
+{
+ Lock lock(mutex_);
+
+ vector<double> probabilities;
+ for(vector<AddressEntry>::iterator it = addresses.begin();
+ it != addresses.end(); ++it){
+ uint32_t rtt = (*it).getRTT();
+ if(rtt == 0) {
+ isc_throw(RTTIsZero, "The RTT is 0");
+ }
+
+ if(rtt == AddressEntry::UNREACHABLE) {
+ probabilities.push_back(0);
+ } else {
+ probabilities.push_back(1.0/(rtt*rtt));
+ }
+ }
+ // Calculate the sum
+ double sum = accumulate(probabilities.begin(), probabilities.end(), 0.0);
+
+ if(sum != 0) {
+ // Normalize the probabilities to make the sum equal to 1.0
+ for(vector<double>::iterator it = probabilities.begin();
+ it != probabilities.end(); ++it){
+ (*it) /= sum;
+ }
+ } else if(probabilities.size() > 0){
+ // If all the nameservers are unreachable, the sum will be 0
+ // So give each server equal opportunity to be selected.
+ for(vector<double>::iterator it = probabilities.begin();
+ it != probabilities.end(); ++it){
+ (*it) = 1.0/probabilities.size();
+ }
+ }
+
+ selector.reset(probabilities);
+}
+
} // namespace dns
} // namespace isc
Modified: branches/trac408/src/lib/nsas/nameserver_entry.h
==============================================================================
--- branches/trac408/src/lib/nsas/nameserver_entry.h (original)
+++ branches/trac408/src/lib/nsas/nameserver_entry.h Wed Dec 8 11:34:52 2010
@@ -28,15 +28,18 @@
#include "address_entry.h"
#include "asiolink.h"
-#include "nsas_entry.h"
#include "nsas_types.h"
#include "hash_key.h"
#include "lru_list.h"
#include "fetchable.h"
#include "resolver_interface.h"
+#include "nsas_entry.h"
+#include "random_number_generator.h"
namespace isc {
namespace nsas {
+
+class NameserverAddress;
/// \brief Inconsistent Owner Names
///
@@ -45,6 +48,16 @@
class InconsistentOwnerNames : public Exception {
public:
InconsistentOwnerNames(const char* file, size_t line, const char* what) :
+ isc::Exception(file, line, what)
+ {}
+};
+
+/// \brief RTT is zero
+///
+/// Thrown if a RTT related with an address is 0.
+class RTTIsZero : public Exception {
+public:
+ RTTIsZero(const char* file, size_t line, const char* what) :
isc::Exception(file, line, what)
{}
};
@@ -87,9 +100,7 @@
///
/// It uses shared_from_this in its methods. It must live inside a shared_ptr.
-class NameserverEntry : public NsasEntry<NameserverEntry>, public Fetchable,
- public boost::enable_shared_from_this<NameserverEntry>
-{
+class NameserverEntry : public NsasEntry<NameserverEntry>, public Fetchable {
public:
/// List of addresses associated with this nameserver
typedef std::vector<AddressEntry> AddressVector;
@@ -130,11 +141,19 @@
NameserverEntry::AddressVector& addresses,
AddressFamily family = ANY_OK, bool expired_ok = false);
- // TODO Is this one of any use at all?
+ /// \brief Return one address
+ ///
+ /// Return one address corresponding to this nameserver
+ /// \param address NameserverAddress object used to receive the address
+ /// \param family The family of user request, AF_INET or AF_INET6
+ /// \return true if one address is found, false otherwise
+ virtual bool getAddress(NameserverAddress& address, short family);
+
/// \brief Return Address that corresponding to the index
///
/// \param index The address index in the address vector
- asiolink::IOAddress getAddressAtIndex(uint32_t index) const;
+ /// \param family The address family, AF_INET or AF_INET6
+ asiolink::IOAddress getAddressAtIndex(uint32_t index, short family) const;
/// \brief Update RTT
///
@@ -148,7 +167,8 @@
///
/// \param rtt Round-Trip Time
/// \param index The address's index in address vector
- void updateAddressRTTAtIndex(uint32_t rtt, uint32_t index);
+ /// \param family The address family, AF_INET or AF_INET6
+ void updateAddressRTTAtIndex(uint32_t rtt, uint32_t index, short family);
/// \brief Set Address Unreachable
///
@@ -241,6 +261,18 @@
/// Call unlocked.
void askIP(boost::shared_ptr<ResolverInterface> resolver,
const isc::dns::RRType&, AddressFamily);
+ /// \brief Update the address selector according to the RTTs of addresses
+ ///
+ /// \param addresses The address list
+ /// \param selector Weighted random generator
+ void updateAddressSelector(std::vector<AddressEntry>& addresses,
+ WeightedRandomIntegerGenerator& selector);
+
+ // TODO Unite address_ and v?_addresses_
+ std::vector<AddressEntry> v4_addresses_; ///< Set of V4 addresses
+ std::vector<AddressEntry> v6_addresses_; ///< Set of V6 addresses
+ WeightedRandomIntegerGenerator v4_address_selector_; ///< Generate one integer according to different probability
+ WeightedRandomIntegerGenerator v6_address_selector_; ///< Generate one integer according to different probability
};
} // namespace dns
Modified: branches/trac408/src/lib/nsas/nsas_entry.h
==============================================================================
--- branches/trac408/src/lib/nsas/nsas_entry.h (original)
+++ branches/trac408/src/lib/nsas/nsas_entry.h Wed Dec 8 11:34:52 2010
@@ -17,6 +17,7 @@
#ifndef __NSAS_ENTRY_H
#define __NSAS_ENTRY_H
+#include <boost/enable_shared_from_this.hpp>
#include <iostream>
#include <exceptions/exceptions.h>
@@ -38,7 +39,6 @@
Exception(file, line, what)
{}
};
-
/// \brief Element of NSAS Internal Lists
///
@@ -64,9 +64,11 @@
/// pointers, but a shared pointer to a base class is not a subclass of a
/// shared pointer to a derived class. For this reason, the type of element
/// being stored is a template parameter.
-
+///
+/// This class is inherited from boost::enable_shared_from_this class
+/// So within a member function a shared_ptr to current object can be obtained
template <typename T>
-class NsasEntry {
+class NsasEntry : public boost::enable_shared_from_this <T> {
public:
/// \brief Default Constructor
Modified: branches/trac408/src/lib/nsas/zone_entry.h
==============================================================================
--- branches/trac408/src/lib/nsas/zone_entry.h (original)
+++ branches/trac408/src/lib/nsas/zone_entry.h Wed Dec 8 11:34:52 2010
@@ -50,9 +50,7 @@
///
/// It uses shared_from_this in its methods. It must live inside a shared_ptr.
-class ZoneEntry : public NsasEntry<ZoneEntry>, public Fetchable,
- public boost::enable_shared_from_this<ZoneEntry>
-{
+class ZoneEntry : public NsasEntry<ZoneEntry>, public Fetchable {
public:
/**
More information about the bind10-changes
mailing list