Add statistics gathering for packet loss.

webrtc/modules/rtp_rtcp/source/packet_loss_stats.cc

+/*
+ *  Copyright (c) 2015 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "webrtc/modules/rtp_rtcp/source/packet_loss_stats.h"
+
+static const int kBufferSize = 100;

[noahric, 2015/06/26 00:21:19]

Comment or name to point out that this is the size at which automatic pruning
occurs.

[bcornell, 2015/06/30 19:47:45]

Done.

+
+namespace webrtc {
+
+PacketLossStats::PacketLossStats()
+    : single_loss_historic_count_(0),
+      multiple_loss_historic_event_count_(0),
+      multiple_loss_historic_packet_count_(0) {
+}
+
+void PacketLossStats::AddLostPacket(uint16_t sequence_number) {
+  // Detect sequence number wrap around.

[noahric, 2015/06/26 00:21:19]

There's another way of handling this where you have a wraparound counter that
you increment and use as the high halfword when adding a new packet. You still
need a check in this function to detect wraparound and the packets need to
arrive in order, but you could get rid of the complexities around the two
buffers (except on full wrap).

[bcornell, 2015/06/30 19:47:45]

Indeed, I'm not sure how to handle that approach if the numbers don't come in
order. If we do want to bake in the assumption that they come in order, the
whole buffer is unnecessary and can be replaced by the last lost sequence number
and the count of adjacent lost packets before it.

+  if (sequence_number < 0x4000 && !lost_packets_buffer_.empty()

[noahric, 2015/06/26 00:21:19]

If you lose every ~200 packets or so, this wraparound check would miss it. Maybe
that's unlikely in practice, but even if you don't do my comment from above
(about the wraparound counter), consider checking the distance from the high
sequence number in lost_packets_buffer_ instead of the lowest (i.e. something
with rbegin(), with some distance like 0x8000). I took a quick look through the
webrtc codebase to find how it's handled elsewhere, but I couldn't find
anything. Hopefully other reviewers will know if there's a generally accepted
algorithm for it.

[bcornell, 2015/06/30 19:47:45]

True, this did not handle extremely sparse loss very well. I have updated it to
use distance, use the last element in the non-wrapped buffer, and always prune
the entire non-wrapped buffer once the wrapped buffer passes a threshold.

+      && *(lost_packets_buffer_.begin()) > 0xC000) {

[noahric, 2015/06/26 00:21:19]

&& at the end of the previous line

(you can probably just run 'git cl format' if you haven't yet)

[bcornell, 2015/06/30 19:47:45]

Done.

+    // The buffer contains large numbers and this is a small number.
+    lost_packets_wrapped_buffer_.insert(sequence_number);
+  } else {
+    lost_packets_buffer_.insert(sequence_number);
+  }
+  if (lost_packets_wrapped_buffer_.size() + lost_packets_buffer_.size()
+      > kBufferSize) {
+    PruneBuffer();
+  }
+}
+
+int PacketLossStats::GetSingleLossCount() const {
+  int single_loss_count, unused1, unused2;
+  ComputeLossCounts(&single_loss_count, &unused1, &unused2);
+  return single_loss_count;
+}
+
+int PacketLossStats::GetMultipleLossEventCount() const {
+  int event_count, unused1, unused2;
+  ComputeLossCounts(&unused1, &event_count, &unused2);
+  return event_count;
+}
+
+int PacketLossStats::GetMultipleLossPacketCount() const {
+  int packet_count, unused1, unused2;
+  ComputeLossCounts(&unused1, &unused2, &packet_count);
+  return packet_count;
+}
+
+void PacketLossStats::ComputeLossCounts(
+    int* out_single_loss_count,
+    int* out_multiple_loss_event_count,
+    int* out_multiple_loss_packet_count) const {
+  *out_single_loss_count = single_loss_historic_count_;
+  *out_multiple_loss_event_count = multiple_loss_historic_event_count_;
+  *out_multiple_loss_packet_count = multiple_loss_historic_packet_count_;
+  if (lost_packets_buffer_.empty()) {
+    return;

[noahric, 2015/06/26 00:21:19]

Consider DCHECK to ensure lost_packets_wrapped_buffer_ is also empty.

[bcornell, 2015/06/30 19:47:45]

Done.

+  }
+  uint16_t last_num = 0;
+  int sequential_count = 0;
+  const std::set<uint16_t>* buffer = &lost_packets_buffer_;
+  for (int i = 0; i < 2; ++i) {

[noahric, 2015/06/26 00:21:19]

C++11 ftw:

for (auto buffer : { &lost_packets_buffer_, &lost_packets_wrapped_buffer_ }) {

[bcornell, 2015/06/30 19:47:45]

Done.

+    for (auto it = buffer->begin(); it != buffer->end(); ++it) {
+      uint16_t next_num = *it;

[noahric, 2015/06/26 00:21:19]

I'd say current_num, though I bet it wouldn't fit on line 72 :)

[bcornell, 2015/06/30 19:47:45]

Done.

+      if (sequential_count > 0 && next_num != ((last_num + 1) & 0xFFFF)) {
+        if (sequential_count == 1) {
+          (*out_single_loss_count)++;
+        } else if (sequential_count > 1) {
+          (*out_multiple_loss_event_count)++;
+          *out_multiple_loss_packet_count += sequential_count;
+        }
+        sequential_count = 0;
+      }
+      sequential_count++;
+      last_num = next_num;
+    }
+    buffer = &lost_packets_wrapped_buffer_;
+  }
+  if (sequential_count == 1) {
+    (*out_single_loss_count)++;
+  } else if (sequential_count > 1) {
+    (*out_multiple_loss_event_count)++;
+    *out_multiple_loss_packet_count += sequential_count;
+  }

[noahric, 2015/06/26 00:21:19]

Is there a reasonable way to do some more thorough pruning here as well and move
it into PruneBuffer? Since we're already enumerating the full list, it seems
like you could prune everything but the last packet (group). Assuming it's fast
enough to do in the normal prune case (if it isn't, maybe you could prune more
often).

[bcornell, 2015/06/30 19:47:45]

Well, the point of the buffer is to allow reasonably old packet loss to come in
out of order. If we don't care about that, we should just decrease the size of
the buffer or eliminate the buffer entirely and require packets to come in
order.

+}
+
+void PacketLossStats::PruneBuffer() {
+  // Remove the oldest lost packet and any contiguous packets and move them
+  // into the historic counts.
+  auto it = lost_packets_buffer_.begin();
+  uint16_t last_removed = *it;
+  int remove_count = 1;
+  it = lost_packets_buffer_.erase(it);
+  while (!lost_packets_buffer_.empty() && *it == last_removed + 1) {
+    last_removed++;
+    remove_count++;
+    it = lost_packets_buffer_.erase(it);
+  }
+  // Continue counting if it is wrap around by swapping in the wrapped buffer
+  // and letting our value wrap as well.
+  if (lost_packets_buffer_.empty()) {
+    lost_packets_buffer_.swap(lost_packets_wrapped_buffer_);
+    it = lost_packets_buffer_.begin();
+    while (!lost_packets_buffer_.empty()

[noahric, 2015/06/26 00:21:19]

Too bad you can't easily combine this with the block above :-/ Especially since
you could replace the block above with this version (that allows wrappping) and
it'd still work.

[bcornell, 2015/06/30 19:47:45]

Don't tell me what I can't combine :-p

+           && *it == ((last_removed + 1) & 0xFFFF)) {
+      last_removed = *it;
+      remove_count++;
+      it = lost_packets_buffer_.erase(it);
+    }
+  }
+  if (remove_count > 1) {
+    multiple_loss_historic_event_count_++;
+    multiple_loss_historic_packet_count_ += remove_count;
+  } else {
+    single_loss_historic_count_++;
+  }
+}
+
+}  // namespace webrtc