Bug 1262671 - Introduce MFBT BufferList class (r=froydnj)
authorBill McCloskey <billm@mozilla.com>
Wed, 11 May 2016 18:02:06 -0700
changeset 340380 010987e0dc81f5021cf3b200ceab78d742783d21
parent 340379 c3b21c100d396a74f2ef871a0e05fc3120052ab9
child 340381 b6fd41905d10140c620d3ee794cec0e3a3994c89
push id1183
push userraliiev@mozilla.com
push dateMon, 05 Sep 2016 20:01:49 +0000
treeherdermozilla-release@3148731bed45 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1262671
milestone49.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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',