change the mechanism for "internal" buffer storage
[folly.git] / folly / io / IOBuf.h
1 /*
2  * Copyright 2013 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/Sharing
169  * -------------------------------
170  *
171  * IOBuf objects themselves are always allocated on the heap.  The IOBuf
172  * constructors are private, so IOBuf objects may not be created on the stack.
173  * In part this is done since some IOBuf objects use small-buffer optimization
174  * and contain the buffer data immediately after the IOBuf object itself.  The
175  * coalesce() and unshare() methods also expect to be able to delete subsequent
176  * IOBuf objects in the chain if they are no longer needed due to coalescing.
177  *
178  * The IOBuf structure also does not provide room for an intrusive refcount on
179  * the IOBuf object itself, only the underlying data buffer is reference
180  * counted.  If users want to share the same IOBuf object between multiple
181  * parts of the code, they are responsible for managing this sharing on their
182  * own.  (For example, by using a shared_ptr.  Alternatively, users always have
183  * the option of using clone() to create a second IOBuf that points to the same
184  * underlying buffer.)
185  *
186  * With jemalloc, allocating small objects like IOBuf objects should be
187  * relatively fast, and the cost of allocating IOBuf objects on the heap and
188  * cloning new IOBufs should be relatively cheap.
189  */
190 namespace detail {
191 // Is T a unique_ptr<> to a standard-layout type?
192 template <class T, class Enable=void> struct IsUniquePtrToSL
193   : public std::false_type { };
194 template <class T, class D>
195 struct IsUniquePtrToSL<
196   std::unique_ptr<T, D>,
197   typename std::enable_if<std::is_standard_layout<T>::value>::type>
198   : public std::true_type { };
199 }  // namespace detail
200
201 class IOBuf {
202  public:
203   class Iterator;
204
205   typedef ByteRange value_type;
206   typedef Iterator iterator;
207   typedef Iterator const_iterator;
208
209   typedef void (*FreeFunction)(void* buf, void* userData);
210
211   /**
212    * Allocate a new IOBuf object with the requested capacity.
213    *
214    * Returns a new IOBuf object that must be (eventually) deleted by the
215    * caller.  The returned IOBuf may actually have slightly more capacity than
216    * requested.
217    *
218    * The data pointer will initially point to the start of the newly allocated
219    * buffer, and will have a data length of 0.
220    *
221    * Throws std::bad_alloc on error.
222    */
223   static std::unique_ptr<IOBuf> create(uint32_t capacity);
224
225   /**
226    * Create a new IOBuf, using a single memory allocation to allocate space
227    * for both the IOBuf object and the data storage space.
228    *
229    * This saves one memory allocation.  However, it can be wasteful if you
230    * later need to grow the buffer using reserve().  If the buffer needs to be
231    * reallocated, the space originally allocated will not be freed() until the
232    * IOBuf object itself is also freed.  (It can also be slightly wasteful in
233    * some cases where you clone this IOBuf and then free the original IOBuf.)
234    */
235   static std::unique_ptr<IOBuf> createCombined(uint32_t capacity);
236
237   /**
238    * Create a new IOBuf, using separate memory allocations for the IOBuf object
239    * for the IOBuf and the data storage space.
240    *
241    * This requires two memory allocations, but saves space in the long run
242    * if you know that you will need to reallocate the data buffer later.
243    */
244   static std::unique_ptr<IOBuf> createSeparate(uint32_t capacity);
245
246   /**
247    * Allocate a new IOBuf chain with the requested total capacity, allocating
248    * no more than maxBufCapacity to each buffer.
249    */
250   static std::unique_ptr<IOBuf> createChain(
251       size_t totalCapacity, uint32_t maxBufCapacity);
252
253   /**
254    * Create a new IOBuf pointing to an existing data buffer.
255    *
256    * The new IOBuffer will assume ownership of the buffer, and free it by
257    * calling the specified FreeFunction when the last IOBuf pointing to this
258    * buffer is destroyed.  The function will be called with a pointer to the
259    * buffer as the first argument, and the supplied userData value as the
260    * second argument.  The free function must never throw exceptions.
261    *
262    * If no FreeFunction is specified, the buffer will be freed using free()
263    * which will result in undefined behavior if the memory was allocated
264    * using 'new'.
265    *
266    * The IOBuf data pointer will initially point to the start of the buffer,
267    *
268    * In the first version of this function, the length of data is unspecified
269    * and is initialized to the capacity of the buffer
270    *
271    * In the second version, the user specifies the valid length of data
272    * in the buffer
273    *
274    * On error, std::bad_alloc will be thrown.  If freeOnError is true (the
275    * default) the buffer will be freed before throwing the error.
276    */
277   static std::unique_ptr<IOBuf> takeOwnership(void* buf, uint32_t capacity,
278                                               FreeFunction freeFn = NULL,
279                                               void* userData = NULL,
280                                               bool freeOnError = true) {
281     return takeOwnership(buf, capacity, capacity, freeFn,
282                          userData, freeOnError);
283   }
284
285   static std::unique_ptr<IOBuf> takeOwnership(void* buf, uint32_t capacity,
286                                               uint32_t length,
287                                               FreeFunction freeFn = NULL,
288                                               void* userData = NULL,
289                                               bool freeOnError = true);
290
291   /**
292    * Create a new IOBuf pointing to an existing data buffer made up of
293    * count objects of a given standard-layout type.
294    *
295    * This is dangerous -- it is essentially equivalent to doing
296    * reinterpret_cast<unsigned char*> on your data -- but it's often useful
297    * for serialization / deserialization.
298    *
299    * The new IOBuffer will assume ownership of the buffer, and free it
300    * appropriately (by calling the UniquePtr's custom deleter, or by calling
301    * delete or delete[] appropriately if there is no custom deleter)
302    * when the buffer is destroyed.  The custom deleter, if any, must never
303    * throw exceptions.
304    *
305    * The IOBuf data pointer will initially point to the start of the buffer,
306    * and the length will be the full capacity of the buffer (count *
307    * sizeof(T)).
308    *
309    * On error, std::bad_alloc will be thrown, and the buffer will be freed
310    * before throwing the error.
311    */
312   template <class UniquePtr>
313   static typename std::enable_if<detail::IsUniquePtrToSL<UniquePtr>::value,
314                                  std::unique_ptr<IOBuf>>::type
315   takeOwnership(UniquePtr&& buf, size_t count=1);
316
317   /**
318    * Create a new IOBuf object that points to an existing user-owned buffer.
319    *
320    * This should only be used when the caller knows the lifetime of the IOBuf
321    * object ahead of time and can ensure that all IOBuf objects that will point
322    * to this buffer will be destroyed before the buffer itself is destroyed.
323    *
324    * This buffer will not be freed automatically when the last IOBuf
325    * referencing it is destroyed.  It is the caller's responsibility to free
326    * the buffer after the last IOBuf has been destroyed.
327    *
328    * The IOBuf data pointer will initially point to the start of the buffer,
329    * and the length will be the full capacity of the buffer.
330    *
331    * An IOBuf created using wrapBuffer() will always be reported as shared.
332    * unshare() may be used to create a writable copy of the buffer.
333    *
334    * On error, std::bad_alloc will be thrown.
335    */
336   static std::unique_ptr<IOBuf> wrapBuffer(const void* buf, uint32_t capacity);
337   static std::unique_ptr<IOBuf> wrapBuffer(ByteRange br) {
338     CHECK_LE(br.size(), std::numeric_limits<uint32_t>::max());
339     return wrapBuffer(br.data(), br.size());
340   }
341
342   /**
343    * Convenience function to create a new IOBuf object that copies data from a
344    * user-supplied buffer, optionally allocating a given amount of
345    * headroom and tailroom.
346    */
347   static std::unique_ptr<IOBuf> copyBuffer(const void* buf, uint32_t size,
348                                            uint32_t headroom=0,
349                                            uint32_t minTailroom=0);
350   static std::unique_ptr<IOBuf> copyBuffer(ByteRange br,
351                                            uint32_t headroom=0,
352                                            uint32_t minTailroom=0) {
353     CHECK_LE(br.size(), std::numeric_limits<uint32_t>::max());
354     return copyBuffer(br.data(), br.size(), headroom, minTailroom);
355   }
356
357   /**
358    * Convenience function to create a new IOBuf object that copies data from a
359    * user-supplied string, optionally allocating a given amount of
360    * headroom and tailroom.
361    *
362    * Beware when attempting to invoke this function with a constant string
363    * literal and a headroom argument: you will likely end up invoking the
364    * version of copyBuffer() above.  IOBuf::copyBuffer("hello", 3) will treat
365    * the first argument as a const void*, and will invoke the version of
366    * copyBuffer() above, with the size argument of 3.
367    */
368   static std::unique_ptr<IOBuf> copyBuffer(const std::string& buf,
369                                            uint32_t headroom=0,
370                                            uint32_t minTailroom=0);
371
372   /**
373    * A version of copyBuffer() that returns a null pointer if the input string
374    * is empty.
375    */
376   static std::unique_ptr<IOBuf> maybeCopyBuffer(const std::string& buf,
377                                                 uint32_t headroom=0,
378                                                 uint32_t minTailroom=0);
379
380   /**
381    * Convenience function to free a chain of IOBufs held by a unique_ptr.
382    */
383   static void destroy(std::unique_ptr<IOBuf>&& data) {
384     auto destroyer = std::move(data);
385   }
386
387   /**
388    * Destroy this IOBuf.
389    *
390    * Deleting an IOBuf will automatically destroy all IOBufs in the chain.
391    * (See the comments above regarding the ownership model of IOBuf chains.
392    * All subsequent IOBufs in the chain are considered to be owned by the head
393    * of the chain.  Users should only explicitly delete the head of a chain.)
394    *
395    * When each individual IOBuf is destroyed, it will release its reference
396    * count on the underlying buffer.  If it was the last user of the buffer,
397    * the buffer will be freed.
398    */
399   ~IOBuf();
400
401   /**
402    * Check whether the chain is empty (i.e., whether the IOBufs in the
403    * chain have a total data length of zero).
404    *
405    * This method is semantically equivalent to
406    *   i->computeChainDataLength()==0
407    * but may run faster because it can short-circuit as soon as it
408    * encounters a buffer with length()!=0
409    */
410   bool empty() const;
411
412   /**
413    * Get the pointer to the start of the data.
414    */
415   const uint8_t* data() const {
416     return data_;
417   }
418
419   /**
420    * Get a writable pointer to the start of the data.
421    *
422    * The caller is responsible for calling unshare() first to ensure that it is
423    * actually safe to write to the buffer.
424    */
425   uint8_t* writableData() {
426     return data_;
427   }
428
429   /**
430    * Get the pointer to the end of the data.
431    */
432   const uint8_t* tail() const {
433     return data_ + length_;
434   }
435
436   /**
437    * Get a writable pointer to the end of the data.
438    *
439    * The caller is responsible for calling unshare() first to ensure that it is
440    * actually safe to write to the buffer.
441    */
442   uint8_t* writableTail() {
443     return data_ + length_;
444   }
445
446   /**
447    * Get the data length.
448    */
449   uint32_t length() const {
450     return length_;
451   }
452
453   /**
454    * Get the amount of head room.
455    *
456    * Returns the number of bytes in the buffer before the start of the data.
457    */
458   uint32_t headroom() const {
459     return data_ - buffer();
460   }
461
462   /**
463    * Get the amount of tail room.
464    *
465    * Returns the number of bytes in the buffer after the end of the data.
466    */
467   uint32_t tailroom() const {
468     return bufferEnd() - tail();
469   }
470
471   /**
472    * Get the pointer to the start of the buffer.
473    *
474    * Note that this is the pointer to the very beginning of the usable buffer,
475    * not the start of valid data within the buffer.  Use the data() method to
476    * get a pointer to the start of the data within the buffer.
477    */
478   const uint8_t* buffer() const {
479     return buf_;
480   }
481
482   /**
483    * Get a writable pointer to the start of the buffer.
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* writableBuffer() {
489     return buf_;
490   }
491
492   /**
493    * Get the pointer to the end of the buffer.
494    *
495    * Note that this is the pointer to the very end of the usable buffer,
496    * not the end of valid data within the buffer.  Use the tail() method to
497    * get a pointer to the end of the data within the buffer.
498    */
499   const uint8_t* bufferEnd() const {
500     return buf_ + capacity_;
501   }
502
503   /**
504    * Get the total size of the buffer.
505    *
506    * This returns the total usable length of the buffer.  Use the length()
507    * method to get the length of the actual valid data in this IOBuf.
508    */
509   uint32_t capacity() const {
510     return capacity_;
511   }
512
513   /**
514    * Get a pointer to the next IOBuf in this chain.
515    */
516   IOBuf* next() {
517     return next_;
518   }
519   const IOBuf* next() const {
520     return next_;
521   }
522
523   /**
524    * Get a pointer to the previous IOBuf in this chain.
525    */
526   IOBuf* prev() {
527     return prev_;
528   }
529   const IOBuf* prev() const {
530     return prev_;
531   }
532
533   /**
534    * Shift the data forwards in the buffer.
535    *
536    * This shifts the data pointer forwards in the buffer to increase the
537    * headroom.  This is commonly used to increase the headroom in a newly
538    * allocated buffer.
539    *
540    * The caller is responsible for ensuring that there is sufficient
541    * tailroom in the buffer before calling advance().
542    *
543    * If there is a non-zero data length, advance() will use memmove() to shift
544    * the data forwards in the buffer.  In this case, the caller is responsible
545    * for making sure the buffer is unshared, so it will not affect other IOBufs
546    * that may be sharing the same underlying buffer.
547    */
548   void advance(uint32_t amount) {
549     // In debug builds, assert if there is a problem.
550     assert(amount <= tailroom());
551
552     if (length_ > 0) {
553       memmove(data_ + amount, data_, length_);
554     }
555     data_ += amount;
556   }
557
558   /**
559    * Shift the data backwards in the buffer.
560    *
561    * The caller is responsible for ensuring that there is sufficient headroom
562    * in the buffer before calling retreat().
563    *
564    * If there is a non-zero data length, retreat() will use memmove() to shift
565    * the data backwards in the buffer.  In this case, the caller is responsible
566    * for making sure the buffer is unshared, so it will not affect other IOBufs
567    * that may be sharing the same underlying buffer.
568    */
569   void retreat(uint32_t amount) {
570     // In debug builds, assert if there is a problem.
571     assert(amount <= headroom());
572
573     if (length_ > 0) {
574       memmove(data_ - amount, data_, length_);
575     }
576     data_ -= amount;
577   }
578
579   /**
580    * Adjust the data pointer to include more valid data at the beginning.
581    *
582    * This moves the data pointer backwards to include more of the available
583    * buffer.  The caller is responsible for ensuring that there is sufficient
584    * headroom for the new data.  The caller is also responsible for populating
585    * this section with valid data.
586    *
587    * This does not modify any actual data in the buffer.
588    */
589   void prepend(uint32_t amount) {
590     DCHECK_LE(amount, headroom());
591     data_ -= amount;
592     length_ += amount;
593   }
594
595   /**
596    * Adjust the tail pointer to include more valid data at the end.
597    *
598    * This moves the tail pointer forwards to include more of the available
599    * buffer.  The caller is responsible for ensuring that there is sufficient
600    * tailroom for the new data.  The caller is also responsible for populating
601    * this section with valid data.
602    *
603    * This does not modify any actual data in the buffer.
604    */
605   void append(uint32_t amount) {
606     DCHECK_LE(amount, tailroom());
607     length_ += amount;
608   }
609
610   /**
611    * Adjust the data pointer forwards to include less valid data.
612    *
613    * This moves the data pointer forwards so that the first amount bytes are no
614    * longer considered valid data.  The caller is responsible for ensuring that
615    * amount is less than or equal to the actual data length.
616    *
617    * This does not modify any actual data in the buffer.
618    */
619   void trimStart(uint32_t amount) {
620     DCHECK_LE(amount, length_);
621     data_ += amount;
622     length_ -= amount;
623   }
624
625   /**
626    * Adjust the tail pointer backwards to include less valid data.
627    *
628    * This moves the tail pointer backwards so that the last amount bytes are no
629    * longer considered valid data.  The caller is responsible for ensuring that
630    * amount is less than or equal to the actual data length.
631    *
632    * This does not modify any actual data in the buffer.
633    */
634   void trimEnd(uint32_t amount) {
635     DCHECK_LE(amount, length_);
636     length_ -= amount;
637   }
638
639   /**
640    * Clear the buffer.
641    *
642    * Postcondition: headroom() == 0, length() == 0, tailroom() == capacity()
643    */
644   void clear() {
645     data_ = writableBuffer();
646     length_ = 0;
647   }
648
649   /**
650    * Ensure that this buffer has at least minHeadroom headroom bytes and at
651    * least minTailroom tailroom bytes.  The buffer must be writable
652    * (you must call unshare() before this, if necessary).
653    *
654    * Postcondition: headroom() >= minHeadroom, tailroom() >= minTailroom,
655    * the data (between data() and data() + length()) is preserved.
656    */
657   void reserve(uint32_t minHeadroom, uint32_t minTailroom) {
658     // Maybe we don't need to do anything.
659     if (headroom() >= minHeadroom && tailroom() >= minTailroom) {
660       return;
661     }
662     // If the buffer is empty but we have enough total room (head + tail),
663     // move the data_ pointer around.
664     if (length() == 0 &&
665         headroom() + tailroom() >= minHeadroom + minTailroom) {
666       data_ = writableBuffer() + minHeadroom;
667       return;
668     }
669     // Bah, we have to do actual work.
670     reserveSlow(minHeadroom, minTailroom);
671   }
672
673   /**
674    * Return true if this IOBuf is part of a chain of multiple IOBufs, or false
675    * if this is the only IOBuf in its chain.
676    */
677   bool isChained() const {
678     assert((next_ == this) == (prev_ == this));
679     return next_ != this;
680   }
681
682   /**
683    * Get the number of IOBufs in this chain.
684    *
685    * Beware that this method has to walk the entire chain.
686    * Use isChained() if you just want to check if this IOBuf is part of a chain
687    * or not.
688    */
689   uint32_t countChainElements() const;
690
691   /**
692    * Get the length of all the data in this IOBuf chain.
693    *
694    * Beware that this method has to walk the entire chain.
695    */
696   uint64_t computeChainDataLength() const;
697
698   /**
699    * Insert another IOBuf chain immediately before this IOBuf.
700    *
701    * For example, if there are two IOBuf chains (A, B, C) and (D, E, F),
702    * and B->prependChain(D) is called, the (D, E, F) chain will be subsumed
703    * and become part of the chain starting at A, which will now look like
704    * (A, D, E, F, B, C)
705    *
706    * Note that since IOBuf chains are circular, head->prependChain(other) can
707    * be used to append the other chain at the very end of the chain pointed to
708    * by head.  For example, if there are two IOBuf chains (A, B, C) and
709    * (D, E, F), and A->prependChain(D) is called, the chain starting at A will
710    * now consist of (A, B, C, D, E, F)
711    *
712    * The elements in the specified IOBuf chain will become part of this chain,
713    * and will be owned by the head of this chain.  When this chain is
714    * destroyed, all elements in the supplied chain will also be destroyed.
715    *
716    * For this reason, appendChain() only accepts an rvalue-reference to a
717    * unique_ptr(), to make it clear that it is taking ownership of the supplied
718    * chain.  If you have a raw pointer, you can pass in a new temporary
719    * unique_ptr around the raw pointer.  If you have an existing,
720    * non-temporary unique_ptr, you must call std::move(ptr) to make it clear
721    * that you are destroying the original pointer.
722    */
723   void prependChain(std::unique_ptr<IOBuf>&& iobuf);
724
725   /**
726    * Append another IOBuf chain immediately after this IOBuf.
727    *
728    * For example, if there are two IOBuf chains (A, B, C) and (D, E, F),
729    * and B->appendChain(D) is called, the (D, E, F) chain will be subsumed
730    * and become part of the chain starting at A, which will now look like
731    * (A, B, D, E, F, C)
732    *
733    * The elements in the specified IOBuf chain will become part of this chain,
734    * and will be owned by the head of this chain.  When this chain is
735    * destroyed, all elements in the supplied chain will also be destroyed.
736    *
737    * For this reason, appendChain() only accepts an rvalue-reference to a
738    * unique_ptr(), to make it clear that it is taking ownership of the supplied
739    * chain.  If you have a raw pointer, you can pass in a new temporary
740    * unique_ptr around the raw pointer.  If you have an existing,
741    * non-temporary unique_ptr, you must call std::move(ptr) to make it clear
742    * that you are destroying the original pointer.
743    */
744   void appendChain(std::unique_ptr<IOBuf>&& iobuf) {
745     // Just use prependChain() on the next element in our chain
746     next_->prependChain(std::move(iobuf));
747   }
748
749   /**
750    * Remove this IOBuf from its current chain.
751    *
752    * Since ownership of all elements an IOBuf chain is normally maintained by
753    * the head of the chain, unlink() transfers ownership of this IOBuf from the
754    * chain and gives it to the caller.  A new unique_ptr to the IOBuf is
755    * returned to the caller.  The caller must store the returned unique_ptr (or
756    * call release() on it) to take ownership, otherwise the IOBuf will be
757    * immediately destroyed.
758    *
759    * Since unlink transfers ownership of the IOBuf to the caller, be careful
760    * not to call unlink() on the head of a chain if you already maintain
761    * ownership on the head of the chain via other means.  The pop() method
762    * is a better choice for that situation.
763    */
764   std::unique_ptr<IOBuf> unlink() {
765     next_->prev_ = prev_;
766     prev_->next_ = next_;
767     prev_ = this;
768     next_ = this;
769     return std::unique_ptr<IOBuf>(this);
770   }
771
772   /**
773    * Remove this IOBuf from its current chain and return a unique_ptr to
774    * the IOBuf that formerly followed it in the chain.
775    */
776   std::unique_ptr<IOBuf> pop() {
777     IOBuf *next = next_;
778     next_->prev_ = prev_;
779     prev_->next_ = next_;
780     prev_ = this;
781     next_ = this;
782     return std::unique_ptr<IOBuf>((next == this) ? NULL : next);
783   }
784
785   /**
786    * Remove a subchain from this chain.
787    *
788    * Remove the subchain starting at head and ending at tail from this chain.
789    *
790    * Returns a unique_ptr pointing to head.  (In other words, ownership of the
791    * head of the subchain is transferred to the caller.)  If the caller ignores
792    * the return value and lets the unique_ptr be destroyed, the subchain will
793    * be immediately destroyed.
794    *
795    * The subchain referenced by the specified head and tail must be part of the
796    * same chain as the current IOBuf, but must not contain the current IOBuf.
797    * However, the specified head and tail may be equal to each other (i.e.,
798    * they may be a subchain of length 1).
799    */
800   std::unique_ptr<IOBuf> separateChain(IOBuf* head, IOBuf* tail) {
801     assert(head != this);
802     assert(tail != this);
803
804     head->prev_->next_ = tail->next_;
805     tail->next_->prev_ = head->prev_;
806
807     head->prev_ = tail;
808     tail->next_ = head;
809
810     return std::unique_ptr<IOBuf>(head);
811   }
812
813   /**
814    * Return true if at least one of the IOBufs in this chain are shared,
815    * or false if all of the IOBufs point to unique buffers.
816    *
817    * Use isSharedOne() to only check this IOBuf rather than the entire chain.
818    */
819   bool isShared() const {
820     const IOBuf* current = this;
821     while (true) {
822       if (current->isSharedOne()) {
823         return true;
824       }
825       current = current->next_;
826       if (current == this) {
827         return false;
828       }
829     }
830   }
831
832   /**
833    * Return true if other IOBufs are also pointing to the buffer used by this
834    * IOBuf, and false otherwise.
835    *
836    * If this IOBuf points at a buffer owned by another (non-IOBuf) part of the
837    * code (i.e., if the IOBuf was created using wrapBuffer(), or was cloned
838    * from such an IOBuf), it is always considered shared.
839    *
840    * This only checks the current IOBuf, and not other IOBufs in the chain.
841    */
842   bool isSharedOne() const {
843     if (LIKELY(flags_ & (kFlagUserOwned | kFlagMaybeShared)) == 0) {
844       return false;
845     }
846
847     // If this is a user-owned buffer, it is always considered shared
848     if (flags_ & kFlagUserOwned) {
849       return true;
850     }
851
852     // kFlagMaybeShared is set, so we need to check the reference count.
853     // (Checking the reference count requires an atomic operation, which is why
854     // we prefer to only check kFlagMaybeShared if possible.)
855     DCHECK(flags_ & kFlagMaybeShared);
856     bool shared = sharedInfo_->refcount.load(std::memory_order_acquire) > 1;
857     if (!shared) {
858       // we're the last one left
859       flags_ &= ~kFlagMaybeShared;
860     }
861     return shared;
862   }
863
864   /**
865    * Ensure that this IOBuf has a unique buffer that is not shared by other
866    * IOBufs.
867    *
868    * unshare() operates on an entire chain of IOBuf objects.  If the chain is
869    * shared, it may also coalesce the chain when making it unique.  If the
870    * chain is coalesced, subsequent IOBuf objects in the current chain will be
871    * automatically deleted.
872    *
873    * Note that buffers owned by other (non-IOBuf) users are automatically
874    * considered shared.
875    *
876    * Throws std::bad_alloc on error.  On error the IOBuf chain will be
877    * unmodified.
878    *
879    * Currently unshare may also throw std::overflow_error if it tries to
880    * coalesce.  (TODO: In the future it would be nice if unshare() were smart
881    * enough not to coalesce the entire buffer if the data is too large.
882    * However, in practice this seems unlikely to become an issue.)
883    */
884   void unshare() {
885     if (isChained()) {
886       unshareChained();
887     } else {
888       unshareOne();
889     }
890   }
891
892   /**
893    * Ensure that this IOBuf has a unique buffer that is not shared by other
894    * IOBufs.
895    *
896    * unshareOne() operates on a single IOBuf object.  This IOBuf will have a
897    * unique buffer after unshareOne() returns, but other IOBufs in the chain
898    * may still be shared after unshareOne() returns.
899    *
900    * Throws std::bad_alloc on error.  On error the IOBuf will be unmodified.
901    */
902   void unshareOne() {
903     if (isSharedOne()) {
904       unshareOneSlow();
905     }
906   }
907
908   /**
909    * Coalesce this IOBuf chain into a single buffer.
910    *
911    * This method moves all of the data in this IOBuf chain into a single
912    * contiguous buffer, if it is not already in one buffer.  After coalesce()
913    * returns, this IOBuf will be a chain of length one.  Other IOBufs in the
914    * chain will be automatically deleted.
915    *
916    * After coalescing, the IOBuf will have at least as much headroom as the
917    * first IOBuf in the chain, and at least as much tailroom as the last IOBuf
918    * in the chain.
919    *
920    * Throws std::bad_alloc on error.  On error the IOBuf chain will be
921    * unmodified.  Throws std::overflow_error if the length of the entire chain
922    * larger than can be described by a uint32_t capacity.
923    *
924    * Returns ByteRange that points to the data IOBuf stores.
925    */
926   ByteRange coalesce() {
927     if (isChained()) {
928       coalesceSlow();
929     }
930     return ByteRange(data_, length_);
931   }
932
933   /**
934    * Ensure that this chain has at least maxLength bytes available as a
935    * contiguous memory range.
936    *
937    * This method coalesces whole buffers in the chain into this buffer as
938    * necessary until this buffer's length() is at least maxLength.
939    *
940    * After coalescing, the IOBuf will have at least as much headroom as the
941    * first IOBuf in the chain, and at least as much tailroom as the last IOBuf
942    * that was coalesced.
943    *
944    * Throws std::bad_alloc on error.  On error the IOBuf chain will be
945    * unmodified.  Throws std::overflow_error if the length of the coalesced
946    * portion of the chain is larger than can be described by a uint32_t
947    * capacity.  (Although maxLength is uint32_t, gather() doesn't split
948    * buffers, so coalescing whole buffers may result in a capacity that can't
949    * be described in uint32_t.
950    *
951    * Upon return, either enough of the chain was coalesced into a contiguous
952    * region, or the entire chain was coalesced.  That is,
953    * length() >= maxLength || !isChained() is true.
954    */
955   void gather(uint32_t maxLength) {
956     if (!isChained() || length_ >= maxLength) {
957       return;
958     }
959     coalesceSlow(maxLength);
960   }
961
962   /**
963    * Return a new IOBuf chain sharing the same data as this chain.
964    *
965    * The new IOBuf chain will normally point to the same underlying data
966    * buffers as the original chain.  (The one exception to this is if some of
967    * the IOBufs in this chain contain small internal data buffers which cannot
968    * be shared.)
969    */
970   std::unique_ptr<IOBuf> clone() const;
971
972   /**
973    * Return a new IOBuf with the same data as this IOBuf.
974    *
975    * The new IOBuf returned will not be part of a chain (even if this IOBuf is
976    * part of a larger chain).
977    */
978   std::unique_ptr<IOBuf> cloneOne() const;
979
980   /**
981    * Return an iovector suitable for e.g. writev()
982    *
983    *   auto iov = buf->getIov();
984    *   auto xfer = writev(fd, iov.data(), iov.size());
985    *
986    * Naturally, the returned iovector is invalid if you modify the buffer
987    * chain.
988    */
989   folly::fbvector<struct iovec> getIov() const;
990
991   /*
992    * Overridden operator new and delete.
993    * These perform specialized memory management to help support
994    * createCombined(), which allocates IOBuf objects together with the buffer
995    * data.
996    */
997   void* operator new(size_t size);
998   void* operator new(size_t size, void* ptr);
999   void operator delete(void* ptr);
1000
1001   /**
1002    * Destructively convert this IOBuf to a fbstring efficiently.
1003    * We rely on fbstring's AcquireMallocatedString constructor to
1004    * transfer memory.
1005    */
1006   fbstring moveToFbString();
1007
1008   /**
1009    * Iteration support: a chain of IOBufs may be iterated through using
1010    * STL-style iterators over const ByteRanges.  Iterators are only invalidated
1011    * if the IOBuf that they currently point to is removed.
1012    */
1013   Iterator cbegin() const;
1014   Iterator cend() const;
1015   Iterator begin() const;
1016   Iterator end() const;
1017
1018  private:
1019   enum FlagsEnum : uint32_t {
1020     kFlagUserOwned = 0x1,
1021     kFlagFreeSharedInfo = 0x2,
1022     kFlagMaybeShared = 0x4,
1023   };
1024
1025   // Values for the type_ field.
1026   // We currently don't really use this for anything, other than to have it
1027   // around for debugging purposes.  We store it at the moment just because we
1028   // have the 4 extra bytes that would just be padding otherwise.
1029   enum ExtBufTypeEnum {
1030     kExtAllocated = 0,
1031     kExtUserSupplied = 1,
1032     kExtUserOwned = 2,
1033     kCombinedAlloc = 3,
1034   };
1035
1036   struct SharedInfo {
1037     SharedInfo();
1038     SharedInfo(FreeFunction fn, void* arg);
1039
1040     // A pointer to a function to call to free the buffer when the refcount
1041     // hits 0.  If this is NULL, free() will be used instead.
1042     FreeFunction freeFn;
1043     void* userData;
1044     std::atomic<uint32_t> refcount;
1045   };
1046   // Helper structs for use by operator new and delete
1047   struct HeapPrefix;
1048   struct HeapStorage;
1049   struct HeapFullStorage;
1050
1051   // Forbidden copy constructor and assignment opererator
1052   IOBuf(IOBuf const &);
1053   IOBuf& operator=(IOBuf const &);
1054
1055   /**
1056    * Create a new IOBuf pointing to an external buffer.
1057    *
1058    * The caller is responsible for holding a reference count for this new
1059    * IOBuf.  The IOBuf constructor does not automatically increment the
1060    * reference count.
1061    */
1062   IOBuf(ExtBufTypeEnum type, uint32_t flags,
1063         uint8_t* buf, uint32_t capacity,
1064         uint8_t* data, uint32_t length,
1065         SharedInfo* sharedInfo);
1066
1067   void unshareOneSlow();
1068   void unshareChained();
1069   void coalesceSlow(size_t maxLength=std::numeric_limits<size_t>::max());
1070   // newLength must be the entire length of the buffers between this and
1071   // end (no truncation)
1072   void coalesceAndReallocate(
1073       size_t newHeadroom,
1074       size_t newLength,
1075       IOBuf* end,
1076       size_t newTailroom);
1077   void decrementRefcount();
1078   void reserveSlow(uint32_t minHeadroom, uint32_t minTailroom);
1079   void freeExtBuffer();
1080
1081   static size_t goodExtBufferSize(uint32_t minCapacity);
1082   static void initExtBuffer(uint8_t* buf, size_t mallocSize,
1083                             SharedInfo** infoReturn,
1084                             uint32_t* capacityReturn);
1085   static void allocExtBuffer(uint32_t minCapacity,
1086                              uint8_t** bufReturn,
1087                              SharedInfo** infoReturn,
1088                              uint32_t* capacityReturn);
1089   static void releaseStorage(HeapStorage* storage, uint16_t freeFlags);
1090   static void freeInternalBuf(void* buf, void* userData);
1091
1092   /*
1093    * Member variables
1094    */
1095
1096   /*
1097    * Links to the next and the previous IOBuf in this chain.
1098    *
1099    * The chain is circularly linked (the last element in the chain points back
1100    * at the head), and next_ and prev_ can never be NULL.  If this IOBuf is the
1101    * only element in the chain, next_ and prev_ will both point to this.
1102    */
1103   IOBuf* next_;
1104   IOBuf* prev_;
1105
1106   /*
1107    * A pointer to the start of the data referenced by this IOBuf, and the
1108    * length of the data.
1109    *
1110    * This may refer to any subsection of the actual buffer capacity.
1111    */
1112   uint8_t* data_;
1113   uint8_t* buf_;
1114   uint32_t length_;
1115   uint32_t capacity_;
1116   mutable uint32_t flags_;
1117   uint32_t type_;
1118   // SharedInfo may be NULL if kFlagUserOwned is set.  It is non-NULL
1119   // in all other cases.
1120   SharedInfo* sharedInfo_;
1121
1122   struct DeleterBase {
1123     virtual ~DeleterBase() { }
1124     virtual void dispose(void* p) = 0;
1125   };
1126
1127   template <class UniquePtr>
1128   struct UniquePtrDeleter : public DeleterBase {
1129     typedef typename UniquePtr::pointer Pointer;
1130     typedef typename UniquePtr::deleter_type Deleter;
1131
1132     explicit UniquePtrDeleter(Deleter deleter) : deleter_(std::move(deleter)){ }
1133     void dispose(void* p) {
1134       try {
1135         deleter_(static_cast<Pointer>(p));
1136         delete this;
1137       } catch (...) {
1138         abort();
1139       }
1140     }
1141
1142    private:
1143     Deleter deleter_;
1144   };
1145
1146   static void freeUniquePtrBuffer(void* ptr, void* userData) {
1147     static_cast<DeleterBase*>(userData)->dispose(ptr);
1148   }
1149 };
1150
1151 template <class UniquePtr>
1152 typename std::enable_if<detail::IsUniquePtrToSL<UniquePtr>::value,
1153                         std::unique_ptr<IOBuf>>::type
1154 IOBuf::takeOwnership(UniquePtr&& buf, size_t count) {
1155   size_t size = count * sizeof(typename UniquePtr::element_type);
1156   DCHECK_LT(size, size_t(std::numeric_limits<uint32_t>::max()));
1157   auto deleter = new UniquePtrDeleter<UniquePtr>(buf.get_deleter());
1158   return takeOwnership(buf.release(),
1159                        size,
1160                        &IOBuf::freeUniquePtrBuffer,
1161                        deleter);
1162 }
1163
1164 inline std::unique_ptr<IOBuf> IOBuf::copyBuffer(
1165     const void* data, uint32_t size, uint32_t headroom,
1166     uint32_t minTailroom) {
1167   uint32_t capacity = headroom + size + minTailroom;
1168   std::unique_ptr<IOBuf> buf = create(capacity);
1169   buf->advance(headroom);
1170   memcpy(buf->writableData(), data, size);
1171   buf->append(size);
1172   return buf;
1173 }
1174
1175 inline std::unique_ptr<IOBuf> IOBuf::copyBuffer(const std::string& buf,
1176                                                 uint32_t headroom,
1177                                                 uint32_t minTailroom) {
1178   return copyBuffer(buf.data(), buf.size(), headroom, minTailroom);
1179 }
1180
1181 inline std::unique_ptr<IOBuf> IOBuf::maybeCopyBuffer(const std::string& buf,
1182                                                      uint32_t headroom,
1183                                                      uint32_t minTailroom) {
1184   if (buf.empty()) {
1185     return nullptr;
1186   }
1187   return copyBuffer(buf.data(), buf.size(), headroom, minTailroom);
1188 }
1189
1190 class IOBuf::Iterator : public boost::iterator_facade<
1191     IOBuf::Iterator,  // Derived
1192     const ByteRange,  // Value
1193     boost::forward_traversal_tag  // Category or traversal
1194   > {
1195   friend class boost::iterator_core_access;
1196  public:
1197   // Note that IOBufs are stored as a circular list without a guard node,
1198   // so pos == end is ambiguous (it may mean "begin" or "end").  To solve
1199   // the ambiguity (at the cost of one extra comparison in the "increment"
1200   // code path), we define end iterators as having pos_ == end_ == nullptr
1201   // and we only allow forward iteration.
1202   explicit Iterator(const IOBuf* pos, const IOBuf* end)
1203     : pos_(pos),
1204       end_(end) {
1205     // Sadly, we must return by const reference, not by value.
1206     if (pos_) {
1207       setVal();
1208     }
1209   }
1210
1211  private:
1212   void setVal() {
1213     val_ = ByteRange(pos_->data(), pos_->tail());
1214   }
1215
1216   void adjustForEnd() {
1217     if (pos_ == end_) {
1218       pos_ = end_ = nullptr;
1219       val_ = ByteRange();
1220     } else {
1221       setVal();
1222     }
1223   }
1224
1225   const ByteRange& dereference() const {
1226     return val_;
1227   }
1228
1229   bool equal(const Iterator& other) const {
1230     // We must compare end_ in addition to pos_, because forward traversal
1231     // requires that if two iterators are equal (a == b) and dereferenceable,
1232     // then ++a == ++b.
1233     return pos_ == other.pos_ && end_ == other.end_;
1234   }
1235
1236   void increment() {
1237     pos_ = pos_->next();
1238     adjustForEnd();
1239   }
1240
1241   const IOBuf* pos_;
1242   const IOBuf* end_;
1243   ByteRange val_;
1244 };
1245
1246 inline IOBuf::Iterator IOBuf::begin() const { return cbegin(); }
1247 inline IOBuf::Iterator IOBuf::end() const { return cend(); }
1248
1249 } // folly
1250
1251 #pragma GCC diagnostic pop
1252
1253 #endif // FOLLY_IO_IOBUF_H_