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 | **/ |
50 | namespace folly { |
51 | namespace io { |
52 | |
53 | namespace detail { |
54 | |
55 | template <class Derived, class BufType> |
56 | class 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 | |
721 | class 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 | |
731 | namespace detail { |
732 | |
733 | template <class Derived> |
734 | class 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 | |
812 | enum class CursorAccess { PRIVATE, UNSHARE }; |
813 | |
814 | template <CursorAccess access> |
815 | class 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 | |
958 | typedef RWCursor<CursorAccess::PRIVATE> RWPrivateCursor; |
959 | typedef 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 | */ |
969 | class 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 | |
1101 | class 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 | |