2008-03-11 Tatsuhiro Tsujikawa <tujikawa at rednoah dot com>

	Fixed high memory footprint when DHT is enabled.
	This is not a memory leak, but DHTReplaceNodeTask is more frequently
	queued than it is processed and the queue is getting longer. As a
	consequence, momory usage is increased.
	As for a fix, instead of issuing DHTReplaceNodeTask, I've implemented
	replacement cache in DHTBucket which is described in Kademlia paper.
	* src/DHTRoutingTable.cc (addNode): Removed the issuing of
	DHTReplaceNodeTask.
	* src/DHTBucket.{h, cc}
	(cacheNode): New function.
	(getCachedNodes): New function.
	(dropNode): Push back cached node to _nodes.
	* test/DHTBucketTest.cc
	(testCacheNode): New test
	(testDropNode): New test

1 files changed, 67 insertions, 0 deletions

diff --git a/test/DHTBucketTest.cc b/test/DHTBucketTest.cc
index c6c3b8f8..f97eb17a 100644
--- a/test/DHTBucketTest.cc
+++ b/test/DHTBucketTest.cc
@@ -17,6 +17,8 @@ class DHTBucketTest:public CppUnit::TestFixture {
   CPPUNIT_TEST(testMoveToHead);
   CPPUNIT_TEST(testMoveToTail);
   CPPUNIT_TEST(testGetGoodNodes);
+  CPPUNIT_TEST(testCacheNode);
+  CPPUNIT_TEST(testDropNode);
   CPPUNIT_TEST_SUITE_END();
 public:
   void setUp() {}
@@ -31,6 +33,8 @@ public:
   void testMoveToHead();
   void testMoveToTail();
   void testGetGoodNodes();
+  void testCacheNode();
+  void testDropNode();
 };
 
 
@@ -337,4 +341,67 @@ void DHTBucketTest::testGetGoodNodes()
   CPPUNIT_ASSERT_EQUAL((uint16_t)6888, goodNodes[5]->getPort());
 }
 
+void DHTBucketTest::testCacheNode()
+{
+  unsigned char localNodeID[DHT_ID_LENGTH];
+  memset(localNodeID, 0, DHT_ID_LENGTH);
+  SharedHandle<DHTNode> localNode = new DHTNode(localNodeID);
+  DHTBucket bucket(localNode);
+
+  SharedHandle<DHTNode> n1 = new DHTNode();
+  SharedHandle<DHTNode> n2 = new DHTNode();
+  SharedHandle<DHTNode> n3 = new DHTNode();
+
+  bucket.cacheNode(n1);
+  bucket.cacheNode(n2);
+  CPPUNIT_ASSERT_EQUAL((size_t)2, bucket.getCachedNodes().size());
+  CPPUNIT_ASSERT(n2 == bucket.getCachedNodes()[0]);
+
+  bucket.cacheNode(n3);
+  CPPUNIT_ASSERT_EQUAL((size_t)2, bucket.getCachedNodes().size());
+  CPPUNIT_ASSERT(n3 == bucket.getCachedNodes()[0]);
+  CPPUNIT_ASSERT(n2 == bucket.getCachedNodes()[1]);
+}
+
+void DHTBucketTest::testDropNode()
+{
+  unsigned char localNodeID[DHT_ID_LENGTH];
+  memset(localNodeID, 0, DHT_ID_LENGTH);
+  SharedHandle<DHTNode> localNode = new DHTNode(localNodeID);
+  DHTBucket bucket(localNode);
+
+  unsigned char id[DHT_ID_LENGTH];
+  SharedHandle<DHTNode> nodes[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
+  for(size_t i = 0; i < DHTBucket::K; ++i) {
+    createID(id, 0xf0, i);
+    nodes[i] = new DHTNode(id);
+    nodes[i]->setPort(6881+i);
+    CPPUNIT_ASSERT(bucket.addNode(nodes[i]));
+  }
+
+  SharedHandle<DHTNode> cachedNode1 = new DHTNode();
+  SharedHandle<DHTNode> cachedNode2 = new DHTNode();
+
+  bucket.dropNode(nodes[3]);
+  // nothing happens because the replacement cache is empty.
+  {
+    std::deque<SharedHandle<DHTNode> > tnodes = bucket.getNodes();
+    CPPUNIT_ASSERT_EQUAL((size_t)8, tnodes.size());
+    CPPUNIT_ASSERT(nodes[3] == tnodes[3]);
+  }
+
+  bucket.cacheNode(cachedNode1);
+  bucket.cacheNode(cachedNode2);
+
+  bucket.dropNode(nodes[3]);
+  {
+    std::deque<SharedHandle<DHTNode> > tnodes = bucket.getNodes();
+    CPPUNIT_ASSERT_EQUAL((size_t)8, tnodes.size());
+    CPPUNIT_ASSERT(tnodes.end() == std::find(tnodes.begin(), tnodes.end(), nodes[3]));
+    CPPUNIT_ASSERT(cachedNode2 == tnodes[7]);
+  }
+  CPPUNIT_ASSERT_EQUAL((size_t)1, bucket.getCachedNodes().size());
+  CPPUNIT_ASSERT(cachedNode1 == bucket.getCachedNodes()[0]);
+}
+
 } // namespace aria2