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/disk_cache/sparse_control.h"
6
7#include "base/bind.h"
8#include "base/format_macros.h"
9#include "base/logging.h"
10#include "base/message_loop/message_loop.h"
11#include "base/strings/string_util.h"
12#include "base/strings/stringprintf.h"
13#include "base/time/time.h"
14#include "net/base/io_buffer.h"
15#include "net/base/net_errors.h"
16#include "net/disk_cache/backend_impl.h"
17#include "net/disk_cache/entry_impl.h"
18#include "net/disk_cache/file.h"
19#include "net/disk_cache/net_log_parameters.h"
20
21using base::Time;
22
23namespace {
24
25// Stream of the sparse data index.
26const int kSparseIndex = 2;
27
28// Stream of the sparse data.
29const int kSparseData = 1;
30
31// We can have up to 64k children.
32const int kMaxMapSize = 8 * 1024;
33
34// The maximum number of bytes that a child can store.
35const int kMaxEntrySize = 0x100000;
36
37// The size of each data block (tracked by the child allocation bitmap).
38const int kBlockSize = 1024;
39
40// Returns the name of a child entry given the base_name and signature of the
41// parent and the child_id.
42// If the entry is called entry_name, child entries will be named something
43// like Range_entry_name:XXX:YYY where XXX is the entry signature and YYY is the
44// number of the particular child.
45std::string GenerateChildName(const std::string& base_name, int64 signature,
46                              int64 child_id) {
47  return base::StringPrintf("Range_%s:%" PRIx64 ":%" PRIx64, base_name.c_str(),
48                            signature, child_id);
49}
50
51// This class deletes the children of a sparse entry.
52class ChildrenDeleter
53    : public base::RefCounted<ChildrenDeleter>,
54      public disk_cache::FileIOCallback {
55 public:
56  ChildrenDeleter(disk_cache::BackendImpl* backend, const std::string& name)
57      : backend_(backend->GetWeakPtr()), name_(name), signature_(0) {}
58
59  virtual void OnFileIOComplete(int bytes_copied) OVERRIDE;
60
61  // Two ways of deleting the children: if we have the children map, use Start()
62  // directly, otherwise pass the data address to ReadData().
63  void Start(char* buffer, int len);
64  void ReadData(disk_cache::Addr address, int len);
65
66 private:
67  friend class base::RefCounted<ChildrenDeleter>;
68  virtual ~ChildrenDeleter() {}
69
70  void DeleteChildren();
71
72  base::WeakPtr<disk_cache::BackendImpl> backend_;
73  std::string name_;
74  disk_cache::Bitmap children_map_;
75  int64 signature_;
76  scoped_ptr<char[]> buffer_;
77  DISALLOW_COPY_AND_ASSIGN(ChildrenDeleter);
78};
79
80// This is the callback of the file operation.
81void ChildrenDeleter::OnFileIOComplete(int bytes_copied) {
82  char* buffer = buffer_.release();
83  Start(buffer, bytes_copied);
84}
85
86void ChildrenDeleter::Start(char* buffer, int len) {
87  buffer_.reset(buffer);
88  if (len < static_cast<int>(sizeof(disk_cache::SparseData)))
89    return Release();
90
91  // Just copy the information from |buffer|, delete |buffer| and start deleting
92  // the child entries.
93  disk_cache::SparseData* data =
94      reinterpret_cast<disk_cache::SparseData*>(buffer);
95  signature_ = data->header.signature;
96
97  int num_bits = (len - sizeof(disk_cache::SparseHeader)) * 8;
98  children_map_.Resize(num_bits, false);
99  children_map_.SetMap(data->bitmap, num_bits / 32);
100  buffer_.reset();
101
102  DeleteChildren();
103}
104
105void ChildrenDeleter::ReadData(disk_cache::Addr address, int len) {
106  DCHECK(address.is_block_file());
107  if (!backend_.get())
108    return Release();
109
110  disk_cache::File* file(backend_->File(address));
111  if (!file)
112    return Release();
113
114  size_t file_offset = address.start_block() * address.BlockSize() +
115                       disk_cache::kBlockHeaderSize;
116
117  buffer_.reset(new char[len]);
118  bool completed;
119  if (!file->Read(buffer_.get(), len, file_offset, this, &completed))
120    return Release();
121
122  if (completed)
123    OnFileIOComplete(len);
124
125  // And wait until OnFileIOComplete gets called.
126}
127
128void ChildrenDeleter::DeleteChildren() {
129  int child_id = 0;
130  if (!children_map_.FindNextSetBit(&child_id) || !backend_.get()) {
131    // We are done. Just delete this object.
132    return Release();
133  }
134  std::string child_name = GenerateChildName(name_, signature_, child_id);
135  backend_->SyncDoomEntry(child_name);
136  children_map_.Set(child_id, false);
137
138  // Post a task to delete the next child.
139  base::MessageLoop::current()->PostTask(
140      FROM_HERE, base::Bind(&ChildrenDeleter::DeleteChildren, this));
141}
142
143// Returns the NetLog event type corresponding to a SparseOperation.
144net::NetLog::EventType GetSparseEventType(
145    disk_cache::SparseControl::SparseOperation operation) {
146  switch (operation) {
147    case disk_cache::SparseControl::kReadOperation:
148      return net::NetLog::TYPE_SPARSE_READ;
149    case disk_cache::SparseControl::kWriteOperation:
150      return net::NetLog::TYPE_SPARSE_WRITE;
151    case disk_cache::SparseControl::kGetRangeOperation:
152      return net::NetLog::TYPE_SPARSE_GET_RANGE;
153    default:
154      NOTREACHED();
155      return net::NetLog::TYPE_CANCELLED;
156  }
157}
158
159// Logs the end event for |operation| on a child entry.  Range operations log
160// no events for each child they search through.
161void LogChildOperationEnd(const net::BoundNetLog& net_log,
162                          disk_cache::SparseControl::SparseOperation operation,
163                          int result) {
164  if (net_log.IsLoggingAllEvents()) {
165    net::NetLog::EventType event_type;
166    switch (operation) {
167      case disk_cache::SparseControl::kReadOperation:
168        event_type = net::NetLog::TYPE_SPARSE_READ_CHILD_DATA;
169        break;
170      case disk_cache::SparseControl::kWriteOperation:
171        event_type = net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA;
172        break;
173      case disk_cache::SparseControl::kGetRangeOperation:
174        return;
175      default:
176        NOTREACHED();
177        return;
178    }
179    net_log.EndEventWithNetErrorCode(event_type, result);
180  }
181}
182
183}  // namespace.
184
185namespace disk_cache {
186
187SparseControl::SparseControl(EntryImpl* entry)
188    : entry_(entry),
189      child_(NULL),
190      operation_(kNoOperation),
191      pending_(false),
192      finished_(false),
193      init_(false),
194      range_found_(false),
195      abort_(false),
196      child_map_(child_data_.bitmap, kNumSparseBits, kNumSparseBits / 32),
197      offset_(0),
198      buf_len_(0),
199      child_offset_(0),
200      child_len_(0),
201      result_(0) {
202  memset(&sparse_header_, 0, sizeof(sparse_header_));
203  memset(&child_data_, 0, sizeof(child_data_));
204}
205
206SparseControl::~SparseControl() {
207  if (child_)
208    CloseChild();
209  if (init_)
210    WriteSparseData();
211}
212
213int SparseControl::Init() {
214  DCHECK(!init_);
215
216  // We should not have sparse data for the exposed entry.
217  if (entry_->GetDataSize(kSparseData))
218    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
219
220  // Now see if there is something where we store our data.
221  int rv = net::OK;
222  int data_len = entry_->GetDataSize(kSparseIndex);
223  if (!data_len) {
224    rv = CreateSparseEntry();
225  } else {
226    rv = OpenSparseEntry(data_len);
227  }
228
229  if (rv == net::OK)
230    init_ = true;
231  return rv;
232}
233
234bool SparseControl::CouldBeSparse() const {
235  DCHECK(!init_);
236
237  if (entry_->GetDataSize(kSparseData))
238    return false;
239
240  // We don't verify the data, just see if it could be there.
241  return (entry_->GetDataSize(kSparseIndex) != 0);
242}
243
244int SparseControl::StartIO(SparseOperation op, int64 offset, net::IOBuffer* buf,
245                           int buf_len, const CompletionCallback& callback) {
246  DCHECK(init_);
247  // We don't support simultaneous IO for sparse data.
248  if (operation_ != kNoOperation)
249    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
250
251  if (offset < 0 || buf_len < 0)
252    return net::ERR_INVALID_ARGUMENT;
253
254  // We only support up to 64 GB.
255  if (offset + buf_len >= 0x1000000000LL || offset + buf_len < 0)
256    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
257
258  DCHECK(!user_buf_.get());
259  DCHECK(user_callback_.is_null());
260
261  if (!buf && (op == kReadOperation || op == kWriteOperation))
262    return 0;
263
264  // Copy the operation parameters.
265  operation_ = op;
266  offset_ = offset;
267  user_buf_ = buf ? new net::DrainableIOBuffer(buf, buf_len) : NULL;
268  buf_len_ = buf_len;
269  user_callback_ = callback;
270
271  result_ = 0;
272  pending_ = false;
273  finished_ = false;
274  abort_ = false;
275
276  if (entry_->net_log().IsLoggingAllEvents()) {
277    entry_->net_log().BeginEvent(
278        GetSparseEventType(operation_),
279        CreateNetLogSparseOperationCallback(offset_, buf_len_));
280  }
281  DoChildrenIO();
282
283  if (!pending_) {
284    // Everything was done synchronously.
285    operation_ = kNoOperation;
286    user_buf_ = NULL;
287    user_callback_.Reset();
288    return result_;
289  }
290
291  return net::ERR_IO_PENDING;
292}
293
294int SparseControl::GetAvailableRange(int64 offset, int len, int64* start) {
295  DCHECK(init_);
296  // We don't support simultaneous IO for sparse data.
297  if (operation_ != kNoOperation)
298    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
299
300  DCHECK(start);
301
302  range_found_ = false;
303  int result = StartIO(
304      kGetRangeOperation, offset, NULL, len, CompletionCallback());
305  if (range_found_) {
306    *start = offset_;
307    return result;
308  }
309
310  // This is a failure. We want to return a valid start value in any case.
311  *start = offset;
312  return result < 0 ? result : 0;  // Don't mask error codes to the caller.
313}
314
315void SparseControl::CancelIO() {
316  if (operation_ == kNoOperation)
317    return;
318  abort_ = true;
319}
320
321int SparseControl::ReadyToUse(const CompletionCallback& callback) {
322  if (!abort_)
323    return net::OK;
324
325  // We'll grab another reference to keep this object alive because we just have
326  // one extra reference due to the pending IO operation itself, but we'll
327  // release that one before invoking user_callback_.
328  entry_->AddRef();  // Balanced in DoAbortCallbacks.
329  abort_callbacks_.push_back(callback);
330  return net::ERR_IO_PENDING;
331}
332
333// Static
334void SparseControl::DeleteChildren(EntryImpl* entry) {
335  DCHECK(entry->GetEntryFlags() & PARENT_ENTRY);
336  int data_len = entry->GetDataSize(kSparseIndex);
337  if (data_len < static_cast<int>(sizeof(SparseData)) ||
338      entry->GetDataSize(kSparseData))
339    return;
340
341  int map_len = data_len - sizeof(SparseHeader);
342  if (map_len > kMaxMapSize || map_len % 4)
343    return;
344
345  char* buffer;
346  Addr address;
347  entry->GetData(kSparseIndex, &buffer, &address);
348  if (!buffer && !address.is_initialized())
349    return;
350
351  entry->net_log().AddEvent(net::NetLog::TYPE_SPARSE_DELETE_CHILDREN);
352
353  DCHECK(entry->backend_.get());
354  ChildrenDeleter* deleter = new ChildrenDeleter(entry->backend_.get(),
355                                                 entry->GetKey());
356  // The object will self destruct when finished.
357  deleter->AddRef();
358
359  if (buffer) {
360    base::MessageLoop::current()->PostTask(
361        FROM_HERE,
362        base::Bind(&ChildrenDeleter::Start, deleter, buffer, data_len));
363  } else {
364    base::MessageLoop::current()->PostTask(
365        FROM_HERE,
366        base::Bind(&ChildrenDeleter::ReadData, deleter, address, data_len));
367  }
368}
369
370// We are going to start using this entry to store sparse data, so we have to
371// initialize our control info.
372int SparseControl::CreateSparseEntry() {
373  if (CHILD_ENTRY & entry_->GetEntryFlags())
374    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
375
376  memset(&sparse_header_, 0, sizeof(sparse_header_));
377  sparse_header_.signature = Time::Now().ToInternalValue();
378  sparse_header_.magic = kIndexMagic;
379  sparse_header_.parent_key_len = entry_->GetKey().size();
380  children_map_.Resize(kNumSparseBits, true);
381
382  // Save the header. The bitmap is saved in the destructor.
383  scoped_refptr<net::IOBuffer> buf(
384      new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_)));
385
386  int rv = entry_->WriteData(kSparseIndex, 0, buf.get(), sizeof(sparse_header_),
387                             CompletionCallback(), false);
388  if (rv != sizeof(sparse_header_)) {
389    DLOG(ERROR) << "Unable to save sparse_header_";
390    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
391  }
392
393  entry_->SetEntryFlags(PARENT_ENTRY);
394  return net::OK;
395}
396
397// We are opening an entry from disk. Make sure that our control data is there.
398int SparseControl::OpenSparseEntry(int data_len) {
399  if (data_len < static_cast<int>(sizeof(SparseData)))
400    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
401
402  if (entry_->GetDataSize(kSparseData))
403    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
404
405  if (!(PARENT_ENTRY & entry_->GetEntryFlags()))
406    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
407
408  // Dont't go over board with the bitmap. 8 KB gives us offsets up to 64 GB.
409  int map_len = data_len - sizeof(sparse_header_);
410  if (map_len > kMaxMapSize || map_len % 4)
411    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
412
413  scoped_refptr<net::IOBuffer> buf(
414      new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_)));
415
416  // Read header.
417  int rv = entry_->ReadData(kSparseIndex, 0, buf.get(), sizeof(sparse_header_),
418                            CompletionCallback());
419  if (rv != static_cast<int>(sizeof(sparse_header_)))
420    return net::ERR_CACHE_READ_FAILURE;
421
422  // The real validation should be performed by the caller. This is just to
423  // double check.
424  if (sparse_header_.magic != kIndexMagic ||
425      sparse_header_.parent_key_len !=
426          static_cast<int>(entry_->GetKey().size()))
427    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
428
429  // Read the actual bitmap.
430  buf = new net::IOBuffer(map_len);
431  rv = entry_->ReadData(kSparseIndex, sizeof(sparse_header_), buf.get(),
432                        map_len, CompletionCallback());
433  if (rv != map_len)
434    return net::ERR_CACHE_READ_FAILURE;
435
436  // Grow the bitmap to the current size and copy the bits.
437  children_map_.Resize(map_len * 8, false);
438  children_map_.SetMap(reinterpret_cast<uint32*>(buf->data()), map_len);
439  return net::OK;
440}
441
442bool SparseControl::OpenChild() {
443  DCHECK_GE(result_, 0);
444
445  std::string key = GenerateChildKey();
446  if (child_) {
447    // Keep using the same child or open another one?.
448    if (key == child_->GetKey())
449      return true;
450    CloseChild();
451  }
452
453  // See if we are tracking this child.
454  if (!ChildPresent())
455    return ContinueWithoutChild(key);
456
457  if (!entry_->backend_.get())
458    return false;
459
460  child_ = entry_->backend_->OpenEntryImpl(key);
461  if (!child_)
462    return ContinueWithoutChild(key);
463
464  EntryImpl* child = static_cast<EntryImpl*>(child_);
465  if (!(CHILD_ENTRY & child->GetEntryFlags()) ||
466      child->GetDataSize(kSparseIndex) <
467          static_cast<int>(sizeof(child_data_)))
468    return KillChildAndContinue(key, false);
469
470  scoped_refptr<net::WrappedIOBuffer> buf(
471      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
472
473  // Read signature.
474  int rv = child_->ReadData(kSparseIndex, 0, buf.get(), sizeof(child_data_),
475                            CompletionCallback());
476  if (rv != sizeof(child_data_))
477    return KillChildAndContinue(key, true);  // This is a fatal failure.
478
479  if (child_data_.header.signature != sparse_header_.signature ||
480      child_data_.header.magic != kIndexMagic)
481    return KillChildAndContinue(key, false);
482
483  if (child_data_.header.last_block_len < 0 ||
484      child_data_.header.last_block_len > kBlockSize) {
485    // Make sure these values are always within range.
486    child_data_.header.last_block_len = 0;
487    child_data_.header.last_block = -1;
488  }
489
490  return true;
491}
492
493void SparseControl::CloseChild() {
494  scoped_refptr<net::WrappedIOBuffer> buf(
495      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
496
497  // Save the allocation bitmap before closing the child entry.
498  int rv = child_->WriteData(kSparseIndex, 0, buf.get(), sizeof(child_data_),
499                             CompletionCallback(), false);
500  if (rv != sizeof(child_data_))
501    DLOG(ERROR) << "Failed to save child data";
502  child_->Release();
503  child_ = NULL;
504}
505
506std::string SparseControl::GenerateChildKey() {
507  return GenerateChildName(entry_->GetKey(), sparse_header_.signature,
508                           offset_ >> 20);
509}
510
511// We are deleting the child because something went wrong.
512bool SparseControl::KillChildAndContinue(const std::string& key, bool fatal) {
513  SetChildBit(false);
514  child_->DoomImpl();
515  child_->Release();
516  child_ = NULL;
517  if (fatal) {
518    result_ = net::ERR_CACHE_READ_FAILURE;
519    return false;
520  }
521  return ContinueWithoutChild(key);
522}
523
524// We were not able to open this child; see what we can do.
525bool SparseControl::ContinueWithoutChild(const std::string& key) {
526  if (kReadOperation == operation_)
527    return false;
528  if (kGetRangeOperation == operation_)
529    return true;
530
531  if (!entry_->backend_.get())
532    return false;
533
534  child_ = entry_->backend_->CreateEntryImpl(key);
535  if (!child_) {
536    child_ = NULL;
537    result_ = net::ERR_CACHE_READ_FAILURE;
538    return false;
539  }
540  // Write signature.
541  InitChildData();
542  return true;
543}
544
545bool SparseControl::ChildPresent() {
546  int child_bit = static_cast<int>(offset_ >> 20);
547  if (children_map_.Size() <= child_bit)
548    return false;
549
550  return children_map_.Get(child_bit);
551}
552
553void SparseControl::SetChildBit(bool value) {
554  int child_bit = static_cast<int>(offset_ >> 20);
555
556  // We may have to increase the bitmap of child entries.
557  if (children_map_.Size() <= child_bit)
558    children_map_.Resize(Bitmap::RequiredArraySize(child_bit + 1) * 32, true);
559
560  children_map_.Set(child_bit, value);
561}
562
563void SparseControl::WriteSparseData() {
564  scoped_refptr<net::IOBuffer> buf(new net::WrappedIOBuffer(
565      reinterpret_cast<const char*>(children_map_.GetMap())));
566
567  int len = children_map_.ArraySize() * 4;
568  int rv = entry_->WriteData(kSparseIndex, sizeof(sparse_header_), buf.get(),
569                             len, CompletionCallback(), false);
570  if (rv != len) {
571    DLOG(ERROR) << "Unable to save sparse map";
572  }
573}
574
575bool SparseControl::VerifyRange() {
576  DCHECK_GE(result_, 0);
577
578  child_offset_ = static_cast<int>(offset_) & (kMaxEntrySize - 1);
579  child_len_ = std::min(buf_len_, kMaxEntrySize - child_offset_);
580
581  // We can write to (or get info from) anywhere in this child.
582  if (operation_ != kReadOperation)
583    return true;
584
585  // Check that there are no holes in this range.
586  int last_bit = (child_offset_ + child_len_ + 1023) >> 10;
587  int start = child_offset_ >> 10;
588  if (child_map_.FindNextBit(&start, last_bit, false)) {
589    // Something is not here.
590    DCHECK_GE(child_data_.header.last_block_len, 0);
591    DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize);
592    int partial_block_len = PartialBlockLength(start);
593    if (start == child_offset_ >> 10) {
594      // It looks like we don't have anything.
595      if (partial_block_len <= (child_offset_ & (kBlockSize - 1)))
596        return false;
597    }
598
599    // We have the first part.
600    child_len_ = (start << 10) - child_offset_;
601    if (partial_block_len) {
602      // We may have a few extra bytes.
603      child_len_ = std::min(child_len_ + partial_block_len, buf_len_);
604    }
605    // There is no need to read more after this one.
606    buf_len_ = child_len_;
607  }
608  return true;
609}
610
611void SparseControl::UpdateRange(int result) {
612  if (result <= 0 || operation_ != kWriteOperation)
613    return;
614
615  DCHECK_GE(child_data_.header.last_block_len, 0);
616  DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize);
617
618  // Write the bitmap.
619  int first_bit = child_offset_ >> 10;
620  int block_offset = child_offset_ & (kBlockSize - 1);
621  if (block_offset && (child_data_.header.last_block != first_bit ||
622                       child_data_.header.last_block_len < block_offset)) {
623    // The first block is not completely filled; ignore it.
624    first_bit++;
625  }
626
627  int last_bit = (child_offset_ + result) >> 10;
628  block_offset = (child_offset_ + result) & (kBlockSize - 1);
629
630  // This condition will hit with the following criteria:
631  // 1. The first byte doesn't follow the last write.
632  // 2. The first byte is in the middle of a block.
633  // 3. The first byte and the last byte are in the same block.
634  if (first_bit > last_bit)
635    return;
636
637  if (block_offset && !child_map_.Get(last_bit)) {
638    // The last block is not completely filled; save it for later.
639    child_data_.header.last_block = last_bit;
640    child_data_.header.last_block_len = block_offset;
641  } else {
642    child_data_.header.last_block = -1;
643  }
644
645  child_map_.SetRange(first_bit, last_bit, true);
646}
647
648int SparseControl::PartialBlockLength(int block_index) const {
649  if (block_index == child_data_.header.last_block)
650    return child_data_.header.last_block_len;
651
652  // This may be the last stored index.
653  int entry_len = child_->GetDataSize(kSparseData);
654  if (block_index == entry_len >> 10)
655    return entry_len & (kBlockSize - 1);
656
657  // This is really empty.
658  return 0;
659}
660
661void SparseControl::InitChildData() {
662  // We know the real type of child_.
663  EntryImpl* child = static_cast<EntryImpl*>(child_);
664  child->SetEntryFlags(CHILD_ENTRY);
665
666  memset(&child_data_, 0, sizeof(child_data_));
667  child_data_.header = sparse_header_;
668
669  scoped_refptr<net::WrappedIOBuffer> buf(
670      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
671
672  int rv = child_->WriteData(kSparseIndex, 0, buf.get(), sizeof(child_data_),
673                             CompletionCallback(), false);
674  if (rv != sizeof(child_data_))
675    DLOG(ERROR) << "Failed to save child data";
676  SetChildBit(true);
677}
678
679void SparseControl::DoChildrenIO() {
680  while (DoChildIO()) continue;
681
682  // Range operations are finished synchronously, often without setting
683  // |finished_| to true.
684  if (kGetRangeOperation == operation_ &&
685      entry_->net_log().IsLoggingAllEvents()) {
686    entry_->net_log().EndEvent(
687        net::NetLog::TYPE_SPARSE_GET_RANGE,
688        CreateNetLogGetAvailableRangeResultCallback(offset_, result_));
689  }
690  if (finished_) {
691    if (kGetRangeOperation != operation_ &&
692        entry_->net_log().IsLoggingAllEvents()) {
693      entry_->net_log().EndEvent(GetSparseEventType(operation_));
694    }
695    if (pending_)
696      DoUserCallback();  // Don't touch this object after this point.
697  }
698}
699
700bool SparseControl::DoChildIO() {
701  finished_ = true;
702  if (!buf_len_ || result_ < 0)
703    return false;
704
705  if (!OpenChild())
706    return false;
707
708  if (!VerifyRange())
709    return false;
710
711  // We have more work to do. Let's not trigger a callback to the caller.
712  finished_ = false;
713  CompletionCallback callback;
714  if (!user_callback_.is_null()) {
715    callback =
716        base::Bind(&SparseControl::OnChildIOCompleted, base::Unretained(this));
717  }
718
719  int rv = 0;
720  switch (operation_) {
721    case kReadOperation:
722      if (entry_->net_log().IsLoggingAllEvents()) {
723        entry_->net_log().BeginEvent(
724            net::NetLog::TYPE_SPARSE_READ_CHILD_DATA,
725            CreateNetLogSparseReadWriteCallback(child_->net_log().source(),
726                                                child_len_));
727      }
728      rv = child_->ReadDataImpl(kSparseData, child_offset_, user_buf_.get(),
729                                child_len_, callback);
730      break;
731    case kWriteOperation:
732      if (entry_->net_log().IsLoggingAllEvents()) {
733        entry_->net_log().BeginEvent(
734            net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA,
735            CreateNetLogSparseReadWriteCallback(child_->net_log().source(),
736                                                child_len_));
737      }
738      rv = child_->WriteDataImpl(kSparseData, child_offset_, user_buf_.get(),
739                                 child_len_, callback, false);
740      break;
741    case kGetRangeOperation:
742      rv = DoGetAvailableRange();
743      break;
744    default:
745      NOTREACHED();
746  }
747
748  if (rv == net::ERR_IO_PENDING) {
749    if (!pending_) {
750      pending_ = true;
751      // The child will protect himself against closing the entry while IO is in
752      // progress. However, this entry can still be closed, and that would not
753      // be a good thing for us, so we increase the refcount until we're
754      // finished doing sparse stuff.
755      entry_->AddRef();  // Balanced in DoUserCallback.
756    }
757    return false;
758  }
759  if (!rv)
760    return false;
761
762  DoChildIOCompleted(rv);
763  return true;
764}
765
766int SparseControl::DoGetAvailableRange() {
767  if (!child_)
768    return child_len_;  // Move on to the next child.
769
770  // Check that there are no holes in this range.
771  int last_bit = (child_offset_ + child_len_ + 1023) >> 10;
772  int start = child_offset_ >> 10;
773  int partial_start_bytes = PartialBlockLength(start);
774  int found = start;
775  int bits_found = child_map_.FindBits(&found, last_bit, true);
776
777  // We don't care if there is a partial block in the middle of the range.
778  int block_offset = child_offset_ & (kBlockSize - 1);
779  if (!bits_found && partial_start_bytes <= block_offset)
780    return child_len_;
781
782  // We are done. Just break the loop and reset result_ to our real result.
783  range_found_ = true;
784
785  // found now points to the first 1. Lets see if we have zeros before it.
786  int empty_start = std::max((found << 10) - child_offset_, 0);
787
788  int bytes_found = bits_found << 10;
789  bytes_found += PartialBlockLength(found + bits_found);
790
791  if (start == found)
792    bytes_found -= block_offset;
793
794  // If the user is searching past the end of this child, bits_found is the
795  // right result; otherwise, we have some empty space at the start of this
796  // query that we have to subtract from the range that we searched.
797  result_ = std::min(bytes_found, child_len_ - empty_start);
798
799  if (!bits_found) {
800    result_ = std::min(partial_start_bytes - block_offset, child_len_);
801    empty_start = 0;
802  }
803
804  // Only update offset_ when this query found zeros at the start.
805  if (empty_start)
806    offset_ += empty_start;
807
808  // This will actually break the loop.
809  buf_len_ = 0;
810  return 0;
811}
812
813void SparseControl::DoChildIOCompleted(int result) {
814  LogChildOperationEnd(entry_->net_log(), operation_, result);
815  if (result < 0) {
816    // We fail the whole operation if we encounter an error.
817    result_ = result;
818    return;
819  }
820
821  UpdateRange(result);
822
823  result_ += result;
824  offset_ += result;
825  buf_len_ -= result;
826
827  // We'll be reusing the user provided buffer for the next chunk.
828  if (buf_len_ && user_buf_.get())
829    user_buf_->DidConsume(result);
830}
831
832void SparseControl::OnChildIOCompleted(int result) {
833  DCHECK_NE(net::ERR_IO_PENDING, result);
834  DoChildIOCompleted(result);
835
836  if (abort_) {
837    // We'll return the current result of the operation, which may be less than
838    // the bytes to read or write, but the user cancelled the operation.
839    abort_ = false;
840    if (entry_->net_log().IsLoggingAllEvents()) {
841      entry_->net_log().AddEvent(net::NetLog::TYPE_CANCELLED);
842      entry_->net_log().EndEvent(GetSparseEventType(operation_));
843    }
844    // We have an indirect reference to this object for every callback so if
845    // there is only one callback, we may delete this object before reaching
846    // DoAbortCallbacks.
847    bool has_abort_callbacks = !abort_callbacks_.empty();
848    DoUserCallback();
849    if (has_abort_callbacks)
850      DoAbortCallbacks();
851    return;
852  }
853
854  // We are running a callback from the message loop. It's time to restart what
855  // we were doing before.
856  DoChildrenIO();
857}
858
859void SparseControl::DoUserCallback() {
860  DCHECK(!user_callback_.is_null());
861  CompletionCallback cb = user_callback_;
862  user_callback_.Reset();
863  user_buf_ = NULL;
864  pending_ = false;
865  operation_ = kNoOperation;
866  int rv = result_;
867  entry_->Release();  // Don't touch object after this line.
868  cb.Run(rv);
869}
870
871void SparseControl::DoAbortCallbacks() {
872  for (size_t i = 0; i < abort_callbacks_.size(); i++) {
873    // Releasing all references to entry_ may result in the destruction of this
874    // object so we should not be touching it after the last Release().
875    CompletionCallback cb = abort_callbacks_[i];
876    if (i == abort_callbacks_.size() - 1)
877      abort_callbacks_.clear();
878
879    entry_->Release();  // Don't touch object after this line.
880    cb.Run(net::OK);
881  }
882}
883
884}  // namespace disk_cache
885