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