Amortize invariant maintenance in DTLSMessageBitmap
After we receive a handshake fragment, we check if the fragment is now
complete. This requires scanning over the entire message bitmap. This is
the one step in MarkRange that does not scale with the number of bytes
the peer sent us.
This is not really a DoS vector due to message size limits but, in
principle, the peer could send us all but the last byte of a message and
then repeatedly send us the first byte, causing us to scan over
msg_len / 8 bytes each time. We can easily amortize this by saving how
far we scanned last time, because bits will never be unmarked. This
means we only advance over each byte in the bitmap once.
Change-Id: I802003d587de4c0a45650b891c76cea8b10acd17
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/72287
Reviewed-by: Nick Harper <nharper@chromium.org>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/ssl/d1_both.cc b/ssl/d1_both.cc
index e0faa6d..f262094 100644
--- a/ssl/d1_both.cc
+++ b/ssl/d1_both.cc
@@ -176,14 +176,17 @@
return false;
}
MarkRange(num_bits, bits_rounded);
+ first_unmarked_byte_ = 0;
return true;
}
void DTLSMessageBitmap::MarkRange(size_t start, size_t end) {
+ assert(start <= end);
+ // Don't bother touching bytes that have already been marked.
+ start = std::max(start, first_unmarked_byte_ << 3);
// Clamp everything within range.
start = std::min(start, bytes_.size() << 3);
end = std::min(end, bytes_.size() << 3);
- assert(start <= end);
if (start >= end) {
return;
}
@@ -200,17 +203,25 @@
}
}
- // Release the buffer if we've marked everything.
- auto iter = std::find_if(bytes_.begin(), bytes_.end(),
- [](uint8_t b) { return b != 0xff; });
- if (iter == bytes_.end()) {
- assert(NextUnmarkedRange(0).empty());
+ // Maintain the |first_unmarked_byte_| invariant. This work is amortized
+ // across all |MarkRange| calls.
+ while (first_unmarked_byte_ < bytes_.size() &&
+ bytes_[first_unmarked_byte_] == 0xff) {
+ first_unmarked_byte_++;
+ }
+ // If the whole message is marked, we no longer need to spend memory on the
+ // bitmap.
+ if (first_unmarked_byte_ >= bytes_.size()) {
bytes_.Reset();
+ first_unmarked_byte_ = 0;
}
}
DTLSMessageBitmap::Range DTLSMessageBitmap::NextUnmarkedRange(
size_t start) const {
+ // Don't bother looking at bytes that are known to be fully marked.
+ start = std::max(start, first_unmarked_byte_ << 3);
+
size_t idx = start >> 3;
if (idx >= bytes_.size()) {
return Range{0, 0};
diff --git a/ssl/internal.h b/ssl/internal.h
index af988de..0ea226a 100644
--- a/ssl/internal.h
+++ b/ssl/internal.h
@@ -3333,6 +3333,9 @@
// bytes_ contains the unmarked bits. We maintain an invariant: if |bytes_| is
// not empty, some bit is unset.
Array<uint8_t> bytes_;
+ // first_unmarked_byte_ is the index of first byte in |bytes_| that is not
+ // 0xff. This is maintained to amortize checking if the message is complete.
+ size_t first_unmarked_byte_ = 0;
};
struct hm_header_st {
