2 * Copyright 2016 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, T>::type read() {
205 if (LIKELY(length() >= sizeof(T))) {
206 val = loadUnaligned<T>(data());
207 offset_ += sizeof(T);
208 advanceBufferIfEmpty();
210 pullSlow(&val, sizeof(T));
217 return Endian::big(read<T>());
222 return Endian::little(read<T>());
226 * Read a fixed-length string.
228 * The std::string-based APIs should probably be avoided unless you
229 * ultimately want the data to live in an std::string. You're better off
230 * using the pull() APIs to copy into a raw buffer otherwise.
232 std::string readFixedString(size_t len) {
235 if (LIKELY(length() >= len)) {
236 str.append(reinterpret_cast<const char*>(data()), len);
238 advanceBufferIfEmpty();
240 readFixedStringSlow(&str, len);
246 * Read a string consisting of bytes until the given terminator character is
247 * seen. Raises an std::length_error if maxLength bytes have been processed
248 * before the terminator is seen.
250 * See comments in readFixedString() about when it's appropriate to use this
253 std::string readTerminatedString(
254 char termChar = '\0',
255 size_t maxLength = std::numeric_limits<size_t>::max());
258 * Read all bytes until the specified predicate returns true.
260 * The predicate will be called on each byte in turn, until it returns false
261 * or until the end of the IOBuf chain is reached.
263 * Returns the result as a string.
265 template <typename Predicate>
266 std::string readWhile(const Predicate& predicate);
269 * Read all bytes until the specified predicate returns true.
271 * This is a more generic version of readWhile() takes an arbitrary Output
272 * object, and calls Output::append() with each chunk of matching data.
274 template <typename Predicate, typename Output>
275 void readWhile(const Predicate& predicate, Output& out);
278 * Skip all bytes until the specified predicate returns true.
280 * The predicate will be called on each byte in turn, until it returns false
281 * or until the end of the IOBuf chain is reached.
283 template <typename Predicate>
284 void skipWhile(const Predicate& predicate);
286 size_t skipAtMost(size_t len) {
287 if (LIKELY(length() >= len)) {
289 advanceBufferIfEmpty();
292 return skipAtMostSlow(len);
295 void skip(size_t len) {
296 if (LIKELY(length() >= len)) {
298 advanceBufferIfEmpty();
304 size_t retreatAtMost(size_t len) {
305 if (len <= offset_) {
309 return retreatAtMostSlow(len);
312 void retreat(size_t len) {
313 if (len <= offset_) {
320 size_t pullAtMost(void* buf, size_t len) {
321 // Fast path: it all fits in one buffer.
322 if (LIKELY(length() >= len)) {
323 memcpy(buf, data(), len);
325 advanceBufferIfEmpty();
328 return pullAtMostSlow(buf, len);
331 void pull(void* buf, size_t len) {
332 if (LIKELY(length() >= len)) {
333 memcpy(buf, data(), len);
335 advanceBufferIfEmpty();
342 * Return the available data in the current buffer.
343 * If you want to gather more data from the chain into a contiguous region
344 * (for hopefully zero-copy access), use gather() before peekBytes().
346 ByteRange peekBytes() {
347 // Ensure that we're pointing to valid data
348 size_t available = length();
349 while (UNLIKELY(available == 0 && tryAdvanceBuffer())) {
350 available = length();
352 return ByteRange{data(), available};
356 * Alternate version of peekBytes() that returns a std::pair
357 * instead of a ByteRange. (This method pre-dates ByteRange.)
359 * This function will eventually be deprecated.
361 std::pair<const uint8_t*, size_t> peek() {
362 auto bytes = peekBytes();
363 return std::make_pair(bytes.data(), bytes.size());
366 void clone(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
367 if (UNLIKELY(cloneAtMost(buf, len) != len)) {
368 std::__throw_out_of_range("underflow");
372 void clone(folly::IOBuf& buf, size_t len) {
373 if (UNLIKELY(cloneAtMost(buf, len) != len)) {
374 std::__throw_out_of_range("underflow");
378 size_t cloneAtMost(folly::IOBuf& buf, size_t len) {
379 std::unique_ptr<folly::IOBuf> tmp;
381 for (int loopCount = 0; true; ++loopCount) {
382 // Fast path: it all fits in one buffer.
383 size_t available = length();
384 if (LIKELY(available >= len)) {
385 if (loopCount == 0) {
386 crtBuf_->cloneOneInto(buf);
387 buf.trimStart(offset_);
388 buf.trimEnd(buf.length() - len);
390 tmp = crtBuf_->cloneOne();
391 tmp->trimStart(offset_);
392 tmp->trimEnd(tmp->length() - len);
393 buf.prependChain(std::move(tmp));
397 advanceBufferIfEmpty();
401 if (loopCount == 0) {
402 crtBuf_->cloneOneInto(buf);
403 buf.trimStart(offset_);
405 tmp = crtBuf_->cloneOne();
406 tmp->trimStart(offset_);
407 buf.prependChain(std::move(tmp));
411 if (UNLIKELY(!tryAdvanceBuffer())) {
418 size_t cloneAtMost(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
420 buf = make_unique<folly::IOBuf>();
422 return cloneAtMost(*buf, len);
426 * Return the distance between two cursors.
428 size_t operator-(const CursorBase& other) const {
429 BufType *otherBuf = other.crtBuf_;
432 if (otherBuf != crtBuf_) {
433 len += otherBuf->length() - other.offset_;
435 for (otherBuf = otherBuf->next();
436 otherBuf != crtBuf_ && otherBuf != other.buffer_;
437 otherBuf = otherBuf->next()) {
438 len += otherBuf->length();
441 if (otherBuf == other.buffer_) {
442 std::__throw_out_of_range("wrap-around");
447 if (offset_ < other.offset_) {
448 std::__throw_out_of_range("underflow");
451 len += offset_ - other.offset_;
458 * Return the distance from the given IOBuf to the this cursor.
460 size_t operator-(const BufType* buf) const {
463 const BufType* curBuf = buf;
464 while (curBuf != crtBuf_) {
465 len += curBuf->length();
466 curBuf = curBuf->next();
467 if (curBuf == buf || curBuf == buffer_) {
468 std::__throw_out_of_range("wrap-around");
483 bool tryAdvanceBuffer() {
484 BufType* nextBuf = crtBuf_->next();
485 if (UNLIKELY(nextBuf == buffer_)) {
486 offset_ = crtBuf_->length();
492 static_cast<Derived*>(this)->advanceDone();
496 bool tryRetreatBuffer() {
497 if (UNLIKELY(crtBuf_ == buffer_)) {
501 crtBuf_ = crtBuf_->prev();
502 offset_ = crtBuf_->length();
503 static_cast<Derived*>(this)->advanceDone();
507 void advanceBufferIfEmpty() {
517 void readFixedStringSlow(std::string* str, size_t len) {
518 for (size_t available; (available = length()) < len; ) {
519 str->append(reinterpret_cast<const char*>(data()), available);
520 if (UNLIKELY(!tryAdvanceBuffer())) {
521 std::__throw_out_of_range("string underflow");
525 str->append(reinterpret_cast<const char*>(data()), len);
527 advanceBufferIfEmpty();
530 size_t pullAtMostSlow(void* buf, size_t len) {
531 uint8_t* p = reinterpret_cast<uint8_t*>(buf);
533 for (size_t available; (available = length()) < len; ) {
534 memcpy(p, data(), available);
536 if (UNLIKELY(!tryAdvanceBuffer())) {
542 memcpy(p, data(), len);
544 advanceBufferIfEmpty();
548 void pullSlow(void* buf, size_t len) {
549 if (UNLIKELY(pullAtMostSlow(buf, len) != len)) {
550 std::__throw_out_of_range("underflow");
554 size_t skipAtMostSlow(size_t len) {
556 for (size_t available; (available = length()) < len; ) {
557 skipped += available;
558 if (UNLIKELY(!tryAdvanceBuffer())) {
564 advanceBufferIfEmpty();
565 return skipped + len;
568 void skipSlow(size_t len) {
569 if (UNLIKELY(skipAtMostSlow(len) != len)) {
570 std::__throw_out_of_range("underflow");
574 size_t retreatAtMostSlow(size_t len) {
575 size_t retreated = 0;
576 for (size_t available; (available = offset_) < len;) {
577 retreated += available;
578 if (UNLIKELY(!tryRetreatBuffer())) {
584 return retreated + len;
587 void retreatSlow(size_t len) {
588 if (UNLIKELY(retreatAtMostSlow(len) != len)) {
589 std::__throw_out_of_range("underflow");
599 } // namespace detail
601 class Cursor : public detail::CursorBase<Cursor, const IOBuf> {
603 explicit Cursor(const IOBuf* buf)
604 : detail::CursorBase<Cursor, const IOBuf>(buf) {}
606 template <class OtherDerived, class OtherBuf>
607 explicit Cursor(const detail::CursorBase<OtherDerived, OtherBuf>& cursor)
608 : detail::CursorBase<Cursor, const IOBuf>(cursor) {}
613 template <class Derived>
617 typename std::enable_if<std::is_arithmetic<T>::value>::type
619 const uint8_t* u8 = reinterpret_cast<const uint8_t*>(&value);
620 Derived* d = static_cast<Derived*>(this);
621 d->push(u8, sizeof(T));
625 void writeBE(T value) {
626 Derived* d = static_cast<Derived*>(this);
627 d->write(Endian::big(value));
631 void writeLE(T value) {
632 Derived* d = static_cast<Derived*>(this);
633 d->write(Endian::little(value));
636 void push(const uint8_t* buf, size_t len) {
637 Derived* d = static_cast<Derived*>(this);
638 if (d->pushAtMost(buf, len) != len) {
639 std::__throw_out_of_range("overflow");
643 void push(ByteRange buf) {
644 if (this->pushAtMost(buf) != buf.size()) {
645 std::__throw_out_of_range("overflow");
649 size_t pushAtMost(ByteRange buf) {
650 Derived* d = static_cast<Derived*>(this);
651 return d->pushAtMost(buf.data(), buf.size());
655 * push len bytes of data from input cursor, data could be in an IOBuf chain.
656 * If input cursor contains less than len bytes, or this cursor has less than
657 * len bytes writable space, an out_of_range exception will be thrown.
659 void push(Cursor cursor, size_t len) {
660 if (this->pushAtMost(cursor, len) != len) {
661 std::__throw_out_of_range("overflow");
665 size_t pushAtMost(Cursor cursor, size_t len) {
668 auto currentBuffer = cursor.peekBytes();
669 const uint8_t* crtData = currentBuffer.data();
670 size_t available = currentBuffer.size();
671 if (available == 0) {
672 // end of buffer chain
675 // all data is in current buffer
676 if (available >= len) {
677 this->push(crtData, len);
679 return written + len;
682 // write the whole current IOBuf
683 this->push(crtData, available);
684 cursor.skip(available);
685 written += available;
691 } // namespace detail
693 enum class CursorAccess {
698 template <CursorAccess access>
700 : public detail::CursorBase<RWCursor<access>, IOBuf>,
701 public detail::Writable<RWCursor<access>> {
702 friend class detail::CursorBase<RWCursor<access>, IOBuf>;
704 explicit RWCursor(IOBuf* buf)
705 : detail::CursorBase<RWCursor<access>, IOBuf>(buf),
706 maybeShared_(true) {}
708 template <class OtherDerived, class OtherBuf>
709 explicit RWCursor(const detail::CursorBase<OtherDerived, OtherBuf>& cursor)
710 : detail::CursorBase<RWCursor<access>, IOBuf>(cursor),
711 maybeShared_(true) {}
713 * Gather at least n bytes contiguously into the current buffer,
714 * by coalescing subsequent buffers from the chain as necessary.
716 void gather(size_t n) {
717 // Forbid attempts to gather beyond the end of this IOBuf chain.
718 // Otherwise we could try to coalesce the head of the chain and end up
719 // accidentally freeing it, invalidating the pointer owned by external
722 // If crtBuf_ == head() then IOBuf::gather() will perform all necessary
723 // checking. We only have to perform an explicit check here when calling
724 // gather() on a non-head element.
725 if (this->crtBuf_ != this->head() && this->totalLength() < n) {
726 throw std::overflow_error("cannot gather() past the end of the chain");
728 this->crtBuf_->gather(this->offset_ + n);
730 void gatherAtMost(size_t n) {
731 size_t size = std::min(n, this->totalLength());
732 return this->crtBuf_->gather(this->offset_ + size);
735 using detail::Writable<RWCursor<access>>::pushAtMost;
736 size_t pushAtMost(const uint8_t* buf, size_t len) {
739 // Fast path: the current buffer is big enough.
740 size_t available = this->length();
741 if (LIKELY(available >= len)) {
742 if (access == CursorAccess::UNSHARE) {
745 memcpy(writableData(), buf, len);
746 this->offset_ += len;
750 if (access == CursorAccess::UNSHARE) {
753 memcpy(writableData(), buf, available);
755 if (UNLIKELY(!this->tryAdvanceBuffer())) {
763 void insert(std::unique_ptr<folly::IOBuf> buf) {
764 folly::IOBuf* nextBuf;
765 if (this->offset_ == 0) {
767 nextBuf = this->crtBuf_;
768 this->crtBuf_->prependChain(std::move(buf));
770 std::unique_ptr<folly::IOBuf> remaining;
771 if (this->crtBuf_->length() - this->offset_ > 0) {
772 // Need to split current IOBuf in two.
773 remaining = this->crtBuf_->cloneOne();
774 remaining->trimStart(this->offset_);
775 nextBuf = remaining.get();
776 buf->prependChain(std::move(remaining));
779 nextBuf = this->crtBuf_->next();
781 this->crtBuf_->trimEnd(this->length());
782 this->crtBuf_->appendChain(std::move(buf));
784 // Jump past the new links
786 this->crtBuf_ = nextBuf;
789 uint8_t* writableData() {
790 return this->crtBuf_->writableData() + this->offset_;
794 void maybeUnshare() {
795 if (UNLIKELY(maybeShared_)) {
796 this->crtBuf_->unshareOne();
797 maybeShared_ = false;
808 typedef RWCursor<CursorAccess::PRIVATE> RWPrivateCursor;
809 typedef RWCursor<CursorAccess::UNSHARE> RWUnshareCursor;
812 * Append to the end of a buffer chain, growing the chain (by allocating new
813 * buffers) in increments of at least growth bytes every time. Won't grow
814 * (and push() and ensure() will throw) if growth == 0.
816 * TODO(tudorb): add a flavor of Appender that reallocates one IOBuf instead
819 class Appender : public detail::Writable<Appender> {
821 Appender(IOBuf* buf, uint64_t growth)
823 crtBuf_(buf->prev()),
827 uint8_t* writableData() {
828 return crtBuf_->writableTail();
831 size_t length() const {
832 return crtBuf_->tailroom();
836 * Mark n bytes (must be <= length()) as appended, as per the
837 * IOBuf::append() method.
839 void append(size_t n) {
844 * Ensure at least n contiguous bytes available to write.
845 * Postcondition: length() >= n.
847 void ensure(uint64_t n) {
848 if (LIKELY(length() >= n)) {
852 // Waste the rest of the current buffer and allocate a new one.
853 // Don't make it too small, either.
855 std::__throw_out_of_range("can't grow buffer chain");
858 n = std::max(n, growth_);
859 buffer_->prependChain(IOBuf::create(n));
860 crtBuf_ = buffer_->prev();
863 using detail::Writable<Appender>::pushAtMost;
864 size_t pushAtMost(const uint8_t* buf, size_t len) {
867 // Fast path: it all fits in one buffer.
868 size_t available = length();
869 if (LIKELY(available >= len)) {
870 memcpy(writableData(), buf, len);
875 memcpy(writableData(), buf, available);
878 if (UNLIKELY(!tryGrowChain())) {
887 * Append to the end of this buffer, using a printf() style
890 * Note that folly/Format.h provides nicer and more type-safe mechanisms
891 * for formatting strings, which should generally be preferred over
892 * printf-style formatting. Appender objects can be used directly as an
893 * output argument for Formatter objects. For example:
895 * Appender app(&iobuf);
896 * format("{} {}", "hello", "world")(app);
898 * However, printf-style strings are still needed when dealing with existing
899 * third-party code in some cases.
901 * This will always add a nul-terminating character after the end
902 * of the output. However, the buffer data length will only be updated to
903 * include the data itself. The nul terminator will be the first byte in the
906 * This method may throw exceptions on error.
908 void printf(FOLLY_PRINTF_FORMAT const char* fmt, ...)
909 FOLLY_PRINTF_FORMAT_ATTR(2, 3);
911 void vprintf(const char* fmt, va_list ap);
914 * Calling an Appender object with a StringPiece will append the string
915 * piece. This allows Appender objects to be used directly with
918 void operator()(StringPiece sp) {
923 bool tryGrowChain() {
924 assert(crtBuf_->next() == buffer_);
929 buffer_->prependChain(IOBuf::create(growth_));
930 crtBuf_ = buffer_->prev();
939 class QueueAppender : public detail::Writable<QueueAppender> {
942 * Create an Appender that writes to a IOBufQueue. When we allocate
943 * space in the queue, we grow no more than growth bytes at once
944 * (unless you call ensure() with a bigger value yourself).
946 QueueAppender(IOBufQueue* queue, uint64_t growth) {
947 reset(queue, growth);
950 void reset(IOBufQueue* queue, uint64_t growth) {
955 uint8_t* writableData() {
956 return static_cast<uint8_t*>(queue_->writableTail());
959 size_t length() const { return queue_->tailroom(); }
961 void append(size_t n) { queue_->postallocate(n); }
963 // Ensure at least n contiguous; can go above growth_, throws if
965 void ensure(uint64_t n) { queue_->preallocate(n, growth_); }
968 typename std::enable_if<std::is_arithmetic<T>::value>::type
971 auto p = queue_->preallocate(sizeof(T), growth_);
972 storeUnaligned(p.first, value);
973 queue_->postallocate(sizeof(T));
976 using detail::Writable<QueueAppender>::pushAtMost;
977 size_t pushAtMost(const uint8_t* buf, size_t len) {
978 size_t remaining = len;
979 while (remaining != 0) {
980 auto p = queue_->preallocate(std::min(remaining, growth_),
983 memcpy(p.first, buf, p.second);
984 queue_->postallocate(p.second);
986 remaining -= p.second;
992 void insert(std::unique_ptr<folly::IOBuf> buf) {
994 queue_->append(std::move(buf), true);
998 void insert(const folly::IOBuf& buf) {
1003 folly::IOBufQueue* queue_;
1009 #include <folly/io/Cursor-inl.h>