2 * Copyright 2013 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #define __STDC_LIMIT_MACROS
19 #include "folly/io/IOBuf.h"
21 #include "folly/Malloc.h"
22 #include "folly/Likely.h"
29 using std::unique_ptr;
35 // This memory segment contains an IOBuf that is still in use
37 // This memory segment contains buffer data that is still in use
42 // When create() is called for buffers less than kDefaultCombinedBufSize,
43 // we allocate a single combined memory segment for the IOBuf and the data
44 // together. See the comments for createCombined()/createSeparate() for more
47 // (The size of 1k is largely just a guess here. We could could probably do
48 // benchmarks of real applications to see if adjusting this number makes a
49 // difference. Callers that know their exact use case can also explicitly
50 // call createCombined() or createSeparate().)
51 kDefaultCombinedBufSize = 1024
58 struct IOBuf::HeapPrefix {
59 HeapPrefix(uint16_t flg)
63 // Reset magic to 0 on destruction. This is solely for debugging purposes
64 // to help catch bugs where someone tries to use HeapStorage after it has
70 std::atomic<uint16_t> flags;
73 struct IOBuf::HeapStorage {
75 // The IOBuf is last in the HeapStorage object.
76 // This way operator new will work even if allocating a subclass of IOBuf
77 // that requires more space.
81 struct IOBuf::HeapFullStorage {
87 IOBuf::SharedInfo::SharedInfo()
90 // Use relaxed memory ordering here. Since we are creating a new SharedInfo,
91 // no other threads should be referring to it yet.
92 refcount.store(1, std::memory_order_relaxed);
95 IOBuf::SharedInfo::SharedInfo(FreeFunction fn, void* arg)
98 // Use relaxed memory ordering here. Since we are creating a new SharedInfo,
99 // no other threads should be referring to it yet.
100 refcount.store(1, std::memory_order_relaxed);
103 void* IOBuf::operator new(size_t size) {
104 size_t fullSize = offsetof(HeapStorage, buf) + size;
105 auto* storage = static_cast<HeapStorage*>(malloc(fullSize));
106 // operator new is not allowed to return NULL
107 if (UNLIKELY(storage == nullptr)) {
108 throw std::bad_alloc();
111 new (&storage->prefix) HeapPrefix(kIOBufInUse);
112 return &(storage->buf);
115 void* IOBuf::operator new(size_t size, void* ptr) {
119 void IOBuf::operator delete(void* ptr) {
120 auto* storageAddr = static_cast<uint8_t*>(ptr) - offsetof(HeapStorage, buf);
121 auto* storage = reinterpret_cast<HeapStorage*>(storageAddr);
122 releaseStorage(storage, kIOBufInUse);
125 void IOBuf::releaseStorage(HeapStorage* storage, uint16_t freeFlags) {
126 CHECK_EQ(storage->prefix.magic, static_cast<uint16_t>(kHeapMagic));
128 // Use relaxed memory order here. If we are unlucky and happen to get
129 // out-of-date data the compare_exchange_weak() call below will catch
130 // it and load new data with memory_order_acq_rel.
131 auto flags = storage->prefix.flags.load(std::memory_order_acquire);
132 DCHECK_EQ((flags & freeFlags), freeFlags);
135 uint16_t newFlags = (flags & ~freeFlags);
137 // The storage space is now unused. Free it.
138 storage->prefix.HeapPrefix::~HeapPrefix();
143 // This storage segment still contains portions that are in use.
144 // Just clear the flags specified in freeFlags for now.
145 auto ret = storage->prefix.flags.compare_exchange_weak(
146 flags, newFlags, std::memory_order_acq_rel);
148 // We successfully updated the flags.
152 // We failed to update the flags. Some other thread probably updated them
153 // and cleared some of the other bits. Continue around the loop to see if
154 // we are the last user now, or if we need to try updating the flags again.
158 void IOBuf::freeInternalBuf(void* buf, void* userData) {
159 auto* storage = static_cast<HeapStorage*>(userData);
160 releaseStorage(storage, kDataInUse);
163 unique_ptr<IOBuf> IOBuf::create(uint32_t capacity) {
164 // For smaller-sized buffers, allocate the IOBuf, SharedInfo, and the buffer
165 // all with a single allocation.
167 // We don't do this for larger buffers since it can be wasteful if the user
168 // needs to reallocate the buffer but keeps using the same IOBuf object.
169 // In this case we can't free the data space until the IOBuf is also
170 // destroyed. Callers can explicitly call createCombined() or
171 // createSeparate() if they know their use case better, and know if they are
172 // likely to reallocate the buffer later.
173 if (capacity <= kDefaultCombinedBufSize) {
174 return createCombined(capacity);
176 return createSeparate(capacity);
179 unique_ptr<IOBuf> IOBuf::createCombined(uint32_t capacity) {
180 // To save a memory allocation, allocate space for the IOBuf object, the
181 // SharedInfo struct, and the data itself all with a single call to malloc().
182 size_t requiredStorage = offsetof(HeapFullStorage, align) + capacity;
183 size_t mallocSize = goodMallocSize(requiredStorage);
184 auto* storage = static_cast<HeapFullStorage*>(malloc(mallocSize));
186 new (&storage->hs.prefix) HeapPrefix(kIOBufInUse | kDataInUse);
187 new (&storage->shared) SharedInfo(freeInternalBuf, storage);
189 uint8_t* bufAddr = reinterpret_cast<uint8_t*>(&storage->align);
190 uint8_t* storageEnd = reinterpret_cast<uint8_t*>(storage) + mallocSize;
191 size_t actualCapacity = storageEnd - bufAddr;
192 unique_ptr<IOBuf> ret(new (&storage->hs.buf) IOBuf(
193 kCombinedAlloc, 0, bufAddr, actualCapacity,
194 bufAddr, 0, &storage->shared));
198 unique_ptr<IOBuf> IOBuf::createSeparate(uint32_t capacity) {
199 // Allocate an external buffer
201 SharedInfo* sharedInfo;
202 uint32_t actualCapacity;
203 allocExtBuffer(capacity, &buf, &sharedInfo, &actualCapacity);
205 // Allocate the IOBuf header
207 return unique_ptr<IOBuf>(new IOBuf(kExtAllocated, 0,
217 unique_ptr<IOBuf> IOBuf::createChain(
218 size_t totalCapacity, uint32_t maxBufCapacity) {
219 unique_ptr<IOBuf> out = create(
220 std::min(totalCapacity, size_t(maxBufCapacity)));
221 size_t allocatedCapacity = out->capacity();
223 while (allocatedCapacity < totalCapacity) {
224 unique_ptr<IOBuf> newBuf = create(
225 std::min(totalCapacity - allocatedCapacity, size_t(maxBufCapacity)));
226 allocatedCapacity += newBuf->capacity();
227 out->prependChain(std::move(newBuf));
233 unique_ptr<IOBuf> IOBuf::takeOwnership(void* buf, uint32_t capacity,
238 SharedInfo* sharedInfo = NULL;
240 // TODO: We could allocate the IOBuf object and SharedInfo all in a single
241 // memory allocation. We could use the existing HeapStorage class, and
242 // define a new kSharedInfoInUse flag. We could change our code to call
243 // releaseStorage(kFlagFreeSharedInfo) when this kFlagFreeSharedInfo,
244 // rather than directly calling delete.
245 sharedInfo = new SharedInfo(freeFn, userData);
247 uint8_t* bufPtr = static_cast<uint8_t*>(buf);
248 return unique_ptr<IOBuf>(new IOBuf(kExtUserSupplied, kFlagFreeSharedInfo,
257 freeFn(buf, userData);
259 // The user's free function is not allowed to throw.
270 unique_ptr<IOBuf> IOBuf::wrapBuffer(const void* buf, uint32_t capacity) {
271 // We cast away the const-ness of the buffer here.
272 // This is okay since IOBuf users must use unshare() to create a copy of
273 // this buffer before writing to the buffer.
274 uint8_t* bufPtr = static_cast<uint8_t*>(const_cast<void*>(buf));
275 return unique_ptr<IOBuf>(new IOBuf(kExtUserSupplied, kFlagUserOwned,
281 IOBuf::IOBuf(ExtBufTypeEnum type,
287 SharedInfo* sharedInfo)
296 sharedInfo_(sharedInfo) {
298 assert(data + length <= buf + capacity);
299 assert(static_cast<bool>(flags & kFlagUserOwned) ==
300 (sharedInfo == NULL));
304 // Destroying an IOBuf destroys the entire chain.
305 // Users of IOBuf should only explicitly delete the head of any chain.
306 // The other elements in the chain will be automatically destroyed.
307 while (next_ != this) {
308 // Since unlink() returns unique_ptr() and we don't store it,
309 // it will automatically delete the unlinked element.
310 (void)next_->unlink();
316 bool IOBuf::empty() const {
317 const IOBuf* current = this;
319 if (current->length() != 0) {
322 current = current->next_;
323 } while (current != this);
327 uint32_t IOBuf::countChainElements() const {
328 uint32_t numElements = 1;
329 for (IOBuf* current = next_; current != this; current = current->next_) {
335 uint64_t IOBuf::computeChainDataLength() const {
336 uint64_t fullLength = length_;
337 for (IOBuf* current = next_; current != this; current = current->next_) {
338 fullLength += current->length_;
343 void IOBuf::prependChain(unique_ptr<IOBuf>&& iobuf) {
344 // Take ownership of the specified IOBuf
345 IOBuf* other = iobuf.release();
347 // Remember the pointer to the tail of the other chain
348 IOBuf* otherTail = other->prev_;
350 // Hook up prev_->next_ to point at the start of the other chain,
351 // and other->prev_ to point at prev_
352 prev_->next_ = other;
353 other->prev_ = prev_;
355 // Hook up otherTail->next_ to point at us,
356 // and prev_ to point back at otherTail,
357 otherTail->next_ = this;
361 unique_ptr<IOBuf> IOBuf::clone() const {
362 unique_ptr<IOBuf> newHead(cloneOne());
364 for (IOBuf* current = next_; current != this; current = current->next_) {
365 newHead->prependChain(current->cloneOne());
371 unique_ptr<IOBuf> IOBuf::cloneOne() const {
373 flags_ |= kFlagMaybeShared;
375 unique_ptr<IOBuf> iobuf(new IOBuf(static_cast<ExtBufTypeEnum>(type_),
376 flags_, buf_, capacity_,
380 sharedInfo_->refcount.fetch_add(1, std::memory_order_acq_rel);
385 void IOBuf::unshareOneSlow() {
386 // Allocate a new buffer for the data
388 SharedInfo* sharedInfo;
389 uint32_t actualCapacity;
390 allocExtBuffer(capacity_, &buf, &sharedInfo, &actualCapacity);
393 // Maintain the same amount of headroom. Since we maintained the same
394 // minimum capacity we also maintain at least the same amount of tailroom.
395 uint32_t headlen = headroom();
396 memcpy(buf + headlen, data_, length_);
398 // Release our reference on the old buffer
400 // Make sure kFlagUserOwned, kFlagMaybeShared, and kFlagFreeSharedInfo
404 // Update the buffer pointers to point to the new buffer
405 data_ = buf + headlen;
407 sharedInfo_ = sharedInfo;
410 void IOBuf::unshareChained() {
411 // unshareChained() should only be called if we are part of a chain of
412 // multiple IOBufs. The caller should have already verified this.
415 IOBuf* current = this;
417 if (current->isSharedOne()) {
418 // we have to unshare
422 current = current->next_;
423 if (current == this) {
424 // None of the IOBufs in the chain are shared,
425 // so return without doing anything
430 // We have to unshare. Let coalesceSlow() do the work.
434 void IOBuf::coalesceSlow() {
435 // coalesceSlow() should only be called if we are part of a chain of multiple
436 // IOBufs. The caller should have already verified this.
439 // Compute the length of the entire chain
440 uint64_t newLength = 0;
443 newLength += end->length_;
445 } while (end != this);
447 coalesceAndReallocate(newLength, end);
448 // We should be only element left in the chain now
449 DCHECK(!isChained());
452 void IOBuf::coalesceSlow(size_t maxLength) {
453 // coalesceSlow() should only be called if we are part of a chain of multiple
454 // IOBufs. The caller should have already verified this.
456 DCHECK_LT(length_, maxLength);
458 // Compute the length of the entire chain
459 uint64_t newLength = 0;
462 newLength += end->length_;
464 if (newLength >= maxLength) {
468 throw std::overflow_error("attempted to coalesce more data than "
473 coalesceAndReallocate(newLength, end);
474 // We should have the requested length now
475 DCHECK_GE(length_, maxLength);
478 void IOBuf::coalesceAndReallocate(size_t newHeadroom,
481 size_t newTailroom) {
482 uint64_t newCapacity = newLength + newHeadroom + newTailroom;
483 if (newCapacity > UINT32_MAX) {
484 throw std::overflow_error("IOBuf chain too large to coalesce");
487 // Allocate space for the coalesced buffer.
488 // We always convert to an external buffer, even if we happened to be an
489 // internal buffer before.
492 uint32_t actualCapacity;
493 allocExtBuffer(newCapacity, &newBuf, &newInfo, &actualCapacity);
495 // Copy the data into the new buffer
496 uint8_t* newData = newBuf + newHeadroom;
497 uint8_t* p = newData;
498 IOBuf* current = this;
499 size_t remaining = newLength;
501 assert(current->length_ <= remaining);
502 remaining -= current->length_;
503 memcpy(p, current->data_, current->length_);
504 p += current->length_;
505 current = current->next_;
506 } while (current != end);
507 assert(remaining == 0);
509 // Point at the new buffer
512 // Make sure kFlagUserOwned, kFlagMaybeShared, and kFlagFreeSharedInfo
516 capacity_ = actualCapacity;
517 type_ = kExtAllocated;
519 sharedInfo_ = newInfo;
523 // Separate from the rest of our chain.
524 // Since we don't store the unique_ptr returned by separateChain(),
525 // this will immediately delete the returned subchain.
527 (void)separateChain(next_, current->prev_);
531 void IOBuf::decrementRefcount() {
532 // Externally owned buffers don't have a SharedInfo object and aren't managed
533 // by the reference count
534 if (flags_ & kFlagUserOwned) {
535 assert(sharedInfo_ == nullptr);
539 // Decrement the refcount
540 uint32_t newcnt = sharedInfo_->refcount.fetch_sub(
541 1, std::memory_order_acq_rel);
542 // Note that fetch_sub() returns the value before we decremented.
543 // If it is 1, we were the only remaining user; if it is greater there are
544 // still other users.
549 // We were the last user. Free the buffer
552 // Free the SharedInfo if it was allocated separately.
554 // This is only used by takeOwnership().
556 // To avoid this special case handling in decrementRefcount(), we could have
557 // takeOwnership() set a custom freeFn() that calls the user's free function
558 // then frees the SharedInfo object. (This would require that
559 // takeOwnership() store the user's free function with its allocated
560 // SharedInfo object.) However, handling this specially with a flag seems
561 // like it shouldn't be problematic.
562 if (flags_ & kFlagFreeSharedInfo) {
567 void IOBuf::reserveSlow(uint32_t minHeadroom, uint32_t minTailroom) {
568 size_t newCapacity = (size_t)length_ + minHeadroom + minTailroom;
569 DCHECK_LT(newCapacity, UINT32_MAX);
571 // reserveSlow() is dangerous if anyone else is sharing the buffer, as we may
572 // reallocate and free the original buffer. It should only ever be called if
573 // we are the only user of the buffer.
574 DCHECK(!isSharedOne());
576 // We'll need to reallocate the buffer.
577 // There are a few options.
578 // - If we have enough total room, move the data around in the buffer
579 // and adjust the data_ pointer.
580 // - If we're using an internal buffer, we'll switch to an external
581 // buffer with enough headroom and tailroom.
582 // - If we have enough headroom (headroom() >= minHeadroom) but not too much
583 // (so we don't waste memory), we can try one of two things, depending on
584 // whether we use jemalloc or not:
585 // - If using jemalloc, we can try to expand in place, avoiding a memcpy()
586 // - If not using jemalloc and we don't have too much to copy,
587 // we'll use realloc() (note that realloc might have to copy
588 // headroom + data + tailroom, see smartRealloc in folly/Malloc.h)
589 // - Otherwise, bite the bullet and reallocate.
590 if (headroom() + tailroom() >= minHeadroom + minTailroom) {
591 uint8_t* newData = writableBuffer() + minHeadroom;
592 memmove(newData, data_, length_);
597 size_t newAllocatedCapacity = goodExtBufferSize(newCapacity);
598 uint8_t* newBuffer = nullptr;
599 uint32_t newHeadroom = 0;
600 uint32_t oldHeadroom = headroom();
602 // If we have a buffer allocated with malloc and we just need more tailroom,
603 // try to use realloc()/rallocm() to grow the buffer in place.
604 if ((flags_ & kFlagUserOwned) == 0 && (sharedInfo_->freeFn == nullptr) &&
605 length_ != 0 && oldHeadroom >= minHeadroom) {
606 if (usingJEMalloc()) {
607 size_t headSlack = oldHeadroom - minHeadroom;
608 // We assume that tailroom is more useful and more important than
609 // headroom (not least because realloc / rallocm allow us to grow the
610 // buffer at the tail, but not at the head) So, if we have more headroom
611 // than we need, we consider that "wasted". We arbitrarily define "too
612 // much" headroom to be 25% of the capacity.
613 if (headSlack * 4 <= newCapacity) {
614 size_t allocatedCapacity = capacity() + sizeof(SharedInfo);
616 if (allocatedCapacity >= jemallocMinInPlaceExpandable) {
617 int r = rallocm(&p, &newAllocatedCapacity, newAllocatedCapacity,
619 if (r == ALLOCM_SUCCESS) {
620 newBuffer = static_cast<uint8_t*>(p);
621 newHeadroom = oldHeadroom;
622 } else if (r == ALLOCM_ERR_OOM) {
623 // shouldn't happen as we don't actually allocate new memory
624 // (due to ALLOCM_NO_MOVE)
625 throw std::bad_alloc();
627 // if ALLOCM_ERR_NOT_MOVED, do nothing, fall back to
628 // malloc/memcpy/free
631 } else { // Not using jemalloc
632 size_t copySlack = capacity() - length_;
633 if (copySlack * 2 <= length_) {
634 void* p = realloc(buf_, newAllocatedCapacity);
635 if (UNLIKELY(p == nullptr)) {
636 throw std::bad_alloc();
638 newBuffer = static_cast<uint8_t*>(p);
639 newHeadroom = oldHeadroom;
644 // None of the previous reallocation strategies worked (or we're using
645 // an internal buffer). malloc/copy/free.
646 if (newBuffer == nullptr) {
647 void* p = malloc(newAllocatedCapacity);
648 if (UNLIKELY(p == nullptr)) {
649 throw std::bad_alloc();
651 newBuffer = static_cast<uint8_t*>(p);
652 memcpy(newBuffer + minHeadroom, data_, length_);
653 if ((flags_ & kFlagUserOwned) == 0) {
656 newHeadroom = minHeadroom;
661 initExtBuffer(newBuffer, newAllocatedCapacity, &info, &cap);
663 if (flags_ & kFlagFreeSharedInfo) {
669 type_ = kExtAllocated;
672 data_ = newBuffer + newHeadroom;
673 // length_ is unchanged
676 void IOBuf::freeExtBuffer() {
677 DCHECK((flags_ & kFlagUserOwned) == 0);
679 if (sharedInfo_->freeFn) {
681 sharedInfo_->freeFn(buf_, sharedInfo_->userData);
683 // The user's free function should never throw. Otherwise we might
684 // throw from the IOBuf destructor. Other code paths like coalesce()
685 // also assume that decrementRefcount() cannot throw.
693 void IOBuf::allocExtBuffer(uint32_t minCapacity,
695 SharedInfo** infoReturn,
696 uint32_t* capacityReturn) {
697 size_t mallocSize = goodExtBufferSize(minCapacity);
698 uint8_t* buf = static_cast<uint8_t*>(malloc(mallocSize));
699 if (UNLIKELY(buf == NULL)) {
700 throw std::bad_alloc();
702 initExtBuffer(buf, mallocSize, infoReturn, capacityReturn);
706 size_t IOBuf::goodExtBufferSize(uint32_t minCapacity) {
707 // Determine how much space we should allocate. We'll store the SharedInfo
708 // for the external buffer just after the buffer itself. (We store it just
709 // after the buffer rather than just before so that the code can still just
710 // use free(buf_) to free the buffer.)
711 size_t minSize = static_cast<size_t>(minCapacity) + sizeof(SharedInfo);
712 // Add room for padding so that the SharedInfo will be aligned on an 8-byte
714 minSize = (minSize + 7) & ~7;
716 // Use goodMallocSize() to bump up the capacity to a decent size to request
717 // from malloc, so we can use all of the space that malloc will probably give
719 return goodMallocSize(minSize);
722 void IOBuf::initExtBuffer(uint8_t* buf, size_t mallocSize,
723 SharedInfo** infoReturn,
724 uint32_t* capacityReturn) {
725 // Find the SharedInfo storage at the end of the buffer
726 // and construct the SharedInfo.
727 uint8_t* infoStart = (buf + mallocSize) - sizeof(SharedInfo);
728 SharedInfo* sharedInfo = new(infoStart) SharedInfo;
730 size_t actualCapacity = infoStart - buf;
731 // On the unlikely possibility that the actual capacity is larger than can
732 // fit in a uint32_t after adding room for the refcount and calling
733 // goodMallocSize(), truncate downwards if necessary.
734 if (actualCapacity >= UINT32_MAX) {
735 *capacityReturn = UINT32_MAX;
737 *capacityReturn = actualCapacity;
740 *infoReturn = sharedInfo;
743 fbstring IOBuf::moveToFbString() {
744 // malloc-allocated buffers are just fine, everything else needs
745 // to be turned into one.
746 if ((flags_ & kFlagUserOwned) || // user owned, not ours to give up
747 sharedInfo_->freeFn != nullptr || // not malloc()-ed
748 headroom() != 0 || // malloc()-ed block doesn't start at beginning
749 tailroom() == 0 || // no room for NUL terminator
750 isShared() || // shared
751 isChained()) { // chained
752 // We might as well get rid of all head and tailroom if we're going
753 // to reallocate; we need 1 byte for NUL terminator.
754 coalesceAndReallocate(0, computeChainDataLength(), this, 1);
757 // Ensure NUL terminated
759 fbstring str(reinterpret_cast<char*>(writableData()),
760 length(), capacity(),
761 AcquireMallocatedString());
763 if (flags_ & kFlagFreeSharedInfo) {
767 // Reset to a state where we can be deleted cleanly
768 flags_ = kFlagUserOwned;
769 sharedInfo_ = nullptr;
775 IOBuf::Iterator IOBuf::cbegin() const {
776 return Iterator(this, this);
779 IOBuf::Iterator IOBuf::cend() const {
780 return Iterator(nullptr, nullptr);
783 folly::fbvector<struct iovec> IOBuf::getIov() const {
784 folly::fbvector<struct iovec> iov;
785 iov.reserve(countChainElements());
786 IOBuf const* p = this;
788 // some code can get confused by empty iovs, so skip them
789 if (p->length() > 0) {
790 iov.push_back({(void*)p->data(), p->length()});