12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef CHROME_BROWSER_EXTENSIONS_UPDATER_REQUEST_QUEUE_H_ 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define CHROME_BROWSER_EXTENSIONS_UPDATER_REQUEST_QUEUE_H_ 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <deque> 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <utility> 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/callback.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/memory/linked_ptr.h" 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/memory/scoped_ptr.h" 14eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "base/time/time.h" 15eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "base/timer/timer.h" 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "net/base/backoff_entry.h" 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace extensions { 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This class keeps track of a queue of requests, and contains the logic to 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// retry requests with some backoff policy. Each request has a 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// net::BackoffEntry instance associated with it. 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The general flow when using this class would be something like this: 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - requests are queued up by calling ScheduleRequest. 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - when a request is ready to be executed, RequestQueue removes the 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// request from the queue, assigns it as active request, and calls 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// the callback that was passed to the constructor. 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - (optionally) when a request has completed unsuccessfully call 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// RetryRequest to put the request back in the queue, using the 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// backoff policy and minimum backoff delay to determine when to 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// next schedule this request. 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - call reset_active_request() to indicate that the active request has 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// been dealt with. 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - call StartNextRequest to schedule the next pending request (if any). 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<typename T> 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class RequestQueue { 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) class iterator; 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RequestQueue(const net::BackoffEntry::Policy* backoff_policy, 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const base::Closure& start_request_callback); 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~RequestQueue(); 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the request that is currently being processed. 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* active_request(); 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the number of times the current request has been retried already. 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int active_request_failure_count(); 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Signals RequestQueue that processing of the current request has completed. 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<T> reset_active_request(); 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Add the given request to the queue, and starts the next request if no 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // request is currently being processed. 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void ScheduleRequest(scoped_ptr<T> request); 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool empty() const; 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t size() const; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the earliest release time of all requests currently in the queue. 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::TimeTicks NextReleaseTime() const; 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Starts the next request, if no request is currently active. This will 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // synchronously call the start_request_callback if the release time of the 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // earliest available request is in the past, otherwise it will call that 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // callback asynchronously after enough time has passed. 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void StartNextRequest(); 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Tell RequestQueue to put the current request back in the queue, after 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // applying the backoff policy to determine when to next try this request. 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If the policy results in a backoff delay smaller than |min_backoff_delay|, 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // that delay is used instead. 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void RetryRequest(const base::TimeDelta& min_backoff_delay); 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator begin(); 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator end(); 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Change the backoff policy used by the queue. 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void set_backoff_policy(const net::BackoffEntry::Policy* backoff_policy); 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) struct Request { 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Request(net::BackoffEntry* backoff_entry, T* request) 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : backoff_entry(backoff_entry), request(request) {} 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) linked_ptr<net::BackoffEntry> backoff_entry; 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) linked_ptr<T> request; 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) }; 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Compares the release time of two pending requests. 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static bool CompareRequests(const Request& a, 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const Request& b); 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Pushes a request with a given backoff entry onto the queue. 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void PushImpl(scoped_ptr<T> request, 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<net::BackoffEntry> backoff_entry); 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The backoff policy used to determine backoff delays. 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const net::BackoffEntry::Policy* backoff_policy_; 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Callback to call when a new request has become the active request. 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::Closure start_request_callback_; 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Priority queue of pending requests. Not using std::priority_queue since 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // the code needs to be able to iterate over all pending requests. 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::deque<Request> pending_requests_; 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Active request and its associated backoff entry. 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<T> active_request_; 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<net::BackoffEntry> active_backoff_entry_; 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Timer to schedule calls to StartNextRequest, if the first pending request 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // hasn't passed its release time yet. 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) base::Timer timer_; 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Iterator class that wraps a std::deque<> iterator, only giving access to the 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// actual request part of each item. 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<typename T> 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class RequestQueue<T>::iterator { 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator() {} 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* operator*() { return it_->request.get(); } 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* operator->() { return it_->request.get(); } 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator& operator++() { 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ++it_; 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return *this; 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool operator!=(const iterator& b) const { 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return it_ != b.it_; 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class RequestQueue<T>; 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::deque<typename RequestQueue<T>::Request> Container; 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) explicit iterator(const typename Container::iterator& it) 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : it_(it) {} 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename Container::iterator it_; 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace extensions 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // CHROME_BROWSER_EXTENSIONS_UPDATER_REQUEST_QUEUE_H_ 148