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/blockfile/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/blockfile/backend_impl.h"
17#include "net/disk_cache/blockfile/entry_impl.h"
18#include "net/disk_cache/blockfile/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.IsLogging()) {
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 (static_cast<uint64>(offset) + static_cast<unsigned int>(buf_len) >=
256      GG_UINT64_C(0x1000000000)) {
257    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
258  }
259
260  DCHECK(!user_buf_.get());
261  DCHECK(user_callback_.is_null());
262
263  if (!buf && (op == kReadOperation || op == kWriteOperation))
264    return 0;
265
266  // Copy the operation parameters.
267  operation_ = op;
268  offset_ = offset;
269  user_buf_ = buf ? new net::DrainableIOBuffer(buf, buf_len) : NULL;
270  buf_len_ = buf_len;
271  user_callback_ = callback;
272
273  result_ = 0;
274  pending_ = false;
275  finished_ = false;
276  abort_ = false;
277
278  if (entry_->net_log().IsLogging()) {
279    entry_->net_log().BeginEvent(
280        GetSparseEventType(operation_),
281        CreateNetLogSparseOperationCallback(offset_, buf_len_));
282  }
283  DoChildrenIO();
284
285  if (!pending_) {
286    // Everything was done synchronously.
287    operation_ = kNoOperation;
288    user_buf_ = NULL;
289    user_callback_.Reset();
290    return result_;
291  }
292
293  return net::ERR_IO_PENDING;
294}
295
296int SparseControl::GetAvailableRange(int64 offset, int len, int64* start) {
297  DCHECK(init_);
298  // We don't support simultaneous IO for sparse data.
299  if (operation_ != kNoOperation)
300    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
301
302  DCHECK(start);
303
304  range_found_ = false;
305  int result = StartIO(
306      kGetRangeOperation, offset, NULL, len, CompletionCallback());
307  if (range_found_) {
308    *start = offset_;
309    return result;
310  }
311
312  // This is a failure. We want to return a valid start value in any case.
313  *start = offset;
314  return result < 0 ? result : 0;  // Don't mask error codes to the caller.
315}
316
317void SparseControl::CancelIO() {
318  if (operation_ == kNoOperation)
319    return;
320  abort_ = true;
321}
322
323int SparseControl::ReadyToUse(const CompletionCallback& callback) {
324  if (!abort_)
325    return net::OK;
326
327  // We'll grab another reference to keep this object alive because we just have
328  // one extra reference due to the pending IO operation itself, but we'll
329  // release that one before invoking user_callback_.
330  entry_->AddRef();  // Balanced in DoAbortCallbacks.
331  abort_callbacks_.push_back(callback);
332  return net::ERR_IO_PENDING;
333}
334
335// Static
336void SparseControl::DeleteChildren(EntryImpl* entry) {
337  DCHECK(entry->GetEntryFlags() & PARENT_ENTRY);
338  int data_len = entry->GetDataSize(kSparseIndex);
339  if (data_len < static_cast<int>(sizeof(SparseData)) ||
340      entry->GetDataSize(kSparseData))
341    return;
342
343  int map_len = data_len - sizeof(SparseHeader);
344  if (map_len > kMaxMapSize || map_len % 4)
345    return;
346
347  char* buffer;
348  Addr address;
349  entry->GetData(kSparseIndex, &buffer, &address);
350  if (!buffer && !address.is_initialized())
351    return;
352
353  entry->net_log().AddEvent(net::NetLog::TYPE_SPARSE_DELETE_CHILDREN);
354
355  DCHECK(entry->backend_.get());
356  ChildrenDeleter* deleter = new ChildrenDeleter(entry->backend_.get(),
357                                                 entry->GetKey());
358  // The object will self destruct when finished.
359  deleter->AddRef();
360
361  if (buffer) {
362    base::MessageLoop::current()->PostTask(
363        FROM_HERE,
364        base::Bind(&ChildrenDeleter::Start, deleter, buffer, data_len));
365  } else {
366    base::MessageLoop::current()->PostTask(
367        FROM_HERE,
368        base::Bind(&ChildrenDeleter::ReadData, deleter, address, data_len));
369  }
370}
371
372// We are going to start using this entry to store sparse data, so we have to
373// initialize our control info.
374int SparseControl::CreateSparseEntry() {
375  if (CHILD_ENTRY & entry_->GetEntryFlags())
376    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
377
378  memset(&sparse_header_, 0, sizeof(sparse_header_));
379  sparse_header_.signature = Time::Now().ToInternalValue();
380  sparse_header_.magic = kIndexMagic;
381  sparse_header_.parent_key_len = entry_->GetKey().size();
382  children_map_.Resize(kNumSparseBits, true);
383
384  // Save the header. The bitmap is saved in the destructor.
385  scoped_refptr<net::IOBuffer> buf(
386      new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_)));
387
388  int rv = entry_->WriteData(kSparseIndex, 0, buf.get(), sizeof(sparse_header_),
389                             CompletionCallback(), false);
390  if (rv != sizeof(sparse_header_)) {
391    DLOG(ERROR) << "Unable to save sparse_header_";
392    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
393  }
394
395  entry_->SetEntryFlags(PARENT_ENTRY);
396  return net::OK;
397}
398
399// We are opening an entry from disk. Make sure that our control data is there.
400int SparseControl::OpenSparseEntry(int data_len) {
401  if (data_len < static_cast<int>(sizeof(SparseData)))
402    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
403
404  if (entry_->GetDataSize(kSparseData))
405    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
406
407  if (!(PARENT_ENTRY & entry_->GetEntryFlags()))
408    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
409
410  // Dont't go over board with the bitmap. 8 KB gives us offsets up to 64 GB.
411  int map_len = data_len - sizeof(sparse_header_);
412  if (map_len > kMaxMapSize || map_len % 4)
413    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
414
415  scoped_refptr<net::IOBuffer> buf(
416      new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_)));
417
418  // Read header.
419  int rv = entry_->ReadData(kSparseIndex, 0, buf.get(), sizeof(sparse_header_),
420                            CompletionCallback());
421  if (rv != static_cast<int>(sizeof(sparse_header_)))
422    return net::ERR_CACHE_READ_FAILURE;
423
424  // The real validation should be performed by the caller. This is just to
425  // double check.
426  if (sparse_header_.magic != kIndexMagic ||
427      sparse_header_.parent_key_len !=
428          static_cast<int>(entry_->GetKey().size()))
429    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
430
431  // Read the actual bitmap.
432  buf = new net::IOBuffer(map_len);
433  rv = entry_->ReadData(kSparseIndex, sizeof(sparse_header_), buf.get(),
434                        map_len, CompletionCallback());
435  if (rv != map_len)
436    return net::ERR_CACHE_READ_FAILURE;
437
438  // Grow the bitmap to the current size and copy the bits.
439  children_map_.Resize(map_len * 8, false);
440  children_map_.SetMap(reinterpret_cast<uint32*>(buf->data()), map_len);
441  return net::OK;
442}
443
444bool SparseControl::OpenChild() {
445  DCHECK_GE(result_, 0);
446
447  std::string key = GenerateChildKey();
448  if (child_) {
449    // Keep using the same child or open another one?.
450    if (key == child_->GetKey())
451      return true;
452    CloseChild();
453  }
454
455  // See if we are tracking this child.
456  if (!ChildPresent())
457    return ContinueWithoutChild(key);
458
459  if (!entry_->backend_.get())
460    return false;
461
462  child_ = entry_->backend_->OpenEntryImpl(key);
463  if (!child_)
464    return ContinueWithoutChild(key);
465
466  EntryImpl* child = static_cast<EntryImpl*>(child_);
467  if (!(CHILD_ENTRY & child->GetEntryFlags()) ||
468      child->GetDataSize(kSparseIndex) <
469          static_cast<int>(sizeof(child_data_)))
470    return KillChildAndContinue(key, false);
471
472  scoped_refptr<net::WrappedIOBuffer> buf(
473      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
474
475  // Read signature.
476  int rv = child_->ReadData(kSparseIndex, 0, buf.get(), sizeof(child_data_),
477                            CompletionCallback());
478  if (rv != sizeof(child_data_))
479    return KillChildAndContinue(key, true);  // This is a fatal failure.
480
481  if (child_data_.header.signature != sparse_header_.signature ||
482      child_data_.header.magic != kIndexMagic)
483    return KillChildAndContinue(key, false);
484
485  if (child_data_.header.last_block_len < 0 ||
486      child_data_.header.last_block_len > kBlockSize) {
487    // Make sure these values are always within range.
488    child_data_.header.last_block_len = 0;
489    child_data_.header.last_block = -1;
490  }
491
492  return true;
493}
494
495void SparseControl::CloseChild() {
496  scoped_refptr<net::WrappedIOBuffer> buf(
497      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
498
499  // Save the allocation bitmap before closing the child entry.
500  int rv = child_->WriteData(kSparseIndex, 0, buf.get(), sizeof(child_data_),
501                             CompletionCallback(), false);
502  if (rv != sizeof(child_data_))
503    DLOG(ERROR) << "Failed to save child data";
504  child_->Release();
505  child_ = NULL;
506}
507
508std::string SparseControl::GenerateChildKey() {
509  return GenerateChildName(entry_->GetKey(), sparse_header_.signature,
510                           offset_ >> 20);
511}
512
513// We are deleting the child because something went wrong.
514bool SparseControl::KillChildAndContinue(const std::string& key, bool fatal) {
515  SetChildBit(false);
516  child_->DoomImpl();
517  child_->Release();
518  child_ = NULL;
519  if (fatal) {
520    result_ = net::ERR_CACHE_READ_FAILURE;
521    return false;
522  }
523  return ContinueWithoutChild(key);
524}
525
526// We were not able to open this child; see what we can do.
527bool SparseControl::ContinueWithoutChild(const std::string& key) {
528  if (kReadOperation == operation_)
529    return false;
530  if (kGetRangeOperation == operation_)
531    return true;
532
533  if (!entry_->backend_.get())
534    return false;
535
536  child_ = entry_->backend_->CreateEntryImpl(key);
537  if (!child_) {
538    child_ = NULL;
539    result_ = net::ERR_CACHE_READ_FAILURE;
540    return false;
541  }
542  // Write signature.
543  InitChildData();
544  return true;
545}
546
547bool SparseControl::ChildPresent() {
548  int child_bit = static_cast<int>(offset_ >> 20);
549  if (children_map_.Size() <= child_bit)
550    return false;
551
552  return children_map_.Get(child_bit);
553}
554
555void SparseControl::SetChildBit(bool value) {
556  int child_bit = static_cast<int>(offset_ >> 20);
557
558  // We may have to increase the bitmap of child entries.
559  if (children_map_.Size() <= child_bit)
560    children_map_.Resize(Bitmap::RequiredArraySize(child_bit + 1) * 32, true);
561
562  children_map_.Set(child_bit, value);
563}
564
565void SparseControl::WriteSparseData() {
566  scoped_refptr<net::IOBuffer> buf(new net::WrappedIOBuffer(
567      reinterpret_cast<const char*>(children_map_.GetMap())));
568
569  int len = children_map_.ArraySize() * 4;
570  int rv = entry_->WriteData(kSparseIndex, sizeof(sparse_header_), buf.get(),
571                             len, CompletionCallback(), false);
572  if (rv != len) {
573    DLOG(ERROR) << "Unable to save sparse map";
574  }
575}
576
577bool SparseControl::VerifyRange() {
578  DCHECK_GE(result_, 0);
579
580  child_offset_ = static_cast<int>(offset_) & (kMaxEntrySize - 1);
581  child_len_ = std::min(buf_len_, kMaxEntrySize - child_offset_);
582
583  // We can write to (or get info from) anywhere in this child.
584  if (operation_ != kReadOperation)
585    return true;
586
587  // Check that there are no holes in this range.
588  int last_bit = (child_offset_ + child_len_ + 1023) >> 10;
589  int start = child_offset_ >> 10;
590  if (child_map_.FindNextBit(&start, last_bit, false)) {
591    // Something is not here.
592    DCHECK_GE(child_data_.header.last_block_len, 0);
593    DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize);
594    int partial_block_len = PartialBlockLength(start);
595    if (start == child_offset_ >> 10) {
596      // It looks like we don't have anything.
597      if (partial_block_len <= (child_offset_ & (kBlockSize - 1)))
598        return false;
599    }
600
601    // We have the first part.
602    child_len_ = (start << 10) - child_offset_;
603    if (partial_block_len) {
604      // We may have a few extra bytes.
605      child_len_ = std::min(child_len_ + partial_block_len, buf_len_);
606    }
607    // There is no need to read more after this one.
608    buf_len_ = child_len_;
609  }
610  return true;
611}
612
613void SparseControl::UpdateRange(int result) {
614  if (result <= 0 || operation_ != kWriteOperation)
615    return;
616
617  DCHECK_GE(child_data_.header.last_block_len, 0);
618  DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize);
619
620  // Write the bitmap.
621  int first_bit = child_offset_ >> 10;
622  int block_offset = child_offset_ & (kBlockSize - 1);
623  if (block_offset && (child_data_.header.last_block != first_bit ||
624                       child_data_.header.last_block_len < block_offset)) {
625    // The first block is not completely filled; ignore it.
626    first_bit++;
627  }
628
629  int last_bit = (child_offset_ + result) >> 10;
630  block_offset = (child_offset_ + result) & (kBlockSize - 1);
631
632  // This condition will hit with the following criteria:
633  // 1. The first byte doesn't follow the last write.
634  // 2. The first byte is in the middle of a block.
635  // 3. The first byte and the last byte are in the same block.
636  if (first_bit > last_bit)
637    return;
638
639  if (block_offset && !child_map_.Get(last_bit)) {
640    // The last block is not completely filled; save it for later.
641    child_data_.header.last_block = last_bit;
642    child_data_.header.last_block_len = block_offset;
643  } else {
644    child_data_.header.last_block = -1;
645  }
646
647  child_map_.SetRange(first_bit, last_bit, true);
648}
649
650int SparseControl::PartialBlockLength(int block_index) const {
651  if (block_index == child_data_.header.last_block)
652    return child_data_.header.last_block_len;
653
654  // This may be the last stored index.
655  int entry_len = child_->GetDataSize(kSparseData);
656  if (block_index == entry_len >> 10)
657    return entry_len & (kBlockSize - 1);
658
659  // This is really empty.
660  return 0;
661}
662
663void SparseControl::InitChildData() {
664  // We know the real type of child_.
665  EntryImpl* child = static_cast<EntryImpl*>(child_);
666  child->SetEntryFlags(CHILD_ENTRY);
667
668  memset(&child_data_, 0, sizeof(child_data_));
669  child_data_.header = sparse_header_;
670
671  scoped_refptr<net::WrappedIOBuffer> buf(
672      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
673
674  int rv = child_->WriteData(kSparseIndex, 0, buf.get(), sizeof(child_data_),
675                             CompletionCallback(), false);
676  if (rv != sizeof(child_data_))
677    DLOG(ERROR) << "Failed to save child data";
678  SetChildBit(true);
679}
680
681void SparseControl::DoChildrenIO() {
682  while (DoChildIO()) continue;
683
684  // Range operations are finished synchronously, often without setting
685  // |finished_| to true.
686  if (kGetRangeOperation == operation_ &&
687      entry_->net_log().IsLogging()) {
688    entry_->net_log().EndEvent(
689        net::NetLog::TYPE_SPARSE_GET_RANGE,
690        CreateNetLogGetAvailableRangeResultCallback(offset_, result_));
691  }
692  if (finished_) {
693    if (kGetRangeOperation != operation_ &&
694        entry_->net_log().IsLogging()) {
695      entry_->net_log().EndEvent(GetSparseEventType(operation_));
696    }
697    if (pending_)
698      DoUserCallback();  // Don't touch this object after this point.
699  }
700}
701
702bool SparseControl::DoChildIO() {
703  finished_ = true;
704  if (!buf_len_ || result_ < 0)
705    return false;
706
707  if (!OpenChild())
708    return false;
709
710  if (!VerifyRange())
711    return false;
712
713  // We have more work to do. Let's not trigger a callback to the caller.
714  finished_ = false;
715  CompletionCallback callback;
716  if (!user_callback_.is_null()) {
717    callback =
718        base::Bind(&SparseControl::OnChildIOCompleted, base::Unretained(this));
719  }
720
721  int rv = 0;
722  switch (operation_) {
723    case kReadOperation:
724      if (entry_->net_log().IsLogging()) {
725        entry_->net_log().BeginEvent(
726            net::NetLog::TYPE_SPARSE_READ_CHILD_DATA,
727            CreateNetLogSparseReadWriteCallback(child_->net_log().source(),
728                                                child_len_));
729      }
730      rv = child_->ReadDataImpl(kSparseData, child_offset_, user_buf_.get(),
731                                child_len_, callback);
732      break;
733    case kWriteOperation:
734      if (entry_->net_log().IsLogging()) {
735        entry_->net_log().BeginEvent(
736            net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA,
737            CreateNetLogSparseReadWriteCallback(child_->net_log().source(),
738                                                child_len_));
739      }
740      rv = child_->WriteDataImpl(kSparseData, child_offset_, user_buf_.get(),
741                                 child_len_, callback, false);
742      break;
743    case kGetRangeOperation:
744      rv = DoGetAvailableRange();
745      break;
746    default:
747      NOTREACHED();
748  }
749
750  if (rv == net::ERR_IO_PENDING) {
751    if (!pending_) {
752      pending_ = true;
753      // The child will protect himself against closing the entry while IO is in
754      // progress. However, this entry can still be closed, and that would not
755      // be a good thing for us, so we increase the refcount until we're
756      // finished doing sparse stuff.
757      entry_->AddRef();  // Balanced in DoUserCallback.
758    }
759    return false;
760  }
761  if (!rv)
762    return false;
763
764  DoChildIOCompleted(rv);
765  return true;
766}
767
768int SparseControl::DoGetAvailableRange() {
769  if (!child_)
770    return child_len_;  // Move on to the next child.
771
772  // Check that there are no holes in this range.
773  int last_bit = (child_offset_ + child_len_ + 1023) >> 10;
774  int start = child_offset_ >> 10;
775  int partial_start_bytes = PartialBlockLength(start);
776  int found = start;
777  int bits_found = child_map_.FindBits(&found, last_bit, true);
778
779  // We don't care if there is a partial block in the middle of the range.
780  int block_offset = child_offset_ & (kBlockSize - 1);
781  if (!bits_found && partial_start_bytes <= block_offset)
782    return child_len_;
783
784  // We are done. Just break the loop and reset result_ to our real result.
785  range_found_ = true;
786
787  // found now points to the first 1. Lets see if we have zeros before it.
788  int empty_start = std::max((found << 10) - child_offset_, 0);
789
790  int bytes_found = bits_found << 10;
791  bytes_found += PartialBlockLength(found + bits_found);
792
793  if (start == found)
794    bytes_found -= block_offset;
795
796  // If the user is searching past the end of this child, bits_found is the
797  // right result; otherwise, we have some empty space at the start of this
798  // query that we have to subtract from the range that we searched.
799  result_ = std::min(bytes_found, child_len_ - empty_start);
800
801  if (!bits_found) {
802    result_ = std::min(partial_start_bytes - block_offset, child_len_);
803    empty_start = 0;
804  }
805
806  // Only update offset_ when this query found zeros at the start.
807  if (empty_start)
808    offset_ += empty_start;
809
810  // This will actually break the loop.
811  buf_len_ = 0;
812  return 0;
813}
814
815void SparseControl::DoChildIOCompleted(int result) {
816  LogChildOperationEnd(entry_->net_log(), operation_, result);
817  if (result < 0) {
818    // We fail the whole operation if we encounter an error.
819    result_ = result;
820    return;
821  }
822
823  UpdateRange(result);
824
825  result_ += result;
826  offset_ += result;
827  buf_len_ -= result;
828
829  // We'll be reusing the user provided buffer for the next chunk.
830  if (buf_len_ && user_buf_.get())
831    user_buf_->DidConsume(result);
832}
833
834void SparseControl::OnChildIOCompleted(int result) {
835  DCHECK_NE(net::ERR_IO_PENDING, result);
836  DoChildIOCompleted(result);
837
838  if (abort_) {
839    // We'll return the current result of the operation, which may be less than
840    // the bytes to read or write, but the user cancelled the operation.
841    abort_ = false;
842    if (entry_->net_log().IsLogging()) {
843      entry_->net_log().AddEvent(net::NetLog::TYPE_CANCELLED);
844      entry_->net_log().EndEvent(GetSparseEventType(operation_));
845    }
846    // We have an indirect reference to this object for every callback so if
847    // there is only one callback, we may delete this object before reaching
848    // DoAbortCallbacks.
849    bool has_abort_callbacks = !abort_callbacks_.empty();
850    DoUserCallback();
851    if (has_abort_callbacks)
852      DoAbortCallbacks();
853    return;
854  }
855
856  // We are running a callback from the message loop. It's time to restart what
857  // we were doing before.
858  DoChildrenIO();
859}
860
861void SparseControl::DoUserCallback() {
862  DCHECK(!user_callback_.is_null());
863  CompletionCallback cb = user_callback_;
864  user_callback_.Reset();
865  user_buf_ = NULL;
866  pending_ = false;
867  operation_ = kNoOperation;
868  int rv = result_;
869  entry_->Release();  // Don't touch object after this line.
870  cb.Run(rv);
871}
872
873void SparseControl::DoAbortCallbacks() {
874  for (size_t i = 0; i < abort_callbacks_.size(); i++) {
875    // Releasing all references to entry_ may result in the destruction of this
876    // object so we should not be touching it after the last Release().
877    CompletionCallback cb = abort_callbacks_[i];
878    if (i == abort_callbacks_.size() - 1)
879      abort_callbacks_.clear();
880
881    entry_->Release();  // Don't touch object after this line.
882    cb.Run(net::OK);
883  }
884}
885
886}  // namespace disk_cache
887