1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "net/http/http_cache.h"
6
7#include <algorithm>
8
9#include "base/compiler_specific.h"
10
11#if defined(OS_POSIX)
12#include <unistd.h>
13#endif
14
15#include "base/bind.h"
16#include "base/bind_helpers.h"
17#include "base/callback.h"
18#include "base/file_util.h"
19#include "base/format_macros.h"
20#include "base/location.h"
21#include "base/memory/ref_counted.h"
22#include "base/message_loop/message_loop.h"
23#include "base/metrics/field_trial.h"
24#include "base/pickle.h"
25#include "base/stl_util.h"
26#include "base/strings/string_number_conversions.h"
27#include "base/strings/string_util.h"
28#include "base/strings/stringprintf.h"
29#include "base/threading/worker_pool.h"
30#include "net/base/cache_type.h"
31#include "net/base/io_buffer.h"
32#include "net/base/load_flags.h"
33#include "net/base/net_errors.h"
34#include "net/base/upload_data_stream.h"
35#include "net/disk_cache/disk_cache.h"
36#include "net/http/http_cache_transaction.h"
37#include "net/http/http_network_layer.h"
38#include "net/http/http_network_session.h"
39#include "net/http/http_request_info.h"
40#include "net/http/http_response_headers.h"
41#include "net/http/http_response_info.h"
42#include "net/http/http_util.h"
43
44namespace {
45
46// Adaptor to delete a file on a worker thread.
47void DeletePath(base::FilePath path) {
48  base::DeleteFile(path, false);
49}
50
51}  // namespace
52
53namespace net {
54
55HttpCache::DefaultBackend::DefaultBackend(CacheType type,
56                                          BackendType backend_type,
57                                          const base::FilePath& path,
58                                          int max_bytes,
59                                          base::MessageLoopProxy* thread)
60    : type_(type),
61      backend_type_(backend_type),
62      path_(path),
63      max_bytes_(max_bytes),
64      thread_(thread) {
65}
66
67HttpCache::DefaultBackend::~DefaultBackend() {}
68
69// static
70HttpCache::BackendFactory* HttpCache::DefaultBackend::InMemory(int max_bytes) {
71  return new DefaultBackend(MEMORY_CACHE, net::CACHE_BACKEND_DEFAULT,
72                            base::FilePath(), max_bytes, NULL);
73}
74
75int HttpCache::DefaultBackend::CreateBackend(
76    NetLog* net_log, scoped_ptr<disk_cache::Backend>* backend,
77    const CompletionCallback& callback) {
78  DCHECK_GE(max_bytes_, 0);
79  return disk_cache::CreateCacheBackend(type_,
80                                        backend_type_,
81                                        path_,
82                                        max_bytes_,
83                                        true,
84                                        thread_.get(),
85                                        net_log,
86                                        backend,
87                                        callback);
88}
89
90//-----------------------------------------------------------------------------
91
92HttpCache::ActiveEntry::ActiveEntry(disk_cache::Entry* entry)
93    : disk_entry(entry),
94      writer(NULL),
95      will_process_pending_queue(false),
96      doomed(false) {
97}
98
99HttpCache::ActiveEntry::~ActiveEntry() {
100  if (disk_entry) {
101    disk_entry->Close();
102    disk_entry = NULL;
103  }
104}
105
106//-----------------------------------------------------------------------------
107
108// This structure keeps track of work items that are attempting to create or
109// open cache entries or the backend itself.
110struct HttpCache::PendingOp {
111  PendingOp() : disk_entry(NULL), writer(NULL) {}
112  ~PendingOp() {}
113
114  disk_cache::Entry* disk_entry;
115  scoped_ptr<disk_cache::Backend> backend;
116  WorkItem* writer;
117  CompletionCallback callback;  // BackendCallback.
118  WorkItemList pending_queue;
119};
120
121//-----------------------------------------------------------------------------
122
123// The type of operation represented by a work item.
124enum WorkItemOperation {
125  WI_CREATE_BACKEND,
126  WI_OPEN_ENTRY,
127  WI_CREATE_ENTRY,
128  WI_DOOM_ENTRY
129};
130
131// A work item encapsulates a single request to the backend with all the
132// information needed to complete that request.
133class HttpCache::WorkItem {
134 public:
135  WorkItem(WorkItemOperation operation, Transaction* trans, ActiveEntry** entry)
136      : operation_(operation),
137        trans_(trans),
138        entry_(entry),
139        backend_(NULL) {}
140  WorkItem(WorkItemOperation operation, Transaction* trans,
141           const net::CompletionCallback& cb, disk_cache::Backend** backend)
142      : operation_(operation),
143        trans_(trans),
144        entry_(NULL),
145        callback_(cb),
146        backend_(backend) {}
147  ~WorkItem() {}
148
149  // Calls back the transaction with the result of the operation.
150  void NotifyTransaction(int result, ActiveEntry* entry) {
151    DCHECK(!entry || entry->disk_entry);
152    if (entry_)
153      *entry_ = entry;
154    if (trans_)
155      trans_->io_callback().Run(result);
156  }
157
158  // Notifies the caller about the operation completion. Returns true if the
159  // callback was invoked.
160  bool DoCallback(int result, disk_cache::Backend* backend) {
161    if (backend_)
162      *backend_ = backend;
163    if (!callback_.is_null()) {
164      callback_.Run(result);
165      return true;
166    }
167    return false;
168  }
169
170  WorkItemOperation operation() { return operation_; }
171  void ClearTransaction() { trans_ = NULL; }
172  void ClearEntry() { entry_ = NULL; }
173  void ClearCallback() { callback_.Reset(); }
174  bool Matches(Transaction* trans) const { return trans == trans_; }
175  bool IsValid() const { return trans_ || entry_ || !callback_.is_null(); }
176
177 private:
178  WorkItemOperation operation_;
179  Transaction* trans_;
180  ActiveEntry** entry_;
181  net::CompletionCallback callback_;  // User callback.
182  disk_cache::Backend** backend_;
183};
184
185//-----------------------------------------------------------------------------
186
187// This class encapsulates a transaction whose only purpose is to write metadata
188// to a given entry.
189class HttpCache::MetadataWriter {
190 public:
191  explicit MetadataWriter(HttpCache::Transaction* trans)
192      : transaction_(trans),
193        verified_(false),
194        buf_len_(0) {
195  }
196
197  ~MetadataWriter() {}
198
199  // Implements the bulk of HttpCache::WriteMetadata.
200  void Write(const GURL& url, base::Time expected_response_time, IOBuffer* buf,
201             int buf_len);
202
203 private:
204  void VerifyResponse(int result);
205  void SelfDestroy();
206  void OnIOComplete(int result);
207
208  scoped_ptr<HttpCache::Transaction> transaction_;
209  bool verified_;
210  scoped_refptr<IOBuffer> buf_;
211  int buf_len_;
212  base::Time expected_response_time_;
213  HttpRequestInfo request_info_;
214  DISALLOW_COPY_AND_ASSIGN(MetadataWriter);
215};
216
217void HttpCache::MetadataWriter::Write(const GURL& url,
218                                      base::Time expected_response_time,
219                                      IOBuffer* buf, int buf_len) {
220  DCHECK_GT(buf_len, 0);
221  DCHECK(buf);
222  DCHECK(buf->data());
223  request_info_.url = url;
224  request_info_.method = "GET";
225  request_info_.load_flags = LOAD_ONLY_FROM_CACHE;
226
227  expected_response_time_ = expected_response_time;
228  buf_ = buf;
229  buf_len_ = buf_len;
230  verified_ = false;
231
232  int rv = transaction_->Start(
233      &request_info_,
234      base::Bind(&MetadataWriter::OnIOComplete, base::Unretained(this)),
235      BoundNetLog());
236  if (rv != ERR_IO_PENDING)
237    VerifyResponse(rv);
238}
239
240void HttpCache::MetadataWriter::VerifyResponse(int result) {
241  verified_ = true;
242  if (result != OK)
243    return SelfDestroy();
244
245  const HttpResponseInfo* response_info = transaction_->GetResponseInfo();
246  DCHECK(response_info->was_cached);
247  if (response_info->response_time != expected_response_time_)
248    return SelfDestroy();
249
250  result = transaction_->WriteMetadata(
251      buf_.get(),
252      buf_len_,
253      base::Bind(&MetadataWriter::OnIOComplete, base::Unretained(this)));
254  if (result != ERR_IO_PENDING)
255    SelfDestroy();
256}
257
258void HttpCache::MetadataWriter::SelfDestroy() {
259  delete this;
260}
261
262void HttpCache::MetadataWriter::OnIOComplete(int result) {
263  if (!verified_)
264    return VerifyResponse(result);
265  SelfDestroy();
266}
267
268//-----------------------------------------------------------------------------
269
270HttpCache::HttpCache(const net::HttpNetworkSession::Params& params,
271                     BackendFactory* backend_factory)
272    : net_log_(params.net_log),
273      backend_factory_(backend_factory),
274      building_backend_(false),
275      mode_(NORMAL),
276      network_layer_(new HttpNetworkLayer(new HttpNetworkSession(params))) {
277}
278
279
280HttpCache::HttpCache(HttpNetworkSession* session,
281                     BackendFactory* backend_factory)
282    : net_log_(session->net_log()),
283      backend_factory_(backend_factory),
284      building_backend_(false),
285      mode_(NORMAL),
286      network_layer_(new HttpNetworkLayer(session)) {
287}
288
289HttpCache::HttpCache(HttpTransactionFactory* network_layer,
290                     NetLog* net_log,
291                     BackendFactory* backend_factory)
292    : net_log_(net_log),
293      backend_factory_(backend_factory),
294      building_backend_(false),
295      mode_(NORMAL),
296      network_layer_(network_layer) {
297}
298
299HttpCache::~HttpCache() {
300  // If we have any active entries remaining, then we need to deactivate them.
301  // We may have some pending calls to OnProcessPendingQueue, but since those
302  // won't run (due to our destruction), we can simply ignore the corresponding
303  // will_process_pending_queue flag.
304  while (!active_entries_.empty()) {
305    ActiveEntry* entry = active_entries_.begin()->second;
306    entry->will_process_pending_queue = false;
307    entry->pending_queue.clear();
308    entry->readers.clear();
309    entry->writer = NULL;
310    DeactivateEntry(entry);
311  }
312
313  STLDeleteElements(&doomed_entries_);
314
315  // Before deleting pending_ops_, we have to make sure that the disk cache is
316  // done with said operations, or it will attempt to use deleted data.
317  disk_cache_.reset();
318
319  PendingOpsMap::iterator pending_it = pending_ops_.begin();
320  for (; pending_it != pending_ops_.end(); ++pending_it) {
321    // We are not notifying the transactions about the cache going away, even
322    // though they are waiting for a callback that will never fire.
323    PendingOp* pending_op = pending_it->second;
324    delete pending_op->writer;
325    bool delete_pending_op = true;
326    if (building_backend_) {
327      // If we don't have a backend, when its construction finishes it will
328      // deliver the callbacks.
329      if (!pending_op->callback.is_null()) {
330        // If not null, the callback will delete the pending operation later.
331        delete_pending_op = false;
332      }
333    } else {
334      pending_op->callback.Reset();
335    }
336
337    STLDeleteElements(&pending_op->pending_queue);
338    if (delete_pending_op)
339      delete pending_op;
340  }
341}
342
343int HttpCache::GetBackend(disk_cache::Backend** backend,
344                          const CompletionCallback& callback) {
345  DCHECK(!callback.is_null());
346
347  if (disk_cache_.get()) {
348    *backend = disk_cache_.get();
349    return OK;
350  }
351
352  return CreateBackend(backend, callback);
353}
354
355disk_cache::Backend* HttpCache::GetCurrentBackend() const {
356  return disk_cache_.get();
357}
358
359// static
360bool HttpCache::ParseResponseInfo(const char* data, int len,
361                                  HttpResponseInfo* response_info,
362                                  bool* response_truncated) {
363  Pickle pickle(data, len);
364  return response_info->InitFromPickle(pickle, response_truncated);
365}
366
367void HttpCache::WriteMetadata(const GURL& url,
368                              RequestPriority priority,
369                              base::Time expected_response_time,
370                              IOBuffer* buf,
371                              int buf_len) {
372  if (!buf_len)
373    return;
374
375  // Do lazy initialization of disk cache if needed.
376  if (!disk_cache_.get()) {
377    // We don't care about the result.
378    CreateBackend(NULL, net::CompletionCallback());
379  }
380
381  HttpCache::Transaction* trans =
382      new HttpCache::Transaction(priority, this, NULL);
383  MetadataWriter* writer = new MetadataWriter(trans);
384
385  // The writer will self destruct when done.
386  writer->Write(url, expected_response_time, buf, buf_len);
387}
388
389void HttpCache::CloseAllConnections() {
390  net::HttpNetworkLayer* network =
391      static_cast<net::HttpNetworkLayer*>(network_layer_.get());
392  HttpNetworkSession* session = network->GetSession();
393  if (session)
394    session->CloseAllConnections();
395  }
396
397void HttpCache::CloseIdleConnections() {
398  net::HttpNetworkLayer* network =
399      static_cast<net::HttpNetworkLayer*>(network_layer_.get());
400  HttpNetworkSession* session = network->GetSession();
401  if (session)
402    session->CloseIdleConnections();
403}
404
405void HttpCache::OnExternalCacheHit(const GURL& url,
406                                   const std::string& http_method) {
407  if (!disk_cache_.get())
408    return;
409
410  HttpRequestInfo request_info;
411  request_info.url = url;
412  request_info.method = http_method;
413  std::string key = GenerateCacheKey(&request_info);
414  disk_cache_->OnExternalCacheHit(key);
415}
416
417void HttpCache::InitializeInfiniteCache(const base::FilePath& path) {
418  if (base::FieldTrialList::FindFullName("InfiniteCache") != "Yes")
419    return;
420  base::WorkerPool::PostTask(FROM_HERE, base::Bind(&DeletePath, path), true);
421}
422
423int HttpCache::CreateTransaction(RequestPriority priority,
424                                 scoped_ptr<HttpTransaction>* trans,
425                                 HttpTransactionDelegate* delegate) {
426  // Do lazy initialization of disk cache if needed.
427  if (!disk_cache_.get()) {
428    // We don't care about the result.
429    CreateBackend(NULL, net::CompletionCallback());
430  }
431
432  trans->reset(new HttpCache::Transaction(priority, this, delegate));
433  return OK;
434}
435
436HttpCache* HttpCache::GetCache() {
437  return this;
438}
439
440HttpNetworkSession* HttpCache::GetSession() {
441  net::HttpNetworkLayer* network =
442      static_cast<net::HttpNetworkLayer*>(network_layer_.get());
443  return network->GetSession();
444}
445
446//-----------------------------------------------------------------------------
447
448int HttpCache::CreateBackend(disk_cache::Backend** backend,
449                             const net::CompletionCallback& callback) {
450  if (!backend_factory_.get())
451    return ERR_FAILED;
452
453  building_backend_ = true;
454
455  scoped_ptr<WorkItem> item(new WorkItem(WI_CREATE_BACKEND, NULL, callback,
456                                         backend));
457
458  // This is the only operation that we can do that is not related to any given
459  // entry, so we use an empty key for it.
460  PendingOp* pending_op = GetPendingOp(std::string());
461  if (pending_op->writer) {
462    if (!callback.is_null())
463      pending_op->pending_queue.push_back(item.release());
464    return ERR_IO_PENDING;
465  }
466
467  DCHECK(pending_op->pending_queue.empty());
468
469  pending_op->writer = item.release();
470  pending_op->callback = base::Bind(&HttpCache::OnPendingOpComplete,
471                                    AsWeakPtr(), pending_op);
472
473  int rv = backend_factory_->CreateBackend(net_log_, &pending_op->backend,
474                                           pending_op->callback);
475  if (rv != ERR_IO_PENDING) {
476    pending_op->writer->ClearCallback();
477    pending_op->callback.Run(rv);
478  }
479
480  return rv;
481}
482
483int HttpCache::GetBackendForTransaction(Transaction* trans) {
484  if (disk_cache_.get())
485    return OK;
486
487  if (!building_backend_)
488    return ERR_FAILED;
489
490  WorkItem* item = new WorkItem(
491      WI_CREATE_BACKEND, trans, net::CompletionCallback(), NULL);
492  PendingOp* pending_op = GetPendingOp(std::string());
493  DCHECK(pending_op->writer);
494  pending_op->pending_queue.push_back(item);
495  return ERR_IO_PENDING;
496}
497
498// Generate a key that can be used inside the cache.
499std::string HttpCache::GenerateCacheKey(const HttpRequestInfo* request) {
500  // Strip out the reference, username, and password sections of the URL.
501  std::string url = HttpUtil::SpecForRequest(request->url);
502
503  DCHECK(mode_ != DISABLE);
504  if (mode_ == NORMAL) {
505    // No valid URL can begin with numerals, so we should not have to worry
506    // about collisions with normal URLs.
507    if (request->upload_data_stream &&
508        request->upload_data_stream->identifier()) {
509      url.insert(0, base::StringPrintf(
510          "%" PRId64 "/", request->upload_data_stream->identifier()));
511    }
512    return url;
513  }
514
515  // In playback and record mode, we cache everything.
516
517  // Lazily initialize.
518  if (playback_cache_map_ == NULL)
519    playback_cache_map_.reset(new PlaybackCacheMap());
520
521  // Each time we request an item from the cache, we tag it with a
522  // generation number.  During playback, multiple fetches for the same
523  // item will use the same generation number and pull the proper
524  // instance of an URL from the cache.
525  int generation = 0;
526  DCHECK(playback_cache_map_ != NULL);
527  if (playback_cache_map_->find(url) != playback_cache_map_->end())
528    generation = (*playback_cache_map_)[url];
529  (*playback_cache_map_)[url] = generation + 1;
530
531  // The key into the cache is GENERATION # + METHOD + URL.
532  std::string result = base::IntToString(generation);
533  result.append(request->method);
534  result.append(url);
535  return result;
536}
537
538void HttpCache::DoomActiveEntry(const std::string& key) {
539  ActiveEntriesMap::iterator it = active_entries_.find(key);
540  if (it == active_entries_.end())
541    return;
542
543  // This is not a performance critical operation, this is handling an error
544  // condition so it is OK to look up the entry again.
545  int rv = DoomEntry(key, NULL);
546  DCHECK_EQ(OK, rv);
547}
548
549int HttpCache::DoomEntry(const std::string& key, Transaction* trans) {
550  // Need to abandon the ActiveEntry, but any transaction attached to the entry
551  // should not be impacted.  Dooming an entry only means that it will no
552  // longer be returned by FindActiveEntry (and it will also be destroyed once
553  // all consumers are finished with the entry).
554  ActiveEntriesMap::iterator it = active_entries_.find(key);
555  if (it == active_entries_.end()) {
556    DCHECK(trans);
557    return AsyncDoomEntry(key, trans);
558  }
559
560  ActiveEntry* entry = it->second;
561  active_entries_.erase(it);
562
563  // We keep track of doomed entries so that we can ensure that they are
564  // cleaned up properly when the cache is destroyed.
565  doomed_entries_.insert(entry);
566
567  entry->disk_entry->Doom();
568  entry->doomed = true;
569
570  DCHECK(entry->writer || !entry->readers.empty());
571  return OK;
572}
573
574int HttpCache::AsyncDoomEntry(const std::string& key, Transaction* trans) {
575  WorkItem* item = new WorkItem(WI_DOOM_ENTRY, trans, NULL);
576  PendingOp* pending_op = GetPendingOp(key);
577  if (pending_op->writer) {
578    pending_op->pending_queue.push_back(item);
579    return ERR_IO_PENDING;
580  }
581
582  DCHECK(pending_op->pending_queue.empty());
583
584  pending_op->writer = item;
585  pending_op->callback = base::Bind(&HttpCache::OnPendingOpComplete,
586                                    AsWeakPtr(), pending_op);
587
588  int rv = disk_cache_->DoomEntry(key, pending_op->callback);
589  if (rv != ERR_IO_PENDING) {
590    item->ClearTransaction();
591    pending_op->callback.Run(rv);
592  }
593
594  return rv;
595}
596
597void HttpCache::DoomMainEntryForUrl(const GURL& url) {
598  HttpRequestInfo temp_info;
599  temp_info.url = url;
600  temp_info.method = "GET";
601  std::string key = GenerateCacheKey(&temp_info);
602
603  // Defer to DoomEntry if there is an active entry, otherwise call
604  // AsyncDoomEntry without triggering a callback.
605  if (active_entries_.count(key))
606    DoomEntry(key, NULL);
607  else
608    AsyncDoomEntry(key, NULL);
609}
610
611void HttpCache::FinalizeDoomedEntry(ActiveEntry* entry) {
612  DCHECK(entry->doomed);
613  DCHECK(!entry->writer);
614  DCHECK(entry->readers.empty());
615  DCHECK(entry->pending_queue.empty());
616
617  ActiveEntriesSet::iterator it = doomed_entries_.find(entry);
618  DCHECK(it != doomed_entries_.end());
619  doomed_entries_.erase(it);
620
621  delete entry;
622}
623
624HttpCache::ActiveEntry* HttpCache::FindActiveEntry(const std::string& key) {
625  ActiveEntriesMap::const_iterator it = active_entries_.find(key);
626  return it != active_entries_.end() ? it->second : NULL;
627}
628
629HttpCache::ActiveEntry* HttpCache::ActivateEntry(
630    disk_cache::Entry* disk_entry) {
631  DCHECK(!FindActiveEntry(disk_entry->GetKey()));
632  ActiveEntry* entry = new ActiveEntry(disk_entry);
633  active_entries_[disk_entry->GetKey()] = entry;
634  return entry;
635}
636
637void HttpCache::DeactivateEntry(ActiveEntry* entry) {
638  DCHECK(!entry->will_process_pending_queue);
639  DCHECK(!entry->doomed);
640  DCHECK(!entry->writer);
641  DCHECK(entry->disk_entry);
642  DCHECK(entry->readers.empty());
643  DCHECK(entry->pending_queue.empty());
644
645  std::string key = entry->disk_entry->GetKey();
646  if (key.empty())
647    return SlowDeactivateEntry(entry);
648
649  ActiveEntriesMap::iterator it = active_entries_.find(key);
650  DCHECK(it != active_entries_.end());
651  DCHECK(it->second == entry);
652
653  active_entries_.erase(it);
654  delete entry;
655}
656
657// We don't know this entry's key so we have to find it without it.
658void HttpCache::SlowDeactivateEntry(ActiveEntry* entry) {
659  for (ActiveEntriesMap::iterator it = active_entries_.begin();
660       it != active_entries_.end(); ++it) {
661    if (it->second == entry) {
662      active_entries_.erase(it);
663      delete entry;
664      break;
665    }
666  }
667}
668
669HttpCache::PendingOp* HttpCache::GetPendingOp(const std::string& key) {
670  DCHECK(!FindActiveEntry(key));
671
672  PendingOpsMap::const_iterator it = pending_ops_.find(key);
673  if (it != pending_ops_.end())
674    return it->second;
675
676  PendingOp* operation = new PendingOp();
677  pending_ops_[key] = operation;
678  return operation;
679}
680
681void HttpCache::DeletePendingOp(PendingOp* pending_op) {
682  std::string key;
683  if (pending_op->disk_entry)
684    key = pending_op->disk_entry->GetKey();
685
686  if (!key.empty()) {
687    PendingOpsMap::iterator it = pending_ops_.find(key);
688    DCHECK(it != pending_ops_.end());
689    pending_ops_.erase(it);
690  } else {
691    for (PendingOpsMap::iterator it = pending_ops_.begin();
692         it != pending_ops_.end(); ++it) {
693      if (it->second == pending_op) {
694        pending_ops_.erase(it);
695        break;
696      }
697    }
698  }
699  DCHECK(pending_op->pending_queue.empty());
700
701  delete pending_op;
702}
703
704int HttpCache::OpenEntry(const std::string& key, ActiveEntry** entry,
705                         Transaction* trans) {
706  ActiveEntry* active_entry = FindActiveEntry(key);
707  if (active_entry) {
708    *entry = active_entry;
709    return OK;
710  }
711
712  WorkItem* item = new WorkItem(WI_OPEN_ENTRY, trans, entry);
713  PendingOp* pending_op = GetPendingOp(key);
714  if (pending_op->writer) {
715    pending_op->pending_queue.push_back(item);
716    return ERR_IO_PENDING;
717  }
718
719  DCHECK(pending_op->pending_queue.empty());
720
721  pending_op->writer = item;
722  pending_op->callback = base::Bind(&HttpCache::OnPendingOpComplete,
723                                    AsWeakPtr(), pending_op);
724
725  int rv = disk_cache_->OpenEntry(key, &(pending_op->disk_entry),
726                                  pending_op->callback);
727  if (rv != ERR_IO_PENDING) {
728    item->ClearTransaction();
729    pending_op->callback.Run(rv);
730  }
731
732  return rv;
733}
734
735int HttpCache::CreateEntry(const std::string& key, ActiveEntry** entry,
736                           Transaction* trans) {
737  if (FindActiveEntry(key)) {
738    return ERR_CACHE_RACE;
739  }
740
741  WorkItem* item = new WorkItem(WI_CREATE_ENTRY, trans, entry);
742  PendingOp* pending_op = GetPendingOp(key);
743  if (pending_op->writer) {
744    pending_op->pending_queue.push_back(item);
745    return ERR_IO_PENDING;
746  }
747
748  DCHECK(pending_op->pending_queue.empty());
749
750  pending_op->writer = item;
751  pending_op->callback = base::Bind(&HttpCache::OnPendingOpComplete,
752                                    AsWeakPtr(), pending_op);
753
754  int rv = disk_cache_->CreateEntry(key, &(pending_op->disk_entry),
755                                    pending_op->callback);
756  if (rv != ERR_IO_PENDING) {
757    item->ClearTransaction();
758    pending_op->callback.Run(rv);
759  }
760
761  return rv;
762}
763
764void HttpCache::DestroyEntry(ActiveEntry* entry) {
765  if (entry->doomed) {
766    FinalizeDoomedEntry(entry);
767  } else {
768    DeactivateEntry(entry);
769  }
770}
771
772int HttpCache::AddTransactionToEntry(ActiveEntry* entry, Transaction* trans) {
773  DCHECK(entry);
774  DCHECK(entry->disk_entry);
775
776  // We implement a basic reader/writer lock for the disk cache entry.  If
777  // there is already a writer, then everyone has to wait for the writer to
778  // finish before they can access the cache entry.  There can be multiple
779  // readers.
780  //
781  // NOTE: If the transaction can only write, then the entry should not be in
782  // use (since any existing entry should have already been doomed).
783
784  if (entry->writer || entry->will_process_pending_queue) {
785    entry->pending_queue.push_back(trans);
786    return ERR_IO_PENDING;
787  }
788
789  if (trans->mode() & Transaction::WRITE) {
790    // transaction needs exclusive access to the entry
791    if (entry->readers.empty()) {
792      entry->writer = trans;
793    } else {
794      entry->pending_queue.push_back(trans);
795      return ERR_IO_PENDING;
796    }
797  } else {
798    // transaction needs read access to the entry
799    entry->readers.push_back(trans);
800  }
801
802  // We do this before calling EntryAvailable to force any further calls to
803  // AddTransactionToEntry to add their transaction to the pending queue, which
804  // ensures FIFO ordering.
805  if (!entry->writer && !entry->pending_queue.empty())
806    ProcessPendingQueue(entry);
807
808  return OK;
809}
810
811void HttpCache::DoneWithEntry(ActiveEntry* entry, Transaction* trans,
812                              bool cancel) {
813  // If we already posted a task to move on to the next transaction and this was
814  // the writer, there is nothing to cancel.
815  if (entry->will_process_pending_queue && entry->readers.empty())
816    return;
817
818  if (entry->writer) {
819    DCHECK(trans == entry->writer);
820
821    // Assume there was a failure.
822    bool success = false;
823    if (cancel) {
824      DCHECK(entry->disk_entry);
825      // This is a successful operation in the sense that we want to keep the
826      // entry.
827      success = trans->AddTruncatedFlag();
828      // The previous operation may have deleted the entry.
829      if (!trans->entry())
830        return;
831    }
832    DoneWritingToEntry(entry, success);
833  } else {
834    DoneReadingFromEntry(entry, trans);
835  }
836}
837
838void HttpCache::DoneWritingToEntry(ActiveEntry* entry, bool success) {
839  DCHECK(entry->readers.empty());
840
841  entry->writer = NULL;
842
843  if (success) {
844    ProcessPendingQueue(entry);
845  } else {
846    DCHECK(!entry->will_process_pending_queue);
847
848    // We failed to create this entry.
849    TransactionList pending_queue;
850    pending_queue.swap(entry->pending_queue);
851
852    entry->disk_entry->Doom();
853    DestroyEntry(entry);
854
855    // We need to do something about these pending entries, which now need to
856    // be added to a new entry.
857    while (!pending_queue.empty()) {
858      // ERR_CACHE_RACE causes the transaction to restart the whole process.
859      pending_queue.front()->io_callback().Run(ERR_CACHE_RACE);
860      pending_queue.pop_front();
861    }
862  }
863}
864
865void HttpCache::DoneReadingFromEntry(ActiveEntry* entry, Transaction* trans) {
866  DCHECK(!entry->writer);
867
868  TransactionList::iterator it =
869      std::find(entry->readers.begin(), entry->readers.end(), trans);
870  DCHECK(it != entry->readers.end());
871
872  entry->readers.erase(it);
873
874  ProcessPendingQueue(entry);
875}
876
877void HttpCache::ConvertWriterToReader(ActiveEntry* entry) {
878  DCHECK(entry->writer);
879  DCHECK(entry->writer->mode() == Transaction::READ_WRITE);
880  DCHECK(entry->readers.empty());
881
882  Transaction* trans = entry->writer;
883
884  entry->writer = NULL;
885  entry->readers.push_back(trans);
886
887  ProcessPendingQueue(entry);
888}
889
890LoadState HttpCache::GetLoadStateForPendingTransaction(
891      const Transaction* trans) {
892  ActiveEntriesMap::const_iterator i = active_entries_.find(trans->key());
893  if (i == active_entries_.end()) {
894    // If this is really a pending transaction, and it is not part of
895    // active_entries_, we should be creating the backend or the entry.
896    return LOAD_STATE_WAITING_FOR_CACHE;
897  }
898
899  Transaction* writer = i->second->writer;
900  return writer ? writer->GetWriterLoadState() : LOAD_STATE_WAITING_FOR_CACHE;
901}
902
903void HttpCache::RemovePendingTransaction(Transaction* trans) {
904  ActiveEntriesMap::const_iterator i = active_entries_.find(trans->key());
905  bool found = false;
906  if (i != active_entries_.end())
907    found = RemovePendingTransactionFromEntry(i->second, trans);
908
909  if (found)
910    return;
911
912  if (building_backend_) {
913    PendingOpsMap::const_iterator j = pending_ops_.find(std::string());
914    if (j != pending_ops_.end())
915      found = RemovePendingTransactionFromPendingOp(j->second, trans);
916
917    if (found)
918      return;
919  }
920
921  PendingOpsMap::const_iterator j = pending_ops_.find(trans->key());
922  if (j != pending_ops_.end())
923    found = RemovePendingTransactionFromPendingOp(j->second, trans);
924
925  if (found)
926    return;
927
928  ActiveEntriesSet::iterator k = doomed_entries_.begin();
929  for (; k != doomed_entries_.end() && !found; ++k)
930    found = RemovePendingTransactionFromEntry(*k, trans);
931
932  DCHECK(found) << "Pending transaction not found";
933}
934
935bool HttpCache::RemovePendingTransactionFromEntry(ActiveEntry* entry,
936                                                  Transaction* trans) {
937  TransactionList& pending_queue = entry->pending_queue;
938
939  TransactionList::iterator j =
940      find(pending_queue.begin(), pending_queue.end(), trans);
941  if (j == pending_queue.end())
942    return false;
943
944  pending_queue.erase(j);
945  return true;
946}
947
948bool HttpCache::RemovePendingTransactionFromPendingOp(PendingOp* pending_op,
949                                                      Transaction* trans) {
950  if (pending_op->writer->Matches(trans)) {
951    pending_op->writer->ClearTransaction();
952    pending_op->writer->ClearEntry();
953    return true;
954  }
955  WorkItemList& pending_queue = pending_op->pending_queue;
956
957  WorkItemList::iterator it = pending_queue.begin();
958  for (; it != pending_queue.end(); ++it) {
959    if ((*it)->Matches(trans)) {
960      delete *it;
961      pending_queue.erase(it);
962      return true;
963    }
964  }
965  return false;
966}
967
968void HttpCache::ProcessPendingQueue(ActiveEntry* entry) {
969  // Multiple readers may finish with an entry at once, so we want to batch up
970  // calls to OnProcessPendingQueue.  This flag also tells us that we should
971  // not delete the entry before OnProcessPendingQueue runs.
972  if (entry->will_process_pending_queue)
973    return;
974  entry->will_process_pending_queue = true;
975
976  base::MessageLoop::current()->PostTask(
977      FROM_HERE,
978      base::Bind(&HttpCache::OnProcessPendingQueue, AsWeakPtr(), entry));
979}
980
981void HttpCache::OnProcessPendingQueue(ActiveEntry* entry) {
982  entry->will_process_pending_queue = false;
983  DCHECK(!entry->writer);
984
985  // If no one is interested in this entry, then we can deactivate it.
986  if (entry->pending_queue.empty()) {
987    if (entry->readers.empty())
988      DestroyEntry(entry);
989    return;
990  }
991
992  // Promote next transaction from the pending queue.
993  Transaction* next = entry->pending_queue.front();
994  if ((next->mode() & Transaction::WRITE) && !entry->readers.empty())
995    return;  // Have to wait.
996
997  entry->pending_queue.erase(entry->pending_queue.begin());
998
999  int rv = AddTransactionToEntry(entry, next);
1000  if (rv != ERR_IO_PENDING) {
1001    next->io_callback().Run(rv);
1002  }
1003}
1004
1005void HttpCache::OnIOComplete(int result, PendingOp* pending_op) {
1006  WorkItemOperation op = pending_op->writer->operation();
1007
1008  // Completing the creation of the backend is simpler than the other cases.
1009  if (op == WI_CREATE_BACKEND)
1010    return OnBackendCreated(result, pending_op);
1011
1012  scoped_ptr<WorkItem> item(pending_op->writer);
1013  bool fail_requests = false;
1014
1015  ActiveEntry* entry = NULL;
1016  std::string key;
1017  if (result == OK) {
1018    if (op == WI_DOOM_ENTRY) {
1019      // Anything after a Doom has to be restarted.
1020      fail_requests = true;
1021    } else if (item->IsValid()) {
1022      key = pending_op->disk_entry->GetKey();
1023      entry = ActivateEntry(pending_op->disk_entry);
1024    } else {
1025      // The writer transaction is gone.
1026      if (op == WI_CREATE_ENTRY)
1027        pending_op->disk_entry->Doom();
1028      pending_op->disk_entry->Close();
1029      pending_op->disk_entry = NULL;
1030      fail_requests = true;
1031    }
1032  }
1033
1034  // We are about to notify a bunch of transactions, and they may decide to
1035  // re-issue a request (or send a different one). If we don't delete
1036  // pending_op, the new request will be appended to the end of the list, and
1037  // we'll see it again from this point before it has a chance to complete (and
1038  // we'll be messing out the request order). The down side is that if for some
1039  // reason notifying request A ends up cancelling request B (for the same key),
1040  // we won't find request B anywhere (because it would be in a local variable
1041  // here) and that's bad. If there is a chance for that to happen, we'll have
1042  // to move the callback used to be a CancelableCallback. By the way, for this
1043  // to happen the action (to cancel B) has to be synchronous to the
1044  // notification for request A.
1045  WorkItemList pending_items;
1046  pending_items.swap(pending_op->pending_queue);
1047  DeletePendingOp(pending_op);
1048
1049  item->NotifyTransaction(result, entry);
1050
1051  while (!pending_items.empty()) {
1052    item.reset(pending_items.front());
1053    pending_items.pop_front();
1054
1055    if (item->operation() == WI_DOOM_ENTRY) {
1056      // A queued doom request is always a race.
1057      fail_requests = true;
1058    } else if (result == OK) {
1059      entry = FindActiveEntry(key);
1060      if (!entry)
1061        fail_requests = true;
1062    }
1063
1064    if (fail_requests) {
1065      item->NotifyTransaction(ERR_CACHE_RACE, NULL);
1066      continue;
1067    }
1068
1069    if (item->operation() == WI_CREATE_ENTRY) {
1070      if (result == OK) {
1071        // A second Create request, but the first request succeeded.
1072        item->NotifyTransaction(ERR_CACHE_CREATE_FAILURE, NULL);
1073      } else {
1074        if (op != WI_CREATE_ENTRY) {
1075          // Failed Open followed by a Create.
1076          item->NotifyTransaction(ERR_CACHE_RACE, NULL);
1077          fail_requests = true;
1078        } else {
1079          item->NotifyTransaction(result, entry);
1080        }
1081      }
1082    } else {
1083      if (op == WI_CREATE_ENTRY && result != OK) {
1084        // Failed Create followed by an Open.
1085        item->NotifyTransaction(ERR_CACHE_RACE, NULL);
1086        fail_requests = true;
1087      } else {
1088        item->NotifyTransaction(result, entry);
1089      }
1090    }
1091  }
1092}
1093
1094// static
1095void HttpCache::OnPendingOpComplete(const base::WeakPtr<HttpCache>& cache,
1096                                    PendingOp* pending_op,
1097                                    int rv) {
1098  if (cache.get()) {
1099    cache->OnIOComplete(rv, pending_op);
1100  } else {
1101    // The callback was cancelled so we should delete the pending_op that
1102    // was used with this callback.
1103    delete pending_op;
1104  }
1105}
1106
1107void HttpCache::OnBackendCreated(int result, PendingOp* pending_op) {
1108  scoped_ptr<WorkItem> item(pending_op->writer);
1109  WorkItemOperation op = item->operation();
1110  DCHECK_EQ(WI_CREATE_BACKEND, op);
1111
1112  // We don't need the callback anymore.
1113  pending_op->callback.Reset();
1114
1115  if (backend_factory_.get()) {
1116    // We may end up calling OnBackendCreated multiple times if we have pending
1117    // work items. The first call saves the backend and releases the factory,
1118    // and the last call clears building_backend_.
1119    backend_factory_.reset();  // Reclaim memory.
1120    if (result == OK)
1121      disk_cache_ = pending_op->backend.Pass();
1122  }
1123
1124  if (!pending_op->pending_queue.empty()) {
1125    WorkItem* pending_item = pending_op->pending_queue.front();
1126    pending_op->pending_queue.pop_front();
1127    DCHECK_EQ(WI_CREATE_BACKEND, pending_item->operation());
1128
1129    // We want to process a single callback at a time, because the cache may
1130    // go away from the callback.
1131    pending_op->writer = pending_item;
1132
1133    base::MessageLoop::current()->PostTask(
1134        FROM_HERE,
1135        base::Bind(
1136            &HttpCache::OnBackendCreated, AsWeakPtr(), result, pending_op));
1137  } else {
1138    building_backend_ = false;
1139    DeletePendingOp(pending_op);
1140  }
1141
1142  // The cache may be gone when we return from the callback.
1143  if (!item->DoCallback(result, disk_cache_.get()))
1144    item->NotifyTransaction(result, NULL);
1145}
1146
1147}  // namespace net
1148