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
11 #include "mozilla/AllocPolicy.h"
12 #include "mozilla/Maybe.h"
13 #include "mozilla/MemoryReporting.h"
14 #include "mozilla/Move.h"
15 #include "mozilla/ScopeExit.h"
16 #include "mozilla/Types.h"
17 #include "mozilla/TypeTraits.h"
18 #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 IsSame
<AllocPolicy
, InfallibleAllocPolicy
>::value
),
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
182 friend class BufferList
;
185 explicit IterImpl(const BufferList
& aBuffers
)
186 : mSegment(0), mData(nullptr), mDataEnd(nullptr) {
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 // Returns true if the memory in the range [Data(), Data() + aBytes) is all
201 // part of one contiguous buffer.
202 bool HasRoomFor(size_t aBytes
) const {
203 MOZ_RELEASE_ASSERT(mData
<= mDataEnd
);
204 return size_t(mDataEnd
- mData
) >= aBytes
;
207 // Returns the maximum value aBytes for which HasRoomFor(aBytes) will be
209 size_t RemainingInSegment() const {
210 MOZ_RELEASE_ASSERT(mData
<= mDataEnd
);
211 return mDataEnd
- mData
;
214 bool HasBytesAvailable(const BufferList
& aBuffers
, uint32_t aBytes
) const {
215 if (RemainingInSegment() >= aBytes
) {
218 aBytes
-= RemainingInSegment();
219 for (size_t i
= mSegment
+ 1; i
< aBuffers
.mSegments
.length(); i
++) {
220 if (aBuffers
.mSegments
[i
].mSize
>= aBytes
) {
223 aBytes
-= aBuffers
.mSegments
[i
].mSize
;
229 // Advances the iterator by aBytes bytes. aBytes must be less than
230 // RemainingInSegment(). If advancing by aBytes takes the iterator to the
231 // end of a buffer, it will be moved to the beginning of the next buffer
232 // unless it is the last buffer.
233 void Advance(const BufferList
& aBuffers
, size_t aBytes
) {
234 const Segment
& segment
= aBuffers
.mSegments
[mSegment
];
235 MOZ_RELEASE_ASSERT(segment
.Start() <= mData
);
236 MOZ_RELEASE_ASSERT(mData
<= mDataEnd
);
237 MOZ_RELEASE_ASSERT(mDataEnd
== segment
.End());
239 MOZ_RELEASE_ASSERT(HasRoomFor(aBytes
));
242 if (mData
== mDataEnd
&& mSegment
+ 1 < aBuffers
.mSegments
.length()) {
244 const Segment
& nextSegment
= aBuffers
.mSegments
[mSegment
];
245 mData
= nextSegment
.Start();
246 mDataEnd
= nextSegment
.End();
247 MOZ_RELEASE_ASSERT(mData
< mDataEnd
);
251 // Advance the iterator by aBytes, possibly crossing segments. This function
252 // returns false if it runs out of buffers to advance through. Otherwise it
254 bool AdvanceAcrossSegments(const BufferList
& aBuffers
, size_t aBytes
) {
255 size_t bytes
= aBytes
;
257 size_t toAdvance
= std::min(bytes
, RemainingInSegment());
261 Advance(aBuffers
, toAdvance
);
267 // Returns true when the iterator reaches the end of the BufferList.
268 bool Done() const { return mData
== mDataEnd
; }
271 // Count the bytes we would need to advance in order to reach aTarget.
272 size_t BytesUntil(const BufferList
& aBuffers
,
273 const IterImpl
& aTarget
) const {
276 MOZ_ASSERT(aTarget
.IsIn(aBuffers
));
279 for (uintptr_t segment
= mSegment
; segment
< aTarget
.mSegment
;
281 offset
+= aBuffers
.mSegments
[segment
].End() - data
;
282 data
= aBuffers
.mSegments
[segment
].mData
;
285 MOZ_RELEASE_ASSERT(IsIn(aBuffers
));
286 MOZ_RELEASE_ASSERT(aTarget
.mData
>= data
);
288 offset
+= aTarget
.mData
- data
;
292 bool IsIn(const BufferList
& aBuffers
) const {
293 return mSegment
< aBuffers
.mSegments
.length() &&
294 mData
>= aBuffers
.mSegments
[mSegment
].mData
&&
295 mData
< aBuffers
.mSegments
[mSegment
].End();
299 // Special convenience method that returns Iter().Data().
301 MOZ_RELEASE_ASSERT(!mSegments
.empty());
302 return mSegments
[0].mData
;
304 const char* Start() const { return mSegments
[0].mData
; }
306 IterImpl
Iter() const { return IterImpl(*this); }
308 // Copies aSize bytes from aData into the BufferList. The storage for these
309 // bytes may be split across multiple buffers. Size() is increased by aSize.
310 inline bool WriteBytes(const char* aData
, size_t aSize
);
312 // Allocates a buffer of at most |aMaxBytes| bytes and, if successful, returns
313 // that buffer, and places its size in |aSize|. If unsuccessful, returns null
314 // and leaves |aSize| undefined.
315 inline char* AllocateBytes(size_t aMaxSize
, size_t* aSize
);
317 // Copies possibly non-contiguous byte range starting at aIter into
318 // aData. aIter is advanced by aSize bytes. Returns false if it runs out of
319 // data before aSize.
320 inline bool ReadBytes(IterImpl
& aIter
, char* aData
, size_t aSize
) const;
322 // Return a new BufferList that shares storage with this BufferList. The new
323 // BufferList is read-only. It allows iteration over aSize bytes starting at
324 // aIter. Borrow can fail, in which case *aSuccess will be false upon
325 // return. The borrowed BufferList can use a different AllocPolicy than the
326 // original one. However, it is not responsible for freeing buffers, so the
327 // AllocPolicy is only used for the buffer vector.
328 template <typename BorrowingAllocPolicy
>
329 BufferList
<BorrowingAllocPolicy
> Borrow(
330 IterImpl
& aIter
, size_t aSize
, bool* aSuccess
,
331 BorrowingAllocPolicy aAP
= BorrowingAllocPolicy()) const;
333 // Return a new BufferList and move storage from this BufferList to it. The
334 // new BufferList owns the buffers. Move can fail, in which case *aSuccess
335 // will be false upon return. The new BufferList can use a different
336 // AllocPolicy than the original one. The new OtherAllocPolicy is responsible
337 // for freeing buffers, so the OtherAllocPolicy must use freeing method
338 // compatible to the original one.
339 template <typename OtherAllocPolicy
>
340 BufferList
<OtherAllocPolicy
> MoveFallible(
341 bool* aSuccess
, OtherAllocPolicy aAP
= OtherAllocPolicy());
343 // Return a new BufferList that adopts the byte range starting at Iter so that
344 // range [aIter, aIter + aSize) is transplanted to the returned BufferList.
345 // Contents of the buffer before aIter + aSize is left undefined.
346 // Extract can fail, in which case *aSuccess will be false upon return. The
347 // moved buffers are erased from the original BufferList. In case of extract
348 // fails, the original BufferList is intact. All other iterators except aIter
350 // This method requires aIter and aSize to be 8-byte aligned.
351 BufferList
Extract(IterImpl
& aIter
, size_t aSize
, bool* aSuccess
);
353 // Return the number of bytes from 'start' to 'end', two iterators within
355 size_t RangeLength(const IterImpl
& start
, const IterImpl
& end
) const {
356 MOZ_ASSERT(start
.IsIn(*this) && end
.IsIn(*this));
357 return start
.BytesUntil(*this, end
);
360 // This takes ownership of the data
361 void* WriteBytesZeroCopy(char* aData
, size_t aSize
, size_t aCapacity
) {
362 MOZ_ASSERT(aCapacity
!= 0);
363 MOZ_ASSERT(aSize
<= aCapacity
);
366 if (!mSegments
.append(Segment(aData
, aSize
, aCapacity
))) {
367 this->free_(aData
, aCapacity
);
375 explicit BufferList(AllocPolicy aAP
)
376 : AllocPolicy(aAP
), mOwning(false), mSize(0), mStandardCapacity(0) {}
378 char* AllocateSegment(size_t aSize
, size_t aCapacity
) {
379 MOZ_RELEASE_ASSERT(mOwning
);
380 MOZ_ASSERT(aCapacity
!= 0);
381 MOZ_ASSERT(aSize
<= aCapacity
);
383 char* data
= this->template pod_malloc
<char>(aCapacity
);
387 if (!mSegments
.append(Segment(data
, aSize
, aCapacity
))) {
388 this->free_(data
, aCapacity
);
396 Vector
<Segment
, 1, AllocPolicy
> mSegments
;
398 size_t mStandardCapacity
;
401 template <typename AllocPolicy
>
402 bool BufferList
<AllocPolicy
>::WriteBytes(const char* aData
, size_t aSize
) {
403 MOZ_RELEASE_ASSERT(mOwning
);
404 MOZ_RELEASE_ASSERT(mStandardCapacity
);
407 while (copied
< aSize
) {
409 char* data
= AllocateBytes(aSize
- copied
, &toCopy
);
413 memcpy(data
, aData
+ copied
, toCopy
);
420 template <typename AllocPolicy
>
421 char* BufferList
<AllocPolicy
>::AllocateBytes(size_t aMaxSize
, size_t* aSize
) {
422 MOZ_RELEASE_ASSERT(mOwning
);
423 MOZ_RELEASE_ASSERT(mStandardCapacity
);
425 if (!mSegments
.empty()) {
426 Segment
& lastSegment
= mSegments
.back();
428 size_t capacity
= lastSegment
.mCapacity
- lastSegment
.mSize
;
430 size_t size
= std::min(aMaxSize
, capacity
);
431 char* data
= lastSegment
.mData
+ lastSegment
.mSize
;
433 lastSegment
.mSize
+= size
;
441 size_t size
= std::min(aMaxSize
, mStandardCapacity
);
442 char* data
= AllocateSegment(size
, mStandardCapacity
);
449 template <typename AllocPolicy
>
450 bool BufferList
<AllocPolicy
>::ReadBytes(IterImpl
& aIter
, char* aData
,
451 size_t aSize
) const {
453 size_t remaining
= aSize
;
455 size_t toCopy
= std::min(aIter
.RemainingInSegment(), remaining
);
457 // We've run out of data in the last segment.
460 memcpy(aData
+ copied
, aIter
.Data(), toCopy
);
464 aIter
.Advance(*this, toCopy
);
470 template <typename AllocPolicy
>
471 template <typename BorrowingAllocPolicy
>
472 BufferList
<BorrowingAllocPolicy
> BufferList
<AllocPolicy
>::Borrow(
473 IterImpl
& aIter
, size_t aSize
, bool* aSuccess
,
474 BorrowingAllocPolicy aAP
) const {
475 BufferList
<BorrowingAllocPolicy
> result(aAP
);
479 size_t toAdvance
= std::min(size
, aIter
.RemainingInSegment());
481 if (!toAdvance
|| !result
.mSegments
.append(
482 typename BufferList
<BorrowingAllocPolicy
>::Segment(
483 aIter
.mData
, toAdvance
, toAdvance
))) {
487 aIter
.Advance(*this, toAdvance
);
491 result
.mSize
= aSize
;
496 template <typename AllocPolicy
>
497 template <typename OtherAllocPolicy
>
498 BufferList
<OtherAllocPolicy
> BufferList
<AllocPolicy
>::MoveFallible(
499 bool* aSuccess
, OtherAllocPolicy aAP
) {
500 BufferList
<OtherAllocPolicy
> result(0, 0, mStandardCapacity
, aAP
);
502 IterImpl iter
= Iter();
503 while (!iter
.Done()) {
504 size_t toAdvance
= iter
.RemainingInSegment();
507 !result
.mSegments
.append(typename BufferList
<OtherAllocPolicy
>::Segment(
508 iter
.mData
, toAdvance
, toAdvance
))) {
510 result
.mSegments
.clear();
513 iter
.Advance(*this, toAdvance
);
516 result
.mSize
= mSize
;
523 template <typename AllocPolicy
>
524 BufferList
<AllocPolicy
> BufferList
<AllocPolicy
>::Extract(IterImpl
& aIter
,
527 MOZ_RELEASE_ASSERT(aSize
);
528 MOZ_RELEASE_ASSERT(mOwning
);
529 MOZ_ASSERT(aSize
% kSegmentAlignment
== 0);
530 MOZ_ASSERT(intptr_t(aIter
.mData
) % kSegmentAlignment
== 0);
532 auto failure
= [this, aSuccess
]() {
534 return BufferList(0, 0, mStandardCapacity
);
537 // Number of segments we'll need to copy data from to satisfy the request.
538 size_t segmentsNeeded
= 0;
539 // If this is None then the last segment is a full segment, otherwise we need
540 // to copy this many bytes.
541 Maybe
<size_t> lastSegmentSize
;
543 // Copy of the iterator to walk the BufferList and see how many segments we
545 IterImpl iter
= aIter
;
546 size_t remaining
= aSize
;
547 while (!iter
.Done() && remaining
&&
548 remaining
>= iter
.RemainingInSegment()) {
549 remaining
-= iter
.RemainingInSegment();
550 iter
.Advance(*this, iter
.RemainingInSegment());
556 // We reached the end of the BufferList and there wasn't enough data to
557 // satisfy the request.
560 lastSegmentSize
.emplace(remaining
);
561 // The last block also counts as a segment. This makes the conditionals
562 // on segmentsNeeded work in the rest of the function.
567 BufferList
result(0, 0, mStandardCapacity
);
568 if (!result
.mSegments
.reserve(segmentsNeeded
+ lastSegmentSize
.isSome())) {
572 // Copy the first segment, it's special because we can't just steal the
573 // entire Segment struct from this->mSegments.
574 size_t firstSegmentSize
= std::min(aSize
, aIter
.RemainingInSegment());
575 if (!result
.WriteBytes(aIter
.Data(), firstSegmentSize
)) {
578 aIter
.Advance(*this, firstSegmentSize
);
581 // The entirety of the request wasn't in the first segment, now copy the
583 if (segmentsNeeded
) {
584 char* finalSegment
= nullptr;
585 // Pre-allocate the final segment so that if this fails, we return before
586 // we delete the elements from |this->mSegments|.
587 if (lastSegmentSize
.isSome()) {
588 MOZ_RELEASE_ASSERT(mStandardCapacity
>= *lastSegmentSize
);
589 finalSegment
= this->template pod_malloc
<char>(mStandardCapacity
);
595 size_t copyStart
= aIter
.mSegment
;
596 // Copy segments from this over to the result and remove them from our
597 // storage. Not needed if the only segment we need to copy is the last
599 size_t segmentsToCopy
= segmentsNeeded
- lastSegmentSize
.isSome();
600 for (size_t i
= 0; i
< segmentsToCopy
; ++i
) {
601 result
.mSegments
.infallibleAppend(Segment(
602 mSegments
[aIter
.mSegment
].mData
, mSegments
[aIter
.mSegment
].mSize
,
603 mSegments
[aIter
.mSegment
].mCapacity
));
604 aIter
.Advance(*this, aIter
.RemainingInSegment());
606 // Due to the way IterImpl works, there are two cases here: (1) if we've
607 // consumed the entirety of the BufferList, then the iterator is pointed at
608 // the end of the final segment, (2) otherwise it is pointed at the start
609 // of the next segment. We want to verify that we really consumed all
610 // |segmentsToCopy| segments.
612 (aIter
.mSegment
== copyStart
+ segmentsToCopy
) ||
613 (aIter
.Done() && aIter
.mSegment
== copyStart
+ segmentsToCopy
- 1));
614 mSegments
.erase(mSegments
.begin() + copyStart
,
615 mSegments
.begin() + copyStart
+ segmentsToCopy
);
617 // Reset the iter's position for what we just deleted.
618 aIter
.mSegment
-= segmentsToCopy
;
620 if (lastSegmentSize
.isSome()) {
621 // We called reserve() on result.mSegments so infallibleAppend is safe.
622 result
.mSegments
.infallibleAppend(
623 Segment(finalSegment
, 0, mStandardCapacity
));
624 bool r
= result
.WriteBytes(aIter
.Data(), *lastSegmentSize
);
625 MOZ_RELEASE_ASSERT(r
);
626 aIter
.Advance(*this, *lastSegmentSize
);
631 result
.mSize
= aSize
;
637 } // namespace mozilla
639 #endif /* mozilla_BufferList_h */