folly/io/IOBuf.cpp

   1 /*
   2  * Copyright 2015 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) {
 149   return ptr;
 150 }
 151
 152 void IOBuf::operator delete(void* ptr) {
 153   auto* storageAddr = static_cast<uint8_t*>(ptr) - offsetof(HeapStorage, buf);
 154   auto* storage = reinterpret_cast<HeapStorage*>(storageAddr);
 155   releaseStorage(storage, kIOBufInUse);
 156 }
 157
 158 void IOBuf::releaseStorage(HeapStorage* storage, uint16_t freeFlags) {
 159   CHECK_EQ(storage->prefix.magic, static_cast<uint16_t>(kHeapMagic));
 160
 161   // Use relaxed memory order here.  If we are unlucky and happen to get
 162   // out-of-date data the compare_exchange_weak() call below will catch
 163   // it and load new data with memory_order_acq_rel.
 164   auto flags = storage->prefix.flags.load(std::memory_order_acquire);
 165   DCHECK_EQ((flags & freeFlags), freeFlags);
 166
 167   while (true) {
 168     uint16_t newFlags = (flags & ~freeFlags);
 169     if (newFlags == 0) {
 170       // The storage space is now unused.  Free it.
 171       storage->prefix.HeapPrefix::~HeapPrefix();
 172       free(storage);
 173       return;
 174     }
 175
 176     // This storage segment still contains portions that are in use.
 177     // Just clear the flags specified in freeFlags for now.
 178     auto ret = storage->prefix.flags.compare_exchange_weak(
 179         flags, newFlags, std::memory_order_acq_rel);
 180     if (ret) {
 181       // We successfully updated the flags.
 182       return;
 183     }
 184
 185     // We failed to update the flags.  Some other thread probably updated them
 186     // and cleared some of the other bits.  Continue around the loop to see if
 187     // we are the last user now, or if we need to try updating the flags again.
 188   }
 189 }
 190
 191 void IOBuf::freeInternalBuf(void* buf, void* userData) {
 192   auto* storage = static_cast<HeapStorage*>(userData);
 193   releaseStorage(storage, kDataInUse);
 194 }
 195
 196 IOBuf::IOBuf(CreateOp, uint64_t capacity)
 197   : next_(this),
 198     prev_(this),
 199     data_(nullptr),
 200     length_(0),
 201     flagsAndSharedInfo_(0) {
 202   SharedInfo* info;
 203   allocExtBuffer(capacity, &buf_, &info, &capacity_);
 204   setSharedInfo(info);
 205   data_ = buf_;
 206 }
 207
 208 IOBuf::IOBuf(CopyBufferOp op, const void* buf, uint64_t size,
 209              uint64_t headroom, uint64_t minTailroom)
 210   : IOBuf(CREATE, headroom + size + minTailroom) {
 211   advance(headroom);
 212   memcpy(writableData(), buf, size);
 213   append(size);
 214 }
 215
 216 IOBuf::IOBuf(CopyBufferOp op, ByteRange br,
 217              uint64_t headroom, uint64_t minTailroom)
 218   : IOBuf(op, br.data(), br.size(), headroom, minTailroom) {
 219 }
 220
 221 unique_ptr<IOBuf> IOBuf::create(uint64_t capacity) {
 222   // For smaller-sized buffers, allocate the IOBuf, SharedInfo, and the buffer
 223   // all with a single allocation.
 224   //
 225   // We don't do this for larger buffers since it can be wasteful if the user
 226   // needs to reallocate the buffer but keeps using the same IOBuf object.
 227   // In this case we can't free the data space until the IOBuf is also
 228   // destroyed.  Callers can explicitly call createCombined() or
 229   // createSeparate() if they know their use case better, and know if they are
 230   // likely to reallocate the buffer later.
 231   if (capacity <= kDefaultCombinedBufSize) {
 232     return createCombined(capacity);
 233   }
 234   return createSeparate(capacity);
 235 }
 236
 237 unique_ptr<IOBuf> IOBuf::createCombined(uint64_t capacity) {
 238   // To save a memory allocation, allocate space for the IOBuf object, the
 239   // SharedInfo struct, and the data itself all with a single call to malloc().
 240   size_t requiredStorage = offsetof(HeapFullStorage, align) + capacity;
 241   size_t mallocSize = goodMallocSize(requiredStorage);
 242   auto* storage = static_cast<HeapFullStorage*>(malloc(mallocSize));
 243
 244   new (&storage->hs.prefix) HeapPrefix(kIOBufInUse | kDataInUse);
 245   new (&storage->shared) SharedInfo(freeInternalBuf, storage);
 246
 247   uint8_t* bufAddr = reinterpret_cast<uint8_t*>(&storage->align);
 248   uint8_t* storageEnd = reinterpret_cast<uint8_t*>(storage) + mallocSize;
 249   size_t actualCapacity = storageEnd - bufAddr;
 250   unique_ptr<IOBuf> ret(new (&storage->hs.buf) IOBuf(
 251         InternalConstructor(), packFlagsAndSharedInfo(0, &storage->shared),
 252         bufAddr, actualCapacity, bufAddr, 0));
 253   return ret;
 254 }
 255
 256 unique_ptr<IOBuf> IOBuf::createSeparate(uint64_t capacity) {
 257   return make_unique<IOBuf>(CREATE, capacity);
 258 }
 259
 260 unique_ptr<IOBuf> IOBuf::createChain(
 261     size_t totalCapacity, uint64_t maxBufCapacity) {
 262   unique_ptr<IOBuf> out = create(
 263       std::min(totalCapacity, size_t(maxBufCapacity)));
 264   size_t allocatedCapacity = out->capacity();
 265
 266   while (allocatedCapacity < totalCapacity) {
 267     unique_ptr<IOBuf> newBuf = create(
 268         std::min(totalCapacity - allocatedCapacity, size_t(maxBufCapacity)));
 269     allocatedCapacity += newBuf->capacity();
 270     out->prependChain(std::move(newBuf));
 271   }
 272
 273   return out;
 274 }
 275
 276 IOBuf::IOBuf(TakeOwnershipOp, void* buf, uint64_t capacity, uint64_t length,
 277              FreeFunction freeFn, void* userData,
 278              bool freeOnError)
 279   : next_(this),
 280     prev_(this),
 281     data_(static_cast<uint8_t*>(buf)),
 282     buf_(static_cast<uint8_t*>(buf)),
 283     length_(length),
 284     capacity_(capacity),
 285     flagsAndSharedInfo_(packFlagsAndSharedInfo(kFlagFreeSharedInfo, nullptr)) {
 286   try {
 287     setSharedInfo(new SharedInfo(freeFn, userData));
 288   } catch (...) {
 289     takeOwnershipError(freeOnError, buf, freeFn, userData);
 290     throw;
 291   }
 292 }
 293
 294 unique_ptr<IOBuf> IOBuf::takeOwnership(void* buf, uint64_t capacity,
 295                                        uint64_t length,
 296                                        FreeFunction freeFn,
 297                                        void* userData,
 298                                        bool freeOnError) {
 299   try {
 300     // TODO: We could allocate the IOBuf object and SharedInfo all in a single
 301     // memory allocation.  We could use the existing HeapStorage class, and
 302     // define a new kSharedInfoInUse flag.  We could change our code to call
 303     // releaseStorage(kFlagFreeSharedInfo) when this kFlagFreeSharedInfo,
 304     // rather than directly calling delete.
 305     //
 306     // Note that we always pass freeOnError as false to the constructor.
 307     // If the constructor throws we'll handle it below.  (We have to handle
 308     // allocation failures from make_unique too.)
 309     return make_unique<IOBuf>(TAKE_OWNERSHIP, buf, capacity, length,
 310                               freeFn, userData, false);
 311   } catch (...) {
 312     takeOwnershipError(freeOnError, buf, freeFn, userData);
 313     throw;
 314   }
 315 }
 316
 317 IOBuf::IOBuf(WrapBufferOp, const void* buf, uint64_t capacity)
 318   : IOBuf(InternalConstructor(), 0,
 319           // We cast away the const-ness of the buffer here.
 320           // This is okay since IOBuf users must use unshare() to create a copy
 321           // of this buffer before writing to the buffer.
 322           static_cast<uint8_t*>(const_cast<void*>(buf)), capacity,
 323           static_cast<uint8_t*>(const_cast<void*>(buf)), capacity) {
 324 }
 325
 326 IOBuf::IOBuf(WrapBufferOp op, ByteRange br)
 327   : IOBuf(op, br.data(), br.size()) {
 328 }
 329
 330 unique_ptr<IOBuf> IOBuf::wrapBuffer(const void* buf, uint64_t capacity) {
 331   return make_unique<IOBuf>(WRAP_BUFFER, buf, capacity);
 332 }
 333
 334 IOBuf::IOBuf() noexcept {
 335 }
 336
 337 IOBuf::IOBuf(IOBuf&& other) noexcept {
 338   *this = std::move(other);
 339 }
 340
 341 IOBuf::IOBuf(const IOBuf& other) {
 342   other.cloneInto(*this);
 343 }
 344
 345 IOBuf::IOBuf(InternalConstructor,
 346              uintptr_t flagsAndSharedInfo,
 347              uint8_t* buf,
 348              uint64_t capacity,
 349              uint8_t* data,
 350              uint64_t length)
 351   : next_(this),
 352     prev_(this),
 353     data_(data),
 354     buf_(buf),
 355     length_(length),
 356     capacity_(capacity),
 357     flagsAndSharedInfo_(flagsAndSharedInfo) {
 358   assert(data >= buf);
 359   assert(data + length <= buf + capacity);
 360 }
 361
 362 IOBuf::~IOBuf() {
 363   // Destroying an IOBuf destroys the entire chain.
 364   // Users of IOBuf should only explicitly delete the head of any chain.
 365   // The other elements in the chain will be automatically destroyed.
 366   while (next_ != this) {
 367     // Since unlink() returns unique_ptr() and we don't store it,
 368     // it will automatically delete the unlinked element.
 369     (void)next_->unlink();
 370   }
 371
 372   decrementRefcount();
 373 }
 374
 375 IOBuf& IOBuf::operator=(IOBuf&& other) noexcept {
 376   if (this == &other) {
 377     return *this;
 378   }
 379
 380   // If we are part of a chain, delete the rest of the chain.
 381   while (next_ != this) {
 382     // Since unlink() returns unique_ptr() and we don't store it,
 383     // it will automatically delete the unlinked element.
 384     (void)next_->unlink();
 385   }
 386
 387   // Decrement our refcount on the current buffer
 388   decrementRefcount();
 389
 390   // Take ownership of the other buffer's data
 391   data_ = other.data_;
 392   buf_ = other.buf_;
 393   length_ = other.length_;
 394   capacity_ = other.capacity_;
 395   flagsAndSharedInfo_ = other.flagsAndSharedInfo_;
 396   // Reset other so it is a clean state to be destroyed.
 397   other.data_ = nullptr;
 398   other.buf_ = nullptr;
 399   other.length_ = 0;
 400   other.capacity_ = 0;
 401   other.flagsAndSharedInfo_ = 0;
 402
 403   // If other was part of the chain, assume ownership of the rest of its chain.
 404   // (It's only valid to perform move assignment on the head of a chain.)
 405   if (other.next_ != &other) {
 406     next_ = other.next_;
 407     next_->prev_ = this;
 408     other.next_ = &other;
 409
 410     prev_ = other.prev_;
 411     prev_->next_ = this;
 412     other.prev_ = &other;
 413   }
 414
 415   // Sanity check to make sure that other is in a valid state to be destroyed.
 416   DCHECK_EQ(other.prev_, &other);
 417   DCHECK_EQ(other.next_, &other);
 418
 419   return *this;
 420 }
 421
 422 IOBuf& IOBuf::operator=(const IOBuf& other) {
 423   if (this != &other) {
 424     *this = IOBuf(other);
 425   }
 426   return *this;
 427 }
 428
 429 bool IOBuf::empty() const {
 430   const IOBuf* current = this;
 431   do {
 432     if (current->length() != 0) {
 433       return false;
 434     }
 435     current = current->next_;
 436   } while (current != this);
 437   return true;
 438 }
 439
 440 size_t IOBuf::countChainElements() const {
 441   size_t numElements = 1;
 442   for (IOBuf* current = next_; current != this; current = current->next_) {
 443     ++numElements;
 444   }
 445   return numElements;
 446 }
 447
 448 uint64_t IOBuf::computeChainDataLength() const {
 449   uint64_t fullLength = length_;
 450   for (IOBuf* current = next_; current != this; current = current->next_) {
 451     fullLength += current->length_;
 452   }
 453   return fullLength;
 454 }
 455
 456 void IOBuf::prependChain(unique_ptr<IOBuf>&& iobuf) {
 457   // Take ownership of the specified IOBuf
 458   IOBuf* other = iobuf.release();
 459
 460   // Remember the pointer to the tail of the other chain
 461   IOBuf* otherTail = other->prev_;
 462
 463   // Hook up prev_->next_ to point at the start of the other chain,
 464   // and other->prev_ to point at prev_
 465   prev_->next_ = other;
 466   other->prev_ = prev_;
 467
 468   // Hook up otherTail->next_ to point at us,
 469   // and prev_ to point back at otherTail,
 470   otherTail->next_ = this;
 471   prev_ = otherTail;
 472 }
 473
 474 unique_ptr<IOBuf> IOBuf::clone() const {
 475   unique_ptr<IOBuf> ret = make_unique<IOBuf>();
 476   cloneInto(*ret);
 477   return ret;
 478 }
 479
 480 unique_ptr<IOBuf> IOBuf::cloneOne() const {
 481   unique_ptr<IOBuf> ret = make_unique<IOBuf>();
 482   cloneOneInto(*ret);
 483   return ret;
 484 }
 485
 486 void IOBuf::cloneInto(IOBuf& other) const {
 487   IOBuf tmp;
 488   cloneOneInto(tmp);
 489
 490   for (IOBuf* current = next_; current != this; current = current->next_) {
 491     tmp.prependChain(current->cloneOne());
 492   }
 493
 494   other = std::move(tmp);
 495 }
 496
 497 void IOBuf::cloneOneInto(IOBuf& other) const {
 498   SharedInfo* info = sharedInfo();
 499   if (info) {
 500     setFlags(kFlagMaybeShared);
 501   }
 502   other = IOBuf(InternalConstructor(),
 503                 flagsAndSharedInfo_, buf_, capacity_,
 504                 data_, length_);
 505   if (info) {
 506     info->refcount.fetch_add(1, std::memory_order_acq_rel);
 507   }
 508 }
 509
 510 void IOBuf::unshareOneSlow() {
 511   // Allocate a new buffer for the data
 512   uint8_t* buf;
 513   SharedInfo* sharedInfo;
 514   uint64_t actualCapacity;
 515   allocExtBuffer(capacity_, &buf, &sharedInfo, &actualCapacity);
 516
 517   // Copy the data
 518   // Maintain the same amount of headroom.  Since we maintained the same
 519   // minimum capacity we also maintain at least the same amount of tailroom.
 520   uint64_t headlen = headroom();
 521   memcpy(buf + headlen, data_, length_);
 522
 523   // Release our reference on the old buffer
 524   decrementRefcount();
 525   // Make sure kFlagMaybeShared and kFlagFreeSharedInfo are all cleared.
 526   setFlagsAndSharedInfo(0, sharedInfo);
 527
 528   // Update the buffer pointers to point to the new buffer
 529   data_ = buf + headlen;
 530   buf_ = buf;
 531 }
 532
 533 void IOBuf::unshareChained() {
 534   // unshareChained() should only be called if we are part of a chain of
 535   // multiple IOBufs.  The caller should have already verified this.
 536   assert(isChained());
 537
 538   IOBuf* current = this;
 539   while (true) {
 540     if (current->isSharedOne()) {
 541       // we have to unshare
 542       break;
 543     }
 544
 545     current = current->next_;
 546     if (current == this) {
 547       // None of the IOBufs in the chain are shared,
 548       // so return without doing anything
 549       return;
 550     }
 551   }
 552
 553   // We have to unshare.  Let coalesceSlow() do the work.
 554   coalesceSlow();
 555 }
 556
 557 void IOBuf::makeManagedChained() {
 558   assert(isChained());
 559
 560   IOBuf* current = this;
 561   while (true) {
 562     current->makeManagedOne();
 563     current = current->next_;
 564     if (current == this) {
 565       break;
 566     }
 567   }
 568 }
 569
 570 void IOBuf::coalesceSlow() {
 571   // coalesceSlow() should only be called if we are part of a chain of multiple
 572   // IOBufs.  The caller should have already verified this.
 573   DCHECK(isChained());
 574
 575   // Compute the length of the entire chain
 576   uint64_t newLength = 0;
 577   IOBuf* end = this;
 578   do {
 579     newLength += end->length_;
 580     end = end->next_;
 581   } while (end != this);
 582
 583   coalesceAndReallocate(newLength, end);
 584   // We should be only element left in the chain now
 585   DCHECK(!isChained());
 586 }
 587
 588 void IOBuf::coalesceSlow(size_t maxLength) {
 589   // coalesceSlow() should only be called if we are part of a chain of multiple
 590   // IOBufs.  The caller should have already verified this.
 591   DCHECK(isChained());
 592   DCHECK_LT(length_, maxLength);
 593
 594   // Compute the length of the entire chain
 595   uint64_t newLength = 0;
 596   IOBuf* end = this;
 597   while (true) {
 598     newLength += end->length_;
 599     end = end->next_;
 600     if (newLength >= maxLength) {
 601       break;
 602     }
 603     if (end == this) {
 604       throw std::overflow_error("attempted to coalesce more data than "
 605                                 "available");
 606     }
 607   }
 608
 609   coalesceAndReallocate(newLength, end);
 610   // We should have the requested length now
 611   DCHECK_GE(length_, maxLength);
 612 }
 613
 614 void IOBuf::coalesceAndReallocate(size_t newHeadroom,
 615                                   size_t newLength,
 616                                   IOBuf* end,
 617                                   size_t newTailroom) {
 618   uint64_t newCapacity = newLength + newHeadroom + newTailroom;
 619
 620   // Allocate space for the coalesced buffer.
 621   // We always convert to an external buffer, even if we happened to be an
 622   // internal buffer before.
 623   uint8_t* newBuf;
 624   SharedInfo* newInfo;
 625   uint64_t actualCapacity;
 626   allocExtBuffer(newCapacity, &newBuf, &newInfo, &actualCapacity);
 627
 628   // Copy the data into the new buffer
 629   uint8_t* newData = newBuf + newHeadroom;
 630   uint8_t* p = newData;
 631   IOBuf* current = this;
 632   size_t remaining = newLength;
 633   do {
 634     assert(current->length_ <= remaining);
 635     remaining -= current->length_;
 636     memcpy(p, current->data_, current->length_);
 637     p += current->length_;
 638     current = current->next_;
 639   } while (current != end);
 640   assert(remaining == 0);
 641
 642   // Point at the new buffer
 643   decrementRefcount();
 644
 645   // Make sure kFlagMaybeShared and kFlagFreeSharedInfo are all cleared.
 646   setFlagsAndSharedInfo(0, newInfo);
 647
 648   capacity_ = actualCapacity;
 649   buf_ = newBuf;
 650   data_ = newData;
 651   length_ = newLength;
 652
 653   // Separate from the rest of our chain.
 654   // Since we don't store the unique_ptr returned by separateChain(),
 655   // this will immediately delete the returned subchain.
 656   if (isChained()) {
 657     (void)separateChain(next_, current->prev_);
 658   }
 659 }
 660
 661 void IOBuf::decrementRefcount() {
 662   // Externally owned buffers don't have a SharedInfo object and aren't managed
 663   // by the reference count
 664   SharedInfo* info = sharedInfo();
 665   if (!info) {
 666     return;
 667   }
 668
 669   // Decrement the refcount
 670   uint32_t newcnt = info->refcount.fetch_sub(
 671       1, std::memory_order_acq_rel);
 672   // Note that fetch_sub() returns the value before we decremented.
 673   // If it is 1, we were the only remaining user; if it is greater there are
 674   // still other users.
 675   if (newcnt > 1) {
 676     return;
 677   }
 678
 679   // We were the last user.  Free the buffer
 680   freeExtBuffer();
 681
 682   // Free the SharedInfo if it was allocated separately.
 683   //
 684   // This is only used by takeOwnership().
 685   //
 686   // To avoid this special case handling in decrementRefcount(), we could have
 687   // takeOwnership() set a custom freeFn() that calls the user's free function
 688   // then frees the SharedInfo object.  (This would require that
 689   // takeOwnership() store the user's free function with its allocated
 690   // SharedInfo object.)  However, handling this specially with a flag seems
 691   // like it shouldn't be problematic.
 692   if (flags() & kFlagFreeSharedInfo) {
 693     delete sharedInfo();
 694   }
 695 }
 696
 697 void IOBuf::reserveSlow(uint64_t minHeadroom, uint64_t minTailroom) {
 698   size_t newCapacity = (size_t)length_ + minHeadroom + minTailroom;
 699   DCHECK_LT(newCapacity, UINT32_MAX);
 700
 701   // reserveSlow() is dangerous if anyone else is sharing the buffer, as we may
 702   // reallocate and free the original buffer.  It should only ever be called if
 703   // we are the only user of the buffer.
 704   DCHECK(!isSharedOne());
 705
 706   // We'll need to reallocate the buffer.
 707   // There are a few options.
 708   // - If we have enough total room, move the data around in the buffer
 709   //   and adjust the data_ pointer.
 710   // - If we're using an internal buffer, we'll switch to an external
 711   //   buffer with enough headroom and tailroom.
 712   // - If we have enough headroom (headroom() >= minHeadroom) but not too much
 713   //   (so we don't waste memory), we can try one of two things, depending on
 714   //   whether we use jemalloc or not:
 715   //   - If using jemalloc, we can try to expand in place, avoiding a memcpy()
 716   //   - If not using jemalloc and we don't have too much to copy,
 717   //     we'll use realloc() (note that realloc might have to copy
 718   //     headroom + data + tailroom, see smartRealloc in folly/Malloc.h)
 719   // - Otherwise, bite the bullet and reallocate.
 720   if (headroom() + tailroom() >= minHeadroom + minTailroom) {
 721     uint8_t* newData = writableBuffer() + minHeadroom;
 722     memmove(newData, data_, length_);
 723     data_ = newData;
 724     return;
 725   }
 726
 727   size_t newAllocatedCapacity = 0;
 728   uint8_t* newBuffer = nullptr;
 729   uint64_t newHeadroom = 0;
 730   uint64_t oldHeadroom = headroom();
 731
 732   // If we have a buffer allocated with malloc and we just need more tailroom,
 733   // try to use realloc()/xallocx() to grow the buffer in place.
 734   SharedInfo* info = sharedInfo();
 735   if (info && (info->freeFn == nullptr) && length_ != 0 &&
 736       oldHeadroom >= minHeadroom) {
 737     size_t headSlack = oldHeadroom - minHeadroom;
 738     newAllocatedCapacity = goodExtBufferSize(newCapacity + headSlack);
 739     if (usingJEMalloc()) {
 740       // We assume that tailroom is more useful and more important than
 741       // headroom (not least because realloc / xallocx allow us to grow the
 742       // buffer at the tail, but not at the head)  So, if we have more headroom
 743       // than we need, we consider that "wasted".  We arbitrarily define "too
 744       // much" headroom to be 25% of the capacity.
 745       if (headSlack * 4 <= newCapacity) {
 746         size_t allocatedCapacity = capacity() + sizeof(SharedInfo);
 747         void* p = buf_;
 748         if (allocatedCapacity >= jemallocMinInPlaceExpandable) {
 749           if (xallocx(p, newAllocatedCapacity, 0, 0) == newAllocatedCapacity) {
 750             newBuffer = static_cast<uint8_t*>(p);
 751             newHeadroom = oldHeadroom;
 752           }
 753           // if xallocx failed, do nothing, fall back to malloc/memcpy/free
 754         }
 755       }
 756     } else {  // Not using jemalloc
 757       size_t copySlack = capacity() - length_;
 758       if (copySlack * 2 <= length_) {
 759         void* p = realloc(buf_, newAllocatedCapacity);
 760         if (UNLIKELY(p == nullptr)) {
 761           throw std::bad_alloc();
 762         }
 763         newBuffer = static_cast<uint8_t*>(p);
 764         newHeadroom = oldHeadroom;
 765       }
 766     }
 767   }
 768
 769   // None of the previous reallocation strategies worked (or we're using
 770   // an internal buffer).  malloc/copy/free.
 771   if (newBuffer == nullptr) {
 772     newAllocatedCapacity = goodExtBufferSize(newCapacity);
 773     void* p = malloc(newAllocatedCapacity);
 774     if (UNLIKELY(p == nullptr)) {
 775       throw std::bad_alloc();
 776     }
 777     newBuffer = static_cast<uint8_t*>(p);
 778     memcpy(newBuffer + minHeadroom, data_, length_);
 779     if (sharedInfo()) {
 780       freeExtBuffer();
 781     }
 782     newHeadroom = minHeadroom;
 783   }
 784
 785   uint64_t cap;
 786   initExtBuffer(newBuffer, newAllocatedCapacity, &info, &cap);
 787
 788   if (flags() & kFlagFreeSharedInfo) {
 789     delete sharedInfo();
 790   }
 791
 792   setFlagsAndSharedInfo(0, info);
 793   capacity_ = cap;
 794   buf_ = newBuffer;
 795   data_ = newBuffer + newHeadroom;
 796   // length_ is unchanged
 797 }
 798
 799 void IOBuf::freeExtBuffer() {
 800   SharedInfo* info = sharedInfo();
 801   DCHECK(info);
 802
 803   if (info->freeFn) {
 804     try {
 805       info->freeFn(buf_, info->userData);
 806     } catch (...) {
 807       // The user's free function should never throw.  Otherwise we might
 808       // throw from the IOBuf destructor.  Other code paths like coalesce()
 809       // also assume that decrementRefcount() cannot throw.
 810       abort();
 811     }
 812   } else {
 813     free(buf_);
 814   }
 815 }
 816
 817 void IOBuf::allocExtBuffer(uint64_t minCapacity,
 818                            uint8_t** bufReturn,
 819                            SharedInfo** infoReturn,
 820                            uint64_t* capacityReturn) {
 821   size_t mallocSize = goodExtBufferSize(minCapacity);
 822   uint8_t* buf = static_cast<uint8_t*>(malloc(mallocSize));
 823   if (UNLIKELY(buf == nullptr)) {
 824     throw std::bad_alloc();
 825   }
 826   initExtBuffer(buf, mallocSize, infoReturn, capacityReturn);
 827   *bufReturn = buf;
 828 }
 829
 830 size_t IOBuf::goodExtBufferSize(uint64_t minCapacity) {
 831   // Determine how much space we should allocate.  We'll store the SharedInfo
 832   // for the external buffer just after the buffer itself.  (We store it just
 833   // after the buffer rather than just before so that the code can still just
 834   // use free(buf_) to free the buffer.)
 835   size_t minSize = static_cast<size_t>(minCapacity) + sizeof(SharedInfo);
 836   // Add room for padding so that the SharedInfo will be aligned on an 8-byte
 837   // boundary.
 838   minSize = (minSize + 7) & ~7;
 839
 840   // Use goodMallocSize() to bump up the capacity to a decent size to request
 841   // from malloc, so we can use all of the space that malloc will probably give
 842   // us anyway.
 843   return goodMallocSize(minSize);
 844 }
 845
 846 void IOBuf::initExtBuffer(uint8_t* buf, size_t mallocSize,
 847                           SharedInfo** infoReturn,
 848                           uint64_t* capacityReturn) {
 849   // Find the SharedInfo storage at the end of the buffer
 850   // and construct the SharedInfo.
 851   uint8_t* infoStart = (buf + mallocSize) - sizeof(SharedInfo);
 852   SharedInfo* sharedInfo = new(infoStart) SharedInfo;
 853
 854   *capacityReturn = infoStart - buf;
 855   *infoReturn = sharedInfo;
 856 }
 857
 858 fbstring IOBuf::moveToFbString() {
 859   // malloc-allocated buffers are just fine, everything else needs
 860   // to be turned into one.
 861   if (!sharedInfo() ||         // user owned, not ours to give up
 862       sharedInfo()->freeFn ||  // not malloc()-ed
 863       headroom() != 0 ||       // malloc()-ed block doesn't start at beginning
 864       tailroom() == 0 ||       // no room for NUL terminator
 865       isShared() ||            // shared
 866       isChained()) {           // chained
 867     // We might as well get rid of all head and tailroom if we're going
 868     // to reallocate; we need 1 byte for NUL terminator.
 869     coalesceAndReallocate(0, computeChainDataLength(), this, 1);
 870   }
 871
 872   // Ensure NUL terminated
 873   *writableTail() = 0;
 874   fbstring str(reinterpret_cast<char*>(writableData()),
 875                length(),  capacity(),
 876                AcquireMallocatedString());
 877
 878   if (flags() & kFlagFreeSharedInfo) {
 879     delete sharedInfo();
 880   }
 881
 882   // Reset to a state where we can be deleted cleanly
 883   flagsAndSharedInfo_ = 0;
 884   buf_ = nullptr;
 885   clear();
 886   return str;
 887 }
 888
 889 IOBuf::Iterator IOBuf::cbegin() const {
 890   return Iterator(this, this);
 891 }
 892
 893 IOBuf::Iterator IOBuf::cend() const {
 894   return Iterator(nullptr, nullptr);
 895 }
 896
 897 folly::fbvector<struct iovec> IOBuf::getIov() const {
 898   folly::fbvector<struct iovec> iov;
 899   iov.reserve(countChainElements());
 900   appendToIov(&iov);
 901   return iov;
 902 }
 903
 904 void IOBuf::appendToIov(folly::fbvector<struct iovec>* iov) const {
 905   IOBuf const* p = this;
 906   do {
 907     // some code can get confused by empty iovs, so skip them
 908     if (p->length() > 0) {
 909       iov->push_back({(void*)p->data(), folly::to<size_t>(p->length())});
 910     }
 911     p = p->next();
 912   } while (p != this);
 913 }
 914
 915 size_t IOBuf::fillIov(struct iovec* iov, size_t len) const {
 916   IOBuf const* p = this;
 917   size_t i = 0;
 918   while (i < len) {
 919     // some code can get confused by empty iovs, so skip them
 920     if (p->length() > 0) {
 921       iov[i].iov_base = const_cast<uint8_t*>(p->data());
 922       iov[i].iov_len = p->length();
 923       i++;
 924     }
 925     p = p->next();
 926     if (p == this) {
 927       return i;
 928     }
 929   }
 930   return 0;
 931 }
 932
 933 size_t IOBufHash::operator()(const IOBuf& buf) const {
 934   folly::hash::SpookyHashV2 hasher;
 935   hasher.Init(0, 0);
 936   io::Cursor cursor(&buf);
 937   for (;;) {
 938     auto p = cursor.peek();
 939     if (p.second == 0) {
 940       break;
 941     }
 942     hasher.Update(p.first, p.second);
 943     cursor.skip(p.second);
 944   }
 945   uint64_t h1;
 946   uint64_t h2;
 947   hasher.Final(&h1, &h2);
 948   return h1;
 949 }
 950
 951 bool IOBufEqual::operator()(const IOBuf& a, const IOBuf& b) const {
 952   io::Cursor ca(&a);
 953   io::Cursor cb(&b);
 954   for (;;) {
 955     auto pa = ca.peek();
 956     auto pb = cb.peek();
 957     if (pa.second == 0 && pb.second == 0) {
 958       return true;
 959     } else if (pa.second == 0 || pb.second == 0) {
 960       return false;
 961     }
 962     size_t n = std::min(pa.second, pb.second);
 963     DCHECK_GT(n, 0);
 964     if (memcmp(pa.first, pb.first, n)) {
 965       return false;
 966     }
 967     ca.skip(n);
 968     cb.skip(n);
 969   }
 970 }
 971
 972 } // folly