Bug 1262671 - Introduce MFBT BufferList class (r=froydnj)
authorBill McCloskey <billm@mozilla.com>
Wed, 11 May 2016 18:02:06 -0700
changeset 372288 010987e0dc81f5021cf3b200ceab78d742783d21
parent 372287 c3b21c100d396a74f2ef871a0e05fc3120052ab9
child 372289 b6fd41905d10140c620d3ee794cec0e3a3994c89
push id19496
push userdmitchell@mozilla.com
push dateFri, 27 May 2016 22:17:17 +0000
reviewersfroydnj
bugs1262671
milestone49.0a1
Bug 1262671 - Introduce MFBT BufferList class (r=froydnj)
memory/mozalloc/mozalloc.h
mfbt/AllocPolicy.h
mfbt/BufferList.h
mfbt/moz.build
mfbt/tests/TestBufferList.cpp
mfbt/tests/moz.build
--- a/memory/mozalloc/mozalloc.h
+++ b/memory/mozalloc/mozalloc.h
@@ -315,16 +315,21 @@ public:
     void free_(void* aPtr)
     {
         free_impl(aPtr);
     }
 
     void reportAllocOverflow() const
     {
     }
+
+    bool checkSimulatedOOM() const
+    {
+        return true;
+    }
 };
 
 #endif  /* ifdef __cplusplus */
 
 #ifdef malloc_impl_
 #undef malloc_impl_
 #undef malloc_impl
 #endif
--- a/mfbt/AllocPolicy.h
+++ b/mfbt/AllocPolicy.h
@@ -7,16 +7,17 @@
 /*
  * An allocation policy concept, usable for structures and algorithms to
  * control how memory is allocated and how failures are handled.
  */
 
 #ifndef mozilla_AllocPolicy_h
 #define mozilla_AllocPolicy_h
 
+#include "mozilla/Attributes.h"
 #include "mozilla/TemplateLib.h"
 
 #include <stddef.h>
 #include <stdlib.h>
 
 namespace mozilla {
 
 /*
new file mode 100644
--- /dev/null
+++ b/mfbt/BufferList.h
@@ -0,0 +1,435 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_BufferList_h
+#define mozilla_BufferList_h
+
+#include <algorithm>
+#include "mozilla/AllocPolicy.h"
+#include "mozilla/Move.h"
+#include "mozilla/Types.h"
+#include "mozilla/TypeTraits.h"
+#include "mozilla/Vector.h"
+#include <string.h>
+
+// BufferList represents a sequence of buffers of data. A BufferList can choose
+// to own its buffers or not. The class handles writing to the buffers,
+// iterating over them, and reading data out. Unlike SegmentedVector, the
+// buffers may be of unequal size. Like SegmentedVector, BufferList is a nice
+// way to avoid large contiguous allocations (which can trigger OOMs).
+
+namespace mozilla {
+
+template<typename AllocPolicy>
+class BufferList : private AllocPolicy
+{
+  // Each buffer in a BufferList has a size and a capacity. The first mSize
+  // bytes are initialized and the remaining |mCapacity - mSize| bytes are free.
+  struct Segment
+  {
+    char* mData;
+    size_t mSize;
+    size_t mCapacity;
+
+    Segment(char* aData, size_t aSize, size_t aCapacity)
+     : mData(aData),
+       mSize(aSize),
+       mCapacity(aCapacity)
+    {
+    }
+
+    Segment(const Segment&) = delete;
+    Segment& operator=(const Segment&) = delete;
+
+    Segment(Segment&&) = default;
+    Segment& operator=(Segment&&) = default;
+
+    char* Start() const { return mData; }
+    char* End() const { return mData + mSize; }
+  };
+
+ public:
+  // For the convenience of callers, all segments are required to be a multiple
+  // of 8 bytes in capacity. Also, every buffer except the last one is required
+  // to be full (i.e., size == capacity). Therefore, a byte at offset N within
+  // the BufferList and stored in memory at an address A will satisfy
+  // (N % Align == A % Align) if Align == 2, 4, or 8.
+  //
+  // NB: FlattenBytes can create non-full segments in the middle of the
+  // list. However, it ensures that these buffers are 8-byte aligned, so the
+  // offset invariant is not violated.
+  static const size_t kSegmentAlignment = 8;
+
+  // Allocate a BufferList. The BufferList will free all its buffers when it is
+  // destroyed. An initial buffer of size aInitialSize and capacity
+  // aInitialCapacity is allocated automatically. This data will be contiguous
+  // an can be accessed via |Start()|. Subsequent buffers will be allocated with
+  // capacity aStandardCapacity.
+  BufferList(size_t aInitialSize,
+             size_t aInitialCapacity,
+             size_t aStandardCapacity,
+             AllocPolicy aAP = AllocPolicy())
+   : AllocPolicy(aAP),
+     mOwning(true),
+     mSize(0),
+     mStandardCapacity(aStandardCapacity)
+  {
+    MOZ_ASSERT(aInitialCapacity % kSegmentAlignment == 0);
+    MOZ_ASSERT(aStandardCapacity % kSegmentAlignment == 0);
+
+    if (aInitialCapacity) {
+      AllocateSegment(aInitialSize, aInitialCapacity);
+    }
+  }
+
+  BufferList(const BufferList& aOther) = delete;
+
+  BufferList(BufferList&& aOther)
+   : mOwning(aOther.mOwning),
+     mSegments(Move(aOther.mSegments)),
+     mSize(aOther.mSize),
+     mStandardCapacity(aOther.mStandardCapacity)
+  {
+    aOther.mSegments.clear();
+    aOther.mSize = 0;
+  }
+
+  BufferList& operator=(const BufferList& aOther) = delete;
+
+  BufferList& operator=(BufferList&& aOther)
+  {
+    Clear();
+
+    mOwning = aOther.mOwning;
+    mSegments = Move(aOther.mSegments);
+    mSize = aOther.mSize;
+    aOther.mSegments.clear();
+    aOther.mSize = 0;
+    return *this;
+  }
+
+  ~BufferList() { Clear(); }
+
+  // Returns the sum of the sizes of all the buffers.
+  size_t Size() const { return mSize; }
+
+  void Clear()
+  {
+    if (mOwning) {
+      for (Segment& segment : mSegments) {
+        this->free_(segment.mData);
+      }
+    }
+    mSegments.clear();
+
+    mSize = 0;
+  }
+
+  // Iterates over bytes in the segments. You can advance it by as many bytes as
+  // you choose.
+  class IterImpl
+  {
+    // Invariants:
+    //   (0) mSegment <= bufferList.mSegments.size()
+    //   (1) mData <= mDataEnd
+    //   (2) If mSegment is not the last segment, mData < mDataEnd
+    uintptr_t mSegment;
+    char* mData;
+    char* mDataEnd;
+
+    friend class BufferList;
+
+  public:
+    explicit IterImpl(const BufferList& aBuffers)
+     : mSegment(0),
+       mData(nullptr),
+       mDataEnd(nullptr)
+    {
+      if (!aBuffers.mSegments.empty()) {
+        mData = aBuffers.mSegments[0].Start();
+        mDataEnd = aBuffers.mSegments[0].End();
+      }
+    }
+
+    // Returns a pointer to the raw data. It is valid to access up to
+    // RemainingInSegment bytes of this buffer.
+    char* Data() const
+    {
+      MOZ_RELEASE_ASSERT(!Done());
+      return mData;
+    }
+
+    // Returns true if the memory in the range [Data(), Data() + aBytes) is all
+    // part of one contiguous buffer.
+    bool HasRoomFor(size_t aBytes) const
+    {
+      MOZ_RELEASE_ASSERT(mData <= mDataEnd);
+      return size_t(mDataEnd - mData) >= aBytes;
+    }
+
+    // Returns the maximum value aBytes for which HasRoomFor(aBytes) will be
+    // true.
+    size_t RemainingInSegment() const
+    {
+      MOZ_RELEASE_ASSERT(mData <= mDataEnd);
+      return mDataEnd - mData;
+    }
+
+    // Advances the iterator by aBytes bytes. aBytes must be less than
+    // RemainingInSegment(). If advancing by aBytes takes the iterator to the
+    // end of a buffer, it will be moved to the beginning of the next buffer
+    // unless it is the last buffer.
+    void Advance(const BufferList& aBuffers, size_t aBytes)
+    {
+      const Segment& segment = aBuffers.mSegments[mSegment];
+      MOZ_RELEASE_ASSERT(segment.Start() <= mData);
+      MOZ_RELEASE_ASSERT(mData <= mDataEnd);
+      MOZ_RELEASE_ASSERT(mDataEnd == segment.End());
+
+      MOZ_RELEASE_ASSERT(HasRoomFor(aBytes));
+      mData += aBytes;
+
+      if (mData == mDataEnd && mSegment + 1 < aBuffers.mSegments.length()) {
+        mSegment++;
+        const Segment& nextSegment = aBuffers.mSegments[mSegment];
+        mData = nextSegment.Start();
+        mDataEnd = nextSegment.End();
+        MOZ_RELEASE_ASSERT(mData < mDataEnd);
+      }
+    }
+
+    // Advance the iterator by aBytes, possibly crossing segments. This function
+    // returns false if it runs out of buffers to advance through. Otherwise it
+    // returns true.
+    bool AdvanceAcrossSegments(const BufferList& aBuffers, size_t aBytes)
+    {
+      size_t bytes = aBytes;
+      while (bytes) {
+        size_t toAdvance = std::min(bytes, RemainingInSegment());
+        if (!toAdvance) {
+          return false;
+        }
+        Advance(aBuffers, toAdvance);
+        bytes -= toAdvance;
+      }
+      return true;
+    }
+
+    // Returns true when the iterator reaches the end of the BufferList.
+    bool Done() const
+    {
+      return mData == mDataEnd;
+    }
+  };
+
+  // Special convenience method that returns Iter().Data().
+  char* Start() { return mSegments[0].mData; }
+
+  IterImpl Iter() const { return IterImpl(*this); }
+
+  // Copies aSize bytes from aData into the BufferList. The storage for these
+  // bytes may be split across multiple buffers. Size() is increased by aSize.
+  inline bool WriteBytes(const char* aData, size_t aSize);
+
+  // Copies possibly non-contiguous byte range starting at aIter into
+  // aData. aIter is advanced by aSize bytes. Returns false if it runs out of
+  // data before aSize.
+  inline bool ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const;
+
+  // FlattenBytes reconfigures the BufferList so that data in the range
+  // [aIter, aIter + aSize) is stored contiguously. A pointer to this data is
+  // returned in aOutData. Returns false if not enough data is available. All
+  // other iterators are invalidated by this method.
+  //
+  // This method requires aIter and aSize to be 8-byte aligned.
+  inline bool FlattenBytes(IterImpl& aIter, const char** aOutData, size_t aSize);
+
+  // Return a new BufferList that shares storage with this BufferList. The new
+  // BufferList is read-only. It allows iteration over aSize bytes starting at
+  // aIter. Borrow can fail, in which case *aSuccess will be false upon
+  // return. The borrowed BufferList can use a different AllocPolicy than the
+  // original one. However, it is not responsible for freeing buffers, so the
+  // AllocPolicy is only used for the buffer vector.
+  template<typename BorrowingAllocPolicy>
+  BufferList<BorrowingAllocPolicy> Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
+                                          BorrowingAllocPolicy aAP = BorrowingAllocPolicy());
+
+private:
+  explicit BufferList(AllocPolicy aAP)
+   : AllocPolicy(aAP),
+     mOwning(false),
+     mSize(0),
+     mStandardCapacity(0)
+  {
+  }
+
+  void* AllocateSegment(size_t aSize, size_t aCapacity)
+  {
+    MOZ_RELEASE_ASSERT(mOwning);
+
+    char* data = this->template pod_malloc<char>(aCapacity);
+    if (!data) {
+      return nullptr;
+    }
+    if (!mSegments.append(Segment(data, aSize, aCapacity))) {
+      this->free_(data);
+      return nullptr;
+    }
+    mSize += aSize;
+    return data;
+  }
+
+  bool mOwning;
+  Vector<Segment, 1, AllocPolicy> mSegments;
+  size_t mSize;
+  size_t mStandardCapacity;
+};
+
+template<typename AllocPolicy>
+bool
+BufferList<AllocPolicy>::WriteBytes(const char* aData, size_t aSize)
+{
+  MOZ_RELEASE_ASSERT(mOwning);
+  MOZ_RELEASE_ASSERT(mStandardCapacity);
+
+  size_t copied = 0;
+  size_t remaining = aSize;
+
+  if (!mSegments.empty()) {
+    Segment& lastSegment = mSegments.back();
+
+    size_t toCopy = std::min(aSize, lastSegment.mCapacity - lastSegment.mSize);
+    memcpy(lastSegment.mData + lastSegment.mSize, aData, toCopy);
+    lastSegment.mSize += toCopy;
+    mSize += toCopy;
+
+    copied += toCopy;
+    remaining -= toCopy;
+  }
+
+  while (remaining) {
+    size_t toCopy = std::min(remaining, mStandardCapacity);
+
+    void* data = AllocateSegment(toCopy, mStandardCapacity);
+    if (!data) {
+      return false;
+    }
+    memcpy(data, aData + copied, toCopy);
+
+    copied += toCopy;
+    remaining -= toCopy;
+  }
+
+  return true;
+}
+
+template<typename AllocPolicy>
+bool
+BufferList<AllocPolicy>::ReadBytes(IterImpl& aIter, char* aData, size_t aSize) const
+{
+  size_t copied = 0;
+  size_t remaining = aSize;
+  while (remaining) {
+    size_t toCopy = std::min(aIter.RemainingInSegment(), remaining);
+    if (!toCopy) {
+      // We've run out of data in the last segment.
+      return false;
+    }
+    memcpy(aData + copied, aIter.Data(), toCopy);
+    copied += toCopy;
+    remaining -= toCopy;
+
+    aIter.Advance(*this, toCopy);
+  }
+
+  return true;
+}
+
+template<typename AllocPolicy>
+bool
+BufferList<AllocPolicy>::FlattenBytes(IterImpl& aIter, const char** aOutData, size_t aSize)
+{
+  MOZ_RELEASE_ASSERT(aSize);
+  MOZ_RELEASE_ASSERT(mOwning);
+
+  if (aIter.HasRoomFor(aSize)) {
+    // If the data is already contiguous, just return a pointer.
+    *aOutData = aIter.Data();
+    aIter.Advance(*this, aSize);
+    return true;
+  }
+
+  // This buffer will become the new contiguous segment.
+  char* buffer = this->template pod_malloc<char>(Size());
+  if (!buffer) {
+    return false;
+  }
+
+  size_t copied = 0;
+  size_t offset;
+  bool found = false;
+  for (size_t i = 0; i < mSegments.length(); i++) {
+    Segment& segment = mSegments[i];
+    memcpy(buffer + copied, segment.Start(), segment.mSize);
+
+    if (i == aIter.mSegment) {
+      offset = copied + (aIter.mData - segment.Start());
+
+      // Do we have aSize bytes after aIter?
+      if (Size() - offset >= aSize) {
+        found = true;
+        *aOutData = buffer + offset;
+
+        aIter.mSegment = 0;
+        aIter.mData = buffer + offset + aSize;
+        aIter.mDataEnd = buffer + Size();
+      }
+    }
+
+    this->free_(segment.mData);
+
+    copied += segment.mSize;
+  }
+
+  mSegments.clear();
+  mSegments.infallibleAppend(Segment(buffer, Size(), Size()));
+
+  if (!found) {
+    aIter.mSegment = 0;
+    aIter.mData = Start();
+    aIter.mDataEnd = Start() + Size();
+  }
+
+  return found;
+}
+
+template<typename AllocPolicy> template<typename BorrowingAllocPolicy>
+BufferList<BorrowingAllocPolicy>
+BufferList<AllocPolicy>::Borrow(IterImpl& aIter, size_t aSize, bool* aSuccess,
+                                BorrowingAllocPolicy aAP)
+{
+  BufferList<BorrowingAllocPolicy> result(aAP);
+
+  size_t size = aSize;
+  while (size) {
+    size_t toAdvance = std::min(size, aIter.RemainingInSegment());
+
+    if (!toAdvance || !result.mSegments.append(Segment(aIter.mData, toAdvance, toAdvance))) {
+      *aSuccess = false;
+      return result;
+    }
+    aIter.Advance(*this, toAdvance);
+    size -= toAdvance;
+  }
+
+  result.mSize = aSize;
+  *aSuccess = true;
+  return result;
+}
+
+} // namespace mozilla
+
+#endif /* mozilla_BufferList_h */
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -19,16 +19,17 @@ EXPORTS.mozilla = [
     'AlreadyAddRefed.h',
     'Array.h',
     'ArrayUtils.h',
     'Assertions.h',
     'Atomics.h',
     'Attributes.h',
     'BinarySearch.h',
     'BloomFilter.h',
+    'BufferList.h',
     'Casting.h',
     'ChaosMode.h',
     'Char16.h',
     'CheckedInt.h',
     'Compiler.h',
     'Compression.h',
     'DebugOnly.h',
     'decimal/Decimal.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestBufferList.cpp
@@ -0,0 +1,243 @@
+/* -*- Mode: C++; tab-width: 9; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+// This is included first to ensure it doesn't implicitly depend on anything
+// else.
+#include "mozilla/BufferList.h"
+
+// It would be nice if we could use the InfallibleAllocPolicy from mozalloc,
+// but MFBT cannot use mozalloc.
+class InfallibleAllocPolicy
+{
+public:
+  template <typename T>
+  T* pod_malloc(size_t aNumElems)
+  {
+    if (aNumElems & mozilla::tl::MulOverflowMask<sizeof(T)>::value) {
+      MOZ_CRASH("TestBufferList.cpp: overflow");
+    }
+    T* rv = static_cast<T*>(malloc(aNumElems * sizeof(T)));
+    if (!rv) {
+      MOZ_CRASH("TestBufferList.cpp: out of memory");
+    }
+    return rv;
+  }
+
+  void free_(void* aPtr) { free(aPtr); }
+
+  void reportAllocOverflow() const {}
+
+  bool checkSimulatedOOM() const { return true; }
+};
+
+typedef mozilla::BufferList<InfallibleAllocPolicy> BufferList;
+
+int main(void)
+{
+  const size_t kInitialSize = 16;
+  const size_t kInitialCapacity = 24;
+  const size_t kStandardCapacity = 32;
+
+  BufferList bl(kInitialSize, kInitialCapacity, kStandardCapacity);
+
+  memset(bl.Start(), 0x0c, kInitialSize);
+  MOZ_RELEASE_ASSERT(bl.Size() == kInitialSize);
+
+  // Simple iteration and access.
+
+  BufferList::IterImpl iter(bl.Iter());
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize);
+  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize));
+  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(kInitialSize + 1));
+  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(size_t(-1)));
+  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
+  MOZ_RELEASE_ASSERT(!iter.Done());
+
+  iter.Advance(bl, 4);
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize - 4);
+  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize - 4));
+  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
+  MOZ_RELEASE_ASSERT(!iter.Done());
+
+  iter.Advance(bl, 11);
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize - 4 - 11);
+  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize - 4 - 11));
+  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(kInitialSize - 4 - 11 + 1));
+  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
+  MOZ_RELEASE_ASSERT(!iter.Done());
+
+  iter.Advance(bl, kInitialSize - 4 - 11);
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 0);
+  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(1));
+  MOZ_RELEASE_ASSERT(iter.Done());
+
+  // Writing to the buffer.
+
+  const size_t kSmallWrite = 16;
+
+  char toWrite[kSmallWrite];
+  memset(toWrite, 0x0a, kSmallWrite);
+  bl.WriteBytes(toWrite, kSmallWrite);
+
+  MOZ_RELEASE_ASSERT(bl.Size() == kInitialSize + kSmallWrite);
+
+  iter = bl.Iter();
+  iter.Advance(bl, kInitialSize);
+  MOZ_RELEASE_ASSERT(!iter.Done());
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialCapacity - kInitialSize);
+  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialCapacity - kInitialSize));
+  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);
+
+  // AdvanceAcrossSegments.
+
+  iter = bl.Iter();
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kInitialCapacity - 4));
+  MOZ_RELEASE_ASSERT(!iter.Done());
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 4);
+  MOZ_RELEASE_ASSERT(iter.HasRoomFor(4));
+  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);
+
+  iter = bl.Iter();
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite - 4));
+  MOZ_RELEASE_ASSERT(!iter.Done());
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 4);
+  MOZ_RELEASE_ASSERT(iter.HasRoomFor(4));
+  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);
+
+  MOZ_RELEASE_ASSERT(bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite - 1));
+  MOZ_RELEASE_ASSERT(bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite));
+  MOZ_RELEASE_ASSERT(!bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite + 1));
+  MOZ_RELEASE_ASSERT(!bl.Iter().AdvanceAcrossSegments(bl, size_t(-1)));
+
+  // Reading non-contiguous bytes.
+
+  char toRead[kSmallWrite];
+  iter = bl.Iter();
+  iter.Advance(bl, kInitialSize);
+  bl.ReadBytes(iter, toRead, kSmallWrite);
+  MOZ_RELEASE_ASSERT(memcmp(toRead, toWrite, kSmallWrite) == 0);
+  MOZ_RELEASE_ASSERT(iter.Done());
+
+  // Make sure reading up to the end of a segment advances the iter to the next
+  // segment.
+  iter = bl.Iter();
+  bl.ReadBytes(iter, toRead, kInitialSize);
+  MOZ_RELEASE_ASSERT(!iter.Done());
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialCapacity - kInitialSize);
+
+  const size_t kBigWrite = 1024;
+
+  char* toWriteBig = static_cast<char*>(malloc(kBigWrite));
+  for (unsigned i = 0; i < kBigWrite; i++) {
+    toWriteBig[i] = i % 37;
+  }
+  bl.WriteBytes(toWriteBig, kBigWrite);
+
+  char* toReadBig = static_cast<char*>(malloc(kBigWrite));
+  iter = bl.Iter();
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite));
+  bl.ReadBytes(iter, toReadBig, kBigWrite);
+  MOZ_RELEASE_ASSERT(memcmp(toReadBig, toWriteBig, kBigWrite) == 0);
+  MOZ_RELEASE_ASSERT(iter.Done());
+
+  free(toReadBig);
+  free(toWriteBig);
+
+  // Currently bl contains these segments:
+  // #0: offset 0, [0x0c]*16 + [0x0a]*8, size 24
+  // #1: offset 24, [0x0a]*8 + [i%37 for i in 0..24], size 32
+  // #2: offset 56, [i%37 for i in 24..56, size 32
+  // ...
+  // #32: offset 1016, [i%37 for i in 984..1016], size 32
+  // #33: offset 1048, [i%37 for i in 1016..1024], size 8
+
+  static size_t kTotalSize = kInitialSize + kSmallWrite + kBigWrite;
+
+  MOZ_RELEASE_ASSERT(bl.Size() == kTotalSize);
+
+  static size_t kLastSegmentSize = (kTotalSize - kInitialCapacity) % kStandardCapacity;
+
+  iter = bl.Iter();
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kTotalSize - kLastSegmentSize - kStandardCapacity));
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kStandardCapacity);
+  iter.Advance(bl, kStandardCapacity);
+  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kLastSegmentSize);
+  MOZ_RELEASE_ASSERT(unsigned(*iter.Data()) == (kTotalSize - kLastSegmentSize - kInitialSize - kSmallWrite) % 37);
+
+  // Flattening.
+
+  const size_t kFlattenSize = 1000;
+
+  const char* flat;
+  iter = bl.Iter();
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kInitialSize));
+  MOZ_RELEASE_ASSERT(bl.FlattenBytes(iter, &flat, kFlattenSize));
+  MOZ_RELEASE_ASSERT(flat[0] == 0x0a);
+  MOZ_RELEASE_ASSERT(flat[kSmallWrite / 2] == 0x0a);
+  for (size_t i = kSmallWrite; i < kFlattenSize; i++) {
+    MOZ_RELEASE_ASSERT(unsigned(flat[i]) == (i - kSmallWrite) % 37);
+  }
+  MOZ_RELEASE_ASSERT(unsigned(*iter.Data()) == (kFlattenSize - kSmallWrite) % 37);
+
+  const size_t kSecondFlattenSize = 40;
+
+  MOZ_RELEASE_ASSERT(bl.FlattenBytes(iter, &flat, kSecondFlattenSize));
+  for (size_t i = 0; i < kSecondFlattenSize; i++) {
+    MOZ_RELEASE_ASSERT(unsigned(flat[i]) == (i + kFlattenSize - kInitialSize) % 37);
+  }
+  MOZ_RELEASE_ASSERT(iter.Done());
+
+  // Clear.
+
+  bl.Clear();
+  MOZ_RELEASE_ASSERT(bl.Size() == 0);
+  MOZ_RELEASE_ASSERT(bl.Iter().Done());
+
+  // Move assignment.
+
+  const size_t kSmallCapacity = 8;
+
+  BufferList bl2(0, kSmallCapacity, kSmallCapacity);
+  bl2.WriteBytes(toWrite, kSmallWrite);
+  bl2.WriteBytes(toWrite, kSmallWrite);
+  bl2.WriteBytes(toWrite, kSmallWrite);
+
+  bl = mozilla::Move(bl2);
+  MOZ_RELEASE_ASSERT(bl2.Size() == 0);
+  MOZ_RELEASE_ASSERT(bl2.Iter().Done());
+
+  iter = bl.Iter();
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kSmallWrite * 3));
+  MOZ_RELEASE_ASSERT(iter.Done());
+
+  // Borrowing.
+
+  const size_t kBorrowStart = 4;
+  const size_t kBorrowSize = 24;
+
+  iter = bl.Iter();
+  iter.Advance(bl, kBorrowStart);
+  bool success;
+  bl2 = bl.Borrow<InfallibleAllocPolicy>(iter, kBorrowSize, &success);
+  MOZ_RELEASE_ASSERT(success);
+  MOZ_RELEASE_ASSERT(bl2.Size() == kBorrowSize);
+
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kSmallWrite * 3 - kBorrowSize - kBorrowStart));
+  MOZ_RELEASE_ASSERT(iter.Done());
+
+  iter = bl2.Iter();
+  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl2, kBorrowSize));
+  MOZ_RELEASE_ASSERT(iter.Done());
+
+  BufferList::IterImpl iter1(bl.Iter()), iter2(bl2.Iter());
+  iter1.Advance(bl, kBorrowStart);
+  MOZ_RELEASE_ASSERT(iter1.Data() == iter2.Data());
+  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl, kBorrowSize - 5));
+  MOZ_RELEASE_ASSERT(iter2.AdvanceAcrossSegments(bl2, kBorrowSize - 5));
+  MOZ_RELEASE_ASSERT(iter1.Data() == iter2.Data());
+
+  return 0;
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -4,16 +4,17 @@
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 CppUnitTests([
     'TestArrayUtils',
     'TestAtomics',
     'TestBinarySearch',
     'TestBloomFilter',
+    'TestBufferList',
     'TestCasting',
     'TestCeilingFloor',
     'TestCheckedInt',
     'TestCountPopulation',
     'TestCountZeroes',
     'TestEndian',
     'TestEnumSet',
     'TestFastBernoulliTrial',