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;
33 const uint32_t IOBuf::kMaxIOBufSize;
34 // Note: Applying offsetof() to an IOBuf is legal according to C++11, since
35 // IOBuf is a standard-layout class. However, this isn't legal with earlier
36 // C++ standards, which require that offsetof() only be used with POD types.
38 // This code compiles with g++ 4.6, but not with g++ 4.4 or earlier versions.
39 const uint32_t IOBuf::kMaxInternalDataSize =
40 kMaxIOBufSize - offsetof(folly::IOBuf, int_.buf);
42 IOBuf::SharedInfo::SharedInfo()
45 // Use relaxed memory ordering here. Since we are creating a new SharedInfo,
46 // no other threads should be referring to it yet.
47 refcount.store(1, std::memory_order_relaxed);
50 IOBuf::SharedInfo::SharedInfo(FreeFunction fn, void* arg)
53 // Use relaxed memory ordering here. Since we are creating a new SharedInfo,
54 // no other threads should be referring to it yet.
55 refcount.store(1, std::memory_order_relaxed);
58 void* IOBuf::operator new(size_t size) {
59 // Since IOBuf::create() manually allocates space for some IOBuf objects
60 // using malloc(), override operator new so that all IOBuf objects are
61 // always allocated using malloc(). This way operator delete can always know
62 // that free() is the correct way to deallocate the memory.
63 void* ptr = malloc(size);
65 // operator new is not allowed to return NULL
66 if (UNLIKELY(ptr == NULL)) {
67 throw std::bad_alloc();
73 void* IOBuf::operator new(size_t size, void* ptr) {
74 assert(size <= kMaxIOBufSize);
78 void IOBuf::operator delete(void* ptr) {
79 // For small buffers, IOBuf::create() manually allocates the space for the
80 // IOBuf object using malloc(). Therefore we override delete to ensure that
81 // the IOBuf space is freed using free() rather than a normal delete.
85 unique_ptr<IOBuf> IOBuf::create(uint32_t capacity) {
86 // If the desired capacity is less than kMaxInternalDataSize,
87 // just allocate a single region large enough for both the IOBuf header and
89 if (capacity <= kMaxInternalDataSize) {
90 void* buf = malloc(kMaxIOBufSize);
91 if (UNLIKELY(buf == NULL)) {
92 throw std::bad_alloc();
95 uint8_t* bufEnd = static_cast<uint8_t*>(buf) + kMaxIOBufSize;
96 unique_ptr<IOBuf> iobuf(new(buf) IOBuf(bufEnd));
97 assert(iobuf->capacity() >= capacity);
101 // Allocate an external buffer
103 SharedInfo* sharedInfo;
104 uint32_t actualCapacity;
105 allocExtBuffer(capacity, &buf, &sharedInfo, &actualCapacity);
107 // Allocate the IOBuf header
109 return unique_ptr<IOBuf>(new IOBuf(kExtAllocated, 0,
119 unique_ptr<IOBuf> IOBuf::createChain(
120 size_t totalCapacity, uint32_t maxBufCapacity) {
121 unique_ptr<IOBuf> out = create(
122 std::min(totalCapacity, size_t(maxBufCapacity)));
123 size_t allocatedCapacity = out->capacity();
125 while (allocatedCapacity < totalCapacity) {
126 unique_ptr<IOBuf> newBuf = create(
127 std::min(totalCapacity - allocatedCapacity, size_t(maxBufCapacity)));
128 allocatedCapacity += newBuf->capacity();
129 out->prependChain(std::move(newBuf));
135 unique_ptr<IOBuf> IOBuf::takeOwnership(void* buf, uint32_t capacity,
140 SharedInfo* sharedInfo = NULL;
142 sharedInfo = new SharedInfo(freeFn, userData);
144 uint8_t* bufPtr = static_cast<uint8_t*>(buf);
145 return unique_ptr<IOBuf>(new IOBuf(kExtUserSupplied, kFlagFreeSharedInfo,
154 freeFn(buf, userData);
156 // The user's free function is not allowed to throw.
167 unique_ptr<IOBuf> IOBuf::wrapBuffer(const void* buf, uint32_t capacity) {
168 // We cast away the const-ness of the buffer here.
169 // This is okay since IOBuf users must use unshare() to create a copy of
170 // this buffer before writing to the buffer.
171 uint8_t* bufPtr = static_cast<uint8_t*>(const_cast<void*>(buf));
172 return unique_ptr<IOBuf>(new IOBuf(kExtUserSupplied, kFlagUserOwned,
178 IOBuf::IOBuf(uint8_t* end)
184 assert(end - int_.buf == kMaxInternalDataSize);
185 assert(end - reinterpret_cast<uint8_t*>(this) == kMaxIOBufSize);
188 IOBuf::IOBuf(ExtBufTypeEnum type,
194 SharedInfo* sharedInfo)
199 flags_(kFlagExt | flags) {
200 ext_.capacity = capacity;
203 ext_.sharedInfo = sharedInfo;
206 assert(data + length <= buf + capacity);
207 assert(static_cast<bool>(flags & kFlagUserOwned) ==
208 (sharedInfo == NULL));
212 // Destroying an IOBuf destroys the entire chain.
213 // Users of IOBuf should only explicitly delete the head of any chain.
214 // The other elements in the chain will be automatically destroyed.
215 while (next_ != this) {
216 // Since unlink() returns unique_ptr() and we don't store it,
217 // it will automatically delete the unlinked element.
218 (void)next_->unlink();
221 if (flags_ & kFlagExt) {
226 bool IOBuf::empty() const {
227 const IOBuf* current = this;
229 if (current->length() != 0) {
232 current = current->next_;
233 } while (current != this);
237 uint32_t IOBuf::countChainElements() const {
238 uint32_t numElements = 1;
239 for (IOBuf* current = next_; current != this; current = current->next_) {
245 uint64_t IOBuf::computeChainDataLength() const {
246 uint64_t fullLength = length_;
247 for (IOBuf* current = next_; current != this; current = current->next_) {
248 fullLength += current->length_;
253 void IOBuf::prependChain(unique_ptr<IOBuf>&& iobuf) {
254 // Take ownership of the specified IOBuf
255 IOBuf* other = iobuf.release();
257 // Remember the pointer to the tail of the other chain
258 IOBuf* otherTail = other->prev_;
260 // Hook up prev_->next_ to point at the start of the other chain,
261 // and other->prev_ to point at prev_
262 prev_->next_ = other;
263 other->prev_ = prev_;
265 // Hook up otherTail->next_ to point at us,
266 // and prev_ to point back at otherTail,
267 otherTail->next_ = this;
271 unique_ptr<IOBuf> IOBuf::clone() const {
272 unique_ptr<IOBuf> newHead(cloneOne());
274 for (IOBuf* current = next_; current != this; current = current->next_) {
275 newHead->prependChain(current->cloneOne());
281 unique_ptr<IOBuf> IOBuf::cloneOne() const {
282 if (flags_ & kFlagExt) {
283 if (ext_.sharedInfo) {
284 flags_ |= kFlagMaybeShared;
286 unique_ptr<IOBuf> iobuf(new IOBuf(static_cast<ExtBufTypeEnum>(ext_.type),
287 flags_, ext_.buf, ext_.capacity,
290 if (ext_.sharedInfo) {
291 ext_.sharedInfo->refcount.fetch_add(1, std::memory_order_acq_rel);
295 // We have an internal data buffer that cannot be shared
296 // Allocate a new IOBuf and copy the data into it.
297 unique_ptr<IOBuf> iobuf(IOBuf::create(kMaxInternalDataSize));
298 assert((iobuf->flags_ & kFlagExt) == 0);
299 iobuf->data_ += headroom();
300 memcpy(iobuf->data_, data_, length_);
301 iobuf->length_ = length_;
306 void IOBuf::unshareOneSlow() {
307 // Internal buffers are always unshared, so unshareOneSlow() can only be
308 // called for external buffers
309 assert(flags_ & kFlagExt);
311 // Allocate a new buffer for the data
313 SharedInfo* sharedInfo;
314 uint32_t actualCapacity;
315 allocExtBuffer(ext_.capacity, &buf, &sharedInfo, &actualCapacity);
318 // Maintain the same amount of headroom. Since we maintained the same
319 // minimum capacity we also maintain at least the same amount of tailroom.
320 uint32_t headlen = headroom();
321 memcpy(buf + headlen, data_, length_);
323 // Release our reference on the old buffer
325 // Make sure kFlagExt is set, and kFlagUserOwned and kFlagFreeSharedInfo
329 // Update the buffer pointers to point to the new buffer
330 data_ = buf + headlen;
332 ext_.sharedInfo = sharedInfo;
335 void IOBuf::unshareChained() {
336 // unshareChained() should only be called if we are part of a chain of
337 // multiple IOBufs. The caller should have already verified this.
340 IOBuf* current = this;
342 if (current->isSharedOne()) {
343 // we have to unshare
347 current = current->next_;
348 if (current == this) {
349 // None of the IOBufs in the chain are shared,
350 // so return without doing anything
355 // We have to unshare. Let coalesceSlow() do the work.
359 void IOBuf::coalesceSlow(size_t maxLength) {
360 // coalesceSlow() should only be called if we are part of a chain of multiple
361 // IOBufs. The caller should have already verified this.
363 assert(length_ < maxLength);
365 // Compute the length of the entire chain
366 uint64_t newLength = 0;
369 newLength += end->length_;
371 } while (newLength < maxLength && end != this);
373 uint64_t newHeadroom = headroom();
374 uint64_t newTailroom = end->prev_->tailroom();
375 coalesceAndReallocate(newHeadroom, newLength, end, newTailroom);
376 // We should be only element left in the chain now
377 assert(length_ >= maxLength || !isChained());
380 void IOBuf::coalesceAndReallocate(size_t newHeadroom,
383 size_t newTailroom) {
384 uint64_t newCapacity = newLength + newHeadroom + newTailroom;
385 if (newCapacity > UINT32_MAX) {
386 throw std::overflow_error("IOBuf chain too large to coalesce");
389 // Allocate space for the coalesced buffer.
390 // We always convert to an external buffer, even if we happened to be an
391 // internal buffer before.
394 uint32_t actualCapacity;
395 allocExtBuffer(newCapacity, &newBuf, &newInfo, &actualCapacity);
397 // Copy the data into the new buffer
398 uint8_t* newData = newBuf + newHeadroom;
399 uint8_t* p = newData;
400 IOBuf* current = this;
401 size_t remaining = newLength;
403 assert(current->length_ <= remaining);
404 remaining -= current->length_;
405 memcpy(p, current->data_, current->length_);
406 p += current->length_;
407 current = current->next_;
408 } while (current != end);
409 assert(remaining == 0);
411 // Point at the new buffer
412 if (flags_ & kFlagExt) {
416 // Make sure kFlagExt is set, and kFlagUserOwned and kFlagFreeSharedInfo
420 ext_.capacity = actualCapacity;
421 ext_.type = kExtAllocated;
423 ext_.sharedInfo = newInfo;
427 // Separate from the rest of our chain.
428 // Since we don't store the unique_ptr returned by separateChain(),
429 // this will immediately delete the returned subchain.
431 (void)separateChain(next_, current->prev_);
435 void IOBuf::decrementRefcount() {
436 assert(flags_ & kFlagExt);
438 // Externally owned buffers don't have a SharedInfo object and aren't managed
439 // by the reference count
440 if (flags_ & kFlagUserOwned) {
441 assert(ext_.sharedInfo == NULL);
445 // Decrement the refcount
446 uint32_t newcnt = ext_.sharedInfo->refcount.fetch_sub(
447 1, std::memory_order_acq_rel);
448 // Note that fetch_sub() returns the value before we decremented.
449 // If it is 1, we were the only remaining user; if it is greater there are
450 // still other users.
455 // We were the last user. Free the buffer
458 // Free the SharedInfo if it was allocated separately.
460 // This is only used by takeOwnership().
462 // To avoid this special case handling in decrementRefcount(), we could have
463 // takeOwnership() set a custom freeFn() that calls the user's free function
464 // then frees the SharedInfo object. (This would require that
465 // takeOwnership() store the user's free function with its allocated
466 // SharedInfo object.) However, handling this specially with a flag seems
467 // like it shouldn't be problematic.
468 if (flags_ & kFlagFreeSharedInfo) {
469 delete ext_.sharedInfo;
473 void IOBuf::reserveSlow(uint32_t minHeadroom, uint32_t minTailroom) {
474 size_t newCapacity = (size_t)length_ + minHeadroom + minTailroom;
475 DCHECK_LT(newCapacity, UINT32_MAX);
477 // reserveSlow() is dangerous if anyone else is sharing the buffer, as we may
478 // reallocate and free the original buffer. It should only ever be called if
479 // we are the only user of the buffer.
480 DCHECK(!isSharedOne());
482 // We'll need to reallocate the buffer.
483 // There are a few options.
484 // - If we have enough total room, move the data around in the buffer
485 // and adjust the data_ pointer.
486 // - If we're using an internal buffer, we'll switch to an external
487 // buffer with enough headroom and tailroom.
488 // - If we have enough headroom (headroom() >= minHeadroom) but not too much
489 // (so we don't waste memory), we can try one of two things, depending on
490 // whether we use jemalloc or not:
491 // - If using jemalloc, we can try to expand in place, avoiding a memcpy()
492 // - If not using jemalloc and we don't have too much to copy,
493 // we'll use realloc() (note that realloc might have to copy
494 // headroom + data + tailroom, see smartRealloc in folly/Malloc.h)
495 // - Otherwise, bite the bullet and reallocate.
496 if (headroom() + tailroom() >= minHeadroom + minTailroom) {
497 uint8_t* newData = writableBuffer() + minHeadroom;
498 memmove(newData, data_, length_);
503 size_t newAllocatedCapacity = goodExtBufferSize(newCapacity);
504 uint8_t* newBuffer = nullptr;
505 uint32_t newHeadroom = 0;
506 uint32_t oldHeadroom = headroom();
508 // If we have a buffer allocated with malloc and we just need more tailroom,
509 // try to use realloc()/rallocm() to grow the buffer in place.
510 if ((flags_ & (kFlagExt | kFlagUserOwned)) == kFlagExt &&
511 (ext_.sharedInfo->freeFn == nullptr) &&
512 length_ != 0 && oldHeadroom >= minHeadroom) {
513 if (usingJEMalloc()) {
514 size_t headSlack = oldHeadroom - minHeadroom;
515 // We assume that tailroom is more useful and more important than
516 // headroom (not least because realloc / rallocm allow us to grow the
517 // buffer at the tail, but not at the head) So, if we have more headroom
518 // than we need, we consider that "wasted". We arbitrarily define "too
519 // much" headroom to be 25% of the capacity.
520 if (headSlack * 4 <= newCapacity) {
521 size_t allocatedCapacity = capacity() + sizeof(SharedInfo);
523 if (allocatedCapacity >= jemallocMinInPlaceExpandable) {
524 int r = rallocm(&p, &newAllocatedCapacity, newAllocatedCapacity,
526 if (r == ALLOCM_SUCCESS) {
527 newBuffer = static_cast<uint8_t*>(p);
528 newHeadroom = oldHeadroom;
529 } else if (r == ALLOCM_ERR_OOM) {
530 // shouldn't happen as we don't actually allocate new memory
531 // (due to ALLOCM_NO_MOVE)
532 throw std::bad_alloc();
534 // if ALLOCM_ERR_NOT_MOVED, do nothing, fall back to
535 // malloc/memcpy/free
538 } else { // Not using jemalloc
539 size_t copySlack = capacity() - length_;
540 if (copySlack * 2 <= length_) {
541 void* p = realloc(ext_.buf, newAllocatedCapacity);
542 if (UNLIKELY(p == nullptr)) {
543 throw std::bad_alloc();
545 newBuffer = static_cast<uint8_t*>(p);
546 newHeadroom = oldHeadroom;
551 // None of the previous reallocation strategies worked (or we're using
552 // an internal buffer). malloc/copy/free.
553 if (newBuffer == nullptr) {
554 void* p = malloc(newAllocatedCapacity);
555 if (UNLIKELY(p == nullptr)) {
556 throw std::bad_alloc();
558 newBuffer = static_cast<uint8_t*>(p);
559 memcpy(newBuffer + minHeadroom, data_, length_);
560 if ((flags_ & (kFlagExt | kFlagUserOwned)) == kFlagExt) {
563 newHeadroom = minHeadroom;
568 initExtBuffer(newBuffer, newAllocatedCapacity, &info, &cap);
570 if (flags_ & kFlagFreeSharedInfo) {
571 delete ext_.sharedInfo;
576 ext_.type = kExtAllocated;
577 ext_.buf = newBuffer;
578 ext_.sharedInfo = info;
579 data_ = newBuffer + newHeadroom;
580 // length_ is unchanged
583 void IOBuf::freeExtBuffer() {
584 DCHECK((flags_ & (kFlagExt | kFlagUserOwned)) == kFlagExt);
586 if (ext_.sharedInfo->freeFn) {
588 ext_.sharedInfo->freeFn(ext_.buf, ext_.sharedInfo->userData);
590 // The user's free function should never throw. Otherwise we might
591 // throw from the IOBuf destructor. Other code paths like coalesce()
592 // also assume that decrementRefcount() cannot throw.
600 void IOBuf::allocExtBuffer(uint32_t minCapacity,
602 SharedInfo** infoReturn,
603 uint32_t* capacityReturn) {
604 size_t mallocSize = goodExtBufferSize(minCapacity);
605 uint8_t* buf = static_cast<uint8_t*>(malloc(mallocSize));
606 if (UNLIKELY(buf == NULL)) {
607 throw std::bad_alloc();
609 initExtBuffer(buf, mallocSize, infoReturn, capacityReturn);
613 size_t IOBuf::goodExtBufferSize(uint32_t minCapacity) {
614 // Determine how much space we should allocate. We'll store the SharedInfo
615 // for the external buffer just after the buffer itself. (We store it just
616 // after the buffer rather than just before so that the code can still just
617 // use free(ext_.buf) to free the buffer.)
618 size_t minSize = static_cast<size_t>(minCapacity) + sizeof(SharedInfo);
619 // Add room for padding so that the SharedInfo will be aligned on an 8-byte
621 minSize = (minSize + 7) & ~7;
623 // Use goodMallocSize() to bump up the capacity to a decent size to request
624 // from malloc, so we can use all of the space that malloc will probably give
626 return goodMallocSize(minSize);
629 void IOBuf::initExtBuffer(uint8_t* buf, size_t mallocSize,
630 SharedInfo** infoReturn,
631 uint32_t* capacityReturn) {
632 // Find the SharedInfo storage at the end of the buffer
633 // and construct the SharedInfo.
634 uint8_t* infoStart = (buf + mallocSize) - sizeof(SharedInfo);
635 SharedInfo* sharedInfo = new(infoStart) SharedInfo;
637 size_t actualCapacity = infoStart - buf;
638 // On the unlikely possibility that the actual capacity is larger than can
639 // fit in a uint32_t after adding room for the refcount and calling
640 // goodMallocSize(), truncate downwards if necessary.
641 if (actualCapacity >= UINT32_MAX) {
642 *capacityReturn = UINT32_MAX;
644 *capacityReturn = actualCapacity;
647 *infoReturn = sharedInfo;
650 fbstring IOBuf::moveToFbString() {
651 // malloc-allocated buffers are just fine, everything else needs
652 // to be turned into one.
653 if ((flags_ & (kFlagExt | kFlagUserOwned)) != kFlagExt || // not malloc()-ed
654 ext_.sharedInfo->freeFn != nullptr || // not malloc()-ed
655 headroom() != 0 || // malloc()-ed block doesn't start at beginning
656 tailroom() == 0 || // no room for NUL terminator
657 isShared() || // shared
658 isChained()) { // chained
659 // We might as well get rid of all head and tailroom if we're going
660 // to reallocate; we need 1 byte for NUL terminator.
661 coalesceAndReallocate(0, computeChainDataLength(), this, 1);
664 // Ensure NUL terminated
666 fbstring str(reinterpret_cast<char*>(writableData()),
667 length(), capacity(),
668 AcquireMallocatedString());
670 if (flags_ & kFlagFreeSharedInfo) {
671 delete ext_.sharedInfo;
674 // Reset to internal buffer.
680 IOBuf::Iterator IOBuf::cbegin() const {
681 return Iterator(this, this);
684 IOBuf::Iterator IOBuf::cend() const {
685 return Iterator(nullptr, nullptr);
688 folly::fbvector<struct iovec> IOBuf::getIov() const {
689 folly::fbvector<struct iovec> iov;
690 iov.reserve(countChainElements());
691 IOBuf const* p = this;
693 // some code can get confused by empty iovs, so skip them
694 if (p->length() > 0) {
695 iov.push_back({(void*)p->data(), p->length()});