1/*
2 * Copyright 2013-present 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#pragma once
17
18#include <cassert>
19#include <cstdarg>
20#include <cstring>
21#include <memory>
22#include <stdexcept>
23#include <type_traits>
24
25#include <folly/Likely.h>
26#include <folly/Memory.h>
27#include <folly/Portability.h>
28#include <folly/Range.h>
29#include <folly/io/IOBuf.h>
30#include <folly/io/IOBufQueue.h>
31#include <folly/lang/Bits.h>
32#include <folly/lang/Exception.h>
33
34/**
35 * Cursor class for fast iteration over IOBuf chains.
36 *
37 * Cursor - Read-only access
38 *
39 * RWPrivateCursor - Read-write access, assumes private access to IOBuf chain
40 * RWUnshareCursor - Read-write access, calls unshare on write (COW)
41 * Appender - Write access, assumes private access to IOBuf chain
42 *
43 * Note that RW cursors write in the preallocated part of buffers (that is,
44 * between the buffer's data() and tail()), while Appenders append to the end
45 * of the buffer (between the buffer's tail() and bufferEnd()). Appenders
46 * automatically adjust the buffer pointers, so you may only use one
47 * Appender with a buffer chain; for this reason, Appenders assume private
48 * access to the buffer (you need to call unshare() yourself if necessary).
49 **/
50namespace folly {
51namespace io {
52
53namespace detail {
54
55template <class Derived, class BufType>
56class CursorBase {
57 // Make all the templated classes friends for copy constructor.
58 template <class D, typename B>
59 friend class CursorBase;
60
61 public:
62 explicit CursorBase(BufType* buf) : crtBuf_(buf), buffer_(buf) {
63 if (crtBuf_) {
64 crtPos_ = crtBegin_ = crtBuf_->data();
65 crtEnd_ = crtBuf_->tail();
66 }
67 }
68
69 /**
70 * Copy constructor.
71 *
72 * This also allows constructing a CursorBase from other derived types.
73 * For instance, this allows constructing a Cursor from an RWPrivateCursor.
74 */
75 template <class OtherDerived, class OtherBuf>
76 explicit CursorBase(const CursorBase<OtherDerived, OtherBuf>& cursor)
77 : crtBuf_(cursor.crtBuf_),
78 buffer_(cursor.buffer_),
79 crtBegin_(cursor.crtBegin_),
80 crtEnd_(cursor.crtEnd_),
81 crtPos_(cursor.crtPos_),
82 absolutePos_(cursor.absolutePos_) {}
83
84 /**
85 * Reset cursor to point to a new buffer.
86 */
87 void reset(BufType* buf) {
88 crtBuf_ = buf;
89 buffer_ = buf;
90 absolutePos_ = 0;
91 if (crtBuf_) {
92 crtPos_ = crtBegin_ = crtBuf_->data();
93 crtEnd_ = crtBuf_->tail();
94 }
95 }
96
97 /**
98 * Get the current Cursor position relative to the head of IOBuf chain.
99 */
100 size_t getCurrentPosition() const {
101 dcheckIntegrity();
102 return (crtPos_ - crtBegin_) + absolutePos_;
103 }
104
105 const uint8_t* data() const {
106 dcheckIntegrity();
107 return crtPos_;
108 }
109
110 /**
111 * Return the remaining space available in the current IOBuf.
112 *
113 * May return 0 if the cursor is at the end of an IOBuf. Use peekBytes()
114 * instead if you want to avoid this. peekBytes() will advance to the next
115 * non-empty IOBuf (up to the end of the chain) if the cursor is currently
116 * pointing at the end of a buffer.
117 */
118 size_t length() const {
119 dcheckIntegrity();
120 return crtEnd_ - crtPos_;
121 }
122
123 /**
124 * Return the space available until the end of the entire IOBuf chain.
125 */
126 size_t totalLength() const {
127 if (crtBuf_ == buffer_) {
128 return crtBuf_->computeChainDataLength() - (crtPos_ - crtBegin_);
129 }
130 CursorBase end(buffer_->prev());
131 end.crtPos_ = end.crtEnd_;
132 return end - *this;
133 }
134
135 /**
136 * Return true if the cursor could advance the specified number of bytes
137 * from its current position.
138 * This is useful for applications that want to do checked reads instead of
139 * catching exceptions and is more efficient than using totalLength as it
140 * walks the minimal set of buffers in the chain to determine the result.
141 */
142 bool canAdvance(size_t amount) const {
143 const IOBuf* nextBuf = crtBuf_;
144 size_t available = length();
145 do {
146 if (available >= amount) {
147 return true;
148 }
149 amount -= available;
150 nextBuf = nextBuf->next();
151 available = nextBuf->length();
152 } while (nextBuf != buffer_);
153 return false;
154 }
155
156 /*
157 * Return true if the cursor is at the end of the entire IOBuf chain.
158 */
159 bool isAtEnd() const {
160 dcheckIntegrity();
161 // Check for the simple cases first.
162 if (crtPos_ != crtEnd_) {
163 return false;
164 }
165 if (crtBuf_ == buffer_->prev()) {
166 return true;
167 }
168 // We are at the end of a buffer, but it isn't the last buffer.
169 // We might still be at the end if the remaining buffers in the chain are
170 // empty.
171 const IOBuf* buf = crtBuf_->next();
172 ;
173 while (buf != buffer_) {
174 if (buf->length() > 0) {
175 return false;
176 }
177 buf = buf->next();
178 }
179 return true;
180 }
181
182 /**
183 * Advances the cursor to the end of the entire IOBuf chain.
184 */
185 void advanceToEnd() {
186 // Simple case, we're already in the last IOBuf.
187 if (crtBuf_ == buffer_->prev()) {
188 crtPos_ = crtEnd_;
189 return;
190 }
191
192 auto* nextBuf = crtBuf_->next();
193 while (nextBuf != buffer_) {
194 absolutePos_ += crtEnd_ - crtBegin_;
195
196 crtBuf_ = nextBuf;
197 nextBuf = crtBuf_->next();
198 crtBegin_ = crtBuf_->data();
199 crtPos_ = crtEnd_ = crtBuf_->tail();
200
201 static_cast<Derived*>(this)->advanceDone();
202 }
203 }
204
205 Derived& operator+=(size_t offset) {
206 Derived* p = static_cast<Derived*>(this);
207 p->skip(offset);
208 return *p;
209 }
210 Derived operator+(size_t offset) const {
211 Derived other(*this);
212 other.skip(offset);
213 return other;
214 }
215
216 Derived& operator-=(size_t offset) {
217 Derived* p = static_cast<Derived*>(this);
218 p->retreat(offset);
219 return *p;
220 }
221 Derived operator-(size_t offset) const {
222 Derived other(*this);
223 other.retreat(offset);
224 return other;
225 }
226
227 /**
228 * Compare cursors for equality/inequality.
229 *
230 * Two cursors are equal if they are pointing to the same location in the
231 * same IOBuf chain.
232 */
233 bool operator==(const Derived& other) const {
234 const IOBuf* crtBuf = crtBuf_;
235 auto crtPos = crtPos_;
236 // We can be pointing to the end of a buffer chunk, find first non-empty.
237 while (crtPos == crtBuf->tail() && crtBuf != buffer_->prev()) {
238 crtBuf = crtBuf->next();
239 crtPos = crtBuf->data();
240 }
241
242 const IOBuf* crtBufOther = other.crtBuf_;
243 auto crtPosOther = other.crtPos_;
244 // We can be pointing to the end of a buffer chunk, find first non-empty.
245 while (crtPosOther == crtBufOther->tail() &&
246 crtBufOther != other.buffer_->prev()) {
247 crtBufOther = crtBufOther->next();
248 crtPosOther = crtBufOther->data();
249 }
250 return (crtPos == crtPosOther) && (crtBuf == crtBufOther);
251 }
252 bool operator!=(const Derived& other) const {
253 return !operator==(other);
254 }
255
256 template <class T>
257 typename std::enable_if<std::is_arithmetic<T>::value, bool>::type tryRead(
258 T& val) {
259 if (LIKELY(crtPos_ + sizeof(T) <= crtEnd_)) {
260 val = loadUnaligned<T>(data());
261 crtPos_ += sizeof(T);
262 return true;
263 }
264 return pullAtMostSlow(&val, sizeof(T)) == sizeof(T);
265 }
266
267 template <class T>
268 bool tryReadBE(T& val) {
269 const bool result = tryRead(val);
270 val = Endian::big(val);
271 return result;
272 }
273
274 template <class T>
275 bool tryReadLE(T& val) {
276 const bool result = tryRead(val);
277 val = Endian::little(val);
278 return result;
279 }
280
281 template <class T>
282 T read() {
283 if (LIKELY(crtPos_ + sizeof(T) <= crtEnd_)) {
284 T val = loadUnaligned<T>(data());
285 crtPos_ += sizeof(T);
286 return val;
287 } else {
288 return readSlow<T>();
289 }
290 }
291
292 template <class T>
293 T readBE() {
294 return Endian::big(read<T>());
295 }
296
297 template <class T>
298 T readLE() {
299 return Endian::little(read<T>());
300 }
301
302 /**
303 * Read a fixed-length string.
304 *
305 * The std::string-based APIs should probably be avoided unless you
306 * ultimately want the data to live in an std::string. You're better off
307 * using the pull() APIs to copy into a raw buffer otherwise.
308 */
309 std::string readFixedString(size_t len) {
310 std::string str;
311 str.reserve(len);
312 if (LIKELY(length() >= len)) {
313 str.append(reinterpret_cast<const char*>(data()), len);
314 crtPos_ += len;
315 } else {
316 readFixedStringSlow(&str, len);
317 }
318 return str;
319 }
320
321 /**
322 * Read a string consisting of bytes until the given terminator character is
323 * seen. Raises an std::length_error if maxLength bytes have been processed
324 * before the terminator is seen.
325 *
326 * See comments in readFixedString() about when it's appropriate to use this
327 * vs. using pull().
328 */
329 std::string readTerminatedString(
330 char termChar = '\0',
331 size_t maxLength = std::numeric_limits<size_t>::max());
332
333 /*
334 * Read all bytes until the specified predicate returns true.
335 *
336 * The predicate will be called on each byte in turn, until it returns false
337 * or until the end of the IOBuf chain is reached.
338 *
339 * Returns the result as a string.
340 */
341 template <typename Predicate>
342 std::string readWhile(const Predicate& predicate);
343
344 /*
345 * Read all bytes until the specified predicate returns true.
346 *
347 * This is a more generic version of readWhile() takes an arbitrary Output
348 * object, and calls Output::append() with each chunk of matching data.
349 */
350 template <typename Predicate, typename Output>
351 void readWhile(const Predicate& predicate, Output& out);
352
353 /*
354 * Skip all bytes until the specified predicate returns true.
355 *
356 * The predicate will be called on each byte in turn, until it returns false
357 * or until the end of the IOBuf chain is reached.
358 */
359 template <typename Predicate>
360 void skipWhile(const Predicate& predicate);
361
362 size_t skipAtMost(size_t len) {
363 dcheckIntegrity();
364 if (LIKELY(crtPos_ + len < crtEnd_)) {
365 crtPos_ += len;
366 return len;
367 }
368 return skipAtMostSlow(len);
369 }
370
371 void skip(size_t len) {
372 dcheckIntegrity();
373 if (LIKELY(crtPos_ + len < crtEnd_)) {
374 crtPos_ += len;
375 } else {
376 skipSlow(len);
377 }
378 }
379
380 /**
381 * Skip bytes in the current IOBuf without advancing to the next one.
382 * Precondition: length() >= len
383 */
384 void skipNoAdvance(size_t len) {
385 DCHECK_LE(len, length());
386 crtPos_ += len;
387 }
388
389 size_t retreatAtMost(size_t len) {
390 dcheckIntegrity();
391 if (len <= static_cast<size_t>(crtPos_ - crtBegin_)) {
392 crtPos_ -= len;
393 return len;
394 }
395 return retreatAtMostSlow(len);
396 }
397
398 void retreat(size_t len) {
399 dcheckIntegrity();
400 if (len <= static_cast<size_t>(crtPos_ - crtBegin_)) {
401 crtPos_ -= len;
402 } else {
403 retreatSlow(len);
404 }
405 }
406
407 size_t pullAtMost(void* buf, size_t len) {
408 dcheckIntegrity();
409 // Fast path: it all fits in one buffer.
410 if (LIKELY(crtPos_ + len <= crtEnd_)) {
411 memcpy(buf, data(), len);
412 crtPos_ += len;
413 return len;
414 }
415 return pullAtMostSlow(buf, len);
416 }
417
418 void pull(void* buf, size_t len) {
419 if (UNLIKELY(len == 0)) {
420 return;
421 }
422 dcheckIntegrity();
423 if (LIKELY(crtPos_ + len <= crtEnd_)) {
424 memcpy(buf, data(), len);
425 crtPos_ += len;
426 } else {
427 pullSlow(buf, len);
428 }
429 }
430
431 /**
432 * Return the available data in the current buffer.
433 * If you want to gather more data from the chain into a contiguous region
434 * (for hopefully zero-copy access), use gather() before peekBytes().
435 */
436 ByteRange peekBytes() {
437 // Ensure that we're pointing to valid data
438 size_t available = length();
439 while (UNLIKELY(available == 0 && tryAdvanceBuffer())) {
440 available = length();
441 }
442 return ByteRange{data(), available};
443 }
444
445 /**
446 * Alternate version of peekBytes() that returns a std::pair
447 * instead of a ByteRange. (This method pre-dates ByteRange.)
448 *
449 * This function will eventually be deprecated.
450 */
451 std::pair<const uint8_t*, size_t> peek() {
452 auto bytes = peekBytes();
453 return std::make_pair(bytes.data(), bytes.size());
454 }
455
456 void clone(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
457 if (UNLIKELY(cloneAtMost(buf, len) != len)) {
458 throw_exception<std::out_of_range>("underflow");
459 }
460 }
461
462 void clone(folly::IOBuf& buf, size_t len) {
463 if (UNLIKELY(cloneAtMost(buf, len) != len)) {
464 throw_exception<std::out_of_range>("underflow");
465 }
466 }
467
468 size_t cloneAtMost(folly::IOBuf& buf, size_t len) {
469 // We might be at the end of buffer.
470 advanceBufferIfEmpty();
471
472 std::unique_ptr<folly::IOBuf> tmp;
473 size_t copied = 0;
474 for (int loopCount = 0; true; ++loopCount) {
475 // Fast path: it all fits in one buffer.
476 size_t available = length();
477 if (LIKELY(available >= len)) {
478 if (loopCount == 0) {
479 crtBuf_->cloneOneInto(buf);
480 buf.trimStart(crtPos_ - crtBegin_);
481 buf.trimEnd(buf.length() - len);
482 } else {
483 tmp = crtBuf_->cloneOne();
484 tmp->trimStart(crtPos_ - crtBegin_);
485 tmp->trimEnd(tmp->length() - len);
486 buf.prependChain(std::move(tmp));
487 }
488
489 crtPos_ += len;
490 advanceBufferIfEmpty();
491 return copied + len;
492 }
493
494 if (loopCount == 0) {
495 crtBuf_->cloneOneInto(buf);
496 buf.trimStart(crtPos_ - crtBegin_);
497 } else {
498 tmp = crtBuf_->cloneOne();
499 tmp->trimStart(crtPos_ - crtBegin_);
500 buf.prependChain(std::move(tmp));
501 }
502
503 copied += available;
504 if (UNLIKELY(!tryAdvanceBuffer())) {
505 return copied;
506 }
507 len -= available;
508 }
509 }
510
511 size_t cloneAtMost(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
512 if (!buf) {
513 buf = std::make_unique<folly::IOBuf>();
514 }
515 return cloneAtMost(*buf, len);
516 }
517
518 /**
519 * Return the distance between two cursors.
520 */
521 size_t operator-(const CursorBase& other) const {
522 BufType* otherBuf = other.crtBuf_;
523 size_t len = 0;
524
525 if (otherBuf != crtBuf_) {
526 len += other.crtEnd_ - other.crtPos_;
527
528 for (otherBuf = otherBuf->next();
529 otherBuf != crtBuf_ && otherBuf != other.buffer_;
530 otherBuf = otherBuf->next()) {
531 len += otherBuf->length();
532 }
533
534 if (otherBuf == other.buffer_) {
535 throw_exception<std::out_of_range>("wrap-around");
536 }
537
538 len += crtPos_ - crtBegin_;
539 } else {
540 if (crtPos_ < other.crtPos_) {
541 throw_exception<std::out_of_range>("underflow");
542 }
543
544 len += crtPos_ - other.crtPos_;
545 }
546
547 return len;
548 }
549
550 /**
551 * Return the distance from the given IOBuf to the this cursor.
552 */
553 size_t operator-(const BufType* buf) const {
554 size_t len = 0;
555
556 const BufType* curBuf = buf;
557 while (curBuf != crtBuf_) {
558 len += curBuf->length();
559 curBuf = curBuf->next();
560 if (curBuf == buf || curBuf == buffer_) {
561 throw_exception<std::out_of_range>("wrap-around");
562 }
563 }
564
565 len += crtPos_ - crtBegin_;
566 return len;
567 }
568
569 protected:
570 void dcheckIntegrity() const {
571 DCHECK(crtBegin_ <= crtPos_ && crtPos_ <= crtEnd_);
572 DCHECK(crtBuf_ == nullptr || crtBegin_ == crtBuf_->data());
573 DCHECK(
574 crtBuf_ == nullptr ||
575 (std::size_t)(crtEnd_ - crtBegin_) == crtBuf_->length());
576 }
577
578 ~CursorBase() {}
579
580 BufType* head() {
581 return buffer_;
582 }
583
584 bool tryAdvanceBuffer() {
585 BufType* nextBuf = crtBuf_->next();
586 if (UNLIKELY(nextBuf == buffer_)) {
587 crtPos_ = crtEnd_;
588 return false;
589 }
590
591 absolutePos_ += crtEnd_ - crtBegin_;
592 crtBuf_ = nextBuf;
593 crtPos_ = crtBegin_ = crtBuf_->data();
594 crtEnd_ = crtBuf_->tail();
595 static_cast<Derived*>(this)->advanceDone();
596 return true;
597 }
598
599 bool tryRetreatBuffer() {
600 if (UNLIKELY(crtBuf_ == buffer_)) {
601 crtPos_ = crtBegin_;
602 return false;
603 }
604 crtBuf_ = crtBuf_->prev();
605 crtBegin_ = crtBuf_->data();
606 crtPos_ = crtEnd_ = crtBuf_->tail();
607 absolutePos_ -= crtEnd_ - crtBegin_;
608 static_cast<Derived*>(this)->advanceDone();
609 return true;
610 }
611
612 void advanceBufferIfEmpty() {
613 dcheckIntegrity();
614 if (crtPos_ == crtEnd_) {
615 tryAdvanceBuffer();
616 }
617 }
618
619 BufType* crtBuf_;
620 BufType* buffer_;
621 const uint8_t* crtBegin_{nullptr};
622 const uint8_t* crtEnd_{nullptr};
623 const uint8_t* crtPos_{nullptr};
624 size_t absolutePos_{0};
625
626 private:
627 template <class T>
628 FOLLY_NOINLINE T readSlow() {
629 T val;
630 pullSlow(&val, sizeof(T));
631 return val;
632 }
633
634 void readFixedStringSlow(std::string* str, size_t len) {
635 for (size_t available; (available = length()) < len;) {
636 str->append(reinterpret_cast<const char*>(data()), available);
637 if (UNLIKELY(!tryAdvanceBuffer())) {
638 throw_exception<std::out_of_range>("string underflow");
639 }
640 len -= available;
641 }
642 str->append(reinterpret_cast<const char*>(data()), len);
643 crtPos_ += len;
644 advanceBufferIfEmpty();
645 }
646
647 size_t pullAtMostSlow(void* buf, size_t len) {
648 // If the length of this buffer is 0 try advancing it.
649 // Otherwise on the first iteration of the following loop memcpy is called
650 // with a null source pointer.
651 if (UNLIKELY(length() == 0 && !tryAdvanceBuffer())) {
652 return 0;
653 }
654 uint8_t* p = reinterpret_cast<uint8_t*>(buf);
655 size_t copied = 0;
656 for (size_t available; (available = length()) < len;) {
657 memcpy(p, data(), available);
658 copied += available;
659 if (UNLIKELY(!tryAdvanceBuffer())) {
660 return copied;
661 }
662 p += available;
663 len -= available;
664 }
665 memcpy(p, data(), len);
666 crtPos_ += len;
667 advanceBufferIfEmpty();
668 return copied + len;
669 }
670
671 void pullSlow(void* buf, size_t len) {
672 if (UNLIKELY(pullAtMostSlow(buf, len) != len)) {
673 throw_exception<std::out_of_range>("underflow");
674 }
675 }
676
677 size_t skipAtMostSlow(size_t len) {
678 size_t skipped = 0;
679 for (size_t available; (available = length()) < len;) {
680 skipped += available;
681 if (UNLIKELY(!tryAdvanceBuffer())) {
682 return skipped;
683 }
684 len -= available;
685 }
686 crtPos_ += len;
687 advanceBufferIfEmpty();
688 return skipped + len;
689 }
690
691 void skipSlow(size_t len) {
692 if (UNLIKELY(skipAtMostSlow(len) != len)) {
693 throw_exception<std::out_of_range>("underflow");
694 }
695 }
696
697 size_t retreatAtMostSlow(size_t len) {
698 size_t retreated = 0;
699 for (size_t available; (available = crtPos_ - crtBegin_) < len;) {
700 retreated += available;
701 if (UNLIKELY(!tryRetreatBuffer())) {
702 return retreated;
703 }
704 len -= available;
705 }
706 crtPos_ -= len;
707 return retreated + len;
708 }
709
710 void retreatSlow(size_t len) {
711 if (UNLIKELY(retreatAtMostSlow(len) != len)) {
712 throw_exception<std::out_of_range>("underflow");
713 }
714 }
715
716 void advanceDone() {}
717};
718
719} // namespace detail
720
721class Cursor : public detail::CursorBase<Cursor, const IOBuf> {
722 public:
723 explicit Cursor(const IOBuf* buf)
724 : detail::CursorBase<Cursor, const IOBuf>(buf) {}
725
726 template <class OtherDerived, class OtherBuf>
727 explicit Cursor(const detail::CursorBase<OtherDerived, OtherBuf>& cursor)
728 : detail::CursorBase<Cursor, const IOBuf>(cursor) {}
729};
730
731namespace detail {
732
733template <class Derived>
734class Writable {
735 public:
736 template <class T>
737 typename std::enable_if<std::is_arithmetic<T>::value>::type write(T value) {
738 const uint8_t* u8 = reinterpret_cast<const uint8_t*>(&value);
739 Derived* d = static_cast<Derived*>(this);
740 d->push(u8, sizeof(T));
741 }
742
743 template <class T>
744 void writeBE(T value) {
745 Derived* d = static_cast<Derived*>(this);
746 d->write(Endian::big(value));
747 }
748
749 template <class T>
750 void writeLE(T value) {
751 Derived* d = static_cast<Derived*>(this);
752 d->write(Endian::little(value));
753 }
754
755 void push(const uint8_t* buf, size_t len) {
756 Derived* d = static_cast<Derived*>(this);
757 if (d->pushAtMost(buf, len) != len) {
758 throw_exception<std::out_of_range>("overflow");
759 }
760 }
761
762 void push(ByteRange buf) {
763 if (this->pushAtMost(buf) != buf.size()) {
764 throw_exception<std::out_of_range>("overflow");
765 }
766 }
767
768 size_t pushAtMost(ByteRange buf) {
769 Derived* d = static_cast<Derived*>(this);
770 return d->pushAtMost(buf.data(), buf.size());
771 }
772
773 /**
774 * push len bytes of data from input cursor, data could be in an IOBuf chain.
775 * If input cursor contains less than len bytes, or this cursor has less than
776 * len bytes writable space, an out_of_range exception will be thrown.
777 */
778 void push(Cursor cursor, size_t len) {
779 if (this->pushAtMost(cursor, len) != len) {
780 throw_exception<std::out_of_range>("overflow");
781 }
782 }
783
784 size_t pushAtMost(Cursor cursor, size_t len) {
785 size_t written = 0;
786 for (;;) {
787 auto currentBuffer = cursor.peekBytes();
788 const uint8_t* crtData = currentBuffer.data();
789 size_t available = currentBuffer.size();
790 if (available == 0) {
791 // end of buffer chain
792 return written;
793 }
794 // all data is in current buffer
795 if (available >= len) {
796 this->push(crtData, len);
797 cursor.skip(len);
798 return written + len;
799 }
800
801 // write the whole current IOBuf
802 this->push(crtData, available);
803 cursor.skip(available);
804 written += available;
805 len -= available;
806 }
807 }
808};
809
810} // namespace detail
811
812enum class CursorAccess { PRIVATE, UNSHARE };
813
814template <CursorAccess access>
815class RWCursor : public detail::CursorBase<RWCursor<access>, IOBuf>,
816 public detail::Writable<RWCursor<access>> {
817 friend class detail::CursorBase<RWCursor<access>, IOBuf>;
818
819 public:
820 explicit RWCursor(IOBuf* buf)
821 : detail::CursorBase<RWCursor<access>, IOBuf>(buf), maybeShared_(true) {}
822
823 template <class OtherDerived, class OtherBuf>
824 explicit RWCursor(const detail::CursorBase<OtherDerived, OtherBuf>& cursor)
825 : detail::CursorBase<RWCursor<access>, IOBuf>(cursor),
826 maybeShared_(true) {}
827 /**
828 * Gather at least n bytes contiguously into the current buffer,
829 * by coalescing subsequent buffers from the chain as necessary.
830 */
831 void gather(size_t n) {
832 // Forbid attempts to gather beyond the end of this IOBuf chain.
833 // Otherwise we could try to coalesce the head of the chain and end up
834 // accidentally freeing it, invalidating the pointer owned by external
835 // code.
836 //
837 // If crtBuf_ == head() then IOBuf::gather() will perform all necessary
838 // checking. We only have to perform an explicit check here when calling
839 // gather() on a non-head element.
840 if (this->crtBuf_ != this->head() && this->totalLength() < n) {
841 throw std::overflow_error("cannot gather() past the end of the chain");
842 }
843 size_t offset = this->crtPos_ - this->crtBegin_;
844 this->crtBuf_->gather(offset + n);
845 this->crtBegin_ = this->crtBuf_->data();
846 this->crtEnd_ = this->crtBuf_->tail();
847 this->crtPos_ = this->crtBegin_ + offset;
848 }
849 void gatherAtMost(size_t n) {
850 this->dcheckIntegrity();
851 size_t size = std::min(n, this->totalLength());
852 size_t offset = this->crtPos_ - this->crtBegin_;
853 this->crtBuf_->gather(offset + size);
854 this->crtBegin_ = this->crtBuf_->data();
855 this->crtEnd_ = this->crtBuf_->tail();
856 this->crtPos_ = this->crtBegin_ + offset;
857 }
858
859 using detail::Writable<RWCursor<access>>::pushAtMost;
860 size_t pushAtMost(const uint8_t* buf, size_t len) {
861 // We have to explicitly check for an input length of 0.
862 // We support buf being nullptr in this case, but we need to avoid calling
863 // memcpy() with a null source pointer, since that is undefined behavior
864 // even if the length is 0.
865 if (len == 0) {
866 return 0;
867 }
868
869 size_t copied = 0;
870 for (;;) {
871 // Fast path: the current buffer is big enough.
872 size_t available = this->length();
873 if (LIKELY(available >= len)) {
874 if (access == CursorAccess::UNSHARE) {
875 maybeUnshare();
876 }
877 memcpy(writableData(), buf, len);
878 this->crtPos_ += len;
879 return copied + len;
880 }
881
882 if (access == CursorAccess::UNSHARE) {
883 maybeUnshare();
884 }
885 memcpy(writableData(), buf, available);
886 copied += available;
887 if (UNLIKELY(!this->tryAdvanceBuffer())) {
888 return copied;
889 }
890 buf += available;
891 len -= available;
892 }
893 }
894
895 void insert(std::unique_ptr<folly::IOBuf> buf) {
896 this->dcheckIntegrity();
897 this->absolutePos_ += buf->computeChainDataLength();
898 if (this->crtPos_ == this->crtBegin_ && this->crtBuf_ != this->buffer_) {
899 // Can just prepend
900 this->crtBuf_->prependChain(std::move(buf));
901 } else {
902 IOBuf* nextBuf;
903 std::unique_ptr<folly::IOBuf> remaining;
904 if (this->crtPos_ != this->crtEnd_) {
905 // Need to split current IOBuf in two.
906 remaining = this->crtBuf_->cloneOne();
907 remaining->trimStart(this->crtPos_ - this->crtBegin_);
908 nextBuf = remaining.get();
909 buf->prependChain(std::move(remaining));
910 } else {
911 // Can just append
912 nextBuf = this->crtBuf_->next();
913 }
914 this->crtBuf_->trimEnd(this->length());
915 this->absolutePos_ += this->crtPos_ - this->crtBegin_;
916 this->crtBuf_->appendChain(std::move(buf));
917
918 if (nextBuf == this->buffer_) {
919 // We've just appended to the end of the buffer, so advance to the end.
920 this->crtBuf_ = this->buffer_->prev();
921 this->crtBegin_ = this->crtBuf_->data();
922 this->crtPos_ = this->crtEnd_ = this->crtBuf_->tail();
923 // This has already been accounted for, so remove it.
924 this->absolutePos_ -= this->crtEnd_ - this->crtBegin_;
925 } else {
926 // Jump past the new links
927 this->crtBuf_ = nextBuf;
928 this->crtPos_ = this->crtBegin_ = this->crtBuf_->data();
929 this->crtEnd_ = this->crtBuf_->tail();
930 }
931 }
932 }
933
934 uint8_t* writableData() {
935 this->dcheckIntegrity();
936 return this->crtBuf_->writableData() + (this->crtPos_ - this->crtBegin_);
937 }
938
939 private:
940 void maybeUnshare() {
941 if (UNLIKELY(maybeShared_)) {
942 size_t offset = this->crtPos_ - this->crtBegin_;
943 this->crtBuf_->unshareOne();
944 this->crtBegin_ = this->crtBuf_->data();
945 this->crtEnd_ = this->crtBuf_->tail();
946 this->crtPos_ = this->crtBegin_ + offset;
947 maybeShared_ = false;
948 }
949 }
950
951 void advanceDone() {
952 maybeShared_ = true;
953 }
954
955 bool maybeShared_;
956};
957
958typedef RWCursor<CursorAccess::PRIVATE> RWPrivateCursor;
959typedef RWCursor<CursorAccess::UNSHARE> RWUnshareCursor;
960
961/**
962 * Append to the end of a buffer chain, growing the chain (by allocating new
963 * buffers) in increments of at least growth bytes every time. Won't grow
964 * (and push() and ensure() will throw) if growth == 0.
965 *
966 * TODO(tudorb): add a flavor of Appender that reallocates one IOBuf instead
967 * of chaining.
968 */
969class Appender : public detail::Writable<Appender> {
970 public:
971 Appender(IOBuf* buf, std::size_t growth)
972 : buffer_(buf), crtBuf_(buf->prev()), growth_(growth) {}
973
974 uint8_t* writableData() {
975 return crtBuf_->writableTail();
976 }
977
978 size_t length() const {
979 return crtBuf_->tailroom();
980 }
981
982 /**
983 * Mark n bytes (must be <= length()) as appended, as per the
984 * IOBuf::append() method.
985 */
986 void append(size_t n) {
987 crtBuf_->append(n);
988 }
989
990 /**
991 * Ensure at least n contiguous bytes available to write.
992 * Postcondition: length() >= n.
993 */
994 void ensure(std::size_t n) {
995 if (LIKELY(length() >= n)) {
996 return;
997 }
998
999 // Waste the rest of the current buffer and allocate a new one.
1000 // Don't make it too small, either.
1001 if (growth_ == 0) {
1002 throw_exception<std::out_of_range>("can't grow buffer chain");
1003 }
1004
1005 n = std::max(n, growth_);
1006 buffer_->prependChain(IOBuf::create(n));
1007 crtBuf_ = buffer_->prev();
1008 }
1009
1010 using detail::Writable<Appender>::pushAtMost;
1011 size_t pushAtMost(const uint8_t* buf, size_t len) {
1012 // We have to explicitly check for an input length of 0.
1013 // We support buf being nullptr in this case, but we need to avoid calling
1014 // memcpy() with a null source pointer, since that is undefined behavior
1015 // even if the length is 0.
1016 if (len == 0) {
1017 return 0;
1018 }
1019
1020 // If the length of this buffer is 0 try growing it.
1021 // Otherwise on the first iteration of the following loop memcpy is called
1022 // with a null source pointer.
1023 if (UNLIKELY(length() == 0 && !tryGrowChain())) {
1024 return 0;
1025 }
1026
1027 size_t copied = 0;
1028 for (;;) {
1029 // Fast path: it all fits in one buffer.
1030 size_t available = length();
1031 if (LIKELY(available >= len)) {
1032 memcpy(writableData(), buf, len);
1033 append(len);
1034 return copied + len;
1035 }
1036
1037 memcpy(writableData(), buf, available);
1038 append(available);
1039 copied += available;
1040 if (UNLIKELY(!tryGrowChain())) {
1041 return copied;
1042 }
1043 buf += available;
1044 len -= available;
1045 }
1046 }
1047
1048 /*
1049 * Append to the end of this buffer, using a printf() style
1050 * format specifier.
1051 *
1052 * Note that folly/Format.h provides nicer and more type-safe mechanisms
1053 * for formatting strings, which should generally be preferred over
1054 * printf-style formatting. Appender objects can be used directly as an
1055 * output argument for Formatter objects. For example:
1056 *
1057 * Appender app(&iobuf);
1058 * format("{} {}", "hello", "world")(app);
1059 *
1060 * However, printf-style strings are still needed when dealing with existing
1061 * third-party code in some cases.
1062 *
1063 * This will always add a nul-terminating character after the end
1064 * of the output. However, the buffer data length will only be updated to
1065 * include the data itself. The nul terminator will be the first byte in the
1066 * buffer tailroom.
1067 *
1068 * This method may throw exceptions on error.
1069 */
1070 void printf(FOLLY_PRINTF_FORMAT const char* fmt, ...)
1071 FOLLY_PRINTF_FORMAT_ATTR(2, 3);
1072
1073 void vprintf(const char* fmt, va_list ap);
1074
1075 /*
1076 * Calling an Appender object with a StringPiece will append the string
1077 * piece. This allows Appender objects to be used directly with
1078 * Formatter.
1079 */
1080 void operator()(StringPiece sp) {
1081 push(ByteRange(sp));
1082 }
1083
1084 private:
1085 bool tryGrowChain() {
1086 assert(crtBuf_->next() == buffer_);
1087 if (growth_ == 0) {
1088 return false;
1089 }
1090
1091 buffer_->prependChain(IOBuf::create(growth_));
1092 crtBuf_ = buffer_->prev();
1093 return true;
1094 }
1095
1096 IOBuf* buffer_;
1097 IOBuf* crtBuf_;
1098 std::size_t growth_;
1099};
1100
1101class QueueAppender : public detail::Writable<QueueAppender> {
1102 public:
1103 /**
1104 * Create an Appender that writes to a IOBufQueue. When we allocate
1105 * space in the queue, we grow no more than growth bytes at once
1106 * (unless you call ensure() with a bigger value yourself).
1107 */
1108 QueueAppender(IOBufQueue* queue, std::size_t growth)
1109 : queueCache_(queue), growth_(growth) {}
1110
1111 void reset(IOBufQueue* queue, std::size_t growth) {
1112 queueCache_.reset(queue);
1113 growth_ = growth;
1114 }
1115
1116 uint8_t* writableData() {
1117 return queueCache_.writableData();
1118 }
1119
1120 size_t length() {
1121 return queueCache_.length();
1122 }
1123
1124 void append(size_t n) {
1125 queueCache_.append(n);
1126 }
1127
1128 // Ensure at least n contiguous; can go above growth_, throws if
1129 // not enough room.
1130 void ensure(size_t n) {
1131 if (length() < n) {
1132 ensureSlow(n);
1133 }
1134 }
1135
1136 template <class T>
1137 typename std::enable_if<std::is_arithmetic<T>::value>::type write(T value) {
1138 // We can't fail.
1139 if (length() >= sizeof(T)) {
1140 storeUnaligned(queueCache_.writableData(), value);
1141 queueCache_.appendUnsafe(sizeof(T));
1142 } else {
1143 writeSlow<T>(value);
1144 }
1145 }
1146
1147 using detail::Writable<QueueAppender>::pushAtMost;
1148 size_t pushAtMost(const uint8_t* buf, size_t len) {
1149 // Fill the current buffer
1150 const size_t copyLength = std::min(len, length());
1151 if (copyLength != 0) {
1152 memcpy(writableData(), buf, copyLength);
1153 queueCache_.appendUnsafe(copyLength);
1154 buf += copyLength;
1155 }
1156 size_t remaining = len - copyLength;
1157 // Allocate more buffers as necessary
1158 while (remaining != 0) {
1159 auto p = queueCache_.queue()->preallocate(
1160 std::min(remaining, growth_), growth_, remaining);
1161 memcpy(p.first, buf, p.second);
1162 queueCache_.queue()->postallocate(p.second);
1163 buf += p.second;
1164 remaining -= p.second;
1165 }
1166 return len;
1167 }
1168
1169 void insert(std::unique_ptr<folly::IOBuf> buf) {
1170 if (buf) {
1171 queueCache_.queue()->append(std::move(buf), true);
1172 }
1173 }
1174
1175 void insert(const folly::IOBuf& buf) {
1176 insert(buf.clone());
1177 }
1178
1179 private:
1180 folly::IOBufQueue::WritableRangeCache queueCache_{nullptr};
1181 size_t growth_{0};
1182
1183 FOLLY_NOINLINE void ensureSlow(size_t n) {
1184 queueCache_.queue()->preallocate(n, growth_);
1185 queueCache_.fillCache();
1186 }
1187
1188 template <class T>
1189 typename std::enable_if<std::is_arithmetic<T>::value>::type FOLLY_NOINLINE
1190 writeSlow(T value) {
1191 queueCache_.queue()->preallocate(sizeof(T), growth_);
1192 queueCache_.fillCache();
1193
1194 storeUnaligned(queueCache_.writableData(), value);
1195 queueCache_.appendUnsafe(sizeof(T));
1196 }
1197};
1198
1199} // namespace io
1200} // namespace folly
1201
1202#include <folly/io/Cursor-inl.h>
1203