BufferList.h 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568
  1. /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /* This Source Code Form is subject to the terms of the Mozilla Public
  3. * License, v. 2.0. If a copy of the MPL was not distributed with this
  4. * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
  5. #ifndef mozilla_BufferList_h
  6. #define mozilla_BufferList_h
  7. #include <algorithm>
  8. #include "mozilla/AllocPolicy.h"
  9. #include "mozilla/Maybe.h"
  10. #include "mozilla/Move.h"
  11. #include "mozilla/ScopeExit.h"
  12. #include "mozilla/Types.h"
  13. #include "mozilla/TypeTraits.h"
  14. #include "mozilla/Vector.h"
  15. #include <string.h>
  16. // Undo potential #include <windows.h> damage to be able to use std::min.
  17. #undef min
  18. // BufferList represents a sequence of buffers of data. A BufferList can choose
  19. // to own its buffers or not. The class handles writing to the buffers,
  20. // iterating over them, and reading data out. Unlike SegmentedVector, the
  21. // buffers may be of unequal size. Like SegmentedVector, BufferList is a nice
  22. // way to avoid large contiguous allocations (which can trigger OOMs).
  23. namespace mozilla {
  24. template<typename AllocPolicy>
  25. class BufferList : private AllocPolicy
  26. {
  27. // Each buffer in a BufferList has a size and a capacity. The first mSize
  28. // bytes are initialized and the remaining |mCapacity - mSize| bytes are free.
  29. struct Segment
  30. {
  31. char* mData;
  32. size_t mSize;
  33. size_t mCapacity;
  34. Segment(char* aData, size_t aSize, size_t aCapacity)
  35. : mData(aData),
  36. mSize(aSize),
  37. mCapacity(aCapacity)
  38. {
  39. }
  40. Segment(const Segment&) = delete;
  41. Segment& operator=(const Segment&) = delete;
  42. Segment(Segment&&) = default;
  43. Segment& operator=(Segment&&) = default;
  44. char* Start() const { return mData; }
  45. char* End() const { return mData + mSize; }
  46. };
  47. template<typename OtherAllocPolicy>
  48. friend class BufferList;
  49. public:
  50. // For the convenience of callers, all segments are required to be a multiple
  51. // of 8 bytes in capacity. Also, every buffer except the last one is required
  52. // to be full (i.e., size == capacity). Therefore, a byte at offset N within
  53. // the BufferList and stored in memory at an address A will satisfy
  54. // (N % Align == A % Align) if Align == 2, 4, or 8.
  55. static const size_t kSegmentAlignment = 8;
  56. // Allocate a BufferList. The BufferList will free all its buffers when it is
  57. // destroyed. An initial buffer of size aInitialSize and capacity
  58. // aInitialCapacity is allocated automatically. This data will be contiguous
  59. // an can be accessed via |Start()|. Subsequent buffers will be allocated with
  60. // capacity aStandardCapacity.
  61. BufferList(size_t aInitialSize,
  62. size_t aInitialCapacity,
  63. size_t aStandardCapacity,
  64. AllocPolicy aAP = AllocPolicy())
  65. : AllocPolicy(aAP),
  66. mOwning(true),
  67. mSegments(aAP),
  68. mSize(0),
  69. mStandardCapacity(aStandardCapacity)
  70. {
  71. MOZ_ASSERT(aInitialCapacity % kSegmentAlignment == 0);
  72. MOZ_ASSERT(aStandardCapacity % kSegmentAlignment == 0);
  73. if (aInitialCapacity) {
  74. AllocateSegment(aInitialSize, aInitialCapacity);
  75. }
  76. }
  77. BufferList(const BufferList& aOther) = delete;
  78. BufferList(BufferList&& aOther)
  79. : mOwning(aOther.mOwning),
  80. mSegments(Move(aOther.mSegments)),
  81. mSize(aOther.mSize),
  82. mStandardCapacity(aOther.mStandardCapacity)
  83. {
  84. aOther.mSegments.clear();
  85. aOther.mSize = 0;
  86. }
  87. BufferList& operator=(const BufferList& aOther) = delete;
  88. BufferList& operator=(BufferList&& aOther)
  89. {
  90. Clear();
  91. mOwning = aOther.mOwning;
  92. mSegments = Move(aOther.mSegments);
  93. mSize = aOther.mSize;
  94. aOther.mSegments.clear();
  95. aOther.mSize = 0;
  96. return *this;
  97. }
  98. ~BufferList() { Clear(); }
  99. // Returns the sum of the sizes of all the buffers.
  100. size_t Size() const { return mSize; }
  101. void Clear()
  102. {
  103. if (mOwning) {
  104. for (Segment& segment : mSegments) {
  105. this->free_(segment.mData);
  106. }
  107. }
  108. mSegments.clear();
  109. mSize = 0;
  110. }
  111. // Iterates over bytes in the segments. You can advance it by as many bytes as
  112. // you choose.
  113. class IterImpl
  114. {
  115. // Invariants:
  116. // (0) mSegment <= bufferList.mSegments.size()
  117. // (1) mData <= mDataEnd
  118. // (2) If mSegment is not the last segment, mData < mDataEnd
  119. uintptr_t mSegment;
  120. char* mData;
  121. char* mDataEnd;
  122. friend class BufferList;
  123. public:
  124. explicit IterImpl(const BufferList& aBuffers)
  125. : mSegment(0),
  126. mData(nullptr),
  127. mDataEnd(nullptr)
  128. {
  129. if (!aBuffers.mSegments.empty()) {
  130. mData = aBuffers.mSegments[0].Start();
  131. mDataEnd = aBuffers.mSegments[0].End();
  132. }
  133. }
  134. // Returns a pointer to the raw data. It is valid to access up to
  135. // RemainingInSegment bytes of this buffer.
  136. char* Data() const
  137. {
  138. MOZ_RELEASE_ASSERT(!Done());
  139. return mData;
  140. }
  141. // Returns true if the memory in the range [Data(), Data() + aBytes) is all
  142. // part of one contiguous buffer.
  143. bool HasRoomFor(size_t aBytes) const
  144. {
  145. MOZ_RELEASE_ASSERT(mData <= mDataEnd);
  146. return size_t(mDataEnd - mData) >= aBytes;
  147. }
  148. // Returns the maximum value aBytes for which HasRoomFor(aBytes) will be
  149. // true.
  150. size_t RemainingInSegment() const
  151. {
  152. MOZ_RELEASE_ASSERT(mData <= mDataEnd);
  153. return mDataEnd - mData;
  154. }
  155. // Advances the iterator by aBytes bytes. aBytes must be less than
  156. // RemainingInSegment(). If advancing by aBytes takes the iterator to the
  157. // end of a buffer, it will be moved to the beginning of the next buffer
  158. // unless it is the last buffer.
  159. void Advance(const BufferList& aBuffers, size_t aBytes)
  160. {
  161. const Segment& segment = aBuffers.mSegments[mSegment];
  162. MOZ_RELEASE_ASSERT(segment.Start() <= mData);
  163. MOZ_RELEASE_ASSERT(mData <= mDataEnd);
  164. MOZ_RELEASE_ASSERT(mDataEnd == segment.End());
  165. MOZ_RELEASE_ASSERT(HasRoomFor(aBytes));
  166. mData += aBytes;
  167. if (mData == mDataEnd && mSegment + 1 < aBuffers.mSegments.length()) {
  168. mSegment++;
  169. const Segment& nextSegment = aBuffers.mSegments[mSegment];
  170. mData = nextSegment.Start();
  171. mDataEnd = nextSegment.End();
  172. MOZ_RELEASE_ASSERT(mData < mDataEnd);
  173. }
  174. }
  175. // Advance the iterator by aBytes, possibly crossing segments. This function
  176. // returns false if it runs out of buffers to advance through. Otherwise it
  177. // returns true.
  178. bool AdvanceAcrossSegments(const BufferList& aBuffers, size_t aBytes)
  179. {
  180. size_t bytes = aBytes;
  181. while (bytes) {
  182. size_t toAdvance = std::min(bytes, RemainingInSegment());
  183. if (!toAdvance) {
  184. return false;
  185. }
  186. Advance(aBuffers, toAdvance);
  187. bytes -= toAdvance;
  188. }
  189. return true;
  190. }
  191. // Returns true when the iterator reaches the end of the BufferList.
  192. bool Done() const
  193. {
  194. return mData == mDataEnd;
  195. }
  196. private:
  197. // Count the bytes we would need to advance in order to reach aTarget.
  198. size_t BytesUntil(const BufferList& aBuffers, const IterImpl& aTarget) const {
  199. size_t offset = 0;
  200. MOZ_ASSERT(aTarget.IsIn(aBuffers));
  201. char* data = mData;
  202. for (uintptr_t segment = mSegment; segment < aTarget.mSegment; segment++) {
  203. offset += aBuffers.mSegments[segment].End() - data;
  204. data = aBuffers.mSegments[segment].mData;
  205. }
  206. MOZ_RELEASE_ASSERT(IsIn(aBuffers));
  207. MOZ_RELEASE_ASSERT(aTarget.mData >= data);
  208. offset += aTarget.mData - data;
  209. return offset;
  210. }
  211. bool IsIn(const BufferList& aBuffers) const {
  212. return mSegment < aBuffers.mSegments.length() &&
  213. mData >= aBuffers.mSegments[mSegment].mData &&
  214. mData < aBuffers.mSegments[mSegment].End();
  215. }
  216. };
  217. // Special convenience method that returns Iter().Data().
  218. char* Start() { return mSegments[0].mData; }
  219. const char* Start() const { return mSegments[0].mData; }
  220. IterImpl Iter() const { return IterImpl(*this); }
  221. // Copies aSize bytes from aData into the BufferList. The storage for these
  222. // bytes may be split across multiple buffers. Size() is increased by aSize.
  223. inline bool WriteBytes(const char* aData, size_t aSize);
  224. // Copies possibly non-contiguous byte range starting at aIter into
  225. // aData. aIter is advanced by aSize bytes. Returns false if it runs out of
  226. // data before aSize.
  227. inline bool ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const;
  228. // Return a new BufferList that shares storage with this BufferList. The new
  229. // BufferList is read-only. It allows iteration over aSize bytes starting at
  230. // aIter. Borrow can fail, in which case *aSuccess will be false upon
  231. // return. The borrowed BufferList can use a different AllocPolicy than the
  232. // original one. However, it is not responsible for freeing buffers, so the
  233. // AllocPolicy is only used for the buffer vector.
  234. template<typename BorrowingAllocPolicy>
  235. BufferList<BorrowingAllocPolicy> Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
  236. BorrowingAllocPolicy aAP = BorrowingAllocPolicy()) const;
  237. // Return a new BufferList and move storage from this BufferList to it. The
  238. // new BufferList owns the buffers. Move can fail, in which case *aSuccess
  239. // will be false upon return. The new BufferList can use a different
  240. // AllocPolicy than the original one. The new OtherAllocPolicy is responsible
  241. // for freeing buffers, so the OtherAllocPolicy must use freeing method
  242. // compatible to the original one.
  243. template<typename OtherAllocPolicy>
  244. BufferList<OtherAllocPolicy> MoveFallible(bool* aSuccess, OtherAllocPolicy aAP = OtherAllocPolicy());
  245. // Return a new BufferList that adopts the byte range starting at Iter so that
  246. // range [aIter, aIter + aSize) is transplanted to the returned BufferList.
  247. // Contents of the buffer before aIter + aSize is left undefined.
  248. // Extract can fail, in which case *aSuccess will be false upon return. The
  249. // moved buffers are erased from the original BufferList. In case of extract
  250. // fails, the original BufferList is intact. All other iterators except aIter
  251. // are invalidated.
  252. // This method requires aIter and aSize to be 8-byte aligned.
  253. BufferList Extract(IterImpl& aIter, size_t aSize, bool* aSuccess);
  254. // Return the number of bytes from 'start' to 'end', two iterators within
  255. // this BufferList.
  256. size_t RangeLength(const IterImpl& start, const IterImpl& end) const {
  257. MOZ_ASSERT(start.IsIn(*this) && end.IsIn(*this));
  258. return start.BytesUntil(*this, end);
  259. }
  260. private:
  261. explicit BufferList(AllocPolicy aAP)
  262. : AllocPolicy(aAP),
  263. mOwning(false),
  264. mSize(0),
  265. mStandardCapacity(0)
  266. {
  267. }
  268. void* AllocateSegment(size_t aSize, size_t aCapacity)
  269. {
  270. MOZ_RELEASE_ASSERT(mOwning);
  271. char* data = this->template pod_malloc<char>(aCapacity);
  272. if (!data) {
  273. return nullptr;
  274. }
  275. if (!mSegments.append(Segment(data, aSize, aCapacity))) {
  276. this->free_(data);
  277. return nullptr;
  278. }
  279. mSize += aSize;
  280. return data;
  281. }
  282. bool mOwning;
  283. Vector<Segment, 1, AllocPolicy> mSegments;
  284. size_t mSize;
  285. size_t mStandardCapacity;
  286. };
  287. template<typename AllocPolicy>
  288. bool
  289. BufferList<AllocPolicy>::WriteBytes(const char* aData, size_t aSize)
  290. {
  291. MOZ_RELEASE_ASSERT(mOwning);
  292. MOZ_RELEASE_ASSERT(mStandardCapacity);
  293. size_t copied = 0;
  294. size_t remaining = aSize;
  295. if (!mSegments.empty()) {
  296. Segment& lastSegment = mSegments.back();
  297. size_t toCopy = std::min(aSize, lastSegment.mCapacity - lastSegment.mSize);
  298. memcpy(lastSegment.mData + lastSegment.mSize, aData, toCopy);
  299. lastSegment.mSize += toCopy;
  300. mSize += toCopy;
  301. copied += toCopy;
  302. remaining -= toCopy;
  303. }
  304. while (remaining) {
  305. size_t toCopy = std::min(remaining, mStandardCapacity);
  306. void* data = AllocateSegment(toCopy, mStandardCapacity);
  307. if (!data) {
  308. return false;
  309. }
  310. memcpy(data, aData + copied, toCopy);
  311. copied += toCopy;
  312. remaining -= toCopy;
  313. }
  314. return true;
  315. }
  316. template<typename AllocPolicy>
  317. bool
  318. BufferList<AllocPolicy>::ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const
  319. {
  320. size_t copied = 0;
  321. size_t remaining = aSize;
  322. while (remaining) {
  323. size_t toCopy = std::min(aIter.RemainingInSegment(), remaining);
  324. if (!toCopy) {
  325. // We've run out of data in the last segment.
  326. return false;
  327. }
  328. memcpy(aData + copied, aIter.Data(), toCopy);
  329. copied += toCopy;
  330. remaining -= toCopy;
  331. aIter.Advance(*this, toCopy);
  332. }
  333. return true;
  334. }
  335. template<typename AllocPolicy> template<typename BorrowingAllocPolicy>
  336. BufferList<BorrowingAllocPolicy>
  337. BufferList<AllocPolicy>::Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
  338. BorrowingAllocPolicy aAP) const
  339. {
  340. BufferList<BorrowingAllocPolicy> result(aAP);
  341. size_t size = aSize;
  342. while (size) {
  343. size_t toAdvance = std::min(size, aIter.RemainingInSegment());
  344. if (!toAdvance || !result.mSegments.append(typename BufferList<BorrowingAllocPolicy>::Segment(aIter.mData, toAdvance, toAdvance))) {
  345. *aSuccess = false;
  346. return result;
  347. }
  348. aIter.Advance(*this, toAdvance);
  349. size -= toAdvance;
  350. }
  351. result.mSize = aSize;
  352. *aSuccess = true;
  353. return result;
  354. }
  355. template<typename AllocPolicy> template<typename OtherAllocPolicy>
  356. BufferList<OtherAllocPolicy>
  357. BufferList<AllocPolicy>::MoveFallible(bool* aSuccess, OtherAllocPolicy aAP)
  358. {
  359. BufferList<OtherAllocPolicy> result(0, 0, mStandardCapacity, aAP);
  360. IterImpl iter = Iter();
  361. while (!iter.Done()) {
  362. size_t toAdvance = iter.RemainingInSegment();
  363. if (!toAdvance || !result.mSegments.append(typename BufferList<OtherAllocPolicy>::Segment(iter.mData, toAdvance, toAdvance))) {
  364. *aSuccess = false;
  365. result.mSegments.clear();
  366. return result;
  367. }
  368. iter.Advance(*this, toAdvance);
  369. }
  370. result.mSize = mSize;
  371. mSegments.clear();
  372. mSize = 0;
  373. *aSuccess = true;
  374. return result;
  375. }
  376. template<typename AllocPolicy>
  377. BufferList<AllocPolicy>
  378. BufferList<AllocPolicy>::Extract(IterImpl& aIter, size_t aSize, bool* aSuccess)
  379. {
  380. MOZ_RELEASE_ASSERT(aSize);
  381. MOZ_RELEASE_ASSERT(mOwning);
  382. MOZ_ASSERT(aSize % kSegmentAlignment == 0);
  383. MOZ_ASSERT(intptr_t(aIter.mData) % kSegmentAlignment == 0);
  384. auto failure = [this, aSuccess]() {
  385. *aSuccess = false;
  386. return BufferList(0, 0, mStandardCapacity);
  387. };
  388. // Number of segments we'll need to copy data from to satisfy the request.
  389. size_t segmentsNeeded = 0;
  390. // If this is None then the last segment is a full segment, otherwise we need
  391. // to copy this many bytes.
  392. Maybe<size_t> lastSegmentSize;
  393. {
  394. // Copy of the iterator to walk the BufferList and see how many segments we
  395. // need to copy.
  396. IterImpl iter = aIter;
  397. size_t remaining = aSize;
  398. while (!iter.Done() && remaining &&
  399. remaining >= iter.RemainingInSegment()) {
  400. remaining -= iter.RemainingInSegment();
  401. iter.Advance(*this, iter.RemainingInSegment());
  402. segmentsNeeded++;
  403. }
  404. if (remaining) {
  405. if (iter.Done()) {
  406. // We reached the end of the BufferList and there wasn't enough data to
  407. // satisfy the request.
  408. return failure();
  409. }
  410. lastSegmentSize.emplace(remaining);
  411. // The last block also counts as a segment. This makes the conditionals
  412. // on segmentsNeeded work in the rest of the function.
  413. segmentsNeeded++;
  414. }
  415. }
  416. BufferList result(0, 0, mStandardCapacity);
  417. if (!result.mSegments.reserve(segmentsNeeded + lastSegmentSize.isSome())) {
  418. return failure();
  419. }
  420. // Copy the first segment, it's special because we can't just steal the
  421. // entire Segment struct from this->mSegments.
  422. size_t firstSegmentSize = std::min(aSize, aIter.RemainingInSegment());
  423. if (!result.WriteBytes(aIter.Data(), firstSegmentSize)) {
  424. return failure();
  425. }
  426. aIter.Advance(*this, firstSegmentSize);
  427. segmentsNeeded--;
  428. // The entirety of the request wasn't in the first segment, now copy the
  429. // rest.
  430. if (segmentsNeeded) {
  431. char* finalSegment = nullptr;
  432. // Pre-allocate the final segment so that if this fails, we return before
  433. // we delete the elements from |this->mSegments|.
  434. if (lastSegmentSize.isSome()) {
  435. MOZ_RELEASE_ASSERT(mStandardCapacity >= *lastSegmentSize);
  436. finalSegment = this->template pod_malloc<char>(mStandardCapacity);
  437. if (!finalSegment) {
  438. return failure();
  439. }
  440. }
  441. size_t copyStart = aIter.mSegment;
  442. // Copy segments from this over to the result and remove them from our
  443. // storage. Not needed if the only segment we need to copy is the last
  444. // partial one.
  445. size_t segmentsToCopy = segmentsNeeded - lastSegmentSize.isSome();
  446. for (size_t i = 0; i < segmentsToCopy; ++i) {
  447. result.mSegments.infallibleAppend(
  448. Segment(mSegments[aIter.mSegment].mData,
  449. mSegments[aIter.mSegment].mSize,
  450. mSegments[aIter.mSegment].mCapacity));
  451. aIter.Advance(*this, aIter.RemainingInSegment());
  452. }
  453. // Due to the way IterImpl works, there are two cases here: (1) if we've
  454. // consumed the entirety of the BufferList, then the iterator is pointed at
  455. // the end of the final segment, (2) otherwise it is pointed at the start
  456. // of the next segment. We want to verify that we really consumed all
  457. // |segmentsToCopy| segments.
  458. MOZ_RELEASE_ASSERT(
  459. (aIter.mSegment == copyStart + segmentsToCopy) ||
  460. (aIter.Done() && aIter.mSegment == copyStart + segmentsToCopy - 1));
  461. mSegments.erase(mSegments.begin() + copyStart,
  462. mSegments.begin() + copyStart + segmentsToCopy);
  463. // Reset the iter's position for what we just deleted.
  464. aIter.mSegment -= segmentsToCopy;
  465. if (lastSegmentSize.isSome()) {
  466. // We called reserve() on result.mSegments so infallibleAppend is safe.
  467. result.mSegments.infallibleAppend(
  468. Segment(finalSegment, 0, mStandardCapacity));
  469. bool r = result.WriteBytes(aIter.Data(), *lastSegmentSize);
  470. MOZ_RELEASE_ASSERT(r);
  471. aIter.Advance(*this, *lastSegmentSize);
  472. }
  473. }
  474. mSize -= aSize;
  475. result.mSize = aSize;
  476. *aSuccess = true;
  477. return result;
  478. }
  479. } // namespace mozilla
  480. #endif /* mozilla_BufferList_h */