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/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/mem_backend_impl.h"
14#include "net/disk_cache/net_log_parameters.h"
15
16using base::Time;
17
18namespace {
19
20const int kSparseData = 1;
21
22// Maximum size of a sparse entry is 2 to the power of this number.
23const int kMaxSparseEntryBits = 12;
24
25// Sparse entry has maximum size of 4KB.
26const int kMaxSparseEntrySize = 1 << kMaxSparseEntryBits;
27
28// Convert global offset to child index.
29inline int ToChildIndex(int64 offset) {
30  return static_cast<int>(offset >> kMaxSparseEntryBits);
31}
32
33// Convert global offset to offset in child entry.
34inline 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.
42std::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().
48base::Value* NetLogChildEntryCreationCallback(
49    const disk_cache::MemEntryImpl* parent,
50    int child_id,
51    net::NetLog::LogLevel /* log_level */) {
52  base::DictionaryValue* dict = new base::DictionaryValue();
53  dict->SetString("key", GenerateChildName(parent->GetKey(), child_id));
54  dict->SetBoolean("created", true);
55  return dict;
56}
57
58}  // namespace
59
60namespace disk_cache {
61
62MemEntryImpl::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
77bool 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
95void 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
121void 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
131bool 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
144void 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
157void 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
166std::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
172Time MemEntryImpl::GetLastUsed() const {
173  return last_used_;
174}
175
176Time MemEntryImpl::GetLastModified() const {
177  return last_modified_;
178}
179
180int32 MemEntryImpl::GetDataSize(int index) const {
181  if (index < 0 || index >= NUM_STREAMS)
182    return 0;
183  return data_size_[index];
184}
185
186int MemEntryImpl::ReadData(int index, int offset, IOBuffer* buf, int buf_len,
187                           const CompletionCallback& callback) {
188  if (net_log_.IsLoggingAllEvents()) {
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_.IsLoggingAllEvents()) {
197    net_log_.EndEvent(
198        net::NetLog::TYPE_ENTRY_READ_DATA,
199        CreateNetLogReadWriteCompleteCallback(result));
200  }
201  return result;
202}
203
204int MemEntryImpl::WriteData(int index, int offset, IOBuffer* buf, int buf_len,
205                            const CompletionCallback& callback, bool truncate) {
206  if (net_log_.IsLoggingAllEvents()) {
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_.IsLoggingAllEvents()) {
215    net_log_.EndEvent(
216        net::NetLog::TYPE_ENTRY_WRITE_DATA,
217        CreateNetLogReadWriteCompleteCallback(result));
218  }
219  return result;
220}
221
222int MemEntryImpl::ReadSparseData(int64 offset, IOBuffer* buf, int buf_len,
223                                 const CompletionCallback& callback) {
224  if (net_log_.IsLoggingAllEvents()) {
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_.IsLoggingAllEvents())
231    net_log_.EndEvent(net::NetLog::TYPE_SPARSE_READ);
232  return result;
233}
234
235int MemEntryImpl::WriteSparseData(int64 offset, IOBuffer* buf, int buf_len,
236                                  const CompletionCallback& callback) {
237  if (net_log_.IsLoggingAllEvents()) {
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_.IsLoggingAllEvents())
244    net_log_.EndEvent(net::NetLog::TYPE_SPARSE_WRITE);
245  return result;
246}
247
248int MemEntryImpl::GetAvailableRange(int64 offset, int len, int64* start,
249                                    const CompletionCallback& callback) {
250  if (net_log_.IsLoggingAllEvents()) {
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_.IsLoggingAllEvents()) {
257    net_log_.EndEvent(
258        net::NetLog::TYPE_SPARSE_GET_RANGE,
259        CreateNetLogGetAvailableRangeResultCallback(*start, result));
260  }
261  return result;
262}
263
264bool MemEntryImpl::CouldBeSparse() const {
265  DCHECK_EQ(kParentEntry, type());
266  return (children_.get() != NULL);
267}
268
269int MemEntryImpl::ReadyForSparseIO(const CompletionCallback& callback) {
270  return net::OK;
271}
272
273// ------------------------------------------------------------------------
274
275MemEntryImpl::~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
282int 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
305int 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
347int 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_.IsLoggingAllEvents()) {
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_.IsLoggingAllEvents()) {
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
404int 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_.IsLoggingAllEvents()) {
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_.IsLoggingAllEvents()) {
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
470int 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) {
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
514void 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
531void 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
542bool 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
559bool 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
580MemEntryImpl* 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
595int 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
627void MemEntryImpl::DetachChild(int child_id) {
628  children_->erase(child_id);
629}
630
631}  // namespace disk_cache
632