Implement a fixed-width ring buffer for DTLS 1.3
DTLS 1.3 ACK management requires that we track:
- Received record numbers, to send in ACKs
- Information about unacked outgoing records, so we can update message
state when ACKs from in
Both of those lists can, in principle, grow unboundedly, but can also be
freely dropped. This class is intended as a fixed-width ring buffer for
managing this. I was worried I'd need need to dip into the scary
uninitialized functions again but actually this is just an InplaceVector
and an integer, so that was quite satisfying.
Bug: 374890768
Change-Id: I4037ef5875a2df70f0dc16df1bbba478362cecce
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/72274
Reviewed-by: Nick Harper <nharper@chromium.org>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/ssl/internal.h b/ssl/internal.h
index 0ea226a..f2b8b93 100644
--- a/ssl/internal.h
+++ b/ssl/internal.h
@@ -674,6 +674,51 @@
PackedSize<N> size_ = 0;
};
+// An MRUQueue maintains a queue of up to |N| objects of type |T|. If the queue
+// is at capacity, adding to the queue pops the least recently added element.
+template <typename T, size_t N>
+class MRUQueue {
+ public:
+ static constexpr bool kAllowUniquePtr = true;
+
+ MRUQueue() = default;
+
+ // If we ever need to make this type movable, we could. (The defaults almost
+ // work except we need |start_| to be reset when moved-from.)
+ MRUQueue(const MRUQueue &other) = delete;
+ MRUQueue &operator=(const MRUQueue &other) = delete;
+
+ bool empty() const { return size() == 0; }
+ size_t size() const { return storage_.size(); }
+
+ T &operator[](size_t i) {
+ BSSL_CHECK(i < size());
+ return storage_[(start_ + i) % N];
+ }
+ const T &operator[](size_t i) const {
+ return (*const_cast<MRUQueue *>(this))[i];
+ }
+
+ void Clear() {
+ storage_.clear();
+ start_ = 0;
+ }
+
+ void PushBack(T t) {
+ if (storage_.size() < N) {
+ assert(start_ == 0);
+ storage_.PushBack(std::move(t));
+ } else {
+ (*this)[0] = std::move(t);
+ start_ = (start_ + 1) % N;
+ }
+ }
+
+ private:
+ InplaceVector<T, N> storage_;
+ PackedSize<N> start_ = 0;
+};
+
// CBBFinishArray behaves like |CBB_finish| but stores the result in an Array.
OPENSSL_EXPORT bool CBBFinishArray(CBB *cbb, Array<uint8_t> *out);
diff --git a/ssl/ssl_internal_test.cc b/ssl/ssl_internal_test.cc
index b6abafd..42c9c79 100644
--- a/ssl/ssl_internal_test.cc
+++ b/ssl/ssl_internal_test.cc
@@ -600,6 +600,69 @@
expect_bitmap(bitmap2, {});
}
+TEST(MRUQueueTest, Basic) {
+ // Use a complex type to confirm the queue handles them correctly.
+ MRUQueue<std::unique_ptr<int>, 8> queue;
+ auto expect_queue = [&](const std::vector<int> &expected) {
+ EXPECT_EQ(queue.size(), expected.size());
+ EXPECT_EQ(queue.empty(), expected.empty());
+ std::vector<int> queue_values;
+ for (size_t i = 0; i < queue.size(); i++) {
+ queue_values.push_back(*queue[i]);
+ }
+ EXPECT_EQ(queue_values, expected);
+ };
+
+ expect_queue({});
+ queue.PushBack(std::make_unique<int>(1));
+ expect_queue({1});
+ queue.PushBack(std::make_unique<int>(2));
+ expect_queue({1, 2});
+ queue.PushBack(std::make_unique<int>(3));
+ expect_queue({1, 2, 3});
+ queue.PushBack(std::make_unique<int>(4));
+ expect_queue({1, 2, 3, 4});
+ queue.PushBack(std::make_unique<int>(5));
+ expect_queue({1, 2, 3, 4, 5});
+ queue.PushBack(std::make_unique<int>(6));
+ expect_queue({1, 2, 3, 4, 5, 6});
+ queue.PushBack(std::make_unique<int>(7));
+ expect_queue({1, 2, 3, 4, 5, 6, 7});
+ queue.PushBack(std::make_unique<int>(8));
+ expect_queue({1, 2, 3, 4, 5, 6, 7, 8});
+
+ // We are at capacity, so later additions will drop the start. Do more than 8
+ // insertions to test that the start index can wrap around.
+ queue.PushBack(std::make_unique<int>(9));
+ expect_queue({2, 3, 4, 5, 6, 7, 8, 9});
+ queue.PushBack(std::make_unique<int>(10));
+ expect_queue({3, 4, 5, 6, 7, 8, 9, 10});
+ queue.PushBack(std::make_unique<int>(11));
+ expect_queue({4, 5, 6, 7, 8, 9, 10, 11});
+ queue.PushBack(std::make_unique<int>(12));
+ expect_queue({5, 6, 7, 8, 9, 10, 11, 12});
+ queue.PushBack(std::make_unique<int>(13));
+ expect_queue({6, 7, 8, 9, 10, 11, 12, 13});
+ queue.PushBack(std::make_unique<int>(14));
+ expect_queue({7, 8, 9, 10, 11, 12, 13, 14});
+ queue.PushBack(std::make_unique<int>(15));
+ expect_queue({8, 9, 10, 11, 12, 13, 14, 15});
+ queue.PushBack(std::make_unique<int>(16));
+ expect_queue({9, 10, 11, 12, 13, 14, 15, 16});
+ queue.PushBack(std::make_unique<int>(17));
+ expect_queue({10, 11, 12, 13, 14, 15, 16, 17});
+
+ // Clearing the queue should not leave the start index in a bad place.
+ queue.Clear();
+ expect_queue({});
+ queue.PushBack(std::make_unique<int>(1));
+ expect_queue({1});
+ queue.PushBack(std::make_unique<int>(2));
+ expect_queue({1, 2});
+ queue.PushBack(std::make_unique<int>(3));
+ expect_queue({1, 2, 3});
+}
+
} // namespace
BSSL_NAMESPACE_END
#endif // !BORINGSSL_SHARED_LIBRARY
