Make it possible to disable and control hash key traversal randomization

Adds support for PERL_PERTURB_KEYS environment variable, which in turn allows one to control
the level of randomization applied to keys() and friends.

When PERL_PERTURB_KEYS is 0 we will not randomize key order at all. The
chance that keys() changes due to an insert will be the same as in
previous perls, basically only when the bucket size is changed.

When PERL_PERTURB_KEYS is 1 we will randomize keys in a non repeatedable
way. The chance that keys() changes due to an insert will be very high.
This is the most secure and default mode.

When PERL_PERTURB_KEYS is 2 we will randomize keys in a repeatedable way.
Repititive runs of the same program should produce the same output every
time. The chance that keys changes due to an insert will be very high.

This patch also makes PERL_HASH_SEED imply a non-default
PERL_PERTURB_KEYS setting. Setting PERL_HASH_SEED=0 (exactly one 0) implies
PERL_PERTURB_KEYS=0 (hash key randomization disabled), settng PERL_HASH_SEED
to any other value, implies PERL_PERTURB_KEYS=2 (deterministic/repeatable
hash key randomization). Specifying PERL_PERTURB_KEYS explicitly to a
different level overrides this behavior.

Includes changes to allow one to compile out various aspects of the
patch. One can compile such that PERL_PERTURB_KEYS is not respected, or
can compile without hash key traversal randomization at all. Note that
support for these modes is incomplete, and currently a few tests will
fail.

Also includes a new subroutine in Hash::Util::hash_traversal_mask()
which can be used to ensure a given hash produces a predictable key
order (assuming the same hash seed is in effect). This sub acts as a
getter and a setter.

NOTE - this patch lacks tests, but I lack tuits to get them done quickly,
so I am pushing this with the hope that others can add them afterwards.

1 files changed, 27 insertions, 4 deletions

diff --git a/pod/perldiag.pod b/pod/perldiag.pod
index 3d8212e96d..8bcdd331b0 100644
--- a/pod/perldiag.pod
+++ b/pod/perldiag.pod
@@ -4047,6 +4047,7 @@ on the version of Perl you are using because it is too new.
 Maybe the code needs to be updated, or maybe it is simply
 wrong and the version check should just be removed.
 
+
 =item perl: warning: Setting locale failed.
 
 (S) The whole warning message will look something like:
@@ -4069,12 +4070,26 @@ fix the problem, however, you will get the same error message each
 time you run Perl.  How to really fix the problem can be found in
 L<perllocale> section B<LOCALE PROBLEMS>.
 
-=item perl: warning: Non hex character in '$ENV{PERL_HASH_SEED}', seed only 
-partially set
+=item perl: warning: Non hex character in '$ENV{PERL_HASH_SEED}', seed only partially set
 
 (W) PERL_HASH_SEED should match /^\s*(?:0x)?[0-9a-fA-F]+\s*\z/ but it
-contained a non hex character. This could mean your hash randomization
-is not being set correctly.
+contained a non hex character. This could mean you are not using the hash
+seed you think you are.
+
+=item perl: warning: strange setting in '$ENV{PERL_PERTURB_KEYS}': '%s'
+
+(W) Perl was run with the environment variable PERL_PERTURB_KEYS defined
+but containing an unexpected value. The legal values of this setting
+are as follows.
+
+  Numeric | String        | Result
+  --------+---------------+-----------------------------------------
+  0       | NO            | Disables key traversal randomization
+  1       | RANDOM        | Enables full key traversal randomization
+  2       | DETERMINISTIC | Enables repeatable key traversal randomization
+
+Both numeric and string values are accepted, but note that string values are
+case sensitive. The default for this setting is "RANDOM" or 1.
 
 =item pid %x not a child
 
@@ -5090,6 +5105,14 @@ F<PERL_ENV_TABLES> (see L<perlvms>) so that the environ array isn't the
 target of the change to
 %ENV which produced the warning.
 
+=item This Perl has not been built with support for randomized hash key traversal but something called Perl_hv_rand_set().
+
+(F) Something has attempted to use an internal API call which
+depends on Perl being compiled with the default support for randomized hash
+key traversal, but this Perl has been compiled without it. You should
+report this warning to the relevant upstream party, or recompile perl
+with default options.
+
 =item thread failed to start: %s
 
 (W threads)(S) The entry point function of threads->create() failed for some reason.