<commit_before>// Copyright 2020 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.

#ifndef TCMALLOC_TRANSFER_CACHE_INTERNAL_H_
#define TCMALLOC_TRANSFER_CACHE_INTERNAL_H_

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

#include <limits>

#include "tcmalloc/internal/config.h"

#ifdef __x86_64__
#include <emmintrin.h>
#include <xmmintrin.h>
#endif

#include <algorithm>
#include <atomic>
#include <cstddef>
#include <utility>

#include "absl/base/attributes.h"
#include "absl/base/casts.h"
#include "absl/base/const_init.h"
#include "absl/base/internal/spinlock.h"
#include "absl/base/macros.h"
#include "absl/base/optimization.h"
#include "absl/base/thread_annotations.h"
#include "absl/synchronization/internal/futex.h"
#include "absl/types/optional.h"
#include "absl/types/span.h"
#include "tcmalloc/central_freelist.h"
#include "tcmalloc/common.h"
#include "tcmalloc/experiment.h"
#include "tcmalloc/internal/logging.h"
#include "tcmalloc/tracking.h"
#include "tcmalloc/transfer_cache_stats.h"

GOOGLE_MALLOC_SECTION_BEGIN
namespace tcmalloc::tcmalloc_internal::internal_transfer_cache {

struct alignas(8) SizeInfo {
  int32_t used;
  int32_t capacity;
};

// TransferCache is used to cache transfers of
// sizemap.num_objects_to_move(size_class) back and forth between
// thread caches and the central cache for a given size class.
template <typename CentralFreeList, typename TransferCacheManager>
class TransferCache {
 public:
  using Manager = TransferCacheManager;
  using FreeList = CentralFreeList;

  static constexpr int kMaxCapacityInBatches = 64;
  static constexpr int kInitialCapacityInBatches = 16;

  constexpr explicit TransferCache(Manager *owner) : TransferCache(owner, 0) {}

  // C++11 has complex rules for direct initialization of an array of aggregate
  // types that are not copy constructible.  The int parameters allows us to do
  // two distinct things at the same time:
  //  - have an implicit constructor (one arg implicit ctors are dangerous)
  //  - build an array of these in an arg pack expansion without a comma
  //    operator trick
  constexpr TransferCache(Manager *owner, int)
      : owner_(owner),
        lock_(absl::kConstInit, absl::base_internal::SCHEDULE_KERNEL_ONLY),
        max_capacity_(0),
        insert_hits_(0),
        remove_hits_(0),
        insert_misses_(0),
        remove_misses_(0),
        slot_info_{},
        slots_(nullptr),
        freelist_do_not_access_directly_() {}

  TransferCache(const TransferCache &) = delete;
  TransferCache &operator=(const TransferCache &) = delete;

  // We require the pageheap_lock with some templates, but not in tests, so the
  // thread safety analysis breaks pretty hard here.
  void Init(size_t cl) ABSL_NO_THREAD_SAFETY_ANALYSIS {
    freelist().Init(cl);
    absl::base_internal::SpinLockHolder h(&lock_);

    // We need at least 2 slots to store list head and tail.
    ASSERT(kMinObjectsToMove >= 2);

    slots_ = nullptr;
    max_capacity_ = 0;
    SizeInfo info = {0, 0};

    size_t bytes = Manager::class_to_size(cl);
    if (cl > 0 && bytes > 0) {
      // Limit the maximum size of the cache based on the size class.  If this
      // is not done, large size class objects will consume a lot of memory if
      // they just sit in the transfer cache.
      size_t objs_to_move = Manager::num_objects_to_move(cl);
      ASSERT(objs_to_move > 0 && bytes > 0);

      // Starting point for the maximum number of entries in the transfer cache.
      // This actual maximum for a given size class may be lower than this
      // maximum value.
      max_capacity_ = kMaxCapacityInBatches * objs_to_move;
      // A transfer cache freelist can have anywhere from 0 to
      // max_capacity_ slots to put link list chains into.
      info.capacity = kInitialCapacityInBatches * objs_to_move;

      // Limit each size class cache to at most 1MB of objects or one entry,
      // whichever is greater. Total transfer cache memory used across all
      // size classes then can't be greater than approximately
      // 1MB * kMaxNumTransferEntries.
      max_capacity_ = std::min<size_t>(
          max_capacity_,
          std::max<size_t>(
              objs_to_move,
              (1024 * 1024) / (bytes * objs_to_move) * objs_to_move));
      info.capacity = std::min(info.capacity, max_capacity_);
      slots_ = reinterpret_cast<void **>(
          owner_->Alloc(max_capacity_ * sizeof(void *)));
    }
    SetSlotInfo(info);
  }

  bool IsFlexible() { return false; }

  // These methods all do internal locking.

  // Insert the specified batch into the transfer cache.  N is the number of
  // elements in the range.  RemoveRange() is the opposite operation.
  void InsertRange(absl::Span<void *> batch, int N) ABSL_LOCKS_EXCLUDED(lock_) {
    const int B = Manager::num_objects_to_move(size_class());
    ASSERT(0 < N && N <= B);
    auto info = slot_info_.load(std::memory_order_relaxed);
    if (N == B && info.used + N <= max_capacity_) {
      absl::base_internal::SpinLockHolder h(&lock_);
      if (MakeCacheSpace()) {
        // MakeCacheSpace can drop the lock, so refetch
        info = slot_info_.load(std::memory_order_relaxed);
        info.used += N;
        SetSlotInfo(info);

        void **entry = GetSlot(info.used - N);
        memcpy(entry, batch.data(), sizeof(void *) * N);
        tracking::Report(kTCInsertHit, size_class(), 1);
        insert_hits_++;
        return;
      }
    }
    insert_misses_.fetch_add(1, std::memory_order_relaxed);
    tracking::Report(kTCInsertMiss, size_class(), 1);
    freelist().InsertRange(batch.data(), N);
  }

  // Returns the actual number of fetched elements and stores elements in the
  // batch.
  ABSL_MUST_USE_RESULT int RemoveRange(void **batch, int N)
      ABSL_LOCKS_EXCLUDED(lock_) {
    ASSERT(N > 0);
    const int B = Manager::num_objects_to_move(size_class());
    int fetch = 0;
    auto info = slot_info_.load(std::memory_order_relaxed);
    if (N == B && info.used >= N) {
      absl::base_internal::SpinLockHolder h(&lock_);
      // Refetch with the lock
      info = slot_info_.load(std::memory_order_relaxed);
      if (info.used >= N) {
        info.used -= N;
        SetSlotInfo(info);
        void **entry = GetSlot(info.used);
        memcpy(batch, entry, sizeof(void *) * N);
        tracking::Report(kTCRemoveHit, size_class(), 1);
        remove_hits_++;
        return N;
      }
    }
    remove_misses_.fetch_add(1, std::memory_order_relaxed);
    tracking::Report(kTCRemoveMiss, size_class(), 1);
    return freelist().RemoveRange(batch + fetch, N - fetch) + fetch;
  }

  // Returns the number of free objects in the central cache.
  size_t central_length() { return freelist().length(); }

  // Returns the number of free objects in the transfer cache.
  size_t tc_length() {
    return static_cast<size_t>(slot_info_.load(std::memory_order_relaxed).used);
  }

  // Returns the number of spans allocated and deallocated from the CFL
  SpanStats GetSpanStats() const { return freelist().GetSpanStats(); }

  // Returns the number of transfer cache insert/remove hits/misses.
  TransferCacheStats GetHitRateStats() ABSL_LOCKS_EXCLUDED(lock_) {
    TransferCacheStats stats;
    {
      absl::base_internal::SpinLockHolder h(&lock_);
      stats.insert_hits = insert_hits_;
      stats.remove_hits = remove_hits_;<commit_msg>Remove dead code.<commit_after>// Copyright 2020 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.

#ifndef TCMALLOC_TRANSFER_CACHE_INTERNAL_H_
#define TCMALLOC_TRANSFER_CACHE_INTERNAL_H_

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

#include <limits>

#include "tcmalloc/internal/config.h"

#ifdef __x86_64__
#include <emmintrin.h>
#include <xmmintrin.h>
#endif

#include <algorithm>
#include <atomic>
#include <cstddef>
#include <utility>

#include "absl/base/attributes.h"
#include "absl/base/casts.h"
#include "absl/base/const_init.h"
#include "absl/base/internal/spinlock.h"
#include "absl/base/macros.h"
#include "absl/base/optimization.h"
#include "absl/base/thread_annotations.h"
#include "absl/synchronization/internal/futex.h"
#include "absl/types/optional.h"
#include "absl/types/span.h"
#include "tcmalloc/central_freelist.h"
#include "tcmalloc/common.h"
#include "tcmalloc/experiment.h"
#include "tcmalloc/internal/logging.h"
#include "tcmalloc/tracking.h"
#include "tcmalloc/transfer_cache_stats.h"

GOOGLE_MALLOC_SECTION_BEGIN
namespace tcmalloc::tcmalloc_internal::internal_transfer_cache {

struct alignas(8) SizeInfo {
  int32_t used;
  int32_t capacity;
};

// TransferCache is used to cache transfers of
// sizemap.num_objects_to_move(size_class) back and forth between
// thread caches and the central cache for a given size class.
template <typename CentralFreeList, typename TransferCacheManager>
class TransferCache {
 public:
  using Manager = TransferCacheManager;
  using FreeList = CentralFreeList;

  static constexpr int kMaxCapacityInBatches = 64;
  static constexpr int kInitialCapacityInBatches = 16;

  constexpr explicit TransferCache(Manager *owner) : TransferCache(owner, 0) {}

  // C++11 has complex rules for direct initialization of an array of aggregate
  // types that are not copy constructible.  The int parameters allows us to do
  // two distinct things at the same time:
  //  - have an implicit constructor (one arg implicit ctors are dangerous)
  //  - build an array of these in an arg pack expansion without a comma
  //    operator trick
  constexpr TransferCache(Manager *owner, int)
      : owner_(owner),
        lock_(absl::kConstInit, absl::base_internal::SCHEDULE_KERNEL_ONLY),
        max_capacity_(0),
        insert_hits_(0),
        remove_hits_(0),
        insert_misses_(0),
        remove_misses_(0),
        slot_info_{},
        slots_(nullptr),
        freelist_do_not_access_directly_() {}

  TransferCache(const TransferCache &) = delete;
  TransferCache &operator=(const TransferCache &) = delete;

  // We require the pageheap_lock with some templates, but not in tests, so the
  // thread safety analysis breaks pretty hard here.
  void Init(size_t cl) ABSL_NO_THREAD_SAFETY_ANALYSIS {
    freelist().Init(cl);
    absl::base_internal::SpinLockHolder h(&lock_);

    // We need at least 2 slots to store list head and tail.
    ASSERT(kMinObjectsToMove >= 2);

    slots_ = nullptr;
    max_capacity_ = 0;
    SizeInfo info = {0, 0};

    size_t bytes = Manager::class_to_size(cl);
    if (cl > 0 && bytes > 0) {
      // Limit the maximum size of the cache based on the size class.  If this
      // is not done, large size class objects will consume a lot of memory if
      // they just sit in the transfer cache.
      size_t objs_to_move = Manager::num_objects_to_move(cl);
      ASSERT(objs_to_move > 0 && bytes > 0);

      // Starting point for the maximum number of entries in the transfer cache.
      // This actual maximum for a given size class may be lower than this
      // maximum value.
      max_capacity_ = kMaxCapacityInBatches * objs_to_move;
      // A transfer cache freelist can have anywhere from 0 to
      // max_capacity_ slots to put link list chains into.
      info.capacity = kInitialCapacityInBatches * objs_to_move;

      // Limit each size class cache to at most 1MB of objects or one entry,
      // whichever is greater. Total transfer cache memory used across all
      // size classes then can't be greater than approximately
      // 1MB * kMaxNumTransferEntries.
      max_capacity_ = std::min<size_t>(
          max_capacity_,
          std::max<size_t>(
              objs_to_move,
              (1024 * 1024) / (bytes * objs_to_move) * objs_to_move));
      info.capacity = std::min(info.capacity, max_capacity_);
      slots_ = reinterpret_cast<void **>(
          owner_->Alloc(max_capacity_ * sizeof(void *)));
    }
    SetSlotInfo(info);
  }

  bool IsFlexible() { return false; }

  // These methods all do internal locking.

  // Insert the specified batch into the transfer cache.  N is the number of
  // elements in the range.  RemoveRange() is the opposite operation.
  void InsertRange(absl::Span<void *> batch, int N) ABSL_LOCKS_EXCLUDED(lock_) {
    const int B = Manager::num_objects_to_move(size_class());
    ASSERT(0 < N && N <= B);
    auto info = slot_info_.load(std::memory_order_relaxed);
    if (N == B && info.used + N <= max_capacity_) {
      absl::base_internal::SpinLockHolder h(&lock_);
      if (MakeCacheSpace()) {
        // MakeCacheSpace can drop the lock, so refetch
        info = slot_info_.load(std::memory_order_relaxed);
        info.used += N;
        SetSlotInfo(info);

        void **entry = GetSlot(info.used - N);
        memcpy(entry, batch.data(), sizeof(void *) * N);
        tracking::Report(kTCInsertHit, size_class(), 1);
        insert_hits_++;
        return;
      }
    }
    insert_misses_.fetch_add(1, std::memory_order_relaxed);
    tracking::Report(kTCInsertMiss, size_class(), 1);
    freelist().InsertRange(batch.data(), N);
  }

  // Returns the actual number of fetched elements and stores elements in the
  // batch.
  ABSL_MUST_USE_RESULT int RemoveRange(void **batch, int N)
      ABSL_LOCKS_EXCLUDED(lock_) {
    ASSERT(N > 0);
    const int B = Manager::num_objects_to_move(size_class());
    auto info = slot_info_.load(std::memory_order_relaxed);
    if (N == B && info.used >= N) {
      absl::base_internal::SpinLockHolder h(&lock_);
      // Refetch with the lock
      info = slot_info_.load(std::memory_order_relaxed);
      if (info.used >= N) {
        info.used -= N;
        SetSlotInfo(info);
        void **entry = GetSlot(info.used);
        memcpy(batch, entry, sizeof(void *) * N);
        tracking::Report(kTCRemoveHit, size_class(), 1);
        remove_hits_++;
        return N;
      }
    }
    remove_misses_.fetch_add(1, std::memory_order_relaxed);
    tracking::Report(kTCRemoveMiss, size_class(), 1);
    return freelist().RemoveRange(batch, N);
  }

  // Returns the number of free objects in the central cache.
  size_t central_length() { return freelist().length(); }

  // Returns the number of free objects in the transfer cache.
  size_t tc_length() {
    return static_cast<size_t>(slot_info_.load(std::memory_order_relaxed).used);
  }

  // Returns the number of spans allocated and deallocated from the CFL
  SpanStats GetSpanStats() const { return freelist().GetSpanStats(); }

  // Returns the number of transfer cache insert/remove hits/misses.
  TransferCacheStats GetHitRateStats() ABSL_LOCKS_EXCLUDED(lock_) {
    TransferCacheStats stats;
    {
      absl::base_internal::SpinLockHolder h(&lock_);
      stats.insert_hits = insert_hits_;
      stats.remove_hits = remove_hits_;
{'fraction_non_alphanumeric': 0.1049488596658408, 'fraction_numerical': 0.007305762022743155, 'mean_word_length': 3.4331174317093778, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 53, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '506421', 'n_tokens_mistral': 4996, 'n_tokens_neox': 4812, 'n_words': 1431}