Internal QUICHE change PiperOrigin-RevId: 278613873 Change-Id: I7362668613bfb081adefa1fcb185c0b0f3df74ac
diff --git a/quic/core/frames/quic_ack_frame.cc b/quic/core/frames/quic_ack_frame.cc index 389f1c0..72e806c 100644 --- a/quic/core/frames/quic_ack_frame.cc +++ b/quic/core/frames/quic_ack_frame.cc
@@ -15,13 +15,6 @@ const QuicPacketCount kMaxPrintRange = 128; -uint64_t PacketNumberIntervalLength( - const QuicInterval<QuicPacketNumber>& interval) { - if (interval.Empty()) { - return 0u; - } - return interval.max() - interval.min(); -} } // namespace bool IsAwaitingPacket(const QuicAckFrame& ack_frame, @@ -86,77 +79,8 @@ if (!packet_number.IsInitialized()) { return; } - // Check if the deque is empty - if (packet_number_deque_.empty()) { - packet_number_deque_.push_front( - QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); - return; - } - QuicInterval<QuicPacketNumber> back = packet_number_deque_.back(); - - // Check for the typical case, - // when the next packet in order is acked - if (back.max() == packet_number) { - packet_number_deque_.back().SetMax(packet_number + 1); - return; - } - // Check if the next packet in order is skipped - if (back.max() < packet_number) { - packet_number_deque_.push_back( - QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); - return; - } - - QuicInterval<QuicPacketNumber> front = packet_number_deque_.front(); - // Check if the packet can be popped on the front - if (front.min() > packet_number + 1) { - packet_number_deque_.push_front( - QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); - return; - } - if (front.min() == packet_number + 1) { - packet_number_deque_.front().SetMin(packet_number); - return; - } - - int i = packet_number_deque_.size() - 1; - // Iterating through the queue backwards - // to find a proper place for the packet - while (i >= 0) { - QuicInterval<QuicPacketNumber> packet_interval = packet_number_deque_[i]; - DCHECK(packet_interval.min() < packet_interval.max()); - // Check if the packet is contained in an interval already - if (packet_interval.Contains(packet_number)) { - return; - } - - // Check if the packet can extend an interval. - if (packet_interval.max() == packet_number) { - packet_number_deque_[i].SetMax(packet_number + 1); - return; - } - // Check if the packet can extend an interval - // and merge two intervals if needed. - // There is no need to merge an interval in the previous - // if statement, as all merges will happen here. - if (packet_interval.min() == packet_number + 1) { - packet_number_deque_[i].SetMin(packet_number); - if (i > 0 && packet_number == packet_number_deque_[i - 1].max()) { - packet_number_deque_[i - 1].SetMax(packet_interval.max()); - packet_number_deque_.erase(packet_number_deque_.begin() + i); - } - return; - } - - // Check if we need to make a new interval for the packet - if (packet_interval.max() < packet_number + 1) { - packet_number_deque_.insert( - packet_number_deque_.begin() + i + 1, - QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); - return; - } - i--; - } + packet_number_intervals_.AddOptimizedForAppend(packet_number, + packet_number + 1); } void PacketNumberQueue::AddRange(QuicPacketNumber lower, @@ -164,136 +88,93 @@ if (!lower.IsInitialized() || !higher.IsInitialized() || lower >= higher) { return; } - if (packet_number_deque_.empty()) { - packet_number_deque_.push_front( - QuicInterval<QuicPacketNumber>(lower, higher)); - return; - } - QuicInterval<QuicPacketNumber> back = packet_number_deque_.back(); - if (back.max() == lower) { - // Check for the typical case, - // when the next packet in order is acked - packet_number_deque_.back().SetMax(higher); - return; - } - if (back.max() < lower) { - // Check if the next packet in order is skipped - packet_number_deque_.push_back( - QuicInterval<QuicPacketNumber>(lower, higher)); - return; - } - QuicInterval<QuicPacketNumber> front = packet_number_deque_.front(); - // Check if the packets are being added in reverse order - if (front.min() == higher) { - packet_number_deque_.front().SetMin(lower); - } else if (front.min() > higher) { - packet_number_deque_.push_front( - QuicInterval<QuicPacketNumber>(lower, higher)); + const auto new_interval = QuicInterval<QuicPacketNumber>(lower, higher); - } else { + if (!packet_number_intervals_.Empty() && + packet_number_intervals_.SpanningInterval().Intersects(new_interval)) { + // TODO(wub): Remove this QUIC_BUG, or the AddRange method entirely. // Ranges must be above or below all existing ranges. QUIC_BUG << "AddRange only supports adding packets above or below the " << "current min:" << Min() << " and max:" << Max() << ", but adding [" << lower << "," << higher << ")"; + return; } + + packet_number_intervals_.AddOptimizedForAppend(new_interval); } bool PacketNumberQueue::RemoveUpTo(QuicPacketNumber higher) { if (!higher.IsInitialized() || Empty()) { return false; } - const QuicPacketNumber old_min = Min(); - while (!packet_number_deque_.empty()) { - QuicInterval<QuicPacketNumber> front = packet_number_deque_.front(); - if (front.max() < higher) { - packet_number_deque_.pop_front(); - } else if (front.min() < higher && front.max() >= higher) { - packet_number_deque_.front().SetMin(higher); - if (front.max() == higher) { - packet_number_deque_.pop_front(); - } - break; - } else { - break; - } - } - - return Empty() || old_min != Min(); + return packet_number_intervals_.TrimLessThan(higher); } void PacketNumberQueue::RemoveSmallestInterval() { - QUIC_BUG_IF(packet_number_deque_.size() < 2) + // TODO(wub): Move this QUIC_BUG to upper level. + QUIC_BUG_IF(packet_number_intervals_.Size() < 2) << (Empty() ? "No intervals to remove." : "Can't remove the last interval."); - packet_number_deque_.pop_front(); + packet_number_intervals_.PopFront(); } void PacketNumberQueue::Clear() { - packet_number_deque_.clear(); + packet_number_intervals_.Clear(); } bool PacketNumberQueue::Contains(QuicPacketNumber packet_number) const { - if (!packet_number.IsInitialized() || packet_number_deque_.empty()) { + if (!packet_number.IsInitialized()) { return false; } - if (packet_number_deque_.front().min() > packet_number || - packet_number_deque_.back().max() <= packet_number) { - return false; - } - for (QuicInterval<QuicPacketNumber> interval : packet_number_deque_) { - if (interval.Contains(packet_number)) { - return true; - } - } - return false; + return packet_number_intervals_.Contains(packet_number); } bool PacketNumberQueue::Empty() const { - return packet_number_deque_.empty(); + return packet_number_intervals_.Empty(); } QuicPacketNumber PacketNumberQueue::Min() const { DCHECK(!Empty()); - return packet_number_deque_.front().min(); + return packet_number_intervals_.begin()->min(); } QuicPacketNumber PacketNumberQueue::Max() const { DCHECK(!Empty()); - return packet_number_deque_.back().max() - 1; + return packet_number_intervals_.rbegin()->max() - 1; } QuicPacketCount PacketNumberQueue::NumPacketsSlow() const { QuicPacketCount n_packets = 0; - for (QuicInterval<QuicPacketNumber> interval : packet_number_deque_) { - n_packets += PacketNumberIntervalLength(interval); + for (const auto& interval : packet_number_intervals_) { + n_packets += interval.Length(); } return n_packets; } size_t PacketNumberQueue::NumIntervals() const { - return packet_number_deque_.size(); + return packet_number_intervals_.Size(); } PacketNumberQueue::const_iterator PacketNumberQueue::begin() const { - return packet_number_deque_.begin(); + return packet_number_intervals_.begin(); } PacketNumberQueue::const_iterator PacketNumberQueue::end() const { - return packet_number_deque_.end(); + return packet_number_intervals_.end(); } PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rbegin() const { - return packet_number_deque_.rbegin(); + return packet_number_intervals_.rbegin(); } PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rend() const { - return packet_number_deque_.rend(); + return packet_number_intervals_.rend(); } QuicPacketCount PacketNumberQueue::LastIntervalLength() const { DCHECK(!Empty()); - return PacketNumberIntervalLength(packet_number_deque_.back()); + return packet_number_intervals_.rbegin()->Length(); } // Largest min...max range for packet numbers where we print the numbers
diff --git a/quic/core/frames/quic_ack_frame.h b/quic/core/frames/quic_ack_frame.h index 771d93e..18675a8 100644 --- a/quic/core/frames/quic_ack_frame.h +++ b/quic/core/frames/quic_ack_frame.h
@@ -8,6 +8,7 @@ #include <ostream> #include "net/third_party/quiche/src/quic/core/quic_interval.h" +#include "net/third_party/quiche/src/quic/core/quic_interval_set.h" #include "net/third_party/quiche/src/quic/core/quic_types.h" #include "net/third_party/quiche/src/quic/platform/api/quic_containers.h" #include "net/third_party/quiche/src/quic/platform/api/quic_export.h" @@ -28,9 +29,8 @@ PacketNumberQueue& operator=(const PacketNumberQueue& other); PacketNumberQueue& operator=(PacketNumberQueue&& other); - typedef QuicDeque<QuicInterval<QuicPacketNumber>>::const_iterator - const_iterator; - typedef QuicDeque<QuicInterval<QuicPacketNumber>>::const_reverse_iterator + typedef QuicIntervalSet<QuicPacketNumber>::const_iterator const_iterator; + typedef QuicIntervalSet<QuicPacketNumber>::const_reverse_iterator const_reverse_iterator; // Adds |packet_number| to the set of packets in the queue. @@ -38,6 +38,7 @@ // Adds packets between [lower, higher) to the set of packets in the queue. It // is undefined behavior to call this with |higher| < |lower|. + // NOTE(wub): Only used in tests as of Nov 2019. void AddRange(QuicPacketNumber lower, QuicPacketNumber higher); // Removes packets with values less than |higher| from the set of packets in @@ -86,7 +87,7 @@ const PacketNumberQueue& q); private: - QuicDeque<QuicInterval<QuicPacketNumber>> packet_number_deque_; + QuicIntervalSet<QuicPacketNumber> packet_number_intervals_; }; struct QUIC_EXPORT_PRIVATE QuicAckFrame {
diff --git a/quic/core/quic_framer.cc b/quic/core/quic_framer.cc index 761645e..353d4e6 100644 --- a/quic/core/quic_framer.cc +++ b/quic/core/quic_framer.cc
@@ -148,6 +148,7 @@ return (Delta(target, a) < Delta(target, b)) ? a : b; } +// TODO(wub): Remove this function & replace the callsites to interval.Length(). uint64_t PacketNumberIntervalLength( const QuicInterval<QuicPacketNumber>& interval) { if (interval.Empty()) {
diff --git a/quic/core/quic_interval_set.h b/quic/core/quic_interval_set.h index 0465a01..28153c1 100644 --- a/quic/core/quic_interval_set.h +++ b/quic/core/quic_interval_set.h
@@ -73,6 +73,7 @@ struct QUIC_NO_EXPORT IntervalLess { bool operator()(const value_type& a, const value_type& b) const; }; + // TODO(wub): Switch to absl::btree_set when it is available in Chromium. typedef std::set<value_type, IntervalLess> Set; public: @@ -152,6 +153,49 @@ // TODO(wub): Similar to AddOptimizedForAppend, we can also have a // AddOptimizedForPrepend if there is a use case. + // Remove the first interval. + // REQUIRES: !Empty() + void PopFront() { + DCHECK(!Empty()); + intervals_.erase(intervals_.begin()); + } + + // Trim all values that is smaller than |value|. Which means + // a) If all values in an interval is smaller than |value|, the entire + // interval is removed. + // b) If some but not all values in an interval is smaller than |value|, the + // min of that interval is raised to |value|. + // Returns true if some intervals are trimmed. + bool TrimLessThan(const T& value) { + // Number of intervals that are fully or partially trimmed. + size_t num_intervals_trimmed = 0; + + while (!intervals_.empty()) { + const_iterator first_interval = intervals_.begin(); + if (first_interval->min() >= value) { + break; + } + + ++num_intervals_trimmed; + + if (first_interval->max() <= value) { + // a) Trim the entire interval. + intervals_.erase(first_interval); + continue; + } + + // b) Trim a prefix of the interval. + // + // Set does not allow in-place updates due to the potential of violating + // its ordering requirements. But increasing the min of the first interval + // will not break the ordering, hence the const_cast. + const_cast<value_type*>(&(*first_interval))->SetMin(value); + break; + } + + return num_intervals_trimmed != 0; + } + // Returns true if this QuicIntervalSet is empty. bool Empty() const { return intervals_.empty(); }
diff --git a/quic/core/quic_interval_set_test.cc b/quic/core/quic_interval_set_test.cc index 3fb483a..efa8fe7 100644 --- a/quic/core/quic_interval_set_test.cc +++ b/quic/core/quic_interval_set_test.cc
@@ -191,6 +191,47 @@ EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 350)); } +TEST_F(QuicIntervalSetTest, PopFront) { + QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}}; + EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800)); + + iset.PopFront(); + EXPECT_TRUE(Check(iset, 2, 400, 500, 700, 800)); + + iset.PopFront(); + EXPECT_TRUE(Check(iset, 1, 700, 800)); + + iset.PopFront(); + EXPECT_TRUE(iset.Empty()); +} + +TEST_F(QuicIntervalSetTest, TrimLessThan) { + QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}}; + EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800)); + + EXPECT_FALSE(iset.TrimLessThan(99)); + EXPECT_FALSE(iset.TrimLessThan(100)); + EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800)); + + EXPECT_TRUE(iset.TrimLessThan(101)); + EXPECT_TRUE(Check(iset, 3, 101, 200, 400, 500, 700, 800)); + + EXPECT_TRUE(iset.TrimLessThan(199)); + EXPECT_TRUE(Check(iset, 3, 199, 200, 400, 500, 700, 800)); + + EXPECT_TRUE(iset.TrimLessThan(450)); + EXPECT_TRUE(Check(iset, 2, 450, 500, 700, 800)); + + EXPECT_TRUE(iset.TrimLessThan(500)); + EXPECT_TRUE(Check(iset, 1, 700, 800)); + + EXPECT_TRUE(iset.TrimLessThan(801)); + EXPECT_TRUE(iset.Empty()); + + EXPECT_FALSE(iset.TrimLessThan(900)); + EXPECT_TRUE(iset.Empty()); +} + TEST_F(QuicIntervalSetTest, QuicIntervalSetBasic) { // Test Add, Get, Contains and Find QuicIntervalSet<int> iset;