/** @file

  Implementation of nexthop consistent hash selections strategies.

  @section license License

  Licensed to the Apache Software Foundation (ASF) under one
  or more contributor license agreements.  See the NOTICE file
  distributed with this work for additional information
  regarding copyright ownership.  The ASF licenses this file
  to you 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

      http://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 <yaml-cpp/yaml.h>

#include "proxy/http/HttpSM.h"
#include "iocore/utils/Machine.h"
#include "tsutil/YamlCfg.h"
#include "proxy/http/remap/NextHopConsistentHash.h"
#include "proxy/ParentSelection.h"

// hash_key strings.
constexpr std::string_view hash_key_url           = "url";
constexpr std::string_view hash_key_hostname      = "hostname";
constexpr std::string_view hash_key_path          = "path";
constexpr std::string_view hash_key_path_query    = "path+query";
constexpr std::string_view hash_key_path_fragment = "path+fragment";
constexpr std::string_view hash_key_cache         = "cache_key";

// hash_url strings
constexpr std::string_view hash_url_request = "request";
constexpr std::string_view hash_url_cache   = "cache";
constexpr std::string_view hash_url_parent  = "parent";

static bool
isWrapped(std::vector<bool> &wrap_around, uint32_t groups)
{
  bool all_wrapped = true;
  for (uint32_t c = 0; c < groups; c++) {
    if (wrap_around[c] == false) {
      all_wrapped = false;
    }
  }
  return all_wrapped;
}

std::shared_ptr<HostRecord>
NextHopConsistentHash::chashLookup(const std::shared_ptr<ATSConsistentHash> &ring, uint32_t cur_ring, ParentResult &result,
                                   HttpRequestData &request_info, bool *wrapped, uint64_t sm_id)
{
  uint64_t                   hash_key = 0;
  std::unique_ptr<ATSHash64> hash     = createHashInstance(parseHashAlgorithm(hash_algorithm), hash_seed0, hash_seed1);
  HostRecord                *host_rec = nullptr;
  ATSConsistentHashIter     *iter     = &result.chashIter[cur_ring];

  if (result.chash_init[cur_ring] == false) {
    hash_key                    = getHashKey(sm_id, request_info, hash.get());
    host_rec                    = static_cast<HostRecord *>(ring->lookup_by_hashval(hash_key, iter, wrapped));
    result.chash_init[cur_ring] = true;
  } else {
    host_rec = static_cast<HostRecord *>(ring->lookup(nullptr, iter, wrapped, hash.get()));
  }
  bool wrap_around = *wrapped;
  *wrapped         = (result.mapWrapped[cur_ring] && *wrapped) ? true : false;
  if (!result.mapWrapped[cur_ring] && wrap_around) {
    result.mapWrapped[cur_ring] = true;
  }

  if (host_rec == nullptr) {
    return nullptr;
  } else {
    std::shared_ptr<HostRecord> h = host_groups[host_rec->group_index][host_rec->host_index];
    return h;
  }
}

NextHopConsistentHash::~NextHopConsistentHash()
{
  NH_Dbg(NH_DBG_CTL, "destructor called for strategy named: %s", strategy_name.c_str());
}

NextHopConsistentHash::NextHopConsistentHash(const std::string_view name, const NHPolicyType &policy, ts::Yaml::Map &n)
  : NextHopSelectionStrategy(name, policy, n)
{
  std::unique_ptr<ATSHash64> hash;

  try {
    if (n["hash_url"]) {
      auto hash_url_val = n["hash_url"].Scalar();
      if (hash_url_val == hash_url_request) {
        hash_url = NHHashUrlType::REQUEST;
      } else if (hash_url_val == hash_url_cache) {
        hash_url = NHHashUrlType::CACHE;
      } else if (hash_url_val == hash_url_parent) {
        hash_url = NHHashUrlType::PARENT;
      } else {
        hash_url = NHHashUrlType::REQUEST;
        NH_Note("Invalid 'hash_url' value, '%s', for the strategy named '%s', using default '%s'.", hash_url_val.c_str(),
                strategy_name.c_str(), hash_url_request.data());
      }
    }
  } catch (std::exception &ex) {
    throw std::invalid_argument("Error parsing the strategy named '" + strategy_name + "' due to '" + ex.what() +
                                "', this strategy will be ignored.");
  }

  try {
    if (n["hash_key"]) {
      auto hash_key_val = n["hash_key"].Scalar();
      if (hash_key_val == hash_key_url) {
        hash_key = NHHashKeyType::URL_HASH_KEY;
      } else if (hash_key_val == hash_key_hostname) {
        hash_key = NHHashKeyType::HOSTNAME_HASH_KEY;
      } else if (hash_key_val == hash_key_path) {
        hash_key = NHHashKeyType::PATH_HASH_KEY;
      } else if (hash_key_val == hash_key_path_query) {
        hash_key = NHHashKeyType::PATH_QUERY_HASH_KEY;
      } else if (hash_key_val == hash_key_path_fragment) {
        hash_key = NHHashKeyType::PATH_FRAGMENT_HASH_KEY;
      } else if (hash_key_val == hash_key_cache) {
        // ToDo: Deprecated in 10.0.x, remove in 11.0.0
        hash_key = NHHashKeyType::CACHE_HASH_KEY;
      } else {
        hash_key = NHHashKeyType::PATH_HASH_KEY;
        NH_Note("Invalid 'hash_key' value, '%s', for the strategy named '%s', using default '%s'.", hash_key_val.c_str(),
                strategy_name.c_str(), hash_key_path.data());
      }
    }
  } catch (std::exception &ex) {
    throw std::invalid_argument("Error parsing the strategy named '" + strategy_name + "' due to '" + ex.what() +
                                "', this strategy will be ignored.");
  }

  // Parse hash_algorithm
  try {
    if (n["hash_algorithm"]) {
      hash_algorithm = n["hash_algorithm"].Scalar();
      if (hash_algorithm != "siphash24" && hash_algorithm != "siphash13") {
        NH_Note("Invalid 'hash_algorithm' value, '%s', for the strategy named '%s', using default 'siphash24'.",
                hash_algorithm.c_str(), strategy_name.c_str());
        hash_algorithm = "siphash24";
      }
    }
  } catch (std::exception &ex) {
    throw std::invalid_argument("Error parsing the strategy named '" + strategy_name + "' due to '" + ex.what() +
                                "', this strategy will be ignored.");
  }

  // Parse hash_seed0
  try {
    if (n["hash_seed0"]) {
      hash_seed0 = n["hash_seed0"].as<uint64_t>();
    }
  } catch (std::exception &ex) {
    throw std::invalid_argument("Error parsing the strategy named '" + strategy_name + "' due to '" + ex.what() +
                                "', this strategy will be ignored.");
  }

  // Parse hash_seed1
  try {
    if (n["hash_seed1"]) {
      hash_seed1 = n["hash_seed1"].as<uint64_t>();
    }
  } catch (std::exception &ex) {
    throw std::invalid_argument("Error parsing the strategy named '" + strategy_name + "' due to '" + ex.what() +
                                "', this strategy will be ignored.");
  }

  // Parse hash_replicas
  try {
    if (n["hash_replicas"]) {
      hash_replicas = n["hash_replicas"].as<int>();
      if (hash_replicas <= 0) {
        NH_Note("Invalid 'hash_replicas' value, %d, for the strategy named '%s', must be > 0, using default 1024.", hash_replicas,
                strategy_name.c_str());
        hash_replicas = 1024;
      }
    }
  } catch (std::exception &ex) {
    throw std::invalid_argument("Error parsing the strategy named '" + strategy_name + "' due to '" + ex.what() +
                                "', this strategy will be ignored.");
  }

  hash = createHashInstance(parseHashAlgorithm(hash_algorithm), hash_seed0, hash_seed1);

  // load up the hash rings.
  for (uint32_t i = 0; i < groups; i++) {
    std::shared_ptr<ATSConsistentHash> hash_ring = std::make_shared<ATSConsistentHash>(hash_replicas);
    for (uint32_t j = 0; j < host_groups[i].size(); j++) {
      // ATSConsistentHash needs the raw pointer.
      HostRecord *p = host_groups[i][j].get();
      // need to copy the 'hash_string' or 'hostname' cstring to 'name' for insertion into ATSConsistentHash.
      if (!p->hash_string.empty()) {
        p->name = const_cast<char *>(p->hash_string.c_str());
      } else {
        p->name = const_cast<char *>(p->hostname.c_str());
      }
      p->group_index = host_groups[i][j]->group_index;
      p->host_index  = host_groups[i][j]->host_index;
      hash_ring->insert(p, p->weight, hash.get());
      NH_Dbg(NH_DBG_CTL, "Loading hash rings - ring: %d, host record: %d, name: %s, hostname: %s, strategy: %s", i, j, p->name,
             p->hostname.c_str(), strategy_name.c_str());
    }
    hash->clear();
    rings.push_back(std::move(hash_ring));
  }
}

// returns a hash key calculated from the request and 'hash_key' configuration
// parameter.
uint64_t
NextHopConsistentHash::getHashKey(uint64_t sm_id, const HttpRequestData &hrdata, ATSHash64 *h)
{
  URL        *url            = nullptr;
  int         len            = 0;
  const char *url_string_ref = nullptr;

  switch (hash_url) {
  case NHHashUrlType::REQUEST:
    break;
  case NHHashUrlType::CACHE:
    if (hrdata.cache_info_lookup_url) {
      url = *(hrdata.cache_info_lookup_url);
    }
    break;
  case NHHashUrlType::PARENT:
    if (hrdata.cache_info_parent_selection_url) {
      url = *(hrdata.cache_info_parent_selection_url);
    }
    break;
  }

  // Make sure we default to the request URL if nothing else worked
  if (!url) {
    url = hrdata.hdr->url_get();
  }

  // calculate a hash using the selected config.
  switch (hash_key) {
  case NHHashKeyType::URL_HASH_KEY:
    url_string_ref = url->string_get_ref(&len, URLNormalize::LC_SCHEME_HOST);
    if (url_string_ref && len > 0) {
      h->update(url_string_ref, len);
      NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] url hash string: %s", sm_id, url_string_ref);
    }
    break;
  // hostname hash
  case NHHashKeyType::HOSTNAME_HASH_KEY:
    if (auto host{url->host_get()}; !host.empty()) {
      h->update(host.data(), host.length());
    }
    break;
  // path + query string
  case NHHashKeyType::PATH_QUERY_HASH_KEY:
    h->update("/", 1);
    if (auto path{url->path_get()}; !path.empty()) {
      h->update(path.data(), path.length());
    }
    if (auto query{url->query_get()}; !query.empty()) {
      h->update("?", 1);
      h->update(query.data(), query.length());
    }
    break;
  // path + fragment hash
  case NHHashKeyType::PATH_FRAGMENT_HASH_KEY:
    h->update("/", 1);
    if (auto path{url->path_get()}; !path.empty()) {
      h->update(path.data(), path.length());
    }
    if (auto fragment{url->fragment_get()}; !fragment.empty()) {
      h->update("?", 1);
      h->update(fragment.data(), fragment.length());
    }
    break;
  // use the cache key created by the TSCacheUrlSet() API (e.g. the cachekey plugin)
  // ToDo: Deprecated in 10.0.x, remove in 11.0.0
  case NHHashKeyType::CACHE_HASH_KEY:
    if (hrdata.cache_info_parent_selection_url && *(hrdata.cache_info_parent_selection_url)) {
      url            = *(hrdata.cache_info_parent_selection_url);
      url_string_ref = url->string_get_ref(&len);
      if (url_string_ref && len > 0) {
        NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] using parent selection over-ride string:'%.*s'.", sm_id, len, url_string_ref);
        h->update(url_string_ref, len);
      }
    } else {
      // URL defaults to hrdata.hdr->url_get() above
      h->update("/", 1);
      if (auto path{url->path_get()}; !path.empty()) {
        NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] the parent selection over-ride url is not set, using default path: %.*s.", sm_id,
               static_cast<int>(path.length()), path.data());
        h->update(path.data(), path.length());
      }
    }
    break;
  // use the path as the hash, default.
  case NHHashKeyType::PATH_HASH_KEY:
  default:
    h->update("/", 1);
    if (auto path{url->path_get()}; !path.empty()) {
      h->update(path.data(), path.length());
    }
    break;
  }

  h->final();
  return h->get();
}

void
NextHopConsistentHash::findNextHop(TSHttpTxn txnp, void * /* ih ATS_UNUSED */, time_t now)
{
  uint32_t const NO_RING_USE_POST_REMAP = uint32_t(0) - 1;

  HttpSM                     *sm           = reinterpret_cast<HttpSM *>(txnp);
  ParentResult               &result       = sm->t_state.parent_result;
  HttpRequestData            &request_info = sm->t_state.request_data;
  int64_t                     sm_id        = sm->sm_id;
  int64_t                     retry_time   = sm->t_state.txn_conf->parent_retry_time;
  time_t                      _now         = now;
  bool                        firstcall    = false;
  bool                        nextHopRetry = false;
  bool                        wrapped      = false;
  std::vector<bool>           wrap_around(groups, false);
  uint32_t                    cur_ring  = 0; // there is a hash ring for each host group
  uint32_t                    lookups   = 0;
  std::shared_ptr<HostRecord> pRec      = nullptr;
  HostStatus                 &pStatus   = HostStatus::instance();
  TSHostStatus                host_stat = TSHostStatus::TS_HOST_STATUS_INIT;
  HostStatRec                *hst       = nullptr;
  Machine                    *machine   = Machine::instance();
  std::string_view            first_call_host;
  int                         first_call_port = 0;

  if (result.line_number == -1 && result.result == ParentResultType::UNDEFINED) {
    firstcall = true;
  }

  // firstcall indicates that this is the first time the state machine has called findNextHop() for this
  // particular transaction so, a parent will be looked up using a hash from the request to locate a
  // parent on the consistent hash ring.  If not first call, then the transaction was unable to use the parent
  // returned from the "firstcall" due to some error so, subsequent calls will not search using a hash but,
  // will instead just increment the hash table iterator to find the next parent on the ring
  if (firstcall) {
    NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] firstcall, line_number: %d, result: %s", sm_id, result.line_number,
           ParentResultStr[static_cast<int>(result.result)]);
    result.line_number = distance;
    cur_ring           = 0;
    for (uint32_t i = 0; i < groups; i++) {
      result.chash_init[i] = false;
      wrap_around[i]       = false;
    }
  } else {
    // not first call, save the previously tried parent.
    if (result.hostname) {
      first_call_host = result.hostname;
      first_call_port = result.port;
    }
    NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] not firstcall, line_number: %d, result: %s", sm_id, result.line_number,
           ParentResultStr[static_cast<int>(result.result)]);
    switch (ring_mode) {
    case NHRingMode::ALTERNATE_RING:
      if (groups > 1) {
        cur_ring = (result.last_group + 1) % groups;
      } else {
        cur_ring = result.last_group;
      }
      break;
    case NHRingMode::PEERING_RING:
      if (groups == 1) {
        result.last_group = cur_ring = NO_RING_USE_POST_REMAP;
      } else {
        ink_assert(groups == 2);
        // look for the next parent on the
        // upstream ring.
        result.last_group = cur_ring = 1;
      }
      break;
    case NHRingMode::EXHAUST_RING:
    default:
      cur_ring = result.last_group;
      break;
    }
  }

  if (cur_ring != NO_RING_USE_POST_REMAP) {
    do {
      // all host groups have been searched and there are no available parents found
      if (isWrapped(wrap_around, groups)) {
        NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] No available parents.", sm_id);
        pRec = nullptr;
        break;
      }

      // search for available parent
      std::shared_ptr<ATSConsistentHash> r = rings[cur_ring];
      pRec                                 = chashLookup(r, cur_ring, result, request_info, &wrapped, sm_id);
      hst                                  = (pRec) ? pStatus.getHostStatus(pRec->hostname.c_str()) : nullptr;
      wrap_around[cur_ring]                = wrapped;
      lookups++;

      // found a parent
      if (pRec) {
        bool is_self = machine->is_self(pRec->hostname.c_str());
        host_stat    = (hst) ? hst->status : TSHostStatus::TS_HOST_STATUS_UP;

        // if the config ignore_self_detect is set to true and the host is down due to SELF_DETECT reason
        // ignore the down status and mark it as available
        if ((host_stat == TS_HOST_STATUS_DOWN && is_self && ignore_self_detect)) {
          if (hst->reasons == Reason::SELF_DETECT) {
            host_stat = TS_HOST_STATUS_UP;
          }
        }

        if (firstcall) {
          result.first_choice_status = (hst) ? hst->status : TSHostStatus::TS_HOST_STATUS_UP;
          // if peering and the selected host is myself, change rings and search for an upstream parent.
          if (ring_mode == NHRingMode::PEERING_RING && (pRec->self || is_self)) {
            if (groups == 1) {
              // use host from post-remap URL
              cur_ring = NO_RING_USE_POST_REMAP;
              pRec     = nullptr;
              break;
            } else {
              // switch to and search the upstream ring.
              cur_ring = 1;
              pRec     = nullptr;
              continue;
            }
          }
        } else {
          // not first call, make sure we're not re-using the same parent, search again if we are.
          if (first_call_host.size() > 0 && first_call_host == pRec->hostname && first_call_port == pRec->getPort(scheme)) {
            pRec = nullptr;
            continue;
          }
        }
        // if the parent is not available check to see if the retry window has expired making it available
        // for retry.
        if (!pRec->available.load() && host_stat == TS_HOST_STATUS_UP) {
          _now == 0 ? _now = time(nullptr) : _now = now;
          // Atomically push failedAt to (_now - retry_time) so only one
          // concurrent transaction with this _now takes the retry slot;
          // sequential retries with a later _now still pass the window check.
          time_t observed = pRec->failedAt.load();
          if ((observed + retry_time) < _now && pRec->failedAt.compare_exchange_strong(observed, _now - retry_time)) {
            nextHopRetry       = true;
            result.last_parent = pRec->host_index;
            result.last_lookup = pRec->group_index;
            result.retry       = nextHopRetry;
            result.result      = ParentResultType::SPECIFIED;
            NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] next hop %s is now retryable", sm_id, pRec->hostname.c_str());
            break;
          }
        }

        // use the available selected parent
        if (pRec->available.load() && host_stat == TS_HOST_STATUS_UP) {
          break;
        }
      }
      // try other rings per the ring mode
      switch (ring_mode) {
      case NHRingMode::ALTERNATE_RING:
        if (pRec && groups > 0) {
          cur_ring = (pRec->group_index + 1) % groups;
        } else {
          cur_ring = 0;
        }
        break;
      case NHRingMode::EXHAUST_RING:
      default:
        if (wrap_around[cur_ring] && groups > 1) {
          cur_ring = (cur_ring + 1) % groups;
        }
        break;
      }

      if (pRec) {
        // if the selected host is down, search again.
        if (!pRec->available || host_stat == TS_HOST_STATUS_DOWN) {
          NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] hostname: %s, available: %s, host_stat: %s", sm_id, pRec->hostname.c_str(),
                 pRec->available ? "true" : "false", HostStatusNames[host_stat]);
          pRec = nullptr;
          continue;
        }
      }
    } while (!pRec);

    NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] Initial parent lookups: %d", sm_id, lookups);
  }

  // ----------------------------------------------------------------------------------------------------
  // Validate and return the final result.
  // ----------------------------------------------------------------------------------------------------

  if (pRec && host_stat == TS_HOST_STATUS_UP && (pRec->available.load() || result.retry)) {
    result.result      = ParentResultType::SPECIFIED;
    result.hostname    = pRec->hostname.c_str();
    result.last_parent = pRec->host_index;
    result.last_lookup = result.last_group = cur_ring;
    switch (scheme) {
    case NHSchemeType::NONE:
    case NHSchemeType::HTTP:
      result.port = pRec->getPort(scheme);
      break;
    case NHSchemeType::HTTPS:
      result.port = pRec->getPort(scheme);
      break;
    }
    result.retry = nextHopRetry;
    // if using a peering ring mode and the parent selected came from the 'peering' group,
    // cur_ring == 0, then if the config allows it, set the flag to not cache the result.
    if (ring_mode == NHRingMode::PEERING_RING && !cache_peer_result && cur_ring == 0) {
      result.do_not_cache_response = true;

      NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] setting do not cache response from a peer per config: %s", sm_id,
             (result.do_not_cache_response) ? "true" : "false");
    }

    // We want to use the pristine/pre-remap URL when going to a peer so it can handle
    // the request without needing extra remaps to handle the post-remap URL
    if (ring_mode == NHRingMode::PEERING_RING && cur_ring == 0 && use_pristine) {
      result.use_pristine = true;
      NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] setting use pristine to true", sm_id);
    }

    ink_assert(result.hostname != nullptr);
    ink_assert(result.port != 0);
    NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] result->result: %s Chosen parent: %s.%d", sm_id,
           ParentResultStr[static_cast<int>(result.result)], result.hostname, result.port);
  } else {
    if (go_direct == true) {
      result.result = ParentResultType::DIRECT;
    } else {
      result.result = ParentResultType::FAIL;
    }
    result.hostname = nullptr;
    result.port     = 0;
    result.retry    = false;

    NH_Dbg(NH_DBG_CTL, "[%" PRIu64 "] result.result: %s set hostname null port 0 retry false", sm_id,
           ParentResultStr[static_cast<int>(result.result)]);
  }
}