Codemod: use #include angle brackets in folly and thrift
[folly.git] / folly / io / IOBuf.h
1 /*
2  * Copyright 2014 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
17 #ifndef FOLLY_IO_IOBUF_H_
18 #define FOLLY_IO_IOBUF_H_
19
20 #include <glog/logging.h>
21 #include <atomic>
22 #include <cassert>
23 #include <cinttypes>
24 #include <cstddef>
25 #include <cstring>
26 #include <memory>
27 #include <limits>
28 #include <sys/uio.h>
29 #include <type_traits>
30
31 #include <boost/iterator/iterator_facade.hpp>
32
33 #include <folly/FBString.h>
34 #include <folly/Range.h>
35 #include <folly/FBVector.h>
36
37 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
38 #pragma GCC diagnostic push
39 #pragma GCC diagnostic ignored "-Wshadow"
40
41 namespace folly {
42
43 /**
44  * An IOBuf is a pointer to a buffer of data.
45  *
46  * IOBuf objects are intended to be used primarily for networking code, and are
47  * modelled somewhat after FreeBSD's mbuf data structure, and Linux's sk_buff
48  * structure.
49  *
50  * IOBuf objects facilitate zero-copy network programming, by allowing multiple
51  * IOBuf objects to point to the same underlying buffer of data, using a
52  * reference count to track when the buffer is no longer needed and can be
53  * freed.
54  *
55  *
56  * Data Layout
57  * -----------
58  *
59  * The IOBuf itself is a small object containing a pointer to the buffer and
60  * information about which segment of the buffer contains valid data.
61  *
62  * The data layout looks like this:
63  *
64  *  +-------+
65  *  | IOBuf |
66  *  +-------+
67  *   /
68  *  |
69  *  v
70  *  +------------+--------------------+-----------+
71  *  | headroom   |        data        |  tailroom |
72  *  +------------+--------------------+-----------+
73  *  ^            ^                    ^           ^
74  *  buffer()   data()               tail()      bufferEnd()
75  *
76  *  The length() method returns the length of the valid data; capacity()
77  *  returns the entire capacity of the buffer (from buffer() to bufferEnd()).
78  *  The headroom() and tailroom() methods return the amount of unused capacity
79  *  available before and after the data.
80  *
81  *
82  * Buffer Sharing
83  * --------------
84  *
85  * The buffer itself is reference counted, and multiple IOBuf objects may point
86  * to the same buffer.  Each IOBuf may point to a different section of valid
87  * data within the underlying buffer.  For example, if multiple protocol
88  * requests are read from the network into a single buffer, a separate IOBuf
89  * may be created for each request, all sharing the same underlying buffer.
90  *
91  * In other words, when multiple IOBufs share the same underlying buffer, the
92  * data() and tail() methods on each IOBuf may point to a different segment of
93  * the data.  However, the buffer() and bufferEnd() methods will point to the
94  * same location for all IOBufs sharing the same underlying buffer.
95  *
96  *       +-----------+     +---------+
97  *       |  IOBuf 1  |     | IOBuf 2 |
98  *       +-----------+     +---------+
99  *        |         | _____/        |
100  *   data |    tail |/    data      | tail
101  *        v         v               v
102  *  +-------------------------------------+
103  *  |     |         |               |     |
104  *  +-------------------------------------+
105  *
106  * If you only read data from an IOBuf, you don't need to worry about other
107  * IOBuf objects possibly sharing the same underlying buffer.  However, if you
108  * ever write to the buffer you need to first ensure that no other IOBufs point
109  * to the same buffer.  The unshare() method may be used to ensure that you
110  * have an unshared buffer.
111  *
112  *
113  * IOBuf Chains
114  * ------------
115  *
116  * IOBuf objects also contain pointers to next and previous IOBuf objects.
117  * This can be used to represent a single logical piece of data that its stored
118  * in non-contiguous chunks in separate buffers.
119  *
120  * A single IOBuf object can only belong to one chain at a time.
121  *
122  * IOBuf chains are always circular.  The "prev" pointer in the head of the
123  * chain points to the tail of the chain.  However, it is up to the user to
124  * decide which IOBuf is the head.  Internally the IOBuf code does not care
125  * which element is the head.
126  *
127  * The lifetime of all IOBufs in the chain are linked: when one element in the
128  * chain is deleted, all other chained elements are also deleted.  Conceptually
129  * it is simplest to treat this as if the head of the chain owns all other
130  * IOBufs in the chain.  When you delete the head of the chain, it will delete
131  * the other elements as well.  For this reason, prependChain() and
132  * appendChain() take ownership of of the new elements being added to this
133  * chain.
134  *
135  * When the coalesce() method is used to coalesce an entire IOBuf chain into a
136  * single IOBuf, all other IOBufs in the chain are eliminated and automatically
137  * deleted.  The unshare() method may coalesce the chain; if it does it will
138  * similarly delete all IOBufs eliminated from the chain.
139  *
140  * As discussed in the following section, it is up to the user to maintain a
141  * lock around the entire IOBuf chain if multiple threads need to access the
142  * chain.  IOBuf does not provide any internal locking.
143  *
144  *
145  * Synchronization
146  * ---------------
147  *
148  * When used in multithread programs, a single IOBuf object should only be used
149  * in a single thread at a time.  If a caller uses a single IOBuf across
150  * multiple threads the caller is responsible for using an external lock to
151  * synchronize access to the IOBuf.
152  *
153  * Two separate IOBuf objects may be accessed concurrently in separate threads
154  * without locking, even if they point to the same underlying buffer.  The
155  * buffer reference count is always accessed atomically, and no other
156  * operations should affect other IOBufs that point to the same data segment.
157  * The caller is responsible for using unshare() to ensure that the data buffer
158  * is not shared by other IOBufs before writing to it, and this ensures that
159  * the data itself is not modified in one thread while also being accessed from
160  * another thread.
161  *
162  * For IOBuf chains, no two IOBufs in the same chain should be accessed
163  * simultaneously in separate threads.  The caller must maintain a lock around
164  * the entire chain if the chain, or individual IOBufs in the chain, may be
165  * accessed by multiple threads.
166  *
167  *
168  * IOBuf Object Allocation
169  * -----------------------
170  *
171  * IOBuf objects themselves exist separately from the data buffer they point
172  * to.  Therefore one must also consider how to allocate and manage the IOBuf
173  * objects.
174  *
175  * It is more common to allocate IOBuf objects on the heap, using the create(),
176  * takeOwnership(), or wrapBuffer() factory functions.  The clone()/cloneOne()
177  * functions also return new heap-allocated IOBufs.  The createCombined()
178  * function allocates the IOBuf object and data storage space together, in a
179  * single memory allocation.  This can improve performance, particularly if you
180  * know that the data buffer and the IOBuf itself will have similar lifetimes.
181  *
182  * That said, it is also possible to allocate IOBufs on the stack or inline
183  * inside another object as well.  This is useful for cases where the IOBuf is
184  * short-lived, or when the overhead of allocating the IOBuf on the heap is
185  * undesirable.
186  *
187  * However, note that stack-allocated IOBufs may only be used as the head of a
188  * chain (or standalone as the only IOBuf in a chain).  All non-head members of
189  * an IOBuf chain must be heap allocated.  (All functions to add nodes to a
190  * chain require a std::unique_ptr<IOBuf>, which enforces this requrement.)
191  *
192  * Additionally, no copy-constructor or assignment operator currently exists,
193  * so stack-allocated IOBufs may only be moved, not copied.  (Technically
194  * nothing is preventing us from adding a copy constructor and assignment
195  * operator.  However, it seems like this would add the possibility for some
196  * confusion.  We would need to determine if these functions would copy just a
197  * single buffer, or the entire chain.)
198  *
199  *
200  * IOBuf Sharing
201  * -------------
202  *
203  * The IOBuf class manages sharing of the underlying buffer that it points to,
204  * maintaining a reference count if multiple IOBufs are pointing at the same
205  * buffer.
206  *
207  * However, it is the callers responsibility to manage sharing and ownership of
208  * IOBuf objects themselves.  The IOBuf structure does not provide room for an
209  * intrusive refcount on the IOBuf object itself, only the underlying data
210  * buffer is reference counted.  If users want to share the same IOBuf object
211  * between multiple parts of the code, they are responsible for managing this
212  * sharing on their own.  (For example, by using a shared_ptr.  Alternatively,
213  * users always have the option of using clone() to create a second IOBuf that
214  * points to the same underlying buffer.)
215  */
216 namespace detail {
217 // Is T a unique_ptr<> to a standard-layout type?
218 template <class T, class Enable=void> struct IsUniquePtrToSL
219   : public std::false_type { };
220 template <class T, class D>
221 struct IsUniquePtrToSL<
222   std::unique_ptr<T, D>,
223   typename std::enable_if<std::is_standard_layout<T>::value>::type>
224   : public std::true_type { };
225 }  // namespace detail
226
227 class IOBuf {
228  public:
229   class Iterator;
230
231   enum CreateOp { CREATE };
232   enum WrapBufferOp { WRAP_BUFFER };
233   enum TakeOwnershipOp { TAKE_OWNERSHIP };
234   enum CopyBufferOp { COPY_BUFFER };
235
236   typedef ByteRange value_type;
237   typedef Iterator iterator;
238   typedef Iterator const_iterator;
239
240   typedef void (*FreeFunction)(void* buf, void* userData);
241
242   /**
243    * Allocate a new IOBuf object with the requested capacity.
244    *
245    * Returns a new IOBuf object that must be (eventually) deleted by the
246    * caller.  The returned IOBuf may actually have slightly more capacity than
247    * requested.
248    *
249    * The data pointer will initially point to the start of the newly allocated
250    * buffer, and will have a data length of 0.
251    *
252    * Throws std::bad_alloc on error.
253    */
254   static std::unique_ptr<IOBuf> create(uint64_t capacity);
255   IOBuf(CreateOp, uint64_t capacity);
256
257   /**
258    * Create a new IOBuf, using a single memory allocation to allocate space
259    * for both the IOBuf object and the data storage space.
260    *
261    * This saves one memory allocation.  However, it can be wasteful if you
262    * later need to grow the buffer using reserve().  If the buffer needs to be
263    * reallocated, the space originally allocated will not be freed() until the
264    * IOBuf object itself is also freed.  (It can also be slightly wasteful in
265    * some cases where you clone this IOBuf and then free the original IOBuf.)
266    */
267   static std::unique_ptr<IOBuf> createCombined(uint64_t capacity);
268
269   /**
270    * Create a new IOBuf, using separate memory allocations for the IOBuf object
271    * for the IOBuf and the data storage space.
272    *
273    * This requires two memory allocations, but saves space in the long run
274    * if you know that you will need to reallocate the data buffer later.
275    */
276   static std::unique_ptr<IOBuf> createSeparate(uint64_t capacity);
277
278   /**
279    * Allocate a new IOBuf chain with the requested total capacity, allocating
280    * no more than maxBufCapacity to each buffer.
281    */
282   static std::unique_ptr<IOBuf> createChain(
283       size_t totalCapacity, uint64_t maxBufCapacity);
284
285   /**
286    * Create a new IOBuf pointing to an existing data buffer.
287    *
288    * The new IOBuffer will assume ownership of the buffer, and free it by
289    * calling the specified FreeFunction when the last IOBuf pointing to this
290    * buffer is destroyed.  The function will be called with a pointer to the
291    * buffer as the first argument, and the supplied userData value as the
292    * second argument.  The free function must never throw exceptions.
293    *
294    * If no FreeFunction is specified, the buffer will be freed using free()
295    * which will result in undefined behavior if the memory was allocated
296    * using 'new'.
297    *
298    * The IOBuf data pointer will initially point to the start of the buffer,
299    *
300    * In the first version of this function, the length of data is unspecified
301    * and is initialized to the capacity of the buffer
302    *
303    * In the second version, the user specifies the valid length of data
304    * in the buffer
305    *
306    * On error, std::bad_alloc will be thrown.  If freeOnError is true (the
307    * default) the buffer will be freed before throwing the error.
308    */
309   static std::unique_ptr<IOBuf> takeOwnership(void* buf, uint64_t capacity,
310                                               FreeFunction freeFn = nullptr,
311                                               void* userData = nullptr,
312                                               bool freeOnError = true) {
313     return takeOwnership(buf, capacity, capacity, freeFn,
314                          userData, freeOnError);
315   }
316   IOBuf(TakeOwnershipOp op, void* buf, uint64_t capacity,
317         FreeFunction freeFn = nullptr, void* userData = nullptr,
318         bool freeOnError = true)
319     : IOBuf(op, buf, capacity, capacity, freeFn, userData, freeOnError) {}
320
321   static std::unique_ptr<IOBuf> takeOwnership(void* buf, uint64_t capacity,
322                                               uint64_t length,
323                                               FreeFunction freeFn = nullptr,
324                                               void* userData = nullptr,
325                                               bool freeOnError = true);
326   IOBuf(TakeOwnershipOp, void* buf, uint64_t capacity, uint64_t length,
327         FreeFunction freeFn = nullptr, void* userData = nullptr,
328         bool freeOnError = true);
329
330   /**
331    * Create a new IOBuf pointing to an existing data buffer made up of
332    * count objects of a given standard-layout type.
333    *
334    * This is dangerous -- it is essentially equivalent to doing
335    * reinterpret_cast<unsigned char*> on your data -- but it's often useful
336    * for serialization / deserialization.
337    *
338    * The new IOBuffer will assume ownership of the buffer, and free it
339    * appropriately (by calling the UniquePtr's custom deleter, or by calling
340    * delete or delete[] appropriately if there is no custom deleter)
341    * when the buffer is destroyed.  The custom deleter, if any, must never
342    * throw exceptions.
343    *
344    * The IOBuf data pointer will initially point to the start of the buffer,
345    * and the length will be the full capacity of the buffer (count *
346    * sizeof(T)).
347    *
348    * On error, std::bad_alloc will be thrown, and the buffer will be freed
349    * before throwing the error.
350    */
351   template <class UniquePtr>
352   static typename std::enable_if<detail::IsUniquePtrToSL<UniquePtr>::value,
353                                  std::unique_ptr<IOBuf>>::type
354   takeOwnership(UniquePtr&& buf, size_t count=1);
355
356   /**
357    * Create a new IOBuf object that points to an existing user-owned buffer.
358    *
359    * This should only be used when the caller knows the lifetime of the IOBuf
360    * object ahead of time and can ensure that all IOBuf objects that will point
361    * to this buffer will be destroyed before the buffer itself is destroyed.
362    *
363    * This buffer will not be freed automatically when the last IOBuf
364    * referencing it is destroyed.  It is the caller's responsibility to free
365    * the buffer after the last IOBuf has been destroyed.
366    *
367    * The IOBuf data pointer will initially point to the start of the buffer,
368    * and the length will be the full capacity of the buffer.
369    *
370    * An IOBuf created using wrapBuffer() will always be reported as shared.
371    * unshare() may be used to create a writable copy of the buffer.
372    *
373    * On error, std::bad_alloc will be thrown.
374    */
375   static std::unique_ptr<IOBuf> wrapBuffer(const void* buf, uint64_t capacity);
376   static std::unique_ptr<IOBuf> wrapBuffer(ByteRange br) {
377     return wrapBuffer(br.data(), br.size());
378   }
379   IOBuf(WrapBufferOp op, const void* buf, uint64_t capacity);
380   IOBuf(WrapBufferOp op, ByteRange br);
381
382   /**
383    * Convenience function to create a new IOBuf object that copies data from a
384    * user-supplied buffer, optionally allocating a given amount of
385    * headroom and tailroom.
386    */
387   static std::unique_ptr<IOBuf> copyBuffer(const void* buf, uint64_t size,
388                                            uint64_t headroom=0,
389                                            uint64_t minTailroom=0);
390   static std::unique_ptr<IOBuf> copyBuffer(ByteRange br,
391                                            uint64_t headroom=0,
392                                            uint64_t minTailroom=0) {
393     return copyBuffer(br.data(), br.size(), headroom, minTailroom);
394   }
395   IOBuf(CopyBufferOp op, const void* buf, uint64_t size,
396         uint64_t headroom=0, uint64_t minTailroom=0);
397   IOBuf(CopyBufferOp op, ByteRange br,
398         uint64_t headroom=0, uint64_t minTailroom=0);
399
400   /**
401    * Convenience function to create a new IOBuf object that copies data from a
402    * user-supplied string, optionally allocating a given amount of
403    * headroom and tailroom.
404    *
405    * Beware when attempting to invoke this function with a constant string
406    * literal and a headroom argument: you will likely end up invoking the
407    * version of copyBuffer() above.  IOBuf::copyBuffer("hello", 3) will treat
408    * the first argument as a const void*, and will invoke the version of
409    * copyBuffer() above, with the size argument of 3.
410    */
411   static std::unique_ptr<IOBuf> copyBuffer(const std::string& buf,
412                                            uint64_t headroom=0,
413                                            uint64_t minTailroom=0);
414   IOBuf(CopyBufferOp op, const std::string& buf,
415         uint64_t headroom=0, uint64_t minTailroom=0)
416     : IOBuf(op, buf.data(), buf.size(), headroom, minTailroom) {}
417
418   /**
419    * A version of copyBuffer() that returns a null pointer if the input string
420    * is empty.
421    */
422   static std::unique_ptr<IOBuf> maybeCopyBuffer(const std::string& buf,
423                                                 uint64_t headroom=0,
424                                                 uint64_t minTailroom=0);
425
426   /**
427    * Convenience function to free a chain of IOBufs held by a unique_ptr.
428    */
429   static void destroy(std::unique_ptr<IOBuf>&& data) {
430     auto destroyer = std::move(data);
431   }
432
433   /**
434    * Destroy this IOBuf.
435    *
436    * Deleting an IOBuf will automatically destroy all IOBufs in the chain.
437    * (See the comments above regarding the ownership model of IOBuf chains.
438    * All subsequent IOBufs in the chain are considered to be owned by the head
439    * of the chain.  Users should only explicitly delete the head of a chain.)
440    *
441    * When each individual IOBuf is destroyed, it will release its reference
442    * count on the underlying buffer.  If it was the last user of the buffer,
443    * the buffer will be freed.
444    */
445   ~IOBuf();
446
447   /**
448    * Check whether the chain is empty (i.e., whether the IOBufs in the
449    * chain have a total data length of zero).
450    *
451    * This method is semantically equivalent to
452    *   i->computeChainDataLength()==0
453    * but may run faster because it can short-circuit as soon as it
454    * encounters a buffer with length()!=0
455    */
456   bool empty() const;
457
458   /**
459    * Get the pointer to the start of the data.
460    */
461   const uint8_t* data() const {
462     return data_;
463   }
464
465   /**
466    * Get a writable pointer to the start of the data.
467    *
468    * The caller is responsible for calling unshare() first to ensure that it is
469    * actually safe to write to the buffer.
470    */
471   uint8_t* writableData() {
472     return data_;
473   }
474
475   /**
476    * Get the pointer to the end of the data.
477    */
478   const uint8_t* tail() const {
479     return data_ + length_;
480   }
481
482   /**
483    * Get a writable pointer to the end of the data.
484    *
485    * The caller is responsible for calling unshare() first to ensure that it is
486    * actually safe to write to the buffer.
487    */
488   uint8_t* writableTail() {
489     return data_ + length_;
490   }
491
492   /**
493    * Get the data length.
494    */
495   uint64_t length() const {
496     return length_;
497   }
498
499   /**
500    * Get the amount of head room.
501    *
502    * Returns the number of bytes in the buffer before the start of the data.
503    */
504   uint64_t headroom() const {
505     return data_ - buffer();
506   }
507
508   /**
509    * Get the amount of tail room.
510    *
511    * Returns the number of bytes in the buffer after the end of the data.
512    */
513   uint64_t tailroom() const {
514     return bufferEnd() - tail();
515   }
516
517   /**
518    * Get the pointer to the start of the buffer.
519    *
520    * Note that this is the pointer to the very beginning of the usable buffer,
521    * not the start of valid data within the buffer.  Use the data() method to
522    * get a pointer to the start of the data within the buffer.
523    */
524   const uint8_t* buffer() const {
525     return buf_;
526   }
527
528   /**
529    * Get a writable pointer to the start of the buffer.
530    *
531    * The caller is responsible for calling unshare() first to ensure that it is
532    * actually safe to write to the buffer.
533    */
534   uint8_t* writableBuffer() {
535     return buf_;
536   }
537
538   /**
539    * Get the pointer to the end of the buffer.
540    *
541    * Note that this is the pointer to the very end of the usable buffer,
542    * not the end of valid data within the buffer.  Use the tail() method to
543    * get a pointer to the end of the data within the buffer.
544    */
545   const uint8_t* bufferEnd() const {
546     return buf_ + capacity_;
547   }
548
549   /**
550    * Get the total size of the buffer.
551    *
552    * This returns the total usable length of the buffer.  Use the length()
553    * method to get the length of the actual valid data in this IOBuf.
554    */
555   uint64_t capacity() const {
556     return capacity_;
557   }
558
559   /**
560    * Get a pointer to the next IOBuf in this chain.
561    */
562   IOBuf* next() {
563     return next_;
564   }
565   const IOBuf* next() const {
566     return next_;
567   }
568
569   /**
570    * Get a pointer to the previous IOBuf in this chain.
571    */
572   IOBuf* prev() {
573     return prev_;
574   }
575   const IOBuf* prev() const {
576     return prev_;
577   }
578
579   /**
580    * Shift the data forwards in the buffer.
581    *
582    * This shifts the data pointer forwards in the buffer to increase the
583    * headroom.  This is commonly used to increase the headroom in a newly
584    * allocated buffer.
585    *
586    * The caller is responsible for ensuring that there is sufficient
587    * tailroom in the buffer before calling advance().
588    *
589    * If there is a non-zero data length, advance() will use memmove() to shift
590    * the data forwards in the buffer.  In this case, the caller is responsible
591    * for making sure the buffer is unshared, so it will not affect other IOBufs
592    * that may be sharing the same underlying buffer.
593    */
594   void advance(uint64_t amount) {
595     // In debug builds, assert if there is a problem.
596     assert(amount <= tailroom());
597
598     if (length_ > 0) {
599       memmove(data_ + amount, data_, length_);
600     }
601     data_ += amount;
602   }
603
604   /**
605    * Shift the data backwards in the buffer.
606    *
607    * The caller is responsible for ensuring that there is sufficient headroom
608    * in the buffer before calling retreat().
609    *
610    * If there is a non-zero data length, retreat() will use memmove() to shift
611    * the data backwards in the buffer.  In this case, the caller is responsible
612    * for making sure the buffer is unshared, so it will not affect other IOBufs
613    * that may be sharing the same underlying buffer.
614    */
615   void retreat(uint64_t amount) {
616     // In debug builds, assert if there is a problem.
617     assert(amount <= headroom());
618
619     if (length_ > 0) {
620       memmove(data_ - amount, data_, length_);
621     }
622     data_ -= amount;
623   }
624
625   /**
626    * Adjust the data pointer to include more valid data at the beginning.
627    *
628    * This moves the data pointer backwards to include more of the available
629    * buffer.  The caller is responsible for ensuring that there is sufficient
630    * headroom for the new data.  The caller is also responsible for populating
631    * this section with valid data.
632    *
633    * This does not modify any actual data in the buffer.
634    */
635   void prepend(uint64_t amount) {
636     DCHECK_LE(amount, headroom());
637     data_ -= amount;
638     length_ += amount;
639   }
640
641   /**
642    * Adjust the tail pointer to include more valid data at the end.
643    *
644    * This moves the tail pointer forwards to include more of the available
645    * buffer.  The caller is responsible for ensuring that there is sufficient
646    * tailroom for the new data.  The caller is also responsible for populating
647    * this section with valid data.
648    *
649    * This does not modify any actual data in the buffer.
650    */
651   void append(uint64_t amount) {
652     DCHECK_LE(amount, tailroom());
653     length_ += amount;
654   }
655
656   /**
657    * Adjust the data pointer forwards to include less valid data.
658    *
659    * This moves the data pointer forwards so that the first amount bytes are no
660    * longer considered valid data.  The caller is responsible for ensuring that
661    * amount is less than or equal to the actual data length.
662    *
663    * This does not modify any actual data in the buffer.
664    */
665   void trimStart(uint64_t amount) {
666     DCHECK_LE(amount, length_);
667     data_ += amount;
668     length_ -= amount;
669   }
670
671   /**
672    * Adjust the tail pointer backwards to include less valid data.
673    *
674    * This moves the tail pointer backwards so that the last amount bytes are no
675    * longer considered valid data.  The caller is responsible for ensuring that
676    * amount is less than or equal to the actual data length.
677    *
678    * This does not modify any actual data in the buffer.
679    */
680   void trimEnd(uint64_t amount) {
681     DCHECK_LE(amount, length_);
682     length_ -= amount;
683   }
684
685   /**
686    * Clear the buffer.
687    *
688    * Postcondition: headroom() == 0, length() == 0, tailroom() == capacity()
689    */
690   void clear() {
691     data_ = writableBuffer();
692     length_ = 0;
693   }
694
695   /**
696    * Ensure that this buffer has at least minHeadroom headroom bytes and at
697    * least minTailroom tailroom bytes.  The buffer must be writable
698    * (you must call unshare() before this, if necessary).
699    *
700    * Postcondition: headroom() >= minHeadroom, tailroom() >= minTailroom,
701    * the data (between data() and data() + length()) is preserved.
702    */
703   void reserve(uint64_t minHeadroom, uint64_t minTailroom) {
704     // Maybe we don't need to do anything.
705     if (headroom() >= minHeadroom && tailroom() >= minTailroom) {
706       return;
707     }
708     // If the buffer is empty but we have enough total room (head + tail),
709     // move the data_ pointer around.
710     if (length() == 0 &&
711         headroom() + tailroom() >= minHeadroom + minTailroom) {
712       data_ = writableBuffer() + minHeadroom;
713       return;
714     }
715     // Bah, we have to do actual work.
716     reserveSlow(minHeadroom, minTailroom);
717   }
718
719   /**
720    * Return true if this IOBuf is part of a chain of multiple IOBufs, or false
721    * if this is the only IOBuf in its chain.
722    */
723   bool isChained() const {
724     assert((next_ == this) == (prev_ == this));
725     return next_ != this;
726   }
727
728   /**
729    * Get the number of IOBufs in this chain.
730    *
731    * Beware that this method has to walk the entire chain.
732    * Use isChained() if you just want to check if this IOBuf is part of a chain
733    * or not.
734    */
735   size_t countChainElements() const;
736
737   /**
738    * Get the length of all the data in this IOBuf chain.
739    *
740    * Beware that this method has to walk the entire chain.
741    */
742   uint64_t computeChainDataLength() const;
743
744   /**
745    * Insert another IOBuf chain immediately before this IOBuf.
746    *
747    * For example, if there are two IOBuf chains (A, B, C) and (D, E, F),
748    * and B->prependChain(D) is called, the (D, E, F) chain will be subsumed
749    * and become part of the chain starting at A, which will now look like
750    * (A, D, E, F, B, C)
751    *
752    * Note that since IOBuf chains are circular, head->prependChain(other) can
753    * be used to append the other chain at the very end of the chain pointed to
754    * by head.  For example, if there are two IOBuf chains (A, B, C) and
755    * (D, E, F), and A->prependChain(D) is called, the chain starting at A will
756    * now consist of (A, B, C, D, E, F)
757    *
758    * The elements in the specified IOBuf chain will become part of this chain,
759    * and will be owned by the head of this chain.  When this chain is
760    * destroyed, all elements in the supplied chain will also be destroyed.
761    *
762    * For this reason, appendChain() only accepts an rvalue-reference to a
763    * unique_ptr(), to make it clear that it is taking ownership of the supplied
764    * chain.  If you have a raw pointer, you can pass in a new temporary
765    * unique_ptr around the raw pointer.  If you have an existing,
766    * non-temporary unique_ptr, you must call std::move(ptr) to make it clear
767    * that you are destroying the original pointer.
768    */
769   void prependChain(std::unique_ptr<IOBuf>&& iobuf);
770
771   /**
772    * Append another IOBuf chain immediately after this IOBuf.
773    *
774    * For example, if there are two IOBuf chains (A, B, C) and (D, E, F),
775    * and B->appendChain(D) is called, the (D, E, F) chain will be subsumed
776    * and become part of the chain starting at A, which will now look like
777    * (A, B, D, E, F, C)
778    *
779    * The elements in the specified IOBuf chain will become part of this chain,
780    * and will be owned by the head of this chain.  When this chain is
781    * destroyed, all elements in the supplied chain will also be destroyed.
782    *
783    * For this reason, appendChain() only accepts an rvalue-reference to a
784    * unique_ptr(), to make it clear that it is taking ownership of the supplied
785    * chain.  If you have a raw pointer, you can pass in a new temporary
786    * unique_ptr around the raw pointer.  If you have an existing,
787    * non-temporary unique_ptr, you must call std::move(ptr) to make it clear
788    * that you are destroying the original pointer.
789    */
790   void appendChain(std::unique_ptr<IOBuf>&& iobuf) {
791     // Just use prependChain() on the next element in our chain
792     next_->prependChain(std::move(iobuf));
793   }
794
795   /**
796    * Remove this IOBuf from its current chain.
797    *
798    * Since ownership of all elements an IOBuf chain is normally maintained by
799    * the head of the chain, unlink() transfers ownership of this IOBuf from the
800    * chain and gives it to the caller.  A new unique_ptr to the IOBuf is
801    * returned to the caller.  The caller must store the returned unique_ptr (or
802    * call release() on it) to take ownership, otherwise the IOBuf will be
803    * immediately destroyed.
804    *
805    * Since unlink transfers ownership of the IOBuf to the caller, be careful
806    * not to call unlink() on the head of a chain if you already maintain
807    * ownership on the head of the chain via other means.  The pop() method
808    * is a better choice for that situation.
809    */
810   std::unique_ptr<IOBuf> unlink() {
811     next_->prev_ = prev_;
812     prev_->next_ = next_;
813     prev_ = this;
814     next_ = this;
815     return std::unique_ptr<IOBuf>(this);
816   }
817
818   /**
819    * Remove this IOBuf from its current chain and return a unique_ptr to
820    * the IOBuf that formerly followed it in the chain.
821    */
822   std::unique_ptr<IOBuf> pop() {
823     IOBuf *next = next_;
824     next_->prev_ = prev_;
825     prev_->next_ = next_;
826     prev_ = this;
827     next_ = this;
828     return std::unique_ptr<IOBuf>((next == this) ? nullptr : next);
829   }
830
831   /**
832    * Remove a subchain from this chain.
833    *
834    * Remove the subchain starting at head and ending at tail from this chain.
835    *
836    * Returns a unique_ptr pointing to head.  (In other words, ownership of the
837    * head of the subchain is transferred to the caller.)  If the caller ignores
838    * the return value and lets the unique_ptr be destroyed, the subchain will
839    * be immediately destroyed.
840    *
841    * The subchain referenced by the specified head and tail must be part of the
842    * same chain as the current IOBuf, but must not contain the current IOBuf.
843    * However, the specified head and tail may be equal to each other (i.e.,
844    * they may be a subchain of length 1).
845    */
846   std::unique_ptr<IOBuf> separateChain(IOBuf* head, IOBuf* tail) {
847     assert(head != this);
848     assert(tail != this);
849
850     head->prev_->next_ = tail->next_;
851     tail->next_->prev_ = head->prev_;
852
853     head->prev_ = tail;
854     tail->next_ = head;
855
856     return std::unique_ptr<IOBuf>(head);
857   }
858
859   /**
860    * Return true if at least one of the IOBufs in this chain are shared,
861    * or false if all of the IOBufs point to unique buffers.
862    *
863    * Use isSharedOne() to only check this IOBuf rather than the entire chain.
864    */
865   bool isShared() const {
866     const IOBuf* current = this;
867     while (true) {
868       if (current->isSharedOne()) {
869         return true;
870       }
871       current = current->next_;
872       if (current == this) {
873         return false;
874       }
875     }
876   }
877
878   /**
879    * Return true if other IOBufs are also pointing to the buffer used by this
880    * IOBuf, and false otherwise.
881    *
882    * If this IOBuf points at a buffer owned by another (non-IOBuf) part of the
883    * code (i.e., if the IOBuf was created using wrapBuffer(), or was cloned
884    * from such an IOBuf), it is always considered shared.
885    *
886    * This only checks the current IOBuf, and not other IOBufs in the chain.
887    */
888   bool isSharedOne() const {
889     // If this is a user-owned buffer, it is always considered shared
890     if (UNLIKELY(!sharedInfo())) {
891       return true;
892     }
893
894     if (LIKELY(!(flags() & kFlagMaybeShared))) {
895       return false;
896     }
897
898     // kFlagMaybeShared is set, so we need to check the reference count.
899     // (Checking the reference count requires an atomic operation, which is why
900     // we prefer to only check kFlagMaybeShared if possible.)
901     bool shared = sharedInfo()->refcount.load(std::memory_order_acquire) > 1;
902     if (!shared) {
903       // we're the last one left
904       clearFlags(kFlagMaybeShared);
905     }
906     return shared;
907   }
908
909   /**
910    * Ensure that this IOBuf has a unique buffer that is not shared by other
911    * IOBufs.
912    *
913    * unshare() operates on an entire chain of IOBuf objects.  If the chain is
914    * shared, it may also coalesce the chain when making it unique.  If the
915    * chain is coalesced, subsequent IOBuf objects in the current chain will be
916    * automatically deleted.
917    *
918    * Note that buffers owned by other (non-IOBuf) users are automatically
919    * considered shared.
920    *
921    * Throws std::bad_alloc on error.  On error the IOBuf chain will be
922    * unmodified.
923    *
924    * Currently unshare may also throw std::overflow_error if it tries to
925    * coalesce.  (TODO: In the future it would be nice if unshare() were smart
926    * enough not to coalesce the entire buffer if the data is too large.
927    * However, in practice this seems unlikely to become an issue.)
928    */
929   void unshare() {
930     if (isChained()) {
931       unshareChained();
932     } else {
933       unshareOne();
934     }
935   }
936
937   /**
938    * Ensure that this IOBuf has a unique buffer that is not shared by other
939    * IOBufs.
940    *
941    * unshareOne() operates on a single IOBuf object.  This IOBuf will have a
942    * unique buffer after unshareOne() returns, but other IOBufs in the chain
943    * may still be shared after unshareOne() returns.
944    *
945    * Throws std::bad_alloc on error.  On error the IOBuf will be unmodified.
946    */
947   void unshareOne() {
948     if (isSharedOne()) {
949       unshareOneSlow();
950     }
951   }
952
953   /**
954    * Coalesce this IOBuf chain into a single buffer.
955    *
956    * This method moves all of the data in this IOBuf chain into a single
957    * contiguous buffer, if it is not already in one buffer.  After coalesce()
958    * returns, this IOBuf will be a chain of length one.  Other IOBufs in the
959    * chain will be automatically deleted.
960    *
961    * After coalescing, the IOBuf will have at least as much headroom as the
962    * first IOBuf in the chain, and at least as much tailroom as the last IOBuf
963    * in the chain.
964    *
965    * Throws std::bad_alloc on error.  On error the IOBuf chain will be
966    * unmodified.
967    *
968    * Returns ByteRange that points to the data IOBuf stores.
969    */
970   ByteRange coalesce() {
971     if (isChained()) {
972       coalesceSlow();
973     }
974     return ByteRange(data_, length_);
975   }
976
977   /**
978    * Ensure that this chain has at least maxLength bytes available as a
979    * contiguous memory range.
980    *
981    * This method coalesces whole buffers in the chain into this buffer as
982    * necessary until this buffer's length() is at least maxLength.
983    *
984    * After coalescing, the IOBuf will have at least as much headroom as the
985    * first IOBuf in the chain, and at least as much tailroom as the last IOBuf
986    * that was coalesced.
987    *
988    * Throws std::bad_alloc or std::overflow_error on error.  On error the IOBuf
989    * chain will be unmodified.  Throws std::overflow_error if maxLength is
990    * longer than the total chain length.
991    *
992    * Upon return, either enough of the chain was coalesced into a contiguous
993    * region, or the entire chain was coalesced.  That is,
994    * length() >= maxLength || !isChained() is true.
995    */
996   void gather(uint64_t maxLength) {
997     if (!isChained() || length_ >= maxLength) {
998       return;
999     }
1000     coalesceSlow(maxLength);
1001   }
1002
1003   /**
1004    * Return a new IOBuf chain sharing the same data as this chain.
1005    *
1006    * The new IOBuf chain will normally point to the same underlying data
1007    * buffers as the original chain.  (The one exception to this is if some of
1008    * the IOBufs in this chain contain small internal data buffers which cannot
1009    * be shared.)
1010    */
1011   std::unique_ptr<IOBuf> clone() const;
1012
1013   /**
1014    * Return a new IOBuf with the same data as this IOBuf.
1015    *
1016    * The new IOBuf returned will not be part of a chain (even if this IOBuf is
1017    * part of a larger chain).
1018    */
1019   std::unique_ptr<IOBuf> cloneOne() const;
1020
1021   /**
1022    * Similar to Clone(). But use other as the head node. Other nodes in the
1023    * chain (if any) will be allocted on heap.
1024    */
1025   void cloneInto(IOBuf& other) const;
1026
1027   /**
1028    * Similar to CloneOne(). But to fill an existing IOBuf instead of a new
1029    * IOBuf.
1030    */
1031   void cloneOneInto(IOBuf& other) const;
1032
1033   /**
1034    * Return an iovector suitable for e.g. writev()
1035    *
1036    *   auto iov = buf->getIov();
1037    *   auto xfer = writev(fd, iov.data(), iov.size());
1038    *
1039    * Naturally, the returned iovector is invalid if you modify the buffer
1040    * chain.
1041    */
1042   folly::fbvector<struct iovec> getIov() const;
1043
1044   /*
1045    * Overridden operator new and delete.
1046    * These perform specialized memory management to help support
1047    * createCombined(), which allocates IOBuf objects together with the buffer
1048    * data.
1049    */
1050   void* operator new(size_t size);
1051   void* operator new(size_t size, void* ptr);
1052   void operator delete(void* ptr);
1053
1054   /**
1055    * Destructively convert this IOBuf to a fbstring efficiently.
1056    * We rely on fbstring's AcquireMallocatedString constructor to
1057    * transfer memory.
1058    */
1059   fbstring moveToFbString();
1060
1061   /**
1062    * Iteration support: a chain of IOBufs may be iterated through using
1063    * STL-style iterators over const ByteRanges.  Iterators are only invalidated
1064    * if the IOBuf that they currently point to is removed.
1065    */
1066   Iterator cbegin() const;
1067   Iterator cend() const;
1068   Iterator begin() const;
1069   Iterator end() const;
1070
1071   /**
1072    * Allocate a new null buffer.
1073    *
1074    * This can be used to allocate an empty IOBuf on the stack.  It will have no
1075    * space allocated for it.  This is generally useful only to later use move
1076    * assignment to fill out the IOBuf.
1077    */
1078   IOBuf() noexcept;
1079
1080   /**
1081    * Move constructor and assignment operator.
1082    *
1083    * In general, you should only ever move the head of an IOBuf chain.
1084    * Internal nodes in an IOBuf chain are owned by the head of the chain, and
1085    * should not be moved from.  (Technically, nothing prevents you from moving
1086    * a non-head node, but the moved-to node will replace the moved-from node in
1087    * the chain.  This has implications for ownership, since non-head nodes are
1088    * owned by the chain head.  You are then responsible for relinquishing
1089    * ownership of the moved-to node, and manually deleting the moved-from
1090    * node.)
1091    *
1092    * With the move assignment operator, the destination of the move should be
1093    * the head of an IOBuf chain or a solitary IOBuf not part of a chain.  If
1094    * the move destination is part of a chain, all other IOBufs in the chain
1095    * will be deleted.
1096    *
1097    * (We currently don't provide a copy constructor or assignment operator.
1098    * The main reason is because it is not clear these operations should copy
1099    * the entire chain or just the single IOBuf.)
1100    */
1101   IOBuf(IOBuf&& other) noexcept;
1102   IOBuf& operator=(IOBuf&& other) noexcept;
1103
1104  private:
1105   enum FlagsEnum : uintptr_t {
1106     // Adding any more flags would not work on 32-bit architectures,
1107     // as these flags are stashed in the least significant 2 bits of a
1108     // max-align-aligned pointer.
1109     kFlagFreeSharedInfo = 0x1,
1110     kFlagMaybeShared = 0x2,
1111     kFlagMask = kFlagFreeSharedInfo | kFlagMaybeShared
1112   };
1113
1114   struct SharedInfo {
1115     SharedInfo();
1116     SharedInfo(FreeFunction fn, void* arg);
1117
1118     // A pointer to a function to call to free the buffer when the refcount
1119     // hits 0.  If this is null, free() will be used instead.
1120     FreeFunction freeFn;
1121     void* userData;
1122     std::atomic<uint32_t> refcount;
1123   };
1124   // Helper structs for use by operator new and delete
1125   struct HeapPrefix;
1126   struct HeapStorage;
1127   struct HeapFullStorage;
1128
1129   // Forbidden copy constructor and assignment opererator
1130   IOBuf(IOBuf const &);
1131   IOBuf& operator=(IOBuf const &);
1132
1133   /**
1134    * Create a new IOBuf pointing to an external buffer.
1135    *
1136    * The caller is responsible for holding a reference count for this new
1137    * IOBuf.  The IOBuf constructor does not automatically increment the
1138    * reference count.
1139    */
1140   struct InternalConstructor {};  // avoid conflicts
1141   IOBuf(InternalConstructor, uintptr_t flagsAndSharedInfo,
1142         uint8_t* buf, uint64_t capacity,
1143         uint8_t* data, uint64_t length);
1144
1145   void unshareOneSlow();
1146   void unshareChained();
1147   void coalesceSlow();
1148   void coalesceSlow(size_t maxLength);
1149   // newLength must be the entire length of the buffers between this and
1150   // end (no truncation)
1151   void coalesceAndReallocate(
1152       size_t newHeadroom,
1153       size_t newLength,
1154       IOBuf* end,
1155       size_t newTailroom);
1156   void coalesceAndReallocate(size_t newLength, IOBuf* end) {
1157     coalesceAndReallocate(headroom(), newLength, end, end->prev_->tailroom());
1158   }
1159   void decrementRefcount();
1160   void reserveSlow(uint64_t minHeadroom, uint64_t minTailroom);
1161   void freeExtBuffer();
1162
1163   static size_t goodExtBufferSize(uint64_t minCapacity);
1164   static void initExtBuffer(uint8_t* buf, size_t mallocSize,
1165                             SharedInfo** infoReturn,
1166                             uint64_t* capacityReturn);
1167   static void allocExtBuffer(uint64_t minCapacity,
1168                              uint8_t** bufReturn,
1169                              SharedInfo** infoReturn,
1170                              uint64_t* capacityReturn);
1171   static void releaseStorage(HeapStorage* storage, uint16_t freeFlags);
1172   static void freeInternalBuf(void* buf, void* userData);
1173
1174   /*
1175    * Member variables
1176    */
1177
1178   /*
1179    * Links to the next and the previous IOBuf in this chain.
1180    *
1181    * The chain is circularly linked (the last element in the chain points back
1182    * at the head), and next_ and prev_ can never be null.  If this IOBuf is the
1183    * only element in the chain, next_ and prev_ will both point to this.
1184    */
1185   IOBuf* next_{this};
1186   IOBuf* prev_{this};
1187
1188   /*
1189    * A pointer to the start of the data referenced by this IOBuf, and the
1190    * length of the data.
1191    *
1192    * This may refer to any subsection of the actual buffer capacity.
1193    */
1194   uint8_t* data_{nullptr};
1195   uint8_t* buf_{nullptr};
1196   uint64_t length_{0};
1197   uint64_t capacity_{0};
1198
1199   // Pack flags in least significant 2 bits, sharedInfo in the rest
1200   mutable uintptr_t flagsAndSharedInfo_{0};
1201
1202   static inline uintptr_t packFlagsAndSharedInfo(uintptr_t flags,
1203                                                  SharedInfo* info) {
1204     uintptr_t uinfo = reinterpret_cast<uintptr_t>(info);
1205     DCHECK_EQ(flags & ~kFlagMask, 0);
1206     DCHECK_EQ(uinfo & kFlagMask, 0);
1207     return flags | uinfo;
1208   }
1209
1210   inline SharedInfo* sharedInfo() const {
1211     return reinterpret_cast<SharedInfo*>(flagsAndSharedInfo_ & ~kFlagMask);
1212   }
1213
1214   inline void setSharedInfo(SharedInfo* info) {
1215     uintptr_t uinfo = reinterpret_cast<uintptr_t>(info);
1216     DCHECK_EQ(uinfo & kFlagMask, 0);
1217     flagsAndSharedInfo_ = (flagsAndSharedInfo_ & kFlagMask) | uinfo;
1218   }
1219
1220   inline uintptr_t flags() const {
1221     return flagsAndSharedInfo_ & kFlagMask;
1222   }
1223
1224   // flags_ are changed from const methods
1225   inline void setFlags(uintptr_t flags) const {
1226     DCHECK_EQ(flags & ~kFlagMask, 0);
1227     flagsAndSharedInfo_ |= flags;
1228   }
1229
1230   inline void clearFlags(uintptr_t flags) const {
1231     DCHECK_EQ(flags & ~kFlagMask, 0);
1232     flagsAndSharedInfo_ &= ~flags;
1233   }
1234
1235   inline void setFlagsAndSharedInfo(uintptr_t flags, SharedInfo* info) {
1236     flagsAndSharedInfo_ = packFlagsAndSharedInfo(flags, info);
1237   }
1238
1239   struct DeleterBase {
1240     virtual ~DeleterBase() { }
1241     virtual void dispose(void* p) = 0;
1242   };
1243
1244   template <class UniquePtr>
1245   struct UniquePtrDeleter : public DeleterBase {
1246     typedef typename UniquePtr::pointer Pointer;
1247     typedef typename UniquePtr::deleter_type Deleter;
1248
1249     explicit UniquePtrDeleter(Deleter deleter) : deleter_(std::move(deleter)){ }
1250     void dispose(void* p) {
1251       try {
1252         deleter_(static_cast<Pointer>(p));
1253         delete this;
1254       } catch (...) {
1255         abort();
1256       }
1257     }
1258
1259    private:
1260     Deleter deleter_;
1261   };
1262
1263   static void freeUniquePtrBuffer(void* ptr, void* userData) {
1264     static_cast<DeleterBase*>(userData)->dispose(ptr);
1265   }
1266 };
1267
1268 /**
1269  * Hasher for IOBuf objects. Hashes the entire chain using SpookyHashV2.
1270  */
1271 struct IOBufHash {
1272   size_t operator()(const IOBuf& buf) const;
1273   size_t operator()(const std::unique_ptr<IOBuf>& buf) const {
1274     return buf ? (*this)(*buf) : 0;
1275   }
1276 };
1277
1278 /**
1279  * Equality predicate for IOBuf objects. Compares data in the entire chain.
1280  */
1281 struct IOBufEqual {
1282   bool operator()(const IOBuf& a, const IOBuf& b) const;
1283   bool operator()(const std::unique_ptr<IOBuf>& a,
1284                   const std::unique_ptr<IOBuf>& b) const {
1285     if (!a && !b) {
1286       return true;
1287     } else if (!a || !b) {
1288       return false;
1289     } else {
1290       return (*this)(*a, *b);
1291     }
1292   }
1293 };
1294
1295 template <class UniquePtr>
1296 typename std::enable_if<detail::IsUniquePtrToSL<UniquePtr>::value,
1297                         std::unique_ptr<IOBuf>>::type
1298 IOBuf::takeOwnership(UniquePtr&& buf, size_t count) {
1299   size_t size = count * sizeof(typename UniquePtr::element_type);
1300   auto deleter = new UniquePtrDeleter<UniquePtr>(buf.get_deleter());
1301   return takeOwnership(buf.release(),
1302                        size,
1303                        &IOBuf::freeUniquePtrBuffer,
1304                        deleter);
1305 }
1306
1307 inline std::unique_ptr<IOBuf> IOBuf::copyBuffer(
1308     const void* data, uint64_t size, uint64_t headroom,
1309     uint64_t minTailroom) {
1310   uint64_t capacity = headroom + size + minTailroom;
1311   std::unique_ptr<IOBuf> buf = create(capacity);
1312   buf->advance(headroom);
1313   memcpy(buf->writableData(), data, size);
1314   buf->append(size);
1315   return buf;
1316 }
1317
1318 inline std::unique_ptr<IOBuf> IOBuf::copyBuffer(const std::string& buf,
1319                                                 uint64_t headroom,
1320                                                 uint64_t minTailroom) {
1321   return copyBuffer(buf.data(), buf.size(), headroom, minTailroom);
1322 }
1323
1324 inline std::unique_ptr<IOBuf> IOBuf::maybeCopyBuffer(const std::string& buf,
1325                                                      uint64_t headroom,
1326                                                      uint64_t minTailroom) {
1327   if (buf.empty()) {
1328     return nullptr;
1329   }
1330   return copyBuffer(buf.data(), buf.size(), headroom, minTailroom);
1331 }
1332
1333 class IOBuf::Iterator : public boost::iterator_facade<
1334     IOBuf::Iterator,  // Derived
1335     const ByteRange,  // Value
1336     boost::forward_traversal_tag  // Category or traversal
1337   > {
1338   friend class boost::iterator_core_access;
1339  public:
1340   // Note that IOBufs are stored as a circular list without a guard node,
1341   // so pos == end is ambiguous (it may mean "begin" or "end").  To solve
1342   // the ambiguity (at the cost of one extra comparison in the "increment"
1343   // code path), we define end iterators as having pos_ == end_ == nullptr
1344   // and we only allow forward iteration.
1345   explicit Iterator(const IOBuf* pos, const IOBuf* end)
1346     : pos_(pos),
1347       end_(end) {
1348     // Sadly, we must return by const reference, not by value.
1349     if (pos_) {
1350       setVal();
1351     }
1352   }
1353
1354  private:
1355   void setVal() {
1356     val_ = ByteRange(pos_->data(), pos_->tail());
1357   }
1358
1359   void adjustForEnd() {
1360     if (pos_ == end_) {
1361       pos_ = end_ = nullptr;
1362       val_ = ByteRange();
1363     } else {
1364       setVal();
1365     }
1366   }
1367
1368   const ByteRange& dereference() const {
1369     return val_;
1370   }
1371
1372   bool equal(const Iterator& other) const {
1373     // We must compare end_ in addition to pos_, because forward traversal
1374     // requires that if two iterators are equal (a == b) and dereferenceable,
1375     // then ++a == ++b.
1376     return pos_ == other.pos_ && end_ == other.end_;
1377   }
1378
1379   void increment() {
1380     pos_ = pos_->next();
1381     adjustForEnd();
1382   }
1383
1384   const IOBuf* pos_;
1385   const IOBuf* end_;
1386   ByteRange val_;
1387 };
1388
1389 inline IOBuf::Iterator IOBuf::begin() const { return cbegin(); }
1390 inline IOBuf::Iterator IOBuf::end() const { return cend(); }
1391
1392 } // folly
1393
1394 #pragma GCC diagnostic pop
1395
1396 #endif // FOLLY_IO_IOBUF_H_