2 * Copyright 2017 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.
23 #include <type_traits>
26 #include <folly/Bits.h>
27 #include <folly/Likely.h>
28 #include <folly/Memory.h>
29 #include <folly/Portability.h>
30 #include <folly/Range.h>
31 #include <folly/io/IOBuf.h>
32 #include <folly/io/IOBufQueue.h>
33 #include <folly/portability/BitsFunctexcept.h>
36 * Cursor class for fast iteration over IOBuf chains.
38 * Cursor - Read-only access
40 * RWPrivateCursor - Read-write access, assumes private access to IOBuf chain
41 * RWUnshareCursor - Read-write access, calls unshare on write (COW)
42 * Appender - Write access, assumes private access to IOBuf chian
44 * Note that RW cursors write in the preallocated part of buffers (that is,
45 * between the buffer's data() and tail()), while Appenders append to the end
46 * of the buffer (between the buffer's tail() and bufferEnd()). Appenders
47 * automatically adjust the buffer pointers, so you may only use one
48 * Appender with a buffer chain; for this reason, Appenders assume private
49 * access to the buffer (you need to call unshare() yourself if necessary).
51 namespace folly { namespace io {
55 template <class Derived, class BufType>
57 // Make all the templated classes friends for copy constructor.
58 template <class D, typename B> friend class CursorBase;
60 explicit CursorBase(BufType* buf) : crtBuf_(buf), buffer_(buf) { }
65 * This also allows constructing a CursorBase from other derived types.
66 * For instance, this allows constructing a Cursor from an RWPrivateCursor.
68 template <class OtherDerived, class OtherBuf>
69 explicit CursorBase(const CursorBase<OtherDerived, OtherBuf>& cursor)
70 : crtBuf_(cursor.crtBuf_),
71 offset_(cursor.offset_),
72 buffer_(cursor.buffer_) { }
75 * Reset cursor to point to a new buffer.
77 void reset(BufType* buf) {
83 const uint8_t* data() const {
84 return crtBuf_->data() + offset_;
88 * Return the remaining space available in the current IOBuf.
90 * May return 0 if the cursor is at the end of an IOBuf. Use peekBytes()
91 * instead if you want to avoid this. peekBytes() will advance to the next
92 * non-empty IOBuf (up to the end of the chain) if the cursor is currently
93 * pointing at the end of a buffer.
95 size_t length() const {
96 return crtBuf_->length() - offset_;
100 * Return the space available until the end of the entire IOBuf chain.
102 size_t totalLength() const {
103 if (crtBuf_ == buffer_) {
104 return crtBuf_->computeChainDataLength() - offset_;
106 CursorBase end(buffer_->prev());
107 end.offset_ = end.buffer_->length();
112 * Return true if the cursor could advance the specified number of bytes
113 * from its current position.
114 * This is useful for applications that want to do checked reads instead of
115 * catching exceptions and is more efficient than using totalLength as it
116 * walks the minimal set of buffers in the chain to determine the result.
118 bool canAdvance(size_t amount) const {
119 const IOBuf* nextBuf = crtBuf_;
120 size_t available = length();
122 if (available >= amount) {
126 nextBuf = nextBuf->next();
127 available = nextBuf->length();
128 } while (nextBuf != buffer_);
133 * Return true if the cursor is at the end of the entire IOBuf chain.
135 bool isAtEnd() const {
136 // Check for the simple cases first.
137 if (offset_ != crtBuf_->length()) {
140 if (crtBuf_ == buffer_->prev()) {
143 // We are at the end of a buffer, but it isn't the last buffer.
144 // We might still be at the end if the remaining buffers in the chain are
146 const IOBuf* buf = crtBuf_->next();;
147 while (buf != buffer_) {
148 if (buf->length() > 0) {
157 * Advances the cursor to the end of the entire IOBuf chain.
159 void advanceToEnd() {
160 offset_ = buffer_->prev()->length();
161 if (crtBuf_ != buffer_->prev()) {
162 crtBuf_ = buffer_->prev();
163 static_cast<Derived*>(this)->advanceDone();
167 Derived& operator+=(size_t offset) {
168 Derived* p = static_cast<Derived*>(this);
172 Derived operator+(size_t offset) const {
173 Derived other(*this);
178 Derived& operator-=(size_t offset) {
179 Derived* p = static_cast<Derived*>(this);
183 Derived operator-(size_t offset) const {
184 Derived other(*this);
185 other.retreat(offset);
190 * Compare cursors for equality/inequality.
192 * Two cursors are equal if they are pointing to the same location in the
195 bool operator==(const Derived& other) const {
196 return (offset_ == other.offset_) && (crtBuf_ == other.crtBuf_);
198 bool operator!=(const Derived& other) const {
199 return !operator==(other);
203 typename std::enable_if<std::is_arithmetic<T>::value, bool>::type tryRead(
205 if (LIKELY(length() >= sizeof(T))) {
206 val = loadUnaligned<T>(data());
207 offset_ += sizeof(T);
208 advanceBufferIfEmpty();
211 return pullAtMostSlow(&val, sizeof(T)) == sizeof(T);
215 bool tryReadBE(T& val) {
216 const bool result = tryRead(val);
217 val = Endian::big(val);
222 bool tryReadLE(T& val) {
223 const bool result = tryRead(val);
224 val = Endian::little(val);
232 std::__throw_out_of_range("underflow");
239 return Endian::big(read<T>());
244 return Endian::little(read<T>());
248 * Read a fixed-length string.
250 * The std::string-based APIs should probably be avoided unless you
251 * ultimately want the data to live in an std::string. You're better off
252 * using the pull() APIs to copy into a raw buffer otherwise.
254 std::string readFixedString(size_t len) {
257 if (LIKELY(length() >= len)) {
258 str.append(reinterpret_cast<const char*>(data()), len);
260 advanceBufferIfEmpty();
262 readFixedStringSlow(&str, len);
268 * Read a string consisting of bytes until the given terminator character is
269 * seen. Raises an std::length_error if maxLength bytes have been processed
270 * before the terminator is seen.
272 * See comments in readFixedString() about when it's appropriate to use this
275 std::string readTerminatedString(
276 char termChar = '\0',
277 size_t maxLength = std::numeric_limits<size_t>::max());
280 * Read all bytes until the specified predicate returns true.
282 * The predicate will be called on each byte in turn, until it returns false
283 * or until the end of the IOBuf chain is reached.
285 * Returns the result as a string.
287 template <typename Predicate>
288 std::string readWhile(const Predicate& predicate);
291 * Read all bytes until the specified predicate returns true.
293 * This is a more generic version of readWhile() takes an arbitrary Output
294 * object, and calls Output::append() with each chunk of matching data.
296 template <typename Predicate, typename Output>
297 void readWhile(const Predicate& predicate, Output& out);
300 * Skip all bytes until the specified predicate returns true.
302 * The predicate will be called on each byte in turn, until it returns false
303 * or until the end of the IOBuf chain is reached.
305 template <typename Predicate>
306 void skipWhile(const Predicate& predicate);
308 size_t skipAtMost(size_t len) {
309 if (LIKELY(length() >= len)) {
311 advanceBufferIfEmpty();
314 return skipAtMostSlow(len);
317 void skip(size_t len) {
318 if (LIKELY(length() >= len)) {
320 advanceBufferIfEmpty();
326 size_t retreatAtMost(size_t len) {
327 if (len <= offset_) {
331 return retreatAtMostSlow(len);
334 void retreat(size_t len) {
335 if (len <= offset_) {
342 size_t pullAtMost(void* buf, size_t len) {
343 // Fast path: it all fits in one buffer.
344 if (LIKELY(length() >= len)) {
345 memcpy(buf, data(), len);
347 advanceBufferIfEmpty();
350 return pullAtMostSlow(buf, len);
353 void pull(void* buf, size_t len) {
354 if (LIKELY(length() >= len)) {
355 memcpy(buf, data(), len);
357 advanceBufferIfEmpty();
364 * Return the available data in the current buffer.
365 * If you want to gather more data from the chain into a contiguous region
366 * (for hopefully zero-copy access), use gather() before peekBytes().
368 ByteRange peekBytes() {
369 // Ensure that we're pointing to valid data
370 size_t available = length();
371 while (UNLIKELY(available == 0 && tryAdvanceBuffer())) {
372 available = length();
374 return ByteRange{data(), available};
378 * Alternate version of peekBytes() that returns a std::pair
379 * instead of a ByteRange. (This method pre-dates ByteRange.)
381 * This function will eventually be deprecated.
383 std::pair<const uint8_t*, size_t> peek() {
384 auto bytes = peekBytes();
385 return std::make_pair(bytes.data(), bytes.size());
388 void clone(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
389 if (UNLIKELY(cloneAtMost(buf, len) != len)) {
390 std::__throw_out_of_range("underflow");
394 void clone(folly::IOBuf& buf, size_t len) {
395 if (UNLIKELY(cloneAtMost(buf, len) != len)) {
396 std::__throw_out_of_range("underflow");
400 size_t cloneAtMost(folly::IOBuf& buf, size_t len) {
401 std::unique_ptr<folly::IOBuf> tmp;
403 for (int loopCount = 0; true; ++loopCount) {
404 // Fast path: it all fits in one buffer.
405 size_t available = length();
406 if (LIKELY(available >= len)) {
407 if (loopCount == 0) {
408 crtBuf_->cloneOneInto(buf);
409 buf.trimStart(offset_);
410 buf.trimEnd(buf.length() - len);
412 tmp = crtBuf_->cloneOne();
413 tmp->trimStart(offset_);
414 tmp->trimEnd(tmp->length() - len);
415 buf.prependChain(std::move(tmp));
419 advanceBufferIfEmpty();
423 if (loopCount == 0) {
424 crtBuf_->cloneOneInto(buf);
425 buf.trimStart(offset_);
427 tmp = crtBuf_->cloneOne();
428 tmp->trimStart(offset_);
429 buf.prependChain(std::move(tmp));
433 if (UNLIKELY(!tryAdvanceBuffer())) {
440 size_t cloneAtMost(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
442 buf = std::make_unique<folly::IOBuf>();
444 return cloneAtMost(*buf, len);
448 * Return the distance between two cursors.
450 size_t operator-(const CursorBase& other) const {
451 BufType *otherBuf = other.crtBuf_;
454 if (otherBuf != crtBuf_) {
455 len += otherBuf->length() - other.offset_;
457 for (otherBuf = otherBuf->next();
458 otherBuf != crtBuf_ && otherBuf != other.buffer_;
459 otherBuf = otherBuf->next()) {
460 len += otherBuf->length();
463 if (otherBuf == other.buffer_) {
464 std::__throw_out_of_range("wrap-around");
469 if (offset_ < other.offset_) {
470 std::__throw_out_of_range("underflow");
473 len += offset_ - other.offset_;
480 * Return the distance from the given IOBuf to the this cursor.
482 size_t operator-(const BufType* buf) const {
485 const BufType* curBuf = buf;
486 while (curBuf != crtBuf_) {
487 len += curBuf->length();
488 curBuf = curBuf->next();
489 if (curBuf == buf || curBuf == buffer_) {
490 std::__throw_out_of_range("wrap-around");
505 bool tryAdvanceBuffer() {
506 BufType* nextBuf = crtBuf_->next();
507 if (UNLIKELY(nextBuf == buffer_)) {
508 offset_ = crtBuf_->length();
514 static_cast<Derived*>(this)->advanceDone();
518 bool tryRetreatBuffer() {
519 if (UNLIKELY(crtBuf_ == buffer_)) {
523 crtBuf_ = crtBuf_->prev();
524 offset_ = crtBuf_->length();
525 static_cast<Derived*>(this)->advanceDone();
529 void advanceBufferIfEmpty() {
539 void readFixedStringSlow(std::string* str, size_t len) {
540 for (size_t available; (available = length()) < len; ) {
541 str->append(reinterpret_cast<const char*>(data()), available);
542 if (UNLIKELY(!tryAdvanceBuffer())) {
543 std::__throw_out_of_range("string underflow");
547 str->append(reinterpret_cast<const char*>(data()), len);
549 advanceBufferIfEmpty();
552 size_t pullAtMostSlow(void* buf, size_t len) {
553 uint8_t* p = reinterpret_cast<uint8_t*>(buf);
555 for (size_t available; (available = length()) < len; ) {
556 memcpy(p, data(), available);
558 if (UNLIKELY(!tryAdvanceBuffer())) {
564 memcpy(p, data(), len);
566 advanceBufferIfEmpty();
570 void pullSlow(void* buf, size_t len) {
571 if (UNLIKELY(pullAtMostSlow(buf, len) != len)) {
572 std::__throw_out_of_range("underflow");
576 size_t skipAtMostSlow(size_t len) {
578 for (size_t available; (available = length()) < len; ) {
579 skipped += available;
580 if (UNLIKELY(!tryAdvanceBuffer())) {
586 advanceBufferIfEmpty();
587 return skipped + len;
590 void skipSlow(size_t len) {
591 if (UNLIKELY(skipAtMostSlow(len) != len)) {
592 std::__throw_out_of_range("underflow");
596 size_t retreatAtMostSlow(size_t len) {
597 size_t retreated = 0;
598 for (size_t available; (available = offset_) < len;) {
599 retreated += available;
600 if (UNLIKELY(!tryRetreatBuffer())) {
606 return retreated + len;
609 void retreatSlow(size_t len) {
610 if (UNLIKELY(retreatAtMostSlow(len) != len)) {
611 std::__throw_out_of_range("underflow");
621 } // namespace detail
623 class Cursor : public detail::CursorBase<Cursor, const IOBuf> {
625 explicit Cursor(const IOBuf* buf)
626 : detail::CursorBase<Cursor, const IOBuf>(buf) {}
628 template <class OtherDerived, class OtherBuf>
629 explicit Cursor(const detail::CursorBase<OtherDerived, OtherBuf>& cursor)
630 : detail::CursorBase<Cursor, const IOBuf>(cursor) {}
635 template <class Derived>
639 typename std::enable_if<std::is_arithmetic<T>::value>::type
641 const uint8_t* u8 = reinterpret_cast<const uint8_t*>(&value);
642 Derived* d = static_cast<Derived*>(this);
643 d->push(u8, sizeof(T));
647 void writeBE(T value) {
648 Derived* d = static_cast<Derived*>(this);
649 d->write(Endian::big(value));
653 void writeLE(T value) {
654 Derived* d = static_cast<Derived*>(this);
655 d->write(Endian::little(value));
658 void push(const uint8_t* buf, size_t len) {
659 Derived* d = static_cast<Derived*>(this);
660 if (d->pushAtMost(buf, len) != len) {
661 std::__throw_out_of_range("overflow");
665 void push(ByteRange buf) {
666 if (this->pushAtMost(buf) != buf.size()) {
667 std::__throw_out_of_range("overflow");
671 size_t pushAtMost(ByteRange buf) {
672 Derived* d = static_cast<Derived*>(this);
673 return d->pushAtMost(buf.data(), buf.size());
677 * push len bytes of data from input cursor, data could be in an IOBuf chain.
678 * If input cursor contains less than len bytes, or this cursor has less than
679 * len bytes writable space, an out_of_range exception will be thrown.
681 void push(Cursor cursor, size_t len) {
682 if (this->pushAtMost(cursor, len) != len) {
683 std::__throw_out_of_range("overflow");
687 size_t pushAtMost(Cursor cursor, size_t len) {
690 auto currentBuffer = cursor.peekBytes();
691 const uint8_t* crtData = currentBuffer.data();
692 size_t available = currentBuffer.size();
693 if (available == 0) {
694 // end of buffer chain
697 // all data is in current buffer
698 if (available >= len) {
699 this->push(crtData, len);
701 return written + len;
704 // write the whole current IOBuf
705 this->push(crtData, available);
706 cursor.skip(available);
707 written += available;
713 } // namespace detail
715 enum class CursorAccess {
720 template <CursorAccess access>
722 : public detail::CursorBase<RWCursor<access>, IOBuf>,
723 public detail::Writable<RWCursor<access>> {
724 friend class detail::CursorBase<RWCursor<access>, IOBuf>;
726 explicit RWCursor(IOBuf* buf)
727 : detail::CursorBase<RWCursor<access>, IOBuf>(buf),
728 maybeShared_(true) {}
730 template <class OtherDerived, class OtherBuf>
731 explicit RWCursor(const detail::CursorBase<OtherDerived, OtherBuf>& cursor)
732 : detail::CursorBase<RWCursor<access>, IOBuf>(cursor),
733 maybeShared_(true) {}
735 * Gather at least n bytes contiguously into the current buffer,
736 * by coalescing subsequent buffers from the chain as necessary.
738 void gather(size_t n) {
739 // Forbid attempts to gather beyond the end of this IOBuf chain.
740 // Otherwise we could try to coalesce the head of the chain and end up
741 // accidentally freeing it, invalidating the pointer owned by external
744 // If crtBuf_ == head() then IOBuf::gather() will perform all necessary
745 // checking. We only have to perform an explicit check here when calling
746 // gather() on a non-head element.
747 if (this->crtBuf_ != this->head() && this->totalLength() < n) {
748 throw std::overflow_error("cannot gather() past the end of the chain");
750 this->crtBuf_->gather(this->offset_ + n);
752 void gatherAtMost(size_t n) {
753 size_t size = std::min(n, this->totalLength());
754 return this->crtBuf_->gather(this->offset_ + size);
757 using detail::Writable<RWCursor<access>>::pushAtMost;
758 size_t pushAtMost(const uint8_t* buf, size_t len) {
761 // Fast path: the current buffer is big enough.
762 size_t available = this->length();
763 if (LIKELY(available >= len)) {
764 if (access == CursorAccess::UNSHARE) {
767 memcpy(writableData(), buf, len);
768 this->offset_ += len;
772 if (access == CursorAccess::UNSHARE) {
775 memcpy(writableData(), buf, available);
777 if (UNLIKELY(!this->tryAdvanceBuffer())) {
785 void insert(std::unique_ptr<folly::IOBuf> buf) {
786 folly::IOBuf* nextBuf;
787 if (this->offset_ == 0) {
789 nextBuf = this->crtBuf_;
790 this->crtBuf_->prependChain(std::move(buf));
792 std::unique_ptr<folly::IOBuf> remaining;
793 if (this->crtBuf_->length() - this->offset_ > 0) {
794 // Need to split current IOBuf in two.
795 remaining = this->crtBuf_->cloneOne();
796 remaining->trimStart(this->offset_);
797 nextBuf = remaining.get();
798 buf->prependChain(std::move(remaining));
801 nextBuf = this->crtBuf_->next();
803 this->crtBuf_->trimEnd(this->length());
804 this->crtBuf_->appendChain(std::move(buf));
806 // Jump past the new links
808 this->crtBuf_ = nextBuf;
811 uint8_t* writableData() {
812 return this->crtBuf_->writableData() + this->offset_;
816 void maybeUnshare() {
817 if (UNLIKELY(maybeShared_)) {
818 this->crtBuf_->unshareOne();
819 maybeShared_ = false;
830 typedef RWCursor<CursorAccess::PRIVATE> RWPrivateCursor;
831 typedef RWCursor<CursorAccess::UNSHARE> RWUnshareCursor;
834 * Append to the end of a buffer chain, growing the chain (by allocating new
835 * buffers) in increments of at least growth bytes every time. Won't grow
836 * (and push() and ensure() will throw) if growth == 0.
838 * TODO(tudorb): add a flavor of Appender that reallocates one IOBuf instead
841 class Appender : public detail::Writable<Appender> {
843 Appender(IOBuf* buf, uint64_t growth)
845 crtBuf_(buf->prev()),
849 uint8_t* writableData() {
850 return crtBuf_->writableTail();
853 size_t length() const {
854 return crtBuf_->tailroom();
858 * Mark n bytes (must be <= length()) as appended, as per the
859 * IOBuf::append() method.
861 void append(size_t n) {
866 * Ensure at least n contiguous bytes available to write.
867 * Postcondition: length() >= n.
869 void ensure(uint64_t n) {
870 if (LIKELY(length() >= n)) {
874 // Waste the rest of the current buffer and allocate a new one.
875 // Don't make it too small, either.
877 std::__throw_out_of_range("can't grow buffer chain");
880 n = std::max(n, growth_);
881 buffer_->prependChain(IOBuf::create(n));
882 crtBuf_ = buffer_->prev();
885 using detail::Writable<Appender>::pushAtMost;
886 size_t pushAtMost(const uint8_t* buf, size_t len) {
889 // Fast path: it all fits in one buffer.
890 size_t available = length();
891 if (LIKELY(available >= len)) {
892 memcpy(writableData(), buf, len);
897 memcpy(writableData(), buf, available);
900 if (UNLIKELY(!tryGrowChain())) {
909 * Append to the end of this buffer, using a printf() style
912 * Note that folly/Format.h provides nicer and more type-safe mechanisms
913 * for formatting strings, which should generally be preferred over
914 * printf-style formatting. Appender objects can be used directly as an
915 * output argument for Formatter objects. For example:
917 * Appender app(&iobuf);
918 * format("{} {}", "hello", "world")(app);
920 * However, printf-style strings are still needed when dealing with existing
921 * third-party code in some cases.
923 * This will always add a nul-terminating character after the end
924 * of the output. However, the buffer data length will only be updated to
925 * include the data itself. The nul terminator will be the first byte in the
928 * This method may throw exceptions on error.
930 void printf(FOLLY_PRINTF_FORMAT const char* fmt, ...)
931 FOLLY_PRINTF_FORMAT_ATTR(2, 3);
933 void vprintf(const char* fmt, va_list ap);
936 * Calling an Appender object with a StringPiece will append the string
937 * piece. This allows Appender objects to be used directly with
940 void operator()(StringPiece sp) {
945 bool tryGrowChain() {
946 assert(crtBuf_->next() == buffer_);
951 buffer_->prependChain(IOBuf::create(growth_));
952 crtBuf_ = buffer_->prev();
961 class QueueAppender : public detail::Writable<QueueAppender> {
964 * Create an Appender that writes to a IOBufQueue. When we allocate
965 * space in the queue, we grow no more than growth bytes at once
966 * (unless you call ensure() with a bigger value yourself).
968 QueueAppender(IOBufQueue* queue, uint64_t growth) {
969 reset(queue, growth);
972 void reset(IOBufQueue* queue, uint64_t growth) {
977 uint8_t* writableData() {
978 return static_cast<uint8_t*>(queue_->writableTail());
981 size_t length() const { return queue_->tailroom(); }
983 void append(size_t n) { queue_->postallocate(n); }
985 // Ensure at least n contiguous; can go above growth_, throws if
987 void ensure(uint64_t n) { queue_->preallocate(n, growth_); }
990 typename std::enable_if<std::is_arithmetic<T>::value>::type
993 auto p = queue_->preallocate(sizeof(T), growth_);
994 storeUnaligned(p.first, value);
995 queue_->postallocate(sizeof(T));
998 using detail::Writable<QueueAppender>::pushAtMost;
999 size_t pushAtMost(const uint8_t* buf, size_t len) {
1000 // Fill the current buffer
1001 const size_t copyLength = std::min(len, length());
1002 if (copyLength != 0) {
1003 memcpy(writableData(), buf, copyLength);
1007 // Allocate more buffers as necessary
1008 size_t remaining = len - copyLength;
1009 while (remaining != 0) {
1010 auto p = queue_->preallocate(std::min(remaining, growth_),
1013 memcpy(p.first, buf, p.second);
1014 queue_->postallocate(p.second);
1016 remaining -= p.second;
1022 void insert(std::unique_ptr<folly::IOBuf> buf) {
1024 queue_->append(std::move(buf), true);
1028 void insert(const folly::IOBuf& buf) {
1029 insert(buf.clone());
1033 folly::IOBufQueue* queue_;
1039 #include <folly/io/Cursor-inl.h>