Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker.cc

 // Copyright 2016 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 "components/certificate_transparency/single_tree_tracker.h"
 
+#include <algorithm>
+#include <iterator>
+#include <list>
 #include <utility>
 
+#include "base/bind.h"
 #include "base/metrics/histogram_macros.h"
+#include "components/certificate_transparency/log_dns_client.h"
+#include "net/base/hash_value.h"
+#include "net/base/net_errors.h"
 #include "net/cert/ct_log_verifier.h"
+#include "net/cert/merkle_audit_proof.h"
+#include "net/cert/merkle_tree_leaf.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/x509_certificate.h"
 
+using net::ct::LogEntry;
+using net::ct::MerkleTreeLeaf;
+using net::ct::SignedCertificateTimestamp;
 using net::ct::SignedTreeHead;
 
 namespace {
 
 // Enum indicating whether an SCT can be checked for inclusion and if not,
 // the reason it cannot.
 //
 // Note: The numeric values are used within a histogram and should not change
 // or be re-assigned.
 enum SCTCanBeCheckedForInclusion {
   // If the SingleTreeTracker does not have a valid STH, then a valid STH is
   // first required to evaluate whether the SCT can be checked for inclusion
   // or not.
   VALID_STH_REQUIRED = 0,
   // If the STH does not cover the SCT (the timestamp in the SCT is greater than
   // MMD + timestamp in the STH), then a newer STH is needed.
   NEWER_STH_REQUIRED = 1,
   // When an SCT is observed, if the SingleTreeTracker instance has a valid STH
   // and the STH covers the SCT (the timestamp in the SCT is less than MMD +
   // timestamp in the STH), then it can be checked for inclusion.
   CAN_BE_CHECKED = 2,
+  // This SCT was not audited because the queue of pending entries was
+  // full.
+  NOT_AUDITED = 3,
   SCT_CAN_BE_CHECKED_MAX
 };
 
 // Measure how often clients encounter very new SCTs, by measuring whether an
 // SCT can be checked for inclusion upon first observation.
 void LogCanBeCheckedForInclusionToUMA(
     SCTCanBeCheckedForInclusion can_be_checked) {
   UMA_HISTOGRAM_ENUMERATION("Net.CertificateTransparency.CanInclusionCheckSCT",
                             can_be_checked, SCT_CAN_BE_CHECKED_MAX);
 }
 
+// Return the leaf hash of the the entry in the log represented by
+// the given |cert| and |sct|. If leaf hash calculation failed, returns
+// an empty string.
+std::string GetLogEntryLeafHash(const net::X509Certificate* cert,
+                                const SignedCertificateTimestamp* sct) {
+  MerkleTreeLeaf leaf;
+  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
+    return std::string("");

[Ryan Sleevi, 2016/09/22 07:08:29]

std::string()

[Eran Messeri, 2016/09/22 20:10:21]

Done.

+
+  std::string leaf_hash;
+  if (!HashMerkleTreeLeaf(leaf, &leaf_hash))
+    return std::string("");

[Ryan Sleevi, 2016/09/22 07:08:28]

std::string()

[Eran Messeri, 2016/09/22 20:10:21]

Done.

+
+  return leaf_hash;
+}
+
+// Audit state of a log entry.
+enum AuditState {
+  // Entry cannot be audited because a newer STH is needed.
+  PENDING_NEWER_STH,
+  // The entry is pending request of its leaf index.
+  PENDING_LEAF_INDEX_REQUEST,
+  // The leaf index of this entry has been requested from the log.
+  LEAF_INDEX_REQUESTED,
+  // A leaf index has been obtained and the entry is now pending request
+  // of an inclusion proof.
+  PENDING_INCLUSION_PROOF_REQUEST,
+  // An inclusion proof for this entry has been requested from the log.
+  INCLUSION_PROOF_REQUESTED
+};

[Ryan Sleevi, 2016/09/22 07:08:28]

Unfortunately, I found this "spread-apart" state a bit harder to reason about
than what we'd talked about.

The reason for this is now the state (and state transitions) are no longer
logically part of one class, but spread throughout the SingleTreeTracker. The
benefit of state machines is in trying to group the state transitions and edges
together, which, combined with a class outline (e.g. separate from the
implementation, even when in the .cc), can make it easier to get the high-level
summary of how edges transition and what state is conveyed through them.

[Eran Messeri, 2016/09/22 20:10:20]

Acknowledged; Having the state transitions in one place would make it easier to
reason about them.
Do you suggest putting this state in the EntryToAudit struct and making it a
full-fledged class?

I don't mind doing that, but it may take up the SingleTreeTracker's ability to
handle throttling at a class level (and instead each entry would throttle
itself).

I think we could avoid many of the states, potentially all of them, if the
LogDnsClient only had one method that would return the leaf index and inclusion
proof nodes based on the leaf hash and throttled requests asynchronously.

+
+// Maximal size of the checked entries cache.
+size_t kCheckedEntriesCacheSize = 100;
+
+// Maximal size of the pending entries queue.
+size_t kPendingEntriesQueueSize = 100;
+
+// Maximum Merge Delay - logs can have individual MMD, but all known logs
+// currently have 24 hours MMD and Chrome's CT policy requires an MMD
+// that's no greater than that. For simplicity, use 24 hours for all logs.
+int kMaximumMergeDelayInHours = 24;
+
+// The log MUST incorporate the a certificate in the tree within the Maximum
+// Merge Delay, so an entry can be audited once the timestamp from the SCT +
+// MMD has passed.
+// Returns true if the timestamp from the STH is newer than SCT timestamp + MMD.
+bool IsSCTReadyForAudit(base::Time sth_timestamp, base::Time sct_timestamp) {
+  static const base::TimeDelta kMaximumMergeDelay =
+      base::TimeDelta::FromHours(kMaximumMergeDelayInHours);

[Ryan Sleevi, 2016/09/22 07:08:28]

Why do this as a function-level static? Why not just make kMaximumMergeDelay a
static base::TimeDelta (which  can be constexpr init'd)?

[Eran Messeri, 2016/09/22 20:10:20]

Done; haven't noticed the exception to
https://google.github.io/styleguide/cppguide.html#Static_and_Global_Variables
made for global variables of class type that can be constexpr initialized.

+  return sct_timestamp + kMaximumMergeDelay < sth_timestamp;
+}
+
 }  // namespace
 
 namespace certificate_transparency {
+// The entry that is being audited. Immutable - once created, the entry
+// to audit does not change.
+struct SingleTreeTracker::EntryToAudit {
+  const base::Time sct_timestamp;
+  const std::string leaf_hash;

[Ryan Sleevi, 2016/09/22 07:08:28]

Why string rather than SHA256HashValue? (see a bunch of the remarks below
though)

[Eran Messeri, 2016/09/22 20:10:21]

Done.

+
+  // Returns true if the leaf hash was calculated correctly and is valid, false
+  // otherwise.
+  bool is_valid() const { return !leaf_hash.empty(); }
+
+  EntryToAudit(net::X509Certificate* cert,
+               const net::ct::SignedCertificateTimestamp* sct)
+      : sct_timestamp(sct->timestamp),
+        leaf_hash(GetLogEntryLeafHash(cert, sct)) {}

[Ryan Sleevi, 2016/09/22 07:08:28]

https://google.github.io/styleguide/cppguide.html#Doing_Work_in_Constructors

"avoid initialization that can fail if you can't signal an error"

[Eran Messeri, 2016/09/22 20:10:21]

Done - changed GetLogEntryLeafHash to be called before the EntryToAudit is
created.

+};
+
+// State of a log entry: its audit state and information necessary to
+// validate an inclusion proof. Gets updated as the entry transitions
+// between the different audit states.
+struct SingleTreeTracker::EntryAuditState {
+  // Current phase of inclusion check.
+  AuditState state;
+  // The index of this entry in the log. Only valid if |state| is
+  // PENDING_INCLUSION_PROOF_REQUEST or INCLUSION_PROOF_REQUESTED
+  uint64_t leaf_index;
+  // The size of the tree for which an inclusion proof was requested.
+  // It is copied from the verified STH in the SingleTreeTracker when the
+  // leaf index is requested so that if a newer STH is provided to the
+  // SingleTreeTracker while the inclusion proof is fetched, it won't be
+  // necessary to re-fetch it.

[Ryan Sleevi, 2016/09/22 07:08:29]

"it won't be necessary to re-fetch it" reads weird - is 'it' the newer STH or
the inclusion proof? I presume you mean "so it won't be necessary to re-fetch
the inclusion proof", but the subtlety of why this is still non-obvious to me,
so it may be useful to expand the comment here.

[Eran Messeri, 2016/09/22 20:10:20]

Done - I've re-worded that comment a bit. The gist is that all of the following
are inputs to the inclusion proof verification method and they all have to
match:
* leaf index (fixed).
* leaf hash (also fixed)
* tree size (gets updated when new STHs are delivered).
* inclusion proof nodes (depend on the tree size provided to
QueryInclusionProofNodes).
* tree root hash (gets updated when new STHs are delivered).

So if we've requested an inclusion proof for node K in tree of size N, then a
newer STH with N' is received, the obtained inclusion proof will not be valid in
the tree N' and a new one will have to be fetched - or we just store N. 

+  // Valid when |leaf_index| is valid or when |state| is LEAF_INDEX_REQUESTED.
+  uint64_t tree_size;
+  // TODO(eranm): Add a root_hash field that's copied from the verified STH
+  // for the same reason |tree_size| is copied, when the inclusion proof
+  // checking code lands and we can use it.
+  // See https://codereview.chromium.org/2182533002/ and
+  // https://crbug.com/631087
+
+  EntryAuditState(AuditState state)
+      : state(state), leaf_index(0), tree_size(0) {}
+};
+
+// Orders entries by the SCT timestamp. In case of tie, which is very unlikely
+// as it requires two SCTs issued from a log at exactly the same time, order
+// by leaf hash.
+bool SingleTreeTracker::OrderByTimestamp::operator()(
+    const EntryToAudit& lhs,
+    const EntryToAudit& rhs) const {
+  if (lhs.sct_timestamp != rhs.sct_timestamp)
+    return lhs.sct_timestamp < rhs.sct_timestamp;
+
+  // TODO(eranm): Copying the hashes just for comparison may be avoided by
+  // using SHA256HashValue as the type for EntryToAudit.leaf_hash.
+  // However as this code should be rarely executed and std::string is easier
+  // to work with, that type is chosen for |leaf_hash|.

[Ryan Sleevi, 2016/09/22 07:08:28]

It's like you already knew where my objection was going to be.

This feels very inefficient. We shouldn't do this :)

[Eran Messeri, 2016/09/22 20:10:21]

Done - EntryToAudit now holds a SHA256HashValue.

+  net::SHA256HashValue lhs_hash, rhs_hash;
+  memcpy(lhs_hash.data, lhs.leaf_hash.c_str(),
+         std::min(32ul, lhs.leaf_hash.size()));

[Ryan Sleevi, 2016/09/22 07:08:28]

When is it ever valid for leaf_hash.size() to != 32? Isn't that something that
should be guaranteed before it ever gets to this place in code?

Why .c_str(), rather than .data()?

Why marshal to SHA256HashValue, when you could just compare the strings
directly?

Why .operator() rather than SHA256HashValueLessThan()(lhs_hash, rhs_hash)? Is
this a Most Vexing Parse?

solve all your problems at once:

return std::tie(lhs.sct_timestamp, lhs.hash) < std::tie(rhs.sct_timestamp,
rhs.hash);

[Eran Messeri, 2016/09/22 20:10:20]

Done - obsolete - I can now use SHA256HashValueLessThan directly.

+  memcpy(rhs_hash.data, rhs.leaf_hash.c_str(),
+         std::min(32ul, rhs.leaf_hash.size()));
+  return net::SHA256HashValueLessThan().operator()(lhs_hash, rhs_hash);
+}
 
 SingleTreeTracker::SingleTreeTracker(
-    scoped_refptr<const net::CTLogVerifier> ct_log)
-    : ct_log_(std::move(ct_log)) {}
+    scoped_refptr<const net::CTLogVerifier> ct_log,
+    LogDnsClient* dns_client)
+    : ct_log_(std::move(ct_log)),
+      checked_entries_(kCheckedEntriesCacheSize),
+      dns_client_(dns_client),
+      weak_factory_(this) {
+  memory_pressure_listener_.reset(new base::MemoryPressureListener(base::Bind(
+      &SingleTreeTracker::OnMemoryPressure, base::Unretained(this))));
+}
 
 SingleTreeTracker::~SingleTreeTracker() {}
 
 void SingleTreeTracker::OnSCTVerified(
     net::X509Certificate* cert,
     const net::ct::SignedCertificateTimestamp* sct) {
   DCHECK_EQ(ct_log_->key_id(), sct->log_id);
 
-  // SCT was previously observed, so its status should not be changed.
-  if (entries_status_.find(sct->timestamp) != entries_status_.end())
+  EntryToAudit entry(cert, sct);
+  if (!entry.is_valid())
     return;
 
+  // Enqueue an entry for auditing if it was not previously observed
+  // and there's space in the queue.
+  if (GetLogEntryInclusionStatus(entry) != SCT_NOT_OBSERVED) {
+    ProcessPendingEntries();
+    return;
+  }
+
+  if (pending_entries_.size() >= kPendingEntriesQueueSize) {
+    // Queue is full - cannot audit SCT.
+    LogCanBeCheckedForInclusionToUMA(NOT_AUDITED);
+    ProcessPendingEntries();
+    return;
+  }
+
   // If there isn't a valid STH or the STH is not fresh enough to check
   // inclusion against, store the SCT for future checking and return.
   if (verified_sth_.timestamp.is_null() ||
-      (verified_sth_.timestamp <
-       (sct->timestamp + base::TimeDelta::FromHours(24)))) {
-    entries_status_.insert(
-        std::make_pair(sct->timestamp, SCT_PENDING_NEWER_STH));
+      !IsSCTReadyForAudit(verified_sth_.timestamp, entry.sct_timestamp)) {
+    pending_entries_.insert(
+        std::make_pair(std::move(entry), EntryAuditState(PENDING_NEWER_STH)));
 
-    if (!verified_sth_.timestamp.is_null()) {
+    if (verified_sth_.timestamp.is_null()) {
+      LogCanBeCheckedForInclusionToUMA(VALID_STH_REQUIRED);
+    } else {
       LogCanBeCheckedForInclusionToUMA(NEWER_STH_REQUIRED);
-    } else {
-      LogCanBeCheckedForInclusionToUMA(VALID_STH_REQUIRED);
     }
-
-    return;
+  } else {
+    LogCanBeCheckedForInclusionToUMA(CAN_BE_CHECKED);
+    pending_entries_.insert(std::make_pair(
+        std::move(entry), EntryAuditState(PENDING_LEAF_INDEX_REQUEST)));
   }
 
-  LogCanBeCheckedForInclusionToUMA(CAN_BE_CHECKED);
-  // TODO(eranm): Check inclusion here.
-  entries_status_.insert(
-      std::make_pair(sct->timestamp, SCT_PENDING_INCLUSION_CHECK));
+  // TODO(eranm): Call this method only if an entry was queued.
+  // The only reason this method is called even if a new entry was not queued
+  // is the way throttling in the LogDnsClient is currently implemented:
+  // Since the LogDnsClient will invoke the callback with

[Ryan Sleevi, 2016/09/22 07:08:29]

Right, LogDnsClient absolutely needs a way to directly signal to consumers once
it's no longer throttling.

The pattern recommended here would be something like

int rv = dns_client_->DoStuff(...);
if (rv == ERR_TEMPORARILY_TRHOTTLED) {
  dns_client_->NotifyWhenNotBusy(base::Bind(&SingleTreeTracker::OnSomething,
weak_factory_.GetWeakPtr()));
  return;
}

And dns_client_ can then just

// Do work
// Enter a state where it is about to yield, and is ready for more work
for (const auto& observer : observers_) {
  PostTask(observer);
}
observers_.clear();
// Yield


Note that I wrote it in the way above because there's all sorts of nuances to
consider here. An Observer* pattern would likely feed the first observer while
constantly starving out other observers, so you likely don't want the watching
"permanent". You also don't want to PostTask the moment you've drained
something, since you may need to invoke it's callback, which could cause the
draining-tasks SingleTreeTracker to ProcessPendingEntries again and fill the
queue. Granted, you still have a starvation risk with the above pattern, but
unless you implement the queuing in the SingleTreeTracker along with some
round-robin scheme of notification, I don't think you an escape that.

[Eran Messeri, 2016/09/22 20:10:21]

Thanks, that's exactly the advice I was after on how to un-throttle.

I'm not too worried about starvation with the above pattern since not all
SingleTreeTrackers will have queues of the same size -  some logs are more
popular than others and so more SCTs from the popular logs will be observed.

+  // ERR_TEMPORARILY_THROTTLED to let the caller know a request has been
+  // throttled, it is possible that the |pending_entries_| queue is full with
+  // pending entries whose requests have been throttled.
+  // In that case the queue will never get emptied since nothing will trigger
+  // ProcessPendingEntries.
+  // Trigger handling of pending requests here to handle the case of a full
+  // |pending_entries_| queue.
+  ProcessPendingEntries();
 }
 
 void SingleTreeTracker::NewSTHObserved(const SignedTreeHead& sth) {
   DCHECK_EQ(ct_log_->key_id(), sth.log_id);
 
   if (!ct_log_->VerifySignedTreeHead(sth)) {
     // Sanity check the STH; the caller should have done this
     // already, but being paranoid here.
     // NOTE(eranm): Right now there's no way to get rid of this check here
     // as this is the first object in the chain that has an instance of
     // a CTLogVerifier to verify the STH.
     return;
   }
 
   // In order to avoid updating |verified_sth_| to an older STH in case
   // an older STH is observed, check that either the observed STH is for
   // a larger tree size or that it is for the same tree size but has
   // a newer timestamp.
   const bool sths_for_same_tree = verified_sth_.tree_size == sth.tree_size;
   const bool received_sth_is_for_larger_tree =
       (verified_sth_.tree_size > sth.tree_size);
   const bool received_sth_is_newer = (sth.timestamp > verified_sth_.timestamp);
 
   if (verified_sth_.timestamp.is_null() || received_sth_is_for_larger_tree ||
       (sths_for_same_tree && received_sth_is_newer)) {
     verified_sth_ = sth;
+  } else {
+    // Observed an old STH - do nothing.
+    return;

[Ryan Sleevi, 2016/09/22 07:08:28]

Rewrite the condition then to make the 'return' the fast-path

[Eran Messeri, 2016/09/22 20:10:21]

Done.

   }
 
   // Find out which SCTs can now be checked for inclusion.
-  // TODO(eranm): Keep two maps of MerkleTreeLeaf instances, one for leaves
-  // pending inclusion checks and one for leaves pending a new STH.
-  // The comparison function between MerkleTreeLeaf instances should use the
-  // timestamp to determine sorting order, so that bulk moving from one
-  // map to the other can happen.
-  auto entry = entries_status_.begin();
-  while (entry != entries_status_.end() &&
-         entry->first < verified_sth_.timestamp) {
-    entry->second = SCT_PENDING_INCLUSION_CHECK;
-    ++entry;
-    // TODO(eranm): Check inclusion here.
-  }
+  auto pending_sth_state_compare =
+      [](std::pair<const EntryToAudit&, const EntryAuditState&> value) {
+        return value.second.state == PENDING_NEWER_STH;
+      };

[Ryan Sleevi, 2016/09/22 07:08:28]

My same remarks about callback temporaries apply to lambda temporaries that are
only used once.

[Eran Messeri, 2016/09/22 20:10:21]

Done.

+
+  // Find the first entry in the PENDING_NEWER_STH state - entries
+  // before that should be pending leaf index / inclusion proof, no
+  // reason to inspect them.
+  auto first_entry_to_audit =
+      std::find_if(pending_entries_.begin(), pending_entries_.end(),
+                   pending_sth_state_compare);
+
+  auto sth_timestamp_compare = [](
+      std::pair<const EntryToAudit&, const EntryAuditState&> value,
+      base::Time sth_timestamp) {
+    return IsSCTReadyForAudit(sth_timestamp, value.first.sct_timestamp);
+  };
+  // Find where to stop - this is the first entry whose timestamp + MMD
+  // is greater than the STH's timestamp.
+  auto entry_to_stop_at =
+      std::lower_bound(pending_entries_.begin(), pending_entries_.end(),

[Ryan Sleevi, 2016/09/22 07:08:28]

BUG? Shouldn't this be first_entry_to_audit, not pending_entries_.begin() ?
Otherwise, what guarantee are you to have that curr_entry < entry_to_stop_at ?

[Eran Messeri, 2016/09/22 20:10:20]

Changed to first_entry_to_audit rather than pending_entries_.begin().
Given the ordering by timestamp and the fact that only entries before a certain
timestamp change state to other than pending, there should not be any entry in a
state other than PENDING_NEWER_STH after first_entry_to_audit.
We could DCHECK for this invariant if you think that's valuable? 

+                       sth.timestamp, sth_timestamp_compare);
+
+  auto curr_entry = first_entry_to_audit;

[Ryan Sleevi, 2016/09/22 07:08:28]

for (auto curr_entry = first_entry_to_audit; curr_entry != entry_to_stop_at;
++curr_entry) {
  DCHECK_EQ(PENDING_NEWER_STH, curr_entry->second.state);
  curr_entry->second.state = PENDING_LEAF_INDEX_REQUEST;
}

?

[Eran Messeri, 2016/09/22 20:10:21]

Done.

+  // Update the state of all entries that can now be checked for inclusion.
+  while (curr_entry != entry_to_stop_at) {
+    DCHECK(curr_entry->second.state == PENDING_NEWER_STH);
+    curr_entry->second.state = PENDING_LEAF_INDEX_REQUEST;
+    ++curr_entry;
+  }
+
+  ProcessPendingEntries();
 }
 
 SingleTreeTracker::SCTInclusionStatus
 SingleTreeTracker::GetLogEntryInclusionStatus(
     net::X509Certificate* cert,
     const net::ct::SignedCertificateTimestamp* sct) {
-  auto it = entries_status_.find(sct->timestamp);
-
-  return it == entries_status_.end() ? SCT_NOT_OBSERVED : it->second;
+  EntryToAudit entry(cert, sct);
+  return GetLogEntryInclusionStatus(entry);

[Ryan Sleevi, 2016/09/22 07:08:29]

There's a noticeable asymmetry here with the callers to
GetLogEntryInclusionStatus - one which checks entry.is_valid() before calling,
the other (this) which depends on GetLogEntryInclusionStatus doing that check.

I'm not clear which is better, although I suspect it's "caller checks" given 
you've only got two callers.

[Eran Messeri, 2016/09/22 20:10:20]

Obsolete - the entry no longer has is_valid method and we don't create it if we
don't have a valid hash.

+}
+
+void SingleTreeTracker::FetchIndexForEntry(const EntryToAudit& entry) {
+  const EntryToAudit* entry_ptr = &entry;

[Ryan Sleevi, 2016/09/22 07:08:28]

This makes me *really* nervous - |entry| could be a stack-local with the way
this function is written.

I cannot convince myself this is safe.

[Eran Messeri, 2016/09/22 20:10:21]

Obsolete - inlined this function (though my preference would have been to leave
it, but that meant passing in a pointer as input parameter, which is against the
style guide AFAIK).

+
+  LogDnsClient::LeafIndexCallback leaf_index_callback =
+      base::Bind(&SingleTreeTracker::OnLeafIndexObtained,
+                 weak_factory_.GetWeakPtr(), entry_ptr);

[Ryan Sleevi, 2016/09/22 07:08:28]

I think I may have mentioned in other CLs, but I personally find this approach -
of stashing callbacks in temporaries - hinders, rather than helps, readability
in understanding how things work/are executed, especially in CodeSearch.

Unless there is specific and concrete need, please prefer to avoid ever creating
stack-local callbacks. Beyond avoiding some additional refcount churn, I believe
this helps keep the code more readable :)

[Eran Messeri, 2016/09/22 20:10:20]

Done - in-lined callback creation. 
You may have mentioned that, I find the other approach works better for me -
that keeping intermediate values in temporary variables, has two benefits in my
opinion:
(1) Documentation: The variable name serves as a description of what the
intermediate value is.
(2) Readability of complex/long statements: where it reduces the nesting of
expressions. In this case, it makes it easier to see what's being passed into
QueryLeafIndex.

Since you find the other way more readable and you do have to review everything
going into //components/certificate_transparency, I'll stick to your suggested
approach.

+
+  dns_client_->QueryLeafIndex(ct_log_->dns_domain(), entry.leaf_hash,
+                              leaf_index_callback);
+}
+
+void SingleTreeTracker::FetchInclusionForEntry(const EntryToAudit& entry,
+                                               uint64_t leaf_index,
+                                               uint64_t tree_size) {
+  LogDnsClient::AuditProofCallback audit_proof_callback =
+      base::Bind(&SingleTreeTracker::OnAuditProofObtained,
+                 weak_factory_.GetWeakPtr(), &entry, tree_size);
+
+  dns_client_->QueryAuditProof(ct_log_->dns_domain(), leaf_index, tree_size,
+                               audit_proof_callback);
+}
+
+void SingleTreeTracker::ProcessPendingEntries() {
+  auto it = pending_entries_.begin();
+  while (it != pending_entries_.end()) {
+    if (it->second.state == PENDING_LEAF_INDEX_REQUEST) {
+      it->second.tree_size = verified_sth_.tree_size;
+      FetchIndexForEntry(it->first);
+      it->second.state = LEAF_INDEX_REQUESTED;
+      break;
+    } else if (it->second.state == PENDING_INCLUSION_PROOF_REQUEST) {
+      FetchInclusionForEntry(it->first, it->second.leaf_index,
+                             it->second.tree_size);
+      it->second.state = INCLUSION_PROOF_REQUESTED;
+      break;
+    }
+    ++it;
+  }
+}
+
+SingleTreeTracker::SCTInclusionStatus
+SingleTreeTracker::GetLogEntryInclusionStatus(const EntryToAudit& entry) {
+  if (!entry.is_valid())
+    return SCT_NOT_OBSERVED;
+
+  auto checked_entries_iterator = checked_entries_.Get(entry.leaf_hash);
+  if (checked_entries_iterator != checked_entries_.end()) {
+    // Only success is cached, so all values in |checked_entries_|
+    // should be true.
+    DCHECK(checked_entries_iterator->second);
+    return SCT_INCLUDED_IN_LOG;
+  }
+
+  auto pending_iterator = pending_entries_.find(entry);
+  if (pending_iterator != pending_entries_.end()) {
+    switch (pending_iterator->second.state) {
+      case PENDING_NEWER_STH:
+        return SCT_PENDING_NEWER_STH;
+      case PENDING_LEAF_INDEX_REQUEST:
+      case LEAF_INDEX_REQUESTED:
+      case PENDING_INCLUSION_PROOF_REQUEST:
+      case INCLUSION_PROOF_REQUESTED:
+        return SCT_PENDING_INCLUSION_CHECK;
+    }
+    NOTREACHED();
+  }
+
+  return SCT_NOT_OBSERVED;
+}
+
+void SingleTreeTracker::OnLeafIndexObtained(const EntryToAudit* entry,
+                                            int net_error,
+                                            uint64_t leaf_index) {
+  auto it = pending_entries_.find(*entry);
+  // The entry may not be present if it was evacuated due to low memory
+  // pressure.
+  if (it == pending_entries_.end()) {
+    ProcessPendingEntries();
+    return;
+  }
+
+  DCHECK(it->second.state == LEAF_INDEX_REQUESTED);
+
+  if (net_error == net::OK) {
+    it->second.state = PENDING_INCLUSION_PROOF_REQUEST;
+    it->second.leaf_index = leaf_index;
+  } else if (net_error == net::Error::ERR_TEMPORARILY_THROTTLED) {
+    // We've been throttled - revert the state of this entry to
+    // the pending state and indicate the tree tracker should
+    // no longer issue new requests.
+    it->second.state = PENDING_LEAF_INDEX_REQUEST;
+    // Break early to avoid calling ProcessPendingEntries - as requests
+    // are being throttled, there's no point in sending more of them.
+    return;
+  } else {
+    // XXX(eranm): Should failures be cached? For now, they are not.
+    // TODO(eranm): Log failure.
+    pending_entries_.erase(it);
+  }
+
+  ProcessPendingEntries();
+}
+
+void SingleTreeTracker::OnAuditProofObtained(
+    const EntryToAudit* entry,
+    uint64_t tree_size,
+    int net_error,
+    std::unique_ptr<net::ct::MerkleAuditProof> proof) {
+  auto it = pending_entries_.find(*entry);
+  // The entry may not be present if it was evacuated due to low memory
+  // pressure.
+  if (it == pending_entries_.end()) {
+    ProcessPendingEntries();
+    return;
+  }
+
+  DCHECK(it->second.state == INCLUSION_PROOF_REQUESTED);
+
+  if (net_error == net::OK) {
+    // TODO(eranm): Once the CTLogVerifier supports that, actually verify the
+    // proof.
+    // TODO(eranm): Log success.
+    checked_entries_.Put(it->first.leaf_hash, true);
+    pending_entries_.erase(it);
+  } else if (net_error == net::Error::ERR_TEMPORARILY_THROTTLED) {
+    // See the documentation in OnLeafIndexObtained on handling the throttled
+    // case.
+    it->second.state = PENDING_INCLUSION_PROOF_REQUEST;
+    return;
+  } else {
+    // XXX(eranm): Should failures be cached? For now, they are not.
+    // TODO(eranm): Log failure.
+    pending_entries_.erase(it);
+  }
+
+  ProcessPendingEntries();
+}
+
+void SingleTreeTracker::OnMemoryPressure(
+    base::MemoryPressureListener::MemoryPressureLevel memory_pressure_level) {
+  switch (memory_pressure_level) {
+    case base::MemoryPressureListener::MEMORY_PRESSURE_LEVEL_NONE:
+      break;

[Ryan Sleevi, 2016/09/22 07:08:28]

Is this necessary? I'm guessing yes (Compiler warning?), but might be useful for
documentation.

[Eran Messeri, 2016/09/22 20:10:21]

Yes, it is. Are you suggesting I document it?

+    case base::MemoryPressureListener::MEMORY_PRESSURE_LEVEL_CRITICAL:
+      pending_entries_.clear();

[Ryan Sleevi, 2016/09/22 07:08:29]

https://google.github.io/styleguide/cppguide.html#Loops_and_Switch_Statements

"Annotate non-trivial fall-through between cases"

This one threw me for a loop when reading, whether or not the break was
intentional.

[Eran Messeri, 2016/09/22 20:10:21]

Done.

+    case base::MemoryPressureListener::MEMORY_PRESSURE_LEVEL_MODERATE:
+      checked_entries_.Clear();
+      break;
+  }
 }
 
 }  // namespace certificate_transparency