1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef mozilla_BufferList_h
8 #define mozilla_BufferList_h
15 #include "mozilla/Assertions.h"
16 #include "mozilla/Attributes.h"
17 #include "mozilla/Maybe.h"
18 #include "mozilla/MemoryReporting.h"
19 #include "mozilla/Vector.h"
21 // BufferList represents a sequence of buffers of data. A BufferList can choose
22 // to own its buffers or not. The class handles writing to the buffers,
23 // iterating over them, and reading data out. Unlike SegmentedVector, the
24 // buffers may be of unequal size. Like SegmentedVector, BufferList is a nice
25 // way to avoid large contiguous allocations (which can trigger OOMs).
27 class InfallibleAllocPolicy
;
31 template <typename AllocPolicy
>
32 class BufferList
: private AllocPolicy
{
33 // Each buffer in a BufferList has a size and a capacity. The first mSize
34 // bytes are initialized and the remaining |mCapacity - mSize| bytes are free.
40 Segment(char* aData
, size_t aSize
, size_t aCapacity
)
41 : mData(aData
), mSize(aSize
), mCapacity(aCapacity
) {}
43 Segment(const Segment
&) = delete;
44 Segment
& operator=(const Segment
&) = delete;
46 Segment(Segment
&&) = default;
47 Segment
& operator=(Segment
&&) = default;
49 char* Start() const { return mData
; }
50 char* End() const { return mData
+ mSize
; }
53 template <typename OtherAllocPolicy
>
54 friend class BufferList
;
57 // For the convenience of callers, all segments are required to be a multiple
58 // of 8 bytes in capacity. Also, every buffer except the last one is required
59 // to be full (i.e., size == capacity). Therefore, a byte at offset N within
60 // the BufferList and stored in memory at an address A will satisfy
61 // (N % Align == A % Align) if Align == 2, 4, or 8.
62 static const size_t kSegmentAlignment
= 8;
64 // Allocate a BufferList. The BufferList will free all its buffers when it is
65 // destroyed. If an infallible allocator is used, an initial buffer of size
66 // aInitialSize and capacity aInitialCapacity is allocated automatically. This
67 // data will be contiguous and can be accessed via |Start()|. If a fallible
68 // alloc policy is used, aInitialSize must be 0, and the fallible |Init()|
69 // method may be called instead. Subsequent buffers will be allocated with
70 // capacity aStandardCapacity.
71 BufferList(size_t aInitialSize
, size_t aInitialCapacity
,
72 size_t aStandardCapacity
, AllocPolicy aAP
= AllocPolicy())
77 mStandardCapacity(aStandardCapacity
) {
78 MOZ_ASSERT(aInitialCapacity
% kSegmentAlignment
== 0);
79 MOZ_ASSERT(aStandardCapacity
% kSegmentAlignment
== 0);
81 if (aInitialCapacity
) {
82 MOZ_ASSERT((aInitialSize
== 0 ||
83 std::is_same_v
<AllocPolicy
, InfallibleAllocPolicy
>),
84 "BufferList may only be constructed with an initial size when "
85 "using an infallible alloc policy");
87 AllocateSegment(aInitialSize
, aInitialCapacity
);
91 BufferList(const BufferList
& aOther
) = delete;
93 BufferList(BufferList
&& aOther
)
94 : mOwning(aOther
.mOwning
),
95 mSegments(std::move(aOther
.mSegments
)),
97 mStandardCapacity(aOther
.mStandardCapacity
) {
98 aOther
.mSegments
.clear();
102 BufferList
& operator=(const BufferList
& aOther
) = delete;
104 BufferList
& operator=(BufferList
&& aOther
) {
107 mOwning
= aOther
.mOwning
;
108 mSegments
= std::move(aOther
.mSegments
);
109 mSize
= aOther
.mSize
;
110 aOther
.mSegments
.clear();
115 ~BufferList() { Clear(); }
117 // Initializes the BufferList with a segment of the given size and capacity.
118 // May only be called once, before any segments have been allocated.
119 bool Init(size_t aInitialSize
, size_t aInitialCapacity
) {
120 MOZ_ASSERT(mSegments
.empty());
121 MOZ_ASSERT(aInitialCapacity
!= 0);
122 MOZ_ASSERT(aInitialCapacity
% kSegmentAlignment
== 0);
124 return AllocateSegment(aInitialSize
, aInitialCapacity
);
127 bool CopyFrom(const BufferList
& aOther
) {
132 // We don't make an exact copy of aOther. Instead, create a single segment
133 // with enough space to hold all data in aOther.
134 if (!Init(aOther
.mSize
, (aOther
.mSize
+ kSegmentAlignment
- 1) &
135 ~(kSegmentAlignment
- 1))) {
140 for (const Segment
& segment
: aOther
.mSegments
) {
141 memcpy(Start() + offset
, segment
.mData
, segment
.mSize
);
142 offset
+= segment
.mSize
;
144 MOZ_ASSERT(offset
== mSize
);
149 // Returns the sum of the sizes of all the buffers.
150 size_t Size() const { return mSize
; }
152 size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) {
153 size_t size
= mSegments
.sizeOfExcludingThis(aMallocSizeOf
);
154 for (Segment
& segment
: mSegments
) {
155 size
+= aMallocSizeOf(segment
.Start());
162 for (Segment
& segment
: mSegments
) {
163 this->free_(segment
.mData
, segment
.mCapacity
);
171 // Iterates over bytes in the segments. You can advance it by as many bytes as
175 // (0) mSegment <= bufferList.mSegments.length()
176 // (1) mData <= mDataEnd
177 // (2) If mSegment is not the last segment, mData < mDataEnd
178 uintptr_t mSegment
{0};
179 char* mData
{nullptr};
180 char* mDataEnd
{nullptr};
181 size_t mAbsoluteOffset
{0};
183 friend class BufferList
;
186 explicit IterImpl(const BufferList
& aBuffers
) {
187 if (!aBuffers
.mSegments
.empty()) {
188 mData
= aBuffers
.mSegments
[0].Start();
189 mDataEnd
= aBuffers
.mSegments
[0].End();
193 // Returns a pointer to the raw data. It is valid to access up to
194 // RemainingInSegment bytes of this buffer.
196 MOZ_RELEASE_ASSERT(!Done());
200 bool operator==(const IterImpl
& other
) const {
201 return mAbsoluteOffset
== other
.mAbsoluteOffset
;
203 bool operator!=(const IterImpl
& other
) const { return !(*this == other
); }
205 // Returns true if the memory in the range [Data(), Data() + aBytes) is all
206 // part of one contiguous buffer.
207 bool HasRoomFor(size_t aBytes
) const {
208 return RemainingInSegment() >= aBytes
;
211 // Returns the largest value aBytes for which HasRoomFor(aBytes) will be
213 size_t RemainingInSegment() const {
214 MOZ_RELEASE_ASSERT(mData
<= mDataEnd
);
215 return mDataEnd
- mData
;
218 // Returns true if there are at least aBytes entries remaining in the
219 // BufferList after this iterator.
220 bool HasBytesAvailable(const BufferList
& aBuffers
, size_t aBytes
) const {
221 return TotalBytesAvailable(aBuffers
) >= aBytes
;
224 // Returns the largest value `aBytes` for which HasBytesAvailable(aBytes)
226 size_t TotalBytesAvailable(const BufferList
& aBuffers
) const {
227 return aBuffers
.mSize
- mAbsoluteOffset
;
230 // Advances the iterator by aBytes bytes. aBytes must be less than
231 // RemainingInSegment(). If advancing by aBytes takes the iterator to the
232 // end of a buffer, it will be moved to the beginning of the next buffer
233 // unless it is the last buffer.
234 void Advance(const BufferList
& aBuffers
, size_t aBytes
) {
235 const Segment
& segment
= aBuffers
.mSegments
[mSegment
];
236 MOZ_RELEASE_ASSERT(segment
.Start() <= mData
);
237 MOZ_RELEASE_ASSERT(mData
<= mDataEnd
);
238 MOZ_RELEASE_ASSERT(mDataEnd
== segment
.End());
240 MOZ_RELEASE_ASSERT(HasRoomFor(aBytes
));
242 mAbsoluteOffset
+= aBytes
;
244 if (mData
== mDataEnd
&& mSegment
+ 1 < aBuffers
.mSegments
.length()) {
246 const Segment
& nextSegment
= aBuffers
.mSegments
[mSegment
];
247 mData
= nextSegment
.Start();
248 mDataEnd
= nextSegment
.End();
249 MOZ_RELEASE_ASSERT(mData
< mDataEnd
);
253 // Advance the iterator by aBytes, possibly crossing segments. This function
254 // returns false if it runs out of buffers to advance through. Otherwise it
256 bool AdvanceAcrossSegments(const BufferList
& aBuffers
, size_t aBytes
) {
257 // If we don't need to cross segments, we can directly use `Advance` to
258 // get to our destination.
259 if (MOZ_LIKELY(aBytes
<= RemainingInSegment())) {
260 Advance(aBuffers
, aBytes
);
264 // Check if we have enough bytes to scan this far forward.
265 if (!HasBytesAvailable(aBuffers
, aBytes
)) {
269 // Compare the distance to our target offset from the end of the
270 // BufferList to the distance from the start of our next segment.
271 // Depending on which is closer, we'll advance either forwards or
273 size_t targetOffset
= mAbsoluteOffset
+ aBytes
;
274 size_t fromEnd
= aBuffers
.mSize
- targetOffset
;
275 if (aBytes
- RemainingInSegment() < fromEnd
) {
276 // Advance through the buffer list until we reach the desired absolute
278 while (mAbsoluteOffset
< targetOffset
) {
279 Advance(aBuffers
, std::min(targetOffset
- mAbsoluteOffset
,
280 RemainingInSegment()));
282 MOZ_ASSERT(mAbsoluteOffset
== targetOffset
);
286 // Scanning starting from the end of the BufferList. We advance
287 // backwards from the final segment until we find the segment to end in.
289 // If we end on a segment boundary, make sure to place the cursor at the
290 // beginning of the next segment.
291 mSegment
= aBuffers
.mSegments
.length() - 1;
292 while (fromEnd
> aBuffers
.mSegments
[mSegment
].mSize
) {
293 fromEnd
-= aBuffers
.mSegments
[mSegment
].mSize
;
296 mDataEnd
= aBuffers
.mSegments
[mSegment
].End();
297 mData
= mDataEnd
- fromEnd
;
298 mAbsoluteOffset
= targetOffset
;
299 MOZ_ASSERT_IF(Done(), mSegment
== aBuffers
.mSegments
.length() - 1);
300 MOZ_ASSERT_IF(Done(), mAbsoluteOffset
== aBuffers
.mSize
);
304 // Returns true when the iterator reaches the end of the BufferList.
305 bool Done() const { return mData
== mDataEnd
; }
307 // The absolute offset of this iterator within the BufferList.
308 size_t AbsoluteOffset() const { return mAbsoluteOffset
; }
311 bool IsIn(const BufferList
& aBuffers
) const {
312 return mSegment
< aBuffers
.mSegments
.length() &&
313 mData
>= aBuffers
.mSegments
[mSegment
].mData
&&
314 mData
< aBuffers
.mSegments
[mSegment
].End();
318 // Special convenience method that returns Iter().Data().
320 MOZ_RELEASE_ASSERT(!mSegments
.empty());
321 return mSegments
[0].mData
;
323 const char* Start() const { return mSegments
[0].mData
; }
325 IterImpl
Iter() const { return IterImpl(*this); }
327 // Copies aSize bytes from aData into the BufferList. The storage for these
328 // bytes may be split across multiple buffers. Size() is increased by aSize.
329 [[nodiscard
]] inline bool WriteBytes(const char* aData
, size_t aSize
);
331 // Allocates a buffer of at most |aMaxBytes| bytes and, if successful, returns
332 // that buffer, and places its size in |aSize|. If unsuccessful, returns null
333 // and leaves |aSize| undefined.
334 inline char* AllocateBytes(size_t aMaxSize
, size_t* aSize
);
336 // Copies possibly non-contiguous byte range starting at aIter into
337 // aData. aIter is advanced by aSize bytes. Returns false if it runs out of
338 // data before aSize.
339 inline bool ReadBytes(IterImpl
& aIter
, char* aData
, size_t aSize
) const;
341 // Return a new BufferList that shares storage with this BufferList. The new
342 // BufferList is read-only. It allows iteration over aSize bytes starting at
343 // aIter. Borrow can fail, in which case *aSuccess will be false upon
344 // return. The borrowed BufferList can use a different AllocPolicy than the
345 // original one. However, it is not responsible for freeing buffers, so the
346 // AllocPolicy is only used for the buffer vector.
347 template <typename BorrowingAllocPolicy
>
348 BufferList
<BorrowingAllocPolicy
> Borrow(
349 IterImpl
& aIter
, size_t aSize
, bool* aSuccess
,
350 BorrowingAllocPolicy aAP
= BorrowingAllocPolicy()) const;
352 // Return a new BufferList and move storage from this BufferList to it. The
353 // new BufferList owns the buffers. Move can fail, in which case *aSuccess
354 // will be false upon return. The new BufferList can use a different
355 // AllocPolicy than the original one. The new OtherAllocPolicy is responsible
356 // for freeing buffers, so the OtherAllocPolicy must use freeing method
357 // compatible to the original one.
358 template <typename OtherAllocPolicy
>
359 BufferList
<OtherAllocPolicy
> MoveFallible(
360 bool* aSuccess
, OtherAllocPolicy aAP
= OtherAllocPolicy());
362 // Return the number of bytes from 'start' to 'end', two iterators within
364 size_t RangeLength(const IterImpl
& start
, const IterImpl
& end
) const {
365 MOZ_ASSERT(start
.IsIn(*this) && end
.IsIn(*this));
366 return end
.mAbsoluteOffset
- start
.mAbsoluteOffset
;
369 // This takes ownership of the data
370 [[nodiscard
]] bool WriteBytesZeroCopy(char* aData
, size_t aSize
,
373 MOZ_ASSERT(aSize
<= aCapacity
);
375 // Don't create zero-length segments; that can cause problems for
376 // consumers of the data (bug 1595453).
378 this->free_(aData
, aCapacity
);
382 if (!mSegments
.append(Segment(aData
, aSize
, aCapacity
))) {
383 this->free_(aData
, aCapacity
);
390 // Truncate this BufferList at the given iterator location, discarding all
391 // data after this point. After this call, all other iterators will be
392 // invalidated, and the passed-in iterator will be "Done".
394 // Returns the number of bytes discarded by this truncation.
395 size_t Truncate(IterImpl
& aIter
);
398 explicit BufferList(AllocPolicy aAP
)
399 : AllocPolicy(aAP
), mOwning(false), mSize(0), mStandardCapacity(0) {}
401 char* AllocateSegment(size_t aSize
, size_t aCapacity
) {
402 MOZ_RELEASE_ASSERT(mOwning
);
403 MOZ_ASSERT(aCapacity
!= 0);
404 MOZ_ASSERT(aSize
<= aCapacity
);
406 char* data
= this->template pod_malloc
<char>(aCapacity
);
410 if (!mSegments
.append(Segment(data
, aSize
, aCapacity
))) {
411 this->free_(data
, aCapacity
);
418 void AssertConsistentSize() const {
421 for (const auto& segment
: mSegments
) {
422 realSize
+= segment
.mSize
;
424 MOZ_ASSERT(realSize
== mSize
, "cached size value is inconsistent!");
429 Vector
<Segment
, 1, AllocPolicy
> mSegments
;
431 size_t mStandardCapacity
;
434 template <typename AllocPolicy
>
435 [[nodiscard
]] bool BufferList
<AllocPolicy
>::WriteBytes(const char* aData
,
437 MOZ_RELEASE_ASSERT(mOwning
);
438 MOZ_RELEASE_ASSERT(mStandardCapacity
);
441 while (copied
< aSize
) {
443 char* data
= AllocateBytes(aSize
- copied
, &toCopy
);
447 memcpy(data
, aData
+ copied
, toCopy
);
454 template <typename AllocPolicy
>
455 char* BufferList
<AllocPolicy
>::AllocateBytes(size_t aMaxSize
, size_t* aSize
) {
456 MOZ_RELEASE_ASSERT(mOwning
);
457 MOZ_RELEASE_ASSERT(mStandardCapacity
);
459 if (!mSegments
.empty()) {
460 Segment
& lastSegment
= mSegments
.back();
462 size_t capacity
= lastSegment
.mCapacity
- lastSegment
.mSize
;
464 size_t size
= std::min(aMaxSize
, capacity
);
465 char* data
= lastSegment
.mData
+ lastSegment
.mSize
;
467 lastSegment
.mSize
+= size
;
475 size_t size
= std::min(aMaxSize
, mStandardCapacity
);
476 char* data
= AllocateSegment(size
, mStandardCapacity
);
483 template <typename AllocPolicy
>
484 bool BufferList
<AllocPolicy
>::ReadBytes(IterImpl
& aIter
, char* aData
,
485 size_t aSize
) const {
487 size_t remaining
= aSize
;
489 size_t toCopy
= std::min(aIter
.RemainingInSegment(), remaining
);
491 // We've run out of data in the last segment.
494 memcpy(aData
+ copied
, aIter
.Data(), toCopy
);
498 aIter
.Advance(*this, toCopy
);
504 template <typename AllocPolicy
>
505 template <typename BorrowingAllocPolicy
>
506 BufferList
<BorrowingAllocPolicy
> BufferList
<AllocPolicy
>::Borrow(
507 IterImpl
& aIter
, size_t aSize
, bool* aSuccess
,
508 BorrowingAllocPolicy aAP
) const {
509 BufferList
<BorrowingAllocPolicy
> result(aAP
);
513 size_t toAdvance
= std::min(size
, aIter
.RemainingInSegment());
515 if (!toAdvance
|| !result
.mSegments
.append(
516 typename BufferList
<BorrowingAllocPolicy
>::Segment(
517 aIter
.mData
, toAdvance
, toAdvance
))) {
521 aIter
.Advance(*this, toAdvance
);
525 result
.mSize
= aSize
;
530 template <typename AllocPolicy
>
531 template <typename OtherAllocPolicy
>
532 BufferList
<OtherAllocPolicy
> BufferList
<AllocPolicy
>::MoveFallible(
533 bool* aSuccess
, OtherAllocPolicy aAP
) {
534 BufferList
<OtherAllocPolicy
> result(0, 0, mStandardCapacity
, aAP
);
536 IterImpl iter
= Iter();
537 while (!iter
.Done()) {
538 size_t toAdvance
= iter
.RemainingInSegment();
541 !result
.mSegments
.append(typename BufferList
<OtherAllocPolicy
>::Segment(
542 iter
.mData
, toAdvance
, toAdvance
))) {
544 result
.mSegments
.clear();
547 iter
.Advance(*this, toAdvance
);
550 result
.mSize
= mSize
;
557 template <typename AllocPolicy
>
558 size_t BufferList
<AllocPolicy
>::Truncate(IterImpl
& aIter
) {
559 MOZ_ASSERT(aIter
.IsIn(*this) || aIter
.Done());
564 size_t prevSize
= mSize
;
566 // Remove any segments after the iterator's current segment.
567 while (mSegments
.length() > aIter
.mSegment
+ 1) {
568 Segment
& toFree
= mSegments
.back();
569 mSize
-= toFree
.mSize
;
571 this->free_(toFree
.mData
, toFree
.mCapacity
);
576 // The last segment is now aIter's current segment. Truncate or remove it.
577 Segment
& seg
= mSegments
.back();
578 MOZ_ASSERT(aIter
.mDataEnd
== seg
.End());
579 mSize
-= aIter
.RemainingInSegment();
580 seg
.mSize
-= aIter
.RemainingInSegment();
583 this->free_(seg
.mData
, seg
.mCapacity
);
588 // Correct `aIter` to point to the new end of the BufferList.
589 if (mSegments
.empty()) {
590 MOZ_ASSERT(mSize
== 0);
592 aIter
.mData
= aIter
.mDataEnd
= nullptr;
594 aIter
.mSegment
= mSegments
.length() - 1;
595 aIter
.mData
= aIter
.mDataEnd
= mSegments
.back().End();
597 MOZ_ASSERT(aIter
.Done());
599 AssertConsistentSize();
600 return prevSize
- mSize
;
603 } // namespace mozilla
605 #endif /* mozilla_BufferList_h */