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 "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
  21 using base::Time;
  22
  23 namespace {
  24
  25 // Stream of the sparse data index.
  26 const int kSparseIndex = 2;
  27
  28 // Stream of the sparse data.
  29 const int kSparseData = 1;
  30
  31 // We can have up to 64k children.
  32 const int kMaxMapSize = 8 * 1024;
  33
  34 // The maximum number of bytes that a child can store.
  35 const int kMaxEntrySize = 0x100000;
  36
  37 // The size of each data block (tracked by the child allocation bitmap).
  38 const 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.
  45 std::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.
  52 class 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   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   ~ChildrenDeleter() override {}
  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.
  81 void ChildrenDeleter::OnFileIOComplete(int bytes_copied) {
  82   char* buffer = buffer_.release();
  83   Start(buffer, bytes_copied);
  84 }
  85
  86 void 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
 105 void 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
 128 void 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.
 144 net::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.
 161 void 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
 185 namespace disk_cache {
 186
 187 SparseControl::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
 206 SparseControl::~SparseControl() {
 207   if (child_)
 208     CloseChild();
 209   if (init_)
 210     WriteSparseData();
 211 }
 212
 213 int 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
 234 bool 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
 244 int 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
 296 int 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
 317 void SparseControl::CancelIO() {
 318   if (operation_ == kNoOperation)
 319     return;
 320   abort_ = true;
 321 }
 322
 323 int 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
 336 void 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.
 374 int 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.
 400 int 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
 444 bool 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
 495 void 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
 508 std::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.
 514 bool 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.
 527 bool 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
 547 bool 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
 555 void 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
 565 void 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
 577 bool 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, kBlockSize);
 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
 613 void 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, kBlockSize);
 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
 650 int 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 is really empty.
 655   return 0;
 656 }
 657
 658 void SparseControl::InitChildData() {
 659   // We know the real type of child_.
 660   EntryImpl* child = static_cast<EntryImpl*>(child_);
 661   child->SetEntryFlags(CHILD_ENTRY);
 662
 663   memset(&child_data_, 0, sizeof(child_data_));
 664   child_data_.header = sparse_header_;
 665
 666   scoped_refptr<net::WrappedIOBuffer> buf(
 667       new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
 668
 669   int rv = child_->WriteData(kSparseIndex, 0, buf.get(), sizeof(child_data_),
 670                              CompletionCallback(), false);
 671   if (rv != sizeof(child_data_))
 672     DLOG(ERROR) << "Failed to save child data";
 673   SetChildBit(true);
 674 }
 675
 676 void SparseControl::DoChildrenIO() {
 677   while (DoChildIO()) continue;
 678
 679   // Range operations are finished synchronously, often without setting
 680   // |finished_| to true.
 681   if (kGetRangeOperation == operation_ &&
 682       entry_->net_log().IsLogging()) {
 683     entry_->net_log().EndEvent(
 684         net::NetLog::TYPE_SPARSE_GET_RANGE,
 685         CreateNetLogGetAvailableRangeResultCallback(offset_, result_));
 686   }
 687   if (finished_) {
 688     if (kGetRangeOperation != operation_ &&
 689         entry_->net_log().IsLogging()) {
 690       entry_->net_log().EndEvent(GetSparseEventType(operation_));
 691     }
 692     if (pending_)
 693       DoUserCallback();  // Don't touch this object after this point.
 694   }
 695 }
 696
 697 bool SparseControl::DoChildIO() {
 698   finished_ = true;
 699   if (!buf_len_ || result_ < 0)
 700     return false;
 701
 702   if (!OpenChild())
 703     return false;
 704
 705   if (!VerifyRange())
 706     return false;
 707
 708   // We have more work to do. Let's not trigger a callback to the caller.
 709   finished_ = false;
 710   CompletionCallback callback;
 711   if (!user_callback_.is_null()) {
 712     callback =
 713         base::Bind(&SparseControl::OnChildIOCompleted, base::Unretained(this));
 714   }
 715
 716   int rv = 0;
 717   switch (operation_) {
 718     case kReadOperation:
 719       if (entry_->net_log().IsLogging()) {
 720         entry_->net_log().BeginEvent(
 721             net::NetLog::TYPE_SPARSE_READ_CHILD_DATA,
 722             CreateNetLogSparseReadWriteCallback(child_->net_log().source(),
 723                                                 child_len_));
 724       }
 725       rv = child_->ReadDataImpl(kSparseData, child_offset_, user_buf_.get(),
 726                                 child_len_, callback);
 727       break;
 728     case kWriteOperation:
 729       if (entry_->net_log().IsLogging()) {
 730         entry_->net_log().BeginEvent(
 731             net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA,
 732             CreateNetLogSparseReadWriteCallback(child_->net_log().source(),
 733                                                 child_len_));
 734       }
 735       rv = child_->WriteDataImpl(kSparseData, child_offset_, user_buf_.get(),
 736                                  child_len_, callback, false);
 737       break;
 738     case kGetRangeOperation:
 739       rv = DoGetAvailableRange();
 740       break;
 741     default:
 742       NOTREACHED();
 743   }
 744
 745   if (rv == net::ERR_IO_PENDING) {
 746     if (!pending_) {
 747       pending_ = true;
 748       // The child will protect himself against closing the entry while IO is in
 749       // progress. However, this entry can still be closed, and that would not
 750       // be a good thing for us, so we increase the refcount until we're
 751       // finished doing sparse stuff.
 752       entry_->AddRef();  // Balanced in DoUserCallback.
 753     }
 754     return false;
 755   }
 756   if (!rv)
 757     return false;
 758
 759   DoChildIOCompleted(rv);
 760   return true;
 761 }
 762
 763 int SparseControl::DoGetAvailableRange() {
 764   if (!child_)
 765     return child_len_;  // Move on to the next child.
 766
 767   // Bits on the bitmap should only be set when the corresponding block was
 768   // fully written (it's really being used). If a block is partially used, it
 769   // has to start with valid data, the length of the valid data is saved in
 770   // |header.last_block_len| and the block itself should match
 771   // |header.last_block|.
 772   //
 773   // In other words, (|header.last_block| + |header.last_block_len|) is the
 774   // offset where the last write ended, and data in that block (which is not
 775   // marked as used because it is not full) will only be reused if the next
 776   // write continues at that point.
 777   //
 778   // This code has to find if there is any data between child_offset_ and
 779   // child_offset_ + child_len_.
 780   int last_bit = (child_offset_ + child_len_ + kBlockSize - 1) >> 10;
 781   int start = child_offset_ >> 10;
 782   int partial_start_bytes = PartialBlockLength(start);
 783   int found = start;
 784   int bits_found = child_map_.FindBits(&found, last_bit, true);
 785   bool is_last_block_in_range = start < child_data_.header.last_block &&
 786                                 child_data_.header.last_block < last_bit;
 787
 788   int block_offset = child_offset_ & (kBlockSize - 1);
 789   if (!bits_found && partial_start_bytes <= block_offset) {
 790     if (!is_last_block_in_range)
 791       return child_len_;
 792     found = last_bit - 1;  // There are some bytes here.
 793   }
 794
 795   // We are done. Just break the loop and reset result_ to our real result.
 796   range_found_ = true;
 797
 798   int bytes_found = bits_found << 10;
 799   bytes_found += PartialBlockLength(found + bits_found);
 800
 801   // found now points to the first bytes. Lets see if we have data before it.
 802   int empty_start = std::max((found << 10) - child_offset_, 0);
 803   if (empty_start >= child_len_)
 804     return child_len_;
 805
 806   // At this point we have bytes_found stored after (found << 10), and we want
 807   // child_len_ bytes after child_offset_. The first empty_start bytes after
 808   // child_offset_ are invalid.
 809
 810   if (start == found)
 811     bytes_found -= block_offset;
 812
 813   // If the user is searching past the end of this child, bits_found is the
 814   // right result; otherwise, we have some empty space at the start of this
 815   // query that we have to subtract from the range that we searched.
 816   result_ = std::min(bytes_found, child_len_ - empty_start);
 817
 818   if (partial_start_bytes) {
 819     result_ = std::min(partial_start_bytes - block_offset, child_len_);
 820     empty_start = 0;
 821   }
 822
 823   // Only update offset_ when this query found zeros at the start.
 824   if (empty_start)
 825     offset_ += empty_start;
 826
 827   // This will actually break the loop.
 828   buf_len_ = 0;
 829   return 0;
 830 }
 831
 832 void SparseControl::DoChildIOCompleted(int result) {
 833   LogChildOperationEnd(entry_->net_log(), operation_, result);
 834   if (result < 0) {
 835     // We fail the whole operation if we encounter an error.
 836     result_ = result;
 837     return;
 838   }
 839
 840   UpdateRange(result);
 841
 842   result_ += result;
 843   offset_ += result;
 844   buf_len_ -= result;
 845
 846   // We'll be reusing the user provided buffer for the next chunk.
 847   if (buf_len_ && user_buf_.get())
 848     user_buf_->DidConsume(result);
 849 }
 850
 851 void SparseControl::OnChildIOCompleted(int result) {
 852   DCHECK_NE(net::ERR_IO_PENDING, result);
 853   DoChildIOCompleted(result);
 854
 855   if (abort_) {
 856     // We'll return the current result of the operation, which may be less than
 857     // the bytes to read or write, but the user cancelled the operation.
 858     abort_ = false;
 859     if (entry_->net_log().IsLogging()) {
 860       entry_->net_log().AddEvent(net::NetLog::TYPE_CANCELLED);
 861       entry_->net_log().EndEvent(GetSparseEventType(operation_));
 862     }
 863     // We have an indirect reference to this object for every callback so if
 864     // there is only one callback, we may delete this object before reaching
 865     // DoAbortCallbacks.
 866     bool has_abort_callbacks = !abort_callbacks_.empty();
 867     DoUserCallback();
 868     if (has_abort_callbacks)
 869       DoAbortCallbacks();
 870     return;
 871   }
 872
 873   // We are running a callback from the message loop. It's time to restart what
 874   // we were doing before.
 875   DoChildrenIO();
 876 }
 877
 878 void SparseControl::DoUserCallback() {
 879   DCHECK(!user_callback_.is_null());
 880   CompletionCallback cb = user_callback_;
 881   user_callback_.Reset();
 882   user_buf_ = NULL;
 883   pending_ = false;
 884   operation_ = kNoOperation;
 885   int rv = result_;
 886   entry_->Release();  // Don't touch object after this line.
 887   cb.Run(rv);
 888 }
 889
 890 void SparseControl::DoAbortCallbacks() {
 891   for (size_t i = 0; i < abort_callbacks_.size(); i++) {
 892     // Releasing all references to entry_ may result in the destruction of this
 893     // object so we should not be touching it after the last Release().
 894     CompletionCallback cb = abort_callbacks_[i];
 895     if (i == abort_callbacks_.size() - 1)
 896       abort_callbacks_.clear();
 897
 898     entry_->Release();  // Don't touch object after this line.
 899     cb.Run(net::OK);
 900   }
 901 }
 902
 903 }  // namespace disk_cache