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

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

Committed: https://crrev.com/30ddbd00f8343a8576c4961fd7aa8fa444780a4a
Cr-Commit-Position: refs/heads/master@{#294661}

[Ryan Hamilton, 2014-09-08 16:57:38]

rch@chromium.org changed reviewers:
+ ianswett@google.com, jri@chromium.org

[Ian Swett, 2014-09-08 17:27:58]

lgtm

Looks good, though it's unfortunate the flag isn't being set properly.

https://codereview.chromium.org/549433006/diff/1/net/quic/quic_connection_log...
File net/quic/quic_connection_logger.cc (right):

https://codereview.chromium.org/549433006/diff/1/net/quic/quic_connection_log...
net/quic/quic_connection_logger.cc:377: if (frame.ack_frame->missing_packets[i]
!= last_missing + 1) {
It's annoying to have to perform this logic in multiple spots, but LGTM.

[Ryan Hamilton, 2014-09-08 17:31:16]

On 2014/09/08 17:27:58, Ian Swett wrote:
> lgtm
> 
> Looks good, though it's unfortunate the flag isn't being set properly.
> 
>
https://codereview.chromium.org/549433006/diff/1/net/quic/quic_connection_log...
> File net/quic/quic_connection_logger.cc (right):
> 
>
https://codereview.chromium.org/549433006/diff/1/net/quic/quic_connection_log...
> net/quic/quic_connection_logger.cc:377: if
(frame.ack_frame->missing_packets[i]
> != last_missing + 1) {
> It's annoying to have to perform this logic in multiple spots, but LGTM.

Yeah, totally agree. :<

[Jana, 2014-09-08 17:46:30]

lgtm

[Ryan Hamilton, 2014-09-08 17:47:10]

The CQ bit was checked by rch@chromium.org

[commit-bot: I haz the power, 2014-09-08 17:48:39]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/rch@chromium.org/549433006/20001

[commit-bot: I haz the power, 2014-09-08 17:48:40]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-09-08 17:48:41]

No LGTM from a valid reviewer yet. Only full committers are accepted.
Even if an LGTM may have been provided, it was from a non-committer or
a provisional committer, _not_ a full super star committer.
See http://www.chromium.org/getting-involved/become-a-committer
Note that this has nothing to do with OWNERS files.

[Ryan Hamilton, 2014-09-08 22:46:02]

rch@chromium.org changed reviewers:
+ eroman@chromium.org

[Ryan Hamilton, 2014-09-08 22:46:03]

eroman: I think you're actually a committer. Can you take a look?

[Jana, 2014-09-08 22:50:50]

aww... my lgtm not special enough :-(

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

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
File net/quic/quic_connection_logger.cc (right):

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:380: if (*it != last_missing + 1) {
possibility of integer overflow?

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:385: if (num_ranges >=
std::numeric_limits<uint8>::max())
is it necessary to iterate everything if this is the only test being performed?

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:388: }
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()) {
  ....
}

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
File net/quic/quic_connection_logger_unittest.cc (right):

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger_unittest.cc:1: // Copyright 2013 The Chromium
Authors. All rights reserved.
welcome to 2014

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger_unittest.cc:39: }
can you add a test where truncation does not occur?

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

Thanks for the review, Eric!

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
File net/quic/quic_connection_logger.cc (right):

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:380: if (*it != last_missing + 1) {
On 2014/09/09 00:08:01, eroman wrote:
> possibility of integer overflow?

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)

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:385: if (num_ranges >=
std::numeric_limits<uint8>::max())
On 2014/09/09 00:08:01, eroman wrote:
> is it necessary to iterate everything if this is the only test being
performed?

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

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:388: }
On 2014/09/09 00:08:01, eroman wrote:
> How clever does this algorithm need to be? (How often is this code run, and
what
> are the relative data sizes).

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 

> 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()) {
>   ....
> }

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?

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
File net/quic/quic_connection_logger_unittest.cc (right):

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger_unittest.cc:1: // Copyright 2013 The Chromium
Authors. All rights reserved.
On 2014/09/09 00:08:01, eroman wrote:
> welcome to 2014

Get off my lawn! :>

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger_unittest.cc:39: }
On 2014/09/09 00:08:01, eroman wrote:
> can you add a test where truncation does not occur?

Done. (That happened implicitly when the empty frame was processed, but better
to be explicit)

[eroman, 2014-09-09 22:35:19]

lgtm

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
File net/quic/quic_connection_logger.cc (right):

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:385: if (num_ranges >=
std::numeric_limits<uint8>::max())
On 2014/09/09 19:00:36, Ryan Hamilton wrote:
> On 2014/09/09 00:08:01, eroman wrote:
> > is it necessary to iterate everything if this is the only test being
> performed?
> 
> as far as I know, but I'd be happy to come up with a better approach if you
can
> think of one?

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

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:388: }
On 2014/09/09 19:00:36, Ryan Hamilton wrote:
> On 2014/09/09 00:08:01, eroman wrote:
> > How clever does this algorithm need to be? (How often is this code run, and
> what
> > are the relative data sizes).
> 
> 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 
> 
> > 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()) {
> >   ....
> > }
> 
> 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?
>  

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]

Thanks for the great review!

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
File net/quic/quic_connection_logger.cc (right):

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:385: if (num_ranges >=
std::numeric_limits<uint8>::max())
On 2014/09/09 22:35:18, eroman wrote:
> On 2014/09/09 19:00:36, Ryan Hamilton wrote:
> > On 2014/09/09 00:08:01, eroman wrote:
> > > is it necessary to iterate everything if this is the only test being
> > performed?
> > 
> > as far as I know, but I'd be happy to come up with a better approach if you
> can
> > think of one?
> 
> 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

Done.

https://codereview.chromium.org/549433006/diff/20001/net/quic/quic_connection...
net/quic/quic_connection_logger.cc:388: }
On 2014/09/09 22:35:18, eroman wrote:
> On 2014/09/09 19:00:36, Ryan Hamilton wrote:
> > On 2014/09/09 00:08:01, eroman wrote:
> > > How clever does this algorithm need to be? (How often is this code run,
and
> > what
> > > are the relative data sizes).
> > 
> > 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 
> > 
> > > 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()) {
> > >   ....
> > > }
> > 
> > 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?
> >  
> 
> 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.

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.

[Ryan Hamilton, 2014-09-12 19:36:08]

The CQ bit was checked by rch@chromium.org

[commit-bot: I haz the power, 2014-09-12 19:38:22]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patchset/549433006/60001

[commit-bot: I haz the power, 2014-09-12 21:26:22]

Committed patchset #4 (id:60001) as 4eaf5e50bc9f6904c653fb00a526fe899df2b766

[commit-bot: I haz the power, 2014-09-12 21:31:21]

Patchset 4 (id:??) landed as
https://crrev.com/30ddbd00f8343a8576c4961fd7aa8fa444780a4a
Cr-Commit-Position: refs/heads/master@{#294661}