// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

//
// Common definitions for the lockdep library.
//

#pragma once

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

#include <lockdep/runtime_api.h>

namespace lockdep {

// Configures the maximum number of dependencies each lock class may have. A
// system may override the default by globally defining this name to the desired
// value. This value is automatically converted to the next suitable prime.
#ifndef LOCK_DEP_MAX_DEPENDENCIES
#define LOCK_DEP_MAX_DEPENDENCIES 31
#endif

// Configures whether lock validation is enabled or not. Defaults to disabled.
// When disabled the locking utilities simply lock the underlying lock types,
// without performing any validation operations.
#ifndef LOCK_DEP_ENABLE_VALIDATION
#define LOCK_DEP_ENABLE_VALIDATION 0
#endif

// Id type used to identify each lock class.
using LockClassId = uintptr_t;

// A sentinel value indicating an empty slot in lock tracking data structures.
constexpr LockClassId kInvalidLockClassId = 0;

namespace internal {

// Returns a prime number that reasonably accommodates a hash table of the given
// number of entries. Each number is selected to be slightly less than twice the
// previous and as far as possible from the nearest two powers of two.
constexpr size_t NextPrime(size_t n) {
  if (n < (1 << 4))
    return 23;
  else if (n < (1 << 5))
    return 53;
  else if (n < (1 << 6))
    return 97;
  else if (n < (1 << 7))
    return 193;
  else if (n < (1 << 8))
    return 389;
  else if (n < (1 << 9))
    return 769;
  else if (n < (1 << 10))
    return 1543;
  else
    return 0;  // The input exceeds the size of this prime table.
}

}  // namespace internal

// The maximum number of dependencies each lock class may have. This is the
// maximum branching factor of the directed graph of locks managed by this
// lock dependency algorithm. The value is a prime number selected to optimize
// the hash map in LockDependencySet.
constexpr size_t kMaxLockDependencies = internal::NextPrime(LOCK_DEP_MAX_DEPENDENCIES);

// Check to make sure that the requested max does not exceed the prime table.
static_assert(kMaxLockDependencies != 0, "LOCK_DEP_MAX_DEPENDENCIES too large!");

// Whether or not lock validation is globally enabled.
constexpr bool kLockValidationEnabled = static_cast<bool>(LOCK_DEP_ENABLE_VALIDATION);

// Utility template alias to simplify selecting different types based whether
// lock validation is enabled or disabled.
template <typename EnabledType, typename DisabledType>
using IfLockValidationEnabled =
    typename std::conditional<kLockValidationEnabled, EnabledType, DisabledType>::type;

// Result type that represents whether a lock attempt was successful, or if not
// which check failed.
enum class LockResult : uint8_t {
  Success,
  AlreadyAcquired,
  OutOfOrder,
  InvalidNesting,
  InvalidIrqSafety,

  // Non-fatal error that indicates the dependency hash set for a particular
  // lock class is full. Consider increasing the size of the lock dependency
  // sets if this error is reported.
  MaxLockDependencies,

  // Internal error value used to differentiate between dependency set updates
  // that add a new edge and those that do not. Only new edges trigger loop
  // detection.
  DependencyExists,
};

// Returns a string representation of the given LockResult.
static inline const char* ToString(LockResult result) {
  switch (result) {
    case LockResult::Success:
      return "Success";
    case LockResult::AlreadyAcquired:
      return "Already Acquired";
    case LockResult::OutOfOrder:
      return "Out Of Order";
    case LockResult::InvalidNesting:
      return "Invalid Nesting";
    case LockResult::InvalidIrqSafety:
      return "Invalid Irq Safety";
    case LockResult::MaxLockDependencies:
      return "Max Lock Dependencies";
    case LockResult::DependencyExists:
      return "Dependency Exists";
    default:
      return "Unknown";
  }
}

}  // namespace lockdep