// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/http/broken_alternative_services.h"

#include "base/containers/adapters.h"
#include "base/functional/bind.h"
#include "base/memory/singleton.h"
#include "base/time/tick_clock.h"
#include "base/time/time.h"
#include "net/http/http_server_properties.h"

namespace net {

namespace {

// Default broken alternative services, which is used when
// exponential_backoff_on_initial_delay is false.
constexpr base::TimeDelta kDefaultBrokenAlternativeProtocolDelay =
    base::Seconds(300);
// Subsequent failures result in exponential (base 2) backoff.
// Given the shortest broken delay is 1s, limit binary shift to limit delay to
// approximately 2 days.
const int kBrokenDelayMaxShift = 18;
// Lower and upper limits of broken alternative service delay.
constexpr base::TimeDelta kMinBrokenAlternativeProtocolDelay = base::Seconds(1);
constexpr base::TimeDelta kMaxBrokenAlternativeProtocolDelay = base::Days(2);

base::TimeDelta ComputeBrokenAlternativeServiceExpirationDelay(
    int broken_count,
    base::TimeDelta initial_delay,
    bool exponential_backoff_on_initial_delay) {
  DCHECK_GE(broken_count, 0);
  // Make sure initial delay is within [1s, 300s].
  if (initial_delay < kMinBrokenAlternativeProtocolDelay) {
    initial_delay = kMinBrokenAlternativeProtocolDelay;
  }
  if (initial_delay > kDefaultBrokenAlternativeProtocolDelay) {
    initial_delay = kDefaultBrokenAlternativeProtocolDelay;
  }
  if (broken_count == 0) {
    return initial_delay;
  }
  // Limit broken_count to avoid overflow.
  if (broken_count > kBrokenDelayMaxShift) {
    broken_count = kBrokenDelayMaxShift;
  }
  base::TimeDelta delay;
  if (exponential_backoff_on_initial_delay) {
    delay = initial_delay * (1 << broken_count);
  } else {
    delay = kDefaultBrokenAlternativeProtocolDelay * (1 << (broken_count - 1));
  }
  return std::min(delay, kMaxBrokenAlternativeProtocolDelay);
}

}  // namespace

BrokenAlternativeService::BrokenAlternativeService(
    const AlternativeService& alternative_service,
    const NetworkAnonymizationKey& network_anonymization_key,
    bool use_network_anonymization_key)
    : alternative_service(alternative_service),
      network_anonymization_key(use_network_anonymization_key
                                    ? network_anonymization_key
                                    : NetworkAnonymizationKey()) {}

BrokenAlternativeService::~BrokenAlternativeService() = default;

bool BrokenAlternativeService::operator<(
    const BrokenAlternativeService& other) const {
  return std::tie(alternative_service, network_anonymization_key) <
         std::tie(other.alternative_service, other.network_anonymization_key);
}

BrokenAlternativeServices::BrokenAlternativeServices(
    int max_recently_broken_alternative_service_entries,
    Delegate* delegate,
    const base::TickClock* clock)
    : delegate_(delegate),
      clock_(clock),
      recently_broken_alternative_services_(
          max_recently_broken_alternative_service_entries),
      initial_delay_(kDefaultBrokenAlternativeProtocolDelay) {
  DCHECK(delegate_);
  DCHECK(clock_);
}

BrokenAlternativeServices::~BrokenAlternativeServices() = default;

void BrokenAlternativeServices::Clear() {
  expiration_timer_.Stop();
  broken_alternative_service_list_.clear();
  broken_alternative_service_map_.clear();
  recently_broken_alternative_services_.Clear();
}

void BrokenAlternativeServices::MarkBrokenUntilDefaultNetworkChanges(
    const BrokenAlternativeService& broken_alternative_service) {
  DCHECK(!broken_alternative_service.alternative_service.host.empty());
  DCHECK_NE(kProtoUnknown,
            broken_alternative_service.alternative_service.protocol);

  // The brokenness will expire on the default network change or based on
  // timer.
  broken_alternative_services_on_default_network_.insert(
      broken_alternative_service);
  MarkBrokenImpl(broken_alternative_service);
}

void BrokenAlternativeServices::MarkBroken(
    const BrokenAlternativeService& broken_alternative_service) {
  // The brokenness expires based only on the timer, not on the default network
  // change.
  broken_alternative_services_on_default_network_.erase(
      broken_alternative_service);
  MarkBrokenImpl(broken_alternative_service);
}

void BrokenAlternativeServices::MarkBrokenImpl(
    const BrokenAlternativeService& broken_alternative_service) {
  // Empty host means use host of origin, callers are supposed to substitute.
  DCHECK(!broken_alternative_service.alternative_service.host.empty());
  DCHECK_NE(kProtoUnknown,
            broken_alternative_service.alternative_service.protocol);

  auto it =
      recently_broken_alternative_services_.Get(broken_alternative_service);
  int broken_count = 0;
  if (it == recently_broken_alternative_services_.end()) {
    recently_broken_alternative_services_.Put(broken_alternative_service, 1);
  } else {
    broken_count = it->second++;
  }
  base::TimeTicks expiration =
      clock_->NowTicks() +
      ComputeBrokenAlternativeServiceExpirationDelay(
          broken_count, initial_delay_, exponential_backoff_on_initial_delay_);
  // Return if alternative service is already in expiration queue.
  BrokenAlternativeServiceList::iterator list_it;
  if (!AddToBrokenListAndMap(broken_alternative_service, expiration,
                             &list_it)) {
    return;
  }

  // If this is now the first entry in the list (i.e.
  // |broken_alternative_service| is the next alt svc to expire), schedule
  // an expiration task for it.
  if (list_it == broken_alternative_service_list_.begin()) {
    ScheduleBrokenAlternateProtocolMappingsExpiration();
  }
}

void BrokenAlternativeServices::MarkRecentlyBroken(
    const BrokenAlternativeService& broken_alternative_service) {
  DCHECK_NE(kProtoUnknown,
            broken_alternative_service.alternative_service.protocol);
  if (recently_broken_alternative_services_.Get(broken_alternative_service) ==
      recently_broken_alternative_services_.end()) {
    recently_broken_alternative_services_.Put(broken_alternative_service, 1);
  }
}

bool BrokenAlternativeServices::IsBroken(
    const BrokenAlternativeService& broken_alternative_service) const {
  // Empty host means use host of origin, callers are supposed to substitute.
  DCHECK(!broken_alternative_service.alternative_service.host.empty());
  return broken_alternative_service_map_.find(broken_alternative_service) !=
         broken_alternative_service_map_.end();
}

bool BrokenAlternativeServices::IsBroken(
    const BrokenAlternativeService& broken_alternative_service,
    base::TimeTicks* brokenness_expiration) const {
  DCHECK(brokenness_expiration != nullptr);
  // Empty host means use host of origin, callers are supposed to substitute.
  DCHECK(!broken_alternative_service.alternative_service.host.empty());
  auto map_it =
      broken_alternative_service_map_.find(broken_alternative_service);
  if (map_it == broken_alternative_service_map_.end()) {
    return false;
  }
  auto list_it = map_it->second;
  *brokenness_expiration = list_it->second;
  return true;
}

bool BrokenAlternativeServices::WasRecentlyBroken(
    const BrokenAlternativeService& broken_alternative_service) {
  DCHECK(!broken_alternative_service.alternative_service.host.empty());
  return recently_broken_alternative_services_.Get(
             broken_alternative_service) !=
             recently_broken_alternative_services_.end() ||
         broken_alternative_service_map_.find(broken_alternative_service) !=
             broken_alternative_service_map_.end();
}

void BrokenAlternativeServices::Confirm(
    const BrokenAlternativeService& broken_alternative_service) {
  DCHECK_NE(kProtoUnknown,
            broken_alternative_service.alternative_service.protocol);

  // Remove |broken_alternative_service| from
  // |broken_alternative_service_list_|, |broken_alternative_service_map_| and
  // |broken_alternative_services_on_default_network_|.
  auto map_it =
      broken_alternative_service_map_.find(broken_alternative_service);
  if (map_it != broken_alternative_service_map_.end()) {
    broken_alternative_service_list_.erase(map_it->second);
    broken_alternative_service_map_.erase(map_it);
  }

  auto it =
      recently_broken_alternative_services_.Get(broken_alternative_service);
  if (it != recently_broken_alternative_services_.end()) {
    recently_broken_alternative_services_.Erase(it);
  }

  broken_alternative_services_on_default_network_.erase(
      broken_alternative_service);
}

bool BrokenAlternativeServices::OnDefaultNetworkChanged() {
  bool changed = !broken_alternative_services_on_default_network_.empty();
  while (!broken_alternative_services_on_default_network_.empty()) {
    Confirm(*broken_alternative_services_on_default_network_.begin());
  }
  return changed;
}

void BrokenAlternativeServices::SetBrokenAndRecentlyBrokenAlternativeServices(
    std::unique_ptr<BrokenAlternativeServiceList>
        broken_alternative_service_list,
    std::unique_ptr<RecentlyBrokenAlternativeServices>
        recently_broken_alternative_services) {
  DCHECK(broken_alternative_service_list);
  DCHECK(recently_broken_alternative_services);

  base::TimeTicks next_expiration =
      broken_alternative_service_list_.empty()
          ? base::TimeTicks::Max()
          : broken_alternative_service_list_.front().second;

  // Add |recently_broken_alternative_services| to
  // |recently_broken_alternative_services_|.
  // If an alt-svc already exists, overwrite its broken-count to the one in
  // |recently_broken_alternative_services|.

  recently_broken_alternative_services_.Swap(
      *recently_broken_alternative_services);
  // Add back all existing recently broken alt svcs to cache so they're at
  // front of recency list (LRUCache::Get() does this automatically).
  for (const auto& [service, broken_count] :
       base::Reversed(*recently_broken_alternative_services)) {
    if (recently_broken_alternative_services_.Get(service) ==
        recently_broken_alternative_services_.end()) {
      recently_broken_alternative_services_.Put(service, broken_count);
    }
  }

  // Append |broken_alternative_service_list| to
  // |broken_alternative_service_list_|
  size_t num_broken_alt_svcs_added = broken_alternative_service_list->size();
  broken_alternative_service_list_.splice(
      broken_alternative_service_list_.begin(),
      *broken_alternative_service_list);
  // For each newly-appended alt svc in |broken_alternative_service_list_|,
  // add an entry to |broken_alternative_service_map_| that points to its
  // list iterator. Also, add an entry for that alt svc in
  // |recently_broken_alternative_services_| if one doesn't exist.
  auto list_it = broken_alternative_service_list_.begin();
  for (size_t i = 0; i < num_broken_alt_svcs_added; ++i) {
    const BrokenAlternativeService& broken_alternative_service = list_it->first;
    auto map_it =
        broken_alternative_service_map_.find(broken_alternative_service);
    if (map_it != broken_alternative_service_map_.end()) {
      // Implies this entry already exists somewhere else in
      // |broken_alternative_service_list_|. Remove the existing entry from
      // |broken_alternative_service_list_|, and update the
      // |broken_alternative_service_map_| entry to point to this list entry
      // instead.
      auto list_existing_entry_it = map_it->second;
      broken_alternative_service_list_.erase(list_existing_entry_it);
      map_it->second = list_it;
    } else {
      broken_alternative_service_map_.insert(
          std::make_pair(broken_alternative_service, list_it));
    }

    if (recently_broken_alternative_services_.Peek(
            broken_alternative_service) ==
        recently_broken_alternative_services_.end()) {
      recently_broken_alternative_services_.Put(broken_alternative_service, 1);
    }

    ++list_it;
  }

  // Sort |broken_alternative_service_list_| by expiration time. This operation
  // does not invalidate list iterators, so |broken_alternative_service_map_|
  // does not need to be updated.
  broken_alternative_service_list_.sort(
      [](const std::pair<BrokenAlternativeService, base::TimeTicks>& lhs,
         const std::pair<BrokenAlternativeService, base::TimeTicks>& rhs)
          -> bool { return lhs.second < rhs.second; });

  base::TimeTicks new_next_expiration =
      broken_alternative_service_list_.empty()
          ? base::TimeTicks::Max()
          : broken_alternative_service_list_.front().second;

  if (new_next_expiration != next_expiration)
    ScheduleBrokenAlternateProtocolMappingsExpiration();
}

void BrokenAlternativeServices::SetDelayParams(
    absl::optional<base::TimeDelta> initial_delay,
    absl::optional<bool> exponential_backoff_on_initial_delay) {
  if (initial_delay.has_value()) {
    initial_delay_ = initial_delay.value();
  }
  if (exponential_backoff_on_initial_delay.has_value()) {
    exponential_backoff_on_initial_delay_ =
        exponential_backoff_on_initial_delay.value();
  }
}

const BrokenAlternativeServiceList&
BrokenAlternativeServices::broken_alternative_service_list() const {
  return broken_alternative_service_list_;
}

const RecentlyBrokenAlternativeServices&
BrokenAlternativeServices::recently_broken_alternative_services() const {
  return recently_broken_alternative_services_;
}

bool BrokenAlternativeServices::AddToBrokenListAndMap(
    const BrokenAlternativeService& broken_alternative_service,
    base::TimeTicks expiration,
    BrokenAlternativeServiceList::iterator* it) {
  DCHECK(it);

  auto map_it =
      broken_alternative_service_map_.find(broken_alternative_service);
  if (map_it != broken_alternative_service_map_.end())
    return false;

  // Iterate from end of |broken_alternative_service_list_| to find where to
  // insert it to keep the list sorted by expiration time.
  auto list_it = broken_alternative_service_list_.end();
  while (list_it != broken_alternative_service_list_.begin()) {
    --list_it;
    if (list_it->second <= expiration) {
      ++list_it;
      break;
    }
  }

  // Insert |broken_alternative_service| into the list and the map.
  list_it = broken_alternative_service_list_.insert(
      list_it, std::make_pair(broken_alternative_service, expiration));
  broken_alternative_service_map_.insert(
      std::make_pair(broken_alternative_service, list_it));

  *it = list_it;
  return true;
}

void BrokenAlternativeServices::ExpireBrokenAlternateProtocolMappings() {
  base::TimeTicks now = clock_->NowTicks();

  while (!broken_alternative_service_list_.empty()) {
    auto it = broken_alternative_service_list_.begin();
    if (now < it->second) {
      break;
    }

    delegate_->OnExpireBrokenAlternativeService(
        it->first.alternative_service, it->first.network_anonymization_key);

    broken_alternative_service_map_.erase(it->first);
    broken_alternative_service_list_.erase(it);
  }

  if (!broken_alternative_service_list_.empty())
    ScheduleBrokenAlternateProtocolMappingsExpiration();
}

void BrokenAlternativeServices ::
    ScheduleBrokenAlternateProtocolMappingsExpiration() {
  DCHECK(!broken_alternative_service_list_.empty());
  base::TimeTicks now = clock_->NowTicks();
  base::TimeTicks next_expiration =
      broken_alternative_service_list_.front().second;
  base::TimeDelta delay =
      next_expiration > now ? next_expiration - now : base::TimeDelta();
  expiration_timer_.Stop();
  expiration_timer_.Start(
      FROM_HERE, delay,
      base::BindOnce(
          &BrokenAlternativeServices ::ExpireBrokenAlternateProtocolMappings,
          weak_ptr_factory_.GetWeakPtr()));
}

}  // namespace net