Fix the logic for computing the number of truncated QUIC ACK frames sent.

net/quic/quic_connection_logger.cc

 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/quic/quic_connection_logger.h"
 
 #include <algorithm>
 #include <string>
 
 #include "base/bind.h"
@@ skipping 349 matching lines @@
 
 void QuicConnectionLogger::OnFrameAddedToPacket(const QuicFrame& frame) {
   switch (frame.type) {
     case PADDING_FRAME:
       break;
     case STREAM_FRAME:
       net_log_.AddEvent(
           NetLog::TYPE_QUIC_SESSION_STREAM_FRAME_SENT,
           base::Bind(&NetLogQuicStreamFrameCallback, frame.stream_frame));
       break;
-    case ACK_FRAME:
+    case ACK_FRAME: {
       net_log_.AddEvent(
           NetLog::TYPE_QUIC_SESSION_ACK_FRAME_SENT,
           base::Bind(&NetLogQuicAckFrameCallback, frame.ack_frame));
-      if (frame.ack_frame->is_truncated)
+      size_t num_ranges = 0;
+      QuicPacketSequenceNumber last_missing = 0;
+      for (SequenceNumberSet::const_iterator it =
+               frame.ack_frame->missing_packets.begin();
+           it != frame.ack_frame->missing_packets.end();
+           ++it) {
+        if (*it != last_missing + 1) {

[eroman, 2014/09/09 00:08:01]

possibility of integer overflow?

[Ryan Hamilton, 2014/09/09 19:00:36]

I guess it's *possible*, but since I'm using != and unsigned overflow is well
defined, I'm not sure how that would be problematic?  (sequence numbers start
small and grow over time, so in the common case, it'll never get near the uint64
max, but of course if we get garbage from the peer, it's possible)

+          ++num_ranges;
+        }
+        last_missing = *it;
+      }
+      if (num_ranges >= std::numeric_limits<uint8>::max())

[eroman, 2014/09/09 00:08:01]

is it necessary to iterate everything if this is the only test being performed?

[Ryan Hamilton, 2014/09/09 19:00:36]

as far as I know, but I'd be happy to come up with a better approach if you can
think of one?

[eroman, 2014/09/09 22:35:18]

What I mean is that the "if" could be moved inside of the loop. You only use
"num_ranges" to compare if it is greater than uint8_max. So you could break out
of the above loop the moment that num_ranges == 256

[Ryan Hamilton, 2014/09/12 19:34:08]

Done.

         ++num_truncated_acks_sent_;
       break;
+    }

[eroman, 2014/09/09 00:08:01]

How clever does this algorithm need to be? (How often is this code run, and what
are the relative data sizes).

If you wanted to fast return when there is no possibility of incrementing
num_truncated_acks_sent you might consider enclosing it in:

if (*missing_packets.rbegin() - *missing_packets.begin() -
missing_packets.size() + 1 >= std::numeric_limits_<uint8>::max()) {
  ....
}

[Ryan Hamilton, 2014/09/09 19:00:36]

Good question. We run it for computing data for histograms. In the common case
missing_packets is empty. (Most connections suffer 0 lost packets). When there
are lost packets, they're typically small (~3). I wouldn't think that it would
be 
Ah, interesting idea! I like using early return here if the upper bound on the
number of ranges is less than the max. I'm curious about your calculation,
though. Since we typically expect a small number of missing packet, I'm inclined
to simply use the number of missing packets as the upper bound. Consider the
case of 2 missing packets which are a long distance apart. last-first-size would
be a large number, whereas size would simply be 2. How 'bout I use size instead?
 

[eroman, 2014/09/09 22:35:18]

Checking on size alone is another short cuircuit. Each addresses different
situations, so it depends what scenario is more likely/expensive. How about
combining the two?

The idea with the short-circuit I listed was to break early when there are many
consecutive packets -- a case I figured might be common

For instance if missing packets were:

1, 2, 3, 4, ...., 299, 300, 350  (size = 301)

The size test alone would not help, since there are more than 256 element in the
set.

However by subtracting the first and last elements we have an upper bound on how
many unique ranges there could be and that is less than 256.

If you wanted to be fancy could work that into an algorithm which runs the
heuristic recursively on each half as needed. Shrug.

[Ryan Hamilton, 2014/09/12 19:34:08]

Gotcha. I think I've implemented basically what you suggested, albeit reordering
slightly to ensure that we don't deref begin() on an empty set.

     case CONGESTION_FEEDBACK_FRAME:
       net_log_.AddEvent(
           NetLog::TYPE_QUIC_SESSION_CONGESTION_FEEDBACK_FRAME_SENT,
           base::Bind(&NetLogQuicCongestionFeedbackFrameCallback,
                      frame.congestion_feedback_frame));
       break;
     case RST_STREAM_FRAME:
       UMA_HISTOGRAM_SPARSE_SLOWLY("Net.QuicSession.RstStreamErrorCodeClient",
                                   frame.rst_stream_frame->error_code);
       net_log_.AddEvent(
@@ skipping 465 matching lines @@
       continue;
     }
     // Record some overlapping patterns, to get a better picture, since this is
     // not very expensive.
     if (i % 3 == 0)
       six_packet_histogram->Add(recent_6_mask);
   }
 }
 
 }  // namespace net