1 // Copyright (c) 2013 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/simple/simple_index.h" 6 7 #include <algorithm> 8 #include <limits> 9 #include <string> 10 #include <utility> 11 12 #include "base/bind.h" 13 #include "base/bind_helpers.h" 14 #include "base/files/file_enumerator.h" 15 #include "base/files/file_util.h" 16 #include "base/logging.h" 17 #include "base/message_loop/message_loop.h" 18 #include "base/metrics/field_trial.h" 19 #include "base/pickle.h" 20 #include "base/strings/string_number_conversions.h" 21 #include "base/strings/string_tokenizer.h" 22 #include "base/task_runner.h" 23 #include "base/threading/worker_pool.h" 24 #include "base/time/time.h" 25 #include "net/base/net_errors.h" 26 #include "net/disk_cache/simple/simple_entry_format.h" 27 #include "net/disk_cache/simple/simple_histogram_macros.h" 28 #include "net/disk_cache/simple/simple_index_delegate.h" 29 #include "net/disk_cache/simple/simple_index_file.h" 30 #include "net/disk_cache/simple/simple_synchronous_entry.h" 31 #include "net/disk_cache/simple/simple_util.h" 32 33 #if defined(OS_POSIX) 34 #include <sys/stat.h> 35 #include <sys/time.h> 36 #endif 37 38 namespace { 39 40 // How many milliseconds we delay writing the index to disk since the last cache 41 // operation has happened. 42 const int kWriteToDiskDelayMSecs = 20000; 43 const int kWriteToDiskOnBackgroundDelayMSecs = 100; 44 45 // Divides the cache space into this amount of parts to evict when only one part 46 // is left. 47 const uint32 kEvictionMarginDivisor = 20; 48 49 const uint32 kBytesInKb = 1024; 50 51 // Utility class used for timestamp comparisons in entry metadata while sorting. 52 class CompareHashesForTimestamp { 53 typedef disk_cache::SimpleIndex SimpleIndex; 54 typedef disk_cache::SimpleIndex::EntrySet EntrySet; 55 public: 56 explicit CompareHashesForTimestamp(const EntrySet& set); 57 58 bool operator()(uint64 hash1, uint64 hash2); 59 private: 60 const EntrySet& entry_set_; 61 }; 62 63 CompareHashesForTimestamp::CompareHashesForTimestamp(const EntrySet& set) 64 : entry_set_(set) { 65 } 66 67 bool CompareHashesForTimestamp::operator()(uint64 hash1, uint64 hash2) { 68 EntrySet::const_iterator it1 = entry_set_.find(hash1); 69 DCHECK(it1 != entry_set_.end()); 70 EntrySet::const_iterator it2 = entry_set_.find(hash2); 71 DCHECK(it2 != entry_set_.end()); 72 return it1->second.GetLastUsedTime() < it2->second.GetLastUsedTime(); 73 } 74 75 } // namespace 76 77 namespace disk_cache { 78 79 EntryMetadata::EntryMetadata() 80 : last_used_time_seconds_since_epoch_(0), 81 entry_size_(0) { 82 } 83 84 EntryMetadata::EntryMetadata(base::Time last_used_time, int entry_size) 85 : last_used_time_seconds_since_epoch_(0), 86 entry_size_(entry_size) { 87 SetLastUsedTime(last_used_time); 88 } 89 90 base::Time EntryMetadata::GetLastUsedTime() const { 91 // Preserve nullity. 92 if (last_used_time_seconds_since_epoch_ == 0) 93 return base::Time(); 94 95 return base::Time::UnixEpoch() + 96 base::TimeDelta::FromSeconds(last_used_time_seconds_since_epoch_); 97 } 98 99 void EntryMetadata::SetLastUsedTime(const base::Time& last_used_time) { 100 // Preserve nullity. 101 if (last_used_time.is_null()) { 102 last_used_time_seconds_since_epoch_ = 0; 103 return; 104 } 105 106 const base::TimeDelta since_unix_epoch = 107 last_used_time - base::Time::UnixEpoch(); 108 const int64 seconds_since_unix_epoch = since_unix_epoch.InSeconds(); 109 DCHECK_LE(implicit_cast<int64>(std::numeric_limits<uint32>::min()), 110 seconds_since_unix_epoch); 111 DCHECK_GE(implicit_cast<int64>(std::numeric_limits<uint32>::max()), 112 seconds_since_unix_epoch); 113 114 last_used_time_seconds_since_epoch_ = seconds_since_unix_epoch; 115 // Avoid accidental nullity. 116 if (last_used_time_seconds_since_epoch_ == 0) 117 last_used_time_seconds_since_epoch_ = 1; 118 } 119 120 void EntryMetadata::Serialize(Pickle* pickle) const { 121 DCHECK(pickle); 122 int64 internal_last_used_time = GetLastUsedTime().ToInternalValue(); 123 pickle->WriteInt64(internal_last_used_time); 124 pickle->WriteUInt64(entry_size_); 125 } 126 127 bool EntryMetadata::Deserialize(PickleIterator* it) { 128 DCHECK(it); 129 int64 tmp_last_used_time; 130 uint64 tmp_entry_size; 131 if (!it->ReadInt64(&tmp_last_used_time) || !it->ReadUInt64(&tmp_entry_size)) 132 return false; 133 SetLastUsedTime(base::Time::FromInternalValue(tmp_last_used_time)); 134 entry_size_ = tmp_entry_size; 135 return true; 136 } 137 138 SimpleIndex::SimpleIndex( 139 const scoped_refptr<base::SingleThreadTaskRunner>& io_thread, 140 SimpleIndexDelegate* delegate, 141 net::CacheType cache_type, 142 scoped_ptr<SimpleIndexFile> index_file) 143 : delegate_(delegate), 144 cache_type_(cache_type), 145 cache_size_(0), 146 max_size_(0), 147 high_watermark_(0), 148 low_watermark_(0), 149 eviction_in_progress_(false), 150 initialized_(false), 151 index_file_(index_file.Pass()), 152 io_thread_(io_thread), 153 // Creating the callback once so it is reused every time 154 // write_to_disk_timer_.Start() is called. 155 write_to_disk_cb_(base::Bind(&SimpleIndex::WriteToDisk, AsWeakPtr())), 156 app_on_background_(false) { 157 } 158 159 SimpleIndex::~SimpleIndex() { 160 DCHECK(io_thread_checker_.CalledOnValidThread()); 161 162 // Fail all callbacks waiting for the index to come up. 163 for (CallbackList::iterator it = to_run_when_initialized_.begin(), 164 end = to_run_when_initialized_.end(); it != end; ++it) { 165 it->Run(net::ERR_ABORTED); 166 } 167 } 168 169 void SimpleIndex::Initialize(base::Time cache_mtime) { 170 DCHECK(io_thread_checker_.CalledOnValidThread()); 171 172 #if defined(OS_ANDROID) 173 if (base::android::IsVMInitialized()) { 174 app_status_listener_.reset(new base::android::ApplicationStatusListener( 175 base::Bind(&SimpleIndex::OnApplicationStateChange, AsWeakPtr()))); 176 } 177 #endif 178 179 SimpleIndexLoadResult* load_result = new SimpleIndexLoadResult(); 180 scoped_ptr<SimpleIndexLoadResult> load_result_scoped(load_result); 181 base::Closure reply = base::Bind( 182 &SimpleIndex::MergeInitializingSet, 183 AsWeakPtr(), 184 base::Passed(&load_result_scoped)); 185 index_file_->LoadIndexEntries(cache_mtime, reply, load_result); 186 } 187 188 bool SimpleIndex::SetMaxSize(int max_bytes) { 189 if (max_bytes < 0) 190 return false; 191 192 // Zero size means use the default. 193 if (!max_bytes) 194 return true; 195 196 max_size_ = max_bytes; 197 high_watermark_ = max_size_ - max_size_ / kEvictionMarginDivisor; 198 low_watermark_ = max_size_ - 2 * (max_size_ / kEvictionMarginDivisor); 199 return true; 200 } 201 202 int SimpleIndex::ExecuteWhenReady(const net::CompletionCallback& task) { 203 DCHECK(io_thread_checker_.CalledOnValidThread()); 204 if (initialized_) 205 io_thread_->PostTask(FROM_HERE, base::Bind(task, net::OK)); 206 else 207 to_run_when_initialized_.push_back(task); 208 return net::ERR_IO_PENDING; 209 } 210 211 scoped_ptr<SimpleIndex::HashList> SimpleIndex::GetEntriesBetween( 212 base::Time initial_time, base::Time end_time) { 213 DCHECK_EQ(true, initialized_); 214 215 if (!initial_time.is_null()) 216 initial_time -= EntryMetadata::GetLowerEpsilonForTimeComparisons(); 217 if (end_time.is_null()) 218 end_time = base::Time::Max(); 219 else 220 end_time += EntryMetadata::GetUpperEpsilonForTimeComparisons(); 221 const base::Time extended_end_time = 222 end_time.is_null() ? base::Time::Max() : end_time; 223 DCHECK(extended_end_time >= initial_time); 224 scoped_ptr<HashList> ret_hashes(new HashList()); 225 for (EntrySet::iterator it = entries_set_.begin(), end = entries_set_.end(); 226 it != end; ++it) { 227 EntryMetadata& metadata = it->second; 228 base::Time entry_time = metadata.GetLastUsedTime(); 229 if (initial_time <= entry_time && entry_time < extended_end_time) 230 ret_hashes->push_back(it->first); 231 } 232 return ret_hashes.Pass(); 233 } 234 235 scoped_ptr<SimpleIndex::HashList> SimpleIndex::GetAllHashes() { 236 return GetEntriesBetween(base::Time(), base::Time()); 237 } 238 239 int32 SimpleIndex::GetEntryCount() const { 240 // TODO(pasko): return a meaningful initial estimate before initialized. 241 return entries_set_.size(); 242 } 243 244 void SimpleIndex::Insert(uint64 entry_hash) { 245 DCHECK(io_thread_checker_.CalledOnValidThread()); 246 // Upon insert we don't know yet the size of the entry. 247 // It will be updated later when the SimpleEntryImpl finishes opening or 248 // creating the new entry, and then UpdateEntrySize will be called. 249 InsertInEntrySet( 250 entry_hash, EntryMetadata(base::Time::Now(), 0), &entries_set_); 251 if (!initialized_) 252 removed_entries_.erase(entry_hash); 253 PostponeWritingToDisk(); 254 } 255 256 void SimpleIndex::Remove(uint64 entry_hash) { 257 DCHECK(io_thread_checker_.CalledOnValidThread()); 258 EntrySet::iterator it = entries_set_.find(entry_hash); 259 if (it != entries_set_.end()) { 260 UpdateEntryIteratorSize(&it, 0); 261 entries_set_.erase(it); 262 } 263 264 if (!initialized_) 265 removed_entries_.insert(entry_hash); 266 PostponeWritingToDisk(); 267 } 268 269 bool SimpleIndex::Has(uint64 hash) const { 270 DCHECK(io_thread_checker_.CalledOnValidThread()); 271 // If not initialized, always return true, forcing it to go to the disk. 272 return !initialized_ || entries_set_.count(hash) > 0; 273 } 274 275 bool SimpleIndex::UseIfExists(uint64 entry_hash) { 276 DCHECK(io_thread_checker_.CalledOnValidThread()); 277 // Always update the last used time, even if it is during initialization. 278 // It will be merged later. 279 EntrySet::iterator it = entries_set_.find(entry_hash); 280 if (it == entries_set_.end()) 281 // If not initialized, always return true, forcing it to go to the disk. 282 return !initialized_; 283 it->second.SetLastUsedTime(base::Time::Now()); 284 PostponeWritingToDisk(); 285 return true; 286 } 287 288 void SimpleIndex::StartEvictionIfNeeded() { 289 DCHECK(io_thread_checker_.CalledOnValidThread()); 290 if (eviction_in_progress_ || cache_size_ <= high_watermark_) 291 return; 292 // Take all live key hashes from the index and sort them by time. 293 eviction_in_progress_ = true; 294 eviction_start_time_ = base::TimeTicks::Now(); 295 SIMPLE_CACHE_UMA(MEMORY_KB, 296 "Eviction.CacheSizeOnStart2", cache_type_, 297 cache_size_ / kBytesInKb); 298 SIMPLE_CACHE_UMA(MEMORY_KB, 299 "Eviction.MaxCacheSizeOnStart2", cache_type_, 300 max_size_ / kBytesInKb); 301 std::vector<uint64> entry_hashes; 302 entry_hashes.reserve(entries_set_.size()); 303 for (EntrySet::const_iterator it = entries_set_.begin(), 304 end = entries_set_.end(); it != end; ++it) { 305 entry_hashes.push_back(it->first); 306 } 307 std::sort(entry_hashes.begin(), entry_hashes.end(), 308 CompareHashesForTimestamp(entries_set_)); 309 310 // Remove as many entries from the index to get below |low_watermark_|. 311 std::vector<uint64>::iterator it = entry_hashes.begin(); 312 uint64 evicted_so_far_size = 0; 313 while (evicted_so_far_size < cache_size_ - low_watermark_) { 314 DCHECK(it != entry_hashes.end()); 315 EntrySet::iterator found_meta = entries_set_.find(*it); 316 DCHECK(found_meta != entries_set_.end()); 317 uint64 to_evict_size = found_meta->second.GetEntrySize(); 318 evicted_so_far_size += to_evict_size; 319 ++it; 320 } 321 322 // Take out the rest of hashes from the eviction list. 323 entry_hashes.erase(it, entry_hashes.end()); 324 SIMPLE_CACHE_UMA(COUNTS, 325 "Eviction.EntryCount", cache_type_, entry_hashes.size()); 326 SIMPLE_CACHE_UMA(TIMES, 327 "Eviction.TimeToSelectEntries", cache_type_, 328 base::TimeTicks::Now() - eviction_start_time_); 329 SIMPLE_CACHE_UMA(MEMORY_KB, 330 "Eviction.SizeOfEvicted2", cache_type_, 331 evicted_so_far_size / kBytesInKb); 332 333 delegate_->DoomEntries(&entry_hashes, base::Bind(&SimpleIndex::EvictionDone, 334 AsWeakPtr())); 335 } 336 337 bool SimpleIndex::UpdateEntrySize(uint64 entry_hash, int entry_size) { 338 DCHECK(io_thread_checker_.CalledOnValidThread()); 339 EntrySet::iterator it = entries_set_.find(entry_hash); 340 if (it == entries_set_.end()) 341 return false; 342 343 UpdateEntryIteratorSize(&it, entry_size); 344 PostponeWritingToDisk(); 345 StartEvictionIfNeeded(); 346 return true; 347 } 348 349 void SimpleIndex::EvictionDone(int result) { 350 DCHECK(io_thread_checker_.CalledOnValidThread()); 351 352 // Ignore the result of eviction. We did our best. 353 eviction_in_progress_ = false; 354 SIMPLE_CACHE_UMA(BOOLEAN, "Eviction.Result", cache_type_, result == net::OK); 355 SIMPLE_CACHE_UMA(TIMES, 356 "Eviction.TimeToDone", cache_type_, 357 base::TimeTicks::Now() - eviction_start_time_); 358 SIMPLE_CACHE_UMA(MEMORY_KB, 359 "Eviction.SizeWhenDone2", cache_type_, 360 cache_size_ / kBytesInKb); 361 } 362 363 // static 364 void SimpleIndex::InsertInEntrySet( 365 uint64 entry_hash, 366 const disk_cache::EntryMetadata& entry_metadata, 367 EntrySet* entry_set) { 368 DCHECK(entry_set); 369 entry_set->insert(std::make_pair(entry_hash, entry_metadata)); 370 } 371 372 void SimpleIndex::PostponeWritingToDisk() { 373 if (!initialized_) 374 return; 375 const int delay = app_on_background_ ? kWriteToDiskOnBackgroundDelayMSecs 376 : kWriteToDiskDelayMSecs; 377 // If the timer is already active, Start() will just Reset it, postponing it. 378 write_to_disk_timer_.Start( 379 FROM_HERE, base::TimeDelta::FromMilliseconds(delay), write_to_disk_cb_); 380 } 381 382 void SimpleIndex::UpdateEntryIteratorSize(EntrySet::iterator* it, 383 int entry_size) { 384 // Update the total cache size with the new entry size. 385 DCHECK(io_thread_checker_.CalledOnValidThread()); 386 DCHECK_GE(cache_size_, implicit_cast<uint64>((*it)->second.GetEntrySize())); 387 cache_size_ -= (*it)->second.GetEntrySize(); 388 cache_size_ += entry_size; 389 (*it)->second.SetEntrySize(entry_size); 390 } 391 392 void SimpleIndex::MergeInitializingSet( 393 scoped_ptr<SimpleIndexLoadResult> load_result) { 394 DCHECK(io_thread_checker_.CalledOnValidThread()); 395 DCHECK(load_result->did_load); 396 397 EntrySet* index_file_entries = &load_result->entries; 398 399 for (base::hash_set<uint64>::const_iterator it = removed_entries_.begin(); 400 it != removed_entries_.end(); ++it) { 401 index_file_entries->erase(*it); 402 } 403 removed_entries_.clear(); 404 405 for (EntrySet::const_iterator it = entries_set_.begin(); 406 it != entries_set_.end(); ++it) { 407 const uint64 entry_hash = it->first; 408 std::pair<EntrySet::iterator, bool> insert_result = 409 index_file_entries->insert(EntrySet::value_type(entry_hash, 410 EntryMetadata())); 411 EntrySet::iterator& possibly_inserted_entry = insert_result.first; 412 possibly_inserted_entry->second = it->second; 413 } 414 415 uint64 merged_cache_size = 0; 416 for (EntrySet::iterator it = index_file_entries->begin(); 417 it != index_file_entries->end(); ++it) { 418 merged_cache_size += it->second.GetEntrySize(); 419 } 420 421 entries_set_.swap(*index_file_entries); 422 cache_size_ = merged_cache_size; 423 initialized_ = true; 424 425 // The actual IO is asynchronous, so calling WriteToDisk() shouldn't slow the 426 // merge down much. 427 if (load_result->flush_required) 428 WriteToDisk(); 429 430 SIMPLE_CACHE_UMA(CUSTOM_COUNTS, 431 "IndexInitializationWaiters", cache_type_, 432 to_run_when_initialized_.size(), 0, 100, 20); 433 // Run all callbacks waiting for the index to come up. 434 for (CallbackList::iterator it = to_run_when_initialized_.begin(), 435 end = to_run_when_initialized_.end(); it != end; ++it) { 436 io_thread_->PostTask(FROM_HERE, base::Bind((*it), net::OK)); 437 } 438 to_run_when_initialized_.clear(); 439 } 440 441 #if defined(OS_ANDROID) 442 void SimpleIndex::OnApplicationStateChange( 443 base::android::ApplicationState state) { 444 DCHECK(io_thread_checker_.CalledOnValidThread()); 445 // For more info about android activities, see: 446 // developer.android.com/training/basics/activity-lifecycle/pausing.html 447 if (state == base::android::APPLICATION_STATE_HAS_RUNNING_ACTIVITIES) { 448 app_on_background_ = false; 449 } else if (state == 450 base::android::APPLICATION_STATE_HAS_STOPPED_ACTIVITIES) { 451 app_on_background_ = true; 452 WriteToDisk(); 453 } 454 } 455 #endif 456 457 void SimpleIndex::WriteToDisk() { 458 DCHECK(io_thread_checker_.CalledOnValidThread()); 459 if (!initialized_) 460 return; 461 SIMPLE_CACHE_UMA(CUSTOM_COUNTS, 462 "IndexNumEntriesOnWrite", cache_type_, 463 entries_set_.size(), 0, 100000, 50); 464 const base::TimeTicks start = base::TimeTicks::Now(); 465 if (!last_write_to_disk_.is_null()) { 466 if (app_on_background_) { 467 SIMPLE_CACHE_UMA(MEDIUM_TIMES, 468 "IndexWriteInterval.Background", cache_type_, 469 start - last_write_to_disk_); 470 } else { 471 SIMPLE_CACHE_UMA(MEDIUM_TIMES, 472 "IndexWriteInterval.Foreground", cache_type_, 473 start - last_write_to_disk_); 474 } 475 } 476 last_write_to_disk_ = start; 477 478 index_file_->WriteToDisk(entries_set_, cache_size_, 479 start, app_on_background_); 480 } 481 482 } // namespace disk_cache 483
