// Copyright 2019 The TCMalloc Authors
//
// 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
//
//     https://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.

#include "tcmalloc/central_freelist.h"

#include <math.h>
#include <stddef.h>
#include <stdint.h>

#include <algorithm>
#include <array>
#include <atomic>
#include <cstring>
#include <memory>
#include <string>
#include <thread>
#include <tuple>
#include <utility>
#include <vector>

#include "benchmark/benchmark.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/algorithm/container.h"
#include "absl/base/internal/spinlock.h"
#include "absl/base/thread_annotations.h"
#include "absl/container/fixed_array.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/memory/memory.h"
#include "absl/numeric/bits.h"
#include "absl/random/random.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/strings/str_join.h"
#include "absl/synchronization/mutex.h"
#include "absl/time/clock.h"
#include "absl/time/time.h"
#include "absl/types/span.h"
#include "tcmalloc/common.h"
#include "tcmalloc/internal/logging.h"
#include "tcmalloc/internal/size_class_info.h"
#include "tcmalloc/mock_static_forwarder.h"
#include "tcmalloc/pagemap.h"
#include "tcmalloc/pages.h"
#include "tcmalloc/sizemap.h"
#include "tcmalloc/span.h"
#include "tcmalloc/span_stats.h"
#include "tcmalloc/static_vars.h"
#include "tcmalloc/stats.h"
#include "tcmalloc/testing/testutil.h"
#include "tcmalloc/testing/thread_manager.h"

namespace tcmalloc {
namespace tcmalloc_internal {

namespace central_freelist_internal {

class StaticForwarderTest : public testing::TestWithParam<size_t> {
 protected:
  size_t size_class_;
  size_t object_size_;
  Length pages_per_span_;
  size_t batch_size_;
  size_t objects_per_span_;
  uint32_t size_reciprocal_;

 private:
  void SetUp() override {
    size_class_ = GetParam();
    if (IsExpandedSizeClass(size_class_)) {
#if ABSL_HAVE_THREAD_SANITIZER || ABSL_HAVE_HWADDRESS_SANITIZER
      GTEST_SKIP() << "Skipping test under sanitizers that conflict with "
                      "address placement";
#endif

      if (!ColdFeatureActive()) {
        // If !ColdFeatureActive(), we will use the normal page heap, which will
        // keep us from seeing memory get the expected tags.
        GTEST_SKIP()
            << "Skipping expanded size classes without cold experiment";
      }
    }
    object_size_ = tc_globals.sizemap().class_to_size(size_class_);
    if (object_size_ == 0) {
      GTEST_SKIP() << "Skipping empty size class.";
    }

    pages_per_span_ = tc_globals.sizemap().class_to_pages(size_class_);
    batch_size_ = tc_globals.sizemap().num_objects_to_move(size_class_);
    objects_per_span_ = pages_per_span_.in_bytes() / object_size_;
    size_reciprocal_ = Span::CalcReciprocal(object_size_);
  }
};

TEST_P(StaticForwarderTest, Simple) {
  Span* span = StaticForwarder::AllocateSpan(size_class_, objects_per_span_,
                                             pages_per_span_);
  ASSERT_NE(span, nullptr);

  absl::FixedArray<void*> batch(objects_per_span_);
  const uint64_t alloc_time = StaticForwarder::clock_now();
  size_t allocated = span->BuildFreelist(object_size_, objects_per_span_,
                                         absl::MakeSpan(batch), alloc_time);
  ASSERT_EQ(allocated, objects_per_span_);

  EXPECT_EQ(size_class_, tc_globals.pagemap().sizeclass(span->first_page()));
  EXPECT_EQ(size_class_, tc_globals.pagemap().sizeclass(span->last_page()));

  // span_test.cc provides test coverage for Span, but we need to obtain several
  // objects to confirm we can map back to the Span pointer from the PageMap.
  for (void* ptr : batch) {
    Span* got;
    StaticForwarder::MapObjectsToSpans({&ptr, 1}, &got, size_class_);
    EXPECT_EQ(span, got);
  }

  for (void* ptr : batch) {
    EXPECT_EQ(span->FreelistPushBatch(absl::MakeSpan(&ptr, 1), object_size_,
                                      size_reciprocal_),
              ptr != batch.back());
  }

  StaticForwarder::DeallocateSpans(objects_per_span_, absl::MakeSpan(&span, 1));
}

class StaticForwarderEnvironment {
  struct SpanData {
    Span* span;
    void* batch[kMaxObjectsToMove];
  };

 public:
  StaticForwarderEnvironment(int size_class, size_t object_size,
                             size_t objects_per_span, Length pages_per_span,
                             int batch_size)
      : size_class_(size_class),
        object_size_(object_size),
        objects_per_span_(objects_per_span),
        pages_per_span_(pages_per_span),
        batch_size_(batch_size) {}

  ~StaticForwarderEnvironment() { Drain(); }

  void RandomlyPoke() {
    absl::BitGen rng;
    double coin = absl::Uniform(rng, 0.0, 1.0);

    if (coin < 0.5) {
      Grow();
    } else if (coin < 0.9) {
      // Deallocate Spans.  We may deallocate more than 1 span, so we bias
      // towards allocating Spans more often than we deallocate.
      Shrink();
    } else {
      Shuffle(rng);
    }
  }

  void Drain() {
    std::vector<std::unique_ptr<SpanData>> spans;

    {
      absl::MutexLock l(mu_);
      if (data_.empty()) {
        return;
      }

      spans = std::move(data_);
      data_.clear();
    }

    // Check mappings.
    std::vector<Span*> free_spans;
    for (const auto& data : spans) {
      EXPECT_EQ(size_class_,
                tc_globals.pagemap().sizeclass(data->span->first_page()));
      EXPECT_EQ(size_class_,
                tc_globals.pagemap().sizeclass(data->span->last_page()));
      // Confirm we can map at least one object back.
      Span* got;
      StaticForwarder::MapObjectsToSpans({&data->batch[0], 1}, &got,
                                         size_class_);
      EXPECT_EQ(data->span, got);

      free_spans.push_back(data->span);
    }

    auto span_span = absl::MakeSpan(free_spans);
    for (int i = 0; i < spans.size(); i += kMaxObjectsToMove) {
      StaticForwarder::DeallocateSpans(objects_per_span_,
                                       span_span.subspan(i, kMaxObjectsToMove));
    }
  }

  void Grow() {
    // Allocate a Span
    Span* span = StaticForwarder::AllocateSpan(size_class_, objects_per_span_,
                                               pages_per_span_);
    ASSERT_NE(span, nullptr);

    auto d = std::make_unique<SpanData>();
    d->span = span;

    size_t allocated = span->BuildFreelist(
        object_size_, objects_per_span_, absl::MakeSpan(d->batch, batch_size_),
        StaticForwarder::clock_now());
    EXPECT_LE(allocated, objects_per_span_);

    EXPECT_EQ(size_class_, tc_globals.pagemap().sizeclass(span->first_page()));
    EXPECT_EQ(size_class_, tc_globals.pagemap().sizeclass(span->last_page()));
    // Confirm we can map at least one object back.
    Span* got;
    StaticForwarder::MapObjectsToSpans({&d->batch[0], 1}, &got, size_class_);
    EXPECT_EQ(span, got);

    absl::MutexLock l(mu_);
    spans_allocated_++;
    data_.push_back(std::move(d));
  }

  void Shrink() {
    absl::BitGen rng;
    std::vector<std::unique_ptr<SpanData>> spans;

    {
      absl::MutexLock l(mu_);
      if (data_.empty()) {
        return;
      }

      size_t count = absl::LogUniform<size_t>(rng, 1, data_.size());
      spans.reserve(count);

      for (int i = 0; i < count; i++) {
        spans.push_back(std::move(data_.back()));
        data_.pop_back();
      }
    }

    // Check mappings.
    std::vector<Span*> free_spans;
    for (auto& data : spans) {
      EXPECT_EQ(size_class_,
                tc_globals.pagemap().sizeclass(data->span->first_page()));
      EXPECT_EQ(size_class_,
                tc_globals.pagemap().sizeclass(data->span->last_page()));
      // Confirm we can map at least one object back.
      Span* got;
      StaticForwarder::MapObjectsToSpans({&data->batch[0], 1}, &got,
                                         size_class_);
      EXPECT_EQ(data->span, got);

      free_spans.push_back(data->span);
    }

    auto span_span = absl::MakeSpan(free_spans);
    for (int i = 0; i < spans.size(); i += kMaxObjectsToMove) {
      StaticForwarder::DeallocateSpans(objects_per_span_,
                                       span_span.subspan(i, kMaxObjectsToMove));
    }
  }

  void Shuffle(absl::BitGen& rng) {
    // Shuffle the shared vector.
    absl::MutexLock l(mu_);
    absl::c_shuffle(data_, rng);
  }

  int64_t BytesAllocated() {
    absl::MutexLock l(mu_);
    return pages_per_span_.in_bytes() * spans_allocated_;
  }

 private:
  int size_class_;
  size_t object_size_;
  size_t objects_per_span_;
  Length pages_per_span_;
  int batch_size_;

  absl::Mutex mu_;
  int64_t spans_allocated_ ABSL_GUARDED_BY(mu_) = 0;
  std::vector<std::unique_ptr<SpanData>> data_ ABSL_GUARDED_BY(mu_);
};

static BackingStats PageHeapStats() {
  PageHeapSpinLockHolder l;
  return tc_globals.page_allocator().stats();
}

TEST_P(StaticForwarderTest, Fuzz) {
#if ABSL_HAVE_THREAD_SANITIZER || ABSL_HAVE_HWADDRESS_SANITIZER
  // TODO(b/193887621):  Enable this test under TSan after addressing benign
  // true positives.
  GTEST_SKIP() << "Skipping test under Thread Sanitizer.";
#endif  // ABSL_HAVE_THREAD_SANITIZER || ABSL_HAVE_HWADDRESS_SANITIZER

  const auto page_heap_before = PageHeapStats();

  StaticForwarderEnvironment env(size_class_, object_size_, objects_per_span_,
                                 pages_per_span_, batch_size_);
  ThreadManager threads;
  threads.Start(10, [&](int) { env.RandomlyPoke(); });

  absl::SleepFor(absl::Milliseconds(50));

  threads.Stop();

  const auto page_heap_after = PageHeapStats();
  // Confirm we did not leak Spans by ensuring the page heap did not grow nearly
  // 1:1 by the total number of Spans we ever allocated.
  //
  // Since we expect to allocate a significant number of spans, we apply a
  // factor of 1/2 (which is unlikely to be flaky) to avoid false negatives
  // if/when a background thread triggers a deallocation.
  const int64_t bytes_allocated = env.BytesAllocated();
  EXPECT_GT(bytes_allocated, 0);
  EXPECT_LE(static_cast<int64_t>(page_heap_after.system_bytes) -
                static_cast<int64_t>(page_heap_before.system_bytes),
            bytes_allocated / 2);
}

TEST(CentralFreeListHelperTest, RecordSameSpanRuns) {
  Span s1, s2, s3;

  struct TestCase {
    std::string name;
    std::vector<Span*> batch;
    int expected_matches;
    std::vector<uint8_t> expected_run_lengths;
  };

  std::vector<TestCase> test_cases = {
      {
          .name = "SingleElement",
          .batch = {&s1},
          .expected_matches = 0,
          .expected_run_lengths = {1},
      },
      {
          .name = "AllSame",
          .batch = {&s1, &s1, &s1},
          .expected_matches = 2,
          .expected_run_lengths = {3, 0, 0},
      },
      {
          .name = "AllDifferent",
          .batch = {&s1, &s2, &s3},
          .expected_matches = 0,
          .expected_run_lengths = {1, 1, 1},
      },
      {
          .name = "MixedRuns",
          .batch = {&s1, &s1, &s2, &s1, &s1, &s1},
          .expected_matches = 3,
          .expected_run_lengths = {2, 0, 1, 3, 0, 0},
      },
  };

  for (const auto& tc : test_cases) {
    SCOPED_TRACE(tc.name);
    std::vector<uint8_t> run_lengths(tc.batch.size(), 0);
    int matches = RecordSameSpanRuns<kMaxObjectsToMove>(
        absl::MakeConstSpan(tc.batch), absl::MakeSpan(run_lengths));
    EXPECT_EQ(matches, tc.expected_matches);
    EXPECT_THAT(run_lengths,
                testing::ElementsAreArray(tc.expected_run_lengths));
  }
}

INSTANTIATE_TEST_SUITE_P(All, StaticForwarderTest,
                         testing::Range(size_t(1), kNumClasses));

}  // namespace central_freelist_internal

namespace {

using central_freelist_internal::kNumLists;
using TypeParam = FakeCentralFreeListEnvironment<
    central_freelist_internal::CentralFreeList<MockStaticForwarder>>;
using CentralFreeListTest = ::testing::TestWithParam<SizeClassInfo>;

TEST_P(CentralFreeListTest, IsolatedSmoke) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  EXPECT_CALL(e.forwarder(), AllocateSpan).Times(1);

  absl::FixedArray<void*> batch(e.batch_size());
  int allocated = e.central_freelist().RemoveRange(
      absl::MakeSpan(&batch[0], e.batch_size()));
  ASSERT_GT(allocated, 0);
  EXPECT_LE(allocated, e.batch_size());

  // We should observe span's utilization captured in the histogram. The number
  // of spans in rest of the buckets should be zero.
  const int bitwidth = absl::bit_width(static_cast<unsigned>(allocated));
  for (int i = 1; i <= absl::bit_width(e.objects_per_span()); ++i) {
    // Skip the check for objects_per_span = 1 since such spans skip most of the
    // central freelist's logic.
    if (i == bitwidth && e.objects_per_span() != 1) {
      EXPECT_EQ(e.central_freelist().NumSpansWith(i), 1);
    } else {
      EXPECT_EQ(e.central_freelist().NumSpansWith(i), 0);
    }
  }

  EXPECT_CALL(e.forwarder(), MapObjectsToSpans).Times(1);
  EXPECT_CALL(e.forwarder(), DeallocateSpans).Times(1);

  // Skip the check for objects_per_span = 1 since such spans skip most of the
  // central freelist's logic.
  SpanStats stats = e.central_freelist().GetSpanStats();
  if (e.objects_per_span() != 1) {
    EXPECT_EQ(stats.num_spans_requested, 1);
    EXPECT_EQ(stats.num_spans_returned, 0);
    EXPECT_EQ(stats.obj_capacity, e.objects_per_span());
  }

  e.central_freelist().InsertRange(absl::MakeSpan(&batch[0], allocated));
  // Skip the check for objects_per_span = 1 since such spans skip most of the
  // central freelist's logic.
  if (e.objects_per_span() != 1) {
    SpanStats stats = e.central_freelist().GetSpanStats();
    EXPECT_EQ(stats.num_spans_requested, 1);
    EXPECT_EQ(stats.num_spans_returned, 1);
    EXPECT_EQ(stats.obj_capacity, 0);
  }

  // Span captured in the histogram with the earlier utilization should have
  // been removed.
  for (int i = 1; i <= absl::bit_width(e.objects_per_span()); ++i) {
    EXPECT_EQ(e.central_freelist().NumSpansWith(i), 0);
  }
}

TEST_P(CentralFreeListTest, SpanUtilizationHistogram) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  constexpr size_t kNumSpans = 10;

  // Request kNumSpans spans.
  void* batch[kMaxObjectsToMove];
  const int num_objects_to_fetch = kNumSpans * e.objects_per_span();
  int total_fetched = 0;
  // Tracks object and corresponding span from which it was allocated.
  std::vector<std::pair<void*, Span*>> object_to_span;
  // Tracks number of objects allocated per span.
  absl::flat_hash_map<Span*, size_t> allocated_per_span;
  int span_idx = 0;

  while (total_fetched < num_objects_to_fetch) {
    size_t n = num_objects_to_fetch - total_fetched;
    int got = e.central_freelist().RemoveRange(
        absl::MakeSpan(batch, std::min(n, e.batch_size())));
    total_fetched += got;

    // Increment span_idx if current objects have been fetched from the new
    // span.
    if (total_fetched > (span_idx + 1) * e.objects_per_span()) {
      ++span_idx;
    }
    // Record fetched object and the associated span.
    for (int i = 0; i < got; ++i) {
      Span* s = e.forwarder().MapObjectToSpan(batch[i]);
      object_to_span.emplace_back(batch[i], s);
      allocated_per_span[s] += 1;
    }
    TC_ASSERT_LT(span_idx, kNumSpans);
  }

  // Make sure that we have fetched exactly from kNumSpans spans.
  EXPECT_EQ(span_idx + 1, kNumSpans);

  // We should have kNumSpans spans in the histogram with number of allocated
  // objects equal to e.objects_per_span() (i.e. in the last bucket).
  // Rest of the buckets should be empty.
  const int expected_bitwidth = absl::bit_width(e.objects_per_span());
  // Skip the check when objects_per_span = 1 as those spans skip most of the
  // central freelist's logic.
  if (e.objects_per_span() != 1) {
    EXPECT_EQ(e.central_freelist().NumSpansWith(expected_bitwidth), kNumSpans);
  }
  for (int i = 1; i < expected_bitwidth; ++i) {
    EXPECT_EQ(e.central_freelist().NumSpansWith(i), 0);
  }

  // Shuffle.
  absl::BitGen rng;
  std::shuffle(object_to_span.begin(), object_to_span.end(), rng);

  // Return objects, a fraction at a time, each time checking that histogram is
  // correct.
  int total_returned = 0;
  const int last_bucket = absl::bit_width(e.objects_per_span()) - 1;
  while (total_returned < num_objects_to_fetch) {
    uint64_t size_to_pop =
        std::min(object_to_span.size() - total_returned, e.batch_size());

    for (int i = 0; i < size_to_pop; ++i) {
      const auto [ptr, span] = object_to_span[i + total_returned];
      batch[i] = ptr;
      --allocated_per_span[span];
    }
    total_returned += size_to_pop;
    e.central_freelist().InsertRange({batch, size_to_pop});

    // Calculate expected histogram.
    std::vector<size_t> expected(absl::bit_width(e.objects_per_span()), 0);
    for (const auto& span_and_count : allocated_per_span) {
      // If span has non-zero allocated objects, include it in the histogram.
      if (span_and_count.second > 0) {
        const size_t bucket = absl::bit_width(span_and_count.second) - 1;
        TC_ASSERT_LE(bucket, last_bucket);
        ++expected[bucket];
      }
    }

    // Fetch number of spans logged in the histogram and compare it with the
    // expected histogram that we calculated using the tracked allocated
    // objects per span.
    for (int i = 1; i <= last_bucket; ++i) {
      EXPECT_EQ(e.central_freelist().NumSpansWith(i), expected[i - 1]);
    }
  }

  // Since no span is live here, histogram must be empty.
  for (int i = 1; i <= last_bucket; ++i) {
    EXPECT_EQ(e.central_freelist().NumSpansWith(i), 0);
  }
}

// Confirms that a call to RemoveRange returns at most kObjectsPerSpan objects
// in cases when there are no non-empty spans in the central freelist. This
// makes sure that we populate, and subsequently allocate from a single span.
// This avoids memory regression due to multiple Populate calls observed in
// b/225880278.
TEST_P(CentralFreeListTest, SinglePopulate) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  // Make sure that we allocate up to kObjectsPerSpan objects in both the span
  // prioritization states.
  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  // Try to fetch sufficiently large number of objects at startup.
  const int num_objects_to_fetch = kMaxObjectsToMove;
  std::vector<void*> objects(num_objects_to_fetch, nullptr);
  const size_t got = e.central_freelist().RemoveRange(
      absl::MakeSpan(objects.data(), num_objects_to_fetch));
  // Confirm we allocated at most kObjectsPerSpan number of objects.
  EXPECT_GT(got, 0);
  EXPECT_LE(got, e.objects_per_span());
  size_t returned = 0;
  while (returned < got) {
    const size_t to_return = std::min(got - returned, e.batch_size());
    e.central_freelist().InsertRange({&objects[returned], to_return});
    returned += to_return;
  }
}

// Tests whether the index generated by the input indexing function matches the
// index of the span on which allocations and deallocation operations are
// carried out.  The test first allocates objects and deallocates them.  After
// each operation, the actual index is matched against the expected one.
template <typename IndexingFunc>
void TestIndexing(TypeParam& e, IndexingFunc f) {
  TC_ASSERT_GT(kNumLists, 0);
  const int num_objects_to_fetch = e.objects_per_span();
  std::vector<void*> objects(num_objects_to_fetch);
  size_t fetched = 0;
  int expected_idx = kNumLists - 1 + kNumLists;

  // Fetch one object at a time from a span and confirm that the span is moved
  // through the nonempty_ lists as we allocate more objects from it.
  while (fetched < num_objects_to_fetch) {
    // Try to fetch one object from the span.
    int got =
        e.central_freelist().RemoveRange(absl::MakeSpan(&objects[fetched], 1));
    fetched += got;
    TC_ASSERT(fetched);
    if (fetched % num_objects_to_fetch == 0) {
      // Span should have been removed from nonempty_ lists because we have
      // allocated all the objects from it.
      EXPECT_EQ(e.central_freelist().NumSpansInList(expected_idx), 0);
    } else {
      expected_idx = f(fetched);
      TC_ASSERT_GE(expected_idx, 0);
      TC_ASSERT_LT(expected_idx, kNumLists * 2);
      // Check that the span exists in the corresponding nonempty_ list.
      EXPECT_EQ(e.central_freelist().NumSpansInList(expected_idx), 1);
    }
  }

  // Similar to our previous test, we now make sure that the span is moved
  // through the nonempty_ lists when we deallocate objects back to it.
  size_t remaining = fetched;
  while (--remaining > 0) {
    // Return objects back to the span one at a time.
    e.central_freelist().InsertRange({&objects[remaining], 1});
    TC_ASSERT(remaining);
    // When allocated objects are more than the threshold, the span is indexed
    // to nonempty_ list 0.
    expected_idx = f(remaining);
    EXPECT_LT(expected_idx, kNumLists * 2);
    EXPECT_EQ(e.central_freelist().NumSpansInList(expected_idx), 1);
  }

  // When the last object is returned, we release the span to the page heap. So,
  // nonempty_[0] should also be empty.
  e.central_freelist().InsertRange({&objects[remaining], 1});
  EXPECT_EQ(e.central_freelist().NumSpansInList(0 + kNumLists), 0);
}

TEST_P(CentralFreeListTest, BitwidthIndexedNonEmptyLists) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  if (e.objects_per_span() <= 2 * kNumLists) {
    GTEST_SKIP()
        << "Skipping test as one hot encoding used for few object spans.";
  }
  auto bitwidth_indexing = [](size_t allocated) {
    size_t bitwidth = absl::bit_width(allocated);
    return kNumLists - std::min(bitwidth, kNumLists) + kNumLists;
  };
  TestIndexing(e, bitwidth_indexing);
}

TEST_P(CentralFreeListTest, DirectIndexedEncodedNonEmptyLists) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  if (e.objects_per_span() > 2 * kNumLists) {
    GTEST_SKIP() << "Skipping test as one hot encoding not required.";
  }
  auto direct_indexing = [](int allocated) {
    if (allocated <= kNumLists) return kNumLists - allocated + kNumLists;
    return kNumLists;
  };
  TestIndexing(e, direct_indexing);
}

// Checks if we are indexing a span in the nonempty_ lists as expected. We also
// check if the spans are correctly being prioritized. That is, we create a
// scenario where we have two live spans, and one span has more allocated
// objects than the other span. On subsequent allocations, we confirm that the
// objects are allocated from the span with a higher number of allocated objects
// as enforced by our prioritization scheme.
TEST_P(CentralFreeListTest, SpanPriority) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);

  // If the number of objects per span is less than 2, we do not use more than
  // one nonempty_ lists. So, we can not prioritize the spans based on how many
  // objects were allocated from them.
  const int objects_per_span = e.objects_per_span();
  if (objects_per_span < 3 || kNumLists < 2) return;

  constexpr int kNumSpans = 2;
  // Track objects allocated per span.
  absl::FixedArray<std::vector<void*>> objects(kNumSpans);
  void* batch[kMaxObjectsToMove];

  const size_t to_fetch = objects_per_span;
  // Allocate all objects from kNumSpans.
  for (int span = 0; span < kNumSpans; ++span) {
    size_t fetched = 0;
    while (fetched < to_fetch) {
      const size_t n = to_fetch - fetched;
      int got = e.central_freelist().RemoveRange(
          absl::MakeSpan(batch, std::min(n, e.batch_size())));
      for (int i = 0; i < got; ++i) {
        objects[span].push_back(batch[i]);
      }
      fetched += got;
    }
  }

  // Perform deallocations so that each span contains only two objects.
  size_t to_release = to_fetch - 2;
  for (int span = 0; span < kNumSpans; ++span) {
    size_t released = 0;
    while (released < to_release) {
      uint64_t n = std::min(to_release - released, e.batch_size());
      for (int i = 0; i < n; ++i) {
        batch[i] = objects[span][i + released];
      }
      released += n;
      e.central_freelist().InsertRange({batch, n});
    }
    objects[span].erase(objects[span].begin(),
                        objects[span].begin() + released);
  }

  // Make sure we have kNumSpans in the expected second-last nonempty_ list.
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 2 + kNumLists),
            kNumSpans);

  // Release an additional object from all but one spans so that they are
  // deprioritized for subsequent allocations.
  to_release = 1;
  for (int span = 1; span < kNumSpans; ++span) {
    size_t released = 0;
    while (released < to_release) {
      uint64_t n = std::min(to_release - released, e.batch_size());
      for (int i = 0; i < n; ++i) {
        batch[i] = objects[span][i + released];
      }
      released += n;
      e.central_freelist().InsertRange({batch, n});
    }
    objects[span].erase(objects[span].begin(),
                        objects[span].begin() + released);
  }

  // Make sure we have kNumSpans-1 spans in the last nonempty_ list and just one
  // span in the second-last list.
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 1 + kNumLists),
            kNumSpans - 1);
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 2 + kNumLists), 1);

  // Allocate one object to ensure that it is being allocated from the span with
  // the highest number of allocated objects.
  int got = e.central_freelist().RemoveRange(absl::MakeSpan(batch, 1));
  EXPECT_EQ(got, 1);
  // Number of spans in the last nonempty_ list should be unchanged (i.e.
  // kNumSpans-1).
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 1 + kNumLists),
            kNumSpans - 1);
  if (e.objects_per_span() == 3) {
    // Since we allocated another object from the span that had two objects
    // allocated from it, so the span would no longer be there in the span list.
    for (int i = kNumLists - 2; i >= 0; --i) {
      EXPECT_EQ(e.central_freelist().NumSpansInList(i + kNumLists), 0);
    }
  } else if (e.objects_per_span() <= 2 * kNumLists) {
    // We should have only one span in the third-last nonempty_ list; this is
    // the span from which we should have allocated the last object.
    EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 3 + kNumLists),
              1);
  } else {
    // We should have only one span in the second-last nonempty_ list; this is
    // the span from which we should have allocated the last object.
    EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 2 + kNumLists),
              1);
  }
  // Return previously allocated object.
  e.central_freelist().InsertRange({batch, 1});

  // Return rest of the objects.
  for (int span = 0; span < kNumSpans; ++span) {
    for (int i = 0; i < objects[span].size(); ++i) {
      e.central_freelist().InsertRange({&objects[span][i], 1});
    }
  }
}

struct SpanLifetimes {
  absl::flat_hash_map<size_t, size_t> live;
  absl::flat_hash_map<size_t, size_t> completed;
  void InitializeDefault() {
    live[0] = 0;
    completed[0] = 0;
    for (int i = 1; i <= 1000000; i *= 10) {
      live[i] = 0;
      completed[i] = 0;
    }
  }
};

void CheckLifetimeStats(TypeParam& e, SpanLifetimes span_lifetimes) {
  SpanLifetimes expected_lifetimes;
  expected_lifetimes.InitializeDefault();

  auto& live = expected_lifetimes.live;
  for (const auto& [key, value] : span_lifetimes.live) {
    live[key] = value;
  }

  auto& completed = expected_lifetimes.completed;
  for (const auto& [key, value] : span_lifetimes.completed) {
    completed[key] = value;
  }

  // Check txt stats
  std::string live_spans_txt = absl::StrFormat(
      R"(live spans:   0 ms <      %d,  1 ms <      %d, 10 ms <      %d,100 ms <      %d,1000 ms <      %d,10000 ms <      %d,100000 ms <      %d,1000000 ms <      %d)",
      live[0], live[1], live[10], live[100], live[1000], live[10000],
      live[100000], live[1000000]);

  std::string completed_spans_txt = absl::StrFormat(
      R"(completed spans:   0 ms <      %d,  1 ms <      %d, 10 ms <      %d,100 ms <      %d,1000 ms <      %d,10000 ms <      %d,100000 ms <      %d,1000000 ms <      %d)",
      completed[0], completed[1], completed[10], completed[100],
      completed[1000], completed[10000], completed[100000], completed[1000000]);

  // Move long-lived spans to the long-lived list. This should not impact
  // lifetime stats.
  e.central_freelist().HandleLongLivedSpans();

  std::string buffer = PrintToString(1024 * 1024, [&](Printer& printer) {
    e.central_freelist().PrintSpanLifetimeStats(printer);
  });

  EXPECT_THAT(buffer, testing::AllOf(testing::HasSubstr(completed_spans_txt),
                                     testing::HasSubstr(live_spans_txt)));

  // Check pbtxt stats
  std::vector<std::pair<size_t, size_t>> bounds = {
      {0, 1},        {1, 10},         {10, 100},         {100, 1000},
      {1000, 10000}, {10000, 100000}, {100000, 1000000}, {1000000, 1000000}};
  std::vector<std::string> live_spans_pbtxt;
  std::vector<std::string> completed_spans_pbtxt;
  for (auto [lower_bound, upper_bound] : bounds) {
    live_spans_pbtxt.push_back(absl::StrFormat(
        "span_lifetime_histogram { lower_bound: %d upper_bound: %d value: %d}",
        lower_bound, upper_bound, live[lower_bound]));
    completed_spans_pbtxt.push_back(
        absl::StrFormat("span_completed_lifetime_histogram { lower_bound: %d "
                        "upper_bound: %d value: %d}",
                        lower_bound, upper_bound, completed[lower_bound]));
  }

  std::string buffer_pbtxt =
      PrintToString(1024 * 1024, [&](PbtxtRegion& region) {
        e.central_freelist().PrintSpanLifetimeStatsInPbtxt(region);
      });
  EXPECT_THAT(
      buffer_pbtxt,
      testing::AllOf(
          testing::HasSubstr(absl::StrJoin(live_spans_pbtxt, " ")),
          testing::HasSubstr(absl::StrJoin(completed_spans_pbtxt, " "))));
}

TEST_P(CentralFreeListTest, HookTracing) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);

  static int insert_count = 0;
  static int remove_count = 0;
  insert_count = 0;
  remove_count = 0;
  auto insert_hook = [](size_t size_class, absl::Span<void*> batch) {
    insert_count += batch.size();
  };
  auto remove_hook = [](size_t size_class, absl::Span<void*> batch) {
    remove_count += batch.size();
  };

  EXPECT_TRUE(e.forwarder().insert_range_hooks_.Add(insert_hook));
  EXPECT_TRUE(e.forwarder().remove_range_hooks_.Add(remove_hook));

  void* batch[kMaxObjectsToMove];
  int got = e.central_freelist().RemoveRange(
      absl::MakeSpan(batch, std::min(size_t{1}, e.batch_size())));
  EXPECT_GT(got, 0);
  EXPECT_EQ(remove_count, got);

  e.central_freelist().InsertRange({batch, static_cast<size_t>(got)});
  EXPECT_EQ(insert_count, got);

  EXPECT_TRUE(e.forwarder().insert_range_hooks_.Remove(insert_hook));
  EXPECT_TRUE(e.forwarder().remove_range_hooks_.Remove(remove_hook));
}

TEST_P(CentralFreeListTest, SpanLifetime) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  // Skip the check for objects_per_span = 1 since such spans skip most of the
  // central freelist's logic.
  if (e.objects_per_span() == 1) {
    GTEST_SKIP() << "Skipping test for objects_per_span = 1.";
  }

  std::vector<void*> all_objects;
  // Request kNumSpans spans.
  void* batch[kMaxObjectsToMove];
  ASSERT_GT(e.objects_per_span(), 0);
  int got = e.central_freelist().RemoveRange(absl::MakeSpan(batch, 1));
  ASSERT_EQ(got, 1);

  e.forwarder().AdvanceClock(absl::Seconds(1));
  CheckLifetimeStats(e, {.live = {{1000, 1}}});

  e.forwarder().AdvanceClock(absl::Seconds(10));
  CheckLifetimeStats(e, {.live = {{10000, 1}}});

  e.forwarder().AdvanceClock(absl::Seconds(100));
  CheckLifetimeStats(e, {.live = {{100000, 1}}});

  e.forwarder().AdvanceClock(absl::Seconds(1000));
  CheckLifetimeStats(e, {.live = {{1000000, 1}}});

  e.forwarder().AdvanceClock(absl::Seconds(-1000));
  e.central_freelist().InsertRange({batch, 1});
  e.forwarder().AdvanceClock(absl::Seconds(1000));
  CheckLifetimeStats(e, {.completed = {{100000, 1}}});
}

TEST_P(CentralFreeListTest, SpanAllocationTracker) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);

  const int objects_per_span = e.objects_per_span();
  if (objects_per_span == 1) return;

  constexpr int kNumSpans = 5;
  // Track objects allocated per span.
  absl::FixedArray<std::vector<void*>> objects(kNumSpans);
  void* batch[kMaxObjectsToMove];

  const size_t to_fetch = objects_per_span;
  // Allocate all objects from kNumSpans.
  for (int span = 0; span < kNumSpans; ++span) {
    size_t fetched = 0;
    while (fetched < to_fetch) {
      const size_t n = to_fetch - fetched;
      int got = e.central_freelist().RemoveRange(
          absl::MakeSpan(batch, std::min(n, e.batch_size())));
      for (int i = 0; i < got; ++i) {
        objects[span].push_back(batch[i]);
      }
      fetched += got;
    }
  }

  // Perform deallocations so that each span contains only one free object.
  for (int span = 0; span < kNumSpans; ++span) {
    batch[0] = objects[span][0];
    e.central_freelist().InsertRange({batch, 1});
    objects[span].erase(objects[span].begin(), objects[span].begin() + 1);
  }

  // Calculate the expected number of allocations served by 1 span. These all
  // come from the case where there are no non-empty spans and a new span has to
  // be allocated.
  int single_spans = objects_per_span / e.batch_size();
  if (objects_per_span % e.batch_size() != 0) {
    single_spans++;
  }
  single_spans *= kNumSpans;

  size_t max_lower_bound = 1 << (absl::bit_width<size_t>(kNumSpans) - 1);
  size_t max_upper_bound = max_lower_bound * 2;

  // Check txt stats
  int got = e.central_freelist().RemoveRange(absl::MakeSpan(batch, kNumSpans));
  EXPECT_EQ(got, kNumSpans);
  std::string buffer = PrintToString(1024 * 1024, [&](Printer& printer) {
    e.central_freelist().PrintNumSpansUsed(printer);
  });
  EXPECT_THAT(
      buffer,
      testing::AllOf(
          testing::HasSubstr(absl::StrFormat("%v :        1", max_lower_bound)),
          testing::ContainsRegex(absl::StrFormat("1 : *%v, ", single_spans))));

  // Check pbtxt stats
  std::string buffer_pbtxt =
      PrintToString(1024 * 1024, [&](PbtxtRegion& region) {
        e.central_freelist().PrintNumSpansUsedInPbtxt(region);
      });
  EXPECT_THAT(buffer_pbtxt,
              testing::AllOf(testing::HasSubstr(absl::StrFormat(
                                 "{ lower_bound: %v upper_bound: %v value: 1}",
                                 max_lower_bound, max_upper_bound)),
                             testing::HasSubstr(absl::StrFormat(
                                 "{ lower_bound: 1 upper_bound: 2 value: %v}",
                                 single_spans))));
}

TEST_P(CentralFreeListTest, SameSpans) {
#ifdef TCMALLOC_INTERNAL_LEGACY_LOCKING
  GTEST_SKIP() << "Stats are non-functional when optimization is not enabled.";
#endif
  const int num_to_move = GetParam().num_to_move;
  TypeParam e(GetParam().size, GetParam().bytes, num_to_move);

  // Roundtrip a batch.
  void* batch[kMaxObjectsToMove];
  const int got =
      e.central_freelist().RemoveRange(absl::MakeSpan(batch, num_to_move));
  ASSERT_GT(got, 0);

  Span* spans[kMaxObjectsToMove];
  e.forwarder().MapObjectsToSpans(absl::MakeSpan(batch, got), spans,
                                  e.kSizeClass);
  absl::flat_hash_set<Span*> pseudo_spans;
  for (int i = 0; i < got; ++i) {
    pseudo_spans.insert(spans[i]);
  }

  e.central_freelist().InsertRange(absl::MakeSpan(batch, got));

  // Check the stats after the first insertion.
  {
    std::string expected_stats = absl::StrFormat(
        "class %3d [ %8zu bytes ] :", e.kSizeClass, GetParam().size);
    for (int i = 0; i < num_to_move; ++i) {
      const bool first_batch =
          e.objects_per_span() > 1 && i == got - pseudo_spans.size();
      const int count = first_batch ? 1 : 0;
      absl::StrAppendFormat(&expected_stats, " %6d", count);
    }
    absl::StrAppend(&expected_stats, "\n");

    std::string buffer = PrintToString(1024 * 1024, [&](Printer& printer) {
      e.central_freelist().PrintSameSpanStats(printer);
    });
    EXPECT_EQ(buffer, expected_stats) << got;
  }
  {
    std::string expected_pbtxt =
        e.objects_per_span() > 1
            ? absl::StrFormat(" same_span_stats { lower_bound: %d value: 1}",
                              got - pseudo_spans.size())
            : "";

    std::string buffer_pbtxt =
        PrintToString(1024 * 1024, [&](PbtxtRegion& region) {
          e.central_freelist().PrintSameSpanStatsInPbtxt(region);
        });
    EXPECT_EQ(buffer_pbtxt, expected_pbtxt) << got;
  }
}

TEST_P(CentralFreeListTest, MultipleSpans) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  std::vector<void*> all_objects;
  constexpr size_t kNumSpans = 10;

  // Request kNumSpans spans.
  void* batch[kMaxObjectsToMove];
  ASSERT_GT(e.objects_per_span(), 0);
  const int num_objects_to_fetch = kNumSpans * e.objects_per_span();
  int total_fetched = 0;
  while (total_fetched < num_objects_to_fetch) {
    size_t n = num_objects_to_fetch - total_fetched;
    int got = e.central_freelist().RemoveRange(
        absl::MakeSpan(batch, std::min(n, e.batch_size())));
    for (int i = 0; i < got; ++i) {
      all_objects.push_back(batch[i]);
    }
    total_fetched += got;
  }

  // We should have kNumSpans spans in the histogram with number of
  // allocated objects equal to e.objects_per_span() (i.e. in the last
  // bucket). Rest of the buckets should be empty.
  const int expected_bitwidth = absl::bit_width(e.objects_per_span());
  // Skip the check for objects_per_span = 1 since such spans skip most of the
  // central freelist's logic.
  if (e.objects_per_span() != 1) {
    EXPECT_EQ(e.central_freelist().NumSpansWith(expected_bitwidth), kNumSpans);
  }
  for (int i = 1; i < expected_bitwidth; ++i) {
    EXPECT_EQ(e.central_freelist().NumSpansWith(i), 0);
  }

  // Skip the check for objects_per_span = 1 since such spans skip most of the
  // central freelist's logic.
  if (e.objects_per_span() != 1) {
    SpanStats stats = e.central_freelist().GetSpanStats();
    EXPECT_EQ(stats.num_spans_requested, kNumSpans);
    EXPECT_EQ(stats.num_spans_returned, 0);
  }

  EXPECT_EQ(all_objects.size(), num_objects_to_fetch);

  // Shuffle
  absl::BitGen rng;
  std::shuffle(all_objects.begin(), all_objects.end(), rng);

  // Return all
  int total_returned = 0;
  while (total_returned < num_objects_to_fetch) {
    uint64_t size_to_pop =
        std::min(all_objects.size() - total_returned, e.batch_size());
    for (int i = 0; i < size_to_pop; ++i) {
      batch[i] = all_objects[i + total_returned];
    }
    total_returned += size_to_pop;
    e.central_freelist().InsertRange({batch, size_to_pop});
    // sanity check
    if (e.objects_per_span() != 1 && total_returned < num_objects_to_fetch) {
      SpanStats stats = e.central_freelist().GetSpanStats();
      EXPECT_GT(stats.num_spans_requested, stats.num_spans_returned);
      EXPECT_NE(stats.obj_capacity, 0);
      // Total spans recorded in the histogram must be equal to the number of
      // live spans.
      size_t spans_in_histogram = 0;
      for (int i = 1; i <= absl::bit_width(e.objects_per_span()); ++i) {
        spans_in_histogram += e.central_freelist().NumSpansWith(i);
      }
      EXPECT_EQ(spans_in_histogram, stats.num_live_spans());
    }
  }

  SpanStats stats = e.central_freelist().GetSpanStats();
  EXPECT_EQ(stats.num_spans_requested, stats.num_spans_returned);
  // Since no span is live, histogram must be empty.
  for (int i = 1; i <= absl::bit_width(e.objects_per_span()); ++i) {
    EXPECT_EQ(e.central_freelist().NumSpansWith(i), 0);
  }
  EXPECT_EQ(stats.obj_capacity, 0);
}

TEST_P(CentralFreeListTest, PassSpanDensityToPageheap) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);
  ASSERT_GE(e.objects_per_span(), 1);
  auto test_function = [&](size_t num_objects,
                           AccessDensityPrediction density) {
    std::vector<void*> objects(e.objects_per_span());
    EXPECT_CALL(e.forwarder(), AllocateSpan(testing::_, testing::_, testing::_))
        .Times(1);
    const size_t to_fetch = std::min(e.objects_per_span(), e.batch_size());
    const size_t fetched =
        e.central_freelist().RemoveRange(absl::MakeSpan(&objects[0], to_fetch));
    size_t returned = 0;
    while (returned < fetched) {
      EXPECT_CALL(e.forwarder(), DeallocateSpans(testing::_, testing::_))
          .Times(1);
      const size_t to_return = std::min(fetched - returned, e.batch_size());
      e.central_freelist().InsertRange({&objects[returned], to_return});
      returned += to_return;
    }
  };
  test_function(1, AccessDensityPrediction::kDense);
  test_function(e.objects_per_span(), AccessDensityPrediction::kDense);
}

TEST_P(CentralFreeListTest, SpanLifetimeWithLongLivedSpans) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);

  const int objects_per_span = e.objects_per_span();
  if (objects_per_span < 3) return;

  constexpr int kNumSpans = 5;
  // Track objects allocated per span.
  absl::FixedArray<std::vector<void*>> objects(kNumSpans);
  void* batch[kMaxObjectsToMove];

  const size_t to_fetch = objects_per_span;
  // Allocate all objects from kNumSpans.
  for (int span = 0; span < kNumSpans; ++span) {
    size_t fetched = 0;
    while (fetched < to_fetch) {
      const size_t n = to_fetch - fetched;
      int got = e.central_freelist().RemoveRange(
          absl::MakeSpan(batch, std::min(n, e.batch_size())));
      for (int i = 0; i < got; ++i) {
        objects[span].push_back(batch[i]);
      }
      fetched += got;
    }
    if (span == 0) {
      e.forwarder().AdvanceClock(
          central_freelist_internal::kLongLivedSpanThreshold -
          absl::Seconds(1));
    }
  }

  size_t to_release = to_fetch - 1;
  for (int span = 0; span < kNumSpans; ++span) {
    size_t released = 0;
    while (released < to_release) {
      uint64_t n = std::min(to_release - released, e.batch_size());
      for (int i = 0; i < n; ++i) {
        batch[i] = objects[span][i + released];
      }
      released += n;
      e.central_freelist().InsertRange({batch, n});
    }
    objects[span].erase(objects[span].begin(),
                        objects[span].begin() + released);
    // Release one object from each span after the long-lived span has been
    // processed. The other spans are more desirable from nalloc perspective,
    // but they won't be prioritized because of lifetime.
    to_release = 1;
  }

  // The first span should be in the last priority list of the normal batch,
  // before calling HandleLongLivedSpans. It only has one allocated object.
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 1 + kNumLists), 1);

  // This should be a no-op since we advanced the clock by less than
  // kLongLivedSpanThreshold.
  e.central_freelist().HandleLongLivedSpans();

  // The first span should be in the last priority list of the normal batch,
  // before calling HandleLongLivedSpans. It only has one allocated object.
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 1 + kNumLists), 1);

  // Advance the clock to make the first span a long-lived span. The others
  // shouldn't change.
  e.forwarder().AdvanceClock(absl::Seconds(2));
  e.central_freelist().HandleLongLivedSpans();

  // The long lived span should be in the last priority list of the long-lived
  // batch, after calling HandleLongLivedSpans.
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 1), 1);
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 1 + kNumLists), 0);

  int got = e.central_freelist().RemoveRange(absl::MakeSpan(batch, 1));
  objects[0].push_back(batch[0]);

  // The long lived span should be used for RemoveRange, even though it has the
  // fewest allocations. It should be moved to the second-last priority list of
  // the normal batch after allocation.
  EXPECT_EQ(got, 1);
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 2), 1);
  EXPECT_EQ(e.central_freelist().NumSpansInList(kNumLists - 1), 0);

  // Return the rest of the objects.
  for (int span = 0; span < kNumSpans; ++span) {
    for (int i = 0; i < objects[span].size(); ++i) {
      e.central_freelist().InsertRange({&objects[span][i], 1});
    }
  }
}

TEST_P(CentralFreeListTest, LongLivedSpansMovedHistogram) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);

  const int objects_per_span = e.objects_per_span();
  if (objects_per_span < 2) return;

  constexpr int kNumSpans =
      central_freelist_internal::kMaxLongLivedSpansToMove + 1;
  // Track objects allocated per span.
  absl::FixedArray<std::vector<void*>> objects(kNumSpans);
  void* batch[kMaxObjectsToMove];

  // Allocate all objects from kNumSpans.
  for (int span = 0; span < kNumSpans; ++span) {
    size_t fetched = 0;
    while (fetched < objects_per_span) {
      const size_t n = objects_per_span - fetched;
      int got = e.central_freelist().RemoveRange(
          absl::MakeSpan(batch, std::min(n, e.batch_size())));
      for (int i = 0; i < got; ++i) {
        objects[span].push_back(batch[i]);
      }
      fetched += got;
    }
  }

  // Release an object from each span so they're in the tracker
  for (int span = 0; span < kNumSpans; ++span) {
    batch[0] = objects[span][0];
    e.central_freelist().InsertRange({batch, 1});
    objects[span].erase(objects[span].begin());
  }

  // Advance the clock to make all spans long-lived.
  e.forwarder().AdvanceClock(
      central_freelist_internal::kLongLivedSpanThreshold * 2);
  // First run should move kMaxLongLivedSpansToMove spans.
  e.central_freelist().HandleLongLivedSpans();
  // Second run should move 1 span.
  e.central_freelist().HandleLongLivedSpans();
  // Third run should move 0 spans.
  e.central_freelist().HandleLongLivedSpans();

  std::string buffer = PrintToString(1024 * 1024, [&](Printer& printer) {
    e.central_freelist().PrintLongLivedSpansMoved(printer);
  });

  EXPECT_THAT(buffer, testing::HasSubstr(
                          "0 <      1,  1 <      1,  2 <      0,  4 <      0,  "
                          "8 <      1"));

  // Check pbtxt stats
  std::string buffer_pbtxt =
      PrintToString(1024 * 1024, [&](PbtxtRegion& region) {
        e.central_freelist().PrintLongLivedSpansMovedInPbtxt(region);
      });
  EXPECT_THAT(
      buffer_pbtxt,
      testing::HasSubstr(
          "long_lived_spans_moved_histogram { lower_bound: 0 upper_bound: 1 "
          "value: 1} long_lived_spans_moved_histogram { lower_bound: 1 "
          "upper_bound: 2 value: 1} long_lived_spans_moved_histogram { "
          "lower_bound: 2 upper_bound: 4 value: 0"
          "} long_lived_spans_moved_histogram { lower_bound: 4 upper_bound: 8 "
          "value: 0} long_lived_spans_moved_histogram { lower_bound: 8 "
          "upper_bound: 16 value: 1}"));

  // Return all objects.
  for (int span = 0; span < kNumSpans; ++span) {
    for (int i = 0; i < objects[span].size(); ++i) {
      e.central_freelist().InsertRange({&objects[span][i], 1});
    }
  }
}

TEST_P(CentralFreeListTest, ParallelHandleLongLivedSpans) {
#if ABSL_HAVE_HWADDRESS_SANITIZER
  GTEST_SKIP()
      << "Skipping under HWASan, which uses the top bits of the pointer.";
#endif

  std::atomic<bool> done(false);
  TypeParam e(GetParam().size, GetParam().bytes, GetParam().num_to_move);

  const int objects_per_span = e.objects_per_span();
  if (objects_per_span < 2) return;

  // Starting spans.
  constexpr int kNumSpans = 100;
  // Track objects allocated per span.
  std::vector<std::vector<void*>> objects(kNumSpans);
  void* batch[kMaxObjectsToMove];
  // void* batch_two[kMaxObjectsToMove];

  // Allocate all objects from kNumSpans.
  for (int span = 0; span < kNumSpans; ++span) {
    size_t fetched = 0;
    while (fetched < objects_per_span) {
      const size_t n = objects_per_span - fetched;
      int got = e.central_freelist().RemoveRange(
          absl::MakeSpan(batch, std::min(n, e.batch_size())));
      for (int i = 0; i < got; ++i) {
        objects[span].push_back(batch[i]);
      }
      fetched += got;
    }
  }

  // Release half of the objects from each span so they're in the tracker lists.
  size_t to_release = objects_per_span / 2;
  for (int span = 0; span < kNumSpans; ++span) {
    size_t released = 0;
    while (released < to_release) {
      uint64_t n = std::min(to_release - released, e.batch_size());
      for (int i = 0; i < n; ++i) {
        batch[i] = objects[span][i + released];
      }
      released += n;
      e.central_freelist().InsertRange({batch, n});
    }
    objects[span].erase(objects[span].begin(),
                        objects[span].begin() + released);
  }

  std::vector<void*> flat_objects[2];
  int i = 0;
  for (const auto& object_list : objects) {
    for (const auto& object : object_list) {
      if (i % 2 == 0) {
        flat_objects[0].push_back(object);
      } else {
        flat_objects[1].push_back(object);
      }
      i++;
    }
  }

  auto handle_long_lived_spans = [&]() {
    absl::BitGen rng;
    while (!done.load(std::memory_order_acquire)) {
      e.central_freelist().HandleLongLivedSpans();
    }
  };

  auto allocate_deallocate_advance = [&](std::vector<void*>& objects) {
    return [&]() {
      void* b[kMaxObjectsToMove];
      absl::BitGen rng;
      while (!done.load(std::memory_order_acquire)) {
        double fraction = absl::Uniform(rng, 0, 3.0);
        if (fraction < 1.0) {
          int got = e.central_freelist().RemoveRange(absl::MakeSpan(b, 1));
          EXPECT_EQ(got, 1);
          objects.push_back(b[0]);
        } else if (fraction < 2.0) {
          if (objects.empty()) continue;
          size_t index = absl::Uniform<size_t>(rng, 0, objects.size());
          e.central_freelist().InsertRange({&objects[index], 1});
          std::swap(objects[index], objects.back());
          objects.pop_back();
        } else {
          e.forwarder().AdvanceClock(
              central_freelist_internal::kLongLivedSpanThreshold / 10);
        }
      }
    };
  };

  std::thread threads[4] = {
      std::thread{handle_long_lived_spans},
      std::thread{handle_long_lived_spans},
      std::thread{allocate_deallocate_advance(flat_objects[0])},
      std::thread{allocate_deallocate_advance(flat_objects[1])}};

  absl::SleepFor(absl::Milliseconds(150));
  done = true;
  for (std::thread& thread : threads) {
    thread.join();
  }

  // Return all objects.
  for (const auto& objects : flat_objects) {
    for (void* object : objects) {
      e.central_freelist().InsertRange({&object, 1});
    }
  }
}

INSTANTIATE_TEST_SUITE_P(CentralFreeList, CentralFreeListTest,
                         // We skip the first size class since it is set to 0.
                         testing::ValuesIn(kSizeClasses.classes.begin() + 1,
                                           kSizeClasses.classes.end()));

}  // namespace
}  // namespace tcmalloc_internal
}  // namespace tcmalloc
