From 669ff083269756bda4d5e48cc35a241a1f82a6a1 Mon Sep 17 00:00:00 2001 From: Marcin Siodelski Date: Wed, 4 May 2016 18:15:48 +0200 Subject: [PATCH] [4493] Optimize lookup of timed out packets. --- src/bin/perfdhcp/stats_mgr.h | 53 +++++++++++++------- src/bin/perfdhcp/tests/stats_mgr_unittest.cc | 17 +++---- 2 files changed, 44 insertions(+), 26 deletions(-) diff --git a/src/bin/perfdhcp/stats_mgr.h b/src/bin/perfdhcp/stats_mgr.h index ca2d62353b..5e3181d1cb 100644 --- a/src/bin/perfdhcp/stats_mgr.h +++ b/src/bin/perfdhcp/stats_mgr.h @@ -14,7 +14,7 @@ #include #include #include -#include +#include #include #include #include @@ -202,7 +202,7 @@ public: /// } /// \endcode /// - /// Example 3: Access elements through hashed index + /// Example 3: Access elements through ordered index by hash /// \code /// // Get the instance of the second search index. /// PktListTransidHashIndex& idx = sent_packets_.template get<1>(); @@ -226,7 +226,10 @@ public: // in the same way as std::list. boost::multi_index::sequenced<>, // The other index keeps products of transaction id. - boost::multi_index::hashed_non_unique< + // Elements with the same hash value are grouped together + // into buckets and transactions are ordered from the + // oldest to latest within a bucket. + boost::multi_index::ordered_non_unique< // Specify hash function to get the product of // transaction id. This product is obtained by calling // hashTransid() function. @@ -442,6 +445,7 @@ public: // bucket size the better. If bucket sizes appear to big we // might want to increase number of buckets. unordered_lookup_size_sum_ += std::distance(p.first, p.second); + bool non_expired_found = false; // Removal can be done only after the loop PktListRemovalQueue to_remove; for (PktListTransidHashIterator it = p.first; it != p.second; @@ -453,26 +457,41 @@ public: // Even though the packet has been found, we continue // iterating over the bucket to remove all those packets // that are timed out. - if ((*it)->getTransid() == rcvd_packet->getTransid()) { + if (!packet_found && ((*it)->getTransid() == rcvd_packet->getTransid())) { packet_found = true; next_sent_ = sent_packets_.template project<0>(it); } - // Check if the packet should be removed due to timeout. - // This includes the packet matching the received one. - ptime now = microsec_clock::universal_time(); - ptime packet_time = (*it)->getTimestamp(); - time_period packet_period(packet_time, now); - if (!packet_period.is_null()) { - double period_fractional = - packet_period.length().total_seconds() + - (static_cast(packet_period.length().fractional_seconds()) - / packet_period.length().ticks_per_second()); - if (drop_time_ > 0 && (period_fractional > drop_time_)) { - // Push the iterator on the removal queue. - to_remove.push(it); + if (!non_expired_found) { + // Check if the packet should be removed due to timeout. + // This includes the packet matching the received one. + ptime now = microsec_clock::universal_time(); + ptime packet_time = (*it)->getTimestamp(); + time_period packet_period(packet_time, now); + if (!packet_period.is_null()) { + double period_fractional = + packet_period.length().total_seconds() + + (static_cast(packet_period.length().fractional_seconds()) + / packet_period.length().ticks_per_second()); + if (drop_time_ > 0 && (period_fractional > drop_time_)) { + // Push the iterator on the removal queue. + to_remove.push(it); + + } else { + // We found first non-expired transaction. All other + // transactions within this bucket are considered + // non-expired because packets are held in the + // order of addition within the bucket. + non_expired_found = true; + } } } + + // If we found the packet and all expired transactions, + // there is nothing more to do. + if (non_expired_found && packet_found) { + break; + } } // Deal with the removal queue. diff --git a/src/bin/perfdhcp/tests/stats_mgr_unittest.cc b/src/bin/perfdhcp/tests/stats_mgr_unittest.cc index a65b14da5f..2c40b2018f 100644 --- a/src/bin/perfdhcp/tests/stats_mgr_unittest.cc +++ b/src/bin/perfdhcp/tests/stats_mgr_unittest.cc @@ -202,11 +202,10 @@ public: for (unsigned int i = 0; i < TEST_COLLECTED_PKT_NUM; ++i) { Pkt4ModifiablePtr sent_packet(createPacket4(DHCPDISCOVER, transid[i])); - // For packets with even index of the transaction id we set - // the packet timestamp to 10s in the past. When DHCPOFFER - // is processed, the packets with timestamps older than - // 2s should be collected. - if (i % 2 == 0) { + // For packets with low indexes we set the timestamps to + // 10s in the past. When DHCPOFFER is processed, the + // packets with timestamps older than 2s should be collected. + if (i < TEST_COLLECTED_PKT_NUM / 2) { sent_packet->modifyTimestamp(-10); } ASSERT_NO_THROW( @@ -226,8 +225,8 @@ public: // packets will be collected. Otherwise, for any unordered lookup // all packets from a bucket should be collected. if (stats_mgr->getUnorderedLookups(StatsMgr4::XCHG_DO) > 0) { - // All packets in the bucket having even transaction id - // indexes should be removed. + // All packets in the bucket having transaction id + // index below TEST_COLLECTED_PKT_NUM / 2 should be removed. EXPECT_EQ(TEST_COLLECTED_PKT_NUM / 2, stats_mgr->getCollectedNum(StatsMgr4::XCHG_DO)); } @@ -255,7 +254,7 @@ public: // that one of them we couldn't match (orphan packet), because // the matched packet had to be collected because of the transaction // timeout. Therefore, we have to count both received packets and - // orhpans. + // orphans. EXPECT_EQ(TEST_COLLECTED_PKT_NUM + 1, stats_mgr->getRcvdPacketsNum(StatsMgr4::XCHG_DO) + stats_mgr->getOrphans(StatsMgr4::XCHG_DO)); @@ -448,7 +447,7 @@ TEST_F(StatsMgrTest, SendReceiveUnordered) { EXPECT_EQ(9, stats_mgr->getUnorderedLookups(StatsMgr4::XCHG_DO)); } -TEST_F(StatsMgrTest, SendReceiveCollectedHighTransid) { +TEST_F(StatsMgrTest, SendReceiveCollected) { // Check that the packet collection mechanism works fine // for any packet returned by the server. for (unsigned int i = 0; i < TEST_COLLECTED_PKT_NUM; ++i) { -- 2.47.2