// 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 <algorithm>
#include <cstddef>
#include <limits>

#include "absl/base/attributes.h"
#include "absl/base/const_init.h"
#include "absl/synchronization/mutex.h"
#include "absl/time/clock.h"
#include "absl/time/time.h"
#include "tcmalloc/central_freelist.h"
#include "tcmalloc/common.h"
#include "tcmalloc/cpu_cache.h"
#include "tcmalloc/internal/logging.h"
#include "tcmalloc/internal/percpu.h"
#include "tcmalloc/internal_malloc_extension.h"
#include "tcmalloc/malloc_extension.h"
#include "tcmalloc/parameters.h"
#include "tcmalloc/static_vars.h"
#include "tcmalloc/stats.h"

// Release memory to the system at a constant rate.
void MallocExtension_Internal_ProcessBackgroundActions() {
  using ::tcmalloc::tcmalloc_internal::Parameters;
  using ::tcmalloc::tcmalloc_internal::tc_globals;

  tcmalloc::MallocExtension::MarkThreadIdle();

  absl::Time prev_time = absl::Now();
  absl::Time last_reclaim = prev_time;
  absl::Time last_shuffle = prev_time;
  absl::Time last_size_class_resize = prev_time;
  absl::Time last_size_class_max_capacity_resize = prev_time;
  absl::Time last_slab_resize_check = prev_time;
  absl::Time last_hpaa_hugepage_check = prev_time;
  absl::Time last_cfl_long_lived_check = prev_time;

#ifndef TCMALLOC_INTERNAL_SMALL_BUT_SLOW
  absl::Time last_transfer_cache_plunder_check = prev_time;
  absl::Time last_transfer_cache_resize_check = prev_time;
#endif

  // We use a separate release rate smoother from the one used by
  // ReleaseMemoryToSystem because a) we want to maintain a constant background
  // release rate, regardless of whether the user is releasing memory; and b) we
  // want to separately account for pages released by ProcessBackgroundActions.
  tcmalloc::tcmalloc_internal::ConstantRatePageAllocatorReleaser releaser;

  while (tcmalloc::MallocExtension::GetBackgroundProcessActionsEnabled()) {
    const absl::Duration sleep_time =
        tcmalloc::MallocExtension::GetBackgroundProcessSleepInterval();

    // Reclaim inactive per-cpu caches once per cpu_cache_shuffle_period.
    //
    // We use a longer 30 sleep cycle reclaim period to make sure that caches
    // are indeed idle. Reclaim drains entire cache, as opposed to cache shuffle
    // for instance that only shrinks a cache by a few objects at a time. So, we
    // might have larger performance degradation if we use a shorter reclaim
    // interval and drain caches that weren't supposed to.
    const absl::Duration cpu_cache_reclaim_period = 30 * sleep_time;

    // Shuffle per-cpu caches once per cpu_cache_shuffle_period.
    const absl::Duration cpu_cache_shuffle_period = 5 * sleep_time;

    const absl::Duration size_class_resize_period = 2 * sleep_time;
    const absl::Duration size_class_max_capacity_resize_period =
        29 * sleep_time;

    // See if we should resize the slab once per cpu_cache_slab_resize_period.
    // This period is coprime to cpu_cache_shuffle_period and
    // cpu_cache_shuffle_period.
    const absl::Duration cpu_cache_slab_resize_period = 29 * sleep_time;

#ifndef TCMALLOC_INTERNAL_SMALL_BUT_SLOW
    // We reclaim unused objects from the transfer caches once per
    // transfer_cache_plunder_period.
    const absl::Duration transfer_cache_plunder_period = 5 * sleep_time;
    // Resize transfer caches once per transfer_cache_resize_period.
    const absl::Duration transfer_cache_resize_period = 2 * sleep_time;
#endif

    // Iterate through hugepage trackers in TCMalloc's HugePageFiller. Apply
    // different treatments (e.g. usermode collapse, custom name sampled VMAs,
    // etc.) once every hpaa_hugepage_check_period.
    const absl::Duration hpaa_hugepage_check_period = 5 * sleep_time;

    // Iterate through all spans and move long-lived spans to the long-lived
    // section of nonempty_ once every cfl_long_lived_check_period.
    const absl::Duration cfl_long_lived_check_period = 5 * sleep_time;

    absl::Time now = absl::Now();

    // TODO(b/278618299):  We guard various actions under a single lock, since
    // individual operations may not be amenable to concurrent operations.
    {
      ABSL_CONST_INIT static absl::Mutex mu(absl::kConstInit);
      absl::MutexLock l(mu);

      // We follow the cache hierarchy in TCMalloc from outermost (per-CPU) to
      // innermost (the page heap).  Freeing up objects at one layer can help
      // aid memory coalescing for inner caches.

      if (tcmalloc::MallocExtension::PerCpuCachesActive()) {
        // Accelerate fences as part of this operation by registering this
        // thread with rseq.  While this is not strictly required to succeed, we
        // do not expect an inconsistent state for rseq (some threads registered
        // and some threads unable to).
        TC_CHECK(tcmalloc::tcmalloc_internal::subtle::percpu::IsFast());

        // Try to reclaim per-cpu caches once every cpu_cache_reclaim_period
        // when enabled.
        if (now - last_reclaim >= cpu_cache_reclaim_period) {
          tc_globals.cpu_cache().TryReclaimingCaches();
          last_reclaim = now;
        }

        if (now - last_shuffle >= cpu_cache_shuffle_period) {
          tc_globals.cpu_cache().ShuffleCpuCaches();
          last_shuffle = now;
        }

        if (now - last_size_class_resize >= size_class_resize_period) {
          tc_globals.cpu_cache().ResizeSizeClasses();
          last_size_class_resize = now;
        }

        if (Parameters::resize_size_class_max_capacity() &&
            now - last_size_class_max_capacity_resize >=
                size_class_max_capacity_resize_period) {
          tc_globals.cpu_cache().ResizeSizeClassMaxCapacities();
          last_size_class_max_capacity_resize = now;
        }

        // See if we need to grow the slab once every kCpuCacheSlabResizePeriod
        // when enabled.
        if (Parameters::per_cpu_caches_dynamic_slab_enabled() &&
            now - last_slab_resize_check >= cpu_cache_slab_resize_period) {
          tc_globals.cpu_cache().ResizeSlabIfNeeded();
          last_slab_resize_check = now;
        }

        tc_globals.cpu_cache().ClearTouchedCpus();
      }

      tc_globals.sharded_transfer_cache().Plunder();

#ifndef TCMALLOC_INTERNAL_SMALL_BUT_SLOW
      // Try to plunder and reclaim unused objects from transfer caches.
      if (now - last_transfer_cache_plunder_check >=
          transfer_cache_plunder_period) {
        tc_globals.transfer_cache().TryPlunder();
        last_transfer_cache_plunder_check = now;
      }

      if (now - last_transfer_cache_resize_check >=
          transfer_cache_resize_period) {
        tc_globals.transfer_cache().TryResizingCaches();
        last_transfer_cache_resize_check = now;
      }
#endif

      if (now - last_hpaa_hugepage_check >= hpaa_hugepage_check_period) {
        tc_globals.page_allocator().TreatHugepageTrackers(
            Parameters::usermode_hugepage_collapse());
        last_hpaa_hugepage_check = now;
      }

      if (Parameters::span_lifetime_tracking() ==
          tcmalloc::tcmalloc_internal::central_freelist_internal::
              LifetimeTracking::kEnabled) {
        if (now - last_cfl_long_lived_check >= cfl_long_lived_check_period) {
          for (int i = 0; i < tcmalloc::tcmalloc_internal::kNumClasses; ++i) {
            tc_globals.central_freelist(i).HandleLongLivedSpans();
          }
          last_cfl_long_lived_check = now;
        }
      }

      // If time goes backwards, we would like to cap the release rate at 0.
      //
      // TODO(b/495452446): Improve test coverage and possibly move to working
      // integer space entirely.
      double calculated_bytes =
          static_cast<size_t>(Parameters::background_release_rate()) *
          absl::ToDoubleSeconds(now - prev_time);
      constexpr double kMaxSsize =
          static_cast<double>(std::numeric_limits<ssize_t>::max());

      ssize_t bytes_to_release = calculated_bytes >= kMaxSsize
                                     ? std::numeric_limits<ssize_t>::max()
                                     : calculated_bytes;
      bytes_to_release = std::max<ssize_t>(bytes_to_release, 0);

      // If release rate is set to 0, do not release memory to system. However,
      // if we want to release free and backed hugepages from HugeRegion,
      // ReleaseMemoryToSystem should be able to release those pages to the
      // system even with bytes_to_release = 0.
      if (bytes_to_release > 0 ||
          Parameters::release_pages_from_huge_region()) {
        releaser.Release(bytes_to_release,
                         /*reason=*/tcmalloc::tcmalloc_internal::
                             PageReleaseReason::kProcessBackgroundActions);
      }

      prev_time = now;
    }

    absl::SleepFor(sleep_time);
  }
}
