no bug - Bumping Firefox l10n changesets r=release a=l10n-bump DONTBUILD CLOSED TREE
[gecko.git] / mfbt / BufferList.h
blob5556abf70088155f5c9edf7aeb0c82eba6fc9f86
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
10 #include <algorithm>
11 #include <cstdint>
12 #include <cstring>
13 #include <numeric>
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;
29 namespace mozilla {
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.
35 struct Segment {
36 char* mData;
37 size_t mSize;
38 size_t mCapacity;
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;
56 public:
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())
73 : AllocPolicy(aAP),
74 mOwning(true),
75 mSegments(aAP),
76 mSize(0),
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)),
96 mSize(aOther.mSize),
97 mStandardCapacity(aOther.mStandardCapacity) {
98 aOther.mSegments.clear();
99 aOther.mSize = 0;
102 BufferList& operator=(const BufferList& aOther) = delete;
104 BufferList& operator=(BufferList&& aOther) {
105 Clear();
107 mOwning = aOther.mOwning;
108 mSegments = std::move(aOther.mSegments);
109 mSize = aOther.mSize;
110 aOther.mSegments.clear();
111 aOther.mSize = 0;
112 return *this;
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) {
128 MOZ_ASSERT(mOwning);
130 Clear();
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))) {
136 return false;
139 size_t offset = 0;
140 for (const Segment& segment : aOther.mSegments) {
141 memcpy(Start() + offset, segment.mData, segment.mSize);
142 offset += segment.mSize;
144 MOZ_ASSERT(offset == mSize);
146 return true;
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());
157 return size;
160 void Clear() {
161 if (mOwning) {
162 for (Segment& segment : mSegments) {
163 this->free_(segment.mData, segment.mCapacity);
166 mSegments.clear();
168 mSize = 0;
171 // Iterates over bytes in the segments. You can advance it by as many bytes as
172 // you choose.
173 class IterImpl {
174 // Invariants:
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;
185 public:
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.
195 char* Data() const {
196 MOZ_RELEASE_ASSERT(!Done());
197 return mData;
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
212 // true.
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)
225 // will be true.
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));
241 mData += aBytes;
242 mAbsoluteOffset += aBytes;
244 if (mData == mDataEnd && mSegment + 1 < aBuffers.mSegments.length()) {
245 mSegment++;
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
255 // returns true.
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);
261 return true;
264 // Check if we have enough bytes to scan this far forward.
265 if (!HasBytesAvailable(aBuffers, aBytes)) {
266 return false;
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
272 // backwards.
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
277 // offset.
278 while (mAbsoluteOffset < targetOffset) {
279 Advance(aBuffers, std::min(targetOffset - mAbsoluteOffset,
280 RemainingInSegment()));
282 MOZ_ASSERT(mAbsoluteOffset == targetOffset);
283 return true;
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;
294 mSegment--;
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);
301 return true;
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; }
310 private:
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().
319 char* Start() {
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
363 // this BufferList.
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,
371 size_t aCapacity) {
372 MOZ_ASSERT(mOwning);
373 MOZ_ASSERT(aSize <= aCapacity);
375 // Don't create zero-length segments; that can cause problems for
376 // consumers of the data (bug 1595453).
377 if (aSize == 0) {
378 this->free_(aData, aCapacity);
379 return true;
382 if (!mSegments.append(Segment(aData, aSize, aCapacity))) {
383 this->free_(aData, aCapacity);
384 return false;
386 mSize += aSize;
387 return true;
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);
397 private:
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);
407 if (!data) {
408 return nullptr;
410 if (!mSegments.append(Segment(data, aSize, aCapacity))) {
411 this->free_(data, aCapacity);
412 return nullptr;
414 mSize += aSize;
415 return data;
418 void AssertConsistentSize() const {
419 #ifdef DEBUG
420 size_t realSize = 0;
421 for (const auto& segment : mSegments) {
422 realSize += segment.mSize;
424 MOZ_ASSERT(realSize == mSize, "cached size value is inconsistent!");
425 #endif
428 bool mOwning;
429 Vector<Segment, 1, AllocPolicy> mSegments;
430 size_t mSize;
431 size_t mStandardCapacity;
434 template <typename AllocPolicy>
435 [[nodiscard]] bool BufferList<AllocPolicy>::WriteBytes(const char* aData,
436 size_t aSize) {
437 MOZ_RELEASE_ASSERT(mOwning);
438 MOZ_RELEASE_ASSERT(mStandardCapacity);
440 size_t copied = 0;
441 while (copied < aSize) {
442 size_t toCopy;
443 char* data = AllocateBytes(aSize - copied, &toCopy);
444 if (!data) {
445 return false;
447 memcpy(data, aData + copied, toCopy);
448 copied += toCopy;
451 return true;
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;
463 if (capacity) {
464 size_t size = std::min(aMaxSize, capacity);
465 char* data = lastSegment.mData + lastSegment.mSize;
467 lastSegment.mSize += size;
468 mSize += size;
470 *aSize = size;
471 return data;
475 size_t size = std::min(aMaxSize, mStandardCapacity);
476 char* data = AllocateSegment(size, mStandardCapacity);
477 if (data) {
478 *aSize = size;
480 return data;
483 template <typename AllocPolicy>
484 bool BufferList<AllocPolicy>::ReadBytes(IterImpl& aIter, char* aData,
485 size_t aSize) const {
486 size_t copied = 0;
487 size_t remaining = aSize;
488 while (remaining) {
489 size_t toCopy = std::min(aIter.RemainingInSegment(), remaining);
490 if (!toCopy) {
491 // We've run out of data in the last segment.
492 return false;
494 memcpy(aData + copied, aIter.Data(), toCopy);
495 copied += toCopy;
496 remaining -= toCopy;
498 aIter.Advance(*this, toCopy);
501 return true;
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);
511 size_t size = aSize;
512 while (size) {
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))) {
518 *aSuccess = false;
519 return result;
521 aIter.Advance(*this, toAdvance);
522 size -= toAdvance;
525 result.mSize = aSize;
526 *aSuccess = true;
527 return result;
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();
540 if (!toAdvance ||
541 !result.mSegments.append(typename BufferList<OtherAllocPolicy>::Segment(
542 iter.mData, toAdvance, toAdvance))) {
543 *aSuccess = false;
544 result.mSegments.clear();
545 return result;
547 iter.Advance(*this, toAdvance);
550 result.mSize = mSize;
551 mSegments.clear();
552 mSize = 0;
553 *aSuccess = true;
554 return result;
557 template <typename AllocPolicy>
558 size_t BufferList<AllocPolicy>::Truncate(IterImpl& aIter) {
559 MOZ_ASSERT(aIter.IsIn(*this) || aIter.Done());
560 if (aIter.Done()) {
561 return 0;
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;
570 if (mOwning) {
571 this->free_(toFree.mData, toFree.mCapacity);
573 mSegments.popBack();
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();
581 if (!seg.mSize) {
582 if (mOwning) {
583 this->free_(seg.mData, seg.mCapacity);
585 mSegments.popBack();
588 // Correct `aIter` to point to the new end of the BufferList.
589 if (mSegments.empty()) {
590 MOZ_ASSERT(mSize == 0);
591 aIter.mSegment = 0;
592 aIter.mData = aIter.mDataEnd = nullptr;
593 } else {
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 */