IOBuf.h | Explore in Territory

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Docs: https://fburl.com/fbcref_iobuf
//

#pragma once

#include <atomic>
#include <cassert>
#include <cinttypes>
#include <cstddef>
#include <cstring>
#include <iterator>
#include <limits>
#include <memory>
#include <string>
#include <type_traits>

#include <glog/logging.h>

#include <folly/FBString.h>
#include <folly/FBVector.h>
#include <folly/Function.h>
#include <folly/Portability.h>
#include <folly/Range.h>
#include <folly/detail/Iterators.h>
#include <folly/lang/CheckedMath.h>
#include <folly/lang/Ordering.h>
#include <folly/portability/SysUio.h>
#include <folly/synchronization/MicroSpinLock.h>

FOLLY_PUSH_WARNING
// Ignore shadowing warnings within this file, so includers can use -Wshadow.
FOLLY_GNU_DISABLE_WARNING(…)
// Some compilers break on -Wdocumentation. Not all compilers recognise that
// option, so we also suppress -Wpragmas
FOLLY_GNU_DISABLE_WARNING(…)
// Ignore documentation warnings, to enable overloads to share documentation
// with differing parameters
FOLLY_GNU_DISABLE_WARNING(…)

namespace folly {

namespace detail {
// Is T a unique_ptr<> to a standard-layout type?
template <typename T>
struct IsUniquePtrToSL : std::false_type { … };
IsUniquePtrToSL<std::unique_ptr<T, D>>;
} // namespace detail

/**
 * IOBuf manages heap-allocated byte buffers.
 *
 * API Details
 * -----------
 *
 *  - The buffer is not necessarily full of meaningful bytes - there may be
 *    uninitialized bytes before and after the central "valid" range of data.
 *  - Buffers are refcounted, and can be shared by multiple IOBuf objects.
 *    - If you ever write to an IOBuf, first use unshare() to get a unique copy.
 *  - IOBufs can be "chained" in a circularly linked list.
 *    - Use coalesce() to turn an IOBuf chain into a single IOBuf.
 *  - IOBufs are not synchronized. The user is responsible for synchronization.
 *    Notes:
 *    - Like a shared_ptr, the refcounting is atomic.
 *    - const IOBuf methods do not mutate any state, so can safely be called
 *      concurrently with each other, as expected.
 *  - IOBufs are typically stored on the heap, so that they can be used in
 *    chains.
 *
 *
 * Data Layout
 * -----------
 *
 * IOBuf objects contains a pointer to the buffer and information about which
 * segment of the buffer contains valid data.
 *
 *      +-------+
 *      | IOBuf |
 *      +-------+
 *       /
 *      |            |----- length() -----|
 *      v
 *      +------------+--------------------+-----------+
 *      | headroom   |        data        |  tailroom |
 *      +------------+--------------------+-----------+
 *      ^            ^                    ^           ^
 *      buffer()   data()               tail()      bufferEnd()
 *
 *      |----------------- capacity() ----------------|
 *
 *
 * Buffer Sharing
 * --------------
 *
 * Each buffer is reference counted, and multiple IOBuf objects may point
 * to the same buffer.  Each IOBuf may point to a different section of valid
 * data within the underlying buffer.  For example, if multiple protocol
 * requests are read from the network into a single buffer, a separate IOBuf
 * may be created for each request, all sharing the same underlying buffer.
 *
 * In other words, when multiple IOBufs share the same underlying buffer, the
 * data() and tail() methods on each IOBuf may point to a different segment of
 * the data.  However, the buffer() and bufferEnd() methods will point to the
 * same location for all IOBufs sharing the same underlying buffer, unless the
 * tail was resized by trimWritableTail() or maybeSplitTail().
 *
 *           +-----------+     +---------+
 *           |  IOBuf 1  |     | IOBuf 2 |
 *           +-----------+     +---------+
 *            |         | _____/        |
 *       data |    tail |/    data      | tail
 *            v         v               v
 *      +-------------------------------------+
 *      |     |         |               |     |
 *      +-------------------------------------+
 *
 * If you only read data from an IOBuf, you don't need to worry about other
 * IOBuf objects possibly sharing the same underlying buffer.  However, if you
 * ever write to the buffer you need to first ensure that no other IOBufs point
 * to the same buffer.  The unshare() method may be used to ensure that you
 * have an unshared buffer.
 *
 *
 * IOBuf Chains
 * ------------
 *
 * IOBuf objects also contain pointers to next and previous IOBuf objects.
 * This can be used to represent a single logical piece of data that is stored
 * in non-contiguous chunks in separate buffers.
 *
 *     +---------------------------------------------------------------+
 *     |                                                               |
 *     |    +-----------+        +-----------+        +-----------+    |
 *     +--> |  IOBuf 1  | -----> |  IOBuf 2  | -----> |  IOBuf 3  | ---+
 *          +-----------+        +-----------+        +-----------+
 *            |        | _________/     |           ___/        \__
 *            |        |/               |          /               \
 *            v        v                v         v                 v
 *      +-------------------------------------+   +-----------------+
 *      |     |        |                |     |   |                 |
 *      +-------------------------------------+   +-----------------+
 *
 * A single IOBuf object can only belong to one chain at a time.
 *
 * IOBuf chains are always circular.  The "prev" pointer in the head of the
 * chain points to the tail of the chain.  However, it is up to the user to
 * decide which IOBuf is the head.  Internally the IOBuf code does not care
 * which element is the head.
 *
 * The lifetime of all IOBufs in the chain are linked: when one element in the
 * chain is deleted, all other chained elements are also deleted.  Conceptually
 * it is simplest to treat this as if the head of the chain owns all other
 * IOBufs in the chain.  When you delete the head of the chain, it will delete
 * the other elements as well.  For this reason, appendToChain() and
 * insertAfterThisOne() take ownership of the new elements being added to this
 * chain.
 *
 * When the coalesce() method is used to coalesce an entire IOBuf chain into a
 * single IOBuf, all other IOBufs in the chain are eliminated and automatically
 * deleted.  The unshare() method may coalesce the chain; if it does it will
 * similarly delete all IOBufs eliminated from the chain.
 *
 * As discussed in the following section, it is up to the user to maintain a
 * lock around the entire IOBuf chain if multiple threads need to access the
 * chain.  IOBuf does not provide any internal locking.
 *
 *
 * Synchronization
 * ---------------
 *
 * When used in multithread programs, a single IOBuf object should only be
 * accessed mutably by a single thread at a time.  All const member functions of
 * IOBuf are safe to call concurrently with one another, but when a caller uses
 * a single IOBuf across multiple threads and at least one thread calls a
 * non-const member function, the caller is responsible for using an external
 * lock to synchronize access to the IOBuf.
 *
 * Two separate IOBuf objects may be accessed concurrently in separate threads
 * without locking, even if they point to the same underlying buffer.  The
 * buffer reference count is always accessed atomically, and no other
 * operations should affect other IOBufs that point to the same data segment.
 * The caller is responsible for using unshare() to ensure that the data buffer
 * is not shared by other IOBufs before writing to it, and this ensures that
 * the data itself is not modified in one thread while also being accessed from
 * another thread.
 *
 * For IOBuf chains, no two IOBufs in the same chain should be accessed
 * simultaneously in separate threads, except where all simultaneous accesses
 * are to const member functions.  The caller must maintain a lock around the
 * entire chain if the chain, or individual IOBufs in the chain, may be accessed
 * by multiple threads with at least one of the threads needing to mutate.
 *
 *
 * IOBuf Object Allocation
 * -----------------------
 *
 * IOBuf objects themselves exist separately from the data buffer they point
 * to.  Therefore one must also consider how to allocate and manage the IOBuf
 * objects. Typically, IOBufs are allocated on the heap.
 *
 *      +--------------+
 *      |  unique_ptr  |
 *      +--------------+
 *        |
 *        v
 *      +---------+
 *      |  IOBuf  |
 *      +---------+
 *        |
 *        v
 *      +----------+
 *      |  buffer  |
 *      +----------+
 *
 *
 * It is more common to allocate IOBuf objects on the heap, using the create(),
 * takeOwnership(), or wrapBuffer() factory functions.  The clone()/cloneOne()
 * functions also return new heap-allocated IOBufs.  The createCombined()
 * function allocates the IOBuf object and data storage space together, in a
 * single memory allocation.  This can improve performance, particularly if you
 * know that the data buffer and the IOBuf itself will have similar lifetimes.
 *
 * That said, it is also possible to allocate IOBufs on the stack or inline
 * inside another object as well.  This is useful for cases where the IOBuf is
 * short-lived, or when the overhead of allocating the IOBuf on the heap is
 * undesirable.
 *
 * However, note that stack-allocated IOBufs may only be used as the head of a
 * chain (or standalone as the only IOBuf in a chain).  All non-head members of
 * an IOBuf chain must be heap allocated.  (All functions to add nodes to a
 * chain require a std::unique_ptr<IOBuf>, which enforces this requirement.)
 *
 * Copying IOBufs is only meaningful for the head of a chain. The entire chain
 * is cloned; the IOBufs will become shared, and the old and new IOBufs will
 * refer to the same underlying memory.
 *
 *
 * IOBuf Sharing
 * -------------
 *
 * The IOBuf class manages sharing of the underlying buffer that it points to,
 * maintaining a reference count if multiple IOBufs are pointing at the same
 * buffer.
 *
 * However, it is the callers responsibility to manage sharing and ownership of
 * IOBuf objects themselves.  The IOBuf structure does not provide room for an
 * intrusive refcount on the IOBuf object itself, only the underlying data
 * buffer is reference counted.  If users want to share the same IOBuf object
 * between multiple parts of the code, they are responsible for managing this
 * sharing on their own.  (For example, by using a shared_ptr.  Alternatively,
 * users always have the option of using clone() to create a second IOBuf that
 * points to the same underlying buffer.)
 *
 *
 * Inspiration
 * -----------
 *
 * IOBuf objects are intended to be used primarily for networking code, and are
 * modelled somewhat after FreeBSD's mbuf data structure, and Linux's sk_buff
 * structure.
 *
 * IOBuf objects facilitate zero-copy network programming, by allowing multiple
 * IOBuf objects to point to the same underlying buffer of data, using a
 * reference count to track when the buffer is no longer needed and can be
 * freed.
 *
 *
 * @refcode folly/docs/examples/folly/io/IOBuf.cpp
 */
class IOBuf { … };

/**
 * Hasher for IOBuf objects. Hashes the entire chain using SpookyHashV2.
 */
struct IOBufHash { … };

/**
 * Ordering for IOBuf objects. Compares data in the entire chain.
 */
struct IOBufCompare { … };

/**
 * Equality predicate for IOBuf objects. Compares data in the entire chain.
 */
struct IOBufEqualTo : compare_equal_to<IOBufCompare> { … };

/**
 * Inequality predicate for IOBuf objects. Compares data in the entire chain.
 */
struct IOBufNotEqualTo : compare_not_equal_to<IOBufCompare> { … };

/**
 * Less predicate for IOBuf objects. Compares data in the entire chain.
 */
struct IOBufLess : compare_less<IOBufCompare> { … };

/**
 * At-most predicate for IOBuf objects. Compares data in the entire chain.
 */
struct IOBufLessEqual : compare_less_equal<IOBufCompare> { … };

/**
 * Greater predicate for IOBuf objects. Compares data in the entire chain.
 */
struct IOBufGreater : compare_greater<IOBufCompare> { … };

/**
 * At-least predicate for IOBuf objects. Compares data in the entire chain.
 */
struct IOBufGreaterEqual : compare_greater_equal<IOBufCompare> { … };

template <class UniquePtr>
typename std::enable_if<
    detail::IsUniquePtrToSL<UniquePtr>::value,
    std::unique_ptr<IOBuf>>::type
IOBuf::takeOwnership(UniquePtr&& buf, size_t count) { … }

inline std::unique_ptr<IOBuf> IOBuf::copyBuffer(
    const void* data,
    std::size_t size,
    std::size_t headroom,
    std::size_t minTailroom) { … }

inline std::unique_ptr<IOBuf> IOBuf::copyBuffer(
    StringPiece buf, std::size_t headroom, std::size_t minTailroom) { … }

inline std::unique_ptr<IOBuf> IOBuf::maybeCopyBuffer(
    StringPiece buf, std::size_t headroom, std::size_t minTailroom) { … }

class IOBuf::Iterator : public detail::IteratorFacade<
                            IOBuf::Iterator,
                            ByteRange const,
                            std::forward_iterator_tag> { … };

inline IOBuf::Iterator IOBuf::begin() const { … }
inline IOBuf::Iterator IOBuf::end() const { … }

template <class Container>
void IOBuf::appendTo(Container& container) const { … }

template <class Container>
Container IOBuf::to() const { … }

} // namespace folly

FOLLY_POP_WARNING
folly/folly/io/IOBuf.h
