mfbt/tests/TestBufferList.cpp

   1 /* -*- Mode: C++; tab-width: 9; 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 file,
   5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 // This is included first to ensure it doesn't implicitly depend on anything
   8 // else.
   9 #include "mozilla/BufferList.h"
  10
  11 // It would be nice if we could use the InfallibleAllocPolicy from mozalloc,
  12 // but MFBT cannot use mozalloc.
  13 class InfallibleAllocPolicy {
  14  public:
  15   template <typename T>
  16   T* pod_malloc(size_t aNumElems) {
  17     if (aNumElems & mozilla::tl::MulOverflowMask<sizeof(T)>::value) {
  18       MOZ_CRASH("TestBufferList.cpp: overflow");
  19     }
  20     T* rv = static_cast<T*>(malloc(aNumElems * sizeof(T)));
  21     if (!rv) {
  22       MOZ_CRASH("TestBufferList.cpp: out of memory");
  23     }
  24     return rv;
  25   }
  26
  27   template <typename T>
  28   void free_(T* aPtr, size_t aNumElems = 0) {
  29     free(aPtr);
  30   }
  31
  32   void reportAllocOverflow() const {}
  33
  34   bool checkSimulatedOOM() const { return true; }
  35 };
  36
  37 typedef mozilla::BufferList<InfallibleAllocPolicy> BufferList;
  38
  39 int main(void) {
  40   const size_t kInitialSize = 16;
  41   const size_t kInitialCapacity = 24;
  42   const size_t kStandardCapacity = 32;
  43
  44   BufferList bl(kInitialSize, kInitialCapacity, kStandardCapacity);
  45
  46   memset(bl.Start(), 0x0c, kInitialSize);
  47   MOZ_RELEASE_ASSERT(bl.Size() == kInitialSize);
  48
  49   // Simple iteration and access.
  50
  51   BufferList::IterImpl iter(bl.Iter());
  52   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize);
  53   MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize));
  54   MOZ_RELEASE_ASSERT(!iter.HasRoomFor(kInitialSize + 1));
  55   MOZ_RELEASE_ASSERT(!iter.HasRoomFor(size_t(-1)));
  56   MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
  57   MOZ_RELEASE_ASSERT(!iter.Done());
  58
  59   iter.Advance(bl, 4);
  60   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize - 4);
  61   MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize - 4));
  62   MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
  63   MOZ_RELEASE_ASSERT(!iter.Done());
  64
  65   iter.Advance(bl, 11);
  66   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize - 4 - 11);
  67   MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize - 4 - 11));
  68   MOZ_RELEASE_ASSERT(!iter.HasRoomFor(kInitialSize - 4 - 11 + 1));
  69   MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
  70   MOZ_RELEASE_ASSERT(!iter.Done());
  71
  72   iter.Advance(bl, kInitialSize - 4 - 11);
  73   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 0);
  74   MOZ_RELEASE_ASSERT(!iter.HasRoomFor(1));
  75   MOZ_RELEASE_ASSERT(iter.Done());
  76
  77   // Writing to the buffer.
  78
  79   const size_t kSmallWrite = 16;
  80
  81   char toWrite[kSmallWrite];
  82   memset(toWrite, 0x0a, kSmallWrite);
  83   MOZ_ALWAYS_TRUE(bl.WriteBytes(toWrite, kSmallWrite));
  84
  85   MOZ_RELEASE_ASSERT(bl.Size() == kInitialSize + kSmallWrite);
  86
  87   iter = bl.Iter();
  88   iter.Advance(bl, kInitialSize);
  89   MOZ_RELEASE_ASSERT(!iter.Done());
  90   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() ==
  91                      kInitialCapacity - kInitialSize);
  92   MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialCapacity - kInitialSize));
  93   MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);
  94
  95   // AdvanceAcrossSegments.
  96
  97   iter = bl.Iter();
  98   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kInitialCapacity - 4));
  99   MOZ_RELEASE_ASSERT(!iter.Done());
 100   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 4);
 101   MOZ_RELEASE_ASSERT(iter.HasRoomFor(4));
 102   MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);
 103
 104   iter = bl.Iter();
 105   MOZ_RELEASE_ASSERT(
 106       iter.AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite - 4));
 107   MOZ_RELEASE_ASSERT(!iter.Done());
 108   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 4);
 109   MOZ_RELEASE_ASSERT(iter.HasRoomFor(4));
 110   MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);
 111
 112   MOZ_RELEASE_ASSERT(
 113       bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite - 1));
 114   MOZ_RELEASE_ASSERT(
 115       bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite));
 116   MOZ_RELEASE_ASSERT(
 117       !bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite + 1));
 118   MOZ_RELEASE_ASSERT(!bl.Iter().AdvanceAcrossSegments(bl, size_t(-1)));
 119
 120   // Reading non-contiguous bytes.
 121
 122   char toRead[kSmallWrite];
 123   iter = bl.Iter();
 124   iter.Advance(bl, kInitialSize);
 125   bl.ReadBytes(iter, toRead, kSmallWrite);
 126   MOZ_RELEASE_ASSERT(memcmp(toRead, toWrite, kSmallWrite) == 0);
 127   MOZ_RELEASE_ASSERT(iter.Done());
 128
 129   // Make sure reading up to the end of a segment advances the iter to the next
 130   // segment.
 131   iter = bl.Iter();
 132   bl.ReadBytes(iter, toRead, kInitialSize);
 133   MOZ_RELEASE_ASSERT(!iter.Done());
 134   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() ==
 135                      kInitialCapacity - kInitialSize);
 136
 137   const size_t kBigWrite = 1024;
 138
 139   char* toWriteBig = static_cast<char*>(malloc(kBigWrite));
 140   for (unsigned i = 0; i < kBigWrite; i++) {
 141     toWriteBig[i] = i % 37;
 142   }
 143   MOZ_ALWAYS_TRUE(bl.WriteBytes(toWriteBig, kBigWrite));
 144
 145   char* toReadBig = static_cast<char*>(malloc(kBigWrite));
 146   iter = bl.Iter();
 147   MOZ_RELEASE_ASSERT(
 148       iter.AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite));
 149   bl.ReadBytes(iter, toReadBig, kBigWrite);
 150   MOZ_RELEASE_ASSERT(memcmp(toReadBig, toWriteBig, kBigWrite) == 0);
 151   MOZ_RELEASE_ASSERT(iter.Done());
 152
 153   free(toReadBig);
 154   free(toWriteBig);
 155
 156   // Currently bl contains these segments:
 157   // #0: offset 0, [0x0c]*16 + [0x0a]*8, size 24
 158   // #1: offset 24, [0x0a]*8 + [i%37 for i in 0..24], size 32
 159   // #2: offset 56, [i%37 for i in 24..56, size 32
 160   // ...
 161   // #32: offset 1016, [i%37 for i in 984..1016], size 32
 162   // #33: offset 1048, [i%37 for i in 1016..1024], size 8
 163
 164   static size_t kTotalSize = kInitialSize + kSmallWrite + kBigWrite;
 165
 166   MOZ_RELEASE_ASSERT(bl.Size() == kTotalSize);
 167
 168   static size_t kLastSegmentSize =
 169       (kTotalSize - kInitialCapacity) % kStandardCapacity;
 170
 171   iter = bl.Iter();
 172   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(
 173       bl, kTotalSize - kLastSegmentSize - kStandardCapacity));
 174   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kStandardCapacity);
 175   iter.Advance(bl, kStandardCapacity);
 176   MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kLastSegmentSize);
 177   MOZ_RELEASE_ASSERT(
 178       unsigned(*iter.Data()) ==
 179       (kTotalSize - kLastSegmentSize - kInitialSize - kSmallWrite) % 37);
 180
 181   // Clear.
 182
 183   bl.Clear();
 184   MOZ_RELEASE_ASSERT(bl.Size() == 0);
 185   MOZ_RELEASE_ASSERT(bl.Iter().Done());
 186
 187   // Move assignment.
 188
 189   const size_t kSmallCapacity = 8;
 190
 191   BufferList bl2(0, kSmallCapacity, kSmallCapacity);
 192   MOZ_ALWAYS_TRUE(bl2.WriteBytes(toWrite, kSmallWrite));
 193   MOZ_ALWAYS_TRUE(bl2.WriteBytes(toWrite, kSmallWrite));
 194   MOZ_ALWAYS_TRUE(bl2.WriteBytes(toWrite, kSmallWrite));
 195
 196   bl = std::move(bl2);
 197   MOZ_RELEASE_ASSERT(bl2.Size() == 0);
 198   MOZ_RELEASE_ASSERT(bl2.Iter().Done());
 199
 200   iter = bl.Iter();
 201   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kSmallWrite * 3));
 202   MOZ_RELEASE_ASSERT(iter.Done());
 203
 204   // MoveFallible
 205
 206   bool success;
 207   bl2 = bl.MoveFallible<InfallibleAllocPolicy>(&success);
 208   MOZ_RELEASE_ASSERT(success);
 209   MOZ_RELEASE_ASSERT(bl.Size() == 0);
 210   MOZ_RELEASE_ASSERT(bl.Iter().Done());
 211   MOZ_RELEASE_ASSERT(bl2.Size() == kSmallWrite * 3);
 212
 213   iter = bl2.Iter();
 214   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl2, kSmallWrite * 3));
 215   MOZ_RELEASE_ASSERT(iter.Done());
 216
 217   bl = bl2.MoveFallible<InfallibleAllocPolicy>(&success);
 218
 219   // Borrowing.
 220
 221   const size_t kBorrowStart = 4;
 222   const size_t kBorrowSize = 24;
 223
 224   iter = bl.Iter();
 225   iter.Advance(bl, kBorrowStart);
 226   bl2 = bl.Borrow<InfallibleAllocPolicy>(iter, kBorrowSize, &success);
 227   MOZ_RELEASE_ASSERT(success);
 228   MOZ_RELEASE_ASSERT(bl2.Size() == kBorrowSize);
 229
 230   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(
 231       bl, kSmallWrite * 3 - kBorrowSize - kBorrowStart));
 232   MOZ_RELEASE_ASSERT(iter.Done());
 233
 234   iter = bl2.Iter();
 235   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl2, kBorrowSize));
 236   MOZ_RELEASE_ASSERT(iter.Done());
 237
 238   BufferList::IterImpl iter1(bl.Iter()), iter2(bl2.Iter());
 239   iter1.Advance(bl, kBorrowStart);
 240   MOZ_RELEASE_ASSERT(iter1.Data() == iter2.Data());
 241   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl, kBorrowSize - 5));
 242   MOZ_RELEASE_ASSERT(iter2.AdvanceAcrossSegments(bl2, kBorrowSize - 5));
 243   MOZ_RELEASE_ASSERT(iter1.Data() == iter2.Data());
 244
 245   // RangeLength.
 246
 247   BufferList bl12(0, 0, 8);
 248   MOZ_ALWAYS_TRUE(bl12.WriteBytes("abcdefgh", 8));
 249   MOZ_ALWAYS_TRUE(bl12.WriteBytes("12345678", 8));
 250
 251   // |iter| is at position 0 (1st segment).
 252   iter = bl12.Iter();
 253   iter1 = bl12.Iter();
 254   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
 255   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 256   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
 257   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 258   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 8);
 259   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 260   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 12);
 261   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 3));
 262   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 15);
 263   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
 264   MOZ_RELEASE_ASSERT(iter1.Done());
 265
 266   // |iter| is at position 1 (1st segment).
 267   iter = bl12.Iter();
 268   iter1 = bl12.Iter();
 269   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl12, 1));
 270   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
 271   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
 272   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 273   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
 274   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 275   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 8);
 276   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 277   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 12);
 278   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 2));
 279   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 14);
 280   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
 281   MOZ_RELEASE_ASSERT(iter1.Done());
 282
 283   // |iter| is at position 8 (2nd segment).
 284   iter = bl12.Iter();
 285   iter1 = bl12.Iter();
 286   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl12, 8));
 287   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 8));
 288   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
 289   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 290   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
 291   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 3));
 292   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 7);
 293   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
 294   MOZ_RELEASE_ASSERT(iter1.Done());
 295
 296   // |iter| is at position 9 (2nd segment).
 297   iter = bl12.Iter();
 298   iter1 = bl12.Iter();
 299   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl12, 9));
 300   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 9));
 301   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
 302   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
 303   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
 304   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 2));
 305   MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 6);
 306   MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
 307   MOZ_RELEASE_ASSERT(iter1.Done());
 308
 309   BufferList bl13(0, 0, 8);
 310   MOZ_ALWAYS_TRUE(bl13.WriteBytes("abcdefgh", 8));
 311   MOZ_ALWAYS_TRUE(bl13.WriteBytes("12345678", 8));
 312   MOZ_ALWAYS_TRUE(bl13.WriteBytes("ABCDEFGH", 8));
 313   MOZ_RELEASE_ASSERT(bl13.Size() == 24);
 314
 315   // At segment border
 316   iter = bl13.Iter();
 317   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 8));
 318   MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 16);
 319   MOZ_RELEASE_ASSERT(iter.Done());
 320   MOZ_RELEASE_ASSERT(bl13.Size() == 8);
 321
 322   // Restore state
 323   MOZ_ALWAYS_TRUE(bl13.WriteBytes("12345678", 8));
 324   MOZ_ALWAYS_TRUE(bl13.WriteBytes("ABCDEFGH", 8));
 325   MOZ_RELEASE_ASSERT(bl13.Size() == 24);
 326
 327   // Before segment border
 328   iter = bl13.Iter();
 329   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 7));
 330   MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 17);
 331   MOZ_RELEASE_ASSERT(iter.Done());
 332   MOZ_RELEASE_ASSERT(bl13.Size() == 7);
 333
 334   // Restore state
 335   MOZ_ALWAYS_TRUE(bl13.WriteBytes("h", 1));
 336   MOZ_ALWAYS_TRUE(bl13.WriteBytes("12345678", 8));
 337   MOZ_ALWAYS_TRUE(bl13.WriteBytes("ABCDEFGH", 8));
 338   MOZ_RELEASE_ASSERT(bl13.Size() == 24);
 339
 340   // In last segment
 341   iter = bl13.Iter();
 342   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 20));
 343   MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 4);
 344   MOZ_RELEASE_ASSERT(iter.Done());
 345   MOZ_RELEASE_ASSERT(bl13.Size() == 20);
 346
 347   // No-op truncate
 348   MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 0);
 349   MOZ_RELEASE_ASSERT(iter.Done());
 350   MOZ_RELEASE_ASSERT(bl13.Size() == 20);
 351
 352   // No-op truncate with fresh iterator
 353   iter = bl13.Iter();
 354   MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 20));
 355   MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 0);
 356   MOZ_RELEASE_ASSERT(iter.Done());
 357   MOZ_RELEASE_ASSERT(bl13.Size() == 20);
 358
 359   // Truncate at start of buffer
 360   iter = bl13.Iter();
 361   MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 20);
 362   MOZ_RELEASE_ASSERT(iter.Done());
 363   MOZ_RELEASE_ASSERT(bl13.Size() == 0);
 364
 365   // No-op truncate at start of buffer
 366   iter = bl13.Iter();
 367   MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 0);
 368   MOZ_RELEASE_ASSERT(iter.Done());
 369   MOZ_RELEASE_ASSERT(bl13.Size() == 0);
 370
 371   return 0;
 372 }