summaryrefslogtreecommitdiffstats
path: root/mfbt/BufferList.h
diff options
context:
space:
mode:
Diffstat (limited to 'mfbt/BufferList.h')
-rw-r--r--mfbt/BufferList.h520
1 files changed, 520 insertions, 0 deletions
diff --git a/mfbt/BufferList.h b/mfbt/BufferList.h
new file mode 100644
index 000000000..26b335957
--- /dev/null
+++ b/mfbt/BufferList.h
@@ -0,0 +1,520 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* 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/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);
+
+ IterImpl iter = aIter;
+ size_t size = aSize;
+ size_t toCopy = std::min(size, aIter.RemainingInSegment());
+ MOZ_ASSERT(toCopy % kSegmentAlignment == 0);
+
+ BufferList result(0, toCopy, mStandardCapacity);
+ BufferList error(0, 0, mStandardCapacity);
+
+ // Copy the head
+ if (!result.WriteBytes(aIter.mData, toCopy)) {
+ *aSuccess = false;
+ return error;
+ }
+ iter.Advance(*this, toCopy);
+ size -= toCopy;
+
+ // Move segments to result
+ auto resultGuard = MakeScopeExit([&] {
+ *aSuccess = false;
+ result.mSegments.erase(result.mSegments.begin()+1, result.mSegments.end());
+ });
+
+ size_t movedSize = 0;
+ uintptr_t toRemoveStart = iter.mSegment;
+ uintptr_t toRemoveEnd = iter.mSegment;
+ while (!iter.Done() &&
+ !iter.HasRoomFor(size)) {
+ if (!result.mSegments.append(Segment(mSegments[iter.mSegment].mData,
+ mSegments[iter.mSegment].mSize,
+ mSegments[iter.mSegment].mCapacity))) {
+ return error;
+ }
+ movedSize += iter.RemainingInSegment();
+ size -= iter.RemainingInSegment();
+ toRemoveEnd++;
+ iter.Advance(*this, iter.RemainingInSegment());
+ }
+
+ if (size) {
+ if (!iter.HasRoomFor(size) ||
+ !result.WriteBytes(iter.Data(), size)) {
+ return error;
+ }
+ iter.Advance(*this, size);
+ }
+
+ mSegments.erase(mSegments.begin() + toRemoveStart, mSegments.begin() + toRemoveEnd);
+ mSize -= movedSize;
+ aIter.mSegment = iter.mSegment - (toRemoveEnd - toRemoveStart);
+ aIter.mData = iter.mData;
+ aIter.mDataEnd = iter.mDataEnd;
+ MOZ_ASSERT(aIter.mDataEnd == mSegments[aIter.mSegment].End());
+ result.mSize = aSize;
+
+ resultGuard.release();
+ *aSuccess = true;
+ return result;
+}
+
+} // namespace mozilla
+
+#endif /* mozilla_BufferList_h */