// Copyright (c) 2010 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "chrome/browser/visitedlink/visitedlink_master.h"
#if defined(OS_WIN)
#include <windows.h>
#include <io.h>
#include <shlobj.h>
#endif // defined(OS_WIN)
#include <stdio.h>
#include <algorithm>
#include "base/file_util.h"
#include "base/logging.h"
#include "base/message_loop.h"
#include "base/path_service.h"
#include "base/process_util.h"
#include "base/rand_util.h"
#include "base/stack_container.h"
#include "base/string_util.h"
#include "base/threading/thread_restrictions.h"
#include "content/browser/browser_thread.h"
#include "chrome/browser/history/history.h"
#include "chrome/browser/profiles/profile.h"
using file_util::ScopedFILE;
using file_util::OpenFile;
using file_util::TruncateFile;
const int32 VisitedLinkMaster::kFileHeaderSignatureOffset = 0;
const int32 VisitedLinkMaster::kFileHeaderVersionOffset = 4;
const int32 VisitedLinkMaster::kFileHeaderLengthOffset = 8;
const int32 VisitedLinkMaster::kFileHeaderUsedOffset = 12;
const int32 VisitedLinkMaster::kFileHeaderSaltOffset = 16;
const int32 VisitedLinkMaster::kFileCurrentVersion = 2;
// the signature at the beginning of the URL table = "VLnk" (visited links)
const int32 VisitedLinkMaster::kFileSignature = 0x6b6e4c56;
const size_t VisitedLinkMaster::kFileHeaderSize =
kFileHeaderSaltOffset + LINK_SALT_LENGTH;
// This value should also be the same as the smallest size in the lookup
// table in NewTableSizeForCount (prime number).
const unsigned VisitedLinkMaster::kDefaultTableSize = 16381;
const size_t VisitedLinkMaster::kBigDeleteThreshold = 64;
namespace {
// Fills the given salt structure with some quasi-random values
// It is not necessary to generate a cryptographically strong random string,
// only that it be reasonably different for different users.
void GenerateSalt(uint8 salt[LINK_SALT_LENGTH]) {
DCHECK_EQ(LINK_SALT_LENGTH, 8) << "This code assumes the length of the salt";
uint64 randval = base::RandUint64();
memcpy(salt, &randval, 8);
}
// AsyncWriter ----------------------------------------------------------------
// This task executes on a background thread and executes a write. This
// prevents us from blocking the UI thread doing I/O.
class AsyncWriter : public Task {
public:
AsyncWriter(FILE* file, int32 offset, const void* data, size_t data_len)
: file_(file),
offset_(offset) {
data_->resize(data_len);
memcpy(&*data_->begin(), data, data_len);
}
virtual void Run() {
WriteToFile(file_, offset_,
&*data_->begin(), static_cast<int32>(data_->size()));
}
// Exposed as a static so it can be called directly from the Master to
// reduce the number of platform-specific I/O sites we have. Returns true if
// the write was complete.
static bool WriteToFile(FILE* file,
off_t offset,
const void* data,
size_t data_len) {
if (fseek(file, offset, SEEK_SET) != 0)
return false; // Don't write to an invalid part of the file.
size_t num_written = fwrite(data, 1, data_len, file);
// The write may not make it to the kernel (stdlib may buffer the write)
// until the next fseek/fclose call. If we crash, it's easy for our used
// item count to be out of sync with the number of hashes we write.
// Protect against this by calling fflush.
int ret = fflush(file);
DCHECK_EQ(0, ret);
return num_written == data_len;
}
private:
// The data to write and where to write it.
FILE* file_;
int32 offset_; // Offset from the beginning of the file.
// Most writes are just a single fingerprint, so we reserve that much in this
// object to avoid mallocs in that case.
StackVector<char, sizeof(VisitedLinkCommon::Fingerprint)> data_;
DISALLOW_COPY_AND_ASSIGN(AsyncWriter);
};
// Used to asynchronously set the end of the file. This must be done on the
// same thread as the writing to keep things synchronized.
class AsyncSetEndOfFile : public Task {
public:
explicit AsyncSetEndOfFile(FILE* file) : file_(file) {}
virtual void Run() {
TruncateFile(file_);
}
private:
FILE* file_;
DISALLOW_COPY_AND_ASSIGN(AsyncSetEndOfFile);
};
// Used to asynchronously close a file. This must be done on the same thread as
// the writing to keep things synchronized.
class AsyncCloseHandle : public Task {
public:
explicit AsyncCloseHandle(FILE* file) : file_(file) {}
virtual void Run() {
fclose(file_);
}
private:
FILE* file_;
DISALLOW_COPY_AND_ASSIGN(AsyncCloseHandle);
};
} // namespace
// TableBuilder ---------------------------------------------------------------
// How rebuilding from history works
// ---------------------------------
//
// We mark that we're rebuilding from history by setting the table_builder_
// member in VisitedLinkMaster to the TableBuilder we create. This builder
// will be called on the history thread by the history system for every URL
// in the database.
//
// The builder will store the fingerprints for those URLs, and then marshalls
// back to the main thread where the VisitedLinkMaster will be notified. The
// master then replaces its table with a new table containing the computed
// fingerprints.
//
// The builder must remain active while the history system is using it.
// Sometimes, the master will be deleted before the rebuild is complete, in
// which case it notifies the builder via DisownMaster(). The builder will
// delete itself once rebuilding is complete, and not execute any callback.
class VisitedLinkMaster::TableBuilder
: public HistoryService::URLEnumerator,
public base::RefCountedThreadSafe<TableBuilder> {
public:
TableBuilder(VisitedLinkMaster* master,
const uint8 salt[LINK_SALT_LENGTH]);
// Called on the main thread when the master is being destroyed. This will
// prevent a crash when the query completes and the master is no longer
// around. We can not actually do anything but mark this fact, since the
// table will be being rebuilt simultaneously on the other thread.
void DisownMaster();
// HistoryService::URLEnumerator
virtual void OnURL(const GURL& url);
virtual void OnComplete(bool succeed);
private:
friend class base::RefCountedThreadSafe<TableBuilder>;
~TableBuilder() {}
// OnComplete mashals to this function on the main thread to do the
// notification.
void OnCompleteMainThread();
// Owner of this object. MAY ONLY BE ACCESSED ON THE MAIN THREAD!
VisitedLinkMaster* master_;
// Indicates whether the operation has failed or not.
bool success_;
// Salt for this new table.
uint8 salt_[LINK_SALT_LENGTH];
// Stores the fingerprints we computed on the background thread.
VisitedLinkCommon::Fingerprints fingerprints_;
};
// VisitedLinkMaster ----------------------------------------------------------
VisitedLinkMaster::VisitedLinkMaster(Listener* listener,
Profile* profile) {
InitMembers(listener, profile);
}
VisitedLinkMaster::VisitedLinkMaster(Listener* listener,
HistoryService* history_service,
bool suppress_rebuild,
const FilePath& filename,
int32 default_table_size) {
InitMembers(listener, NULL);
database_name_override_ = filename;
table_size_override_ = default_table_size;
history_service_override_ = history_service;
suppress_rebuild_ = suppress_rebuild;
}
VisitedLinkMaster::~VisitedLinkMaster() {
if (table_builder_.get()) {
// Prevent the table builder from calling us back now that we're being
// destroyed. Note that we DON'T delete the object, since the history
// system is still writing into it. When that is complete, the table
// builder will destroy itself when it finds we are gone.
table_builder_->DisownMaster();
}
FreeURLTable();
}
void VisitedLinkMaster::InitMembers(Listener* listener, Profile* profile) {
DCHECK(listener);
listener_ = listener;
file_ = NULL;
shared_memory_ = NULL;
shared_memory_serial_ = 0;
used_items_ = 0;
table_size_override_ = 0;
history_service_override_ = NULL;
suppress_rebuild_ = false;
profile_ = profile;
#ifndef NDEBUG
posted_asynchronous_operation_ = false;
#endif
}
bool VisitedLinkMaster::Init() {
// We probably shouldn't be loading this from the UI thread,
// but it does need to happen early on in startup.
// http://code.google.com/p/chromium/issues/detail?id=24163
base::ThreadRestrictions::ScopedAllowIO allow_io;
if (!InitFromFile())
return InitFromScratch(suppress_rebuild_);
return true;
}
VisitedLinkMaster::Hash VisitedLinkMaster::TryToAddURL(const GURL& url) {
// Extra check that we are not incognito. This should not happen.
if (profile_ && profile_->IsOffTheRecord()) {
NOTREACHED();
return null_hash_;
}
if (!url.is_valid())
return null_hash_; // Don't add invalid URLs.
Fingerprint fingerprint = ComputeURLFingerprint(url.spec().data(),
url.spec().size(),
salt_);
if (table_builder_) {
// If we have a pending delete for this fingerprint, cancel it.
std::set<Fingerprint>::iterator found =
deleted_since_rebuild_.find(fingerprint);
if (found != deleted_since_rebuild_.end())
deleted_since_rebuild_.erase(found);
// A rebuild is in progress, save this addition in the temporary list so
// it can be added once rebuild is complete.
added_since_rebuild_.insert(fingerprint);
}
// If the table is "full", we don't add URLs and just drop them on the floor.
// This can happen if we get thousands of new URLs and something causes
// the table resizing to fail. This check prevents a hang in that case. Note
// that this is *not* the resize limit, this is just a sanity check.
if (used_items_ / 8 > table_length_ / 10)
return null_hash_; // Table is more than 80% full.
return AddFingerprint(fingerprint, true);
}
void VisitedLinkMaster::AddURL(const GURL& url) {
Hash index = TryToAddURL(url);
if (!table_builder_ && index != null_hash_) {
// Not rebuilding, so we want to keep the file on disk up-to-date.
WriteUsedItemCountToFile();
WriteHashRangeToFile(index, index);
ResizeTableIfNecessary();
}
}
void VisitedLinkMaster::AddURLs(const std::vector<GURL>& url) {
for (std::vector<GURL>::const_iterator i = url.begin();
i != url.end(); ++i) {
Hash index = TryToAddURL(*i);
if (!table_builder_ && index != null_hash_)
ResizeTableIfNecessary();
}
// Keeps the file on disk up-to-date.
if (!table_builder_)
WriteFullTable();
}
void VisitedLinkMaster::DeleteAllURLs() {
// Any pending modifications are invalid.
added_since_rebuild_.clear();
deleted_since_rebuild_.clear();
// Clear the hash table.
used_items_ = 0;
memset(hash_table_, 0, this->table_length_ * sizeof(Fingerprint));
// Resize it if it is now too empty. Resize may write the new table out for
// us, otherwise, schedule writing the new table to disk ourselves.
if (!ResizeTableIfNecessary())
WriteFullTable();
listener_->Reset();
}
void VisitedLinkMaster::DeleteURLs(const std::set<GURL>& urls) {
typedef std::set<GURL>::const_iterator SetIterator;
if (urls.empty())
return;
listener_->Reset();
if (table_builder_) {
// A rebuild is in progress, save this deletion in the temporary list so
// it can be added once rebuild is complete.
for (SetIterator i = urls.begin(); i != urls.end(); ++i) {
if (!i->is_valid())
continue;
Fingerprint fingerprint =
ComputeURLFingerprint(i->spec().data(), i->spec().size(), salt_);
deleted_since_rebuild_.insert(fingerprint);
// If the URL was just added and now we're deleting it, it may be in the
// list of things added since the last rebuild. Delete it from that list.
std::set<Fingerprint>::iterator found =
added_since_rebuild_.find(fingerprint);
if (found != added_since_rebuild_.end())
added_since_rebuild_.erase(found);
// Delete the URLs from the in-memory table, but don't bother writing
// to disk since it will be replaced soon.
DeleteFingerprint(fingerprint, false);
}
return;
}
// Compute the deleted URLs' fingerprints and delete them
std::set<Fingerprint> deleted_fingerprints;
for (SetIterator i = urls.begin(); i != urls.end(); ++i) {
if (!i->is_valid())
continue;
deleted_fingerprints.insert(
ComputeURLFingerprint(i->spec().data(), i->spec().size(), salt_));
}
DeleteFingerprintsFromCurrentTable(deleted_fingerprints);
}
// See VisitedLinkCommon::IsVisited which should be in sync with this algorithm
VisitedLinkMaster::Hash VisitedLinkMaster::AddFingerprint(
Fingerprint fingerprint,
bool send_notifications) {
if (!hash_table_ || table_length_ == 0) {
NOTREACHED(); // Not initialized.
return null_hash_;
}
Hash cur_hash = HashFingerprint(fingerprint);
Hash first_hash = cur_hash;
while (true) {
Fingerprint cur_fingerprint = FingerprintAt(cur_hash);
if (cur_fingerprint == fingerprint)
return null_hash_; // This fingerprint is already in there, do nothing.
if (cur_fingerprint == null_fingerprint_) {
// End of probe sequence found, insert here.
hash_table_[cur_hash] = fingerprint;
used_items_++;
// If allowed, notify listener that a new visited link was added.
if (send_notifications)
listener_->Add(fingerprint);
return cur_hash;
}
// Advance in the probe sequence.
cur_hash = IncrementHash(cur_hash);
if (cur_hash == first_hash) {
// This means that we've wrapped around and are about to go into an
// infinite loop. Something was wrong with the hashtable resizing
// logic, so stop here.
NOTREACHED();
return null_hash_;
}
}
}
void VisitedLinkMaster::DeleteFingerprintsFromCurrentTable(
const std::set<Fingerprint>& fingerprints) {
bool bulk_write = (fingerprints.size() > kBigDeleteThreshold);
// Delete the URLs from the table.
for (std::set<Fingerprint>::const_iterator i = fingerprints.begin();
i != fingerprints.end(); ++i)
DeleteFingerprint(*i, !bulk_write);
// These deleted fingerprints may make us shrink the table.
if (ResizeTableIfNecessary())
return; // The resize function wrote the new table to disk for us.
// Nobody wrote this out for us, write the full file to disk.
if (bulk_write)
WriteFullTable();
}
bool VisitedLinkMaster::DeleteFingerprint(Fingerprint fingerprint,
bool update_file) {
if (!hash_table_ || table_length_ == 0) {
NOTREACHED(); // Not initialized.
return false;
}
if (!IsVisited(fingerprint))
return false; // Not in the database to delete.
// First update the header used count.
used_items_--;
if (update_file)
WriteUsedItemCountToFile();
Hash deleted_hash = HashFingerprint(fingerprint);
// Find the range of "stuff" in the hash table that is adjacent to this
// fingerprint. These are things that could be affected by the change in
// the hash table. Since we use linear probing, anything after the deleted
// item up until an empty item could be affected.
Hash end_range = deleted_hash;
while (true) {
Hash next_hash = IncrementHash(end_range);
if (next_hash == deleted_hash)
break; // We wrapped around and the whole table is full.
if (!hash_table_[next_hash])
break; // Found the last spot.
end_range = next_hash;
}
// We could get all fancy and move the affected fingerprints around, but
// instead we just remove them all and re-add them (minus our deleted one).
// This will mean there's a small window of time where the affected links
// won't be marked visited.
StackVector<Fingerprint, 32> shuffled_fingerprints;
Hash stop_loop = IncrementHash(end_range); // The end range is inclusive.
for (Hash i = deleted_hash; i != stop_loop; i = IncrementHash(i)) {
if (hash_table_[i] != fingerprint) {
// Don't save the one we're deleting!
shuffled_fingerprints->push_back(hash_table_[i]);
// This will balance the increment of this value in AddFingerprint below
// so there is no net change.
used_items_--;
}
hash_table_[i] = null_fingerprint_;
}
if (!shuffled_fingerprints->empty()) {
// Need to add the new items back.
for (size_t i = 0; i < shuffled_fingerprints->size(); i++)
AddFingerprint(shuffled_fingerprints[i], false);
}
// Write the affected range to disk [deleted_hash, end_range].
if (update_file)
WriteHashRangeToFile(deleted_hash, end_range);
return true;
}
bool VisitedLinkMaster::WriteFullTable() {
// This function can get called when the file is open, for example, when we
// resize the table. We must handle this case and not try to reopen the file,
// since there may be write operations pending on the file I/O thread.
//
// Note that once we start writing, we do not delete on error. This means
// there can be a partial file, but the short file will be detected next time
// we start, and will be replaced.
//
// This might possibly get corrupted if we crash in the middle of writing.
// We should pick up the most common types of these failures when we notice
// that the file size is different when we load it back in, and then we will
// regenerate the table.
if (!file_) {
FilePath filename;
GetDatabaseFileName(&filename);
file_ = OpenFile(filename, "wb+");
if (!file_) {
DLOG(ERROR) << "Failed to open file " << filename.value();
return false;
}
}
// Write the new header.
int32 header[4];
header[0] = kFileSignature;
header[1] = kFileCurrentVersion;
header[2] = table_length_;
header[3] = used_items_;
WriteToFile(file_, 0, header, sizeof(header));
WriteToFile(file_, sizeof(header), salt_, LINK_SALT_LENGTH);
// Write the hash data.
WriteToFile(file_, kFileHeaderSize,
hash_table_, table_length_ * sizeof(Fingerprint));
// The hash table may have shrunk, so make sure this is the end.
BrowserThread::PostTask(
BrowserThread::FILE, FROM_HERE, new AsyncSetEndOfFile(file_));
return true;
}
bool VisitedLinkMaster::InitFromFile() {
DCHECK(file_ == NULL);
FilePath filename;
GetDatabaseFileName(&filename);
ScopedFILE file_closer(OpenFile(filename, "rb+"));
if (!file_closer.get())
return false;
int32 num_entries, used_count;
if (!ReadFileHeader(file_closer.get(), &num_entries, &used_count, salt_))
return false; // Header isn't valid.
// Allocate and read the table.
if (!CreateURLTable(num_entries, false))
return false;
if (!ReadFromFile(file_closer.get(), kFileHeaderSize,
hash_table_, num_entries * sizeof(Fingerprint))) {
FreeURLTable();
return false;
}
used_items_ = used_count;
#ifndef NDEBUG
DebugValidate();
#endif
file_ = file_closer.release();
return true;
}
bool VisitedLinkMaster::InitFromScratch(bool suppress_rebuild) {
int32 table_size = kDefaultTableSize;
if (table_size_override_)
table_size = table_size_override_;
// The salt must be generated before the table so that it can be copied to
// the shared memory.
GenerateSalt(salt_);
if (!CreateURLTable(table_size, true))
return false;
#ifndef NDEBUG
DebugValidate();
#endif
if (suppress_rebuild) {
// When we disallow rebuilds (normally just unit tests), just use the
// current empty table.
return WriteFullTable();
}
// This will build the table from history. On the first run, history will
// be empty, so this will be correct. This will also write the new table
// to disk. We don't want to save explicitly here, since the rebuild may
// not complete, leaving us with an empty but valid visited link database.
// In the future, we won't know we need to try rebuilding again.
return RebuildTableFromHistory();
}
bool VisitedLinkMaster::ReadFileHeader(FILE* file,
int32* num_entries,
int32* used_count,
uint8 salt[LINK_SALT_LENGTH]) {
// Get file size.
// Note that there is no need to seek back to the original location in the
// file since ReadFromFile() [which is the next call accessing the file]
// seeks before reading.
if (fseek(file, 0, SEEK_END) == -1)
return false;
size_t file_size = ftell(file);
if (file_size <= kFileHeaderSize)
return false;
uint8 header[kFileHeaderSize];
if (!ReadFromFile(file, 0, &header, kFileHeaderSize))
return false;
// Verify the signature.
int32 signature;
memcpy(&signature, &header[kFileHeaderSignatureOffset], sizeof(signature));
if (signature != kFileSignature)
return false;
// Verify the version is up-to-date. As with other read errors, a version
// mistmatch will trigger a rebuild of the database from history, which will
// have the effect of migrating the database.
int32 version;
memcpy(&version, &header[kFileHeaderVersionOffset], sizeof(version));
if (version != kFileCurrentVersion)
return false; // Bad version.
// Read the table size and make sure it matches the file size.
memcpy(num_entries, &header[kFileHeaderLengthOffset], sizeof(*num_entries));
if (*num_entries * sizeof(Fingerprint) + kFileHeaderSize != file_size)
return false; // Bad size.
// Read the used item count.
memcpy(used_count, &header[kFileHeaderUsedOffset], sizeof(*used_count));
if (*used_count > *num_entries)
return false; // Bad used item count;
// Read the salt.
memcpy(salt, &header[kFileHeaderSaltOffset], LINK_SALT_LENGTH);
// This file looks OK from the header's perspective.
return true;
}
bool VisitedLinkMaster::GetDatabaseFileName(FilePath* filename) {
if (!database_name_override_.empty()) {
// use this filename, the directory must exist
*filename = database_name_override_;
return true;
}
if (!profile_ || profile_->GetPath().empty())
return false;
FilePath profile_dir = profile_->GetPath();
*filename = profile_dir.Append(FILE_PATH_LITERAL("Visited Links"));
return true;
}
// Initializes the shared memory structure. The salt should already be filled
// in so that it can be written to the shared memory
bool VisitedLinkMaster::CreateURLTable(int32 num_entries, bool init_to_empty) {
// The table is the size of the table followed by the entries.
uint32 alloc_size = num_entries * sizeof(Fingerprint) + sizeof(SharedHeader);
// Create the shared memory object.
shared_memory_ = new base::SharedMemory();
if (!shared_memory_)
return false;
if (!shared_memory_->CreateAndMapAnonymous(alloc_size)) {
delete shared_memory_;
shared_memory_ = NULL;
return false;
}
if (init_to_empty) {
memset(shared_memory_->memory(), 0, alloc_size);
used_items_ = 0;
}
table_length_ = num_entries;
// Save the header for other processes to read.
SharedHeader* header = static_cast<SharedHeader*>(shared_memory_->memory());
header->length = table_length_;
memcpy(header->salt, salt_, LINK_SALT_LENGTH);
// Our table pointer is just the data immediately following the size.
hash_table_ = reinterpret_cast<Fingerprint*>(
static_cast<char*>(shared_memory_->memory()) + sizeof(SharedHeader));
return true;
}
bool VisitedLinkMaster::BeginReplaceURLTable(int32 num_entries) {
base::SharedMemory *old_shared_memory = shared_memory_;
Fingerprint* old_hash_table = hash_table_;
int32 old_table_length = table_length_;
if (!CreateURLTable(num_entries, true)) {
// Try to put back the old state.
shared_memory_ = old_shared_memory;
hash_table_ = old_hash_table;
table_length_ = old_table_length;
return false;
}
#ifndef NDEBUG
DebugValidate();
#endif
return true;
}
void VisitedLinkMaster::FreeURLTable() {
if (shared_memory_) {
delete shared_memory_;
shared_memory_ = NULL;
}
if (!file_)
return;
BrowserThread::PostTask(
BrowserThread::FILE, FROM_HERE, new AsyncCloseHandle(file_));
}
bool VisitedLinkMaster::ResizeTableIfNecessary() {
DCHECK(table_length_ > 0) << "Must have a table";
// Load limits for good performance/space. We are pretty conservative about
// keeping the table not very full. This is because we use linear probing
// which increases the likelihood of clumps of entries which will reduce
// performance.
const float max_table_load = 0.5f; // Grow when we're > this full.
const float min_table_load = 0.2f; // Shrink when we're < this full.
float load = ComputeTableLoad();
if (load < max_table_load &&
(table_length_ <= static_cast<float>(kDefaultTableSize) ||
load > min_table_load))
return false;
// Table needs to grow or shrink.
int new_size = NewTableSizeForCount(used_items_);
DCHECK(new_size > used_items_);
DCHECK(load <= min_table_load || new_size > table_length_);
ResizeTable(new_size);
return true;
}
void VisitedLinkMaster::ResizeTable(int32 new_size) {
DCHECK(shared_memory_ && shared_memory_->memory() && hash_table_);
shared_memory_serial_++;
#ifndef NDEBUG
DebugValidate();
#endif
base::SharedMemory* old_shared_memory = shared_memory_;
Fingerprint* old_hash_table = hash_table_;
int32 old_table_length = table_length_;
if (!BeginReplaceURLTable(new_size))
return;
// Now we have two tables, our local copy which is the old one, and the new
// one loaded into this object where we need to copy the data.
for (int32 i = 0; i < old_table_length; i++) {
Fingerprint cur = old_hash_table[i];
if (cur)
AddFingerprint(cur, false);
}
// On error unmapping, just forget about it since we can't do anything
// else to release it.
delete old_shared_memory;
// Send an update notification to all child processes so they read the new
// table.
listener_->NewTable(shared_memory_);
#ifndef NDEBUG
DebugValidate();
#endif
// The new table needs to be written to disk.
WriteFullTable();
}
uint32 VisitedLinkMaster::NewTableSizeForCount(int32 item_count) const {
// These table sizes are selected to be the maximum prime number less than
// a "convenient" multiple of 1K.
static const int table_sizes[] = {
16381, // 16K = 16384 <- don't shrink below this table size
// (should be == default_table_size)
32767, // 32K = 32768
65521, // 64K = 65536
130051, // 128K = 131072
262127, // 256K = 262144
524269, // 512K = 524288
1048549, // 1M = 1048576
2097143, // 2M = 2097152
4194301, // 4M = 4194304
8388571, // 8M = 8388608
16777199, // 16M = 16777216
33554347}; // 32M = 33554432
// Try to leave the table 33% full.
int desired = item_count * 3;
// Find the closest prime.
for (size_t i = 0; i < arraysize(table_sizes); i ++) {
if (table_sizes[i] > desired)
return table_sizes[i];
}
// Growing very big, just approximate a "good" number, not growing as much
// as normal.
return item_count * 2 - 1;
}
// See the TableBuilder definition in the header file for how this works.
bool VisitedLinkMaster::RebuildTableFromHistory() {
DCHECK(!table_builder_);
if (table_builder_)
return false;
HistoryService* history_service = history_service_override_;
if (!history_service && profile_) {
history_service = profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
}
if (!history_service) {
DLOG(WARNING) << "Attempted to rebuild visited link table, but couldn't "
"obtain a HistoryService.";
return false;
}
// TODO(brettw) make sure we have reasonable salt!
table_builder_ = new TableBuilder(this, salt_);
// Make sure the table builder stays live during the call, even if the
// master is deleted. This is balanced in TableBuilder::OnCompleteMainThread.
table_builder_->AddRef();
history_service->IterateURLs(table_builder_);
return true;
}
// See the TableBuilder declaration above for how this works.
void VisitedLinkMaster::OnTableRebuildComplete(
bool success,
const std::vector<Fingerprint>& fingerprints) {
if (success) {
// Replace the old table with a new blank one.
shared_memory_serial_++;
// We are responsible for freeing it AFTER it has been replaced if
// replacement succeeds.
base::SharedMemory* old_shared_memory = shared_memory_;
int new_table_size = NewTableSizeForCount(
static_cast<int>(fingerprints.size() + added_since_rebuild_.size()));
if (BeginReplaceURLTable(new_table_size)) {
// Free the old table.
delete old_shared_memory;
// Add the stored fingerprints to the hash table.
for (size_t i = 0; i < fingerprints.size(); i++)
AddFingerprint(fingerprints[i], false);
// Also add anything that was added while we were asynchronously
// generating the new table.
for (std::set<Fingerprint>::iterator i = added_since_rebuild_.begin();
i != added_since_rebuild_.end(); ++i)
AddFingerprint(*i, false);
added_since_rebuild_.clear();
// Now handle deletions.
DeleteFingerprintsFromCurrentTable(deleted_since_rebuild_);
deleted_since_rebuild_.clear();
// Send an update notification to all child processes.
listener_->NewTable(shared_memory_);
// We shouldn't be writing the table from the main thread!
// http://code.google.com/p/chromium/issues/detail?id=24163
base::ThreadRestrictions::ScopedAllowIO allow_io;
WriteFullTable();
}
}
table_builder_ = NULL; // Will release our reference to the builder.
// Notify the unit test that the rebuild is complete (will be NULL in prod.)
if (rebuild_complete_task_.get()) {
rebuild_complete_task_->Run();
rebuild_complete_task_.reset(NULL);
}
}
void VisitedLinkMaster::WriteToFile(FILE* file,
off_t offset,
void* data,
int32 data_size) {
#ifndef NDEBUG
posted_asynchronous_operation_ = true;
#endif
BrowserThread::PostTask(
BrowserThread::FILE, FROM_HERE,
new AsyncWriter(file, offset, data, data_size));
}
void VisitedLinkMaster::WriteUsedItemCountToFile() {
if (!file_)
return; // See comment on the file_ variable for why this might happen.
WriteToFile(file_, kFileHeaderUsedOffset, &used_items_, sizeof(used_items_));
}
void VisitedLinkMaster::WriteHashRangeToFile(Hash first_hash, Hash last_hash) {
if (!file_)
return; // See comment on the file_ variable for why this might happen.
if (last_hash < first_hash) {
// Handle wraparound at 0. This first write is first_hash->EOF
WriteToFile(file_, first_hash * sizeof(Fingerprint) + kFileHeaderSize,
&hash_table_[first_hash],
(table_length_ - first_hash + 1) * sizeof(Fingerprint));
// Now do 0->last_lash.
WriteToFile(file_, kFileHeaderSize, hash_table_,
(last_hash + 1) * sizeof(Fingerprint));
} else {
// Normal case, just write the range.
WriteToFile(file_, first_hash * sizeof(Fingerprint) + kFileHeaderSize,
&hash_table_[first_hash],
(last_hash - first_hash + 1) * sizeof(Fingerprint));
}
}
bool VisitedLinkMaster::ReadFromFile(FILE* file,
off_t offset,
void* data,
size_t data_size) {
#ifndef NDEBUG
// Since this function is synchronous, we require that no asynchronous
// operations could possibly be pending.
DCHECK(!posted_asynchronous_operation_);
#endif
if (fseek(file, offset, SEEK_SET) != 0)
return false;
size_t num_read = fread(data, 1, data_size, file);
return num_read == data_size;
}
// VisitedLinkTableBuilder ----------------------------------------------------
VisitedLinkMaster::TableBuilder::TableBuilder(
VisitedLinkMaster* master,
const uint8 salt[LINK_SALT_LENGTH])
: master_(master),
success_(true) {
fingerprints_.reserve(4096);
memcpy(salt_, salt, sizeof(salt));
}
// TODO(brettw): Do we want to try to cancel the request if this happens? It
// could delay shutdown if there are a lot of URLs.
void VisitedLinkMaster::TableBuilder::DisownMaster() {
master_ = NULL;
}
void VisitedLinkMaster::TableBuilder::OnURL(const GURL& url) {
if (!url.is_empty()) {
fingerprints_.push_back(VisitedLinkMaster::ComputeURLFingerprint(
url.spec().data(), url.spec().length(), salt_));
}
}
void VisitedLinkMaster::TableBuilder::OnComplete(bool success) {
success_ = success;
DLOG_IF(WARNING, !success) << "Unable to rebuild visited links";
// Marshal to the main thread to notify the VisitedLinkMaster that the
// rebuild is complete.
BrowserThread::PostTask(
BrowserThread::UI, FROM_HERE,
NewRunnableMethod(this, &TableBuilder::OnCompleteMainThread));
}
void VisitedLinkMaster::TableBuilder::OnCompleteMainThread() {
if (master_)
master_->OnTableRebuildComplete(success_, fingerprints_);
// WILL (generally) DELETE THIS! This balances the AddRef in
// VisitedLinkMaster::RebuildTableFromHistory.
Release();
}