Fix and refactor HttpServerPropertiesImpl's alternative services brokenness expiration behavior

net/http/broken_alternative_services.cc

+// Copyright (c) 2017 The Chromium Authors. All rights reserved.
+// 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/memory/singleton.h"
+#include "base/time/time.h"
+#include "net/http/http_server_properties_impl.h"
+
+namespace net {
+
+namespace {
+
+// Initial delay for broken alternative services.
+const uint64_t kBrokenAlternativeProtocolDelaySecs = 300;
+// Subsequent failures result in exponential (base 2) backoff.
+// Limit binary shift to limit delay to approximately 2 days.
+const int kBrokenDelayMaxShift = 9;
+
+base::TimeDelta ComputeBrokenAlternativeServiceExpirationDelay(
+    int broken_count) {
+  DCHECK(broken_count >= 0);
+  if (broken_count > kBrokenDelayMaxShift)
+    broken_count = kBrokenDelayMaxShift;
+  return base::TimeDelta::FromSeconds(kBrokenAlternativeProtocolDelaySecs) *
+         (1 << broken_count);
+}
+
+// Default implementation of BrokenAlternativeServices::Clock.
+class DefaultClock : public BrokenAlternativeServices::Clock {
+ public:
+  static DefaultClock* GetInstance() {
+    return base::Singleton<DefaultClock>::get();
+  }
+
+  DefaultClock() {}
+  ~DefaultClock() override {}

[Ryan Hamilton, 2017/05/26 03:52:08]

Do you need these since they're default?

[wangyix1, 2017/05/27 01:20:08]

Done.

+
+  base::TimeTicks Now() const override { return base::TimeTicks::Now(); }
+
+ private:
+  DefaultClock(const DefaultClock&) = delete;
+  void operator=(const DefaultClock&) = delete;

[Ryan Hamilton, 2017/05/26 03:52:08]

these don't need to be made private since they're deleted, but since this class
has no members, I don't think it's worth deleting these constructors.

[wangyix1, 2017/05/27 01:20:09]

Done.

+};
+
+}  // namespace
+
+BrokenAlternativeServices::Clock*
+BrokenAlternativeServices::Clock::GetDefaultClockInstance() {
+  return DefaultClock::GetInstance();

[Ryan Hamilton, 2017/05/26 03:52:08]

I would just inline the base::Singleton<> call here since it's still hidden in
the .cc file

[wangyix1, 2017/05/27 01:20:08]

Tried this and got compiler error:
'get' is a private member of 'base::Singleton<DefaultClock>

[Ryan Hamilton, 2017/05/27 13:28:15]

*mind blown*

+}
+
+BrokenAlternativeServices::BrokenAlternativeServices(Delegate* delegate,
+                                                     Clock* clock)
+    : delegate_(delegate),
+      recently_broken_alternative_services_(
+          RecentlyBrokenAlternativeServices::NO_AUTO_EVICT),
+      clock_(clock),
+      weak_ptr_factory_(this) {
+  DCHECK(delegate_);
+}
+
+BrokenAlternativeServices::~BrokenAlternativeServices() {}
+
+void BrokenAlternativeServices::MarkAlternativeServiceBroken(
+    const AlternativeService& alternative_service) {
+  // Empty host means use host of origin, callers are supposed to substitute.
+  DCHECK(!alternative_service.host.empty());
+  if (alternative_service.protocol == kProtoUnknown) {
+    LOG(DFATAL) << "Trying to mark unknown alternate protocol broken.";
+    return;
+  }

[Ryan Hamilton, 2017/05/26 03:52:08]

I think I'd just DCHECK this.

[wangyix1, 2017/05/27 01:20:09]

Done.

+  auto it = recently_broken_alternative_services_.Get(alternative_service);
+  int broken_count = 0;
+  if (it == recently_broken_alternative_services_.end()) {
+    recently_broken_alternative_services_.Put(alternative_service, 1);
+  } else {
+    broken_count = it->second++;
+  }
+  base::TimeTicks expiration =
+      clock_->Now() +
+      ComputeBrokenAlternativeServiceExpirationDelay(broken_count);
+  // Return if alternative service is already in expiration queue.
+  BrokenAlternativeServiceList::iterator list_it;
+  if (!AddToBrokenAlternativeServiceListAndMap(alternative_service, expiration,
+                                               &list_it)) {
+    return;
+  }
+
+  // If this is now the first entry in the list (i.e. |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::MarkAlternativeServiceRecentlyBroken(
+    const AlternativeService& alternative_service) {
+  if (recently_broken_alternative_services_.Get(alternative_service) ==
+      recently_broken_alternative_services_.end()) {
+    recently_broken_alternative_services_.Put(alternative_service, 1);
+  }
+}
+
+bool BrokenAlternativeServices::IsAlternativeServiceBroken(
+    const AlternativeService& alternative_service) const {
+  // Empty host means use host of origin, callers are supposed to substitute.
+  DCHECK(!alternative_service.host.empty());
+  return broken_alternative_service_map_.find(alternative_service) !=
+         broken_alternative_service_map_.end();
+}
+
+bool BrokenAlternativeServices::WasAlternativeServiceRecentlyBroken(
+    const AlternativeService& alternative_service) {
+  if (alternative_service.protocol == kProtoUnknown)
+    return false;

[Ryan Hamilton, 2017/05/26 03:52:08]

I suspect we don't need this since it's already forbidden to put unknown
protocols in the list, right?

[wangyix1, 2017/05/27 01:20:10]

Done.

+
+  return recently_broken_alternative_services_.Get(alternative_service) !=
+         recently_broken_alternative_services_.end();
+}
+
+void BrokenAlternativeServices::ConfirmAlternativeService(
+    const AlternativeService& alternative_service) {
+  if (alternative_service.protocol == kProtoUnknown)
+    return;
+
+  // Remove |alternative_service| from |alternative_service_list_| and
+  // |alternative_service_map_|.
+  auto map_it = broken_alternative_service_map_.find(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(alternative_service);
+  if (it != recently_broken_alternative_services_.end()) {
+    recently_broken_alternative_services_.Erase(it);
+  }
+}
+
+bool BrokenAlternativeServices ::AddToBrokenAlternativeServiceListAndMap(

[Ryan Hamilton, 2017/05/26 03:52:08]

nit: no space before "::"

[wangyix1, 2017/05/27 01:20:08]

Done.

+    const AlternativeService& alternative_service,
+    base::TimeTicks expiration,
+    BrokenAlternativeServiceList::iterator* it) {
+  DCHECK(it);
+
+  auto map_it = broken_alternative_service_map_.find(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();

[Ryan Hamilton, 2017/05/26 03:52:08]

Is it safe to do -- on an end() iterator? I think you might want to use rbegin
and rend to loop over the list in reverse order.

[wangyix1, 2017/05/27 01:20:09]

The reason I used an iterator instead of reverse_iterator is because
list::insert does not work with a reverse_iterator.

About decrementing end(), I found this, it looks like it's okay?
https://stackoverflow.com/questions/5322104/how-portable-is-end-iterator-decr...

[Ryan Hamilton, 2017/05/27 13:28:15]

Ah, I see. Fwiw, reverse_iterator has a base() method.
Cool. Looks good. 

+  while (list_it != broken_alternative_service_list_.begin()) {
+    --list_it;
+    if (list_it->expiration <= expiration) {
+      ++list_it;
+      break;
+    }
+  }

[Ryan Hamilton, 2017/05/26 03:52:08]

Could std::lower_bound be used here?

[wangyix1, 2017/05/27 01:20:10]

Looks like std::lower_bound was designed for containers with random access
iterators (it internally does binary search). This would be very inefficient for
std::list

[Ryan Hamilton, 2017/05/27 13:28:15]

Fair enough. Interestingly it appears to be merely linear:

The number of comparisons performed is logarithmic in the distance between first
and last (At most log
2(last - first) + O(1) comparisons). However, for non-RandomAccessIterators, the
number of iterator increments is linear.

[wangyix1, 2017/05/30 21:18:17]

Oh interesting. If it's linear, it should be fine to use std::lower_bound then.
However, I assume it will do a linear search from the beginning, whereas my code
does it from the end, which I think is preferable. What do you think?

+
+  // Insert |alternative_service| into the list and the map
+  list_it = broken_alternative_service_list_.insert(
+      list_it, BrokenAltSvcExpireInfo(alternative_service, expiration));
+  broken_alternative_service_map_.insert(
+      std::make_pair(alternative_service, list_it));
+
+  *it = list_it;
+  return true;
+}
+
+void BrokenAlternativeServices ::ExpireBrokenAlternateProtocolMappings() {
+  base::TimeTicks now = clock_->Now();
+  ;

[Ryan Hamilton, 2017/05/26 03:52:07]

nit: remove this?

[wangyix1, 2017/05/27 01:20:09]

Done.

+  while (!broken_alternative_service_list_.empty()) {
+    auto it = broken_alternative_service_list_.begin();
+    if (now < it->expiration) {
+      break;
+    }
+
+    const AlternativeService expired_alternative_service =
+        it->alternative_service;
+    broken_alternative_service_map_.erase(expired_alternative_service);
+    broken_alternative_service_list_.erase(it);
+
+    delegate_->OnExpireBrokenAlternativeService(expired_alternative_service);

[Ryan Hamilton, 2017/05/26 03:52:08]

not that it super matters, but since On...() takes a const&, if you call this
method with it->alternative_service (before you erase the iterator, obviously
:>) then you can avoid a copy.

[wangyix1, 2017/05/27 01:20:09]

Done.

+  }
+
+  if (!broken_alternative_service_list_.empty())
+    ScheduleBrokenAlternateProtocolMappingsExpiration();
+}
+
+void BrokenAlternativeServices ::
+    ScheduleBrokenAlternateProtocolMappingsExpiration() {
+  DCHECK(!broken_alternative_service_list_.empty());
+  base::TimeTicks now = clock_->Now();
+  base::TimeTicks when = broken_alternative_service_list_.front().expiration;
+  base::TimeDelta delay = when > now ? when - now : base::TimeDelta();
+  expiration_timer_.Stop();
+  expiration_timer_.Start(
+      FROM_HERE, delay,
+      base::Bind(
+          &BrokenAlternativeServices ::ExpireBrokenAlternateProtocolMappings,
+          weak_ptr_factory_.GetWeakPtr()));
+}
+
+}  // namespace net