Updated random seed patchkit

Updated random seed patchkit

[Andi Kleen]

I addressed all review comments, clarified some code.
The random seed generation in gcc.c is now fixed too and toplev.c
detects this case and doesn't rerun the CRC.

Repasses bootstrap and testsuite on x86_64-linux.

Since the previous version was approved I will commit in 24h,
unless there are new objections.

-Andi

[PATCH 2/3] Use urandom to get random seed

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

When available use /dev/urandom to get the random seem. This will lower the probability
of collisions.

On other systems it will fallback to the old methods.

Passes bootstrap + testsuite on x86_64. Ok?

gcc/:

* 2011-09-26   Andi Kleen <ak@linux.intel.com>

	* toplev.c (init_local_tick): Try reading random seed from /dev/urandom
---
 gcc/toplev.c |   12 +++++++++++-
 1 files changed, 11 insertions(+), 1 deletions(-)

diff --git a/gcc/toplev.c b/gcc/toplev.c
index 78583fc..ab6b5a4 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -262,7 +262,17 @@ init_local_tick (void)
 {
   if (!flag_random_seed)
     {
-      /* Get some more or less random data.  */
+      /* Try urandom first. Time of day is too likely to collide. 
+	 In case of any error we just use the local tick. */
+
+      int fd = open ("/dev/urandom", O_RDONLY);
+      if (fd >= 0)
+        {
+          read (fd, &random_seed, sizeof (random_seed));
+          close (fd);
+        }
+
+      /* Now get the tick anyways  */
 #ifdef HAVE_GETTIMEOFDAY
       {
 	struct timeval tv;
-- 
1.7.5.4

[PATCH 3/3] Use urandom in gcc.c too

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

gcc also takes generates a random number in some special circumstances,
so teach it about /dev/urandom too.

gcc/:

2011-09-27   Andi Kleen <ak@linux.intel.com>

	* gcc.c (get_local_tick). Rename to get_random_number.  Read from /dev/urandom.
	Add getpid call.
	(compare_debug_dump_opt_spec_function): Drop getpid call.
---
 gcc/gcc.c |   22 ++++++++++++++++------
 1 files changed, 16 insertions(+), 6 deletions(-)

diff --git a/gcc/gcc.c b/gcc/gcc.c
index ddec8db..3bfdf77 100644
--- a/gcc/gcc.c
+++ b/gcc/gcc.c
@@ -8062,12 +8062,22 @@ print_asm_header_spec_function (int arg ATTRIBUTE_UNUSED,
   return NULL;
 }
 
-/* Compute a timestamp to initialize flag_random_seed.  */
+/* Get a random number for -frandom-seed */
 
-static unsigned
-get_local_tick (void)
+static unsigned HOST_WIDE_INT
+get_random_number (void)
 {
-  unsigned ret = 0;
+  unsigned HOST_WIDE_INT ret = 0;
+  int fd; 
+
+  fd = open ("/dev/urandom", O_RDONLY); 
+  if (fd >= 0)
+    {
+      read (fd, &ret, sizeof (HOST_WIDE_INT));
+      close (fd);
+      if (ret)
+        return ret;
+    }
 
   /* Get some more or less random data.  */
 #ifdef HAVE_GETTIMEOFDAY
@@ -8086,7 +8096,7 @@ get_local_tick (void)
   }
 #endif
 
-  return ret;
+  return ret ^ getpid();
 }
 
 /* %:compare-debug-dump-opt spec function.  Save the last argument,
@@ -8145,7 +8155,7 @@ compare_debug_dump_opt_spec_function (int arg,
 
   if (!which)
     {
-      unsigned HOST_WIDE_INT value = get_local_tick () ^ getpid ();
+      unsigned HOST_WIDE_INT value = get_random_number ();
 
       sprintf (random_seed, HOST_WIDE_INT_PRINT_HEX, value);
     }
-- 
1.7.5.4

[PATCH 1/3] Change random seeds to 64bit and drop re-crcing

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

I had some trouble with random build failures in a large LTO project
and it turned out to be random seed collisions in a highly parallel build
(thanks to Honza for suggesting that)

There were multiple problems:
- The way to generate the random seed is not very random (milliseconds time plus pid)
and prone to collisions on highly parallel builds
- It's only 32bit
- Several users take the existing ascii seed and re-CRC32 it again, which
doesn't exactly improve it.

This patch changes that to:
- Always use 64bit seeds as numbers (no re-crcing)
- Change all users to use HOST_WIDE_INT
- When the user specifies a random seed it's still crc32ed, but only in
this case.

Passes bootstrap + testsuite on x86_64-linux.

gcc/cp:

2011-09-26   Andi Kleen <ak@linux.intel.com>

	* repo.c (finish_repo): Use HOST_WIDE_INT_PRINT_HEX_PURE.

gcc/:

2011-09-26   Andi Kleen <ak@linux.intel.com>

	* hwint.h (HOST_WIDE_INT_PRINT_HEX_PURE): Add.
	* lto-streamer.c (lto_get_section_name): Remove crc32_string.
 	Handle numerical random seed.
	* lto-streamer.h (lto_file_decl_data): Change id to unsigned HOST_WIDE_INT.
	* toplev.c (random_seed): Add.
	(init_random_seed): Change for numerical random seed.
	(get_random_seed): Return as HOST_WIDE_INT.
	(set_random_seed): Crc32 existing string.
	* toplev.h (get_random_seed): Change to numercal return.
	* tree.c (get_file_function_name): Remove CRC. Handle numerical random seed.

gcc/lto/:

2011-09-26   Andi Kleen <ak@linux.intel.com>

	* lto.c (lto_resolution_read): Remove id dumping.
	(lto_section_with_id): Turn id HOST_WIDE_ID.
	(create_subid_section_table): Dito.
---
 gcc/cp/repo.c      |    3 ++-
 gcc/hwint.h        |    1 +
 gcc/lto-streamer.c |    8 ++++----
 gcc/lto-streamer.h |    2 +-
 gcc/lto/lto.c      |   11 ++++-------
 gcc/toplev.c       |   27 +++++++++++++++++----------
 gcc/toplev.h       |    2 +-
 gcc/tree.c         |    6 +++---
 8 files changed, 33 insertions(+), 27 deletions(-)

diff --git a/gcc/cp/repo.c b/gcc/cp/repo.c
index 16a192e..ca971b6 100644
--- a/gcc/cp/repo.c
+++ b/gcc/cp/repo.c
@@ -263,7 +263,8 @@ finish_repo (void)
 	 anonymous namespaces will get the same mangling when this
 	 file is recompiled.  */
       if (!strstr (args, "'-frandom-seed="))
-	fprintf (repo_file, " '-frandom-seed=%s'", get_random_seed (false));
+	fprintf (repo_file, " '-frandom-seed=" HOST_WIDE_INT_PRINT_HEX_PURE "'", 
+		 get_random_seed (false));
       fprintf (repo_file, "\n");
     }
 
diff --git a/gcc/hwint.h b/gcc/hwint.h
index 2643aee..f5e0bee 100644
--- a/gcc/hwint.h
+++ b/gcc/hwint.h
@@ -102,6 +102,7 @@ extern char sizeof_long_long_must_be_8[sizeof(long long) == 8 ? 1 : -1];
 #define HOST_WIDE_INT_PRINT_DEC_C HOST_WIDE_INT_PRINT_DEC HOST_WIDE_INT_PRINT_C
 #define HOST_WIDE_INT_PRINT_UNSIGNED "%" HOST_WIDE_INT_PRINT "u"
 #define HOST_WIDE_INT_PRINT_HEX "%#" HOST_WIDE_INT_PRINT "x"
+#define HOST_WIDE_INT_PRINT_HEX_PURE "%" HOST_WIDE_INT_PRINT "x"
 
 /* Set HOST_WIDEST_INT.  This is a 64-bit type unless the compiler
    in use has no 64-bit type at all; in that case it's 32 bits.  */
diff --git a/gcc/lto-streamer.c b/gcc/lto-streamer.c
index 633c3ce..e3ccb79 100644
--- a/gcc/lto-streamer.c
+++ b/gcc/lto-streamer.c
@@ -166,13 +166,13 @@ lto_get_section_name (int section_type, const char *name, struct lto_file_decl_d
      doesn't confuse the reader with merged sections.
 
      For options don't add a ID, the option reader cannot deal with them
-     and merging should be ok here.
-
-     XXX: use crc64 to minimize collisions? */
+     and merging should be ok here. */
   if (section_type == LTO_section_opts)
     strcpy (post, "");
+  else if (f != NULL) 
+    sprintf (post, "." HOST_WIDE_INT_PRINT_HEX_PURE, f->id);
   else
-    sprintf (post, ".%x", f ? f->id : crc32_string(0, get_random_seed (false)));
+    sprintf (post, "." HOST_WIDE_INT_PRINT_HEX_PURE, get_random_seed (false)); 
   return concat (LTO_SECTION_NAME_PREFIX, sep, add, post, NULL);
 }
 
diff --git a/gcc/lto-streamer.h b/gcc/lto-streamer.h
index 190d6a3..2564bd2 100644
--- a/gcc/lto-streamer.h
+++ b/gcc/lto-streamer.h
@@ -552,7 +552,7 @@ struct GTY(()) lto_file_decl_data
   struct lto_file_decl_data *next;
 
   /* Sub ID for merged objects. */
-  unsigned id;
+  unsigned HOST_WIDE_INT id;
 
   /* Symbol resolutions for this file */
   VEC(ld_plugin_symbol_resolution_t,heap) * GTY((skip)) resolutions;
diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
index 0b1dcb9..77eb1a1 100644
--- a/gcc/lto/lto.c
+++ b/gcc/lto/lto.c
@@ -976,9 +976,6 @@ lto_resolution_read (splay_tree file_ids, FILE *resolution, lto_file *file)
 	}
 
       file_data = (struct lto_file_decl_data *)nd->value;
-      if (cgraph_dump_file)
-	fprintf (cgraph_dump_file, "Adding resolution %u %u to id %x\n",
-		 index, r, file_data->id);
       VEC_safe_grow_cleared (ld_plugin_symbol_resolution_t, heap, 
 			     file_data->resolutions,
 			     max_index + 1);
@@ -990,14 +987,14 @@ lto_resolution_read (splay_tree file_ids, FILE *resolution, lto_file *file)
 /* Is the name for a id'ed LTO section? */
 
 static int 
-lto_section_with_id (const char *name, unsigned *id)
+lto_section_with_id (const char *name, unsigned HOST_WIDE_INT *id)
 {
   const char *s;
 
   if (strncmp (name, LTO_SECTION_NAME_PREFIX, strlen (LTO_SECTION_NAME_PREFIX)))
     return 0;
   s = strrchr (name, '.');
-  return s && sscanf (s, ".%x", id) == 1;
+  return s && sscanf (s, "." HOST_WIDE_INT_PRINT_HEX_PURE, id) == 1;
 }
 
 /* Create file_data of each sub file id */
@@ -1008,7 +1005,7 @@ create_subid_section_table (void **slot, void *data)
   struct lto_section_slot s_slot, *new_slot;
   struct lto_section_slot *ls = *(struct lto_section_slot **)slot;
   splay_tree file_ids = (splay_tree)data;
-  unsigned id;
+  unsigned HOST_WIDE_INT id;
   splay_tree_node nd;
   void **hash_slot;
   char *new_name;
@@ -1080,7 +1077,7 @@ static int lto_create_files_from_ids (splay_tree_node node, void *data)
 
   lto_file_finalize (file_data, lw->file);
   if (cgraph_dump_file)
-    fprintf (cgraph_dump_file, "Creating file %s with sub id %x\n", 
+    fprintf (cgraph_dump_file, "Creating file %s with sub id " HOST_WIDE_INT_PRINT_HEX "\n", 
 	     file_data->file_name, file_data->id);
   file_data->next = *lw->file_data;
   *lw->file_data = file_data;
diff --git a/gcc/toplev.c b/gcc/toplev.c
index 3688c09..78583fc 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -141,6 +141,9 @@ static const char *flag_random_seed;
    user has specified a particular random seed.  */
 unsigned local_tick;
 
+/* Random number for this compilation */
+HOST_WIDE_INT random_seed;
+
 /* -f flags.  */
 
 /* Generate code for GNU or NeXT Objective-C runtime environment.  */
@@ -251,7 +254,7 @@ announce_function (tree decl)
     }
 }
 
-/* Initialize local_tick with the time of day, or -1 if
+/* Initialize local_tick with a random number or -1 if
    flag_random_seed is set.  */
 
 static void
@@ -286,24 +289,28 @@ init_local_tick (void)
 static void
 init_random_seed (void)
 {
-  unsigned HOST_WIDE_INT value;
-  static char random_seed[HOST_BITS_PER_WIDE_INT / 4 + 3];
-
-  value = local_tick ^ getpid ();
+  if (flag_random_seed)
+    {
+      char *endp;
 
-  sprintf (random_seed, HOST_WIDE_INT_PRINT_HEX, value);
-  flag_random_seed = random_seed;
+      /* When the driver passed in a hex number don't crc it again */
+      random_seed = strtoul (flag_random_seed, &endp, 0);
+      if (!(endp > flag_random_seed && *endp == 0))
+        random_seed = crc32_string (0, flag_random_seed);
+    }
+  else if (!random_seed)
+    random_seed = local_tick ^ getpid ();  /* Old racey fallback method */
 }
 
-/* Obtain the random_seed string.  Unless NOINIT, initialize it if
+/* Obtain the random_seed.  Unless NOINIT, initialize it if
    it's not provided in the command line.  */
 
-const char *
+HOST_WIDE_INT
 get_random_seed (bool noinit)
 {
   if (!flag_random_seed && !noinit)
     init_random_seed ();
-  return flag_random_seed;
+  return random_seed;
 }
 
 /* Modify the random_seed string to VAL.  Return its previous
diff --git a/gcc/toplev.h b/gcc/toplev.h
index 2455dc0..588cfdb 100644
--- a/gcc/toplev.h
+++ b/gcc/toplev.h
@@ -77,7 +77,7 @@ extern bool set_src_pwd		       (const char *);
 
 /* Functions used to manipulate the random seed.  */
 
-extern const char *get_random_seed (bool);
+extern HOST_WIDE_INT get_random_seed (bool);
 extern const char *set_random_seed (const char *);
 
 #endif /* ! GCC_TOPLEV_H */
diff --git a/gcc/tree.c b/gcc/tree.c
index a53c9f4..6a2e9fb 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -8749,11 +8749,11 @@ get_file_function_name (const char *type)
 	file = input_filename;
 
       len = strlen (file);
-      q = (char *) alloca (9 * 2 + len + 1);
+      q = (char *) alloca (9 + 17 + len + 1);
       memcpy (q, file, len + 1);
 
-      sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
-	       crc32_string (0, get_random_seed (false)));
+      snprintf (q + len, 9 + 17 + 1, "_%08X_" HOST_WIDE_INT_PRINT_HEX, 
+		crc32_string (0, name), get_random_seed (false));
 
       p = q;
     }
-- 
1.7.5.4

Re: [PATCH 2/3] Use urandom to get random seed

[Richard Guenther]

On Wed, Sep 28, 2011 at 2:49 PM, Andi Kleen <andi@firstfloor.org> wrote:
> From: Andi Kleen <ak@linux.intel.com>
>
> When available use /dev/urandom to get the random seem. This will lower the probability
> of collisions.
>
> On other systems it will fallback to the old methods.
>
> Passes bootstrap + testsuite on x86_64. Ok?
>
> gcc/:
>
> * 2011-09-26   Andi Kleen <ak@linux.intel.com>
>
>        * toplev.c (init_local_tick): Try reading random seed from /dev/urandom
> ---
>  gcc/toplev.c |   12 +++++++++++-
>  1 files changed, 11 insertions(+), 1 deletions(-)
>
> diff --git a/gcc/toplev.c b/gcc/toplev.c
> index 78583fc..ab6b5a4 100644
> --- a/gcc/toplev.c
> +++ b/gcc/toplev.c
> @@ -262,7 +262,17 @@ init_local_tick (void)
>  {
>   if (!flag_random_seed)
>     {
> -      /* Get some more or less random data.  */
> +      /* Try urandom first. Time of day is too likely to collide.
> +        In case of any error we just use the local tick. */
> +
> +      int fd = open ("/dev/urandom", O_RDONLY);
> +      if (fd >= 0)
> +        {
> +          read (fd, &random_seed, sizeof (random_seed));

I suppose we might get interrupted before anything is read and
read can return with -1 (I suppose partial reads are quite unlikely
though)?  Thus, don't we need the usual EINTR loop?

If not, the patch is ok.

Thanks,
Richard.

> +          close (fd);
> +        }
> +
> +      /* Now get the tick anyways  */
>  #ifdef HAVE_GETTIMEOFDAY
>       {
>        struct timeval tv;
> --
> 1.7.5.4
>
>

Re: [PATCH 2/3] Use urandom to get random seed

[Andi Kleen]

> I suppose we might get interrupted before anything is read and
> read can return with -1 (I suppose partial reads are quite unlikely
> though)?  Thus, don't we need the usual EINTR loop?

When we get interrupted gcc will die. I don't think gcc handles any
asynchronous signals, right?

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH 2/3] Use urandom to get random seed

[Basile Starynkevitch]

On Wed, 28 Sep 2011 16:56:32 +0200
Andi Kleen <andi@firstfloor.org> wrote:

> > I suppose we might get interrupted before anything is read and
> > read can return with -1 (I suppose partial reads are quite unlikely
> > though)?  Thus, don't we need the usual EINTR loop?
> 
> When we get interrupted gcc will die. I don't think gcc handles any
> asynchronous signals, right?


That depends upon the signal. If we got SIGCHLD or SIGWINCH, the call to read probably
gets EINTR, but the signal is ignored unless explicitly handled.

So I would suggest testing for EINTR.

Besides, perhaps some plugins could install their signal handlers....

Regards.
-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: [PATCH 2/3] Use urandom to get random seed

[Andi Kleen]

> That depends upon the signal. If we got SIGCHLD or SIGWINCH, the call to read probably
> gets EINTR, but the signal is ignored unless explicitly handled.

ignored signals do not cause EINTR no.

And I don't think either gcc.c nor toplev.c can get SIGCHLD at this point.

-Andi

Re: [PATCH 1/3] Change random seeds to 64bit and drop re-crcing

[H.J. Lu]

On Wed, Sep 28, 2011 at 5:49 AM, Andi Kleen <andi@firstfloor.org> wrote:
> From: Andi Kleen <ak@linux.intel.com>
>
> I had some trouble with random build failures in a large LTO project
> and it turned out to be random seed collisions in a highly parallel build
> (thanks to Honza for suggesting that)
>
> There were multiple problems:
> - The way to generate the random seed is not very random (milliseconds time plus pid)
> and prone to collisions on highly parallel builds
> - It's only 32bit
> - Several users take the existing ascii seed and re-CRC32 it again, which
> doesn't exactly improve it.
>
> This patch changes that to:
> - Always use 64bit seeds as numbers (no re-crcing)
> - Change all users to use HOST_WIDE_INT
> - When the user specifies a random seed it's still crc32ed, but only in
> this case.
>
> Passes bootstrap + testsuite on x86_64-linux.
>
> gcc/cp:
>
> 2011-09-26   Andi Kleen <ak@linux.intel.com>
>
>        * repo.c (finish_repo): Use HOST_WIDE_INT_PRINT_HEX_PURE.
>
> gcc/:
>
> 2011-09-26   Andi Kleen <ak@linux.intel.com>
>
>        * hwint.h (HOST_WIDE_INT_PRINT_HEX_PURE): Add.
>        * lto-streamer.c (lto_get_section_name): Remove crc32_string.
>        Handle numerical random seed.
>        * lto-streamer.h (lto_file_decl_data): Change id to unsigned HOST_WIDE_INT.
>        * toplev.c (random_seed): Add.
>        (init_random_seed): Change for numerical random seed.
>        (get_random_seed): Return as HOST_WIDE_INT.
>        (set_random_seed): Crc32 existing string.
>        * toplev.h (get_random_seed): Change to numercal return.
>        * tree.c (get_file_function_name): Remove CRC. Handle numerical random seed.
>
> gcc/lto/:
>
> 2011-09-26   Andi Kleen <ak@linux.intel.com>
>
>        * lto.c (lto_resolution_read): Remove id dumping.
>        (lto_section_with_id): Turn id HOST_WIDE_ID.
>        (create_subid_section_table): Dito.

This patch caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50568

-- 
H.J.