// Copyright 2019 The Abseil 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 "absl/strings/internal/cordz_handle.h"

#include <random>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/memory/memory.h"
#include "absl/synchronization/internal/thread_pool.h"
#include "absl/synchronization/notification.h"
#include "absl/time/clock.h"
#include "absl/time/time.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {
namespace {

using ::testing::ElementsAre;
using ::testing::Gt;
using ::testing::IsEmpty;
using ::testing::SizeIs;

// Local less verbose helper
std::vector<const CordzHandle*> DeleteQueue() {
  return CordzHandle::DiagnosticsGetDeleteQueue();
}

struct CordzHandleDeleteTracker : public CordzHandle {
  bool* deleted;
  explicit CordzHandleDeleteTracker(bool* deleted) : deleted(deleted) {}
  ~CordzHandleDeleteTracker() override { *deleted = true; }
};

TEST(CordzHandleTest, DeleteQueueIsEmpty) {
  EXPECT_THAT(DeleteQueue(), SizeIs(0));
}

TEST(CordzHandleTest, CordzHandleCreateDelete) {
  bool deleted = false;
  auto* handle = new CordzHandleDeleteTracker(&deleted);
  EXPECT_FALSE(handle->is_snapshot());
  EXPECT_TRUE(handle->SafeToDelete());
  EXPECT_THAT(DeleteQueue(), SizeIs(0));

  CordzHandle::Delete(handle);
  EXPECT_THAT(DeleteQueue(), SizeIs(0));
  EXPECT_TRUE(deleted);
}

TEST(CordzHandleTest, CordzSnapshotCreateDelete) {
  auto* snapshot = new CordzSnapshot();
  EXPECT_TRUE(snapshot->is_snapshot());
  EXPECT_TRUE(snapshot->SafeToDelete());
  EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot));
  delete snapshot;
  EXPECT_THAT(DeleteQueue(), SizeIs(0));
}

TEST(CordzHandleTest, CordzHandleCreateDeleteWithSnapshot) {
  bool deleted = false;
  auto* snapshot = new CordzSnapshot();
  auto* handle = new CordzHandleDeleteTracker(&deleted);
  EXPECT_FALSE(handle->SafeToDelete());

  CordzHandle::Delete(handle);
  EXPECT_THAT(DeleteQueue(), ElementsAre(handle, snapshot));
  EXPECT_FALSE(deleted);
  EXPECT_FALSE(handle->SafeToDelete());

  delete snapshot;
  EXPECT_THAT(DeleteQueue(), SizeIs(0));
  EXPECT_TRUE(deleted);
}

TEST(CordzHandleTest, MultiSnapshot) {
  bool deleted[3] = {false, false, false};

  CordzSnapshot* snapshot[3];
  CordzHandleDeleteTracker* handle[3];
  for (int i = 0; i < 3; ++i) {
    snapshot[i] = new CordzSnapshot();
    handle[i] = new CordzHandleDeleteTracker(&deleted[i]);
    CordzHandle::Delete(handle[i]);
  }

  EXPECT_THAT(DeleteQueue(), ElementsAre(handle[2], snapshot[2], handle[1],
                                         snapshot[1], handle[0], snapshot[0]));
  EXPECT_THAT(deleted, ElementsAre(false, false, false));

  delete snapshot[1];
  EXPECT_THAT(DeleteQueue(), ElementsAre(handle[2], snapshot[2], handle[1],
                                         handle[0], snapshot[0]));
  EXPECT_THAT(deleted, ElementsAre(false, false, false));

  delete snapshot[0];
  EXPECT_THAT(DeleteQueue(), ElementsAre(handle[2], snapshot[2]));
  EXPECT_THAT(deleted, ElementsAre(true, true, false));

  delete snapshot[2];
  EXPECT_THAT(DeleteQueue(), SizeIs(0));
  EXPECT_THAT(deleted, ElementsAre(true, true, deleted));
}

TEST(CordzHandleTest, DiagnosticsHandleIsSafeToInspect) {
  CordzSnapshot snapshot1;
  EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(nullptr));

  auto* handle1 = new CordzHandle();
  EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1));

  CordzHandle::Delete(handle1);
  EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1));

  CordzSnapshot snapshot2;
  auto* handle2 = new CordzHandle();
  EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1));
  EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle2));
  EXPECT_FALSE(snapshot2.DiagnosticsHandleIsSafeToInspect(handle1));
  EXPECT_TRUE(snapshot2.DiagnosticsHandleIsSafeToInspect(handle2));

  CordzHandle::Delete(handle2);
  EXPECT_TRUE(snapshot1.DiagnosticsHandleIsSafeToInspect(handle1));
}

TEST(CordzHandleTest, DiagnosticsGetSafeToInspectDeletedHandles) {
  EXPECT_THAT(DeleteQueue(), IsEmpty());

  auto* handle = new CordzHandle();
  auto* snapshot1 = new CordzSnapshot();

  // snapshot1 should be able to see handle.
  EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot1));
  EXPECT_TRUE(snapshot1->DiagnosticsHandleIsSafeToInspect(handle));
  EXPECT_THAT(snapshot1->DiagnosticsGetSafeToInspectDeletedHandles(),
              IsEmpty());

  // This handle will be safe to inspect as long as snapshot1 is alive. However,
  // since only snapshot1 can prove that it's alive, it will be hidden from
  // snapshot2.
  CordzHandle::Delete(handle);

  // This snapshot shouldn't be able to see handle because handle was already
  // sent to Delete.
  auto* snapshot2 = new CordzSnapshot();

  // DeleteQueue elements are LIFO order.
  EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot2, handle, snapshot1));

  EXPECT_TRUE(snapshot1->DiagnosticsHandleIsSafeToInspect(handle));
  EXPECT_FALSE(snapshot2->DiagnosticsHandleIsSafeToInspect(handle));

  EXPECT_THAT(snapshot1->DiagnosticsGetSafeToInspectDeletedHandles(),
              ElementsAre(handle));
  EXPECT_THAT(snapshot2->DiagnosticsGetSafeToInspectDeletedHandles(),
              IsEmpty());

  CordzHandle::Delete(snapshot1);
  EXPECT_THAT(DeleteQueue(), ElementsAre(snapshot2));

  CordzHandle::Delete(snapshot2);
  EXPECT_THAT(DeleteQueue(), IsEmpty());
}

// Create and delete CordzHandle and CordzSnapshot objects in multiple threads
// so that tsan has some time to chew on it and look for memory problems.
TEST(CordzHandleTest, MultiThreaded) {
  Notification stop;
  static constexpr int kNumThreads = 4;
  // Keep the number of handles relatively small so that the test will naturally
  // transition to an empty delete queue during the test. If there are, say, 100
  // handles, that will virtually never happen. With 10 handles and around 50k
  // iterations in each of 4 threads, the delete queue appears to become empty
  // around 200 times.
  static constexpr int kNumHandles = 10;

  // Each thread is going to pick a random index and atomically swap its
  // CordzHandle with one in handles. This way, each thread can avoid
  // manipulating a CordzHandle that might be operated upon in another thread.
  std::vector<std::atomic<CordzHandle*>> handles(kNumHandles);

  absl::synchronization_internal::ThreadPool pool(kNumThreads);

  for (int i = 0; i < kNumThreads; ++i) {
    pool.Schedule([&stop, &handles]() {
      std::minstd_rand gen;
      std::uniform_int_distribution<int> dist_type(0, 2);
      std::uniform_int_distribution<int> dist_handle(0, kNumHandles - 1);
      size_t max_safe_to_inspect = 0;
      while (!stop.HasBeenNotified()) {
        CordzHandle* handle;
        switch (dist_type(gen)) {
          case 0:
            handle = new CordzHandle();
            break;
          case 1:
            handle = new CordzSnapshot();
            break;
          default:
            handle = nullptr;
            break;
        }
        CordzHandle* old_handle = handles[dist_handle(gen)].exchange(handle);
        if (old_handle != nullptr) {
          std::vector<const CordzHandle*> safe_to_inspect =
              old_handle->DiagnosticsGetSafeToInspectDeletedHandles();
          for (const CordzHandle* handle : safe_to_inspect) {
            // We're in a tight loop, so don't generate too many error messages.
            ASSERT_FALSE(handle->is_snapshot());
          }
          if (safe_to_inspect.size() > max_safe_to_inspect) {
            max_safe_to_inspect = safe_to_inspect.size();
          }
          CordzHandle::Delete(old_handle);
        }
      }

      // Confirm that the test did *something*. This check will be satisfied as
      // long as this thread has delete a CordzSnapshot object and a
      // non-snapshot CordzHandle was deleted after the CordzSnapshot was
      // created. This max_safe_to_inspect count will often reach around 30
      // (assuming 4 threads and 10 slots for live handles). Don't use a strict
      // bound to avoid making this test flaky.
      EXPECT_THAT(max_safe_to_inspect, Gt(0));

      // Have each thread attempt to clean up everything. Some thread will be
      // the last to reach this cleanup code, and it will be guaranteed to clean
      // up everything because nothing remains to create new handles.
      for (auto& h : handles) {
        if (CordzHandle* handle = h.exchange(nullptr)) {
          CordzHandle::Delete(handle);
        }
      }
  });
  }

  // The threads will hammer away.  Give it a little bit of time for tsan to
  // spot errors.
  absl::SleepFor(absl::Seconds(3));
  stop.Notify();
}

}  // namespace
}  // namespace cord_internal
ABSL_NAMESPACE_END
}  // namespace absl