121d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen// Copyright (c) 2010 The Chromium Authors. All rights reserved. 2c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// found in the LICENSE file. 4c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 521d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen#include "chrome/browser/visitedlink/visitedlink_master.h" 6c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 7c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#if defined(OS_WIN) 8c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include <windows.h> 9c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include <io.h> 10c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include <shlobj.h> 11c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif // defined(OS_WIN) 12c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include <stdio.h> 13c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 14c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include <algorithm> 15c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 16c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/file_util.h" 17c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/logging.h" 18c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/message_loop.h" 19c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/path_service.h" 20c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/process_util.h" 21c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/rand_util.h" 22c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/stack_container.h" 23c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/string_util.h" 243f50c38dc070f4bb515c1b64450dae14f316474eKristian Monsen#include "base/threading/thread_restrictions.h" 25dc0f95d653279beabeb9817299e2902918ba123eKristian Monsen#include "content/browser/browser_thread.h" 26c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "chrome/browser/history/history.h" 2721d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen#include "chrome/browser/profiles/profile.h" 28c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 29c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochusing file_util::ScopedFILE; 30c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochusing file_util::OpenFile; 31c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochusing file_util::TruncateFile; 32c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 33c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int32 VisitedLinkMaster::kFileHeaderSignatureOffset = 0; 34c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int32 VisitedLinkMaster::kFileHeaderVersionOffset = 4; 35c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int32 VisitedLinkMaster::kFileHeaderLengthOffset = 8; 36c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int32 VisitedLinkMaster::kFileHeaderUsedOffset = 12; 37c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int32 VisitedLinkMaster::kFileHeaderSaltOffset = 16; 38c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 39c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int32 VisitedLinkMaster::kFileCurrentVersion = 2; 40c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 41c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// the signature at the beginning of the URL table = "VLnk" (visited links) 42c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int32 VisitedLinkMaster::kFileSignature = 0x6b6e4c56; 43c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst size_t VisitedLinkMaster::kFileHeaderSize = 44c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch kFileHeaderSaltOffset + LINK_SALT_LENGTH; 45c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 46c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// This value should also be the same as the smallest size in the lookup 47c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// table in NewTableSizeForCount (prime number). 48c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst unsigned VisitedLinkMaster::kDefaultTableSize = 16381; 49c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 50c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst size_t VisitedLinkMaster::kBigDeleteThreshold = 64; 51c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 52c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochnamespace { 53c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 54c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Fills the given salt structure with some quasi-random values 55c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// It is not necessary to generate a cryptographically strong random string, 56c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// only that it be reasonably different for different users. 57c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid GenerateSalt(uint8 salt[LINK_SALT_LENGTH]) { 58c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK_EQ(LINK_SALT_LENGTH, 8) << "This code assumes the length of the salt"; 59c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch uint64 randval = base::RandUint64(); 60c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(salt, &randval, 8); 61c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 62c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 63c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// AsyncWriter ---------------------------------------------------------------- 64c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 65c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// This task executes on a background thread and executes a write. This 66c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// prevents us from blocking the UI thread doing I/O. 67c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass AsyncWriter : public Task { 68c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch public: 69c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch AsyncWriter(FILE* file, int32 offset, const void* data, size_t data_len) 70c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch : file_(file), 71c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch offset_(offset) { 72c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch data_->resize(data_len); 73c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(&*data_->begin(), data, data_len); 74c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 75c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 76c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch virtual void Run() { 77c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, offset_, 78c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch &*data_->begin(), static_cast<int32>(data_->size())); 79c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 80c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 81c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Exposed as a static so it can be called directly from the Master to 82c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // reduce the number of platform-specific I/O sites we have. Returns true if 83c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // the write was complete. 84c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch static bool WriteToFile(FILE* file, 85c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch off_t offset, 86c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const void* data, 87c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch size_t data_len) { 88c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (fseek(file, offset, SEEK_SET) != 0) 89c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // Don't write to an invalid part of the file. 90c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 91c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch size_t num_written = fwrite(data, 1, data_len, file); 92c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 93c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // The write may not make it to the kernel (stdlib may buffer the write) 94c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // until the next fseek/fclose call. If we crash, it's easy for our used 95c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // item count to be out of sync with the number of hashes we write. 96c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Protect against this by calling fflush. 97c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int ret = fflush(file); 98c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK_EQ(0, ret); 99c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return num_written == data_len; 100c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 101c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 102c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch private: 103c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // The data to write and where to write it. 104c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FILE* file_; 105c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 offset_; // Offset from the beginning of the file. 106c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 107c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Most writes are just a single fingerprint, so we reserve that much in this 108c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // object to avoid mallocs in that case. 109c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch StackVector<char, sizeof(VisitedLinkCommon::Fingerprint)> data_; 110c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 111c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DISALLOW_COPY_AND_ASSIGN(AsyncWriter); 112c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch}; 113c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 114c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Used to asynchronously set the end of the file. This must be done on the 115c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// same thread as the writing to keep things synchronized. 116c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass AsyncSetEndOfFile : public Task { 117c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch public: 118c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch explicit AsyncSetEndOfFile(FILE* file) : file_(file) {} 119c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 120c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch virtual void Run() { 121c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TruncateFile(file_); 122c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 123c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 124c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch private: 125c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FILE* file_; 126c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DISALLOW_COPY_AND_ASSIGN(AsyncSetEndOfFile); 127c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch}; 128c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 129c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Used to asynchronously close a file. This must be done on the same thread as 130c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// the writing to keep things synchronized. 131c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass AsyncCloseHandle : public Task { 132c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch public: 133c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch explicit AsyncCloseHandle(FILE* file) : file_(file) {} 134c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 135c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch virtual void Run() { 136c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch fclose(file_); 137c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 138c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 139c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch private: 140c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FILE* file_; 141c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DISALLOW_COPY_AND_ASSIGN(AsyncCloseHandle); 142c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch}; 143c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 144c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} // namespace 145c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 146c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// TableBuilder --------------------------------------------------------------- 147c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 148c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// How rebuilding from history works 149c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// --------------------------------- 150c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 151c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// We mark that we're rebuilding from history by setting the table_builder_ 152c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// member in VisitedLinkMaster to the TableBuilder we create. This builder 153c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// will be called on the history thread by the history system for every URL 154c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// in the database. 155c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 156c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// The builder will store the fingerprints for those URLs, and then marshalls 157c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// back to the main thread where the VisitedLinkMaster will be notified. The 158c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// master then replaces its table with a new table containing the computed 159c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// fingerprints. 160c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 161c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// The builder must remain active while the history system is using it. 162c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Sometimes, the master will be deleted before the rebuild is complete, in 163c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// which case it notifies the builder via DisownMaster(). The builder will 164c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// delete itself once rebuilding is complete, and not execute any callback. 165c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass VisitedLinkMaster::TableBuilder 166c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch : public HistoryService::URLEnumerator, 167c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch public base::RefCountedThreadSafe<TableBuilder> { 168c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch public: 169c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TableBuilder(VisitedLinkMaster* master, 170c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const uint8 salt[LINK_SALT_LENGTH]); 171c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 172c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Called on the main thread when the master is being destroyed. This will 173c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // prevent a crash when the query completes and the master is no longer 174c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // around. We can not actually do anything but mark this fact, since the 175c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // table will be being rebuilt simultaneously on the other thread. 176c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch void DisownMaster(); 177c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 178c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // HistoryService::URLEnumerator 179c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch virtual void OnURL(const GURL& url); 180c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch virtual void OnComplete(bool succeed); 181c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 182c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch private: 183c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch friend class base::RefCountedThreadSafe<TableBuilder>; 184c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 185c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ~TableBuilder() {} 186c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 187c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // OnComplete mashals to this function on the main thread to do the 188c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // notification. 189c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch void OnCompleteMainThread(); 190c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 191c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Owner of this object. MAY ONLY BE ACCESSED ON THE MAIN THREAD! 192c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch VisitedLinkMaster* master_; 193c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 194c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Indicates whether the operation has failed or not. 195c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool success_; 196c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 197c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Salt for this new table. 198c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch uint8 salt_[LINK_SALT_LENGTH]; 199c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 200c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Stores the fingerprints we computed on the background thread. 201c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch VisitedLinkCommon::Fingerprints fingerprints_; 202c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch}; 203c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 204c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// VisitedLinkMaster ---------------------------------------------------------- 205c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 206c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochVisitedLinkMaster::VisitedLinkMaster(Listener* listener, 207c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Profile* profile) { 208c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch InitMembers(listener, profile); 209c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 210c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 211c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochVisitedLinkMaster::VisitedLinkMaster(Listener* listener, 212c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch HistoryService* history_service, 213c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool suppress_rebuild, 214c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const FilePath& filename, 215c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 default_table_size) { 216c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch InitMembers(listener, NULL); 217c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 218c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch database_name_override_ = filename; 219c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_size_override_ = default_table_size; 220c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch history_service_override_ = history_service; 221c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch suppress_rebuild_ = suppress_rebuild; 222c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 223c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 224c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochVisitedLinkMaster::~VisitedLinkMaster() { 225c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (table_builder_.get()) { 226c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Prevent the table builder from calling us back now that we're being 227c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // destroyed. Note that we DON'T delete the object, since the history 228c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // system is still writing into it. When that is complete, the table 229c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // builder will destroy itself when it finds we are gone. 230c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_builder_->DisownMaster(); 231c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 232c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FreeURLTable(); 233c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 234c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 235c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::InitMembers(Listener* listener, Profile* profile) { 236c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(listener); 237c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 238c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch listener_ = listener; 239c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch file_ = NULL; 240c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_ = NULL; 241c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_serial_ = 0; 242c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch used_items_ = 0; 243c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_size_override_ = 0; 244c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch history_service_override_ = NULL; 245c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch suppress_rebuild_ = false; 246c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch profile_ = profile; 247c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 248c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 249c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch posted_asynchronous_operation_ = false; 250c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 251c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 252c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 253c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::Init() { 254513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch // We probably shouldn't be loading this from the UI thread, 255513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch // but it does need to happen early on in startup. 256513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch // http://code.google.com/p/chromium/issues/detail?id=24163 257513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch base::ThreadRestrictions::ScopedAllowIO allow_io; 258c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!InitFromFile()) 259c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return InitFromScratch(suppress_rebuild_); 260c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 261c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 262c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 263c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochVisitedLinkMaster::Hash VisitedLinkMaster::TryToAddURL(const GURL& url) { 264ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen // Extra check that we are not incognito. This should not happen. 265c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (profile_ && profile_->IsOffTheRecord()) { 266c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch NOTREACHED(); 267c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return null_hash_; 268c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 269c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 270c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!url.is_valid()) 271c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return null_hash_; // Don't add invalid URLs. 272c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 273c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Fingerprint fingerprint = ComputeURLFingerprint(url.spec().data(), 274c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch url.spec().size(), 275c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch salt_); 276c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (table_builder_) { 277c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // If we have a pending delete for this fingerprint, cancel it. 278c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::set<Fingerprint>::iterator found = 279c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch deleted_since_rebuild_.find(fingerprint); 280c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (found != deleted_since_rebuild_.end()) 281c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch deleted_since_rebuild_.erase(found); 282c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 283c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // A rebuild is in progress, save this addition in the temporary list so 284c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // it can be added once rebuild is complete. 285c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch added_since_rebuild_.insert(fingerprint); 286c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 287c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 288c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // If the table is "full", we don't add URLs and just drop them on the floor. 289c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This can happen if we get thousands of new URLs and something causes 290c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // the table resizing to fail. This check prevents a hang in that case. Note 291c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // that this is *not* the resize limit, this is just a sanity check. 292c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (used_items_ / 8 > table_length_ / 10) 293c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return null_hash_; // Table is more than 80% full. 294c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 295c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return AddFingerprint(fingerprint, true); 296c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 297c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 298c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::AddURL(const GURL& url) { 299c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash index = TryToAddURL(url); 300c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!table_builder_ && index != null_hash_) { 301c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Not rebuilding, so we want to keep the file on disk up-to-date. 302c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteUsedItemCountToFile(); 303c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteHashRangeToFile(index, index); 304c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ResizeTableIfNecessary(); 305c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 306c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 307c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 308c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::AddURLs(const std::vector<GURL>& url) { 309c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (std::vector<GURL>::const_iterator i = url.begin(); 310c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch i != url.end(); ++i) { 311c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash index = TryToAddURL(*i); 312c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!table_builder_ && index != null_hash_) 313c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ResizeTableIfNecessary(); 314c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 315c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 316c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Keeps the file on disk up-to-date. 317c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!table_builder_) 318c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteFullTable(); 319c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 320c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 321c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::DeleteAllURLs() { 322c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Any pending modifications are invalid. 323c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch added_since_rebuild_.clear(); 324c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch deleted_since_rebuild_.clear(); 325c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 326c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Clear the hash table. 327c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch used_items_ = 0; 328c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memset(hash_table_, 0, this->table_length_ * sizeof(Fingerprint)); 329c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 330c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Resize it if it is now too empty. Resize may write the new table out for 331c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // us, otherwise, schedule writing the new table to disk ourselves. 332c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!ResizeTableIfNecessary()) 333c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteFullTable(); 334c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 335c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch listener_->Reset(); 336c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 337c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 338c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::DeleteURLs(const std::set<GURL>& urls) { 339c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch typedef std::set<GURL>::const_iterator SetIterator; 340c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 341c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (urls.empty()) 342c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; 343c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 344c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch listener_->Reset(); 345c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 346c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (table_builder_) { 347c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // A rebuild is in progress, save this deletion in the temporary list so 348c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // it can be added once rebuild is complete. 349c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (SetIterator i = urls.begin(); i != urls.end(); ++i) { 350c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!i->is_valid()) 351c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch continue; 352c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 353c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Fingerprint fingerprint = 354c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ComputeURLFingerprint(i->spec().data(), i->spec().size(), salt_); 355c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch deleted_since_rebuild_.insert(fingerprint); 356c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 357c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // If the URL was just added and now we're deleting it, it may be in the 358c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // list of things added since the last rebuild. Delete it from that list. 359c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::set<Fingerprint>::iterator found = 360c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch added_since_rebuild_.find(fingerprint); 361c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (found != added_since_rebuild_.end()) 362c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch added_since_rebuild_.erase(found); 363c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 364c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Delete the URLs from the in-memory table, but don't bother writing 365c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // to disk since it will be replaced soon. 366c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DeleteFingerprint(fingerprint, false); 367c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 368c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; 369c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 370c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 371c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Compute the deleted URLs' fingerprints and delete them 372c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::set<Fingerprint> deleted_fingerprints; 373c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (SetIterator i = urls.begin(); i != urls.end(); ++i) { 374c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!i->is_valid()) 375c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch continue; 376c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch deleted_fingerprints.insert( 377c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ComputeURLFingerprint(i->spec().data(), i->spec().size(), salt_)); 378c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 379c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DeleteFingerprintsFromCurrentTable(deleted_fingerprints); 380c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 381c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 382c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// See VisitedLinkCommon::IsVisited which should be in sync with this algorithm 383c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochVisitedLinkMaster::Hash VisitedLinkMaster::AddFingerprint( 384c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Fingerprint fingerprint, 385c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool send_notifications) { 386c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!hash_table_ || table_length_ == 0) { 387c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch NOTREACHED(); // Not initialized. 388c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return null_hash_; 389c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 390c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 391c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash cur_hash = HashFingerprint(fingerprint); 392c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash first_hash = cur_hash; 393c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch while (true) { 394c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Fingerprint cur_fingerprint = FingerprintAt(cur_hash); 395c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (cur_fingerprint == fingerprint) 396c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return null_hash_; // This fingerprint is already in there, do nothing. 397c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 398c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (cur_fingerprint == null_fingerprint_) { 399c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // End of probe sequence found, insert here. 400c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch hash_table_[cur_hash] = fingerprint; 401c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch used_items_++; 402c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // If allowed, notify listener that a new visited link was added. 403c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (send_notifications) 404c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch listener_->Add(fingerprint); 405c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return cur_hash; 406c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 407c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 408c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Advance in the probe sequence. 409c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch cur_hash = IncrementHash(cur_hash); 410c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (cur_hash == first_hash) { 411c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This means that we've wrapped around and are about to go into an 412c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // infinite loop. Something was wrong with the hashtable resizing 413c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // logic, so stop here. 414c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch NOTREACHED(); 415c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return null_hash_; 416c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 417c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 418c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 419c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 420c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::DeleteFingerprintsFromCurrentTable( 421c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const std::set<Fingerprint>& fingerprints) { 422c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool bulk_write = (fingerprints.size() > kBigDeleteThreshold); 423c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 424c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Delete the URLs from the table. 425c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (std::set<Fingerprint>::const_iterator i = fingerprints.begin(); 426c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch i != fingerprints.end(); ++i) 427c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DeleteFingerprint(*i, !bulk_write); 428c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 429c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // These deleted fingerprints may make us shrink the table. 430c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (ResizeTableIfNecessary()) 431c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; // The resize function wrote the new table to disk for us. 432c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 433c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Nobody wrote this out for us, write the full file to disk. 434c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (bulk_write) 435c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteFullTable(); 436c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 437c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 438c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::DeleteFingerprint(Fingerprint fingerprint, 439c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool update_file) { 440c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!hash_table_ || table_length_ == 0) { 441c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch NOTREACHED(); // Not initialized. 442c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 443c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 444c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!IsVisited(fingerprint)) 445c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // Not in the database to delete. 446c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 447c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // First update the header used count. 448c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch used_items_--; 449c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (update_file) 450c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteUsedItemCountToFile(); 451c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 452c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash deleted_hash = HashFingerprint(fingerprint); 453c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 454c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Find the range of "stuff" in the hash table that is adjacent to this 455c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // fingerprint. These are things that could be affected by the change in 456c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // the hash table. Since we use linear probing, anything after the deleted 457c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // item up until an empty item could be affected. 458c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash end_range = deleted_hash; 459c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch while (true) { 460c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash next_hash = IncrementHash(end_range); 461c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (next_hash == deleted_hash) 462c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch break; // We wrapped around and the whole table is full. 463c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!hash_table_[next_hash]) 464c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch break; // Found the last spot. 465c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch end_range = next_hash; 466c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 467c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 468c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // We could get all fancy and move the affected fingerprints around, but 469c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // instead we just remove them all and re-add them (minus our deleted one). 470c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This will mean there's a small window of time where the affected links 471c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // won't be marked visited. 472c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch StackVector<Fingerprint, 32> shuffled_fingerprints; 473c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Hash stop_loop = IncrementHash(end_range); // The end range is inclusive. 474c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (Hash i = deleted_hash; i != stop_loop; i = IncrementHash(i)) { 475c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (hash_table_[i] != fingerprint) { 476c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Don't save the one we're deleting! 477c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shuffled_fingerprints->push_back(hash_table_[i]); 478c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 479c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This will balance the increment of this value in AddFingerprint below 480c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // so there is no net change. 481c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch used_items_--; 482c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 483c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch hash_table_[i] = null_fingerprint_; 484c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 485c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 486c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!shuffled_fingerprints->empty()) { 487c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Need to add the new items back. 488c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (size_t i = 0; i < shuffled_fingerprints->size(); i++) 489c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch AddFingerprint(shuffled_fingerprints[i], false); 490c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 491c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 492c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Write the affected range to disk [deleted_hash, end_range]. 493c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (update_file) 494c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteHashRangeToFile(deleted_hash, end_range); 495c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 496c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 497c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 498c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 499c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::WriteFullTable() { 500c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This function can get called when the file is open, for example, when we 501c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // resize the table. We must handle this case and not try to reopen the file, 502c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // since there may be write operations pending on the file I/O thread. 503c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // 504c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Note that once we start writing, we do not delete on error. This means 505c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // there can be a partial file, but the short file will be detected next time 506c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // we start, and will be replaced. 507c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // 508c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This might possibly get corrupted if we crash in the middle of writing. 509c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // We should pick up the most common types of these failures when we notice 510c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // that the file size is different when we load it back in, and then we will 511c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // regenerate the table. 512c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!file_) { 513c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FilePath filename; 514c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch GetDatabaseFileName(&filename); 515c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch file_ = OpenFile(filename, "wb+"); 516c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!file_) { 517c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DLOG(ERROR) << "Failed to open file " << filename.value(); 518c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 519c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 520c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 521c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 522c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Write the new header. 523c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 header[4]; 524c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch header[0] = kFileSignature; 525c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch header[1] = kFileCurrentVersion; 526c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch header[2] = table_length_; 527c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch header[3] = used_items_; 528c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, 0, header, sizeof(header)); 529c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, sizeof(header), salt_, LINK_SALT_LENGTH); 530c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 531c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Write the hash data. 532c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, kFileHeaderSize, 533c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch hash_table_, table_length_ * sizeof(Fingerprint)); 534c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 535c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // The hash table may have shrunk, so make sure this is the end. 536731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::PostTask( 537731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::FILE, FROM_HERE, new AsyncSetEndOfFile(file_)); 538c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 539c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 540c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 541c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::InitFromFile() { 542c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(file_ == NULL); 543c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 544c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FilePath filename; 545c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch GetDatabaseFileName(&filename); 546c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ScopedFILE file_closer(OpenFile(filename, "rb+")); 547c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!file_closer.get()) 548c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 549c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 550c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 num_entries, used_count; 551c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!ReadFileHeader(file_closer.get(), &num_entries, &used_count, salt_)) 552c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // Header isn't valid. 553c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 554c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Allocate and read the table. 555c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!CreateURLTable(num_entries, false)) 556c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 557c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!ReadFromFile(file_closer.get(), kFileHeaderSize, 558c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch hash_table_, num_entries * sizeof(Fingerprint))) { 559c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FreeURLTable(); 560c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 561c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 562c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch used_items_ = used_count; 563c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 564c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 565c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DebugValidate(); 566c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 567c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 568c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch file_ = file_closer.release(); 569c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 570c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 571c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 572c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::InitFromScratch(bool suppress_rebuild) { 573c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 table_size = kDefaultTableSize; 574c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (table_size_override_) 575c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_size = table_size_override_; 576c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 577c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // The salt must be generated before the table so that it can be copied to 578c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // the shared memory. 579c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch GenerateSalt(salt_); 580c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!CreateURLTable(table_size, true)) 581c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 582c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 583c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 584c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DebugValidate(); 585c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 586c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 587c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (suppress_rebuild) { 588c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // When we disallow rebuilds (normally just unit tests), just use the 589c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // current empty table. 590c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return WriteFullTable(); 591c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 592c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 593c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This will build the table from history. On the first run, history will 594c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // be empty, so this will be correct. This will also write the new table 595c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // to disk. We don't want to save explicitly here, since the rebuild may 596c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // not complete, leaving us with an empty but valid visited link database. 597c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // In the future, we won't know we need to try rebuilding again. 598c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return RebuildTableFromHistory(); 599c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 600c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 601c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::ReadFileHeader(FILE* file, 602c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32* num_entries, 603c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32* used_count, 604c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch uint8 salt[LINK_SALT_LENGTH]) { 605c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Get file size. 606c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Note that there is no need to seek back to the original location in the 607c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // file since ReadFromFile() [which is the next call accessing the file] 608c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // seeks before reading. 609c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (fseek(file, 0, SEEK_END) == -1) 610c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 611c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch size_t file_size = ftell(file); 612c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 613c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (file_size <= kFileHeaderSize) 614c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 615c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 616c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch uint8 header[kFileHeaderSize]; 617c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!ReadFromFile(file, 0, &header, kFileHeaderSize)) 618c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 619c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 620c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Verify the signature. 621c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 signature; 622c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(&signature, &header[kFileHeaderSignatureOffset], sizeof(signature)); 623c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (signature != kFileSignature) 624c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 625c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 626c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Verify the version is up-to-date. As with other read errors, a version 627c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // mistmatch will trigger a rebuild of the database from history, which will 628c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // have the effect of migrating the database. 629c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 version; 630c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(&version, &header[kFileHeaderVersionOffset], sizeof(version)); 631c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (version != kFileCurrentVersion) 632c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // Bad version. 633c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 634c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Read the table size and make sure it matches the file size. 635c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(num_entries, &header[kFileHeaderLengthOffset], sizeof(*num_entries)); 636c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (*num_entries * sizeof(Fingerprint) + kFileHeaderSize != file_size) 637c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // Bad size. 638c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 639c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Read the used item count. 640c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(used_count, &header[kFileHeaderUsedOffset], sizeof(*used_count)); 641c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (*used_count > *num_entries) 642c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // Bad used item count; 643c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 644c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Read the salt. 645c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(salt, &header[kFileHeaderSaltOffset], LINK_SALT_LENGTH); 646c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 647c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This file looks OK from the header's perspective. 648c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 649c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 650c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 651c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::GetDatabaseFileName(FilePath* filename) { 652c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!database_name_override_.empty()) { 653c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // use this filename, the directory must exist 654c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch *filename = database_name_override_; 655c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 656c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 657c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 658c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!profile_ || profile_->GetPath().empty()) 659c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 660c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 661c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FilePath profile_dir = profile_->GetPath(); 662c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch *filename = profile_dir.Append(FILE_PATH_LITERAL("Visited Links")); 663c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 664c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 665c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 666c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Initializes the shared memory structure. The salt should already be filled 667c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// in so that it can be written to the shared memory 668c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::CreateURLTable(int32 num_entries, bool init_to_empty) { 669c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // The table is the size of the table followed by the entries. 670c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch uint32 alloc_size = num_entries * sizeof(Fingerprint) + sizeof(SharedHeader); 671c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 672c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Create the shared memory object. 673c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_ = new base::SharedMemory(); 674c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!shared_memory_) 675c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 676c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 677513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch if (!shared_memory_->CreateAndMapAnonymous(alloc_size)) { 678c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch delete shared_memory_; 679c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_ = NULL; 680c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 681c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 682c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 683c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (init_to_empty) { 684c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memset(shared_memory_->memory(), 0, alloc_size); 685c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch used_items_ = 0; 686c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 687c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_length_ = num_entries; 688c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 689c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Save the header for other processes to read. 690c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SharedHeader* header = static_cast<SharedHeader*>(shared_memory_->memory()); 691c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch header->length = table_length_; 692c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(header->salt, salt_, LINK_SALT_LENGTH); 693c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 694c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Our table pointer is just the data immediately following the size. 695c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch hash_table_ = reinterpret_cast<Fingerprint*>( 696c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch static_cast<char*>(shared_memory_->memory()) + sizeof(SharedHeader)); 697c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 698c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 699c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 700c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 701c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::BeginReplaceURLTable(int32 num_entries) { 702c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch base::SharedMemory *old_shared_memory = shared_memory_; 703c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Fingerprint* old_hash_table = hash_table_; 704c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 old_table_length = table_length_; 705c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!CreateURLTable(num_entries, true)) { 706c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Try to put back the old state. 707c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_ = old_shared_memory; 708c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch hash_table_ = old_hash_table; 709c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_length_ = old_table_length; 710c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 711c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 712c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 713c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 714c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DebugValidate(); 715c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 716c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 717c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 718c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 719c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 720c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::FreeURLTable() { 721c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (shared_memory_) { 722c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch delete shared_memory_; 723c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_ = NULL; 724c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 725c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!file_) 726c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; 727c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 728731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::PostTask( 729731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::FILE, FROM_HERE, new AsyncCloseHandle(file_)); 730c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 731c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 732c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::ResizeTableIfNecessary() { 733c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(table_length_ > 0) << "Must have a table"; 734c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 735c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Load limits for good performance/space. We are pretty conservative about 736c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // keeping the table not very full. This is because we use linear probing 737c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // which increases the likelihood of clumps of entries which will reduce 738c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // performance. 739c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const float max_table_load = 0.5f; // Grow when we're > this full. 740c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const float min_table_load = 0.2f; // Shrink when we're < this full. 741c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 742c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch float load = ComputeTableLoad(); 743c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (load < max_table_load && 744c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch (table_length_ <= static_cast<float>(kDefaultTableSize) || 745c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch load > min_table_load)) 746c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 747c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 748c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Table needs to grow or shrink. 749c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int new_size = NewTableSizeForCount(used_items_); 750c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(new_size > used_items_); 751c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(load <= min_table_load || new_size > table_length_); 752c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ResizeTable(new_size); 753c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 754c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 755c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 756c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::ResizeTable(int32 new_size) { 757c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(shared_memory_ && shared_memory_->memory() && hash_table_); 758c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_serial_++; 759c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 760c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 761c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DebugValidate(); 762c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 763c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 764c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch base::SharedMemory* old_shared_memory = shared_memory_; 765c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Fingerprint* old_hash_table = hash_table_; 766c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 old_table_length = table_length_; 767c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!BeginReplaceURLTable(new_size)) 768c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; 769c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 770c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Now we have two tables, our local copy which is the old one, and the new 771c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // one loaded into this object where we need to copy the data. 772c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (int32 i = 0; i < old_table_length; i++) { 773c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Fingerprint cur = old_hash_table[i]; 774c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (cur) 775c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch AddFingerprint(cur, false); 776c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 777c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 778c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // On error unmapping, just forget about it since we can't do anything 779c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // else to release it. 780c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch delete old_shared_memory; 781c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 782c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Send an update notification to all child processes so they read the new 783c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // table. 784c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch listener_->NewTable(shared_memory_); 785c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 786c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 787c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DebugValidate(); 788c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 789c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 790c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // The new table needs to be written to disk. 791c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteFullTable(); 792c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 793c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 794c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochuint32 VisitedLinkMaster::NewTableSizeForCount(int32 item_count) const { 795c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // These table sizes are selected to be the maximum prime number less than 796c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // a "convenient" multiple of 1K. 797c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch static const int table_sizes[] = { 798c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 16381, // 16K = 16384 <- don't shrink below this table size 799c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // (should be == default_table_size) 800c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 32767, // 32K = 32768 801c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 65521, // 64K = 65536 802c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 130051, // 128K = 131072 803c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 262127, // 256K = 262144 804c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 524269, // 512K = 524288 805c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 1048549, // 1M = 1048576 806c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 2097143, // 2M = 2097152 807c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 4194301, // 4M = 4194304 808c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 8388571, // 8M = 8388608 809c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 16777199, // 16M = 16777216 810c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 33554347}; // 32M = 33554432 811c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 812c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Try to leave the table 33% full. 813c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int desired = item_count * 3; 814c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 815c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Find the closest prime. 816c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (size_t i = 0; i < arraysize(table_sizes); i ++) { 817c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (table_sizes[i] > desired) 818c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return table_sizes[i]; 819c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 820c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 821c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Growing very big, just approximate a "good" number, not growing as much 822c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // as normal. 823c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return item_count * 2 - 1; 824c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 825c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 826c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// See the TableBuilder definition in the header file for how this works. 827c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::RebuildTableFromHistory() { 828c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(!table_builder_); 829c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (table_builder_) 830c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 831c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 832c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch HistoryService* history_service = history_service_override_; 833c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!history_service && profile_) { 834c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch history_service = profile_->GetHistoryService(Profile::EXPLICIT_ACCESS); 835c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 836c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 837c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!history_service) { 838c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DLOG(WARNING) << "Attempted to rebuild visited link table, but couldn't " 839c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch "obtain a HistoryService."; 840c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 841c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 842c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 843c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // TODO(brettw) make sure we have reasonable salt! 844c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_builder_ = new TableBuilder(this, salt_); 845c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 846c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Make sure the table builder stays live during the call, even if the 847c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // master is deleted. This is balanced in TableBuilder::OnCompleteMainThread. 848c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_builder_->AddRef(); 849c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch history_service->IterateURLs(table_builder_); 850c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 851c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 852c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 853c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// See the TableBuilder declaration above for how this works. 854c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::OnTableRebuildComplete( 855c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool success, 856c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const std::vector<Fingerprint>& fingerprints) { 857c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (success) { 858c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Replace the old table with a new blank one. 859c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch shared_memory_serial_++; 860c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 861c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // We are responsible for freeing it AFTER it has been replaced if 862c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // replacement succeeds. 863c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch base::SharedMemory* old_shared_memory = shared_memory_; 864c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 865c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int new_table_size = NewTableSizeForCount( 866c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch static_cast<int>(fingerprints.size() + added_since_rebuild_.size())); 867c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (BeginReplaceURLTable(new_table_size)) { 868c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Free the old table. 869c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch delete old_shared_memory; 870c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 871c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Add the stored fingerprints to the hash table. 872c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (size_t i = 0; i < fingerprints.size(); i++) 873c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch AddFingerprint(fingerprints[i], false); 874c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 875c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Also add anything that was added while we were asynchronously 876c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // generating the new table. 877c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (std::set<Fingerprint>::iterator i = added_since_rebuild_.begin(); 878c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch i != added_since_rebuild_.end(); ++i) 879c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch AddFingerprint(*i, false); 880c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch added_since_rebuild_.clear(); 881c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 882c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Now handle deletions. 883c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DeleteFingerprintsFromCurrentTable(deleted_since_rebuild_); 884c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch deleted_since_rebuild_.clear(); 885c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 886c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Send an update notification to all child processes. 887c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch listener_->NewTable(shared_memory_); 888c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 889513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch // We shouldn't be writing the table from the main thread! 890513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch // http://code.google.com/p/chromium/issues/detail?id=24163 891513209b27ff55e2841eac0e4120199c23acce758Ben Murdoch base::ThreadRestrictions::ScopedAllowIO allow_io; 892c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteFullTable(); 893c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 894c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 895c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch table_builder_ = NULL; // Will release our reference to the builder. 896c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 897c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Notify the unit test that the rebuild is complete (will be NULL in prod.) 898c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (rebuild_complete_task_.get()) { 899c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch rebuild_complete_task_->Run(); 900c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch rebuild_complete_task_.reset(NULL); 901c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 902c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 903c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 904c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::WriteToFile(FILE* file, 905c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch off_t offset, 906c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch void* data, 907c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch int32 data_size) { 908c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 909c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch posted_asynchronous_operation_ = true; 910c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 911c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 912731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::PostTask( 913731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::FILE, FROM_HERE, 914c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch new AsyncWriter(file, offset, data, data_size)); 915c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 916c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 917c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::WriteUsedItemCountToFile() { 918c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!file_) 919c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; // See comment on the file_ variable for why this might happen. 920c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, kFileHeaderUsedOffset, &used_items_, sizeof(used_items_)); 921c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 922c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 923c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::WriteHashRangeToFile(Hash first_hash, Hash last_hash) { 924c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!file_) 925c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; // See comment on the file_ variable for why this might happen. 926c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (last_hash < first_hash) { 927c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Handle wraparound at 0. This first write is first_hash->EOF 928c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, first_hash * sizeof(Fingerprint) + kFileHeaderSize, 929c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch &hash_table_[first_hash], 930c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch (table_length_ - first_hash + 1) * sizeof(Fingerprint)); 931c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 932c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Now do 0->last_lash. 933c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, kFileHeaderSize, hash_table_, 934c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch (last_hash + 1) * sizeof(Fingerprint)); 935c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else { 936c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Normal case, just write the range. 937c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch WriteToFile(file_, first_hash * sizeof(Fingerprint) + kFileHeaderSize, 938c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch &hash_table_[first_hash], 939c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch (last_hash - first_hash + 1) * sizeof(Fingerprint)); 940c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 941c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 942c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 943c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool VisitedLinkMaster::ReadFromFile(FILE* file, 944c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch off_t offset, 945c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch void* data, 946c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch size_t data_size) { 947c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef NDEBUG 948c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Since this function is synchronous, we require that no asynchronous 949c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // operations could possibly be pending. 950c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(!posted_asynchronous_operation_); 951c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#endif 952c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 95372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (fseek(file, offset, SEEK_SET) != 0) 95472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return false; 955c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 956c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch size_t num_read = fread(data, 1, data_size, file); 957c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return num_read == data_size; 958c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 959c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 960c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// VisitedLinkTableBuilder ---------------------------------------------------- 961c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 962c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochVisitedLinkMaster::TableBuilder::TableBuilder( 963c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch VisitedLinkMaster* master, 964c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const uint8 salt[LINK_SALT_LENGTH]) 965c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch : master_(master), 966c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch success_(true) { 967c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch fingerprints_.reserve(4096); 968c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch memcpy(salt_, salt, sizeof(salt)); 969c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 970c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 971c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// TODO(brettw): Do we want to try to cancel the request if this happens? It 972c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// could delay shutdown if there are a lot of URLs. 973c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::TableBuilder::DisownMaster() { 974c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch master_ = NULL; 975c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 976c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 977c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::TableBuilder::OnURL(const GURL& url) { 978c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!url.is_empty()) { 979c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch fingerprints_.push_back(VisitedLinkMaster::ComputeURLFingerprint( 980c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch url.spec().data(), url.spec().length(), salt_)); 981c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 982c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 983c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 984c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::TableBuilder::OnComplete(bool success) { 985c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch success_ = success; 986c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DLOG_IF(WARNING, !success) << "Unable to rebuild visited links"; 987c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 988c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Marshal to the main thread to notify the VisitedLinkMaster that the 989c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // rebuild is complete. 990731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::PostTask( 991731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BrowserThread::UI, FROM_HERE, 992c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch NewRunnableMethod(this, &TableBuilder::OnCompleteMainThread)); 993c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 994c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 995c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid VisitedLinkMaster::TableBuilder::OnCompleteMainThread() { 996c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (master_) 997c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch master_->OnTableRebuildComplete(success_, fingerprints_); 998c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 999c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // WILL (generally) DELETE THIS! This balances the AddRef in 1000c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // VisitedLinkMaster::RebuildTableFromHistory. 1001c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Release(); 1002c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 1003