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