[Downloads/History] Comply with RFC 4122 when generating GUIDs.

components/history/core/browser/download_database.cc

 // Copyright (c) 2012 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 "components/history/core/browser/download_database.h"
 
 #include <limits>
 #include <string>
 #include <vector>
 
@@ skipping 174 matching lines @@
   return EnsureColumnExists("etag", "VARCHAR NOT NULL DEFAULT \"\"") &&
          EnsureColumnExists("last_modified", "VARCHAR NOT NULL DEFAULT \"\"");
 }
 
 bool DownloadDatabase::MigrateHashHttpMethodAndGenerateGuids() {
   if (!EnsureColumnExists("guid", "VARCHAR NOT NULL DEFAULT ''") ||
       !EnsureColumnExists("hash", "BLOB NOT NULL DEFAULT X''") ||
       !EnsureColumnExists("http_method", "VARCHAR NOT NULL DEFAULT ''"))
     return false;
 
-  // Generate GUIDs for each download. The GUID is generated thusly:
+  // Generate GUIDs for each download. GUIDs based on random data should conform
+  // with RFC 4122 section 4.4. Given the following field layout (based on RFC
+  // 4122):
   //
-  //    XXXXXXXX-RRRR-RRRR-RRRR-RRRRRRRRRRRR
+  //  0                   1                   2                   3
+  //  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |                          time_low                             |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |       time_mid                |         time_hi_and_version   |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |clk_seq_hi_res |  clk_seq_low  |         node (0-1)            |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |                         node (2-5)                            |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //
+  // * Bits 4-7 of time_hi_and_version should be set to 0b0100 == 4
+  // * Bits 6-7 of clk_seq_hi_res should be set to 0b10
+  // * All other bits should be random or pseudorandom.
+  //
+  // We are going to take the liberty of setting time_low to the 32-bit download
+  // ID. That will guarantee that no two randomly generated GUIDs will collide
+  // even if the 90 bits of entropy doesn't save us.
+  //
+  // Translated to the canonical string representation, the GUID is generated
+  // thusly:
+  //
+  //    XXXXXXXX-RRRR-4RRR-yRRR-RRRRRRRRRRRR

[sky, 2016/04/08 21:59:32]

The old code may not have generated the 4 and y, right? If so, are there
problems with previous entries that may not follow the new values?

[asanka, 2016/04/11 17:32:59]

None at all. I'd have added migration code if it did.

The decision to use GUIDs was so that the persistent ID of a download had known
properties (fixed size, case insensitive, unique-subject-to-case-normalization,
comprised of unambiguous character set). Other than that, callers treat the IDs
as opaque strings. Those that treat the string as a GUID and attempt to parse it
will succeed regardless of whether the GUID matches the requirements of a ver 4
GUID or not. No known parser attempts to validate whether a GUID conforms to
just the types specified in RFC 4122.

The formats are there so that a GUID generated using one method won't
accidentally collide with a GUID generated using another method. Other than that
the method isn't interesting to a caller.

On Posix base::GenerateGUID() generates type 4 GUIDs. I've experimentally
verified that this is also the case for Windows although the
CoCreateGuid/UuidCreate APIs don't document the type of GUID generated. The code
above also generates type 4 GUIDs on all platforms during migration. The code
that was there before generates type 4 GUIDs with the exception that the 6 fixed
format indicator bits are not fixed (let's call these type IGs for Incorrectly
Generated).

Hence the probability of collision between an IG GUID and a type 4 GUID ==
(1/64) * (probability of collision between two type 4 GUIDs).

I decided to be pedantic here since there's a spec and I felt like we should
generate conformant GUIDs.

   //    \__  __/ \___________  ____________/
   //       \/                \/
-  //       |          Random hex digits
+  //       |          R = random hex digit.
+  //       |          y = one of {'8','9','A','B'} selected randomly.
+  //       |          4 = the character '4'.
   //       |
   //       Hex representation of 32-bit download ID.
   //
-  // The 96 random bits provide entropy while the 32-bits from the download ID
-  // ensure that the generated identifiers will at least be unique amongst the
-  // download rows in the unlikely event there's a collision in the 96 entropy
-  // bits.
-  //
   // This GUID generation scheme is only used for migrated download rows and
   // assumes that the likelihood of a collision with a GUID generated via
   // base::GenerateGUID() will be vanishingly small.
   const char kMigrateGuidsQuery[] =
       "UPDATE downloads SET guid = printf"
-      "(\"%08X-%s-%s-%s-%s\", id, hex(randomblob(2)), hex(randomblob(2)),"
-      " hex(randomblob(2)), hex(randomblob(6)))";
+      "(\"%08X-%s-4%s-%01X%s-%s\","
+      " id,"
+      " hex(randomblob(2)),"
+      " substr(hex(randomblob(2)),2),"
+      " (8 | (random() & 3)),"
+      " substr(hex(randomblob(2)),2),"
+      " hex(randomblob(6)))";
   return GetDB().Execute(kMigrateGuidsQuery);
 }
 
 bool DownloadDatabase::InitDownloadTable() {
   const char kSchema[] =
       "CREATE TABLE downloads ("
       "id INTEGER PRIMARY KEY,"             // Primary key.
       "guid VARCHAR NOT NULL,"              // GUID.
       "current_path LONGVARCHAR NOT NULL,"  // Current disk location
       "target_path LONGVARCHAR NOT NULL,"   // Final disk location
@@ skipping 388 matching lines @@
 size_t DownloadDatabase::CountDownloads() {
   EnsureInProgressEntriesCleanedUp();
 
   sql::Statement statement(GetDB().GetCachedStatement(SQL_FROM_HERE,
       "SELECT count(*) from downloads"));
   statement.Step();
   return statement.ColumnInt(0);
 }
 
 }  // namespace history