//  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
//  This source code is licensed under both the GPLv2 (found in the
//  COPYING file in the root directory) and Apache 2.0 License
//  (found in the LICENSE.Apache file in the root directory).
//
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "cache/sharded_cache.h"

#include <algorithm>
#include <cstdint>
#include <memory>

#include "env/unique_id_gen.h"
#include "rocksdb/env.h"
#include "util/hash.h"
#include "util/math.h"
#include "util/mutexlock.h"

namespace ROCKSDB_NAMESPACE {
namespace {
// The generated seeds must fit in 31 bits so that
// ShardedCacheOptions::hash_seed can be set to it explicitly, for
// diagnostic/debugging purposes.
constexpr uint32_t kSeedMask = 0x7fffffff;
uint32_t DetermineSeed(int32_t hash_seed_option) {
  if (hash_seed_option >= 0) {
    // User-specified exact seed
    return static_cast<uint32_t>(hash_seed_option);
  }
  static SemiStructuredUniqueIdGen gen;
  if (hash_seed_option == ShardedCacheOptions::kHostHashSeed) {
    std::string hostname;
    Status s = Env::Default()->GetHostNameString(&hostname);
    if (s.ok()) {
      return GetSliceHash(hostname) & kSeedMask;
    } else {
      // Fall back on something stable within the process.
      return static_cast<uint32_t>(gen.GetBaseUpper()) & kSeedMask;
    }
  } else {
    // for kQuasiRandomHashSeed and fallback
    uint32_t val = gen.GenerateNext<uint32_t>() & kSeedMask;
    // Perform some 31-bit bijective transformations so that we get
    // quasirandom, not just incrementing. (An incrementing seed from a
    // random starting point would be fine, but hard to describe in a name.)
    // See https://en.wikipedia.org/wiki/Quasirandom and using a murmur-like
    // transformation here for our bijection in the lower 31 bits.
    // See https://en.wikipedia.org/wiki/MurmurHash
    val *= /*31-bit prime*/ 1150630961;
    val ^= (val & kSeedMask) >> 17;
    val *= /*31-bit prime*/ 1320603883;
    return val & kSeedMask;
  }
}
}  // namespace

ShardedCacheBase::ShardedCacheBase(const ShardedCacheOptions& opts)
    : Cache(opts.memory_allocator),
      last_id_(1),
      shard_mask_((uint32_t{1} << opts.num_shard_bits) - 1),
      hash_seed_(DetermineSeed(opts.hash_seed)),
      strict_capacity_limit_(opts.strict_capacity_limit),
      capacity_(opts.capacity) {}

size_t ShardedCacheBase::ComputePerShardCapacity(size_t capacity) const {
  uint32_t num_shards = GetNumShards();
  return (capacity + (num_shards - 1)) / num_shards;
}

size_t ShardedCacheBase::GetPerShardCapacity() const {
  return ComputePerShardCapacity(GetCapacity());
}

uint64_t ShardedCacheBase::NewId() {
  return last_id_.fetch_add(1, std::memory_order_relaxed);
}

size_t ShardedCacheBase::GetCapacity() const {
  MutexLock l(&config_mutex_);
  return capacity_;
}

bool ShardedCacheBase::HasStrictCapacityLimit() const {
  MutexLock l(&config_mutex_);
  return strict_capacity_limit_;
}

size_t ShardedCacheBase::GetUsage(Handle* handle) const {
  return GetCharge(handle);
}

std::string ShardedCacheBase::GetPrintableOptions() const {
  std::string ret;
  ret.reserve(20000);
  const int kBufferSize = 200;
  char buffer[kBufferSize];
  {
    MutexLock l(&config_mutex_);
    snprintf(buffer, kBufferSize, "    capacity : %" ROCKSDB_PRIszt "\n",
             capacity_);
    ret.append(buffer);
    snprintf(buffer, kBufferSize, "    num_shard_bits : %d\n",
             GetNumShardBits());
    ret.append(buffer);
    snprintf(buffer, kBufferSize, "    strict_capacity_limit : %d\n",
             strict_capacity_limit_);
    ret.append(buffer);
  }
  snprintf(buffer, kBufferSize, "    memory_allocator : %s\n",
           memory_allocator() ? memory_allocator()->Name() : "None");
  ret.append(buffer);
  AppendPrintableOptions(ret);
  return ret;
}

int GetDefaultCacheShardBits(size_t capacity, size_t min_shard_size) {
  int num_shard_bits = 0;
  size_t num_shards = capacity / min_shard_size;
  while (num_shards >>= 1) {
    if (++num_shard_bits >= 6) {
      // No more than 6.
      return num_shard_bits;
    }
  }
  return num_shard_bits;
}

int ShardedCacheBase::GetNumShardBits() const {
  return BitsSetToOne(shard_mask_);
}

uint32_t ShardedCacheBase::GetNumShards() const { return shard_mask_ + 1; }

}  // namespace ROCKSDB_NAMESPACE