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