summaryrefslogtreecommitdiff
path: root/system/framework/BufferList.h
diff options
context:
space:
mode:
Diffstat (limited to 'system/framework/BufferList.h')
-rw-r--r--system/framework/BufferList.h567
1 files changed, 567 insertions, 0 deletions
diff --git a/system/framework/BufferList.h b/system/framework/BufferList.h
new file mode 100644
index 000000000..57e293f18
--- /dev/null
+++ b/system/framework/BufferList.h
@@ -0,0 +1,567 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_BufferList_h
+#define mozilla_BufferList_h
+
+#include <algorithm>
+#include "mozilla/AllocPolicy.h"
+#include "mozilla/Maybe.h"
+#include "mozilla/Move.h"
+#include "mozilla/ScopeExit.h"
+#include "mozilla/Types.h"
+#include "mozilla/TypeTraits.h"
+#include "mozilla/Vector.h"
+#include <string.h>
+
+// Undo potential #include <windows.h> damage to be able to use std::min.
+#undef min
+
+// BufferList represents a sequence of buffers of data. A BufferList can choose
+// to own its buffers or not. The class handles writing to the buffers,
+// iterating over them, and reading data out. Unlike SegmentedVector, the
+// buffers may be of unequal size. Like SegmentedVector, BufferList is a nice
+// way to avoid large contiguous allocations (which can trigger OOMs).
+
+namespace mozilla {
+
+template<typename AllocPolicy>
+class BufferList : private AllocPolicy
+{
+ // Each buffer in a BufferList has a size and a capacity. The first mSize
+ // bytes are initialized and the remaining |mCapacity - mSize| bytes are free.
+ struct Segment
+ {
+ char* mData;
+ size_t mSize;
+ size_t mCapacity;
+
+ Segment(char* aData, size_t aSize, size_t aCapacity)
+ : mData(aData),
+ mSize(aSize),
+ mCapacity(aCapacity)
+ {
+ }
+
+ Segment(const Segment&) = delete;
+ Segment& operator=(const Segment&) = delete;
+
+ Segment(Segment&&) = default;
+ Segment& operator=(Segment&&) = default;
+
+ char* Start() const { return mData; }
+ char* End() const { return mData + mSize; }
+ };
+
+ template<typename OtherAllocPolicy>
+ friend class BufferList;
+
+ public:
+ // For the convenience of callers, all segments are required to be a multiple
+ // of 8 bytes in capacity. Also, every buffer except the last one is required
+ // to be full (i.e., size == capacity). Therefore, a byte at offset N within
+ // the BufferList and stored in memory at an address A will satisfy
+ // (N % Align == A % Align) if Align == 2, 4, or 8.
+ static const size_t kSegmentAlignment = 8;
+
+ // Allocate a BufferList. The BufferList will free all its buffers when it is
+ // destroyed. An initial buffer of size aInitialSize and capacity
+ // aInitialCapacity is allocated automatically. This data will be contiguous
+ // an can be accessed via |Start()|. Subsequent buffers will be allocated with
+ // capacity aStandardCapacity.
+ BufferList(size_t aInitialSize,
+ size_t aInitialCapacity,
+ size_t aStandardCapacity,
+ AllocPolicy aAP = AllocPolicy())
+ : AllocPolicy(aAP),
+ mOwning(true),
+ mSegments(aAP),
+ mSize(0),
+ mStandardCapacity(aStandardCapacity)
+ {
+ MOZ_ASSERT(aInitialCapacity % kSegmentAlignment == 0);
+ MOZ_ASSERT(aStandardCapacity % kSegmentAlignment == 0);
+
+ if (aInitialCapacity) {
+ AllocateSegment(aInitialSize, aInitialCapacity);
+ }
+ }
+
+ BufferList(const BufferList& aOther) = delete;
+
+ BufferList(BufferList&& aOther)
+ : mOwning(aOther.mOwning),
+ mSegments(Move(aOther.mSegments)),
+ mSize(aOther.mSize),
+ mStandardCapacity(aOther.mStandardCapacity)
+ {
+ aOther.mSegments.clear();
+ aOther.mSize = 0;
+ }
+
+ BufferList& operator=(const BufferList& aOther) = delete;
+
+ BufferList& operator=(BufferList&& aOther)
+ {
+ Clear();
+
+ mOwning = aOther.mOwning;
+ mSegments = Move(aOther.mSegments);
+ mSize = aOther.mSize;
+ aOther.mSegments.clear();
+ aOther.mSize = 0;
+ return *this;
+ }
+
+ ~BufferList() { Clear(); }
+
+ // Returns the sum of the sizes of all the buffers.
+ size_t Size() const { return mSize; }
+
+ void Clear()
+ {
+ if (mOwning) {
+ for (Segment& segment : mSegments) {
+ this->free_(segment.mData);
+ }
+ }
+ mSegments.clear();
+
+ mSize = 0;
+ }
+
+ // Iterates over bytes in the segments. You can advance it by as many bytes as
+ // you choose.
+ class IterImpl
+ {
+ // Invariants:
+ // (0) mSegment <= bufferList.mSegments.size()
+ // (1) mData <= mDataEnd
+ // (2) If mSegment is not the last segment, mData < mDataEnd
+ uintptr_t mSegment;
+ char* mData;
+ char* mDataEnd;
+
+ friend class BufferList;
+
+ public:
+ explicit IterImpl(const BufferList& aBuffers)
+ : mSegment(0),
+ mData(nullptr),
+ mDataEnd(nullptr)
+ {
+ if (!aBuffers.mSegments.empty()) {
+ mData = aBuffers.mSegments[0].Start();
+ mDataEnd = aBuffers.mSegments[0].End();
+ }
+ }
+
+ // Returns a pointer to the raw data. It is valid to access up to
+ // RemainingInSegment bytes of this buffer.
+ char* Data() const
+ {
+ MOZ_RELEASE_ASSERT(!Done());
+ return mData;
+ }
+
+ // Returns true if the memory in the range [Data(), Data() + aBytes) is all
+ // part of one contiguous buffer.
+ bool HasRoomFor(size_t aBytes) const
+ {
+ MOZ_RELEASE_ASSERT(mData <= mDataEnd);
+ return size_t(mDataEnd - mData) >= aBytes;
+ }
+
+ // Returns the maximum value aBytes for which HasRoomFor(aBytes) will be
+ // true.
+ size_t RemainingInSegment() const
+ {
+ MOZ_RELEASE_ASSERT(mData <= mDataEnd);
+ return mDataEnd - mData;
+ }
+
+ // Advances the iterator by aBytes bytes. aBytes must be less than
+ // RemainingInSegment(). If advancing by aBytes takes the iterator to the
+ // end of a buffer, it will be moved to the beginning of the next buffer
+ // unless it is the last buffer.
+ void Advance(const BufferList& aBuffers, size_t aBytes)
+ {
+ const Segment& segment = aBuffers.mSegments[mSegment];
+ MOZ_RELEASE_ASSERT(segment.Start() <= mData);
+ MOZ_RELEASE_ASSERT(mData <= mDataEnd);
+ MOZ_RELEASE_ASSERT(mDataEnd == segment.End());
+
+ MOZ_RELEASE_ASSERT(HasRoomFor(aBytes));
+ mData += aBytes;
+
+ if (mData == mDataEnd && mSegment + 1 < aBuffers.mSegments.length()) {
+ mSegment++;
+ const Segment& nextSegment = aBuffers.mSegments[mSegment];
+ mData = nextSegment.Start();
+ mDataEnd = nextSegment.End();
+ MOZ_RELEASE_ASSERT(mData < mDataEnd);
+ }
+ }
+
+ // Advance the iterator by aBytes, possibly crossing segments. This function
+ // returns false if it runs out of buffers to advance through. Otherwise it
+ // returns true.
+ bool AdvanceAcrossSegments(const BufferList& aBuffers, size_t aBytes)
+ {
+ size_t bytes = aBytes;
+ while (bytes) {
+ size_t toAdvance = std::min(bytes, RemainingInSegment());
+ if (!toAdvance) {
+ return false;
+ }
+ Advance(aBuffers, toAdvance);
+ bytes -= toAdvance;
+ }
+ return true;
+ }
+
+ // Returns true when the iterator reaches the end of the BufferList.
+ bool Done() const
+ {
+ return mData == mDataEnd;
+ }
+
+ private:
+
+ // Count the bytes we would need to advance in order to reach aTarget.
+ size_t BytesUntil(const BufferList& aBuffers, const IterImpl& aTarget) const {
+ size_t offset = 0;
+
+ MOZ_ASSERT(aTarget.IsIn(aBuffers));
+
+ char* data = mData;
+ for (uintptr_t segment = mSegment; segment < aTarget.mSegment; segment++) {
+ offset += aBuffers.mSegments[segment].End() - data;
+ data = aBuffers.mSegments[segment].mData;
+ }
+
+ MOZ_RELEASE_ASSERT(IsIn(aBuffers));
+ MOZ_RELEASE_ASSERT(aTarget.mData >= data);
+
+ offset += aTarget.mData - data;
+ return offset;
+ }
+
+ bool IsIn(const BufferList& aBuffers) const {
+ return mSegment < aBuffers.mSegments.length() &&
+ mData >= aBuffers.mSegments[mSegment].mData &&
+ mData < aBuffers.mSegments[mSegment].End();
+ }
+ };
+
+ // Special convenience method that returns Iter().Data().
+ char* Start() { return mSegments[0].mData; }
+ const char* Start() const { return mSegments[0].mData; }
+
+ IterImpl Iter() const { return IterImpl(*this); }
+
+ // Copies aSize bytes from aData into the BufferList. The storage for these
+ // bytes may be split across multiple buffers. Size() is increased by aSize.
+ inline bool WriteBytes(const char* aData, size_t aSize);
+
+ // Copies possibly non-contiguous byte range starting at aIter into
+ // aData. aIter is advanced by aSize bytes. Returns false if it runs out of
+ // data before aSize.
+ inline bool ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const;
+
+ // Return a new BufferList that shares storage with this BufferList. The new
+ // BufferList is read-only. It allows iteration over aSize bytes starting at
+ // aIter. Borrow can fail, in which case *aSuccess will be false upon
+ // return. The borrowed BufferList can use a different AllocPolicy than the
+ // original one. However, it is not responsible for freeing buffers, so the
+ // AllocPolicy is only used for the buffer vector.
+ template<typename BorrowingAllocPolicy>
+ BufferList<BorrowingAllocPolicy> Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
+ BorrowingAllocPolicy aAP = BorrowingAllocPolicy()) const;
+
+ // Return a new BufferList and move storage from this BufferList to it. The
+ // new BufferList owns the buffers. Move can fail, in which case *aSuccess
+ // will be false upon return. The new BufferList can use a different
+ // AllocPolicy than the original one. The new OtherAllocPolicy is responsible
+ // for freeing buffers, so the OtherAllocPolicy must use freeing method
+ // compatible to the original one.
+ template<typename OtherAllocPolicy>
+ BufferList<OtherAllocPolicy> MoveFallible(bool* aSuccess, OtherAllocPolicy aAP = OtherAllocPolicy());
+
+ // Return a new BufferList that adopts the byte range starting at Iter so that
+ // range [aIter, aIter + aSize) is transplanted to the returned BufferList.
+ // Contents of the buffer before aIter + aSize is left undefined.
+ // Extract can fail, in which case *aSuccess will be false upon return. The
+ // moved buffers are erased from the original BufferList. In case of extract
+ // fails, the original BufferList is intact. All other iterators except aIter
+ // are invalidated.
+ // This method requires aIter and aSize to be 8-byte aligned.
+ BufferList Extract(IterImpl& aIter, size_t aSize, bool* aSuccess);
+
+ // Return the number of bytes from 'start' to 'end', two iterators within
+ // this BufferList.
+ size_t RangeLength(const IterImpl& start, const IterImpl& end) const {
+ MOZ_ASSERT(start.IsIn(*this) && end.IsIn(*this));
+ return start.BytesUntil(*this, end);
+ }
+
+private:
+ explicit BufferList(AllocPolicy aAP)
+ : AllocPolicy(aAP),
+ mOwning(false),
+ mSize(0),
+ mStandardCapacity(0)
+ {
+ }
+
+ void* AllocateSegment(size_t aSize, size_t aCapacity)
+ {
+ MOZ_RELEASE_ASSERT(mOwning);
+
+ char* data = this->template pod_malloc<char>(aCapacity);
+ if (!data) {
+ return nullptr;
+ }
+ if (!mSegments.append(Segment(data, aSize, aCapacity))) {
+ this->free_(data);
+ return nullptr;
+ }
+ mSize += aSize;
+ return data;
+ }
+
+ bool mOwning;
+ Vector<Segment, 1, AllocPolicy> mSegments;
+ size_t mSize;
+ size_t mStandardCapacity;
+};
+
+template<typename AllocPolicy>
+bool
+BufferList<AllocPolicy>::WriteBytes(const char* aData, size_t aSize)
+{
+ MOZ_RELEASE_ASSERT(mOwning);
+ MOZ_RELEASE_ASSERT(mStandardCapacity);
+
+ size_t copied = 0;
+ size_t remaining = aSize;
+
+ if (!mSegments.empty()) {
+ Segment& lastSegment = mSegments.back();
+
+ size_t toCopy = std::min(aSize, lastSegment.mCapacity - lastSegment.mSize);
+ memcpy(lastSegment.mData + lastSegment.mSize, aData, toCopy);
+ lastSegment.mSize += toCopy;
+ mSize += toCopy;
+
+ copied += toCopy;
+ remaining -= toCopy;
+ }
+
+ while (remaining) {
+ size_t toCopy = std::min(remaining, mStandardCapacity);
+
+ void* data = AllocateSegment(toCopy, mStandardCapacity);
+ if (!data) {
+ return false;
+ }
+ memcpy(data, aData + copied, toCopy);
+
+ copied += toCopy;
+ remaining -= toCopy;
+ }
+
+ return true;
+}
+
+template<typename AllocPolicy>
+bool
+BufferList<AllocPolicy>::ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const
+{
+ size_t copied = 0;
+ size_t remaining = aSize;
+ while (remaining) {
+ size_t toCopy = std::min(aIter.RemainingInSegment(), remaining);
+ if (!toCopy) {
+ // We've run out of data in the last segment.
+ return false;
+ }
+ memcpy(aData + copied, aIter.Data(), toCopy);
+ copied += toCopy;
+ remaining -= toCopy;
+
+ aIter.Advance(*this, toCopy);
+ }
+
+ return true;
+}
+
+template<typename AllocPolicy> template<typename BorrowingAllocPolicy>
+BufferList<BorrowingAllocPolicy>
+BufferList<AllocPolicy>::Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
+ BorrowingAllocPolicy aAP) const
+{
+ BufferList<BorrowingAllocPolicy> result(aAP);
+
+ size_t size = aSize;
+ while (size) {
+ size_t toAdvance = std::min(size, aIter.RemainingInSegment());
+
+ if (!toAdvance || !result.mSegments.append(typename BufferList<BorrowingAllocPolicy>::Segment(aIter.mData, toAdvance, toAdvance))) {
+ *aSuccess = false;
+ return result;
+ }
+ aIter.Advance(*this, toAdvance);
+ size -= toAdvance;
+ }
+
+ result.mSize = aSize;
+ *aSuccess = true;
+ return result;
+}
+
+template<typename AllocPolicy> template<typename OtherAllocPolicy>
+BufferList<OtherAllocPolicy>
+BufferList<AllocPolicy>::MoveFallible(bool* aSuccess, OtherAllocPolicy aAP)
+{
+ BufferList<OtherAllocPolicy> result(0, 0, mStandardCapacity, aAP);
+
+ IterImpl iter = Iter();
+ while (!iter.Done()) {
+ size_t toAdvance = iter.RemainingInSegment();
+
+ if (!toAdvance || !result.mSegments.append(typename BufferList<OtherAllocPolicy>::Segment(iter.mData, toAdvance, toAdvance))) {
+ *aSuccess = false;
+ result.mSegments.clear();
+ return result;
+ }
+ iter.Advance(*this, toAdvance);
+ }
+
+ result.mSize = mSize;
+ mSegments.clear();
+ mSize = 0;
+ *aSuccess = true;
+ return result;
+}
+
+template<typename AllocPolicy>
+BufferList<AllocPolicy>
+BufferList<AllocPolicy>::Extract(IterImpl& aIter, size_t aSize, bool* aSuccess)
+{
+ MOZ_RELEASE_ASSERT(aSize);
+ MOZ_RELEASE_ASSERT(mOwning);
+ MOZ_ASSERT(aSize % kSegmentAlignment == 0);
+ MOZ_ASSERT(intptr_t(aIter.mData) % kSegmentAlignment == 0);
+
+ auto failure = [this, aSuccess]() {
+ *aSuccess = false;
+ return BufferList(0, 0, mStandardCapacity);
+ };
+
+ // Number of segments we'll need to copy data from to satisfy the request.
+ size_t segmentsNeeded = 0;
+ // If this is None then the last segment is a full segment, otherwise we need
+ // to copy this many bytes.
+ Maybe<size_t> lastSegmentSize;
+ {
+ // Copy of the iterator to walk the BufferList and see how many segments we
+ // need to copy.
+ IterImpl iter = aIter;
+ size_t remaining = aSize;
+ while (!iter.Done() && remaining &&
+ remaining >= iter.RemainingInSegment()) {
+ remaining -= iter.RemainingInSegment();
+ iter.Advance(*this, iter.RemainingInSegment());
+ segmentsNeeded++;
+ }
+
+ if (remaining) {
+ if (iter.Done()) {
+ // We reached the end of the BufferList and there wasn't enough data to
+ // satisfy the request.
+ return failure();
+ }
+ lastSegmentSize.emplace(remaining);
+ // The last block also counts as a segment. This makes the conditionals
+ // on segmentsNeeded work in the rest of the function.
+ segmentsNeeded++;
+ }
+ }
+
+ BufferList result(0, 0, mStandardCapacity);
+ if (!result.mSegments.reserve(segmentsNeeded + lastSegmentSize.isSome())) {
+ return failure();
+ }
+
+ // Copy the first segment, it's special because we can't just steal the
+ // entire Segment struct from this->mSegments.
+ size_t firstSegmentSize = std::min(aSize, aIter.RemainingInSegment());
+ if (!result.WriteBytes(aIter.Data(), firstSegmentSize)) {
+ return failure();
+ }
+ aIter.Advance(*this, firstSegmentSize);
+ segmentsNeeded--;
+
+ // The entirety of the request wasn't in the first segment, now copy the
+ // rest.
+ if (segmentsNeeded) {
+ char* finalSegment = nullptr;
+ // Pre-allocate the final segment so that if this fails, we return before
+ // we delete the elements from |this->mSegments|.
+ if (lastSegmentSize.isSome()) {
+ MOZ_RELEASE_ASSERT(mStandardCapacity >= *lastSegmentSize);
+ finalSegment = this->template pod_malloc<char>(mStandardCapacity);
+ if (!finalSegment) {
+ return failure();
+ }
+ }
+
+ size_t copyStart = aIter.mSegment;
+ // Copy segments from this over to the result and remove them from our
+ // storage. Not needed if the only segment we need to copy is the last
+ // partial one.
+ size_t segmentsToCopy = segmentsNeeded - lastSegmentSize.isSome();
+ for (size_t i = 0; i < segmentsToCopy; ++i) {
+ result.mSegments.infallibleAppend(
+ Segment(mSegments[aIter.mSegment].mData,
+ mSegments[aIter.mSegment].mSize,
+ mSegments[aIter.mSegment].mCapacity));
+ aIter.Advance(*this, aIter.RemainingInSegment());
+ }
+ // Due to the way IterImpl works, there are two cases here: (1) if we've
+ // consumed the entirety of the BufferList, then the iterator is pointed at
+ // the end of the final segment, (2) otherwise it is pointed at the start
+ // of the next segment. We want to verify that we really consumed all
+ // |segmentsToCopy| segments.
+ MOZ_RELEASE_ASSERT(
+ (aIter.mSegment == copyStart + segmentsToCopy) ||
+ (aIter.Done() && aIter.mSegment == copyStart + segmentsToCopy - 1));
+ mSegments.erase(mSegments.begin() + copyStart,
+ mSegments.begin() + copyStart + segmentsToCopy);
+
+ // Reset the iter's position for what we just deleted.
+ aIter.mSegment -= segmentsToCopy;
+
+ if (lastSegmentSize.isSome()) {
+ // We called reserve() on result.mSegments so infallibleAppend is safe.
+ result.mSegments.infallibleAppend(
+ Segment(finalSegment, 0, mStandardCapacity));
+ bool r = result.WriteBytes(aIter.Data(), *lastSegmentSize);
+ MOZ_RELEASE_ASSERT(r);
+ aIter.Advance(*this, *lastSegmentSize);
+ }
+ }
+
+ mSize -= aSize;
+ result.mSize = aSize;
+
+ *aSuccess = true;
+ return result;
+}
+
+} // namespace mozilla
+
+#endif /* mozilla_BufferList_h */
generated by cgit v1.2.3 (git 2.26.2) at 2024-09-21 15:30:41 +0000