diff options
52 files changed, 7594 insertions, 22 deletions
@@ -12,6 +12,17 @@ It has "listen_on" and "forward_addresses" options. (Trac #389, r3448) + 127. [bug] stephen + During normal operation process termination and resurrection messages + are now output regardless of the state of the verbose flag. + (Trac #229, svn r3828) + + 126. [func] stephen, vorner, ocean + The Nameserver Address Store (NSAS) component has been added. It takes + care of choosing an IP address of a nameserver when a zone needs to be + contacted. + (Trac #356, Trac #408, svn r3823) + bind10-devel-20101201 released on December 01, 2010 125. [func] jelte diff --git a/configure.ac b/configure.ac index d0f47a7e3a..b555039b04 100644 --- a/configure.ac +++ b/configure.ac @@ -318,7 +318,7 @@ if test "${boost_include_path}" ; then BOOST_INCLUDES="-I${boost_include_path}" CPPFLAGS="$CPPFLAGS $BOOST_INCLUDES" fi -AC_CHECK_HEADERS([boost/shared_ptr.hpp boost/foreach.hpp],, +AC_CHECK_HEADERS([boost/shared_ptr.hpp boost/foreach.hpp boost/interprocess/sync/interprocess_upgradable_mutex.hpp],, AC_MSG_ERROR([Missing required header files.])) CPPFLAGS="$CPPFLAGS_SAVES" AC_SUBST(BOOST_INCLUDES) @@ -523,6 +523,8 @@ AC_CONFIG_FILES([Makefile src/lib/log/Makefile src/lib/testutils/Makefile src/lib/testutils/testdata/Makefile + src/lib/nsas/Makefile + src/lib/nsas/tests/Makefile ]) AC_OUTPUT([src/bin/cfgmgr/b10-cfgmgr.py src/bin/cfgmgr/tests/b10-cfgmgr_test.py diff --git a/doc/Doxyfile b/doc/Doxyfile index 9aa4a4281d..0e1ab00d0f 100644 --- a/doc/Doxyfile +++ b/doc/Doxyfile @@ -568,7 +568,7 @@ WARN_LOGFILE = # directories like "/usr/src/myproject". Separate the files or directories # with spaces. -INPUT = ../src/lib/cc ../src/lib/config ../src/lib/dns ../src/lib/exceptions ../src/lib/datasrc ../src/bin/auth ../src/lib/bench ../src/lib/log ../src/lib/asiolink/ +INPUT = ../src/lib/cc ../src/lib/config ../src/lib/dns ../src/lib/exceptions ../src/lib/datasrc ../src/bin/auth ../src/lib/bench ../src/lib/log ../src/lib/asiolink/ ../src/lib/nsas # This tag can be used to specify the character encoding of the source files # that doxygen parses. Internally doxygen uses the UTF-8 encoding, which is diff --git a/doc/guide/bind10-guide.html b/doc/guide/bind10-guide.html index e82dc4a491..b2c132ecf2 100644 --- a/doc/guide/bind10-guide.html +++ b/doc/guide/bind10-guide.html @@ -128,7 +128,7 @@ libraries, to build BIND 10 from source code. </p></div><p> Building from source code requires the Boost - build-time headers. At least Boost version 1.34 is required. + build-time headers. At least Boost version 1.35 is required. </p><p> diff --git a/doc/guide/bind10-guide.xml b/doc/guide/bind10-guide.xml index 696fb454a5..89cd160133 100644 --- a/doc/guide/bind10-guide.xml +++ b/doc/guide/bind10-guide.xml @@ -274,7 +274,7 @@ var/ <para> Building from source code requires the Boost - build-time headers. At least Boost version 1.34 is required. + build-time headers. At least Boost version 1.35 is required. <!-- TODO: we don't check for this version --> <!-- NOTE: jreed has tested with 1.34, 1.38, and 1.41. --> </para> diff --git a/src/bin/bind10/bind10.py.in b/src/bin/bind10/bind10.py.in index c19f93a632..46e793acdd 100644 --- a/src/bin/bind10/bind10.py.in +++ b/src/bin/bind10/bind10.py.in @@ -627,27 +627,44 @@ class BoB: raise if pid == 0: break if pid in self.processes: + + # One of the processes we know about. Get information on it. proc_info = self.processes.pop(pid) proc_info.restart_schedule.set_run_stop_time() self.dead_processes[proc_info.pid] = proc_info - if self.verbose: - sys.stdout.write("[bind10] Process %s (PID %d) died.\n" % - (proc_info.name, proc_info.pid)) - if proc_info.name == "b10-msgq": - if self.verbose and self.runnable: + + # Write out message, but only if in the running state: + # During startup and shutdown, these messages are handled + # elsewhere. + if self.runnable: + if exit_status is None: + sys.stdout.write( + "[bind10] Process %s (PID %d) died: exit status not available" % + (proc_info.name, proc_info.pid)) + else: + sys.stdout.write( + "[bind10] Process %s (PID %d) terminated, exit status = %d\n" % + (proc_info.name, proc_info.pid, exit_status)) + + # Was it a special process? + if proc_info.name == "b10-msgq": sys.stdout.write( "[bind10] The b10-msgq process died, shutting down.\n") - self.runnable = False + self.runnable = False else: sys.stdout.write("[bind10] Unknown child pid %d exited.\n" % pid) def restart_processes(self): - """Restart any dead processes. - Returns the time when the next process is ready to be restarted. - If the server is shutting down, returns 0. - If there are no processes, returns None. - The values returned can be safely passed into select() as the - timeout value.""" + """ + Restart any dead processes: + + * Returns the time when the next process is ready to be restarted. + * If the server is shutting down, returns 0. + * If there are no processes, returns None. + + The values returned can be safely passed into select() as the + timeout value. + """ next_restart = None # if we're shutting down, then don't restart if not self.runnable: @@ -664,13 +681,12 @@ class BoB: else: if self.verbose: sys.stdout.write("[bind10] Resurrecting dead %s process...\n" % - proc_info.name) + proc_info.name) try: proc_info.respawn() self.processes[proc_info.pid] = proc_info - if self.verbose: - sys.stdout.write("[bind10] Resurrected %s (PID %d)\n" % - (proc_info.name, proc_info.pid)) + sys.stdout.write("[bind10] Resurrected %s (PID %d)\n" % + (proc_info.name, proc_info.pid)) except: still_dead[proc_info.pid] = proc_info # remember any processes that refuse to be resurrected diff --git a/src/lib/Makefile.am b/src/lib/Makefile.am index 24123f28bb..866ca65091 100644 --- a/src/lib/Makefile.am +++ b/src/lib/Makefile.am @@ -1,2 +1,2 @@ SUBDIRS = exceptions dns cc config datasrc python xfr bench log asiolink \ - testutils + testutils nsas diff --git a/src/lib/datasrc/tests/datasrc_unittest.cc b/src/lib/datasrc/tests/datasrc_unittest.cc index b6f6964020..8718c125d5 100644 --- a/src/lib/datasrc/tests/datasrc_unittest.cc +++ b/src/lib/datasrc/tests/datasrc_unittest.cc @@ -877,12 +877,32 @@ TEST_F(DataSrcTest, NSECZonecutOfNonsecureZone) { EXPECT_TRUE(it->isLast()); } -TEST_F(DataSrcTest, RootDSQuery) { +// Test sending a DS query to root (nonsense, but it should survive) +TEST_F(DataSrcTest, RootDSQuery1) { EXPECT_NO_THROW(createAndProcessQuery(Name("."), RRClass::IN(), RRType::DS())); headerCheck(msg, Rcode::REFUSED(), true, false, true, 0, 0, 0); } +// The same, but when we have the root zone +// (which triggers rfc4035 section 3.1.4.1) +TEST_F(DataSrcTest, RootDSQuery2) { + // The message + msg.makeResponse(); + msg.setOpcode(Opcode::QUERY()); + msg.addQuestion(Question(Name("."), RRClass::IN(), RRType::DS())); + msg.setHeaderFlag(Message::HEADERFLAG_RD); + // Prepare the source + DataSrcPtr sql3_source = DataSrcPtr(new Sqlite3DataSrc); + ConstElementPtr sqlite_root = Element::fromJSON( + "{ \"database_file\": \"" TEST_DATA_DIR "/test-root.sqlite3\"}"); + EXPECT_NO_THROW(sql3_source->init(sqlite_root)); + // Make the query + EXPECT_NO_THROW(performQuery(*sql3_source, cache, msg)); + + headerCheck(msg, Rcode::NOERROR(), true, true, true, 0, 1, 0); +} + TEST_F(DataSrcTest, DSQueryFromCache) { // explicitly enable hot spot cache cache.setEnabled(true); diff --git a/src/lib/nsas/Makefile.am b/src/lib/nsas/Makefile.am new file mode 100644 index 0000000000..9e250bcaea --- /dev/null +++ b/src/lib/nsas/Makefile.am @@ -0,0 +1,36 @@ +SUBDIRS = . tests + +AM_CPPFLAGS = -I$(top_srcdir)/src/lib -I$(top_builddir)/src/lib +AM_CPPFLAGS += $(BOOST_INCLUDES) +AM_CPPFLAGS += -I$(top_srcdir)/src/lib/dns -I$(top_builddir)/src/lib/dns +AM_CPPFLAGS += -I$(top_srcdir)/src/lib/nsas -I$(top_builddir)/src/lib/nsas +AM_CPPFLAGS += $(SQLITE_CFLAGS) +AM_CXXFLAGS = $(B10_CXXFLAGS) + +if USE_GXX +# Some versions of GCC warn about some versions of Boost regarding +# missing initializer for members in its posix_time. +# https://svn.boost.org/trac/boost/ticket/3477 +AM_CXXFLAGS += -Wno-missing-field-initializers +endif + +lib_LTLIBRARIES = libnsas.la +libnsas_la_SOURCES = address_entry.h address_entry.cc +libnsas_la_SOURCES += asiolink.h +libnsas_la_SOURCES += hash.cc hash.h +libnsas_la_SOURCES += hash_deleter.h +libnsas_la_SOURCES += hash_key.cc hash_key.h +libnsas_la_SOURCES += hash_table.h +libnsas_la_SOURCES += lru_list.h +libnsas_la_SOURCES += nameserver_address_store.cc nameserver_address_store.h +libnsas_la_SOURCES += nameserver_address.h nameserver_address.cc +libnsas_la_SOURCES += nameserver_entry.cc nameserver_entry.h +libnsas_la_SOURCES += nsas_entry_compare.h +libnsas_la_SOURCES += nsas_entry.h nsas_types.h +libnsas_la_SOURCES += zone_entry.cc zone_entry.h +libnsas_la_SOURCES += fetchable.h +libnsas_la_SOURCES += address_request_callback.h +libnsas_la_SOURCES += resolver_interface.h +libnsas_la_SOURCES += random_number_generator.h + +CLEANFILES = *.gcno *.gcda diff --git a/src/lib/nsas/README b/src/lib/nsas/README new file mode 100644 index 0000000000..cdcc9fd636 --- /dev/null +++ b/src/lib/nsas/README @@ -0,0 +1,7 @@ +For an overview of the Nameserver Address Store, see the requirements and design +documents at http://bind10.isc.org/wiki/Resolver. + +At the time of writing (19 October 2010), the file asiolink.h is present in this +directory only for the purposes of development. When the recursor's +asynchronous I/O code has been finished, this will be removed and the NSAS will +use the "real" code. diff --git a/src/lib/nsas/TODO b/src/lib/nsas/TODO new file mode 100644 index 0000000000..4a206908f0 --- /dev/null +++ b/src/lib/nsas/TODO @@ -0,0 +1,40 @@ +Long term: +* Make a mechanism the cache (which does not exist at the time of writing this + note) will be able to notify the NSAS that something has changed (address, + new nameserver, etc). Because the cache will have access to the data and + knows when it changes (it updates its structures), it is the best place. It + will be caching even data like authority and additional sections. It will + notify us somehow (we will need to tell it when). + + The changes we need to know about is when set of nameservers or set of + addresses for a nameserver change and when a NS record or nameserver's A or + AAAA record is explicitly removed from the cache. +* Optimisation to pass max two outstanding queries on the network (but fetch + everything from cache right away). The first can be done by having number of + packets on the network, with max of 4 (each query are 2 of them, A and AAAA), + if it drops to 2, another one can be send. +* Add the cache cookies/contexts. +* Logging. +* Remove LRU from the nameserver entries, drop them when they are not + referenced by any zone entry. This will remove duplicates, keep the RTTs + longer and will provide access to everything that exists. This is + tricky, though, because we need to be thread safe. There seems to be + solution to use weak_ptr inside the hash_table instead of shared_ptr and + catch the exception inside get() (and getOrAdd) and delete the dead pointer. +* Better way to dispatch all calbacks in a list is needed. We take them out of + the list and dispatch them one by one. This is wrong because when an + exception happens inside the callback, we lose the ones not dispatched yet. + + What should be done in this situation anyway? Putting them back? Will anybody + still call them? Taking them one by one? + + Or recommend that if the result is really needed, that destruction of it + should be considered failure if it wasn't called yet? Make it the default + (eg. signal failure by destruction or call that function from destructor)? +* Make a zone entry hash table have multiple LRU lists, each one for part of the + slots. This will prevent locking contention while still keeping close to + the theoretical LRU behaviour (statistically, accesses to each of the part + should be as common as to others). + + It might be a good idea to encapsulate the LRUs into the hash table directly + (or create a class holding both the hash table and the LRU lists). diff --git a/src/lib/nsas/address_entry.cc b/src/lib/nsas/address_entry.cc new file mode 100644 index 0000000000..3449f9f8ef --- /dev/null +++ b/src/lib/nsas/address_entry.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +/// \file address_entry.cc +/// +/// This file exists to define the single constant \c AddressEntry::UNREACHABLE, +/// equal to the value \c UINT32_MAX. +/// +/// Ideally we could use \c UINT32_MAX directly in the header file, but this +/// constant is defined in \c stdint.h only if the macro \c __STDC_LIMIT_MACROS +/// is defined first. (This apparently is the C89 standard.) Defining the +/// macro in \c address_entry.h before including \c stdint.h doesn't work as +/// it is possible that in a source file, \c stdint.h will be included before +/// \c address_entry.h. In that case, the \c stdint.h include sentinel will +/// prevent \c stdint.h being included a second time and the value won't be +/// defined. +/// +/// The easiest solution is the one presented here: declare the value as a +/// static class constant, and define it in this source file. As we can control +/// the order of include files, this ensures that the value is defined. + +#define __STDC_LIMIT_MACROS +#include <stdint.h> + +#include "address_entry.h" + +namespace isc { +namespace nsas { +const uint32_t AddressEntry::UNREACHABLE = UINT32_MAX; +} +} diff --git a/src/lib/nsas/address_entry.h b/src/lib/nsas/address_entry.h new file mode 100644 index 0000000000..293c46e053 --- /dev/null +++ b/src/lib/nsas/address_entry.h @@ -0,0 +1,104 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __ADDRESS_ENTRY_H +#define __ADDRESS_ENTRY_H + +/// \brief Address Entry +/// +/// Lightweight class that couples an address with a RTT and provides some +/// convenience methods for accessing and updating the information. + +#include <stdint.h> +#include "asiolink.h" + +namespace isc { +namespace nsas { + +class AddressEntry { +public: + /// Creates an address entry given IOAddress entry and RTT + /// This is the only constructor; the default copy constructor and + /// assignment operator are valid for this object. + /// + /// \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), dead_until_(0) + {} + + /// \return Address object + asiolink::IOAddress getAddress() const { + return address_; + } + + /// \return Current round-trip time + 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_; + } + + /// Set current RTT + /// + /// \param rtt New RTT to be associated with this address + void setRTT(uint32_t rtt) { + 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. + void setUnreachable() { + setRTT(UNREACHABLE); // Largest long number is code for unreachable + } + + /// Check if address is unreachable + /// + /// \return true if the address is unreachable, false if not + bool isUnreachable() { + return (getRTT() == UNREACHABLE); // The getRTT() will check the cache time for unreachable server + } + + /// \return true if the object is a V4 address + bool isV4() const { + return (address_.getFamily() == AF_INET); + } + + /// \return true if the object is a V6 address + bool isV6() const { + return (address_.getFamily() == AF_INET6); + } + + // Next element is defined public for testing + static const uint32_t UNREACHABLE; ///< RTT indicating unreachable address + +private: + asiolink::IOAddress address_; ///< Address + uint32_t rtt_; ///< Round-trip time + time_t dead_until_; ///< Dead time for unreachable server +}; + +} // namespace dns +} // namespace isc + + +#endif // __ADDRESS_ENTRY_H diff --git a/src/lib/nsas/address_request_callback.h b/src/lib/nsas/address_request_callback.h new file mode 100644 index 0000000000..a24a8ee0e8 --- /dev/null +++ b/src/lib/nsas/address_request_callback.h @@ -0,0 +1,74 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __ADDRESS_REQUEST_CALLBACK_H +#define __ADDRESS_REQUEST_CALLBACK_H + +#include "asiolink.h" +#include "nameserver_address.h" + +namespace isc { +namespace nsas { + +/// \brief Callback When Address Obtained +/// +/// This is the callback object used to return an address of a nameserver to a +/// caller. It (or a subclass of it) is passed to the NSAS when a request is +/// made for the address of a nameserver. When an address is available, +/// methods on the passed objects are called. +/// +/// Note that there is no guarantee as to when the methods are called; they +/// could be called after the function call that made the address request has +/// returned the caller. Equally, the call could complete before that function +/// call returns. It is up to the caller to handle all cases. +/// +/// In terms of use, a shared pointer to this object is passed to the NSAS. +/// The NSAS will store the object via a shared pointer and after the callback +/// will delete the pointer. Whether this results in the deletion of the +/// callback object is up to the caller - if the caller wants to retain it +/// they should keep the shared pointer. + +class AddressRequestCallback { +public: + + /// Default constructor, copy contructor and assignment operator + /// are implicitly present and are OK. + + /// \brief Virtual Destructor + virtual ~AddressRequestCallback() + {} + + /// \brief Success Callback + /// + /// This method is used when an address has been retrieved for the request. + /// + /// \param address Address to be used to access the nameserver. + virtual void success(const NameserverAddress& address) = 0; + + /// \brief Unreachable + /// + /// This method is called when a request is made for an address, but all + /// the addresses for the zone are marked as unreachable. This may be + /// due to the NS records being unobtainable, or the A records for known + /// nameservers being unobtainable. + virtual void unreachable() = 0; + +}; + +} // namespace nsas +} // namespace isc + +#endif // __ADDRESS_REQUEST_CALLBACK_H diff --git a/src/lib/nsas/asiolink.h b/src/lib/nsas/asiolink.h new file mode 100644 index 0000000000..4efa38477f --- /dev/null +++ b/src/lib/nsas/asiolink.h @@ -0,0 +1,60 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __ASIOLINK_H +#define __ASIOLINK_H + +#include <string> +#include <sys/socket.h> + +namespace asiolink { + +/// \brief IO Address Dummy Class +/// +/// As part of ther recursor, Evan has written the asiolink.h file, which +/// encapsulates some of the boost::asio classes. Until these are checked +/// into trunk and merged with this branch, these dummy classes should fulfill +/// their function. + +class IOAddress { +public: + /// \param address_str String representing the address + IOAddress(const std::string& address_str) : address_(address_str) + {} + + /// \param Just a virtual destructor + virtual ~ IOAddress() { } + + /// \return Textual representation of the address + std::string toText() const + {return address_;} + + /// \return Address family of the address + virtual short getFamily() const { + return ((address_.find(".") != std::string::npos) ? AF_INET : AF_INET6); + } + + /// \return true if two addresses are equal + bool equal(const IOAddress& address) + {return (toText() == address.toText());} + +private: + std::string address_; ///< Address represented +}; + +} // namespace asiolink + +#endif // __ASIOLINK_H diff --git a/src/lib/nsas/fetchable.h b/src/lib/nsas/fetchable.h new file mode 100644 index 0000000000..fffff200e6 --- /dev/null +++ b/src/lib/nsas/fetchable.h @@ -0,0 +1,68 @@ +// Copyright (C) 2010 CZ NIC +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $id$ + +#ifndef __FETCHABLE_H +#define __FETCHABLE_H + +/** + * \file fetchable.h + * \short Interface of information that can be fetched. + */ + +namespace isc { +namespace nsas { + +/** + * \short Interface of information that can be fetched. + * + * This just holds a state of information that can be fetched from somewhere. + * No locking is performed, if it is desirable, it should be locked manually. + */ +class Fetchable { + public: + /// \short States the Fetchable object can be in. + enum State { + /// \short No one yet asked for the information. + NOT_ASKED, + /// \short The information is too old and should not be used. + EXPIRED, + /// \short The information is asked for but it did not arrive. + IN_PROGRESS, + /// \short It is not possible to get the information. + UNREACHABLE, + /// \short The information is already present. + READY + }; + /// \short Constructors + //@{ + /// This creates the Fetchable object in the given state. + Fetchable(State state = NOT_ASKED) : + state_(state) + { } + //@} + /// \short Getter and setter of current state. + //@{ + State getState() const { return state_; } + void setState(State state) { state_ = state; } + //@} + private: + State state_; +}; + +} // namespace nsas +} // namespace isc + +#endif // __FETCHABLE_H diff --git a/src/lib/nsas/hash.cc b/src/lib/nsas/hash.cc new file mode 100644 index 0000000000..33dfc7c9bc --- /dev/null +++ b/src/lib/nsas/hash.cc @@ -0,0 +1,170 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +/*! \file + * Some parts of this code were copied from BIND-9, which in turn was derived + * from universal hash function libraries of Rice University. + +\section license UH Universal Hashing Library + +Copyright ((c)) 2002, Rice University +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following + disclaimer in the documentation and/or other materials provided + with the distribution. + + * Neither the name of Rice University (RICE) nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + + +This software is provided by RICE and the contributors on an "as is" +basis, without any representations or warranties of any kind, express +or implied including, but not limited to, representations or +warranties of non-infringement, merchantability or fitness for a +particular purpose. In no event shall RICE or contributors be liable +for any direct, indirect, incidental, special, exemplary, or +consequential damages (including, but not limited to, procurement of +substitute goods or services; loss of use, data, or profits; or +business interruption) however caused and on any theory of liability, +whether in contract, strict liability, or tort (including negligence +or otherwise) arising in any way out of the use of this software, even +if advised of the possibility of such damage. +*/ + +#include <cassert> +#include <stdlib.h> +#include <algorithm> +#include <cassert> +#include <string> + +#include <config.h> + +#include "hash.h" + +using namespace std; + +namespace isc { +namespace nsas { + +// Constructor. + +Hash::Hash(uint32_t tablesize, uint32_t maxkeylen, bool randomise) : + tablesize_(tablesize), maxkeylen_(min<uint32_t>(maxkeylen, + (255 - sizeof(uint16_t)))) +{ + // (Code taken from BIND-9) + // + // Check to see that we can cope with the maximum key length which, due + // to the limitations, should not be more than 255 in total. The actual + // number of characters in the name that are considered is reduced to + // ensure that the class is taken into account in the hash. (This accounts + // for the "+ sizeof(uint16_t)" in the calculations below. + // + // Overflow check. Since our implementation only does a modulo + // operation at the last stage of hash calculation, the accumulator + // must not overflow. + hash_accum_t overflow_limit = + 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8); + if (overflow_limit < (maxkeylen_ + sizeof(uint16_t) + 1) * 0xff) { + isc_throw(KeyLengthTooLong, "Hash key length too long for Hash class"); + } + + // Initialize the random number generator with the current time. + // TODO: Use something other than pseudo-random numbers. + union { + unsigned int seed; + time_t curtime; + } init_value; + + if (randomise) { + init_value.curtime = time(NULL); + } + else { + init_value.seed = 0; + } + srandom(init_value.seed); + + // Fill in the random vector. + randvec_.reserve(maxkeylen_ + sizeof(uint16_t) + 1); + for (uint32_t i = 0; i < (maxkeylen + sizeof(uint16_t) + 1); ++i) { + randvec_.push_back(static_cast<hash_random_t>(random() & 0xffff)); + } + assert(sizeof(hash_random_t) == 2); // So that the "& 0xffff" is valid + + // Finally, initialize the mapping table for uppercase to lowercase + // characters. A table is used as indexing a table is faster than calling + // the tolower() function. + casemap_.reserve(256); + for (int i = 0; i < 256; ++i) { + casemap_.push_back(i); + } + for (int i = 'A'; i <= 'Z'; ++i) { + casemap_[i] += ('a' - 'A'); + } +} + + +uint32_t Hash::operator()(const HashKey& key, bool ignorecase) const +{ + // Calculation as given in BIND-9. + hash_accum_t partial_sum = 0; + uint32_t i = 0; // Used after the end of the loop + + // Perform the hashing. If the key length if more than the maximum we set + // up this hash for, ignore the excess. + if (ignorecase) { + for (i = 0; i < min(key.keylen, maxkeylen_); ++i) { + partial_sum += mapLower(key.key[i]) * randvec_[i]; + } + } else { + for (i = 0; i < min(key.keylen, maxkeylen_); ++i) { + partial_sum += key.key[i] * randvec_[i]; + } + } + + // Add the hash of the class code + union { + uint16_t class_code; // Copy of the class code + char bytes[sizeof(uint16_t)]; // Byte equivalent + } convert; + + convert.class_code = key.class_code.getCode(); + for (int j = 0; j < sizeof(uint16_t); ++j, ++i) { + partial_sum += convert.bytes[j] * randvec_[i]; + } + + // ... and finish up. + partial_sum += randvec_[i]; + + // Determine the hash value + uint32_t value = partial_sum % prime32_; + + // ... and round it to fit the table size + return (value % tablesize_); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/hash.h b/src/lib/nsas/hash.h new file mode 100644 index 0000000000..6913dfc7e4 --- /dev/null +++ b/src/lib/nsas/hash.h @@ -0,0 +1,127 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __HASH_H +#define __HASH_H + +#include <stdint.h> +#include <vector> + +#include <exceptions/exceptions.h> + +#include "hash_key.h" + +namespace isc { +namespace nsas { + +/// \brief Too Long Key Length +/// +/// Thrown if the expected maximum key length is too long for the data types +/// declared in the class. +class KeyLengthTooLong : public isc::Exception { +public: + KeyLengthTooLong(const char* file, size_t line, const char* what) : + isc::Exception(file, line, what) + {} +}; + + +/// \brief Hash Calculation +/// +/// Class abstracting the mechanics of the hash calculation. +class Hash { +public: + + /// \brief Constructor + /// + /// Constructs the hash table and initialises all data structures needed + /// for the hashing. + /// + /// \param tablesize Size of the hash table. For best performance, this + /// should be a prime number. + /// \param maxkeylen Maximum length (in bytes) of a key to be hashed. + /// calculation will return a value between 0 and N-1. The default + /// value of 255 is the maximum size of a DNS name. + /// \param randomise If true (the default), the pseudo-random number + /// generator is seeded with the current time. Otherwise it is initialised + /// to a known sequence. This is principally for unit tests, where a random + /// sequence could lead to problems in checking results. + Hash(uint32_t tablesize, uint32_t maxkeylen = 255, bool randomise = true); + + /// \bool Virtual Destructor + virtual ~Hash() + {} + + /// \brief Return Size + /// + /// \return The hash table size with which this object was initialized + virtual uint32_t tableSize() const { + return tablesize_; + } + + /// \brief Return Key Length + /// + /// \return Maximum length of a key that this class can cope with. + virtual uint32_t maxKeyLength() const { + return maxkeylen_; + } + + /// \brief Hash Value + /// + /// \param key Parameters comprising the key to be hashed. + /// \param ignorecase true for case to be ignored when calculating the + /// hash value, false for it to be taken into account. + /// + /// \return Hash value, a number between 0 and N-1. + virtual uint32_t operator()(const HashKey& key, + bool ignorecase = true) const; + + /// \brief Map Lower Case to Upper Case + /// + /// Equivalent of tolower(), but using a table lookup instead of a + /// function call. This should make the mapping faster. + /// + /// \param inchar Input character + /// + /// \return Mapped character + virtual unsigned char mapLower(unsigned char inchar) const { + return casemap_[inchar]; + } + +private: + + /// \name Local Typedefs + /// + /// Typedefs for use in the code. This makes it easier to compare the + /// hashing code with that in BIND-9. + //@{ + typedef uint32_t hash_accum_t; ///< Accumulator + typedef uint16_t hash_random_t; ///< Random number used in hash + //@} + + uint32_t tablesize_; ///< Size of the hash table + uint32_t maxkeylen_; ///< Maximum key length + std::vector<unsigned char> casemap_; ///< Case mapping table + std::vector<hash_random_t> randvec_; ///< Vector of random numbers + + static const uint32_t prime32_ = 0xfffffffb; ///< 2^32 - 5 + ///< Specifies range of hash output +}; + +} // namspace nsas +} // namespace isc + +#endif // __HASH_H diff --git a/src/lib/nsas/hash_deleter.h b/src/lib/nsas/hash_deleter.h new file mode 100644 index 0000000000..b112707b7b --- /dev/null +++ b/src/lib/nsas/hash_deleter.h @@ -0,0 +1,76 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __HASH_DELETER_H +#define __HASH_DELETER_H + +#include <boost/shared_ptr.hpp> +#include "hash_table.h" +#include "lru_list.h" + +namespace isc { +namespace nsas { + +/// \brief Delete Object from Hash Table +/// +/// This is the object passed to the LRU list constructors that deletes the +/// ZoneEntry from the hash table when the zone is deleted from the LRU list. +/// +/// It is declared as a nested class so as to be able to access the +/// hash table without the need to be declared as "friend" or the need +/// to define accessor methods. +template <typename T> +class HashDeleter : public LruList<T>::Dropped { +public: + + /// \brief Constructor + /// + /// \param hashtable Reference to the hash table from which information is + /// to be deleted. The table is assumed to remain in existence for the life + /// of this object. + /// + /// \param hashtable Hash table from which the element should be deleted. + HashDeleter(HashTable<T>& hashtable) : hashtable_(hashtable) + {} + + /// \brief Destructor + /// + virtual ~HashDeleter(){} + + // The default copy constructor and assignment operator are correct for + // this object. + + /// \brief Deletion Function + /// + /// Performs the deletion of the zone entry from the hash table. + /// + /// \param element Element to be deleted + virtual void operator()(T* element) const; + +private: + HashTable<T>& hashtable_; ///< Hash table to access element +}; + +// delete the object from the relevant hash table +template <class T> +void HashDeleter<T>::operator()(T* element) const { + hashtable_.remove(element->hashKey()); +} + +} // namespace nsas +} // namespace isc + +#endif // __HASH_DELETER_H diff --git a/src/lib/nsas/hash_key.cc b/src/lib/nsas/hash_key.cc new file mode 100644 index 0000000000..813dd12cf4 --- /dev/null +++ b/src/lib/nsas/hash_key.cc @@ -0,0 +1,53 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <cstring> + +#include <config.h> +#include "hash_key.h" + +namespace isc { +namespace nsas { + +/// Hash Equality Function +bool HashKey::operator==(const isc::nsas::HashKey& other) { + + // Check key lengths + if (other.keylen == keylen) { + + // ... and classes + if (other.class_code == class_code) { + + // ... before the expensive operation. This involves a + // byte-by-byte comparison, doing a case-independent match. + // memcmp() doesn't work (exact match) nor does strcmp or its + // variation (stops on the first null byte). + // + // TODO: Use a lookup table to map upper to lower case (for speed) + for (int i = 0; i < other.keylen; ++i) { + if (tolower(static_cast<unsigned char>(other.key[i])) != + tolower(static_cast<unsigned char>(key[i]))) { + return false; // Mismatch + } + } + return true; // All bytes matched + } + } + return false; // Key length or class did not match +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/hash_key.h b/src/lib/nsas/hash_key.h new file mode 100644 index 0000000000..1b84659472 --- /dev/null +++ b/src/lib/nsas/hash_key.h @@ -0,0 +1,99 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __HASH_KEY_H +#define __HASH_KEY_H + +#include <dns/rrclass.h> + +#include <stdint.h> +#include <string> +#include <config.h> + +namespace isc { +namespace nsas { + +/// \brief Hash Key +/// +/// In the nameserver address store, an object is placed into a hash table +/// according to its key (name) and class. +/// +/// The key comprises two elements, a pointer to the start of a char string +/// holding the data that describes the key and a length. This has been +/// chosen over a std::string because: +/// +/// # The key may not be a string, it may be binary data +/// # The overhead of creating std::string objects from such data. +/// +/// "key" is declared as "const char*" - rather than the more semantically +/// correct "const uint8_t*" - simply because if std::strings are used, then +/// the c_str function will return a "const char*". +/// +/// To avoid passing round three elements (key, key length, and class), they +/// have been combined into this simple struct. +struct HashKey { + + /// \brief Constructor + /// + /// Basic constructor to make the hash key. + /// + /// \param the_key Array of bytes for which key is to be constructed + /// \param the_keylen Length of the byte array + /// \param the_class_code Class of this entry + HashKey(const char* the_key, uint32_t the_keylen, + const isc::dns::RRClass& the_class_code) : + key(the_key), + keylen(the_keylen), + class_code(the_class_code) + {} + + /// \brief String Constructor + /// + /// Convenience constructor using a std::string. + /// + /// \param the_key Name to use as the key for the hash + /// \param the_class_code Class of this entry + HashKey(const std::string& the_key, + const isc::dns::RRClass& the_class_code) : + key(the_key.c_str()), + keylen(the_key.size()), + class_code(the_class_code) + {} + + /// \brief Equality + /// + /// Convenience for unit testing, this matches two hash keys as being + /// equal if the key strings match on a case-independent basis and the + /// classes match. + /// + /// Note that the class strings may include null bytes; the match is + /// done on a byte-by-byte basis, with codes in the range 'A' to 'Z' being + /// mapped to 'a' to 'z'. + /// + /// \param other Hash key to compare against. + /// + /// \return true if the two hash key objects are the same. + bool operator==(const isc::nsas::HashKey& other); + + const char* key; ///< Pointer to the start of the key string + uint32_t keylen; ///< Length of the key string + isc::dns::RRClass class_code; ///< Class associated with the key +}; + +} // namespace nsas +} // namespace isc + +#endif // __HASH_KEY_H diff --git a/src/lib/nsas/hash_table.h b/src/lib/nsas/hash_table.h new file mode 100644 index 0000000000..d72665ce24 --- /dev/null +++ b/src/lib/nsas/hash_table.h @@ -0,0 +1,342 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __HASH_TABLE_H +#define __HASH_TABLE_H + +#include <boost/shared_ptr.hpp> +#include <boost/thread.hpp> +#include <boost/interprocess/sync/sharable_lock.hpp> +#include <boost/interprocess/sync/scoped_lock.hpp> +#include <boost/interprocess/sync/interprocess_upgradable_mutex.hpp> +#include <list> + +#include <config.h> + +#include "hash.h" +#include "hash_key.h" + +// Maximum key length if the maximum size of a DNS name +#define MAX_KEY_LENGTH 255 + +namespace isc { +namespace nsas { + +/// \brief Hash Table Slot +/// +/// Describes the entry for the hash table. This is non-copyable (because +/// the mutex is non-copyable), but we need to be able to copy it to initialize +/// a vector of hash table slots. As the copy is only needed for +/// initialization, and as there is no need to copy state when this happens, we +/// cheat: the copy constructor constructs a newly initialized HashTableSlot and +/// does not copy its argument. +template <typename T> +struct HashTableSlot { + + /// \brief Type definitions + /// + //@{ + + typedef typename std::list<boost::shared_ptr<T> >::iterator iterator; + ///< Iterator over elements with same hash + + typedef boost::interprocess::interprocess_upgradable_mutex mutex_type; + ///< Mutex protecting this slot + //@} + + /// \brief Default Constructor + HashTableSlot() + {} + + /// \brief Copy Constructor + /// + /// ... which as noted in the class description does not copy. + HashTableSlot(const HashTableSlot<T>&) + { } + +public: + mutex_type mutex_; ///< Protection mutex + std::list<boost::shared_ptr<T> > list_; ///< List head +}; + +/// \brief Comparison Object Class +/// +/// The base class for a comparison object; this object is used to compare +/// an object in the hash table with a key, and indicates whether the two +/// match. All objects used for comparison in hash tables should be derived +/// from this class. +template <typename T> +class HashTableCompare { +public: + /// \brief Constructor + HashTableCompare(){} + + /// \brief virtual Destructor + virtual ~HashTableCompare() {} + + /// \brief Comparison Function + /// + /// Compares an object against a name in the hash table and reports if the + /// object's name is the same. + /// + /// \param object Pointer to the object + /// \param key Key describing the object + /// + /// \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 Hash Table +/// +/// This class is an implementation of a hash table in which the zones and +/// nameservers of the Nameserver Address Store are held. +/// +/// A special class has been written (rather than use an existing hash table +/// class) to improve concurrency. Rather than lock the entire hash table when +/// an object is added/removed/looked up, only the entry for a particular hash +/// value is locked. To do this, each entry in the hash table is a pair of +/// mutex/STL List; the mutex protects that particular list. +/// +/// \param T Class of object to be stored in the table. +template <typename T> +class HashTable { +public: + + /// \brief Type Definitions + /// + //@{ + typedef typename + boost::interprocess::sharable_lock<typename HashTableSlot<T>::mutex_type> + sharable_lock; ///< Type for a scope-limited read-lock + + typedef typename + boost::interprocess::scoped_lock<typename HashTableSlot<T>::mutex_type> + scoped_lock; ///< Type for a scope-limited write-lock + //@} + + /// \brief Constructor + /// + /// Initialises the hash table. + /// + /// \param CmpFn Compare function (or object) used to compare an object with + /// to get the name to be used as a key in the table. The object should be + /// created via a "new" as ownership passes to the hash table. The hash + /// table will take the responsibility of deleting it. + /// \param size Size of the hash table. For best result, this should be a + /// 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 + /// + /// Returns a shared_ptr object pointing to the table entry + /// + /// \param key Name of the object (and class). The hash of this is + /// calculated and used to index the table. + /// + /// \return Shared pointer to the object or NULL if it is not there. + boost::shared_ptr<T> get(const HashKey& key) { + uint32_t index = hash_(key); + sharable_lock lock(table_[index].mutex_); + return getInternal(key, index); + } + + /// \brief Remove Entry + /// + /// Remove the specified entry. The shared pointer to the object is + /// destroyed, so if this is the last pointer, the object itself is also + /// destroyed. + /// + /// \param key Name of the object (and class). The hash of this is + /// calculated and used to index the table. + /// + /// \return true if the object was deleted, false if it was not found. + bool remove(const HashKey& key); + + /// \brief Add Entry + /// + /// Adds the specified entry to the table. If there is an entry already + /// there, it is either replaced or the addition fails, depending on the + /// setting of the "replace" parameter. + /// + /// \param object Pointer to the object to be added. If the addition is + /// successful, this object will have a shared pointer pointing to it; it + /// should not be deleted by the caller. + /// \param key Key to use to calculate the hash. + /// \param replace If true, when an object is added and an object with the + /// same name already exists, the existing object is replaced. If false, + // the addition fails and a status is returned. + /// \return true if the object was successfully added, false otherwise. + bool add(boost::shared_ptr<T>& object, const HashKey& key, + bool replace = false) + { + uint32_t index = hash_(key); + scoped_lock lock(table_[index].mutex_); + return addInternal(object, key, index, replace); + } + + /** + * \brief Attomicly lookup an entry or add a new one if it does not exist. + * + * Looks up an entry specified by key in the table. If it is not there, + * it calls generator() and adds its result to the table under given key. + * It is performed attomically to prevent race conditions. + * + * \param key The entry to lookup. + * \param generator will be called when the item is not there. Its result + * will be added and returned. The generator should return as soon + * as possible, the slot is locked during its execution. + * \return The boolean part of pair tells if the value was added (true + * means new value, false looked up one). The other part is the + * object, either found or created. + * \todo This uses a scoped_lock, which does not allow sharing and is + * used a lot in the code. It might turn out in future that it is a + * problem and that most of the accesses is read only. In that case we + * could split it to fast-slow path - first try to find it with + * shared_lock. If it fails, lock by scoped_lock, try to find again (we + * unlocked it, so it might have appeared) and if it still isn't there, + * create it. Not implemented now as it might or might not help (it + * could even slow it down) and the code would get more complicated. + */ + template<class Generator> + std::pair<bool, boost::shared_ptr<T> > getOrAdd(const HashKey& key, + const Generator& generator) + { + uint32_t index = hash_(key); + scoped_lock lock(table_[index].mutex_); + boost::shared_ptr<T> result(getInternal(key, index)); + if (result) { + return (std::pair<bool, boost::shared_ptr<T> >(false, result)); + } else { + result = generator(); + addInternal(result, key, index); + return (std::pair<bool, boost::shared_ptr<T> >(true, result)); + } + } + + /// \brief Returns Size of Hash Table + /// + /// \return Size of hash table + uint32_t tableSize() const { + return table_.size(); + } + +protected: + // Internal parts, expect to be already locked + boost::shared_ptr<T> getInternal(const HashKey& key, + uint32_t index); + bool addInternal(boost::shared_ptr<T>& object, const HashKey& key, + uint32_t index, bool replace = false); + +private: + Hash hash_; ///< Hashing function + std::vector<HashTableSlot<T> > table_; ///< The hash table itself + boost::shared_ptr<HashTableCompare<T> > compare_; ///< Compare object +}; + + +// Constructor +template <typename T> +HashTable<T>::HashTable(HashTableCompare<T>* compare, uint32_t size) : + hash_(size, MAX_KEY_LENGTH), table_(size), compare_(compare) +{} + +// Lookup an object in the table +template <typename T> +boost::shared_ptr<T> HashTable<T>::getInternal(const HashKey& key, + uint32_t index) +{ + // Locate the object. + typename HashTableSlot<T>::iterator i; + for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) { + if ((*compare_)(i->get(), key)) { + + // Found it, so return the shared pointer object + return (*i); + } + } + + // Did not find it, return an empty shared pointer object. + return boost::shared_ptr<T>(); +} + +// Remove an entry from the hash table +template <typename T> +bool HashTable<T>::remove(const HashKey& key) { + + // Calculate the hash value + uint32_t index = hash_(key); + + // Access to the elements of this hash slot are accessed under a mutex. + // The mutex will be released when this object goes out of scope and is + // destroyed. + scoped_lock lock(table_[index].mutex_); + + // Now search this list to see if the element already exists. + typename HashTableSlot<T>::iterator i; + for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) { + if ((*compare_)(i->get(), key)) { + + // Object found so delete it. + table_[index].list_.erase(i); + return true;; + } + } + + // When we get here, we know that there is no element with the key in the + // list, so tell the caller. + return false; +} + +// Add an entry to the hash table +template <typename T> +bool HashTable<T>::addInternal(boost::shared_ptr<T>& object, + const HashKey& key, uint32_t index, bool replace) +{ + // Search this list to see if the element already exists. + typename HashTableSlot<T>::iterator i; + for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) { + if ((*compare_)(i->get(), key)) { + + // Object found. If we are not allowed to replace the element, + // return an error. Otherwise erase it from the list and exit the + // loop. + if (replace) { + table_[index].list_.erase(i); + break; + } + else { + return false; + } + } + } + + // When we get here, we know that there is no element with the key in the + // list - in which case, add the new object. + table_[index].list_.push_back(object); + + return true; +} + +} // namespace nsas +} // namespace isc + +#endif // __HASH_TABLE_H diff --git a/src/lib/nsas/lru_list.h b/src/lib/nsas/lru_list.h new file mode 100644 index 0000000000..ad67927bdd --- /dev/null +++ b/src/lib/nsas/lru_list.h @@ -0,0 +1,238 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __LRU_LIST_H +#define __LRU_LIST_H + +#include <list> +#include <string> + +#include <boost/noncopyable.hpp> +#include <boost/shared_ptr.hpp> +#include <boost/thread.hpp> +#include <boost/interprocess/sync/scoped_lock.hpp> + +#include <config.h> + +namespace isc { +namespace nsas { + +/// \brief LRU List +/// +/// Provides the LRU list for the zone and nameserver objects. The list is +/// created with a specific size. Entries are added to the back of the list +/// and removed from the front. It is also possible to pull an element out +/// of the middle of the list and add it to the end of the list, an action that +/// should be done when the element is referenced. +/// +/// It is not intended that the class be copied, and the derivation from +/// boost::noncopyable enforces this. +template <typename T> +class LruList : boost::noncopyable { +public: + typedef typename std::list<boost::shared_ptr<T> > lru_list; + typedef typename lru_list::iterator iterator; + + /// \brief Dropped Operation + /// + /// When an object is dropped from the LRU list because it has not been + /// accessed for some time, it is possible that the action should trigger + /// some other functions. For this reason, it is possible to register + /// a list-wide functor object to execute in this casee. + /// + /// Note that the function does not execute as the result of a call to + /// remove() - that is an explicit call and it is assumed that the caller + /// will handle any additional operations needed. + class Dropped { + public: + /// \brief Constructor + Dropped(){} + + /// \brief Virtual Destructor + virtual ~Dropped(){} + + /// \brief Dropped Object Handler + /// + /// Function object called when the object drops off the end of the + /// LRU list. + /// + /// \param drop Object being dropped. + virtual void operator()(T* drop) const = 0; + }; + + /// \brief Constructor + /// + /// \param max_size Maximum size of the list before elements are dropped. + /// \param dropped Pointer to a function object that will get called as + /// elements are dropped. This object will be stored using a shared_ptr, + /// so should be allocated with new(). + LruList(uint32_t max_size = 1000, Dropped* dropped = NULL) : + max_size_(max_size), count_(0), dropped_(dropped) + {} + + /// \brief Virtual Destructor + virtual ~LruList() + {} + + /// \brief Add Element + /// + /// Add a new element to the end of the list. + /// + /// \param element Reference to the element to add. + /// + /// \return Handle describing the element in the LRU list. + virtual void add(boost::shared_ptr<T>& element); + + /// \brief Remove Element + /// + /// Removes an element from the list. If the element is not present (i.e. + /// its internal list pointer is invalid), this is a no-op. + /// + /// \param element Reference to the element to remove. + virtual void remove(boost::shared_ptr<T>& element); + + /// \brief Touch Element + /// + /// The name comes from the Unix "touch" command. All this does is to + /// move the specified entry from the middle of the list to the end of + /// the list. + /// + /// \param element Reference to the element to touch. + virtual void touch(boost::shared_ptr<T>& element); + + /// \brief Return Size of the List + /// + /// An independent count is kept of the list size, as list.size() may take + /// some time if the list is big. + /// + /// \return Number of elements in the list + virtual uint32_t size() const { + + // Don't bother to lock the mutex. If an update is in progress, we + // receive either the value just before the update or just after it. + // Either way, this call could have come just before or just after + // that operation, so the value would have been just as uncertain. + return count_; + } + + /// \brief Return Maximum Size + /// + /// \return Maximum size of the list + virtual uint32_t getMaxSize() const { + return max_size_; + } + + /// \brief Set Maximum Size + /// + /// \param new_size New maximum list size + virtual void setMaxSize(uint32_t max_size) { + max_size_ = max_size; + } + +private: + boost::mutex mutex_; ///< List protection + std::list<boost::shared_ptr<T> > lru_; ///< The LRU list itself + uint32_t max_size_; ///< Max size of the list + uint32_t count_; ///< Count of elements + boost::shared_ptr<Dropped> dropped_; ///< Dropped object +}; + +// Add entry to the list +template <typename T> +void LruList<T>::add(boost::shared_ptr<T>& element) { + + // Protect list against concurrent access + boost::interprocess::scoped_lock<boost::mutex> lock(mutex_); + + // Add the entry and set its pointer field to point into the list. + // insert() is used to get the pointer. + element->setLruIterator(lru_.insert(lru_.end(), element)); + + // ... and update the count while we have the mutex. + ++count_; + + // If the count takes us above the maximum size of the list, remove elements + // from the front. The current list size could be more than one above the + // maximum size of the list if the maximum size was changed after + // construction. + while (count_ > max_size_) { + if (!lru_.empty()) { + + // Run the drop handler (if there is one) on the + + // to-be-dropped object. + if (dropped_) { + (*dropped_)(lru_.begin()->get()); + } + + // ... and get rid of it from the list + lru_.pop_front(); + --count_; + } + else { + + // TODO: Log this condition (count_ > 0 when list empty) - + // it should not happen + count_ = 0; + break; + } + } +} + +// Remove an element from the list +template <typename T> +void LruList<T>::remove(boost::shared_ptr<T>& element) { + + // An element can only be removed it its internal pointer is valid. + // If it is, the pointer can be used to access the list because no matter + // what other elements are added or removed, the pointer remains valid. + // + // If the pointer is not valid, this is a no-op. + if (element->iteratorValid()) { + + // Is valid, so protect list against concurrent access + boost::interprocess::scoped_lock<boost::mutex> lock(mutex_); + + lru_.erase(element->getLruIterator()); // Remove element from list + element->invalidateIterator(); // Invalidate pointer + --count_; // One less element + } +} + +// Touch an element - remove it from the list and add to the end +template <typename T> +void LruList<T>::touch(boost::shared_ptr<T>& element) { + + // As before, if the pointer is not valid, this is a no-op. + if (element->iteratorValid()) { + + // Protect list against concurrent access + boost::interprocess::scoped_lock<boost::mutex> lock(mutex_); + + // Move the element to the end of the list. + lru_.splice(lru_.end(), lru_, element->getLruIterator()); + + // Update the iterator in the element to point to it. We can + // offset from end() as a list has a bidirectional iterator. + iterator i = lru_.end(); + element->setLruIterator(--i); + } +} + +} // namespace nsas +} // namespace isc + +#endif // __LRU_LIST_H diff --git a/src/lib/nsas/nameserver_address.cc b/src/lib/nsas/nameserver_address.cc new file mode 100644 index 0000000000..5bb02c0e85 --- /dev/null +++ b/src/lib/nsas/nameserver_address.cc @@ -0,0 +1,30 @@ +// Copyright (C) 2010 CZ NIC +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $id$ + +#include "nameserver_address.h" +#include "nameserver_entry.h" + +namespace isc { +namespace nsas { + +void +NameserverAddress::updateRTT(uint32_t rtt) const { + // We delegate it to the address entry inside the nameserver entry + ns_->updateAddressRTT(rtt, address_.getAddress(), family_); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/nameserver_address.h b/src/lib/nsas/nameserver_address.h new file mode 100644 index 0000000000..d609844e2f --- /dev/null +++ b/src/lib/nsas/nameserver_address.h @@ -0,0 +1,119 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NAMESERVER_ADDRESS_H +#define __NAMESERVER_ADDRESS_H + +#include <boost/shared_ptr.hpp> + +#include <exceptions/exceptions.h> + +#include "asiolink.h" +#include "address_entry.h" +#include "nsas_types.h" + +namespace isc { +namespace nsas { + +class ZoneEntry; +class NameserverEntry; + +/// \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 +/// request an address for the name server. It contains one address +/// that can be used by resolver. When the resolver get query back from the name +/// server, it should update the name server's RTT(Round Trip Time) with this +/// object. +/// +/// It is not thread safe, only reentrant. It is expected to be kept inside +/// the resolver and used only once for the address and once for the update. + +class NameserverAddress { +public: + /// \brief Constructor + /// + /// The NameserverAddress object will contain one shared_ptr object that + /// pointed to NameserverEntry which contains the address as well as it's + /// corresponding index. The user can update it's RTT with the index later. + /// + /// \param namerserver A shared_ptr that points to a NameserverEntry object + /// 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 + /// \param family Address family, V4_ONLY or V6_ONLY + NameserverAddress(const boost::shared_ptr<NameserverEntry>& nameserver, + const AddressEntry& address, AddressFamily family): + ns_(nameserver), address_(address), family_(family) + { + if(!ns_) { + isc_throw(NullNameserverEntryPointer, "NULL NameserverEntry pointer."); + } + } + + /// \brief Default Constructor + NameserverAddress() : address_(asiolink::IOAddress("::1")) { } + + /// \brief Return address + /// + asiolink::IOAddress getAddress() const { + return (address_.getAddress()); + } + + /// \brief Update Round-trip Time + /// + /// When the user get one request back from the name server, it should + /// update the address's RTT. + /// \param rtt The new Round-Trip Time + void updateRTT(uint32_t rtt) const; + + /// Short access to the AddressEntry inside. + //@{ + const AddressEntry& getAddressEntry() const { + return (address_); + } + AddressEntry& getAddressEntry() { + return (address_); + } + //@} +private: + + /* + * Note: Previous implementation used index into the entry. That is wrong, + * as the list of addresses may change. Thil would cause setting a + * different address or a crash. + */ + boost::shared_ptr<NameserverEntry> ns_; ///< Shared-pointer to NameserverEntry object + AddressEntry address_; ///< The address + AddressFamily family_; ///< The address family (V4_ONLY or V6_ONLY) +}; + +} // namespace nsas +} // namespace isc + +#endif//__NAMESERVER_ADDRESS_H diff --git a/src/lib/nsas/nameserver_address_store.cc b/src/lib/nsas/nameserver_address_store.cc new file mode 100644 index 0000000000..5c79106dfd --- /dev/null +++ b/src/lib/nsas/nameserver_address_store.cc @@ -0,0 +1,96 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <boost/thread.hpp> +#include <boost/shared_ptr.hpp> +#include <boost/foreach.hpp> + +#include <config.h> +#include <dns/rdataclass.h> + +#include "hash_table.h" +#include "lru_list.h" +#include "hash_deleter.h" +#include "nsas_entry_compare.h" +#include "nameserver_entry.h" +#include "nameserver_address_store.h" +#include "zone_entry.h" +#include "address_request_callback.h" + +using namespace isc::dns; +using namespace std; +using namespace boost; + +namespace isc { +namespace nsas { + +// Constructor. +// +// The LRU lists are set equal to three times the size of the respective +// hash table, on the assumption that three elements is the longest linear +// search we want to do when looking up names in the hash table. +NameserverAddressStore::NameserverAddressStore( + shared_ptr<ResolverInterface> resolver, uint32_t zonehashsize, + uint32_t nshashsize) : + zone_hash_(new HashTable<ZoneEntry>(new NsasEntryCompare<ZoneEntry>, + zonehashsize)), + nameserver_hash_(new HashTable<NameserverEntry>( + new NsasEntryCompare<NameserverEntry>, nshashsize)), + zone_lru_(new LruList<ZoneEntry>((3 * zonehashsize), + new HashDeleter<ZoneEntry>(*zone_hash_))), + nameserver_lru_(new LruList<NameserverEntry>((3 * nshashsize), + new HashDeleter<NameserverEntry>(*nameserver_hash_))), + resolver_(resolver) +{ } + +namespace { + +/* + * We use pointers here so there's no call to any copy constructor. + * It is easier for the compiler to inline it and prove that there's + * no need to copy anything. In that case, the bind should not be + * called at all to create the object, just call the function. + */ +shared_ptr<ZoneEntry> +newZone(const shared_ptr<ResolverInterface>* resolver, const string* zone, + const RRClass* class_code, + const shared_ptr<HashTable<NameserverEntry> >* ns_hash, + const shared_ptr<LruList<NameserverEntry> >* ns_lru) +{ + shared_ptr<ZoneEntry> result(new ZoneEntry(*resolver, *zone, *class_code, + *ns_hash, *ns_lru)); + return (result); +} + +} + +void +NameserverAddressStore::lookup(const string& zone, const RRClass& class_code, + shared_ptr<AddressRequestCallback> callback, AddressFamily family) +{ + pair<bool, shared_ptr<ZoneEntry> > zone_obj(zone_hash_->getOrAdd(HashKey( + zone, class_code), boost::bind(newZone, &resolver_, &zone, &class_code, + &nameserver_hash_, &nameserver_lru_))); + if (zone_obj.first) { + zone_lru_->add(zone_obj.second); + } else { + zone_lru_->touch(zone_obj.second); + } + zone_obj.second->addCallback(callback, family); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/nameserver_address_store.h b/src/lib/nsas/nameserver_address_store.h new file mode 100644 index 0000000000..4fce3a47a1 --- /dev/null +++ b/src/lib/nsas/nameserver_address_store.h @@ -0,0 +1,118 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NAMESERVER_ADDRESS_STORE_H +#define __NAMESERVER_ADDRESS_STORE_H + +#include <string> +#include <vector> + +#include <boost/shared_ptr.hpp> + +#include "nsas_types.h" + +namespace isc { +// Some forward declarations, so we do not need to include so many headers + +namespace dns { +class RRClass; +} + +namespace nsas { + +class ResolverInterface; +template<class T> class HashTable; +template<class T> class LruList; +class ZoneEntry; +class NameserverEntry; +class AddressRequestCallback; + +/// \brief Nameserver Address Store +/// +/// This class implements the bare bones of the nameserver address store - the +/// storage of nameserver information. An additional layer above it implements +/// the logic for sending queries for the nameserver addresses if they are not +/// in the store. + +class NameserverAddressStore { +public: + + /// \brief Constructor + /// + /// The constructor sizes all the tables. As there are various + /// relationships between the table sizes, and as some values are best as + /// prime numbers, the table sizes are determined by compile-time values. + /// + /// \param resolver Which resolver object (or resolver-like, in case of + /// tests) should it use to ask questions. + /// \param zonehashsize Size of the zone hash table. The default value of + /// 1009 is the first prime number above 1000. + /// \param nshash size Size of the nameserver hash table. The default + /// value of 3001 is the first prime number over 3000, and by implication, + /// there is an assumption that there will be more nameservers than zones + /// in the store. + NameserverAddressStore(boost::shared_ptr<ResolverInterface> resolver, + uint32_t zonehashsize = 1009, uint32_t nshashsize = 3001); + + /// \brief Destructor + /// + /// Empty virtual destructor. + virtual ~NameserverAddressStore() + {} + + /// \brief Lookup Address for a Zone + /// + /// Looks up the address of a nameserver in the zone. + /// + /// \param zone Name of zone for which an address is required. + /// \param class_code Class of the zone. + /// \param callback Callback object used to pass the result back to the + /// caller. + /// \param family Which address is requested. + void lookup(const std::string& zone, const dns::RRClass& class_code, + boost::shared_ptr<AddressRequestCallback> callback, AddressFamily + family = ANY_OK); + + /// \brief Protected Members + /// + /// These members should be private. However, with so few public methods + /// and with a lot of internal processing, the testing of this class is + /// problematical. + /// + /// To get round this, a number of elements are declared protected. This + /// means that tests can be carried out by testing a subclass. The subclass + /// does not override the main class methods, but does contain additional + /// methods to set up data and examine the internal state of the class. + //@{ +protected: + // Zone and nameserver hash tables + boost::shared_ptr<HashTable<ZoneEntry> > zone_hash_; + boost::shared_ptr<HashTable<NameserverEntry> > nameserver_hash_; + + // ... and the LRU lists + boost::shared_ptr<LruList<ZoneEntry> > zone_lru_; + boost::shared_ptr<LruList<NameserverEntry> > nameserver_lru_; + // The resolver we use +private: + boost::shared_ptr<ResolverInterface> resolver_; + //}@ +}; + +} // namespace nsas +} // namespace isc + + +#endif // __NAMESERVER_ADDRESS_STORE_H diff --git a/src/lib/nsas/nameserver_entry.cc b/src/lib/nsas/nameserver_entry.cc new file mode 100644 index 0000000000..891edcd83a --- /dev/null +++ b/src/lib/nsas/nameserver_entry.cc @@ -0,0 +1,425 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <algorithm> +#include <functional> +#include <cassert> +#include <iostream> +#include <boost/bind.hpp> +#include <boost/foreach.hpp> + +#include <ctype.h> +#include <strings.h> + +#include <config.h> + +#include <exceptions/exceptions.h> +#include <dns/name.h> +#include <dns/rrclass.h> +#include <dns/rrttl.h> +#include <dns/question.h> + +#include "address_entry.h" +#include "nameserver_address.h" +#include "nameserver_entry.h" +#include "resolver_interface.h" + +using namespace asiolink; +using namespace isc::nsas; +using namespace isc::dns; +using namespace std; +using namespace boost; + +namespace isc { +namespace nsas { + +namespace { + +// Just shorter type alias +typedef recursive_mutex::scoped_lock Lock; + +} + +// Returns the list of addresses matching the given family +Fetchable::State +NameserverEntry::getAddresses(AddressVector& addresses, + AddressFamily family, bool expired_ok) +{ + Lock lock(mutex_); + + // Check TTL + time_t now(time(NULL)); + // We take = as well, so we catch TTL 0 correctly + // expiration_ == 0 means not set, the reason is we are UNREACHABLE or + // NOT_ASKED or IN_PROGRESS + if (getState() != NOT_ASKED && expiration_ && expiration_ <= now) { + setState(EXPIRED); + } + + if (getState() == EXPIRED && !expired_ok) { + return EXPIRED; + } + + switch (getState()) { + case IN_PROGRESS: + /* + * Did we receive the address already? + * + * We might have already received the addresses for this family + * and still wait for the other (in which case has_address_[family] + * will be true). We might already received a negative answer, + * in which case expect_address_[family] is false and + * has_address_[family] is false as well. + */ + if (!has_address_[family] && expect_address_[family]) { + return IN_PROGRESS; + } + // If we do not expect the address, then fall trough to READY + case EXPIRED: // If expired_ok, we pretend to be ready + case READY: + if (!has_address_[family]) { + return UNREACHABLE; + } + break; // OK, we give some answers + case NOT_ASKED: + case UNREACHABLE: + // Reject giving any data + return (getState()); + } + + shared_ptr<NameserverEntry> self(shared_from_this()); + // If any address is OK, just pass everything we have + if (family == ANY_OK) { + BOOST_FOREACH(const AddressEntry& entry, addresses_[V6_ONLY]) { + addresses.push_back(NameserverAddress(self, entry, V6_ONLY)); + } + BOOST_FOREACH(const AddressEntry& entry, addresses_[V4_ONLY]) { + addresses.push_back(NameserverAddress(self, entry, V4_ONLY)); + } + } else { + BOOST_FOREACH(const AddressEntry& entry, addresses_[family]) { + addresses.push_back(NameserverAddress(self, entry, family)); + } + } + if (getState() == EXPIRED && expired_ok) { + return READY; + } + return getState(); +} + +// Return the address corresponding to the family +asiolink::IOAddress +NameserverEntry::getAddressAtIndex(size_t index, AddressFamily family) const { + Lock lock(mutex_); + + assert(index < addresses_[family].size()); + + return (addresses_[family][index].getAddress()); +} + +// Set the address RTT to a specific value +void +NameserverEntry::setAddressRTT(const IOAddress& address, uint32_t rtt) { + Lock lock(mutex_); + + // Search through the list of addresses for a match + AddressFamily family(V4_ONLY); + for (;;) { + BOOST_FOREACH(AddressEntry& entry, addresses_[family]) { + if (entry.getAddress().equal(address)) { + entry.setRTT(rtt); + return; + } + } + + // Hack. C++ does not allow ++ on enums, enumerating trough them is pain + switch (family) { + case V4_ONLY: family = V6_ONLY; break; + default: return; + } + } +} + +// Update the address's rtt +#define UPDATE_RTT_ALPHA 0.7 +void +NameserverEntry::updateAddressRTTAtIndex(uint32_t rtt, size_t index, + AddressFamily family) +{ + Lock lock(mutex_); + + //make sure it is a valid index + if(index >= addresses_[family].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_[family][index].getRTT(); + uint32_t new_rtt = (uint32_t)(old_rtt * UPDATE_RTT_ALPHA + rtt * + (1 - UPDATE_RTT_ALPHA)); + addresses_[family][index].setRTT(new_rtt); +} + +void +NameserverEntry::updateAddressRTT(uint32_t rtt, + const asiolink::IOAddress& address, AddressFamily family) +{ + Lock lock(mutex_); + for (size_t i(0); i < addresses_[family].size(); ++ i) { + if (addresses_[family][i].getAddress().equal(address)) { + updateAddressRTTAtIndex(rtt, i, family); + return; + } + } +} + +// Sets the address to be unreachable +void +NameserverEntry::setAddressUnreachable(const IOAddress& address) { + setAddressRTT(address, AddressEntry::UNREACHABLE); +} + +/** + * \short A callback into the resolver. + * + * Whenever we ask the resolver something, this is created and the answer is + * fed back trough this. It holds a shared pointer to the entry so it is not + * destroyed too soon. + */ +class NameserverEntry::ResolverCallback : public ResolverInterface::Callback { + public: + ResolverCallback(shared_ptr<NameserverEntry> entry, + AddressFamily family, const RRType& type) : + entry_(entry), + family_(family), + type_(type) + { } + /** + * \short We received the address successfully. + * + * This extracts the addresses out from the response and puts them + * inside the entry. It tries to reuse the address entries from before (if there were any), to keep their RTTs. + */ + virtual void success(const shared_ptr<AbstractRRset>& response) { + time_t now = time(NULL); + + Lock lock(entry_->mutex_); + + vector<AddressEntry> entries; + + if (response->getType() != type_ || + response->getClass() != RRClass(entry_->getClass())) + { + // TODO Log we got answer of different type + failureInternal(lock); + return; + } + + for (RdataIteratorPtr i(response->getRdataIterator()); + !i->isLast(); i->next()) + { + // Try to find the original value and reuse it + string address(i->getCurrent().toText()); + AddressEntry *found(NULL); + BOOST_FOREACH(AddressEntry& entry, + entry_->previous_addresses_[family_]) + { + if (entry.getAddress().toText() == address) { + // Good, found it. + found = &entry; + break; + } + } + // If we found it, use it. If not, create a new one. + entries.push_back(found ? *found : AddressEntry(IOAddress( + i->getCurrent().toText()), 1)); + } + + // We no longer need the previous set of addresses, we have + // the current ones now. + entry_->previous_addresses_[family_].clear(); + + if (entries.empty()) { + // No data there, count it as a failure + failureInternal(lock); + } else { + // We received the data, so mark it + entry_->expect_address_[family_] = false; + entry_->expect_address_[ANY_OK] = + entry_->expect_address_[V4_ONLY] || + entry_->expect_address_[V6_ONLY]; + // Everything is here (all address families) + if (!entry_->expect_address_[ANY_OK]) { + entry_->setState(READY); + } + // We have some address + entry_->has_address_[ANY_OK] = + entry_->has_address_[family_] = true; + // Insert the entries inside + entry_->addresses_[family_].swap(entries); + // Update the expiration time. If it is 0, it means we + // did not set it yet, so reset + time_t expiration(now + response->getTTL().getValue()); + if (entry_->expiration_) { + // We expire at the time first address expires + entry_->expiration_ = min(entry_->expiration_, expiration); + } else { + // We have no expiration time set, use this one + entry_->expiration_ = expiration; + } + // Run the right callbacks + dispatchCallbacks(lock); + } + } + /** + * \short The resolver failed to retrieve the data. + * + * So mark the current address family as unreachable. + */ + virtual void failure() { + Lock lock(entry_->mutex_); + failureInternal(lock); + } + private: + shared_ptr<NameserverEntry> entry_; + AddressFamily family_; + RRType type_; + + // Dispatches all relevant callbacks. Keeps lock unlocked afterwards. + // TODO: We might want to use recursive lock and get rid of this + void dispatchCallbacks(Lock& lock) + { + // We dispatch ANY addresses if there is at last one address or + // there's no chance we'll get some in future + bool dispatch_any = entry_->has_address_[ANY_OK] || + !entry_->expect_address_[ANY_OK]; + // Sort out the callbacks we want + vector<CallbackPair> keep; + vector<shared_ptr<NameserverEntry::Callback> > dispatch; + BOOST_FOREACH(const CallbackPair &callback, entry_->callbacks_) + { + if (callback.first == family_ || (dispatch_any && + callback.first == ANY_OK)) + { + dispatch.push_back(callback.second); + } else { + keep.push_back(callback); + } + } + // Put there only the ones that we do not want, drop the rest + keep.swap(entry_->callbacks_); + keep.clear(); + + // We can't keep the lock while we execute callbacks + lock.unlock(); + // Run all the callbacks + /* + * FIXME: This is not completely exception safe. If there's an + * exception in a callback, we lose the rest of them. + */ + BOOST_FOREACH(const shared_ptr<NameserverEntry::Callback>& + callback, dispatch) + { + (*callback)(entry_); + } + } + + // Handle a failure to optain data. Dispatches callbacks and leaves + // lock unlocked + void failureInternal(Lock &lock) { + // Set state of the addresses + entry_->expect_address_[family_] = false; + entry_->expect_address_[ANY_OK] = + entry_->expect_address_[V4_ONLY] || + entry_->expect_address_[V6_ONLY]; + // When we do not expect any more addresses, decide the state + if (!entry_->expect_address_[ANY_OK]) { + if (entry_->has_address_[ANY_OK]) { + // We have at last one kind of address, so OK + entry_->setState(READY); + } else { + // No addresses :-( + entry_->setState(UNREACHABLE); + } + } + // Drop the previous addresses, no use of them now + entry_->previous_addresses_[family_].clear(); + // Dispatch any relevant callbacks + dispatchCallbacks(lock); + } +}; + +void +NameserverEntry::askIP(shared_ptr<ResolverInterface> resolver, + const RRType& type, AddressFamily family) +{ + QuestionPtr question(new Question(Name(getName()), RRClass(getClass()), + type)); + shared_ptr<ResolverCallback> callback(new ResolverCallback( + shared_from_this(), family, type)); + resolver->resolve(question, callback); +} + +void +NameserverEntry::askIP(shared_ptr<ResolverInterface> resolver, + shared_ptr<Callback> callback, AddressFamily family) +{ + Lock lock(mutex_); + + if (getState() == EXPIRED || getState() == NOT_ASKED) { + // We will request the addresses + + // Set internal state first + // We store the old addresses so we can pick their RTT when + // we get the same addresses again (most probably) + previous_addresses_[V4_ONLY].clear(); + previous_addresses_[V6_ONLY].clear(); + addresses_[V4_ONLY].swap(previous_addresses_[V4_ONLY]); + addresses_[V6_ONLY].swap(previous_addresses_[V6_ONLY]); + setState(IN_PROGRESS); + has_address_[V4_ONLY] = has_address_[V6_ONLY] = has_address_[ANY_OK] = + false; + expect_address_[V4_ONLY] = expect_address_[V6_ONLY] = + expect_address_[ANY_OK] = true; + expiration_ = 0; + + // Store the callback + callbacks_.push_back(CallbackPair(family, callback)); + + // Ask for both types of addresses + // We are unlocked here, as the callback from that might want to lock + lock.unlock(); + askIP(resolver, RRType::A(), V4_ONLY); + askIP(resolver, RRType::AAAA(), V6_ONLY); + // Make sure we end the routine when we are not locked + return; + } else { + // We already asked. Do we expect this address type still to come? + if (!expect_address_[family]) { + // We do not expect it to come, dispatch right away + lock.unlock(); + (*callback)(shared_from_this()); + return; + } else { + // It will come in future, store the callback until then + callbacks_.push_back(CallbackPair(family, callback)); + } + } +} + +} // namespace dns +} // namespace isc diff --git a/src/lib/nsas/nameserver_entry.h b/src/lib/nsas/nameserver_entry.h new file mode 100644 index 0000000000..223aca859e --- /dev/null +++ b/src/lib/nsas/nameserver_entry.h @@ -0,0 +1,279 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NAMESERVER_ENTRY_H +#define __NAMESERVER_ENTRY_H + +#include <string> +#include <vector> +#include <boost/thread.hpp> +#include <boost/enable_shared_from_this.hpp> + +#include <exceptions/exceptions.h> +#include <dns/rrset.h> +#include <dns/rrtype.h> + +#include "address_entry.h" +#include "asiolink.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 "nameserver_address.h" + +namespace isc { +namespace nsas { + +class NameserverAddress; + +/// \brief Inconsistent Owner Names +/// +/// Thrown if a NameserverEntry is constructed from both an A and AAAA RRset +/// where the owner names do not match. +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) + {} +}; + +/// \brief Inconsistent Class +/// +/// Thrown if a NameserverEntry is constructed from both an A and AAAA RRset +/// where the classes do not match. +class InconsistentClass : public Exception { +public: + InconsistentClass(const char* file, size_t line, const char* what) : + isc::Exception(file, line, what) + {} +}; + +class ZoneEntry; +class ResolverInterface; + +/// \brief Nameserver Entry +/// +/// Describes a nameserver and its addresses. A nameserver be authoritative +/// for several zones (hence is pointed to by more than one zone entry), and +/// may have several addresses associated with it. +/// +/// The addresses expire after their TTL has been reached. For simplicity, +/// (and because it is unlikely that A and AAAA records from the same zone have +/// different TTLs) there is one expiration time for all address records. +/// When that is reached, all records are declared expired and new fetches +/// started for the information. +/// +/// As this object will be stored in the nameserver address store LRU list, +/// it is derived from the LRU list entry class. +/// +/// It uses shared_from_this in its methods. It must live inside a shared_ptr. + +class NameserverEntry : public NsasEntry<NameserverEntry>, public Fetchable { +public: + /// List of addresses associated with this nameserver + typedef std::vector<NameserverAddress> AddressVector; + typedef AddressVector::iterator AddressVectorIterator; + + /// \brief Constructor where no A records are supplied. + /// + /// \param name Name of the nameserver, + /// \param class_code class of the nameserver + NameserverEntry(const std::string& name, + const isc::dns::RRClass& class_code) : + name_(name), + classCode_(class_code), + expiration_(0) + {} + + /* + * \brief Return Address + * + * Returns a vector of addresses corresponding to this nameserver. + * + * \param addresses Vector of address entries into which will be appended + * addresses that match the specified criteria. (The reason for + * choosing this signature is that addresses from more than one + * nameserver may be retrieved, in which case appending to an existing + * list of addresses is convenient.) + * \param family The family of address that is requested. + * \param expired_ok Return addresses even when expired. This is here + * because an address with TTL 0 is expired at the exact time it + * arrives. But when we call the callback, the owner of callback + * is allowed to use them anyway so it should set expired_ok + * to true. + * \return The state this is currently in. If the TTL expires, it enters + * the EXPIRED state by itself and passes no addresses. It may be + * IN_PROGRESS and still return some addresses (when one address family + * arrived and is is returned, but the other is still on the way). + * \todo Should we sort out unreachable addresses as well? + */ + Fetchable::State getAddresses(AddressVector& addresses, + AddressFamily family = ANY_OK, bool expired_ok = false); + + /// \brief Return Address that corresponding to the index + /// + /// \param index The address index in the address vector + /// \param family The address family, V4_ONLY or V6_ONLY + asiolink::IOAddress getAddressAtIndex(size_t index, + AddressFamily family) const; + + /// \brief Update RTT + /// + /// Updates the RTT for a particular address + /// + /// \param address Address to update + /// \param RTT New RTT for the address + void setAddressRTT(const asiolink::IOAddress& address, uint32_t rtt); + + /// \brief Update RTT of the address that corresponding to the index + /// + /// Shouldn't probably be used directly. Use corresponding + /// NameserverAddress. + /// \param rtt Round-Trip Time + /// \param index The address's index in address vector + /// \param family The address family, V4_ONLY or V6_ONLY + void updateAddressRTTAtIndex(uint32_t rtt, size_t index, + AddressFamily family); + /** + * \short Update RTT of an address. + * + * This is similar to updateAddressRTTAtIndex, but you pass the address, + * not it's index. Passing the index might be unsafe, because the position + * of the address or the cound of addresses may change in time. + * + * \param rtt Round-Trip Time + * \param address The address whose RTT should be updated. + * \param family The address family, V4_ONLY or V6_ONLY + */ + void updateAddressRTT(uint32_t rtt, const asiolink::IOAddress& address, + AddressFamily family); + + /// \brief Set Address Unreachable + /// + /// Sets the specified address to be unreachable + /// + /// \param address Address to update + void setAddressUnreachable(const asiolink::IOAddress& address); + + /// \return Owner Name of RRset + std::string getName() const { + return name_; + } + + /// \return Class of RRset + const isc::dns::RRClass& getClass() const { + return classCode_; + } + + /// \return Hash Key of the Nameserver + virtual HashKey hashKey() const { + return HashKey(name_, classCode_); + } + + /// \return Hash Key of the Nameserver + + /// \return Expiration Time of Data + /// + /// Returns the expiration time of addresses for this nameserver. For + /// simplicity, this quantity is calculated as the minimum expiration time + /// of the A and AAAA address records. + time_t getExpiration() const { + return expiration_; + } + + /// \name Obtaining the IP addresses from resolver + //@{ + /// \short A callback that some information here arrived (or are unavailable). + struct Callback { + virtual void operator()(boost::shared_ptr<NameserverEntry> self) = 0; + /// \short Virtual destructor, so descendants are properly cleaned up + virtual ~ Callback() {} + }; + + /** + * \short Asks the resolver for IP address (or addresses). + * + * Adds a callback for given zone when they are ready or the information + * is found unreachable. + * + * If it is not in NOT_ASKED or EXPIRED state, it does not ask the for the + * IP address again, it just inserts the callback. It is up to the caller + * not to insert one callback multiple times. + * + * The callback might be called directly from this function. + * + * \param resolver Who to ask. + * \param callback The callback. + * \param family Which addresses are interesting to the caller. This does + * not change which adresses are requested, but the callback might + * be executed when at last one requested type is available (eg. not + * waiting for the other one). + * \return The state the entry is currently in. It can return UNREACHABLE + * even when there are addresses, if there are no addresses for this + * family. + */ + void askIP(boost::shared_ptr<ResolverInterface> resolver, + boost::shared_ptr<Callback> callback, AddressFamily family); + //@} + +private: + mutable boost::recursive_mutex mutex_; ///< Mutex protecting this object + std::string name_; ///< Canonical name of the nameserver + isc::dns::RRClass classCode_; ///< Class of the nameserver + /** + * \short Address lists. + * + * Only V4_ONLY and V6_ONLY is used, therefore we use the nearest larger + * value as the size of the array. + * + * previous_addresses is kept until the data arrive again on re-fetch and + * is used to pick up the RTTs from there. + */ + std::vector<AddressEntry> addresses_[ANY_OK], previous_addresses_[ANY_OK]; + time_t expiration_; ///< Summary expiration time. 0 = unset + // Do we have some addresses already? Do we expect some to come? + // These are set after asking for IP, if NOT_ASKED, they are uninitialized + bool has_address_[ADDR_REQ_MAX], expect_address_[ADDR_REQ_MAX]; + // Callbacks from resolver + class ResolverCallback; + friend class ResolverCallback; + // Callbacks inserted into this object + typedef std::pair<AddressFamily, boost::shared_ptr<Callback> > + CallbackPair; + std::vector<CallbackPair> callbacks_; + /// \short Private version that does the actual asking of one address type + /// + /// Call unlocked. + void askIP(boost::shared_ptr<ResolverInterface> resolver, + const isc::dns::RRType&, AddressFamily); +}; + +} // namespace dns +} // namespace isc + +#endif // __NAMESERVER_ENTRY_H diff --git a/src/lib/nsas/nsas_entry.h b/src/lib/nsas/nsas_entry.h new file mode 100644 index 0000000000..57a23843d2 --- /dev/null +++ b/src/lib/nsas/nsas_entry.h @@ -0,0 +1,140 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NSAS_ENTRY_H +#define __NSAS_ENTRY_H + +#include <boost/enable_shared_from_this.hpp> +#include <iostream> + +#include <exceptions/exceptions.h> + +#include "hash_key.h" +#include "hash_table.h" +#include "lru_list.h" + +namespace isc { +namespace nsas { + +/// \brief Invalid Iterator +/// +/// Thrown if an attempt was made to access the iterator - the pointer into +/// the LRU list where this element is located - when it is marked as invalid. +class InvalidLruIterator : public isc::Exception { +public: + InvalidLruIterator(const char* file, size_t line, const char* what) : + Exception(file, line, what) + {} +}; + +/// \brief Element of NSAS Internal Lists +/// +/// This defines an element of the NSAS lists. All elements stored in these +/// lists *MUST* be derived from this object. +/// +/// The class provides two properties: +/// +/// # The method hashKey(), which returns a hash key associated with the +/// object. +/// # Storage for a pointer into the LRU list, used to quickly locate the +/// element when it is being "touched". +/// +/// Although it would be possible to require classes stored in the list +/// to have particular methods (and so eliminate the inheritance), this +/// would require the implementor to know something about the list and to +/// provide the appropriate logic. +/// +/// Unfortunately, using a base class does not simplify the definition of +/// the list classes (by allowing the list to be defined as a list +/// of base class objects), as the lists are a list of shared pointers to +/// objects, not a list of pointers to object. Arguments are shared +/// 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 : public boost::enable_shared_from_this <T> { +public: + + /// \brief Default Constructor + /// + /// Ensures that the handle into the LRU list is invalid. + NsasEntry() : valid_(false) + {} + + /// \brief Virtual Destructor + virtual ~NsasEntry() + {} + + /// Copy constructor and assignment operator OK for this class + + /// \brief Hash Key + /// + /// Returns the hash key for this element. + /// + /// TODO: Consider returning a reference to an internal object, for speed + virtual HashKey hashKey() const = 0; + + /// \brief Sets the iterator of the object + /// + /// Sets the iterator of an object and, as a side effect, marks it as valid. + /// + /// \param iterator Iterator of this element in the list + virtual void setLruIterator(typename LruList<T>::iterator iterator) { + iterator_ = iterator; + valid_ = true; + } + + /// \brief Return Iterator + /// + /// \return iterator Iterator of this element in the list. + /// + /// \exception InvalidLruIterator Thrown if the iterator is not valid. + virtual typename LruList<T>::iterator getLruIterator() const { + if (! valid_) { + isc_throw(InvalidLruIterator, + "pointer of element into LRU list was not valid"); + } + return iterator_; + } + + /// \brief Iterator Valid + /// + /// \return true if the stored iterator is valid. + virtual bool iteratorValid() const { + return valid_; + } + + /// \brief Invalidate Iterator + /// + /// Marks the iterator as invalid; it can oly be set valid again by a call + /// to setLruIterator. + virtual void invalidateIterator() { + valid_ = false; + } + +private: + typename LruList<T>::iterator iterator_; ///< Handle into the LRU List + bool valid_; ///< true if handle is valid +}; + +} // namespace nsas +} // namespace isc + + +#endif // __NSAS_ENTRY_H diff --git a/src/lib/nsas/nsas_entry_compare.h b/src/lib/nsas/nsas_entry_compare.h new file mode 100644 index 0000000000..fdad262eb5 --- /dev/null +++ b/src/lib/nsas/nsas_entry_compare.h @@ -0,0 +1,55 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NSAS_ENTRY_COMPARE_H +#define __NSAS_ENTRY_COMPARE_H + +#include "hash_key.h" +#include "hash_table.h" + +namespace isc { +namespace nsas { + +/// \brief Hash Table Comparison Object +/// +/// The HashTable class requires a comparison object that checks if an object +/// matches a hash key. This check can be generalised for objects derived from +/// NsasEntry, as they all have the hashKey() method; this class takes +/// advantage of that. +template <typename T> +class NsasEntryCompare : public HashTableCompare<T> { +public: + + // The default constructor is OK for this class. + + /// \brief Comparison Function + /// + /// Checks the hash key given against the hash key provided by the NSAS + /// element. + /// + /// \param object Pointer to the object + /// \param key Hash key to compare against. + /// + /// \return true if the object matches the key. + virtual bool operator()(T* object, const HashKey& key) const { + return (object->hashKey() == key); + } +}; + +} // namespace nsas +} // namespace isc + +#endif // __NSAS_ENTRY_COMPARE_H diff --git a/src/lib/nsas/nsas_types.h b/src/lib/nsas/nsas_types.h new file mode 100644 index 0000000000..c4d8355be4 --- /dev/null +++ b/src/lib/nsas/nsas_types.h @@ -0,0 +1,49 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NSAS_TYPES_H +#define __NSAS_TYPES_H + +/// \file nsas_types.h +/// \brief Nameserver Address Store Types +/// +/// Defines a set of types used within the Network Address Store. + +namespace isc { +namespace nsas { + +/** + * \brief Address requested + * + * The order is significant, it is used as array indices and sometime only + * the first two are used. + */ +enum AddressFamily { + /// \short Interested only in IPv4 address + V4_ONLY, + /// \short Interested only in IPv6 address + V6_ONLY, + /// \short Any address is good + ANY_OK, + /// \short Bumper value, does not mean anything, it just represents the + /// max value + ADDR_REQ_MAX +}; + +} +} + +#endif // __NSAS_TYPES_H diff --git a/src/lib/nsas/random_number_generator.h b/src/lib/nsas/random_number_generator.h new file mode 100644 index 0000000000..2b1c144e0e --- /dev/null +++ b/src/lib/nsas/random_number_generator.h @@ -0,0 +1,159 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NSAS_RANDOM_NUMBER_GENERATOR_H +#define __NSAS_RANDOM_NUMBER_GENERATOR_H + +#include <cmath> +#include <numeric> +#include <boost/random/mersenne_twister.hpp> +#include <boost/random/uniform_int.hpp> +#include <boost/random/uniform_real.hpp> +#include <boost/random/variate_generator.hpp> + +namespace isc { +namespace nsas { + +/// \brief Uniform random integer generator +/// +/// Generate uniformly distributed integers in range of [min, max] +class UniformRandomIntegerGenerator{ +public: + /// \brief Constructor + /// + /// \param min The minimum number in the range + /// \param max The maximum number in the range + UniformRandomIntegerGenerator(int min, int max): + min_(min), max_(max), dist_(min, max), generator_(rng_, dist_) + { + // Init with the current time + rng_.seed(time(NULL)); + } + + /// \brief Generate uniformly distributed integer + int operator()() { return generator_(); } +private: + /// Hide default and copy constructor + UniformRandomIntegerGenerator();///< Default constructor + UniformRandomIntegerGenerator(const UniformRandomIntegerGenerator&); ///< Copy constructor + + int min_; ///< The minimum integer that can generate + int max_; ///< The maximum integer that can generate + boost::uniform_int<> dist_; ///< Distribute uniformly. + boost::mt19937 rng_; ///< Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator + boost::variate_generator<boost::mt19937&, boost::uniform_int<> > generator_; ///< Uniform generator +}; + +/// \brief Weighted random integer generator +/// +/// Generate random integers according different probabilities +class WeightedRandomIntegerGenerator { +public: + /// \brief Constructor + /// + /// \param probabilities The probabies for all the integers, the probability must be + /// between 0 and 1.0, the sum of probabilities must be equal to 1. + /// For example, if the probabilities contains the following values: + /// 0.5 0.3 0.2, the 1st integer will be generated more frequently than the + /// other integers and the probability is proportional to its value. + /// \param min The minimum integer that generated, other integers will be + /// min, min + 1, ..., min + probabilities.size() - 1 + WeightedRandomIntegerGenerator(const std::vector<double>& probabilities, + size_t min = 0): + dist_(0, 1.0), uniform_real_gen_(rng_, dist_), min_(min) + { + // The probabilities must be valid + assert(isProbabilitiesValid(probabilities)); + // Calculate the partial sum of probabilities + std::partial_sum(probabilities.begin(), probabilities.end(), + std::back_inserter(cumulative_)); + // Init with the current time + rng_.seed(time(NULL)); + } + + /// \brief Default constructor + /// + WeightedRandomIntegerGenerator(): + dist_(0, 1.0), uniform_real_gen_(rng_, dist_), min_(0) + { + } + + /// \brief Reset the probabilities + /// + /// Change the weights of each integers + /// \param probabilities The probabies for all the integers + /// \param min The minimum integer that generated + void reset(const std::vector<double>& probabilities, size_t min = 0) + { + // The probabilities must be valid + assert(isProbabilitiesValid(probabilities)); + + // Reset the cumulative sum + cumulative_.clear(); + + // Calculate the partial sum of probabilities + std::partial_sum(probabilities.begin(), probabilities.end(), + std::back_inserter(cumulative_)); + + // Reset the minimum integer + min_ = min; + } + + /// \brief Generate weighted random integer + size_t operator()() + { + return std::lower_bound(cumulative_.begin(), cumulative_.end(), uniform_real_gen_()) + - cumulative_.begin() + min_; + } + +private: + /// \brief Check the validation of probabilities vector + /// + /// The probability must be in range of [0, 1.0] and the sum must be equal to 1.0 + /// Empty probabilities is also valid. + bool isProbabilitiesValid(const std::vector<double>& probabilities) const + { + typedef std::vector<double>::const_iterator Iterator; + double sum = probabilities.empty() ? 1.0 : 0.0; + for(Iterator it = probabilities.begin(); it != probabilities.end(); ++it){ + //The probability must be in [0, 1.0] + if(*it < 0.0 || *it > 1.0) { + return false; + } + + sum += *it; + } + + double epsilon = 0.0001; + // The sum must be equal to 1 + return fabs(sum - 1.0) < epsilon; + } + + // Shortcut typedefs + typedef boost::variate_generator<boost::mt19937&, boost::uniform_real<> > UniformRealGenerator; + + std::vector<double> cumulative_; ///< The partial sum of the probabilities + boost::mt19937 rng_; ///< Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator + boost::uniform_real<> dist_; ///< Uniformly distributed real numbers + UniformRealGenerator uniform_real_gen_; ///< Uniformly distributed random real numbers generator + size_t min_; ///< The minimum integer that will be generated +}; + +} // namespace dns +} // namespace isc + + +#endif//__NSAS_RANDOM_NUMBER_GENERATOR_H diff --git a/src/lib/nsas/resolver_interface.h b/src/lib/nsas/resolver_interface.h new file mode 100644 index 0000000000..303b8e4242 --- /dev/null +++ b/src/lib/nsas/resolver_interface.h @@ -0,0 +1,80 @@ +// Copyright (C) 2010 CZ NIC +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $id$ + +#ifndef __RESOLVER_INTERFACE_H +#define __RESOLVER_INTERFACE_H + +#include <dns/message.h> +#include <dns/rrset.h> + +/** + * \file resolver_interface.h + * \short Temporary interface to resolver. + * + * This file contains a dummy interface for the resolver, which does not yet + * exist. When the resolver appears, this file should either wrap its + * interface or, better, be removed completely. + */ + +namespace isc { +namespace nsas { + +/** + * \short Abstract interface to the resolver. + * + * Abstract interface to the resolver. The NameserverAddressStore uses this + * to ask for addresses. It is here because resolver does not yet exist. + * + * It is abstract to allow tests pass dummy resolvers. + */ +class ResolverInterface { + public: + /// \short An abstract callback when data from resolver are ready. + class Callback { + public: + /// \short Some data arrived. + virtual void success( + const boost::shared_ptr<isc::dns::AbstractRRset>& + response) = 0; + /** + * \short No data available. + * + * \todo Pass some reason. + */ + virtual void failure() = 0; + /// \short Virtual destructor, so descendants are cleaned up + virtual ~ Callback() {}; + }; + typedef boost::shared_ptr<Callback> CallbackPtr; + /** + * \short Ask a question. + * + * Asks the resolver a question. Once the answer is ready + * the callback is called. + * + * \param question What to ask. The resolver will decide who. + * \param callback What should happen when the answer is ready. + */ + virtual void resolve(const isc::dns::QuestionPtr& question, + const CallbackPtr& callback) = 0; + /// \short Virtual destructor, so descendants are properly cleaned up + virtual ~ ResolverInterface() {} +}; + +} // namespace nsas +} // namespace isc + +#endif //__RESOLVER_INTERFACE_H diff --git a/src/lib/nsas/tests/Makefile.am b/src/lib/nsas/tests/Makefile.am new file mode 100644 index 0000000000..14c4057332 --- /dev/null +++ b/src/lib/nsas/tests/Makefile.am @@ -0,0 +1,44 @@ +SUBDIRS = . + +AM_CPPFLAGS = -I$(top_builddir)/src/lib -I$(top_srcdir)/src/lib +AM_CPPFLAGS += -I$(top_srcdir)/src/lib/dns -I$(top_builddir)/src/lib/dns +AM_CPPFLAGS += -I$(top_srcdir)/src/lib/nsas -I$(top_builddir)/src/lib/nsas +AM_CXXFLAGS = $(B10_CXXFLAGS) + +AM_LDFLAGS = +if USE_STATIC_LINK +AM_LDFLAGS += -static +endif +AM_LDFLAGS += -lboost_thread + +CLEANFILES = *.gcno *.gcda + +TESTS = +if HAVE_GTEST +TESTS += run_unittests +run_unittests_SOURCES = run_unittests.cc +run_unittests_SOURCES += address_entry_unittest.cc +run_unittests_SOURCES += hash_deleter_unittest.cc +run_unittests_SOURCES += hash_key_unittest.cc +run_unittests_SOURCES += hash_table_unittest.cc +run_unittests_SOURCES += hash_unittest.cc +run_unittests_SOURCES += lru_list_unittest.cc +run_unittests_SOURCES += nameserver_address_unittest.cc +run_unittests_SOURCES += nameserver_address_store_unittest.cc +run_unittests_SOURCES += nameserver_entry_unittest.cc +run_unittests_SOURCES += nsas_entry_compare_unittest.cc +run_unittests_SOURCES += nsas_test.h +run_unittests_SOURCES += zone_entry_unittest.cc +run_unittests_SOURCES += fetchable_unittest.cc +run_unittests_SOURCES += random_number_generator_unittest.cc + +run_unittests_CPPFLAGS = $(AM_CPPFLAGS) $(GTEST_INCLUDES) +run_unittests_LDFLAGS = $(AM_LDFLAGS) $(GTEST_LDFLAGS) +run_unittests_LDADD = $(GTEST_LDADD) + +run_unittests_LDADD += $(top_builddir)/src/lib/nsas/libnsas.la +run_unittests_LDADD += $(top_builddir)/src/lib/dns/libdns++.la +run_unittests_LDADD += $(top_builddir)/src/lib/exceptions/libexceptions.la +endif + +noinst_PROGRAMS = $(TESTS) diff --git a/src/lib/nsas/tests/address_entry_unittest.cc b/src/lib/nsas/tests/address_entry_unittest.cc new file mode 100644 index 0000000000..7947dbcf75 --- /dev/null +++ b/src/lib/nsas/tests/address_entry_unittest.cc @@ -0,0 +1,116 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <limits.h> +#include <gtest/gtest.h> + +// Need to define the following macro to get UINT32_MAX +#ifndef __STDC_LIMIT_MACROS +#define __STDC_LIMIT_MACROS +#endif +#include <stdint.h> + + +#include "../asiolink.h" +#include "../address_entry.h" + +static std::string V4A_TEXT("1.2.3.4"); +static std::string V4B_TEXT("5.6.7.8"); +static std::string V6A_TEXT("2001:dead:beef::0"); +static std::string V6B_TEXT("1984:1985::1986:1987"); + +using namespace asiolink; +using namespace std; +using namespace isc::nsas; + +/// \brief Test Fixture Class +/// +/// Constructs four IOAddress objects, two V4 addresses and two V6 addresses. +/// They are initialised in the constructor owing to the restrictions of +/// the IOAddress class. + +class AddressEntryTest : public ::testing::Test { +protected: + AddressEntryTest() : + v4a_(V4A_TEXT), v4b_(V4B_TEXT), + v6a_(V6A_TEXT), v6b_(V6B_TEXT) + {} + + IOAddress v4a_; ///< First V4 address + IOAddress v4b_; ///< Second V4 address + IOAddress v6a_; ///< First V6 address + IOAddress v6b_; ///< Second V6 address +}; + +/// Tests of the various constructors +TEST_F(AddressEntryTest, Constructor) { + + // Basic constructor with V4 address + AddressEntry alpha(v4a_); + EXPECT_EQ(V4A_TEXT, alpha.getAddress().toText()); + EXPECT_EQ(0, alpha.getRTT()); + + // General constructor with V4 address + AddressEntry beta(v4b_, 42); + EXPECT_EQ(V4B_TEXT, beta.getAddress().toText()); + EXPECT_EQ(42, beta.getRTT()); + + // Basic constructor with V6 address + AddressEntry gamma(v6a_); + EXPECT_EQ(V6A_TEXT, gamma.getAddress().toText()); + EXPECT_EQ(0, gamma.getRTT()); + + // General constructor with V6 address + AddressEntry delta(v6b_, 75); + EXPECT_EQ(V6B_TEXT, delta.getAddress().toText()); + EXPECT_EQ(75, delta.getRTT()); +} + +/// Setting and getting the round-trip time. Also includes unreachable +/// checks. +TEST_F(AddressEntryTest, RTT) { + + AddressEntry alpha(v4a_); + EXPECT_EQ(0, alpha.getRTT()); + + // Check set and get of RTT + long rtt = 1276; + alpha.setRTT(rtt); + EXPECT_EQ(rtt, alpha.getRTT()); + + // Check unreachability + alpha.setUnreachable(); + EXPECT_TRUE(alpha.isUnreachable()); + + alpha.setRTT(27); + EXPECT_FALSE(alpha.isUnreachable()); + + // ... and check the implementation of unreachability + alpha.setUnreachable(); + EXPECT_EQ(AddressEntry::UNREACHABLE, alpha.getRTT()); +} + +/// Checking the address type. +TEST_F(AddressEntryTest, AddressType) { + + AddressEntry alpha(v4a_); + EXPECT_TRUE(alpha.isV4()); + EXPECT_FALSE(alpha.isV6()); + + AddressEntry beta(v6a_); + EXPECT_FALSE(beta.isV4()); + EXPECT_TRUE(beta.isV6()); +} diff --git a/src/lib/nsas/tests/fetchable_unittest.cc b/src/lib/nsas/tests/fetchable_unittest.cc new file mode 100644 index 0000000000..88b55869a6 --- /dev/null +++ b/src/lib/nsas/tests/fetchable_unittest.cc @@ -0,0 +1,34 @@ +// Copyright (C) 2010 CZ NIC +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $id$ + +#include "../fetchable.h" + +#include <gtest/gtest.h> + +using namespace isc::nsas; + +namespace { + +TEST(Fetchable, accessMethods) { + Fetchable f; + EXPECT_EQ(Fetchable::NOT_ASKED, f.getState()); + f.setState(Fetchable::IN_PROGRESS); + EXPECT_EQ(Fetchable::IN_PROGRESS, f.getState()); + Fetchable funr(Fetchable::UNREACHABLE); + EXPECT_EQ(Fetchable::UNREACHABLE, funr.getState()); +} + +} diff --git a/src/lib/nsas/tests/hash_deleter_unittest.cc b/src/lib/nsas/tests/hash_deleter_unittest.cc new file mode 100644 index 0000000000..0d5d1f512c --- /dev/null +++ b/src/lib/nsas/tests/hash_deleter_unittest.cc @@ -0,0 +1,116 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <algorithm> +#include <string> +#include <vector> + +#include <gtest/gtest.h> +#include <boost/lexical_cast.hpp> + +#include <dns/rrclass.h> + +#include "../nsas_entry.h" +#include "../hash_table.h" +#include "../hash_key.h" +#include "../lru_list.h" +#include "../hash_deleter.h" + +#include "nsas_test.h" +#include "../nsas_entry_compare.h" + +using namespace std; +using namespace isc::dns; + +namespace isc { +namespace nsas { + + +/// \brief Text Fixture Class +class HashDeleterTest : public ::testing::Test { +protected: + HashDeleterTest() : + entry1_(new TestEntry("alpha", RRClass::IN())), + entry2_(new TestEntry("beta", RRClass::CH())), + entry3_(new TestEntry("gamma", RRClass::HS())), + entry4_(new TestEntry("delta", RRClass::IN())), + entry5_(new TestEntry("epsilon", RRClass::CH())), + entry6_(new TestEntry("zeta", RRClass::HS())), + entry7_(new TestEntry("eta", RRClass::IN())), + hash_table_(new NsasEntryCompare<TestEntry>()), + lru_list_(3, new HashDeleter<TestEntry>(hash_table_)) + {} + + + boost::shared_ptr<TestEntry> entry1_; + boost::shared_ptr<TestEntry> entry2_; + boost::shared_ptr<TestEntry> entry3_; + boost::shared_ptr<TestEntry> entry4_; + boost::shared_ptr<TestEntry> entry5_; + boost::shared_ptr<TestEntry> entry6_; + boost::shared_ptr<TestEntry> entry7_; + + HashTable<TestEntry> hash_table_; ///< Hash table being tested + LruList<TestEntry> lru_list_; ///< Associated LRU list +}; + + +// Basic test. The test of the constructor etc. have been done in the test +// fixture class. +TEST_F(HashDeleterTest, Constructor) { + + // Add entry1 to both the hash table and the LRU list + EXPECT_EQ(1, entry1_.use_count()); + hash_table_.add(entry1_, entry1_->hashKey()); + EXPECT_EQ(2, entry1_.use_count()); + lru_list_.add(entry1_); + EXPECT_EQ(3, entry1_.use_count()); + + // Add entry 2. + EXPECT_EQ(1, entry2_.use_count()); + hash_table_.add(entry2_, entry2_->hashKey()); + EXPECT_EQ(2, entry2_.use_count()); + lru_list_.add(entry2_); + EXPECT_EQ(3, entry2_.use_count()); + + // Add entry 3. + EXPECT_EQ(1, entry3_.use_count()); + hash_table_.add(entry3_, entry3_->hashKey()); + EXPECT_EQ(2, entry3_.use_count()); + lru_list_.add(entry3_); + EXPECT_EQ(3, entry3_.use_count()); + + // Adding entry 4 should drop entry 1 from the list and from the + // associated hash table. + + // Add entry 4. + EXPECT_EQ(1, entry4_.use_count()); + hash_table_.add(entry4_, entry4_->hashKey()); + EXPECT_EQ(2, entry4_.use_count()); + lru_list_.add(entry4_); + EXPECT_EQ(3, entry4_.use_count()); + + // Entry 1 should only be referred to by the text fixture, being removed + // from both the LRU list and the hash table. + EXPECT_EQ(1, entry1_.use_count()); + + // ... and check that is does not exist in the table. + boost::shared_ptr<TestEntry> x = hash_table_.get(entry1_->hashKey()); + EXPECT_FALSE(x); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/hash_key_unittest.cc b/src/lib/nsas/tests/hash_key_unittest.cc new file mode 100644 index 0000000000..80013e3e55 --- /dev/null +++ b/src/lib/nsas/tests/hash_key_unittest.cc @@ -0,0 +1,86 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <algorithm> +#include <string> +#include <vector> + +#include <gtest/gtest.h> +#include <boost/lexical_cast.hpp> + +#include "../hash_key.h" +#include <dns/rrclass.h> + +using namespace std; +using namespace isc::dns; + +namespace isc { +namespace nsas { + +/// \brief Test Fixture Class +class HashKeyTest : public ::testing::Test { +}; + + +// Test of the constructor +TEST_F(HashKeyTest, Constructor) { + + // Basic constructor + string test1("ABCDEF"); + HashKey key1(test1.c_str(), test1.size(), RRClass::IN()); + EXPECT_EQ(key1.key, test1.c_str()); + EXPECT_EQ(key1.keylen, test1.size()); + EXPECT_EQ(key1.class_code, RRClass::IN()); + + // String constructor + string test2("uvwxyz"); + HashKey key2(test2, RRClass::CH()); + EXPECT_EQ(key2.key, test2.c_str()); + EXPECT_EQ(key2.keylen, test2.size()); + EXPECT_EQ(key2.class_code, RRClass::CH()); +} + +// Equality check +TEST_F(HashKeyTest, Equality) { + string test1("abcdef123"); // Simple string + string test2("abcdef123"); // Same key, different object + string test3("AbCdEf123"); // Same key, different case (unequal) + string test4("ABCDE123"); // Different key (almost same) + string test5("uvwxyz987"); // Different key + + EXPECT_TRUE(HashKey(test1, RRClass::IN()) == HashKey(test1, + RRClass::IN())); // Same key and class + EXPECT_FALSE(HashKey(test1, RRClass::IN()) == HashKey(test1, + RRClass::CH())); // Different class + + EXPECT_TRUE(HashKey(test1, RRClass::CH()) == HashKey(test2, + RRClass::CH())); // Same value key/class + EXPECT_FALSE(HashKey(test1, RRClass::CH()) == HashKey(test2, + RRClass::IN())); + + EXPECT_TRUE(HashKey(test1, RRClass::HS()) == HashKey(test3, + RRClass::HS())); // Same key + EXPECT_FALSE(HashKey(test1, RRClass::HS()) == HashKey(test3, + RRClass::IN())); + + EXPECT_FALSE(HashKey(test1, RRClass::IN()) == HashKey(test4, + RRClass::IN())); + EXPECT_FALSE(HashKey(test1, RRClass::IN()) == HashKey(test5, + RRClass::IN())); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/hash_table_unittest.cc b/src/lib/nsas/tests/hash_table_unittest.cc new file mode 100644 index 0000000000..caec2dcef8 --- /dev/null +++ b/src/lib/nsas/tests/hash_table_unittest.cc @@ -0,0 +1,256 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <gtest/gtest.h> +#include <boost/shared_ptr.hpp> +#include <boost/bind.hpp> + +#include <string.h> +#include <iostream> + +#include <dns/rrclass.h> + +#include "../hash_table.h" +#include "../hash_key.h" + +#include "../nsas_entry_compare.h" +#include "nsas_test.h" + +using namespace std; +using boost::shared_ptr; +using namespace isc::dns; + +namespace isc { +namespace nsas { + +/// \brief Text Fixture Class +/// +/// Many of the tests are based on checking reference counts. In all tests, +/// objects named dummyN_ have a reference count of 1 because they are a member +/// of this class which has been instantiated for the test. The reference count +/// is increased as they are added to the hash table for testing and decreased +/// as they are removed. +class HashTableTest : public ::testing::Test { +protected: + + // Constructor - initialize the objects + HashTableTest() : + table_(new NsasEntryCompare<TestEntry>()), + dummy1_(new TestEntry("test", RRClass::IN())), + dummy2_(new TestEntry("test", RRClass::IN())), + dummy3_(new TestEntry("Something_Else", RRClass::IN())), + dummy4_(new TestEntry("test", RRClass::CH())) + {} + + // Members. + HashTable<TestEntry> table_; + boost::shared_ptr<TestEntry> dummy1_; + boost::shared_ptr<TestEntry> dummy2_; + boost::shared_ptr<TestEntry> dummy3_; + boost::shared_ptr<TestEntry> dummy4_; +}; + + +// Test of the constructor +TEST_F(HashTableTest, Constructor) { + + // Default constructor + HashTable<TestEntry> table1(new NsasEntryCompare<TestEntry>()); + EXPECT_EQ(HASHTABLE_DEFAULT_SIZE, table1.tableSize()); + + // Non default constructor + EXPECT_NE(42, HASHTABLE_DEFAULT_SIZE); + HashTable<TestEntry> table2(new NsasEntryCompare<TestEntry>(), 42); + EXPECT_EQ(42, table2.tableSize()); +} + + +// Basic test of addition +TEST_F(HashTableTest, AddTest) { + + // Using two objects with the same name and class, + EXPECT_EQ(dummy1_->getName(), dummy2_->getName()); + EXPECT_EQ(dummy1_->getClass(), dummy2_->getClass()); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(1, dummy2_.use_count()); + + // Add first one to the hash table_ + bool result = table_.add(dummy1_, dummy1_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(2, dummy1_.use_count()); + EXPECT_EQ(1, dummy2_.use_count()); + + // Attempt to add the second object with the same name and class fails. + result = table_.add(dummy2_, dummy2_->hashKey()); + EXPECT_FALSE(result); + EXPECT_EQ(2, dummy1_.use_count()); + EXPECT_EQ(1, dummy2_.use_count()); + + // Replacing an entry should work though + result = table_.add(dummy2_, dummy2_->hashKey(), true); + EXPECT_TRUE(result); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(2, dummy2_.use_count()); +} + +// Test the remove functionality +TEST_F(HashTableTest, RemoveTest) { + + // Using two objects with different names but the same class + EXPECT_NE(dummy1_->getName(), dummy3_->getName()); + EXPECT_EQ(dummy1_->getClass(), dummy3_->getClass()); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(1, dummy3_.use_count()); + + // Add first one to the hash table_ + bool result = table_.add(dummy1_, dummy1_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(2, dummy1_.use_count()); + EXPECT_EQ(1, dummy3_.use_count()); + + // Now remove it. + result = table_.remove(dummy1_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(1, dummy3_.use_count()); + + // Attempt to remove it again. + result = table_.remove(dummy1_->hashKey()); + EXPECT_FALSE(result); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(1, dummy3_.use_count()); + + // Add both entries to table_, then remove one (checks that it will + // remove the correct one). + result = table_.add(dummy1_, dummy1_->hashKey()); + EXPECT_TRUE(result); + result = table_.add(dummy3_, dummy3_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(2, dummy1_.use_count()); + EXPECT_EQ(2, dummy3_.use_count()); + + result = table_.remove(dummy1_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(2, dummy3_.use_count()); +} + +// Test the "get" functionality +TEST_F(HashTableTest, GetTest) { + + // Using two objects with different names but the same class + EXPECT_NE(dummy1_->getName(), dummy3_->getName()); + EXPECT_EQ(dummy1_->getClass(), dummy3_->getClass()); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(1, dummy3_.use_count()); + + // Add both to the hash table + bool result = table_.add(dummy1_, dummy1_->hashKey()); + EXPECT_TRUE(result); + result = table_.add(dummy3_, dummy3_->hashKey()); + EXPECT_TRUE(result); + + // Lookup the first + boost::shared_ptr<TestEntry> value = table_.get(dummy1_->hashKey()); + EXPECT_EQ(value.get(), dummy1_.get()); + + // ... and the second + value = table_.get(dummy3_->hashKey()); + EXPECT_EQ(value.get(), dummy3_.get()); + + // Remove the first + result = table_.remove(dummy1_->hashKey()); + EXPECT_TRUE(result); + + // ... and a lookup should return empty + value = table_.get(dummy1_->hashKey()); + EXPECT_TRUE(value.get() == NULL); +} + +shared_ptr<TestEntry> +pass(shared_ptr<TestEntry> value) { + return (value); +} + +TEST_F(HashTableTest, GetOrAddTest) { + // Add one entry + EXPECT_TRUE(table_.add(dummy1_, dummy1_->hashKey())); + + // Check it looks it up + std::pair<bool, shared_ptr<TestEntry> > result = table_.getOrAdd( + dummy1_->hashKey(), boost::bind(pass, dummy3_)); + EXPECT_FALSE(result.first); + EXPECT_EQ(dummy1_.get(), result.second.get()); + + // Check it says it adds the value + result = table_.getOrAdd(dummy3_->hashKey(), boost::bind(pass, dummy3_)); + EXPECT_TRUE(result.first); + EXPECT_EQ(dummy3_.get(), result.second.get()); + + // Check it really did add it + EXPECT_EQ(dummy3_.get(), table_.get(dummy3_->hashKey()).get()); +} + +// Test that objects with the same name and different classes are distinct. +TEST_F(HashTableTest, ClassTest) { + + // Using two objects with the same name and different classes + EXPECT_EQ(dummy1_->getName(), dummy4_->getName()); + EXPECT_NE(dummy1_->getClass(), dummy4_->getClass()); + EXPECT_EQ(1, dummy1_.use_count()); + EXPECT_EQ(1, dummy4_.use_count()); + + // Add both to the hash table + bool result = table_.add(dummy1_, dummy1_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(2, dummy1_.use_count()); + + result = table_.add(dummy4_, dummy4_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(2, dummy4_.use_count()); + + // Lookup the first + boost::shared_ptr<TestEntry> value1 = table_.get(dummy1_->hashKey()); + EXPECT_EQ(value1.get(), dummy1_.get()); + EXPECT_EQ(3, dummy1_.use_count()); + EXPECT_EQ(2, dummy4_.use_count()); + + // ... and the second + boost::shared_ptr<TestEntry> value4 = table_.get(dummy4_->hashKey()); + EXPECT_EQ(value4.get(), dummy4_.get()); + EXPECT_EQ(3, dummy1_.use_count()); + EXPECT_EQ(3, dummy4_.use_count()); + + // ... and check they are different + EXPECT_NE(dummy1_.get(), dummy4_.get()); + + // Remove the first + result = table_.remove(dummy1_->hashKey()); + EXPECT_TRUE(result); + EXPECT_EQ(2, dummy1_.use_count()); + EXPECT_EQ(3, dummy4_.use_count()); + + // ... and a lookup should return empty + boost::shared_ptr<TestEntry> value1a = table_.get(dummy1_->hashKey()); + EXPECT_TRUE(value1a.get() == NULL); +} + + + + + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/hash_unittest.cc b/src/lib/nsas/tests/hash_unittest.cc new file mode 100644 index 0000000000..fc914faba1 --- /dev/null +++ b/src/lib/nsas/tests/hash_unittest.cc @@ -0,0 +1,194 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <algorithm> +#include <string> +#include <vector> + +#include <gtest/gtest.h> +#include <boost/lexical_cast.hpp> + +#include "../hash.h" + +#include "nsas_test.h" + +using namespace std; + +namespace isc { +namespace nsas { + +// Utility function to count the number of unique values in a vector +static uint32_t CountUnique(const vector<uint32_t>& input) { + + // Duplicate the vector as this will be destroyed in the process. + vector<uint32_t> vcopy(input); + + // Check to see if values are unique. Do this by sorting the values into + // ascending order, removing duplicates, and checking the size again. + // + // Note that "unique" only shifts elements around - it does not remove non- + // unique values, so it does not change the size of the vector. The call to + // erase removes the elements between the last unique element and the end + // of the vector, so shrinking the vector. + sort(vcopy.begin(), vcopy.end()); + vcopy.erase(unique(vcopy.begin(), vcopy.end()), vcopy.end()); + + // ... and return the count of elements remaining. + return (vcopy.size()); +} + + +/// \brief Test Fixture Class +class HashTest : public ::testing::Test { +}; + + +// Test of the constructor +TEST_F(HashTest, Constructor) { + + // Default constructor + Hash hash1(HASHTABLE_DEFAULT_SIZE, 250); + EXPECT_EQ(HASHTABLE_DEFAULT_SIZE, hash1.tableSize()); + EXPECT_EQ(250, hash1.maxKeyLength()); +} + +// Test of the hash algorithm. Without duplicating the code for the algorithm +// here, testing is a bit awkward. So the tests will check that a series of +// names get hashed to different values. (Choosing a HASHTABLE_DEFAULT_SIZE element array should +// give minimal overlap; we'll allow for a maximum of 2 collisions with 50 +// similar names. If there are more, perhaps the algorithm is at fault. + +TEST_F(HashTest, Algorithm) { + + const int size = HASHTABLE_DEFAULT_SIZE; // Size of the hash table + Hash hash(size, 255, false);// Hashing algorithm object with seed + // randomisation disabled + string base = "alphabeta"; // Base of the names to behashed + vector<uint32_t> values; // Results stored here + + // Generate hash values + for (int i = 0; i < 50; ++i) { + string name = base + boost::lexical_cast<string>(i); + uint32_t hashval = hash(HashKey(name.c_str(), name.size(), + RRClass(0))); + EXPECT_LT(hashval, size); + values.push_back(hashval); + } + uint32_t cursize = values.size(); + + // Count the unique values in the array + uint32_t newsize = CountUnique(values); + + // We don't expect many clashes. + EXPECT_GE(newsize + 2, cursize); +} + +// Test the case mapping function. + +TEST_F(HashTest, CaseMapping) { + + Hash hash(HASHTABLE_DEFAULT_SIZE, 255); + + // Check all unsigned characters + for (int i = 0; i < 255; ++i) { + if ((i >= 'A') && (i <= 'Z')) { + EXPECT_EQ(static_cast<unsigned char>(i - 'A' + 'a'), + hash.mapLower((unsigned char)i)); + } + else { + EXPECT_EQ(i, hash.mapLower(i)); + } + } +} + +// Test the mapping of mixed-case names +TEST_F(HashTest, MixedCase) { + + std::string test1 = "example1234.co.uk."; + std::string test2 = "EXAmple1234.co.uk."; + + Hash hash(HASHTABLE_DEFAULT_SIZE, 255, false); // Disable randomisation for testing + + // Case not ignored, hashes should be different + uint32_t value1 = hash(HashKey(test1.c_str(), test1.size(), RRClass::IN()), + false); + uint32_t value2 = hash(HashKey(test2.c_str(), test2.size(), RRClass::IN()), + false); + EXPECT_NE(value1, value2); + + // Case ignored, hashes should be the same + uint32_t value3 = hash(HashKey(test1.c_str(), test1.size(), RRClass::IN()), + true); + uint32_t value4 = hash(HashKey(test2.c_str(), test2.size(), RRClass::IN()), + true); + EXPECT_EQ(value3, value4); + + // Check the default setting. + uint32_t value5 = hash(HashKey(test1.c_str(), test1.size(), RRClass::IN())); + uint32_t value6 = hash(HashKey(test2.c_str(), test2.size(), RRClass::IN())); + EXPECT_EQ(value5, value6); + + // ... and just for good measure + EXPECT_EQ(value1, value3); + EXPECT_EQ(value1, value5); +} + +// Test that the same name but different classes get mapped differently. +TEST_F(HashTest, ClassCodes) { + + std::string test1 = "example1234.co.uk."; + Hash hash(HASHTABLE_DEFAULT_SIZE, 255, false); // Disable randomisation for testing + + // Just try codes in the range 0 to 9 - more than covers the allocated + // codes. + vector<uint32_t> values; + for (uint32_t i = 0; i < 10; ++i) { + values.push_back(hash(HashKey(test1.c_str(), test1.size(), + RRClass(i)))); + } + + // find the number of unique values in the array. Although there can + // be some clashes, we don't expect too many. + uint32_t cursize = values.size(); + + // Count the unique values in the array + uint32_t newsize = CountUnique(values); + + // We don't expect many clashes. + EXPECT_GE(newsize + 2, cursize); +} + + +// Test that the code performs when the length of the key is excessive +TEST_F(HashTest, Overlong) { + + // String 1 is a suitable prefix, string 2 is the same prefix plus 4096 + // repetions of the character 'x'. + std::string string1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ012345"; + std::string string2 = string1 + string(4096, 'x'); + + Hash hash(HASHTABLE_DEFAULT_SIZE, string1.size()); + + // Do two hashes + uint32_t value1 = hash(HashKey(string1.c_str(), string1.size(), + RRClass(0))); + uint32_t value2 = hash(HashKey(string2.c_str(), string2.size(), + RRClass(0))); + EXPECT_EQ(value1, value2); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/lru_list_unittest.cc b/src/lib/nsas/tests/lru_list_unittest.cc new file mode 100644 index 0000000000..1efae54814 --- /dev/null +++ b/src/lib/nsas/tests/lru_list_unittest.cc @@ -0,0 +1,289 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <iostream> +#include <algorithm> +#include <string> +#include <vector> + +#include <gtest/gtest.h> +#include <boost/lexical_cast.hpp> + +#include "../nsas_entry.h" +#include "../lru_list.h" + +#include "nsas_test.h" + +using namespace std; + +namespace isc { +namespace nsas { + +/// \brief Dropped Functor Class +/// +/// Functor object is called when an object is dropped from the LRU list. +/// To prove that it has run, this function does nothing more than set the +/// MS bit on the 16-bit class value. +class Dropped : public LruList<TestEntry>::Dropped { +public: + virtual void operator()(TestEntry* entry) const { + entry->setClass(RRClass(entry->getClass().getCode() | 0x8000)); + } +}; + + +/// \brief Text Fixture Class +class LruListTest : public ::testing::Test { +protected: + LruListTest() : + entry1_(new TestEntry("alpha", RRClass::IN())), + entry2_(new TestEntry("beta", RRClass::CH())), + entry3_(new TestEntry("gamma", RRClass::HS())), + entry4_(new TestEntry("delta", RRClass::IN())), + entry5_(new TestEntry("epsilon", RRClass::HS())), + entry6_(new TestEntry("zeta", RRClass::CH())), + entry7_(new TestEntry("eta", RRClass::IN())) + {} + + virtual ~LruListTest() + {} + + boost::shared_ptr<TestEntry> entry1_; + boost::shared_ptr<TestEntry> entry2_; + boost::shared_ptr<TestEntry> entry3_; + boost::shared_ptr<TestEntry> entry4_; + boost::shared_ptr<TestEntry> entry5_; + boost::shared_ptr<TestEntry> entry6_; + boost::shared_ptr<TestEntry> entry7_; +}; + + +// Test of the constructor +TEST_F(LruListTest, Constructor) { + LruList<TestEntry> lru(100); + EXPECT_EQ(100, lru.getMaxSize()); + EXPECT_EQ(0, lru.size()); +} + +// Test of Get/Set the maximum number of entrys +TEST_F(LruListTest, GetSet) { + LruList<TestEntry> lru(100); + EXPECT_EQ(100, lru.getMaxSize()); + lru.setMaxSize(42); + EXPECT_EQ(42, lru.getMaxSize()); +} + +// Test that adding an entry really does add an entry +TEST_F(LruListTest, Add) { + LruList<TestEntry> lru(100); + EXPECT_EQ(0, lru.size()); + + lru.add(entry1_); + EXPECT_EQ(1, lru.size()); + + lru.add(entry2_); + EXPECT_EQ(2, lru.size()); +} + +// Test that removing an entry really does remove it. +TEST_F(LruListTest, Remove) { + LruList<TestEntry> lru(100); + EXPECT_EQ(0, lru.size()); + + EXPECT_FALSE(entry1_->iteratorValid()); + lru.add(entry1_); + EXPECT_TRUE(entry1_->iteratorValid()); + EXPECT_EQ(1, lru.size()); + + EXPECT_FALSE(entry2_->iteratorValid()); + lru.add(entry2_); + EXPECT_TRUE(entry2_->iteratorValid()); + EXPECT_EQ(2, lru.size()); + + lru.remove(entry1_); + EXPECT_FALSE(entry1_->iteratorValid()); + EXPECT_EQ(1, lru.size()); +} + +// Check that adding a new entry to a limited size list does delete the +// oldest entry from the list. +TEST_F(LruListTest, SizeLimit) { + LruList<TestEntry> lru(3); + EXPECT_EQ(0, lru.size()); + + // Add first entry and check that the shared pointer's reference count + // has increased. There will be two references: one from the "entry1_" + // member in the test fixture class, and one from the list. + EXPECT_EQ(1, entry1_.use_count()); + lru.add(entry1_); + EXPECT_EQ(2, entry1_.use_count()); + EXPECT_EQ(1, lru.size()); + + // Same for entry 2. + EXPECT_EQ(1, entry2_.use_count()); + lru.add(entry2_); + EXPECT_EQ(2, entry2_.use_count()); + EXPECT_EQ(2, lru.size()); + + // Same for entry 3. + EXPECT_EQ(1, entry3_.use_count()); + lru.add(entry3_); + EXPECT_EQ(2, entry3_.use_count()); + EXPECT_EQ(3, lru.size()); + + // Adding entry 4 should remove entry 1 from the list. This will + // delete the list's shared pointer to the entry and will therefore + // drop the reference count back to one (from the "entry1_" member in + // the text fixture class). + EXPECT_EQ(2, entry1_.use_count()); + EXPECT_EQ(1, entry4_.use_count()); + lru.add(entry4_); + EXPECT_EQ(1, entry1_.use_count()); + EXPECT_EQ(2, entry4_.use_count()); + EXPECT_EQ(3, lru.size()); + + // Adding entry 5 should remove entry 2 from the list. + EXPECT_EQ(2, entry2_.use_count()); + EXPECT_EQ(1, entry5_.use_count()); + lru.add(entry5_); + EXPECT_EQ(1, entry2_.use_count()); + EXPECT_EQ(2, entry5_.use_count()); + EXPECT_EQ(3, lru.size()); +} + +// Check that "touching" an entry adds it to the back of the list. +TEST_F(LruListTest, Touch) { + + // Create the list + LruList<TestEntry> lru(3); + EXPECT_EQ(0, lru.size()); + lru.add(entry1_); + lru.add(entry2_); + lru.add(entry3_); + + // Check the reference counts of the entrys and the list size + EXPECT_EQ(2, entry1_.use_count()); + EXPECT_EQ(2, entry2_.use_count()); + EXPECT_EQ(2, entry3_.use_count()); + EXPECT_EQ(1, entry4_.use_count()); + EXPECT_EQ(1, entry5_.use_count()); + EXPECT_EQ(1, entry6_.use_count()); + EXPECT_EQ(1, entry7_.use_count()); + EXPECT_EQ(3, lru.size()); + + // "Touch" the first entry + lru.touch(entry1_); + + // Adding two more entries should not remove the touched entry. + lru.add(entry4_); + lru.add(entry5_); + + // Check the status of the entrys and the list. + EXPECT_EQ(2, entry1_.use_count()); + EXPECT_EQ(1, entry2_.use_count()); + EXPECT_EQ(1, entry3_.use_count()); + EXPECT_EQ(2, entry4_.use_count()); + EXPECT_EQ(2, entry5_.use_count()); + EXPECT_EQ(1, entry6_.use_count()); + EXPECT_EQ(1, entry7_.use_count()); + EXPECT_EQ(3, lru.size()); + + // Now touch the entry agin to move it to the back of the list. + // This checks that the iterator stored in the entry as a result of the + // last touch operation is valid. + lru.touch(entry1_); + + // Check this by adding two more entrys and checking reference counts + // to see what is stored. + lru.add(entry6_); + lru.add(entry7_); + + EXPECT_EQ(2, entry1_.use_count()); + EXPECT_EQ(1, entry2_.use_count()); + EXPECT_EQ(1, entry3_.use_count()); + EXPECT_EQ(1, entry4_.use_count()); + EXPECT_EQ(1, entry5_.use_count()); + EXPECT_EQ(2, entry6_.use_count()); + EXPECT_EQ(2, entry7_.use_count()); + EXPECT_EQ(3, lru.size()); +} + +// Dropped functor tests: tests that the function object is called when an +// object expires from the list. +TEST_F(LruListTest, Dropped) { + + // Create an object with an expiration handler. + LruList<TestEntry> lru(3, new Dropped()); + + // Fill the list + lru.add(entry1_); + lru.add(entry2_); + lru.add(entry3_); + + EXPECT_EQ(RRClass::IN(), entry1_->getClass()); + EXPECT_EQ(RRClass::CH(), entry2_->getClass()); + + // Add another entry and check that the handler runs. + EXPECT_EQ(0, (entry1_->getClass().getCode() & 0x8000)); + lru.add(entry4_); + EXPECT_NE(0, (entry1_->getClass().getCode() & 0x8000)); + + EXPECT_EQ(0, (entry2_->getClass().getCode() & 0x8000)); + lru.add(entry5_); + EXPECT_NE(0, (entry2_->getClass().getCode() & 0x8000)); + + // Delete an entry and check that the handler does not run. + EXPECT_EQ(0, (entry3_->getClass().getCode() & 0x8000)); + lru.remove(entry3_); + EXPECT_EQ(0, (entry3_->getClass().getCode() & 0x8000)); +} + +// Miscellaneous tests - pathological conditions +TEST_F(LruListTest, Miscellaneous) { + + // Zero size list should not allow entrys to be added + LruList<TestEntry> lru_1(0); + lru_1.add(entry1_); + EXPECT_EQ(0, lru_1.size()); + EXPECT_EQ(1, entry1_.use_count()); + + // Removing an uninserted entry should not affect the list. + LruList<TestEntry> lru_2(100); + lru_2.add(entry1_); + lru_2.add(entry2_); + lru_2.add(entry3_); + EXPECT_EQ(3, lru_2.size()); + + lru_2.remove(entry4_); + EXPECT_EQ(2, entry1_.use_count()); + EXPECT_EQ(2, entry2_.use_count()); + EXPECT_EQ(2, entry3_.use_count()); + EXPECT_EQ(1, entry4_.use_count()); + EXPECT_EQ(1, entry5_.use_count()); + EXPECT_EQ(3, lru_2.size()); + + // Touching an uninserted entry should not affect the list. + lru_2.touch(entry5_); + EXPECT_EQ(2, entry1_.use_count()); + EXPECT_EQ(2, entry2_.use_count()); + EXPECT_EQ(2, entry3_.use_count()); + EXPECT_EQ(1, entry4_.use_count()); + EXPECT_EQ(1, entry5_.use_count()); + EXPECT_EQ(3, lru_2.size()); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/nameserver_address_store_unittest.cc b/src/lib/nsas/tests/nameserver_address_store_unittest.cc new file mode 100644 index 0000000000..7a8687b200 --- /dev/null +++ b/src/lib/nsas/tests/nameserver_address_store_unittest.cc @@ -0,0 +1,407 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +/// \brief Test Deleter Objects +/// +/// This file contains tests for the "deleter" classes within the nameserver +/// address store. These act to delete zones from the zone hash table when +/// the element reaches the top of the LRU list. + +#include <dns/rrttl.h> +#include <dns/rdataclass.h> +#include <dns/rrclass.h> + +#include <gtest/gtest.h> +#include <boost/shared_ptr.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/foreach.hpp> + +#include <string.h> +#include <cassert> + +#include "../nameserver_address_store.h" +#include "../nsas_entry_compare.h" +#include "../nameserver_entry.h" +#include "../zone_entry.h" +#include "../address_request_callback.h" +#include "nsas_test.h" + +using namespace isc::dns; +using namespace std; +using namespace boost; + +namespace isc { +namespace nsas { + + +/// \brief NSAS Store +/// +/// This is a subclass of the NameserverAddressStore class, with methods to +/// access the internal members to check that the deleter objects are working. +class DerivedNsas : public NameserverAddressStore { +public: + /// \brief Constructor + /// + /// \param hashsize Size of the zone hash table + /// \param lrusize Size of the zone hash table + DerivedNsas(shared_ptr<TestResolver> resolver, uint32_t hashsize, + uint32_t lrusize) : + NameserverAddressStore(resolver, hashsize, lrusize), + resolver_(resolver) + {} + + /// \brief Virtual Destructor + virtual ~DerivedNsas() + {} + + /// \brief Add Nameserver Entry to Hash and LRU Tables + void AddNameserverEntry(boost::shared_ptr<NameserverEntry>& entry) { + HashKey h = entry->hashKey(); + nameserver_hash_->add(entry, h); + nameserver_lru_->add(entry); + } + + /// \brief Add Zone Entry to Hash and LRU Tables + void AddZoneEntry(boost::shared_ptr<ZoneEntry>& entry) { + HashKey h = entry->hashKey(); + zone_hash_->add(entry, h); + zone_lru_->add(entry); + } + /** + * \short Just wraps the common lookup + * + * It calls the lookup and provides the authority section + * if it is asked for by the resolver. + */ + void lookupAndAnswer(const string& name, const RRClass& class_code, + shared_ptr<AbstractRRset> authority, + shared_ptr<AddressRequestCallback> callback) + { + size_t size(resolver_->requests.size()); + NameserverAddressStore::lookup(name, class_code, callback, ANY_OK); + // It asked something, the only thing it can ask is the NS list + if (size < resolver_->requests.size()) { + resolver_->provideNS(size, authority); + // Once answered, drop the request so noone else sees it + resolver_->requests.erase(resolver_->requests.begin() + size); + } else { + ADD_FAILURE() << "Not asked for NS"; + } + } +private: + shared_ptr<TestResolver> resolver_; +}; + + + +/// \brief Text Fixture Class +class NameserverAddressStoreTest : public TestWithRdata { +protected: + + NameserverAddressStoreTest() : + authority_(new RRset(Name("example.net."), RRClass::IN(), RRType::NS(), + RRTTL(128))), + empty_authority_(new RRset(Name("example.net."), RRClass::IN(), + RRType::NS(), RRTTL(128))), + resolver_(new TestResolver) + { + // Constructor - initialize a set of nameserver and zone objects. For + // convenience, these are stored in vectors. + for (int i = 1; i <= 9; ++i) { + std::string name = "nameserver" + boost::lexical_cast<std::string>( + i); + nameservers_.push_back(boost::shared_ptr<NameserverEntry>( + new NameserverEntry(name, RRClass(40 + i)))); + } + + // Some zones. They will not use the tables in this test, so it can be + // empty + for (int i = 1; i <= 9; ++i) { + std::string name = "zone" + boost::lexical_cast<std::string>(i); + zones_.push_back(boost::shared_ptr<ZoneEntry>(new ZoneEntry( + resolver_, name, RRClass(40 + i), + shared_ptr<HashTable<NameserverEntry> >(), + shared_ptr<LruList<NameserverEntry> >()))); + } + + // A nameserver serving data + authority_->addRdata(ConstRdataPtr(new rdata::generic::NS(Name( + "ns.example.com.")))); + + // This is reused because of convenience, clear it just in case + NSASCallback::results.clear(); + } + + // Vector of pointers to nameserver and zone entries. + std::vector<boost::shared_ptr<NameserverEntry> > nameservers_; + std::vector<boost::shared_ptr<ZoneEntry> > zones_; + + RRsetPtr authority_, empty_authority_; + + shared_ptr<TestResolver> resolver_; + + class NSASCallback : public AddressRequestCallback { + public: + typedef pair<bool, NameserverAddress> Result; + static vector<Result> results; + virtual void success(const NameserverAddress& address) { + results.push_back(Result(true, address)); + } + virtual void unreachable() { + results.push_back(Result(false, NameserverAddress())); + } + }; + + boost::shared_ptr<AddressRequestCallback> getCallback() { + return (boost::shared_ptr<AddressRequestCallback>(new NSASCallback)); + } +}; + +vector<NameserverAddressStoreTest::NSASCallback::Result> + NameserverAddressStoreTest::NSASCallback::results; + + +/// \brief Remove Zone Entry from Hash Table +/// +/// Check that when an entry reaches the top of the zone LRU list, it is removed from the +/// hash table as well. +TEST_F(NameserverAddressStoreTest, ZoneDeletionCheck) { + + // Create a NSAS with a hash size of three and a LRU size of 9 (both zone and + // nameserver tables). + DerivedNsas nsas(resolver_, 2, 2); + + // Add six entries to the tables. After addition the reference count of each element + // should be 3 - one for the entry in the zones_ vector, and one each for the entries + // in the LRU list and hash table. + for (int i = 1; i <= 6; ++i) { + EXPECT_EQ(1, zones_[i].use_count()); + nsas.AddZoneEntry(zones_[i]); + EXPECT_EQ(3, zones_[i].use_count()); + } + + // Adding another entry should cause the first one to drop off the LRU list, which + // should also trigger the deletion of the entry from the hash table. This should + // reduce its use count to 1. + EXPECT_EQ(1, zones_[7].use_count()); + nsas.AddZoneEntry(zones_[7]); + EXPECT_EQ(3, zones_[7].use_count()); + + EXPECT_EQ(1, zones_[1].use_count()); +} + + +/// \brief Remove Entry from Hash Table +/// +/// Check that when an entry reaches the top of the LRU list, it is removed from the +/// hash table as well. +TEST_F(NameserverAddressStoreTest, NameserverDeletionCheck) { + + // Create a NSAS with a hash size of three and a LRU size of 9 (both zone and + // nameserver tables). + DerivedNsas nsas(resolver_, 2, 2); + + // Add six entries to the tables. After addition the reference count of each element + // should be 3 - one for the entry in the nameservers_ vector, and one each for the entries + // in the LRU list and hash table. + for (int i = 1; i <= 6; ++i) { + EXPECT_EQ(1, nameservers_[i].use_count()); + nsas.AddNameserverEntry(nameservers_[i]); + EXPECT_EQ(3, nameservers_[i].use_count()); + } + + // Adding another entry should cause the first one to drop off the LRU list, which + // should also trigger the deletion of the entry from the hash table. This should + // reduce its use count to 1. + EXPECT_EQ(1, nameservers_[7].use_count()); + nsas.AddNameserverEntry(nameservers_[7]); + EXPECT_EQ(3, nameservers_[7].use_count()); + + EXPECT_EQ(1, nameservers_[1].use_count()); +} + +/** + * \short Try lookup on empty store. + * + * Check if it asks correct questions and it keeps correct internal state. + */ +TEST_F(NameserverAddressStoreTest, emptyLookup) { + DerivedNsas nsas(resolver_, 10, 10); + // Ask it a question + nsas.lookupAndAnswer("example.net.", RRClass::IN(), authority_, + getCallback()); + // It should ask for IP addresses for ns.example.com. + EXPECT_NO_THROW(resolver_->asksIPs(Name("ns.example.com."), 0, 1)); + + // Ask another question for the same zone + nsas.lookup("example.net.", RRClass::IN(), getCallback()); + // It should ask no more questions now + EXPECT_EQ(2, resolver_->requests.size()); + + // Ask another question with different zone but the same nameserver + authority_->setName(Name("example.com.")); + nsas.lookupAndAnswer("example.com.", RRClass::IN(), authority_, + getCallback()); + // It still should ask nothing + EXPECT_EQ(2, resolver_->requests.size()); + + // We provide IP address of one nameserver, it should generate all the + // results + EXPECT_NO_THROW(resolver_->answer(0, Name("ns.example.com."), RRType::A(), + rdata::in::A("192.0.2.1"))); + EXPECT_EQ(3, NSASCallback::results.size()); + BOOST_FOREACH(const NSASCallback::Result& result, NSASCallback::results) { + EXPECT_TRUE(result.first); + EXPECT_EQ("192.0.2.1", result.second.getAddress().toText()); + } +} + +/** + * \short Try looking up a zone that does not have any nameservers. + * + * It should not ask anything and say it is unreachable right away. + */ +TEST_F(NameserverAddressStoreTest, zoneWithoutNameservers) { + DerivedNsas nsas(resolver_, 10, 10); + // Ask it a question + nsas.lookupAndAnswer("example.net.", RRClass::IN(), empty_authority_, + getCallback()); + // There should be no questions, because there's nothing to ask + EXPECT_EQ(0, resolver_->requests.size()); + // And there should be one "unreachable" answer for the query + ASSERT_EQ(1, NSASCallback::results.size()); + EXPECT_FALSE(NSASCallback::results[0].first); +} + +/** + * \short Try looking up a zone that has only an unreachable nameserver. + * + * It should be unreachable. Furthermore, subsequent questions for that zone + * or other zone with the same nameserver should be unreachable right away, + * without further asking. + */ +TEST_F(NameserverAddressStoreTest, unreachableNS) { + DerivedNsas nsas(resolver_, 10, 10); + // Ask it a question + nsas.lookupAndAnswer("example.net.", RRClass::IN(), authority_, + getCallback()); + // It should ask for IP addresses for example.com. + EXPECT_NO_THROW(resolver_->asksIPs(Name("ns.example.com."), 0, 1)); + + // Ask another question with different zone but the same nameserver + authority_->setName(Name("example.com.")); + nsas.lookupAndAnswer("example.com.", RRClass::IN(), authority_, + getCallback()); + // It should ask nothing more now + EXPECT_EQ(2, resolver_->requests.size()); + + // We say there are no addresses + resolver_->requests[0].second->failure(); + resolver_->requests[1].second->failure(); + + // We should have 2 answers now + EXPECT_EQ(2, NSASCallback::results.size()); + // When we ask one same and one other zone with the same nameserver, + // it should generate no questions and answer right away + nsas.lookup("example.net.", RRClass::IN(), getCallback()); + authority_->setName(Name("example.org.")); + nsas.lookupAndAnswer("example.org.", RRClass::IN(), authority_, + getCallback()); + // There should be 4 negative answers now + EXPECT_EQ(4, NSASCallback::results.size()); + BOOST_FOREACH(const NSASCallback::Result& result, NSASCallback::results) { + EXPECT_FALSE(result.first); + } +} + +/** + * \short Try to stress it little bit by having multiple zones and nameservers. + * + * Does some asking, on a set of zones that share some nameservers, with + * slower answering, evicting data, etc. + */ +TEST_F(NameserverAddressStoreTest, CombinedTest) { + // Create small caches, so we get some evictions + DerivedNsas nsas(resolver_, 1, 1); + // Ask for example.net. It has single nameserver out of the zone + nsas.lookupAndAnswer("example.net.", RRClass::IN(), authority_, + getCallback()); + // It should ask for the nameserver IP addresses + EXPECT_NO_THROW(resolver_->asksIPs(Name("ns.example.com."), 0, 1)); + EXPECT_EQ(0, NSASCallback::results.size()); + // But we do not answer it right away. We create a new zone and + // let this nameserver entry get out. + rrns_->addRdata(rdata::generic::NS("example.cz")); + nsas.lookupAndAnswer(EXAMPLE_CO_UK, RRClass::IN(), rrns_, getCallback()); + // It really should ask something, one of the nameservers + // (or both) + ASSERT_GT(resolver_->requests.size(), 2); + Name name(resolver_->requests[2].first->getName()); + EXPECT_TRUE(name == Name("example.fr") || name == Name("example.de") || + name == Name("example.cz")); + EXPECT_NO_THROW(resolver_->asksIPs(name, 2, 3)); + EXPECT_EQ(0, NSASCallback::results.size()); + + size_t request_count(resolver_->requests.size()); + // This should still be in the hash table, so try it asks no more questions + nsas.lookup("example.net.", RRClass::IN(), getCallback()); + EXPECT_EQ(request_count, resolver_->requests.size()); + EXPECT_EQ(0, NSASCallback::results.size()); + + // We respond to one of the 3 nameservers + EXPECT_NO_THROW(resolver_->answer(2, name, RRType::A(), + rdata::in::A("192.0.2.1"))); + // That should trigger one answer + EXPECT_EQ(1, NSASCallback::results.size()); + EXPECT_TRUE(NSASCallback::results[0].first); + EXPECT_EQ("192.0.2.1", + NSASCallback::results[0].second.getAddress().toText()); + EXPECT_NO_THROW(resolver_->answer(3, name, RRType::AAAA(), + rdata::in::AAAA("2001:bd8::1"))); + // And there should be yet another query + ASSERT_GT(resolver_->requests.size(), 4); + EXPECT_NE(name, resolver_->requests[4].first->getName()); + Name another_name = resolver_->requests[4].first->getName(); + EXPECT_TRUE(another_name == Name("example.fr") || + another_name == Name("example.de") || + another_name == Name("example.cz")); + request_count = resolver_->requests.size(); + + // But when ask for a different zone with the first nameserver, it should + // ask again, as it is evicted already + authority_->setName(Name("example.com.")); + nsas.lookupAndAnswer("example.com.", RRClass::IN(), authority_, + getCallback()); + EXPECT_EQ(request_count + 2, resolver_->requests.size()); + EXPECT_NO_THROW(resolver_->asksIPs(Name("ns.example.com."), request_count, + request_count + 1)); + // Now, we answer both queries for the same address + // and three (one for the original, one for this one) more answers should + // arrive + NSASCallback::results.clear(); + EXPECT_NO_THROW(resolver_->answer(0, Name("ns.example.com."), RRType::A(), + rdata::in::A("192.0.2.2"))); + EXPECT_NO_THROW(resolver_->answer(request_count, Name("ns.example.com."), + RRType::A(), rdata::in::A("192.0.2.2"))); + EXPECT_EQ(3, NSASCallback::results.size()); + BOOST_FOREACH(const NSASCallback::Result& result, NSASCallback::results) { + EXPECT_TRUE(result.first); + EXPECT_EQ("192.0.2.2", result.second.getAddress().toText()); + } +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/nameserver_address_unittest.cc b/src/lib/nsas/tests/nameserver_address_unittest.cc new file mode 100644 index 0000000000..8161d73d30 --- /dev/null +++ b/src/lib/nsas/tests/nameserver_address_unittest.cc @@ -0,0 +1,134 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <gtest/gtest.h> + +#include <dns/name.h> +#include <dns/rdata.h> +#include <dns/rrclass.h> +#include <dns/rrset.h> +#include <dns/rrttl.h> + +#include "../nameserver_address.h" +#include "../nameserver_entry.h" +#include "nsas_test.h" + +namespace isc { +namespace nsas { + +using namespace dns; +using namespace rdata; +using namespace boost; + +#define TEST_ADDRESS_INDEX 1 + +/// \brief NameserverEntry sample class for testing +class NameserverEntrySample { +public: + NameserverEntrySample(): + name_("example.org"), + rrv4_(new BasicRRset(name_, RRClass::IN(), RRType::A(), RRTTL(1200))) + { + // Add some sample A records + rrv4_->addRdata(ConstRdataPtr(new RdataTest<A>("1.2.3.4"))); + rrv4_->addRdata(ConstRdataPtr(new RdataTest<A>("5.6.7.8"))); + rrv4_->addRdata(ConstRdataPtr(new RdataTest<A>("9.10.11.12"))); + + ns_.reset(new NameserverEntry(name_.toText(), RRClass::IN())); + shared_ptr<TestResolver> resolver(new TestResolver); + ns_->askIP(resolver, shared_ptr<Callback>(new Callback), ANY_OK); + resolver->asksIPs(name_, 0, 1); + resolver->requests[0].second->success(rrv4_); + } + + // Return the sample NameserverEntry + boost::shared_ptr<NameserverEntry>& getNameserverEntry() { return ns_; } + + // Return the IOAddress corresponding to the index in rrv4_ + asiolink::IOAddress getAddressAtIndex(uint32_t index) { + return ns_.get()->getAddressAtIndex(index, V4_ONLY); + } + + // Return the addresses count stored in RRset + unsigned int getAddressesCount() const { return rrv4_->getRdataCount(); } + + // Return the RTT of the address + uint32_t getAddressRTTAtIndex(uint32_t index) { + NameserverEntry::AddressVector addresses; + ns_.get()->getAddresses(addresses); + return (addresses[index].getAddressEntry().getRTT()); + } + +private: + Name name_; ///< Name of the sample + shared_ptr<BasicRRset> rrv4_; ///< Standard RRSet - IN, A, lowercase name + boost::shared_ptr<NameserverEntry> ns_; ///< Shared_ptr that points to a NameserverEntry object + + class Callback : public NameserverEntry::Callback { + public: + virtual void operator()(shared_ptr<NameserverEntry>) { } + }; +}; + +/// \brief Test Fixture Class +class NameserverAddressTest : public ::testing::Test { +protected: + // Constructor + NameserverAddressTest(): + ns_address_(ns_sample_.getNameserverEntry(), + ns_sample_.getNameserverEntry()->getAddressAtIndex( + TEST_ADDRESS_INDEX, V4_ONLY), V4_ONLY) + { + } + + NameserverEntrySample ns_sample_; + // Valid NameserverAddress object + NameserverAddress ns_address_; +}; + +// Test that the address is equal to the address in NameserverEntry +TEST_F(NameserverAddressTest, Address) { + EXPECT_TRUE(ns_address_.getAddress().equal( ns_sample_.getAddressAtIndex(TEST_ADDRESS_INDEX))); + + boost::shared_ptr<NameserverEntry> empty_ne((NameserverEntry*)NULL); + // It will throw an NullNameserverEntryPointer exception with the empty NameserverEntry shared pointer + ASSERT_THROW({NameserverAddress empty_ns_address(empty_ne, + asiolink::IOAddress("127.0.0.1"), V4_ONLY);}, + NullNameserverEntryPointer); +} + +// Test that the RTT is updated +TEST_F(NameserverAddressTest, UpdateRTT) { + uint32_t old_rtt = ns_sample_.getAddressRTTAtIndex(TEST_ADDRESS_INDEX); + uint32_t new_rtt = old_rtt + 10; + + uint32_t old_rtt0 = ns_sample_.getAddressRTTAtIndex(0); + uint32_t old_rtt2 = ns_sample_.getAddressRTTAtIndex(2); + + for(int i = 0; i < 10000; ++i){ + ns_address_.updateRTT(new_rtt); + } + + //The RTT should have been updated + EXPECT_NE(new_rtt, ns_sample_.getAddressRTTAtIndex(TEST_ADDRESS_INDEX)); + + //The RTTs not been updated should remain unchanged + EXPECT_EQ(old_rtt0, ns_sample_.getAddressRTTAtIndex(0)); + EXPECT_EQ(old_rtt2, ns_sample_.getAddressRTTAtIndex(2)); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/nameserver_entry_unittest.cc b/src/lib/nsas/tests/nameserver_entry_unittest.cc new file mode 100644 index 0000000000..4234d1d211 --- /dev/null +++ b/src/lib/nsas/tests/nameserver_entry_unittest.cc @@ -0,0 +1,519 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <iostream> +#include <algorithm> + +#include <limits.h> +#include <boost/foreach.hpp> +#include <boost/shared_ptr.hpp> +#include <gtest/gtest.h> + +#include <dns/rdata.h> +#include <dns/rrset.h> +#include <dns/rrclass.h> +#include <dns/rdataclass.h> +#include <dns/rrttl.h> +#include <dns/name.h> +#include <exceptions/exceptions.h> + +#include "../asiolink.h" +#include "../address_entry.h" +#include "../nameserver_entry.h" +#include "../nameserver_address.h" +#include "../zone_entry.h" + +#include "nsas_test.h" + +using namespace isc::nsas; +using namespace asiolink; +using namespace std; +using namespace isc::dns; +using namespace rdata; +using namespace boost; + +namespace { + +/// \brief Test Fixture Class +class NameserverEntryTest : public TestWithRdata { +protected: + /// \short Just a really stupid callback counting times called + struct Callback : public NameserverEntry::Callback { + size_t count; + virtual void operator()(shared_ptr<NameserverEntry>) { + count ++; + } + Callback() : count(0) { } + }; +private: + /** + * \short Fills an rrset into the NameserverEntry trough resolver. + * + * This function is used when we want to pass data to a NameserverEntry + * trough the resolver. + * \param resolver The resolver used by the NameserverEntry + * \param index Index of the query in the resolver. + * \param set The answer. If the pointer is empty, it is taken + * as a failure. + */ + void fillSet(shared_ptr<TestResolver> resolver, size_t index, + shared_ptr<BasicRRset> set) + { + if (set) { + resolver->requests[index].second->success(set); + } else { + resolver->requests[index].second->failure(); + } + } +protected: + /// Fills the nameserver entry with data trough ask IP + void fillNSEntry(shared_ptr<NameserverEntry> entry, + shared_ptr<BasicRRset> rrv4, shared_ptr<BasicRRset> rrv6) + { + // Prepare data to run askIP + shared_ptr<TestResolver> resolver(new TestResolver); + shared_ptr<Callback> callback(new Callback); + // Let it ask for data + entry->askIP(resolver, callback, ANY_OK); + // Check it really asked and sort the queries + EXPECT_TRUE(resolver->asksIPs(Name(entry->getName()), 0, 1)); + // Respond with answers + fillSet(resolver, 0, rrv4); + fillSet(resolver, 1, rrv6); + } +}; + +/// Tests of the default constructor +TEST_F(NameserverEntryTest, DefaultConstructor) { + + // Default constructor should not create any RRsets + NameserverEntry alpha(EXAMPLE_CO_UK, RRClass::IN()); + EXPECT_EQ(EXAMPLE_CO_UK, alpha.getName()); + EXPECT_EQ(RRClass::IN(), alpha.getClass()); + + // Also check that no addresses have been created. + NameserverEntry::AddressVector addresses; + alpha.getAddresses(addresses); + EXPECT_TRUE(addresses.empty()); +} + +// Test the the RTT on tthe created addresses is not 0 and is different +TEST_F(NameserverEntryTest, InitialRTT) { + + // Get the RTT for the different addresses + shared_ptr<NameserverEntry> alpha(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(alpha, rrv4_, rrv6_); + NameserverEntry::AddressVector vec; + alpha->getAddresses(vec); + + // Check they are not 0 and they are all small, they should be some kind + // of randomish numbers, so we can't expect much more here + BOOST_FOREACH(NameserverAddress& entry, vec) { + EXPECT_GT(entry.getAddressEntry().getRTT(), 0); + // 20 is some arbitrary small value + EXPECT_LT(entry.getAddressEntry().getRTT(), 20); + } +} + +// Set an address RTT to a given value +TEST_F(NameserverEntryTest, SetRTT) { + + // Get the RTT for the different addresses + shared_ptr<NameserverEntry> alpha(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(alpha, rrv4_, rrv6_); + NameserverEntry::AddressVector vec; + alpha->getAddresses(vec); + + ASSERT_TRUE(vec.size() > 0); + + // Take the first address and change the RTT. + IOAddress first_address = vec[0].getAddress(); + uint32_t first_rtt = vec[0].getAddressEntry().getRTT(); + uint32_t new_rtt = first_rtt + 42; + alpha->setAddressRTT(first_address, new_rtt); + + // Now see if it has changed + NameserverEntry::AddressVector newvec; + alpha->getAddresses(newvec); + + int matchcount = 0; + for (NameserverEntry::AddressVectorIterator i = newvec.begin(); + i != newvec.end(); ++i) { + if (i->getAddress().equal(first_address)) { + ++matchcount; + EXPECT_EQ(i->getAddressEntry().getRTT(), new_rtt); + } + } + + // ... and make sure there was only one match in the set we retrieved + EXPECT_EQ(1, matchcount); +} + +// Set an address RTT to be unreachable +TEST_F(NameserverEntryTest, Unreachable) { + + // Get the RTT for the different addresses + shared_ptr<NameserverEntry> alpha(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(alpha, rrv4_, rrv6_); + NameserverEntry::AddressVector vec; + alpha->getAddresses(vec); + + ASSERT_TRUE(vec.size() > 0); + + // Take the first address and mark as unreachable. + IOAddress first_address = vec[0].getAddress(); + EXPECT_FALSE(vec[0].getAddressEntry().isUnreachable()); + + alpha->setAddressUnreachable(first_address); + + // Now see if it has changed + NameserverEntry::AddressVector newvec; + alpha->getAddresses(newvec); + + int matchcount = 0; + for (NameserverEntry::AddressVectorIterator i = newvec.begin(); + i != newvec.end(); ++i) { + if (i->getAddress().equal(first_address)) { + ++matchcount; + EXPECT_TRUE(i->getAddressEntry().isUnreachable()); + } + } + + // ... and make sure there was only one match in the set we retrieved + EXPECT_EQ(1, matchcount); +} + +// Test that the expiration time of records is set correctly. +// +// Note that for testing purposes we use the three-argument NameserverEntry +// constructor (where we supply the time). It eliminates intermittent errors +// cause when this test is run just as the clock "ticks over" to another second. +// TODO Return the way where we can pass time inside somehow +TEST_F(NameserverEntryTest, ExpirationTime) { + + time_t curtime = time(NULL); + time_t expiration = 0; + + // Test where there is a single TTL + shared_ptr<NameserverEntry> alpha(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(alpha, rrv4_, shared_ptr<BasicRRset>()); + expiration = alpha->getExpiration(); + EXPECT_EQ(expiration, curtime + rrv4_->getTTL().getValue()); + + shared_ptr<NameserverEntry> beta(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(beta, shared_ptr<BasicRRset>(), rrv6_); + expiration = beta->getExpiration(); + EXPECT_EQ(expiration, curtime + rrv6_->getTTL().getValue()); + + // Test where there are two different TTLs + EXPECT_NE(rrv4_->getTTL().getValue(), rrv6_->getTTL().getValue()); + shared_ptr<NameserverEntry> gamma(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(gamma, rrv4_, rrv6_); + uint32_t minttl = min(rrv4_->getTTL().getValue(), rrv6_->getTTL().getValue()); + expiration = gamma->getExpiration(); + EXPECT_EQ(expiration, curtime + minttl); + + // Finally check where we don't specify a current time. All we know is + // that the expiration time should be greater than the TTL (as the current + // time is greater than zero). + + shared_ptr<NameserverEntry> delta(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(delta, rrv4_, shared_ptr<BasicRRset>()); + EXPECT_GT(delta->getExpiration(), rrv4_->getTTL().getValue()); +} + + +// Test that the name of this nameserver is set correctly. +TEST_F(NameserverEntryTest, CheckName) { + + // Default constructor + NameserverEntry alpha(EXAMPLE_CO_UK, RRClass::IN()); + EXPECT_EQ(EXAMPLE_CO_UK, alpha.getName()); +} + +// Check that it can cope with non-IN classes. +TEST_F(NameserverEntryTest, CheckClass) { + + // Default constructor + NameserverEntry alpha(EXAMPLE_CO_UK, RRClass::CH()); + EXPECT_EQ(RRClass::CH(), alpha.getClass()); +} + +// Tests if it asks the IP addresses and calls callbacks when it comes +// including the right addresses are returned and that they expire +TEST_F(NameserverEntryTest, IPCallbacks) { + shared_ptr<NameserverEntry> entry(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + shared_ptr<Callback> callback(new Callback); + shared_ptr<TestResolver> resolver(new TestResolver); + + entry->askIP(resolver, callback, ANY_OK); + // Ensure it becomes IN_PROGRESS + EXPECT_EQ(Fetchable::IN_PROGRESS, entry->getState()); + // Now, there should be two queries in the resolver + EXPECT_EQ(2, resolver->requests.size()); + ASSERT_TRUE(resolver->asksIPs(Name(EXAMPLE_CO_UK), 0, 1)); + + // Another one might ask + entry->askIP(resolver, callback, V4_ONLY); + // There should still be only two queries in the resolver + ASSERT_EQ(2, resolver->requests.size()); + + // Another one, with need of IPv6 address + entry->askIP(resolver, callback, V6_ONLY); + + // Answer one and see that the callbacks are called + resolver->answer(0, Name(EXAMPLE_CO_UK), RRType::A(), + rdata::in::A("192.0.2.1")); + + // Both callbacks that want IPv4 should be called by now + EXPECT_EQ(2, callback->count); + // It should contain one IP address + NameserverEntry::AddressVector addresses; + // Still in progress, waiting for the other address + EXPECT_EQ(Fetchable::IN_PROGRESS, entry->getAddresses(addresses)); + EXPECT_EQ(1, addresses.size()); + // Answer IPv6 address + // It is with zero TTL, so it should expire right away + resolver->answer(1, Name(EXAMPLE_CO_UK), RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"), 0); + // The other callback should appear + EXPECT_EQ(3, callback->count); + // It should return the one address. It should be expired, but + // we ignore it for now + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V6_ONLY, true)); + // Another address should appear + EXPECT_EQ(2, addresses.size()); + // But when we do not ignore it, it should not appear + EXPECT_EQ(Fetchable::EXPIRED, entry->getAddresses(addresses, V6_ONLY)); + EXPECT_EQ(2, addresses.size()); +} + +// Test the callback is called even when the address is unreachable +TEST_F(NameserverEntryTest, IPCallbacksUnreachable) { + shared_ptr<NameserverEntry> entry(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + shared_ptr<Callback> callback(new Callback); + shared_ptr<TestResolver> resolver(new TestResolver); + + // Ask for its IP + entry->askIP(resolver, callback, ANY_OK); + // Check it asks the resolver + EXPECT_EQ(2, resolver->requests.size()); + ASSERT_TRUE(resolver->asksIPs(Name(EXAMPLE_CO_UK), 0, 1)); + resolver->requests[0].second->failure(); + // It should still wait for the second one + EXPECT_EQ(0, callback->count); + EXPECT_EQ(Fetchable::IN_PROGRESS, entry->getState()); + // It should call the callback now and be unrechable + resolver->requests[1].second->failure(); + EXPECT_EQ(1, callback->count); + EXPECT_EQ(Fetchable::UNREACHABLE, entry->getState()); + NameserverEntry::AddressVector addresses; + EXPECT_EQ(Fetchable::UNREACHABLE, entry->getAddresses(addresses)); + EXPECT_EQ(0, addresses.size()); +} + +/* + * Tests that it works even when we provide the answer right away, directly + * from resolve. + */ +TEST_F(NameserverEntryTest, DirectAnswer) { + shared_ptr<NameserverEntry> entry(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + shared_ptr<Callback> callback(new Callback); + shared_ptr<TestResolver> resolver(new TestResolver); + resolver->addPresetAnswer(Question(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::A()), rrv4_); + resolver->addPresetAnswer(Question(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::AAAA()), rrv6_); + resolver->addPresetAnswer(Question(Name(EXAMPLE_NET), RRClass::IN(), + RRType::A()), shared_ptr<AbstractRRset>()); + resolver->addPresetAnswer(Question(Name(EXAMPLE_NET), RRClass::IN(), + RRType::AAAA()), shared_ptr<AbstractRRset>()); + + // A successfull test first + entry->askIP(resolver, callback, ANY_OK); + EXPECT_EQ(0, resolver->requests.size()); + EXPECT_EQ(1, callback->count); + NameserverEntry::AddressVector addresses; + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses)); + EXPECT_EQ(5, addresses.size()); + + // An unsuccessfull test + callback->count = 0; + entry.reset(new NameserverEntry(EXAMPLE_NET, RRClass::IN())); + entry->askIP(resolver, callback, ANY_OK); + EXPECT_EQ(0, resolver->requests.size()); + EXPECT_EQ(1, callback->count); + addresses.clear(); + EXPECT_EQ(Fetchable::UNREACHABLE, entry->getAddresses(addresses)); + EXPECT_EQ(0, addresses.size()); +} + +/* + * This one tests if it works when the data time out and a different + * data is received the next time. + */ +TEST_F(NameserverEntryTest, ChangedExpired) { + shared_ptr<NameserverEntry> entry(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + shared_ptr<Callback> callback(new Callback); + shared_ptr<TestResolver> resolver(new TestResolver); + + // Ask the first time + entry->askIP(resolver, callback, V4_ONLY); + entry->askIP(resolver, callback, V6_ONLY); + EXPECT_TRUE(resolver->asksIPs(Name(EXAMPLE_CO_UK), 0, 1)); + EXPECT_EQ(Fetchable::IN_PROGRESS, entry->getState()); + resolver->answer(0, Name(EXAMPLE_CO_UK), RRType::A(), + rdata::in::A("192.0.2.1"), 0); + resolver->answer(1, Name(EXAMPLE_CO_UK), RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"), 0); + EXPECT_EQ(2, callback->count); + NameserverEntry::AddressVector addresses; + // We must accept expired as well, as the TTL is 0 (and it is OK, + // because we just got the callback) + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V4_ONLY, true)); + ASSERT_EQ(1, addresses.size()); + EXPECT_EQ("192.0.2.1", addresses[0].getAddress().toText()); + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V6_ONLY, true)); + ASSERT_EQ(2, addresses.size()); + EXPECT_EQ("2001:db8::1", addresses[1].getAddress().toText()); + + // Ask the second time. The callbacks should not fire right away and it + // should request the addresses again + entry->askIP(resolver, callback, V4_ONLY); + entry->askIP(resolver, callback, V6_ONLY); + EXPECT_EQ(2, callback->count); + EXPECT_TRUE(resolver->asksIPs(Name(EXAMPLE_CO_UK), 2, 3)); + EXPECT_EQ(Fetchable::IN_PROGRESS, entry->getState()); + resolver->answer(0, Name(EXAMPLE_CO_UK), RRType::A(), + rdata::in::A("192.0.2.2")); + resolver->answer(1, Name(EXAMPLE_CO_UK), RRType::AAAA(), + rdata::in::AAAA("2001:db8::2")); + // We should get the new addresses and they should not expire, + // so we should get them without accepting expired + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V4_ONLY)); + ASSERT_EQ(3, addresses.size()); + EXPECT_EQ("192.0.2.2", addresses[2].getAddress().toText()); + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V6_ONLY)); + ASSERT_EQ(4, addresses.size()); + EXPECT_EQ("2001:db8::2", addresses[3].getAddress().toText()); +} + +/* + * When the data expire and is asked again, the original RTT is kept. + */ +TEST_F(NameserverEntryTest, KeepRTT) { + shared_ptr<NameserverEntry> entry(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + shared_ptr<Callback> callback(new Callback); + shared_ptr<TestResolver> resolver(new TestResolver); + + // Ask the first time + entry->askIP(resolver, callback, V4_ONLY); + entry->askIP(resolver, callback, V6_ONLY); + EXPECT_TRUE(resolver->asksIPs(Name(EXAMPLE_CO_UK), 0, 1)); + EXPECT_EQ(Fetchable::IN_PROGRESS, entry->getState()); + resolver->answer(0, Name(EXAMPLE_CO_UK), RRType::A(), + rdata::in::A("192.0.2.1"), 0); + resolver->answer(1, Name(EXAMPLE_CO_UK), RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"), 0); + EXPECT_EQ(2, callback->count); + NameserverEntry::AddressVector addresses; + // We must accept expired as well, as the TTL is 0 (and it is OK, + // because we just got the callback) + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V4_ONLY, true)); + ASSERT_EQ(1, addresses.size()); + EXPECT_EQ("192.0.2.1", addresses[0].getAddress().toText()); + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V6_ONLY, true)); + ASSERT_EQ(2, addresses.size()); + EXPECT_EQ("2001:db8::1", addresses[1].getAddress().toText()); + BOOST_FOREACH(const NameserverAddress& address, addresses) { + entry->setAddressRTT(address.getAddress(), 123); + } + + // Ask the second time. The callbacks should not fire right away and it + // should request the addresses again + entry->askIP(resolver, callback, V4_ONLY); + entry->askIP(resolver, callback, V6_ONLY); + EXPECT_EQ(2, callback->count); + EXPECT_TRUE(resolver->asksIPs(Name(EXAMPLE_CO_UK), 2, 3)); + EXPECT_EQ(Fetchable::IN_PROGRESS, entry->getState()); + resolver->answer(0, Name(EXAMPLE_CO_UK), RRType::A(), + rdata::in::A("192.0.2.1")); + resolver->answer(1, Name(EXAMPLE_CO_UK), RRType::AAAA(), + rdata::in::AAAA("2001:db8::1")); + // We should get the new addresses and they should not expire, + // so we should get them without accepting expired + addresses.clear(); + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V4_ONLY)); + ASSERT_EQ(1, addresses.size()); + EXPECT_EQ("192.0.2.1", addresses[0].getAddress().toText()); + EXPECT_EQ(Fetchable::READY, entry->getAddresses(addresses, V6_ONLY)); + ASSERT_EQ(2, addresses.size()); + EXPECT_EQ("2001:db8::1", addresses[1].getAddress().toText()); + // They should have the RTT we set to them + BOOST_FOREACH(NameserverAddress& address, addresses) { + EXPECT_EQ(123, address.getAddressEntry().getRTT()); + } +} + +// Test the RTT is updated smoothly +TEST_F(NameserverEntryTest, UpdateRTT) { + shared_ptr<NameserverEntry> ns(new NameserverEntry(EXAMPLE_CO_UK, + RRClass::IN())); + fillNSEntry(ns, rrv4_, rrv6_); + NameserverEntry::AddressVector vec; + ns->getAddresses(vec); + + // Initialize the rtt with a small value + uint32_t init_rtt = 1; + ns->setAddressRTT(vec[0].getAddress(), init_rtt); + // The rtt will be stablized to a large value + uint32_t stable_rtt = 100; + + // Update the rtt + vec[0].updateRTT(stable_rtt); + + vec.clear(); + ns->getAddresses(vec); + uint32_t new_rtt = vec[0].getAddressEntry().getRTT(); + + // The rtt should not close to new rtt immediately + EXPECT_TRUE((stable_rtt - new_rtt) > (new_rtt - init_rtt)); + + // Update the rtt for enough times + for(int i = 0; i < 10000; ++i){ + vec[0].updateRTT(stable_rtt); + } + vec.clear(); + ns->getAddresses(vec); + new_rtt = vec[0].getAddressEntry().getRTT(); + + // The rtt should be close to stable rtt value + EXPECT_TRUE((stable_rtt - new_rtt) < (new_rtt - init_rtt)); +} + +} // namespace diff --git a/src/lib/nsas/tests/nsas_entry_compare_unittest.cc b/src/lib/nsas/tests/nsas_entry_compare_unittest.cc new file mode 100644 index 0000000000..837d0c54dd --- /dev/null +++ b/src/lib/nsas/tests/nsas_entry_compare_unittest.cc @@ -0,0 +1,59 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <algorithm> +#include <string> +#include <vector> + +#include <gtest/gtest.h> +#include <boost/lexical_cast.hpp> + +#include "../hash_key.h" +#include "../nsas_entry_compare.h" +#include "nsas_test.h" + +using namespace std; + +namespace isc { +namespace nsas { + +/// \brief Test Fixture Class +class NsasEntryCompareTest : public ::testing::Test { +}; + + +// Test of the comparison +TEST_F(NsasEntryCompareTest, Compare) { + + // Construct a couple of different objects + TestEntry entry1("test1", RRClass(42)); + TestEntry entry2("test1", RRClass(24)); + TestEntry entry3("test2", RRClass(42)); + + // Create corresponding hash key objects + HashKey key1(entry1.getName(), entry1.getClass()); + HashKey key2(entry2.getName(), entry2.getClass()); + HashKey key3(entry3.getName(), entry3.getClass()); + + // Perform the comparison + NsasEntryCompare<TestEntry> compare; + + EXPECT_TRUE(compare(&entry1, key1)); + EXPECT_FALSE(compare(&entry1, key2)); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/nsas_test.h b/src/lib/nsas/tests/nsas_test.h new file mode 100644 index 0000000000..7fc548fd8f --- /dev/null +++ b/src/lib/nsas/tests/nsas_test.h @@ -0,0 +1,411 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __NSAS_TEST_H +#define __NSAS_TEST_H + +/// \file nsas_test.h +/// +/// Contains miscellaneous classes and other stuff to help with the nameserver +/// address store tests. + +#include <string> +#include <vector> + +#include <config.h> + +#include <dns/buffer.h> +#include <dns/rdata.h> +#include <dns/rrtype.h> +#include <dns/rrttl.h> +#include <dns/messagerenderer.h> +#include <dns/rdataclass.h> +#include "../nsas_entry.h" +#include "../resolver_interface.h" + +using namespace isc::dns::rdata; +using namespace isc::dns; + +namespace isc { +namespace dns { + +/// \brief Class Types +/// +/// Very simple classes to provide a type for the RdataTest class below. +/// All they do is return the type code associated with the record type. + +class A { +public: + uint16_t getType() const + {return RRType::A().getCode();} +}; + +class AAAA { +public: + uint16_t getType() const + {return RRType::AAAA().getCode();} +}; + +class MX { +public: + uint16_t getType() const + {return RRType::MX().getCode();} +}; + +/// \brief Hold Rdata +/// +/// A concrete implementation of the Rdata class, this holds data for the +/// tests. All RRs in the tests are either A, AAAA, NS or MX records, and +/// as a result the text form of the Rdata is a single uninterpreted string. +/// For this reason, a single class definition + +template <typename T> +class RdataTest: public Rdata { +public: + + /// \brief Constructor + /// + /// Set the data in the object. + /// + /// \param v4address IPV4 address to store. (The format of this address is + /// not checked.) + RdataTest(const std::string& data) : data_(data) + {} + + /// \brief Convert Rdata to string + /// + /// This is the convenient interface to extract the information stored + /// in this object into a form that can be used by the tests. + virtual std::string toText() const { + return (data_); + } + + /// \brief Return type of Rdata + /// + /// Returns the type of the data. May be useful in the tests, although this + /// will not appear in the main code as this interface is not defined. + virtual uint16_t getType() const { + return (type_.getType()); + } + + /// \name Unused Methods + /// + /// These methods are not used in the tests. + /// + //@{ + /// \brief Render the \c Rdata in the wire format to a buffer + virtual void toWire(OutputBuffer& buffer) const; + + /// \brief render the \Rdata in the wire format to a \c MessageRenderer + virtual void toWire(MessageRenderer& renderer) const; + + /// \brief Comparison Method + virtual int compare(const Rdata& other) const; + //@} + +private: + std::string data_; ///< Rdata itself + T type_; ///< Identifies type of the Rdata +}; + +template <typename T> +void RdataTest<T>::toWire(OutputBuffer&) const { +} + +template <typename T> +void RdataTest<T>::toWire(MessageRenderer&) const { +} + +template <typename T> +int RdataTest<T>::compare(const Rdata&) const { + return 0; +} + +} // namespace dns +} // namespace isc + +namespace isc { +namespace nsas { + +/// \brief Test Entry Class +/// +/// This is an element that can be stored in both the hash table and the +/// LRU list. + +class TestEntry : public NsasEntry<TestEntry> { +public: + + /// \brief Constructor + /// + /// \param name Name that will be used for the object. This will form + /// part of the key. + /// \param class_code Class associated with the object. + TestEntry(std::string name, const isc::dns::RRClass& class_code) : + name_(name), class_code_(class_code) + {} + + /// \brief Virtual Destructor + virtual ~TestEntry() + {} + + /// \brief Return Hash Key + /// + /// This must be overridden in all classes derived from NsasEntry, and + /// returns the hash key corresponding to the name and class. + virtual HashKey hashKey() const { + return HashKey(name_, class_code_); + } + + /// \brief Get the Name + /// + /// \return Name given to this object + virtual std::string getName() const { + return name_; + } + + /// \brief Set the Name + /// + /// \param name New name of the object + virtual void setName(const std::string& name) { + name_ = name; + } + + /// \brief Get the Class + /// + /// \return Class code assigned to this object + virtual const isc::dns::RRClass& getClass() const { + return class_code_; + } + + /// \brief Set the Class + /// + /// \param class_code New class code of the object + virtual void setClass(const isc::dns::RRClass& class_code) { + class_code_ = class_code; + } + +private: + std::string name_; ///< Name of the object + isc::dns::RRClass class_code_; ///< Class of the object +}; + +/// \brief isc::nsas Constants +/// +/// Some constants used in the various tests. + +static const uint32_t HASHTABLE_DEFAULT_SIZE = 1009; ///< First prime above 1000 + +} // namespace nsas +} // namespace isc + +namespace { + +using namespace std; + +/* + * This pretends to be a resolver. It stores the queries and + * they can be answered. + */ +class TestResolver : public isc::nsas::ResolverInterface { + private: + bool checkIndex(size_t index) { + return (requests.size() > index); + } + + typedef std::map<isc::dns::Question, boost::shared_ptr<AbstractRRset> > + PresetAnswers; + PresetAnswers answers_; + public: + typedef pair<QuestionPtr, CallbackPtr> Request; + vector<Request> requests; + virtual void resolve(const QuestionPtr& q, const CallbackPtr& c) { + PresetAnswers::iterator it(answers_.find(*q)); + if (it == answers_.end()) { + requests.push_back(Request(q, c)); + } else { + if (it->second) { + c->success(it->second); + } else { + c->failure(); + } + } + } + + /* + * Add a preset answer. If shared_ptr() is passed (eg. NULL), + * it will generate failure. If the question is not preset, + * it goes to requests and you can answer later. + */ + void addPresetAnswer(const isc::dns::Question& question, + boost::shared_ptr<AbstractRRset> answer) + { + answers_[question] = answer; + } + + // Thrown if the query at the given index does not exist. + class NoSuchRequest : public std::exception { }; + + // Thrown if the answer does not match the query + class DifferentRequest : public std::exception { }; + + QuestionPtr operator[](size_t index) { + if (index >= requests.size()) { + throw NoSuchRequest(); + } + return (requests[index].first); + } + /* + * Looks if the two provided requests in resolver are A and AAAA. + * Sorts them so index1 is A. + * + * Returns false if there aren't enough elements + */ + bool asksIPs(const Name& name, size_t index1, size_t index2) { + size_t max = (index1 < index2) ? index2 : index1; + if (!checkIndex(max)) { + return false; + } + EXPECT_EQ(name, (*this)[index1]->getName()); + EXPECT_EQ(name, (*this)[index2]->getName()); + EXPECT_EQ(RRClass::IN(), (*this)[index1]->getClass()); + EXPECT_EQ(RRClass::IN(), (*this)[index2]->getClass()); + // If they are the other way around, swap + if ((*this)[index1]->getType() == RRType::AAAA() && + (*this)[index2]->getType() == RRType::A()) + { + TestResolver::Request tmp((*this).requests[index1]); + (*this).requests[index1] = + (*this).requests[index2]; + (*this).requests[index2] = tmp; + } + // Check the correct addresses + EXPECT_EQ(RRType::A(), (*this)[index1]->getType()); + EXPECT_EQ(RRType::AAAA(), (*this)[index2]->getType()); + return (true); + } + + /* + * Sends a simple answer to a query. + * Provide index of a query and the address to pass. + */ + void answer(size_t index, const Name& name, const RRType& type, + const rdata::Rdata& rdata, size_t TTL = 100) + { + if (index >= requests.size()) { + throw NoSuchRequest(); + } + RRsetPtr set(new RRset(name, RRClass::IN(), + type, RRTTL(TTL))); + set->addRdata(rdata); + requests[index].second->success(set); + } + + void provideNS(size_t index, + boost::shared_ptr<AbstractRRset> nameservers) + { + if (index >= requests.size()) { + throw NoSuchRequest(); + } + if (requests[index].first->getName() != nameservers->getName() || + requests[index].first->getType() != RRType::NS()) + { + throw DifferentRequest(); + } + requests[index].second->success(nameservers); + } +}; + +// String constants. These should end in a dot. +static const std::string EXAMPLE_CO_UK("example.co.uk."); +static const std::string EXAMPLE_NET("example.net."); +static const std::string MIXED_EXAMPLE_CO_UK("EXAmple.co.uk."); + +class TestWithRdata : public ::testing::Test { +protected: + typedef boost::shared_ptr<RRset> RRsetPtr; + /// \brief Constructor + /// + /// Initializes the RRsets used in the tests. The RRsets themselves have to + /// be initialized with the basic data on their construction. The Rdata for + /// them is added in SetUp(). + TestWithRdata() : + rrv4_(new RRset(Name(EXAMPLE_CO_UK), RRClass::IN(), RRType::A(), + RRTTL(1200))), + rrcase_(new RRset(Name(MIXED_EXAMPLE_CO_UK), RRClass::IN(), + RRType::A(), RRTTL(1200))), + rrch_(new RRset(Name(EXAMPLE_CO_UK), RRClass::CH(), RRType::A(), + RRTTL(1200))), + rrns_(new RRset(Name(EXAMPLE_CO_UK), RRClass::IN(), RRType::NS(), + RRTTL(1200))), + rr_single_(new RRset(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::NS(), RRTTL(600))), + rr_empty_(new RRset(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::NS(), RRTTL(600))), + rrv6_(new RRset(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::AAAA(), RRTTL(900))), + rrnet_(new RRset(Name(EXAMPLE_NET), RRClass::IN(), RRType::A(), + RRTTL(600))), + ns_name_("ns.example.net.") + {} + + /// \brief Add Rdata to RRsets + /// + /// The data are added as const pointers to avoid the stricter type checking + /// applied by the Rdata code. There is no need for it in these tests. + virtual void SetUp() { + + // A records + rrv4_->addRdata(ConstRdataPtr(new RdataTest<A>("1.2.3.4"))); + rrv4_->addRdata(ConstRdataPtr(new RdataTest<A>("5.6.7.8"))); + rrv4_->addRdata(ConstRdataPtr(new RdataTest<A>("9.10.11.12"))); + + // A records + rrcase_->addRdata(ConstRdataPtr(new RdataTest<A>("13.14.15.16"))); + + // No idea what Chaosnet address look like other than they are 16 bits + // The fact that they are type A is probably also incorrect. + rrch_->addRdata(ConstRdataPtr(new RdataTest<A>("1324"))); + + // NS records take a single name + rrns_->addRdata(rdata::generic::NS("example.fr")); + rrns_->addRdata(rdata::generic::NS("example.de")); + + // Single NS record with 0 TTL + rr_single_->addRdata(rdata::generic::NS(ns_name_)); + + // AAAA records + rrv6_->addRdata(ConstRdataPtr(new RdataTest<AAAA>("2001::1002"))); + rrv6_->addRdata(ConstRdataPtr(new RdataTest<AAAA>("dead:beef:feed::"))); + + // A record for example.net + rrnet_->addRdata(ConstRdataPtr(new RdataTest<A>("17.18.18.20"))); + } + + /// \brief Data for the tests + RRsetPtr rrv4_; ///< Standard RRSet - IN, A, lowercase name + RRsetPtr rrcase_; ///< Mixed-case name + RRsetPtr rrch_; ///< Non-IN RRset (Chaos in this case) + RRsetPtr rrns_; ///< NS RRset + RRsetPtr rr_single_; ///< NS RRset with single NS + RRsetPtr rr_empty_; ///< NS RRset without any nameservers + RRsetPtr rrv6_; ///< Standard RRset, IN, AAAA, lowercase name + RRsetPtr rrnet_; ///< example.net A RRset + Name ns_name_; ///< Nameserver name of ns.example.net +}; + +} // Empty namespace + +#endif // __NSAS_TEST_H diff --git a/src/lib/nsas/tests/random_number_generator_unittest.cc b/src/lib/nsas/tests/random_number_generator_unittest.cc new file mode 100644 index 0000000000..714b1afdf9 --- /dev/null +++ b/src/lib/nsas/tests/random_number_generator_unittest.cc @@ -0,0 +1,290 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <gtest/gtest.h> +#include <boost/shared_ptr.hpp> + +#include <algorithm> +#include <iostream> +#include <vector> + +#include "random_number_generator.h" + +namespace isc { +namespace nsas { + +using namespace std; + +/// \brief Test Fixture Class for uniform random number generator +/// +/// The hard part for this test is how to test that the number is random? +/// and how to test that the number is uniformly distributed? +/// Or maybe we can trust the boost implementation +class UniformRandomIntegerGeneratorTest : public ::testing::Test { +public: + UniformRandomIntegerGeneratorTest(): + gen_(min_, max_) + { + } + virtual ~UniformRandomIntegerGeneratorTest(){} + + int gen() { return gen_(); } + int max() const { return max_; } + int min() const { return min_; } + +private: + UniformRandomIntegerGenerator gen_; + + const static int min_ = 1; + const static int max_ = 10; +}; + +/// Some validation tests will incur performance penalty, so the tests are +/// made only in "debug" version with assert(). But if NDEBUG is defined +/// the tests will be failed since assert() is non-op in non-debug version. +/// The "#ifndef NDEBUG" is added to make the tests be performed only in +/// non-debug environment. +#ifndef NDEBUG +// Test of the constructor +TEST_F(UniformRandomIntegerGeneratorTest, Constructor) { + // The range must be min<=max + ASSERT_DEATH(UniformRandomIntegerGenerator(3, 2), ""); +} +#endif + +// Test of the generated integers are in the range [min, max] +TEST_F(UniformRandomIntegerGeneratorTest, IntegerRange) { + vector<int> numbers; + + // Generate a lot of random integers + for(int i = 0; i < max()*10; ++i){ + numbers.push_back(gen()); + } + + // Remove the duplicated values + sort(numbers.begin(), numbers.end()); + vector<int>::iterator it = unique(numbers.begin(), numbers.end()); + + // make sure the numbers are in range [min, max] + ASSERT_EQ(it - numbers.begin(), max() - min() + 1); +} + + +/// \brief Test Fixture Class for weighted random number generator +class WeightedRandomIntegerGeneratorTest : public ::testing::Test { +public: + WeightedRandomIntegerGeneratorTest() + { } + + virtual ~WeightedRandomIntegerGeneratorTest() + { } +}; + +// Test of the weighted random number generator constructor +TEST_F(WeightedRandomIntegerGeneratorTest, Constructor) +{ + vector<double> probabilities; + + // If no probabilities is provided, the smallest integer will always be generated + WeightedRandomIntegerGenerator gen(probabilities, 123); + for(int i = 0; i < 100; ++i){ + ASSERT_EQ(gen(), 123); + } + +/// Some validation tests will incur performance penalty, so the tests are +/// made only in "debug" version with assert(). But if NDEBUG is defined +/// the tests will be failed since assert() is non-op in non-debug version. +/// The "#ifndef NDEBUG" is added to make the tests be performed only in +/// non-debug environment. +#ifndef NDEBUG + //The probability must be >= 0 + probabilities.push_back(-0.1); + probabilities.push_back(1.1); + ASSERT_DEATH(WeightedRandomIntegerGenerator gen2(probabilities), ""); + + //The probability must be <= 1.0 + probabilities.clear(); + probabilities.push_back(0.1); + probabilities.push_back(1.1); + ASSERT_DEATH(WeightedRandomIntegerGenerator gen3(probabilities), ""); + + //The sum must be equal to 1.0 + probabilities.clear(); + probabilities.push_back(0.2); + probabilities.push_back(0.9); + ASSERT_DEATH(WeightedRandomIntegerGenerator gen4(probabilities), ""); + + //The sum must be equal to 1.0 + probabilities.clear(); + probabilities.push_back(0.3); + probabilities.push_back(0.2); + probabilities.push_back(0.1); + ASSERT_DEATH(WeightedRandomIntegerGenerator gen5(probabilities), ""); +#endif +} + +// Test the randomization of the generator +TEST_F(WeightedRandomIntegerGeneratorTest, WeightedRandomization) +{ + const int repeats = 100000; + // We repeat the simulation for N=repeats times + // for each probability p, its average is mu = N*p + // variance sigma^2 = N * p * (1-p) + // sigma = sqrt(N*2/9) + // we should make sure that mu - 4sigma < count < mu + 4sigma + // which means for 99.99366% of the time this should be true + { + double p = 0.5; + vector<double> probabilities; + probabilities.push_back(p); + probabilities.push_back(p); + + // Uniformly generated integers + WeightedRandomIntegerGenerator gen(probabilities); + int c1 = 0; + int c2 = 0; + for(int i = 0; i < repeats; ++i){ + int n = gen(); + if(n == 0) ++c1; + else if(n == 1) ++c2; + } + double mu = repeats * p; + double sigma = sqrt(repeats * p * (1 - p)); + ASSERT_TRUE(fabs(c1 - mu) < 4*sigma); + ASSERT_TRUE(fabs(c2 - mu) < 4*sigma); + } + + { + vector<double> probabilities; + int c1 = 0; + int c2 = 0; + double p1 = 0.2; + double p2 = 0.8; + probabilities.push_back(p1); + probabilities.push_back(p2); + WeightedRandomIntegerGenerator gen(probabilities); + for(int i = 0; i < repeats; ++i){ + int n = gen(); + if(n == 0) ++c1; + else if(n == 1) ++c2; + } + double mu1 = repeats * p1; + double mu2 = repeats * p2; + double sigma1 = sqrt(repeats * p1 * (1 - p1)); + double sigma2 = sqrt(repeats * p2 * (1 - p2)); + ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1); + ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2); + } + + { + vector<double> probabilities; + int c1 = 0; + int c2 = 0; + double p1 = 0.8; + double p2 = 0.2; + probabilities.push_back(p1); + probabilities.push_back(p2); + WeightedRandomIntegerGenerator gen(probabilities); + for(int i = 0; i < repeats; ++i){ + int n = gen(); + if(n == 0) ++c1; + else if(n == 1) ++c2; + } + double mu1 = repeats * p1; + double mu2 = repeats * p2; + double sigma1 = sqrt(repeats * p1 * (1 - p1)); + double sigma2 = sqrt(repeats * p2 * (1 - p2)); + ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1); + ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2); + } + + { + vector<double> probabilities; + int c1 = 0; + int c2 = 0; + int c3 = 0; + double p1 = 0.5; + double p2 = 0.25; + double p3 = 0.25; + probabilities.push_back(p1); + probabilities.push_back(p2); + probabilities.push_back(p3); + WeightedRandomIntegerGenerator gen(probabilities); + for(int i = 0; i < repeats; ++i){ + int n = gen(); + if(n == 0) ++c1; + else if(n == 1) ++c2; + else if(n == 2) ++c3; + } + double mu1 = repeats * p1; + double mu2 = repeats * p2; + double mu3 = repeats * p3; + double sigma1 = sqrt(repeats * p1 * (1 - p1)); + double sigma2 = sqrt(repeats * p2 * (1 - p2)); + double sigma3 = sqrt(repeats * p3 * (1 - p3)); + ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1); + ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2); + ASSERT_TRUE(fabs(c3 - mu3) < 4*sigma3); + } +} + +// Test the reset function of generator +TEST_F(WeightedRandomIntegerGeneratorTest, ResetProbabilities) +{ + const int repeats = 100000; + vector<double> probabilities; + int c1 = 0; + int c2 = 0; + double p1 = 0.8; + double p2 = 0.2; + probabilities.push_back(p1); + probabilities.push_back(p2); + WeightedRandomIntegerGenerator gen(probabilities); + for(int i = 0; i < repeats; ++i){ + int n = gen(); + if(n == 0) ++c1; + else if(n == 1) ++c2; + } + double mu1 = repeats * p1; + double mu2 = repeats * p2; + double sigma1 = sqrt(repeats * p1 * (1 - p1)); + double sigma2 = sqrt(repeats * p2 * (1 - p2)); + ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1); + ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2); + + // Reset the probabilities + probabilities.clear(); + c1 = c2 = 0; + p1 = 0.2; + p2 = 0.8; + probabilities.push_back(p1); + probabilities.push_back(p2); + gen.reset(probabilities); + for(int i = 0; i < repeats; ++i){ + int n = gen(); + if(n == 0) ++c1; + else if(n == 1) ++c2; + } + mu1 = repeats * p1; + mu2 = repeats * p2; + sigma1 = sqrt(repeats * p1 * (1 - p1)); + sigma2 = sqrt(repeats * p2 * (1 - p2)); + ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1); + ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2); +} + +} // namespace nsas +} // namespace isc diff --git a/src/lib/nsas/tests/run_unittests.cc b/src/lib/nsas/tests/run_unittests.cc new file mode 100644 index 0000000000..c8e9189589 --- /dev/null +++ b/src/lib/nsas/tests/run_unittests.cc @@ -0,0 +1,26 @@ +// Copyright (C) 2009 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id: run_unittests.cc 3020 2010-09-26 03:47:26Z jinmei $ + +#include <gtest/gtest.h> + +#include <dns/tests/unittest_util.h> + +int +main(int argc, char* argv[]) { + ::testing::InitGoogleTest(&argc, argv); + + return (RUN_ALL_TESTS()); +} diff --git a/src/lib/nsas/tests/zone_entry_unittest.cc b/src/lib/nsas/tests/zone_entry_unittest.cc new file mode 100644 index 0000000000..412f05decc --- /dev/null +++ b/src/lib/nsas/tests/zone_entry_unittest.cc @@ -0,0 +1,753 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#include <gtest/gtest.h> +#include <boost/shared_ptr.hpp> +#include <boost/foreach.hpp> +#include <boost/lexical_cast.hpp> +#include <cmath> + +#include <dns/rrclass.h> +#include <dns/rdataclass.h> + +#include "../asiolink.h" +#include "../zone_entry.h" +#include "../nameserver_entry.h" +#include "../address_request_callback.h" +#include "../nsas_entry_compare.h" +#include "../hash_deleter.h" + +#include "nsas_test.h" + +using namespace isc::nsas; +using namespace asiolink; +using namespace std; +using namespace boost; +using namespace isc::dns; + +namespace { + +/// \brief Inherited version with access into its internals for tests +class InheritedZoneEntry : public ZoneEntry { + public: + InheritedZoneEntry(shared_ptr<ResolverInterface> resolver, + const std::string& name, const RRClass& class_code, + shared_ptr<HashTable<NameserverEntry> > nameserver_table, + shared_ptr<LruList<NameserverEntry> > nameserver_lru) : + ZoneEntry(resolver, name, class_code, nameserver_table, + nameserver_lru) + { } + NameserverVector& nameservers() { return nameservers_; } +}; + +/// \brief Test Fixture Class +class ZoneEntryTest : public TestWithRdata { +protected: + /// \brief Constructor + ZoneEntryTest() : + nameserver_table_(new HashTable<NameserverEntry>( + new NsasEntryCompare<NameserverEntry>)), + nameserver_lru_(new LruList<NameserverEntry>( + (3 * nameserver_table_->tableSize()), + new HashDeleter<NameserverEntry>(*nameserver_table_))), + resolver_(new TestResolver), + callback_(new Callback) + { } + /// \brief Tables of nameservers to pass into zone entry constructor + shared_ptr<HashTable<NameserverEntry> > nameserver_table_; + shared_ptr<LruList<NameserverEntry> > nameserver_lru_; + /// \brief The resolver + shared_ptr<TestResolver> resolver_; + + /** + * \short A callback we use into the zone. + * + * It counts failures and stores successufll results. + */ + struct Callback : public AddressRequestCallback { + Callback() : unreachable_count_(0) {} + size_t unreachable_count_; + vector<NameserverAddress> successes_; + virtual void unreachable() { unreachable_count_ ++; } + virtual void success(const NameserverAddress& address) { + successes_.push_back(address); + } + }; + shared_ptr<Callback> callback_; + + // Empty callback to pass to nameserver entry, to do injection of them + struct NseCallback : public NameserverEntry::Callback { + virtual void operator()(shared_ptr<NameserverEntry>) { } + }; + + shared_ptr<NseCallback> nseCallback() { + return (shared_ptr<NseCallback>(new NseCallback)); + } + + /** + * \short Function returning a new zone. + * + * Convenience funcion, just creating a new zone, to shorten the code. + */ + shared_ptr<InheritedZoneEntry> getZone() { + return (shared_ptr<InheritedZoneEntry>(new InheritedZoneEntry( + resolver_, EXAMPLE_CO_UK, RRClass::IN(), nameserver_table_, + nameserver_lru_))); + } + + /** + * \short Creates and injects a NameserverEntry + * + * This is used by few tests checking it works when the nameserver + * hash table already contains the NameserverEntry. This function + * creates one and puts it into the hash table. + */ + shared_ptr<NameserverEntry> injectEntry() { + shared_ptr<NameserverEntry> nse(new NameserverEntry(ns_name_.toText(), + RRClass::IN())); + nameserver_table_->add(nse, HashKey(ns_name_.toText(), RRClass::IN())); + EXPECT_EQ(Fetchable::NOT_ASKED, nse->getState()); + return (nse); + } + + /** + * \short Common part of few tests. + * + * All the tests NameserverEntryReady, NameserverEntryNotAsked, + * NameserverEntryInProgress, NameserverEntryExpired, + * NameserverEntryUnreachable check that it does not break + * when the nameserver hash table already contains the nameserver + * in one of the Fetchable::State. + * + * All the tests prepare the NameserverEntry and then call this + * to see if the zone really works. This asks and checks if it + * asks for the IP addresses or not and if it succeeds or fails. + * + * \param answer Should it ask for IP addresses of the nameserver? + * If not, it expects it already asked during the preparation + * (therefore the request count in resolver is 2). + * \param success_count How many callbacks to the zone should + * succeed. + * \param failure_count How many callbacks to the zone should + * fail. + */ + void checkInjected(bool answer, size_t success_count = 1, + size_t failure_count = 0) + { + // Create the zone and check it acts correctly + shared_ptr<InheritedZoneEntry> zone(getZone()); + resolver_->addPresetAnswer(Question(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::NS()), rr_single_); + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(2, resolver_->requests.size()); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 0, 1)); + if (answer) { + EXPECT_NO_THROW(resolver_->answer(0, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"))); + EXPECT_NO_THROW(resolver_->answer(1, ns_name_, RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"))); + } + // Check the answers + EXPECT_EQ(Fetchable::READY, zone->getState()); + EXPECT_EQ(failure_count, callback_->unreachable_count_); + EXPECT_EQ(success_count, callback_->successes_.size()); + for (size_t i = 0; i < callback_->successes_.size(); ++ i) { + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[i].getAddress()) || + IOAddress("2001:db8::1").equal( + callback_->successes_[i].getAddress())); + } + } +}; + +/// Tests of the default constructor +TEST_F(ZoneEntryTest, DefaultConstructor) { + + // Default constructor should not create any RRsets + InheritedZoneEntry alpha(resolver_, EXAMPLE_CO_UK, + RRClass::IN(), nameserver_table_, nameserver_lru_); + EXPECT_EQ(EXAMPLE_CO_UK, alpha.getName()); + EXPECT_EQ(RRClass::IN(), alpha.getClass()); + EXPECT_TRUE(alpha.nameservers().empty()); +} + +/** + * \short Test with no nameservers. + * + * When we create a zone that does not have any nameservers, + * it should return failures right away (eg. no queries to nameservers + * should be generated anywhere and the failure should be provided). + */ +TEST_F(ZoneEntryTest, CallbackNoNS) { + shared_ptr<InheritedZoneEntry> zone(getZone()); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + // feed it with a callback + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + // Give it the (empty) nameserver list + EXPECT_NO_THROW(resolver_->provideNS(0, rr_empty_)); + // It should tell us it is unreachable. + EXPECT_TRUE(callback_->successes_.empty()); + EXPECT_EQ(1, callback_->unreachable_count_); +} + +/** + * \short Test how the zone behaves when the list of nameserves change. + * + * We use TTL of 0, so it asks every time for new list of nameservers. + * This allows us to pass a different list each time. + * + * So, this implicitly tests that it behaves correctly with 0 TTL as well, + * it means that it answers even with 0 TTL and that it answers only + * one query (or, all queries queued at that time). + * + * We change the list twice, to see it can ask for another nameserver and + * then to see if it can return to the previous (already cached) nameserver. + */ +TEST_F(ZoneEntryTest, ChangedNS) { + // Make it zero TTL, so it expires right away + rr_single_->setTTL(RRTTL(0)); + shared_ptr<InheritedZoneEntry> zone(getZone()); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + // Feed it with callback + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + EXPECT_NO_THROW(resolver_->provideNS(0, rr_single_)); + // It should not be answered yet, it should ask for the IP addresses + // (trough the NameserverEntry there) + EXPECT_TRUE(callback_->successes_.empty()); + EXPECT_EQ(0, callback_->unreachable_count_); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 1, 2)); + EXPECT_NO_THROW(resolver_->answer(1, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"))); + ASSERT_EQ(1, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[0].getAddress())); + EXPECT_NO_THROW(resolver_->answer(2, ns_name_, RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"))); + EXPECT_EQ(1, callback_->successes_.size()); + // It should request the NSs again, as TTL is 0 + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(4, resolver_->requests.size()); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + + Name different_name("ns.example.com"); + // Create a different answer + RRsetPtr different_ns(new RRset(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::NS(), RRTTL(0))); + different_ns->addRdata(rdata::generic::NS(different_name)); + EXPECT_NO_THROW(resolver_->provideNS(3, different_ns)); + // It should become ready and ask for the new nameserver addresses + EXPECT_EQ(Fetchable::READY, zone->getState()); + // Answer one of the IP addresses, we should get an address now + EXPECT_TRUE(resolver_->asksIPs(different_name, 4, 5)); + EXPECT_NO_THROW(resolver_->answer(4, different_name, RRType::A(), + rdata::in::A("192.0.2.2"))); + ASSERT_EQ(2, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.2").equal( + callback_->successes_[1].getAddress())); + + // And now, switch back, as it timed out again + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(7, resolver_->requests.size()); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + // When we answer with the original, it should still be cached and + // we should get the answer + EXPECT_NO_THROW(resolver_->provideNS(0, rr_single_)); + EXPECT_EQ(7, resolver_->requests.size()); + EXPECT_EQ(Fetchable::READY, zone->getState()); + ASSERT_EQ(3, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[0].getAddress())); +} + +/** + * \short Check it works when everything is answered. + * + * This test emulates a situation when all queries for NS rrsets and + * IP addresses (of the NameserverEntry objects inside) are answered + * positively. All the callbacks should be called and answer to them + * provided. + */ +TEST_F(ZoneEntryTest, CallbacksAnswered) { + shared_ptr<InheritedZoneEntry> zone(getZone()); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + // Feed it with a callback + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + EXPECT_NO_THROW(resolver_->provideNS(0, rr_single_)); + // It should not be answered yet, its NameserverEntry should ask for the + // IP addresses + EXPECT_TRUE(callback_->successes_.empty()); + EXPECT_EQ(0, callback_->unreachable_count_); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 1, 2)); + // We should be READY, as it marks we have nameservers + // (not that they are ready) + EXPECT_EQ(Fetchable::READY, zone->getState()); + // Give two more callbacks, with different address families + zone->addCallback(callback_, V4_ONLY); + zone->addCallback(callback_, V6_ONLY); + // Nothing more is asked + EXPECT_EQ(3, resolver_->requests.size()); + EXPECT_NO_THROW(resolver_->answer(1, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"))); + // Two are answered (ANY and V4) + ASSERT_EQ(2, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[0].getAddress())); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[1].getAddress())); + // None are rejected + EXPECT_EQ(0, callback_->unreachable_count_); + // Answer the IPv6 one as well + EXPECT_NO_THROW(resolver_->answer(2, ns_name_, RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"))); + // This should answer the third callback + EXPECT_EQ(0, callback_->unreachable_count_); + ASSERT_EQ(3, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("2001:db8::1").equal( + callback_->successes_[2].getAddress())); + // It should think it is ready + EXPECT_EQ(Fetchable::READY, zone->getState()); + // When we ask something more, it should be answered right away + zone->addCallback(callback_, V4_ONLY); + EXPECT_EQ(3, resolver_->requests.size()); + ASSERT_EQ(4, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[3].getAddress())); + EXPECT_EQ(0, callback_->unreachable_count_); +} + +/** + * \short Test zone reachable only on IPv4. + * + * This test simulates a zone with its nameservers reachable only + * over IPv4. It means we answer the NS query, the A query, but + * we generate a failure for AAAA. + * + * The callbacks asking for any address and IPv4 address should be + * called successfully, while the ones asking for IPv6 addresses should + * fail. + */ +TEST_F(ZoneEntryTest, CallbacksAOnly) { + shared_ptr<InheritedZoneEntry> zone(getZone()); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + EXPECT_NO_THROW(resolver_->provideNS(0, rr_single_)); + // It should not be answered yet, it should ask for the IP addresses + EXPECT_TRUE(callback_->successes_.empty()); + EXPECT_EQ(0, callback_->unreachable_count_); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 1, 2)); + EXPECT_EQ(Fetchable::READY, zone->getState()); + // Give two more callbacks, with different address families + zone->addCallback(callback_, V4_ONLY); + zone->addCallback(callback_, V6_ONLY); + ASSERT_GE(resolver_->requests.size(), 3); + // We tell its NameserverEntry we can't get IPv6 address + resolver_->requests[2].second->failure(); + // One should be rejected (V6_ONLY one), but two still stay + EXPECT_EQ(0, callback_->successes_.size()); + EXPECT_EQ(1, callback_->unreachable_count_); + // Answer the A one and see it answers what can be answered + EXPECT_NO_THROW(resolver_->answer(1, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"))); + ASSERT_EQ(2, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[0].getAddress())); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[1].getAddress())); + EXPECT_EQ(1, callback_->unreachable_count_); + // Everything arriwed, so we are ready + EXPECT_EQ(Fetchable::READY, zone->getState()); + // Try asking something more and see it asks no more + zone->addCallback(callback_, V4_ONLY); + EXPECT_EQ(3, resolver_->requests.size()); + ASSERT_EQ(3, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[2].getAddress())); + EXPECT_EQ(1, callback_->unreachable_count_); + + zone->addCallback(callback_, V6_ONLY); + EXPECT_EQ(3, resolver_->requests.size()); + EXPECT_EQ(3, callback_->successes_.size()); + EXPECT_EQ(2, callback_->unreachable_count_); +} + +/** + * \short Test with unreachable and v6-reachable nameserver. + * + * In this test we have a zone with two nameservers. The first one of them + * is unreachable, it will not have any addresses. We check that the ZoneEntry + * is patient and asks and waits for the second one and then returns the + * (successful) answers to us. + */ +TEST_F(ZoneEntryTest, CallbackTwoNS) { + shared_ptr<InheritedZoneEntry> zone(getZone()); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + zone->addCallback(callback_, V4_ONLY); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + EXPECT_NO_THROW(resolver_->provideNS(0, rrns_)); + EXPECT_EQ(Fetchable::READY, zone->getState()); + // It asks a question (we do not know which nameserver) + shared_ptr<Name> name; + ASSERT_NO_THROW(name.reset(new Name((*resolver_)[1]->getName()))); + ASSERT_TRUE(resolver_->asksIPs(*name, 1, 2)); + resolver_->requests[1].second->failure(); + // Nothing should be answered or failed yet, there's second one + EXPECT_EQ(0, callback_->unreachable_count_); + EXPECT_EQ(0, callback_->successes_.size()); + ASSERT_TRUE(resolver_->asksIPs((*resolver_)[3]->getName(), 3, 4)); + // Fail the second one + resolver_->requests[3].second->failure(); + // The callback should be failed now, as there is no chance of getting + // v4 address + EXPECT_EQ(1, callback_->unreachable_count_); + EXPECT_EQ(0, callback_->successes_.size()); + // And question for v6 or any should still wait while v4 should be failed + // right away + zone->addCallback(callback_, V6_ONLY); + EXPECT_EQ(1, callback_->unreachable_count_); + EXPECT_EQ(0, callback_->successes_.size()); + + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(1, callback_->unreachable_count_); + EXPECT_EQ(0, callback_->successes_.size()); + + zone->addCallback(callback_, V4_ONLY); + EXPECT_EQ(2, callback_->unreachable_count_); + EXPECT_EQ(0, callback_->successes_.size()); + // Answer the IPv6 one + EXPECT_NO_THROW(resolver_->answer(2, (*resolver_)[2]->getName(), + RRType::AAAA(), rdata::in::AAAA("2001:db8::1"))); + + // Ready, as we have at last some address + EXPECT_EQ(Fetchable::READY, zone->getState()); + // The other callbacks should be answered now + EXPECT_EQ(2, callback_->unreachable_count_); + ASSERT_EQ(2, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("2001:db8::1").equal( + callback_->successes_[0].getAddress())); + EXPECT_TRUE(IOAddress("2001:db8::1").equal( + callback_->successes_[1].getAddress())); +} + +/** + * \short This test checks it works with answers from cache. + * + * The resolver might provide the answer by calling the callback both sometime + * later or directly from its resolve method, causing recursion back inside + * the ZoneEntry. This test checks it works even in the second case (eg. that + * the ZoneEntry is able to handle callback called directly from the + * resolve). Tries checking both positive and negative answers. + */ +TEST_F(ZoneEntryTest, DirectAnswer) { + shared_ptr<InheritedZoneEntry> zone(getZone()); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + + // One unsuccessfull attempt, nameservers fail + resolver_->addPresetAnswer(Question(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::NS()), shared_ptr<AbstractRRset>()); + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(0, callback_->successes_.size()); + EXPECT_EQ(1, callback_->unreachable_count_); + EXPECT_EQ(0, resolver_->requests.size()); + EXPECT_EQ(Fetchable::UNREACHABLE, zone->getState()); + + // Successfull attempt now + zone = getZone(); + // First, fill the answers to all the questions it should ask + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + resolver_->addPresetAnswer(Question(Name(EXAMPLE_CO_UK), RRClass::IN(), + RRType::NS()), rr_single_); + Name ns_name("ns.example.net"); + rrv4_->setName(ns_name); + resolver_->addPresetAnswer(Question(ns_name, RRClass::IN(), RRType::A()), + rrv4_); + rrv6_->setName(ns_name); + resolver_->addPresetAnswer(Question(ns_name, RRClass::IN(), + RRType::AAAA()), rrv6_); + // Reset the results + callback_->unreachable_count_ = 0; + // Ask for the IP address + zone->addCallback(callback_, ANY_OK); + // It should be answered right away, positively + EXPECT_EQ(1, callback_->successes_.size()); + EXPECT_EQ(0, callback_->unreachable_count_); + EXPECT_EQ(0, resolver_->requests.size()); + EXPECT_EQ(Fetchable::READY, zone->getState()); + + // Reset the results + callback_->successes_.clear(); + // Now, pretend we do not have IP addresses + resolver_->addPresetAnswer(Question(ns_name, RRClass::IN(), RRType::A()), + shared_ptr<AbstractRRset>()); + resolver_->addPresetAnswer(Question(ns_name, RRClass::IN(), + RRType::AAAA()), shared_ptr<AbstractRRset>()); + // Get another zone and ask it again. It should fail. + // Clean the table first, though, so it does not find the old nameserver + nameserver_table_->remove(HashKey(ns_name.toText(), RRClass::IN())); + zone = getZone(); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(0, callback_->successes_.size()); + EXPECT_EQ(1, callback_->unreachable_count_); + EXPECT_EQ(0, resolver_->requests.size()); + // It should be ready, but have no IP addresses on the nameservers + EXPECT_EQ(Fetchable::READY, zone->getState()); +} + +/** + * \short Test it works with timeouting NameserverEntries. + * + * In this test we have a zone with nameserver addresses at TTL 0. + * So, the NameserverEntry expires each time the ZoneEntry tries to get + * its addresses and must ask it again. + */ +TEST_F(ZoneEntryTest, AddressTimeout) { + shared_ptr<InheritedZoneEntry> zone(getZone()); + EXPECT_EQ(Fetchable::NOT_ASKED, zone->getState()); + zone->addCallback(callback_, ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, zone->getState()); + EXPECT_NO_THROW(resolver_->provideNS(0, rr_single_)); + // It should not be answered yet, it should ask for the IP addresses + EXPECT_TRUE(callback_->successes_.empty()); + EXPECT_EQ(0, callback_->unreachable_count_); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 1, 2)); + // We should be READY, as it marks we have nameservers + // (not that they are ready) + EXPECT_EQ(Fetchable::READY, zone->getState()); + EXPECT_NO_THROW(resolver_->answer(1, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"), 0)); + // It answers, not rejects + ASSERT_EQ(1, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[0].getAddress())); + EXPECT_EQ(0, callback_->unreachable_count_); + // As well with IPv6 + EXPECT_NO_THROW(resolver_->answer(2, ns_name_, RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"), 0)); + EXPECT_EQ(1, callback_->successes_.size()); + EXPECT_EQ(Fetchable::READY, zone->getState()); + // When we ask for another one, it should ask for the addresses again + zone->addCallback(callback_, ANY_OK); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 3, 4)); + EXPECT_EQ(0, callback_->unreachable_count_); + EXPECT_EQ(1, callback_->successes_.size()); + EXPECT_NO_THROW(resolver_->answer(3, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"), 0)); + EXPECT_EQ(0, callback_->unreachable_count_); + ASSERT_EQ(2, callback_->successes_.size()); + EXPECT_TRUE(IOAddress("192.0.2.1").equal( + callback_->successes_[1].getAddress())); +} + +/** + * \short Injection tests. + * + * These tests check the ZoneEntry does not break when the nameserver hash + * table already contains a NameserverEntry in some given state. Each test + * for a different state. + */ +//@{ + +/// \short Test how the zone reacts to a nameserver entry in ready state +TEST_F(ZoneEntryTest, NameserverEntryReady) { + // Inject the entry + shared_ptr<NameserverEntry> nse(injectEntry()); + // Fill it with data + nse->askIP(resolver_, nseCallback(), ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, nse->getState()); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 0, 1)); + EXPECT_NO_THROW(resolver_->answer(0, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"))); + EXPECT_NO_THROW(resolver_->answer(1, ns_name_, RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"))); + EXPECT_EQ(Fetchable::READY, nse->getState()); + + checkInjected(false); +} + +/// \short Test how the zone reacts to a nameserver in not asked state +TEST_F(ZoneEntryTest, NameserverEntryNotAsked) { + // Inject the entry + injectEntry(); + // We do not need it, nothing to modify on it + + checkInjected(true); +} + +/// \short What if the zone finds a nameserver in progress? +TEST_F(ZoneEntryTest, NameserverEntryInProgress) { + // Prepare the nameserver entry + shared_ptr<NameserverEntry> nse(injectEntry()); + nse->askIP(resolver_, nseCallback(), ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, nse->getState()); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 0, 1)); + + checkInjected(true); +} + +/// \short Check Zone's reaction to found expired nameserver +TEST_F(ZoneEntryTest, NameserverEntryExpired) { + shared_ptr<NameserverEntry> nse(injectEntry()); + nse->askIP(resolver_, nseCallback(), ANY_OK); + EXPECT_EQ(Fetchable::IN_PROGRESS, nse->getState()); + EXPECT_TRUE(resolver_->asksIPs(ns_name_, 0, 1)); + EXPECT_NO_THROW(resolver_->answer(0, ns_name_, RRType::A(), + rdata::in::A("192.0.2.1"), 0)); + EXPECT_NO_THROW(resolver_->answer(1, ns_name_, RRType::AAAA(), + rdata::in::AAAA("2001:db8::1"), 0)); + EXPECT_EQ(Fetchable::READY, nse->getState()); + NameserverEntry::AddressVector addresses; + EXPECT_EQ(Fetchable::EXPIRED, nse->getAddresses(addresses)); + EXPECT_EQ(Fetchable::EXPIRED, nse->getState()); + resolver_->requests.clear(); + + checkInjected(true); +} + +/// \short Check how it reacts to an unreachable zone already in the table +TEST_F(ZoneEntryTest, NameserverEntryUnreachable) { + shared_ptr<NameserverEntry> nse(injectEntry()); + nse->askIP(resolver_, nseCallback(), ANY_OK); + ASSERT_EQ(2, resolver_->requests.size()); + resolver_->requests[0].second->failure(); + resolver_->requests[1].second->failure(); + EXPECT_EQ(Fetchable::UNREACHABLE, nse->getState()); + + checkInjected(false, 0, 1); +} + +//@} + +// Count hits of each address +void +countHits(size_t *counts, const vector<NameserverAddress>& successes) { + BOOST_FOREACH(const NameserverAddress& address, successes) { + // We use the last digit as an index + string address_string(address.getAddress().toText()); + size_t index(address_string[address_string.size() - 1] - '0' - 1); + ASSERT_LT(index, 3); + counts[index] ++; + } +} + +// Select one address from the address list +TEST_F(ZoneEntryTest, AddressSelection) { + const size_t repeats = 100000; + // Create the zone, give it 2 nameservers and total of 3 addresses + // (one of them is ipv6) + shared_ptr<ZoneEntry> zone(getZone()); + zone->addCallback(callback_, ANY_OK); + EXPECT_NO_THROW(resolver_->provideNS(0, rrns_)); + ASSERT_GT(resolver_->requests.size(), 1); + Name name1(resolver_->requests[1].first->getName()); + EXPECT_TRUE(resolver_->asksIPs(name1, 1, 2)); + resolver_->answer(1, name1, RRType::A(), rdata::in::A("192.0.2.1")); + resolver_->answer(2, name1, RRType::AAAA(), + rdata::in::AAAA("2001:db8::2")); + ASSERT_GT(resolver_->requests.size(), 3); + Name name2(resolver_->requests[3].first->getName()); + EXPECT_TRUE(resolver_->asksIPs(name2, 3, 4)); + resolver_->answer(3, name2, RRType::A(), rdata::in::A("192.0.2.3")); + resolver_->requests[4].second->failure(); + + shared_ptr<NameserverEntry> ns1(nameserver_table_->get(HashKey( + name1.toText(), RRClass::IN()))), + ns2(nameserver_table_->get(HashKey(name2.toText(), RRClass::IN()))); + + size_t counts[3] = {0, 0, 0}; + callback_->successes_.clear(); + + // Test they have the same probabilities when they have the same RTT + for (size_t i(0); i < repeats; ++ i) { + zone->addCallback(callback_, ANY_OK); + } + countHits(counts, callback_->successes_); + // We repeat the simulation for N=repeats times + // for each address, the probability is p = 1/3, the average mu = N*p + // variance sigma^2 = N * p * (1-p) = N * 1/3 * 2/3 = N*2/9 + // sigma = sqrt(N*2/9) + // we should make sure that mu - 4sigma < c < mu + 4sigma + // which means for 99.99366% of the time this should be true + double p = 1.0 / 3.0; + double mu = repeats * p; + double sigma = sqrt(repeats * p * (1 - p)); + for (size_t i(0); i < 3; ++ i) { + ASSERT_TRUE(fabs(counts[i] - mu) < 4*sigma); + } + + // reset the environment + callback_->successes_.clear(); + counts[0] = counts[1] = counts[2] = 0; + + // Test when the RTT is not the same + ns1->setAddressRTT(IOAddress("192.0.2.1"), 1); + ns1->setAddressRTT(IOAddress("2001:db8::2"), 2); + ns2->setAddressRTT(IOAddress("192.0.2.3"), 3); + for (size_t i(0); i < repeats; ++ i) { + zone->addCallback(callback_, ANY_OK); + } + countHits(counts, callback_->successes_); + // We expect that the selection probability for each address that + // it will be in the range of [mu-4Sigma, mu+4Sigma] + double ps[3]; + ps[0] = 1.0/(1.0 + 1.0/4.0 + 1.0/9.0); + ps[1] = (1.0/4.0)/(1.0 + 1.0/4.0 + 1.0/9.0); + ps[2] = (1.0/9.0)/(1.0 + 1.0/4.0 + 1.0/9.0); + for (size_t i(0); i < 3; ++ i) { + double mu = repeats * ps[i]; + double sigma = sqrt(repeats * ps[i] * (1 - ps[i])); + ASSERT_TRUE(fabs(counts[i] - mu < 4 * sigma)); + } + + // reset the environment + callback_->successes_.clear(); + counts[0] = counts[1] = counts[2] = 0; + + // Test with unreachable address + ns1->setAddressRTT(IOAddress("192.0.2.1"), 1); + ns1->setAddressRTT(IOAddress("2001:db8::2"), 100); + ns2->setAddressUnreachable(IOAddress("192.0.2.3")); + for (size_t i(0); i < repeats; ++ i) { + zone->addCallback(callback_, ANY_OK); + } + countHits(counts, callback_->successes_); + // The unreachable one shouldn't be called + EXPECT_EQ(0, counts[2]); + + // reset the environment + callback_->successes_.clear(); + counts[0] = counts[1] = counts[2] = 0; + + // Test with all unreachable + ns1->setAddressUnreachable(IOAddress("192.0.2.1")); + ns1->setAddressUnreachable(IOAddress("2001:db8::2")); + ns2->setAddressUnreachable(IOAddress("192.0.2.3")); + for (size_t i(0); i < repeats; ++ i) { + zone->addCallback(callback_, ANY_OK); + } + countHits(counts, callback_->successes_); + // They should have about the same probability + for (size_t i(0); i < 3; ++ i) { + ASSERT_TRUE(fabs(counts[i] - mu) < 4*sigma); + } + + // TODO: The unreachable server should be changed to reachable after 5minutes, but how to test? +} + +} // namespace diff --git a/src/lib/nsas/zone_entry.cc b/src/lib/nsas/zone_entry.cc new file mode 100644 index 0000000000..25d5660091 --- /dev/null +++ b/src/lib/nsas/zone_entry.cc @@ -0,0 +1,526 @@ +// Copyright (C) 2010 CZ NIC +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $id$ + +#include "zone_entry.h" +#include "address_request_callback.h" +#include "nameserver_entry.h" + +#include <algorithm> +#include <boost/foreach.hpp> +#include <boost/random.hpp> +#include <dns/rrttl.h> +#include <dns/rdataclass.h> + +using namespace std; +using namespace boost; + +namespace isc { + +using namespace dns; + +namespace nsas { + +ZoneEntry::ZoneEntry(boost::shared_ptr<ResolverInterface> resolver, + const std::string& name, const isc::dns::RRClass& class_code, + boost::shared_ptr<HashTable<NameserverEntry> > nameserver_table, + boost::shared_ptr<LruList<NameserverEntry> > nameserver_lru) : + expiry_(0), + name_(name), class_code_(class_code), resolver_(resolver), + nameserver_table_(nameserver_table), nameserver_lru_(nameserver_lru) +{ + in_process_[ANY_OK] = false; + in_process_[V4_ONLY] = false; + in_process_[V6_ONLY] = false; +} + +namespace { +// Shorter aliases for frequently used types +typedef recursive_mutex::scoped_lock Lock; // Local lock, nameservers not locked +typedef shared_ptr<AddressRequestCallback> CallbackPtr; + +/* + * Create a nameserver. + * Called inside a mutex so it is filled in atomically. + */ +shared_ptr<NameserverEntry> +newNs(const std::string* name, const RRClass* class_code) { + return (shared_ptr<NameserverEntry>(new NameserverEntry(*name, + *class_code))); +} + +} + +/** + * \short Callback class that ZoneEntry passes to a resolver. + * + * We need to ask for the list of nameservers. So we pass ResolverCallback + * object to it, when it knows the answer, method of this thing will be + * called. + * + * It is a nested friend class and should be considered as a part of ZoneEntry + * code. It manipulates directly ZoneEntry's data members, locks it and like + * that. Mostly eliminates C++ bad design of missing lambda functions. + */ +class ZoneEntry::ResolverCallback : public ResolverInterface::Callback { + public: + /// \short Constructor. Pass "this" zone entry + ResolverCallback(shared_ptr<ZoneEntry> entry) : + entry_(entry) + { } + /** + * \short It successfully received nameserver list. + * + * It fills the nameservers into the ZoneEntry whose callback this is. + * If there are in the hash table, it is used. If not, they are + * created. This might still fail, if the list is empty. + * + * It then calls process, to go trough the list of nameservers, + * examining them and seeing if some addresses are already there + * and to ask for the rest of them. + */ + virtual void success(const shared_ptr<AbstractRRset>& answer) { + Lock lock(entry_->mutex_); + RdataIteratorPtr iterator(answer->getRdataIterator()); + // If there are no data + if (iterator->isLast()) { + failureInternal(answer->getTTL().getValue()); + return; + } else { + /* + * We store the nameservers we have currently (we might have + * none, at startup, but when we time out and ask again, we + * do), so we can just reuse them instead of looking them up in + * the table or creating them. + */ + map<string, NameserverPtr> old; + BOOST_FOREACH(const NameserverPtr& ptr, entry_->nameservers_) { + old[ptr->getName()] = ptr; + } + /* + * List of original nameservers we did not ask for IP address + * yet. + */ + set<NameserverPtr> old_not_asked; + old_not_asked.swap(entry_->nameservers_not_asked_); + + // Once we have them put aside, remove the original set + // of nameservers from the entry + entry_->nameservers_.clear(); + // And put the ones from the answer them, reusing if possible + for (; !iterator->isLast(); iterator->next()) { + try { + // Get the name from there + Name ns_name(dynamic_cast<const rdata::generic::NS&>( + iterator->getCurrent()).getNSName()); + // Try to find it in the old ones + map<string, NameserverPtr>::iterator old_ns(old.find( + ns_name.toText())); + /* + * We didn't have this nameserver before. So we just + * look it up in the hash table or create it. + */ + if (old_ns == old.end()) { + // Look it up or create it + string ns_name_str(ns_name.toText()); + pair<bool, NameserverPtr> from_hash( + entry_->nameserver_table_->getOrAdd(HashKey( + ns_name_str, entry_->class_code_), bind( + newNs, &ns_name_str, &entry_->class_code_))); + // Make it at the front of the list + if (from_hash.first) { + entry_->nameserver_lru_->add(from_hash.second); + } else { + entry_->nameserver_lru_->touch( + from_hash.second); + } + // And add it at last to the entry + entry_->nameservers_.push_back(from_hash.second); + entry_->nameservers_not_asked_.insert( + from_hash.second); + } else { + // We had it before, reuse it + entry_->nameservers_.push_back(old_ns->second); + // Did we ask it already? If not, it is still not + // asked (the one designing std interface must + // have been mad) + if (old_not_asked.find(old_ns->second) != + old_not_asked.end()) + { + entry_->nameservers_not_asked_.insert( + old_ns->second); + } + } + } + // OK, we skip this one as it is not NS (log?) + catch (bad_cast&) { } + } + + // It is unbelievable, but we found no nameservers there + if (entry_->nameservers_.empty()) { + // So we fail the same way as if we got empty list + failureInternal(answer->getTTL().getValue()); + return; + } else { + // Ok, we have them. So set us as ready, set our + // expiration time and try to answer what we can, ask + // if there's still someone to ask. + entry_->setState(READY); + entry_->expiry_ = answer->getTTL().getValue() + time(NULL); + entry_->process(ADDR_REQ_MAX, NameserverPtr()); + return; + } + } + } + /// \short Failed to receive answer. + virtual void failure() { + failureInternal(300); + } + private: + /** + * \short Common function called when "it did not work" + * + * It marks the ZoneEntry as unreachable and processes callbacks (by + * calling process). + */ + void failureInternal(time_t ttl) { + Lock lock(entry_->mutex_); + entry_->setState(UNREACHABLE); + entry_->expiry_ = ttl + time(NULL); + // Process all three callback lists and tell them KO + entry_->process(ADDR_REQ_MAX, NameserverPtr()); + } + /// \short The entry we are callback of + shared_ptr<ZoneEntry> entry_; +}; + +void +ZoneEntry::addCallback(CallbackPtr callback, AddressFamily family) { + Lock lock(mutex_); + + bool ask(false); + + // Look at expiration time + if (expiry_ && time(NULL) >= expiry_) { + setState(EXPIRED); + } + + // We need to ask (again) + if (getState() == EXPIRED || getState() == NOT_ASKED) { + ask = true; + } + + // We do not have the answer right away, just queue the callback + bool execute(!ask && getState() != IN_PROGRESS && + callbacks_[family].empty()); + callbacks_[family].push_back(callback); + if (execute) { + // Try to process it right away, store if not possible to handle + process(family, NameserverPtr()); + return; + } + + if (ask) { + setState(IN_PROGRESS); + // Our callback might be directly called from resolve, unlock now + QuestionPtr question(new Question(Name(name_), class_code_, + RRType::NS())); + shared_ptr<ResolverCallback> resolver_callback( + new ResolverCallback(shared_from_this())); + resolver_->resolve(question, resolver_callback); + return; + } +} + +namespace { + +// This just moves items from one container to another +template<class Container> +void +move(Container& into, Container& from) { + into.insert(into.end(), from.begin(), from.end()); + from.clear(); +} + +// 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 +updateAddressSelector(std::vector<NameserverAddress>& addresses, + WeightedRandomIntegerGenerator& selector) +{ + vector<double> probabilities; + BOOST_FOREACH(NameserverAddress& address, addresses) { + uint32_t rtt = address.getAddressEntry().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); +} + +} + +/** + * \short Sets given boolean to false when destroyed. + * + * This is hack eliminating C++ missing finally. We need to make sure + * the value gets set to false when we leave the function, so we use + * a Guard object, that sets it when it gets out of scope. + */ +class ZoneEntry::ProcessGuard { + public: + ProcessGuard(bool& guarded) : + guarded_(guarded) + { } + ~ ProcessGuard() { + guarded_ = false; + } + private: + bool& guarded_; +}; + +/** + * \short Callback from NameserverEntry to us. + * + * We registre object of this class whenever some ZoneEntry has a need to be + * notified of a change (received data) inside its NameserverEntry. + * + * This is part of the ZoneEntry code (not visible from outside, accessing + * private functions). It is here just because C++ does not know propper lambda + * functions. + */ +class ZoneEntry::NameserverCallback : public NameserverEntry::Callback { + public: + /** + * \short Constructor. + * + * \param entry The ZoneEntry to be notified. + * \param family For which address family this change is, so we + * do not process all the nameserves and callbacks there. + */ + NameserverCallback(shared_ptr<ZoneEntry> entry, AddressFamily family) : + entry_(entry), + family_(family) + { } + /** + * \short Callback method. + * + * This is called by NameserverEntry when the change happens. + * We just call process to go trough relevant nameservers and call + * any callbacks we can. + */ + virtual void operator()(NameserverPtr ns) { + entry_->process(family_, ns); + } + private: + shared_ptr<ZoneEntry> entry_; + AddressFamily family_; +}; + +void +ZoneEntry::dispatchFailures(AddressFamily family) { + // We extract all the callbacks + vector<CallbackPtr> callbacks; + if (family == ADDR_REQ_MAX) { + move(callbacks_[ANY_OK], callbacks_[V4_ONLY]); + move(callbacks_[ANY_OK], callbacks_[V6_ONLY]); + family = ANY_OK; + } + callbacks.swap(callbacks_[family]); + BOOST_FOREACH(const CallbackPtr& callback, callbacks) { + callback->unreachable(); + } +} + +void +ZoneEntry::process(AddressFamily family, + const shared_ptr<NameserverEntry>& nameserver) +{ + Lock lock(mutex_); + switch (getState()) { + // These are not interesting, nothing to return now + case NOT_ASKED: + case IN_PROGRESS: + case EXPIRED: + break; + case UNREACHABLE: { + dispatchFailures(family); + // And we do nothing more now + break; + } + case READY: + if (family == ADDR_REQ_MAX) { + // Just process each one separately + // TODO Think this over, is it safe, to unlock in the middle? + process(ANY_OK, nameserver); + process(V4_ONLY, nameserver); + process(V6_ONLY, nameserver); + } else { + // Nothing to do anyway for this family, be dormant + if (callbacks_[family].empty()) { + return; + } + /* + * If we have multiple nameservers and more than 1 of them + * is in the cache, we want to choose from all their addresses. + * So we ensure this instance of process is the only one on + * the stack. If not, we terminate and let the outernmost + * one handle it when we return to it. + * + * If we didn't do it, one instance would call "resolve". If it + * was from cache, it would imediatelly recurse back to another + * process (trough the nameserver callback, etc), which would + * take that only one nameserver and trigger all callbacks. + * Only then would resolve terminate and we could ask for the + * second nameserver. This way, we first receive all the + * nameservers that are already in cache and trigger the + * callbacks only then. + * + * However, this does not wait for external fetches of + * nameserver addresses, as the callback is called after + * process terminates. Therefore this waits only for filling + * of the nameservers which we already have in cache. + */ + if (in_process_[family]) { + return; + } + // Mark we are on the stack + ProcessGuard guard(in_process_[family]); + in_process_[family] = true; + // Variables to store the data to + NameserverEntry::AddressVector addresses; + NameserverVector to_ask; + bool pending(false); + + // Pick info from the nameservers + BOOST_FOREACH(const NameserverPtr& ns, nameservers_) { + Fetchable::State ns_state(ns->getAddresses(addresses, + family, ns == nameserver)); + switch (ns_state) { + case IN_PROGRESS: + pending = true; + // Someone asked it, but not us, we don't have + // callback + if (nameservers_not_asked_.find(ns) != + nameservers_not_asked_.end()) + { + to_ask.push_back(ns); + } + break; + case NOT_ASKED: + case EXPIRED: + to_ask.push_back(ns); + break; + case UNREACHABLE: + case READY: + // Not interested, but avoiding warning + break; + } + } + + // We have someone to ask, so do it + if (!to_ask.empty()) { + // We ask everything that makes sense now + nameservers_not_asked_.clear(); + /* + * TODO: Possible place for an optimisation. We now ask + * everything we can. We should limit this to something like + * 2 concurrent NS fetches (and fetch cache first, then + * fetch the remote ones). But fetching everything right + * away is simpler. + */ + BOOST_FOREACH(const NameserverPtr& ns, to_ask) { + // Put all 3 callbacks there. If we put just the + // current family, it might not work due to missing + // callback for different one. + // If they recurse back to us (call directly), we kill + // it by the in_process_ + insertCallback(ns, ADDR_REQ_MAX); + } + // Retry with all the data that might have arrived + in_process_[family] = false; + // We do not provide the callback again + process(family, nameserver); + // And be done + return; + // We have some addresses to answer + } else if (!addresses.empty()) { + // Prepare the selector of addresses + // TODO: Think of a way how to keep it for a while + // (not update every time) + updateAddressSelector(addresses, address_selector); + + // Extract the callbacks + vector<CallbackPtr> to_execute; + // FIXME: Think of a solution where we do not lose + // any callbacks upon exception + to_execute.swap(callbacks_[family]); + + // Run the callbacks + BOOST_FOREACH(const CallbackPtr& callback, to_execute) { + callback->success(addresses[address_selector()]); + } + return; + } else if (!pending) { + dispatchFailures(family); + return; + } + } + return; + } +} + +void +ZoneEntry::insertCallback(NameserverPtr ns, AddressFamily family) { + if (family == ADDR_REQ_MAX) { + insertCallback(ns, ANY_OK); + insertCallback(ns, V4_ONLY); + insertCallback(ns, V6_ONLY); + } else { + shared_ptr<NameserverCallback> callback(new NameserverCallback( + shared_from_this(), family)); + ns->askIP(resolver_, callback, family); + } +} + +}; // namespace nsas +}; // namespace isc diff --git a/src/lib/nsas/zone_entry.h b/src/lib/nsas/zone_entry.h new file mode 100644 index 0000000000..82eadf6fbe --- /dev/null +++ b/src/lib/nsas/zone_entry.h @@ -0,0 +1,175 @@ +// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC") +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH +// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, +// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE +// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +// PERFORMANCE OF THIS SOFTWARE. + +// $Id$ + +#ifndef __ZONE_ENTRY_H +#define __ZONE_ENTRY_H + +#include <string> +#include <vector> +#include <set> +#include <boost/thread.hpp> +#include <boost/shared_ptr.hpp> +#include <boost/enable_shared_from_this.hpp> + +#include <dns/rrset.h> + +#include "hash_key.h" +#include "nsas_entry.h" +#include "asiolink.h" +#include "fetchable.h" +#include "resolver_interface.h" +#include "nsas_types.h" +#include "random_number_generator.h" + +namespace isc { +namespace nsas { + +class NameserverEntry; +class AddressRequestCallback; + +/// \brief Zone Entry +/// +/// The zone entry object describes a zone for which nameserver address +/// information is held. +/// +/// Although the interface is simple, the internal processing is fairly +/// complicated, in that the class takes account of triggering fetches for +/// addresses of nameservers when the address records expire. +/// +/// It uses shared_from_this in its methods. It must live inside a shared_ptr. + +class ZoneEntry : public NsasEntry<ZoneEntry>, public Fetchable { +public: + + /** + * \brief Constructor. + * + * It asks the resolver any needed questions to get the nameservers. + * + * \param resolver The resolver used to ask for IP addresses + * \param name Name of the zone + * \param class_code Class of this zone (zones of different classes have + * different objects. + * \todo Move to cc file, include the lookup (if NSAS uses resolver for + * everything) + */ + ZoneEntry(boost::shared_ptr<ResolverInterface> resolver, + const std::string& name, const isc::dns::RRClass& class_code, + boost::shared_ptr<HashTable<NameserverEntry> > nameserver_table, + boost::shared_ptr<LruList<NameserverEntry> > nameserver_lru); + + /// \return Name of the zone + std::string getName() const { + return name_; + } + + /// \return Class of zone + const isc::dns::RRClass& getClass() const { + return class_code_; + } + + /// \return Return Hash Key + virtual HashKey hashKey() const { + return HashKey(name_, class_code_); + } + + /** + * \short Put another callback inside. + * + * This callback is either executed right away, if it is possible, + * or queued for later. + * + * \param callback The callback itself. + * \param family Which address family is acceptable as an answer? + */ + void addCallback(boost::shared_ptr<AddressRequestCallback> + callback, AddressFamily family); + + /// \short Protected members, so they can be accessed by tests. + //@{ +protected: + // TODO Read-Write lock? + typedef boost::shared_ptr<NameserverEntry> NameserverPtr; + typedef std::vector<NameserverPtr> NameserverVector; + NameserverVector nameservers_; ///< Nameservers + // Which nameservers didn't have any of our callbacks yet + std::set<NameserverPtr> nameservers_not_asked_; + /* + * Callbacks. For each fimily type one vector, so we can process + * them separately. + */ + std::vector<boost::shared_ptr<AddressRequestCallback> > + callbacks_[ADDR_REQ_MAX]; + time_t expiry_; ///< Expiry time of this entry, 0 means not set + //}@ +private: + mutable boost::recursive_mutex mutex_; ///< Mutex protecting this zone entry + std::string name_; ///< Canonical zone name + isc::dns::RRClass class_code_; ///< Class code + /** + * \short Process all the callbacks that can be processed + * + * The purpose of this funtion is to ask all nameservers for their IP + * addresses and execute all callbacks that can be executed. It is + * called whenever new callback appears and there's a chance it could + * be answered or when new information is available (list of nameservers, + * nameserver is unreachable or has an address). + * \param family Which is the interesting address family where the change + * happened. ADDR_REQ_MAX means it could be any of them and it will + * trigger processing of all callbacks no matter what their family + * was. + * \param nameserver Pass a nameserver if the change was triggered by + * the nameserver (if it wasn't triggered by a nameserver, pass empty + * pointer). This one will be accepted even with 0 TTL, the information + * just arrived and we are allowed to use it just now. + * \todo With the recursive locks now, we might want to simplify executing + * callbacks (here and other functions as well); + */ + void process(AddressFamily family, + const boost::shared_ptr<NameserverEntry>& nameserver); + // Resolver we use + boost::shared_ptr<ResolverInterface> resolver_; + // We store the nameserver table and lru, so we can look up when there's + // update + boost::shared_ptr<HashTable<NameserverEntry> > nameserver_table_; + boost::shared_ptr<LruList<NameserverEntry> > nameserver_lru_; + // Resolver callback class, documentation with the class declaration + class ResolverCallback; + // It has direct access to us + friend class ResolverCallback; + // Guard class to eliminate missing finally + class ProcessGuard; + friend class ProcessGuard; + // Are we in the process method? + bool in_process_[ADDR_REQ_MAX]; + // Callback from nameserver entry (documented with the class) + class NameserverCallback; + // And it can get into our internals as well (call process) + friend class NameserverCallback; + // This dispatches callbacks of given family with failures + void dispatchFailures(AddressFamily family); + // Put a callback into the nameserver entry. Same ADDR_REQ_MAX means for + // all families + void insertCallback(NameserverPtr nameserver, AddressFamily family); + // A random generator for this zone entry + // TODO: A more global one? Per thread one? + WeightedRandomIntegerGenerator address_selector; +}; + +} // namespace nsas +} // namespace isc + +#endif // __ZONE_ENTRY_H |