folly/io/IOBuf.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef __STDC_LIMIT_MACROS
  18 #define __STDC_LIMIT_MACROS
  19 #endif
  20
  21 #include <folly/io/IOBuf.h>
  22
  23 #include <folly/Conv.h>
  24 #include <folly/Likely.h>
  25 #include <folly/Malloc.h>
  26 #include <folly/Memory.h>
  27 #include <folly/ScopeGuard.h>
  28 #include <folly/SpookyHashV2.h>
  29 #include <folly/io/Cursor.h>
  30
  31 #include <stdexcept>
  32 #include <assert.h>
  33 #include <stdint.h>
  34 #include <stdlib.h>
  35
  36 using std::unique_ptr;
  37
  38 namespace {
  39
  40 enum : uint16_t {
  41   kHeapMagic = 0xa5a5,
  42   // This memory segment contains an IOBuf that is still in use
  43   kIOBufInUse = 0x01,
  44   // This memory segment contains buffer data that is still in use
  45   kDataInUse = 0x02,
  46 };
  47
  48 enum : uint64_t {
  49   // When create() is called for buffers less than kDefaultCombinedBufSize,
  50   // we allocate a single combined memory segment for the IOBuf and the data
  51   // together.  See the comments for createCombined()/createSeparate() for more
  52   // details.
  53   //
  54   // (The size of 1k is largely just a guess here.  We could could probably do
  55   // benchmarks of real applications to see if adjusting this number makes a
  56   // difference.  Callers that know their exact use case can also explicitly
  57   // call createCombined() or createSeparate().)
  58   kDefaultCombinedBufSize = 1024
  59 };
  60
  61 // Helper function for IOBuf::takeOwnership()
  62 void takeOwnershipError(bool freeOnError, void* buf,
  63                         folly::IOBuf::FreeFunction freeFn,
  64                         void* userData) {
  65   if (!freeOnError) {
  66     return;
  67   }
  68   if (!freeFn) {
  69     free(buf);
  70     return;
  71   }
  72   try {
  73     freeFn(buf, userData);
  74   } catch (...) {
  75     // The user's free function is not allowed to throw.
  76     // (We are already in the middle of throwing an exception, so
  77     // we cannot let this exception go unhandled.)
  78     abort();
  79   }
  80 }
  81
  82 } // unnamed namespace
  83
  84 namespace folly {
  85
  86 struct IOBuf::HeapPrefix {
  87   HeapPrefix(uint16_t flg)
  88     : magic(kHeapMagic),
  89       flags(flg) {}
  90   ~HeapPrefix() {
  91     // Reset magic to 0 on destruction.  This is solely for debugging purposes
  92     // to help catch bugs where someone tries to use HeapStorage after it has
  93     // been deleted.
  94     magic = 0;
  95   }
  96
  97   uint16_t magic;
  98   std::atomic<uint16_t> flags;
  99 };
 100
 101 struct IOBuf::HeapStorage {
 102   HeapPrefix prefix;
 103   // The IOBuf is last in the HeapStorage object.
 104   // This way operator new will work even if allocating a subclass of IOBuf
 105   // that requires more space.
 106   folly::IOBuf buf;
 107 };
 108
 109 struct IOBuf::HeapFullStorage {
 110   // Make sure jemalloc allocates from the 64-byte class.  Putting this here
 111   // because HeapStorage is private so it can't be at namespace level.
 112   static_assert(sizeof(HeapStorage) <= 64,
 113                 "IOBuf may not grow over 56 bytes!");
 114
 115   HeapStorage hs;
 116   SharedInfo shared;
 117   std::max_align_t align;
 118 };
 119
 120 IOBuf::SharedInfo::SharedInfo()
 121   : freeFn(nullptr),
 122     userData(nullptr) {
 123   // Use relaxed memory ordering here.  Since we are creating a new SharedInfo,
 124   // no other threads should be referring to it yet.
 125   refcount.store(1, std::memory_order_relaxed);
 126 }
 127
 128 IOBuf::SharedInfo::SharedInfo(FreeFunction fn, void* arg)
 129   : freeFn(fn),
 130     userData(arg) {
 131   // Use relaxed memory ordering here.  Since we are creating a new SharedInfo,
 132   // no other threads should be referring to it yet.
 133   refcount.store(1, std::memory_order_relaxed);
 134 }
 135
 136 void* IOBuf::operator new(size_t size) {
 137   size_t fullSize = offsetof(HeapStorage, buf) + size;
 138   auto* storage = static_cast<HeapStorage*>(malloc(fullSize));
 139   // operator new is not allowed to return NULL
 140   if (UNLIKELY(storage == nullptr)) {
 141     throw std::bad_alloc();
 142   }
 143
 144   new (&storage->prefix) HeapPrefix(kIOBufInUse);
 145   return &(storage->buf);
 146 }
 147
 148 void* IOBuf::operator new(size_t /* size */, void* ptr) { return ptr; }
 149
 150 void IOBuf::operator delete(void* ptr) {
 151   auto* storageAddr = static_cast<uint8_t*>(ptr) - offsetof(HeapStorage, buf);
 152   auto* storage = reinterpret_cast<HeapStorage*>(storageAddr);
 153   releaseStorage(storage, kIOBufInUse);
 154 }
 155
 156 void IOBuf::releaseStorage(HeapStorage* storage, uint16_t freeFlags) {
 157   CHECK_EQ(storage->prefix.magic, static_cast<uint16_t>(kHeapMagic));
 158
 159   // Use relaxed memory order here.  If we are unlucky and happen to get
 160   // out-of-date data the compare_exchange_weak() call below will catch
 161   // it and load new data with memory_order_acq_rel.
 162   auto flags = storage->prefix.flags.load(std::memory_order_acquire);
 163   DCHECK_EQ((flags & freeFlags), freeFlags);
 164
 165   while (true) {
 166     uint16_t newFlags = uint16_t(flags & ~freeFlags);
 167     if (newFlags == 0) {
 168       // The storage space is now unused.  Free it.
 169       storage->prefix.HeapPrefix::~HeapPrefix();
 170       free(storage);
 171       return;
 172     }
 173
 174     // This storage segment still contains portions that are in use.
 175     // Just clear the flags specified in freeFlags for now.
 176     auto ret = storage->prefix.flags.compare_exchange_weak(
 177         flags, newFlags, std::memory_order_acq_rel);
 178     if (ret) {
 179       // We successfully updated the flags.
 180       return;
 181     }
 182
 183     // We failed to update the flags.  Some other thread probably updated them
 184     // and cleared some of the other bits.  Continue around the loop to see if
 185     // we are the last user now, or if we need to try updating the flags again.
 186   }
 187 }
 188
 189 void IOBuf::freeInternalBuf(void* /* buf */, void* userData) {
 190   auto* storage = static_cast<HeapStorage*>(userData);
 191   releaseStorage(storage, kDataInUse);
 192 }
 193
 194 IOBuf::IOBuf(CreateOp, uint64_t capacity)
 195   : next_(this),
 196     prev_(this),
 197     data_(nullptr),
 198     length_(0),
 199     flagsAndSharedInfo_(0) {
 200   SharedInfo* info;
 201   allocExtBuffer(capacity, &buf_, &info, &capacity_);
 202   setSharedInfo(info);
 203   data_ = buf_;
 204 }
 205
 206 IOBuf::IOBuf(CopyBufferOp /* op */,
 207              const void* buf,
 208              uint64_t size,
 209              uint64_t headroom,
 210              uint64_t minTailroom)
 211     : IOBuf(CREATE, headroom + size + minTailroom) {
 212   advance(headroom);
 213   if (size > 0) {
 214     assert(buf != nullptr);
 215     memcpy(writableData(), buf, size);
 216     append(size);
 217   }
 218 }
 219
 220 IOBuf::IOBuf(CopyBufferOp op, ByteRange br,
 221              uint64_t headroom, uint64_t minTailroom)
 222   : IOBuf(op, br.data(), br.size(), headroom, minTailroom) {
 223 }
 224
 225 unique_ptr<IOBuf> IOBuf::create(uint64_t capacity) {
 226   // For smaller-sized buffers, allocate the IOBuf, SharedInfo, and the buffer
 227   // all with a single allocation.
 228   //
 229   // We don't do this for larger buffers since it can be wasteful if the user
 230   // needs to reallocate the buffer but keeps using the same IOBuf object.
 231   // In this case we can't free the data space until the IOBuf is also
 232   // destroyed.  Callers can explicitly call createCombined() or
 233   // createSeparate() if they know their use case better, and know if they are
 234   // likely to reallocate the buffer later.
 235   if (capacity <= kDefaultCombinedBufSize) {
 236     return createCombined(capacity);
 237   }
 238   return createSeparate(capacity);
 239 }
 240
 241 unique_ptr<IOBuf> IOBuf::createCombined(uint64_t capacity) {
 242   // To save a memory allocation, allocate space for the IOBuf object, the
 243   // SharedInfo struct, and the data itself all with a single call to malloc().
 244   size_t requiredStorage = offsetof(HeapFullStorage, align) + capacity;
 245   size_t mallocSize = goodMallocSize(requiredStorage);
 246   auto* storage = static_cast<HeapFullStorage*>(malloc(mallocSize));
 247
 248   new (&storage->hs.prefix) HeapPrefix(kIOBufInUse | kDataInUse);
 249   new (&storage->shared) SharedInfo(freeInternalBuf, storage);
 250
 251   uint8_t* bufAddr = reinterpret_cast<uint8_t*>(&storage->align);
 252   uint8_t* storageEnd = reinterpret_cast<uint8_t*>(storage) + mallocSize;
 253   size_t actualCapacity = size_t(storageEnd - bufAddr);
 254   unique_ptr<IOBuf> ret(new (&storage->hs.buf) IOBuf(
 255         InternalConstructor(), packFlagsAndSharedInfo(0, &storage->shared),
 256         bufAddr, actualCapacity, bufAddr, 0));
 257   return ret;
 258 }
 259
 260 unique_ptr<IOBuf> IOBuf::createSeparate(uint64_t capacity) {
 261   return make_unique<IOBuf>(CREATE, capacity);
 262 }
 263
 264 unique_ptr<IOBuf> IOBuf::createChain(
 265     size_t totalCapacity, uint64_t maxBufCapacity) {
 266   unique_ptr<IOBuf> out = create(
 267       std::min(totalCapacity, size_t(maxBufCapacity)));
 268   size_t allocatedCapacity = out->capacity();
 269
 270   while (allocatedCapacity < totalCapacity) {
 271     unique_ptr<IOBuf> newBuf = create(
 272         std::min(totalCapacity - allocatedCapacity, size_t(maxBufCapacity)));
 273     allocatedCapacity += newBuf->capacity();
 274     out->prependChain(std::move(newBuf));
 275   }
 276
 277   return out;
 278 }
 279
 280 IOBuf::IOBuf(TakeOwnershipOp, void* buf, uint64_t capacity, uint64_t length,
 281              FreeFunction freeFn, void* userData,
 282              bool freeOnError)
 283   : next_(this),
 284     prev_(this),
 285     data_(static_cast<uint8_t*>(buf)),
 286     buf_(static_cast<uint8_t*>(buf)),
 287     length_(length),
 288     capacity_(capacity),
 289     flagsAndSharedInfo_(packFlagsAndSharedInfo(kFlagFreeSharedInfo, nullptr)) {
 290   try {
 291     setSharedInfo(new SharedInfo(freeFn, userData));
 292   } catch (...) {
 293     takeOwnershipError(freeOnError, buf, freeFn, userData);
 294     throw;
 295   }
 296 }
 297
 298 unique_ptr<IOBuf> IOBuf::takeOwnership(void* buf, uint64_t capacity,
 299                                        uint64_t length,
 300                                        FreeFunction freeFn,
 301                                        void* userData,
 302                                        bool freeOnError) {
 303   try {
 304     // TODO: We could allocate the IOBuf object and SharedInfo all in a single
 305     // memory allocation.  We could use the existing HeapStorage class, and
 306     // define a new kSharedInfoInUse flag.  We could change our code to call
 307     // releaseStorage(kFlagFreeSharedInfo) when this kFlagFreeSharedInfo,
 308     // rather than directly calling delete.
 309     //
 310     // Note that we always pass freeOnError as false to the constructor.
 311     // If the constructor throws we'll handle it below.  (We have to handle
 312     // allocation failures from make_unique too.)
 313     return make_unique<IOBuf>(TAKE_OWNERSHIP, buf, capacity, length,
 314                               freeFn, userData, false);
 315   } catch (...) {
 316     takeOwnershipError(freeOnError, buf, freeFn, userData);
 317     throw;
 318   }
 319 }
 320
 321 IOBuf::IOBuf(WrapBufferOp, const void* buf, uint64_t capacity)
 322   : IOBuf(InternalConstructor(), 0,
 323           // We cast away the const-ness of the buffer here.
 324           // This is okay since IOBuf users must use unshare() to create a copy
 325           // of this buffer before writing to the buffer.
 326           static_cast<uint8_t*>(const_cast<void*>(buf)), capacity,
 327           static_cast<uint8_t*>(const_cast<void*>(buf)), capacity) {
 328 }
 329
 330 IOBuf::IOBuf(WrapBufferOp op, ByteRange br)
 331   : IOBuf(op, br.data(), br.size()) {
 332 }
 333
 334 unique_ptr<IOBuf> IOBuf::wrapBuffer(const void* buf, uint64_t capacity) {
 335   return make_unique<IOBuf>(WRAP_BUFFER, buf, capacity);
 336 }
 337
 338 IOBuf IOBuf::wrapBufferAsValue(const void* buf, uint64_t capacity) {
 339   return IOBuf(WrapBufferOp::WRAP_BUFFER, buf, capacity);
 340 }
 341
 342 IOBuf::IOBuf() noexcept {
 343 }
 344
 345 IOBuf::IOBuf(IOBuf&& other) noexcept
 346     : data_(other.data_),
 347       buf_(other.buf_),
 348       length_(other.length_),
 349       capacity_(other.capacity_),
 350       flagsAndSharedInfo_(other.flagsAndSharedInfo_) {
 351   // Reset other so it is a clean state to be destroyed.
 352   other.data_ = nullptr;
 353   other.buf_ = nullptr;
 354   other.length_ = 0;
 355   other.capacity_ = 0;
 356   other.flagsAndSharedInfo_ = 0;
 357
 358   // If other was part of the chain, assume ownership of the rest of its chain.
 359   // (It's only valid to perform move assignment on the head of a chain.)
 360   if (other.next_ != &other) {
 361     next_ = other.next_;
 362     next_->prev_ = this;
 363     other.next_ = &other;
 364
 365     prev_ = other.prev_;
 366     prev_->next_ = this;
 367     other.prev_ = &other;
 368   }
 369
 370   // Sanity check to make sure that other is in a valid state to be destroyed.
 371   DCHECK_EQ(other.prev_, &other);
 372   DCHECK_EQ(other.next_, &other);
 373 }
 374
 375 IOBuf::IOBuf(const IOBuf& other) {
 376   *this = other.cloneAsValue();
 377 }
 378
 379 IOBuf::IOBuf(InternalConstructor,
 380              uintptr_t flagsAndSharedInfo,
 381              uint8_t* buf,
 382              uint64_t capacity,
 383              uint8_t* data,
 384              uint64_t length)
 385   : next_(this),
 386     prev_(this),
 387     data_(data),
 388     buf_(buf),
 389     length_(length),
 390     capacity_(capacity),
 391     flagsAndSharedInfo_(flagsAndSharedInfo) {
 392   assert(data >= buf);
 393   assert(data + length <= buf + capacity);
 394 }
 395
 396 IOBuf::~IOBuf() {
 397   // Destroying an IOBuf destroys the entire chain.
 398   // Users of IOBuf should only explicitly delete the head of any chain.
 399   // The other elements in the chain will be automatically destroyed.
 400   while (next_ != this) {
 401     // Since unlink() returns unique_ptr() and we don't store it,
 402     // it will automatically delete the unlinked element.
 403     (void)next_->unlink();
 404   }
 405
 406   decrementRefcount();
 407 }
 408
 409 IOBuf& IOBuf::operator=(IOBuf&& other) noexcept {
 410   if (this == &other) {
 411     return *this;
 412   }
 413
 414   // If we are part of a chain, delete the rest of the chain.
 415   while (next_ != this) {
 416     // Since unlink() returns unique_ptr() and we don't store it,
 417     // it will automatically delete the unlinked element.
 418     (void)next_->unlink();
 419   }
 420
 421   // Decrement our refcount on the current buffer
 422   decrementRefcount();
 423
 424   // Take ownership of the other buffer's data
 425   data_ = other.data_;
 426   buf_ = other.buf_;
 427   length_ = other.length_;
 428   capacity_ = other.capacity_;
 429   flagsAndSharedInfo_ = other.flagsAndSharedInfo_;
 430   // Reset other so it is a clean state to be destroyed.
 431   other.data_ = nullptr;
 432   other.buf_ = nullptr;
 433   other.length_ = 0;
 434   other.capacity_ = 0;
 435   other.flagsAndSharedInfo_ = 0;
 436
 437   // If other was part of the chain, assume ownership of the rest of its chain.
 438   // (It's only valid to perform move assignment on the head of a chain.)
 439   if (other.next_ != &other) {
 440     next_ = other.next_;
 441     next_->prev_ = this;
 442     other.next_ = &other;
 443
 444     prev_ = other.prev_;
 445     prev_->next_ = this;
 446     other.prev_ = &other;
 447   }
 448
 449   // Sanity check to make sure that other is in a valid state to be destroyed.
 450   DCHECK_EQ(other.prev_, &other);
 451   DCHECK_EQ(other.next_, &other);
 452
 453   return *this;
 454 }
 455
 456 IOBuf& IOBuf::operator=(const IOBuf& other) {
 457   if (this != &other) {
 458     *this = IOBuf(other);
 459   }
 460   return *this;
 461 }
 462
 463 bool IOBuf::empty() const {
 464   const IOBuf* current = this;
 465   do {
 466     if (current->length() != 0) {
 467       return false;
 468     }
 469     current = current->next_;
 470   } while (current != this);
 471   return true;
 472 }
 473
 474 size_t IOBuf::countChainElements() const {
 475   size_t numElements = 1;
 476   for (IOBuf* current = next_; current != this; current = current->next_) {
 477     ++numElements;
 478   }
 479   return numElements;
 480 }
 481
 482 uint64_t IOBuf::computeChainDataLength() const {
 483   uint64_t fullLength = length_;
 484   for (IOBuf* current = next_; current != this; current = current->next_) {
 485     fullLength += current->length_;
 486   }
 487   return fullLength;
 488 }
 489
 490 void IOBuf::prependChain(unique_ptr<IOBuf>&& iobuf) {
 491   // Take ownership of the specified IOBuf
 492   IOBuf* other = iobuf.release();
 493
 494   // Remember the pointer to the tail of the other chain
 495   IOBuf* otherTail = other->prev_;
 496
 497   // Hook up prev_->next_ to point at the start of the other chain,
 498   // and other->prev_ to point at prev_
 499   prev_->next_ = other;
 500   other->prev_ = prev_;
 501
 502   // Hook up otherTail->next_ to point at us,
 503   // and prev_ to point back at otherTail,
 504   otherTail->next_ = this;
 505   prev_ = otherTail;
 506 }
 507
 508 unique_ptr<IOBuf> IOBuf::clone() const {
 509   return make_unique<IOBuf>(cloneAsValue());
 510 }
 511
 512 unique_ptr<IOBuf> IOBuf::cloneOne() const {
 513   return make_unique<IOBuf>(cloneOneAsValue());
 514 }
 515
 516 unique_ptr<IOBuf> IOBuf::cloneCoalesced() const {
 517   return make_unique<IOBuf>(cloneCoalescedAsValue());
 518 }
 519
 520 IOBuf IOBuf::cloneAsValue() const {
 521   auto tmp = cloneOneAsValue();
 522
 523   for (IOBuf* current = next_; current != this; current = current->next_) {
 524     tmp.prependChain(current->cloneOne());
 525   }
 526
 527   return tmp;
 528 }
 529
 530 IOBuf IOBuf::cloneOneAsValue() const {
 531   if (SharedInfo* info = sharedInfo()) {
 532     setFlags(kFlagMaybeShared);
 533     info->refcount.fetch_add(1, std::memory_order_acq_rel);
 534   }
 535   return IOBuf(
 536       InternalConstructor(),
 537       flagsAndSharedInfo_,
 538       buf_,
 539       capacity_,
 540       data_,
 541       length_);
 542 }
 543
 544 IOBuf IOBuf::cloneCoalescedAsValue() const {
 545   if (!isChained()) {
 546     return cloneOneAsValue();
 547   }
 548   // Coalesce into newBuf
 549   const uint64_t newLength = computeChainDataLength();
 550   const uint64_t newHeadroom = headroom();
 551   const uint64_t newTailroom = prev()->tailroom();
 552   const uint64_t newCapacity = newLength + newHeadroom + newTailroom;
 553   IOBuf newBuf{CREATE, newCapacity};
 554   newBuf.advance(newHeadroom);
 555
 556   auto current = this;
 557   do {
 558     if (current->length() > 0) {
 559       DCHECK_NOTNULL(current->data());
 560       DCHECK_LE(current->length(), newBuf.tailroom());
 561       memcpy(newBuf.writableTail(), current->data(), current->length());
 562       newBuf.append(current->length());
 563     }
 564     current = current->next();
 565   } while (current != this);
 566
 567   DCHECK_EQ(newLength, newBuf.length());
 568   DCHECK_EQ(newHeadroom, newBuf.headroom());
 569   DCHECK_LE(newTailroom, newBuf.tailroom());
 570
 571   return newBuf;
 572 }
 573
 574 void IOBuf::unshareOneSlow() {
 575   // Allocate a new buffer for the data
 576   uint8_t* buf;
 577   SharedInfo* sharedInfo;
 578   uint64_t actualCapacity;
 579   allocExtBuffer(capacity_, &buf, &sharedInfo, &actualCapacity);
 580
 581   // Copy the data
 582   // Maintain the same amount of headroom.  Since we maintained the same
 583   // minimum capacity we also maintain at least the same amount of tailroom.
 584   uint64_t headlen = headroom();
 585   if (length_ > 0) {
 586     assert(data_ != nullptr);
 587     memcpy(buf + headlen, data_, length_);
 588   }
 589
 590   // Release our reference on the old buffer
 591   decrementRefcount();
 592   // Make sure kFlagMaybeShared and kFlagFreeSharedInfo are all cleared.
 593   setFlagsAndSharedInfo(0, sharedInfo);
 594
 595   // Update the buffer pointers to point to the new buffer
 596   data_ = buf + headlen;
 597   buf_ = buf;
 598 }
 599
 600 void IOBuf::unshareChained() {
 601   // unshareChained() should only be called if we are part of a chain of
 602   // multiple IOBufs.  The caller should have already verified this.
 603   assert(isChained());
 604
 605   IOBuf* current = this;
 606   while (true) {
 607     if (current->isSharedOne()) {
 608       // we have to unshare
 609       break;
 610     }
 611
 612     current = current->next_;
 613     if (current == this) {
 614       // None of the IOBufs in the chain are shared,
 615       // so return without doing anything
 616       return;
 617     }
 618   }
 619
 620   // We have to unshare.  Let coalesceSlow() do the work.
 621   coalesceSlow();
 622 }
 623
 624 void IOBuf::markExternallyShared() {
 625   IOBuf* current = this;
 626   do {
 627     current->markExternallySharedOne();
 628     current = current->next_;
 629   } while (current != this);
 630 }
 631
 632 void IOBuf::makeManagedChained() {
 633   assert(isChained());
 634
 635   IOBuf* current = this;
 636   while (true) {
 637     current->makeManagedOne();
 638     current = current->next_;
 639     if (current == this) {
 640       break;
 641     }
 642   }
 643 }
 644
 645 void IOBuf::coalesceSlow() {
 646   // coalesceSlow() should only be called if we are part of a chain of multiple
 647   // IOBufs.  The caller should have already verified this.
 648   DCHECK(isChained());
 649
 650   // Compute the length of the entire chain
 651   uint64_t newLength = 0;
 652   IOBuf* end = this;
 653   do {
 654     newLength += end->length_;
 655     end = end->next_;
 656   } while (end != this);
 657
 658   coalesceAndReallocate(newLength, end);
 659   // We should be only element left in the chain now
 660   DCHECK(!isChained());
 661 }
 662
 663 void IOBuf::coalesceSlow(size_t maxLength) {
 664   // coalesceSlow() should only be called if we are part of a chain of multiple
 665   // IOBufs.  The caller should have already verified this.
 666   DCHECK(isChained());
 667   DCHECK_LT(length_, maxLength);
 668
 669   // Compute the length of the entire chain
 670   uint64_t newLength = 0;
 671   IOBuf* end = this;
 672   while (true) {
 673     newLength += end->length_;
 674     end = end->next_;
 675     if (newLength >= maxLength) {
 676       break;
 677     }
 678     if (end == this) {
 679       throw std::overflow_error("attempted to coalesce more data than "
 680                                 "available");
 681     }
 682   }
 683
 684   coalesceAndReallocate(newLength, end);
 685   // We should have the requested length now
 686   DCHECK_GE(length_, maxLength);
 687 }
 688
 689 void IOBuf::coalesceAndReallocate(size_t newHeadroom,
 690                                   size_t newLength,
 691                                   IOBuf* end,
 692                                   size_t newTailroom) {
 693   uint64_t newCapacity = newLength + newHeadroom + newTailroom;
 694
 695   // Allocate space for the coalesced buffer.
 696   // We always convert to an external buffer, even if we happened to be an
 697   // internal buffer before.
 698   uint8_t* newBuf;
 699   SharedInfo* newInfo;
 700   uint64_t actualCapacity;
 701   allocExtBuffer(newCapacity, &newBuf, &newInfo, &actualCapacity);
 702
 703   // Copy the data into the new buffer
 704   uint8_t* newData = newBuf + newHeadroom;
 705   uint8_t* p = newData;
 706   IOBuf* current = this;
 707   size_t remaining = newLength;
 708   do {
 709     if (current->length_ > 0) {
 710       assert(current->length_ <= remaining);
 711       assert(current->data_ != nullptr);
 712       remaining -= current->length_;
 713       memcpy(p, current->data_, current->length_);
 714       p += current->length_;
 715     }
 716     current = current->next_;
 717   } while (current != end);
 718   assert(remaining == 0);
 719
 720   // Point at the new buffer
 721   decrementRefcount();
 722
 723   // Make sure kFlagMaybeShared and kFlagFreeSharedInfo are all cleared.
 724   setFlagsAndSharedInfo(0, newInfo);
 725
 726   capacity_ = actualCapacity;
 727   buf_ = newBuf;
 728   data_ = newData;
 729   length_ = newLength;
 730
 731   // Separate from the rest of our chain.
 732   // Since we don't store the unique_ptr returned by separateChain(),
 733   // this will immediately delete the returned subchain.
 734   if (isChained()) {
 735     (void)separateChain(next_, current->prev_);
 736   }
 737 }
 738
 739 void IOBuf::decrementRefcount() {
 740   // Externally owned buffers don't have a SharedInfo object and aren't managed
 741   // by the reference count
 742   SharedInfo* info = sharedInfo();
 743   if (!info) {
 744     return;
 745   }
 746
 747   // Decrement the refcount
 748   uint32_t newcnt = info->refcount.fetch_sub(
 749       1, std::memory_order_acq_rel);
 750   // Note that fetch_sub() returns the value before we decremented.
 751   // If it is 1, we were the only remaining user; if it is greater there are
 752   // still other users.
 753   if (newcnt > 1) {
 754     return;
 755   }
 756
 757   // We were the last user.  Free the buffer
 758   freeExtBuffer();
 759
 760   // Free the SharedInfo if it was allocated separately.
 761   //
 762   // This is only used by takeOwnership().
 763   //
 764   // To avoid this special case handling in decrementRefcount(), we could have
 765   // takeOwnership() set a custom freeFn() that calls the user's free function
 766   // then frees the SharedInfo object.  (This would require that
 767   // takeOwnership() store the user's free function with its allocated
 768   // SharedInfo object.)  However, handling this specially with a flag seems
 769   // like it shouldn't be problematic.
 770   if (flags() & kFlagFreeSharedInfo) {
 771     delete sharedInfo();
 772   }
 773 }
 774
 775 void IOBuf::reserveSlow(uint64_t minHeadroom, uint64_t minTailroom) {
 776   size_t newCapacity = (size_t)length_ + minHeadroom + minTailroom;
 777   DCHECK_LT(newCapacity, UINT32_MAX);
 778
 779   // reserveSlow() is dangerous if anyone else is sharing the buffer, as we may
 780   // reallocate and free the original buffer.  It should only ever be called if
 781   // we are the only user of the buffer.
 782   DCHECK(!isSharedOne());
 783
 784   // We'll need to reallocate the buffer.
 785   // There are a few options.
 786   // - If we have enough total room, move the data around in the buffer
 787   //   and adjust the data_ pointer.
 788   // - If we're using an internal buffer, we'll switch to an external
 789   //   buffer with enough headroom and tailroom.
 790   // - If we have enough headroom (headroom() >= minHeadroom) but not too much
 791   //   (so we don't waste memory), we can try one of two things, depending on
 792   //   whether we use jemalloc or not:
 793   //   - If using jemalloc, we can try to expand in place, avoiding a memcpy()
 794   //   - If not using jemalloc and we don't have too much to copy,
 795   //     we'll use realloc() (note that realloc might have to copy
 796   //     headroom + data + tailroom, see smartRealloc in folly/Malloc.h)
 797   // - Otherwise, bite the bullet and reallocate.
 798   if (headroom() + tailroom() >= minHeadroom + minTailroom) {
 799     uint8_t* newData = writableBuffer() + minHeadroom;
 800     memmove(newData, data_, length_);
 801     data_ = newData;
 802     return;
 803   }
 804
 805   size_t newAllocatedCapacity = 0;
 806   uint8_t* newBuffer = nullptr;
 807   uint64_t newHeadroom = 0;
 808   uint64_t oldHeadroom = headroom();
 809
 810   // If we have a buffer allocated with malloc and we just need more tailroom,
 811   // try to use realloc()/xallocx() to grow the buffer in place.
 812   SharedInfo* info = sharedInfo();
 813   if (info && (info->freeFn == nullptr) && length_ != 0 &&
 814       oldHeadroom >= minHeadroom) {
 815     size_t headSlack = oldHeadroom - minHeadroom;
 816     newAllocatedCapacity = goodExtBufferSize(newCapacity + headSlack);
 817     if (usingJEMalloc()) {
 818       // We assume that tailroom is more useful and more important than
 819       // headroom (not least because realloc / xallocx allow us to grow the
 820       // buffer at the tail, but not at the head)  So, if we have more headroom
 821       // than we need, we consider that "wasted".  We arbitrarily define "too
 822       // much" headroom to be 25% of the capacity.
 823       if (headSlack * 4 <= newCapacity) {
 824         size_t allocatedCapacity = capacity() + sizeof(SharedInfo);
 825         void* p = buf_;
 826         if (allocatedCapacity >= jemallocMinInPlaceExpandable) {
 827           if (xallocx(p, newAllocatedCapacity, 0, 0) == newAllocatedCapacity) {
 828             newBuffer = static_cast<uint8_t*>(p);
 829             newHeadroom = oldHeadroom;
 830           }
 831           // if xallocx failed, do nothing, fall back to malloc/memcpy/free
 832         }
 833       }
 834     } else {  // Not using jemalloc
 835       size_t copySlack = capacity() - length_;
 836       if (copySlack * 2 <= length_) {
 837         void* p = realloc(buf_, newAllocatedCapacity);
 838         if (UNLIKELY(p == nullptr)) {
 839           throw std::bad_alloc();
 840         }
 841         newBuffer = static_cast<uint8_t*>(p);
 842         newHeadroom = oldHeadroom;
 843       }
 844     }
 845   }
 846
 847   // None of the previous reallocation strategies worked (or we're using
 848   // an internal buffer).  malloc/copy/free.
 849   if (newBuffer == nullptr) {
 850     newAllocatedCapacity = goodExtBufferSize(newCapacity);
 851     void* p = malloc(newAllocatedCapacity);
 852     if (UNLIKELY(p == nullptr)) {
 853       throw std::bad_alloc();
 854     }
 855     newBuffer = static_cast<uint8_t*>(p);
 856     if (length_ > 0) {
 857       assert(data_ != nullptr);
 858       memcpy(newBuffer + minHeadroom, data_, length_);
 859     }
 860     if (sharedInfo()) {
 861       freeExtBuffer();
 862     }
 863     newHeadroom = minHeadroom;
 864   }
 865
 866   uint64_t cap;
 867   initExtBuffer(newBuffer, newAllocatedCapacity, &info, &cap);
 868
 869   if (flags() & kFlagFreeSharedInfo) {
 870     delete sharedInfo();
 871   }
 872
 873   setFlagsAndSharedInfo(0, info);
 874   capacity_ = cap;
 875   buf_ = newBuffer;
 876   data_ = newBuffer + newHeadroom;
 877   // length_ is unchanged
 878 }
 879
 880 void IOBuf::freeExtBuffer() {
 881   SharedInfo* info = sharedInfo();
 882   DCHECK(info);
 883
 884   if (info->freeFn) {
 885     try {
 886       info->freeFn(buf_, info->userData);
 887     } catch (...) {
 888       // The user's free function should never throw.  Otherwise we might
 889       // throw from the IOBuf destructor.  Other code paths like coalesce()
 890       // also assume that decrementRefcount() cannot throw.
 891       abort();
 892     }
 893   } else {
 894     free(buf_);
 895   }
 896 }
 897
 898 void IOBuf::allocExtBuffer(uint64_t minCapacity,
 899                            uint8_t** bufReturn,
 900                            SharedInfo** infoReturn,
 901                            uint64_t* capacityReturn) {
 902   size_t mallocSize = goodExtBufferSize(minCapacity);
 903   uint8_t* buf = static_cast<uint8_t*>(malloc(mallocSize));
 904   if (UNLIKELY(buf == nullptr)) {
 905     throw std::bad_alloc();
 906   }
 907   initExtBuffer(buf, mallocSize, infoReturn, capacityReturn);
 908   *bufReturn = buf;
 909 }
 910
 911 size_t IOBuf::goodExtBufferSize(uint64_t minCapacity) {
 912   // Determine how much space we should allocate.  We'll store the SharedInfo
 913   // for the external buffer just after the buffer itself.  (We store it just
 914   // after the buffer rather than just before so that the code can still just
 915   // use free(buf_) to free the buffer.)
 916   size_t minSize = static_cast<size_t>(minCapacity) + sizeof(SharedInfo);
 917   // Add room for padding so that the SharedInfo will be aligned on an 8-byte
 918   // boundary.
 919   minSize = (minSize + 7) & ~7;
 920
 921   // Use goodMallocSize() to bump up the capacity to a decent size to request
 922   // from malloc, so we can use all of the space that malloc will probably give
 923   // us anyway.
 924   return goodMallocSize(minSize);
 925 }
 926
 927 void IOBuf::initExtBuffer(uint8_t* buf, size_t mallocSize,
 928                           SharedInfo** infoReturn,
 929                           uint64_t* capacityReturn) {
 930   // Find the SharedInfo storage at the end of the buffer
 931   // and construct the SharedInfo.
 932   uint8_t* infoStart = (buf + mallocSize) - sizeof(SharedInfo);
 933   SharedInfo* sharedInfo = new(infoStart) SharedInfo;
 934
 935   *capacityReturn = uint64_t(infoStart - buf);
 936   *infoReturn = sharedInfo;
 937 }
 938
 939 fbstring IOBuf::moveToFbString() {
 940   // malloc-allocated buffers are just fine, everything else needs
 941   // to be turned into one.
 942   if (!sharedInfo() ||         // user owned, not ours to give up
 943       sharedInfo()->freeFn ||  // not malloc()-ed
 944       headroom() != 0 ||       // malloc()-ed block doesn't start at beginning
 945       tailroom() == 0 ||       // no room for NUL terminator
 946       isShared() ||            // shared
 947       isChained()) {           // chained
 948     // We might as well get rid of all head and tailroom if we're going
 949     // to reallocate; we need 1 byte for NUL terminator.
 950     coalesceAndReallocate(0, computeChainDataLength(), this, 1);
 951   }
 952
 953   // Ensure NUL terminated
 954   *writableTail() = 0;
 955   fbstring str(reinterpret_cast<char*>(writableData()),
 956                length(),  capacity(),
 957                AcquireMallocatedString());
 958
 959   if (flags() & kFlagFreeSharedInfo) {
 960     delete sharedInfo();
 961   }
 962
 963   // Reset to a state where we can be deleted cleanly
 964   flagsAndSharedInfo_ = 0;
 965   buf_ = nullptr;
 966   clear();
 967   return str;
 968 }
 969
 970 IOBuf::Iterator IOBuf::cbegin() const {
 971   return Iterator(this, this);
 972 }
 973
 974 IOBuf::Iterator IOBuf::cend() const {
 975   return Iterator(nullptr, nullptr);
 976 }
 977
 978 folly::fbvector<struct iovec> IOBuf::getIov() const {
 979   folly::fbvector<struct iovec> iov;
 980   iov.reserve(countChainElements());
 981   appendToIov(&iov);
 982   return iov;
 983 }
 984
 985 void IOBuf::appendToIov(folly::fbvector<struct iovec>* iov) const {
 986   IOBuf const* p = this;
 987   do {
 988     // some code can get confused by empty iovs, so skip them
 989     if (p->length() > 0) {
 990       iov->push_back({(void*)p->data(), folly::to<size_t>(p->length())});
 991     }
 992     p = p->next();
 993   } while (p != this);
 994 }
 995
 996 size_t IOBuf::fillIov(struct iovec* iov, size_t len) const {
 997   IOBuf const* p = this;
 998   size_t i = 0;
 999   while (i < len) {
1000     // some code can get confused by empty iovs, so skip them
1001     if (p->length() > 0) {
1002       iov[i].iov_base = const_cast<uint8_t*>(p->data());
1003       iov[i].iov_len = p->length();
1004       i++;
1005     }
1006     p = p->next();
1007     if (p == this) {
1008       return i;
1009     }
1010   }
1011   return 0;
1012 }
1013
1014 size_t IOBufHash::operator()(const IOBuf& buf) const {
1015   folly::hash::SpookyHashV2 hasher;
1016   hasher.Init(0, 0);
1017   io::Cursor cursor(&buf);
1018   for (;;) {
1019     auto b = cursor.peekBytes();
1020     if (b.empty()) {
1021       break;
1022     }
1023     hasher.Update(b.data(), b.size());
1024     cursor.skip(b.size());
1025   }
1026   uint64_t h1;
1027   uint64_t h2;
1028   hasher.Final(&h1, &h2);
1029   return h1;
1030 }
1031
1032 bool IOBufEqual::operator()(const IOBuf& a, const IOBuf& b) const {
1033   io::Cursor ca(&a);
1034   io::Cursor cb(&b);
1035   for (;;) {
1036     auto ba = ca.peekBytes();
1037     auto bb = cb.peekBytes();
1038     if (ba.empty() && bb.empty()) {
1039       return true;
1040     } else if (ba.empty() || bb.empty()) {
1041       return false;
1042     }
1043     size_t n = std::min(ba.size(), bb.size());
1044     DCHECK_GT(n, 0u);
1045     if (memcmp(ba.data(), bb.data(), n)) {
1046       return false;
1047     }
1048     ca.skip(n);
1049     cb.skip(n);
1050   }
1051 }
1052
1053 } // folly