text: /*
   * Copyright 2013 Google Inc.
   *
   * Licensed 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.
   */
  
  // Author: jud@google.com (Jud Porter)
  
  #include "net/instaweb/rewriter/public/critical_finder_support_util.h"
  
  #include <algorithm>
  #include <map>
  #include <set>
  #include <utility>
  
  #include "base/logging.h"
  #include "net/instaweb/public/global_constants.h"
  #include "net/instaweb/rewriter/critical_keys.pb.h"
  #include "net/instaweb/rewriter/public/property_cache_util.h"
  #include "net/instaweb/rewriter/public/rewrite_driver.h"
  #include "net/instaweb/rewriter/public/rewrite_options.h"
  #include "net/instaweb/util/public/property_cache.h"
  #include "pagespeed/kernel/base/base64_util.h"
  #include "pagespeed/kernel/base/message_handler.h"
  #include "pagespeed/kernel/base/scoped_ptr.h"
  #include "pagespeed/kernel/base/string_util.h"
  #include "pagespeed/kernel/base/timer.h"
  #include "pagespeed/kernel/http/request_headers.h"
  #include "pagespeed/kernel/util/nonce_generator.h"
  
  namespace net_instaweb {
  
  namespace {
  
  typedef std::map<GoogleString, int> SupportMap;
  
  // *dest += addend, but capping at kint32max
  inline void SaturatingAddTo(int32 addend, int32* dest) {
    int64 result = *dest;
    result += addend;
    *dest = (result > kint32max) ? kint32max : static_cast<int32>(result);
  }
  
  bool LessBySupportMapValue(const SupportMap::value_type& pair1,
                             const SupportMap::value_type& pair2) {
      return (pair1.second < pair2.second);
  }
  
  SupportMap ConvertCriticalKeysProtoToSupportMap(
      const CriticalKeys& critical_keys) {
    SupportMap support_map;
    // Start by reading in the support data.
    for (int i = 0; i < critical_keys.key_evidence_size(); ++i) {
      const CriticalKeys::KeyEvidence& evidence = critical_keys.key_evidence(i);
      if (!evidence.key().empty()) {
        // We aggregate here just in case of a corrupt duplicate entry.
        SaturatingAddTo(evidence.support(), &support_map[evidence.key()]);
      }
    }
    return support_map;
  }
  
  void WriteSupportMapToCriticalKeysProto(const SupportMap& support_map,
                                          CriticalKeys* critical_keys) {
    // Clean out the existing evidence and inject the fresh evidence.
    critical_keys->clear_key_evidence();
    for (SupportMap::const_iterator entry = support_map.begin();
         entry != support_map.end(); ++entry) {
      CriticalKeys::KeyEvidence* evidence = critical_keys->add_key_evidence();
      evidence->set_key(entry->first);
      evidence->set_support(entry->second);
    }
  }
  
  // Decay a single support value by multiplying it by k / (k+1), rounding down.
  // Fractional arithmetic done in int64 to avoid int overflow.
  inline int Decay(int support_interval, int64 support_value) {
    support_value *= support_interval;
    support_value /= support_interval + 1;
    return support_value;
  }
  
  // Decay support, deleting elements whose support drops to 0.
  void DecaySupportMap(int support_interval, SupportMap* support_map) {
    SupportMap::iterator next = support_map->begin(), end = support_map->end();
    while (next != end) {
      // We increment at the top of the loop so that we can erase curr
      // without invalidating next.  See:
      // http://stackoverflow.com/questions/2874441/deleting-elements-from-stl-set-while-iterating
      SupportMap::iterator curr = next++;
      // Multiply support_value by the fraction
      // support_interval / (support_interval + 1)
      // using int64 to avoid overflow.
      int support_value = Decay(support_interval, curr->second);
      if (support_value == 0 && curr->second > 0) {
        // Remove entry when its support falls to 0 (this will expire entries that
        // should not be candidates; if curr should still be a candidate, we will
        // re-insert it as part of beaconing).
        support_map->erase(curr);
      } else {
        curr->second = static_cast<int32>(support_value);
      }
    }
  }
  
  void ClearInvalidNonces(const int64 now_ms, CriticalKeys* critical_keys) {
    // Invalidate expired entries, and if no valid entries remain then delete all
    // outstanding entries.
    bool found_valid_nonce = false;
    for (int i = 0; i < critical_keys->pending_nonce_size(); ++i) {
      CriticalKeys::PendingNonce* entry = critical_keys->mutable_pending_nonce(i);
      if (!entry->has_nonce()) {
        // Entry unoccupied.  Fall through.
      } else if ((entry->timestamp_ms() + kBeaconTimeoutIntervalMs) < now_ms) {
        entry->clear_timestamp_ms();
        entry->clear_nonce();
        critical_keys->set_nonces_recently_expired(
            critical_keys->nonces_recently_expired() + 1);
      } else {
        found_valid_nonce = true;
      }
    }
    if (!found_valid_nonce) {
      critical_keys->clear_pending_nonce();
    }
  }
  
  // Generate a nonce and record the existence of a beacon with that nonce sent at
  // timestamp_ms, updating *nonce with the new value.
  void AddNonceToCriticalSelectors(const int64 timestamp_ms,
                                   NonceGenerator* nonce_generator,
                                   CriticalKeys* critical_keys,
                                   GoogleString* nonce) {
    CHECK(nonce_generator != NULL);
    uint64 nonce_value = nonce_generator->NewNonce();
    StringPiece nonce_piece(reinterpret_cast<char*>(&nonce_value),
                            sizeof(nonce_value));
    Web64Encode(nonce_piece, nonce);
    if (nonce->size() > 11) {
      // Only keep the first 66 bits of nonce since original value is 64 bits.
      nonce->resize(11);
    }
    ClearInvalidNonces(timestamp_ms, critical_keys);
    // Look for an invalid entry to reuse.
    CriticalKeys::PendingNonce* pending_nonce = NULL;
    for (int i = 0; i < critical_keys->pending_nonce_size(); ++i) {
      CriticalKeys::PendingNonce* entry = critical_keys->mutable_pending_nonce(i);
      if (!entry->has_nonce()) {
        pending_nonce = entry;
        break;
      }
    }
    if (pending_nonce == NULL) {
      // No entry to reuse; create new entry
      pending_nonce = critical_keys->add_pending_nonce();
    }
    pending_nonce->set_timestamp_ms(timestamp_ms);
    pending_nonce->set_nonce(*nonce);
  }
  
  }  // namespace
  
  // Check whether the given nonce is valid, invalidating any expired nonce
  // entries we might encounter.  To avoid the need to copy and clear the nonce
  // list, we invalidate the entry used and any expired entries by clearing the
  // nonce value and timestamp.  These entries will be reused by
  // AddNonceToCriticalSelectors.
  bool ValidateAndExpireNonce(int64 now_ms, StringPiece nonce,
                              CriticalKeys* critical_keys) {
    if (nonce.empty()) {
      // Someone sent us a clearly bogus beacon result.
      return false;
    }
    ClearInvalidNonces(now_ms, critical_keys);
    for (int i = 0; i < critical_keys->pending_nonce_size(); ++i) {
      CriticalKeys::PendingNonce* entry = critical_keys->mutable_pending_nonce(i);
      if (nonce == entry->nonce()) {
        // Matched.  Entry is valid.  Remove it.
        entry->clear_timestamp_ms();
        entry->clear_nonce();
        return true;
      }
    }
    return false;
  }
  
  void GetCriticalKeysFromProto(int64 support_percentage,
                                const CriticalKeys& critical_keys,
                                StringSet* keys) {
    int64 support_threshold =
        (support_percentage == 0) ?
        1 : (support_percentage * critical_keys.maximum_possible_support());
    // Collect supported beacon results
    for (int i = 0; i < critical_keys.key_evidence_size(); ++i) {
      const CriticalKeys::KeyEvidence& evidence = critical_keys.key_evidence(i);
      // Do percentage conversion on support value using int64 to avoid overflow.
      int64 support = evidence.support();
      if (support * 100 >= support_threshold && !evidence.key().empty()) {
        keys->insert(evidence.key());
      }
    }
  }
  
  // Merge the given set into the existing critical key proto by adding
  // support for new_set to existing support.
  void UpdateCriticalKeys(bool require_prior_support,
                          const StringSet& new_set, int support_value,
                          CriticalKeys* critical_keys) {
    DCHECK(critical_keys != NULL);
    SupportMap support_map = ConvertCriticalKeysProtoToSupportMap(*critical_keys);
    DecaySupportMap(support_value, &support_map);
    // Update maximum_possible_support.  Initial value must account for legacy
    // data.
    int maximum_support;
    if (critical_keys->has_maximum_possible_support()) {
      maximum_support =
          Decay(support_value, critical_keys->maximum_possible_support());
    } else if (support_map.empty()) {
      maximum_support = 0;
    } else {
      maximum_support = std::max_element(support_map.begin(), support_map.end(),
                                         LessBySupportMapValue)->second;
    }
    SaturatingAddTo(support_value, &maximum_support);
    critical_keys->set_maximum_possible_support(maximum_support);
    // Actually add the new_set to the support_map.
    if (require_prior_support) {
      for (StringSet::const_iterator s = new_set.begin();
           s != new_set.end(); ++s) {
        // Only add entries that are already in the support_map
        // (critical_css_beacon_filter initializes candidate entries to have
        // support 0).  This avoids a cache-fill DoS with spurious beacon data.
        SupportMap::iterator entry = support_map.find(*s);
        if (entry != support_map.end()) {
          SaturatingAddTo(support_value, &entry->second);
        }
      }
    } else {
      // Unconditionally add entries to support_map.
      for (StringSet::const_iterator s = new_set.begin();
           s != new_set.end(); ++s) {
        SaturatingAddTo(support_value, &support_map[*s]);
      }
    }
    critical_keys->set_valid_beacons_received(
        critical_keys->valid_beacons_received() + 1);
    critical_keys->set_nonces_recently_expired(0);
    WriteSupportMapToCriticalKeysProto(support_map, critical_keys);
  }
  
  void WriteCriticalKeysToPropertyCache(
      const StringSet& new_keys, StringPiece nonce, int support_interval,
      CriticalKeysWriteFlags flags,
      StringPiece property_name, const PropertyCache* cache,
      const PropertyCache::Cohort* cohort, AbstractPropertyPage* page,
      MessageHandler* message_handler, Timer* timer) {
    // We can't do anything here if page is NULL, so bail out early.
    if (page == NULL) {
      return;
    }
    scoped_ptr<CriticalKeys> critical_keys;
    // TODO(jud): Consider refactoring this into the subclasses as part of the
    // WriteCriticalSelectors refactoring that's ongoing.  Note that this may
    // break slamm's tests at the bottom of critical_selector_finder_test.cc
    // depending on how subclassing is done, so some care will be required.
    if (flags & kReplacePriorResult) {
      critical_keys.reset(new CriticalKeys);
    } else {
      // We first need to read the current critical keys in the property cache,
      // then update it with the new set if it exists, or create it if it doesn't.
      PropertyCacheDecodeResult decode_result;
      critical_keys.reset(DecodeFromPropertyCache<CriticalKeys>(
          cache, page, cohort, property_name, -1, &decode_result));
      switch (decode_result) {
        case kPropertyCacheDecodeOk:
          // We successfully decoded the property cache value, so use the returned
          // CriticalKeys.
          break;
        case kPropertyCacheDecodeNotFound:
          // We either got here because the property cache is not set up correctly
          // (the cohort doesn't exist), or we just don't have a value already.
          // For the former, bail out since there is no use trying to update the
          // property cache if it is not setup. For the later, create a new
          // CriticalKeys, since we just haven't written a value before.
          if (cohort == NULL) {
            return;
          }
          FALLTHROUGH_INTENDED;
        case kPropertyCacheDecodeExpired:
        case kPropertyCacheDecodeParseError:
          // We can proceed here, but we need to create a new CriticalKeys.
          critical_keys.reset(new CriticalKeys);
          break;
      }
  
      if (!(flags & kSkipNonceCheck) &&
          !ValidateAndExpireNonce(timer->NowMs(), nonce, critical_keys.get())) {
        return;
      }
    }
    UpdateCriticalKeys(flags & kRequirePriorSupport, new_keys, support_interval,
                       critical_keys.get());
  
    PropertyCacheUpdateResult result = UpdateInPropertyCache(
        *critical_keys, cohort, property_name, false /* write_cohort */, page);
    switch (result) {
      case kPropertyCacheUpdateNotFound:
        message_handler->MessageS(kWarning,
                                  "Unable to get Critical keys set for update.");
        break;
      case kPropertyCacheUpdateEncodeError:
        message_handler->MessageS(kWarning, "Trouble marshaling CriticalKeys!?");
        break;
      case kPropertyCacheUpdateOk:
        // Nothing more to do.
        break;
    }
  }
  
  bool ShouldBeacon(const CriticalKeys& proto, const RewriteDriver& driver) {
    // When downstream cache integration is enabled, and there is a rebeaconing
    // key already specified in the config, we should only rebeacon when there
    // is a matching key in the beacon requesting header.
    if (driver.options()->IsDownstreamCacheIntegrationEnabled() &&
        driver.options()->IsDownstreamCacheRebeaconingKeyConfigured()) {
      return driver.options()->MatchesDownstreamCacheRebeaconingKey(
          driver.request_headers()->Lookup1(kPsaShouldBeacon));
    }
    int64 now_ms = driver.timer()->NowMs();
    return now_ms >= proto.next_beacon_timestamp_ms();
  }
  
  void PrepareForBeaconInsertionHelper(CriticalKeys* proto,
                                       NonceGenerator* nonce_generator,
                                       RewriteDriver* driver,
                                       bool using_candidate_key_detection,
                                       BeaconMetadata* result) {
    result->status = kDoNotBeacon;
    if (!ShouldBeacon(*proto, *driver)) {
      return;
    }
  
    if (driver->options()->IsDownstreamCacheIntegrationEnabled() &&
        !driver->options()->IsDownstreamCacheRebeaconingKeyConfigured()) {
      // Note that we do not put out this message on a per request basis, because
      // it will clutter up the logs. Instead we do it only once every beaconing
      // interval.
      driver->message_handler()->Message(
          kWarning,
          "You seem to have downstream caching configured on your server. "
          "DownstreamCacheRebeaconingKey should also be set for this to work "
          "correctly. Refer to "
          "https://developers.google.com/speed/pagespeed/module/"
          "downstream-caching#beaconing "
          "for more details.");
    }
    // We need to rebeacon so update the timestamp for the next time to
    // rebeacon. If we are using candidate key detection, then check how many
    // valid beacons we have received since the last time the candidate keys
    // changed to determine if we are doing high frequency vs low frequency
    // beaconing.
    // TODO(jmaessen): Add noise to inter-beacon interval.  How? Currently first
    // visit to page after next_beacon_timestamp_ms will beacon.
    int64 beacon_reinstrument_time_ms =
        driver->options()->beacon_reinstrument_time_sec() * Timer::kSecondMs;
    if ((proto->nonces_recently_expired() > kNonceExpirationLimit) ||
        (using_candidate_key_detection &&
         (proto->valid_beacons_received() >= kHighFreqBeaconCount))) {
      beacon_reinstrument_time_ms *= kLowFreqBeaconMult;
    }
    int64 now_ms = driver->timer()->NowMs();
    proto->set_next_beacon_timestamp_ms(now_ms + beacon_reinstrument_time_ms);
  
    AddNonceToCriticalSelectors(now_ms, nonce_generator, proto, &result->nonce);
    result->status = kBeaconWithNonce;
  }
  
  bool UpdateCandidateKeys(const StringSet& keys, CriticalKeys* proto,
                           bool clear_rebeacon_timestamp) {
    // Check to see if candidate keys are already known to pcache.  Insert
    // previously-unknown candidates with a support of 0, to indicate that beacon
    // results for those keys will be considered valid.  Other keys returned in a
    // beacon result will simply be ignored, avoiding DoSing the pcache.  New
    // candidate keys cause us to re-beacon.
    SupportMap support_map = ConvertCriticalKeysProtoToSupportMap(*proto);
    bool support_map_changed = false;
    for (StringSet::const_iterator i = keys.begin(), end = keys.end(); i != end;
         ++i) {
      if (support_map.insert(pair<GoogleString, int>(*i, 0)).second) {
        support_map_changed = true;
      }
    }
    if (support_map_changed) {
      // The candidate keys changed, so we need to go into high frequency
      // beaconing mode. Reset the number of beacons received to signal this.
      proto->set_valid_beacons_received(0);
      // Clear the rebeaconing timestamp to force rebeaconing if requested.
      if (clear_rebeacon_timestamp) {
        proto->clear_next_beacon_timestamp_ms();
      }
      // Update the proto value with the new set of keys. Note that we are not
      // changing the calculated set of critical keys, so we don't need to
      // update the state in the RewriteDriver.
      WriteSupportMapToCriticalKeysProto(support_map, proto);
      return true;
    }
  
    return false;
  }
  
  }  // namespace net_instaweb
  