// Copyright (c) 2012 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 "content/browser/loader/resource_scheduler.h"

#include "base/stl_util.h"
#include "content/common/resource_messages.h"
#include "content/browser/loader/resource_message_delegate.h"
#include "content/public/browser/resource_controller.h"
#include "content/public/browser/resource_request_info.h"
#include "content/public/browser/resource_throttle.h"
#include "ipc/ipc_message_macros.h"
#include "net/base/host_port_pair.h"
#include "net/base/load_flags.h"
#include "net/base/request_priority.h"
#include "net/http/http_server_properties.h"
#include "net/url_request/url_request.h"
#include "net/url_request/url_request_context.h"

namespace content {

static const size_t kMaxNumDelayableRequestsPerClient = 10;
static const size_t kMaxNumDelayableRequestsPerHost = 6;

// A thin wrapper around net::PriorityQueue that deals with
// ScheduledResourceRequests instead of PriorityQueue::Pointers.
class ResourceScheduler::RequestQueue {
 private:
  typedef net::PriorityQueue<ScheduledResourceRequest*> NetQueue;

 public:
  class Iterator {
   public:
    Iterator(NetQueue* queue) : queue_(queue) {
      DCHECK(queue != NULL);
      current_pointer_ = queue_->FirstMax();
    }

    Iterator& operator++() {
      current_pointer_ = queue_->GetNextTowardsLastMin(current_pointer_);
      return *this;
    }

    Iterator operator++(int) {
      Iterator result(*this);
      ++(*this);
      return result;
    }

    ScheduledResourceRequest* value() {
      return current_pointer_.value();
    }

    bool is_null() {
      return current_pointer_.is_null();
    }

   private:
    NetQueue* queue_;
    NetQueue::Pointer current_pointer_;
  };

  RequestQueue() : queue_(net::NUM_PRIORITIES) {}
  ~RequestQueue() {}

  // Adds |request| to the queue with given |priority|.
  void Insert(ScheduledResourceRequest* request,
              net::RequestPriority priority) {
    DCHECK(!ContainsKey(pointers_, request));
    NetQueue::Pointer pointer = queue_.Insert(request, priority);
    pointers_[request] = pointer;
  }

  // Removes |request| from the queue.
  void Erase(ScheduledResourceRequest* request) {
    PointerMap::iterator it = pointers_.find(request);
    DCHECK(it != pointers_.end());
    if (it == pointers_.end())
      return;
    queue_.Erase(it->second);
    pointers_.erase(it);
  }

  // Returns the highest priority request that's queued, or NULL if none are.
  ScheduledResourceRequest* FirstMax() {
    return queue_.FirstMax().value();
  }

  Iterator GetNextHighestIterator() {
    return Iterator(&queue_);
  }

  // Returns true if |request| is queued.
  bool IsQueued(ScheduledResourceRequest* request) const {
    return ContainsKey(pointers_, request);
  }

  // Returns true if no requests are queued.
  bool IsEmpty() const { return queue_.size() == 0; }

 private:
  typedef std::map<ScheduledResourceRequest*, NetQueue::Pointer> PointerMap;

  NetQueue queue_;
  PointerMap pointers_;
};

// This is the handle we return to the ResourceDispatcherHostImpl so it can
// interact with the request.
class ResourceScheduler::ScheduledResourceRequest
    : public ResourceMessageDelegate,
      public ResourceThrottle {
 public:
  ScheduledResourceRequest(const ClientId& client_id,
                           net::URLRequest* request,
                           ResourceScheduler* scheduler)
      : ResourceMessageDelegate(request),
        client_id_(client_id),
        request_(request),
        ready_(false),
        deferred_(false),
        scheduler_(scheduler) {
    TRACE_EVENT_ASYNC_BEGIN1("net", "URLRequest", request_,
                             "url", request->url().spec());
  }

  virtual ~ScheduledResourceRequest() {
    scheduler_->RemoveRequest(this);
  }

  void Start() {
    TRACE_EVENT_ASYNC_STEP_PAST0("net", "URLRequest", request_, "Queued");
    ready_ = true;
    if (deferred_ && request_->status().is_success()) {
      deferred_ = false;
      controller()->Resume();
    }
  }

  const ClientId& client_id() const { return client_id_; }
  net::URLRequest* url_request() { return request_; }
  const net::URLRequest* url_request() const { return request_; }

 private:
  // ResourceMessageDelegate interface:
  virtual bool OnMessageReceived(const IPC::Message& message,
                                 bool* message_was_ok) OVERRIDE {
    bool handled = true;
    IPC_BEGIN_MESSAGE_MAP_EX(ScheduledResourceRequest, message, *message_was_ok)
      IPC_MESSAGE_HANDLER(ResourceHostMsg_DidChangePriority, DidChangePriority)
      IPC_MESSAGE_UNHANDLED(handled = false)
    IPC_END_MESSAGE_MAP_EX()
    return handled;
  }

  // ResourceThrottle interface:
  virtual void WillStartRequest(bool* defer) OVERRIDE {
    deferred_ = *defer = !ready_;
  }

  virtual const char* GetNameForLogging() const OVERRIDE {
    return "ResourceScheduler";
  }

  void DidChangePriority(int request_id, net::RequestPriority new_priority) {
    scheduler_->ReprioritizeRequest(this, new_priority);
  }

  ClientId client_id_;
  net::URLRequest* request_;
  bool ready_;
  bool deferred_;
  ResourceScheduler* scheduler_;

  DISALLOW_COPY_AND_ASSIGN(ScheduledResourceRequest);
};

// Each client represents a tab.
struct ResourceScheduler::Client {
  Client() : has_body(false) {}
  ~Client() {}

  bool has_body;
  RequestQueue pending_requests;
  RequestSet in_flight_requests;
};

ResourceScheduler::ResourceScheduler() {
}

ResourceScheduler::~ResourceScheduler() {
  DCHECK(unowned_requests_.empty());
  DCHECK(client_map_.empty());
}

scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest(
    int child_id,
    int route_id,
    net::URLRequest* url_request) {
  DCHECK(CalledOnValidThread());
  ClientId client_id = MakeClientId(child_id, route_id);
  scoped_ptr<ScheduledResourceRequest> request(
      new ScheduledResourceRequest(client_id, url_request, this));

  ClientMap::iterator it = client_map_.find(client_id);
  if (it == client_map_.end()) {
    // There are several ways this could happen:
    // 1. <a ping> requests don't have a route_id.
    // 2. Most unittests don't send the IPCs needed to register Clients.
    // 3. The tab is closed while a RequestResource IPC is in flight.
    unowned_requests_.insert(request.get());
    request->Start();
    return request.PassAs<ResourceThrottle>();
  }

  Client* client = it->second;
  if (ShouldStartRequest(request.get(), client) == START_REQUEST) {
    StartRequest(request.get(), client);
  } else {
    client->pending_requests.Insert(request.get(), url_request->priority());
  }
  return request.PassAs<ResourceThrottle>();
}

void ResourceScheduler::RemoveRequest(ScheduledResourceRequest* request) {
  DCHECK(CalledOnValidThread());
  if (ContainsKey(unowned_requests_, request)) {
    unowned_requests_.erase(request);
    return;
  }

  ClientMap::iterator client_it = client_map_.find(request->client_id());
  if (client_it == client_map_.end()) {
    return;
  }

  Client* client = client_it->second;

  if (client->pending_requests.IsQueued(request)) {
    client->pending_requests.Erase(request);
    DCHECK(!ContainsKey(client->in_flight_requests, request));
  } else {
    size_t erased = client->in_flight_requests.erase(request);
    DCHECK(erased);

    // Removing this request may have freed up another to load.
    LoadAnyStartablePendingRequests(client);
  }
}

void ResourceScheduler::OnClientCreated(int child_id, int route_id) {
  DCHECK(CalledOnValidThread());
  ClientId client_id = MakeClientId(child_id, route_id);
  DCHECK(!ContainsKey(client_map_, client_id));

  client_map_[client_id] = new Client;
}

void ResourceScheduler::OnClientDeleted(int child_id, int route_id) {
  DCHECK(CalledOnValidThread());
  ClientId client_id = MakeClientId(child_id, route_id);
  DCHECK(ContainsKey(client_map_, client_id));
  ClientMap::iterator it = client_map_.find(client_id);
  if (it == client_map_.end())
    return;

  Client* client = it->second;

  // FYI, ResourceDispatcherHost cancels all of the requests after this function
  // is called. It should end up canceling all of the requests except for a
  // cross-renderer navigation.
  for (RequestSet::iterator it = client->in_flight_requests.begin();
       it != client->in_flight_requests.end(); ++it) {
    unowned_requests_.insert(*it);
  }
  client->in_flight_requests.clear();

  delete client;
  client_map_.erase(it);
}

void ResourceScheduler::OnNavigate(int child_id, int route_id) {
  DCHECK(CalledOnValidThread());
  ClientId client_id = MakeClientId(child_id, route_id);

  ClientMap::iterator it = client_map_.find(client_id);
  if (it == client_map_.end()) {
    // The client was likely deleted shortly before we received this IPC.
    return;
  }

  Client* client = it->second;
  client->has_body = false;
}

void ResourceScheduler::OnWillInsertBody(int child_id, int route_id) {
  DCHECK(CalledOnValidThread());
  ClientId client_id = MakeClientId(child_id, route_id);

  ClientMap::iterator it = client_map_.find(client_id);
  if (it == client_map_.end()) {
    // The client was likely deleted shortly before we received this IPC.
    return;
  }

  Client* client = it->second;
  client->has_body = false;
  if (!client->has_body) {
    client->has_body = true;
    LoadAnyStartablePendingRequests(client);
  }
}

void ResourceScheduler::StartRequest(ScheduledResourceRequest* request,
                                     Client* client) {
  client->in_flight_requests.insert(request);
  request->Start();
}

void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
                                            net::RequestPriority new_priority) {
  if (request->url_request()->load_flags() & net::LOAD_IGNORE_LIMITS) {
    // We should not be re-prioritizing requests with the
    // IGNORE_LIMITS flag.
    NOTREACHED();
    return;
  }
  net::RequestPriority old_priority = request->url_request()->priority();
  DCHECK_NE(new_priority, old_priority);
  request->url_request()->SetPriority(new_priority);
  ClientMap::iterator client_it = client_map_.find(request->client_id());
  if (client_it == client_map_.end()) {
    // The client was likely deleted shortly before we received this IPC.
    return;
  }

  Client *client = client_it->second;
  if (!client->pending_requests.IsQueued(request)) {
    DCHECK(ContainsKey(client->in_flight_requests, request));
    // Request has already started.
    return;
  }

  client->pending_requests.Erase(request);
  client->pending_requests.Insert(request,
                                  request->url_request()->priority());

  if (new_priority > old_priority) {
    // Check if this request is now able to load at its new priority.
    LoadAnyStartablePendingRequests(client);
  }
}

void ResourceScheduler::LoadAnyStartablePendingRequests(Client* client) {
  // We iterate through all the pending requests, starting with the highest
  // priority one. For each entry, one of three things can happen:
  // 1) We start the request, remove it from the list, and keep checking.
  // 2) We do NOT start the request, but ShouldStartRequest() signals us that
  //    there may be room for other requests, so we keep checking and leave
  //    the previous request still in the list.
  // 3) We do not start the request, same as above, but StartRequest() tells
  //    us there's no point in checking any further requests.

  RequestQueue::Iterator request_iter =
      client->pending_requests.GetNextHighestIterator();

  while (!request_iter.is_null()) {
    ScheduledResourceRequest* request = request_iter.value();
    ShouldStartReqResult query_result = ShouldStartRequest(request, client);

    if (query_result == START_REQUEST) {
      client->pending_requests.Erase(request);
      StartRequest(request, client);

      // StartRequest can modify the pending list, so we (re)start evaluation
      // from the currently highest priority request. Avoid copying a singular
      // iterator, which would trigger undefined behavior.
      if (client->pending_requests.GetNextHighestIterator().is_null())
        break;
      request_iter = client->pending_requests.GetNextHighestIterator();
    } else if (query_result == DO_NOT_START_REQUEST_AND_KEEP_SEARCHING) {
      ++request_iter;
      continue;
    } else {
      DCHECK(query_result == DO_NOT_START_REQUEST_AND_STOP_SEARCHING);
      break;
    }
  }
}

void ResourceScheduler::GetNumDelayableRequestsInFlight(
    Client* client,
    const net::HostPortPair& active_request_host,
    size_t* total_delayable,
    size_t* total_for_active_host) const {
  DCHECK(client != NULL && total_delayable != NULL &&
         total_for_active_host != NULL);

  size_t total_delayable_count = 0;
  size_t same_host_count = 0;
  for (RequestSet::iterator it = client->in_flight_requests.begin();
       it != client->in_flight_requests.end(); ++it) {
    net::HostPortPair host_port_pair =
        net::HostPortPair::FromURL((*it)->url_request()->url());

    if (active_request_host.Equals(host_port_pair)) {
      same_host_count++;
    }

    if ((*it)->url_request()->priority() < net::LOW) {
      const net::HttpServerProperties& http_server_properties =
          *(*it)->url_request()->context()->http_server_properties();

      if (!http_server_properties.SupportsSpdy(host_port_pair)) {
        ++total_delayable_count;
      }
    }
  }
  *total_delayable = total_delayable_count;
  *total_for_active_host = same_host_count;
}

// ShouldStartRequest is the main scheduling algorithm.
//
// Requests are categorized into two categories:
//
// 1. Immediately issued requests, which are:
//
//   * Higher priority requests (>= net::LOW).
//   * Synchronous requests.
//   * Requests to SPDY-capable origin servers.
//   * Non-HTTP[S] requests.
//
// 2. The remainder are delayable requests, which follow these rules:
//
//   * If no high priority requests are in flight, start loading low priority
//     requests.
//   * Once the renderer has a <body>, start loading delayable requests.
//   * Never exceed 10 delayable requests in flight per client.
//   * Never exceed 6 delayable requests for a given host.
//   * Prior to <body>, allow one delayable request to load at a time.
ResourceScheduler::ShouldStartReqResult ResourceScheduler::ShouldStartRequest(
    ScheduledResourceRequest* request,
    Client* client) const {
  const net::URLRequest& url_request = *request->url_request();

  // TODO(simonjam): This may end up causing disk contention. We should
  // experiment with throttling if that happens.
  if (!url_request.url().SchemeIsHTTPOrHTTPS()) {
    return START_REQUEST;
  }

  const net::HttpServerProperties& http_server_properties =
      *url_request.context()->http_server_properties();

  if (url_request.priority() >= net::LOW ||
      !ResourceRequestInfo::ForRequest(&url_request)->IsAsync()) {
    return START_REQUEST;
  }

  net::HostPortPair host_port_pair =
      net::HostPortPair::FromURL(url_request.url());

  // TODO(willchan): We should really improve this algorithm as described in
  // crbug.com/164101. Also, theoretically we should not count a SPDY request
  // against the delayable requests limit.
  if (http_server_properties.SupportsSpdy(host_port_pair)) {
    return START_REQUEST;
  }

  size_t num_delayable_requests_in_flight = 0;
  size_t num_requests_in_flight_for_host = 0;
  GetNumDelayableRequestsInFlight(client, host_port_pair,
                                  &num_delayable_requests_in_flight,
                                  &num_requests_in_flight_for_host);

  if (num_delayable_requests_in_flight >= kMaxNumDelayableRequestsPerClient) {
    return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
  }

  if (num_requests_in_flight_for_host >= kMaxNumDelayableRequestsPerHost) {
    // There may be other requests for other hosts we'd allow, so keep checking.
    return DO_NOT_START_REQUEST_AND_KEEP_SEARCHING;
  }

  bool have_immediate_requests_in_flight =
      client->in_flight_requests.size() > num_delayable_requests_in_flight;
  if (have_immediate_requests_in_flight && !client->has_body &&
      num_delayable_requests_in_flight != 0) {
    return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
  }

  return START_REQUEST;
}

ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
    int child_id, int route_id) {
  return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
}

}  // namespace content