pw_ring_buffer: Initial checkin This is the beginnings of the ring buffer module. To start, there is only one type of ring buffer: the PrefixedEntryRingBuffer. This ring buffer supports variable length entries, and optionally a user-supplied preamble byte. The variable length entries are delimited with a length-value encoding, with the lengths varints. A consequence of this storage approach is that it is possible for the ring buffer to be a valid protocol buffer in memory (minus the dering). This is a port of David Rogers <davidrogers@google.com>'s work on an internal project. Change-Id: Ia2b4da38712828451066b4638c73bfab295b26c8
diff --git a/BUILD.gn b/BUILD.gn index 609ecbf..29cba53 100644 --- a/BUILD.gn +++ b/BUILD.gn
@@ -92,6 +92,7 @@ "$dir_pw_protobuf:tests", "$dir_pw_protobuf_compiler:tests", "$dir_pw_result:tests", + "$dir_pw_ring_buffer:tests", "$dir_pw_span:tests", "$dir_pw_status:tests", "$dir_pw_string:tests",
diff --git a/docs/BUILD.gn b/docs/BUILD.gn index 6cc390e..1a3de08 100644 --- a/docs/BUILD.gn +++ b/docs/BUILD.gn
@@ -82,6 +82,7 @@ "$dir_pw_protobuf:docs", "$dir_pw_protobuf_compiler:docs", "$dir_pw_result:docs", + "$dir_pw_ring_buffer:docs", "$dir_pw_span:docs", "$dir_pw_status:docs", "$dir_pw_string:docs",
diff --git a/modules.gni b/modules.gni index 809d385..b8ed005 100644 --- a/modules.gni +++ b/modules.gni
@@ -43,6 +43,7 @@ dir_pw_protobuf = "$dir_pigweed/pw_protobuf" dir_pw_protobuf_compiler = "$dir_pigweed/pw_protobuf_compiler" dir_pw_result = "$dir_pigweed/pw_result" +dir_pw_ring_buffer = "$dir_pigweed/pw_ring_buffer" dir_pw_span = "$dir_pigweed/pw_span" dir_pw_status = "$dir_pigweed/pw_status" dir_pw_string = "$dir_pigweed/pw_string"
diff --git a/pw_ring_buffer/BUILD b/pw_ring_buffer/BUILD new file mode 100644 index 0000000..476ca1d --- /dev/null +++ b/pw_ring_buffer/BUILD
@@ -0,0 +1,45 @@ +# Copyright 2020 The Pigweed Authors +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +load( + "//pw_build:pigweed.bzl", + "pw_cc_library", + "pw_cc_test", +) + +package(default_visibility = ["//visibility:public"]) + +licenses(["notice"]) # Apache License 2.0 + +pw_cc_library( + name = "pw_ring_buffer", + hdrs = [ + "public/pw_ring_buffer/prefixed_entry_ring_buffer.h", + ], + srcs = [ + "prefixed_entry_ring_buffer.cc", + ], + includes = ["public"], +) + +pw_cc_test( + name = "prefixed_entry_ring_buffer_test", + srcs = [ + "prefixed_entry_ring_buffer_test.cc", + ], + deps = [ + ":pw_ring_buffer", + "//pw_unit_test", + ], +)
diff --git a/pw_ring_buffer/BUILD.gn b/pw_ring_buffer/BUILD.gn new file mode 100644 index 0000000..f51a094 --- /dev/null +++ b/pw_ring_buffer/BUILD.gn
@@ -0,0 +1,45 @@ +# Copyright 2020 The Pigweed Authors +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +import("$dir_pw_docgen/docs.gni") +import("$dir_pw_unit_test/test.gni") + +config("default_config") { + include_dirs = [ "public" ] +} + +source_set("pw_ring_buffer") { + public_configs = [ ":default_config" ] + public_deps = [ + "$dir_pw_containers", + "$dir_pw_span", + "$dir_pw_status", + ] + sources = [ "prefixed_entry_ring_buffer.cc" ] + public = [ "public/pw_ring_buffer/prefixed_entry_ring_buffer.h" ] + deps = [ "$dir_pw_varint" ] +} + +pw_test_group("tests") { + tests = [ ":prefixed_entry_ring_buffer_test" ] +} + +pw_test("prefixed_entry_ring_buffer_test") { + deps = [ ":pw_ring_buffer" ] + sources = [ "prefixed_entry_ring_buffer_test.cc" ] +} + +pw_doc_group("docs") { + sources = [ "docs.rst" ] +}
diff --git a/pw_ring_buffer/docs.rst b/pw_ring_buffer/docs.rst new file mode 100644 index 0000000..c3ab200 --- /dev/null +++ b/pw_ring_buffer/docs.rst
@@ -0,0 +1,20 @@ +.. default-domain:: cpp + +.. highlight:: sh + +-------------- +pw_ring_buffer +-------------- +The ``pw_ring_buffer`` module will eventually provide several ring buffer +implementations, each with different tradeoffs. + +This documentation is incomplete :) + +Compatibility +============= +* C++11 + +Dependencies +============ +* ``pw_span`` +* ``pw_containers`` - for tests only
diff --git a/pw_ring_buffer/prefixed_entry_ring_buffer.cc b/pw_ring_buffer/prefixed_entry_ring_buffer.cc new file mode 100644 index 0000000..dd475ff --- /dev/null +++ b/pw_ring_buffer/prefixed_entry_ring_buffer.cc
@@ -0,0 +1,267 @@ +// Copyright 2020 The Pigweed Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "pw_ring_buffer/prefixed_entry_ring_buffer.h" + +#include <cstring> + +#include "pw_varint/varint.h" + +namespace pw { +namespace ring_buffer { + +using std::byte; + +void PrefixedEntryRingBuffer::Clear() { + read_idx_ = 0; + write_idx_ = 0; + entry_count_ = 0; +} + +Status PrefixedEntryRingBuffer::SetBuffer(span<byte> buffer) { + if ((buffer.data() == nullptr) || // + (buffer.size_bytes() == 0) || // + (buffer.size_bytes() > kMaxBufferBytes)) { + return Status::INVALID_ARGUMENT; + } + + buffer_ = buffer.data(); + buffer_bytes_ = buffer.size_bytes(); + + Clear(); + return Status::OK; +} + +Status PrefixedEntryRingBuffer::PushBack(span<const byte> data, + byte user_preamble_data) { + if (buffer_ == nullptr) { + return Status::FAILED_PRECONDITION; + } + if (data.size_bytes() == 0) { + return Status::INVALID_ARGUMENT; + } + + // Prepare the preamble, and ensure we can fit the preamble and entry. + byte varint_buf[kMaxEntryPreambleBytes]; + size_t varint_bytes = varint::Encode<size_t>(data.size_bytes(), varint_buf); + size_t total_write_bytes = + (user_preamble_ ? 1 : 0) + varint_bytes + data.size_bytes(); + if (buffer_bytes_ < total_write_bytes) { + return Status::OUT_OF_RANGE; + } + + // Drop old entries until we have space for the new entry. + while (RawAvailableBytes() < total_write_bytes) { + PopFront(); + } + + // Write the new entry into the ring buffer. + if (user_preamble_) { + RawWrite(span(&user_preamble_data, sizeof(user_preamble_data))); + } + RawWrite(span(varint_buf, varint_bytes)); + RawWrite(data); + entry_count_++; + return Status::OK; +} + +auto GetOutput(span<byte> data_out, size_t* write_index) { + return [data_out, write_index](span<const byte> src) -> Status { + size_t copy_size = std::min(data_out.size_bytes(), src.size_bytes()); + + memcpy(data_out.data() + *write_index, src.data(), copy_size); + *write_index += copy_size; + + return (copy_size == src.size_bytes()) ? Status::OK + : Status::RESOURCE_EXHAUSTED; + }; +} + +Status PrefixedEntryRingBuffer::PeekFront(span<byte> data, size_t* bytes_read) { + *bytes_read = 0; + return InternalRead(GetOutput(data, bytes_read), false); +} + +Status PrefixedEntryRingBuffer::PeekFront(ReadOutput output) { + return InternalRead(output, false); +} + +Status PrefixedEntryRingBuffer::PeekFrontWithPreamble(span<byte> data, + size_t* bytes_read) { + *bytes_read = 0; + return InternalRead(GetOutput(data, bytes_read), true); +} + +Status PrefixedEntryRingBuffer::PeekFrontWithPreamble(ReadOutput output) { + return InternalRead(output, true); +} + +// T should be similar to Status (*read_output)(span<const byte>) +template <typename T> +Status PrefixedEntryRingBuffer::InternalRead(T read_output, bool get_preamble) { + if (buffer_ == nullptr) { + return Status::FAILED_PRECONDITION; + } + if (EntryCount() == 0) { + return Status::OUT_OF_RANGE; + } + + // Figure out where to start reading (wrapped); accounting for preamble. + EntryInfo info = FrontEntryInfo(); + size_t read_bytes = info.data_bytes; + size_t data_read_idx = read_idx_; + if (get_preamble) { + read_bytes += info.preamble_bytes; + } else { + data_read_idx = IncrementIndex(data_read_idx, info.preamble_bytes); + } + + // Read bytes, stopping at the end of the buffer if this entry wraps. + size_t bytes_until_wrap = buffer_bytes_ - data_read_idx; + size_t bytes_to_copy = std::min(read_bytes, bytes_until_wrap); + Status status = read_output(span(buffer_ + data_read_idx, bytes_to_copy)); + + // If the entry wrapped, read the remaining bytes. + if (status.ok() && (bytes_to_copy < read_bytes)) { + status = read_output(span(buffer_, read_bytes - bytes_to_copy)); + } + return status; +} + +Status PrefixedEntryRingBuffer::PopFront() { + if (buffer_ == nullptr) { + return Status::FAILED_PRECONDITION; + } + if (EntryCount() == 0) { + return Status::OUT_OF_RANGE; + } + + // Advance the read pointer past the front entry to the next one. + EntryInfo info = FrontEntryInfo(); + size_t entry_bytes = info.preamble_bytes + info.data_bytes; + read_idx_ = IncrementIndex(read_idx_, entry_bytes); + entry_count_--; + return Status::OK; +} + +Status PrefixedEntryRingBuffer::Dering() { + if (buffer_ == nullptr) { + return Status::FAILED_PRECONDITION; + } + // Check if by luck we're already deringed. + if (read_idx_ == 0) { + return Status::OK; + } + + auto buffer_span = span(buffer_, buffer_bytes_); + std::rotate( + buffer_span.begin(), buffer_span.begin() + read_idx_, buffer_span.end()); + + // If the new index is past the end of the buffer, + // alias it back (wrap) to the start of the buffer. + if (write_idx_ < read_idx_) { + write_idx_ += buffer_bytes_; + } + write_idx_ -= read_idx_; + read_idx_ = 0; + return Status::OK; +} + +size_t PrefixedEntryRingBuffer::FrontEntryDataSizeBytes() { + if (EntryCount() == 0) { + return 0; + } + return FrontEntryInfo().data_bytes; +} + +size_t PrefixedEntryRingBuffer::FrontEntryTotalSizeBytes() { + if (EntryCount() == 0) { + return 0; + } + EntryInfo info = FrontEntryInfo(); + return info.preamble_bytes + info.data_bytes; +} + +PrefixedEntryRingBuffer::EntryInfo PrefixedEntryRingBuffer::FrontEntryInfo() { + // Entry headers consists of: (optional prefix byte, varint size, data...) + + // Read the entry header; extract the varint and it's size in bytes. + byte varint_buf[kMaxEntryPreambleBytes]; + RawRead(varint_buf, + IncrementIndex(read_idx_, user_preamble_ ? 1 : 0), + kMaxEntryPreambleBytes); + uint64_t entry_size; + size_t varint_size = varint::Decode(varint_buf, &entry_size); + + EntryInfo info = {}; + info.preamble_bytes = (user_preamble_ ? 1 : 0) + varint_size; + info.data_bytes = entry_size; + return info; +} + +// Comparisons ordered for more probable early exits, assuming the reader is +// not far behind the writer compared to the size of the ring. +size_t PrefixedEntryRingBuffer::RawAvailableBytes() { + // Case: Not wrapped. + if (read_idx_ < write_idx_) { + return buffer_bytes_ - (write_idx_ - read_idx_); + } + // Case: Wrapped + if (read_idx_ > write_idx_) { + return read_idx_ - write_idx_; + } + // Case: Matched read and write heads; empty or full. + return entry_count_ ? 0 : buffer_bytes_; +} + +void PrefixedEntryRingBuffer::RawWrite(span<const std::byte> source) { + // Write until the end of the source or the backing buffer. + size_t bytes_until_wrap = buffer_bytes_ - write_idx_; + size_t bytes_to_copy = std::min(source.size(), bytes_until_wrap); + memcpy(buffer_ + write_idx_, source.data(), bytes_to_copy); + + // If there wasn't space in the backing buffer, wrap to the front. + if (bytes_to_copy < source.size()) { + memcpy( + buffer_, source.data() + bytes_to_copy, source.size() - bytes_to_copy); + } + write_idx_ = IncrementIndex(write_idx_, source.size()); +} + +void PrefixedEntryRingBuffer::RawRead(byte* destination, + size_t source_idx, + size_t length_bytes) { + // Read the pre-wrap bytes. + size_t bytes_until_wrap = buffer_bytes_ - source_idx; + size_t bytes_to_copy = std::min(length_bytes, bytes_until_wrap); + memcpy(destination, buffer_ + source_idx, bytes_to_copy); + + // Read the post-wrap bytes, if needed. + if (bytes_to_copy < length_bytes) { + memcpy(destination + bytes_to_copy, buffer_, length_bytes - bytes_to_copy); + } +} + +size_t PrefixedEntryRingBuffer::IncrementIndex(size_t index, size_t count) { + // Note: This doesn't use modulus (%) since the branch is cheaper, and we + // guarantee that count will never be greater than buffer_bytes_. + index += count; + if (index > buffer_bytes_) { + index -= buffer_bytes_; + } + return index; +} + +} // namespace ring_buffer +} // namespace pw
diff --git a/pw_ring_buffer/prefixed_entry_ring_buffer_test.cc b/pw_ring_buffer/prefixed_entry_ring_buffer_test.cc new file mode 100644 index 0000000..f4dd005 --- /dev/null +++ b/pw_ring_buffer/prefixed_entry_ring_buffer_test.cc
@@ -0,0 +1,367 @@ +// Copyright 2020 The Pigweed Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "pw_ring_buffer/prefixed_entry_ring_buffer.h" + +#include <cstddef> +#include <cstdint> + +#include "pw_containers/vector.h" +#include "pw_unit_test/framework.h" + +using std::byte; + +namespace pw { +namespace ring_buffer { +namespace { + +TEST(PrefixedEntryRingBuffer, NoBuffer) { + PrefixedEntryRingBuffer ring(false); + + byte buf[32]; + size_t count; + + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.SetBuffer(span<byte>(nullptr, 10u)), Status::INVALID_ARGUMENT); + EXPECT_EQ(ring.SetBuffer(span(buf, 0u)), Status::INVALID_ARGUMENT); + EXPECT_EQ(ring.FrontEntryDataSizeBytes(), 0u); + + EXPECT_EQ(ring.PushBack(buf), Status::FAILED_PRECONDITION); + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.PeekFront(buf, &count), Status::FAILED_PRECONDITION); + EXPECT_EQ(count, 0u); + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.PeekFrontWithPreamble(buf, &count), + Status::FAILED_PRECONDITION); + EXPECT_EQ(count, 0u); + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.PopFront(), Status::FAILED_PRECONDITION); + EXPECT_EQ(ring.EntryCount(), 0u); +} + +// Single entry to write/read/pop over and over again. +constexpr byte single_entry_data[] = {byte(1), + byte(2), + byte(3), + byte(4), + byte(5), + byte(6), + byte(7), + byte(8), + byte(9)}; +constexpr size_t single_entry_total_size = sizeof(single_entry_data) + 1; +constexpr size_t single_entry_test_buffer_size = + (single_entry_total_size * 7) / 2; + +// Make sure the single_entry_size is even so single_entry_buffer_Size gets the +// proper wrap/even behavior when getting to the end of the buffer. +static_assert((single_entry_total_size % 2) == 0u); +constexpr size_t kSingleEntryCycles = 300u; + +// Repeatedly write the same data, read it, and pop it, done over and over +// again. +void SingleEntryWriteReadTest(bool user_data) { + PrefixedEntryRingBuffer ring(user_data); + byte test_buffer[single_entry_test_buffer_size]; + + byte read_buffer[single_entry_total_size]; + + // Set read_size to an unexpected value to make sure result checks don't luck + // out and happen to see a previous value. + size_t read_size = 500U; + + EXPECT_EQ(ring.SetBuffer(test_buffer), Status::OK); + + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.PopFront(), Status::OUT_OF_RANGE); + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.PushBack(span(single_entry_data, 0u)), + Status::INVALID_ARGUMENT); + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.PushBack(span(single_entry_data, sizeof(test_buffer) + 5)), + Status::OUT_OF_RANGE); + EXPECT_EQ(ring.EntryCount(), 0u); + EXPECT_EQ(ring.PeekFront(read_buffer, &read_size), Status::OUT_OF_RANGE); + EXPECT_EQ(read_size, 0u); + read_size = 500U; + EXPECT_EQ(ring.PeekFrontWithPreamble(read_buffer, &read_size), + Status::OUT_OF_RANGE); + EXPECT_EQ(read_size, 0u); + + size_t user_preamble_bytes = (user_data ? 1 : 0); + size_t data_size = sizeof(single_entry_data) - user_preamble_bytes; + size_t data_offset = single_entry_total_size - data_size; + + byte expect_buffer[single_entry_total_size] = {}; + expect_buffer[user_preamble_bytes] = byte(data_size); + memcpy(expect_buffer + data_offset, single_entry_data, data_size); + + for (size_t i = 0; i < kSingleEntryCycles; i++) { + ASSERT_EQ(ring.FrontEntryDataSizeBytes(), 0u); + ASSERT_EQ(ring.FrontEntryTotalSizeBytes(), 0u); + + ASSERT_EQ(ring.PushBack(span(single_entry_data, data_size), byte(i)), + Status::OK); + ASSERT_EQ(ring.FrontEntryDataSizeBytes(), data_size); + ASSERT_EQ(ring.FrontEntryTotalSizeBytes(), single_entry_total_size); + + read_size = 500U; + ASSERT_EQ(ring.PeekFront(read_buffer, &read_size), Status::OK); + ASSERT_EQ(read_size, data_size); + + // ASSERT_THAT(span(expect_buffer).last(data_size), + // testing::ElementsAreArray(span(read_buffer, data_size))); + ASSERT_EQ( + memcmp( + span(expect_buffer).last(data_size).data(), read_buffer, data_size), + 0); + + read_size = 500U; + ASSERT_EQ(ring.PeekFrontWithPreamble(read_buffer, &read_size), Status::OK); + ASSERT_EQ(read_size, single_entry_total_size); + ASSERT_EQ(ring.PopFront(), Status::OK); + + if (user_data) { + expect_buffer[0] = byte(i); + } + + // ASSERT_THAT(span(expect_buffer), + // testing::ElementsAreArray(span(read_buffer))); + ASSERT_EQ(memcmp(expect_buffer, read_buffer, single_entry_total_size), 0); + } +} + +TEST(PrefixedEntryRingBuffer, SingleEntryWriteReadNoUserData) { + SingleEntryWriteReadTest(false); +} + +TEST(PrefixedEntryRingBuffer, SingleEntryWriteReadYesUserData) { + SingleEntryWriteReadTest(true); +} + +constexpr size_t kOuterCycles = 5000u; +constexpr size_t kCountingUpMaxExpectedEntries = + single_entry_test_buffer_size / single_entry_total_size; + +// Write data that is filled with a byte value that increments each write. Write +// many times without read/pop and then check to make sure correct contents are +// in the ring buffer. +template <bool user_data> +void CountingUpWriteReadTest() { + PrefixedEntryRingBuffer ring(user_data); + byte test_buffer[single_entry_test_buffer_size]; + + EXPECT_EQ(ring.SetBuffer(test_buffer), Status::OK); + EXPECT_EQ(ring.EntryCount(), 0u); + + constexpr size_t data_size = sizeof(single_entry_data) - (user_data ? 1 : 0); + + for (size_t i = 0; i < kOuterCycles; i++) { + size_t seed = i; + + byte write_buffer[data_size]; + + size_t j; + for (j = 0; j < kSingleEntryCycles; j++) { + memset(write_buffer, j + seed, sizeof(write_buffer)); + + ASSERT_EQ(ring.PushBack(write_buffer), Status::OK); + + size_t expected_count = (j < kCountingUpMaxExpectedEntries) + ? j + 1 + : kCountingUpMaxExpectedEntries; + ASSERT_EQ(ring.EntryCount(), expected_count); + } + size_t final_write_j = j; + size_t fill_val = seed + final_write_j - kCountingUpMaxExpectedEntries; + + for (j = 0; j < kCountingUpMaxExpectedEntries; j++) { + byte read_buffer[sizeof(write_buffer)]; + size_t read_size; + memset(write_buffer, fill_val + j, sizeof(write_buffer)); + ASSERT_EQ(ring.PeekFront(read_buffer, &read_size), Status::OK); + + ASSERT_EQ(memcmp(write_buffer, read_buffer, data_size), 0); + + ASSERT_EQ(ring.PopFront(), Status::OK); + } + } +} + +TEST(PrefixedEntryRingBuffer, CountingUpWriteReadNoUserData) { + CountingUpWriteReadTest<false>(); +} + +TEST(PrefixedEntryRingBuffer, CountingUpWriteReadYesUserData) { + CountingUpWriteReadTest<true>(); +} + +// Create statically to prevent allocating a capture in the lambda below. +static pw::Vector<byte, single_entry_total_size> read_buffer; + +// Repeatedly write the same data, read it, and pop it, done over and over +// again. +void SingleEntryWriteReadWithSectionWriterTest(bool user_data) { + PrefixedEntryRingBuffer ring(user_data); + byte test_buffer[single_entry_test_buffer_size]; + + EXPECT_EQ(ring.SetBuffer(test_buffer), Status::OK); + + auto output = [](span<const byte> src) -> Status { + for (byte b : src) { + read_buffer.push_back(b); + } + return Status::OK; + }; + + size_t user_preamble_bytes = (user_data ? 1 : 0); + size_t data_size = sizeof(single_entry_data) - user_preamble_bytes; + size_t data_offset = single_entry_total_size - data_size; + + byte expect_buffer[single_entry_total_size] = {}; + expect_buffer[user_preamble_bytes] = byte(data_size); + memcpy(expect_buffer + data_offset, single_entry_data, data_size); + + for (size_t i = 0; i < kSingleEntryCycles; i++) { + ASSERT_EQ(ring.FrontEntryDataSizeBytes(), 0u); + ASSERT_EQ(ring.FrontEntryTotalSizeBytes(), 0u); + + ASSERT_EQ(ring.PushBack(span(single_entry_data, data_size), byte(i)), + Status::OK); + ASSERT_EQ(ring.FrontEntryDataSizeBytes(), data_size); + ASSERT_EQ(ring.FrontEntryTotalSizeBytes(), single_entry_total_size); + + read_buffer.clear(); + ASSERT_EQ(ring.PeekFront(output), Status::OK); + ASSERT_EQ(read_buffer.size(), data_size); + + ASSERT_EQ(memcmp(span(expect_buffer).last(data_size).data(), + read_buffer.data(), + data_size), + 0); + + read_buffer.clear(); + ASSERT_EQ(ring.PeekFrontWithPreamble(output), Status::OK); + ASSERT_EQ(read_buffer.size(), single_entry_total_size); + ASSERT_EQ(ring.PopFront(), Status::OK); + + if (user_data) { + expect_buffer[0] = byte(i); + } + + ASSERT_EQ( + memcmp(expect_buffer, read_buffer.data(), single_entry_total_size), 0); + } +} + +TEST(PrefixedEntryRingBuffer, SingleEntryWriteReadWithSectionWriterNoUserData) { + SingleEntryWriteReadWithSectionWriterTest(false); +} + +TEST(PrefixedEntryRingBuffer, + SingleEntryWriteReadWithSectionWriterYesUserData) { + SingleEntryWriteReadWithSectionWriterTest(true); +} + +constexpr size_t kEntrySizeBytes = 8u; +constexpr size_t kTotalEntryCount = 20u; +constexpr size_t kBufferExtraBytes = 5u; +constexpr size_t kTestBufferSize = + (kEntrySizeBytes * kTotalEntryCount) + kBufferExtraBytes; + +// Create statically to prevent allocating a capture in the lambda below. +static pw::Vector<byte, kTestBufferSize> actual_result; + +void DeringTest(bool preload) { + PrefixedEntryRingBuffer ring; + + byte test_buffer[kTestBufferSize]; + EXPECT_EQ(ring.SetBuffer(test_buffer), Status::OK); + + // Entry data is entry size - preamble (single byte in this case). + byte single_entry_data[kEntrySizeBytes - 1u]; + auto entry_data = span(single_entry_data); + size_t i; + + size_t loop_goal = preload ? 500 : 1; + + for (size_t main_loop_count = 0; main_loop_count < loop_goal; + main_loop_count++) { + if (preload) { + // Prime the ringbuffer with some junk data to get the buffer + // wrapped. + for (i = 0; i < (kTotalEntryCount * (main_loop_count % 64u)); i++) { + memset(single_entry_data, i, sizeof(single_entry_data)); + ring.PushBack(single_entry_data); + } + } + + // Build up the expected buffer and fill the ring buffer with the test data. + pw::Vector<byte, kTestBufferSize> expected_result; + for (i = 0; i < kTotalEntryCount; i++) { + // First component of the entry: the varint size. + static_assert(sizeof(single_entry_data) < 127); + expected_result.push_back(byte(sizeof(single_entry_data))); + + // Second component of the entry: the raw data. + memset(single_entry_data, 'a' + i, sizeof(single_entry_data)); + for (byte b : entry_data) { + expected_result.push_back(b); + } + + // The ring buffer internally pushes the varint size byte. + ring.PushBack(single_entry_data); + } + + // Check values before doing the dering. + EXPECT_EQ(ring.EntryCount(), kTotalEntryCount); + EXPECT_EQ(expected_result.size(), ring.TotalUsedBytes()); + + ASSERT_EQ(ring.Dering(), Status::OK); + + // Check values after doing the dering. + EXPECT_EQ(ring.EntryCount(), kTotalEntryCount); + EXPECT_EQ(expected_result.size(), ring.TotalUsedBytes()); + + // Read out the entries of the ring buffer. + actual_result.clear(); + auto output = [](span<const byte> src) -> Status { + for (byte b : src) { + actual_result.push_back(b); + } + return Status::OK; + }; + while (ring.EntryCount()) { + ASSERT_EQ(ring.PeekFrontWithPreamble(output), Status::OK); + ASSERT_EQ(ring.PopFront(), Status::OK); + } + + // Ensure the actual result out of the ring buffer matches our manually + // computed result. + EXPECT_EQ(expected_result.size(), actual_result.size()); + ASSERT_EQ(memcmp(test_buffer, actual_result.data(), actual_result.size()), + 0); + ASSERT_EQ( + memcmp( + expected_result.data(), actual_result.data(), actual_result.size()), + 0); + } +} + +TEST(PrefixedEntryRingBuffer, Dering) { DeringTest(true); } +TEST(PrefixedEntryRingBuffer, DeringNoPreload) { DeringTest(false); } + +} // namespace +} // namespace ring_buffer +} // namespace pw
diff --git a/pw_ring_buffer/public/pw_ring_buffer/prefixed_entry_ring_buffer.h b/pw_ring_buffer/public/pw_ring_buffer/prefixed_entry_ring_buffer.h new file mode 100644 index 0000000..902a310 --- /dev/null +++ b/pw_ring_buffer/public/pw_ring_buffer/prefixed_entry_ring_buffer.h
@@ -0,0 +1,179 @@ +// Copyright 2020 The Pigweed Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. +#pragma once + +#include <cstddef> + +#include "pw_span/span.h" +#include "pw_status/status.h" + +namespace pw { +namespace ring_buffer { + +// A circular ring buffer for arbitrary length data entries. Each PushBack() +// produces a buffer entry. Each entry consists of a preamble followed by an +// arbitrary length data chunk/blob. The preamble is comprised of an optional +// user preamble byte and an always present varint. The varint encodes the +// number of bytes in the data chunk/blob. +// +// The ring buffer holds the most recent entries stored in the buffer. Once +// filled to capacity, incoming entries bump out the oldest entries to make +// room. Entries are internally wrapped around as needed. +class PrefixedEntryRingBuffer { + public: + typedef Status (*ReadOutput)(span<const std::byte>); + + PrefixedEntryRingBuffer(bool user_preamble = false) + : buffer_(nullptr), + buffer_bytes_(0), + write_idx_(0), + read_idx_(0), + entry_count_(0), + user_preamble_(user_preamble) {} + + // Set the raw buffer to be used by the ring buffer. + // + // Return values: + // OK - successfully set the raw buffer. + // INVALID_ARGUMENT - Argument was nullptr, size zero, or too large. + Status SetBuffer(span<std::byte> buffer); + + // Removes all data from the ring buffer. + void Clear(); + + // Write a chunk/blob of data to the ring buffer. If available space is less + // than size of data chunk to be written then silently pop and discard oldest + // stored data chunks until space is available. + // + // Preamble argument is a caller-provided value prepended to the front of the + // entry. It is only used if user_preamble was set at class construction + // time. + // + // Return values: + // OK - Data successfully written to the ring buffer. + // INVALID_ARGUMENT - Size of data to write is zero bytes + // FAILED_PRECONDITION - Buffer not initialized. + // OUT_OF_RANGE - Size of data is greater than buffer size. + Status PushBack(span<const std::byte> data, + std::byte user_preamble_data = std::byte(0)); + + // Read the oldest stored data chunk/blob of data from the ring buffer to + // the provided destination span. The number of bytes read is written to + // bytes_read + // + // Return values: + // OK - Data successfully read from the ring buffer. + // FAILED_PRECONDITION - Buffer not initialized. + // OUT_OF_RANGE - No entries in ring buffer to read. + // RESOURCE_EXHAUSTED - Destination data span was smaller number of bytes than + // the data size of the data chunk being read. Available destination bytes + // were filled, remaining bytes of the data chunk were ignored. + Status PeekFront(span<std::byte> data, size_t* bytes_read); + + Status PeekFront(ReadOutput output); + + // Same as Read but includes the entry's preamble of optional user value and + // the varint of the data size + Status PeekFrontWithPreamble(span<std::byte> data, size_t* bytes_read); + + Status PeekFrontWithPreamble(ReadOutput output); + + // Pop and discard the oldest stored data chunk/blob of data from the ring + // buffer. + // + // Return values: + // OK - Data successfully read from the ring buffer. + // FAILED_PRECONDITION - Buffer not initialized. + // OUT_OF_RANGE - No entries in ring buffer to pop. + Status PopFront(); + + // Dering the buffer by reordering entries internally in the buffer by + // rotating to have the oldest entry is at the lowest address/index with + // newest entry at the highest address. + // + // Return values: + // OK - Buffer data successfully deringed. + // FAILED_PRECONDITION - Buffer not initialized. + Status Dering(); + + // Get the number of variable-length entries currently in the ring buffer. + // + // Return value: + // Entry count. + size_t EntryCount() { return entry_count_; } + + // Get the size in bytes of all the current entries in the ring buffer, + // including preamble and data chunk/blob. + size_t TotalUsedBytes() { return buffer_bytes_ - RawAvailableBytes(); } + + // Get the size in bytes of the next data chunk/blob, not including + // preamble, to be read. + size_t FrontEntryDataSizeBytes(); + + // Get the size in bytes of the next entry, including preamble and data + // chunk/blob, to be read. + size_t FrontEntryTotalSizeBytes(); + + private: + struct EntryInfo { + size_t preamble_bytes; + size_t data_bytes; + }; + + // Internal version of Read used by all the public interface versions. T + // should be of type ReadOutput. + template <typename T> + Status InternalRead(T read_output, bool get_preamble); + + // Get info struct with the size of the preamble and data chunk/blob for the + // next entry to be read. + EntryInfo FrontEntryInfo(); + + // Get the raw number of available bytes free in the ring buffer. This is + // not available bytes for data, since there is a variable size preamble for + // each entry. + size_t RawAvailableBytes(); + + // Do the basic write of the specified number of bytes starting at the last + // write index of the ring buffer to the destination, handing any wrap-around + // of the ring buffer. This is basic, raw operation with no safety checks. + void RawWrite(span<const std::byte> source); + + // Do the basic read of the specified number of bytes starting at the given + // index of the ring buffer to the destination, handing any wrap-around of + // the ring buffer. This is basic, raw operation with no safety checks. + void RawRead(std::byte* destination, size_t source_idx, size_t length_bytes); + + size_t IncrementIndex(size_t index, size_t count); + + std::byte* buffer_; + size_t buffer_bytes_; + + size_t write_idx_; + size_t read_idx_; + size_t entry_count_; + const bool user_preamble_; + + // Worst case size for the variable-sized preable that is prepended to + // each entry. + static constexpr size_t kMaxEntryPreambleBytes = sizeof(size_t) + 1; + + // Maximum bufer size allowed. Restricted to this to allow index aliasing to + // not overflow. + static constexpr size_t kMaxBufferBytes = + std::numeric_limits<size_t>::max() / 2; +}; + +} // namespace ring_buffer +} // namespace pw