folly/io/IOBuf.cpp

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