// Copyright 2016 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: cheesy@google.com (Steve Hill)

#ifndef PAGESPEED_CONTROLLER_POPULARITY_CONTEST_SCHEDULE_REWRITE_CONTROLLER_H_
#define PAGESPEED_CONTROLLER_POPULARITY_CONTEST_SCHEDULE_REWRITE_CONTROLLER_H_

#include <cstddef>
#include <unordered_map>

#include "pagespeed/controller/priority_queue.h"
#include "pagespeed/controller/schedule_rewrite_controller.h"
#include "pagespeed/kernel/base/abstract_mutex.h"
#include "pagespeed/kernel/base/basictypes.h"
#include "pagespeed/kernel/base/function.h"
#include "pagespeed/kernel/base/statistics.h"
#include "pagespeed/kernel/base/string.h"
#include "pagespeed/kernel/base/timer.h"
#include "pagespeed/kernel/base/scoped_ptr.h"
#include "pagespeed/kernel/base/thread_annotations.h"
#include "pagespeed/kernel/base/thread_system.h"

// Implementation of ScheduleRewriteController that uses priority queue to
// process rewrites in the order of most requested. Gurantees that at most one
// client will be waiting for a given key. Also limits the number of queued
// rewrites and the number of rewrites running in parallel.
//
// Every request is tracked in a Rewrite object, the lifetime of which is
// described by the following state digram:
//
//      begin
//        |
//  +-----v-----+
//  |           | Queue full
//  |  STOPPED  +-----------> delete <---------+
//  |           |                              |
//  +-----+-----+                              |
//        |                                    |
// ScheduleRewrite()                           | Other Rewrite needs
//        |    +----+                          | slot in queue and
//        |    |    | ScheduleRewrite()        | this is oldest rewrite
//  +-----v----+-+  | (increments priority     | in AWAITING_RETRY.
//  |            <--+  discards old request)   |
//  |   QUEUED   |                             |
//  |            <--+    ScheduleRewrite()  +--+-------+
//  +-----+------+  |  (increments priority)|          |
//        |         +-----------------------+ AWAITING |
//     Pop Queue                            |  RETRY   |
// (when most requested)                    |          |
//        |                                 +----^-----+
//        |   +-----+                            |
//        |   |     | ScheduleRewrite()          |
//  +-----v---+-+   | (increments priority       |
//  |           |   |  rejects new request)      |
//  |  RUNNING  <---+                            |
//  |           |                                |
//  +--+----+---+                                |
//     |    |                                    |
//     |    +------------------------------------+
//     |           NotifyFailure()
//     |
//     +-----------------------------> delete
//                 NotifySuccess()

namespace net_instaweb {

class PopularityContestScheduleRewriteController
    : public ScheduleRewriteController {
 public:
  static const char kNumRewritesRequested[];
  static const char kNumRewritesSucceeded[];
  static const char kNumRewritesFailed[];
  static const char kNumRewritesRejectedQueueSize[];
  static const char kNumRewritesRejectedInProgress[];
  static const char kRewriteQueueSize[];
  static const char kNumRewritesRunning[];
  static const char kNumRewritesAwaitingRetry[];

  // max_running_rewrites and max_queued_rewrites are CHECKed to be > 0.
  // Since max_running_rewrites is implicity bounded by the queue size,
  // you probably want queued >= running, but this isn't enforced by the code.
  PopularityContestScheduleRewriteController(ThreadSystem* thread_system,
                                             Statistics* statistics,
                                             Timer* timer,
                                             int max_running_rewrites,
                                             int max_queued_rewrites);
  virtual ~PopularityContestScheduleRewriteController();

  // ScheduleRewriteController interface.
  void ScheduleRewrite(const GoogleString& key, Function* callback) override;
  void NotifyRewriteComplete(const GoogleString& key) override;
  void NotifyRewriteFailed(const GoogleString& key) override;

  static void InitStats(Statistics* stats);

 private:
  enum RewriteState {
    STOPPED,
    QUEUED,
    RUNNING,
    AWAITING_RETRY,
  };

  struct Rewrite {
    Rewrite(const GoogleString& k)
        : key(k), saved_priority(0), callback(nullptr), state(STOPPED) {}
    GoogleString key;
    int saved_priority;
    Function* callback;
    RewriteState state;
  };

  struct StringPtrHash {
    size_t operator()(const GoogleString* x) const {
      return std::hash<GoogleString>()(*x);
    }
  };

  struct StringPtrEq {
    bool operator()(const GoogleString* a, const GoogleString* b) const {
      return (a == b || *a == *b);
    }
  };

  typedef std::unordered_map<const GoogleString*, Rewrite*,
                             StringPtrHash, StringPtrEq>
      RewriteMap;

  // Consider starting the next rewrite in queue_, depending on available
  // resources. Returns either nullptr or a Function which must be run
  // *WITHOUT* mutex_ locked.
  Function* AttemptStartRewrite()
      EXCLUSIVE_LOCKS_REQUIRED(mutex_) WARN_UNUSED_RESULT;

  // Start the supplied rewrite, ie: Update bookkeeping.
  // Returns the callback from the rewrite, which must be run *WITHOUT*
  // mutex_ locked.
  Function* StartRewrite(Rewrite* rewrite)
      EXCLUSIVE_LOCKS_REQUIRED(mutex_) WARN_UNUSED_RESULT;

  // Stop the supplied rewrite. Undoes the bookkeeping from Start.
  void StopRewrite(Rewrite* rewrite) EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // Save the Rewrite so it may be retried later. The Rewrite may later be
  // discarded if the queue fills up.
  void SaveRewriteForRetry(Rewrite* rewrite) EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // If there are no remaining slots in the queue, will drop the oldest Rewrite
  // on the retry queue.
  void ConsiderDroppingRetry() EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // Retrieve or create a Rewrite by key from all_rewrites_. The return value
  // is protected by mutex_ which should remain held until you are done with
  // the Rewrite.
  Rewrite* GetRewrite(const GoogleString& key) EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // delete a Rewrite and remove it from all_rewrites_.
  void DeleteRewrite(const Rewrite* rewrite) EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // Re-assign max_queued_rewrites. For use only in tests.
  void SetMaxQueueSizeForTesting(int size) LOCKS_EXCLUDED(mutex_);

  scoped_ptr<AbstractMutex> mutex_;
  // All known rewrites, indexed by Rewrite->key. Key pointers are all owned
  // by their respective Rewrite.
  RewriteMap all_rewrites_ GUARDED_BY(mutex_);
  // No additional templates required on queue_; it uses pointer hash/eq.
  PriorityQueue<Rewrite*> queue_ GUARDED_BY(mutex_);

  // The retry queue is ordered by negative time last seen. This allows us to
  // quickly discard the oldest items, if we need to.
  PriorityQueue<Rewrite*> retry_queue_ GUARDED_BY(mutex_);

  Timer* timer_;

  int running_rewrites_ GUARDED_BY(mutex_);
  const int max_running_rewrites_;
  // max_queued_rewrites_ can't be const because of SetMaxQueueSizeForTesting.
  int max_queued_rewrites_ GUARDED_BY(mutex_);

  TimedVariable* num_rewrite_requests_;
  TimedVariable* num_rewrites_succeeded_;
  TimedVariable* num_rewrites_failed_;
  TimedVariable* num_rewrites_rejected_queue_size_;
  TimedVariable* num_rewrites_rejected_in_progress_;
  UpDownCounter* queue_size_;
  UpDownCounter* num_rewrites_running_;
  UpDownCounter* num_rewrites_awaiting_retry_;

  friend class PopularityContestScheduleRewriteControllerTest;

  DISALLOW_COPY_AND_ASSIGN(PopularityContestScheduleRewriteController);
};

}  // namespace net_instaweb

#endif  // PAGESPEED_CONTROLLER_POPULARITY_CONTEST_SCHEDULE_REWRITE_CONTROLLER_H_