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

components/history/core/browser/download_database.cc

Index: components/history/core/browser/download_database.cc
diff --git a/components/history/core/browser/download_database.cc b/components/history/core/browser/download_database.cc
index 93b707c9fe22f76c0bfbac30ce721b4710e40289..8303b48b2d2696258d437ffb45d678dd34591de1 100644
--- a/components/history/core/browser/download_database.cc
+++ b/components/history/core/browser/download_database.cc
@@ -192,27 +192,54 @@ bool DownloadDatabase::MigrateHashHttpMethodAndGenerateGuids() {
       !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);
 }