visitedlink_writer.cc 40 KB

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