net/disk_cache/memory/mem_entry_impl.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/memory/mem_entry_impl.h"
   6
   7 #include "base/bind.h"
   8 #include "base/logging.h"
   9 #include "base/strings/stringprintf.h"
  10 #include "base/values.h"
  11 #include "net/base/io_buffer.h"
  12 #include "net/base/net_errors.h"
  13 #include "net/disk_cache/memory/mem_backend_impl.h"
  14 #include "net/disk_cache/net_log_parameters.h"
  15
  16 using base::Time;
  17
  18 namespace {
  19
  20 const int kSparseData = 1;
  21
  22 // Maximum size of a sparse entry is 2 to the power of this number.
  23 const int kMaxSparseEntryBits = 12;
  24
  25 // Sparse entry has maximum size of 4KB.
  26 const int kMaxSparseEntrySize = 1 << kMaxSparseEntryBits;
  27
  28 // Convert global offset to child index.
  29 inline int ToChildIndex(int64 offset) {
  30   return static_cast<int>(offset >> kMaxSparseEntryBits);
  31 }
  32
  33 // Convert global offset to offset in child entry.
  34 inline int ToChildOffset(int64 offset) {
  35   return static_cast<int>(offset & (kMaxSparseEntrySize - 1));
  36 }
  37
  38 // Returns a name for a child entry given the base_name of the parent and the
  39 // child_id.  This name is only used for logging purposes.
  40 // If the entry is called entry_name, child entries will be named something
  41 // like Range_entry_name:YYY where YYY is the number of the particular child.
  42 std::string GenerateChildName(const std::string& base_name, int child_id) {
  43   return base::StringPrintf("Range_%s:%i", base_name.c_str(), child_id);
  44 }
  45
  46 // Returns NetLog parameters for the creation of a child MemEntryImpl.  Separate
  47 // function needed because child entries don't suppport GetKey().
  48 scoped_ptr<base::Value> NetLogChildEntryCreationCallback(
  49     const disk_cache::MemEntryImpl* parent,
  50     int child_id,
  51     net::NetLogCaptureMode /* capture_mode */) {
  52   scoped_ptr<base::DictionaryValue> dict(new base::DictionaryValue());
  53   dict->SetString("key", GenerateChildName(parent->GetKey(), child_id));
  54   dict->SetBoolean("created", true);
  55   return dict.Pass();
  56 }
  57
  58 }  // namespace
  59
  60 namespace disk_cache {
  61
  62 MemEntryImpl::MemEntryImpl(MemBackendImpl* backend) {
  63   doomed_ = false;
  64   backend_ = backend;
  65   ref_count_ = 0;
  66   parent_ = NULL;
  67   child_id_ = 0;
  68   child_first_pos_ = 0;
  69   next_ = NULL;
  70   prev_ = NULL;
  71   for (int i = 0; i < NUM_STREAMS; i++)
  72     data_size_[i] = 0;
  73 }
  74
  75 // ------------------------------------------------------------------------
  76
  77 bool MemEntryImpl::CreateEntry(const std::string& key, net::NetLog* net_log) {
  78   key_ = key;
  79   Time current = Time::Now();
  80   last_modified_ = current;
  81   last_used_ = current;
  82
  83   net_log_ = net::BoundNetLog::Make(net_log,
  84                                     net::NetLog::SOURCE_MEMORY_CACHE_ENTRY);
  85   // Must be called after |key_| is set, so GetKey() works.
  86   net_log_.BeginEvent(
  87       net::NetLog::TYPE_DISK_CACHE_MEM_ENTRY_IMPL,
  88       CreateNetLogEntryCreationCallback(this, true));
  89
  90   Open();
  91   backend_->ModifyStorageSize(0, static_cast<int32>(key.size()));
  92   return true;
  93 }
  94
  95 void MemEntryImpl::InternalDoom() {
  96   net_log_.AddEvent(net::NetLog::TYPE_ENTRY_DOOM);
  97   doomed_ = true;
  98   if (!ref_count_) {
  99     if (type() == kParentEntry) {
 100       // If this is a parent entry, we need to doom all the child entries.
 101       if (children_.get()) {
 102         EntryMap children;
 103         children.swap(*children_);
 104         for (EntryMap::iterator i = children.begin();
 105              i != children.end(); ++i) {
 106           // Since a pointer to this object is also saved in the map, avoid
 107           // dooming it.
 108           if (i->second != this)
 109             i->second->Doom();
 110         }
 111         DCHECK(children_->empty());
 112       }
 113     } else {
 114       // If this is a child entry, detach it from the parent.
 115       parent_->DetachChild(child_id_);
 116     }
 117     delete this;
 118   }
 119 }
 120
 121 void MemEntryImpl::Open() {
 122   // Only a parent entry can be opened.
 123   // TODO(hclam): make sure it's correct to not apply the concept of ref
 124   // counting to child entry.
 125   DCHECK(type() == kParentEntry);
 126   ref_count_++;
 127   DCHECK_GE(ref_count_, 0);
 128   DCHECK(!doomed_);
 129 }
 130
 131 bool MemEntryImpl::InUse() {
 132   if (type() == kParentEntry) {
 133     return ref_count_ > 0;
 134   } else {
 135     // A child entry is always not in use. The consequence is that a child entry
 136     // can always be evicted while the associated parent entry is currently in
 137     // used (i.e. opened).
 138     return false;
 139   }
 140 }
 141
 142 // ------------------------------------------------------------------------
 143
 144 void MemEntryImpl::Doom() {
 145   if (doomed_)
 146     return;
 147   if (type() == kParentEntry) {
 148     // Perform internal doom from the backend if this is a parent entry.
 149     backend_->InternalDoomEntry(this);
 150   } else {
 151     // Manually detach from the backend and perform internal doom.
 152     backend_->RemoveFromRankingList(this);
 153     InternalDoom();
 154   }
 155 }
 156
 157 void MemEntryImpl::Close() {
 158   // Only a parent entry can be closed.
 159   DCHECK(type() == kParentEntry);
 160   ref_count_--;
 161   DCHECK_GE(ref_count_, 0);
 162   if (!ref_count_ && doomed_)
 163     InternalDoom();
 164 }
 165
 166 std::string MemEntryImpl::GetKey() const {
 167   // A child entry doesn't have key so this method should not be called.
 168   DCHECK(type() == kParentEntry);
 169   return key_;
 170 }
 171
 172 Time MemEntryImpl::GetLastUsed() const {
 173   return last_used_;
 174 }
 175
 176 Time MemEntryImpl::GetLastModified() const {
 177   return last_modified_;
 178 }
 179
 180 int32 MemEntryImpl::GetDataSize(int index) const {
 181   if (index < 0 || index >= NUM_STREAMS)
 182     return 0;
 183   return data_size_[index];
 184 }
 185
 186 int MemEntryImpl::ReadData(int index, int offset, IOBuffer* buf, int buf_len,
 187                            const CompletionCallback& callback) {
 188   if (net_log_.IsCapturing()) {
 189     net_log_.BeginEvent(
 190         net::NetLog::TYPE_ENTRY_READ_DATA,
 191         CreateNetLogReadWriteDataCallback(index, offset, buf_len, false));
 192   }
 193
 194   int result = InternalReadData(index, offset, buf, buf_len);
 195
 196   if (net_log_.IsCapturing()) {
 197     net_log_.EndEvent(
 198         net::NetLog::TYPE_ENTRY_READ_DATA,
 199         CreateNetLogReadWriteCompleteCallback(result));
 200   }
 201   return result;
 202 }
 203
 204 int MemEntryImpl::WriteData(int index, int offset, IOBuffer* buf, int buf_len,
 205                             const CompletionCallback& callback, bool truncate) {
 206   if (net_log_.IsCapturing()) {
 207     net_log_.BeginEvent(
 208         net::NetLog::TYPE_ENTRY_WRITE_DATA,
 209         CreateNetLogReadWriteDataCallback(index, offset, buf_len, truncate));
 210   }
 211
 212   int result = InternalWriteData(index, offset, buf, buf_len, truncate);
 213
 214   if (net_log_.IsCapturing()) {
 215     net_log_.EndEvent(
 216         net::NetLog::TYPE_ENTRY_WRITE_DATA,
 217         CreateNetLogReadWriteCompleteCallback(result));
 218   }
 219   return result;
 220 }
 221
 222 int MemEntryImpl::ReadSparseData(int64 offset, IOBuffer* buf, int buf_len,
 223                                  const CompletionCallback& callback) {
 224   if (net_log_.IsCapturing()) {
 225     net_log_.BeginEvent(
 226         net::NetLog::TYPE_SPARSE_READ,
 227         CreateNetLogSparseOperationCallback(offset, buf_len));
 228   }
 229   int result = InternalReadSparseData(offset, buf, buf_len);
 230   if (net_log_.IsCapturing())
 231     net_log_.EndEvent(net::NetLog::TYPE_SPARSE_READ);
 232   return result;
 233 }
 234
 235 int MemEntryImpl::WriteSparseData(int64 offset, IOBuffer* buf, int buf_len,
 236                                   const CompletionCallback& callback) {
 237   if (net_log_.IsCapturing()) {
 238     net_log_.BeginEvent(
 239         net::NetLog::TYPE_SPARSE_WRITE,
 240         CreateNetLogSparseOperationCallback(offset, buf_len));
 241   }
 242   int result = InternalWriteSparseData(offset, buf, buf_len);
 243   if (net_log_.IsCapturing())
 244     net_log_.EndEvent(net::NetLog::TYPE_SPARSE_WRITE);
 245   return result;
 246 }
 247
 248 int MemEntryImpl::GetAvailableRange(int64 offset, int len, int64* start,
 249                                     const CompletionCallback& callback) {
 250   if (net_log_.IsCapturing()) {
 251     net_log_.BeginEvent(
 252         net::NetLog::TYPE_SPARSE_GET_RANGE,
 253         CreateNetLogSparseOperationCallback(offset, len));
 254   }
 255   int result = GetAvailableRange(offset, len, start);
 256   if (net_log_.IsCapturing()) {
 257     net_log_.EndEvent(
 258         net::NetLog::TYPE_SPARSE_GET_RANGE,
 259         CreateNetLogGetAvailableRangeResultCallback(*start, result));
 260   }
 261   return result;
 262 }
 263
 264 bool MemEntryImpl::CouldBeSparse() const {
 265   DCHECK_EQ(kParentEntry, type());
 266   return (children_.get() != NULL);
 267 }
 268
 269 int MemEntryImpl::ReadyForSparseIO(const CompletionCallback& callback) {
 270   return net::OK;
 271 }
 272
 273 // ------------------------------------------------------------------------
 274
 275 MemEntryImpl::~MemEntryImpl() {
 276   for (int i = 0; i < NUM_STREAMS; i++)
 277     backend_->ModifyStorageSize(data_size_[i], 0);
 278   backend_->ModifyStorageSize(static_cast<int32>(key_.size()), 0);
 279   net_log_.EndEvent(net::NetLog::TYPE_DISK_CACHE_MEM_ENTRY_IMPL);
 280 }
 281
 282 int MemEntryImpl::InternalReadData(int index, int offset, IOBuffer* buf,
 283                                    int buf_len) {
 284   DCHECK(type() == kParentEntry || index == kSparseData);
 285
 286   if (index < 0 || index >= NUM_STREAMS)
 287     return net::ERR_INVALID_ARGUMENT;
 288
 289   int entry_size = GetDataSize(index);
 290   if (offset >= entry_size || offset < 0 || !buf_len)
 291     return 0;
 292
 293   if (buf_len < 0)
 294     return net::ERR_INVALID_ARGUMENT;
 295
 296   if (offset + buf_len > entry_size)
 297     buf_len = entry_size - offset;
 298
 299   UpdateRank(false);
 300
 301   memcpy(buf->data(), &(data_[index])[offset], buf_len);
 302   return buf_len;
 303 }
 304
 305 int MemEntryImpl::InternalWriteData(int index, int offset, IOBuffer* buf,
 306                                     int buf_len, bool truncate) {
 307   DCHECK(type() == kParentEntry || index == kSparseData);
 308
 309   if (index < 0 || index >= NUM_STREAMS)
 310     return net::ERR_INVALID_ARGUMENT;
 311
 312   if (offset < 0 || buf_len < 0)
 313     return net::ERR_INVALID_ARGUMENT;
 314
 315   int max_file_size = backend_->MaxFileSize();
 316
 317   // offset of buf_len could be negative numbers.
 318   if (offset > max_file_size || buf_len > max_file_size ||
 319       offset + buf_len > max_file_size) {
 320     return net::ERR_FAILED;
 321   }
 322
 323   // Read the size at this point.
 324   int entry_size = GetDataSize(index);
 325
 326   PrepareTarget(index, offset, buf_len);
 327
 328   if (entry_size < offset + buf_len) {
 329     backend_->ModifyStorageSize(entry_size, offset + buf_len);
 330     data_size_[index] = offset + buf_len;
 331   } else if (truncate) {
 332     if (entry_size > offset + buf_len) {
 333       backend_->ModifyStorageSize(entry_size, offset + buf_len);
 334       data_size_[index] = offset + buf_len;
 335     }
 336   }
 337
 338   UpdateRank(true);
 339
 340   if (!buf_len)
 341     return 0;
 342
 343   memcpy(&(data_[index])[offset], buf->data(), buf_len);
 344   return buf_len;
 345 }
 346
 347 int MemEntryImpl::InternalReadSparseData(int64 offset, IOBuffer* buf,
 348                                          int buf_len) {
 349   DCHECK(type() == kParentEntry);
 350
 351   if (!InitSparseInfo())
 352     return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
 353
 354   if (offset < 0 || buf_len < 0)
 355     return net::ERR_INVALID_ARGUMENT;
 356
 357   // We will keep using this buffer and adjust the offset in this buffer.
 358   scoped_refptr<net::DrainableIOBuffer> io_buf(
 359       new net::DrainableIOBuffer(buf, buf_len));
 360
 361   // Iterate until we have read enough.
 362   while (io_buf->BytesRemaining()) {
 363     MemEntryImpl* child = OpenChild(offset + io_buf->BytesConsumed(), false);
 364
 365     // No child present for that offset.
 366     if (!child)
 367       break;
 368
 369     // We then need to prepare the child offset and len.
 370     int child_offset = ToChildOffset(offset + io_buf->BytesConsumed());
 371
 372     // If we are trying to read from a position that the child entry has no data
 373     // we should stop.
 374     if (child_offset < child->child_first_pos_)
 375       break;
 376     if (net_log_.IsCapturing()) {
 377       net_log_.BeginEvent(
 378           net::NetLog::TYPE_SPARSE_READ_CHILD_DATA,
 379           CreateNetLogSparseReadWriteCallback(child->net_log().source(),
 380                                               io_buf->BytesRemaining()));
 381     }
 382     int ret = child->ReadData(kSparseData, child_offset, io_buf.get(),
 383                               io_buf->BytesRemaining(), CompletionCallback());
 384     if (net_log_.IsCapturing()) {
 385       net_log_.EndEventWithNetErrorCode(
 386           net::NetLog::TYPE_SPARSE_READ_CHILD_DATA, ret);
 387     }
 388
 389     // If we encounter an error in one entry, return immediately.
 390     if (ret < 0)
 391       return ret;
 392     else if (ret == 0)
 393       break;
 394
 395     // Increment the counter by number of bytes read in the child entry.
 396     io_buf->DidConsume(ret);
 397   }
 398
 399   UpdateRank(false);
 400
 401   return io_buf->BytesConsumed();
 402 }
 403
 404 int MemEntryImpl::InternalWriteSparseData(int64 offset, IOBuffer* buf,
 405                                           int buf_len) {
 406   DCHECK(type() == kParentEntry);
 407
 408   if (!InitSparseInfo())
 409     return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
 410
 411   if (offset < 0 || buf_len < 0)
 412     return net::ERR_INVALID_ARGUMENT;
 413
 414   scoped_refptr<net::DrainableIOBuffer> io_buf(
 415       new net::DrainableIOBuffer(buf, buf_len));
 416
 417   // This loop walks through child entries continuously starting from |offset|
 418   // and writes blocks of data (of maximum size kMaxSparseEntrySize) into each
 419   // child entry until all |buf_len| bytes are written. The write operation can
 420   // start in the middle of an entry.
 421   while (io_buf->BytesRemaining()) {
 422     MemEntryImpl* child = OpenChild(offset + io_buf->BytesConsumed(), true);
 423     int child_offset = ToChildOffset(offset + io_buf->BytesConsumed());
 424
 425     // Find the right amount to write, this evaluates the remaining bytes to
 426     // write and remaining capacity of this child entry.
 427     int write_len = std::min(static_cast<int>(io_buf->BytesRemaining()),
 428                              kMaxSparseEntrySize - child_offset);
 429
 430     // Keep a record of the last byte position (exclusive) in the child.
 431     int data_size = child->GetDataSize(kSparseData);
 432
 433     if (net_log_.IsCapturing()) {
 434       net_log_.BeginEvent(
 435           net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA,
 436           CreateNetLogSparseReadWriteCallback(child->net_log().source(),
 437                                               write_len));
 438     }
 439
 440     // Always writes to the child entry. This operation may overwrite data
 441     // previously written.
 442     // TODO(hclam): if there is data in the entry and this write is not
 443     // continuous we may want to discard this write.
 444     int ret = child->WriteData(kSparseData, child_offset, io_buf.get(),
 445                                write_len, CompletionCallback(), true);
 446     if (net_log_.IsCapturing()) {
 447       net_log_.EndEventWithNetErrorCode(
 448           net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA, ret);
 449     }
 450     if (ret < 0)
 451       return ret;
 452     else if (ret == 0)
 453       break;
 454
 455     // Keep a record of the first byte position in the child if the write was
 456     // not aligned nor continuous. This is to enable witting to the middle
 457     // of an entry and still keep track of data off the aligned edge.
 458     if (data_size != child_offset)
 459       child->child_first_pos_ = child_offset;
 460
 461     // Adjust the offset in the IO buffer.
 462     io_buf->DidConsume(ret);
 463   }
 464
 465   UpdateRank(true);
 466
 467   return io_buf->BytesConsumed();
 468 }
 469
 470 int MemEntryImpl::GetAvailableRange(int64 offset, int len, int64* start) {
 471   DCHECK(type() == kParentEntry);
 472   DCHECK(start);
 473
 474   if (!InitSparseInfo())
 475     return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
 476
 477   if (offset < 0 || len < 0 || !start)
 478     return net::ERR_INVALID_ARGUMENT;
 479
 480   MemEntryImpl* current_child = NULL;
 481
 482   // Find the first child and record the number of empty bytes.
 483   int empty = FindNextChild(offset, len, &current_child);
 484   if (current_child && empty < len) {
 485     *start = offset + empty;
 486     len -= empty;
 487
 488     // Counts the number of continuous bytes.
 489     int continuous = 0;
 490
 491     // This loop scan for continuous bytes.
 492     while (len && current_child) {
 493       // Number of bytes available in this child.
 494       int data_size = current_child->GetDataSize(kSparseData) -
 495                       ToChildOffset(*start + continuous);
 496       if (data_size > len)
 497         data_size = len;
 498
 499       // We have found more continuous bytes so increment the count. Also
 500       // decrement the length we should scan.
 501       continuous += data_size;
 502       len -= data_size;
 503
 504       // If the next child is discontinuous, break the loop.
 505       if (FindNextChild(*start + continuous, len, &current_child))
 506         break;
 507     }
 508     return continuous;
 509   }
 510   *start = offset;
 511   return 0;
 512 }
 513
 514 void MemEntryImpl::PrepareTarget(int index, int offset, int buf_len) {
 515   int entry_size = GetDataSize(index);
 516
 517   if (entry_size >= offset + buf_len)
 518     return;  // Not growing the stored data.
 519
 520   if (static_cast<int>(data_[index].size()) < offset + buf_len)
 521     data_[index].resize(offset + buf_len);
 522
 523   if (offset <= entry_size)
 524     return;  // There is no "hole" on the stored data.
 525
 526   // Cleanup the hole not written by the user. The point is to avoid returning
 527   // random stuff later on.
 528   memset(&(data_[index])[entry_size], 0, offset - entry_size);
 529 }
 530
 531 void MemEntryImpl::UpdateRank(bool modified) {
 532   Time current = Time::Now();
 533   last_used_ = current;
 534
 535   if (modified)
 536     last_modified_ = current;
 537
 538   if (!doomed_)
 539     backend_->UpdateRank(this);
 540 }
 541
 542 bool MemEntryImpl::InitSparseInfo() {
 543   DCHECK(type() == kParentEntry);
 544
 545   if (!children_.get()) {
 546     // If we already have some data in sparse stream but we are being
 547     // initialized as a sparse entry, we should fail.
 548     if (GetDataSize(kSparseData))
 549       return false;
 550     children_.reset(new EntryMap());
 551
 552     // The parent entry stores data for the first block, so save this object to
 553     // index 0.
 554     (*children_)[0] = this;
 555   }
 556   return true;
 557 }
 558
 559 bool MemEntryImpl::InitChildEntry(MemEntryImpl* parent, int child_id,
 560                                   net::NetLog* net_log) {
 561   DCHECK(!parent_);
 562   DCHECK(!child_id_);
 563
 564   net_log_ = net::BoundNetLog::Make(net_log,
 565                                     net::NetLog::SOURCE_MEMORY_CACHE_ENTRY);
 566   net_log_.BeginEvent(
 567       net::NetLog::TYPE_DISK_CACHE_MEM_ENTRY_IMPL,
 568       base::Bind(&NetLogChildEntryCreationCallback, parent, child_id_));
 569
 570   parent_ = parent;
 571   child_id_ = child_id;
 572   Time current = Time::Now();
 573   last_modified_ = current;
 574   last_used_ = current;
 575   // Insert this to the backend's ranking list.
 576   backend_->InsertIntoRankingList(this);
 577   return true;
 578 }
 579
 580 MemEntryImpl* MemEntryImpl::OpenChild(int64 offset, bool create) {
 581   DCHECK(type() == kParentEntry);
 582   int index = ToChildIndex(offset);
 583   EntryMap::iterator i = children_->find(index);
 584   if (i != children_->end()) {
 585     return i->second;
 586   } else if (create) {
 587     MemEntryImpl* child = new MemEntryImpl(backend_);
 588     child->InitChildEntry(this, index, net_log_.net_log());
 589     (*children_)[index] = child;
 590     return child;
 591   }
 592   return NULL;
 593 }
 594
 595 int MemEntryImpl::FindNextChild(int64 offset, int len, MemEntryImpl** child) {
 596   DCHECK(child);
 597   *child = NULL;
 598   int scanned_len = 0;
 599
 600   // This loop tries to find the first existing child.
 601   while (scanned_len < len) {
 602     // This points to the current offset in the child.
 603     int current_child_offset = ToChildOffset(offset + scanned_len);
 604     MemEntryImpl* current_child = OpenChild(offset + scanned_len, false);
 605     if (current_child) {
 606       int child_first_pos = current_child->child_first_pos_;
 607
 608       // This points to the first byte that we should be reading from, we need
 609       // to take care of the filled region and the current offset in the child.
 610       int first_pos =  std::max(current_child_offset, child_first_pos);
 611
 612       // If the first byte position we should read from doesn't exceed the
 613       // filled region, we have found the first child.
 614       if (first_pos < current_child->GetDataSize(kSparseData)) {
 615          *child = current_child;
 616
 617          // We need to advance the scanned length.
 618          scanned_len += first_pos - current_child_offset;
 619          break;
 620       }
 621     }
 622     scanned_len += kMaxSparseEntrySize - current_child_offset;
 623   }
 624   return scanned_len;
 625 }
 626
 627 void MemEntryImpl::DetachChild(int child_id) {
 628   children_->erase(child_id);
 629 }
 630
 631 }  // namespace disk_cache