relnote: QUIC streamable frames can now use a freelist for their packet buffers, Guarded by gfe2_fe…

net/quic/quic_buffer_pool.h

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// A free list for character buffers, optimized to avoid TLB misses.
+//
+// This seeks to solve 2 problems:
+// 1. Free lists are broadly beneficial to most malloc implementations that QUIC
+//    relies on, but especially TCMalloc. Certain QUIC allocations
+//    disproportionately fill up the TCMalloc caches, which leads to TCMalloc
+//    running in a less efficient manner than usual because its other buckets
+//    end up starved.
+// 2. TCMalloc will release unused memory back to the system periodically.
+//    However, it does so out of contiguous allocations, which can lead to the
+//    physical memory becoming fragmented between the processes running.
+//
+// An ordinary FreeList solves the first problem, essentially by artificially
+// inflating a particular TCMalloc bucket without impacting TCMalloc directly.
+// However, it does nothing to solve the second problem.
+//
+// This free list instead uses huge blocks of memory (so-called "Regions"). Each
+// block stores the block's free list and the blocks buffer pool. The huge block
+// is opportunistically acquired as huge pages (a 2MB page) to avoid physical
+// memory fragmentation, and to decrease the likelihood of TLB misses.
+// Additionally, the region pointers are stored in the same storage as the
+// buffer pool itself, which lends itself to avoiding a pointer dereference
+// (again, further polluting the TLBs), at the expense of having a compiled-in
+// maximum number of regions.
+//
+// Fundamentally, the QuicBufferPool supercedes a new char[] and delete[] pair.
+// There is an additional New(size_t, bool), which makes the use of a
+// QuicBufferPool flag-flippable.
+//
+// QuicBufferPool is not thread-safe. Using it without external locking will
+// cause pool corruption.
+//
+// The memory returned by QuicBufferPool is always aligned to at least 16 bytes,
+// so it can be used with SSE instructions without additional work.
+//
+// QuicBufferPool is errno-transparent; it makes system calls, but errno will
+// always be restored to the original value after them.
+//
+// QuicBufferPool does not release memory until the whole object is destroyed.
+//
+#ifndef NET_QUIC_QUIC_BUFFER_POOL_H_
+#define NET_QUIC_QUIC_BUFFER_POOL_H_
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <limits>
+#include <new>
+#include <type_traits>
+
+#include "base/logging.h"
+#include "base/memory/aligned_memory.h"
+#include "net/quic/quic_bug_tracker.h"
+#include "net/quic/quic_protocol.h"
+
+#define PREDICT_FALSE(x) x
+#define PREDICT_TRUE(x) x
+
+#define PROT_READ 0x04
+#define PROT_WRITE 0x02
+#define MAP_PRIVATE 0x02
+#define MAP_ANONYMOUS 0x20
+
+namespace net {
+
+template <size_t MaxBufferSize,
+          size_t MaxNumRegions,
+          size_t RegionSize = 8 * 1024 * 1024>
+class QuicBufferPool : public QuicBufferAllocator {
+ public:
+  QuicBufferPool() = default;
+  explicit QuicBufferPool(base::LinkerInitialized linker_initialized);
+  char* New(size_t size) override;
+  char* New(size_t size, bool flag_enable) override;
+  void Delete(char* buf) override;
+  void MarkAllocatorIdle() override;
+
+ private:
+  friend class QuicBufferPoolTest;
+
+  // The minimum alignment for objects in a region.
+  static const size_t kMinAlignment = 16;
+
+  static const size_t kAlignedMaxBufferSize =
+      ((MaxBufferSize + kMinAlignment - 1) / kMinAlignment) * kMinAlignment;
+  static_assert((RegionSize % 4096) == 0, "Regions must be page aligned.");
+  static_assert((kAlignedMaxBufferSize % kMinAlignment) == 0,
+                "Alignment calculation failure: aligned buffer size is not "
+                "aligned to the minimum alignment.");
+  static_assert(kAlignedMaxBufferSize >= MaxBufferSize,
+                "Alignment calculation failure: aligned buffer size smaller "
+                "than the max buffer size.");
+  static_assert(MaxBufferSize + kMinAlignment > kAlignedMaxBufferSize,
+                "Alignment calculation failure: aligned buffer size is larger "
+                "than it needs to be.");
+
+  // The actual size of an allocation within the region.
+  static const size_t kAllocSize = kAlignedMaxBufferSize;
+
+  // The usable region size includes kMinAlignment to ensure there's room to
+  // align up after the free list.
+  static const size_t kUsableRegionSize = RegionSize - kMinAlignment;
+
+  // The number of buffers that can fit in the usable memory space.
+  static const size_t kNumBuffersPerRegion =
+      kUsableRegionSize / (kAllocSize + sizeof(char*));
+
+  // A region of memory that buffers can be allocated from.
+  class Region {
+   public:
+    Region() = default;
+    explicit Region(base::LinkerInitialized linker_initialized);
+    ~Region();
+
+    // Allocates a region of memory and initializes the free list within that
+    // memory. Has no effect if the region has already been initialized. If this
+    // method fails, Initialize can be called again to try again later.
+    bool Initialize();
+
+    // Releases the memory backing a region.
+    void Release();
+
+    // Returns a new buffer of |kAllocSize| bytes.
+    // Returns nullptr if there are no available slots.
+    char* New();
+
+    // Releases a buffer. Must be called with memory within the region.
+    void Delete(char* buf);
+
+    // Returns true if the Region contains |buf|.
+    bool Contains(char* buf) const;
+
+    // Returns true if the Region has no outstanding allocations.
+    bool Empty() const;
+
+    // Swaps one region with another region.
+    void Swap(Region* other);
+
+   private:
+    // The offset of the free list within the region.
+    static const size_t kFreeListOffset = 0;
+
+    // The offset of the first buffer within the region.
+    static const size_t kBufferStartOffset =
+        RegionSize - (kNumBuffersPerRegion * kAllocSize);
+
+    static_assert(
+        (kFreeListOffset % sizeof(char*)) == 0,
+        "kFreeListOffset must be aligned to a free list entry boundary.");
+    static_assert(kAlignedMaxBufferSize < kUsableRegionSize,
+                  "MaxBufferSize is too large to fit in a 2MB page.");
+    static_assert(
+        MaxBufferSize > sizeof(char*),
+        "MaxBufferSize must be at least the size of a freelist entry.");
+    static_assert(kNumBuffersPerRegion > 0, "Pool will not hold any buffers.");
+    static_assert(
+        kBufferStartOffset >=
+            kFreeListOffset + (sizeof(char*) * kNumBuffersPerRegion),
+        "Region offset calculation failure; freelist overlaps with buffers.");
+    static_assert(kNumBuffersPerRegion <
+                      static_cast<size_t>(std::numeric_limits<int>::max()),
+                  "Region buffer calculation failure; more buffers can be "
+                  "stored in a region than are indexable by an int.");
+    static_assert(static_cast<int>(kNumBuffersPerRegion * MaxNumRegions) ==
+                      kNumBuffersPerRegion * MaxNumRegions,
+                  "The number of possible allocations in this pool will "
+                  "overflow an int.");
+
+    // Returns a pointer to the linear free list.
+    char** free_list() {
+      return reinterpret_cast<char**>(base_ + kFreeListOffset);
+    }
+
+    // POSIX mmap, except errno is preserved.
+    // clang-format off
+    static void* MmapPreserveErrno(void* addr,
+                                   size_t length,
+                                   int prot,
+                                   int flags,
+                                   int fd,
+                                   off_t offset);
+    // clang-format on
+
+    // POSIX munmap, except errno is preserved.
+    static void MunmapPreserveErrno(void* addr, size_t length);
+
+    char* base_ = nullptr;
+    unsigned int next_free_ = 0;
+
+    DISALLOW_COPY_AND_ASSIGN(Region);
+  };
+
+  // Returns heap-allocated memory. Only fails if malloc fails.
+  static char* FallbackNew(size_t size);
+
+  // Releases |buf| to the heap.
+  static void FallbackDelete(char* buf);
+
+  // The current number of buffers in use across all regions.
+  unsigned int current_allocations_ = 0;
+
+  // The maximum region in regions_ that was successfully initialized.
+  unsigned int max_region_ = 0;
+  std::array<Region, MaxNumRegions> regions_;
+
+  DISALLOW_COPY_AND_ASSIGN(QuicBufferPool);
+};
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::QuicBufferPool(
+    base::LinkerInitialized /* linker_initialized */) {}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+char* QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::New(
+    size_t size) {
+  if (PREDICT_FALSE(size > kAlignedMaxBufferSize)) {
+    QUIC_BUG << "Request for buffer of size " << size
+             << " greater than pool buffer size " << kAlignedMaxBufferSize;
+    return FallbackNew(size);
+  }
+
+  // Lazy-initialize the first region if we need to.
+  if (PREDICT_FALSE(max_region_ == 0)) {
+    if (PREDICT_FALSE(!regions_[0].Initialize())) {
+      QUIC_BUG << "Failed to initialize first region in buffer pool.";
+      return FallbackNew(size);
+    }
+    max_region_ = 1;
+  }
+
+  // Find the first Region that can allocate some memory. Prioritize the lower
+  // order regions so higher order regions can be released.
+  for (unsigned int current_region = 0; current_region < max_region_;
+       ++current_region) {
+    Region& region = regions_[current_region];
+    char* const buf = region.New();
+    if (buf != nullptr) {
+      ++current_allocations_;
+      return buf;
+    }
+  }
+
+  // If all of the regions are full and we can add more regions, try to add a
+  // new one. Note that we never release regions until QuicBufferPool
+  // destruction.
+  if (PREDICT_TRUE(max_region_ < MaxNumRegions)) {
+    Region& new_region = regions_[max_region_];
+    if (PREDICT_FALSE(!new_region.Initialize())) {
+      QUIC_BUG << "Failed to initialize new region in buffer pool.";
+      return FallbackNew(size);
+    }
+    // If this region was just initialized, it's guaranteed to be able to return
+    // some memory.
+    char* const buf = new_region.New();
+    if (PREDICT_TRUE(buf != nullptr)) {
+      ++current_allocations_;
+      ++max_region_;
+      return buf;
+    } else {
+      QUIC_BUG << "Freshly initialized Region failed to allocate memory";
+    }
+  }
+
+  QUIC_BUG << "Ran out of room in QuicBufferPool.";
+  return FallbackNew(size);
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+char* QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::New(
+    size_t size,
+    bool flag_enable) {
+  if (flag_enable) {
+    return New(size);
+  } else {
+    return FallbackNew(size);
+  }
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Delete(
+    char* buf) {
+  if (buf == nullptr) {
+    return;
+  }
+  for (unsigned int i = 0; i < max_region_; ++i) {
+    Region* region = &regions_[i];
+    if (region->Contains(buf)) {
+      region->Delete(buf);
+      // If the region is empty, move it to the back of the list of regions.
+      if (region->Empty()) {
+        DCHECK_GE(max_region_, 1u);
+        region->Swap(&regions_[max_region_ - 1]);
+      }
+      --current_allocations_;
+      if (max_region_ > 1 && regions_[max_region_ - 1].Empty() &&
+          current_allocations_ < ((max_region_ * kNumBuffersPerRegion) -
+                                  (kNumBuffersPerRegion >> 1))) {
+        // We have 1.5 Regions worth of memory free, and the last region is
+        // completely empty. Let's release the last Region back to the OS; it
+        // seems like we don't need it right now. Note that this will never
+        // release regions_[0].
+        regions_[--max_region_].Release();
+      }
+      return;
+    }
+  }
+  FallbackDelete(buf);
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void QuicBufferPool<MaxBufferSize,
+                    MaxNumRegions,
+                    RegionSize>::MarkAllocatorIdle() {
+  if (current_allocations_ == 0 && max_region_ == 1) {
+    regions_[0].Release();
+    max_region_ = 0;
+  }
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Region::Region(
+    base::LinkerInitialized /* linker_initialized */) {}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Region::~Region() {
+  // If the region was allocated but all of the buffers in the region haven't
+  // been freed yet, defer freeing until the last buffer is released.
+  if (base_ != nullptr && next_free_ != 0) {
+    QUIC_BUG << "Freeing " << this << " with " << next_free_
+             << " unfreed allocations.";
+    MunmapPreserveErrno(base_, RegionSize);
+  }
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+bool QuicBufferPool<MaxBufferSize,
+                    MaxNumRegions,
+                    RegionSize>::Region::Initialize() {
+  if (base_ != nullptr) {
+    return true;
+  }
+
+  const int prot_flags = PROT_READ | PROT_WRITE;
+  const int map_flags = MAP_PRIVATE | MAP_ANONYMOUS;
+  // char* buf = static_cast<char*>(MAP_FAILED);
+  char* buf = nullptr;
+#ifdef MAP_HUGETLB
+  // Try to get 2MB pages first.
+  // clang-format off
+  buf = static_cast<char*>(MmapPreserveErrno(
+          static_cast<void*>(nullptr),
+          RegionSize,
+          prot_flags,
+          map_flags | MAP_HUGETLB,
+          -1,
+          0));
+#endif
+  if (buf == nullptr) {
+    // Otherwise we have to use 4K pages.
+    buf = static_cast<char*>(MmapPreserveErrno(
+        static_cast<void*>(nullptr),
+        RegionSize,
+        prot_flags,
+        map_flags,
+        -1,
+        0));
+  }
+  // clang-format on
+
+  if (PREDICT_FALSE(buf == nullptr)) {
+    return false;
+  }
+
+  base_ = buf;
+
+  // Walk the memory in linear order; the free list comes first, then comes the
+  // memory.
+  for (size_t i = 0; i < kNumBuffersPerRegion; ++i) {
+    free_list()[i] = base_ + kBufferStartOffset + (kAllocSize * i);
+  }
+
+  return true;
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void QuicBufferPool<MaxBufferSize,
+                    MaxNumRegions,
+                    RegionSize>::Region::Release() {
+  DCHECK(base_ != nullptr);
+  DCHECK_EQ(0u, next_free_);
+  if (base_ == nullptr) {
+    return;
+  }
+
+  // We'll continue holding onto virtual address space, but the physical backing
+  // is released. This is faster than munmap, and we have plenty of virtual
+  // address space to burn.
+  MunmapPreserveErrno(base_, RegionSize);
+  base_ = nullptr;
+  next_free_ = 0;
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+char* QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Region::New() {
+  if (next_free_ < kNumBuffersPerRegion) {
+    return free_list()[next_free_++];
+  } else {
+    return nullptr;
+  }
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Region::Delete(
+    char* buf) {
+  DCHECK_GT(next_free_, 0u);
+  free_list()[--next_free_] = buf;
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+bool QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Region::Contains(
+    char* buf) const {
+  return (base_ <= buf) && (buf + MaxBufferSize <= base_ + RegionSize);
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+bool QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Region::Empty()
+    const {
+  return next_free_ == 0;
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::Region::Swap(
+    Region* other) {
+  if (this == other) {
+    return;
+  }
+  using std::swap;
+  swap(next_free_, other->next_free_);
+  swap(base_, other->base_);
+}
+
+// clang-format off
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void* QuicBufferPool<MaxBufferSize, MaxNumRegions,
+                     RegionSize>::Region::MmapPreserveErrno(void* addr,
+                                                            size_t length,
+                                                            int prot,
+                                                            int flags,
+                                                            int fd,
+                                                            off_t offset) {
+  // clang-format on
+  const int old_errno = errno;
+  void* ret = base::AlignedAlloc(length, kMinAlignment);
+  errno = old_errno;
+  return ret;
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void QuicBufferPool<MaxBufferSize,
+                    MaxNumRegions,
+                    RegionSize>::Region::MunmapPreserveErrno(void* addr,
+                                                             size_t length) {
+  const int old_errno = errno;
+  base::AlignedFree(addr);
+  errno = old_errno;
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+char* QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::FallbackNew(
+    size_t size) {
+  return new char[size];
+}
+
+template <size_t MaxBufferSize, size_t MaxNumRegions, size_t RegionSize>
+void QuicBufferPool<MaxBufferSize, MaxNumRegions, RegionSize>::FallbackDelete(
+    char* buf) {
+  delete[] buf;
+}
+
+}  // namespace net
+
+#endif  // NET_QUIC_QUIC_BUFFER_POOL_H_