Line data Source code
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/. */
6 :
7 : #ifndef mozilla_BufferList_h
8 : #define mozilla_BufferList_h
9 :
10 : #include <algorithm>
11 : #include "mozilla/AllocPolicy.h"
12 : #include "mozilla/Move.h"
13 : #include "mozilla/ScopeExit.h"
14 : #include "mozilla/Types.h"
15 : #include "mozilla/TypeTraits.h"
16 : #include "mozilla/Vector.h"
17 : #include <string.h>
18 :
19 : // BufferList represents a sequence of buffers of data. A BufferList can choose
20 : // to own its buffers or not. The class handles writing to the buffers,
21 : // iterating over them, and reading data out. Unlike SegmentedVector, the
22 : // buffers may be of unequal size. Like SegmentedVector, BufferList is a nice
23 : // way to avoid large contiguous allocations (which can trigger OOMs).
24 :
25 : class InfallibleAllocPolicy;
26 :
27 : namespace mozilla {
28 :
29 : template<typename AllocPolicy>
30 : class BufferList : private AllocPolicy
31 : {
32 : // Each buffer in a BufferList has a size and a capacity. The first mSize
33 : // bytes are initialized and the remaining |mCapacity - mSize| bytes are free.
34 : struct Segment
35 : {
36 : char* mData;
37 : size_t mSize;
38 : size_t mCapacity;
39 :
40 2650 : Segment(char* aData, size_t aSize, size_t aCapacity)
41 : : mData(aData),
42 : mSize(aSize),
43 2650 : mCapacity(aCapacity)
44 : {
45 2650 : }
46 :
47 : Segment(const Segment&) = delete;
48 : Segment& operator=(const Segment&) = delete;
49 :
50 : Segment(Segment&&) = default;
51 : Segment& operator=(Segment&&) = default;
52 :
53 152081 : char* Start() const { return mData; }
54 152121 : char* End() const { return mData + mSize; }
55 : };
56 :
57 : template<typename OtherAllocPolicy>
58 : friend class BufferList;
59 :
60 : public:
61 : // For the convenience of callers, all segments are required to be a multiple
62 : // of 8 bytes in capacity. Also, every buffer except the last one is required
63 : // to be full (i.e., size == capacity). Therefore, a byte at offset N within
64 : // the BufferList and stored in memory at an address A will satisfy
65 : // (N % Align == A % Align) if Align == 2, 4, or 8.
66 : static const size_t kSegmentAlignment = 8;
67 :
68 : // Allocate a BufferList. The BufferList will free all its buffers when it is
69 : // destroyed. If an infallible allocator is used, an initial buffer of size
70 : // aInitialSize and capacity aInitialCapacity is allocated automatically. This
71 : // data will be contiguous and can be accessed via |Start()|. If a fallible
72 : // alloc policy is used, aInitialSize must be 0, and the fallible |Init()|
73 : // method may be called instead. Subsequent buffers will be allocated with
74 : // capacity aStandardCapacity.
75 1581 : BufferList(size_t aInitialSize,
76 : size_t aInitialCapacity,
77 : size_t aStandardCapacity,
78 : AllocPolicy aAP = AllocPolicy())
79 : : AllocPolicy(aAP),
80 : mOwning(true),
81 : mSegments(aAP),
82 : mSize(0),
83 1581 : mStandardCapacity(aStandardCapacity)
84 : {
85 1581 : MOZ_ASSERT(aInitialCapacity % kSegmentAlignment == 0);
86 1581 : MOZ_ASSERT(aStandardCapacity % kSegmentAlignment == 0);
87 :
88 1581 : if (aInitialCapacity) {
89 307 : MOZ_ASSERT((aInitialSize == 0 || IsSame<AllocPolicy, InfallibleAllocPolicy>::value),
90 : "BufferList may only be constructed with an initial size when "
91 : "using an infallible alloc policy");
92 :
93 1305 : AllocateSegment(aInitialSize, aInitialCapacity);
94 : }
95 1581 : }
96 :
97 : BufferList(const BufferList& aOther) = delete;
98 :
99 822 : BufferList(BufferList&& aOther)
100 822 : : mOwning(aOther.mOwning),
101 822 : mSegments(Move(aOther.mSegments)),
102 822 : mSize(aOther.mSize),
103 3288 : mStandardCapacity(aOther.mStandardCapacity)
104 : {
105 822 : aOther.mSegments.clear();
106 822 : aOther.mSize = 0;
107 822 : }
108 :
109 : BufferList& operator=(const BufferList& aOther) = delete;
110 :
111 400 : BufferList& operator=(BufferList&& aOther)
112 : {
113 400 : Clear();
114 :
115 400 : mOwning = aOther.mOwning;
116 400 : mSegments = Move(aOther.mSegments);
117 400 : mSize = aOther.mSize;
118 400 : aOther.mSegments.clear();
119 400 : aOther.mSize = 0;
120 400 : return *this;
121 : }
122 :
123 2470 : ~BufferList() { Clear(); }
124 :
125 : // Initializes the BufferList with a segment of the given size and capacity.
126 : // May only be called once, before any segments have been allocated.
127 0 : bool Init(size_t aInitialSize, size_t aInitialCapacity)
128 : {
129 0 : MOZ_ASSERT(mSegments.empty());
130 0 : MOZ_ASSERT(aInitialCapacity != 0);
131 0 : MOZ_ASSERT(aInitialCapacity % kSegmentAlignment == 0);
132 :
133 0 : return AllocateSegment(aInitialSize, aInitialCapacity);
134 : }
135 :
136 : // Returns the sum of the sizes of all the buffers.
137 1957 : size_t Size() const { return mSize; }
138 :
139 2899 : void Clear()
140 : {
141 2899 : if (mOwning) {
142 5078 : for (Segment& segment : mSegments) {
143 2436 : this->free_(segment.mData);
144 : }
145 : }
146 2899 : mSegments.clear();
147 :
148 2899 : mSize = 0;
149 2899 : }
150 :
151 : // Iterates over bytes in the segments. You can advance it by as many bytes as
152 : // you choose.
153 : class IterImpl
154 : {
155 : // Invariants:
156 : // (0) mSegment <= bufferList.mSegments.length()
157 : // (1) mData <= mDataEnd
158 : // (2) If mSegment is not the last segment, mData < mDataEnd
159 : uintptr_t mSegment;
160 : char* mData;
161 : char* mDataEnd;
162 :
163 : friend class BufferList;
164 :
165 : public:
166 1293 : explicit IterImpl(const BufferList& aBuffers)
167 : : mSegment(0),
168 : mData(nullptr),
169 1293 : mDataEnd(nullptr)
170 : {
171 1293 : if (!aBuffers.mSegments.empty()) {
172 1280 : mData = aBuffers.mSegments[0].Start();
173 1280 : mDataEnd = aBuffers.mSegments[0].End();
174 : }
175 1293 : }
176 :
177 : // Returns a pointer to the raw data. It is valid to access up to
178 : // RemainingInSegment bytes of this buffer.
179 141676 : char* Data() const
180 : {
181 141676 : MOZ_RELEASE_ASSERT(!Done());
182 141677 : return mData;
183 : }
184 :
185 : // Returns true if the memory in the range [Data(), Data() + aBytes) is all
186 : // part of one contiguous buffer.
187 277389 : bool HasRoomFor(size_t aBytes) const
188 : {
189 277389 : MOZ_RELEASE_ASSERT(mData <= mDataEnd);
190 277389 : return size_t(mDataEnd - mData) >= aBytes;
191 : }
192 :
193 : // Returns the maximum value aBytes for which HasRoomFor(aBytes) will be
194 : // true.
195 22004 : size_t RemainingInSegment() const
196 : {
197 22004 : MOZ_RELEASE_ASSERT(mData <= mDataEnd);
198 22004 : return mDataEnd - mData;
199 : }
200 :
201 : // Advances the iterator by aBytes bytes. aBytes must be less than
202 : // RemainingInSegment(). If advancing by aBytes takes the iterator to the
203 : // end of a buffer, it will be moved to the beginning of the next buffer
204 : // unless it is the last buffer.
205 148897 : void Advance(const BufferList& aBuffers, size_t aBytes)
206 : {
207 148897 : const Segment& segment = aBuffers.mSegments[mSegment];
208 148898 : MOZ_RELEASE_ASSERT(segment.Start() <= mData);
209 148898 : MOZ_RELEASE_ASSERT(mData <= mDataEnd);
210 148898 : MOZ_RELEASE_ASSERT(mDataEnd == segment.End());
211 :
212 148898 : MOZ_RELEASE_ASSERT(HasRoomFor(aBytes));
213 148898 : mData += aBytes;
214 :
215 148898 : if (mData == mDataEnd && mSegment + 1 < aBuffers.mSegments.length()) {
216 1903 : mSegment++;
217 1903 : const Segment& nextSegment = aBuffers.mSegments[mSegment];
218 1903 : mData = nextSegment.Start();
219 1903 : mDataEnd = nextSegment.End();
220 1903 : MOZ_RELEASE_ASSERT(mData < mDataEnd);
221 : }
222 148898 : }
223 :
224 : // Advance the iterator by aBytes, possibly crossing segments. This function
225 : // returns false if it runs out of buffers to advance through. Otherwise it
226 : // returns true.
227 13290 : bool AdvanceAcrossSegments(const BufferList& aBuffers, size_t aBytes)
228 : {
229 13290 : size_t bytes = aBytes;
230 31178 : while (bytes) {
231 8944 : size_t toAdvance = std::min(bytes, RemainingInSegment());
232 8944 : if (!toAdvance) {
233 0 : return false;
234 : }
235 8944 : Advance(aBuffers, toAdvance);
236 8944 : bytes -= toAdvance;
237 : }
238 13290 : return true;
239 : }
240 :
241 : // Returns true when the iterator reaches the end of the BufferList.
242 146037 : bool Done() const
243 : {
244 146037 : return mData == mDataEnd;
245 : }
246 :
247 : private:
248 :
249 : // Count the bytes we would need to advance in order to reach aTarget.
250 0 : size_t BytesUntil(const BufferList& aBuffers, const IterImpl& aTarget) const {
251 0 : size_t offset = 0;
252 :
253 0 : MOZ_ASSERT(aTarget.IsIn(aBuffers));
254 :
255 0 : char* data = mData;
256 0 : for (uintptr_t segment = mSegment; segment < aTarget.mSegment; segment++) {
257 0 : offset += aBuffers.mSegments[segment].End() - data;
258 0 : data = aBuffers.mSegments[segment].mData;
259 : }
260 :
261 0 : MOZ_RELEASE_ASSERT(IsIn(aBuffers));
262 0 : MOZ_RELEASE_ASSERT(aTarget.mData >= data);
263 :
264 0 : offset += aTarget.mData - data;
265 0 : return offset;
266 : }
267 :
268 0 : bool IsIn(const BufferList& aBuffers) const {
269 0 : return mSegment < aBuffers.mSegments.length() &&
270 0 : mData >= aBuffers.mSegments[mSegment].mData &&
271 0 : mData < aBuffers.mSegments[mSegment].End();
272 : }
273 : };
274 :
275 : // Special convenience method that returns Iter().Data().
276 958 : char* Start()
277 : {
278 958 : MOZ_RELEASE_ASSERT(!mSegments.empty());
279 958 : return mSegments[0].mData;
280 : }
281 398 : const char* Start() const { return mSegments[0].mData; }
282 :
283 901 : IterImpl Iter() const { return IterImpl(*this); }
284 :
285 : // Copies aSize bytes from aData into the BufferList. The storage for these
286 : // bytes may be split across multiple buffers. Size() is increased by aSize.
287 : inline bool WriteBytes(const char* aData, size_t aSize);
288 :
289 : // Allocates a buffer of at most |aMaxBytes| bytes and, if successful, returns
290 : // that buffer, and places its size in |aSize|. If unsuccessful, returns null
291 : // and leaves |aSize| undefined.
292 : inline char* AllocateBytes(size_t aMaxSize, size_t* aSize);
293 :
294 : // Copies possibly non-contiguous byte range starting at aIter into
295 : // aData. aIter is advanced by aSize bytes. Returns false if it runs out of
296 : // data before aSize.
297 : inline bool ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const;
298 :
299 : // Return a new BufferList that shares storage with this BufferList. The new
300 : // BufferList is read-only. It allows iteration over aSize bytes starting at
301 : // aIter. Borrow can fail, in which case *aSuccess will be false upon
302 : // return. The borrowed BufferList can use a different AllocPolicy than the
303 : // original one. However, it is not responsible for freeing buffers, so the
304 : // AllocPolicy is only used for the buffer vector.
305 : template<typename BorrowingAllocPolicy>
306 : BufferList<BorrowingAllocPolicy> Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
307 : BorrowingAllocPolicy aAP = BorrowingAllocPolicy()) const;
308 :
309 : // Return a new BufferList and move storage from this BufferList to it. The
310 : // new BufferList owns the buffers. Move can fail, in which case *aSuccess
311 : // will be false upon return. The new BufferList can use a different
312 : // AllocPolicy than the original one. The new OtherAllocPolicy is responsible
313 : // for freeing buffers, so the OtherAllocPolicy must use freeing method
314 : // compatible to the original one.
315 : template<typename OtherAllocPolicy>
316 : BufferList<OtherAllocPolicy> MoveFallible(bool* aSuccess, OtherAllocPolicy aAP = OtherAllocPolicy());
317 :
318 : // Return a new BufferList that adopts the byte range starting at Iter so that
319 : // range [aIter, aIter + aSize) is transplanted to the returned BufferList.
320 : // Contents of the buffer before aIter + aSize is left undefined.
321 : // Extract can fail, in which case *aSuccess will be false upon return. The
322 : // moved buffers are erased from the original BufferList. In case of extract
323 : // fails, the original BufferList is intact. All other iterators except aIter
324 : // are invalidated.
325 : // This method requires aIter and aSize to be 8-byte aligned.
326 : BufferList Extract(IterImpl& aIter, size_t aSize, bool* aSuccess);
327 :
328 : // Return the number of bytes from 'start' to 'end', two iterators within
329 : // this BufferList.
330 0 : size_t RangeLength(const IterImpl& start, const IterImpl& end) const {
331 0 : MOZ_ASSERT(start.IsIn(*this) && end.IsIn(*this));
332 0 : return start.BytesUntil(*this, end);
333 : }
334 :
335 : private:
336 86 : explicit BufferList(AllocPolicy aAP)
337 : : AllocPolicy(aAP),
338 : mOwning(false),
339 : mSize(0),
340 86 : mStandardCapacity(0)
341 : {
342 86 : }
343 :
344 2457 : char* AllocateSegment(size_t aSize, size_t aCapacity)
345 : {
346 2457 : MOZ_RELEASE_ASSERT(mOwning);
347 2457 : MOZ_ASSERT(aCapacity != 0);
348 2457 : MOZ_ASSERT(aSize <= aCapacity);
349 :
350 2457 : char* data = this->template pod_malloc<char>(aCapacity);
351 2457 : if (!data) {
352 0 : return nullptr;
353 : }
354 2457 : if (!mSegments.append(Segment(data, aSize, aCapacity))) {
355 0 : this->free_(data);
356 0 : return nullptr;
357 : }
358 2457 : mSize += aSize;
359 2457 : return data;
360 : }
361 :
362 : bool mOwning;
363 : Vector<Segment, 1, AllocPolicy> mSegments;
364 : size_t mSize;
365 : size_t mStandardCapacity;
366 : };
367 :
368 : template<typename AllocPolicy>
369 : bool
370 149210 : BufferList<AllocPolicy>::WriteBytes(const char* aData, size_t aSize)
371 : {
372 149210 : MOZ_RELEASE_ASSERT(mOwning);
373 149210 : MOZ_RELEASE_ASSERT(mStandardCapacity);
374 :
375 149210 : size_t copied = 0;
376 446826 : while (copied < aSize) {
377 : size_t toCopy;
378 148809 : char* data = AllocateBytes(aSize - copied, &toCopy);
379 148808 : if (!data) {
380 0 : return false;
381 : }
382 148808 : memcpy(data, aData + copied, toCopy);
383 148808 : copied += toCopy;
384 : }
385 :
386 149209 : return true;
387 : }
388 :
389 : template<typename AllocPolicy>
390 : char*
391 148809 : BufferList<AllocPolicy>::AllocateBytes(size_t aMaxSize, size_t* aSize)
392 : {
393 148809 : MOZ_RELEASE_ASSERT(mOwning);
394 148809 : MOZ_RELEASE_ASSERT(mStandardCapacity);
395 :
396 148809 : if (!mSegments.empty()) {
397 148735 : Segment& lastSegment = mSegments.back();
398 :
399 148735 : size_t capacity = lastSegment.mCapacity - lastSegment.mSize;
400 148735 : if (capacity) {
401 147657 : size_t size = std::min(aMaxSize, capacity);
402 147657 : char* data = lastSegment.mData + lastSegment.mSize;
403 :
404 147657 : lastSegment.mSize += size;
405 147657 : mSize += size;
406 :
407 147657 : *aSize = size;
408 147657 : return data;
409 : }
410 : }
411 :
412 1152 : size_t size = std::min(aMaxSize, mStandardCapacity);
413 1152 : char* data = AllocateSegment(size, mStandardCapacity);
414 1152 : if (data) {
415 1152 : *aSize = size;
416 : }
417 1152 : return data;
418 : }
419 :
420 : template<typename AllocPolicy>
421 : bool
422 11891 : BufferList<AllocPolicy>::ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const
423 : {
424 11891 : size_t copied = 0;
425 11891 : size_t remaining = aSize;
426 34387 : while (remaining) {
427 11248 : size_t toCopy = std::min(aIter.RemainingInSegment(), remaining);
428 11248 : if (!toCopy) {
429 : // We've run out of data in the last segment.
430 0 : return false;
431 : }
432 11248 : memcpy(aData + copied, aIter.Data(), toCopy);
433 11248 : copied += toCopy;
434 11248 : remaining -= toCopy;
435 :
436 11248 : aIter.Advance(*this, toCopy);
437 : }
438 :
439 11891 : return true;
440 : }
441 :
442 : template<typename AllocPolicy> template<typename BorrowingAllocPolicy>
443 : BufferList<BorrowingAllocPolicy>
444 86 : BufferList<AllocPolicy>::Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
445 : BorrowingAllocPolicy aAP) const
446 : {
447 86 : BufferList<BorrowingAllocPolicy> result(aAP);
448 :
449 86 : size_t size = aSize;
450 240 : while (size) {
451 77 : size_t toAdvance = std::min(size, aIter.RemainingInSegment());
452 :
453 77 : if (!toAdvance || !result.mSegments.append(typename BufferList<BorrowingAllocPolicy>::Segment(aIter.mData, toAdvance, toAdvance))) {
454 0 : *aSuccess = false;
455 0 : return result;
456 : }
457 77 : aIter.Advance(*this, toAdvance);
458 77 : size -= toAdvance;
459 : }
460 :
461 86 : result.mSize = aSize;
462 86 : *aSuccess = true;
463 86 : return result;
464 : }
465 :
466 : template<typename AllocPolicy> template<typename OtherAllocPolicy>
467 : BufferList<OtherAllocPolicy>
468 118 : BufferList<AllocPolicy>::MoveFallible(bool* aSuccess, OtherAllocPolicy aAP)
469 : {
470 118 : BufferList<OtherAllocPolicy> result(0, 0, mStandardCapacity, aAP);
471 :
472 118 : IterImpl iter = Iter();
473 350 : while (!iter.Done()) {
474 116 : size_t toAdvance = iter.RemainingInSegment();
475 :
476 116 : if (!toAdvance || !result.mSegments.append(typename BufferList<OtherAllocPolicy>::Segment(iter.mData, toAdvance, toAdvance))) {
477 0 : *aSuccess = false;
478 0 : result.mSegments.clear();
479 0 : return result;
480 : }
481 116 : iter.Advance(*this, toAdvance);
482 : }
483 :
484 118 : result.mSize = mSize;
485 118 : mSegments.clear();
486 118 : mSize = 0;
487 118 : *aSuccess = true;
488 118 : return result;
489 : }
490 :
491 : template<typename AllocPolicy>
492 : BufferList<AllocPolicy>
493 40 : BufferList<AllocPolicy>::Extract(IterImpl& aIter, size_t aSize, bool* aSuccess)
494 : {
495 40 : MOZ_RELEASE_ASSERT(aSize);
496 40 : MOZ_RELEASE_ASSERT(mOwning);
497 40 : MOZ_ASSERT(aSize % kSegmentAlignment == 0);
498 40 : MOZ_ASSERT(intptr_t(aIter.mData) % kSegmentAlignment == 0);
499 :
500 40 : IterImpl iter = aIter;
501 40 : size_t size = aSize;
502 40 : size_t toCopy = std::min(size, aIter.RemainingInSegment());
503 40 : MOZ_ASSERT(toCopy % kSegmentAlignment == 0);
504 :
505 80 : BufferList result(0, toCopy, mStandardCapacity);
506 80 : BufferList error(0, 0, mStandardCapacity);
507 :
508 : // Copy the head
509 40 : if (!result.WriteBytes(aIter.mData, toCopy)) {
510 0 : *aSuccess = false;
511 0 : return error;
512 : }
513 40 : iter.Advance(*this, toCopy);
514 40 : size -= toCopy;
515 :
516 : // Move segments to result
517 0 : auto resultGuard = MakeScopeExit([&] {
518 0 : *aSuccess = false;
519 0 : result.mSegments.erase(result.mSegments.begin()+1, result.mSegments.end());
520 80 : });
521 :
522 40 : size_t movedSize = 0;
523 40 : uintptr_t toRemoveStart = iter.mSegment;
524 40 : uintptr_t toRemoveEnd = iter.mSegment;
525 80 : while (!iter.Done() &&
526 40 : !iter.HasRoomFor(size)) {
527 0 : if (!result.mSegments.append(Segment(mSegments[iter.mSegment].mData,
528 0 : mSegments[iter.mSegment].mSize,
529 0 : mSegments[iter.mSegment].mCapacity))) {
530 0 : return error;
531 : }
532 0 : movedSize += iter.RemainingInSegment();
533 0 : size -= iter.RemainingInSegment();
534 0 : toRemoveEnd++;
535 0 : iter.Advance(*this, iter.RemainingInSegment());
536 : }
537 :
538 40 : if (size) {
539 0 : if (!iter.HasRoomFor(size) ||
540 0 : !result.WriteBytes(iter.Data(), size)) {
541 0 : return error;
542 : }
543 0 : iter.Advance(*this, size);
544 : }
545 :
546 40 : mSegments.erase(mSegments.begin() + toRemoveStart, mSegments.begin() + toRemoveEnd);
547 40 : mSize -= movedSize;
548 40 : aIter.mSegment = iter.mSegment - (toRemoveEnd - toRemoveStart);
549 40 : aIter.mData = iter.mData;
550 40 : aIter.mDataEnd = iter.mDataEnd;
551 40 : MOZ_ASSERT(aIter.mDataEnd == mSegments[aIter.mSegment].End());
552 40 : result.mSize = aSize;
553 :
554 40 : resultGuard.release();
555 40 : *aSuccess = true;
556 40 : return result;
557 : }
558 :
559 : } // namespace mozilla
560 :
561 : #endif /* mozilla_BufferList_h */
|
