BIND 10 trac2750, updated. c0e91c529e7e110f68c30c127a8370643a1a9b78 [2750] Add comprehensive test for DomainTree validity with insert() and remove()
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Sep 3 04:34:55 UTC 2013
The branch, trac2750 has been updated
via c0e91c529e7e110f68c30c127a8370643a1a9b78 (commit)
via b30ae178084dbfda0da6ccfee9f8d1e27c926b0d (commit)
via e2cb0a39c9819482df8e7cd32ba37ed405d715fd (commit)
from 63e54b17e5b43ee480cb83a4fa0fa6ba08e2ccfa (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit c0e91c529e7e110f68c30c127a8370643a1a9b78
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Sep 3 10:04:36 2013 +0530
[2750] Add comprehensive test for DomainTree validity with insert() and remove()
commit b30ae178084dbfda0da6ccfee9f8d1e27c926b0d
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Sep 3 10:03:33 2013 +0530
[2750] Add a comment describing the test
commit e2cb0a39c9819482df8e7cd32ba37ed405d715fd
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Sep 3 10:03:15 2013 +0530
[2750] Move the RNG to a class variable (so the same RNG can be reused)
Otherwise, reseeding with time(NULL) will return the same sequence in
other tests if they start within the same second.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 6 +
.../datasrc/tests/memory/domaintree_unittest.cc | 155 +++++++++++++++++++-
2 files changed, 158 insertions(+), 3 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 776603a..3f23629 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -2433,6 +2433,12 @@ DomainTree<T>::tryNodeFusion(util::MemorySegment& mem_sgmt,
break;
}
+ // If upper node is the root node (.), don't attempt node fusion
+ // with it. The root node must always exist.
+ if (upper_node == root_.get()) {
+ break;
+ }
+
// Create a new label sequence with (subtree_root+upper_node)
// labels.
uint8_t buf[isc::dns::LabelSequence::MAX_SERIALIZED_LENGTH];
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index 6058e44..574577b 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -31,6 +31,10 @@
#include <boost/format.hpp>
+#include <stdlib.h>
+
+#include <set>
+#include <algorithm>
#include <fstream>
using namespace std;
@@ -38,6 +42,7 @@ using namespace isc;
using namespace isc::dns;
using isc::UnitTestUtil;
using namespace isc::datasrc::memory;
+using isc::util::random::UniformRandomIntegerGenerator;
// XXX: some compilers cannot find class static constants used in
// EXPECT_xxx macros, for which we need an explicit empty definition.
@@ -141,7 +146,8 @@ protected:
TestDomainTree::create(mem_sgmt_, true)),
dtree(*dtree_holder_.get()),
dtree_expose_empty_node(*dtree_expose_empty_node_holder_.get()),
- cdtnode(NULL)
+ cdtnode(NULL),
+ name_gen_('a', 'z')
{
for (int i = 0; i < name_count; ++i) {
dtree.insert(mem_sgmt_, Name(domain_names[i]), &dtnode);
@@ -154,6 +160,8 @@ protected:
EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(
new int(node_distances[i])));
}
+
+ srandom(time(NULL));
}
util::MemorySegmentLocal mem_sgmt_;
@@ -163,6 +171,7 @@ protected:
TestDomainTree& dtree_expose_empty_node;
TestDomainTreeNode* dtnode;
const TestDomainTreeNode* cdtnode;
+ UniformRandomIntegerGenerator name_gen_;
uint8_t buf[LabelSequence::MAX_SERIALIZED_LENGTH];
};
@@ -201,7 +210,6 @@ TEST_F(DomainTreeTest, checkDistanceRandom) {
TreeHolder mytree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
TestDomainTree& mytree = *mytree_holder.get();
- isc::util::random::UniformRandomIntegerGenerator gen('a', 'z');
const int log_num_nodes = 20;
// Make a large million+ node top-level domain tree, i.e., the
@@ -216,7 +224,7 @@ TEST_F(DomainTreeTest, checkDistanceRandom) {
string namestr;
while (true) {
for (int j = 0; j < 32; j++) {
- namestr += gen();
+ namestr += name_gen_();
}
namestr += '.';
@@ -380,6 +388,11 @@ TEST_F(DomainTreeTest, insertNames) {
}
TEST_F(DomainTreeTest, remove) {
+ // This testcase checks that after node removal, the binary-search
+ // tree is valid and all nodes that are supposed to exist are
+ // present in the correct order. It mainly tests DomainTree as a
+ // BST, and not particularly as a red-black tree.
+
// Delete single nodes and check if the rest of the nodes exist
for (int j = 0; j < ordered_names_count; ++j) {
TreeHolder holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_, true));
@@ -448,6 +461,142 @@ TEST_F(DomainTreeTest, remove) {
}
}
+void
+insertNodes(util::MemorySegment& mem_sgmt, TestDomainTree& tree,
+ std::set<std::string>& names, size_t num_nodes,
+ UniformRandomIntegerGenerator& name_gen)
+{
+ for (size_t i = 0; i < num_nodes; ++i) {
+ std::string namestr;
+ while (true) {
+ for (int j = 0; j < 32; j++) {
+ namestr += name_gen();
+ }
+ namestr += '.';
+
+ TestDomainTreeNode* cnode;
+ if (tree.insert(mem_sgmt, Name(namestr), &cnode) ==
+ TestDomainTree::SUCCESS) {
+ names.insert(namestr);
+ break;
+ }
+
+ namestr.clear();
+ }
+ }
+}
+
+void
+removeNodes(util::MemorySegment& mem_sgmt, TestDomainTree& tree,
+ std::set<std::string>& names, size_t num_nodes)
+{
+ size_t set_size = names.size();
+
+ for (size_t i = 0; i < num_nodes; ++i) {
+ // Here, UniformRandomIntegerGenerator is not a great RNG as
+ // it'll likely get seeded with the same seed throughout this
+ // testcase, and the size of the names set keeps changing.
+
+ std::set<std::string>::iterator it(names.begin());
+ // This is rather inefficient, but it's a test...
+ std::advance(it, random() % set_size);
+ std::string nstr(*it);
+
+ TestDomainTreeNode* node;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(nstr), &node));
+
+ tree.remove(mem_sgmt, node, deleteData);
+
+ names.erase(*it);
+ --set_size;
+ }
+}
+
+void
+checkTree(const TestDomainTree& tree,
+ const std::set<std::string>& names)
+{
+ // The distance from each node to its sub-tree root must be less
+ // than 2 * log_2(256).
+ EXPECT_GE(2 * 8, tree.getHeight());
+
+ // Also check RB tree properties
+ EXPECT_TRUE(tree.checkProperties());
+
+ // Now, walk through nodes in order.
+ TestDomainTreeNodeChain node_path;
+ const TestDomainTreeNode* cnode;
+
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name("."), &cnode, node_path));
+
+ // Skip to the next node after "."
+ cnode = tree.nextNode(node_path);
+ if (!cnode) {
+ // Empty tree.
+ return;
+ }
+
+ for (std::set<std::string>::const_iterator it = names.begin();
+ it != names.end(); ++it)
+ {
+ const Name n1(*it);
+ const Name n2(cnode->getName());
+
+ const NameComparisonResult result = n1.compare(n2);
+ EXPECT_EQ(NameComparisonResult::EQUAL, result.getRelation());
+
+ cnode = tree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), cnode);
+}
+
+TEST_F(DomainTreeTest, insertAndRemove) {
+ // What is the best way to test our red-black tree code? It is not a
+ // good method to test every case handled in the actual code itself
+ // (such as in insertRebalance() and removeRebalance()). This is
+ // because our approach itself may be incorrect.
+ //
+ // We test our code at the interface level here by exercising the
+ // tree randomly multiple times, checking that red-black tree
+ // properties are valid, and all the nodes that are supposed to be
+ // in the tree exist and are in order.
+
+ // NOTE: These tests are run within a single tree in the
+ // forest. Fusion, etc. are tested elsewhere. The number of nodes in
+ // the tree doesn't grow over 256.
+
+ TreeHolder holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_, true));
+ TestDomainTree& tree(*holder.get());
+ std::set<std::string> names;
+
+ size_t node_count = 0;
+
+ // Repeat the insert/remove test some 4096 times
+ for (int i = 0; i < 4096; ++i) {
+ UniformRandomIntegerGenerator gen(1, 256 - node_count);
+ size_t num_nodes = gen();
+ node_count += num_nodes;
+
+ insertNodes(mem_sgmt_, tree, names, num_nodes, name_gen_);
+ checkTree(tree, names);
+
+ UniformRandomIntegerGenerator gen2(1, node_count);
+ num_nodes = gen2();
+ node_count -= num_nodes;
+
+ removeNodes(mem_sgmt_, tree, names, num_nodes);
+ checkTree(tree, names);
+ }
+
+ // Remove the rest of the nodes.
+ removeNodes(mem_sgmt_, tree, names, node_count);
+ checkTree(tree, names);
+}
+
TEST_F(DomainTreeTest, nodeFusion) {
// Test that node fusion occurs when conditions permit.
More information about the bind10-changes
mailing list