net/disk_cache/blockfile/sparse_control.cc

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